5 /* Extended regular expression matching and search library,
7 * (Implements POSIX draft P10003.2/D11.2, except for
8 * internationalization features.)
10 * Copyright (C) 1993 Free Software Foundation, Inc.
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2, or (at your option)
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. */
26 /* AIX requires this to be the first thing in the file. */
27 #if defined (_AIX) && !defined(REGEX_MALLOC)
35 #define SQUID_NO_ALLOC_PROTECT 1
38 #if USE_GNUREGEX /* only if squid needs it. Usually not */
41 #define REGEX_MALLOC 1
44 /* We used to test for `BSTRING' here, but only GCC and Emacs define
45 * `BSTRING', as far as I know, and neither of them use this code. */
46 #if HAVE_STRING_H || STDC_HEADERS
53 /* Define the syntax stuff for \<, \>, etc. */
55 /* This must be nonzero for the wordchar and notwordchar pattern
56 * commands in re_match_2. */
63 extern char *re_syntax_table
;
65 #else /* not SYNTAX_TABLE */
67 /* How many characters in the character set. */
68 #define CHAR_SET_SIZE 256
70 static char re_syntax_table
[CHAR_SET_SIZE
];
73 init_syntax_once(void)
81 memset(re_syntax_table
, 0, sizeof re_syntax_table
);
83 for (c
= 'a'; c
<= 'z'; c
++)
84 re_syntax_table
[c
] = Sword
;
86 for (c
= 'A'; c
<= 'Z'; c
++)
87 re_syntax_table
[c
] = Sword
;
89 for (c
= '0'; c
<= '9'; c
++)
90 re_syntax_table
[c
] = Sword
;
92 re_syntax_table
['_'] = Sword
;
97 #endif /* not SYNTAX_TABLE */
99 #define SYNTAX(c) re_syntax_table[c]
101 /* Get the interface, including the syntax bits. */
102 #include "compat/GnuRegex.h"
104 /* Compile a fastmap for the compiled pattern in BUFFER; used to
105 * accelerate searches. Return 0 if successful and -2 if was an
107 static int re_compile_fastmap(struct re_pattern_buffer
* buffer
);
110 /* Search in the string STRING (with length LENGTH) for the pattern
111 * compiled into BUFFER. Start searching at position START, for RANGE
112 * characters. Return the starting position of the match, -1 for no
113 * match, or -2 for an internal error. Also return register
114 * information in REGS (if REGS and BUFFER->no_sub are nonzero). */
115 static int re_search(struct re_pattern_buffer
* buffer
, const char *string
,
116 int length
, int start
, int range
, struct re_registers
* regs
);
119 /* Like `re_search', but search in the concatenation of STRING1 and
120 * STRING2. Also, stop searching at index START + STOP. */
121 static int re_search_2(struct re_pattern_buffer
* buffer
, const char *string1
,
122 int length1
, const char *string2
, int length2
,
123 int start
, int range
, struct re_registers
* regs
, int stop
);
126 /* Like `re_search_2', but return how many characters in STRING the regexp
127 * in BUFFER matched, starting at position START. */
128 static int re_match_2(struct re_pattern_buffer
* buffer
, const char *string1
,
129 int length1
, const char *string2
, int length2
,
130 int start
, struct re_registers
* regs
, int stop
);
133 /* isalpha etc. are used for the character classes. */
141 #define ISBLANK(c) (isascii ((unsigned char)c) && isblank ((unsigned char)c))
143 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
146 #define ISGRAPH(c) (isascii ((unsigned char)c) && isgraph ((unsigned char)c))
148 #define ISGRAPH(c) (isascii ((unsigned char)c) && isprint ((unsigned char)c) && !isspace ((unsigned char)c))
151 #define ISPRINT(c) (isascii ((unsigned char)c) && isprint ((unsigned char)c))
152 #define ISDIGIT(c) (isascii ((unsigned char)c) && isdigit ((unsigned char)c))
153 #define ISALNUM(c) (isascii ((unsigned char)c) && isalnum ((unsigned char)c))
154 #define ISALPHA(c) (isascii ((unsigned char)c) && isalpha ((unsigned char)c))
155 #define ISCNTRL(c) (isascii ((unsigned char)c) && iscntrl ((unsigned char)c))
156 #define ISLOWER(c) (isascii ((unsigned char)c) && islower ((unsigned char)c))
157 #define ISPUNCT(c) (isascii ((unsigned char)c) && ispunct ((unsigned char)c))
158 #define ISSPACE(c) (isascii ((unsigned char)c) && isspace ((unsigned char)c))
159 #define ISUPPER(c) (isascii ((unsigned char)c) && isupper ((unsigned char)c))
160 #define ISXDIGIT(c) (isascii ((unsigned char)c) && isxdigit ((unsigned char)c))
166 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
167 * since ours (we hope) works properly with all combinations of
168 * machines, compilers, `char' and `unsigned char' argument types.
169 * (Per Bothner suggested the basic approach.) */
170 #undef SIGN_EXTEND_CHAR
172 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
173 #else /* not __STDC__ */
174 /* As in Harbison and Steele. */
175 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
178 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
179 * use `alloca' instead of `malloc'. This is because using malloc in
180 * re_search* or re_match* could cause memory leaks when C-g is used in
181 * Emacs; also, malloc is slower and causes storage fragmentation. On
182 * the other hand, malloc is more portable, and easier to debug.
184 * Because we sometimes use alloca, some routines have to be macros,
185 * not functions -- `alloca'-allocated space disappears at the end of the
186 * function it is called in. */
190 #define REGEX_ALLOCATE malloc
191 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
193 #else /* not REGEX_MALLOC */
195 /* Emacs already defines alloca, sometimes. */
198 /* Make alloca work the best possible way. */
200 #define alloca __builtin_alloca
201 #else /* not __GNUC__ */
204 #else /* not __GNUC__ or HAVE_ALLOCA_H */
205 #ifndef _AIX /* Already did AIX, up at the top. */
207 #endif /* not _AIX */
208 #endif /* not HAVE_ALLOCA_H */
209 #endif /* not __GNUC__ */
211 #endif /* not alloca */
213 #define REGEX_ALLOCATE alloca
215 /* Assumes a `char *destination' variable. */
216 #define REGEX_REALLOCATE(source, osize, nsize) \
217 (destination = (char *) alloca (nsize), \
218 xmemcpy (destination, source, osize), \
221 #endif /* not REGEX_MALLOC */
224 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
225 * `string1' or just past its end. This works if PTR is NULL, which is
227 #define FIRST_STRING_P(ptr) \
228 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
230 /* (Re)Allocate N items of type T using malloc, or fail. */
231 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
232 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
233 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
235 #define BYTEWIDTH 8 /* In bits. */
237 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
239 #define MAX(a, b) ((a) > (b) ? (a) : (b))
240 #define MIN(a, b) ((a) < (b) ? (a) : (b))
242 #if !defined(__MINGW32__) /* MinGW defines boolean */
243 typedef char boolean
;
248 /* These are the command codes that appear in compiled regular
249 * expressions. Some opcodes are followed by argument bytes. A
250 * command code can specify any interpretation whatsoever for its
251 * arguments. Zero bytes may appear in the compiled regular expression.
253 * The value of `exactn' is needed in search.c (search_buffer) in Emacs.
254 * So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
255 * `exactn' we use here must also be 1. */
260 /* Followed by one byte giving n, then by n literal bytes. */
263 /* Matches any (more or less) character. */
266 /* Matches any one char belonging to specified set. First
267 * following byte is number of bitmap bytes. Then come bytes
268 * for a bitmap saying which chars are in. Bits in each byte
269 * are ordered low-bit-first. A character is in the set if its
270 * bit is 1. A character too large to have a bit in the map is
271 * automatically not in the set. */
274 /* Same parameters as charset, but match any character that is
275 * not one of those specified. */
278 /* Start remembering the text that is matched, for storing in a
279 * register. Followed by one byte with the register number, in
280 * the range 0 to one less than the pattern buffer's re_nsub
281 * field. Then followed by one byte with the number of groups
282 * inner to this one. (This last has to be part of the
283 * start_memory only because we need it in the on_failure_jump
287 /* Stop remembering the text that is matched and store it in a
288 * memory register. Followed by one byte with the register
289 * number, in the range 0 to one less than `re_nsub' in the
290 * pattern buffer, and one byte with the number of inner groups,
291 * just like `start_memory'. (We need the number of inner
292 * groups here because we don't have any easy way of finding the
293 * corresponding start_memory when we're at a stop_memory.) */
296 /* Match a duplicate of something remembered. Followed by one
297 * byte containing the register number. */
300 /* Fail unless at beginning of line. */
303 /* Fail unless at end of line. */
306 /* Succeeds if or at beginning of string to be matched. */
309 /* Analogously, for end of buffer/string. */
312 /* Followed by two byte relative address to which to jump. */
315 /* Same as jump, but marks the end of an alternative. */
318 /* Followed by two-byte relative address of place to resume at
319 * in case of failure. */
322 /* Like on_failure_jump, but pushes a placeholder instead of the
323 * current string position when executed. */
324 on_failure_keep_string_jump
,
326 /* Throw away latest failure point and then jump to following
327 * two-byte relative address. */
330 /* Change to pop_failure_jump if know won't have to backtrack to
331 * match; otherwise change to jump. This is used to jump
332 * back to the beginning of a repeat. If what follows this jump
333 * clearly won't match what the repeat does, such that we can be
334 * sure that there is no use backtracking out of repetitions
335 * already matched, then we change it to a pop_failure_jump.
336 * Followed by two-byte address. */
339 /* Jump to following two-byte address, and push a dummy failure
340 * point. This failure point will be thrown away if an attempt
341 * is made to use it for a failure. A `+' construct makes this
342 * before the first repeat. Also used as an intermediary kind
343 * of jump when compiling an alternative. */
346 /* Push a dummy failure point and continue. Used at the end of
350 /* Followed by two-byte relative address and two-byte number n.
351 * After matching N times, jump to the address upon failure. */
354 /* Followed by two-byte relative address, and two-byte number n.
355 * Jump to the address N times, then fail. */
358 /* Set the following two-byte relative address to the
359 * subsequent two-byte number. The address *includes* the two
360 * bytes of number. */
363 wordchar
, /* Matches any word-constituent character. */
364 notwordchar
, /* Matches any char that is not a word-constituent. */
366 wordbeg
, /* Succeeds if at word beginning. */
367 wordend
, /* Succeeds if at word end. */
369 wordbound
, /* Succeeds if at a word boundary. */
370 notwordbound
/* Succeeds if not at a word boundary. */
374 /* Common operations on the compiled pattern. */
376 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
378 #define STORE_NUMBER(destination, number) \
380 (destination)[0] = (number) & 0377; \
381 (destination)[1] = (number) >> 8; \
384 /* Same as STORE_NUMBER, except increment DESTINATION to
385 * the byte after where the number is stored. Therefore, DESTINATION
386 * must be an lvalue. */
388 #define STORE_NUMBER_AND_INCR(destination, number) \
390 STORE_NUMBER (destination, number); \
391 (destination) += 2; \
394 /* Put into DESTINATION a number stored in two contiguous bytes starting
397 #define EXTRACT_NUMBER(destination, source) \
399 (destination) = *(source) & 0377; \
400 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \
405 extract_number(dest
, source
)
407 unsigned char *source
;
409 int temp
= SIGN_EXTEND_CHAR(*(source
+ 1));
410 *dest
= *source
& 0377;
414 #ifndef EXTRACT_MACROS /* To debug the macros. */
415 #undef EXTRACT_NUMBER
416 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
417 #endif /* not EXTRACT_MACROS */
421 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
422 * SOURCE must be an lvalue. */
424 #define EXTRACT_NUMBER_AND_INCR(destination, source) \
426 EXTRACT_NUMBER (destination, source); \
432 extract_number_and_incr(destination
, source
)
434 unsigned char **source
;
436 extract_number(destination
, *source
);
440 #ifndef EXTRACT_MACROS
441 #undef EXTRACT_NUMBER_AND_INCR
442 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
443 extract_number_and_incr (&dest, &src)
444 #endif /* not EXTRACT_MACROS */
448 /* If DEBUG is defined, Regex prints many voluminous messages about what
449 * it is doing (if the variable `debug' is nonzero). If linked with the
450 * main program in `iregex.c', you can enter patterns and strings
451 * interactively. And if linked with the main program in `main.c' and
452 * the other test files, you can run the already-written tests. */
456 /* We use standard I/O for debugging. */
459 /* It is useful to test things that ``must'' be true when debugging. */
462 static int debug
= 0;
464 #define DEBUG_STATEMENT(e) e
465 #define DEBUG_PRINT1(x) if (debug) printf (x)
466 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
467 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
468 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
469 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
470 if (debug) print_partial_compiled_pattern (s, e)
471 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
472 if (debug) print_double_string (w, s1, sz1, s2, sz2)
475 extern void printchar();
477 /* Print the fastmap in human-readable form. */
480 print_fastmap(fastmap
)
483 unsigned was_a_range
= 0;
486 while (i
< (1 << BYTEWIDTH
)) {
490 while (i
< (1 << BYTEWIDTH
) && fastmap
[i
]) {
504 /* Print a compiled pattern string in human-readable form, starting at
505 * the START pointer into it and ending just before the pointer END. */
508 print_partial_compiled_pattern(start
, end
)
509 unsigned char *start
;
513 unsigned char *p
= start
;
514 unsigned char *pend
= end
;
520 /* Loop over pattern commands. */
522 switch ((re_opcode_t
) * p
++) {
529 printf("/exactn/%d", mcnt
);
538 printf("/start_memory/%d/%d", mcnt
, *p
++);
543 printf("/stop_memory/%d/%d", mcnt
, *p
++);
547 printf("/duplicate/%d", *p
++);
559 (re_opcode_t
) * (p
- 1) == charset_not
? "_not" : "");
561 assert(p
+ *p
< pend
);
563 for (c
= 0; c
< *p
; c
++) {
565 unsigned char map_byte
= p
[1 + c
];
569 for (bit
= 0; bit
< BYTEWIDTH
; bit
++)
570 if (map_byte
& (1 << bit
))
571 printchar(c
* BYTEWIDTH
+ bit
);
585 case on_failure_jump
:
586 extract_number_and_incr(&mcnt
, &p
);
587 printf("/on_failure_jump/0/%d", mcnt
);
590 case on_failure_keep_string_jump
:
591 extract_number_and_incr(&mcnt
, &p
);
592 printf("/on_failure_keep_string_jump/0/%d", mcnt
);
595 case dummy_failure_jump
:
596 extract_number_and_incr(&mcnt
, &p
);
597 printf("/dummy_failure_jump/0/%d", mcnt
);
600 case push_dummy_failure
:
601 printf("/push_dummy_failure");
605 extract_number_and_incr(&mcnt
, &p
);
606 printf("/maybe_pop_jump/0/%d", mcnt
);
609 case pop_failure_jump
:
610 extract_number_and_incr(&mcnt
, &p
);
611 printf("/pop_failure_jump/0/%d", mcnt
);
615 extract_number_and_incr(&mcnt
, &p
);
616 printf("/jump_past_alt/0/%d", mcnt
);
620 extract_number_and_incr(&mcnt
, &p
);
621 printf("/jump/0/%d", mcnt
);
625 extract_number_and_incr(&mcnt
, &p
);
626 extract_number_and_incr(&mcnt2
, &p
);
627 printf("/succeed_n/0/%d/0/%d", mcnt
, mcnt2
);
631 extract_number_and_incr(&mcnt
, &p
);
632 extract_number_and_incr(&mcnt2
, &p
);
633 printf("/jump_n/0/%d/0/%d", mcnt
, mcnt2
);
637 extract_number_and_incr(&mcnt
, &p
);
638 extract_number_and_incr(&mcnt2
, &p
);
639 printf("/set_number_at/0/%d/0/%d", mcnt
, mcnt2
);
643 printf("/wordbound");
647 printf("/notwordbound");
662 printf("/notwordchar");
674 printf("?%d", *(p
- 1));
682 print_compiled_pattern(bufp
)
683 struct re_pattern_buffer
*bufp
;
685 unsigned char *buffer
= bufp
->buffer
;
687 print_partial_compiled_pattern(buffer
, buffer
+ bufp
->used
);
688 printf("%d bytes used/%d bytes allocated.\n", bufp
->used
, bufp
->allocated
);
690 if (bufp
->fastmap_accurate
&& bufp
->fastmap
) {
692 print_fastmap(bufp
->fastmap
);
694 printf("re_nsub: %d\t", bufp
->re_nsub
);
695 printf("regs_alloc: %d\t", bufp
->regs_allocated
);
696 printf("can_be_null: %d\t", bufp
->can_be_null
);
697 printf("newline_anchor: %d\n", bufp
->newline_anchor
);
698 printf("no_sub: %d\t", bufp
->no_sub
);
699 printf("not_bol: %d\t", bufp
->not_bol
);
700 printf("not_eol: %d\t", bufp
->not_eol
);
701 printf("syntax: %d\n", bufp
->syntax
);
702 /* Perhaps we should print the translate table? */
707 print_double_string(where
, string1
, size1
, string2
, size2
)
719 if (FIRST_STRING_P(where
)) {
720 for (this_char
= where
- string1
; this_char
< size1
; this_char
++)
721 printchar(string1
[this_char
]);
725 for (this_char
= where
- string2
; this_char
< size2
; this_char
++)
726 printchar(string2
[this_char
]);
730 #else /* not DEBUG */
735 #define DEBUG_STATEMENT(e)
736 #define DEBUG_PRINT1(x)
737 #define DEBUG_PRINT2(x1, x2)
738 #define DEBUG_PRINT3(x1, x2, x3)
739 #define DEBUG_PRINT4(x1, x2, x3, x4)
740 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
741 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
743 #endif /* not DEBUG */
745 /* This table gives an error message for each of the error codes listed
746 * in regex.h. Obviously the order here has to be same as there. */
748 static const char *re_error_msg
[] = {NULL
, /* REG_NOERROR */
749 "No match", /* REG_NOMATCH */
750 "Invalid regular expression", /* REG_BADPAT */
751 "Invalid collation character", /* REG_ECOLLATE */
752 "Invalid character class name", /* REG_ECTYPE */
753 "Trailing backslash", /* REG_EESCAPE */
754 "Invalid back reference", /* REG_ESUBREG */
755 "Unmatched [ or [^", /* REG_EBRACK */
756 "Unmatched ( or \\(", /* REG_EPAREN */
757 "Unmatched \\{", /* REG_EBRACE */
758 "Invalid content of \\{\\}", /* REG_BADBR */
759 "Invalid range end", /* REG_ERANGE */
760 "Memory exhausted", /* REG_ESPACE */
761 "Invalid preceding regular expression", /* REG_BADRPT */
762 "Premature end of regular expression", /* REG_EEND */
763 "Regular expression too big", /* REG_ESIZE */
764 "Unmatched ) or \\)", /* REG_ERPAREN */
767 /* Subroutine declarations and macros for regex_compile. */
769 /* Fetch the next character in the uncompiled pattern---translating it
770 * if necessary. Also cast from a signed character in the constant
771 * string passed to us by the user to an unsigned char that we can use
772 * as an array index (in, e.g., `translate'). */
773 #define PATFETCH(c) \
774 do {if (p == pend) return REG_EEND; \
775 c = (unsigned char) *p++; \
776 if (translate) c = translate[c]; \
779 /* Fetch the next character in the uncompiled pattern, with no
781 #define PATFETCH_RAW(c) \
782 do {if (p == pend) return REG_EEND; \
783 c = (unsigned char) *p++; \
786 /* Go backwards one character in the pattern. */
787 #define PATUNFETCH p--
790 /* If `translate' is non-null, return translate[D], else just D. We
791 * cast the subscript to translate because some data is declared as
792 * `char *', to avoid warnings when a string constant is passed. But
793 * when we use a character as a subscript we must make it unsigned. */
794 #define TRANSLATE(d) (translate ? translate[(unsigned char) (d)] : (d))
797 /* Macros for outputting the compiled pattern into `buffer'. */
799 /* If the buffer isn't allocated when it comes in, use this. */
800 #define INIT_BUF_SIZE 32
802 /* Make sure we have at least N more bytes of space in buffer. */
803 #define GET_BUFFER_SPACE(n) \
804 while (b - bufp->buffer + (n) > bufp->allocated) \
807 /* Make sure we have one more byte of buffer space and then add C to it. */
808 #define BUF_PUSH(c) \
810 GET_BUFFER_SPACE (1); \
811 *b++ = (unsigned char) (c); \
815 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
816 #define BUF_PUSH_2(c1, c2) \
818 GET_BUFFER_SPACE (2); \
819 *b++ = (unsigned char) (c1); \
820 *b++ = (unsigned char) (c2); \
824 /* As with BUF_PUSH_2, except for three bytes. */
825 #define BUF_PUSH_3(c1, c2, c3) \
827 GET_BUFFER_SPACE (3); \
828 *b++ = (unsigned char) (c1); \
829 *b++ = (unsigned char) (c2); \
830 *b++ = (unsigned char) (c3); \
834 /* Store a jump with opcode OP at LOC to location TO. We store a
835 * relative address offset by the three bytes the jump itself occupies. */
836 #define STORE_JUMP(op, loc, to) \
837 store_op1 (op, loc, (to) - (loc) - 3)
839 /* Likewise, for a two-argument jump. */
840 #define STORE_JUMP2(op, loc, to, arg) \
841 store_op2 (op, loc, (to) - (loc) - 3, arg)
843 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
844 #define INSERT_JUMP(op, loc, to) \
845 insert_op1 (op, loc, (to) - (loc) - 3, b)
847 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
848 #define INSERT_JUMP2(op, loc, to, arg) \
849 insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
852 /* This is not an arbitrary limit: the arguments which represent offsets
853 * into the pattern are two bytes long. So if 2^16 bytes turns out to
854 * be too small, many things would have to change. */
855 #define MAX_BUF_SIZE (1L << 16)
858 /* Extend the buffer by twice its current size via realloc and
859 * reset the pointers that pointed into the old block to point to the
860 * correct places in the new one. If extending the buffer results in it
861 * being larger than MAX_BUF_SIZE, then flag memory exhausted. */
862 #define EXTEND_BUFFER() \
864 unsigned char *old_buffer = bufp->buffer; \
865 if (bufp->allocated == MAX_BUF_SIZE) \
867 bufp->allocated <<= 1; \
868 if (bufp->allocated > MAX_BUF_SIZE) \
869 bufp->allocated = MAX_BUF_SIZE; \
870 bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
871 if (bufp->buffer == NULL) \
873 /* If the buffer moved, move all the pointers into it. */ \
874 if (old_buffer != bufp->buffer) \
876 b = (b - old_buffer) + bufp->buffer; \
877 begalt = (begalt - old_buffer) + bufp->buffer; \
878 if (fixup_alt_jump) \
879 fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
881 laststart = (laststart - old_buffer) + bufp->buffer; \
883 pending_exact = (pending_exact - old_buffer) + bufp->buffer; \
888 /* Since we have one byte reserved for the register number argument to
889 * {start,stop}_memory, the maximum number of groups we can report
890 * things about is what fits in that byte. */
891 #define MAX_REGNUM 255
893 /* But patterns can have more than `MAX_REGNUM' registers. We just
894 * ignore the excess. */
895 typedef unsigned regnum_t
;
898 /* Macros for the compile stack. */
900 /* Since offsets can go either forwards or backwards, this type needs to
901 * be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
902 typedef int pattern_offset_t
;
905 pattern_offset_t begalt_offset
;
906 pattern_offset_t fixup_alt_jump
;
907 pattern_offset_t inner_group_offset
;
908 pattern_offset_t laststart_offset
;
910 } compile_stack_elt_t
;
914 compile_stack_elt_t
*stack
;
916 unsigned avail
; /* Offset of next open position. */
917 } compile_stack_type
;
919 static void store_op1(re_opcode_t op
, unsigned char *loc
, int arg
);
920 static void store_op2( re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
);
921 static void insert_op1(re_opcode_t op
, unsigned char *loc
, int arg
, unsigned char *end
);
922 static void insert_op2(re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
, unsigned char *end
);
923 static boolean
at_begline_loc_p(const char * pattern
, const char *p
, reg_syntax_t syntax
);
924 static boolean
at_endline_loc_p(const char *p
, const char *pend
, int syntax
);
925 static boolean
group_in_compile_stack(compile_stack_type compile_stack
, regnum_t regnum
);
926 static reg_errcode_t
compile_range(const char **p_ptr
, const char *pend
, char *translate
, reg_syntax_t syntax
, unsigned char *b
);
928 #define INIT_COMPILE_STACK_SIZE 32
930 #define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
931 #define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
933 /* The next available element. */
934 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
937 /* Set the bit for character C in a list. */
938 #define SET_LIST_BIT(c) \
939 (b[((unsigned char) (c)) / BYTEWIDTH] \
940 |= 1 << (((unsigned char) c) % BYTEWIDTH))
943 /* Get the next unsigned number in the uncompiled pattern. */
944 #define GET_UNSIGNED_NUMBER(num) \
948 while (ISDIGIT (c)) \
952 num = num * 10 + c - '0'; \
960 #define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
962 #define IS_CHAR_CLASS(string) \
963 (STREQ (string, "alpha") || STREQ (string, "upper") \
964 || STREQ (string, "lower") || STREQ (string, "digit") \
965 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
966 || STREQ (string, "space") || STREQ (string, "print") \
967 || STREQ (string, "punct") || STREQ (string, "graph") \
968 || STREQ (string, "cntrl") || STREQ (string, "blank"))
970 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
971 * Returns one of error codes defined in `regex.h', or zero for success.
973 * Assumes the `allocated' (and perhaps `buffer') and `translate'
974 * fields are set in BUFP on entry.
976 * If it succeeds, results are put in BUFP (if it returns an error, the
977 * contents of BUFP are undefined):
978 * `buffer' is the compiled pattern;
979 * `syntax' is set to SYNTAX;
980 * `used' is set to the length of the compiled pattern;
981 * `fastmap_accurate' is zero;
982 * `re_nsub' is the number of subexpressions in PATTERN;
983 * `not_bol' and `not_eol' are zero;
985 * The `fastmap' and `newline_anchor' fields are neither
986 * examined nor set. */
989 regex_compile(const char *pattern
, int size
, reg_syntax_t syntax
, struct re_pattern_buffer
*bufp
)
991 /* We fetch characters from PATTERN here. Even though PATTERN is
992 * `char *' (i.e., signed), we declare these variables as unsigned, so
993 * they can be reliably used as array indices. */
994 register unsigned char c
, c1
;
996 /* A random tempory spot in PATTERN. */
999 /* Points to the end of the buffer, where we should append. */
1000 register unsigned char *b
;
1002 /* Keeps track of unclosed groups. */
1003 compile_stack_type compile_stack
;
1005 /* Points to the current (ending) position in the pattern. */
1006 const char *p
= pattern
;
1007 const char *pend
= pattern
+ size
;
1009 /* How to translate the characters in the pattern. */
1010 char *translate
= bufp
->translate
;
1012 /* Address of the count-byte of the most recently inserted `exactn'
1013 * command. This makes it possible to tell if a new exact-match
1014 * character can be added to that command or if the character requires
1015 * a new `exactn' command. */
1016 unsigned char *pending_exact
= 0;
1018 /* Address of start of the most recently finished expression.
1019 * This tells, e.g., postfix * where to find the start of its
1020 * operand. Reset at the beginning of groups and alternatives. */
1021 unsigned char *laststart
= 0;
1023 /* Address of beginning of regexp, or inside of last group. */
1024 unsigned char *begalt
;
1026 /* Place in the uncompiled pattern (i.e., the {) to
1027 * which to go back if the interval is invalid. */
1028 const char *beg_interval
;
1030 /* Address of the place where a forward jump should go to the end of
1031 * the containing expression. Each alternative of an `or' -- except the
1032 * last -- ends with a forward jump of this sort. */
1033 unsigned char *fixup_alt_jump
= 0;
1035 /* Counts open-groups as they are encountered. Remembered for the
1036 * matching close-group on the compile stack, so the same register
1037 * number is put in the stop_memory as the start_memory. */
1038 regnum_t regnum
= 0;
1041 DEBUG_PRINT1("\nCompiling pattern: ");
1043 unsigned debug_count
;
1045 for (debug_count
= 0; debug_count
< size
; debug_count
++)
1046 printchar(pattern
[debug_count
]);
1051 /* Initialize the compile stack. */
1052 compile_stack
.stack
= TALLOC(INIT_COMPILE_STACK_SIZE
, compile_stack_elt_t
);
1053 if (compile_stack
.stack
== NULL
)
1056 compile_stack
.size
= INIT_COMPILE_STACK_SIZE
;
1057 compile_stack
.avail
= 0;
1059 /* Initialize the pattern buffer. */
1060 bufp
->syntax
= syntax
;
1061 bufp
->fastmap_accurate
= 0;
1062 bufp
->not_bol
= bufp
->not_eol
= 0;
1064 /* Set `used' to zero, so that if we return an error, the pattern
1065 * printer (for debugging) will think there's no pattern. We reset it
1069 /* Always count groups, whether or not bufp->no_sub is set. */
1072 #if !defined (SYNTAX_TABLE)
1073 /* Initialize the syntax table. */
1077 if (bufp
->allocated
== 0) {
1078 if (bufp
->buffer
) { /* If zero allocated, but buffer is non-null, try to realloc
1079 * enough space. This loses if buffer's address is bogus, but
1080 * that is the user's responsibility. */
1081 RETALLOC(bufp
->buffer
, INIT_BUF_SIZE
, unsigned char);
1082 } else { /* Caller did not allocate a buffer. Do it for them. */
1083 bufp
->buffer
= TALLOC(INIT_BUF_SIZE
, unsigned char);
1088 bufp
->allocated
= INIT_BUF_SIZE
;
1090 begalt
= b
= bufp
->buffer
;
1092 /* Loop through the uncompiled pattern until we're at the end. */
1098 if ( /* If at start of pattern, it's an operator. */
1100 /* If context independent, it's an operator. */
1101 || syntax
& RE_CONTEXT_INDEP_ANCHORS
1102 /* Otherwise, depends on what's come before. */
1103 || at_begline_loc_p(pattern
, p
, syntax
))
1112 if ( /* If at end of pattern, it's an operator. */
1114 /* If context independent, it's an operator. */
1115 || syntax
& RE_CONTEXT_INDEP_ANCHORS
1116 /* Otherwise, depends on what's next. */
1117 || at_endline_loc_p(p
, pend
, syntax
))
1127 if ((syntax
& RE_BK_PLUS_QM
)
1128 || (syntax
& RE_LIMITED_OPS
))
1132 /* If there is no previous pattern... */
1134 if (syntax
& RE_CONTEXT_INVALID_OPS
)
1136 else if (!(syntax
& RE_CONTEXT_INDEP_OPS
))
1139 /* Are we optimizing this jump? */
1140 boolean keep_string_p
= false;
1142 /* 1 means zero (many) matches is allowed. */
1143 char zero_times_ok
= 0, many_times_ok
= 0;
1145 /* If there is a sequence of repetition chars, collapse it
1146 * down to just one (the right one). We can't combine
1147 * interval operators with these because of, e.g., `a{2}*',
1148 * which should only match an even number of `a's. */
1151 zero_times_ok
|= c
!= '+';
1152 many_times_ok
|= c
!= '?';
1160 || (!(syntax
& RE_BK_PLUS_QM
) && (c
== '+' || c
== '?')));
1162 else if (syntax
& RE_BK_PLUS_QM
&& c
== '\\') {
1167 if (!(c1
== '+' || c1
== '?')) {
1178 /* If we get here, we found another repeat character. */
1181 /* Star, etc. applied to an empty pattern is equivalent
1182 * to an empty pattern. */
1186 /* Now we know whether or not zero matches is allowed
1187 * and also whether or not two or more matches is allowed. */
1188 if (many_times_ok
) { /* More than one repetition is allowed, so put in at the
1189 * end a backward relative jump from `b' to before the next
1190 * jump we're going to put in below (which jumps from
1191 * laststart to after this jump).
1193 * But if we are at the `*' in the exact sequence `.*\n',
1194 * insert an unconditional jump backwards to the .,
1195 * instead of the beginning of the loop. This way we only
1196 * push a failure point once, instead of every time
1197 * through the loop. */
1198 assert(p
- 1 > pattern
);
1200 /* Allocate the space for the jump. */
1201 GET_BUFFER_SPACE(3);
1203 /* We know we are not at the first character of the pattern,
1204 * because laststart was nonzero. And we've already
1205 * incremented `p', by the way, to be the character after
1206 * the `*'. Do we have to do something analogous here
1207 * for null bytes, because of RE_DOT_NOT_NULL? */
1208 if (TRANSLATE(*(p
- 2)) == TRANSLATE('.')
1210 && p
< pend
&& TRANSLATE(*p
) == TRANSLATE('\n')
1211 && !(syntax
& RE_DOT_NEWLINE
)) { /* We have .*\n. */
1212 STORE_JUMP(jump
, b
, laststart
);
1213 keep_string_p
= true;
1215 /* Anything else. */
1216 STORE_JUMP(maybe_pop_jump
, b
, laststart
- 3);
1218 /* We've added more stuff to the buffer. */
1221 /* On failure, jump from laststart to b + 3, which will be the
1222 * end of the buffer after this jump is inserted. */
1223 GET_BUFFER_SPACE(3);
1224 INSERT_JUMP(keep_string_p
? on_failure_keep_string_jump
1230 if (!zero_times_ok
) {
1231 /* At least one repetition is required, so insert a
1232 * `dummy_failure_jump' before the initial
1233 * `on_failure_jump' instruction of the loop. This
1234 * effects a skip over that instruction the first time
1235 * we hit that loop. */
1236 GET_BUFFER_SPACE(3);
1237 INSERT_JUMP(dummy_failure_jump
, laststart
, laststart
+ 6);
1251 boolean had_char_class
= false;
1256 /* Ensure that we have enough space to push a charset: the
1257 * opcode, the length count, and the bitset; 34 bytes in all. */
1258 GET_BUFFER_SPACE(34);
1262 /* We test `*p == '^' twice, instead of using an if
1263 * statement, so we only need one BUF_PUSH. */
1264 BUF_PUSH(*p
== '^' ? charset_not
: charset
);
1268 /* Remember the first position in the bracket expression. */
1271 /* Push the number of bytes in the bitmap. */
1272 BUF_PUSH((1 << BYTEWIDTH
) / BYTEWIDTH
);
1274 /* Clear the whole map. */
1275 memset(b
, 0, (1 << BYTEWIDTH
) / BYTEWIDTH
);
1277 /* charset_not matches newline according to a syntax bit. */
1278 if ((re_opcode_t
) b
[-2] == charset_not
1279 && (syntax
& RE_HAT_LISTS_NOT_NEWLINE
))
1282 /* Read in characters and ranges, setting map bits. */
1289 /* \ might escape characters inside [...] and [^...]. */
1290 if ((syntax
& RE_BACKSLASH_ESCAPE_IN_LISTS
) && c
== '\\') {
1298 /* Could be the end of the bracket expression. If it's
1299 * not (i.e., when the bracket expression is `[]' so
1300 * far), the ']' character bit gets set way below. */
1301 if (c
== ']' && p
!= p1
+ 1)
1304 /* Look ahead to see if it's a range when the last thing
1305 * was a character class. */
1306 if (had_char_class
&& c
== '-' && *p
!= ']')
1309 /* Look ahead to see if it's a range when the last thing
1310 * was a character: if this is a hyphen not at the
1311 * beginning or the end of a list, then it's the range
1314 && !(p
- 2 >= pattern
&& p
[-2] == '[')
1315 && !(p
- 3 >= pattern
&& p
[-3] == '[' && p
[-2] == '^')
1318 = compile_range(&p
, pend
, translate
, syntax
, b
);
1319 if (ret
!= REG_NOERROR
)
1321 } else if (p
[0] == '-' && p
[1] != ']') { /* This handles ranges made up of characters only. */
1324 /* Move past the `-'. */
1327 ret
= compile_range(&p
, pend
, translate
, syntax
, b
);
1328 if (ret
!= REG_NOERROR
)
1331 /* See if we're at the beginning of a possible character
1334 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && *p
== ':') { /* Leave room for the null. */
1335 char str
[CHAR_CLASS_MAX_LENGTH
+ 1];
1340 /* If pattern is `[[:'. */
1346 if (c
== ':' || c
== ']' || p
== pend
1347 || c1
== CHAR_CLASS_MAX_LENGTH
)
1353 /* If isn't a word bracketed by `[:' and:`]':
1354 * undo the ending character, the letters, and leave
1355 * the leading `:' and `[' (but set bits for them). */
1356 if (c
== ':' && *p
== ']') {
1358 boolean is_alnum
= STREQ(str
, "alnum");
1359 boolean is_alpha
= STREQ(str
, "alpha");
1360 boolean is_blank
= STREQ(str
, "blank");
1361 boolean is_cntrl
= STREQ(str
, "cntrl");
1362 boolean is_digit
= STREQ(str
, "digit");
1363 boolean is_graph
= STREQ(str
, "graph");
1364 boolean is_lower
= STREQ(str
, "lower");
1365 boolean is_print
= STREQ(str
, "print");
1366 boolean is_punct
= STREQ(str
, "punct");
1367 boolean is_space
= STREQ(str
, "space");
1368 boolean is_upper
= STREQ(str
, "upper");
1369 boolean is_xdigit
= STREQ(str
, "xdigit");
1371 if (!IS_CHAR_CLASS(str
))
1374 /* Throw away the ] at the end of the character
1381 for (ch
= 0; ch
< 1 << BYTEWIDTH
; ch
++) {
1382 if ((is_alnum
&& ISALNUM(ch
))
1383 || (is_alpha
&& ISALPHA(ch
))
1384 || (is_blank
&& ISBLANK(ch
))
1385 || (is_cntrl
&& ISCNTRL(ch
))
1386 || (is_digit
&& ISDIGIT(ch
))
1387 || (is_graph
&& ISGRAPH(ch
))
1388 || (is_lower
&& ISLOWER(ch
))
1389 || (is_print
&& ISPRINT(ch
))
1390 || (is_punct
&& ISPUNCT(ch
))
1391 || (is_space
&& ISSPACE(ch
))
1392 || (is_upper
&& ISUPPER(ch
))
1393 || (is_xdigit
&& ISXDIGIT(ch
)))
1396 had_char_class
= true;
1403 had_char_class
= false;
1406 had_char_class
= false;
1411 /* Discard any (non)matching list bytes that are all 0 at the
1412 * end of the map. Decrease the map-length byte too. */
1413 while ((int) b
[-1] > 0 && b
[b
[-1] - 1] == 0)
1421 if (syntax
& RE_NO_BK_PARENS
)
1428 if (syntax
& RE_NO_BK_PARENS
)
1435 if (syntax
& RE_NEWLINE_ALT
)
1442 if (syntax
& RE_NO_BK_VBAR
)
1449 if (syntax
& RE_INTERVALS
&& syntax
& RE_NO_BK_BRACES
)
1450 goto handle_interval
;
1459 /* Do not translate the character after the \, so that we can
1460 * distinguish, e.g., \B from \b, even if we normally would
1461 * translate, e.g., B to b. */
1466 if (syntax
& RE_NO_BK_PARENS
)
1467 goto normal_backslash
;
1473 if (COMPILE_STACK_FULL
) {
1474 RETALLOC(compile_stack
.stack
, compile_stack
.size
<< 1,
1475 compile_stack_elt_t
);
1476 if (compile_stack
.stack
== NULL
)
1479 compile_stack
.size
<<= 1;
1481 /* These are the values to restore when we hit end of this
1482 * group. They are all relative offsets, so that if the
1483 * whole pattern moves because of realloc, they will still
1485 COMPILE_STACK_TOP
.begalt_offset
= begalt
- bufp
->buffer
;
1486 COMPILE_STACK_TOP
.fixup_alt_jump
1487 = fixup_alt_jump
? fixup_alt_jump
- bufp
->buffer
+ 1 : 0;
1488 COMPILE_STACK_TOP
.laststart_offset
= b
- bufp
->buffer
;
1489 COMPILE_STACK_TOP
.regnum
= regnum
;
1491 /* We will eventually replace the 0 with the number of
1492 * groups inner to this one. But do not push a
1493 * start_memory for groups beyond the last one we can
1494 * represent in the compiled pattern. */
1495 if (regnum
<= MAX_REGNUM
) {
1496 COMPILE_STACK_TOP
.inner_group_offset
= b
- bufp
->buffer
+ 2;
1497 BUF_PUSH_3(start_memory
, regnum
, 0);
1499 compile_stack
.avail
++;
1504 /* If we've reached MAX_REGNUM groups, then this open
1505 * won't actually generate any code, so we'll have to
1506 * clear pending_exact explicitly. */
1512 if (syntax
& RE_NO_BK_PARENS
)
1513 goto normal_backslash
;
1515 if (COMPILE_STACK_EMPTY
) {
1516 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
1517 goto normal_backslash
;
1522 if (fixup_alt_jump
) { /* Push a dummy failure point at the end of the
1523 * alternative for a possible future
1524 * `pop_failure_jump' to pop. See comments at
1525 * `push_dummy_failure' in `re_match_2'. */
1526 BUF_PUSH(push_dummy_failure
);
1528 /* We allocated space for this jump when we assigned
1529 * to `fixup_alt_jump', in the `handle_alt' case below. */
1530 STORE_JUMP(jump_past_alt
, fixup_alt_jump
, b
- 1);
1532 /* See similar code for backslashed left paren above. */
1533 if (COMPILE_STACK_EMPTY
) {
1534 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
1539 /* Since we just checked for an empty stack above, this
1540 * ``can't happen''. */
1541 assert(compile_stack
.avail
!= 0);
1543 /* We don't just want to restore into `regnum', because
1544 * later groups should continue to be numbered higher,
1545 * as in `(ab)c(de)' -- the second group is #2. */
1546 regnum_t this_group_regnum
;
1548 compile_stack
.avail
--;
1549 begalt
= bufp
->buffer
+ COMPILE_STACK_TOP
.begalt_offset
;
1551 = COMPILE_STACK_TOP
.fixup_alt_jump
1552 ? bufp
->buffer
+ COMPILE_STACK_TOP
.fixup_alt_jump
- 1
1554 laststart
= bufp
->buffer
+ COMPILE_STACK_TOP
.laststart_offset
;
1555 this_group_regnum
= COMPILE_STACK_TOP
.regnum
;
1556 /* If we've reached MAX_REGNUM groups, then this open
1557 * won't actually generate any code, so we'll have to
1558 * clear pending_exact explicitly. */
1561 /* We're at the end of the group, so now we know how many
1562 * groups were inside this one. */
1563 if (this_group_regnum
<= MAX_REGNUM
) {
1564 unsigned char *inner_group_loc
1565 = bufp
->buffer
+ COMPILE_STACK_TOP
.inner_group_offset
;
1567 *inner_group_loc
= regnum
- this_group_regnum
;
1568 BUF_PUSH_3(stop_memory
, this_group_regnum
,
1569 regnum
- this_group_regnum
);
1575 case '|': /* `\|'. */
1576 if (syntax
& RE_LIMITED_OPS
|| syntax
& RE_NO_BK_VBAR
)
1577 goto normal_backslash
;
1579 if (syntax
& RE_LIMITED_OPS
)
1582 /* Insert before the previous alternative a jump which
1583 * jumps to this alternative if the former fails. */
1584 GET_BUFFER_SPACE(3);
1585 INSERT_JUMP(on_failure_jump
, begalt
, b
+ 6);
1589 /* The alternative before this one has a jump after it
1590 * which gets executed if it gets matched. Adjust that
1591 * jump so it will jump to this alternative's analogous
1592 * jump (put in below, which in turn will jump to the next
1593 * (if any) alternative's such jump, etc.). The last such
1594 * jump jumps to the correct final destination. A picture:
1600 * If we are at `b', then fixup_alt_jump right now points to a
1601 * three-byte space after `a'. We'll put in the jump, set
1602 * fixup_alt_jump to right after `b', and leave behind three
1603 * bytes which we'll fill in when we get to after `c'. */
1606 STORE_JUMP(jump_past_alt
, fixup_alt_jump
, b
);
1608 /* Mark and leave space for a jump after this alternative,
1609 * to be filled in later either by next alternative or
1610 * when know we're at the end of a series of alternatives. */
1612 GET_BUFFER_SPACE(3);
1621 /* If \{ is a literal. */
1622 if (!(syntax
& RE_INTERVALS
)
1623 /* If we're at `\{' and it's not the open-interval
1625 || ((syntax
& RE_INTERVALS
) && (syntax
& RE_NO_BK_BRACES
))
1626 || (p
- 2 == pattern
&& p
== pend
))
1627 goto normal_backslash
;
1630 /* If got here, then the syntax allows intervals. */
1632 /* At least (most) this many matches must be made. */
1633 int lower_bound
= -1, upper_bound
= -1;
1635 beg_interval
= p
- 1;
1638 if (syntax
& RE_NO_BK_BRACES
)
1639 goto unfetch_interval
;
1643 GET_UNSIGNED_NUMBER(lower_bound
);
1646 GET_UNSIGNED_NUMBER(upper_bound
);
1647 if (upper_bound
< 0)
1648 upper_bound
= RE_DUP_MAX
;
1650 /* Interval such as `{1}' => match exactly once. */
1651 upper_bound
= lower_bound
;
1653 if (lower_bound
< 0 || upper_bound
> RE_DUP_MAX
1654 || lower_bound
> upper_bound
) {
1655 if (syntax
& RE_NO_BK_BRACES
)
1656 goto unfetch_interval
;
1660 if (!(syntax
& RE_NO_BK_BRACES
)) {
1667 if (syntax
& RE_NO_BK_BRACES
)
1668 goto unfetch_interval
;
1672 /* We just parsed a valid interval. */
1674 /* If it's invalid to have no preceding re. */
1676 if (syntax
& RE_CONTEXT_INVALID_OPS
)
1678 else if (syntax
& RE_CONTEXT_INDEP_OPS
)
1681 goto unfetch_interval
;
1683 /* If the upper bound is zero, don't want to succeed at
1684 * all; jump from `laststart' to `b + 3', which will be
1685 * the end of the buffer after we insert the jump. */
1686 if (upper_bound
== 0) {
1687 GET_BUFFER_SPACE(3);
1688 INSERT_JUMP(jump
, laststart
, b
+ 3);
1691 /* Otherwise, we have a nontrivial interval. When
1692 * we're all done, the pattern will look like:
1693 * set_number_at <jump count> <upper bound>
1694 * set_number_at <succeed_n count> <lower bound>
1695 * succeed_n <after jump addr> <succed_n count>
1697 * jump_n <succeed_n addr> <jump count>
1698 * (The upper bound and `jump_n' are omitted if
1699 * `upper_bound' is 1, though.) */
1700 else { /* If the upper bound is > 1, we need to insert
1701 * more at the end of the loop. */
1702 unsigned nbytes
= 10 + (upper_bound
> 1) * 10;
1704 GET_BUFFER_SPACE(nbytes
);
1706 /* Initialize lower bound of the `succeed_n', even
1707 * though it will be set during matching by its
1708 * attendant `set_number_at' (inserted next),
1709 * because `re_compile_fastmap' needs to know.
1710 * Jump to the `jump_n' we might insert below. */
1711 INSERT_JUMP2(succeed_n
, laststart
,
1712 b
+ 5 + (upper_bound
> 1) * 5,
1716 /* Code to initialize the lower bound. Insert
1717 * before the `succeed_n'. The `5' is the last two
1718 * bytes of this `set_number_at', plus 3 bytes of
1719 * the following `succeed_n'. */
1720 insert_op2(set_number_at
, laststart
, 5, lower_bound
, b
);
1723 if (upper_bound
> 1) { /* More than one repetition is allowed, so
1724 * append a backward jump to the `succeed_n'
1725 * that starts this interval.
1727 * When we've reached this during matching,
1728 * we'll have matched the interval once, so
1729 * jump back only `upper_bound - 1' times. */
1730 STORE_JUMP2(jump_n
, b
, laststart
+ 5,
1734 /* The location we want to set is the second
1735 * parameter of the `jump_n'; that is `b-2' as
1736 * an absolute address. `laststart' will be
1737 * the `set_number_at' we're about to insert;
1738 * `laststart+3' the number to set, the source
1739 * for the relative address. But we are
1740 * inserting into the middle of the pattern --
1741 * so everything is getting moved up by 5.
1742 * Conclusion: (b - 2) - (laststart + 3) + 5,
1743 * i.e., b - laststart.
1745 * We insert this at the beginning of the loop
1746 * so that if we fail during matching, we'll
1747 * reinitialize the bounds. */
1748 insert_op2(set_number_at
, laststart
, b
- laststart
,
1749 upper_bound
- 1, b
);
1754 beg_interval
= NULL
;
1759 /* If an invalid interval, match the characters as literals. */
1760 assert(beg_interval
);
1762 beg_interval
= NULL
;
1764 /* normal_char and normal_backslash need `c'. */
1767 if (!(syntax
& RE_NO_BK_BRACES
)) {
1768 if (p
> pattern
&& p
[-1] == '\\')
1769 goto normal_backslash
;
1782 BUF_PUSH(notwordchar
);
1795 BUF_PUSH(wordbound
);
1799 BUF_PUSH(notwordbound
);
1819 if (syntax
& RE_NO_BK_REFS
)
1827 /* Can't back reference to a subexpression if inside of it. */
1828 if (group_in_compile_stack(compile_stack
, c1
))
1832 BUF_PUSH_2(duplicate
, c1
);
1838 if (syntax
& RE_BK_PLUS_QM
)
1841 goto normal_backslash
;
1845 /* You might think it would be useful for \ to mean
1846 * not to translate; but if we don't translate it
1847 * it will never match anything. */
1855 /* Expects the character in `c'. */
1857 /* If no exactn currently being built. */
1860 /* If last exactn not at current position. */
1861 || pending_exact
+ *pending_exact
+ 1 != b
1863 /* We have only one byte following the exactn for the count. */
1864 || *pending_exact
== (1 << BYTEWIDTH
) - 1
1866 /* If followed by a repetition operator. */
1867 || *p
== '*' || *p
== '^'
1868 || ((syntax
& RE_BK_PLUS_QM
)
1869 ? *p
== '\\' && (p
[1] == '+' || p
[1] == '?')
1870 : (*p
== '+' || *p
== '?'))
1871 || ((syntax
& RE_INTERVALS
)
1872 && ((syntax
& RE_NO_BK_BRACES
)
1874 : (p
[0] == '\\' && p
[1] == '{')))) {
1875 /* Start building a new exactn. */
1879 BUF_PUSH_2(exactn
, 0);
1880 pending_exact
= b
- 1;
1886 } /* while p != pend */
1889 /* Through the pattern now. */
1892 STORE_JUMP(jump_past_alt
, fixup_alt_jump
, b
);
1894 if (!COMPILE_STACK_EMPTY
)
1897 free(compile_stack
.stack
);
1899 /* We have succeeded; set the length of the buffer. */
1900 bufp
->used
= b
- bufp
->buffer
;
1904 DEBUG_PRINT1("\nCompiled pattern: ");
1905 print_compiled_pattern(bufp
);
1910 } /* regex_compile */
1912 /* Subroutines for `regex_compile'. */
1914 /* Store OP at LOC followed by two-byte integer parameter ARG. */
1916 void store_op1(re_opcode_t op
, unsigned char *loc
, int arg
)
1918 *loc
= (unsigned char) op
;
1919 STORE_NUMBER(loc
+ 1, arg
);
1923 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
1926 store_op2( re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
)
1928 *loc
= (unsigned char) op
;
1929 STORE_NUMBER(loc
+ 1, arg1
);
1930 STORE_NUMBER(loc
+ 3, arg2
);
1934 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
1935 * for OP followed by two-byte integer parameter ARG. */
1938 insert_op1(re_opcode_t op
, unsigned char *loc
, int arg
, unsigned char *end
)
1940 register unsigned char *pfrom
= end
;
1941 register unsigned char *pto
= end
+ 3;
1943 while (pfrom
!= loc
)
1946 store_op1(op
, loc
, arg
);
1950 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
1953 insert_op2(re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
, unsigned char *end
)
1955 register unsigned char *pfrom
= end
;
1956 register unsigned char *pto
= end
+ 5;
1958 while (pfrom
!= loc
)
1961 store_op2(op
, loc
, arg1
, arg2
);
1965 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
1966 * after an alternative or a begin-subexpression. We assume there is at
1967 * least one character before the ^. */
1970 at_begline_loc_p(const char * pattern
, const char *p
, reg_syntax_t syntax
)
1972 const char *prev
= p
- 2;
1973 boolean prev_prev_backslash
= prev
> pattern
&& prev
[-1] == '\\';
1976 /* After a subexpression? */
1977 (*prev
== '(' && (syntax
& RE_NO_BK_PARENS
|| prev_prev_backslash
))
1978 /* After an alternative? */
1979 || (*prev
== '|' && (syntax
& RE_NO_BK_VBAR
|| prev_prev_backslash
));
1983 /* The dual of at_begline_loc_p. This one is for $. We assume there is
1984 * at least one character after the $, i.e., `P < PEND'. */
1987 at_endline_loc_p(const char *p
, const char *pend
, int syntax
)
1989 const char *next
= p
;
1990 boolean next_backslash
= *next
== '\\';
1991 const char *next_next
= p
+ 1 < pend
? p
+ 1 : NULL
;
1994 /* Before a subexpression? */
1995 (syntax
& RE_NO_BK_PARENS
? *next
== ')'
1996 : next_backslash
&& next_next
&& *next_next
== ')')
1997 /* Before an alternative? */
1998 || (syntax
& RE_NO_BK_VBAR
? *next
== '|'
1999 : next_backslash
&& next_next
&& *next_next
== '|');
2003 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2004 * false if it's not. */
2007 group_in_compile_stack(compile_stack_type compile_stack
, regnum_t regnum
)
2011 for (this_element
= compile_stack
.avail
- 1;
2014 if (compile_stack
.stack
[this_element
].regnum
== regnum
)
2021 /* Read the ending character of a range (in a bracket expression) from the
2022 * uncompiled pattern *P_PTR (which ends at PEND). We assume the
2023 * starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
2024 * Then we set the translation of all bits between the starting and
2025 * ending characters (inclusive) in the compiled pattern B.
2027 * Return an error code.
2029 * We use these short variable names so we can use the same macros as
2030 * `regex_compile' itself. */
2033 compile_range(const char **p_ptr
, const char *pend
, char *translate
, reg_syntax_t syntax
, unsigned char *b
)
2037 const char *p
= *p_ptr
;
2038 int range_start
, range_end
;
2043 /* Even though the pattern is a signed `char *', we need to fetch
2044 * with unsigned char *'s; if the high bit of the pattern character
2045 * is set, the range endpoints will be negative if we fetch using a
2048 * We also want to fetch the endpoints without translating them; the
2049 * appropriate translation is done in the bit-setting loop below. */
2050 range_start
= ((unsigned char *) p
)[-2];
2051 range_end
= ((unsigned char *) p
)[0];
2053 /* Have to increment the pointer into the pattern string, so the
2054 * caller isn't still at the ending character. */
2057 /* If the start is after the end, the range is empty. */
2058 if (range_start
> range_end
)
2059 return syntax
& RE_NO_EMPTY_RANGES
? REG_ERANGE
: REG_NOERROR
;
2061 /* Here we see why `this_char' has to be larger than an `unsigned
2062 * char' -- the range is inclusive, so if `range_end' == 0xff
2063 * (assuming 8-bit characters), we would otherwise go into an infinite
2064 * loop, since all characters <= 0xff. */
2065 for (this_char
= range_start
; this_char
<= range_end
; this_char
++) {
2066 SET_LIST_BIT(TRANSLATE(this_char
));
2072 /* Failure stack declarations and macros; both re_compile_fastmap and
2073 * re_match_2 use a failure stack. These have to be macros because of
2074 * REGEX_ALLOCATE. */
2077 /* Number of failure points for which to initially allocate space
2078 * when matching. If this number is exceeded, we allocate more
2079 * space, so it is not a hard limit. */
2080 #ifndef INIT_FAILURE_ALLOC
2081 #define INIT_FAILURE_ALLOC 5
2084 /* Roughly the maximum number of failure points on the stack. Would be
2085 * exactly that if always used MAX_FAILURE_SPACE each time we failed.
2086 * This is a variable only so users of regex can assign to it; we never
2087 * change it ourselves. */
2088 int re_max_failures
= 2000;
2090 typedef const unsigned char *fail_stack_elt_t
;
2093 fail_stack_elt_t
*stack
;
2095 unsigned avail
; /* Offset of next open position. */
2098 #define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
2099 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
2100 #define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
2101 #define FAIL_STACK_TOP() (fail_stack.stack[fail_stack.avail])
2104 /* Initialize `fail_stack'. Do `return -2' if the alloc fails. */
2106 #define INIT_FAIL_STACK() \
2108 fail_stack.stack = (fail_stack_elt_t *) \
2109 REGEX_ALLOCATE (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t)); \
2111 if (fail_stack.stack == NULL) \
2114 fail_stack.size = INIT_FAILURE_ALLOC; \
2115 fail_stack.avail = 0; \
2119 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
2121 * Return 1 if succeeds, and 0 if either ran out of memory
2122 * allocating space for it or it was already too large.
2124 * REGEX_REALLOCATE requires `destination' be declared. */
2126 #define DOUBLE_FAIL_STACK(fail_stack) \
2127 ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS \
2129 : ((fail_stack).stack = (fail_stack_elt_t *) \
2130 REGEX_REALLOCATE ((fail_stack).stack, \
2131 (fail_stack).size * sizeof (fail_stack_elt_t), \
2132 ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)), \
2134 (fail_stack).stack == NULL \
2136 : ((fail_stack).size <<= 1, \
2140 /* Push PATTERN_OP on FAIL_STACK.
2142 * Return 1 if was able to do so and 0 if ran out of memory allocating
2143 * space to do so. */
2144 #define PUSH_PATTERN_OP(pattern_op, fail_stack) \
2145 ((FAIL_STACK_FULL () \
2146 && !DOUBLE_FAIL_STACK (fail_stack)) \
2148 : ((fail_stack).stack[(fail_stack).avail++] = pattern_op, \
2151 /* This pushes an item onto the failure stack. Must be a four-byte
2152 * value. Assumes the variable `fail_stack'. Probably should only
2153 * be called from within `PUSH_FAILURE_POINT'. */
2154 #define PUSH_FAILURE_ITEM(item) \
2155 fail_stack.stack[fail_stack.avail++] = (fail_stack_elt_t) item
2157 /* The complement operation. Assumes `fail_stack' is nonempty. */
2158 #define POP_FAILURE_ITEM() fail_stack.stack[--fail_stack.avail]
2160 /* Used to omit pushing failure point id's when we're not debugging. */
2162 #define DEBUG_PUSH PUSH_FAILURE_ITEM
2163 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_ITEM ()
2165 #define DEBUG_PUSH(item)
2166 #define DEBUG_POP(item_addr)
2170 /* Push the information about the state we will need
2171 * if we ever fail back to it.
2173 * Requires variables fail_stack, regstart, regend, reg_info, and
2174 * num_regs be declared. DOUBLE_FAIL_STACK requires `destination' be
2177 * Does `return FAILURE_CODE' if runs out of memory. */
2179 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
2181 char *destination; \
2182 /* Must be int, so when we don't save any registers, the arithmetic \
2183 of 0 + -1 isn't done as unsigned. */ \
2186 DEBUG_STATEMENT (failure_id++); \
2187 DEBUG_STATEMENT (nfailure_points_pushed++); \
2188 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
2189 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
2190 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
2192 DEBUG_PRINT2 (" slots needed: %d\n", NUM_FAILURE_ITEMS); \
2193 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
2195 /* Ensure we have enough space allocated for what we will push. */ \
2196 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
2198 if (!DOUBLE_FAIL_STACK (fail_stack)) \
2199 return failure_code; \
2201 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
2202 (fail_stack).size); \
2203 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
2206 /* Push the info, starting with the registers. */ \
2207 DEBUG_PRINT1 ("\n"); \
2209 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
2212 DEBUG_PRINT2 (" Pushing reg: %d\n", this_reg); \
2213 DEBUG_STATEMENT (num_regs_pushed++); \
2215 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2216 PUSH_FAILURE_ITEM (regstart[this_reg]); \
2218 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2219 PUSH_FAILURE_ITEM (regend[this_reg]); \
2221 DEBUG_PRINT2 (" info: 0x%x\n ", reg_info[this_reg]); \
2222 DEBUG_PRINT2 (" match_null=%d", \
2223 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
2224 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
2225 DEBUG_PRINT2 (" matched_something=%d", \
2226 MATCHED_SOMETHING (reg_info[this_reg])); \
2227 DEBUG_PRINT2 (" ever_matched=%d", \
2228 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
2229 DEBUG_PRINT1 ("\n"); \
2230 PUSH_FAILURE_ITEM (reg_info[this_reg].word); \
2233 DEBUG_PRINT2 (" Pushing low active reg: %d\n", lowest_active_reg);\
2234 PUSH_FAILURE_ITEM (lowest_active_reg); \
2236 DEBUG_PRINT2 (" Pushing high active reg: %d\n", highest_active_reg);\
2237 PUSH_FAILURE_ITEM (highest_active_reg); \
2239 DEBUG_PRINT2 (" Pushing pattern 0x%x: ", pattern_place); \
2240 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
2241 PUSH_FAILURE_ITEM (pattern_place); \
2243 DEBUG_PRINT2 (" Pushing string 0x%x: `", string_place); \
2244 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
2246 DEBUG_PRINT1 ("'\n"); \
2247 PUSH_FAILURE_ITEM (string_place); \
2249 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
2250 DEBUG_PUSH (failure_id); \
2253 /* This is the number of items that are pushed and popped on the stack
2254 * for each register. */
2255 #define NUM_REG_ITEMS 3
2257 /* Individual items aside from the registers. */
2259 #define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
2261 #define NUM_NONREG_ITEMS 4
2264 /* We push at most this many items on the stack. */
2265 #define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
2267 /* We actually push this many items. */
2268 #define NUM_FAILURE_ITEMS \
2269 ((highest_active_reg - lowest_active_reg + 1) * NUM_REG_ITEMS \
2272 /* How many items can still be added to the stack without overflowing it. */
2273 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
2276 /* Pops what PUSH_FAIL_STACK pushes.
2278 * We restore into the parameters, all of which should be lvalues:
2279 * STR -- the saved data position.
2280 * PAT -- the saved pattern position.
2281 * LOW_REG, HIGH_REG -- the highest and lowest active registers.
2282 * REGSTART, REGEND -- arrays of string positions.
2283 * REG_INFO -- array of information about each subexpression.
2285 * Also assumes the variables `fail_stack' and (if debugging), `bufp',
2286 * `pend', `string1', `size1', `string2', and `size2'. */
2288 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
2290 DEBUG_STATEMENT (fail_stack_elt_t failure_id;) \
2292 const unsigned char *string_temp; \
2294 assert (!FAIL_STACK_EMPTY ()); \
2296 /* Remove failure points and point to how many regs pushed. */ \
2297 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
2298 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
2299 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
2301 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
2303 DEBUG_POP (&failure_id); \
2304 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
2306 /* If the saved string location is NULL, it came from an \
2307 on_failure_keep_string_jump opcode, and we want to throw away the \
2308 saved NULL, thus retaining our current position in the string. */ \
2309 string_temp = POP_FAILURE_ITEM (); \
2310 if (string_temp != NULL) \
2311 str = (const char *) string_temp; \
2313 DEBUG_PRINT2 (" Popping string 0x%x: `", str); \
2314 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
2315 DEBUG_PRINT1 ("'\n"); \
2317 pat = (unsigned char *) POP_FAILURE_ITEM (); \
2318 DEBUG_PRINT2 (" Popping pattern 0x%x: ", pat); \
2319 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
2321 /* Restore register info. */ \
2322 high_reg = (unsigned long) POP_FAILURE_ITEM (); \
2323 DEBUG_PRINT2 (" Popping high active reg: %d\n", high_reg); \
2325 low_reg = (unsigned long) POP_FAILURE_ITEM (); \
2326 DEBUG_PRINT2 (" Popping low active reg: %d\n", low_reg); \
2328 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
2330 DEBUG_PRINT2 (" Popping reg: %d\n", this_reg); \
2332 reg_info[this_reg].word = POP_FAILURE_ITEM (); \
2333 DEBUG_PRINT2 (" info: 0x%x\n", reg_info[this_reg]); \
2335 regend[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2336 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2338 regstart[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2339 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2342 DEBUG_STATEMENT (nfailure_points_popped++); \
2343 } /* POP_FAILURE_POINT */
2345 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2346 * BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
2347 * characters can start a string that matches the pattern. This fastmap
2348 * is used by re_search to skip quickly over impossible starting points.
2350 * The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2351 * area as BUFP->fastmap.
2353 * We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2354 * the pattern buffer.
2356 * Returns 0 if we succeed, -2 if an internal error. */
2359 re_compile_fastmap(struct re_pattern_buffer
*bufp
)
2362 re_compile_fastmap(bufp
)
2363 struct re_pattern_buffer
*bufp
;
2367 fail_stack_type fail_stack
;
2368 #ifndef REGEX_MALLOC
2371 /* We don't push any register information onto the failure stack. */
2372 unsigned num_regs
= 0;
2374 register char *fastmap
= bufp
->fastmap
;
2375 unsigned char *pattern
= bufp
->buffer
;
2376 unsigned long size
= bufp
->used
;
2377 const unsigned char *p
= pattern
;
2378 register unsigned char *pend
= pattern
+ size
;
2380 /* Assume that each path through the pattern can be null until
2381 * proven otherwise. We set this false at the bottom of switch
2382 * statement, to which we get only if a particular path doesn't
2383 * match the empty string. */
2384 boolean path_can_be_null
= true;
2386 /* We aren't doing a `succeed_n' to begin with. */
2387 boolean succeed_n_p
= false;
2389 assert(fastmap
!= NULL
&& p
!= NULL
);
2392 memset(fastmap
, 0, 1 << BYTEWIDTH
); /* Assume nothing's valid. */
2393 bufp
->fastmap_accurate
= 1; /* It will be when we're done. */
2394 bufp
->can_be_null
= 0;
2396 while (p
!= pend
|| !FAIL_STACK_EMPTY()) {
2398 bufp
->can_be_null
|= path_can_be_null
;
2400 /* Reset for next path. */
2401 path_can_be_null
= true;
2403 p
= fail_stack
.stack
[--fail_stack
.avail
];
2405 /* We should never be about to go beyond the end of the pattern. */
2408 #ifdef SWITCH_ENUM_BUG
2409 switch ((int) ((re_opcode_t
) * p
++))
2411 switch ((re_opcode_t
) * p
++)
2415 /* I guess the idea here is to simply not bother with a fastmap
2416 * if a backreference is used, since it's too hard to figure out
2417 * the fastmap for the corresponding group. Setting
2418 * `can_be_null' stops `re_search_2' from using the fastmap, so
2419 * that is all we do. */
2421 bufp
->can_be_null
= 1;
2425 /* Following are the cases which match a character. These end
2434 for (j
= *p
++ * BYTEWIDTH
- 1; j
>= 0; j
--)
2435 if (p
[j
/ BYTEWIDTH
] & (1 << (j
% BYTEWIDTH
)))
2441 /* Chars beyond end of map must be allowed. */
2442 for (j
= *p
* BYTEWIDTH
; j
< (1 << BYTEWIDTH
); j
++)
2445 for (j
= *p
++ * BYTEWIDTH
- 1; j
>= 0; j
--)
2446 if (!(p
[j
/ BYTEWIDTH
] & (1 << (j
% BYTEWIDTH
))))
2452 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
2453 if (SYNTAX(j
) == Sword
)
2459 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
2460 if (SYNTAX(j
) != Sword
)
2466 /* `.' matches anything ... */
2467 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
2470 /* ... except perhaps newline. */
2471 if (!(bufp
->syntax
& RE_DOT_NEWLINE
))
2474 /* Return if we have already set `can_be_null'; if we have,
2475 * then the fastmap is irrelevant. Something's wrong here. */
2476 else if (bufp
->can_be_null
)
2479 /* Otherwise, have to check alternative paths. */
2492 case push_dummy_failure
:
2497 case pop_failure_jump
:
2498 case maybe_pop_jump
:
2501 case dummy_failure_jump
:
2502 EXTRACT_NUMBER_AND_INCR(j
, p
);
2507 /* Jump backward implies we just went through the body of a
2508 * loop and matched nothing. Opcode jumped to should be
2509 * `on_failure_jump' or `succeed_n'. Just treat it like an
2510 * ordinary jump. For a * loop, it has pushed its failure
2511 * point already; if so, discard that as redundant. */
2512 if ((re_opcode_t
) * p
!= on_failure_jump
2513 && (re_opcode_t
) * p
!= succeed_n
)
2517 EXTRACT_NUMBER_AND_INCR(j
, p
);
2520 /* If what's on the stack is where we are now, pop it. */
2521 if (!FAIL_STACK_EMPTY()
2522 && fail_stack
.stack
[fail_stack
.avail
- 1] == p
)
2528 case on_failure_jump
:
2529 case on_failure_keep_string_jump
:
2530 handle_on_failure_jump
:
2531 EXTRACT_NUMBER_AND_INCR(j
, p
);
2533 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
2534 * end of the pattern. We don't want to push such a point,
2535 * since when we restore it above, entering the switch will
2536 * increment `p' past the end of the pattern. We don't need
2537 * to push such a point since we obviously won't find any more
2538 * fastmap entries beyond `pend'. Such a pattern can match
2539 * the null string, though. */
2541 if (!PUSH_PATTERN_OP(p
+ j
, fail_stack
))
2544 bufp
->can_be_null
= 1;
2547 EXTRACT_NUMBER_AND_INCR(k
, p
); /* Skip the n. */
2548 succeed_n_p
= false;
2554 /* Get to the number of times to succeed. */
2557 /* Increment p past the n for when k != 0. */
2558 EXTRACT_NUMBER_AND_INCR(k
, p
);
2561 succeed_n_p
= true; /* Spaghetti code alert. */
2562 goto handle_on_failure_jump
;
2579 abort(); /* We have listed all the cases. */
2582 /* Getting here means we have found the possible starting
2583 * characters for one path of the pattern -- and that the empty
2584 * string does not match. We need not follow this path further.
2585 * Instead, look at the next alternative (remembered on the
2586 * stack), or quit if no more. The test at the top of the loop
2587 * does these things. */
2588 path_can_be_null
= false;
2592 /* Set `can_be_null' for the last path (also the first path, if the
2593 * pattern is empty). */
2594 bufp
->can_be_null
|= path_can_be_null
;
2596 } /* re_compile_fastmap */
2598 /* Searching routines. */
2600 /* Like re_search_2, below, but only one string is specified, and
2601 * doesn't let you say where to stop matching. */
2604 re_search(bufp
, string
, size
, startpos
, range
, regs
)
2605 struct re_pattern_buffer
*bufp
;
2607 int size
, startpos
, range
;
2608 struct re_registers
*regs
;
2610 return re_search_2(bufp
, NULL
, 0, string
, size
, startpos
, range
,
2615 /* Using the compiled pattern in BUFP->buffer, first tries to match the
2616 * virtual concatenation of STRING1 and STRING2, starting first at index
2617 * STARTPOS, then at STARTPOS + 1, and so on.
2619 * STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
2621 * RANGE is how far to scan while trying to match. RANGE = 0 means try
2622 * only at STARTPOS; in general, the last start tried is STARTPOS +
2625 * In REGS, return the indices of the virtual concatenation of STRING1
2626 * and STRING2 that matched the entire BUFP->buffer and its contained
2629 * Do not consider matching one past the index STOP in the virtual
2630 * concatenation of STRING1 and STRING2.
2632 * We return either the position in the strings at which the match was
2633 * found, -1 if no match, or -2 if error (such as failure
2634 * stack overflow). */
2637 re_search_2(bufp
, string1
, size1
, string2
, size2
, startpos
, range
, regs
, stop
)
2638 struct re_pattern_buffer
*bufp
;
2639 const char *string1
, *string2
;
2643 struct re_registers
*regs
;
2647 register char *fastmap
= bufp
->fastmap
;
2648 register char *translate
= bufp
->translate
;
2649 int total_size
= size1
+ size2
;
2650 int endpos
= startpos
+ range
;
2652 /* Check for out-of-range STARTPOS. */
2653 if (startpos
< 0 || startpos
> total_size
)
2656 /* Fix up RANGE if it might eventually take us outside
2657 * the virtual concatenation of STRING1 and STRING2. */
2659 range
= -1 - startpos
;
2660 else if (endpos
> total_size
)
2661 range
= total_size
- startpos
;
2663 /* If the search isn't to be a backwards one, don't waste time in a
2664 * search for a pattern that must be anchored. */
2665 if (bufp
->used
> 0 && (re_opcode_t
) bufp
->buffer
[0] == begbuf
&& range
> 0) {
2671 /* Update the fastmap now if not correct already. */
2672 if (fastmap
&& !bufp
->fastmap_accurate
)
2673 if (re_compile_fastmap(bufp
) == -2)
2676 /* Loop through the string, looking for a place to start matching. */
2678 /* If a fastmap is supplied, skip quickly over characters that
2679 * cannot be the start of a match. If the pattern can match the
2680 * null string, however, we don't need to skip characters; we want
2681 * the first null string. */
2682 if (fastmap
&& startpos
< total_size
&& !bufp
->can_be_null
) {
2683 if (range
> 0) { /* Searching forwards. */
2684 register const char *d
;
2685 register int lim
= 0;
2688 if (startpos
< size1
&& startpos
+ range
>= size1
)
2689 lim
= range
- (size1
- startpos
);
2691 d
= (startpos
>= size1
? string2
- size1
: string1
) + startpos
;
2693 /* Written out as an if-else to avoid testing `translate'
2694 * inside the loop. */
2697 && !fastmap
[(unsigned char)
2698 translate
[(unsigned char) *d
++]])
2701 while (range
> lim
&& !fastmap
[(unsigned char) *d
++])
2704 startpos
+= irange
- range
;
2705 } else { /* Searching backwards. */
2706 register char c
= (size1
== 0 || startpos
>= size1
2707 ? string2
[startpos
- size1
]
2708 : string1
[startpos
]);
2710 if (!fastmap
[(unsigned char) TRANSLATE(c
)])
2714 /* If can't match the null string, and that's all we have left, fail. */
2715 if (range
>= 0 && startpos
== total_size
&& fastmap
2716 && !bufp
->can_be_null
)
2719 val
= re_match_2(bufp
, string1
, size1
, string2
, size2
,
2720 startpos
, regs
, stop
);
2730 else if (range
> 0) {
2741 /* Declarations and macros for re_match_2. */
2743 /* Structure for per-register (a.k.a. per-group) information.
2744 * This must not be longer than one word, because we push this value
2745 * onto the failure stack. Other register information, such as the
2746 * starting and ending positions (which are addresses), and the list of
2747 * inner groups (which is a bits list) are maintained in separate
2750 * We are making a (strictly speaking) nonportable assumption here: that
2751 * the compiler will pack our bit fields into something that fits into
2752 * the type of `word', i.e., is something that fits into one item on the
2755 fail_stack_elt_t word
;
2757 /* This field is one if this group can match the empty string,
2758 * zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
2759 #define MATCH_NULL_UNSET_VALUE 3
2760 unsigned match_null_string_p
:2;
2761 unsigned is_active
:1;
2762 unsigned matched_something
:1;
2763 unsigned ever_matched_something
:1;
2765 } register_info_type
;
2766 static boolean
alt_match_null_string_p(unsigned char *p
, unsigned char *end
, register_info_type
*reg_info
);
2767 static boolean
common_op_match_null_string_p( unsigned char **p
, unsigned char *end
, register_info_type
*reg_info
);
2768 static int bcmp_translate(unsigned char const *s1
, unsigned char const *s2
, register int len
, char *translate
);
2769 static boolean
group_match_null_string_p(unsigned char **p
, unsigned char *end
, register_info_type
*reg_info
);
2771 #define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
2772 #define IS_ACTIVE(R) ((R).bits.is_active)
2773 #define MATCHED_SOMETHING(R) ((R).bits.matched_something)
2774 #define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
2777 /* Call this when have matched a real character; it sets `matched' flags
2778 * for the subexpressions which we are currently inside. Also records
2779 * that those subexprs have matched. */
2780 #define SET_REGS_MATCHED() \
2784 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
2786 MATCHED_SOMETHING (reg_info[r]) \
2787 = EVER_MATCHED_SOMETHING (reg_info[r]) \
2794 /* This converts PTR, a pointer into one of the search strings `string1'
2795 * and `string2' into an offset from the beginning of that string. */
2796 #define POINTER_TO_OFFSET(ptr) \
2797 (FIRST_STRING_P (ptr) ? (ptr) - string1 : (ptr) - string2 + size1)
2799 /* Registers are set to a sentinel when they haven't yet matched. */
2800 #define REG_UNSET_VALUE ((char *) -1)
2801 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
2804 /* Macros for dealing with the split strings in re_match_2. */
2806 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
2808 /* Call before fetching a character with *d. This switches over to
2809 * string2 if necessary. */
2810 #define PREFETCH() \
2813 /* End of string2 => fail. */ \
2814 if (dend == end_match_2) \
2816 /* End of string1 => advance to string2. */ \
2818 dend = end_match_2; \
2822 /* Test if at very beginning or at very end of the virtual concatenation
2823 * of `string1' and `string2'. If only one string, it's `string2'. */
2824 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
2825 #define AT_STRINGS_END(d) ((d) == end2)
2828 /* Test if D points to a character which is word-constituent. We have
2829 * two special cases to check for: if past the end of string1, look at
2830 * the first character in string2; and if before the beginning of
2831 * string2, look at the last character in string1. */
2832 #define WORDCHAR_P(d) \
2833 (SYNTAX ((d) == end1 ? *string2 \
2834 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
2837 /* Test if the character before D and the one at D differ with respect
2838 * to being word-constituent. */
2839 #define AT_WORD_BOUNDARY(d) \
2840 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
2841 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
2844 /* Free everything we malloc. */
2846 #define FREE_VAR(var) if (var) free (var); var = NULL
2847 #define FREE_VARIABLES() \
2849 FREE_VAR (fail_stack.stack); \
2850 FREE_VAR (regstart); \
2851 FREE_VAR (regend); \
2852 FREE_VAR (old_regstart); \
2853 FREE_VAR (old_regend); \
2854 FREE_VAR (best_regstart); \
2855 FREE_VAR (best_regend); \
2856 FREE_VAR (reg_info); \
2857 FREE_VAR (reg_dummy); \
2858 FREE_VAR (reg_info_dummy); \
2860 #else /* not REGEX_MALLOC */
2861 /* Some MIPS systems (at least) want this to free alloca'd storage. */
2862 #define FREE_VARIABLES() alloca (0)
2863 #endif /* not REGEX_MALLOC */
2866 /* These values must meet several constraints. They must not be valid
2867 * register values; since we have a limit of 255 registers (because
2868 * we use only one byte in the pattern for the register number), we can
2869 * use numbers larger than 255. They must differ by 1, because of
2870 * NUM_FAILURE_ITEMS above. And the value for the lowest register must
2871 * be larger than the value for the highest register, so we do not try
2872 * to actually save any registers when none are active. */
2873 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
2874 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
2876 /* Matching routines. */
2878 /* re_match_2 matches the compiled pattern in BUFP against the
2879 * the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
2880 * and SIZE2, respectively). We start matching at POS, and stop
2883 * If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
2884 * store offsets for the substring each group matched in REGS. See the
2885 * documentation for exactly how many groups we fill.
2887 * We return -1 if no match, -2 if an internal error (such as the
2888 * failure stack overflowing). Otherwise, we return the length of the
2889 * matched substring. */
2892 re_match_2(bufp
, string1
, size1
, string2
, size2
, pos
, regs
, stop
)
2893 struct re_pattern_buffer
*bufp
;
2894 const char *string1
, *string2
;
2897 struct re_registers
*regs
;
2900 /* General temporaries. */
2904 /* Just past the end of the corresponding string. */
2905 const char *end1
, *end2
;
2907 /* Pointers into string1 and string2, just past the last characters in
2908 * each to consider matching. */
2909 const char *end_match_1
, *end_match_2
;
2911 /* Where we are in the data, and the end of the current string. */
2912 const char *d
, *dend
;
2914 /* Where we are in the pattern, and the end of the pattern. */
2915 unsigned char *p
= bufp
->buffer
;
2916 register unsigned char *pend
= p
+ bufp
->used
;
2918 /* We use this to map every character in the string. */
2919 char *translate
= bufp
->translate
;
2921 /* Failure point stack. Each place that can handle a failure further
2922 * down the line pushes a failure point on this stack. It consists of
2923 * restart, regend, and reg_info for all registers corresponding to
2924 * the subexpressions we're currently inside, plus the number of such
2925 * registers, and, finally, two char *'s. The first char * is where
2926 * to resume scanning the pattern; the second one is where to resume
2927 * scanning the strings. If the latter is zero, the failure point is
2928 * a ``dummy''; if a failure happens and the failure point is a dummy,
2929 * it gets discarded and the next next one is tried. */
2930 fail_stack_type fail_stack
;
2932 static unsigned failure_id
= 0;
2933 unsigned nfailure_points_pushed
= 0, nfailure_points_popped
= 0;
2936 /* We fill all the registers internally, independent of what we
2937 * return, for use in backreferences. The number here includes
2938 * an element for register zero. */
2939 unsigned num_regs
= bufp
->re_nsub
+ 1;
2941 /* The currently active registers. */
2942 unsigned long lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
2943 unsigned long highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
2945 /* Information on the contents of registers. These are pointers into
2946 * the input strings; they record just what was matched (on this
2947 * attempt) by a subexpression part of the pattern, that is, the
2948 * regnum-th regstart pointer points to where in the pattern we began
2949 * matching and the regnum-th regend points to right after where we
2950 * stopped matching the regnum-th subexpression. (The zeroth register
2951 * keeps track of what the whole pattern matches.) */
2952 const char **regstart
= NULL
, **regend
= NULL
;
2954 /* If a group that's operated upon by a repetition operator fails to
2955 * match anything, then the register for its start will need to be
2956 * restored because it will have been set to wherever in the string we
2957 * are when we last see its open-group operator. Similarly for a
2958 * register's end. */
2959 const char **old_regstart
= NULL
, **old_regend
= NULL
;
2961 /* The is_active field of reg_info helps us keep track of which (possibly
2962 * nested) subexpressions we are currently in. The matched_something
2963 * field of reg_info[reg_num] helps us tell whether or not we have
2964 * matched any of the pattern so far this time through the reg_num-th
2965 * subexpression. These two fields get reset each time through any
2966 * loop their register is in. */
2967 register_info_type
*reg_info
= NULL
;
2969 /* The following record the register info as found in the above
2970 * variables when we find a match better than any we've seen before.
2971 * This happens as we backtrack through the failure points, which in
2972 * turn happens only if we have not yet matched the entire string. */
2973 unsigned best_regs_set
= false;
2974 const char **best_regstart
= NULL
, **best_regend
= NULL
;
2976 /* Logically, this is `best_regend[0]'. But we don't want to have to
2977 * allocate space for that if we're not allocating space for anything
2978 * else (see below). Also, we never need info about register 0 for
2979 * any of the other register vectors, and it seems rather a kludge to
2980 * treat `best_regend' differently than the rest. So we keep track of
2981 * the end of the best match so far in a separate variable. We
2982 * initialize this to NULL so that when we backtrack the first time
2983 * and need to test it, it's not garbage. */
2984 const char *match_end
= NULL
;
2986 /* Used when we pop values we don't care about. */
2987 const char **reg_dummy
= NULL
;
2988 register_info_type
*reg_info_dummy
= NULL
;
2991 /* Counts the total number of registers pushed. */
2992 unsigned num_regs_pushed
= 0;
2995 DEBUG_PRINT1("\n\nEntering re_match_2.\n");
2999 /* Do not bother to initialize all the register variables if there are
3000 * no groups in the pattern, as it takes a fair amount of time. If
3001 * there are groups, we include space for register 0 (the whole
3002 * pattern), even though we never use it, since it simplifies the
3003 * array indexing. We should fix this. */
3004 if (bufp
->re_nsub
) {
3005 regstart
= REGEX_TALLOC(num_regs
, const char *);
3006 regend
= REGEX_TALLOC(num_regs
, const char *);
3007 old_regstart
= REGEX_TALLOC(num_regs
, const char *);
3008 old_regend
= REGEX_TALLOC(num_regs
, const char *);
3009 best_regstart
= REGEX_TALLOC(num_regs
, const char *);
3010 best_regend
= REGEX_TALLOC(num_regs
, const char *);
3011 reg_info
= REGEX_TALLOC(num_regs
, register_info_type
);
3012 reg_dummy
= REGEX_TALLOC(num_regs
, const char *);
3013 reg_info_dummy
= REGEX_TALLOC(num_regs
, register_info_type
);
3015 if (!(regstart
&& regend
&& old_regstart
&& old_regend
&& reg_info
3016 && best_regstart
&& best_regend
&& reg_dummy
&& reg_info_dummy
)) {
3023 /* We must initialize all our variables to NULL, so that
3024 * `FREE_VARIABLES' doesn't try to free them. */
3025 regstart
= regend
= old_regstart
= old_regend
= best_regstart
3026 = best_regend
= reg_dummy
= NULL
;
3027 reg_info
= reg_info_dummy
= (register_info_type
*) NULL
;
3029 #endif /* REGEX_MALLOC */
3031 /* The starting position is bogus. */
3032 if (pos
< 0 || pos
> size1
+ size2
) {
3036 /* Initialize subexpression text positions to -1 to mark ones that no
3037 * start_memory/stop_memory has been seen for. Also initialize the
3038 * register information struct. */
3039 for (mcnt
= 1; mcnt
< num_regs
; mcnt
++) {
3040 regstart
[mcnt
] = regend
[mcnt
]
3041 = old_regstart
[mcnt
] = old_regend
[mcnt
] = REG_UNSET_VALUE
;
3043 REG_MATCH_NULL_STRING_P(reg_info
[mcnt
]) = MATCH_NULL_UNSET_VALUE
;
3044 IS_ACTIVE(reg_info
[mcnt
]) = 0;
3045 MATCHED_SOMETHING(reg_info
[mcnt
]) = 0;
3046 EVER_MATCHED_SOMETHING(reg_info
[mcnt
]) = 0;
3049 /* We move `string1' into `string2' if the latter's empty -- but not if
3050 * `string1' is null. */
3051 if (size2
== 0 && string1
!= NULL
) {
3057 end1
= string1
+ size1
;
3058 end2
= string2
+ size2
;
3060 /* Compute where to stop matching, within the two strings. */
3061 if (stop
<= size1
) {
3062 end_match_1
= string1
+ stop
;
3063 end_match_2
= string2
;
3066 end_match_2
= string2
+ stop
- size1
;
3069 /* `p' scans through the pattern as `d' scans through the data.
3070 * `dend' is the end of the input string that `d' points within. `d'
3071 * is advanced into the following input string whenever necessary, but
3072 * this happens before fetching; therefore, at the beginning of the
3073 * loop, `d' can be pointing at the end of a string, but it cannot
3074 * equal `string2'. */
3075 if (size1
> 0 && pos
<= size1
) {
3079 d
= string2
+ pos
- size1
;
3083 DEBUG_PRINT1("The compiled pattern is: ");
3084 DEBUG_PRINT_COMPILED_PATTERN(bufp
, p
, pend
);
3085 DEBUG_PRINT1("The string to match is: `");
3086 DEBUG_PRINT_DOUBLE_STRING(d
, string1
, size1
, string2
, size2
);
3087 DEBUG_PRINT1("'\n");
3089 /* This loops over pattern commands. It exits by returning from the
3090 * function if the match is complete, or it drops through if the match
3091 * fails at this starting point in the input data. */
3093 DEBUG_PRINT2("\n0x%x: ", p
);
3095 if (p
== pend
) { /* End of pattern means we might have succeeded. */
3096 DEBUG_PRINT1("end of pattern ... ");
3098 /* If we haven't matched the entire string, and we want the
3099 * longest match, try backtracking. */
3100 if (d
!= end_match_2
) {
3101 DEBUG_PRINT1("backtracking.\n");
3103 if (!FAIL_STACK_EMPTY()) { /* More failure points to try. */
3104 boolean same_str_p
= (FIRST_STRING_P(match_end
)
3105 == MATCHING_IN_FIRST_STRING
);
3107 /* If exceeds best match so far, save it. */
3109 || (same_str_p
&& d
> match_end
)
3110 || (!same_str_p
&& !MATCHING_IN_FIRST_STRING
)) {
3111 best_regs_set
= true;
3114 DEBUG_PRINT1("\nSAVING match as best so far.\n");
3116 for (mcnt
= 1; mcnt
< num_regs
; mcnt
++) {
3117 best_regstart
[mcnt
] = regstart
[mcnt
];
3118 best_regend
[mcnt
] = regend
[mcnt
];
3123 /* If no failure points, don't restore garbage. */
3124 else if (best_regs_set
) {
3126 /* Restore best match. It may happen that `dend ==
3127 * end_match_1' while the restored d is in string2.
3128 * For example, the pattern `x.*y.*z' against the
3129 * strings `x-' and `y-z-', if the two strings are
3130 * not consecutive in memory. */
3131 DEBUG_PRINT1("Restoring best registers.\n");
3134 dend
= ((d
>= string1
&& d
<= end1
)
3135 ? end_match_1
: end_match_2
);
3137 for (mcnt
= 1; mcnt
< num_regs
; mcnt
++) {
3138 regstart
[mcnt
] = best_regstart
[mcnt
];
3139 regend
[mcnt
] = best_regend
[mcnt
];
3142 } /* d != end_match_2 */
3143 DEBUG_PRINT1("Accepting match.\n");
3145 /* If caller wants register contents data back, do it. */
3146 if (regs
&& !bufp
->no_sub
) {
3147 /* Have the register data arrays been allocated? */
3148 if (bufp
->regs_allocated
== REGS_UNALLOCATED
) { /* No. So allocate them with malloc. We need one
3149 * extra element beyond `num_regs' for the `-1' marker
3151 regs
->num_regs
= MAX(RE_NREGS
, num_regs
+ 1);
3152 regs
->start
= TALLOC(regs
->num_regs
, regoff_t
);
3153 regs
->end
= TALLOC(regs
->num_regs
, regoff_t
);
3154 if (regs
->start
== NULL
|| regs
->end
== NULL
)
3156 bufp
->regs_allocated
= REGS_REALLOCATE
;
3157 } else if (bufp
->regs_allocated
== REGS_REALLOCATE
) { /* Yes. If we need more elements than were already
3158 * allocated, reallocate them. If we need fewer, just
3159 * leave it alone. */
3160 if (regs
->num_regs
< num_regs
+ 1) {
3161 regs
->num_regs
= num_regs
+ 1;
3162 RETALLOC(regs
->start
, regs
->num_regs
, regoff_t
);
3163 RETALLOC(regs
->end
, regs
->num_regs
, regoff_t
);
3164 if (regs
->start
== NULL
|| regs
->end
== NULL
)
3168 assert(bufp
->regs_allocated
== REGS_FIXED
);
3170 /* Convert the pointer data in `regstart' and `regend' to
3171 * indices. Register zero has to be set differently,
3172 * since we haven't kept track of any info for it. */
3173 if (regs
->num_regs
> 0) {
3174 regs
->start
[0] = pos
;
3175 regs
->end
[0] = (MATCHING_IN_FIRST_STRING
? d
- string1
3176 : d
- string2
+ size1
);
3178 /* Go through the first `min (num_regs, regs->num_regs)'
3179 * registers, since that is all we initialized. */
3180 for (mcnt
= 1; mcnt
< MIN(num_regs
, regs
->num_regs
); mcnt
++) {
3181 if (REG_UNSET(regstart
[mcnt
]) || REG_UNSET(regend
[mcnt
]))
3182 regs
->start
[mcnt
] = regs
->end
[mcnt
] = -1;
3184 regs
->start
[mcnt
] = POINTER_TO_OFFSET(regstart
[mcnt
]);
3185 regs
->end
[mcnt
] = POINTER_TO_OFFSET(regend
[mcnt
]);
3189 /* If the regs structure we return has more elements than
3190 * were in the pattern, set the extra elements to -1. If
3191 * we (re)allocated the registers, this is the case,
3192 * because we always allocate enough to have at least one
3194 for (mcnt
= num_regs
; mcnt
< regs
->num_regs
; mcnt
++)
3195 regs
->start
[mcnt
] = regs
->end
[mcnt
] = -1;
3196 } /* regs && !bufp->no_sub */
3198 DEBUG_PRINT4("%u failure points pushed, %u popped (%u remain).\n",
3199 nfailure_points_pushed
, nfailure_points_popped
,
3200 nfailure_points_pushed
- nfailure_points_popped
);
3201 DEBUG_PRINT2("%u registers pushed.\n", num_regs_pushed
);
3203 mcnt
= d
- pos
- (MATCHING_IN_FIRST_STRING
3207 DEBUG_PRINT2("Returning %d from re_match_2.\n", mcnt
);
3211 /* Otherwise match next pattern command. */
3212 #ifdef SWITCH_ENUM_BUG
3213 switch ((int) ((re_opcode_t
) * p
++))
3215 switch ((re_opcode_t
) * p
++)
3218 /* Ignore these. Used to ignore the n of succeed_n's which
3219 * currently have n == 0. */
3221 DEBUG_PRINT1("EXECUTING no_op.\n");
3225 /* Match the next n pattern characters exactly. The following
3226 * byte in the pattern defines n, and the n bytes after that
3227 * are the characters to match. */
3230 DEBUG_PRINT2("EXECUTING exactn %d.\n", mcnt
);
3232 /* This is written out as an if-else so we don't waste time
3233 * testing `translate' inside the loop. */
3237 if (translate
[(unsigned char) *d
++] != (char) *p
++)
3243 if (*d
++ != (char) *p
++)
3251 /* Match any character except possibly a newline or a null. */
3253 DEBUG_PRINT1("EXECUTING anychar.\n");
3257 if ((!(bufp
->syntax
& RE_DOT_NEWLINE
) && TRANSLATE(*d
) == '\n')
3258 || (bufp
->syntax
& RE_DOT_NOT_NULL
&& TRANSLATE(*d
) == '\000'))
3262 DEBUG_PRINT2(" Matched `%d'.\n", *d
);
3269 register unsigned char c
;
3270 boolean
not = (re_opcode_t
) * (p
- 1) == charset_not
;
3272 DEBUG_PRINT2("EXECUTING charset%s.\n", not ? "_not" : "");
3275 c
= TRANSLATE(*d
); /* The character to match. */
3277 /* Cast to `unsigned' instead of `unsigned char' in case the
3278 * bit list is a full 32 bytes long. */
3279 if (c
< (unsigned) (*p
* BYTEWIDTH
)
3280 && p
[1 + c
/ BYTEWIDTH
] & (1 << (c
% BYTEWIDTH
)))
3294 /* The beginning of a group is represented by start_memory.
3295 * The arguments are the register number in the next byte, and the
3296 * number of groups inner to this one in the next. The text
3297 * matched within the group is recorded (in the internal
3298 * registers data structure) under the register number. */
3300 DEBUG_PRINT3("EXECUTING start_memory %d (%d):\n", *p
, p
[1]);
3302 /* Find out if this group can match the empty string. */
3303 p1
= p
; /* To send to group_match_null_string_p. */
3305 if (REG_MATCH_NULL_STRING_P(reg_info
[*p
]) == MATCH_NULL_UNSET_VALUE
)
3306 REG_MATCH_NULL_STRING_P(reg_info
[*p
])
3307 = group_match_null_string_p(&p1
, pend
, reg_info
);
3309 /* Save the position in the string where we were the last time
3310 * we were at this open-group operator in case the group is
3311 * operated upon by a repetition operator, e.g., with `(a*)*b'
3312 * against `ab'; then we want to ignore where we are now in
3313 * the string in case this attempt to match fails. */
3314 old_regstart
[*p
] = REG_MATCH_NULL_STRING_P(reg_info
[*p
])
3315 ? REG_UNSET(regstart
[*p
]) ? d
: regstart
[*p
]
3317 DEBUG_PRINT2(" old_regstart: %d\n",
3318 POINTER_TO_OFFSET(old_regstart
[*p
]));
3321 DEBUG_PRINT2(" regstart: %d\n", POINTER_TO_OFFSET(regstart
[*p
]));
3323 IS_ACTIVE(reg_info
[*p
]) = 1;
3324 MATCHED_SOMETHING(reg_info
[*p
]) = 0;
3326 /* This is the new highest active register. */
3327 highest_active_reg
= *p
;
3329 /* If nothing was active before, this is the new lowest active
3331 if (lowest_active_reg
== NO_LOWEST_ACTIVE_REG
)
3332 lowest_active_reg
= *p
;
3334 /* Move past the register number and inner group count. */
3339 /* The stop_memory opcode represents the end of a group. Its
3340 * arguments are the same as start_memory's: the register
3341 * number, and the number of inner groups. */
3343 DEBUG_PRINT3("EXECUTING stop_memory %d (%d):\n", *p
, p
[1]);
3345 /* We need to save the string position the last time we were at
3346 * this close-group operator in case the group is operated
3347 * upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
3348 * against `aba'; then we want to ignore where we are now in
3349 * the string in case this attempt to match fails. */
3350 old_regend
[*p
] = REG_MATCH_NULL_STRING_P(reg_info
[*p
])
3351 ? REG_UNSET(regend
[*p
]) ? d
: regend
[*p
]
3353 DEBUG_PRINT2(" old_regend: %d\n",
3354 POINTER_TO_OFFSET(old_regend
[*p
]));
3357 DEBUG_PRINT2(" regend: %d\n", POINTER_TO_OFFSET(regend
[*p
]));
3359 /* This register isn't active anymore. */
3360 IS_ACTIVE(reg_info
[*p
]) = 0;
3362 /* If this was the only register active, nothing is active
3364 if (lowest_active_reg
== highest_active_reg
) {
3365 lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
3366 highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
3367 } else { /* We must scan for the new highest active register, since
3368 * it isn't necessarily one less than now: consider
3369 * (a(b)c(d(e)f)g). When group 3 ends, after the f), the
3370 * new highest active register is 1. */
3371 unsigned char r
= *p
- 1;
3372 while (r
> 0 && !IS_ACTIVE(reg_info
[r
]))
3375 /* If we end up at register zero, that means that we saved
3376 * the registers as the result of an `on_failure_jump', not
3377 * a `start_memory', and we jumped to past the innermost
3378 * `stop_memory'. For example, in ((.)*) we save
3379 * registers 1 and 2 as a result of the *, but when we pop
3380 * back to the second ), we are at the stop_memory 1.
3381 * Thus, nothing is active. */
3383 lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
3384 highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
3386 highest_active_reg
= r
;
3389 /* If just failed to match something this time around with a
3390 * group that's operated on by a repetition operator, try to
3391 * force exit from the ``loop'', and restore the register
3392 * information for this group that we had before trying this
3394 if ((!MATCHED_SOMETHING(reg_info
[*p
])
3395 || (re_opcode_t
) p
[-3] == start_memory
)
3396 && (p
+ 2) < pend
) {
3397 boolean is_a_jump_n
= false;
3401 switch ((re_opcode_t
) * p1
++) {
3404 case pop_failure_jump
:
3405 case maybe_pop_jump
:
3407 case dummy_failure_jump
:
3408 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
3419 /* If the next operation is a jump backwards in the pattern
3420 * to an on_failure_jump right before the start_memory
3421 * corresponding to this stop_memory, exit from the loop
3422 * by forcing a failure after pushing on the stack the
3423 * on_failure_jump's jump in the pattern, and d. */
3424 if (mcnt
< 0 && (re_opcode_t
) * p1
== on_failure_jump
3425 && (re_opcode_t
) p1
[3] == start_memory
&& p1
[4] == *p
) {
3426 /* If this group ever matched anything, then restore
3427 * what its registers were before trying this last
3428 * failed match, e.g., with `(a*)*b' against `ab' for
3429 * regstart[1], and, e.g., with `((a*)*(b*)*)*'
3430 * against `aba' for regend[3].
3432 * Also restore the registers for inner groups for,
3433 * e.g., `((a*)(b*))*' against `aba' (register 3 would
3434 * otherwise get trashed). */
3436 if (EVER_MATCHED_SOMETHING(reg_info
[*p
])) {
3439 EVER_MATCHED_SOMETHING(reg_info
[*p
]) = 0;
3441 /* Restore this and inner groups' (if any) registers. */
3442 for (r
= *p
; r
< *p
+ *(p
+ 1); r
++) {
3443 regstart
[r
] = old_regstart
[r
];
3445 /* xx why this test? */
3446 if ((long) old_regend
[r
] >= (long) regstart
[r
])
3447 regend
[r
] = old_regend
[r
];
3451 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
3452 PUSH_FAILURE_POINT(p1
+ mcnt
, d
, -2);
3457 /* Move past the register number and the inner group count. */
3462 /* \<digit> has been turned into a `duplicate' command which is
3463 * followed by the numeric value of <digit> as the register number. */
3465 register const char *d2
, *dend2
;
3466 int regno
= *p
++; /* Get which register to match against. */
3467 DEBUG_PRINT2("EXECUTING duplicate %d.\n", regno
);
3469 /* Can't back reference a group which we've never matched. */
3470 if (REG_UNSET(regstart
[regno
]) || REG_UNSET(regend
[regno
]))
3473 /* Where in input to try to start matching. */
3474 d2
= regstart
[regno
];
3476 /* Where to stop matching; if both the place to start and
3477 * the place to stop matching are in the same string, then
3478 * set to the place to stop, otherwise, for now have to use
3479 * the end of the first string. */
3481 dend2
= ((FIRST_STRING_P(regstart
[regno
])
3482 == FIRST_STRING_P(regend
[regno
]))
3483 ? regend
[regno
] : end_match_1
);
3485 /* If necessary, advance to next segment in register
3487 while (d2
== dend2
) {
3488 if (dend2
== end_match_2
)
3490 if (dend2
== regend
[regno
])
3493 /* End of string1 => advance to string2. */
3495 dend2
= regend
[regno
];
3497 /* At end of register contents => success */
3501 /* If necessary, advance to next segment in data. */
3504 /* How many characters left in this segment to match. */
3507 /* Want how many consecutive characters we can match in
3508 * one shot, so, if necessary, adjust the count. */
3509 if (mcnt
> dend2
- d2
)
3512 /* Compare that many; failure if mismatch, else move
3515 ? bcmp_translate((unsigned char *)d
, (unsigned char *)d2
, mcnt
, translate
)
3516 : memcmp(d
, d2
, mcnt
))
3518 d
+= mcnt
, d2
+= mcnt
;
3524 /* begline matches the empty string at the beginning of the string
3525 * (unless `not_bol' is set in `bufp'), and, if
3526 * `newline_anchor' is set, after newlines. */
3528 DEBUG_PRINT1("EXECUTING begline.\n");
3530 if (AT_STRINGS_BEG(d
)) {
3533 } else if (d
[-1] == '\n' && bufp
->newline_anchor
) {
3536 /* In all other cases, we fail. */
3540 /* endline is the dual of begline. */
3542 DEBUG_PRINT1("EXECUTING endline.\n");
3544 if (AT_STRINGS_END(d
)) {
3548 /* We have to ``prefetch'' the next character. */
3549 else if ((d
== end1
? *string2
: *d
) == '\n'
3550 && bufp
->newline_anchor
) {
3556 /* Match at the very beginning of the data. */
3558 DEBUG_PRINT1("EXECUTING begbuf.\n");
3559 if (AT_STRINGS_BEG(d
))
3564 /* Match at the very end of the data. */
3566 DEBUG_PRINT1("EXECUTING endbuf.\n");
3567 if (AT_STRINGS_END(d
))
3572 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
3573 * pushes NULL as the value for the string on the stack. Then
3574 * `pop_failure_point' will keep the current value for the
3575 * string, instead of restoring it. To see why, consider
3576 * matching `foo\nbar' against `.*\n'. The .* matches the foo;
3577 * then the . fails against the \n. But the next thing we want
3578 * to do is match the \n against the \n; if we restored the
3579 * string value, we would be back at the foo.
3581 * Because this is used only in specific cases, we don't need to
3582 * check all the things that `on_failure_jump' does, to make
3583 * sure the right things get saved on the stack. Hence we don't
3584 * share its code. The only reason to push anything on the
3585 * stack at all is that otherwise we would have to change
3586 * `anychar's code to do something besides goto fail in this
3587 * case; that seems worse than this. */
3588 case on_failure_keep_string_jump
:
3589 DEBUG_PRINT1("EXECUTING on_failure_keep_string_jump");
3591 EXTRACT_NUMBER_AND_INCR(mcnt
, p
);
3592 DEBUG_PRINT3(" %d (to 0x%x):\n", mcnt
, p
+ mcnt
);
3594 PUSH_FAILURE_POINT(p
+ mcnt
, NULL
, -2);
3598 /* Uses of on_failure_jump:
3600 * Each alternative starts with an on_failure_jump that points
3601 * to the beginning of the next alternative. Each alternative
3602 * except the last ends with a jump that in effect jumps past
3603 * the rest of the alternatives. (They really jump to the
3604 * ending jump of the following alternative, because tensioning
3605 * these jumps is a hassle.)
3607 * Repeats start with an on_failure_jump that points past both
3608 * the repetition text and either the following jump or
3609 * pop_failure_jump back to this on_failure_jump. */
3610 case on_failure_jump
:
3612 DEBUG_PRINT1("EXECUTING on_failure_jump");
3614 EXTRACT_NUMBER_AND_INCR(mcnt
, p
);
3615 DEBUG_PRINT3(" %d (to 0x%x)", mcnt
, p
+ mcnt
);
3617 /* If this on_failure_jump comes right before a group (i.e.,
3618 * the original * applied to a group), save the information
3619 * for that group and all inner ones, so that if we fail back
3620 * to this point, the group's information will be correct.
3621 * For example, in \(a*\)*\1, we need the preceding group,
3622 * and in \(\(a*\)b*\)\2, we need the inner group. */
3624 /* We can't use `p' to check ahead because we push
3625 * a failure point to `p + mcnt' after we do this. */
3628 /* We need to skip no_op's before we look for the
3629 * start_memory in case this on_failure_jump is happening as
3630 * the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
3632 while (p1
< pend
&& (re_opcode_t
) * p1
== no_op
)
3635 if (p1
< pend
&& (re_opcode_t
) * p1
== start_memory
) {
3636 /* We have a new highest active register now. This will
3637 * get reset at the start_memory we are about to get to,
3638 * but we will have saved all the registers relevant to
3639 * this repetition op, as described above. */
3640 highest_active_reg
= *(p1
+ 1) + *(p1
+ 2);
3641 if (lowest_active_reg
== NO_LOWEST_ACTIVE_REG
)
3642 lowest_active_reg
= *(p1
+ 1);
3644 DEBUG_PRINT1(":\n");
3645 PUSH_FAILURE_POINT(p
+ mcnt
, d
, -2);
3649 /* A smart repeat ends with `maybe_pop_jump'.
3650 * We change it to either `pop_failure_jump' or `jump'. */
3651 case maybe_pop_jump
:
3652 EXTRACT_NUMBER_AND_INCR(mcnt
, p
);
3653 DEBUG_PRINT2("EXECUTING maybe_pop_jump %d.\n", mcnt
);
3655 register unsigned char *p2
= p
;
3657 /* Compare the beginning of the repeat with what in the
3658 * pattern follows its end. If we can establish that there
3659 * is nothing that they would both match, i.e., that we
3660 * would have to backtrack because of (as in, e.g., `a*a')
3661 * then we can change to pop_failure_jump, because we'll
3662 * never have to backtrack.
3664 * This is not true in the case of alternatives: in
3665 * `(a|ab)*' we do need to backtrack to the `ab' alternative
3666 * (e.g., if the string was `ab'). But instead of trying to
3667 * detect that here, the alternative has put on a dummy
3668 * failure point which is what we will end up popping. */
3670 /* Skip over open/close-group commands. */
3671 while (p2
+ 2 < pend
3672 && ((re_opcode_t
) * p2
== stop_memory
3673 || (re_opcode_t
) * p2
== start_memory
))
3674 p2
+= 3; /* Skip over args, too. */
3676 /* If we're at the end of the pattern, we can change. */
3678 /* Consider what happens when matching ":\(.*\)"
3679 * against ":/". I don't really understand this code
3681 p
[-3] = (unsigned char) pop_failure_jump
;
3683 (" End of pattern: change to `pop_failure_jump'.\n");
3684 } else if ((re_opcode_t
) * p2
== exactn
3685 || (bufp
->newline_anchor
&& (re_opcode_t
) * p2
== endline
)) {
3686 register unsigned char c
3687 = *p2
== (unsigned char) endline
? '\n' : p2
[2];
3690 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
3691 * to the `maybe_finalize_jump' of this case. Examine what
3693 if ((re_opcode_t
) p1
[3] == exactn
&& p1
[5] != c
) {
3694 p
[-3] = (unsigned char) pop_failure_jump
;
3695 DEBUG_PRINT3(" %c != %c => pop_failure_jump.\n",
3697 } else if ((re_opcode_t
) p1
[3] == charset
3698 || (re_opcode_t
) p1
[3] == charset_not
) {
3699 int not = (re_opcode_t
) p1
[3] == charset_not
;
3701 if (c
< (unsigned char) (p1
[4] * BYTEWIDTH
)
3702 && p1
[5 + c
/ BYTEWIDTH
] & (1 << (c
% BYTEWIDTH
)))
3705 /* `not' is equal to 1 if c would match, which means
3706 * that we can't change to pop_failure_jump. */
3708 p
[-3] = (unsigned char) pop_failure_jump
;
3709 DEBUG_PRINT1(" No match => pop_failure_jump.\n");
3714 p
-= 2; /* Point at relative address again. */
3715 if ((re_opcode_t
) p
[-1] != pop_failure_jump
) {
3716 p
[-1] = (unsigned char) jump
;
3717 DEBUG_PRINT1(" Match => jump.\n");
3718 goto unconditional_jump
;
3720 /* Note fall through. */
3723 /* The end of a simple repeat has a pop_failure_jump back to
3724 * its matching on_failure_jump, where the latter will push a
3725 * failure point. The pop_failure_jump takes off failure
3726 * points put on by this pop_failure_jump's matching
3727 * on_failure_jump; we got through the pattern to here from the
3728 * matching on_failure_jump, so didn't fail. */
3729 case pop_failure_jump
: {
3730 /* We need to pass separate storage for the lowest and
3731 * highest registers, even though we don't care about the
3732 * actual values. Otherwise, we will restore only one
3733 * register from the stack, since lowest will == highest in
3734 * `pop_failure_point'. */
3735 unsigned long dummy_low_reg
, dummy_high_reg
;
3736 unsigned char *pdummy
;
3739 DEBUG_PRINT1("EXECUTING pop_failure_jump.\n");
3740 POP_FAILURE_POINT(sdummy
, pdummy
,
3741 dummy_low_reg
, dummy_high_reg
,
3742 reg_dummy
, reg_dummy
, reg_info_dummy
);
3744 /* Note fall through. */
3747 /* Unconditionally jump (without popping any failure points). */
3750 EXTRACT_NUMBER_AND_INCR(mcnt
, p
); /* Get the amount to jump. */
3751 DEBUG_PRINT2("EXECUTING jump %d ", mcnt
);
3752 p
+= mcnt
; /* Do the jump. */
3753 DEBUG_PRINT2("(to 0x%x).\n", p
);
3757 /* We need this opcode so we can detect where alternatives end
3758 * in `group_match_null_string_p' et al. */
3760 DEBUG_PRINT1("EXECUTING jump_past_alt.\n");
3761 goto unconditional_jump
;
3764 /* Normally, the on_failure_jump pushes a failure point, which
3765 * then gets popped at pop_failure_jump. We will end up at
3766 * pop_failure_jump, also, and with a pattern of, say, `a+', we
3767 * are skipping over the on_failure_jump, so we have to push
3768 * something meaningless for pop_failure_jump to pop. */
3769 case dummy_failure_jump
:
3770 DEBUG_PRINT1("EXECUTING dummy_failure_jump.\n");
3771 /* It doesn't matter what we push for the string here. What
3772 * the code at `fail' tests is the value for the pattern. */
3773 PUSH_FAILURE_POINT(0, 0, -2);
3774 goto unconditional_jump
;
3777 /* At the end of an alternative, we need to push a dummy failure
3778 * point in case we are followed by a `pop_failure_jump', because
3779 * we don't want the failure point for the alternative to be
3780 * popped. For example, matching `(a|ab)*' against `aab'
3781 * requires that we match the `ab' alternative. */
3782 case push_dummy_failure
:
3783 DEBUG_PRINT1("EXECUTING push_dummy_failure.\n");
3784 /* See comments just above at `dummy_failure_jump' about the
3786 PUSH_FAILURE_POINT(0, 0, -2);
3789 /* Have to succeed matching what follows at least n times.
3790 * After that, handle like `on_failure_jump'. */
3792 EXTRACT_NUMBER(mcnt
, p
+ 2);
3793 DEBUG_PRINT2("EXECUTING succeed_n %d.\n", mcnt
);
3796 /* Originally, this is how many times we HAVE to succeed. */
3800 STORE_NUMBER_AND_INCR(p
, mcnt
);
3801 DEBUG_PRINT3(" Setting 0x%x to %d.\n", p
, mcnt
);
3802 } else if (mcnt
== 0) {
3803 DEBUG_PRINT2(" Setting two bytes from 0x%x to no_op.\n", p
+ 2);
3804 p
[2] = (unsigned char) no_op
;
3805 p
[3] = (unsigned char) no_op
;
3811 EXTRACT_NUMBER(mcnt
, p
+ 2);
3812 DEBUG_PRINT2("EXECUTING jump_n %d.\n", mcnt
);
3814 /* Originally, this is how many times we CAN jump. */
3817 STORE_NUMBER(p
+ 2, mcnt
);
3818 goto unconditional_jump
;
3820 /* If don't have to jump any more, skip over the rest of command. */
3825 case set_number_at
: {
3826 DEBUG_PRINT1("EXECUTING set_number_at.\n");
3828 EXTRACT_NUMBER_AND_INCR(mcnt
, p
);
3830 EXTRACT_NUMBER_AND_INCR(mcnt
, p
);
3831 DEBUG_PRINT3(" Setting 0x%x to %d.\n", p1
, mcnt
);
3832 STORE_NUMBER(p1
, mcnt
);
3837 DEBUG_PRINT1("EXECUTING wordbound.\n");
3838 if (AT_WORD_BOUNDARY(d
))
3843 DEBUG_PRINT1("EXECUTING notwordbound.\n");
3844 if (AT_WORD_BOUNDARY(d
))
3849 DEBUG_PRINT1("EXECUTING wordbeg.\n");
3850 if (WORDCHAR_P(d
) && (AT_STRINGS_BEG(d
) || !WORDCHAR_P(d
- 1)))
3855 DEBUG_PRINT1("EXECUTING wordend.\n");
3856 if (!AT_STRINGS_BEG(d
) && WORDCHAR_P(d
- 1)
3857 && (!WORDCHAR_P(d
) || AT_STRINGS_END(d
)))
3862 DEBUG_PRINT1("EXECUTING non-Emacs wordchar.\n");
3871 DEBUG_PRINT1("EXECUTING non-Emacs notwordchar.\n");
3882 continue; /* Successfully executed one pattern command; keep going. */
3885 /* We goto here if a matching operation fails. */
3887 if (!FAIL_STACK_EMPTY()) { /* A restart point is known. Restore to that state. */
3888 DEBUG_PRINT1("\nFAIL:\n");
3889 POP_FAILURE_POINT(d
, p
,
3890 lowest_active_reg
, highest_active_reg
,
3891 regstart
, regend
, reg_info
);
3893 /* If this failure point is a dummy, try the next one. */
3897 /* If we failed to the end of the pattern, don't examine *p. */
3900 boolean is_a_jump_n
= false;
3902 /* If failed to a backwards jump that's part of a repetition
3903 * loop, need to pop this failure point and use the next one. */
3904 switch ((re_opcode_t
) * p
) {
3907 case maybe_pop_jump
:
3908 case pop_failure_jump
:
3911 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
3914 if ((is_a_jump_n
&& (re_opcode_t
) * p1
== succeed_n
)
3916 && (re_opcode_t
) * p1
== on_failure_jump
))
3924 if (d
>= string1
&& d
<= end1
)
3927 break; /* Matching at this starting point really fails. */
3931 goto restore_best_regs
;
3935 return -1; /* Failure to match. */
3938 /* Subroutine definitions for re_match_2. */
3940 /* We are passed P pointing to a register number after a start_memory.
3942 * Return true if the pattern up to the corresponding stop_memory can
3943 * match the empty string, and false otherwise.
3945 * If we find the matching stop_memory, sets P to point to one past its number.
3946 * Otherwise, sets P to an undefined byte less than or equal to END.
3948 * We don't handle duplicates properly (yet). */
3951 group_match_null_string_p(unsigned char **p
, unsigned char *end
, register_info_type
*reg_info
)
3954 /* Point to after the args to the start_memory. */
3955 unsigned char *p1
= *p
+ 2;
3958 /* Skip over opcodes that can match nothing, and return true or
3959 * false, as appropriate, when we get to one that can't, or to the
3960 * matching stop_memory. */
3962 switch ((re_opcode_t
) * p1
) {
3963 /* Could be either a loop or a series of alternatives. */
3964 case on_failure_jump
:
3966 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
3968 /* If the next operation is not a jump backwards in the
3972 /* Go through the on_failure_jumps of the alternatives,
3973 * seeing if any of the alternatives cannot match nothing.
3974 * The last alternative starts with only a jump,
3975 * whereas the rest start with on_failure_jump and end
3976 * with a jump, e.g., here is the pattern for `a|b|c':
3978 * /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
3979 * /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
3982 * So, we have to first go through the first (n-1)
3983 * alternatives and then deal with the last one separately. */
3986 /* Deal with the first (n-1) alternatives, which start
3987 * with an on_failure_jump (see above) that jumps to right
3988 * past a jump_past_alt. */
3990 while ((re_opcode_t
) p1
[mcnt
- 3] == jump_past_alt
) {
3991 /* `mcnt' holds how many bytes long the alternative
3992 * is, including the ending `jump_past_alt' and
3995 if (!alt_match_null_string_p(p1
, p1
+ mcnt
- 3,
3999 /* Move to right after this alternative, including the
4003 /* Break if it's the beginning of an n-th alternative
4004 * that doesn't begin with an on_failure_jump. */
4005 if ((re_opcode_t
) * p1
!= on_failure_jump
)
4008 /* Still have to check that it's not an n-th
4009 * alternative that starts with an on_failure_jump. */
4011 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
4012 if ((re_opcode_t
) p1
[mcnt
- 3] != jump_past_alt
) {
4013 /* Get to the beginning of the n-th alternative. */
4019 /* Deal with the last alternative: go back and get number
4020 * of the `jump_past_alt' just before it. `mcnt' contains
4021 * the length of the alternative. */
4022 EXTRACT_NUMBER(mcnt
, p1
- 2);
4024 if (!alt_match_null_string_p(p1
, p1
+ mcnt
, reg_info
))
4027 p1
+= mcnt
; /* Get past the n-th alternative. */
4033 assert(p1
[1] == **p
);
4039 if (!common_op_match_null_string_p(&p1
, end
, reg_info
))
4042 } /* while p1 < end */
4045 } /* group_match_null_string_p */
4048 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
4049 * It expects P to be the first byte of a single alternative and END one
4050 * byte past the last. The alternative can contain groups. */
4053 alt_match_null_string_p(unsigned char *p
, unsigned char *end
, register_info_type
*reg_info
)
4056 unsigned char *p1
= p
;
4059 /* Skip over opcodes that can match nothing, and break when we get
4060 * to one that can't. */
4062 switch ((re_opcode_t
) * p1
) {
4064 case on_failure_jump
:
4066 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
4071 if (!common_op_match_null_string_p(&p1
, end
, reg_info
))
4074 } /* while p1 < end */
4077 } /* alt_match_null_string_p */
4080 /* Deals with the ops common to group_match_null_string_p and
4081 * alt_match_null_string_p.
4083 * Sets P to one after the op and its arguments, if any. */
4086 common_op_match_null_string_p( unsigned char **p
, unsigned char *end
, register_info_type
*reg_info
)
4091 unsigned char *p1
= *p
;
4093 switch ((re_opcode_t
) * p1
++) {
4107 assert(reg_no
> 0 && reg_no
<= MAX_REGNUM
);
4108 ret
= group_match_null_string_p(&p1
, end
, reg_info
);
4110 /* Have to set this here in case we're checking a group which
4111 * contains a group and a back reference to it. */
4113 if (REG_MATCH_NULL_STRING_P(reg_info
[reg_no
]) == MATCH_NULL_UNSET_VALUE
)
4114 REG_MATCH_NULL_STRING_P(reg_info
[reg_no
]) = ret
;
4120 /* If this is an optimized succeed_n for zero times, make the jump. */
4122 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
4130 /* Get to the number of times to succeed. */
4132 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
4136 EXTRACT_NUMBER_AND_INCR(mcnt
, p1
);
4143 if (!REG_MATCH_NULL_STRING_P(reg_info
[*p1
]))
4151 /* All other opcodes mean we cannot match the empty string. */
4157 } /* common_op_match_null_string_p */
4160 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
4161 * bytes; nonzero otherwise. */
4164 bcmp_translate(unsigned char const *s1
, unsigned char const*s2
, register int len
, char *translate
)
4166 register unsigned char const *p1
= s1
, *p2
= s2
;
4168 if (translate
[*p1
++] != translate
[*p2
++])
4175 /* Entry points for GNU code. */
4178 /* POSIX.2 functions */
4180 /* regcomp takes a regular expression as a string and compiles it.
4182 * PREG is a regex_t *. We do not expect any fields to be initialized,
4183 * since POSIX says we shouldn't. Thus, we set
4185 * `buffer' to the compiled pattern;
4186 * `used' to the length of the compiled pattern;
4187 * `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
4188 * REG_EXTENDED bit in CFLAGS is set; otherwise, to
4189 * RE_SYNTAX_POSIX_BASIC;
4190 * `newline_anchor' to REG_NEWLINE being set in CFLAGS;
4191 * `fastmap' and `fastmap_accurate' to zero;
4192 * `re_nsub' to the number of subexpressions in PATTERN.
4194 * PATTERN is the address of the pattern string.
4196 * CFLAGS is a series of bits which affect compilation.
4198 * If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
4199 * use POSIX basic syntax.
4201 * If REG_NEWLINE is set, then . and [^...] don't match newline.
4202 * Also, regexec will try a match beginning after every newline.
4204 * If REG_ICASE is set, then we considers upper- and lowercase
4205 * versions of letters to be equivalent when matching.
4207 * If REG_NOSUB is set, then when PREG is passed to regexec, that
4208 * routine will report only success or failure, and nothing about the
4211 * It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
4212 * the return codes and their meanings.) */
4215 regcomp(preg
, pattern
, cflags
)
4217 const char *pattern
;
4222 = (cflags
& REG_EXTENDED
) ?
4223 RE_SYNTAX_POSIX_EXTENDED
: RE_SYNTAX_POSIX_BASIC
;
4225 /* regex_compile will allocate the space for the compiled pattern. */
4227 preg
->allocated
= 0;
4229 /* Don't bother to use a fastmap when searching. This simplifies the
4230 * REG_NEWLINE case: if we used a fastmap, we'd have to put all the
4231 * characters after newlines into the fastmap. This way, we just try
4232 * every character. */
4235 if (cflags
& REG_ICASE
) {
4238 preg
->translate
= (char *) malloc(CHAR_SET_SIZE
);
4239 if (preg
->translate
== NULL
)
4240 return (int) REG_ESPACE
;
4242 /* Map uppercase characters to corresponding lowercase ones. */
4243 for (i
= 0; i
< CHAR_SET_SIZE
; i
++)
4244 preg
->translate
[i
] = ISUPPER(i
) ? tolower(i
) : i
;
4246 preg
->translate
= NULL
;
4248 /* If REG_NEWLINE is set, newlines are treated differently. */
4249 if (cflags
& REG_NEWLINE
) { /* REG_NEWLINE implies neither . nor [^...] match newline. */
4250 syntax
&= ~RE_DOT_NEWLINE
;
4251 syntax
|= RE_HAT_LISTS_NOT_NEWLINE
;
4252 /* It also changes the matching behavior. */
4253 preg
->newline_anchor
= 1;
4255 preg
->newline_anchor
= 0;
4257 preg
->no_sub
= !!(cflags
& REG_NOSUB
);
4259 /* POSIX says a null character in the pattern terminates it, so we
4260 * can use strlen here in compiling the pattern. */
4261 ret
= regex_compile(pattern
, strlen(pattern
), syntax
, preg
);
4263 /* POSIX doesn't distinguish between an unmatched open-group and an
4264 * unmatched close-group: both are REG_EPAREN. */
4265 if (ret
== REG_ERPAREN
)
4272 /* regexec searches for a given pattern, specified by PREG, in the
4275 * If NMATCH is zero or REG_NOSUB was set in the cflags argument to
4276 * `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
4277 * least NMATCH elements, and we set them to the offsets of the
4278 * corresponding matched substrings.
4280 * EFLAGS specifies `execution flags' which affect matching: if
4281 * REG_NOTBOL is set, then ^ does not match at the beginning of the
4282 * string; if REG_NOTEOL is set, then $ does not match at the end.
4284 * We return 0 if we find a match and REG_NOMATCH if not. */
4287 regexec(preg
, string
, nmatch
, pmatch
, eflags
)
4288 const regex_t
*preg
;
4291 regmatch_t pmatch
[];
4295 struct re_registers regs
;
4296 regex_t private_preg
;
4297 int len
= strlen(string
);
4298 boolean want_reg_info
= !preg
->no_sub
&& nmatch
> 0;
4300 private_preg
= *preg
;
4302 private_preg
.not_bol
= !!(eflags
& REG_NOTBOL
);
4303 private_preg
.not_eol
= !!(eflags
& REG_NOTEOL
);
4305 /* The user has told us exactly how many registers to return
4306 * information about, via `nmatch'. We have to pass that on to the
4307 * matching routines. */
4308 private_preg
.regs_allocated
= REGS_FIXED
;
4310 if (want_reg_info
) {
4311 regs
.num_regs
= nmatch
;
4312 regs
.start
= TALLOC(nmatch
, regoff_t
);
4313 regs
.end
= TALLOC(nmatch
, regoff_t
);
4314 if (regs
.start
== NULL
|| regs
.end
== NULL
)
4315 return (int) REG_NOMATCH
;
4317 /* Perform the searching operation. */
4318 ret
= re_search(&private_preg
, string
, len
,
4319 /* start: */ 0, /* range: */ len
,
4320 want_reg_info
? ®s
: (struct re_registers
*) 0);
4322 /* Copy the register information to the POSIX structure. */
4323 if (want_reg_info
) {
4327 for (r
= 0; r
< nmatch
; r
++) {
4328 pmatch
[r
].rm_so
= regs
.start
[r
];
4329 pmatch
[r
].rm_eo
= regs
.end
[r
];
4332 /* If we needed the temporary register info, free the space now. */
4336 /* We want zero return to mean success, unlike `re_search'. */
4337 return ret
>= 0 ? (int) REG_NOERROR
: (int) REG_NOMATCH
;
4341 /* Returns a message corresponding to an error code, ERRCODE, returned
4342 * from either regcomp or regexec. We don't use PREG here. */
4345 regerror(int errcode
, const regex_t
*preg
, char *errbuf
, size_t errbuf_size
)
4351 || errcode
>= (sizeof(re_error_msg
) / sizeof(re_error_msg
[0])))
4352 /* Only error codes returned by the rest of the code should be passed
4353 * to this routine. If we are given anything else, or if other regex
4354 * code generates an invalid error code, then the program has a bug.
4355 * Dump core so we can fix it. */
4358 msg
= re_error_msg
[errcode
];
4360 /* POSIX doesn't require that we do anything in this case, but why
4365 msg_size
= strlen(msg
) + 1; /* Includes the null. */
4367 if (errbuf_size
!= 0) {
4368 if (msg_size
> errbuf_size
) {
4369 strncpy(errbuf
, msg
, errbuf_size
- 1);
4370 errbuf
[errbuf_size
- 1] = 0;
4372 strcpy(errbuf
, msg
);
4378 /* Free dynamically allocated space used by PREG. */
4384 if (preg
->buffer
!= NULL
)
4386 preg
->buffer
= NULL
;
4388 preg
->allocated
= 0;
4391 if (preg
->fastmap
!= NULL
)
4392 free(preg
->fastmap
);
4393 preg
->fastmap
= NULL
;
4394 preg
->fastmap_accurate
= 0;
4396 if (preg
->translate
!= NULL
)
4397 free(preg
->translate
);
4398 preg
->translate
= NULL
;
4400 #endif /* USE_GNUREGEX */
4404 * make-backup-files: t
4405 * version-control: t
4406 * trim-versions-without-asking: nil