Mercurial > repo
view src/ploki/re.c @ 12292:d51f2100210c draft
<kspalaiologos> `` cat <<<"asmbf && bfi output.b" > /hackenv/ibin/asmbf
| author | HackEso <hackeso@esolangs.org> |
|---|---|
| date | Thu, 02 Jan 2020 15:38:21 +0000 |
| parents | ac0403686959 |
| children |
line wrap: on
line source
#include "config.h" #include "IO.h" #include "Str.h" #include "hash.h" #include "main_io.h" #include "main_opt.h" #include "re.h" #include "xmalloc.h" #include "zz.h" #include <ctype.h> #include <limits.h> #include <stddef.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> enum {CLASS_SIZE = UCHAR_MAX / CHAR_BIT + 1u}; static unsigned char dc_word[CLASS_SIZE]; static unsigned char dc_alpha[CLASS_SIZE]; static unsigned char dc_cntrl[CLASS_SIZE]; static unsigned char dc_digit[CLASS_SIZE]; static unsigned char dc_lower[CLASS_SIZE]; static unsigned char dc_print[CLASS_SIZE]; static unsigned char dc_space[CLASS_SIZE]; static unsigned char dc_upper[CLASS_SIZE]; static unsigned char dc_xdigit[CLASS_SIZE]; static void fill(unsigned char *v, int (*pred)(int)) { unsigned char c; for (c = UCHAR_MAX; c; --c) { v[c / CHAR_BIT] |= !!pred(c) << c % CHAR_BIT; } v[0] |= !!pred(0); } static void nfill(unsigned char *v, int (*pred)(int)) { unsigned char c; for (c = UCHAR_MAX; c; --c) { v[c / CHAR_BIT] |= !pred(c) << c % CHAR_BIT; } v[0] |= !pred(0); } ATTR_CONST static int siword(int c) { return c == '_' || isalnum(c); } enum {MAGIC = 23}; static Hash rcache; static String cached[MAGIC]; static size_t cachfill, cachlast; static size_t hash(const void *s, size_t seed) { return St_hash(s, seed); } static int compar(const void *a, const void *b) { return St_cmp(a, b); } enum t_re_node { RE_ALTER, RE_ANYCH, RE_AT_BOL, RE_AT_BOS, RE_AT_EOL, RE_AT_EOS, RE_AT_MATCH, RE_AT_NOMATCH, RE_AT_NWBOUND, RE_AT_WBOUND, RE_BACKCHECK, RE_BACKREF, RE_BEGIN_CAPTURE, RE_CLASS, RE_DEFCLASS, RE_END_CAPTURE, RE_INDEP, RE_LITERAL, RE_N_CLASS, RE_N_DEFCLASS, RE_PARTIAL, RE_REP_FRUGAL, RE_REP_GREEDY, RE_SELECT, RE_STUFF_FRUGAL, RE_STUFF_GREEDY, RE_XREP_FRUGAL, RE_XREP_GREEDY }; #define CMN_HDR enum t_re_node type; union my_node *next typedef union my_node { struct { CMN_HDR; } x; struct { CMN_HDR; union my_node *arg; } alter; struct { CMN_HDR; size_t n; } backref; struct { CMN_HDR; size_t n; } capture; struct { CMN_HDR; unsigned char vec[CLASS_SIZE]; } class; struct { CMN_HDR; unsigned char *vec; } defclass; struct { CMN_HDR; union my_node *arg; } indep; struct { CMN_HDR; unsigned char *buf; size_t len; } literal; struct { CMN_HDR; union my_node *arg; size_t min, max; size_t n; } rep; struct { CMN_HDR; union my_node *arg; union my_node *cond; } select; } re_node; #include "re_block.c.h" enum re_flags { FL_NONE = 0, FL_ANCHOR_START = 1 }; struct cap_state { size_t start, end, pending; }; struct my_regex { re_node *start; size_t repets; size_t *repbuf; t_block alloc; size_t captures; struct cap_state *cap_ptr; size_t refs; enum re_flags flags; size_t minlen; }; static void delv(void *v) { re_free(v); } void re_init(void) { fill(dc_word, siword); fill(dc_alpha, isalpha); fill(dc_cntrl, iscntrl); fill(dc_digit, isdigit); fill(dc_lower, islower); fill(dc_print, isprint); fill(dc_space, isspace); fill(dc_upper, isupper); fill(dc_xdigit, isxdigit); h_init(&rcache, hash, compar, NULL, delv); } void re_end(void) { h_end(&rcache); while (cachfill) { --cachfill; St_clear(&cached[cachfill]); } cachlast = 0; } enum {ESCAPE = '!'}; #define MEATCHARP(c) strchr("!|({<[]>})*+?:.'^$`", c) #define ENDBRANCHP(c) strchr("|({<[", c) struct parse_context { t_regex *base; t_block *block; const String *s; size_t *p; }; static void skipspace(const String *const s, size_t *const p) { restart: while (isspace(ST_INDEX(s, *p))) { --*p; } if (ST_INDEX(s, *p) == ']' && ST_INDEX(s, *p - 1u) == '#') { *p -= 2u; while (ST_INDEX(s, *p) != EOF) { if (ST_INDEX(s, *p) == '[') { --*p; goto restart; } if (ST_INDEX(s, *p) == ESCAPE && ST_INDEX(s, *p - 1u) != EOF) { --*p; } --*p; } } } #define PRAZ(name) static re_node *name(const struct parse_context *con, re_node *next, re_node *curolan_zebeth) #define SNORK const String *const s = con->s; size_t *const p = con->p #define CALL(name, nextn, glob) name(con, nextn, glob) #define TAILC(name) return CALL(name, next, curolan_zebeth) PRAZ(quantifire); PRAZ(branch); PRAZ(alternation); PRAZ(atom) { SNORK; (void)curolan_zebeth; skipspace(s, p); switch (ST_INDEX(s, *p)) { case '(': case '<': case '{': case '[': case EOF: { re_node *cur = bl_node(con->block); cur->literal.type = RE_LITERAL; cur->literal.next = next; cur->literal.buf = NULL; cur->literal.len = 0; return cur; } case ESCAPE: { re_node *cur = bl_node(con->block); --*p; if (isdigit(ST_INDEX(s, *p))) { do { --*p; } while (isdigit(ST_INDEX(s, *p))); cur->backref.type = RE_BACKREF; cur->backref.next = next; cur->backref.n = strtoul(St_ptr(s) + *p + 1, NULL, 10); } else if (isalpha(ST_INDEX(s, *p))) { switch (ST_INDEX(s, *p)) { case 'A': cur->x.type = RE_AT_BOL; cur->x.next = next; --*p; break; case 'Z': cur->x.type = RE_AT_EOL; cur->x.next = next; --*p; break; case 'b': cur->x.type = RE_AT_WBOUND; cur->x.next = next; --*p; break; case 'B': cur->x.type = RE_AT_NWBOUND; cur->x.next = next; --*p; break; case 'c': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_cntrl; cur->defclass.next = next; --*p; break; case 'C': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_cntrl; cur->defclass.next = next; --*p; break; case 'd': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_digit; cur->defclass.next = next; --*p; break; case 'D': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_digit; cur->defclass.next = next; --*p; break; case 'l': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_lower; cur->defclass.next = next; --*p; break; case 'L': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_lower; cur->defclass.next = next; --*p; break; case 'p': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_print; cur->defclass.next = next; --*p; break; case 'P': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_print; cur->defclass.next = next; --*p; break; case 'q': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_alpha; cur->defclass.next = next; --*p; break; case 'Q': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_alpha; cur->defclass.next = next; --*p; break; case 's': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_space; cur->defclass.next = next; --*p; break; case 'S': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_space; cur->defclass.next = next; --*p; break; case 'u': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_upper; cur->defclass.next = next; --*p; break; case 'U': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_upper; cur->defclass.next = next; --*p; break; case 'w': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_word; cur->defclass.next = next; --*p; break; case 'W': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_word; cur->defclass.next = next; --*p; break; case 'x': cur->defclass.type = RE_DEFCLASS; cur->defclass.vec = dc_xdigit; cur->defclass.next = next; --*p; break; case 'X': cur->defclass.type = RE_N_DEFCLASS; cur->defclass.vec = dc_xdigit; cur->defclass.next = next; --*p; break; default: goto default_escape; } } else default_escape: { cur->literal.type = RE_LITERAL; cur->literal.next = next; cur->literal.buf = bl_string(con->block, cur->literal.len = 1); if (ST_INDEX(s, *p) == EOF) { cur->literal.buf[0] = ESCAPE; } else { cur->literal.buf[0] = ST_INDEX(s, *p); --*p; } } return cur; } case ')': { re_node *cur; --*p; cur = CALL(alternation, next, next); skipspace(s, p); if (ST_INDEX(s, *p) == '(') { --*p; } return cur; } case ']': { re_node *cur; switch (ST_INDEX(s, *p - 1u)) { case '&': *p -= 2u; cur = bl_node(con->block); cur->indep.type = RE_AT_MATCH; cur->indep.next = next; cur->indep.arg = CALL(alternation, NULL, NULL); break; case '^': *p -= 2u; cur = bl_node(con->block); cur->indep.type = RE_AT_NOMATCH; cur->indep.next = next; cur->indep.arg = CALL(alternation, NULL, NULL); break; case '?': *p -= 2u; cur = bl_node(con->block); cur->select.type = RE_SELECT; cur->select.cond = CALL(quantifire, NULL, NULL); cur->select.arg = CALL(branch, next, next); skipspace(s, p); if (ST_INDEX(s, *p) == '|') { --*p; cur->select.next = CALL(alternation, next, next); } else { cur->select.next = next; } break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { size_t i; for (i = *p - 2u; isdigit(ST_INDEX(s, i)); --i) ; if (ST_INDEX(s, i) != '[') { goto std_atom; } cur = bl_node(con->block); cur->backref.type = RE_BACKCHECK; cur->backref.next = next; cur->backref.n = strtoul(St_ptr(s) + i + 1u, NULL, 10); *p = i - 1u; return cur; } default: goto std_atom; } skipspace(s, p); if (ST_INDEX(s, *p) == '[') { --*p; } return cur; } case '>': { re_node *cur = bl_node(con->block); --*p; cur->indep.type = RE_INDEP; cur->indep.next = next; cur->indep.arg = CALL(alternation, NULL, NULL); skipspace(s, p); if (ST_INDEX(s, *p) == '<') { --*p; } return cur; } case '}': { re_node *begin = bl_node(con->block); re_node *end = bl_node(con->block); --*p; begin->capture.n = end->capture.n = con->base->captures++; end->capture.type = RE_END_CAPTURE; end->capture.next = next; begin->capture.type = RE_BEGIN_CAPTURE; begin->capture.next = CALL(alternation, end, end); skipspace(s, p); if (ST_INDEX(s, *p) == '{') { --*p; } return begin; } case '^': { re_node *cur = bl_node(con->block); cur->x.type = RE_AT_BOS; cur->x.next = next; --*p; return cur; } case '$': { re_node *cur = bl_node(con->block); cur->x.type = RE_AT_EOS; cur->x.next = next; --*p; return cur; } case '.': { re_node *cur = bl_node(con->block); cur->x.type = RE_ANYCH; cur->x.next = next; --*p; return cur; } case '`': { String tmp; int c; re_node *cur = bl_node(con->block); cur->literal.type = RE_PARTIAL; cur->literal.next = next; --*p; St_init(&tmp); while ( (c = ST_INDEX(s, *p)) != EOF && c != '`' ) { --*p; if (c == ESCAPE && ST_INDEX(s, *p) != EOF) { c = ST_INDEX(s, *p); --*p; } St_cat_c(&tmp, c); } if (c == '`') { --*p; } St_reverse(&tmp); cur->literal.buf = bl_string(con->block, cur->literal.len = St_len(&tmp)); memcpy(cur->literal.buf, St_ptr(&tmp), St_len(&tmp)); St_clear(&tmp); return cur; } case '\'': { int c; re_node *cur = bl_node(con->block); cur->class.type = RE_CLASS; cur->class.next = next; memset(cur->class.vec, '\0', sizeof cur->class.vec); for (--*p; (c = ST_INDEX(s, *p)) != EOF && c != '\''; --*p) { if (c == ESCAPE) { switch (c = ST_INDEX(s, *p - 1)) { case EOF: cur->class.vec[ESCAPE / CHAR_BIT] |= 1u << ESCAPE % CHAR_BIT; break; case 'c': fill(cur->class.vec, iscntrl); --*p; break; case 'C': nfill(cur->class.vec, iscntrl); --*p; break; case 'd': fill(cur->class.vec, isdigit); --*p; break; case 'D': nfill(cur->class.vec, isdigit); --*p; break; case 'l': fill(cur->class.vec, islower); --*p; break; case 'L': nfill(cur->class.vec, islower); --*p; break; case 'p': fill(cur->class.vec, isprint); --*p; break; case 'P': nfill(cur->class.vec, isprint); --*p; break; case 'q': fill(cur->class.vec, isalpha); --*p; break; case 'Q': nfill(cur->class.vec, isalpha); --*p; break; case 's': fill(cur->class.vec, isspace); --*p; break; case 'S': nfill(cur->class.vec, isspace); --*p; break; case 'u': fill(cur->class.vec, isupper); --*p; break; case 'U': nfill(cur->class.vec, isupper); --*p; break; case 'w': fill(cur->class.vec, siword); --*p; break; case 'W': nfill(cur->class.vec, siword); --*p; break; case 'x': fill(cur->class.vec, isxdigit); --*p; break; case 'X': nfill(cur->class.vec, isxdigit); --*p; break; default: cur->class.vec[c / CHAR_BIT] |= 1u << c % CHAR_BIT; --*p; break; } } else { int b; if (ST_INDEX(s, *p - 1) == '-' && (b = ST_INDEX(s, *p - 2)) != EOF) { if (b == ESCAPE && (b = ST_INDEX(s, *p - 3)) == EOF) { b = ESCAPE; } if (b > c) { goto normal_char; } for (; b < c; ++b) { cur->class.vec[b / CHAR_BIT] |= 1u << b % CHAR_BIT; } cur->class.vec[b / CHAR_BIT] |= 1u << b % CHAR_BIT; *p -= 2; if (ST_INDEX(s, *p) == ESCAPE && ST_INDEX(s, *p - 1) != EOF) { --*p; } } else if (ST_INDEX(s, *p) == ']' && *p >= 8 && ST_INDEX(s, *p - 1) == ':') { #define CXCLASS_CHECK(n, t, f, o, b) if (1) { \ if (memcmp(St_ptr(s) + *p - (n), (t), (n) - 1) != 0) { \ goto normal_char; \ } \ (b)(cur->class.vec, (f)); \ *p -= (o); \ break; \ } else (void)0 #define CCLASS_CHECK(t, f, o) CXCLASS_CHECK(sizeof (t), t, f, o, fill) #define CNCLASS_CHECK(t, f, o) CXCLASS_CHECK(sizeof (t), t, f, o, nfill) if (ST_INDEX(s, *p - 8) == '[' && ST_INDEX(s, *p - 7) == ':') { switch (ST_INDEX(s, *p - 6)) { case 'a': if (ST_INDEX(s, *p - 5) != 'l') { goto normal_char; } switch (ST_INDEX(s, *p - 4)) { case 'n': CCLASS_CHECK("um", isalnum, 8); case 'p': CCLASS_CHECK("ha", isalpha, 8); default: goto normal_char; } break; case 'c': CCLASS_CHECK("ntrl", iscntrl, 8); case 'd': CCLASS_CHECK("igit", isdigit, 8); case 'g': CCLASS_CHECK("raph", isgraph, 8); case 'l': CCLASS_CHECK("ower", islower, 8); case 'p': switch (ST_INDEX(s, *p - 5)) { case 'r': CCLASS_CHECK("int", isprint, 8); case 'u': CCLASS_CHECK("nct", ispunct, 8); default: goto normal_char; } break; case 's': CCLASS_CHECK("pace", isspace, 8); case 'u': CCLASS_CHECK("pper", isupper, 8); default: goto normal_char; } } else if (*p >= 9 && ST_INDEX(s, *p - 9) == '[' && ST_INDEX(s, *p - 8) == ':') { switch (ST_INDEX(s, *p - 7)) { case 'x': CCLASS_CHECK("digit", isxdigit, 9); case '^': switch (ST_INDEX(s, *p - 6)) { case 'a': if (ST_INDEX(s, *p - 5) != 'l') { goto normal_char; } switch (ST_INDEX(s, *p - 4)) { case 'n': CNCLASS_CHECK("um", isalnum, 9); case 'p': CNCLASS_CHECK("ha", isalpha, 9); default: goto normal_char; } break; case 'c': CNCLASS_CHECK("ntrl", iscntrl, 9); case 'd': CNCLASS_CHECK("igit", isdigit, 9); case 'g': CNCLASS_CHECK("raph", isgraph, 9); case 'l': CNCLASS_CHECK("ower", islower, 9); case 'p': switch (ST_INDEX(s, *p - 5)) { case 'r': CNCLASS_CHECK("int", isprint, 9); case 'u': CNCLASS_CHECK("nct", ispunct, 9); default: goto normal_char; } break; case 's': CNCLASS_CHECK("pace", isspace, 9); case 'u': CNCLASS_CHECK("pper", isupper, 9); default: goto normal_char; } break; default: goto normal_char; } } else if (*p >= 10 && memcmp(St_ptr(s) + *p - 10, "[:^xdigit", 9) == 0) { nfill(cur->class.vec, isxdigit); *p -= 10; } else { goto normal_char; } } else if (ST_INDEX(s, *p) == '^' && ((b = ST_INDEX(s, *p - 1) == '\'') || b == EOF)) { cur->class.type = RE_N_CLASS; } else normal_char: { cur->class.vec[c / CHAR_BIT] |= 1u << c % CHAR_BIT; } } } if (c == '\'') { --*p; } if (cur->class.type == RE_CLASS) { size_t i; for (i = 0; i < CLASS_SIZE; ++i) { if (cur->class.vec[i] != (unsigned char)~0u) { return cur; } } cur->x.type = RE_ANYCH; } else { size_t i; assert(cur->class.type == RE_N_CLASS); for (i = 0; i < CLASS_SIZE; ++i) { if (cur->class.vec[i] != 0) { return cur; } } cur->x.type = RE_ANYCH; } return cur; } std_atom: default: { re_node *cur = bl_node(con->block); cur->literal.type = RE_LITERAL; /*XXX?*/ if (next && next->x.type == RE_LITERAL) { if (next->literal.len) { cur->literal.buf = bl_string(con->block, cur->literal.len = 1u + next->literal.len); memcpy(cur->literal.buf + 1, next->literal.buf, next->literal.len); } cur->literal.next = next->literal.next; } else { cur->literal.next = next; cur->literal.buf = bl_string(con->block, cur->literal.len = 1); } cur->literal.buf[0] = ST_INDEX(s, *p); --*p; return cur; } } } PRAZ(literal) { SNORK; int c; String tmp; re_node *cur; skipspace(s, p); if ((ST_INDEX(s, *p) != ESCAPE || isalnum(ST_INDEX(s, *p - 1))) && MEATCHARP(ST_INDEX(s, *p))) { TAILC(atom); } cur = bl_node(con->block); cur->literal.type = RE_LITERAL; cur->literal.next = next; St_init(&tmp); while ( (c = ST_INDEX(s, *p)) != EOF && ( !MEATCHARP(c) || (c == ESCAPE && !isalnum(ST_INDEX(s, *p - 1))) ) ) { --*p; if (c == ESCAPE && ST_INDEX(s, *p) != EOF) { c = ST_INDEX(s, *p); --*p; } St_cat_c(&tmp, c); skipspace(s, p); } St_reverse(&tmp); if (next && next->x.type == RE_LITERAL) { if (next->literal.len) { St_cat_m(&tmp, next->literal.buf, next->literal.len); } cur->literal.next = next->literal.next; } cur->literal.buf = bl_string(con->block, cur->literal.len = St_len(&tmp)); memcpy(cur->literal.buf, St_ptr(&tmp), St_len(&tmp)); St_clear(&tmp); return cur; } #define RETURN_REP(lo, hi, grdy) \ do { \ re_node *cur = bl_node(con->block); \ cur->rep.type = (grdy); \ cur->rep.next = next; \ cur->rep.min = (lo); \ cur->rep.max = (hi); \ cur->rep.n = con->base->repets++; \ cur->rep.arg = CALL(atom, cur, NULL); \ return cur; \ } while (0) #define STD_REP_CASE(lo, hi, grdy) \ do { \ --*p; \ RETURN_REP(lo, hi, grdy); \ } while (0) #define CUSTOM_REP_CASE(off, grdy, mismatch) \ do { \ size_t from, to; \ to = *p - 1 - (off); \ while (isdigit(ST_INDEX(s, to))) { \ --to; \ } \ if (ST_INDEX(s, to) == ':') { \ *p = to - 1; \ to = ST_INDEX(s, to + 1) == ':' ? (size_t)-1 : strtoul(St_ptr(s) + to + 1, NULL, 10); \ from = to; \ } else { \ if (ST_INDEX(s, to) != ',') { \ mismatch; \ } \ from = to - 1; \ if (!isdigit(ST_INDEX(s, from))) { \ mismatch; \ } \ do { \ --from; \ } while (isdigit(ST_INDEX(s, from))); \ if (ST_INDEX(s, from) != ':') { \ mismatch; \ } \ *p = from - 1; \ from = strtoul(St_ptr(s) + from + 1, NULL, 10); \ to = ST_INDEX(s, to + 1) == ':' ? (size_t)-1 : strtoul(St_ptr(s) + to + 1, NULL, 10); \ } \ if (to == 1) { \ if (from == 1) { \ TAILC(atom); \ } \ if (from == 0) { \ re_node *cur = bl_node(con->block); \ cur->alter.type = RE_ALTER; \ if ((grdy) == RE_REP_GREEDY) { \ cur->alter.next = next; \ cur->alter.arg = CALL(atom, next, NULL); \ } else { \ cur->alter.arg = next; \ cur->alter.next = CALL(atom, next, NULL); \ } \ return cur; \ } \ } \ RETURN_REP(from, to, grdy); \ } while (0) PRAZ(quantifire) { SNORK; skipspace(s, p); switch (ST_INDEX(s, *p)) { case EOF: return next; case '?': switch (ST_INDEX(s, *p - 1)) { case ':': CUSTOM_REP_CASE(1, RE_REP_FRUGAL, goto hook); case '*': --*p; STD_REP_CASE(0, -1, RE_REP_FRUGAL); case '+': --*p; STD_REP_CASE(1, -1, RE_REP_FRUGAL); case '?': { re_node *cur = bl_node(con->block); *p -= 2; cur->alter.type = RE_ALTER; cur->alter.next = CALL(atom, next, NULL); cur->alter.arg = next; return cur; } hook: default: { re_node *cur = bl_node(con->block); --*p; cur->alter.type = RE_ALTER; cur->alter.next = next; cur->alter.arg = CALL(atom, next, NULL); return cur; } } case ':': CUSTOM_REP_CASE(0, RE_REP_GREEDY, goto noquanti); case '*': STD_REP_CASE(0, -1, RE_REP_GREEDY); case '+': STD_REP_CASE(1, -1, RE_REP_GREEDY); noquanti: default: TAILC(literal); } } PRAZ(branch) { SNORK; skipspace(s, p); while (ST_INDEX(s, *p) != EOF && !ENDBRANCHP(ST_INDEX(s, *p))) { next = CALL(quantifire, next, curolan_zebeth); skipspace(s, p); } return next; } PRAZ(alternation) { SNORK; re_node *cur; skipspace(s, p); if (ST_INDEX(s, *p) == EOF) { return next; } next = CALL(branch, next, curolan_zebeth); skipspace(s, p); if (ST_INDEX(s, *p) != '|') { return next; } --*p; cur = bl_node(con->block); cur->alter.type = RE_ALTER; cur->alter.next = next; cur->alter.arg = CALL(alternation, curolan_zebeth, curolan_zebeth); return cur; } ATTR_CONST static size_t minimum(const size_t a, const size_t b) { return a < b ? a : b; } ATTR_CONST static size_t maximum(const size_t a, const size_t b) { return a > b ? a : b; } ATTR_PURE static size_t subminlen(const re_node *node, const re_node *end, size_t start) { if (!node || node == end) { return start; } switch (node->x.type) { case RE_ALTER: return minimum( subminlen(node->alter.arg, end, start), subminlen(node->alter.next, end, start) ); case RE_ANYCH: case RE_CLASS: case RE_DEFCLASS: case RE_N_CLASS: case RE_N_DEFCLASS: return subminlen(node->x.next, end, start + 1u); case RE_AT_BOL: case RE_AT_BOS: case RE_AT_EOL: case RE_AT_EOS: case RE_AT_NWBOUND: case RE_AT_WBOUND: case RE_BACKCHECK: case RE_BACKREF: case RE_BEGIN_CAPTURE: case RE_END_CAPTURE: case RE_PARTIAL: case RE_STUFF_FRUGAL: case RE_STUFF_GREEDY: return subminlen(node->x.next, end, start); case RE_AT_MATCH: return maximum( subminlen(node->indep.arg, end, start), subminlen(node->indep.next, end, start) ); case RE_AT_NOMATCH: return subminlen(node->indep.next, end, start); case RE_INDEP: return subminlen(node->indep.next, end, start + subminlen(node->indep.arg, NULL, 0)); case RE_LITERAL: return subminlen(node->literal.next, end, start + node->literal.len); case RE_SELECT: return minimum( subminlen(node->select.cond, end, start) + subminlen(node->select.arg, end, start), subminlen(node->select.next, end, start) ); case RE_REP_FRUGAL: case RE_REP_GREEDY: if (node->rep.min == 0) { return subminlen(node->rep.next, end, start); } return subminlen(node->rep.next, end, start + node->rep.min * subminlen(node->rep.arg, node, 0)); case RE_XREP_FRUGAL: case RE_XREP_GREEDY: if (node->rep.min == 0) { return subminlen(node->rep.next, end, start); } return subminlen(node->rep.next, end, start + node->rep.min * subminlen(node->rep.arg, NULL, 0)); } NOTREACHED; } ATTR_PURE static size_t minlen(const re_node *node) { return subminlen(node, NULL, 0); } static void reinit(t_regex *re) { const struct cap_state null = { -1, -1, -1 }; size_t i; for (i = 0; i < re->captures; ++i) { re->cap_ptr[i] = null; } } static re_node **notcomplex(re_node **node, const re_node *end) { assert(*node != NULL); if (*node == end) { return node; } switch ((*node)->x.type) { case RE_ALTER: case RE_AT_MATCH: case RE_AT_NOMATCH: case RE_BACKCHECK: case RE_BACKREF: case RE_BEGIN_CAPTURE: case RE_END_CAPTURE: case RE_INDEP: case RE_PARTIAL: case RE_REP_FRUGAL: case RE_REP_GREEDY: case RE_SELECT: case RE_STUFF_FRUGAL: case RE_STUFF_GREEDY: return NULL; case RE_XREP_FRUGAL: case RE_XREP_GREEDY: if ((*node)->rep.min == (*node)->rep.max) { return notcomplex(&(*node)->rep.next, end); } return NULL; case RE_ANYCH: case RE_AT_BOL: case RE_AT_BOS: case RE_AT_EOL: case RE_AT_EOS: case RE_AT_NWBOUND: case RE_AT_WBOUND: case RE_CLASS: case RE_DEFCLASS: case RE_LITERAL: case RE_N_CLASS: case RE_N_DEFCLASS: return notcomplex(&(*node)->x.next, end); } NOTREACHED; } static void trysimpl(re_node *node) { assert(node->x.type == RE_REP_FRUGAL || node->x.type == RE_REP_GREEDY); { re_node **const tmp = notcomplex(&node->rep.arg, node); if (!tmp) { return; } *tmp = NULL; } switch (node->rep.type) { case RE_REP_FRUGAL: if ( node->rep.arg->x.type == RE_ANYCH && node->rep.arg->x.next == NULL && node->rep.max == (size_t)-1 ) { if (node->rep.min == 0) { node->x.type = RE_STUFF_FRUGAL; break; } if (node->rep.min == 1) { node->rep.arg->x.next = node->x.next; node->rep.arg->x.type = RE_STUFF_FRUGAL; node->x.next = node->rep.arg; node->x.type = RE_ANYCH; break; } } node->rep.n = minlen(node->rep.arg); node->rep.type = RE_XREP_FRUGAL; break; case RE_REP_GREEDY: if ( node->rep.arg->x.type == RE_ANYCH && node->rep.arg->x.next == NULL && node->rep.max == (size_t)-1 ) { if (node->rep.min == 0) { node->x.type = RE_STUFF_GREEDY; break; } if (node->rep.min == 1) { node->rep.arg->x.next = node->x.next; node->rep.arg->x.type = RE_STUFF_GREEDY; node->x.next = node->rep.arg; node->x.type = RE_ANYCH; break; } } node->rep.n = minlen(node->rep.arg); node->rep.type = RE_XREP_GREEDY; break; default: NOTREACHED; } } static void simplerep(re_node *node, const re_node *const end) { if (!node || node == end) { return; } switch (node->x.type) { case RE_ALTER: simplerep(node->alter.arg, end); simplerep(node->alter.next, end); return; case RE_AT_MATCH: case RE_AT_NOMATCH: case RE_INDEP: simplerep(node->indep.arg, end); simplerep(node->indep.next, end); return; case RE_ANYCH: case RE_AT_BOL: case RE_AT_BOS: case RE_AT_EOL: case RE_AT_EOS: case RE_AT_NWBOUND: case RE_AT_WBOUND: case RE_BACKCHECK: case RE_BACKREF: case RE_BEGIN_CAPTURE: case RE_CLASS: case RE_DEFCLASS: case RE_END_CAPTURE: case RE_LITERAL: case RE_N_CLASS: case RE_N_DEFCLASS: case RE_PARTIAL: simplerep(node->x.next, end); return; case RE_REP_FRUGAL: case RE_REP_GREEDY: simplerep(node->rep.next, end); simplerep(node->rep.arg, node); trysimpl(node); return; case RE_SELECT: simplerep(node->select.cond, end); simplerep(node->select.arg, end); simplerep(node->select.next, end); return; case RE_STUFF_FRUGAL: case RE_STUFF_GREEDY: case RE_XREP_FRUGAL: case RE_XREP_GREEDY: return; } NOTREACHED; } ATTR_PURE static int anchorbegp(const re_node *node) { return node && ( node->x.type == RE_AT_BOS || node->x.type == RE_STUFF_FRUGAL || node->x.type == RE_STUFF_GREEDY || ( node->x.type == RE_ALTER && anchorbegp(node->alter.arg) && anchorbegp(node->alter.next) ) || ( node->x.type == RE_INDEP && anchorbegp(node->indep.arg) ) || ( node->x.type == RE_AT_MATCH && ( anchorbegp(node->indep.arg) || anchorbegp(node->indep.next) ) ) || ( ( node->x.type == RE_AT_NOMATCH || node->x.type == RE_AT_BOL || node->x.type == RE_AT_EOL || node->x.type == RE_AT_EOS || node->x.type == RE_AT_NWBOUND || node->x.type == RE_AT_WBOUND || node->x.type == RE_BEGIN_CAPTURE || node->x.type == RE_BACKCHECK ) && anchorbegp(node->x.next) ) ) ; } static void dostuff(t_regex *re) { simplerep(re->start, NULL); if (!re->start || anchorbegp(re->start)) { re->flags |= FL_ANCHOR_START; } } t_regex *re_compile(const String *s) { size_t p; struct parse_context dcon; t_regex *re; void *pre; if (h_get(&rcache, s, &pre) == H_OK) { re = pre; ++re->refs; return re; } re = xmalloc(1, sizeof *re); re->flags = FL_NONE; re->refs = 0; re->repets = 0; bl_init(&re->alloc); re->cap_ptr = NULL; re->captures = 0; dcon.base = re; dcon.block = &re->alloc; dcon.s = s; p = St_len(s) - 1; dcon.p = &p; re->start = alternation(&dcon, NULL, NULL); if (re->captures) { re->cap_ptr = xmalloc(re->captures, sizeof *re->cap_ptr); reinit(re); } dostuff(re); re->minlen = minlen(re->start); re->repbuf = xmalloc(re->repets, sizeof *re->repbuf); if (cachfill < sizeof cached / sizeof cached[0]) { St_init(&cached[cachfill]); St_cpy(&cached[cachfill], s); ++re->refs; h_put(&rcache, &cached[cachfill], re, 1); ++cachfill; } else { h_del(&rcache, &cached[cachlast]); St_cpy(&cached[cachlast], s); ++re->refs; h_put(&rcache, &cached[cachlast], re, 1); cachlast = (cachlast + 1u) % (sizeof cached / sizeof cached[0]); } if (Opt.debug & DBG_REGEX) { io_write_s(Err, "Compiled "); re_dump(re, io_fp(Err)); } return re; } t_regex *re_dup(t_regex *re) { ++re->refs; return re; } void re_free(t_regex *re) { if (re->refs) { --re->refs; return; } bl_free(&re->alloc); xfree(re->repbuf); xfree(re->cap_ptr); xfree(re); } ATTR_PURE static int match_class(unsigned char c, const unsigned char *vec) { return vec[c / CHAR_BIT] & 1u << c % CHAR_BIT; } static void *mem_dup(const void *p, size_t n, size_t m) { void *q = xmalloc(n, m); memcpy(q, p, n * m); return q; } #define NO_MATCH ((size_t)-1) #define Mmatch0(Xmatch, Xindex) \ size_t tmp; \ \ if (!node) { \ return o; \ } \ \ switch (node->x.type) { \ case RE_ALTER: \ if ((tmp = Xmatch(base, node->alter.arg, s, o)) == NO_MATCH) { \ return Xmatch(base, node->alter.next, s, o); \ } \ return tmp; \ \ case RE_ANYCH: \ if (Xindex(s, o) != EOF) { \ return Xmatch(base, node->x.next, s, o + 1u); \ } \ return NO_MATCH; \ \ case RE_AT_BOL: \ if (o == 0 || Xindex(s, o - 1u) == '\n') { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_AT_BOS: \ if (o == 0) { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_AT_EOL: \ if ( \ Xindex(s, o) == '\n' || \ ( \ o && Xindex(s, o) == EOF && Xindex(s, o - 1u) != '\n' \ ) \ ) { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_AT_EOS: \ if (Xindex(s, o) == EOF) { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_AT_MATCH: { \ struct cap_state *prev = mem_dup(base->cap_ptr, base->captures, sizeof *base->cap_ptr); \ tmp = Xmatch(base, node->indep.arg, s, o); \ if (tmp != NO_MATCH) { \ tmp = Xmatch(base, node->indep.next, s, o); \ if (tmp == NO_MATCH) { \ memcpy(base->cap_ptr, prev, base->captures * sizeof *base->cap_ptr); \ } \ } \ xfree(prev); \ return tmp; \ } \ \ case RE_AT_NOMATCH: { \ struct cap_state *prev = mem_dup(base->cap_ptr, base->captures, sizeof *base->cap_ptr); \ tmp = Xmatch(base, node->indep.arg, s, o); \ if (tmp == NO_MATCH) { \ tmp = Xmatch(base, node->indep.next, s, o); \ } else { \ memcpy(base->cap_ptr, prev, base->captures * sizeof *base->cap_ptr); \ tmp = NO_MATCH; \ } \ xfree(prev); \ return tmp; \ } \ \ case RE_AT_NWBOUND: \ if (siword(Xindex(s, o - 1u)) == siword(Xindex(s, o))) { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_AT_WBOUND: \ if (siword(Xindex(s, o - 1u)) != siword(Xindex(s, o))) { \ return Xmatch(base, node->x.next, s, o); \ } \ return NO_MATCH; \ \ case RE_BACKCHECK: \ if ( \ node->backref.n < base->captures && \ base->cap_ptr[node->backref.n].start + 1u && \ base->cap_ptr[node->backref.n].end + 1u && \ base->cap_ptr[node->backref.n].end >= base->cap_ptr[node->backref.n].start \ ) { \ return Xmatch(base, node->backref.next, s, o); \ } \ return NO_MATCH #define Mmatch1(Xmatch, Xindex) \ case RE_BEGIN_CAPTURE: { \ const size_t prev = base->cap_ptr[node->capture.n].pending; \ base->cap_ptr[node->capture.n].pending = o; \ if ((tmp = Xmatch(base, node->capture.next, s, o)) == NO_MATCH) { \ base->cap_ptr[node->capture.n].pending = prev; \ } \ return tmp; \ } \ \ case RE_CLASS: \ if ( \ Xindex(s, o) != EOF && \ match_class(Xindex(s, o), node->class.vec) \ ) { \ return Xmatch(base, node->class.next, s, o + 1u); \ } \ return NO_MATCH; \ \ case RE_DEFCLASS: \ if ( \ Xindex(s, o) != EOF && \ match_class(Xindex(s, o), node->defclass.vec) \ ) { \ return Xmatch(base, node->defclass.next, s, o + 1u); \ } \ return NO_MATCH; \ \ case RE_END_CAPTURE: { \ const size_t prevbeg = base->cap_ptr[node->capture.n].start; \ const size_t prevend = base->cap_ptr[node->capture.n].end; \ if (base->cap_ptr[node->capture.n].pending + 1u == 0u) { \ return NO_MATCH; \ } \ \ base->cap_ptr[node->capture.n].end = o; \ base->cap_ptr[node->capture.n].start = base->cap_ptr[node->capture.n].pending; \ if ((tmp = Xmatch(base, node->capture.next, s, o)) == NO_MATCH) { \ base->cap_ptr[node->capture.n].end = prevend; \ base->cap_ptr[node->capture.n].start = prevbeg; \ } \ return tmp; \ } \ \ case RE_INDEP: { \ struct cap_state *prev = mem_dup(base->cap_ptr, base->captures, sizeof *base->cap_ptr); \ if ((tmp = Xmatch(base, node->indep.arg, s, o)) != NO_MATCH) { \ tmp = Xmatch(base, node->indep.next, s, tmp); \ if (tmp == NO_MATCH) { \ memcpy(base->cap_ptr, prev, base->captures * sizeof *base->cap_ptr); \ } \ } \ xfree(prev); \ return tmp; \ } \ \ case RE_N_CLASS: \ if ( \ Xindex(s, o) != EOF && \ !match_class(Xindex(s, o), node->class.vec) \ ) { \ return Xmatch(base, node->class.next, s, o + 1u); \ } \ return NO_MATCH; \ \ case RE_N_DEFCLASS: \ if ( \ Xindex(s, o) != EOF && \ !match_class(Xindex(s, o), node->defclass.vec) \ ) { \ return Xmatch(base, node->defclass.next, s, o + 1u); \ } \ return NO_MATCH; \ \ case RE_PARTIAL: { \ size_t n; \ for (n = 0; n < node->literal.len; ++n) { \ if (node->literal.buf[n] != Xindex(s, o + n)) { \ break; \ } \ } \ for (; n; --n) { \ if ((tmp = Xmatch(base, node->literal.next, s, o + n)) != NO_MATCH) { \ return tmp; \ } \ } \ return Xmatch(base, node->literal.next, s, o); \ } \ \ case RE_SELECT: { \ struct cap_state *prev = mem_dup(base->cap_ptr, base->captures, sizeof *base->cap_ptr); \ if ((tmp = Xmatch(base, node->select.cond, s, o)) != NO_MATCH) { \ tmp = Xmatch(base, node->select.arg, s, tmp); \ if (tmp == NO_MATCH) { \ memcpy(base->cap_ptr, prev, base->captures * sizeof *base->cap_ptr); \ } \ } else { \ tmp = Xmatch(base, node->select.next, s, o); \ } \ xfree(prev); \ return tmp; \ } \ \ case RE_REP_FRUGAL: \ if (base->repbuf[node->rep.n] >= node->rep.max) { \ const size_t n = base->repbuf[node->rep.n]; \ \ base->repbuf[node->rep.n] = 0; \ tmp = Xmatch(base, node->rep.next, s, o); \ base->repbuf[node->rep.n] = n; \ return tmp; \ } else if (base->repbuf[node->rep.n] >= node->rep.min) { \ const size_t n = base->repbuf[node->rep.n]; \ \ base->repbuf[node->rep.n] = 0; \ if ((tmp = Xmatch(base, node->rep.next, s, o)) != NO_MATCH) { \ base->repbuf[node->rep.n] = n; \ return tmp; \ } \ base->repbuf[node->rep.n] = n + 1u; \ tmp = Xmatch(base, node->rep.arg, s, o); \ --base->repbuf[node->rep.n]; \ return tmp; \ } else { \ ++base->repbuf[node->rep.n]; \ tmp = Xmatch(base, node->rep.arg, s, o); \ --base->repbuf[node->rep.n]; \ return tmp; \ } \ \ case RE_REP_GREEDY: \ if (base->repbuf[node->rep.n] >= node->rep.max) { \ const size_t n = base->repbuf[node->rep.n]; \ \ base->repbuf[node->rep.n] = 0; \ tmp = Xmatch(base, node->rep.next, s, o); \ base->repbuf[node->rep.n] = n; \ return tmp; \ } else if (base->repbuf[node->rep.n] >= node->rep.min) { \ const size_t n = base->repbuf[node->rep.n]; \ \ ++base->repbuf[node->rep.n]; \ if ((tmp = Xmatch(base, node->rep.arg, s, o)) != NO_MATCH) { \ --base->repbuf[node->rep.n]; \ return tmp; \ } \ base->repbuf[node->rep.n] = 0; \ tmp = Xmatch(base, node->rep.next, s, o); \ base->repbuf[node->rep.n] = n; \ return tmp; \ } else { \ ++base->repbuf[node->rep.n]; \ tmp = Xmatch(base, node->rep.arg, s, o); \ --base->repbuf[node->rep.n]; \ return tmp; \ } \ \ case RE_XREP_FRUGAL: { \ size_t n; \ \ for (n = 0; n < node->rep.min; ++n) { \ if ((tmp = Xmatch(base, node->rep.arg, s, o)) == NO_MATCH) { \ return NO_MATCH; \ } \ o = tmp; \ } \ \ for (; n < node->rep.max; ++n) { \ if ((tmp = Xmatch(base, node->rep.next, s, o)) != NO_MATCH) { \ return tmp; \ } \ if ((tmp = Xmatch(base, node->rep.arg, s, o)) == NO_MATCH) { \ return NO_MATCH; \ } \ o = tmp; \ } \ return Xmatch(base, node->rep.next, s, o); \ } \ \ case RE_XREP_GREEDY: { \ size_t n; \ \ for (n = 0; n < node->rep.min; ++n) { \ if ((tmp = Xmatch(base, node->rep.arg, s, o)) == NO_MATCH) { \ return NO_MATCH; \ } \ o = tmp; \ } \ \ for (; n < node->rep.max; ++n) { \ if ((tmp = Xmatch(base, node->rep.arg, s, o)) == NO_MATCH) { \ break; \ } \ o = tmp; \ } \ \ for (; n > node->rep.min; --n) { \ if ((tmp = Xmatch(base, node->rep.next, s, o)) != NO_MATCH) { \ return tmp; \ } \ o -= node->rep.n; \ } \ \ return Xmatch(base, node->rep.next, s, o); \ } \ } \ \ NOTREACHED static size_t match(const t_regex *base, const re_node *node, const String *s, size_t o) { Mmatch0(match, ST_INDEX); case RE_BACKREF: if ( node->backref.n < base->captures && base->cap_ptr[node->backref.n].start + 1u && base->cap_ptr[node->backref.n].end + 1u && base->cap_ptr[node->backref.n].end >= base->cap_ptr[node->backref.n].start && ( base->cap_ptr[node->backref.n].end - base->cap_ptr[node->backref.n].start <= St_len(s) - o && memcmp( St_ptr(s) + base->cap_ptr[node->backref.n].start, St_ptr(s) + o, base->cap_ptr[node->backref.n].end - base->cap_ptr[node->backref.n].start ) == 0 ) ) { return match(base, node->backref.next, s, o + base->cap_ptr[node->backref.n].end - base->cap_ptr[node->backref.n].start); } return NO_MATCH; case RE_LITERAL: if ( node->literal.len == 0 || ( node->literal.len <= St_len(s) - o && memcmp(node->literal.buf, St_ptr(s) + o, node->literal.len) == 0 ) ) { return match(base, node->literal.next, s, o + node->literal.len); } return NO_MATCH; case RE_STUFF_FRUGAL: if (!node->x.next) { return o; } if (node->x.next->x.type == RE_LITERAL && node->x.next->literal.len) { for ( o = St_stro_m(s, o, node->x.next->literal.buf, node->x.next->literal.len); o + 1u; o = St_stro_m(s, o + 1u, node->x.next->literal.buf, node->x.next->literal.len) ) { if ((tmp = match(base, node->x.next->literal.next, s, o + node->x.next->literal.len)) != NO_MATCH) { return tmp; } } return NO_MATCH; } for (; o <= St_len(s); ++o) { if ((tmp = match(base, node->x.next, s, o)) != NO_MATCH) { return tmp; } } return NO_MATCH; case RE_STUFF_GREEDY: { size_t n; if (!node->x.next) { return St_len(s); } if (node->x.next->x.type == RE_LITERAL && node->x.next->literal.len) { for ( n = St_rstr_m(s, node->x.next->literal.buf, node->x.next->literal.len); n > o && n + 1u; n = St_rstro_m(s, n - 1u, node->x.next->literal.buf, node->x.next->literal.len) ) { if ((tmp = match(base, node->x.next->literal.next, s, n + node->x.next->literal.len)) != NO_MATCH) { return tmp; } if (!n) { break; } } if (n == o) { return match(base, node->x.next->literal.next, s, n + node->x.next->literal.len); } return NO_MATCH; } for (n = St_len(s); n > o; --n) { if ((tmp = match(base, node->x.next, s, n)) != NO_MATCH) { return tmp; } } return match(base, node->x.next, s, o); } Mmatch1(match, ST_INDEX); } static size_t iomatch(const t_regex *base, const re_node *node, IO *s, size_t o) { Mmatch0(iomatch, io_peek); case RE_BACKREF: if ( node->backref.n < base->captures && base->cap_ptr[node->backref.n].start + 1u && base->cap_ptr[node->backref.n].end + 1u && base->cap_ptr[node->backref.n].end >= base->cap_ptr[node->backref.n].start && ( io_xcmp( s, base->cap_ptr[node->backref.n].start, o, base->cap_ptr[node->backref.n].end - base->cap_ptr[node->backref.n].start ) == 0 ) ) { return iomatch(base, node->backref.next, s, o + base->cap_ptr[node->backref.n].end - base->cap_ptr[node->backref.n].start); } return NO_MATCH; case RE_LITERAL: if ( node->literal.len == 0 || ( io_cmppeek(s, o, node->literal.buf, node->literal.len) == 0 ) ) { return iomatch(base, node->literal.next, s, o + node->literal.len); } return NO_MATCH; case RE_STUFF_FRUGAL: if (!node->x.next) { return o; } for (; io_peek(s, o) != EOF; ++o) { if ((tmp = iomatch(base, node->x.next, s, o)) != NO_MATCH) { return tmp; } } return iomatch(base, node->x.next, s, o); case RE_STUFF_GREEDY: { size_t n; for (n = o; io_peek(s, n) != EOF; ++n) ; if (!node->x.next) { return n; } for (; n > o; --n) { if ((tmp = iomatch(base, node->x.next, s, n)) != NO_MATCH) { return tmp; } } return iomatch(base, node->x.next, s, o); } Mmatch1(iomatch, io_peek); } #define DEFRBUF ((void)0) #define MRETURN(x) return (x) #define INITRBUF(re) memset((re)->repbuf, '\0', (re)->repets * sizeof *(re)->repbuf) int re_iomatch(t_regex *re, IO *io, size_t *ms, size_t *me) { size_t i; DEFRBUF; INITRBUF(re); assert(re != NULL); assert(io != NULL); assert(io_bufred(io)); assert(ms != NULL); assert(me != NULL); reinit(re); if (re->flags & FL_ANCHOR_START) { if ((*me = iomatch(re, re->start, io, 0)) == NO_MATCH) { MRETURN(0); } *ms = 0; MRETURN(1); } for (i = 0; io_peek(io, i) != EOF; ++i) { if ((*me = iomatch(re, re->start, io, i)) != NO_MATCH) { *ms = i; MRETURN(1); } } if ((*me = iomatch(re, re->start, io, i)) != NO_MATCH) { *ms = i; MRETURN(1); } MRETURN(0); } int re_match(t_regex *re, const String *s, size_t *ms, size_t *me) { size_t i; DEFRBUF; INITRBUF(re); assert(re != NULL); assert(s != NULL); assert(ms != NULL); assert(me != NULL); if (re->minlen > St_len(s)) { MRETURN(0); } reinit(re); if (re->flags & FL_ANCHOR_START) { if ((*me = match(re, re->start, s, 0)) == NO_MATCH) { MRETURN(0); } *ms = 0; MRETURN(1); } if (re->start->x.type == RE_LITERAL && re->start->literal.len) { for ( i = St_str_m(s, re->start->literal.buf, re->start->literal.len); i + 1u; i = St_stro_m(s, i + 1u, re->start->literal.buf, re->start->literal.len) ) { if ((*me = match(re, re->start->literal.next, s, i + re->start->literal.len)) != NO_MATCH) { *ms = i; MRETURN(1); } } MRETURN(0); } for (i = 0; i <= St_len(s) - re->minlen; ++i) { if ((*me = match(re, re->start, s, i)) != NO_MATCH) { *ms = i; MRETURN(1); } } MRETURN(0); } size_t re_cabra(const t_regex *re) { return re->captures; } int re_backref(const t_regex *re, size_t i, size_t *a, size_t *z) { if (i >= re->captures) { return -1; } if (!(re->cap_ptr[i].start + 1u && re->cap_ptr[i].end + 1u)) { return 1; } *a = re->cap_ptr[i].start; *z = re->cap_ptr[i].end; return 0; } ATTR_PURE static const re_node *branchend(const re_node *a, const re_node *b) { for (; a; a = a->x.next) { const re_node *q = b; for (; q; q = q->x.next) { if (a == q) { return q; } } } return NULL; } static void decom_class(String *s, const unsigned char vec[HAVE_C99(static CLASS_SIZE)]) { unsigned char i; int flag = 0; char big_enough[100]; for (i = 0; i < UCHAR_MAX; ++i) { if (vec[i / CHAR_BIT] & 1u << i % CHAR_BIT) { if (vec[(i + 1u) / CHAR_BIT] & 1u << (i + 1u) % CHAR_BIT) { if (!flag) { flag = 1; goto mess; } flag = 1; } else { if (flag) { if (i > 1u && vec[(i - 2u) / CHAR_BIT] & 1u << (i - 2u) % CHAR_BIT) { St_cat_c(s, '-'); } flag = 0; } mess: if (!isprint(i)) { St_cat_c(s, '\\'); switch (i) { case '\a': St_cat_c(s, 'a'); break; case '\b': St_cat_c(s, 'b'); break; case '\f': St_cat_c(s, 'f'); break; case '\n': St_cat_c(s, 'n'); break; case '\r': St_cat_c(s, 'r'); break; case '\t': St_cat_c(s, 't'); break; case '\v': St_cat_c(s, 'v'); break; default: sprintf(big_enough, "%03o", (unsigned)i); St_cat_s(s, big_enough); break; } } else { if (strchr("\\\"", (char)i)) { St_cat_c(s, '\\'); } St_cat_c(s, i); if (strchr("!'-", (char)i)) { St_cat_c(s, ESCAPE); } } } } } if (vec[i / CHAR_BIT] & 1u << i % CHAR_BIT) { if (flag) { if (vec[(i - 2u) / CHAR_BIT] & 1u << (i - 2u) % CHAR_BIT) { St_cat_c(s, '-'); } flag = 0; } if (!isprint(i)) { St_cat_c(s, '\\'); switch (i) { case '\a': St_cat_c(s, 'a'); break; case '\b': St_cat_c(s, 'b'); break; case '\f': St_cat_c(s, 'f'); break; case '\n': St_cat_c(s, 'n'); break; case '\r': St_cat_c(s, 'r'); break; case '\t': St_cat_c(s, 't'); break; case '\v': St_cat_c(s, 'v'); break; default: sprintf(big_enough, "%03o", (unsigned)i); St_cat_s(s, big_enough); break; } } else { if (strchr("\\\"", (char)i)) { St_cat_c(s, '\\'); } St_cat_c(s, i); if (strchr("!'-", (char)i)) { St_cat_c(s, ESCAPE); } } } } static void dumpclass(FILE *fp, const unsigned char vec[HAVE_C99(static CLASS_SIZE)]) { String tmp; St_init(&tmp); decom_class(&tmp, vec); ST_WRITE(&tmp, fp); St_clear(&tmp); } ATTR_CONST static int cdefclass(const unsigned char *ptr) { if (ptr == dc_word) { return 'w'; } if (ptr == dc_alpha) { return 'q'; } if (ptr == dc_cntrl) { return 'c'; } if (ptr == dc_digit) { return 'd'; } if (ptr == dc_lower) { return 'l'; } if (ptr == dc_print) { return 'p'; } if (ptr == dc_space) { return 's'; } if (ptr == dc_upper) { return 'u'; } if (ptr == dc_xdigit) { return 'x'; } NOTREACHED; } static void decom_liter(String *s, const re_node *node) { size_t i; assert(node->x.type == RE_LITERAL || node->x.type == RE_PARTIAL); for (i = 0; i < node->literal.len; ++i) { if (!isprint((unsigned char)node->literal.buf[i])) { St_cat_c(s, '\\'); switch (node->literal.buf[i]) { case '\a': St_cat_c(s, 'a'); break; case '\b': St_cat_c(s, 'b'); break; case '\f': St_cat_c(s, 'f'); break; case '\n': St_cat_c(s, 'n'); break; case '\r': St_cat_c(s, 'r'); break; case '\t': St_cat_c(s, 't'); break; case '\v': St_cat_c(s, 'v'); break; default: { char big_enough[100]; sprintf(big_enough, "%03o", (unsigned)(unsigned char)node->literal.buf[i]); St_cat_s(s, big_enough); break; } } } else { if (node->x.type == RE_LITERAL && strchr("\"\\", node->literal.buf[i])) { St_cat_c(s, '\\'); } St_cat_c(s, node->literal.buf[i]); if (MEATCHARP(node->literal.buf[i])) { St_cat_c(s, ESCAPE); } } } } static void dumpliter(FILE *fp, const re_node *node) { String tmp; St_init(&tmp); decom_liter(&tmp, node); ST_WRITE(&tmp, fp); St_clear(&tmp); } static void do_indent(FILE *fp, size_t n) { for (; n; --n) { fputs(" ", fp); } } static void dumpnode(FILE *fp, const re_node *node, const re_node *end, const size_t indent) { if (node == end) { return; } assert(node != NULL); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); switch (node->x.type) { case RE_ALTER: { const re_node *const be = branchend(node->alter.arg, node->alter.next); fputs("branch {\n", fp); dumpnode(fp, node->alter.arg, be, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} or {\n", fp); dumpnode(fp, node->alter.next, be, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /branch\n", fp); dumpnode(fp, be, end, indent); return; } case RE_ANYCH: fputs("anychar\n", fp); break; case RE_AT_BOL: fputs("at beginning of line\n", fp); break; case RE_AT_BOS: fputs("at beginning of string\n", fp); break; case RE_AT_EOL: fputs("at end of line\n", fp); break; case RE_AT_EOS: fputs("at end of string\n", fp); break; case RE_AT_MATCH: fputs("at match {\n", fp); dumpnode(fp, node->indep.arg, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /at match\n", fp); break; case RE_AT_NOMATCH: fputs("not at match {\n", fp); dumpnode(fp, node->indep.arg, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /not at match\n", fp); break; case RE_AT_NWBOUND: fputs("not at word boundary\n", fp); break; case RE_AT_WBOUND: fputs("at word boundary\n", fp); break; case RE_BACKCHECK: fprintf(fp, "check capture (%lu)\n", (unsigned long)node->backref.n); break; case RE_BACKREF: fprintf(fp, "backref (%lu)\n", (unsigned long)node->backref.n); break; case RE_BEGIN_CAPTURE: fprintf(fp, "begin capture (%lu)\n", (unsigned long)node->backref.n); break; case RE_CLASS: fputs("character class '", fp); dumpclass(fp, node->class.vec); fputs("'\n", fp); break; case RE_DEFCLASS: fprintf(fp, "character class %c!\n", cdefclass(node->defclass.vec)); break; case RE_END_CAPTURE: fprintf(fp, "end capture (%lu)\n", (unsigned long)node->backref.n); break; case RE_INDEP: fputs("independent submatch {\n", fp); dumpnode(fp, node->indep.arg, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /independent submatch\n", fp); break; case RE_LITERAL: fputs("literal \"", fp); dumpliter(fp, node); fputs("\"\n", fp); break; case RE_N_CLASS: fputs("negated character class '", fp); dumpclass(fp, node->class.vec); fputs("'\n", fp); break; case RE_N_DEFCLASS: fprintf(fp, "character class %c!\n", toupper(cdefclass(node->defclass.vec))); break; case RE_PARTIAL: fputs("abbreviation `", fp); dumpliter(fp, node); fputs("`\n", fp); break; case RE_REP_FRUGAL: fputs("repetition ", fp); if (node->rep.min == node->rep.max) { fprintf(fp, ":%lu:?", (unsigned long)node->rep.min); } else if (node->rep.max != (size_t)-1) { fprintf(fp, ":%lu,%lu:?", (unsigned long)node->rep.min, (unsigned long)node->rep.max); } else { switch (node->rep.min) { case 0: fputs("*?", fp); break; case 1: fputs("+?", fp); break; default: fprintf(fp, ":%lu,:?", (unsigned long)node->rep.min); break; } } fputs(" {\n", fp); dumpnode(fp, node->rep.arg, node, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /repetition\n", fp); break; case RE_REP_GREEDY: fputs("repetition ", fp); if (node->rep.min == node->rep.max) { fprintf(fp, ":%lu:", (unsigned long)node->rep.min); } else if (node->rep.max != (size_t)-1) { fprintf(fp, ":%lu,%lu:", (unsigned long)node->rep.min, (unsigned long)node->rep.max); } else { switch (node->rep.min) { case 0: fputs("*", fp); break; case 1: fputs("+", fp); break; default: fprintf(fp, ":%lu,:", (unsigned long)node->rep.min); break; } } fputs(" {\n", fp); dumpnode(fp, node->rep.arg, node, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /repetition\n", fp); break; case RE_SELECT: { const re_node *const be = branchend(node->select.arg, node->select.next); fputs("if {\n", fp); dumpnode(fp, node->select.cond, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} then {\n", fp); dumpnode(fp, node->select.arg, be, indent + 1); if (node->select.next != be) { fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} else {\n", fp); dumpnode(fp, node->select.next, be, indent + 1); } fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /if\n", fp); dumpnode(fp, be, end, indent); return; } case RE_STUFF_FRUGAL: fputs(".*?\n", fp); break; case RE_STUFF_GREEDY: fputs(".*\n", fp); break; case RE_XREP_FRUGAL: fputs("simple repetition ", fp); if (node->rep.min == node->rep.max) { fprintf(fp, ":%lu:?", (unsigned long)node->rep.min); } else if (node->rep.max != (size_t)-1) { fprintf(fp, ":%lu,%lu:?", (unsigned long)node->rep.min, (unsigned long)node->rep.max); } else { switch (node->rep.min) { case 0: fputs("*?", fp); break; case 1: fputs("+?", fp); break; default: fprintf(fp, ":%lu,:?", (unsigned long)node->rep.min); break; } } fputs(" {\n", fp); dumpnode(fp, node->rep.arg, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /simple repetition\n", fp); break; case RE_XREP_GREEDY: fputs("simple repetition ", fp); if (node->rep.min == node->rep.max) { fprintf(fp, ":%lu:", (unsigned long)node->rep.min); } else if (node->rep.max != (size_t)-1) { fprintf(fp, ":%lu,%lu:", (unsigned long)node->rep.min, (unsigned long)node->rep.max); } else { switch (node->rep.min) { case 0: fputs("*", fp); break; case 1: fputs("+", fp); break; default: fprintf(fp, ":%lu,:", (unsigned long)node->rep.min); break; } } fputs(" {\n", fp); dumpnode(fp, node->rep.arg, NULL, indent + 1); fprintf(fp, "[%p] ", (const void *)node); do_indent(fp, indent); fputs("} /simple repetition\n", fp); break; } dumpnode(fp, node->x.next, end, indent); } void re_dump(const t_regex *re, FILE *fp) { fprintf(fp, "RE: minlen=%lu, anchor=%s\n", (unsigned long)re->minlen, re->flags & FL_ANCHOR_START ? "start" : "none"); dumpnode(fp, re->start, NULL, 0); } static void cat_n(String *s, unsigned long n) { char big_enough[100]; sprintf(big_enough, "%lu", n); St_cat_s(s, big_enough); } static void decom_repeat(String *s, const re_node *node) { assert( node->x.type == RE_REP_FRUGAL || node->x.type == RE_REP_GREEDY || node->x.type == RE_XREP_FRUGAL || node->x.type == RE_XREP_GREEDY ); if (node->rep.min == 0 && node->rep.max == (size_t)-1) { St_cat_c(s, '*'); } else if (node->rep.min == 0 && node->rep.max == 1) { St_cat_c(s, '?'); } else if (node->rep.min == 1 && node->rep.max == (size_t)-1) { St_cat_c(s, '+'); } else if (node->rep.min == node->rep.max) { St_cat_c(s, ':'); cat_n(s, node->rep.min); St_cat_c(s, ':'); } else if (node->rep.max == (size_t)-1) { St_cat_c(s, ':'); cat_n(s, node->rep.min); St_cat_m(s, ",:", 2); } else { St_cat_c(s, ':'); cat_n(s, node->rep.min); St_cat_c(s, ','); cat_n(s, node->rep.max); St_cat_c(s, ':'); } if (node->rep.type == RE_REP_FRUGAL || node->rep.type == RE_XREP_FRUGAL) { St_cat_c(s, '?'); } } static void decom_node(String *s, const re_node *node, const re_node *end) { if (node == end) { return; } assert(node != NULL); switch (node->x.type) { case RE_ALTER: { const re_node *const be = branchend(node->alter.arg, node->alter.next); St_cat_c(s, '('); decom_node(s, node->alter.arg, be); St_cat_c(s, '|'); decom_node(s, node->alter.next, be); St_cat_c(s, ')'); decom_node(s, be, end); break; } case RE_ANYCH: St_cat_c(s, '.'); decom_node(s, node->x.next, end); break; case RE_AT_BOL: St_cat_m(s, "A!", 2); decom_node(s, node->x.next, end); break; case RE_AT_BOS: St_cat_c(s, '^'); decom_node(s, node->x.next, end); break; case RE_AT_EOL: St_cat_m(s, "Z!", 2); decom_node(s, node->x.next, end); break; case RE_AT_EOS: St_cat_c(s, '$'); decom_node(s, node->x.next, end); break; case RE_AT_MATCH: St_cat_c(s, '['); decom_node(s, node->indep.arg, NULL); St_cat_m(s, "&]", 2); decom_node(s, node->indep.next, end); break; case RE_AT_NOMATCH: St_cat_c(s, '['); decom_node(s, node->indep.arg, NULL); St_cat_m(s, "^]", 2); decom_node(s, node->indep.next, end); break; case RE_AT_NWBOUND: St_cat_m(s, "B!", 2); decom_node(s, node->x.next, end); break; case RE_AT_WBOUND: St_cat_m(s, "b!", 2); decom_node(s, node->x.next, end); break; case RE_BACKREF: case RE_BACKCHECK: { String tmp; if (node->x.type == RE_BACKCHECK) { St_cat_c(s, '['); } St_init(&tmp); #if HAVE_VSNPRINTF_P St_xprintf(&tmp, "%lu", (unsigned long)node->backref.n); #else St_num(&tmp, node->backref.n); #endif St_cat(s, &tmp); St_clear(&tmp); if (node->x.type == RE_BACKCHECK) { St_cat_c(s, ']'); } else { St_cat_c(s, ESCAPE); } decom_node(s, node->backref.next, end); break; } case RE_BEGIN_CAPTURE: St_cat_c(s, '{'); decom_node(s, node->x.next, end); break; case RE_CLASS: St_cat_c(s, '\''); decom_class(s, node->class.vec); St_cat_c(s, '\''); decom_node(s, node->class.next, end); break; case RE_DEFCLASS: St_cat_c(s, cdefclass(node->defclass.vec)); St_cat_c(s, ESCAPE); decom_node(s, node->defclass.next, end); break; case RE_END_CAPTURE: St_cat_c(s, '}'); decom_node(s, node->x.next, end); break; case RE_INDEP: St_cat_c(s, '<'); decom_node(s, node->indep.arg, NULL); St_cat_c(s, '>'); decom_node(s, node->indep.next, end); break; case RE_LITERAL: decom_liter(s, node); decom_node(s, node->literal.next, end); break; case RE_N_CLASS: St_cat_m(s, "'^", 2); decom_class(s, node->class.vec); St_cat_c(s, '\''); decom_node(s, node->class.next, end); break; case RE_N_DEFCLASS: St_cat_c(s, toupper(cdefclass(node->defclass.vec))); St_cat_c(s, ESCAPE); decom_node(s, node->defclass.next, end); break; case RE_PARTIAL: St_cat_c(s, '`'); decom_liter(s, node); St_cat_c(s, '`'); break; case RE_REP_FRUGAL: case RE_REP_GREEDY: St_cat_c(s, '('); decom_node(s, node->rep.arg, node); St_cat_c(s, ')'); decom_repeat(s, node); decom_node(s, node->rep.next, end); break; case RE_SELECT: { const re_node *const be = branchend(node->select.arg, node->select.next); St_cat_c(s, '['); if (be != node->select.next) { decom_node(s, node->select.next, be); St_cat_c(s, '|'); } decom_node(s, node->select.arg, be); St_cat_c(s, '('); decom_node(s, node->select.cond, NULL); St_cat_c(s, ')'); St_cat_m(s, "?]", 2); decom_node(s, be, end); break; } case RE_STUFF_FRUGAL: St_cat_m(s, ".*?", 3); decom_node(s, node->x.next, end); break; case RE_STUFF_GREEDY: St_cat_m(s, ".*", 2); decom_node(s, node->x.next, end); break; case RE_XREP_FRUGAL: case RE_XREP_GREEDY: St_cat_c(s, '('); decom_node(s, node->rep.arg, NULL); St_cat_c(s, ')'); decom_repeat(s, node); decom_node(s, node->rep.next, end); break; } } void re_decompile(const t_regex *re, String *s) { St_zero(s); decom_node(s, re->start, NULL); }