pattern.c

(724 lines)
   1 //
   2 // pattern.c - Compile strings into BP pattern objects that can be matched against.
   3 //
   4 #include <ctype.h>
   5 #include <err.h>
   6 #include <setjmp.h>
   7 #include <stdbool.h>
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include <unistd.h>
  12 
  13 #include "pattern.h"
  14 #include "utf8.h"
  15 #include "utils.h"
  16 
  17 #define Pattern(_tag, _start, _end, _min, _max, ...)                                                                   \
  18     allocate_pat((bp_pat_t){.type = _tag,                                                                              \
  19                             .start = _start,                                                                           \
  20                             .end = _end,                                                                               \
  21                             .min_matchlen = _min,                                                                      \
  22                             .max_matchlen = _max,                                                                      \
  23                             .__tagged._tag = {__VA_ARGS__}})
  24 #define UNBOUNDED(pat) ((pat)->max_matchlen == -1)
  25 
  26 static bp_pat_t *allocated_pats = NULL;
  27 
  28 __attribute__((nonnull)) static bp_pat_t *bp_pattern_nl(const char *str, const char *end, bool allow_nl);
  29 __attribute__((nonnull)) static bp_pat_t *bp_simplepattern(const char *str, const char *end);
  30 
  31 // For error-handling purposes, use setjmp/longjmp to break out of deeply
  32 // recursive function calls when a parse error occurs.
  33 bool is_in_try_catch = false;
  34 static jmp_buf err_jmp;
  35 static maybe_pat_t parse_error = {.success = false};
  36 
  37 #define __TRY_PATTERN__                                                                                                \
  38     bool was_in_try_catch = is_in_try_catch;                                                                           \
  39     if (!is_in_try_catch) {                                                                                            \
  40         is_in_try_catch = true;                                                                                        \
  41         if (setjmp(err_jmp)) return parse_error;                                                                       \
  42     }
  43 #define __END_TRY_PATTERN__                                                                                            \
  44     if (!was_in_try_catch) is_in_try_catch = false;
  45 
  46 static inline void parse_err(const char *start, const char *end, const char *msg) {
  47     if (!is_in_try_catch) {
  48         fprintf(stderr, "Parse error: %s\n%.*s\n", msg, (int)(end - start), start);
  49         exit(1);
  50     }
  51     parse_error.value.error.start = start;
  52     parse_error.value.error.end = end;
  53     parse_error.value.error.msg = msg;
  54     longjmp(err_jmp, 1);
  55 }
  56 
  57 //
  58 // Allocate a new pattern for this file (ensuring it will be automatically
  59 // freed when the file is freed)
  60 //
  61 public
  62 bp_pat_t *allocate_pat(bp_pat_t pat) {
  63     static size_t next_pat_id = 1;
  64     bp_pat_t *allocated = new (bp_pat_t);
  65     *allocated = pat;
  66     allocated->home = &allocated_pats;
  67     allocated->next = allocated_pats;
  68     allocated->id = next_pat_id++;
  69     if (allocated_pats) allocated_pats->home = &allocated->next;
  70     allocated_pats = allocated;
  71     return allocated;
  72 }
  73 
  74 //
  75 // Helper function to initialize a range object.
  76 //
  77 __attribute__((nonnull(1, 2, 5))) static bp_pat_t *new_range(const char *start, const char *end, size_t min,
  78                                                              ssize_t max, bp_pat_t *repeating, bp_pat_t *sep) {
  79     size_t minlen = min * repeating->min_matchlen + (min > 0 ? min - 1 : 0) * (sep ? sep->min_matchlen : 0);
  80     ssize_t maxlen =
  81         (max == -1 || UNBOUNDED(repeating) || (max != 0 && max != 1 && sep && UNBOUNDED(sep)))
  82             ? (ssize_t)-1
  83             : max * repeating->max_matchlen + (ssize_t)(max > 0 ? min - 1 : 0) * (ssize_t)(sep ? sep->min_matchlen : 0);
  84     return Pattern(BP_REPEAT, start, end, minlen, maxlen, .min = min, .max = max, .repeat_pat = repeating, .sep = sep);
  85 }
  86 
  87 //
  88 // Take a pattern and expand it into a chain of patterns if it's followed by
  89 // any patterns (e.g. "`x `y"), otherwise return the original input.
  90 //
  91 __attribute__((nonnull)) static bp_pat_t *expand_chain(bp_pat_t *first, const char *end, bool allow_nl) {
  92     const char *str = after_spaces(first->end, allow_nl, end);
  93     bp_pat_t *second = bp_simplepattern(str, end);
  94     if (second == NULL) return first;
  95     second = expand_chain(second, end, allow_nl);
  96     return chain_together(first, second);
  97 }
  98 
  99 //
 100 // Match trailing => replacements (with optional pattern beforehand)
 101 //
 102 __attribute__((nonnull)) static bp_pat_t *expand_replacements(bp_pat_t *replace_pat, const char *end, bool allow_nl) {
 103     const char *str = replace_pat->end;
 104     while (matchstr(&str, "=>", allow_nl, end)) {
 105         const char *repstr;
 106         size_t replen;
 107         if (matchchar(&str, '"', allow_nl, end) || matchchar(&str, '\'', allow_nl, end)
 108             || matchchar(&str, '}', allow_nl, end) || matchchar(&str, '\002', allow_nl, end)) {
 109             char closequote = str[-1] == '}' ? '{' : (str[-1] == '\002' ? '\003' : str[-1]);
 110             repstr = str;
 111             for (; str < end && *str != closequote; str = next_char(str, end)) {
 112                 if (*str == '\\') {
 113                     if (!str[1] || str[1] == '\n')
 114                         parse_err(str, str + 1, "There should be an escape sequence after this backslash.");
 115                     str = next_char(str, end);
 116                 }
 117             }
 118             replen = (size_t)(str - repstr);
 119             (void)matchchar(&str, closequote, true, end);
 120         } else {
 121             repstr = "";
 122             replen = 0;
 123         }
 124 
 125         replace_pat = Pattern(BP_REPLACE, replace_pat->start, str, replace_pat->min_matchlen, replace_pat->max_matchlen,
 126                               .pat = replace_pat, .text = repstr, .len = replen);
 127     }
 128     return replace_pat;
 129 }
 130 
 131 //
 132 // Take a pattern and parse any "=>" replacements and then expand it into a
 133 // chain of choices if it's followed by any "/"-separated patterns (e.g.
 134 // "`x/`y"), otherwise return the original input.
 135 //
 136 __attribute__((nonnull)) static bp_pat_t *expand_choices(bp_pat_t *first, const char *end, bool allow_nl) {
 137     first = expand_chain(first, end, allow_nl);
 138     first = expand_replacements(first, end, allow_nl);
 139     const char *str = first->end;
 140     if (!matchchar(&str, '/', allow_nl, end)) return first;
 141     str = after_spaces(str, allow_nl, end);
 142     bp_pat_t *second = bp_simplepattern(str, end);
 143     if (second) str = second->end;
 144     if (matchstr(&str, "=>", allow_nl, end))
 145         second = expand_replacements(second ? second : Pattern(BP_STRING, str - 2, str - 2, 0, 0), end, allow_nl);
 146     if (!second) parse_err(str, str, "There should be a pattern here after a '/'");
 147     second = expand_choices(second, end, allow_nl);
 148     return either_pat(first, second);
 149 }
 150 
 151 //
 152 // Given two patterns, return a new pattern for the first pattern followed by
 153 // the second. If either pattern is NULL, return the other.
 154 //
 155 public
 156 bp_pat_t *chain_together(bp_pat_t *first, bp_pat_t *second) {
 157     if (first == NULL) return second;
 158     if (second == NULL) return first;
 159 
 160     if (first->type == BP_STRING && first->max_matchlen == 0) return second;
 161     if (second->type == BP_STRING && second->max_matchlen == 0) return first;
 162 
 163     if (first->type == BP_DEFINITIONS && second->type == BP_DEFINITIONS) {
 164         return Pattern(BP_CHAIN, first->start, second->end, second->min_matchlen, second->max_matchlen, .first = first,
 165                        .second = second);
 166     }
 167 
 168     size_t minlen = first->min_matchlen + second->min_matchlen;
 169     ssize_t maxlen = (UNBOUNDED(first) || UNBOUNDED(second)) ? (ssize_t)-1 : first->max_matchlen + second->max_matchlen;
 170     return Pattern(BP_CHAIN, first->start, second->end, minlen, maxlen, .first = first, .second = second);
 171 }
 172 
 173 //
 174 // Given two patterns, return a new pattern for matching either the first
 175 // pattern or the second. If either pattern is NULL, return the other.
 176 //
 177 public
 178 bp_pat_t *either_pat(bp_pat_t *first, bp_pat_t *second) {
 179     if (first == NULL) return second;
 180     if (second == NULL) return first;
 181     size_t minlen = first->min_matchlen < second->min_matchlen ? first->min_matchlen : second->min_matchlen;
 182     ssize_t maxlen = (UNBOUNDED(first) || UNBOUNDED(second))
 183                          ? (ssize_t)-1
 184                          : (first->max_matchlen > second->max_matchlen ? first->max_matchlen : second->max_matchlen);
 185     return Pattern(BP_OTHERWISE, first->start, second->end, minlen, maxlen, .first = first, .second = second);
 186 }
 187 
 188 //
 189 // Parse a definition
 190 //
 191 __attribute__((nonnull)) static bp_pat_t *_bp_definition(const char *start, const char *end) {
 192     if (start >= end || !(isalpha(*start) || *start == '_')) return NULL;
 193     const char *str = after_name(start, end);
 194     size_t namelen = (size_t)(str - start);
 195     if (!matchchar(&str, ':', false, end)) return NULL;
 196     bool is_tagged = str < end && *str == ':' && matchchar(&str, ':', false, end);
 197     bp_pat_t *def = bp_pattern_nl(str, end, false);
 198     if (!def) parse_err(str, end, "Could not parse this definition.");
 199     str = def->end;
 200     (void)matchchar(&str, ';', false, end); // Optional semicolon
 201     if (is_tagged) { // `id:: foo` means define a rule named `id` that gives captures an `id` tag
 202         def = Pattern(BP_TAGGED, def->start, def->end, def->min_matchlen, def->max_matchlen, .pat = def, .name = start,
 203                       .namelen = namelen);
 204     }
 205     bp_pat_t *next_def = _bp_definition(after_spaces(str, true, end), end);
 206     return Pattern(BP_DEFINITIONS, start, next_def ? next_def->end : str, 0, -1, .name = start, .namelen = namelen,
 207                    .meaning = def, .next_def = next_def);
 208 }
 209 
 210 //
 211 // Compile a string of BP code into a BP pattern object.
 212 //
 213 __attribute__((nonnull)) static bp_pat_t *_bp_simplepattern(const char *str, const char *end,
 214                                                             bool inside_stringpattern) {
 215     str = after_spaces(str, false, end);
 216     if (!*str) return NULL;
 217     const char *start = str;
 218     char c = *str;
 219     str = next_char(str, end);
 220     switch (c) {
 221     // Any char (dot)
 222     case '.': {
 223         // As a special case, 3+ dots is parsed as a series of "any char" followed by a single "upto"
 224         // In other words, `...foo` parses as `(.)(..foo)` instead of `(..(.)) (foo)`
 225         // This is so that `...` can mean "at least one character upto" instead of "upto any character",
 226         // which is tautologically the same as matching any single character.
 227         if (*str == '.' && (str + 1 >= end || str[1] != '.')) { // ".."
 228             str = next_char(str, end);
 229             enum bp_pattype_e type = BP_UPTO;
 230             bp_pat_t *extra_arg = NULL;
 231             if (matchchar(&str, '%', false, end)) {
 232                 extra_arg = bp_simplepattern(str, end);
 233                 if (extra_arg) str = extra_arg->end;
 234                 else parse_err(str, str, "There should be a pattern to skip here after the '%'");
 235             } else if (matchchar(&str, '=', false, end)) {
 236                 extra_arg = bp_simplepattern(str, end);
 237                 if (extra_arg) str = extra_arg->end;
 238                 else parse_err(str, str, "There should be a pattern here after the '='");
 239                 type = BP_UPTO_STRICT;
 240             }
 241             bp_pat_t *target;
 242             if (inside_stringpattern) {
 243                 target = NULL;
 244             } else {
 245                 target = bp_simplepattern(str, end);
 246                 // Bugfix: `echo "foo@" | bp '{..}{"@"}'` should be parsed as `.."@"`
 247                 // not '(.."") "@"'
 248                 while (target && target->type == BP_STRING && target->max_matchlen == 0)
 249                     target = bp_simplepattern(target->end, end);
 250             }
 251             return type == BP_UPTO ? Pattern(BP_UPTO, start, str, 0, -1, .target = target, .skip = extra_arg)
 252                                    : Pattern(BP_UPTO_STRICT, start, str, 0, -1, .target = target, .skip = extra_arg);
 253         } else {
 254             return Pattern(BP_ANYCHAR, start, str, 1, UTF8_MAXCHARLEN);
 255         }
 256     }
 257     // Char literals
 258     case '`': {
 259         bp_pat_t *all = NULL;
 260         do { // Comma-separated items:
 261             if (str >= end || !*str || *str == '\n')
 262                 parse_err(str, str, "There should be a character here after the '`'");
 263 
 264             const char *c1_loc = str;
 265             str = next_char(c1_loc, end);
 266             if (*str == '-') { // Range
 267                 const char *c2_loc = ++str;
 268                 if (next_char(c1_loc, end) > c1_loc + 1 || next_char(c2_loc, end) > c2_loc + 1)
 269                     parse_err(start, next_char(c2_loc, end), "Sorry, UTF-8 character ranges are not yet supported.");
 270                 char c1 = *c1_loc, c2 = *c2_loc;
 271                 if (!c2 || c2 == '\n')
 272                     parse_err(str, str, "There should be a character here to complete the character range.");
 273                 if (c1 > c2) { // Swap order
 274                     char tmp = c1;
 275                     c1 = c2;
 276                     c2 = tmp;
 277                 }
 278                 str = next_char(c2_loc, end);
 279                 bp_pat_t *pat =
 280                     Pattern(BP_RANGE, start == c1_loc - 1 ? start : c1_loc, str, 1, 1, .low = c1, .high = c2);
 281                 all = either_pat(all, pat);
 282             } else {
 283                 size_t len = (size_t)(str - c1_loc);
 284                 bp_pat_t *pat = Pattern(BP_STRING, start, str, len, (ssize_t)len, .string = strndup(c1_loc, len));
 285                 all = either_pat(all, pat);
 286             }
 287         } while (*str++ == ',');
 288 
 289         return all;
 290     }
 291     // Escapes
 292     case '\\': {
 293         if (!*str || *str == '\n') parse_err(str, str, "There should be an escape sequence here after this backslash.");
 294 
 295         bp_pat_t *all = NULL;
 296         do { // Comma-separated items:
 297             const char *itemstart = str - 1;
 298             if (*str == 'N') { // \N (nodent)
 299                 all = either_pat(all, Pattern(BP_NODENT, itemstart, ++str, 1, -1));
 300                 continue;
 301             } else if (*str == 'C') { // \C (current indent)
 302                 all = either_pat(all, Pattern(BP_CURDENT, itemstart, ++str, 1, -1));
 303                 continue;
 304             } else if (*str == 'i') { // \i (identifier char)
 305                 all = either_pat(all, Pattern(BP_ID_CONTINUE, itemstart, ++str, 1, -1));
 306                 continue;
 307             } else if (*str == 'I') { // \I (identifier char, not including numbers)
 308                 all = either_pat(all, Pattern(BP_ID_START, itemstart, ++str, 1, -1));
 309                 continue;
 310             } else if (*str == 'b') { // \b word boundary
 311                 all = either_pat(all, Pattern(BP_WORD_BOUNDARY, itemstart, ++str, 0, 0));
 312                 continue;
 313             }
 314 
 315             const char *opstart = str;
 316             unsigned char e_low = (unsigned char)unescapechar(str, &str, end);
 317             if (str == opstart) parse_err(start, str + 1, "This isn't a valid escape sequence.");
 318             unsigned char e_high = e_low;
 319             if (*str == '-') { // Escape range (e.g. \x00-\xFF)
 320                 ++str;
 321                 if (next_char(str, end) != str + 1)
 322                     parse_err(start, next_char(str, end), "Sorry, UTF8 escape sequences are not supported in ranges.");
 323                 const char *seqstart = str;
 324                 e_high = (unsigned char)unescapechar(str, &str, end);
 325                 if (str == seqstart) parse_err(seqstart, str + 1, "This value isn't a valid escape sequence");
 326                 if (e_high < e_low)
 327                     parse_err(start, str, "Escape ranges should be low-to-high, but this is high-to-low.");
 328             }
 329             bp_pat_t *esc = Pattern(BP_RANGE, start, str, 1, 1, .low = e_low, .high = e_high);
 330             all = either_pat(all, esc);
 331         } while (*str == ',' && str++ < end);
 332 
 333         return all;
 334     }
 335     // Word boundary
 336     case '|': {
 337         return Pattern(BP_WORD_BOUNDARY, start, str, 0, 0);
 338     }
 339     // String literal
 340     case '"':
 341     case '\'':
 342     case '\002':
 343     case '}': {
 344         char endquote = c == '\002' ? '\003' : (c == '}' ? '{' : c);
 345         char *litstart = (char *)str;
 346         while (str < end && *str != endquote)
 347             str = next_char(str, end);
 348         size_t len = (size_t)(str - litstart);
 349         str = next_char(str, end);
 350         if (c == '}') ++start; // Don't include the "}" in the pattern source range
 351         return Pattern(BP_STRING, start, str, len, (ssize_t)len, .string = strndup(litstart, len));
 352     }
 353     // Not <pat>
 354     case '!': {
 355         bp_pat_t *p = bp_simplepattern(str, end);
 356         if (!p) parse_err(str, str, "There should be a pattern after this '!'");
 357         return Pattern(BP_NOT, start, p->end, 0, 0, .pat = p);
 358     }
 359     // Number of repetitions: <N>(-<N> / - / + / "")
 360     case '0':
 361     case '1':
 362     case '2':
 363     case '3':
 364     case '4':
 365     case '5':
 366     case '6':
 367     case '7':
 368     case '8':
 369     case '9': {
 370         size_t min = 0;
 371         ssize_t max = -1;
 372         --str;
 373         long n1 = strtol(str, (char **)&str, 10);
 374         if (matchchar(&str, '-', false, end)) {
 375             str = after_spaces(str, false, end);
 376             const char *numstart = str;
 377             long n2 = strtol(str, (char **)&str, 10);
 378             if (str == numstart) min = 0, max = (ssize_t)n1;
 379             else min = (size_t)n1, max = (ssize_t)n2;
 380         } else if (matchchar(&str, '+', false, end)) {
 381             min = (size_t)n1, max = -1;
 382         } else {
 383             min = (size_t)n1, max = (ssize_t)n1;
 384         }
 385         bp_pat_t *repeating = bp_simplepattern(str, end);
 386         if (!repeating) parse_err(str, str, "There should be a pattern after this repetition count.");
 387         str = repeating->end;
 388         bp_pat_t *sep = NULL;
 389         if (matchchar(&str, '%', false, end)) {
 390             sep = bp_simplepattern(str, end);
 391             if (!sep) parse_err(str, str, "There should be a separator pattern after this '%%'");
 392             str = sep->end;
 393         } else {
 394             str = repeating->end;
 395         }
 396         return new_range(start, str, min, max, repeating, sep);
 397     }
 398     // Lookbehind
 399     case '<': {
 400         bp_pat_t *behind = bp_simplepattern(str, end);
 401         if (!behind) parse_err(str, str, "There should be a pattern after this '<'");
 402         return Pattern(BP_AFTER, start, behind->end, 0, 0, .pat = behind);
 403     }
 404     // Lookahead
 405     case '>': {
 406         bp_pat_t *ahead = bp_simplepattern(str, end);
 407         if (!ahead) parse_err(str, str, "There should be a pattern after this '>'");
 408         return Pattern(BP_BEFORE, start, ahead->end, 0, 0, .pat = ahead);
 409     }
 410     // Parentheses
 411     case '(': {
 412         bp_pat_t *pat = bp_pattern_nl(str, end, true);
 413         if (!pat) parse_err(str, str, "There should be a valid pattern after this parenthesis.");
 414         str = pat->end;
 415         if (!matchchar(&str, ')', true, end)) parse_err(str, str, "Missing paren: )");
 416         pat->start = start;
 417         pat->end = str;
 418         return pat;
 419     }
 420     // Square brackets
 421     case '[': {
 422         bp_pat_t *maybe = bp_pattern_nl(str, end, true);
 423         if (!maybe) parse_err(str, str, "There should be a valid pattern after this square bracket.");
 424         str = maybe->end;
 425         (void)matchchar(&str, ']', true, end);
 426         return new_range(start, str, 0, 1, maybe, NULL);
 427     }
 428     // Repeating
 429     case '*':
 430     case '+': {
 431         size_t min = (size_t)(c == '*' ? 0 : 1);
 432         bp_pat_t *repeating = bp_simplepattern(str, end);
 433         if (!repeating) parse_err(str, str, "There should be a valid pattern to repeat here");
 434         str = repeating->end;
 435         bp_pat_t *sep = NULL;
 436         if (matchchar(&str, '%', false, end)) {
 437             sep = bp_simplepattern(str, end);
 438             if (!sep) parse_err(str, str, "There should be a separator pattern after the '%%' here.");
 439             str = sep->end;
 440         }
 441         return new_range(start, str, min, -1, repeating, sep);
 442     }
 443     // Capture
 444     case '@': {
 445         if (matchchar(&str, ':', false, end)) { // Tagged capture @:Foo=pat
 446             const char *name = str;
 447             str = after_name(name, end);
 448             if (str <= name) parse_err(start, str, "There should be an identifier after this '@:'");
 449             size_t namelen = (size_t)(str - name);
 450             bp_pat_t *p = NULL;
 451             if (matchchar(&str, '=', false, end)) {
 452                 p = bp_simplepattern(str, end);
 453                 if (p) str = p->end;
 454             }
 455             return Pattern(BP_TAGGED, start, str, p ? p->min_matchlen : 0, p ? p->max_matchlen : 0, .pat = p,
 456                            .name = name, .namelen = namelen);
 457         }
 458 
 459         const char *name = NULL;
 460         size_t namelen = 0;
 461         const char *a = after_name(str, end);
 462         const char *eq = a;
 463         bool backreffable = false;
 464         if (a > str && matchchar(&eq, ':', false, end)) {
 465             name = str;
 466             namelen = (size_t)(a - str);
 467             str = eq;
 468             backreffable = true;
 469         } else if (a > str && !matchstr(&eq, "=>", false, end) && matchchar(&eq, '=', false, end)) {
 470             name = str;
 471             namelen = (size_t)(a - str);
 472             str = eq;
 473         }
 474         bp_pat_t *pat = bp_simplepattern(str, end);
 475         if (!pat) parse_err(str, str, "There should be a valid pattern here to capture after the '@'");
 476 
 477         return Pattern(BP_CAPTURE, start, pat->end, pat->min_matchlen, pat->max_matchlen, .pat = pat, .name = name,
 478                        .namelen = namelen, .backreffable = backreffable);
 479     }
 480     // Start of file/line
 481     case '^': {
 482         if (*str == '^') return Pattern(BP_START_OF_FILE, start, ++str, 0, 0);
 483         return Pattern(BP_START_OF_LINE, start, str, 0, 0);
 484     }
 485     // End of file/line:
 486     case '$': {
 487         if (*str == '$') return Pattern(BP_END_OF_FILE, start, ++str, 0, 0);
 488         return Pattern(BP_END_OF_LINE, start, str, 0, 0);
 489     }
 490     default: {
 491         bp_pat_t *def = _bp_definition(start, end);
 492         if (def) return def;
 493         // Reference
 494         if (!isalpha(c) && c != '_') return NULL;
 495         str = after_name(start, end);
 496         size_t namelen = (size_t)(str - start);
 497         return Pattern(BP_REF, start, str, 0, -1, .name = start, .len = namelen);
 498     }
 499     }
 500 }
 501 
 502 //
 503 // Similar to bp_simplepattern, except that the pattern begins with an implicit
 504 // '}' open quote that can be closed with '{'
 505 //
 506 public
 507 maybe_pat_t bp_stringpattern(const char *str, const char *end) {
 508     __TRY_PATTERN__
 509     if (!end) end = str + strlen(str);
 510     char *start = (char *)str;
 511     while (str < end && *str != '{')
 512         str = next_char(str, end);
 513     size_t len = (size_t)(str - start);
 514     bp_pat_t *pat = len > 0 ? Pattern(BP_STRING, start, str, len, (ssize_t)len, .string = strndup(start, len)) : NULL;
 515     str += 1;
 516     if (str < end) {
 517         bp_pat_t *interp = bp_pattern_nl(str, end, true);
 518         if (interp) pat = chain_together(pat, interp);
 519         pat->end = end;
 520     }
 521     __END_TRY_PATTERN__
 522     return (maybe_pat_t){.success = true, .value.pat = pat};
 523 }
 524 
 525 //
 526 // Wrapper for _bp_simplepattern() that expands any postfix operators (~, !~)
 527 //
 528 static bp_pat_t *bp_simplepattern(const char *str, const char *end) {
 529     const char *start = str;
 530     bp_pat_t *pat = _bp_simplepattern(str, end, false);
 531     if (pat == NULL) return pat;
 532     str = pat->end;
 533 
 534     // Expand postfix operators (if any)
 535     while (str < end) {
 536         enum bp_pattype_e type;
 537         if (matchchar(&str, '~', false, end)) type = BP_MATCH;
 538         else if (matchstr(&str, "!~", false, end)) type = BP_NOT_MATCH;
 539         else break;
 540 
 541         bp_pat_t *first = pat;
 542         bp_pat_t *second = bp_simplepattern(str, end);
 543         if (!second) parse_err(str, str, "There should be a valid pattern here");
 544 
 545         pat = type == BP_MATCH ? Pattern(BP_MATCH, start, second->end, first->min_matchlen, first->max_matchlen,
 546                                          .pat = first, .must_match = second)
 547                                : Pattern(BP_NOT_MATCH, start, second->end, first->min_matchlen, first->max_matchlen,
 548                                          .pat = first, .must_not_match = second);
 549         str = pat->end;
 550     }
 551 
 552     return pat;
 553 }
 554 
 555 //
 556 // Given a pattern and a replacement string, compile the two into a BP
 557 // replace pattern.
 558 //
 559 public
 560 maybe_pat_t bp_replacement(bp_pat_t *replacepat, const char *replacement, const char *end) {
 561     const char *p = replacement;
 562     if (!end) end = replacement + strlen(replacement);
 563     __TRY_PATTERN__
 564     for (; p < end; p++) {
 565         if (*p == '\\') {
 566             if (!p[1] || p[1] == '\n')
 567                 parse_err(p, p, "There should be an escape sequence or pattern here after this backslash.");
 568             ++p;
 569         }
 570     }
 571     __END_TRY_PATTERN__
 572     size_t rlen = (size_t)(p - replacement);
 573     char *rcpy = new (char[rlen + 1]);
 574     memcpy(rcpy, replacement, rlen);
 575     bp_pat_t *pat = Pattern(BP_REPLACE, replacepat->start, replacepat->end, replacepat->min_matchlen,
 576                             replacepat->max_matchlen, .pat = replacepat, .text = rcpy, .len = rlen);
 577     return (maybe_pat_t){.success = true, .value.pat = pat};
 578 }
 579 
 580 static bp_pat_t *bp_pattern_nl(const char *str, const char *end, bool allow_nl) {
 581     str = after_spaces(str, allow_nl, end);
 582     bp_pat_t *pat = bp_simplepattern(str, end);
 583     if (pat != NULL) pat = expand_choices(pat, end, allow_nl);
 584     if (matchstr(&str, "=>", allow_nl, end))
 585         pat = expand_replacements(pat ? pat : Pattern(BP_STRING, str - 2, str - 2, 0, 0), end, allow_nl);
 586     return pat;
 587 }
 588 
 589 //
 590 // Return a new back reference to an existing match.
 591 //
 592 public
 593 bp_pat_t *bp_raw_literal(const char *str, size_t len) {
 594     return Pattern(BP_STRING, str, &str[len], len, (ssize_t)len, .string = strndup(str, len));
 595 }
 596 
 597 //
 598 // Compile a string representing a BP pattern into a pattern object.
 599 //
 600 public
 601 maybe_pat_t bp_pattern(const char *str, const char *end) {
 602     str = after_spaces(str, true, end);
 603     if (!end) end = str + strlen(str);
 604     __TRY_PATTERN__
 605     bp_pat_t *ret = bp_pattern_nl(str, end, false);
 606     __END_TRY_PATTERN__
 607     if (ret && after_spaces(ret->end, true, end) < end)
 608         return (maybe_pat_t){.success = false,
 609                              .value.error.start = ret->end,
 610                              .value.error.end = end,
 611                              .value.error.msg = "Failed to parse this part of the pattern"};
 612     else if (ret) return (maybe_pat_t){.success = true, .value.pat = ret};
 613     else
 614         return (maybe_pat_t){.success = false,
 615                              .value.error.start = str,
 616                              .value.error.end = end,
 617                              .value.error.msg = "Failed to parse this pattern"};
 618 }
 619 
 620 public
 621 void free_all_pats(void) {
 622     while (allocated_pats) {
 623         bp_pat_t *tofree = allocated_pats;
 624         allocated_pats = tofree->next;
 625         delete (&tofree);
 626     }
 627 }
 628 
 629 public
 630 void delete_pat(bp_pat_t **at_pat, bool recursive) {
 631     bp_pat_t *pat = *at_pat;
 632     if (!pat) return;
 633 
 634 #define T(tag, ...)                                                                                                    \
 635     case tag: {                                                                                                        \
 636         auto _data = When(pat, tag);                                                                                   \
 637         __VA_ARGS__;                                                                                                   \
 638         break;                                                                                                         \
 639     }
 640 #define F(field) delete_pat(&_data->field, true)
 641     if (recursive) {
 642         switch (pat->type) {
 643             T(BP_DEFINITIONS, F(meaning), F(next_def))
 644             T(BP_REPEAT, F(sep), F(repeat_pat))
 645             T(BP_CHAIN, F(first), F(second))
 646             T(BP_UPTO, F(target), F(skip))
 647             T(BP_UPTO_STRICT, F(target), F(skip))
 648             T(BP_OTHERWISE, F(first), F(second))
 649             T(BP_MATCH, F(pat), F(must_match))
 650             T(BP_NOT_MATCH, F(pat), F(must_not_match))
 651             T(BP_REPLACE, F(pat))
 652             T(BP_CAPTURE, F(pat))
 653             T(BP_TAGGED, F(pat))
 654             T(BP_NOT, F(pat))
 655             T(BP_AFTER, F(pat))
 656             T(BP_BEFORE, F(pat))
 657             T(BP_LEFTRECURSION, F(fallback))
 658             T(
 659                 BP_STRING, if (_data->string) {
 660                     free((char *)_data->string);
 661                     _data->string = NULL;
 662                 })
 663         default: break;
 664         }
 665     }
 666 #undef F
 667 #undef T
 668 
 669     if (pat->home) *(pat->home) = pat->next;
 670     if (pat->next) pat->next->home = pat->home;
 671     delete (at_pat);
 672 }
 673 
 674 int fprint_pattern(FILE *stream, bp_pat_t *pat) {
 675     if (!pat) return fputs("(null)", stream);
 676     switch (pat->type) {
 677 #define CASE(name, ...)                                                                                                \
 678     case BP_##name: {                                                                                                  \
 679         __auto_type data = pat->__tagged.BP_##name;                                                                    \
 680         (void)data;                                                                                                    \
 681         int _printed = fputs(#name, stream);                                                                           \
 682         __VA_ARGS__;                                                                                                   \
 683         return _printed;                                                                                               \
 684     }
 685 #define FMT(...) _printed += fprintf(stream, __VA_ARGS__)
 686 #define PAT(p) _printed += fprint_pattern(stream, p)
 687         CASE(ERROR)
 688         CASE(ANYCHAR)
 689         CASE(ID_START)
 690         CASE(ID_CONTINUE)
 691         CASE(STRING, FMT("(\"%s\")", data.string))
 692         CASE(RANGE, FMT("('%c'-'%c')", data.low, data.high))
 693         CASE(NOT, FMT("("); PAT(data.pat); FMT(")"))
 694         CASE(UPTO, FMT("("); PAT(data.target); FMT(", skip="); PAT(data.skip); FMT(")"))
 695         CASE(UPTO_STRICT, FMT("("); PAT(data.target); FMT(", skip=)"); PAT(data.skip))
 696         CASE(REPEAT, FMT("(%u-%d, ", data.min, data.max); PAT(data.repeat_pat); FMT(", sep="); PAT(data.sep); FMT(")"))
 697         CASE(BEFORE, FMT("("); PAT(data.pat); FMT(")"))
 698         CASE(AFTER, FMT("("); PAT(data.pat); FMT(")"))
 699         CASE(CAPTURE, FMT("("); PAT(data.pat);
 700              FMT(", name=%.*s, backref=%s)", data.namelen, data.name, data.backreffable ? "yes" : "no"))
 701         CASE(OTHERWISE, FMT("("); PAT(data.first); FMT(", "); PAT(data.second); FMT(")"))
 702         CASE(CHAIN, FMT("("); PAT(data.first); FMT(", "); PAT(data.second); FMT(")"))
 703         CASE(MATCH, FMT("("); PAT(data.pat); FMT(", matches="); PAT(data.must_match); FMT(")"))
 704         CASE(NOT_MATCH, FMT("("); PAT(data.pat); FMT(", must_not_match="); PAT(data.must_not_match); FMT(")"))
 705         CASE(REPLACE, FMT("("); PAT(data.pat); FMT(", \"%.*s\")", data.len, data.text))
 706         CASE(REF, FMT("(%.*s)", data.len, data.name))
 707         CASE(NODENT)
 708         CASE(CURDENT)
 709         CASE(START_OF_FILE)
 710         CASE(START_OF_LINE)
 711         CASE(END_OF_FILE)
 712         CASE(END_OF_LINE)
 713         CASE(WORD_BOUNDARY)
 714         CASE(DEFINITIONS, FMT("(%.*s=", data.namelen, data.name); PAT(data.meaning); FMT("); "); PAT(data.next_def))
 715         CASE(TAGGED, FMT("(%.*s=", data.namelen, data.name); PAT(data.pat);
 716              FMT(" backref=%s)", data.backreffable ? "yes" : "no"))
 717 #undef PAT
 718 #undef FMT
 719 #undef P
 720     default: return fputs("???", stream);
 721     }
 722 }
 723 
 724 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0