1 /* Extended regular expression matching and search library,
3 (Implements POSIX draft P10003.2/D11.2, except for
4 internationalization features.)
6 Copyright (C) 1985, 89, 90, 91, 92 Free Software Foundation, Inc.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
22 /* AIX requires this to be the first thing in the file. */
23 #if defined (_AIX) && !defined (REGEX_MALLOC)
29 /* We need this for `regex.h', and perhaps for the Emacs include files. */
30 #include <sys/types.h>
32 /* The `emacs' switch turns on certain matching commands
33 that make sense only in Emacs. */
41 /* Emacs uses `NULL' as a predicate. */
46 /* We used to test for `BSTRING' here, but only GCC and Emacs define
47 `BSTRING', as far as I know, and neither of them use this code. */
48 #if USG || STDC_HEADERS
50 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
51 #define bcopy(s, d, n) memcpy ((d), (s), (n))
52 #define bzero(s, n) memset ((s), 0, (n))
65 /* Define the syntax stuff for \<, \>, etc. */
67 /* This must be nonzero for the wordchar and notwordchar pattern
68 commands in re_match_2. */
75 extern char *re_syntax_table;
77 #else /* not SYNTAX_TABLE */
79 /* How many characters in the character set. */
80 #define CHAR_SET_SIZE 256
82 static char re_syntax_table[CHAR_SET_SIZE];
93 bzero (re_syntax_table, sizeof re_syntax_table);
95 for (c = 'a'; c <= 'z'; c++)
96 re_syntax_table[c] = Sword;
98 for (c = 'A'; c <= 'Z'; c++)
99 re_syntax_table[c] = Sword;
101 for (c = '0'; c <= '9'; c++)
102 re_syntax_table[c] = Sword;
104 re_syntax_table['_'] = Sword;
109 #endif /* not SYNTAX_TABLE */
111 #define SYNTAX(c) re_syntax_table[c]
113 #endif /* not emacs */
115 /* Get the interface, including the syntax bits. */
119 /* isalpha etc. are used for the character classes. */
122 #define isgraph(c) (isprint (c) && !isspace (c))
125 #define isblank(c) ((c) == ' ' || (c) == '\t')
132 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
133 since ours (we hope) works properly with all combinations of
134 machines, compilers, `char' and `unsigned char' argument types.
135 (Per Bothner suggested the basic approach.) */
136 #undef SIGN_EXTEND_CHAR
139 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
140 #else /* On VMS, VAXC doesn't recognize `signed' before `char' */
141 #define SIGN_EXTEND_CHAR(c) ((char) (c))
144 /* As in Harbison and Steele. */
145 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
148 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
149 use `alloca' instead of `malloc'. This is because using malloc in
150 re_search* or re_match* could cause memory leaks when C-g is used in
151 Emacs; also, malloc is slower and causes storage fragmentation. On
152 the other hand, malloc is more portable, and easier to debug.
154 Because we sometimes use alloca, some routines have to be macros,
155 not functions -- `alloca'-allocated space disappears at the end of the
156 function it is called in. */
160 #define REGEX_ALLOCATE malloc
161 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
163 #else /* not REGEX_MALLOC */
165 /* Emacs already defines alloca, sometimes. */
168 /* Make alloca work the best possible way. */
170 #define alloca __builtin_alloca
171 #else /* not __GNUC__ */
174 #else /* not __GNUC__ or HAVE_ALLOCA_H */
175 #ifndef _AIX /* Already did AIX, up at the top. */
177 #endif /* not _AIX */
178 #endif /* not HAVE_ALLOCA_H */
179 #endif /* not __GNUC__ */
181 #endif /* not alloca */
183 #define REGEX_ALLOCATE alloca
185 /* Assumes a `char *destination' variable. */
186 #define REGEX_REALLOCATE(source, osize, nsize) \
187 (destination = (char *) alloca (nsize), \
188 bcopy (source, destination, osize), \
191 #endif /* not REGEX_MALLOC */
194 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
195 `string1' or just past its end. This works if PTR is NULL, which is
197 #define FIRST_STRING_P(ptr) \
198 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
200 /* (Re)Allocate N items of type T using malloc, or fail. */
201 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
202 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
203 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
205 #define BYTEWIDTH 8 /* In bits. */
207 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
209 #define MAX(a, b) ((a) > (b) ? (a) : (b))
210 #define MIN(a, b) ((a) < (b) ? (a) : (b))
212 typedef char boolean;
216 /* These are the command codes that appear in compiled regular
217 expressions. Some opcodes are followed by argument bytes. A
218 command code can specify any interpretation whatsoever for its
219 arguments. Zero bytes may appear in the compiled regular expression.
221 The value of `exactn' is needed in search.c (search_buffer) in Emacs.
222 So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
223 `exactn' we use here must also be 1. */
229 /* Followed by one byte giving n, then by n literal bytes. */
232 /* Matches any (more or less) character. */
235 /* Matches any one char belonging to specified set. First
236 following byte is number of bitmap bytes. Then come bytes
237 for a bitmap saying which chars are in. Bits in each byte
238 are ordered low-bit-first. A character is in the set if its
239 bit is 1. A character too large to have a bit in the map is
240 automatically not in the set. */
243 /* Same parameters as charset, but match any character that is
244 not one of those specified. */
247 /* Start remembering the text that is matched, for storing in a
248 register. Followed by one byte with the register number, in
249 the range 0 to one less than the pattern buffer's re_nsub
250 field. Then followed by one byte with the number of groups
251 inner to this one. (This last has to be part of the
252 start_memory only because we need it in the on_failure_jump
256 /* Stop remembering the text that is matched and store it in a
257 memory register. Followed by one byte with the register
258 number, in the range 0 to one less than `re_nsub' in the
259 pattern buffer, and one byte with the number of inner groups,
260 just like `start_memory'. (We need the number of inner
261 groups here because we don't have any easy way of finding the
262 corresponding start_memory when we're at a stop_memory.) */
265 /* Match a duplicate of something remembered. Followed by one
266 byte containing the register number. */
269 /* Fail unless at beginning of line. */
272 /* Fail unless at end of line. */
275 /* Succeeds if at beginning of buffer (if emacs) or at beginning
276 of string to be matched (if not). */
279 /* Analogously, for end of buffer/string. */
282 /* Followed by two byte relative address to which to jump. */
285 /* Same as jump, but marks the end of an alternative. */
288 /* Followed by two-byte relative address of place to resume at
289 in case of failure. */
292 /* Like on_failure_jump, but pushes a placeholder instead of the
293 current string position when executed. */
294 on_failure_keep_string_jump,
296 /* Throw away latest failure point and then jump to following
297 two-byte relative address. */
300 /* Change to pop_failure_jump if know won't have to backtrack to
301 match; otherwise change to jump. This is used to jump
302 back to the beginning of a repeat. If what follows this jump
303 clearly won't match what the repeat does, such that we can be
304 sure that there is no use backtracking out of repetitions
305 already matched, then we change it to a pop_failure_jump.
306 Followed by two-byte address. */
309 /* Jump to following two-byte address, and push a dummy failure
310 point. This failure point will be thrown away if an attempt
311 is made to use it for a failure. A `+' construct makes this
312 before the first repeat. Also used as an intermediary kind
313 of jump when compiling an alternative. */
316 /* Push a dummy failure point and continue. Used at the end of
320 /* Followed by two-byte relative address and two-byte number n.
321 After matching N times, jump to the address upon failure. */
324 /* Followed by two-byte relative address, and two-byte number n.
325 Jump to the address N times, then fail. */
328 /* Set the following two-byte relative address to the
329 subsequent two-byte number. The address *includes* the two
333 wordchar, /* Matches any word-constituent character. */
334 notwordchar, /* Matches any char that is not a word-constituent. */
336 wordbeg, /* Succeeds if at word beginning. */
337 wordend, /* Succeeds if at word end. */
339 wordbound, /* Succeeds if at a word boundary. */
340 notwordbound /* Succeeds if not at a word boundary. */
343 ,before_dot, /* Succeeds if before point. */
344 at_dot, /* Succeeds if at point. */
345 after_dot, /* Succeeds if after point. */
347 /* Matches any character whose syntax is specified. Followed by
348 a byte which contains a syntax code, e.g., Sword. */
351 /* Matches any character whose syntax is not that specified. */
356 /* Common operations on the compiled pattern. */
358 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
360 #define STORE_NUMBER(destination, number) \
362 (destination)[0] = (number) & 0377; \
363 (destination)[1] = (number) >> 8; \
366 /* Same as STORE_NUMBER, except increment DESTINATION to
367 the byte after where the number is stored. Therefore, DESTINATION
368 must be an lvalue. */
370 #define STORE_NUMBER_AND_INCR(destination, number) \
372 STORE_NUMBER (destination, number); \
373 (destination) += 2; \
376 /* Put into DESTINATION a number stored in two contiguous bytes starting
379 #define EXTRACT_NUMBER(destination, source) \
381 (destination) = *(source) & 0377; \
382 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \
387 extract_number (dest, source)
389 unsigned char *source;
391 int temp = SIGN_EXTEND_CHAR (*(source + 1));
392 *dest = *source & 0377;
396 #ifndef EXTRACT_MACROS /* To debug the macros. */
397 #undef EXTRACT_NUMBER
398 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
399 #endif /* not EXTRACT_MACROS */
403 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
404 SOURCE must be an lvalue. */
406 #define EXTRACT_NUMBER_AND_INCR(destination, source) \
408 EXTRACT_NUMBER (destination, source); \
414 extract_number_and_incr (destination, source)
416 unsigned char **source;
418 extract_number (destination, *source);
422 #ifndef EXTRACT_MACROS
423 #undef EXTRACT_NUMBER_AND_INCR
424 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
425 extract_number_and_incr (&dest, &src)
426 #endif /* not EXTRACT_MACROS */
430 /* If DEBUG is defined, Regex prints many voluminous messages about what
431 it is doing (if the variable `debug' is nonzero). If linked with the
432 main program in `iregex.c', you can enter patterns and strings
433 interactively. And if linked with the main program in `main.c' and
434 the other test files, you can run the already-written tests. */
438 /* We use standard I/O for debugging. */
441 /* It is useful to test things that ``must'' be true when debugging. */
444 static int debug = 0;
446 #define DEBUG_STATEMENT(e) e
447 #define DEBUG_PRINT1(x) if (debug) printf (x)
448 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
449 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
450 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
451 if (debug) print_partial_compiled_pattern (s, e)
452 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
453 if (debug) print_double_string (w, s1, sz1, s2, sz2)
456 extern void printchar ();
458 /* Print the fastmap in human-readable form. */
461 print_fastmap (fastmap)
464 unsigned was_a_range = 0;
467 while (i < (1 << BYTEWIDTH))
473 while (i < (1 << BYTEWIDTH) && fastmap[i])
489 /* Print a compiled pattern string in human-readable form, starting at
490 the START pointer into it and ending just before the pointer END. */
493 print_partial_compiled_pattern (start, end)
494 unsigned char *start;
498 unsigned char *p = start;
499 unsigned char *pend = end;
507 /* Loop over pattern commands. */
510 switch ((re_opcode_t) *p++)
518 printf ("/exactn/%d", mcnt);
529 printf ("/start_memory/%d/%d", mcnt, *p++);
534 printf ("/stop_memory/%d/%d", mcnt, *p++);
538 printf ("/duplicate/%d", *p++);
550 printf ("/charset%s",
551 (re_opcode_t) *(p - 1) == charset_not ? "_not" : "");
553 assert (p + *p < pend);
555 for (c = 0; c < *p; c++)
558 unsigned char map_byte = p[1 + c];
562 for (bit = 0; bit < BYTEWIDTH; bit++)
563 if (map_byte & (1 << bit))
564 printchar (c * BYTEWIDTH + bit);
578 case on_failure_jump:
579 extract_number_and_incr (&mcnt, &p);
580 printf ("/on_failure_jump/0/%d", mcnt);
583 case on_failure_keep_string_jump:
584 extract_number_and_incr (&mcnt, &p);
585 printf ("/on_failure_keep_string_jump/0/%d", mcnt);
588 case dummy_failure_jump:
589 extract_number_and_incr (&mcnt, &p);
590 printf ("/dummy_failure_jump/0/%d", mcnt);
593 case push_dummy_failure:
594 printf ("/push_dummy_failure");
598 extract_number_and_incr (&mcnt, &p);
599 printf ("/maybe_pop_jump/0/%d", mcnt);
602 case pop_failure_jump:
603 extract_number_and_incr (&mcnt, &p);
604 printf ("/pop_failure_jump/0/%d", mcnt);
608 extract_number_and_incr (&mcnt, &p);
609 printf ("/jump_past_alt/0/%d", mcnt);
613 extract_number_and_incr (&mcnt, &p);
614 printf ("/jump/0/%d", mcnt);
618 extract_number_and_incr (&mcnt, &p);
619 extract_number_and_incr (&mcnt2, &p);
620 printf ("/succeed_n/0/%d/0/%d", mcnt, mcnt2);
624 extract_number_and_incr (&mcnt, &p);
625 extract_number_and_incr (&mcnt2, &p);
626 printf ("/jump_n/0/%d/0/%d", mcnt, mcnt2);
630 extract_number_and_incr (&mcnt, &p);
631 extract_number_and_incr (&mcnt2, &p);
632 printf ("/set_number_at/0/%d/0/%d", mcnt, mcnt2);
636 printf ("/wordbound");
640 printf ("/notwordbound");
652 printf ("/before_dot");
660 printf ("/after_dot");
664 printf ("/syntaxspec");
666 printf ("/%d", mcnt);
670 printf ("/notsyntaxspec");
672 printf ("/%d", mcnt);
677 printf ("/wordchar");
681 printf ("/notwordchar");
693 printf ("?%d", *(p-1));
701 print_compiled_pattern (bufp)
702 struct re_pattern_buffer *bufp;
704 unsigned char *buffer = bufp->buffer;
706 print_partial_compiled_pattern (buffer, buffer + bufp->used);
707 printf ("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated);
709 if (bufp->fastmap_accurate && bufp->fastmap)
711 printf ("fastmap: ");
712 print_fastmap (bufp->fastmap);
715 printf ("re_nsub: %d\t", bufp->re_nsub);
716 printf ("regs_alloc: %d\t", bufp->regs_allocated);
717 printf ("can_be_null: %d\t", bufp->can_be_null);
718 printf ("newline_anchor: %d\n", bufp->newline_anchor);
719 printf ("no_sub: %d\t", bufp->no_sub);
720 printf ("not_bol: %d\t", bufp->not_bol);
721 printf ("not_eol: %d\t", bufp->not_eol);
722 printf ("syntax: %d\n", bufp->syntax);
723 /* Perhaps we should print the translate table? */
728 print_double_string (where, string1, size1, string2, size2)
741 if (FIRST_STRING_P (where))
743 for (this_char = where - string1; this_char < size1; this_char++)
744 printchar (string1[this_char]);
749 for (this_char = where - string2; this_char < size2; this_char++)
750 printchar (string2[this_char]);
754 #else /* not DEBUG */
759 #define DEBUG_STATEMENT(e)
760 #define DEBUG_PRINT1(x)
761 #define DEBUG_PRINT2(x1, x2)
762 #define DEBUG_PRINT3(x1, x2, x3)
763 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
764 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
766 #endif /* not DEBUG */
768 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
769 also be assigned to arbitrarily: each pattern buffer stores its own
770 syntax, so it can be changed between regex compilations. */
771 reg_syntax_t re_syntax_options = RE_SYNTAX_EMACS;
774 /* Specify the precise syntax of regexps for compilation. This provides
775 for compatibility for various utilities which historically have
776 different, incompatible syntaxes.
778 The argument SYNTAX is a bit mask comprised of the various bits
779 defined in regex.h. We return the old syntax. */
782 re_set_syntax (syntax)
785 reg_syntax_t ret = re_syntax_options;
787 re_syntax_options = syntax;
791 /* This table gives an error message for each of the error codes listed
792 in regex.h. Obviously the order here has to be same as there. */
794 static const char *re_error_msg[] =
795 { NULL, /* REG_NOERROR */
796 "No match", /* REG_NOMATCH */
797 "Invalid regular expression", /* REG_BADPAT */
798 "Invalid collation character", /* REG_ECOLLATE */
799 "Invalid character class name", /* REG_ECTYPE */
800 "Trailing backslash", /* REG_EESCAPE */
801 "Invalid back reference", /* REG_ESUBREG */
802 "Unmatched [ or [^", /* REG_EBRACK */
803 "Unmatched ( or \\(", /* REG_EPAREN */
804 "Unmatched \\{", /* REG_EBRACE */
805 "Invalid content of \\{\\}", /* REG_BADBR */
806 "Invalid range end", /* REG_ERANGE */
807 "Memory exhausted", /* REG_ESPACE */
808 "Invalid preceding regular expression", /* REG_BADRPT */
809 "Premature end of regular expression", /* REG_EEND */
810 "Regular expression too big", /* REG_ESIZE */
811 "Unmatched ) or \\)", /* REG_ERPAREN */
814 /* Subroutine declarations and macros for regex_compile. */
816 static void store_op1 (), store_op2 ();
817 static void insert_op1 (), insert_op2 ();
818 static boolean at_begline_loc_p (), at_endline_loc_p ();
819 static boolean group_in_compile_stack ();
820 static reg_errcode_t compile_range ();
822 /* Fetch the next character in the uncompiled pattern---translating it
823 if necessary. Also cast from a signed character in the constant
824 string passed to us by the user to an unsigned char that we can use
825 as an array index (in, e.g., `translate'). */
826 #define PATFETCH(c) \
827 do {if (p == pend) return REG_EEND; \
828 c = (unsigned char) *p++; \
829 if (translate) c = translate[c]; \
832 /* Fetch the next character in the uncompiled pattern, with no
834 #define PATFETCH_RAW(c) \
835 do {if (p == pend) return REG_EEND; \
836 c = (unsigned char) *p++; \
839 /* Go backwards one character in the pattern. */
840 #define PATUNFETCH p--
843 /* If `translate' is non-null, return translate[D], else just D. We
844 cast the subscript to translate because some data is declared as
845 `char *', to avoid warnings when a string constant is passed. But
846 when we use a character as a subscript we must make it unsigned. */
847 #define TRANSLATE(d) (translate ? translate[(unsigned char) (d)] : (d))
850 /* Macros for outputting the compiled pattern into `buffer'. */
852 /* If the buffer isn't allocated when it comes in, use this. */
853 #define INIT_BUF_SIZE 32
855 /* Make sure we have at least N more bytes of space in buffer. */
856 #define GET_BUFFER_SPACE(n) \
857 while (b - bufp->buffer + (n) > bufp->allocated) \
860 /* Make sure we have one more byte of buffer space and then add C to it. */
861 #define BUF_PUSH(c) \
863 GET_BUFFER_SPACE (1); \
864 *b++ = (unsigned char) (c); \
868 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
869 #define BUF_PUSH_2(c1, c2) \
871 GET_BUFFER_SPACE (2); \
872 *b++ = (unsigned char) (c1); \
873 *b++ = (unsigned char) (c2); \
877 /* As with BUF_PUSH_2, except for three bytes. */
878 #define BUF_PUSH_3(c1, c2, c3) \
880 GET_BUFFER_SPACE (3); \
881 *b++ = (unsigned char) (c1); \
882 *b++ = (unsigned char) (c2); \
883 *b++ = (unsigned char) (c3); \
887 /* Store a jump with opcode OP at LOC to location TO. We store a
888 relative address offset by the three bytes the jump itself occupies. */
889 #define STORE_JUMP(op, loc, to) \
890 store_op1 (op, loc, (to) - (loc) - 3)
892 /* Likewise, for a two-argument jump. */
893 #define STORE_JUMP2(op, loc, to, arg) \
894 store_op2 (op, loc, (to) - (loc) - 3, arg)
896 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
897 #define INSERT_JUMP(op, loc, to) \
898 insert_op1 (op, loc, (to) - (loc) - 3, b)
900 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
901 #define INSERT_JUMP2(op, loc, to, arg) \
902 insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
905 /* This is not an arbitrary limit: the arguments which represent offsets
906 into the pattern are two bytes long. So if 2^16 bytes turns out to
907 be too small, many things would have to change. */
908 #define MAX_BUF_SIZE (1L << 16)
911 /* Extend the buffer by twice its current size via realloc and
912 reset the pointers that pointed into the old block to point to the
913 correct places in the new one. If extending the buffer results in it
914 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
915 #define EXTEND_BUFFER() \
917 unsigned char *old_buffer = bufp->buffer; \
918 if (bufp->allocated == MAX_BUF_SIZE) \
920 bufp->allocated <<= 1; \
921 if (bufp->allocated > MAX_BUF_SIZE) \
922 bufp->allocated = MAX_BUF_SIZE; \
923 bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
924 if (bufp->buffer == NULL) \
926 /* If the buffer moved, move all the pointers into it. */ \
927 if (old_buffer != bufp->buffer) \
929 b = (b - old_buffer) + bufp->buffer; \
930 begalt = (begalt - old_buffer) + bufp->buffer; \
931 if (fixup_alt_jump) \
932 fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
934 laststart = (laststart - old_buffer) + bufp->buffer; \
936 pending_exact = (pending_exact - old_buffer) + bufp->buffer; \
941 /* Since we have one byte reserved for the register number argument to
942 {start,stop}_memory, the maximum number of groups we can report
943 things about is what fits in that byte. */
944 #define MAX_REGNUM 255
946 /* But patterns can have more than `MAX_REGNUM' registers. We just
947 ignore the excess. */
948 typedef unsigned regnum_t;
951 /* Macros for the compile stack. */
953 /* Since offsets can go either forwards or backwards, this type needs to
954 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
955 typedef int pattern_offset_t;
959 pattern_offset_t begalt_offset;
960 pattern_offset_t fixup_alt_jump;
961 pattern_offset_t inner_group_offset;
962 pattern_offset_t laststart_offset;
964 } compile_stack_elt_t;
969 compile_stack_elt_t *stack;
971 unsigned avail; /* Offset of next open position. */
972 } compile_stack_type;
975 #define INIT_COMPILE_STACK_SIZE 32
977 #define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
978 #define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
980 /* The next available element. */
981 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
984 /* Set the bit for character C in a list. */
985 #define SET_LIST_BIT(c) \
986 (b[((unsigned char) (c)) / BYTEWIDTH] \
987 |= 1 << (((unsigned char) c) % BYTEWIDTH))
990 /* Get the next unsigned number in the uncompiled pattern. */
991 #define GET_UNSIGNED_NUMBER(num) \
995 while (isdigit (c)) \
999 num = num * 10 + c - '0'; \
1007 #define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
1009 #define IS_CHAR_CLASS(string) \
1010 (STREQ (string, "alpha") || STREQ (string, "upper") \
1011 || STREQ (string, "lower") || STREQ (string, "digit") \
1012 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
1013 || STREQ (string, "space") || STREQ (string, "print") \
1014 || STREQ (string, "punct") || STREQ (string, "graph") \
1015 || STREQ (string, "cntrl") || STREQ (string, "blank"))
1017 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1018 Returns one of error codes defined in `regex.h', or zero for success.
1020 Assumes the `allocated' (and perhaps `buffer') and `translate'
1021 fields are set in BUFP on entry.
1023 If it succeeds, results are put in BUFP (if it returns an error, the
1024 contents of BUFP are undefined):
1025 `buffer' is the compiled pattern;
1026 `syntax' is set to SYNTAX;
1027 `used' is set to the length of the compiled pattern;
1028 `fastmap_accurate' is set to zero;
1029 `re_nsub' is set to the number of groups in PATTERN;
1030 `not_bol' and `not_eol' are set to zero.
1032 The `fastmap' and `newline_anchor' fields are neither
1033 examined nor set. */
1035 static reg_errcode_t
1036 regex_compile (pattern, size, syntax, bufp)
1037 const char *pattern;
1039 reg_syntax_t syntax;
1040 struct re_pattern_buffer *bufp;
1042 /* We fetch characters from PATTERN here. Even though PATTERN is
1043 `char *' (i.e., signed), we declare these variables as unsigned, so
1044 they can be reliably used as array indices. */
1045 register unsigned char c, c1;
1047 /* A random tempory spot in PATTERN. */
1050 /* Points to the end of the buffer, where we should append. */
1051 register unsigned char *b;
1053 /* Keeps track of unclosed groups. */
1054 compile_stack_type compile_stack;
1056 /* Points to the current (ending) position in the pattern. */
1057 const char *p = pattern;
1058 const char *pend = pattern + size;
1060 /* How to translate the characters in the pattern. */
1061 char *translate = bufp->translate;
1063 /* Address of the count-byte of the most recently inserted `exactn'
1064 command. This makes it possible to tell if a new exact-match
1065 character can be added to that command or if the character requires
1066 a new `exactn' command. */
1067 unsigned char *pending_exact = 0;
1069 /* Address of start of the most recently finished expression.
1070 This tells, e.g., postfix * where to find the start of its
1071 operand. Reset at the beginning of groups and alternatives. */
1072 unsigned char *laststart = 0;
1074 /* Address of beginning of regexp, or inside of last group. */
1075 unsigned char *begalt;
1077 /* Place in the uncompiled pattern (i.e., the {) to
1078 which to go back if the interval is invalid. */
1079 const char *beg_interval;
1081 /* Address of the place where a forward jump should go to the end of
1082 the containing expression. Each alternative of an `or' -- except the
1083 last -- ends with a forward jump of this sort. */
1084 unsigned char *fixup_alt_jump = 0;
1086 /* Counts open-groups as they are encountered. Remembered for the
1087 matching close-group on the compile stack, so the same register
1088 number is put in the stop_memory as the start_memory. */
1089 regnum_t regnum = 0;
1092 DEBUG_PRINT1 ("\nCompiling pattern: ");
1095 unsigned debug_count;
1097 for (debug_count = 0; debug_count < size; debug_count++)
1098 printchar (pattern[debug_count]);
1103 /* Initialize the compile stack. */
1104 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1105 if (compile_stack.stack == NULL)
1108 compile_stack.size = INIT_COMPILE_STACK_SIZE;
1109 compile_stack.avail = 0;
1111 /* Initialize the pattern buffer. */
1112 bufp->syntax = syntax;
1113 bufp->fastmap_accurate = 0;
1114 bufp->not_bol = bufp->not_eol = 0;
1116 /* Set `used' to zero, so that if we return an error, the pattern
1117 printer (for debugging) will think there's no pattern. We reset it
1121 /* Always count groups, whether or not bufp->no_sub is set. */
1124 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1125 /* Initialize the syntax table. */
1126 init_syntax_once ();
1129 if (bufp->allocated == 0)
1132 { /* If zero allocated, but buffer is non-null, try to realloc
1133 enough space. This loses if buffer's address is bogus, but
1134 that is the user's responsibility. */
1135 RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1138 { /* Caller did not allocate a buffer. Do it for them. */
1139 bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1141 if (!bufp->buffer) return REG_ESPACE;
1143 bufp->allocated = INIT_BUF_SIZE;
1146 begalt = b = bufp->buffer;
1148 /* Loop through the uncompiled pattern until we're at the end. */
1157 if ( /* If at start of pattern, it's an operator. */
1159 /* If context independent, it's an operator. */
1160 || syntax & RE_CONTEXT_INDEP_ANCHORS
1161 /* Otherwise, depends on what's come before. */
1162 || at_begline_loc_p (pattern, p, syntax))
1172 if ( /* If at end of pattern, it's an operator. */
1174 /* If context independent, it's an operator. */
1175 || syntax & RE_CONTEXT_INDEP_ANCHORS
1176 /* Otherwise, depends on what's next. */
1177 || at_endline_loc_p (p, pend, syntax))
1187 if ((syntax & RE_BK_PLUS_QM)
1188 || (syntax & RE_LIMITED_OPS))
1192 /* If there is no previous pattern... */
1195 if (syntax & RE_CONTEXT_INVALID_OPS)
1197 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1202 /* Are we optimizing this jump? */
1203 boolean keep_string_p = false;
1205 /* 1 means zero (many) matches is allowed. */
1206 char zero_times_ok = 0, many_times_ok = 0;
1208 /* If there is a sequence of repetition chars, collapse it
1209 down to just one (the right one). We can't combine
1210 interval operators with these because of, e.g., `a{2}*',
1211 which should only match an even number of `a's. */
1215 zero_times_ok |= c != '+';
1216 many_times_ok |= c != '?';
1224 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1227 else if (syntax & RE_BK_PLUS_QM && c == '\\')
1229 if (p == pend) return REG_EESCAPE;
1232 if (!(c1 == '+' || c1 == '?'))
1247 /* If we get here, we found another repeat character. */
1250 /* Star, etc. applied to an empty pattern is equivalent
1251 to an empty pattern. */
1255 /* Now we know whether or not zero matches is allowed
1256 and also whether or not two or more matches is allowed. */
1258 { /* More than one repetition is allowed, so put in at the
1259 end a backward relative jump from `b' to before the next
1260 jump we're going to put in below (which jumps from
1261 laststart to after this jump).
1263 But if we are at the `*' in the exact sequence `.*\n',
1264 insert an unconditional jump backwards to the .,
1265 instead of the beginning of the loop. This way we only
1266 push a failure point once, instead of every time
1267 through the loop. */
1268 assert (p - 1 > pattern);
1270 /* Allocate the space for the jump. */
1271 GET_BUFFER_SPACE (3);
1273 /* We know we are not at the first character of the pattern,
1274 because laststart was nonzero. And we've already
1275 incremented `p', by the way, to be the character after
1276 the `*'. Do we have to do something analogous here
1277 for null bytes, because of RE_DOT_NOT_NULL? */
1278 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
1279 && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
1280 && !(syntax & RE_DOT_NEWLINE))
1281 { /* We have .*\n. */
1282 STORE_JUMP (jump, b, laststart);
1283 keep_string_p = true;
1286 /* Anything else. */
1287 STORE_JUMP (maybe_pop_jump, b, laststart - 3);
1289 /* We've added more stuff to the buffer. */
1293 /* On failure, jump from laststart to b + 3, which will be the
1294 end of the buffer after this jump is inserted. */
1295 GET_BUFFER_SPACE (3);
1296 INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
1304 /* At least one repetition is required, so insert a
1305 `dummy_failure_jump' before the initial
1306 `on_failure_jump' instruction of the loop. This
1307 effects a skip over that instruction the first time
1308 we hit that loop. */
1309 GET_BUFFER_SPACE (3);
1310 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
1325 boolean had_char_class = false;
1327 if (p == pend) return REG_EBRACK;
1329 /* Ensure that we have enough space to push a charset: the
1330 opcode, the length count, and the bitset; 34 bytes in all. */
1331 GET_BUFFER_SPACE (34);
1335 /* We test `*p == '^' twice, instead of using an if
1336 statement, so we only need one BUF_PUSH. */
1337 BUF_PUSH (*p == '^' ? charset_not : charset);
1341 /* Remember the first position in the bracket expression. */
1344 /* Push the number of bytes in the bitmap. */
1345 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
1347 /* Clear the whole map. */
1348 bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
1350 /* charset_not matches newline according to a syntax bit. */
1351 if ((re_opcode_t) b[-2] == charset_not
1352 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
1353 SET_LIST_BIT ('\n');
1355 /* Read in characters and ranges, setting map bits. */
1358 if (p == pend) return REG_EBRACK;
1362 /* \ might escape characters inside [...] and [^...]. */
1363 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
1365 if (p == pend) return REG_EESCAPE;
1372 /* Could be the end of the bracket expression. If it's
1373 not (i.e., when the bracket expression is `[]' so
1374 far), the ']' character bit gets set way below. */
1375 if (c == ']' && p != p1 + 1)
1378 /* Look ahead to see if it's a range when the last thing
1379 was a character class. */
1380 if (had_char_class && c == '-' && *p != ']')
1383 /* Look ahead to see if it's a range when the last thing
1384 was a character: if this is a hyphen not at the
1385 beginning or the end of a list, then it's the range
1388 && !(p - 2 >= pattern && p[-2] == '[')
1389 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
1393 = compile_range (&p, pend, translate, syntax, b);
1394 if (ret != REG_NOERROR) return ret;
1397 else if (p[0] == '-' && p[1] != ']')
1398 { /* This handles ranges made up of characters only. */
1401 /* Move past the `-'. */
1404 ret = compile_range (&p, pend, translate, syntax, b);
1405 if (ret != REG_NOERROR) return ret;
1408 /* See if we're at the beginning of a possible character
1411 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
1412 { /* Leave room for the null. */
1413 char str[CHAR_CLASS_MAX_LENGTH + 1];
1418 /* If pattern is `[[:'. */
1419 if (p == pend) return REG_EBRACK;
1424 if (c == ':' || c == ']' || p == pend
1425 || c1 == CHAR_CLASS_MAX_LENGTH)
1431 /* If isn't a word bracketed by `[:' and:`]':
1432 undo the ending character, the letters, and leave
1433 the leading `:' and `[' (but set bits for them). */
1434 if (c == ':' && *p == ']')
1437 boolean is_alnum = STREQ (str, "alnum");
1438 boolean is_alpha = STREQ (str, "alpha");
1439 boolean is_blank = STREQ (str, "blank");
1440 boolean is_cntrl = STREQ (str, "cntrl");
1441 boolean is_digit = STREQ (str, "digit");
1442 boolean is_graph = STREQ (str, "graph");
1443 boolean is_lower = STREQ (str, "lower");
1444 boolean is_print = STREQ (str, "print");
1445 boolean is_punct = STREQ (str, "punct");
1446 boolean is_space = STREQ (str, "space");
1447 boolean is_upper = STREQ (str, "upper");
1448 boolean is_xdigit = STREQ (str, "xdigit");
1450 if (!IS_CHAR_CLASS (str)) return REG_ECTYPE;
1452 /* Throw away the ] at the end of the character
1456 if (p == pend) return REG_EBRACK;
1458 for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
1460 if ( (is_alnum && isalnum (ch))
1461 || (is_alpha && isalpha (ch))
1462 || (is_blank && isblank (ch))
1463 || (is_cntrl && iscntrl (ch))
1464 || (is_digit && isdigit (ch))
1465 || (is_graph && isgraph (ch))
1466 || (is_lower && islower (ch))
1467 || (is_print && isprint (ch))
1468 || (is_punct && ispunct (ch))
1469 || (is_space && isspace (ch))
1470 || (is_upper && isupper (ch))
1471 || (is_xdigit && isxdigit (ch)))
1474 had_char_class = true;
1483 had_char_class = false;
1488 had_char_class = false;
1493 /* Discard any (non)matching list bytes that are all 0 at the
1494 end of the map. Decrease the map-length byte too. */
1495 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
1503 if (syntax & RE_NO_BK_PARENS)
1510 if (syntax & RE_NO_BK_PARENS)
1517 if (syntax & RE_NEWLINE_ALT)
1524 if (syntax & RE_NO_BK_VBAR)
1531 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
1532 goto handle_interval;
1538 if (p == pend) return REG_EESCAPE;
1540 /* Do not translate the character after the \, so that we can
1541 distinguish, e.g., \B from \b, even if we normally would
1542 translate, e.g., B to b. */
1548 if (syntax & RE_NO_BK_PARENS)
1549 goto normal_backslash;
1555 if (COMPILE_STACK_FULL)
1557 RETALLOC (compile_stack.stack, compile_stack.size << 1,
1558 compile_stack_elt_t);
1559 if (compile_stack.stack == NULL) return REG_ESPACE;
1561 compile_stack.size <<= 1;
1564 /* These are the values to restore when we hit end of this
1565 group. They are all relative offsets, so that if the
1566 whole pattern moves because of realloc, they will still
1568 COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
1569 COMPILE_STACK_TOP.fixup_alt_jump
1570 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
1571 COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
1572 COMPILE_STACK_TOP.regnum = regnum;
1574 /* We will eventually replace the 0 with the number of
1575 groups inner to this one. But do not push a
1576 start_memory for groups beyond the last one we can
1577 represent in the compiled pattern. */
1578 if (regnum <= MAX_REGNUM)
1580 COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
1581 BUF_PUSH_3 (start_memory, regnum, 0);
1584 compile_stack.avail++;
1593 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
1595 if (COMPILE_STACK_EMPTY)
1596 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1597 goto normal_backslash;
1603 { /* Push a dummy failure point at the end of the
1604 alternative for a possible future
1605 `pop_failure_jump' to pop. See comments at
1606 `push_dummy_failure' in `re_match_2'. */
1607 BUF_PUSH (push_dummy_failure);
1609 /* We allocated space for this jump when we assigned
1610 to `fixup_alt_jump', in the `handle_alt' case below. */
1611 STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
1614 /* See similar code for backslashed left paren above. */
1615 if (COMPILE_STACK_EMPTY)
1616 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
1621 /* Since we just checked for an empty stack above, this
1622 ``can't happen''. */
1623 assert (compile_stack.avail != 0);
1625 /* We don't just want to restore into `regnum', because
1626 later groups should continue to be numbered higher,
1627 as in `(ab)c(de)' -- the second group is #2. */
1628 regnum_t this_group_regnum;
1630 compile_stack.avail--;
1631 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
1633 = COMPILE_STACK_TOP.fixup_alt_jump
1634 ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
1636 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
1637 this_group_regnum = COMPILE_STACK_TOP.regnum;
1639 /* We're at the end of the group, so now we know how many
1640 groups were inside this one. */
1641 if (this_group_regnum <= MAX_REGNUM)
1643 unsigned char *inner_group_loc
1644 = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
1646 *inner_group_loc = regnum - this_group_regnum;
1647 BUF_PUSH_3 (stop_memory, this_group_regnum,
1648 regnum - this_group_regnum);
1654 case '|': /* `\|'. */
1655 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
1656 goto normal_backslash;
1658 if (syntax & RE_LIMITED_OPS)
1661 /* Insert before the previous alternative a jump which
1662 jumps to this alternative if the former fails. */
1663 GET_BUFFER_SPACE (3);
1664 INSERT_JUMP (on_failure_jump, begalt, b + 6);
1668 /* The alternative before this one has a jump after it
1669 which gets executed if it gets matched. Adjust that
1670 jump so it will jump to this alternative's analogous
1671 jump (put in below, which in turn will jump to the next
1672 (if any) alternative's such jump, etc.). The last such
1673 jump jumps to the correct final destination. A picture:
1679 If we are at `b,' then fixup_alt_jump right now points to a
1680 three-byte space after `a.' We'll put in the jump, set
1681 fixup_alt_jump to right after `b,' and leave behind three
1682 bytes which we'll fill in when we get to after `c.' */
1685 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
1687 /* Mark and leave space for a jump after this alternative,
1688 to be filled in later either by next alternative or
1689 when know we're at the end of a series of alternatives. */
1691 GET_BUFFER_SPACE (3);
1700 /* If \{ is a literal. */
1701 if (!(syntax & RE_INTERVALS)
1702 /* If we're at `\{' and it's not the open-interval
1704 || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1705 || (p - 2 == pattern && p == pend))
1706 goto normal_backslash;
1710 /* If got here, then the syntax allows intervals. */
1712 /* At least (most) this many matches must be made. */
1713 int lower_bound = -1, upper_bound = -1;
1715 beg_interval = p - 1;
1719 if (syntax & RE_NO_BK_BRACES)
1720 goto unfetch_interval;
1725 GET_UNSIGNED_NUMBER (lower_bound);
1729 GET_UNSIGNED_NUMBER (upper_bound);
1730 if (upper_bound < 0) upper_bound = RE_DUP_MAX;
1733 /* Interval such as `{1}' => match exactly once. */
1734 upper_bound = lower_bound;
1736 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
1737 || lower_bound > upper_bound)
1739 if (syntax & RE_NO_BK_BRACES)
1740 goto unfetch_interval;
1745 if (!(syntax & RE_NO_BK_BRACES))
1747 if (c != '\\') return REG_EBRACE;
1754 if (syntax & RE_NO_BK_BRACES)
1755 goto unfetch_interval;
1760 /* We just parsed a valid interval. */
1762 /* If it's invalid to have no preceding re. */
1765 if (syntax & RE_CONTEXT_INVALID_OPS)
1767 else if (syntax & RE_CONTEXT_INDEP_OPS)
1770 goto unfetch_interval;
1773 /* If the upper bound is zero, don't want to succeed at
1774 all; jump from `laststart' to `b + 3', which will be
1775 the end of the buffer after we insert the jump. */
1776 if (upper_bound == 0)
1778 GET_BUFFER_SPACE (3);
1779 INSERT_JUMP (jump, laststart, b + 3);
1783 /* Otherwise, we have a nontrivial interval. When
1784 we're all done, the pattern will look like:
1785 set_number_at <jump count> <upper bound>
1786 set_number_at <succeed_n count> <lower bound>
1787 succeed_n <after jump addr> <succed_n count>
1789 jump_n <succeed_n addr> <jump count>
1790 (The upper bound and `jump_n' are omitted if
1791 `upper_bound' is 1, though.) */
1793 { /* If the upper bound is > 1, we need to insert
1794 more at the end of the loop. */
1795 unsigned nbytes = 10 + (upper_bound > 1) * 10;
1797 GET_BUFFER_SPACE (nbytes);
1799 /* Initialize lower bound of the `succeed_n', even
1800 though it will be set during matching by its
1801 attendant `set_number_at' (inserted next),
1802 because `re_compile_fastmap' needs to know.
1803 Jump to the `jump_n' we might insert below. */
1804 INSERT_JUMP2 (succeed_n, laststart,
1805 b + 5 + (upper_bound > 1) * 5,
1809 /* Code to initialize the lower bound. Insert
1810 before the `succeed_n'. The `5' is the last two
1811 bytes of this `set_number_at', plus 3 bytes of
1812 the following `succeed_n'. */
1813 insert_op2 (set_number_at, laststart, 5, lower_bound, b);
1816 if (upper_bound > 1)
1817 { /* More than one repetition is allowed, so
1818 append a backward jump to the `succeed_n'
1819 that starts this interval.
1821 When we've reached this during matching,
1822 we'll have matched the interval once, so
1823 jump back only `upper_bound - 1' times. */
1824 STORE_JUMP2 (jump_n, b, laststart + 5,
1828 /* The location we want to set is the second
1829 parameter of the `jump_n'; that is `b-2' as
1830 an absolute address. `laststart' will be
1831 the `set_number_at' we're about to insert;
1832 `laststart+3' the number to set, the source
1833 for the relative address. But we are
1834 inserting into the middle of the pattern --
1835 so everything is getting moved up by 5.
1836 Conclusion: (b - 2) - (laststart + 3) + 5,
1837 i.e., b - laststart.
1839 We insert this at the beginning of the loop
1840 so that if we fail during matching, we'll
1841 reinitialize the bounds. */
1842 insert_op2 (set_number_at, laststart, b - laststart,
1843 upper_bound - 1, b);
1848 beg_interval = NULL;
1853 /* If an invalid interval, match the characters as literals. */
1854 assert (beg_interval);
1856 beg_interval = NULL;
1858 /* normal_char and normal_backslash need `c'. */
1861 if (!(syntax & RE_NO_BK_BRACES))
1863 if (p > pattern && p[-1] == '\\')
1864 goto normal_backslash;
1869 /* There is no way to specify the before_dot and after_dot
1870 operators. rms says this is ok. --karl */
1878 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
1884 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
1891 BUF_PUSH (wordchar);
1897 BUF_PUSH (notwordchar);
1910 BUF_PUSH (wordbound);
1914 BUF_PUSH (notwordbound);
1925 case '1': case '2': case '3': case '4': case '5':
1926 case '6': case '7': case '8': case '9':
1927 if (syntax & RE_NO_BK_REFS)
1935 /* Can't back reference to a subexpression if inside of it. */
1936 if (group_in_compile_stack (compile_stack, c1))
1940 BUF_PUSH_2 (duplicate, c1);
1946 if (syntax & RE_BK_PLUS_QM)
1949 goto normal_backslash;
1953 /* You might think it would be useful for \ to mean
1954 not to translate; but if we don't translate it
1955 it will never match anything. */
1963 /* Expects the character in `c'. */
1965 /* If no exactn currently being built. */
1968 /* If last exactn not at current position. */
1969 || pending_exact + *pending_exact + 1 != b
1971 /* We have only one byte following the exactn for the count. */
1972 || *pending_exact == (1 << BYTEWIDTH) - 1
1974 /* If followed by a repetition operator. */
1975 || *p == '*' || *p == '^'
1976 || ((syntax & RE_BK_PLUS_QM)
1977 ? *p == '\\' && (p[1] == '+' || p[1] == '?')
1978 : (*p == '+' || *p == '?'))
1979 || ((syntax & RE_INTERVALS)
1980 && ((syntax & RE_NO_BK_BRACES)
1982 : (p[0] == '\\' && p[1] == '{'))))
1984 /* Start building a new exactn. */
1988 BUF_PUSH_2 (exactn, 0);
1989 pending_exact = b - 1;
1996 } /* while p != pend */
1999 /* Through the pattern now. */
2002 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2004 if (!COMPILE_STACK_EMPTY)
2007 free (compile_stack.stack);
2009 /* We have succeeded; set the length of the buffer. */
2010 bufp->used = b - bufp->buffer;
2015 DEBUG_PRINT1 ("\nCompiled pattern: ");
2016 print_compiled_pattern (bufp);
2021 } /* regex_compile */
2023 /* Subroutines for `regex_compile'. */
2025 /* Store OP at LOC followed by two-byte integer parameter ARG. */
2028 store_op1 (op, loc, arg)
2033 *loc = (unsigned char) op;
2034 STORE_NUMBER (loc + 1, arg);
2038 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
2041 store_op2 (op, loc, arg1, arg2)
2046 *loc = (unsigned char) op;
2047 STORE_NUMBER (loc + 1, arg1);
2048 STORE_NUMBER (loc + 3, arg2);
2052 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2053 for OP followed by two-byte integer parameter ARG. */
2056 insert_op1 (op, loc, arg, end)
2062 register unsigned char *pfrom = end;
2063 register unsigned char *pto = end + 3;
2065 while (pfrom != loc)
2068 store_op1 (op, loc, arg);
2072 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
2075 insert_op2 (op, loc, arg1, arg2, end)
2081 register unsigned char *pfrom = end;
2082 register unsigned char *pto = end + 5;
2084 while (pfrom != loc)
2087 store_op2 (op, loc, arg1, arg2);
2091 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
2092 after an alternative or a begin-subexpression. We assume there is at
2093 least one character before the ^. */
2096 at_begline_loc_p (pattern, p, syntax)
2097 const char *pattern, *p;
2098 reg_syntax_t syntax;
2100 const char *prev = p - 2;
2101 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2104 /* After a subexpression? */
2105 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2106 /* After an alternative? */
2107 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2111 /* The dual of at_begline_loc_p. This one is for $. We assume there is
2112 at least one character after the $, i.e., `P < PEND'. */
2115 at_endline_loc_p (p, pend, syntax)
2116 const char *p, *pend;
2119 const char *next = p;
2120 boolean next_backslash = *next == '\\';
2121 const char *next_next = p + 1 < pend ? p + 1 : NULL;
2124 /* Before a subexpression? */
2125 (syntax & RE_NO_BK_PARENS ? *next == ')'
2126 : next_backslash && next_next && *next_next == ')')
2127 /* Before an alternative? */
2128 || (syntax & RE_NO_BK_VBAR ? *next == '|'
2129 : next_backslash && next_next && *next_next == '|');
2133 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2134 false if it's not. */
2137 group_in_compile_stack (compile_stack, regnum)
2138 compile_stack_type compile_stack;
2143 for (this_element = compile_stack.avail - 1;
2146 if (compile_stack.stack[this_element].regnum == regnum)
2153 /* Read the ending character of a range (in a bracket expression) from the
2154 uncompiled pattern *P_PTR (which ends at PEND). We assume the
2155 starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
2156 Then we set the translation of all bits between the starting and
2157 ending characters (inclusive) in the compiled pattern B.
2159 Return an error code.
2161 We use these short variable names so we can use the same macros as
2162 `regex_compile' itself. */
2164 static reg_errcode_t
2165 compile_range (p_ptr, pend, translate, syntax, b)
2166 const char **p_ptr, *pend;
2168 reg_syntax_t syntax;
2173 const char *p = *p_ptr;
2175 /* Even though the pattern is a signed `char *', we need to fetch into
2176 `unsigned char's. Reason: if the high bit of the pattern character
2177 is set, the range endpoints will be negative if we fetch into a
2179 unsigned char range_end;
2180 unsigned char range_start = p[-2];
2185 PATFETCH (range_end);
2187 /* Have to increment the pointer into the pattern string, so the
2188 caller isn't still at the ending character. */
2191 /* If the start is after the end, the range is empty. */
2192 if (range_start > range_end)
2193 return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2195 /* Here we see why `this_char' has to be larger than an `unsigned
2196 char' -- the range is inclusive, so if `range_end' == 0xff
2197 (assuming 8-bit characters), we would otherwise go into an infinite
2198 loop, since all characters <= 0xff. */
2199 for (this_char = range_start; this_char <= range_end; this_char++)
2201 SET_LIST_BIT (TRANSLATE (this_char));
2207 /* Failure stack declarations and macros; both re_compile_fastmap and
2208 re_match_2 use a failure stack. These have to be macros because of
2212 /* Number of failure points for which to initially allocate space
2213 when matching. If this number is exceeded, we allocate more
2214 space, so it is not a hard limit. */
2215 #ifndef INIT_FAILURE_ALLOC
2216 #define INIT_FAILURE_ALLOC 5
2219 /* Roughly the maximum number of failure points on the stack. Would be
2220 exactly that if always used MAX_FAILURE_SPACE each time we failed.
2221 This is a variable only so users of regex can assign to it; we never
2222 change it ourselves. */
2223 int re_max_failures = 2000;
2225 typedef const unsigned char *fail_stack_elt_t;
2229 fail_stack_elt_t *stack;
2231 unsigned avail; /* Offset of next open position. */
2234 #define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
2235 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
2236 #define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
2237 #define FAIL_STACK_TOP() (fail_stack.stack[fail_stack.avail])
2240 /* Initialize `fail_stack'. Do `return -2' if the alloc fails. */
2242 #define INIT_FAIL_STACK() \
2244 fail_stack.stack = (fail_stack_elt_t *) \
2245 REGEX_ALLOCATE (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t)); \
2247 if (fail_stack.stack == NULL) \
2250 fail_stack.size = INIT_FAILURE_ALLOC; \
2251 fail_stack.avail = 0; \
2255 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
2257 Return 1 if succeeds, and 0 if either ran out of memory
2258 allocating space for it or it was already too large.
2260 REGEX_REALLOCATE requires `destination' be declared. */
2262 #define DOUBLE_FAIL_STACK(fail_stack) \
2263 ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS \
2265 : ((fail_stack).stack = (fail_stack_elt_t *) \
2266 REGEX_REALLOCATE ((fail_stack).stack, \
2267 (fail_stack).size * sizeof (fail_stack_elt_t), \
2268 ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)), \
2270 (fail_stack).stack == NULL \
2272 : ((fail_stack).size <<= 1, \
2276 /* Push PATTERN_OP on FAIL_STACK.
2278 Return 1 if was able to do so and 0 if ran out of memory allocating
2280 #define PUSH_PATTERN_OP(pattern_op, fail_stack) \
2281 ((FAIL_STACK_FULL () \
2282 && !DOUBLE_FAIL_STACK (fail_stack)) \
2284 : ((fail_stack).stack[(fail_stack).avail++] = pattern_op, \
2287 /* This pushes an item onto the failure stack. Must be a four-byte
2288 value. Assumes the variable `fail_stack'. Probably should only
2289 be called from within `PUSH_FAILURE_POINT'. */
2290 #define PUSH_FAILURE_ITEM(item) \
2291 fail_stack.stack[fail_stack.avail++] = (fail_stack_elt_t) item
2293 /* The complement operation. Assumes `fail_stack' is nonempty. */
2294 #define POP_FAILURE_ITEM() fail_stack.stack[--fail_stack.avail]
2296 /* Used to omit pushing failure point id's when we're not debugging. */
2298 #define DEBUG_PUSH PUSH_FAILURE_ITEM
2299 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_ITEM ()
2301 #define DEBUG_PUSH(item)
2302 #define DEBUG_POP(item_addr)
2306 /* Push the information about the state we will need
2307 if we ever fail back to it.
2309 Requires variables fail_stack, regstart, regend, reg_info, and
2310 num_regs be declared. DOUBLE_FAIL_STACK requires `destination' be
2313 Does `return FAILURE_CODE' if runs out of memory. */
2315 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
2317 char *destination; \
2318 /* Must be int, so when we don't save any registers, the arithmetic \
2319 of 0 + -1 isn't done as unsigned. */ \
2322 DEBUG_STATEMENT (failure_id++); \
2323 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
2324 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
2325 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
2327 DEBUG_PRINT2 (" slots needed: %d\n", NUM_FAILURE_ITEMS); \
2328 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
2330 /* Ensure we have enough space allocated for what we will push. */ \
2331 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
2333 if (!DOUBLE_FAIL_STACK (fail_stack)) \
2334 return failure_code; \
2336 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
2337 (fail_stack).size); \
2338 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
2341 /* Push the info, starting with the registers. */ \
2342 DEBUG_PRINT1 ("\n"); \
2344 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
2347 DEBUG_PRINT2 (" Pushing reg: %d\n", this_reg); \
2348 DEBUG_STATEMENT (num_regs_pushed++); \
2350 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2351 PUSH_FAILURE_ITEM (regstart[this_reg]); \
2353 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2354 PUSH_FAILURE_ITEM (regend[this_reg]); \
2356 DEBUG_PRINT2 (" info: 0x%x\n ", reg_info[this_reg]); \
2357 DEBUG_PRINT2 (" match_null=%d", \
2358 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
2359 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
2360 DEBUG_PRINT2 (" matched_something=%d", \
2361 MATCHED_SOMETHING (reg_info[this_reg])); \
2362 DEBUG_PRINT2 (" ever_matched=%d", \
2363 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
2364 DEBUG_PRINT1 ("\n"); \
2365 PUSH_FAILURE_ITEM (reg_info[this_reg].word); \
2368 DEBUG_PRINT2 (" Pushing low active reg: %d\n", lowest_active_reg);\
2369 PUSH_FAILURE_ITEM (lowest_active_reg); \
2371 DEBUG_PRINT2 (" Pushing high active reg: %d\n", highest_active_reg);\
2372 PUSH_FAILURE_ITEM (highest_active_reg); \
2374 DEBUG_PRINT2 (" Pushing pattern 0x%x: ", pattern_place); \
2375 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
2376 PUSH_FAILURE_ITEM (pattern_place); \
2378 DEBUG_PRINT2 (" Pushing string 0x%x: `", string_place); \
2379 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
2381 DEBUG_PRINT1 ("'\n"); \
2382 PUSH_FAILURE_ITEM (string_place); \
2384 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
2385 DEBUG_PUSH (failure_id); \
2388 /* This is the number of items that are pushed and popped on the stack
2389 for each register. */
2390 #define NUM_REG_ITEMS 3
2392 /* Individual items aside from the registers. */
2394 #define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
2396 #define NUM_NONREG_ITEMS 4
2399 /* We push at most this many items on the stack. */
2400 #define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
2402 /* We actually push this many items. */
2403 #define NUM_FAILURE_ITEMS \
2404 ((highest_active_reg - lowest_active_reg + 1) * NUM_REG_ITEMS \
2407 /* How many items can still be added to the stack without overflowing it. */
2408 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
2411 /* Pops what PUSH_FAIL_STACK pushes.
2413 We restore into the parameters, all of which should be lvalues:
2414 STR -- the saved data position.
2415 PAT -- the saved pattern position.
2416 LOW_REG, HIGH_REG -- the highest and lowest active registers.
2417 REGSTART, REGEND -- arrays of string positions.
2418 REG_INFO -- array of information about each subexpression.
2420 Also assumes the variables `fail_stack' and (if debugging), `bufp',
2421 `pend', `string1', `size1', `string2', and `size2'. */
2423 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
2425 DEBUG_STATEMENT (fail_stack_elt_t failure_id;) \
2427 const unsigned char *string_temp; \
2429 assert (!FAIL_STACK_EMPTY ()); \
2431 /* Remove failure points and point to how many regs pushed. */ \
2432 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
2433 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
2434 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
2436 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
2438 DEBUG_POP (&failure_id); \
2439 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
2441 /* If the saved string location is NULL, it came from an \
2442 on_failure_keep_string_jump opcode, and we want to throw away the \
2443 saved NULL, thus retaining our current position in the string. */ \
2444 string_temp = POP_FAILURE_ITEM (); \
2445 if (string_temp != NULL) \
2446 str = (const char *) string_temp; \
2448 DEBUG_PRINT2 (" Popping string 0x%x: `", str); \
2449 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
2450 DEBUG_PRINT1 ("'\n"); \
2452 pat = (unsigned char *) POP_FAILURE_ITEM (); \
2453 DEBUG_PRINT2 (" Popping pattern 0x%x: ", pat); \
2454 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
2456 /* Restore register info. */ \
2457 high_reg = (unsigned) POP_FAILURE_ITEM (); \
2458 DEBUG_PRINT2 (" Popping high active reg: %d\n", high_reg); \
2460 low_reg = (unsigned) POP_FAILURE_ITEM (); \
2461 DEBUG_PRINT2 (" Popping low active reg: %d\n", low_reg); \
2463 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
2465 DEBUG_PRINT2 (" Popping reg: %d\n", this_reg); \
2467 reg_info[this_reg].word = POP_FAILURE_ITEM (); \
2468 DEBUG_PRINT2 (" info: 0x%x\n", reg_info[this_reg]); \
2470 regend[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2471 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \
2473 regstart[this_reg] = (const char *) POP_FAILURE_ITEM (); \
2474 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \
2476 } /* POP_FAILURE_POINT */
2478 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2479 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
2480 characters can start a string that matches the pattern. This fastmap
2481 is used by re_search to skip quickly over impossible starting points.
2483 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2484 area as BUFP->fastmap.
2486 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2489 Returns 0 if we succeed, -2 if an internal error. */
2492 re_compile_fastmap (bufp)
2493 struct re_pattern_buffer *bufp;
2496 fail_stack_type fail_stack;
2497 #ifndef REGEX_MALLOC
2500 /* We don't push any register information onto the failure stack. */
2501 unsigned num_regs = 0;
2503 register char *fastmap = bufp->fastmap;
2504 unsigned char *pattern = bufp->buffer;
2505 unsigned long size = bufp->used;
2506 const unsigned char *p = pattern;
2507 register unsigned char *pend = pattern + size;
2509 /* Assume that each path through the pattern can be null until
2510 proven otherwise. We set this false at the bottom of switch
2511 statement, to which we get only if a particular path doesn't
2512 match the empty string. */
2513 boolean path_can_be_null = true;
2515 /* We aren't doing a `succeed_n' to begin with. */
2516 boolean succeed_n_p = false;
2518 assert (fastmap != NULL && p != NULL);
2521 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
2522 bufp->fastmap_accurate = 1; /* It will be when we're done. */
2523 bufp->can_be_null = 0;
2525 while (p != pend || !FAIL_STACK_EMPTY ())
2529 bufp->can_be_null |= path_can_be_null;
2531 /* Reset for next path. */
2532 path_can_be_null = true;
2534 p = fail_stack.stack[--fail_stack.avail];
2537 /* We should never be about to go beyond the end of the pattern. */
2540 #ifdef SWITCH_ENUM_BUG
2541 switch ((int) ((re_opcode_t) *p++))
2543 switch ((re_opcode_t) *p++)
2547 /* I guess the idea here is to simply not bother with a fastmap
2548 if a backreference is used, since it's too hard to figure out
2549 the fastmap for the corresponding group. Setting
2550 `can_be_null' stops `re_search_2' from using the fastmap, so
2551 that is all we do. */
2553 bufp->can_be_null = 1;
2557 /* Following are the cases which match a character. These end
2566 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2567 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
2573 /* Chars beyond end of map must be allowed. */
2574 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
2577 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2578 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
2584 for (j = 0; j < (1 << BYTEWIDTH); j++)
2585 if (SYNTAX (j) == Sword)
2591 for (j = 0; j < (1 << BYTEWIDTH); j++)
2592 if (SYNTAX (j) != Sword)
2598 /* `.' matches anything ... */
2599 for (j = 0; j < (1 << BYTEWIDTH); j++)
2602 /* ... except perhaps newline. */
2603 if (!(bufp->syntax & RE_DOT_NEWLINE))
2606 /* Return if we have already set `can_be_null'; if we have,
2607 then the fastmap is irrelevant. Something's wrong here. */
2608 else if (bufp->can_be_null)
2611 /* Otherwise, have to check alternative paths. */
2618 for (j = 0; j < (1 << BYTEWIDTH); j++)
2619 if (SYNTAX (j) == (enum syntaxcode) k)
2626 for (j = 0; j < (1 << BYTEWIDTH); j++)
2627 if (SYNTAX (j) != (enum syntaxcode) k)
2632 /* All cases after this match the empty string. These end with
2640 #endif /* not emacs */
2652 case push_dummy_failure:
2657 case pop_failure_jump:
2658 case maybe_pop_jump:
2661 case dummy_failure_jump:
2662 EXTRACT_NUMBER_AND_INCR (j, p);
2667 /* Jump backward implies we just went through the body of a
2668 loop and matched nothing. Opcode jumped to should be
2669 `on_failure_jump' or `succeed_n'. Just treat it like an
2670 ordinary jump. For a * loop, it has pushed its failure
2671 point already; if so, discard that as redundant. */
2672 if ((re_opcode_t) *p != on_failure_jump
2673 && (re_opcode_t) *p != succeed_n)
2677 EXTRACT_NUMBER_AND_INCR (j, p);
2680 /* If what's on the stack is where we are now, pop it. */
2681 if (!FAIL_STACK_EMPTY ()
2682 && fail_stack.stack[fail_stack.avail - 1] == p)
2688 case on_failure_jump:
2689 case on_failure_keep_string_jump:
2690 handle_on_failure_jump:
2691 EXTRACT_NUMBER_AND_INCR (j, p);
2693 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
2694 end of the pattern. We don't want to push such a point,
2695 since when we restore it above, entering the switch will
2696 increment `p' past the end of the pattern. We don't need
2697 to push such a point since we obviously won't find any more
2698 fastmap entries beyond `pend'. Such a pattern can match
2699 the null string, though. */
2702 if (!PUSH_PATTERN_OP (p + j, fail_stack))
2706 bufp->can_be_null = 1;
2710 EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */
2711 succeed_n_p = false;
2718 /* Get to the number of times to succeed. */
2721 /* Increment p past the n for when k != 0. */
2722 EXTRACT_NUMBER_AND_INCR (k, p);
2726 succeed_n_p = true; /* Spaghetti code alert. */
2727 goto handle_on_failure_jump;
2744 abort (); /* We have listed all the cases. */
2747 /* Getting here means we have found the possible starting
2748 characters for one path of the pattern -- and that the empty
2749 string does not match. We need not follow this path further.
2750 Instead, look at the next alternative (remembered on the
2751 stack), or quit if no more. The test at the top of the loop
2752 does these things. */
2753 path_can_be_null = false;
2757 /* Set `can_be_null' for the last path (also the first path, if the
2758 pattern is empty). */
2759 bufp->can_be_null |= path_can_be_null;
2761 } /* re_compile_fastmap */
2763 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
2764 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
2765 this memory for recording register information. STARTS and ENDS
2766 must be allocated using the malloc library routine, and must each
2767 be at least NUM_REGS * sizeof (regoff_t) bytes long.
2769 If NUM_REGS == 0, then subsequent matches should allocate their own
2772 Unless this function is called, the first search or match using
2773 PATTERN_BUFFER will allocate its own register data, without
2774 freeing the old data. */
2777 re_set_registers (bufp, regs, num_regs, starts, ends)
2778 struct re_pattern_buffer *bufp;
2779 struct re_registers *regs;
2781 regoff_t *starts, *ends;
2785 bufp->regs_allocated = REGS_REALLOCATE;
2786 regs->num_regs = num_regs;
2787 regs->start = starts;
2792 bufp->regs_allocated = REGS_UNALLOCATED;
2794 regs->start = regs->end = (regoff_t) 0;
2798 /* Searching routines. */
2800 /* Like re_search_2, below, but only one string is specified, and
2801 doesn't let you say where to stop matching. */
2804 re_search (bufp, string, size, startpos, range, regs)
2805 struct re_pattern_buffer *bufp;
2807 int size, startpos, range;
2808 struct re_registers *regs;
2810 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
2815 /* Using the compiled pattern in BUFP->buffer, first tries to match the
2816 virtual concatenation of STRING1 and STRING2, starting first at index
2817 STARTPOS, then at STARTPOS + 1, and so on.
2819 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
2821 RANGE is how far to scan while trying to match. RANGE = 0 means try
2822 only at STARTPOS; in general, the last start tried is STARTPOS +
2825 In REGS, return the indices of the virtual concatenation of STRING1
2826 and STRING2 that matched the entire BUFP->buffer and its contained
2829 Do not consider matching one past the index STOP in the virtual
2830 concatenation of STRING1 and STRING2.
2832 We return either the position in the strings at which the match was
2833 found, -1 if no match, or -2 if error (such as failure
2837 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
2838 struct re_pattern_buffer *bufp;
2839 const char *string1, *string2;
2843 struct re_registers *regs;
2847 register char *fastmap = bufp->fastmap;
2848 register char *translate = bufp->translate;
2849 int total_size = size1 + size2;
2850 int endpos = startpos + range;
2852 /* Check for out-of-range STARTPOS. */
2853 if (startpos < 0 || startpos > total_size)
2856 /* Fix up RANGE if it might eventually take us outside
2857 the virtual concatenation of STRING1 and STRING2. */
2859 range = -1 - startpos;
2860 else if (endpos > total_size)
2861 range = total_size - startpos;
2863 /* Update the fastmap now if not correct already. */
2864 if (fastmap && !bufp->fastmap_accurate)
2865 if (re_compile_fastmap (bufp) == -2)
2868 /* If the search isn't to be a backwards one, don't waste time in a
2869 long search for a pattern that says it is anchored. */
2870 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf
2881 /* If a fastmap is supplied, skip quickly over characters that
2882 cannot be the start of a match. If the pattern can match the
2883 null string, however, we don't need to skip characters; we want
2884 the first null string. */
2885 if (fastmap && startpos < total_size && !bufp->can_be_null)
2887 if (range > 0) /* Searching forwards. */
2889 register const char *d;
2890 register int lim = 0;
2893 if (startpos < size1 && startpos + range >= size1)
2894 lim = range - (size1 - startpos);
2896 d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
2898 /* Written out as an if-else to avoid testing `translate'
2902 && !fastmap[(unsigned char) translate[*d++]])
2905 while (range > lim && !fastmap[(unsigned char) *d++])
2908 startpos += irange - range;
2910 else /* Searching backwards. */
2912 register char c = (size1 == 0 || startpos >= size1
2913 ? string2[startpos - size1]
2914 : string1[startpos]);
2916 if (!fastmap[TRANSLATE (c)])
2921 /* If can't match the null string, and that's all we have left, fail. */
2922 if (range >= 0 && startpos == total_size && fastmap
2923 && !bufp->can_be_null)
2926 val = re_match_2 (bufp, string1, size1, string2, size2,
2927 startpos, regs, stop);
2951 /* Declarations and macros for re_match_2. */
2953 static int bcmp_translate ();
2954 static boolean alt_match_null_string_p (),
2955 common_op_match_null_string_p (),
2956 group_match_null_string_p ();
2958 /* Structure for per-register (a.k.a. per-group) information.
2959 This must not be longer than one word, because we push this value
2960 onto the failure stack. Other register information, such as the
2961 starting and ending positions (which are addresses), and the list of
2962 inner groups (which is a bits list) are maintained in separate
2965 We are making a (strictly speaking) nonportable assumption here: that
2966 the compiler will pack our bit fields into something that fits into
2967 the type of `word', i.e., is something that fits into one item on the
2971 fail_stack_elt_t word;
2974 /* This field is one if this group can match the empty string,
2975 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
2976 #define MATCH_NULL_UNSET_VALUE 3
2977 unsigned match_null_string_p : 2;
2978 unsigned is_active : 1;
2979 unsigned matched_something : 1;
2980 unsigned ever_matched_something : 1;
2982 } register_info_type;
2984 #define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
2985 #define IS_ACTIVE(R) ((R).bits.is_active)
2986 #define MATCHED_SOMETHING(R) ((R).bits.matched_something)
2987 #define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
2990 /* Call this when have matched something; it sets `matched' flags for the
2991 registers corresponding to the group of which we currently are inside.
2992 Also records whether this group ever matched something. We only care
2993 about this information at `stop_memory', and then only about the
2994 previous time through the loop (if the group is starred or whatever).
2995 So it is ok to clear all the nonactive registers here. */
2996 #define SET_REGS_MATCHED() \
3000 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
3002 MATCHED_SOMETHING (reg_info[r]) \
3003 = EVER_MATCHED_SOMETHING (reg_info[r]) \
3010 /* This converts PTR, a pointer into one of the search strings `string1'
3011 and `string2' into an offset from the beginning of that string. */
3012 #define POINTER_TO_OFFSET(ptr) \
3013 (FIRST_STRING_P (ptr) ? (ptr) - string1 : (ptr) - string2 + size1)
3015 /* Registers are set to a sentinel when they haven't yet matched. */
3016 #define REG_UNSET_VALUE ((char *) -1)
3017 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
3020 /* Macros for dealing with the split strings in re_match_2. */
3022 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
3024 /* Call before fetching a character with *d. This switches over to
3025 string2 if necessary. */
3026 #define PREFETCH() \
3029 /* End of string2 => fail. */ \
3030 if (dend == end_match_2) \
3032 /* End of string1 => advance to string2. */ \
3034 dend = end_match_2; \
3038 /* Test if at very beginning or at very end of the virtual concatenation
3039 of `string1' and `string2'. If only one string, it's `string2'. */
3040 #define AT_STRINGS_BEG() (d == (size1 ? string1 : string2) || !size2)
3041 #define AT_STRINGS_END() (d == end2)
3044 /* Test if D points to a character which is word-constituent. We have
3045 two special cases to check for: if past the end of string1, look at
3046 the first character in string2; and if before the beginning of
3047 string2, look at the last character in string1.
3049 Assumes `string1' exists, so use in conjunction with AT_STRINGS_BEG (). */
3050 #define LETTER_P(d) \
3051 (SYNTAX ((d) == end1 ? *string2 \
3052 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) == Sword)
3054 /* Test if the character before D and the one at D differ with respect
3055 to being word-constituent. */
3056 #define AT_WORD_BOUNDARY(d) \
3057 (AT_STRINGS_BEG () || AT_STRINGS_END () || LETTER_P (d - 1) != LETTER_P (d))
3060 /* Free everything we malloc. */
3062 #define FREE_VAR(var) if (var) free (var); var = NULL
3063 #define FREE_VARIABLES() \
3065 FREE_VAR (fail_stack.stack); \
3066 FREE_VAR (regstart); \
3067 FREE_VAR (regend); \
3068 FREE_VAR (old_regstart); \
3069 FREE_VAR (old_regend); \
3070 FREE_VAR (best_regstart); \
3071 FREE_VAR (best_regend); \
3072 FREE_VAR (reg_info); \
3073 FREE_VAR (reg_dummy); \
3074 FREE_VAR (reg_info_dummy); \
3076 #else /* not REGEX_MALLOC */
3077 /* Some MIPS systems (at least) want this to free alloca'd storage. */
3078 #define FREE_VARIABLES() alloca (0)
3079 #endif /* not REGEX_MALLOC */
3082 /* These values must meet several constraints. They must not be valid
3083 register values; since we have a limit of 255 registers (because
3084 we use only one byte in the pattern for the register number), we can
3085 use numbers larger than 255. They must differ by 1, because of
3086 NUM_FAILURE_ITEMS above. And the value for the lowest register must
3087 be larger than the value for the highest register, so we do not try
3088 to actually save any registers when none are active. */
3089 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
3090 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
3092 /* Matching routines. */
3094 #ifndef emacs /* Emacs never uses this. */
3095 /* re_match is like re_match_2 except it takes only a single string. */
3098 re_match (bufp, string, size, pos, regs)
3099 struct re_pattern_buffer *bufp;
3102 struct re_registers *regs;
3104 return re_match_2 (bufp, NULL, 0, string, size, pos, regs, size);
3106 #endif /* not emacs */
3109 /* re_match_2 matches the compiled pattern in BUFP against the
3110 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
3111 and SIZE2, respectively). We start matching at POS, and stop
3114 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
3115 store offsets for the substring each group matched in REGS. See the
3116 documentation for exactly how many groups we fill.
3118 We return -1 if no match, -2 if an internal error (such as the
3119 failure stack overflowing). Otherwise, we return the length of the
3120 matched substring. */
3123 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
3124 struct re_pattern_buffer *bufp;
3125 const char *string1, *string2;
3128 struct re_registers *regs;
3131 /* General temporaries. */
3135 /* Just past the end of the corresponding string. */
3136 const char *end1, *end2;
3138 /* Pointers into string1 and string2, just past the last characters in
3139 each to consider matching. */
3140 const char *end_match_1, *end_match_2;
3142 /* Where we are in the data, and the end of the current string. */
3143 const char *d, *dend;
3145 /* Where we are in the pattern, and the end of the pattern. */
3146 unsigned char *p = bufp->buffer;
3147 register unsigned char *pend = p + bufp->used;
3149 /* We use this to map every character in the string. */
3150 char *translate = bufp->translate;
3152 /* Failure point stack. Each place that can handle a failure further
3153 down the line pushes a failure point on this stack. It consists of
3154 restart, regend, and reg_info for all registers corresponding to
3155 the subexpressions we're currently inside, plus the number of such
3156 registers, and, finally, two char *'s. The first char * is where
3157 to resume scanning the pattern; the second one is where to resume
3158 scanning the strings. If the latter is zero, the failure point is
3159 a ``dummy''; if a failure happens and the failure point is a dummy,
3160 it gets discarded and the next next one is tried. */
3161 fail_stack_type fail_stack;
3163 static unsigned failure_id = 0;
3166 /* We fill all the registers internally, independent of what we
3167 return, for use in backreferences. The number here includes
3168 an element for register zero. */
3169 unsigned num_regs = bufp->re_nsub + 1;
3171 /* The currently active registers. */
3172 unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3173 unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3175 /* Information on the contents of registers. These are pointers into
3176 the input strings; they record just what was matched (on this
3177 attempt) by a subexpression part of the pattern, that is, the
3178 regnum-th regstart pointer points to where in the pattern we began
3179 matching and the regnum-th regend points to right after where we
3180 stopped matching the regnum-th subexpression. (The zeroth register
3181 keeps track of what the whole pattern matches.) */
3182 const char **regstart, **regend;
3184 /* If a group that's operated upon by a repetition operator fails to
3185 match anything, then the register for its start will need to be
3186 restored because it will have been set to wherever in the string we
3187 are when we last see its open-group operator. Similarly for a
3189 const char **old_regstart, **old_regend;
3191 /* The is_active field of reg_info helps us keep track of which (possibly
3192 nested) subexpressions we are currently in. The matched_something
3193 field of reg_info[reg_num] helps us tell whether or not we have
3194 matched any of the pattern so far this time through the reg_num-th
3195 subexpression. These two fields get reset each time through any
3196 loop their register is in. */
3197 register_info_type *reg_info;
3199 /* The following record the register info as found in the above
3200 variables when we find a match better than any we've seen before.
3201 This happens as we backtrack through the failure points, which in
3202 turn happens only if we have not yet matched the entire string. */
3203 unsigned best_regs_set = false;
3204 const char **best_regstart, **best_regend;
3206 /* Logically, this is `best_regend[0]'. But we don't want to have to
3207 allocate space for that if we're not allocating space for anything
3208 else (see below). Also, we never need info about register 0 for
3209 any of the other register vectors, and it seems rather a kludge to
3210 treat `best_regend' differently than the rest. So we keep track of
3211 the end of the best match so far in a separate variable. We
3212 initialize this to NULL so that when we backtrack the first time
3213 and need to test it, it's not garbage. */
3214 const char *match_end = NULL;
3216 /* Used when we pop values we don't care about. */
3217 const char **reg_dummy;
3218 register_info_type *reg_info_dummy;
3221 /* Counts the total number of registers pushed. */
3222 unsigned num_regs_pushed = 0;
3225 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
3229 /* Do not bother to initialize all the register variables if there are
3230 no groups in the pattern, as it takes a fair amount of time. If
3231 there are groups, we include space for register 0 (the whole
3232 pattern), even though we never use it, since it simplifies the
3233 array indexing. We should fix this. */
3236 regstart = REGEX_TALLOC (num_regs, const char *);
3237 regend = REGEX_TALLOC (num_regs, const char *);
3238 old_regstart = REGEX_TALLOC (num_regs, const char *);
3239 old_regend = REGEX_TALLOC (num_regs, const char *);
3240 best_regstart = REGEX_TALLOC (num_regs, const char *);
3241 best_regend = REGEX_TALLOC (num_regs, const char *);
3242 reg_info = REGEX_TALLOC (num_regs, register_info_type);
3243 reg_dummy = REGEX_TALLOC (num_regs, const char *);
3244 reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
3246 if (!(regstart && regend && old_regstart && old_regend && reg_info
3247 && best_regstart && best_regend && reg_dummy && reg_info_dummy))
3256 /* We must initialize all our variables to NULL, so that
3257 `FREE_VARIABLES' doesn't try to free them. Too bad this isn't
3258 Lisp, so we could have a list of variables. As it is, */
3259 regstart = regend = old_regstart = old_regend = best_regstart
3260 = best_regend = reg_dummy = NULL;
3261 reg_info = reg_info_dummy = (register_info_type *) NULL;
3263 #endif /* REGEX_MALLOC */
3265 /* The starting position is bogus. */
3266 if (pos < 0 || pos > size1 + size2)
3272 /* Initialize subexpression text positions to -1 to mark ones that no
3273 start_memory/stop_memory has been seen for. Also initialize the
3274 register information struct. */
3275 for (mcnt = 1; mcnt < num_regs; mcnt++)
3277 regstart[mcnt] = regend[mcnt]
3278 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
3280 REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
3281 IS_ACTIVE (reg_info[mcnt]) = 0;
3282 MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3283 EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3286 /* We move `string1' into `string2' if the latter's empty -- but not if
3287 `string1' is null. */
3288 if (size2 == 0 && string1 != NULL)
3295 end1 = string1 + size1;
3296 end2 = string2 + size2;
3298 /* Compute where to stop matching, within the two strings. */
3301 end_match_1 = string1 + stop;
3302 end_match_2 = string2;
3307 end_match_2 = string2 + stop - size1;
3310 /* `p' scans through the pattern as `d' scans through the data.
3311 `dend' is the end of the input string that `d' points within. `d'
3312 is advanced into the following input string whenever necessary, but
3313 this happens before fetching; therefore, at the beginning of the
3314 loop, `d' can be pointing at the end of a string, but it cannot
3316 if (size1 > 0 && pos <= size1)
3323 d = string2 + pos - size1;
3327 DEBUG_PRINT1 ("The compiled pattern is: ");
3328 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
3329 DEBUG_PRINT1 ("The string to match is: `");
3330 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
3331 DEBUG_PRINT1 ("'\n");
3333 /* This loops over pattern commands. It exits by returning from the
3334 function if the match is complete, or it drops through if the match
3335 fails at this starting point in the input data. */
3338 DEBUG_PRINT2 ("\n0x%x: ", p);
3341 { /* End of pattern means we might have succeeded. */
3342 DEBUG_PRINT1 ("End of pattern: ");
3343 /* If not end of string, try backtracking. Otherwise done. */
3344 if (d != end_match_2)
3346 DEBUG_PRINT1 ("backtracking.\n");
3348 if (!FAIL_STACK_EMPTY ())
3349 { /* More failure points to try. */
3350 boolean same_str_p = (FIRST_STRING_P (match_end)
3351 == MATCHING_IN_FIRST_STRING);
3353 /* If exceeds best match so far, save it. */
3355 || (same_str_p && d > match_end)
3356 || (!same_str_p && !MATCHING_IN_FIRST_STRING))
3358 best_regs_set = true;
3361 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
3363 for (mcnt = 1; mcnt < num_regs; mcnt++)
3365 best_regstart[mcnt] = regstart[mcnt];
3366 best_regend[mcnt] = regend[mcnt];
3372 /* If no failure points, don't restore garbage. */
3373 else if (best_regs_set)
3376 /* Restore best match. It may happen that `dend ==
3377 end_match_1' while the restored d is in string2.
3378 For example, the pattern `x.*y.*z' against the
3379 strings `x-' and `y-z-', if the two strings are
3380 not consecutive in memory. */
3382 dend = ((d >= string1 && d <= end1)
3383 ? end_match_1 : end_match_2);
3385 for (mcnt = 1; mcnt < num_regs; mcnt++)
3387 regstart[mcnt] = best_regstart[mcnt];
3388 regend[mcnt] = best_regend[mcnt];
3391 } /* d != end_match_2 */
3393 DEBUG_PRINT1 ("\nAccepting match.\n");
3395 /* If caller wants register contents data back, do it. */
3396 if (regs && !bufp->no_sub)
3398 /* Have the register data arrays been allocated? */
3399 if (bufp->regs_allocated == REGS_UNALLOCATED)
3400 { /* No. So allocate them with malloc. We need one
3401 extra element beyond `num_regs' for the `-1' marker
3403 regs->num_regs = MAX (RE_NREGS, num_regs + 1);
3404 regs->start = TALLOC (regs->num_regs, regoff_t);
3405 regs->end = TALLOC (regs->num_regs, regoff_t);
3406 if (regs->start == NULL || regs->end == NULL)
3408 bufp->regs_allocated = REGS_REALLOCATE;
3410 else if (bufp->regs_allocated == REGS_REALLOCATE)
3411 { /* Yes. If we need more elements than were already
3412 allocated, reallocate them. If we need fewer, just
3414 if (regs->num_regs < num_regs + 1)
3416 regs->num_regs = num_regs + 1;
3417 RETALLOC (regs->start, regs->num_regs, regoff_t);
3418 RETALLOC (regs->end, regs->num_regs, regoff_t);
3419 if (regs->start == NULL || regs->end == NULL)
3424 assert (bufp->regs_allocated == REGS_FIXED);
3426 /* Convert the pointer data in `regstart' and `regend' to
3427 indices. Register zero has to be set differently,
3428 since we haven't kept track of any info for it. */
3429 if (regs->num_regs > 0)
3431 regs->start[0] = pos;
3432 regs->end[0] = (MATCHING_IN_FIRST_STRING ? d - string1
3433 : d - string2 + size1);
3436 /* Go through the first `min (num_regs, regs->num_regs)'
3437 registers, since that is all we initialized. */
3438 for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++)
3440 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
3441 regs->start[mcnt] = regs->end[mcnt] = -1;
3444 regs->start[mcnt] = POINTER_TO_OFFSET (regstart[mcnt]);
3445 regs->end[mcnt] = POINTER_TO_OFFSET (regend[mcnt]);
3449 /* If the regs structure we return has more elements than
3450 were in the pattern, set the extra elements to -1. If
3451 we (re)allocated the registers, this is the case,
3452 because we always allocate enough to have at least one
3454 for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
3455 regs->start[mcnt] = regs->end[mcnt] = -1;
3456 } /* regs && !bufp->no_sub */
3459 DEBUG_PRINT2 ("%d registers pushed.\n", num_regs_pushed);
3461 mcnt = d - pos - (MATCHING_IN_FIRST_STRING
3465 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
3470 /* Otherwise match next pattern command. */
3471 #ifdef SWITCH_ENUM_BUG
3472 switch ((int) ((re_opcode_t) *p++))
3474 switch ((re_opcode_t) *p++)
3477 /* Ignore these. Used to ignore the n of succeed_n's which
3478 currently have n == 0. */
3480 DEBUG_PRINT1 ("EXECUTING no_op.\n");
3484 /* Match the next n pattern characters exactly. The following
3485 byte in the pattern defines n, and the n bytes after that
3486 are the characters to match. */
3489 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
3491 /* This is written out as an if-else so we don't waste time
3492 testing `translate' inside the loop. */
3498 if (translate[(unsigned char) *d++] != (char) *p++)
3508 if (*d++ != (char) *p++) goto fail;
3512 SET_REGS_MATCHED ();
3516 /* Match any character except possibly a newline or a null. */
3518 DEBUG_PRINT1 ("EXECUTING anychar.\n");
3522 if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
3523 || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
3526 SET_REGS_MATCHED ();
3527 DEBUG_PRINT2 (" Matched `%d'.\n", *d);
3535 register unsigned char c;
3536 boolean not = (re_opcode_t) *(p - 1) == charset_not;
3538 DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
3541 c = TRANSLATE (*d); /* The character to match. */
3543 /* Cast to `unsigned' instead of `unsigned char' in case the
3544 bit list is a full 32 bytes long. */
3545 if (c < (unsigned) (*p * BYTEWIDTH)
3546 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3551 if (!not) goto fail;
3553 SET_REGS_MATCHED ();
3559 /* The beginning of a group is represented by start_memory.
3560 The arguments are the register number in the next byte, and the
3561 number of groups inner to this one in the next. The text
3562 matched within the group is recorded (in the internal
3563 registers data structure) under the register number. */
3565 DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]);
3567 /* Find out if this group can match the empty string. */
3568 p1 = p; /* To send to group_match_null_string_p. */
3570 if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
3571 REG_MATCH_NULL_STRING_P (reg_info[*p])
3572 = group_match_null_string_p (&p1, pend, reg_info);
3574 /* Save the position in the string where we were the last time
3575 we were at this open-group operator in case the group is
3576 operated upon by a repetition operator, e.g., with `(a*)*b'
3577 against `ab'; then we want to ignore where we are now in
3578 the string in case this attempt to match fails. */
3579 old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3580 ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
3582 DEBUG_PRINT2 (" old_regstart: %d\n",
3583 POINTER_TO_OFFSET (old_regstart[*p]));
3586 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
3588 IS_ACTIVE (reg_info[*p]) = 1;
3589 MATCHED_SOMETHING (reg_info[*p]) = 0;
3591 /* This is the new highest active register. */
3592 highest_active_reg = *p;
3594 /* If nothing was active before, this is the new lowest active
3596 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3597 lowest_active_reg = *p;
3599 /* Move past the register number and inner group count. */
3604 /* The stop_memory opcode represents the end of a group. Its
3605 arguments are the same as start_memory's: the register
3606 number, and the number of inner groups. */
3608 DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
3610 /* We need to save the string position the last time we were at
3611 this close-group operator in case the group is operated
3612 upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
3613 against `aba'; then we want to ignore where we are now in
3614 the string in case this attempt to match fails. */
3615 old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3616 ? REG_UNSET (regend[*p]) ? d : regend[*p]
3618 DEBUG_PRINT2 (" old_regend: %d\n",
3619 POINTER_TO_OFFSET (old_regend[*p]));
3622 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
3624 /* This register isn't active anymore. */
3625 IS_ACTIVE (reg_info[*p]) = 0;
3627 /* If this was the only register active, nothing is active
3629 if (lowest_active_reg == highest_active_reg)
3631 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3632 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3635 { /* We must scan for the new highest active register, since
3636 it isn't necessarily one less than now: consider
3637 (a(b)c(d(e)f)g). When group 3 ends, after the f), the
3638 new highest active register is 1. */
3639 unsigned char r = *p - 1;
3640 while (r > 0 && !IS_ACTIVE (reg_info[r]))
3643 /* If we end up at register zero, that means that we saved
3644 the registers as the result of an `on_failure_jump', not
3645 a `start_memory', and we jumped to past the innermost
3646 `stop_memory'. For example, in ((.)*) we save
3647 registers 1 and 2 as a result of the *, but when we pop
3648 back to the second ), we are at the stop_memory 1.
3649 Thus, nothing is active. */
3652 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3653 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3656 highest_active_reg = r;
3659 /* If just failed to match something this time around with a
3660 group that's operated on by a repetition operator, try to
3661 force exit from the ``loop,'' and restore the register
3662 information for this group that we had before trying this
3664 if ((!MATCHED_SOMETHING (reg_info[*p])
3665 || (re_opcode_t) p[-3] == start_memory)
3668 boolean is_a_jump_n = false;
3672 switch ((re_opcode_t) *p1++)
3676 case pop_failure_jump:
3677 case maybe_pop_jump:
3679 case dummy_failure_jump:
3680 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3690 /* If the next operation is a jump backwards in the pattern
3691 to an on_failure_jump right before the start_memory
3692 corresponding to this stop_memory, exit from the loop
3693 by forcing a failure after pushing on the stack the
3694 on_failure_jump's jump in the pattern, and d. */
3695 if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
3696 && (re_opcode_t) p1[3] == start_memory && p1[4] == *p)
3698 /* If this group ever matched anything, then restore
3699 what its registers were before trying this last
3700 failed match, e.g., with `(a*)*b' against `ab' for
3701 regstart[1], and, e.g., with `((a*)*(b*)*)*'
3702 against `aba' for regend[3].
3704 Also restore the registers for inner groups for,
3705 e.g., `((a*)(b*))*' against `aba' (register 3 would
3706 otherwise get trashed). */
3708 if (EVER_MATCHED_SOMETHING (reg_info[*p]))
3712 EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
3714 /* Restore this and inner groups' (if any) registers. */
3715 for (r = *p; r < *p + *(p + 1); r++)
3717 regstart[r] = old_regstart[r];
3719 /* xx why this test? */
3720 if ((int) old_regend[r] >= (int) regstart[r])
3721 regend[r] = old_regend[r];
3725 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3726 PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
3732 /* Move past the register number and the inner group count. */
3737 /* \<digit> has been turned into a `duplicate' command which is
3738 followed by the numeric value of <digit> as the register number. */
3741 register const char *d2, *dend2;
3742 int regno = *p++; /* Get which register to match against. */
3743 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
3745 /* Can't back reference a group which we've never matched. */
3746 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
3749 /* Where in input to try to start matching. */
3750 d2 = regstart[regno];
3752 /* Where to stop matching; if both the place to start and
3753 the place to stop matching are in the same string, then
3754 set to the place to stop, otherwise, for now have to use
3755 the end of the first string. */
3757 dend2 = ((FIRST_STRING_P (regstart[regno])
3758 == FIRST_STRING_P (regend[regno]))
3759 ? regend[regno] : end_match_1);
3762 /* If necessary, advance to next segment in register
3766 if (dend2 == end_match_2) break;
3767 if (dend2 == regend[regno]) break;
3769 /* End of string1 => advance to string2. */
3771 dend2 = regend[regno];
3773 /* At end of register contents => success */
3774 if (d2 == dend2) break;
3776 /* If necessary, advance to next segment in data. */
3779 /* How many characters left in this segment to match. */
3782 /* Want how many consecutive characters we can match in
3783 one shot, so, if necessary, adjust the count. */
3784 if (mcnt > dend2 - d2)
3787 /* Compare that many; failure if mismatch, else move
3790 ? bcmp_translate (d, d2, mcnt, translate)
3791 : bcmp (d, d2, mcnt))
3793 d += mcnt, d2 += mcnt;
3799 /* begline matches the empty string at the beginning of the string
3800 (unless `not_bol' is set in `bufp'), and, if
3801 `newline_anchor' is set, after newlines. */
3803 DEBUG_PRINT1 ("EXECUTING begline.\n");
3805 if (AT_STRINGS_BEG ())
3807 if (!bufp->not_bol) break;
3809 else if (d[-1] == '\n' && bufp->newline_anchor)
3813 /* In all other cases, we fail. */
3817 /* endline is the dual of begline. */
3819 DEBUG_PRINT1 ("EXECUTING endline.\n");
3821 if (AT_STRINGS_END ())
3823 if (!bufp->not_eol) break;
3826 /* We have to ``prefetch'' the next character. */
3827 else if ((d == end1 ? *string2 : *d) == '\n'
3828 && bufp->newline_anchor)
3835 /* Match at the very beginning of the data. */
3837 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
3838 if (AT_STRINGS_BEG ())
3843 /* Match at the very end of the data. */
3845 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
3846 if (AT_STRINGS_END ())
3851 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
3852 pushes NULL as the value for the string on the stack. Then
3853 `pop_failure_point' will keep the current value for the
3854 string, instead of restoring it. To see why, consider
3855 matching `foo\nbar' against `.*\n'. The .* matches the foo;
3856 then the . fails against the \n. But the next thing we want
3857 to do is match the \n against the \n; if we restored the
3858 string value, we would be back at the foo.
3860 Because this is used only in specific cases, we don't need to
3861 check all the things that `on_failure_jump' does, to make
3862 sure the right things get saved on the stack. Hence we don't
3863 share its code. The only reason to push anything on the
3864 stack at all is that otherwise we would have to change
3865 `anychar's code to do something besides goto fail in this
3866 case; that seems worse than this. */
3867 case on_failure_keep_string_jump:
3868 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
3870 EXTRACT_NUMBER_AND_INCR (mcnt, p);
3871 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
3873 PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
3877 /* Uses of on_failure_jump:
3879 Each alternative starts with an on_failure_jump that points
3880 to the beginning of the next alternative. Each alternative
3881 except the last ends with a jump that in effect jumps past
3882 the rest of the alternatives. (They really jump to the
3883 ending jump of the following alternative, because tensioning
3884 these jumps is a hassle.)
3886 Repeats start with an on_failure_jump that points past both
3887 the repetition text and either the following jump or
3888 pop_failure_jump back to this on_failure_jump. */
3889 case on_failure_jump:
3891 DEBUG_PRINT1 ("EXECUTING on_failure_jump");
3893 EXTRACT_NUMBER_AND_INCR (mcnt, p);
3894 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
3896 /* If this on_failure_jump comes right before a group (i.e.,
3897 the original * applied to a group), save the information
3898 for that group and all inner ones, so that if we fail back
3899 to this point, the group's information will be correct.
3900 For example, in \(a*\)*\1, we only need the preceding group,
3901 and in \(\(a*\)b*\)\2, we need the inner group. */
3903 /* We can't use `p' to check ahead because we push
3904 a failure point to `p + mcnt' after we do this. */
3907 /* We need to skip no_op's before we look for the
3908 start_memory in case this on_failure_jump is happening as
3909 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
3911 while (p1 < pend && (re_opcode_t) *p1 == no_op)
3914 if (p1 < pend && (re_opcode_t) *p1 == start_memory)
3916 /* We have a new highest active register now. This will
3917 get reset at the start_memory we are about to get to,
3918 but we will have saved all the registers relevant to
3919 this repetition op, as described above. */
3920 highest_active_reg = *(p1 + 1) + *(p1 + 2);
3921 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3922 lowest_active_reg = *(p1 + 1);
3925 DEBUG_PRINT1 (":\n");
3926 PUSH_FAILURE_POINT (p + mcnt, d, -2);
3930 /* A smart repeat ends with a maybe_pop_jump.
3931 We change it either to a pop_failure_jump or a jump. */
3932 case maybe_pop_jump:
3933 EXTRACT_NUMBER_AND_INCR (mcnt, p);
3934 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
3936 register unsigned char *p2 = p;
3938 /* Compare the beginning of the repeat with what in the
3939 pattern follows its end. If we can establish that there
3940 is nothing that they would both match, i.e., that we
3941 would have to backtrack because of (as in, e.g., `a*a')
3942 then we can change to pop_failure_jump, because we'll
3943 never have to backtrack.
3945 This is not true in the case of alternatives: in
3946 `(a|ab)*' we do need to backtrack to the `ab' alternative
3947 (e.g., if the string was `ab'). But instead of trying to
3948 detect that here, the alternative has put on a dummy
3949 failure point which is what we will end up popping. */
3951 /* Skip over open/close-group commands. */
3952 while (p2 + 2 < pend
3953 && ((re_opcode_t) *p2 == stop_memory
3954 || (re_opcode_t) *p2 == start_memory))
3955 p2 += 3; /* Skip over args, too. */
3957 /* If we're at the end of the pattern, we can change. */
3960 p[-3] = (unsigned char) pop_failure_jump;
3962 (" End of pattern: change to `pop_failure_jump'.\n");
3965 else if ((re_opcode_t) *p2 == exactn
3966 || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
3968 register unsigned char c
3969 = *p2 == (unsigned char) endline ? '\n' : p2[2];
3972 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
3973 to the `maybe_finalize_jump' of this case. Examine what
3975 if ((re_opcode_t) p1[3] == exactn && p1[5] != c)
3976 p[-3] = (unsigned char) pop_failure_jump;
3977 else if ((re_opcode_t) p1[3] == charset
3978 || (re_opcode_t) p1[3] == charset_not)
3980 int not = (re_opcode_t) p1[3] == charset_not;
3982 if (c < (unsigned char) (p1[4] * BYTEWIDTH)
3983 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3986 /* `not' is equal to 1 if c would match, which means
3987 that we can't change to pop_failure_jump. */
3990 p[-3] = (unsigned char) pop_failure_jump;
3992 (" No match: change to `pop_failure_jump'.\n");
3998 p -= 2; /* Point at relative address again. */
3999 if ((re_opcode_t) p[-1] != pop_failure_jump)
4001 p[-1] = (unsigned char) jump;
4002 goto unconditional_jump;
4004 /* Note fall through. */
4007 /* The end of a simple repeat has a pop_failure_jump back to
4008 its matching on_failure_jump, where the latter will push a
4009 failure point. The pop_failure_jump takes off failure
4010 points put on by this pop_failure_jump's matching
4011 on_failure_jump; we got through the pattern to here from the
4012 matching on_failure_jump, so didn't fail. */
4013 case pop_failure_jump:
4015 /* We need to pass separate storage for the lowest and
4016 highest registers, even though we don't care about the
4017 actual values. Otherwise, we will restore only one
4018 register from the stack, since lowest will == highest in
4019 `pop_failure_point'. */
4020 unsigned dummy_low_reg, dummy_high_reg;
4021 unsigned char *pdummy;
4024 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
4025 POP_FAILURE_POINT (sdummy, pdummy,
4026 dummy_low_reg, dummy_high_reg,
4027 reg_dummy, reg_dummy, reg_info_dummy);
4029 /* Note fall through. */
4032 /* Unconditionally jump (without popping any failure points). */
4035 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
4036 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
4037 p += mcnt; /* Do the jump. */
4038 DEBUG_PRINT2 ("(to 0x%x).\n", p);
4042 /* We need this opcode so we can detect where alternatives end
4043 in `group_match_null_string_p' et al. */
4045 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
4046 goto unconditional_jump;
4049 /* Normally, the on_failure_jump pushes a failure point, which
4050 then gets popped at pop_failure_jump. We will end up at
4051 pop_failure_jump, also, and with a pattern of, say, `a+', we
4052 are skipping over the on_failure_jump, so we have to push
4053 something meaningless for pop_failure_jump to pop. */
4054 case dummy_failure_jump:
4055 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
4056 /* It doesn't matter what we push for the string here. What
4057 the code at `fail' tests is the value for the pattern. */
4058 PUSH_FAILURE_POINT (0, 0, -2);
4059 goto unconditional_jump;
4062 /* At the end of an alternative, we need to push a dummy failure
4063 point in case we are followed by a pop_failure_jump', because
4064 we don't want the failure point for the alternative to be
4065 popped. For example, matching `(a|ab)*' against `aab'
4066 requires that we match the `ab' alternative. */
4067 case push_dummy_failure:
4068 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
4069 /* See comments just above at `dummy_failure_jump' about the
4071 PUSH_FAILURE_POINT (0, 0, -2);
4074 /* Have to succeed matching what follows at least n times.
4075 After that, handle like `on_failure_jump'. */
4077 EXTRACT_NUMBER (mcnt, p + 2);
4078 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
4081 /* Originally, this is how many times we HAVE to succeed. */
4086 STORE_NUMBER_AND_INCR (p, mcnt);
4087 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p, mcnt);
4091 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n", p+2);
4092 p[2] = (unsigned char) no_op;
4093 p[3] = (unsigned char) no_op;
4099 EXTRACT_NUMBER (mcnt, p + 2);
4100 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
4102 /* Originally, this is how many times we CAN jump. */
4106 STORE_NUMBER (p + 2, mcnt);
4107 goto unconditional_jump;
4109 /* If don't have to jump any more, skip over the rest of command. */
4116 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
4118 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4120 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4121 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1, mcnt);
4122 STORE_NUMBER (p1, mcnt);
4127 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
4128 if (AT_WORD_BOUNDARY (d))
4133 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
4134 if (AT_WORD_BOUNDARY (d))
4139 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
4140 if (LETTER_P (d) && (AT_STRINGS_BEG () || !LETTER_P (d - 1)))
4145 DEBUG_PRINT1 ("EXECUTING wordend.\n");
4146 if (!AT_STRINGS_BEG () && LETTER_P (d - 1)
4147 && (!LETTER_P (d) || AT_STRINGS_END ()))
4154 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
4155 if (PTR_CHAR_POS ((unsigned char *) d) >= point)
4160 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4161 if (PTR_CHAR_POS ((unsigned char *) d) != point)
4166 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
4167 if (PTR_CHAR_POS ((unsigned char *) d) <= point)
4170 #else /* not emacs19 */
4172 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4173 if (PTR_CHAR_POS ((unsigned char *) d) + 1 != point)
4176 #endif /* not emacs19 */
4179 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
4184 DEBUG_PRINT1 ("EXECUTING wordchar.\n");
4188 if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail;
4189 SET_REGS_MATCHED ();
4193 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
4195 goto matchnotsyntax;
4198 DEBUG_PRINT1 ("EXECUTING notwordchar.\n");
4200 matchnotsyntax: /* We goto here from notsyntaxspec. */
4202 if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail;
4203 SET_REGS_MATCHED ();
4206 #else /* not emacs */
4208 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
4212 SET_REGS_MATCHED ();
4216 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
4220 SET_REGS_MATCHED ();
4222 #endif /* not emacs */
4227 continue; /* Successfully executed one pattern command; keep going. */
4230 /* We goto here if a matching operation fails. */
4232 if (!FAIL_STACK_EMPTY ())
4233 { /* A restart point is known. Restore to that state. */
4234 DEBUG_PRINT1 ("\nFAIL:\n");
4235 POP_FAILURE_POINT (d, p,
4236 lowest_active_reg, highest_active_reg,
4237 regstart, regend, reg_info);
4239 /* If this failure point is a dummy, try the next one. */
4243 /* If we failed to the end of the pattern, don't examine *p. */
4247 boolean is_a_jump_n = false;
4249 /* If failed to a backwards jump that's part of a repetition
4250 loop, need to pop this failure point and use the next one. */
4251 switch ((re_opcode_t) *p)
4255 case maybe_pop_jump:
4256 case pop_failure_jump:
4259 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4262 if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
4264 && (re_opcode_t) *p1 == on_failure_jump))
4272 if (d >= string1 && d <= end1)
4276 break; /* Matching at this starting point really fails. */
4280 goto restore_best_regs;
4284 return -1; /* Failure to match. */
4287 /* Subroutine definitions for re_match_2. */
4290 /* We are passed P pointing to a register number after a start_memory.
4292 Return true if the pattern up to the corresponding stop_memory can
4293 match the empty string, and false otherwise.
4295 If we find the matching stop_memory, sets P to point to one past its number.
4296 Otherwise, sets P to an undefined byte less than or equal to END.
4298 We don't handle duplicates properly (yet). */
4301 group_match_null_string_p (p, end, reg_info)
4302 unsigned char **p, *end;
4303 register_info_type *reg_info;
4306 /* Point to after the args to the start_memory. */
4307 unsigned char *p1 = *p + 2;
4311 /* Skip over opcodes that can match nothing, and return true or
4312 false, as appropriate, when we get to one that can't, or to the
4313 matching stop_memory. */
4315 switch ((re_opcode_t) *p1)
4317 /* Could be either a loop or a series of alternatives. */
4318 case on_failure_jump:
4320 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4322 /* If the next operation is not a jump backwards in the
4327 /* Go through the on_failure_jumps of the alternatives,
4328 seeing if any of the alternatives cannot match nothing.
4329 The last alternative starts with only a jump,
4330 whereas the rest start with on_failure_jump and end
4331 with a jump, e.g., here is the pattern for `a|b|c':
4333 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
4334 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
4337 So, we have to first go through the first (n-1)
4338 alternatives and then deal with the last one separately. */
4341 /* Deal with the first (n-1) alternatives, which start
4342 with an on_failure_jump (see above) that jumps to right
4343 past a jump_past_alt. */
4345 while ((re_opcode_t) p1[mcnt-3] == jump_past_alt)
4347 /* `mcnt' holds how many bytes long the alternative
4348 is, including the ending `jump_past_alt' and
4351 if (!alt_match_null_string_p (p1, p1 + mcnt - 3,
4355 /* Move to right after this alternative, including the
4359 /* Break if it's the beginning of an n-th alternative
4360 that doesn't begin with an on_failure_jump. */
4361 if ((re_opcode_t) *p1 != on_failure_jump)
4364 /* Still have to check that it's not an n-th
4365 alternative that starts with an on_failure_jump. */
4367 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4368 if ((re_opcode_t) p1[mcnt-3] != jump_past_alt)
4370 /* Get to the beginning of the n-th alternative. */
4376 /* Deal with the last alternative: go back and get number
4377 of the `jump_past_alt' just before it. `mcnt' contains
4378 the length of the alternative. */
4379 EXTRACT_NUMBER (mcnt, p1 - 2);
4381 if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info))
4384 p1 += mcnt; /* Get past the n-th alternative. */
4390 assert (p1[1] == **p);
4396 if (!common_op_match_null_string_p (&p1, end, reg_info))
4399 } /* while p1 < end */
4402 } /* group_match_null_string_p */
4405 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
4406 It expects P to be the first byte of a single alternative and END one
4407 byte past the last. The alternative can contain groups. */
4410 alt_match_null_string_p (p, end, reg_info)
4411 unsigned char *p, *end;
4412 register_info_type *reg_info;
4415 unsigned char *p1 = p;
4419 /* Skip over opcodes that can match nothing, and break when we get
4420 to one that can't. */
4422 switch ((re_opcode_t) *p1)
4425 case on_failure_jump:
4427 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4432 if (!common_op_match_null_string_p (&p1, end, reg_info))
4435 } /* while p1 < end */
4438 } /* alt_match_null_string_p */
4441 /* Deals with the ops common to group_match_null_string_p and
4442 alt_match_null_string_p.
4444 Sets P to one after the op and its arguments, if any. */
4447 common_op_match_null_string_p (p, end, reg_info)
4448 unsigned char **p, *end;
4449 register_info_type *reg_info;
4454 unsigned char *p1 = *p;
4456 switch ((re_opcode_t) *p1++)
4476 assert (reg_no > 0 && reg_no <= MAX_REGNUM);
4477 ret = group_match_null_string_p (&p1, end, reg_info);
4479 /* Have to set this here in case we're checking a group which
4480 contains a group and a back reference to it. */
4482 if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
4483 REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
4489 /* If this is an optimized succeed_n for zero times, make the jump. */
4491 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4499 /* Get to the number of times to succeed. */
4501 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4506 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4514 if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
4522 /* All other opcodes mean we cannot match the empty string. */
4528 } /* common_op_match_null_string_p */
4531 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
4532 bytes; nonzero otherwise. */
4535 bcmp_translate (s1, s2, len, translate)
4536 unsigned char *s1, *s2;
4540 register unsigned char *p1 = s1, *p2 = s2;
4543 if (translate[*p1++] != translate[*p2++]) return 1;
4549 /* Entry points for GNU code. */
4551 /* re_compile_pattern is the GNU regular expression compiler: it
4552 compiles PATTERN (of length SIZE) and puts the result in BUFP.
4553 Returns 0 if the pattern was valid, otherwise an error string.
4555 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
4556 are set in BUFP on entry.
4558 We call regex_compile to do the actual compilation. */
4561 re_compile_pattern (pattern, length, bufp)
4562 const char *pattern;
4564 struct re_pattern_buffer *bufp;
4568 /* GNU code is written to assume at least RE_NREGS registers will be set
4569 (and at least one extra will be -1). */
4570 bufp->regs_allocated = REGS_UNALLOCATED;
4572 /* And GNU code determines whether or not to get register information
4573 by passing null for the REGS argument to re_match, etc., not by
4577 /* Match anchors at newline. */
4578 bufp->newline_anchor = 1;
4580 ret = regex_compile (pattern, length, re_syntax_options, bufp);
4582 return re_error_msg[(int) ret];
4585 /* Entry points compatible with 4.2 BSD regex library. We don't define
4586 them if this is an Emacs or POSIX compilation. */
4588 #if !defined (emacs) && !defined (_POSIX_SOURCE)
4590 /* BSD has one and only one pattern buffer. */
4591 static struct re_pattern_buffer re_comp_buf;
4601 if (!re_comp_buf.buffer)
4602 return "No previous regular expression";
4606 if (!re_comp_buf.buffer)
4608 re_comp_buf.buffer = (unsigned char *) malloc (200);
4609 if (re_comp_buf.buffer == NULL)
4610 return "Memory exhausted";
4611 re_comp_buf.allocated = 200;
4613 re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
4614 if (re_comp_buf.fastmap == NULL)
4615 return "Memory exhausted";
4618 /* Since `re_exec' always passes NULL for the `regs' argument, we
4619 don't need to initialize the pattern buffer fields which affect it. */
4621 /* Match anchors at newlines. */
4622 re_comp_buf.newline_anchor = 1;
4624 ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
4626 /* Yes, we're discarding `const' here. */
4627 return (char *) re_error_msg[(int) ret];
4635 const int len = strlen (s);
4637 0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
4639 #endif /* not emacs and not _POSIX_SOURCE */
4641 /* POSIX.2 functions. Don't define these for Emacs. */
4645 /* regcomp takes a regular expression as a string and compiles it.
4647 PREG is a regex_t *. We do not expect any fields to be initialized,
4648 since POSIX says we shouldn't. Thus, we set
4650 `buffer' to the compiled pattern;
4651 `used' to the length of the compiled pattern;
4652 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
4653 REG_EXTENDED bit in CFLAGS is set; otherwise, to
4654 RE_SYNTAX_POSIX_BASIC;
4655 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
4656 `fastmap' and `fastmap_accurate' to zero;
4657 `re_nsub' to the number of subexpressions in PATTERN.
4659 PATTERN is the address of the pattern string.
4661 CFLAGS is a series of bits which affect compilation.
4663 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
4664 use POSIX basic syntax.
4666 If REG_NEWLINE is set, then . and [^...] don't match newline.
4667 Also, regexec will try a match beginning after every newline.
4669 If REG_ICASE is set, then we considers upper- and lowercase
4670 versions of letters to be equivalent when matching.
4672 If REG_NOSUB is set, then when PREG is passed to regexec, that
4673 routine will report only success or failure, and nothing about the
4676 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
4677 the return codes and their meanings.) */
4680 regcomp (preg, pattern, cflags)
4682 const char *pattern;
4687 = cflags & REG_EXTENDED ? RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
4689 /* regex_compile will allocate the space for the compiled pattern. */
4692 /* Don't bother to use a fastmap when searching. This simplifies the
4693 REG_NEWLINE case: if we used a fastmap, we'd have to put all the
4694 characters after newlines into the fastmap. This way, we just try
4698 if (cflags & REG_ICASE)
4702 preg->translate = (char *) malloc (CHAR_SET_SIZE);
4703 if (preg->translate == NULL)
4704 return (int) REG_ESPACE;
4706 /* Map uppercase characters to corresponding lowercase ones. */
4707 for (i = 0; i < CHAR_SET_SIZE; i++)
4708 preg->translate[i] = isupper (i) ? tolower (i) : i;
4711 preg->translate = NULL;
4713 /* If REG_NEWLINE is set, newlines are treated differently. */
4714 if (cflags & REG_NEWLINE)
4715 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
4716 syntax &= ~RE_DOT_NEWLINE;
4717 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
4718 /* It also changes the matching behavior. */
4719 preg->newline_anchor = 1;
4722 preg->newline_anchor = 0;
4724 preg->no_sub = !!(cflags & REG_NOSUB);
4726 /* POSIX says a null character in the pattern terminates it, so we
4727 can use strlen here in compiling the pattern. */
4728 ret = regex_compile (pattern, strlen (pattern), syntax, preg);
4730 /* POSIX doesn't distinguish between an unmatched open-group and an
4731 unmatched close-group: both are REG_EPAREN. */
4732 if (ret == REG_ERPAREN) ret = REG_EPAREN;
4738 /* regexec searches for a given pattern, specified by PREG, in the
4741 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
4742 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
4743 least NMATCH elements, and we set them to the offsets of the
4744 corresponding matched substrings.
4746 EFLAGS specifies `execution flags' which affect matching: if
4747 REG_NOTBOL is set, then ^ does not match at the beginning of the
4748 string; if REG_NOTEOL is set, then $ does not match at the end.
4750 We return 0 if we find a match and REG_NOMATCH if not. */
4753 regexec (preg, string, nmatch, pmatch, eflags)
4754 const regex_t *preg;
4757 regmatch_t pmatch[];
4761 struct re_registers regs;
4762 regex_t private_preg;
4763 int len = strlen (string);
4764 boolean want_reg_info = !preg->no_sub && nmatch > 0;
4766 private_preg = *preg;
4768 private_preg.not_bol = !!(eflags & REG_NOTBOL);
4769 private_preg.not_eol = !!(eflags & REG_NOTEOL);
4771 /* The user has told us exactly how many registers to return
4772 information about, via `nmatch'. We have to pass that on to the
4773 matching routines. */
4774 private_preg.regs_allocated = REGS_FIXED;
4778 regs.num_regs = nmatch;
4779 regs.start = TALLOC (nmatch, regoff_t);
4780 regs.end = TALLOC (nmatch, regoff_t);
4781 if (regs.start == NULL || regs.end == NULL)
4782 return (int) REG_NOMATCH;
4785 /* Perform the searching operation. */
4786 ret = re_search (&private_preg, string, len,
4787 /* start: */ 0, /* range: */ len,
4788 want_reg_info ? ®s : (struct re_registers *) 0);
4790 /* Copy the register information to the POSIX structure. */
4797 for (r = 0; r < nmatch; r++)
4799 pmatch[r].rm_so = regs.start[r];
4800 pmatch[r].rm_eo = regs.end[r];
4804 /* If we needed the temporary register info, free the space now. */
4809 /* We want zero return to mean success, unlike `re_search'. */
4810 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
4814 /* Returns a message corresponding to an error code, ERRCODE, returned
4815 from either regcomp or regexec. */
4818 regerror (errcode, preg, errbuf, errbuf_size)
4820 const regex_t *preg;
4825 = re_error_msg[errcode] == NULL ? "Success" : re_error_msg[errcode];
4826 size_t msg_size = strlen (msg) + 1; /* Includes the null. */
4828 if (errbuf_size != 0)
4830 if (msg_size > errbuf_size)
4832 strncpy (errbuf, msg, errbuf_size - 1);
4833 errbuf[errbuf_size - 1] = 0;
4836 strcpy (errbuf, msg);
4843 /* Free dynamically allocated space used by PREG. */
4849 if (preg->buffer != NULL)
4850 free (preg->buffer);
4851 preg->buffer = NULL;
4853 preg->allocated = 0;
4856 if (preg->fastmap != NULL)
4857 free (preg->fastmap);
4858 preg->fastmap = NULL;
4859 preg->fastmap_accurate = 0;
4861 if (preg->translate != NULL)
4862 free (preg->translate);
4863 preg->translate = NULL;
4866 #endif /* not emacs */
4870 make-backup-files: t
4872 trim-versions-without-asking: nil