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.02k|static RD_INLINE RD_UNUSED void *rd_malloc(size_t sz) { 146| 3.02k| void *p = malloc(sz); 147| 3.02k| rd_assert(p); ------------------ | | 159| 3.02k|#define rd_assert(EXPR) assert(EXPR) ------------------ | Branch (147:9): [True: 0, False: 3.02k] | Branch (147:9): [True: 3.02k, False: 0] ------------------ 148| 3.02k| return p; 149| 3.02k|} regexp.c:rd_free: 157| 5.09k|static RD_INLINE RD_UNUSED void rd_free(void *ptr) { 158| 5.09k| free(ptr); 159| 5.09k|} 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: 10, False: 2.07k] ------------------ 1014| | /* Avoid stack exhaustion in recursive parseatom() et.al. */ 1015| 10| if (errorp) ------------------ | Branch (1015:21): [True: 10, False: 0] ------------------ 1016| 10| *errorp = "regexp pattern too long (max 10000)"; 1017| 10| return NULL; 1018| 10| } 1019| | 1020| 2.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.11k, False: 955] ------------------ 1026| 1.11k| if (errorp) ------------------ | Branch (1026:21): [True: 1.11k, False: 0] ------------------ 1027| 1.11k| *errorp = g->error; 1028| 1.11k| rd_free(g->pstart); 1029| 1.11k| rd_free(prog); 1030| 1.11k| return NULL; 1031| 1.11k| } 1032| | 1033| 955| g->source = pattern; 1034| 955| g->ncclass = 0; 1035| 955| g->nsub = 1; 1036| 34.0k| for (i = 0; i < MAXSUB; ++i) ------------------ | | 45| 34.0k|#define MAXSUB REG_MAXSUB ------------------ | Branch (1036:21): [True: 33.1k, False: 955] ------------------ 1037| 33.1k| 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: 41, False: 914] ------------------ 1051| 41| 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| 258k|static void next(Restate *g) { 530| 258k| g->lookahead = lex(g); 531| 258k|} regexp.c:lex: 370| 258k|static int lex(Restate *g) { 371| 258k| int quoted = nextrune(g); 372| 258k| if (quoted) { ------------------ | Branch (372:13): [True: 3.55k, False: 254k] ------------------ 373| 3.55k| switch (g->yychar) { ------------------ | Branch (373:25): [True: 1.91k, False: 1.64k] ------------------ 374| 203| case 'b': ------------------ | Branch (374:17): [True: 203, False: 3.35k] ------------------ 375| 203| return L_WORD; 376| 205| case 'B': ------------------ | Branch (376:17): [True: 205, False: 3.35k] ------------------ 377| 205| return L_NWORD; 378| 74| case 'd': ------------------ | Branch (378:17): [True: 74, False: 3.48k] ------------------ 379| 74| newcclass(g); 380| 74| addranges_d(g); 381| 74| return L_CCLASS; 382| 90| case 's': ------------------ | Branch (382:17): [True: 90, False: 3.46k] ------------------ 383| 90| newcclass(g); 384| 90| addranges_s(g); 385| 90| return L_CCLASS; 386| 91| case 'w': ------------------ | Branch (386:17): [True: 91, False: 3.46k] ------------------ 387| 91| newcclass(g); 388| 91| addranges_w(g); 389| 91| return L_CCLASS; 390| 91| case 'D': ------------------ | Branch (390:17): [True: 91, False: 3.46k] ------------------ 391| 91| newcclass(g); 392| 91| addranges_d(g); 393| 91| return L_NCCLASS; 394| 155| case 'S': ------------------ | Branch (394:17): [True: 155, False: 3.40k] ------------------ 395| 155| newcclass(g); 396| 155| addranges_s(g); 397| 155| return L_NCCLASS; 398| 54| case 'W': ------------------ | Branch (398:17): [True: 54, False: 3.50k] ------------------ 399| 54| newcclass(g); 400| 54| addranges_w(g); 401| 54| return L_NCCLASS; 402| 951| case '0': ------------------ | Branch (402:17): [True: 951, False: 2.60k] ------------------ 403| 951| g->yychar = 0; 404| 951| return L_CHAR; 405| 3.55k| } 406| 1.64k| if (g->yychar >= '0' && g->yychar <= '9') { ------------------ | Branch (406:21): [True: 1.31k, False: 325] | Branch (406:41): [True: 1.10k, False: 215] ------------------ 407| 1.10k| g->yychar -= '0'; 408| 1.10k| if (*g->source >= '0' && *g->source <= '9') ------------------ | Branch (408:29): [True: 794, False: 309] | Branch (408:50): [True: 199, False: 595] ------------------ 409| 199| g->yychar = g->yychar * 10 + *g->source++ - '0'; 410| 1.10k| return L_REF; 411| 1.10k| } 412| 540| return L_CHAR; 413| 1.64k| } 414| | 415| 254k| switch (g->yychar) { ------------------ | Branch (415:17): [True: 45.4k, False: 209k] ------------------ 416| 1.12k| case 0: ------------------ | Branch (416:9): [True: 1.12k, False: 253k] ------------------ 417| 1.87k| case '$': ------------------ | Branch (417:9): [True: 756, False: 254k] ------------------ 418| 4.10k| case ')': ------------------ | Branch (418:9): [True: 2.22k, False: 252k] ------------------ 419| 8.52k| case '*': ------------------ | Branch (419:9): [True: 4.42k, False: 250k] ------------------ 420| 9.27k| case '+': ------------------ | Branch (420:9): [True: 751, False: 254k] ------------------ 421| 12.3k| case '.': ------------------ | Branch (421:9): [True: 3.03k, False: 251k] ------------------ 422| 16.0k| case '?': ------------------ | Branch (422:9): [True: 3.72k, False: 251k] ------------------ 423| 32.1k| case '^': ------------------ | Branch (423:9): [True: 16.1k, False: 238k] ------------------ 424| 45.4k| case '|': ------------------ | Branch (424:9): [True: 13.3k, False: 241k] ------------------ 425| 45.4k| return g->yychar; 426| 254k| } 427| | 428| 209k| if (g->yychar == '{') ------------------ | Branch (428:13): [True: 2.10k, False: 207k] ------------------ 429| 2.10k| return lexcount(g); 430| 207k| if (g->yychar == '[') ------------------ | Branch (430:13): [True: 743, False: 206k] ------------------ 431| 743| return lexclass(g); 432| 206k| if (g->yychar == '(') { ------------------ | Branch (432:13): [True: 3.79k, False: 202k] ------------------ 433| 3.79k| if (g->source[0] == '?') { ------------------ | Branch (433:21): [True: 2.63k, False: 1.16k] ------------------ 434| 2.63k| if (g->source[1] == ':') { ------------------ | Branch (434:29): [True: 824, False: 1.80k] ------------------ 435| 824| g->source += 2; 436| 824| return L_NC; 437| 824| } 438| 1.80k| if (g->source[1] == '=') { ------------------ | Branch (438:29): [True: 784, False: 1.02k] ------------------ 439| 784| g->source += 2; 440| 784| return L_PLA; 441| 784| } 442| 1.02k| if (g->source[1] == '!') { ------------------ | Branch (442:29): [True: 1.00k, False: 17] ------------------ 443| 1.00k| g->source += 2; 444| 1.00k| return L_NLA; 445| 1.00k| } 446| 1.02k| } 447| 1.17k| return '('; 448| 3.79k| } 449| | 450| 202k| return L_CHAR; 451| 206k|} regexp.c:nextrune: 131| 265k|static int nextrune(Restate *g) { 132| 265k| g->source += chartorune(&g->yychar, g->source); 133| 265k| if (g->yychar == '\\') { ------------------ | Branch (133:13): [True: 9.79k, False: 255k] ------------------ 134| 9.79k| g->source += chartorune(&g->yychar, g->source); 135| 9.79k| switch (g->yychar) { ------------------ | Branch (135:25): [True: 4.39k, False: 5.39k] ------------------ 136| 11| case 0: ------------------ | Branch (136:17): [True: 11, False: 9.78k] ------------------ 137| 11| die(g, "unterminated escape sequence"); 138| 205| case 'f': ------------------ | Branch (138:17): [True: 194, False: 9.60k] ------------------ 139| 205| g->yychar = '\f'; 140| 205| return 0; 141| 219| case 'n': ------------------ | Branch (141:17): [True: 219, False: 9.57k] ------------------ 142| 219| g->yychar = '\n'; 143| 219| return 0; 144| 244| case 'r': ------------------ | Branch (144:17): [True: 244, False: 9.55k] ------------------ 145| 244| g->yychar = '\r'; 146| 244| return 0; 147| 194| case 't': ------------------ | Branch (147:17): [True: 194, False: 9.60k] ------------------ 148| 194| g->yychar = '\t'; 149| 194| return 0; 150| 194| case 'v': ------------------ | Branch (150:17): [True: 194, False: 9.60k] ------------------ 151| 194| g->yychar = '\v'; 152| 194| return 0; 153| 194| case 'c': ------------------ | Branch (153:17): [True: 194, False: 9.60k] ------------------ 154| 194| g->yychar = (*g->source++) & 31; 155| 194| return 0; 156| 1.24k| case 'x': ------------------ | Branch (156:17): [True: 1.24k, False: 8.55k] ------------------ 157| 1.24k| g->yychar = hex(g, *g->source++) << 4; 158| 1.24k| g->yychar += hex(g, *g->source++); 159| 1.24k| if (g->yychar == 0) { ------------------ | Branch (159:29): [True: 343, False: 899] ------------------ 160| 343| g->yychar = '0'; 161| 343| return 1; 162| 343| } 163| 899| return 0; 164| 1.90k| case 'u': ------------------ | Branch (164:17): [True: 1.90k, False: 7.89k] ------------------ 165| 1.90k| g->yychar = hex(g, *g->source++) << 12; 166| 1.90k| g->yychar += hex(g, *g->source++) << 8; 167| 1.90k| g->yychar += hex(g, *g->source++) << 4; 168| 1.90k| g->yychar += hex(g, *g->source++); 169| 1.90k| if (g->yychar == 0) { ------------------ | Branch (169:29): [True: 393, False: 1.51k] ------------------ 170| 393| g->yychar = '0'; 171| 393| return 1; 172| 393| } 173| 1.51k| return 0; 174| 9.79k| } 175| 5.39k| if (strchr(ESCAPES, g->yychar)) ------------------ | | 129| 5.39k|#define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|0123456789" ------------------ | Branch (175:21): [True: 4.95k, False: 448] ------------------ 176| 4.95k| return 1; 177| 448| if (isalpharune(g->yychar) || ------------------ | Branch (177:21): [True: 10, False: 438] ------------------ 178| 438| g->yychar == '_') /* check identity escape */ ------------------ | Branch (178:21): [True: 1, False: 437] ------------------ 179| 11| die(g, "invalid escape character"); 180| 448| return 0; 181| 5.39k| } 182| 255k| return 0; 183| 265k|} regexp.c:chartorune: 37| 275k|static int chartorune(Rune *r, const char *s) { 38| | /* TODO: Add UTF-8 decoding */ 39| 275k| *r = *s; 40| 275k| return 1; 41| 275k|} regexp.c:hex: 111| 9.82k|static int hex(Restate *g, int c) { 112| 9.82k| if (c >= '0' && c <= '9') ------------------ | Branch (112:13): [True: 9.64k, False: 177] | Branch (112:25): [True: 3.18k, False: 6.46k] ------------------ 113| 3.18k| return c - '0'; 114| 6.64k| if (c >= 'a' && c <= 'f') ------------------ | Branch (114:13): [True: 3.30k, False: 3.34k] | Branch (114:25): [True: 3.26k, False: 32] ------------------ 115| 3.26k| return c - 'a' + 0xA; 116| 3.37k| if (c >= 'A' && c <= 'F') ------------------ | Branch (116:13): [True: 3.17k, False: 200] | Branch (116:25): [True: 3.10k, False: 64] ------------------ 117| 3.10k| return c - 'A' + 0xA; 118| 264| die(g, "invalid escape sequence"); 119| 264| return 0; 120| 3.37k|} regexp.c:isalpharune: 25| 448|static int isalpharune(Rune c) { 26| | /* TODO: Add unicode support */ 27| 448| return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); ------------------ | Branch (27:17): [True: 241, False: 207] | Branch (27:29): [True: 5, False: 236] | Branch (27:43): [True: 232, False: 211] | Branch (27:55): [True: 5, False: 227] ------------------ 28| 448|} regexp.c:newcclass: 218| 1.29k|static void newcclass(Restate *g) { 219| 1.29k| if (g->ncclass >= nelem(g->prog->cclass)) ------------------ | | 21| 1.29k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (219:13): [True: 7, False: 1.29k] ------------------ 220| 7| die(g, "too many character classes"); 221| 1.29k| g->yycc = g->prog->cclass + g->ncclass++; 222| 1.29k| g->yycc->end = g->yycc->spans; 223| 1.29k|} regexp.c:addranges_d: 234| 901|static void addranges_d(Restate *g) { 235| 901| addrange(g, '0', '9'); 236| 901|} regexp.c:addrange: 225| 8.88k|static void addrange(Restate *g, Rune a, Rune b) { 226| 8.88k| if (a > b) ------------------ | Branch (226:13): [True: 44, False: 8.83k] ------------------ 227| 44| die(g, "invalid character class range"); 228| 8.88k| if (g->yycc->end + 2 == g->yycc->spans + nelem(g->yycc->spans)) ------------------ | | 21| 8.88k|#define nelem(a) (sizeof(a) / sizeof(a)[0]) ------------------ | Branch (228:13): [True: 42, False: 8.83k] ------------------ 229| 42| die(g, "too many character class ranges"); 230| 8.88k| *g->yycc->end++ = a; 231| 8.88k| *g->yycc->end++ = b; 232| 8.88k|} regexp.c:addranges_s: 243| 474|static void addranges_s(Restate *g) { 244| 474| addrange(g, 0x9, 0x9); 245| 474| addrange(g, 0xA, 0xD); 246| 474| addrange(g, 0x20, 0x20); 247| 474| addrange(g, 0xA0, 0xA0); 248| 474| addrange(g, 0x2028, 0x2029); 249| 474| addrange(g, 0xFEFF, 0xFEFF); 250| 474|} regexp.c:addranges_w: 262| 242|static void addranges_w(Restate *g) { 263| 242| addrange(g, '0', '9'); 264| 242| addrange(g, 'A', 'Z'); 265| 242| addrange(g, '_', '_'); 266| 242| addrange(g, 'a', 'z'); 267| 242|} regexp.c:lexcount: 185| 2.10k|static int lexcount(Restate *g) { 186| 2.10k| g->yychar = *g->source++; 187| | 188| 2.10k| g->yymin = dec(g, g->yychar); 189| 2.10k| g->yychar = *g->source++; 190| 4.10k| while (g->yychar != ',' && g->yychar != '}') { ------------------ | Branch (190:16): [True: 3.13k, False: 963] | Branch (190:36): [True: 1.99k, False: 1.14k] ------------------ 191| 1.99k| g->yymin = g->yymin * 10 + dec(g, g->yychar); 192| 1.99k| g->yychar = *g->source++; 193| 1.99k| } 194| 2.10k| if (g->yymin >= REPINF) ------------------ | | 43| 2.10k|#define REPINF 255 ------------------ | Branch (194:13): [True: 22, False: 2.08k] ------------------ 195| 22| die(g, "numeric overflow"); 196| | 197| 2.10k| if (g->yychar == ',') { ------------------ | Branch (197:13): [True: 906, False: 1.20k] ------------------ 198| 906| g->yychar = *g->source++; 199| 906| if (g->yychar == '}') { ------------------ | Branch (199:21): [True: 260, False: 646] ------------------ 200| 260| g->yymax = REPINF; ------------------ | | 43| 260|#define REPINF 255 ------------------ 201| 646| } else { 202| 646| g->yymax = dec(g, g->yychar); 203| 646| g->yychar = *g->source++; 204| 1.77k| while (g->yychar != '}') { ------------------ | Branch (204:32): [True: 1.12k, False: 646] ------------------ 205| 1.12k| g->yymax = g->yymax * 10 + dec(g, g->yychar); 206| 1.12k| g->yychar = *g->source++; 207| 1.12k| } 208| 646| if (g->yymax >= REPINF) ------------------ | | 43| 646|#define REPINF 255 ------------------ | Branch (208:29): [True: 20, False: 626] ------------------ 209| 20| die(g, "numeric overflow"); 210| 646| } 211| 1.20k| } else { 212| 1.20k| g->yymax = g->yymin; 213| 1.20k| } 214| | 215| 2.10k| return L_COUNT; 216| 2.10k|} regexp.c:dec: 122| 5.87k|static int dec(Restate *g, int c) { 123| 5.87k| if (c >= '0' && c <= '9') ------------------ | Branch (123:13): [True: 5.78k, False: 86] | Branch (123:25): [True: 5.75k, False: 28] ------------------ 124| 5.75k| return c - '0'; 125| 114| die(g, "invalid quantifier"); 126| 114| return 0; 127| 5.87k|} regexp.c:lexclass: 277| 743|static int lexclass(Restate *g) { 278| 743| int type = L_CCLASS; 279| 743| int quoted, havesave, havedash; 280| 743| Rune save = 0; 281| | 282| 743| newcclass(g); 283| | 284| 743| quoted = nextrune(g); 285| 743| if (!quoted && g->yychar == '^') { ------------------ | Branch (285:13): [True: 532, False: 211] | Branch (285:24): [True: 35, False: 497] ------------------ 286| 35| type = L_NCCLASS; 287| 35| quoted = nextrune(g); 288| 35| } 289| | 290| 743| havesave = havedash = 0; 291| 7.23k| for (;;) { 292| 7.23k| if (g->yychar == 0) ------------------ | Branch (292:21): [True: 229, False: 7.00k] ------------------ 293| 229| die(g, "unterminated character class"); 294| 7.23k| if (!quoted && g->yychar == ']') ------------------ | Branch (294:21): [True: 4.87k, False: 2.35k] | Branch (294:32): [True: 427, False: 4.44k] ------------------ 295| 427| break; 296| | 297| 6.80k| if (!quoted && g->yychar == '-') { ------------------ | Branch (297:21): [True: 4.44k, False: 2.35k] | Branch (297:32): [True: 2.18k, False: 2.26k] ------------------ 298| 2.18k| if (havesave) { ------------------ | Branch (298:29): [True: 1.62k, False: 561] ------------------ 299| 1.62k| if (havedash) { ------------------ | Branch (299:37): [True: 463, False: 1.16k] ------------------ 300| 463| addrange(g, save, '-'); 301| 463| havesave = havedash = 0; 302| 1.16k| } else { 303| 1.16k| havedash = 1; 304| 1.16k| } 305| 1.62k| } else { 306| 561| save = '-'; 307| 561| havesave = 1; 308| 561| } 309| 4.62k| } else if (quoted && strchr("DSWdsw", g->yychar)) { ------------------ | Branch (309:28): [True: 2.12k, False: 2.49k] | Branch (309:38): [True: 1.47k, False: 651] ------------------ 310| 1.47k| if (havesave) { ------------------ | Branch (310:29): [True: 539, False: 939] ------------------ 311| 539| addrange(g, save, save); 312| 539| if (havedash) ------------------ | Branch (312:37): [True: 195, False: 344] ------------------ 313| 195| addrange(g, '-', '-'); 314| 539| } 315| 1.47k| switch (g->yychar) { ------------------ | Branch (315:33): [True: 1.47k, False: 3] ------------------ 316| 738| case 'd': ------------------ | Branch (316:25): [True: 738, False: 740] ------------------ 317| 738| addranges_d(g); 318| 738| break; 319| 231| case 's': ------------------ | Branch (319:25): [True: 231, False: 1.24k] ------------------ 320| 231| addranges_s(g); 321| 231| break; 322| 99| case 'w': ------------------ | Branch (322:25): [True: 99, False: 1.37k] ------------------ 323| 99| addranges_w(g); 324| 99| break; 325| 312| case 'D': ------------------ | Branch (325:25): [True: 312, False: 1.16k] ------------------ 326| 312| addranges_D(g); 327| 312| break; 328| 4| case 'S': ------------------ | Branch (328:25): [True: 4, False: 1.47k] ------------------ 329| 4| addranges_S(g); 330| 4| break; 331| 91| case 'W': ------------------ | Branch (331:25): [True: 91, False: 1.38k] ------------------ 332| 91| addranges_W(g); 333| 91| break; 334| 1.47k| } 335| 1.44k| havesave = havedash = 0; 336| 3.14k| } else { 337| 3.14k| if (quoted) { ------------------ | Branch (337:29): [True: 651, False: 2.49k] ------------------ 338| 651| if (g->yychar == 'b') ------------------ | Branch (338:37): [True: 196, False: 455] ------------------ 339| 196| g->yychar = '\b'; 340| 455| else if (g->yychar == '0') ------------------ | Branch (340:42): [True: 198, False: 257] ------------------ 341| 198| g->yychar = 0; 342| | /* else identity escape */ 343| 651| } 344| 3.14k| if (havesave) { ------------------ | Branch (344:29): [True: 1.74k, False: 1.39k] ------------------ 345| 1.74k| if (havedash) { ------------------ | Branch (345:37): [True: 455, False: 1.29k] ------------------ 346| 455| addrange(g, save, g->yychar); 347| 455| havesave = havedash = 0; 348| 1.29k| } else { 349| 1.29k| addrange(g, save, save); 350| 1.29k| save = g->yychar; 351| 1.29k| } 352| 1.74k| } else { 353| 1.39k| save = g->yychar; 354| 1.39k| havesave = 1; 355| 1.39k| } 356| 3.14k| } 357| | 358| 6.77k| quoted = nextrune(g); 359| 6.77k| } 360| | 361| 708| if (havesave) { ------------------ | Branch (361:13): [True: 143, False: 565] ------------------ 362| 143| addrange(g, save, save); 363| 143| if (havedash) ------------------ | Branch (363:21): [True: 42, False: 101] ------------------ 364| 42| addrange(g, '-', '-'); 365| 143| } 366| | 367| 708| return type; 368| 743|} regexp.c:addranges_D: 238| 312|static void addranges_D(Restate *g) { 239| 312| addrange(g, 0, '0' - 1); 240| 312| addrange(g, '9' + 1, 0xFFFF); 241| 312|} 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| 91|static void addranges_W(Restate *g) { 270| 91| addrange(g, 0, '0' - 1); 271| 91| addrange(g, '9' + 1, 'A' - 1); 272| 91| addrange(g, 'Z' + 1, '_' - 1); 273| 91| addrange(g, '_' + 1, 'a' - 1); 274| 91| addrange(g, 'z' + 1, 0xFFFF); 275| 91|} regexp.c:parsealt: 654| 5.26k|static Renode *parsealt(Restate *g) { 655| 5.26k| Renode *alt, *x; 656| 5.26k| alt = parsecat(g); 657| 18.6k| while (re_accept(g, '|')) { ------------------ | Branch (657:16): [True: 13.3k, False: 5.26k] ------------------ 658| 13.3k| x = alt; 659| 13.3k| alt = newnode(g, P_ALT); 660| 13.3k| alt->x = x; 661| 13.3k| alt->y = parsecat(g); 662| 13.3k| } 663| 5.26k| return alt; 664| 5.26k|} regexp.c:parsecat: 638| 18.6k|static Renode *parsecat(Restate *g) { 639| 18.6k| Renode *cat, *x; 640| 18.6k| if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') { ------------------ | Branch (640:13): [True: 18.5k, False: 108] | Branch (640:29): [True: 6.00k, False: 12.5k] | Branch (640:52): [True: 4.61k, False: 1.39k] ------------------ 641| 4.61k| cat = parserep(g); 642| 230k| while (g->lookahead && g->lookahead != '|' && ------------------ | Branch (642:24): [True: 227k, False: 2.93k] | Branch (642:40): [True: 226k, False: 854] ------------------ 643| 226k| g->lookahead != ')') { ------------------ | Branch (643:24): [True: 225k, False: 827] ------------------ 644| 225k| x = cat; 645| 225k| cat = newnode(g, P_CAT); 646| 225k| cat->x = x; 647| 225k| cat->y = parserep(g); 648| 225k| } 649| 4.61k| return cat; 650| 4.61k| } 651| 14.0k| return NULL; 652| 18.6k|} regexp.c:parserep: 609| 230k|static Renode *parserep(Restate *g) { 610| 230k| Renode *atom; 611| | 612| 230k| if (re_accept(g, '^')) ------------------ | Branch (612:13): [True: 16.1k, False: 214k] ------------------ 613| 16.1k| return newnode(g, P_BOL); 614| 214k| if (re_accept(g, '$')) ------------------ | Branch (614:13): [True: 756, False: 213k] ------------------ 615| 756| return newnode(g, P_EOL); 616| 213k| if (re_accept(g, L_WORD)) ------------------ | Branch (616:13): [True: 203, False: 213k] ------------------ 617| 203| return newnode(g, P_WORD); 618| 213k| if (re_accept(g, L_NWORD)) ------------------ | Branch (618:13): [True: 205, False: 213k] ------------------ 619| 205| return newnode(g, P_NWORD); 620| | 621| 213k| atom = parseatom(g); 622| 213k| if (g->lookahead == L_COUNT) { ------------------ | Branch (622:13): [True: 1.86k, False: 211k] ------------------ 623| 1.86k| int min = g->yymin, max = g->yymax; 624| 1.86k| next(g); 625| 1.86k| if (max < min) ------------------ | Branch (625:21): [True: 3, False: 1.86k] ------------------ 626| 3| die(g, "invalid quantifier"); 627| 1.86k| return newrep(g, atom, re_accept(g, '?'), min, max); 628| 1.86k| } 629| 211k| if (re_accept(g, '*')) ------------------ | Branch (629:13): [True: 4.41k, False: 206k] ------------------ 630| 4.41k| return newrep(g, atom, re_accept(g, '?'), 0, REPINF); ------------------ | | 43| 4.41k|#define REPINF 255 ------------------ 631| 206k| if (re_accept(g, '+')) ------------------ | Branch (631:13): [True: 740, False: 205k] ------------------ 632| 740| return newrep(g, atom, re_accept(g, '?'), 1, REPINF); ------------------ | | 43| 740|#define REPINF 255 ------------------ 633| 205k| if (re_accept(g, '?')) ------------------ | Branch (633:13): [True: 574, False: 205k] ------------------ 634| 574| return newrep(g, atom, re_accept(g, '?'), 0, 1); 635| 205k| return atom; 636| 205k|} regexp.c:parseatom: 543| 213k|static Renode *parseatom(Restate *g) { 544| 213k| Renode *atom; 545| 213k| if (g->lookahead == L_CHAR) { ------------------ | Branch (545:13): [True: 203k, False: 9.04k] ------------------ 546| 203k| atom = newnode(g, P_CHAR); 547| 203k| atom->c = g->yychar; 548| 203k| next(g); 549| 203k| return atom; 550| 203k| } 551| 9.04k| if (g->lookahead == L_CCLASS) { ------------------ | Branch (551:13): [True: 647, False: 8.39k] ------------------ 552| 647| atom = newnode(g, P_CCLASS); 553| 647| atom->cc = g->yycc; 554| 647| next(g); 555| 647| return atom; 556| 647| } 557| 8.39k| if (g->lookahead == L_NCCLASS) { ------------------ | Branch (557:13): [True: 326, False: 8.06k] ------------------ 558| 326| atom = newnode(g, P_NCCLASS); 559| 326| atom->cc = g->yycc; 560| 326| next(g); 561| 326| return atom; 562| 326| } 563| 8.06k| if (g->lookahead == L_REF) { ------------------ | Branch (563:13): [True: 1.10k, False: 6.96k] ------------------ 564| 1.10k| atom = newnode(g, P_REF); 565| 1.10k| if (g->yychar == 0 || g->yychar > g->nsub || !g->sub[g->yychar]) ------------------ | Branch (565:21): [True: 0, False: 1.10k] | Branch (565:39): [True: 17, False: 1.08k] | Branch (565:62): [True: 9, False: 1.07k] ------------------ 566| 26| die(g, "invalid back-reference"); 567| 1.10k| atom->n = g->yychar; 568| 1.10k| atom->x = g->sub[g->yychar]; 569| 1.10k| next(g); 570| 1.10k| return atom; 571| 1.10k| } 572| 6.96k| if (re_accept(g, '.')) ------------------ | Branch (572:13): [True: 3.03k, False: 3.93k] ------------------ 573| 3.03k| return newnode(g, P_ANY); 574| 3.93k| if (re_accept(g, '(')) { ------------------ | Branch (574:13): [True: 1.17k, False: 2.75k] ------------------ 575| 1.17k| atom = newnode(g, P_PAR); 576| 1.17k| if (g->nsub == MAXSUB) ------------------ | | 45| 1.17k|#define MAXSUB REG_MAXSUB ------------------ | Branch (576:21): [True: 7, False: 1.17k] ------------------ 577| 7| die(g, "too many captures"); 578| 1.17k| atom->n = g->nsub++; 579| 1.17k| atom->x = parsealt(g); 580| 1.17k| g->sub[atom->n] = atom; 581| 1.17k| if (!re_accept(g, ')')) ------------------ | Branch (581:21): [True: 46, False: 1.13k] ------------------ 582| 46| die(g, "unmatched '('"); 583| 1.17k| return atom; 584| 1.17k| } 585| 2.75k| if (re_accept(g, L_NC)) { ------------------ | Branch (585:13): [True: 824, False: 1.92k] ------------------ 586| 824| atom = parsealt(g); 587| 824| if (!re_accept(g, ')')) ------------------ | Branch (587:21): [True: 12, False: 812] ------------------ 588| 12| die(g, "unmatched '('"); 589| 824| return atom; 590| 824| } 591| 1.92k| if (re_accept(g, L_PLA)) { ------------------ | Branch (591:13): [True: 784, False: 1.14k] ------------------ 592| 784| atom = newnode(g, P_PLA); 593| 784| atom->x = parsealt(g); 594| 784| if (!re_accept(g, ')')) ------------------ | Branch (594:21): [True: 9, False: 775] ------------------ 595| 9| die(g, "unmatched '('"); 596| 784| return atom; 597| 784| } 598| 1.14k| if (re_accept(g, L_NLA)) { ------------------ | Branch (598:13): [True: 1.00k, False: 136] ------------------ 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: 998] ------------------ 602| 10| die(g, "unmatched '('"); 603| 1.00k| return atom; 604| 1.00k| } 605| 136| die(g, "syntax error"); 606| | return NULL; 607| 1.14k|} regexp.c:newrep: 518| 7.58k|static Renode *newrep(Restate *g, Renode *atom, int ng, int min, int max) { 519| 7.58k| Renode *rep = newnode(g, P_REP); 520| 7.58k| if (max == REPINF && empty(atom)) ------------------ | | 43| 15.1k|#define REPINF 255 ------------------ | Branch (520:13): [True: 5.40k, False: 2.17k] | Branch (520:30): [True: 43, False: 5.36k] ------------------ 521| 43| die(g, "infinite loop matching the empty string"); 522| 7.58k| rep->ng = ng; 523| 7.58k| rep->m = min; 524| 7.58k| rep->n = max; 525| 7.58k| rep->x = atom; 526| 7.58k| return rep; 527| 7.58k|} regexp.c:empty: 494| 16.7k|static int empty(Renode *node) { 495| 16.7k| if (!node) ------------------ | Branch (495:13): [True: 736, False: 16.0k] ------------------ 496| 736| return 1; 497| 16.0k| switch (node->type) { 498| 215| default: ------------------ | Branch (498:9): [True: 215, False: 15.8k] ------------------ 499| 215| return 1; 500| 4.11k| case P_CAT: ------------------ | Branch (500:9): [True: 4.11k, False: 11.9k] ------------------ 501| 4.11k| return empty(node->x) && empty(node->y); ------------------ | Branch (501:24): [True: 2.12k, False: 1.99k] | Branch (501:42): [True: 1.72k, False: 399] ------------------ 502| 619| case P_ALT: ------------------ | Branch (502:9): [True: 619, False: 15.4k] ------------------ 503| 619| return empty(node->x) || empty(node->y); ------------------ | Branch (503:24): [True: 399, False: 220] | Branch (503:42): [True: 109, False: 111] ------------------ 504| 1.49k| case P_REP: ------------------ | Branch (504:9): [True: 1.49k, False: 14.5k] ------------------ 505| 1.49k| return empty(node->x) || node->m == 0; ------------------ | Branch (505:24): [True: 194, False: 1.30k] | Branch (505:42): [True: 1.21k, False: 88] ------------------ 506| 1.82k| case P_PAR: ------------------ | Branch (506:9): [True: 1.82k, False: 14.2k] ------------------ 507| 1.82k| return empty(node->x); 508| 970| case P_REF: ------------------ | Branch (508:9): [True: 970, False: 15.0k] ------------------ 509| 970| return empty(node->x); 510| 1.07k| case P_ANY: ------------------ | Branch (510:9): [True: 1.07k, False: 14.9k] ------------------ 511| 6.39k| case P_CHAR: ------------------ | Branch (511:9): [True: 5.32k, False: 10.7k] ------------------ 512| 6.60k| case P_CCLASS: ------------------ | Branch (512:9): [True: 202, False: 15.8k] ------------------ 513| 6.79k| case P_NCCLASS: ------------------ | Branch (513:9): [True: 198, False: 15.8k] ------------------ 514| 6.79k| return 0; 515| 16.0k| } 516| 16.0k|} regexp.c:re_accept: 533| 1.53M|static int re_accept(Restate *g, int t) { 534| 1.53M| if (g->lookahead == t) { ------------------ | Branch (534:13): [True: 48.5k, False: 1.48M] ------------------ 535| 48.5k| next(g); 536| 48.5k| return 1; 537| 48.5k| } 538| 1.48M| return 0; 539| 1.53M|} regexp.c:newnode: 482| 475k|static Renode *newnode(Restate *g, int type) { 483| 475k| Renode *node = g->pend++; 484| 475k| node->type = type; 485| 475k| node->cc = NULL; 486| 475k| node->c = 0; 487| 475k| node->ng = 0; 488| 475k| node->m = 0; 489| 475k| node->n = 0; 490| | node->x = node->y = NULL; 491| 475k| return node; 492| 475k|} regexp.c:die: 84| 1.11k|static void die(Restate *g, const char *message) { 85| 1.11k| g->error = message; 86| 1.11k| longjmp(g->kaboom, 1); 87| 1.11k|} regexp.c:count: 697| 460k|static unsigned int count(Renode *node) { 698| 460k| unsigned int min, max; 699| 460k| if (!node) ------------------ | Branch (699:13): [True: 12.7k, False: 447k] ------------------ 700| 12.7k| return 0; 701| 447k| switch (node->type) { 702| 213k| default: ------------------ | Branch (702:9): [True: 213k, False: 234k] ------------------ 703| 213k| return 1; 704| 213k| case P_CAT: ------------------ | Branch (704:9): [True: 213k, False: 234k] ------------------ 705| 213k| return count(node->x) + count(node->y); 706| 12.2k| case P_ALT: ------------------ | Branch (706:9): [True: 12.2k, False: 435k] ------------------ 707| 12.2k| return count(node->x) + count(node->y) + 2; 708| 6.98k| case P_REP: ------------------ | Branch (708:9): [True: 6.98k, False: 440k] ------------------ 709| 6.98k| min = node->m; 710| 6.98k| max = node->n; 711| 6.98k| if (min == max) ------------------ | Branch (711:21): [True: 1.07k, False: 5.90k] ------------------ 712| 1.07k| return count(node->x) * min; 713| 5.90k| if (max < REPINF) ------------------ | | 43| 5.90k|#define REPINF 255 ------------------ | Branch (713:21): [True: 902, False: 5.00k] ------------------ 714| 902| return count(node->x) * max + (max - min); 715| 5.00k| return count(node->x) * (min + 1) + 2; 716| 573| case P_PAR: ------------------ | Branch (716:9): [True: 573, False: 447k] ------------------ 717| 573| return count(node->x) + 2; 718| 456| case P_PLA: ------------------ | Branch (718:9): [True: 456, False: 447k] ------------------ 719| 456| return count(node->x) + 2; 720| 440| case P_NLA: ------------------ | Branch (720:9): [True: 440, False: 447k] ------------------ 721| 440| return count(node->x) + 2; 722| 447k| } 723| 447k|} 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| 553k|static void compile(Reprog *prog, Renode *node) { 736| 553k| Reinst *inst, *split, *jump; 737| 553k| unsigned int i; 738| | 739| 553k| if (!node) ------------------ | Branch (739:13): [True: 15.2k, False: 538k] ------------------ 740| 15.2k| return; 741| | 742| 538k| switch (node->type) { ------------------ | Branch (742:17): [True: 538k, False: 0] ------------------ 743| 186k| case P_CAT: ------------------ | Branch (743:9): [True: 186k, False: 351k] ------------------ 744| 186k| compile(prog, node->x); 745| 186k| compile(prog, node->y); 746| 186k| break; 747| | 748| 13.3k| case P_ALT: ------------------ | Branch (748:9): [True: 13.3k, False: 524k] ------------------ 749| 13.3k| split = emit(prog, I_SPLIT); 750| 13.3k| compile(prog, node->x); 751| 13.3k| jump = emit(prog, I_JUMP); 752| 13.3k| compile(prog, node->y); 753| 13.3k| split->x = split + 1; 754| 13.3k| split->y = jump + 1; 755| 13.3k| jump->x = prog->end; 756| 13.3k| break; 757| | 758| 10.3k| case P_REP: ------------------ | Branch (758:9): [True: 10.3k, False: 527k] ------------------ 759| 146k| for (i = 0; i < node->m; ++i) { ------------------ | Branch (759:29): [True: 135k, False: 10.3k] ------------------ 760| 135k| inst = prog->end; 761| 135k| compile(prog, node->x); 762| 135k| } 763| 10.3k| if (node->m == node->n) ------------------ | Branch (763:21): [True: 2.39k, False: 7.98k] ------------------ 764| 2.39k| break; 765| 7.98k| if (node->n < REPINF) { ------------------ | | 43| 7.98k|#define REPINF 255 ------------------ | Branch (765:21): [True: 1.36k, False: 6.62k] ------------------ 766| 5.82k| for (i = node->m; i < node->n; ++i) { ------------------ | Branch (766:43): [True: 4.45k, False: 1.36k] ------------------ 767| 4.45k| split = emit(prog, I_SPLIT); 768| 4.45k| compile(prog, node->x); 769| 4.45k| if (node->ng) { ------------------ | Branch (769:37): [True: 611, False: 3.84k] ------------------ 770| 611| split->y = split + 1; 771| 611| split->x = prog->end; 772| 3.84k| } else { 773| 3.84k| split->x = split + 1; 774| 3.84k| split->y = prog->end; 775| 3.84k| } 776| 4.45k| } 777| 6.62k| } else if (node->m == 0) { ------------------ | Branch (777:28): [True: 4.87k, False: 1.74k] ------------------ 778| 4.87k| split = emit(prog, I_SPLIT); 779| 4.87k| compile(prog, node->x); 780| 4.87k| jump = emit(prog, I_JUMP); 781| 4.87k| if (node->ng) { ------------------ | Branch (781:29): [True: 2.21k, False: 2.66k] ------------------ 782| 2.21k| split->y = split + 1; 783| 2.21k| split->x = prog->end; 784| 2.66k| } else { 785| 2.66k| split->x = split + 1; 786| 2.66k| split->y = prog->end; 787| 2.66k| } 788| 4.87k| jump->x = split; 789| 4.87k| } else { 790| 1.74k| split = emit(prog, I_SPLIT); 791| 1.74k| if (node->ng) { ------------------ | Branch (791:29): [True: 583, False: 1.16k] ------------------ 792| 583| split->y = inst; 793| 583| split->x = prog->end; 794| 1.16k| } else { 795| 1.16k| split->x = inst; 796| 1.16k| split->y = prog->end; 797| 1.16k| } 798| 1.74k| } 799| 7.98k| break; 800| | 801| 8.88k| case P_BOL: ------------------ | Branch (801:9): [True: 8.88k, False: 529k] ------------------ 802| 8.88k| emit(prog, I_BOL); 803| 8.88k| break; 804| 914| case P_EOL: ------------------ | Branch (804:9): [True: 914, False: 537k] ------------------ 805| 914| emit(prog, I_EOL); 806| 914| break; 807| 516| case P_WORD: ------------------ | Branch (807:9): [True: 516, False: 537k] ------------------ 808| 516| emit(prog, I_WORD); 809| 516| break; 810| 543| case P_NWORD: ------------------ | Branch (810:9): [True: 543, False: 537k] ------------------ 811| 543| emit(prog, I_NWORD); 812| 543| break; 813| | 814| 5.85k| case P_PAR: ------------------ | Branch (814:9): [True: 5.85k, False: 532k] ------------------ 815| 5.85k| inst = emit(prog, I_LPAR); 816| 5.85k| inst->n = node->n; 817| 5.85k| compile(prog, node->x); 818| 5.85k| inst = emit(prog, I_RPAR); 819| 5.85k| inst->n = node->n; 820| 5.85k| break; 821| 804| case P_PLA: ------------------ | Branch (821:9): [True: 804, False: 537k] ------------------ 822| 804| split = emit(prog, I_PLA); 823| 804| compile(prog, node->x); 824| 804| emit(prog, I_END); 825| 804| split->x = split + 1; 826| 804| split->y = prog->end; 827| 804| break; 828| 700| case P_NLA: ------------------ | Branch (828:9): [True: 700, False: 537k] ------------------ 829| 700| split = emit(prog, I_NLA); 830| 700| compile(prog, node->x); 831| 700| emit(prog, I_END); 832| 700| split->x = split + 1; 833| 700| split->y = prog->end; 834| 700| break; 835| | 836| 6.89k| case P_ANY: ------------------ | Branch (836:9): [True: 6.89k, False: 531k] ------------------ 837| 6.89k| emit(prog, I_ANY); 838| 6.89k| break; 839| 300k| case P_CHAR: ------------------ | Branch (839:9): [True: 300k, False: 237k] ------------------ 840| 300k| inst = emit(prog, I_CHAR); 841| 300k| inst->c = (prog->flags & REG_ICASE) ? canon(node->c) : node->c; ------------------ | Branch (841:27): [True: 0, False: 300k] ------------------ 842| 300k| break; 843| 561| case P_CCLASS: ------------------ | Branch (843:9): [True: 561, False: 537k] ------------------ 844| 561| inst = emit(prog, I_CCLASS); 845| 561| inst->cc = node->cc; 846| 561| break; 847| 550| case P_NCCLASS: ------------------ | Branch (847:9): [True: 550, False: 537k] ------------------ 848| 550| inst = emit(prog, I_NCCLASS); 849| 550| inst->cc = node->cc; 850| 550| break; 851| 716| case P_REF: ------------------ | Branch (851:9): [True: 716, False: 537k] ------------------ 852| 716| inst = emit(prog, I_REF); 853| 716| inst->n = node->n; 854| 716| break; 855| 538k| } 856| 538k|} 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.12k] ------------------ 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|}