git.gag.com Git - debian/amanda/blob - regex-src/engine.c

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