From 6f5bb02b923c1402eba04ce78033317da401971e Mon Sep 17 00:00:00 2001 From: Bruce Hill Date: Sat, 6 May 2023 13:43:32 -0400 Subject: Use tagged union style for extra safety and concision --- json.c | 2 +- match.c | 170 ++++++++++++++++++++++-------------------- pattern.c | 238 ++++++++++++++++++++++------------------------------------- pattern.h | 86 +++++++++++++++------ printmatch.c | 5 +- 5 files changed, 245 insertions(+), 256 deletions(-) diff --git a/json.c b/json.c index 17533ca..71ada3b 100644 --- a/json.c +++ b/json.c @@ -28,7 +28,7 @@ static int _json_match(const char *text, match_t *m, int comma, bool verbose) comma = 0; printf("{"); if (m->pat->type == BP_TAGGED) { - printf("\"tag\":\"%.*s\"", (int)m->pat->args.capture.namelen, m->pat->args.capture.name); + printf("\"tag\":\"%.*s\"", (int)Match(m->pat, BP_TAGGED)->namelen, Match(m->pat, BP_TAGGED)->name); comma = 1; } if (verbose) { diff --git a/match.c b/match.c index 9e0a0ec..9a784b3 100644 --- a/match.c +++ b/match.c @@ -227,13 +227,15 @@ static pat_t *_lookup_def(match_ctx_t *ctx, pat_t *defs, const char *name, size_ { while (defs) { if (defs->type == BP_CHAIN) { - pat_t *second = _lookup_def(ctx, defs->args.multiple.second, name, namelen); + auto chain = Match(defs, BP_CHAIN); + pat_t *second = _lookup_def(ctx, chain->second, name, namelen); if (second) return second; - defs = defs->args.multiple.first; + defs = chain->first; } else if (defs->type == BP_DEFINITIONS) { - if (namelen == defs->args.def.namelen && strncmp(defs->args.def.name, name, namelen) == 0) - return defs->args.def.meaning; - defs = defs->args.def.next_def; + auto def = Match(defs, BP_DEFINITIONS); + if (namelen == def->namelen && strncmp(def->name, name, namelen) == 0) + return def->meaning; + defs = def->next_def; } else { match_error(ctx, "Invalid pattern type in definitions"); return NULL; @@ -263,7 +265,8 @@ __attribute__((nonnull(1))) static inline pat_t *deref(match_ctx_t *ctx, pat_t *pat) { if (pat && pat->type == BP_REF) { - pat_t *def = lookup_ctx(ctx, pat->args.ref.name, pat->args.ref.len); + auto ref = Match(pat, BP_REF); + pat_t *def = lookup_ctx(ctx, ref->name, ref->len); if (def) return def; } return pat; @@ -280,23 +283,27 @@ static pat_t *get_prerequisite(match_ctx_t *ctx, pat_t *pat) for (pat_t *p = pat; p; ) { switch (p->type) { case BP_BEFORE: - p = p->args.pat; break; + p = Match(p, BP_BEFORE)->pat; break; case BP_REPEAT: - if (p->args.repetitions.min == 0) + if (Match(p, BP_REPEAT)->min == 0) return p; - p = p->args.repetitions.repeat_pat; break; - case BP_CAPTURE: case BP_TAGGED: - p = p->args.capture.capture_pat; break; + p = Match(p, BP_REPEAT)->repeat_pat; break; + case BP_CAPTURE: + p = Match(p, BP_CAPTURE)->pat; break; + case BP_TAGGED: + p = Match(p, BP_TAGGED)->pat; break; case BP_CHAIN: { - pat_t *f = p->args.multiple.first; + auto chain = Match(p, BP_CHAIN); // If pattern is something like (|"foo"|), then use "foo" as the first thing to scan for - p = (f->type == BP_WORD_BOUNDARY || f->type == BP_START_OF_LINE) ? p->args.multiple.second : f; + p = (chain->first->type == BP_WORD_BOUNDARY || chain->first->type == BP_START_OF_LINE) ? chain->second : chain->first; break; } - case BP_MATCH: case BP_NOT_MATCH: - p = p->args.multiple.first; break; + case BP_MATCH: + p = Match(p, BP_MATCH)->pat; break; + case BP_NOT_MATCH: + p = Match(p, BP_NOT_MATCH)->pat; break; case BP_REPLACE: - p = p->args.replace.pat; break; + p = Match(p, BP_REPLACE)->pat; break; case BP_REF: { if (++derefs > 10) return p; // In case of left recursion pat_t *p2 = deref(ctx, p); @@ -331,7 +338,7 @@ static match_t *_next_match(match_ctx_t *ctx, const char *str, pat_t *pat, pat_t // we can just rely on the highly optimized memmem() implementation to skip // past areas where we know we won't find a match. if (!skip && first->type == BP_STRING && first->min_matchlen > 0 && !ctx->ignorecase) { - char *found = memmem(str, (size_t)(ctx->end - str), first->args.string, first->min_matchlen); + char *found = memmem(str, (size_t)(ctx->end - str), Match(first, BP_STRING)->string, first->min_matchlen); str = found ? found : ctx->end; } else if (!skip && str > ctx->start && (first->type == BP_START_OF_LINE || first->type == BP_END_OF_LINE)) { char *found = memchr(str, '\n', (size_t)(ctx->end - str)); @@ -363,7 +370,7 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) ctx2.cache = &(cache_t){0}; ctx2.parent_ctx = ctx; ctx2.defs = pat; - match_t *m = match(&ctx2, str, pat->args.def.meaning); + match_t *m = match(&ctx2, str, Match(pat, BP_DEFINITIONS)->meaning); cache_destroy(&ctx2); return m; } @@ -373,11 +380,12 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) // a special case, but if a pattern invokes itself at a later // point, it can be handled with normal recursion. // See: left-recursion.md for more details. - if (str == pat->args.leftrec->at) { - pat->args.leftrec->visited = true; - return clone_match(pat->args.leftrec->match); + auto leftrec = Match(pat, BP_LEFTRECURSION); + if (str == leftrec->at) { + leftrec->visited = true; + return clone_match(leftrec->match); } else { - return match(pat->args.leftrec->ctx, str, pat->args.leftrec->fallback); + return match(leftrec->ctx, str, leftrec->fallback); } } case BP_ANYCHAR: { @@ -407,18 +415,19 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) } case BP_STRING: { if (&str[pat->min_matchlen] > ctx->end) return NULL; - if (pat->min_matchlen > 0 && (ctx->ignorecase ? strncasecmp : strncmp)(str, pat->args.string, pat->min_matchlen) != 0) + if (pat->min_matchlen > 0 && (ctx->ignorecase ? strncasecmp : strncmp)(str, Match(pat, BP_STRING)->string, pat->min_matchlen) != 0) return NULL; return new_match(pat, str, str + pat->min_matchlen, NULL); } case BP_RANGE: { if (str >= ctx->end) return NULL; - if ((unsigned char)*str < pat->args.range.low || (unsigned char)*str > pat->args.range.high) + auto range = Match(pat, BP_RANGE); + if ((unsigned char)*str < range->low || (unsigned char)*str > range->high) return NULL; return new_match(pat, str, str+1, NULL); } case BP_NOT: { - match_t *m = match(ctx, str, pat->args.pat); + match_t *m = match(ctx, str, Match(pat, BP_NOT)->pat); if (m != NULL) { recycle_match(&m); return NULL; @@ -427,8 +436,8 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) } case BP_UPTO: case BP_UPTO_STRICT: { match_t *m = new_match(pat, str, str, NULL); - pat_t *target = deref(ctx, pat->args.multiple.first), - *skip = deref(ctx, pat->args.multiple.second); + pat_t *target = deref(ctx, pat->type == BP_UPTO ? Match(pat, BP_UPTO)->target : Match(pat, BP_UPTO_STRICT)->target), + *skip = deref(ctx, pat->type == BP_UPTO ? Match(pat, BP_UPTO)->skip : Match(pat, BP_UPTO_STRICT)->skip); if (!target && !skip) { while (str < ctx->end && *str != '\n') ++str; m->end = str; @@ -473,11 +482,11 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) case BP_REPEAT: { match_t *m = new_match(pat, str, str, NULL); size_t reps = 0; - ssize_t max = pat->args.repetitions.max; - pat_t *repeating = deref(ctx, pat->args.repetitions.repeat_pat); - pat_t *sep = deref(ctx, pat->args.repetitions.sep); + auto repeat = Match(pat, BP_REPEAT); + pat_t *repeating = deref(ctx, repeat->repeat_pat); + pat_t *sep = deref(ctx, repeat->sep); size_t child_cap = 0, nchildren = 0; - for (reps = 0; max == -1 || reps < (size_t)max; ++reps) { + for (reps = 0; repeat->max == -1 || reps < (size_t)repeat->max; ++reps) { const char *start = str; // Separator match_t *msep = NULL; @@ -501,10 +510,10 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) // of looping infinitely. if (msep) recycle_match(&msep); recycle_match(&mp); - if (pat->args.repetitions.max == -1) + if (repeat->max == -1) reps = ~(size_t)0; else - reps = (size_t)pat->args.repetitions.max; + reps = (size_t)repeat->max; break; } if (msep) { @@ -523,7 +532,7 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) str = mp->end; } - if (reps < (size_t)pat->args.repetitions.min) { + if (reps < (size_t)repeat->min) { recycle_match(&m); return NULL; } @@ -531,7 +540,7 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) return m; } case BP_AFTER: { - pat_t *back = deref(ctx, pat->args.pat); + pat_t *back = deref(ctx, Match(pat, BP_AFTER)->pat); if (!back) return NULL; // We only care about the region from the backtrack pos up to the @@ -564,36 +573,38 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) return NULL; } case BP_BEFORE: { - match_t *after = match(ctx, str, pat->args.pat); + match_t *after = match(ctx, str, Match(pat, BP_BEFORE)->pat); return after ? new_match(pat, str, str, MATCHES(after)) : NULL; } case BP_CAPTURE: case BP_TAGGED: { - if (!pat->args.pat) + pat_t *to_match = pat->type == BP_CAPTURE ? Match(pat, BP_CAPTURE)->pat : Match(pat, BP_TAGGED)->pat; + if (!to_match) return new_match(pat, str, str, NULL); - match_t *p = match(ctx, str, pat->args.pat); + match_t *p = match(ctx, str, to_match); return p ? new_match(pat, str, p->end, MATCHES(p)) : NULL; } case BP_OTHERWISE: { - match_t *m = match(ctx, str, pat->args.multiple.first); - return m ? m : match(ctx, str, pat->args.multiple.second); + match_t *m = match(ctx, str, Match(pat, BP_OTHERWISE)->first); + return m ? m : match(ctx, str, Match(pat, BP_OTHERWISE)->second); } case BP_CHAIN: { - if (pat->args.multiple.first->type == BP_DEFINITIONS) { + auto chain = Match(pat, BP_CHAIN); + if (chain->first->type == BP_DEFINITIONS) { match_ctx_t ctx2 = *ctx; ctx2.cache = &(cache_t){0}; ctx2.parent_ctx = ctx; - ctx2.defs = pat->args.multiple.first; - match_t *m = match(&ctx2, str, pat->args.multiple.second); + ctx2.defs = chain->first; + match_t *m = match(&ctx2, str, chain->second); cache_destroy(&ctx2); return m; } - match_t *m1 = match(ctx, str, pat->args.multiple.first); + match_t *m1 = match(ctx, str, chain->first); if (m1 == NULL) return NULL; match_t *m2; // Push backrefs and run matching, then cleanup - if (m1->pat->type == BP_CAPTURE && m1->pat->args.capture.name && m1->pat->args.capture.backreffable) { + if (m1->pat->type == BP_CAPTURE && Match(m1->pat, BP_CAPTURE)->name && Match(m1->pat, BP_CAPTURE)->backreffable) { // Temporarily add a rule that the backref name matches the // exact string of the original match (no replacements) pat_t *backref; @@ -618,20 +629,18 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) ctx2.defs = &(pat_t){ .type = BP_DEFINITIONS, .start = m1->pat->start, .end = m1->pat->end, - .args = { - .def = { - .name = m1->pat->args.capture.name, - .namelen = m1->pat->args.capture.namelen, - .meaning = backref, - } + .__tagged.BP_DEFINITIONS = { + .name = Match(m1->pat, BP_CAPTURE)->name, + .namelen = Match(m1->pat, BP_CAPTURE)->namelen, + .meaning = backref, }, }; - m2 = match(&ctx2, m1->end, pat->args.multiple.second); + m2 = match(&ctx2, m1->end, chain->second); if (!m2) // No need to keep the backref in memory if it didn't match delete_pat(&backref, false); cache_destroy(&ctx2); } else { - m2 = match(ctx, m1->end, pat->args.multiple.second); + m2 = match(ctx, m1->end, chain->second); } if (m2 == NULL) { @@ -642,7 +651,8 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) return new_match(pat, str, m2->end, MATCHES(m1, m2)); } case BP_MATCH: case BP_NOT_MATCH: { - match_t *m1 = match(ctx, str, pat->args.multiple.first); + pat_t *target = pat->type == BP_MATCH ? Match(pat, BP_MATCH)->pat : Match(pat, BP_NOT_MATCH)->pat; + match_t *m1 = match(ctx, str, target); if (m1 == NULL) return NULL; // ~ matches iff the text of matches @@ -651,21 +661,26 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) slice_ctx.cache = &(cache_t){0}; slice_ctx.start = m1->start; slice_ctx.end = m1->end; - match_t *m2 = _next_match(&slice_ctx, slice_ctx.start, pat->args.multiple.second, NULL); - if ((!m2 && pat->type == BP_MATCH) || (m2 && pat->type == BP_NOT_MATCH)) { - cache_destroy(&slice_ctx); + match_t *ret = NULL, *m2 = NULL; + if (pat->type == BP_MATCH) { + m2 = _next_match(&slice_ctx, slice_ctx.start, Match(pat, BP_MATCH)->must_match, NULL); + if (m2) ret = new_match(pat, m1->start, m1->end, MATCHES(m1, m2)); + } else { + m2 = _next_match(&slice_ctx, slice_ctx.start, Match(pat, BP_NOT_MATCH)->must_not_match, NULL); + if (!m2) ret = new_match(pat, m1->start, m1->end, MATCHES(m1)); + } + cache_destroy(&slice_ctx); + if (!ret) { if (m2) recycle_match(&m2); recycle_match(&m1); - return NULL; } - match_t *ret = new_match(pat, m1->start, m1->end, (pat->type == BP_MATCH) ? MATCHES(m1, m2) : MATCHES(m1)); - cache_destroy(&slice_ctx); return ret; } case BP_REPLACE: { match_t *p = NULL; - if (pat->args.replace.pat) { - p = match(ctx, str, pat->args.replace.pat); + auto replace = Match(pat, BP_REPLACE); + if (replace->pat) { + p = match(ctx, str, replace->pat); if (p == NULL) return NULL; } return new_match(pat, str, p ? p->end : str, MATCHES(p)); @@ -674,9 +689,10 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) if (has_cached_failure(ctx, str, pat)) return NULL; - pat_t *ref = lookup_ctx(ctx, pat->args.ref.name, pat->args.ref.len); + auto ref_pat = Match(pat, BP_REF); + pat_t *ref = lookup_ctx(ctx, ref_pat->name, ref_pat->len); if (ref == NULL) { - match_error(ctx, "Unknown pattern: '%.*s'", (int)pat->args.ref.len, pat->args.ref.name); + match_error(ctx, "Unknown pattern: '%.*s'", (int)ref_pat->len, ref_pat->name); return NULL; } @@ -687,7 +703,7 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) .type = BP_LEFTRECURSION, .start = ref->start, .end = ref->end, .min_matchlen = 0, .max_matchlen = -1, - .args.leftrec = &(leftrec_info_t){ + .__tagged.BP_LEFTRECURSION = { .match = NULL, .visited = false, .at = str, @@ -700,21 +716,19 @@ static match_t *match(match_ctx_t *ctx, const char *str, pat_t *pat) ctx2.defs = &(pat_t){ .type = BP_DEFINITIONS, .start = pat->start, .end = pat->end, - .args = { - .def = { - .name = pat->args.ref.name, - .namelen = pat->args.ref.len, - .meaning = &rec_op, - } + .__tagged.BP_DEFINITIONS = { + .name = ref_pat->name, + .namelen = ref_pat->len, + .meaning = &rec_op, }, }; match_t *m = match(&ctx2, str, ref); // If left recursion was involved, keep retrying while forward progress can be made: - if (m && rec_op.args.leftrec->visited) { + if (m && rec_op.__tagged.BP_LEFTRECURSION.visited) { while (1) { const char *prev = m->end; - rec_op.args.leftrec->match = m; + rec_op.__tagged.BP_LEFTRECURSION.match = m; ctx2.cache = &(cache_t){0}; match_t *m2 = match(&ctx2, str, ref); cache_destroy(&ctx2); @@ -897,7 +911,7 @@ bool next_match(match_t **m, const char *start, const char *end, pat_t *pat, pat __attribute__((nonnull)) static match_t *_get_numbered_capture(match_t *m, int *n) { - if ((m->pat->type == BP_CAPTURE && m->pat->args.capture.namelen == 0) || m->pat->type == BP_TAGGED) { + if ((m->pat->type == BP_CAPTURE && Match(m->pat, BP_CAPTURE)->namelen == 0) || m->pat->type == BP_TAGGED) { if (*n == 1) { return m; } else { @@ -925,7 +939,7 @@ match_t *get_numbered_capture(match_t *m, int n) { if (n <= 0) return m; if (m->pat->type == BP_TAGGED || m->pat->type == BP_CAPTURE) { - if (n == 1 && m->pat->type == BP_CAPTURE && m->pat->args.capture.namelen == 0) return m; + if (n == 1 && m->pat->type == BP_CAPTURE && Match(m->pat, BP_CAPTURE)->namelen == 0) return m; if (m->children) { for (int i = 0; m->children[i]; i++) { match_t *cap = _get_numbered_capture(m->children[i], &n); @@ -943,9 +957,9 @@ match_t *get_numbered_capture(match_t *m, int n) // match_t *_get_named_capture(match_t *m, const char *name, size_t namelen) { - if (m->pat->type == BP_CAPTURE && m->pat->args.capture.name - && m->pat->args.capture.namelen == namelen - && strncmp(m->pat->args.capture.name, name, m->pat->args.capture.namelen) == 0) + if (m->pat->type == BP_CAPTURE && Match(m->pat, BP_CAPTURE)->name + && Match(m->pat, BP_CAPTURE)->namelen == namelen + && strncmp(Match(m->pat, BP_CAPTURE)->name, name, Match(m->pat, BP_CAPTURE)->namelen) == 0) return m; if (m->pat->type == BP_TAGGED || m->pat->type == BP_CAPTURE) diff --git a/pattern.c b/pattern.c index 9eee45a..75b21b3 100644 --- a/pattern.c +++ b/pattern.c @@ -46,24 +46,17 @@ static inline void parse_err(const char *start, const char *end, const char *msg // Allocate a new pattern for this file (ensuring it will be automatically // freed when the file is freed) // -__attribute__((returns_nonnull, nonnull(2))) -static pat_t *new_pat(enum pattype_e type, const char *start, const char *end, size_t minlen, ssize_t maxlen) +pat_t *allocate_pat(pat_t pat) { static size_t next_pat_id = 1; - pat_t *pat = new(pat_t); - *pat = (pat_t){ - .home = &allocated_pats, - .next = allocated_pats, - .type = type, - .start = start, - .end = end, - .min_matchlen = minlen, - .max_matchlen = maxlen, - .id = next_pat_id++, - }; - if (allocated_pats) allocated_pats->home = &pat->next; - allocated_pats = pat; - return pat; + pat_t *allocated = new(pat_t); + *allocated = pat; + allocated->home = &allocated_pats; + allocated->next = allocated_pats; + allocated->id = next_pat_id++; + if (allocated_pats) allocated_pats->home = &allocated->next; + allocated_pats = allocated; + return allocated; } // @@ -75,12 +68,8 @@ static pat_t *new_range(const char *start, const char *end, size_t min, ssize_t size_t minlen = min*repeating->min_matchlen + (min > 0 ? min-1 : 0)*(sep ? sep->min_matchlen : 0); ssize_t maxlen = (max == -1 || UNBOUNDED(repeating) || (max != 0 && max != 1 && sep && UNBOUNDED(sep))) ? (ssize_t)-1 : max*repeating->max_matchlen + (ssize_t)(max > 0 ? min-1 : 0)*(ssize_t)(sep ? sep->min_matchlen : 0); - pat_t *range = new_pat(BP_REPEAT, start, end, minlen, maxlen); - range->args.repetitions.min = min; - range->args.repetitions.max = max; - range->args.repetitions.repeat_pat = repeating; - range->args.repetitions.sep = sep; - return range; + return Pattern(BP_REPEAT, start, end, minlen, maxlen, + .min=min, .max=max, .repeat_pat=repeating, .sep=sep); } // @@ -126,12 +115,9 @@ static pat_t *expand_replacements(pat_t *replace_pat, const char *end, bool allo replen = 0; } - pat_t *pat = new_pat(BP_REPLACE, replace_pat->start, str, - replace_pat->min_matchlen, replace_pat->max_matchlen); - pat->args.replace.pat = replace_pat; - pat->args.replace.text = repstr; - pat->args.replace.len = replen; - replace_pat = pat; + replace_pat = Pattern(BP_REPLACE, replace_pat->start, str, + replace_pat->min_matchlen, replace_pat->max_matchlen, + .pat=replace_pat, .text=repstr, .len=replen); } return replace_pat; } @@ -152,7 +138,7 @@ static pat_t *expand_choices(pat_t *first, const char *end, bool allow_nl) pat_t *second = bp_simplepattern(str, end); if (second) str = second->end; if (matchstr(&str, "=>", allow_nl, end)) - second = expand_replacements(second ? second : new_pat(BP_STRING, str-2, str-2, 0, 0), end, allow_nl); + second = expand_replacements(second ? second : Pattern(BP_STRING, str-2, str-2, 0, 0), end, allow_nl); if (!second) parse_err(str, str, "There should be a pattern here after a '/'"); second = expand_choices(second, end, allow_nl); @@ -169,18 +155,12 @@ pat_t *chain_together(pat_t *first, pat_t *second) if (second == NULL) return first; if (first->type == BP_DEFINITIONS && second->type == BP_DEFINITIONS) { - pat_t *chain = new_pat(BP_CHAIN, first->start, second->end, second->min_matchlen, second->max_matchlen); - chain->args.multiple.first = first; - chain->args.multiple.second = second; - return chain; + return Pattern(BP_CHAIN, first->start, second->end, second->min_matchlen, second->max_matchlen, .first=first, .second=second); } size_t minlen = first->min_matchlen + second->min_matchlen; ssize_t maxlen = (UNBOUNDED(first) || UNBOUNDED(second)) ? (ssize_t)-1 : first->max_matchlen + second->max_matchlen; - pat_t *chain = new_pat(BP_CHAIN, first->start, second->end, minlen, maxlen); - chain->args.multiple.first = first; - chain->args.multiple.second = second; - return chain; + return Pattern(BP_CHAIN, first->start, second->end, minlen, maxlen, .first=first, .second=second); } // @@ -194,10 +174,7 @@ pat_t *either_pat(pat_t *first, pat_t *second) size_t minlen = first->min_matchlen < second->min_matchlen ? first->min_matchlen : second->min_matchlen; ssize_t maxlen = (UNBOUNDED(first) || UNBOUNDED(second)) ? (ssize_t)-1 : (first->max_matchlen > second->max_matchlen ? first->max_matchlen : second->max_matchlen); - pat_t *either = new_pat(BP_OTHERWISE, first->start, second->end, minlen, maxlen); - either->args.multiple.first = first; - either->args.multiple.second = second; - return either; + return Pattern(BP_OTHERWISE, first->start, second->end, minlen, maxlen, .first=first, .second=second); } // @@ -215,21 +192,13 @@ static pat_t *_bp_definition(const char *start, const char *end) if (!def) parse_err(str, end, "Could not parse this definition."); str = def->end; (void)matchchar(&str, ';', false, end); // Optional semicolon - pat_t *ret = new_pat(BP_DEFINITIONS, start, str, 0, -1); - ret->args.def.name = start; - ret->args.def.namelen = namelen; if (is_tagged) { // `id:: foo` means define a rule named `id` that gives captures an `id` tag - pat_t *capture = new_pat(BP_TAGGED, def->start, def->end, def->min_matchlen, def->max_matchlen); - capture->args.capture.capture_pat = def; - capture->args.capture.name = start; - capture->args.capture.namelen = namelen; - def = capture; + def = Pattern(BP_TAGGED, def->start, def->end, def->min_matchlen, def->max_matchlen, + .pat=def, .name=start, .namelen=namelen); } - ret->args.def.meaning = def; - ret->args.def.next_def = _bp_definition(after_spaces(str, true, end), end); - if (ret->args.def.next_def) - ret->end = ret->args.def.next_def->end; - return ret; + pat_t *next_def = _bp_definition(after_spaces(str, true, end), end); + return Pattern(BP_DEFINITIONS, start, next_def ? next_def->end : str, 0, -1, + .name=start, .namelen=namelen, .meaning=def, .next_def=next_def); } // @@ -252,25 +221,30 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st pat_t *extra_arg = NULL; if (matchchar(&str, '%', false, end)) { extra_arg = bp_simplepattern(str, end); - if (!extra_arg) + if (extra_arg) + str = extra_arg->end; + else parse_err(str, str, "There should be a pattern to skip here after the '%'"); } else if (matchchar(&str, '=', false, end)) { extra_arg = bp_simplepattern(str, end); - if (!extra_arg) + if (extra_arg) + str = extra_arg->end; + else parse_err(str, str, "There should be a pattern here after the '='"); type = BP_UPTO_STRICT; } - pat_t *upto = new_pat(type, start, extra_arg ? extra_arg->end : str, 0, -1); - upto->args.multiple.second = extra_arg; + pat_t *target; if (inside_stringpattern) { - maybe_pat_t target = bp_stringpattern(upto->end, end); - upto->args.multiple.first = target.success ? target.value.pat : NULL; + maybe_pat_t maybe_target = bp_stringpattern(str, end); + target = maybe_target.success ? maybe_target.value.pat : NULL; } else { - upto->args.multiple.first = bp_simplepattern(upto->end, end); + target = bp_simplepattern(str, end); } - return upto; + return type == BP_UPTO ? + Pattern(BP_UPTO, start, str, 0, -1, .target=target, .skip=extra_arg) + : Pattern(BP_UPTO_STRICT, start, str, 0, -1, .target=target, .skip=extra_arg); } else { - return new_pat(BP_ANYCHAR, start, str, 1, UTF8_MAXCHARLEN); + return Pattern(BP_ANYCHAR, start, str, 1, UTF8_MAXCHARLEN); } } // Char literals @@ -295,14 +269,11 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st c2 = tmp; } str = next_char(c2_loc, end); - pat_t *pat = new_pat(BP_RANGE, start == c1_loc - 1 ? start : c1_loc, str, 1, 1); - pat->args.range.low = (unsigned char)c1; - pat->args.range.high = (unsigned char)c2; + pat_t *pat = Pattern(BP_RANGE, start == c1_loc - 1 ? start : c1_loc, str, 1, 1, .low=c1, .high=c2); all = either_pat(all, pat); } else { size_t len = (size_t)(str - c1_loc); - pat_t *pat = new_pat(BP_STRING, start, str, len, (ssize_t)len); - pat->args.string = c1_loc; + pat_t *pat = Pattern(BP_STRING, start, str, len, (ssize_t)len, .string=c1_loc); all = either_pat(all, pat); } } while (*str++ == ','); @@ -318,19 +289,19 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st do { // Comma-separated items: const char *itemstart = str-1; if (*str == 'N') { // \N (nodent) - all = either_pat(all, new_pat(BP_NODENT, itemstart, ++str, 1, -1)); + all = either_pat(all, Pattern(BP_NODENT, itemstart, ++str, 1, -1)); continue; } else if (*str == 'C') { // \C (current indent) - all = either_pat(all, new_pat(BP_CURDENT, itemstart, ++str, 1, -1)); + all = either_pat(all, Pattern(BP_CURDENT, itemstart, ++str, 1, -1)); continue; } else if (*str == 'i') { // \i (identifier char) - all = either_pat(all, new_pat(BP_ID_CONTINUE, itemstart, ++str, 1, -1)); + all = either_pat(all, Pattern(BP_ID_CONTINUE, itemstart, ++str, 1, -1)); continue; } else if (*str == 'I') { // \I (identifier char, not including numbers) - all = either_pat(all, new_pat(BP_ID_START, itemstart, ++str, 1, -1)); + all = either_pat(all, Pattern(BP_ID_START, itemstart, ++str, 1, -1)); continue; } else if (*str == 'b') { // \b word boundary - all = either_pat(all, new_pat(BP_WORD_BOUNDARY, itemstart, ++str, 0, 0)); + all = either_pat(all, Pattern(BP_WORD_BOUNDARY, itemstart, ++str, 0, 0)); continue; } @@ -350,9 +321,7 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st if (e_high < e_low) parse_err(start, str, "Escape ranges should be low-to-high, but this is high-to-low."); } - pat_t *esc = new_pat(BP_RANGE, start, str, 1, 1); - esc->args.range.low = e_low; - esc->args.range.high = e_high; + pat_t *esc = Pattern(BP_RANGE, start, str, 1, 1, .low=e_low, .high=e_high); all = either_pat(all, esc); } while (*str == ',' && str++ < end); @@ -360,7 +329,7 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st } // Word boundary case '|': { - return new_pat(BP_WORD_BOUNDARY, start, str, 0, 0); + return Pattern(BP_WORD_BOUNDARY, start, str, 0, 0); } // String literal case '"': case '\'': case '\002': case '{': { @@ -370,18 +339,13 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st str = next_char(str, end); size_t len = (size_t)(str - litstart); str = next_char(str, end); - - pat_t *pat = new_pat(BP_STRING, start, str, len, (ssize_t)len); - pat->args.string = litstart; - return pat; + return Pattern(BP_STRING, start, str, len, (ssize_t)len, .string=litstart); } // Not case '!': { pat_t *p = bp_simplepattern(str, end); if (!p) parse_err(str, str, "There should be a pattern after this '!'"); - pat_t *not = new_pat(BP_NOT, start, p->end, 0, 0); - not->args.pat = p; - return not; + return Pattern(BP_NOT, start, p->end, 0, 0, .pat=p); } // Number of repetitions: (- / - / + / "") case '0': case '1': case '2': case '3': case '4': case '5': @@ -421,21 +385,14 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st pat_t *behind = bp_simplepattern(str, end); if (!behind) parse_err(str, str, "There should be a pattern after this '<'"); - str = behind->end; - str = behind->end; - pat_t *pat = new_pat(BP_AFTER, start, str, 0, 0); - pat->args.pat = behind; - return pat; + return Pattern(BP_AFTER, start, behind->end, 0, 0, .pat=behind); } // Lookahead case '>': { pat_t *ahead = bp_simplepattern(str, end); if (!ahead) parse_err(str, str, "There should be a pattern after this '>'"); - str = ahead->end; - pat_t *pat = new_pat(BP_BEFORE, start, str, 0, 0); - pat->args.pat = ahead; - return pat; + return Pattern(BP_BEFORE, start, ahead->end, 0, 0, .pat=ahead); } // Parentheses case '(': { @@ -486,11 +443,8 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st p = bp_simplepattern(str, end); if (p) str = p->end; } - pat_t *tagged = new_pat(BP_TAGGED, start, str, p ? p->min_matchlen : 0, p ? p->max_matchlen : 0); - tagged->args.capture.capture_pat = p; - tagged->args.capture.name = name; - tagged->args.capture.namelen = namelen; - return tagged; + return Pattern(BP_TAGGED, start, str, p ? p->min_matchlen : 0, p ? p->max_matchlen : 0, + .pat=p, .name=name, .namelen=namelen); } const char *name = NULL; @@ -512,24 +466,20 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st if (!pat) parse_err(str, str, "There should be a valid pattern here to capture after the '@'"); - pat_t *capture = new_pat(BP_CAPTURE, start, pat->end, pat->min_matchlen, pat->max_matchlen); - capture->args.capture.capture_pat = pat; - capture->args.capture.name = name; - capture->args.capture.namelen = namelen; - capture->args.capture.backreffable = backreffable; - return capture; + return Pattern(BP_CAPTURE, start, pat->end, pat->min_matchlen, pat->max_matchlen, + .pat = pat, .name = name, .namelen = namelen, .backreffable = backreffable); } // Start of file/line case '^': { if (*str == '^') - return new_pat(BP_START_OF_FILE, start, ++str, 0, 0); - return new_pat(BP_START_OF_LINE, start, str, 0, 0); + return Pattern(BP_START_OF_FILE, start, ++str, 0, 0); + return Pattern(BP_START_OF_LINE, start, str, 0, 0); } // End of file/line: case '$': { if (*str == '$') - return new_pat(BP_END_OF_FILE, start, ++str, 0, 0); - return new_pat(BP_END_OF_LINE, start, str, 0, 0); + return Pattern(BP_END_OF_FILE, start, ++str, 0, 0); + return Pattern(BP_END_OF_LINE, start, str, 0, 0); } default: { pat_t *def = _bp_definition(start, end); @@ -538,10 +488,7 @@ static pat_t *_bp_simplepattern(const char *str, const char *end, bool inside_st if (!isalpha(c) && c != '_') return NULL; str = after_name(start, end); size_t namelen = (size_t)(str - start); - pat_t *ref = new_pat(BP_REF, start, str, 0, -1); - ref->args.ref.name = start; - ref->args.ref.len = namelen; - return ref; + return Pattern(BP_REF, start, str, 0, -1, .name=start, .len=namelen); } } } @@ -570,8 +517,7 @@ maybe_pat_t bp_stringpattern(const char *str, const char *end) // End of string size_t len = (size_t)(str - start); if (len > 0) { - pat_t *str_chunk = new_pat(BP_STRING, start, str, len, (ssize_t)len); - str_chunk->args.string = start; + pat_t *str_chunk = Pattern(BP_STRING, start, str, len, (ssize_t)len, .string=start); ret = chain_together(ret, str_chunk); } if (interp) { @@ -581,7 +527,7 @@ maybe_pat_t bp_stringpattern(const char *str, const char *end) (void)matchchar(&str, ';', false, end); } } - if (!ret) ret = new_pat(BP_STRING, str, str, 0, 0); + if (!ret) ret = Pattern(BP_STRING, str, str, 0, 0); __END_TRY_PATTERN__ return (maybe_pat_t){.success = true, .value.pat = ret}; } @@ -610,9 +556,9 @@ static pat_t *bp_simplepattern(const char *str, const char *end) if (!second) parse_err(str, str, "There should be a valid pattern here"); - pat = new_pat(type, start, second->end, first->min_matchlen, first->max_matchlen); - pat->args.multiple.first = first; - pat->args.multiple.second = second; + pat = type == BP_MATCH ? + Pattern(BP_MATCH, start, second->end, first->min_matchlen, first->max_matchlen, .pat=first, .must_match=second) + : Pattern(BP_NOT_MATCH, start, second->end, first->min_matchlen, first->max_matchlen, .pat=first, .must_not_match=second); str = pat->end; } @@ -625,8 +571,6 @@ static pat_t *bp_simplepattern(const char *str, const char *end) // maybe_pat_t bp_replacement(pat_t *replacepat, const char *replacement, const char *end) { - pat_t *pat = new_pat(BP_REPLACE, replacepat->start, replacepat->end, replacepat->min_matchlen, replacepat->max_matchlen); - pat->args.replace.pat = replacepat; const char *p = replacement; if (!end) end = replacement + strlen(replacement); __TRY_PATTERN__ @@ -641,8 +585,8 @@ maybe_pat_t bp_replacement(pat_t *replacepat, const char *replacement, const cha size_t rlen = (size_t)(p-replacement); char *rcpy = new(char[rlen + 1]); memcpy(rcpy, replacement, rlen); - pat->args.replace.text = rcpy; - pat->args.replace.len = rlen; + pat_t *pat = Pattern(BP_REPLACE, replacepat->start, replacepat->end, replacepat->min_matchlen, replacepat->max_matchlen, + .pat=replacepat, .text=rcpy, .len=rlen); return (maybe_pat_t){.success = true, .value.pat = pat}; } @@ -652,7 +596,7 @@ static pat_t *bp_pattern_nl(const char *str, const char *end, bool allow_nl) pat_t *pat = bp_simplepattern(str, end); if (pat != NULL) pat = expand_choices(pat, end, allow_nl); if (matchstr(&str, "=>", allow_nl, end)) - pat = expand_replacements(pat ? pat : new_pat(BP_STRING, str-2, str-2, 0, 0), end, allow_nl); + pat = expand_replacements(pat ? pat : Pattern(BP_STRING, str-2, str-2, 0, 0), end, allow_nl); return pat; } @@ -661,9 +605,7 @@ static pat_t *bp_pattern_nl(const char *str, const char *end, bool allow_nl) // pat_t *bp_raw_literal(const char *str, size_t len) { - pat_t *lit = new_pat(BP_STRING, str, &str[len], len, (ssize_t)len); - lit->args.string = str; - return lit; + return Pattern(BP_STRING, str, &str[len], len, (ssize_t)len, .string=str); } // @@ -698,36 +640,30 @@ void delete_pat(pat_t **at_pat, bool recursive) pat_t *pat = *at_pat; if (!pat) return; +#define T(tag, ...) case tag: { auto _data = Match(pat, tag); __VA_ARGS__; break; } +#define F(field) delete_pat(&_data->field, true) if (recursive) { switch (pat->type) { - case BP_DEFINITIONS: - delete_pat(&pat->args.def.meaning, true); - delete_pat(&pat->args.def.next_def, true); - break; - case BP_REPEAT: - delete_pat(&pat->args.repetitions.sep, true); - delete_pat(&pat->args.repetitions.repeat_pat, true); - break; - case BP_CHAIN: case BP_UPTO: case BP_UPTO_STRICT: - case BP_OTHERWISE: case BP_NOT_MATCH: case BP_MATCH: - delete_pat(&pat->args.multiple.first, true); - delete_pat(&pat->args.multiple.second, true); - break; - case BP_REPLACE: - delete_pat(&pat->args.replace.pat, true); - break; - case BP_CAPTURE: case BP_TAGGED: - delete_pat(&pat->args.capture.capture_pat, true); - break; - case BP_NOT: case BP_AFTER: case BP_BEFORE: - delete_pat(&pat->args.pat, true); - break; - case BP_LEFTRECURSION: - delete_pat(&pat->args.leftrec->fallback, true); - break; + T(BP_DEFINITIONS, F(meaning), F(next_def)) + T(BP_REPEAT, F(sep), F(repeat_pat)) + T(BP_CHAIN, F(first), F(second)) + T(BP_UPTO, F(target), F(skip)) + T(BP_UPTO_STRICT, F(target), F(skip)) + T(BP_OTHERWISE, F(first), F(second)) + T(BP_MATCH, F(pat), F(must_match)) + T(BP_NOT_MATCH, F(pat), F(must_not_match)) + T(BP_REPLACE, F(pat)) + T(BP_CAPTURE, F(pat)) + T(BP_TAGGED, F(pat)) + T(BP_NOT, F(pat)) + T(BP_AFTER, F(pat)) + T(BP_BEFORE, F(pat)) + T(BP_LEFTRECURSION, F(fallback)) default: break; } } +#undef F +#undef T if (pat->home) *(pat->home) = pat->next; if (pat->next) pat->next->home = pat->home; diff --git a/pattern.h b/pattern.h index 0543244..32a2311 100644 --- a/pattern.h +++ b/pattern.h @@ -6,11 +6,19 @@ #include #include #include +#include -#define UNBOUNDED(pat) ((pat)->max_matchlen == -1) +#ifndef auto +#define auto __auto_type +#endif +#define UNBOUNDED(pat) ((pat)->max_matchlen == -1) +#define Match(x, _tag) ((x)->type == _tag ? &(x)->__tagged._tag : (errx(1, __FILE__ ":%d This was supposed to be a " # _tag "\n", __LINE__), &(x)->__tagged._tag)) +#define Pattern(_tag, _start, _end, _min, _max, ...) allocate_pat((pat_t){.type=_tag, .start=_start, .end=_end, \ + .min_matchlen=_min, .max_matchlen=_max, .__tagged._tag={__VA_ARGS__}}) // BP virtual machine pattern types enum pattype_e { + BP_ERROR = 0, BP_ANYCHAR = 1, BP_ID_START = 2, BP_ID_CONTINUE = 3, @@ -53,45 +61,73 @@ typedef struct pat_s { uint32_t min_matchlen; int32_t max_matchlen; // -1 means unbounded length union { - const char *string; - struct { - const char *name; - uint32_t len; - } ref; - struct { - const char *name; - uint32_t namelen; - struct pat_s *meaning, *next_def; - } def; struct { - unsigned char low, high; - } range; + const char *start, *end, *msg; + } BP_ERROR; + struct {} BP_ANYCHAR; + struct {} BP_ID_START; + struct {} BP_ID_CONTINUE; + struct {const char *string;} BP_STRING; + struct {unsigned char low, high; } BP_RANGE; + struct {struct pat_s *pat;} BP_NOT; + struct {struct pat_s *target, *skip;} BP_UPTO; + struct {struct pat_s *target, *skip;} BP_UPTO_STRICT; struct { uint32_t min; int32_t max; struct pat_s *sep, *repeat_pat; - } repetitions; - // TODO: use a linked list instead of a binary tree + } BP_REPEAT; + struct {struct pat_s *pat;} BP_BEFORE; + struct {struct pat_s *pat;} BP_AFTER; + struct { + struct pat_s *pat; + const char *name; + uint16_t namelen; + bool backreffable; + } BP_CAPTURE; + struct { + struct pat_s *first, *second; + } BP_OTHERWISE; struct { struct pat_s *first, *second; - } multiple; + } BP_CHAIN; + struct {struct pat_s *pat, *must_match;} BP_MATCH; + struct {struct pat_s *pat, *must_not_match;} BP_NOT_MATCH; struct { struct pat_s *pat; const char *text; uint32_t len; - } replace; + } BP_REPLACE; struct { - struct pat_s *capture_pat; + const char *name; + uint32_t len; + } BP_REF; + struct {} BP_NODENT; + struct {} BP_CURDENT; + struct {} BP_START_OF_FILE; + struct {} BP_START_OF_LINE; + struct {} BP_END_OF_FILE; + struct {} BP_END_OF_LINE; + struct {} BP_WORD_BOUNDARY; + struct { + const char *name; + uint32_t namelen; + struct pat_s *meaning, *next_def; + } BP_DEFINITIONS; + struct { + struct pat_s *pat; const char *name; uint16_t namelen; bool backreffable; - } capture; - struct leftrec_info_s *leftrec; + } BP_TAGGED; struct { - const char *start, *end, *msg; - } error; - struct pat_s *pat; - } args; + struct match_s *match; + const char *at; + struct pat_s *fallback; + void *ctx; + bool visited; + } BP_LEFTRECURSION; + } __tagged; } pat_t; typedef struct leftrec_info_s { @@ -112,6 +148,8 @@ typedef struct { } value; } maybe_pat_t; +__attribute__((returns_nonnull)) +pat_t *allocate_pat(pat_t pat); __attribute__((nonnull, returns_nonnull)) pat_t *bp_raw_literal(const char *str, size_t len); __attribute__((nonnull(1))) diff --git a/printmatch.c b/printmatch.c index c079b23..2cbd511 100644 --- a/printmatch.c +++ b/printmatch.c @@ -200,8 +200,9 @@ int fprint_match(FILE *out, const char *file_start, match_t *m, print_options_t { int printed = 0; if (m->pat->type == BP_REPLACE) { - const char *text = m->pat->args.replace.text; - const char *end = &text[m->pat->args.replace.len]; + auto rep = Match(m->pat, BP_REPLACE); + const char *text = rep->text; + const char *end = &text[rep->len]; if (opts && opts->replace_color) printed += fprintf(out, "%s", opts->replace_color); // TODO: clean up the line numbering code -- cgit v1.2.3