lib/libc/regex/engine.c

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