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.4 2004/02/06 22:36:50 joerg 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(register 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         /* simplify the situation where possible */
 163         if (g->cflags&REG_NOSUB)
 164                 nmatch = 0;
 165         if (eflags&REG_STARTEND) {
 166                 start = string + pmatch[0].rm_so;
 167                 stop = string + pmatch[0].rm_eo;
 168         } else {
 169                 start = string;
 170                 stop = start + strlen(start);
 171         }
 172         if (stop < start)
 173                 return(REG_INVARG);
 174
 175         /* prescreening; this does wonders for this rather slow code */
 176         if (g->must != NULL) {
 177                 if (g->charjump != NULL && g->matchjump != NULL) {
 178                         mustfirst = g->must;
 179                         mustlast = g->must + g->mlen - 1;
 180                         charjump = g->charjump;
 181                         matchjump = g->matchjump;
 182                         pp = mustlast;
 183                         for (dp = start+g->mlen-1; dp < stop;) {
 184                                 /* Fast skip non-matches */
 185                                 while (dp < stop && charjump[*dp])
 186                                         dp += charjump[*dp];
 187
 188                                 if (dp >= stop)
 189                                         break;
 190
 191                                 /* Greedy matcher */
 192                                 /* We depend on not being used for
 193                                  * for strings of length 1
 194                                  */
 195                                 while (*--dp == *--pp && pp != mustfirst);
 196
 197                                 if (*dp == *pp)
 198                                         break;
 199
 200                                 /* Jump to next possible match */
 201                                 mj = matchjump[pp - mustfirst];
 202                                 cj = charjump[*dp];
 203                                 dp += (cj < mj ? mj : cj);
 204                                 pp = mustlast;
 205                         }
 206                         if (pp != mustfirst)
 207                                 return(REG_NOMATCH);
 208                 } else {
 209                         for (dp = start; dp < stop; dp++)
 210                                 if (*dp == g->must[0] &&
 211                                     stop - dp >= g->mlen &&
 212                                     memcmp(dp, g->must, (size_t)g->mlen) == 0)
 213                                         break;
 214                         if (dp == stop)         /* we didn't find g->must */
 215                                 return(REG_NOMATCH);
 216                 }
 217         }
 218
 219         /* match struct setup */
 220         m->g = g;
 221         m->eflags = eflags;
 222         m->pmatch = NULL;
 223         m->lastpos = NULL;
 224         m->offp = string;
 225         m->beginp = start;
 226         m->endp = stop;
 227         STATESETUP(m, 4);
 228         SETUP(m->st);
 229         SETUP(m->fresh);
 230         SETUP(m->tmp);
 231         SETUP(m->empty);
 232         CLEAR(m->empty);
 233
 234         /* Adjust start according to moffset, to speed things up */
 235         if (g->moffset > -1)
 236                 start = ((dp - g->moffset) < start) ? start : dp - g->moffset;
 237
 238         /* this loop does only one repetition except for backrefs */
 239         for (;;) {
 240                 endp = fast(m, start, stop, gf, gl);
 241                 if (endp == NULL) {             /* a miss */
 242                         STATETEARDOWN(m);
 243                         return(REG_NOMATCH);
 244                 }
 245                 if (nmatch == 0 && !g->backrefs)
 246                         break;          /* no further info needed */
 247
 248                 /* where? */
 249                 assert(m->coldp != NULL);
 250                 for (;;) {
 251                         NOTE("finding start");
 252                         endp = slow(m, m->coldp, stop, gf, gl);
 253                         if (endp != NULL)
 254                                 break;
 255                         assert(m->coldp < m->endp);
 256                         m->coldp++;
 257                 }
 258                 if (nmatch == 1 && !g->backrefs)
 259                         break;          /* no further info needed */
 260
 261                 /* oh my, he wants the subexpressions... */
 262                 if (m->pmatch == NULL)
 263                         m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) *
 264                                                         sizeof(regmatch_t));
 265                 if (m->pmatch == NULL) {
 266                         STATETEARDOWN(m);
 267                         return(REG_ESPACE);
 268                 }
 269                 for (i = 1; i <= m->g->nsub; i++)
 270                         m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
 271                 if (!g->backrefs && !(m->eflags&REG_BACKR)) {
 272                         NOTE("dissecting");
 273                         dp = dissect(m, m->coldp, endp, gf, gl);
 274                 } else {
 275                         if (g->nplus > 0 && m->lastpos == NULL)
 276                                 m->lastpos = (char **)malloc((g->nplus+1) *
 277                                                         sizeof(char *));
 278                         if (g->nplus > 0 && m->lastpos == NULL) {
 279                                 free(m->pmatch);
 280                                 STATETEARDOWN(m);
 281                                 return(REG_ESPACE);
 282                         }
 283                         NOTE("backref dissect");
 284                         dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
 285                 }
 286                 if (dp != NULL)
 287                         break;
 288
 289                 /* uh-oh... we couldn't find a subexpression-level match */
 290                 assert(g->backrefs);    /* must be back references doing it */
 291                 assert(g->nplus == 0 || m->lastpos != NULL);
 292                 for (;;) {
 293                         if (dp != NULL || endp <= m->coldp)
 294                                 break;          /* defeat */
 295                         NOTE("backoff");
 296                         endp = slow(m, m->coldp, endp-1, gf, gl);
 297                         if (endp == NULL)
 298                                 break;          /* defeat */
 299                         /* try it on a shorter possibility */
 300 #ifndef NDEBUG
 301                         for (i = 1; i <= m->g->nsub; i++) {
 302                                 assert(m->pmatch[i].rm_so == -1);
 303                                 assert(m->pmatch[i].rm_eo == -1);
 304                         }
 305 #endif
 306                         NOTE("backoff dissect");
 307                         dp = backref(m, m->coldp, endp, gf, gl, (sopno)0);
 308                 }
 309                 assert(dp == NULL || dp == endp);
 310                 if (dp != NULL)         /* found a shorter one */
 311                         break;
 312
 313                 /* despite initial appearances, there is no match here */
 314                 NOTE("false alarm");
 315                 start = m->coldp + 1;   /* recycle starting later */
 316                 assert(start <= stop);
 317         }
 318
 319         /* fill in the details if requested */
 320         if (nmatch > 0) {
 321                 pmatch[0].rm_so = m->coldp - m->offp;
 322                 pmatch[0].rm_eo = endp - m->offp;
 323         }
 324         if (nmatch > 1) {
 325                 assert(m->pmatch != NULL);
 326                 for (i = 1; i < nmatch; i++)
 327                         if (i <= m->g->nsub)
 328                                 pmatch[i] = m->pmatch[i];
 329                         else {
 330                                 pmatch[i].rm_so = -1;
 331                                 pmatch[i].rm_eo = -1;
 332                         }
 333         }
 334
 335         if (m->pmatch != NULL)
 336                 free((char *)m->pmatch);
 337         if (m->lastpos != NULL)
 338                 free((char *)m->lastpos);
 339         STATETEARDOWN(m);
 340         return(0);
 341 }
 342
 343 /*
 344  - dissect - figure out what matched what, no back references
 345  == static char *dissect(register struct match *m, char *start, \
 346  ==     char *stop, sopno startst, sopno stopst);
 347  */
 348 static char *                   /* == stop (success) always */
 349 dissect(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 350 {
 351         int i;
 352         sopno ss;               /* start sop of current subRE */
 353         sopno es;               /* end sop of current subRE */
 354         char *sp;               /* start of string matched by it */
 355         char *stp;              /* string matched by it cannot pass here */
 356         char *rest;             /* start of rest of string */
 357         char *tail;             /* string unmatched by rest of RE */
 358         sopno ssub;             /* start sop of subsubRE */
 359         sopno esub;             /* end sop of subsubRE */
 360         char *ssp;              /* start of string matched by subsubRE */
 361         char *sep;              /* end of string matched by subsubRE */
 362         char *oldssp;           /* previous ssp */
 363         char *dp;
 364
 365         AT("diss", start, stop, startst, stopst);
 366         sp = start;
 367         for (ss = startst; ss < stopst; ss = es) {
 368                 /* identify end of subRE */
 369                 es = ss;
 370                 switch (OP(m->g->strip[es])) {
 371                 case OPLUS_:
 372                 case OQUEST_:
 373                         es += OPND(m->g->strip[es]);
 374                         break;
 375                 case OCH_:
 376                         while (OP(m->g->strip[es]) != O_CH)
 377                                 es += OPND(m->g->strip[es]);
 378                         break;
 379                 }
 380                 es++;
 381
 382                 /* figure out what it matched */
 383                 switch (OP(m->g->strip[ss])) {
 384                 case OEND:
 385                         assert(nope);
 386                         break;
 387                 case OCHAR:
 388                         sp++;
 389                         break;
 390                 case OBOL:
 391                 case OEOL:
 392                 case OBOW:
 393                 case OEOW:
 394                         break;
 395                 case OANY:
 396                 case OANYOF:
 397                         sp++;
 398                         break;
 399                 case OBACK_:
 400                 case O_BACK:
 401                         assert(nope);
 402                         break;
 403                 /* cases where length of match is hard to find */
 404                 case OQUEST_:
 405                         stp = stop;
 406                         for (;;) {
 407                                 /* how long could this one be? */
 408                                 rest = slow(m, sp, stp, ss, es);
 409                                 assert(rest != NULL);   /* it did match */
 410                                 /* could the rest match the rest? */
 411                                 tail = slow(m, rest, stop, es, stopst);
 412                                 if (tail == stop)
 413                                         break;          /* yes! */
 414                                 /* no -- try a shorter match for this one */
 415                                 stp = rest - 1;
 416                                 assert(stp >= sp);      /* it did work */
 417                         }
 418                         ssub = ss + 1;
 419                         esub = es - 1;
 420                         /* did innards match? */
 421                         if (slow(m, sp, rest, ssub, esub) != NULL) {
 422                                 dp = dissect(m, sp, rest, ssub, esub);
 423                                 assert(dp == rest);
 424                         } else          /* no */
 425                                 assert(sp == rest);
 426                         sp = rest;
 427                         break;
 428                 case OPLUS_:
 429                         stp = stop;
 430                         for (;;) {
 431                                 /* how long could this one be? */
 432                                 rest = slow(m, sp, stp, ss, es);
 433                                 assert(rest != NULL);   /* it did match */
 434                                 /* could the rest match the rest? */
 435                                 tail = slow(m, rest, stop, es, stopst);
 436                                 if (tail == stop)
 437                                         break;          /* yes! */
 438                                 /* no -- try a shorter match for this one */
 439                                 stp = rest - 1;
 440                                 assert(stp >= sp);      /* it did work */
 441                         }
 442                         ssub = ss + 1;
 443                         esub = es - 1;
 444                         ssp = sp;
 445                         oldssp = ssp;
 446                         for (;;) {      /* find last match of innards */
 447                                 sep = slow(m, ssp, rest, ssub, esub);
 448                                 if (sep == NULL || sep == ssp)
 449                                         break;  /* failed or matched null */
 450                                 oldssp = ssp;   /* on to next try */
 451                                 ssp = sep;
 452                         }
 453                         if (sep == NULL) {
 454                                 /* last successful match */
 455                                 sep = ssp;
 456                                 ssp = oldssp;
 457                         }
 458                         assert(sep == rest);    /* must exhaust substring */
 459                         assert(slow(m, ssp, sep, ssub, esub) == rest);
 460                         dp = dissect(m, ssp, sep, ssub, esub);
 461                         assert(dp == sep);
 462                         sp = rest;
 463                         break;
 464                 case OCH_:
 465                         stp = stop;
 466                         for (;;) {
 467                                 /* how long could this one be? */
 468                                 rest = slow(m, sp, stp, ss, es);
 469                                 assert(rest != NULL);   /* it did match */
 470                                 /* could the rest match the rest? */
 471                                 tail = slow(m, rest, stop, es, stopst);
 472                                 if (tail == stop)
 473                                         break;          /* yes! */
 474                                 /* no -- try a shorter match for this one */
 475                                 stp = rest - 1;
 476                                 assert(stp >= sp);      /* it did work */
 477                         }
 478                         ssub = ss + 1;
 479                         esub = ss + OPND(m->g->strip[ss]) - 1;
 480                         assert(OP(m->g->strip[esub]) == OOR1);
 481                         for (;;) {      /* find first matching branch */
 482                                 if (slow(m, sp, rest, ssub, esub) == rest)
 483                                         break;  /* it matched all of it */
 484                                 /* that one missed, try next one */
 485                                 assert(OP(m->g->strip[esub]) == OOR1);
 486                                 esub++;
 487                                 assert(OP(m->g->strip[esub]) == OOR2);
 488                                 ssub = esub + 1;
 489                                 esub += OPND(m->g->strip[esub]);
 490                                 if (OP(m->g->strip[esub]) == OOR2)
 491                                         esub--;
 492                                 else
 493                                         assert(OP(m->g->strip[esub]) == O_CH);
 494                         }
 495                         dp = dissect(m, sp, rest, ssub, esub);
 496                         assert(dp == rest);
 497                         sp = rest;
 498                         break;
 499                 case O_PLUS:
 500                 case O_QUEST:
 501                 case OOR1:
 502                 case OOR2:
 503                 case O_CH:
 504                         assert(nope);
 505                         break;
 506                 case OLPAREN:
 507                         i = OPND(m->g->strip[ss]);
 508                         assert(0 < i && i <= m->g->nsub);
 509                         m->pmatch[i].rm_so = sp - m->offp;
 510                         break;
 511                 case ORPAREN:
 512                         i = OPND(m->g->strip[ss]);
 513                         assert(0 < i && i <= m->g->nsub);
 514                         m->pmatch[i].rm_eo = sp - m->offp;
 515                         break;
 516                 default:                /* uh oh */
 517                         assert(nope);
 518                         break;
 519                 }
 520         }
 521
 522         assert(sp == stop);
 523         return(sp);
 524 }
 525
 526 /*
 527  - backref - figure out what matched what, figuring in back references
 528  == static char *backref(register struct match *m, char *start, \
 529  ==     char *stop, sopno startst, sopno stopst, sopno lev);
 530  */
 531 static char *                   /* == stop (success) or NULL (failure) */
 532 backref(struct match *m, char *start, char *stop, sopno startst, sopno stopst,
 533         sopno lev)                      /* PLUS nesting level */
 534 {
 535         int i;
 536         sopno ss;               /* start sop of current subRE */
 537         char *sp;               /* start of string matched by it */
 538         sopno ssub;             /* start sop of subsubRE */
 539         sopno esub;             /* end sop of subsubRE */
 540         char *ssp;              /* start of string matched by subsubRE */
 541         char *dp;
 542         size_t len;
 543         int hard;
 544         sop s;
 545         regoff_t offsave;
 546         cset *cs;
 547
 548         AT("back", start, stop, startst, stopst);
 549         sp = start;
 550
 551         /* get as far as we can with easy stuff */
 552         hard = 0;
 553         for (ss = startst; !hard && ss < stopst; ss++)
 554                 switch (OP(s = m->g->strip[ss])) {
 555                 case OCHAR:
 556                         if (sp == stop || *sp++ != (char)OPND(s))
 557                                 return(NULL);
 558                         break;
 559                 case OANY:
 560                         if (sp == stop)
 561                                 return(NULL);
 562                         sp++;
 563                         break;
 564                 case OANYOF:
 565                         cs = &m->g->sets[OPND(s)];
 566                         if (sp == stop || !CHIN(cs, *sp++))
 567                                 return(NULL);
 568                         break;
 569                 case OBOL:
 570                         if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 571                                         (sp < m->endp && *(sp-1) == '\n' &&
 572                                                 (m->g->cflags&REG_NEWLINE)) )
 573                                 { /* yes */ }
 574                         else
 575                                 return(NULL);
 576                         break;
 577                 case OEOL:
 578                         if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 579                                         (sp < m->endp && *sp == '\n' &&
 580                                                 (m->g->cflags&REG_NEWLINE)) )
 581                                 { /* yes */ }
 582                         else
 583                                 return(NULL);
 584                         break;
 585                 case OBOW:
 586                         if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 587                                         (sp < m->endp && *(sp-1) == '\n' &&
 588                                                 (m->g->cflags&REG_NEWLINE)) ||
 589                                         (sp > m->beginp &&
 590                                                         !ISWORD(*(sp-1))) ) &&
 591                                         (sp < m->endp && ISWORD(*sp)) )
 592                                 { /* yes */ }
 593                         else
 594                                 return(NULL);
 595                         break;
 596                 case OEOW:
 597                         if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 598                                         (sp < m->endp && *sp == '\n' &&
 599                                                 (m->g->cflags&REG_NEWLINE)) ||
 600                                         (sp < m->endp && !ISWORD(*sp)) ) &&
 601                                         (sp > m->beginp && ISWORD(*(sp-1))) )
 602                                 { /* yes */ }
 603                         else
 604                                 return(NULL);
 605                         break;
 606                 case O_QUEST:
 607                         break;
 608                 case OOR1:      /* matches null but needs to skip */
 609                         ss++;
 610                         s = m->g->strip[ss];
 611                         do {
 612                                 assert(OP(s) == OOR2);
 613                                 ss += OPND(s);
 614                         } while (OP(s = m->g->strip[ss]) != O_CH);
 615                         /* note that the ss++ gets us past the O_CH */
 616                         break;
 617                 default:        /* have to make a choice */
 618                         hard = 1;
 619                         break;
 620                 }
 621         if (!hard) {            /* that was it! */
 622                 if (sp != stop)
 623                         return(NULL);
 624                 return(sp);
 625         }
 626         ss--;                   /* adjust for the for's final increment */
 627
 628         /* the hard stuff */
 629         AT("hard", sp, stop, ss, stopst);
 630         s = m->g->strip[ss];
 631         switch (OP(s)) {
 632         case OBACK_:            /* the vilest depths */
 633                 i = OPND(s);
 634                 assert(0 < i && i <= m->g->nsub);
 635                 if (m->pmatch[i].rm_eo == -1)
 636                         return(NULL);
 637                 assert(m->pmatch[i].rm_so != -1);
 638                 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
 639                 assert(stop - m->beginp >= len);
 640                 if (sp > stop - len)
 641                         return(NULL);   /* not enough left to match */
 642                 ssp = m->offp + m->pmatch[i].rm_so;
 643                 if (memcmp(sp, ssp, len) != 0)
 644                         return(NULL);
 645                 while (m->g->strip[ss] != SOP(O_BACK, i))
 646                         ss++;
 647                 return(backref(m, sp+len, stop, ss+1, stopst, lev));
 648                 break;
 649         case OQUEST_:           /* to null or not */
 650                 dp = backref(m, sp, stop, ss+1, stopst, lev);
 651                 if (dp != NULL)
 652                         return(dp);     /* not */
 653                 return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev));
 654                 break;
 655         case OPLUS_:
 656                 assert(m->lastpos != NULL);
 657                 assert(lev+1 <= m->g->nplus);
 658                 m->lastpos[lev+1] = sp;
 659                 return(backref(m, sp, stop, ss+1, stopst, lev+1));
 660                 break;
 661         case O_PLUS:
 662                 if (sp == m->lastpos[lev])      /* last pass matched null */
 663                         return(backref(m, sp, stop, ss+1, stopst, lev-1));
 664                 /* try another pass */
 665                 m->lastpos[lev] = sp;
 666                 dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev);
 667                 if (dp == NULL)
 668                         return(backref(m, sp, stop, ss+1, stopst, lev-1));
 669                 else
 670                         return(dp);
 671                 break;
 672         case OCH_:              /* find the right one, if any */
 673                 ssub = ss + 1;
 674                 esub = ss + OPND(s) - 1;
 675                 assert(OP(m->g->strip[esub]) == OOR1);
 676                 for (;;) {      /* find first matching branch */
 677                         dp = backref(m, sp, stop, ssub, esub, lev);
 678                         if (dp != NULL)
 679                                 return(dp);
 680                         /* that one missed, try next one */
 681                         if (OP(m->g->strip[esub]) == O_CH)
 682                                 return(NULL);   /* there is none */
 683                         esub++;
 684                         assert(OP(m->g->strip[esub]) == OOR2);
 685                         ssub = esub + 1;
 686                         esub += OPND(m->g->strip[esub]);
 687                         if (OP(m->g->strip[esub]) == OOR2)
 688                                 esub--;
 689                         else
 690                                 assert(OP(m->g->strip[esub]) == O_CH);
 691                 }
 692                 break;
 693         case OLPAREN:           /* must undo assignment if rest fails */
 694                 i = OPND(s);
 695                 assert(0 < i && i <= m->g->nsub);
 696                 offsave = m->pmatch[i].rm_so;
 697                 m->pmatch[i].rm_so = sp - m->offp;
 698                 dp = backref(m, sp, stop, ss+1, stopst, lev);
 699                 if (dp != NULL)
 700                         return(dp);
 701                 m->pmatch[i].rm_so = offsave;
 702                 return(NULL);
 703                 break;
 704         case ORPAREN:           /* must undo assignment if rest fails */
 705                 i = OPND(s);
 706                 assert(0 < i && i <= m->g->nsub);
 707                 offsave = m->pmatch[i].rm_eo;
 708                 m->pmatch[i].rm_eo = sp - m->offp;
 709                 dp = backref(m, sp, stop, ss+1, stopst, lev);
 710                 if (dp != NULL)
 711                         return(dp);
 712                 m->pmatch[i].rm_eo = offsave;
 713                 return(NULL);
 714                 break;
 715         default:                /* uh oh */
 716                 assert(nope);
 717                 break;
 718         }
 719
 720         /* "can't happen" */
 721         assert(nope);
 722         /* NOTREACHED */
 723         return "shut up gcc";
 724 }
 725
 726 /*
 727  - fast - step through the string at top speed
 728  == static char *fast(register struct match *m, char *start, \
 729  ==     char *stop, sopno startst, sopno stopst);
 730  */
 731 static char *                   /* where tentative match ended, or NULL */
 732 fast(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 733 {
 734         states st = m->st;
 735         states fresh = m->fresh;
 736         states tmp = m->tmp;
 737         char *p = start;
 738         int c = (start == m->beginp) ? OUT : *(start-1);
 739         int lastc;              /* previous c */
 740         int flagch;
 741         int i;
 742         char *coldp;            /* last p after which no match was underway */
 743
 744         CLEAR(st);
 745         SET1(st, startst);
 746         st = step(m->g, startst, stopst, st, NOTHING, st);
 747         ASSIGN(fresh, st);
 748         SP("start", st, *p);
 749         coldp = NULL;
 750         for (;;) {
 751                 /* next character */
 752                 lastc = c;
 753                 c = (p == m->endp) ? OUT : *p;
 754                 if (EQ(st, fresh))
 755                         coldp = p;
 756
 757                 /* is there an EOL and/or BOL between lastc and c? */
 758                 flagch = '\0';
 759                 i = 0;
 760                 if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 761                                 (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 762                         flagch = BOL;
 763                         i = m->g->nbol;
 764                 }
 765                 if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 766                                 (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 767                         flagch = (flagch == BOL) ? BOLEOL : EOL;
 768                         i += m->g->neol;
 769                 }
 770                 if (i != 0) {
 771                         for (; i > 0; i--)
 772                                 st = step(m->g, startst, stopst, st, flagch, st);
 773                         SP("boleol", st, c);
 774                 }
 775
 776                 /* how about a word boundary? */
 777                 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 778                                         (c != OUT && ISWORD(c)) ) {
 779                         flagch = BOW;
 780                 }
 781                 if ( (lastc != OUT && ISWORD(lastc)) &&
 782                                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 783                         flagch = EOW;
 784                 }
 785                 if (flagch == BOW || flagch == EOW) {
 786                         st = step(m->g, startst, stopst, st, flagch, st);
 787                         SP("boweow", st, c);
 788                 }
 789
 790                 /* are we done? */
 791                 if (ISSET(st, stopst) || p == stop)
 792                         break;          /* NOTE BREAK OUT */
 793
 794                 /* no, we must deal with this character */
 795                 ASSIGN(tmp, st);
 796                 ASSIGN(st, fresh);
 797                 assert(c != OUT);
 798                 st = step(m->g, startst, stopst, tmp, c, st);
 799                 SP("aft", st, c);
 800                 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 801                 p++;
 802         }
 803
 804         assert(coldp != NULL);
 805         m->coldp = coldp;
 806         if (ISSET(st, stopst))
 807                 return(p+1);
 808         else
 809                 return(NULL);
 810 }
 811
 812 /*
 813  - slow - step through the string more deliberately
 814  == static char *slow(register struct match *m, char *start, \
 815  ==     char *stop, sopno startst, sopno stopst);
 816  */
 817 static char *                   /* where it ended */
 818 slow(struct match *m, char *start, char *stop, sopno startst, sopno stopst)
 819 {
 820         states st = m->st;
 821         states empty = m->empty;
 822         states tmp = m->tmp;
 823         char *p = start;
 824         int c = (start == m->beginp) ? OUT : *(start-1);
 825         int lastc;              /* previous c */
 826         int flagch;
 827         int i;
 828         char *matchp;           /* last p at which a match ended */
 829
 830         AT("slow", start, stop, startst, stopst);
 831         CLEAR(st);
 832         SET1(st, startst);
 833         SP("sstart", st, *p);
 834         st = step(m->g, startst, stopst, st, NOTHING, st);
 835         matchp = NULL;
 836         for (;;) {
 837                 /* next character */
 838                 lastc = c;
 839                 c = (p == m->endp) ? OUT : *p;
 840
 841                 /* is there an EOL and/or BOL between lastc and c? */
 842                 flagch = '\0';
 843                 i = 0;
 844                 if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 845                                 (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 846                         flagch = BOL;
 847                         i = m->g->nbol;
 848                 }
 849                 if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 850                                 (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 851                         flagch = (flagch == BOL) ? BOLEOL : EOL;
 852                         i += m->g->neol;
 853                 }
 854                 if (i != 0) {
 855                         for (; i > 0; i--)
 856                                 st = step(m->g, startst, stopst, st, flagch, st);
 857                         SP("sboleol", st, c);
 858                 }
 859
 860                 /* how about a word boundary? */
 861                 if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 862                                         (c != OUT && ISWORD(c)) ) {
 863                         flagch = BOW;
 864                 }
 865                 if ( (lastc != OUT && ISWORD(lastc)) &&
 866                                 (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 867                         flagch = EOW;
 868                 }
 869                 if (flagch == BOW || flagch == EOW) {
 870                         st = step(m->g, startst, stopst, st, flagch, st);
 871                         SP("sboweow", st, c);
 872                 }
 873
 874                 /* are we done? */
 875                 if (ISSET(st, stopst))
 876                         matchp = p;
 877                 if (EQ(st, empty) || p == stop)
 878                         break;          /* NOTE BREAK OUT */
 879
 880                 /* no, we must deal with this character */
 881                 ASSIGN(tmp, st);
 882                 ASSIGN(st, empty);
 883                 assert(c != OUT);
 884                 st = step(m->g, startst, stopst, tmp, c, st);
 885                 SP("saft", st, c);
 886                 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 887                 p++;
 888         }
 889
 890         return(matchp);
 891 }
 892
 893
 894 /*
 895  - step - map set of states reachable before char to set reachable after
 896  == static states step(register struct re_guts *g, sopno start, sopno stop, \
 897  ==     register states bef, int ch, register states aft);
 898  == #define     BOL     (OUT+1)
 899  == #define     EOL     (BOL+1)
 900  == #define     BOLEOL  (BOL+2)
 901  == #define     NOTHING (BOL+3)
 902  == #define     BOW     (BOL+4)
 903  == #define     EOW     (BOL+5)
 904  == #define     CODEMAX (BOL+5)         // highest code used
 905  == #define     NONCHAR(c)      ((c) > CHAR_MAX)
 906  == #define     NNONCHAR        (CODEMAX-CHAR_MAX)
 907  */
 908 static states
 909 step(struct re_guts *g,
 910      sopno start,               /* start state within strip */
 911      sopno stop,                /* state after stop state within strip */
 912      states bef,                /* states reachable before */
 913      int ch,                    /* character or NONCHAR code */
 914      states aft)                /* states already known reachable after */
 915 {
 916         cset *cs;
 917         sop s;
 918         sopno pc;
 919         onestate here;                  /* note, macros know this name */
 920         sopno look;
 921         int i;
 922
 923         for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
 924                 s = g->strip[pc];
 925                 switch (OP(s)) {
 926                 case OEND:
 927                         assert(pc == stop-1);
 928                         break;
 929                 case OCHAR:
 930                         /* only characters can match */
 931                         assert(!NONCHAR(ch) || ch != (char)OPND(s));
 932                         if (ch == (char)OPND(s))
 933                                 FWD(aft, bef, 1);
 934                         break;
 935                 case OBOL:
 936                         if (ch == BOL || ch == BOLEOL)
 937                                 FWD(aft, bef, 1);
 938                         break;
 939                 case OEOL:
 940                         if (ch == EOL || ch == BOLEOL)
 941                                 FWD(aft, bef, 1);
 942                         break;
 943                 case OBOW:
 944                         if (ch == BOW)
 945                                 FWD(aft, bef, 1);
 946                         break;
 947                 case OEOW:
 948                         if (ch == EOW)
 949                                 FWD(aft, bef, 1);
 950                         break;
 951                 case OANY:
 952                         if (!NONCHAR(ch))
 953                                 FWD(aft, bef, 1);
 954                         break;
 955                 case OANYOF:
 956                         cs = &g->sets[OPND(s)];
 957                         if (!NONCHAR(ch) && CHIN(cs, ch))
 958                                 FWD(aft, bef, 1);
 959                         break;
 960                 case OBACK_:            /* ignored here */
 961                 case O_BACK:
 962                         FWD(aft, aft, 1);
 963                         break;
 964                 case OPLUS_:            /* forward, this is just an empty */
 965                         FWD(aft, aft, 1);
 966                         break;
 967                 case O_PLUS:            /* both forward and back */
 968                         FWD(aft, aft, 1);
 969                         i = ISSETBACK(aft, OPND(s));
 970                         BACK(aft, aft, OPND(s));
 971                         if (!i && ISSETBACK(aft, OPND(s))) {
 972                                 /* oho, must reconsider loop body */
 973                                 pc -= OPND(s) + 1;
 974                                 INIT(here, pc);
 975                         }
 976                         break;
 977                 case OQUEST_:           /* two branches, both forward */
 978                         FWD(aft, aft, 1);
 979                         FWD(aft, aft, OPND(s));
 980                         break;
 981                 case O_QUEST:           /* just an empty */
 982                         FWD(aft, aft, 1);
 983                         break;
 984                 case OLPAREN:           /* not significant here */
 985                 case ORPAREN:
 986                         FWD(aft, aft, 1);
 987                         break;
 988                 case OCH_:              /* mark the first two branches */
 989                         FWD(aft, aft, 1);
 990                         assert(OP(g->strip[pc+OPND(s)]) == OOR2);
 991                         FWD(aft, aft, OPND(s));
 992                         break;
 993                 case OOR1:              /* done a branch, find the O_CH */
 994                         if (ISSTATEIN(aft, here)) {
 995                                 for (look = 1;
 996                                                 OP(s = g->strip[pc+look]) != O_CH;
 997                                                 look += OPND(s))
 998                                         assert(OP(s) == OOR2);
 999                                 FWD(aft, aft, look);
1000                         }
1001                         break;
1002                 case OOR2:              /* propagate OCH_'s marking */
1003                         FWD(aft, aft, 1);
1004                         if (OP(g->strip[pc+OPND(s)]) != O_CH) {
1005                                 assert(OP(g->strip[pc+OPND(s)]) == OOR2);
1006                                 FWD(aft, aft, OPND(s));
1007                         }
1008                         break;
1009                 case O_CH:              /* just empty */
1010                         FWD(aft, aft, 1);
1011                         break;
1012                 default:                /* ooooops... */
1013                         assert(nope);
1014                         break;
1015                 }
1016         }
1017
1018         return(aft);
1019 }
1020
1021 #ifdef REDEBUG
1022 /*
1023  - print - print a set of states
1024  == #ifdef REDEBUG
1025  == static void print(struct match *m, char *caption, states st, \
1026  ==     int ch, FILE *d);
1027  == #endif
1028  */
1029 static void
1030 print(struct match *m, char *caption, states st, int ch, FILE *d)
1031 {
1032         struct re_guts *g = m->g;
1033         int i;
1034         int first = 1;
1035
1036         if (!(m->eflags&REG_TRACE))
1037                 return;
1038
1039         fprintf(d, "%s", caption);
1040         if (ch != '\0')
1041                 fprintf(d, " %s", pchar(ch));
1042         for (i = 0; i < g->nstates; i++)
1043                 if (ISSET(st, i)) {
1044                         fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
1045                         first = 0;
1046                 }
1047         fprintf(d, "\n");
1048 }
1049
1050 /*
1051  - at - print current situation
1052  == #ifdef REDEBUG
1053  == static void at(struct match *m, char *title, char *start, char *stop, \
1054  ==                                             sopno startst, sopno stopst);
1055  == #endif
1056  */
1057 static void
1058 at(struct match *m, char *title, char *start, char *stop, sopno startst,
1059    sopno stopst)
1060 {
1061         if (!(m->eflags&REG_TRACE))
1062                 return;
1063
1064         printf("%s %s-", title, pchar(*start));
1065         printf("%s ", pchar(*stop));
1066         printf("%ld-%ld\n", (long)startst, (long)stopst);
1067 }
1068
1069 #ifndef PCHARDONE
1070 #define PCHARDONE       /* never again */
1071 /*
1072  - pchar - make a character printable
1073  == #ifdef REDEBUG
1074  == static char *pchar(int ch);
1075  == #endif
1076  *
1077  * Is this identical to regchar() over in debug.c?  Well, yes.  But a
1078  * duplicate here avoids having a debugging-capable regexec.o tied to
1079  * a matching debug.o, and this is convenient.  It all disappears in
1080  * the non-debug compilation anyway, so it doesn't matter much.
1081  */
1082 static char *                   /* -> representation */
1083 pchar(int ch)
1084 {
1085         static char pbuf[10];
1086
1087         if (isprint((uch)ch) || ch == ' ')
1088                 sprintf(pbuf, "%c", ch);
1089         else
1090                 sprintf(pbuf, "\\%o", ch);
1091         return(pbuf);
1092 }
1093 #endif
1094 #endif
1095
1096 #undef  matcher
1097 #undef  fast
1098 #undef  slow
1099 #undef  dissect
1100 #undef  backref
1101 #undef  step
1102 #undef  print
1103 #undef  at
1104 #undef  match