| 1 |
/* |
| 2 |
* re_*comp and friends - compile REs |
| 3 |
* This file #includes several others (see the bottom). |
| 4 |
* |
| 5 |
* Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. |
| 6 |
* |
| 7 |
* Development of this software was funded, in part, by Cray Research Inc., |
| 8 |
* UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics |
| 9 |
* Corporation, none of whom are responsible for the results. The author |
| 10 |
* thanks all of them. |
| 11 |
* |
| 12 |
* Redistribution and use in source and binary forms -- with or without |
| 13 |
* modification -- are permitted for any purpose, provided that |
| 14 |
* redistributions in source form retain this entire copyright notice and |
| 15 |
* indicate the origin and nature of any modifications. |
| 16 |
* |
| 17 |
* I'd appreciate being given credit for this package in the documentation |
| 18 |
* of software which uses it, but that is not a requirement. |
| 19 |
* |
| 20 |
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, |
| 21 |
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY |
| 22 |
* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL |
| 23 |
* HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 24 |
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 25 |
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; |
| 26 |
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, |
| 27 |
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR |
| 28 |
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF |
| 29 |
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 30 |
* |
| 31 |
* src/backend/regex/regcomp.c |
| 32 |
* |
| 33 |
*/ |
| 34 |
|
| 35 |
#include "regex/regguts.h" |
| 36 |
|
| 37 |
/* |
| 38 |
* forward declarations, up here so forward datatypes etc. are defined early |
| 39 |
*/ |
| 40 |
/* === regcomp.c === */ |
| 41 |
static void moresubs(struct vars *v, int wanted); |
| 42 |
static int freev(struct vars *v, int err); |
| 43 |
static void makesearch(struct vars *v, struct nfa *nfa); |
| 44 |
static struct subre *parse(struct vars *v, int stopper, int type, |
| 45 |
struct state *init, struct state *final); |
| 46 |
static struct subre *parsebranch(struct vars *v, int stopper, int type, |
| 47 |
struct state *left, struct state *right, |
| 48 |
int partial); |
| 49 |
static struct subre *parseqatom(struct vars *v, int stopper, int type, |
| 50 |
struct state *lp, struct state *rp, |
| 51 |
struct subre *top); |
| 52 |
static void nonword(struct vars *v, int dir, struct state *lp, |
| 53 |
struct state *rp); |
| 54 |
static void word(struct vars *v, int dir, struct state *lp, struct state *rp); |
| 55 |
static void charclass(struct vars *v, enum char_classes cls, struct state *lp, |
| 56 |
struct state *rp); |
| 57 |
static void charclasscomplement(struct vars *v, enum char_classes cls, |
| 58 |
struct state *lp, struct state *rp); |
| 59 |
static int scannum(struct vars *v); |
| 60 |
static void repeat(struct vars *v, struct state *lp, struct state *rp, |
| 61 |
int m, int n); |
| 62 |
static void bracket(struct vars *v, struct state *lp, struct state *rp); |
| 63 |
static void cbracket(struct vars *v, struct state *lp, struct state *rp); |
| 64 |
static void brackpart(struct vars *v, struct state *lp, struct state *rp, |
| 65 |
bool *have_cclassc); |
| 66 |
static const chr *scanplain(struct vars *v); |
| 67 |
static void onechr(struct vars *v, chr c, struct state *lp, struct state *rp); |
| 68 |
static void optimizebracket(struct vars *v, struct state *lp, struct state *rp); |
| 69 |
static void wordchrs(struct vars *v); |
| 70 |
static void processlacon(struct vars *v, struct state *begin, |
| 71 |
struct state *end, int latype, |
| 72 |
struct state *lp, struct state *rp); |
| 73 |
static struct subre *subre(struct vars *v, int op, int flags, |
| 74 |
struct state *begin, struct state *end); |
| 75 |
static void freesubre(struct vars *v, struct subre *sr); |
| 76 |
static void freesubreandsiblings(struct vars *v, struct subre *sr); |
| 77 |
static void freesrnode(struct vars *v, struct subre *sr); |
| 78 |
static void removecaptures(struct vars *v, struct subre *t); |
| 79 |
static int numst(struct subre *t, int start); |
| 80 |
static void markst(struct subre *t); |
| 81 |
static void cleanst(struct vars *v); |
| 82 |
static long nfatree(struct vars *v, struct subre *t, FILE *f); |
| 83 |
static long nfanode(struct vars *v, struct subre *t, |
| 84 |
int converttosearch, FILE *f); |
| 85 |
static int newlacon(struct vars *v, struct state *begin, struct state *end, |
| 86 |
int latype); |
| 87 |
static void freelacons(struct subre *subs, int n); |
| 88 |
static void rfree(regex_t *re); |
| 89 |
static int rstacktoodeep(void); |
| 90 |
|
| 91 |
#ifdef REG_DEBUG |
| 92 |
static void dump(regex_t *re, FILE *f); |
| 93 |
static void dumpst(struct subre *t, FILE *f, int nfapresent); |
| 94 |
static void stdump(struct subre *t, FILE *f, int nfapresent); |
| 95 |
static const char *stid(struct subre *t, char *buf, size_t bufsize); |
| 96 |
#endif |
| 97 |
/* === regc_lex.c === */ |
| 98 |
static void lexstart(struct vars *v); |
| 99 |
static void prefixes(struct vars *v); |
| 100 |
static int next(struct vars *v); |
| 101 |
static int lexescape(struct vars *v); |
| 102 |
static chr lexdigits(struct vars *v, int base, int minlen, int maxlen); |
| 103 |
static int brenext(struct vars *v, chr c); |
| 104 |
static void skip(struct vars *v); |
| 105 |
static chr newline(void); |
| 106 |
static chr chrnamed(struct vars *v, const chr *startp, const chr *endp, |
| 107 |
chr lastresort); |
| 108 |
|
| 109 |
/* === regc_color.c === */ |
| 110 |
static void initcm(struct vars *v, struct colormap *cm); |
| 111 |
static void freecm(struct colormap *cm); |
| 112 |
static color maxcolor(struct colormap *cm); |
| 113 |
static color newcolor(struct colormap *cm); |
| 114 |
static void freecolor(struct colormap *cm, color co); |
| 115 |
static color pseudocolor(struct colormap *cm); |
| 116 |
static color subcolor(struct colormap *cm, chr c); |
| 117 |
static color subcolorhi(struct colormap *cm, color *pco); |
| 118 |
static color newsub(struct colormap *cm, color co); |
| 119 |
static int newhicolorrow(struct colormap *cm, int oldrow); |
| 120 |
static void newhicolorcols(struct colormap *cm); |
| 121 |
static void subcolorcvec(struct vars *v, struct cvec *cv, struct state *lp, |
| 122 |
struct state *rp); |
| 123 |
static void subcoloronechr(struct vars *v, chr ch, struct state *lp, |
| 124 |
struct state *rp, color *lastsubcolor); |
| 125 |
static void subcoloronerange(struct vars *v, chr from, chr to, |
| 126 |
struct state *lp, struct state *rp, |
| 127 |
color *lastsubcolor); |
| 128 |
static void subcoloronerow(struct vars *v, int rownum, struct state *lp, |
| 129 |
struct state *rp, color *lastsubcolor); |
| 130 |
static void okcolors(struct nfa *nfa, struct colormap *cm); |
| 131 |
static void colorchain(struct colormap *cm, struct arc *a); |
| 132 |
static void uncolorchain(struct colormap *cm, struct arc *a); |
| 133 |
static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but, |
| 134 |
struct state *from, struct state *to); |
| 135 |
static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type, |
| 136 |
struct state *of, struct state *from, |
| 137 |
struct state *to); |
| 138 |
|
| 139 |
#ifdef REG_DEBUG |
| 140 |
static void dumpcolors(struct colormap *cm, FILE *f); |
| 141 |
static void dumpchr(chr c, FILE *f); |
| 142 |
#endif |
| 143 |
/* === regc_nfa.c === */ |
| 144 |
static struct nfa *newnfa(struct vars *v, struct colormap *cm, |
| 145 |
struct nfa *parent); |
| 146 |
static void freenfa(struct nfa *nfa); |
| 147 |
static struct state *newstate(struct nfa *nfa); |
| 148 |
static struct state *newfstate(struct nfa *nfa, int flag); |
| 149 |
static void dropstate(struct nfa *nfa, struct state *s); |
| 150 |
static void freestate(struct nfa *nfa, struct state *s); |
| 151 |
static void newarc(struct nfa *nfa, int t, color co, |
| 152 |
struct state *from, struct state *to); |
| 153 |
static void createarc(struct nfa *nfa, int t, color co, |
| 154 |
struct state *from, struct state *to); |
| 155 |
static struct arc *allocarc(struct nfa *nfa); |
| 156 |
static void freearc(struct nfa *nfa, struct arc *victim); |
| 157 |
static void changearcsource(struct arc *a, struct state *newfrom); |
| 158 |
static void changearctarget(struct arc *a, struct state *newto); |
| 159 |
static int hasnonemptyout(struct state *s); |
| 160 |
static struct arc *findarc(struct state *s, int type, color co); |
| 161 |
static void cparc(struct nfa *nfa, struct arc *oa, |
| 162 |
struct state *from, struct state *to); |
| 163 |
static void sortins(struct nfa *nfa, struct state *s); |
| 164 |
static int sortins_cmp(const void *a, const void *b); |
| 165 |
static void sortouts(struct nfa *nfa, struct state *s); |
| 166 |
static int sortouts_cmp(const void *a, const void *b); |
| 167 |
static void moveins(struct nfa *nfa, struct state *oldState, |
| 168 |
struct state *newState); |
| 169 |
static void copyins(struct nfa *nfa, struct state *oldState, |
| 170 |
struct state *newState); |
| 171 |
static void mergeins(struct nfa *nfa, struct state *s, |
| 172 |
struct arc **arcarray, int arccount); |
| 173 |
static void moveouts(struct nfa *nfa, struct state *oldState, |
| 174 |
struct state *newState); |
| 175 |
static void copyouts(struct nfa *nfa, struct state *oldState, |
| 176 |
struct state *newState); |
| 177 |
static void cloneouts(struct nfa *nfa, struct state *old, struct state *from, |
| 178 |
struct state *to, int type); |
| 179 |
static void delsub(struct nfa *nfa, struct state *lp, struct state *rp); |
| 180 |
static void deltraverse(struct nfa *nfa, struct state *leftend, |
| 181 |
struct state *s); |
| 182 |
static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop, |
| 183 |
struct state *from, struct state *to); |
| 184 |
static void duptraverse(struct nfa *nfa, struct state *s, struct state *stmp); |
| 185 |
static void removeconstraints(struct nfa *nfa, struct state *start, struct state *stop); |
| 186 |
static void removetraverse(struct nfa *nfa, struct state *s); |
| 187 |
static void cleartraverse(struct nfa *nfa, struct state *s); |
| 188 |
static struct state *single_color_transition(struct state *s1, |
| 189 |
struct state *s2); |
| 190 |
static void specialcolors(struct nfa *nfa); |
| 191 |
static long optimize(struct nfa *nfa, FILE *f); |
| 192 |
static void pullback(struct nfa *nfa, FILE *f); |
| 193 |
static int pull(struct nfa *nfa, struct arc *con, |
| 194 |
struct state **intermediates); |
| 195 |
static void pushfwd(struct nfa *nfa, FILE *f); |
| 196 |
static int push(struct nfa *nfa, struct arc *con, |
| 197 |
struct state **intermediates); |
| 198 |
|
| 199 |
#define INCOMPATIBLE 1 /* destroys arc */ |
| 200 |
#define SATISFIED 2 /* constraint satisfied */ |
| 201 |
#define COMPATIBLE 3 /* compatible but not satisfied yet */ |
| 202 |
#define REPLACEARC 4 /* replace arc's color with constraint color */ |
| 203 |
static int combine(struct nfa *nfa, struct arc *con, struct arc *a); |
| 204 |
static void fixempties(struct nfa *nfa, FILE *f); |
| 205 |
static struct state *emptyreachable(struct nfa *nfa, struct state *s, |
| 206 |
struct state *lastfound, |
| 207 |
struct arc **inarcsorig); |
| 208 |
static int isconstraintarc(struct arc *a); |
| 209 |
static int hasconstraintout(struct state *s); |
| 210 |
static void fixconstraintloops(struct nfa *nfa, FILE *f); |
| 211 |
static int findconstraintloop(struct nfa *nfa, struct state *s); |
| 212 |
static void breakconstraintloop(struct nfa *nfa, struct state *sinitial); |
| 213 |
static void clonesuccessorstates(struct nfa *nfa, struct state *ssource, |
| 214 |
struct state *sclone, |
| 215 |
struct state *spredecessor, |
| 216 |
struct arc *refarc, char *curdonemap, |
| 217 |
char *outerdonemap, int nstates); |
| 218 |
static void removecantmatch(struct nfa *nfa); |
| 219 |
static void cleanup(struct nfa *nfa); |
| 220 |
static void markreachable(struct nfa *nfa, struct state *s, |
| 221 |
struct state *okay, struct state *mark); |
| 222 |
static void markcanreach(struct nfa *nfa, struct state *s, struct state *okay, |
| 223 |
struct state *mark); |
| 224 |
static long analyze(struct nfa *nfa); |
| 225 |
static void checkmatchall(struct nfa *nfa); |
| 226 |
static bool checkmatchall_recurse(struct nfa *nfa, struct state *s, |
| 227 |
bool **haspaths); |
| 228 |
static bool check_out_colors_match(struct state *s, color co1, color co2); |
| 229 |
static bool check_in_colors_match(struct state *s, color co1, color co2); |
| 230 |
static void compact(struct nfa *nfa, struct cnfa *cnfa); |
| 231 |
static void carcsort(struct carc *first, size_t n); |
| 232 |
static int carc_cmp(const void *a, const void *b); |
| 233 |
static void freecnfa(struct cnfa *cnfa); |
| 234 |
static void dumpnfa(struct nfa *nfa, FILE *f); |
| 235 |
|
| 236 |
#ifdef REG_DEBUG |
| 237 |
static void dumpstate(struct state *s, FILE *f); |
| 238 |
static void dumparcs(struct state *s, FILE *f); |
| 239 |
static void dumparc(struct arc *a, struct state *s, FILE *f); |
| 240 |
static void dumpcnfa(struct cnfa *cnfa, FILE *f); |
| 241 |
static void dumpcstate(int st, struct cnfa *cnfa, FILE *f); |
| 242 |
#endif |
| 243 |
/* === regc_cvec.c === */ |
| 244 |
static struct cvec *newcvec(int nchrs, int nranges); |
| 245 |
static struct cvec *clearcvec(struct cvec *cv); |
| 246 |
static void addchr(struct cvec *cv, chr c); |
| 247 |
static void addrange(struct cvec *cv, chr from, chr to); |
| 248 |
static struct cvec *getcvec(struct vars *v, int nchrs, int nranges); |
| 249 |
static void freecvec(struct cvec *cv); |
| 250 |
|
| 251 |
/* === regc_pg_locale.c === */ |
| 252 |
static int pg_wc_isdigit(pg_wchar c); |
| 253 |
static int pg_wc_isalpha(pg_wchar c); |
| 254 |
static int pg_wc_isalnum(pg_wchar c); |
| 255 |
static int pg_wc_isword(pg_wchar c); |
| 256 |
static int pg_wc_isupper(pg_wchar c); |
| 257 |
static int pg_wc_islower(pg_wchar c); |
| 258 |
static int pg_wc_isgraph(pg_wchar c); |
| 259 |
static int pg_wc_isprint(pg_wchar c); |
| 260 |
static int pg_wc_ispunct(pg_wchar c); |
| 261 |
static int pg_wc_isspace(pg_wchar c); |
| 262 |
static pg_wchar pg_wc_toupper(pg_wchar c); |
| 263 |
static pg_wchar pg_wc_tolower(pg_wchar c); |
| 264 |
|
| 265 |
/* === regc_locale.c === */ |
| 266 |
static chr element(struct vars *v, const chr *startp, const chr *endp); |
| 267 |
static struct cvec *range(struct vars *v, chr a, chr b, int cases); |
| 268 |
static int before(chr x, chr y); |
| 269 |
static struct cvec *eclass(struct vars *v, chr c, int cases); |
| 270 |
static enum char_classes lookupcclass(struct vars *v, const chr *startp, |
| 271 |
const chr *endp); |
| 272 |
static struct cvec *cclasscvec(struct vars *v, enum char_classes cclasscode, |
| 273 |
int cases); |
| 274 |
static int cclass_column_index(struct colormap *cm, chr c); |
| 275 |
static struct cvec *allcases(struct vars *v, chr c); |
| 276 |
static int cmp(const chr *x, const chr *y, size_t len); |
| 277 |
static int casecmp(const chr *x, const chr *y, size_t len); |
| 278 |
|
| 279 |
|
| 280 |
/* internal variables, bundled for easy passing around */ |
| 281 |
struct vars |
| 282 |
{ |
| 283 |
regex_t *re; |
| 284 |
const chr *now; /* scan pointer into string */ |
| 285 |
const chr *stop; /* end of string */ |
| 286 |
int err; /* error code (0 if none) */ |
| 287 |
int cflags; /* copy of compile flags */ |
| 288 |
int lasttype; /* type of previous token */ |
| 289 |
int nexttype; /* type of next token */ |
| 290 |
chr nextvalue; /* value (if any) of next token */ |
| 291 |
int lexcon; /* lexical context type (see regc_lex.c) */ |
| 292 |
int nsubexp; /* subexpression count */ |
| 293 |
struct subre **subs; /* subRE pointer vector */ |
| 294 |
size_t nsubs; /* length of vector */ |
| 295 |
struct subre *sub10[10]; /* initial vector, enough for most */ |
| 296 |
struct nfa *nfa; /* the NFA */ |
| 297 |
struct colormap *cm; /* character color map */ |
| 298 |
color nlcolor; /* color of newline */ |
| 299 |
struct state *wordchrs; /* state in nfa holding word-char outarcs */ |
| 300 |
struct subre *tree; /* subexpression tree */ |
| 301 |
struct subre *treechain; /* all tree nodes allocated */ |
| 302 |
struct subre *treefree; /* any free tree nodes */ |
| 303 |
int ntree; /* number of tree nodes, plus one */ |
| 304 |
struct cvec *cv; /* interface cvec */ |
| 305 |
struct cvec *cv2; /* utility cvec */ |
| 306 |
struct subre *lacons; /* lookaround-constraint vector */ |
| 307 |
int nlacons; /* size of lacons[]; note that only slots |
| 308 |
* numbered 1 .. nlacons-1 are used */ |
| 309 |
size_t spaceused; /* approx. space used for compilation */ |
| 310 |
}; |
| 311 |
|
| 312 |
/* parsing macros; most know that `v' is the struct vars pointer */ |
| 313 |
#define NEXT() (next(v)) /* advance by one token */ |
| 314 |
#define SEE(t) (v->nexttype == (t)) /* is next token this? */ |
| 315 |
#define EAT(t) (SEE(t) && next(v)) /* if next is this, swallow it */ |
| 316 |
#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ |
| 317 |
#define ISERR() VISERR(v) |
| 318 |
#define VERR(vv,e) ((vv)->nexttype = EOS, \ |
| 319 |
(vv)->err = ((vv)->err ? (vv)->err : (e))) |
| 320 |
#define ERR(e) VERR(v, e) /* record an error */ |
| 321 |
#define NOERR() {if (ISERR()) return;} /* if error seen, return */ |
| 322 |
#define NOERRN() {if (ISERR()) return NULL;} /* NOERR with retval */ |
| 323 |
#define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */ |
| 324 |
#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0) /* error if c false */ |
| 325 |
#define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */ |
| 326 |
#define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y) |
| 327 |
|
| 328 |
/* token type codes, some also used as NFA arc types */ |
| 329 |
#define EMPTY 'n' /* no token present */ |
| 330 |
#define EOS 'e' /* end of string */ |
| 331 |
#define PLAIN 'p' /* ordinary character */ |
| 332 |
#define DIGIT 'd' /* digit (in bound) */ |
| 333 |
#define BACKREF 'b' /* back reference */ |
| 334 |
#define COLLEL 'I' /* start of [. */ |
| 335 |
#define ECLASS 'E' /* start of [= */ |
| 336 |
#define CCLASS 'C' /* start of [: */ |
| 337 |
#define END 'X' /* end of [. [= [: */ |
| 338 |
#define CCLASSS 's' /* char class shorthand escape */ |
| 339 |
#define CCLASSC 'c' /* complement char class shorthand escape */ |
| 340 |
#define RANGE 'R' /* - within [] which might be range delim. */ |
| 341 |
#define LACON 'L' /* lookaround constraint subRE */ |
| 342 |
#define AHEAD 'a' /* color-lookahead arc */ |
| 343 |
#define BEHIND 'r' /* color-lookbehind arc */ |
| 344 |
#define WBDRY 'w' /* word boundary constraint */ |
| 345 |
#define NWBDRY 'W' /* non-word-boundary constraint */ |
| 346 |
#define CANTMATCH 'x' /* arc that cannot match anything */ |
| 347 |
#define SBEGIN 'A' /* beginning of string (even if not BOL) */ |
| 348 |
#define SEND 'Z' /* end of string (even if not EOL) */ |
| 349 |
|
| 350 |
/* is an arc colored, and hence should belong to a color chain? */ |
| 351 |
/* the test on "co" eliminates RAINBOW arcs, which we don't bother to chain */ |
| 352 |
#define COLORED(a) \ |
| 353 |
((a)->co >= 0 && \ |
| 354 |
((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND)) |
| 355 |
|
| 356 |
|
| 357 |
/* static function list */ |
| 358 |
static const struct fns functions = { |
| 359 |
rfree, /* regfree insides */ |
| 360 |
rstacktoodeep /* check for stack getting dangerously deep */ |
| 361 |
}; |
| 362 |
|
| 363 |
|
| 364 |
|
| 365 |
/* |
| 366 |
* pg_regcomp - compile regular expression |
| 367 |
* |
| 368 |
* Note: on failure, no resources remain allocated, so pg_regfree() |
| 369 |
* need not be applied to re. |
| 370 |
*/ |
| 371 |
int |
| 372 |
pg_regcomp(regex_t *re, |
| 373 |
const chr *string, |
| 374 |
size_t len, |
| 375 |
int flags, |
| 376 |
Oid collation) |
| 377 |
{ |
| 378 |
struct vars var; |
| 379 |
struct vars *v = &var; |
| 380 |
struct guts *g; |
| 381 |
int i; |
| 382 |
size_t j; |
| 383 |
|
| 384 |
#ifdef REG_DEBUG |
| 385 |
FILE *debug = (flags & REG_PROGRESS) ? stdout : (FILE *) NULL; |
| 386 |
#else |
| 387 |
FILE *debug = (FILE *) NULL; |
| 388 |
#endif |
| 389 |
|
| 390 |
#define CNOERR() { if (ISERR()) return freev(v, v->err); } |
| 391 |
|
| 392 |
/* sanity checks */ |
| 393 |
|
| 394 |
if (re == NULL || string == NULL) |
| 395 |
return REG_INVARG; |
| 396 |
if ((flags & REG_QUOTE) && |
| 397 |
(flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE))) |
| 398 |
return REG_INVARG; |
| 399 |
if (!(flags & REG_EXTENDED) && (flags & REG_ADVF)) |
| 400 |
return REG_INVARG; |
| 401 |
|
| 402 |
/* Initialize locale-dependent support */ |
| 403 |
pg_set_regex_collation(collation); |
| 404 |
|
| 405 |
/* initial setup (after which freev() is callable) */ |
| 406 |
v->re = re; |
| 407 |
v->now = string; |
| 408 |
v->stop = v->now + len; |
| 409 |
v->err = 0; |
| 410 |
v->cflags = flags; |
| 411 |
v->nsubexp = 0; |
| 412 |
v->subs = v->sub10; |
| 413 |
v->nsubs = 10; |
| 414 |
for (j = 0; j < v->nsubs; j++) |
| 415 |
v->subs[j] = NULL; |
| 416 |
v->nfa = NULL; |
| 417 |
v->cm = NULL; |
| 418 |
v->nlcolor = COLORLESS; |
| 419 |
v->wordchrs = NULL; |
| 420 |
v->tree = NULL; |
| 421 |
v->treechain = NULL; |
| 422 |
v->treefree = NULL; |
| 423 |
v->cv = NULL; |
| 424 |
v->cv2 = NULL; |
| 425 |
v->lacons = NULL; |
| 426 |
v->nlacons = 0; |
| 427 |
v->spaceused = 0; |
| 428 |
re->re_magic = REMAGIC; |
| 429 |
re->re_info = 0; /* bits get set during parse */ |
| 430 |
re->re_csize = sizeof(chr); |
| 431 |
re->re_collation = collation; |
| 432 |
re->re_guts = NULL; |
| 433 |
re->re_fns = VS(&functions); |
| 434 |
|
| 435 |
/* more complex setup, malloced things */ |
| 436 |
re->re_guts = VS(MALLOC(sizeof(struct guts))); |
| 437 |
if (re->re_guts == NULL) |
| 438 |
return freev(v, REG_ESPACE); |
| 439 |
g = (struct guts *) re->re_guts; |
| 440 |
g->tree = NULL; |
| 441 |
initcm(v, &g->cmap); |
| 442 |
v->cm = &g->cmap; |
| 443 |
g->lacons = NULL; |
| 444 |
g->nlacons = 0; |
| 445 |
ZAPCNFA(g->search); |
| 446 |
v->nfa = newnfa(v, v->cm, (struct nfa *) NULL); |
| 447 |
CNOERR(); |
| 448 |
/* set up a reasonably-sized transient cvec for getcvec usage */ |
| 449 |
v->cv = newcvec(100, 20); |
| 450 |
if (v->cv == NULL) |
| 451 |
return freev(v, REG_ESPACE); |
| 452 |
|
| 453 |
/* parsing */ |
| 454 |
lexstart(v); /* also handles prefixes */ |
| 455 |
if ((v->cflags & REG_NLSTOP) || (v->cflags & REG_NLANCH)) |
| 456 |
{ |
| 457 |
/* assign newline a unique color */ |
| 458 |
v->nlcolor = subcolor(v->cm, newline()); |
| 459 |
okcolors(v->nfa, v->cm); |
| 460 |
} |
| 461 |
CNOERR(); |
| 462 |
v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final); |
| 463 |
assert(SEE(EOS)); /* even if error; ISERR() => SEE(EOS) */ |
| 464 |
CNOERR(); |
| 465 |
assert(v->tree != NULL); |
| 466 |
|
| 467 |
/* finish setup of nfa and its subre tree */ |
| 468 |
specialcolors(v->nfa); |
| 469 |
CNOERR(); |
| 470 |
#ifdef REG_DEBUG |
| 471 |
if (debug != NULL) |
| 472 |
{ |
| 473 |
fprintf(debug, "\n\n\n========= RAW ==========\n"); |
| 474 |
dumpnfa(v->nfa, debug); |
| 475 |
dumpst(v->tree, debug, 1); |
| 476 |
} |
| 477 |
#endif |
| 478 |
if (v->cflags & REG_NOSUB) |
| 479 |
removecaptures(v, v->tree); |
| 480 |
v->ntree = numst(v->tree, 1); |
| 481 |
markst(v->tree); |
| 482 |
cleanst(v); |
| 483 |
#ifdef REG_DEBUG |
| 484 |
if (debug != NULL) |
| 485 |
{ |
| 486 |
fprintf(debug, "\n\n\n========= TREE FIXED ==========\n"); |
| 487 |
dumpst(v->tree, debug, 1); |
| 488 |
} |
| 489 |
#endif |
| 490 |
|
| 491 |
/* build compacted NFAs for tree and lacons */ |
| 492 |
re->re_info |= nfatree(v, v->tree, debug); |
| 493 |
CNOERR(); |
| 494 |
assert(v->nlacons == 0 || v->lacons != NULL); |
| 495 |
for (i = 1; i < v->nlacons; i++) |
| 496 |
{ |
| 497 |
struct subre *lasub = &v->lacons[i]; |
| 498 |
|
| 499 |
#ifdef REG_DEBUG |
| 500 |
if (debug != NULL) |
| 501 |
fprintf(debug, "\n\n\n========= LA%d ==========\n", i); |
| 502 |
#endif |
| 503 |
|
| 504 |
/* Prepend .* to pattern if it's a lookbehind LACON */ |
| 505 |
nfanode(v, lasub, !LATYPE_IS_AHEAD(lasub->latype), debug); |
| 506 |
} |
| 507 |
CNOERR(); |
| 508 |
if (v->tree->flags & SHORTER) |
| 509 |
NOTE(REG_USHORTEST); |
| 510 |
|
| 511 |
/* build compacted NFAs for tree, lacons, fast search */ |
| 512 |
#ifdef REG_DEBUG |
| 513 |
if (debug != NULL) |
| 514 |
fprintf(debug, "\n\n\n========= SEARCH ==========\n"); |
| 515 |
#endif |
| 516 |
/* can sacrifice main NFA now, so use it as work area */ |
| 517 |
(DISCARD) optimize(v->nfa, debug); |
| 518 |
CNOERR(); |
| 519 |
makesearch(v, v->nfa); |
| 520 |
CNOERR(); |
| 521 |
compact(v->nfa, &g->search); |
| 522 |
CNOERR(); |
| 523 |
|
| 524 |
/* looks okay, package it up */ |
| 525 |
re->re_nsub = v->nsubexp; |
| 526 |
v->re = NULL; /* freev no longer frees re */ |
| 527 |
g->magic = GUTSMAGIC; |
| 528 |
g->cflags = v->cflags; |
| 529 |
g->info = re->re_info; |
| 530 |
g->nsub = re->re_nsub; |
| 531 |
g->tree = v->tree; |
| 532 |
v->tree = NULL; |
| 533 |
g->ntree = v->ntree; |
| 534 |
g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp; |
| 535 |
g->lacons = v->lacons; |
| 536 |
v->lacons = NULL; |
| 537 |
g->nlacons = v->nlacons; |
| 538 |
|
| 539 |
#ifdef REG_DEBUG |
| 540 |
if (flags & REG_DUMP) |
| 541 |
{ |
| 542 |
dump(re, stdout); |
| 543 |
fflush(stdout); |
| 544 |
} |
| 545 |
#endif |
| 546 |
|
| 547 |
assert(v->err == 0); |
| 548 |
return freev(v, 0); |
| 549 |
} |
| 550 |
|
| 551 |
/* |
| 552 |
* moresubs - enlarge subRE vector |
| 553 |
*/ |
| 554 |
static void |
| 555 |
moresubs(struct vars *v, |
| 556 |
int wanted) /* want enough room for this one */ |
| 557 |
{ |
| 558 |
struct subre **p; |
| 559 |
size_t n; |
| 560 |
|
| 561 |
assert(wanted > 0 && (size_t) wanted >= v->nsubs); |
| 562 |
n = (size_t) wanted * 3 / 2 + 1; |
| 563 |
|
| 564 |
/* n is bounded by the number of states, so no chance of overflow here */ |
| 565 |
if (v->subs == v->sub10) |
| 566 |
{ |
| 567 |
p = (struct subre **) MALLOC(n * sizeof(struct subre *)); |
| 568 |
if (p != NULL) |
| 569 |
memcpy(VS(p), VS(v->subs), |
| 570 |
v->nsubs * sizeof(struct subre *)); |
| 571 |
} |
| 572 |
else |
| 573 |
p = (struct subre **) REALLOC(v->subs, n * sizeof(struct subre *)); |
| 574 |
if (p == NULL) |
| 575 |
{ |
| 576 |
ERR(REG_ESPACE); |
| 577 |
return; |
| 578 |
} |
| 579 |
v->subs = p; |
| 580 |
for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++) |
| 581 |
*p = NULL; |
| 582 |
assert(v->nsubs == n); |
| 583 |
assert((size_t) wanted < v->nsubs); |
| 584 |
} |
| 585 |
|
| 586 |
/* |
| 587 |
* freev - free vars struct's substructures where necessary |
| 588 |
* |
| 589 |
* Optionally does error-number setting, and always returns error code |
| 590 |
* (if any), to make error-handling code terser. |
| 591 |
*/ |
| 592 |
static int |
| 593 |
freev(struct vars *v, |
| 594 |
int err) |
| 595 |
{ |
| 596 |
if (v->re != NULL) |
| 597 |
rfree(v->re); |
| 598 |
if (v->subs != v->sub10) |
| 599 |
FREE(v->subs); |
| 600 |
if (v->nfa != NULL) |
| 601 |
freenfa(v->nfa); |
| 602 |
if (v->tree != NULL) |
| 603 |
freesubre(v, v->tree); |
| 604 |
if (v->treechain != NULL) |
| 605 |
cleanst(v); |
| 606 |
if (v->cv != NULL) |
| 607 |
freecvec(v->cv); |
| 608 |
if (v->cv2 != NULL) |
| 609 |
freecvec(v->cv2); |
| 610 |
if (v->lacons != NULL) |
| 611 |
freelacons(v->lacons, v->nlacons); |
| 612 |
ERR(err); /* nop if err==0 */ |
| 613 |
|
| 614 |
return v->err; |
| 615 |
} |
| 616 |
|
| 617 |
/* |
| 618 |
* makesearch - turn an NFA into a search NFA (implicit prepend of .*?) |
| 619 |
* NFA must have been optimize()d already. |
| 620 |
*/ |
| 621 |
static void |
| 622 |
makesearch(struct vars *v, |
| 623 |
struct nfa *nfa) |
| 624 |
{ |
| 625 |
struct arc *a; |
| 626 |
struct arc *b; |
| 627 |
struct state *pre = nfa->pre; |
| 628 |
struct state *s; |
| 629 |
struct state *s2; |
| 630 |
struct state *slist; |
| 631 |
|
| 632 |
/* no loops are needed if it's anchored */ |
| 633 |
for (a = pre->outs; a != NULL; a = a->outchain) |
| 634 |
{ |
| 635 |
assert(a->type == PLAIN); |
| 636 |
if (a->co != nfa->bos[0] && a->co != nfa->bos[1]) |
| 637 |
break; |
| 638 |
} |
| 639 |
if (a != NULL) |
| 640 |
{ |
| 641 |
/* add implicit .* in front */ |
| 642 |
rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre); |
| 643 |
|
| 644 |
/* and ^* and \A* too -- not always necessary, but harmless */ |
| 645 |
newarc(nfa, PLAIN, nfa->bos[0], pre, pre); |
| 646 |
newarc(nfa, PLAIN, nfa->bos[1], pre, pre); |
| 647 |
|
| 648 |
/* |
| 649 |
* The pattern is still MATCHALL if it was before, but the max match |
| 650 |
* length is now infinity. |
| 651 |
*/ |
| 652 |
if (nfa->flags & MATCHALL) |
| 653 |
nfa->maxmatchall = DUPINF; |
| 654 |
} |
| 655 |
|
| 656 |
/* |
| 657 |
* Now here's the subtle part. Because many REs have no lookback |
| 658 |
* constraints, often knowing when you were in the pre state tells you |
| 659 |
* little; it's the next state(s) that are informative. But some of them |
| 660 |
* may have other inarcs, i.e. it may be possible to make actual progress |
| 661 |
* and then return to one of them. We must de-optimize such cases, |
| 662 |
* splitting each such state into progress and no-progress states. |
| 663 |
*/ |
| 664 |
|
| 665 |
/* first, make a list of the states reachable from pre and elsewhere */ |
| 666 |
slist = NULL; |
| 667 |
for (a = pre->outs; a != NULL; a = a->outchain) |
| 668 |
{ |
| 669 |
s = a->to; |
| 670 |
for (b = s->ins; b != NULL; b = b->inchain) |
| 671 |
{ |
| 672 |
if (b->from != pre) |
| 673 |
break; |
| 674 |
} |
| 675 |
|
| 676 |
/* |
| 677 |
* We want to mark states as being in the list already by having non |
| 678 |
* NULL tmp fields, but we can't just store the old slist value in tmp |
| 679 |
* because that doesn't work for the first such state. Instead, the |
| 680 |
* first list entry gets its own address in tmp. |
| 681 |
*/ |
| 682 |
if (b != NULL && s->tmp == NULL) |
| 683 |
{ |
| 684 |
s->tmp = (slist != NULL) ? slist : s; |
| 685 |
slist = s; |
| 686 |
} |
| 687 |
} |
| 688 |
|
| 689 |
/* do the splits */ |
| 690 |
for (s = slist; s != NULL; s = s2) |
| 691 |
{ |
| 692 |
s2 = newstate(nfa); |
| 693 |
NOERR(); |
| 694 |
copyouts(nfa, s, s2); |
| 695 |
NOERR(); |
| 696 |
for (a = s->ins; a != NULL; a = b) |
| 697 |
{ |
| 698 |
b = a->inchain; |
| 699 |
if (a->from != pre) |
| 700 |
{ |
| 701 |
cparc(nfa, a, a->from, s2); |
| 702 |
freearc(nfa, a); |
| 703 |
} |
| 704 |
} |
| 705 |
s2 = (s->tmp != s) ? s->tmp : NULL; |
| 706 |
s->tmp = NULL; /* clean up while we're at it */ |
| 707 |
} |
| 708 |
} |
| 709 |
|
| 710 |
/* |
| 711 |
* parse - parse an RE |
| 712 |
* |
| 713 |
* This is actually just the top level, which parses a bunch of branches |
| 714 |
* tied together with '|'. If there's more than one, they appear in the |
| 715 |
* tree as the children of a '|' subre. |
| 716 |
*/ |
| 717 |
static struct subre * |
| 718 |
parse(struct vars *v, |
| 719 |
int stopper, /* EOS or ')' */ |
| 720 |
int type, /* LACON (lookaround subRE) or PLAIN */ |
| 721 |
struct state *init, /* initial state */ |
| 722 |
struct state *final) /* final state */ |
| 723 |
{ |
| 724 |
struct subre *branches; /* top level */ |
| 725 |
struct subre *lastbranch; /* latest branch */ |
| 726 |
|
| 727 |
assert(stopper == ')' || stopper == EOS); |
| 728 |
|
| 729 |
branches = subre(v, '|', LONGER, init, final); |
| 730 |
NOERRN(); |
| 731 |
lastbranch = NULL; |
| 732 |
do |
| 733 |
{ /* a branch */ |
| 734 |
struct subre *branch; |
| 735 |
struct state *left; /* scaffolding for branch */ |
| 736 |
struct state *right; |
| 737 |
|
| 738 |
left = newstate(v->nfa); |
| 739 |
right = newstate(v->nfa); |
| 740 |
NOERRN(); |
| 741 |
EMPTYARC(init, left); |
| 742 |
EMPTYARC(right, final); |
| 743 |
NOERRN(); |
| 744 |
branch = parsebranch(v, stopper, type, left, right, 0); |
| 745 |
NOERRN(); |
| 746 |
if (lastbranch) |
| 747 |
lastbranch->sibling = branch; |
| 748 |
else |
| 749 |
branches->child = branch; |
| 750 |
branches->flags |= UP(branches->flags | branch->flags); |
| 751 |
lastbranch = branch; |
| 752 |
} while (EAT('|')); |
| 753 |
assert(SEE(stopper) || SEE(EOS)); |
| 754 |
|
| 755 |
if (!SEE(stopper)) |
| 756 |
{ |
| 757 |
assert(stopper == ')' && SEE(EOS)); |
| 758 |
ERR(REG_EPAREN); |
| 759 |
} |
| 760 |
|
| 761 |
/* optimize out simple cases */ |
| 762 |
if (lastbranch == branches->child) |
| 763 |
{ /* only one branch */ |
| 764 |
assert(lastbranch->sibling == NULL); |
| 765 |
freesrnode(v, branches); |
| 766 |
branches = lastbranch; |
| 767 |
} |
| 768 |
else if (!MESSY(branches->flags)) |
| 769 |
{ /* no interesting innards */ |
| 770 |
freesubreandsiblings(v, branches->child); |
| 771 |
branches->child = NULL; |
| 772 |
branches->op = '='; |
| 773 |
} |
| 774 |
|
| 775 |
return branches; |
| 776 |
} |
| 777 |
|
| 778 |
/* |
| 779 |
* parsebranch - parse one branch of an RE |
| 780 |
* |
| 781 |
* This mostly manages concatenation, working closely with parseqatom(). |
| 782 |
* Concatenated things are bundled up as much as possible, with separate |
| 783 |
* '.' nodes introduced only when necessary due to substructure. |
| 784 |
*/ |
| 785 |
static struct subre * |
| 786 |
parsebranch(struct vars *v, |
| 787 |
int stopper, /* EOS or ')' */ |
| 788 |
int type, /* LACON (lookaround subRE) or PLAIN */ |
| 789 |
struct state *left, /* leftmost state */ |
| 790 |
struct state *right, /* rightmost state */ |
| 791 |
int partial) /* is this only part of a branch? */ |
| 792 |
{ |
| 793 |
struct state *lp; /* left end of current construct */ |
| 794 |
int seencontent; /* is there anything in this branch yet? */ |
| 795 |
struct subre *t; |
| 796 |
|
| 797 |
lp = left; |
| 798 |
seencontent = 0; |
| 799 |
t = subre(v, '=', 0, left, right); /* op '=' is tentative */ |
| 800 |
NOERRN(); |
| 801 |
while (!SEE('|') && !SEE(stopper) && !SEE(EOS)) |
| 802 |
{ |
| 803 |
if (seencontent) |
| 804 |
{ /* implicit concat operator */ |
| 805 |
lp = newstate(v->nfa); |
| 806 |
NOERRN(); |
| 807 |
moveins(v->nfa, right, lp); |
| 808 |
} |
| 809 |
seencontent = 1; |
| 810 |
|
| 811 |
/* NB, recursion in parseqatom() may swallow rest of branch */ |
| 812 |
t = parseqatom(v, stopper, type, lp, right, t); |
| 813 |
NOERRN(); |
| 814 |
} |
| 815 |
|
| 816 |
if (!seencontent) |
| 817 |
{ /* empty branch */ |
| 818 |
if (!partial) |
| 819 |
NOTE(REG_UUNSPEC); |
| 820 |
assert(lp == left); |
| 821 |
EMPTYARC(left, right); |
| 822 |
} |
| 823 |
|
| 824 |
return t; |
| 825 |
} |
| 826 |
|
| 827 |
/* |
| 828 |
* parseqatom - parse one quantified atom or constraint of an RE |
| 829 |
* |
| 830 |
* The bookkeeping near the end cooperates very closely with parsebranch(); |
| 831 |
* in particular, it contains a recursion that can involve parsing the rest |
| 832 |
* of the branch, making this function's name somewhat inaccurate. |
| 833 |
* |
| 834 |
* Usually, the return value is just "top", but in some cases where we |
| 835 |
* have parsed the rest of the branch, we may deem "top" redundant and |
| 836 |
* free it, returning some child subre instead. |
| 837 |
*/ |
| 838 |
static struct subre * |
| 839 |
parseqatom(struct vars *v, |
| 840 |
int stopper, /* EOS or ')' */ |
| 841 |
int type, /* LACON (lookaround subRE) or PLAIN */ |
| 842 |
struct state *lp, /* left state to hang it on */ |
| 843 |
struct state *rp, /* right state to hang it on */ |
| 844 |
struct subre *top) /* subtree top */ |
| 845 |
{ |
| 846 |
struct state *s; /* temporaries for new states */ |
| 847 |
struct state *s2; |
| 848 |
|
| 849 |
#define ARCV(t, val) newarc(v->nfa, t, val, lp, rp) |
| 850 |
int m, |
| 851 |
n; |
| 852 |
struct subre *atom; /* atom's subtree */ |
| 853 |
struct subre *t; |
| 854 |
int cap; /* capturing parens? */ |
| 855 |
int latype; /* lookaround constraint type */ |
| 856 |
int subno; /* capturing-parens or backref number */ |
| 857 |
int atomtype; |
| 858 |
int qprefer; /* quantifier short/long preference */ |
| 859 |
int f; |
| 860 |
struct subre **atomp; /* where the pointer to atom is */ |
| 861 |
|
| 862 |
/* initial bookkeeping */ |
| 863 |
atom = NULL; |
| 864 |
assert(lp->nouts == 0); /* must string new code */ |
| 865 |
assert(rp->nins == 0); /* between lp and rp */ |
| 866 |
subno = 0; /* just to shut lint up */ |
| 867 |
|
| 868 |
/* an atom or constraint... */ |
| 869 |
atomtype = v->nexttype; |
| 870 |
switch (atomtype) |
| 871 |
{ |
| 872 |
/* first, constraints, which end by returning */ |
| 873 |
case '^': |
| 874 |
ARCV('^', 1); |
| 875 |
if (v->cflags & REG_NLANCH) |
| 876 |
ARCV(BEHIND, v->nlcolor); |
| 877 |
NEXT(); |
| 878 |
return top; |
| 879 |
break; |
| 880 |
case '$': |
| 881 |
ARCV('$', 1); |
| 882 |
if (v->cflags & REG_NLANCH) |
| 883 |
ARCV(AHEAD, v->nlcolor); |
| 884 |
NEXT(); |
| 885 |
return top; |
| 886 |
break; |
| 887 |
case SBEGIN: |
| 888 |
ARCV('^', 1); /* BOL */ |
| 889 |
ARCV('^', 0); /* or BOS */ |
| 890 |
NEXT(); |
| 891 |
return top; |
| 892 |
break; |
| 893 |
case SEND: |
| 894 |
ARCV('$', 1); /* EOL */ |
| 895 |
ARCV('$', 0); /* or EOS */ |
| 896 |
NEXT(); |
| 897 |
return top; |
| 898 |
break; |
| 899 |
case '<': |
| 900 |
wordchrs(v); |
| 901 |
s = newstate(v->nfa); |
| 902 |
NOERRN(); |
| 903 |
nonword(v, BEHIND, lp, s); |
| 904 |
word(v, AHEAD, s, rp); |
| 905 |
NEXT(); |
| 906 |
return top; |
| 907 |
break; |
| 908 |
case '>': |
| 909 |
wordchrs(v); |
| 910 |
s = newstate(v->nfa); |
| 911 |
NOERRN(); |
| 912 |
word(v, BEHIND, lp, s); |
| 913 |
nonword(v, AHEAD, s, rp); |
| 914 |
NEXT(); |
| 915 |
return top; |
| 916 |
break; |
| 917 |
case WBDRY: |
| 918 |
wordchrs(v); |
| 919 |
s = newstate(v->nfa); |
| 920 |
NOERRN(); |
| 921 |
nonword(v, BEHIND, lp, s); |
| 922 |
word(v, AHEAD, s, rp); |
| 923 |
s = newstate(v->nfa); |
| 924 |
NOERRN(); |
| 925 |
word(v, BEHIND, lp, s); |
| 926 |
nonword(v, AHEAD, s, rp); |
| 927 |
NEXT(); |
| 928 |
return top; |
| 929 |
break; |
| 930 |
case NWBDRY: |
| 931 |
wordchrs(v); |
| 932 |
s = newstate(v->nfa); |
| 933 |
NOERRN(); |
| 934 |
word(v, BEHIND, lp, s); |
| 935 |
word(v, AHEAD, s, rp); |
| 936 |
s = newstate(v->nfa); |
| 937 |
NOERRN(); |
| 938 |
nonword(v, BEHIND, lp, s); |
| 939 |
nonword(v, AHEAD, s, rp); |
| 940 |
NEXT(); |
| 941 |
return top; |
| 942 |
break; |
| 943 |
case LACON: /* lookaround constraint */ |
| 944 |
latype = v->nextvalue; |
| 945 |
NEXT(); |
| 946 |
s = newstate(v->nfa); |
| 947 |
s2 = newstate(v->nfa); |
| 948 |
NOERRN(); |
| 949 |
t = parse(v, ')', LACON, s, s2); |
| 950 |
freesubre(v, t); /* internal structure irrelevant */ |
| 951 |
NOERRN(); |
| 952 |
assert(SEE(')')); |
| 953 |
NEXT(); |
| 954 |
processlacon(v, s, s2, latype, lp, rp); |
| 955 |
return top; |
| 956 |
break; |
| 957 |
/* then errors, to get them out of the way */ |
| 958 |
case '*': |
| 959 |
case '+': |
| 960 |
case '?': |
| 961 |
case '{': |
| 962 |
ERR(REG_BADRPT); |
| 963 |
return top; |
| 964 |
break; |
| 965 |
default: |
| 966 |
ERR(REG_ASSERT); |
| 967 |
return top; |
| 968 |
break; |
| 969 |
/* then plain characters, and minor variants on that theme */ |
| 970 |
case ')': /* unbalanced paren */ |
| 971 |
if ((v->cflags & REG_ADVANCED) != REG_EXTENDED) |
| 972 |
{ |
| 973 |
ERR(REG_EPAREN); |
| 974 |
return top; |
| 975 |
} |
| 976 |
/* legal in EREs due to specification botch */ |
| 977 |
NOTE(REG_UPBOTCH); |
| 978 |
/* fall through into case PLAIN */ |
| 979 |
/* FALLTHROUGH */ |
| 980 |
case PLAIN: |
| 981 |
onechr(v, v->nextvalue, lp, rp); |
| 982 |
okcolors(v->nfa, v->cm); |
| 983 |
NOERRN(); |
| 984 |
NEXT(); |
| 985 |
break; |
| 986 |
case '[': |
| 987 |
if (v->nextvalue == 1) |
| 988 |
bracket(v, lp, rp); |
| 989 |
else |
| 990 |
cbracket(v, lp, rp); |
| 991 |
assert(SEE(']') || ISERR()); |
| 992 |
NEXT(); |
| 993 |
break; |
| 994 |
case CCLASSS: |
| 995 |
charclass(v, (enum char_classes) v->nextvalue, lp, rp); |
| 996 |
okcolors(v->nfa, v->cm); |
| 997 |
NEXT(); |
| 998 |
break; |
| 999 |
case CCLASSC: |
| 1000 |
charclasscomplement(v, (enum char_classes) v->nextvalue, lp, rp); |
| 1001 |
/* charclasscomplement() did okcolors() internally */ |
| 1002 |
NEXT(); |
| 1003 |
break; |
| 1004 |
case '.': |
| 1005 |
rainbow(v->nfa, v->cm, PLAIN, |
| 1006 |
(v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS, |
| 1007 |
lp, rp); |
| 1008 |
NEXT(); |
| 1009 |
break; |
| 1010 |
/* and finally the ugly stuff */ |
| 1011 |
case '(': /* value flags as capturing or non */ |
| 1012 |
cap = (type == LACON) ? 0 : v->nextvalue; |
| 1013 |
if (cap) |
| 1014 |
{ |
| 1015 |
v->nsubexp++; |
| 1016 |
subno = v->nsubexp; |
| 1017 |
if ((size_t) subno >= v->nsubs) |
| 1018 |
moresubs(v, subno); |
| 1019 |
} |
| 1020 |
else |
| 1021 |
atomtype = PLAIN; /* something that's not '(' */ |
| 1022 |
NEXT(); |
| 1023 |
|
| 1024 |
/* |
| 1025 |
* Make separate endpoint states to keep this sub-NFA distinct |
| 1026 |
* from what surrounds it. We need to be sure that when we |
| 1027 |
* duplicate the sub-NFA for a backref, we get the right |
| 1028 |
* states/arcs and no others. In particular, letting a backref |
| 1029 |
* duplicate the sub-NFA from lp to rp would be quite wrong, |
| 1030 |
* because we may add quantification superstructure around this |
| 1031 |
* atom below. (Perhaps we could skip the extra states for |
| 1032 |
* non-capturing parens, but it seems not worth the trouble.) |
| 1033 |
*/ |
| 1034 |
s = newstate(v->nfa); |
| 1035 |
s2 = newstate(v->nfa); |
| 1036 |
NOERRN(); |
| 1037 |
/* We may not need these arcs, but keep things connected for now */ |
| 1038 |
EMPTYARC(lp, s); |
| 1039 |
EMPTYARC(s2, rp); |
| 1040 |
NOERRN(); |
| 1041 |
atom = parse(v, ')', type, s, s2); |
| 1042 |
assert(SEE(')') || ISERR()); |
| 1043 |
NEXT(); |
| 1044 |
NOERRN(); |
| 1045 |
if (cap) |
| 1046 |
{ |
| 1047 |
if (atom->capno == 0) |
| 1048 |
{ |
| 1049 |
/* normal case: just mark the atom as capturing */ |
| 1050 |
atom->flags |= CAP; |
| 1051 |
atom->capno = subno; |
| 1052 |
} |
| 1053 |
else |
| 1054 |
{ |
| 1055 |
/* generate no-op wrapper node to handle "((x))" */ |
| 1056 |
t = subre(v, '(', atom->flags | CAP, s, s2); |
| 1057 |
NOERRN(); |
| 1058 |
t->capno = subno; |
| 1059 |
t->child = atom; |
| 1060 |
atom = t; |
| 1061 |
} |
| 1062 |
assert(v->subs[subno] == NULL); |
| 1063 |
v->subs[subno] = atom; |
| 1064 |
} |
| 1065 |
/* postpone everything else pending possible {0} */ |
| 1066 |
break; |
| 1067 |
case BACKREF: /* the Feature From The Black Lagoon */ |
| 1068 |
INSIST(type != LACON, REG_ESUBREG); |
| 1069 |
subno = v->nextvalue; |
| 1070 |
assert(subno > 0); |
| 1071 |
INSIST(subno < v->nsubs, REG_ESUBREG); |
| 1072 |
NOERRN(); |
| 1073 |
INSIST(v->subs[subno] != NULL, REG_ESUBREG); |
| 1074 |
NOERRN(); |
| 1075 |
atom = subre(v, 'b', BACKR, lp, rp); |
| 1076 |
NOERRN(); |
| 1077 |
atom->backno = subno; |
| 1078 |
v->subs[subno]->flags |= BRUSE; |
| 1079 |
EMPTYARC(lp, rp); /* temporarily, so there's something */ |
| 1080 |
NEXT(); |
| 1081 |
break; |
| 1082 |
} |
| 1083 |
|
| 1084 |
/* ...and an atom may be followed by a quantifier */ |
| 1085 |
switch (v->nexttype) |
| 1086 |
{ |
| 1087 |
case '*': |
| 1088 |
m = 0; |
| 1089 |
n = DUPINF; |
| 1090 |
qprefer = (v->nextvalue) ? LONGER : SHORTER; |
| 1091 |
NEXT(); |
| 1092 |
break; |
| 1093 |
case '+': |
| 1094 |
m = 1; |
| 1095 |
n = DUPINF; |
| 1096 |
qprefer = (v->nextvalue) ? LONGER : SHORTER; |
| 1097 |
NEXT(); |
| 1098 |
break; |
| 1099 |
case '?': |
| 1100 |
m = 0; |
| 1101 |
n = 1; |
| 1102 |
qprefer = (v->nextvalue) ? LONGER : SHORTER; |
| 1103 |
NEXT(); |
| 1104 |
break; |
| 1105 |
case '{': |
| 1106 |
NEXT(); |
| 1107 |
m = scannum(v); |
| 1108 |
if (EAT(',')) |
| 1109 |
{ |
| 1110 |
if (SEE(DIGIT)) |
| 1111 |
n = scannum(v); |
| 1112 |
else |
| 1113 |
n = DUPINF; |
| 1114 |
if (m > n) |
| 1115 |
{ |
| 1116 |
ERR(REG_BADBR); |
| 1117 |
return top; |
| 1118 |
} |
| 1119 |
/* {m,n} exercises preference, even if it's {m,m} */ |
| 1120 |
qprefer = (v->nextvalue) ? LONGER : SHORTER; |
| 1121 |
} |
| 1122 |
else |
| 1123 |
{ |
| 1124 |
n = m; |
| 1125 |
/* {m} passes operand's preference through */ |
| 1126 |
qprefer = 0; |
| 1127 |
} |
| 1128 |
if (!SEE('}')) |
| 1129 |
{ /* catches errors too */ |
| 1130 |
ERR(REG_BADBR); |
| 1131 |
return top; |
| 1132 |
} |
| 1133 |
NEXT(); |
| 1134 |
break; |
| 1135 |
default: /* no quantifier */ |
| 1136 |
m = n = 1; |
| 1137 |
qprefer = 0; |
| 1138 |
break; |
| 1139 |
} |
| 1140 |
|
| 1141 |
/* annoying special case: {0} or {0,0} cancels everything */ |
| 1142 |
if (m == 0 && n == 0) |
| 1143 |
{ |
| 1144 |
/* |
| 1145 |
* If we had capturing subexpression(s) within the atom, we don't want |
| 1146 |
* to destroy them, because it's legal (if useless) to back-ref them |
| 1147 |
* later. Hence, just unlink the atom from lp/rp and then ignore it. |
| 1148 |
*/ |
| 1149 |
if (atom != NULL && (atom->flags & CAP)) |
| 1150 |
{ |
| 1151 |
delsub(v->nfa, lp, atom->begin); |
| 1152 |
delsub(v->nfa, atom->end, rp); |
| 1153 |
} |
| 1154 |
else |
| 1155 |
{ |
| 1156 |
/* Otherwise, we can clean up any subre infrastructure we made */ |
| 1157 |
if (atom != NULL) |
| 1158 |
freesubre(v, atom); |
| 1159 |
delsub(v->nfa, lp, rp); |
| 1160 |
} |
| 1161 |
EMPTYARC(lp, rp); |
| 1162 |
return top; |
| 1163 |
} |
| 1164 |
|
| 1165 |
/* if not a messy case, avoid hard part */ |
| 1166 |
assert(!MESSY(top->flags)); |
| 1167 |
f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0); |
| 1168 |
if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f))) |
| 1169 |
{ |
| 1170 |
if (!(m == 1 && n == 1)) |
| 1171 |
repeat(v, lp, rp, m, n); |
| 1172 |
if (atom != NULL) |
| 1173 |
freesubre(v, atom); |
| 1174 |
top->flags = f; |
| 1175 |
return top; |
| 1176 |
} |
| 1177 |
|
| 1178 |
/* |
| 1179 |
* hard part: something messy |
| 1180 |
* |
| 1181 |
* That is, capturing parens, back reference, short/long clash, or an atom |
| 1182 |
* with substructure containing one of those. |
| 1183 |
*/ |
| 1184 |
|
| 1185 |
/* now we'll need a subre for the contents even if they're boring */ |
| 1186 |
if (atom == NULL) |
| 1187 |
{ |
| 1188 |
atom = subre(v, '=', 0, lp, rp); |
| 1189 |
NOERRN(); |
| 1190 |
} |
| 1191 |
|
| 1192 |
/* |
| 1193 |
* For what follows, we need the atom to have its own begin/end states |
| 1194 |
* that are distinct from lp/rp, so that we can wrap iteration structure |
| 1195 |
* around it. The parenthesized-atom case above already made suitable |
| 1196 |
* states (and we don't want to modify a capturing subre, since it's |
| 1197 |
* already recorded in v->subs[]). Otherwise, we need more states. |
| 1198 |
*/ |
| 1199 |
if (atom->begin == lp || atom->end == rp) |
| 1200 |
{ |
| 1201 |
s = newstate(v->nfa); |
| 1202 |
s2 = newstate(v->nfa); |
| 1203 |
NOERRN(); |
| 1204 |
moveouts(v->nfa, lp, s); |
| 1205 |
moveins(v->nfa, rp, s2); |
| 1206 |
atom->begin = s; |
| 1207 |
atom->end = s2; |
| 1208 |
} |
| 1209 |
else |
| 1210 |
{ |
| 1211 |
/* The atom's OK, but we must temporarily disconnect it from lp/rp */ |
| 1212 |
/* (this removes the EMPTY arcs we made above) */ |
| 1213 |
delsub(v->nfa, lp, atom->begin); |
| 1214 |
delsub(v->nfa, atom->end, rp); |
| 1215 |
} |
| 1216 |
|
| 1217 |
/*---------- |
| 1218 |
* Prepare a general-purpose state skeleton. |
| 1219 |
* |
| 1220 |
* In the no-backrefs case, we want this: |
| 1221 |
* |
| 1222 |
* [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp] |
| 1223 |
* |
| 1224 |
* where prefix is some repetitions of atom, and "rest" is the remainder |
| 1225 |
* of the branch. In the general case we need: |
| 1226 |
* |
| 1227 |
* [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp] |
| 1228 |
* |
| 1229 |
* where the iterator wraps around the atom. |
| 1230 |
* |
| 1231 |
* We make the s state here for both cases; s2 is made below if needed |
| 1232 |
*---------- |
| 1233 |
*/ |
| 1234 |
s = newstate(v->nfa); /* set up starting state */ |
| 1235 |
NOERRN(); |
| 1236 |
EMPTYARC(lp, s); |
| 1237 |
NOERRN(); |
| 1238 |
|
| 1239 |
/* break remaining subRE into x{...} and what follows */ |
| 1240 |
t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp); |
| 1241 |
NOERRN(); |
| 1242 |
t->child = atom; |
| 1243 |
atomp = &t->child; |
| 1244 |
|
| 1245 |
/* |
| 1246 |
* Here we should recurse to fill t->child->sibling ... but we must |
| 1247 |
* postpone that to the end. One reason is that t->child may be replaced |
| 1248 |
* below, and we don't want to worry about its sibling link. |
| 1249 |
*/ |
| 1250 |
|
| 1251 |
/* |
| 1252 |
* Convert top node to a concatenation of the prefix (top->child, covering |
| 1253 |
* whatever we parsed previously) and remaining (t). Note that the prefix |
| 1254 |
* could be empty, in which case this concatenation node is unnecessary. |
| 1255 |
* To keep things simple, we operate in a general way for now, and get rid |
| 1256 |
* of unnecessary subres below. |
| 1257 |
*/ |
| 1258 |
assert(top->op == '=' && top->child == NULL); |
| 1259 |
top->child = subre(v, '=', top->flags, top->begin, lp); |
| 1260 |
NOERRN(); |
| 1261 |
top->op = '.'; |
| 1262 |
top->child->sibling = t; |
| 1263 |
/* top->flags will get updated later */ |
| 1264 |
|
| 1265 |
/* if it's a backref, now is the time to replicate the subNFA */ |
| 1266 |
if (atomtype == BACKREF) |
| 1267 |
{ |
| 1268 |
assert(atom->begin->nouts == 1); /* just the EMPTY */ |
| 1269 |
delsub(v->nfa, atom->begin, atom->end); |
| 1270 |
assert(v->subs[subno] != NULL); |
| 1271 |
|
| 1272 |
/* |
| 1273 |
* And here's why the recursion got postponed: it must wait until the |
| 1274 |
* skeleton is filled in, because it may hit a backref that wants to |
| 1275 |
* copy the filled-in skeleton. |
| 1276 |
*/ |
| 1277 |
dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end, |
| 1278 |
atom->begin, atom->end); |
| 1279 |
NOERRN(); |
| 1280 |
|
| 1281 |
/* The backref node's NFA should not enforce any constraints */ |
| 1282 |
removeconstraints(v->nfa, atom->begin, atom->end); |
| 1283 |
NOERRN(); |
| 1284 |
} |
| 1285 |
|
| 1286 |
/* |
| 1287 |
* It's quantifier time. If the atom is just a backref, we'll let it deal |
| 1288 |
* with quantifiers internally. |
| 1289 |
*/ |
| 1290 |
if (atomtype == BACKREF) |
| 1291 |
{ |
| 1292 |
/* special case: backrefs have internal quantifiers */ |
| 1293 |
EMPTYARC(s, atom->begin); /* empty prefix */ |
| 1294 |
/* just stuff everything into atom */ |
| 1295 |
repeat(v, atom->begin, atom->end, m, n); |
| 1296 |
atom->min = (short) m; |
| 1297 |
atom->max = (short) n; |
| 1298 |
atom->flags |= COMBINE(qprefer, atom->flags); |
| 1299 |
/* rest of branch can be strung starting from atom->end */ |
| 1300 |
s2 = atom->end; |
| 1301 |
} |
| 1302 |
else if (m == 1 && n == 1 && |
| 1303 |
(qprefer == 0 || |
| 1304 |
(atom->flags & (LONGER | SHORTER | MIXED)) == 0 || |
| 1305 |
qprefer == (atom->flags & (LONGER | SHORTER | MIXED)))) |
| 1306 |
{ |
| 1307 |
/* no/vacuous quantifier: done */ |
| 1308 |
EMPTYARC(s, atom->begin); /* empty prefix */ |
| 1309 |
/* rest of branch can be strung starting from atom->end */ |
| 1310 |
s2 = atom->end; |
| 1311 |
} |
| 1312 |
else if (!(atom->flags & (CAP | BACKR))) |
| 1313 |
{ |
| 1314 |
/* |
| 1315 |
* If there's no captures nor backrefs in the atom being repeated, we |
| 1316 |
* don't really care where the submatches of the iteration are, so we |
| 1317 |
* don't need an iteration node. Make a plain DFA node instead. |
| 1318 |
*/ |
| 1319 |
EMPTYARC(s, atom->begin); /* empty prefix */ |
| 1320 |
repeat(v, atom->begin, atom->end, m, n); |
| 1321 |
f = COMBINE(qprefer, atom->flags); |
| 1322 |
t = subre(v, '=', f, atom->begin, atom->end); |
| 1323 |
NOERRN(); |
| 1324 |
freesubre(v, atom); |
| 1325 |
*atomp = t; |
| 1326 |
/* rest of branch can be strung starting from t->end */ |
| 1327 |
s2 = t->end; |
| 1328 |
} |
| 1329 |
else if (m > 0 && !(atom->flags & BACKR)) |
| 1330 |
{ |
| 1331 |
/* |
| 1332 |
* If there's no backrefs involved, we can turn x{m,n} into |
| 1333 |
* x{m-1,n-1}x, with capturing parens in only the second x. This is |
| 1334 |
* valid because we only care about capturing matches from the final |
| 1335 |
* iteration of the quantifier. It's a win because we can implement |
| 1336 |
* the backref-free left side as a plain DFA node, since we don't |
| 1337 |
* really care where its submatches are. |
| 1338 |
*/ |
| 1339 |
dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin); |
| 1340 |
assert(m >= 1 && m != DUPINF && n >= 1); |
| 1341 |
repeat(v, s, atom->begin, m - 1, (n == DUPINF) ? n : n - 1); |
| 1342 |
f = COMBINE(qprefer, atom->flags); |
| 1343 |
t = subre(v, '.', f, s, atom->end); /* prefix and atom */ |
| 1344 |
NOERRN(); |
| 1345 |
t->child = subre(v, '=', PREF(f), s, atom->begin); |
| 1346 |
NOERRN(); |
| 1347 |
t->child->sibling = atom; |
| 1348 |
*atomp = t; |
| 1349 |
/* rest of branch can be strung starting from atom->end */ |
| 1350 |
s2 = atom->end; |
| 1351 |
} |
| 1352 |
else |
| 1353 |
{ |
| 1354 |
/* general case: need an iteration node */ |
| 1355 |
s2 = newstate(v->nfa); |
| 1356 |
NOERRN(); |
| 1357 |
moveouts(v->nfa, atom->end, s2); |
| 1358 |
NOERRN(); |
| 1359 |
dupnfa(v->nfa, atom->begin, atom->end, s, s2); |
| 1360 |
repeat(v, s, s2, m, n); |
| 1361 |
f = COMBINE(qprefer, atom->flags); |
| 1362 |
t = subre(v, '*', f, s, s2); |
| 1363 |
NOERRN(); |
| 1364 |
t->min = (short) m; |
| 1365 |
t->max = (short) n; |
| 1366 |
t->child = atom; |
| 1367 |
*atomp = t; |
| 1368 |
/* rest of branch is to be strung from iteration's end state */ |
| 1369 |
} |
| 1370 |
|
| 1371 |
/* and finally, look after that postponed recursion */ |
| 1372 |
t = top->child->sibling; |
| 1373 |
if (!(SEE('|') || SEE(stopper) || SEE(EOS))) |
| 1374 |
{ |
| 1375 |
/* parse all the rest of the branch, and insert in t->child->sibling */ |
| 1376 |
t->child->sibling = parsebranch(v, stopper, type, s2, rp, 1); |
| 1377 |
NOERRN(); |
| 1378 |
assert(SEE('|') || SEE(stopper) || SEE(EOS)); |
| 1379 |
|
| 1380 |
/* here's the promised update of the flags */ |
| 1381 |
t->flags |= COMBINE(t->flags, t->child->sibling->flags); |
| 1382 |
top->flags |= COMBINE(top->flags, t->flags); |
| 1383 |
|
| 1384 |
/* neither t nor top could be directly marked for capture as yet */ |
| 1385 |
assert(t->capno == 0); |
| 1386 |
assert(top->capno == 0); |
| 1387 |
|
| 1388 |
/* |
| 1389 |
* At this point both top and t are concatenation (op == '.') subres, |
| 1390 |
* and we have top->child = prefix of branch, top->child->sibling = t, |
| 1391 |
* t->child = messy atom (with quantification superstructure if |
| 1392 |
* needed), t->child->sibling = rest of branch. |
| 1393 |
* |
| 1394 |
* If the messy atom was the first thing in the branch, then |
| 1395 |
* top->child is vacuous and we can get rid of one level of |
| 1396 |
* concatenation. |
| 1397 |
*/ |
| 1398 |
assert(top->child->op == '='); |
| 1399 |
if (top->child->begin == top->child->end) |
| 1400 |
{ |
| 1401 |
assert(!MESSY(top->child->flags)); |
| 1402 |
freesubre(v, top->child); |
| 1403 |
top->child = t->child; |
| 1404 |
freesrnode(v, t); |
| 1405 |
} |
| 1406 |
|
| 1407 |
/* |
| 1408 |
* Otherwise, it's possible that t->child is not messy in itself, but |
| 1409 |
* we considered it messy because its greediness conflicts with what |
| 1410 |
* preceded it. Then it could be that the combination of t->child and |
| 1411 |
* the rest of the branch is also not messy, in which case we can get |
| 1412 |
* rid of the child concatenation by merging t->child and the rest of |
| 1413 |
* the branch into one plain DFA node. |
| 1414 |
*/ |
| 1415 |
else if (t->child->op == '=' && |
| 1416 |
t->child->sibling->op == '=' && |
| 1417 |
!MESSY(UP(t->child->flags | t->child->sibling->flags))) |
| 1418 |
{ |
| 1419 |
t->op = '='; |
| 1420 |
t->flags = COMBINE(t->child->flags, t->child->sibling->flags); |
| 1421 |
freesubreandsiblings(v, t->child); |
| 1422 |
t->child = NULL; |
| 1423 |
} |
| 1424 |
} |
| 1425 |
else |
| 1426 |
{ |
| 1427 |
/* |
| 1428 |
* There's nothing left in the branch, so we don't need the second |
| 1429 |
* concatenation node 't'. Just link s2 straight to rp. |
| 1430 |
*/ |
| 1431 |
EMPTYARC(s2, rp); |
| 1432 |
top->child->sibling = t->child; |
| 1433 |
top->flags |= COMBINE(top->flags, top->child->sibling->flags); |
| 1434 |
freesrnode(v, t); |
| 1435 |
|
| 1436 |
/* |
| 1437 |
* Again, it could be that top->child is vacuous (if the messy atom |
| 1438 |
* was in fact the only thing in the branch). In that case we need no |
| 1439 |
* concatenation at all; just replace top with top->child->sibling. |
| 1440 |
*/ |
| 1441 |
assert(top->child->op == '='); |
| 1442 |
if (top->child->begin == top->child->end) |
| 1443 |
{ |
| 1444 |
assert(!MESSY(top->child->flags)); |
| 1445 |
t = top->child->sibling; |
| 1446 |
top->child->sibling = NULL; |
| 1447 |
freesubre(v, top); |
| 1448 |
top = t; |
| 1449 |
} |
| 1450 |
} |
| 1451 |
|
| 1452 |
return top; |
| 1453 |
} |
| 1454 |
|
| 1455 |
/* |
| 1456 |
* nonword - generate arcs for non-word-character ahead or behind |
| 1457 |
*/ |
| 1458 |
static void |
| 1459 |
nonword(struct vars *v, |
| 1460 |
int dir, /* AHEAD or BEHIND */ |
| 1461 |
struct state *lp, |
| 1462 |
struct state *rp) |
| 1463 |
{ |
| 1464 |
int anchor = (dir == AHEAD) ? '$' : '^'; |
| 1465 |
|
| 1466 |
assert(dir == AHEAD || dir == BEHIND); |
| 1467 |
newarc(v->nfa, anchor, 1, lp, rp); |
| 1468 |
newarc(v->nfa, anchor, 0, lp, rp); |
| 1469 |
colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp); |
| 1470 |
/* (no need for special attention to \n) */ |
| 1471 |
} |
| 1472 |
|
| 1473 |
/* |
| 1474 |
* word - generate arcs for word character ahead or behind |
| 1475 |
*/ |
| 1476 |
static void |
| 1477 |
word(struct vars *v, |
| 1478 |
int dir, /* AHEAD or BEHIND */ |
| 1479 |
struct state *lp, |
| 1480 |
struct state *rp) |
| 1481 |
{ |
| 1482 |
assert(dir == AHEAD || dir == BEHIND); |
| 1483 |
cloneouts(v->nfa, v->wordchrs, lp, rp, dir); |
| 1484 |
/* (no need for special attention to \n) */ |
| 1485 |
} |
| 1486 |
|
| 1487 |
/* |
| 1488 |
* charclass - generate arcs for a character class |
| 1489 |
* |
| 1490 |
* This is used for both atoms (\w and sibling escapes) and for elements |
| 1491 |
* of bracket expressions. The caller is responsible for calling okcolors() |
| 1492 |
* at the end of processing the atom or bracket. |
| 1493 |
*/ |
| 1494 |
static void |
| 1495 |
charclass(struct vars *v, |
| 1496 |
enum char_classes cls, |
| 1497 |
struct state *lp, |
| 1498 |
struct state *rp) |
| 1499 |
{ |
| 1500 |
struct cvec *cv; |
| 1501 |
|
| 1502 |
/* obtain possibly-cached cvec for char class */ |
| 1503 |
NOTE(REG_ULOCALE); |
| 1504 |
cv = cclasscvec(v, cls, (v->cflags & REG_ICASE)); |
| 1505 |
NOERR(); |
| 1506 |
|
| 1507 |
/* build the arcs; this may cause color splitting */ |
| 1508 |
subcolorcvec(v, cv, lp, rp); |
| 1509 |
} |
| 1510 |
|
| 1511 |
/* |
| 1512 |
* charclasscomplement - generate arcs for a complemented character class |
| 1513 |
* |
| 1514 |
* This is used for both atoms (\W and sibling escapes) and for elements |
| 1515 |
* of bracket expressions. In bracket expressions, it is the caller's |
| 1516 |
* responsibility that there not be any open subcolors when this is called. |
| 1517 |
*/ |
| 1518 |
static void |
| 1519 |
charclasscomplement(struct vars *v, |
| 1520 |
enum char_classes cls, |
| 1521 |
struct state *lp, |
| 1522 |
struct state *rp) |
| 1523 |
{ |
| 1524 |
struct state *cstate; |
| 1525 |
struct cvec *cv; |
| 1526 |
|
| 1527 |
/* make dummy state to hang temporary arcs on */ |
| 1528 |
cstate = newstate(v->nfa); |
| 1529 |
NOERR(); |
| 1530 |
|
| 1531 |
/* obtain possibly-cached cvec for char class */ |
| 1532 |
NOTE(REG_ULOCALE); |
| 1533 |
cv = cclasscvec(v, cls, (v->cflags & REG_ICASE)); |
| 1534 |
NOERR(); |
| 1535 |
|
| 1536 |
/* build arcs for char class; this may cause color splitting */ |
| 1537 |
subcolorcvec(v, cv, cstate, cstate); |
| 1538 |
NOERR(); |
| 1539 |
|
| 1540 |
/* clean up any subcolors in the arc set */ |
| 1541 |
okcolors(v->nfa, v->cm); |
| 1542 |
NOERR(); |
| 1543 |
|
| 1544 |
/* now build output arcs for the complement of the char class */ |
| 1545 |
colorcomplement(v->nfa, v->cm, PLAIN, cstate, lp, rp); |
| 1546 |
NOERR(); |
| 1547 |
|
| 1548 |
/* clean up dummy state */ |
| 1549 |
dropstate(v->nfa, cstate); |
| 1550 |
} |
| 1551 |
|
| 1552 |
/* |
| 1553 |
* scannum - scan a number |
| 1554 |
*/ |
| 1555 |
static int /* value, <= DUPMAX */ |
| 1556 |
scannum(struct vars *v) |
| 1557 |
{ |
| 1558 |
int n = 0; |
| 1559 |
|
| 1560 |
while (SEE(DIGIT) && n < DUPMAX) |
| 1561 |
{ |
| 1562 |
n = n * 10 + v->nextvalue; |
| 1563 |
NEXT(); |
| 1564 |
} |
| 1565 |
if (SEE(DIGIT) || n > DUPMAX) |
| 1566 |
{ |
| 1567 |
ERR(REG_BADBR); |
| 1568 |
return 0; |
| 1569 |
} |
| 1570 |
return n; |
| 1571 |
} |
| 1572 |
|
| 1573 |
/* |
| 1574 |
* repeat - replicate subNFA for quantifiers |
| 1575 |
* |
| 1576 |
* The sub-NFA strung from lp to rp is modified to represent m to n |
| 1577 |
* repetitions of its initial contents. |
| 1578 |
* |
| 1579 |
* The duplication sequences used here are chosen carefully so that any |
| 1580 |
* pointers starting out pointing into the subexpression end up pointing into |
| 1581 |
* the last occurrence. (Note that it may not be strung between the same |
| 1582 |
* left and right end states, however!) This used to be important for the |
| 1583 |
* subRE tree, although the important bits are now handled by the in-line |
| 1584 |
* code in parse(), and when this is called, it doesn't matter any more. |
| 1585 |
*/ |
| 1586 |
static void |
| 1587 |
repeat(struct vars *v, |
| 1588 |
struct state *lp, |
| 1589 |
struct state *rp, |
| 1590 |
int m, |
| 1591 |
int n) |
| 1592 |
{ |
| 1593 |
#define SOME 2 |
| 1594 |
#define INF 3 |
| 1595 |
#define PAIR(x, y) ((x)*4 + (y)) |
| 1596 |
#define REDUCE(x) ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) ) |
| 1597 |
const int rm = REDUCE(m); |
| 1598 |
const int rn = REDUCE(n); |
| 1599 |
struct state *s; |
| 1600 |
struct state *s2; |
| 1601 |
|
| 1602 |
switch (PAIR(rm, rn)) |
| 1603 |
{ |
| 1604 |
case PAIR(0, 0): /* empty string */ |
| 1605 |
delsub(v->nfa, lp, rp); |
| 1606 |
EMPTYARC(lp, rp); |
| 1607 |
break; |
| 1608 |
case PAIR(0, 1): /* do as x| */ |
| 1609 |
EMPTYARC(lp, rp); |
| 1610 |
break; |
| 1611 |
case PAIR(0, SOME): /* do as x{1,n}| */ |
| 1612 |
repeat(v, lp, rp, 1, n); |
| 1613 |
NOERR(); |
| 1614 |
EMPTYARC(lp, rp); |
| 1615 |
break; |
| 1616 |
case PAIR(0, INF): /* loop x around */ |
| 1617 |
s = newstate(v->nfa); |
| 1618 |
NOERR(); |
| 1619 |
moveouts(v->nfa, lp, s); |
| 1620 |
moveins(v->nfa, rp, s); |
| 1621 |
EMPTYARC(lp, s); |
| 1622 |
EMPTYARC(s, rp); |
| 1623 |
break; |
| 1624 |
case PAIR(1, 1): /* no action required */ |
| 1625 |
break; |
| 1626 |
case PAIR(1, SOME): /* do as x{0,n-1}x = (x{1,n-1}|)x */ |
| 1627 |
s = newstate(v->nfa); |
| 1628 |
NOERR(); |
| 1629 |
moveouts(v->nfa, lp, s); |
| 1630 |
dupnfa(v->nfa, s, rp, lp, s); |
| 1631 |
NOERR(); |
| 1632 |
repeat(v, lp, s, 1, n - 1); |
| 1633 |
NOERR(); |
| 1634 |
EMPTYARC(lp, s); |
| 1635 |
break; |
| 1636 |
case PAIR(1, INF): /* add loopback arc */ |
| 1637 |
s = newstate(v->nfa); |
| 1638 |
s2 = newstate(v->nfa); |
| 1639 |
NOERR(); |
| 1640 |
moveouts(v->nfa, lp, s); |
| 1641 |
moveins(v->nfa, rp, s2); |
| 1642 |
EMPTYARC(lp, s); |
| 1643 |
EMPTYARC(s2, rp); |
| 1644 |
EMPTYARC(s2, s); |
| 1645 |
break; |
| 1646 |
case PAIR(SOME, SOME): /* do as x{m-1,n-1}x */ |
| 1647 |
s = newstate(v->nfa); |
| 1648 |
NOERR(); |
| 1649 |
moveouts(v->nfa, lp, s); |
| 1650 |
dupnfa(v->nfa, s, rp, lp, s); |
| 1651 |
NOERR(); |
| 1652 |
repeat(v, lp, s, m - 1, n - 1); |
| 1653 |
break; |
| 1654 |
case PAIR(SOME, INF): /* do as x{m-1,}x */ |
| 1655 |
s = newstate(v->nfa); |
| 1656 |
NOERR(); |
| 1657 |
moveouts(v->nfa, lp, s); |
| 1658 |
dupnfa(v->nfa, s, rp, lp, s); |
| 1659 |
NOERR(); |
| 1660 |
repeat(v, lp, s, m - 1, n); |
| 1661 |
break; |
| 1662 |
default: |
| 1663 |
ERR(REG_ASSERT); |
| 1664 |
break; |
| 1665 |
} |
| 1666 |
} |
| 1667 |
|
| 1668 |
/* |
| 1669 |
* bracket - handle non-complemented bracket expression |
| 1670 |
* |
| 1671 |
* Also called from cbracket for complemented bracket expressions. |
| 1672 |
*/ |
| 1673 |
static void |
| 1674 |
bracket(struct vars *v, |
| 1675 |
struct state *lp, |
| 1676 |
struct state *rp) |
| 1677 |
{ |
| 1678 |
/* |
| 1679 |
* We can't process complemented char classes (e.g. \W) immediately while |
| 1680 |
* scanning the bracket expression, else color bookkeeping gets confused. |
| 1681 |
* Instead, remember whether we saw any in have_cclassc[], and process |
| 1682 |
* them at the end. |
| 1683 |
*/ |
| 1684 |
bool have_cclassc[NUM_CCLASSES]; |
| 1685 |
bool any_cclassc; |
| 1686 |
int i; |
| 1687 |
|
| 1688 |
memset(have_cclassc, false, sizeof(have_cclassc)); |
| 1689 |
|
| 1690 |
assert(SEE('[')); |
| 1691 |
NEXT(); |
| 1692 |
while (!SEE(']') && !SEE(EOS)) |
| 1693 |
brackpart(v, lp, rp, have_cclassc); |
| 1694 |
assert(SEE(']') || ISERR()); |
| 1695 |
|
| 1696 |
/* close up open subcolors from the positive bracket elements */ |
| 1697 |
okcolors(v->nfa, v->cm); |
| 1698 |
NOERR(); |
| 1699 |
|
| 1700 |
/* now handle any complemented elements */ |
| 1701 |
any_cclassc = false; |
| 1702 |
for (i = 0; i < NUM_CCLASSES; i++) |
| 1703 |
{ |
| 1704 |
if (have_cclassc[i]) |
| 1705 |
{ |
| 1706 |
charclasscomplement(v, (enum char_classes) i, lp, rp); |
| 1707 |
NOERR(); |
| 1708 |
any_cclassc = true; |
| 1709 |
} |
| 1710 |
} |
| 1711 |
|
| 1712 |
/* |
| 1713 |
* If we had any complemented elements, see if we can optimize the bracket |
| 1714 |
* into a rainbow. Since a complemented element is the only way a WHITE |
| 1715 |
* arc could get into the result, there's no point in checking otherwise. |
| 1716 |
*/ |
| 1717 |
if (any_cclassc) |
| 1718 |
optimizebracket(v, lp, rp); |
| 1719 |
} |
| 1720 |
|
| 1721 |
/* |
| 1722 |
* cbracket - handle complemented bracket expression |
| 1723 |
* |
| 1724 |
* We do it by calling bracket() with dummy endpoints, and then complementing |
| 1725 |
* the result. The alternative would be to invoke rainbow(), and then delete |
| 1726 |
* arcs as the b.e. is seen... but that gets messy, and is really quite |
| 1727 |
* infeasible now that rainbow() just puts out one RAINBOW arc. |
| 1728 |
*/ |
| 1729 |
static void |
| 1730 |
cbracket(struct vars *v, |
| 1731 |
struct state *lp, |
| 1732 |
struct state *rp) |
| 1733 |
{ |
| 1734 |
struct state *left = newstate(v->nfa); |
| 1735 |
struct state *right = newstate(v->nfa); |
| 1736 |
|
| 1737 |
NOERR(); |
| 1738 |
bracket(v, left, right); |
| 1739 |
|
| 1740 |
/* in NLSTOP mode, ensure newline is not part of the result set */ |
| 1741 |
if (v->cflags & REG_NLSTOP) |
| 1742 |
newarc(v->nfa, PLAIN, v->nlcolor, left, right); |
| 1743 |
NOERR(); |
| 1744 |
|
| 1745 |
assert(lp->nouts == 0); /* all outarcs will be ours */ |
| 1746 |
|
| 1747 |
/* |
| 1748 |
* Easy part of complementing, and all there is to do since the MCCE code |
| 1749 |
* was removed. Note that the result of colorcomplement() cannot be a |
| 1750 |
* rainbow, since we don't allow empty brackets; so there's no point in |
| 1751 |
* calling optimizebracket() again. |
| 1752 |
*/ |
| 1753 |
colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp); |
| 1754 |
NOERR(); |
| 1755 |
dropstate(v->nfa, left); |
| 1756 |
assert(right->nins == 0); |
| 1757 |
freestate(v->nfa, right); |
| 1758 |
} |
| 1759 |
|
| 1760 |
/* |
| 1761 |
* brackpart - handle one item (or range) within a bracket expression |
| 1762 |
*/ |
| 1763 |
static void |
| 1764 |
brackpart(struct vars *v, |
| 1765 |
struct state *lp, |
| 1766 |
struct state *rp, |
| 1767 |
bool *have_cclassc) |
| 1768 |
{ |
| 1769 |
chr startc; |
| 1770 |
chr endc; |
| 1771 |
struct cvec *cv; |
| 1772 |
enum char_classes cls; |
| 1773 |
const chr *startp; |
| 1774 |
const chr *endp; |
| 1775 |
|
| 1776 |
/* parse something, get rid of special cases, take shortcuts */ |
| 1777 |
switch (v->nexttype) |
| 1778 |
{ |
| 1779 |
case RANGE: /* a-b-c or other botch */ |
| 1780 |
ERR(REG_ERANGE); |
| 1781 |
return; |
| 1782 |
break; |
| 1783 |
case PLAIN: |
| 1784 |
startc = v->nextvalue; |
| 1785 |
NEXT(); |
| 1786 |
/* shortcut for ordinary chr (not range) */ |
| 1787 |
if (!SEE(RANGE)) |
| 1788 |
{ |
| 1789 |
onechr(v, startc, lp, rp); |
| 1790 |
return; |
| 1791 |
} |
| 1792 |
NOERR(); |
| 1793 |
break; |
| 1794 |
case COLLEL: |
| 1795 |
startp = v->now; |
| 1796 |
endp = scanplain(v); |
| 1797 |
INSIST(startp < endp, REG_ECOLLATE); |
| 1798 |
NOERR(); |
| 1799 |
startc = element(v, startp, endp); |
| 1800 |
NOERR(); |
| 1801 |
break; |
| 1802 |
case ECLASS: |
| 1803 |
startp = v->now; |
| 1804 |
endp = scanplain(v); |
| 1805 |
INSIST(startp < endp, REG_ECOLLATE); |
| 1806 |
NOERR(); |
| 1807 |
startc = element(v, startp, endp); |
| 1808 |
NOERR(); |
| 1809 |
cv = eclass(v, startc, (v->cflags & REG_ICASE)); |
| 1810 |
NOERR(); |
| 1811 |
subcolorcvec(v, cv, lp, rp); |
| 1812 |
return; |
| 1813 |
break; |
| 1814 |
case CCLASS: |
| 1815 |
startp = v->now; |
| 1816 |
endp = scanplain(v); |
| 1817 |
INSIST(startp < endp, REG_ECTYPE); |
| 1818 |
NOERR(); |
| 1819 |
cls = lookupcclass(v, startp, endp); |
| 1820 |
NOERR(); |
| 1821 |
charclass(v, cls, lp, rp); |
| 1822 |
return; |
| 1823 |
break; |
| 1824 |
case CCLASSS: |
| 1825 |
charclass(v, (enum char_classes) v->nextvalue, lp, rp); |
| 1826 |
NEXT(); |
| 1827 |
return; |
| 1828 |
break; |
| 1829 |
case CCLASSC: |
| 1830 |
/* we cannot call charclasscomplement() immediately */ |
| 1831 |
have_cclassc[v->nextvalue] = true; |
| 1832 |
NEXT(); |
| 1833 |
return; |
| 1834 |
break; |
| 1835 |
default: |
| 1836 |
ERR(REG_ASSERT); |
| 1837 |
return; |
| 1838 |
break; |
| 1839 |
} |
| 1840 |
|
| 1841 |
if (SEE(RANGE)) |
| 1842 |
{ |
| 1843 |
NEXT(); |
| 1844 |
switch (v->nexttype) |
| 1845 |
{ |
| 1846 |
case PLAIN: |
| 1847 |
case RANGE: |
| 1848 |
endc = v->nextvalue; |
| 1849 |
NEXT(); |
| 1850 |
NOERR(); |
| 1851 |
break; |
| 1852 |
case COLLEL: |
| 1853 |
startp = v->now; |
| 1854 |
endp = scanplain(v); |
| 1855 |
INSIST(startp < endp, REG_ECOLLATE); |
| 1856 |
NOERR(); |
| 1857 |
endc = element(v, startp, endp); |
| 1858 |
NOERR(); |
| 1859 |
break; |
| 1860 |
default: |
| 1861 |
ERR(REG_ERANGE); |
| 1862 |
return; |
| 1863 |
break; |
| 1864 |
} |
| 1865 |
} |
| 1866 |
else |
| 1867 |
endc = startc; |
| 1868 |
|
| 1869 |
/* |
| 1870 |
* Ranges are unportable. Actually, standard C does guarantee that digits |
| 1871 |
* are contiguous, but making that an exception is just too complicated. |
| 1872 |
*/ |
| 1873 |
if (startc != endc) |
| 1874 |
NOTE(REG_UUNPORT); |
| 1875 |
cv = range(v, startc, endc, (v->cflags & REG_ICASE)); |
| 1876 |
NOERR(); |
| 1877 |
subcolorcvec(v, cv, lp, rp); |
| 1878 |
} |
| 1879 |
|
| 1880 |
/* |
| 1881 |
* scanplain - scan PLAIN contents of [. etc. |
| 1882 |
* |
| 1883 |
* Certain bits of trickery in regc_lex.c know that this code does not try |
| 1884 |
* to look past the final bracket of the [. etc. |
| 1885 |
*/ |
| 1886 |
static const chr * /* just after end of sequence */ |
| 1887 |
scanplain(struct vars *v) |
| 1888 |
{ |
| 1889 |
const chr *endp; |
| 1890 |
|
| 1891 |
assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS)); |
| 1892 |
NEXT(); |
| 1893 |
|
| 1894 |
endp = v->now; |
| 1895 |
while (SEE(PLAIN)) |
| 1896 |
{ |
| 1897 |
endp = v->now; |
| 1898 |
NEXT(); |
| 1899 |
} |
| 1900 |
|
| 1901 |
assert(SEE(END) || ISERR()); |
| 1902 |
NEXT(); |
| 1903 |
|
| 1904 |
return endp; |
| 1905 |
} |
| 1906 |
|
| 1907 |
/* |
| 1908 |
* onechr - fill in arcs for a plain character, and possible case complements |
| 1909 |
* This is mostly a shortcut for efficient handling of the common case. |
| 1910 |
*/ |
| 1911 |
static void |
| 1912 |
onechr(struct vars *v, |
| 1913 |
chr c, |
| 1914 |
struct state *lp, |
| 1915 |
struct state *rp) |
| 1916 |
{ |
| 1917 |
if (!(v->cflags & REG_ICASE)) |
| 1918 |
{ |
| 1919 |
color lastsubcolor = COLORLESS; |
| 1920 |
|
| 1921 |
subcoloronechr(v, c, lp, rp, &lastsubcolor); |
| 1922 |
return; |
| 1923 |
} |
| 1924 |
|
| 1925 |
/* rats, need general case anyway... */ |
| 1926 |
subcolorcvec(v, allcases(v, c), lp, rp); |
| 1927 |
} |
| 1928 |
|
| 1929 |
/* |
| 1930 |
* optimizebracket - see if bracket expression can be converted to RAINBOW |
| 1931 |
* |
| 1932 |
* Cases such as "[\s\S]" can produce a set of arcs of all colors, which we |
| 1933 |
* can replace by a single RAINBOW arc for efficiency. (This might seem |
| 1934 |
* like a silly way to write ".", but it's seemingly a common locution in |
| 1935 |
* some other flavors of regex, so take the trouble to support it well.) |
| 1936 |
*/ |
| 1937 |
static void |
| 1938 |
optimizebracket(struct vars *v, |
| 1939 |
struct state *lp, |
| 1940 |
struct state *rp) |
| 1941 |
{ |
| 1942 |
struct colordesc *cd; |
| 1943 |
struct colordesc *end = CDEND(v->cm); |
| 1944 |
struct arc *a; |
| 1945 |
bool israinbow; |
| 1946 |
|
| 1947 |
/* |
| 1948 |
* Scan lp's out-arcs and transiently mark the mentioned colors. We |
| 1949 |
* expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp. |
| 1950 |
* (Note: there shouldn't be any pseudocolors yet, but check anyway.) |
| 1951 |
*/ |
| 1952 |
for (a = lp->outs; a != NULL; a = a->outchain) |
| 1953 |
{ |
| 1954 |
assert(a->type == PLAIN); |
| 1955 |
assert(a->co >= 0); /* i.e. not RAINBOW */ |
| 1956 |
assert(a->to == rp); |
| 1957 |
cd = &v->cm->cd[a->co]; |
| 1958 |
assert(!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO)); |
| 1959 |
cd->flags |= COLMARK; |
| 1960 |
} |
| 1961 |
|
| 1962 |
/* Scan colors, clear transient marks, check for unmarked live colors */ |
| 1963 |
israinbow = true; |
| 1964 |
for (cd = v->cm->cd; cd < end; cd++) |
| 1965 |
{ |
| 1966 |
if (cd->flags & COLMARK) |
| 1967 |
cd->flags &= ~COLMARK; |
| 1968 |
else if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO)) |
| 1969 |
israinbow = false; |
| 1970 |
} |
| 1971 |
|
| 1972 |
/* Can't do anything if not all colors have arcs */ |
| 1973 |
if (!israinbow) |
| 1974 |
return; |
| 1975 |
|
| 1976 |
/* OK, drop existing arcs and replace with a rainbow */ |
| 1977 |
while ((a = lp->outs) != NULL) |
| 1978 |
freearc(v->nfa, a); |
| 1979 |
newarc(v->nfa, PLAIN, RAINBOW, lp, rp); |
| 1980 |
} |
| 1981 |
|
| 1982 |
/* |
| 1983 |
* wordchrs - set up word-chr list for word-boundary stuff, if needed |
| 1984 |
* |
| 1985 |
* The list is kept as a bunch of circular arcs on an otherwise-unused state. |
| 1986 |
* |
| 1987 |
* Note that this must not be called while we have any open subcolors, |
| 1988 |
* else construction of the list would confuse color bookkeeping. |
| 1989 |
* Hence, we can't currently apply a similar optimization in |
| 1990 |
* charclass[complement](), as those need to be usable within bracket |
| 1991 |
* expressions. |
| 1992 |
*/ |
| 1993 |
static void |
| 1994 |
wordchrs(struct vars *v) |
| 1995 |
{ |
| 1996 |
struct state *cstate; |
| 1997 |
struct cvec *cv; |
| 1998 |
|
| 1999 |
if (v->wordchrs != NULL) |
| 2000 |
return; /* done already */ |
| 2001 |
|
| 2002 |
/* make dummy state to hang the cache arcs on */ |
| 2003 |
cstate = newstate(v->nfa); |
| 2004 |
NOERR(); |
| 2005 |
|
| 2006 |
/* obtain possibly-cached cvec for \w characters */ |
| 2007 |
NOTE(REG_ULOCALE); |
| 2008 |
cv = cclasscvec(v, CC_WORD, (v->cflags & REG_ICASE)); |
| 2009 |
NOERR(); |
| 2010 |
|
| 2011 |
/* build the arcs; this may cause color splitting */ |
| 2012 |
subcolorcvec(v, cv, cstate, cstate); |
| 2013 |
NOERR(); |
| 2014 |
|
| 2015 |
/* close new open subcolors to ensure the cache entry is self-contained */ |
| 2016 |
okcolors(v->nfa, v->cm); |
| 2017 |
NOERR(); |
| 2018 |
|
| 2019 |
/* success! save the cache pointer */ |
| 2020 |
v->wordchrs = cstate; |
| 2021 |
} |
| 2022 |
|
| 2023 |
/* |
| 2024 |
* processlacon - generate the NFA representation of a LACON |
| 2025 |
* |
| 2026 |
* In the general case this is just newlacon() + newarc(), but some cases |
| 2027 |
* can be optimized. |
| 2028 |
*/ |
| 2029 |
static void |
| 2030 |
processlacon(struct vars *v, |
| 2031 |
struct state *begin, /* start of parsed LACON sub-re */ |
| 2032 |
struct state *end, /* end of parsed LACON sub-re */ |
| 2033 |
int latype, |
| 2034 |
struct state *lp, /* left state to hang it on */ |
| 2035 |
struct state *rp) /* right state to hang it on */ |
| 2036 |
{ |
| 2037 |
struct state *s1; |
| 2038 |
int n; |
| 2039 |
|
| 2040 |
/* |
| 2041 |
* Check for lookaround RE consisting of a single plain color arc (or set |
| 2042 |
* of arcs); this would typically be a simple chr or a bracket expression. |
| 2043 |
*/ |
| 2044 |
s1 = single_color_transition(begin, end); |
| 2045 |
switch (latype) |
| 2046 |
{ |
| 2047 |
case LATYPE_AHEAD_POS: |
| 2048 |
/* If lookahead RE is just colorset C, convert to AHEAD(C) */ |
| 2049 |
if (s1 != NULL) |
| 2050 |
{ |
| 2051 |
cloneouts(v->nfa, s1, lp, rp, AHEAD); |
| 2052 |
return; |
| 2053 |
} |
| 2054 |
break; |
| 2055 |
case LATYPE_AHEAD_NEG: |
| 2056 |
/* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */ |
| 2057 |
if (s1 != NULL) |
| 2058 |
{ |
| 2059 |
colorcomplement(v->nfa, v->cm, AHEAD, s1, lp, rp); |
| 2060 |
newarc(v->nfa, '$', 1, lp, rp); |
| 2061 |
newarc(v->nfa, '$', 0, lp, rp); |
| 2062 |
return; |
| 2063 |
} |
| 2064 |
break; |
| 2065 |
case LATYPE_BEHIND_POS: |
| 2066 |
/* If lookbehind RE is just colorset C, convert to BEHIND(C) */ |
| 2067 |
if (s1 != NULL) |
| 2068 |
{ |
| 2069 |
cloneouts(v->nfa, s1, lp, rp, BEHIND); |
| 2070 |
return; |
| 2071 |
} |
| 2072 |
break; |
| 2073 |
case LATYPE_BEHIND_NEG: |
| 2074 |
/* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */ |
| 2075 |
if (s1 != NULL) |
| 2076 |
{ |
| 2077 |
colorcomplement(v->nfa, v->cm, BEHIND, s1, lp, rp); |
| 2078 |
newarc(v->nfa, '^', 1, lp, rp); |
| 2079 |
newarc(v->nfa, '^', 0, lp, rp); |
| 2080 |
return; |
| 2081 |
} |
| 2082 |
break; |
| 2083 |
default: |
| 2084 |
assert(NOTREACHED); |
| 2085 |
} |
| 2086 |
|
| 2087 |
/* General case: we need a LACON subre and arc */ |
| 2088 |
n = newlacon(v, begin, end, latype); |
| 2089 |
newarc(v->nfa, LACON, n, lp, rp); |
| 2090 |
} |
| 2091 |
|
| 2092 |
/* |
| 2093 |
* subre - allocate a subre |
| 2094 |
*/ |
| 2095 |
static struct subre * |
| 2096 |
subre(struct vars *v, |
| 2097 |
int op, |
| 2098 |
int flags, |
| 2099 |
struct state *begin, |
| 2100 |
struct state *end) |
| 2101 |
{ |
| 2102 |
struct subre *ret = v->treefree; |
| 2103 |
|
| 2104 |
/* |
| 2105 |
* Checking for stack overflow here is sufficient to protect parse() and |
| 2106 |
* its recursive subroutines. |
| 2107 |
*/ |
| 2108 |
if (STACK_TOO_DEEP(v->re)) |
| 2109 |
{ |
| 2110 |
ERR(REG_ETOOBIG); |
| 2111 |
return NULL; |
| 2112 |
} |
| 2113 |
|
| 2114 |
if (ret != NULL) |
| 2115 |
v->treefree = ret->child; |
| 2116 |
else |
| 2117 |
{ |
| 2118 |
ret = (struct subre *) MALLOC(sizeof(struct subre)); |
| 2119 |
if (ret == NULL) |
| 2120 |
{ |
| 2121 |
ERR(REG_ESPACE); |
| 2122 |
return NULL; |
| 2123 |
} |
| 2124 |
ret->chain = v->treechain; |
| 2125 |
v->treechain = ret; |
| 2126 |
} |
| 2127 |
|
| 2128 |
assert(strchr("=b|.*(", op) != NULL); |
| 2129 |
|
| 2130 |
ret->op = op; |
| 2131 |
ret->flags = flags; |
| 2132 |
ret->latype = (char) -1; |
| 2133 |
ret->id = 0; /* will be assigned later */ |
| 2134 |
ret->capno = 0; |
| 2135 |
ret->backno = 0; |
| 2136 |
ret->min = ret->max = 1; |
| 2137 |
ret->child = NULL; |
| 2138 |
ret->sibling = NULL; |
| 2139 |
ret->begin = begin; |
| 2140 |
ret->end = end; |
| 2141 |
ZAPCNFA(ret->cnfa); |
| 2142 |
|
| 2143 |
return ret; |
| 2144 |
} |
| 2145 |
|
| 2146 |
/* |
| 2147 |
* freesubre - free a subRE subtree |
| 2148 |
* |
| 2149 |
* This frees child node(s) of the given subRE too, |
| 2150 |
* but not its siblings. |
| 2151 |
*/ |
| 2152 |
static void |
| 2153 |
freesubre(struct vars *v, /* might be NULL */ |
| 2154 |
struct subre *sr) |
| 2155 |
{ |
| 2156 |
if (sr == NULL) |
| 2157 |
return; |
| 2158 |
|
| 2159 |
if (sr->child != NULL) |
| 2160 |
freesubreandsiblings(v, sr->child); |
| 2161 |
|
| 2162 |
freesrnode(v, sr); |
| 2163 |
} |
| 2164 |
|
| 2165 |
/* |
| 2166 |
* freesubreandsiblings - free a subRE subtree |
| 2167 |
* |
| 2168 |
* This frees child node(s) of the given subRE too, |
| 2169 |
* as well as any following siblings. |
| 2170 |
*/ |
| 2171 |
static void |
| 2172 |
freesubreandsiblings(struct vars *v, /* might be NULL */ |
| 2173 |
struct subre *sr) |
| 2174 |
{ |
| 2175 |
while (sr != NULL) |
| 2176 |
{ |
| 2177 |
struct subre *next = sr->sibling; |
| 2178 |
|
| 2179 |
freesubre(v, sr); |
| 2180 |
sr = next; |
| 2181 |
} |
| 2182 |
} |
| 2183 |
|
| 2184 |
/* |
| 2185 |
* freesrnode - free one node in a subRE subtree |
| 2186 |
*/ |
| 2187 |
static void |
| 2188 |
freesrnode(struct vars *v, /* might be NULL */ |
| 2189 |
struct subre *sr) |
| 2190 |
{ |
| 2191 |
if (sr == NULL) |
| 2192 |
return; |
| 2193 |
|
| 2194 |
if (!NULLCNFA(sr->cnfa)) |
| 2195 |
freecnfa(&sr->cnfa); |
| 2196 |
sr->flags = 0; /* in particular, not INUSE */ |
| 2197 |
sr->child = sr->sibling = NULL; |
| 2198 |
sr->begin = sr->end = NULL; |
| 2199 |
|
| 2200 |
if (v != NULL && v->treechain != NULL) |
| 2201 |
{ |
| 2202 |
/* we're still parsing, maybe we can reuse the subre */ |
| 2203 |
sr->child = v->treefree; |
| 2204 |
v->treefree = sr; |
| 2205 |
} |
| 2206 |
else |
| 2207 |
FREE(sr); |
| 2208 |
} |
| 2209 |
|
| 2210 |
/* |
| 2211 |
* removecaptures - remove unnecessary capture subREs |
| 2212 |
* |
| 2213 |
* If the caller said that it doesn't care about subexpression match data, |
| 2214 |
* we may delete the "capture" markers on subREs that are not referenced |
| 2215 |
* by any backrefs, and then simplify anything that's become non-messy. |
| 2216 |
* Call this only if REG_NOSUB flag is set. |
| 2217 |
*/ |
| 2218 |
static void |
| 2219 |
removecaptures(struct vars *v, |
| 2220 |
struct subre *t) |
| 2221 |
{ |
| 2222 |
struct subre *t2; |
| 2223 |
|
| 2224 |
assert(t != NULL); |
| 2225 |
|
| 2226 |
/* |
| 2227 |
* If this isn't itself a backref target, clear capno and tentatively |
| 2228 |
* clear CAP flag. |
| 2229 |
*/ |
| 2230 |
if (!(t->flags & BRUSE)) |
| 2231 |
{ |
| 2232 |
t->capno = 0; |
| 2233 |
t->flags &= ~CAP; |
| 2234 |
} |
| 2235 |
|
| 2236 |
/* Now recurse to children */ |
| 2237 |
for (t2 = t->child; t2 != NULL; t2 = t2->sibling) |
| 2238 |
{ |
| 2239 |
removecaptures(v, t2); |
| 2240 |
/* Propagate child CAP flag back up, if it's still set */ |
| 2241 |
if (t2->flags & CAP) |
| 2242 |
t->flags |= CAP; |
| 2243 |
} |
| 2244 |
|
| 2245 |
/* |
| 2246 |
* If t now contains neither captures nor backrefs, there's no longer any |
| 2247 |
* need to care where its sub-match boundaries are, so we can reduce it to |
| 2248 |
* a simple DFA node. (Note in particular that MIXED child greediness is |
| 2249 |
* not a hindrance here, so we don't use the MESSY() macro.) |
| 2250 |
*/ |
| 2251 |
if ((t->flags & (CAP | BACKR)) == 0) |
| 2252 |
{ |
| 2253 |
if (t->child) |
| 2254 |
freesubreandsiblings(v, t->child); |
| 2255 |
t->child = NULL; |
| 2256 |
t->op = '='; |
| 2257 |
t->flags &= ~MIXED; |
| 2258 |
} |
| 2259 |
} |
| 2260 |
|
| 2261 |
/* |
| 2262 |
* numst - number tree nodes (assigning "id" indexes) |
| 2263 |
*/ |
| 2264 |
static int /* next number */ |
| 2265 |
numst(struct subre *t, |
| 2266 |
int start) /* starting point for subtree numbers */ |
| 2267 |
{ |
| 2268 |
int i; |
| 2269 |
struct subre *t2; |
| 2270 |
|
| 2271 |
assert(t != NULL); |
| 2272 |
|
| 2273 |
i = start; |
| 2274 |
t->id = i++; |
| 2275 |
for (t2 = t->child; t2 != NULL; t2 = t2->sibling) |
| 2276 |
i = numst(t2, i); |
| 2277 |
return i; |
| 2278 |
} |
| 2279 |
|
| 2280 |
/* |
| 2281 |
* markst - mark tree nodes as INUSE |
| 2282 |
* |
| 2283 |
* Note: this is a great deal more subtle than it looks. During initial |
| 2284 |
* parsing of a regex, all subres are linked into the treechain list; |
| 2285 |
* discarded ones are also linked into the treefree list for possible reuse. |
| 2286 |
* After we are done creating all subres required for a regex, we run markst() |
| 2287 |
* then cleanst(), which results in discarding all subres not reachable from |
| 2288 |
* v->tree. We then clear v->treechain, indicating that subres must be found |
| 2289 |
* by descending from v->tree. This changes the behavior of freesubre(): it |
| 2290 |
* will henceforth FREE() unwanted subres rather than sticking them into the |
| 2291 |
* treefree list. (Doing that any earlier would result in dangling links in |
| 2292 |
* the treechain list.) This all means that freev() will clean up correctly |
| 2293 |
* if invoked before or after markst()+cleanst(); but it would not work if |
| 2294 |
* called partway through this state conversion, so we mustn't error out |
| 2295 |
* in or between these two functions. |
| 2296 |
*/ |
| 2297 |
static void |
| 2298 |
markst(struct subre *t) |
| 2299 |
{ |
| 2300 |
struct subre *t2; |
| 2301 |
|
| 2302 |
assert(t != NULL); |
| 2303 |
|
| 2304 |
t->flags |= INUSE; |
| 2305 |
for (t2 = t->child; t2 != NULL; t2 = t2->sibling) |
| 2306 |
markst(t2); |
| 2307 |
} |
| 2308 |
|
| 2309 |
/* |
| 2310 |
* cleanst - free any tree nodes not marked INUSE |
| 2311 |
*/ |
| 2312 |
static void |
| 2313 |
cleanst(struct vars *v) |
| 2314 |
{ |
| 2315 |
struct subre *t; |
| 2316 |
struct subre *next; |
| 2317 |
|
| 2318 |
for (t = v->treechain; t != NULL; t = next) |
| 2319 |
{ |
| 2320 |
next = t->chain; |
| 2321 |
if (!(t->flags & INUSE)) |
| 2322 |
FREE(t); |
| 2323 |
} |
| 2324 |
v->treechain = NULL; |
| 2325 |
v->treefree = NULL; /* just on general principles */ |
| 2326 |
} |
| 2327 |
|
| 2328 |
/* |
| 2329 |
* nfatree - turn a subRE subtree into a tree of compacted NFAs |
| 2330 |
*/ |
| 2331 |
static long /* optimize results from top node */ |
| 2332 |
nfatree(struct vars *v, |
| 2333 |
struct subre *t, |
| 2334 |
FILE *f) /* for debug output */ |
| 2335 |
{ |
| 2336 |
struct subre *t2; |
| 2337 |
|
| 2338 |
assert(t != NULL && t->begin != NULL); |
| 2339 |
|
| 2340 |
for (t2 = t->child; t2 != NULL; t2 = t2->sibling) |
| 2341 |
(DISCARD) nfatree(v, t2, f); |
| 2342 |
|
| 2343 |
return nfanode(v, t, 0, f); |
| 2344 |
} |
| 2345 |
|
| 2346 |
/* |
| 2347 |
* nfanode - do one NFA for nfatree or lacons |
| 2348 |
* |
| 2349 |
* If converttosearch is true, apply makesearch() to the NFA. |
| 2350 |
*/ |
| 2351 |
static long /* optimize results */ |
| 2352 |
nfanode(struct vars *v, |
| 2353 |
struct subre *t, |
| 2354 |
int converttosearch, |
| 2355 |
FILE *f) /* for debug output */ |
| 2356 |
{ |
| 2357 |
struct nfa *nfa; |
| 2358 |
long ret = 0; |
| 2359 |
|
| 2360 |
assert(t->begin != NULL); |
| 2361 |
|
| 2362 |
#ifdef REG_DEBUG |
| 2363 |
if (f != NULL) |
| 2364 |
{ |
| 2365 |
char idbuf[50]; |
| 2366 |
|
| 2367 |
fprintf(f, "\n\n\n========= TREE NODE %s ==========\n", |
| 2368 |
stid(t, idbuf, sizeof(idbuf))); |
| 2369 |
} |
| 2370 |
#endif |
| 2371 |
nfa = newnfa(v, v->cm, v->nfa); |
| 2372 |
NOERRZ(); |
| 2373 |
dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final); |
| 2374 |
nfa->flags = v->nfa->flags; |
| 2375 |
if (!ISERR()) |
| 2376 |
specialcolors(nfa); |
| 2377 |
if (!ISERR()) |
| 2378 |
ret = optimize(nfa, f); |
| 2379 |
if (converttosearch && !ISERR()) |
| 2380 |
makesearch(v, nfa); |
| 2381 |
if (!ISERR()) |
| 2382 |
compact(nfa, &t->cnfa); |
| 2383 |
|
| 2384 |
freenfa(nfa); |
| 2385 |
return ret; |
| 2386 |
} |
| 2387 |
|
| 2388 |
/* |
| 2389 |
* newlacon - allocate a lookaround-constraint subRE |
| 2390 |
*/ |
| 2391 |
static int /* lacon number */ |
| 2392 |
newlacon(struct vars *v, |
| 2393 |
struct state *begin, |
| 2394 |
struct state *end, |
| 2395 |
int latype) |
| 2396 |
{ |
| 2397 |
int n; |
| 2398 |
struct subre *newlacons; |
| 2399 |
struct subre *sub; |
| 2400 |
|
| 2401 |
if (v->nlacons == 0) |
| 2402 |
{ |
| 2403 |
n = 1; /* skip 0th */ |
| 2404 |
newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); |
| 2405 |
} |
| 2406 |
else |
| 2407 |
{ |
| 2408 |
n = v->nlacons; |
| 2409 |
/* better use REALLOC_ARRAY here, as struct subre is big */ |
| 2410 |
newlacons = REALLOC_ARRAY(v->lacons, struct subre, n + 1); |
| 2411 |
} |
| 2412 |
if (newlacons == NULL) |
| 2413 |
{ |
| 2414 |
ERR(REG_ESPACE); |
| 2415 |
return 0; |
| 2416 |
} |
| 2417 |
v->lacons = newlacons; |
| 2418 |
v->nlacons = n + 1; |
| 2419 |
sub = &v->lacons[n]; |
| 2420 |
sub->begin = begin; |
| 2421 |
sub->end = end; |
| 2422 |
sub->latype = latype; |
| 2423 |
ZAPCNFA(sub->cnfa); |
| 2424 |
return n; |
| 2425 |
} |
| 2426 |
|
| 2427 |
/* |
| 2428 |
* freelacons - free lookaround-constraint subRE vector |
| 2429 |
*/ |
| 2430 |
static void |
| 2431 |
freelacons(struct subre *subs, |
| 2432 |
int n) |
| 2433 |
{ |
| 2434 |
struct subre *sub; |
| 2435 |
int i; |
| 2436 |
|
| 2437 |
assert(n > 0); |
| 2438 |
for (sub = subs + 1, i = n - 1; i > 0; sub++, i--) /* no 0th */ |
| 2439 |
if (!NULLCNFA(sub->cnfa)) |
| 2440 |
freecnfa(&sub->cnfa); |
| 2441 |
FREE(subs); |
| 2442 |
} |
| 2443 |
|
| 2444 |
/* |
| 2445 |
* rfree - free a whole RE (insides of regfree) |
| 2446 |
*/ |
| 2447 |
static void |
| 2448 |
rfree(regex_t *re) |
| 2449 |
{ |
| 2450 |
struct guts *g; |
| 2451 |
|
| 2452 |
if (re == NULL || re->re_magic != REMAGIC) |
| 2453 |
return; |
| 2454 |
|
| 2455 |
re->re_magic = 0; /* invalidate RE */ |
| 2456 |
g = (struct guts *) re->re_guts; |
| 2457 |
re->re_guts = NULL; |
| 2458 |
re->re_fns = NULL; |
| 2459 |
if (g != NULL) |
| 2460 |
{ |
| 2461 |
g->magic = 0; |
| 2462 |
freecm(&g->cmap); |
| 2463 |
if (g->tree != NULL) |
| 2464 |
freesubre((struct vars *) NULL, g->tree); |
| 2465 |
if (g->lacons != NULL) |
| 2466 |
freelacons(g->lacons, g->nlacons); |
| 2467 |
if (!NULLCNFA(g->search)) |
| 2468 |
freecnfa(&g->search); |
| 2469 |
FREE(g); |
| 2470 |
} |
| 2471 |
} |
| 2472 |
|
| 2473 |
/* |
| 2474 |
* rstacktoodeep - check for stack getting dangerously deep |
| 2475 |
* |
| 2476 |
* Return nonzero to fail the operation with error code REG_ETOOBIG, |
| 2477 |
* zero to keep going |
| 2478 |
* |
| 2479 |
* The current implementation is Postgres-specific. If we ever get around |
| 2480 |
* to splitting the regex code out as a standalone library, there will need |
| 2481 |
* to be some API to let applications define a callback function for this. |
| 2482 |
*/ |
| 2483 |
static int |
| 2484 |
rstacktoodeep(void) |
| 2485 |
{ |
| 2486 |
return stack_is_too_deep(); |
| 2487 |
} |
| 2488 |
|
| 2489 |
#ifdef REG_DEBUG |
| 2490 |
|
| 2491 |
/* |
| 2492 |
* dump - dump an RE in human-readable form |
| 2493 |
*/ |
| 2494 |
static void |
| 2495 |
dump(regex_t *re, |
| 2496 |
FILE *f) |
| 2497 |
{ |
| 2498 |
struct guts *g; |
| 2499 |
int i; |
| 2500 |
|
| 2501 |
if (re->re_magic != REMAGIC) |
| 2502 |
fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic, |
| 2503 |
REMAGIC); |
| 2504 |
if (re->re_guts == NULL) |
| 2505 |
{ |
| 2506 |
fprintf(f, "NULL guts!!!\n"); |
| 2507 |
return; |
| 2508 |
} |
| 2509 |
g = (struct guts *) re->re_guts; |
| 2510 |
if (g->magic != GUTSMAGIC) |
| 2511 |
fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic, |
| 2512 |
GUTSMAGIC); |
| 2513 |
|
| 2514 |
fprintf(f, "\n\n\n========= DUMP ==========\n"); |
| 2515 |
fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", |
| 2516 |
(int) re->re_nsub, re->re_info, re->re_csize, g->ntree); |
| 2517 |
|
| 2518 |
dumpcolors(&g->cmap, f); |
| 2519 |
if (!NULLCNFA(g->search)) |
| 2520 |
{ |
| 2521 |
fprintf(f, "\nsearch:\n"); |
| 2522 |
dumpcnfa(&g->search, f); |
| 2523 |
} |
| 2524 |
for (i = 1; i < g->nlacons; i++) |
| 2525 |
{ |
| 2526 |
struct subre *lasub = &g->lacons[i]; |
| 2527 |
const char *latype; |
| 2528 |
|
| 2529 |
switch (lasub->latype) |
| 2530 |
{ |
| 2531 |
case LATYPE_AHEAD_POS: |
| 2532 |
latype = "positive lookahead"; |
| 2533 |
break; |
| 2534 |
case LATYPE_AHEAD_NEG: |
| 2535 |
latype = "negative lookahead"; |
| 2536 |
break; |
| 2537 |
case LATYPE_BEHIND_POS: |
| 2538 |
latype = "positive lookbehind"; |
| 2539 |
break; |
| 2540 |
case LATYPE_BEHIND_NEG: |
| 2541 |
latype = "negative lookbehind"; |
| 2542 |
break; |
| 2543 |
default: |
| 2544 |
latype = "???"; |
| 2545 |
break; |
| 2546 |
} |
| 2547 |
fprintf(f, "\nla%d (%s):\n", i, latype); |
| 2548 |
dumpcnfa(&lasub->cnfa, f); |
| 2549 |
} |
| 2550 |
fprintf(f, "\n"); |
| 2551 |
dumpst(g->tree, f, 0); |
| 2552 |
} |
| 2553 |
|
| 2554 |
/* |
| 2555 |
* dumpst - dump a subRE tree |
| 2556 |
*/ |
| 2557 |
static void |
| 2558 |
dumpst(struct subre *t, |
| 2559 |
FILE *f, |
| 2560 |
int nfapresent) /* is the original NFA still around? */ |
| 2561 |
{ |
| 2562 |
if (t == NULL) |
| 2563 |
fprintf(f, "null tree\n"); |
| 2564 |
else |
| 2565 |
stdump(t, f, nfapresent); |
| 2566 |
fflush(f); |
| 2567 |
} |
| 2568 |
|
| 2569 |
/* |
| 2570 |
* stdump - recursive guts of dumpst |
| 2571 |
*/ |
| 2572 |
static void |
| 2573 |
stdump(struct subre *t, |
| 2574 |
FILE *f, |
| 2575 |
int nfapresent) /* is the original NFA still around? */ |
| 2576 |
{ |
| 2577 |
char idbuf[50]; |
| 2578 |
struct subre *t2; |
| 2579 |
|
| 2580 |
fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op); |
| 2581 |
if (t->flags & LONGER) |
| 2582 |
fprintf(f, " longest"); |
| 2583 |
if (t->flags & SHORTER) |
| 2584 |
fprintf(f, " shortest"); |
| 2585 |
if (t->flags & MIXED) |
| 2586 |
fprintf(f, " hasmixed"); |
| 2587 |
if (t->flags & CAP) |
| 2588 |
fprintf(f, " hascapture"); |
| 2589 |
if (t->flags & BACKR) |
| 2590 |
fprintf(f, " hasbackref"); |
| 2591 |
if (t->flags & BRUSE) |
| 2592 |
fprintf(f, " isreferenced"); |
| 2593 |
if (!(t->flags & INUSE)) |
| 2594 |
fprintf(f, " UNUSED"); |
| 2595 |
if (t->latype != (char) -1) |
| 2596 |
fprintf(f, " latype(%d)", t->latype); |
| 2597 |
if (t->capno != 0) |
| 2598 |
fprintf(f, " capture(%d)", t->capno); |
| 2599 |
if (t->backno != 0) |
| 2600 |
fprintf(f, " backref(%d)", t->backno); |
| 2601 |
if (t->min != 1 || t->max != 1) |
| 2602 |
{ |
| 2603 |
fprintf(f, " {%d,", t->min); |
| 2604 |
if (t->max != DUPINF) |
| 2605 |
fprintf(f, "%d", t->max); |
| 2606 |
fprintf(f, "}"); |
| 2607 |
} |
| 2608 |
if (nfapresent) |
| 2609 |
fprintf(f, " %ld-%ld", (long) t->begin->no, (long) t->end->no); |
| 2610 |
if (t->child != NULL) |
| 2611 |
fprintf(f, " C:%s", stid(t->child, idbuf, sizeof(idbuf))); |
| 2612 |
/* printing second child isn't necessary, but it is often helpful */ |
| 2613 |
if (t->child != NULL && t->child->sibling != NULL) |
| 2614 |
fprintf(f, " C2:%s", stid(t->child->sibling, idbuf, sizeof(idbuf))); |
| 2615 |
if (t->sibling != NULL) |
| 2616 |
fprintf(f, " S:%s", stid(t->sibling, idbuf, sizeof(idbuf))); |
| 2617 |
if (!NULLCNFA(t->cnfa)) |
| 2618 |
{ |
| 2619 |
fprintf(f, "\n"); |
| 2620 |
dumpcnfa(&t->cnfa, f); |
| 2621 |
} |
| 2622 |
fprintf(f, "\n"); |
| 2623 |
for (t2 = t->child; t2 != NULL; t2 = t2->sibling) |
| 2624 |
stdump(t2, f, nfapresent); |
| 2625 |
} |
| 2626 |
|
| 2627 |
/* |
| 2628 |
* stid - identify a subtree node for dumping |
| 2629 |
*/ |
| 2630 |
static const char * /* points to buf or constant string */ |
| 2631 |
stid(struct subre *t, |
| 2632 |
char *buf, |
| 2633 |
size_t bufsize) |
| 2634 |
{ |
| 2635 |
/* big enough for hex int or decimal t->id? */ |
| 2636 |
if (bufsize < sizeof(void *) * 2 + 3 || bufsize < sizeof(t->id) * 3 + 1) |
| 2637 |
return "unable"; |
| 2638 |
if (t->id != 0) |
| 2639 |
sprintf(buf, "%d", t->id); |
| 2640 |
else |
| 2641 |
sprintf(buf, "%p", t); |
| 2642 |
return buf; |
| 2643 |
} |
| 2644 |
#endif /* REG_DEBUG */ |
| 2645 |
|
| 2646 |
|
| 2647 |
#include "regc_lex.c" |
| 2648 |
#include "regc_color.c" |
| 2649 |
#include "regc_nfa.c" |
| 2650 |
#include "regc_cvec.c" |
| 2651 |
#include "regc_pg_locale.c" |
| 2652 |
#include "regc_locale.c" |