lib/libc/regex/engine.c

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