1 /* Extended regular expression matching and search library,
3 (Implements POSIX draft P1003.2/D11.2, except for some of the
4 internationalization features.)
6 Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
7 2002, 2003, 2004 Free Software Foundation, Inc.
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License along
20 with this program; if not, write to the Free Software Foundation,
21 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
23 /* AIX requires this to be the first thing in the file. */
24 #if defined _AIX && !defined REGEX_MALLOC
35 #ifndef INSIDE_RECURSION
39 # define WIDE_CHAR_SUPPORT (HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_BTOWC)
41 /* For platform which support the ISO C amendement 1 functionality we
42 support user defined character classes. */
43 # if defined _LIBC || WIDE_CHAR_SUPPORT
44 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
50 /* We have to keep the namespace clean. */
51 # define regfree(preg) __regfree (preg)
52 # define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
53 # define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
54 # define regerror(errcode, preg, errbuf, errbuf_size) \
55 __regerror(errcode, preg, errbuf, errbuf_size)
56 # define re_set_registers(bu, re, nu, st, en) \
57 __re_set_registers (bu, re, nu, st, en)
58 # define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
59 __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
60 # define re_match(bufp, string, size, pos, regs) \
61 __re_match (bufp, string, size, pos, regs)
62 # define re_search(bufp, string, size, startpos, range, regs) \
63 __re_search (bufp, string, size, startpos, range, regs)
64 # define re_compile_pattern(pattern, length, bufp) \
65 __re_compile_pattern (pattern, length, bufp)
66 # define re_set_syntax(syntax) __re_set_syntax (syntax)
67 # define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
68 __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
69 # define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
71 # define btowc __btowc
72 # define iswctype __iswctype
73 # define mbrtowc __mbrtowc
74 # define wcslen __wcslen
75 # define wcscoll __wcscoll
76 # define wcrtomb __wcrtomb
78 /* We are also using some library internals. */
79 # include <locale/localeinfo.h>
80 # include <locale/elem-hash.h>
81 # include <langinfo.h>
82 # include <locale/coll-lookup.h>
88 # define gettext(msgid) __dcgettext ("libc", msgid, LC_MESSAGES)
89 /* This define is so xgettext can find the internationalizable strings. */
90 # define gettext_noop(msgid) msgid
92 /* This is for other GNU distributions with internationalized messages. */
96 /* Support for bounded pointers. */
97 # if !defined _LIBC && !defined __BOUNDED_POINTERS__
98 # define __bounded /* nothing */
99 # define __unbounded /* nothing */
100 # define __ptrvalue /* nothing */
103 /* The `emacs' switch turns on certain matching commands
104 that make sense only in Emacs. */
111 # else /* not emacs */
113 /* If we are not linking with Emacs proper,
114 we can't use the relocating allocator
115 even if config.h says that we can. */
120 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
121 If nothing else has been done, use the method below. */
122 # ifdef INHIBIT_STRING_HEADER
123 # if !(defined HAVE_BZERO && defined HAVE_BCOPY)
124 # if !defined bzero && !defined bcopy
125 # undef INHIBIT_STRING_HEADER
130 /* This is the normal way of making sure we have a bcopy and a bzero.
131 This is used in most programs--a few other programs avoid this
132 by defining INHIBIT_STRING_HEADER. */
133 # ifndef INHIBIT_STRING_HEADER
137 # define bzero(s, n) (memset (s, '\0', n), (s))
139 # define bzero(s, n) __bzero (s, n)
144 /* Define the syntax stuff for \<, \>, etc. */
146 /* This must be nonzero for the wordchar and notwordchar pattern
147 commands in re_match_2. */
152 # ifdef SWITCH_ENUM_BUG
153 # define SWITCH_ENUM_CAST(x) ((int)(x))
155 # define SWITCH_ENUM_CAST(x) (x)
158 # endif /* not emacs */
163 # define MB_LEN_MAX 1
166 /* Get the interface, including the syntax bits. */
169 /* isalpha etc. are used for the character classes. */
172 /* Jim Meyering writes:
174 "... Some ctype macros are valid only for character codes that
175 isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
176 using /bin/cc or gcc but without giving an ansi option). So, all
177 ctype uses should be through macros like ISPRINT... If
178 STDC_HEADERS is defined, then autoconf has verified that the ctype
179 macros don't need to be guarded with references to isascii. ...
180 Defining isascii to 1 should let any compiler worth its salt
181 eliminate the && through constant folding."
182 Solaris defines some of these symbols so we must undefine them first. */
184 # if defined STDC_HEADERS || (!defined isascii && !defined HAVE_ISASCII)
185 # define IN_CTYPE_DOMAIN(c) 1
187 # define IN_CTYPE_DOMAIN(c) isascii(c)
191 # define ISBLANK(c) (IN_CTYPE_DOMAIN (c) && isblank (c))
193 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
196 # define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isgraph (c))
198 # define ISGRAPH(c) (IN_CTYPE_DOMAIN (c) && isprint (c) && !isspace (c))
202 # define ISPRINT(c) (IN_CTYPE_DOMAIN (c) && isprint (c))
203 # define ISDIGIT(c) (IN_CTYPE_DOMAIN (c) && isdigit (c))
204 # define ISALNUM(c) (IN_CTYPE_DOMAIN (c) && isalnum (c))
205 # define ISALPHA(c) (IN_CTYPE_DOMAIN (c) && isalpha (c))
206 # define ISCNTRL(c) (IN_CTYPE_DOMAIN (c) && iscntrl (c))
207 # define ISLOWER(c) (IN_CTYPE_DOMAIN (c) && islower (c))
208 # define ISPUNCT(c) (IN_CTYPE_DOMAIN (c) && ispunct (c))
209 # define ISSPACE(c) (IN_CTYPE_DOMAIN (c) && isspace (c))
210 # define ISUPPER(c) (IN_CTYPE_DOMAIN (c) && isupper (c))
211 # define ISXDIGIT(c) (IN_CTYPE_DOMAIN (c) && isxdigit (c))
214 # define TOLOWER(c) _tolower(c)
216 # define TOLOWER(c) tolower(c)
220 /* How many characters in the character set. */
221 # define CHAR_SET_SIZE 256
225 extern char *re_syntax_table;
227 # else /* not SYNTAX_TABLE */
229 static char re_syntax_table[CHAR_SET_SIZE];
232 init_syntax_once (void)
239 bzero (re_syntax_table, sizeof re_syntax_table);
241 for (c = 0; c < CHAR_SET_SIZE; ++c)
243 re_syntax_table[c] = Sword;
245 re_syntax_table['_'] = Sword;
250 # endif /* not SYNTAX_TABLE */
252 # define SYNTAX(c) re_syntax_table[(unsigned char) (c)]
256 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
257 use `alloca' instead of `malloc'. This is because using malloc in
258 re_search* or re_match* could cause memory leaks when C-g is used in
259 Emacs; also, malloc is slower and causes storage fragmentation. On
260 the other hand, malloc is more portable, and easier to debug.
262 Because we sometimes use alloca, some routines have to be macros,
263 not functions -- `alloca'-allocated space disappears at the end of the
264 function it is called in. */
268 # define REGEX_ALLOCATE malloc
269 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
270 # define REGEX_FREE free
272 # else /* not REGEX_MALLOC */
274 /* Emacs already defines alloca, sometimes. */
277 /* Make alloca work the best possible way. */
280 # endif /* not alloca */
282 # define REGEX_ALLOCATE alloca
284 /* Assumes a `char *destination' variable. */
285 # define REGEX_REALLOCATE(source, osize, nsize) \
286 (destination = (char *) alloca (nsize), \
287 memcpy (destination, source, osize))
289 /* No need to do anything to free, after alloca. */
290 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
292 # endif /* not REGEX_MALLOC */
294 /* Define how to allocate the failure stack. */
296 # if defined REL_ALLOC && defined REGEX_MALLOC
298 # define REGEX_ALLOCATE_STACK(size) \
299 r_alloc (&failure_stack_ptr, (size))
300 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
301 r_re_alloc (&failure_stack_ptr, (nsize))
302 # define REGEX_FREE_STACK(ptr) \
303 r_alloc_free (&failure_stack_ptr)
305 # else /* not using relocating allocator */
309 # define REGEX_ALLOCATE_STACK malloc
310 # define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
311 # define REGEX_FREE_STACK free
313 # else /* not REGEX_MALLOC */
315 # define REGEX_ALLOCATE_STACK alloca
317 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
318 REGEX_REALLOCATE (source, osize, nsize)
319 /* No need to explicitly free anything. */
320 # define REGEX_FREE_STACK(arg)
322 # endif /* not REGEX_MALLOC */
323 # endif /* not using relocating allocator */
326 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
327 `string1' or just past its end. This works if PTR is NULL, which is
329 # define FIRST_STRING_P(ptr) \
330 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
332 /* (Re)Allocate N items of type T using malloc, or fail. */
333 # define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
334 # define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
335 # define RETALLOC_IF(addr, n, t) \
336 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
337 # define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
339 # define BYTEWIDTH 8 /* In bits. */
341 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
345 # define MAX(a, b) ((a) > (b) ? (a) : (b))
346 # define MIN(a, b) ((a) < (b) ? (a) : (b))
348 typedef char boolean;
352 static reg_errcode_t byte_regex_compile (const char *pattern, size_t size,
354 struct re_pattern_buffer *bufp);
356 static int byte_re_match_2_internal (struct re_pattern_buffer *bufp,
357 const char *string1, int size1,
358 const char *string2, int size2,
360 struct re_registers *regs,
362 static int byte_re_search_2 (struct re_pattern_buffer *bufp,
363 const char *string1, int size1,
364 const char *string2, int size2,
365 int startpos, int range,
366 struct re_registers *regs, int stop);
367 static int byte_re_compile_fastmap (struct re_pattern_buffer *bufp);
370 static reg_errcode_t wcs_regex_compile (const char *pattern, size_t size,
372 struct re_pattern_buffer *bufp);
375 static int wcs_re_match_2_internal (struct re_pattern_buffer *bufp,
376 const char *cstring1, int csize1,
377 const char *cstring2, int csize2,
379 struct re_registers *regs,
381 wchar_t *string1, int size1,
382 wchar_t *string2, int size2,
383 int *mbs_offset1, int *mbs_offset2);
384 static int wcs_re_search_2 (struct re_pattern_buffer *bufp,
385 const char *string1, int size1,
386 const char *string2, int size2,
387 int startpos, int range,
388 struct re_registers *regs, int stop);
389 static int wcs_re_compile_fastmap (struct re_pattern_buffer *bufp);
392 /* These are the command codes that appear in compiled regular
393 expressions. Some opcodes are followed by argument bytes. A
394 command code can specify any interpretation whatsoever for its
395 arguments. Zero bytes may appear in the compiled regular expression. */
401 /* Succeed right away--no more backtracking. */
404 /* Followed by one byte giving n, then by n literal bytes. */
408 /* Same as exactn, but contains binary data. */
412 /* Matches any (more or less) character. */
415 /* Matches any one char belonging to specified set. First
416 following byte is number of bitmap bytes. Then come bytes
417 for a bitmap saying which chars are in. Bits in each byte
418 are ordered low-bit-first. A character is in the set if its
419 bit is 1. A character too large to have a bit in the map is
420 automatically not in the set. */
421 /* ifdef MBS_SUPPORT, following element is length of character
422 classes, length of collating symbols, length of equivalence
423 classes, length of character ranges, and length of characters.
424 Next, character class element, collating symbols elements,
425 equivalence class elements, range elements, and character
427 See regex_compile function. */
430 /* Same parameters as charset, but match any character that is
431 not one of those specified. */
434 /* Start remembering the text that is matched, for storing in a
435 register. Followed by one byte with the register number, in
436 the range 0 to one less than the pattern buffer's re_nsub
437 field. Then followed by one byte with the number of groups
438 inner to this one. (This last has to be part of the
439 start_memory only because we need it in the on_failure_jump
443 /* Stop remembering the text that is matched and store it in a
444 memory register. Followed by one byte with the register
445 number, in the range 0 to one less than `re_nsub' in the
446 pattern buffer, and one byte with the number of inner groups,
447 just like `start_memory'. (We need the number of inner
448 groups here because we don't have any easy way of finding the
449 corresponding start_memory when we're at a stop_memory.) */
452 /* Match a duplicate of something remembered. Followed by one
453 byte containing the register number. */
456 /* Fail unless at beginning of line. */
459 /* Fail unless at end of line. */
462 /* Succeeds if at beginning of buffer (if emacs) or at beginning
463 of string to be matched (if not). */
466 /* Analogously, for end of buffer/string. */
469 /* Followed by two byte relative address to which to jump. */
472 /* Same as jump, but marks the end of an alternative. */
475 /* Followed by two-byte relative address of place to resume at
476 in case of failure. */
477 /* ifdef MBS_SUPPORT, the size of address is 1. */
480 /* Like on_failure_jump, but pushes a placeholder instead of the
481 current string position when executed. */
482 on_failure_keep_string_jump,
484 /* Throw away latest failure point and then jump to following
485 two-byte relative address. */
486 /* ifdef MBS_SUPPORT, the size of address is 1. */
489 /* Change to pop_failure_jump if know won't have to backtrack to
490 match; otherwise change to jump. This is used to jump
491 back to the beginning of a repeat. If what follows this jump
492 clearly won't match what the repeat does, such that we can be
493 sure that there is no use backtracking out of repetitions
494 already matched, then we change it to a pop_failure_jump.
495 Followed by two-byte address. */
496 /* ifdef MBS_SUPPORT, the size of address is 1. */
499 /* Jump to following two-byte address, and push a dummy failure
500 point. This failure point will be thrown away if an attempt
501 is made to use it for a failure. A `+' construct makes this
502 before the first repeat. Also used as an intermediary kind
503 of jump when compiling an alternative. */
504 /* ifdef MBS_SUPPORT, the size of address is 1. */
507 /* Push a dummy failure point and continue. Used at the end of
511 /* Followed by two-byte relative address and two-byte number n.
512 After matching N times, jump to the address upon failure. */
513 /* ifdef MBS_SUPPORT, the size of address is 1. */
516 /* Followed by two-byte relative address, and two-byte number n.
517 Jump to the address N times, then fail. */
518 /* ifdef MBS_SUPPORT, the size of address is 1. */
521 /* Set the following two-byte relative address to the
522 subsequent two-byte number. The address *includes* the two
524 /* ifdef MBS_SUPPORT, the size of address is 1. */
527 wordchar, /* Matches any word-constituent character. */
528 notwordchar, /* Matches any char that is not a word-constituent. */
530 wordbeg, /* Succeeds if at word beginning. */
531 wordend, /* Succeeds if at word end. */
533 wordbound, /* Succeeds if at a word boundary. */
534 notwordbound /* Succeeds if not at a word boundary. */
537 ,before_dot, /* Succeeds if before point. */
538 at_dot, /* Succeeds if at point. */
539 after_dot, /* Succeeds if after point. */
541 /* Matches any character whose syntax is specified. Followed by
542 a byte which contains a syntax code, e.g., Sword. */
545 /* Matches any character whose syntax is not that specified. */
549 #endif /* not INSIDE_RECURSION */
554 # define UCHAR_T unsigned char
555 # define COMPILED_BUFFER_VAR bufp->buffer
556 # define OFFSET_ADDRESS_SIZE 2
557 # define PREFIX(name) byte_##name
558 # define ARG_PREFIX(name) name
559 # define PUT_CHAR(c) putchar (c)
562 # define CHAR_T wchar_t
563 # define UCHAR_T wchar_t
564 # define COMPILED_BUFFER_VAR wc_buffer
565 # define OFFSET_ADDRESS_SIZE 1 /* the size which STORE_NUMBER macro use */
566 # define CHAR_CLASS_SIZE ((__alignof__(wctype_t)+sizeof(wctype_t))/sizeof(CHAR_T)+1)
567 # define PREFIX(name) wcs_##name
568 # define ARG_PREFIX(name) c##name
569 /* Should we use wide stream?? */
570 # define PUT_CHAR(c) printf ("%C", c);
576 # define INSIDE_RECURSION
578 # undef INSIDE_RECURSION
581 # define INSIDE_RECURSION
583 # undef INSIDE_RECURSION
588 # include "unlocked-io.h"
591 #ifdef INSIDE_RECURSION
592 /* Common operations on the compiled pattern. */
594 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
595 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
598 # define STORE_NUMBER(destination, number) \
600 *(destination) = (UCHAR_T)(number); \
603 # define STORE_NUMBER(destination, number) \
605 (destination)[0] = (number) & 0377; \
606 (destination)[1] = (number) >> 8; \
610 /* Same as STORE_NUMBER, except increment DESTINATION to
611 the byte after where the number is stored. Therefore, DESTINATION
612 must be an lvalue. */
613 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
615 # define STORE_NUMBER_AND_INCR(destination, number) \
617 STORE_NUMBER (destination, number); \
618 (destination) += OFFSET_ADDRESS_SIZE; \
621 /* Put into DESTINATION a number stored in two contiguous bytes starting
623 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
626 # define EXTRACT_NUMBER(destination, source) \
628 (destination) = *(source); \
631 # define EXTRACT_NUMBER(destination, source) \
633 (destination) = *(source) & 0377; \
634 (destination) += (signed char) (*((source) + 1)) << 8; \
640 PREFIX(extract_number) (int *dest, UCHAR_T *source)
645 signed char temp = source[1];
646 *dest = *source & 0377;
651 # ifndef EXTRACT_MACROS /* To debug the macros. */
652 # undef EXTRACT_NUMBER
653 # define EXTRACT_NUMBER(dest, src) PREFIX(extract_number) (&dest, src)
654 # endif /* not EXTRACT_MACROS */
658 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
659 SOURCE must be an lvalue. */
661 # define EXTRACT_NUMBER_AND_INCR(destination, source) \
663 EXTRACT_NUMBER (destination, source); \
664 (source) += OFFSET_ADDRESS_SIZE; \
669 PREFIX(extract_number_and_incr) (int *destination, UCHAR_T **source)
671 PREFIX(extract_number) (destination, *source);
672 *source += OFFSET_ADDRESS_SIZE;
675 # ifndef EXTRACT_MACROS
676 # undef EXTRACT_NUMBER_AND_INCR
677 # define EXTRACT_NUMBER_AND_INCR(dest, src) \
678 PREFIX(extract_number_and_incr) (&dest, &src)
679 # endif /* not EXTRACT_MACROS */
685 /* If DEBUG is defined, Regex prints many voluminous messages about what
686 it is doing (if the variable `debug' is nonzero). If linked with the
687 main program in `iregex.c', you can enter patterns and strings
688 interactively. And if linked with the main program in `main.c' and
689 the other test files, you can run the already-written tests. */
693 # ifndef DEFINED_ONCE
695 /* We use standard I/O for debugging. */
698 /* It is useful to test things that ``must'' be true when debugging. */
703 # define DEBUG_STATEMENT(e) e
704 # define DEBUG_PRINT1(x) if (debug) printf (x)
705 # define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
706 # define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
707 # define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
708 # endif /* not DEFINED_ONCE */
710 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
711 if (debug) PREFIX(print_partial_compiled_pattern) (s, e)
712 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
713 if (debug) PREFIX(print_double_string) (w, s1, sz1, s2, sz2)
716 /* Print the fastmap in human-readable form. */
718 # ifndef DEFINED_ONCE
720 print_fastmap (char *fastmap)
722 unsigned was_a_range = 0;
725 while (i < (1 << BYTEWIDTH))
731 while (i < (1 << BYTEWIDTH) && fastmap[i])
745 # endif /* not DEFINED_ONCE */
748 /* Print a compiled pattern string in human-readable form, starting at
749 the START pointer into it and ending just before the pointer END. */
752 PREFIX(print_partial_compiled_pattern) (UCHAR_T *start, UCHAR_T *end)
765 /* Loop over pattern commands. */
769 printf ("%td:\t", p - start);
771 printf ("%ld:\t", (long int) (p - start));
774 switch ((re_opcode_t) *p++)
782 printf ("/exactn/%d", mcnt);
794 printf ("/exactn_bin/%d", mcnt);
797 printf("/%lx", (long int) *p++);
801 # endif /* MBS_SUPPORT */
805 printf ("/start_memory/%d/%ld", mcnt, (long int) *p++);
810 printf ("/stop_memory/%d/%ld", mcnt, (long int) *p++);
814 printf ("/duplicate/%ld", (long int) *p++);
827 printf ("/charset [%s",
828 (re_opcode_t) *(workp - 1) == charset_not ? "^" : "");
830 length = *workp++; /* the length of char_classes */
831 for (i=0 ; i<length ; i++)
832 printf("[:%lx:]", (long int) *p++);
833 length = *workp++; /* the length of collating_symbol */
834 for (i=0 ; i<length ;)
838 PUT_CHAR((i++,*p++));
842 length = *workp++; /* the length of equivalence_class */
843 for (i=0 ; i<length ;)
847 PUT_CHAR((i++,*p++));
851 length = *workp++; /* the length of char_range */
852 for (i=0 ; i<length ; i++)
854 wchar_t range_start = *p++;
855 wchar_t range_end = *p++;
856 printf("%C-%C", range_start, range_end);
858 length = *workp++; /* the length of char */
859 for (i=0 ; i<length ; i++)
863 register int c, last = -100;
864 register int in_range = 0;
866 printf ("/charset [%s",
867 (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
869 assert (p + *p < pend);
871 for (c = 0; c < 256; c++)
873 && (p[1 + (c/8)] & (1 << (c % 8))))
875 /* Are we starting a range? */
876 if (last + 1 == c && ! in_range)
881 /* Have we broken a range? */
882 else if (last + 1 != c && in_range)
912 case on_failure_jump:
913 PREFIX(extract_number_and_incr) (&mcnt, &p);
915 printf ("/on_failure_jump to %td", p + mcnt - start);
917 printf ("/on_failure_jump to %ld", (long int) (p + mcnt - start));
921 case on_failure_keep_string_jump:
922 PREFIX(extract_number_and_incr) (&mcnt, &p);
924 printf ("/on_failure_keep_string_jump to %td", p + mcnt - start);
926 printf ("/on_failure_keep_string_jump to %ld",
927 (long int) (p + mcnt - start));
931 case dummy_failure_jump:
932 PREFIX(extract_number_and_incr) (&mcnt, &p);
934 printf ("/dummy_failure_jump to %td", p + mcnt - start);
936 printf ("/dummy_failure_jump to %ld", (long int) (p + mcnt - start));
940 case push_dummy_failure:
941 printf ("/push_dummy_failure");
945 PREFIX(extract_number_and_incr) (&mcnt, &p);
947 printf ("/maybe_pop_jump to %td", p + mcnt - start);
949 printf ("/maybe_pop_jump to %ld", (long int) (p + mcnt - start));
953 case pop_failure_jump:
954 PREFIX(extract_number_and_incr) (&mcnt, &p);
956 printf ("/pop_failure_jump to %td", p + mcnt - start);
958 printf ("/pop_failure_jump to %ld", (long int) (p + mcnt - start));
963 PREFIX(extract_number_and_incr) (&mcnt, &p);
965 printf ("/jump_past_alt to %td", p + mcnt - start);
967 printf ("/jump_past_alt to %ld", (long int) (p + mcnt - start));
972 PREFIX(extract_number_and_incr) (&mcnt, &p);
974 printf ("/jump to %td", p + mcnt - start);
976 printf ("/jump to %ld", (long int) (p + mcnt - start));
981 PREFIX(extract_number_and_incr) (&mcnt, &p);
983 PREFIX(extract_number_and_incr) (&mcnt2, &p);
985 printf ("/succeed_n to %td, %d times", p1 - start, mcnt2);
987 printf ("/succeed_n to %ld, %d times",
988 (long int) (p1 - start), mcnt2);
993 PREFIX(extract_number_and_incr) (&mcnt, &p);
995 PREFIX(extract_number_and_incr) (&mcnt2, &p);
996 printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
1000 PREFIX(extract_number_and_incr) (&mcnt, &p);
1002 PREFIX(extract_number_and_incr) (&mcnt2, &p);
1004 printf ("/set_number_at location %td to %d", p1 - start, mcnt2);
1006 printf ("/set_number_at location %ld to %d",
1007 (long int) (p1 - start), mcnt2);
1012 printf ("/wordbound");
1016 printf ("/notwordbound");
1020 printf ("/wordbeg");
1024 printf ("/wordend");
1029 printf ("/before_dot");
1037 printf ("/after_dot");
1041 printf ("/syntaxspec");
1043 printf ("/%d", mcnt);
1047 printf ("/notsyntaxspec");
1049 printf ("/%d", mcnt);
1054 printf ("/wordchar");
1058 printf ("/notwordchar");
1070 printf ("?%ld", (long int) *(p-1));
1077 printf ("%td:\tend of pattern.\n", p - start);
1079 printf ("%ld:\tend of pattern.\n", (long int) (p - start));
1085 PREFIX(print_compiled_pattern) (struct re_pattern_buffer *bufp)
1087 UCHAR_T *buffer = (UCHAR_T*) bufp->buffer;
1089 PREFIX(print_partial_compiled_pattern) (buffer, buffer
1090 + bufp->used / sizeof(UCHAR_T));
1091 printf ("%ld bytes used/%ld bytes allocated.\n",
1092 bufp->used, bufp->allocated);
1094 if (bufp->fastmap_accurate && bufp->fastmap)
1096 printf ("fastmap: ");
1097 print_fastmap (bufp->fastmap);
1101 printf ("re_nsub: %Zd\t", bufp->re_nsub);
1103 printf ("re_nsub: %ld\t", (long int) bufp->re_nsub);
1105 printf ("regs_alloc: %d\t", bufp->regs_allocated);
1106 printf ("can_be_null: %d\t", bufp->can_be_null);
1107 printf ("newline_anchor: %d\n", bufp->newline_anchor);
1108 printf ("no_sub: %d\t", bufp->no_sub);
1109 printf ("not_bol: %d\t", bufp->not_bol);
1110 printf ("not_eol: %d\t", bufp->not_eol);
1111 printf ("syntax: %lx\n", bufp->syntax);
1112 /* Perhaps we should print the translate table? */
1117 PREFIX(print_double_string) (const CHAR_T *where,
1118 const CHAR_T *string1,
1119 const CHAR_T *string2,
1131 if (FIRST_STRING_P (where))
1133 for (this_char = where - string1; this_char < size1; this_char++)
1134 PUT_CHAR (string1[this_char]);
1140 for (this_char = where - string2; this_char < size2; this_char++)
1142 PUT_CHAR (string2[this_char]);
1145 fputs ("...", stdout);
1152 # ifndef DEFINED_ONCE
1161 # else /* not DEBUG */
1163 # ifndef DEFINED_ONCE
1167 # define DEBUG_STATEMENT(e)
1168 # define DEBUG_PRINT1(x)
1169 # define DEBUG_PRINT2(x1, x2)
1170 # define DEBUG_PRINT3(x1, x2, x3)
1171 # define DEBUG_PRINT4(x1, x2, x3, x4)
1172 # endif /* not DEFINED_ONCE */
1173 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1174 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1176 # endif /* not DEBUG */
1181 /* This convert a multibyte string to a wide character string.
1182 And write their correspondances to offset_buffer(see below)
1183 and write whether each wchar_t is binary data to is_binary.
1184 This assume invalid multibyte sequences as binary data.
1185 We assume offset_buffer and is_binary is already allocated
1189 convert_mbs_to_wcs (CHAR_T *dest,
1190 const unsigned char* src,
1192 /* The length of multibyte string. */
1195 /* Correspondences between src(char string) and
1196 dest(wchar_t string) for optimization. E.g.:
1198 dest = {'X', 'Y', 'Z'}
1199 (each "xxx", "y" and "zz" represent one
1200 multibyte character corresponding to 'X',
1202 offset_buffer = {0, 0+3("xxx"), 0+3+1("y"),
1209 wchar_t *pdest = dest;
1210 const unsigned char *psrc = src;
1211 size_t wc_count = 0;
1215 size_t mb_remain = len;
1216 size_t mb_count = 0;
1218 /* Initialize the conversion state. */
1219 memset (&mbs, 0, sizeof (mbstate_t));
1221 offset_buffer[0] = 0;
1222 for( ; mb_remain > 0 ; ++wc_count, ++pdest, mb_remain -= consumed,
1225 consumed = mbrtowc (pdest, psrc, mb_remain, &mbs);
1228 /* failed to convert. maybe src contains binary data.
1229 So we consume 1 byte manualy. */
1233 is_binary[wc_count] = TRUE;
1236 is_binary[wc_count] = FALSE;
1237 /* In sjis encoding, we use yen sign as escape character in
1238 place of reverse solidus. So we convert 0x5c(yen sign in
1239 sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1240 solidus in UCS2). */
1241 if (consumed == 1 && (int) *psrc == 0x5c && (int) *pdest == 0xa5)
1242 *pdest = (wchar_t) *psrc;
1244 offset_buffer[wc_count + 1] = mb_count += consumed;
1247 /* Fill remain of the buffer with sentinel. */
1248 for (i = wc_count + 1 ; i <= len ; i++)
1249 offset_buffer[i] = mb_count + 1;
1256 #else /* not INSIDE_RECURSION */
1258 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1259 also be assigned to arbitrarily: each pattern buffer stores its own
1260 syntax, so it can be changed between regex compilations. */
1261 /* This has no initializer because initialized variables in Emacs
1262 become read-only after dumping. */
1263 reg_syntax_t re_syntax_options;
1266 /* Specify the precise syntax of regexps for compilation. This provides
1267 for compatibility for various utilities which historically have
1268 different, incompatible syntaxes.
1270 The argument SYNTAX is a bit mask comprised of the various bits
1271 defined in regex.h. We return the old syntax. */
1274 re_set_syntax (reg_syntax_t syntax)
1276 reg_syntax_t ret = re_syntax_options;
1278 re_syntax_options = syntax;
1280 if (syntax & RE_DEBUG)
1282 else if (debug) /* was on but now is not */
1288 weak_alias (__re_set_syntax, re_set_syntax)
1291 /* This table gives an error message for each of the error codes listed
1292 in regex.h. Obviously the order here has to be same as there.
1293 POSIX doesn't require that we do anything for REG_NOERROR,
1294 but why not be nice? */
1296 static const char re_error_msgid[] =
1298 # define REG_NOERROR_IDX 0
1299 gettext_noop ("Success") /* REG_NOERROR */
1301 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1302 gettext_noop ("No match") /* REG_NOMATCH */
1304 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1305 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1307 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1308 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1310 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1311 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1313 # define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1314 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1316 # define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1317 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1319 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1320 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
1322 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1323 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1325 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1326 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1328 # define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1329 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1331 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1332 gettext_noop ("Invalid range end") /* REG_ERANGE */
1334 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1335 gettext_noop ("Memory exhausted") /* REG_ESPACE */
1337 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1338 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1340 # define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1341 gettext_noop ("Premature end of regular expression") /* REG_EEND */
1343 # define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
1344 gettext_noop ("Regular expression too big") /* REG_ESIZE */
1346 # define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
1347 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1350 static const size_t re_error_msgid_idx[] =
1371 #endif /* INSIDE_RECURSION */
1373 #ifndef DEFINED_ONCE
1374 /* Avoiding alloca during matching, to placate r_alloc. */
1376 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1377 searching and matching functions should not call alloca. On some
1378 systems, alloca is implemented in terms of malloc, and if we're
1379 using the relocating allocator routines, then malloc could cause a
1380 relocation, which might (if the strings being searched are in the
1381 ralloc heap) shift the data out from underneath the regexp
1384 Here's another reason to avoid allocation: Emacs
1385 processes input from X in a signal handler; processing X input may
1386 call malloc; if input arrives while a matching routine is calling
1387 malloc, then we're scrod. But Emacs can't just block input while
1388 calling matching routines; then we don't notice interrupts when
1389 they come in. So, Emacs blocks input around all regexp calls
1390 except the matching calls, which it leaves unprotected, in the
1391 faith that they will not malloc. */
1393 /* Normally, this is fine. */
1394 # define MATCH_MAY_ALLOCATE
1396 /* When using GNU C, we are not REALLY using the C alloca, no matter
1397 what config.h may say. So don't take precautions for it. */
1402 /* The match routines may not allocate if (1) they would do it with malloc
1403 and (2) it's not safe for them to use malloc.
1404 Note that if REL_ALLOC is defined, matching would not use malloc for the
1405 failure stack, but we would still use it for the register vectors;
1406 so REL_ALLOC should not affect this. */
1407 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1408 # undef MATCH_MAY_ALLOCATE
1410 #endif /* not DEFINED_ONCE */
1412 #ifdef INSIDE_RECURSION
1413 /* Failure stack declarations and macros; both re_compile_fastmap and
1414 re_match_2 use a failure stack. These have to be macros because of
1415 REGEX_ALLOCATE_STACK. */
1418 /* Number of failure points for which to initially allocate space
1419 when matching. If this number is exceeded, we allocate more
1420 space, so it is not a hard limit. */
1421 # ifndef INIT_FAILURE_ALLOC
1422 # define INIT_FAILURE_ALLOC 5
1425 /* Roughly the maximum number of failure points on the stack. Would be
1426 exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1427 This is a variable only so users of regex can assign to it; we never
1428 change it ourselves. */
1430 # ifdef INT_IS_16BIT
1432 # ifndef DEFINED_ONCE
1433 # if defined MATCH_MAY_ALLOCATE
1434 /* 4400 was enough to cause a crash on Alpha OSF/1,
1435 whose default stack limit is 2mb. */
1436 long int re_max_failures = 4000;
1438 long int re_max_failures = 2000;
1442 union PREFIX(fail_stack_elt)
1448 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1452 PREFIX(fail_stack_elt_t) *stack;
1453 unsigned long int size;
1454 unsigned long int avail; /* Offset of next open position. */
1455 } PREFIX(fail_stack_type);
1457 # else /* not INT_IS_16BIT */
1459 # ifndef DEFINED_ONCE
1460 # if defined MATCH_MAY_ALLOCATE
1461 /* 4400 was enough to cause a crash on Alpha OSF/1,
1462 whose default stack limit is 2mb. */
1463 int re_max_failures = 4000;
1465 int re_max_failures = 2000;
1469 union PREFIX(fail_stack_elt)
1475 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1479 PREFIX(fail_stack_elt_t) *stack;
1481 unsigned avail; /* Offset of next open position. */
1482 } PREFIX(fail_stack_type);
1484 # endif /* INT_IS_16BIT */
1486 # ifndef DEFINED_ONCE
1487 # define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
1488 # define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1489 # define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
1493 /* Define macros to initialize and free the failure stack.
1494 Do `return -2' if the alloc fails. */
1496 # ifdef MATCH_MAY_ALLOCATE
1497 # define INIT_FAIL_STACK() \
1499 fail_stack.stack = (PREFIX(fail_stack_elt_t) *) \
1500 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1502 if (fail_stack.stack == NULL) \
1505 fail_stack.size = INIT_FAILURE_ALLOC; \
1506 fail_stack.avail = 0; \
1509 # define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack)
1511 # define INIT_FAIL_STACK() \
1513 fail_stack.avail = 0; \
1516 # define RESET_FAIL_STACK()
1520 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1522 Return 1 if succeeds, and 0 if either ran out of memory
1523 allocating space for it or it was already too large.
1525 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1527 # define DOUBLE_FAIL_STACK(fail_stack) \
1528 ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1530 : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *) \
1531 REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1532 (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)), \
1533 ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1535 (fail_stack).stack == NULL \
1537 : ((fail_stack).size <<= 1, \
1541 /* Push pointer POINTER on FAIL_STACK.
1542 Return 1 if was able to do so and 0 if ran out of memory allocating
1544 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK) \
1545 ((FAIL_STACK_FULL () \
1546 && !DOUBLE_FAIL_STACK (FAIL_STACK)) \
1548 : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER, \
1551 /* Push a pointer value onto the failure stack.
1552 Assumes the variable `fail_stack'. Probably should only
1553 be called from within `PUSH_FAILURE_POINT'. */
1554 # define PUSH_FAILURE_POINTER(item) \
1555 fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1557 /* This pushes an integer-valued item onto the failure stack.
1558 Assumes the variable `fail_stack'. Probably should only
1559 be called from within `PUSH_FAILURE_POINT'. */
1560 # define PUSH_FAILURE_INT(item) \
1561 fail_stack.stack[fail_stack.avail++].integer = (item)
1563 /* Push a fail_stack_elt_t value onto the failure stack.
1564 Assumes the variable `fail_stack'. Probably should only
1565 be called from within `PUSH_FAILURE_POINT'. */
1566 # define PUSH_FAILURE_ELT(item) \
1567 fail_stack.stack[fail_stack.avail++] = (item)
1569 /* These three POP... operations complement the three PUSH... operations.
1570 All assume that `fail_stack' is nonempty. */
1571 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1572 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1573 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1575 /* Used to omit pushing failure point id's when we're not debugging. */
1577 # define DEBUG_PUSH PUSH_FAILURE_INT
1578 # define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1580 # define DEBUG_PUSH(item)
1581 # define DEBUG_POP(item_addr)
1585 /* Push the information about the state we will need
1586 if we ever fail back to it.
1588 Requires variables fail_stack, regstart, regend, reg_info, and
1589 num_regs_pushed be declared. DOUBLE_FAIL_STACK requires `destination'
1592 Does `return FAILURE_CODE' if runs out of memory. */
1594 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
1596 char *destination; \
1597 /* Must be int, so when we don't save any registers, the arithmetic \
1598 of 0 + -1 isn't done as unsigned. */ \
1599 /* Can't be int, since there is not a shred of a guarantee that int \
1600 is wide enough to hold a value of something to which pointer can \
1602 active_reg_t this_reg; \
1604 DEBUG_STATEMENT (failure_id++); \
1605 DEBUG_STATEMENT (nfailure_points_pushed++); \
1606 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
1607 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
1608 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
1610 DEBUG_PRINT2 (" slots needed: %ld\n", NUM_FAILURE_ITEMS); \
1611 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
1613 /* Ensure we have enough space allocated for what we will push. */ \
1614 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
1616 if (!DOUBLE_FAIL_STACK (fail_stack)) \
1617 return failure_code; \
1619 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
1620 (fail_stack).size); \
1621 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1624 /* Push the info, starting with the registers. */ \
1625 DEBUG_PRINT1 ("\n"); \
1628 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1631 DEBUG_PRINT2 (" Pushing reg: %lu\n", this_reg); \
1632 DEBUG_STATEMENT (num_regs_pushed++); \
1634 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1635 PUSH_FAILURE_POINTER (regstart[this_reg]); \
1637 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1638 PUSH_FAILURE_POINTER (regend[this_reg]); \
1640 DEBUG_PRINT2 (" info: %p\n ", \
1641 reg_info[this_reg].word.pointer); \
1642 DEBUG_PRINT2 (" match_null=%d", \
1643 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
1644 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
1645 DEBUG_PRINT2 (" matched_something=%d", \
1646 MATCHED_SOMETHING (reg_info[this_reg])); \
1647 DEBUG_PRINT2 (" ever_matched=%d", \
1648 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
1649 DEBUG_PRINT1 ("\n"); \
1650 PUSH_FAILURE_ELT (reg_info[this_reg].word); \
1653 DEBUG_PRINT2 (" Pushing low active reg: %ld\n", lowest_active_reg);\
1654 PUSH_FAILURE_INT (lowest_active_reg); \
1656 DEBUG_PRINT2 (" Pushing high active reg: %ld\n", highest_active_reg);\
1657 PUSH_FAILURE_INT (highest_active_reg); \
1659 DEBUG_PRINT2 (" Pushing pattern %p:\n", pattern_place); \
1660 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
1661 PUSH_FAILURE_POINTER (pattern_place); \
1663 DEBUG_PRINT2 (" Pushing string %p: `", string_place); \
1664 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
1666 DEBUG_PRINT1 ("'\n"); \
1667 PUSH_FAILURE_POINTER (string_place); \
1669 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
1670 DEBUG_PUSH (failure_id); \
1673 # ifndef DEFINED_ONCE
1674 /* This is the number of items that are pushed and popped on the stack
1675 for each register. */
1676 # define NUM_REG_ITEMS 3
1678 /* Individual items aside from the registers. */
1680 # define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
1682 # define NUM_NONREG_ITEMS 4
1685 /* We push at most this many items on the stack. */
1686 /* We used to use (num_regs - 1), which is the number of registers
1687 this regexp will save; but that was changed to 5
1688 to avoid stack overflow for a regexp with lots of parens. */
1689 # define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1691 /* We actually push this many items. */
1692 # define NUM_FAILURE_ITEMS \
1694 ? 0 : highest_active_reg - lowest_active_reg + 1) \
1698 /* How many items can still be added to the stack without overflowing it. */
1699 # define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1700 # endif /* not DEFINED_ONCE */
1703 /* Pops what PUSH_FAIL_STACK pushes.
1705 We restore into the parameters, all of which should be lvalues:
1706 STR -- the saved data position.
1707 PAT -- the saved pattern position.
1708 LOW_REG, HIGH_REG -- the highest and lowest active registers.
1709 REGSTART, REGEND -- arrays of string positions.
1710 REG_INFO -- array of information about each subexpression.
1712 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1713 `pend', `string1', `size1', `string2', and `size2'. */
1714 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1716 DEBUG_STATEMENT (unsigned failure_id;) \
1717 active_reg_t this_reg; \
1718 const UCHAR_T *string_temp; \
1720 assert (!FAIL_STACK_EMPTY ()); \
1722 /* Remove failure points and point to how many regs pushed. */ \
1723 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
1724 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
1725 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
1727 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
1729 DEBUG_POP (&failure_id); \
1730 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
1732 /* If the saved string location is NULL, it came from an \
1733 on_failure_keep_string_jump opcode, and we want to throw away the \
1734 saved NULL, thus retaining our current position in the string. */ \
1735 string_temp = POP_FAILURE_POINTER (); \
1736 if (string_temp != NULL) \
1737 str = (const CHAR_T *) string_temp; \
1739 DEBUG_PRINT2 (" Popping string %p: `", str); \
1740 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1741 DEBUG_PRINT1 ("'\n"); \
1743 pat = (UCHAR_T *) POP_FAILURE_POINTER (); \
1744 DEBUG_PRINT2 (" Popping pattern %p:\n", pat); \
1745 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1747 /* Restore register info. */ \
1748 high_reg = (active_reg_t) POP_FAILURE_INT (); \
1749 DEBUG_PRINT2 (" Popping high active reg: %ld\n", high_reg); \
1751 low_reg = (active_reg_t) POP_FAILURE_INT (); \
1752 DEBUG_PRINT2 (" Popping low active reg: %ld\n", low_reg); \
1755 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
1757 DEBUG_PRINT2 (" Popping reg: %ld\n", this_reg); \
1759 reg_info[this_reg].word = POP_FAILURE_ELT (); \
1760 DEBUG_PRINT2 (" info: %p\n", \
1761 reg_info[this_reg].word.pointer); \
1763 regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1764 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1766 regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1767 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1771 for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1773 reg_info[this_reg].word.integer = 0; \
1774 regend[this_reg] = 0; \
1775 regstart[this_reg] = 0; \
1777 highest_active_reg = high_reg; \
1780 set_regs_matched_done = 0; \
1781 DEBUG_STATEMENT (nfailure_points_popped++); \
1782 } /* POP_FAILURE_POINT */
1784 /* Structure for per-register (a.k.a. per-group) information.
1785 Other register information, such as the
1786 starting and ending positions (which are addresses), and the list of
1787 inner groups (which is a bits list) are maintained in separate
1790 We are making a (strictly speaking) nonportable assumption here: that
1791 the compiler will pack our bit fields into something that fits into
1792 the type of `word', i.e., is something that fits into one item on the
1796 /* Declarations and macros for re_match_2. */
1800 PREFIX(fail_stack_elt_t) word;
1803 /* This field is one if this group can match the empty string,
1804 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
1805 # define MATCH_NULL_UNSET_VALUE 3
1806 unsigned match_null_string_p : 2;
1807 unsigned is_active : 1;
1808 unsigned matched_something : 1;
1809 unsigned ever_matched_something : 1;
1811 } PREFIX(register_info_type);
1813 # ifndef DEFINED_ONCE
1814 # define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
1815 # define IS_ACTIVE(R) ((R).bits.is_active)
1816 # define MATCHED_SOMETHING(R) ((R).bits.matched_something)
1817 # define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
1820 /* Call this when have matched a real character; it sets `matched' flags
1821 for the subexpressions which we are currently inside. Also records
1822 that those subexprs have matched. */
1823 # define SET_REGS_MATCHED() \
1826 if (!set_regs_matched_done) \
1829 set_regs_matched_done = 1; \
1830 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
1832 MATCHED_SOMETHING (reg_info[r]) \
1833 = EVER_MATCHED_SOMETHING (reg_info[r]) \
1839 # endif /* not DEFINED_ONCE */
1841 /* Registers are set to a sentinel when they haven't yet matched. */
1842 static CHAR_T PREFIX(reg_unset_dummy);
1843 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1844 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1846 /* Subroutine declarations and macros for regex_compile. */
1847 static void PREFIX(store_op1) (re_opcode_t op, UCHAR_T *loc, int arg);
1848 static void PREFIX(store_op2) (re_opcode_t op, UCHAR_T *loc,
1849 int arg1, int arg2);
1850 static void PREFIX(insert_op1) (re_opcode_t op, UCHAR_T *loc,
1851 int arg, UCHAR_T *end);
1852 static void PREFIX(insert_op2) (re_opcode_t op, UCHAR_T *loc,
1853 int arg1, int arg2, UCHAR_T *end);
1854 static boolean PREFIX(at_begline_loc_p) (const CHAR_T *pattern,
1856 reg_syntax_t syntax);
1857 static boolean PREFIX(at_endline_loc_p) (const CHAR_T *p,
1859 reg_syntax_t syntax);
1861 static reg_errcode_t wcs_compile_range (CHAR_T range_start,
1862 const CHAR_T **p_ptr,
1865 reg_syntax_t syntax,
1868 static void insert_space (int num, CHAR_T *loc, CHAR_T *end);
1870 static reg_errcode_t byte_compile_range (unsigned int range_start,
1874 reg_syntax_t syntax,
1878 /* Fetch the next character in the uncompiled pattern---translating it
1879 if necessary. Also cast from a signed character in the constant
1880 string passed to us by the user to an unsigned char that we can use
1881 as an array index (in, e.g., `translate'). */
1882 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1883 because it is impossible to allocate 4GB array for some encodings
1884 which have 4 byte character_set like UCS4. */
1887 # define PATFETCH(c) \
1888 do {if (p == pend) return REG_EEND; \
1889 c = (UCHAR_T) *p++; \
1890 if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c]; \
1893 # define PATFETCH(c) \
1894 do {if (p == pend) return REG_EEND; \
1895 c = (unsigned char) *p++; \
1896 if (translate) c = (unsigned char) translate[c]; \
1901 /* Fetch the next character in the uncompiled pattern, with no
1903 # define PATFETCH_RAW(c) \
1904 do {if (p == pend) return REG_EEND; \
1905 c = (UCHAR_T) *p++; \
1908 /* Go backwards one character in the pattern. */
1909 # define PATUNFETCH p--
1912 /* If `translate' is non-null, return translate[D], else just D. We
1913 cast the subscript to translate because some data is declared as
1914 `char *', to avoid warnings when a string constant is passed. But
1915 when we use a character as a subscript we must make it unsigned. */
1916 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1917 because it is impossible to allocate 4GB array for some encodings
1918 which have 4 byte character_set like UCS4. */
1922 # define TRANSLATE(d) \
1923 ((translate && ((UCHAR_T) (d)) <= 0xff) \
1924 ? (char) translate[(unsigned char) (d)] : (d))
1926 # define TRANSLATE(d) \
1927 (translate ? (char) translate[(unsigned char) (d)] : (d))
1932 /* Macros for outputting the compiled pattern into `buffer'. */
1934 /* If the buffer isn't allocated when it comes in, use this. */
1935 # define INIT_BUF_SIZE (32 * sizeof(UCHAR_T))
1937 /* Make sure we have at least N more bytes of space in buffer. */
1939 # define GET_BUFFER_SPACE(n) \
1940 while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR \
1941 + (n)*sizeof(CHAR_T)) > bufp->allocated) \
1944 # define GET_BUFFER_SPACE(n) \
1945 while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated) \
1949 /* Make sure we have one more byte of buffer space and then add C to it. */
1950 # define BUF_PUSH(c) \
1952 GET_BUFFER_SPACE (1); \
1953 *b++ = (UCHAR_T) (c); \
1957 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
1958 # define BUF_PUSH_2(c1, c2) \
1960 GET_BUFFER_SPACE (2); \
1961 *b++ = (UCHAR_T) (c1); \
1962 *b++ = (UCHAR_T) (c2); \
1966 /* As with BUF_PUSH_2, except for three bytes. */
1967 # define BUF_PUSH_3(c1, c2, c3) \
1969 GET_BUFFER_SPACE (3); \
1970 *b++ = (UCHAR_T) (c1); \
1971 *b++ = (UCHAR_T) (c2); \
1972 *b++ = (UCHAR_T) (c3); \
1975 /* Store a jump with opcode OP at LOC to location TO. We store a
1976 relative address offset by the three bytes the jump itself occupies. */
1977 # define STORE_JUMP(op, loc, to) \
1978 PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
1980 /* Likewise, for a two-argument jump. */
1981 # define STORE_JUMP2(op, loc, to, arg) \
1982 PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
1984 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
1985 # define INSERT_JUMP(op, loc, to) \
1986 PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
1988 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
1989 # define INSERT_JUMP2(op, loc, to, arg) \
1990 PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
1993 /* This is not an arbitrary limit: the arguments which represent offsets
1994 into the pattern are two bytes long. So if 2^16 bytes turns out to
1995 be too small, many things would have to change. */
1996 /* Any other compiler which, like MSC, has allocation limit below 2^16
1997 bytes will have to use approach similar to what was done below for
1998 MSC and drop MAX_BUF_SIZE a bit. Otherwise you may end up
1999 reallocating to 0 bytes. Such thing is not going to work too well.
2000 You have been warned!! */
2001 # ifndef DEFINED_ONCE
2002 # if defined _MSC_VER && !defined WIN32
2003 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2004 The REALLOC define eliminates a flurry of conversion warnings,
2005 but is not required. */
2006 # define MAX_BUF_SIZE 65500L
2007 # define REALLOC(p,s) realloc ((p), (size_t) (s))
2009 # define MAX_BUF_SIZE (1L << 16)
2010 # define REALLOC(p,s) realloc ((p), (s))
2013 /* Extend the buffer by twice its current size via realloc and
2014 reset the pointers that pointed into the old block to point to the
2015 correct places in the new one. If extending the buffer results in it
2016 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
2017 # if __BOUNDED_POINTERS__
2018 # define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
2019 # define MOVE_BUFFER_POINTER(P) \
2020 (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
2021 # define ELSE_EXTEND_BUFFER_HIGH_BOUND \
2024 SET_HIGH_BOUND (b); \
2025 SET_HIGH_BOUND (begalt); \
2026 if (fixup_alt_jump) \
2027 SET_HIGH_BOUND (fixup_alt_jump); \
2029 SET_HIGH_BOUND (laststart); \
2030 if (pending_exact) \
2031 SET_HIGH_BOUND (pending_exact); \
2034 # define MOVE_BUFFER_POINTER(P) (P) += incr
2035 # define ELSE_EXTEND_BUFFER_HIGH_BOUND
2037 # endif /* not DEFINED_ONCE */
2040 # define EXTEND_BUFFER() \
2042 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2044 if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE) \
2046 bufp->allocated <<= 1; \
2047 if (bufp->allocated > MAX_BUF_SIZE) \
2048 bufp->allocated = MAX_BUF_SIZE; \
2049 /* How many characters the new buffer can have? */ \
2050 wchar_count = bufp->allocated / sizeof(UCHAR_T); \
2051 if (wchar_count == 0) wchar_count = 1; \
2052 /* Truncate the buffer to CHAR_T align. */ \
2053 bufp->allocated = wchar_count * sizeof(UCHAR_T); \
2054 RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T); \
2055 bufp->buffer = (char*)COMPILED_BUFFER_VAR; \
2056 if (COMPILED_BUFFER_VAR == NULL) \
2057 return REG_ESPACE; \
2058 /* If the buffer moved, move all the pointers into it. */ \
2059 if (old_buffer != COMPILED_BUFFER_VAR) \
2061 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2062 MOVE_BUFFER_POINTER (b); \
2063 MOVE_BUFFER_POINTER (begalt); \
2064 if (fixup_alt_jump) \
2065 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2067 MOVE_BUFFER_POINTER (laststart); \
2068 if (pending_exact) \
2069 MOVE_BUFFER_POINTER (pending_exact); \
2071 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2074 # define EXTEND_BUFFER() \
2076 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2077 if (bufp->allocated == MAX_BUF_SIZE) \
2079 bufp->allocated <<= 1; \
2080 if (bufp->allocated > MAX_BUF_SIZE) \
2081 bufp->allocated = MAX_BUF_SIZE; \
2082 bufp->buffer = REALLOC (COMPILED_BUFFER_VAR, bufp->allocated); \
2083 if (COMPILED_BUFFER_VAR == NULL) \
2084 return REG_ESPACE; \
2085 /* If the buffer moved, move all the pointers into it. */ \
2086 if (old_buffer != COMPILED_BUFFER_VAR) \
2088 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2089 MOVE_BUFFER_POINTER (b); \
2090 MOVE_BUFFER_POINTER (begalt); \
2091 if (fixup_alt_jump) \
2092 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2094 MOVE_BUFFER_POINTER (laststart); \
2095 if (pending_exact) \
2096 MOVE_BUFFER_POINTER (pending_exact); \
2098 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2102 # ifndef DEFINED_ONCE
2103 /* Since we have one byte reserved for the register number argument to
2104 {start,stop}_memory, the maximum number of groups we can report
2105 things about is what fits in that byte. */
2106 # define MAX_REGNUM 255
2108 /* But patterns can have more than `MAX_REGNUM' registers. We just
2109 ignore the excess. */
2110 typedef unsigned regnum_t;
2113 /* Macros for the compile stack. */
2115 /* Since offsets can go either forwards or backwards, this type needs to
2116 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
2117 /* int may be not enough when sizeof(int) == 2. */
2118 typedef long pattern_offset_t;
2122 pattern_offset_t begalt_offset;
2123 pattern_offset_t fixup_alt_jump;
2124 pattern_offset_t inner_group_offset;
2125 pattern_offset_t laststart_offset;
2127 } compile_stack_elt_t;
2132 compile_stack_elt_t *stack;
2134 unsigned avail; /* Offset of next open position. */
2135 } compile_stack_type;
2138 # define INIT_COMPILE_STACK_SIZE 32
2140 # define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
2141 # define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
2143 /* The next available element. */
2144 # define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2146 # endif /* not DEFINED_ONCE */
2148 /* Set the bit for character C in a list. */
2149 # ifndef DEFINED_ONCE
2150 # define SET_LIST_BIT(c) \
2151 (b[((unsigned char) (c)) / BYTEWIDTH] \
2152 |= 1 << (((unsigned char) c) % BYTEWIDTH))
2153 # endif /* DEFINED_ONCE */
2155 /* Get the next unsigned number in the uncompiled pattern. */
2156 # define GET_UNSIGNED_NUMBER(num) \
2161 if (c < '0' || c > '9') \
2163 if (num <= RE_DUP_MAX) \
2167 num = num * 10 + c - '0'; \
2172 # ifndef DEFINED_ONCE
2173 # if defined _LIBC || WIDE_CHAR_SUPPORT
2174 /* The GNU C library provides support for user-defined character classes
2175 and the functions from ISO C amendement 1. */
2176 # ifdef CHARCLASS_NAME_MAX
2177 # define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2179 /* This shouldn't happen but some implementation might still have this
2180 problem. Use a reasonable default value. */
2181 # define CHAR_CLASS_MAX_LENGTH 256
2185 # define IS_CHAR_CLASS(string) __wctype (string)
2187 # define IS_CHAR_CLASS(string) wctype (string)
2190 # define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
2192 # define IS_CHAR_CLASS(string) \
2193 (STREQ (string, "alpha") || STREQ (string, "upper") \
2194 || STREQ (string, "lower") || STREQ (string, "digit") \
2195 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
2196 || STREQ (string, "space") || STREQ (string, "print") \
2197 || STREQ (string, "punct") || STREQ (string, "graph") \
2198 || STREQ (string, "cntrl") || STREQ (string, "blank"))
2200 # endif /* DEFINED_ONCE */
2202 # ifndef MATCH_MAY_ALLOCATE
2204 /* If we cannot allocate large objects within re_match_2_internal,
2205 we make the fail stack and register vectors global.
2206 The fail stack, we grow to the maximum size when a regexp
2208 The register vectors, we adjust in size each time we
2209 compile a regexp, according to the number of registers it needs. */
2211 static PREFIX(fail_stack_type) fail_stack;
2213 /* Size with which the following vectors are currently allocated.
2214 That is so we can make them bigger as needed,
2215 but never make them smaller. */
2216 # ifdef DEFINED_ONCE
2217 static int regs_allocated_size;
2219 static const char ** regstart, ** regend;
2220 static const char ** old_regstart, ** old_regend;
2221 static const char **best_regstart, **best_regend;
2222 static const char **reg_dummy;
2223 # endif /* DEFINED_ONCE */
2225 static PREFIX(register_info_type) *PREFIX(reg_info);
2226 static PREFIX(register_info_type) *PREFIX(reg_info_dummy);
2228 /* Make the register vectors big enough for NUM_REGS registers,
2229 but don't make them smaller. */
2232 PREFIX(regex_grow_registers) (int num_regs)
2234 if (num_regs > regs_allocated_size)
2236 RETALLOC_IF (regstart, num_regs, const char *);
2237 RETALLOC_IF (regend, num_regs, const char *);
2238 RETALLOC_IF (old_regstart, num_regs, const char *);
2239 RETALLOC_IF (old_regend, num_regs, const char *);
2240 RETALLOC_IF (best_regstart, num_regs, const char *);
2241 RETALLOC_IF (best_regend, num_regs, const char *);
2242 RETALLOC_IF (PREFIX(reg_info), num_regs, PREFIX(register_info_type));
2243 RETALLOC_IF (reg_dummy, num_regs, const char *);
2244 RETALLOC_IF (PREFIX(reg_info_dummy), num_regs, PREFIX(register_info_type));
2246 regs_allocated_size = num_regs;
2250 # endif /* not MATCH_MAY_ALLOCATE */
2252 # ifndef DEFINED_ONCE
2253 static boolean group_in_compile_stack (compile_stack_type
2256 # endif /* not DEFINED_ONCE */
2258 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2259 Returns one of error codes defined in `regex.h', or zero for success.
2261 Assumes the `allocated' (and perhaps `buffer') and `translate'
2262 fields are set in BUFP on entry.
2264 If it succeeds, results are put in BUFP (if it returns an error, the
2265 contents of BUFP are undefined):
2266 `buffer' is the compiled pattern;
2267 `syntax' is set to SYNTAX;
2268 `used' is set to the length of the compiled pattern;
2269 `fastmap_accurate' is zero;
2270 `re_nsub' is the number of subexpressions in PATTERN;
2271 `not_bol' and `not_eol' are zero;
2273 The `fastmap' and `newline_anchor' fields are neither
2274 examined nor set. */
2276 /* Return, freeing storage we allocated. */
2278 # define FREE_STACK_RETURN(value) \
2279 return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2281 # define FREE_STACK_RETURN(value) \
2282 return (free (compile_stack.stack), value)
2285 static reg_errcode_t
2286 PREFIX(regex_compile) (const char *ARG_PREFIX(pattern),
2287 size_t ARG_PREFIX(size),
2288 reg_syntax_t syntax,
2289 struct re_pattern_buffer *bufp)
2291 /* We fetch characters from PATTERN here. Even though PATTERN is
2292 `char *' (i.e., signed), we declare these variables as unsigned, so
2293 they can be reliably used as array indices. */
2294 register UCHAR_T c, c1;
2297 /* A temporary space to keep wchar_t pattern and compiled pattern. */
2298 CHAR_T *pattern, *COMPILED_BUFFER_VAR;
2300 /* offset buffer for optimization. See convert_mbs_to_wc. */
2301 int *mbs_offset = NULL;
2302 /* It hold whether each wchar_t is binary data or not. */
2303 char *is_binary = NULL;
2304 /* A flag whether exactn is handling binary data or not. */
2305 char is_exactn_bin = FALSE;
2308 /* A random temporary spot in PATTERN. */
2311 /* Points to the end of the buffer, where we should append. */
2312 register UCHAR_T *b;
2314 /* Keeps track of unclosed groups. */
2315 compile_stack_type compile_stack;
2317 /* Points to the current (ending) position in the pattern. */
2322 const CHAR_T *p = pattern;
2323 const CHAR_T *pend = pattern + size;
2326 /* How to translate the characters in the pattern. */
2327 RE_TRANSLATE_TYPE translate = bufp->translate;
2329 /* Address of the count-byte of the most recently inserted `exactn'
2330 command. This makes it possible to tell if a new exact-match
2331 character can be added to that command or if the character requires
2332 a new `exactn' command. */
2333 UCHAR_T *pending_exact = 0;
2335 /* Address of start of the most recently finished expression.
2336 This tells, e.g., postfix * where to find the start of its
2337 operand. Reset at the beginning of groups and alternatives. */
2338 UCHAR_T *laststart = 0;
2340 /* Address of beginning of regexp, or inside of last group. */
2343 /* Address of the place where a forward jump should go to the end of
2344 the containing expression. Each alternative of an `or' -- except the
2345 last -- ends with a forward jump of this sort. */
2346 UCHAR_T *fixup_alt_jump = 0;
2348 /* Counts open-groups as they are encountered. Remembered for the
2349 matching close-group on the compile stack, so the same register
2350 number is put in the stop_memory as the start_memory. */
2351 regnum_t regnum = 0;
2354 /* Initialize the wchar_t PATTERN and offset_buffer. */
2355 p = pend = pattern = TALLOC(csize + 1, CHAR_T);
2356 mbs_offset = TALLOC(csize + 1, int);
2357 is_binary = TALLOC(csize + 1, char);
2358 if (pattern == NULL || mbs_offset == NULL || is_binary == NULL)
2365 pattern[csize] = L'\0'; /* sentinel */
2366 size = convert_mbs_to_wcs(pattern, cpattern, csize, mbs_offset, is_binary);
2378 DEBUG_PRINT1 ("\nCompiling pattern: ");
2381 unsigned debug_count;
2383 for (debug_count = 0; debug_count < size; debug_count++)
2384 PUT_CHAR (pattern[debug_count]);
2389 /* Initialize the compile stack. */
2390 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2391 if (compile_stack.stack == NULL)
2401 compile_stack.size = INIT_COMPILE_STACK_SIZE;
2402 compile_stack.avail = 0;
2404 /* Initialize the pattern buffer. */
2405 bufp->syntax = syntax;
2406 bufp->fastmap_accurate = 0;
2407 bufp->not_bol = bufp->not_eol = 0;
2409 /* Set `used' to zero, so that if we return an error, the pattern
2410 printer (for debugging) will think there's no pattern. We reset it
2414 /* Always count groups, whether or not bufp->no_sub is set. */
2417 #if !defined emacs && !defined SYNTAX_TABLE
2418 /* Initialize the syntax table. */
2419 init_syntax_once ();
2422 if (bufp->allocated == 0)
2425 { /* If zero allocated, but buffer is non-null, try to realloc
2426 enough space. This loses if buffer's address is bogus, but
2427 that is the user's responsibility. */
2429 /* Free bufp->buffer and allocate an array for wchar_t pattern
2432 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE/sizeof(UCHAR_T),
2435 RETALLOC (COMPILED_BUFFER_VAR, INIT_BUF_SIZE, UCHAR_T);
2439 { /* Caller did not allocate a buffer. Do it for them. */
2440 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE / sizeof(UCHAR_T),
2444 if (!COMPILED_BUFFER_VAR) FREE_STACK_RETURN (REG_ESPACE);
2446 bufp->buffer = (char*)COMPILED_BUFFER_VAR;
2448 bufp->allocated = INIT_BUF_SIZE;
2452 COMPILED_BUFFER_VAR = (UCHAR_T*) bufp->buffer;
2455 begalt = b = COMPILED_BUFFER_VAR;
2457 /* Loop through the uncompiled pattern until we're at the end. */
2466 if ( /* If at start of pattern, it's an operator. */
2468 /* If context independent, it's an operator. */
2469 || syntax & RE_CONTEXT_INDEP_ANCHORS
2470 /* Otherwise, depends on what's come before. */
2471 || PREFIX(at_begline_loc_p) (pattern, p, syntax))
2481 if ( /* If at end of pattern, it's an operator. */
2483 /* If context independent, it's an operator. */
2484 || syntax & RE_CONTEXT_INDEP_ANCHORS
2485 /* Otherwise, depends on what's next. */
2486 || PREFIX(at_endline_loc_p) (p, pend, syntax))
2496 if ((syntax & RE_BK_PLUS_QM)
2497 || (syntax & RE_LIMITED_OPS))
2501 /* If there is no previous pattern... */
2504 if (syntax & RE_CONTEXT_INVALID_OPS)
2505 FREE_STACK_RETURN (REG_BADRPT);
2506 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2511 /* Are we optimizing this jump? */
2512 boolean keep_string_p = false;
2514 /* 1 means zero (many) matches is allowed. */
2515 char zero_times_ok = 0, many_times_ok = 0;
2517 /* If there is a sequence of repetition chars, collapse it
2518 down to just one (the right one). We can't combine
2519 interval operators with these because of, e.g., `a{2}*',
2520 which should only match an even number of `a's. */
2524 zero_times_ok |= c != '+';
2525 many_times_ok |= c != '?';
2533 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
2536 else if (syntax & RE_BK_PLUS_QM && c == '\\')
2538 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2541 if (!(c1 == '+' || c1 == '?'))
2556 /* If we get here, we found another repeat character. */
2559 /* Star, etc. applied to an empty pattern is equivalent
2560 to an empty pattern. */
2564 /* Now we know whether or not zero matches is allowed
2565 and also whether or not two or more matches is allowed. */
2567 { /* More than one repetition is allowed, so put in at the
2568 end a backward relative jump from `b' to before the next
2569 jump we're going to put in below (which jumps from
2570 laststart to after this jump).
2572 But if we are at the `*' in the exact sequence `.*\n',
2573 insert an unconditional jump backwards to the .,
2574 instead of the beginning of the loop. This way we only
2575 push a failure point once, instead of every time
2576 through the loop. */
2577 assert (p - 1 > pattern);
2579 /* Allocate the space for the jump. */
2580 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2582 /* We know we are not at the first character of the pattern,
2583 because laststart was nonzero. And we've already
2584 incremented `p', by the way, to be the character after
2585 the `*'. Do we have to do something analogous here
2586 for null bytes, because of RE_DOT_NOT_NULL? */
2587 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2589 && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2590 && !(syntax & RE_DOT_NEWLINE))
2591 { /* We have .*\n. */
2592 STORE_JUMP (jump, b, laststart);
2593 keep_string_p = true;
2596 /* Anything else. */
2597 STORE_JUMP (maybe_pop_jump, b, laststart -
2598 (1 + OFFSET_ADDRESS_SIZE));
2600 /* We've added more stuff to the buffer. */
2601 b += 1 + OFFSET_ADDRESS_SIZE;
2604 /* On failure, jump from laststart to b + 3, which will be the
2605 end of the buffer after this jump is inserted. */
2606 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2608 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2609 INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2611 laststart, b + 1 + OFFSET_ADDRESS_SIZE);
2613 b += 1 + OFFSET_ADDRESS_SIZE;
2617 /* At least one repetition is required, so insert a
2618 `dummy_failure_jump' before the initial
2619 `on_failure_jump' instruction of the loop. This
2620 effects a skip over that instruction the first time
2621 we hit that loop. */
2622 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2623 INSERT_JUMP (dummy_failure_jump, laststart, laststart +
2624 2 + 2 * OFFSET_ADDRESS_SIZE);
2625 b += 1 + OFFSET_ADDRESS_SIZE;
2639 boolean had_char_class = false;
2641 CHAR_T range_start = 0xffffffff;
2643 unsigned int range_start = 0xffffffff;
2645 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2648 /* We assume a charset(_not) structure as a wchar_t array.
2649 charset[0] = (re_opcode_t) charset(_not)
2650 charset[1] = l (= length of char_classes)
2651 charset[2] = m (= length of collating_symbols)
2652 charset[3] = n (= length of equivalence_classes)
2653 charset[4] = o (= length of char_ranges)
2654 charset[5] = p (= length of chars)
2656 charset[6] = char_class (wctype_t)
2657 charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2659 charset[l+5] = char_class (wctype_t)
2661 charset[l+6] = collating_symbol (wchar_t)
2663 charset[l+m+5] = collating_symbol (wchar_t)
2664 ifdef _LIBC we use the index if
2665 _NL_COLLATE_SYMB_EXTRAMB instead of
2668 charset[l+m+6] = equivalence_classes (wchar_t)
2670 charset[l+m+n+5] = equivalence_classes (wchar_t)
2671 ifdef _LIBC we use the index in
2672 _NL_COLLATE_WEIGHT instead of
2675 charset[l+m+n+6] = range_start
2676 charset[l+m+n+7] = range_end
2678 charset[l+m+n+2o+4] = range_start
2679 charset[l+m+n+2o+5] = range_end
2680 ifdef _LIBC we use the value looked up
2681 in _NL_COLLATE_COLLSEQ instead of
2684 charset[l+m+n+2o+6] = char
2686 charset[l+m+n+2o+p+5] = char
2690 /* We need at least 6 spaces: the opcode, the length of
2691 char_classes, the length of collating_symbols, the length of
2692 equivalence_classes, the length of char_ranges, the length of
2694 GET_BUFFER_SPACE (6);
2696 /* Save b as laststart. And We use laststart as the pointer
2697 to the first element of the charset here.
2698 In other words, laststart[i] indicates charset[i]. */
2701 /* We test `*p == '^' twice, instead of using an if
2702 statement, so we only need one BUF_PUSH. */
2703 BUF_PUSH (*p == '^' ? charset_not : charset);
2707 /* Push the length of char_classes, the length of
2708 collating_symbols, the length of equivalence_classes, the
2709 length of char_ranges and the length of chars. */
2710 BUF_PUSH_3 (0, 0, 0);
2713 /* Remember the first position in the bracket expression. */
2716 /* charset_not matches newline according to a syntax bit. */
2717 if ((re_opcode_t) b[-6] == charset_not
2718 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2721 laststart[5]++; /* Update the length of characters */
2724 /* Read in characters and ranges, setting map bits. */
2727 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2731 /* \ might escape characters inside [...] and [^...]. */
2732 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2734 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2738 laststart[5]++; /* Update the length of chars */
2743 /* Could be the end of the bracket expression. If it's
2744 not (i.e., when the bracket expression is `[]' so
2745 far), the ']' character bit gets set way below. */
2746 if (c == ']' && p != p1 + 1)
2749 /* Look ahead to see if it's a range when the last thing
2750 was a character class. */
2751 if (had_char_class && c == '-' && *p != ']')
2752 FREE_STACK_RETURN (REG_ERANGE);
2754 /* Look ahead to see if it's a range when the last thing
2755 was a character: if this is a hyphen not at the
2756 beginning or the end of a list, then it's the range
2759 && !(p - 2 >= pattern && p[-2] == '[')
2760 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2764 /* Allocate the space for range_start and range_end. */
2765 GET_BUFFER_SPACE (2);
2766 /* Update the pointer to indicate end of buffer. */
2768 ret = wcs_compile_range (range_start, &p, pend, translate,
2769 syntax, b, laststart);
2770 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2771 range_start = 0xffffffff;
2773 else if (p[0] == '-' && p[1] != ']')
2774 { /* This handles ranges made up of characters only. */
2777 /* Move past the `-'. */
2779 /* Allocate the space for range_start and range_end. */
2780 GET_BUFFER_SPACE (2);
2781 /* Update the pointer to indicate end of buffer. */
2783 ret = wcs_compile_range (c, &p, pend, translate, syntax, b,
2785 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2786 range_start = 0xffffffff;
2789 /* See if we're at the beginning of a possible character
2791 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2792 { /* Leave room for the null. */
2793 char str[CHAR_CLASS_MAX_LENGTH + 1];
2798 /* If pattern is `[[:'. */
2799 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2804 if ((c == ':' && *p == ']') || p == pend)
2806 if (c1 < CHAR_CLASS_MAX_LENGTH)
2809 /* This is in any case an invalid class name. */
2814 /* If isn't a word bracketed by `[:' and `:]':
2815 undo the ending character, the letters, and leave
2816 the leading `:' and `[' (but store them as character). */
2817 if (c == ':' && *p == ']')
2822 /* Query the character class as wctype_t. */
2823 wt = IS_CHAR_CLASS (str);
2825 FREE_STACK_RETURN (REG_ECTYPE);
2827 /* Throw away the ] at the end of the character
2831 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2833 /* Allocate the space for character class. */
2834 GET_BUFFER_SPACE(CHAR_CLASS_SIZE);
2835 /* Update the pointer to indicate end of buffer. */
2836 b += CHAR_CLASS_SIZE;
2837 /* Move data which follow character classes
2838 not to violate the data. */
2839 insert_space(CHAR_CLASS_SIZE,
2840 laststart + 6 + laststart[1],
2842 alignedp = ((uintptr_t)(laststart + 6 + laststart[1])
2843 + __alignof__(wctype_t) - 1)
2844 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2845 /* Store the character class. */
2846 *((wctype_t*)alignedp) = wt;
2847 /* Update length of char_classes */
2848 laststart[1] += CHAR_CLASS_SIZE;
2850 had_char_class = true;
2859 laststart[5] += 2; /* Update the length of characters */
2861 had_char_class = false;
2864 else if (syntax & RE_CHAR_CLASSES && c == '[' && (*p == '='
2867 CHAR_T str[128]; /* Should be large enough. */
2868 CHAR_T delim = *p; /* '=' or '.' */
2871 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2876 /* If pattern is `[[=' or '[[.'. */
2877 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2882 if ((c == delim && *p == ']') || p == pend)
2884 if (c1 < sizeof (str) - 1)
2887 /* This is in any case an invalid class name. */
2892 if (c == delim && *p == ']' && str[0] != '\0')
2894 unsigned int i, offset;
2895 /* If we have no collation data we use the default
2896 collation in which each character is in a class
2897 by itself. It also means that ASCII is the
2898 character set and therefore we cannot have character
2899 with more than one byte in the multibyte
2902 /* If not defined _LIBC, we push the name and
2903 `\0' for the sake of matching performance. */
2904 int datasize = c1 + 1;
2912 FREE_STACK_RETURN (REG_ECOLLATE);
2917 const int32_t *table;
2918 const int32_t *weights;
2919 const int32_t *extra;
2920 const int32_t *indirect;
2923 /* This #include defines a local function! */
2924 # include <locale/weightwc.h>
2928 /* We push the index for equivalence class. */
2931 table = (const int32_t *)
2932 _NL_CURRENT (LC_COLLATE,
2933 _NL_COLLATE_TABLEWC);
2934 weights = (const int32_t *)
2935 _NL_CURRENT (LC_COLLATE,
2936 _NL_COLLATE_WEIGHTWC);
2937 extra = (const int32_t *)
2938 _NL_CURRENT (LC_COLLATE,
2939 _NL_COLLATE_EXTRAWC);
2940 indirect = (const int32_t *)
2941 _NL_CURRENT (LC_COLLATE,
2942 _NL_COLLATE_INDIRECTWC);
2944 idx = findidx ((const wint_t**)&cp);
2945 if (idx == 0 || cp < (wint_t*) str + c1)
2946 /* This is no valid character. */
2947 FREE_STACK_RETURN (REG_ECOLLATE);
2949 str[0] = (wchar_t)idx;
2951 else /* delim == '.' */
2953 /* We push collation sequence value
2954 for collating symbol. */
2956 const int32_t *symb_table;
2957 const unsigned char *extra;
2964 /* We have to convert the name to a single-byte
2965 string. This is possible since the names
2966 consist of ASCII characters and the internal
2967 representation is UCS4. */
2968 for (i = 0; i < c1; ++i)
2969 char_str[i] = str[i];
2972 _NL_CURRENT_WORD (LC_COLLATE,
2973 _NL_COLLATE_SYMB_HASH_SIZEMB);
2974 symb_table = (const int32_t *)
2975 _NL_CURRENT (LC_COLLATE,
2976 _NL_COLLATE_SYMB_TABLEMB);
2977 extra = (const unsigned char *)
2978 _NL_CURRENT (LC_COLLATE,
2979 _NL_COLLATE_SYMB_EXTRAMB);
2981 /* Locate the character in the hashing table. */
2982 hash = elem_hash (char_str, c1);
2985 elem = hash % table_size;
2986 second = hash % (table_size - 2);
2987 while (symb_table[2 * elem] != 0)
2989 /* First compare the hashing value. */
2990 if (symb_table[2 * elem] == hash
2991 && c1 == extra[symb_table[2 * elem + 1]]
2992 && memcmp (char_str,
2993 &extra[symb_table[2 * elem + 1]
2996 /* Yep, this is the entry. */
2997 idx = symb_table[2 * elem + 1];
2998 idx += 1 + extra[idx];
3006 if (symb_table[2 * elem] != 0)
3008 /* Compute the index of the byte sequence
3010 idx += 1 + extra[idx];
3011 /* Adjust for the alignment. */
3012 idx = (idx + 3) & ~3;
3014 str[0] = (wchar_t) idx + 4;
3016 else if (symb_table[2 * elem] == 0 && c1 == 1)
3018 /* No valid character. Match it as a
3019 single byte character. */
3020 had_char_class = false;
3022 /* Update the length of characters */
3024 range_start = str[0];
3026 /* Throw away the ] at the end of the
3027 collating symbol. */
3029 /* exit from the switch block. */
3033 FREE_STACK_RETURN (REG_ECOLLATE);
3038 /* Throw away the ] at the end of the equivalence
3039 class (or collating symbol). */
3042 /* Allocate the space for the equivalence class
3043 (or collating symbol) (and '\0' if needed). */
3044 GET_BUFFER_SPACE(datasize);
3045 /* Update the pointer to indicate end of buffer. */
3049 { /* equivalence class */
3050 /* Calculate the offset of char_ranges,
3051 which is next to equivalence_classes. */
3052 offset = laststart[1] + laststart[2]
3055 insert_space(datasize, laststart + offset, b - 1);
3057 /* Write the equivalence_class and \0. */
3058 for (i = 0 ; i < datasize ; i++)
3059 laststart[offset + i] = str[i];
3061 /* Update the length of equivalence_classes. */
3062 laststart[3] += datasize;
3063 had_char_class = true;
3065 else /* delim == '.' */
3066 { /* collating symbol */
3067 /* Calculate the offset of the equivalence_classes,
3068 which is next to collating_symbols. */
3069 offset = laststart[1] + laststart[2] + 6;
3070 /* Insert space and write the collationg_symbol
3072 insert_space(datasize, laststart + offset, b-1);
3073 for (i = 0 ; i < datasize ; i++)
3074 laststart[offset + i] = str[i];
3076 /* In re_match_2_internal if range_start < -1, we
3077 assume -range_start is the offset of the
3078 collating symbol which is specified as
3079 the character of the range start. So we assign
3080 -(laststart[1] + laststart[2] + 6) to
3082 range_start = -(laststart[1] + laststart[2] + 6);
3083 /* Update the length of collating_symbol. */
3084 laststart[2] += datasize;
3085 had_char_class = false;
3095 laststart[5] += 2; /* Update the length of characters */
3096 range_start = delim;
3097 had_char_class = false;
3102 had_char_class = false;
3104 laststart[5]++; /* Update the length of characters */
3110 /* Ensure that we have enough space to push a charset: the
3111 opcode, the length count, and the bitset; 34 bytes in all. */
3112 GET_BUFFER_SPACE (34);
3116 /* We test `*p == '^' twice, instead of using an if
3117 statement, so we only need one BUF_PUSH. */
3118 BUF_PUSH (*p == '^' ? charset_not : charset);
3122 /* Remember the first position in the bracket expression. */
3125 /* Push the number of bytes in the bitmap. */
3126 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
3128 /* Clear the whole map. */
3129 bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
3131 /* charset_not matches newline according to a syntax bit. */
3132 if ((re_opcode_t) b[-2] == charset_not
3133 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
3134 SET_LIST_BIT ('\n');
3136 /* Read in characters and ranges, setting map bits. */
3139 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3143 /* \ might escape characters inside [...] and [^...]. */
3144 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
3146 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3154 /* Could be the end of the bracket expression. If it's
3155 not (i.e., when the bracket expression is `[]' so
3156 far), the ']' character bit gets set way below. */
3157 if (c == ']' && p != p1 + 1)
3160 /* Look ahead to see if it's a range when the last thing
3161 was a character class. */
3162 if (had_char_class && c == '-' && *p != ']')
3163 FREE_STACK_RETURN (REG_ERANGE);
3165 /* Look ahead to see if it's a range when the last thing
3166 was a character: if this is a hyphen not at the
3167 beginning or the end of a list, then it's the range
3170 && !(p - 2 >= pattern && p[-2] == '[')
3171 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
3175 = byte_compile_range (range_start, &p, pend, translate,
3177 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3178 range_start = 0xffffffff;
3181 else if (p[0] == '-' && p[1] != ']')
3182 { /* This handles ranges made up of characters only. */
3185 /* Move past the `-'. */
3188 ret = byte_compile_range (c, &p, pend, translate, syntax, b);
3189 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3190 range_start = 0xffffffff;
3193 /* See if we're at the beginning of a possible character
3196 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
3197 { /* Leave room for the null. */
3198 char str[CHAR_CLASS_MAX_LENGTH + 1];
3203 /* If pattern is `[[:'. */
3204 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3209 if ((c == ':' && *p == ']') || p == pend)
3211 if (c1 < CHAR_CLASS_MAX_LENGTH)
3214 /* This is in any case an invalid class name. */
3219 /* If isn't a word bracketed by `[:' and `:]':
3220 undo the ending character, the letters, and leave
3221 the leading `:' and `[' (but set bits for them). */
3222 if (c == ':' && *p == ']')
3224 # if defined _LIBC || WIDE_CHAR_SUPPORT
3225 boolean is_lower = STREQ (str, "lower");
3226 boolean is_upper = STREQ (str, "upper");
3230 wt = IS_CHAR_CLASS (str);
3232 FREE_STACK_RETURN (REG_ECTYPE);
3234 /* Throw away the ] at the end of the character
3238 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3240 for (ch = 0; ch < 1 << BYTEWIDTH; ++ch)
3242 if (iswctype (btowc (ch), wt))
3245 if (translate && (is_upper || is_lower)
3246 && (ISUPPER (ch) || ISLOWER (ch)))
3250 had_char_class = true;
3253 boolean is_alnum = STREQ (str, "alnum");
3254 boolean is_alpha = STREQ (str, "alpha");
3255 boolean is_blank = STREQ (str, "blank");
3256 boolean is_cntrl = STREQ (str, "cntrl");
3257 boolean is_digit = STREQ (str, "digit");
3258 boolean is_graph = STREQ (str, "graph");
3259 boolean is_lower = STREQ (str, "lower");
3260 boolean is_print = STREQ (str, "print");
3261 boolean is_punct = STREQ (str, "punct");
3262 boolean is_space = STREQ (str, "space");
3263 boolean is_upper = STREQ (str, "upper");
3264 boolean is_xdigit = STREQ (str, "xdigit");
3266 if (!IS_CHAR_CLASS (str))
3267 FREE_STACK_RETURN (REG_ECTYPE);
3269 /* Throw away the ] at the end of the character
3273 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3275 for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
3277 /* This was split into 3 if's to
3278 avoid an arbitrary limit in some compiler. */
3279 if ( (is_alnum && ISALNUM (ch))
3280 || (is_alpha && ISALPHA (ch))
3281 || (is_blank && ISBLANK (ch))
3282 || (is_cntrl && ISCNTRL (ch)))
3284 if ( (is_digit && ISDIGIT (ch))
3285 || (is_graph && ISGRAPH (ch))
3286 || (is_lower && ISLOWER (ch))
3287 || (is_print && ISPRINT (ch)))
3289 if ( (is_punct && ISPUNCT (ch))
3290 || (is_space && ISSPACE (ch))
3291 || (is_upper && ISUPPER (ch))
3292 || (is_xdigit && ISXDIGIT (ch)))
3294 if ( translate && (is_upper || is_lower)
3295 && (ISUPPER (ch) || ISLOWER (ch)))
3298 had_char_class = true;
3299 # endif /* libc || wctype.h */
3309 had_char_class = false;
3312 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '=')
3314 unsigned char str[MB_LEN_MAX + 1];
3317 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3323 /* If pattern is `[[='. */
3324 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3329 if ((c == '=' && *p == ']') || p == pend)
3331 if (c1 < MB_LEN_MAX)
3334 /* This is in any case an invalid class name. */
3339 if (c == '=' && *p == ']' && str[0] != '\0')
3341 /* If we have no collation data we use the default
3342 collation in which each character is in a class
3343 by itself. It also means that ASCII is the
3344 character set and therefore we cannot have character
3345 with more than one byte in the multibyte
3352 FREE_STACK_RETURN (REG_ECOLLATE);
3354 /* Throw away the ] at the end of the equivalence
3358 /* Set the bit for the character. */
3359 SET_LIST_BIT (str[0]);
3364 /* Try to match the byte sequence in `str' against
3365 those known to the collate implementation.
3366 First find out whether the bytes in `str' are
3367 actually from exactly one character. */
3368 const int32_t *table;
3369 const unsigned char *weights;
3370 const unsigned char *extra;
3371 const int32_t *indirect;
3373 const unsigned char *cp = str;
3376 /* This #include defines a local function! */
3377 # include <locale/weight.h>
3379 table = (const int32_t *)
3380 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3381 weights = (const unsigned char *)
3382 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3383 extra = (const unsigned char *)
3384 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3385 indirect = (const int32_t *)
3386 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3388 idx = findidx (&cp);
3389 if (idx == 0 || cp < str + c1)
3390 /* This is no valid character. */
3391 FREE_STACK_RETURN (REG_ECOLLATE);
3393 /* Throw away the ] at the end of the equivalence
3397 /* Now we have to go throught the whole table
3398 and find all characters which have the same
3401 XXX Note that this is not entirely correct.
3402 we would have to match multibyte sequences
3403 but this is not possible with the current
3405 for (ch = 1; ch < 256; ++ch)
3406 /* XXX This test would have to be changed if we
3407 would allow matching multibyte sequences. */
3410 int32_t idx2 = table[ch];
3411 size_t len = weights[idx2];
3413 /* Test whether the lenghts match. */
3414 if (weights[idx] == len)
3416 /* They do. New compare the bytes of
3421 && (weights[idx + 1 + cnt]
3422 == weights[idx2 + 1 + cnt]))
3426 /* They match. Mark the character as
3433 had_char_class = true;
3443 had_char_class = false;
3446 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '.')
3448 unsigned char str[128]; /* Should be large enough. */
3451 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3457 /* If pattern is `[[.'. */
3458 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3463 if ((c == '.' && *p == ']') || p == pend)
3465 if (c1 < sizeof (str))
3468 /* This is in any case an invalid class name. */
3473 if (c == '.' && *p == ']' && str[0] != '\0')
3475 /* If we have no collation data we use the default
3476 collation in which each character is the name
3477 for its own class which contains only the one
3478 character. It also means that ASCII is the
3479 character set and therefore we cannot have character
3480 with more than one byte in the multibyte
3487 FREE_STACK_RETURN (REG_ECOLLATE);
3489 /* Throw away the ] at the end of the equivalence
3493 /* Set the bit for the character. */
3494 SET_LIST_BIT (str[0]);
3495 range_start = ((const unsigned char *) str)[0];
3500 /* Try to match the byte sequence in `str' against
3501 those known to the collate implementation.
3502 First find out whether the bytes in `str' are
3503 actually from exactly one character. */
3505 const int32_t *symb_table;
3506 const unsigned char *extra;
3513 _NL_CURRENT_WORD (LC_COLLATE,
3514 _NL_COLLATE_SYMB_HASH_SIZEMB);
3515 symb_table = (const int32_t *)
3516 _NL_CURRENT (LC_COLLATE,
3517 _NL_COLLATE_SYMB_TABLEMB);
3518 extra = (const unsigned char *)
3519 _NL_CURRENT (LC_COLLATE,
3520 _NL_COLLATE_SYMB_EXTRAMB);
3522 /* Locate the character in the hashing table. */
3523 hash = elem_hash (str, c1);
3526 elem = hash % table_size;
3527 second = hash % (table_size - 2);
3528 while (symb_table[2 * elem] != 0)
3530 /* First compare the hashing value. */
3531 if (symb_table[2 * elem] == hash
3532 && c1 == extra[symb_table[2 * elem + 1]]
3534 &extra[symb_table[2 * elem + 1]
3538 /* Yep, this is the entry. */
3539 idx = symb_table[2 * elem + 1];
3540 idx += 1 + extra[idx];
3548 if (symb_table[2 * elem] == 0)
3549 /* This is no valid character. */
3550 FREE_STACK_RETURN (REG_ECOLLATE);
3552 /* Throw away the ] at the end of the equivalence
3556 /* Now add the multibyte character(s) we found
3559 XXX Note that this is not entirely correct.
3560 we would have to match multibyte sequences
3561 but this is not possible with the current
3562 implementation. Also, we have to match
3563 collating symbols, which expand to more than
3564 one file, as a whole and not allow the
3565 individual bytes. */
3568 range_start = extra[idx];
3571 SET_LIST_BIT (extra[idx]);
3576 had_char_class = false;
3586 had_char_class = false;
3591 had_char_class = false;
3597 /* Discard any (non)matching list bytes that are all 0 at the
3598 end of the map. Decrease the map-length byte too. */
3599 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
3608 if (syntax & RE_NO_BK_PARENS)
3615 if (syntax & RE_NO_BK_PARENS)
3622 if (syntax & RE_NEWLINE_ALT)
3629 if (syntax & RE_NO_BK_VBAR)
3636 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
3637 goto handle_interval;
3643 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3645 /* Do not translate the character after the \, so that we can
3646 distinguish, e.g., \B from \b, even if we normally would
3647 translate, e.g., B to b. */
3653 if (syntax & RE_NO_BK_PARENS)
3654 goto normal_backslash;
3660 if (COMPILE_STACK_FULL)
3662 RETALLOC (compile_stack.stack, compile_stack.size << 1,
3663 compile_stack_elt_t);
3664 if (compile_stack.stack == NULL) return REG_ESPACE;
3666 compile_stack.size <<= 1;
3669 /* These are the values to restore when we hit end of this
3670 group. They are all relative offsets, so that if the
3671 whole pattern moves because of realloc, they will still
3673 COMPILE_STACK_TOP.begalt_offset = begalt - COMPILED_BUFFER_VAR;
3674 COMPILE_STACK_TOP.fixup_alt_jump
3675 = fixup_alt_jump ? fixup_alt_jump - COMPILED_BUFFER_VAR + 1 : 0;
3676 COMPILE_STACK_TOP.laststart_offset = b - COMPILED_BUFFER_VAR;
3677 COMPILE_STACK_TOP.regnum = regnum;
3679 /* We will eventually replace the 0 with the number of
3680 groups inner to this one. But do not push a
3681 start_memory for groups beyond the last one we can
3682 represent in the compiled pattern. */
3683 if (regnum <= MAX_REGNUM)
3685 COMPILE_STACK_TOP.inner_group_offset = b
3686 - COMPILED_BUFFER_VAR + 2;
3687 BUF_PUSH_3 (start_memory, regnum, 0);
3690 compile_stack.avail++;
3695 /* If we've reached MAX_REGNUM groups, then this open
3696 won't actually generate any code, so we'll have to
3697 clear pending_exact explicitly. */
3703 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
3705 if (COMPILE_STACK_EMPTY)
3707 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3708 goto normal_backslash;
3710 FREE_STACK_RETURN (REG_ERPAREN);
3715 { /* Push a dummy failure point at the end of the
3716 alternative for a possible future
3717 `pop_failure_jump' to pop. See comments at
3718 `push_dummy_failure' in `re_match_2'. */
3719 BUF_PUSH (push_dummy_failure);
3721 /* We allocated space for this jump when we assigned
3722 to `fixup_alt_jump', in the `handle_alt' case below. */
3723 STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
3726 /* See similar code for backslashed left paren above. */
3727 if (COMPILE_STACK_EMPTY)
3729 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3732 FREE_STACK_RETURN (REG_ERPAREN);
3735 /* Since we just checked for an empty stack above, this
3736 ``can't happen''. */
3737 assert (compile_stack.avail != 0);
3739 /* We don't just want to restore into `regnum', because
3740 later groups should continue to be numbered higher,
3741 as in `(ab)c(de)' -- the second group is #2. */
3742 regnum_t this_group_regnum;
3744 compile_stack.avail--;
3745 begalt = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.begalt_offset;
3747 = COMPILE_STACK_TOP.fixup_alt_jump
3748 ? COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.fixup_alt_jump - 1
3750 laststart = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.laststart_offset;
3751 this_group_regnum = COMPILE_STACK_TOP.regnum;
3752 /* If we've reached MAX_REGNUM groups, then this open
3753 won't actually generate any code, so we'll have to
3754 clear pending_exact explicitly. */
3757 /* We're at the end of the group, so now we know how many
3758 groups were inside this one. */
3759 if (this_group_regnum <= MAX_REGNUM)
3761 UCHAR_T *inner_group_loc
3762 = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.inner_group_offset;
3764 *inner_group_loc = regnum - this_group_regnum;
3765 BUF_PUSH_3 (stop_memory, this_group_regnum,
3766 regnum - this_group_regnum);
3772 case '|': /* `\|'. */
3773 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
3774 goto normal_backslash;
3776 if (syntax & RE_LIMITED_OPS)
3779 /* Insert before the previous alternative a jump which
3780 jumps to this alternative if the former fails. */
3781 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3782 INSERT_JUMP (on_failure_jump, begalt,
3783 b + 2 + 2 * OFFSET_ADDRESS_SIZE);
3785 b += 1 + OFFSET_ADDRESS_SIZE;
3787 /* The alternative before this one has a jump after it
3788 which gets executed if it gets matched. Adjust that
3789 jump so it will jump to this alternative's analogous
3790 jump (put in below, which in turn will jump to the next
3791 (if any) alternative's such jump, etc.). The last such
3792 jump jumps to the correct final destination. A picture:
3798 If we are at `b', then fixup_alt_jump right now points to a
3799 three-byte space after `a'. We'll put in the jump, set
3800 fixup_alt_jump to right after `b', and leave behind three
3801 bytes which we'll fill in when we get to after `c'. */
3804 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
3806 /* Mark and leave space for a jump after this alternative,
3807 to be filled in later either by next alternative or
3808 when know we're at the end of a series of alternatives. */
3810 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3811 b += 1 + OFFSET_ADDRESS_SIZE;
3819 /* If \{ is a literal. */
3820 if (!(syntax & RE_INTERVALS)
3821 /* If we're at `\{' and it's not the open-interval
3823 || (syntax & RE_NO_BK_BRACES))
3824 goto normal_backslash;
3828 /* If got here, then the syntax allows intervals. */
3830 /* At least (most) this many matches must be made. */
3831 int lower_bound = -1, upper_bound = -1;
3833 /* Place in the uncompiled pattern (i.e., just after
3834 the '{') to go back to if the interval is invalid. */
3835 const CHAR_T *beg_interval = p;
3838 goto invalid_interval;
3840 GET_UNSIGNED_NUMBER (lower_bound);
3844 GET_UNSIGNED_NUMBER (upper_bound);
3845 if (upper_bound < 0)
3846 upper_bound = RE_DUP_MAX;
3849 /* Interval such as `{1}' => match exactly once. */
3850 upper_bound = lower_bound;
3852 if (! (0 <= lower_bound && lower_bound <= upper_bound))
3853 goto invalid_interval;
3855 if (!(syntax & RE_NO_BK_BRACES))
3857 if (c != '\\' || p == pend)
3858 goto invalid_interval;
3863 goto invalid_interval;
3865 /* If it's invalid to have no preceding re. */
3868 if (syntax & RE_CONTEXT_INVALID_OPS
3869 && !(syntax & RE_INVALID_INTERVAL_ORD))
3870 FREE_STACK_RETURN (REG_BADRPT);
3871 else if (syntax & RE_CONTEXT_INDEP_OPS)
3874 goto unfetch_interval;
3877 /* We just parsed a valid interval. */
3879 if (RE_DUP_MAX < upper_bound)
3880 FREE_STACK_RETURN (REG_BADBR);
3882 /* If the upper bound is zero, don't want to succeed at
3883 all; jump from `laststart' to `b + 3', which will be
3884 the end of the buffer after we insert the jump. */
3885 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE'
3886 instead of 'b + 3'. */
3887 if (upper_bound == 0)
3889 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3890 INSERT_JUMP (jump, laststart, b + 1
3891 + OFFSET_ADDRESS_SIZE);
3892 b += 1 + OFFSET_ADDRESS_SIZE;
3895 /* Otherwise, we have a nontrivial interval. When
3896 we're all done, the pattern will look like:
3897 set_number_at <jump count> <upper bound>
3898 set_number_at <succeed_n count> <lower bound>
3899 succeed_n <after jump addr> <succeed_n count>
3901 jump_n <succeed_n addr> <jump count>
3902 (The upper bound and `jump_n' are omitted if
3903 `upper_bound' is 1, though.) */
3905 { /* If the upper bound is > 1, we need to insert
3906 more at the end of the loop. */
3907 unsigned nbytes = 2 + 4 * OFFSET_ADDRESS_SIZE +
3908 (upper_bound > 1) * (2 + 4 * OFFSET_ADDRESS_SIZE);
3910 GET_BUFFER_SPACE (nbytes);
3912 /* Initialize lower bound of the `succeed_n', even
3913 though it will be set during matching by its
3914 attendant `set_number_at' (inserted next),
3915 because `re_compile_fastmap' needs to know.
3916 Jump to the `jump_n' we might insert below. */
3917 INSERT_JUMP2 (succeed_n, laststart,
3918 b + 1 + 2 * OFFSET_ADDRESS_SIZE
3919 + (upper_bound > 1) * (1 + 2 * OFFSET_ADDRESS_SIZE)
3921 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3923 /* Code to initialize the lower bound. Insert
3924 before the `succeed_n'. The `5' is the last two
3925 bytes of this `set_number_at', plus 3 bytes of
3926 the following `succeed_n'. */
3927 /* ifdef WCHAR, The '1+2*OFFSET_ADDRESS_SIZE'
3928 is the 'set_number_at', plus '1+OFFSET_ADDRESS_SIZE'
3929 of the following `succeed_n'. */
3930 PREFIX(insert_op2) (set_number_at, laststart, 1
3931 + 2 * OFFSET_ADDRESS_SIZE, lower_bound, b);
3932 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3934 if (upper_bound > 1)
3935 { /* More than one repetition is allowed, so
3936 append a backward jump to the `succeed_n'
3937 that starts this interval.
3939 When we've reached this during matching,
3940 we'll have matched the interval once, so
3941 jump back only `upper_bound - 1' times. */
3942 STORE_JUMP2 (jump_n, b, laststart
3943 + 2 * OFFSET_ADDRESS_SIZE + 1,
3945 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3947 /* The location we want to set is the second
3948 parameter of the `jump_n'; that is `b-2' as
3949 an absolute address. `laststart' will be
3950 the `set_number_at' we're about to insert;
3951 `laststart+3' the number to set, the source
3952 for the relative address. But we are
3953 inserting into the middle of the pattern --
3954 so everything is getting moved up by 5.
3955 Conclusion: (b - 2) - (laststart + 3) + 5,
3956 i.e., b - laststart.
3958 We insert this at the beginning of the loop
3959 so that if we fail during matching, we'll
3960 reinitialize the bounds. */
3961 PREFIX(insert_op2) (set_number_at, laststart,
3963 upper_bound - 1, b);
3964 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
3971 if (!(syntax & RE_INVALID_INTERVAL_ORD))
3972 FREE_STACK_RETURN (p == pend ? REG_EBRACE : REG_BADBR);
3974 /* Match the characters as literals. */
3977 if (syntax & RE_NO_BK_BRACES)
3980 goto normal_backslash;
3984 /* There is no way to specify the before_dot and after_dot
3985 operators. rms says this is ok. --karl */
3993 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
3999 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
4005 if (syntax & RE_NO_GNU_OPS)
4008 BUF_PUSH (wordchar);
4013 if (syntax & RE_NO_GNU_OPS)
4016 BUF_PUSH (notwordchar);
4021 if (syntax & RE_NO_GNU_OPS)
4027 if (syntax & RE_NO_GNU_OPS)
4033 if (syntax & RE_NO_GNU_OPS)
4035 BUF_PUSH (wordbound);
4039 if (syntax & RE_NO_GNU_OPS)
4041 BUF_PUSH (notwordbound);
4045 if (syntax & RE_NO_GNU_OPS)
4051 if (syntax & RE_NO_GNU_OPS)
4056 case '1': case '2': case '3': case '4': case '5':
4057 case '6': case '7': case '8': case '9':
4058 if (syntax & RE_NO_BK_REFS)
4064 FREE_STACK_RETURN (REG_ESUBREG);
4066 /* Can't back reference to a subexpression if inside of it. */
4067 if (group_in_compile_stack (compile_stack, (regnum_t) c1))
4071 BUF_PUSH_2 (duplicate, c1);
4077 if (syntax & RE_BK_PLUS_QM)
4080 goto normal_backslash;
4084 /* You might think it would be useful for \ to mean
4085 not to translate; but if we don't translate it
4086 it will never match anything. */
4094 /* Expects the character in `c'. */
4096 /* If no exactn currently being built. */
4099 /* If last exactn handle binary(or character) and
4100 new exactn handle character(or binary). */
4101 || is_exactn_bin != is_binary[p - 1 - pattern]
4104 /* If last exactn not at current position. */
4105 || pending_exact + *pending_exact + 1 != b
4107 /* We have only one byte following the exactn for the count. */
4108 || *pending_exact == (1 << BYTEWIDTH) - 1
4110 /* If followed by a repetition operator. */
4111 || *p == '*' || *p == '^'
4112 || ((syntax & RE_BK_PLUS_QM)
4113 ? *p == '\\' && (p[1] == '+' || p[1] == '?')
4114 : (*p == '+' || *p == '?'))
4115 || ((syntax & RE_INTERVALS)
4116 && ((syntax & RE_NO_BK_BRACES)
4118 : (p[0] == '\\' && p[1] == '{'))))
4120 /* Start building a new exactn. */
4125 /* Is this exactn binary data or character? */
4126 is_exactn_bin = is_binary[p - 1 - pattern];
4128 BUF_PUSH_2 (exactn_bin, 0);
4130 BUF_PUSH_2 (exactn, 0);
4132 BUF_PUSH_2 (exactn, 0);
4134 pending_exact = b - 1;
4141 } /* while p != pend */
4144 /* Through the pattern now. */
4147 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
4149 if (!COMPILE_STACK_EMPTY)
4150 FREE_STACK_RETURN (REG_EPAREN);
4152 /* If we don't want backtracking, force success
4153 the first time we reach the end of the compiled pattern. */
4154 if (syntax & RE_NO_POSIX_BACKTRACKING)
4162 free (compile_stack.stack);
4164 /* We have succeeded; set the length of the buffer. */
4166 bufp->used = (uintptr_t) b - (uintptr_t) COMPILED_BUFFER_VAR;
4168 bufp->used = b - bufp->buffer;
4174 DEBUG_PRINT1 ("\nCompiled pattern: \n");
4175 PREFIX(print_compiled_pattern) (bufp);
4179 #ifndef MATCH_MAY_ALLOCATE
4180 /* Initialize the failure stack to the largest possible stack. This
4181 isn't necessary unless we're trying to avoid calling alloca in
4182 the search and match routines. */
4184 int num_regs = bufp->re_nsub + 1;
4186 /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
4187 is strictly greater than re_max_failures, the largest possible stack
4188 is 2 * re_max_failures failure points. */
4189 if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
4191 fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
4194 if (! fail_stack.stack)
4196 = (PREFIX(fail_stack_elt_t) *) xmalloc (fail_stack.size
4197 * sizeof (PREFIX(fail_stack_elt_t)));
4200 = (PREFIX(fail_stack_elt_t) *) xrealloc (fail_stack.stack,
4202 * sizeof (PREFIX(fail_stack_elt_t))));
4203 # else /* not emacs */
4204 if (! fail_stack.stack)
4206 = malloc (fail_stack.size * sizeof (PREFIX(fail_stack_elt_t)));
4209 = realloc (fail_stack.stack,
4210 fail_stack.size * sizeof (PREFIX(fail_stack_elt_t)));
4211 # endif /* not emacs */
4214 PREFIX(regex_grow_registers) (num_regs);
4216 #endif /* not MATCH_MAY_ALLOCATE */
4219 } /* regex_compile */
4221 /* Subroutines for `regex_compile'. */
4223 /* Store OP at LOC followed by two-byte integer parameter ARG. */
4224 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4227 PREFIX(store_op1) (re_opcode_t op, UCHAR_T *loc, int arg)
4229 *loc = (UCHAR_T) op;
4230 STORE_NUMBER (loc + 1, arg);
4234 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
4235 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4238 PREFIX(store_op2) (re_opcode_t op, UCHAR_T *loc, int arg1, int arg2)
4240 *loc = (UCHAR_T) op;
4241 STORE_NUMBER (loc + 1, arg1);
4242 STORE_NUMBER (loc + 1 + OFFSET_ADDRESS_SIZE, arg2);
4246 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
4247 for OP followed by two-byte integer parameter ARG. */
4248 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4251 PREFIX(insert_op1) (re_opcode_t op, UCHAR_T *loc, int arg, UCHAR_T *end)
4253 register UCHAR_T *pfrom = end;
4254 register UCHAR_T *pto = end + 1 + OFFSET_ADDRESS_SIZE;
4256 while (pfrom != loc)
4259 PREFIX(store_op1) (op, loc, arg);
4263 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
4264 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4267 PREFIX(insert_op2) (re_opcode_t op, UCHAR_T *loc, int arg1, int arg2,
4270 register UCHAR_T *pfrom = end;
4271 register UCHAR_T *pto = end + 1 + 2 * OFFSET_ADDRESS_SIZE;
4273 while (pfrom != loc)
4276 PREFIX(store_op2) (op, loc, arg1, arg2);
4280 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
4281 after an alternative or a begin-subexpression. We assume there is at
4282 least one character before the ^. */
4285 PREFIX(at_begline_loc_p) (const CHAR_T *pattern, const CHAR_T *p,
4286 reg_syntax_t syntax)
4288 const CHAR_T *prev = p - 2;
4289 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
4292 /* After a subexpression? */
4293 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
4294 /* After an alternative? */
4295 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
4299 /* The dual of at_begline_loc_p. This one is for $. We assume there is
4300 at least one character after the $, i.e., `P < PEND'. */
4303 PREFIX(at_endline_loc_p) (const CHAR_T *p, const CHAR_T *pend,
4304 reg_syntax_t syntax)
4306 const CHAR_T *next = p;
4307 boolean next_backslash = *next == '\\';
4308 const CHAR_T *next_next = p + 1 < pend ? p + 1 : 0;
4311 /* Before a subexpression? */
4312 (syntax & RE_NO_BK_PARENS ? *next == ')'
4313 : next_backslash && next_next && *next_next == ')')
4314 /* Before an alternative? */
4315 || (syntax & RE_NO_BK_VBAR ? *next == '|'
4316 : next_backslash && next_next && *next_next == '|');
4319 #else /* not INSIDE_RECURSION */
4321 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
4322 false if it's not. */
4325 group_in_compile_stack (compile_stack_type compile_stack,
4330 for (this_element = compile_stack.avail - 1;
4333 if (compile_stack.stack[this_element].regnum == regnum)
4338 #endif /* not INSIDE_RECURSION */
4340 #ifdef INSIDE_RECURSION
4343 /* This insert space, which size is "num", into the pattern at "loc".
4344 "end" must point the end of the allocated buffer. */
4346 insert_space (int num, CHAR_T *loc, CHAR_T *end)
4348 register CHAR_T *pto = end;
4349 register CHAR_T *pfrom = end - num;
4351 while (pfrom >= loc)
4357 static reg_errcode_t
4358 wcs_compile_range (CHAR_T range_start_char,
4359 const CHAR_T **p_ptr, const CHAR_T *pend,
4360 RE_TRANSLATE_TYPE translate, reg_syntax_t syntax,
4361 CHAR_T *b, CHAR_T *char_set)
4363 const CHAR_T *p = *p_ptr;
4364 CHAR_T range_start, range_end;
4368 uint32_t start_val, end_val;
4374 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4377 const char *collseq = (const char *) _NL_CURRENT(LC_COLLATE,
4378 _NL_COLLATE_COLLSEQWC);
4379 const unsigned char *extra = (const unsigned char *)
4380 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4382 if (range_start_char < -1)
4384 /* range_start is a collating symbol. */
4386 /* Retreive the index and get collation sequence value. */
4387 wextra = (int32_t*)(extra + char_set[-range_start_char]);
4388 start_val = wextra[1 + *wextra];
4391 start_val = collseq_table_lookup(collseq, TRANSLATE(range_start_char));
4393 end_val = collseq_table_lookup (collseq, TRANSLATE (p[0]));
4395 /* Report an error if the range is empty and the syntax prohibits
4397 ret = ((syntax & RE_NO_EMPTY_RANGES)
4398 && (start_val > end_val))? REG_ERANGE : REG_NOERROR;
4400 /* Insert space to the end of the char_ranges. */
4401 insert_space(2, b - char_set[5] - 2, b - 1);
4402 *(b - char_set[5] - 2) = (wchar_t)start_val;
4403 *(b - char_set[5] - 1) = (wchar_t)end_val;
4404 char_set[4]++; /* ranges_index */
4409 range_start = (range_start_char >= 0)? TRANSLATE (range_start_char):
4411 range_end = TRANSLATE (p[0]);
4412 /* Report an error if the range is empty and the syntax prohibits
4414 ret = ((syntax & RE_NO_EMPTY_RANGES)
4415 && (range_start > range_end))? REG_ERANGE : REG_NOERROR;
4417 /* Insert space to the end of the char_ranges. */
4418 insert_space(2, b - char_set[5] - 2, b - 1);
4419 *(b - char_set[5] - 2) = range_start;
4420 *(b - char_set[5] - 1) = range_end;
4421 char_set[4]++; /* ranges_index */
4423 /* Have to increment the pointer into the pattern string, so the
4424 caller isn't still at the ending character. */
4430 /* Read the ending character of a range (in a bracket expression) from the
4431 uncompiled pattern *P_PTR (which ends at PEND). We assume the
4432 starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
4433 Then we set the translation of all bits between the starting and
4434 ending characters (inclusive) in the compiled pattern B.
4436 Return an error code.
4438 We use these short variable names so we can use the same macros as
4439 `regex_compile' itself. */
4441 static reg_errcode_t
4442 byte_compile_range (unsigned int range_start_char,
4443 const char **p_ptr, const char *pend,
4444 RE_TRANSLATE_TYPE translate, reg_syntax_t syntax,
4448 const char *p = *p_ptr;
4451 const unsigned char *collseq;
4452 unsigned int start_colseq;
4453 unsigned int end_colseq;
4461 /* Have to increment the pointer into the pattern string, so the
4462 caller isn't still at the ending character. */
4465 /* Report an error if the range is empty and the syntax prohibits this. */
4466 ret = syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
4469 collseq = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
4470 _NL_COLLATE_COLLSEQMB);
4472 start_colseq = collseq[(unsigned char) TRANSLATE (range_start_char)];
4473 end_colseq = collseq[(unsigned char) TRANSLATE (p[0])];
4474 for (this_char = 0; this_char <= (unsigned char) -1; ++this_char)
4476 unsigned int this_colseq = collseq[(unsigned char) TRANSLATE (this_char)];
4478 if (start_colseq <= this_colseq && this_colseq <= end_colseq)
4480 SET_LIST_BIT (TRANSLATE (this_char));
4485 /* Here we see why `this_char' has to be larger than an `unsigned
4486 char' -- we would otherwise go into an infinite loop, since all
4487 characters <= 0xff. */
4488 range_start_char = TRANSLATE (range_start_char);
4489 /* TRANSLATE(p[0]) is casted to char (not unsigned char) in TRANSLATE,
4490 and some compilers cast it to int implicitly, so following for_loop
4491 may fall to (almost) infinite loop.
4492 e.g. If translate[p[0]] = 0xff, end_char may equals to 0xffffffff.
4493 To avoid this, we cast p[0] to unsigned int and truncate it. */
4494 end_char = ((unsigned)TRANSLATE(p[0]) & ((1 << BYTEWIDTH) - 1));
4496 for (this_char = range_start_char; this_char <= end_char; ++this_char)
4498 SET_LIST_BIT (TRANSLATE (this_char));
4507 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4508 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4509 characters can start a string that matches the pattern. This fastmap
4510 is used by re_search to skip quickly over impossible starting points.
4512 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4513 area as BUFP->fastmap.
4515 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4518 Returns 0 if we succeed, -2 if an internal error. */
4521 /* local function for re_compile_fastmap.
4522 truncate wchar_t character to char. */
4524 static unsigned char
4525 truncate_wchar (CHAR_T c)
4527 unsigned char buf[MB_CUR_MAX];
4530 memset (&state, '\0', sizeof (state));
4531 retval = wcrtomb (buf, c, &state);
4532 return retval > 0 ? buf[0] : (unsigned char) c;
4537 PREFIX(re_compile_fastmap) (struct re_pattern_buffer *bufp)
4540 #ifdef MATCH_MAY_ALLOCATE
4541 PREFIX(fail_stack_type) fail_stack;
4543 #ifndef REGEX_MALLOC
4547 register char *fastmap = bufp->fastmap;
4550 /* We need to cast pattern to (wchar_t*), because we casted this compiled
4551 pattern to (char*) in regex_compile. */
4552 UCHAR_T *pattern = (UCHAR_T*)bufp->buffer;
4553 register UCHAR_T *pend = (UCHAR_T*) (bufp->buffer + bufp->used);
4555 UCHAR_T *pattern = bufp->buffer;
4556 register UCHAR_T *pend = pattern + bufp->used;
4558 UCHAR_T *p = pattern;
4561 /* This holds the pointer to the failure stack, when
4562 it is allocated relocatably. */
4563 fail_stack_elt_t *failure_stack_ptr;
4566 /* Assume that each path through the pattern can be null until
4567 proven otherwise. We set this false at the bottom of switch
4568 statement, to which we get only if a particular path doesn't
4569 match the empty string. */
4570 boolean path_can_be_null = true;
4572 /* We aren't doing a `succeed_n' to begin with. */
4573 boolean succeed_n_p = false;
4575 assert (fastmap != NULL && p != NULL);
4578 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
4579 bufp->fastmap_accurate = 1; /* It will be when we're done. */
4580 bufp->can_be_null = 0;
4584 if (p == pend || *p == succeed)
4586 /* We have reached the (effective) end of pattern. */
4587 if (!FAIL_STACK_EMPTY ())
4589 bufp->can_be_null |= path_can_be_null;
4591 /* Reset for next path. */
4592 path_can_be_null = true;
4594 p = fail_stack.stack[--fail_stack.avail].pointer;
4602 /* We should never be about to go beyond the end of the pattern. */
4605 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
4608 /* I guess the idea here is to simply not bother with a fastmap
4609 if a backreference is used, since it's too hard to figure out
4610 the fastmap for the corresponding group. Setting
4611 `can_be_null' stops `re_search_2' from using the fastmap, so
4612 that is all we do. */
4614 bufp->can_be_null = 1;
4618 /* Following are the cases which match a character. These end
4623 fastmap[truncate_wchar(p[1])] = 1;
4637 /* It is hard to distinguish fastmap from (multi byte) characters
4638 which depends on current locale. */
4643 bufp->can_be_null = 1;
4647 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4648 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
4654 /* Chars beyond end of map must be allowed. */
4655 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
4658 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4659 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
4665 for (j = 0; j < (1 << BYTEWIDTH); j++)
4666 if (SYNTAX (j) == Sword)
4672 for (j = 0; j < (1 << BYTEWIDTH); j++)
4673 if (SYNTAX (j) != Sword)
4680 int fastmap_newline = fastmap['\n'];
4682 /* `.' matches anything ... */
4683 for (j = 0; j < (1 << BYTEWIDTH); j++)
4686 /* ... except perhaps newline. */
4687 if (!(bufp->syntax & RE_DOT_NEWLINE))
4688 fastmap['\n'] = fastmap_newline;
4690 /* Return if we have already set `can_be_null'; if we have,
4691 then the fastmap is irrelevant. Something's wrong here. */
4692 else if (bufp->can_be_null)
4695 /* Otherwise, have to check alternative paths. */
4702 for (j = 0; j < (1 << BYTEWIDTH); j++)
4703 if (SYNTAX (j) == (enum syntaxcode) k)
4710 for (j = 0; j < (1 << BYTEWIDTH); j++)
4711 if (SYNTAX (j) != (enum syntaxcode) k)
4716 /* All cases after this match the empty string. These end with
4736 case push_dummy_failure:
4741 case pop_failure_jump:
4742 case maybe_pop_jump:
4745 case dummy_failure_jump:
4746 EXTRACT_NUMBER_AND_INCR (j, p);
4751 /* Jump backward implies we just went through the body of a
4752 loop and matched nothing. Opcode jumped to should be
4753 `on_failure_jump' or `succeed_n'. Just treat it like an
4754 ordinary jump. For a * loop, it has pushed its failure
4755 point already; if so, discard that as redundant. */
4756 if ((re_opcode_t) *p != on_failure_jump
4757 && (re_opcode_t) *p != succeed_n)
4761 EXTRACT_NUMBER_AND_INCR (j, p);
4764 /* If what's on the stack is where we are now, pop it. */
4765 if (!FAIL_STACK_EMPTY ()
4766 && fail_stack.stack[fail_stack.avail - 1].pointer == p)
4772 case on_failure_jump:
4773 case on_failure_keep_string_jump:
4774 handle_on_failure_jump:
4775 EXTRACT_NUMBER_AND_INCR (j, p);
4777 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
4778 end of the pattern. We don't want to push such a point,
4779 since when we restore it above, entering the switch will
4780 increment `p' past the end of the pattern. We don't need
4781 to push such a point since we obviously won't find any more
4782 fastmap entries beyond `pend'. Such a pattern can match
4783 the null string, though. */
4786 if (!PUSH_PATTERN_OP (p + j, fail_stack))
4788 RESET_FAIL_STACK ();
4793 bufp->can_be_null = 1;
4797 EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */
4798 succeed_n_p = false;
4805 /* Get to the number of times to succeed. */
4806 p += OFFSET_ADDRESS_SIZE;
4808 /* Increment p past the n for when k != 0. */
4809 EXTRACT_NUMBER_AND_INCR (k, p);
4812 p -= 2 * OFFSET_ADDRESS_SIZE;
4813 succeed_n_p = true; /* Spaghetti code alert. */
4814 goto handle_on_failure_jump;
4820 p += 2 * OFFSET_ADDRESS_SIZE;
4831 abort (); /* We have listed all the cases. */
4834 /* Getting here means we have found the possible starting
4835 characters for one path of the pattern -- and that the empty
4836 string does not match. We need not follow this path further.
4837 Instead, look at the next alternative (remembered on the
4838 stack), or quit if no more. The test at the top of the loop
4839 does these things. */
4840 path_can_be_null = false;
4844 /* Set `can_be_null' for the last path (also the first path, if the
4845 pattern is empty). */
4846 bufp->can_be_null |= path_can_be_null;
4849 RESET_FAIL_STACK ();
4853 #else /* not INSIDE_RECURSION */
4856 re_compile_fastmap (struct re_pattern_buffer *bufp)
4859 if (MB_CUR_MAX != 1)
4860 return wcs_re_compile_fastmap(bufp);
4863 return byte_re_compile_fastmap(bufp);
4864 } /* re_compile_fastmap */
4866 weak_alias (__re_compile_fastmap, re_compile_fastmap)
4870 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
4871 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
4872 this memory for recording register information. STARTS and ENDS
4873 must be allocated using the malloc library routine, and must each
4874 be at least NUM_REGS * sizeof (regoff_t) bytes long.
4876 If NUM_REGS == 0, then subsequent matches should allocate their own
4879 Unless this function is called, the first search or match using
4880 PATTERN_BUFFER will allocate its own register data, without
4881 freeing the old data. */
4884 re_set_registers (struct re_pattern_buffer *bufp,
4885 struct re_registers *regs,
4886 unsigned int num_regs,
4887 regoff_t *starts, regoff_t *ends)
4891 bufp->regs_allocated = REGS_REALLOCATE;
4892 regs->num_regs = num_regs;
4893 regs->start = starts;
4898 bufp->regs_allocated = REGS_UNALLOCATED;
4900 regs->start = regs->end = (regoff_t *) 0;
4904 weak_alias (__re_set_registers, re_set_registers)
4907 /* Searching routines. */
4909 /* Like re_search_2, below, but only one string is specified, and
4910 doesn't let you say where to stop matching. */
4913 re_search (struct re_pattern_buffer *bufp,
4915 int size, int startpos, int range,
4916 struct re_registers *regs)
4918 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
4922 weak_alias (__re_search, re_search)
4926 /* Using the compiled pattern in BUFP->buffer, first tries to match the
4927 virtual concatenation of STRING1 and STRING2, starting first at index
4928 STARTPOS, then at STARTPOS + 1, and so on.
4930 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
4932 RANGE is how far to scan while trying to match. RANGE = 0 means try
4933 only at STARTPOS; in general, the last start tried is STARTPOS +
4936 In REGS, return the indices of the virtual concatenation of STRING1
4937 and STRING2 that matched the entire BUFP->buffer and its contained
4940 Do not consider matching one past the index STOP in the virtual
4941 concatenation of STRING1 and STRING2.
4943 We return either the position in the strings at which the match was
4944 found, -1 if no match, or -2 if error (such as failure
4948 re_search_2 (struct re_pattern_buffer *bufp,
4949 const char *string1, int size1,
4950 const char *string2, int size2,
4951 int startpos, int range,
4952 struct re_registers *regs,
4956 if (MB_CUR_MAX != 1)
4957 return wcs_re_search_2 (bufp, string1, size1, string2, size2, startpos,
4961 return byte_re_search_2 (bufp, string1, size1, string2, size2, startpos,
4965 weak_alias (__re_search_2, re_search_2)
4968 #endif /* not INSIDE_RECURSION */
4970 #ifdef INSIDE_RECURSION
4972 #ifdef MATCH_MAY_ALLOCATE
4973 # define FREE_VAR(var) if (var) REGEX_FREE (var); var = NULL
4975 # define FREE_VAR(var) if (var) free (var); var = NULL
4979 # define MAX_ALLOCA_SIZE 2000
4981 # define FREE_WCS_BUFFERS() \
4983 if (size1 > MAX_ALLOCA_SIZE) \
4985 free (wcs_string1); \
4986 free (mbs_offset1); \
4990 FREE_VAR (wcs_string1); \
4991 FREE_VAR (mbs_offset1); \
4993 if (size2 > MAX_ALLOCA_SIZE) \
4995 free (wcs_string2); \
4996 free (mbs_offset2); \
5000 FREE_VAR (wcs_string2); \
5001 FREE_VAR (mbs_offset2); \
5009 PREFIX(re_search_2) (struct re_pattern_buffer *bufp,
5010 const char *string1, int size1,
5011 const char *string2, int size2,
5012 int startpos, int range,
5013 struct re_registers *regs,
5017 register char *fastmap = bufp->fastmap;
5018 register RE_TRANSLATE_TYPE translate = bufp->translate;
5019 int total_size = size1 + size2;
5020 int endpos = startpos + range;
5022 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5023 wchar_t *wcs_string1 = NULL, *wcs_string2 = NULL;
5024 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5025 int wcs_size1 = 0, wcs_size2 = 0;
5026 /* offset buffer for optimizatoin. See convert_mbs_to_wc. */
5027 int *mbs_offset1 = NULL, *mbs_offset2 = NULL;
5028 /* They hold whether each wchar_t is binary data or not. */
5029 char *is_binary = NULL;
5032 /* Check for out-of-range STARTPOS. */
5033 if (startpos < 0 || startpos > total_size)
5036 /* Fix up RANGE if it might eventually take us outside
5037 the virtual concatenation of STRING1 and STRING2.
5038 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
5040 range = 0 - startpos;
5041 else if (endpos > total_size)
5042 range = total_size - startpos;
5044 /* If the search isn't to be a backwards one, don't waste time in a
5045 search for a pattern that must be anchored. */
5046 if (bufp->used > 0 && range > 0
5047 && ((re_opcode_t) bufp->buffer[0] == begbuf
5048 /* `begline' is like `begbuf' if it cannot match at newlines. */
5049 || ((re_opcode_t) bufp->buffer[0] == begline
5050 && !bufp->newline_anchor)))
5059 /* In a forward search for something that starts with \=.
5060 don't keep searching past point. */
5061 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
5063 range = PT - startpos;
5069 /* Update the fastmap now if not correct already. */
5070 if (fastmap && !bufp->fastmap_accurate)
5071 if (re_compile_fastmap (bufp) == -2)
5075 /* Allocate wchar_t array for wcs_string1 and wcs_string2 and
5076 fill them with converted string. */
5079 if (size1 > MAX_ALLOCA_SIZE)
5081 wcs_string1 = TALLOC (size1 + 1, CHAR_T);
5082 mbs_offset1 = TALLOC (size1 + 1, int);
5083 is_binary = TALLOC (size1 + 1, char);
5087 wcs_string1 = REGEX_TALLOC (size1 + 1, CHAR_T);
5088 mbs_offset1 = REGEX_TALLOC (size1 + 1, int);
5089 is_binary = REGEX_TALLOC (size1 + 1, char);
5091 if (!wcs_string1 || !mbs_offset1 || !is_binary)
5093 if (size1 > MAX_ALLOCA_SIZE)
5101 FREE_VAR (wcs_string1);
5102 FREE_VAR (mbs_offset1);
5103 FREE_VAR (is_binary);
5107 wcs_size1 = convert_mbs_to_wcs(wcs_string1, string1, size1,
5108 mbs_offset1, is_binary);
5109 wcs_string1[wcs_size1] = L'\0'; /* for a sentinel */
5110 if (size1 > MAX_ALLOCA_SIZE)
5113 FREE_VAR (is_binary);
5117 if (size2 > MAX_ALLOCA_SIZE)
5119 wcs_string2 = TALLOC (size2 + 1, CHAR_T);
5120 mbs_offset2 = TALLOC (size2 + 1, int);
5121 is_binary = TALLOC (size2 + 1, char);
5125 wcs_string2 = REGEX_TALLOC (size2 + 1, CHAR_T);
5126 mbs_offset2 = REGEX_TALLOC (size2 + 1, int);
5127 is_binary = REGEX_TALLOC (size2 + 1, char);
5129 if (!wcs_string2 || !mbs_offset2 || !is_binary)
5131 FREE_WCS_BUFFERS ();
5132 if (size2 > MAX_ALLOCA_SIZE)
5135 FREE_VAR (is_binary);
5138 wcs_size2 = convert_mbs_to_wcs(wcs_string2, string2, size2,
5139 mbs_offset2, is_binary);
5140 wcs_string2[wcs_size2] = L'\0'; /* for a sentinel */
5141 if (size2 > MAX_ALLOCA_SIZE)
5144 FREE_VAR (is_binary);
5149 /* Loop through the string, looking for a place to start matching. */
5152 /* If a fastmap is supplied, skip quickly over characters that
5153 cannot be the start of a match. If the pattern can match the
5154 null string, however, we don't need to skip characters; we want
5155 the first null string. */
5156 if (fastmap && startpos < total_size && !bufp->can_be_null)
5158 if (range > 0) /* Searching forwards. */
5160 register const char *d;
5161 register int lim = 0;
5164 if (startpos < size1 && startpos + range >= size1)
5165 lim = range - (size1 - startpos);
5167 d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
5169 /* Written out as an if-else to avoid testing `translate'
5173 && !fastmap[(unsigned char)
5174 translate[(unsigned char) *d++]])
5177 while (range > lim && !fastmap[(unsigned char) *d++])
5180 startpos += irange - range;
5182 else /* Searching backwards. */
5184 register CHAR_T c = (size1 == 0 || startpos >= size1
5185 ? string2[startpos - size1]
5186 : string1[startpos]);
5188 if (!fastmap[(unsigned char) TRANSLATE (c)])
5193 /* If can't match the null string, and that's all we have left, fail. */
5194 if (range >= 0 && startpos == total_size && fastmap
5195 && !bufp->can_be_null)
5198 FREE_WCS_BUFFERS ();
5204 val = wcs_re_match_2_internal (bufp, string1, size1, string2,
5205 size2, startpos, regs, stop,
5206 wcs_string1, wcs_size1,
5207 wcs_string2, wcs_size2,
5208 mbs_offset1, mbs_offset2);
5210 val = byte_re_match_2_internal (bufp, string1, size1, string2,
5211 size2, startpos, regs, stop);
5214 #ifndef REGEX_MALLOC
5223 FREE_WCS_BUFFERS ();
5231 FREE_WCS_BUFFERS ();
5251 FREE_WCS_BUFFERS ();
5257 /* This converts PTR, a pointer into one of the search wchar_t strings
5258 `string1' and `string2' into an multibyte string offset from the
5259 beginning of that string. We use mbs_offset to optimize.
5260 See convert_mbs_to_wcs. */
5261 # define POINTER_TO_OFFSET(ptr) \
5262 (FIRST_STRING_P (ptr) \
5263 ? ((regoff_t)(mbs_offset1 != NULL? mbs_offset1[(ptr)-string1] : 0)) \
5264 : ((regoff_t)((mbs_offset2 != NULL? mbs_offset2[(ptr)-string2] : 0) \
5267 /* This converts PTR, a pointer into one of the search strings `string1'
5268 and `string2' into an offset from the beginning of that string. */
5269 # define POINTER_TO_OFFSET(ptr) \
5270 (FIRST_STRING_P (ptr) \
5271 ? ((regoff_t) ((ptr) - string1)) \
5272 : ((regoff_t) ((ptr) - string2 + size1)))
5275 /* Macros for dealing with the split strings in re_match_2. */
5277 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
5279 /* Call before fetching a character with *d. This switches over to
5280 string2 if necessary. */
5281 #define PREFETCH() \
5284 /* End of string2 => fail. */ \
5285 if (dend == end_match_2) \
5287 /* End of string1 => advance to string2. */ \
5289 dend = end_match_2; \
5292 /* Test if at very beginning or at very end of the virtual concatenation
5293 of `string1' and `string2'. If only one string, it's `string2'. */
5294 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
5295 #define AT_STRINGS_END(d) ((d) == end2)
5298 /* Test if D points to a character which is word-constituent. We have
5299 two special cases to check for: if past the end of string1, look at
5300 the first character in string2; and if before the beginning of
5301 string2, look at the last character in string1. */
5303 /* Use internationalized API instead of SYNTAX. */
5304 # define WORDCHAR_P(d) \
5305 (iswalnum ((wint_t)((d) == end1 ? *string2 \
5306 : (d) == string2 - 1 ? *(end1 - 1) : *(d))) != 0 \
5307 || ((d) == end1 ? *string2 \
5308 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) == L'_')
5310 # define WORDCHAR_P(d) \
5311 (SYNTAX ((d) == end1 ? *string2 \
5312 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
5316 /* Disabled due to a compiler bug -- see comment at case wordbound */
5318 /* Test if the character before D and the one at D differ with respect
5319 to being word-constituent. */
5320 #define AT_WORD_BOUNDARY(d) \
5321 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
5322 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
5325 /* Free everything we malloc. */
5326 #ifdef MATCH_MAY_ALLOCATE
5328 # define FREE_VARIABLES() \
5330 REGEX_FREE_STACK (fail_stack.stack); \
5331 FREE_VAR (regstart); \
5332 FREE_VAR (regend); \
5333 FREE_VAR (old_regstart); \
5334 FREE_VAR (old_regend); \
5335 FREE_VAR (best_regstart); \
5336 FREE_VAR (best_regend); \
5337 FREE_VAR (reg_info); \
5338 FREE_VAR (reg_dummy); \
5339 FREE_VAR (reg_info_dummy); \
5340 if (!cant_free_wcs_buf) \
5342 FREE_VAR (string1); \
5343 FREE_VAR (string2); \
5344 FREE_VAR (mbs_offset1); \
5345 FREE_VAR (mbs_offset2); \
5349 # define FREE_VARIABLES() \
5351 REGEX_FREE_STACK (fail_stack.stack); \
5352 FREE_VAR (regstart); \
5353 FREE_VAR (regend); \
5354 FREE_VAR (old_regstart); \
5355 FREE_VAR (old_regend); \
5356 FREE_VAR (best_regstart); \
5357 FREE_VAR (best_regend); \
5358 FREE_VAR (reg_info); \
5359 FREE_VAR (reg_dummy); \
5360 FREE_VAR (reg_info_dummy); \
5365 # define FREE_VARIABLES() \
5367 if (!cant_free_wcs_buf) \
5369 FREE_VAR (string1); \
5370 FREE_VAR (string2); \
5371 FREE_VAR (mbs_offset1); \
5372 FREE_VAR (mbs_offset2); \
5376 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
5378 #endif /* not MATCH_MAY_ALLOCATE */
5380 /* These values must meet several constraints. They must not be valid
5381 register values; since we have a limit of 255 registers (because
5382 we use only one byte in the pattern for the register number), we can
5383 use numbers larger than 255. They must differ by 1, because of
5384 NUM_FAILURE_ITEMS above. And the value for the lowest register must
5385 be larger than the value for the highest register, so we do not try
5386 to actually save any registers when none are active. */
5387 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
5388 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
5390 #else /* not INSIDE_RECURSION */
5391 /* Matching routines. */
5393 #ifndef emacs /* Emacs never uses this. */
5394 /* re_match is like re_match_2 except it takes only a single string. */
5397 re_match (struct re_pattern_buffer *bufp,
5400 struct re_registers *regs)
5404 if (MB_CUR_MAX != 1)
5405 result = wcs_re_match_2_internal (bufp, NULL, 0, string, size,
5407 NULL, 0, NULL, 0, NULL, NULL);
5410 result = byte_re_match_2_internal (bufp, NULL, 0, string, size,
5412 # ifndef REGEX_MALLOC
5420 weak_alias (__re_match, re_match)
5422 #endif /* not emacs */
5424 #endif /* not INSIDE_RECURSION */
5426 #ifdef INSIDE_RECURSION
5427 static boolean PREFIX(group_match_null_string_p) (UCHAR_T **p,
5429 PREFIX(register_info_type) *reg_info);
5430 static boolean PREFIX(alt_match_null_string_p) (UCHAR_T *p,
5432 PREFIX(register_info_type) *reg_info);
5433 static boolean PREFIX(common_op_match_null_string_p) (UCHAR_T **p,
5435 PREFIX(register_info_type) *reg_info);
5436 static int PREFIX(bcmp_translate) (const CHAR_T *s1, const CHAR_T *s2,
5437 int len, char *translate);
5438 #else /* not INSIDE_RECURSION */
5440 /* re_match_2 matches the compiled pattern in BUFP against the
5441 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
5442 and SIZE2, respectively). We start matching at POS, and stop
5445 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
5446 store offsets for the substring each group matched in REGS. See the
5447 documentation for exactly how many groups we fill.
5449 We return -1 if no match, -2 if an internal error (such as the
5450 failure stack overflowing). Otherwise, we return the length of the
5451 matched substring. */
5454 re_match_2 (struct re_pattern_buffer *bufp,
5455 const char *string1, int size1,
5456 const char *string2, int size2,
5457 int pos, struct re_registers *regs,
5462 if (MB_CUR_MAX != 1)
5463 result = wcs_re_match_2_internal (bufp, string1, size1, string2, size2,
5465 NULL, 0, NULL, 0, NULL, NULL);
5468 result = byte_re_match_2_internal (bufp, string1, size1, string2, size2,
5471 #ifndef REGEX_MALLOC
5479 weak_alias (__re_match_2, re_match_2)
5482 #endif /* not INSIDE_RECURSION */
5484 #ifdef INSIDE_RECURSION
5488 /* This check the substring (from 0, to length) of the multibyte string,
5489 to which offset_buffer correspond. And count how many wchar_t_characters
5490 the substring occupy. We use offset_buffer to optimization.
5491 See convert_mbs_to_wcs. */
5494 count_mbs_length (int *offset_buffer, int length)
5498 /* Check whether the size is valid. */
5502 if (offset_buffer == NULL)
5505 /* If there are no multibyte character, offset_buffer[i] == i.
5506 Optmize for this case. */
5507 if (offset_buffer[length] == length)
5510 /* Set up upper with length. (because for all i, offset_buffer[i] >= i) */
5516 int middle = (lower + upper) / 2;
5517 if (middle == lower || middle == upper)
5519 if (offset_buffer[middle] > length)
5521 else if (offset_buffer[middle] < length)
5531 /* This is a separate function so that we can force an alloca cleanup
5535 wcs_re_match_2_internal (struct re_pattern_buffer *bufp,
5536 const char *cstring1, int csize1,
5537 const char *cstring2, int csize2,
5539 struct re_registers *regs,
5541 /* string1 == string2 == NULL means
5542 string1/2, size1/2 and mbs_offset1/2 need
5543 setting up in this function. */
5544 /* We need wchar_t * buffers corresponding to
5545 cstring1, cstring2. */
5546 wchar_t *string1, int size1,
5547 wchar_t *string2, int size2,
5548 /* Offset buffer for optimization. See
5549 convert_mbs_to_wc. */
5554 byte_re_match_2_internal (struct re_pattern_buffer *bufp,
5555 const char *string1, int size1,
5556 const char *string2, int size2,
5558 struct re_registers *regs,
5562 /* General temporaries. */
5566 /* They hold whether each wchar_t is binary data or not. */
5567 char *is_binary = NULL;
5568 /* If true, we can't free string1/2, mbs_offset1/2. */
5569 int cant_free_wcs_buf = 1;
5572 /* Just past the end of the corresponding string. */
5573 const CHAR_T *end1, *end2;
5575 /* Pointers into string1 and string2, just past the last characters in
5576 each to consider matching. */
5577 const CHAR_T *end_match_1, *end_match_2;
5579 /* Where we are in the data, and the end of the current string. */
5580 const CHAR_T *d, *dend;
5582 /* Where we are in the pattern, and the end of the pattern. */
5584 UCHAR_T *pattern, *p;
5585 register UCHAR_T *pend;
5587 UCHAR_T *p = bufp->buffer;
5588 register UCHAR_T *pend = p + bufp->used;
5591 /* Mark the opcode just after a start_memory, so we can test for an
5592 empty subpattern when we get to the stop_memory. */
5593 UCHAR_T *just_past_start_mem = 0;
5595 /* We use this to map every character in the string. */
5596 RE_TRANSLATE_TYPE translate = bufp->translate;
5598 /* Failure point stack. Each place that can handle a failure further
5599 down the line pushes a failure point on this stack. It consists of
5600 restart, regend, and reg_info for all registers corresponding to
5601 the subexpressions we're currently inside, plus the number of such
5602 registers, and, finally, two char *'s. The first char * is where
5603 to resume scanning the pattern; the second one is where to resume
5604 scanning the strings. If the latter is zero, the failure point is
5605 a ``dummy''; if a failure happens and the failure point is a dummy,
5606 it gets discarded and the next next one is tried. */
5607 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5608 PREFIX(fail_stack_type) fail_stack;
5611 static unsigned failure_id;
5612 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
5616 /* This holds the pointer to the failure stack, when
5617 it is allocated relocatably. */
5618 fail_stack_elt_t *failure_stack_ptr;
5621 /* We fill all the registers internally, independent of what we
5622 return, for use in backreferences. The number here includes
5623 an element for register zero. */
5624 size_t num_regs = bufp->re_nsub + 1;
5626 /* The currently active registers. */
5627 active_reg_t lowest_active_reg = NO_LOWEST_ACTIVE_REG;
5628 active_reg_t highest_active_reg = NO_HIGHEST_ACTIVE_REG;
5630 /* Information on the contents of registers. These are pointers into
5631 the input strings; they record just what was matched (on this
5632 attempt) by a subexpression part of the pattern, that is, the
5633 regnum-th regstart pointer points to where in the pattern we began
5634 matching and the regnum-th regend points to right after where we
5635 stopped matching the regnum-th subexpression. (The zeroth register
5636 keeps track of what the whole pattern matches.) */
5637 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5638 const CHAR_T **regstart, **regend;
5641 /* If a group that's operated upon by a repetition operator fails to
5642 match anything, then the register for its start will need to be
5643 restored because it will have been set to wherever in the string we
5644 are when we last see its open-group operator. Similarly for a
5646 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5647 const CHAR_T **old_regstart, **old_regend;
5650 /* The is_active field of reg_info helps us keep track of which (possibly
5651 nested) subexpressions we are currently in. The matched_something
5652 field of reg_info[reg_num] helps us tell whether or not we have
5653 matched any of the pattern so far this time through the reg_num-th
5654 subexpression. These two fields get reset each time through any
5655 loop their register is in. */
5656 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5657 PREFIX(register_info_type) *reg_info;
5660 /* The following record the register info as found in the above
5661 variables when we find a match better than any we've seen before.
5662 This happens as we backtrack through the failure points, which in
5663 turn happens only if we have not yet matched the entire string. */
5664 unsigned best_regs_set = false;
5665 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5666 const CHAR_T **best_regstart, **best_regend;
5669 /* Logically, this is `best_regend[0]'. But we don't want to have to
5670 allocate space for that if we're not allocating space for anything
5671 else (see below). Also, we never need info about register 0 for
5672 any of the other register vectors, and it seems rather a kludge to
5673 treat `best_regend' differently than the rest. So we keep track of
5674 the end of the best match so far in a separate variable. We
5675 initialize this to NULL so that when we backtrack the first time
5676 and need to test it, it's not garbage. */
5677 const CHAR_T *match_end = NULL;
5679 /* This helps SET_REGS_MATCHED avoid doing redundant work. */
5680 int set_regs_matched_done = 0;
5682 /* Used when we pop values we don't care about. */
5683 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5684 const CHAR_T **reg_dummy;
5685 PREFIX(register_info_type) *reg_info_dummy;
5689 /* Counts the total number of registers pushed. */
5690 unsigned num_regs_pushed = 0;
5693 /* Definitions for state transitions. More efficiently for gcc. */
5695 # if defined HAVE_SUBTRACT_LOCAL_LABELS && defined SHARED
5700 const void *__unbounded ptr; \
5701 offset = (p == pend \
5702 ? 0 : jmptable[SWITCH_ENUM_CAST ((re_opcode_t) *p++)]); \
5703 ptr = &&end_of_pattern + offset; \
5708 &&label_##x - &&end_of_pattern
5709 # define JUMP_TABLE_TYPE const int
5714 const void *__unbounded ptr; \
5715 ptr = (p == pend ? &&end_of_pattern \
5716 : jmptable[SWITCH_ENUM_CAST ((re_opcode_t) *p++)]); \
5722 # define JUMP_TABLE_TYPE const void *const
5724 # define CASE(x) label_##x
5725 static JUMP_TABLE_TYPE jmptable[] =
5744 REF (jump_past_alt),
5745 REF (on_failure_jump),
5746 REF (on_failure_keep_string_jump),
5747 REF (pop_failure_jump),
5748 REF (maybe_pop_jump),
5749 REF (dummy_failure_jump),
5750 REF (push_dummy_failure),
5753 REF (set_number_at),
5775 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
5779 #ifdef MATCH_MAY_ALLOCATE
5780 /* Do not bother to initialize all the register variables if there are
5781 no groups in the pattern, as it takes a fair amount of time. If
5782 there are groups, we include space for register 0 (the whole
5783 pattern), even though we never use it, since it simplifies the
5784 array indexing. We should fix this. */
5787 regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5788 regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5789 old_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5790 old_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5791 best_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5792 best_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5793 reg_info = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5794 reg_dummy = REGEX_TALLOC (num_regs, const CHAR_T *);
5795 reg_info_dummy = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5797 if (!(regstart && regend && old_regstart && old_regend && reg_info
5798 && best_regstart && best_regend && reg_dummy && reg_info_dummy))
5806 /* We must initialize all our variables to NULL, so that
5807 `FREE_VARIABLES' doesn't try to free them. */
5808 regstart = regend = old_regstart = old_regend = best_regstart
5809 = best_regend = reg_dummy = NULL;
5810 reg_info = reg_info_dummy = (PREFIX(register_info_type) *) NULL;
5812 #endif /* MATCH_MAY_ALLOCATE */
5814 /* The starting position is bogus. */
5816 if (pos < 0 || pos > csize1 + csize2)
5818 if (pos < 0 || pos > size1 + size2)
5826 /* Allocate wchar_t array for string1 and string2 and
5827 fill them with converted string. */
5828 if (string1 == NULL && string2 == NULL)
5830 /* We need seting up buffers here. */
5832 /* We must free wcs buffers in this function. */
5833 cant_free_wcs_buf = 0;
5837 string1 = REGEX_TALLOC (csize1 + 1, CHAR_T);
5838 mbs_offset1 = REGEX_TALLOC (csize1 + 1, int);
5839 is_binary = REGEX_TALLOC (csize1 + 1, char);
5840 if (!string1 || !mbs_offset1 || !is_binary)
5843 FREE_VAR (mbs_offset1);
5844 FREE_VAR (is_binary);
5850 string2 = REGEX_TALLOC (csize2 + 1, CHAR_T);
5851 mbs_offset2 = REGEX_TALLOC (csize2 + 1, int);
5852 is_binary = REGEX_TALLOC (csize2 + 1, char);
5853 if (!string2 || !mbs_offset2 || !is_binary)
5856 FREE_VAR (mbs_offset1);
5858 FREE_VAR (mbs_offset2);
5859 FREE_VAR (is_binary);
5862 size2 = convert_mbs_to_wcs(string2, cstring2, csize2,
5863 mbs_offset2, is_binary);
5864 string2[size2] = L'\0'; /* for a sentinel */
5865 FREE_VAR (is_binary);
5869 /* We need to cast pattern to (wchar_t*), because we casted this compiled
5870 pattern to (char*) in regex_compile. */
5871 p = pattern = (CHAR_T*)bufp->buffer;
5872 pend = (CHAR_T*)(bufp->buffer + bufp->used);
5876 /* Initialize subexpression text positions to -1 to mark ones that no
5877 start_memory/stop_memory has been seen for. Also initialize the
5878 register information struct. */
5879 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
5881 regstart[mcnt] = regend[mcnt]
5882 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
5884 REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
5885 IS_ACTIVE (reg_info[mcnt]) = 0;
5886 MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5887 EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5890 /* We move `string1' into `string2' if the latter's empty -- but not if
5891 `string1' is null. */
5892 if (size2 == 0 && string1 != NULL)
5899 mbs_offset2 = mbs_offset1;
5905 end1 = string1 + size1;
5906 end2 = string2 + size2;
5908 /* Compute where to stop matching, within the two strings. */
5912 mcnt = count_mbs_length(mbs_offset1, stop);
5913 end_match_1 = string1 + mcnt;
5914 end_match_2 = string2;
5918 if (stop > csize1 + csize2)
5919 stop = csize1 + csize2;
5921 mcnt = count_mbs_length(mbs_offset2, stop-csize1);
5922 end_match_2 = string2 + mcnt;
5925 { /* count_mbs_length return error. */
5932 end_match_1 = string1 + stop;
5933 end_match_2 = string2;
5938 end_match_2 = string2 + stop - size1;
5942 /* `p' scans through the pattern as `d' scans through the data.
5943 `dend' is the end of the input string that `d' points within. `d'
5944 is advanced into the following input string whenever necessary, but
5945 this happens before fetching; therefore, at the beginning of the
5946 loop, `d' can be pointing at the end of a string, but it cannot
5949 if (size1 > 0 && pos <= csize1)
5951 mcnt = count_mbs_length(mbs_offset1, pos);
5957 mcnt = count_mbs_length(mbs_offset2, pos-csize1);
5963 { /* count_mbs_length return error. */
5968 if (size1 > 0 && pos <= size1)
5975 d = string2 + pos - size1;
5980 DEBUG_PRINT1 ("The compiled pattern is:\n");
5981 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
5982 DEBUG_PRINT1 ("The string to match is: `");
5983 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
5984 DEBUG_PRINT1 ("'\n");
5986 /* This loops over pattern commands. It exits by returning from the
5987 function if the match is complete, or it drops through if the match
5988 fails at this starting point in the input data. */
5992 DEBUG_PRINT2 ("\n%p: ", p);
5994 DEBUG_PRINT2 ("\n0x%x: ", p);
6006 /* End of pattern means we might have succeeded. */
6007 DEBUG_PRINT1 ("end of pattern ... ");
6009 /* If we haven't matched the entire string, and we want the
6010 longest match, try backtracking. */
6011 if (d != end_match_2)
6013 /* 1 if this match is the best seen so far. */
6014 boolean best_match_p;
6017 /* 1 if this match ends in the same string (string1 or string2)
6018 as the best previous match. */
6019 boolean same_str_p = (FIRST_STRING_P (match_end)
6020 == MATCHING_IN_FIRST_STRING);
6022 /* AIX compiler got confused when this was combined
6023 with the previous declaration. */
6025 best_match_p = d > match_end;
6027 best_match_p = !MATCHING_IN_FIRST_STRING;
6030 DEBUG_PRINT1 ("backtracking.\n");
6032 if (!FAIL_STACK_EMPTY ())
6033 { /* More failure points to try. */
6035 /* If exceeds best match so far, save it. */
6036 if (!best_regs_set || best_match_p)
6038 best_regs_set = true;
6041 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
6043 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6045 best_regstart[mcnt] = regstart[mcnt];
6046 best_regend[mcnt] = regend[mcnt];
6052 /* If no failure points, don't restore garbage. And if
6053 last match is real best match, don't restore second
6055 else if (best_regs_set && !best_match_p)
6058 /* Restore best match. It may happen that `dend ==
6059 end_match_1' while the restored d is in string2.
6060 For example, the pattern `x.*y.*z' against the
6061 strings `x-' and `y-z-', if the two strings are
6062 not consecutive in memory. */
6063 DEBUG_PRINT1 ("Restoring best registers.\n");
6066 dend = ((d >= string1 && d <= end1)
6067 ? end_match_1 : end_match_2);
6069 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6071 regstart[mcnt] = best_regstart[mcnt];
6072 regend[mcnt] = best_regend[mcnt];
6075 } /* d != end_match_2 */
6078 DEBUG_PRINT1 ("Accepting match.\n");
6079 /* If caller wants register contents data back, do it. */
6080 if (regs && !bufp->no_sub)
6082 /* Have the register data arrays been allocated? */
6083 if (bufp->regs_allocated == REGS_UNALLOCATED)
6084 { /* No. So allocate them with malloc. We need one
6085 extra element beyond `num_regs' for the `-1' marker
6087 regs->num_regs = MAX (RE_NREGS, num_regs + 1);
6088 regs->start = TALLOC (regs->num_regs, regoff_t);
6089 regs->end = TALLOC (regs->num_regs, regoff_t);
6090 if (regs->start == NULL || regs->end == NULL)
6095 bufp->regs_allocated = REGS_REALLOCATE;
6097 else if (bufp->regs_allocated == REGS_REALLOCATE)
6098 { /* Yes. If we need more elements than were already
6099 allocated, reallocate them. If we need fewer, just
6101 if (regs->num_regs < num_regs + 1)
6103 regs->num_regs = num_regs + 1;
6104 RETALLOC (regs->start, regs->num_regs, regoff_t);
6105 RETALLOC (regs->end, regs->num_regs, regoff_t);
6106 if (regs->start == NULL || regs->end == NULL)
6115 /* These braces fend off a "empty body in an else-statement"
6116 warning under GCC when assert expands to nothing. */
6117 assert (bufp->regs_allocated == REGS_FIXED);
6120 /* Convert the pointer data in `regstart' and `regend' to
6121 indices. Register zero has to be set differently,
6122 since we haven't kept track of any info for it. */
6123 if (regs->num_regs > 0)
6125 regs->start[0] = pos;
6127 if (MATCHING_IN_FIRST_STRING)
6128 regs->end[0] = (mbs_offset1 != NULL ?
6129 mbs_offset1[d-string1] : 0);
6131 regs->end[0] = csize1 + (mbs_offset2 != NULL
6132 ? mbs_offset2[d-string2] : 0);
6134 regs->end[0] = (MATCHING_IN_FIRST_STRING
6135 ? ((regoff_t) (d - string1))
6136 : ((regoff_t) (d - string2 + size1)));
6140 /* Go through the first `min (num_regs, regs->num_regs)'
6141 registers, since that is all we initialized. */
6142 for (mcnt = 1; (unsigned) mcnt < MIN (num_regs, regs->num_regs);
6145 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
6146 regs->start[mcnt] = regs->end[mcnt] = -1;
6150 = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
6152 = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
6156 /* If the regs structure we return has more elements than
6157 were in the pattern, set the extra elements to -1. If
6158 we (re)allocated the registers, this is the case,
6159 because we always allocate enough to have at least one
6161 for (mcnt = num_regs; (unsigned) mcnt < regs->num_regs; mcnt++)
6162 regs->start[mcnt] = regs->end[mcnt] = -1;
6163 } /* regs && !bufp->no_sub */
6165 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
6166 nfailure_points_pushed, nfailure_points_popped,
6167 nfailure_points_pushed - nfailure_points_popped);
6168 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
6171 if (MATCHING_IN_FIRST_STRING)
6172 mcnt = mbs_offset1 != NULL ? mbs_offset1[d-string1] : 0;
6174 mcnt = (mbs_offset2 != NULL ? mbs_offset2[d-string2] : 0) +
6178 mcnt = d - pos - (MATCHING_IN_FIRST_STRING
6179 ? string1 : string2 - size1);
6182 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
6189 /* Otherwise match next pattern command. */
6190 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
6193 /* Ignore these. Used to ignore the n of succeed_n's which
6194 currently have n == 0. */
6196 DEBUG_PRINT1 ("EXECUTING no_op.\n");
6200 DEBUG_PRINT1 ("EXECUTING succeed.\n");
6203 /* Match the next n pattern characters exactly. The following
6204 byte in the pattern defines n, and the n bytes after that
6205 are the characters to match. */
6211 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
6213 /* This is written out as an if-else so we don't waste time
6214 testing `translate' inside the loop. */
6223 if ((UCHAR_T) translate[(unsigned char) *d++]
6229 if (*d++ != (CHAR_T) *p++)
6233 if ((UCHAR_T) translate[(unsigned char) *d++]
6245 if (*d++ != (CHAR_T) *p++) goto fail;
6249 SET_REGS_MATCHED ();
6253 /* Match any character except possibly a newline or a null. */
6255 DEBUG_PRINT1 ("EXECUTING anychar.\n");
6259 if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
6260 || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
6263 SET_REGS_MATCHED ();
6264 DEBUG_PRINT2 (" Matched `%ld'.\n", (long int) *d);
6274 unsigned int i, char_class_length, coll_symbol_length,
6275 equiv_class_length, ranges_length, chars_length, length;
6276 CHAR_T *workp, *workp2, *charset_top;
6277 #define WORK_BUFFER_SIZE 128
6278 CHAR_T str_buf[WORK_BUFFER_SIZE];
6283 boolean negate = (re_opcode_t) *(p - 1) == charset_not;
6285 DEBUG_PRINT2 ("EXECUTING charset%s.\n", negate ? "_not" : "");
6287 c = TRANSLATE (*d); /* The character to match. */
6290 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
6292 charset_top = p - 1;
6293 char_class_length = *p++;
6294 coll_symbol_length = *p++;
6295 equiv_class_length = *p++;
6296 ranges_length = *p++;
6297 chars_length = *p++;
6298 /* p points charset[6], so the address of the next instruction
6299 (charset[l+m+n+2o+k+p']) equals p[l+m+n+2*o+p'],
6300 where l=length of char_classes, m=length of collating_symbol,
6301 n=equivalence_class, o=length of char_range,
6302 p'=length of character. */
6304 /* Update p to indicate the next instruction. */
6305 p += char_class_length + coll_symbol_length+ equiv_class_length +
6306 2*ranges_length + chars_length;
6308 /* match with char_class? */
6309 for (i = 0; i < char_class_length ; i += CHAR_CLASS_SIZE)
6312 uintptr_t alignedp = ((uintptr_t)workp
6313 + __alignof__(wctype_t) - 1)
6314 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
6315 wctype = *((wctype_t*)alignedp);
6316 workp += CHAR_CLASS_SIZE;
6317 if (iswctype((wint_t)c, wctype))
6318 goto char_set_matched;
6321 /* match with collating_symbol? */
6325 const unsigned char *extra = (const unsigned char *)
6326 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
6328 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;
6332 wextra = (int32_t*)(extra + *workp++);
6333 for (i = 0; i < *wextra; ++i)
6334 if (TRANSLATE(d[i]) != wextra[1 + i])
6339 /* Update d, however d will be incremented at
6340 char_set_matched:, we decrement d here. */
6342 goto char_set_matched;
6346 else /* (nrules == 0) */
6348 /* If we can't look up collation data, we use wcscoll
6351 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;)
6353 const CHAR_T *backup_d = d, *backup_dend = dend;
6354 length = wcslen (workp);
6356 /* If wcscoll(the collating symbol, whole string) > 0,
6357 any substring of the string never match with the
6358 collating symbol. */
6359 if (wcscoll (workp, d) > 0)
6361 workp += length + 1;
6365 /* First, we compare the collating symbol with
6366 the first character of the string.
6367 If it don't match, we add the next character to
6368 the compare buffer in turn. */
6369 for (i = 0 ; i < WORK_BUFFER_SIZE-1 ; i++, d++)
6374 if (dend == end_match_2)
6380 /* add next character to the compare buffer. */
6381 str_buf[i] = TRANSLATE(*d);
6382 str_buf[i+1] = '\0';
6384 match = wcscoll (workp, str_buf);
6386 goto char_set_matched;
6389 /* (str_buf > workp) indicate (str_buf + X > workp),
6390 because for all X (str_buf + X > str_buf).
6391 So we don't need continue this loop. */
6394 /* Otherwise(str_buf < workp),
6395 (str_buf+next_character) may equals (workp).
6396 So we continue this loop. */
6401 workp += length + 1;
6404 /* match with equivalence_class? */
6408 const CHAR_T *backup_d = d, *backup_dend = dend;
6409 /* Try to match the equivalence class against
6410 those known to the collate implementation. */
6411 const int32_t *table;
6412 const int32_t *weights;
6413 const int32_t *extra;
6414 const int32_t *indirect;
6419 /* This #include defines a local function! */
6420 # include <locale/weightwc.h>
6422 table = (const int32_t *)
6423 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
6424 weights = (const wint_t *)
6425 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
6426 extra = (const wint_t *)
6427 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
6428 indirect = (const int32_t *)
6429 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
6431 /* Write 1 collating element to str_buf, and
6435 for (i = 0 ; idx2 == 0 && i < WORK_BUFFER_SIZE - 1; i++)
6437 cp = (wint_t*)str_buf;
6440 if (dend == end_match_2)
6445 str_buf[i] = TRANSLATE(*(d+i));
6446 str_buf[i+1] = '\0'; /* sentinel */
6447 idx2 = findidx ((const wint_t**)&cp);
6450 /* Update d, however d will be incremented at
6451 char_set_matched:, we decrement d here. */
6452 d = backup_d + ((wchar_t*)cp - (wchar_t*)str_buf - 1);
6455 if (dend == end_match_2)
6464 len = weights[idx2];
6466 for (workp2 = workp + equiv_class_length ; workp < workp2 ;
6469 idx = (int32_t)*workp;
6470 /* We already checked idx != 0 in regex_compile. */
6472 if (idx2 != 0 && len == weights[idx])
6475 while (cnt < len && (weights[idx + 1 + cnt]
6476 == weights[idx2 + 1 + cnt]))
6480 goto char_set_matched;
6487 else /* (nrules == 0) */
6489 /* If we can't look up collation data, we use wcscoll
6492 for (workp2 = workp + equiv_class_length ; workp < workp2 ;)
6494 const CHAR_T *backup_d = d, *backup_dend = dend;
6495 length = wcslen (workp);
6497 /* If wcscoll(the collating symbol, whole string) > 0,
6498 any substring of the string never match with the
6499 collating symbol. */
6500 if (wcscoll (workp, d) > 0)
6502 workp += length + 1;
6506 /* First, we compare the equivalence class with
6507 the first character of the string.
6508 If it don't match, we add the next character to
6509 the compare buffer in turn. */
6510 for (i = 0 ; i < WORK_BUFFER_SIZE - 1 ; i++, d++)
6515 if (dend == end_match_2)
6521 /* add next character to the compare buffer. */
6522 str_buf[i] = TRANSLATE(*d);
6523 str_buf[i+1] = '\0';
6525 match = wcscoll (workp, str_buf);
6528 goto char_set_matched;
6531 /* (str_buf > workp) indicate (str_buf + X > workp),
6532 because for all X (str_buf + X > str_buf).
6533 So we don't need continue this loop. */
6536 /* Otherwise(str_buf < workp),
6537 (str_buf+next_character) may equals (workp).
6538 So we continue this loop. */
6543 workp += length + 1;
6547 /* match with char_range? */
6551 uint32_t collseqval;
6552 const char *collseq = (const char *)
6553 _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
6555 collseqval = collseq_table_lookup (collseq, c);
6557 for (; workp < p - chars_length ;)
6559 uint32_t start_val, end_val;
6561 /* We already compute the collation sequence value
6562 of the characters (or collating symbols). */
6563 start_val = (uint32_t) *workp++; /* range_start */
6564 end_val = (uint32_t) *workp++; /* range_end */
6566 if (start_val <= collseqval && collseqval <= end_val)
6567 goto char_set_matched;
6573 /* We set range_start_char at str_buf[0], range_end_char
6574 at str_buf[4], and compared char at str_buf[2]. */
6579 for (; workp < p - chars_length ;)
6581 wchar_t *range_start_char, *range_end_char;
6583 /* match if (range_start_char <= c <= range_end_char). */
6585 /* If range_start(or end) < 0, we assume -range_start(end)
6586 is the offset of the collating symbol which is specified
6587 as the character of the range start(end). */
6591 range_start_char = charset_top - (*workp++);
6594 str_buf[0] = *workp++;
6595 range_start_char = str_buf;
6600 range_end_char = charset_top - (*workp++);
6603 str_buf[4] = *workp++;
6604 range_end_char = str_buf + 4;
6607 if (wcscoll (range_start_char, str_buf+2) <= 0
6608 && wcscoll (str_buf+2, range_end_char) <= 0)
6609 goto char_set_matched;
6613 /* match with char? */
6614 for (; workp < p ; workp++)
6616 goto char_set_matched;
6621 if (negate) goto fail;
6623 /* Cast to `unsigned' instead of `unsigned char' in case the
6624 bit list is a full 32 bytes long. */
6625 if (c < (unsigned) (*p * BYTEWIDTH)
6626 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
6631 if (!negate) goto fail;
6632 #undef WORK_BUFFER_SIZE
6634 SET_REGS_MATCHED ();
6640 /* The beginning of a group is represented by start_memory.
6641 The arguments are the register number in the next byte, and the
6642 number of groups inner to this one in the next. The text
6643 matched within the group is recorded (in the internal
6644 registers data structure) under the register number. */
6645 CASE (start_memory):
6646 DEBUG_PRINT3 ("EXECUTING start_memory %ld (%ld):\n",
6647 (long int) *p, (long int) p[1]);
6649 /* Find out if this group can match the empty string. */
6650 p1 = p; /* To send to group_match_null_string_p. */
6652 if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
6653 REG_MATCH_NULL_STRING_P (reg_info[*p])
6654 = PREFIX(group_match_null_string_p) (&p1, pend, reg_info);
6656 /* Save the position in the string where we were the last time
6657 we were at this open-group operator in case the group is
6658 operated upon by a repetition operator, e.g., with `(a*)*b'
6659 against `ab'; then we want to ignore where we are now in
6660 the string in case this attempt to match fails. */
6661 old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6662 ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
6664 DEBUG_PRINT2 (" old_regstart: %d\n",
6665 POINTER_TO_OFFSET (old_regstart[*p]));
6668 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
6670 IS_ACTIVE (reg_info[*p]) = 1;
6671 MATCHED_SOMETHING (reg_info[*p]) = 0;
6673 /* Clear this whenever we change the register activity status. */
6674 set_regs_matched_done = 0;
6676 /* This is the new highest active register. */
6677 highest_active_reg = *p;
6679 /* If nothing was active before, this is the new lowest active
6681 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
6682 lowest_active_reg = *p;
6684 /* Move past the register number and inner group count. */
6686 just_past_start_mem = p;
6691 /* The stop_memory opcode represents the end of a group. Its
6692 arguments are the same as start_memory's: the register
6693 number, and the number of inner groups. */
6695 DEBUG_PRINT3 ("EXECUTING stop_memory %ld (%ld):\n",
6696 (long int) *p, (long int) p[1]);
6698 /* We need to save the string position the last time we were at
6699 this close-group operator in case the group is operated
6700 upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
6701 against `aba'; then we want to ignore where we are now in
6702 the string in case this attempt to match fails. */
6703 old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6704 ? REG_UNSET (regend[*p]) ? d : regend[*p]
6706 DEBUG_PRINT2 (" old_regend: %d\n",
6707 POINTER_TO_OFFSET (old_regend[*p]));
6710 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
6712 /* This register isn't active anymore. */
6713 IS_ACTIVE (reg_info[*p]) = 0;
6715 /* Clear this whenever we change the register activity status. */
6716 set_regs_matched_done = 0;
6718 /* If this was the only register active, nothing is active
6720 if (lowest_active_reg == highest_active_reg)
6722 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6723 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6726 { /* We must scan for the new highest active register, since
6727 it isn't necessarily one less than now: consider
6728 (a(b)c(d(e)f)g). When group 3 ends, after the f), the
6729 new highest active register is 1. */
6731 while (r > 0 && !IS_ACTIVE (reg_info[r]))
6734 /* If we end up at register zero, that means that we saved
6735 the registers as the result of an `on_failure_jump', not
6736 a `start_memory', and we jumped to past the innermost
6737 `stop_memory'. For example, in ((.)*) we save
6738 registers 1 and 2 as a result of the *, but when we pop
6739 back to the second ), we are at the stop_memory 1.
6740 Thus, nothing is active. */
6743 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6744 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6747 highest_active_reg = r;
6750 /* If just failed to match something this time around with a
6751 group that's operated on by a repetition operator, try to
6752 force exit from the ``loop'', and restore the register
6753 information for this group that we had before trying this
6755 if ((!MATCHED_SOMETHING (reg_info[*p])
6756 || just_past_start_mem == p - 1)
6759 boolean is_a_jump_n = false;
6763 switch ((re_opcode_t) *p1++)
6767 case pop_failure_jump:
6768 case maybe_pop_jump:
6770 case dummy_failure_jump:
6771 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6773 p1 += OFFSET_ADDRESS_SIZE;
6781 /* If the next operation is a jump backwards in the pattern
6782 to an on_failure_jump right before the start_memory
6783 corresponding to this stop_memory, exit from the loop
6784 by forcing a failure after pushing on the stack the
6785 on_failure_jump's jump in the pattern, and d. */
6786 if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
6787 && (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == start_memory
6788 && p1[2+OFFSET_ADDRESS_SIZE] == *p)
6790 /* If this group ever matched anything, then restore
6791 what its registers were before trying this last
6792 failed match, e.g., with `(a*)*b' against `ab' for
6793 regstart[1], and, e.g., with `((a*)*(b*)*)*'
6794 against `aba' for regend[3].
6796 Also restore the registers for inner groups for,
6797 e.g., `((a*)(b*))*' against `aba' (register 3 would
6798 otherwise get trashed). */
6800 if (EVER_MATCHED_SOMETHING (reg_info[*p]))
6804 EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
6806 /* Restore this and inner groups' (if any) registers. */
6807 for (r = *p; r < (unsigned) *p + (unsigned) *(p + 1);
6810 regstart[r] = old_regstart[r];
6812 /* xx why this test? */
6813 if (old_regend[r] >= regstart[r])
6814 regend[r] = old_regend[r];
6818 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6819 PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
6825 /* Move past the register number and the inner group count. */
6830 /* \<digit> has been turned into a `duplicate' command which is
6831 followed by the numeric value of <digit> as the register number. */
6834 register const CHAR_T *d2, *dend2;
6835 int regno = *p++; /* Get which register to match against. */
6836 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
6838 /* Can't back reference a group which we've never matched. */
6839 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
6842 /* Where in input to try to start matching. */
6843 d2 = regstart[regno];
6845 /* Where to stop matching; if both the place to start and
6846 the place to stop matching are in the same string, then
6847 set to the place to stop, otherwise, for now have to use
6848 the end of the first string. */
6850 dend2 = ((FIRST_STRING_P (regstart[regno])
6851 == FIRST_STRING_P (regend[regno]))
6852 ? regend[regno] : end_match_1);
6855 /* If necessary, advance to next segment in register
6859 if (dend2 == end_match_2) break;
6860 if (dend2 == regend[regno]) break;
6862 /* End of string1 => advance to string2. */
6864 dend2 = regend[regno];
6866 /* At end of register contents => success */
6867 if (d2 == dend2) break;
6869 /* If necessary, advance to next segment in data. */
6872 /* How many characters left in this segment to match. */
6875 /* Want how many consecutive characters we can match in
6876 one shot, so, if necessary, adjust the count. */
6877 if (mcnt > dend2 - d2)
6880 /* Compare that many; failure if mismatch, else move
6883 ? PREFIX(bcmp_translate) (d, d2, mcnt, translate)
6884 : memcmp (d, d2, mcnt*sizeof(UCHAR_T)))
6886 d += mcnt, d2 += mcnt;
6888 /* Do this because we've match some characters. */
6889 SET_REGS_MATCHED ();
6895 /* begline matches the empty string at the beginning of the string
6896 (unless `not_bol' is set in `bufp'), and, if
6897 `newline_anchor' is set, after newlines. */
6899 DEBUG_PRINT1 ("EXECUTING begline.\n");
6901 if (AT_STRINGS_BEG (d))
6908 else if (d[-1] == '\n' && bufp->newline_anchor)
6912 /* In all other cases, we fail. */
6916 /* endline is the dual of begline. */
6918 DEBUG_PRINT1 ("EXECUTING endline.\n");
6920 if (AT_STRINGS_END (d))
6928 /* We have to ``prefetch'' the next character. */
6929 else if ((d == end1 ? *string2 : *d) == '\n'
6930 && bufp->newline_anchor)
6937 /* Match at the very beginning of the data. */
6939 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
6940 if (AT_STRINGS_BEG (d))
6947 /* Match at the very end of the data. */
6949 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
6950 if (AT_STRINGS_END (d))
6957 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
6958 pushes NULL as the value for the string on the stack. Then
6959 `pop_failure_point' will keep the current value for the
6960 string, instead of restoring it. To see why, consider
6961 matching `foo\nbar' against `.*\n'. The .* matches the foo;
6962 then the . fails against the \n. But the next thing we want
6963 to do is match the \n against the \n; if we restored the
6964 string value, we would be back at the foo.
6966 Because this is used only in specific cases, we don't need to
6967 check all the things that `on_failure_jump' does, to make
6968 sure the right things get saved on the stack. Hence we don't
6969 share its code. The only reason to push anything on the
6970 stack at all is that otherwise we would have to change
6971 `anychar's code to do something besides goto fail in this
6972 case; that seems worse than this. */
6973 CASE (on_failure_keep_string_jump):
6974 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
6976 EXTRACT_NUMBER_AND_INCR (mcnt, p);
6978 DEBUG_PRINT3 (" %d (to %p):\n", mcnt, p + mcnt);
6980 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
6983 PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
6987 /* Uses of on_failure_jump:
6989 Each alternative starts with an on_failure_jump that points
6990 to the beginning of the next alternative. Each alternative
6991 except the last ends with a jump that in effect jumps past
6992 the rest of the alternatives. (They really jump to the
6993 ending jump of the following alternative, because tensioning
6994 these jumps is a hassle.)
6996 Repeats start with an on_failure_jump that points past both
6997 the repetition text and either the following jump or
6998 pop_failure_jump back to this on_failure_jump. */
6999 CASE (on_failure_jump):
7001 DEBUG_PRINT1 ("EXECUTING on_failure_jump");
7003 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7005 DEBUG_PRINT3 (" %d (to %p)", mcnt, p + mcnt);
7007 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
7010 /* If this on_failure_jump comes right before a group (i.e.,
7011 the original * applied to a group), save the information
7012 for that group and all inner ones, so that if we fail back
7013 to this point, the group's information will be correct.
7014 For example, in \(a*\)*\1, we need the preceding group,
7015 and in \(zz\(a*\)b*\)\2, we need the inner group. */
7017 /* We can't use `p' to check ahead because we push
7018 a failure point to `p + mcnt' after we do this. */
7021 /* We need to skip no_op's before we look for the
7022 start_memory in case this on_failure_jump is happening as
7023 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
7025 while (p1 < pend && (re_opcode_t) *p1 == no_op)
7028 if (p1 < pend && (re_opcode_t) *p1 == start_memory)
7030 /* We have a new highest active register now. This will
7031 get reset at the start_memory we are about to get to,
7032 but we will have saved all the registers relevant to
7033 this repetition op, as described above. */
7034 highest_active_reg = *(p1 + 1) + *(p1 + 2);
7035 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
7036 lowest_active_reg = *(p1 + 1);
7039 DEBUG_PRINT1 (":\n");
7040 PUSH_FAILURE_POINT (p + mcnt, d, -2);
7044 /* A smart repeat ends with `maybe_pop_jump'.
7045 We change it to either `pop_failure_jump' or `jump'. */
7046 CASE (maybe_pop_jump):
7047 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7048 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
7050 register UCHAR_T *p2 = p;
7052 /* Compare the beginning of the repeat with what in the
7053 pattern follows its end. If we can establish that there
7054 is nothing that they would both match, i.e., that we
7055 would have to backtrack because of (as in, e.g., `a*a')
7056 then we can change to pop_failure_jump, because we'll
7057 never have to backtrack.
7059 This is not true in the case of alternatives: in
7060 `(a|ab)*' we do need to backtrack to the `ab' alternative
7061 (e.g., if the string was `ab'). But instead of trying to
7062 detect that here, the alternative has put on a dummy
7063 failure point which is what we will end up popping. */
7065 /* Skip over open/close-group commands.
7066 If what follows this loop is a ...+ construct,
7067 look at what begins its body, since we will have to
7068 match at least one of that. */
7072 && ((re_opcode_t) *p2 == stop_memory
7073 || (re_opcode_t) *p2 == start_memory))
7075 else if (p2 + 2 + 2 * OFFSET_ADDRESS_SIZE < pend
7076 && (re_opcode_t) *p2 == dummy_failure_jump)
7077 p2 += 2 + 2 * OFFSET_ADDRESS_SIZE;
7083 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
7084 to the `maybe_finalize_jump' of this case. Examine what
7087 /* If we're at the end of the pattern, we can change. */
7090 /* Consider what happens when matching ":\(.*\)"
7091 against ":/". I don't really understand this code
7093 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7096 (" End of pattern: change to `pop_failure_jump'.\n");
7099 else if ((re_opcode_t) *p2 == exactn
7101 || (re_opcode_t) *p2 == exactn_bin
7103 || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
7106 = *p2 == (UCHAR_T) endline ? '\n' : p2[2];
7108 if (((re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn
7110 || (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn_bin
7112 ) && p1[3+OFFSET_ADDRESS_SIZE] != c)
7114 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7117 DEBUG_PRINT3 (" %C != %C => pop_failure_jump.\n",
7119 (wint_t) p1[3+OFFSET_ADDRESS_SIZE]);
7121 DEBUG_PRINT3 (" %c != %c => pop_failure_jump.\n",
7123 (char) p1[3+OFFSET_ADDRESS_SIZE]);
7128 else if ((re_opcode_t) p1[3] == charset
7129 || (re_opcode_t) p1[3] == charset_not)
7131 int negate = (re_opcode_t) p1[3] == charset_not;
7133 if (c < (unsigned) (p1[4] * BYTEWIDTH)
7134 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
7137 /* `negate' is equal to 1 if c would match, which means
7138 that we can't change to pop_failure_jump. */
7141 p[-3] = (unsigned char) pop_failure_jump;
7142 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7145 #endif /* not WCHAR */
7148 else if ((re_opcode_t) *p2 == charset)
7150 /* We win if the first character of the loop is not part
7152 if ((re_opcode_t) p1[3] == exactn
7153 && ! ((int) p2[1] * BYTEWIDTH > (int) p1[5]
7154 && (p2[2 + p1[5] / BYTEWIDTH]
7155 & (1 << (p1[5] % BYTEWIDTH)))))
7157 p[-3] = (unsigned char) pop_failure_jump;
7158 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7161 else if ((re_opcode_t) p1[3] == charset_not)
7164 /* We win if the charset_not inside the loop
7165 lists every character listed in the charset after. */
7166 for (idx = 0; idx < (int) p2[1]; idx++)
7167 if (! (p2[2 + idx] == 0
7168 || (idx < (int) p1[4]
7169 && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
7174 p[-3] = (unsigned char) pop_failure_jump;
7175 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7178 else if ((re_opcode_t) p1[3] == charset)
7181 /* We win if the charset inside the loop
7182 has no overlap with the one after the loop. */
7184 idx < (int) p2[1] && idx < (int) p1[4];
7186 if ((p2[2 + idx] & p1[5 + idx]) != 0)
7189 if (idx == p2[1] || idx == p1[4])
7191 p[-3] = (unsigned char) pop_failure_jump;
7192 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7196 #endif /* not WCHAR */
7198 p -= OFFSET_ADDRESS_SIZE; /* Point at relative address again. */
7199 if ((re_opcode_t) p[-1] != pop_failure_jump)
7201 p[-1] = (UCHAR_T) jump;
7202 DEBUG_PRINT1 (" Match => jump.\n");
7203 goto unconditional_jump;
7205 /* Note fall through. */
7208 /* The end of a simple repeat has a pop_failure_jump back to
7209 its matching on_failure_jump, where the latter will push a
7210 failure point. The pop_failure_jump takes off failure
7211 points put on by this pop_failure_jump's matching
7212 on_failure_jump; we got through the pattern to here from the
7213 matching on_failure_jump, so didn't fail. */
7214 CASE (pop_failure_jump):
7216 /* We need to pass separate storage for the lowest and
7217 highest registers, even though we don't care about the
7218 actual values. Otherwise, we will restore only one
7219 register from the stack, since lowest will == highest in
7220 `pop_failure_point'. */
7221 active_reg_t dummy_low_reg, dummy_high_reg;
7222 UCHAR_T *pdummy = NULL;
7223 const CHAR_T *sdummy = NULL;
7225 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
7226 POP_FAILURE_POINT (sdummy, pdummy,
7227 dummy_low_reg, dummy_high_reg,
7228 reg_dummy, reg_dummy, reg_info_dummy);
7230 /* Note fall through. */
7234 DEBUG_PRINT2 ("\n%p: ", p);
7236 DEBUG_PRINT2 ("\n0x%x: ", p);
7238 /* Note fall through. */
7240 /* Unconditionally jump (without popping any failure points). */
7242 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
7243 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
7244 p += mcnt; /* Do the jump. */
7246 DEBUG_PRINT2 ("(to %p).\n", p);
7248 DEBUG_PRINT2 ("(to 0x%x).\n", p);
7253 /* We need this opcode so we can detect where alternatives end
7254 in `group_match_null_string_p' et al. */
7255 CASE (jump_past_alt):
7256 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
7257 goto unconditional_jump;
7260 /* Normally, the on_failure_jump pushes a failure point, which
7261 then gets popped at pop_failure_jump. We will end up at
7262 pop_failure_jump, also, and with a pattern of, say, `a+', we
7263 are skipping over the on_failure_jump, so we have to push
7264 something meaningless for pop_failure_jump to pop. */
7265 CASE (dummy_failure_jump):
7266 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
7267 /* It doesn't matter what we push for the string here. What
7268 the code at `fail' tests is the value for the pattern. */
7269 PUSH_FAILURE_POINT (NULL, NULL, -2);
7270 goto unconditional_jump;
7273 /* At the end of an alternative, we need to push a dummy failure
7274 point in case we are followed by a `pop_failure_jump', because
7275 we don't want the failure point for the alternative to be
7276 popped. For example, matching `(a|ab)*' against `aab'
7277 requires that we match the `ab' alternative. */
7278 CASE (push_dummy_failure):
7279 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
7280 /* See comments just above at `dummy_failure_jump' about the
7282 PUSH_FAILURE_POINT (NULL, NULL, -2);
7285 /* Have to succeed matching what follows at least n times.
7286 After that, handle like `on_failure_jump'. */
7288 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7289 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
7292 /* Originally, this is how many times we HAVE to succeed. */
7296 p += OFFSET_ADDRESS_SIZE;
7297 STORE_NUMBER_AND_INCR (p, mcnt);
7299 DEBUG_PRINT3 (" Setting %p to %d.\n", p - OFFSET_ADDRESS_SIZE
7302 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p - OFFSET_ADDRESS_SIZE
7309 DEBUG_PRINT2 (" Setting two bytes from %p to no_op.\n",
7310 p + OFFSET_ADDRESS_SIZE);
7312 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n",
7313 p + OFFSET_ADDRESS_SIZE);
7317 p[1] = (UCHAR_T) no_op;
7319 p[2] = (UCHAR_T) no_op;
7320 p[3] = (UCHAR_T) no_op;
7327 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7328 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
7330 /* Originally, this is how many times we CAN jump. */
7334 STORE_NUMBER (p + OFFSET_ADDRESS_SIZE, mcnt);
7337 DEBUG_PRINT3 (" Setting %p to %d.\n", p + OFFSET_ADDRESS_SIZE,
7340 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p + OFFSET_ADDRESS_SIZE,
7343 goto unconditional_jump;
7345 /* If don't have to jump any more, skip over the rest of command. */
7347 p += 2 * OFFSET_ADDRESS_SIZE;
7350 CASE (set_number_at):
7352 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
7354 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7356 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7358 DEBUG_PRINT3 (" Setting %p to %d.\n", p1, mcnt);
7360 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1, mcnt);
7362 STORE_NUMBER (p1, mcnt);
7367 /* The DEC Alpha C compiler 3.x generates incorrect code for the
7368 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
7369 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
7370 macro and introducing temporary variables works around the bug. */
7373 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7374 if (AT_WORD_BOUNDARY (d))
7380 CASE (notwordbound):
7381 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7382 if (AT_WORD_BOUNDARY (d))
7388 boolean prevchar, thischar;
7390 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7391 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7396 prevchar = WORDCHAR_P (d - 1);
7397 thischar = WORDCHAR_P (d);
7398 if (prevchar != thischar)
7405 CASE (notwordbound):
7407 boolean prevchar, thischar;
7409 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7410 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7413 prevchar = WORDCHAR_P (d - 1);
7414 thischar = WORDCHAR_P (d);
7415 if (prevchar != thischar)
7422 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
7423 if (!AT_STRINGS_END (d) && WORDCHAR_P (d)
7424 && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
7431 DEBUG_PRINT1 ("EXECUTING wordend.\n");
7432 if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
7433 && (AT_STRINGS_END (d) || !WORDCHAR_P (d)))
7441 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
7442 if (PTR_CHAR_POS ((unsigned char *) d) >= point)
7447 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
7448 if (PTR_CHAR_POS ((unsigned char *) d) != point)
7453 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
7454 if (PTR_CHAR_POS ((unsigned char *) d) <= point)
7459 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
7464 DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
7468 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7470 if (SYNTAX (d[-1]) != (enum syntaxcode) mcnt)
7472 SET_REGS_MATCHED ();
7475 CASE (notsyntaxspec):
7476 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
7478 goto matchnotsyntax;
7481 DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
7485 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7487 if (SYNTAX (d[-1]) == (enum syntaxcode) mcnt)
7489 SET_REGS_MATCHED ();
7492 #else /* not emacs */
7494 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
7496 if (!WORDCHAR_P (d))
7498 SET_REGS_MATCHED ();
7503 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
7507 SET_REGS_MATCHED ();
7510 #endif /* not emacs */
7516 continue; /* Successfully executed one pattern command; keep going. */
7520 /* We goto here if a matching operation fails. */
7522 if (!FAIL_STACK_EMPTY ())
7523 { /* A restart point is known. Restore to that state. */
7524 DEBUG_PRINT1 ("\nFAIL:\n");
7525 POP_FAILURE_POINT (d, p,
7526 lowest_active_reg, highest_active_reg,
7527 regstart, regend, reg_info);
7529 /* If this failure point is a dummy, try the next one. */
7533 /* If we failed to the end of the pattern, don't examine *p. */
7537 boolean is_a_jump_n = false;
7539 /* If failed to a backwards jump that's part of a repetition
7540 loop, need to pop this failure point and use the next one. */
7541 switch ((re_opcode_t) *p)
7545 case maybe_pop_jump:
7546 case pop_failure_jump:
7549 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7552 if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
7554 && (re_opcode_t) *p1 == on_failure_jump))
7562 if (d >= string1 && d <= end1)
7566 break; /* Matching at this starting point really fails. */
7570 goto restore_best_regs;
7574 return -1; /* Failure to match. */
7577 /* Subroutine definitions for re_match_2. */
7580 /* We are passed P pointing to a register number after a start_memory.
7582 Return true if the pattern up to the corresponding stop_memory can
7583 match the empty string, and false otherwise.
7585 If we find the matching stop_memory, sets P to point to one past its number.
7586 Otherwise, sets P to an undefined byte less than or equal to END.
7588 We don't handle duplicates properly (yet). */
7591 PREFIX(group_match_null_string_p) (UCHAR_T **p, UCHAR_T *end,
7592 PREFIX(register_info_type) *reg_info)
7595 /* Point to after the args to the start_memory. */
7596 UCHAR_T *p1 = *p + 2;
7600 /* Skip over opcodes that can match nothing, and return true or
7601 false, as appropriate, when we get to one that can't, or to the
7602 matching stop_memory. */
7604 switch ((re_opcode_t) *p1)
7606 /* Could be either a loop or a series of alternatives. */
7607 case on_failure_jump:
7609 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7611 /* If the next operation is not a jump backwards in the
7616 /* Go through the on_failure_jumps of the alternatives,
7617 seeing if any of the alternatives cannot match nothing.
7618 The last alternative starts with only a jump,
7619 whereas the rest start with on_failure_jump and end
7620 with a jump, e.g., here is the pattern for `a|b|c':
7622 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
7623 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
7626 So, we have to first go through the first (n-1)
7627 alternatives and then deal with the last one separately. */
7630 /* Deal with the first (n-1) alternatives, which start
7631 with an on_failure_jump (see above) that jumps to right
7632 past a jump_past_alt. */
7634 while ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] ==
7637 /* `mcnt' holds how many bytes long the alternative
7638 is, including the ending `jump_past_alt' and
7641 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt -
7642 (1 + OFFSET_ADDRESS_SIZE),
7646 /* Move to right after this alternative, including the
7650 /* Break if it's the beginning of an n-th alternative
7651 that doesn't begin with an on_failure_jump. */
7652 if ((re_opcode_t) *p1 != on_failure_jump)
7655 /* Still have to check that it's not an n-th
7656 alternative that starts with an on_failure_jump. */
7658 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7659 if ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] !=
7662 /* Get to the beginning of the n-th alternative. */
7663 p1 -= 1 + OFFSET_ADDRESS_SIZE;
7668 /* Deal with the last alternative: go back and get number
7669 of the `jump_past_alt' just before it. `mcnt' contains
7670 the length of the alternative. */
7671 EXTRACT_NUMBER (mcnt, p1 - OFFSET_ADDRESS_SIZE);
7673 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt, reg_info))
7676 p1 += mcnt; /* Get past the n-th alternative. */
7682 assert (p1[1] == **p);
7688 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7691 } /* while p1 < end */
7694 } /* group_match_null_string_p */
7697 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
7698 It expects P to be the first byte of a single alternative and END one
7699 byte past the last. The alternative can contain groups. */
7702 PREFIX(alt_match_null_string_p) (UCHAR_T *p, UCHAR_T *end,
7703 PREFIX(register_info_type) *reg_info)
7710 /* Skip over opcodes that can match nothing, and break when we get
7711 to one that can't. */
7713 switch ((re_opcode_t) *p1)
7716 case on_failure_jump:
7718 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7723 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7726 } /* while p1 < end */
7729 } /* alt_match_null_string_p */
7732 /* Deals with the ops common to group_match_null_string_p and
7733 alt_match_null_string_p.
7735 Sets P to one after the op and its arguments, if any. */
7738 PREFIX(common_op_match_null_string_p) (UCHAR_T **p, UCHAR_T *end,
7739 PREFIX(register_info_type) *reg_info)
7746 switch ((re_opcode_t) *p1++)
7766 assert (reg_no > 0 && reg_no <= MAX_REGNUM);
7767 ret = PREFIX(group_match_null_string_p) (&p1, end, reg_info);
7769 /* Have to set this here in case we're checking a group which
7770 contains a group and a back reference to it. */
7772 if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
7773 REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
7779 /* If this is an optimized succeed_n for zero times, make the jump. */
7781 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7789 /* Get to the number of times to succeed. */
7790 p1 += OFFSET_ADDRESS_SIZE;
7791 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7795 p1 -= 2 * OFFSET_ADDRESS_SIZE;
7796 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7804 if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
7809 p1 += 2 * OFFSET_ADDRESS_SIZE;
7812 /* All other opcodes mean we cannot match the empty string. */
7818 } /* common_op_match_null_string_p */
7821 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
7822 bytes; nonzero otherwise. */
7825 PREFIX(bcmp_translate) (const CHAR_T *s1, const CHAR_T *s2,
7827 RE_TRANSLATE_TYPE translate)
7829 register const UCHAR_T *p1 = (const UCHAR_T *) s1;
7830 register const UCHAR_T *p2 = (const UCHAR_T *) s2;
7834 if (((*p1<=0xff)?translate[*p1++]:*p1++)
7835 != ((*p2<=0xff)?translate[*p2++]:*p2++))
7838 if (translate[*p1++] != translate[*p2++]) return 1;
7846 #else /* not INSIDE_RECURSION */
7848 /* Entry points for GNU code. */
7850 /* re_compile_pattern is the GNU regular expression compiler: it
7851 compiles PATTERN (of length SIZE) and puts the result in BUFP.
7852 Returns 0 if the pattern was valid, otherwise an error string.
7854 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
7855 are set in BUFP on entry.
7857 We call regex_compile to do the actual compilation. */
7860 re_compile_pattern (const char *pattern,
7862 struct re_pattern_buffer *bufp)
7866 /* GNU code is written to assume at least RE_NREGS registers will be set
7867 (and at least one extra will be -1). */
7868 bufp->regs_allocated = REGS_UNALLOCATED;
7870 /* And GNU code determines whether or not to get register information
7871 by passing null for the REGS argument to re_match, etc., not by
7875 /* Match anchors at newline. */
7876 bufp->newline_anchor = 1;
7879 if (MB_CUR_MAX != 1)
7880 ret = wcs_regex_compile (pattern, length, re_syntax_options, bufp);
7883 ret = byte_regex_compile (pattern, length, re_syntax_options, bufp);
7887 return gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
7890 weak_alias (__re_compile_pattern, re_compile_pattern)
7893 /* Entry points compatible with 4.2 BSD regex library. We don't define
7894 them unless specifically requested. */
7896 #if defined _REGEX_RE_COMP || defined _LIBC
7898 /* BSD has one and only one pattern buffer. */
7899 static struct re_pattern_buffer re_comp_buf;
7903 /* Make these definitions weak in libc, so POSIX programs can redefine
7904 these names if they don't use our functions, and still use
7905 regcomp/regexec below without link errors. */
7908 re_comp (const char *s)
7914 if (!re_comp_buf.buffer)
7915 return (char *) gettext ("No previous regular expression");
7919 if (!re_comp_buf.buffer)
7921 re_comp_buf.buffer = malloc (200);
7922 if (re_comp_buf.buffer == NULL)
7923 return (char *) gettext (re_error_msgid
7924 + re_error_msgid_idx[(int) REG_ESPACE]);
7925 re_comp_buf.allocated = 200;
7927 re_comp_buf.fastmap = malloc (1 << BYTEWIDTH);
7928 if (re_comp_buf.fastmap == NULL)
7929 return (char *) gettext (re_error_msgid
7930 + re_error_msgid_idx[(int) REG_ESPACE]);
7933 /* Since `re_exec' always passes NULL for the `regs' argument, we
7934 don't need to initialize the pattern buffer fields which affect it. */
7936 /* Match anchors at newlines. */
7937 re_comp_buf.newline_anchor = 1;
7940 if (MB_CUR_MAX != 1)
7941 ret = wcs_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
7944 ret = byte_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
7949 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
7950 return (char *) gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
7958 re_exec (const char *s)
7960 const int len = strlen (s);
7962 0 <= re_search (&re_comp_buf, s, len, 0, len, 0);
7965 #endif /* _REGEX_RE_COMP */
7967 /* POSIX.2 functions. Don't define these for Emacs. */
7971 /* regcomp takes a regular expression as a string and compiles it.
7973 PREG is a regex_t *. We do not expect any fields to be initialized,
7974 since POSIX says we shouldn't. Thus, we set
7976 `buffer' to the compiled pattern;
7977 `used' to the length of the compiled pattern;
7978 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
7979 REG_EXTENDED bit in CFLAGS is set; otherwise, to
7980 RE_SYNTAX_POSIX_BASIC;
7981 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
7982 `fastmap' to an allocated space for the fastmap;
7983 `fastmap_accurate' to zero;
7984 `re_nsub' to the number of subexpressions in PATTERN.
7986 PATTERN is the address of the pattern string.
7988 CFLAGS is a series of bits which affect compilation.
7990 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
7991 use POSIX basic syntax.
7993 If REG_NEWLINE is set, then . and [^...] don't match newline.
7994 Also, regexec will try a match beginning after every newline.
7996 If REG_ICASE is set, then we considers upper- and lowercase
7997 versions of letters to be equivalent when matching.
7999 If REG_NOSUB is set, then when PREG is passed to regexec, that
8000 routine will report only success or failure, and nothing about the
8003 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
8004 the return codes and their meanings.) */
8007 regcomp (regex_t *preg, const char *pattern, int cflags)
8011 = (cflags & REG_EXTENDED) ?
8012 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
8014 /* regex_compile will allocate the space for the compiled pattern. */
8016 preg->allocated = 0;
8019 /* Try to allocate space for the fastmap. */
8020 preg->fastmap = malloc (1 << BYTEWIDTH);
8022 if (cflags & REG_ICASE)
8026 preg->translate = malloc (CHAR_SET_SIZE
8027 * sizeof (*(RE_TRANSLATE_TYPE)0));
8028 if (preg->translate == NULL)
8029 return (int) REG_ESPACE;
8031 /* Map uppercase characters to corresponding lowercase ones. */
8032 for (i = 0; i < CHAR_SET_SIZE; i++)
8033 preg->translate[i] = ISUPPER (i) ? TOLOWER (i) : i;
8036 preg->translate = NULL;
8038 /* If REG_NEWLINE is set, newlines are treated differently. */
8039 if (cflags & REG_NEWLINE)
8040 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
8041 syntax &= ~RE_DOT_NEWLINE;
8042 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
8043 /* It also changes the matching behavior. */
8044 preg->newline_anchor = 1;
8047 preg->newline_anchor = 0;
8049 preg->no_sub = !!(cflags & REG_NOSUB);
8051 /* POSIX says a null character in the pattern terminates it, so we
8052 can use strlen here in compiling the pattern. */
8054 if (MB_CUR_MAX != 1)
8055 ret = wcs_regex_compile (pattern, strlen (pattern), syntax, preg);
8058 ret = byte_regex_compile (pattern, strlen (pattern), syntax, preg);
8060 /* POSIX doesn't distinguish between an unmatched open-group and an
8061 unmatched close-group: both are REG_EPAREN. */
8062 if (ret == REG_ERPAREN) ret = REG_EPAREN;
8064 if (ret == REG_NOERROR && preg->fastmap)
8066 /* Compute the fastmap now, since regexec cannot modify the pattern
8068 if (re_compile_fastmap (preg) == -2)
8070 /* Some error occurred while computing the fastmap, just forget
8072 free (preg->fastmap);
8073 preg->fastmap = NULL;
8080 weak_alias (__regcomp, regcomp)
8084 /* regexec searches for a given pattern, specified by PREG, in the
8087 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
8088 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
8089 least NMATCH elements, and we set them to the offsets of the
8090 corresponding matched substrings.
8092 EFLAGS specifies `execution flags' which affect matching: if
8093 REG_NOTBOL is set, then ^ does not match at the beginning of the
8094 string; if REG_NOTEOL is set, then $ does not match at the end.
8096 We return 0 if we find a match and REG_NOMATCH if not. */
8099 regexec (const regex_t *preg, const char *string,
8100 size_t nmatch, regmatch_t pmatch[], int eflags)
8103 struct re_registers regs;
8104 regex_t private_preg;
8105 int len = strlen (string);
8106 boolean want_reg_info = !preg->no_sub && nmatch > 0;
8108 private_preg = *preg;
8110 private_preg.not_bol = !!(eflags & REG_NOTBOL);
8111 private_preg.not_eol = !!(eflags & REG_NOTEOL);
8113 /* The user has told us exactly how many registers to return
8114 information about, via `nmatch'. We have to pass that on to the
8115 matching routines. */
8116 private_preg.regs_allocated = REGS_FIXED;
8120 regs.num_regs = nmatch;
8121 regs.start = TALLOC (nmatch * 2, regoff_t);
8122 if (regs.start == NULL)
8123 return (int) REG_NOMATCH;
8124 regs.end = regs.start + nmatch;
8127 /* Perform the searching operation. */
8128 ret = re_search (&private_preg, string, len,
8129 /* start: */ 0, /* range: */ len,
8130 want_reg_info ? ®s : 0);
8132 /* Copy the register information to the POSIX structure. */
8139 for (r = 0; r < nmatch; r++)
8141 pmatch[r].rm_so = regs.start[r];
8142 pmatch[r].rm_eo = regs.end[r];
8146 /* If we needed the temporary register info, free the space now. */
8150 /* We want zero return to mean success, unlike `re_search'. */
8151 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
8154 weak_alias (__regexec, regexec)
8158 /* Returns a message corresponding to an error code, ERRCODE, returned
8159 from either regcomp or regexec. We don't use PREG here. */
8162 regerror (int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
8168 || errcode >= (int) (sizeof (re_error_msgid_idx)
8169 / sizeof (re_error_msgid_idx[0])))
8170 /* Only error codes returned by the rest of the code should be passed
8171 to this routine. If we are given anything else, or if other regex
8172 code generates an invalid error code, then the program has a bug.
8173 Dump core so we can fix it. */
8176 msg = gettext (re_error_msgid + re_error_msgid_idx[errcode]);
8178 msg_size = strlen (msg) + 1; /* Includes the null. */
8180 if (errbuf_size != 0)
8182 if (msg_size > errbuf_size)
8184 #if defined HAVE_MEMPCPY || defined _LIBC
8185 *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
8187 memcpy (errbuf, msg, errbuf_size - 1);
8188 errbuf[errbuf_size - 1] = 0;
8192 memcpy (errbuf, msg, msg_size);
8198 weak_alias (__regerror, regerror)
8202 /* Free dynamically allocated space used by PREG. */
8205 regfree (regex_t *preg)
8207 if (preg->buffer != NULL)
8208 free (preg->buffer);
8209 preg->buffer = NULL;
8211 preg->allocated = 0;
8214 if (preg->fastmap != NULL)
8215 free (preg->fastmap);
8216 preg->fastmap = NULL;
8217 preg->fastmap_accurate = 0;
8219 if (preg->translate != NULL)
8220 free (preg->translate);
8221 preg->translate = NULL;
8224 weak_alias (__regfree, regfree)
8227 #endif /* not emacs */
8229 #endif /* not INSIDE_RECURSION */
8233 #undef STORE_NUMBER_AND_INCR
8234 #undef EXTRACT_NUMBER
8235 #undef EXTRACT_NUMBER_AND_INCR
8237 #undef DEBUG_PRINT_COMPILED_PATTERN
8238 #undef DEBUG_PRINT_DOUBLE_STRING
8240 #undef INIT_FAIL_STACK
8241 #undef RESET_FAIL_STACK
8242 #undef DOUBLE_FAIL_STACK
8243 #undef PUSH_PATTERN_OP
8244 #undef PUSH_FAILURE_POINTER
8245 #undef PUSH_FAILURE_INT
8246 #undef PUSH_FAILURE_ELT
8247 #undef POP_FAILURE_POINTER
8248 #undef POP_FAILURE_INT
8249 #undef POP_FAILURE_ELT
8252 #undef PUSH_FAILURE_POINT
8253 #undef POP_FAILURE_POINT
8255 #undef REG_UNSET_VALUE
8263 #undef INIT_BUF_SIZE
8264 #undef GET_BUFFER_SPACE
8272 #undef EXTEND_BUFFER
8273 #undef GET_UNSIGNED_NUMBER
8274 #undef FREE_STACK_RETURN
8276 # undef POINTER_TO_OFFSET
8277 # undef MATCHING_IN_FRST_STRING
8279 # undef AT_STRINGS_BEG
8280 # undef AT_STRINGS_END
8283 # undef FREE_VARIABLES
8284 # undef NO_HIGHEST_ACTIVE_REG
8285 # undef NO_LOWEST_ACTIVE_REG
8289 # undef COMPILED_BUFFER_VAR
8290 # undef OFFSET_ADDRESS_SIZE
8291 # undef CHAR_CLASS_SIZE
8298 # define DEFINED_ONCE