regexp.c:rd_calloc: 139| 2.07k|static RD_INLINE RD_UNUSED void *rd_calloc(size_t num, size_t sz) { 140| 2.07k| void *p = calloc(num, sz); 141| 2.07k| rd_assert(p); ------------------ | | 159| 2.07k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (141:9): [True: 0, False: 2.07k] | Branch (141:9): [True: 2.07k, False: 0] ------------------ 142| 2.07k| return p; 143| 2.07k|} regexp.c:rd_malloc: 145| 3.03k|static RD_INLINE RD_UNUSED void *rd_malloc(size_t sz) { 146| 3.03k| void *p = malloc(sz); 147| 3.03k| rd_assert(p); ------------------ | | 159| 3.03k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (147:9): [True: 0, False: 3.03k] | Branch (147:9): [True: 3.03k, False: 0] ------------------ 148| 3.03k| return p; 149| 3.03k|} regexp.c:rd_free: 157| 5.11k|static RD_INLINE RD_UNUSED void rd_free(void *ptr) { 158| 5.11k| free(ptr); 159| 5.11k|} re_regcomp: 1004| 2.08k|Reprog *re_regcomp(const char *pattern, int cflags, const char **errorp) { 1005| 2.08k| Reprog *prog; 1006| 2.08k| Restate *g; 1007| 2.08k| Renode *node; 1008| 2.08k| Reinst *split, *jump; 1009| 2.08k| int i; 1010| 2.08k| unsigned int ncount; 1011| 2.08k| size_t pattern_len = strlen(pattern); 1012| | 1013| 2.08k| if (pattern_len > 10000) { ------------------ | Branch (1013:13): [True: 9, False: 2.07k] ------------------ 1014| | /* Avoid stack exhaustion in recursive parseatom() et.al. */ 1015| 9| if (errorp) ------------------ | Branch (1015:21): [True: 9, False: 0] ------------------ 1016| 9| *errorp = "regexp pattern too long (max 10000)"; 1017| 9| return NULL; 1018| 9| } 1019| | 1020| 2.07k| prog = rd_calloc(1, sizeof(Reprog)); 1021| 2.07k| g = &prog->g; 1022| 2.07k| g->prog = prog; 1023| 2.07k| g->pstart = g->pend = rd_malloc(sizeof(Renode) * pattern_len * 2); 1024| | 1025| 2.07k| if (setjmp(g->kaboom)) { ------------------ | Branch (1025:13): [True: 1.12k, False: 955] ------------------ 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| 955| g->source = pattern; 1034| 955| g->ncclass = 0; 1035| 955| 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: 955] ------------------ 1037| 33.2k| g->sub[i] = 0; 1038| | 1039| 955| g->prog->flags = cflags; 1040| | 1041| 955| next(g); 1042| 955| node = parsealt(g); 1043| 955| if (g->lookahead == ')') ------------------ | Branch (1043:13): [True: 18, False: 937] ------------------ 1044| 18| die(g, "unmatched ')'"); 1045| 955| if (g->lookahead != 0) ------------------ | Branch (1045:13): [True: 0, False: 955] ------------------ 1046| 0| die(g, "syntax error"); 1047| | 1048| 955| g->prog->nsub = g->nsub; 1049| 955| ncount = count(node); 1050| 955| if (ncount > 10000) ------------------ | Branch (1050:13): [True: 45, False: 910] ------------------ 1051| 45| die(g, "regexp graph too large"); 1052| 955| g->prog->start = g->prog->end = 1053| 955| rd_malloc((ncount + 6) * sizeof(Reinst)); 1054| | 1055| 955| split = emit(g->prog, I_SPLIT); 1056| 955| split->x = split + 3; 1057| 955| split->y = split + 1; 1058| 955| emit(g->prog, I_ANYNL); 1059| 955| jump = emit(g->prog, I_JUMP); 1060| 955| jump->x = split; 1061| 955| emit(g->prog, I_LPAR); 1062| 955| compile(g->prog, node); 1063| 955| emit(g->prog, I_RPAR); 1064| 955| emit(g->prog, I_END); 1065| | 1066| |#ifdef TEST 1067| | dumpnode(node); 1068| | putchar('\n'); 1069| | dumpprog(g->prog); 1070| |#endif 1071| | 1072| 955| rd_free(g->pstart); 1073| | 1074| 955| if (errorp) ------------------ | Branch (1074:13): [True: 955, False: 0] ------------------ 1075| 955| *errorp = NULL; 1076| 955| return g->prog; 1077| 2.07k|} re_regfree: 1079| 955|void re_regfree(Reprog *prog) { 1080| 955| if (prog) { ------------------ | Branch (1080:13): [True: 955, False: 0] ------------------ 1081| 955| rd_free(prog->start); 1082| 955| rd_free(prog); 1083| 955| } 1084| 955|} regexp.c:next: 529| 222k|static void next(Restate *g) { 530| 222k| g->lookahead = lex(g); 531| 222k|} regexp.c:lex: 370| 222k|static int lex(Restate *g) { 371| 222k| int quoted = nextrune(g); 372| 222k| if (quoted) { ------------------ | Branch (372:13): [True: 3.76k, False: 218k] ------------------ 373| 3.76k| switch (g->yychar) { ------------------ | Branch (373:25): [True: 2.35k, False: 1.41k] ------------------ 374| 206| case 'b': ------------------ | Branch (374:17): [True: 206, False: 3.56k] ------------------ 375| 206| return L_WORD; 376| 320| case 'B': ------------------ | Branch (376:17): [True: 320, False: 3.44k] ------------------ 377| 320| return L_NWORD; 378| 88| case 'd': ------------------ | Branch (378:17): [True: 88, False: 3.67k] ------------------ 379| 88| newcclass(g); 380| 88| addranges_d(g); 381| 88| return L_CCLASS; 382| 97| case 's': ------------------ | Branch (382:17): [True: 97, False: 3.66k] ------------------ 383| 97| newcclass(g); 384| 97| addranges_s(g); 385| 97| return L_CCLASS; 386| 104| case 'w': ------------------ | Branch (386:17): [True: 104, False: 3.66k] ------------------ 387| 104| newcclass(g); 388| 104| addranges_w(g); 389| 104| return L_CCLASS; 390| 107| case 'D': ------------------ | Branch (390:17): [True: 107, False: 3.65k] ------------------ 391| 107| newcclass(g); 392| 107| addranges_d(g); 393| 107| return L_NCCLASS; 394| 129| case 'S': ------------------ | Branch (394:17): [True: 129, False: 3.63k] ------------------ 395| 129| newcclass(g); 396| 129| addranges_s(g); 397| 129| return L_NCCLASS; 398| 91| case 'W': ------------------ | Branch (398:17): [True: 91, False: 3.67k] ------------------ 399| 91| newcclass(g); 400| 91| addranges_w(g); 401| 91| return L_NCCLASS; 402| 1.21k| case '0': ------------------ | Branch (402:17): [True: 1.21k, False: 2.55k] ------------------ 403| 1.21k| g->yychar = 0; 404| 1.21k| return L_CHAR; 405| 3.76k| } 406| 1.41k| if (g->yychar >= '0' && g->yychar <= '9') { ------------------ | Branch (406:21): [True: 1.19k, False: 219] | Branch (406:41): [True: 975, False: 216] ------------------ 407| 975| g->yychar -= '0'; 408| 975| if (*g->source >= '0' && *g->source <= '9') ------------------ | Branch (408:29): [True: 657, False: 318] | Branch (408:50): [True: 202, False: 455] ------------------ 409| 202| g->yychar = g->yychar * 10 + *g->source++ - '0'; 410| 975| return L_REF; 411| 975| } 412| 435| return L_CHAR; 413| 1.41k| } 414| | 415| 218k| switch (g->yychar) { ------------------ | Branch (415:17): [True: 36.1k, False: 182k] ------------------ 416| 1.13k| case 0: ------------------ | Branch (416:9): [True: 1.13k, False: 217k] ------------------ 417| 1.92k| case '$': ------------------ | Branch (417:9): [True: 786, False: 218k] ------------------ 418| 4.14k| case ')': ------------------ | Branch (418:9): [True: 2.21k, False: 216k] ------------------ 419| 7.86k| case '*': ------------------ | Branch (419:9): [True: 3.72k, False: 215k] ------------------ 420| 8.61k| case '+': ------------------ | Branch (420:9): [True: 750, False: 218k] ------------------ 421| 11.1k| case '.': ------------------ | Branch (421:9): [True: 2.52k, False: 216k] ------------------ 422| 14.8k| case '?': ------------------ | Branch (422:9): [True: 3.68k, False: 215k] ------------------ 423| 30.9k| case '^': ------------------ | Branch (423:9): [True: 16.1k, False: 202k] ------------------ 424| 36.1k| case '|': ------------------ | Branch (424:9): [True: 5.18k, False: 213k] ------------------ 425| 36.1k| return g->yychar; 426| 218k| } 427| | 428| 182k| if (g->yychar == '{') ------------------ | Branch (428:13): [True: 2.22k, False: 180k] ------------------ 429| 2.22k| return lexcount(g); 430| 180k| if (g->yychar == '[') ------------------ | Branch (430:13): [True: 769, False: 179k] ------------------ 431| 769| return lexclass(g); 432| 179k| if (g->yychar == '(') { ------------------ | Branch (432:13): [True: 3.84k, False: 175k] ------------------ 433| 3.84k| if (g->source[0] == '?') { ------------------ | Branch (433:21): [True: 2.64k, False: 1.19k] ------------------ 434| 2.64k| if (g->source[1] == ':') { ------------------ | Branch (434:29): [True: 832, False: 1.81k] ------------------ 435| 832| g->source += 2; 436| 832| return L_NC; 437| 832| } 438| 1.81k| if (g->source[1] == '=') { ------------------ | Branch (438:29): [True: 790, False: 1.02k] ------------------ 439| 790| g->source += 2; 440| 790| return L_PLA; 441| 790| } 442| 1.02k| if (g->source[1] == '!') { ------------------ | Branch (442:29): [True: 1.00k, False: 21] ------------------ 443| 1.00k| g->source += 2; 444| 1.00k| return L_NLA; 445| 1.00k| } 446| 1.02k| } 447| 1.21k| return '('; 448| 3.84k| } 449| | 450| 175k| return L_CHAR; 451| 179k|} regexp.c:nextrune: 131| 229k|static int nextrune(Restate *g) { 132| 229k| g->source += chartorune(&g->yychar, g->source); 133| 229k| if (g->yychar == '\\') { ------------------ | Branch (133:13): [True: 9.73k, False: 220k] ------------------ 134| 9.73k| g->source += chartorune(&g->yychar, g->source); 135| 9.73k| switch (g->yychar) { ------------------ | Branch (135:25): [True: 4.32k, False: 5.40k] ------------------ 136| 6| case 0: ------------------ | Branch (136:17): [True: 6, False: 9.73k] ------------------ 137| 6| die(g, "unterminated escape sequence"); 138| 305| case 'f': ------------------ | Branch (138:17): [True: 299, False: 9.43k] ------------------ 139| 305| g->yychar = '\f'; 140| 305| return 0; 141| 241| case 'n': ------------------ | Branch (141:17): [True: 241, False: 9.49k] ------------------ 142| 241| g->yychar = '\n'; 143| 241| return 0; 144| 194| case 'r': ------------------ | Branch (144:17): [True: 194, False: 9.54k] ------------------ 145| 194| g->yychar = '\r'; 146| 194| return 0; 147| 195| case 't': ------------------ | Branch (147:17): [True: 195, False: 9.54k] ------------------ 148| 195| g->yychar = '\t'; 149| 195| return 0; 150| 194| case 'v': ------------------ | Branch (150:17): [True: 194, False: 9.54k] ------------------ 151| 194| g->yychar = '\v'; 152| 194| return 0; 153| 206| case 'c': ------------------ | Branch (153:17): [True: 206, False: 9.53k] ------------------ 154| 206| g->yychar = (*g->source++) & 31; 155| 206| return 0; 156| 1.56k| case 'x': ------------------ | Branch (156:17): [True: 1.56k, False: 8.17k] ------------------ 157| 1.56k| g->yychar = hex(g, *g->source++) << 4; 158| 1.56k| g->yychar += hex(g, *g->source++); 159| 1.56k| if (g->yychar == 0) { ------------------ | Branch (159:29): [True: 511, False: 1.05k] ------------------ 160| 511| g->yychar = '0'; 161| 511| return 1; 162| 511| } 163| 1.05k| return 0; 164| 1.43k| case 'u': ------------------ | Branch (164:17): [True: 1.43k, False: 8.30k] ------------------ 165| 1.43k| g->yychar = hex(g, *g->source++) << 12; 166| 1.43k| g->yychar += hex(g, *g->source++) << 8; 167| 1.43k| g->yychar += hex(g, *g->source++) << 4; 168| 1.43k| g->yychar += hex(g, *g->source++); 169| 1.43k| if (g->yychar == 0) { ------------------ | Branch (169:29): [True: 471, False: 960] ------------------ 170| 471| g->yychar = '0'; 171| 471| return 1; 172| 471| } 173| 960| return 0; 174| 9.73k| } 175| 5.40k| if (strchr(ESCAPES, g->yychar)) ------------------ | | 129| 5.40k|#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" ------------------ | Branch (175:21): [True: 4.93k, False: 474] ------------------ 176| 4.93k| return 1; 177| 474| if (isalpharune(g->yychar) || ------------------ | Branch (177:21): [True: 11, False: 463] ------------------ 178| 463| g->yychar == '_') /* check identity escape */ ------------------ | Branch (178:21): [True: 2, False: 461] ------------------ 179| 13| die(g, "invalid escape character"); 180| 474| return 0; 181| 5.40k| } 182| 220k| return 0; 183| 229k|} regexp.c:chartorune: 37| 239k|static int chartorune(Rune *r, const char *s) { 38| | /* TODO: Add UTF-8 decoding */ 39| 239k| *r = *s; 40| 239k| return 1; 41| 239k|} regexp.c:hex: 111| 8.58k|static int hex(Restate *g, int c) { 112| 8.58k| if (c >= '0' && c <= '9') ------------------ | Branch (112:13): [True: 8.41k, False: 169] | Branch (112:25): [True: 3.64k, False: 4.76k] ------------------ 113| 3.64k| return c - '0'; 114| 4.93k| if (c >= 'a' && c <= 'f') ------------------ | Branch (114:13): [True: 2.11k, False: 2.81k] | Branch (114:25): [True: 2.08k, False: 31] ------------------ 115| 2.08k| return c - 'a' + 0xA; 116| 2.84k| if (c >= 'A' && c <= 'F') ------------------ | Branch (116:13): [True: 2.65k, False: 191] | Branch (116:25): [True: 2.59k, False: 63] ------------------ 117| 2.59k| return c - 'A' + 0xA; 118| 254| die(g, "invalid escape sequence"); 119| 254| return 0; 120| 2.84k|} regexp.c:isalpharune: 25| 474|static int isalpharune(Rune c) { 26| | /* TODO: Add unicode support */ 27| 474| return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); ------------------ | Branch (27:17): [True: 261, False: 213] | Branch (27:29): [True: 5, False: 256] | Branch (27:43): [True: 248, False: 221] | Branch (27:55): [True: 6, False: 242] ------------------ 28| 474|} 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| 934|static void addranges_d(Restate *g) { 235| 934| addrange(g, '0', '9'); 236| 934|} regexp.c:addrange: 225| 8.89k|static void addrange(Restate *g, Rune a, Rune b) { 226| 8.89k| if (a > b) ------------------ | Branch (226:13): [True: 51, False: 8.84k] ------------------ 227| 51| die(g, "invalid character class range"); 228| 8.89k| if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) ------------------ | | 21| 8.89k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (228:13): [True: 45, False: 8.84k] ------------------ 229| 45| die(g, "too many character class ranges"); 230| 8.89k| *g->yycc->end++ = a; 231| 8.89k| *g->yycc->end++ = b; 232| 8.89k|} regexp.c:addranges_s: 243| 455|static void addranges_s(Restate *g) { 244| 455| addrange(g, 0x9, 0x9); 245| 455| addrange(g, 0xA, 0xD); 246| 455| addrange(g, 0x20, 0x20); 247| 455| addrange(g, 0xA0, 0xA0); 248| 455| addrange(g, 0x2028, 0x2029); 249| 455| addrange(g, 0xFEFF, 0xFEFF); 250| 455|} regexp.c:addranges_w: 262| 300|static void addranges_w(Restate *g) { 263| 300| addrange(g, '0', '9'); 264| 300| addrange(g, 'A', 'Z'); 265| 300| addrange(g, '_', '_'); 266| 300| addrange(g, 'a', 'z'); 267| 300|} regexp.c:lexcount: 185| 2.22k|static int lexcount(Restate *g) { 186| 2.22k| g->yychar = *g->source++; 187| | 188| 2.22k| g->yymin = dec(g, g->yychar); 189| 2.22k| g->yychar = *g->source++; 190| 4.23k| while (g->yychar != ',' && g->yychar != '}') { ------------------ | Branch (190:16): [True: 3.32k, False: 915] | Branch (190:36): [True: 2.01k, False: 1.31k] ------------------ 191| 2.01k| g->yymin = g->yymin * 10 + dec(g, g->yychar); 192| 2.01k| g->yychar = *g->source++; 193| 2.01k| } 194| 2.22k| if (g->yymin >= REPINF) ------------------ | | 43| 2.22k|#define REPINF 255 ------------------ | Branch (194:13): [True: 22, False: 2.20k] ------------------ 195| 22| die(g, "numeric overflow"); 196| | 197| 2.22k| if (g->yychar == ',') { ------------------ | Branch (197:13): [True: 857, False: 1.37k] ------------------ 198| 857| g->yychar = *g->source++; 199| 857| if (g->yychar == '}') { ------------------ | Branch (199:21): [True: 257, False: 600] ------------------ 200| 257| g->yymax = REPINF; ------------------ | | 43| 257|#define REPINF 255 ------------------ 201| 600| } else { 202| 600| g->yymax = dec(g, g->yychar); 203| 600| g->yychar = *g->source++; 204| 1.48k| while (g->yychar != '}') { ------------------ | Branch (204:32): [True: 889, False: 600] ------------------ 205| 889| g->yymax = g->yymax * 10 + dec(g, g->yychar); 206| 889| g->yychar = *g->source++; 207| 889| } 208| 600| if (g->yymax >= REPINF) ------------------ | | 43| 600|#define REPINF 255 ------------------ | Branch (208:29): [True: 18, False: 582] ------------------ 209| 18| die(g, "numeric overflow"); 210| 600| } 211| 1.37k| } else { 212| 1.37k| g->yymax = g->yymin; 213| 1.37k| } 214| | 215| 2.22k| return L_COUNT; 216| 2.22k|} regexp.c:dec: 122| 5.72k|static int dec(Restate *g, int c) { 123| 5.72k| if (c >= '0' && c <= '9') ------------------ | Branch (123:13): [True: 5.64k, False: 85] | Branch (123:25): [True: 5.60k, False: 35] ------------------ 124| 5.60k| return c - '0'; 125| 120| die(g, "invalid quantifier"); 126| 120| return 0; 127| 5.72k|} regexp.c:lexclass: 277| 769|static int lexclass(Restate *g) { 278| 769| int type = L_CCLASS; 279| 769| int quoted, havesave, havedash; 280| 769| Rune save = 0; 281| | 282| 769| newcclass(g); 283| | 284| 769| quoted = nextrune(g); 285| 769| if (!quoted && g->yychar == '^') { ------------------ | Branch (285:13): [True: 554, False: 215] | Branch (285:24): [True: 34, False: 520] ------------------ 286| 34| type = L_NCCLASS; 287| 34| quoted = nextrune(g); 288| 34| } 289| | 290| 769| havesave = havedash = 0; 291| 7.06k| for (;;) { 292| 7.06k| if (g->yychar == 0) ------------------ | Branch (292:21): [True: 217, False: 6.85k] ------------------ 293| 217| die(g, "unterminated character class"); 294| 7.06k| if (!quoted && g->yychar == ']') ------------------ | Branch (294:21): [True: 4.70k, False: 2.36k] | Branch (294:32): [True: 456, False: 4.24k] ------------------ 295| 456| break; 296| | 297| 6.61k| if (!quoted && g->yychar == '-') { ------------------ | Branch (297:21): [True: 4.24k, False: 2.36k] | Branch (297:32): [True: 2.18k, False: 2.05k] ------------------ 298| 2.18k| if (havesave) { ------------------ | Branch (298:29): [True: 1.60k, False: 580] ------------------ 299| 1.60k| if (havedash) { ------------------ | Branch (299:37): [True: 483, False: 1.12k] ------------------ 300| 483| addrange(g, save, '-'); 301| 483| havesave = havedash = 0; 302| 1.12k| } else { 303| 1.12k| havedash = 1; 304| 1.12k| } 305| 1.60k| } else { 306| 580| save = '-'; 307| 580| havesave = 1; 308| 580| } 309| 4.42k| } else if (quoted && strchr("DSWdsw", g->yychar)) { ------------------ | Branch (309:28): [True: 2.14k, False: 2.27k] | Branch (309:38): [True: 1.48k, False: 665] ------------------ 310| 1.48k| if (havesave) { ------------------ | Branch (310:29): [True: 537, False: 947] ------------------ 311| 537| addrange(g, save, save); 312| 537| if (havedash) ------------------ | Branch (312:37): [True: 195, False: 342] ------------------ 313| 195| addrange(g, '-', '-'); 314| 537| } 315| 1.48k| switch (g->yychar) { ------------------ | Branch (315:33): [True: 1.48k, False: 3] ------------------ 316| 741| case 'd': ------------------ | Branch (316:25): [True: 741, False: 743] ------------------ 317| 741| addranges_d(g); 318| 741| break; 319| 231| case 's': ------------------ | Branch (319:25): [True: 231, False: 1.25k] ------------------ 320| 231| addranges_s(g); 321| 231| break; 322| 107| case 'w': ------------------ | Branch (322:25): [True: 107, False: 1.37k] ------------------ 323| 107| addranges_w(g); 324| 107| break; 325| 313| case 'D': ------------------ | Branch (325:25): [True: 313, False: 1.17k] ------------------ 326| 313| addranges_D(g); 327| 313| break; 328| 3| case 'S': ------------------ | Branch (328:25): [True: 3, False: 1.48k] ------------------ 329| 3| addranges_S(g); 330| 3| break; 331| 86| case 'W': ------------------ | Branch (331:25): [True: 86, False: 1.39k] ------------------ 332| 86| addranges_W(g); 333| 86| break; 334| 1.48k| } 335| 1.44k| havesave = havedash = 0; 336| 2.94k| } else { 337| 2.94k| if (quoted) { ------------------ | Branch (337:29): [True: 665, False: 2.27k] ------------------ 338| 665| if (g->yychar == 'b') ------------------ | Branch (338:37): [True: 196, False: 469] ------------------ 339| 196| g->yychar = '\b'; 340| 469| else if (g->yychar == '0') ------------------ | Branch (340:42): [True: 198, False: 271] ------------------ 341| 198| g->yychar = 0; 342| | /* else identity escape */ 343| 665| } 344| 2.94k| if (havesave) { ------------------ | Branch (344:29): [True: 1.57k, False: 1.36k] ------------------ 345| 1.57k| if (havedash) { ------------------ | Branch (345:37): [True: 395, False: 1.18k] ------------------ 346| 395| addrange(g, save, g->yychar); 347| 395| havesave = havedash = 0; 348| 1.18k| } else { 349| 1.18k| addrange(g, save, save); 350| 1.18k| save = g->yychar; 351| 1.18k| } 352| 1.57k| } else { 353| 1.36k| save = g->yychar; 354| 1.36k| havesave = 1; 355| 1.36k| } 356| 2.94k| } 357| | 358| 6.57k| quoted = nextrune(g); 359| 6.57k| } 360| | 361| 733| if (havesave) { ------------------ | Branch (361:13): [True: 180, False: 553] ------------------ 362| 180| addrange(g, save, save); 363| 180| if (havedash) ------------------ | Branch (363:21): [True: 46, False: 134] ------------------ 364| 46| addrange(g, '-', '-'); 365| 180| } 366| | 367| 733| return type; 368| 769|} regexp.c:addranges_D: 238| 313|static void addranges_D(Restate *g) { 239| 313| addrange(g, 0, '0' - 1); 240| 313| addrange(g, '9' + 1, 0xFFFF); 241| 313|} regexp.c:addranges_S: 252| 3|static void addranges_S(Restate *g) { 253| 3| addrange(g, 0, 0x9 - 1); 254| 3| addrange(g, 0x9 + 1, 0xA - 1); 255| 3| addrange(g, 0xD + 1, 0x20 - 1); 256| 3| addrange(g, 0x20 + 1, 0xA0 - 1); 257| 3| addrange(g, 0xA0 + 1, 0x2028 - 1); 258| 3| addrange(g, 0x2029 + 1, 0xFEFF - 1); 259| 3| addrange(g, 0xFEFF + 1, 0xFFFF); 260| 3|} regexp.c:addranges_W: 269| 86|static void addranges_W(Restate *g) { 270| 86| addrange(g, 0, '0' - 1); 271| 86| addrange(g, '9' + 1, 'A' - 1); 272| 86| addrange(g, 'Z' + 1, '_' - 1); 273| 86| addrange(g, '_' + 1, 'a' - 1); 274| 86| addrange(g, 'z' + 1, 0xFFFF); 275| 86|} regexp.c:parsealt: 654| 5.31k|static Renode *parsealt(Restate *g) { 655| 5.31k| Renode *alt, *x; 656| 5.31k| alt = parsecat(g); 657| 10.5k| while (re_accept(g, '|')) { ------------------ | Branch (657:16): [True: 5.18k, False: 5.31k] ------------------ 658| 5.18k| x = alt; 659| 5.18k| alt = newnode(g, P_ALT); 660| 5.18k| alt->x = x; 661| 5.18k| alt->y = parsecat(g); 662| 5.18k| } 663| 5.31k| return alt; 664| 5.31k|} regexp.c:parsecat: 638| 10.5k|static Renode *parsecat(Restate *g) { 639| 10.5k| Renode *cat, *x; 640| 10.5k| if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { ------------------ | Branch (640:13): [True: 10.3k, False: 111] | Branch (640:29): [True: 5.99k, False: 4.40k] | Branch (640:52): [True: 4.59k, False: 1.39k] ------------------ 641| 4.59k| cat = parserep(g); 642| 203k| while (g->lookahead && g->lookahead != '|' && ------------------ | Branch (642:24): [True: 200k, False: 2.98k] | Branch (642:40): [True: 199k, False: 787] ------------------ 643| 199k| g->lookahead != ')') { ------------------ | Branch (643:24): [True: 198k, False: 822] ------------------ 644| 198k| x = cat; 645| 198k| cat = newnode(g, P_CAT); 646| 198k| cat->x = x; 647| 198k| cat->y = parserep(g); 648| 198k| } 649| 4.59k| return cat; 650| 4.59k| } 651| 5.90k| return NULL; 652| 10.5k|} regexp.c:parserep: 609| 203k|static Renode *parserep(Restate *g) { 610| 203k| Renode *atom; 611| | 612| 203k| if (re_accept(g, '^')) ------------------ | Branch (612:13): [True: 16.1k, False: 187k] ------------------ 613| 16.1k| return newnode(g, P_BOL); 614| 187k| if (re_accept(g, '$')) ------------------ | Branch (614:13): [True: 786, False: 186k] ------------------ 615| 786| return newnode(g, P_EOL); 616| 186k| if (re_accept(g, L_WORD)) ------------------ | Branch (616:13): [True: 206, False: 186k] ------------------ 617| 206| return newnode(g, P_WORD); 618| 186k| if (re_accept(g, L_NWORD)) ------------------ | Branch (618:13): [True: 320, False: 185k] ------------------ 619| 320| return newnode(g, P_NWORD); 620| | 621| 185k| atom = parseatom(g); 622| 185k| if (g->lookahead == L_COUNT) { ------------------ | Branch (622:13): [True: 1.98k, False: 183k] ------------------ 623| 1.98k| int min = g->yymin, max = g->yymax; 624| 1.98k| next(g); 625| 1.98k| if (max < min) ------------------ | Branch (625:21): [True: 6, False: 1.98k] ------------------ 626| 6| die(g, "invalid quantifier"); 627| 1.98k| return newrep(g, atom, re_accept(g, '?'), min, max); 628| 1.98k| } 629| 183k| if (re_accept(g, '*')) ------------------ | Branch (629:13): [True: 3.71k, False: 180k] ------------------ 630| 3.71k| return newrep(g, atom, re_accept(g, '?'), 0, REPINF); ------------------ | | 43| 3.71k|#define REPINF 255 ------------------ 631| 180k| if (re_accept(g, '+')) ------------------ | Branch (631:13): [True: 739, False: 179k] ------------------ 632| 739| return newrep(g, atom, re_accept(g, '?'), 1, REPINF); ------------------ | | 43| 739|#define REPINF 255 ------------------ 633| 179k| if (re_accept(g, '?')) ------------------ | Branch (633:13): [True: 654, False: 178k] ------------------ 634| 654| return newrep(g, atom, re_accept(g, '?'), 0, 1); 635| 178k| return atom; 636| 179k|} regexp.c:parseatom: 543| 185k|static Renode *parseatom(Restate *g) { 544| 185k| Renode *atom; 545| 185k| if (g->lookahead == L_CHAR) { ------------------ | Branch (545:13): [True: 177k, False: 8.54k] ------------------ 546| 177k| atom = newnode(g, P_CHAR); 547| 177k| atom->c = g->yychar; 548| 177k| next(g); 549| 177k| return atom; 550| 177k| } 551| 8.54k| if (g->lookahead == L_CCLASS) { ------------------ | Branch (551:13): [True: 711, False: 7.83k] ------------------ 552| 711| atom = newnode(g, P_CCLASS); 553| 711| atom->cc = g->yycc; 554| 711| next(g); 555| 711| return atom; 556| 711| } 557| 7.83k| if (g->lookahead == L_NCCLASS) { ------------------ | Branch (557:13): [True: 352, False: 7.48k] ------------------ 558| 352| atom = newnode(g, P_NCCLASS); 559| 352| atom->cc = g->yycc; 560| 352| next(g); 561| 352| return atom; 562| 352| } 563| 7.48k| if (g->lookahead == L_REF) { ------------------ | Branch (563:13): [True: 975, False: 6.50k] ------------------ 564| 975| atom = newnode(g, P_REF); 565| 975| if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) ------------------ | Branch (565:21): [True: 0, False: 975] | Branch (565:39): [True: 24, False: 951] | Branch (565:62): [True: 10, False: 941] ------------------ 566| 34| die(g, "invalid back-reference"); 567| 975| atom->n = g->yychar; 568| 975| atom->x = g->sub[g->yychar]; 569| 975| next(g); 570| 975| return atom; 571| 975| } 572| 6.50k| if (re_accept(g, '.')) ------------------ | Branch (572:13): [True: 2.52k, False: 3.97k] ------------------ 573| 2.52k| return newnode(g, P_ANY); 574| 3.97k| if (re_accept(g, '(')) { ------------------ | Branch (574:13): [True: 1.21k, False: 2.76k] ------------------ 575| 1.21k| atom = newnode(g, P_PAR); 576| 1.21k| if (g->nsub == MAXSUB) ------------------ | | 45| 1.21k|#define MAXSUB REG_MAXSUB ------------------ | Branch (576:21): [True: 7, False: 1.21k] ------------------ 577| 7| die(g, "too many captures"); 578| 1.21k| atom->n = g->nsub++; 579| 1.21k| atom->x = parsealt(g); 580| 1.21k| g->sub[atom->n] = atom; 581| 1.21k| if (!re_accept(g, ')')) ------------------ | Branch (581:21): [True: 57, False: 1.16k] ------------------ 582| 57| die(g, "unmatched '('"); 583| 1.21k| return atom; 584| 1.21k| } 585| 2.76k| if (re_accept(g, L_NC)) { ------------------ | Branch (585:13): [True: 832, False: 1.92k] ------------------ 586| 832| atom = parsealt(g); 587| 832| if (!re_accept(g, ')')) ------------------ | Branch (587:21): [True: 14, False: 818] ------------------ 588| 14| die(g, "unmatched '('"); 589| 832| return atom; 590| 832| } 591| 1.92k| if (re_accept(g, L_PLA)) { ------------------ | Branch (591:13): [True: 790, False: 1.13k] ------------------ 592| 790| atom = newnode(g, P_PLA); 593| 790| atom->x = parsealt(g); 594| 790| if (!re_accept(g, ')')) ------------------ | Branch (594:21): [True: 9, False: 781] ------------------ 595| 9| die(g, "unmatched '('"); 596| 790| return atom; 597| 790| } 598| 1.13k| if (re_accept(g, L_NLA)) { ------------------ | Branch (598:13): [True: 1.00k, False: 133] ------------------ 599| 1.00k| atom = newnode(g, P_NLA); 600| 1.00k| atom->x = parsealt(g); 601| 1.00k| if (!re_accept(g, ')')) ------------------ | Branch (601:21): [True: 10, False: 995] ------------------ 602| 10| die(g, "unmatched '('"); 603| 1.00k| return atom; 604| 1.00k| } 605| 133| die(g, "syntax error"); 606| | return NULL; 607| 1.13k|} regexp.c:newrep: 518| 7.08k|static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { 519| 7.08k| Renode *rep = newnode(g, P_REP); 520| 7.08k| if (max == REPINF && empty(atom)) ------------------ | | 43| 14.1k|#define REPINF 255 ------------------ | Branch (520:13): [True: 4.70k, False: 2.38k] | Branch (520:30): [True: 37, False: 4.66k] ------------------ 521| 37| die(g, "infinite loop matching the empty string"); 522| 7.08k| rep->ng = ng; 523| 7.08k| rep->m = min; 524| 7.08k| rep->n = max; 525| 7.08k| rep->x = atom; 526| 7.08k| return rep; 527| 7.08k|} regexp.c:empty: 494| 12.6k|static int empty(Renode *node) { 495| 12.6k| if (!node) ------------------ | Branch (495:13): [True: 715, False: 11.9k] ------------------ 496| 715| return 1; 497| 11.9k| switch (node->type) { 498| 369| default: ------------------ | Branch (498:9): [True: 369, False: 11.5k] ------------------ 499| 369| return 1; 500| 1.95k| case P_CAT: ------------------ | Branch (500:9): [True: 1.95k, False: 9.95k] ------------------ 501| 1.95k| return empty(node->x) && empty(node->y); ------------------ | Branch (501:24): [True: 1.71k, False: 242] | Branch (501:42): [True: 1.43k, False: 276] ------------------ 502| 522| case P_ALT: ------------------ | Branch (502:9): [True: 522, False: 11.3k] ------------------ 503| 522| return empty(node->x) || empty(node->y); ------------------ | Branch (503:24): [True: 306, False: 216] | Branch (503:42): [True: 108, False: 108] ------------------ 504| 946| case P_REP: ------------------ | Branch (504:9): [True: 946, False: 10.9k] ------------------ 505| 946| return empty(node->x) || node->m == 0; ------------------ | Branch (505:24): [True: 194, False: 752] | Branch (505:42): [True: 665, False: 87] ------------------ 506| 1.75k| case P_PAR: ------------------ | Branch (506:9): [True: 1.75k, False: 10.1k] ------------------ 507| 1.75k| return empty(node->x); 508| 812| case P_REF: ------------------ | Branch (508:9): [True: 812, False: 11.0k] ------------------ 509| 812| return empty(node->x); 510| 578| case P_ANY: ------------------ | Branch (510:9): [True: 578, False: 11.3k] ------------------ 511| 5.14k| case P_CHAR: ------------------ | Branch (511:9): [True: 4.56k, False: 7.34k] ------------------ 512| 5.34k| case P_CCLASS: ------------------ | Branch (512:9): [True: 204, False: 11.7k] ------------------ 513| 5.54k| case P_NCCLASS: ------------------ | Branch (513:9): [True: 200, False: 11.7k] ------------------ 514| 5.54k| return 0; 515| 11.9k| } 516| 11.9k|} regexp.c:re_accept: 533| 1.33M|static int re_accept(Restate *g, int t) { 534| 1.33M| if (g->lookahead == t) { ------------------ | Branch (534:13): [True: 39.2k, False: 1.29M] ------------------ 535| 39.2k| next(g); 536| 39.2k| return 1; 537| 39.2k| } 538| 1.29M| return 0; 539| 1.33M|} regexp.c:newnode: 482| 413k|static Renode *newnode(Restate *g, int type) { 483| 413k| Renode *node = g->pend++; 484| 413k| node->type = type; 485| 413k| node->cc = NULL; 486| 413k| node->c = 0; 487| 413k| node->ng = 0; 488| 413k| node->m = 0; 489| 413k| node->n = 0; 490| | node->x = node->y = NULL; 491| 413k| return node; 492| 413k|} 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| 373k|static unsigned int count(Renode *node) { 698| 373k| unsigned int min, max; 699| 373k| if (!node) ------------------ | Branch (699:13): [True: 5.02k, False: 368k] ------------------ 700| 5.02k| return 0; 701| 368k| switch (node->type) { 702| 178k| default: ------------------ | Branch (702:9): [True: 178k, False: 189k] ------------------ 703| 178k| return 1; 704| 178k| case P_CAT: ------------------ | Branch (704:9): [True: 178k, False: 190k] ------------------ 705| 178k| return count(node->x) + count(node->y); 706| 4.52k| case P_ALT: ------------------ | Branch (706:9): [True: 4.52k, False: 363k] ------------------ 707| 4.52k| return count(node->x) + count(node->y) + 2; 708| 5.44k| case P_REP: ------------------ | Branch (708:9): [True: 5.44k, False: 362k] ------------------ 709| 5.44k| min = node->m; 710| 5.44k| max = node->n; 711| 5.44k| if (min == max) ------------------ | Branch (711:21): [True: 916, False: 4.53k] ------------------ 712| 916| return count(node->x) * min; 713| 4.53k| if (max < REPINF) ------------------ | | 43| 4.53k|#define REPINF 255 ------------------ | Branch (713:21): [True: 922, False: 3.61k] ------------------ 714| 922| return count(node->x) * max + (max - min); 715| 3.61k| return count(node->x) * (min + 1) + 2; 716| 570| case P_PAR: ------------------ | Branch (716:9): [True: 570, False: 367k] ------------------ 717| 570| return count(node->x) + 2; 718| 468| case P_PLA: ------------------ | Branch (718:9): [True: 468, False: 367k] ------------------ 719| 468| return count(node->x) + 2; 720| 432| case P_NLA: ------------------ | Branch (720:9): [True: 432, False: 367k] ------------------ 721| 432| return count(node->x) + 2; 722| 368k| } 723| 368k|} regexp.c:emit: 725| 346k|static Reinst *emit(Reprog *prog, int opcode) { 726| 346k| Reinst *inst = prog->end++; 727| 346k| inst->opcode = opcode; 728| 346k| inst->n = 0; 729| 346k| inst->c = 0; 730| 346k| inst->cc = NULL; 731| | inst->x = inst->y = NULL; 732| 346k| return inst; 733| 346k|} regexp.c:compile: 735| 501k|static void compile(Reprog *prog, Renode *node) { 736| 501k| Reinst *inst, *split, *jump; 737| 501k| unsigned int i; 738| | 739| 501k| if (!node) ------------------ | Branch (739:13): [True: 7.76k, False: 493k] ------------------ 740| 7.76k| return; 741| | 742| 493k| switch (node->type) { ------------------ | Branch (742:17): [True: 493k, False: 0] ------------------ 743| 170k| case P_CAT: ------------------ | Branch (743:9): [True: 170k, False: 323k] ------------------ 744| 170k| compile(prog, node->x); 745| 170k| compile(prog, node->y); 746| 170k| break; 747| | 748| 5.62k| case P_ALT: ------------------ | Branch (748:9): [True: 5.62k, False: 488k] ------------------ 749| 5.62k| split = emit(prog, I_SPLIT); 750| 5.62k| compile(prog, node->x); 751| 5.62k| jump = emit(prog, I_JUMP); 752| 5.62k| compile(prog, node->y); 753| 5.62k| split->x = split + 1; 754| 5.62k| split->y = jump + 1; 755| 5.62k| jump->x = prog->end; 756| 5.62k| break; 757| | 758| 8.27k| case P_REP: ------------------ | Branch (758:9): [True: 8.27k, False: 485k] ------------------ 759| 142k| for (i = 0; i < node->m; ++i) { ------------------ | Branch (759:29): [True: 133k, False: 8.27k] ------------------ 760| 133k| inst = prog->end; 761| 133k| compile(prog, node->x); 762| 133k| } 763| 8.27k| if (node->m == node->n) ------------------ | Branch (763:21): [True: 2.37k, False: 5.89k] ------------------ 764| 2.37k| break; 765| 5.89k| if (node->n < REPINF) { ------------------ | | 43| 5.89k|#define REPINF 255 ------------------ | Branch (765:21): [True: 1.26k, False: 4.63k] ------------------ 766| 5.68k| for (i = node->m; i < node->n; ++i) { ------------------ | Branch (766:43): [True: 4.41k, False: 1.26k] ------------------ 767| 4.41k| split = emit(prog, I_SPLIT); 768| 4.41k| compile(prog, node->x); 769| 4.41k| if (node->ng) { ------------------ | Branch (769:37): [True: 593, False: 3.82k] ------------------ 770| 593| split->y = split + 1; 771| 593| split->x = prog->end; 772| 3.82k| } else { 773| 3.82k| split->x = split + 1; 774| 3.82k| split->y = prog->end; 775| 3.82k| } 776| 4.41k| } 777| 4.63k| } else if (node->m == 0) { ------------------ | Branch (777:28): [True: 3.09k, False: 1.54k] ------------------ 778| 3.09k| split = emit(prog, I_SPLIT); 779| 3.09k| compile(prog, node->x); 780| 3.09k| jump = emit(prog, I_JUMP); 781| 3.09k| if (node->ng) { ------------------ | Branch (781:29): [True: 1.36k, False: 1.72k] ------------------ 782| 1.36k| split->y = split + 1; 783| 1.36k| split->x = prog->end; 784| 1.72k| } else { 785| 1.72k| split->x = split + 1; 786| 1.72k| split->y = prog->end; 787| 1.72k| } 788| 3.09k| jump->x = split; 789| 3.09k| } else { 790| 1.54k| split = emit(prog, I_SPLIT); 791| 1.54k| if (node->ng) { ------------------ | Branch (791:29): [True: 422, False: 1.11k] ------------------ 792| 422| split->y = inst; 793| 422| split->x = prog->end; 794| 1.11k| } else { 795| 1.11k| split->x = inst; 796| 1.11k| split->y = prog->end; 797| 1.11k| } 798| 1.54k| } 799| 5.89k| break; 800| | 801| 16.0k| case P_BOL: ------------------ | Branch (801:9): [True: 16.0k, False: 477k] ------------------ 802| 16.0k| emit(prog, I_BOL); 803| 16.0k| break; 804| 1.13k| case P_EOL: ------------------ | Branch (804:9): [True: 1.13k, False: 492k] ------------------ 805| 1.13k| emit(prog, I_EOL); 806| 1.13k| break; 807| 514| case P_WORD: ------------------ | Branch (807:9): [True: 514, False: 493k] ------------------ 808| 514| emit(prog, I_WORD); 809| 514| break; 810| 598| case P_NWORD: ------------------ | Branch (810:9): [True: 598, False: 493k] ------------------ 811| 598| emit(prog, I_NWORD); 812| 598| break; 813| | 814| 5.88k| case P_PAR: ------------------ | Branch (814:9): [True: 5.88k, False: 487k] ------------------ 815| 5.88k| inst = emit(prog, I_LPAR); 816| 5.88k| inst->n = node->n; 817| 5.88k| compile(prog, node->x); 818| 5.88k| inst = emit(prog, I_RPAR); 819| 5.88k| inst->n = node->n; 820| 5.88k| break; 821| 825| case P_PLA: ------------------ | Branch (821:9): [True: 825, False: 492k] ------------------ 822| 825| split = emit(prog, I_PLA); 823| 825| compile(prog, node->x); 824| 825| emit(prog, I_END); 825| 825| split->x = split + 1; 826| 825| split->y = prog->end; 827| 825| break; 828| 754| case P_NLA: ------------------ | Branch (828:9): [True: 754, False: 492k] ------------------ 829| 754| split = emit(prog, I_NLA); 830| 754| compile(prog, node->x); 831| 754| emit(prog, I_END); 832| 754| split->x = split + 1; 833| 754| split->y = prog->end; 834| 754| break; 835| | 836| 4.79k| case P_ANY: ------------------ | Branch (836:9): [True: 4.79k, False: 488k] ------------------ 837| 4.79k| emit(prog, I_ANY); 838| 4.79k| break; 839| 277k| case P_CHAR: ------------------ | Branch (839:9): [True: 277k, False: 216k] ------------------ 840| 277k| inst = emit(prog, I_CHAR); 841| 277k| inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; ------------------ | Branch (841:27): [True: 0, False: 277k] ------------------ 842| 277k| break; 843| 672| case P_CCLASS: ------------------ | Branch (843:9): [True: 672, False: 493k] ------------------ 844| 672| inst = emit(prog, I_CCLASS); 845| 672| inst->cc = node->cc; 846| 672| break; 847| 529| case P_NCCLASS: ------------------ | Branch (847:9): [True: 529, False: 493k] ------------------ 848| 529| inst = emit(prog, I_NCCLASS); 849| 529| inst->cc = node->cc; 850| 529| break; 851| 795| case P_REF: ------------------ | Branch (851:9): [True: 795, False: 492k] ------------------ 852| 795| inst = emit(prog, I_REF); 853| 795| inst->n = node->n; 854| 795| break; 855| 493k| } 856| 493k|} LLVMFuzzerTestOneInput: 44| 2.08k|int LLVMFuzzerTestOneInput(uint8_t *data, size_t size) { 45| | /* wrap random data in a null-terminated string */ 46| 2.08k| char *null_terminated = malloc(size + 1); 47| 2.08k| memcpy(null_terminated, data, size); 48| 2.08k| null_terminated[size] = '\0'; 49| | 50| 2.08k| const char *error; 51| 2.08k| Reprog *p = re_regcomp(null_terminated, 0, &error); 52| 2.08k| if (p != NULL) { ------------------ | Branch (52:13): [True: 955, False: 1.13k] ------------------ 53| 955| re_regfree(p); 54| 955| } 55| | 56| | /* cleanup */ 57| 2.08k| free(null_terminated); 58| | 59| 2.08k| return 0; 60| 2.08k|}