GnuRegex.c
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3 *
4 * Squid software is distributed under GPLv2+ license and includes
5 * contributions from numerous individuals and organizations.
6 * Please see the COPYING and CONTRIBUTORS files for details.
7 */
8
9/* Extended regular expression matching and search library,
10 * version 0.12.
11 * (Implements POSIX draft P10003.2/D11.2, except for
12 * internationalization features.)
13 *
14 * Copyright (C) 1993 Free Software Foundation, Inc.
15 *
16 * This program is free software; you can redistribute it and/or modify
17 * it under the terms of the GNU General Public License as published by
18 * the Free Software Foundation; either version 2, or (at your option)
19 * any later version.
20 *
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * You should have received a copy of the GNU General Public License
27 * along with this program; if not, write to the Free Software
28 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. */
29
30/* AIX requires this to be the first thing in the file. */
31#if defined (_AIX) && !defined(REGEX_MALLOC)
32#pragma alloca
33#endif
34
35#ifndef _GNU_SOURCE
36#define _GNU_SOURCE 1
37#endif
38
39#include "squid.h"
40
41#if USE_GNUREGEX /* only if squid needs it. Usually not */
42
43/* Starting with v12.1, GCC warns of various problems with this ancient code. */
44/* GCC versions prior to v12.1 do not support these pragmas. */
45#if (__GNUC__ == 12 && __GNUC_MINOR__ >= 1) || (__GNUC__ > 12)
46#pragma GCC diagnostic ignored "-Warray-bounds"
47#pragma GCC diagnostic ignored "-Wuse-after-free"
48#endif
49
50#if !HAVE_ALLOCA
51#define REGEX_MALLOC 1
52#endif
53
54/* We used to test for `BSTRING' here, but only GCC and Emacs define
55 * `BSTRING', as far as I know, and neither of them use this code. */
56#if HAVE_STRING_H || STDC_HEADERS
57#include <string.h>
58#else
59#include <strings.h>
60#endif
61
62/* Define the syntax stuff for <, >, etc. */
63
64/* This must be nonzero for the wordchar and notwordchar pattern
65 * commands in re_match_2. */
66#ifndef Sword
67#define Sword 1
68#endif
69
70#ifdef SYNTAX_TABLE
71
72extern char *re_syntax_table;
73
74#else /* not SYNTAX_TABLE */
75
76/* How many characters in the character set. */
77#define CHAR_SET_SIZE 256
78
80
81static void
83{
84 register int c;
85 static int done = 0;
86
87 if (done)
88 return;
89
90 memset(re_syntax_table, 0, sizeof re_syntax_table);
91
92 for (c = 'a'; c <= 'z'; c++)
94
95 for (c = 'A'; c <= 'Z'; c++)
97
98 for (c = '0'; c <= '9'; c++)
100
101 re_syntax_table['_'] = Sword;
102
103 done = 1;
104}
105
106#endif /* not SYNTAX_TABLE */
107
108/* Get the interface, including the syntax bits. */
109#include "compat/GnuRegex.h"
110
111/* Compile a fastmap for the compiled pattern in BUFFER; used to
112 * accelerate searches. Return 0 if successful and -2 if was an
113 * internal error. */
114static int re_compile_fastmap(struct re_pattern_buffer * buffer);
115
116/* Search in the string STRING (with length LENGTH) for the pattern
117 * compiled into BUFFER. Start searching at position START, for RANGE
118 * characters. Return the starting position of the match, -1 for no
119 * match, or -2 for an internal error. Also return register
120 * information in REGS (if REGS and BUFFER->no_sub are nonzero). */
121static int re_search(struct re_pattern_buffer * buffer, const char *string,
122 int length, int start, int range, struct re_registers * regs);
123
124/* Like `re_search', but search in the concatenation of STRING1 and
125 * STRING2. Also, stop searching at index START + STOP. */
126static int re_search_2(struct re_pattern_buffer * buffer, const char *string1,
127 int length1, const char *string2, int length2,
128 int start, int range, struct re_registers * regs, int stop);
129
130/* Like `re_search_2', but return how many characters in STRING the regexp
131 * in BUFFER matched, starting at position START. */
132static int re_match_2(struct re_pattern_buffer * buffer, const char *string1,
133 int length1, const char *string2, int length2,
134 int start, struct re_registers * regs, int stop);
135
136/* isalpha etc. are used for the character classes. */
137#include <ctype.h>
138
139#ifndef isascii
140#define isascii(c) 1
141#endif
142
143#ifdef isblank
144#define ISBLANK(c) (isascii ((unsigned char)c) && isblank ((unsigned char)c))
145#else
146#define ISBLANK(c) ((c) == ' ' || (c) == '\t')
147#endif
148#ifdef isgraph
149#define ISGRAPH(c) (isascii ((unsigned char)c) && isgraph ((unsigned char)c))
150#else
151#define ISGRAPH(c) (isascii ((unsigned char)c) && isprint ((unsigned char)c) && !isspace ((unsigned char)c))
152#endif
153
154#define ISPRINT(c) (isascii ((unsigned char)c) && isprint ((unsigned char)c))
155#define ISDIGIT(c) (isascii ((unsigned char)c) && isdigit ((unsigned char)c))
156#define ISALNUM(c) (isascii ((unsigned char)c) && isalnum ((unsigned char)c))
157#define ISALPHA(c) (isascii ((unsigned char)c) && isalpha ((unsigned char)c))
158#define ISCNTRL(c) (isascii ((unsigned char)c) && iscntrl ((unsigned char)c))
159#define ISLOWER(c) (isascii ((unsigned char)c) && islower ((unsigned char)c))
160#define ISPUNCT(c) (isascii ((unsigned char)c) && ispunct ((unsigned char)c))
161#define ISSPACE(c) (isascii ((unsigned char)c) && isspace ((unsigned char)c))
162#define ISUPPER(c) (isascii ((unsigned char)c) && isupper ((unsigned char)c))
163#define ISXDIGIT(c) (isascii ((unsigned char)c) && isxdigit ((unsigned char)c))
164
165/* We remove any previous definition of `SIGN_EXTEND_CHAR',
166 * since ours (we hope) works properly with all combinations of
167 * machines, compilers, `char' and `unsigned char' argument types.
168 * (Per Bothner suggested the basic approach.) */
169#undef SIGN_EXTEND_CHAR
170#ifdef __STDC__
171#define SIGN_EXTEND_CHAR(c) ((signed char) (c))
172#else /* not __STDC__ */
173/* As in Harbison and Steele. */
174#define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
175#endif
176
177/* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
178 * use `alloca' instead of `malloc'. This is because using malloc in
179 * re_search* or re_match* could cause memory leaks when C-g is used in
180 * Emacs; also, malloc is slower and causes storage fragmentation. On
181 * the other hand, malloc is more portable, and easier to debug.
182 *
183 * Because we sometimes use alloca, some routines have to be macros,
184 * not functions -- `alloca'-allocated space disappears at the end of the
185 * function it is called in. */
186
187#ifdef REGEX_MALLOC
188
189#define REGEX_ALLOCATE malloc
190#define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
191
192#else /* not REGEX_MALLOC */
193
194/* Emacs already defines alloca, sometimes. */
195#ifndef alloca
196
197/* Make alloca work the best possible way. */
198#ifdef __GNUC__
199#define alloca __builtin_alloca
200#else /* not __GNUC__ */
201#if HAVE_ALLOCA_H
202#include <alloca.h>
203#else /* not __GNUC__ or HAVE_ALLOCA_H */
204#ifndef _AIX /* Already did AIX, up at the top. */
205char *alloca();
206#endif /* not _AIX */
207#endif /* not HAVE_ALLOCA_H */
208#endif /* not __GNUC__ */
209
210#endif /* not alloca */
211
212#define REGEX_ALLOCATE alloca
213
214/* Assumes a `char *destination' variable. */
215#define REGEX_REALLOCATE(source, osize, nsize) \
216 (destination = (char *) alloca (nsize), \
217 memcpy (destination, source, osize), \
218 destination)
219
220#endif /* not REGEX_MALLOC */
221
222/* True if `size1' is non-NULL and PTR is pointing anywhere inside
223 * `string1' or just past its end. This works if PTR is NULL, which is
224 * a good thing. */
225#define FIRST_STRING_P(ptr) \
226 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
227
228/* (Re)Allocate N items of type T using malloc, or fail. */
229#define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
230#define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
231#define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
232
233#define BYTEWIDTH 8 /* In bits. */
234
235#define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
236
237#if !defined(__MINGW32__) /* MinGW defines boolean */
238typedef char boolean;
239#endif
240#define false 0
241#define true 1
242
243/* These are the command codes that appear in compiled regular
244 * expressions. Some opcodes are followed by argument bytes. A
245 * command code can specify any interpretation whatsoever for its
246 * arguments. Zero bytes may appear in the compiled regular expression.
247 *
248 * The value of `exactn' is needed in search.c (search_buffer) in Emacs.
249 * So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
250 * `exactn' we use here must also be 1. */
251
252typedef enum {
253 no_op = 0,
254
255 /* Followed by one byte giving n, then by n literal bytes. */
257
258 /* Matches any (more or less) character. */
260
261 /* Matches any one char belonging to specified set. First
262 * following byte is number of bitmap bytes. Then come bytes
263 * for a bitmap saying which chars are in. Bits in each byte
264 * are ordered low-bit-first. A character is in the set if its
265 * bit is 1. A character too large to have a bit in the map is
266 * automatically not in the set. */
268
269 /* Same parameters as charset, but match any character that is
270 * not one of those specified. */
272
273 /* Start remembering the text that is matched, for storing in a
274 * register. Followed by one byte with the register number, in
275 * the range 0 to one less than the pattern buffer's re_nsub
276 * field. Then followed by one byte with the number of groups
277 * inner to this one. (This last has to be part of the
278 * start_memory only because we need it in the on_failure_jump
279 * of re_match_2.) */
281
282 /* Stop remembering the text that is matched and store it in a
283 * memory register. Followed by one byte with the register
284 * number, in the range 0 to one less than `re_nsub' in the
285 * pattern buffer, and one byte with the number of inner groups,
286 * just like `start_memory'. (We need the number of inner
287 * groups here because we don't have any easy way of finding the
288 * corresponding start_memory when we're at a stop_memory.) */
290
291 /* Match a duplicate of something remembered. Followed by one
292 * byte containing the register number. */
294
295 /* Fail unless at beginning of line. */
297
298 /* Fail unless at end of line. */
300
301 /* Succeeds if or at beginning of string to be matched. */
303
304 /* Analogously, for end of buffer/string. */
306
307 /* Followed by two byte relative address to which to jump. */
309
310 /* Same as jump, but marks the end of an alternative. */
312
313 /* Followed by two-byte relative address of place to resume at
314 * in case of failure. */
316
317 /* Like on_failure_jump, but pushes a placeholder instead of the
318 * current string position when executed. */
320
321 /* Throw away latest failure point and then jump to following
322 * two-byte relative address. */
324
325 /* Change to pop_failure_jump if know won't have to backtrack to
326 * match; otherwise change to jump. This is used to jump
327 * back to the beginning of a repeat. If what follows this jump
328 * clearly won't match what the repeat does, such that we can be
329 * sure that there is no use backtracking out of repetitions
330 * already matched, then we change it to a pop_failure_jump.
331 * Followed by two-byte address. */
333
334 /* Jump to following two-byte address, and push a dummy failure
335 * point. This failure point will be thrown away if an attempt
336 * is made to use it for a failure. A `+' construct makes this
337 * before the first repeat. Also used as an intermediary kind
338 * of jump when compiling an alternative. */
340
341 /* Push a dummy failure point and continue. Used at the end of
342 * alternatives. */
344
345 /* Followed by two-byte relative address and two-byte number n.
346 * After matching N times, jump to the address upon failure. */
348
349 /* Followed by two-byte relative address, and two-byte number n.
350 * Jump to the address N times, then fail. */
352
353 /* Set the following two-byte relative address to the
354 * subsequent two-byte number. The address *includes* the two
355 * bytes of number. */
357
358 wordchar, /* Matches any word-constituent character. */
359 notwordchar, /* Matches any char that is not a word-constituent. */
360
361 wordbeg, /* Succeeds if at word beginning. */
362 wordend, /* Succeeds if at word end. */
363
364 wordbound, /* Succeeds if at a word boundary. */
365 notwordbound /* Succeeds if not at a word boundary. */
366
368
369/* Common operations on the compiled pattern. */
370
371/* Store NUMBER in two contiguous bytes starting at DESTINATION. */
372
373#define STORE_NUMBER(destination, number) \
374 do { \
375 (destination)[0] = (number) & 0377; \
376 (destination)[1] = (number) >> 8; \
377 } while (0)
378
379/* Same as STORE_NUMBER, except increment DESTINATION to
380 * the byte after where the number is stored. Therefore, DESTINATION
381 * must be an lvalue. */
382
383#define STORE_NUMBER_AND_INCR(destination, number) \
384 do { \
385 STORE_NUMBER (destination, number); \
386 (destination) += 2; \
387 } while (0)
388
389/* Put into DESTINATION a number stored in two contiguous bytes starting
390 * at SOURCE. */
391
392#define EXTRACT_NUMBER(destination, source) \
393 do { \
394 (destination) = *(source) & 0377; \
395 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \
396 } while (0)
397
398#ifdef DEBUG
399static void
400extract_number(dest, source)
401int *dest;
402unsigned char *source;
403{
404 int temp = SIGN_EXTEND_CHAR(*(source + 1));
405 *dest = *source & 0377;
406 *dest += temp << 8;
407}
408
409#ifndef EXTRACT_MACROS /* To debug the macros. */
410#undef EXTRACT_NUMBER
411#define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
412#endif /* not EXTRACT_MACROS */
413
414#endif /* DEBUG */
415
416/* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
417 * SOURCE must be an lvalue. */
418
419#define EXTRACT_NUMBER_AND_INCR(destination, source) \
420 do { \
421 EXTRACT_NUMBER (destination, source); \
422 (source) += 2; \
423 } while (0)
424
425#ifdef DEBUG
426static void
427extract_number_and_incr(destination, source)
428int *destination;
429unsigned char **source;
430{
431 extract_number(destination, *source);
432 *source += 2;
433}
434
435#ifndef EXTRACT_MACROS
436#undef EXTRACT_NUMBER_AND_INCR
437#define EXTRACT_NUMBER_AND_INCR(dest, src) \
438 extract_number_and_incr (&dest, &src)
439#endif /* not EXTRACT_MACROS */
440
441#endif /* DEBUG */
442
443/* If DEBUG is defined, Regex prints many voluminous messages about what
444 * it is doing (if the variable `debug' is nonzero). If linked with the
445 * main program in `iregex.c', you can enter patterns and strings
446 * interactively. And if linked with the main program in `main.c' and
447 * the other test files, you can run the already-written tests. */
448
449#ifdef DEBUG
450
451static int debug = 0;
452
453#define DEBUG_STATEMENT(e) e
454#define DEBUG_PRINT1(x) if (debug) printf (x)
455#define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
456#define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
457#define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
458#define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
459 if (debug) print_partial_compiled_pattern (s, e)
460#define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
461 if (debug) print_double_string (w, s1, sz1, s2, sz2)
462
463extern void printchar();
464
465/* Print the fastmap in human-readable form. */
466
467void
468print_fastmap(fastmap)
469char *fastmap;
470{
471 unsigned was_a_range = 0;
472 unsigned i = 0;
473
474 while (i < (1 << BYTEWIDTH)) {
475 if (fastmap[i++]) {
476 was_a_range = 0;
477 printchar(i - 1);
478 while (i < (1 << BYTEWIDTH) && fastmap[i]) {
479 was_a_range = 1;
480 i++;
481 }
482 if (was_a_range) {
483 printf("-");
484 printchar(i - 1);
485 }
486 }
487 }
488 putchar('\n');
489}
490
491/* Print a compiled pattern string in human-readable form, starting at
492 * the START pointer into it and ending just before the pointer END. */
493
494void
495print_partial_compiled_pattern(start, end)
496unsigned char *start;
497unsigned char *end;
498{
499 int mcnt, mcnt2;
500 unsigned char *p = start;
501 unsigned char *pend = end;
502
503 if (start == NULL) {
504 printf("(null)\n");
505 return;
506 }
507 /* Loop over pattern commands. */
508 while (p < pend) {
509 switch ((re_opcode_t) * p++) {
510 case no_op:
511 printf("/no_op");
512 break;
513
514 case exactn:
515 mcnt = *p++;
516 printf("/exactn/%d", mcnt);
517 do {
518 putchar('/');
519 printchar(*p++);
520 } while (--mcnt);
521 break;
522
523 case start_memory:
524 mcnt = *p++;
525 printf("/start_memory/%d/%d", mcnt, *p++);
526 break;
527
528 case stop_memory:
529 mcnt = *p++;
530 printf("/stop_memory/%d/%d", mcnt, *p++);
531 break;
532
533 case duplicate:
534 printf("/duplicate/%d", *p++);
535 break;
536
537 case anychar:
538 printf("/anychar");
539 break;
540
541 case charset:
542 case charset_not: {
543 register int c;
544
545 printf("/charset%s",
546 (re_opcode_t) * (p - 1) == charset_not ? "_not" : "");
547
548 assert(p + *p < pend);
549
550 for (c = 0; c < *p; c++) {
551 unsigned bit;
552 unsigned char map_byte = p[1 + c];
553
554 putchar('/');
555
556 for (bit = 0; bit < BYTEWIDTH; bit++)
557 if (map_byte & (1 << bit))
558 printchar(c * BYTEWIDTH + bit);
559 }
560 p += 1 + *p;
561 break;
562 }
563
564 case begline:
565 printf("/begline");
566 break;
567
568 case endline:
569 printf("/endline");
570 break;
571
572 case on_failure_jump:
573 extract_number_and_incr(&mcnt, &p);
574 printf("/on_failure_jump/0/%d", mcnt);
575 break;
576
578 extract_number_and_incr(&mcnt, &p);
579 printf("/on_failure_keep_string_jump/0/%d", mcnt);
580 break;
581
583 extract_number_and_incr(&mcnt, &p);
584 printf("/dummy_failure_jump/0/%d", mcnt);
585 break;
586
588 printf("/push_dummy_failure");
589 break;
590
591 case maybe_pop_jump:
592 extract_number_and_incr(&mcnt, &p);
593 printf("/maybe_pop_jump/0/%d", mcnt);
594 break;
595
596 case pop_failure_jump:
597 extract_number_and_incr(&mcnt, &p);
598 printf("/pop_failure_jump/0/%d", mcnt);
599 break;
600
601 case jump_past_alt:
602 extract_number_and_incr(&mcnt, &p);
603 printf("/jump_past_alt/0/%d", mcnt);
604 break;
605
606 case jump:
607 extract_number_and_incr(&mcnt, &p);
608 printf("/jump/0/%d", mcnt);
609 break;
610
611 case succeed_n:
612 extract_number_and_incr(&mcnt, &p);
613 extract_number_and_incr(&mcnt2, &p);
614 printf("/succeed_n/0/%d/0/%d", mcnt, mcnt2);
615 break;
616
617 case jump_n:
618 extract_number_and_incr(&mcnt, &p);
619 extract_number_and_incr(&mcnt2, &p);
620 printf("/jump_n/0/%d/0/%d", mcnt, mcnt2);
621 break;
622
623 case set_number_at:
624 extract_number_and_incr(&mcnt, &p);
625 extract_number_and_incr(&mcnt2, &p);
626 printf("/set_number_at/0/%d/0/%d", mcnt, mcnt2);
627 break;
628
629 case wordbound:
630 printf("/wordbound");
631 break;
632
633 case notwordbound:
634 printf("/notwordbound");
635 break;
636
637 case wordbeg:
638 printf("/wordbeg");
639 break;
640
641 case wordend:
642 printf("/wordend");
643
644 case wordchar:
645 printf("/wordchar");
646 break;
647
648 case notwordchar:
649 printf("/notwordchar");
650 break;
651
652 case begbuf:
653 printf("/begbuf");
654 break;
655
656 case endbuf:
657 printf("/endbuf");
658 break;
659
660 default:
661 printf("?%d", *(p - 1));
662 }
663 }
664 printf("/\n");
665}
666
667void
668print_compiled_pattern(bufp)
669struct re_pattern_buffer *bufp;
670{
671 unsigned char *buffer = bufp->buffer;
672
673 print_partial_compiled_pattern(buffer, buffer + bufp->used);
674 printf("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated);
675
676 if (bufp->fastmap_accurate && bufp->fastmap) {
677 printf("fastmap: ");
678 print_fastmap(bufp->fastmap);
679 }
680 printf("re_nsub: %d\t", bufp->re_nsub);
681 printf("regs_alloc: %d\t", bufp->regs_allocated);
682 printf("can_be_null: %d\t", bufp->can_be_null);
683 printf("newline_anchor: %d\n", bufp->newline_anchor);
684 printf("no_sub: %d\t", bufp->no_sub);
685 printf("not_bol: %d\t", bufp->not_bol);
686 printf("not_eol: %d\t", bufp->not_eol);
687 printf("syntax: %d\n", bufp->syntax);
688 /* Perhaps we should print the translate table? */
689}
690
691void
692print_double_string(where, string1, size1, string2, size2)
693const char *where;
694const char *string1;
695const char *string2;
696int size1;
697int size2;
698{
699 unsigned this_char;
700
701 if (where == NULL)
702 printf("(null)");
703 else {
704 if (FIRST_STRING_P(where)) {
705 for (this_char = where - string1; this_char < size1; this_char++)
706 printchar(string1[this_char]);
707
708 where = string2;
709 }
710 for (this_char = where - string2; this_char < size2; this_char++)
711 printchar(string2[this_char]);
712 }
713}
714
715#else /* not DEBUG */
716
717#undef assert
718#define assert(e)
719
720#define DEBUG_STATEMENT(e)
721#define DEBUG_PRINT1(x)
722#define DEBUG_PRINT2(x1, x2)
723#define DEBUG_PRINT3(x1, x2, x3)
724#define DEBUG_PRINT4(x1, x2, x3, x4)
725#define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
726#define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
727
728#endif /* not DEBUG */
729
730/* This table gives an error message for each of the error codes listed
731 * in regex.h. Obviously the order here has to be same as there. */
732
733static const char *re_error_msg[] = {NULL, /* REG_NOERROR */
734 "No match", /* REG_NOMATCH */
735 "Invalid regular expression", /* REG_BADPAT */
736 "Invalid collation character", /* REG_ECOLLATE */
737 "Invalid character class name", /* REG_ECTYPE */
738 "Trailing backslash", /* REG_EESCAPE */
739 "Invalid back reference", /* REG_ESUBREG */
740 "Unmatched [ or [^", /* REG_EBRACK */
741 "Unmatched ( or \\(", /* REG_EPAREN */
742 "Unmatched \\{", /* REG_EBRACE */
743 "Invalid content of \\{\\}", /* REG_BADBR */
744 "Invalid range end", /* REG_ERANGE */
745 "Memory exhausted", /* REG_ESPACE */
746 "Invalid preceding regular expression", /* REG_BADRPT */
747 "Premature end of regular expression", /* REG_EEND */
748 "Regular expression too big", /* REG_ESIZE */
749 "Unmatched ) or \\)", /* REG_ERPAREN */
750 };
751
752/* Subroutine declarations and macros for regex_compile. */
753
754/* Fetch the next character in the uncompiled pattern---translating it
755 * if necessary. Also cast from a signed character in the constant
756 * string passed to us by the user to an unsigned char that we can use
757 * as an array index (in, e.g., `translate'). */
758#define PATFETCH(c) \
759 do {if (p == pend) return REG_EEND; \
760 c = (unsigned char) *p++; \
761 if (translate) c = translate[c]; \
762 } while (0)
763
764/* Fetch the next character in the uncompiled pattern, with no
765 * translation. */
766#define PATFETCH_RAW(c) \
767 do {if (p == pend) return REG_EEND; \
768 c = (unsigned char) *p++; \
769 } while (0)
770
771/* Go backwards one character in the pattern. */
772#define PATUNFETCH p--
773
774/* If `translate' is non-null, return translate[D], else just D. We
775 * cast the subscript to translate because some data is declared as
776 * `char *', to avoid warnings when a string constant is passed. But
777 * when we use a character as a subscript we must make it unsigned. */
778#define TRANSLATE(d) (translate ? translate[(unsigned char) (d)] : (d))
779
780/* Macros for outputting the compiled pattern into `buffer'. */
781
782/* If the buffer isn't allocated when it comes in, use this. */
783#define INIT_BUF_SIZE 32
784
785/* Make sure we have at least N more bytes of space in buffer. */
786#define GET_BUFFER_SPACE(n) \
787 while (b - bufp->buffer + (n) > bufp->allocated) \
788 EXTEND_BUFFER ()
789
790/* Make sure we have one more byte of buffer space and then add C to it. */
791#define BUF_PUSH(c) \
792 do { \
793 GET_BUFFER_SPACE (1); \
794 *b++ = (unsigned char) (c); \
795 } while (0)
796
797/* Ensure we have two more bytes of buffer space and then append C1 and C2. */
798#define BUF_PUSH_2(c1, c2) \
799 do { \
800 GET_BUFFER_SPACE (2); \
801 *b++ = (unsigned char) (c1); \
802 *b++ = (unsigned char) (c2); \
803 } while (0)
804
805/* As with BUF_PUSH_2, except for three bytes. */
806#define BUF_PUSH_3(c1, c2, c3) \
807 do { \
808 GET_BUFFER_SPACE (3); \
809 *b++ = (unsigned char) (c1); \
810 *b++ = (unsigned char) (c2); \
811 *b++ = (unsigned char) (c3); \
812 } while (0)
813
814/* Store a jump with opcode OP at LOC to location TO. We store a
815 * relative address offset by the three bytes the jump itself occupies. */
816#define STORE_JUMP(op, loc, to) \
817 store_op1 (op, loc, (to) - (loc) - 3)
818
819/* Likewise, for a two-argument jump. */
820#define STORE_JUMP2(op, loc, to, arg) \
821 store_op2 (op, loc, (to) - (loc) - 3, arg)
822
823/* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
824#define INSERT_JUMP(op, loc, to) \
825 insert_op1 (op, loc, (to) - (loc) - 3, b)
826
827/* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
828#define INSERT_JUMP2(op, loc, to, arg) \
829 insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
830
831/* This is not an arbitrary limit: the arguments which represent offsets
832 * into the pattern are two bytes long. So if 2^16 bytes turns out to
833 * be too small, many things would have to change. */
834#define MAX_BUF_SIZE (1L << 16)
835
836/* Extend the buffer by twice its current size via realloc and
837 * reset the pointers that pointed into the old block to point to the
838 * correct places in the new one. If extending the buffer results in it
839 * being larger than MAX_BUF_SIZE, then flag memory exhausted. */
840#define EXTEND_BUFFER() \
841 do { \
842 unsigned char *old_buffer = bufp->buffer; \
843 if (bufp->allocated == MAX_BUF_SIZE) \
844 return REG_ESIZE; \
845 bufp->allocated <<= 1; \
846 if (bufp->allocated > MAX_BUF_SIZE) \
847 bufp->allocated = MAX_BUF_SIZE; \
848 bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
849 if (bufp->buffer == NULL) \
850 return REG_ESPACE; \
851 /* If the buffer moved, move all the pointers into it. */ \
852 if (old_buffer != bufp->buffer) \
853 { \
854 b = (b - old_buffer) + bufp->buffer; \
855 begalt = (begalt - old_buffer) + bufp->buffer; \
856 if (fixup_alt_jump) \
857 fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
858 if (laststart) \
859 laststart = (laststart - old_buffer) + bufp->buffer; \
860 if (pending_exact) \
861 pending_exact = (pending_exact - old_buffer) + bufp->buffer; \
862 } \
863 } while (0)
864
865/* Since we have one byte reserved for the register number argument to
866 * {start,stop}_memory, the maximum number of groups we can report
867 * things about is what fits in that byte. */
868#define MAX_REGNUM 255
869
870/* But patterns can have more than `MAX_REGNUM' registers. We just
871 * ignore the excess. */
872typedef unsigned regnum_t;
873
874/* Macros for the compile stack. */
875
876/* Since offsets can go either forwards or backwards, this type needs to
877 * be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
879
880typedef struct {
887
888typedef struct {
890 unsigned size;
891 unsigned avail; /* Offset of next open position. */
893
894static void store_op1(re_opcode_t op, unsigned char *loc, int arg);
895static void store_op2( re_opcode_t op, unsigned char *loc, int arg1, int arg2);
896static void insert_op1(re_opcode_t op, unsigned char *loc, int arg, unsigned char *end);
897static void insert_op2(re_opcode_t op, unsigned char *loc, int arg1, int arg2, unsigned char *end);
898static boolean at_begline_loc_p(const char * pattern, const char *p, reg_syntax_t syntax);
899static boolean at_endline_loc_p(const char *p, const char *pend, int syntax);
900static boolean group_in_compile_stack(compile_stack_type compile_stack, regnum_t regnum);
901static reg_errcode_t compile_range(const char **p_ptr, const char *pend, char *translate, reg_syntax_t syntax, unsigned char *b);
902
903#define INIT_COMPILE_STACK_SIZE 32
904
905/* The next available element. */
906#define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
907
908/* Set the bit for character C in a list. */
909#define SET_LIST_BIT(c) \
910 (b[((unsigned char) (c)) / BYTEWIDTH] \
911 |= 1 << (((unsigned char) c) % BYTEWIDTH))
912
913/* Get the next unsigned number in the uncompiled pattern. */
914#define GET_UNSIGNED_NUMBER(num) \
915 { if (p != pend) \
916 { \
917 PATFETCH (c); \
918 while (ISDIGIT (c)) \
919 { \
920 if (num < 0) \
921 num = 0; \
922 num = num * 10 + c - '0'; \
923 if (p == pend) \
924 break; \
925 PATFETCH (c); \
926 } \
927 } \
928 }
929
930#define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
931
932#define IS_CHAR_CLASS(string) \
933 (STREQ (string, "alpha") || STREQ (string, "upper") \
934 || STREQ (string, "lower") || STREQ (string, "digit") \
935 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
936 || STREQ (string, "space") || STREQ (string, "print") \
937 || STREQ (string, "punct") || STREQ (string, "graph") \
938 || STREQ (string, "cntrl") || STREQ (string, "blank"))
939
940/* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
941 * Returns one of error codes defined in `regex.h', or zero for success.
942 *
943 * Assumes the `allocated' (and perhaps `buffer') and `translate'
944 * fields are set in BUFP on entry.
945 *
946 * If it succeeds, results are put in BUFP (if it returns an error, the
947 * contents of BUFP are undefined):
948 * `buffer' is the compiled pattern;
949 * `syntax' is set to SYNTAX;
950 * `used' is set to the length of the compiled pattern;
951 * `fastmap_accurate' is zero;
952 * `re_nsub' is the number of subexpressions in PATTERN;
953 * `not_bol' and `not_eol' are zero;
954 *
955 * The `fastmap' and `newline_anchor' fields are neither
956 * examined nor set. */
957
958static reg_errcode_t
959regex_compile(const char *pattern, int size, reg_syntax_t syntax, struct re_pattern_buffer *bufp)
960{
961 /* We fetch characters from PATTERN here. Even though PATTERN is
962 * `char *' (i.e., signed), we declare these variables as unsigned, so
963 * they can be reliably used as array indices. */
964 register unsigned char c, c1;
965
966 /* A random temporary spot in PATTERN. */
967 const char *p1;
968
969 /* Points to the end of the buffer, where we should append. */
970 register unsigned char *b;
971
972 /* Keeps track of unclosed groups. */
973 compile_stack_type compile_stack;
974
975 /* Points to the current (ending) position in the pattern. */
976 const char *p = pattern;
977 const char *pend = pattern + size;
978
979 /* How to translate the characters in the pattern. */
980 char *translate = bufp->translate;
981
982 /* Address of the count-byte of the most recently inserted `exactn'
983 * command. This makes it possible to tell if a new exact-match
984 * character can be added to that command or if the character requires
985 * a new `exactn' command. */
986 unsigned char *pending_exact = 0;
987
988 /* Address of start of the most recently finished expression.
989 * This tells, e.g., postfix * where to find the start of its
990 * operand. Reset at the beginning of groups and alternatives. */
991 unsigned char *laststart = 0;
992
993 /* Address of beginning of regexp, or inside of last group. */
994 unsigned char *begalt;
995
996 /* Place in the uncompiled pattern (i.e., the {) to
997 * which to go back if the interval is invalid. */
998 const char *beg_interval;
999
1000 /* Address of the place where a forward jump should go to the end of
1001 * the containing expression. Each alternative of an `or' -- except the
1002 * last -- ends with a forward jump of this sort. */
1003 unsigned char *fixup_alt_jump = 0;
1004
1005 /* Counts open-groups as they are encountered. Remembered for the
1006 * matching close-group on the compile stack, so the same register
1007 * number is put in the stop_memory as the start_memory. */
1008 regnum_t regnum = 0;
1009
1010#ifdef DEBUG
1011 DEBUG_PRINT1("\nCompiling pattern: ");
1012 if (debug) {
1013 unsigned debug_count;
1014
1015 for (debug_count = 0; debug_count < size; debug_count++)
1016 printchar(pattern[debug_count]);
1017 putchar('\n');
1018 }
1019#endif /* DEBUG */
1020
1021 /* Initialize the compile stack. */
1023 if (compile_stack.stack == NULL)
1024 return REG_ESPACE;
1025
1026 compile_stack.size = INIT_COMPILE_STACK_SIZE;
1027 compile_stack.avail = 0;
1028
1029 /* Initialize the pattern buffer. */
1030 bufp->syntax = syntax;
1031 bufp->fastmap_accurate = 0;
1032 bufp->not_bol = bufp->not_eol = 0;
1033
1034 /* Set `used' to zero, so that if we return an error, the pattern
1035 * printer (for debugging) will think there's no pattern. We reset it
1036 * at the end. */
1037 bufp->used = 0;
1038
1039 /* Always count groups, whether or not bufp->no_sub is set. */
1040 bufp->re_nsub = 0;
1041
1042#if !defined (SYNTAX_TABLE)
1043 /* Initialize the syntax table. */
1045#endif
1046
1047 if (bufp->allocated == 0) {
1048 if (bufp->buffer) {
1049 /* If zero allocated, but buffer is non-null, try to realloc
1050 * enough space. This loses if buffer's address is bogus, but
1051 * that is the user's responsibility. */
1052 RETALLOC(bufp->buffer, INIT_BUF_SIZE, unsigned char);
1053 } else { /* Caller did not allocate a buffer. Do it for them. */
1054 bufp->buffer = TALLOC(INIT_BUF_SIZE, unsigned char);
1055 }
1056 if (!bufp->buffer)
1057 return REG_ESPACE;
1058
1059 bufp->allocated = INIT_BUF_SIZE;
1060 }
1061 begalt = b = bufp->buffer;
1062
1063 /* Loop through the uncompiled pattern until we're at the end. */
1064 while (p != pend) {
1065 PATFETCH(c);
1066
1067 switch (c) {
1068 case '^': {
1069 if ( /* If at start of pattern, it's an operator. */
1070 p == pattern + 1
1071 /* If context independent, it's an operator. */
1072 || syntax & RE_CONTEXT_INDEP_ANCHORS
1073 /* Otherwise, depends on what's come before. */
1074 || at_begline_loc_p(pattern, p, syntax))
1076 else
1077 goto normal_char;
1078 }
1079 break;
1080
1081 case '$': {
1082 if ( /* If at end of pattern, it's an operator. */
1083 p == pend
1084 /* If context independent, it's an operator. */
1085 || syntax & RE_CONTEXT_INDEP_ANCHORS
1086 /* Otherwise, depends on what's next. */
1087 || at_endline_loc_p(p, pend, syntax))
1089 else
1090 goto normal_char;
1091 }
1092 break;
1093
1094 case '+':
1095 case '?':
1096 if ((syntax & RE_BK_PLUS_QM)
1097 || (syntax & RE_LIMITED_OPS))
1098 goto normal_char;
1099handle_plus:
1100 case '*':
1101 /* If there is no previous pattern... */
1102 if (!laststart) {
1103 if (syntax & RE_CONTEXT_INVALID_OPS)
1104 return REG_BADRPT;
1105 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1106 goto normal_char;
1107 } {
1108 /* Are we optimizing this jump? */
1109 boolean keep_string_p = false;
1110
1111 /* 1 means zero (many) matches is allowed. */
1112 char zero_times_ok = 0, many_times_ok = 0;
1113
1114 /* If there is a sequence of repetition chars, collapse it
1115 * down to just one (the right one). We can't combine
1116 * interval operators with these because of, e.g., `a{2}*',
1117 * which should only match an even number of `a's. */
1118
1119 for (;;) {
1120 zero_times_ok |= c != '+';
1121 many_times_ok |= c != '?';
1122
1123 if (p == pend)
1124 break;
1125
1126 PATFETCH(c);
1127
1128 if (c == '*'
1129 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')));
1130
1131 else if (syntax & RE_BK_PLUS_QM && c == '\\') {
1132 if (p == pend)
1133 return REG_EESCAPE;
1134
1135 PATFETCH(c1);
1136 if (!(c1 == '+' || c1 == '?')) {
1137 PATUNFETCH;
1138 PATUNFETCH;
1139 break;
1140 }
1141 c = c1;
1142 } else {
1143 PATUNFETCH;
1144 break;
1145 }
1146
1147 /* If we get here, we found another repeat character. */
1148 }
1149
1150 /* Star, etc. applied to an empty pattern is equivalent
1151 * to an empty pattern. */
1152 if (!laststart)
1153 break;
1154
1155 /* Now we know whether or not zero matches is allowed
1156 * and also whether or not two or more matches is allowed. */
1157 if (many_times_ok) {
1158 /* More than one repetition is allowed, so put in at the
1159 * end a backward relative jump from `b' to before the next
1160 * jump we're going to put in below (which jumps from
1161 * laststart to after this jump).
1162 *
1163 * But if we are at the `*' in the exact sequence `.*\n',
1164 * insert an unconditional jump backwards to the .,
1165 * instead of the beginning of the loop. This way we only
1166 * push a failure point once, instead of every time
1167 * through the loop. */
1168 assert(p - 1 > pattern);
1169
1170 /* Allocate the space for the jump. */
1172
1173 /* We know we are not at the first character of the pattern,
1174 * because laststart was nonzero. And we've already
1175 * incremented `p', by the way, to be the character after
1176 * the `*'. Do we have to do something analogous here
1177 * for null bytes, because of RE_DOT_NOT_NULL? */
1178 if (TRANSLATE(*(p - 2)) == TRANSLATE('.')
1179 && zero_times_ok
1180 && p < pend && TRANSLATE(*p) == TRANSLATE('\n')
1181 && !(syntax & RE_DOT_NEWLINE)) { /* We have .*\n. */
1182 STORE_JUMP(jump, b, laststart);
1183 keep_string_p = true;
1184 } else
1185 /* Anything else. */
1186 STORE_JUMP(maybe_pop_jump, b, laststart - 3);
1187
1188 /* We've added more stuff to the buffer. */
1189 b += 3;
1190 }
1191 /* On failure, jump from laststart to b + 3, which will be the
1192 * end of the buffer after this jump is inserted. */
1196 laststart, b + 3);
1197 pending_exact = 0;
1198 b += 3;
1199
1200 if (!zero_times_ok) {
1201 /* At least one repetition is required, so insert a
1202 * `dummy_failure_jump' before the initial
1203 * `on_failure_jump' instruction of the loop. This
1204 * effects a skip over that instruction the first time
1205 * we hit that loop. */
1207 INSERT_JUMP(dummy_failure_jump, laststart, laststart + 6);
1208 b += 3;
1209 }
1210 }
1211 break;
1212
1213 case '.':
1214 laststart = b;
1216 break;
1217
1218 case '[': {
1219 boolean had_char_class = false;
1220
1221 if (p == pend)
1222 return REG_EBRACK;
1223
1224 /* Ensure that we have enough space to push a charset: the
1225 * opcode, the length count, and the bitset; 34 bytes in all. */
1226 GET_BUFFER_SPACE(34);
1227
1228 laststart = b;
1229
1230 /* We test `*p == '^' twice, instead of using an if
1231 * statement, so we only need one BUF_PUSH. */
1232 BUF_PUSH(*p == '^' ? charset_not : charset);
1233 if (*p == '^')
1234 p++;
1235
1236 /* Remember the first position in the bracket expression. */
1237 p1 = p;
1238
1239 /* Push the number of bytes in the bitmap. */
1240 BUF_PUSH((1 << BYTEWIDTH) / BYTEWIDTH);
1241
1242 /* Clear the whole map. */
1243 memset(b, 0, (1 << BYTEWIDTH) / BYTEWIDTH);
1244
1245 /* charset_not matches newline according to a syntax bit. */
1246 if ((re_opcode_t) b[-2] == charset_not
1247 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
1248 SET_LIST_BIT('\n');
1249
1250 /* Read in characters and ranges, setting map bits. */
1251 for (;;) {
1252 if (p == pend)
1253 return REG_EBRACK;
1254
1255 PATFETCH(c);
1256
1257 /* \ might escape characters inside [...] and [^...]. */
1258 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\') {
1259 if (p == pend)
1260 return REG_EESCAPE;
1261
1262 PATFETCH(c1);
1263 SET_LIST_BIT(c1);
1264 continue;
1265 }
1266 /* Could be the end of the bracket expression. If it's
1267 * not (i.e., when the bracket expression is `[]' so
1268 * far), the ']' character bit gets set way below. */
1269 if (c == ']' && p != p1 + 1)
1270 break;
1271
1272 /* Look ahead to see if it's a range when the last thing
1273 * was a character class. */
1274 if (had_char_class && c == '-' && *p != ']')
1275 return REG_ERANGE;
1276
1277 /* Look ahead to see if it's a range when the last thing
1278 * was a character: if this is a hyphen not at the
1279 * beginning or the end of a list, then it's the range
1280 * operator. */
1281 if (c == '-'
1282 && !(p - 2 >= pattern && p[-2] == '[')
1283 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
1284 && *p != ']') {
1285 reg_errcode_t ret
1286 = compile_range(&p, pend, translate, syntax, b);
1287 if (ret != REG_NOERROR)
1288 return ret;
1289 } else if (p[0] == '-' && p[1] != ']') { /* This handles ranges made up of characters only. */
1290 reg_errcode_t ret;
1291
1292 /* Move past the `-'. */
1293 PATFETCH(c1);
1294
1295 ret = compile_range(&p, pend, translate, syntax, b);
1296 if (ret != REG_NOERROR)
1297 return ret;
1298 }
1299 /* See if we're at the beginning of a possible character
1300 * class. */
1301
1302 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':') { /* Leave room for the null. */
1303 char str[CHAR_CLASS_MAX_LENGTH + 1];
1304
1305 PATFETCH(c);
1306 c1 = 0;
1307
1308 /* If pattern is `[[:'. */
1309 if (p == pend)
1310 return REG_EBRACK;
1311
1312 for (;;) {
1313 PATFETCH(c);
1314 if (c == ':' || c == ']' || p == pend
1315 || c1 == CHAR_CLASS_MAX_LENGTH)
1316 break;
1317 str[c1++] = c;
1318 }
1319 str[c1] = '\0';
1320
1321 /* If isn't a word bracketed by `[:' and:`]':
1322 * undo the ending character, the letters, and leave
1323 * the leading `:' and `[' (but set bits for them). */
1324 if (c == ':' && *p == ']') {
1325 int ch;
1326 boolean is_alnum = STREQ(str, "alnum");
1327 boolean is_alpha = STREQ(str, "alpha");
1328 boolean is_blank = STREQ(str, "blank");
1329 boolean is_cntrl = STREQ(str, "cntrl");
1330 boolean is_digit = STREQ(str, "digit");
1331 boolean is_graph = STREQ(str, "graph");
1332 boolean is_lower = STREQ(str, "lower");
1333 boolean is_print = STREQ(str, "print");
1334 boolean is_punct = STREQ(str, "punct");
1335 boolean is_space = STREQ(str, "space");
1336 boolean is_upper = STREQ(str, "upper");
1337 boolean is_xdigit = STREQ(str, "xdigit");
1338
1339 if (!IS_CHAR_CLASS(str))
1340 return REG_ECTYPE;
1341
1342 /* Throw away the ] at the end of the character
1343 * class. */
1344 PATFETCH(c);
1345
1346 if (p == pend)
1347 return REG_EBRACK;
1348
1349 for (ch = 0; ch < 1 << BYTEWIDTH; ch++) {
1350 if ((is_alnum && ISALNUM(ch))
1351 || (is_alpha && ISALPHA(ch))
1352 || (is_blank && ISBLANK(ch))
1353 || (is_cntrl && ISCNTRL(ch))
1354 || (is_digit && ISDIGIT(ch))
1355 || (is_graph && ISGRAPH(ch))
1356 || (is_lower && ISLOWER(ch))
1357 || (is_print && ISPRINT(ch))
1358 || (is_punct && ISPUNCT(ch))
1359 || (is_space && ISSPACE(ch))
1360 || (is_upper && ISUPPER(ch))
1361 || (is_xdigit && ISXDIGIT(ch)))
1362 SET_LIST_BIT(ch);
1363 }
1364 had_char_class = true;
1365 } else {
1366 c1++;
1367 while (c1--)
1368 PATUNFETCH;
1369 SET_LIST_BIT('[');
1370 SET_LIST_BIT(':');
1371 had_char_class = false;
1372 }
1373 } else {
1374 had_char_class = false;
1375 SET_LIST_BIT(c);
1376 }
1377 }
1378
1379 /* Discard any (non)matching list bytes that are all 0 at the
1380 * end of the map. Decrease the map-length byte too. */
1381 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
1382 b[-1]--;
1383 b += b[-1];
1384 }
1385 break;
1386
1387 case '(':
1388 if (syntax & RE_NO_BK_PARENS)
1389 goto handle_open;
1390 else
1391 goto normal_char;
1392
1393 case ')':
1394 if (syntax & RE_NO_BK_PARENS)
1395 goto handle_close;
1396 else
1397 goto normal_char;
1398
1399 case '\n':
1400 if (syntax & RE_NEWLINE_ALT)
1401 goto handle_alt;
1402 else
1403 goto normal_char;
1404
1405 case '|':
1406 if (syntax & RE_NO_BK_VBAR)
1407 goto handle_alt;
1408 else
1409 goto normal_char;
1410
1411 case '{':
1412 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
1413 goto handle_interval;
1414 else
1415 goto normal_char;
1416
1417 case '\\':
1418 if (p == pend)
1419 return REG_EESCAPE;
1420
1421 /* Do not translate the character after the \, so that we can
1422 * distinguish, e.g., \B from \b, even if we normally would
1423 * translate, e.g., B to b. */
1424 PATFETCH_RAW(c);
1425
1426 switch (c) {
1427 case '(':
1428 if (syntax & RE_NO_BK_PARENS)
1429 goto normal_backslash;
1430
1431handle_open:
1432 bufp->re_nsub++;
1433 regnum++;
1434
1435 if (compile_stack.avail == compile_stack.size) {
1436 RETALLOC(compile_stack.stack, compile_stack.size << 1,
1438 if (compile_stack.stack == NULL)
1439 return REG_ESPACE;
1440
1441 compile_stack.size <<= 1;
1442 }
1443 /* These are the values to restore when we hit end of this
1444 * group. They are all relative offsets, so that if the
1445 * whole pattern moves because of realloc, they will still
1446 * be valid. */
1447 COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
1448 COMPILE_STACK_TOP.fixup_alt_jump
1449 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
1450 COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
1451 COMPILE_STACK_TOP.regnum = regnum;
1452
1453 /* We will eventually replace the 0 with the number of
1454 * groups inner to this one. But do not push a
1455 * start_memory for groups beyond the last one we can
1456 * represent in the compiled pattern. */
1457 if (regnum <= MAX_REGNUM) {
1458 COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
1459 BUF_PUSH_3(start_memory, regnum, 0);
1460 }
1461 compile_stack.avail++;
1462
1463 fixup_alt_jump = 0;
1464 laststart = 0;
1465 begalt = b;
1466 /* If we've reached MAX_REGNUM groups, then this open
1467 * won't actually generate any code, so we'll have to
1468 * clear pending_exact explicitly. */
1469 pending_exact = 0;
1470 break;
1471
1472 case ')':
1473 if (syntax & RE_NO_BK_PARENS)
1474 goto normal_backslash;
1475
1476 if (compile_stack.avail == 0) {
1477 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1478 goto normal_backslash;
1479 else
1480 return REG_ERPAREN;
1481 }
1482handle_close:
1483 if (fixup_alt_jump) {
1484 /* Push a dummy failure point at the end of the
1485 * alternative for a possible future
1486 * `pop_failure_jump' to pop. See comments at
1487 * `push_dummy_failure' in `re_match_2'. */
1489
1490 /* We allocated space for this jump when we assigned
1491 * to `fixup_alt_jump', in the `handle_alt' case below. */
1492 STORE_JUMP(jump_past_alt, fixup_alt_jump, b - 1);
1493 }
1494 /* See similar code for backslashed left paren above. */
1495 if (compile_stack.avail == 0) {
1496 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1497 goto normal_char;
1498 else
1499 return REG_ERPAREN;
1500 }
1501 /* Since we just checked for an empty stack above, this
1502 * ``can't happen''. */
1503 assert(compile_stack.avail != 0);
1504 {
1505 /* We don't just want to restore into `regnum', because
1506 * later groups should continue to be numbered higher,
1507 * as in `(ab)c(de)' -- the second group is #2. */
1508 regnum_t this_group_regnum;
1509
1510 compile_stack.avail--;
1511 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
1512 fixup_alt_jump
1513 = COMPILE_STACK_TOP.fixup_alt_jump
1514 ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
1515 : 0;
1516 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
1517 this_group_regnum = COMPILE_STACK_TOP.regnum;
1518 /* If we've reached MAX_REGNUM groups, then this open
1519 * won't actually generate any code, so we'll have to
1520 * clear pending_exact explicitly. */
1521 pending_exact = 0;
1522
1523 /* We're at the end of the group, so now we know how many
1524 * groups were inside this one. */
1525 if (this_group_regnum <= MAX_REGNUM) {
1526 unsigned char *inner_group_loc
1527 = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
1528
1529 *inner_group_loc = regnum - this_group_regnum;
1530 BUF_PUSH_3(stop_memory, this_group_regnum,
1531 regnum - this_group_regnum);
1532 }
1533 }
1534 break;
1535
1536 case '|': /* `\|'. */
1537 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
1538 goto normal_backslash;
1539handle_alt:
1540 if (syntax & RE_LIMITED_OPS)
1541 goto normal_char;
1542
1543 /* Insert before the previous alternative a jump which
1544 * jumps to this alternative if the former fails. */
1546 INSERT_JUMP(on_failure_jump, begalt, b + 6);
1547 pending_exact = 0;
1548 b += 3;
1549
1550 /* The alternative before this one has a jump after it
1551 * which gets executed if it gets matched. Adjust that
1552 * jump so it will jump to this alternative's analogous
1553 * jump (put in below, which in turn will jump to the next
1554 * (if any) alternative's such jump, etc.). The last such
1555 * jump jumps to the correct final destination. A picture:
1556 * _____ _____
1557 * | | | |
1558 * | v | v
1559 * a | b | c
1560 *
1561 * If we are at `b', then fixup_alt_jump right now points to a
1562 * three-byte space after `a'. We'll put in the jump, set
1563 * fixup_alt_jump to right after `b', and leave behind three
1564 * bytes which we'll fill in when we get to after `c'. */
1565
1566 if (fixup_alt_jump)
1567 STORE_JUMP(jump_past_alt, fixup_alt_jump, b);
1568
1569 /* Mark and leave space for a jump after this alternative,
1570 * to be filled in later either by next alternative or
1571 * when know we're at the end of a series of alternatives. */
1572 fixup_alt_jump = b;
1574 b += 3;
1575
1576 laststart = 0;
1577 begalt = b;
1578 break;
1579
1580 case '{':
1581 /* If \{ is a literal. */
1582 if (!(syntax & RE_INTERVALS)
1583 /* If we're at `\{' and it's not the open-interval
1584 * operator. */
1585 || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1586 || (p - 2 == pattern && p == pend))
1587 goto normal_backslash;
1588
1589handle_interval: {
1590 /* If got here, then the syntax allows intervals. */
1591
1592 /* At least (most) this many matches must be made. */
1593 int lower_bound = -1, upper_bound = -1;
1594
1595 beg_interval = p - 1;
1596
1597 if (p == pend) {
1598 if (syntax & RE_NO_BK_BRACES)
1599 goto unfetch_interval;
1600 else
1601 return REG_EBRACE;
1602 }
1603 GET_UNSIGNED_NUMBER(lower_bound);
1604
1605 if (c == ',') {
1606 GET_UNSIGNED_NUMBER(upper_bound);
1607 if (upper_bound < 0)
1608 upper_bound = RE_DUP_MAX;
1609 } else
1610 /* Interval such as `{1}' => match exactly once. */
1611 upper_bound = lower_bound;
1612
1613 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
1614 || lower_bound > upper_bound) {
1615 if (syntax & RE_NO_BK_BRACES)
1616 goto unfetch_interval;
1617 else
1618 return REG_BADBR;
1619 }
1620 if (!(syntax & RE_NO_BK_BRACES)) {
1621 if (c != '\\')
1622 return REG_EBRACE;
1623
1624 PATFETCH(c);
1625 }
1626 if (c != '}') {
1627 if (syntax & RE_NO_BK_BRACES)
1628 goto unfetch_interval;
1629 else
1630 return REG_BADBR;
1631 }
1632 /* We just parsed a valid interval. */
1633
1634 /* If it's invalid to have no preceding re. */
1635 if (!laststart) {
1636 if (syntax & RE_CONTEXT_INVALID_OPS)
1637 return REG_BADRPT;
1638 else if (syntax & RE_CONTEXT_INDEP_OPS)
1639 laststart = b;
1640 else
1641 goto unfetch_interval;
1642 }
1643 /* If the upper bound is zero, don't want to succeed at
1644 * all; jump from `laststart' to `b + 3', which will be
1645 * the end of the buffer after we insert the jump. */
1646 if (upper_bound == 0) {
1648 INSERT_JUMP(jump, laststart, b + 3);
1649 b += 3;
1650 }
1651 /* Otherwise, we have a nontrivial interval. When
1652 * we're all done, the pattern will look like:
1653 * set_number_at <jump count> <upper bound>
1654 * set_number_at <succeed_n count> <lower bound>
1655 * succeed_n <after jump addr> <succed_n count>
1656 * <body of loop>
1657 * jump_n <succeed_n addr> <jump count>
1658 * (The upper bound and `jump_n' are omitted if
1659 * `upper_bound' is 1, though.) */
1660 else {
1661 /* If the upper bound is > 1, we need to insert
1662 * more at the end of the loop. */
1663 unsigned nbytes = 10 + (upper_bound > 1) * 10;
1664
1665 GET_BUFFER_SPACE(nbytes);
1666
1667 /* Initialize lower bound of the `succeed_n', even
1668 * though it will be set during matching by its
1669 * attendant `set_number_at' (inserted next),
1670 * because `re_compile_fastmap' needs to know.
1671 * Jump to the `jump_n' we might insert below. */
1672 INSERT_JUMP2(succeed_n, laststart,
1673 b + 5 + (upper_bound > 1) * 5,
1674 lower_bound);
1675 b += 5;
1676
1677 /* Code to initialize the lower bound. Insert
1678 * before the `succeed_n'. The `5' is the last two
1679 * bytes of this `set_number_at', plus 3 bytes of
1680 * the following `succeed_n'. */
1681 insert_op2(set_number_at, laststart, 5, lower_bound, b);
1682 b += 5;
1683
1684 if (upper_bound > 1) {
1685 /* More than one repetition is allowed, so
1686 * append a backward jump to the `succeed_n'
1687 * that starts this interval.
1688 *
1689 * When we've reached this during matching,
1690 * we'll have matched the interval once, so
1691 * jump back only `upper_bound - 1' times. */
1692 STORE_JUMP2(jump_n, b, laststart + 5,
1693 upper_bound - 1);
1694 b += 5;
1695
1696 /* The location we want to set is the second
1697 * parameter of the `jump_n'; that is `b-2' as
1698 * an absolute address. `laststart' will be
1699 * the `set_number_at' we're about to insert;
1700 * `laststart+3' the number to set, the source
1701 * for the relative address. But we are
1702 * inserting into the middle of the pattern --
1703 * so everything is getting moved up by 5.
1704 * Conclusion: (b - 2) - (laststart + 3) + 5,
1705 * i.e., b - laststart.
1706 *
1707 * We insert this at the beginning of the loop
1708 * so that if we fail during matching, we'll
1709 * reinitialize the bounds. */
1710 insert_op2(set_number_at, laststart, b - laststart,
1711 upper_bound - 1, b);
1712 b += 5;
1713 }
1714 }
1715 pending_exact = 0;
1716 beg_interval = NULL;
1717 }
1718 break;
1719
1720unfetch_interval:
1721 /* If an invalid interval, match the characters as literals. */
1722 assert(beg_interval);
1723 p = beg_interval;
1724 beg_interval = NULL;
1725
1726 /* normal_char and normal_backslash need `c'. */
1727 PATFETCH(c);
1728
1729 if (!(syntax & RE_NO_BK_BRACES)) {
1730 if (p > pattern && p[-1] == '\\')
1731 goto normal_backslash;
1732 }
1733 goto normal_char;
1734
1735 case 'w':
1736 laststart = b;
1738 break;
1739
1740 case 'W':
1741 laststart = b;
1743 break;
1744
1745 case '<':
1747 break;
1748
1749 case '>':
1751 break;
1752
1753 case 'b':
1755 break;
1756
1757 case 'B':
1759 break;
1760
1761 case '`':
1763 break;
1764
1765 case '\'':
1767 break;
1768
1769 case '1':
1770 case '2':
1771 case '3':
1772 case '4':
1773 case '5':
1774 case '6':
1775 case '7':
1776 case '8':
1777 case '9':
1778 if (syntax & RE_NO_BK_REFS)
1779 goto normal_char;
1780
1781 c1 = c - '0';
1782
1783 if (c1 > regnum)
1784 return REG_ESUBREG;
1785
1786 /* Can't back reference to a subexpression if inside of it. */
1787 if (group_in_compile_stack(compile_stack, c1))
1788 goto normal_char;
1789
1790 laststart = b;
1791 BUF_PUSH_2(duplicate, c1);
1792 break;
1793
1794 case '+':
1795 case '?':
1796 if (syntax & RE_BK_PLUS_QM)
1797 goto handle_plus;
1798 else
1799 goto normal_backslash;
1800
1801 default:
1802normal_backslash:
1803 /* You might think it would be useful for \ to mean
1804 * not to translate; but if we don't translate it
1805 * it will never match anything. */
1806 c = TRANSLATE(c);
1807 goto normal_char;
1808 }
1809 break;
1810
1811 default:
1812 /* Expects the character in `c'. */
1813normal_char:
1814 /* If no exactn currently being built. */
1815 if (!pending_exact
1816
1817 /* If last exactn not at current position. */
1818 || pending_exact + *pending_exact + 1 != b
1819
1820 /* We have only one byte following the exactn for the count. */
1821 || *pending_exact == (1 << BYTEWIDTH) - 1
1822
1823 /* If followed by a repetition operator. */
1824 || *p == '*' || *p == '^'
1825 || ((syntax & RE_BK_PLUS_QM)
1826 ? *p == '\\' && (p[1] == '+' || p[1] == '?')
1827 : (*p == '+' || *p == '?'))
1828 || ((syntax & RE_INTERVALS)
1829 && ((syntax & RE_NO_BK_BRACES)
1830 ? *p == '{'
1831 : (p[0] == '\\' && p[1] == '{')))) {
1832 /* Start building a new exactn. */
1833
1834 laststart = b;
1835
1836 BUF_PUSH_2(exactn, 0);
1837 pending_exact = b - 1;
1838 }
1839 BUF_PUSH(c);
1840 (*pending_exact)++;
1841 break;
1842 } /* switch (c) */
1843 } /* while p != pend */
1844
1845 /* Through the pattern now. */
1846
1847 if (fixup_alt_jump)
1848 STORE_JUMP(jump_past_alt, fixup_alt_jump, b);
1849
1850 if (compile_stack.avail != 0)
1851 return REG_EPAREN;
1852
1853 free(compile_stack.stack);
1854
1855 /* We have succeeded; set the length of the buffer. */
1856 bufp->used = b - bufp->buffer;
1857
1858#ifdef DEBUG
1859 if (debug) {
1860 DEBUG_PRINT1("\nCompiled pattern: ");
1861 print_compiled_pattern(bufp);
1862 }
1863#endif /* DEBUG */
1864
1865 return REG_NOERROR;
1866} /* regex_compile */
1867
1868/* Subroutines for `regex_compile'. */
1869
1870/* Store OP at LOC followed by two-byte integer parameter ARG. */
1871
1872void store_op1(re_opcode_t op, unsigned char *loc, int arg)
1873{
1874 *loc = (unsigned char) op;
1875 STORE_NUMBER(loc + 1, arg);
1876}
1877
1878/* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
1879
1880void
1881store_op2( re_opcode_t op, unsigned char *loc, int arg1, int arg2)
1882{
1883 *loc = (unsigned char) op;
1884 STORE_NUMBER(loc + 1, arg1);
1885 STORE_NUMBER(loc + 3, arg2);
1886}
1887
1888/* Copy the bytes from LOC to END to open up three bytes of space at LOC
1889 * for OP followed by two-byte integer parameter ARG. */
1890
1891void
1892insert_op1(re_opcode_t op, unsigned char *loc, int arg, unsigned char *end)
1893{
1894 register unsigned char *pfrom = end;
1895 register unsigned char *pto = end + 3;
1896
1897 while (pfrom != loc)
1898 *--pto = *--pfrom;
1899
1900 store_op1(op, loc, arg);
1901}
1902
1903/* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
1904
1905void
1906insert_op2(re_opcode_t op, unsigned char *loc, int arg1, int arg2, unsigned char *end)
1907{
1908 register unsigned char *pfrom = end;
1909 register unsigned char *pto = end + 5;
1910
1911 while (pfrom != loc)
1912 *--pto = *--pfrom;
1913
1914 store_op2(op, loc, arg1, arg2);
1915}
1916
1917/* P points to just after a ^ in PATTERN. Return true if that ^ comes
1918 * after an alternative or a begin-subexpression. We assume there is at
1919 * least one character before the ^. */
1920
1921boolean
1922at_begline_loc_p(const char * pattern, const char *p, reg_syntax_t syntax)
1923{
1924 const char *prev = p - 2;
1925 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
1926
1927 return
1928 /* After a subexpression? */
1929 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
1930 /* After an alternative? */
1931 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
1932}
1933
1934/* The dual of at_begline_loc_p. This one is for $. We assume there is
1935 * at least one character after the $, i.e., `P < PEND'. */
1936
1937boolean
1938at_endline_loc_p(const char *p, const char *pend, int syntax)
1939{
1940 const char *next = p;
1941 boolean next_backslash = *next == '\\';
1942 const char *next_next = p + 1 < pend ? p + 1 : NULL;
1943
1944 return
1945 /* Before a subexpression? */
1946 (syntax & RE_NO_BK_PARENS ? *next == ')'
1947 : next_backslash && next_next && *next_next == ')')
1948 /* Before an alternative? */
1949 || (syntax & RE_NO_BK_VBAR ? *next == '|'
1950 : next_backslash && next_next && *next_next == '|');
1951}
1952
1953/* Returns true if REGNUM is in one of COMPILE_STACK's elements and
1954 * false if it's not. */
1955
1956boolean
1958{
1959 int this_element;
1960
1961 for (this_element = compile_stack.avail - 1;
1962 this_element >= 0;
1963 this_element--)
1964 if (compile_stack.stack[this_element].regnum == regnum)
1965 return true;
1966
1967 return false;
1968}
1969
1970/* Read the ending character of a range (in a bracket expression) from the
1971 * uncompiled pattern *P_PTR (which ends at PEND). We assume the
1972 * starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
1973 * Then we set the translation of all bits between the starting and
1974 * ending characters (inclusive) in the compiled pattern B.
1975 *
1976 * Return an error code.
1977 *
1978 * We use these short variable names so we can use the same macros as
1979 * `regex_compile' itself. */
1980
1982compile_range(const char **p_ptr, const char *pend, char *translate, reg_syntax_t syntax, unsigned char *b)
1983{
1984 unsigned this_char;
1985
1986 const char *p = *p_ptr;
1987 int range_start, range_end;
1988
1989 if (p == pend)
1990 return REG_ERANGE;
1991
1992 /* Even though the pattern is a signed `char *', we need to fetch
1993 * with unsigned char *'s; if the high bit of the pattern character
1994 * is set, the range endpoints will be negative if we fetch using a
1995 * signed char *.
1996 *
1997 * We also want to fetch the endpoints without translating them; the
1998 * appropriate translation is done in the bit-setting loop below. */
1999 range_start = ((unsigned char *) p)[-2];
2000 range_end = ((unsigned char *) p)[0];
2001
2002 /* Have to increment the pointer into the pattern string, so the
2003 * caller isn't still at the ending character. */
2004 (*p_ptr)++;
2005
2006 /* If the start is after the end, the range is empty. */
2007 if (range_start > range_end)
2008 return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2009
2010 /* Here we see why `this_char' has to be larger than an `unsigned
2011 * char' -- the range is inclusive, so if `range_end' == 0xff
2012 * (assuming 8-bit characters), we would otherwise go into an infinite
2013 * loop, since all characters <= 0xff. */
2014 for (this_char = range_start; this_char <= range_end; this_char++) {
2015 SET_LIST_BIT(TRANSLATE(this_char));
2016 }
2017
2018 return REG_NOERROR;
2019}
2020
2021/* Failure stack declarations and macros; both re_compile_fastmap and
2022 * re_match_2 use a failure stack. These have to be macros because of
2023 * REGEX_ALLOCATE. */
2024
2025/* Number of failure points for which to initially allocate space
2026 * when matching. If this number is exceeded, we allocate more
2027 * space, so it is not a hard limit. */
2028#ifndef INIT_FAILURE_ALLOC
2029#define INIT_FAILURE_ALLOC 5
2030#endif
2031
2032/* Roughly the maximum number of failure points on the stack. Would be
2033 * exactly that if always used MAX_FAILURE_SPACE each time we failed.
2034 * This is a variable only so users of regex can assign to it; we never
2035 * change it ourselves. */
2037
2038typedef const unsigned char *fail_stack_elt_t;
2039
2040typedef struct {
2042 unsigned size;
2043 unsigned avail; /* Offset of next open position. */
2045
2046#define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
2047#define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
2048#define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
2049#define FAIL_STACK_TOP() (fail_stack.stack[fail_stack.avail])
2050
2051/* Initialize `fail_stack'. Do `return -2' if the alloc fails. */
2052
2053#define INIT_FAIL_STACK() \
2054 do { \
2055 fail_stack.stack = (fail_stack_elt_t *) \
2056 REGEX_ALLOCATE (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t)); \
2057 \
2058 if (fail_stack.stack == NULL) \
2059 return -2; \
2060 \
2061 fail_stack.size = INIT_FAILURE_ALLOC; \
2062 fail_stack.avail = 0; \
2063 } while (0)
2064
2065/* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
2066 *
2067 * Return 1 if succeeds, and 0 if either ran out of memory
2068 * allocating space for it or it was already too large.
2069 *
2070 * REGEX_REALLOCATE requires `destination' be declared. */
2071
2072#define DOUBLE_FAIL_STACK(fail_stack) \
2073 ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS \
2074 ? 0 \
2075 : ((fail_stack).stack = (fail_stack_elt_t *) \
2076 REGEX_REALLOCATE ((fail_stack).stack, \
2077 (fail_stack).size * sizeof (fail_stack_elt_t), \
2078 ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)), \
2079 \
2080 (fail_stack).stack == NULL \
2081 ? 0 \
2082 : ((fail_stack).size <<= 1, \
2083 1)))
2084
2085/* Push PATTERN_OP on FAIL_STACK.
2086 *
2087 * Return 1 if was able to do so and 0 if ran out of memory allocating
2088 * space to do so. */
2089#define PUSH_PATTERN_OP(pattern_op, fail_stack) \
2090 ((FAIL_STACK_FULL () \
2091 && !DOUBLE_FAIL_STACK (fail_stack)) \
2092 ? 0 \
2093 : ((fail_stack).stack[(fail_stack).avail++] = pattern_op, \
2094 1))
2095
2096/* This pushes an item onto the failure stack. Must be a four-byte
2097 * value. Assumes the variable `fail_stack'. Probably should only
2098 * be called from within `PUSH_FAILURE_POINT'. */
2099#define PUSH_FAILURE_ITEM(item) \
2100 fail_stack.stack[fail_stack.avail++] = (fail_stack_elt_t) item
2101
2102/* The complement operation. Assumes `fail_stack' is nonempty. */
2103#define POP_FAILURE_ITEM() fail_stack.stack[--fail_stack.avail]
2104
2105/* Used to omit pushing failure point id's when we're not debugging. */
2106#ifdef DEBUG
2107#define DEBUG_PUSH PUSH_FAILURE_ITEM
2108#define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_ITEM ()
2109#else
2110#define DEBUG_PUSH(item)
2111#define DEBUG_POP(item_addr)
2112#endif
2113
2114/* Push the information about the state we will need
2115 * if we ever fail back to it.
2116 *
2117 * Requires variables fail_stack, regstart, regend, reg_info, and
2118 * num_regs be declared. DOUBLE_FAIL_STACK requires `destination' be
2119 * declared.
2120 *
2121 * Does `return FAILURE_CODE' if runs out of memory. */
2122
2123#define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
2124 do { \
2125 char *destination; \
2126 /* Must be int, so when we don't save any registers, the arithmetic \
2127 of 0 + -1 isn't done as unsigned. */ \
2128 int this_reg; \
2129 \
2130 DEBUG_STATEMENT (failure_id++); \
2131 DEBUG_STATEMENT (nfailure_points_pushed++); \
2132 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
2133 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
2134 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
2135 \
2136 DEBUG_PRINT2 (" slots needed: %d\n", NUM_FAILURE_ITEMS); \
2137 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
2138 \
2139 /* Ensure we have enough space allocated for what we will push. */ \
2140 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
2141 { \
2142 if (!DOUBLE_FAIL_STACK (fail_stack)) \
2143 return failure_code; \
2144 \
2145 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
2146 (fail_stack).size); \
2147 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
2148 } \
2149 \
2150 /* Push the info, starting with the registers. */ \
2151 DEBUG_PRINT1 ("\n"); \
2152 \
2153 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
2154 this_reg++) \
2155 { \
2156 DEBUG_PRINT2 (" Pushing reg: %d\n", this_reg); \
2157 DEBUG_STATEMENT (num_regs_pushed++); \
2158 \
2159 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2160 PUSH_FAILURE_ITEM (regstart[this_reg]); \
2161 \
2162 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2163 PUSH_FAILURE_ITEM (regend[this_reg]); \
2164 \
2165 DEBUG_PRINT2 (" info: 0x%x\n ", reg_info[this_reg]); \
2166 DEBUG_PRINT2 (" match_null=%d", \
2167 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
2168 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
2169 DEBUG_PRINT2 (" matched_something=%d", \
2170 MATCHED_SOMETHING (reg_info[this_reg])); \
2171 DEBUG_PRINT2 (" ever_matched=%d", \
2172 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
2173 DEBUG_PRINT1 ("\n"); \
2174 PUSH_FAILURE_ITEM (reg_info[this_reg].word); \
2175 } \
2176 \
2177 DEBUG_PRINT2 (" Pushing low active reg: %d\n", lowest_active_reg);\
2178 PUSH_FAILURE_ITEM (lowest_active_reg); \
2179 \
2180 DEBUG_PRINT2 (" Pushing high active reg: %d\n", highest_active_reg);\
2181 PUSH_FAILURE_ITEM (highest_active_reg); \
2182 \
2183 DEBUG_PRINT2 (" Pushing pattern 0x%x: ", pattern_place); \
2184 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
2185 PUSH_FAILURE_ITEM (pattern_place); \
2186 \
2187 DEBUG_PRINT2 (" Pushing string 0x%x: `", string_place); \
2188 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
2189 size2); \
2190 DEBUG_PRINT1 ("'\n"); \
2191 PUSH_FAILURE_ITEM (string_place); \
2192 \
2193 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
2194 DEBUG_PUSH (failure_id); \
2195 } while (0)
2196
2197/* This is the number of items that are pushed and popped on the stack
2198 * for each register. */
2199#define NUM_REG_ITEMS 3
2200
2201/* Individual items aside from the registers. */
2202#ifdef DEBUG
2203#define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
2204#else
2205#define NUM_NONREG_ITEMS 4
2206#endif
2207
2208/* We push at most this many items on the stack. */
2209#define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
2210
2211/* We actually push this many items. */
2212#define NUM_FAILURE_ITEMS \
2213 ((highest_active_reg - lowest_active_reg + 1) * NUM_REG_ITEMS \
2214 + NUM_NONREG_ITEMS)
2215
2216/* How many items can still be added to the stack without overflowing it. */
2217#define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
2218
2219/* Pops what PUSH_FAIL_STACK pushes.
2220 *
2221 * We restore into the parameters, all of which should be lvalues:
2222 * STR -- the saved data position.
2223 * PAT -- the saved pattern position.
2224 * LOW_REG, HIGH_REG -- the highest and lowest active registers.
2225 * REGSTART, REGEND -- arrays of string positions.
2226 * REG_INFO -- array of information about each subexpression.
2227 *
2228 * Also assumes the variables `fail_stack' and (if debugging), `bufp',
2229 * `pend', `string1', `size1', `string2', and `size2'. */
2231#define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
2232{ \
2233 DEBUG_STATEMENT (fail_stack_elt_t failure_id;) \
2234 int this_reg; \
2235 const unsigned char *string_temp; \
2236 \
2237 assert (!FAIL_STACK_EMPTY ()); \
2238 \
2239 /* Remove failure points and point to how many regs pushed. */ \
2240 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
2241 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
2242 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
2243 \
2244 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
2245 \
2246 DEBUG_POP (&failure_id); \
2247 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
2248 \
2249 /* If the saved string location is NULL, it came from an \
2250 on_failure_keep_string_jump opcode, and we want to throw away the \
2251 saved NULL, thus retaining our current position in the string. */ \
2252 string_temp = POP_FAILURE_ITEM (); \
2253 if (string_temp != NULL) \
2254 str = (const char *) string_temp; \
2255 \
2256 DEBUG_PRINT2 (" Popping string 0x%x: `", str); \
2257 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
2258 DEBUG_PRINT1 ("'\n"); \
2259 \
2260 pat = (unsigned char *) POP_FAILURE_ITEM (); \
2261 DEBUG_PRINT2 (" Popping pattern 0x%x: ", pat); \
2262 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
2263 \
2264 /* Restore register info. */ \
2265 high_reg = (unsigned long) POP_FAILURE_ITEM (); \
2266 DEBUG_PRINT2 (" Popping high active reg: %d\n", high_reg); \
2267 \
2268 low_reg = (unsigned long) POP_FAILURE_ITEM (); \
2269 DEBUG_PRINT2 (" Popping low active reg: %d\n", low_reg); \
2270 \
2271 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
2272 { \
2273 DEBUG_PRINT2 (" Popping reg: %d\n", this_reg); \
2274 \
2275 reg_info[this_reg].word = POP_FAILURE_ITEM (); \
2276 DEBUG_PRINT2 (" info: 0x%x\n", reg_info[this_reg]); \
2277 \
2278 regend[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2279 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2280 \
2281 regstart[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2282 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2283 } \
2284 \
2285 DEBUG_STATEMENT (nfailure_points_popped++); \
2286} /* POP_FAILURE_POINT */
2287
2288/* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2289 * BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
2290 * characters can start a string that matches the pattern. This fastmap
2291 * is used by re_search to skip quickly over impossible starting points.
2292 *
2293 * The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2294 * area as BUFP->fastmap.
2295 *
2296 * We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2297 * the pattern buffer.
2298 *
2299 * Returns 0 if we succeed, -2 if an internal error. */
2300#ifdef STDC_HEADERS
2301int
2303#else
2304int
2306struct re_pattern_buffer *bufp;
2307#endif
2308{
2309 int j, k;
2310 fail_stack_type fail_stack;
2311#ifndef REGEX_MALLOC
2312 char *destination;
2313#endif
2314 /* We don't push any register information onto the failure stack. */
2315 unsigned num_regs = 0;
2316
2317 register char *fastmap = bufp->fastmap;
2318 unsigned char *pattern = bufp->buffer;
2319 unsigned long size = bufp->used;
2320 const unsigned char *p = pattern;
2321 register unsigned char *pend = pattern + size;
2322
2323 /* Assume that each path through the pattern can be null until
2324 * proven otherwise. We set this false at the bottom of switch
2325 * statement, to which we get only if a particular path doesn't
2326 * match the empty string. */
2327 boolean path_can_be_null = true;
2328
2329 /* We aren't doing a `succeed_n' to begin with. */
2330 boolean succeed_n_p = false;
2331
2332 assert(fastmap != NULL && p != NULL);
2333
2335 memset(fastmap, 0, 1 << BYTEWIDTH); /* Assume nothing's valid. */
2336 bufp->fastmap_accurate = 1; /* It will be when we're done. */
2337 bufp->can_be_null = 0;
2338
2339 while (p != pend || !FAIL_STACK_EMPTY()) {
2340 if (p == pend) {
2341 bufp->can_be_null |= path_can_be_null;
2342
2343 /* Reset for next path. */
2344 path_can_be_null = true;
2345
2346 p = fail_stack.stack[--fail_stack.avail];
2347 }
2348 /* We should never be about to go beyond the end of the pattern. */
2349 assert(p < pend);
2350
2351#ifdef SWITCH_ENUM_BUG
2352 switch ((int) ((re_opcode_t) * p++))
2353#else
2354 switch ((re_opcode_t) * p++)
2355#endif
2356 {
2357
2358 /* I guess the idea here is to simply not bother with a fastmap
2359 * if a backreference is used, since it's too hard to figure out
2360 * the fastmap for the corresponding group. Setting
2361 * `can_be_null' stops `re_search_2' from using the fastmap, so
2362 * that is all we do. */
2363 case duplicate:
2364 bufp->can_be_null = 1;
2365 return 0;
2366
2367 /* Following are the cases which match a character. These end
2368 * with `break'. */
2369
2370 case exactn:
2371 fastmap[p[1]] = 1;
2372 break;
2373
2374 case charset:
2375 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2376 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
2377 fastmap[j] = 1;
2378 break;
2379
2380 case charset_not:
2381 /* Chars beyond end of map must be allowed. */
2382 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
2383 fastmap[j] = 1;
2384
2385 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2386 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
2387 fastmap[j] = 1;
2388 break;
2389
2390 case wordchar:
2391 for (j = 0; j < (1 << BYTEWIDTH); j++)
2392 if (re_syntax_table[j] == Sword)
2393 fastmap[j] = 1;
2394 break;
2395
2396 case notwordchar:
2397 for (j = 0; j < (1 << BYTEWIDTH); j++)
2398 if (re_syntax_table[j] != Sword)
2399 fastmap[j] = 1;
2400 break;
2401
2402 case anychar:
2403 /* `.' matches anything ... */
2404 for (j = 0; j < (1 << BYTEWIDTH); j++)
2405 fastmap[j] = 1;
2406
2407 /* ... except perhaps newline. */
2408 if (!(bufp->syntax & RE_DOT_NEWLINE))
2409 fastmap['\n'] = 0;
2410
2411 /* Return if we have already set `can_be_null'; if we have,
2412 * then the fastmap is irrelevant. Something's wrong here. */
2413 else if (bufp->can_be_null)
2414 return 0;
2415
2416 /* Otherwise, have to check alternative paths. */
2417 break;
2418
2419 case no_op:
2420 case begline:
2421 case endline:
2422 case begbuf:
2423 case endbuf:
2424 case wordbound:
2425 case notwordbound:
2426 case wordbeg:
2427 case wordend:
2428 case push_dummy_failure:
2429 continue;
2430
2431 case jump_n:
2432 case pop_failure_jump:
2433 case maybe_pop_jump:
2434 case jump:
2435 case jump_past_alt:
2436 case dummy_failure_jump:
2438 p += j;
2439 if (j > 0)
2440 continue;
2441
2442 /* Jump backward implies we just went through the body of a
2443 * loop and matched nothing. Opcode jumped to should be
2444 * `on_failure_jump' or `succeed_n'. Just treat it like an
2445 * ordinary jump. For a * loop, it has pushed its failure
2446 * point already; if so, discard that as redundant. */
2447 if ((re_opcode_t) * p != on_failure_jump
2448 && (re_opcode_t) * p != succeed_n)
2449 continue;
2450
2451 p++;
2453 p += j;
2454
2455 /* If what's on the stack is where we are now, pop it. */
2456 if (!FAIL_STACK_EMPTY()
2457 && fail_stack.stack[fail_stack.avail - 1] == p)
2458 fail_stack.avail--;
2459
2460 continue;
2461
2462 case on_failure_jump:
2464handle_on_failure_jump:
2466
2467 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
2468 * end of the pattern. We don't want to push such a point,
2469 * since when we restore it above, entering the switch will
2470 * increment `p' past the end of the pattern. We don't need
2471 * to push such a point since we obviously won't find any more
2472 * fastmap entries beyond `pend'. Such a pattern can match
2473 * the null string, though. */
2474 if (p + j < pend) {
2475 if (!PUSH_PATTERN_OP(p + j, fail_stack))
2476 return -2;
2477 } else
2478 bufp->can_be_null = 1;
2479
2480 if (succeed_n_p) {
2481 EXTRACT_NUMBER_AND_INCR(k, p); /* Skip the n. */
2482 succeed_n_p = false;
2483 }
2484 continue;
2485
2486 case succeed_n:
2487 /* Get to the number of times to succeed. */
2488 p += 2;
2489
2490 /* Increment p past the n for when k != 0. */
2492 if (k == 0) {
2493 p -= 4;
2494 succeed_n_p = true; /* Spaghetti code alert. */
2495 goto handle_on_failure_jump;
2496 }
2497 continue;
2498
2499 case set_number_at:
2500 p += 4;
2501 continue;
2502
2503 case start_memory:
2504 case stop_memory:
2505 p += 2;
2506 continue;
2507
2508 default:
2509 abort(); /* We have listed all the cases. */
2510 } /* switch *p++ */
2511
2512 /* Getting here means we have found the possible starting
2513 * characters for one path of the pattern -- and that the empty
2514 * string does not match. We need not follow this path further.
2515 * Instead, look at the next alternative (remembered on the
2516 * stack), or quit if no more. The test at the top of the loop
2517 * does these things. */
2518 path_can_be_null = false;
2519 p = pend;
2520 } /* while p */
2521
2522 /* Set `can_be_null' for the last path (also the first path, if the
2523 * pattern is empty). */
2524 bufp->can_be_null |= path_can_be_null;
2525 return 0;
2526} /* re_compile_fastmap */
2527
2528/* Searching routines. */
2529
2530/* Like re_search_2, below, but only one string is specified, and
2531 * doesn't let you say where to stop matching. */
2532
2533static int
2534re_search(bufp, string, size, startpos, range, regs)
2535struct re_pattern_buffer *bufp;
2536const char *string;
2537int size, startpos, range;
2538struct re_registers *regs;
2539{
2540 return re_search_2(bufp, NULL, 0, string, size, startpos, range,
2541 regs, size);
2542}
2543
2544/* Using the compiled pattern in BUFP->buffer, first tries to match the
2545 * virtual concatenation of STRING1 and STRING2, starting first at index
2546 * STARTPOS, then at STARTPOS + 1, and so on.
2547 *
2548 * STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
2549 *
2550 * RANGE is how far to scan while trying to match. RANGE = 0 means try
2551 * only at STARTPOS; in general, the last start tried is STARTPOS +
2552 * RANGE.
2553 *
2554 * In REGS, return the indices of the virtual concatenation of STRING1
2555 * and STRING2 that matched the entire BUFP->buffer and its contained
2556 * subexpressions.
2557 *
2558 * Do not consider matching one past the index STOP in the virtual
2559 * concatenation of STRING1 and STRING2.
2560 *
2561 * We return either the position in the strings at which the match was
2562 * found, -1 if no match, or -2 if error (such as failure
2563 * stack overflow). */
2564
2565static int
2566re_search_2(bufp, string1, size1, string2, size2, startpos, range, regs, stop)
2567struct re_pattern_buffer *bufp;
2568const char *string1, *string2;
2569int size1, size2;
2570int startpos;
2571int range;
2572struct re_registers *regs;
2573int stop;
2574{
2575 int val;
2576 register char *fastmap = bufp->fastmap;
2577 register char *translate = bufp->translate;
2578 int total_size = size1 + size2;
2579 int endpos = startpos + range;
2580
2581 /* Check for out-of-range STARTPOS. */
2582 if (startpos < 0 || startpos > total_size)
2583 return -1;
2584
2585 /* Fix up RANGE if it might eventually take us outside
2586 * the virtual concatenation of STRING1 and STRING2. */
2587 if (endpos < -1)
2588 range = -1 - startpos;
2589 else if (endpos > total_size)
2590 range = total_size - startpos;
2591
2592 /* If the search isn't to be a backwards one, don't waste time in a
2593 * search for a pattern that must be anchored. */
2594 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0) {
2595 if (startpos > 0)
2596 return -1;
2597 else
2598 range = 1;
2599 }
2600 /* Update the fastmap now if not correct already. */
2601 if (fastmap && !bufp->fastmap_accurate)
2602 if (re_compile_fastmap(bufp) == -2)
2603 return -2;
2604
2605 /* Loop through the string, looking for a place to start matching. */
2606 for (;;) {
2607 /* If a fastmap is supplied, skip quickly over characters that
2608 * cannot be the start of a match. If the pattern can match the
2609 * null string, however, we don't need to skip characters; we want
2610 * the first null string. */
2611 if (fastmap && startpos < total_size && !bufp->can_be_null) {
2612 if (range > 0) { /* Searching forwards. */
2613 register const char *d;
2614 register int lim = 0;
2615 int irange = range;
2616
2617 if (startpos < size1 && startpos + range >= size1)
2618 lim = range - (size1 - startpos);
2619
2620 d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
2621
2622 /* Written out as an if-else to avoid testing `translate'
2623 * inside the loop. */
2624 if (translate)
2625 while (range > lim
2626 && !fastmap[(unsigned char)
2627 translate[(unsigned char) *d++]])
2628 range--;
2629 else
2630 while (range > lim && !fastmap[(unsigned char) *d++])
2631 range--;
2632
2633 startpos += irange - range;
2634 } else { /* Searching backwards. */
2635 register char c = (size1 == 0 || startpos >= size1
2636 ? string2[startpos - size1]
2637 : string1[startpos]);
2638
2639 if (!fastmap[(unsigned char) TRANSLATE(c)])
2640 goto advance;
2641 }
2642 }
2643 /* If can't match the null string, and that's all we have left, fail. */
2644 if (range >= 0 && startpos == total_size && fastmap
2645 && !bufp->can_be_null)
2646 return -1;
2647
2648 val = re_match_2(bufp, string1, size1, string2, size2,
2649 startpos, regs, stop);
2650 if (val >= 0)
2651 return startpos;
2652
2653 if (val == -2)
2654 return -2;
2655
2656advance:
2657 if (!range)
2658 break;
2659 else if (range > 0) {
2660 range--;
2661 startpos++;
2662 } else {
2663 range++;
2664 startpos--;
2665 }
2666 }
2667 return -1;
2668} /* re_search_2 */
2669
2670/* Declarations and macros for re_match_2. */
2671
2672/* Structure for per-register (a.k.a. per-group) information.
2673 * This must not be longer than one word, because we push this value
2674 * onto the failure stack. Other register information, such as the
2675 * starting and ending positions (which are addresses), and the list of
2676 * inner groups (which is a bits list) are maintained in separate
2677 * variables.
2678 *
2679 * We are making a (strictly speaking) nonportable assumption here: that
2680 * the compiler will pack our bit fields into something that fits into
2681 * the type of `word', i.e., is something that fits into one item on the
2682 * failure stack. */
2683typedef union {
2684 fail_stack_elt_t word;
2685 struct {
2686 /* This field is one if this group can match the empty string,
2687 * zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
2688#define MATCH_NULL_UNSET_VALUE 3
2689 unsigned match_null_string_p:2;
2690 unsigned is_active:1;
2691 unsigned matched_something:1;
2692 unsigned ever_matched_something:1;
2693 } bits;
2695static boolean alt_match_null_string_p(unsigned char *p, unsigned char *end, register_info_type *reg_info);
2696static boolean common_op_match_null_string_p( unsigned char **p, unsigned char *end, register_info_type *reg_info);
2697static int bcmp_translate(unsigned char const *s1, unsigned char const *s2, register int len, char *translate);
2698static boolean group_match_null_string_p(unsigned char **p, unsigned char *end, register_info_type *reg_info);
2700#define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
2701#define IS_ACTIVE(R) ((R).bits.is_active)
2702#define MATCHED_SOMETHING(R) ((R).bits.matched_something)
2703#define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
2704
2705/* Call this when have matched a real character; it sets `matched' flags
2706 * for the subexpressions which we are currently inside. Also records
2707 * that those subexprs have matched. */
2708#define SET_REGS_MATCHED() \
2709 do \
2710 { \
2711 unsigned r; \
2712 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
2713 { \
2714 MATCHED_SOMETHING (reg_info[r]) \
2715 = EVER_MATCHED_SOMETHING (reg_info[r]) \
2716 = 1; \
2717 } \
2718 } \
2719 while (0)
2721/* This converts PTR, a pointer into one of the search strings `string1'
2722 * and `string2' into an offset from the beginning of that string. */
2723#define POINTER_TO_OFFSET(ptr) \
2724 (FIRST_STRING_P (ptr) ? (ptr) - string1 : (ptr) - string2 + size1)
2726/* Registers are set to a sentinel when they haven't yet matched. */
2727#define REG_UNSET_VALUE ((char *) -1)
2728#define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
2730/* Macros for dealing with the split strings in re_match_2. */
2731
2732#define MATCHING_IN_FIRST_STRING (dend == end_match_1)
2734/* Call before fetching a character with *d. This switches over to
2735 * string2 if necessary. */
2736#define PREFETCH() \
2737 while (d == dend) \
2738 { \
2739 /* End of string2 => fail. */ \
2740 if (dend == end_match_2) \
2741 goto fail; \
2742 /* End of string1 => advance to string2. */ \
2743 d = string2; \
2744 dend = end_match_2; \
2745 }
2747/* Test if at very beginning or at very end of the virtual concatenation
2748 * of `string1' and `string2'. If only one string, it's `string2'. */
2749#define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
2750static int at_strings_end(const char *d, const char *end2)
2751{
2752 return d == end2;
2753}
2754
2755/* Test if D points to a character which is word-constituent. We have
2756 * two special cases to check for: if past the end of string1, look at
2757 * the first character in string2; and if before the beginning of
2758 * string2, look at the last character in string1. */
2759#define WORDCHAR_P(d) \
2760 (re_syntax_table[(d) == end1 ? *string2 \
2761 : (d) == string2 - 1 ? *(end1 - 1) : *(d)] \
2762 == Sword)
2763static int
2764wordchar_p(const char *d, const char *end1, const char *string2)
2765{
2766 return re_syntax_table[(d) == end1 ? *string2
2767 : (d) == string2 - 1 ? *(end1 - 1) : *(d)]
2768 == Sword;
2769}
2771/* Test if the character before D and the one at D differ with respect
2772 * to being word-constituent. */
2773#define AT_WORD_BOUNDARY(d) \
2774 (AT_STRINGS_BEG (d) || at_strings_end(d,end2) \
2775 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
2777/* Free everything we malloc. */
2778#ifdef REGEX_MALLOC
2779#define FREE_VAR(var) if (var) free (var); var = NULL
2780#define FREE_VARIABLES() \
2781 do { \
2782 FREE_VAR (fail_stack.stack); \
2783 FREE_VAR (regstart); \
2784 FREE_VAR (regend); \
2785 FREE_VAR (old_regstart); \
2786 FREE_VAR (old_regend); \
2787 FREE_VAR (best_regstart); \
2788 FREE_VAR (best_regend); \
2789 FREE_VAR (reg_info); \
2790 FREE_VAR (reg_dummy); \
2791 FREE_VAR (reg_info_dummy); \
2792 } while (0)
2793#else /* not REGEX_MALLOC */
2794/* Some MIPS systems (at least) want this to free alloca'd storage. */
2795#define FREE_VARIABLES() alloca (0)
2796#endif /* not REGEX_MALLOC */
2797
2798/* These values must meet several constraints. They must not be valid
2799 * register values; since we have a limit of 255 registers (because
2800 * we use only one byte in the pattern for the register number), we can
2801 * use numbers larger than 255. They must differ by 1, because of
2802 * NUM_FAILURE_ITEMS above. And the value for the lowest register must
2803 * be larger than the value for the highest register, so we do not try
2804 * to actually save any registers when none are active. */
2805#define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
2806#define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
2807
2808/* Matching routines. */
2809
2810/* re_match_2 matches the compiled pattern in BUFP against the
2811 * the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
2812 * and SIZE2, respectively). We start matching at POS, and stop
2813 * matching at STOP.
2814 *
2815 * If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
2816 * store offsets for the substring each group matched in REGS. See the
2817 * documentation for exactly how many groups we fill.
2818 *
2819 * We return -1 if no match, -2 if an internal error (such as the
2820 * failure stack overflowing). Otherwise, we return the length of the
2821 * matched substring. */
2822
2823int
2824re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop)
2825struct re_pattern_buffer *bufp;
2826const char *string1, *string2;
2827int size1, size2;
2828int pos;
2829struct re_registers *regs;
2830int stop;
2831{
2832 /* General temporaries. */
2833 int mcnt;
2834 unsigned char *p1;
2835
2836 /* Just past the end of the corresponding string. */
2837 const char *end1, *end2;
2838
2839 /* Pointers into string1 and string2, just past the last characters in
2840 * each to consider matching. */
2841 const char *end_match_1, *end_match_2;
2842
2843 /* Where we are in the data, and the end of the current string. */
2844 const char *d, *dend;
2845
2846 /* Where we are in the pattern, and the end of the pattern. */
2847 unsigned char *p = bufp->buffer;
2848 register unsigned char *pend = p + bufp->used;
2849
2850 /* We use this to map every character in the string. */
2851 char *translate = bufp->translate;
2852
2853 /* Failure point stack. Each place that can handle a failure further
2854 * down the line pushes a failure point on this stack. It consists of
2855 * restart, regend, and reg_info for all registers corresponding to
2856 * the subexpressions we're currently inside, plus the number of such
2857 * registers, and, finally, two char *'s. The first char * is where
2858 * to resume scanning the pattern; the second one is where to resume
2859 * scanning the strings. If the latter is zero, the failure point is
2860 * a ``dummy''; if a failure happens and the failure point is a dummy,
2861 * it gets discarded and the next next one is tried. */
2862 fail_stack_type fail_stack;
2863#ifdef DEBUG
2864 static unsigned failure_id = 0;
2865 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
2866#endif
2867
2868 /* We fill all the registers internally, independent of what we
2869 * return, for use in backreferences. The number here includes
2870 * an element for register zero. */
2871 unsigned num_regs = bufp->re_nsub + 1;
2872
2873 /* The currently active registers. */
2874 unsigned long lowest_active_reg = NO_LOWEST_ACTIVE_REG;
2875 unsigned long highest_active_reg = NO_HIGHEST_ACTIVE_REG;
2876
2877 /* Information on the contents of registers. These are pointers into
2878 * the input strings; they record just what was matched (on this
2879 * attempt) by a subexpression part of the pattern, that is, the
2880 * regnum-th regstart pointer points to where in the pattern we began
2881 * matching and the regnum-th regend points to right after where we
2882 * stopped matching the regnum-th subexpression. (The zeroth register
2883 * keeps track of what the whole pattern matches.) */
2884 const char **regstart = NULL, **regend = NULL;
2885
2886 /* If a group that's operated upon by a repetition operator fails to
2887 * match anything, then the register for its start will need to be
2888 * restored because it will have been set to wherever in the string we
2889 * are when we last see its open-group operator. Similarly for a
2890 * register's end. */
2891 const char **old_regstart = NULL, **old_regend = NULL;
2892
2893 /* The is_active field of reg_info helps us keep track of which (possibly
2894 * nested) subexpressions we are currently in. The matched_something
2895 * field of reg_info[reg_num] helps us tell whether or not we have
2896 * matched any of the pattern so far this time through the reg_num-th
2897 * subexpression. These two fields get reset each time through any
2898 * loop their register is in. */
2899 register_info_type *reg_info = NULL;
2900
2901 /* The following record the register info as found in the above
2902 * variables when we find a match better than any we've seen before.
2903 * This happens as we backtrack through the failure points, which in
2904 * turn happens only if we have not yet matched the entire string. */
2905 unsigned best_regs_set = false;
2906 const char **best_regstart = NULL, **best_regend = NULL;
2907
2908 /* Logically, this is `best_regend[0]'. But we don't want to have to
2909 * allocate space for that if we're not allocating space for anything
2910 * else (see below). Also, we never need info about register 0 for
2911 * any of the other register vectors, and it seems rather a kludge to
2912 * treat `best_regend' differently than the rest. So we keep track of
2913 * the end of the best match so far in a separate variable. We
2914 * initialize this to NULL so that when we backtrack the first time
2915 * and need to test it, it's not garbage. */
2916 const char *match_end = NULL;
2917
2918 /* Used when we pop values we don't care about. */
2919 const char **reg_dummy = NULL;
2920 register_info_type *reg_info_dummy = NULL;
2921
2922#ifdef DEBUG
2923 /* Counts the total number of registers pushed. */
2924 unsigned num_regs_pushed = 0;
2925#endif
2926
2927 DEBUG_PRINT1("\n\nEntering re_match_2.\n");
2928
2930
2931 /* Do not bother to initialize all the register variables if there are
2932 * no groups in the pattern, as it takes a fair amount of time. If
2933 * there are groups, we include space for register 0 (the whole
2934 * pattern), even though we never use it, since it simplifies the
2935 * array indexing. We should fix this. */
2936 if (bufp->re_nsub) {
2937 regstart = REGEX_TALLOC(num_regs, const char *);
2938 regend = REGEX_TALLOC(num_regs, const char *);
2939 old_regstart = REGEX_TALLOC(num_regs, const char *);
2940 old_regend = REGEX_TALLOC(num_regs, const char *);
2941 best_regstart = REGEX_TALLOC(num_regs, const char *);
2942 best_regend = REGEX_TALLOC(num_regs, const char *);
2944 reg_dummy = REGEX_TALLOC(num_regs, const char *);
2945 reg_info_dummy = REGEX_TALLOC(num_regs, register_info_type);
2946
2947 if (!(regstart && regend && old_regstart && old_regend && reg_info
2948 && best_regstart && best_regend && reg_dummy && reg_info_dummy)) {
2950 return -2;
2951 }
2952 }
2953#ifdef REGEX_MALLOC
2954 else {
2955 /* We must initialize all our variables to NULL, so that
2956 * `FREE_VARIABLES' doesn't try to free them. */
2957 regstart = regend = old_regstart = old_regend = best_regstart
2958 = best_regend = reg_dummy = NULL;
2959 reg_info = reg_info_dummy = (register_info_type *) NULL;
2960 }
2961#endif /* REGEX_MALLOC */
2962
2963 /* The starting position is bogus. */
2964 if (pos < 0 || pos > size1 + size2) {
2966 return -1;
2967 }
2968 /* Initialize subexpression text positions to -1 to mark ones that no
2969 * start_memory/stop_memory has been seen for. Also initialize the
2970 * register information struct. */
2971 for (mcnt = 1; mcnt < num_regs; mcnt++) {
2972 regstart[mcnt] = regend[mcnt]
2973 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
2974
2976 IS_ACTIVE(reg_info[mcnt]) = 0;
2977 MATCHED_SOMETHING(reg_info[mcnt]) = 0;
2978 EVER_MATCHED_SOMETHING(reg_info[mcnt]) = 0;
2979 }
2980
2981 /* We move `string1' into `string2' if the latter's empty -- but not if
2982 * `string1' is null. */
2983 if (size2 == 0 && string1 != NULL) {
2984 string2 = string1;
2985 size2 = size1;
2986 string1 = 0;
2987 size1 = 0;
2988 }
2989 end1 = string1 + size1;
2990 end2 = string2 + size2;
2991
2992 /* Compute where to stop matching, within the two strings. */
2993 if (stop <= size1) {
2994 end_match_1 = string1 + stop;
2995 end_match_2 = string2;
2996 } else {
2997 end_match_1 = end1;
2998 end_match_2 = string2 + stop - size1;
2999 }
3000
3001 /* `p' scans through the pattern as `d' scans through the data.
3002 * `dend' is the end of the input string that `d' points within. `d'
3003 * is advanced into the following input string whenever necessary, but
3004 * this happens before fetching; therefore, at the beginning of the
3005 * loop, `d' can be pointing at the end of a string, but it cannot
3006 * equal `string2'. */
3007 if (size1 > 0 && pos <= size1) {
3008 d = string1 + pos;
3009 dend = end_match_1;
3010 } else {
3011 d = string2 + pos - size1;
3012 dend = end_match_2;
3013 }
3014
3015 DEBUG_PRINT1("The compiled pattern is: ");
3016 DEBUG_PRINT_COMPILED_PATTERN(bufp, p, pend);
3017 DEBUG_PRINT1("The string to match is: `");
3018 DEBUG_PRINT_DOUBLE_STRING(d, string1, size1, string2, size2);
3019 DEBUG_PRINT1("'\n");
3020
3021 /* This loops over pattern commands. It exits by returning from the
3022 * function if the match is complete, or it drops through if the match
3023 * fails at this starting point in the input data. */
3024 for (;;) {
3025 DEBUG_PRINT2("\n0x%x: ", p);
3026
3027 if (p == pend) { /* End of pattern means we might have succeeded. */
3028 DEBUG_PRINT1("end of pattern ... ");
3029
3030 /* If we haven't matched the entire string, and we want the
3031 * longest match, try backtracking. */
3032 if (d != end_match_2) {
3033 DEBUG_PRINT1("backtracking.\n");
3034
3035 if (!FAIL_STACK_EMPTY()) { /* More failure points to try. */
3036 boolean same_str_p = (FIRST_STRING_P(match_end)
3038
3039 /* If exceeds best match so far, save it. */
3040 if (!best_regs_set
3041 || (same_str_p && d > match_end)
3042 || (!same_str_p && !MATCHING_IN_FIRST_STRING)) {
3043 best_regs_set = true;
3044 match_end = d;
3045
3046 DEBUG_PRINT1("\nSAVING match as best so far.\n");
3047
3048 for (mcnt = 1; mcnt < num_regs; mcnt++) {
3049 best_regstart[mcnt] = regstart[mcnt];
3050 best_regend[mcnt] = regend[mcnt];
3051 }
3052 }
3053 goto fail;
3054 }
3055 /* If no failure points, don't restore garbage. */
3056 else if (best_regs_set) {
3057restore_best_regs:
3058 /* Restore best match. It may happen that `dend ==
3059 * end_match_1' while the restored d is in string2.
3060 * For example, the pattern `x.*y.*z' against the
3061 * strings `x-' and `y-z-', if the two strings are
3062 * not consecutive in memory. */
3063 DEBUG_PRINT1("Restoring best registers.\n");
3064
3065 d = match_end;
3066 dend = ((d >= string1 && d <= end1)
3067 ? end_match_1 : end_match_2);
3068
3069 for (mcnt = 1; mcnt < num_regs; mcnt++) {
3070 regstart[mcnt] = best_regstart[mcnt];
3071 regend[mcnt] = best_regend[mcnt];
3072 }
3073 }
3074 } /* d != end_match_2 */
3075 DEBUG_PRINT1("Accepting match.\n");
3076
3077 /* If caller wants register contents data back, do it. */
3078 if (regs && !bufp->no_sub) {
3079 /* Have the register data arrays been allocated? */
3080 if (bufp->regs_allocated == REGS_UNALLOCATED) {
3081 /* No. So allocate them with malloc. We need one
3082 * extra element beyond `num_regs' for the `-1' marker
3083 * GNU code uses. */
3084 regs->num_regs = max(RE_NREGS, num_regs + 1);
3085 regs->start = TALLOC(regs->num_regs, regoff_t);
3086 regs->end = TALLOC(regs->num_regs, regoff_t);
3087 if (regs->start == NULL || regs->end == NULL)
3088 return -2;
3090 } else if (bufp->regs_allocated == REGS_REALLOCATE) {
3091 /* Yes. If we need more elements than were already
3092 * allocated, reallocate them. If we need fewer, just
3093 * leave it alone. */
3094 if (regs->num_regs < num_regs + 1) {
3095 regs->num_regs = num_regs + 1;
3096 RETALLOC(regs->start, regs->num_regs, regoff_t);
3097 RETALLOC(regs->end, regs->num_regs, regoff_t);
3098 if (regs->start == NULL || regs->end == NULL)
3099 return -2;
3100 }
3101 } else
3103
3104 /* Convert the pointer data in `regstart' and `regend' to
3105 * indices. Register zero has to be set differently,
3106 * since we haven't kept track of any info for it. */
3107 if (regs->num_regs > 0) {
3108 regs->start[0] = pos;
3109 regs->end[0] = (MATCHING_IN_FIRST_STRING ? d - string1
3110 : d - string2 + size1);
3111 }
3112 /* Go through the first `min (num_regs, regs->num_regs)'
3113 * registers, since that is all we initialized. */
3114 for (mcnt = 1; mcnt < min(num_regs, regs->num_regs); mcnt++) {
3115 if (REG_UNSET(regstart[mcnt]) || REG_UNSET(regend[mcnt]))
3116 regs->start[mcnt] = regs->end[mcnt] = -1;
3117 else {
3118 regs->start[mcnt] = POINTER_TO_OFFSET(regstart[mcnt]);
3119 regs->end[mcnt] = POINTER_TO_OFFSET(regend[mcnt]);
3120 }
3121 }
3122
3123 /* If the regs structure we return has more elements than
3124 * were in the pattern, set the extra elements to -1. If
3125 * we (re)allocated the registers, this is the case,
3126 * because we always allocate enough to have at least one
3127 * -1 at the end. */
3128 for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
3129 regs->start[mcnt] = regs->end[mcnt] = -1;
3130 } /* regs && !bufp->no_sub */
3132 DEBUG_PRINT4("%u failure points pushed, %u popped (%u remain).\n",
3133 nfailure_points_pushed, nfailure_points_popped,
3134 nfailure_points_pushed - nfailure_points_popped);
3135 DEBUG_PRINT2("%u registers pushed.\n", num_regs_pushed);
3136
3137 mcnt = d - pos - (MATCHING_IN_FIRST_STRING
3138 ? string1
3139 : string2 - size1);
3140
3141 DEBUG_PRINT2("Returning %d from re_match_2.\n", mcnt);
3142
3143 return mcnt;
3144 }
3145 /* Otherwise match next pattern command. */
3146#ifdef SWITCH_ENUM_BUG
3147 switch ((int) ((re_opcode_t) * p++))
3148#else
3149 switch ((re_opcode_t) * p++)
3150#endif
3151 {
3152 /* Ignore these. Used to ignore the n of succeed_n's which
3153 * currently have n == 0. */
3154 case no_op:
3155 DEBUG_PRINT1("EXECUTING no_op.\n");
3156 break;
3157
3158 /* Match the next n pattern characters exactly. The following
3159 * byte in the pattern defines n, and the n bytes after that
3160 * are the characters to match. */
3161 case exactn:
3162 mcnt = *p++;
3163 DEBUG_PRINT2("EXECUTING exactn %d.\n", mcnt);
3164
3165 /* This is written out as an if-else so we don't waste time
3166 * testing `translate' inside the loop. */
3167 if (translate) {
3168 do {
3169 PREFETCH();
3170 if (translate[(unsigned char) *d++] != (char) *p++)
3171 goto fail;
3172 } while (--mcnt);
3173 } else {
3174 do {
3175 PREFETCH();
3176 if (*d++ != (char) *p++)
3177 goto fail;
3178 } while (--mcnt);
3179 }
3181 break;
3182
3183 /* Match any character except possibly a newline or a null. */
3184 case anychar:
3185 DEBUG_PRINT1("EXECUTING anychar.\n");
3186
3187 PREFETCH();
3188
3189 if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE(*d) == '\n')
3190 || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE(*d) == '\000'))
3191 goto fail;
3192
3194 DEBUG_PRINT2(" Matched `%d'.\n", *d);
3195 d++;
3196 break;
3197
3198 case charset:
3199 case charset_not: {
3200 register unsigned char c;
3201 boolean not = (re_opcode_t) * (p - 1) == charset_not;
3202
3203 DEBUG_PRINT2("EXECUTING charset%s.\n", not ? "_not" : "");
3204
3205 PREFETCH();
3206 c = TRANSLATE(*d); /* The character to match. */
3207
3208 /* Cast to `unsigned' instead of `unsigned char' in case the
3209 * bit list is a full 32 bytes long. */
3210 if (c < (unsigned) (*p * BYTEWIDTH)
3211 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3212 not = !not;
3213
3214 p += 1 + *p;
3215
3216 if (!not)
3217 goto fail;
3218
3220 d++;
3221 break;
3222 }
3223
3224 /* The beginning of a group is represented by start_memory.
3225 * The arguments are the register number in the next byte, and the
3226 * number of groups inner to this one in the next. The text
3227 * matched within the group is recorded (in the internal
3228 * registers data structure) under the register number. */
3229 case start_memory:
3230 DEBUG_PRINT3("EXECUTING start_memory %d (%d):\n", *p, p[1]);
3231
3232 /* Find out if this group can match the empty string. */
3233 p1 = p; /* To send to group_match_null_string_p. */
3234
3236 REG_MATCH_NULL_STRING_P(reg_info[*p])
3237 = group_match_null_string_p(&p1, pend, reg_info);
3238
3239 /* Save the position in the string where we were the last time
3240 * we were at this open-group operator in case the group is
3241 * operated upon by a repetition operator, e.g., with `(a*)*b'
3242 * against `ab'; then we want to ignore where we are now in
3243 * the string in case this attempt to match fails. */
3244 old_regstart[*p] = REG_MATCH_NULL_STRING_P(reg_info[*p])
3245 ? REG_UNSET(regstart[*p]) ? d : regstart[*p]
3246 : regstart[*p];
3247 DEBUG_PRINT2(" old_regstart: %d\n",
3248 POINTER_TO_OFFSET(old_regstart[*p]));
3249
3250 regstart[*p] = d;
3251 DEBUG_PRINT2(" regstart: %d\n", POINTER_TO_OFFSET(regstart[*p]));
3252
3253 IS_ACTIVE(reg_info[*p]) = 1;
3254 MATCHED_SOMETHING(reg_info[*p]) = 0;
3255
3256 /* This is the new highest active register. */
3257 highest_active_reg = *p;
3258
3259 /* If nothing was active before, this is the new lowest active
3260 * register. */
3261 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3262 lowest_active_reg = *p;
3263
3264 /* Move past the register number and inner group count. */
3265 p += 2;
3266 break;
3267
3268 /* The stop_memory opcode represents the end of a group. Its
3269 * arguments are the same as start_memory's: the register
3270 * number, and the number of inner groups. */
3271 case stop_memory:
3272 DEBUG_PRINT3("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
3273
3274 /* We need to save the string position the last time we were at
3275 * this close-group operator in case the group is operated
3276 * upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
3277 * against `aba'; then we want to ignore where we are now in
3278 * the string in case this attempt to match fails. */
3279 old_regend[*p] = REG_MATCH_NULL_STRING_P(reg_info[*p])
3280 ? REG_UNSET(regend[*p]) ? d : regend[*p]
3281 : regend[*p];
3282 DEBUG_PRINT2(" old_regend: %d\n",
3283 POINTER_TO_OFFSET(old_regend[*p]));
3284
3285 regend[*p] = d;
3286 DEBUG_PRINT2(" regend: %d\n", POINTER_TO_OFFSET(regend[*p]));
3287
3288 /* This register isn't active anymore. */
3289 IS_ACTIVE(reg_info[*p]) = 0;
3290
3291 /* If this was the only register active, nothing is active
3292 * anymore. */
3293 if (lowest_active_reg == highest_active_reg) {
3294 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3295 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3296 } else {
3297 /* We must scan for the new highest active register, since
3298 * it isn't necessarily one less than now: consider
3299 * (a(b)c(d(e)f)g). When group 3 ends, after the f), the
3300 * new highest active register is 1. */
3301 unsigned char r = *p - 1;
3302 while (r > 0 && !IS_ACTIVE(reg_info[r]))
3303 r--;
3304
3305 /* If we end up at register zero, that means that we saved
3306 * the registers as the result of an `on_failure_jump', not
3307 * a `start_memory', and we jumped to past the innermost
3308 * `stop_memory'. For example, in ((.)*) we save
3309 * registers 1 and 2 as a result of the *, but when we pop
3310 * back to the second ), we are at the stop_memory 1.
3311 * Thus, nothing is active. */
3312 if (r == 0) {
3313 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3314 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3315 } else
3316 highest_active_reg = r;
3317 }
3318
3319 /* If just failed to match something this time around with a
3320 * group that's operated on by a repetition operator, try to
3321 * force exit from the ``loop'', and restore the register
3322 * information for this group that we had before trying this
3323 * last match. */
3324 if ((!MATCHED_SOMETHING(reg_info[*p])
3325 || (re_opcode_t) p[-3] == start_memory)
3326 && (p + 2) < pend) {
3327 boolean is_a_jump_n = false;
3328
3329 p1 = p + 2;
3330 mcnt = 0;
3331 switch ((re_opcode_t) * p1++) {
3332 case jump_n:
3333 is_a_jump_n = true;
3334 case pop_failure_jump:
3335 case maybe_pop_jump:
3336 case jump:
3337 case dummy_failure_jump:
3338 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3339 if (is_a_jump_n)
3340 p1 += 2;
3341 break;
3342
3343 default:
3344 /* do nothing */
3345 ;
3346 }
3347 p1 += mcnt;
3348
3349 /* If the next operation is a jump backwards in the pattern
3350 * to an on_failure_jump right before the start_memory
3351 * corresponding to this stop_memory, exit from the loop
3352 * by forcing a failure after pushing on the stack the
3353 * on_failure_jump's jump in the pattern, and d. */
3354 if (mcnt < 0 && (re_opcode_t) * p1 == on_failure_jump
3355 && (re_opcode_t) p1[3] == start_memory && p1[4] == *p) {
3356 /* If this group ever matched anything, then restore
3357 * what its registers were before trying this last
3358 * failed match, e.g., with `(a*)*b' against `ab' for
3359 * regstart[1], and, e.g., with `((a*)*(b*)*)*'
3360 * against `aba' for regend[3].
3361 *
3362 * Also restore the registers for inner groups for,
3363 * e.g., `((a*)(b*))*' against `aba' (register 3 would
3364 * otherwise get trashed). */
3365
3366 if (EVER_MATCHED_SOMETHING(reg_info[*p])) {
3367 unsigned r;
3368
3369 EVER_MATCHED_SOMETHING(reg_info[*p]) = 0;
3370
3371 /* Restore this and inner groups' (if any) registers. */
3372 for (r = *p; r < *p + *(p + 1); r++) {
3373 regstart[r] = old_regstart[r];
3374
3375 /* xx why this test? */
3376 if ((long) old_regend[r] >= (long) regstart[r])
3377 regend[r] = old_regend[r];
3378 }
3379 }
3380 p1++;
3381 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3382 PUSH_FAILURE_POINT(p1 + mcnt, d, -2);
3383
3384 goto fail;
3385 }
3386 }
3387 /* Move past the register number and the inner group count. */
3388 p += 2;
3389 break;
3390
3391 /* <digit> has been turned into a `duplicate' command which is
3392 * followed by the numeric value of <digit> as the register number. */
3393 case duplicate: {
3394 register const char *d2, *dend2;
3395 int regno = *p++; /* Get which register to match against. */
3396 DEBUG_PRINT2("EXECUTING duplicate %d.\n", regno);
3397
3398 /* Can't back reference a group which we've never matched. */
3399 if (REG_UNSET(regstart[regno]) || REG_UNSET(regend[regno]))
3400 goto fail;
3401
3402 /* Where in input to try to start matching. */
3403 d2 = regstart[regno];
3404
3405 /* Where to stop matching; if both the place to start and
3406 * the place to stop matching are in the same string, then
3407 * set to the place to stop, otherwise, for now have to use
3408 * the end of the first string. */
3409
3410 dend2 = ((FIRST_STRING_P(regstart[regno])
3411 == FIRST_STRING_P(regend[regno]))
3412 ? regend[regno] : end_match_1);
3413 for (;;) {
3414 /* If necessary, advance to next segment in register
3415 * contents. */
3416 while (d2 == dend2) {
3417 if (dend2 == end_match_2)
3418 break;
3419 if (dend2 == regend[regno])
3420 break;
3421
3422 /* End of string1 => advance to string2. */
3423 d2 = string2;
3424 dend2 = regend[regno];
3425 }
3426 /* At end of register contents => success */
3427 if (d2 == dend2)
3428 break;
3429
3430 /* If necessary, advance to next segment in data. */
3431 PREFETCH();
3432
3433 /* How many characters left in this segment to match. */
3434 mcnt = dend - d;
3435
3436 /* Want how many consecutive characters we can match in
3437 * one shot, so, if necessary, adjust the count. */
3438 if (mcnt > dend2 - d2)
3439 mcnt = dend2 - d2;
3440
3441 /* Compare that many; failure if mismatch, else move
3442 * past them. */
3443 if (translate
3444 ? bcmp_translate((unsigned char *)d, (unsigned char *)d2, mcnt, translate)
3445 : memcmp(d, d2, mcnt))
3446 goto fail;
3447 d += mcnt, d2 += mcnt;
3448 }
3449 }
3450 break;
3451
3452 /* begline matches the empty string at the beginning of the string
3453 * (unless `not_bol' is set in `bufp'), and, if
3454 * `newline_anchor' is set, after newlines. */
3455 case begline:
3456 DEBUG_PRINT1("EXECUTING begline.\n");
3457
3458 if (AT_STRINGS_BEG(d)) {
3459 if (!bufp->not_bol)
3460 break;
3461 } else if (d[-1] == '\n' && bufp->newline_anchor) {
3462 break;
3463 }
3464 /* In all other cases, we fail. */
3465 goto fail;
3466
3467 /* endline is the dual of begline. */
3468 case endline:
3469 DEBUG_PRINT1("EXECUTING endline.\n");
3470
3471 if (at_strings_end(d,end2)) {
3472 if (!bufp->not_eol)
3473 break;
3474 }
3475 /* We have to ``prefetch'' the next character. */
3476 else if ((d == end1 ? *string2 : *d) == '\n'
3477 && bufp->newline_anchor) {
3478 break;
3479 }
3480 goto fail;
3481
3482 /* Match at the very beginning of the data. */
3483 case begbuf:
3484 DEBUG_PRINT1("EXECUTING begbuf.\n");
3485 if (AT_STRINGS_BEG(d))
3486 break;
3487 goto fail;
3488
3489 /* Match at the very end of the data. */
3490 case endbuf:
3491 DEBUG_PRINT1("EXECUTING endbuf.\n");
3492 if (at_strings_end(d,end2))
3493 break;
3494 goto fail;
3495
3496 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
3497 * pushes NULL as the value for the string on the stack. Then
3498 * `pop_failure_point' will keep the current value for the
3499 * string, instead of restoring it. To see why, consider
3500 * matching `foo\nbar' against `.*\n'. The .* matches the foo;
3501 * then the . fails against the \n. But the next thing we want
3502 * to do is match the \n against the \n; if we restored the
3503 * string value, we would be back at the foo.
3504 *
3505 * Because this is used only in specific cases, we don't need to
3506 * check all the things that `on_failure_jump' does, to make
3507 * sure the right things get saved on the stack. Hence we don't
3508 * share its code. The only reason to push anything on the
3509 * stack at all is that otherwise we would have to change
3510 * `anychar's code to do something besides goto fail in this
3511 * case; that seems worse than this. */
3513 DEBUG_PRINT1("EXECUTING on_failure_keep_string_jump");
3514
3515 EXTRACT_NUMBER_AND_INCR(mcnt, p);
3516 DEBUG_PRINT3(" %d (to 0x%x):\n", mcnt, p + mcnt);
3517
3518 PUSH_FAILURE_POINT(p + mcnt, NULL, -2);
3519 break;
3520
3521 /* Uses of on_failure_jump:
3522 *
3523 * Each alternative starts with an on_failure_jump that points
3524 * to the beginning of the next alternative. Each alternative
3525 * except the last ends with a jump that in effect jumps past
3526 * the rest of the alternatives. (They really jump to the
3527 * ending jump of the following alternative, because tensioning
3528 * these jumps is a hassle.)
3529 *
3530 * Repeats start with an on_failure_jump that points past both
3531 * the repetition text and either the following jump or
3532 * pop_failure_jump back to this on_failure_jump. */
3533 case on_failure_jump:
3534on_failure:
3535 DEBUG_PRINT1("EXECUTING on_failure_jump");
3536
3537 EXTRACT_NUMBER_AND_INCR(mcnt, p);
3538 DEBUG_PRINT3(" %d (to 0x%x)", mcnt, p + mcnt);
3539
3540 /* If this on_failure_jump comes right before a group (i.e.,
3541 * the original * applied to a group), save the information
3542 * for that group and all inner ones, so that if we fail back
3543 * to this point, the group's information will be correct.
3544 * For example, in \‍(a*\‍)*\1, we need the preceding group,
3545 * and in \‍(\‍(a*\‍)b*\‍)\2, we need the inner group. */
3546
3547 /* We can't use `p' to check ahead because we push
3548 * a failure point to `p + mcnt' after we do this. */
3549 p1 = p;
3550
3551 /* We need to skip no_op's before we look for the
3552 * start_memory in case this on_failure_jump is happening as
3553 * the result of a completed succeed_n, as in \‍(a\‍)\{1,3\}b\1
3554 * against aba. */
3555 while (p1 < pend && (re_opcode_t) * p1 == no_op)
3556 p1++;
3557
3558 if (p1 < pend && (re_opcode_t) * p1 == start_memory) {
3559 /* We have a new highest active register now. This will
3560 * get reset at the start_memory we are about to get to,
3561 * but we will have saved all the registers relevant to
3562 * this repetition op, as described above. */
3563 highest_active_reg = *(p1 + 1) + *(p1 + 2);
3564 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3565 lowest_active_reg = *(p1 + 1);
3566 }
3567 DEBUG_PRINT1(":\n");
3568 PUSH_FAILURE_POINT(p + mcnt, d, -2);
3569 break;
3570
3571 /* A smart repeat ends with `maybe_pop_jump'.
3572 * We change it to either `pop_failure_jump' or `jump'. */
3573 case maybe_pop_jump:
3574 EXTRACT_NUMBER_AND_INCR(mcnt, p);
3575 DEBUG_PRINT2("EXECUTING maybe_pop_jump %d.\n", mcnt);
3576 {
3577 register unsigned char *p2 = p;
3578
3579 /* Compare the beginning of the repeat with what in the
3580 * pattern follows its end. If we can establish that there
3581 * is nothing that they would both match, i.e., that we
3582 * would have to backtrack because of (as in, e.g., `a*a')
3583 * then we can change to pop_failure_jump, because we'll
3584 * never have to backtrack.
3585 *
3586 * This is not true in the case of alternatives: in
3587 * `(a|ab)*' we do need to backtrack to the `ab' alternative
3588 * (e.g., if the string was `ab'). But instead of trying to
3589 * detect that here, the alternative has put on a dummy
3590 * failure point which is what we will end up popping. */
3591
3592 /* Skip over open/close-group commands. */
3593 while (p2 + 2 < pend
3594 && ((re_opcode_t) * p2 == stop_memory
3595 || (re_opcode_t) * p2 == start_memory))
3596 p2 += 3; /* Skip over args, too. */
3597
3598 /* If we're at the end of the pattern, we can change. */
3599 if (p2 == pend) {
3600 /* Consider what happens when matching ":\‍(.*\‍)"
3601 * against ":/". I don't really understand this code
3602 * yet. */
3603 p[-3] = (unsigned char) pop_failure_jump;
3605 (" End of pattern: change to `pop_failure_jump'.\n");
3606 } else if ((re_opcode_t) * p2 == exactn
3607 || (bufp->newline_anchor && (re_opcode_t) * p2 == endline)) {
3608 register unsigned char c
3609 = *p2 == (unsigned char) endline ? '\n' : p2[2];
3610 p1 = p + mcnt;
3611
3612 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
3613 * to the `maybe_finalize_jump' of this case. Examine what
3614 * follows. */
3615 if ((re_opcode_t) p1[3] == exactn && p1[5] != c) {
3616 p[-3] = (unsigned char) pop_failure_jump;
3617 DEBUG_PRINT3(" %c != %c => pop_failure_jump.\n",
3618 c, p1[5]);
3619 } else if ((re_opcode_t) p1[3] == charset
3620 || (re_opcode_t) p1[3] == charset_not) {
3621 int not = (re_opcode_t) p1[3] == charset_not;
3622
3623 if (c < (unsigned char) (p1[4] * BYTEWIDTH)
3624 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3625 not = !not;
3626
3627 /* `not' is equal to 1 if c would match, which means
3628 * that we can't change to pop_failure_jump. */
3629 if (!not) {
3630 p[-3] = (unsigned char) pop_failure_jump;
3631 DEBUG_PRINT1(" No match => pop_failure_jump.\n");
3632 }
3633 }
3634 }
3635 }
3636 p -= 2; /* Point at relative address again. */
3637 if ((re_opcode_t) p[-1] != pop_failure_jump) {
3638 p[-1] = (unsigned char) jump;
3639 DEBUG_PRINT1(" Match => jump.\n");
3640 goto unconditional_jump;
3641 }
3642 /* Note fall through. */
3643
3644 /* The end of a simple repeat has a pop_failure_jump back to
3645 * its matching on_failure_jump, where the latter will push a
3646 * failure point. The pop_failure_jump takes off failure
3647 * points put on by this pop_failure_jump's matching
3648 * on_failure_jump; we got through the pattern to here from the
3649 * matching on_failure_jump, so didn't fail. */
3650 case pop_failure_jump: {
3651 /* We need to pass separate storage for the lowest and
3652 * highest registers, even though we don't care about the
3653 * actual values. Otherwise, we will restore only one
3654 * register from the stack, since lowest will == highest in
3655 * `pop_failure_point'. */
3656 unsigned long dummy_low_reg, dummy_high_reg;
3657 unsigned char *pdummy;
3658 const char *sdummy;
3659
3660 DEBUG_PRINT1("EXECUTING pop_failure_jump.\n");
3661 POP_FAILURE_POINT(sdummy, pdummy,
3662 dummy_low_reg, dummy_high_reg,
3663 reg_dummy, reg_dummy, reg_info_dummy);
3664 /* avoid GCC 4.6 set but unused variables warning. Does not matter here. */
3665 if (pdummy || sdummy)
3666 (void)0;
3667 }
3668 /* Note fall through. */
3669
3670 /* Unconditionally jump (without popping any failure points). */
3671 case jump:
3672unconditional_jump:
3673 EXTRACT_NUMBER_AND_INCR(mcnt, p); /* Get the amount to jump. */
3674 DEBUG_PRINT2("EXECUTING jump %d ", mcnt);
3675 p += mcnt; /* Do the jump. */
3676 DEBUG_PRINT2("(to 0x%x).\n", p);
3677 break;
3678
3679 /* We need this opcode so we can detect where alternatives end
3680 * in `group_match_null_string_p' et al. */
3681 case jump_past_alt:
3682 DEBUG_PRINT1("EXECUTING jump_past_alt.\n");
3683 goto unconditional_jump;
3684
3685 /* Normally, the on_failure_jump pushes a failure point, which
3686 * then gets popped at pop_failure_jump. We will end up at
3687 * pop_failure_jump, also, and with a pattern of, say, `a+', we
3688 * are skipping over the on_failure_jump, so we have to push
3689 * something meaningless for pop_failure_jump to pop. */
3690 case dummy_failure_jump:
3691 DEBUG_PRINT1("EXECUTING dummy_failure_jump.\n");
3692 /* It doesn't matter what we push for the string here. What
3693 * the code at `fail' tests is the value for the pattern. */
3694 PUSH_FAILURE_POINT(0, 0, -2);
3695 goto unconditional_jump;
3696
3697 /* At the end of an alternative, we need to push a dummy failure
3698 * point in case we are followed by a `pop_failure_jump', because
3699 * we don't want the failure point for the alternative to be
3700 * popped. For example, matching `(a|ab)*' against `aab'
3701 * requires that we match the `ab' alternative. */
3702 case push_dummy_failure:
3703 DEBUG_PRINT1("EXECUTING push_dummy_failure.\n");
3704 /* See comments just above at `dummy_failure_jump' about the
3705 * two zeroes. */
3706 PUSH_FAILURE_POINT(0, 0, -2);
3707 break;
3708
3709 /* Have to succeed matching what follows at least n times.
3710 * After that, handle like `on_failure_jump'. */
3711 case succeed_n:
3712 EXTRACT_NUMBER(mcnt, p + 2);
3713 DEBUG_PRINT2("EXECUTING succeed_n %d.\n", mcnt);
3714
3715 assert(mcnt >= 0);
3716 /* Originally, this is how many times we HAVE to succeed. */
3717 if (mcnt > 0) {
3718 mcnt--;
3719 p += 2;
3720 STORE_NUMBER_AND_INCR(p, mcnt);
3721 DEBUG_PRINT3(" Setting 0x%x to %d.\n", p, mcnt);
3722 } else if (mcnt == 0) {
3723 DEBUG_PRINT2(" Setting two bytes from 0x%x to no_op.\n", p + 2);
3724 p[2] = (unsigned char) no_op;
3725 p[3] = (unsigned char) no_op;
3726 goto on_failure;
3727 }
3728 break;
3729
3730 case jump_n:
3731 EXTRACT_NUMBER(mcnt, p + 2);
3732 DEBUG_PRINT2("EXECUTING jump_n %d.\n", mcnt);
3733
3734 /* Originally, this is how many times we CAN jump. */
3735 if (mcnt) {
3736 mcnt--;
3737 STORE_NUMBER(p + 2, mcnt);
3738 goto unconditional_jump;
3739 }
3740 /* If don't have to jump any more, skip over the rest of command. */
3741 else
3742 p += 4;
3743 break;
3744
3745 case set_number_at: {
3746 DEBUG_PRINT1("EXECUTING set_number_at.\n");
3747
3748 EXTRACT_NUMBER_AND_INCR(mcnt, p);
3749 p1 = p + mcnt;
3750 EXTRACT_NUMBER_AND_INCR(mcnt, p);
3751 DEBUG_PRINT3(" Setting 0x%x to %d.\n", p1, mcnt);
3752 STORE_NUMBER(p1, mcnt);
3753 break;
3754 }
3755
3756 case wordbound:
3757 DEBUG_PRINT1("EXECUTING wordbound.\n");
3758 if (AT_WORD_BOUNDARY(d))
3759 break;
3760 goto fail;
3761
3762 case notwordbound:
3763 DEBUG_PRINT1("EXECUTING notwordbound.\n");
3764 if (AT_WORD_BOUNDARY(d))
3765 goto fail;
3766 break;
3767
3768 case wordbeg:
3769 DEBUG_PRINT1("EXECUTING wordbeg.\n");
3770 if (wordchar_p(d,end1,string2) && (AT_STRINGS_BEG(d) || !WORDCHAR_P(d - 1)))
3771 break;
3772 goto fail;
3773
3774 case wordend:
3775 DEBUG_PRINT1("EXECUTING wordend.\n");
3776 if (!AT_STRINGS_BEG(d) && WORDCHAR_P(d - 1)
3777 && (!wordchar_p(d,end1,string2) || at_strings_end(d,end2)))
3778 break;
3779 goto fail;
3780
3781 case wordchar:
3782 DEBUG_PRINT1("EXECUTING non-Emacs wordchar.\n");
3783 PREFETCH();
3784 if (!wordchar_p(d,end1,string2))
3785 goto fail;
3787 d++;
3788 break;
3789
3790 case notwordchar:
3791 DEBUG_PRINT1("EXECUTING non-Emacs notwordchar.\n");
3792 PREFETCH();
3793 if (wordchar_p(d,end1,string2))
3794 goto fail;
3796 d++;
3797 break;
3798
3799 default:
3800 abort();
3801 }
3802 continue; /* Successfully executed one pattern command; keep going. */
3803
3804 /* We goto here if a matching operation fails. */
3805fail:
3806 if (!FAIL_STACK_EMPTY()) { /* A restart point is known. Restore to that state. */
3807 DEBUG_PRINT1("\nFAIL:\n");
3808 POP_FAILURE_POINT(d, p,
3809 lowest_active_reg, highest_active_reg,
3810 regstart, regend, reg_info);
3811
3812 /* If this failure point is a dummy, try the next one. */
3813 if (!p)
3814 goto fail;
3815
3816 /* If we failed to the end of the pattern, don't examine *p. */
3817 assert(p <= pend);
3818 if (p < pend) {
3819 boolean is_a_jump_n = false;
3820
3821 /* If failed to a backwards jump that's part of a repetition
3822 * loop, need to pop this failure point and use the next one. */
3823 switch ((re_opcode_t) * p) {
3824 case jump_n:
3825 is_a_jump_n = true;
3826 case maybe_pop_jump:
3827 case pop_failure_jump:
3828 case jump:
3829 p1 = p + 1;
3830 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3831 p1 += mcnt;
3832
3833 if ((is_a_jump_n && (re_opcode_t) * p1 == succeed_n)
3834 || (!is_a_jump_n
3835 && (re_opcode_t) * p1 == on_failure_jump))
3836 goto fail;
3837 break;
3838 default:
3839 /* do nothing */
3840 ;
3841 }
3842 }
3843 if (d >= string1 && d <= end1)
3844 dend = end_match_1;
3845 } else
3846 break; /* Matching at this starting point really fails. */
3847 } /* for (;;) */
3848
3849 if (best_regs_set)
3850 goto restore_best_regs;
3851
3853
3854 return -1; /* Failure to match. */
3855} /* re_match_2 */
3856
3857/* Subroutine definitions for re_match_2. */
3858
3859/* We are passed P pointing to a register number after a start_memory.
3860 *
3861 * Return true if the pattern up to the corresponding stop_memory can
3862 * match the empty string, and false otherwise.
3863 *
3864 * If we find the matching stop_memory, sets P to point to one past its number.
3865 * Otherwise, sets P to an undefined byte less than or equal to END.
3866 *
3867 * We don't handle duplicates properly (yet). */
3868
3869boolean
3870group_match_null_string_p(unsigned char **p, unsigned char *end, register_info_type *reg_info)
3871{
3872 int mcnt;
3873 /* Point to after the args to the start_memory. */
3874 unsigned char *p1 = *p + 2;
3875
3876 while (p1 < end) {
3877 /* Skip over opcodes that can match nothing, and return true or
3878 * false, as appropriate, when we get to one that can't, or to the
3879 * matching stop_memory. */
3880
3881 switch ((re_opcode_t) * p1) {
3882 /* Could be either a loop or a series of alternatives. */
3883 case on_failure_jump:
3884 p1++;
3885 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3886
3887 /* If the next operation is not a jump backwards in the
3888 * pattern. */
3889
3890 if (mcnt >= 0) {
3891 /* Go through the on_failure_jumps of the alternatives,
3892 * seeing if any of the alternatives cannot match nothing.
3893 * The last alternative starts with only a jump,
3894 * whereas the rest start with on_failure_jump and end
3895 * with a jump, e.g., here is the pattern for `a|b|c':
3896 *
3897 * /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
3898 * /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
3899 * /exactn/1/c
3900 *
3901 * So, we have to first go through the first (n-1)
3902 * alternatives and then deal with the last one separately. */
3903
3904 /* Deal with the first (n-1) alternatives, which start
3905 * with an on_failure_jump (see above) that jumps to right
3906 * past a jump_past_alt. */
3907
3908 while ((re_opcode_t) p1[mcnt - 3] == jump_past_alt) {
3909 /* `mcnt' holds how many bytes long the alternative
3910 * is, including the ending `jump_past_alt' and
3911 * its number. */
3912
3913 if (!alt_match_null_string_p(p1, p1 + mcnt - 3,
3914 reg_info))
3915 return false;
3916
3917 /* Move to right after this alternative, including the
3918 * jump_past_alt. */
3919 p1 += mcnt;
3920
3921 /* Break if it's the beginning of an n-th alternative
3922 * that doesn't begin with an on_failure_jump. */
3923 if ((re_opcode_t) * p1 != on_failure_jump)
3924 break;
3925
3926 /* Still have to check that it's not an n-th
3927 * alternative that starts with an on_failure_jump. */
3928 p1++;
3929 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3930 if ((re_opcode_t) p1[mcnt - 3] != jump_past_alt) {
3931 /* Get to the beginning of the n-th alternative. */
3932 p1 -= 3;
3933 break;
3934 }
3935 }
3936
3937 /* Deal with the last alternative: go back and get number
3938 * of the `jump_past_alt' just before it. `mcnt' contains
3939 * the length of the alternative. */
3940 EXTRACT_NUMBER(mcnt, p1 - 2);
3941
3942 if (!alt_match_null_string_p(p1, p1 + mcnt, reg_info))
3943 return false;
3944
3945 p1 += mcnt; /* Get past the n-th alternative. */
3946 } /* if mcnt > 0 */
3947 break;
3948
3949 case stop_memory:
3950 assert(p1[1] == **p);
3951 *p = p1 + 2;
3952 return true;
3953
3954 default:
3955 if (!common_op_match_null_string_p(&p1, end, reg_info))
3956 return false;
3957 }
3958 } /* while p1 < end */
3959
3960 return false;
3961} /* group_match_null_string_p */
3962
3963/* Similar to group_match_null_string_p, but doesn't deal with alternatives:
3964 * It expects P to be the first byte of a single alternative and END one
3965 * byte past the last. The alternative can contain groups. */
3966
3967boolean
3968alt_match_null_string_p(unsigned char *p, unsigned char *end, register_info_type *reg_info)
3969{
3970 int mcnt;
3971 unsigned char *p1 = p;
3972
3973 while (p1 < end) {
3974 /* Skip over opcodes that can match nothing, and break when we get
3975 * to one that can't. */
3976
3977 switch ((re_opcode_t) * p1) {
3978 /* It's a loop. */
3979 case on_failure_jump:
3980 p1++;
3981 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
3982 p1 += mcnt;
3983 break;
3984
3985 default:
3986 if (!common_op_match_null_string_p(&p1, end, reg_info))
3987 return false;
3988 }
3989 } /* while p1 < end */
3990
3991 return true;
3992} /* alt_match_null_string_p */
3993
3994/* Deals with the ops common to group_match_null_string_p and
3995 * alt_match_null_string_p.
3996 *
3997 * Sets P to one after the op and its arguments, if any. */
3998
3999boolean
4000common_op_match_null_string_p( unsigned char **p, unsigned char *end, register_info_type *reg_info)
4001{
4002 int mcnt;
4003 boolean ret;
4004 int reg_no;
4005 unsigned char *p1 = *p;
4006
4007 switch ((re_opcode_t) * p1++) {
4008 case no_op:
4009 case begline:
4010 case endline:
4011 case begbuf:
4012 case endbuf:
4013 case wordbeg:
4014 case wordend:
4015 case wordbound:
4016 case notwordbound:
4017 break;
4018
4019 case start_memory:
4020 reg_no = *p1;
4021 assert(reg_no > 0 && reg_no <= MAX_REGNUM);
4022 ret = group_match_null_string_p(&p1, end, reg_info);
4023
4024 /* Have to set this here in case we're checking a group which
4025 * contains a group and a back reference to it. */
4026
4027 if (REG_MATCH_NULL_STRING_P(reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
4028 REG_MATCH_NULL_STRING_P(reg_info[reg_no]) = ret;
4029
4030 if (!ret)
4031 return false;
4032 break;
4033
4034 /* If this is an optimized succeed_n for zero times, make the jump. */
4035 case jump:
4036 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
4037 if (mcnt >= 0)
4038 p1 += mcnt;
4039 else
4040 return false;
4041 break;
4042
4043 case succeed_n:
4044 /* Get to the number of times to succeed. */
4045 p1 += 2;
4046 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
4047
4048 if (mcnt == 0) {
4049 p1 -= 4;
4050 EXTRACT_NUMBER_AND_INCR(mcnt, p1);
4051 p1 += mcnt;
4052 } else
4053 return false;
4054 break;
4055
4056 case duplicate:
4057 if (!REG_MATCH_NULL_STRING_P(reg_info[*p1]))
4058 return false;
4059 break;
4060
4061 case set_number_at:
4062 p1 += 4;
4063
4064 default:
4065 /* All other opcodes mean we cannot match the empty string. */
4066 return false;
4067 }
4068
4069 *p = p1;
4070 return true;
4071} /* common_op_match_null_string_p */
4072
4073/* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
4074 * bytes; nonzero otherwise. */
4075
4076int
4077bcmp_translate(unsigned char const *s1, unsigned char const*s2, register int len, char *translate)
4078{
4079 register unsigned char const *p1 = s1, *p2 = s2;
4080 while (len) {
4081 if (translate[*p1++] != translate[*p2++])
4082 return 1;
4083 len--;
4084 }
4085 return 0;
4086}
4087
4088/* Entry points for GNU code. */
4089
4090/* POSIX.2 functions */
4091
4092/* regcomp takes a regular expression as a string and compiles it.
4093 *
4094 * PREG is a regex_t *. We do not expect any fields to be initialized,
4095 * since POSIX says we shouldn't. Thus, we set
4096 *
4097 * `buffer' to the compiled pattern;
4098 * `used' to the length of the compiled pattern;
4099 * `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
4100 * REG_EXTENDED bit in CFLAGS is set; otherwise, to
4101 * RE_SYNTAX_POSIX_BASIC;
4102 * `newline_anchor' to REG_NEWLINE being set in CFLAGS;
4103 * `fastmap' and `fastmap_accurate' to zero;
4104 * `re_nsub' to the number of subexpressions in PATTERN.
4105 *
4106 * PATTERN is the address of the pattern string.
4107 *
4108 * CFLAGS is a series of bits which affect compilation.
4109 *
4110 * If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
4111 * use POSIX basic syntax.
4112 *
4113 * If REG_NEWLINE is set, then . and [^...] don't match newline.
4114 * Also, regexec will try a match beginning after every newline.
4115 *
4116 * If REG_ICASE is set, then we considers upper- and lowercase
4117 * versions of letters to be equivalent when matching.
4118 *
4119 * If REG_NOSUB is set, then when PREG is passed to regexec, that
4120 * routine will report only success or failure, and nothing about the
4121 * registers.
4122 *
4123 * It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
4124 * the return codes and their meanings.) */
4125
4126int
4127regcomp(preg, pattern, cflags)
4128regex_t *preg;
4129const char *pattern;
4130int cflags;
4131{
4132 reg_errcode_t ret;
4133 unsigned syntax
4134 = (cflags & REG_EXTENDED) ?
4136
4137 /* regex_compile will allocate the space for the compiled pattern. */
4138 preg->buffer = 0;
4139 preg->allocated = 0;
4140
4141 /* Don't bother to use a fastmap when searching. This simplifies the
4142 * REG_NEWLINE case: if we used a fastmap, we'd have to put all the
4143 * characters after newlines into the fastmap. This way, we just try
4144 * every character. */
4145 preg->fastmap = 0;
4146
4147 if (cflags & REG_ICASE) {
4148 unsigned i;
4149
4150 preg->translate = (char *) malloc(CHAR_SET_SIZE);
4151 if (preg->translate == NULL)
4152 return (int) REG_ESPACE;
4153
4154 /* Map uppercase characters to corresponding lowercase ones. */
4155 for (i = 0; i < CHAR_SET_SIZE; i++)
4156 preg->translate[i] = ISUPPER(i) ? tolower(i) : i;
4157 } else
4158 preg->translate = NULL;
4159
4160 /* If REG_NEWLINE is set, newlines are treated differently. */
4161 if (cflags & REG_NEWLINE) { /* REG_NEWLINE implies neither . nor [^...] match newline. */
4162 syntax &= ~RE_DOT_NEWLINE;
4163 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
4164 /* It also changes the matching behavior. */
4165 preg->newline_anchor = 1;
4166 } else
4167 preg->newline_anchor = 0;
4168
4169 preg->no_sub = !!(cflags & REG_NOSUB);
4170
4171 /* POSIX says a null character in the pattern terminates it, so we
4172 * can use strlen here in compiling the pattern. */
4173 ret = regex_compile(pattern, strlen(pattern), syntax, preg);
4174
4175 /* POSIX doesn't distinguish between an unmatched open-group and an
4176 * unmatched close-group: both are REG_EPAREN. */
4177 if (ret == REG_ERPAREN)
4178 ret = REG_EPAREN;
4179
4180 return (int) ret;
4181}
4182
4183/* regexec searches for a given pattern, specified by PREG, in the
4184 * string STRING.
4185 *
4186 * If NMATCH is zero or REG_NOSUB was set in the cflags argument to
4187 * `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
4188 * least NMATCH elements, and we set them to the offsets of the
4189 * corresponding matched substrings.
4190 *
4191 * EFLAGS specifies `execution flags' which affect matching: if
4192 * REG_NOTBOL is set, then ^ does not match at the beginning of the
4193 * string; if REG_NOTEOL is set, then $ does not match at the end.
4194 *
4195 * We return 0 if we find a match and REG_NOMATCH if not. */
4196
4197int
4198regexec(preg, string, nmatch, pmatch, eflags)
4199const regex_t *preg;
4200const char *string;
4201size_t nmatch;
4202regmatch_t pmatch[];
4203int eflags;
4204{
4205 int ret;
4206 struct re_registers regs;
4207 regex_t private_preg;
4208 int len = strlen(string);
4209 boolean want_reg_info = !preg->no_sub && nmatch > 0;
4210
4211 private_preg = *preg;
4212
4213 private_preg.not_bol = !!(eflags & REG_NOTBOL);
4214 private_preg.not_eol = !!(eflags & REG_NOTEOL);
4215
4216 /* The user has told us exactly how many registers to return
4217 * information about, via `nmatch'. We have to pass that on to the
4218 * matching routines. */
4219 private_preg.regs_allocated = REGS_FIXED;
4220
4221 if (want_reg_info) {
4222 regs.num_regs = nmatch;
4223 regs.start = TALLOC(nmatch, regoff_t);
4224 regs.end = TALLOC(nmatch, regoff_t);
4225 if (regs.start == NULL || regs.end == NULL)
4226 return (int) REG_NOMATCH;
4227 }
4228 /* Perform the searching operation. */
4229 ret = re_search(&private_preg, string, len,
4230 /* start: */ 0, /* range: */ len,
4231 want_reg_info ? &regs : (struct re_registers *) 0);
4232
4233 /* Copy the register information to the POSIX structure. */
4234 if (want_reg_info) {
4235 if (ret >= 0) {
4236 unsigned r;
4237
4238 for (r = 0; r < nmatch; r++) {
4239 pmatch[r].rm_so = regs.start[r];
4240 pmatch[r].rm_eo = regs.end[r];
4241 }
4242 }
4243 /* If we needed the temporary register info, free the space now. */
4244 free(regs.start);
4245 free(regs.end);
4246 }
4247 /* We want zero return to mean success, unlike `re_search'. */
4248 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
4249}
4250
4251/* Returns a message corresponding to an error code, ERRCODE, returned
4252 * from either regcomp or regexec. We don't use PREG here. */
4253
4254size_t
4255regerror(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
4256{
4257 const char *msg;
4258 size_t msg_size;
4259
4260 if (errcode < 0
4261 || errcode >= (sizeof(re_error_msg) / sizeof(re_error_msg[0])))
4262 /* Only error codes returned by the rest of the code should be passed
4263 * to this routine. If we are given anything else, or if other regex
4264 * code generates an invalid error code, then the program has a bug.
4265 * Dump core so we can fix it. */
4266 abort();
4267
4268 msg = re_error_msg[errcode];
4269
4270 /* POSIX doesn't require that we do anything in this case, but why
4271 * not be nice. */
4272 if (!msg)
4273 msg = "Success";
4274
4275 msg_size = strlen(msg) + 1; /* Includes the null. */
4276
4277 if (errbuf_size != 0) {
4278 if (msg_size > errbuf_size) {
4279 strncpy(errbuf, msg, errbuf_size - 1);
4280 errbuf[errbuf_size - 1] = 0;
4281 } else
4282 strcpy(errbuf, msg);
4283 }
4284 return msg_size;
4285}
4286
4287/* Free dynamically allocated space used by PREG. */
4288
4289void
4290regfree(preg)
4291regex_t *preg;
4292{
4293 if (preg->buffer != NULL)
4294 free(preg->buffer);
4295 preg->buffer = NULL;
4296
4297 preg->allocated = 0;
4298 preg->used = 0;
4299
4300 if (preg->fastmap != NULL)
4301 free(preg->fastmap);
4302 preg->fastmap = NULL;
4303 preg->fastmap_accurate = 0;
4304
4305 if (preg->translate != NULL)
4306 free(preg->translate);
4307 preg->translate = NULL;
4308}
4309#endif /* USE_GNUREGEX */
4310
4311/*
4312 * Local variables:
4313 * make-backup-files: t
4314 * version-control: t
4315 * trim-versions-without-asking: nil
4316 * End:
4317 */
4318
int regexec(regex_t *preg, const char *string, size_t nmatch, pmatch, int eflags) const
Definition: GnuRegex.c:4195
#define PREFETCH()
Definition: GnuRegex.c:2733
#define CHAR_CLASS_MAX_LENGTH
Definition: GnuRegex.c:930
size_t regerror(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
Definition: GnuRegex.c:4252
int pattern_offset_t
Definition: GnuRegex.c:878
#define INIT_FAIL_STACK()
Definition: GnuRegex.c:2053
static reg_errcode_t compile_range(const char **p_ptr, const char *pend, char *translate, reg_syntax_t syntax, unsigned char *b)
Definition: GnuRegex.c:1982
#define ISPUNCT(c)
Definition: GnuRegex.c:160
static int bcmp_translate(unsigned char const *s1, unsigned char const *s2, register int len, char *translate)
Definition: GnuRegex.c:4074
static void insert_op1(re_opcode_t op, unsigned char *loc, int arg, unsigned char *end)
Definition: GnuRegex.c:1892
static boolean group_in_compile_stack(compile_stack_type compile_stack, regnum_t regnum)
Definition: GnuRegex.c:1957
#define FAIL_STACK_EMPTY()
Definition: GnuRegex.c:2046
static reg_errcode_t regex_compile(const char *pattern, int size, reg_syntax_t syntax, struct re_pattern_buffer *bufp)
Definition: GnuRegex.c:959
int re_max_failures
Definition: GnuRegex.c:2036
#define ISUPPER(c)
Definition: GnuRegex.c:162
#define TRANSLATE(d)
Definition: GnuRegex.c:778
static void insert_op2(re_opcode_t op, unsigned char *loc, int arg1, int arg2, unsigned char *end)
Definition: GnuRegex.c:1906
#define ISGRAPH(c)
Definition: GnuRegex.c:151
char boolean
Definition: GnuRegex.c:238
#define ISBLANK(c)
Definition: GnuRegex.c:146
#define MATCHED_SOMETHING(R)
Definition: GnuRegex.c:2699
int regcomp(regex_t *preg, const char *pattern, int cflags)
Definition: GnuRegex.c:4124
#define BUF_PUSH_3(c1, c2, c3)
Definition: GnuRegex.c:806
#define COMPILE_STACK_TOP
Definition: GnuRegex.c:906
#define Sword
Definition: GnuRegex.c:67
#define ISXDIGIT(c)
Definition: GnuRegex.c:163
#define FIRST_STRING_P(ptr)
Definition: GnuRegex.c:225
#define AT_STRINGS_BEG(d)
Definition: GnuRegex.c:2746
#define INSERT_JUMP(op, loc, to)
Definition: GnuRegex.c:824
#define IS_ACTIVE(R)
Definition: GnuRegex.c:2698
#define ISCNTRL(c)
Definition: GnuRegex.c:158
#define NO_LOWEST_ACTIVE_REG
Definition: GnuRegex.c:2803
#define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)
Definition: GnuRegex.c:2230
#define PATFETCH(c)
Definition: GnuRegex.c:758
#define INIT_BUF_SIZE
Definition: GnuRegex.c:783
static boolean at_endline_loc_p(const char *p, const char *pend, int syntax)
Definition: GnuRegex.c:1938
static boolean common_op_match_null_string_p(unsigned char **p, unsigned char *end, register_info_type *reg_info)
Definition: GnuRegex.c:3997
#define STORE_NUMBER(destination, number)
Definition: GnuRegex.c:373
static int re_search_2(struct re_pattern_buffer *buffer, const char *string1, int length1, const char *string2, int length2, int start, int range, struct re_registers *regs, int stop)
Definition: GnuRegex.c:2563
#define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)
Definition: GnuRegex.c:2123
#define PUSH_PATTERN_OP(pattern_op, fail_stack)
Definition: GnuRegex.c:2089
#define PATUNFETCH
Definition: GnuRegex.c:772
#define REG_UNSET_VALUE
Definition: GnuRegex.c:2724
#define MATCHING_IN_FIRST_STRING
Definition: GnuRegex.c:2729
#define INSERT_JUMP2(op, loc, to, arg)
Definition: GnuRegex.c:828
#define FREE_VARIABLES()
Definition: GnuRegex.c:2777
#define GET_BUFFER_SPACE(n)
Definition: GnuRegex.c:786
const unsigned char * fail_stack_elt_t
Definition: GnuRegex.c:2038
static void store_op1(re_opcode_t op, unsigned char *loc, int arg)
Definition: GnuRegex.c:1872
static char re_syntax_table[CHAR_SET_SIZE]
Definition: GnuRegex.c:79
#define IS_CHAR_CLASS(string)
Definition: GnuRegex.c:932
#define POINTER_TO_OFFSET(ptr)
Definition: GnuRegex.c:2720
#define ISALNUM(c)
Definition: GnuRegex.c:156
#define BUF_PUSH_2(c1, c2)
Definition: GnuRegex.c:798
#define DEBUG_PRINT1(x)
Definition: GnuRegex.c:721
#define PATFETCH_RAW(c)
Definition: GnuRegex.c:766
static int re_search(struct re_pattern_buffer *buffer, const char *string, int length, int start, int range, struct re_registers *regs)
Definition: GnuRegex.c:2531
#define INIT_COMPILE_STACK_SIZE
Definition: GnuRegex.c:903
#define EXTRACT_NUMBER(destination, source)
Definition: GnuRegex.c:392
#define WORDCHAR_P(d)
Definition: GnuRegex.c:2756
unsigned regnum_t
Definition: GnuRegex.c:872
#define MATCH_NULL_UNSET_VALUE
Definition: GnuRegex.c:2685
#define SET_LIST_BIT(c)
Definition: GnuRegex.c:909
static void init_syntax_once(void)
Definition: GnuRegex.c:82
#define SET_REGS_MATCHED()
Definition: GnuRegex.c:2705
#define STORE_JUMP2(op, loc, to, arg)
Definition: GnuRegex.c:820
static int re_compile_fastmap(struct re_pattern_buffer *buffer)
Definition: GnuRegex.c:2302
#define REGEX_TALLOC(n, t)
Definition: GnuRegex.c:231
#define DEBUG_PRINT2(x1, x2)
Definition: GnuRegex.c:722
#define GET_UNSIGNED_NUMBER(num)
Definition: GnuRegex.c:914
static int at_strings_end(const char *d, const char *end2)
Definition: GnuRegex.c:2747
static boolean group_match_null_string_p(unsigned char **p, unsigned char *end, register_info_type *reg_info)
Definition: GnuRegex.c:3867
#define TALLOC(n, t)
Definition: GnuRegex.c:229
#define STREQ(s1, s2)
Definition: GnuRegex.c:235
#define ISDIGIT(c)
Definition: GnuRegex.c:155
#define NO_HIGHEST_ACTIVE_REG
Definition: GnuRegex.c:2802
#define EXTRACT_NUMBER_AND_INCR(destination, source)
Definition: GnuRegex.c:419
static boolean alt_match_null_string_p(unsigned char *p, unsigned char *end, register_info_type *reg_info)
Definition: GnuRegex.c:3965
#define REG_MATCH_NULL_STRING_P(R)
Definition: GnuRegex.c:2697
#define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
Definition: GnuRegex.c:725
#define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
Definition: GnuRegex.c:726
#define DEBUG_PRINT4(x1, x2, x3, x4)
Definition: GnuRegex.c:724
#define ISLOWER(c)
Definition: GnuRegex.c:159
#define STORE_JUMP(op, loc, to)
Definition: GnuRegex.c:816
re_opcode_t
Definition: GnuRegex.c:252
@ notwordchar
Definition: GnuRegex.c:359
@ endline
Definition: GnuRegex.c:299
@ duplicate
Definition: GnuRegex.c:293
@ set_number_at
Definition: GnuRegex.c:356
@ pop_failure_jump
Definition: GnuRegex.c:323
@ wordchar
Definition: GnuRegex.c:358
@ no_op
Definition: GnuRegex.c:253
@ jump_past_alt
Definition: GnuRegex.c:311
@ jump_n
Definition: GnuRegex.c:351
@ anychar
Definition: GnuRegex.c:259
@ dummy_failure_jump
Definition: GnuRegex.c:339
@ wordbound
Definition: GnuRegex.c:364
@ begline
Definition: GnuRegex.c:296
@ endbuf
Definition: GnuRegex.c:305
@ maybe_pop_jump
Definition: GnuRegex.c:332
@ jump
Definition: GnuRegex.c:308
@ on_failure_jump
Definition: GnuRegex.c:315
@ charset
Definition: GnuRegex.c:267
@ stop_memory
Definition: GnuRegex.c:289
@ notwordbound
Definition: GnuRegex.c:365
@ exactn
Definition: GnuRegex.c:256
@ begbuf
Definition: GnuRegex.c:302
@ charset_not
Definition: GnuRegex.c:271
@ wordend
Definition: GnuRegex.c:362
@ wordbeg
Definition: GnuRegex.c:361
@ on_failure_keep_string_jump
Definition: GnuRegex.c:319
@ succeed_n
Definition: GnuRegex.c:347
@ push_dummy_failure
Definition: GnuRegex.c:343
@ start_memory
Definition: GnuRegex.c:280
static int wordchar_p(const char *d, const char *end1, const char *string2)
Definition: GnuRegex.c:2761
#define EVER_MATCHED_SOMETHING(R)
Definition: GnuRegex.c:2700
#define assert(e)
Definition: GnuRegex.c:718
#define BYTEWIDTH
Definition: GnuRegex.c:233
void regfree(regex_t *preg)
Definition: GnuRegex.c:4287
static const char * re_error_msg[]
Definition: GnuRegex.c:733
#define CHAR_SET_SIZE
Definition: GnuRegex.c:77
#define DEBUG_PRINT3(x1, x2, x3)
Definition: GnuRegex.c:723
static boolean at_begline_loc_p(const char *pattern, const char *p, reg_syntax_t syntax)
Definition: GnuRegex.c:1922
#define RETALLOC(addr, n, t)
Definition: GnuRegex.c:230
#define ISSPACE(c)
Definition: GnuRegex.c:161
static void store_op2(re_opcode_t op, unsigned char *loc, int arg1, int arg2)
Definition: GnuRegex.c:1881
#define STORE_NUMBER_AND_INCR(destination, number)
Definition: GnuRegex.c:383
#define BUF_PUSH(c)
Definition: GnuRegex.c:791
static int re_match_2(struct re_pattern_buffer *buffer, const char *string1, int length1, const char *string2, int length2, int start, struct re_registers *regs, int stop)
Definition: GnuRegex.c:2821
#define MAX_REGNUM
Definition: GnuRegex.c:868
#define ISPRINT(c)
Definition: GnuRegex.c:154
#define AT_WORD_BOUNDARY(d)
Definition: GnuRegex.c:2770
#define ISALPHA(c)
Definition: GnuRegex.c:157
#define REG_UNSET(e)
Definition: GnuRegex.c:2725
#define SIGN_EXTEND_CHAR(c)
Definition: GnuRegex.c:174
#define RE_LIMITED_OPS
Definition: GnuRegex.h:118
#define REG_ICASE
Definition: GnuRegex.h:230
#define RE_SYNTAX_POSIX_EXTENDED
Definition: GnuRegex.h:199
reg_errcode_t
Definition: GnuRegex.h:255
@ REG_ERANGE
Definition: GnuRegex.h:270
@ REG_NOMATCH
Definition: GnuRegex.h:257
@ REG_ERPAREN
Definition: GnuRegex.h:277
@ REG_EBRACK
Definition: GnuRegex.h:266
@ REG_ECTYPE
Definition: GnuRegex.h:263
@ REG_ESPACE
Definition: GnuRegex.h:271
@ REG_EESCAPE
Definition: GnuRegex.h:264
@ REG_EPAREN
Definition: GnuRegex.h:267
@ REG_ESUBREG
Definition: GnuRegex.h:265
@ REG_BADBR
Definition: GnuRegex.h:269
@ REG_BADRPT
Definition: GnuRegex.h:272
@ REG_NOERROR
Definition: GnuRegex.h:256
@ REG_EBRACE
Definition: GnuRegex.h:268
#define REGS_UNALLOCATED
Definition: GnuRegex.h:327
#define RE_DOT_NOT_NULL
Definition: GnuRegex.h:105
#define RE_NREGS
Definition: GnuRegex.h:374
#define RE_INTERVALS
Definition: GnuRegex.h:114
unsigned reg_syntax_t
Definition: GnuRegex.h:56
#define RE_DOT_NEWLINE
Definition: GnuRegex.h:101
#define RE_BACKSLASH_ESCAPE_IN_LISTS
Definition: GnuRegex.h:60
#define RE_CONTEXT_INDEP_ANCHORS
Definition: GnuRegex.h:85
#define REGS_FIXED
Definition: GnuRegex.h:329
int regoff_t
Definition: GnuRegex.h:360
#define REG_EXTENDED
Definition: GnuRegex.h:226
#define RE_NEWLINE_ALT
Definition: GnuRegex.h:122
#define RE_NO_BK_VBAR
Definition: GnuRegex.h:139
#define REGS_REALLOCATE
Definition: GnuRegex.h:328
#define RE_NO_BK_BRACES
Definition: GnuRegex.h:127
#define RE_BK_PLUS_QM
Definition: GnuRegex.h:65
#define RE_CHAR_CLASSES
Definition: GnuRegex.h:71
#define REG_NOTEOL
Definition: GnuRegex.h:251
#define REG_NOTBOL
Definition: GnuRegex.h:248
#define RE_DUP_MAX
Definition: GnuRegex.h:220
#define RE_CONTEXT_INDEP_OPS
Definition: GnuRegex.h:93
#define RE_HAT_LISTS_NOT_NEWLINE
Definition: GnuRegex.h:109
#define REG_NEWLINE
Definition: GnuRegex.h:235
#define REG_NOSUB
Definition: GnuRegex.h:239
#define RE_NO_EMPTY_RANGES
Definition: GnuRegex.h:145
#define RE_CONTEXT_INVALID_OPS
Definition: GnuRegex.h:97
#define RE_NO_BK_REFS
Definition: GnuRegex.h:135
#define RE_SYNTAX_POSIX_BASIC
Definition: GnuRegex.h:190
#define RE_UNMATCHED_RIGHT_PAREN_ORD
Definition: GnuRegex.h:149
#define RE_NO_BK_PARENS
Definition: GnuRegex.h:131
int size
Definition: ModDevPoll.cc:75
@ s1
Definition: cf_gen.cc:55
A const & max(A const &lhs, A const &rhs)
A const & min(A const &lhs, A const &rhs)
pattern_offset_t inner_group_offset
Definition: GnuRegex.c:883
pattern_offset_t begalt_offset
Definition: GnuRegex.c:881
pattern_offset_t fixup_alt_jump
Definition: GnuRegex.c:882
pattern_offset_t laststart_offset
Definition: GnuRegex.c:884
unsigned avail
Definition: GnuRegex.c:891
compile_stack_elt_t * stack
Definition: GnuRegex.c:889
unsigned avail
Definition: GnuRegex.c:2043
fail_stack_elt_t * stack
Definition: GnuRegex.c:2041
unsigned size
Definition: GnuRegex.c:2042
unsigned can_be_null
Definition: GnuRegex.h:321
unsigned newline_anchor
Definition: GnuRegex.h:348
unsigned not_bol
Definition: GnuRegex.h:342
unsigned long allocated
Definition: GnuRegex.h:294
unsigned regs_allocated
Definition: GnuRegex.h:330
unsigned fastmap_accurate
Definition: GnuRegex.h:334
unsigned no_sub
Definition: GnuRegex.h:338
unsigned not_eol
Definition: GnuRegex.h:345
reg_syntax_t syntax
Definition: GnuRegex.h:300
unsigned long used
Definition: GnuRegex.h:297
char * translate
Definition: GnuRegex.h:311
unsigned char * buffer
Definition: GnuRegex.h:291
regoff_t * end
Definition: GnuRegex.h:367
regoff_t * start
Definition: GnuRegex.h:366
unsigned num_regs
Definition: GnuRegex.h:365
regoff_t rm_eo
Definition: GnuRegex.h:382
regoff_t rm_so
Definition: GnuRegex.h:381
int unsigned int
Definition: stub_fd.cc:19
static int debug
Definition: tcp-banger3.c:105
#define NULL
Definition: types.h:166

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors