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

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