head 1.6; access; symbols; locks; strict; comment @ * @; 1.6 date 2026.10.14.22.25.13; author agc; state dead; branches; next 1.5; commitid EvQuBHLEvZ6nMuZG; 1.5 date 2025.07.23.01.14.07; author agc; state Exp; branches; next 1.4; commitid rSrs7KEnJrB89O3G; 1.4 date 2023.06.21.23.48.08; author agc; state Exp; branches; next 1.3; commitid Dr4GIJKe5KhuaStE; 1.3 date 2023.02.24.19.01.10; author agc; state Exp; branches; next 1.2; commitid XNCIUwEY3IazkOeE; 1.2 date 2021.12.04.01.54.51; author agc; state Exp; branches; next 1.1; commitid 0yjZXZ7z7xDY0hjD; 1.1 date 2021.10.05.01.23.39; author agc; state Exp; branches; next ; commitid iWez0YTivClGMybD; desc @@ 1.6 log @Remove this old code, it's been superceded - see pkgsrc/devel/libagcre and pkgsrc/textproc/agcre @ text @/*- * Copyright (c) 2013,2017 Alistair Crooks. All Rights reserved. * All rights reserved. * * Parts of this are: * Copyright (c) 2007-2009 Russ Cox, Google Inc. All rights reserved. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include #include #include #include #include #include #include #include #include "agcre.h" /* callback struct */ typedef struct cb_t { int (*func)(uint32_t); /* function */ uint8_t negate; /* take the complement of the result */ } cb_t; /* sets are implemented as combinations of ranges, individual cases, and callbacks */ typedef struct set_t { uint32_t rangec; /* # of ranges */ uint32_t maxrange; /* size of range array */ uint32_t *ranges; /* range array */ uint32_t casec; /* # of cases */ uint32_t maxcase; /* size of case array */ uint32_t *cases; /* case array */ uint32_t callbackc; /* # of callbacks */ uint32_t maxcallback; /* size of callback array */ cb_t *callbacks; /* callback array */ uint8_t complement; /* complement of set */ } set_t; #define AT_LEAST 0xffffffff #define BOF 0xffffffffU /* a regexp token */ typedef struct retoken_t { struct retoken_t *left; /* token on left */ struct retoken_t *right; /* token on right */ uint64_t so; /* start offset */ uint32_t n; /* number */ uint32_t nparens; /* () count */ uint32_t lo; /* repeat low count */ uint32_t hi; /* repeat high count */ uint32_t ch; /* current char */ uint8_t type; /* type of token */ uint8_t lazy; /* use lazy matching */ uint8_t noncapture; /* non-capture subexpression */ uint8_t icase; /* icase token */ } retoken_t; /* token types */ #define TOK_ALT 0x01 #define TOK_BACKREF 0x02 #define TOK_BROKEN 0x03 #define TOK_CAT 0x04 #define TOK_COLLECTION 0x05 #define TOK_DOT 0x06 #define TOK_EOL 0x07 #define TOK_FORGET 0x08 #define TOK_LIT 0x09 #define TOK_PAREN 0x0a #define TOK_PLUS 0x0b #define TOK_QUEST 0x0c #define TOK_REP 0x0d #define TOK_SET TOK_COLLECTION #define TOK_STAR 0x0e #define TOK_WIDTH 0x0f #define TOK_ZEROWIDTH 0x10 /* input structure */ typedef struct input_t { const char *s; /* string */ uint64_t so; /* start offset */ uint64_t eo; /* end offset */ uint64_t c; /* current offset */ int msgc; /* # of chars in message buf */ char msg[256]; /* message buffer */ retoken_t parse; /* current token when parsing */ uint32_t parenc; /* # of parentheses */ struct re_t *re; /* pointer to internal re */ uint32_t ch; /* current char */ uint32_t prevch; /* previous char */ uint8_t bytes; /* size of current char */ uint8_t prevbytes; /* size of previous char */ uint8_t icase; /* persistent icase */ } input_t; #define AGCRE_IN_WIDTH \ (AGCRE_REG_UTF16LE | AGCRE_REG_UTF16BE | AGCRE_REG_UTF32LE | AGCRE_REG_UTF32BE) /* virtual machine instruction */ typedef struct instr_t { struct instr_t *lhs; /* lhs */ struct instr_t *rhs; /* rhs */ uint32_t n; /* character */ uint32_t gen; /* generation number */ uint8_t op; /* instruction number */ uint8_t icase; /* instruction number */ } instr_t; /* instruction opcodes */ #define OP_ANY 0x01 #define OP_BACKREF 0x02 #define OP_CHAR 0x03 #define OP_JUMP 0x04 #define OP_MATCH 0x05 #define OP_SAVE 0x06 #define OP_SET 0x07 #define OP_SPLIT 0x08 #define OP_ZEROWIDTH 0x09 /* a context structure */ typedef struct context_t { struct context_t *next; /* for freeing nodes */ uint32_t ref; /* reference count */ uint32_t nsub; /* # matches */ uint32_t c; /* chars in backref */ agcre_regmatch_t sub[1]; /* match structures */ } context_t; /* a thread structure */ typedef struct re_thread_t { instr_t *pc; /* instruction */ context_t *ctx; /* context */ } re_thread_t; /* list of threads */ typedef struct threadlist_t { uint32_t nthreads; /* # of threads */ re_thread_t t[1]; /* the threads */ } threadlist_t; #define MAGIC1 0xac1deaf0 #define MAGIC2 0x41525345 #define MAGIC3 0xd0d0d00d #define MAGIC4 0x666f7572 /* regular expression internals */ typedef struct re_t { uint32_t magic1; /* magic number #1 */ instr_t *prog; /* start of instructions */ uint32_t instrc; /* # of instructions */ uint32_t gen; /* generation number */ uint32_t setc; /* # of sets */ uint32_t maxset; /* allocated # of sets */ uint32_t magic2; /* magic number #2 */ set_t *sets; /* sets */ uint32_t flags; /* comp/exec flags */ context_t *ctxlist; /* list of contexts */ uint32_t magic3; /* magic number #3 */ instr_t *pc; /* prog counter */ uint32_t magic4; /* magic number #4 */ int msgc; /* # of chars in msg buffer */ char msg[256]; /* message buffer */ } re_t; /* * regular expressions have an implicit .* at the start to find the * first match. for anchored searches (not that many in comparison * to regular regular expressions) we need to jump over those * instructions (in the regexec phase). * Dump of compiled expression instructions for the pattern: "i" * (without quotes) * * Cat(LazyStar(Dot), Paren(0, Lit(i))) * 0. split 3, 1 * 1. any * 2. jmp 0 * 3. save 0 * 4. char i * 5. save 1 * 6. match * * so for anchored searches, we jump over the first 3 instructions */ #define LEADING_DOT_STAR_INSTRS 3 /* all static function forward declarations */ __BEGIN_DECLS static void set_free(set_t */*set*/); static int set_add_case(set_t */*set*/, uint32_t /*n*/); static int set_add_range(set_t */*set*/, uint32_t /*lo*/, uint32_t /*hi*/); static int set_add_callback(set_t */*set*/, int (*/*func*/)(uint32_t), int /*negate*/); static int set_isset(set_t */*set*/, uint32_t /*n*/); static int set_complement(set_t */*set*/); static retoken_t *parse_extended(agcre_regex_t */*re*/, input_t */*in*/); static retoken_t *parse_nospec(agcre_regex_t */*re*/, input_t */*in*/); static retoken_t *parse_basic(agcre_regex_t */*re*/, input_t */*in*/, uint32_t /*flags*/); static int get_next_token(input_t */*in*/); static int unicode_isWhite_Space(uint32_t /*ch*/); static int unicode_isDash(uint32_t /*ch*/); static int unicode_isHyphen(uint32_t /*ch*/); static int unicode_isQuotation_Mark(uint32_t /*ch*/); static int unicode_isTerminal_Punctuation(uint32_t /*ch*/); static int unicode_isHex_Digit(uint32_t /*ch*/); static int unicode_isOther_Alphabetic(uint32_t /*ch*/); static int unicode_isOther_Lowercase(uint32_t /*ch*/); static int unicode_isOther_Uppercase(uint32_t /*ch*/); static int unicode_isPattern_White_Space(uint32_t /*ch*/); static int unicode_isalnum(uint32_t /*ch*/); static int unicode_isalpha(uint32_t /*ch*/); static int unicode_ispunct2(uint32_t /*ch*/); static int unicode_isblank(uint32_t /*ch*/); static int unicode_iscntrl(uint32_t /*ch*/); static int unicode_isdigit(uint32_t /*ch*/); static int unicode_isgraph(uint32_t /*ch*/); static int unicode_islower(uint32_t /*ch*/); static int unicode_isprint(uint32_t /*ch*/); static int unicode_ispunct(uint32_t /*ch*/); static int unicode_isspace(uint32_t /*ch*/); static int unicode_isupper(uint32_t /*ch*/); static int unicode_isxdigit(uint32_t /*ch*/); static int unicode_isword(uint32_t /*ch*/); static uint32_t unicode_tolower(uint32_t /*ch*/); static uint32_t unicode_toupper(uint32_t /*ch*/); __END_DECLS #ifndef __printflike #define __printflike(n, m) __attribute__((format(printf,n,m))) #endif #ifndef howmany #define howmany(x, y) (((x)+((y)-1))/(y)) #endif /* create a new token */ static retoken_t * newtok(int type, retoken_t *left, retoken_t *right, uint8_t icase) { retoken_t *token; if ((token = calloc(1, sizeof(*token))) != NULL) { token->type = type; token->left = left; token->right = right; token->icase = icase; } return token; } /* how many instructions does tok need? */ static int count(retoken_t *tok, int *errc) { switch(tok->type) { case TOK_ALT: return 2 + count(tok->left, errc) + count(tok->right, errc); case TOK_BACKREF: case TOK_COLLECTION: case TOK_DOT: case TOK_LIT: case TOK_WIDTH: case TOK_ZEROWIDTH: return 1; case TOK_FORGET: return 0; case TOK_CAT: return count(tok->left, errc) + count(tok->right, errc); case TOK_PAREN: case TOK_STAR: return 2 + count(tok->left, errc); case TOK_PLUS: case TOK_QUEST: return 1 + count(tok->left, errc); default: *errc = 1; return 0; } } /* make a new set */ static inline set_t * newset(re_t *re) { set_t *set; if (re->setc == re->maxset) { set = realloc(re->sets, (re->maxset + 8) * sizeof(*set)); if (set == NULL) { //error_message(in, "can't extend sets past %u", in->re->maxset); return NULL; } memset(&set[re->setc], 0x0, 8 * sizeof(*set)); re->maxset += 8; re->sets = set; } return &re->sets[re->setc++]; } /* take parse tokens, and emit vm instructions */ static int emit(re_t *re, retoken_t *tok) { instr_t *p1; instr_t *p2; instr_t *t; set_t *set; switch(tok->type) { case TOK_ALT: re->pc->op = OP_SPLIT; p1 = re->pc++; p1->lhs = re->pc; emit(re, tok->left); re->pc->op = OP_JUMP; p2 = re->pc++; p1->rhs = re->pc; emit(re, tok->right); p2->lhs = re->pc; return 1; case TOK_BACKREF: re->pc->op = OP_BACKREF; re->pc->n = tok->ch; re->pc->icase = tok->icase; re->pc++; return 1; case TOK_CAT: emit(re, tok->left); emit(re, tok->right); return 1; case TOK_COLLECTION: re->pc->op = OP_SET; re->pc->n = tok->ch; re->pc->icase = tok->icase; re->pc++; return 1; case TOK_DOT: re->pc++->op = OP_ANY; return 1; case TOK_LIT: re->pc->op = OP_CHAR; re->pc->n = tok->ch; re->pc->icase = tok->icase; re->pc++; return 1; case TOK_PAREN: re->pc->op = OP_SAVE; re->pc->n = 2*tok->nparens; re->pc++; emit(re, tok->left); re->pc->op = OP_SAVE; re->pc->n = 2*tok->nparens + 1; re->pc++; return 1; case TOK_PLUS: p1 = re->pc; emit(re, tok->left); re->pc->op = OP_SPLIT; re->pc->lhs = p1; p2 = re->pc; re->pc++; p2->rhs = re->pc; if (tok->lazy) { t = p2->lhs; p2->lhs = p2->rhs; p2->rhs = t; } return 1; case TOK_QUEST: re->pc->op = OP_SPLIT; p1 = re->pc++; p1->lhs = re->pc; emit(re, tok->left); p1->rhs = re->pc; if (tok->lazy) { t = p1->lhs; p1->lhs = p1->rhs; p1->rhs = t; } return 1; case TOK_STAR: re->pc->op = OP_SPLIT; p1 = re->pc++; p1->lhs = re->pc; emit(re, tok->left); re->pc->op = OP_JUMP; re->pc->lhs = p1; re->pc++; p1->rhs = re->pc; if (tok->lazy) { t = p1->lhs; p1->lhs = p1->rhs; p1->rhs = t; } return 1; case TOK_WIDTH: re->pc->op = OP_SET; re->pc->n = re->setc; re->pc->icase = tok->icase; if ((set = newset(re)) == NULL) { return 0; } set_add_callback(set, (tok->ch == 'd' || tok->ch == 'D') ? unicode_isdigit : (tok->ch == 'p' || tok->ch == 'P') ? unicode_isprint : (tok->ch == 's' || tok->ch == 'S') ? unicode_isspace : unicode_isword, unicode_isupper(tok->ch)); re->pc++; return 1; case TOK_ZEROWIDTH: re->pc->op = OP_ZEROWIDTH; re->pc->n = tok->ch; re->pc++; return 1; } return 1; } /* recursive function to free a token and its children */ static void freetok(retoken_t *tok) { if (tok) { freetok(tok->left); freetok(tok->right); free(tok); } } /* recursive function to print a token and its children */ static void print_token(retoken_t *tok) { if (tok->icase) { printf("Icase+"); } switch(tok->type) { case TOK_ALT: printf("Alt("); print_token(tok->left); printf(", "); print_token(tok->right); printf(")"); break; case TOK_BACKREF: printf("Backref(%d)", tok->ch); break; case TOK_CAT: printf("Cat("); print_token(tok->left); printf(", "); print_token(tok->right); printf(")"); break; case TOK_COLLECTION: printf("Set(%u)", tok->ch); break; case TOK_DOT: printf("Dot"); break; case TOK_LIT: printf("Lit(%c)", tok->ch); break; case TOK_PAREN: printf("Paren(%d, ", tok->nparens); print_token(tok->left); printf(")"); break; case TOK_PLUS: if (tok->lazy) { printf("Lazy"); } printf("Plus("); print_token(tok->left); printf(")"); break; case TOK_QUEST: if (tok->lazy) { printf("Lazy"); } printf("Quest("); print_token(tok->left); printf(")"); break; case TOK_STAR: if (tok->lazy) { printf("Lazy"); } printf("Star("); print_token(tok->left); printf(")"); break; case TOK_WIDTH: printf("Width(%c)", tok->ch); break; case TOK_ZEROWIDTH: printf("Zerowidth(%c)", tok->ch); break; default: printf("???"); break; } } /* print all the instructions in the program */ static int printprog(re_t *re) { uint32_t pc; instr_t *instr; for (pc = 0, instr = re->prog ; pc < re->instrc ; pc++, instr++) { switch(instr->op) { case OP_ANY: printf("%2d. any\n", pc); break; case OP_BACKREF: printf("%2d. backref %d\n", pc, instr->n); break; case OP_CHAR: printf("%2d. char %c\n", pc, instr->n); break; case OP_JUMP: printf("%2d. jmp %d\n", pc, (int)(instr->lhs - re->prog)); break; case OP_MATCH: printf("%2d. match\n", pc); break; case OP_SAVE: printf("%2d. save %d\n", pc, instr->n); break; case OP_SET: printf("%2d. set %d\n", pc, instr->n); break; case OP_SPLIT: printf("%2d. split %d, %d\n", pc, (int)(instr->lhs - re->prog), (int)(instr->rhs - re->prog)); break; case OP_ZEROWIDTH: printf("%2d. zerowidth(%c)\n", pc, instr->n); break; default: fprintf(stderr, "printprog - bad type %d\n", instr->op); return 0; } } return 1; } static retoken_t *rec_repeat(input_t *in); /* add a warning message */ static __printflike(2,3) void error_message(input_t *in, const char *fmt, ...) { va_list args; if (in->msgc == 0) { /* don't overwrite previous messages */ va_start(args, fmt); in->msgc = vsnprintf(in->msg, sizeof(in->msg), fmt, args); va_end(args); } } /* check current character is as expected, then get next token */ static int accept_char(input_t *in, uint32_t expected) { int ret; ret = 1; if (in->parse.ch != expected) { error_message(in, "expected: '%c', got '%c'", expected, in->s[in->c]); ret = 0; } get_next_token(in); return ret; } /* clone a token */ static retoken_t * clone_token(input_t *in, retoken_t *orig) { retoken_t *token; if ((token = newtok(orig->type, NULL, NULL, orig->icase)) == NULL) { return NULL; } token->lazy = orig->lazy; token->nparens = orig->nparens; token->ch = orig->ch; if (orig->left) { token->left = clone_token(in, orig->left); } if (orig->right) { token->right = clone_token(in, orig->right); } return token; } /* concat two subexpressions together */ static retoken_t * rec_concat(input_t *in, retoken_t *token) { retoken_t *rhs; retoken_t *cat; while (in->parse.type != TOK_EOL && in->parse.type != TOK_ALT && in->parse.ch != ')') { if ((rhs = rec_repeat(in)) == NULL || (cat = newtok(TOK_CAT, token, rhs, 0)) == NULL || (token = rec_concat(in, cat)) == NULL) { return NULL; } } return token; } /* recognise an alternate */ static retoken_t * rec_alt(input_t *in) { retoken_t *repeat; retoken_t *token; retoken_t *cat; retoken_t *alt; if ((repeat = rec_repeat(in)) == NULL || (token = rec_concat(in, repeat)) == NULL) { return NULL; } while (in->parse.type == TOK_ALT) { if (!accept_char(in, '|')) { return NULL; } if ((repeat = rec_repeat(in)) == NULL || (cat = rec_concat(in, repeat)) == NULL || (alt = newtok(TOK_ALT, token, cat, 0)) == NULL || (token = rec_concat(in, alt)) == NULL) { return NULL; } } return token; } /* recognise a single atom */ static retoken_t * rec_single(input_t *in) { retoken_t *token; retoken_t *alt; int parenc; token = NULL; switch(in->parse.type) { case TOK_PAREN: accept_char(in, '('); if (in->parse.noncapture) { if ((token = rec_alt(in)) == NULL) { return NULL; } } else { parenc = ++in->parenc; if ((alt = rec_alt(in)) == NULL || (token = newtok(TOK_PAREN, alt, NULL, 0)) == NULL) { return NULL; } token->nparens = parenc; } if (!accept_char(in, ')')) { return NULL; } break; case TOK_BACKREF: if ((token = newtok(TOK_BACKREF, NULL, NULL, in->parse.icase)) == NULL) { return NULL; } if (in->parse.ch > in->parenc) { error_message(in, "backref %d out of range", in->ch); return NULL; } accept_char(in, token->ch = in->parse.ch); break; case TOK_DOT: case TOK_LIT: case TOK_COLLECTION: case TOK_WIDTH: case TOK_ZEROWIDTH: if ((token = newtok(in->parse.type, NULL, NULL, in->parse.icase)) == NULL) { return NULL; } token->ch = in->parse.ch; token->icase = in->parse.icase; get_next_token(in); break; } return token; } /* a repetition of subexpressions */ static retoken_t * rec_repeat(input_t *in) { retoken_t *cloned; retoken_t *quest; retoken_t *token; retoken_t *orig; uint32_t i; if ((token = rec_single(in)) == NULL) { return NULL; } orig = token; switch(in->parse.type) { case TOK_STAR: case TOK_PLUS: case TOK_QUEST: if ((token = newtok(in->parse.type, token, NULL, in->parse.icase)) == NULL) { return NULL; } token->lazy = in->parse.lazy; get_next_token(in); break; case TOK_REP: if (in->parse.lo == 0 && in->parse.hi == 0) { orig->type = TOK_FORGET; } for (i = 1 ; i < in->parse.lo ; i++) { if ((cloned = clone_token(in, orig)) == NULL || (token = newtok(TOK_CAT, token, cloned, in->parse.icase)) == NULL) { return NULL; } } if (in->parse.hi == AT_LEAST) { if ((token = newtok(TOK_PLUS, token, NULL, in->parse.icase)) == NULL) { return NULL; } } else { for ( ; i < in->parse.hi ; i++) { if ((cloned = clone_token(in, orig)) == NULL || (quest = newtok(TOK_QUEST, cloned, NULL, in->parse.icase)) == NULL || (token = newtok(TOK_CAT, token, quest, in->parse.icase)) == NULL) { return NULL; } } } get_next_token(in); break; } return token; } /* recognise literal tokens in nospec expression */ static retoken_t * nospec_token(input_t *in) { retoken_t *tok; tok = newtok(TOK_LIT, NULL, NULL, 0); tok->ch = in->s[in->c++]; if (in->c == in->eo) { return tok; } return newtok(TOK_CAT, tok, nospec_token(in), 0); } /* either start of line, or start of nested subexpression */ #define BASIC_IS_START(i, in) \ ((i) == (in) || ((size_t)(i - in) >= 2 && (i)[-2] == '\\' && (i)[-1] == '(')) #define BASIC_IS_END(i, in, sz) \ (((size_t)((i) - (in)) == (sz) - 1) || ((i)[1] == '\\' && (i)[2] == ')')) /* convert a basic regexp into an extended one */ static ssize_t regextend(const char *in, size_t insize, char *out, size_t outsize, uint32_t flags) { const char *i; char *o; for (i = in, o = out ; (size_t)(i - in) < insize && (size_t)(o - out) < outsize ; i++) { switch(*i) { case '+': case '|': case '?': case '{': case '}': case '(': case ')': /* +, |, ?, {, }, (, ) are ordinary characters */ *o++ = '\\'; *o++ = *i; break; case '\\': switch(i[1]) { case '(': case ')': case '{': case '}': /* basic bounds delimiters are \{ and \} */ /* basic nested subexpressions are \( and \) */ *o++ = *++i; break; default: /* pass through other backslash-escaped chars */ *o++ = *i; break; } break; case '^': case '$': /* ^ is an ordinary char, except at start */ /* $ is an ordinary char, except at end */ if ((*i == '^' && !BASIC_IS_START(i, in)) || (*i == '$' && !BASIC_IS_END(i, in, insize))) { *o++ = '\\'; } *o++ = *i; break; case '*': if (flags & AGCRE_REG_CTAGS) { /* * is an ordinary character - see ctags */ *o++ = '\\'; *o++ = *i; } else { /* THIS IS WHAT THE RE_FORMAT PAGE SAYS FOR '*' not for ctags, though */ if ((*i == '*' && BASIC_IS_START(i, in))) { *o++ = '\\'; } *o++ = *i; } break; default: *o++ = *i; break; } } *o = 0x0; return (ssize_t)(o - out); } /* parse the string */ static retoken_t * parse_string(input_t *in) { retoken_t *dotstar; retoken_t *token; retoken_t *cat; retoken_t *alt; get_next_token(in); if ((alt = rec_alt(in)) == NULL) { return NULL; } /* make pattern ".*?(PATTERN)" */ if ((token = newtok(TOK_PAREN, alt, NULL, 0)) == NULL || (cat = newtok(TOK_DOT, NULL, NULL, 0)) == NULL || (dotstar = newtok(TOK_STAR, cat, NULL, 0)) == NULL) { return NULL; } dotstar->lazy = 1; return newtok(TOK_CAT, dotstar, token, 0); } /* parse an extended reg exp */ static retoken_t * parse_extended(agcre_regex_t *agcre, input_t *in) { retoken_t *entry; re_t *re; re = agcre->re_g; if ((entry = parse_string(in)) == 0) { memcpy(re->msg, in->msg, in->msgc); return 0; } agcre->re_nsub = in->parenc + 1; return entry; } /* parse a nospec regexp */ static retoken_t * parse_nospec(agcre_regex_t *agcre, input_t *in) { retoken_t *dotstar; retoken_t *tok; tok = nospec_token(in); tok = newtok(TOK_PAREN, tok, NULL, 0); dotstar = newtok(TOK_STAR, newtok(TOK_DOT, NULL, NULL, 0), NULL, 0); dotstar->lazy = 1; tok = newtok(TOK_CAT, dotstar, tok, 0); agcre->re_nsub = in->parenc + 1; return tok; } /* convert basic regexp to extended then parse */ static retoken_t * parse_basic(agcre_regex_t *agcre, input_t *in, uint32_t flags) { ssize_t size; char s[AGCRE_MAX_EXPR_LENGTH * 4]; size = regextend(&in->s[in->so], in->eo - in->so, s, sizeof(s), flags); in->s = s; in->so = 0; in->eo = size; return parse_extended(agcre, in); } #define BOL 0xffffffffU /* unwrap a character, including UTF-8 chars, into 32bit char */ static inline int unwrap_utf8(input_t *in) { uint32_t n; uint32_t j; in->ch = in->s[in->c]; if (in->ch <= 0x7f) { /* 0XXX XXXX one byte */ in->bytes = 1; n = in->ch; } else if ((in->ch & 0xe0) == 0xc0) { /* 110X XXXX 2 bytes */ in->bytes = 2; n = (in->ch & 0x1f); } else if ((in->ch & 0xf0) == 0xe0) { /* 1110 XXXX three bytes */ in->bytes = 3; n = (in->ch & 0x0f); } else if ((in->ch & 0xf8) == 0xf0) { /* 1111 0XXX four bytes */ in->bytes = 4; n = (in->ch & 0x07); } else if ((in->ch & 0xfc) == 0xf8) { /* 1111 10XX five bytes */ in->bytes = 5; n = (in->ch & 0x03); } else if ((in->ch & 0xfe) == 0xfc) { /* 1111 110X six bytes */ in->bytes = 6; n = (in->ch & 0x01); } else { return 0; } if (in->c + in->bytes - 1 > in->eo) { return 0; } for (j = 1 ; j < in->bytes ; j++) { n = (n << 6) | (in->s[in->c + j] & 0x3f); } in->ch = n; return 1; } /* return 1 if host is bigendian */ static inline int host_is_bigendian(void) { int indian = 1; return (*(char *)(void *)&indian) ? 0 : 1; } /* swap 32bit integer */ static inline uint32_t swap32(uint32_t x) { x = ((x & 0x0000ffff) << 16) | ((x & 0xffff0000) >> 16); x = ((x & 0x00ff00ff) << 8) | ((x & 0xff00ff00) >> 8); return x; } /* swap 16bit integer */ static inline uint32_t swap16(uint16_t x) { return ((x & 0x00ff) << 8) | ((x & 0xff00) >> 8); } /* higher level get-next-char function */ static inline int get_next_char(input_t *in, uint32_t flags) { uint32_t i32; uint16_t i16; in->prevch = in->ch; in->prevbytes = in->bytes; switch(flags & AGCRE_IN_WIDTH) { case AGCRE_REG_UTF16LE: in->bytes = 1; memcpy(&i16, &in->s[in->c * 2], 2); in->ch = (host_is_bigendian()) ? swap16(i16) : i16; return 1; case AGCRE_REG_UTF16BE: in->bytes = 1; memcpy(&i16, &in->s[in->c * 2], 2); in->ch = (!host_is_bigendian()) ? swap16(i16) : i16; return 1; case AGCRE_REG_UTF32LE: in->bytes = 1; memcpy(&i32, &in->s[in->c * 4], 4); in->ch = (host_is_bigendian()) ? swap32(i32) : i32; return 1; case AGCRE_REG_UTF32BE: in->bytes = 1; memcpy(&i32, &in->s[in->c * 4], 4); in->ch = (!host_is_bigendian()) ? swap32(i32) : i32; return 1; default: return unwrap_utf8(in); } } /* return the number of bytes in a context */ static inline uint32_t context_bytes(uint32_t n) { return sizeof(context_t) + (n * sizeof(agcre_regmatch_t)); } /* create a new context */ static context_t * make_new_context(re_t *re, int n) { context_t *ctx; if ((ctx = re->ctxlist) != NULL) { re->ctxlist = ctx->next; memset(ctx, 0x0, context_bytes(n)); } else { ctx = calloc(1, context_bytes(n)); } ctx->nsub = n; ctx->ref = 1; return ctx; } /* increment reference count in the context */ static inline context_t * incref(context_t *ctx) { ctx->ref += 1; return ctx; } /* save the current offset in the match context */ static context_t * mark(re_t *re, context_t *ctx, int i, input_t *in, int delta) { context_t *newctx; uint32_t j; if (ctx->ref > 1) { newctx = make_new_context(re, ctx->nsub); for (j = 0; j < ctx->nsub; j++) { newctx->sub[j] = ctx->sub[j]; } ctx->ref -= 1; ctx = newctx; } if (i % 2 == 0) { ctx->sub[i / 2].rm_so = in->c + delta; } else { ctx->sub[i / 2].rm_eo = in->c + delta; } return ctx; } /* decrement reference count in the context */ static inline void decref(re_t *re, context_t *ctx) { if (--ctx->ref == 0) { ctx->next = re->ctxlist; re->ctxlist = ctx; } } /* create a new thread */ static re_thread_t newthread(instr_t *pc, context_t *ctx) { re_thread_t t = {pc, ctx}; return t; } /* create a new thread list */ static threadlist_t * threadlist(uint32_t instrc) { return calloc(1, sizeof(threadlist_t) + (instrc * sizeof(re_thread_t))); } /* add a new thread to the list */ static int addthread(re_t *re, threadlist_t *list, re_thread_t t, input_t *in, int delta, int width) { context_t *ctx; if (width) { /* we don't check generation for 0-width matches */ if (t.pc->gen == re->gen) { decref(re, t.ctx); return 1; } t.pc->gen = re->gen; } switch(t.pc->op) { case OP_JUMP: addthread(re, list, newthread(t.pc->lhs, t.ctx), in, delta, width); break; case OP_SPLIT: addthread(re, list, newthread(t.pc->lhs, incref(t.ctx)), in, delta, width); addthread(re, list, newthread(t.pc->rhs, t.ctx), in, delta, width); break; case OP_SAVE: if ((ctx = mark(re, t.ctx, t.pc->n, in, delta)) == NULL) { return 0; } addthread(re, list, newthread(t.pc+1, ctx), in, delta, width); break; default: list->t[list->nthreads++] = t; break; } return 1; } /* return 1 at beginning of line */ static inline int isbegline(re_t *re, input_t *in) { return (re->flags & AGCRE_REG_NOTBOL) ? 0 : (in->prevch == '\n' || in->prevch == BOL); } /* return 1 at end of line */ static inline int isendline(re_t *re, input_t *in) { return (re->flags & AGCRE_REG_NOTEOL) ? 0 : in->c == in->eo; } /* return 1 at beginning of words */ static inline int isbegword(re_t *re, input_t *in) { return (isbegline(re, in) || ((!unicode_isword(in->prevch)) && unicode_isword(in->ch))); } /* return 1 at end of words */ static inline int isendword(re_t *re, input_t *in) { return (isendline(re, in) || ((in->c > in->so && unicode_isword(in->prevch) && !unicode_isword(in->ch)))); } /* do the chars match? */ static inline int charmatch(re_t *re, instr_t *instr, uint32_t ch, uint32_t wanted) { if ((re->flags & AGCRE_REG_ICASE) || instr->icase) { return unicode_tolower(ch) == unicode_tolower(wanted); } return (ch == wanted); } /* can we match "any" character? */ static inline int anymatch(re_t *re, input_t *in) { if ((re->flags & AGCRE_REG_NEWLINE) && in->ch == '\n') { return 0; } return (in->c < in->eo); } /* are the chars in the set? */ static inline int setmatch(re_t *re, set_t *set, input_t *in, instr_t *instr) { if ((re->flags & AGCRE_REG_ICASE) || instr->icase) { return set_isset(set, unicode_tolower(in->ch)) || set_isset(set, unicode_toupper(in->ch)); } return set_isset(set, in->ch); } /* is this a zerowidth match? */ static inline int zeromatch(re_t *re, uint32_t type, input_t *in) { switch(type) { case '^': return isbegline(re, in); case '$': return isendline(re, in); case '<': return isbegword(re, in); case '>': return isendword(re, in); case 'b': return isbegword(re, in) || isendword(re, in); } return 0; } /* we take the leftmost longest match */ static inline int is_better_match(context_t *ctx, context_t *prev) { agcre_regoff_t prevlen; agcre_regoff_t ctxlen; prevlen = (prev) ? prev->sub[0].rm_eo - prev->sub[0].rm_so : -1; ctxlen = ctx->sub[0].rm_eo - ctx->sub[0].rm_so; if (ctxlen > prevlen) { return 1; } return (ctxlen == prevlen) ? (ctx->sub[0].rm_so < prev->sub[0].rm_so) : 0; } /* get length of utf16 string in 16bit chars */ static inline size_t strlen16(const uint16_t *s) { uint32_t i; for (i = 0 ; s[i] != 0x0000 ; i++) { } return i; } /* get length of utf32 string in 32bit chars */ static inline size_t strlen32(const uint32_t *s) { uint32_t i; for (i = 0 ; s[i] != 0 ; i++) { } return i; } /* get length of string in terms of bytes */ static inline uint32_t get_length_in_bytes(const void *vs, uint32_t flags) { switch(flags & AGCRE_IN_WIDTH) { case AGCRE_REG_UTF16LE: case AGCRE_REG_UTF16BE: return strlen16(vs) * 2; case AGCRE_REG_UTF32LE: case AGCRE_REG_UTF32BE: return strlen32(vs) * 4; default: return strlen(vs); } } /* free all contexts */ static inline void free_contexts(context_t *ctx) { context_t *next; for ( ; ctx ; ctx = next) { next = ctx->next; free(ctx); } } /* unwrap a character, including UTF-8 chars, into 32bit char */ static inline int lex_unwrap_utf8(input_t *in) { uint32_t n; uint32_t j; in->ch = in->s[in->c]; if (in->ch <= 0x7f) { /* 0XXX XXXX one byte */ in->bytes = 1; n = in->ch; } else if ((in->ch & 0xe0) == 0xc0) { /* 110X XXXX 2 bytes */ in->bytes = 2; n = (in->ch & 0x1f); } else if ((in->ch & 0xf0) == 0xe0) { /* 1110 XXXX three bytes */ in->bytes = 3; n = (in->ch & 0x0f); } else if ((in->ch & 0xf8) == 0xf0) { /* 1111 0XXX four bytes */ in->bytes = 4; n = (in->ch & 0x07); } else if ((in->ch & 0xfc) == 0xf8) { /* 1111 10XX five bytes */ in->bytes = 5; n = (in->ch & 0x03); } else if ((in->ch & 0xfe) == 0xfc) { /* 1111 110X six bytes */ in->bytes = 6; n = (in->ch & 0x01); } else { return 0; } if (in->c + in->bytes - 1 > in->eo) { return 0; } for (j = 1 ; j < in->bytes ; j++) { n = (n << 6) | (in->s[in->c + j] & 0x3f); } in->ch = n; in->c += in->bytes; return 1; } /* return 1 if host is bigendian */ static inline int lex_host_is_bigendian(void) { int indian = 1; return (*(char *)(void *)&indian) ? 0 : 1; } /* swap 32bit integer */ static inline uint32_t lex_swap32(uint32_t x) { x = ((x & 0x0000ffff) << 16) | ((x & 0xffff0000) >> 16); x = ((x & 0x00ff00ff) << 8) | ((x & 0xff00ff00) >> 8); return x; } /* swap 16bit integer */ static inline uint32_t lex_swap16(uint16_t x) { return ((x & 0x00ff) << 8) | ((x & 0xff00) >> 8); } /* return the next char */ static inline int in_nextchar(input_t *in) { uint32_t i32; uint16_t i16; if (in->c == in->eo) { return 0; } in->prevch = in->ch; in->prevbytes = in->bytes; switch(in->re->flags & AGCRE_IN_WIDTH) { case AGCRE_REG_UTF16LE: in->bytes = 2; memcpy(&i16, &in->s[in->c], in->bytes); in->ch = (lex_host_is_bigendian()) ? lex_swap16(i16) : i16; in->c += in->bytes; return 1; case AGCRE_REG_UTF16BE: in->bytes = 2; memcpy(&i16, &in->s[in->c], in->bytes); in->ch = (!lex_host_is_bigendian()) ? lex_swap16(i16) : i16; in->c += in->bytes; return 1; case AGCRE_REG_UTF32LE: in->bytes = 4; memcpy(&i32, &in->s[in->c], in->bytes); in->ch = (lex_host_is_bigendian()) ? lex_swap32(i32) : i32; in->c += in->bytes; return 1; case AGCRE_REG_UTF32BE: in->bytes = 4; memcpy(&i32, &in->s[in->c], in->bytes); in->ch = (!lex_host_is_bigendian()) ? lex_swap32(i32) : i32; in->c += in->bytes; return 1; default: return lex_unwrap_utf8(in); } } /* look ahead */ static inline uint32_t in_peek(input_t *in, int32_t delta) { return in->s[in->c + delta]; } /* keep an error message, only if we don't have one already */ static int lex_error_message(input_t *in, const char *fmt, ...) { va_list args; if (in->msgc == 0) { va_start(args, fmt); in->msgc = vsnprintf(in->msg, sizeof(in->msg), fmt, args); va_end(args); } return TOK_BROKEN; } /* do we have a lazy marker? */ static inline void lazy(input_t *in, retoken_t *token) { if (in_peek(in, 0) == '?') { in_nextchar(in); token->lazy = 1; } } /* get a number, up to width digits wide */ static inline int get_number(input_t *in, uint32_t *num, uint32_t width, uint32_t base) { static const char *hex = "0123456789abcdef"; const char *p; uint32_t i; for (*num = 0, i = 0 ; i < width ; i++) { if ((p = strchr(hex, in_peek(in, i))) == NULL || (uint32_t)(p - hex) >= base) { break; } *num = (*num * base) + (uint32_t)(p - hex); } if (i > width) { return 0; } in->c += i; return 1; } /* recognise a specific, bounded repeat */ static inline int rep(input_t *in) { retoken_t *parse; parse = &in->parse; if (!get_number(in, &parse->lo, 4, 10)) { return lex_error_message(in, "number too large '%.6s", &in->s[parse->so]); } parse->hi = parse->lo; if (in_peek(in, 0) == ',') { in_nextchar(in); if (!get_number(in, &parse->hi, 4, 10)) { return lex_error_message(in, "number too large '%.6s", &in->s[parse->so]); } if (parse->hi == 0) { parse->hi = AT_LEAST; } } if (parse->lo > parse->hi) { return lex_error_message(in, "low %u > hi %u", parse->lo, parse->hi); } in_nextchar(in); if (in->ch != '}') { return lex_error_message(in, "expected } at end of repeat", &in->s[parse->so]); } return TOK_REP; } /* recognise a backslash sequence */ static int rec_backslash(input_t *in, retoken_t *token, int want_backrefs) { in_nextchar(in); switch(token->ch = in->ch) { case 'u': if (!get_number(in, &token->ch, 4, 16)) { return lex_error_message(in, "bad unicode character '%.6s", &in->s[token->so]); } break; case 'n': token->ch = '\n'; return TOK_LIT; case 'r': token->ch = '\r'; return TOK_LIT; case 't': token->ch = '\t'; return TOK_LIT; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': in->c -= in->prevbytes; if (want_backrefs && get_number(in, &token->ch, 2, 10)) { return TOK_BACKREF; } break; default: if (strchr("<>b", token->ch) != NULL) { return TOK_ZEROWIDTH; } if (strchr("DPSWdpsw", token->ch) != NULL) { return TOK_WIDTH; } break; } return TOK_LIT; } /* function to calculate a hash, used in stringswitch */ static uint32_t djbhashn(const char *s, size_t len) { uint32_t hash; for (hash = 5381; len-- > 0 ; ) { hash = hash * 33 + *s++; } return hash + (hash >> 5); } /* recognise a posix class */ static int rec_posix_class(input_t *in, set_t *set) { char *p; if ((p = memchr(&in->s[in->c], ']', 10)) == NULL) { return 0; } switch(djbhashn(&in->s[in->c], (size_t)(p - &in->s[in->c]) + 1)) { case /* ":alnum:]" */ 0x32ef56fd: set_add_callback(set, unicode_isalnum, 0); in->c += 8; return 1; case /* ":alpha:]" */ 0x330d1aee: set_add_callback(set, unicode_isalpha, 0); in->c += 8; return 1; case /* ":blank:]" */ 0x815acf00: set_add_callback(set, unicode_isblank, 0); in->c += 8; return 1; case /* ":cntrl:]" */ 0xd6f15906: set_add_callback(set, unicode_iscntrl, 0); in->c += 8; return 1; case /* ":digit:]" */ 0x1154c1e2: set_add_callback(set, unicode_isdigit, 0); in->c += 8; return 1; case /* ":graph:]" */ 0xcb51807: set_add_callback(set, unicode_isgraph, 0); in->c += 8; return 1; case /* ":lower:]" */ 0x8bfc6af8: set_add_callback(set, unicode_islower, 0); in->c += 8; return 1; case /* ":print:]" */ 0xc7bbf92b: set_add_callback(set, unicode_isprint, 0); in->c += 8; return 1; case /* ":punct:]" */ 0xcf4a84ca: set_add_callback(set, unicode_ispunct, 0); in->c += 8; return 1; case /* ":punct2:]" */ 0xf09af6aa: set_add_callback(set, unicode_ispunct2, 0); in->c += 9; return 1; case /* ":space:]" */ 0xa876bcf2: set_add_callback(set, unicode_isspace, 0); in->c += 8; return 1; case /* ":upper:]" */ 0x40541fdb: set_add_callback(set, unicode_isupper, 0); in->c += 8; return 1; case /* ":xdigit:]" */ 0x24758e84: set_add_callback(set, unicode_isxdigit, 0); in->c += 9; return 1; case /* ":word:]" */ 0x96b11914: set_add_callback(set, unicode_isword, 0); in->c += 7; return 1; default: return 0; } } /* recognise a set */ static int rec_set(input_t *in) { const int nobackrefs = 0; retoken_t *token; retoken_t bs; uint32_t prevch; set_t *set; int complement; int done; int ch; if (memcmp(&in->s[in->c], "[:<:]]", 6) == 0 || memcmp(&in->s[in->c], "[:>:]]", 6) == 0) { in->parse.ch = in->s[in->c + 2]; in->c += 6; return TOK_ZEROWIDTH; } if (in->re->setc == in->re->maxset) { set = realloc(in->re->sets, (in->re->maxset + 8) * sizeof(*set)); if (set == NULL) { return lex_error_message(in, "can't extend sets past %u", in->re->maxset); } memset(&set[in->re->setc], 0x0, 8 * sizeof(*set)); in->re->maxset += 8; in->re->sets = set; } set = &in->re->sets[in->parse.ch = in->re->setc++]; token = &in->parse; complement = 0; if (in_peek(in, 0) == '^') { complement = 1; set_complement(set); in_nextchar(in); } for (done = 0, prevch = in->prevch ; !done && in_nextchar(in) ; ) { switch(ch = in->ch) { case '\\': memset(&bs, 0x0, sizeof(bs)); switch (rec_backslash(in, &bs, nobackrefs)) { case TOK_BROKEN: return lex_error_message(in, "bad backslash '%.10s'", &in->s[token->so]); case TOK_LIT: set_add_case(set, bs.ch); break; case TOK_WIDTH: set_add_callback(set, (token->ch == 'd' || token->ch == 'D') ? unicode_isdigit : (token->ch == 'p' || token->ch == 'P') ? unicode_isprint : (token->ch == 's' || token->ch == 'S') ? unicode_isspace : unicode_isword, unicode_isupper((uint8_t)token->ch)); break; } break; case '[': if (!rec_posix_class(in, set)) { return lex_error_message(in, "bad posix class '%.30s'", &in->s[token->so]); } break; case ']': if (in->c == token->so + complement + 2) { set_add_case(set, ']'); } else { done = 1; } break; case '-': if (in->c == token->so + complement + 2) { set_add_case(set, '-'); } else { prevch = in->prevch; in_nextchar(in); set_add_range(set, prevch, in->ch); } break; default: set_add_case(set, ch); break; } } if (in->ch != ']') { return lex_error_message(in, "expected ']' at end of set: %s", &in->s[token->so]); } return TOK_SET; } /* lexer function */ static int get_next_token(input_t *in) { const int backrefs = 1; retoken_t *token = &in->parse; memset(token, 0x0, sizeof(*token)); token->so = in->c; if (!in_nextchar(in)) { return token->type = TOK_EOL; } token->icase = in->icase; switch(token->ch = in->ch) { case '(': if (in_peek(in, 0) == '?') { if (in_peek(in, 1) == ':') { in->c += 2; token->noncapture = 1; } if (in_peek(in, 1) == 'i') { in->c += 3; in->icase = 1; return get_next_token(in); } if (in_peek(in, 1) == '-' && in_peek(in, 2) == 'i') { in->c += 4; in->icase = 0; return get_next_token(in); } } return token->type = TOK_PAREN; case ')': return token->type = TOK_PAREN; case '?': lazy(in, token); return token->type = TOK_QUEST; case '*': lazy(in, token); return token->type = TOK_STAR; case '+': lazy(in, token); return token->type = TOK_PLUS; case '|': return token->type = TOK_ALT; case '{': return token->type = rep(in); case '^': case '$': return token->type = TOK_ZEROWIDTH; case '[': return token->type = rec_set(in); case '.': return token->type = TOK_DOT; case '\\': return token->type = rec_backslash(in, token, backrefs); default: return token->type = TOK_LIT; } } /* free resources used by a set */ static void set_free(set_t *set) { free(set->ranges); free(set->cases); free(set->callbacks); } /* add a single 'case' to a set - a single member */ static int set_add_case(set_t *set, uint32_t n) { uint32_t *v; if (set->casec == set->maxcase) { v = realloc(set->cases, (set->maxcase + 16) * sizeof(*v)); if (v == NULL) { fprintf(stderr, "set_add_case: failure\n"); return 0; } set->maxcase += 16; set->cases = v; } set->cases[set->casec++] = n; return 1; } /* add a range to a set */ static int set_add_range(set_t *set, uint32_t lo, uint32_t hi) { uint32_t *v; if (set->rangec == set->maxrange) { v = realloc(set->ranges, (set->maxrange + 16) * sizeof(*v)); if (v == NULL) { fprintf(stderr, "set_add_range: failure\n"); return 0; } set->maxrange += 16; set->ranges = v; } set->ranges[set->rangec++] = lo; set->ranges[set->rangec++] = hi; return 1; } /* add a callback function to a set */ static int set_add_callback(set_t *set, int (*func)(uint32_t), int negate) { cb_t *v; if (set->callbackc == set->maxcallback) { v = realloc(set->callbacks, (set->maxcallback + 16) * sizeof(*v)); if (v == NULL) { fprintf(stderr, "set_add_callback: failure\n"); return 0; } set->maxcallback += 16; set->callbacks = v; } set->callbacks[set->callbackc].func = func; set->callbacks[set->callbackc++].negate = negate; return 1; } /* test if a number is present in the set */ static int set_isset(set_t *set, uint32_t n) { uint32_t i; for (i = 0 ; i < set->casec ; i++) { if (set->cases[i] == n) { return 1 - set->complement; } } for (i = 0 ; i < set->rangec ; i += 2) { if (n >= set->ranges[i] && n <= set->ranges[i + 1]) { return 1 - set->complement; } } for (i = 0 ; i < set->callbackc ; i += 2) { if ((*set->callbacks[i].func)(n) == 1 - set->callbacks[i].negate) { return 1 - set->complement; } } return set->complement; } /* set the complement flag */ static int set_complement(set_t *set) { return set->complement = 1 - set->complement; } #define RANGE(a, b) do { \ if (ch >= (a) && ch <= (b)) { \ return 1; \ } \ } while(/*CONSTCOND*/0) /* return 1 if ch has White Space property */ static int unicode_isWhite_Space(uint32_t ch) { switch(ch) { case 0x0020: case 0x0085: case 0x00A0: case 0x1680: case 0x2028: case 0x2029: case 0x202F: case 0x205F: case 0x3000: return 1; } RANGE(0x0009, 0x000D); RANGE(0x2000, 0x200A); return 0; } /* return 1 if ch has Dash property */ static int unicode_isDash(uint32_t ch) { switch(ch) { case 0x002D: case 0x058A: case 0x05BE: case 0x1400: case 0x1806: case 0x2053: case 0x207B: case 0x208B: case 0x2212: case 0x2E17: case 0x2E1A: case 0x2E40: case 0x301C: case 0x3030: case 0x30A0: case 0xFE58: case 0xFE63: case 0xFF0D: return 1; } RANGE(0x2010, 0x2015); RANGE(0x2E3A, 0x2E3B); RANGE(0xFE31, 0xFE32); return 0; } /* return 1 if ch has Hyphen property */ static int unicode_isHyphen(uint32_t ch) { switch(ch) { case 0x002D: case 0x00AD: case 0x058A: case 0x1806: case 0x2E17: case 0x30FB: case 0xFE63: case 0xFF0D: case 0xFF65: return 1; } RANGE(0x2010, 0x2011); return 0; } /* return 1 if ch has Quotation Mark property */ static int unicode_isQuotation_Mark(uint32_t ch) { switch(ch) { case 0x0022: case 0x0027: case 0x00AB: case 0x00BB: case 0x2018: case 0x2019: case 0x201A: case 0x201D: case 0x201E: case 0x201F: case 0x2039: case 0x203A: case 0x2E42: case 0x300C: case 0x300D: case 0x300E: case 0x300F: case 0x301D: case 0xFE41: case 0xFE42: case 0xFE43: case 0xFE44: case 0xFF02: case 0xFF07: case 0xFF62: case 0xFF63: return 1; } RANGE(0x201B, 0x201C); RANGE(0x301E, 0x301F); return 0; } /* return 1 if ch has Terminal Punctuation property */ static int unicode_isTerminal_Punctuation(uint32_t ch) { switch(ch) { case 0x0021: case 0x002C: case 0x002E: case 0x003F: case 0x037E: case 0x0387: case 0x0589: case 0x05C3: case 0x060C: case 0x061B: case 0x061F: case 0x06D4: case 0x070C: case 0x085E: case 0x0F08: case 0x17DA: case 0x2E2E: case 0x2E3C: case 0x2E41: case 0xA92F: case 0xAADF: case 0xABEB: case 0xFF01: case 0xFF0C: case 0xFF0E: case 0xFF1F: case 0xFF61: case 0xFF64: case 0x1039F: case 0x103D0: case 0x10857: case 0x1091F: case 0x111CD: case 0x112A9: case 0x1145B: case 0x11C71: case 0x16AF5: case 0x16B44: case 0x1BC9F: return 1; } RANGE(0x003A, 0x003B); RANGE(0x0700, 0x070A); RANGE(0x07F8, 0x07F9); RANGE(0x0830, 0x083E); RANGE(0x0964, 0x0965); RANGE(0x0E5A, 0x0E5B); RANGE(0x0F0D, 0x0F12); RANGE(0x104A, 0x104B); RANGE(0x1361, 0x1368); RANGE(0x166D, 0x166E); RANGE(0x16EB, 0x16ED); RANGE(0x1735, 0x1736); RANGE(0x17D4, 0x17D6); RANGE(0x1802, 0x1805); RANGE(0x1808, 0x1809); RANGE(0x1944, 0x1945); RANGE(0x1AA8, 0x1AAB); RANGE(0x1B5A, 0x1B5B); RANGE(0x1B5D, 0x1B5F); RANGE(0x1C3B, 0x1C3F); RANGE(0x1C7E, 0x1C7F); RANGE(0x203C, 0x203D); RANGE(0x2047, 0x2049); RANGE(0x3001, 0x3002); RANGE(0xA4FE, 0xA4FF); RANGE(0xA60D, 0xA60F); RANGE(0xA6F3, 0xA6F7); RANGE(0xA876, 0xA877); RANGE(0xA8CE, 0xA8CF); RANGE(0xA9C7, 0xA9C9); RANGE(0xAA5D, 0xAA5F); RANGE(0xAAF0, 0xAAF1); RANGE(0xFE50, 0xFE52); RANGE(0xFE54, 0xFE57); RANGE(0xFF1A, 0xFF1B); RANGE(0x10A56, 0x10A57); RANGE(0x10AF0, 0x10AF5); RANGE(0x10B3A, 0x10B3F); RANGE(0x10B99, 0x10B9C); RANGE(0x11047, 0x1104D); RANGE(0x110BE, 0x110C1); RANGE(0x11141, 0x11143); RANGE(0x111C5, 0x111C6); RANGE(0x111DE, 0x111DF); RANGE(0x11238, 0x1123C); RANGE(0x1144B, 0x1144D); RANGE(0x115C2, 0x115C5); RANGE(0x115C9, 0x115D7); RANGE(0x11641, 0x11642); RANGE(0x1173C, 0x1173E); RANGE(0x11A42, 0x11A43); RANGE(0x11A9B, 0x11A9C); RANGE(0x11AA1, 0x11AA2); RANGE(0x11C41, 0x11C43); RANGE(0x12470, 0x12474); RANGE(0x16A6E, 0x16A6F); RANGE(0x16B37, 0x16B39); RANGE(0x1DA87, 0x1DA8A); return 0; } /* return 1 if ch has Hex Digit property */ static int unicode_isHex_Digit(uint32_t ch) { RANGE(0x0030, 0x0039); RANGE(0x0041, 0x0046); RANGE(0x0061, 0x0066); RANGE(0xFF10, 0xFF19); RANGE(0xFF21, 0xFF26); RANGE(0xFF41, 0xFF46); return 0; } /* return 1 if ch has Other Alphabetic property */ static int unicode_isOther_Alphabetic(uint32_t ch) { switch(ch) { case 0x0345: case 0x05BF: case 0x05C7: case 0x0670: case 0x06ED: case 0x0711: case 0x0903: case 0x093A: case 0x093B: case 0x0981: case 0x09D7: case 0x0A03: case 0x0A51: case 0x0A75: case 0x0A83: case 0x0AC9: case 0x0B01: case 0x0B3E: case 0x0B3F: case 0x0B40: case 0x0B56: case 0x0B57: case 0x0B82: case 0x0BC0: case 0x0BD7: case 0x0C00: case 0x0C81: case 0x0CBE: case 0x0CBF: case 0x0CC6: case 0x0CCC: case 0x0D57: case 0x0DD6: case 0x0E31: case 0x0E4D: case 0x0EB1: case 0x0ECD: case 0x0F7F: case 0x1031: case 0x1038: case 0x1062: case 0x1082: case 0x109C: case 0x109D: case 0x135F: case 0x17B6: case 0x17C6: case 0x18A9: case 0x1932: case 0x1A1B: case 0x1A55: case 0x1A56: case 0x1A57: case 0x1A61: case 0x1A62: case 0x1B04: case 0x1B35: case 0x1B3B: case 0x1B3C: case 0x1B42: case 0x1B43: case 0x1B82: case 0x1BA1: case 0x1BE7: case 0x1BED: case 0x1BEE: case 0xA827: case 0xA8C5: case 0xA952: case 0xA983: case 0xA9BC: case 0xAA43: case 0xAA4C: case 0xAA4D: case 0xAAB0: case 0xAABE: case 0xAAEB: case 0xAAF5: case 0xABE5: case 0xABE8: case 0xFB1E: case 0x11000: case 0x11001: case 0x11002: case 0x11082: case 0x1112C: case 0x11182: case 0x111BF: case 0x11234: case 0x11237: case 0x1123E: case 0x112DF: case 0x11340: case 0x11357: case 0x11445: case 0x114B9: case 0x114BA: case 0x114C1: case 0x115BE: case 0x1163D: case 0x1163E: case 0x11640: case 0x116AB: case 0x116AC: case 0x116AD: case 0x11726: case 0x11A39: case 0x11A97: case 0x11C2F: case 0x11C3E: case 0x11CA9: case 0x11CB1: case 0x11CB4: case 0x11D3A: case 0x11D43: case 0x11D47: case 0x1BC9E: case 0x1E947: return 1; } RANGE(0x05B0, 0x05BD); RANGE(0x05C1, 0x05C2); RANGE(0x05C4, 0x05C5); RANGE(0x0610, 0x061A); RANGE(0x064B, 0x0657); RANGE(0x0659, 0x065F); RANGE(0x06D6, 0x06DC); RANGE(0x06E1, 0x06E4); RANGE(0x06E7, 0x06E8); RANGE(0x0730, 0x073F); RANGE(0x07A6, 0x07B0); RANGE(0x0816, 0x0817); RANGE(0x081B, 0x0823); RANGE(0x0825, 0x0827); RANGE(0x0829, 0x082C); RANGE(0x08D4, 0x08DF); RANGE(0x08E3, 0x08E9); RANGE(0x08F0, 0x0902); RANGE(0x093E, 0x0940); RANGE(0x0941, 0x0948); RANGE(0x0949, 0x094C); RANGE(0x094E, 0x094F); RANGE(0x0955, 0x0957); RANGE(0x0962, 0x0963); RANGE(0x0982, 0x0983); RANGE(0x09BE, 0x09C0); RANGE(0x09C1, 0x09C4); RANGE(0x09C7, 0x09C8); RANGE(0x09CB, 0x09CC); RANGE(0x09E2, 0x09E3); RANGE(0x0A01, 0x0A02); RANGE(0x0A3E, 0x0A40); RANGE(0x0A41, 0x0A42); RANGE(0x0A47, 0x0A48); RANGE(0x0A4B, 0x0A4C); RANGE(0x0A70, 0x0A71); RANGE(0x0A81, 0x0A82); RANGE(0x0ABE, 0x0AC0); RANGE(0x0AC1, 0x0AC5); RANGE(0x0AC7, 0x0AC8); RANGE(0x0ACB, 0x0ACC); RANGE(0x0AE2, 0x0AE3); RANGE(0x0AFA, 0x0AFC); RANGE(0x0B02, 0x0B03); RANGE(0x0B41, 0x0B44); RANGE(0x0B47, 0x0B48); RANGE(0x0B4B, 0x0B4C); RANGE(0x0B62, 0x0B63); RANGE(0x0BBE, 0x0BBF); RANGE(0x0BC1, 0x0BC2); RANGE(0x0BC6, 0x0BC8); RANGE(0x0BCA, 0x0BCC); RANGE(0x0C01, 0x0C03); RANGE(0x0C3E, 0x0C40); RANGE(0x0C41, 0x0C44); RANGE(0x0C46, 0x0C48); RANGE(0x0C4A, 0x0C4C); RANGE(0x0C55, 0x0C56); RANGE(0x0C62, 0x0C63); RANGE(0x0C82, 0x0C83); RANGE(0x0CC0, 0x0CC4); RANGE(0x0CC7, 0x0CC8); RANGE(0x0CCA, 0x0CCB); RANGE(0x0CD5, 0x0CD6); RANGE(0x0CE2, 0x0CE3); RANGE(0x0D00, 0x0D01); RANGE(0x0D02, 0x0D03); RANGE(0x0D3E, 0x0D40); RANGE(0x0D41, 0x0D44); RANGE(0x0D46, 0x0D48); RANGE(0x0D4A, 0x0D4C); RANGE(0x0D62, 0x0D63); RANGE(0x0D82, 0x0D83); RANGE(0x0DCF, 0x0DD1); RANGE(0x0DD2, 0x0DD4); RANGE(0x0DD8, 0x0DDF); RANGE(0x0DF2, 0x0DF3); RANGE(0x0E34, 0x0E3A); RANGE(0x0EB4, 0x0EB9); RANGE(0x0EBB, 0x0EBC); RANGE(0x0F71, 0x0F7E); RANGE(0x0F80, 0x0F81); RANGE(0x0F8D, 0x0F97); RANGE(0x0F99, 0x0FBC); RANGE(0x102B, 0x102C); RANGE(0x102D, 0x1030); RANGE(0x1032, 0x1036); RANGE(0x103B, 0x103C); RANGE(0x103D, 0x103E); RANGE(0x1056, 0x1057); RANGE(0x1058, 0x1059); RANGE(0x105E, 0x1060); RANGE(0x1067, 0x1068); RANGE(0x1071, 0x1074); RANGE(0x1083, 0x1084); RANGE(0x1085, 0x1086); RANGE(0x1712, 0x1713); RANGE(0x1732, 0x1733); RANGE(0x1752, 0x1753); RANGE(0x1772, 0x1773); RANGE(0x17B7, 0x17BD); RANGE(0x17BE, 0x17C5); RANGE(0x17C7, 0x17C8); RANGE(0x1885, 0x1886); RANGE(0x1920, 0x1922); RANGE(0x1923, 0x1926); RANGE(0x1927, 0x1928); RANGE(0x1929, 0x192B); RANGE(0x1930, 0x1931); RANGE(0x1933, 0x1938); RANGE(0x1A17, 0x1A18); RANGE(0x1A19, 0x1A1A); RANGE(0x1A58, 0x1A5E); RANGE(0x1A63, 0x1A64); RANGE(0x1A65, 0x1A6C); RANGE(0x1A6D, 0x1A72); RANGE(0x1A73, 0x1A74); RANGE(0x1B00, 0x1B03); RANGE(0x1B36, 0x1B3A); RANGE(0x1B3D, 0x1B41); RANGE(0x1B80, 0x1B81); RANGE(0x1BA2, 0x1BA5); RANGE(0x1BA6, 0x1BA7); RANGE(0x1BA8, 0x1BA9); RANGE(0x1BAC, 0x1BAD); RANGE(0x1BE8, 0x1BE9); RANGE(0x1BEA, 0x1BEC); RANGE(0x1BEF, 0x1BF1); RANGE(0x1C24, 0x1C2B); RANGE(0x1C2C, 0x1C33); RANGE(0x1C34, 0x1C35); RANGE(0x1CF2, 0x1CF3); RANGE(0x1DE7, 0x1DF4); RANGE(0x24B6, 0x24E9); RANGE(0x2DE0, 0x2DFF); RANGE(0xA674, 0xA67B); RANGE(0xA69E, 0xA69F); RANGE(0xA823, 0xA824); RANGE(0xA825, 0xA826); RANGE(0xA880, 0xA881); RANGE(0xA8B4, 0xA8C3); RANGE(0xA926, 0xA92A); RANGE(0xA947, 0xA951); RANGE(0xA980, 0xA982); RANGE(0xA9B4, 0xA9B5); RANGE(0xA9B6, 0xA9B9); RANGE(0xA9BA, 0xA9BB); RANGE(0xA9BD, 0xA9BF); RANGE(0xAA29, 0xAA2E); RANGE(0xAA2F, 0xAA30); RANGE(0xAA31, 0xAA32); RANGE(0xAA33, 0xAA34); RANGE(0xAA35, 0xAA36); RANGE(0xAAB2, 0xAAB4); RANGE(0xAAB7, 0xAAB8); RANGE(0xAAEC, 0xAAED); RANGE(0xAAEE, 0xAAEF); RANGE(0xABE3, 0xABE4); RANGE(0xABE6, 0xABE7); RANGE(0xABE9, 0xABEA); RANGE(0x10376, 0x1037A); RANGE(0x10A01, 0x10A03); RANGE(0x10A05, 0x10A06); RANGE(0x10A0C, 0x10A0F); RANGE(0x11038, 0x11045); RANGE(0x110B0, 0x110B2); RANGE(0x110B3, 0x110B6); RANGE(0x110B7, 0x110B8); RANGE(0x11100, 0x11102); RANGE(0x11127, 0x1112B); RANGE(0x1112D, 0x11132); RANGE(0x11180, 0x11181); RANGE(0x111B3, 0x111B5); RANGE(0x111B6, 0x111BE); RANGE(0x1122C, 0x1122E); RANGE(0x1122F, 0x11231); RANGE(0x11232, 0x11233); RANGE(0x112E0, 0x112E2); RANGE(0x112E3, 0x112E8); RANGE(0x11300, 0x11301); RANGE(0x11302, 0x11303); RANGE(0x1133E, 0x1133F); RANGE(0x11341, 0x11344); RANGE(0x11347, 0x11348); RANGE(0x1134B, 0x1134C); RANGE(0x11362, 0x11363); RANGE(0x11435, 0x11437); RANGE(0x11438, 0x1143F); RANGE(0x11440, 0x11441); RANGE(0x11443, 0x11444); RANGE(0x114B0, 0x114B2); RANGE(0x114B3, 0x114B8); RANGE(0x114BB, 0x114BE); RANGE(0x114BF, 0x114C0); RANGE(0x115AF, 0x115B1); RANGE(0x115B2, 0x115B5); RANGE(0x115B8, 0x115BB); RANGE(0x115BC, 0x115BD); RANGE(0x115DC, 0x115DD); RANGE(0x11630, 0x11632); RANGE(0x11633, 0x1163A); RANGE(0x1163B, 0x1163C); RANGE(0x116AE, 0x116AF); RANGE(0x116B0, 0x116B5); RANGE(0x1171D, 0x1171F); RANGE(0x11720, 0x11721); RANGE(0x11722, 0x11725); RANGE(0x11727, 0x1172A); RANGE(0x11A01, 0x11A06); RANGE(0x11A07, 0x11A08); RANGE(0x11A09, 0x11A0A); RANGE(0x11A35, 0x11A38); RANGE(0x11A3B, 0x11A3E); RANGE(0x11A51, 0x11A56); RANGE(0x11A57, 0x11A58); RANGE(0x11A59, 0x11A5B); RANGE(0x11A8A, 0x11A96); RANGE(0x11C30, 0x11C36); RANGE(0x11C38, 0x11C3D); RANGE(0x11C92, 0x11CA7); RANGE(0x11CAA, 0x11CB0); RANGE(0x11CB2, 0x11CB3); RANGE(0x11CB5, 0x11CB6); RANGE(0x11D31, 0x11D36); RANGE(0x11D3C, 0x11D3D); RANGE(0x11D3F, 0x11D41); RANGE(0x16B30, 0x16B36); RANGE(0x16F51, 0x16F7E); RANGE(0x1E000, 0x1E006); RANGE(0x1E008, 0x1E018); RANGE(0x1E01B, 0x1E021); RANGE(0x1E023, 0x1E024); RANGE(0x1E026, 0x1E02A); RANGE(0x1F130, 0x1F149); RANGE(0x1F150, 0x1F169); RANGE(0x1F170, 0x1F189); return 0; } /* return 1 if ch has Other Lowercase property */ static int unicode_isOther_Lowercase(uint32_t ch) { switch(ch) { case 0x00AA: case 0x00BA: case 0x0345: case 0x037A: case 0x1D78: case 0x2071: case 0x207F: case 0xA770: return 1; } RANGE(0x02B0, 0x02B8); RANGE(0x02C0, 0x02C1); RANGE(0x02E0, 0x02E4); RANGE(0x1D2C, 0x1D6A); RANGE(0x1D9B, 0x1DBF); RANGE(0x2090, 0x209C); RANGE(0x2170, 0x217F); RANGE(0x24D0, 0x24E9); RANGE(0x2C7C, 0x2C7D); RANGE(0xA69C, 0xA69D); RANGE(0xA7F8, 0xA7F9); RANGE(0xAB5C, 0xAB5F); return 0; } /* return 1 if ch has Other Uppercase property */ static int unicode_isOther_Uppercase(uint32_t ch) { RANGE(0x2160, 0x216F); RANGE(0x24B6, 0x24CF); RANGE(0x1F130, 0x1F149); RANGE(0x1F150, 0x1F169); RANGE(0x1F170, 0x1F189); return 0; } /* return 1 if ch has Pattern White Space property */ static int unicode_isPattern_White_Space(uint32_t ch) { switch(ch) { case 0x0020: case 0x0085: case 0x2028: case 0x2029: return 1; } RANGE(0x0009, 0x000D); RANGE(0x200E, 0x200F); return 0; } static int unicode_isalnum(uint32_t ch) { return unicode_isalpha(ch) || unicode_isdigit(ch); } static int unicode_isalpha(uint32_t ch) { RANGE(0x0041, 0x005a); RANGE(0x0061, 0x007a); return unicode_isOther_Alphabetic(ch); } static int unicode_isblank(uint32_t ch) { switch(ch) { case 0x0009: return 1; } return unicode_isWhite_Space(ch) || unicode_isPattern_White_Space(ch); } static int unicode_iscntrl(uint32_t ch) { switch(ch) { case 0x0000: case 0x007f: return 1; } RANGE(0x0001, 0x001f); return 0; } static int unicode_isdigit(uint32_t ch) { RANGE(0x0030, 0x0039); RANGE(0xFF10, 0xFF19); return 0; } static int unicode_isgraph(uint32_t ch) { RANGE(0x0021, 0x007e); return 0; } static int unicode_islower(uint32_t ch) { RANGE(0x0061, 0x007a); return unicode_isOther_Lowercase(ch); } static int unicode_isprint(uint32_t ch) { RANGE(0x0020, 0x007e); /* XXX */ return 0; } static int unicode_ispunct(uint32_t ch) { return unicode_isTerminal_Punctuation(ch) || unicode_isQuotation_Mark(ch) || unicode_isHyphen(ch) || unicode_isDash(ch); } static int unicode_isspace(uint32_t ch) { return unicode_isWhite_Space(ch); } static int unicode_isupper(uint32_t ch) { RANGE(0x0041, 0x005a); return unicode_isOther_Uppercase(ch); } static int unicode_isxdigit(uint32_t ch) { return unicode_isHex_Digit(ch); } static int unicode_isword(uint32_t ch) { return unicode_isalnum(ch) || ch == '_'; } static int unicode_ispunct2(uint32_t ch) { if (!unicode_isprint(ch) || unicode_isspace(ch) || unicode_isword(ch)) { return 0; } return 1; } static uint32_t unicode_tolower(uint32_t ch) { if (unicode_isupper(ch)) { ch += 0x20; } return ch; } static uint32_t unicode_toupper(uint32_t ch) { if (unicode_islower(ch)) { ch -= 0x20; } return ch; } /* allocate space - used in regasub */ static int growspace(char **buf, size_t *size, size_t cc, size_t incr) { size_t newsize; char *newv; if (*size < cc + incr) { newsize = howmany(cc + incr, 64) * 64; newv = realloc(*buf, newsize); if (newv == NULL) { return 0; } memset(&newv[*size], 0x0, newsize - *size); *buf = newv; *size = newsize; } return 1; } /* check it was compiled properly */ static inline int good_struct(const agcre_regex_t *agcre) { re_t *re; if (agcre == NULL || agcre->re_magic != AGCRE_MAGIC2) { return 0; } if ((re = agcre->re_g) == NULL) { return 0; } return re->magic1 = MAGIC1 && re->magic2 == MAGIC2 && re->magic3 == MAGIC3 && re->magic4 == MAGIC4; } /***********************************************************/ /* allocate a new structure and return it */ agcre_regex_t * agcre_new(void) { return calloc(1, sizeof(agcre_regex_t)); } /* compile regular expression */ int agcre_regcomp(agcre_regex_t *agcre, const void *vs, uint32_t flags) { retoken_t *tok; uint32_t n; input_t in; re_t *re; int errc; if (agcre == NULL || vs == NULL) { return AGCRE_REG_FAILURE; } memset(&in, 0x0, sizeof(in)); in.s = (const char *)vs; in.eo = (flags & AGCRE_REG_PEND) ? (agcre_regoff_t)(agcre->re_endp - in.s) : (agcre_regoff_t)strlen(in.s); memset(agcre, 0x0, sizeof(*agcre)); if ((agcre->re_g = re = in.re = calloc(1, sizeof(*re))) == NULL) { return AGCRE_REG_FAILURE; } re->magic1 = MAGIC1; re->magic2 = MAGIC2; re->magic3 = MAGIC3; re->magic4 = MAGIC4; if (in.eo - in.so > AGCRE_MAX_EXPR_LENGTH) { re->msgc = snprintf(re->msg, sizeof(re->msg), "expression length %llu larger than %u", (unsigned long long)(in.eo - in.so), AGCRE_MAX_EXPR_LENGTH); return AGCRE_REG_FAILURE; } if (flags & AGCRE_REG_EXTENDED) { tok = parse_extended(agcre, &in); } else if (flags & AGCRE_REG_BASIC) { tok = parse_basic(agcre, &in, flags); } else if (flags & AGCRE_REG_NOSPEC) { tok = parse_nospec(agcre, &in); } else { re->msgc = snprintf(re->msg, sizeof(re->msg), "unknown type of regexp"); return AGCRE_REG_FAILURE; } if (tok == NULL) { return AGCRE_REG_FAILURE; } if (flags & AGCRE_REG_DUMP) { print_token(tok); printf("\n"); } errc = 0; n = count(tok, &errc) + 1; if (errc) { re->msgc = snprintf(re->msg, sizeof(re->msg), "illegal token parse"); return AGCRE_REG_FAILURE; } if ((re->pc = re->prog = calloc(1, n * sizeof(re->prog[0]))) == NULL) { re->msgc = snprintf(re->msg, sizeof(re->msg), "%d instruction allocation failure", n); return AGCRE_REG_FAILURE; } re->flags = flags; emit(re, tok); freetok(tok); re->pc->op = OP_MATCH; re->pc += 1; re->instrc = re->pc - re->prog; agcre->re_magic = AGCRE_MAGIC2; if (flags & AGCRE_REG_DUMP) { printprog(re); } return AGCRE_REG_SUCCESS; } #ifndef USE_ARG #define USE_ARG(x) /*LINTED*/(void)&x #endif /* format the error nicely */ size_t agcre_regerror(int errcode, const agcre_regex_t *agcre, char *errbuf, size_t size) { re_t *re; USE_ARG(errcode); if (!good_struct(agcre) || size == 0 || errbuf == NULL) { return 0; } re = agcre->re_g; return snprintf(errbuf, size, "%s", re->msg); } /* execute the regular expression */ int agcre_regexec(agcre_regex_t *agcre, const void *vs, size_t matchc, agcre_regmatch_t *m, uint32_t flags) { threadlist_t *current; threadlist_t *next; threadlist_t *tmp; context_t *matched; context_t *ctx; uint32_t prevflags; uint32_t instrc; input_t in; instr_t *instr; instr_t *prog; size_t i; re_t *re; int ret; if (!good_struct(agcre) || vs == NULL || (matchc > 0 && m == NULL)) { return AGCRE_REG_FAILURE; } if ((re = agcre->re_g) == NULL) { return AGCRE_REG_FAILURE; } if (agcre->re_magic != AGCRE_MAGIC2) { re->msgc = snprintf(re->msg, sizeof(re->msg), "bad magic number 0x%x, not 0x%x", agcre->re_magic, AGCRE_MAGIC2); return AGCRE_REG_FAILURE; } if (matchc > AGCRE_MAX_SUBEXPR) { re->msgc = snprintf(re->msg, sizeof(re->msg), "matchc %zu larger than limit %u", matchc, AGCRE_MAX_SUBEXPR); return AGCRE_REG_FAILURE; } memset(&in, 0x0, sizeof(in)); in.s = (const char *)vs; in.so = (flags & AGCRE_REG_STARTEND) ? m[0].rm_so : 0; in.eo = (flags & AGCRE_REG_STARTEND) ? m[0].rm_eo : get_length_in_bytes(vs, flags); matched = NULL; ctx = make_new_context(re, matchc); for (i = 0; i < matchc ; i++) { m[i].rm_so = m[i].rm_eo = -1; ctx->sub[i].rm_so = ctx->sub[i].rm_eo = -1; } instrc = re->instrc; prog = re->prog; if ((flags | re->flags) & AGCRE_REG_ANCHOR) { instrc -= LEADING_DOT_STAR_INSTRS; prog += LEADING_DOT_STAR_INSTRS; } current = threadlist(instrc); next = threadlist(instrc); re->gen += 1; prevflags = re->flags; re->flags |= flags; in.c = in.so; addthread(re, current, newthread(prog, ctx), &in, 0, 1); ret = AGCRE_REG_FAILURE; for (in.ch = BOL ; ; in.c += in.bytes) { if (current->nthreads == 0) { break; } if (!get_next_char(&in, flags)) { break; } if (re->flags & AGCRE_REG_TRACE) { printf("\n%lld 0x%0x", (long long)in.c, in.ch); } for (re->gen++, i = 0; i < current->nthreads ; i++) { instr = current->t[i].pc; ctx = current->t[i].ctx; if (re->flags & AGCRE_REG_TRACE) { printf("\nthread %zu, pc %d, ctx %p", i, (int)(instr - prog), ctx); } switch(instr->op) { case OP_CHAR: if (!charmatch(re, instr, in.ch, instr->n)) { decref(re, ctx); break; } goto eol_check; case OP_SET: if (!setmatch(re, &re->sets[instr->n], &in, instr)) { decref(re, ctx); break; } goto eol_check; case OP_ANY: eol_check: if (!anymatch(re, &in)) { decref(re, ctx); break; } addthread(re, next, newthread(instr + 1, ctx), &in, in.bytes, 1); break; case OP_BACKREF: if (!charmatch(re, instr, in.ch, in.s[ctx->sub[instr->n].rm_so + ctx->c])) { decref(re, ctx); break; } if (ctx->c == ctx->sub[instr->n].rm_eo - ctx->sub[instr->n].rm_so - in.bytes) { addthread(re, next, newthread(instr + 1, ctx), &in, 0, 1); } else { ctx->c += in.bytes; addthread(re, next, newthread(instr, ctx), &in, ctx->c, 1); } continue; case OP_ZEROWIDTH: if (!zeromatch(re, instr->n, &in)) { decref(re, ctx); break; } addthread(re, current, newthread(instr + 1, ctx), &in, 0, 0); continue; case OP_MATCH: if (is_better_match(ctx, matched)) { if (!matched) { matched = make_new_context(re, matchc); } memcpy(matched, ctx, context_bytes(matchc)); } for (i++; i < current->nthreads ; i++) { decref(re, current->t[i].ctx); } if (ctx->sub[0].rm_eo - ctx->sub[0].rm_so == 0) { addthread(re, next, newthread(prog, ctx), &in, in.bytes, 1); } goto break_for; /* OP_JUMP, OP_SPLIT, OP_SAVE handled in addthread, so that */ /* machine execution matches what a backtracker would do. */ /* This is discussed (but not shown as code) in */ /* Regular Expression Matching: the Virtual Machine Approach. */ } } break_for: tmp = current; current = next; next = tmp; next->nthreads = 0; if (in.c > in.eo) { break; } #if 0 if ((flags & AGCRE_REG_ANCHOR) && ((matched == NULL && current->nthreads < 2 && in.c > in.so) || (matched && matched->sub[0].rm_so > (int64_t)in.so))) { break; } #endif } if (matched) { if (!(flags & AGCRE_REG_NOSUB)) { for (i = 0; i < matchc; i++) { m[i] = matched->sub[i]; } } decref(re, matched); ret = AGCRE_REG_SUCCESS; } free(current); free(next); decref(re, ctx); re->flags = prevflags; return ret; } /* execute the regular expression backwards */ int agcre_rev_regexec(agcre_regex_t *agcre, const void *vs, size_t matchc, agcre_regmatch_t *m, uint32_t flags) { uint32_t revflags; uint32_t bolflags; int64_t from; int64_t to; int64_t i; int found; int lastmatch; if (!good_struct(agcre) || vs == NULL || (matchc > 0 && m == NULL)) { return AGCRE_REG_FAILURE; } if (flags & AGCRE_REG_STARTEND) { from = m[0].rm_so; to = m[0].rm_eo; } else { from = 0; to = strlen(vs); } /* initialise here or final regexec doesn't work for "^$" */ lastmatch = 0; m[0].rm_so = from; m[0].rm_eo = to; /* quick check to see if we have anything */ if (agcre_regexec(agcre, vs, matchc, m, flags | AGCRE_REG_STARTEND) != 0) { lastmatch = m[0].rm_so; return AGCRE_REG_FAILURE; } revflags = (AGCRE_REG_STARTEND | AGCRE_REG_ANCHOR); for (found = 0, i = to - 1 ; i >= from ; --i) { m[0].rm_so = i; m[0].rm_eo = to; bolflags = (i > 0) ? AGCRE_REG_NOTBOL : 0; if (agcre_regexec(agcre, vs, matchc, m, flags | revflags | bolflags) == 0) { found += 1; lastmatch = i; } else if (found > 0) { break; } } /* just do 1 final forward search to load m array */ m[0].rm_so = lastmatch; m[0].rm_eo = to; bolflags = (lastmatch > 0) ? AGCRE_REG_NOTBOL : 0; return agcre_regexec(agcre, vs, matchc, m, flags | revflags | bolflags); } /* free the regular expression */ void agcre_regfree(agcre_regex_t *agcre) { uint32_t i; re_t *re; if (agcre && good_struct(agcre)) { if ((re = agcre->re_g) != NULL) { free(re->prog); for (i = 0 ; i < re->setc ; i++) { set_free(&re->sets[i]); } free(re->sets); free_contexts(re->ctxlist); free(re); } } } /* do regexp sed-style substitution */ ssize_t agcre_regnsub(char *buf, size_t size, const char *repl, const agcre_regmatch_t *rm, const char *str) { const char *i; uint32_t len; uint32_t num; char *o; int outofroom = 0; if (buf == NULL || repl == NULL || rm == NULL || str == NULL || size == 0) { return -1; } memset(buf, 0x0, size); for (i = repl, o = buf ; *i ; ) { if ((size_t)(o - buf) >= size - 1) { /* not enough space, transition to observe */ outofroom = 1; } if (*i == '&' || (*i == '\\' && (i[1] >= '0' && i[1] <= '9'))) { num = (i[0] == '&') ? 0 : (i[1] - '0'); if (rm[num].rm_so < 0 || rm[num].rm_eo < 0 || rm[num].rm_eo - rm[num].rm_so < 0 || rm[num].rm_eo < rm[num].rm_so || rm[num].rm_eo > rm[0].rm_eo) { /* sanity check on regmatch values */ return -1; } len = rm[num].rm_eo - rm[num].rm_so; if (len >= (size - (size_t)(o - buf))) { /* not enough space, transition to observe */ outofroom = 1; } if (!outofroom) { memcpy(o, &str[rm[num].rm_so], len); } i += 2; o += len; } else { if (!outofroom) { *o = *i; } i += 1; o += 1; } } if (!outofroom) { *o = 0x0; } return (ssize_t)(o - buf); } /* do regexp sed-style substitution */ ssize_t agcre_regasub(char **buf, const char *repl, const agcre_regmatch_t *rm, const char *str) { const char *i; uint32_t len; uint32_t num; size_t size; size_t cc; if (buf == NULL || repl == NULL || rm == NULL || str == NULL) { return -1; } *buf = NULL; for (i = repl, size = cc = 0 ; *i ; ) { if (*i == '&' || (*i == '\\' && (i[1] >= '0' && i[1] <= '9'))) { num = (i[0] == '&') ? 0 : (i[1] - '0'); if (rm[num].rm_so < 0 || rm[num].rm_eo < 0 || rm[num].rm_eo - rm[num].rm_so < 0 || rm[num].rm_eo < rm[num].rm_so || rm[num].rm_eo > rm[0].rm_eo) { /* sanity check on regmatch values */ return -1; } len = rm[num].rm_eo - rm[num].rm_so; if (!growspace(buf, &size, cc, len)) { return -1; } memcpy(&(*buf)[cc], &str[rm[num].rm_so], len); i += 2; cc += len; } else { if (!growspace(buf, &size, cc, 1)) { return -1; } (*buf)[cc++] = *i++; } } (*buf)[cc] = 0x0; return cc; } @ 1.5 log @agcre: fix up beginning of word and end of word tests - use parentheses to make it obvious to the compiler when to short-circuit. Add tests for beginning word and end of word (with and without \< and \> guards) Bump version to 20250722 @ text @@ 1.4 log @agcre version 20230621 ====================== + agcre - added internal magic numbers to agcre to attempt to catch if misbehaving programs overwrite sections of memory + agcre - check internal magic numbers before attempting to execute regex programs + agcre - bump agcre magic number in the external structure + agcre - bump version number in header file. Fix up tests to ensure correct operation @ text @d1182 2 a1183 2 return (isbegline(re, in) || !unicode_isword(in->prevch)) && unicode_isword(in->ch); d1190 2 a1191 2 return (isendline(re, in) || (in->c > in->so && unicode_isword(in->prevch))) && (!unicode_isword(in->ch)); @ 1.3 log @Update agcre (yet another regexp library) to version 20230224 + revamp the reverse searching functionality + bug fixes + don't terminate searches too early + update namespace protection to just use simple definitions + bump version to 20230224 @ text @d162 5 d169 1 d175 1 d179 1 d181 1 d2681 16 d2725 7 a2731 1 agcre->re_g = re = in.re = calloc(1, sizeof(*re)); d2773 1 a2773 1 agcre->re_magic = AGCRE_MAGIC; d2791 1 a2791 1 if (agcre == NULL || size == 0 || errbuf == NULL) { d2816 1 a2816 1 if (agcre == NULL || vs == NULL || (matchc > 0 && m == NULL)) { d2822 1 a2822 1 if (agcre->re_magic != AGCRE_MAGIC) { d2824 1 a2824 1 "bad magic number 0x%x, not 0x%x", agcre->re_magic, AGCRE_MAGIC); d2976 3 d3021 1 a3021 1 if (agcre) { @ 1.2 log @Add visibility definitions for agcre. For any sources embedding these routines, simply define HIDE_AGCRE, before including the agcre.h header file, and the routines will have the hidden visibility attribute set on them. For more information on that, see https://gcc.gnu.org/wiki/Visibility To stop agcre routines being exported in a .so, simply define HIDE_AGCRE - I've been doing this successfully in library Makefiles, for example, this is from elex/lib/Makefile (elex is a library that calls the agcre functions): # set symbol visibility for .so CPPFLAGS+= -DHIDE_AGCRE and the agcre symbols will be found just fine when linking and running, but will not be exported by the linker. This can save headaches, and weird crashes, especially when combined with ASLR (when two libraries define the same symbol, but with different structs or arguments). BEFORE: [2021/12/03 Fri 17:47:19] agc@@netbsd-002 ~/local/elex-20211115 [13781] > nm -D lib/libelex.so w _Jv_RegisterClasses w __cxa_finalize w __deregister_frame_info U __fstat50 w __register_frame_info U __sF 000000000020f198 D _end 000000000000c240 T _fini 0000000000000ea0 T _init 000000000000aa13 T agcre_new 000000000000bc48 T agcre_regasub 000000000000aa28 T agcre_regcomp 000000000000adde T agcre_regerror 000000000000ae48 T agcre_regexec 000000000000b8fd T agcre_regfree 000000000000b9a2 T agcre_regnsub 000000000000b7e8 T agcre_rev_regexec U asprintf U calloc 00000000000027f6 T elex_dispose 0000000000002b6a T elex_exec 0000000000002f5b T elex_exec_str 0000000000002982 T elex_make_new_rule 00000000000027bb T elex_new U fclose U fopen U fprintf U free U fwrite U memchr U memcmp U memcpy U memmove U memset U mmap U munmap U printf U putchar U realloc U snprintf U strchr U strcmp U strdup 000000000000c10c T striter_dispose 000000000000c165 T striter_exec 000000000000c1da T striter_exec_mem 000000000000c0f7 T striter_new U strlen U strtol U strtoul U vsnprintf U warn U warnx [2021/12/03 Fri 17:47:22] agc@@netbsd-002 ~/local/elex-20211115 [13782] > AFTER adding HIDE_AGCRE (and HIDE_STRITER) to elex/lib/Makefile: [2021/12/03 Fri 17:47:45] agc@@netbsd-002 ~/local/elex-20211115 [13774] > nm -D lib/libelex.so w _Jv_RegisterClasses w __cxa_finalize w __deregister_frame_info U __fstat50 w __register_frame_info U __sF 000000000020e160 D _end 000000000000bf30 T _fini 0000000000000c00 T _init U asprintf U calloc 00000000000024e6 T elex_dispose 000000000000285a T elex_exec 0000000000002c4b T elex_exec_str 0000000000002672 T elex_make_new_rule 00000000000024ab T elex_new U fclose U fopen U fprintf U free U fwrite U memchr U memcmp U memcpy U memmove U memset U mmap U munmap U printf U putchar U realloc U snprintf U strchr U strcmp U strdup U strlen U strtol U strtoul U vsnprintf U warn U warnx @ text @d226 1 d237 1 a237 1 static int unicode_isident(uint32_t /*ch*/); d421 1 a421 1 unicode_isident, d1173 2 a1174 2 return (isbegline(re, in) || !unicode_isident(in->prevch)) && unicode_isident(in->ch); d1181 2 a1182 2 return (isendline(re, in) || (in->c > in->so && unicode_isident(in->prevch))) && (!unicode_isident(in->ch)); a1580 4 case /* ":ident:]" */ 0x8a1572f1: set_add_callback(set, unicode_isident, 0); in->c += 8; return 1; d1593 4 d1609 4 d1669 1 a1669 1 unicode_isident, d2620 1 a2620 1 unicode_isident(uint32_t ch) d2625 9 d2675 1 a2675 1 AGCRE_EXPORT agcre_regex_t * d2682 1 a2682 1 AGCRE_EXPORT int d2754 1 a2754 1 AGCRE_EXPORT size_t d2768 1 a2768 1 AGCRE_EXPORT int d2934 1 a2934 1 AGCRE_EXPORT int d2937 7 a2943 5 int64_t from; int64_t to; int64_t i; int found; int this; d2952 10 a2961 1 flags |= (AGCRE_REG_STARTEND | AGCRE_REG_ANCHOR); d2965 2 a2966 1 if ((this = agcre_regexec(agcre, vs, matchc, m, flags)) == 0) { d2968 1 d2970 1 a2970 3 m[0].rm_so = i + 1; m[0].rm_eo = to; return agcre_regexec(agcre, vs, matchc, m, flags); d2973 5 a2977 1 return AGCRE_REG_FAILURE; d2981 1 a2981 1 AGCRE_EXPORT void d3001 1 a3001 1 AGCRE_EXPORT ssize_t d3054 1 a3054 1 AGCRE_EXPORT ssize_t @ 1.1 log @Update agcre to version 20211001 20211001 ======== + move to a single source file, which can just be included as a single file (the library method can still be used for this as well - sometimes, it's just easier to drop in a single file to other projects) + add AGCRE_EMBED_CTAGS as a primary regular expresion type (same as basic regexps, but where a '*' occurs as a non-column 0 element of the pattern, it is assumed to be a standard character, as produced by ctags(1) output; basic regular expressions only accept '*' as a standard character as the first element of the expression). Yay. + make the version string in the program a real string, so it can be found using strings(1) + add an agcre_rev_regexec(3) function, which searches the text in an efficient, reverse manner, a la strrchr(3) or memrchr(3) fashion. + add agcre_regnsub(3) and agcre_regasub(3) functions + bump the shared lib version to 1.0 + cut version 20211001 @ text @d2661 1 a2661 1 agcre_regex_t * d2668 1 a2668 1 int d2740 1 a2740 1 size_t d2754 1 a2754 1 int d2920 1 a2920 1 int d2952 1 a2952 1 void d2972 1 a2972 1 ssize_t d3025 1 a3025 1 ssize_t @