git.cworth.org Git - vogl/blob - src/voglcore/regex/engine.c

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