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