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