lib/Support/regengine.inc

   1 /*-
   2  * This code is derived from OpenBSD's libc/regex, original license follows:
   3  *
   4  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
   5  * Copyright (c) 1992, 1993, 1994
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Henry Spencer.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  *
  35  *      @(#)engine.c    8.5 (Berkeley) 3/20/94
  36  */
  37
  38 /*
  39  * The matching engine and friends.  This file is #included by regexec.c
  40  * after suitable #defines of a variety of macros used herein, so that
  41  * different state representations can be used without duplicating masses
  42  * of code.
  43  */
  44
  45 #ifdef SNAMES
  46 #define matcher smatcher
  47 #define fast    sfast
  48 #define slow    sslow
  49 #define dissect sdissect
  50 #define backref sbackref
  51 #define step    sstep
  52 #define print   sprint
  53 #define at      sat
  54 #define match   smat
  55 #define nope    snope
  56 #endif
  57 #ifdef LNAMES
  58 #define matcher lmatcher
  59 #define fast    lfast
  60 #define slow    lslow
  61 #define dissect ldissect
  62 #define backref lbackref
  63 #define step    lstep
  64 #define print   lprint
  65 #define at      lat
  66 #define match   lmat
  67 #define nope    lnope
  68 #endif
  69
  70 /* another structure passed up and down to avoid zillions of parameters */
  71 struct match {
  72         struct re_guts *g;
  73         int eflags;
  74         llvm_regmatch_t *pmatch;        /* [nsub+1] (0 element unused) */
  75         char *offp;             /* offsets work from here */
  76         char *beginp;           /* start of string -- virtual NUL precedes */
  77         char *endp;             /* end of string -- virtual NUL here */
  78         char *coldp;            /* can be no match starting before here */
  79         char **lastpos;         /* [nplus+1] */
  80         STATEVARS;
  81         states st;              /* current states */
  82         states fresh;           /* states for a fresh start */
  83         states tmp;             /* temporary */
  84         states empty;           /* empty set of states */
  85 };
  86
  87 static int matcher(struct re_guts *, char *, size_t, llvm_regmatch_t[], int);
  88 static char *dissect(struct match *, char *, char *, sopno, sopno);
  89 static char *backref(struct match *, char *, char *, sopno, sopno, sopno, int);
  90 static char *fast(struct match *, char *, char *, sopno, sopno);
  91 static char *slow(struct match *, char *, char *, sopno, sopno);
  92 static states step(struct re_guts *, sopno, sopno, states, int, states);
  93 #define MAX_RECURSION   100
  94 #define BOL     (OUT+1)
  95 #define EOL     (BOL+1)
  96 #define BOLEOL  (BOL+2)
  97 #define NOTHING (BOL+3)
  98 #define BOW     (BOL+4)
  99 #define EOW     (BOL+5)
 100 #define CODEMAX (BOL+5)         /* highest code used */
 101 #define NONCHAR(c)      ((c) > CHAR_MAX)
 102 #define NNONCHAR        (CODEMAX-CHAR_MAX)
 103 #ifdef REDEBUG
 104 static void print(struct match *, char *, states, int, FILE *);
 105 #endif
 106 #ifdef REDEBUG
 107 static void at(struct match *, char *, char *, char *, sopno, sopno);
 108 #endif
 109 #ifdef REDEBUG
 110 static char *pchar(int);
 111 #endif
 112
 113 #ifdef REDEBUG
 114 #define SP(t, s, c)     print(m, t, s, c, stdout)
 115 #define AT(t, p1, p2, s1, s2)   at(m, t, p1, p2, s1, s2)
 116 #define NOTE(str)       { if (m->eflags&REG_TRACE) (void)printf("=%s\n", (str)); }
 117 static int nope = 0;
 118 #else
 119 #define SP(t, s, c)     /* nothing */
 120 #define AT(t, p1, p2, s1, s2)   /* nothing */
 121 #define NOTE(s) /* nothing */
 122 #endif
 123
 124 /*
 125  - matcher - the actual matching engine
 126  */
 127 static int                      /* 0 success, REG_NOMATCH failure */
 128 matcher(struct re_guts *g, char *string, size_t nmatch, llvm_regmatch_t pmatch[],
 129     int eflags)
 130 {
 131         char *endp;
 132         size_t i;
 133         struct match mv;
 134         struct match *m = &mv;
 135         char *dp;
 136         const sopno gf = g->firststate+1;       /* +1 for OEND */
 137         const sopno gl = g->laststate;
 138         char *start;
 139         char *stop;
 140
 141         /* simplify the situation where possible */
 142         if (g->cflags&REG_NOSUB)
 143                 nmatch = 0;
 144         if (eflags&REG_STARTEND) {
 145                 start = string + pmatch[0].rm_so;
 146                 stop = string + pmatch[0].rm_eo;
 147         } else {
 148                 start = string;
 149                 stop = start + strlen(start);
 150         }
 151         if (stop < start)
 152                 return(REG_INVARG);
 153
 154         /* prescreening; this does wonders for this rather slow code */
 155         if (g->must != NULL) {
 156                 for (dp = start; dp < stop; dp++)
 157                         if (*dp == g->must[0] && stop - dp >= g->mlen &&
 158                                 memcmp(dp, g->must, (size_t)g->mlen) == 0)
 159                                 break;
 160                 if (dp == stop)         /* we didn't find g->must */
 161                         return(REG_NOMATCH);
 162         }
 163
 164         /* match struct setup */
 165         m->g = g;
 166         m->eflags = eflags;
 167         m->pmatch = NULL;
 168         m->lastpos = NULL;
 169         m->offp = string;
 170         m->beginp = start;
 171         m->endp = stop;
 172         STATESETUP(m, 4);
 173         SETUP(m->st);
 174         SETUP(m->fresh);
 175         SETUP(m->tmp);
 176         SETUP(m->empty);
 177         CLEAR(m->empty);
 178
 179         /* this loop does only one repetition except for backrefs */
 180         for (;;) {
 181                 endp = fast(m, start, stop, gf, gl);
 182                 if (endp == NULL) {             /* a miss */
 183                         free(m->pmatch);
 184                         free(m->lastpos);
 185                         STATETEARDOWN(m);
 186                         return(REG_NOMATCH);
 187                 }
 188                 if (nmatch == 0 && !g->backrefs)
 189                         break;          /* no further info needed */
 190
 191                 /* where? */
 192                 assert(m->coldp != NULL);
 193                 for (;;) {
 194                         NOTE("finding start");
 195                         endp = slow(m, m->coldp, stop, gf, gl);
 196                         if (endp != NULL)
 197                                 break;
 198                         assert(m->coldp < m->endp);
 199                         m->coldp++;
 200                 }
 201                 if (nmatch == 1 && !g->backrefs)
 202                         break;          /* no further info needed */
 203
 204                 /* oh my, he wants the subexpressions... */
 205                 if (m->pmatch == NULL)
 206                         m->pmatch = (llvm_regmatch_t *)malloc((m->g->nsub + 1) *
 207                                                         sizeof(llvm_regmatch_t));
 208                 if (m->pmatch == NULL) {
 209                         STATETEARDOWN(m);
 210                         return(REG_ESPACE);
 211                 }
 212                 for (i = 1; i <= m->g->nsub; i++)
 213                         m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
 214                 if (!g->backrefs && !(m->eflags&REG_BACKR)) {
 215                         NOTE("dissecting");
 216                         dp = dissect(m, m->coldp, endp, gf, gl);
 217                 } else {
 218                         if (g->nplus > 0 && m->lastpos == NULL)
 219                                 m->lastpos = (char **)malloc((g->nplus+1) *
 220                                                         sizeof(char *));
 221                         if (g->nplus > 0 && m->lastpos == NULL) {
 222                                 free(m->pmatch);
 223                                 STATETEARDOWN(m);
 224                                 return(REG_ESPACE);
 225                         }
 226                         NOTE("backref dissect");
 227                         dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 228                 }
 229                 if (dp != NULL)
 230                         break;
 231
 232                 /* uh-oh... we couldn't find a subexpression-level match */
 233                 assert(g->backrefs);    /* must be back references doing it */
 234                 assert(g->nplus == 0 || m->lastpos != NULL);
 235                 for (;;) {
 236                         if (dp != NULL || endp <= m->coldp)
 237                                 break;          /* defeat */
 238                         NOTE("backoff");
 239                         endp = slow(m, m->coldp, endp-1, gf, gl);
 240                         if (endp == NULL)
 241                                 break;          /* defeat */
 242                         /* try it on a shorter possibility */
 243 #ifndef NDEBUG
 244                         for (i = 1; i <= m->g->nsub; i++) {
 245                                 assert(m->pmatch[i].rm_so == -1);
 246                                 assert(m->pmatch[i].rm_eo == -1);
 247                         }
 248 #endif
 249                         NOTE("backoff dissect");
 250                         dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 251                 }
 252                 assert(dp == NULL || dp == endp);
 253                 if (dp != NULL)         /* found a shorter one */
 254                         break;
 255
 256                 /* despite initial appearances, there is no match here */
 257                 NOTE("false alarm");
 258                 if (m->coldp == stop)
 259                         break;
 260                 start = m->coldp + 1;   /* recycle starting later */
 261         }
 262
 263         /* fill in the details if requested */
 264         if (nmatch > 0) {
 265                 pmatch[0].rm_so = m->coldp - m->offp;
 266                 pmatch[0].rm_eo = endp - m->offp;
 267         }
 268         if (nmatch > 1) {
 269                 assert(m->pmatch != NULL);
 270                 for (i = 1; i < nmatch; i++)
 271                         if (i <= m->g->nsub)
 272                                 pmatch[i] = m->pmatch[i];
 273                         else {
 274                                 pmatch[i].rm_so = -1;
 275                                 pmatch[i].rm_eo = -1;
 276                         }
 277         }
 278
 279         if (m->pmatch != NULL)
 280                 free((char *)m->pmatch);
 281         if (m->lastpos != NULL)
 282                 free((char *)m->lastpos);
 283         STATETEARDOWN(m);
 284         return(0);
 285 }
 286
 287 /*
 288  - dissect - figure out what matched what, no back references
 289  */
 290 static char *                   /* == stop (success) always */
 291 dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 292 {
 293         int i;
 294         sopno ss;       /* start sop of current subRE */
 295         sopno es;       /* end sop of current subRE */
 296         char *sp;       /* start of string matched by it */
 297         char *stp;      /* string matched by it cannot pass here */
 298         char *rest;     /* start of rest of string */
 299         char *tail;     /* string unmatched by rest of RE */
 300         sopno ssub;     /* start sop of subsubRE */
 301         sopno esub;     /* end sop of subsubRE */
 302         char *ssp;      /* start of string matched by subsubRE */
 303         char *sep;      /* end of string matched by subsubRE */
 304         char *oldssp;   /* previous ssp */
 305
 306         AT("diss", start, stop, startst, stopst);
 307         sp = start;
 308         for (ss = startst; ss < stopst; ss = es) {
 309                 /* identify end of subRE */
 310                 es = ss;
 311                 switch (OP(m->g->strip[es])) {
 312                 case OPLUS_:
 313                 case OQUEST_:
 314                         es += OPND(m->g->strip[es]);
 315                         break;
 316                 case OCH_:
 317                         while (OP(m->g->strip[es]) != O_CH)
 318                                 es += OPND(m->g->strip[es]);
 319                         break;
 320                 }
 321                 es++;
 322
 323                 /* figure out what it matched */
 324                 switch (OP(m->g->strip[ss])) {
 325                 case OEND:
 326                         assert(nope);
 327                         break;
 328                 case OCHAR:
 329                         sp++;
 330                         break;
 331                 case OBOL:
 332                 case OEOL:
 333                 case OBOW:
 334                 case OEOW:
 335                         break;
 336                 case OANY:
 337                 case OANYOF:
 338                         sp++;
 339                         break;
 340                 case OBACK_:
 341                 case O_BACK:
 342                         assert(nope);
 343                         break;
 344                 /* cases where length of match is hard to find */
 345                 case OQUEST_:
 346                         stp = stop;
 347                         for (;;) {
 348                                 /* how long could this one be? */
 349                                 rest = slow(m, sp, stp, ss, es);
 350                                 assert(rest != NULL);   /* it did match */
 351                                 /* could the rest match the rest? */
 352                                 tail = slow(m, rest, stop, es, stopst);
 353                                 if (tail == stop)
 354                                         break;          /* yes! */
 355                                 /* no -- try a shorter match for this one */
 356                                 stp = rest - 1;
 357                                 assert(stp >= sp);      /* it did work */
 358                         }
 359                         ssub = ss + 1;
 360                         esub = es - 1;
 361                         /* did innards match? */
 362                         if (slow(m, sp, rest, ssub, esub) != NULL) {
 363                                 char *dp = dissect(m, sp, rest, ssub, esub);
 364                                 (void)dp; /* avoid warning if assertions off */
 365                                 assert(dp == rest);
 366                         } else          /* no */
 367                                 assert(sp == rest);
 368                         sp = rest;
 369                         break;
 370                 case OPLUS_:
 371                         stp = stop;
 372                         for (;;) {
 373                                 /* how long could this one be? */
 374                                 rest = slow(m, sp, stp, ss, es);
 375                                 assert(rest != NULL);   /* it did match */
 376                                 /* could the rest match the rest? */
 377                                 tail = slow(m, rest, stop, es, stopst);
 378                                 if (tail == stop)
 379                                         break;          /* yes! */
 380                                 /* no -- try a shorter match for this one */
 381                                 stp = rest - 1;
 382                                 assert(stp >= sp);      /* it did work */
 383                         }
 384                         ssub = ss + 1;
 385                         esub = es - 1;
 386                         ssp = sp;
 387                         oldssp = ssp;
 388                         for (;;) {      /* find last match of innards */
 389                                 sep = slow(m, ssp, rest, ssub, esub);
 390                                 if (sep == NULL || sep == ssp)
 391                                         break;  /* failed or matched null */
 392                                 oldssp = ssp;   /* on to next try */
 393                                 ssp = sep;
 394                         }
 395                         if (sep == NULL) {
 396                                 /* last successful match */
 397                                 sep = ssp;
 398                                 ssp = oldssp;
 399                         }
 400                         assert(sep == rest);    /* must exhaust substring */
 401                         assert(slow(m, ssp, sep, ssub, esub) == rest);
 402                         {
 403                                 char *dp = dissect(m, ssp, sep, ssub, esub);
 404                                 (void)dp; /* avoid warning if assertions off */
 405                                 assert(dp == sep);
 406                         }
 407                         sp = rest;
 408                         break;
 409                 case OCH_:
 410                         stp = stop;
 411                         for (;;) {
 412                                 /* how long could this one be? */
 413                                 rest = slow(m, sp, stp, ss, es);
 414                                 assert(rest != NULL);   /* it did match */
 415                                 /* could the rest match the rest? */
 416                                 tail = slow(m, rest, stop, es, stopst);
 417                                 if (tail == stop)
 418                                         break;          /* yes! */
 419                                 /* no -- try a shorter match for this one */
 420                                 stp = rest - 1;
 421                                 assert(stp >= sp);      /* it did work */
 422                         }
 423                         ssub = ss + 1;
 424                         esub = ss + OPND(m->g->strip[ss]) - 1;
 425                         assert(OP(m->g->strip[esub]) == OOR1);
 426                         for (;;) {      /* find first matching branch */
 427                                 if (slow(m, sp, rest, ssub, esub) == rest)
 428                                         break;  /* it matched all of it */
 429                                 /* that one missed, try next one */
 430                                 assert(OP(m->g->strip[esub]) == OOR1);
 431                                 esub++;
 432                                 assert(OP(m->g->strip[esub]) == OOR2);
 433                                 ssub = esub + 1;
 434                                 esub += OPND(m->g->strip[esub]);
 435                                 if (OP(m->g->strip[esub]) == OOR2)
 436                                         esub--;
 437                                 else
 438                                         assert(OP(m->g->strip[esub]) == O_CH);
 439                         }
 440                         {
 441                                 char *dp = dissect(m, sp, rest, ssub, esub);
 442                                 (void)dp; /* avoid warning if assertions off */
 443                                 assert(dp == rest);
 444                         }
 445                         sp = rest;
 446                         break;
 447                 case O_PLUS:
 448                 case O_QUEST:
 449                 case OOR1:
 450                 case OOR2:
 451                 case O_CH:
 452                         assert(nope);
 453                         break;
 454                 case OLPAREN:
 455                         i = OPND(m->g->strip[ss]);
 456                         assert(0 < i && i <= m->g->nsub);
 457                         m->pmatch[i].rm_so = sp - m->offp;
 458                         break;
 459                 case ORPAREN:
 460                         i = OPND(m->g->strip[ss]);
 461                         assert(0 < i && i <= m->g->nsub);
 462                         m->pmatch[i].rm_eo = sp - m->offp;
 463                         break;
 464                 default:                /* uh oh */
 465                         assert(nope);
 466                         break;
 467                 }
 468         }
 469
 470         assert(sp == stop);
 471         return(sp);
 472 }
 473
 474 /*
 475  - backref - figure out what matched what, figuring in back references
 476  */
 477 static char *                   /* == stop (success) or NULL (failure) */
 478 backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 479     sopno lev, int rec)                 /* PLUS nesting level */
 480 {
 481         int i;
 482         sopno ss;       /* start sop of current subRE */
 483         char *sp;       /* start of string matched by it */
 484         sopno ssub;     /* start sop of subsubRE */
 485         sopno esub;     /* end sop of subsubRE */
 486         char *ssp;      /* start of string matched by subsubRE */
 487         char *dp;
 488         size_t len;
 489         int hard;
 490         sop s;
 491         llvm_regoff_t offsave;
 492         cset *cs;
 493
 494         AT("back", start, stop, startst, stopst);
 495         sp = start;
 496
 497         /* get as far as we can with easy stuff */
 498         hard = 0;
 499         for (ss = startst; !hard && ss < stopst; ss++)
 500                 switch (OP(s = m->g->strip[ss])) {
 501                 case OCHAR:
 502                         if (sp == stop || *sp++ != (char)OPND(s))
 503                                 return(NULL);
 504                         break;
 505                 case OANY:
 506                         if (sp == stop)
 507                                 return(NULL);
 508                         sp++;
 509                         break;
 510                 case OANYOF:
 511                         cs = &m->g->sets[OPND(s)];
 512                         if (sp == stop || !CHIN(cs, *sp++))
 513                                 return(NULL);
 514                         break;
 515                 case OBOL:
 516                         if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 517                                         (sp < m->endp && *(sp-1) == '\n' &&
 518                                                 (m->g->cflags&REG_NEWLINE)) )
 519                                 { /* yes */ }
 520                         else
 521                                 return(NULL);
 522                         break;
 523                 case OEOL:
 524                         if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 525                                         (sp < m->endp && *sp == '\n' &&
 526                                                 (m->g->cflags&REG_NEWLINE)) )
 527                                 { /* yes */ }
 528                         else
 529                                 return(NULL);
 530                         break;
 531                 case OBOW:
 532                         if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 533                                         (sp < m->endp && *(sp-1) == '\n' &&
 534                                                 (m->g->cflags&REG_NEWLINE)) ||
 535                                         (sp > m->beginp &&
 536                                                         !ISWORD(*(sp-1))) ) &&
 537                                         (sp < m->endp && ISWORD(*sp)) )
 538                                 { /* yes */ }
 539                         else
 540                                 return(NULL);
 541                         break;
 542                 case OEOW:
 543                         if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 544                                         (sp < m->endp && *sp == '\n' &&
 545                                                 (m->g->cflags&REG_NEWLINE)) ||
 546                                         (sp < m->endp && !ISWORD(*sp)) ) &&
 547                                         (sp > m->beginp && ISWORD(*(sp-1))) )
 548                                 { /* yes */ }
 549                         else
 550                                 return(NULL);
 551                         break;
 552                 case O_QUEST:
 553                         break;
 554                 case OOR1:      /* matches null but needs to skip */
 555                         ss++;
 556                         s = m->g->strip[ss];
 557                         do {
 558                                 assert(OP(s) == OOR2);
 559                                 ss += OPND(s);
 560                         } while (OP(s = m->g->strip[ss]) != O_CH);
 561                         /* note that the ss++ gets us past the O_CH */
 562                         break;
 563                 default:        /* have to make a choice */
 564                         hard = 1;
 565                         break;
 566                 }
 567         if (!hard) {            /* that was it! */
 568                 if (sp != stop)
 569                         return(NULL);
 570                 return(sp);
 571         }
 572         ss--;                   /* adjust for the for's final increment */
 573
 574         /* the hard stuff */
 575         AT("hard", sp, stop, ss, stopst);
 576         s = m->g->strip[ss];
 577         switch (OP(s)) {
 578         case OBACK_:            /* the vilest depths */
 579                 i = OPND(s);
 580                 assert(0 < i && i <= m->g->nsub);
 581                 if (m->pmatch[i].rm_eo == -1)
 582                         return(NULL);
 583                 assert(m->pmatch[i].rm_so != -1);
 584                 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
 585                 if (len == 0 && rec++ > MAX_RECURSION)
 586                         return(NULL);
 587                 assert(stop - m->beginp >= len);
 588                 if (sp > stop - len)
 589                         return(NULL);   /* not enough left to match */
 590                 ssp = m->offp + m->pmatch[i].rm_so;
 591                 if (memcmp(sp, ssp, len) != 0)
 592                         return(NULL);
 593                 while (m->g->strip[ss] != SOP(O_BACK, i))
 594                         ss++;
 595                 return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
 596                 break;
 597         case OQUEST_:           /* to null or not */
 598                 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 599                 if (dp != NULL)
 600                         return(dp);     /* not */
 601                 return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
 602                 break;
 603         case OPLUS_:
 604                 assert(m->lastpos != NULL);
 605                 assert(lev+1 <= m->g->nplus);
 606                 m->lastpos[lev+1] = sp;
 607                 return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
 608                 break;
 609         case O_PLUS:
 610                 if (sp == m->lastpos[lev])      /* last pass matched null */
 611                         return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 612                 /* try another pass */
 613                 m->lastpos[lev] = sp;
 614                 dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
 615                 if (dp == NULL)
 616                         return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 617                 else
 618                         return(dp);
 619                 break;
 620         case OCH_:              /* find the right one, if any */
 621                 ssub = ss + 1;
 622                 esub = ss + OPND(s) - 1;
 623                 assert(OP(m->g->strip[esub]) == OOR1);
 624                 for (;;) {      /* find first matching branch */
 625                         dp = backref(m, sp, stop, ssub, esub, lev, rec);
 626                         if (dp != NULL)
 627                                 return(dp);
 628                         /* that one missed, try next one */
 629                         if (OP(m->g->strip[esub]) == O_CH)
 630                                 return(NULL);   /* there is none */
 631                         esub++;
 632                         assert(OP(m->g->strip[esub]) == OOR2);
 633                         ssub = esub + 1;
 634                         esub += OPND(m->g->strip[esub]);
 635                         if (OP(m->g->strip[esub]) == OOR2)
 636                                 esub--;
 637                         else
 638                                 assert(OP(m->g->strip[esub]) == O_CH);
 639                 }
 640                 break;
 641         case OLPAREN:           /* must undo assignment if rest fails */
 642                 i = OPND(s);
 643                 assert(0 < i && i <= m->g->nsub);
 644                 offsave = m->pmatch[i].rm_so;
 645                 m->pmatch[i].rm_so = sp - m->offp;
 646                 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 647                 if (dp != NULL)
 648                         return(dp);
 649                 m->pmatch[i].rm_so = offsave;
 650                 return(NULL);
 651                 break;
 652         case ORPAREN:           /* must undo assignment if rest fails */
 653                 i = OPND(s);
 654                 assert(0 < i && i <= m->g->nsub);
 655                 offsave = m->pmatch[i].rm_eo;
 656                 m->pmatch[i].rm_eo = sp - m->offp;
 657                 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 658                 if (dp != NULL)
 659                         return(dp);
 660                 m->pmatch[i].rm_eo = offsave;
 661                 return(NULL);
 662                 break;
 663         default:                /* uh oh */
 664                 assert(nope);
 665                 break;
 666         }
 667
 668         /* "can't happen" */
 669         assert(nope);
 670         /* NOTREACHED */
 671         return NULL;
 672 }
 673
 674 /*
 675  - fast - step through the string at top speed
 676  */
 677 static char *                   /* where tentative match ended, or NULL */
 678 fast(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 679 {
 680         states st = m->st;
 681         states fresh = m->fresh;
 682         states tmp = m->tmp;
 683         char *p = start;
 684         int c = (start == m->beginp) ? OUT : *(start-1);
 685         int lastc;      /* previous c */
 686         int flagch;
 687         int i;
 688         char *coldp;    /* last p after which no match was underway */
 689
 690         CLEAR(st);
 691         SET1(st, startst);
 692         st = step(m->g, startst, stopst, st, NOTHING, st);
 693         ASSIGN(fresh, st);
 694         SP("start", st, *p);
 695         coldp = NULL;
 696         for (;;) {
 697                 /* next character */
 698                 lastc = c;
 699                 c = (p == m->endp) ? OUT : *p;
 700                 if (EQ(st, fresh))
 701                         coldp = p;
 702
 703                 /* is there an EOL and/or BOL between lastc and c? */
 704                 flagch = '\0';
 705                 i = 0;
 706                 if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 707                                 (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 708                         flagch = BOL;
 709                         i = m->g->nbol;
 710                 }
 711                 if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 712                                 (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 713                         flagch = (flagch == BOL) ? BOLEOL : EOL;
 714                         i += m->g->neol;
 715                 }
 716                 if (i != 0) {
 717                         for (; i > 0; i--)
 718                                 st = step(m->g, startst, stopst, st, flagch, st);
 719                         SP("boleol", st, c);
 720                 }
 721
 722                 /* how about a word boundary? */
 723                 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 724                                         (c != OUT && ISWORD(c)) ) {
 725                         flagch = BOW;
 726                 }
 727                 if ( (lastc != OUT && ISWORD(lastc)) &&
 728                                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 729                         flagch = EOW;
 730                 }
 731                 if (flagch == BOW || flagch == EOW) {
 732                         st = step(m->g, startst, stopst, st, flagch, st);
 733                         SP("boweow", st, c);
 734                 }
 735
 736                 /* are we done? */
 737                 if (ISSET(st, stopst) || p == stop)
 738                         break;          /* NOTE BREAK OUT */
 739
 740                 /* no, we must deal with this character */
 741                 ASSIGN(tmp, st);
 742                 ASSIGN(st, fresh);
 743                 assert(c != OUT);
 744                 st = step(m->g, startst, stopst, tmp, c, st);
 745                 SP("aft", st, c);
 746                 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 747                 p++;
 748         }
 749
 750         assert(coldp != NULL);
 751         m->coldp = coldp;
 752         if (ISSET(st, stopst))
 753                 return(p+1);
 754         else
 755                 return(NULL);
 756 }
 757
 758 /*
 759  - slow - step through the string more deliberately
 760  */
 761 static char *                   /* where it ended */
 762 slow(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 763 {
 764         states st = m->st;
 765         states empty = m->empty;
 766         states tmp = m->tmp;
 767         char *p = start;
 768         int c = (start == m->beginp) ? OUT : *(start-1);
 769         int lastc;      /* previous c */
 770         int flagch;
 771         int i;
 772         char *matchp;   /* last p at which a match ended */
 773
 774         AT("slow", start, stop, startst, stopst);
 775         CLEAR(st);
 776         SET1(st, startst);
 777         SP("sstart", st, *p);
 778         st = step(m->g, startst, stopst, st, NOTHING, st);
 779         matchp = NULL;
 780         for (;;) {
 781                 /* next character */
 782                 lastc = c;
 783                 c = (p == m->endp) ? OUT : *p;
 784
 785                 /* is there an EOL and/or BOL between lastc and c? */
 786                 flagch = '\0';
 787                 i = 0;
 788                 if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 789                                 (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 790                         flagch = BOL;
 791                         i = m->g->nbol;
 792                 }
 793                 if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 794                                 (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 795                         flagch = (flagch == BOL) ? BOLEOL : EOL;
 796                         i += m->g->neol;
 797                 }
 798                 if (i != 0) {
 799                         for (; i > 0; i--)
 800                                 st = step(m->g, startst, stopst, st, flagch, st);
 801                         SP("sboleol", st, c);
 802                 }
 803
 804                 /* how about a word boundary? */
 805                 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 806                                         (c != OUT && ISWORD(c)) ) {
 807                         flagch = BOW;
 808                 }
 809                 if ( (lastc != OUT && ISWORD(lastc)) &&
 810                                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 811                         flagch = EOW;
 812                 }
 813                 if (flagch == BOW || flagch == EOW) {
 814                         st = step(m->g, startst, stopst, st, flagch, st);
 815                         SP("sboweow", st, c);
 816                 }
 817
 818                 /* are we done? */
 819                 if (ISSET(st, stopst))
 820                         matchp = p;
 821                 if (EQ(st, empty) || p == stop)
 822                         break;          /* NOTE BREAK OUT */
 823
 824                 /* no, we must deal with this character */
 825                 ASSIGN(tmp, st);
 826                 ASSIGN(st, empty);
 827                 assert(c != OUT);
 828                 st = step(m->g, startst, stopst, tmp, c, st);
 829                 SP("saft", st, c);
 830                 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 831                 p++;
 832         }
 833
 834         return(matchp);
 835 }
 836
 837
 838 /*
 839  - step - map set of states reachable before char to set reachable after
 840  */
 841 static states
 842 step(struct re_guts *g,
 843     sopno start,                /* start state within strip */
 844     sopno stop,                 /* state after stop state within strip */
 845     states bef,                 /* states reachable before */
 846     int ch,                     /* character or NONCHAR code */
 847     states aft)                 /* states already known reachable after */
 848 {
 849         cset *cs;
 850         sop s;
 851         sopno pc;
 852         onestate here;          /* note, macros know this name */
 853         sopno look;
 854         int i;
 855
 856         for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
 857                 s = g->strip[pc];
 858                 switch (OP(s)) {
 859                 case OEND:
 860                         assert(pc == stop-1);
 861                         break;
 862                 case OCHAR:
 863                         /* only characters can match */
 864                         assert(!NONCHAR(ch) || ch != (char)OPND(s));
 865                         if (ch == (char)OPND(s))
 866                                 FWD(aft, bef, 1);
 867                         break;
 868                 case OBOL:
 869                         if (ch == BOL || ch == BOLEOL)
 870                                 FWD(aft, bef, 1);
 871                         break;
 872                 case OEOL:
 873                         if (ch == EOL || ch == BOLEOL)
 874                                 FWD(aft, bef, 1);
 875                         break;
 876                 case OBOW:
 877                         if (ch == BOW)
 878                                 FWD(aft, bef, 1);
 879                         break;
 880                 case OEOW:
 881                         if (ch == EOW)
 882                                 FWD(aft, bef, 1);
 883                         break;
 884                 case OANY:
 885                         if (!NONCHAR(ch))
 886                                 FWD(aft, bef, 1);
 887                         break;
 888                 case OANYOF:
 889                         cs = &g->sets[OPND(s)];
 890                         if (!NONCHAR(ch) && CHIN(cs, ch))
 891                                 FWD(aft, bef, 1);
 892                         break;
 893                 case OBACK_:            /* ignored here */
 894                 case O_BACK:
 895                         FWD(aft, aft, 1);
 896                         break;
 897                 case OPLUS_:            /* forward, this is just an empty */
 898                         FWD(aft, aft, 1);
 899                         break;
 900                 case O_PLUS:            /* both forward and back */
 901                         FWD(aft, aft, 1);
 902                         i = ISSETBACK(aft, OPND(s));
 903                         BACK(aft, aft, OPND(s));
 904                         if (!i && ISSETBACK(aft, OPND(s))) {
 905                                 /* oho, must reconsider loop body */
 906                                 pc -= OPND(s) + 1;
 907                                 INIT(here, pc);
 908                         }
 909                         break;
 910                 case OQUEST_:           /* two branches, both forward */
 911                         FWD(aft, aft, 1);
 912                         FWD(aft, aft, OPND(s));
 913                         break;
 914                 case O_QUEST:           /* just an empty */
 915                         FWD(aft, aft, 1);
 916                         break;
 917                 case OLPAREN:           /* not significant here */
 918                 case ORPAREN:
 919                         FWD(aft, aft, 1);
 920                         break;
 921                 case OCH_:              /* mark the first two branches */
 922                         FWD(aft, aft, 1);
 923                         assert(OP(g->strip[pc+OPND(s)]) == OOR2);
 924                         FWD(aft, aft, OPND(s));
 925                         break;
 926                 case OOR1:              /* done a branch, find the O_CH */
 927                         if (ISSTATEIN(aft, here)) {
 928                                 for (look = 1;
 929                                                 OP(s = g->strip[pc+look]) != O_CH;
 930                                                 look += OPND(s))
 931                                         assert(OP(s) == OOR2);
 932                                 FWD(aft, aft, look);
 933                         }
 934                         break;
 935                 case OOR2:              /* propagate OCH_'s marking */
 936                         FWD(aft, aft, 1);
 937                         if (OP(g->strip[pc+OPND(s)]) != O_CH) {
 938                                 assert(OP(g->strip[pc+OPND(s)]) == OOR2);
 939                                 FWD(aft, aft, OPND(s));
 940                         }
 941                         break;
 942                 case O_CH:              /* just empty */
 943                         FWD(aft, aft, 1);
 944                         break;
 945                 default:                /* ooooops... */
 946                         assert(nope);
 947                         break;
 948                 }
 949         }
 950
 951         return(aft);
 952 }
 953
 954 #ifdef REDEBUG
 955 /*
 956  - print - print a set of states
 957  */
 958 static void
 959 print(struct match *m, char *caption, states st, int ch, FILE *d)
 960 {
 961         struct re_guts *g = m->g;
 962         int i;
 963         int first = 1;
 964
 965         if (!(m->eflags&REG_TRACE))
 966                 return;
 967
 968         (void)fprintf(d, "%s", caption);
 969         if (ch != '\0')
 970                 (void)fprintf(d, " %s", pchar(ch));
 971         for (i = 0; i < g->nstates; i++)
 972                 if (ISSET(st, i)) {
 973                         (void)fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
 974                         first = 0;
 975                 }
 976         (void)fprintf(d, "\n");
 977 }
 978
 979 /*
 980  - at - print current situation
 981  */
 982 static void
 983 at(struct match *m, char *title, char *start, char *stop, sopno startst,
 984     sopno stopst)
 985 {
 986         if (!(m->eflags&REG_TRACE))
 987                 return;
 988
 989         (void)printf("%s %s-", title, pchar(*start));
 990         (void)printf("%s ", pchar(*stop));
 991         (void)printf("%ld-%ld\n", (long)startst, (long)stopst);
 992 }
 993
 994 #ifndef PCHARDONE
 995 #define PCHARDONE       /* never again */
 996 /*
 997  - pchar - make a character printable
 998  *
 999  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
1000  * duplicate here avoids having a debugging-capable regexec.o tied to
1001  * a matching debug.o, and this is convenient.  It all disappears in
1002  * the non-debug compilation anyway, so it doesn't matter much.
1003  */
1004 static char *                   /* -> representation */
1005 pchar(int ch)
1006 {
1007         static char pbuf[10];
1008
1009         if (isprint(ch) || ch == ' ')
1010                 (void)snprintf(pbuf, sizeof pbuf, "%c", ch);
1011         else
1012                 (void)snprintf(pbuf, sizeof pbuf, "\\%o", ch);
1013         return(pbuf);
1014 }
1015 #endif
1016 #endif
1017
1018 #undef  matcher
1019 #undef  fast
1020 #undef  slow
1021 #undef  dissect
1022 #undef  backref
1023 #undef  step
1024 #undef  print
1025 #undef  at
1026 #undef  match
1027 #undef  nope