regexp.c:rd_calloc: 139| 1.98k|static RD_INLINE RD_UNUSED void *rd_calloc(size_t num, size_t sz) { 140| 1.98k| void *p = calloc(num, sz); 141| 1.98k| rd_assert(p); ------------------ | | 159| 1.98k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (141:9): [True: 0, False: 1.98k] | Branch (141:9): [True: 1.98k, False: 0] ------------------ 142| 1.98k| return p; 143| 1.98k|} regexp.c:rd_malloc: 145| 2.90k|static RD_INLINE RD_UNUSED void *rd_malloc(size_t sz) { 146| 2.90k| void *p = malloc(sz); 147| 2.90k| rd_assert(p); ------------------ | | 159| 2.90k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (147:9): [True: 0, False: 2.90k] | Branch (147:9): [True: 2.90k, False: 0] ------------------ 148| 2.90k| return p; 149| 2.90k|} regexp.c:rd_free: 157| 4.89k|static RD_INLINE RD_UNUSED void rd_free(void *ptr) { 158| 4.89k| free(ptr); 159| 4.89k|} re_regcomp: 1004| 1.99k|Reprog *re_regcomp(const char *pattern, int cflags, const char **errorp) { 1005| 1.99k| Reprog *prog; 1006| 1.99k| Restate *g; 1007| 1.99k| Renode *node; 1008| 1.99k| Reinst *split, *jump; 1009| 1.99k| int i; 1010| 1.99k| unsigned int ncount; 1011| 1.99k| size_t pattern_len = strlen(pattern); 1012| | 1013| 1.99k| if (pattern_len > 10000) { ------------------ | Branch (1013:13): [True: 8, False: 1.98k] ------------------ 1014| | /* Avoid stack exhaustion in recursive parseatom() et.al. */ 1015| 8| if (errorp) ------------------ | Branch (1015:21): [True: 8, False: 0] ------------------ 1016| 8| *errorp = "regexp pattern too long (max 10000)"; 1017| 8| return NULL; 1018| 8| } 1019| | 1020| 1.98k| prog = rd_calloc(1, sizeof(Reprog)); 1021| 1.98k| g = &prog->g; 1022| 1.98k| g->prog = prog; 1023| 1.98k| g->pstart = g->pend = rd_malloc(sizeof(Renode) * pattern_len * 2); 1024| | 1025| 1.98k| if (setjmp(g->kaboom)) { ------------------ | Branch (1025:13): [True: 1.06k, False: 921] ------------------ 1026| 1.06k| if (errorp) ------------------ | Branch (1026:21): [True: 1.06k, False: 0] ------------------ 1027| 1.06k| *errorp = g->error; 1028| 1.06k| rd_free(g->pstart); 1029| 1.06k| rd_free(prog); 1030| 1.06k| return NULL; 1031| 1.06k| } 1032| | 1033| 921| g->source = pattern; 1034| 921| g->ncclass = 0; 1035| 921| g->nsub = 1; 1036| 32.6k| for (i = 0; i < MAXSUB; ++i) ------------------ | | 45| 32.6k|#define MAXSUB REG_MAXSUB ------------------ | Branch (1036:21): [True: 31.7k, False: 921] ------------------ 1037| 31.7k| g->sub[i] = 0; 1038| | 1039| 921| g->prog->flags = cflags; 1040| | 1041| 921| next(g); 1042| 921| node = parsealt(g); 1043| 921| if (g->lookahead == ')') ------------------ | Branch (1043:13): [True: 17, False: 904] ------------------ 1044| 17| die(g, "unmatched ')'"); 1045| 921| if (g->lookahead != 0) ------------------ | Branch (1045:13): [True: 0, False: 921] ------------------ 1046| 0| die(g, "syntax error"); 1047| | 1048| 921| g->prog->nsub = g->nsub; 1049| 921| ncount = count(node); 1050| 921| if (ncount > 10000) ------------------ | Branch (1050:13): [True: 37, False: 884] ------------------ 1051| 37| die(g, "regexp graph too large"); 1052| 921| g->prog->start = g->prog->end = 1053| 921| rd_malloc((ncount + 6) * sizeof(Reinst)); 1054| | 1055| 921| split = emit(g->prog, I_SPLIT); 1056| 921| split->x = split + 3; 1057| 921| split->y = split + 1; 1058| 921| emit(g->prog, I_ANYNL); 1059| 921| jump = emit(g->prog, I_JUMP); 1060| 921| jump->x = split; 1061| 921| emit(g->prog, I_LPAR); 1062| 921| compile(g->prog, node); 1063| 921| emit(g->prog, I_RPAR); 1064| 921| emit(g->prog, I_END); 1065| | 1066| |#ifdef TEST 1067| | dumpnode(node); 1068| | putchar('\n'); 1069| | dumpprog(g->prog); 1070| |#endif 1071| | 1072| 921| rd_free(g->pstart); 1073| | 1074| 921| if (errorp) ------------------ | Branch (1074:13): [True: 921, False: 0] ------------------ 1075| 921| *errorp = NULL; 1076| 921| return g->prog; 1077| 1.98k|} re_regfree: 1079| 921|void re_regfree(Reprog *prog) { 1080| 921| if (prog) { ------------------ | Branch (1080:13): [True: 921, False: 0] ------------------ 1081| 921| rd_free(prog->start); 1082| 921| rd_free(prog); 1083| 921| } 1084| 921|} regexp.c:next: 529| 237k|static void next(Restate *g) { 530| 237k| g->lookahead = lex(g); 531| 237k|} regexp.c:lex: 370| 237k|static int lex(Restate *g) { 371| 237k| int quoted = nextrune(g); 372| 237k| if (quoted) { ------------------ | Branch (372:13): [True: 3.74k, False: 233k] ------------------ 373| 3.74k| switch (g->yychar) { ------------------ | Branch (373:25): [True: 2.21k, False: 1.52k] ------------------ 374| 207| case 'b': ------------------ | Branch (374:17): [True: 207, False: 3.53k] ------------------ 375| 207| return L_WORD; 376| 217| case 'B': ------------------ | Branch (376:17): [True: 217, False: 3.52k] ------------------ 377| 217| return L_NWORD; 378| 72| case 'd': ------------------ | Branch (378:17): [True: 72, False: 3.66k] ------------------ 379| 72| newcclass(g); 380| 72| addranges_d(g); 381| 72| return L_CCLASS; 382| 116| case 's': ------------------ | Branch (382:17): [True: 116, False: 3.62k] ------------------ 383| 116| newcclass(g); 384| 116| addranges_s(g); 385| 116| return L_CCLASS; 386| 105| case 'w': ------------------ | Branch (386:17): [True: 105, False: 3.63k] ------------------ 387| 105| newcclass(g); 388| 105| addranges_w(g); 389| 105| return L_CCLASS; 390| 133| case 'D': ------------------ | Branch (390:17): [True: 133, False: 3.60k] ------------------ 391| 133| newcclass(g); 392| 133| addranges_d(g); 393| 133| return L_NCCLASS; 394| 107| case 'S': ------------------ | Branch (394:17): [True: 107, False: 3.63k] ------------------ 395| 107| newcclass(g); 396| 107| addranges_s(g); 397| 107| return L_NCCLASS; 398| 113| case 'W': ------------------ | Branch (398:17): [True: 113, False: 3.62k] ------------------ 399| 113| newcclass(g); 400| 113| addranges_w(g); 401| 113| return L_NCCLASS; 402| 1.14k| case '0': ------------------ | Branch (402:17): [True: 1.14k, False: 2.59k] ------------------ 403| 1.14k| g->yychar = 0; 404| 1.14k| return L_CHAR; 405| 3.74k| } 406| 1.52k| if (g->yychar >= '0' && g->yychar <= '9') { ------------------ | Branch (406:21): [True: 1.26k, False: 255] | Branch (406:41): [True: 1.02k, False: 239] ------------------ 407| 1.02k| g->yychar -= '0'; 408| 1.02k| if (*g->source >= '0' && *g->source <= '9') ------------------ | Branch (408:29): [True: 668, False: 361] | Branch (408:50): [True: 203, False: 465] ------------------ 409| 203| g->yychar = g->yychar * 10 + *g->source++ - '0'; 410| 1.02k| return L_REF; 411| 1.02k| } 412| 494| return L_CHAR; 413| 1.52k| } 414| | 415| 233k| switch (g->yychar) { ------------------ | Branch (415:17): [True: 45.5k, False: 187k] ------------------ 416| 1.08k| case 0: ------------------ | Branch (416:9): [True: 1.08k, False: 232k] ------------------ 417| 18.7k| case '$': ------------------ | Branch (417:9): [True: 17.6k, False: 215k] ------------------ 418| 20.8k| case ')': ------------------ | Branch (418:9): [True: 2.09k, False: 231k] ------------------ 419| 23.4k| case '*': ------------------ | Branch (419:9): [True: 2.56k, False: 230k] ------------------ 420| 24.2k| case '+': ------------------ | Branch (420:9): [True: 867, False: 232k] ------------------ 421| 25.7k| case '.': ------------------ | Branch (421:9): [True: 1.42k, False: 231k] ------------------ 422| 28.4k| case '?': ------------------ | Branch (422:9): [True: 2.70k, False: 230k] ------------------ 423| 34.7k| case '^': ------------------ | Branch (423:9): [True: 6.35k, False: 227k] ------------------ 424| 45.5k| case '|': ------------------ | Branch (424:9): [True: 10.7k, False: 222k] ------------------ 425| 45.5k| return g->yychar; 426| 233k| } 427| | 428| 187k| if (g->yychar == '{') ------------------ | Branch (428:13): [True: 1.83k, False: 185k] ------------------ 429| 1.83k| return lexcount(g); 430| 185k| if (g->yychar == '[') ------------------ | Branch (430:13): [True: 736, False: 185k] ------------------ 431| 736| return lexclass(g); 432| 185k| if (g->yychar == '(') { ------------------ | Branch (432:13): [True: 3.63k, False: 181k] ------------------ 433| 3.63k| if (g->source[0] == '?') { ------------------ | Branch (433:21): [True: 2.49k, False: 1.13k] ------------------ 434| 2.49k| if (g->source[1] == ':') { ------------------ | Branch (434:29): [True: 704, False: 1.79k] ------------------ 435| 704| g->source += 2; 436| 704| return L_NC; 437| 704| } 438| 1.79k| if (g->source[1] == '=') { ------------------ | Branch (438:29): [True: 698, False: 1.09k] ------------------ 439| 698| g->source += 2; 440| 698| return L_PLA; 441| 698| } 442| 1.09k| if (g->source[1] == '!') { ------------------ | Branch (442:29): [True: 1.06k, False: 24] ------------------ 443| 1.06k| g->source += 2; 444| 1.06k| return L_NLA; 445| 1.06k| } 446| 1.09k| } 447| 1.15k| return '('; 448| 3.63k| } 449| | 450| 181k| return L_CHAR; 451| 185k|} regexp.c:nextrune: 131| 244k|static int nextrune(Restate *g) { 132| 244k| g->source += chartorune(&g->yychar, g->source); 133| 244k| if (g->yychar == '\\') { ------------------ | Branch (133:13): [True: 9.89k, False: 234k] ------------------ 134| 9.89k| g->source += chartorune(&g->yychar, g->source); 135| 9.89k| switch (g->yychar) { ------------------ | Branch (135:25): [True: 4.46k, False: 5.43k] ------------------ 136| 13| case 0: ------------------ | Branch (136:17): [True: 13, False: 9.87k] ------------------ 137| 13| die(g, "unterminated escape sequence"); 138| 213| case 'f': ------------------ | Branch (138:17): [True: 200, False: 9.69k] ------------------ 139| 213| g->yychar = '\f'; 140| 213| return 0; 141| 220| case 'n': ------------------ | Branch (141:17): [True: 220, False: 9.67k] ------------------ 142| 220| g->yychar = '\n'; 143| 220| return 0; 144| 194| case 'r': ------------------ | Branch (144:17): [True: 194, False: 9.69k] ------------------ 145| 194| g->yychar = '\r'; 146| 194| return 0; 147| 195| case 't': ------------------ | Branch (147:17): [True: 195, False: 9.69k] ------------------ 148| 195| g->yychar = '\t'; 149| 195| return 0; 150| 220| case 'v': ------------------ | Branch (150:17): [True: 220, False: 9.67k] ------------------ 151| 220| g->yychar = '\v'; 152| 220| return 0; 153| 198| case 'c': ------------------ | Branch (153:17): [True: 198, False: 9.69k] ------------------ 154| 198| g->yychar = (*g->source++) & 31; 155| 198| return 0; 156| 1.61k| case 'x': ------------------ | Branch (156:17): [True: 1.61k, False: 8.27k] ------------------ 157| 1.61k| g->yychar = hex(g, *g->source++) << 4; 158| 1.61k| g->yychar += hex(g, *g->source++); 159| 1.61k| if (g->yychar == 0) { ------------------ | Branch (159:29): [True: 478, False: 1.13k] ------------------ 160| 478| g->yychar = '0'; 161| 478| return 1; 162| 478| } 163| 1.13k| return 0; 164| 1.60k| case 'u': ------------------ | Branch (164:17): [True: 1.60k, False: 8.28k] ------------------ 165| 1.60k| g->yychar = hex(g, *g->source++) << 12; 166| 1.60k| g->yychar += hex(g, *g->source++) << 8; 167| 1.60k| g->yychar += hex(g, *g->source++) << 4; 168| 1.60k| g->yychar += hex(g, *g->source++); 169| 1.60k| if (g->yychar == 0) { ------------------ | Branch (169:29): [True: 468, False: 1.13k] ------------------ 170| 468| g->yychar = '0'; 171| 468| return 1; 172| 468| } 173| 1.13k| return 0; 174| 9.89k| } 175| 5.43k| if (strchr(ESCAPES, g->yychar)) ------------------ | | 129| 5.43k|#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" ------------------ | Branch (175:21): [True: 4.90k, False: 528] ------------------ 176| 4.90k| return 1; 177| 528| if (isalpharune(g->yychar) || ------------------ | Branch (177:21): [True: 10, False: 518] ------------------ 178| 518| g->yychar == '_') /* check identity escape */ ------------------ | Branch (178:21): [True: 1, False: 517] ------------------ 179| 11| die(g, "invalid escape character"); 180| 528| return 0; 181| 5.43k| } 182| 234k| return 0; 183| 244k|} regexp.c:chartorune: 37| 254k|static int chartorune(Rune *r, const char *s) { 38| | /* TODO: Add UTF-8 decoding */ 39| 254k| *r = *s; 40| 254k| return 1; 41| 254k|} regexp.c:hex: 111| 9.37k|static int hex(Restate *g, int c) { 112| 9.37k| if (c >= '0' && c <= '9') ------------------ | Branch (112:13): [True: 9.21k, False: 161] | Branch (112:25): [True: 3.61k, False: 5.59k] ------------------ 113| 3.61k| return c - '0'; 114| 5.75k| if (c >= 'a' && c <= 'f') ------------------ | Branch (114:13): [True: 2.50k, False: 3.24k] | Branch (114:25): [True: 2.47k, False: 30] ------------------ 115| 2.47k| return c - 'a' + 0xA; 116| 3.27k| if (c >= 'A' && c <= 'F') ------------------ | Branch (116:13): [True: 3.09k, False: 183] | Branch (116:25): [True: 3.03k, False: 65] ------------------ 117| 3.03k| return c - 'A' + 0xA; 118| 248| die(g, "invalid escape sequence"); 119| 248| return 0; 120| 3.27k|} regexp.c:isalpharune: 25| 528|static int isalpharune(Rune c) { 26| | /* TODO: Add unicode support */ 27| 528| return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); ------------------ | Branch (27:17): [True: 323, False: 205] | Branch (27:29): [True: 6, False: 317] | Branch (27:43): [True: 309, False: 213] | Branch (27:55): [True: 4, False: 305] ------------------ 28| 528|} regexp.c:newcclass: 218| 1.38k|static void newcclass(Restate *g) { 219| 1.38k| if (g->ncclass >= nelem(g->prog->cclass)) ------------------ | | 21| 1.38k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (219:13): [True: 7, False: 1.37k] ------------------ 220| 7| die(g, "too many character classes"); 221| 1.38k| g->yycc = g->prog->cclass + g->ncclass++; 222| 1.38k| g->yycc->end = g->yycc->spans; 223| 1.38k|} regexp.c:addranges_d: 234| 830|static void addranges_d(Restate *g) { 235| 830| addrange(g, '0', '9'); 236| 830|} regexp.c:addrange: 225| 8.94k|static void addrange(Restate *g, Rune a, Rune b) { 226| 8.94k| if (a > b) ------------------ | Branch (226:13): [True: 43, False: 8.90k] ------------------ 227| 43| die(g, "invalid character class range"); 228| 8.94k| if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) ------------------ | | 21| 8.94k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (228:13): [True: 45, False: 8.89k] ------------------ 229| 45| die(g, "too many character class ranges"); 230| 8.94k| *g->yycc->end++ = a; 231| 8.94k| *g->yycc->end++ = b; 232| 8.94k|} regexp.c:addranges_s: 243| 447|static void addranges_s(Restate *g) { 244| 447| addrange(g, 0x9, 0x9); 245| 447| addrange(g, 0xA, 0xD); 246| 447| addrange(g, 0x20, 0x20); 247| 447| addrange(g, 0xA0, 0xA0); 248| 447| addrange(g, 0x2028, 0x2029); 249| 447| addrange(g, 0xFEFF, 0xFEFF); 250| 447|} regexp.c:addranges_w: 262| 326|static void addranges_w(Restate *g) { 263| 326| addrange(g, '0', '9'); 264| 326| addrange(g, 'A', 'Z'); 265| 326| addrange(g, '_', '_'); 266| 326| addrange(g, 'a', 'z'); 267| 326|} regexp.c:lexcount: 185| 1.83k|static int lexcount(Restate *g) { 186| 1.83k| g->yychar = *g->source++; 187| | 188| 1.83k| g->yymin = dec(g, g->yychar); 189| 1.83k| g->yychar = *g->source++; 190| 3.64k| while (g->yychar != ',' && g->yychar != '}') { ------------------ | Branch (190:16): [True: 2.71k, False: 929] | Branch (190:36): [True: 1.80k, False: 903] ------------------ 191| 1.80k| g->yymin = g->yymin * 10 + dec(g, g->yychar); 192| 1.80k| g->yychar = *g->source++; 193| 1.80k| } 194| 1.83k| if (g->yymin >= REPINF) ------------------ | | 43| 1.83k|#define REPINF 255 ------------------ | Branch (194:13): [True: 13, False: 1.81k] ------------------ 195| 13| die(g, "numeric overflow"); 196| | 197| 1.83k| if (g->yychar == ',') { ------------------ | Branch (197:13): [True: 877, False: 955] ------------------ 198| 877| g->yychar = *g->source++; 199| 877| if (g->yychar == '}') { ------------------ | Branch (199:21): [True: 303, False: 574] ------------------ 200| 303| g->yymax = REPINF; ------------------ | | 43| 303|#define REPINF 255 ------------------ 201| 574| } else { 202| 574| g->yymax = dec(g, g->yychar); 203| 574| g->yychar = *g->source++; 204| 1.55k| while (g->yychar != '}') { ------------------ | Branch (204:32): [True: 979, False: 574] ------------------ 205| 979| g->yymax = g->yymax * 10 + dec(g, g->yychar); 206| 979| g->yychar = *g->source++; 207| 979| } 208| 574| if (g->yymax >= REPINF) ------------------ | | 43| 574|#define REPINF 255 ------------------ | Branch (208:29): [True: 17, False: 557] ------------------ 209| 17| die(g, "numeric overflow"); 210| 574| } 211| 955| } else { 212| 955| g->yymax = g->yymin; 213| 955| } 214| | 215| 1.83k| return L_COUNT; 216| 1.83k|} regexp.c:dec: 122| 5.19k|static int dec(Restate *g, int c) { 123| 5.19k| if (c >= '0' && c <= '9') ------------------ | Branch (123:13): [True: 5.11k, False: 75] | Branch (123:25): [True: 5.09k, False: 27] ------------------ 124| 5.09k| return c - '0'; 125| 102| die(g, "invalid quantifier"); 126| 102| return 0; 127| 5.19k|} regexp.c:lexclass: 277| 736|static int lexclass(Restate *g) { 278| 736| int type = L_CCLASS; 279| 736| int quoted, havesave, havedash; 280| 736| Rune save = 0; 281| | 282| 736| newcclass(g); 283| | 284| 736| quoted = nextrune(g); 285| 736| if (!quoted && g->yychar == '^') { ------------------ | Branch (285:13): [True: 526, False: 210] | Branch (285:24): [True: 34, False: 492] ------------------ 286| 34| type = L_NCCLASS; 287| 34| quoted = nextrune(g); 288| 34| } 289| | 290| 736| havesave = havedash = 0; 291| 6.94k| for (;;) { 292| 6.94k| if (g->yychar == 0) ------------------ | Branch (292:21): [True: 217, False: 6.72k] ------------------ 293| 217| die(g, "unterminated character class"); 294| 6.94k| if (!quoted && g->yychar == ']') ------------------ | Branch (294:21): [True: 4.61k, False: 2.32k] | Branch (294:32): [True: 431, False: 4.18k] ------------------ 295| 431| break; 296| | 297| 6.51k| if (!quoted && g->yychar == '-') { ------------------ | Branch (297:21): [True: 4.18k, False: 2.32k] | Branch (297:32): [True: 2.12k, False: 2.06k] ------------------ 298| 2.12k| if (havesave) { ------------------ | Branch (298:29): [True: 1.56k, False: 562] ------------------ 299| 1.56k| if (havedash) { ------------------ | Branch (299:37): [True: 459, False: 1.10k] ------------------ 300| 459| addrange(g, save, '-'); 301| 459| havesave = havedash = 0; 302| 1.10k| } else { 303| 1.10k| havedash = 1; 304| 1.10k| } 305| 1.56k| } else { 306| 562| save = '-'; 307| 562| havesave = 1; 308| 562| } 309| 4.38k| } else if (quoted && strchr("DSWdsw", g->yychar)) { ------------------ | Branch (309:28): [True: 2.10k, False: 2.27k] | Branch (309:38): [True: 1.41k, False: 695] ------------------ 310| 1.41k| if (havesave) { ------------------ | Branch (310:29): [True: 571, False: 843] ------------------ 311| 571| addrange(g, save, save); 312| 571| if (havedash) ------------------ | Branch (312:37): [True: 196, False: 375] ------------------ 313| 196| addrange(g, '-', '-'); 314| 571| } 315| 1.41k| switch (g->yychar) { ------------------ | Branch (315:33): [True: 1.41k, False: 3] ------------------ 316| 627| case 'd': ------------------ | Branch (316:25): [True: 627, False: 787] ------------------ 317| 627| addranges_d(g); 318| 627| break; 319| 226| case 's': ------------------ | Branch (319:25): [True: 226, False: 1.18k] ------------------ 320| 226| addranges_s(g); 321| 226| break; 322| 110| case 'w': ------------------ | Branch (322:25): [True: 110, False: 1.30k] ------------------ 323| 110| addranges_w(g); 324| 110| break; 325| 356| case 'D': ------------------ | Branch (325:25): [True: 356, False: 1.05k] ------------------ 326| 356| addranges_D(g); 327| 356| break; 328| 7| case 'S': ------------------ | Branch (328:25): [True: 7, False: 1.40k] ------------------ 329| 7| addranges_S(g); 330| 7| break; 331| 85| case 'W': ------------------ | Branch (331:25): [True: 85, False: 1.32k] ------------------ 332| 85| addranges_W(g); 333| 85| break; 334| 1.41k| } 335| 1.37k| havesave = havedash = 0; 336| 2.97k| } else { 337| 2.97k| if (quoted) { ------------------ | Branch (337:29): [True: 695, False: 2.27k] ------------------ 338| 695| if (g->yychar == 'b') ------------------ | Branch (338:37): [True: 197, False: 498] ------------------ 339| 197| g->yychar = '\b'; 340| 498| else if (g->yychar == '0') ------------------ | Branch (340:42): [True: 271, False: 227] ------------------ 341| 271| g->yychar = 0; 342| | /* else identity escape */ 343| 695| } 344| 2.97k| if (havesave) { ------------------ | Branch (344:29): [True: 1.58k, False: 1.39k] ------------------ 345| 1.58k| if (havedash) { ------------------ | Branch (345:37): [True: 403, False: 1.17k] ------------------ 346| 403| addrange(g, save, g->yychar); 347| 403| havesave = havedash = 0; 348| 1.17k| } else { 349| 1.17k| addrange(g, save, save); 350| 1.17k| save = g->yychar; 351| 1.17k| } 352| 1.58k| } else { 353| 1.39k| save = g->yychar; 354| 1.39k| havesave = 1; 355| 1.39k| } 356| 2.97k| } 357| | 358| 6.47k| quoted = nextrune(g); 359| 6.47k| } 360| | 361| 697| if (havesave) { ------------------ | Branch (361:13): [True: 178, False: 519] ------------------ 362| 178| addrange(g, save, save); 363| 178| if (havedash) ------------------ | Branch (363:21): [True: 40, False: 138] ------------------ 364| 40| addrange(g, '-', '-'); 365| 178| } 366| | 367| 697| return type; 368| 736|} regexp.c:addranges_D: 238| 356|static void addranges_D(Restate *g) { 239| 356| addrange(g, 0, '0' - 1); 240| 356| addrange(g, '9' + 1, 0xFFFF); 241| 356|} regexp.c:addranges_S: 252| 7|static void addranges_S(Restate *g) { 253| 7| addrange(g, 0, 0x9 - 1); 254| 7| addrange(g, 0x9 + 1, 0xA - 1); 255| 7| addrange(g, 0xD + 1, 0x20 - 1); 256| 7| addrange(g, 0x20 + 1, 0xA0 - 1); 257| 7| addrange(g, 0xA0 + 1, 0x2028 - 1); 258| 7| addrange(g, 0x2029 + 1, 0xFEFF - 1); 259| 7| addrange(g, 0xFEFF + 1, 0xFFFF); 260| 7|} regexp.c:addranges_W: 269| 85|static void addranges_W(Restate *g) { 270| 85| addrange(g, 0, '0' - 1); 271| 85| addrange(g, '9' + 1, 'A' - 1); 272| 85| addrange(g, 'Z' + 1, '_' - 1); 273| 85| addrange(g, '_' + 1, 'a' - 1); 274| 85| addrange(g, 'z' + 1, 0xFFFF); 275| 85|} regexp.c:parsealt: 654| 5.07k|static Renode *parsealt(Restate *g) { 655| 5.07k| Renode *alt, *x; 656| 5.07k| alt = parsecat(g); 657| 15.8k| while (re_accept(g, '|')) { ------------------ | Branch (657:16): [True: 10.7k, False: 5.07k] ------------------ 658| 10.7k| x = alt; 659| 10.7k| alt = newnode(g, P_ALT); 660| 10.7k| alt->x = x; 661| 10.7k| alt->y = parsecat(g); 662| 10.7k| } 663| 5.07k| return alt; 664| 5.07k|} regexp.c:parsecat: 638| 15.8k|static Renode *parsecat(Restate *g) { 639| 15.8k| Renode *cat, *x; 640| 15.8k| if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { ------------------ | Branch (640:13): [True: 15.6k, False: 102] | Branch (640:29): [True: 5.78k, False: 9.91k] | Branch (640:52): [True: 4.56k, False: 1.22k] ------------------ 641| 4.56k| cat = parserep(g); 642| 214k| while (g->lookahead && g->lookahead != '|' && ------------------ | Branch (642:24): [True: 211k, False: 2.87k] | Branch (642:40): [True: 211k, False: 815] ------------------ 643| 211k| g->lookahead != ')') { ------------------ | Branch (643:24): [True: 210k, False: 874] ------------------ 644| 210k| x = cat; 645| 210k| cat = newnode(g, P_CAT); 646| 210k| cat->x = x; 647| 210k| cat->y = parserep(g); 648| 210k| } 649| 4.56k| return cat; 650| 4.56k| } 651| 11.2k| return NULL; 652| 15.8k|} regexp.c:parserep: 609| 214k|static Renode *parserep(Restate *g) { 610| 214k| Renode *atom; 611| | 612| 214k| if (re_accept(g, '^')) ------------------ | Branch (612:13): [True: 6.35k, False: 208k] ------------------ 613| 6.35k| return newnode(g, P_BOL); 614| 208k| if (re_accept(g, '$')) ------------------ | Branch (614:13): [True: 17.6k, False: 190k] ------------------ 615| 17.6k| return newnode(g, P_EOL); 616| 190k| if (re_accept(g, L_WORD)) ------------------ | Branch (616:13): [True: 207, False: 190k] ------------------ 617| 207| return newnode(g, P_WORD); 618| 190k| if (re_accept(g, L_NWORD)) ------------------ | Branch (618:13): [True: 217, False: 190k] ------------------ 619| 217| return newnode(g, P_NWORD); 620| | 621| 190k| atom = parseatom(g); 622| 190k| if (g->lookahead == L_COUNT) { ------------------ | Branch (622:13): [True: 1.62k, False: 188k] ------------------ 623| 1.62k| int min = g->yymin, max = g->yymax; 624| 1.62k| next(g); 625| 1.62k| if (max < min) ------------------ | Branch (625:21): [True: 8, False: 1.61k] ------------------ 626| 8| die(g, "invalid quantifier"); 627| 1.62k| return newrep(g, atom, re_accept(g, '?'), min, max); 628| 1.62k| } 629| 188k| if (re_accept(g, '*')) ------------------ | Branch (629:13): [True: 2.55k, False: 186k] ------------------ 630| 2.55k| return newrep(g, atom, re_accept(g, '?'), 0, REPINF); ------------------ | | 43| 2.55k|#define REPINF 255 ------------------ 631| 186k| if (re_accept(g, '+')) ------------------ | Branch (631:13): [True: 856, False: 185k] ------------------ 632| 856| return newrep(g, atom, re_accept(g, '?'), 1, REPINF); ------------------ | | 43| 856|#define REPINF 255 ------------------ 633| 185k| if (re_accept(g, '?')) ------------------ | Branch (633:13): [True: 633, False: 184k] ------------------ 634| 633| return newrep(g, atom, re_accept(g, '?'), 0, 1); 635| 184k| return atom; 636| 185k|} regexp.c:parseatom: 543| 190k|static Renode *parseatom(Restate *g) { 544| 190k| Renode *atom; 545| 190k| if (g->lookahead == L_CHAR) { ------------------ | Branch (545:13): [True: 183k, False: 7.27k] ------------------ 546| 183k| atom = newnode(g, P_CHAR); 547| 183k| atom->c = g->yychar; 548| 183k| next(g); 549| 183k| return atom; 550| 183k| } 551| 7.27k| if (g->lookahead == L_CCLASS) { ------------------ | Branch (551:13): [True: 689, False: 6.58k] ------------------ 552| 689| atom = newnode(g, P_CCLASS); 553| 689| atom->cc = g->yycc; 554| 689| next(g); 555| 689| return atom; 556| 689| } 557| 6.58k| if (g->lookahead == L_NCCLASS) { ------------------ | Branch (557:13): [True: 378, False: 6.21k] ------------------ 558| 378| atom = newnode(g, P_NCCLASS); 559| 378| atom->cc = g->yycc; 560| 378| next(g); 561| 378| return atom; 562| 378| } 563| 6.21k| if (g->lookahead == L_REF) { ------------------ | Branch (563:13): [True: 1.02k, False: 5.18k] ------------------ 564| 1.02k| atom = newnode(g, P_REF); 565| 1.02k| if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) ------------------ | Branch (565:21): [True: 0, False: 1.02k] | Branch (565:39): [True: 21, False: 1.00k] | Branch (565:62): [True: 11, False: 997] ------------------ 566| 32| die(g, "invalid back-reference"); 567| 1.02k| atom->n = g->yychar; 568| 1.02k| atom->x = g->sub[g->yychar]; 569| 1.02k| next(g); 570| 1.02k| return atom; 571| 1.02k| } 572| 5.18k| if (re_accept(g, '.')) ------------------ | Branch (572:13): [True: 1.42k, False: 3.75k] ------------------ 573| 1.42k| return newnode(g, P_ANY); 574| 3.75k| if (re_accept(g, '(')) { ------------------ | Branch (574:13): [True: 1.15k, False: 2.60k] ------------------ 575| 1.15k| atom = newnode(g, P_PAR); 576| 1.15k| if (g->nsub == MAXSUB) ------------------ | | 45| 1.15k|#define MAXSUB REG_MAXSUB ------------------ | Branch (576:21): [True: 5, False: 1.15k] ------------------ 577| 5| die(g, "too many captures"); 578| 1.15k| atom->n = g->nsub++; 579| 1.15k| atom->x = parsealt(g); 580| 1.15k| g->sub[atom->n] = atom; 581| 1.15k| if (!re_accept(g, ')')) ------------------ | Branch (581:21): [True: 48, False: 1.11k] ------------------ 582| 48| die(g, "unmatched '('"); 583| 1.15k| return atom; 584| 1.15k| } 585| 2.60k| if (re_accept(g, L_NC)) { ------------------ | Branch (585:13): [True: 704, False: 1.89k] ------------------ 586| 704| atom = parsealt(g); 587| 704| if (!re_accept(g, ')')) ------------------ | Branch (587:21): [True: 13, False: 691] ------------------ 588| 13| die(g, "unmatched '('"); 589| 704| return atom; 590| 704| } 591| 1.89k| if (re_accept(g, L_PLA)) { ------------------ | Branch (591:13): [True: 698, False: 1.19k] ------------------ 592| 698| atom = newnode(g, P_PLA); 593| 698| atom->x = parsealt(g); 594| 698| if (!re_accept(g, ')')) ------------------ | Branch (594:21): [True: 9, False: 689] ------------------ 595| 9| die(g, "unmatched '('"); 596| 698| return atom; 597| 698| } 598| 1.19k| if (re_accept(g, L_NLA)) { ------------------ | Branch (598:13): [True: 1.06k, False: 129] ------------------ 599| 1.06k| atom = newnode(g, P_NLA); 600| 1.06k| atom->x = parsealt(g); 601| 1.06k| if (!re_accept(g, ')')) ------------------ | Branch (601:21): [True: 10, False: 1.05k] ------------------ 602| 10| die(g, "unmatched '('"); 603| 1.06k| return atom; 604| 1.06k| } 605| 129| die(g, "syntax error"); 606| | return NULL; 607| 1.19k|} regexp.c:newrep: 518| 5.66k|static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { 519| 5.66k| Renode *rep = newnode(g, P_REP); 520| 5.66k| if (max == REPINF && empty(atom)) ------------------ | | 43| 11.3k|#define REPINF 255 ------------------ | Branch (520:13): [True: 3.71k, False: 1.95k] | Branch (520:30): [True: 42, False: 3.66k] ------------------ 521| 42| die(g, "infinite loop matching the empty string"); 522| 5.66k| rep->ng = ng; 523| 5.66k| rep->m = min; 524| 5.66k| rep->n = max; 525| 5.66k| rep->x = atom; 526| 5.66k| return rep; 527| 5.66k|} regexp.c:empty: 494| 14.0k|static int empty(Renode *node) { 495| 14.0k| if (!node) ------------------ | Branch (495:13): [True: 1.06k, False: 13.0k] ------------------ 496| 1.06k| return 1; 497| 13.0k| switch (node->type) { 498| 235| default: ------------------ | Branch (498:9): [True: 235, False: 12.8k] ------------------ 499| 235| return 1; 500| 2.72k| case P_CAT: ------------------ | Branch (500:9): [True: 2.72k, False: 10.3k] ------------------ 501| 2.72k| return empty(node->x) && empty(node->y); ------------------ | Branch (501:24): [True: 2.23k, False: 496] | Branch (501:42): [True: 1.87k, False: 352] ------------------ 502| 676| case P_ALT: ------------------ | Branch (502:9): [True: 676, False: 12.3k] ------------------ 503| 676| return empty(node->x) || empty(node->y); ------------------ | Branch (503:24): [True: 452, False: 224] | Branch (503:42): [True: 111, False: 113] ------------------ 504| 1.25k| case P_REP: ------------------ | Branch (504:9): [True: 1.25k, False: 11.7k] ------------------ 505| 1.25k| return empty(node->x) || node->m == 0; ------------------ | Branch (505:24): [True: 194, False: 1.05k] | Branch (505:42): [True: 975, False: 81] ------------------ 506| 2.26k| case P_PAR: ------------------ | Branch (506:9): [True: 2.26k, False: 10.7k] ------------------ 507| 2.26k| return empty(node->x); 508| 1.02k| case P_REF: ------------------ | Branch (508:9): [True: 1.02k, False: 12.0k] ------------------ 509| 1.02k| return empty(node->x); 510| 511| case P_ANY: ------------------ | Branch (510:9): [True: 511, False: 12.5k] ------------------ 511| 4.39k| case P_CHAR: ------------------ | Branch (511:9): [True: 3.87k, False: 9.15k] ------------------ 512| 4.65k| case P_CCLASS: ------------------ | Branch (512:9): [True: 267, False: 12.7k] ------------------ 513| 4.86k| case P_NCCLASS: ------------------ | Branch (513:9): [True: 210, False: 12.8k] ------------------ 514| 4.86k| return 0; 515| 13.0k| } 516| 13.0k|} regexp.c:re_accept: 533| 1.39M|static int re_accept(Restate *g, int t) { 534| 1.39M| if (g->lookahead == t) { ------------------ | Branch (534:13): [True: 48.3k, False: 1.34M] ------------------ 535| 48.3k| next(g); 536| 48.3k| return 1; 537| 48.3k| } 538| 1.34M| return 0; 539| 1.39M|} regexp.c:newnode: 482| 440k|static Renode *newnode(Restate *g, int type) { 483| 440k| Renode *node = g->pend++; 484| 440k| node->type = type; 485| 440k| node->cc = NULL; 486| 440k| node->c = 0; 487| 440k| node->ng = 0; 488| 440k| node->m = 0; 489| 440k| node->n = 0; 490| | node->x = node->y = NULL; 491| 440k| return node; 492| 440k|} regexp.c:die: 84| 1.06k|static void die(Restate *g, const char *message) { 85| 1.06k| g->error = message; 86| 1.06k| longjmp(g->kaboom, 1); 87| 1.06k|} regexp.c:count: 697| 419k|static unsigned int count(Renode *node) { 698| 419k| unsigned int min, max; 699| 419k| if (!node) ------------------ | Branch (699:13): [True: 10.4k, False: 409k] ------------------ 700| 10.4k| return 0; 701| 409k| switch (node->type) { 702| 196k| default: ------------------ | Branch (702:9): [True: 196k, False: 212k] ------------------ 703| 196k| return 1; 704| 196k| case P_CAT: ------------------ | Branch (704:9): [True: 196k, False: 213k] ------------------ 705| 196k| return count(node->x) + count(node->y); 706| 9.98k| case P_ALT: ------------------ | Branch (706:9): [True: 9.98k, False: 399k] ------------------ 707| 9.98k| return count(node->x) + count(node->y) + 2; 708| 4.88k| case P_REP: ------------------ | Branch (708:9): [True: 4.88k, False: 404k] ------------------ 709| 4.88k| min = node->m; 710| 4.88k| max = node->n; 711| 4.88k| if (min == max) ------------------ | Branch (711:21): [True: 816, False: 4.06k] ------------------ 712| 816| return count(node->x) * min; 713| 4.06k| if (max < REPINF) ------------------ | | 43| 4.06k|#define REPINF 255 ------------------ | Branch (713:21): [True: 954, False: 3.11k] ------------------ 714| 954| return count(node->x) * max + (max - min); 715| 3.11k| return count(node->x) * (min + 1) + 2; 716| 539| case P_PAR: ------------------ | Branch (716:9): [True: 539, False: 408k] ------------------ 717| 539| return count(node->x) + 2; 718| 466| case P_PLA: ------------------ | Branch (718:9): [True: 466, False: 408k] ------------------ 719| 466| return count(node->x) + 2; 720| 442| case P_NLA: ------------------ | Branch (720:9): [True: 442, False: 408k] ------------------ 721| 442| return count(node->x) + 2; 722| 409k| } 723| 409k|} regexp.c:emit: 725| 373k|static Reinst *emit(Reprog *prog, int opcode) { 726| 373k| Reinst *inst = prog->end++; 727| 373k| inst->opcode = opcode; 728| 373k| inst->n = 0; 729| 373k| inst->c = 0; 730| 373k| inst->cc = NULL; 731| | inst->x = inst->y = NULL; 732| 373k| return inst; 733| 373k|} regexp.c:compile: 735| 527k|static void compile(Reprog *prog, Renode *node) { 736| 527k| Reinst *inst, *split, *jump; 737| 527k| unsigned int i; 738| | 739| 527k| if (!node) ------------------ | Branch (739:13): [True: 13.1k, False: 514k] ------------------ 740| 13.1k| return; 741| | 742| 514k| switch (node->type) { ------------------ | Branch (742:17): [True: 514k, False: 0] ------------------ 743| 168k| case P_CAT: ------------------ | Branch (743:9): [True: 168k, False: 345k] ------------------ 744| 168k| compile(prog, node->x); 745| 168k| compile(prog, node->y); 746| 168k| break; 747| | 748| 11.0k| case P_ALT: ------------------ | Branch (748:9): [True: 11.0k, False: 503k] ------------------ 749| 11.0k| split = emit(prog, I_SPLIT); 750| 11.0k| compile(prog, node->x); 751| 11.0k| jump = emit(prog, I_JUMP); 752| 11.0k| compile(prog, node->y); 753| 11.0k| split->x = split + 1; 754| 11.0k| split->y = jump + 1; 755| 11.0k| jump->x = prog->end; 756| 11.0k| break; 757| | 758| 7.40k| case P_REP: ------------------ | Branch (758:9): [True: 7.40k, False: 506k] ------------------ 759| 159k| for (i = 0; i < node->m; ++i) { ------------------ | Branch (759:29): [True: 151k, False: 7.40k] ------------------ 760| 151k| inst = prog->end; 761| 151k| compile(prog, node->x); 762| 151k| } 763| 7.40k| if (node->m == node->n) ------------------ | Branch (763:21): [True: 2.28k, False: 5.12k] ------------------ 764| 2.28k| break; 765| 5.12k| if (node->n < REPINF) { ------------------ | | 43| 5.12k|#define REPINF 255 ------------------ | Branch (765:21): [True: 1.36k, False: 3.75k] ------------------ 766| 6.59k| for (i = node->m; i < node->n; ++i) { ------------------ | Branch (766:43): [True: 5.23k, False: 1.36k] ------------------ 767| 5.23k| split = emit(prog, I_SPLIT); 768| 5.23k| compile(prog, node->x); 769| 5.23k| if (node->ng) { ------------------ | Branch (769:37): [True: 592, False: 4.63k] ------------------ 770| 592| split->y = split + 1; 771| 592| split->x = prog->end; 772| 4.63k| } else { 773| 4.63k| split->x = split + 1; 774| 4.63k| split->y = prog->end; 775| 4.63k| } 776| 5.23k| } 777| 3.75k| } else if (node->m == 0) { ------------------ | Branch (777:28): [True: 2.03k, False: 1.72k] ------------------ 778| 2.03k| split = emit(prog, I_SPLIT); 779| 2.03k| compile(prog, node->x); 780| 2.03k| jump = emit(prog, I_JUMP); 781| 2.03k| if (node->ng) { ------------------ | Branch (781:29): [True: 948, False: 1.08k] ------------------ 782| 948| split->y = split + 1; 783| 948| split->x = prog->end; 784| 1.08k| } else { 785| 1.08k| split->x = split + 1; 786| 1.08k| split->y = prog->end; 787| 1.08k| } 788| 2.03k| jump->x = split; 789| 2.03k| } else { 790| 1.72k| split = emit(prog, I_SPLIT); 791| 1.72k| if (node->ng) { ------------------ | Branch (791:29): [True: 712, False: 1.01k] ------------------ 792| 712| split->y = inst; 793| 712| split->x = prog->end; 794| 1.01k| } else { 795| 1.01k| split->x = inst; 796| 1.01k| split->y = prog->end; 797| 1.01k| } 798| 1.72k| } 799| 5.12k| break; 800| | 801| 6.08k| case P_BOL: ------------------ | Branch (801:9): [True: 6.08k, False: 507k] ------------------ 802| 6.08k| emit(prog, I_BOL); 803| 6.08k| break; 804| 9.74k| case P_EOL: ------------------ | Branch (804:9): [True: 9.74k, False: 504k] ------------------ 805| 9.74k| emit(prog, I_EOL); 806| 9.74k| break; 807| 535| case P_WORD: ------------------ | Branch (807:9): [True: 535, False: 513k] ------------------ 808| 535| emit(prog, I_WORD); 809| 535| break; 810| 475| case P_NWORD: ------------------ | Branch (810:9): [True: 475, False: 513k] ------------------ 811| 475| emit(prog, I_NWORD); 812| 475| break; 813| | 814| 5.91k| case P_PAR: ------------------ | Branch (814:9): [True: 5.91k, False: 508k] ------------------ 815| 5.91k| inst = emit(prog, I_LPAR); 816| 5.91k| inst->n = node->n; 817| 5.91k| compile(prog, node->x); 818| 5.91k| inst = emit(prog, I_RPAR); 819| 5.91k| inst->n = node->n; 820| 5.91k| break; 821| 1.27k| case P_PLA: ------------------ | Branch (821:9): [True: 1.27k, False: 512k] ------------------ 822| 1.27k| split = emit(prog, I_PLA); 823| 1.27k| compile(prog, node->x); 824| 1.27k| emit(prog, I_END); 825| 1.27k| split->x = split + 1; 826| 1.27k| split->y = prog->end; 827| 1.27k| break; 828| 809| case P_NLA: ------------------ | Branch (828:9): [True: 809, False: 513k] ------------------ 829| 809| split = emit(prog, I_NLA); 830| 809| compile(prog, node->x); 831| 809| emit(prog, I_END); 832| 809| split->x = split + 1; 833| 809| split->y = prog->end; 834| 809| break; 835| | 836| 3.98k| case P_ANY: ------------------ | Branch (836:9): [True: 3.98k, False: 510k] ------------------ 837| 3.98k| emit(prog, I_ANY); 838| 3.98k| break; 839| 296k| case P_CHAR: ------------------ | Branch (839:9): [True: 296k, False: 217k] ------------------ 840| 296k| inst = emit(prog, I_CHAR); 841| 296k| inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; ------------------ | Branch (841:27): [True: 0, False: 296k] ------------------ 842| 296k| break; 843| 605| case P_CCLASS: ------------------ | Branch (843:9): [True: 605, False: 513k] ------------------ 844| 605| inst = emit(prog, I_CCLASS); 845| 605| inst->cc = node->cc; 846| 605| break; 847| 570| case P_NCCLASS: ------------------ | Branch (847:9): [True: 570, False: 513k] ------------------ 848| 570| inst = emit(prog, I_NCCLASS); 849| 570| inst->cc = node->cc; 850| 570| break; 851| 756| case P_REF: ------------------ | Branch (851:9): [True: 756, False: 513k] ------------------ 852| 756| inst = emit(prog, I_REF); 853| 756| inst->n = node->n; 854| 756| break; 855| 514k| } 856| 514k|} LLVMFuzzerTestOneInput: 44| 1.99k|int LLVMFuzzerTestOneInput(uint8_t *data, size_t size) { 45| | /* wrap random data in a null-terminated string */ 46| 1.99k| char *null_terminated = malloc(size + 1); 47| 1.99k| memcpy(null_terminated, data, size); 48| 1.99k| null_terminated[size] = '\0'; 49| | 50| 1.99k| const char *error; 51| 1.99k| Reprog *p = re_regcomp(null_terminated, 0, &error); 52| 1.99k| if (p != NULL) { ------------------ | Branch (52:13): [True: 921, False: 1.07k] ------------------ 53| 921| re_regfree(p); 54| 921| } 55| | 56| | /* cleanup */ 57| 1.99k| free(null_terminated); 58| | 59| 1.99k| return 0; 60| 1.99k|}