#include <stdlib.h>#include <stdio.h>#include <string.h>#include <setjmp.h>#include <limits.h> #include "regexp.h"#include "utf.h" #define emit regemit#define next regnext#define accept regaccept #ifndef nelem#define nelem(a) (int)(sizeof (a) / sizeof (a)[0])#endif #define REPINF 255#ifndef REG_MAXPROG#define REG_MAXPROG (32 << 10)#endif#ifndef REG_MAXREC#define REG_MAXREC 1024#endif#ifndef REG_MAXSPAN#define REG_MAXSPAN 64#endif#ifndef REG_MAXCLASS#define REG_MAXCLASS 16#endif typedef struct Reclass Reclass;typedef struct Renode Renode;typedef struct Reinst Reinst;typedef struct Rethread Rethread; struct Reclass { Rune *end; Rune spans[REG_MAXSPAN];}; struct Reprog { Reinst *start, *end; int flags; int nsub; Reclass cclass[REG_MAXCLASS];}; struct cstate { Reprog *prog; Renode *pstart, *pend; const char *source; int ncclass; int nsub; Renode *sub[REG_MAXSUB]; int lookahead; Rune yychar; Reclass *yycc; int yymin, yymax; const char *error; jmp_buf kaboom;}; static void die(struct cstate *g, const char *message){ g->error = message; longjmp(g->kaboom, 1);} static int canon(Rune c){ Rune u = toupperrune(c); if (c >= 128 && u < 128) return c; return u;} /* Scan */ enum { L_CHAR = 256, L_CCLASS, /* character class */ L_NCCLASS, /* negative character class */ L_NC, /* "(?:" no capture */ L_PLA, /* "(?=" positive lookahead */ L_NLA, /* "(?!" negative lookahead */ L_WORD, /* "\b" word boundary */ L_NWORD, /* "\B" non-word boundary */ L_REF, /* "\1" back-reference */ L_COUNT, /* {M,N} */}; static int hex(struct cstate *g, int c){ if (c >= '0' && c <= '9') return c - '0'; if (c >= 'a' && c <= 'f') return c - 'a' + 0xA; if (c >= 'A' && c <= 'F') return c - 'A' + 0xA; die(g, "invalid escape sequence"); return 0;} static int dec(struct cstate *g, int c){ if (c >= '0' && c <= '9') return c - '0'; die(g, "invalid quantifier"); return 0;} #define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|-0123456789" static int isunicodeletter(int c){ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || isalpharune(c);} static int nextrune(struct cstate *g){ if (!*g->source) { g->yychar = EOF; return 0; } g->source += chartorune(&g->yychar, g->source); if (g->yychar == '\\') { if (!*g->source) die(g, "unterminated escape sequence"); g->source += chartorune(&g->yychar, g->source); switch (g->yychar) { case 'f': g->yychar = '\f'; return 0; case 'n': g->yychar = '\n'; return 0; case 'r': g->yychar = '\r'; return 0; case 't': g->yychar = '\t'; return 0; case 'v': g->yychar = '\v'; return 0; case 'c': if (!g->source[0]) die(g, "unterminated escape sequence"); g->yychar = (*g->source++) & 31; return 0; case 'x': if (!g->source[0] || !g->source[1]) die(g, "unterminated escape sequence"); g->yychar = hex(g, *g->source++) << 4; g->yychar += hex(g, *g->source++); if (g->yychar == 0) { g->yychar = '0'; return 1; } return 0; case 'u': if (!g->source[0] || !g->source[1] || !g->source[2] || !g->source[3]) die(g, "unterminated escape sequence"); g->yychar = hex(g, *g->source++) << 12; g->yychar += hex(g, *g->source++) << 8; g->yychar += hex(g, *g->source++) << 4; g->yychar += hex(g, *g->source++); if (g->yychar == 0) { g->yychar = '0'; return 1; } return 0; case 0: g->yychar = '0'; return 1; } if (strchr(ESCAPES, g->yychar)) return 1; if (isunicodeletter(g->yychar) || g->yychar == '_') /* check identity escape */ die(g, "invalid escape character"); return 0; } return 0;} static int lexcount(struct cstate *g){ g->yychar = *g->source++; g->yymin = dec(g, g->yychar); g->yychar = *g->source++; while (g->yychar != ',' && g->yychar != '}') { g->yymin = g->yymin * 10 + dec(g, g->yychar); g->yychar = *g->source++; if (g->yymin >= REPINF) die(g, "numeric overflow"); } if (g->yychar == ',') { g->yychar = *g->source++; if (g->yychar == '}') { g->yymax = REPINF; } else { g->yymax = dec(g, g->yychar); g->yychar = *g->source++; while (g->yychar != '}') { g->yymax = g->yymax * 10 + dec(g, g->yychar); g->yychar = *g->source++; if (g->yymax >= REPINF) die(g, "numeric overflow"); } } } else { g->yymax = g->yymin; } return L_COUNT;} static void newcclass(struct cstate *g){ if (g->ncclass >= nelem(g->prog->cclass)) die(g, "too many character classes"); g->yycc = g->prog->cclass + g->ncclass++; g->yycc->end = g->yycc->spans;} static void addrange(struct cstate *g, Rune a, Rune b){ if (a > b) die(g, "invalid character class range"); if (g->yycc->end + 2 >= g->yycc->spans + nelem(g->yycc->spans)) die(g, "too many character class ranges"); *g->yycc->end++ = a; *g->yycc->end++ = b;} static void addranges_d(struct cstate *g){ addrange(g, '0', '9');} static void addranges_D(struct cstate *g){ addrange(g, 0, '0'-1); addrange(g, '9'+1, 0xFFFF);} static void addranges_s(struct cstate *g){ addrange(g, 0x9, 0xD); addrange(g, 0x20, 0x20); addrange(g, 0xA0, 0xA0); addrange(g, 0x2028, 0x2029); addrange(g, 0xFEFF, 0xFEFF);} static void addranges_S(struct cstate *g){ addrange(g, 0, 0x9-1); addrange(g, 0xD+1, 0x20-1); addrange(g, 0x20+1, 0xA0-1); addrange(g, 0xA0+1, 0x2028-1); addrange(g, 0x2029+1, 0xFEFF-1); addrange(g, 0xFEFF+1, 0xFFFF);} static void addranges_w(struct cstate *g){ addrange(g, '0', '9'); addrange(g, 'A', 'Z'); addrange(g, '_', '_'); addrange(g, 'a', 'z');} static void addranges_W(struct cstate *g){ addrange(g, 0, '0'-1); addrange(g, '9'+1, 'A'-1); addrange(g, 'Z'+1, '_'-1); addrange(g, '_'+1, 'a'-1); addrange(g, 'z'+1, 0xFFFF);} static int lexclass(struct cstate *g){ int type = L_CCLASS; int quoted, havesave, havedash; Rune save = 0; newcclass(g); quoted = nextrune(g); if (!quoted && g->yychar == '^') { type = L_NCCLASS; quoted = nextrune(g); } havesave = havedash = 0; for (;;) { if (g->yychar == EOF) die(g, "unterminated character class"); if (!quoted && g->yychar == ']') break; if (!quoted && g->yychar == '-') { if (havesave) { if (havedash) { addrange(g, save, '-'); havesave = havedash = 0; } else { havedash = 1; } } else { save = '-'; havesave = 1; } } else if (quoted && strchr("DSWdsw", g->yychar)) { if (havesave) { addrange(g, save, save); if (havedash) addrange(g, '-', '-'); } switch (g->yychar) { case 'd': addranges_d(g); break; case 's': addranges_s(g); break; case 'w': addranges_w(g); break; case 'D': addranges_D(g); break; case 'S': addranges_S(g); break; case 'W': addranges_W(g); break; } havesave = havedash = 0; } else { if (quoted) { if (g->yychar == 'b') g->yychar = '\b'; else if (g->yychar == '0') g->yychar = 0; /* else identity escape */ } if (havesave) { if (havedash) { addrange(g, save, g->yychar); havesave = havedash = 0; } else { addrange(g, save, save); save = g->yychar; } } else { save = g->yychar; havesave = 1; } } quoted = nextrune(g); } if (havesave) { addrange(g, save, save); if (havedash) addrange(g, '-', '-'); } return type;} static int lex(struct cstate *g){ int quoted = nextrune(g); if (quoted) { switch (g->yychar) { case 'b': return L_WORD; case 'B': return L_NWORD; case 'd': newcclass(g); addranges_d(g); return L_CCLASS; case 's': newcclass(g); addranges_s(g); return L_CCLASS; case 'w': newcclass(g); addranges_w(g); return L_CCLASS; case 'D': newcclass(g); addranges_d(g); return L_NCCLASS; case 'S': newcclass(g); addranges_s(g); return L_NCCLASS; case 'W': newcclass(g); addranges_w(g); return L_NCCLASS; case '0': g->yychar = 0; return L_CHAR; } if (g->yychar >= '0' && g->yychar <= '9') { g->yychar -= '0'; if (*g->source >= '0' && *g->source <= '9') g->yychar = g->yychar * 10 + *g->source++ - '0'; return L_REF; } return L_CHAR; } switch (g->yychar) { case EOF: case '$': case ')': case '*': case '+': case '.': case '?': case '^': case '|': return g->yychar; } if (g->yychar == '{') return lexcount(g); if (g->yychar == '[') return lexclass(g); if (g->yychar == '(') { if (g->source[0] == '?') { if (g->source[1] == ':') { g->source += 2; return L_NC; } if (g->source[1] == '=') { g->source += 2; return L_PLA; } if (g->source[1] == '!') { g->source += 2; return L_NLA; } } return '('; } return L_CHAR;} /* Parse */ enum { P_CAT, P_ALT, P_REP, P_BOL, P_EOL, P_WORD, P_NWORD, P_PAR, P_PLA, P_NLA, P_ANY, P_CHAR, P_CCLASS, P_NCCLASS, P_REF,}; struct Renode { unsigned char type; unsigned char ng, m, n; Rune c; Reclass *cc; Renode *x; Renode *y;}; static Renode *newnode(struct cstate *g, int type){ Renode *node = g->pend++; node->type = type; node->cc = NULL; node->c = 0; node->ng = 0; node->m = 0; node->n = 0; node->x = node->y = NULL; return node;} static int empty(Renode *node){ if (!node) return 1; switch (node->type) { default: return 1; case P_CAT: return empty(node->x) && empty(node->y); case P_ALT: return empty(node->x) || empty(node->y); case P_REP: return empty(node->x) || node->m == 0; case P_PAR: return empty(node->x); case P_REF: return empty(node->x); case P_ANY: case P_CHAR: case P_CCLASS: case P_NCCLASS: return 0; }} static Renode *newrep(struct cstate *g, Renode *atom, int ng, int min, int max){ Renode *rep = newnode(g, P_REP); if (max == REPINF && empty(atom)) die(g, "infinite loop matching the empty string"); rep->ng = ng; rep->m = min; rep->n = max; rep->x = atom; return rep;} static void next(struct cstate *g){ g->lookahead = lex(g);} static int accept(struct cstate *g, int t){ if (g->lookahead == t) { next(g); return 1; } return 0;} static Renode *parsealt(struct cstate *g); static Renode *parseatom(struct cstate *g){ Renode *atom; if (g->lookahead == L_CHAR) { atom = newnode(g, P_CHAR); atom->c = g->yychar; next(g); return atom; } if (g->lookahead == L_CCLASS) { atom = newnode(g, P_CCLASS); atom->cc = g->yycc; next(g); return atom;Lines 1–500 of 1221. Load more
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <setjmp.h> #include <limits.h> #include "regexp.h" #include "utf.h" #define emit regemit #define next regnext #define accept regaccept #ifndef nelem #define nelem(a) (int)(sizeof (a) / sizeof (a)[0]) #endif #define REPINF 255 #ifndef REG_MAXPROG #define REG_MAXPROG (32 << 10) #endif #ifndef REG_MAXREC #define REG_MAXREC 1024 #endif #ifndef REG_MAXSPAN #define REG_MAXSPAN 64 #endif #ifndef REG_MAXCLASS #define REG_MAXCLASS 16 #endif typedef struct Reclass Reclass; typedef struct Renode Renode; typedef struct Reinst Reinst; typedef struct Rethread Rethread; struct Reclass { Rune *end; Rune spans[REG_MAXSPAN]; }; struct Reprog { Reinst *start, *end; int flags; int nsub; Reclass cclass[REG_MAXCLASS]; }; struct cstate { Reprog *prog; Renode *pstart, *pend; const char *source; int ncclass; int nsub; Renode *sub[REG_MAXSUB]; int lookahead; Rune yychar; Reclass *yycc; int yymin, yymax; const char *error; jmp_buf kaboom; }; static void die(struct cstate *g, const char *message) { g->error = message; longjmp(g->kaboom, 1); } static int canon(Rune c) { Rune u = toupperrune(c); if (c >= 128 && u < 128) return c; return u; } /* Scan */ enum { L_CHAR = 256, L_CCLASS, /* character class */ L_NCCLASS, /* negative character class */ L_NC, /* "(?:" no capture */ L_PLA, /* "(?=" positive lookahead */ L_NLA, /* "(?!" negative lookahead */ L_WORD, /* "\b" word boundary */ L_NWORD, /* "\B" non-word boundary */ L_REF, /* "\1" back-reference */ L_COUNT, /* {M,N} */ }; static int hex(struct cstate *g, int c) { if (c >= '0' && c <= '9') return c - '0'; if (c >= 'a' && c <= 'f') return c - 'a' + 0xA; if (c >= 'A' && c <= 'F') return c - 'A' + 0xA; die(g, "invalid escape sequence"); return 0; } static int dec(struct cstate *g, int c) { if (c >= '0' && c <= '9') return c - '0'; die(g, "invalid quantifier"); return 0; } #define ESCAPES "BbDdSsWw^$\\.*+?()[]{}|-0123456789" static int isunicodeletter(int c) { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || isalpharune(c); } static int nextrune(struct cstate *g) { if (!*g->source) { g->yychar = EOF; return 0; } g->source += chartorune(&g->yychar, g->source); if (g->yychar == '\\') { if (!*g->source) die(g, "unterminated escape sequence"); g->source += chartorune(&g->yychar, g->source); switch (g->yychar) { case 'f': g->yychar = '\f'; return 0; case 'n': g->yychar = '\n'; return 0; case 'r': g->yychar = '\r'; return 0; case 't': g->yychar = '\t'; return 0; case 'v': g->yychar = '\v'; return 0; case 'c': if (!g->source[0]) die(g, "unterminated escape sequence"); g->yychar = (*g->source++) & 31; return 0; case 'x': if (!g->source[0] || !g->source[1]) die(g, "unterminated escape sequence"); g->yychar = hex(g, *g->source++) << 4; g->yychar += hex(g, *g->source++); if (g->yychar == 0) { g->yychar = '0'; return 1; } return 0; case 'u': if (!g->source[0] || !g->source[1] || !g->source[2] || !g->source[3]) die(g, "unterminated escape sequence"); g->yychar = hex(g, *g->source++) << 12; g->yychar += hex(g, *g->source++) << 8; g->yychar += hex(g, *g->source++) << 4; g->yychar += hex(g, *g->source++); if (g->yychar == 0) { g->yychar = '0'; return 1; } return 0; case 0: g->yychar = '0'; return 1; } if (strchr(ESCAPES, g->yychar)) return 1; if (isunicodeletter(g->yychar) || g->yychar == '_') /* check identity escape */ die(g, "invalid escape character"); return 0; } return 0; } static int lexcount(struct cstate *g) { g->yychar = *g->source++; g->yymin = dec(g, g->yychar); g->yychar = *g->source++; while (g->yychar != ',' && g->yychar != '}') { g->yymin = g->yymin * 10 + dec(g, g->yychar); g->yychar = *g->source++; if (g->yymin >= REPINF) die(g, "numeric overflow"); } if (g->yychar == ',') { g->yychar = *g->source++; if (g->yychar == '}') { g->yymax = REPINF; } else { g->yymax = dec(g, g->yychar); g->yychar = *g->source++; while (g->yychar != '}') { g->yymax = g->yymax * 10 + dec(g, g->yychar); g->yychar = *g->source++; if (g->yymax >= REPINF) die(g, "numeric overflow"); } } } else { g->yymax = g->yymin; } return L_COUNT; } static void newcclass(struct cstate *g) { if (g->ncclass >= nelem(g->prog->cclass)) die(g, "too many character classes"); g->yycc = g->prog->cclass + g->ncclass++; g->yycc->end = g->yycc->spans; } static void addrange(struct cstate *g, Rune a, Rune b) { if (a > b) die(g, "invalid character class range"); if (g->yycc->end + 2 >= g->yycc->spans + nelem(g->yycc->spans)) die(g, "too many character class ranges"); *g->yycc->end++ = a; *g->yycc->end++ = b; } static void addranges_d(struct cstate *g) { addrange(g, '0', '9'); } static void addranges_D(struct cstate *g) { addrange(g, 0, '0'-1); addrange(g, '9'+1, 0xFFFF); } static void addranges_s(struct cstate *g) { addrange(g, 0x9, 0xD); addrange(g, 0x20, 0x20); addrange(g, 0xA0, 0xA0); addrange(g, 0x2028, 0x2029); addrange(g, 0xFEFF, 0xFEFF); } static void addranges_S(struct cstate *g) { addrange(g, 0, 0x9-1); addrange(g, 0xD+1, 0x20-1); addrange(g, 0x20+1, 0xA0-1); addrange(g, 0xA0+1, 0x2028-1); addrange(g, 0x2029+1, 0xFEFF-1); addrange(g, 0xFEFF+1, 0xFFFF); } static void addranges_w(struct cstate *g) { addrange(g, '0', '9'); addrange(g, 'A', 'Z'); addrange(g, '_', '_'); addrange(g, 'a', 'z'); } static void addranges_W(struct cstate *g) { addrange(g, 0, '0'-1); addrange(g, '9'+1, 'A'-1); addrange(g, 'Z'+1, '_'-1); addrange(g, '_'+1, 'a'-1); addrange(g, 'z'+1, 0xFFFF); } static int lexclass(struct cstate *g) { int type = L_CCLASS; int quoted, havesave, havedash; Rune save = 0; newcclass(g); quoted = nextrune(g); if (!quoted && g->yychar == '^') { type = L_NCCLASS; quoted = nextrune(g); } havesave = havedash = 0; for (;;) { if (g->yychar == EOF) die(g, "unterminated character class"); if (!quoted && g->yychar == ']') break; if (!quoted && g->yychar == '-') { if (havesave) { if (havedash) { addrange(g, save, '-'); havesave = havedash = 0; } else { havedash = 1; } } else { save = '-'; havesave = 1; } } else if (quoted && strchr("DSWdsw", g->yychar)) { if (havesave) { addrange(g, save, save); if (havedash) addrange(g, '-', '-'); } switch (g->yychar) { case 'd': addranges_d(g); break; case 's': addranges_s(g); break; case 'w': addranges_w(g); break; case 'D': addranges_D(g); break; case 'S': addranges_S(g); break; case 'W': addranges_W(g); break; } havesave = havedash = 0; } else { if (quoted) { if (g->yychar == 'b') g->yychar = '\b'; else if (g->yychar == '0') g->yychar = 0; /* else identity escape */ } if (havesave) { if (havedash) { addrange(g, save, g->yychar); havesave = havedash = 0; } else { addrange(g, save, save); save = g->yychar; } } else { save = g->yychar; havesave = 1; } } quoted = nextrune(g); } if (havesave) { addrange(g, save, save); if (havedash) addrange(g, '-', '-'); } return type; } static int lex(struct cstate *g) { int quoted = nextrune(g); if (quoted) { switch (g->yychar) { case 'b': return L_WORD; case 'B': return L_NWORD; case 'd': newcclass(g); addranges_d(g); return L_CCLASS; case 's': newcclass(g); addranges_s(g); return L_CCLASS; case 'w': newcclass(g); addranges_w(g); return L_CCLASS; case 'D': newcclass(g); addranges_d(g); return L_NCCLASS; case 'S': newcclass(g); addranges_s(g); return L_NCCLASS; case 'W': newcclass(g); addranges_w(g); return L_NCCLASS; case '0': g->yychar = 0; return L_CHAR; } if (g->yychar >= '0' && g->yychar <= '9') { g->yychar -= '0'; if (*g->source >= '0' && *g->source <= '9') g->yychar = g->yychar * 10 + *g->source++ - '0'; return L_REF; } return L_CHAR; } switch (g->yychar) { case EOF: case '$': case ')': case '*': case '+': case '.': case '?': case '^': case '|': return g->yychar; } if (g->yychar == '{') return lexcount(g); if (g->yychar == '[') return lexclass(g); if (g->yychar == '(') { if (g->source[0] == '?') { if (g->source[1] == ':') { g->source += 2; return L_NC; } if (g->source[1] == '=') { g->source += 2; return L_PLA; } if (g->source[1] == '!') { g->source += 2; return L_NLA; } } return '('; } return L_CHAR; } /* Parse */ enum { P_CAT, P_ALT, P_REP, P_BOL, P_EOL, P_WORD, P_NWORD, P_PAR, P_PLA, P_NLA, P_ANY, P_CHAR, P_CCLASS, P_NCCLASS, P_REF, }; struct Renode { unsigned char type; unsigned char ng, m, n; Rune c; Reclass *cc; Renode *x; Renode *y; }; static Renode *newnode(struct cstate *g, int type) { Renode *node = g->pend++; node->type = type; node->cc = NULL; node->c = 0; node->ng = 0; node->m = 0; node->n = 0; node->x = node->y = NULL; return node; } static int empty(Renode *node) { if (!node) return 1; switch (node->type) { default: return 1; case P_CAT: return empty(node->x) && empty(node->y); case P_ALT: return empty(node->x) || empty(node->y); case P_REP: return empty(node->x) || node->m == 0; case P_PAR: return empty(node->x); case P_REF: return empty(node->x); case P_ANY: case P_CHAR: case P_CCLASS: case P_NCCLASS: return 0; } } static Renode *newrep(struct cstate *g, Renode *atom, int ng, int min, int max) { Renode *rep = newnode(g, P_REP); if (max == REPINF && empty(atom)) die(g, "infinite loop matching the empty string"); rep->ng = ng; rep->m = min; rep->n = max; rep->x = atom; return rep; } static void next(struct cstate *g) { g->lookahead = lex(g); } static int accept(struct cstate *g, int t) { if (g->lookahead == t) { next(g); return 1; } return 0; } static Renode *parsealt(struct cstate *g); static Renode *parseatom(struct cstate *g) { Renode *atom; if (g->lookahead == L_CHAR) { atom = newnode(g, P_CHAR); atom->c = g->yychar; next(g); return atom; } if (g->lookahead == L_CCLASS) { atom = newnode(g, P_CCLASS); atom->cc = g->yycc; next(g); return atom;