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.10k|static RD_INLINE RD_UNUSED void rd_free(void *ptr) { 158| 5.10k| free(ptr); 159| 5.10k|} 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: 952] ------------------ 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| 952| g->source = pattern; 1034| 952| g->ncclass = 0; 1035| 952| 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: 952] ------------------ 1037| 33.2k| g->sub[i] = 0; 1038| | 1039| 952| g->prog->flags = cflags; 1040| | 1041| 952| next(g); 1042| 952| node = parsealt(g); 1043| 952| if (g->lookahead == ')') ------------------ | Branch (1043:13): [True: 19, False: 933] ------------------ 1044| 19| die(g, "unmatched ')'"); 1045| 952| if (g->lookahead != 0) ------------------ | Branch (1045:13): [True: 0, False: 952] ------------------ 1046| 0| die(g, "syntax error"); 1047| | 1048| 952| g->prog->nsub = g->nsub; 1049| 952| ncount = count(node); 1050| 952| if (ncount > 10000) ------------------ | Branch (1050:13): [True: 42, False: 910] ------------------ 1051| 42| die(g, "regexp graph too large"); 1052| 952| g->prog->start = g->prog->end = 1053| 952| rd_malloc((ncount + 6) * sizeof(Reinst)); 1054| | 1055| 952| split = emit(g->prog, I_SPLIT); 1056| 952| split->x = split + 3; 1057| 952| split->y = split + 1; 1058| 952| emit(g->prog, I_ANYNL); 1059| 952| jump = emit(g->prog, I_JUMP); 1060| 952| jump->x = split; 1061| 952| emit(g->prog, I_LPAR); 1062| 952| compile(g->prog, node); 1063| 952| emit(g->prog, I_RPAR); 1064| 952| emit(g->prog, I_END); 1065| | 1066| |#ifdef TEST 1067| | dumpnode(node); 1068| | putchar('\n'); 1069| | dumpprog(g->prog); 1070| |#endif 1071| | 1072| 952| rd_free(g->pstart); 1073| | 1074| 952| if (errorp) ------------------ | Branch (1074:13): [True: 952, False: 0] ------------------ 1075| 952| *errorp = NULL; 1076| 952| return g->prog; 1077| 2.07k|} re_regfree: 1079| 952|void re_regfree(Reprog *prog) { 1080| 952| if (prog) { ------------------ | Branch (1080:13): [True: 952, False: 0] ------------------ 1081| 952| rd_free(prog->start); 1082| 952| rd_free(prog); 1083| 952| } 1084| 952|} regexp.c:next: 529| 253k|static void next(Restate *g) { 530| 253k| g->lookahead = lex(g); 531| 253k|} regexp.c:lex: 370| 253k|static int lex(Restate *g) { 371| 253k| int quoted = nextrune(g); 372| 253k| if (quoted) { ------------------ | Branch (372:13): [True: 3.72k, False: 250k] ------------------ 373| 3.72k| switch (g->yychar) { ------------------ | Branch (373:25): [True: 2.32k, False: 1.39k] ------------------ 374| 208| case 'b': ------------------ | Branch (374:17): [True: 208, False: 3.51k] ------------------ 375| 208| return L_WORD; 376| 332| case 'B': ------------------ | Branch (376:17): [True: 332, False: 3.39k] ------------------ 377| 332| return L_NWORD; 378| 75| case 'd': ------------------ | Branch (378:17): [True: 75, False: 3.64k] ------------------ 379| 75| newcclass(g); 380| 75| addranges_d(g); 381| 75| return L_CCLASS; 382| 121| case 's': ------------------ | Branch (382:17): [True: 121, False: 3.60k] ------------------ 383| 121| newcclass(g); 384| 121| addranges_s(g); 385| 121| return L_CCLASS; 386| 105| case 'w': ------------------ | Branch (386:17): [True: 105, False: 3.61k] ------------------ 387| 105| newcclass(g); 388| 105| addranges_w(g); 389| 105| return L_CCLASS; 390| 104| case 'D': ------------------ | Branch (390:17): [True: 104, False: 3.61k] ------------------ 391| 104| newcclass(g); 392| 104| addranges_d(g); 393| 104| return L_NCCLASS; 394| 143| case 'S': ------------------ | Branch (394:17): [True: 143, False: 3.58k] ------------------ 395| 143| newcclass(g); 396| 143| addranges_s(g); 397| 143| return L_NCCLASS; 398| 86| case 'W': ------------------ | Branch (398:17): [True: 86, False: 3.63k] ------------------ 399| 86| newcclass(g); 400| 86| addranges_w(g); 401| 86| return L_NCCLASS; 402| 1.15k| case '0': ------------------ | Branch (402:17): [True: 1.15k, False: 2.57k] ------------------ 403| 1.15k| g->yychar = 0; 404| 1.15k| return L_CHAR; 405| 3.72k| } 406| 1.39k| if (g->yychar >= '0' && g->yychar <= '9') { ------------------ | Branch (406:21): [True: 1.19k, False: 202] | Branch (406:41): [True: 970, False: 226] ------------------ 407| 970| g->yychar -= '0'; 408| 970| if (*g->source >= '0' && *g->source <= '9') ------------------ | Branch (408:29): [True: 655, False: 315] | Branch (408:50): [True: 201, False: 454] ------------------ 409| 201| g->yychar = g->yychar * 10 + *g->source++ - '0'; 410| 970| return L_REF; 411| 970| } 412| 428| return L_CHAR; 413| 1.39k| } 414| | 415| 250k| switch (g->yychar) { ------------------ | Branch (415:17): [True: 52.8k, False: 197k] ------------------ 416| 1.13k| case 0: ------------------ | Branch (416:9): [True: 1.13k, False: 248k] ------------------ 417| 17.6k| case '$': ------------------ | Branch (417:9): [True: 16.4k, False: 233k] ------------------ 418| 19.8k| case ')': ------------------ | Branch (418:9): [True: 2.21k, False: 247k] ------------------ 419| 24.0k| case '*': ------------------ | Branch (419:9): [True: 4.23k, False: 245k] ------------------ 420| 24.9k| case '+': ------------------ | Branch (420:9): [True: 868, False: 249k] ------------------ 421| 26.9k| case '.': ------------------ | Branch (421:9): [True: 2.04k, False: 248k] ------------------ 422| 30.5k| case '?': ------------------ | Branch (422:9): [True: 3.60k, False: 246k] ------------------ 423| 37.6k| case '^': ------------------ | Branch (423:9): [True: 7.05k, False: 243k] ------------------ 424| 52.8k| case '|': ------------------ | Branch (424:9): [True: 15.2k, False: 234k] ------------------ 425| 52.8k| return g->yychar; 426| 250k| } 427| | 428| 196k| if (g->yychar == '{') ------------------ | Branch (428:13): [True: 1.92k, False: 195k] ------------------ 429| 1.92k| return lexcount(g); 430| 195k| if (g->yychar == '[') ------------------ | Branch (430:13): [True: 786, False: 194k] ------------------ 431| 786| return lexclass(g); 432| 194k| if (g->yychar == '(') { ------------------ | Branch (432:13): [True: 3.69k, False: 190k] ------------------ 433| 3.69k| if (g->source[0] == '?') { ------------------ | Branch (433:21): [True: 2.48k, False: 1.20k] ------------------ 434| 2.48k| if (g->source[1] == ':') { ------------------ | Branch (434:29): [True: 687, False: 1.80k] ------------------ 435| 687| g->source += 2; 436| 687| return L_NC; 437| 687| } 438| 1.80k| if (g->source[1] == '=') { ------------------ | Branch (438:29): [True: 790, False: 1.01k] ------------------ 439| 790| g->source += 2; 440| 790| return L_PLA; 441| 790| } 442| 1.01k| if (g->source[1] == '!') { ------------------ | Branch (442:29): [True: 992, False: 19] ------------------ 443| 992| g->source += 2; 444| 992| return L_NLA; 445| 992| } 446| 1.01k| } 447| 1.22k| return '('; 448| 3.69k| } 449| | 450| 190k| return L_CHAR; 451| 194k|} regexp.c:nextrune: 131| 261k|static int nextrune(Restate *g) { 132| 261k| g->source += chartorune(&g->yychar, g->source); 133| 261k| if (g->yychar == '\\') { ------------------ | Branch (133:13): [True: 11.0k, False: 250k] ------------------ 134| 11.0k| g->source += chartorune(&g->yychar, g->source); 135| 11.0k| switch (g->yychar) { ------------------ | Branch (135:25): [True: 5.43k, False: 5.59k] ------------------ 136| 4| case 0: ------------------ | Branch (136:17): [True: 4, False: 11.0k] ------------------ 137| 4| die(g, "unterminated escape sequence"); 138| 1.01k| case 'f': ------------------ | Branch (138:17): [True: 1.01k, False: 10.0k] ------------------ 139| 1.01k| g->yychar = '\f'; 140| 1.01k| return 0; 141| 306| case 'n': ------------------ | Branch (141:17): [True: 306, False: 10.7k] ------------------ 142| 306| g->yychar = '\n'; 143| 306| return 0; 144| 195| case 'r': ------------------ | Branch (144:17): [True: 195, False: 10.8k] ------------------ 145| 195| g->yychar = '\r'; 146| 195| return 0; 147| 194| case 't': ------------------ | Branch (147:17): [True: 194, False: 10.8k] ------------------ 148| 194| g->yychar = '\t'; 149| 194| return 0; 150| 194| case 'v': ------------------ | Branch (150:17): [True: 194, False: 10.8k] ------------------ 151| 194| g->yychar = '\v'; 152| 194| return 0; 153| 331| case 'c': ------------------ | Branch (153:17): [True: 331, False: 10.7k] ------------------ 154| 331| g->yychar = (*g->source++) & 31; 155| 331| return 0; 156| 1.56k| case 'x': ------------------ | Branch (156:17): [True: 1.56k, False: 9.46k] ------------------ 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: 488, False: 1.07k] ------------------ 160| 488| g->yychar = '0'; 161| 488| return 1; 162| 488| } 163| 1.07k| return 0; 164| 1.63k| case 'u': ------------------ | Branch (164:17): [True: 1.63k, False: 9.39k] ------------------ 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: 461, False: 1.17k] ------------------ 170| 461| g->yychar = '0'; 171| 461| return 1; 172| 461| } 173| 1.17k| return 0; 174| 11.0k| } 175| 5.59k| if (strchr(ESCAPES, g->yychar)) ------------------ | | 129| 5.59k|#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" ------------------ | Branch (175:21): [True: 5.08k, False: 514] ------------------ 176| 5.08k| return 1; 177| 514| if (isalpharune(g->yychar) || ------------------ | Branch (177:21): [True: 10, False: 504] ------------------ 178| 504| g->yychar == '_') /* check identity escape */ ------------------ | Branch (178:21): [True: 1, False: 503] ------------------ 179| 11| die(g, "invalid escape character"); 180| 514| return 0; 181| 5.59k| } 182| 250k| return 0; 183| 261k|} regexp.c:chartorune: 37| 272k|static int chartorune(Rune *r, const char *s) { 38| | /* TODO: Add UTF-8 decoding */ 39| 272k| *r = *s; 40| 272k| return 1; 41| 272k|} regexp.c:hex: 111| 9.36k|static int hex(Restate *g, int c) { 112| 9.36k| if (c >= '0' && c <= '9') ------------------ | Branch (112:13): [True: 9.19k, False: 173] | Branch (112:25): [True: 3.66k, False: 5.52k] ------------------ 113| 3.66k| return c - '0'; 114| 5.70k| if (c >= 'a' && c <= 'f') ------------------ | Branch (114:13): [True: 2.26k, False: 3.43k] | Branch (114:25): [True: 2.23k, False: 31] ------------------ 115| 2.23k| return c - 'a' + 0xA; 116| 3.46k| if (c >= 'A' && c <= 'F') ------------------ | Branch (116:13): [True: 3.27k, False: 197] | Branch (116:25): [True: 3.20k, False: 67] ------------------ 117| 3.20k| return c - 'A' + 0xA; 118| 264| die(g, "invalid escape sequence"); 119| 264| return 0; 120| 3.46k|} regexp.c:isalpharune: 25| 514|static int isalpharune(Rune c) { 26| | /* TODO: Add unicode support */ 27| 514| return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); ------------------ | Branch (27:17): [True: 261, False: 253] | Branch (27:29): [True: 6, False: 255] | Branch (27:43): [True: 253, False: 255] | Branch (27:55): [True: 4, False: 249] ------------------ 28| 514|} regexp.c:newcclass: 218| 1.42k|static void newcclass(Restate *g) { 219| 1.42k| if (g->ncclass >= nelem(g->prog->cclass)) ------------------ | | 21| 1.42k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (219:13): [True: 7, False: 1.41k] ------------------ 220| 7| die(g, "too many character classes"); 221| 1.42k| g->yycc = g->prog->cclass + g->ncclass++; 222| 1.42k| g->yycc->end = g->yycc->spans; 223| 1.42k|} regexp.c:addranges_d: 234| 914|static void addranges_d(Restate *g) { 235| 914| addrange(g, '0', '9'); 236| 914|} regexp.c:addrange: 225| 9.59k|static void addrange(Restate *g, Rune a, Rune b) { 226| 9.59k| if (a > b) ------------------ | Branch (226:13): [True: 46, False: 9.55k] ------------------ 227| 46| die(g, "invalid character class range"); 228| 9.59k| if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) ------------------ | | 21| 9.59k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (228:13): [True: 42, False: 9.55k] ------------------ 229| 42| die(g, "too many character class ranges"); 230| 9.59k| *g->yycc->end++ = a; 231| 9.59k| *g->yycc->end++ = b; 232| 9.59k|} regexp.c:addranges_s: 243| 503|static void addranges_s(Restate *g) { 244| 503| addrange(g, 0x9, 0x9); 245| 503| addrange(g, 0xA, 0xD); 246| 503| addrange(g, 0x20, 0x20); 247| 503| addrange(g, 0xA0, 0xA0); 248| 503| addrange(g, 0x2028, 0x2029); 249| 503| addrange(g, 0xFEFF, 0xFEFF); 250| 503|} regexp.c:addranges_w: 262| 302|static void addranges_w(Restate *g) { 263| 302| addrange(g, '0', '9'); 264| 302| addrange(g, 'A', 'Z'); 265| 302| addrange(g, '_', '_'); 266| 302| addrange(g, 'a', 'z'); 267| 302|} regexp.c:lexcount: 185| 1.92k|static int lexcount(Restate *g) { 186| 1.92k| g->yychar = *g->source++; 187| | 188| 1.92k| g->yymin = dec(g, g->yychar); 189| 1.92k| g->yychar = *g->source++; 190| 3.71k| while (g->yychar != ',' && g->yychar != '}') { ------------------ | Branch (190:16): [True: 2.82k, False: 894] | Branch (190:36): [True: 1.79k, False: 1.02k] ------------------ 191| 1.79k| g->yymin = g->yymin * 10 + dec(g, g->yychar); 192| 1.79k| g->yychar = *g->source++; 193| 1.79k| } 194| 1.92k| if (g->yymin >= REPINF) ------------------ | | 43| 1.92k|#define REPINF 255 ------------------ | Branch (194:13): [True: 22, False: 1.89k] ------------------ 195| 22| die(g, "numeric overflow"); 196| | 197| 1.92k| if (g->yychar == ',') { ------------------ | Branch (197:13): [True: 837, False: 1.08k] ------------------ 198| 837| g->yychar = *g->source++; 199| 837| if (g->yychar == '}') { ------------------ | Branch (199:21): [True: 268, False: 569] ------------------ 200| 268| g->yymax = REPINF; ------------------ | | 43| 268|#define REPINF 255 ------------------ 201| 569| } else { 202| 569| g->yymax = dec(g, g->yychar); 203| 569| g->yychar = *g->source++; 204| 1.54k| while (g->yychar != '}') { ------------------ | Branch (204:32): [True: 973, False: 569] ------------------ 205| 973| g->yymax = g->yymax * 10 + dec(g, g->yychar); 206| 973| g->yychar = *g->source++; 207| 973| } 208| 569| if (g->yymax >= REPINF) ------------------ | | 43| 569|#define REPINF 255 ------------------ | Branch (208:29): [True: 18, False: 551] ------------------ 209| 18| die(g, "numeric overflow"); 210| 569| } 211| 1.08k| } else { 212| 1.08k| g->yymax = g->yymin; 213| 1.08k| } 214| | 215| 1.92k| return L_COUNT; 216| 1.92k|} regexp.c:dec: 122| 5.25k|static int dec(Restate *g, int c) { 123| 5.25k| if (c >= '0' && c <= '9') ------------------ | Branch (123:13): [True: 5.17k, False: 87] | Branch (123:25): [True: 5.14k, False: 30] ------------------ 124| 5.14k| return c - '0'; 125| 117| die(g, "invalid quantifier"); 126| 117| return 0; 127| 5.25k|} regexp.c:lexclass: 277| 786|static int lexclass(Restate *g) { 278| 786| int type = L_CCLASS; 279| 786| int quoted, havesave, havedash; 280| 786| Rune save = 0; 281| | 282| 786| newcclass(g); 283| | 284| 786| quoted = nextrune(g); 285| 786| if (!quoted && g->yychar == '^') { ------------------ | Branch (285:13): [True: 572, False: 214] | Branch (285:24): [True: 35, False: 537] ------------------ 286| 35| type = L_NCCLASS; 287| 35| quoted = nextrune(g); 288| 35| } 289| | 290| 786| havesave = havedash = 0; 291| 7.56k| for (;;) { 292| 7.56k| if (g->yychar == 0) ------------------ | Branch (292:21): [True: 230, False: 7.33k] ------------------ 293| 230| die(g, "unterminated character class"); 294| 7.56k| if (!quoted && g->yychar == ']') ------------------ | Branch (294:21): [True: 5.02k, False: 2.53k] | Branch (294:32): [True: 469, False: 4.55k] ------------------ 295| 469| break; 296| | 297| 7.09k| if (!quoted && g->yychar == '-') { ------------------ | Branch (297:21): [True: 4.55k, False: 2.53k] | Branch (297:32): [True: 2.17k, False: 2.38k] ------------------ 298| 2.17k| if (havesave) { ------------------ | Branch (298:29): [True: 1.58k, False: 590] ------------------ 299| 1.58k| if (havedash) { ------------------ | Branch (299:37): [True: 436, False: 1.14k] ------------------ 300| 436| addrange(g, save, '-'); 301| 436| havesave = havedash = 0; 302| 1.14k| } else { 303| 1.14k| havedash = 1; 304| 1.14k| } 305| 1.58k| } else { 306| 590| save = '-'; 307| 590| havesave = 1; 308| 590| } 309| 4.92k| } else if (quoted && strchr("DSWdsw", g->yychar)) { ------------------ | Branch (309:28): [True: 2.30k, False: 2.61k] | Branch (309:38): [True: 1.50k, False: 808] ------------------ 310| 1.50k| if (havesave) { ------------------ | Branch (310:29): [True: 548, False: 953] ------------------ 311| 548| addrange(g, save, save); 312| 548| if (havedash) ------------------ | Branch (312:37): [True: 195, False: 353] ------------------ 313| 195| addrange(g, '-', '-'); 314| 548| } 315| 1.50k| switch (g->yychar) { ------------------ | Branch (315:33): [True: 1.49k, False: 2] ------------------ 316| 737| case 'd': ------------------ | Branch (316:25): [True: 737, False: 764] ------------------ 317| 737| addranges_d(g); 318| 737| break; 319| 241| case 's': ------------------ | Branch (319:25): [True: 241, False: 1.26k] ------------------ 320| 241| addranges_s(g); 321| 241| break; 322| 113| case 'w': ------------------ | Branch (322:25): [True: 113, False: 1.38k] ------------------ 323| 113| addranges_w(g); 324| 113| break; 325| 323| case 'D': ------------------ | Branch (325:25): [True: 323, False: 1.17k] ------------------ 326| 323| addranges_D(g); 327| 323| break; 328| 4| case 'S': ------------------ | Branch (328:25): [True: 4, False: 1.49k] ------------------ 329| 4| addranges_S(g); 330| 4| break; 331| 81| case 'W': ------------------ | Branch (331:25): [True: 81, False: 1.42k] ------------------ 332| 81| addranges_W(g); 333| 81| break; 334| 1.50k| } 335| 1.46k| havesave = havedash = 0; 336| 3.42k| } else { 337| 3.42k| if (quoted) { ------------------ | Branch (337:29): [True: 808, False: 2.61k] ------------------ 338| 808| if (g->yychar == 'b') ------------------ | Branch (338:37): [True: 195, False: 613] ------------------ 339| 195| g->yychar = '\b'; 340| 613| else if (g->yychar == '0') ------------------ | Branch (340:42): [True: 290, False: 323] ------------------ 341| 290| g->yychar = 0; 342| | /* else identity escape */ 343| 808| } 344| 3.42k| if (havesave) { ------------------ | Branch (344:29): [True: 2.04k, False: 1.38k] ------------------ 345| 2.04k| if (havedash) { ------------------ | Branch (345:37): [True: 456, False: 1.58k] ------------------ 346| 456| addrange(g, save, g->yychar); 347| 456| havesave = havedash = 0; 348| 1.58k| } else { 349| 1.58k| addrange(g, save, save); 350| 1.58k| save = g->yychar; 351| 1.58k| } 352| 2.04k| } else { 353| 1.38k| save = g->yychar; 354| 1.38k| havesave = 1; 355| 1.38k| } 356| 3.42k| } 357| | 358| 7.06k| quoted = nextrune(g); 359| 7.06k| } 360| | 361| 749| if (havesave) { ------------------ | Branch (361:13): [True: 179, False: 570] ------------------ 362| 179| addrange(g, save, save); 363| 179| if (havedash) ------------------ | Branch (363:21): [True: 52, False: 127] ------------------ 364| 52| addrange(g, '-', '-'); 365| 179| } 366| | 367| 749| return type; 368| 786|} regexp.c:addranges_D: 238| 323|static void addranges_D(Restate *g) { 239| 323| addrange(g, 0, '0' - 1); 240| 323| addrange(g, '9' + 1, 0xFFFF); 241| 323|} regexp.c:addranges_S: 252| 4|static void addranges_S(Restate *g) { 253| 4| addrange(g, 0, 0x9 - 1); 254| 4| addrange(g, 0x9 + 1, 0xA - 1); 255| 4| addrange(g, 0xD + 1, 0x20 - 1); 256| 4| addrange(g, 0x20 + 1, 0xA0 - 1); 257| 4| addrange(g, 0xA0 + 1, 0x2028 - 1); 258| 4| addrange(g, 0x2029 + 1, 0xFEFF - 1); 259| 4| addrange(g, 0xFEFF + 1, 0xFFFF); 260| 4|} regexp.c:addranges_W: 269| 81|static void addranges_W(Restate *g) { 270| 81| addrange(g, 0, '0' - 1); 271| 81| addrange(g, '9' + 1, 'A' - 1); 272| 81| addrange(g, 'Z' + 1, '_' - 1); 273| 81| addrange(g, '_' + 1, 'a' - 1); 274| 81| addrange(g, 'z' + 1, 0xFFFF); 275| 81|} regexp.c:parsealt: 654| 5.16k|static Renode *parsealt(Restate *g) { 655| 5.16k| Renode *alt, *x; 656| 5.16k| alt = parsecat(g); 657| 20.3k| while (re_accept(g, '|')) { ------------------ | Branch (657:16): [True: 15.2k, False: 5.16k] ------------------ 658| 15.2k| x = alt; 659| 15.2k| alt = newnode(g, P_ALT); 660| 15.2k| alt->x = x; 661| 15.2k| alt->y = parsecat(g); 662| 15.2k| } 663| 5.16k| return alt; 664| 5.16k|} regexp.c:parsecat: 638| 20.3k|static Renode *parsecat(Restate *g) { 639| 20.3k| Renode *cat, *x; 640| 20.3k| if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { ------------------ | Branch (640:13): [True: 20.2k, False: 105] | Branch (640:29): [True: 5.90k, False: 14.3k] | Branch (640:52): [True: 4.54k, False: 1.36k] ------------------ 641| 4.54k| cat = parserep(g); 642| 224k| while (g->lookahead && g->lookahead != '|' && ------------------ | Branch (642:24): [True: 221k, False: 2.85k] | Branch (642:40): [True: 220k, False: 845] ------------------ 643| 220k| g->lookahead != ')') { ------------------ | Branch (643:24): [True: 219k, False: 844] ------------------ 644| 219k| x = cat; 645| 219k| cat = newnode(g, P_CAT); 646| 219k| cat->x = x; 647| 219k| cat->y = parserep(g); 648| 219k| } 649| 4.54k| return cat; 650| 4.54k| } 651| 15.8k| return NULL; 652| 20.3k|} regexp.c:parserep: 609| 224k|static Renode *parserep(Restate *g) { 610| 224k| Renode *atom; 611| | 612| 224k| if (re_accept(g, '^')) ------------------ | Branch (612:13): [True: 7.05k, False: 217k] ------------------ 613| 7.05k| return newnode(g, P_BOL); 614| 217k| if (re_accept(g, '$')) ------------------ | Branch (614:13): [True: 16.4k, False: 200k] ------------------ 615| 16.4k| return newnode(g, P_EOL); 616| 200k| if (re_accept(g, L_WORD)) ------------------ | Branch (616:13): [True: 208, False: 200k] ------------------ 617| 208| return newnode(g, P_WORD); 618| 200k| if (re_accept(g, L_NWORD)) ------------------ | Branch (618:13): [True: 332, False: 200k] ------------------ 619| 332| return newnode(g, P_NWORD); 620| | 621| 200k| atom = parseatom(g); 622| 200k| if (g->lookahead == L_COUNT) { ------------------ | Branch (622:13): [True: 1.69k, False: 198k] ------------------ 623| 1.69k| int min = g->yymin, max = g->yymax; 624| 1.69k| next(g); 625| 1.69k| if (max < min) ------------------ | Branch (625:21): [True: 14, False: 1.67k] ------------------ 626| 14| die(g, "invalid quantifier"); 627| 1.69k| return newrep(g, atom, re_accept(g, '?'), min, max); 628| 1.69k| } 629| 198k| if (re_accept(g, '*')) ------------------ | Branch (629:13): [True: 4.22k, False: 194k] ------------------ 630| 4.22k| return newrep(g, atom, re_accept(g, '?'), 0, REPINF); ------------------ | | 43| 4.22k|#define REPINF 255 ------------------ 631| 194k| if (re_accept(g, '+')) ------------------ | Branch (631:13): [True: 857, False: 193k] ------------------ 632| 857| return newrep(g, atom, re_accept(g, '?'), 1, REPINF); ------------------ | | 43| 857|#define REPINF 255 ------------------ 633| 193k| if (re_accept(g, '?')) ------------------ | Branch (633:13): [True: 742, False: 192k] ------------------ 634| 742| return newrep(g, atom, re_accept(g, '?'), 0, 1); 635| 192k| return atom; 636| 193k|} regexp.c:parseatom: 543| 200k|static Renode *parseatom(Restate *g) { 544| 200k| Renode *atom; 545| 200k| if (g->lookahead == L_CHAR) { ------------------ | Branch (545:13): [True: 192k, False: 7.91k] ------------------ 546| 192k| atom = newnode(g, P_CHAR); 547| 192k| atom->c = g->yychar; 548| 192k| next(g); 549| 192k| return atom; 550| 192k| } 551| 7.91k| if (g->lookahead == L_CCLASS) { ------------------ | Branch (551:13): [True: 735, False: 7.18k] ------------------ 552| 735| atom = newnode(g, P_CCLASS); 553| 735| atom->cc = g->yycc; 554| 735| next(g); 555| 735| return atom; 556| 735| } 557| 7.18k| if (g->lookahead == L_NCCLASS) { ------------------ | Branch (557:13): [True: 359, False: 6.82k] ------------------ 558| 359| atom = newnode(g, P_NCCLASS); 559| 359| atom->cc = g->yycc; 560| 359| next(g); 561| 359| return atom; 562| 359| } 563| 6.82k| if (g->lookahead == L_REF) { ------------------ | Branch (563:13): [True: 969, False: 5.85k] ------------------ 564| 969| atom = newnode(g, P_REF); 565| 969| if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) ------------------ | Branch (565:21): [True: 0, False: 969] | Branch (565:39): [True: 20, False: 949] | Branch (565:62): [True: 13, False: 936] ------------------ 566| 33| die(g, "invalid back-reference"); 567| 969| atom->n = g->yychar; 568| 969| atom->x = g->sub[g->yychar]; 569| 969| next(g); 570| 969| return atom; 571| 969| } 572| 5.85k| if (re_accept(g, '.')) ------------------ | Branch (572:13): [True: 2.04k, False: 3.81k] ------------------ 573| 2.04k| return newnode(g, P_ANY); 574| 3.81k| if (re_accept(g, '(')) { ------------------ | Branch (574:13): [True: 1.22k, False: 2.59k] ------------------ 575| 1.22k| atom = newnode(g, P_PAR); 576| 1.22k| if (g->nsub == MAXSUB) ------------------ | | 45| 1.22k|#define MAXSUB REG_MAXSUB ------------------ | Branch (576:21): [True: 6, False: 1.21k] ------------------ 577| 6| die(g, "too many captures"); 578| 1.22k| atom->n = g->nsub++; 579| 1.22k| atom->x = parsealt(g); 580| 1.22k| g->sub[atom->n] = atom; 581| 1.22k| if (!re_accept(g, ')')) ------------------ | Branch (581:21): [True: 58, False: 1.16k] ------------------ 582| 58| die(g, "unmatched '('"); 583| 1.22k| return atom; 584| 1.22k| } 585| 2.59k| if (re_accept(g, L_NC)) { ------------------ | Branch (585:13): [True: 687, False: 1.90k] ------------------ 586| 687| atom = parsealt(g); 587| 687| if (!re_accept(g, ')')) ------------------ | Branch (587:21): [True: 12, False: 675] ------------------ 588| 12| die(g, "unmatched '('"); 589| 687| return atom; 590| 687| } 591| 1.90k| if (re_accept(g, L_PLA)) { ------------------ | Branch (591:13): [True: 790, False: 1.11k] ------------------ 592| 790| atom = newnode(g, P_PLA); 593| 790| atom->x = parsealt(g); 594| 790| if (!re_accept(g, ')')) ------------------ | Branch (594:21): [True: 10, False: 780] ------------------ 595| 10| die(g, "unmatched '('"); 596| 790| return atom; 597| 790| } 598| 1.11k| if (re_accept(g, L_NLA)) { ------------------ | Branch (598:13): [True: 992, False: 125] ------------------ 599| 992| atom = newnode(g, P_NLA); 600| 992| atom->x = parsealt(g); 601| 992| if (!re_accept(g, ')')) ------------------ | Branch (601:21): [True: 9, False: 983] ------------------ 602| 9| die(g, "unmatched '('"); 603| 992| return atom; 604| 992| } 605| 125| die(g, "syntax error"); 606| | return NULL; 607| 1.11k|} regexp.c:newrep: 518| 7.49k|static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { 519| 7.49k| Renode *rep = newnode(g, P_REP); 520| 7.49k| if (max == REPINF && empty(atom)) ------------------ | | 43| 14.9k|#define REPINF 255 ------------------ | Branch (520:13): [True: 5.33k, False: 2.15k] | Branch (520:30): [True: 41, False: 5.29k] ------------------ 521| 41| die(g, "infinite loop matching the empty string"); 522| 7.49k| rep->ng = ng; 523| 7.49k| rep->m = min; 524| 7.49k| rep->n = max; 525| 7.49k| rep->x = atom; 526| 7.49k| return rep; 527| 7.49k|} regexp.c:empty: 494| 13.4k|static int empty(Renode *node) { 495| 13.4k| if (!node) ------------------ | Branch (495:13): [True: 838, False: 12.5k] ------------------ 496| 838| return 1; 497| 12.5k| switch (node->type) { 498| 224| default: ------------------ | Branch (498:9): [True: 224, False: 12.3k] ------------------ 499| 224| return 1; 500| 1.99k| case P_CAT: ------------------ | Branch (500:9): [True: 1.99k, False: 10.5k] ------------------ 501| 1.99k| return empty(node->x) && empty(node->y); ------------------ | Branch (501:24): [True: 1.68k, False: 307] | Branch (501:42): [True: 1.40k, False: 282] ------------------ 502| 679| case P_ALT: ------------------ | Branch (502:9): [True: 679, False: 11.8k] ------------------ 503| 679| return empty(node->x) || empty(node->y); ------------------ | Branch (503:24): [True: 457, False: 222] | Branch (503:42): [True: 111, False: 111] ------------------ 504| 943| case P_REP: ------------------ | Branch (504:9): [True: 943, False: 11.6k] ------------------ 505| 943| return empty(node->x) || node->m == 0; ------------------ | Branch (505:24): [True: 194, False: 749] | Branch (505:42): [True: 668, False: 81] ------------------ 506| 1.75k| case P_PAR: ------------------ | Branch (506:9): [True: 1.75k, False: 10.8k] ------------------ 507| 1.75k| return empty(node->x); 508| 798| case P_REF: ------------------ | Branch (508:9): [True: 798, False: 11.7k] ------------------ 509| 798| return empty(node->x); 510| 641| case P_ANY: ------------------ | Branch (510:9): [True: 641, False: 11.9k] ------------------ 511| 5.78k| case P_CHAR: ------------------ | Branch (511:9): [True: 5.14k, False: 7.43k] ------------------ 512| 5.98k| case P_CCLASS: ------------------ | Branch (512:9): [True: 204, False: 12.3k] ------------------ 513| 6.18k| case P_NCCLASS: ------------------ | Branch (513:9): [True: 200, False: 12.3k] ------------------ 514| 6.18k| return 0; 515| 12.5k| } 516| 12.5k|} regexp.c:re_accept: 533| 1.46M|static int re_accept(Restate *g, int t) { 534| 1.46M| if (g->lookahead == t) { ------------------ | Branch (534:13): [True: 55.8k, False: 1.41M] ------------------ 535| 55.8k| next(g); 536| 55.8k| return 1; 537| 55.8k| } 538| 1.41M| return 0; 539| 1.46M|} regexp.c:newnode: 482| 465k|static Renode *newnode(Restate *g, int type) { 483| 465k| Renode *node = g->pend++; 484| 465k| node->type = type; 485| 465k| node->cc = NULL; 486| 465k| node->c = 0; 487| 465k| node->ng = 0; 488| 465k| node->m = 0; 489| 465k| node->n = 0; 490| | node->x = node->y = NULL; 491| 465k| return node; 492| 465k|} 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| 409k|static unsigned int count(Renode *node) { 698| 409k| unsigned int min, max; 699| 409k| if (!node) ------------------ | Branch (699:13): [True: 15.0k, False: 393k] ------------------ 700| 15.0k| return 0; 701| 393k| switch (node->type) { 702| 185k| default: ------------------ | Branch (702:9): [True: 185k, False: 208k] ------------------ 703| 185k| return 1; 704| 185k| case P_CAT: ------------------ | Branch (704:9): [True: 185k, False: 208k] ------------------ 705| 185k| return count(node->x) + count(node->y); 706| 14.6k| case P_ALT: ------------------ | Branch (706:9): [True: 14.6k, False: 379k] ------------------ 707| 14.6k| return count(node->x) + count(node->y) + 2; 708| 6.75k| case P_REP: ------------------ | Branch (708:9): [True: 6.75k, False: 387k] ------------------ 709| 6.75k| min = node->m; 710| 6.75k| max = node->n; 711| 6.75k| if (min == max) ------------------ | Branch (711:21): [True: 946, False: 5.80k] ------------------ 712| 946| return count(node->x) * min; 713| 5.80k| if (max < REPINF) ------------------ | | 43| 5.80k|#define REPINF 255 ------------------ | Branch (713:21): [True: 951, False: 4.85k] ------------------ 714| 951| return count(node->x) * max + (max - min); 715| 4.85k| return count(node->x) * (min + 1) + 2; 716| 578| case P_PAR: ------------------ | Branch (716:9): [True: 578, False: 393k] ------------------ 717| 578| return count(node->x) + 2; 718| 469| case P_PLA: ------------------ | Branch (718:9): [True: 469, False: 393k] ------------------ 719| 469| return count(node->x) + 2; 720| 445| case P_NLA: ------------------ | Branch (720:9): [True: 445, False: 393k] ------------------ 721| 445| return count(node->x) + 2; 722| 393k| } 723| 393k|} regexp.c:emit: 725| 383k|static Reinst *emit(Reprog *prog, int opcode) { 726| 383k| Reinst *inst = prog->end++; 727| 383k| inst->opcode = opcode; 728| 383k| inst->n = 0; 729| 383k| inst->c = 0; 730| 383k| inst->cc = NULL; 731| | inst->x = inst->y = NULL; 732| 383k| return inst; 733| 383k|} regexp.c:compile: 735| 535k|static void compile(Reprog *prog, Renode *node) { 736| 535k| Reinst *inst, *split, *jump; 737| 535k| unsigned int i; 738| | 739| 535k| if (!node) ------------------ | Branch (739:13): [True: 17.4k, False: 517k] ------------------ 740| 17.4k| return; 741| | 742| 517k| switch (node->type) { ------------------ | Branch (742:17): [True: 517k, False: 0] ------------------ 743| 168k| case P_CAT: ------------------ | Branch (743:9): [True: 168k, False: 349k] ------------------ 744| 168k| compile(prog, node->x); 745| 168k| compile(prog, node->y); 746| 168k| break; 747| | 748| 15.5k| case P_ALT: ------------------ | Branch (748:9): [True: 15.5k, False: 502k] ------------------ 749| 15.5k| split = emit(prog, I_SPLIT); 750| 15.5k| compile(prog, node->x); 751| 15.5k| jump = emit(prog, I_JUMP); 752| 15.5k| compile(prog, node->y); 753| 15.5k| split->x = split + 1; 754| 15.5k| split->y = jump + 1; 755| 15.5k| jump->x = prog->end; 756| 15.5k| break; 757| | 758| 9.28k| case P_REP: ------------------ | Branch (758:9): [True: 9.28k, False: 508k] ------------------ 759| 159k| for (i = 0; i < node->m; ++i) { ------------------ | Branch (759:29): [True: 149k, False: 9.28k] ------------------ 760| 149k| inst = prog->end; 761| 149k| compile(prog, node->x); 762| 149k| } 763| 9.28k| if (node->m == node->n) ------------------ | Branch (763:21): [True: 2.50k, False: 6.78k] ------------------ 764| 2.50k| break; 765| 6.78k| if (node->n < REPINF) { ------------------ | | 43| 6.78k|#define REPINF 255 ------------------ | Branch (765:21): [True: 1.38k, False: 5.39k] ------------------ 766| 6.47k| for (i = node->m; i < node->n; ++i) { ------------------ | Branch (766:43): [True: 5.08k, False: 1.38k] ------------------ 767| 5.08k| split = emit(prog, I_SPLIT); 768| 5.08k| compile(prog, node->x); 769| 5.08k| if (node->ng) { ------------------ | Branch (769:37): [True: 562, False: 4.52k] ------------------ 770| 562| split->y = split + 1; 771| 562| split->x = prog->end; 772| 4.52k| } else { 773| 4.52k| split->x = split + 1; 774| 4.52k| split->y = prog->end; 775| 4.52k| } 776| 5.08k| } 777| 5.39k| } else if (node->m == 0) { ------------------ | Branch (777:28): [True: 3.50k, False: 1.89k] ------------------ 778| 3.50k| split = emit(prog, I_SPLIT); 779| 3.50k| compile(prog, node->x); 780| 3.50k| jump = emit(prog, I_JUMP); 781| 3.50k| if (node->ng) { ------------------ | Branch (781:29): [True: 1.60k, False: 1.89k] ------------------ 782| 1.60k| split->y = split + 1; 783| 1.60k| split->x = prog->end; 784| 1.89k| } else { 785| 1.89k| split->x = split + 1; 786| 1.89k| split->y = prog->end; 787| 1.89k| } 788| 3.50k| jump->x = split; 789| 3.50k| } else { 790| 1.89k| split = emit(prog, I_SPLIT); 791| 1.89k| if (node->ng) { ------------------ | Branch (791:29): [True: 724, False: 1.17k] ------------------ 792| 724| split->y = inst; 793| 724| split->x = prog->end; 794| 1.17k| } else { 795| 1.17k| split->x = inst; 796| 1.17k| split->y = prog->end; 797| 1.17k| } 798| 1.89k| } 799| 6.78k| break; 800| | 801| 7.25k| case P_BOL: ------------------ | Branch (801:9): [True: 7.25k, False: 510k] ------------------ 802| 7.25k| emit(prog, I_BOL); 803| 7.25k| break; 804| 9.68k| case P_EOL: ------------------ | Branch (804:9): [True: 9.68k, False: 507k] ------------------ 805| 9.68k| emit(prog, I_EOL); 806| 9.68k| break; 807| 569| case P_WORD: ------------------ | Branch (807:9): [True: 569, False: 517k] ------------------ 808| 569| emit(prog, I_WORD); 809| 569| break; 810| 424| case P_NWORD: ------------------ | Branch (810:9): [True: 424, False: 517k] ------------------ 811| 424| emit(prog, I_NWORD); 812| 424| break; 813| | 814| 6.45k| case P_PAR: ------------------ | Branch (814:9): [True: 6.45k, False: 511k] ------------------ 815| 6.45k| inst = emit(prog, I_LPAR); 816| 6.45k| inst->n = node->n; 817| 6.45k| compile(prog, node->x); 818| 6.45k| inst = emit(prog, I_RPAR); 819| 6.45k| inst->n = node->n; 820| 6.45k| break; 821| 828| case P_PLA: ------------------ | Branch (821:9): [True: 828, False: 516k] ------------------ 822| 828| split = emit(prog, I_PLA); 823| 828| compile(prog, node->x); 824| 828| emit(prog, I_END); 825| 828| split->x = split + 1; 826| 828| split->y = prog->end; 827| 828| break; 828| 824| case P_NLA: ------------------ | Branch (828:9): [True: 824, False: 516k] ------------------ 829| 824| split = emit(prog, I_NLA); 830| 824| compile(prog, node->x); 831| 824| emit(prog, I_END); 832| 824| split->x = split + 1; 833| 824| split->y = prog->end; 834| 824| break; 835| | 836| 4.22k| case P_ANY: ------------------ | Branch (836:9): [True: 4.22k, False: 513k] ------------------ 837| 4.22k| emit(prog, I_ANY); 838| 4.22k| break; 839| 292k| case P_CHAR: ------------------ | Branch (839:9): [True: 292k, False: 225k] ------------------ 840| 292k| inst = emit(prog, I_CHAR); 841| 292k| inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; ------------------ | Branch (841:27): [True: 0, False: 292k] ------------------ 842| 292k| break; 843| 543| case P_CCLASS: ------------------ | Branch (843:9): [True: 543, False: 517k] ------------------ 844| 543| inst = emit(prog, I_CCLASS); 845| 543| inst->cc = node->cc; 846| 543| break; 847| 499| case P_NCCLASS: ------------------ | Branch (847:9): [True: 499, False: 517k] ------------------ 848| 499| inst = emit(prog, I_NCCLASS); 849| 499| inst->cc = node->cc; 850| 499| break; 851| 773| case P_REF: ------------------ | Branch (851:9): [True: 773, False: 516k] ------------------ 852| 773| inst = emit(prog, I_REF); 853| 773| inst->n = node->n; 854| 773| break; 855| 517k| } 856| 517k|} 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: 952, False: 1.13k] ------------------ 53| 952| re_regfree(p); 54| 952| } 55| | 56| | /* cleanup */ 57| 2.08k| free(null_terminated); 58| | 59| 2.08k| return 0; 60| 2.08k|}