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