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