[fix crash in regexec.c]
[perl.git] / regexec.c
1 /*    regexec.c
2  */
3
4 /*
5  * "One Ring to rule them all, One Ring to find them..."
6  */
7
8 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
9  * confused with the original package (see point 3 below).  Thanks, Henry!
10  */
11
12 /* Additional note: this code is very heavily munged from Henry's version
13  * in places.  In some spots I've traded clarity for efficiency, so don't
14  * blame Henry for some of the lack of readability.
15  */
16
17 /*SUPPRESS 112*/
18 /*
19  * regcomp and regexec -- regsub and regerror are not used in perl
20  *
21  *      Copyright (c) 1986 by University of Toronto.
22  *      Written by Henry Spencer.  Not derived from licensed software.
23  *
24  *      Permission is granted to anyone to use this software for any
25  *      purpose on any computer system, and to redistribute it freely,
26  *      subject to the following restrictions:
27  *
28  *      1. The author is not responsible for the consequences of use of
29  *              this software, no matter how awful, even if they arise
30  *              from defects in it.
31  *
32  *      2. The origin of this software must not be misrepresented, either
33  *              by explicit claim or by omission.
34  *
35  *      3. Altered versions must be plainly marked as such, and must not
36  *              be misrepresented as being the original software.
37  *
38  ****    Alterations to Henry's code are...
39  ****
40  ****    Copyright (c) 1991-1994, Larry Wall
41  ****
42  ****    You may distribute under the terms of either the GNU General Public
43  ****    License or the Artistic License, as specified in the README file.
44  *
45  * Beware that some of this code is subtly aware of the way operator
46  * precedence is structured in regular expressions.  Serious changes in
47  * regular-expression syntax might require a total rethink.
48  */
49 #include "EXTERN.h"
50 #include "perl.h"
51 #include "regcomp.h"
52
53 #ifndef STATIC
54 #define STATIC  static
55 #endif
56
57 #ifdef DEBUGGING
58 static I32 regnarrate = 0;
59 static char* regprogram = 0;
60 #endif
61
62 /* Current curly descriptor */
63 typedef struct curcur CURCUR;
64 struct curcur {
65     int         parenfloor;     /* how far back to strip paren data */
66     int         cur;            /* how many instances of scan we've matched */
67     int         min;            /* the minimal number of scans to match */
68     int         max;            /* the maximal number of scans to match */
69     int         minmod;         /* whether to work our way up or down */
70     char *      scan;           /* the thing to match */
71     char *      next;           /* what has to match after it */
72     char *      lastloc;        /* where we started matching this scan */
73     CURCUR *    oldcc;          /* current curly before we started this one */
74 };
75
76 static CURCUR* regcc;
77
78 typedef I32 CHECKPOINT;
79
80 CHECKPOINT regcppush _((I32 parenfloor));
81 char * regcppop _((void));
82
83 CHECKPOINT
84 regcppush(parenfloor)
85 I32 parenfloor;
86 {
87     int retval = savestack_ix;
88     int i = (regsize - parenfloor) * 3;
89     int p;
90
91     SSCHECK(i + 5);
92     for (p = regsize; p > parenfloor; p--) {
93         SSPUSHPTR(regendp[p]);
94         SSPUSHPTR(regstartp[p]);
95         SSPUSHINT(p);
96     }
97     SSPUSHINT(regsize);
98     SSPUSHINT(*reglastparen);
99     SSPUSHPTR(reginput);
100     SSPUSHINT(i + 3);
101     SSPUSHINT(SAVEt_REGCONTEXT);
102     return retval;
103 }
104
105 char*
106 regcppop()
107 {
108     I32 i = SSPOPINT;
109     U32 paren = 0;
110     char *input;
111     char *tmps;
112     assert(i == SAVEt_REGCONTEXT);
113     i = SSPOPINT;
114     input = (char *) SSPOPPTR;
115     *reglastparen = SSPOPINT;
116     regsize = SSPOPINT;
117     for (i -= 3; i > 0; i -= 3) {
118         paren = (U32)SSPOPINT;
119         regstartp[paren] = (char *) SSPOPPTR;
120         tmps = (char*)SSPOPPTR;
121         if (paren <= *reglastparen)
122             regendp[paren] = tmps;
123     }
124     for (paren = *reglastparen + 1; paren <= regnpar; paren++) {
125         if (paren > regsize)
126             regstartp[paren] = Nullch;
127         regendp[paren] = Nullch;
128     }
129     return input;
130 }
131
132 #define regcpblow(cp) leave_scope(cp)
133
134 /*
135  * regexec and friends
136  */
137
138 /*
139  * Forwards.
140  */
141
142 static I32 regmatch _((char *prog));
143 static I32 regrepeat _((char *p, I32 max));
144 static I32 regtry _((regexp *prog, char *startpos));
145
146 /*
147  - regexec - match a regexp against a string
148  */
149 I32
150 regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
151 register regexp *prog;
152 char *stringarg;
153 register char *strend;  /* pointer to null at end of string */
154 char *strbeg;   /* real beginning of string */
155 I32 minend;     /* end of match must be at least minend after stringarg */
156 SV *screamer;
157 I32 safebase;   /* no need to remember string in subbase */
158 {
159     register char *s;
160     register I32 i;
161     register char *c;
162     register char *startpos = stringarg;
163     register I32 tmp;
164     I32 minlen = 0;             /* must match at least this many chars */
165     I32 dontbother = 0; /* how many characters not to try at end */
166     CURCUR cc;
167
168     cc.cur = 0;
169     regcc = &cc;
170
171 #ifdef DEBUGGING
172     regnarrate = debug & 512;
173     regprogram = prog->program;
174 #endif
175
176     /* Be paranoid... */
177     if (prog == NULL || startpos == NULL) {
178         croak("NULL regexp parameter");
179         return 0;
180     }
181
182     if (startpos == strbeg)     /* is ^ valid at stringarg? */
183         regprev = '\n';
184     else {
185         regprev = stringarg[-1];
186         if (!multiline && regprev == '\n')
187             regprev = '\0';             /* force ^ to NOT match */
188     }
189     regprecomp = prog->precomp;
190     regnpar = prog->nparens;
191     /* Check validity of program. */
192     if (UCHARAT(prog->program) != MAGIC) {
193         FAIL("corrupted regexp program");
194     }
195
196     if (prog->do_folding) {
197         i = strend - startpos;
198         New(1101,c,i+1,char);
199         Copy(startpos, c, i+1, char);
200         startpos = c;
201         strend = startpos + i;
202         for (s = startpos; s < strend; s++)
203             if (isUPPER(*s))
204                 *s = toLOWER(*s);
205     }
206
207     /* If there is a "must appear" string, look for it. */
208     s = startpos;
209     if (prog->regmust != Nullsv &&
210         (!(prog->reganch & ROPT_ANCH)
211          || (multiline && prog->regback >= 0)) )
212     {
213         if (stringarg == strbeg && screamer) {
214             if (screamfirst[BmRARE(prog->regmust)] >= 0)
215                     s = screaminstr(screamer,prog->regmust);
216             else
217                     s = Nullch;
218         }
219         else
220             s = fbm_instr((unsigned char*)s, (unsigned char*)strend,
221                 prog->regmust);
222         if (!s) {
223             ++BmUSEFUL(prog->regmust);  /* hooray */
224             goto phooey;        /* not present */
225         }
226         else if (prog->regback >= 0) {
227             s -= prog->regback;
228             if (s < startpos)
229                 s = startpos;
230             minlen = prog->regback + SvCUR(prog->regmust);
231         }
232         else if (!prog->naughty && --BmUSEFUL(prog->regmust) < 0) { /* boo */
233             SvREFCNT_dec(prog->regmust);
234             prog->regmust = Nullsv;     /* disable regmust */
235             s = startpos;
236         }
237         else {
238             s = startpos;
239             minlen = SvCUR(prog->regmust);
240         }
241     }
242
243     /* Mark beginning of line for ^ . */
244     regbol = startpos;
245
246     /* Mark end of line for $ (and such) */
247     regeol = strend;
248
249     /* see how far we have to get to not match where we matched before */
250     regtill = startpos+minend;
251
252     /* Simplest case:  anchored match need be tried only once. */
253     /*  [unless multiline is set] */
254     if (prog->reganch & ROPT_ANCH) {
255         if (regtry(prog, startpos))
256             goto got_it;
257         else if (multiline || (prog->reganch & ROPT_IMPLICIT)) {
258             if (minlen)
259                 dontbother = minlen - 1;
260             strend -= dontbother;
261             /* for multiline we only have to try after newlines */
262             if (s > startpos)
263                 s--;
264             while (s < strend) {
265                 if (*s++ == '\n') {
266                     if (s < strend && regtry(prog, s))
267                         goto got_it;
268                 }
269             }
270         }
271         goto phooey;
272     }
273
274     /* Messy cases:  unanchored match. */
275     if (prog->regstart) {
276         if (prog->reganch & ROPT_SKIP) {  /* we have /x+whatever/ */
277             /* it must be a one character string */
278             i = SvPVX(prog->regstart)[0];
279             while (s < strend) {
280                 if (*s == i) {
281                     if (regtry(prog, s))
282                         goto got_it;
283                     s++;
284                     while (s < strend && *s == i)
285                         s++;
286                 }
287                 s++;
288             }
289         }
290         else if (SvPOK(prog->regstart) == 3) {
291             /* We know what string it must start with. */
292             while ((s = fbm_instr((unsigned char*)s,
293               (unsigned char*)strend, prog->regstart)) != NULL)
294             {
295                 if (regtry(prog, s))
296                     goto got_it;
297                 s++;
298             }
299         }
300         else {
301             c = SvPVX(prog->regstart);
302             while ((s = ninstr(s, strend, c, c + SvCUR(prog->regstart))) != NULL)
303             {
304                 if (regtry(prog, s))
305                     goto got_it;
306                 s++;
307             }
308         }
309         goto phooey;
310     }
311     /*SUPPRESS 560*/
312     if (c = prog->regstclass) {
313         I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
314
315         if (minlen)
316             dontbother = minlen - 1;
317         strend -= dontbother;   /* don't bother with what can't match */
318         tmp = 1;
319         /* We know what class it must start with. */
320         switch (OP(c)) {
321         case ANYOF:
322             c = OPERAND(c);
323             while (s < strend) {
324                 i = UCHARAT(s);
325                 if (!(c[i >> 3] & (1 << (i&7)))) {
326                     if (tmp && regtry(prog, s))
327                         goto got_it;
328                     else
329                         tmp = doevery;
330                 }
331                 else
332                     tmp = 1;
333                 s++;
334             }
335             break;
336         case BOUND:
337             if (minlen)
338                 dontbother++,strend--;
339             if (s != startpos) {
340                 i = s[-1];
341                 tmp = isALNUM(i);
342             }
343             else
344                 tmp = isALNUM(regprev); /* assume not alphanumeric */
345             while (s < strend) {
346                 i = *s;
347                 if (tmp != isALNUM(i)) {
348                     tmp = !tmp;
349                     if (regtry(prog, s))
350                         goto got_it;
351                 }
352                 s++;
353             }
354             if ((minlen || tmp) && regtry(prog,s))
355                 goto got_it;
356             break;
357         case NBOUND:
358             if (minlen)
359                 dontbother++,strend--;
360             if (s != startpos) {
361                 i = s[-1];
362                 tmp = isALNUM(i);
363             }
364             else
365                 tmp = isALNUM(regprev); /* assume not alphanumeric */
366             while (s < strend) {
367                 i = *s;
368                 if (tmp != isALNUM(i))
369                     tmp = !tmp;
370                 else if (regtry(prog, s))
371                     goto got_it;
372                 s++;
373             }
374             if ((minlen || !tmp) && regtry(prog,s))
375                 goto got_it;
376             break;
377         case ALNUM:
378             while (s < strend) {
379                 i = *s;
380                 if (isALNUM(i)) {
381                     if (tmp && regtry(prog, s))
382                         goto got_it;
383                     else
384                         tmp = doevery;
385                 }
386                 else
387                     tmp = 1;
388                 s++;
389             }
390             break;
391         case NALNUM:
392             while (s < strend) {
393                 i = *s;
394                 if (!isALNUM(i)) {
395                     if (tmp && regtry(prog, s))
396                         goto got_it;
397                     else
398                         tmp = doevery;
399                 }
400                 else
401                     tmp = 1;
402                 s++;
403             }
404             break;
405         case SPACE:
406             while (s < strend) {
407                 if (isSPACE(*s)) {
408                     if (tmp && regtry(prog, s))
409                         goto got_it;
410                     else
411                         tmp = doevery;
412                 }
413                 else
414                     tmp = 1;
415                 s++;
416             }
417             break;
418         case NSPACE:
419             while (s < strend) {
420                 if (!isSPACE(*s)) {
421                     if (tmp && regtry(prog, s))
422                         goto got_it;
423                     else
424                         tmp = doevery;
425                 }
426                 else
427                     tmp = 1;
428                 s++;
429             }
430             break;
431         case DIGIT:
432             while (s < strend) {
433                 if (isDIGIT(*s)) {
434                     if (tmp && regtry(prog, s))
435                         goto got_it;
436                     else
437                         tmp = doevery;
438                 }
439                 else
440                     tmp = 1;
441                 s++;
442             }
443             break;
444         case NDIGIT:
445             while (s < strend) {
446                 if (!isDIGIT(*s)) {
447                     if (tmp && regtry(prog, s))
448                         goto got_it;
449                     else
450                         tmp = doevery;
451                 }
452                 else
453                     tmp = 1;
454                 s++;
455             }
456             break;
457         }
458     }
459     else {
460         if (minlen)
461             dontbother = minlen - 1;
462         strend -= dontbother;
463         /* We don't know much -- general case. */
464         do {
465             if (regtry(prog, s))
466                 goto got_it;
467         } while (s++ < strend);
468     }
469
470     /* Failure. */
471     goto phooey;
472
473 got_it:
474     strend += dontbother;       /* uncheat */
475     prog->subbeg = strbeg;
476     prog->subend = strend;
477     if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding) {
478         i = strend - startpos + (stringarg - strbeg);
479         if (safebase) {                 /* no need for $digit later */
480             s = strbeg;
481             prog->subend = s+i;
482         }
483         else if (strbeg != prog->subbase) {
484             s = savepvn(strbeg,i);      /* so $digit will work later */
485             if (prog->subbase)
486                 Safefree(prog->subbase);
487             prog->subbeg = prog->subbase = s;
488             prog->subend = s+i;
489         }
490         else {
491             prog->subbeg = s = prog->subbase;
492             prog->subend = s+i;
493         }
494         s += (stringarg - strbeg);
495         for (i = 0; i <= prog->nparens; i++) {
496             if (prog->endp[i]) {
497                 prog->startp[i] = s + (prog->startp[i] - startpos);
498                 prog->endp[i] = s + (prog->endp[i] - startpos);
499             }
500         }
501         if (prog->do_folding)
502             Safefree(startpos);
503     }
504     return 1;
505
506 phooey:
507     if (prog->do_folding)
508         Safefree(startpos);
509     return 0;
510 }
511
512 /*
513  - regtry - try match at specific point
514  */
515 static I32                      /* 0 failure, 1 success */
516 regtry(prog, startpos)
517 regexp *prog;
518 char *startpos;
519 {
520     register I32 i;
521     register char **sp;
522     register char **ep;
523
524     reginput = startpos;
525     regstartp = prog->startp;
526     regendp = prog->endp;
527     reglastparen = &prog->lastparen;
528     prog->lastparen = 0;
529     regsize = 0;
530
531     sp = prog->startp;
532     ep = prog->endp;
533     if (prog->nparens) {
534         for (i = prog->nparens; i >= 0; i--) {
535             *sp++ = NULL;
536             *ep++ = NULL;
537         }
538     }
539     if (regmatch(prog->program + 1) && reginput >= regtill) {
540         prog->startp[0] = startpos;
541         prog->endp[0] = reginput;
542         return 1;
543     }
544     else
545         return 0;
546 }
547
548 /*
549  - regmatch - main matching routine
550  *
551  * Conceptually the strategy is simple:  check to see whether the current
552  * node matches, call self recursively to see whether the rest matches,
553  * and then act accordingly.  In practice we make some effort to avoid
554  * recursion, in particular by going through "ordinary" nodes (that don't
555  * need to know whether the rest of the match failed) by a loop instead of
556  * by recursion.
557  */
558 /* [lwall] I've hoisted the register declarations to the outer block in order to
559  * maybe save a little bit of pushing and popping on the stack.  It also takes
560  * advantage of machines that use a register save mask on subroutine entry.
561  */
562 static I32                      /* 0 failure, 1 success */
563 regmatch(prog)
564 char *prog;
565 {
566     register char *scan;        /* Current node. */
567     char *next;                 /* Next node. */
568     register I32 nextchar;
569     register I32 n;             /* no or next */
570     register I32 ln;            /* len or last */
571     register char *s;           /* operand or save */
572     register char *locinput = reginput;
573     int minmod = 0;
574
575     nextchar = *locinput;
576     scan = prog;
577     while (scan != NULL) {
578 #ifdef DEBUGGING
579         if (regnarrate)
580             fprintf(stderr, "%2d%-8.8s\t<%.10s>\n",
581                 scan - regprogram, regprop(scan), locinput);
582 #endif
583
584 #ifdef REGALIGN
585         next = scan + NEXT(scan);
586         if (next == scan)
587             next = NULL;
588 #else
589         next = regnext(scan);
590 #endif
591
592         switch (OP(scan)) {
593         case BOL:
594             if (locinput == regbol
595                 ? regprev == '\n'
596                 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
597             {
598                 /* regtill = regbol; */
599                 break;
600             }
601             return 0;
602         case MBOL:
603             if (locinput == regbol
604                 ? regprev == '\n'
605                 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
606             {
607                 break;
608             }
609             return 0;
610         case SBOL:
611             if (locinput == regbol && regprev == '\n')
612                 break;
613             return 0;
614         case GBOL:
615             if (locinput == regbol)
616                 break;
617             return 0;
618         case EOL:
619             if (multiline)
620                 goto meol;
621             else
622                 goto seol;
623         case MEOL:
624           meol:
625             if ((nextchar || locinput < regeol) && nextchar != '\n')
626                 return 0;
627             break;
628         case SEOL:
629           seol:
630             if ((nextchar || locinput < regeol) && nextchar != '\n')
631                 return 0;
632             if (regeol - locinput > 1)
633                 return 0;
634             break;
635         case SANY:
636             if (!nextchar && locinput >= regeol)
637                 return 0;
638             nextchar = *++locinput;
639             break;
640         case ANY:
641             if (!nextchar && locinput >= regeol || nextchar == '\n')
642                 return 0;
643             nextchar = *++locinput;
644             break;
645         case EXACTLY:
646             s = OPERAND(scan);
647             ln = *s++;
648             /* Inline the first character, for speed. */
649             if (*s != nextchar)
650                 return 0;
651             if (regeol - locinput < ln)
652                 return 0;
653             if (ln > 1 && bcmp(s, locinput, ln) != 0)
654                 return 0;
655             locinput += ln;
656             nextchar = *locinput;
657             break;
658         case ANYOF:
659             s = OPERAND(scan);
660             if (nextchar < 0)
661                 nextchar = UCHARAT(locinput);
662             if (s[nextchar >> 3] & (1 << (nextchar&7)))
663                 return 0;
664             if (!nextchar && locinput >= regeol)
665                 return 0;
666             nextchar = *++locinput;
667             break;
668         case ALNUM:
669             if (!nextchar)
670                 return 0;
671             if (!isALNUM(nextchar))
672                 return 0;
673             nextchar = *++locinput;
674             break;
675         case NALNUM:
676             if (!nextchar && locinput >= regeol)
677                 return 0;
678             if (isALNUM(nextchar))
679                 return 0;
680             nextchar = *++locinput;
681             break;
682         case NBOUND:
683         case BOUND:
684             if (locinput == regbol)     /* was last char in word? */
685                 ln = isALNUM(regprev);
686             else 
687                 ln = isALNUM(locinput[-1]);
688             n = isALNUM(nextchar); /* is next char in word? */
689             if ((ln == n) == (OP(scan) == BOUND))
690                 return 0;
691             break;
692         case SPACE:
693             if (!nextchar && locinput >= regeol)
694                 return 0;
695             if (!isSPACE(nextchar))
696                 return 0;
697             nextchar = *++locinput;
698             break;
699         case NSPACE:
700             if (!nextchar)
701                 return 0;
702             if (isSPACE(nextchar))
703                 return 0;
704             nextchar = *++locinput;
705             break;
706         case DIGIT:
707             if (!isDIGIT(nextchar))
708                 return 0;
709             nextchar = *++locinput;
710             break;
711         case NDIGIT:
712             if (!nextchar && locinput >= regeol)
713                 return 0;
714             if (isDIGIT(nextchar))
715                 return 0;
716             nextchar = *++locinput;
717             break;
718         case REF:
719             n = ARG1(scan);  /* which paren pair */
720             s = regstartp[n];
721             if (!s)
722                 return 0;
723             if (!regendp[n])
724                 return 0;
725             if (s == regendp[n])
726                 break;
727             /* Inline the first character, for speed. */
728             if (*s != nextchar)
729                 return 0;
730             ln = regendp[n] - s;
731             if (locinput + ln > regeol)
732                 return 0;
733             if (ln > 1 && bcmp(s, locinput, ln) != 0)
734                 return 0;
735             locinput += ln;
736             nextchar = *locinput;
737             break;
738
739         case NOTHING:
740             break;
741         case BACK:
742             break;
743         case OPEN:
744             n = ARG1(scan);  /* which paren pair */
745             regstartp[n] = locinput;
746             if (n > regsize)
747                 regsize = n;
748             break;
749         case CLOSE:
750             n = ARG1(scan);  /* which paren pair */
751             regendp[n] = locinput;
752             if (n > *reglastparen)
753                 *reglastparen = n;
754             break;
755         case CURLYX: {
756                 CURCUR cc;
757                 CHECKPOINT cp = savestack_ix;
758                 cc.oldcc = regcc;
759                 regcc = &cc;
760                 cc.parenfloor = *reglastparen;
761                 cc.cur = -1;
762                 cc.min = ARG1(scan);
763                 cc.max  = ARG2(scan);
764                 cc.scan = NEXTOPER(scan) + 4;
765                 cc.next = next;
766                 cc.minmod = minmod;
767                 cc.lastloc = 0;
768                 reginput = locinput;
769                 n = regmatch(PREVOPER(next));   /* start on the WHILEM */
770                 regcpblow(cp);
771                 regcc = cc.oldcc;
772                 return n;
773             }
774             /* NOT REACHED */
775         case WHILEM: {
776                 /*
777                  * This is really hard to understand, because after we match
778                  * what we're trying to match, we must make sure the rest of
779                  * the RE is going to match for sure, and to do that we have
780                  * to go back UP the parse tree by recursing ever deeper.  And
781                  * if it fails, we have to reset our parent's current state
782                  * that we can try again after backing off.
783                  */
784
785                 CURCUR* cc = regcc;
786                 n = cc->cur + 1;
787                 reginput = locinput;
788
789                 /* If degenerate scan matches "", assume scan done. */
790
791                 if (locinput == cc->lastloc) {
792                     regcc = cc->oldcc;
793                     ln = regcc->cur;
794                     if (regmatch(cc->next))
795                         return TRUE;
796                     regcc->cur = ln;
797                     regcc = cc;
798                     return FALSE;
799                 }
800
801                 /* First just match a string of min scans. */
802
803                 if (n < cc->min) {
804                     cc->cur = n;
805                     cc->lastloc = locinput;
806                     return regmatch(cc->scan);
807                 }
808
809                 /* Prefer next over scan for minimal matching. */
810
811                 if (cc->minmod) {
812                     regcc = cc->oldcc;
813                     ln = regcc->cur;
814                     if (regmatch(cc->next))
815                         return TRUE;    /* All done. */
816                     regcc->cur = ln;
817                     regcc = cc;
818
819                     if (n >= cc->max)   /* Maximum greed exceeded? */
820                         return FALSE;
821
822                     /* Try scanning more and see if it helps. */
823                     reginput = locinput;
824                     cc->cur = n;
825                     cc->lastloc = locinput;
826                     return regmatch(cc->scan);
827                 }
828
829                 /* Prefer scan over next for maximal matching. */
830
831                 if (n < cc->max) {      /* More greed allowed? */
832                     regcppush(cc->parenfloor);
833                     cc->cur = n;
834                     cc->lastloc = locinput;
835                     if (regmatch(cc->scan))
836                         return TRUE;
837                     regcppop();         /* Restore some previous $<digit>s? */
838                     reginput = locinput;
839                 }
840
841                 /* Failed deeper matches of scan, so see if this one works. */
842                 regcc = cc->oldcc;
843                 ln = regcc->cur;
844                 if (regmatch(cc->next))
845                     return TRUE;
846                 regcc->cur = ln;
847                 regcc = cc;
848                 return FALSE;
849             }
850             /* NOT REACHED */
851         case BRANCH: {
852                 if (OP(next) != BRANCH)   /* No choice. */
853                     next = NEXTOPER(scan);/* Avoid recursion. */
854                 else {
855                     do {
856                         reginput = locinput;
857                         if (regmatch(NEXTOPER(scan)))
858                             return 1;
859 #ifdef REGALIGN
860                         /*SUPPRESS 560*/
861                         if (n = NEXT(scan))
862                             scan += n;
863                         else
864                             scan = NULL;
865 #else
866                         scan = regnext(scan);
867 #endif
868                     } while (scan != NULL && OP(scan) == BRANCH);
869                     return 0;
870                     /* NOTREACHED */
871                 }
872             }
873             break;
874         case MINMOD:
875             minmod = 1;
876             break;
877         case CURLY:
878             ln = ARG1(scan);  /* min to match */
879             n  = ARG2(scan);  /* max to match */
880             scan = NEXTOPER(scan) + 4;
881             goto repeat;
882         case STAR:
883             ln = 0;
884             n = 32767;
885             scan = NEXTOPER(scan);
886             goto repeat;
887         case PLUS:
888             /*
889             * Lookahead to avoid useless match attempts
890             * when we know what character comes next.
891             */
892             ln = 1;
893             n = 32767;
894             scan = NEXTOPER(scan);
895           repeat:
896             if (OP(next) == EXACTLY)
897                 nextchar = *(OPERAND(next)+1);
898             else
899                 nextchar = -1000;
900             reginput = locinput;
901             if (minmod) {
902                 minmod = 0;
903                 if (ln && regrepeat(scan, ln) < ln)
904                     return 0;
905                 while (n >= ln) {
906                     /* If it could work, try it. */
907                     if (nextchar == -1000 || *reginput == nextchar)
908                         if (regmatch(next))
909                             return 1;
910                     /* Couldn't or didn't -- back up. */
911                     if (regrepeat(scan, 1)) {
912                         ln++;
913                         reginput = locinput + ln;
914                     }
915                     else
916                         return 0;
917                 }
918             }
919             else {
920                 n = regrepeat(scan, n);
921                 if (ln < n && regkind[(U8)OP(next)] == EOL &&
922                     (!multiline || OP(next) == SEOL))
923                     ln = n;                     /* why back off? */
924                 while (n >= ln) {
925                     /* If it could work, try it. */
926                     if (nextchar == -1000 || *reginput == nextchar)
927                         if (regmatch(next))
928                             return 1;
929                     /* Couldn't or didn't -- back up. */
930                     n--;
931                     reginput = locinput + n;
932                 }
933             }
934             return 0;
935         case SUCCEED:
936         case END:
937             reginput = locinput;        /* put where regtry can find it */
938             return 1;                   /* Success! */
939         case IFMATCH:
940             reginput = locinput;
941             scan = NEXTOPER(scan);
942             if (!regmatch(scan))
943                 return 0;
944             break;
945         case UNLESSM:
946             reginput = locinput;
947             scan = NEXTOPER(scan);
948             if (regmatch(scan))
949                 return 0;
950             break;
951         default:
952             fprintf(stderr, "%x %d\n",(unsigned)scan,scan[1]);
953             FAIL("regexp memory corruption");
954         }
955         scan = next;
956     }
957
958     /*
959     * We get here only if there's trouble -- normally "case END" is
960     * the terminating point.
961     */
962     FAIL("corrupted regexp pointers");
963     /*NOTREACHED*/
964     return 0;
965 }
966
967 /*
968  - regrepeat - repeatedly match something simple, report how many
969  */
970 /*
971  * [This routine now assumes that it will only match on things of length 1.
972  * That was true before, but now we assume scan - reginput is the count,
973  * rather than incrementing count on every character.]
974  */
975 static I32
976 regrepeat(p, max)
977 char *p;
978 I32 max;
979 {
980     register char *scan;
981     register char *opnd;
982     register I32 c;
983     register char *loceol = regeol;
984
985     scan = reginput;
986     if (max != 32767 && max < loceol - scan)
987       loceol = scan + max;
988     opnd = OPERAND(p);
989     switch (OP(p)) {
990     case ANY:
991         while (scan < loceol && *scan != '\n')
992             scan++;
993         break;
994     case SANY:
995         scan = loceol;
996         break;
997     case EXACTLY:               /* length of string is 1 */
998         opnd++;
999         while (scan < loceol && *opnd == *scan)
1000             scan++;
1001         break;
1002     case ANYOF:
1003         c = UCHARAT(scan);
1004         while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
1005             scan++;
1006             c = UCHARAT(scan);
1007         }
1008         break;
1009     case ALNUM:
1010         while (scan < loceol && isALNUM(*scan))
1011             scan++;
1012         break;
1013     case NALNUM:
1014         while (scan < loceol && !isALNUM(*scan))
1015             scan++;
1016         break;
1017     case SPACE:
1018         while (scan < loceol && isSPACE(*scan))
1019             scan++;
1020         break;
1021     case NSPACE:
1022         while (scan < loceol && !isSPACE(*scan))
1023             scan++;
1024         break;
1025     case DIGIT:
1026         while (scan < loceol && isDIGIT(*scan))
1027             scan++;
1028         break;
1029     case NDIGIT:
1030         while (scan < loceol && !isDIGIT(*scan))
1031             scan++;
1032         break;
1033     default:            /* Called on something of 0 width. */
1034         break;          /* So match right here or not at all. */
1035     }
1036
1037     c = scan - reginput;
1038     reginput = scan;
1039
1040     return(c);
1041 }
1042
1043 /*
1044  - regnext - dig the "next" pointer out of a node
1045  *
1046  * [Note, when REGALIGN is defined there are two places in regmatch()
1047  * that bypass this code for speed.]
1048  */
1049 char *
1050 regnext(p)
1051 register char *p;
1052 {
1053     register I32 offset;
1054
1055     if (p == &regdummy)
1056         return(NULL);
1057
1058     offset = NEXT(p);
1059     if (offset == 0)
1060         return(NULL);
1061
1062 #ifdef REGALIGN
1063     return(p+offset);
1064 #else
1065     if (OP(p) == BACK)
1066         return(p-offset);
1067     else
1068         return(p+offset);
1069 #endif
1070 }