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