This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
PATCH: bug in perlbug w.r.t. environment variables
[perl5.git] / regexec.c
CommitLineData
a0d0e21e
LW
1/* regexec.c
2 */
3
4/*
5 * "One Ring to rule them all, One Ring to find them..."
6 */
7
a687059c
LW
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
e50aee73
AD
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
f0fcb552 22/*SUPPRESS 112*/
a687059c 23/*
e50aee73 24 * pregcomp and pregexec -- regsub and regerror are not used in perl
a687059c
LW
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 ****
9607fc9c 45 **** Copyright (c) 1991-1997, Larry Wall
a687059c 46 ****
9ef589d8
LW
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.
a687059c
LW
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
a0d0e21e
LW
63static I32 regnarrate = 0;
64static char* regprogram = 0;
a687059c
LW
65#endif
66
a0d0e21e
LW
67/* Current curly descriptor */
68typedef struct curcur CURCUR;
69struct 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
81static CURCUR* regcc;
82
83typedef I32 CHECKPOINT;
84
55497cff
PP
85static CHECKPOINT regcppush _((I32 parenfloor));
86static char * regcppop _((void));
a0d0e21e 87
55497cff 88static CHECKPOINT
a0d0e21e
LW
89regcppush(parenfloor)
90I32 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
55497cff 110static char *
a0d0e21e
LW
111regcppop()
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
a687059c 139/*
e50aee73 140 * pregexec and friends
a687059c
LW
141 */
142
143/*
a687059c
LW
144 * Forwards.
145 */
a0d0e21e
LW
146
147static I32 regmatch _((char *prog));
148static I32 regrepeat _((char *p, I32 max));
149static I32 regtry _((regexp *prog, char *startpos));
bbce6d69
PP
150static bool reginclass _((char *p, I32 c));
151
152static bool regtainted; /* tainted information used? */
a687059c
LW
153
154/*
e50aee73 155 - pregexec - match a regexp against a string
a687059c 156 */
79072805 157I32
e50aee73 158pregexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
a687059c
LW
159register regexp *prog;
160char *stringarg;
161register char *strend; /* pointer to null at end of string */
162char *strbeg; /* real beginning of string */
79072805
LW
163I32 minend; /* end of match must be at least minend after stringarg */
164SV *screamer;
165I32 safebase; /* no need to remember string in subbase */
a687059c 166{
a0d0e21e 167 register char *s;
a0d0e21e
LW
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;
a687059c 174
a0d0e21e 175 cc.cur = 0;
4633a7c4 176 cc.oldcc = 0;
a0d0e21e
LW
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 }
bbce6d69 197
a0d0e21e 198 regprecomp = prog->precomp;
a0d0e21e
LW
199 /* Check validity of program. */
200 if (UCHARAT(prog->program) != MAGIC) {
201 FAIL("corrupted regexp program");
202 }
203
bbce6d69
PP
204 regnpar = prog->nparens;
205 regtainted = FALSE;
a0d0e21e
LW
206
207 /* If there is a "must appear" string, look for it. */
208 s = startpos;
209 if (prog->regmust != Nullsv &&
774d564b
PP
210 !(prog->reganch & ROPT_ANCH_GPOS) &&
211 (!(prog->reganch & ROPT_ANCH_BOL)
a0d0e21e
LW
212 || (multiline && prog->regback >= 0)) )
213 {
214 if (stringarg == strbeg && screamer) {
215 if (screamfirst[BmRARE(prog->regmust)] >= 0)
216 s = screaminstr(screamer,prog->regmust);
217 else
218 s = Nullch;
0a12ae7d 219 }
a0d0e21e
LW
220 else
221 s = fbm_instr((unsigned char*)s, (unsigned char*)strend,
222 prog->regmust);
223 if (!s) {
224 ++BmUSEFUL(prog->regmust); /* hooray */
225 goto phooey; /* not present */
a687059c 226 }
a0d0e21e
LW
227 else if (prog->regback >= 0) {
228 s -= prog->regback;
229 if (s < startpos)
230 s = startpos;
231 minlen = prog->regback + SvCUR(prog->regmust);
a687059c 232 }
a0d0e21e
LW
233 else if (!prog->naughty && --BmUSEFUL(prog->regmust) < 0) { /* boo */
234 SvREFCNT_dec(prog->regmust);
235 prog->regmust = Nullsv; /* disable regmust */
236 s = startpos;
237 }
238 else {
239 s = startpos;
240 minlen = SvCUR(prog->regmust);
a687059c 241 }
a0d0e21e 242 }
a687059c 243
a0d0e21e
LW
244 /* Mark beginning of line for ^ . */
245 regbol = startpos;
a687059c 246
a0d0e21e
LW
247 /* Mark end of line for $ (and such) */
248 regeol = strend;
a687059c 249
a0d0e21e
LW
250 /* see how far we have to get to not match where we matched before */
251 regtill = startpos+minend;
a687059c 252
a0d0e21e 253 /* Simplest case: anchored match need be tried only once. */
774d564b 254 /* [unless only anchor is BOL and multiline is set] */
a0d0e21e
LW
255 if (prog->reganch & ROPT_ANCH) {
256 if (regtry(prog, startpos))
257 goto got_it;
774d564b
PP
258 else if (!(prog->reganch & ROPT_ANCH_GPOS) &&
259 (multiline || (prog->reganch & ROPT_IMPLICIT)))
260 {
a0d0e21e
LW
261 if (minlen)
262 dontbother = minlen - 1;
263 strend -= dontbother;
264 /* for multiline we only have to try after newlines */
265 if (s > startpos)
266 s--;
267 while (s < strend) {
268 if (*s++ == '\n') {
269 if (s < strend && regtry(prog, s))
270 goto got_it;
271 }
35c8bce7 272 }
35c8bce7 273 }
a0d0e21e
LW
274 goto phooey;
275 }
35c8bce7 276
a0d0e21e
LW
277 /* Messy cases: unanchored match. */
278 if (prog->regstart) {
279 if (prog->reganch & ROPT_SKIP) { /* we have /x+whatever/ */
280 /* it must be a one character string */
bbce6d69 281 char ch = SvPVX(prog->regstart)[0];
a0d0e21e 282 while (s < strend) {
bbce6d69 283 if (*s == ch) {
a0d0e21e 284 if (regtry(prog, s))
a687059c 285 goto got_it;
a0d0e21e 286 s++;
bbce6d69 287 while (s < strend && *s == ch)
a0d0e21e 288 s++;
a687059c 289 }
a0d0e21e
LW
290 s++;
291 }
a687059c 292 }
47109bfb 293 else if (SvTYPE(prog->regstart) == SVt_PVBM) {
a0d0e21e
LW
294 /* We know what string it must start with. */
295 while ((s = fbm_instr((unsigned char*)s,
296 (unsigned char*)strend, prog->regstart)) != NULL)
297 {
298 if (regtry(prog, s))
299 goto got_it;
300 s++;
301 }
302 }
47109bfb 303 else { /* Optimized fbm_instr: */
a0d0e21e
LW
304 c = SvPVX(prog->regstart);
305 while ((s = ninstr(s, strend, c, c + SvCUR(prog->regstart))) != NULL)
306 {
307 if (regtry(prog, s))
308 goto got_it;
309 s++;
310 }
311 }
312 goto phooey;
313 }
314 /*SUPPRESS 560*/
315 if (c = prog->regstclass) {
316 I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
a687059c 317
a0d0e21e
LW
318 if (minlen)
319 dontbother = minlen - 1;
320 strend -= dontbother; /* don't bother with what can't match */
321 tmp = 1;
322 /* We know what class it must start with. */
323 switch (OP(c)) {
324 case ANYOF:
325 c = OPERAND(c);
326 while (s < strend) {
bbce6d69 327 if (reginclass(c, *s)) {
a0d0e21e
LW
328 if (tmp && regtry(prog, s))
329 goto got_it;
330 else
331 tmp = doevery;
a687059c 332 }
a0d0e21e
LW
333 else
334 tmp = 1;
335 s++;
336 }
337 break;
bbce6d69
PP
338 case BOUNDL:
339 regtainted = TRUE;
340 /* FALL THROUGH */
a0d0e21e
LW
341 case BOUND:
342 if (minlen)
343 dontbother++,strend--;
bbce6d69 344 tmp = (s != startpos) ? UCHARAT(s - 1) : regprev;
95bac841 345 tmp = ((OP(c) == BOUND ? isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
a0d0e21e 346 while (s < strend) {
95bac841 347 if (tmp == !(OP(c) == BOUND ? isALNUM(*s) : isALNUM_LC(*s))) {
a0d0e21e
LW
348 tmp = !tmp;
349 if (regtry(prog, s))
350 goto got_it;
a687059c 351 }
a0d0e21e
LW
352 s++;
353 }
354 if ((minlen || tmp) && regtry(prog,s))
355 goto got_it;
356 break;
bbce6d69
PP
357 case NBOUNDL:
358 regtainted = TRUE;
359 /* FALL THROUGH */
a0d0e21e
LW
360 case NBOUND:
361 if (minlen)
362 dontbother++,strend--;
bbce6d69 363 tmp = (s != startpos) ? UCHARAT(s - 1) : regprev;
95bac841 364 tmp = ((OP(c) == NBOUND ? isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
a0d0e21e 365 while (s < strend) {
95bac841 366 if (tmp == !(OP(c) == NBOUND ? isALNUM(*s) : isALNUM_LC(*s)))
a0d0e21e
LW
367 tmp = !tmp;
368 else if (regtry(prog, s))
369 goto got_it;
370 s++;
371 }
372 if ((minlen || !tmp) && regtry(prog,s))
373 goto got_it;
374 break;
375 case ALNUM:
376 while (s < strend) {
bbce6d69
PP
377 if (isALNUM(*s)) {
378 if (tmp && regtry(prog, s))
379 goto got_it;
380 else
381 tmp = doevery;
382 }
383 else
384 tmp = 1;
385 s++;
386 }
387 break;
388 case ALNUML:
389 regtainted = TRUE;
390 while (s < strend) {
391 if (isALNUM_LC(*s)) {
a0d0e21e
LW
392 if (tmp && regtry(prog, s))
393 goto got_it;
a687059c 394 else
a0d0e21e
LW
395 tmp = doevery;
396 }
397 else
398 tmp = 1;
399 s++;
400 }
401 break;
402 case NALNUM:
403 while (s < strend) {
bbce6d69
PP
404 if (!isALNUM(*s)) {
405 if (tmp && regtry(prog, s))
406 goto got_it;
407 else
408 tmp = doevery;
409 }
410 else
411 tmp = 1;
412 s++;
413 }
414 break;
415 case NALNUML:
416 regtainted = TRUE;
417 while (s < strend) {
418 if (!isALNUM_LC(*s)) {
a0d0e21e
LW
419 if (tmp && regtry(prog, s))
420 goto got_it;
a687059c 421 else
a0d0e21e 422 tmp = doevery;
a687059c 423 }
a0d0e21e
LW
424 else
425 tmp = 1;
426 s++;
427 }
428 break;
429 case SPACE:
430 while (s < strend) {
431 if (isSPACE(*s)) {
432 if (tmp && regtry(prog, s))
433 goto got_it;
434 else
435 tmp = doevery;
2304df62 436 }
a0d0e21e
LW
437 else
438 tmp = 1;
439 s++;
440 }
441 break;
bbce6d69
PP
442 case SPACEL:
443 regtainted = TRUE;
444 while (s < strend) {
445 if (isSPACE_LC(*s)) {
446 if (tmp && regtry(prog, s))
447 goto got_it;
448 else
449 tmp = doevery;
450 }
451 else
452 tmp = 1;
453 s++;
454 }
455 break;
a0d0e21e
LW
456 case NSPACE:
457 while (s < strend) {
458 if (!isSPACE(*s)) {
459 if (tmp && regtry(prog, s))
460 goto got_it;
461 else
462 tmp = doevery;
a687059c 463 }
a0d0e21e
LW
464 else
465 tmp = 1;
466 s++;
467 }
468 break;
bbce6d69
PP
469 case NSPACEL:
470 regtainted = TRUE;
471 while (s < strend) {
472 if (!isSPACE_LC(*s)) {
473 if (tmp && regtry(prog, s))
474 goto got_it;
475 else
476 tmp = doevery;
477 }
478 else
479 tmp = 1;
480 s++;
481 }
482 break;
a0d0e21e
LW
483 case DIGIT:
484 while (s < strend) {
485 if (isDIGIT(*s)) {
486 if (tmp && regtry(prog, s))
487 goto got_it;
488 else
489 tmp = doevery;
2b69d0c2 490 }
a0d0e21e
LW
491 else
492 tmp = 1;
493 s++;
494 }
495 break;
496 case NDIGIT:
497 while (s < strend) {
498 if (!isDIGIT(*s)) {
499 if (tmp && regtry(prog, s))
500 goto got_it;
501 else
502 tmp = doevery;
a687059c 503 }
a0d0e21e
LW
504 else
505 tmp = 1;
506 s++;
507 }
508 break;
a687059c 509 }
a0d0e21e
LW
510 }
511 else {
512 if (minlen)
513 dontbother = minlen - 1;
514 strend -= dontbother;
515 /* We don't know much -- general case. */
516 do {
517 if (regtry(prog, s))
518 goto got_it;
519 } while (s++ < strend);
520 }
521
522 /* Failure. */
523 goto phooey;
a687059c 524
a0d0e21e 525got_it:
420218e7 526 strend += dontbother; /* uncheat */
a0d0e21e
LW
527 prog->subbeg = strbeg;
528 prog->subend = strend;
bbce6d69 529 prog->exec_tainted = regtainted;
5f05dabc
PP
530
531 /* make sure $`, $&, $', and $digit will work later */
137443ea
PP
532 if (strbeg != prog->subbase) {
533 if (safebase) {
534 if (prog->subbase) {
535 Safefree(prog->subbase);
536 prog->subbase = Nullch;
537 }
538 }
539 else {
540 I32 i = strend - startpos + (stringarg - strbeg);
541 s = savepvn(strbeg, i);
542 Safefree(prog->subbase);
543 prog->subbase = s;
544 prog->subbeg = prog->subbase;
545 prog->subend = prog->subbase + i;
546 s = prog->subbase + (stringarg - strbeg);
547 for (i = 0; i <= prog->nparens; i++) {
548 if (prog->endp[i]) {
549 prog->startp[i] = s + (prog->startp[i] - startpos);
550 prog->endp[i] = s + (prog->endp[i] - startpos);
551 }
a0d0e21e
LW
552 }
553 }
a0d0e21e
LW
554 }
555 return 1;
556
557phooey:
a0d0e21e 558 return 0;
a687059c
LW
559}
560
561/*
562 - regtry - try match at specific point
563 */
79072805 564static I32 /* 0 failure, 1 success */
a0d0e21e 565regtry(prog, startpos)
a687059c 566regexp *prog;
a0d0e21e 567char *startpos;
a687059c 568{
a0d0e21e
LW
569 register I32 i;
570 register char **sp;
571 register char **ep;
572
573 reginput = startpos;
574 regstartp = prog->startp;
575 regendp = prog->endp;
576 reglastparen = &prog->lastparen;
577 prog->lastparen = 0;
578 regsize = 0;
579
580 sp = prog->startp;
581 ep = prog->endp;
582 if (prog->nparens) {
583 for (i = prog->nparens; i >= 0; i--) {
584 *sp++ = NULL;
585 *ep++ = NULL;
a687059c 586 }
a0d0e21e
LW
587 }
588 if (regmatch(prog->program + 1) && reginput >= regtill) {
589 prog->startp[0] = startpos;
590 prog->endp[0] = reginput;
591 return 1;
592 }
593 else
594 return 0;
a687059c
LW
595}
596
597/*
598 - regmatch - main matching routine
599 *
600 * Conceptually the strategy is simple: check to see whether the current
601 * node matches, call self recursively to see whether the rest matches,
602 * and then act accordingly. In practice we make some effort to avoid
603 * recursion, in particular by going through "ordinary" nodes (that don't
604 * need to know whether the rest of the match failed) by a loop instead of
605 * by recursion.
606 */
607/* [lwall] I've hoisted the register declarations to the outer block in order to
608 * maybe save a little bit of pushing and popping on the stack. It also takes
609 * advantage of machines that use a register save mask on subroutine entry.
610 */
79072805 611static I32 /* 0 failure, 1 success */
a687059c
LW
612regmatch(prog)
613char *prog;
614{
a0d0e21e
LW
615 register char *scan; /* Current node. */
616 char *next; /* Next node. */
617 register I32 nextchar;
618 register I32 n; /* no or next */
619 register I32 ln; /* len or last */
620 register char *s; /* operand or save */
621 register char *locinput = reginput;
bbce6d69 622 register I32 c1, c2; /* case fold search */
a0d0e21e 623 int minmod = 0;
4633a7c4
LW
624#ifdef DEBUGGING
625 static int regindent = 0;
626 regindent++;
627#endif
a0d0e21e 628
bbce6d69 629 nextchar = UCHARAT(locinput);
a0d0e21e
LW
630 scan = prog;
631 while (scan != NULL) {
a687059c 632#ifdef DEBUGGING
4633a7c4
LW
633#define sayYES goto yes
634#define sayNO goto no
635#define saySAME(x) if (x) goto yes; else goto no
636 if (regnarrate) {
46fc3d4c
PP
637 SV *prop = sv_newmortal();
638 regprop(prop, scan);
639 PerlIO_printf(Perl_debug_log, "%*s%2d%-8.8s\t<%.10s>\n",
640 regindent*2, "", scan - regprogram,
641 SvPVX(prop), locinput);
4633a7c4
LW
642 }
643#else
644#define sayYES return 1
645#define sayNO return 0
646#define saySAME(x) return x
a687059c
LW
647#endif
648
649#ifdef REGALIGN
a0d0e21e
LW
650 next = scan + NEXT(scan);
651 if (next == scan)
652 next = NULL;
a687059c 653#else
a0d0e21e 654 next = regnext(scan);
a687059c
LW
655#endif
656
a0d0e21e
LW
657 switch (OP(scan)) {
658 case BOL:
659 if (locinput == regbol
660 ? regprev == '\n'
661 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
662 {
663 /* regtill = regbol; */
664 break;
665 }
4633a7c4 666 sayNO;
a0d0e21e
LW
667 case MBOL:
668 if (locinput == regbol
669 ? regprev == '\n'
670 : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
671 {
672 break;
673 }
4633a7c4 674 sayNO;
a0d0e21e
LW
675 case SBOL:
676 if (locinput == regbol && regprev == '\n')
677 break;
4633a7c4 678 sayNO;
774d564b 679 case GPOS:
a0d0e21e
LW
680 if (locinput == regbol)
681 break;
4633a7c4 682 sayNO;
a0d0e21e
LW
683 case EOL:
684 if (multiline)
685 goto meol;
686 else
687 goto seol;
688 case MEOL:
689 meol:
690 if ((nextchar || locinput < regeol) && nextchar != '\n')
4633a7c4 691 sayNO;
a0d0e21e
LW
692 break;
693 case SEOL:
694 seol:
695 if ((nextchar || locinput < regeol) && nextchar != '\n')
4633a7c4 696 sayNO;
a0d0e21e 697 if (regeol - locinput > 1)
4633a7c4 698 sayNO;
a0d0e21e
LW
699 break;
700 case SANY:
701 if (!nextchar && locinput >= regeol)
4633a7c4 702 sayNO;
bbce6d69 703 nextchar = UCHARAT(++locinput);
a0d0e21e
LW
704 break;
705 case ANY:
706 if (!nextchar && locinput >= regeol || nextchar == '\n')
4633a7c4 707 sayNO;
bbce6d69 708 nextchar = UCHARAT(++locinput);
a0d0e21e 709 break;
bbce6d69 710 case EXACT:
a0d0e21e
LW
711 s = OPERAND(scan);
712 ln = *s++;
713 /* Inline the first character, for speed. */
95bac841 714 if (UCHARAT(s) != nextchar)
4633a7c4 715 sayNO;
a0d0e21e 716 if (regeol - locinput < ln)
4633a7c4 717 sayNO;
36477c24 718 if (ln > 1 && memNE(s, locinput, ln))
4633a7c4 719 sayNO;
a0d0e21e 720 locinput += ln;
bbce6d69
PP
721 nextchar = UCHARAT(locinput);
722 break;
723 case EXACTFL:
724 regtainted = TRUE;
725 /* FALL THROUGH */
726 case EXACTF:
727 s = OPERAND(scan);
728 ln = *s++;
729 /* Inline the first character, for speed. */
730 if (UCHARAT(s) != nextchar &&
731 UCHARAT(s) != ((OP(scan) == EXACTF)
732 ? fold : fold_locale)[nextchar])
733 sayNO;
734 if (regeol - locinput < ln)
735 sayNO;
5f05dabc
PP
736 if (ln > 1 && (OP(scan) == EXACTF
737 ? ibcmp(s, locinput, ln)
738 : ibcmp_locale(s, locinput, ln)))
bbce6d69
PP
739 sayNO;
740 locinput += ln;
741 nextchar = UCHARAT(locinput);
a0d0e21e
LW
742 break;
743 case ANYOF:
744 s = OPERAND(scan);
745 if (nextchar < 0)
746 nextchar = UCHARAT(locinput);
bbce6d69 747 if (!reginclass(s, nextchar))
4633a7c4 748 sayNO;
a0d0e21e 749 if (!nextchar && locinput >= regeol)
4633a7c4 750 sayNO;
bbce6d69 751 nextchar = UCHARAT(++locinput);
a0d0e21e 752 break;
bbce6d69
PP
753 case ALNUML:
754 regtainted = TRUE;
755 /* FALL THROUGH */
a0d0e21e
LW
756 case ALNUM:
757 if (!nextchar)
4633a7c4 758 sayNO;
bbce6d69
PP
759 if (!(OP(scan) == ALNUM
760 ? isALNUM(nextchar) : isALNUM_LC(nextchar)))
4633a7c4 761 sayNO;
bbce6d69 762 nextchar = UCHARAT(++locinput);
a0d0e21e 763 break;
bbce6d69
PP
764 case NALNUML:
765 regtainted = TRUE;
766 /* FALL THROUGH */
a0d0e21e
LW
767 case NALNUM:
768 if (!nextchar && locinput >= regeol)
4633a7c4 769 sayNO;
bbce6d69
PP
770 if (OP(scan) == NALNUM
771 ? isALNUM(nextchar) : isALNUM_LC(nextchar))
4633a7c4 772 sayNO;
bbce6d69 773 nextchar = UCHARAT(++locinput);
a0d0e21e 774 break;
bbce6d69
PP
775 case BOUNDL:
776 case NBOUNDL:
777 regtainted = TRUE;
778 /* FALL THROUGH */
a0d0e21e 779 case BOUND:
bbce6d69
PP
780 case NBOUND:
781 /* was last char in word? */
782 ln = (locinput != regbol) ? UCHARAT(locinput - 1) : regprev;
783 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
784 ln = isALNUM(ln);
785 n = isALNUM(nextchar);
786 }
787 else {
788 ln = isALNUM_LC(ln);
789 n = isALNUM_LC(nextchar);
790 }
95bac841 791 if (((!ln) == (!n)) == (OP(scan) == BOUND || OP(scan) == BOUNDL))
4633a7c4 792 sayNO;
a0d0e21e 793 break;
bbce6d69
PP
794 case SPACEL:
795 regtainted = TRUE;
796 /* FALL THROUGH */
a0d0e21e
LW
797 case SPACE:
798 if (!nextchar && locinput >= regeol)
4633a7c4 799 sayNO;
bbce6d69
PP
800 if (!(OP(scan) == SPACE
801 ? isSPACE(nextchar) : isSPACE_LC(nextchar)))
4633a7c4 802 sayNO;
bbce6d69 803 nextchar = UCHARAT(++locinput);
a0d0e21e 804 break;
bbce6d69
PP
805 case NSPACEL:
806 regtainted = TRUE;
807 /* FALL THROUGH */
a0d0e21e
LW
808 case NSPACE:
809 if (!nextchar)
4633a7c4 810 sayNO;
bbce6d69
PP
811 if (OP(scan) == SPACE
812 ? isSPACE(nextchar) : isSPACE_LC(nextchar))
4633a7c4 813 sayNO;
bbce6d69 814 nextchar = UCHARAT(++locinput);
a0d0e21e
LW
815 break;
816 case DIGIT:
817 if (!isDIGIT(nextchar))
4633a7c4 818 sayNO;
bbce6d69 819 nextchar = UCHARAT(++locinput);
a0d0e21e
LW
820 break;
821 case NDIGIT:
822 if (!nextchar && locinput >= regeol)
4633a7c4 823 sayNO;
a0d0e21e 824 if (isDIGIT(nextchar))
4633a7c4 825 sayNO;
bbce6d69 826 nextchar = UCHARAT(++locinput);
a0d0e21e
LW
827 break;
828 case REF:
829 n = ARG1(scan); /* which paren pair */
830 s = regstartp[n];
831 if (!s)
4633a7c4 832 sayNO;
a0d0e21e 833 if (!regendp[n])
4633a7c4 834 sayNO;
a0d0e21e
LW
835 if (s == regendp[n])
836 break;
837 /* Inline the first character, for speed. */
95bac841 838 if (UCHARAT(s) != nextchar)
4633a7c4 839 sayNO;
a0d0e21e
LW
840 ln = regendp[n] - s;
841 if (locinput + ln > regeol)
4633a7c4 842 sayNO;
36477c24 843 if (ln > 1 && memNE(s, locinput, ln))
4633a7c4 844 sayNO;
a0d0e21e 845 locinput += ln;
bbce6d69 846 nextchar = UCHARAT(locinput);
a0d0e21e
LW
847 break;
848
849 case NOTHING:
850 break;
851 case BACK:
852 break;
853 case OPEN:
854 n = ARG1(scan); /* which paren pair */
855 regstartp[n] = locinput;
856 if (n > regsize)
857 regsize = n;
858 break;
859 case CLOSE:
860 n = ARG1(scan); /* which paren pair */
861 regendp[n] = locinput;
862 if (n > *reglastparen)
863 *reglastparen = n;
864 break;
865 case CURLYX: {
866 CURCUR cc;
867 CHECKPOINT cp = savestack_ix;
868 cc.oldcc = regcc;
869 regcc = &cc;
870 cc.parenfloor = *reglastparen;
871 cc.cur = -1;
872 cc.min = ARG1(scan);
873 cc.max = ARG2(scan);
874 cc.scan = NEXTOPER(scan) + 4;
875 cc.next = next;
876 cc.minmod = minmod;
877 cc.lastloc = 0;
878 reginput = locinput;
879 n = regmatch(PREVOPER(next)); /* start on the WHILEM */
880 regcpblow(cp);
881 regcc = cc.oldcc;
4633a7c4 882 saySAME(n);
a0d0e21e
LW
883 }
884 /* NOT REACHED */
885 case WHILEM: {
886 /*
887 * This is really hard to understand, because after we match
888 * what we're trying to match, we must make sure the rest of
889 * the RE is going to match for sure, and to do that we have
890 * to go back UP the parse tree by recursing ever deeper. And
891 * if it fails, we have to reset our parent's current state
892 * that we can try again after backing off.
893 */
894
5f05dabc 895 CHECKPOINT cp;
a0d0e21e 896 CURCUR* cc = regcc;
4633a7c4 897 n = cc->cur + 1; /* how many we know we matched */
a0d0e21e
LW
898 reginput = locinput;
899
4633a7c4
LW
900#ifdef DEBUGGING
901 if (regnarrate)
68dc0745
PP
902 PerlIO_printf(Perl_debug_log, "%*s %ld %lx\n", regindent*2, "",
903 (long)n, (long)cc);
4633a7c4
LW
904#endif
905
a0d0e21e
LW
906 /* If degenerate scan matches "", assume scan done. */
907
579cf2c3 908 if (locinput == cc->lastloc && n >= cc->min) {
a0d0e21e
LW
909 regcc = cc->oldcc;
910 ln = regcc->cur;
911 if (regmatch(cc->next))
4633a7c4 912 sayYES;
a0d0e21e
LW
913 regcc->cur = ln;
914 regcc = cc;
4633a7c4 915 sayNO;
a0d0e21e
LW
916 }
917
918 /* First just match a string of min scans. */
919
920 if (n < cc->min) {
921 cc->cur = n;
922 cc->lastloc = locinput;
4633a7c4
LW
923 if (regmatch(cc->scan))
924 sayYES;
925 cc->cur = n - 1;
926 sayNO;
a0d0e21e
LW
927 }
928
929 /* Prefer next over scan for minimal matching. */
930
931 if (cc->minmod) {
932 regcc = cc->oldcc;
933 ln = regcc->cur;
5f05dabc
PP
934 cp = regcppush(cc->parenfloor);
935 if (regmatch(cc->next)) {
936 regcpblow(cp);
4633a7c4 937 sayYES; /* All done. */
5f05dabc
PP
938 }
939 regcppop();
a0d0e21e
LW
940 regcc->cur = ln;
941 regcc = cc;
942
943 if (n >= cc->max) /* Maximum greed exceeded? */
4633a7c4 944 sayNO;
a687059c 945
a0d0e21e
LW
946 /* Try scanning more and see if it helps. */
947 reginput = locinput;
948 cc->cur = n;
949 cc->lastloc = locinput;
5f05dabc
PP
950 cp = regcppush(cc->parenfloor);
951 if (regmatch(cc->scan)) {
952 regcpblow(cp);
4633a7c4 953 sayYES;
5f05dabc
PP
954 }
955 regcppop();
4633a7c4
LW
956 cc->cur = n - 1;
957 sayNO;
a0d0e21e
LW
958 }
959
960 /* Prefer scan over next for maximal matching. */
961
962 if (n < cc->max) { /* More greed allowed? */
5f05dabc 963 cp = regcppush(cc->parenfloor);
a0d0e21e
LW
964 cc->cur = n;
965 cc->lastloc = locinput;
5f05dabc
PP
966 if (regmatch(cc->scan)) {
967 regcpblow(cp);
4633a7c4 968 sayYES;
5f05dabc 969 }
a0d0e21e
LW
970 regcppop(); /* Restore some previous $<digit>s? */
971 reginput = locinput;
972 }
973
974 /* Failed deeper matches of scan, so see if this one works. */
975 regcc = cc->oldcc;
976 ln = regcc->cur;
977 if (regmatch(cc->next))
4633a7c4 978 sayYES;
a0d0e21e
LW
979 regcc->cur = ln;
980 regcc = cc;
4633a7c4
LW
981 cc->cur = n - 1;
982 sayNO;
a0d0e21e
LW
983 }
984 /* NOT REACHED */
985 case BRANCH: {
986 if (OP(next) != BRANCH) /* No choice. */
987 next = NEXTOPER(scan);/* Avoid recursion. */
988 else {
748a9306 989 int lastparen = *reglastparen;
a0d0e21e
LW
990 do {
991 reginput = locinput;
992 if (regmatch(NEXTOPER(scan)))
4633a7c4 993 sayYES;
748a9306
LW
994 for (n = *reglastparen; n > lastparen; n--)
995 regendp[n] = 0;
996 *reglastparen = n;
997
a687059c 998#ifdef REGALIGN
a0d0e21e
LW
999 /*SUPPRESS 560*/
1000 if (n = NEXT(scan))
1001 scan += n;
1002 else
1003 scan = NULL;
a687059c 1004#else
a0d0e21e 1005 scan = regnext(scan);
79072805 1006#endif
a0d0e21e 1007 } while (scan != NULL && OP(scan) == BRANCH);
4633a7c4 1008 sayNO;
a0d0e21e 1009 /* NOTREACHED */
a687059c 1010 }
a0d0e21e
LW
1011 }
1012 break;
1013 case MINMOD:
1014 minmod = 1;
1015 break;
1016 case CURLY:
1017 ln = ARG1(scan); /* min to match */
1018 n = ARG2(scan); /* max to match */
1019 scan = NEXTOPER(scan) + 4;
1020 goto repeat;
1021 case STAR:
1022 ln = 0;
1023 n = 32767;
1024 scan = NEXTOPER(scan);
1025 goto repeat;
1026 case PLUS:
1027 /*
1028 * Lookahead to avoid useless match attempts
1029 * when we know what character comes next.
1030 */
1031 ln = 1;
1032 n = 32767;
1033 scan = NEXTOPER(scan);
1034 repeat:
bbce6d69
PP
1035 if (regkind[(U8)OP(next)] == EXACT) {
1036 c1 = UCHARAT(OPERAND(next) + 1);
1037 if (OP(next) == EXACTF)
1038 c2 = fold[c1];
1039 else if (OP(next) == EXACTFL)
1040 c2 = fold_locale[c1];
1041 else
1042 c2 = c1;
1043 }
a0d0e21e 1044 else
bbce6d69 1045 c1 = c2 = -1000;
a0d0e21e
LW
1046 reginput = locinput;
1047 if (minmod) {
1048 minmod = 0;
1049 if (ln && regrepeat(scan, ln) < ln)
4633a7c4 1050 sayNO;
8e07c86e 1051 while (n >= ln || (n == 32767 && ln > 0)) { /* ln overflow ? */
a0d0e21e 1052 /* If it could work, try it. */
bbce6d69
PP
1053 if (c1 == -1000 ||
1054 UCHARAT(reginput) == c1 ||
1055 UCHARAT(reginput) == c2)
1056 {
a0d0e21e 1057 if (regmatch(next))
4633a7c4 1058 sayYES;
bbce6d69 1059 }
a0d0e21e 1060 /* Couldn't or didn't -- back up. */
748a9306 1061 reginput = locinput + ln;
a0d0e21e
LW
1062 if (regrepeat(scan, 1)) {
1063 ln++;
1064 reginput = locinput + ln;
1065 }
1066 else
4633a7c4 1067 sayNO;
a0d0e21e
LW
1068 }
1069 }
1070 else {
1071 n = regrepeat(scan, n);
1072 if (ln < n && regkind[(U8)OP(next)] == EOL &&
1073 (!multiline || OP(next) == SEOL))
1074 ln = n; /* why back off? */
1075 while (n >= ln) {
1076 /* If it could work, try it. */
bbce6d69
PP
1077 if (c1 == -1000 ||
1078 UCHARAT(reginput) == c1 ||
1079 UCHARAT(reginput) == c2)
1080 {
a0d0e21e 1081 if (regmatch(next))
4633a7c4 1082 sayYES;
bbce6d69 1083 }
a0d0e21e
LW
1084 /* Couldn't or didn't -- back up. */
1085 n--;
1086 reginput = locinput + n;
1087 }
1088 }
4633a7c4 1089 sayNO;
a0d0e21e
LW
1090 case SUCCEED:
1091 case END:
1092 reginput = locinput; /* put where regtry can find it */
4633a7c4 1093 sayYES; /* Success! */
a0d0e21e
LW
1094 case IFMATCH:
1095 reginput = locinput;
1096 scan = NEXTOPER(scan);
1097 if (!regmatch(scan))
4633a7c4 1098 sayNO;
a0d0e21e
LW
1099 break;
1100 case UNLESSM:
1101 reginput = locinput;
1102 scan = NEXTOPER(scan);
1103 if (regmatch(scan))
4633a7c4 1104 sayNO;
a0d0e21e
LW
1105 break;
1106 default:
c030ccd9
CS
1107 PerlIO_printf(PerlIO_stderr(), "%lx %d\n",
1108 (unsigned long)scan, scan[1]);
a0d0e21e 1109 FAIL("regexp memory corruption");
a687059c 1110 }
a0d0e21e
LW
1111 scan = next;
1112 }
a687059c 1113
a0d0e21e
LW
1114 /*
1115 * We get here only if there's trouble -- normally "case END" is
1116 * the terminating point.
1117 */
1118 FAIL("corrupted regexp pointers");
1119 /*NOTREACHED*/
4633a7c4
LW
1120 sayNO;
1121
1122yes:
1123#ifdef DEBUGGING
1124 regindent--;
1125#endif
1126 return 1;
1127
1128no:
1129#ifdef DEBUGGING
1130 regindent--;
1131#endif
a0d0e21e 1132 return 0;
a687059c
LW
1133}
1134
1135/*
1136 - regrepeat - repeatedly match something simple, report how many
1137 */
1138/*
1139 * [This routine now assumes that it will only match on things of length 1.
1140 * That was true before, but now we assume scan - reginput is the count,
1141 * rather than incrementing count on every character.]
1142 */
79072805 1143static I32
00bf170e 1144regrepeat(p, max)
a687059c 1145char *p;
79072805 1146I32 max;
a687059c 1147{
a0d0e21e
LW
1148 register char *scan;
1149 register char *opnd;
1150 register I32 c;
1151 register char *loceol = regeol;
1152
1153 scan = reginput;
1154 if (max != 32767 && max < loceol - scan)
1155 loceol = scan + max;
1156 opnd = OPERAND(p);
1157 switch (OP(p)) {
1158 case ANY:
1159 while (scan < loceol && *scan != '\n')
1160 scan++;
1161 break;
1162 case SANY:
1163 scan = loceol;
1164 break;
bbce6d69
PP
1165 case EXACT: /* length of string is 1 */
1166 c = UCHARAT(++opnd);
1167 while (scan < loceol && UCHARAT(scan) == c)
1168 scan++;
1169 break;
1170 case EXACTF: /* length of string is 1 */
1171 c = UCHARAT(++opnd);
1172 while (scan < loceol &&
1173 (UCHARAT(scan) == c || UCHARAT(scan) == fold[c]))
1174 scan++;
1175 break;
1176 case EXACTFL: /* length of string is 1 */
1177 regtainted = TRUE;
1178 c = UCHARAT(++opnd);
1179 while (scan < loceol &&
1180 (UCHARAT(scan) == c || UCHARAT(scan) == fold_locale[c]))
a0d0e21e
LW
1181 scan++;
1182 break;
1183 case ANYOF:
bbce6d69 1184 while (scan < loceol && reginclass(opnd, *scan))
a0d0e21e 1185 scan++;
a0d0e21e
LW
1186 break;
1187 case ALNUM:
1188 while (scan < loceol && isALNUM(*scan))
1189 scan++;
1190 break;
bbce6d69
PP
1191 case ALNUML:
1192 regtainted = TRUE;
1193 while (scan < loceol && isALNUM_LC(*scan))
1194 scan++;
1195 break;
a0d0e21e
LW
1196 case NALNUM:
1197 while (scan < loceol && !isALNUM(*scan))
1198 scan++;
1199 break;
bbce6d69
PP
1200 case NALNUML:
1201 regtainted = TRUE;
1202 while (scan < loceol && !isALNUM_LC(*scan))
1203 scan++;
1204 break;
a0d0e21e
LW
1205 case SPACE:
1206 while (scan < loceol && isSPACE(*scan))
1207 scan++;
1208 break;
bbce6d69
PP
1209 case SPACEL:
1210 regtainted = TRUE;
1211 while (scan < loceol && isSPACE_LC(*scan))
1212 scan++;
1213 break;
a0d0e21e
LW
1214 case NSPACE:
1215 while (scan < loceol && !isSPACE(*scan))
1216 scan++;
1217 break;
bbce6d69
PP
1218 case NSPACEL:
1219 regtainted = TRUE;
1220 while (scan < loceol && !isSPACE_LC(*scan))
1221 scan++;
1222 break;
a0d0e21e
LW
1223 case DIGIT:
1224 while (scan < loceol && isDIGIT(*scan))
1225 scan++;
1226 break;
1227 case NDIGIT:
1228 while (scan < loceol && !isDIGIT(*scan))
1229 scan++;
1230 break;
1231 default: /* Called on something of 0 width. */
1232 break; /* So match right here or not at all. */
1233 }
a687059c 1234
a0d0e21e
LW
1235 c = scan - reginput;
1236 reginput = scan;
a687059c 1237
a0d0e21e 1238 return(c);
a687059c
LW
1239}
1240
1241/*
bbce6d69
PP
1242 - regclass - determine if a character falls into a character class
1243 */
1244
1245static bool
1246reginclass(p, c)
1247register char *p;
1248register I32 c;
1249{
1250 char flags = *p;
1251 bool match = FALSE;
1252
1253 c &= 0xFF;
1254 if (p[1 + (c >> 3)] & (1 << (c & 7)))
1255 match = TRUE;
1256 else if (flags & ANYOF_FOLD) {
1257 I32 cf;
1258 if (flags & ANYOF_LOCALE) {
1259 regtainted = TRUE;
1260 cf = fold_locale[c];
1261 }
1262 else
1263 cf = fold[c];
1264 if (p[1 + (cf >> 3)] & (1 << (cf & 7)))
1265 match = TRUE;
1266 }
1267
1268 if (!match && (flags & ANYOF_ISA)) {
1269 regtainted = TRUE;
1270
1271 if (((flags & ANYOF_ALNUML) && isALNUM_LC(c)) ||
1272 ((flags & ANYOF_NALNUML) && !isALNUM_LC(c)) ||
1273 ((flags & ANYOF_SPACEL) && isSPACE_LC(c)) ||
1274 ((flags & ANYOF_NSPACEL) && !isSPACE_LC(c)))
1275 {
1276 match = TRUE;
1277 }
1278 }
1279
1280 return match ^ ((flags & ANYOF_INVERT) != 0);
1281}
1282
1283/*
a687059c
LW
1284 - regnext - dig the "next" pointer out of a node
1285 *
1286 * [Note, when REGALIGN is defined there are two places in regmatch()
1287 * that bypass this code for speed.]
1288 */
1289char *
1290regnext(p)
1291register char *p;
1292{
a0d0e21e 1293 register I32 offset;
a687059c 1294
a0d0e21e
LW
1295 if (p == &regdummy)
1296 return(NULL);
a687059c 1297
a0d0e21e
LW
1298 offset = NEXT(p);
1299 if (offset == 0)
1300 return(NULL);
a687059c
LW
1301
1302#ifdef REGALIGN
a0d0e21e 1303 return(p+offset);
a687059c 1304#else
a0d0e21e
LW
1305 if (OP(p) == BACK)
1306 return(p-offset);
1307 else
1308 return(p+offset);
a687059c
LW
1309#endif
1310}