1 /* Extended regular expression matching and search library,
3 (Implements POSIX draft P1003.2/D11.2, except for some of the
4 internationalization features.)
5 Copyright (C) 1993-1999, 2000, 2001 Free Software Foundation, Inc.
6 This file is part of the GNU C Library.
8 The GNU C Library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU Lesser General Public
10 License as published by the Free Software Foundation; either
11 version 2.1 of the License, or (at your option) any later version.
13 The GNU C Library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public
19 License along with the GNU C Library; if not, see
20 <http://www.gnu.org/licenses/>. */
22 /* To exclude some unwanted junk.... */
25 /* unistd.h must be included with _LIBC defined: we need smallint */
30 # define _REGEX_RE_COMP
32 # define __RE_TRANSLATE_TYPE char *
33 # define RE_TRANSLATE_TYPE __RE_TRANSLATE_TYPE
39 /* AIX requires this to be the first thing in the file. */
40 #if defined _AIX && !defined REGEX_MALLOC
48 #ifndef INSIDE_RECURSION
50 # if defined STDC_HEADERS && !defined emacs
53 /* We need this for `regex.h', and perhaps for the Emacs include files. */
54 # include <sys/types.h>
58 /* For platform which support the ISO C amendement 1 functionality we
59 support user defined character classes. */
60 # if defined __UCLIBC_HAS_WCHAR__
61 # define WIDE_CHAR_SUPPORT 1
62 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
68 /* We have to keep the namespace clean. */
70 # define btowc __btowc
72 /* We are also using some library internals. */
73 # include <locale/localeinfo.h>
74 # include <locale/elem-hash.h>
75 # include <langinfo.h>
76 # include <locale/coll-lookup.h>
80 # define gettext(msgid) (msgid)
84 /* This define is so xgettext can find the internationalizable
86 # define gettext_noop(String) String
89 /* The `emacs' switch turns on certain matching commands
90 that make sense only in Emacs. */
97 # else /* not emacs */
99 /* If we are not linking with Emacs proper,
100 we can't use the relocating allocator
101 even if config.h says that we can. */
104 # if defined STDC_HEADERS || defined _LIBC
111 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
112 If nothing else has been done, use the method below. */
113 # ifdef INHIBIT_STRING_HEADER
114 # if !(defined HAVE_BZERO && defined HAVE_BCOPY)
115 # if !defined bzero && !defined bcopy
116 # undef INHIBIT_STRING_HEADER
121 /* This is the normal way of making sure we have a bcopy and a bzero.
122 This is used in most programs--a few other programs avoid this
123 by defining INHIBIT_STRING_HEADER. */
124 # ifndef INHIBIT_STRING_HEADER
125 # if defined HAVE_STRING_H || defined STDC_HEADERS || defined _LIBC
129 # define bzero(s, n) (memset (s, '\0', n), (s))
131 # define bzero(s, n) __bzero (s, n)
135 # include <strings.h>
137 # define memcmp(s1, s2, n) bcmp (s1, s2, n)
140 # define memcpy(d, s, n) (bcopy (s, d, n), (d))
145 /* Define the syntax stuff for \<, \>, etc. */
147 /* This must be nonzero for the wordchar and notwordchar pattern
148 commands in re_match_2. */
153 # ifdef SWITCH_ENUM_BUG
154 # define SWITCH_ENUM_CAST(x) ((int)(x))
156 # define SWITCH_ENUM_CAST(x) (x)
159 # endif /* not emacs */
161 # if defined _LIBC || defined HAVE_LIMITS_H
166 # define MB_LEN_MAX 1
169 /* Get the interface, including the syntax bits. */
171 # define translate __REPB_PREFIX(translate)
173 /* isalpha etc. are used for the character classes. */
176 /* Jim Meyering writes:
178 "... Some ctype macros are valid only for character codes that
179 isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
180 using /bin/cc or gcc but without giving an ansi option). So, all
181 ctype uses should be through macros like ISPRINT... If
182 STDC_HEADERS is defined, then autoconf has verified that the ctype
183 macros don't need to be guarded with references to isascii. ...
184 Defining isascii to 1 should let any compiler worth its salt
185 eliminate the && through constant folding."
186 Solaris defines some of these symbols so we must undefine them first. */
189 # if defined STDC_HEADERS || (!defined isascii && !defined HAVE_ISASCII)
190 # define ISASCII(c) 1
192 # define ISASCII(c) isascii(c)
196 # define ISBLANK(c) (ISASCII (c) && isblank (c))
198 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
201 # define ISGRAPH(c) (ISASCII (c) && isgraph (c))
203 # define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
207 # define ISPRINT(c) (ISASCII (c) && isprint (c))
208 # define ISDIGIT(c) (ISASCII (c) && isdigit (c))
209 # define ISALNUM(c) (ISASCII (c) && isalnum (c))
210 # define ISALPHA(c) (ISASCII (c) && isalpha (c))
211 # define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
212 # define ISLOWER(c) (ISASCII (c) && islower (c))
213 # define ISPUNCT(c) (ISASCII (c) && ispunct (c))
214 # define ISSPACE(c) (ISASCII (c) && isspace (c))
215 # define ISUPPER(c) (ISASCII (c) && isupper (c))
216 # define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
219 # define TOLOWER(c) _tolower(c)
221 # define TOLOWER(c) tolower(c)
225 # define NULL (void *)0
228 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
229 since ours (we hope) works properly with all combinations of
230 machines, compilers, `char' and `unsigned char' argument types.
231 (Per Bothner suggested the basic approach.) */
232 # undef SIGN_EXTEND_CHAR
234 # define SIGN_EXTEND_CHAR(c) ((signed char) (c))
235 # else /* not __STDC__ */
236 /* As in Harbison and Steele. */
237 # define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
241 /* How many characters in the character set. */
242 # define CHAR_SET_SIZE 256
246 extern char *re_syntax_table
;
248 # else /* not SYNTAX_TABLE */
250 static char re_syntax_table
[CHAR_SET_SIZE
];
252 static void init_syntax_once (void);
255 init_syntax_once (void)
258 static smallint done
= 0;
262 bzero (re_syntax_table
, sizeof re_syntax_table
);
264 for (c
= 0; c
< CHAR_SET_SIZE
; ++c
)
266 re_syntax_table
[c
] = Sword
;
268 re_syntax_table
['_'] = Sword
;
273 # endif /* not SYNTAX_TABLE */
275 # define SYNTAX(c) re_syntax_table[(unsigned char) (c)]
279 /* Integer type for pointers. */
280 # if !defined _LIBC && !defined __intptr_t_defined
281 typedef unsigned long int uintptr_t;
284 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
285 use `alloca' instead of `malloc'. This is because using malloc in
286 re_search* or re_match* could cause memory leaks when C-g is used in
287 Emacs; also, malloc is slower and causes storage fragmentation. On
288 the other hand, malloc is more portable, and easier to debug.
290 Because we sometimes use alloca, some routines have to be macros,
291 not functions -- `alloca'-allocated space disappears at the end of the
292 function it is called in. */
296 # define REGEX_ALLOCATE malloc
297 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
298 # define REGEX_FREE free
300 # else /* not REGEX_MALLOC */
302 /* Emacs already defines alloca, sometimes. */
305 /* Make alloca work the best possible way. */
307 # define alloca __builtin_alloca
308 # else /* not __GNUC__ */
311 # endif /* HAVE_ALLOCA_H */
312 # endif /* not __GNUC__ */
314 # endif /* not alloca */
316 # define REGEX_ALLOCATE alloca
318 /* Assumes a `char *destination' variable. */
319 # define REGEX_REALLOCATE(source, osize, nsize) \
320 (destination = (char *) alloca (nsize), \
321 memcpy (destination, source, osize))
323 /* No need to do anything to free, after alloca. */
324 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
326 # endif /* not REGEX_MALLOC */
328 /* Define how to allocate the failure stack. */
330 # if defined REL_ALLOC && defined REGEX_MALLOC
332 # define REGEX_ALLOCATE_STACK(size) \
333 r_alloc (&failure_stack_ptr, (size))
334 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
335 r_re_alloc (&failure_stack_ptr, (nsize))
336 # define REGEX_FREE_STACK(ptr) \
337 r_alloc_free (&failure_stack_ptr)
339 # else /* not using relocating allocator */
343 # define REGEX_ALLOCATE_STACK malloc
344 # define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
345 # define REGEX_FREE_STACK free
347 # else /* not REGEX_MALLOC */
349 # define REGEX_ALLOCATE_STACK alloca
351 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
352 REGEX_REALLOCATE (source, osize, nsize)
353 /* No need to explicitly free anything. */
354 # define REGEX_FREE_STACK(arg)
356 # endif /* not REGEX_MALLOC */
357 # endif /* not using relocating allocator */
360 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
361 `string1' or just past its end. This works if PTR is NULL, which is
363 # define FIRST_STRING_P(ptr) \
364 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
366 /* (Re)Allocate N items of type T using malloc, or fail. */
367 # define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
368 # define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
369 # define RETALLOC_IF(addr, n, t) \
370 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
371 # define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
373 # define BYTEWIDTH 8 /* In bits. */
375 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
379 # define MAX(a, b) ((a) > (b) ? (a) : (b))
380 # define MIN(a, b) ((a) < (b) ? (a) : (b))
382 typedef char boolean
;
386 static reg_errcode_t
byte_regex_compile (const char *pattern
, size_t size
,
388 struct re_pattern_buffer
*bufp
);
390 static int byte_re_match_2_internal (struct re_pattern_buffer
*bufp
,
391 const char *string1
, int size1
,
392 const char *string2
, int size2
,
394 struct re_registers
*regs
,
396 static int byte_re_search_2 (struct re_pattern_buffer
*bufp
,
397 const char *string1
, int size1
,
398 const char *string2
, int size2
,
399 int startpos
, int range
,
400 struct re_registers
*regs
, int stop
);
401 static int byte_re_compile_fastmap (struct re_pattern_buffer
*bufp
);
404 static reg_errcode_t
wcs_regex_compile (const char *pattern
, size_t size
,
406 struct re_pattern_buffer
*bufp
);
409 static int wcs_re_match_2_internal (struct re_pattern_buffer
*bufp
,
410 const char *cstring1
, int csize1
,
411 const char *cstring2
, int csize2
,
413 struct re_registers
*regs
,
415 wchar_t *string1
, int size1
,
416 wchar_t *string2
, int size2
,
417 int *mbs_offset1
, int *mbs_offset2
);
418 static int wcs_re_search_2 (struct re_pattern_buffer
*bufp
,
419 const char *string1
, int size1
,
420 const char *string2
, int size2
,
421 int startpos
, int range
,
422 struct re_registers
*regs
, int stop
);
423 static int wcs_re_compile_fastmap (struct re_pattern_buffer
*bufp
);
426 /* These are the command codes that appear in compiled regular
427 expressions. Some opcodes are followed by argument bytes. A
428 command code can specify any interpretation whatsoever for its
429 arguments. Zero bytes may appear in the compiled regular expression. */
435 /* Succeed right away--no more backtracking. */
438 /* Followed by one byte giving n, then by n literal bytes. */
442 /* Same as exactn, but contains binary data. */
446 /* Matches any (more or less) character. */
449 /* Matches any one char belonging to specified set. First
450 following byte is number of bitmap bytes. Then come bytes
451 for a bitmap saying which chars are in. Bits in each byte
452 are ordered low-bit-first. A character is in the set if its
453 bit is 1. A character too large to have a bit in the map is
454 automatically not in the set. */
455 /* ifdef MBS_SUPPORT, following element is length of character
456 classes, length of collating symbols, length of equivalence
457 classes, length of character ranges, and length of characters.
458 Next, character class element, collating symbols elements,
459 equivalence class elements, range elements, and character
461 See regex_compile function. */
464 /* Same parameters as charset, but match any character that is
465 not one of those specified. */
468 /* Start remembering the text that is matched, for storing in a
469 register. Followed by one byte with the register number, in
470 the range 0 to one less than the pattern buffer's re_nsub
471 field. Then followed by one byte with the number of groups
472 inner to this one. (This last has to be part of the
473 start_memory only because we need it in the on_failure_jump
477 /* Stop remembering the text that is matched and store it in a
478 memory register. Followed by one byte with the register
479 number, in the range 0 to one less than `re_nsub' in the
480 pattern buffer, and one byte with the number of inner groups,
481 just like `start_memory'. (We need the number of inner
482 groups here because we don't have any easy way of finding the
483 corresponding start_memory when we're at a stop_memory.) */
486 /* Match a duplicate of something remembered. Followed by one
487 byte containing the register number. */
490 /* Fail unless at beginning of line. */
493 /* Fail unless at end of line. */
496 /* Succeeds if at beginning of buffer (if emacs) or at beginning
497 of string to be matched (if not). */
500 /* Analogously, for end of buffer/string. */
503 /* Followed by two byte relative address to which to jump. */
506 /* Same as jump, but marks the end of an alternative. */
509 /* Followed by two-byte relative address of place to resume at
510 in case of failure. */
511 /* ifdef MBS_SUPPORT, the size of address is 1. */
514 /* Like on_failure_jump, but pushes a placeholder instead of the
515 current string position when executed. */
516 on_failure_keep_string_jump
,
518 /* Throw away latest failure point and then jump to following
519 two-byte relative address. */
520 /* ifdef MBS_SUPPORT, the size of address is 1. */
523 /* Change to pop_failure_jump if know won't have to backtrack to
524 match; otherwise change to jump. This is used to jump
525 back to the beginning of a repeat. If what follows this jump
526 clearly won't match what the repeat does, such that we can be
527 sure that there is no use backtracking out of repetitions
528 already matched, then we change it to a pop_failure_jump.
529 Followed by two-byte address. */
530 /* ifdef MBS_SUPPORT, the size of address is 1. */
533 /* Jump to following two-byte address, and push a dummy failure
534 point. This failure point will be thrown away if an attempt
535 is made to use it for a failure. A `+' construct makes this
536 before the first repeat. Also used as an intermediary kind
537 of jump when compiling an alternative. */
538 /* ifdef MBS_SUPPORT, the size of address is 1. */
541 /* Push a dummy failure point and continue. Used at the end of
545 /* Followed by two-byte relative address and two-byte number n.
546 After matching N times, jump to the address upon failure. */
547 /* ifdef MBS_SUPPORT, the size of address is 1. */
550 /* Followed by two-byte relative address, and two-byte number n.
551 Jump to the address N times, then fail. */
552 /* ifdef MBS_SUPPORT, the size of address is 1. */
555 /* Set the following two-byte relative address to the
556 subsequent two-byte number. The address *includes* the two
558 /* ifdef MBS_SUPPORT, the size of address is 1. */
561 wordchar
, /* Matches any word-constituent character. */
562 notwordchar
, /* Matches any char that is not a word-constituent. */
564 wordbeg
, /* Succeeds if at word beginning. */
565 wordend
, /* Succeeds if at word end. */
567 wordbound
, /* Succeeds if at a word boundary. */
568 notwordbound
/* Succeeds if not at a word boundary. */
571 ,before_dot
, /* Succeeds if before point. */
572 at_dot
, /* Succeeds if at point. */
573 after_dot
, /* Succeeds if after point. */
575 /* Matches any character whose syntax is specified. Followed by
576 a byte which contains a syntax code, e.g., Sword. */
579 /* Matches any character whose syntax is not that specified. */
583 #endif /* not INSIDE_RECURSION */
588 # define UCHAR_T unsigned char
589 # define COMPILED_BUFFER_VAR bufp->buffer
590 # define OFFSET_ADDRESS_SIZE 2
591 # define PREFIX(name) byte_##name
592 # define ARG_PREFIX(name) name
593 # define PUT_CHAR(c) putchar (c)
596 # define CHAR_T wchar_t
597 # define UCHAR_T wchar_t
598 # define COMPILED_BUFFER_VAR wc_buffer
599 # define OFFSET_ADDRESS_SIZE 1 /* the size which STORE_NUMBER macro use */
600 # define CHAR_CLASS_SIZE ((__alignof__(wctype_t)+sizeof(wctype_t))/sizeof(CHAR_T)+1)
601 # define PREFIX(name) wcs_##name
602 # define ARG_PREFIX(name) c##name
603 /* Should we use wide stream?? */
604 # define PUT_CHAR(c) printf ("%C", c);
610 # define INSIDE_RECURSION
611 # include "regex_old.c"
612 # undef INSIDE_RECURSION
615 # define INSIDE_RECURSION
616 # include "regex_old.c"
617 # undef INSIDE_RECURSION
621 #ifdef INSIDE_RECURSION
622 /* Common operations on the compiled pattern. */
624 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
625 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
628 # define STORE_NUMBER(destination, number) \
630 *(destination) = (UCHAR_T)(number); \
633 # define STORE_NUMBER(destination, number) \
635 (destination)[0] = (number) & 0377; \
636 (destination)[1] = (number) >> 8; \
640 /* Same as STORE_NUMBER, except increment DESTINATION to
641 the byte after where the number is stored. Therefore, DESTINATION
642 must be an lvalue. */
643 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
645 # define STORE_NUMBER_AND_INCR(destination, number) \
647 STORE_NUMBER (destination, number); \
648 (destination) += OFFSET_ADDRESS_SIZE; \
651 /* Put into DESTINATION a number stored in two contiguous bytes starting
653 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
656 # define EXTRACT_NUMBER(destination, source) \
658 (destination) = *(source); \
661 # define EXTRACT_NUMBER(destination, source) \
663 (destination) = *(source) & 0377; \
664 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \
669 static void PREFIX(extract_number
) (int *dest
, UCHAR_T
*source
)
674 int temp
= SIGN_EXTEND_CHAR (*(source
+ 1));
675 *dest
= *source
& 0377;
680 # ifndef EXTRACT_MACROS /* To debug the macros. */
681 # undef EXTRACT_NUMBER
682 # define EXTRACT_NUMBER(dest, src) PREFIX(extract_number) (&dest, src)
683 # endif /* not EXTRACT_MACROS */
687 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
688 SOURCE must be an lvalue. */
690 # define EXTRACT_NUMBER_AND_INCR(destination, source) \
692 EXTRACT_NUMBER (destination, source); \
693 (source) += OFFSET_ADDRESS_SIZE; \
697 static void PREFIX(extract_number_and_incr
) (int *destination
,
700 PREFIX(extract_number
) (destination
, *source
);
701 *source
+= OFFSET_ADDRESS_SIZE
;
704 # ifndef EXTRACT_MACROS
705 # undef EXTRACT_NUMBER_AND_INCR
706 # define EXTRACT_NUMBER_AND_INCR(dest, src) \
707 PREFIX(extract_number_and_incr) (&dest, &src)
708 # endif /* not EXTRACT_MACROS */
714 /* If DEBUG is defined, Regex prints many voluminous messages about what
715 it is doing (if the variable `debug' is nonzero). If linked with the
716 main program in `iregex.c', you can enter patterns and strings
717 interactively. And if linked with the main program in `main.c' and
718 the other test files, you can run the already-written tests. */
722 # ifndef DEFINED_ONCE
724 /* We use standard I/O for debugging. */
727 /* It is useful to test things that ``must'' be true when debugging. */
730 static smallint debug
;
732 # define DEBUG_STATEMENT(e) e
733 # define DEBUG_PRINT1(x) if (debug) printf (x)
734 # define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
735 # define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
736 # define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
737 # endif /* not DEFINED_ONCE */
739 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
740 if (debug) PREFIX(print_partial_compiled_pattern) (s, e)
741 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
742 if (debug) PREFIX(print_double_string) (w, s1, sz1, s2, sz2)
745 /* Print the fastmap in human-readable form. */
747 # ifndef DEFINED_ONCE
749 print_fastmap (char *fastmap
)
751 unsigned was_a_range
= 0;
754 while (i
< (1 << BYTEWIDTH
))
760 while (i
< (1 << BYTEWIDTH
) && fastmap
[i
])
774 # endif /* not DEFINED_ONCE */
777 /* Print a compiled pattern string in human-readable form, starting at
778 the START pointer into it and ending just before the pointer END. */
781 PREFIX(print_partial_compiled_pattern
) (UCHAR_T
*start
, UCHAR_T
*end
)
794 /* Loop over pattern commands. */
798 printf ("%td:\t", p
- start
);
800 printf ("%ld:\t", (long int) (p
- start
));
803 switch ((re_opcode_t
) *p
++)
811 printf ("/exactn/%d", mcnt
);
823 printf ("/exactn_bin/%d", mcnt
);
826 printf("/%lx", (long int) *p
++);
830 # endif /* MBS_SUPPORT */
834 printf ("/start_memory/%d/%ld", mcnt
, (long int) *p
++);
839 printf ("/stop_memory/%d/%ld", mcnt
, (long int) *p
++);
843 printf ("/duplicate/%ld", (long int) *p
++);
856 printf ("/charset [%s",
857 (re_opcode_t
) *(workp
- 1) == charset_not
? "^" : "");
859 length
= *workp
++; /* the length of char_classes */
860 for (i
=0 ; i
<length
; i
++)
861 printf("[:%lx:]", (long int) *p
++);
862 length
= *workp
++; /* the length of collating_symbol */
863 for (i
=0 ; i
<length
;)
867 PUT_CHAR((i
++,*p
++));
871 length
= *workp
++; /* the length of equivalence_class */
872 for (i
=0 ; i
<length
;)
876 PUT_CHAR((i
++,*p
++));
880 length
= *workp
++; /* the length of char_range */
881 for (i
=0 ; i
<length
; i
++)
883 wchar_t range_start
= *p
++;
884 wchar_t range_end
= *p
++;
885 printf("%C-%C", range_start
, range_end
);
887 length
= *workp
++; /* the length of char */
888 for (i
=0 ; i
<length
; i
++)
892 register int c
, last
= -100;
893 register int in_range
= 0;
895 printf ("/charset [%s",
896 (re_opcode_t
) *(p
- 1) == charset_not
? "^" : "");
898 assert (p
+ *p
< pend
);
900 for (c
= 0; c
< 256; c
++)
902 && (p
[1 + (c
/8)] & (1 << (c
% 8))))
904 /* Are we starting a range? */
905 if (last
+ 1 == c
&& ! in_range
)
910 /* Have we broken a range? */
911 else if (last
+ 1 != c
&& in_range
)
941 case on_failure_jump
:
942 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
944 printf ("/on_failure_jump to %td", p
+ mcnt
- start
);
946 printf ("/on_failure_jump to %ld", (long int) (p
+ mcnt
- start
));
950 case on_failure_keep_string_jump
:
951 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
953 printf ("/on_failure_keep_string_jump to %td", p
+ mcnt
- start
);
955 printf ("/on_failure_keep_string_jump to %ld",
956 (long int) (p
+ mcnt
- start
));
960 case dummy_failure_jump
:
961 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
963 printf ("/dummy_failure_jump to %td", p
+ mcnt
- start
);
965 printf ("/dummy_failure_jump to %ld", (long int) (p
+ mcnt
- start
));
969 case push_dummy_failure
:
970 printf ("/push_dummy_failure");
974 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
976 printf ("/maybe_pop_jump to %td", p
+ mcnt
- start
);
978 printf ("/maybe_pop_jump to %ld", (long int) (p
+ mcnt
- start
));
982 case pop_failure_jump
:
983 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
985 printf ("/pop_failure_jump to %td", p
+ mcnt
- start
);
987 printf ("/pop_failure_jump to %ld", (long int) (p
+ mcnt
- start
));
992 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
994 printf ("/jump_past_alt to %td", p
+ mcnt
- start
);
996 printf ("/jump_past_alt to %ld", (long int) (p
+ mcnt
- start
));
1001 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
1003 printf ("/jump to %td", p
+ mcnt
- start
);
1005 printf ("/jump to %ld", (long int) (p
+ mcnt
- start
));
1010 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
1012 PREFIX(extract_number_and_incr
) (&mcnt2
, &p
);
1014 printf ("/succeed_n to %td, %d times", p1
- start
, mcnt2
);
1016 printf ("/succeed_n to %ld, %d times",
1017 (long int) (p1
- start
), mcnt2
);
1022 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
1024 PREFIX(extract_number_and_incr
) (&mcnt2
, &p
);
1025 printf ("/jump_n to %d, %d times", p1
- start
, mcnt2
);
1029 PREFIX(extract_number_and_incr
) (&mcnt
, &p
);
1031 PREFIX(extract_number_and_incr
) (&mcnt2
, &p
);
1033 printf ("/set_number_at location %td to %d", p1
- start
, mcnt2
);
1035 printf ("/set_number_at location %ld to %d",
1036 (long int) (p1
- start
), mcnt2
);
1041 printf ("/wordbound");
1045 printf ("/notwordbound");
1049 printf ("/wordbeg");
1053 printf ("/wordend");
1058 printf ("/before_dot");
1066 printf ("/after_dot");
1070 printf ("/syntaxspec");
1072 printf ("/%d", mcnt
);
1076 printf ("/notsyntaxspec");
1078 printf ("/%d", mcnt
);
1083 printf ("/wordchar");
1087 printf ("/notwordchar");
1099 printf ("?%ld", (long int) *(p
-1));
1106 printf ("%td:\tend of pattern.\n", p
- start
);
1108 printf ("%ld:\tend of pattern.\n", (long int) (p
- start
));
1114 PREFIX(print_compiled_pattern
) (struct re_pattern_buffer
*bufp
)
1116 UCHAR_T
*buffer
= (UCHAR_T
*) bufp
->buffer
;
1118 PREFIX(print_partial_compiled_pattern
) (buffer
, buffer
1119 + bufp
->used
/ sizeof(UCHAR_T
));
1120 printf ("%ld bytes used/%ld bytes allocated.\n",
1121 bufp
->used
, bufp
->allocated
);
1123 if (bufp
->fastmap_accurate
&& bufp
->fastmap
)
1125 printf ("fastmap: ");
1126 print_fastmap (bufp
->fastmap
);
1130 printf ("re_nsub: %Zd\t", bufp
->re_nsub
);
1132 printf ("re_nsub: %ld\t", (long int) bufp
->re_nsub
);
1134 printf ("regs_alloc: %d\t", bufp
->regs_allocated
);
1135 printf ("can_be_null: %d\t", bufp
->can_be_null
);
1136 printf ("newline_anchor: %d\n", bufp
->newline_anchor
);
1137 printf ("no_sub: %d\t", bufp
->no_sub
);
1138 printf ("not_bol: %d\t", bufp
->not_bol
);
1139 printf ("not_eol: %d\t", bufp
->not_eol
);
1140 printf ("syntax: %lx\n", bufp
->syntax
);
1141 /* Perhaps we should print the translate table? */
1146 PREFIX(print_double_string
) (
1147 const CHAR_T
*where
,
1148 const CHAR_T
*string1
,
1150 const CHAR_T
*string2
,
1161 if (FIRST_STRING_P (where
))
1163 for (this_char
= where
- string1
; this_char
< size1
; this_char
++)
1164 PUT_CHAR (string1
[this_char
]);
1170 for (this_char
= where
- string2
; this_char
< size2
; this_char
++)
1172 PUT_CHAR (string2
[this_char
]);
1175 fputs ("...", stdout
);
1182 # if 0 /* ndef DEFINED_ONCE */
1190 # else /* not DEBUG */
1192 # ifndef DEFINED_ONCE
1196 # define DEBUG_STATEMENT(e)
1197 # define DEBUG_PRINT1(x)
1198 # define DEBUG_PRINT2(x1, x2)
1199 # define DEBUG_PRINT3(x1, x2, x3)
1200 # define DEBUG_PRINT4(x1, x2, x3, x4)
1201 # endif /* not DEFINED_ONCE */
1202 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1203 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1205 # endif /* not DEBUG */
1210 /* This convert a multibyte string to a wide character string.
1211 And write their correspondances to offset_buffer(see below)
1212 and write whether each wchar_t is binary data to is_binary.
1213 This assume invalid multibyte sequences as binary data.
1214 We assume offset_buffer and is_binary is already allocated
1218 convert_mbs_to_wcs (
1220 const unsigned char* src
,
1221 size_t len
, /* the length of multibyte string. */
1223 /* It hold correspondances between src(char string) and
1224 dest(wchar_t string) for optimization.
1226 dest = {'X', 'Y', 'Z'}
1227 (each "xxx", "y" and "zz" represent one multibyte character
1228 corresponding to 'X', 'Y' and 'Z'.)
1229 offset_buffer = {0, 0+3("xxx"), 0+3+1("y"), 0+3+1+2("zz")}
1235 wchar_t *pdest
= dest
;
1236 const unsigned char *psrc
= src
;
1237 size_t wc_count
= 0;
1241 size_t mb_remain
= len
;
1242 size_t mb_count
= 0;
1244 /* Initialize the conversion state. */
1245 memset (&mbs
, 0, sizeof (mbstate_t));
1247 offset_buffer
[0] = 0;
1248 for( ; mb_remain
> 0 ; ++wc_count
, ++pdest
, mb_remain
-= consumed
,
1252 consumed
= __mbrtowc (pdest
, psrc
, mb_remain
, &mbs
);
1254 consumed
= mbrtowc (pdest
, psrc
, mb_remain
, &mbs
);
1258 /* failed to convert. maybe src contains binary data.
1259 So we consume 1 byte manualy. */
1263 is_binary
[wc_count
] = TRUE
;
1266 is_binary
[wc_count
] = FALSE
;
1267 /* In sjis encoding, we use yen sign as escape character in
1268 place of reverse solidus. So we convert 0x5c(yen sign in
1269 sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1270 solidus in UCS2). */
1271 if (consumed
== 1 && (int) *psrc
== 0x5c && (int) *pdest
== 0xa5)
1272 *pdest
= (wchar_t) *psrc
;
1274 offset_buffer
[wc_count
+ 1] = mb_count
+= consumed
;
1277 /* Fill remain of the buffer with sentinel. */
1278 for (i
= wc_count
+ 1 ; i
<= len
; i
++)
1279 offset_buffer
[i
] = mb_count
+ 1;
1286 #else /* not INSIDE_RECURSION */
1288 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1289 also be assigned to arbitrarily: each pattern buffer stores its own
1290 syntax, so it can be changed between regex compilations. */
1291 /* This has no initializer because initialized variables in Emacs
1292 become read-only after dumping. */
1293 reg_syntax_t re_syntax_options
;
1296 /* Specify the precise syntax of regexps for compilation. This provides
1297 for compatibility for various utilities which historically have
1298 different, incompatible syntaxes.
1300 The argument SYNTAX is a bit mask comprised of the various bits
1301 defined in regex.h. We return the old syntax. */
1304 re_set_syntax (reg_syntax_t syntax
)
1306 reg_syntax_t ret
= re_syntax_options
;
1308 re_syntax_options
= syntax
;
1310 if (syntax
& RE_DEBUG
)
1312 else if (debug
) /* was on but now is not */
1318 /* This table gives an error message for each of the error codes listed
1319 in regex.h. Obviously the order here has to be same as there.
1320 POSIX doesn't require that we do anything for REG_NOERROR,
1321 but why not be nice? */
1323 static const char re_error_msgid
[] =
1325 # define REG_NOERROR_IDX 0
1326 gettext_noop ("Success") /* REG_NOERROR */
1328 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1329 gettext_noop ("No match") /* REG_NOMATCH */
1331 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1332 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1334 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1335 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1337 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1338 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1340 # define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1341 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1343 # define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1344 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1346 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1347 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
1349 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1350 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1352 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1353 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1355 # define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1356 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1358 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1359 gettext_noop ("Invalid range end") /* REG_ERANGE */
1361 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1362 gettext_noop ("Memory exhausted") /* REG_ESPACE */
1364 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1365 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1367 # define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1368 gettext_noop ("Premature end of regular expression") /* REG_EEND */
1370 # define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
1371 gettext_noop ("Regular expression too big") /* REG_ESIZE */
1373 # define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
1374 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1377 static const uint16_t re_error_msgid_idx
[] =
1398 #endif /* INSIDE_RECURSION */
1400 #ifndef DEFINED_ONCE
1401 /* Avoiding alloca during matching, to placate r_alloc. */
1403 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1404 searching and matching functions should not call alloca. On some
1405 systems, alloca is implemented in terms of malloc, and if we're
1406 using the relocating allocator routines, then malloc could cause a
1407 relocation, which might (if the strings being searched are in the
1408 ralloc heap) shift the data out from underneath the regexp
1411 Here's another reason to avoid allocation: Emacs
1412 processes input from X in a signal handler; processing X input may
1413 call malloc; if input arrives while a matching routine is calling
1414 malloc, then we're scrod. But Emacs can't just block input while
1415 calling matching routines; then we don't notice interrupts when
1416 they come in. So, Emacs blocks input around all regexp calls
1417 except the matching calls, which it leaves unprotected, in the
1418 faith that they will not malloc. */
1420 /* Normally, this is fine. */
1421 # define MATCH_MAY_ALLOCATE
1423 /* When using GNU C, we are not REALLY using the C alloca, no matter
1424 what config.h may say. So don't take precautions for it. */
1429 /* The match routines may not allocate if (1) they would do it with malloc
1430 and (2) it's not safe for them to use malloc.
1431 Note that if REL_ALLOC is defined, matching would not use malloc for the
1432 failure stack, but we would still use it for the register vectors;
1433 so REL_ALLOC should not affect this. */
1434 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1435 # undef MATCH_MAY_ALLOCATE
1437 #endif /* not DEFINED_ONCE */
1439 #ifdef INSIDE_RECURSION
1440 /* Failure stack declarations and macros; both re_compile_fastmap and
1441 re_match_2 use a failure stack. These have to be macros because of
1442 REGEX_ALLOCATE_STACK. */
1445 /* Number of failure points for which to initially allocate space
1446 when matching. If this number is exceeded, we allocate more
1447 space, so it is not a hard limit. */
1448 # ifndef INIT_FAILURE_ALLOC
1449 # define INIT_FAILURE_ALLOC 5
1452 /* Roughly the maximum number of failure points on the stack. Would be
1453 exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1454 This is a variable only so users of regex can assign to it; we never
1455 change it ourselves. */
1457 # ifdef 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 long int re_max_failures
= 4000;
1465 long 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
;
1480 unsigned long int size
;
1481 unsigned long int avail
; /* Offset of next open position. */
1482 } PREFIX(fail_stack_type
);
1484 # else /* not INT_IS_16BIT */
1486 # ifndef DEFINED_ONCE
1487 # if defined MATCH_MAY_ALLOCATE
1488 /* 4400 was enough to cause a crash on Alpha OSF/1,
1489 whose default stack limit is 2mb. */
1490 int re_max_failures
= 4000;
1492 int re_max_failures
= 2000;
1496 union PREFIX(fail_stack_elt
)
1502 typedef union PREFIX(fail_stack_elt
) PREFIX(fail_stack_elt_t
);
1506 PREFIX(fail_stack_elt_t
) *stack
;
1508 unsigned avail
; /* Offset of next open position. */
1509 } PREFIX(fail_stack_type
);
1511 # endif /* INT_IS_16BIT */
1513 # ifndef DEFINED_ONCE
1514 # define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
1515 # define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1516 # define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
1520 /* Define macros to initialize and free the failure stack.
1521 Do `return -2' if the alloc fails. */
1523 # ifdef MATCH_MAY_ALLOCATE
1524 # define INIT_FAIL_STACK() \
1526 fail_stack.stack = (PREFIX(fail_stack_elt_t) *) \
1527 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1529 if (fail_stack.stack == NULL) \
1532 fail_stack.size = INIT_FAILURE_ALLOC; \
1533 fail_stack.avail = 0; \
1536 # define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack)
1538 # define INIT_FAIL_STACK() \
1540 fail_stack.avail = 0; \
1543 # define RESET_FAIL_STACK()
1547 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1549 Return 1 if succeeds, and 0 if either ran out of memory
1550 allocating space for it or it was already too large.
1552 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1554 # define DOUBLE_FAIL_STACK(fail_stack) \
1555 ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1557 : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *) \
1558 REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1559 (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)), \
1560 ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1562 (fail_stack).stack == NULL \
1564 : ((fail_stack).size <<= 1, \
1568 /* Push pointer POINTER on FAIL_STACK.
1569 Return 1 if was able to do so and 0 if ran out of memory allocating
1571 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK) \
1572 ((FAIL_STACK_FULL () \
1573 && !DOUBLE_FAIL_STACK (FAIL_STACK)) \
1575 : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER, \
1578 /* Push a pointer value onto the failure stack.
1579 Assumes the variable `fail_stack'. Probably should only
1580 be called from within `PUSH_FAILURE_POINT'. */
1581 # define PUSH_FAILURE_POINTER(item) \
1582 fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1584 /* This pushes an integer-valued item onto the failure stack.
1585 Assumes the variable `fail_stack'. Probably should only
1586 be called from within `PUSH_FAILURE_POINT'. */
1587 # define PUSH_FAILURE_INT(item) \
1588 fail_stack.stack[fail_stack.avail++].integer = (item)
1590 /* Push a fail_stack_elt_t value onto the failure stack.
1591 Assumes the variable `fail_stack'. Probably should only
1592 be called from within `PUSH_FAILURE_POINT'. */
1593 # define PUSH_FAILURE_ELT(item) \
1594 fail_stack.stack[fail_stack.avail++] = (item)
1596 /* These three POP... operations complement the three PUSH... operations.
1597 All assume that `fail_stack' is nonempty. */
1598 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1599 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1600 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1602 /* Used to omit pushing failure point id's when we're not debugging. */
1604 # define DEBUG_PUSH PUSH_FAILURE_INT
1605 # define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1607 # define DEBUG_PUSH(item)
1608 # define DEBUG_POP(item_addr)
1612 /* Push the information about the state we will need
1613 if we ever fail back to it.
1615 Requires variables fail_stack, regstart, regend, reg_info, and
1616 num_regs_pushed be declared. DOUBLE_FAIL_STACK requires `destination'
1619 Does `return FAILURE_CODE' if runs out of memory. */
1621 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
1623 char *destination; \
1624 /* Must be int, so when we don't save any registers, the arithmetic \
1625 of 0 + -1 isn't done as unsigned. */ \
1626 /* Can't be int, since there is not a shred of a guarantee that int \
1627 is wide enough to hold a value of something to which pointer can \
1629 active_reg_t this_reg; \
1631 DEBUG_STATEMENT (failure_id++); \
1632 DEBUG_STATEMENT (nfailure_points_pushed++); \
1633 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
1634 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
1635 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
1637 DEBUG_PRINT2 (" slots needed: %ld\n", NUM_FAILURE_ITEMS); \
1638 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
1640 /* Ensure we have enough space allocated for what we will push. */ \
1641 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
1643 if (!DOUBLE_FAIL_STACK (fail_stack)) \
1644 return failure_code; \
1646 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
1647 (fail_stack).size); \
1648 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1651 /* Push the info, starting with the registers. */ \
1652 DEBUG_PRINT1 ("\n"); \
1655 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1658 DEBUG_PRINT2 (" Pushing reg: %lu\n", this_reg); \
1659 DEBUG_STATEMENT (num_regs_pushed++); \
1661 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1662 PUSH_FAILURE_POINTER (regstart[this_reg]); \
1664 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1665 PUSH_FAILURE_POINTER (regend[this_reg]); \
1667 DEBUG_PRINT2 (" info: %p\n ", \
1668 reg_info[this_reg].word.pointer); \
1669 DEBUG_PRINT2 (" match_null=%d", \
1670 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
1671 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
1672 DEBUG_PRINT2 (" matched_something=%d", \
1673 MATCHED_SOMETHING (reg_info[this_reg])); \
1674 DEBUG_PRINT2 (" ever_matched=%d", \
1675 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
1676 DEBUG_PRINT1 ("\n"); \
1677 PUSH_FAILURE_ELT (reg_info[this_reg].word); \
1680 DEBUG_PRINT2 (" Pushing low active reg: %ld\n", lowest_active_reg);\
1681 PUSH_FAILURE_INT (lowest_active_reg); \
1683 DEBUG_PRINT2 (" Pushing high active reg: %ld\n", highest_active_reg);\
1684 PUSH_FAILURE_INT (highest_active_reg); \
1686 DEBUG_PRINT2 (" Pushing pattern %p:\n", pattern_place); \
1687 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
1688 PUSH_FAILURE_POINTER (pattern_place); \
1690 DEBUG_PRINT2 (" Pushing string %p: `", string_place); \
1691 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
1693 DEBUG_PRINT1 ("'\n"); \
1694 PUSH_FAILURE_POINTER (string_place); \
1696 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
1697 DEBUG_PUSH (failure_id); \
1700 # ifndef DEFINED_ONCE
1701 /* This is the number of items that are pushed and popped on the stack
1702 for each register. */
1703 # define NUM_REG_ITEMS 3
1705 /* Individual items aside from the registers. */
1707 # define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
1709 # define NUM_NONREG_ITEMS 4
1712 /* We push at most this many items on the stack. */
1713 /* We used to use (num_regs - 1), which is the number of registers
1714 this regexp will save; but that was changed to 5
1715 to avoid stack overflow for a regexp with lots of parens. */
1716 # define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1718 /* We actually push this many items. */
1719 # define NUM_FAILURE_ITEMS \
1721 ? 0 : highest_active_reg - lowest_active_reg + 1) \
1725 /* How many items can still be added to the stack without overflowing it. */
1726 # define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1727 # endif /* not DEFINED_ONCE */
1730 /* Pops what PUSH_FAIL_STACK pushes.
1732 We restore into the parameters, all of which should be lvalues:
1733 STR -- the saved data position.
1734 PAT -- the saved pattern position.
1735 LOW_REG, HIGH_REG -- the highest and lowest active registers.
1736 REGSTART, REGEND -- arrays of string positions.
1737 REG_INFO -- array of information about each subexpression.
1739 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1740 `pend', `string1', `size1', `string2', and `size2'. */
1741 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1743 DEBUG_STATEMENT (unsigned failure_id;) \
1744 active_reg_t this_reg; \
1745 const UCHAR_T *string_temp; \
1747 assert (!FAIL_STACK_EMPTY ()); \
1749 /* Remove failure points and point to how many regs pushed. */ \
1750 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
1751 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
1752 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
1754 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
1756 DEBUG_POP (&failure_id); \
1757 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
1759 /* If the saved string location is NULL, it came from an \
1760 on_failure_keep_string_jump opcode, and we want to throw away the \
1761 saved NULL, thus retaining our current position in the string. */ \
1762 string_temp = POP_FAILURE_POINTER (); \
1763 if (string_temp != NULL) \
1764 str = (const CHAR_T *) string_temp; \
1766 DEBUG_PRINT2 (" Popping string %p: `", str); \
1767 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1768 DEBUG_PRINT1 ("'\n"); \
1770 pat = (UCHAR_T *) POP_FAILURE_POINTER (); \
1771 DEBUG_PRINT2 (" Popping pattern %p:\n", pat); \
1772 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1774 /* Restore register info. */ \
1775 high_reg = (active_reg_t) POP_FAILURE_INT (); \
1776 DEBUG_PRINT2 (" Popping high active reg: %ld\n", high_reg); \
1778 low_reg = (active_reg_t) POP_FAILURE_INT (); \
1779 DEBUG_PRINT2 (" Popping low active reg: %ld\n", low_reg); \
1782 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
1784 DEBUG_PRINT2 (" Popping reg: %ld\n", this_reg); \
1786 reg_info[this_reg].word = POP_FAILURE_ELT (); \
1787 DEBUG_PRINT2 (" info: %p\n", \
1788 reg_info[this_reg].word.pointer); \
1790 regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1791 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1793 regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1794 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1798 for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1800 reg_info[this_reg].word.integer = 0; \
1801 regend[this_reg] = 0; \
1802 regstart[this_reg] = 0; \
1804 highest_active_reg = high_reg; \
1807 set_regs_matched_done = 0; \
1808 DEBUG_STATEMENT (nfailure_points_popped++); \
1809 } /* POP_FAILURE_POINT */
1811 /* Structure for per-register (a.k.a. per-group) information.
1812 Other register information, such as the
1813 starting and ending positions (which are addresses), and the list of
1814 inner groups (which is a bits list) are maintained in separate
1817 We are making a (strictly speaking) nonportable assumption here: that
1818 the compiler will pack our bit fields into something that fits into
1819 the type of `word', i.e., is something that fits into one item on the
1823 /* Declarations and macros for re_match_2. */
1827 PREFIX(fail_stack_elt_t
) word
;
1830 /* This field is one if this group can match the empty string,
1831 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
1832 # define MATCH_NULL_UNSET_VALUE 3
1833 unsigned match_null_string_p
: 2;
1834 unsigned is_active
: 1;
1835 unsigned matched_something
: 1;
1836 unsigned ever_matched_something
: 1;
1838 } PREFIX(register_info_type
);
1840 # ifndef DEFINED_ONCE
1841 # define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
1842 # define IS_ACTIVE(R) ((R).bits.is_active)
1843 # define MATCHED_SOMETHING(R) ((R).bits.matched_something)
1844 # define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
1847 /* Call this when have matched a real character; it sets `matched' flags
1848 for the subexpressions which we are currently inside. Also records
1849 that those subexprs have matched. */
1850 # define SET_REGS_MATCHED() \
1853 if (!set_regs_matched_done) \
1856 set_regs_matched_done = 1; \
1857 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
1859 MATCHED_SOMETHING (reg_info[r]) \
1860 = EVER_MATCHED_SOMETHING (reg_info[r]) \
1866 # endif /* not DEFINED_ONCE */
1868 /* Registers are set to a sentinel when they haven't yet matched. */
1869 static CHAR_T
PREFIX(reg_unset_dummy
);
1870 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1871 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1873 /* Subroutine declarations and macros for regex_compile. */
1874 static void PREFIX(store_op1
) (re_opcode_t op
, UCHAR_T
*loc
, int arg
);
1875 static void PREFIX(store_op2
) (re_opcode_t op
, UCHAR_T
*loc
,
1876 int arg1
, int arg2
);
1877 static void PREFIX(insert_op1
) (re_opcode_t op
, UCHAR_T
*loc
,
1878 int arg
, UCHAR_T
*end
);
1879 static void PREFIX(insert_op2
) (re_opcode_t op
, UCHAR_T
*loc
,
1880 int arg1
, int arg2
, UCHAR_T
*end
);
1881 static boolean
PREFIX(at_begline_loc_p
) (const CHAR_T
*pattern
,
1883 reg_syntax_t syntax
);
1884 static boolean
PREFIX(at_endline_loc_p
) (const CHAR_T
*p
,
1886 reg_syntax_t syntax
);
1888 static reg_errcode_t
wcs_compile_range (CHAR_T range_start
,
1889 const CHAR_T
**p_ptr
,
1891 __RE_TRANSLATE_TYPE translate
,
1892 reg_syntax_t syntax
,
1895 static void insert_space (int num
, CHAR_T
*loc
, CHAR_T
*end
);
1897 static reg_errcode_t
byte_compile_range (unsigned int range_start
,
1900 __RE_TRANSLATE_TYPE translate
,
1901 reg_syntax_t syntax
,
1905 /* Fetch the next character in the uncompiled pattern---translating it
1906 if necessary. Also cast from a signed character in the constant
1907 string passed to us by the user to an unsigned char that we can use
1908 as an array index (in, e.g., `translate'). */
1909 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1910 because it is impossible to allocate 4GB array for some encodings
1911 which have 4 byte character_set like UCS4. */
1914 # define PATFETCH(c) \
1915 do {if (p == pend) return REG_EEND; \
1916 c = (UCHAR_T) *p++; \
1917 if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c]; \
1920 # define PATFETCH(c) \
1921 do {if (p == pend) return REG_EEND; \
1922 c = (unsigned char) *p++; \
1923 if (translate) c = (unsigned char) translate[c]; \
1928 /* Fetch the next character in the uncompiled pattern, with no
1930 # define PATFETCH_RAW(c) \
1931 do {if (p == pend) return REG_EEND; \
1932 c = (UCHAR_T) *p++; \
1935 /* Go backwards one character in the pattern. */
1936 # define PATUNFETCH p--
1939 /* If `translate' is non-null, return translate[D], else just D. We
1940 cast the subscript to translate because some data is declared as
1941 `char *', to avoid warnings when a string constant is passed. But
1942 when we use a character as a subscript we must make it unsigned. */
1943 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1944 because it is impossible to allocate 4GB array for some encodings
1945 which have 4 byte character_set like UCS4. */
1949 # define TRANSLATE(d) \
1950 ((translate && ((UCHAR_T) (d)) <= 0xff) \
1951 ? (char) translate[(unsigned char) (d)] : (d))
1953 # define TRANSLATE(d) \
1954 (translate ? (char) translate[(unsigned char) (d)] : (d))
1959 /* Macros for outputting the compiled pattern into `buffer'. */
1961 /* If the buffer isn't allocated when it comes in, use this. */
1962 # define INIT_BUF_SIZE (32 * sizeof(UCHAR_T))
1964 /* Make sure we have at least N more bytes of space in buffer. */
1966 # define GET_BUFFER_SPACE(n) \
1967 while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR \
1968 + (n)*sizeof(CHAR_T)) > bufp->allocated) \
1971 # define GET_BUFFER_SPACE(n) \
1972 while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated) \
1976 /* Make sure we have one more byte of buffer space and then add C to it. */
1977 # define BUF_PUSH(c) \
1979 GET_BUFFER_SPACE (1); \
1980 *b++ = (UCHAR_T) (c); \
1984 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
1985 # define BUF_PUSH_2(c1, c2) \
1987 GET_BUFFER_SPACE (2); \
1988 *b++ = (UCHAR_T) (c1); \
1989 *b++ = (UCHAR_T) (c2); \
1993 /* As with BUF_PUSH_2, except for three bytes. */
1994 # define BUF_PUSH_3(c1, c2, c3) \
1996 GET_BUFFER_SPACE (3); \
1997 *b++ = (UCHAR_T) (c1); \
1998 *b++ = (UCHAR_T) (c2); \
1999 *b++ = (UCHAR_T) (c3); \
2002 /* Store a jump with opcode OP at LOC to location TO. We store a
2003 relative address offset by the three bytes the jump itself occupies. */
2004 # define STORE_JUMP(op, loc, to) \
2005 PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
2007 /* Likewise, for a two-argument jump. */
2008 # define STORE_JUMP2(op, loc, to, arg) \
2009 PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
2011 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
2012 # define INSERT_JUMP(op, loc, to) \
2013 PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
2015 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
2016 # define INSERT_JUMP2(op, loc, to, arg) \
2017 PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
2020 /* This is not an arbitrary limit: the arguments which represent offsets
2021 into the pattern are two bytes long. So if 2^16 bytes turns out to
2022 be too small, many things would have to change. */
2023 /* Any other compiler which, like MSC, has allocation limit below 2^16
2024 bytes will have to use approach similar to what was done below for
2025 MSC and drop MAX_BUF_SIZE a bit. Otherwise you may end up
2026 reallocating to 0 bytes. Such thing is not going to work too well.
2027 You have been warned!! */
2028 # ifndef DEFINED_ONCE
2029 # if defined _MSC_VER && !defined WIN32
2030 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2031 The REALLOC define eliminates a flurry of conversion warnings,
2032 but is not required. */
2033 # define MAX_BUF_SIZE 65500L
2034 # define REALLOC(p,s) realloc ((p), (size_t) (s))
2036 # define MAX_BUF_SIZE (1L << 16)
2037 # define REALLOC(p,s) realloc ((p), (s))
2039 # endif /* not DEFINED_ONCE */
2041 /* Extend the buffer by twice its current size via realloc and
2042 reset the pointers that pointed into the old block to point to the
2043 correct places in the new one. If extending the buffer results in it
2044 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
2046 # define EXTEND_BUFFER() \
2048 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2050 if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE) \
2052 bufp->allocated <<= 1; \
2053 if (bufp->allocated > MAX_BUF_SIZE) \
2054 bufp->allocated = MAX_BUF_SIZE; \
2055 /* How many characters the new buffer can have? */ \
2056 wchar_count = bufp->allocated / sizeof(UCHAR_T); \
2057 if (wchar_count == 0) wchar_count = 1; \
2058 /* Truncate the buffer to CHAR_T align. */ \
2059 bufp->allocated = wchar_count * sizeof(UCHAR_T); \
2060 RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T); \
2061 bufp->buffer = (char*)COMPILED_BUFFER_VAR; \
2062 if (COMPILED_BUFFER_VAR == NULL) \
2063 return REG_ESPACE; \
2064 /* If the buffer moved, move all the pointers into it. */ \
2065 if (old_buffer != COMPILED_BUFFER_VAR) \
2067 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2070 if (fixup_alt_jump) \
2071 fixup_alt_jump += incr; \
2073 laststart += incr; \
2074 if (pending_exact) \
2075 pending_exact += incr; \
2079 # define EXTEND_BUFFER() \
2081 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2082 if (bufp->allocated == MAX_BUF_SIZE) \
2084 bufp->allocated <<= 1; \
2085 if (bufp->allocated > MAX_BUF_SIZE) \
2086 bufp->allocated = MAX_BUF_SIZE; \
2087 bufp->buffer = (UCHAR_T *) REALLOC (COMPILED_BUFFER_VAR, \
2089 if (COMPILED_BUFFER_VAR == NULL) \
2090 return REG_ESPACE; \
2091 /* If the buffer moved, move all the pointers into it. */ \
2092 if (old_buffer != COMPILED_BUFFER_VAR) \
2094 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2097 if (fixup_alt_jump) \
2098 fixup_alt_jump += incr; \
2100 laststart += incr; \
2101 if (pending_exact) \
2102 pending_exact += incr; \
2107 # ifndef DEFINED_ONCE
2108 /* Since we have one byte reserved for the register number argument to
2109 {start,stop}_memory, the maximum number of groups we can report
2110 things about is what fits in that byte. */
2111 # define MAX_REGNUM 255
2113 /* But patterns can have more than `MAX_REGNUM' registers. We just
2114 ignore the excess. */
2115 typedef unsigned regnum_t
;
2118 /* Macros for the compile stack. */
2120 /* Since offsets can go either forwards or backwards, this type needs to
2121 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
2122 /* int may be not enough when sizeof(int) == 2. */
2123 typedef long pattern_offset_t
;
2127 pattern_offset_t begalt_offset
;
2128 pattern_offset_t fixup_alt_jump
;
2129 pattern_offset_t inner_group_offset
;
2130 pattern_offset_t laststart_offset
;
2132 } compile_stack_elt_t
;
2137 compile_stack_elt_t
*stack
;
2139 unsigned avail
; /* Offset of next open position. */
2140 } compile_stack_type
;
2143 # define INIT_COMPILE_STACK_SIZE 32
2145 # define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
2146 # define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
2148 /* The next available element. */
2149 # define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2151 # endif /* not DEFINED_ONCE */
2153 /* Set the bit for character C in a list. */
2154 # ifndef DEFINED_ONCE
2155 # define SET_LIST_BIT(c) \
2156 (b[((unsigned char) (c)) / BYTEWIDTH] \
2157 |= 1 << (((unsigned char) c) % BYTEWIDTH))
2158 # endif /* DEFINED_ONCE */
2160 /* Get the next unsigned number in the uncompiled pattern. */
2161 # define GET_UNSIGNED_NUMBER(num) \
2166 if (c < '0' || c > '9') \
2168 if (num <= RE_DUP_MAX) \
2172 num = num * 10 + c - '0'; \
2177 # ifndef DEFINED_ONCE
2178 # if defined _LIBC || defined WIDE_CHAR_SUPPORT
2179 /* The GNU C library provides support for user-defined character classes
2180 and the functions from ISO C amendement 1. */
2181 # ifdef CHARCLASS_NAME_MAX
2182 # define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2184 /* This shouldn't happen but some implementation might still have this
2185 problem. Use a reasonable default value. */
2186 # define CHAR_CLASS_MAX_LENGTH 256
2190 # define IS_CHAR_CLASS(string) __wctype (string)
2192 # define IS_CHAR_CLASS(string) wctype (string)
2195 # define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
2197 # define IS_CHAR_CLASS(string) \
2198 (STREQ (string, "alpha") || STREQ (string, "upper") \
2199 || STREQ (string, "lower") || STREQ (string, "digit") \
2200 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
2201 || STREQ (string, "space") || STREQ (string, "print") \
2202 || STREQ (string, "punct") || STREQ (string, "graph") \
2203 || STREQ (string, "cntrl") || STREQ (string, "blank"))
2205 # endif /* DEFINED_ONCE */
2207 # ifndef MATCH_MAY_ALLOCATE
2209 /* If we cannot allocate large objects within re_match_2_internal,
2210 we make the fail stack and register vectors global.
2211 The fail stack, we grow to the maximum size when a regexp
2213 The register vectors, we adjust in size each time we
2214 compile a regexp, according to the number of registers it needs. */
2216 static PREFIX(fail_stack_type
) fail_stack
;
2218 /* Size with which the following vectors are currently allocated.
2219 That is so we can make them bigger as needed,
2220 but never make them smaller. */
2221 # ifdef DEFINED_ONCE
2222 static int regs_allocated_size
;
2224 static const char ** regstart
, ** regend
;
2225 static const char ** old_regstart
, ** old_regend
;
2226 static const char **best_regstart
, **best_regend
;
2227 static const char **reg_dummy
;
2228 # endif /* DEFINED_ONCE */
2230 static PREFIX(register_info_type
) *PREFIX(reg_info
);
2231 static PREFIX(register_info_type
) *PREFIX(reg_info_dummy
);
2233 /* Make the register vectors big enough for NUM_REGS registers,
2234 but don't make them smaller. */
2237 PREFIX(regex_grow_registers
) (int num_regs
)
2239 if (num_regs
> regs_allocated_size
)
2241 RETALLOC_IF (regstart
, num_regs
, const char *);
2242 RETALLOC_IF (regend
, num_regs
, const char *);
2243 RETALLOC_IF (old_regstart
, num_regs
, const char *);
2244 RETALLOC_IF (old_regend
, num_regs
, const char *);
2245 RETALLOC_IF (best_regstart
, num_regs
, const char *);
2246 RETALLOC_IF (best_regend
, num_regs
, const char *);
2247 RETALLOC_IF (PREFIX(reg_info
), num_regs
, PREFIX(register_info_type
));
2248 RETALLOC_IF (reg_dummy
, num_regs
, const char *);
2249 RETALLOC_IF (PREFIX(reg_info_dummy
), num_regs
, PREFIX(register_info_type
));
2251 regs_allocated_size
= num_regs
;
2255 # endif /* not MATCH_MAY_ALLOCATE */
2257 # ifndef DEFINED_ONCE
2258 static boolean
group_in_compile_stack (compile_stack_type
2261 # endif /* not DEFINED_ONCE */
2263 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2264 Returns one of error codes defined in `regex.h', or zero for success.
2266 Assumes the `allocated' (and perhaps `buffer') and `translate'
2267 fields are set in BUFP on entry.
2269 If it succeeds, results are put in BUFP (if it returns an error, the
2270 contents of BUFP are undefined):
2271 `buffer' is the compiled pattern;
2272 `syntax' is set to SYNTAX;
2273 `used' is set to the length of the compiled pattern;
2274 `fastmap_accurate' is zero;
2275 `re_nsub' is the number of subexpressions in PATTERN;
2276 `not_bol' and `not_eol' are zero;
2278 The `fastmap' and `newline_anchor' fields are neither
2279 examined nor set. */
2281 /* Return, freeing storage we allocated. */
2283 # define FREE_STACK_RETURN(value) \
2284 return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2286 # define FREE_STACK_RETURN(value) \
2287 return (free (compile_stack.stack), value)
2290 static reg_errcode_t
2291 PREFIX(regex_compile
) (
2292 const char *ARG_PREFIX(pattern
),
2293 size_t ARG_PREFIX(size
),
2294 reg_syntax_t syntax
,
2295 struct re_pattern_buffer
*bufp
)
2297 /* We fetch characters from PATTERN here. Even though PATTERN is
2298 `char *' (i.e., signed), we declare these variables as unsigned, so
2299 they can be reliably used as array indices. */
2300 register UCHAR_T c
, c1
;
2303 /* A temporary space to keep wchar_t pattern and compiled pattern. */
2304 CHAR_T
*pattern
, *COMPILED_BUFFER_VAR
;
2306 /* offset buffer for optimization. See convert_mbs_to_wc. */
2307 int *mbs_offset
= NULL
;
2308 /* It hold whether each wchar_t is binary data or not. */
2309 char *is_binary
= NULL
;
2310 /* A flag whether exactn is handling binary data or not. */
2311 char is_exactn_bin
= FALSE
;
2314 /* A random temporary spot in PATTERN. */
2317 /* Points to the end of the buffer, where we should append. */
2318 register UCHAR_T
*b
;
2320 /* Keeps track of unclosed groups. */
2321 compile_stack_type compile_stack
;
2323 /* Points to the current (ending) position in the pattern. */
2328 const CHAR_T
*p
= pattern
;
2329 const CHAR_T
*pend
= pattern
+ size
;
2332 /* How to translate the characters in the pattern. */
2333 __RE_TRANSLATE_TYPE translate
= bufp
->translate
;
2335 /* Address of the count-byte of the most recently inserted `exactn'
2336 command. This makes it possible to tell if a new exact-match
2337 character can be added to that command or if the character requires
2338 a new `exactn' command. */
2339 UCHAR_T
*pending_exact
= 0;
2341 /* Address of start of the most recently finished expression.
2342 This tells, e.g., postfix * where to find the start of its
2343 operand. Reset at the beginning of groups and alternatives. */
2344 UCHAR_T
*laststart
= 0;
2346 /* Address of beginning of regexp, or inside of last group. */
2349 /* Address of the place where a forward jump should go to the end of
2350 the containing expression. Each alternative of an `or' -- except the
2351 last -- ends with a forward jump of this sort. */
2352 UCHAR_T
*fixup_alt_jump
= 0;
2354 /* Counts open-groups as they are encountered. Remembered for the
2355 matching close-group on the compile stack, so the same register
2356 number is put in the stop_memory as the start_memory. */
2357 regnum_t regnum
= 0;
2360 /* Initialize the wchar_t PATTERN and offset_buffer. */
2361 p
= pend
= pattern
= TALLOC(csize
+ 1, CHAR_T
);
2362 mbs_offset
= TALLOC(csize
+ 1, int);
2363 is_binary
= TALLOC(csize
+ 1, char);
2364 if (pattern
== NULL
|| mbs_offset
== NULL
|| is_binary
== NULL
)
2371 pattern
[csize
] = L
'\0'; /* sentinel */
2372 size
= convert_mbs_to_wcs(pattern
, cpattern
, csize
, mbs_offset
, is_binary
);
2384 DEBUG_PRINT1 ("\nCompiling pattern: ");
2387 unsigned debug_count
;
2389 for (debug_count
= 0; debug_count
< size
; debug_count
++)
2390 PUT_CHAR (pattern
[debug_count
]);
2395 /* Initialize the compile stack. */
2396 compile_stack
.stack
= TALLOC (INIT_COMPILE_STACK_SIZE
, compile_stack_elt_t
);
2397 if (compile_stack
.stack
== NULL
)
2407 compile_stack
.size
= INIT_COMPILE_STACK_SIZE
;
2408 compile_stack
.avail
= 0;
2410 /* Initialize the pattern buffer. */
2411 bufp
->syntax
= syntax
;
2412 bufp
->fastmap_accurate
= 0;
2413 bufp
->not_bol
= bufp
->not_eol
= 0;
2415 /* Set `used' to zero, so that if we return an error, the pattern
2416 printer (for debugging) will think there's no pattern. We reset it
2420 /* Always count groups, whether or not bufp->no_sub is set. */
2423 #if !defined emacs && !defined SYNTAX_TABLE
2424 /* Initialize the syntax table. */
2425 init_syntax_once ();
2428 if (bufp
->allocated
== 0)
2431 { /* If zero allocated, but buffer is non-null, try to realloc
2432 enough space. This loses if buffer's address is bogus, but
2433 that is the user's responsibility. */
2435 /* Free bufp->buffer and allocate an array for wchar_t pattern
2438 COMPILED_BUFFER_VAR
= TALLOC (INIT_BUF_SIZE
/sizeof(UCHAR_T
),
2441 RETALLOC (COMPILED_BUFFER_VAR
, INIT_BUF_SIZE
, UCHAR_T
);
2445 { /* Caller did not allocate a buffer. Do it for them. */
2446 COMPILED_BUFFER_VAR
= TALLOC (INIT_BUF_SIZE
/ sizeof(UCHAR_T
),
2450 if (!COMPILED_BUFFER_VAR
) FREE_STACK_RETURN (REG_ESPACE
);
2452 bufp
->buffer
= (char*)COMPILED_BUFFER_VAR
;
2454 bufp
->allocated
= INIT_BUF_SIZE
;
2458 COMPILED_BUFFER_VAR
= (UCHAR_T
*) bufp
->buffer
;
2461 begalt
= b
= COMPILED_BUFFER_VAR
;
2463 /* Loop through the uncompiled pattern until we're at the end. */
2472 if ( /* If at start of pattern, it's an operator. */
2474 /* If context independent, it's an operator. */
2475 || syntax
& RE_CONTEXT_INDEP_ANCHORS
2476 /* Otherwise, depends on what's come before. */
2477 || PREFIX(at_begline_loc_p
) (pattern
, p
, syntax
))
2487 if ( /* If at end of pattern, it's an operator. */
2489 /* If context independent, it's an operator. */
2490 || syntax
& RE_CONTEXT_INDEP_ANCHORS
2491 /* Otherwise, depends on what's next. */
2492 || PREFIX(at_endline_loc_p
) (p
, pend
, syntax
))
2502 if ((syntax
& RE_BK_PLUS_QM
)
2503 || (syntax
& RE_LIMITED_OPS
))
2507 /* If there is no previous pattern... */
2510 if (syntax
& RE_CONTEXT_INVALID_OPS
)
2511 FREE_STACK_RETURN (REG_BADRPT
);
2512 else if (!(syntax
& RE_CONTEXT_INDEP_OPS
))
2517 /* Are we optimizing this jump? */
2518 boolean keep_string_p
= false;
2520 /* 1 means zero (many) matches is allowed. */
2521 char zero_times_ok
= 0, many_times_ok
= 0;
2523 /* If there is a sequence of repetition chars, collapse it
2524 down to just one (the right one). We can't combine
2525 interval operators with these because of, e.g., `a{2}*',
2526 which should only match an even number of `a's. */
2530 zero_times_ok
|= c
!= '+';
2531 many_times_ok
|= c
!= '?';
2539 || (!(syntax
& RE_BK_PLUS_QM
) && (c
== '+' || c
== '?')))
2542 else if (syntax
& RE_BK_PLUS_QM
&& c
== '\\')
2544 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
2547 if (!(c1
== '+' || c1
== '?'))
2562 /* If we get here, we found another repeat character. */
2565 /* Star, etc. applied to an empty pattern is equivalent
2566 to an empty pattern. */
2570 /* Now we know whether or not zero matches is allowed
2571 and also whether or not two or more matches is allowed. */
2573 { /* More than one repetition is allowed, so put in at the
2574 end a backward relative jump from `b' to before the next
2575 jump we're going to put in below (which jumps from
2576 laststart to after this jump).
2578 But if we are at the `*' in the exact sequence `.*\n',
2579 insert an unconditional jump backwards to the .,
2580 instead of the beginning of the loop. This way we only
2581 push a failure point once, instead of every time
2582 through the loop. */
2583 assert (p
- 1 > pattern
);
2585 /* Allocate the space for the jump. */
2586 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
2588 /* We know we are not at the first character of the pattern,
2589 because laststart was nonzero. And we've already
2590 incremented `p', by the way, to be the character after
2591 the `*'. Do we have to do something analogous here
2592 for null bytes, because of RE_DOT_NOT_NULL? */
2593 if (TRANSLATE (*(p
- 2)) == TRANSLATE ('.')
2595 && p
< pend
&& TRANSLATE (*p
) == TRANSLATE ('\n')
2596 && !(syntax
& RE_DOT_NEWLINE
))
2597 { /* We have .*\n. */
2598 STORE_JUMP (jump
, b
, laststart
);
2599 keep_string_p
= true;
2602 /* Anything else. */
2603 STORE_JUMP (maybe_pop_jump
, b
, laststart
-
2604 (1 + OFFSET_ADDRESS_SIZE
));
2606 /* We've added more stuff to the buffer. */
2607 b
+= 1 + OFFSET_ADDRESS_SIZE
;
2610 /* On failure, jump from laststart to b + 3, which will be the
2611 end of the buffer after this jump is inserted. */
2612 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2614 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
2615 INSERT_JUMP (keep_string_p
? on_failure_keep_string_jump
2617 laststart
, b
+ 1 + OFFSET_ADDRESS_SIZE
);
2619 b
+= 1 + OFFSET_ADDRESS_SIZE
;
2623 /* At least one repetition is required, so insert a
2624 `dummy_failure_jump' before the initial
2625 `on_failure_jump' instruction of the loop. This
2626 effects a skip over that instruction the first time
2627 we hit that loop. */
2628 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
2629 INSERT_JUMP (dummy_failure_jump
, laststart
, laststart
+
2630 2 + 2 * OFFSET_ADDRESS_SIZE
);
2631 b
+= 1 + OFFSET_ADDRESS_SIZE
;
2645 boolean had_char_class
= false;
2647 CHAR_T range_start
= 0xffffffff;
2649 unsigned int range_start
= 0xffffffff;
2651 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2654 /* We assume a charset(_not) structure as a wchar_t array.
2655 charset[0] = (re_opcode_t) charset(_not)
2656 charset[1] = l (= length of char_classes)
2657 charset[2] = m (= length of collating_symbols)
2658 charset[3] = n (= length of equivalence_classes)
2659 charset[4] = o (= length of char_ranges)
2660 charset[5] = p (= length of chars)
2662 charset[6] = char_class (wctype_t)
2663 charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2665 charset[l+5] = char_class (wctype_t)
2667 charset[l+6] = collating_symbol (wchar_t)
2669 charset[l+m+5] = collating_symbol (wchar_t)
2670 ifdef _LIBC we use the index if
2671 _NL_COLLATE_SYMB_EXTRAMB instead of
2674 charset[l+m+6] = equivalence_classes (wchar_t)
2676 charset[l+m+n+5] = equivalence_classes (wchar_t)
2677 ifdef _LIBC we use the index in
2678 _NL_COLLATE_WEIGHT instead of
2681 charset[l+m+n+6] = range_start
2682 charset[l+m+n+7] = range_end
2684 charset[l+m+n+2o+4] = range_start
2685 charset[l+m+n+2o+5] = range_end
2686 ifdef _LIBC we use the value looked up
2687 in _NL_COLLATE_COLLSEQ instead of
2690 charset[l+m+n+2o+6] = char
2692 charset[l+m+n+2o+p+5] = char
2696 /* We need at least 6 spaces: the opcode, the length of
2697 char_classes, the length of collating_symbols, the length of
2698 equivalence_classes, the length of char_ranges, the length of
2700 GET_BUFFER_SPACE (6);
2702 /* Save b as laststart. And We use laststart as the pointer
2703 to the first element of the charset here.
2704 In other words, laststart[i] indicates charset[i]. */
2707 /* We test `*p == '^' twice, instead of using an if
2708 statement, so we only need one BUF_PUSH. */
2709 BUF_PUSH (*p
== '^' ? charset_not
: charset
);
2713 /* Push the length of char_classes, the length of
2714 collating_symbols, the length of equivalence_classes, the
2715 length of char_ranges and the length of chars. */
2716 BUF_PUSH_3 (0, 0, 0);
2719 /* Remember the first position in the bracket expression. */
2722 /* charset_not matches newline according to a syntax bit. */
2723 if ((re_opcode_t
) b
[-6] == charset_not
2724 && (syntax
& RE_HAT_LISTS_NOT_NEWLINE
))
2727 laststart
[5]++; /* Update the length of characters */
2730 /* Read in characters and ranges, setting map bits. */
2733 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2737 /* \ might escape characters inside [...] and [^...]. */
2738 if ((syntax
& RE_BACKSLASH_ESCAPE_IN_LISTS
) && c
== '\\')
2740 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
2744 laststart
[5]++; /* Update the length of chars */
2749 /* Could be the end of the bracket expression. If it's
2750 not (i.e., when the bracket expression is `[]' so
2751 far), the ']' character bit gets set way below. */
2752 if (c
== ']' && p
!= p1
+ 1)
2755 /* Look ahead to see if it's a range when the last thing
2756 was a character class. */
2757 if (had_char_class
&& c
== '-' && *p
!= ']')
2758 FREE_STACK_RETURN (REG_ERANGE
);
2760 /* Look ahead to see if it's a range when the last thing
2761 was a character: if this is a hyphen not at the
2762 beginning or the end of a list, then it's the range
2765 && !(p
- 2 >= pattern
&& p
[-2] == '[')
2766 && !(p
- 3 >= pattern
&& p
[-3] == '[' && p
[-2] == '^')
2770 /* Allocate the space for range_start and range_end. */
2771 GET_BUFFER_SPACE (2);
2772 /* Update the pointer to indicate end of buffer. */
2774 ret
= wcs_compile_range (range_start
, &p
, pend
, translate
,
2775 syntax
, b
, laststart
);
2776 if (ret
!= REG_NOERROR
) FREE_STACK_RETURN (ret
);
2777 range_start
= 0xffffffff;
2779 else if (p
[0] == '-' && p
[1] != ']')
2780 { /* This handles ranges made up of characters only. */
2783 /* Move past the `-'. */
2785 /* Allocate the space for range_start and range_end. */
2786 GET_BUFFER_SPACE (2);
2787 /* Update the pointer to indicate end of buffer. */
2789 ret
= wcs_compile_range (c
, &p
, pend
, translate
, syntax
, b
,
2791 if (ret
!= REG_NOERROR
) FREE_STACK_RETURN (ret
);
2792 range_start
= 0xffffffff;
2795 /* See if we're at the beginning of a possible character
2797 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && *p
== ':')
2798 { /* Leave room for the null. */
2799 char str
[CHAR_CLASS_MAX_LENGTH
+ 1];
2804 /* If pattern is `[[:'. */
2805 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2810 if ((c
== ':' && *p
== ']') || p
== pend
)
2812 if (c1
< CHAR_CLASS_MAX_LENGTH
)
2815 /* This is in any case an invalid class name. */
2820 /* If isn't a word bracketed by `[:' and `:]':
2821 undo the ending character, the letters, and leave
2822 the leading `:' and `[' (but store them as character). */
2823 if (c
== ':' && *p
== ']')
2828 /* Query the character class as wctype_t. */
2829 wt
= IS_CHAR_CLASS (str
);
2831 FREE_STACK_RETURN (REG_ECTYPE
);
2833 /* Throw away the ] at the end of the character
2837 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2839 /* Allocate the space for character class. */
2840 GET_BUFFER_SPACE(CHAR_CLASS_SIZE
);
2841 /* Update the pointer to indicate end of buffer. */
2842 b
+= CHAR_CLASS_SIZE
;
2843 /* Move data which follow character classes
2844 not to violate the data. */
2845 insert_space(CHAR_CLASS_SIZE
,
2846 laststart
+ 6 + laststart
[1],
2848 alignedp
= ((uintptr_t)(laststart
+ 6 + laststart
[1])
2849 + __alignof__(wctype_t) - 1)
2850 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2851 /* Store the character class. */
2852 *((wctype_t*)alignedp
) = wt
;
2853 /* Update length of char_classes */
2854 laststart
[1] += CHAR_CLASS_SIZE
;
2856 had_char_class
= true;
2865 laststart
[5] += 2; /* Update the length of characters */
2867 had_char_class
= false;
2870 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && (*p
== '='
2873 CHAR_T str
[128]; /* Should be large enough. */
2874 CHAR_T delim
= *p
; /* '=' or '.' */
2877 _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
2882 /* If pattern is `[[=' or '[[.'. */
2883 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2888 if ((c
== delim
&& *p
== ']') || p
== pend
)
2890 if (c1
< sizeof (str
) - 1)
2893 /* This is in any case an invalid class name. */
2898 if (c
== delim
&& *p
== ']' && str
[0] != '\0')
2900 unsigned int i
, offset
;
2901 /* If we have no collation data we use the default
2902 collation in which each character is in a class
2903 by itself. It also means that ASCII is the
2904 character set and therefore we cannot have character
2905 with more than one byte in the multibyte
2908 /* If not defined _LIBC, we push the name and
2909 `\0' for the sake of matching performance. */
2910 int datasize
= c1
+ 1;
2918 FREE_STACK_RETURN (REG_ECOLLATE
);
2923 const int32_t *table
;
2924 const int32_t *weights
;
2925 const int32_t *extra
;
2926 const int32_t *indirect
;
2929 /* This #include defines a local function! */
2930 # include <locale/weightwc.h>
2934 /* We push the index for equivalence class. */
2937 table
= (const int32_t *)
2938 _NL_CURRENT (LC_COLLATE
,
2939 _NL_COLLATE_TABLEWC
);
2940 weights
= (const int32_t *)
2941 _NL_CURRENT (LC_COLLATE
,
2942 _NL_COLLATE_WEIGHTWC
);
2943 extra
= (const int32_t *)
2944 _NL_CURRENT (LC_COLLATE
,
2945 _NL_COLLATE_EXTRAWC
);
2946 indirect
= (const int32_t *)
2947 _NL_CURRENT (LC_COLLATE
,
2948 _NL_COLLATE_INDIRECTWC
);
2950 idx
= findidx ((const wint_t**)&cp
);
2951 if (idx
== 0 || cp
< (wint_t*) str
+ c1
)
2952 /* This is no valid character. */
2953 FREE_STACK_RETURN (REG_ECOLLATE
);
2955 str
[0] = (wchar_t)idx
;
2957 else /* delim == '.' */
2959 /* We push collation sequence value
2960 for collating symbol. */
2962 const int32_t *symb_table
;
2963 const unsigned char *extra
;
2970 /* We have to convert the name to a single-byte
2971 string. This is possible since the names
2972 consist of ASCII characters and the internal
2973 representation is UCS4. */
2974 for (i
= 0; i
< c1
; ++i
)
2975 char_str
[i
] = str
[i
];
2978 _NL_CURRENT_WORD (LC_COLLATE
,
2979 _NL_COLLATE_SYMB_HASH_SIZEMB
);
2980 symb_table
= (const int32_t *)
2981 _NL_CURRENT (LC_COLLATE
,
2982 _NL_COLLATE_SYMB_TABLEMB
);
2983 extra
= (const unsigned char *)
2984 _NL_CURRENT (LC_COLLATE
,
2985 _NL_COLLATE_SYMB_EXTRAMB
);
2987 /* Locate the character in the hashing table. */
2988 hash
= elem_hash (char_str
, c1
);
2991 elem
= hash
% table_size
;
2992 second
= hash
% (table_size
- 2);
2993 while (symb_table
[2 * elem
] != 0)
2995 /* First compare the hashing value. */
2996 if (symb_table
[2 * elem
] == hash
2997 && c1
== extra
[symb_table
[2 * elem
+ 1]]
2998 && memcmp (char_str
,
2999 &extra
[symb_table
[2 * elem
+ 1]
3002 /* Yep, this is the entry. */
3003 idx
= symb_table
[2 * elem
+ 1];
3004 idx
+= 1 + extra
[idx
];
3012 if (symb_table
[2 * elem
] != 0)
3014 /* Compute the index of the byte sequence
3016 idx
+= 1 + extra
[idx
];
3017 /* Adjust for the alignment. */
3018 idx
= (idx
+ 3) & ~3;
3020 str
[0] = (wchar_t) idx
+ 4;
3022 else if (symb_table
[2 * elem
] == 0 && c1
== 1)
3024 /* No valid character. Match it as a
3025 single byte character. */
3026 had_char_class
= false;
3028 /* Update the length of characters */
3030 range_start
= str
[0];
3032 /* Throw away the ] at the end of the
3033 collating symbol. */
3035 /* exit from the switch block. */
3039 FREE_STACK_RETURN (REG_ECOLLATE
);
3044 /* Throw away the ] at the end of the equivalence
3045 class (or collating symbol). */
3048 /* Allocate the space for the equivalence class
3049 (or collating symbol) (and '\0' if needed). */
3050 GET_BUFFER_SPACE(datasize
);
3051 /* Update the pointer to indicate end of buffer. */
3055 { /* equivalence class */
3056 /* Calculate the offset of char_ranges,
3057 which is next to equivalence_classes. */
3058 offset
= laststart
[1] + laststart
[2]
3061 insert_space(datasize
, laststart
+ offset
, b
- 1);
3063 /* Write the equivalence_class and \0. */
3064 for (i
= 0 ; i
< datasize
; i
++)
3065 laststart
[offset
+ i
] = str
[i
];
3067 /* Update the length of equivalence_classes. */
3068 laststart
[3] += datasize
;
3069 had_char_class
= true;
3071 else /* delim == '.' */
3072 { /* collating symbol */
3073 /* Calculate the offset of the equivalence_classes,
3074 which is next to collating_symbols. */
3075 offset
= laststart
[1] + laststart
[2] + 6;
3076 /* Insert space and write the collationg_symbol
3078 insert_space(datasize
, laststart
+ offset
, b
-1);
3079 for (i
= 0 ; i
< datasize
; i
++)
3080 laststart
[offset
+ i
] = str
[i
];
3082 /* In re_match_2_internal if range_start < -1, we
3083 assume -range_start is the offset of the
3084 collating symbol which is specified as
3085 the character of the range start. So we assign
3086 -(laststart[1] + laststart[2] + 6) to
3088 range_start
= -(laststart
[1] + laststart
[2] + 6);
3089 /* Update the length of collating_symbol. */
3090 laststart
[2] += datasize
;
3091 had_char_class
= false;
3101 laststart
[5] += 2; /* Update the length of characters */
3102 range_start
= delim
;
3103 had_char_class
= false;
3108 had_char_class
= false;
3110 laststart
[5]++; /* Update the length of characters */
3116 /* Ensure that we have enough space to push a charset: the
3117 opcode, the length count, and the bitset; 34 bytes in all. */
3118 GET_BUFFER_SPACE (34);
3122 /* We test `*p == '^' twice, instead of using an if
3123 statement, so we only need one BUF_PUSH. */
3124 BUF_PUSH (*p
== '^' ? charset_not
: charset
);
3128 /* Remember the first position in the bracket expression. */
3131 /* Push the number of bytes in the bitmap. */
3132 BUF_PUSH ((1 << BYTEWIDTH
) / BYTEWIDTH
);
3134 /* Clear the whole map. */
3135 bzero (b
, (1 << BYTEWIDTH
) / BYTEWIDTH
);
3137 /* charset_not matches newline according to a syntax bit. */
3138 if ((re_opcode_t
) b
[-2] == charset_not
3139 && (syntax
& RE_HAT_LISTS_NOT_NEWLINE
))
3140 SET_LIST_BIT ('\n');
3142 /* Read in characters and ranges, setting map bits. */
3145 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3149 /* \ might escape characters inside [...] and [^...]. */
3150 if ((syntax
& RE_BACKSLASH_ESCAPE_IN_LISTS
) && c
== '\\')
3152 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
3160 /* Could be the end of the bracket expression. If it's
3161 not (i.e., when the bracket expression is `[]' so
3162 far), the ']' character bit gets set way below. */
3163 if (c
== ']' && p
!= p1
+ 1)
3166 /* Look ahead to see if it's a range when the last thing
3167 was a character class. */
3168 if (had_char_class
&& c
== '-' && *p
!= ']')
3169 FREE_STACK_RETURN (REG_ERANGE
);
3171 /* Look ahead to see if it's a range when the last thing
3172 was a character: if this is a hyphen not at the
3173 beginning or the end of a list, then it's the range
3176 && !(p
- 2 >= pattern
&& p
[-2] == '[')
3177 && !(p
- 3 >= pattern
&& p
[-3] == '[' && p
[-2] == '^')
3181 = byte_compile_range (range_start
, &p
, pend
, translate
,
3183 if (ret
!= REG_NOERROR
) FREE_STACK_RETURN (ret
);
3184 range_start
= 0xffffffff;
3187 else if (p
[0] == '-' && p
[1] != ']')
3188 { /* This handles ranges made up of characters only. */
3191 /* Move past the `-'. */
3194 ret
= byte_compile_range (c
, &p
, pend
, translate
, syntax
, b
);
3195 if (ret
!= REG_NOERROR
) FREE_STACK_RETURN (ret
);
3196 range_start
= 0xffffffff;
3199 /* See if we're at the beginning of a possible character
3202 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && *p
== ':')
3203 { /* Leave room for the null. */
3204 char str
[CHAR_CLASS_MAX_LENGTH
+ 1];
3209 /* If pattern is `[[:'. */
3210 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3215 if ((c
== ':' && *p
== ']') || p
== pend
)
3217 #if CHAR_CLASS_MAX_LENGTH != 256
3218 if (c1
< CHAR_CLASS_MAX_LENGTH
)
3221 /* This is in any case an invalid class name. */
3229 /* If isn't a word bracketed by `[:' and `:]':
3230 undo the ending character, the letters, and leave
3231 the leading `:' and `[' (but set bits for them). */
3232 if (c
== ':' && *p
== ']')
3234 # if defined _LIBC || defined WIDE_CHAR_SUPPORT
3235 boolean is_lower
= STREQ (str
, "lower");
3236 boolean is_upper
= STREQ (str
, "upper");
3240 wt
= IS_CHAR_CLASS (str
);
3242 FREE_STACK_RETURN (REG_ECTYPE
);
3244 /* Throw away the ] at the end of the character
3248 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3250 for (ch
= 0; ch
< 1 << BYTEWIDTH
; ++ch
)
3253 if (__iswctype (__btowc (ch
), wt
))
3256 if (iswctype (btowc (ch
), wt
))
3260 if (translate
&& (is_upper
|| is_lower
)
3261 && (ISUPPER (ch
) || ISLOWER (ch
)))
3265 had_char_class
= true;
3268 boolean is_alnum
= STREQ (str
, "alnum");
3269 boolean is_alpha
= STREQ (str
, "alpha");
3270 boolean is_blank
= STREQ (str
, "blank");
3271 boolean is_cntrl
= STREQ (str
, "cntrl");
3272 boolean is_digit
= STREQ (str
, "digit");
3273 boolean is_graph
= STREQ (str
, "graph");
3274 boolean is_lower
= STREQ (str
, "lower");
3275 boolean is_print
= STREQ (str
, "print");
3276 boolean is_punct
= STREQ (str
, "punct");
3277 boolean is_space
= STREQ (str
, "space");
3278 boolean is_upper
= STREQ (str
, "upper");
3279 boolean is_xdigit
= STREQ (str
, "xdigit");
3281 if (!IS_CHAR_CLASS (str
))
3282 FREE_STACK_RETURN (REG_ECTYPE
);
3284 /* Throw away the ] at the end of the character
3288 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3290 for (ch
= 0; ch
< 1 << BYTEWIDTH
; ch
++)
3292 /* This was split into 3 if's to
3293 avoid an arbitrary limit in some compiler. */
3294 if ( (is_alnum
&& ISALNUM (ch
))
3295 || (is_alpha
&& ISALPHA (ch
))
3296 || (is_blank
&& ISBLANK (ch
))
3297 || (is_cntrl
&& ISCNTRL (ch
)))
3299 if ( (is_digit
&& ISDIGIT (ch
))
3300 || (is_graph
&& ISGRAPH (ch
))
3301 || (is_lower
&& ISLOWER (ch
))
3302 || (is_print
&& ISPRINT (ch
)))
3304 if ( (is_punct
&& ISPUNCT (ch
))
3305 || (is_space
&& ISSPACE (ch
))
3306 || (is_upper
&& ISUPPER (ch
))
3307 || (is_xdigit
&& ISXDIGIT (ch
)))
3309 if ( translate
&& (is_upper
|| is_lower
)
3310 && (ISUPPER (ch
) || ISLOWER (ch
)))
3313 had_char_class
= true;
3314 # endif /* libc || wctype.h */
3324 had_char_class
= false;
3327 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && *p
== '=')
3329 unsigned char str
[MB_LEN_MAX
+ 1];
3332 _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3338 /* If pattern is `[[='. */
3339 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3344 if ((c
== '=' && *p
== ']') || p
== pend
)
3346 if (c1
< MB_LEN_MAX
)
3349 /* This is in any case an invalid class name. */
3354 if (c
== '=' && *p
== ']' && str
[0] != '\0')
3356 /* If we have no collation data we use the default
3357 collation in which each character is in a class
3358 by itself. It also means that ASCII is the
3359 character set and therefore we cannot have character
3360 with more than one byte in the multibyte
3367 FREE_STACK_RETURN (REG_ECOLLATE
);
3369 /* Throw away the ] at the end of the equivalence
3373 /* Set the bit for the character. */
3374 SET_LIST_BIT (str
[0]);
3379 /* Try to match the byte sequence in `str' against
3380 those known to the collate implementation.
3381 First find out whether the bytes in `str' are
3382 actually from exactly one character. */
3383 const int32_t *table
;
3384 const unsigned char *weights
;
3385 const unsigned char *extra
;
3386 const int32_t *indirect
;
3388 const unsigned char *cp
= str
;
3391 /* This #include defines a local function! */
3392 # include <locale/weight.h>
3394 table
= (const int32_t *)
3395 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEMB
);
3396 weights
= (const unsigned char *)
3397 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTMB
);
3398 extra
= (const unsigned char *)
3399 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAMB
);
3400 indirect
= (const int32_t *)
3401 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTMB
);
3403 idx
= findidx (&cp
);
3404 if (idx
== 0 || cp
< str
+ c1
)
3405 /* This is no valid character. */
3406 FREE_STACK_RETURN (REG_ECOLLATE
);
3408 /* Throw away the ] at the end of the equivalence
3412 /* Now we have to go throught the whole table
3413 and find all characters which have the same
3416 XXX Note that this is not entirely correct.
3417 we would have to match multibyte sequences
3418 but this is not possible with the current
3420 for (ch
= 1; ch
< 256; ++ch
)
3421 /* XXX This test would have to be changed if we
3422 would allow matching multibyte sequences. */
3425 int32_t idx2
= table
[ch
];
3426 size_t len
= weights
[idx2
];
3428 /* Test whether the lenghts match. */
3429 if (weights
[idx
] == len
)
3431 /* They do. New compare the bytes of
3436 && (weights
[idx
+ 1 + cnt
]
3437 == weights
[idx2
+ 1 + cnt
]))
3441 /* They match. Mark the character as
3448 had_char_class
= true;
3458 had_char_class
= false;
3461 else if (syntax
& RE_CHAR_CLASSES
&& c
== '[' && *p
== '.')
3463 unsigned char str
[128]; /* Should be large enough. */
3466 _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3472 /* If pattern is `[[.'. */
3473 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
3478 if ((c
== '.' && *p
== ']') || p
== pend
)
3480 if (c1
< sizeof (str
))
3483 /* This is in any case an invalid class name. */
3488 if (c
== '.' && *p
== ']' && str
[0] != '\0')
3490 /* If we have no collation data we use the default
3491 collation in which each character is the name
3492 for its own class which contains only the one
3493 character. It also means that ASCII is the
3494 character set and therefore we cannot have character
3495 with more than one byte in the multibyte
3502 FREE_STACK_RETURN (REG_ECOLLATE
);
3504 /* Throw away the ] at the end of the equivalence
3508 /* Set the bit for the character. */
3509 SET_LIST_BIT (str
[0]);
3510 range_start
= ((const unsigned char *) str
)[0];
3515 /* Try to match the byte sequence in `str' against
3516 those known to the collate implementation.
3517 First find out whether the bytes in `str' are
3518 actually from exactly one character. */
3520 const int32_t *symb_table
;
3521 const unsigned char *extra
;
3528 _NL_CURRENT_WORD (LC_COLLATE
,
3529 _NL_COLLATE_SYMB_HASH_SIZEMB
);
3530 symb_table
= (const int32_t *)
3531 _NL_CURRENT (LC_COLLATE
,
3532 _NL_COLLATE_SYMB_TABLEMB
);
3533 extra
= (const unsigned char *)
3534 _NL_CURRENT (LC_COLLATE
,
3535 _NL_COLLATE_SYMB_EXTRAMB
);
3537 /* Locate the character in the hashing table. */
3538 hash
= elem_hash (str
, c1
);
3541 elem
= hash
% table_size
;
3542 second
= hash
% (table_size
- 2);
3543 while (symb_table
[2 * elem
] != 0)
3545 /* First compare the hashing value. */
3546 if (symb_table
[2 * elem
] == hash
3547 && c1
== extra
[symb_table
[2 * elem
+ 1]]
3549 &extra
[symb_table
[2 * elem
+ 1]
3553 /* Yep, this is the entry. */
3554 idx
= symb_table
[2 * elem
+ 1];
3555 idx
+= 1 + extra
[idx
];
3563 if (symb_table
[2 * elem
] == 0)
3564 /* This is no valid character. */
3565 FREE_STACK_RETURN (REG_ECOLLATE
);
3567 /* Throw away the ] at the end of the equivalence
3571 /* Now add the multibyte character(s) we found
3574 XXX Note that this is not entirely correct.
3575 we would have to match multibyte sequences
3576 but this is not possible with the current
3577 implementation. Also, we have to match
3578 collating symbols, which expand to more than
3579 one file, as a whole and not allow the
3580 individual bytes. */
3583 range_start
= extra
[idx
];
3586 SET_LIST_BIT (extra
[idx
]);
3591 had_char_class
= false;
3601 had_char_class
= false;
3606 had_char_class
= false;
3612 /* Discard any (non)matching list bytes that are all 0 at the
3613 end of the map. Decrease the map-length byte too. */
3614 while ((int) b
[-1] > 0 && b
[b
[-1] - 1] == 0)
3623 if (syntax
& RE_NO_BK_PARENS
)
3630 if (syntax
& RE_NO_BK_PARENS
)
3637 if (syntax
& RE_NEWLINE_ALT
)
3644 if (syntax
& RE_NO_BK_VBAR
)
3651 if (syntax
& RE_INTERVALS
&& syntax
& RE_NO_BK_BRACES
)
3652 goto handle_interval
;
3658 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
3660 /* Do not translate the character after the \, so that we can
3661 distinguish, e.g., \B from \b, even if we normally would
3662 translate, e.g., B to b. */
3668 if (syntax
& RE_NO_BK_PARENS
)
3669 goto normal_backslash
;
3675 if (COMPILE_STACK_FULL
)
3677 RETALLOC (compile_stack
.stack
, compile_stack
.size
<< 1,
3678 compile_stack_elt_t
);
3679 if (compile_stack
.stack
== NULL
) return REG_ESPACE
;
3681 compile_stack
.size
<<= 1;
3684 /* These are the values to restore when we hit end of this
3685 group. They are all relative offsets, so that if the
3686 whole pattern moves because of realloc, they will still
3688 COMPILE_STACK_TOP
.begalt_offset
= begalt
- COMPILED_BUFFER_VAR
;
3689 COMPILE_STACK_TOP
.fixup_alt_jump
3690 = fixup_alt_jump
? fixup_alt_jump
- COMPILED_BUFFER_VAR
+ 1 : 0;
3691 COMPILE_STACK_TOP
.laststart_offset
= b
- COMPILED_BUFFER_VAR
;
3692 COMPILE_STACK_TOP
.regnum
= regnum
;
3694 /* We will eventually replace the 0 with the number of
3695 groups inner to this one. But do not push a
3696 start_memory for groups beyond the last one we can
3697 represent in the compiled pattern. */
3698 if (regnum
<= MAX_REGNUM
)
3700 COMPILE_STACK_TOP
.inner_group_offset
= b
3701 - COMPILED_BUFFER_VAR
+ 2;
3702 BUF_PUSH_3 (start_memory
, regnum
, 0);
3705 compile_stack
.avail
++;
3710 /* If we've reached MAX_REGNUM groups, then this open
3711 won't actually generate any code, so we'll have to
3712 clear pending_exact explicitly. */
3718 if (syntax
& RE_NO_BK_PARENS
) goto normal_backslash
;
3720 if (COMPILE_STACK_EMPTY
)
3722 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
3723 goto normal_backslash
;
3725 FREE_STACK_RETURN (REG_ERPAREN
);
3730 { /* Push a dummy failure point at the end of the
3731 alternative for a possible future
3732 `pop_failure_jump' to pop. See comments at
3733 `push_dummy_failure' in `re_match_2'. */
3734 BUF_PUSH (push_dummy_failure
);
3736 /* We allocated space for this jump when we assigned
3737 to `fixup_alt_jump', in the `handle_alt' case below. */
3738 STORE_JUMP (jump_past_alt
, fixup_alt_jump
, b
- 1);
3741 /* See similar code for backslashed left paren above. */
3742 if (COMPILE_STACK_EMPTY
)
3744 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
3747 FREE_STACK_RETURN (REG_ERPAREN
);
3750 /* Since we just checked for an empty stack above, this
3751 ``can't happen''. */
3752 assert (compile_stack
.avail
!= 0);
3754 /* We don't just want to restore into `regnum', because
3755 later groups should continue to be numbered higher,
3756 as in `(ab)c(de)' -- the second group is #2. */
3757 regnum_t this_group_regnum
;
3759 compile_stack
.avail
--;
3760 begalt
= COMPILED_BUFFER_VAR
+ COMPILE_STACK_TOP
.begalt_offset
;
3762 = COMPILE_STACK_TOP
.fixup_alt_jump
3763 ? COMPILED_BUFFER_VAR
+ COMPILE_STACK_TOP
.fixup_alt_jump
- 1
3765 laststart
= COMPILED_BUFFER_VAR
+ COMPILE_STACK_TOP
.laststart_offset
;
3766 this_group_regnum
= COMPILE_STACK_TOP
.regnum
;
3767 /* If we've reached MAX_REGNUM groups, then this open
3768 won't actually generate any code, so we'll have to
3769 clear pending_exact explicitly. */
3772 /* We're at the end of the group, so now we know how many
3773 groups were inside this one. */
3774 if (this_group_regnum
<= MAX_REGNUM
)
3776 UCHAR_T
*inner_group_loc
3777 = COMPILED_BUFFER_VAR
+ COMPILE_STACK_TOP
.inner_group_offset
;
3779 *inner_group_loc
= regnum
- this_group_regnum
;
3780 BUF_PUSH_3 (stop_memory
, this_group_regnum
,
3781 regnum
- this_group_regnum
);
3787 case '|': /* `\|'. */
3788 if (syntax
& RE_LIMITED_OPS
|| syntax
& RE_NO_BK_VBAR
)
3789 goto normal_backslash
;
3791 if (syntax
& RE_LIMITED_OPS
)
3794 /* Insert before the previous alternative a jump which
3795 jumps to this alternative if the former fails. */
3796 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
3797 INSERT_JUMP (on_failure_jump
, begalt
,
3798 b
+ 2 + 2 * OFFSET_ADDRESS_SIZE
);
3800 b
+= 1 + OFFSET_ADDRESS_SIZE
;
3802 /* The alternative before this one has a jump after it
3803 which gets executed if it gets matched. Adjust that
3804 jump so it will jump to this alternative's analogous
3805 jump (put in below, which in turn will jump to the next
3806 (if any) alternative's such jump, etc.). The last such
3807 jump jumps to the correct final destination. A picture:
3813 If we are at `b', then fixup_alt_jump right now points to a
3814 three-byte space after `a'. We'll put in the jump, set
3815 fixup_alt_jump to right after `b', and leave behind three
3816 bytes which we'll fill in when we get to after `c'. */
3819 STORE_JUMP (jump_past_alt
, fixup_alt_jump
, b
);
3821 /* Mark and leave space for a jump after this alternative,
3822 to be filled in later either by next alternative or
3823 when know we're at the end of a series of alternatives. */
3825 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
3826 b
+= 1 + OFFSET_ADDRESS_SIZE
;
3834 /* If \{ is a literal. */
3835 if (!(syntax
& RE_INTERVALS
)
3836 /* If we're at `\{' and it's not the open-interval
3838 || (syntax
& RE_NO_BK_BRACES
))
3839 goto normal_backslash
;
3843 /* If got here, then the syntax allows intervals. */
3845 /* At least (most) this many matches must be made. */
3846 int lower_bound
= -1, upper_bound
= -1;
3848 /* Place in the uncompiled pattern (i.e., just after
3849 the '{') to go back to if the interval is invalid. */
3850 const CHAR_T
*beg_interval
= p
;
3853 goto invalid_interval
;
3855 GET_UNSIGNED_NUMBER (lower_bound
);
3859 GET_UNSIGNED_NUMBER (upper_bound
);
3860 if (upper_bound
< 0)
3861 upper_bound
= RE_DUP_MAX
;
3864 /* Interval such as `{1}' => match exactly once. */
3865 upper_bound
= lower_bound
;
3867 if (! (0 <= lower_bound
&& lower_bound
<= upper_bound
))
3868 goto invalid_interval
;
3870 if (!(syntax
& RE_NO_BK_BRACES
))
3872 if (c
!= '\\' || p
== pend
)
3873 goto invalid_interval
;
3878 goto invalid_interval
;
3880 /* If it's invalid to have no preceding re. */
3883 if (syntax
& RE_CONTEXT_INVALID_OPS
3884 && !(syntax
& RE_INVALID_INTERVAL_ORD
))
3885 FREE_STACK_RETURN (REG_BADRPT
);
3886 else if (syntax
& RE_CONTEXT_INDEP_OPS
)
3889 goto unfetch_interval
;
3892 /* We just parsed a valid interval. */
3894 if (RE_DUP_MAX
< upper_bound
)
3895 FREE_STACK_RETURN (REG_BADBR
);
3897 /* If the upper bound is zero, don't want to succeed at
3898 all; jump from `laststart' to `b + 3', which will be
3899 the end of the buffer after we insert the jump. */
3900 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE'
3901 instead of 'b + 3'. */
3902 if (upper_bound
== 0)
3904 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE
);
3905 INSERT_JUMP (jump
, laststart
, b
+ 1
3906 + OFFSET_ADDRESS_SIZE
);
3907 b
+= 1 + OFFSET_ADDRESS_SIZE
;
3910 /* Otherwise, we have a nontrivial interval. When
3911 we're all done, the pattern will look like:
3912 set_number_at <jump count> <upper bound>
3913 set_number_at <succeed_n count> <lower bound>
3914 succeed_n <after jump addr> <succeed_n count>
3916 jump_n <succeed_n addr> <jump count>
3917 (The upper bound and `jump_n' are omitted if
3918 `upper_bound' is 1, though.) */
3920 { /* If the upper bound is > 1, we need to insert
3921 more at the end of the loop. */
3922 unsigned nbytes
= 2 + 4 * OFFSET_ADDRESS_SIZE
+
3923 (upper_bound
> 1) * (2 + 4 * OFFSET_ADDRESS_SIZE
);
3925 GET_BUFFER_SPACE (nbytes
);
3927 /* Initialize lower bound of the `succeed_n', even
3928 though it will be set during matching by its
3929 attendant `set_number_at' (inserted next),
3930 because `re_compile_fastmap' needs to know.
3931 Jump to the `jump_n' we might insert below. */
3932 INSERT_JUMP2 (succeed_n
, laststart
,
3933 b
+ 1 + 2 * OFFSET_ADDRESS_SIZE
3934 + (upper_bound
> 1) * (1 + 2 * OFFSET_ADDRESS_SIZE
)
3936 b
+= 1 + 2 * OFFSET_ADDRESS_SIZE
;
3938 /* Code to initialize the lower bound. Insert
3939 before the `succeed_n'. The `5' is the last two
3940 bytes of this `set_number_at', plus 3 bytes of
3941 the following `succeed_n'. */
3942 /* ifdef WCHAR, The '1+2*OFFSET_ADDRESS_SIZE'
3943 is the 'set_number_at', plus '1+OFFSET_ADDRESS_SIZE'
3944 of the following `succeed_n'. */
3945 PREFIX(insert_op2
) (set_number_at
, laststart
, 1
3946 + 2 * OFFSET_ADDRESS_SIZE
, lower_bound
, b
);
3947 b
+= 1 + 2 * OFFSET_ADDRESS_SIZE
;
3949 if (upper_bound
> 1)
3950 { /* More than one repetition is allowed, so
3951 append a backward jump to the `succeed_n'
3952 that starts this interval.
3954 When we've reached this during matching,
3955 we'll have matched the interval once, so
3956 jump back only `upper_bound - 1' times. */
3957 STORE_JUMP2 (jump_n
, b
, laststart
3958 + 2 * OFFSET_ADDRESS_SIZE
+ 1,
3960 b
+= 1 + 2 * OFFSET_ADDRESS_SIZE
;
3962 /* The location we want to set is the second
3963 parameter of the `jump_n'; that is `b-2' as
3964 an absolute address. `laststart' will be
3965 the `set_number_at' we're about to insert;
3966 `laststart+3' the number to set, the source
3967 for the relative address. But we are
3968 inserting into the middle of the pattern --
3969 so everything is getting moved up by 5.
3970 Conclusion: (b - 2) - (laststart + 3) + 5,
3971 i.e., b - laststart.
3973 We insert this at the beginning of the loop
3974 so that if we fail during matching, we'll
3975 reinitialize the bounds. */
3976 PREFIX(insert_op2
) (set_number_at
, laststart
,
3978 upper_bound
- 1, b
);
3979 b
+= 1 + 2 * OFFSET_ADDRESS_SIZE
;
3986 if (!(syntax
& RE_INVALID_INTERVAL_ORD
))
3987 FREE_STACK_RETURN (p
== pend
? REG_EBRACE
: REG_BADBR
);
3989 /* Match the characters as literals. */
3992 if (syntax
& RE_NO_BK_BRACES
)
3995 goto normal_backslash
;
3999 /* There is no way to specify the before_dot and after_dot
4000 operators. rms says this is ok. --karl */
4008 BUF_PUSH_2 (syntaxspec
, syntax_spec_code
[c
]);
4014 BUF_PUSH_2 (notsyntaxspec
, syntax_spec_code
[c
]);
4020 if (syntax
& RE_NO_GNU_OPS
)
4023 BUF_PUSH (wordchar
);
4028 if (syntax
& RE_NO_GNU_OPS
)
4031 BUF_PUSH (notwordchar
);
4036 if (syntax
& RE_NO_GNU_OPS
)
4042 if (syntax
& RE_NO_GNU_OPS
)
4048 if (syntax
& RE_NO_GNU_OPS
)
4050 BUF_PUSH (wordbound
);
4054 if (syntax
& RE_NO_GNU_OPS
)
4056 BUF_PUSH (notwordbound
);
4060 if (syntax
& RE_NO_GNU_OPS
)
4066 if (syntax
& RE_NO_GNU_OPS
)
4071 case '1': case '2': case '3': case '4': case '5':
4072 case '6': case '7': case '8': case '9':
4073 if (syntax
& RE_NO_BK_REFS
)
4079 FREE_STACK_RETURN (REG_ESUBREG
);
4081 /* Can't back reference to a subexpression if inside of it. */
4082 if (group_in_compile_stack (compile_stack
, (regnum_t
) c1
))
4086 BUF_PUSH_2 (duplicate
, c1
);
4092 if (syntax
& RE_BK_PLUS_QM
)
4095 goto normal_backslash
;
4099 /* You might think it would be useful for \ to mean
4100 not to translate; but if we don't translate it
4101 it will never match anything. */
4109 /* Expects the character in `c'. */
4111 /* If no exactn currently being built. */
4114 /* If last exactn handle binary(or character) and
4115 new exactn handle character(or binary). */
4116 || is_exactn_bin
!= is_binary
[p
- 1 - pattern
]
4119 /* If last exactn not at current position. */
4120 || pending_exact
+ *pending_exact
+ 1 != b
4122 /* We have only one byte following the exactn for the count. */
4123 || *pending_exact
== (1 << BYTEWIDTH
) - 1
4125 /* If followed by a repetition operator. */
4126 || *p
== '*' || *p
== '^'
4127 || ((syntax
& RE_BK_PLUS_QM
)
4128 ? *p
== '\\' && (p
[1] == '+' || p
[1] == '?')
4129 : (*p
== '+' || *p
== '?'))
4130 || ((syntax
& RE_INTERVALS
)
4131 && ((syntax
& RE_NO_BK_BRACES
)
4133 : (p
[0] == '\\' && p
[1] == '{'))))
4135 /* Start building a new exactn. */
4140 /* Is this exactn binary data or character? */
4141 is_exactn_bin
= is_binary
[p
- 1 - pattern
];
4143 BUF_PUSH_2 (exactn_bin
, 0);
4145 BUF_PUSH_2 (exactn
, 0);
4147 BUF_PUSH_2 (exactn
, 0);
4149 pending_exact
= b
- 1;
4156 } /* while p != pend */
4159 /* Through the pattern now. */
4162 STORE_JUMP (jump_past_alt
, fixup_alt_jump
, b
);
4164 if (!COMPILE_STACK_EMPTY
)
4165 FREE_STACK_RETURN (REG_EPAREN
);
4167 /* If we don't want backtracking, force success
4168 the first time we reach the end of the compiled pattern. */
4169 if (syntax
& RE_NO_POSIX_BACKTRACKING
)
4177 free (compile_stack
.stack
);
4179 /* We have succeeded; set the length of the buffer. */
4181 bufp
->used
= (uintptr_t) b
- (uintptr_t) COMPILED_BUFFER_VAR
;
4183 bufp
->used
= b
- bufp
->buffer
;
4189 DEBUG_PRINT1 ("\nCompiled pattern: \n");
4190 PREFIX(print_compiled_pattern
) (bufp
);
4194 #ifndef MATCH_MAY_ALLOCATE
4195 /* Initialize the failure stack to the largest possible stack. This
4196 isn't necessary unless we're trying to avoid calling alloca in
4197 the search and match routines. */
4199 int num_regs
= bufp
->re_nsub
+ 1;
4201 /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
4202 is strictly greater than re_max_failures, the largest possible stack
4203 is 2 * re_max_failures failure points. */
4204 if (fail_stack
.size
< (2 * re_max_failures
* MAX_FAILURE_ITEMS
))
4206 fail_stack
.size
= (2 * re_max_failures
* MAX_FAILURE_ITEMS
);
4209 if (! fail_stack
.stack
)
4211 = (PREFIX(fail_stack_elt_t
) *) xmalloc (fail_stack
.size
4212 * sizeof (PREFIX(fail_stack_elt_t
)));
4215 = (PREFIX(fail_stack_elt_t
) *) xrealloc (fail_stack
.stack
,
4217 * sizeof (PREFIX(fail_stack_elt_t
))));
4218 # else /* not emacs */
4219 if (! fail_stack
.stack
)
4221 = (PREFIX(fail_stack_elt_t
) *) malloc (fail_stack
.size
4222 * sizeof (PREFIX(fail_stack_elt_t
)));
4225 = (PREFIX(fail_stack_elt_t
) *) realloc (fail_stack
.stack
,
4227 * sizeof (PREFIX(fail_stack_elt_t
))));
4228 # endif /* not emacs */
4231 PREFIX(regex_grow_registers
) (num_regs
);
4233 #endif /* not MATCH_MAY_ALLOCATE */
4236 } /* regex_compile */
4238 /* Subroutines for `regex_compile'. */
4240 /* Store OP at LOC followed by two-byte integer parameter ARG. */
4241 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4249 *loc
= (UCHAR_T
) op
;
4250 STORE_NUMBER (loc
+ 1, arg
);
4254 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
4255 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4263 *loc
= (UCHAR_T
) op
;
4264 STORE_NUMBER (loc
+ 1, arg1
);
4265 STORE_NUMBER (loc
+ 1 + OFFSET_ADDRESS_SIZE
, arg2
);
4269 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
4270 for OP followed by two-byte integer parameter ARG. */
4271 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4274 PREFIX(insert_op1
) (
4280 register UCHAR_T
*pfrom
= end
;
4281 register UCHAR_T
*pto
= end
+ 1 + OFFSET_ADDRESS_SIZE
;
4283 while (pfrom
!= loc
)
4286 PREFIX(store_op1
) (op
, loc
, arg
);
4290 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
4291 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4294 PREFIX(insert_op2
) (
4300 register UCHAR_T
*pfrom
= end
;
4301 register UCHAR_T
*pto
= end
+ 1 + 2 * OFFSET_ADDRESS_SIZE
;
4303 while (pfrom
!= loc
)
4306 PREFIX(store_op2
) (op
, loc
, arg1
, arg2
);
4310 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
4311 after an alternative or a begin-subexpression. We assume there is at
4312 least one character before the ^. */
4315 PREFIX(at_begline_loc_p
) (
4316 const CHAR_T
*pattern
, const CHAR_T
*p
,
4317 reg_syntax_t syntax
)
4319 const CHAR_T
*prev
= p
- 2;
4320 boolean prev_prev_backslash
= prev
> pattern
&& prev
[-1] == '\\';
4323 /* After a subexpression? */
4324 (*prev
== '(' && (syntax
& RE_NO_BK_PARENS
|| prev_prev_backslash
))
4325 /* After an alternative? */
4326 || (*prev
== '|' && (syntax
& RE_NO_BK_VBAR
|| prev_prev_backslash
));
4330 /* The dual of at_begline_loc_p. This one is for $. We assume there is
4331 at least one character after the $, i.e., `P < PEND'. */
4334 PREFIX(at_endline_loc_p
) (
4335 const CHAR_T
*p
, const CHAR_T
*pend
,
4336 reg_syntax_t syntax
)
4338 const CHAR_T
*next
= p
;
4339 boolean next_backslash
= *next
== '\\';
4340 const CHAR_T
*next_next
= p
+ 1 < pend
? p
+ 1 : 0;
4343 /* Before a subexpression? */
4344 (syntax
& RE_NO_BK_PARENS
? *next
== ')'
4345 : next_backslash
&& next_next
&& *next_next
== ')')
4346 /* Before an alternative? */
4347 || (syntax
& RE_NO_BK_VBAR
? *next
== '|'
4348 : next_backslash
&& next_next
&& *next_next
== '|');
4351 #else /* not INSIDE_RECURSION */
4353 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
4354 false if it's not. */
4357 group_in_compile_stack (
4358 compile_stack_type compile_stack
,
4363 for (this_element
= compile_stack
.avail
- 1;
4366 if (compile_stack
.stack
[this_element
].regnum
== regnum
)
4371 #endif /* not INSIDE_RECURSION */
4373 #ifdef INSIDE_RECURSION
4376 /* This insert space, which size is "num", into the pattern at "loc".
4377 "end" must point the end of the allocated buffer. */
4384 register CHAR_T
*pto
= end
;
4385 register CHAR_T
*pfrom
= end
- num
;
4387 while (pfrom
>= loc
)
4393 static reg_errcode_t
4395 CHAR_T range_start_char
,
4396 const CHAR_T
**p_ptr
, const CHAR_T
*pend
,
4397 __RE_TRANSLATE_TYPE translate
,
4398 reg_syntax_t syntax
,
4399 CHAR_T
*b
, CHAR_T
*char_set
)
4401 const CHAR_T
*p
= *p_ptr
;
4402 CHAR_T range_start
, range_end
;
4406 uint32_t start_val
, end_val
;
4412 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
4415 const char *collseq
= (const char *) _NL_CURRENT(LC_COLLATE
,
4416 _NL_COLLATE_COLLSEQWC
);
4417 const unsigned char *extra
= (const unsigned char *)
4418 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
4420 if (range_start_char
< -1)
4422 /* range_start is a collating symbol. */
4424 /* Retreive the index and get collation sequence value. */
4425 wextra
= (int32_t*)(extra
+ char_set
[-range_start_char
]);
4426 start_val
= wextra
[1 + *wextra
];
4429 start_val
= collseq_table_lookup(collseq
, TRANSLATE(range_start_char
));
4431 end_val
= collseq_table_lookup (collseq
, TRANSLATE (p
[0]));
4433 /* Report an error if the range is empty and the syntax prohibits
4435 ret
= ((syntax
& RE_NO_EMPTY_RANGES
)
4436 && (start_val
> end_val
))? REG_ERANGE
: REG_NOERROR
;
4438 /* Insert space to the end of the char_ranges. */
4439 insert_space(2, b
- char_set
[5] - 2, b
- 1);
4440 *(b
- char_set
[5] - 2) = (wchar_t)start_val
;
4441 *(b
- char_set
[5] - 1) = (wchar_t)end_val
;
4442 char_set
[4]++; /* ranges_index */
4447 range_start
= (range_start_char
>= 0)? TRANSLATE (range_start_char
):
4449 range_end
= TRANSLATE (p
[0]);
4450 /* Report an error if the range is empty and the syntax prohibits
4452 ret
= ((syntax
& RE_NO_EMPTY_RANGES
)
4453 && (range_start
> range_end
))? REG_ERANGE
: REG_NOERROR
;
4455 /* Insert space to the end of the char_ranges. */
4456 insert_space(2, b
- char_set
[5] - 2, b
- 1);
4457 *(b
- char_set
[5] - 2) = range_start
;
4458 *(b
- char_set
[5] - 1) = range_end
;
4459 char_set
[4]++; /* ranges_index */
4461 /* Have to increment the pointer into the pattern string, so the
4462 caller isn't still at the ending character. */
4468 /* Read the ending character of a range (in a bracket expression) from the
4469 uncompiled pattern *P_PTR (which ends at PEND). We assume the
4470 starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
4471 Then we set the translation of all bits between the starting and
4472 ending characters (inclusive) in the compiled pattern B.
4474 Return an error code.
4476 We use these short variable names so we can use the same macros as
4477 `regex_compile' itself. */
4479 static reg_errcode_t
4480 byte_compile_range (
4481 unsigned int range_start_char
,
4482 const char **p_ptr
, const char *pend
,
4483 __RE_TRANSLATE_TYPE translate
,
4484 reg_syntax_t syntax
,
4488 const char *p
= *p_ptr
;
4491 const unsigned char *collseq
;
4492 unsigned int start_colseq
;
4493 unsigned int end_colseq
;
4501 /* Have to increment the pointer into the pattern string, so the
4502 caller isn't still at the ending character. */
4505 /* Report an error if the range is empty and the syntax prohibits this. */
4506 ret
= syntax
& RE_NO_EMPTY_RANGES
? REG_ERANGE
: REG_NOERROR
;
4509 collseq
= (const unsigned char *) _NL_CURRENT (LC_COLLATE
,
4510 _NL_COLLATE_COLLSEQMB
);
4512 start_colseq
= collseq
[(unsigned char) TRANSLATE (range_start_char
)];
4513 end_colseq
= collseq
[(unsigned char) TRANSLATE (p
[0])];
4514 for (this_char
= 0; this_char
<= (unsigned char) -1; ++this_char
)
4516 unsigned int this_colseq
= collseq
[(unsigned char) TRANSLATE (this_char
)];
4518 if (start_colseq
<= this_colseq
&& this_colseq
<= end_colseq
)
4520 SET_LIST_BIT (TRANSLATE (this_char
));
4525 /* Here we see why `this_char' has to be larger than an `unsigned
4526 char' -- we would otherwise go into an infinite loop, since all
4527 characters <= 0xff. */
4528 range_start_char
= TRANSLATE (range_start_char
);
4529 /* TRANSLATE(p[0]) is casted to char (not unsigned char) in TRANSLATE,
4530 and some compilers cast it to int implicitly, so following for_loop
4531 may fall to (almost) infinite loop.
4532 e.g. If translate[p[0]] = 0xff, end_char may equals to 0xffffffff.
4533 To avoid this, we cast p[0] to unsigned int and truncate it. */
4534 end_char
= ((unsigned)TRANSLATE(p
[0]) & ((1 << BYTEWIDTH
) - 1));
4536 for (this_char
= range_start_char
; this_char
<= end_char
; ++this_char
)
4538 SET_LIST_BIT (TRANSLATE (this_char
));
4547 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4548 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4549 characters can start a string that matches the pattern. This fastmap
4550 is used by re_search to skip quickly over impossible starting points.
4552 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4553 area as BUFP->fastmap.
4555 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4558 Returns 0 if we succeed, -2 if an internal error. */
4561 /* local function for re_compile_fastmap.
4562 truncate wchar_t character to char. */
4563 static unsigned char truncate_wchar (CHAR_T c
)
4565 unsigned char buf
[MB_CUR_MAX
];
4568 memset (&state
, '\0', sizeof (state
));
4570 retval
= __wcrtomb (buf
, c
, &state
);
4572 retval
= wcrtomb (buf
, c
, &state
);
4574 return retval
> 0 ? buf
[0] : (unsigned char) c
;
4579 PREFIX(re_compile_fastmap
) (struct re_pattern_buffer
*bufp
)
4582 #ifdef MATCH_MAY_ALLOCATE
4583 PREFIX(fail_stack_type
) fail_stack
;
4585 #ifndef REGEX_MALLOC
4589 register char *fastmap
= bufp
->fastmap
;
4592 /* We need to cast pattern to (wchar_t*), because we casted this compiled
4593 pattern to (char*) in regex_compile. */
4594 UCHAR_T
*pattern
= (UCHAR_T
*)bufp
->buffer
;
4595 register UCHAR_T
*pend
= (UCHAR_T
*) (bufp
->buffer
+ bufp
->used
);
4597 UCHAR_T
*pattern
= bufp
->buffer
;
4598 register UCHAR_T
*pend
= pattern
+ bufp
->used
;
4600 UCHAR_T
*p
= pattern
;
4603 /* This holds the pointer to the failure stack, when
4604 it is allocated relocatably. */
4605 fail_stack_elt_t
*failure_stack_ptr
;
4608 /* Assume that each path through the pattern can be null until
4609 proven otherwise. We set this false at the bottom of switch
4610 statement, to which we get only if a particular path doesn't
4611 match the empty string. */
4612 boolean path_can_be_null
= true;
4614 /* We aren't doing a `succeed_n' to begin with. */
4615 boolean succeed_n_p
= false;
4617 assert (fastmap
!= NULL
&& p
!= NULL
);
4620 bzero (fastmap
, 1 << BYTEWIDTH
); /* Assume nothing's valid. */
4621 bufp
->fastmap_accurate
= 1; /* It will be when we're done. */
4622 bufp
->can_be_null
= 0;
4626 if (p
== pend
|| *p
== succeed
)
4628 /* We have reached the (effective) end of pattern. */
4629 if (!FAIL_STACK_EMPTY ())
4631 bufp
->can_be_null
|= path_can_be_null
;
4633 /* Reset for next path. */
4634 path_can_be_null
= true;
4636 p
= fail_stack
.stack
[--fail_stack
.avail
].pointer
;
4644 /* We should never be about to go beyond the end of the pattern. */
4647 switch (SWITCH_ENUM_CAST ((re_opcode_t
) *p
++))
4650 /* I guess the idea here is to simply not bother with a fastmap
4651 if a backreference is used, since it's too hard to figure out
4652 the fastmap for the corresponding group. Setting
4653 `can_be_null' stops `re_search_2' from using the fastmap, so
4654 that is all we do. */
4656 bufp
->can_be_null
= 1;
4660 /* Following are the cases which match a character. These end
4665 fastmap
[truncate_wchar(p
[1])] = 1;
4679 /* It is hard to distinguish fastmap from (multi byte) characters
4680 which depends on current locale. */
4685 bufp
->can_be_null
= 1;
4689 for (j
= *p
++ * BYTEWIDTH
- 1; j
>= 0; j
--)
4690 if (p
[j
/ BYTEWIDTH
] & (1 << (j
% BYTEWIDTH
)))
4696 /* Chars beyond end of map must be allowed. */
4697 for (j
= *p
* BYTEWIDTH
; j
< (1 << BYTEWIDTH
); j
++)
4700 for (j
= *p
++ * BYTEWIDTH
- 1; j
>= 0; j
--)
4701 if (!(p
[j
/ BYTEWIDTH
] & (1 << (j
% BYTEWIDTH
))))
4707 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
4708 if (SYNTAX (j
) == Sword
)
4714 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
4715 if (SYNTAX (j
) != Sword
)
4722 int fastmap_newline
= fastmap
['\n'];
4724 /* `.' matches anything ... */
4725 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
4728 /* ... except perhaps newline. */
4729 if (!(bufp
->syntax
& RE_DOT_NEWLINE
))
4730 fastmap
['\n'] = fastmap_newline
;
4732 /* Return if we have already set `can_be_null'; if we have,
4733 then the fastmap is irrelevant. Something's wrong here. */
4734 else if (bufp
->can_be_null
)
4737 /* Otherwise, have to check alternative paths. */
4744 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
4745 if (SYNTAX (j
) == (enum syntaxcode
) k
)
4752 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
4753 if (SYNTAX (j
) != (enum syntaxcode
) k
)
4758 /* All cases after this match the empty string. These end with
4778 case push_dummy_failure
:
4783 case pop_failure_jump
:
4784 case maybe_pop_jump
:
4787 case dummy_failure_jump
:
4788 EXTRACT_NUMBER_AND_INCR (j
, p
);
4793 /* Jump backward implies we just went through the body of a
4794 loop and matched nothing. Opcode jumped to should be
4795 `on_failure_jump' or `succeed_n'. Just treat it like an
4796 ordinary jump. For a * loop, it has pushed its failure
4797 point already; if so, discard that as redundant. */
4798 if ((re_opcode_t
) *p
!= on_failure_jump
4799 && (re_opcode_t
) *p
!= succeed_n
)
4803 EXTRACT_NUMBER_AND_INCR (j
, p
);
4806 /* If what's on the stack is where we are now, pop it. */
4807 if (!FAIL_STACK_EMPTY ()
4808 && fail_stack
.stack
[fail_stack
.avail
- 1].pointer
== p
)
4814 case on_failure_jump
:
4815 case on_failure_keep_string_jump
:
4816 handle_on_failure_jump
:
4817 EXTRACT_NUMBER_AND_INCR (j
, p
);
4819 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
4820 end of the pattern. We don't want to push such a point,
4821 since when we restore it above, entering the switch will
4822 increment `p' past the end of the pattern. We don't need
4823 to push such a point since we obviously won't find any more
4824 fastmap entries beyond `pend'. Such a pattern can match
4825 the null string, though. */
4828 if (!PUSH_PATTERN_OP (p
+ j
, fail_stack
))
4830 RESET_FAIL_STACK ();
4835 bufp
->can_be_null
= 1;
4839 EXTRACT_NUMBER_AND_INCR (k
, p
); /* Skip the n. */
4840 succeed_n_p
= false;
4847 /* Get to the number of times to succeed. */
4848 p
+= OFFSET_ADDRESS_SIZE
;
4850 /* Increment p past the n for when k != 0. */
4851 EXTRACT_NUMBER_AND_INCR (k
, p
);
4854 p
-= 2 * OFFSET_ADDRESS_SIZE
;
4855 succeed_n_p
= true; /* Spaghetti code alert. */
4856 goto handle_on_failure_jump
;
4862 p
+= 2 * OFFSET_ADDRESS_SIZE
;
4873 abort (); /* We have listed all the cases. */
4876 /* Getting here means we have found the possible starting
4877 characters for one path of the pattern -- and that the empty
4878 string does not match. We need not follow this path further.
4879 Instead, look at the next alternative (remembered on the
4880 stack), or quit if no more. The test at the top of the loop
4881 does these things. */
4882 path_can_be_null
= false;
4886 /* Set `can_be_null' for the last path (also the first path, if the
4887 pattern is empty). */
4888 bufp
->can_be_null
|= path_can_be_null
;
4891 RESET_FAIL_STACK ();
4895 #else /* not INSIDE_RECURSION */
4898 re_compile_fastmap (struct re_pattern_buffer
*bufp
)
4901 if (MB_CUR_MAX
!= 1)
4902 return wcs_re_compile_fastmap(bufp
);
4904 return byte_re_compile_fastmap(bufp
);
4906 libc_hidden_def(re_compile_fastmap
)
4909 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
4910 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
4911 this memory for recording register information. STARTS and ENDS
4912 must be allocated using the malloc library routine, and must each
4913 be at least NUM_REGS * sizeof (regoff_t) bytes long.
4915 If NUM_REGS == 0, then subsequent matches should allocate their own
4918 Unless this function is called, the first search or match using
4919 PATTERN_BUFFER will allocate its own register data, without
4920 freeing the old data. */
4924 struct re_pattern_buffer
*bufp
,
4925 struct re_registers
*regs
,
4927 regoff_t
*starts
, regoff_t
*ends
)
4931 bufp
->regs_allocated
= REGS_REALLOCATE
;
4932 regs
->num_regs
= num_regs
;
4933 regs
->start
= starts
;
4938 bufp
->regs_allocated
= REGS_UNALLOCATED
;
4940 regs
->start
= regs
->end
= (regoff_t
*) 0;
4944 /* Searching routines. */
4946 /* Like re_search_2, below, but only one string is specified, and
4947 doesn't let you say where to stop matching. */
4951 struct re_pattern_buffer
*bufp
,
4953 int size
, int startpos
, int range
,
4954 struct re_registers
*regs
)
4956 return re_search_2 (bufp
, NULL
, 0, string
, size
, startpos
, range
,
4959 libc_hidden_def(re_search
)
4962 /* Using the compiled pattern in BUFP->buffer, first tries to match the
4963 virtual concatenation of STRING1 and STRING2, starting first at index
4964 STARTPOS, then at STARTPOS + 1, and so on.
4966 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
4968 RANGE is how far to scan while trying to match. RANGE = 0 means try
4969 only at STARTPOS; in general, the last start tried is STARTPOS +
4972 In REGS, return the indices of the virtual concatenation of STRING1
4973 and STRING2 that matched the entire BUFP->buffer and its contained
4976 Do not consider matching one past the index STOP in the virtual
4977 concatenation of STRING1 and STRING2.
4979 We return either the position in the strings at which the match was
4980 found, -1 if no match, or -2 if error (such as failure
4985 struct re_pattern_buffer
*bufp
,
4986 const char *string1
, int size1
,
4987 const char *string2
, int size2
,
4990 struct re_registers
*regs
,
4994 if (MB_CUR_MAX
!= 1)
4995 return wcs_re_search_2 (bufp
, string1
, size1
, string2
, size2
, startpos
,
4998 return byte_re_search_2 (bufp
, string1
, size1
, string2
, size2
, startpos
,
5001 libc_hidden_def(re_search_2
)
5003 #endif /* not INSIDE_RECURSION */
5005 #ifdef INSIDE_RECURSION
5007 #ifdef MATCH_MAY_ALLOCATE
5008 # define FREE_VAR(var) if (var) REGEX_FREE (var); var = NULL
5010 # define FREE_VAR(var) free (var); var = NULL
5014 # define MAX_ALLOCA_SIZE 2000
5016 # define FREE_WCS_BUFFERS() \
5018 if (size1 > MAX_ALLOCA_SIZE) \
5020 free (wcs_string1); \
5021 free (mbs_offset1); \
5025 FREE_VAR (wcs_string1); \
5026 FREE_VAR (mbs_offset1); \
5028 if (size2 > MAX_ALLOCA_SIZE) \
5030 free (wcs_string2); \
5031 free (mbs_offset2); \
5035 FREE_VAR (wcs_string2); \
5036 FREE_VAR (mbs_offset2); \
5044 PREFIX(re_search_2
) (
5045 struct re_pattern_buffer
*bufp
,
5046 const char *string1
, int size1
,
5047 const char *string2
, int size2
,
5050 struct re_registers
*regs
,
5054 register char *fastmap
= bufp
->fastmap
;
5055 register __RE_TRANSLATE_TYPE translate
= bufp
->translate
;
5056 int total_size
= size1
+ size2
;
5057 int endpos
= startpos
+ range
;
5059 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5060 wchar_t *wcs_string1
= NULL
, *wcs_string2
= NULL
;
5061 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5062 int wcs_size1
= 0, wcs_size2
= 0;
5063 /* offset buffer for optimization. See convert_mbs_to_wc. */
5064 int *mbs_offset1
= NULL
, *mbs_offset2
= NULL
;
5065 /* They hold whether each wchar_t is binary data or not. */
5066 char *is_binary
= NULL
;
5069 /* Check for out-of-range STARTPOS. */
5070 if (startpos
< 0 || startpos
> total_size
)
5073 /* Fix up RANGE if it might eventually take us outside
5074 the virtual concatenation of STRING1 and STRING2.
5075 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
5077 range
= 0 - startpos
;
5078 else if (endpos
> total_size
)
5079 range
= total_size
- startpos
;
5081 /* If the search isn't to be a backwards one, don't waste time in a
5082 search for a pattern that must be anchored. */
5083 if (bufp
->used
> 0 && range
> 0
5084 && ((re_opcode_t
) bufp
->buffer
[0] == begbuf
5085 /* `begline' is like `begbuf' if it cannot match at newlines. */
5086 || ((re_opcode_t
) bufp
->buffer
[0] == begline
5087 && !bufp
->newline_anchor
)))
5096 /* In a forward search for something that starts with \=.
5097 don't keep searching past point. */
5098 if (bufp
->used
> 0 && (re_opcode_t
) bufp
->buffer
[0] == at_dot
&& range
> 0)
5100 range
= PT
- startpos
;
5106 /* Update the fastmap now if not correct already. */
5107 if (fastmap
&& !bufp
->fastmap_accurate
)
5108 if (re_compile_fastmap (bufp
) == -2)
5112 /* Allocate wchar_t array for wcs_string1 and wcs_string2 and
5113 fill them with converted string. */
5116 if (size1
> MAX_ALLOCA_SIZE
)
5118 wcs_string1
= TALLOC (size1
+ 1, CHAR_T
);
5119 mbs_offset1
= TALLOC (size1
+ 1, int);
5120 is_binary
= TALLOC (size1
+ 1, char);
5124 wcs_string1
= REGEX_TALLOC (size1
+ 1, CHAR_T
);
5125 mbs_offset1
= REGEX_TALLOC (size1
+ 1, int);
5126 is_binary
= REGEX_TALLOC (size1
+ 1, char);
5128 if (!wcs_string1
|| !mbs_offset1
|| !is_binary
)
5130 if (size1
> MAX_ALLOCA_SIZE
)
5138 FREE_VAR (wcs_string1
);
5139 FREE_VAR (mbs_offset1
);
5140 FREE_VAR (is_binary
);
5144 wcs_size1
= convert_mbs_to_wcs(wcs_string1
, string1
, size1
,
5145 mbs_offset1
, is_binary
);
5146 wcs_string1
[wcs_size1
] = L
'\0'; /* for a sentinel */
5147 if (size1
> MAX_ALLOCA_SIZE
)
5150 FREE_VAR (is_binary
);
5154 if (size2
> MAX_ALLOCA_SIZE
)
5156 wcs_string2
= TALLOC (size2
+ 1, CHAR_T
);
5157 mbs_offset2
= TALLOC (size2
+ 1, int);
5158 is_binary
= TALLOC (size2
+ 1, char);
5162 wcs_string2
= REGEX_TALLOC (size2
+ 1, CHAR_T
);
5163 mbs_offset2
= REGEX_TALLOC (size2
+ 1, int);
5164 is_binary
= REGEX_TALLOC (size2
+ 1, char);
5166 if (!wcs_string2
|| !mbs_offset2
|| !is_binary
)
5168 FREE_WCS_BUFFERS ();
5169 if (size2
> MAX_ALLOCA_SIZE
)
5172 FREE_VAR (is_binary
);
5175 wcs_size2
= convert_mbs_to_wcs(wcs_string2
, string2
, size2
,
5176 mbs_offset2
, is_binary
);
5177 wcs_string2
[wcs_size2
] = L
'\0'; /* for a sentinel */
5178 if (size2
> MAX_ALLOCA_SIZE
)
5181 FREE_VAR (is_binary
);
5186 /* Loop through the string, looking for a place to start matching. */
5189 /* If a fastmap is supplied, skip quickly over characters that
5190 cannot be the start of a match. If the pattern can match the
5191 null string, however, we don't need to skip characters; we want
5192 the first null string. */
5193 if (fastmap
&& startpos
< total_size
&& !bufp
->can_be_null
)
5195 if (range
> 0) /* Searching forwards. */
5197 register const char *d
;
5198 register int lim
= 0;
5201 if (startpos
< size1
&& startpos
+ range
>= size1
)
5202 lim
= range
- (size1
- startpos
);
5204 d
= (startpos
>= size1
? string2
- size1
: string1
) + startpos
;
5206 /* Written out as an if-else to avoid testing `translate'
5210 && !fastmap
[(unsigned char)
5211 translate
[(unsigned char) *d
++]])
5214 while (range
> lim
&& !fastmap
[(unsigned char) *d
++])
5217 startpos
+= irange
- range
;
5219 else /* Searching backwards. */
5221 register CHAR_T c
= (size1
== 0 || startpos
>= size1
5222 ? string2
[startpos
- size1
]
5223 : string1
[startpos
]);
5225 if (!fastmap
[(unsigned char) TRANSLATE (c
)])
5230 /* If can't match the null string, and that's all we have left, fail. */
5231 if (range
>= 0 && startpos
== total_size
&& fastmap
5232 && !bufp
->can_be_null
)
5235 FREE_WCS_BUFFERS ();
5241 val
= wcs_re_match_2_internal (bufp
, string1
, size1
, string2
,
5242 size2
, startpos
, regs
, stop
,
5243 wcs_string1
, wcs_size1
,
5244 wcs_string2
, wcs_size2
,
5245 mbs_offset1
, mbs_offset2
);
5247 val
= byte_re_match_2_internal (bufp
, string1
, size1
, string2
,
5248 size2
, startpos
, regs
, stop
);
5251 #ifndef REGEX_MALLOC
5260 FREE_WCS_BUFFERS ();
5268 FREE_WCS_BUFFERS ();
5288 FREE_WCS_BUFFERS ();
5294 /* This converts PTR, a pointer into one of the search wchar_t strings
5295 `string1' and `string2' into an multibyte string offset from the
5296 beginning of that string. We use mbs_offset to optimize.
5297 See convert_mbs_to_wcs. */
5298 # define POINTER_TO_OFFSET(ptr) \
5299 (FIRST_STRING_P (ptr) \
5300 ? ((regoff_t)(mbs_offset1 != NULL? mbs_offset1[(ptr)-string1] : 0)) \
5301 : ((regoff_t)((mbs_offset2 != NULL? mbs_offset2[(ptr)-string2] : 0) \
5304 /* This converts PTR, a pointer into one of the search strings `string1'
5305 and `string2' into an offset from the beginning of that string. */
5306 # define POINTER_TO_OFFSET(ptr) \
5307 (FIRST_STRING_P (ptr) \
5308 ? ((regoff_t) ((ptr) - string1)) \
5309 : ((regoff_t) ((ptr) - string2 + size1)))
5312 /* Macros for dealing with the split strings in re_match_2. */
5314 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
5316 /* Call before fetching a character with *d. This switches over to
5317 string2 if necessary. */
5318 #define PREFETCH() \
5321 /* End of string2 => fail. */ \
5322 if (dend == end_match_2) \
5324 /* End of string1 => advance to string2. */ \
5326 dend = end_match_2; \
5329 /* Test if at very beginning or at very end of the virtual concatenation
5330 of `string1' and `string2'. If only one string, it's `string2'. */
5331 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
5332 #define AT_STRINGS_END(d) ((d) == end2)
5335 /* Test if D points to a character which is word-constituent. We have
5336 two special cases to check for: if past the end of string1, look at
5337 the first character in string2; and if before the beginning of
5338 string2, look at the last character in string1. */
5340 /* Use internationalized API instead of SYNTAX. */
5341 # define WORDCHAR_P(d) \
5342 (iswalnum ((wint_t)((d) == end1 ? *string2 \
5343 : (d) == string2 - 1 ? *(end1 - 1) : *(d))) != 0 \
5344 || ((d) == end1 ? *string2 \
5345 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) == L'_')
5347 # define WORDCHAR_P(d) \
5348 (SYNTAX ((d) == end1 ? *string2 \
5349 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
5353 /* Disabled due to a compiler bug -- see comment at case wordbound */
5355 /* Test if the character before D and the one at D differ with respect
5356 to being word-constituent. */
5357 #define AT_WORD_BOUNDARY(d) \
5358 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
5359 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
5362 /* Free everything we malloc. */
5363 #ifdef MATCH_MAY_ALLOCATE
5365 # define FREE_VARIABLES() \
5367 REGEX_FREE_STACK (fail_stack.stack); \
5368 FREE_VAR (regstart); \
5369 FREE_VAR (regend); \
5370 FREE_VAR (old_regstart); \
5371 FREE_VAR (old_regend); \
5372 FREE_VAR (best_regstart); \
5373 FREE_VAR (best_regend); \
5374 FREE_VAR (reg_info); \
5375 FREE_VAR (reg_dummy); \
5376 FREE_VAR (reg_info_dummy); \
5377 if (!cant_free_wcs_buf) \
5379 FREE_VAR (string1); \
5380 FREE_VAR (string2); \
5381 FREE_VAR (mbs_offset1); \
5382 FREE_VAR (mbs_offset2); \
5386 # define FREE_VARIABLES() \
5388 REGEX_FREE_STACK (fail_stack.stack); \
5389 FREE_VAR (regstart); \
5390 FREE_VAR (regend); \
5391 FREE_VAR (old_regstart); \
5392 FREE_VAR (old_regend); \
5393 FREE_VAR (best_regstart); \
5394 FREE_VAR (best_regend); \
5395 FREE_VAR (reg_info); \
5396 FREE_VAR (reg_dummy); \
5397 FREE_VAR (reg_info_dummy); \
5402 # define FREE_VARIABLES() \
5404 if (!cant_free_wcs_buf) \
5406 FREE_VAR (string1); \
5407 FREE_VAR (string2); \
5408 FREE_VAR (mbs_offset1); \
5409 FREE_VAR (mbs_offset2); \
5413 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
5415 #endif /* not MATCH_MAY_ALLOCATE */
5417 /* These values must meet several constraints. They must not be valid
5418 register values; since we have a limit of 255 registers (because
5419 we use only one byte in the pattern for the register number), we can
5420 use numbers larger than 255. They must differ by 1, because of
5421 NUM_FAILURE_ITEMS above. And the value for the lowest register must
5422 be larger than the value for the highest register, so we do not try
5423 to actually save any registers when none are active. */
5424 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
5425 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
5427 #else /* not INSIDE_RECURSION */
5428 /* Matching routines. */
5430 #ifndef emacs /* Emacs never uses this. */
5431 /* re_match is like re_match_2 except it takes only a single string. */
5435 struct re_pattern_buffer
*bufp
,
5438 struct re_registers
*regs
)
5442 if (MB_CUR_MAX
!= 1)
5443 result
= wcs_re_match_2_internal (bufp
, NULL
, 0, string
, size
,
5445 NULL
, 0, NULL
, 0, NULL
, NULL
);
5448 result
= byte_re_match_2_internal (bufp
, NULL
, 0, string
, size
,
5450 # ifndef REGEX_MALLOC
5457 #endif /* not emacs */
5459 #endif /* not INSIDE_RECURSION */
5461 #ifdef INSIDE_RECURSION
5462 static boolean
PREFIX(group_match_null_string_p
) (UCHAR_T
**p
,
5464 PREFIX(register_info_type
) *reg_info
);
5465 static boolean
PREFIX(alt_match_null_string_p
) (UCHAR_T
*p
,
5467 PREFIX(register_info_type
) *reg_info
);
5468 static boolean
PREFIX(common_op_match_null_string_p
) (UCHAR_T
**p
,
5470 PREFIX(register_info_type
) *reg_info
);
5471 static int PREFIX(bcmp_translate
) (const CHAR_T
*s1
, const CHAR_T
*s2
,
5472 int len
, __RE_TRANSLATE_TYPE translate
);
5473 #else /* not INSIDE_RECURSION */
5475 /* re_match_2 matches the compiled pattern in BUFP against the
5476 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
5477 and SIZE2, respectively). We start matching at POS, and stop
5480 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
5481 store offsets for the substring each group matched in REGS. See the
5482 documentation for exactly how many groups we fill.
5484 We return -1 if no match, -2 if an internal error (such as the
5485 failure stack overflowing). Otherwise, we return the length of the
5486 matched substring. */
5490 struct re_pattern_buffer
*bufp
,
5491 const char *string1
, int size1
,
5492 const char *string2
, int size2
,
5494 struct re_registers
*regs
,
5499 if (MB_CUR_MAX
!= 1)
5500 result
= wcs_re_match_2_internal (bufp
, string1
, size1
, string2
, size2
,
5502 NULL
, 0, NULL
, 0, NULL
, NULL
);
5505 result
= byte_re_match_2_internal (bufp
, string1
, size1
, string2
, size2
,
5508 #ifndef REGEX_MALLOC
5516 #endif /* not INSIDE_RECURSION */
5518 #ifdef INSIDE_RECURSION
5521 static int count_mbs_length (int *, int);
5523 /* This check the substring (from 0, to length) of the multibyte string,
5524 to which offset_buffer correspond. And count how many wchar_t_characters
5525 the substring occupy. We use offset_buffer to optimization.
5526 See convert_mbs_to_wcs. */
5535 /* Check whether the size is valid. */
5539 if (offset_buffer
== NULL
)
5542 /* If there are no multibyte character, offset_buffer[i] == i.
5543 Optmize for this case. */
5544 if (offset_buffer
[length
] == length
)
5547 /* Set up upper with length. (because for all i, offset_buffer[i] >= i) */
5553 int middle
= (lower
+ upper
) / 2;
5554 if (middle
== lower
|| middle
== upper
)
5556 if (offset_buffer
[middle
] > length
)
5558 else if (offset_buffer
[middle
] < length
)
5568 /* This is a separate function so that we can force an alloca cleanup
5572 wcs_re_match_2_internal (
5573 struct re_pattern_buffer
*bufp
,
5574 const char *cstring1
, int csize1
,
5575 const char *cstring2
, int csize2
,
5577 struct re_registers
*regs
,
5579 /* string1 == string2 == NULL means string1/2, size1/2 and
5580 mbs_offset1/2 need seting up in this function. */
5581 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5582 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5583 wchar_t *string1
, int size1
,
5584 wchar_t *string2
, int size2
,
5585 /* offset buffer for optimization. See convert_mbs_to_wc. */
5586 int *mbs_offset1
, int *mbs_offset2
)
5589 byte_re_match_2_internal (
5590 struct re_pattern_buffer
*bufp
,
5591 const char *string1
, int size1
,
5592 const char *string2
, int size2
,
5594 struct re_registers
*regs
,
5598 /* General temporaries. */
5602 /* They hold whether each wchar_t is binary data or not. */
5603 char *is_binary
= NULL
;
5604 /* If true, we can't free string1/2, mbs_offset1/2. */
5605 int cant_free_wcs_buf
= 1;
5608 /* Just past the end of the corresponding string. */
5609 const CHAR_T
*end1
, *end2
;
5611 /* Pointers into string1 and string2, just past the last characters in
5612 each to consider matching. */
5613 const CHAR_T
*end_match_1
, *end_match_2
;
5615 /* Where we are in the data, and the end of the current string. */
5616 const CHAR_T
*d
, *dend
;
5618 /* Where we are in the pattern, and the end of the pattern. */
5620 UCHAR_T
*pattern
, *p
;
5621 register UCHAR_T
*pend
;
5623 UCHAR_T
*p
= bufp
->buffer
;
5624 register UCHAR_T
*pend
= p
+ bufp
->used
;
5627 /* Mark the opcode just after a start_memory, so we can test for an
5628 empty subpattern when we get to the stop_memory. */
5629 UCHAR_T
*just_past_start_mem
= 0;
5631 /* We use this to map every character in the string. */
5632 __RE_TRANSLATE_TYPE translate
= bufp
->translate
;
5634 /* Failure point stack. Each place that can handle a failure further
5635 down the line pushes a failure point on this stack. It consists of
5636 restart, regend, and reg_info for all registers corresponding to
5637 the subexpressions we're currently inside, plus the number of such
5638 registers, and, finally, two char *'s. The first char * is where
5639 to resume scanning the pattern; the second one is where to resume
5640 scanning the strings. If the latter is zero, the failure point is
5641 a ``dummy''; if a failure happens and the failure point is a dummy,
5642 it gets discarded and the next next one is tried. */
5643 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5644 PREFIX(fail_stack_type
) fail_stack
;
5647 static unsigned failure_id
;
5648 unsigned nfailure_points_pushed
= 0, nfailure_points_popped
= 0;
5652 /* This holds the pointer to the failure stack, when
5653 it is allocated relocatably. */
5654 fail_stack_elt_t
*failure_stack_ptr
;
5657 /* We fill all the registers internally, independent of what we
5658 return, for use in backreferences. The number here includes
5659 an element for register zero. */
5660 size_t num_regs
= bufp
->re_nsub
+ 1;
5662 /* The currently active registers. */
5663 active_reg_t lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
5664 active_reg_t highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
5666 /* Information on the contents of registers. These are pointers into
5667 the input strings; they record just what was matched (on this
5668 attempt) by a subexpression part of the pattern, that is, the
5669 regnum-th regstart pointer points to where in the pattern we began
5670 matching and the regnum-th regend points to right after where we
5671 stopped matching the regnum-th subexpression. (The zeroth register
5672 keeps track of what the whole pattern matches.) */
5673 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5674 const CHAR_T
**regstart
, **regend
;
5677 /* If a group that's operated upon by a repetition operator fails to
5678 match anything, then the register for its start will need to be
5679 restored because it will have been set to wherever in the string we
5680 are when we last see its open-group operator. Similarly for a
5682 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5683 const CHAR_T
**old_regstart
, **old_regend
;
5686 /* The is_active field of reg_info helps us keep track of which (possibly
5687 nested) subexpressions we are currently in. The matched_something
5688 field of reg_info[reg_num] helps us tell whether or not we have
5689 matched any of the pattern so far this time through the reg_num-th
5690 subexpression. These two fields get reset each time through any
5691 loop their register is in. */
5692 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5693 PREFIX(register_info_type
) *reg_info
;
5696 /* The following record the register info as found in the above
5697 variables when we find a match better than any we've seen before.
5698 This happens as we backtrack through the failure points, which in
5699 turn happens only if we have not yet matched the entire string. */
5700 unsigned best_regs_set
= false;
5701 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5702 const CHAR_T
**best_regstart
, **best_regend
;
5705 /* Logically, this is `best_regend[0]'. But we don't want to have to
5706 allocate space for that if we're not allocating space for anything
5707 else (see below). Also, we never need info about register 0 for
5708 any of the other register vectors, and it seems rather a kludge to
5709 treat `best_regend' differently than the rest. So we keep track of
5710 the end of the best match so far in a separate variable. We
5711 initialize this to NULL so that when we backtrack the first time
5712 and need to test it, it's not garbage. */
5713 const CHAR_T
*match_end
= NULL
;
5715 /* This helps SET_REGS_MATCHED avoid doing redundant work. */
5716 int set_regs_matched_done
= 0;
5718 /* Used when we pop values we don't care about. */
5719 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5720 const CHAR_T
**reg_dummy
;
5721 PREFIX(register_info_type
) *reg_info_dummy
;
5725 /* Counts the total number of registers pushed. */
5726 unsigned num_regs_pushed
= 0;
5729 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
5733 #ifdef MATCH_MAY_ALLOCATE
5734 /* Do not bother to initialize all the register variables if there are
5735 no groups in the pattern, as it takes a fair amount of time. If
5736 there are groups, we include space for register 0 (the whole
5737 pattern), even though we never use it, since it simplifies the
5738 array indexing. We should fix this. */
5741 regstart
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5742 regend
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5743 old_regstart
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5744 old_regend
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5745 best_regstart
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5746 best_regend
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5747 reg_info
= REGEX_TALLOC (num_regs
, PREFIX(register_info_type
));
5748 reg_dummy
= REGEX_TALLOC (num_regs
, const CHAR_T
*);
5749 reg_info_dummy
= REGEX_TALLOC (num_regs
, PREFIX(register_info_type
));
5751 if (!(regstart
&& regend
&& old_regstart
&& old_regend
&& reg_info
5752 && best_regstart
&& best_regend
&& reg_dummy
&& reg_info_dummy
))
5760 /* We must initialize all our variables to NULL, so that
5761 `FREE_VARIABLES' doesn't try to free them. */
5762 regstart
= regend
= old_regstart
= old_regend
= best_regstart
5763 = best_regend
= reg_dummy
= NULL
;
5764 reg_info
= reg_info_dummy
= (PREFIX(register_info_type
) *) NULL
;
5766 #endif /* MATCH_MAY_ALLOCATE */
5768 /* The starting position is bogus. */
5770 if (pos
< 0 || pos
> csize1
+ csize2
)
5772 if (pos
< 0 || pos
> size1
+ size2
)
5780 /* Allocate wchar_t array for string1 and string2 and
5781 fill them with converted string. */
5782 if (string1
== NULL
&& string2
== NULL
)
5784 /* We need seting up buffers here. */
5786 /* We must free wcs buffers in this function. */
5787 cant_free_wcs_buf
= 0;
5791 string1
= REGEX_TALLOC (csize1
+ 1, CHAR_T
);
5792 mbs_offset1
= REGEX_TALLOC (csize1
+ 1, int);
5793 is_binary
= REGEX_TALLOC (csize1
+ 1, char);
5794 if (!string1
|| !mbs_offset1
|| !is_binary
)
5797 FREE_VAR (mbs_offset1
);
5798 FREE_VAR (is_binary
);
5804 string2
= REGEX_TALLOC (csize2
+ 1, CHAR_T
);
5805 mbs_offset2
= REGEX_TALLOC (csize2
+ 1, int);
5806 is_binary
= REGEX_TALLOC (csize2
+ 1, char);
5807 if (!string2
|| !mbs_offset2
|| !is_binary
)
5810 FREE_VAR (mbs_offset1
);
5812 FREE_VAR (mbs_offset2
);
5813 FREE_VAR (is_binary
);
5816 size2
= convert_mbs_to_wcs(string2
, cstring2
, csize2
,
5817 mbs_offset2
, is_binary
);
5818 string2
[size2
] = L
'\0'; /* for a sentinel */
5819 FREE_VAR (is_binary
);
5823 /* We need to cast pattern to (wchar_t*), because we casted this compiled
5824 pattern to (char*) in regex_compile. */
5825 p
= pattern
= (CHAR_T
*)bufp
->buffer
;
5826 pend
= (CHAR_T
*)(bufp
->buffer
+ bufp
->used
);
5830 /* Initialize subexpression text positions to -1 to mark ones that no
5831 start_memory/stop_memory has been seen for. Also initialize the
5832 register information struct. */
5833 for (mcnt
= 1; (unsigned) mcnt
< num_regs
; mcnt
++)
5835 regstart
[mcnt
] = regend
[mcnt
]
5836 = old_regstart
[mcnt
] = old_regend
[mcnt
] = REG_UNSET_VALUE
;
5838 REG_MATCH_NULL_STRING_P (reg_info
[mcnt
]) = MATCH_NULL_UNSET_VALUE
;
5839 IS_ACTIVE (reg_info
[mcnt
]) = 0;
5840 MATCHED_SOMETHING (reg_info
[mcnt
]) = 0;
5841 EVER_MATCHED_SOMETHING (reg_info
[mcnt
]) = 0;
5844 /* We move `string1' into `string2' if the latter's empty -- but not if
5845 `string1' is null. */
5846 if (size2
== 0 && string1
!= NULL
)
5853 mbs_offset2
= mbs_offset1
;
5859 end1
= string1
+ size1
;
5860 end2
= string2
+ size2
;
5862 /* Compute where to stop matching, within the two strings. */
5866 mcnt
= count_mbs_length(mbs_offset1
, stop
);
5867 end_match_1
= string1
+ mcnt
;
5868 end_match_2
= string2
;
5872 if (stop
> csize1
+ csize2
)
5873 stop
= csize1
+ csize2
;
5875 mcnt
= count_mbs_length(mbs_offset2
, stop
-csize1
);
5876 end_match_2
= string2
+ mcnt
;
5879 { /* count_mbs_length return error. */
5886 end_match_1
= string1
+ stop
;
5887 end_match_2
= string2
;
5892 end_match_2
= string2
+ stop
- size1
;
5896 /* `p' scans through the pattern as `d' scans through the data.
5897 `dend' is the end of the input string that `d' points within. `d'
5898 is advanced into the following input string whenever necessary, but
5899 this happens before fetching; therefore, at the beginning of the
5900 loop, `d' can be pointing at the end of a string, but it cannot
5903 if (size1
> 0 && pos
<= csize1
)
5905 mcnt
= count_mbs_length(mbs_offset1
, pos
);
5911 mcnt
= count_mbs_length(mbs_offset2
, pos
-csize1
);
5917 { /* count_mbs_length return error. */
5922 if (size1
> 0 && pos
<= size1
)
5929 d
= string2
+ pos
- size1
;
5934 DEBUG_PRINT1 ("The compiled pattern is:\n");
5935 DEBUG_PRINT_COMPILED_PATTERN (bufp
, p
, pend
);
5936 DEBUG_PRINT1 ("The string to match is: `");
5937 DEBUG_PRINT_DOUBLE_STRING (d
, string1
, size1
, string2
, size2
);
5938 DEBUG_PRINT1 ("'\n");
5940 /* This loops over pattern commands. It exits by returning from the
5941 function if the match is complete, or it drops through if the match
5942 fails at this starting point in the input data. */
5946 DEBUG_PRINT2 ("\n%p: ", p
);
5948 DEBUG_PRINT2 ("\n0x%x: ", p
);
5952 { /* End of pattern means we might have succeeded. */
5953 DEBUG_PRINT1 ("end of pattern ... ");
5955 /* If we haven't matched the entire string, and we want the
5956 longest match, try backtracking. */
5957 if (d
!= end_match_2
)
5959 /* 1 if this match ends in the same string (string1 or string2)
5960 as the best previous match. */
5961 boolean same_str_p
= (FIRST_STRING_P (match_end
)
5962 == MATCHING_IN_FIRST_STRING
);
5963 /* 1 if this match is the best seen so far. */
5964 boolean best_match_p
;
5966 /* AIX compiler got confused when this was combined
5967 with the previous declaration. */
5969 best_match_p
= d
> match_end
;
5971 best_match_p
= !MATCHING_IN_FIRST_STRING
;
5973 DEBUG_PRINT1 ("backtracking.\n");
5975 if (!FAIL_STACK_EMPTY ())
5976 { /* More failure points to try. */
5978 /* If exceeds best match so far, save it. */
5979 if (!best_regs_set
|| best_match_p
)
5981 best_regs_set
= true;
5984 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
5986 for (mcnt
= 1; (unsigned) mcnt
< num_regs
; mcnt
++)
5988 best_regstart
[mcnt
] = regstart
[mcnt
];
5989 best_regend
[mcnt
] = regend
[mcnt
];
5995 /* If no failure points, don't restore garbage. And if
5996 last match is real best match, don't restore second
5998 else if (best_regs_set
&& !best_match_p
)
6001 /* Restore best match. It may happen that `dend ==
6002 end_match_1' while the restored d is in string2.
6003 For example, the pattern `x.*y.*z' against the
6004 strings `x-' and `y-z-', if the two strings are
6005 not consecutive in memory. */
6006 DEBUG_PRINT1 ("Restoring best registers.\n");
6009 dend
= ((d
>= string1
&& d
<= end1
)
6010 ? end_match_1
: end_match_2
);
6012 for (mcnt
= 1; (unsigned) mcnt
< num_regs
; mcnt
++)
6014 regstart
[mcnt
] = best_regstart
[mcnt
];
6015 regend
[mcnt
] = best_regend
[mcnt
];
6018 } /* d != end_match_2 */
6021 DEBUG_PRINT1 ("Accepting match.\n");
6022 /* If caller wants register contents data back, do it. */
6023 if (regs
&& !bufp
->no_sub
)
6025 /* Have the register data arrays been allocated? */
6026 if (bufp
->regs_allocated
== REGS_UNALLOCATED
)
6027 { /* No. So allocate them with malloc. We need one
6028 extra element beyond `num_regs' for the `-1' marker
6031 * "If REGS_UNALLOCATED, allocate space in the regs structure
6032 * for max(RE_NREGS, re_nsub + 1) groups"
6033 * but real-world testsuites fail with contrived examples
6034 * with lots of groups.
6035 * I don't see why we can't just allocate exact needed number.
6036 * Incidentally, it makes RE_NREGS unused.
6038 * regs->num_regs = MAX (RE_NREGS, num_regs + 1); - VERY WRONG
6039 * regs->num_regs = MIN (RE_NREGS, num_regs + 1); - slightly less wrong
6040 * good one which passes uclibc test/regex/tst-regex2.c:
6042 regs
->num_regs
= num_regs
+ 1;
6043 regs
->start
= TALLOC (regs
->num_regs
, regoff_t
);
6044 regs
->end
= TALLOC (regs
->num_regs
, regoff_t
);
6045 if (regs
->start
== NULL
|| regs
->end
== NULL
)
6050 bufp
->regs_allocated
= REGS_REALLOCATE
;
6052 else if (bufp
->regs_allocated
== REGS_REALLOCATE
)
6053 { /* Yes. If we need more elements than were already
6054 allocated, reallocate them. If we need fewer, just
6056 if (regs
->num_regs
< num_regs
+ 1)
6058 regs
->num_regs
= num_regs
+ 1;
6059 RETALLOC (regs
->start
, regs
->num_regs
, regoff_t
);
6060 RETALLOC (regs
->end
, regs
->num_regs
, regoff_t
);
6061 if (regs
->start
== NULL
|| regs
->end
== NULL
)
6070 /* These braces fend off a "empty body in an else-statement"
6071 warning under GCC when assert expands to nothing. */
6072 assert (bufp
->regs_allocated
== REGS_FIXED
);
6075 /* Convert the pointer data in `regstart' and `regend' to
6076 indices. Register zero has to be set differently,
6077 since we haven't kept track of any info for it. */
6078 if (regs
->num_regs
> 0)
6080 regs
->start
[0] = pos
;
6082 if (MATCHING_IN_FIRST_STRING
)
6083 regs
->end
[0] = mbs_offset1
!= NULL
?
6084 mbs_offset1
[d
-string1
] : 0;
6086 regs
->end
[0] = csize1
+ (mbs_offset2
!= NULL
?
6087 mbs_offset2
[d
-string2
] : 0);
6089 regs
->end
[0] = (MATCHING_IN_FIRST_STRING
6090 ? ((regoff_t
) (d
- string1
))
6091 : ((regoff_t
) (d
- string2
+ size1
)));
6095 /* Go through the first `min (num_regs, regs->num_regs)'
6096 registers, since that is all we initialized. */
6097 for (mcnt
= 1; (unsigned) mcnt
< MIN (num_regs
, regs
->num_regs
);
6100 if (REG_UNSET (regstart
[mcnt
]) || REG_UNSET (regend
[mcnt
]))
6101 regs
->start
[mcnt
] = regs
->end
[mcnt
] = -1;
6105 = (regoff_t
) POINTER_TO_OFFSET (regstart
[mcnt
]);
6107 = (regoff_t
) POINTER_TO_OFFSET (regend
[mcnt
]);
6111 /* If the regs structure we return has more elements than
6112 were in the pattern, set the extra elements to -1. If
6113 we (re)allocated the registers, this is the case,
6114 because we always allocate enough to have at least one
6116 for (mcnt
= num_regs
; (unsigned) mcnt
< regs
->num_regs
; mcnt
++)
6117 regs
->start
[mcnt
] = regs
->end
[mcnt
] = -1;
6118 } /* regs && !bufp->no_sub */
6120 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
6121 nfailure_points_pushed
, nfailure_points_popped
,
6122 nfailure_points_pushed
- nfailure_points_popped
);
6123 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed
);
6126 if (MATCHING_IN_FIRST_STRING
)
6127 mcnt
= mbs_offset1
!= NULL
? mbs_offset1
[d
-string1
] : 0;
6129 mcnt
= (mbs_offset2
!= NULL
? mbs_offset2
[d
-string2
] : 0) +
6133 mcnt
= d
- pos
- (MATCHING_IN_FIRST_STRING
6138 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt
);
6144 /* Otherwise match next pattern command. */
6145 switch (SWITCH_ENUM_CAST ((re_opcode_t
) *p
++))
6147 /* Ignore these. Used to ignore the n of succeed_n's which
6148 currently have n == 0. */
6150 DEBUG_PRINT1 ("EXECUTING no_op.\n");
6154 DEBUG_PRINT1 ("EXECUTING succeed.\n");
6157 /* Match the next n pattern characters exactly. The following
6158 byte in the pattern defines n, and the n bytes after that
6159 are the characters to match. */
6165 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt
);
6167 /* This is written out as an if-else so we don't waste time
6168 testing `translate' inside the loop. */
6177 if ((UCHAR_T
) translate
[(unsigned char) *d
++]
6183 if (*d
++ != (CHAR_T
) *p
++)
6187 if ((UCHAR_T
) translate
[(unsigned char) *d
++]
6199 if (*d
++ != (CHAR_T
) *p
++) goto fail
;
6203 SET_REGS_MATCHED ();
6207 /* Match any character except possibly a newline or a null. */
6209 DEBUG_PRINT1 ("EXECUTING anychar.\n");
6213 if ((!(bufp
->syntax
& RE_DOT_NEWLINE
) && TRANSLATE (*d
) == '\n')
6214 || (bufp
->syntax
& RE_DOT_NOT_NULL
&& TRANSLATE (*d
) == '\000'))
6217 SET_REGS_MATCHED ();
6218 DEBUG_PRINT2 (" Matched `%ld'.\n", (long int) *d
);
6228 unsigned int i
, char_class_length
, coll_symbol_length
,
6229 equiv_class_length
, ranges_length
, chars_length
, length
;
6230 CHAR_T
*workp
, *workp2
, *charset_top
;
6231 #define WORK_BUFFER_SIZE 128
6232 CHAR_T str_buf
[WORK_BUFFER_SIZE
];
6237 boolean
not = (re_opcode_t
) *(p
- 1) == charset_not
;
6239 DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
6241 c
= TRANSLATE (*d
); /* The character to match. */
6244 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
6246 charset_top
= p
- 1;
6247 char_class_length
= *p
++;
6248 coll_symbol_length
= *p
++;
6249 equiv_class_length
= *p
++;
6250 ranges_length
= *p
++;
6251 chars_length
= *p
++;
6252 /* p points charset[6], so the address of the next instruction
6253 (charset[l+m+n+2o+k+p']) equals p[l+m+n+2*o+p'],
6254 where l=length of char_classes, m=length of collating_symbol,
6255 n=equivalence_class, o=length of char_range,
6256 p'=length of character. */
6258 /* Update p to indicate the next instruction. */
6259 p
+= char_class_length
+ coll_symbol_length
+ equiv_class_length
+
6260 2*ranges_length
+ chars_length
;
6262 /* match with char_class? */
6263 for (i
= 0; i
< char_class_length
; i
+= CHAR_CLASS_SIZE
)
6266 uintptr_t alignedp
= ((uintptr_t)workp
6267 + __alignof__(wctype_t) - 1)
6268 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
6269 wctype
= *((wctype_t*)alignedp
);
6270 workp
+= CHAR_CLASS_SIZE
;
6272 if (__iswctype((wint_t)c
, wctype
))
6273 goto char_set_matched
;
6275 if (iswctype((wint_t)c
, wctype
))
6276 goto char_set_matched
;
6280 /* match with collating_symbol? */
6284 const unsigned char *extra
= (const unsigned char *)
6285 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
6287 for (workp2
= workp
+ coll_symbol_length
; workp
< workp2
;
6291 wextra
= (int32_t*)(extra
+ *workp
++);
6292 for (i
= 0; i
< *wextra
; ++i
)
6293 if (TRANSLATE(d
[i
]) != wextra
[1 + i
])
6298 /* Update d, however d will be incremented at
6299 char_set_matched:, we decrement d here. */
6301 goto char_set_matched
;
6305 else /* (nrules == 0) */
6307 /* If we can't look up collation data, we use wcscoll
6310 for (workp2
= workp
+ coll_symbol_length
; workp
< workp2
;)
6312 const CHAR_T
*backup_d
= d
, *backup_dend
= dend
;
6314 length
= __wcslen (workp
);
6316 length
= wcslen (workp
);
6319 /* If wcscoll(the collating symbol, whole string) > 0,
6320 any substring of the string never match with the
6321 collating symbol. */
6323 if (__wcscoll (workp
, d
) > 0)
6325 if (wcscoll (workp
, d
) > 0)
6328 workp
+= length
+ 1;
6332 /* First, we compare the collating symbol with
6333 the first character of the string.
6334 If it don't match, we add the next character to
6335 the compare buffer in turn. */
6336 for (i
= 0 ; i
< WORK_BUFFER_SIZE
-1 ; i
++, d
++)
6341 if (dend
== end_match_2
)
6347 /* add next character to the compare buffer. */
6348 str_buf
[i
] = TRANSLATE(*d
);
6349 str_buf
[i
+1] = '\0';
6352 match
= __wcscoll (workp
, str_buf
);
6354 match
= wcscoll (workp
, str_buf
);
6357 goto char_set_matched
;
6360 /* (str_buf > workp) indicate (str_buf + X > workp),
6361 because for all X (str_buf + X > str_buf).
6362 So we don't need continue this loop. */
6365 /* Otherwise(str_buf < workp),
6366 (str_buf+next_character) may equals (workp).
6367 So we continue this loop. */
6372 workp
+= length
+ 1;
6375 /* match with equivalence_class? */
6379 const CHAR_T
*backup_d
= d
, *backup_dend
= dend
;
6380 /* Try to match the equivalence class against
6381 those known to the collate implementation. */
6382 const int32_t *table
;
6383 const int32_t *weights
;
6384 const int32_t *extra
;
6385 const int32_t *indirect
;
6390 /* This #include defines a local function! */
6391 # include <locale/weightwc.h>
6393 table
= (const int32_t *)
6394 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEWC
);
6395 weights
= (const wint_t *)
6396 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTWC
);
6397 extra
= (const wint_t *)
6398 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAWC
);
6399 indirect
= (const int32_t *)
6400 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTWC
);
6402 /* Write 1 collating element to str_buf, and
6406 for (i
= 0 ; idx2
== 0 && i
< WORK_BUFFER_SIZE
- 1; i
++)
6408 cp
= (wint_t*)str_buf
;
6411 if (dend
== end_match_2
)
6416 str_buf
[i
] = TRANSLATE(*(d
+i
));
6417 str_buf
[i
+1] = '\0'; /* sentinel */
6418 idx2
= findidx ((const wint_t**)&cp
);
6421 /* Update d, however d will be incremented at
6422 char_set_matched:, we decrement d here. */
6423 d
= backup_d
+ ((wchar_t*)cp
- (wchar_t*)str_buf
- 1);
6426 if (dend
== end_match_2
)
6435 len
= weights
[idx2
];
6437 for (workp2
= workp
+ equiv_class_length
; workp
< workp2
;
6440 idx
= (int32_t)*workp
;
6441 /* We already checked idx != 0 in regex_compile. */
6443 if (idx2
!= 0 && len
== weights
[idx
])
6446 while (cnt
< len
&& (weights
[idx
+ 1 + cnt
]
6447 == weights
[idx2
+ 1 + cnt
]))
6451 goto char_set_matched
;
6458 else /* (nrules == 0) */
6460 /* If we can't look up collation data, we use wcscoll
6463 for (workp2
= workp
+ equiv_class_length
; workp
< workp2
;)
6465 const CHAR_T
*backup_d
= d
, *backup_dend
= dend
;
6467 length
= __wcslen (workp
);
6469 length
= wcslen (workp
);
6472 /* If wcscoll(the collating symbol, whole string) > 0,
6473 any substring of the string never match with the
6474 collating symbol. */
6476 if (__wcscoll (workp
, d
) > 0)
6478 if (wcscoll (workp
, d
) > 0)
6481 workp
+= length
+ 1;
6485 /* First, we compare the equivalence class with
6486 the first character of the string.
6487 If it don't match, we add the next character to
6488 the compare buffer in turn. */
6489 for (i
= 0 ; i
< WORK_BUFFER_SIZE
- 1 ; i
++, d
++)
6494 if (dend
== end_match_2
)
6500 /* add next character to the compare buffer. */
6501 str_buf
[i
] = TRANSLATE(*d
);
6502 str_buf
[i
+1] = '\0';
6505 match
= __wcscoll (workp
, str_buf
);
6507 match
= wcscoll (workp
, str_buf
);
6511 goto char_set_matched
;
6514 /* (str_buf > workp) indicate (str_buf + X > workp),
6515 because for all X (str_buf + X > str_buf).
6516 So we don't need continue this loop. */
6519 /* Otherwise(str_buf < workp),
6520 (str_buf+next_character) may equals (workp).
6521 So we continue this loop. */
6526 workp
+= length
+ 1;
6530 /* match with char_range? */
6534 uint32_t collseqval
;
6535 const char *collseq
= (const char *)
6536 _NL_CURRENT(LC_COLLATE
, _NL_COLLATE_COLLSEQWC
);
6538 collseqval
= collseq_table_lookup (collseq
, c
);
6540 for (; workp
< p
- chars_length
;)
6542 uint32_t start_val
, end_val
;
6544 /* We already compute the collation sequence value
6545 of the characters (or collating symbols). */
6546 start_val
= (uint32_t) *workp
++; /* range_start */
6547 end_val
= (uint32_t) *workp
++; /* range_end */
6549 if (start_val
<= collseqval
&& collseqval
<= end_val
)
6550 goto char_set_matched
;
6556 /* We set range_start_char at str_buf[0], range_end_char
6557 at str_buf[4], and compared char at str_buf[2]. */
6562 for (; workp
< p
- chars_length
;)
6564 wchar_t *range_start_char
, *range_end_char
;
6566 /* match if (range_start_char <= c <= range_end_char). */
6568 /* If range_start(or end) < 0, we assume -range_start(end)
6569 is the offset of the collating symbol which is specified
6570 as the character of the range start(end). */
6574 range_start_char
= charset_top
- (*workp
++);
6577 str_buf
[0] = *workp
++;
6578 range_start_char
= str_buf
;
6583 range_end_char
= charset_top
- (*workp
++);
6586 str_buf
[4] = *workp
++;
6587 range_end_char
= str_buf
+ 4;
6591 if (__wcscoll (range_start_char
, str_buf
+2) <= 0
6592 && __wcscoll (str_buf
+2, range_end_char
) <= 0)
6594 if (wcscoll (range_start_char
, str_buf
+2) <= 0
6595 && wcscoll (str_buf
+2, range_end_char
) <= 0)
6597 goto char_set_matched
;
6601 /* match with char? */
6602 for (; workp
< p
; workp
++)
6604 goto char_set_matched
;
6611 /* Cast to `unsigned' instead of `unsigned char' in case the
6612 bit list is a full 32 bytes long. */
6613 if (c
< (unsigned) (*p
* BYTEWIDTH
)
6614 && p
[1 + c
/ BYTEWIDTH
] & (1 << (c
% BYTEWIDTH
)))
6619 if (!not) goto fail
;
6620 #undef WORK_BUFFER_SIZE
6622 SET_REGS_MATCHED ();
6628 /* The beginning of a group is represented by start_memory.
6629 The arguments are the register number in the next byte, and the
6630 number of groups inner to this one in the next. The text
6631 matched within the group is recorded (in the internal
6632 registers data structure) under the register number. */
6634 DEBUG_PRINT3 ("EXECUTING start_memory %ld (%ld):\n",
6635 (long int) *p
, (long int) p
[1]);
6637 /* Find out if this group can match the empty string. */
6638 p1
= p
; /* To send to group_match_null_string_p. */
6640 if (REG_MATCH_NULL_STRING_P (reg_info
[*p
]) == MATCH_NULL_UNSET_VALUE
)
6641 REG_MATCH_NULL_STRING_P (reg_info
[*p
])
6642 = PREFIX(group_match_null_string_p
) (&p1
, pend
, reg_info
);
6644 /* Save the position in the string where we were the last time
6645 we were at this open-group operator in case the group is
6646 operated upon by a repetition operator, e.g., with `(a*)*b'
6647 against `ab'; then we want to ignore where we are now in
6648 the string in case this attempt to match fails. */
6649 old_regstart
[*p
] = REG_MATCH_NULL_STRING_P (reg_info
[*p
])
6650 ? REG_UNSET (regstart
[*p
]) ? d
: regstart
[*p
]
6652 DEBUG_PRINT2 (" old_regstart: %d\n",
6653 POINTER_TO_OFFSET (old_regstart
[*p
]));
6656 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart
[*p
]));
6658 IS_ACTIVE (reg_info
[*p
]) = 1;
6659 MATCHED_SOMETHING (reg_info
[*p
]) = 0;
6661 /* Clear this whenever we change the register activity status. */
6662 set_regs_matched_done
= 0;
6664 /* This is the new highest active register. */
6665 highest_active_reg
= *p
;
6667 /* If nothing was active before, this is the new lowest active
6669 if (lowest_active_reg
== NO_LOWEST_ACTIVE_REG
)
6670 lowest_active_reg
= *p
;
6672 /* Move past the register number and inner group count. */
6674 just_past_start_mem
= p
;
6679 /* The stop_memory opcode represents the end of a group. Its
6680 arguments are the same as start_memory's: the register
6681 number, and the number of inner groups. */
6683 DEBUG_PRINT3 ("EXECUTING stop_memory %ld (%ld):\n",
6684 (long int) *p
, (long int) p
[1]);
6686 /* We need to save the string position the last time we were at
6687 this close-group operator in case the group is operated
6688 upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
6689 against `aba'; then we want to ignore where we are now in
6690 the string in case this attempt to match fails. */
6691 old_regend
[*p
] = REG_MATCH_NULL_STRING_P (reg_info
[*p
])
6692 ? REG_UNSET (regend
[*p
]) ? d
: regend
[*p
]
6694 DEBUG_PRINT2 (" old_regend: %d\n",
6695 POINTER_TO_OFFSET (old_regend
[*p
]));
6698 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend
[*p
]));
6700 /* This register isn't active anymore. */
6701 IS_ACTIVE (reg_info
[*p
]) = 0;
6703 /* Clear this whenever we change the register activity status. */
6704 set_regs_matched_done
= 0;
6706 /* If this was the only register active, nothing is active
6708 if (lowest_active_reg
== highest_active_reg
)
6710 lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
6711 highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
6714 { /* We must scan for the new highest active register, since
6715 it isn't necessarily one less than now: consider
6716 (a(b)c(d(e)f)g). When group 3 ends, after the f), the
6717 new highest active register is 1. */
6719 while (r
> 0 && !IS_ACTIVE (reg_info
[r
]))
6722 /* If we end up at register zero, that means that we saved
6723 the registers as the result of an `on_failure_jump', not
6724 a `start_memory', and we jumped to past the innermost
6725 `stop_memory'. For example, in ((.)*) we save
6726 registers 1 and 2 as a result of the *, but when we pop
6727 back to the second ), we are at the stop_memory 1.
6728 Thus, nothing is active. */
6731 lowest_active_reg
= NO_LOWEST_ACTIVE_REG
;
6732 highest_active_reg
= NO_HIGHEST_ACTIVE_REG
;
6735 highest_active_reg
= r
;
6738 /* If just failed to match something this time around with a
6739 group that's operated on by a repetition operator, try to
6740 force exit from the ``loop'', and restore the register
6741 information for this group that we had before trying this
6743 if ((!MATCHED_SOMETHING (reg_info
[*p
])
6744 || just_past_start_mem
== p
- 1)
6747 boolean is_a_jump_n
= false;
6751 switch ((re_opcode_t
) *p1
++)
6755 case pop_failure_jump
:
6756 case maybe_pop_jump
:
6758 case dummy_failure_jump
:
6759 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
6761 p1
+= OFFSET_ADDRESS_SIZE
;
6769 /* If the next operation is a jump backwards in the pattern
6770 to an on_failure_jump right before the start_memory
6771 corresponding to this stop_memory, exit from the loop
6772 by forcing a failure after pushing on the stack the
6773 on_failure_jump's jump in the pattern, and d. */
6774 if (mcnt
< 0 && (re_opcode_t
) *p1
== on_failure_jump
6775 && (re_opcode_t
) p1
[1+OFFSET_ADDRESS_SIZE
] == start_memory
6776 && p1
[2+OFFSET_ADDRESS_SIZE
] == *p
)
6778 /* If this group ever matched anything, then restore
6779 what its registers were before trying this last
6780 failed match, e.g., with `(a*)*b' against `ab' for
6781 regstart[1], and, e.g., with `((a*)*(b*)*)*'
6782 against `aba' for regend[3].
6784 Also restore the registers for inner groups for,
6785 e.g., `((a*)(b*))*' against `aba' (register 3 would
6786 otherwise get trashed). */
6788 if (EVER_MATCHED_SOMETHING (reg_info
[*p
]))
6792 EVER_MATCHED_SOMETHING (reg_info
[*p
]) = 0;
6794 /* Restore this and inner groups' (if any) registers. */
6795 for (r
= *p
; r
< (unsigned) *p
+ (unsigned) *(p
+ 1);
6798 regstart
[r
] = old_regstart
[r
];
6800 /* xx why this test? */
6801 if (old_regend
[r
] >= regstart
[r
])
6802 regend
[r
] = old_regend
[r
];
6806 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
6807 PUSH_FAILURE_POINT (p1
+ mcnt
, d
, -2);
6813 /* Move past the register number and the inner group count. */
6818 /* \<digit> has been turned into a `duplicate' command which is
6819 followed by the numeric value of <digit> as the register number. */
6822 register const CHAR_T
*d2
, *dend2
;
6823 int regno
= *p
++; /* Get which register to match against. */
6824 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno
);
6826 /* Can't back reference a group which we've never matched. */
6827 if (REG_UNSET (regstart
[regno
]) || REG_UNSET (regend
[regno
]))
6830 /* Where in input to try to start matching. */
6831 d2
= regstart
[regno
];
6833 /* Where to stop matching; if both the place to start and
6834 the place to stop matching are in the same string, then
6835 set to the place to stop, otherwise, for now have to use
6836 the end of the first string. */
6838 dend2
= ((FIRST_STRING_P (regstart
[regno
])
6839 == FIRST_STRING_P (regend
[regno
]))
6840 ? regend
[regno
] : end_match_1
);
6843 /* If necessary, advance to next segment in register
6847 if (dend2
== end_match_2
) break;
6848 if (dend2
== regend
[regno
]) break;
6850 /* End of string1 => advance to string2. */
6852 dend2
= regend
[regno
];
6854 /* At end of register contents => success */
6855 if (d2
== dend2
) break;
6857 /* If necessary, advance to next segment in data. */
6860 /* How many characters left in this segment to match. */
6863 /* Want how many consecutive characters we can match in
6864 one shot, so, if necessary, adjust the count. */
6865 if (mcnt
> dend2
- d2
)
6868 /* Compare that many; failure if mismatch, else move
6871 ? PREFIX(bcmp_translate
) (d
, d2
, mcnt
, translate
)
6872 : memcmp (d
, d2
, mcnt
*sizeof(UCHAR_T
)))
6874 d
+= mcnt
, d2
+= mcnt
;
6876 /* Do this because we've match some characters. */
6877 SET_REGS_MATCHED ();
6883 /* begline matches the empty string at the beginning of the string
6884 (unless `not_bol' is set in `bufp'), and, if
6885 `newline_anchor' is set, after newlines. */
6887 DEBUG_PRINT1 ("EXECUTING begline.\n");
6889 if (AT_STRINGS_BEG (d
))
6891 if (!bufp
->not_bol
) break;
6893 else if (d
[-1] == '\n' && bufp
->newline_anchor
)
6897 /* In all other cases, we fail. */
6901 /* endline is the dual of begline. */
6903 DEBUG_PRINT1 ("EXECUTING endline.\n");
6905 if (AT_STRINGS_END (d
))
6907 if (!bufp
->not_eol
) break;
6910 /* We have to ``prefetch'' the next character. */
6911 else if ((d
== end1
? *string2
: *d
) == '\n'
6912 && bufp
->newline_anchor
)
6919 /* Match at the very beginning of the data. */
6921 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
6922 if (AT_STRINGS_BEG (d
))
6927 /* Match at the very end of the data. */
6929 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
6930 if (AT_STRINGS_END (d
))
6935 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
6936 pushes NULL as the value for the string on the stack. Then
6937 `pop_failure_point' will keep the current value for the
6938 string, instead of restoring it. To see why, consider
6939 matching `foo\nbar' against `.*\n'. The .* matches the foo;
6940 then the . fails against the \n. But the next thing we want
6941 to do is match the \n against the \n; if we restored the
6942 string value, we would be back at the foo.
6944 Because this is used only in specific cases, we don't need to
6945 check all the things that `on_failure_jump' does, to make
6946 sure the right things get saved on the stack. Hence we don't
6947 share its code. The only reason to push anything on the
6948 stack at all is that otherwise we would have to change
6949 `anychar's code to do something besides goto fail in this
6950 case; that seems worse than this. */
6951 case on_failure_keep_string_jump
:
6952 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
6954 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
6956 DEBUG_PRINT3 (" %d (to %p):\n", mcnt
, p
+ mcnt
);
6958 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt
, p
+ mcnt
);
6961 PUSH_FAILURE_POINT (p
+ mcnt
, NULL
, -2);
6965 /* Uses of on_failure_jump:
6967 Each alternative starts with an on_failure_jump that points
6968 to the beginning of the next alternative. Each alternative
6969 except the last ends with a jump that in effect jumps past
6970 the rest of the alternatives. (They really jump to the
6971 ending jump of the following alternative, because tensioning
6972 these jumps is a hassle.)
6974 Repeats start with an on_failure_jump that points past both
6975 the repetition text and either the following jump or
6976 pop_failure_jump back to this on_failure_jump. */
6977 case on_failure_jump
:
6979 DEBUG_PRINT1 ("EXECUTING on_failure_jump");
6981 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
6983 DEBUG_PRINT3 (" %d (to %p)", mcnt
, p
+ mcnt
);
6985 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt
, p
+ mcnt
);
6988 /* If this on_failure_jump comes right before a group (i.e.,
6989 the original * applied to a group), save the information
6990 for that group and all inner ones, so that if we fail back
6991 to this point, the group's information will be correct.
6992 For example, in \(a*\)*\1, we need the preceding group,
6993 and in \(zz\(a*\)b*\)\2, we need the inner group. */
6995 /* We can't use `p' to check ahead because we push
6996 a failure point to `p + mcnt' after we do this. */
6999 /* We need to skip no_op's before we look for the
7000 start_memory in case this on_failure_jump is happening as
7001 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
7003 while (p1
< pend
&& (re_opcode_t
) *p1
== no_op
)
7006 if (p1
< pend
&& (re_opcode_t
) *p1
== start_memory
)
7008 /* We have a new highest active register now. This will
7009 get reset at the start_memory we are about to get to,
7010 but we will have saved all the registers relevant to
7011 this repetition op, as described above. */
7012 highest_active_reg
= *(p1
+ 1) + *(p1
+ 2);
7013 if (lowest_active_reg
== NO_LOWEST_ACTIVE_REG
)
7014 lowest_active_reg
= *(p1
+ 1);
7017 DEBUG_PRINT1 (":\n");
7018 PUSH_FAILURE_POINT (p
+ mcnt
, d
, -2);
7022 /* A smart repeat ends with `maybe_pop_jump'.
7023 We change it to either `pop_failure_jump' or `jump'. */
7024 case maybe_pop_jump
:
7025 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
7026 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt
);
7028 register UCHAR_T
*p2
= p
;
7030 /* Compare the beginning of the repeat with what in the
7031 pattern follows its end. If we can establish that there
7032 is nothing that they would both match, i.e., that we
7033 would have to backtrack because of (as in, e.g., `a*a')
7034 then we can change to pop_failure_jump, because we'll
7035 never have to backtrack.
7037 This is not true in the case of alternatives: in
7038 `(a|ab)*' we do need to backtrack to the `ab' alternative
7039 (e.g., if the string was `ab'). But instead of trying to
7040 detect that here, the alternative has put on a dummy
7041 failure point which is what we will end up popping. */
7043 /* Skip over open/close-group commands.
7044 If what follows this loop is a ...+ construct,
7045 look at what begins its body, since we will have to
7046 match at least one of that. */
7050 && ((re_opcode_t
) *p2
== stop_memory
7051 || (re_opcode_t
) *p2
== start_memory
))
7053 else if (p2
+ 2 + 2 * OFFSET_ADDRESS_SIZE
< pend
7054 && (re_opcode_t
) *p2
== dummy_failure_jump
)
7055 p2
+= 2 + 2 * OFFSET_ADDRESS_SIZE
;
7061 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
7062 to the `maybe_finalize_jump' of this case. Examine what
7065 /* If we're at the end of the pattern, we can change. */
7068 /* Consider what happens when matching ":\(.*\)"
7069 against ":/". I don't really understand this code
7071 p
[-(1+OFFSET_ADDRESS_SIZE
)] = (UCHAR_T
)
7074 (" End of pattern: change to `pop_failure_jump'.\n");
7077 else if ((re_opcode_t
) *p2
== exactn
7079 || (re_opcode_t
) *p2
== exactn_bin
7081 || (bufp
->newline_anchor
&& (re_opcode_t
) *p2
== endline
))
7084 = *p2
== (UCHAR_T
) endline
? '\n' : p2
[2];
7086 if (((re_opcode_t
) p1
[1+OFFSET_ADDRESS_SIZE
] == exactn
7088 || (re_opcode_t
) p1
[1+OFFSET_ADDRESS_SIZE
] == exactn_bin
7090 ) && p1
[3+OFFSET_ADDRESS_SIZE
] != c
)
7092 p
[-(1+OFFSET_ADDRESS_SIZE
)] = (UCHAR_T
)
7095 DEBUG_PRINT3 (" %C != %C => pop_failure_jump.\n",
7097 (wint_t) p1
[3+OFFSET_ADDRESS_SIZE
]);
7099 DEBUG_PRINT3 (" %c != %c => pop_failure_jump.\n",
7101 (char) p1
[3+OFFSET_ADDRESS_SIZE
]);
7106 else if ((re_opcode_t
) p1
[3] == charset
7107 || (re_opcode_t
) p1
[3] == charset_not
)
7109 int not = (re_opcode_t
) p1
[3] == charset_not
;
7111 if (c
< (unsigned) (p1
[4] * BYTEWIDTH
)
7112 && p1
[5 + c
/ BYTEWIDTH
] & (1 << (c
% BYTEWIDTH
)))
7115 /* `not' is equal to 1 if c would match, which means
7116 that we can't change to pop_failure_jump. */
7119 p
[-3] = (unsigned char) pop_failure_jump
;
7120 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7123 #endif /* not WCHAR */
7126 else if ((re_opcode_t
) *p2
== charset
)
7128 /* We win if the first character of the loop is not part
7130 if ((re_opcode_t
) p1
[3] == exactn
7131 && ! ((int) p2
[1] * BYTEWIDTH
> (int) p1
[5]
7132 && (p2
[2 + p1
[5] / BYTEWIDTH
]
7133 & (1 << (p1
[5] % BYTEWIDTH
)))))
7135 p
[-3] = (unsigned char) pop_failure_jump
;
7136 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7139 else if ((re_opcode_t
) p1
[3] == charset_not
)
7142 /* We win if the charset_not inside the loop
7143 lists every character listed in the charset after. */
7144 for (idx
= 0; idx
< (int) p2
[1]; idx
++)
7145 if (! (p2
[2 + idx
] == 0
7146 || (idx
< (int) p1
[4]
7147 && ((p2
[2 + idx
] & ~ p1
[5 + idx
]) == 0))))
7152 p
[-3] = (unsigned char) pop_failure_jump
;
7153 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7156 else if ((re_opcode_t
) p1
[3] == charset
)
7159 /* We win if the charset inside the loop
7160 has no overlap with the one after the loop. */
7162 idx
< (int) p2
[1] && idx
< (int) p1
[4];
7164 if ((p2
[2 + idx
] & p1
[5 + idx
]) != 0)
7167 if (idx
== p2
[1] || idx
== p1
[4])
7169 p
[-3] = (unsigned char) pop_failure_jump
;
7170 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7174 #endif /* not WCHAR */
7176 p
-= OFFSET_ADDRESS_SIZE
; /* Point at relative address again. */
7177 if ((re_opcode_t
) p
[-1] != pop_failure_jump
)
7179 p
[-1] = (UCHAR_T
) jump
;
7180 DEBUG_PRINT1 (" Match => jump.\n");
7181 goto unconditional_jump
;
7183 /* Note fall through. */
7186 /* The end of a simple repeat has a pop_failure_jump back to
7187 its matching on_failure_jump, where the latter will push a
7188 failure point. The pop_failure_jump takes off failure
7189 points put on by this pop_failure_jump's matching
7190 on_failure_jump; we got through the pattern to here from the
7191 matching on_failure_jump, so didn't fail. */
7192 case pop_failure_jump
:
7194 /* We need to pass separate storage for the lowest and
7195 highest registers, even though we don't care about the
7196 actual values. Otherwise, we will restore only one
7197 register from the stack, since lowest will == highest in
7198 `pop_failure_point'. */
7199 active_reg_t dummy_low_reg
, dummy_high_reg
;
7200 UCHAR_T
*pdummy
= NULL
;
7201 const CHAR_T
*sdummy
= NULL
;
7203 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
7204 POP_FAILURE_POINT (sdummy
, pdummy
,
7205 dummy_low_reg
, dummy_high_reg
,
7206 reg_dummy
, reg_dummy
, reg_info_dummy
);
7208 /* Silence 'set but not used' warnings. */
7212 /* Note fall through. */
7216 DEBUG_PRINT2 ("\n%p: ", p
);
7218 DEBUG_PRINT2 ("\n0x%x: ", p
);
7220 /* Note fall through. */
7222 /* Unconditionally jump (without popping any failure points). */
7224 EXTRACT_NUMBER_AND_INCR (mcnt
, p
); /* Get the amount to jump. */
7225 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt
);
7226 p
+= mcnt
; /* Do the jump. */
7228 DEBUG_PRINT2 ("(to %p).\n", p
);
7230 DEBUG_PRINT2 ("(to 0x%x).\n", p
);
7235 /* We need this opcode so we can detect where alternatives end
7236 in `group_match_null_string_p' et al. */
7238 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
7239 goto unconditional_jump
;
7242 /* Normally, the on_failure_jump pushes a failure point, which
7243 then gets popped at pop_failure_jump. We will end up at
7244 pop_failure_jump, also, and with a pattern of, say, `a+', we
7245 are skipping over the on_failure_jump, so we have to push
7246 something meaningless for pop_failure_jump to pop. */
7247 case dummy_failure_jump
:
7248 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
7249 /* It doesn't matter what we push for the string here. What
7250 the code at `fail' tests is the value for the pattern. */
7251 PUSH_FAILURE_POINT (NULL
, NULL
, -2);
7252 goto unconditional_jump
;
7255 /* At the end of an alternative, we need to push a dummy failure
7256 point in case we are followed by a `pop_failure_jump', because
7257 we don't want the failure point for the alternative to be
7258 popped. For example, matching `(a|ab)*' against `aab'
7259 requires that we match the `ab' alternative. */
7260 case push_dummy_failure
:
7261 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
7262 /* See comments just above at `dummy_failure_jump' about the
7264 PUSH_FAILURE_POINT (NULL
, NULL
, -2);
7267 /* Have to succeed matching what follows at least n times.
7268 After that, handle like `on_failure_jump'. */
7270 EXTRACT_NUMBER (mcnt
, p
+ OFFSET_ADDRESS_SIZE
);
7271 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt
);
7274 /* Originally, this is how many times we HAVE to succeed. */
7278 p
+= OFFSET_ADDRESS_SIZE
;
7279 STORE_NUMBER_AND_INCR (p
, mcnt
);
7281 DEBUG_PRINT3 (" Setting %p to %d.\n", p
- OFFSET_ADDRESS_SIZE
7284 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p
- OFFSET_ADDRESS_SIZE
7291 DEBUG_PRINT2 (" Setting two bytes from %p to no_op.\n",
7292 p
+ OFFSET_ADDRESS_SIZE
);
7294 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n",
7295 p
+ OFFSET_ADDRESS_SIZE
);
7299 p
[1] = (UCHAR_T
) no_op
;
7301 p
[2] = (UCHAR_T
) no_op
;
7302 p
[3] = (UCHAR_T
) no_op
;
7309 EXTRACT_NUMBER (mcnt
, p
+ OFFSET_ADDRESS_SIZE
);
7310 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt
);
7312 /* Originally, this is how many times we CAN jump. */
7316 STORE_NUMBER (p
+ OFFSET_ADDRESS_SIZE
, mcnt
);
7319 DEBUG_PRINT3 (" Setting %p to %d.\n", p
+ OFFSET_ADDRESS_SIZE
,
7322 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p
+ OFFSET_ADDRESS_SIZE
,
7325 goto unconditional_jump
;
7327 /* If don't have to jump any more, skip over the rest of command. */
7329 p
+= 2 * OFFSET_ADDRESS_SIZE
;
7334 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
7336 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
7338 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
7340 DEBUG_PRINT3 (" Setting %p to %d.\n", p1
, mcnt
);
7342 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1
, mcnt
);
7344 STORE_NUMBER (p1
, mcnt
);
7349 /* The DEC Alpha C compiler 3.x generates incorrect code for the
7350 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
7351 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
7352 macro and introducing temporary variables works around the bug. */
7355 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7356 if (AT_WORD_BOUNDARY (d
))
7361 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7362 if (AT_WORD_BOUNDARY (d
))
7368 boolean prevchar
, thischar
;
7370 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7371 if (AT_STRINGS_BEG (d
) || AT_STRINGS_END (d
))
7374 prevchar
= WORDCHAR_P (d
- 1);
7375 thischar
= WORDCHAR_P (d
);
7376 if (prevchar
!= thischar
)
7383 boolean prevchar
, thischar
;
7385 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7386 if (AT_STRINGS_BEG (d
) || AT_STRINGS_END (d
))
7389 prevchar
= WORDCHAR_P (d
- 1);
7390 thischar
= WORDCHAR_P (d
);
7391 if (prevchar
!= thischar
)
7398 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
7399 if (!AT_STRINGS_END (d
) && WORDCHAR_P (d
)
7400 && (AT_STRINGS_BEG (d
) || !WORDCHAR_P (d
- 1)))
7405 DEBUG_PRINT1 ("EXECUTING wordend.\n");
7406 if (!AT_STRINGS_BEG (d
) && WORDCHAR_P (d
- 1)
7407 && (AT_STRINGS_END (d
) || !WORDCHAR_P (d
)))
7413 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
7414 if (PTR_CHAR_POS ((unsigned char *) d
) >= point
)
7419 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
7420 if (PTR_CHAR_POS ((unsigned char *) d
) != point
)
7425 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
7426 if (PTR_CHAR_POS ((unsigned char *) d
) <= point
)
7431 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt
);
7436 DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
7440 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7442 if (SYNTAX (d
[-1]) != (enum syntaxcode
) mcnt
)
7444 SET_REGS_MATCHED ();
7448 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt
);
7450 goto matchnotsyntax
;
7453 DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
7457 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7459 if (SYNTAX (d
[-1]) == (enum syntaxcode
) mcnt
)
7461 SET_REGS_MATCHED ();
7464 #else /* not emacs */
7466 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
7468 if (!WORDCHAR_P (d
))
7470 SET_REGS_MATCHED ();
7475 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
7479 SET_REGS_MATCHED ();
7482 #endif /* not emacs */
7487 continue; /* Successfully executed one pattern command; keep going. */
7490 /* We goto here if a matching operation fails. */
7492 if (!FAIL_STACK_EMPTY ())
7493 { /* A restart point is known. Restore to that state. */
7494 DEBUG_PRINT1 ("\nFAIL:\n");
7495 POP_FAILURE_POINT (d
, p
,
7496 lowest_active_reg
, highest_active_reg
,
7497 regstart
, regend
, reg_info
);
7499 /* If this failure point is a dummy, try the next one. */
7503 /* If we failed to the end of the pattern, don't examine *p. */
7507 boolean is_a_jump_n
= false;
7509 /* If failed to a backwards jump that's part of a repetition
7510 loop, need to pop this failure point and use the next one. */
7511 switch ((re_opcode_t
) *p
)
7515 case maybe_pop_jump
:
7516 case pop_failure_jump
:
7519 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7522 if ((is_a_jump_n
&& (re_opcode_t
) *p1
== succeed_n
)
7524 && (re_opcode_t
) *p1
== on_failure_jump
))
7532 if (d
>= string1
&& d
<= end1
)
7536 break; /* Matching at this starting point really fails. */
7540 goto restore_best_regs
;
7544 return -1; /* Failure to match. */
7547 /* Subroutine definitions for re_match_2. */
7550 /* We are passed P pointing to a register number after a start_memory.
7552 Return true if the pattern up to the corresponding stop_memory can
7553 match the empty string, and false otherwise.
7555 If we find the matching stop_memory, sets P to point to one past its number.
7556 Otherwise, sets P to an undefined byte less than or equal to END.
7558 We don't handle duplicates properly (yet). */
7561 PREFIX(group_match_null_string_p
) (
7562 UCHAR_T
**p
, UCHAR_T
*end
,
7563 PREFIX(register_info_type
) *reg_info
)
7566 /* Point to after the args to the start_memory. */
7567 UCHAR_T
*p1
= *p
+ 2;
7571 /* Skip over opcodes that can match nothing, and return true or
7572 false, as appropriate, when we get to one that can't, or to the
7573 matching stop_memory. */
7575 switch ((re_opcode_t
) *p1
)
7577 /* Could be either a loop or a series of alternatives. */
7578 case on_failure_jump
:
7580 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7582 /* If the next operation is not a jump backwards in the
7587 /* Go through the on_failure_jumps of the alternatives,
7588 seeing if any of the alternatives cannot match nothing.
7589 The last alternative starts with only a jump,
7590 whereas the rest start with on_failure_jump and end
7591 with a jump, e.g., here is the pattern for `a|b|c':
7593 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
7594 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
7597 So, we have to first go through the first (n-1)
7598 alternatives and then deal with the last one separately. */
7601 /* Deal with the first (n-1) alternatives, which start
7602 with an on_failure_jump (see above) that jumps to right
7603 past a jump_past_alt. */
7605 while ((re_opcode_t
) p1
[mcnt
-(1+OFFSET_ADDRESS_SIZE
)] ==
7608 /* `mcnt' holds how many bytes long the alternative
7609 is, including the ending `jump_past_alt' and
7612 if (!PREFIX(alt_match_null_string_p
) (p1
, p1
+ mcnt
-
7613 (1 + OFFSET_ADDRESS_SIZE
),
7617 /* Move to right after this alternative, including the
7621 /* Break if it's the beginning of an n-th alternative
7622 that doesn't begin with an on_failure_jump. */
7623 if ((re_opcode_t
) *p1
!= on_failure_jump
)
7626 /* Still have to check that it's not an n-th
7627 alternative that starts with an on_failure_jump. */
7629 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7630 if ((re_opcode_t
) p1
[mcnt
-(1+OFFSET_ADDRESS_SIZE
)] !=
7633 /* Get to the beginning of the n-th alternative. */
7634 p1
-= 1 + OFFSET_ADDRESS_SIZE
;
7639 /* Deal with the last alternative: go back and get number
7640 of the `jump_past_alt' just before it. `mcnt' contains
7641 the length of the alternative. */
7642 EXTRACT_NUMBER (mcnt
, p1
- OFFSET_ADDRESS_SIZE
);
7644 if (!PREFIX(alt_match_null_string_p
) (p1
, p1
+ mcnt
, reg_info
))
7647 p1
+= mcnt
; /* Get past the n-th alternative. */
7653 assert (p1
[1] == **p
);
7659 if (!PREFIX(common_op_match_null_string_p
) (&p1
, end
, reg_info
))
7662 } /* while p1 < end */
7665 } /* group_match_null_string_p */
7668 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
7669 It expects P to be the first byte of a single alternative and END one
7670 byte past the last. The alternative can contain groups. */
7673 PREFIX(alt_match_null_string_p
) (
7674 UCHAR_T
*p
, UCHAR_T
*end
,
7675 PREFIX(register_info_type
) *reg_info
)
7682 /* Skip over opcodes that can match nothing, and break when we get
7683 to one that can't. */
7685 switch ((re_opcode_t
) *p1
)
7688 case on_failure_jump
:
7690 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7695 if (!PREFIX(common_op_match_null_string_p
) (&p1
, end
, reg_info
))
7698 } /* while p1 < end */
7701 } /* alt_match_null_string_p */
7704 /* Deals with the ops common to group_match_null_string_p and
7705 alt_match_null_string_p.
7707 Sets P to one after the op and its arguments, if any. */
7710 PREFIX(common_op_match_null_string_p
) (
7711 UCHAR_T
**p
, UCHAR_T
*end
,
7712 PREFIX(register_info_type
) *reg_info
)
7719 switch ((re_opcode_t
) *p1
++)
7739 assert (reg_no
> 0 && reg_no
<= MAX_REGNUM
);
7740 ret
= PREFIX(group_match_null_string_p
) (&p1
, end
, reg_info
);
7742 /* Have to set this here in case we're checking a group which
7743 contains a group and a back reference to it. */
7745 if (REG_MATCH_NULL_STRING_P (reg_info
[reg_no
]) == MATCH_NULL_UNSET_VALUE
)
7746 REG_MATCH_NULL_STRING_P (reg_info
[reg_no
]) = ret
;
7752 /* If this is an optimized succeed_n for zero times, make the jump. */
7754 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7762 /* Get to the number of times to succeed. */
7763 p1
+= OFFSET_ADDRESS_SIZE
;
7764 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7768 p1
-= 2 * OFFSET_ADDRESS_SIZE
;
7769 EXTRACT_NUMBER_AND_INCR (mcnt
, p1
);
7777 if (!REG_MATCH_NULL_STRING_P (reg_info
[*p1
]))
7782 p1
+= 2 * OFFSET_ADDRESS_SIZE
;
7785 /* All other opcodes mean we cannot match the empty string. */
7791 } /* common_op_match_null_string_p */
7794 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
7795 bytes; nonzero otherwise. */
7798 PREFIX(bcmp_translate
) (
7799 const CHAR_T
*s1
, const CHAR_T
*s2
,
7801 __RE_TRANSLATE_TYPE translate
)
7803 register const UCHAR_T
*p1
= (const UCHAR_T
*) s1
;
7804 register const UCHAR_T
*p2
= (const UCHAR_T
*) s2
;
7808 if (((*p1
<=0xff)?translate
[*p1
++]:*p1
++)
7809 != ((*p2
<=0xff)?translate
[*p2
++]:*p2
++))
7812 if (translate
[*p1
++] != translate
[*p2
++]) return 1;
7820 #else /* not INSIDE_RECURSION */
7822 /* Entry points for GNU code. */
7824 /* re_compile_pattern is the GNU regular expression compiler: it
7825 compiles PATTERN (of length SIZE) and puts the result in BUFP.
7826 Returns 0 if the pattern was valid, otherwise an error string.
7828 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
7829 are set in BUFP on entry.
7831 We call regex_compile to do the actual compilation. */
7834 re_compile_pattern (const char *pattern
,
7836 struct re_pattern_buffer
*bufp
)
7840 /* GNU code is written to assume at least RE_NREGS registers will be set
7841 (and at least one extra will be -1). */
7842 bufp
->regs_allocated
= REGS_UNALLOCATED
;
7844 /* And GNU code determines whether or not to get register information
7845 by passing null for the REGS argument to re_match, etc., not by
7849 /* Match anchors at newline. */
7850 bufp
->newline_anchor
= 1;
7853 if (MB_CUR_MAX
!= 1)
7854 ret
= wcs_regex_compile (pattern
, length
, re_syntax_options
, bufp
);
7857 ret
= byte_regex_compile (pattern
, length
, re_syntax_options
, bufp
);
7861 return gettext (re_error_msgid
+ re_error_msgid_idx
[(int) ret
]);
7864 /* Entry points compatible with 4.2 BSD regex library. We don't define
7865 them unless specifically requested. */
7867 #if defined _REGEX_RE_COMP || defined _LIBC
7869 /* BSD has one and only one pattern buffer. */
7870 static struct re_pattern_buffer re_comp_buf
;
7874 /* Make these definitions weak in libc, so POSIX programs can redefine
7875 these names if they don't use our functions, and still use
7876 regcomp/regexec below without link errors. */
7879 re_comp (const char *s
)
7885 if (!re_comp_buf
.buffer
)
7886 return gettext ("No previous regular expression");
7890 if (!re_comp_buf
.buffer
)
7892 re_comp_buf
.buffer
= (unsigned char *) malloc (200);
7893 if (re_comp_buf
.buffer
== NULL
)
7894 return (char *) gettext (re_error_msgid
7895 + re_error_msgid_idx
[(int) REG_ESPACE
]);
7896 re_comp_buf
.allocated
= 200;
7898 re_comp_buf
.fastmap
= (char *) malloc (1 << BYTEWIDTH
);
7899 if (re_comp_buf
.fastmap
== NULL
)
7900 return (char *) gettext (re_error_msgid
7901 + re_error_msgid_idx
[(int) REG_ESPACE
]);
7904 /* Since `re_exec' always passes NULL for the `regs' argument, we
7905 don't need to initialize the pattern buffer fields which affect it. */
7907 /* Match anchors at newlines. */
7908 re_comp_buf
.newline_anchor
= 1;
7911 if (MB_CUR_MAX
!= 1)
7912 ret
= wcs_regex_compile (s
, strlen (s
), re_syntax_options
, &re_comp_buf
);
7915 ret
= byte_regex_compile (s
, strlen (s
), re_syntax_options
, &re_comp_buf
);
7920 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
7921 return (char *) gettext (re_error_msgid
+ re_error_msgid_idx
[(int) ret
]);
7926 #if defined _LIBC || defined __UCLIBC__
7929 re_exec (const char *s
)
7931 const int len
= strlen (s
);
7933 0 <= re_search (&re_comp_buf
, s
, len
, 0, len
, (struct re_registers
*) 0);
7936 #endif /* _REGEX_RE_COMP */
7938 /* POSIX.2 functions. Don't define these for Emacs. */
7942 /* regcomp takes a regular expression as a string and compiles it.
7944 PREG is a regex_t *. We do not expect any fields to be initialized,
7945 since POSIX says we shouldn't. Thus, we set
7947 `buffer' to the compiled pattern;
7948 `used' to the length of the compiled pattern;
7949 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
7950 REG_EXTENDED bit in CFLAGS is set; otherwise, to
7951 RE_SYNTAX_POSIX_BASIC;
7952 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
7953 `fastmap' to an allocated space for the fastmap;
7954 `fastmap_accurate' to zero;
7955 `re_nsub' to the number of subexpressions in PATTERN.
7957 PATTERN is the address of the pattern string.
7959 CFLAGS is a series of bits which affect compilation.
7961 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
7962 use POSIX basic syntax.
7964 If REG_NEWLINE is set, then . and [^...] don't match newline.
7965 Also, regexec will try a match beginning after every newline.
7967 If REG_ICASE is set, then we considers upper- and lowercase
7968 versions of letters to be equivalent when matching.
7970 If REG_NOSUB is set, then when PREG is passed to regexec, that
7971 routine will report only success or failure, and nothing about the
7974 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
7975 the return codes and their meanings.) */
7980 const char *pattern
,
7985 = (cflags
& REG_EXTENDED
) ?
7986 RE_SYNTAX_POSIX_EXTENDED
: RE_SYNTAX_POSIX_BASIC
;
7988 /* regex_compile will allocate the space for the compiled pattern. */
7990 preg
->allocated
= 0;
7993 /* Try to allocate space for the fastmap. */
7994 preg
->fastmap
= (char *) malloc (1 << BYTEWIDTH
);
7996 if (cflags
& REG_ICASE
)
8001 = (__RE_TRANSLATE_TYPE
) malloc (CHAR_SET_SIZE
8002 * sizeof (*(__RE_TRANSLATE_TYPE
)0));
8003 if (preg
->translate
== NULL
)
8004 return (int) REG_ESPACE
;
8006 /* Map uppercase characters to corresponding lowercase ones. */
8007 for (i
= 0; i
< CHAR_SET_SIZE
; i
++)
8008 preg
->translate
[i
] = ISUPPER (i
) ? TOLOWER (i
) : i
;
8011 preg
->translate
= NULL
;
8013 /* If REG_NEWLINE is set, newlines are treated differently. */
8014 if (cflags
& REG_NEWLINE
)
8015 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
8016 syntax
&= ~RE_DOT_NEWLINE
;
8017 syntax
|= RE_HAT_LISTS_NOT_NEWLINE
;
8018 /* It also changes the matching behavior. */
8019 preg
->newline_anchor
= 1;
8022 preg
->newline_anchor
= 0;
8024 preg
->no_sub
= !!(cflags
& REG_NOSUB
);
8026 /* POSIX says a null character in the pattern terminates it, so we
8027 can use strlen here in compiling the pattern. */
8029 if (MB_CUR_MAX
!= 1)
8030 ret
= wcs_regex_compile (pattern
, strlen (pattern
), syntax
, preg
);
8033 ret
= byte_regex_compile (pattern
, strlen (pattern
), syntax
, preg
);
8035 /* POSIX doesn't distinguish between an unmatched open-group and an
8036 unmatched close-group: both are REG_EPAREN. */
8037 if (ret
== REG_ERPAREN
) ret
= REG_EPAREN
;
8039 if (ret
== REG_NOERROR
&& preg
->fastmap
)
8041 /* Compute the fastmap now, since regexec cannot modify the pattern
8043 if (re_compile_fastmap (preg
) == -2)
8045 /* Some error occurred while computing the fastmap, just forget
8047 free (preg
->fastmap
);
8048 preg
->fastmap
= NULL
;
8056 /* regexec searches for a given pattern, specified by PREG, in the
8059 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
8060 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
8061 least NMATCH elements, and we set them to the offsets of the
8062 corresponding matched substrings.
8064 EFLAGS specifies `execution flags' which affect matching: if
8065 REG_NOTBOL is set, then ^ does not match at the beginning of the
8066 string; if REG_NOTEOL is set, then $ does not match at the end.
8068 We return 0 if we find a match and REG_NOMATCH if not. */
8072 const regex_t
*preg
,
8075 regmatch_t pmatch
[],
8079 struct re_registers regs
;
8080 regex_t private_preg
;
8081 int len
= strlen (string
);
8082 boolean want_reg_info
= !preg
->no_sub
&& nmatch
> 0;
8084 /* use hidden memcpy() ourselves rather than gcc calling public memcpy() */
8085 memcpy(&private_preg
, preg
, sizeof(*preg
));
8087 private_preg
.not_bol
= !!(eflags
& REG_NOTBOL
);
8088 private_preg
.not_eol
= !!(eflags
& REG_NOTEOL
);
8090 /* The user has told us exactly how many registers to return
8091 information about, via `nmatch'. We have to pass that on to the
8092 matching routines. */
8093 private_preg
.regs_allocated
= REGS_FIXED
;
8097 regs
.num_regs
= nmatch
;
8098 regs
.start
= TALLOC (nmatch
* 2, regoff_t
);
8099 if (regs
.start
== NULL
)
8100 return (int) REG_NOMATCH
;
8101 regs
.end
= regs
.start
+ nmatch
;
8104 /* Perform the searching operation. */
8105 ret
= re_search (&private_preg
, string
, len
,
8106 /* start: */ 0, /* range: */ len
,
8107 want_reg_info
? ®s
: (struct re_registers
*) 0);
8109 /* Copy the register information to the POSIX structure. */
8116 for (r
= 0; r
< nmatch
; r
++)
8118 pmatch
[r
].rm_so
= regs
.start
[r
];
8119 pmatch
[r
].rm_eo
= regs
.end
[r
];
8123 /* If we needed the temporary register info, free the space now. */
8127 /* We want zero return to mean success, unlike `re_search'. */
8128 return ret
>= 0 ? (int) REG_NOERROR
: (int) REG_NOMATCH
;
8130 libc_hidden_def(regexec
)
8133 /* Returns a message corresponding to an error code, ERRCODE, returned
8134 from either regcomp or regexec. We don't use PREG here. */
8139 const regex_t
* preg attribute_unused
,
8147 || errcode
>= (int) (sizeof (re_error_msgid_idx
)
8148 / sizeof (re_error_msgid_idx
[0])))
8149 /* Only error codes returned by the rest of the code should be passed
8150 to this routine. If we are given anything else, or if other regex
8151 code generates an invalid error code, then the program has a bug.
8152 Dump core so we can fix it. */
8155 msg
= gettext (re_error_msgid
+ re_error_msgid_idx
[errcode
]);
8157 msg_size
= strlen (msg
) + 1; /* Includes the null. */
8159 if (errbuf_size
!= 0)
8161 if (msg_size
> errbuf_size
)
8163 memcpy (errbuf
, msg
, errbuf_size
- 1);
8164 errbuf
[errbuf_size
- 1] = 0;
8167 memcpy (errbuf
, msg
, msg_size
);
8174 /* Free dynamically allocated space used by PREG. */
8177 regfree (regex_t
*preg
)
8179 free (preg
->buffer
);
8180 preg
->buffer
= NULL
;
8182 preg
->allocated
= 0;
8185 free (preg
->fastmap
);
8186 preg
->fastmap
= NULL
;
8187 preg
->fastmap_accurate
= 0;
8189 free (preg
->translate
);
8190 preg
->translate
= NULL
;
8192 libc_hidden_def(regfree
)
8194 #endif /* not emacs */
8196 #endif /* not INSIDE_RECURSION */
8200 #undef STORE_NUMBER_AND_INCR
8201 #undef EXTRACT_NUMBER
8202 #undef EXTRACT_NUMBER_AND_INCR
8204 #undef DEBUG_PRINT_COMPILED_PATTERN
8205 #undef DEBUG_PRINT_DOUBLE_STRING
8207 #undef INIT_FAIL_STACK
8208 #undef RESET_FAIL_STACK
8209 #undef DOUBLE_FAIL_STACK
8210 #undef PUSH_PATTERN_OP
8211 #undef PUSH_FAILURE_POINTER
8212 #undef PUSH_FAILURE_INT
8213 #undef PUSH_FAILURE_ELT
8214 #undef POP_FAILURE_POINTER
8215 #undef POP_FAILURE_INT
8216 #undef POP_FAILURE_ELT
8219 #undef PUSH_FAILURE_POINT
8220 #undef POP_FAILURE_POINT
8222 #undef REG_UNSET_VALUE
8230 #undef INIT_BUF_SIZE
8231 #undef GET_BUFFER_SPACE
8239 #undef EXTEND_BUFFER
8240 #undef GET_UNSIGNED_NUMBER
8241 #undef FREE_STACK_RETURN
8243 # undef POINTER_TO_OFFSET
8244 # undef MATCHING_IN_FRST_STRING
8246 # undef AT_STRINGS_BEG
8247 # undef AT_STRINGS_END
8250 # undef FREE_VARIABLES
8251 # undef NO_HIGHEST_ACTIVE_REG
8252 # undef NO_LOWEST_ACTIVE_REG
8256 # undef COMPILED_BUFFER_VAR
8257 # undef OFFSET_ADDRESS_SIZE
8258 # undef CHAR_CLASS_SIZE
8265 # define DEFINED_ONCE