regexp.c:rd_calloc: 139| 2.08k|static RD_INLINE RD_UNUSED void *rd_calloc(size_t num, size_t sz) { 140| 2.08k| void *p = calloc(num, sz); 141| 2.08k| rd_assert(p); ------------------ | | 159| 2.08k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (141:9): [True: 0, False: 2.08k] | Branch (141:9): [True: 2.08k, False: 0] ------------------ 142| 2.08k| return p; 143| 2.08k|} regexp.c:rd_malloc: 145| 3.04k|static RD_INLINE RD_UNUSED void *rd_malloc(size_t sz) { 146| 3.04k| void *p = malloc(sz); 147| 3.04k| rd_assert(p); ------------------ | | 159| 3.04k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (147:9): [True: 0, False: 3.04k] | Branch (147:9): [True: 3.04k, False: 0] ------------------ 148| 3.04k| return p; 149| 3.04k|} regexp.c:rd_free: 157| 5.12k|static RD_INLINE RD_UNUSED void rd_free(void *ptr) { 158| 5.12k| free(ptr); 159| 5.12k|} re_regcomp: 1004| 2.09k|Reprog *re_regcomp(const char *pattern, int cflags, const char **errorp) { 1005| 2.09k| Reprog *prog; 1006| 2.09k| Restate *g; 1007| 2.09k| Renode *node; 1008| 2.09k| Reinst *split, *jump; 1009| 2.09k| int i; 1010| 2.09k| unsigned int ncount; 1011| 2.09k| size_t pattern_len = strlen(pattern); 1012| | 1013| 2.09k| if (pattern_len > 10000) { ------------------ | Branch (1013:13): [True: 10, False: 2.08k] ------------------ 1014| | /* Avoid stack exhaustion in recursive parseatom() et.al. */ 1015| 10| if (errorp) ------------------ | Branch (1015:21): [True: 10, False: 0] ------------------ 1016| 10| *errorp = "regexp pattern too long (max 10000)"; 1017| 10| return NULL; 1018| 10| } 1019| | 1020| 2.08k| prog = rd_calloc(1, sizeof(Reprog)); 1021| 2.08k| g = &prog->g; 1022| 2.08k| g->prog = prog; 1023| 2.08k| g->pstart = g->pend = rd_malloc(sizeof(Renode) * pattern_len * 2); 1024| | 1025| 2.08k| if (setjmp(g->kaboom)) { ------------------ | Branch (1025:13): [True: 1.12k, False: 961] ------------------ 1026| 1.12k| if (errorp) ------------------ | Branch (1026:21): [True: 1.12k, False: 0] ------------------ 1027| 1.12k| *errorp = g->error; 1028| 1.12k| rd_free(g->pstart); 1029| 1.12k| rd_free(prog); 1030| 1.12k| return NULL; 1031| 1.12k| } 1032| | 1033| 961| g->source = pattern; 1034| 961| g->ncclass = 0; 1035| 961| g->nsub = 1; 1036| 34.2k| for (i = 0; i < MAXSUB; ++i) ------------------ | | 45| 34.2k|#define MAXSUB REG_MAXSUB ------------------ | Branch (1036:21): [True: 33.2k, False: 961] ------------------ 1037| 33.2k| g->sub[i] = 0; 1038| | 1039| 961| g->prog->flags = cflags; 1040| | 1041| 961| next(g); 1042| 961| node = parsealt(g); 1043| 961| if (g->lookahead == ')') ------------------ | Branch (1043:13): [True: 17, False: 944] ------------------ 1044| 17| die(g, "unmatched ')'"); 1045| 961| if (g->lookahead != 0) ------------------ | Branch (1045:13): [True: 0, False: 961] ------------------ 1046| 0| die(g, "syntax error"); 1047| | 1048| 961| g->prog->nsub = g->nsub; 1049| 961| ncount = count(node); 1050| 961| if (ncount > 10000) ------------------ | Branch (1050:13): [True: 40, False: 921] ------------------ 1051| 40| die(g, "regexp graph too large"); 1052| 961| g->prog->start = g->prog->end = 1053| 961| rd_malloc((ncount + 6) * sizeof(Reinst)); 1054| | 1055| 961| split = emit(g->prog, I_SPLIT); 1056| 961| split->x = split + 3; 1057| 961| split->y = split + 1; 1058| 961| emit(g->prog, I_ANYNL); 1059| 961| jump = emit(g->prog, I_JUMP); 1060| 961| jump->x = split; 1061| 961| emit(g->prog, I_LPAR); 1062| 961| compile(g->prog, node); 1063| 961| emit(g->prog, I_RPAR); 1064| 961| emit(g->prog, I_END); 1065| | 1066| |#ifdef TEST 1067| | dumpnode(node); 1068| | putchar('\n'); 1069| | dumpprog(g->prog); 1070| |#endif 1071| | 1072| 961| rd_free(g->pstart); 1073| | 1074| 961| if (errorp) ------------------ | Branch (1074:13): [True: 961, False: 0] ------------------ 1075| 961| *errorp = NULL; 1076| 961| return g->prog; 1077| 2.08k|} re_regfree: 1079| 961|void re_regfree(Reprog *prog) { 1080| 961| if (prog) { ------------------ | Branch (1080:13): [True: 961, False: 0] ------------------ 1081| 961| rd_free(prog->start); 1082| 961| rd_free(prog); 1083| 961| } 1084| 961|} regexp.c:next: 529| 257k|static void next(Restate *g) { 530| 257k| g->lookahead = lex(g); 531| 257k|} regexp.c:lex: 370| 257k|static int lex(Restate *g) { 371| 257k| int quoted = nextrune(g); 372| 257k| if (quoted) { ------------------ | Branch (372:13): [True: 3.50k, False: 254k] ------------------ 373| 3.50k| switch (g->yychar) { ------------------ | Branch (373:25): [True: 2.05k, False: 1.45k] ------------------ 374| 202| case 'b': ------------------ | Branch (374:17): [True: 202, False: 3.30k] ------------------ 375| 202| return L_WORD; 376| 257| case 'B': ------------------ | Branch (376:17): [True: 257, False: 3.24k] ------------------ 377| 257| return L_NWORD; 378| 75| case 'd': ------------------ | Branch (378:17): [True: 75, False: 3.42k] ------------------ 379| 75| newcclass(g); 380| 75| addranges_d(g); 381| 75| return L_CCLASS; 382| 94| case 's': ------------------ | Branch (382:17): [True: 94, False: 3.41k] ------------------ 383| 94| newcclass(g); 384| 94| addranges_s(g); 385| 94| return L_CCLASS; 386| 98| case 'w': ------------------ | Branch (386:17): [True: 98, False: 3.40k] ------------------ 387| 98| newcclass(g); 388| 98| addranges_w(g); 389| 98| return L_CCLASS; 390| 75| case 'D': ------------------ | Branch (390:17): [True: 75, False: 3.42k] ------------------ 391| 75| newcclass(g); 392| 75| addranges_d(g); 393| 75| return L_NCCLASS; 394| 139| case 'S': ------------------ | Branch (394:17): [True: 139, False: 3.36k] ------------------ 395| 139| newcclass(g); 396| 139| addranges_s(g); 397| 139| return L_NCCLASS; 398| 68| case 'W': ------------------ | Branch (398:17): [True: 68, False: 3.43k] ------------------ 399| 68| newcclass(g); 400| 68| addranges_w(g); 401| 68| return L_NCCLASS; 402| 1.04k| case '0': ------------------ | Branch (402:17): [True: 1.04k, False: 2.46k] ------------------ 403| 1.04k| g->yychar = 0; 404| 1.04k| return L_CHAR; 405| 3.50k| } 406| 1.45k| if (g->yychar >= '0' && g->yychar <= '9') { ------------------ | Branch (406:21): [True: 1.22k, False: 225] | Branch (406:41): [True: 1.00k, False: 226] ------------------ 407| 1.00k| g->yychar -= '0'; 408| 1.00k| if (*g->source >= '0' && *g->source <= '9') ------------------ | Branch (408:29): [True: 685, False: 317] | Branch (408:50): [True: 206, False: 479] ------------------ 409| 206| g->yychar = g->yychar * 10 + *g->source++ - '0'; 410| 1.00k| return L_REF; 411| 1.00k| } 412| 451| return L_CHAR; 413| 1.45k| } 414| | 415| 254k| switch (g->yychar) { ------------------ | Branch (415:17): [True: 75.2k, False: 178k] ------------------ 416| 1.13k| case 0: ------------------ | Branch (416:9): [True: 1.13k, False: 253k] ------------------ 417| 2.03k| case '$': ------------------ | Branch (417:9): [True: 903, False: 253k] ------------------ 418| 4.17k| case ')': ------------------ | Branch (418:9): [True: 2.14k, False: 252k] ------------------ 419| 7.87k| case '*': ------------------ | Branch (419:9): [True: 3.69k, False: 250k] ------------------ 420| 8.61k| case '+': ------------------ | Branch (420:9): [True: 743, False: 253k] ------------------ 421| 11.4k| case '.': ------------------ | Branch (421:9): [True: 2.86k, False: 251k] ------------------ 422| 14.9k| case '?': ------------------ | Branch (422:9): [True: 3.47k, False: 250k] ------------------ 423| 58.4k| case '^': ------------------ | Branch (423:9): [True: 43.5k, False: 210k] ------------------ 424| 75.2k| case '|': ------------------ | Branch (424:9): [True: 16.8k, False: 237k] ------------------ 425| 75.2k| return g->yychar; 426| 254k| } 427| | 428| 178k| if (g->yychar == '{') ------------------ | Branch (428:13): [True: 2.02k, False: 176k] ------------------ 429| 2.02k| return lexcount(g); 430| 176k| if (g->yychar == '[') ------------------ | Branch (430:13): [True: 799, False: 175k] ------------------ 431| 799| return lexclass(g); 432| 175k| if (g->yychar == '(') { ------------------ | Branch (432:13): [True: 3.72k, False: 172k] ------------------ 433| 3.72k| if (g->source[0] == '?') { ------------------ | Branch (433:21): [True: 2.61k, False: 1.11k] ------------------ 434| 2.61k| if (g->source[1] == ':') { ------------------ | Branch (434:29): [True: 828, False: 1.78k] ------------------ 435| 828| g->source += 2; 436| 828| return L_NC; 437| 828| } 438| 1.78k| if (g->source[1] == '=') { ------------------ | Branch (438:29): [True: 786, False: 1.00k] ------------------ 439| 786| g->source += 2; 440| 786| return L_PLA; 441| 786| } 442| 1.00k| if (g->source[1] == '!') { ------------------ | Branch (442:29): [True: 980, False: 21] ------------------ 443| 980| g->source += 2; 444| 980| return L_NLA; 445| 980| } 446| 1.00k| } 447| 1.13k| return '('; 448| 3.72k| } 449| | 450| 172k| return L_CHAR; 451| 175k|} regexp.c:nextrune: 131| 265k|static int nextrune(Restate *g) { 132| 265k| g->source += chartorune(&g->yychar, g->source); 133| 265k| if (g->yychar == '\\') { ------------------ | Branch (133:13): [True: 9.84k, False: 255k] ------------------ 134| 9.84k| g->source += chartorune(&g->yychar, g->source); 135| 9.84k| switch (g->yychar) { ------------------ | Branch (135:25): [True: 4.36k, False: 5.48k] ------------------ 136| 5| case 0: ------------------ | Branch (136:17): [True: 5, False: 9.84k] ------------------ 137| 5| die(g, "unterminated escape sequence"); 138| 200| case 'f': ------------------ | Branch (138:17): [True: 195, False: 9.65k] ------------------ 139| 200| g->yychar = '\f'; 140| 200| return 0; 141| 284| case 'n': ------------------ | Branch (141:17): [True: 284, False: 9.56k] ------------------ 142| 284| g->yychar = '\n'; 143| 284| return 0; 144| 195| case 'r': ------------------ | Branch (144:17): [True: 195, False: 9.65k] ------------------ 145| 195| g->yychar = '\r'; 146| 195| return 0; 147| 194| case 't': ------------------ | Branch (147:17): [True: 194, False: 9.65k] ------------------ 148| 194| g->yychar = '\t'; 149| 194| return 0; 150| 194| case 'v': ------------------ | Branch (150:17): [True: 194, False: 9.65k] ------------------ 151| 194| g->yychar = '\v'; 152| 194| return 0; 153| 197| case 'c': ------------------ | Branch (153:17): [True: 197, False: 9.65k] ------------------ 154| 197| g->yychar = (*g->source++) & 31; 155| 197| return 0; 156| 1.46k| case 'x': ------------------ | Branch (156:17): [True: 1.46k, False: 8.38k] ------------------ 157| 1.46k| g->yychar = hex(g, *g->source++) << 4; 158| 1.46k| g->yychar += hex(g, *g->source++); 159| 1.46k| if (g->yychar == 0) { ------------------ | Branch (159:29): [True: 382, False: 1.08k] ------------------ 160| 382| g->yychar = '0'; 161| 382| return 1; 162| 382| } 163| 1.08k| return 0; 164| 1.63k| case 'u': ------------------ | Branch (164:17): [True: 1.63k, False: 8.21k] ------------------ 165| 1.63k| g->yychar = hex(g, *g->source++) << 12; 166| 1.63k| g->yychar += hex(g, *g->source++) << 8; 167| 1.63k| g->yychar += hex(g, *g->source++) << 4; 168| 1.63k| g->yychar += hex(g, *g->source++); 169| 1.63k| if (g->yychar == 0) { ------------------ | Branch (169:29): [True: 453, False: 1.17k] ------------------ 170| 453| g->yychar = '0'; 171| 453| return 1; 172| 453| } 173| 1.17k| return 0; 174| 9.84k| } 175| 5.48k| if (strchr(ESCAPES, g->yychar)) ------------------ | | 129| 5.48k|#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" ------------------ | Branch (175:21): [True: 4.99k, False: 491] ------------------ 176| 4.99k| return 1; 177| 491| if (isalpharune(g->yychar) || ------------------ | Branch (177:21): [True: 13, False: 478] ------------------ 178| 478| g->yychar == '_') /* check identity escape */ ------------------ | Branch (178:21): [True: 1, False: 477] ------------------ 179| 14| die(g, "invalid escape character"); 180| 491| return 0; 181| 5.48k| } 182| 255k| return 0; 183| 265k|} regexp.c:chartorune: 37| 275k|static int chartorune(Rune *r, const char *s) { 38| | /* TODO: Add UTF-8 decoding */ 39| 275k| *r = *s; 40| 275k| return 1; 41| 275k|} regexp.c:hex: 111| 9.17k|static int hex(Restate *g, int c) { 112| 9.17k| if (c >= '0' && c <= '9') ------------------ | Branch (112:13): [True: 9.00k, False: 166] | Branch (112:25): [True: 3.47k, False: 5.53k] ------------------ 113| 3.47k| return c - '0'; 114| 5.69k| if (c >= 'a' && c <= 'f') ------------------ | Branch (114:13): [True: 2.42k, False: 3.26k] | Branch (114:25): [True: 2.39k, False: 36] ------------------ 115| 2.39k| return c - 'a' + 0xA; 116| 3.30k| if (c >= 'A' && c <= 'F') ------------------ | Branch (116:13): [True: 3.11k, False: 188] | Branch (116:25): [True: 3.04k, False: 72] ------------------ 117| 3.04k| return c - 'A' + 0xA; 118| 260| die(g, "invalid escape sequence"); 119| 260| return 0; 120| 3.30k|} regexp.c:isalpharune: 25| 491|static int isalpharune(Rune c) { 26| | /* TODO: Add unicode support */ 27| 491| return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); ------------------ | Branch (27:17): [True: 265, False: 226] | Branch (27:29): [True: 6, False: 259] | Branch (27:43): [True: 249, False: 236] | Branch (27:55): [True: 7, False: 242] ------------------ 28| 491|} regexp.c:newcclass: 218| 1.34k|static void newcclass(Restate *g) { 219| 1.34k| if (g->ncclass >= nelem(g->prog->cclass)) ------------------ | | 21| 1.34k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (219:13): [True: 7, False: 1.34k] ------------------ 220| 7| die(g, "too many character classes"); 221| 1.34k| g->yycc = g->prog->cclass + g->ncclass++; 222| 1.34k| g->yycc->end = g->yycc->spans; 223| 1.34k|} regexp.c:addranges_d: 234| 1.01k|static void addranges_d(Restate *g) { 235| 1.01k| addrange(g, '0', '9'); 236| 1.01k|} regexp.c:addrange: 225| 9.14k|static void addrange(Restate *g, Rune a, Rune b) { 226| 9.14k| if (a > b) ------------------ | Branch (226:13): [True: 51, False: 9.09k] ------------------ 227| 51| die(g, "invalid character class range"); 228| 9.14k| if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) ------------------ | | 21| 9.14k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (228:13): [True: 44, False: 9.10k] ------------------ 229| 44| die(g, "too many character class ranges"); 230| 9.14k| *g->yycc->end++ = a; 231| 9.14k| *g->yycc->end++ = b; 232| 9.14k|} regexp.c:addranges_s: 243| 479|static void addranges_s(Restate *g) { 244| 479| addrange(g, 0x9, 0x9); 245| 479| addrange(g, 0xA, 0xD); 246| 479| addrange(g, 0x20, 0x20); 247| 479| addrange(g, 0xA0, 0xA0); 248| 479| addrange(g, 0x2028, 0x2029); 249| 479| addrange(g, 0xFEFF, 0xFEFF); 250| 479|} regexp.c:addranges_w: 262| 276|static void addranges_w(Restate *g) { 263| 276| addrange(g, '0', '9'); 264| 276| addrange(g, 'A', 'Z'); 265| 276| addrange(g, '_', '_'); 266| 276| addrange(g, 'a', 'z'); 267| 276|} regexp.c:lexcount: 185| 2.02k|static int lexcount(Restate *g) { 186| 2.02k| g->yychar = *g->source++; 187| | 188| 2.02k| g->yymin = dec(g, g->yychar); 189| 2.02k| g->yychar = *g->source++; 190| 3.75k| while (g->yychar != ',' && g->yychar != '}') { ------------------ | Branch (190:16): [True: 2.88k, False: 876] | Branch (190:36): [True: 1.73k, False: 1.14k] ------------------ 191| 1.73k| g->yymin = g->yymin * 10 + dec(g, g->yychar); 192| 1.73k| g->yychar = *g->source++; 193| 1.73k| } 194| 2.02k| if (g->yymin >= REPINF) ------------------ | | 43| 2.02k|#define REPINF 255 ------------------ | Branch (194:13): [True: 20, False: 2.00k] ------------------ 195| 20| die(g, "numeric overflow"); 196| | 197| 2.02k| if (g->yychar == ',') { ------------------ | Branch (197:13): [True: 817, False: 1.20k] ------------------ 198| 817| g->yychar = *g->source++; 199| 817| if (g->yychar == '}') { ------------------ | Branch (199:21): [True: 254, False: 563] ------------------ 200| 254| g->yymax = REPINF; ------------------ | | 43| 254|#define REPINF 255 ------------------ 201| 563| } else { 202| 563| g->yymax = dec(g, g->yychar); 203| 563| g->yychar = *g->source++; 204| 1.34k| while (g->yychar != '}') { ------------------ | Branch (204:32): [True: 781, False: 563] ------------------ 205| 781| g->yymax = g->yymax * 10 + dec(g, g->yychar); 206| 781| g->yychar = *g->source++; 207| 781| } 208| 563| if (g->yymax >= REPINF) ------------------ | | 43| 563|#define REPINF 255 ------------------ | Branch (208:29): [True: 16, False: 547] ------------------ 209| 16| die(g, "numeric overflow"); 210| 563| } 211| 1.20k| } else { 212| 1.20k| g->yymax = g->yymin; 213| 1.20k| } 214| | 215| 2.02k| return L_COUNT; 216| 2.02k|} regexp.c:dec: 122| 5.10k|static int dec(Restate *g, int c) { 123| 5.10k| if (c >= '0' && c <= '9') ------------------ | Branch (123:13): [True: 5.01k, False: 83] | Branch (123:25): [True: 4.98k, False: 33] ------------------ 124| 4.98k| return c - '0'; 125| 116| die(g, "invalid quantifier"); 126| 116| return 0; 127| 5.10k|} regexp.c:lexclass: 277| 799|static int lexclass(Restate *g) { 278| 799| int type = L_CCLASS; 279| 799| int quoted, havesave, havedash; 280| 799| Rune save = 0; 281| | 282| 799| newcclass(g); 283| | 284| 799| quoted = nextrune(g); 285| 799| if (!quoted && g->yychar == '^') { ------------------ | Branch (285:13): [True: 569, False: 230] | Branch (285:24): [True: 34, False: 535] ------------------ 286| 34| type = L_NCCLASS; 287| 34| quoted = nextrune(g); 288| 34| } 289| | 290| 799| havesave = havedash = 0; 291| 7.52k| for (;;) { 292| 7.52k| if (g->yychar == 0) ------------------ | Branch (292:21): [True: 228, False: 7.29k] ------------------ 293| 228| die(g, "unterminated character class"); 294| 7.52k| if (!quoted && g->yychar == ']') ------------------ | Branch (294:21): [True: 4.96k, False: 2.55k] | Branch (294:32): [True: 477, False: 4.49k] ------------------ 295| 477| break; 296| | 297| 7.04k| if (!quoted && g->yychar == '-') { ------------------ | Branch (297:21): [True: 4.49k, False: 2.55k] | Branch (297:32): [True: 2.33k, False: 2.15k] ------------------ 298| 2.33k| if (havesave) { ------------------ | Branch (298:29): [True: 1.70k, False: 626] ------------------ 299| 1.70k| if (havedash) { ------------------ | Branch (299:37): [True: 500, False: 1.20k] ------------------ 300| 500| addrange(g, save, '-'); 301| 500| havesave = havedash = 0; 302| 1.20k| } else { 303| 1.20k| havedash = 1; 304| 1.20k| } 305| 1.70k| } else { 306| 626| save = '-'; 307| 626| havesave = 1; 308| 626| } 309| 4.71k| } else if (quoted && strchr("DSWdsw", g->yychar)) { ------------------ | Branch (309:28): [True: 2.32k, False: 2.38k] | Branch (309:38): [True: 1.64k, False: 687] ------------------ 310| 1.64k| if (havesave) { ------------------ | Branch (310:29): [True: 541, False: 1.10k] ------------------ 311| 541| addrange(g, save, save); 312| 541| if (havedash) ------------------ | Branch (312:37): [True: 195, False: 346] ------------------ 313| 195| addrange(g, '-', '-'); 314| 541| } 315| 1.64k| switch (g->yychar) { ------------------ | Branch (315:33): [True: 1.63k, False: 3] ------------------ 316| 870| case 'd': ------------------ | Branch (316:25): [True: 870, False: 772] ------------------ 317| 870| addranges_d(g); 318| 870| break; 319| 248| case 's': ------------------ | Branch (319:25): [True: 248, False: 1.39k] ------------------ 320| 248| addranges_s(g); 321| 248| break; 322| 112| case 'w': ------------------ | Branch (322:25): [True: 112, False: 1.53k] ------------------ 323| 112| addranges_w(g); 324| 112| break; 325| 320| case 'D': ------------------ | Branch (325:25): [True: 320, False: 1.32k] ------------------ 326| 320| addranges_D(g); 327| 320| break; 328| 5| case 'S': ------------------ | Branch (328:25): [True: 5, False: 1.63k] ------------------ 329| 5| addranges_S(g); 330| 5| break; 331| 84| case 'W': ------------------ | Branch (331:25): [True: 84, False: 1.55k] ------------------ 332| 84| addranges_W(g); 333| 84| break; 334| 1.64k| } 335| 1.60k| havesave = havedash = 0; 336| 3.07k| } else { 337| 3.07k| if (quoted) { ------------------ | Branch (337:29): [True: 687, False: 2.38k] ------------------ 338| 687| if (g->yychar == 'b') ------------------ | Branch (338:37): [True: 198, False: 489] ------------------ 339| 198| g->yychar = '\b'; 340| 489| else if (g->yychar == '0') ------------------ | Branch (340:42): [True: 194, False: 295] ------------------ 341| 194| g->yychar = 0; 342| | /* else identity escape */ 343| 687| } 344| 3.07k| if (havesave) { ------------------ | Branch (344:29): [True: 1.66k, False: 1.40k] ------------------ 345| 1.66k| if (havedash) { ------------------ | Branch (345:37): [True: 454, False: 1.21k] ------------------ 346| 454| addrange(g, save, g->yychar); 347| 454| havesave = havedash = 0; 348| 1.21k| } else { 349| 1.21k| addrange(g, save, save); 350| 1.21k| save = g->yychar; 351| 1.21k| } 352| 1.66k| } else { 353| 1.40k| save = g->yychar; 354| 1.40k| havesave = 1; 355| 1.40k| } 356| 3.07k| } 357| | 358| 7.01k| quoted = nextrune(g); 359| 7.01k| } 360| | 361| 762| if (havesave) { ------------------ | Branch (361:13): [True: 176, False: 586] ------------------ 362| 176| addrange(g, save, save); 363| 176| if (havedash) ------------------ | Branch (363:21): [True: 51, False: 125] ------------------ 364| 51| addrange(g, '-', '-'); 365| 176| } 366| | 367| 762| return type; 368| 799|} regexp.c:addranges_D: 238| 320|static void addranges_D(Restate *g) { 239| 320| addrange(g, 0, '0' - 1); 240| 320| addrange(g, '9' + 1, 0xFFFF); 241| 320|} regexp.c:addranges_S: 252| 5|static void addranges_S(Restate *g) { 253| 5| addrange(g, 0, 0x9 - 1); 254| 5| addrange(g, 0x9 + 1, 0xA - 1); 255| 5| addrange(g, 0xD + 1, 0x20 - 1); 256| 5| addrange(g, 0x20 + 1, 0xA0 - 1); 257| 5| addrange(g, 0xA0 + 1, 0x2028 - 1); 258| 5| addrange(g, 0x2029 + 1, 0xFEFF - 1); 259| 5| addrange(g, 0xFEFF + 1, 0xFFFF); 260| 5|} regexp.c:addranges_W: 269| 84|static void addranges_W(Restate *g) { 270| 84| addrange(g, 0, '0' - 1); 271| 84| addrange(g, '9' + 1, 'A' - 1); 272| 84| addrange(g, 'Z' + 1, '_' - 1); 273| 84| addrange(g, '_' + 1, 'a' - 1); 274| 84| addrange(g, 'z' + 1, 0xFFFF); 275| 84|} regexp.c:parsealt: 654| 5.19k|static Renode *parsealt(Restate *g) { 655| 5.19k| Renode *alt, *x; 656| 5.19k| alt = parsecat(g); 657| 21.9k| while (re_accept(g, '|')) { ------------------ | Branch (657:16): [True: 16.8k, False: 5.19k] ------------------ 658| 16.8k| x = alt; 659| 16.8k| alt = newnode(g, P_ALT); 660| 16.8k| alt->x = x; 661| 16.8k| alt->y = parsecat(g); 662| 16.8k| } 663| 5.19k| return alt; 664| 5.19k|} regexp.c:parsecat: 638| 21.9k|static Renode *parsecat(Restate *g) { 639| 21.9k| Renode *cat, *x; 640| 21.9k| if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { ------------------ | Branch (640:13): [True: 21.8k, False: 106] | Branch (640:29): [True: 5.87k, False: 16.0k] | Branch (640:52): [True: 4.52k, False: 1.35k] ------------------ 641| 4.52k| cat = parserep(g); 642| 227k| while (g->lookahead && g->lookahead != '|' && ------------------ | Branch (642:24): [True: 224k, False: 2.94k] | Branch (642:40): [True: 223k, False: 792] ------------------ 643| 223k| g->lookahead != ')') { ------------------ | Branch (643:24): [True: 222k, False: 789] ------------------ 644| 222k| x = cat; 645| 222k| cat = newnode(g, P_CAT); 646| 222k| cat->x = x; 647| 222k| cat->y = parserep(g); 648| 222k| } 649| 4.52k| return cat; 650| 4.52k| } 651| 17.4k| return NULL; 652| 21.9k|} regexp.c:parserep: 609| 227k|static Renode *parserep(Restate *g) { 610| 227k| Renode *atom; 611| | 612| 227k| if (re_accept(g, '^')) ------------------ | Branch (612:13): [True: 43.5k, False: 183k] ------------------ 613| 43.5k| return newnode(g, P_BOL); 614| 183k| if (re_accept(g, '$')) ------------------ | Branch (614:13): [True: 903, False: 182k] ------------------ 615| 903| return newnode(g, P_EOL); 616| 182k| if (re_accept(g, L_WORD)) ------------------ | Branch (616:13): [True: 202, False: 182k] ------------------ 617| 202| return newnode(g, P_WORD); 618| 182k| if (re_accept(g, L_NWORD)) ------------------ | Branch (618:13): [True: 257, False: 182k] ------------------ 619| 257| return newnode(g, P_NWORD); 620| | 621| 182k| atom = parseatom(g); 622| 182k| if (g->lookahead == L_COUNT) { ------------------ | Branch (622:13): [True: 1.79k, False: 180k] ------------------ 623| 1.79k| int min = g->yymin, max = g->yymax; 624| 1.79k| next(g); 625| 1.79k| if (max < min) ------------------ | Branch (625:21): [True: 7, False: 1.78k] ------------------ 626| 7| die(g, "invalid quantifier"); 627| 1.79k| return newrep(g, atom, re_accept(g, '?'), min, max); 628| 1.79k| } 629| 180k| if (re_accept(g, '*')) ------------------ | Branch (629:13): [True: 3.68k, False: 176k] ------------------ 630| 3.68k| return newrep(g, atom, re_accept(g, '?'), 0, REPINF); ------------------ | | 43| 3.68k|#define REPINF 255 ------------------ 631| 176k| if (re_accept(g, '+')) ------------------ | Branch (631:13): [True: 731, False: 176k] ------------------ 632| 731| return newrep(g, atom, re_accept(g, '?'), 1, REPINF); ------------------ | | 43| 731|#define REPINF 255 ------------------ 633| 176k| if (re_accept(g, '?')) ------------------ | Branch (633:13): [True: 616, False: 175k] ------------------ 634| 616| return newrep(g, atom, re_accept(g, '?'), 0, 1); 635| 175k| return atom; 636| 176k|} regexp.c:parseatom: 543| 182k|static Renode *parseatom(Restate *g) { 544| 182k| Renode *atom; 545| 182k| if (g->lookahead == L_CHAR) { ------------------ | Branch (545:13): [True: 173k, False: 8.74k] ------------------ 546| 173k| atom = newnode(g, P_CHAR); 547| 173k| atom->c = g->yychar; 548| 173k| next(g); 549| 173k| return atom; 550| 173k| } 551| 8.74k| if (g->lookahead == L_CCLASS) { ------------------ | Branch (551:13): [True: 709, False: 8.03k] ------------------ 552| 709| atom = newnode(g, P_CCLASS); 553| 709| atom->cc = g->yycc; 554| 709| next(g); 555| 709| return atom; 556| 709| } 557| 8.03k| if (g->lookahead == L_NCCLASS) { ------------------ | Branch (557:13): [True: 307, False: 7.73k] ------------------ 558| 307| atom = newnode(g, P_NCCLASS); 559| 307| atom->cc = g->yycc; 560| 307| next(g); 561| 307| return atom; 562| 307| } 563| 7.73k| if (g->lookahead == L_REF) { ------------------ | Branch (563:13): [True: 1.00k, False: 6.73k] ------------------ 564| 1.00k| atom = newnode(g, P_REF); 565| 1.00k| if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) ------------------ | Branch (565:21): [True: 0, False: 1.00k] | Branch (565:39): [True: 21, False: 980] | Branch (565:62): [True: 12, False: 968] ------------------ 566| 33| die(g, "invalid back-reference"); 567| 1.00k| atom->n = g->yychar; 568| 1.00k| atom->x = g->sub[g->yychar]; 569| 1.00k| next(g); 570| 1.00k| return atom; 571| 1.00k| } 572| 6.73k| if (re_accept(g, '.')) ------------------ | Branch (572:13): [True: 2.86k, False: 3.86k] ------------------ 573| 2.86k| return newnode(g, P_ANY); 574| 3.86k| if (re_accept(g, '(')) { ------------------ | Branch (574:13): [True: 1.13k, False: 2.73k] ------------------ 575| 1.13k| atom = newnode(g, P_PAR); 576| 1.13k| if (g->nsub == MAXSUB) ------------------ | | 45| 1.13k|#define MAXSUB REG_MAXSUB ------------------ | Branch (576:21): [True: 6, False: 1.12k] ------------------ 577| 6| die(g, "too many captures"); 578| 1.13k| atom->n = g->nsub++; 579| 1.13k| atom->x = parsealt(g); 580| 1.13k| g->sub[atom->n] = atom; 581| 1.13k| if (!re_accept(g, ')')) ------------------ | Branch (581:21): [True: 50, False: 1.08k] ------------------ 582| 50| die(g, "unmatched '('"); 583| 1.13k| return atom; 584| 1.13k| } 585| 2.73k| if (re_accept(g, L_NC)) { ------------------ | Branch (585:13): [True: 828, False: 1.90k] ------------------ 586| 828| atom = parsealt(g); 587| 828| if (!re_accept(g, ')')) ------------------ | Branch (587:21): [True: 14, False: 814] ------------------ 588| 14| die(g, "unmatched '('"); 589| 828| return atom; 590| 828| } 591| 1.90k| if (re_accept(g, L_PLA)) { ------------------ | Branch (591:13): [True: 786, False: 1.11k] ------------------ 592| 786| atom = newnode(g, P_PLA); 593| 786| atom->x = parsealt(g); 594| 786| if (!re_accept(g, ')')) ------------------ | Branch (594:21): [True: 9, False: 777] ------------------ 595| 9| die(g, "unmatched '('"); 596| 786| return atom; 597| 786| } 598| 1.11k| if (re_accept(g, L_NLA)) { ------------------ | Branch (598:13): [True: 980, False: 137] ------------------ 599| 980| atom = newnode(g, P_NLA); 600| 980| atom->x = parsealt(g); 601| 980| if (!re_accept(g, ')')) ------------------ | Branch (601:21): [True: 9, False: 971] ------------------ 602| 9| die(g, "unmatched '('"); 603| 980| return atom; 604| 980| } 605| 137| die(g, "syntax error"); 606| | return NULL; 607| 1.11k|} regexp.c:newrep: 518| 6.81k|static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { 519| 6.81k| Renode *rep = newnode(g, P_REP); 520| 6.81k| if (max == REPINF && empty(atom)) ------------------ | | 43| 13.6k|#define REPINF 255 ------------------ | Branch (520:13): [True: 4.66k, False: 2.14k] | Branch (520:30): [True: 38, False: 4.62k] ------------------ 521| 38| die(g, "infinite loop matching the empty string"); 522| 6.81k| rep->ng = ng; 523| 6.81k| rep->m = min; 524| 6.81k| rep->n = max; 525| 6.81k| rep->x = atom; 526| 6.81k| return rep; 527| 6.81k|} regexp.c:empty: 494| 12.8k|static int empty(Renode *node) { 495| 12.8k| if (!node) ------------------ | Branch (495:13): [True: 713, False: 12.1k] ------------------ 496| 713| return 1; 497| 12.1k| switch (node->type) { 498| 360| default: ------------------ | Branch (498:9): [True: 360, False: 11.7k] ------------------ 499| 360| return 1; 500| 2.09k| case P_CAT: ------------------ | Branch (500:9): [True: 2.09k, False: 10.0k] ------------------ 501| 2.09k| return empty(node->x) && empty(node->y); ------------------ | Branch (501:24): [True: 1.74k, False: 345] | Branch (501:42): [True: 1.46k, False: 281] ------------------ 502| 545| case P_ALT: ------------------ | Branch (502:9): [True: 545, False: 11.5k] ------------------ 503| 545| return empty(node->x) || empty(node->y); ------------------ | Branch (503:24): [True: 326, False: 219] | Branch (503:42): [True: 108, False: 111] ------------------ 504| 994| case P_REP: ------------------ | Branch (504:9): [True: 994, False: 11.1k] ------------------ 505| 994| return empty(node->x) || node->m == 0; ------------------ | Branch (505:24): [True: 194, False: 800] | Branch (505:42): [True: 714, False: 86] ------------------ 506| 1.75k| case P_PAR: ------------------ | Branch (506:9): [True: 1.75k, False: 10.3k] ------------------ 507| 1.75k| return empty(node->x); 508| 805| case P_REF: ------------------ | Branch (508:9): [True: 805, False: 11.3k] ------------------ 509| 805| return empty(node->x); 510| 524| case P_ANY: ------------------ | Branch (510:9): [True: 524, False: 11.5k] ------------------ 511| 5.15k| case P_CHAR: ------------------ | Branch (511:9): [True: 4.63k, False: 7.47k] ------------------ 512| 5.35k| case P_CCLASS: ------------------ | Branch (512:9): [True: 202, False: 11.9k] ------------------ 513| 5.55k| case P_NCCLASS: ------------------ | Branch (513:9): [True: 199, False: 11.9k] ------------------ 514| 5.55k| return 0; 515| 12.1k| } 516| 12.1k|} regexp.c:re_accept: 533| 1.34M|static int re_accept(Restate *g, int t) { 534| 1.34M| if (g->lookahead == t) { ------------------ | Branch (534:13): [True: 78.2k, False: 1.27M] ------------------ 535| 78.2k| next(g); 536| 78.2k| return 1; 537| 78.2k| } 538| 1.27M| return 0; 539| 1.34M|} regexp.c:newnode: 482| 472k|static Renode *newnode(Restate *g, int type) { 483| 472k| Renode *node = g->pend++; 484| 472k| node->type = type; 485| 472k| node->cc = NULL; 486| 472k| node->c = 0; 487| 472k| node->ng = 0; 488| 472k| node->m = 0; 489| 472k| node->n = 0; 490| | node->x = node->y = NULL; 491| 472k| return node; 492| 472k|} regexp.c:die: 84| 1.12k|static void die(Restate *g, const char *message) { 85| 1.12k| g->error = message; 86| 1.12k| longjmp(g->kaboom, 1); 87| 1.12k|} regexp.c:count: 697| 446k|static unsigned int count(Renode *node) { 698| 446k| unsigned int min, max; 699| 446k| if (!node) ------------------ | Branch (699:13): [True: 16.6k, False: 429k] ------------------ 700| 16.6k| return 0; 701| 429k| switch (node->type) { 702| 203k| default: ------------------ | Branch (702:9): [True: 203k, False: 225k] ------------------ 703| 203k| return 1; 704| 203k| case P_CAT: ------------------ | Branch (704:9): [True: 203k, False: 226k] ------------------ 705| 203k| return count(node->x) + count(node->y); 706| 16.2k| case P_ALT: ------------------ | Branch (706:9): [True: 16.2k, False: 413k] ------------------ 707| 16.2k| return count(node->x) + count(node->y) + 2; 708| 4.76k| case P_REP: ------------------ | Branch (708:9): [True: 4.76k, False: 424k] ------------------ 709| 4.76k| min = node->m; 710| 4.76k| max = node->n; 711| 4.76k| if (min == max) ------------------ | Branch (711:21): [True: 909, False: 3.85k] ------------------ 712| 909| return count(node->x) * min; 713| 3.85k| if (max < REPINF) ------------------ | | 43| 3.85k|#define REPINF 255 ------------------ | Branch (713:21): [True: 880, False: 2.97k] ------------------ 714| 880| return count(node->x) * max + (max - min); 715| 2.97k| return count(node->x) * (min + 1) + 2; 716| 518| case P_PAR: ------------------ | Branch (716:9): [True: 518, False: 428k] ------------------ 717| 518| return count(node->x) + 2; 718| 446| case P_PLA: ------------------ | Branch (718:9): [True: 446, False: 429k] ------------------ 719| 446| return count(node->x) + 2; 720| 435| case P_NLA: ------------------ | Branch (720:9): [True: 435, False: 429k] ------------------ 721| 435| return count(node->x) + 2; 722| 429k| } 723| 429k|} regexp.c:emit: 725| 398k|static Reinst *emit(Reprog *prog, int opcode) { 726| 398k| Reinst *inst = prog->end++; 727| 398k| inst->opcode = opcode; 728| 398k| inst->n = 0; 729| 398k| inst->c = 0; 730| 398k| inst->cc = NULL; 731| | inst->x = inst->y = NULL; 732| 398k| return inst; 733| 398k|} regexp.c:compile: 735| 573k|static void compile(Reprog *prog, Renode *node) { 736| 573k| Reinst *inst, *split, *jump; 737| 573k| unsigned int i; 738| | 739| 573k| if (!node) ------------------ | Branch (739:13): [True: 19.2k, False: 554k] ------------------ 740| 19.2k| return; 741| | 742| 554k| switch (node->type) { ------------------ | Branch (742:17): [True: 554k, False: 0] ------------------ 743| 192k| case P_CAT: ------------------ | Branch (743:9): [True: 192k, False: 361k] ------------------ 744| 192k| compile(prog, node->x); 745| 192k| compile(prog, node->y); 746| 192k| break; 747| | 748| 17.3k| case P_ALT: ------------------ | Branch (748:9): [True: 17.3k, False: 537k] ------------------ 749| 17.3k| split = emit(prog, I_SPLIT); 750| 17.3k| compile(prog, node->x); 751| 17.3k| jump = emit(prog, I_JUMP); 752| 17.3k| compile(prog, node->y); 753| 17.3k| split->x = split + 1; 754| 17.3k| split->y = jump + 1; 755| 17.3k| jump->x = prog->end; 756| 17.3k| break; 757| | 758| 8.01k| case P_REP: ------------------ | Branch (758:9): [True: 8.01k, False: 546k] ------------------ 759| 144k| for (i = 0; i < node->m; ++i) { ------------------ | Branch (759:29): [True: 136k, False: 8.01k] ------------------ 760| 136k| inst = prog->end; 761| 136k| compile(prog, node->x); 762| 136k| } 763| 8.01k| if (node->m == node->n) ------------------ | Branch (763:21): [True: 2.20k, False: 5.80k] ------------------ 764| 2.20k| break; 765| 5.80k| if (node->n < REPINF) { ------------------ | | 43| 5.80k|#define REPINF 255 ------------------ | Branch (765:21): [True: 1.27k, False: 4.53k] ------------------ 766| 7.62k| for (i = node->m; i < node->n; ++i) { ------------------ | Branch (766:43): [True: 6.34k, False: 1.27k] ------------------ 767| 6.34k| split = emit(prog, I_SPLIT); 768| 6.34k| compile(prog, node->x); 769| 6.34k| if (node->ng) { ------------------ | Branch (769:37): [True: 616, False: 5.72k] ------------------ 770| 616| split->y = split + 1; 771| 616| split->x = prog->end; 772| 5.72k| } else { 773| 5.72k| split->x = split + 1; 774| 5.72k| split->y = prog->end; 775| 5.72k| } 776| 6.34k| } 777| 4.53k| } else if (node->m == 0) { ------------------ | Branch (777:28): [True: 2.86k, False: 1.66k] ------------------ 778| 2.86k| split = emit(prog, I_SPLIT); 779| 2.86k| compile(prog, node->x); 780| 2.86k| jump = emit(prog, I_JUMP); 781| 2.86k| if (node->ng) { ------------------ | Branch (781:29): [True: 1.38k, False: 1.47k] ------------------ 782| 1.38k| split->y = split + 1; 783| 1.38k| split->x = prog->end; 784| 1.47k| } else { 785| 1.47k| split->x = split + 1; 786| 1.47k| split->y = prog->end; 787| 1.47k| } 788| 2.86k| jump->x = split; 789| 2.86k| } else { 790| 1.66k| split = emit(prog, I_SPLIT); 791| 1.66k| if (node->ng) { ------------------ | Branch (791:29): [True: 544, False: 1.12k] ------------------ 792| 544| split->y = inst; 793| 544| split->x = prog->end; 794| 1.12k| } else { 795| 1.12k| split->x = inst; 796| 1.12k| split->y = prog->end; 797| 1.12k| } 798| 1.66k| } 799| 5.80k| break; 800| | 801| 40.0k| case P_BOL: ------------------ | Branch (801:9): [True: 40.0k, False: 514k] ------------------ 802| 40.0k| emit(prog, I_BOL); 803| 40.0k| break; 804| 1.18k| case P_EOL: ------------------ | Branch (804:9): [True: 1.18k, False: 553k] ------------------ 805| 1.18k| emit(prog, I_EOL); 806| 1.18k| break; 807| 506| case P_WORD: ------------------ | Branch (807:9): [True: 506, False: 554k] ------------------ 808| 506| emit(prog, I_WORD); 809| 506| break; 810| 491| case P_NWORD: ------------------ | Branch (810:9): [True: 491, False: 554k] ------------------ 811| 491| emit(prog, I_NWORD); 812| 491| break; 813| | 814| 5.84k| case P_PAR: ------------------ | Branch (814:9): [True: 5.84k, False: 548k] ------------------ 815| 5.84k| inst = emit(prog, I_LPAR); 816| 5.84k| inst->n = node->n; 817| 5.84k| compile(prog, node->x); 818| 5.84k| inst = emit(prog, I_RPAR); 819| 5.84k| inst->n = node->n; 820| 5.84k| break; 821| 714| case P_PLA: ------------------ | Branch (821:9): [True: 714, False: 553k] ------------------ 822| 714| split = emit(prog, I_PLA); 823| 714| compile(prog, node->x); 824| 714| emit(prog, I_END); 825| 714| split->x = split + 1; 826| 714| split->y = prog->end; 827| 714| break; 828| 761| case P_NLA: ------------------ | Branch (828:9): [True: 761, False: 553k] ------------------ 829| 761| split = emit(prog, I_NLA); 830| 761| compile(prog, node->x); 831| 761| emit(prog, I_END); 832| 761| split->x = split + 1; 833| 761| split->y = prog->end; 834| 761| break; 835| | 836| 8.15k| case P_ANY: ------------------ | Branch (836:9): [True: 8.15k, False: 546k] ------------------ 837| 8.15k| emit(prog, I_ANY); 838| 8.15k| break; 839| 276k| case P_CHAR: ------------------ | Branch (839:9): [True: 276k, False: 277k] ------------------ 840| 276k| inst = emit(prog, I_CHAR); 841| 276k| inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; ------------------ | Branch (841:27): [True: 0, False: 276k] ------------------ 842| 276k| break; 843| 701| case P_CCLASS: ------------------ | Branch (843:9): [True: 701, False: 554k] ------------------ 844| 701| inst = emit(prog, I_CCLASS); 845| 701| inst->cc = node->cc; 846| 701| break; 847| 415| case P_NCCLASS: ------------------ | Branch (847:9): [True: 415, False: 554k] ------------------ 848| 415| inst = emit(prog, I_NCCLASS); 849| 415| inst->cc = node->cc; 850| 415| break; 851| 819| case P_REF: ------------------ | Branch (851:9): [True: 819, False: 553k] ------------------ 852| 819| inst = emit(prog, I_REF); 853| 819| inst->n = node->n; 854| 819| break; 855| 554k| } 856| 554k|} LLVMFuzzerTestOneInput: 44| 2.09k|int LLVMFuzzerTestOneInput(uint8_t *data, size_t size) { 45| | /* wrap random data in a null-terminated string */ 46| 2.09k| char *null_terminated = malloc(size + 1); 47| 2.09k| memcpy(null_terminated, data, size); 48| 2.09k| null_terminated[size] = '\0'; 49| | 50| 2.09k| const char *error; 51| 2.09k| Reprog *p = re_regcomp(null_terminated, 0, &error); 52| 2.09k| if (p != NULL) { ------------------ | Branch (52:13): [True: 961, False: 1.13k] ------------------ 53| 961| re_regfree(p); 54| 961| } 55| | 56| | /* cleanup */ 57| 2.09k| free(null_terminated); 58| | 59| 2.09k| return 0; 60| 2.09k|}