1198090Srdivacky/*- 2198090Srdivacky * This code is derived from OpenBSD's libc/regex, original license follows: 3198090Srdivacky * 4198090Srdivacky * Copyright (c) 1992, 1993, 1994 Henry Spencer. 5198090Srdivacky * Copyright (c) 1992, 1993, 1994 6198090Srdivacky * The Regents of the University of California. All rights reserved. 7198090Srdivacky * 8198090Srdivacky * This code is derived from software contributed to Berkeley by 9198090Srdivacky * Henry Spencer. 10198090Srdivacky * 11198090Srdivacky * Redistribution and use in source and binary forms, with or without 12198090Srdivacky * modification, are permitted provided that the following conditions 13198090Srdivacky * are met: 14198090Srdivacky * 1. Redistributions of source code must retain the above copyright 15198090Srdivacky * notice, this list of conditions and the following disclaimer. 16198090Srdivacky * 2. Redistributions in binary form must reproduce the above copyright 17198090Srdivacky * notice, this list of conditions and the following disclaimer in the 18198090Srdivacky * documentation and/or other materials provided with the distribution. 19198090Srdivacky * 3. Neither the name of the University nor the names of its contributors 20198090Srdivacky * may be used to endorse or promote products derived from this software 21198090Srdivacky * without specific prior written permission. 22198090Srdivacky * 23198090Srdivacky * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24198090Srdivacky * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25198090Srdivacky * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26198090Srdivacky * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27198090Srdivacky * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28198090Srdivacky * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29198090Srdivacky * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30198090Srdivacky * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31198090Srdivacky * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32198090Srdivacky * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33198090Srdivacky * SUCH DAMAGE. 34198090Srdivacky * 35198090Srdivacky * @(#)engine.c 8.5 (Berkeley) 3/20/94 36198090Srdivacky */ 37198090Srdivacky 38198090Srdivacky/* 39198090Srdivacky * The matching engine and friends. This file is #included by regexec.c 40198090Srdivacky * after suitable #defines of a variety of macros used herein, so that 41198090Srdivacky * different state representations can be used without duplicating masses 42198090Srdivacky * of code. 43198090Srdivacky */ 44198090Srdivacky 45198090Srdivacky#ifdef SNAMES 46198090Srdivacky#define matcher smatcher 47198090Srdivacky#define fast sfast 48198090Srdivacky#define slow sslow 49198090Srdivacky#define dissect sdissect 50198090Srdivacky#define backref sbackref 51198090Srdivacky#define step sstep 52198090Srdivacky#define print sprint 53198090Srdivacky#define at sat 54198090Srdivacky#define match smat 55198090Srdivacky#define nope snope 56198090Srdivacky#endif 57198090Srdivacky#ifdef LNAMES 58198090Srdivacky#define matcher lmatcher 59198090Srdivacky#define fast lfast 60198090Srdivacky#define slow lslow 61198090Srdivacky#define dissect ldissect 62198090Srdivacky#define backref lbackref 63198090Srdivacky#define step lstep 64198090Srdivacky#define print lprint 65198090Srdivacky#define at lat 66198090Srdivacky#define match lmat 67198090Srdivacky#define nope lnope 68198090Srdivacky#endif 69198090Srdivacky 70198090Srdivacky/* another structure passed up and down to avoid zillions of parameters */ 71198090Srdivackystruct match { 72198090Srdivacky struct re_guts *g; 73198090Srdivacky int eflags; 74198090Srdivacky llvm_regmatch_t *pmatch; /* [nsub+1] (0 element unused) */ 75206274Srdivacky const char *offp; /* offsets work from here */ 76206274Srdivacky const char *beginp; /* start of string -- virtual NUL precedes */ 77206274Srdivacky const char *endp; /* end of string -- virtual NUL here */ 78206274Srdivacky const char *coldp; /* can be no match starting before here */ 79206274Srdivacky const char **lastpos; /* [nplus+1] */ 80198090Srdivacky STATEVARS; 81198090Srdivacky states st; /* current states */ 82198090Srdivacky states fresh; /* states for a fresh start */ 83198090Srdivacky states tmp; /* temporary */ 84198090Srdivacky states empty; /* empty set of states */ 85198090Srdivacky}; 86198090Srdivacky 87206274Srdivackystatic int matcher(struct re_guts *, const char *, size_t, 88206274Srdivacky llvm_regmatch_t[], int); 89206274Srdivackystatic const char *dissect(struct match *, const char *, const char *, sopno, 90206274Srdivacky sopno); 91206274Srdivackystatic const char *backref(struct match *, const char *, const char *, sopno, 92206274Srdivacky sopno, sopno, int); 93206274Srdivackystatic const char *fast(struct match *, const char *, const char *, sopno, sopno); 94206274Srdivackystatic const char *slow(struct match *, const char *, const char *, sopno, sopno); 95198090Srdivackystatic states step(struct re_guts *, sopno, sopno, states, int, states); 96198090Srdivacky#define MAX_RECURSION 100 97198090Srdivacky#define BOL (OUT+1) 98198090Srdivacky#define EOL (BOL+1) 99198090Srdivacky#define BOLEOL (BOL+2) 100198090Srdivacky#define NOTHING (BOL+3) 101198090Srdivacky#define BOW (BOL+4) 102198090Srdivacky#define EOW (BOL+5) 103198090Srdivacky#define CODEMAX (BOL+5) /* highest code used */ 104198090Srdivacky#define NONCHAR(c) ((c) > CHAR_MAX) 105198090Srdivacky#define NNONCHAR (CODEMAX-CHAR_MAX) 106198090Srdivacky#ifdef REDEBUG 107198090Srdivackystatic void print(struct match *, char *, states, int, FILE *); 108198090Srdivacky#endif 109198090Srdivacky#ifdef REDEBUG 110198090Srdivackystatic void at(struct match *, char *, char *, char *, sopno, sopno); 111198090Srdivacky#endif 112198090Srdivacky#ifdef REDEBUG 113198090Srdivackystatic char *pchar(int); 114198090Srdivacky#endif 115198090Srdivacky 116198090Srdivacky#ifdef REDEBUG 117198090Srdivacky#define SP(t, s, c) print(m, t, s, c, stdout) 118198090Srdivacky#define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2) 119198090Srdivacky#define NOTE(str) { if (m->eflags®_TRACE) (void)printf("=%s\n", (str)); } 120198090Srdivackystatic int nope = 0; 121198090Srdivacky#else 122198090Srdivacky#define SP(t, s, c) /* nothing */ 123198090Srdivacky#define AT(t, p1, p2, s1, s2) /* nothing */ 124198090Srdivacky#define NOTE(s) /* nothing */ 125198090Srdivacky#endif 126198090Srdivacky 127198090Srdivacky/* 128198090Srdivacky - matcher - the actual matching engine 129198090Srdivacky */ 130198090Srdivackystatic int /* 0 success, REG_NOMATCH failure */ 131206274Srdivackymatcher(struct re_guts *g, const char *string, size_t nmatch, 132206274Srdivacky llvm_regmatch_t pmatch[], 133198090Srdivacky int eflags) 134198090Srdivacky{ 135206274Srdivacky const char *endp; 136198090Srdivacky size_t i; 137198090Srdivacky struct match mv; 138198090Srdivacky struct match *m = &mv; 139206274Srdivacky const char *dp; 140198090Srdivacky const sopno gf = g->firststate+1; /* +1 for OEND */ 141198090Srdivacky const sopno gl = g->laststate; 142206274Srdivacky const char *start; 143206274Srdivacky const char *stop; 144198090Srdivacky 145198090Srdivacky /* simplify the situation where possible */ 146198090Srdivacky if (g->cflags®_NOSUB) 147198090Srdivacky nmatch = 0; 148198090Srdivacky if (eflags®_STARTEND) { 149198090Srdivacky start = string + pmatch[0].rm_so; 150198090Srdivacky stop = string + pmatch[0].rm_eo; 151198090Srdivacky } else { 152198090Srdivacky start = string; 153198090Srdivacky stop = start + strlen(start); 154198090Srdivacky } 155198090Srdivacky if (stop < start) 156198090Srdivacky return(REG_INVARG); 157198090Srdivacky 158198090Srdivacky /* prescreening; this does wonders for this rather slow code */ 159198090Srdivacky if (g->must != NULL) { 160198090Srdivacky for (dp = start; dp < stop; dp++) 161198090Srdivacky if (*dp == g->must[0] && stop - dp >= g->mlen && 162198090Srdivacky memcmp(dp, g->must, (size_t)g->mlen) == 0) 163198090Srdivacky break; 164198090Srdivacky if (dp == stop) /* we didn't find g->must */ 165198090Srdivacky return(REG_NOMATCH); 166198090Srdivacky } 167198090Srdivacky 168198090Srdivacky /* match struct setup */ 169198090Srdivacky m->g = g; 170198090Srdivacky m->eflags = eflags; 171198090Srdivacky m->pmatch = NULL; 172198090Srdivacky m->lastpos = NULL; 173198090Srdivacky m->offp = string; 174198090Srdivacky m->beginp = start; 175198090Srdivacky m->endp = stop; 176198090Srdivacky STATESETUP(m, 4); 177198090Srdivacky SETUP(m->st); 178198090Srdivacky SETUP(m->fresh); 179198090Srdivacky SETUP(m->tmp); 180198090Srdivacky SETUP(m->empty); 181198090Srdivacky CLEAR(m->empty); 182198090Srdivacky 183198090Srdivacky /* this loop does only one repetition except for backrefs */ 184198090Srdivacky for (;;) { 185198090Srdivacky endp = fast(m, start, stop, gf, gl); 186198090Srdivacky if (endp == NULL) { /* a miss */ 187198090Srdivacky free(m->pmatch); 188207618Srdivacky free((void*)m->lastpos); 189198090Srdivacky STATETEARDOWN(m); 190198090Srdivacky return(REG_NOMATCH); 191198090Srdivacky } 192198090Srdivacky if (nmatch == 0 && !g->backrefs) 193198090Srdivacky break; /* no further info needed */ 194198090Srdivacky 195198090Srdivacky /* where? */ 196198090Srdivacky assert(m->coldp != NULL); 197198090Srdivacky for (;;) { 198198090Srdivacky NOTE("finding start"); 199198090Srdivacky endp = slow(m, m->coldp, stop, gf, gl); 200198090Srdivacky if (endp != NULL) 201198090Srdivacky break; 202198090Srdivacky assert(m->coldp < m->endp); 203198090Srdivacky m->coldp++; 204198090Srdivacky } 205198090Srdivacky if (nmatch == 1 && !g->backrefs) 206198090Srdivacky break; /* no further info needed */ 207198090Srdivacky 208276479Sdim /* oh my, they want the subexpressions... */ 209198090Srdivacky if (m->pmatch == NULL) 210198090Srdivacky m->pmatch = (llvm_regmatch_t *)malloc((m->g->nsub + 1) * 211198090Srdivacky sizeof(llvm_regmatch_t)); 212198090Srdivacky if (m->pmatch == NULL) { 213198090Srdivacky STATETEARDOWN(m); 214198090Srdivacky return(REG_ESPACE); 215198090Srdivacky } 216198090Srdivacky for (i = 1; i <= m->g->nsub; i++) 217198090Srdivacky m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1; 218198090Srdivacky if (!g->backrefs && !(m->eflags®_BACKR)) { 219198090Srdivacky NOTE("dissecting"); 220198090Srdivacky dp = dissect(m, m->coldp, endp, gf, gl); 221198090Srdivacky } else { 222198090Srdivacky if (g->nplus > 0 && m->lastpos == NULL) 223206274Srdivacky m->lastpos = (const char **)malloc((g->nplus+1) * 224198090Srdivacky sizeof(char *)); 225198090Srdivacky if (g->nplus > 0 && m->lastpos == NULL) { 226198090Srdivacky free(m->pmatch); 227198090Srdivacky STATETEARDOWN(m); 228198090Srdivacky return(REG_ESPACE); 229198090Srdivacky } 230198090Srdivacky NOTE("backref dissect"); 231198090Srdivacky dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); 232198090Srdivacky } 233198090Srdivacky if (dp != NULL) 234198090Srdivacky break; 235198090Srdivacky 236198090Srdivacky /* uh-oh... we couldn't find a subexpression-level match */ 237198090Srdivacky assert(g->backrefs); /* must be back references doing it */ 238198090Srdivacky assert(g->nplus == 0 || m->lastpos != NULL); 239198090Srdivacky for (;;) { 240198090Srdivacky if (dp != NULL || endp <= m->coldp) 241198090Srdivacky break; /* defeat */ 242198090Srdivacky NOTE("backoff"); 243198090Srdivacky endp = slow(m, m->coldp, endp-1, gf, gl); 244198090Srdivacky if (endp == NULL) 245198090Srdivacky break; /* defeat */ 246198090Srdivacky /* try it on a shorter possibility */ 247198090Srdivacky#ifndef NDEBUG 248198090Srdivacky for (i = 1; i <= m->g->nsub; i++) { 249198090Srdivacky assert(m->pmatch[i].rm_so == -1); 250198090Srdivacky assert(m->pmatch[i].rm_eo == -1); 251198090Srdivacky } 252198090Srdivacky#endif 253198090Srdivacky NOTE("backoff dissect"); 254198090Srdivacky dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); 255198090Srdivacky } 256198090Srdivacky assert(dp == NULL || dp == endp); 257198090Srdivacky if (dp != NULL) /* found a shorter one */ 258198090Srdivacky break; 259198090Srdivacky 260198090Srdivacky /* despite initial appearances, there is no match here */ 261198090Srdivacky NOTE("false alarm"); 262198090Srdivacky if (m->coldp == stop) 263198090Srdivacky break; 264198090Srdivacky start = m->coldp + 1; /* recycle starting later */ 265198090Srdivacky } 266198090Srdivacky 267198090Srdivacky /* fill in the details if requested */ 268198090Srdivacky if (nmatch > 0) { 269198090Srdivacky pmatch[0].rm_so = m->coldp - m->offp; 270198090Srdivacky pmatch[0].rm_eo = endp - m->offp; 271198090Srdivacky } 272198090Srdivacky if (nmatch > 1) { 273198090Srdivacky assert(m->pmatch != NULL); 274198090Srdivacky for (i = 1; i < nmatch; i++) 275198090Srdivacky if (i <= m->g->nsub) 276198090Srdivacky pmatch[i] = m->pmatch[i]; 277198090Srdivacky else { 278198090Srdivacky pmatch[i].rm_so = -1; 279198090Srdivacky pmatch[i].rm_eo = -1; 280198090Srdivacky } 281198090Srdivacky } 282198090Srdivacky 283198090Srdivacky if (m->pmatch != NULL) 284198090Srdivacky free((char *)m->pmatch); 285198090Srdivacky if (m->lastpos != NULL) 286198090Srdivacky free((char *)m->lastpos); 287198090Srdivacky STATETEARDOWN(m); 288198090Srdivacky return(0); 289198090Srdivacky} 290198090Srdivacky 291198090Srdivacky/* 292198090Srdivacky - dissect - figure out what matched what, no back references 293198090Srdivacky */ 294206274Srdivackystatic const char * /* == stop (success) always */ 295206274Srdivackydissect(struct match *m, const char *start, const char *stop, sopno startst, 296206274Srdivacky sopno stopst) 297198090Srdivacky{ 298198090Srdivacky int i; 299198090Srdivacky sopno ss; /* start sop of current subRE */ 300198090Srdivacky sopno es; /* end sop of current subRE */ 301206274Srdivacky const char *sp; /* start of string matched by it */ 302206274Srdivacky const char *stp; /* string matched by it cannot pass here */ 303206274Srdivacky const char *rest; /* start of rest of string */ 304206274Srdivacky const char *tail; /* string unmatched by rest of RE */ 305198090Srdivacky sopno ssub; /* start sop of subsubRE */ 306198090Srdivacky sopno esub; /* end sop of subsubRE */ 307206274Srdivacky const char *ssp; /* start of string matched by subsubRE */ 308206274Srdivacky const char *sep; /* end of string matched by subsubRE */ 309206274Srdivacky const char *oldssp; /* previous ssp */ 310198090Srdivacky 311198090Srdivacky AT("diss", start, stop, startst, stopst); 312198090Srdivacky sp = start; 313198090Srdivacky for (ss = startst; ss < stopst; ss = es) { 314198090Srdivacky /* identify end of subRE */ 315198090Srdivacky es = ss; 316198090Srdivacky switch (OP(m->g->strip[es])) { 317198090Srdivacky case OPLUS_: 318198090Srdivacky case OQUEST_: 319198090Srdivacky es += OPND(m->g->strip[es]); 320198090Srdivacky break; 321198090Srdivacky case OCH_: 322198090Srdivacky while (OP(m->g->strip[es]) != O_CH) 323198090Srdivacky es += OPND(m->g->strip[es]); 324198090Srdivacky break; 325198090Srdivacky } 326198090Srdivacky es++; 327198090Srdivacky 328198090Srdivacky /* figure out what it matched */ 329198090Srdivacky switch (OP(m->g->strip[ss])) { 330198090Srdivacky case OEND: 331198090Srdivacky assert(nope); 332198090Srdivacky break; 333198090Srdivacky case OCHAR: 334198090Srdivacky sp++; 335198090Srdivacky break; 336198090Srdivacky case OBOL: 337198090Srdivacky case OEOL: 338198090Srdivacky case OBOW: 339198090Srdivacky case OEOW: 340198090Srdivacky break; 341198090Srdivacky case OANY: 342198090Srdivacky case OANYOF: 343198090Srdivacky sp++; 344198090Srdivacky break; 345198090Srdivacky case OBACK_: 346198090Srdivacky case O_BACK: 347198090Srdivacky assert(nope); 348198090Srdivacky break; 349198090Srdivacky /* cases where length of match is hard to find */ 350198090Srdivacky case OQUEST_: 351198090Srdivacky stp = stop; 352198090Srdivacky for (;;) { 353198090Srdivacky /* how long could this one be? */ 354198090Srdivacky rest = slow(m, sp, stp, ss, es); 355198090Srdivacky assert(rest != NULL); /* it did match */ 356198090Srdivacky /* could the rest match the rest? */ 357198090Srdivacky tail = slow(m, rest, stop, es, stopst); 358198090Srdivacky if (tail == stop) 359198090Srdivacky break; /* yes! */ 360198090Srdivacky /* no -- try a shorter match for this one */ 361198090Srdivacky stp = rest - 1; 362198090Srdivacky assert(stp >= sp); /* it did work */ 363198090Srdivacky } 364198090Srdivacky ssub = ss + 1; 365198090Srdivacky esub = es - 1; 366198090Srdivacky /* did innards match? */ 367198090Srdivacky if (slow(m, sp, rest, ssub, esub) != NULL) { 368206274Srdivacky const char *dp = dissect(m, sp, rest, ssub, esub); 369198090Srdivacky (void)dp; /* avoid warning if assertions off */ 370198090Srdivacky assert(dp == rest); 371198090Srdivacky } else /* no */ 372198090Srdivacky assert(sp == rest); 373198090Srdivacky sp = rest; 374198090Srdivacky break; 375198090Srdivacky case OPLUS_: 376198090Srdivacky stp = stop; 377198090Srdivacky for (;;) { 378198090Srdivacky /* how long could this one be? */ 379198090Srdivacky rest = slow(m, sp, stp, ss, es); 380198090Srdivacky assert(rest != NULL); /* it did match */ 381198090Srdivacky /* could the rest match the rest? */ 382198090Srdivacky tail = slow(m, rest, stop, es, stopst); 383198090Srdivacky if (tail == stop) 384198090Srdivacky break; /* yes! */ 385198090Srdivacky /* no -- try a shorter match for this one */ 386198090Srdivacky stp = rest - 1; 387198090Srdivacky assert(stp >= sp); /* it did work */ 388198090Srdivacky } 389198090Srdivacky ssub = ss + 1; 390198090Srdivacky esub = es - 1; 391198090Srdivacky ssp = sp; 392198090Srdivacky oldssp = ssp; 393198090Srdivacky for (;;) { /* find last match of innards */ 394198090Srdivacky sep = slow(m, ssp, rest, ssub, esub); 395198090Srdivacky if (sep == NULL || sep == ssp) 396198090Srdivacky break; /* failed or matched null */ 397198090Srdivacky oldssp = ssp; /* on to next try */ 398198090Srdivacky ssp = sep; 399198090Srdivacky } 400198090Srdivacky if (sep == NULL) { 401198090Srdivacky /* last successful match */ 402198090Srdivacky sep = ssp; 403198090Srdivacky ssp = oldssp; 404198090Srdivacky } 405198090Srdivacky assert(sep == rest); /* must exhaust substring */ 406198090Srdivacky assert(slow(m, ssp, sep, ssub, esub) == rest); 407198090Srdivacky { 408206274Srdivacky const char *dp = dissect(m, ssp, sep, ssub, esub); 409198090Srdivacky (void)dp; /* avoid warning if assertions off */ 410198090Srdivacky assert(dp == sep); 411198090Srdivacky } 412198090Srdivacky sp = rest; 413198090Srdivacky break; 414198090Srdivacky case OCH_: 415198090Srdivacky stp = stop; 416198090Srdivacky for (;;) { 417198090Srdivacky /* how long could this one be? */ 418198090Srdivacky rest = slow(m, sp, stp, ss, es); 419198090Srdivacky assert(rest != NULL); /* it did match */ 420198090Srdivacky /* could the rest match the rest? */ 421198090Srdivacky tail = slow(m, rest, stop, es, stopst); 422198090Srdivacky if (tail == stop) 423198090Srdivacky break; /* yes! */ 424198090Srdivacky /* no -- try a shorter match for this one */ 425198090Srdivacky stp = rest - 1; 426198090Srdivacky assert(stp >= sp); /* it did work */ 427198090Srdivacky } 428198090Srdivacky ssub = ss + 1; 429198090Srdivacky esub = ss + OPND(m->g->strip[ss]) - 1; 430198090Srdivacky assert(OP(m->g->strip[esub]) == OOR1); 431198090Srdivacky for (;;) { /* find first matching branch */ 432198090Srdivacky if (slow(m, sp, rest, ssub, esub) == rest) 433198090Srdivacky break; /* it matched all of it */ 434198090Srdivacky /* that one missed, try next one */ 435198090Srdivacky assert(OP(m->g->strip[esub]) == OOR1); 436198090Srdivacky esub++; 437198090Srdivacky assert(OP(m->g->strip[esub]) == OOR2); 438198090Srdivacky ssub = esub + 1; 439198090Srdivacky esub += OPND(m->g->strip[esub]); 440198090Srdivacky if (OP(m->g->strip[esub]) == OOR2) 441198090Srdivacky esub--; 442198090Srdivacky else 443198090Srdivacky assert(OP(m->g->strip[esub]) == O_CH); 444198090Srdivacky } 445198090Srdivacky { 446206274Srdivacky const char *dp = dissect(m, sp, rest, ssub, esub); 447198090Srdivacky (void)dp; /* avoid warning if assertions off */ 448198090Srdivacky assert(dp == rest); 449198090Srdivacky } 450198090Srdivacky sp = rest; 451198090Srdivacky break; 452198090Srdivacky case O_PLUS: 453198090Srdivacky case O_QUEST: 454198090Srdivacky case OOR1: 455198090Srdivacky case OOR2: 456198090Srdivacky case O_CH: 457198090Srdivacky assert(nope); 458198090Srdivacky break; 459198090Srdivacky case OLPAREN: 460198090Srdivacky i = OPND(m->g->strip[ss]); 461198090Srdivacky assert(0 < i && i <= m->g->nsub); 462198090Srdivacky m->pmatch[i].rm_so = sp - m->offp; 463198090Srdivacky break; 464198090Srdivacky case ORPAREN: 465198090Srdivacky i = OPND(m->g->strip[ss]); 466198090Srdivacky assert(0 < i && i <= m->g->nsub); 467198090Srdivacky m->pmatch[i].rm_eo = sp - m->offp; 468198090Srdivacky break; 469198090Srdivacky default: /* uh oh */ 470198090Srdivacky assert(nope); 471198090Srdivacky break; 472198090Srdivacky } 473198090Srdivacky } 474198090Srdivacky 475198090Srdivacky assert(sp == stop); 476198090Srdivacky return(sp); 477198090Srdivacky} 478198090Srdivacky 479198090Srdivacky/* 480198090Srdivacky - backref - figure out what matched what, figuring in back references 481198090Srdivacky */ 482206274Srdivackystatic const char * /* == stop (success) or NULL (failure) */ 483206274Srdivackybackref(struct match *m, const char *start, const char *stop, sopno startst, 484206274Srdivacky sopno stopst, sopno lev, int rec) /* PLUS nesting level */ 485198090Srdivacky{ 486198090Srdivacky int i; 487198090Srdivacky sopno ss; /* start sop of current subRE */ 488206274Srdivacky const char *sp; /* start of string matched by it */ 489198090Srdivacky sopno ssub; /* start sop of subsubRE */ 490198090Srdivacky sopno esub; /* end sop of subsubRE */ 491206274Srdivacky const char *ssp; /* start of string matched by subsubRE */ 492206274Srdivacky const char *dp; 493198090Srdivacky size_t len; 494198090Srdivacky int hard; 495198090Srdivacky sop s; 496198090Srdivacky llvm_regoff_t offsave; 497198090Srdivacky cset *cs; 498198090Srdivacky 499198090Srdivacky AT("back", start, stop, startst, stopst); 500198090Srdivacky sp = start; 501198090Srdivacky 502198090Srdivacky /* get as far as we can with easy stuff */ 503198090Srdivacky hard = 0; 504198090Srdivacky for (ss = startst; !hard && ss < stopst; ss++) 505198090Srdivacky switch (OP(s = m->g->strip[ss])) { 506198090Srdivacky case OCHAR: 507198090Srdivacky if (sp == stop || *sp++ != (char)OPND(s)) 508198090Srdivacky return(NULL); 509198090Srdivacky break; 510198090Srdivacky case OANY: 511198090Srdivacky if (sp == stop) 512198090Srdivacky return(NULL); 513198090Srdivacky sp++; 514198090Srdivacky break; 515198090Srdivacky case OANYOF: 516198090Srdivacky cs = &m->g->sets[OPND(s)]; 517198090Srdivacky if (sp == stop || !CHIN(cs, *sp++)) 518198090Srdivacky return(NULL); 519198090Srdivacky break; 520198090Srdivacky case OBOL: 521198090Srdivacky if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) || 522198090Srdivacky (sp < m->endp && *(sp-1) == '\n' && 523198090Srdivacky (m->g->cflags®_NEWLINE)) ) 524198090Srdivacky { /* yes */ } 525198090Srdivacky else 526198090Srdivacky return(NULL); 527198090Srdivacky break; 528198090Srdivacky case OEOL: 529198090Srdivacky if ( (sp == m->endp && !(m->eflags®_NOTEOL)) || 530198090Srdivacky (sp < m->endp && *sp == '\n' && 531198090Srdivacky (m->g->cflags®_NEWLINE)) ) 532198090Srdivacky { /* yes */ } 533198090Srdivacky else 534198090Srdivacky return(NULL); 535198090Srdivacky break; 536198090Srdivacky case OBOW: 537198090Srdivacky if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) || 538198090Srdivacky (sp < m->endp && *(sp-1) == '\n' && 539198090Srdivacky (m->g->cflags®_NEWLINE)) || 540198090Srdivacky (sp > m->beginp && 541198090Srdivacky !ISWORD(*(sp-1))) ) && 542198090Srdivacky (sp < m->endp && ISWORD(*sp)) ) 543198090Srdivacky { /* yes */ } 544198090Srdivacky else 545198090Srdivacky return(NULL); 546198090Srdivacky break; 547198090Srdivacky case OEOW: 548198090Srdivacky if (( (sp == m->endp && !(m->eflags®_NOTEOL)) || 549198090Srdivacky (sp < m->endp && *sp == '\n' && 550198090Srdivacky (m->g->cflags®_NEWLINE)) || 551198090Srdivacky (sp < m->endp && !ISWORD(*sp)) ) && 552198090Srdivacky (sp > m->beginp && ISWORD(*(sp-1))) ) 553198090Srdivacky { /* yes */ } 554198090Srdivacky else 555198090Srdivacky return(NULL); 556198090Srdivacky break; 557198090Srdivacky case O_QUEST: 558198090Srdivacky break; 559198090Srdivacky case OOR1: /* matches null but needs to skip */ 560198090Srdivacky ss++; 561198090Srdivacky s = m->g->strip[ss]; 562198090Srdivacky do { 563198090Srdivacky assert(OP(s) == OOR2); 564198090Srdivacky ss += OPND(s); 565198090Srdivacky } while (OP(s = m->g->strip[ss]) != O_CH); 566198090Srdivacky /* note that the ss++ gets us past the O_CH */ 567198090Srdivacky break; 568198090Srdivacky default: /* have to make a choice */ 569198090Srdivacky hard = 1; 570198090Srdivacky break; 571198090Srdivacky } 572198090Srdivacky if (!hard) { /* that was it! */ 573198090Srdivacky if (sp != stop) 574198090Srdivacky return(NULL); 575198090Srdivacky return(sp); 576198090Srdivacky } 577198090Srdivacky ss--; /* adjust for the for's final increment */ 578198090Srdivacky 579198090Srdivacky /* the hard stuff */ 580198090Srdivacky AT("hard", sp, stop, ss, stopst); 581198090Srdivacky s = m->g->strip[ss]; 582198090Srdivacky switch (OP(s)) { 583198090Srdivacky case OBACK_: /* the vilest depths */ 584198090Srdivacky i = OPND(s); 585198090Srdivacky assert(0 < i && i <= m->g->nsub); 586198090Srdivacky if (m->pmatch[i].rm_eo == -1) 587198090Srdivacky return(NULL); 588198090Srdivacky assert(m->pmatch[i].rm_so != -1); 589198090Srdivacky len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; 590198090Srdivacky if (len == 0 && rec++ > MAX_RECURSION) 591198090Srdivacky return(NULL); 592198090Srdivacky assert(stop - m->beginp >= len); 593198090Srdivacky if (sp > stop - len) 594198090Srdivacky return(NULL); /* not enough left to match */ 595198090Srdivacky ssp = m->offp + m->pmatch[i].rm_so; 596198090Srdivacky if (memcmp(sp, ssp, len) != 0) 597198090Srdivacky return(NULL); 598198090Srdivacky while (m->g->strip[ss] != SOP(O_BACK, i)) 599198090Srdivacky ss++; 600198090Srdivacky return(backref(m, sp+len, stop, ss+1, stopst, lev, rec)); 601198090Srdivacky break; 602198090Srdivacky case OQUEST_: /* to null or not */ 603198090Srdivacky dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 604198090Srdivacky if (dp != NULL) 605198090Srdivacky return(dp); /* not */ 606198090Srdivacky return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec)); 607198090Srdivacky break; 608198090Srdivacky case OPLUS_: 609198090Srdivacky assert(m->lastpos != NULL); 610198090Srdivacky assert(lev+1 <= m->g->nplus); 611198090Srdivacky m->lastpos[lev+1] = sp; 612198090Srdivacky return(backref(m, sp, stop, ss+1, stopst, lev+1, rec)); 613198090Srdivacky break; 614198090Srdivacky case O_PLUS: 615198090Srdivacky if (sp == m->lastpos[lev]) /* last pass matched null */ 616198090Srdivacky return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); 617198090Srdivacky /* try another pass */ 618198090Srdivacky m->lastpos[lev] = sp; 619198090Srdivacky dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec); 620198090Srdivacky if (dp == NULL) 621198090Srdivacky return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); 622198090Srdivacky else 623198090Srdivacky return(dp); 624198090Srdivacky break; 625198090Srdivacky case OCH_: /* find the right one, if any */ 626198090Srdivacky ssub = ss + 1; 627198090Srdivacky esub = ss + OPND(s) - 1; 628198090Srdivacky assert(OP(m->g->strip[esub]) == OOR1); 629198090Srdivacky for (;;) { /* find first matching branch */ 630198090Srdivacky dp = backref(m, sp, stop, ssub, esub, lev, rec); 631198090Srdivacky if (dp != NULL) 632198090Srdivacky return(dp); 633198090Srdivacky /* that one missed, try next one */ 634198090Srdivacky if (OP(m->g->strip[esub]) == O_CH) 635198090Srdivacky return(NULL); /* there is none */ 636198090Srdivacky esub++; 637198090Srdivacky assert(OP(m->g->strip[esub]) == OOR2); 638198090Srdivacky ssub = esub + 1; 639198090Srdivacky esub += OPND(m->g->strip[esub]); 640198090Srdivacky if (OP(m->g->strip[esub]) == OOR2) 641198090Srdivacky esub--; 642198090Srdivacky else 643198090Srdivacky assert(OP(m->g->strip[esub]) == O_CH); 644198090Srdivacky } 645198090Srdivacky break; 646198090Srdivacky case OLPAREN: /* must undo assignment if rest fails */ 647198090Srdivacky i = OPND(s); 648198090Srdivacky assert(0 < i && i <= m->g->nsub); 649198090Srdivacky offsave = m->pmatch[i].rm_so; 650198090Srdivacky m->pmatch[i].rm_so = sp - m->offp; 651198090Srdivacky dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 652198090Srdivacky if (dp != NULL) 653198090Srdivacky return(dp); 654198090Srdivacky m->pmatch[i].rm_so = offsave; 655198090Srdivacky return(NULL); 656198090Srdivacky break; 657198090Srdivacky case ORPAREN: /* must undo assignment if rest fails */ 658198090Srdivacky i = OPND(s); 659198090Srdivacky assert(0 < i && i <= m->g->nsub); 660198090Srdivacky offsave = m->pmatch[i].rm_eo; 661198090Srdivacky m->pmatch[i].rm_eo = sp - m->offp; 662198090Srdivacky dp = backref(m, sp, stop, ss+1, stopst, lev, rec); 663198090Srdivacky if (dp != NULL) 664198090Srdivacky return(dp); 665198090Srdivacky m->pmatch[i].rm_eo = offsave; 666198090Srdivacky return(NULL); 667198090Srdivacky break; 668198090Srdivacky default: /* uh oh */ 669198090Srdivacky assert(nope); 670198090Srdivacky break; 671198090Srdivacky } 672198090Srdivacky 673198090Srdivacky /* "can't happen" */ 674198090Srdivacky assert(nope); 675198090Srdivacky /* NOTREACHED */ 676198090Srdivacky return NULL; 677198090Srdivacky} 678198090Srdivacky 679198090Srdivacky/* 680198090Srdivacky - fast - step through the string at top speed 681198090Srdivacky */ 682206274Srdivackystatic const char * /* where tentative match ended, or NULL */ 683206274Srdivackyfast(struct match *m, const char *start, const char *stop, sopno startst, 684206274Srdivacky sopno stopst) 685198090Srdivacky{ 686198090Srdivacky states st = m->st; 687198090Srdivacky states fresh = m->fresh; 688198090Srdivacky states tmp = m->tmp; 689206274Srdivacky const char *p = start; 690198090Srdivacky int c = (start == m->beginp) ? OUT : *(start-1); 691198090Srdivacky int lastc; /* previous c */ 692198090Srdivacky int flagch; 693198090Srdivacky int i; 694206274Srdivacky const char *coldp; /* last p after which no match was underway */ 695198090Srdivacky 696198090Srdivacky CLEAR(st); 697198090Srdivacky SET1(st, startst); 698198090Srdivacky st = step(m->g, startst, stopst, st, NOTHING, st); 699198090Srdivacky ASSIGN(fresh, st); 700198090Srdivacky SP("start", st, *p); 701198090Srdivacky coldp = NULL; 702198090Srdivacky for (;;) { 703198090Srdivacky /* next character */ 704198090Srdivacky lastc = c; 705198090Srdivacky c = (p == m->endp) ? OUT : *p; 706198090Srdivacky if (EQ(st, fresh)) 707198090Srdivacky coldp = p; 708198090Srdivacky 709198090Srdivacky /* is there an EOL and/or BOL between lastc and c? */ 710198090Srdivacky flagch = '\0'; 711198090Srdivacky i = 0; 712198090Srdivacky if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || 713198090Srdivacky (lastc == OUT && !(m->eflags®_NOTBOL)) ) { 714198090Srdivacky flagch = BOL; 715198090Srdivacky i = m->g->nbol; 716198090Srdivacky } 717198090Srdivacky if ( (c == '\n' && m->g->cflags®_NEWLINE) || 718198090Srdivacky (c == OUT && !(m->eflags®_NOTEOL)) ) { 719198090Srdivacky flagch = (flagch == BOL) ? BOLEOL : EOL; 720198090Srdivacky i += m->g->neol; 721198090Srdivacky } 722198090Srdivacky if (i != 0) { 723198090Srdivacky for (; i > 0; i--) 724198090Srdivacky st = step(m->g, startst, stopst, st, flagch, st); 725198090Srdivacky SP("boleol", st, c); 726198090Srdivacky } 727198090Srdivacky 728198090Srdivacky /* how about a word boundary? */ 729198090Srdivacky if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && 730198090Srdivacky (c != OUT && ISWORD(c)) ) { 731198090Srdivacky flagch = BOW; 732198090Srdivacky } 733198090Srdivacky if ( (lastc != OUT && ISWORD(lastc)) && 734198090Srdivacky (flagch == EOL || (c != OUT && !ISWORD(c))) ) { 735198090Srdivacky flagch = EOW; 736198090Srdivacky } 737198090Srdivacky if (flagch == BOW || flagch == EOW) { 738198090Srdivacky st = step(m->g, startst, stopst, st, flagch, st); 739198090Srdivacky SP("boweow", st, c); 740198090Srdivacky } 741198090Srdivacky 742198090Srdivacky /* are we done? */ 743198090Srdivacky if (ISSET(st, stopst) || p == stop) 744198090Srdivacky break; /* NOTE BREAK OUT */ 745198090Srdivacky 746198090Srdivacky /* no, we must deal with this character */ 747198090Srdivacky ASSIGN(tmp, st); 748198090Srdivacky ASSIGN(st, fresh); 749198090Srdivacky assert(c != OUT); 750198090Srdivacky st = step(m->g, startst, stopst, tmp, c, st); 751198090Srdivacky SP("aft", st, c); 752198090Srdivacky assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); 753198090Srdivacky p++; 754198090Srdivacky } 755198090Srdivacky 756198090Srdivacky assert(coldp != NULL); 757198090Srdivacky m->coldp = coldp; 758198090Srdivacky if (ISSET(st, stopst)) 759198090Srdivacky return(p+1); 760198090Srdivacky else 761198090Srdivacky return(NULL); 762198090Srdivacky} 763198090Srdivacky 764198090Srdivacky/* 765198090Srdivacky - slow - step through the string more deliberately 766198090Srdivacky */ 767206274Srdivackystatic const char * /* where it ended */ 768206274Srdivackyslow(struct match *m, const char *start, const char *stop, sopno startst, 769206274Srdivacky sopno stopst) 770198090Srdivacky{ 771198090Srdivacky states st = m->st; 772198090Srdivacky states empty = m->empty; 773198090Srdivacky states tmp = m->tmp; 774206274Srdivacky const char *p = start; 775198090Srdivacky int c = (start == m->beginp) ? OUT : *(start-1); 776198090Srdivacky int lastc; /* previous c */ 777198090Srdivacky int flagch; 778198090Srdivacky int i; 779206274Srdivacky const char *matchp; /* last p at which a match ended */ 780198090Srdivacky 781198090Srdivacky AT("slow", start, stop, startst, stopst); 782198090Srdivacky CLEAR(st); 783198090Srdivacky SET1(st, startst); 784198090Srdivacky SP("sstart", st, *p); 785198090Srdivacky st = step(m->g, startst, stopst, st, NOTHING, st); 786198090Srdivacky matchp = NULL; 787198090Srdivacky for (;;) { 788198090Srdivacky /* next character */ 789198090Srdivacky lastc = c; 790198090Srdivacky c = (p == m->endp) ? OUT : *p; 791198090Srdivacky 792198090Srdivacky /* is there an EOL and/or BOL between lastc and c? */ 793198090Srdivacky flagch = '\0'; 794198090Srdivacky i = 0; 795198090Srdivacky if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || 796198090Srdivacky (lastc == OUT && !(m->eflags®_NOTBOL)) ) { 797198090Srdivacky flagch = BOL; 798198090Srdivacky i = m->g->nbol; 799198090Srdivacky } 800198090Srdivacky if ( (c == '\n' && m->g->cflags®_NEWLINE) || 801198090Srdivacky (c == OUT && !(m->eflags®_NOTEOL)) ) { 802198090Srdivacky flagch = (flagch == BOL) ? BOLEOL : EOL; 803198090Srdivacky i += m->g->neol; 804198090Srdivacky } 805198090Srdivacky if (i != 0) { 806198090Srdivacky for (; i > 0; i--) 807198090Srdivacky st = step(m->g, startst, stopst, st, flagch, st); 808198090Srdivacky SP("sboleol", st, c); 809198090Srdivacky } 810198090Srdivacky 811198090Srdivacky /* how about a word boundary? */ 812198090Srdivacky if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) && 813198090Srdivacky (c != OUT && ISWORD(c)) ) { 814198090Srdivacky flagch = BOW; 815198090Srdivacky } 816198090Srdivacky if ( (lastc != OUT && ISWORD(lastc)) && 817198090Srdivacky (flagch == EOL || (c != OUT && !ISWORD(c))) ) { 818198090Srdivacky flagch = EOW; 819198090Srdivacky } 820198090Srdivacky if (flagch == BOW || flagch == EOW) { 821198090Srdivacky st = step(m->g, startst, stopst, st, flagch, st); 822198090Srdivacky SP("sboweow", st, c); 823198090Srdivacky } 824198090Srdivacky 825198090Srdivacky /* are we done? */ 826198090Srdivacky if (ISSET(st, stopst)) 827198090Srdivacky matchp = p; 828198090Srdivacky if (EQ(st, empty) || p == stop) 829198090Srdivacky break; /* NOTE BREAK OUT */ 830198090Srdivacky 831198090Srdivacky /* no, we must deal with this character */ 832198090Srdivacky ASSIGN(tmp, st); 833198090Srdivacky ASSIGN(st, empty); 834198090Srdivacky assert(c != OUT); 835198090Srdivacky st = step(m->g, startst, stopst, tmp, c, st); 836198090Srdivacky SP("saft", st, c); 837198090Srdivacky assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st)); 838198090Srdivacky p++; 839198090Srdivacky } 840198090Srdivacky 841198090Srdivacky return(matchp); 842198090Srdivacky} 843198090Srdivacky 844198090Srdivacky 845198090Srdivacky/* 846198090Srdivacky - step - map set of states reachable before char to set reachable after 847198090Srdivacky */ 848198090Srdivackystatic states 849198090Srdivackystep(struct re_guts *g, 850198090Srdivacky sopno start, /* start state within strip */ 851198090Srdivacky sopno stop, /* state after stop state within strip */ 852198090Srdivacky states bef, /* states reachable before */ 853198090Srdivacky int ch, /* character or NONCHAR code */ 854198090Srdivacky states aft) /* states already known reachable after */ 855198090Srdivacky{ 856198090Srdivacky cset *cs; 857198090Srdivacky sop s; 858198090Srdivacky sopno pc; 859198090Srdivacky onestate here; /* note, macros know this name */ 860198090Srdivacky sopno look; 861198090Srdivacky int i; 862198090Srdivacky 863198090Srdivacky for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) { 864198090Srdivacky s = g->strip[pc]; 865198090Srdivacky switch (OP(s)) { 866198090Srdivacky case OEND: 867198090Srdivacky assert(pc == stop-1); 868198090Srdivacky break; 869198090Srdivacky case OCHAR: 870198090Srdivacky /* only characters can match */ 871198090Srdivacky assert(!NONCHAR(ch) || ch != (char)OPND(s)); 872198090Srdivacky if (ch == (char)OPND(s)) 873198090Srdivacky FWD(aft, bef, 1); 874198090Srdivacky break; 875198090Srdivacky case OBOL: 876198090Srdivacky if (ch == BOL || ch == BOLEOL) 877198090Srdivacky FWD(aft, bef, 1); 878198090Srdivacky break; 879198090Srdivacky case OEOL: 880198090Srdivacky if (ch == EOL || ch == BOLEOL) 881198090Srdivacky FWD(aft, bef, 1); 882198090Srdivacky break; 883198090Srdivacky case OBOW: 884198090Srdivacky if (ch == BOW) 885198090Srdivacky FWD(aft, bef, 1); 886198090Srdivacky break; 887198090Srdivacky case OEOW: 888198090Srdivacky if (ch == EOW) 889198090Srdivacky FWD(aft, bef, 1); 890198090Srdivacky break; 891198090Srdivacky case OANY: 892198090Srdivacky if (!NONCHAR(ch)) 893198090Srdivacky FWD(aft, bef, 1); 894198090Srdivacky break; 895198090Srdivacky case OANYOF: 896198090Srdivacky cs = &g->sets[OPND(s)]; 897198090Srdivacky if (!NONCHAR(ch) && CHIN(cs, ch)) 898198090Srdivacky FWD(aft, bef, 1); 899198090Srdivacky break; 900198090Srdivacky case OBACK_: /* ignored here */ 901198090Srdivacky case O_BACK: 902198090Srdivacky FWD(aft, aft, 1); 903198090Srdivacky break; 904198090Srdivacky case OPLUS_: /* forward, this is just an empty */ 905198090Srdivacky FWD(aft, aft, 1); 906198090Srdivacky break; 907198090Srdivacky case O_PLUS: /* both forward and back */ 908198090Srdivacky FWD(aft, aft, 1); 909198090Srdivacky i = ISSETBACK(aft, OPND(s)); 910198090Srdivacky BACK(aft, aft, OPND(s)); 911198090Srdivacky if (!i && ISSETBACK(aft, OPND(s))) { 912198090Srdivacky /* oho, must reconsider loop body */ 913198090Srdivacky pc -= OPND(s) + 1; 914198090Srdivacky INIT(here, pc); 915198090Srdivacky } 916198090Srdivacky break; 917198090Srdivacky case OQUEST_: /* two branches, both forward */ 918198090Srdivacky FWD(aft, aft, 1); 919198090Srdivacky FWD(aft, aft, OPND(s)); 920198090Srdivacky break; 921198090Srdivacky case O_QUEST: /* just an empty */ 922198090Srdivacky FWD(aft, aft, 1); 923198090Srdivacky break; 924198090Srdivacky case OLPAREN: /* not significant here */ 925198090Srdivacky case ORPAREN: 926198090Srdivacky FWD(aft, aft, 1); 927198090Srdivacky break; 928198090Srdivacky case OCH_: /* mark the first two branches */ 929198090Srdivacky FWD(aft, aft, 1); 930198090Srdivacky assert(OP(g->strip[pc+OPND(s)]) == OOR2); 931198090Srdivacky FWD(aft, aft, OPND(s)); 932198090Srdivacky break; 933198090Srdivacky case OOR1: /* done a branch, find the O_CH */ 934198090Srdivacky if (ISSTATEIN(aft, here)) { 935198090Srdivacky for (look = 1; 936198090Srdivacky OP(s = g->strip[pc+look]) != O_CH; 937198090Srdivacky look += OPND(s)) 938198090Srdivacky assert(OP(s) == OOR2); 939198090Srdivacky FWD(aft, aft, look); 940198090Srdivacky } 941198090Srdivacky break; 942198090Srdivacky case OOR2: /* propagate OCH_'s marking */ 943198090Srdivacky FWD(aft, aft, 1); 944198090Srdivacky if (OP(g->strip[pc+OPND(s)]) != O_CH) { 945198090Srdivacky assert(OP(g->strip[pc+OPND(s)]) == OOR2); 946198090Srdivacky FWD(aft, aft, OPND(s)); 947198090Srdivacky } 948198090Srdivacky break; 949198090Srdivacky case O_CH: /* just empty */ 950198090Srdivacky FWD(aft, aft, 1); 951198090Srdivacky break; 952198090Srdivacky default: /* ooooops... */ 953198090Srdivacky assert(nope); 954198090Srdivacky break; 955198090Srdivacky } 956198090Srdivacky } 957198090Srdivacky 958198090Srdivacky return(aft); 959198090Srdivacky} 960198090Srdivacky 961198090Srdivacky#ifdef REDEBUG 962198090Srdivacky/* 963198090Srdivacky - print - print a set of states 964198090Srdivacky */ 965198090Srdivackystatic void 966198090Srdivackyprint(struct match *m, char *caption, states st, int ch, FILE *d) 967198090Srdivacky{ 968198090Srdivacky struct re_guts *g = m->g; 969198090Srdivacky int i; 970198090Srdivacky int first = 1; 971198090Srdivacky 972198090Srdivacky if (!(m->eflags®_TRACE)) 973198090Srdivacky return; 974198090Srdivacky 975198090Srdivacky (void)fprintf(d, "%s", caption); 976198090Srdivacky if (ch != '\0') 977198090Srdivacky (void)fprintf(d, " %s", pchar(ch)); 978198090Srdivacky for (i = 0; i < g->nstates; i++) 979198090Srdivacky if (ISSET(st, i)) { 980198090Srdivacky (void)fprintf(d, "%s%d", (first) ? "\t" : ", ", i); 981198090Srdivacky first = 0; 982198090Srdivacky } 983198090Srdivacky (void)fprintf(d, "\n"); 984198090Srdivacky} 985198090Srdivacky 986198090Srdivacky/* 987198090Srdivacky - at - print current situation 988198090Srdivacky */ 989198090Srdivackystatic void 990198090Srdivackyat(struct match *m, char *title, char *start, char *stop, sopno startst, 991198090Srdivacky sopno stopst) 992198090Srdivacky{ 993198090Srdivacky if (!(m->eflags®_TRACE)) 994198090Srdivacky return; 995198090Srdivacky 996198090Srdivacky (void)printf("%s %s-", title, pchar(*start)); 997198090Srdivacky (void)printf("%s ", pchar(*stop)); 998198090Srdivacky (void)printf("%ld-%ld\n", (long)startst, (long)stopst); 999198090Srdivacky} 1000198090Srdivacky 1001198090Srdivacky#ifndef PCHARDONE 1002198090Srdivacky#define PCHARDONE /* never again */ 1003198090Srdivacky/* 1004198090Srdivacky - pchar - make a character printable 1005198090Srdivacky * 1006198090Srdivacky * Is this identical to regchar() over in debug.c? Well, yes. But a 1007198090Srdivacky * duplicate here avoids having a debugging-capable regexec.o tied to 1008198090Srdivacky * a matching debug.o, and this is convenient. It all disappears in 1009198090Srdivacky * the non-debug compilation anyway, so it doesn't matter much. 1010198090Srdivacky */ 1011198090Srdivackystatic char * /* -> representation */ 1012198090Srdivackypchar(int ch) 1013198090Srdivacky{ 1014198090Srdivacky static char pbuf[10]; 1015198090Srdivacky 1016341825Sdim if (isPrint(ch) || ch == ' ') 1017198090Srdivacky (void)snprintf(pbuf, sizeof pbuf, "%c", ch); 1018198090Srdivacky else 1019198090Srdivacky (void)snprintf(pbuf, sizeof pbuf, "\\%o", ch); 1020198090Srdivacky return(pbuf); 1021198090Srdivacky} 1022198090Srdivacky#endif 1023198090Srdivacky#endif 1024198090Srdivacky 1025198090Srdivacky#undef matcher 1026198090Srdivacky#undef fast 1027198090Srdivacky#undef slow 1028198090Srdivacky#undef dissect 1029198090Srdivacky#undef backref 1030198090Srdivacky#undef step 1031198090Srdivacky#undef print 1032198090Srdivacky#undef at 1033198090Srdivacky#undef match 1034198090Srdivacky#undef nope 1035