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