1 /* Extended regular expression matching and search library, version
2 0.12. (Implements POSIX draft P1003.2/D11.2, except for some of the
3 internationalization features.)
5 Copyright (C) 1993-2017 Free Software Foundation, Inc.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 - structure the opcode space into opcode+flag.
22 - merge with glibc's regex.[ch].
23 - replace (succeed_n + jump_n + set_number_at) with something that doesn't
24 need to modify the compiled regexp so that re_match can be reentrant.
25 - get rid of on_failure_jump_smart by doing the optimization in re_comp
26 rather than at run-time, so that re_match can be reentrant.
29 /* AIX requires this to be the first thing in the file. */
30 #if defined _AIX && !defined REGEX_MALLOC
34 /* Ignore some GCC warnings for now. This section should go away
35 once the Emacs and Gnulib regex code is merged. */
36 #if 4 < __GNUC__ + (5 <= __GNUC_MINOR__) || defined __clang__
37 # pragma GCC diagnostic ignored "-Wstrict-overflow"
39 # pragma GCC diagnostic ignored "-Wunused-function"
40 # pragma GCC diagnostic ignored "-Wunused-macros"
41 # pragma GCC diagnostic ignored "-Wunused-result"
42 # pragma GCC diagnostic ignored "-Wunused-variable"
46 #if 4 < __GNUC__ + (6 <= __GNUC_MINOR__) && ! defined __clang__
47 # pragma GCC diagnostic ignored "-Wunused-but-set-variable"
56 /* We need this for `regex.h', and perhaps for the Emacs include files. */
57 # include <sys/types.h>
60 /* Whether to use ISO C Amendment 1 wide char functions.
61 Those should not be used for Emacs since it uses its own. */
63 #define WIDE_CHAR_SUPPORT 1
65 #define WIDE_CHAR_SUPPORT \
66 (HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_BTOWC && !emacs)
69 /* For platform which support the ISO C amendment 1 functionality we
70 support user defined character classes. */
72 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
78 /* We have to keep the namespace clean. */
79 # define regfree(preg) __regfree (preg)
80 # define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
81 # define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
82 # define regerror(err_code, preg, errbuf, errbuf_size) \
83 __regerror (err_code, preg, errbuf, errbuf_size)
84 # define re_set_registers(bu, re, nu, st, en) \
85 __re_set_registers (bu, re, nu, st, en)
86 # define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
87 __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
88 # define re_match(bufp, string, size, pos, regs) \
89 __re_match (bufp, string, size, pos, regs)
90 # define re_search(bufp, string, size, startpos, range, regs) \
91 __re_search (bufp, string, size, startpos, range, regs)
92 # define re_compile_pattern(pattern, length, bufp) \
93 __re_compile_pattern (pattern, length, bufp)
94 # define re_set_syntax(syntax) __re_set_syntax (syntax)
95 # define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
96 __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
97 # define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
99 /* Make sure we call libc's function even if the user overrides them. */
100 # define btowc __btowc
101 # define iswctype __iswctype
102 # define wctype __wctype
104 # define WEAK_ALIAS(a,b) weak_alias (a, b)
106 /* We are also using some library internals. */
107 # include <locale/localeinfo.h>
108 # include <locale/elem-hash.h>
109 # include <langinfo.h>
111 # define WEAK_ALIAS(a,b)
114 /* This is for other GNU distributions with internationalized messages. */
115 #if HAVE_LIBINTL_H || defined _LIBC
116 # include <libintl.h>
118 # define gettext(msgid) (msgid)
122 /* This define is so xgettext can find the internationalizable
124 # define gettext_noop(String) String
127 /* The `emacs' switch turns on certain matching commands
128 that make sense only in Emacs. */
132 # include "character.h"
136 # include "category.h"
138 /* Make syntax table lookup grant data in gl_state. */
139 # define SYNTAX(c) syntax_property (c, 1)
144 # define malloc xmalloc
148 # define realloc xrealloc
154 /* Converts the pointer to the char to BEG-based offset from the start. */
155 # define PTR_TO_OFFSET(d) POS_AS_IN_BUFFER (POINTER_TO_OFFSET (d))
156 /* Strings are 0-indexed, buffers are 1-indexed; we pun on the boolean
157 result to get the right base index. */
158 # define POS_AS_IN_BUFFER(p) ((p) + (NILP (re_match_object) || BUFFERP (re_match_object)))
160 # define RE_MULTIBYTE_P(bufp) ((bufp)->multibyte)
161 # define RE_TARGET_MULTIBYTE_P(bufp) ((bufp)->target_multibyte)
162 # define RE_STRING_CHAR(p, multibyte) \
163 (multibyte ? (STRING_CHAR (p)) : (*(p)))
164 # define RE_STRING_CHAR_AND_LENGTH(p, len, multibyte) \
165 (multibyte ? (STRING_CHAR_AND_LENGTH (p, len)) : ((len) = 1, *(p)))
167 # define RE_CHAR_TO_MULTIBYTE(c) UNIBYTE_TO_CHAR (c)
169 # define RE_CHAR_TO_UNIBYTE(c) CHAR_TO_BYTE_SAFE (c)
171 /* Set C a (possibly converted to multibyte) character before P. P
172 points into a string which is the virtual concatenation of STR1
173 (which ends at END1) or STR2 (which ends at END2). */
174 # define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
176 if (target_multibyte) \
178 re_char *dtemp = (p) == (str2) ? (end1) : (p); \
179 re_char *dlimit = ((p) > (str2) && (p) <= (end2)) ? (str2) : (str1); \
180 while (dtemp-- > dlimit && !CHAR_HEAD_P (*dtemp)); \
181 c = STRING_CHAR (dtemp); \
185 (c = ((p) == (str2) ? (end1) : (p))[-1]); \
186 (c) = RE_CHAR_TO_MULTIBYTE (c); \
190 /* Set C a (possibly converted to multibyte) character at P, and set
191 LEN to the byte length of that character. */
192 # define GET_CHAR_AFTER(c, p, len) \
194 if (target_multibyte) \
195 (c) = STRING_CHAR_AND_LENGTH (p, len); \
200 (c) = RE_CHAR_TO_MULTIBYTE (c); \
204 #else /* not emacs */
206 /* If we are not linking with Emacs proper,
207 we can't use the relocating allocator
208 even if config.h says that we can. */
213 /* When used in Emacs's lib-src, we need xmalloc and xrealloc. */
216 xmalloc (size_t size
)
218 void *val
= malloc (size
);
221 write (STDERR_FILENO
, "virtual memory exhausted\n", 25);
228 xrealloc (void *block
, size_t size
)
231 /* We must call malloc explicitly when BLOCK is 0, since some
232 reallocs don't do this. */
236 val
= realloc (block
, size
);
239 write (STDERR_FILENO
, "virtual memory exhausted\n", 25);
248 # define malloc xmalloc
252 # define realloc xrealloc
254 # include <stdbool.h>
257 /* Define the syntax stuff for \<, \>, etc. */
259 /* Sword must be nonzero for the wordchar pattern commands in re_match_2. */
260 enum syntaxcode
{ Swhitespace
= 0, Sword
= 1, Ssymbol
= 2 };
262 /* Dummy macros for non-Emacs environments. */
263 # define MAX_MULTIBYTE_LENGTH 1
264 # define RE_MULTIBYTE_P(x) 0
265 # define RE_TARGET_MULTIBYTE_P(x) 0
266 # define WORD_BOUNDARY_P(c1, c2) (0)
267 # define BYTES_BY_CHAR_HEAD(p) (1)
268 # define PREV_CHAR_BOUNDARY(p, limit) ((p)--)
269 # define STRING_CHAR(p) (*(p))
270 # define RE_STRING_CHAR(p, multibyte) STRING_CHAR (p)
271 # define CHAR_STRING(c, s) (*(s) = (c), 1)
272 # define STRING_CHAR_AND_LENGTH(p, actual_len) ((actual_len) = 1, *(p))
273 # define RE_STRING_CHAR_AND_LENGTH(p, len, multibyte) STRING_CHAR_AND_LENGTH (p, len)
274 # define RE_CHAR_TO_MULTIBYTE(c) (c)
275 # define RE_CHAR_TO_UNIBYTE(c) (c)
276 # define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
277 (c = ((p) == (str2) ? *((end1) - 1) : *((p) - 1)))
278 # define GET_CHAR_AFTER(c, p, len) \
280 # define CHAR_BYTE8_P(c) (0)
281 # define CHAR_LEADING_CODE(c) (c)
283 #endif /* not emacs */
286 # define RE_TRANSLATE(TBL, C) ((unsigned char)(TBL)[C])
287 # define RE_TRANSLATE_P(TBL) (TBL)
290 /* Get the interface, including the syntax bits. */
293 /* isalpha etc. are used for the character classes. */
298 /* 1 if C is an ASCII character. */
299 # define IS_REAL_ASCII(c) ((c) < 0200)
301 /* 1 if C is a unibyte character. */
302 # define ISUNIBYTE(c) (SINGLE_BYTE_CHAR_P ((c)))
304 /* The Emacs definitions should not be directly affected by locales. */
306 /* In Emacs, these are only used for single-byte characters. */
307 # define ISDIGIT(c) ((c) >= '0' && (c) <= '9')
308 # define ISCNTRL(c) ((c) < ' ')
309 # define ISXDIGIT(c) (((c) >= '0' && (c) <= '9') \
310 || ((c) >= 'a' && (c) <= 'f') \
311 || ((c) >= 'A' && (c) <= 'F'))
313 /* The rest must handle multibyte characters. */
315 # define ISBLANK(c) (IS_REAL_ASCII (c) \
316 ? ((c) == ' ' || (c) == '\t') \
319 # define ISGRAPH(c) (SINGLE_BYTE_CHAR_P (c) \
320 ? (c) > ' ' && !((c) >= 0177 && (c) <= 0240) \
323 # define ISPRINT(c) (SINGLE_BYTE_CHAR_P (c) \
324 ? (c) >= ' ' && !((c) >= 0177 && (c) <= 0237) \
327 # define ISALNUM(c) (IS_REAL_ASCII (c) \
328 ? (((c) >= 'a' && (c) <= 'z') \
329 || ((c) >= 'A' && (c) <= 'Z') \
330 || ((c) >= '0' && (c) <= '9')) \
333 # define ISALPHA(c) (IS_REAL_ASCII (c) \
334 ? (((c) >= 'a' && (c) <= 'z') \
335 || ((c) >= 'A' && (c) <= 'Z')) \
338 # define ISLOWER(c) lowercasep (c)
340 # define ISPUNCT(c) (IS_REAL_ASCII (c) \
341 ? ((c) > ' ' && (c) < 0177 \
342 && !(((c) >= 'a' && (c) <= 'z') \
343 || ((c) >= 'A' && (c) <= 'Z') \
344 || ((c) >= '0' && (c) <= '9'))) \
345 : SYNTAX (c) != Sword)
347 # define ISSPACE(c) (SYNTAX (c) == Swhitespace)
349 # define ISUPPER(c) uppercasep (c)
351 # define ISWORD(c) (SYNTAX (c) == Sword)
353 #else /* not emacs */
355 /* 1 if C is an ASCII character. */
356 # define IS_REAL_ASCII(c) ((c) < 0200)
358 /* This distinction is not meaningful, except in Emacs. */
359 # define ISUNIBYTE(c) 1
362 # define ISBLANK(c) isblank (c)
364 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
367 # define ISGRAPH(c) isgraph (c)
369 # define ISGRAPH(c) (isprint (c) && !isspace (c))
372 /* Solaris defines ISPRINT so we must undefine it first. */
374 # define ISPRINT(c) isprint (c)
375 # define ISDIGIT(c) isdigit (c)
376 # define ISALNUM(c) isalnum (c)
377 # define ISALPHA(c) isalpha (c)
378 # define ISCNTRL(c) iscntrl (c)
379 # define ISLOWER(c) islower (c)
380 # define ISPUNCT(c) ispunct (c)
381 # define ISSPACE(c) isspace (c)
382 # define ISUPPER(c) isupper (c)
383 # define ISXDIGIT(c) isxdigit (c)
385 # define ISWORD(c) ISALPHA (c)
388 # define TOLOWER(c) _tolower (c)
390 # define TOLOWER(c) tolower (c)
393 /* How many characters in the character set. */
394 # define CHAR_SET_SIZE 256
398 extern char *re_syntax_table
;
400 # else /* not SYNTAX_TABLE */
402 static char re_syntax_table
[CHAR_SET_SIZE
];
405 init_syntax_once (void)
413 memset (re_syntax_table
, 0, sizeof re_syntax_table
);
415 for (c
= 0; c
< CHAR_SET_SIZE
; ++c
)
417 re_syntax_table
[c
] = Sword
;
419 re_syntax_table
['_'] = Ssymbol
;
424 # endif /* not SYNTAX_TABLE */
426 # define SYNTAX(c) re_syntax_table[(c)]
428 #endif /* not emacs */
430 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
432 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
433 use `alloca' instead of `malloc'. This is because using malloc in
434 re_search* or re_match* could cause memory leaks when C-g is used in
435 Emacs; also, malloc is slower and causes storage fragmentation. On
436 the other hand, malloc is more portable, and easier to debug.
438 Because we sometimes use alloca, some routines have to be macros,
439 not functions -- `alloca'-allocated space disappears at the end of the
440 function it is called in. */
444 # define REGEX_ALLOCATE malloc
445 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
446 # define REGEX_FREE free
448 #else /* not REGEX_MALLOC */
451 # define REGEX_USE_SAFE_ALLOCA USE_SAFE_ALLOCA
452 # define REGEX_SAFE_FREE() SAFE_FREE ()
453 # define REGEX_ALLOCATE SAFE_ALLOCA
456 # define REGEX_ALLOCATE alloca
459 /* Assumes a `char *destination' variable. */
460 # define REGEX_REALLOCATE(source, osize, nsize) \
461 (destination = REGEX_ALLOCATE (nsize), \
462 memcpy (destination, source, osize))
464 /* No need to do anything to free, after alloca. */
465 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
467 #endif /* not REGEX_MALLOC */
469 #ifndef REGEX_USE_SAFE_ALLOCA
470 # define REGEX_USE_SAFE_ALLOCA ((void) 0)
471 # define REGEX_SAFE_FREE() ((void) 0)
474 /* Define how to allocate the failure stack. */
476 #if defined REL_ALLOC && defined REGEX_MALLOC
478 # define REGEX_ALLOCATE_STACK(size) \
479 r_alloc (&failure_stack_ptr, (size))
480 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
481 r_re_alloc (&failure_stack_ptr, (nsize))
482 # define REGEX_FREE_STACK(ptr) \
483 r_alloc_free (&failure_stack_ptr)
485 #else /* not using relocating allocator */
487 # define REGEX_ALLOCATE_STACK(size) REGEX_ALLOCATE (size)
488 # define REGEX_REALLOCATE_STACK(source, o, n) REGEX_REALLOCATE (source, o, n)
489 # define REGEX_FREE_STACK(ptr) REGEX_FREE (ptr)
491 #endif /* not using relocating allocator */
494 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
495 `string1' or just past its end. This works if PTR is NULL, which is
497 #define FIRST_STRING_P(ptr) \
498 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
500 /* (Re)Allocate N items of type T using malloc, or fail. */
501 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
502 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
503 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
505 #define BYTEWIDTH 8 /* In bits. */
510 # define max(a, b) ((a) > (b) ? (a) : (b))
511 # define min(a, b) ((a) < (b) ? (a) : (b))
514 /* Type of source-pattern and string chars. */
516 typedef unsigned char re_char
;
517 typedef const re_char const_re_char
;
519 typedef const unsigned char re_char
;
520 typedef re_char const_re_char
;
523 typedef char boolean
;
525 static regoff_t
re_match_2_internal (struct re_pattern_buffer
*bufp
,
526 re_char
*string1
, size_t size1
,
527 re_char
*string2
, size_t size2
,
529 struct re_registers
*regs
,
532 /* These are the command codes that appear in compiled regular
533 expressions. Some opcodes are followed by argument bytes. A
534 command code can specify any interpretation whatsoever for its
535 arguments. Zero bytes may appear in the compiled regular expression. */
541 /* Succeed right away--no more backtracking. */
544 /* Followed by one byte giving n, then by n literal bytes. */
547 /* Matches any (more or less) character. */
550 /* Matches any one char belonging to specified set. First
551 following byte is number of bitmap bytes. Then come bytes
552 for a bitmap saying which chars are in. Bits in each byte
553 are ordered low-bit-first. A character is in the set if its
554 bit is 1. A character too large to have a bit in the map is
555 automatically not in the set.
557 If the length byte has the 0x80 bit set, then that stuff
558 is followed by a range table:
559 2 bytes of flags for character sets (low 8 bits, high 8 bits)
560 See RANGE_TABLE_WORK_BITS below.
561 2 bytes, the number of pairs that follow (upto 32767)
562 pairs, each 2 multibyte characters,
563 each multibyte character represented as 3 bytes. */
566 /* Same parameters as charset, but match any character that is
567 not one of those specified. */
570 /* Start remembering the text that is matched, for storing in a
571 register. Followed by one byte with the register number, in
572 the range 0 to one less than the pattern buffer's re_nsub
576 /* Stop remembering the text that is matched and store it in a
577 memory register. Followed by one byte with the register
578 number, in the range 0 to one less than `re_nsub' in the
582 /* Match a duplicate of something remembered. Followed by one
583 byte containing the register number. */
586 /* Fail unless at beginning of line. */
589 /* Fail unless at end of line. */
592 /* Succeeds if at beginning of buffer (if emacs) or at beginning
593 of string to be matched (if not). */
596 /* Analogously, for end of buffer/string. */
599 /* Followed by two byte relative address to which to jump. */
602 /* Followed by two-byte relative address of place to resume at
603 in case of failure. */
606 /* Like on_failure_jump, but pushes a placeholder instead of the
607 current string position when executed. */
608 on_failure_keep_string_jump
,
610 /* Just like `on_failure_jump', except that it checks that we
611 don't get stuck in an infinite loop (matching an empty string
613 on_failure_jump_loop
,
615 /* Just like `on_failure_jump_loop', except that it checks for
616 a different kind of loop (the kind that shows up with non-greedy
617 operators). This operation has to be immediately preceded
619 on_failure_jump_nastyloop
,
621 /* A smart `on_failure_jump' used for greedy * and + operators.
622 It analyzes the loop before which it is put and if the
623 loop does not require backtracking, it changes itself to
624 `on_failure_keep_string_jump' and short-circuits the loop,
625 else it just defaults to changing itself into `on_failure_jump'.
626 It assumes that it is pointing to just past a `jump'. */
627 on_failure_jump_smart
,
629 /* Followed by two-byte relative address and two-byte number n.
630 After matching N times, jump to the address upon failure.
631 Does not work if N starts at 0: use on_failure_jump_loop
635 /* Followed by two-byte relative address, and two-byte number n.
636 Jump to the address N times, then fail. */
639 /* Set the following two-byte relative address to the
640 subsequent two-byte number. The address *includes* the two
644 wordbeg
, /* Succeeds if at word beginning. */
645 wordend
, /* Succeeds if at word end. */
647 wordbound
, /* Succeeds if at a word boundary. */
648 notwordbound
, /* Succeeds if not at a word boundary. */
650 symbeg
, /* Succeeds if at symbol beginning. */
651 symend
, /* Succeeds if at symbol end. */
653 /* Matches any character whose syntax is specified. Followed by
654 a byte which contains a syntax code, e.g., Sword. */
657 /* Matches any character whose syntax is not that specified. */
661 , at_dot
, /* Succeeds if at point. */
663 /* Matches any character whose category-set contains the specified
664 category. The operator is followed by a byte which contains a
665 category code (mnemonic ASCII character). */
668 /* Matches any character whose category-set does not contain the
669 specified category. The operator is followed by a byte which
670 contains the category code (mnemonic ASCII character). */
675 /* Common operations on the compiled pattern. */
677 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
679 #define STORE_NUMBER(destination, number) \
681 (destination)[0] = (number) & 0377; \
682 (destination)[1] = (number) >> 8; \
685 /* Same as STORE_NUMBER, except increment DESTINATION to
686 the byte after where the number is stored. Therefore, DESTINATION
687 must be an lvalue. */
689 #define STORE_NUMBER_AND_INCR(destination, number) \
691 STORE_NUMBER (destination, number); \
692 (destination) += 2; \
695 /* Put into DESTINATION a number stored in two contiguous bytes starting
698 #define EXTRACT_NUMBER(destination, source) \
699 ((destination) = extract_number (source))
702 extract_number (re_char
*source
)
704 unsigned leading_byte
= SIGN_EXTEND_CHAR (source
[1]);
705 return (leading_byte
<< 8) + source
[0];
708 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
709 SOURCE must be an lvalue. */
711 #define EXTRACT_NUMBER_AND_INCR(destination, source) \
712 ((destination) = extract_number_and_incr (&source))
715 extract_number_and_incr (re_char
**source
)
717 int num
= extract_number (*source
);
722 /* Store a multibyte character in three contiguous bytes starting
723 DESTINATION, and increment DESTINATION to the byte after where the
724 character is stored. Therefore, DESTINATION must be an lvalue. */
726 #define STORE_CHARACTER_AND_INCR(destination, character) \
728 (destination)[0] = (character) & 0377; \
729 (destination)[1] = ((character) >> 8) & 0377; \
730 (destination)[2] = (character) >> 16; \
731 (destination) += 3; \
734 /* Put into DESTINATION a character stored in three contiguous bytes
735 starting at SOURCE. */
737 #define EXTRACT_CHARACTER(destination, source) \
739 (destination) = ((source)[0] \
740 | ((source)[1] << 8) \
741 | ((source)[2] << 16)); \
745 /* Macros for charset. */
747 /* Size of bitmap of charset P in bytes. P is a start of charset,
748 i.e. *P is (re_opcode_t) charset or (re_opcode_t) charset_not. */
749 #define CHARSET_BITMAP_SIZE(p) ((p)[1] & 0x7F)
751 /* Nonzero if charset P has range table. */
752 #define CHARSET_RANGE_TABLE_EXISTS_P(p) ((p)[1] & 0x80)
754 /* Return the address of range table of charset P. But not the start
755 of table itself, but the before where the number of ranges is
756 stored. `2 +' means to skip re_opcode_t and size of bitmap,
757 and the 2 bytes of flags at the start of the range table. */
758 #define CHARSET_RANGE_TABLE(p) (&(p)[4 + CHARSET_BITMAP_SIZE (p)])
761 /* Extract the bit flags that start a range table. */
762 #define CHARSET_RANGE_TABLE_BITS(p) \
763 ((p)[2 + CHARSET_BITMAP_SIZE (p)] \
764 + (p)[3 + CHARSET_BITMAP_SIZE (p)] * 0x100)
767 /* Return the address of end of RANGE_TABLE. COUNT is number of
768 ranges (which is a pair of (start, end)) in the RANGE_TABLE. `* 2'
769 is start of range and end of range. `* 3' is size of each start
771 #define CHARSET_RANGE_TABLE_END(range_table, count) \
772 ((range_table) + (count) * 2 * 3)
774 /* If DEBUG is defined, Regex prints many voluminous messages about what
775 it is doing (if the variable `debug' is nonzero). If linked with the
776 main program in `iregex.c', you can enter patterns and strings
777 interactively. And if linked with the main program in `main.c' and
778 the other test files, you can run the already-written tests. */
782 /* We use standard I/O for debugging. */
785 /* It is useful to test things that ``must'' be true when debugging. */
788 static int debug
= -100000;
790 # define DEBUG_STATEMENT(e) e
791 # define DEBUG_PRINT(...) if (debug > 0) printf (__VA_ARGS__)
792 # define DEBUG_COMPILES_ARGUMENTS
793 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
794 if (debug > 0) print_partial_compiled_pattern (s, e)
795 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
796 if (debug > 0) print_double_string (w, s1, sz1, s2, sz2)
799 /* Print the fastmap in human-readable form. */
802 print_fastmap (char *fastmap
)
804 unsigned was_a_range
= 0;
807 while (i
< (1 << BYTEWIDTH
))
813 while (i
< (1 << BYTEWIDTH
) && fastmap
[i
])
829 /* Print a compiled pattern string in human-readable form, starting at
830 the START pointer into it and ending just before the pointer END. */
833 print_partial_compiled_pattern (re_char
*start
, re_char
*end
)
841 fprintf (stderr
, "(null)\n");
845 /* Loop over pattern commands. */
848 fprintf (stderr
, "%td:\t", p
- start
);
850 switch ((re_opcode_t
) *p
++)
853 fprintf (stderr
, "/no_op");
857 fprintf (stderr
, "/succeed");
862 fprintf (stderr
, "/exactn/%d", mcnt
);
865 fprintf (stderr
, "/%c", *p
++);
871 fprintf (stderr
, "/start_memory/%d", *p
++);
875 fprintf (stderr
, "/stop_memory/%d", *p
++);
879 fprintf (stderr
, "/duplicate/%d", *p
++);
883 fprintf (stderr
, "/anychar");
889 register int c
, last
= -100;
890 register int in_range
= 0;
891 int length
= CHARSET_BITMAP_SIZE (p
- 1);
892 int has_range_table
= CHARSET_RANGE_TABLE_EXISTS_P (p
- 1);
894 fprintf (stderr
, "/charset [%s",
895 (re_opcode_t
) *(p
- 1) == charset_not
? "^" : "");
898 fprintf (stderr
, " !extends past end of pattern! ");
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
)
907 fprintf (stderr
, "-");
910 /* Have we broken a range? */
911 else if (last
+ 1 != c
&& in_range
)
913 fprintf (stderr
, "%c", last
);
918 fprintf (stderr
, "%c", c
);
924 fprintf (stderr
, "%c", last
);
926 fprintf (stderr
, "]");
933 fprintf (stderr
, "has-range-table");
935 /* ??? Should print the range table; for now, just skip it. */
936 p
+= 2; /* skip range table bits */
937 EXTRACT_NUMBER_AND_INCR (count
, p
);
938 p
= CHARSET_RANGE_TABLE_END (p
, count
);
944 fprintf (stderr
, "/begline");
948 fprintf (stderr
, "/endline");
951 case on_failure_jump
:
952 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
953 fprintf (stderr
, "/on_failure_jump to %td", p
+ mcnt
- start
);
956 case on_failure_keep_string_jump
:
957 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
958 fprintf (stderr
, "/on_failure_keep_string_jump to %td",
962 case on_failure_jump_nastyloop
:
963 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
964 fprintf (stderr
, "/on_failure_jump_nastyloop to %td",
968 case on_failure_jump_loop
:
969 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
970 fprintf (stderr
, "/on_failure_jump_loop to %td",
974 case on_failure_jump_smart
:
975 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
976 fprintf (stderr
, "/on_failure_jump_smart to %td",
981 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
982 fprintf (stderr
, "/jump to %td", p
+ mcnt
- start
);
986 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
987 EXTRACT_NUMBER_AND_INCR (mcnt2
, p
);
988 fprintf (stderr
, "/succeed_n to %td, %d times",
989 p
- 2 + mcnt
- start
, mcnt2
);
993 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
994 EXTRACT_NUMBER_AND_INCR (mcnt2
, p
);
995 fprintf (stderr
, "/jump_n to %td, %d times",
996 p
- 2 + mcnt
- start
, mcnt2
);
1000 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
1001 EXTRACT_NUMBER_AND_INCR (mcnt2
, p
);
1002 fprintf (stderr
, "/set_number_at location %td to %d",
1003 p
- 2 + mcnt
- start
, mcnt2
);
1007 fprintf (stderr
, "/wordbound");
1011 fprintf (stderr
, "/notwordbound");
1015 fprintf (stderr
, "/wordbeg");
1019 fprintf (stderr
, "/wordend");
1023 fprintf (stderr
, "/symbeg");
1027 fprintf (stderr
, "/symend");
1031 fprintf (stderr
, "/syntaxspec");
1033 fprintf (stderr
, "/%d", mcnt
);
1037 fprintf (stderr
, "/notsyntaxspec");
1039 fprintf (stderr
, "/%d", mcnt
);
1044 fprintf (stderr
, "/at_dot");
1048 fprintf (stderr
, "/categoryspec");
1050 fprintf (stderr
, "/%d", mcnt
);
1053 case notcategoryspec
:
1054 fprintf (stderr
, "/notcategoryspec");
1056 fprintf (stderr
, "/%d", mcnt
);
1061 fprintf (stderr
, "/begbuf");
1065 fprintf (stderr
, "/endbuf");
1069 fprintf (stderr
, "?%d", *(p
-1));
1072 fprintf (stderr
, "\n");
1075 fprintf (stderr
, "%td:\tend of pattern.\n", p
- start
);
1080 print_compiled_pattern (struct re_pattern_buffer
*bufp
)
1082 re_char
*buffer
= bufp
->buffer
;
1084 print_partial_compiled_pattern (buffer
, buffer
+ bufp
->used
);
1085 printf ("%ld bytes used/%ld bytes allocated.\n",
1086 bufp
->used
, bufp
->allocated
);
1088 if (bufp
->fastmap_accurate
&& bufp
->fastmap
)
1090 printf ("fastmap: ");
1091 print_fastmap (bufp
->fastmap
);
1094 printf ("re_nsub: %zu\t", bufp
->re_nsub
);
1095 printf ("regs_alloc: %d\t", bufp
->regs_allocated
);
1096 printf ("can_be_null: %d\t", bufp
->can_be_null
);
1097 printf ("no_sub: %d\t", bufp
->no_sub
);
1098 printf ("not_bol: %d\t", bufp
->not_bol
);
1099 printf ("not_eol: %d\t", bufp
->not_eol
);
1101 printf ("syntax: %lx\n", bufp
->syntax
);
1104 /* Perhaps we should print the translate table? */
1109 print_double_string (re_char
*where
, re_char
*string1
, ssize_t size1
,
1110 re_char
*string2
, ssize_t size2
)
1118 if (FIRST_STRING_P (where
))
1120 for (this_char
= where
- string1
; this_char
< size1
; this_char
++)
1121 putchar (string1
[this_char
]);
1126 for (this_char
= where
- string2
; this_char
< size2
; this_char
++)
1127 putchar (string2
[this_char
]);
1131 #else /* not DEBUG */
1136 # define DEBUG_STATEMENT(e)
1137 # define DEBUG_PRINT(...)
1138 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1139 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1141 #endif /* not DEBUG */
1145 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1146 also be assigned to arbitrarily: each pattern buffer stores its own
1147 syntax, so it can be changed between regex compilations. */
1148 /* This has no initializer because initialized variables in Emacs
1149 become read-only after dumping. */
1150 reg_syntax_t re_syntax_options
;
1153 /* Specify the precise syntax of regexps for compilation. This provides
1154 for compatibility for various utilities which historically have
1155 different, incompatible syntaxes.
1157 The argument SYNTAX is a bit mask comprised of the various bits
1158 defined in regex.h. We return the old syntax. */
1161 re_set_syntax (reg_syntax_t syntax
)
1163 reg_syntax_t ret
= re_syntax_options
;
1165 re_syntax_options
= syntax
;
1168 WEAK_ALIAS (__re_set_syntax
, re_set_syntax
)
1172 /* This table gives an error message for each of the error codes listed
1173 in regex.h. Obviously the order here has to be same as there.
1174 POSIX doesn't require that we do anything for REG_NOERROR,
1175 but why not be nice? */
1177 static const char *re_error_msgid
[] =
1179 gettext_noop ("Success"), /* REG_NOERROR */
1180 gettext_noop ("No match"), /* REG_NOMATCH */
1181 gettext_noop ("Invalid regular expression"), /* REG_BADPAT */
1182 gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */
1183 gettext_noop ("Invalid character class name"), /* REG_ECTYPE */
1184 gettext_noop ("Trailing backslash"), /* REG_EESCAPE */
1185 gettext_noop ("Invalid back reference"), /* REG_ESUBREG */
1186 gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */
1187 gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */
1188 gettext_noop ("Unmatched \\{"), /* REG_EBRACE */
1189 gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */
1190 gettext_noop ("Invalid range end"), /* REG_ERANGE */
1191 gettext_noop ("Memory exhausted"), /* REG_ESPACE */
1192 gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */
1193 gettext_noop ("Premature end of regular expression"), /* REG_EEND */
1194 gettext_noop ("Regular expression too big"), /* REG_ESIZE */
1195 gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */
1196 gettext_noop ("Range striding over charsets") /* REG_ERANGEX */
1199 /* Avoiding alloca during matching, to placate r_alloc. */
1201 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1202 searching and matching functions should not call alloca. On some
1203 systems, alloca is implemented in terms of malloc, and if we're
1204 using the relocating allocator routines, then malloc could cause a
1205 relocation, which might (if the strings being searched are in the
1206 ralloc heap) shift the data out from underneath the regexp
1209 Here's another reason to avoid allocation: Emacs
1210 processes input from X in a signal handler; processing X input may
1211 call malloc; if input arrives while a matching routine is calling
1212 malloc, then we're scrod. But Emacs can't just block input while
1213 calling matching routines; then we don't notice interrupts when
1214 they come in. So, Emacs blocks input around all regexp calls
1215 except the matching calls, which it leaves unprotected, in the
1216 faith that they will not malloc. */
1218 /* Normally, this is fine. */
1219 #define MATCH_MAY_ALLOCATE
1221 /* The match routines may not allocate if (1) they would do it with malloc
1222 and (2) it's not safe for them to use malloc.
1223 Note that if REL_ALLOC is defined, matching would not use malloc for the
1224 failure stack, but we would still use it for the register vectors;
1225 so REL_ALLOC should not affect this. */
1226 #if defined REGEX_MALLOC && defined emacs
1227 # undef MATCH_MAY_ALLOCATE
1231 /* Failure stack declarations and macros; both re_compile_fastmap and
1232 re_match_2 use a failure stack. These have to be macros because of
1233 REGEX_ALLOCATE_STACK. */
1236 /* Approximate number of failure points for which to initially allocate space
1237 when matching. If this number is exceeded, we allocate more
1238 space, so it is not a hard limit. */
1239 #ifndef INIT_FAILURE_ALLOC
1240 # define INIT_FAILURE_ALLOC 20
1243 /* Roughly the maximum number of failure points on the stack. Would be
1244 exactly that if always used TYPICAL_FAILURE_SIZE items each time we failed.
1245 This is a variable only so users of regex can assign to it; we never
1246 change it ourselves. We always multiply it by TYPICAL_FAILURE_SIZE
1247 before using it, so it should probably be a byte-count instead. */
1248 # if defined MATCH_MAY_ALLOCATE
1249 /* Note that 4400 was enough to cause a crash on Alpha OSF/1,
1250 whose default stack limit is 2mb. In order for a larger
1251 value to work reliably, you have to try to make it accord
1252 with the process stack limit. */
1253 size_t re_max_failures
= 40000;
1255 size_t re_max_failures
= 4000;
1258 union fail_stack_elt
1261 /* This should be the biggest `int' that's no bigger than a pointer. */
1265 typedef union fail_stack_elt fail_stack_elt_t
;
1269 fail_stack_elt_t
*stack
;
1271 size_t avail
; /* Offset of next open position. */
1272 size_t frame
; /* Offset of the cur constructed frame. */
1275 #define FAIL_STACK_EMPTY() (fail_stack.frame == 0)
1278 /* Define macros to initialize and free the failure stack.
1279 Do `return -2' if the alloc fails. */
1281 #ifdef MATCH_MAY_ALLOCATE
1282 # define INIT_FAIL_STACK() \
1284 fail_stack.stack = \
1285 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * TYPICAL_FAILURE_SIZE \
1286 * sizeof (fail_stack_elt_t)); \
1288 if (fail_stack.stack == NULL) \
1291 fail_stack.size = INIT_FAILURE_ALLOC; \
1292 fail_stack.avail = 0; \
1293 fail_stack.frame = 0; \
1296 # define INIT_FAIL_STACK() \
1298 fail_stack.avail = 0; \
1299 fail_stack.frame = 0; \
1302 # define RETALLOC_IF(addr, n, t) \
1303 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
1307 /* Double the size of FAIL_STACK, up to a limit
1308 which allows approximately `re_max_failures' items.
1310 Return 1 if succeeds, and 0 if either ran out of memory
1311 allocating space for it or it was already too large.
1313 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1315 /* Factor to increase the failure stack size by
1316 when we increase it.
1317 This used to be 2, but 2 was too wasteful
1318 because the old discarded stacks added up to as much space
1319 were as ultimate, maximum-size stack. */
1320 #define FAIL_STACK_GROWTH_FACTOR 4
1322 #define GROW_FAIL_STACK(fail_stack) \
1323 (((fail_stack).size * sizeof (fail_stack_elt_t) \
1324 >= re_max_failures * TYPICAL_FAILURE_SIZE) \
1326 : ((fail_stack).stack \
1327 = REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1328 (fail_stack).size * sizeof (fail_stack_elt_t), \
1329 min (re_max_failures * TYPICAL_FAILURE_SIZE, \
1330 ((fail_stack).size * sizeof (fail_stack_elt_t) \
1331 * FAIL_STACK_GROWTH_FACTOR))), \
1333 (fail_stack).stack == NULL \
1335 : ((fail_stack).size \
1336 = (min (re_max_failures * TYPICAL_FAILURE_SIZE, \
1337 ((fail_stack).size * sizeof (fail_stack_elt_t) \
1338 * FAIL_STACK_GROWTH_FACTOR)) \
1339 / sizeof (fail_stack_elt_t)), \
1343 /* Push a pointer value onto the failure stack.
1344 Assumes the variable `fail_stack'. Probably should only
1345 be called from within `PUSH_FAILURE_POINT'. */
1346 #define PUSH_FAILURE_POINTER(item) \
1347 fail_stack.stack[fail_stack.avail++].pointer = (item)
1349 /* This pushes an integer-valued item onto the failure stack.
1350 Assumes the variable `fail_stack'. Probably should only
1351 be called from within `PUSH_FAILURE_POINT'. */
1352 #define PUSH_FAILURE_INT(item) \
1353 fail_stack.stack[fail_stack.avail++].integer = (item)
1355 /* These POP... operations complement the PUSH... operations.
1356 All assume that `fail_stack' is nonempty. */
1357 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1358 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1360 /* Individual items aside from the registers. */
1361 #define NUM_NONREG_ITEMS 3
1363 /* Used to examine the stack (to detect infinite loops). */
1364 #define FAILURE_PAT(h) fail_stack.stack[(h) - 1].pointer
1365 #define FAILURE_STR(h) (fail_stack.stack[(h) - 2].pointer)
1366 #define NEXT_FAILURE_HANDLE(h) fail_stack.stack[(h) - 3].integer
1367 #define TOP_FAILURE_HANDLE() fail_stack.frame
1370 #define ENSURE_FAIL_STACK(space) \
1371 while (REMAINING_AVAIL_SLOTS <= space) { \
1372 if (!GROW_FAIL_STACK (fail_stack)) \
1374 DEBUG_PRINT ("\n Doubled stack; size now: %zd\n", (fail_stack).size);\
1375 DEBUG_PRINT (" slots available: %zd\n", REMAINING_AVAIL_SLOTS);\
1378 /* Push register NUM onto the stack. */
1379 #define PUSH_FAILURE_REG(num) \
1381 char *destination; \
1383 ENSURE_FAIL_STACK(3); \
1384 DEBUG_PRINT (" Push reg %ld (spanning %p -> %p)\n", \
1385 n, regstart[n], regend[n]); \
1386 PUSH_FAILURE_POINTER (regstart[n]); \
1387 PUSH_FAILURE_POINTER (regend[n]); \
1388 PUSH_FAILURE_INT (n); \
1391 /* Change the counter's value to VAL, but make sure that it will
1392 be reset when backtracking. */
1393 #define PUSH_NUMBER(ptr,val) \
1395 char *destination; \
1397 ENSURE_FAIL_STACK(3); \
1398 EXTRACT_NUMBER (c, ptr); \
1399 DEBUG_PRINT (" Push number %p = %d -> %d\n", ptr, c, val); \
1400 PUSH_FAILURE_INT (c); \
1401 PUSH_FAILURE_POINTER (ptr); \
1402 PUSH_FAILURE_INT (-1); \
1403 STORE_NUMBER (ptr, val); \
1406 /* Pop a saved register off the stack. */
1407 #define POP_FAILURE_REG_OR_COUNT() \
1409 long pfreg = POP_FAILURE_INT (); \
1412 /* It's a counter. */ \
1413 /* Here, we discard `const', making re_match non-reentrant. */ \
1414 unsigned char *ptr = (unsigned char*) POP_FAILURE_POINTER (); \
1415 pfreg = POP_FAILURE_INT (); \
1416 STORE_NUMBER (ptr, pfreg); \
1417 DEBUG_PRINT (" Pop counter %p = %ld\n", ptr, pfreg); \
1421 regend[pfreg] = POP_FAILURE_POINTER (); \
1422 regstart[pfreg] = POP_FAILURE_POINTER (); \
1423 DEBUG_PRINT (" Pop reg %ld (spanning %p -> %p)\n", \
1424 pfreg, regstart[pfreg], regend[pfreg]); \
1428 /* Check that we are not stuck in an infinite loop. */
1429 #define CHECK_INFINITE_LOOP(pat_cur, string_place) \
1431 ssize_t failure = TOP_FAILURE_HANDLE (); \
1432 /* Check for infinite matching loops */ \
1433 while (failure > 0 \
1434 && (FAILURE_STR (failure) == string_place \
1435 || FAILURE_STR (failure) == NULL)) \
1437 assert (FAILURE_PAT (failure) >= bufp->buffer \
1438 && FAILURE_PAT (failure) <= bufp->buffer + bufp->used); \
1439 if (FAILURE_PAT (failure) == pat_cur) \
1444 DEBUG_PRINT (" Other pattern: %p\n", FAILURE_PAT (failure)); \
1445 failure = NEXT_FAILURE_HANDLE(failure); \
1447 DEBUG_PRINT (" Other string: %p\n", FAILURE_STR (failure)); \
1450 /* Push the information about the state we will need
1451 if we ever fail back to it.
1453 Requires variables fail_stack, regstart, regend and
1454 num_regs be declared. GROW_FAIL_STACK requires `destination' be
1457 Does `return FAILURE_CODE' if runs out of memory. */
1459 #define PUSH_FAILURE_POINT(pattern, string_place) \
1461 char *destination; \
1462 /* Must be int, so when we don't save any registers, the arithmetic \
1463 of 0 + -1 isn't done as unsigned. */ \
1465 DEBUG_STATEMENT (nfailure_points_pushed++); \
1466 DEBUG_PRINT ("\nPUSH_FAILURE_POINT:\n"); \
1467 DEBUG_PRINT (" Before push, next avail: %zd\n", (fail_stack).avail); \
1468 DEBUG_PRINT (" size: %zd\n", (fail_stack).size);\
1470 ENSURE_FAIL_STACK (NUM_NONREG_ITEMS); \
1472 DEBUG_PRINT ("\n"); \
1474 DEBUG_PRINT (" Push frame index: %zd\n", fail_stack.frame); \
1475 PUSH_FAILURE_INT (fail_stack.frame); \
1477 DEBUG_PRINT (" Push string %p: \"", string_place); \
1478 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, size2);\
1479 DEBUG_PRINT ("\"\n"); \
1480 PUSH_FAILURE_POINTER (string_place); \
1482 DEBUG_PRINT (" Push pattern %p: ", pattern); \
1483 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern, pend); \
1484 PUSH_FAILURE_POINTER (pattern); \
1486 /* Close the frame by moving the frame pointer past it. */ \
1487 fail_stack.frame = fail_stack.avail; \
1490 /* Estimate the size of data pushed by a typical failure stack entry.
1491 An estimate is all we need, because all we use this for
1492 is to choose a limit for how big to make the failure stack. */
1493 /* BEWARE, the value `20' is hard-coded in emacs.c:main(). */
1494 #define TYPICAL_FAILURE_SIZE 20
1496 /* How many items can still be added to the stack without overflowing it. */
1497 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1500 /* Pops what PUSH_FAIL_STACK pushes.
1502 We restore into the parameters, all of which should be lvalues:
1503 STR -- the saved data position.
1504 PAT -- the saved pattern position.
1505 REGSTART, REGEND -- arrays of string positions.
1507 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1508 `pend', `string1', `size1', `string2', and `size2'. */
1510 #define POP_FAILURE_POINT(str, pat) \
1512 assert (!FAIL_STACK_EMPTY ()); \
1514 /* Remove failure points and point to how many regs pushed. */ \
1515 DEBUG_PRINT ("POP_FAILURE_POINT:\n"); \
1516 DEBUG_PRINT (" Before pop, next avail: %zd\n", fail_stack.avail); \
1517 DEBUG_PRINT (" size: %zd\n", fail_stack.size); \
1519 /* Pop the saved registers. */ \
1520 while (fail_stack.frame < fail_stack.avail) \
1521 POP_FAILURE_REG_OR_COUNT (); \
1523 pat = POP_FAILURE_POINTER (); \
1524 DEBUG_PRINT (" Popping pattern %p: ", pat); \
1525 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1527 /* If the saved string location is NULL, it came from an \
1528 on_failure_keep_string_jump opcode, and we want to throw away the \
1529 saved NULL, thus retaining our current position in the string. */ \
1530 str = POP_FAILURE_POINTER (); \
1531 DEBUG_PRINT (" Popping string %p: \"", str); \
1532 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1533 DEBUG_PRINT ("\"\n"); \
1535 fail_stack.frame = POP_FAILURE_INT (); \
1536 DEBUG_PRINT (" Popping frame index: %zd\n", fail_stack.frame); \
1538 assert (fail_stack.avail >= 0); \
1539 assert (fail_stack.frame <= fail_stack.avail); \
1541 DEBUG_STATEMENT (nfailure_points_popped++); \
1542 } while (0) /* POP_FAILURE_POINT */
1546 /* Registers are set to a sentinel when they haven't yet matched. */
1547 #define REG_UNSET(e) ((e) == NULL)
1549 /* Subroutine declarations and macros for regex_compile. */
1551 static reg_errcode_t
regex_compile (re_char
*pattern
, size_t size
,
1553 bool posix_backtracking
,
1554 const char *whitespace_regexp
,
1556 reg_syntax_t syntax
,
1558 struct re_pattern_buffer
*bufp
);
1559 static void store_op1 (re_opcode_t op
, unsigned char *loc
, int arg
);
1560 static void store_op2 (re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
);
1561 static void insert_op1 (re_opcode_t op
, unsigned char *loc
,
1562 int arg
, unsigned char *end
);
1563 static void insert_op2 (re_opcode_t op
, unsigned char *loc
,
1564 int arg1
, int arg2
, unsigned char *end
);
1565 static boolean
at_begline_loc_p (re_char
*pattern
, re_char
*p
,
1566 reg_syntax_t syntax
);
1567 static boolean
at_endline_loc_p (re_char
*p
, re_char
*pend
,
1568 reg_syntax_t syntax
);
1569 static re_char
*skip_one_char (re_char
*p
);
1570 static int analyze_first (re_char
*p
, re_char
*pend
,
1571 char *fastmap
, const int multibyte
);
1573 /* Fetch the next character in the uncompiled pattern, with no
1575 #define PATFETCH(c) \
1578 if (p == pend) return REG_EEND; \
1579 c = RE_STRING_CHAR_AND_LENGTH (p, len, multibyte); \
1584 /* If `translate' is non-null, return translate[D], else just D. We
1585 cast the subscript to translate because some data is declared as
1586 `char *', to avoid warnings when a string constant is passed. But
1587 when we use a character as a subscript we must make it unsigned. */
1589 # define TRANSLATE(d) \
1590 (RE_TRANSLATE_P (translate) ? RE_TRANSLATE (translate, (d)) : (d))
1594 /* Macros for outputting the compiled pattern into `buffer'. */
1596 /* If the buffer isn't allocated when it comes in, use this. */
1597 #define INIT_BUF_SIZE 32
1599 /* Make sure we have at least N more bytes of space in buffer. */
1600 #define GET_BUFFER_SPACE(n) \
1601 while ((size_t) (b - bufp->buffer + (n)) > bufp->allocated) \
1604 /* Make sure we have one more byte of buffer space and then add C to it. */
1605 #define BUF_PUSH(c) \
1607 GET_BUFFER_SPACE (1); \
1608 *b++ = (unsigned char) (c); \
1612 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
1613 #define BUF_PUSH_2(c1, c2) \
1615 GET_BUFFER_SPACE (2); \
1616 *b++ = (unsigned char) (c1); \
1617 *b++ = (unsigned char) (c2); \
1621 /* Store a jump with opcode OP at LOC to location TO. We store a
1622 relative address offset by the three bytes the jump itself occupies. */
1623 #define STORE_JUMP(op, loc, to) \
1624 store_op1 (op, loc, (to) - (loc) - 3)
1626 /* Likewise, for a two-argument jump. */
1627 #define STORE_JUMP2(op, loc, to, arg) \
1628 store_op2 (op, loc, (to) - (loc) - 3, arg)
1630 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
1631 #define INSERT_JUMP(op, loc, to) \
1632 insert_op1 (op, loc, (to) - (loc) - 3, b)
1634 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
1635 #define INSERT_JUMP2(op, loc, to, arg) \
1636 insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
1639 /* This is not an arbitrary limit: the arguments which represent offsets
1640 into the pattern are two bytes long. So if 2^15 bytes turns out to
1641 be too small, many things would have to change. */
1642 # define MAX_BUF_SIZE (1L << 15)
1644 /* Extend the buffer by twice its current size via realloc and
1645 reset the pointers that pointed into the old block to point to the
1646 correct places in the new one. If extending the buffer results in it
1647 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
1648 #define EXTEND_BUFFER() \
1650 unsigned char *old_buffer = bufp->buffer; \
1651 if (bufp->allocated == MAX_BUF_SIZE) \
1653 bufp->allocated <<= 1; \
1654 if (bufp->allocated > MAX_BUF_SIZE) \
1655 bufp->allocated = MAX_BUF_SIZE; \
1656 ptrdiff_t b_off = b - old_buffer; \
1657 ptrdiff_t begalt_off = begalt - old_buffer; \
1658 bool fixup_alt_jump_set = !!fixup_alt_jump; \
1659 bool laststart_set = !!laststart; \
1660 bool pending_exact_set = !!pending_exact; \
1661 ptrdiff_t fixup_alt_jump_off, laststart_off, pending_exact_off; \
1662 if (fixup_alt_jump_set) fixup_alt_jump_off = fixup_alt_jump - old_buffer; \
1663 if (laststart_set) laststart_off = laststart - old_buffer; \
1664 if (pending_exact_set) pending_exact_off = pending_exact - old_buffer; \
1665 RETALLOC (bufp->buffer, bufp->allocated, unsigned char); \
1666 if (bufp->buffer == NULL) \
1667 return REG_ESPACE; \
1668 unsigned char *new_buffer = bufp->buffer; \
1669 b = new_buffer + b_off; \
1670 begalt = new_buffer + begalt_off; \
1671 if (fixup_alt_jump_set) fixup_alt_jump = new_buffer + fixup_alt_jump_off; \
1672 if (laststart_set) laststart = new_buffer + laststart_off; \
1673 if (pending_exact_set) pending_exact = new_buffer + pending_exact_off; \
1677 /* Since we have one byte reserved for the register number argument to
1678 {start,stop}_memory, the maximum number of groups we can report
1679 things about is what fits in that byte. */
1680 #define MAX_REGNUM 255
1682 /* But patterns can have more than `MAX_REGNUM' registers. We just
1683 ignore the excess. */
1684 typedef int regnum_t
;
1687 /* Macros for the compile stack. */
1689 /* Since offsets can go either forwards or backwards, this type needs to
1690 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
1691 /* int may be not enough when sizeof(int) == 2. */
1692 typedef long pattern_offset_t
;
1696 pattern_offset_t begalt_offset
;
1697 pattern_offset_t fixup_alt_jump
;
1698 pattern_offset_t laststart_offset
;
1700 } compile_stack_elt_t
;
1705 compile_stack_elt_t
*stack
;
1707 size_t avail
; /* Offset of next open position. */
1708 } compile_stack_type
;
1711 #define INIT_COMPILE_STACK_SIZE 32
1713 #define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
1714 #define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
1716 /* The next available element. */
1717 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1719 /* Explicit quit checking is needed for Emacs, which uses polling to
1720 process input events. */
1722 # define IMMEDIATE_QUIT_CHECK \
1724 if (immediate_quit) QUIT; \
1727 # define IMMEDIATE_QUIT_CHECK ((void)0)
1730 /* Structure to manage work area for range table. */
1731 struct range_table_work_area
1733 int *table
; /* actual work area. */
1734 int allocated
; /* allocated size for work area in bytes. */
1735 int used
; /* actually used size in words. */
1736 int bits
; /* flag to record character classes */
1741 /* Make sure that WORK_AREA can hold more N multibyte characters.
1742 This is used only in set_image_of_range and set_image_of_range_1.
1743 It expects WORK_AREA to be a pointer.
1744 If it can't get the space, it returns from the surrounding function. */
1746 #define EXTEND_RANGE_TABLE(work_area, n) \
1748 if (((work_area).used + (n)) * sizeof (int) > (work_area).allocated) \
1750 extend_range_table_work_area (&work_area); \
1751 if ((work_area).table == 0) \
1752 return (REG_ESPACE); \
1756 #define SET_RANGE_TABLE_WORK_AREA_BIT(work_area, bit) \
1757 (work_area).bits |= (bit)
1759 /* Set a range (RANGE_START, RANGE_END) to WORK_AREA. */
1760 #define SET_RANGE_TABLE_WORK_AREA(work_area, range_start, range_end) \
1762 EXTEND_RANGE_TABLE ((work_area), 2); \
1763 (work_area).table[(work_area).used++] = (range_start); \
1764 (work_area).table[(work_area).used++] = (range_end); \
1769 /* Free allocated memory for WORK_AREA. */
1770 #define FREE_RANGE_TABLE_WORK_AREA(work_area) \
1772 if ((work_area).table) \
1773 free ((work_area).table); \
1776 #define CLEAR_RANGE_TABLE_WORK_USED(work_area) ((work_area).used = 0, (work_area).bits = 0)
1777 #define RANGE_TABLE_WORK_USED(work_area) ((work_area).used)
1778 #define RANGE_TABLE_WORK_BITS(work_area) ((work_area).bits)
1779 #define RANGE_TABLE_WORK_ELT(work_area, i) ((work_area).table[i])
1781 /* Bits used to implement the multibyte-part of the various character classes
1782 such as [:alnum:] in a charset's range table. The code currently assumes
1783 that only the low 16 bits are used. */
1784 #define BIT_WORD 0x1
1785 #define BIT_LOWER 0x2
1786 #define BIT_PUNCT 0x4
1787 #define BIT_SPACE 0x8
1788 #define BIT_UPPER 0x10
1789 #define BIT_MULTIBYTE 0x20
1790 #define BIT_ALPHA 0x40
1791 #define BIT_ALNUM 0x80
1792 #define BIT_GRAPH 0x100
1793 #define BIT_PRINT 0x200
1794 #define BIT_BLANK 0x400
1797 /* Set the bit for character C in a list. */
1798 #define SET_LIST_BIT(c) (b[((c)) / BYTEWIDTH] |= 1 << ((c) % BYTEWIDTH))
1803 /* Store characters in the range FROM to TO in the bitmap at B (for
1804 ASCII and unibyte characters) and WORK_AREA (for multibyte
1805 characters) while translating them and paying attention to the
1806 continuity of translated characters.
1808 Implementation note: It is better to implement these fairly big
1809 macros by a function, but it's not that easy because macros called
1810 in this macro assume various local variables already declared. */
1812 /* Both FROM and TO are ASCII characters. */
1814 #define SETUP_ASCII_RANGE(work_area, FROM, TO) \
1818 for (C0 = (FROM); C0 <= (TO); C0++) \
1820 C1 = TRANSLATE (C0); \
1821 if (! ASCII_CHAR_P (C1)) \
1823 SET_RANGE_TABLE_WORK_AREA ((work_area), C1, C1); \
1824 if ((C1 = RE_CHAR_TO_UNIBYTE (C1)) < 0) \
1827 SET_LIST_BIT (C1); \
1832 /* Both FROM and TO are unibyte characters (0x80..0xFF). */
1834 #define SETUP_UNIBYTE_RANGE(work_area, FROM, TO) \
1836 int C0, C1, C2, I; \
1837 int USED = RANGE_TABLE_WORK_USED (work_area); \
1839 for (C0 = (FROM); C0 <= (TO); C0++) \
1841 C1 = RE_CHAR_TO_MULTIBYTE (C0); \
1842 if (CHAR_BYTE8_P (C1)) \
1843 SET_LIST_BIT (C0); \
1846 C2 = TRANSLATE (C1); \
1848 || (C1 = RE_CHAR_TO_UNIBYTE (C2)) < 0) \
1850 SET_LIST_BIT (C1); \
1851 for (I = RANGE_TABLE_WORK_USED (work_area) - 2; I >= USED; I -= 2) \
1853 int from = RANGE_TABLE_WORK_ELT (work_area, I); \
1854 int to = RANGE_TABLE_WORK_ELT (work_area, I + 1); \
1856 if (C2 >= from - 1 && C2 <= to + 1) \
1858 if (C2 == from - 1) \
1859 RANGE_TABLE_WORK_ELT (work_area, I)--; \
1860 else if (C2 == to + 1) \
1861 RANGE_TABLE_WORK_ELT (work_area, I + 1)++; \
1866 SET_RANGE_TABLE_WORK_AREA ((work_area), C2, C2); \
1872 /* Both FROM and TO are multibyte characters. */
1874 #define SETUP_MULTIBYTE_RANGE(work_area, FROM, TO) \
1876 int C0, C1, C2, I, USED = RANGE_TABLE_WORK_USED (work_area); \
1878 SET_RANGE_TABLE_WORK_AREA ((work_area), (FROM), (TO)); \
1879 for (C0 = (FROM); C0 <= (TO); C0++) \
1881 C1 = TRANSLATE (C0); \
1882 if ((C2 = RE_CHAR_TO_UNIBYTE (C1)) >= 0 \
1883 || (C1 != C0 && (C2 = RE_CHAR_TO_UNIBYTE (C0)) >= 0)) \
1884 SET_LIST_BIT (C2); \
1885 if (C1 >= (FROM) && C1 <= (TO)) \
1887 for (I = RANGE_TABLE_WORK_USED (work_area) - 2; I >= USED; I -= 2) \
1889 int from = RANGE_TABLE_WORK_ELT (work_area, I); \
1890 int to = RANGE_TABLE_WORK_ELT (work_area, I + 1); \
1892 if (C1 >= from - 1 && C1 <= to + 1) \
1894 if (C1 == from - 1) \
1895 RANGE_TABLE_WORK_ELT (work_area, I)--; \
1896 else if (C1 == to + 1) \
1897 RANGE_TABLE_WORK_ELT (work_area, I + 1)++; \
1902 SET_RANGE_TABLE_WORK_AREA ((work_area), C1, C1); \
1908 /* Get the next unsigned number in the uncompiled pattern. */
1909 #define GET_INTERVAL_COUNT(num) \
1912 FREE_STACK_RETURN (REG_EBRACE); \
1916 while ('0' <= c && c <= '9') \
1920 if (RE_DUP_MAX / 10 - (RE_DUP_MAX % 10 < c - '0') < num) \
1921 FREE_STACK_RETURN (REG_BADBR); \
1922 num = num * 10 + c - '0'; \
1924 FREE_STACK_RETURN (REG_EBRACE); \
1930 #if ! WIDE_CHAR_SUPPORT
1932 /* Parse a character class, i.e. string such as "[:name:]". *strp
1933 points to the string to be parsed and limit is length, in bytes, of
1936 If *strp point to a string that begins with "[:name:]", where name is
1937 a non-empty sequence of lower case letters, *strp will be advanced past the
1938 closing square bracket and RECC_* constant which maps to the name will be
1939 returned. If name is not a valid character class name zero, or RECC_ERROR,
1942 Otherwise, if *strp doesn’t begin with "[:name:]", -1 is returned.
1944 The function can be used on ASCII and multibyte (UTF-8-encoded) strings.
1947 re_wctype_parse (const unsigned char **strp
, unsigned limit
)
1949 const char *beg
= (const char *)*strp
, *it
;
1951 if (limit
< 4 || beg
[0] != '[' || beg
[1] != ':')
1954 beg
+= 2; /* skip opening ‘[:’ */
1955 limit
-= 3; /* opening ‘[:’ and half of closing ‘:]’; --limit handles rest */
1956 for (it
= beg
; it
[0] != ':' || it
[1] != ']'; ++it
)
1960 *strp
= (const unsigned char *)(it
+ 2);
1962 /* Sort tests in the length=five case by frequency the classes to minimize
1963 number of times we fail the comparison. The frequencies of character class
1964 names used in Emacs sources as of 2016-07-27:
1966 $ find \( -name \*.c -o -name \*.el \) -exec grep -h '\[:[a-z]*:]' {} + |
1967 sed 's/]/]\n/g' |grep -o '\[:[a-z]*:]' |sort |uniq -c |sort -nr
1985 If you update this list, consider also updating chain of or’ed conditions
1986 in execute_charset function.
1991 if (!memcmp (beg
, "word", 4)) return RECC_WORD
;
1994 if (!memcmp (beg
, "alnum", 5)) return RECC_ALNUM
;
1995 if (!memcmp (beg
, "alpha", 5)) return RECC_ALPHA
;
1996 if (!memcmp (beg
, "space", 5)) return RECC_SPACE
;
1997 if (!memcmp (beg
, "digit", 5)) return RECC_DIGIT
;
1998 if (!memcmp (beg
, "blank", 5)) return RECC_BLANK
;
1999 if (!memcmp (beg
, "upper", 5)) return RECC_UPPER
;
2000 if (!memcmp (beg
, "lower", 5)) return RECC_LOWER
;
2001 if (!memcmp (beg
, "punct", 5)) return RECC_PUNCT
;
2002 if (!memcmp (beg
, "ascii", 5)) return RECC_ASCII
;
2003 if (!memcmp (beg
, "graph", 5)) return RECC_GRAPH
;
2004 if (!memcmp (beg
, "print", 5)) return RECC_PRINT
;
2005 if (!memcmp (beg
, "cntrl", 5)) return RECC_CNTRL
;
2008 if (!memcmp (beg
, "xdigit", 6)) return RECC_XDIGIT
;
2011 if (!memcmp (beg
, "unibyte", 7)) return RECC_UNIBYTE
;
2014 if (!memcmp (beg
, "nonascii", 8)) return RECC_NONASCII
;
2017 if (!memcmp (beg
, "multibyte", 9)) return RECC_MULTIBYTE
;
2024 /* True if CH is in the char class CC. */
2026 re_iswctype (int ch
, re_wctype_t cc
)
2030 case RECC_ALNUM
: return ISALNUM (ch
) != 0;
2031 case RECC_ALPHA
: return ISALPHA (ch
) != 0;
2032 case RECC_BLANK
: return ISBLANK (ch
) != 0;
2033 case RECC_CNTRL
: return ISCNTRL (ch
) != 0;
2034 case RECC_DIGIT
: return ISDIGIT (ch
) != 0;
2035 case RECC_GRAPH
: return ISGRAPH (ch
) != 0;
2036 case RECC_LOWER
: return ISLOWER (ch
) != 0;
2037 case RECC_PRINT
: return ISPRINT (ch
) != 0;
2038 case RECC_PUNCT
: return ISPUNCT (ch
) != 0;
2039 case RECC_SPACE
: return ISSPACE (ch
) != 0;
2040 case RECC_UPPER
: return ISUPPER (ch
) != 0;
2041 case RECC_XDIGIT
: return ISXDIGIT (ch
) != 0;
2042 case RECC_ASCII
: return IS_REAL_ASCII (ch
) != 0;
2043 case RECC_NONASCII
: return !IS_REAL_ASCII (ch
);
2044 case RECC_UNIBYTE
: return ISUNIBYTE (ch
) != 0;
2045 case RECC_MULTIBYTE
: return !ISUNIBYTE (ch
);
2046 case RECC_WORD
: return ISWORD (ch
) != 0;
2047 case RECC_ERROR
: return false;
2053 /* Return a bit-pattern to use in the range-table bits to match multibyte
2054 chars of class CC. */
2056 re_wctype_to_bit (re_wctype_t cc
)
2061 case RECC_MULTIBYTE
: return BIT_MULTIBYTE
;
2062 case RECC_ALPHA
: return BIT_ALPHA
;
2063 case RECC_ALNUM
: return BIT_ALNUM
;
2064 case RECC_WORD
: return BIT_WORD
;
2065 case RECC_LOWER
: return BIT_LOWER
;
2066 case RECC_UPPER
: return BIT_UPPER
;
2067 case RECC_PUNCT
: return BIT_PUNCT
;
2068 case RECC_SPACE
: return BIT_SPACE
;
2069 case RECC_GRAPH
: return BIT_GRAPH
;
2070 case RECC_PRINT
: return BIT_PRINT
;
2071 case RECC_BLANK
: return BIT_BLANK
;
2072 case RECC_ASCII
: case RECC_DIGIT
: case RECC_XDIGIT
: case RECC_CNTRL
:
2073 case RECC_UNIBYTE
: case RECC_ERROR
: return 0;
2080 /* Filling in the work area of a range. */
2082 /* Actually extend the space in WORK_AREA. */
2085 extend_range_table_work_area (struct range_table_work_area
*work_area
)
2087 work_area
->allocated
+= 16 * sizeof (int);
2088 work_area
->table
= realloc (work_area
->table
, work_area
->allocated
);
2094 /* Carefully find the ranges of codes that are equivalent
2095 under case conversion to the range start..end when passed through
2096 TRANSLATE. Handle the case where non-letters can come in between
2097 two upper-case letters (which happens in Latin-1).
2098 Also handle the case of groups of more than 2 case-equivalent chars.
2100 The basic method is to look at consecutive characters and see
2101 if they can form a run that can be handled as one.
2103 Returns -1 if successful, REG_ESPACE if ran out of space. */
2106 set_image_of_range_1 (struct range_table_work_area
*work_area
,
2107 re_wchar_t start
, re_wchar_t end
,
2108 RE_TRANSLATE_TYPE translate
)
2110 /* `one_case' indicates a character, or a run of characters,
2111 each of which is an isolate (no case-equivalents).
2112 This includes all ASCII non-letters.
2114 `two_case' indicates a character, or a run of characters,
2115 each of which has two case-equivalent forms.
2116 This includes all ASCII letters.
2118 `strange' indicates a character that has more than one
2121 enum case_type
{one_case
, two_case
, strange
};
2123 /* Describe the run that is in progress,
2124 which the next character can try to extend.
2125 If run_type is strange, that means there really is no run.
2126 If run_type is one_case, then run_start...run_end is the run.
2127 If run_type is two_case, then the run is run_start...run_end,
2128 and the case-equivalents end at run_eqv_end. */
2130 enum case_type run_type
= strange
;
2131 int run_start
, run_end
, run_eqv_end
;
2133 Lisp_Object eqv_table
;
2135 if (!RE_TRANSLATE_P (translate
))
2137 EXTEND_RANGE_TABLE (work_area
, 2);
2138 work_area
->table
[work_area
->used
++] = (start
);
2139 work_area
->table
[work_area
->used
++] = (end
);
2143 eqv_table
= XCHAR_TABLE (translate
)->extras
[2];
2145 for (; start
<= end
; start
++)
2147 enum case_type this_type
;
2148 int eqv
= RE_TRANSLATE (eqv_table
, start
);
2149 int minchar
, maxchar
;
2151 /* Classify this character */
2153 this_type
= one_case
;
2154 else if (RE_TRANSLATE (eqv_table
, eqv
) == start
)
2155 this_type
= two_case
;
2157 this_type
= strange
;
2160 minchar
= start
, maxchar
= eqv
;
2162 minchar
= eqv
, maxchar
= start
;
2164 /* Can this character extend the run in progress? */
2165 if (this_type
== strange
|| this_type
!= run_type
2166 || !(minchar
== run_end
+ 1
2167 && (run_type
== two_case
2168 ? maxchar
== run_eqv_end
+ 1 : 1)))
2171 Record each of its equivalent ranges. */
2172 if (run_type
== one_case
)
2174 EXTEND_RANGE_TABLE (work_area
, 2);
2175 work_area
->table
[work_area
->used
++] = run_start
;
2176 work_area
->table
[work_area
->used
++] = run_end
;
2178 else if (run_type
== two_case
)
2180 EXTEND_RANGE_TABLE (work_area
, 4);
2181 work_area
->table
[work_area
->used
++] = run_start
;
2182 work_area
->table
[work_area
->used
++] = run_end
;
2183 work_area
->table
[work_area
->used
++]
2184 = RE_TRANSLATE (eqv_table
, run_start
);
2185 work_area
->table
[work_area
->used
++]
2186 = RE_TRANSLATE (eqv_table
, run_end
);
2191 if (this_type
== strange
)
2193 /* For a strange character, add each of its equivalents, one
2194 by one. Don't start a range. */
2197 EXTEND_RANGE_TABLE (work_area
, 2);
2198 work_area
->table
[work_area
->used
++] = eqv
;
2199 work_area
->table
[work_area
->used
++] = eqv
;
2200 eqv
= RE_TRANSLATE (eqv_table
, eqv
);
2202 while (eqv
!= start
);
2205 /* Add this char to the run, or start a new run. */
2206 else if (run_type
== strange
)
2208 /* Initialize a new range. */
2209 run_type
= this_type
;
2212 run_eqv_end
= RE_TRANSLATE (eqv_table
, run_end
);
2216 /* Extend a running range. */
2218 run_eqv_end
= RE_TRANSLATE (eqv_table
, run_end
);
2222 /* If a run is still in progress at the end, finish it now
2223 by recording its equivalent ranges. */
2224 if (run_type
== one_case
)
2226 EXTEND_RANGE_TABLE (work_area
, 2);
2227 work_area
->table
[work_area
->used
++] = run_start
;
2228 work_area
->table
[work_area
->used
++] = run_end
;
2230 else if (run_type
== two_case
)
2232 EXTEND_RANGE_TABLE (work_area
, 4);
2233 work_area
->table
[work_area
->used
++] = run_start
;
2234 work_area
->table
[work_area
->used
++] = run_end
;
2235 work_area
->table
[work_area
->used
++]
2236 = RE_TRANSLATE (eqv_table
, run_start
);
2237 work_area
->table
[work_area
->used
++]
2238 = RE_TRANSLATE (eqv_table
, run_end
);
2246 /* Record the image of the range start..end when passed through
2247 TRANSLATE. This is not necessarily TRANSLATE(start)..TRANSLATE(end)
2248 and is not even necessarily contiguous.
2249 Normally we approximate it with the smallest contiguous range that contains
2250 all the chars we need. However, for Latin-1 we go to extra effort
2253 This function is not called for ASCII ranges.
2255 Returns -1 if successful, REG_ESPACE if ran out of space. */
2258 set_image_of_range (struct range_table_work_area
*work_area
,
2259 re_wchar_t start
, re_wchar_t end
,
2260 RE_TRANSLATE_TYPE translate
)
2262 re_wchar_t cmin
, cmax
;
2265 /* For Latin-1 ranges, use set_image_of_range_1
2266 to get proper handling of ranges that include letters and nonletters.
2267 For a range that includes the whole of Latin-1, this is not necessary.
2268 For other character sets, we don't bother to get this right. */
2269 if (RE_TRANSLATE_P (translate
) && start
< 04400
2270 && !(start
< 04200 && end
>= 04377))
2277 tem
= set_image_of_range_1 (work_area
, start
, newend
, translate
);
2287 EXTEND_RANGE_TABLE (work_area
, 2);
2288 work_area
->table
[work_area
->used
++] = (start
);
2289 work_area
->table
[work_area
->used
++] = (end
);
2291 cmin
= -1, cmax
= -1;
2293 if (RE_TRANSLATE_P (translate
))
2297 for (ch
= start
; ch
<= end
; ch
++)
2299 re_wchar_t c
= TRANSLATE (ch
);
2300 if (! (start
<= c
&& c
<= end
))
2306 cmin
= min (cmin
, c
);
2307 cmax
= max (cmax
, c
);
2314 EXTEND_RANGE_TABLE (work_area
, 2);
2315 work_area
->table
[work_area
->used
++] = (cmin
);
2316 work_area
->table
[work_area
->used
++] = (cmax
);
2324 #ifndef MATCH_MAY_ALLOCATE
2326 /* If we cannot allocate large objects within re_match_2_internal,
2327 we make the fail stack and register vectors global.
2328 The fail stack, we grow to the maximum size when a regexp
2330 The register vectors, we adjust in size each time we
2331 compile a regexp, according to the number of registers it needs. */
2333 static fail_stack_type fail_stack
;
2335 /* Size with which the following vectors are currently allocated.
2336 That is so we can make them bigger as needed,
2337 but never make them smaller. */
2338 static int regs_allocated_size
;
2340 static re_char
** regstart
, ** regend
;
2341 static re_char
**best_regstart
, **best_regend
;
2343 /* Make the register vectors big enough for NUM_REGS registers,
2344 but don't make them smaller. */
2347 regex_grow_registers (int num_regs
)
2349 if (num_regs
> regs_allocated_size
)
2351 RETALLOC_IF (regstart
, num_regs
, re_char
*);
2352 RETALLOC_IF (regend
, num_regs
, re_char
*);
2353 RETALLOC_IF (best_regstart
, num_regs
, re_char
*);
2354 RETALLOC_IF (best_regend
, num_regs
, re_char
*);
2356 regs_allocated_size
= num_regs
;
2360 #endif /* not MATCH_MAY_ALLOCATE */
2362 static boolean
group_in_compile_stack (compile_stack_type compile_stack
,
2365 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2366 Returns one of error codes defined in `regex.h', or zero for success.
2368 If WHITESPACE_REGEXP is given (only #ifdef emacs), it is used instead of
2369 a space character in PATTERN.
2371 Assumes the `allocated' (and perhaps `buffer') and `translate'
2372 fields are set in BUFP on entry.
2374 If it succeeds, results are put in BUFP (if it returns an error, the
2375 contents of BUFP are undefined):
2376 `buffer' is the compiled pattern;
2377 `syntax' is set to SYNTAX;
2378 `used' is set to the length of the compiled pattern;
2379 `fastmap_accurate' is zero;
2380 `re_nsub' is the number of subexpressions in PATTERN;
2381 `not_bol' and `not_eol' are zero;
2383 The `fastmap' field is neither examined nor set. */
2385 /* Insert the `jump' from the end of last alternative to "here".
2386 The space for the jump has already been allocated. */
2387 #define FIXUP_ALT_JUMP() \
2389 if (fixup_alt_jump) \
2390 STORE_JUMP (jump, fixup_alt_jump, b); \
2394 /* Return, freeing storage we allocated. */
2395 #define FREE_STACK_RETURN(value) \
2397 FREE_RANGE_TABLE_WORK_AREA (range_table_work); \
2398 free (compile_stack.stack); \
2402 static reg_errcode_t
2403 regex_compile (const_re_char
*pattern
, size_t size
,
2405 # define syntax RE_SYNTAX_EMACS
2406 bool posix_backtracking
,
2407 const char *whitespace_regexp
,
2409 reg_syntax_t syntax
,
2410 # define posix_backtracking (!(syntax & RE_NO_POSIX_BACKTRACKING))
2412 struct re_pattern_buffer
*bufp
)
2414 /* We fetch characters from PATTERN here. */
2415 register re_wchar_t c
, c1
;
2417 /* Points to the end of the buffer, where we should append. */
2418 register unsigned char *b
;
2420 /* Keeps track of unclosed groups. */
2421 compile_stack_type compile_stack
;
2423 /* Points to the current (ending) position in the pattern. */
2425 /* `const' makes AIX compiler fail. */
2426 unsigned char *p
= pattern
;
2428 re_char
*p
= pattern
;
2430 re_char
*pend
= pattern
+ size
;
2432 /* How to translate the characters in the pattern. */
2433 RE_TRANSLATE_TYPE translate
= bufp
->translate
;
2435 /* Address of the count-byte of the most recently inserted `exactn'
2436 command. This makes it possible to tell if a new exact-match
2437 character can be added to that command or if the character requires
2438 a new `exactn' command. */
2439 unsigned char *pending_exact
= 0;
2441 /* Address of start of the most recently finished expression.
2442 This tells, e.g., postfix * where to find the start of its
2443 operand. Reset at the beginning of groups and alternatives. */
2444 unsigned char *laststart
= 0;
2446 /* Address of beginning of regexp, or inside of last group. */
2447 unsigned char *begalt
;
2449 /* Place in the uncompiled pattern (i.e., the {) to
2450 which to go back if the interval is invalid. */
2451 re_char
*beg_interval
;
2453 /* Address of the place where a forward jump should go to the end of
2454 the containing expression. Each alternative of an `or' -- except the
2455 last -- ends with a forward jump of this sort. */
2456 unsigned char *fixup_alt_jump
= 0;
2458 /* Work area for range table of charset. */
2459 struct range_table_work_area range_table_work
;
2461 /* If the object matched can contain multibyte characters. */
2462 const boolean multibyte
= RE_MULTIBYTE_P (bufp
);
2465 /* Nonzero if we have pushed down into a subpattern. */
2466 int in_subpattern
= 0;
2468 /* These hold the values of p, pattern, and pend from the main
2469 pattern when we have pushed into a subpattern. */
2471 re_char
*main_pattern
;
2477 DEBUG_PRINT ("\nCompiling pattern: ");
2480 unsigned debug_count
;
2482 for (debug_count
= 0; debug_count
< size
; debug_count
++)
2483 putchar (pattern
[debug_count
]);
2488 /* Initialize the compile stack. */
2489 compile_stack
.stack
= TALLOC (INIT_COMPILE_STACK_SIZE
, compile_stack_elt_t
);
2490 if (compile_stack
.stack
== NULL
)
2493 compile_stack
.size
= INIT_COMPILE_STACK_SIZE
;
2494 compile_stack
.avail
= 0;
2496 range_table_work
.table
= 0;
2497 range_table_work
.allocated
= 0;
2499 /* Initialize the pattern buffer. */
2501 bufp
->syntax
= syntax
;
2503 bufp
->fastmap_accurate
= 0;
2504 bufp
->not_bol
= bufp
->not_eol
= 0;
2505 bufp
->used_syntax
= 0;
2507 /* Set `used' to zero, so that if we return an error, the pattern
2508 printer (for debugging) will think there's no pattern. We reset it
2512 /* Always count groups, whether or not bufp->no_sub is set. */
2515 #if !defined emacs && !defined SYNTAX_TABLE
2516 /* Initialize the syntax table. */
2517 init_syntax_once ();
2520 if (bufp
->allocated
== 0)
2523 { /* If zero allocated, but buffer is non-null, try to realloc
2524 enough space. This loses if buffer's address is bogus, but
2525 that is the user's responsibility. */
2526 RETALLOC (bufp
->buffer
, INIT_BUF_SIZE
, unsigned char);
2529 { /* Caller did not allocate a buffer. Do it for them. */
2530 bufp
->buffer
= TALLOC (INIT_BUF_SIZE
, unsigned char);
2532 if (!bufp
->buffer
) FREE_STACK_RETURN (REG_ESPACE
);
2534 bufp
->allocated
= INIT_BUF_SIZE
;
2537 begalt
= b
= bufp
->buffer
;
2539 /* Loop through the uncompiled pattern until we're at the end. */
2545 /* If this is the end of an included regexp,
2546 pop back to the main regexp and try again. */
2550 pattern
= main_pattern
;
2556 /* If this is the end of the main regexp, we are done. */
2569 /* If there's no special whitespace regexp, treat
2570 spaces normally. And don't try to do this recursively. */
2571 if (!whitespace_regexp
|| in_subpattern
)
2574 /* Peek past following spaces. */
2581 /* If the spaces are followed by a repetition op,
2582 treat them normally. */
2584 && (*p1
== '*' || *p1
== '+' || *p1
== '?'
2585 || (*p1
== '\\' && p1
+ 1 != pend
&& p1
[1] == '{')))
2588 /* Replace the spaces with the whitespace regexp. */
2592 main_pattern
= pattern
;
2593 p
= pattern
= (re_char
*) whitespace_regexp
;
2594 pend
= p
+ strlen (whitespace_regexp
);
2601 if ( /* If at start of pattern, it's an operator. */
2603 /* If context independent, it's an operator. */
2604 || syntax
& RE_CONTEXT_INDEP_ANCHORS
2605 /* Otherwise, depends on what's come before. */
2606 || at_begline_loc_p (pattern
, p
, syntax
))
2607 BUF_PUSH ((syntax
& RE_NO_NEWLINE_ANCHOR
) ? begbuf
: begline
);
2616 if ( /* If at end of pattern, it's an operator. */
2618 /* If context independent, it's an operator. */
2619 || syntax
& RE_CONTEXT_INDEP_ANCHORS
2620 /* Otherwise, depends on what's next. */
2621 || at_endline_loc_p (p
, pend
, syntax
))
2622 BUF_PUSH ((syntax
& RE_NO_NEWLINE_ANCHOR
) ? endbuf
: endline
);
2631 if ((syntax
& RE_BK_PLUS_QM
)
2632 || (syntax
& RE_LIMITED_OPS
))
2636 /* If there is no previous pattern... */
2639 if (syntax
& RE_CONTEXT_INVALID_OPS
)
2640 FREE_STACK_RETURN (REG_BADRPT
);
2641 else if (!(syntax
& RE_CONTEXT_INDEP_OPS
))
2646 /* 1 means zero (many) matches is allowed. */
2647 boolean zero_times_ok
= 0, many_times_ok
= 0;
2650 /* If there is a sequence of repetition chars, collapse it
2651 down to just one (the right one). We can't combine
2652 interval operators with these because of, e.g., `a{2}*',
2653 which should only match an even number of `a's. */
2657 if ((syntax
& RE_FRUGAL
)
2658 && c
== '?' && (zero_times_ok
|| many_times_ok
))
2662 zero_times_ok
|= c
!= '+';
2663 many_times_ok
|= c
!= '?';
2669 || (!(syntax
& RE_BK_PLUS_QM
)
2670 && (*p
== '+' || *p
== '?')))
2672 else if (syntax
& RE_BK_PLUS_QM
&& *p
== '\\')
2675 FREE_STACK_RETURN (REG_EESCAPE
);
2676 if (p
[1] == '+' || p
[1] == '?')
2677 PATFETCH (c
); /* Gobble up the backslash. */
2683 /* If we get here, we found another repeat character. */
2687 /* Star, etc. applied to an empty pattern is equivalent
2688 to an empty pattern. */
2689 if (!laststart
|| laststart
== b
)
2692 /* Now we know whether or not zero matches is allowed
2693 and also whether or not two or more matches is allowed. */
2698 boolean simple
= skip_one_char (laststart
) == b
;
2699 size_t startoffset
= 0;
2701 /* Check if the loop can match the empty string. */
2702 (simple
|| !analyze_first (laststart
, b
, NULL
, 0))
2703 ? on_failure_jump
: on_failure_jump_loop
;
2704 assert (skip_one_char (laststart
) <= b
);
2706 if (!zero_times_ok
&& simple
)
2707 { /* Since simple * loops can be made faster by using
2708 on_failure_keep_string_jump, we turn simple P+
2709 into PP* if P is simple. */
2710 unsigned char *p1
, *p2
;
2711 startoffset
= b
- laststart
;
2712 GET_BUFFER_SPACE (startoffset
);
2713 p1
= b
; p2
= laststart
;
2719 GET_BUFFER_SPACE (6);
2722 STORE_JUMP (ofj
, b
, b
+ 6);
2724 /* Simple * loops can use on_failure_keep_string_jump
2725 depending on what follows. But since we don't know
2726 that yet, we leave the decision up to
2727 on_failure_jump_smart. */
2728 INSERT_JUMP (simple
? on_failure_jump_smart
: ofj
,
2729 laststart
+ startoffset
, b
+ 6);
2731 STORE_JUMP (jump
, b
, laststart
+ startoffset
);
2736 /* A simple ? pattern. */
2737 assert (zero_times_ok
);
2738 GET_BUFFER_SPACE (3);
2739 INSERT_JUMP (on_failure_jump
, laststart
, b
+ 3);
2743 else /* not greedy */
2744 { /* I wish the greedy and non-greedy cases could be merged. */
2746 GET_BUFFER_SPACE (7); /* We might use less. */
2749 boolean emptyp
= analyze_first (laststart
, b
, NULL
, 0);
2751 /* The non-greedy multiple match looks like
2752 a repeat..until: we only need a conditional jump
2753 at the end of the loop. */
2754 if (emptyp
) BUF_PUSH (no_op
);
2755 STORE_JUMP (emptyp
? on_failure_jump_nastyloop
2756 : on_failure_jump
, b
, laststart
);
2760 /* The repeat...until naturally matches one or more.
2761 To also match zero times, we need to first jump to
2762 the end of the loop (its conditional jump). */
2763 INSERT_JUMP (jump
, laststart
, b
);
2769 /* non-greedy a?? */
2770 INSERT_JUMP (jump
, laststart
, b
+ 3);
2772 INSERT_JUMP (on_failure_jump
, laststart
, laststart
+ 6);
2791 CLEAR_RANGE_TABLE_WORK_USED (range_table_work
);
2793 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2795 /* Ensure that we have enough space to push a charset: the
2796 opcode, the length count, and the bitset; 34 bytes in all. */
2797 GET_BUFFER_SPACE (34);
2801 /* We test `*p == '^' twice, instead of using an if
2802 statement, so we only need one BUF_PUSH. */
2803 BUF_PUSH (*p
== '^' ? charset_not
: charset
);
2807 /* Remember the first position in the bracket expression. */
2810 /* Push the number of bytes in the bitmap. */
2811 BUF_PUSH ((1 << BYTEWIDTH
) / BYTEWIDTH
);
2813 /* Clear the whole map. */
2814 memset (b
, 0, (1 << BYTEWIDTH
) / BYTEWIDTH
);
2816 /* charset_not matches newline according to a syntax bit. */
2817 if ((re_opcode_t
) b
[-2] == charset_not
2818 && (syntax
& RE_HAT_LISTS_NOT_NEWLINE
))
2819 SET_LIST_BIT ('\n');
2821 /* Read in characters and ranges, setting map bits. */
2824 boolean escaped_char
= false;
2825 const unsigned char *p2
= p
;
2829 if (p
== pend
) FREE_STACK_RETURN (REG_EBRACK
);
2831 /* See if we're at the beginning of a possible character
2833 if (syntax
& RE_CHAR_CLASSES
&&
2834 (cc
= re_wctype_parse(&p
, pend
- p
)) != -1)
2837 FREE_STACK_RETURN (REG_ECTYPE
);
2840 FREE_STACK_RETURN (REG_EBRACK
);
2843 for (ch
= 0; ch
< (1 << BYTEWIDTH
); ++ch
)
2844 if (re_iswctype (btowc (ch
), cc
))
2847 if (c
< (1 << BYTEWIDTH
))
2851 /* Most character classes in a multibyte match just set
2852 a flag. Exceptions are is_blank, is_digit, is_cntrl, and
2853 is_xdigit, since they can only match ASCII characters.
2854 We don't need to handle them for multibyte. */
2856 /* Setup the gl_state object to its buffer-defined value.
2857 This hardcodes the buffer-global syntax-table for ASCII
2858 chars, while the other chars will obey syntax-table
2859 properties. It's not ideal, but it's the way it's been
2861 SETUP_BUFFER_SYNTAX_TABLE ();
2863 for (c
= 0; c
< 0x80; ++c
)
2864 if (re_iswctype (c
, cc
))
2870 if (ASCII_CHAR_P (c1
))
2872 else if ((c1
= RE_CHAR_TO_UNIBYTE (c1
)) >= 0)
2875 SET_RANGE_TABLE_WORK_AREA_BIT
2876 (range_table_work
, re_wctype_to_bit (cc
));
2878 /* In most cases the matching rule for char classes only
2879 uses the syntax table for multibyte chars, so that the
2880 content of the syntax-table is not hardcoded in the
2881 range_table. SPACE and WORD are the two exceptions. */
2882 if ((1 << cc
) & ((1 << RECC_SPACE
) | (1 << RECC_WORD
)))
2883 bufp
->used_syntax
= 1;
2885 /* Repeat the loop. */
2889 /* Don't translate yet. The range TRANSLATE(X..Y) cannot
2890 always be determined from TRANSLATE(X) and TRANSLATE(Y)
2891 So the translation is done later in a loop. Example:
2892 (let ((case-fold-search t)) (string-match "[A-_]" "A")) */
2895 /* \ might escape characters inside [...] and [^...]. */
2896 if ((syntax
& RE_BACKSLASH_ESCAPE_IN_LISTS
) && c
== '\\')
2898 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
2901 escaped_char
= true;
2905 /* Could be the end of the bracket expression. If it's
2906 not (i.e., when the bracket expression is `[]' so
2907 far), the ']' character bit gets set way below. */
2908 if (c
== ']' && p2
!= p1
)
2912 if (p
< pend
&& p
[0] == '-' && p
[1] != ']')
2915 /* Discard the `-'. */
2918 /* Fetch the character which ends the range. */
2921 if (CHAR_BYTE8_P (c1
)
2922 && ! ASCII_CHAR_P (c
) && ! CHAR_BYTE8_P (c
))
2923 /* Treat the range from a multibyte character to
2924 raw-byte character as empty. */
2929 /* Range from C to C. */
2934 if (syntax
& RE_NO_EMPTY_RANGES
)
2935 FREE_STACK_RETURN (REG_ERANGEX
);
2936 /* Else, repeat the loop. */
2941 /* Set the range into bitmap */
2942 for (; c
<= c1
; c
++)
2945 if (ch
< (1 << BYTEWIDTH
))
2952 SETUP_ASCII_RANGE (range_table_work
, c
, ch
);
2954 if (CHAR_BYTE8_P (c1
))
2955 c
= BYTE8_TO_CHAR (128);
2959 if (CHAR_BYTE8_P (c
))
2961 c
= CHAR_TO_BYTE8 (c
);
2962 c1
= CHAR_TO_BYTE8 (c1
);
2963 for (; c
<= c1
; c
++)
2968 SETUP_MULTIBYTE_RANGE (range_table_work
, c
, c1
);
2972 SETUP_UNIBYTE_RANGE (range_table_work
, c
, c1
);
2979 /* Discard any (non)matching list bytes that are all 0 at the
2980 end of the map. Decrease the map-length byte too. */
2981 while ((int) b
[-1] > 0 && b
[b
[-1] - 1] == 0)
2985 /* Build real range table from work area. */
2986 if (RANGE_TABLE_WORK_USED (range_table_work
)
2987 || RANGE_TABLE_WORK_BITS (range_table_work
))
2990 int used
= RANGE_TABLE_WORK_USED (range_table_work
);
2992 /* Allocate space for COUNT + RANGE_TABLE. Needs two
2993 bytes for flags, two for COUNT, and three bytes for
2995 GET_BUFFER_SPACE (4 + used
* 3);
2997 /* Indicate the existence of range table. */
2998 laststart
[1] |= 0x80;
3000 /* Store the character class flag bits into the range table.
3001 If not in emacs, these flag bits are always 0. */
3002 *b
++ = RANGE_TABLE_WORK_BITS (range_table_work
) & 0xff;
3003 *b
++ = RANGE_TABLE_WORK_BITS (range_table_work
) >> 8;
3005 STORE_NUMBER_AND_INCR (b
, used
/ 2);
3006 for (i
= 0; i
< used
; i
++)
3007 STORE_CHARACTER_AND_INCR
3008 (b
, RANGE_TABLE_WORK_ELT (range_table_work
, i
));
3015 if (syntax
& RE_NO_BK_PARENS
)
3022 if (syntax
& RE_NO_BK_PARENS
)
3029 if (syntax
& RE_NEWLINE_ALT
)
3036 if (syntax
& RE_NO_BK_VBAR
)
3043 if (syntax
& RE_INTERVALS
&& syntax
& RE_NO_BK_BRACES
)
3044 goto handle_interval
;
3050 if (p
== pend
) FREE_STACK_RETURN (REG_EESCAPE
);
3052 /* Do not translate the character after the \, so that we can
3053 distinguish, e.g., \B from \b, even if we normally would
3054 translate, e.g., B to b. */
3060 if (syntax
& RE_NO_BK_PARENS
)
3061 goto normal_backslash
;
3066 regnum_t regnum
= 0;
3069 /* Look for a special (?...) construct */
3070 if ((syntax
& RE_SHY_GROUPS
) && *p
== '?')
3072 PATFETCH (c
); /* Gobble up the '?'. */
3078 case ':': shy
= 1; break;
3080 /* An explicitly specified regnum must start
3083 FREE_STACK_RETURN (REG_BADPAT
);
3084 case '1': case '2': case '3': case '4':
3085 case '5': case '6': case '7': case '8': case '9':
3086 regnum
= 10*regnum
+ (c
- '0'); break;
3088 /* Only (?:...) is supported right now. */
3089 FREE_STACK_RETURN (REG_BADPAT
);
3096 regnum
= ++bufp
->re_nsub
;
3098 { /* It's actually not shy, but explicitly numbered. */
3100 if (regnum
> bufp
->re_nsub
)
3101 bufp
->re_nsub
= regnum
;
3102 else if (regnum
> bufp
->re_nsub
3103 /* Ideally, we'd want to check that the specified
3104 group can't have matched (i.e. all subgroups
3105 using the same regnum are in other branches of
3106 OR patterns), but we don't currently keep track
3107 of enough info to do that easily. */
3108 || group_in_compile_stack (compile_stack
, regnum
))
3109 FREE_STACK_RETURN (REG_BADPAT
);
3112 /* It's really shy. */
3113 regnum
= - bufp
->re_nsub
;
3115 if (COMPILE_STACK_FULL
)
3117 RETALLOC (compile_stack
.stack
, compile_stack
.size
<< 1,
3118 compile_stack_elt_t
);
3119 if (compile_stack
.stack
== NULL
) return REG_ESPACE
;
3121 compile_stack
.size
<<= 1;
3124 /* These are the values to restore when we hit end of this
3125 group. They are all relative offsets, so that if the
3126 whole pattern moves because of realloc, they will still
3128 COMPILE_STACK_TOP
.begalt_offset
= begalt
- bufp
->buffer
;
3129 COMPILE_STACK_TOP
.fixup_alt_jump
3130 = fixup_alt_jump
? fixup_alt_jump
- bufp
->buffer
+ 1 : 0;
3131 COMPILE_STACK_TOP
.laststart_offset
= b
- bufp
->buffer
;
3132 COMPILE_STACK_TOP
.regnum
= regnum
;
3134 /* Do not push a start_memory for groups beyond the last one
3135 we can represent in the compiled pattern. */
3136 if (regnum
<= MAX_REGNUM
&& regnum
> 0)
3137 BUF_PUSH_2 (start_memory
, regnum
);
3139 compile_stack
.avail
++;
3144 /* If we've reached MAX_REGNUM groups, then this open
3145 won't actually generate any code, so we'll have to
3146 clear pending_exact explicitly. */
3152 if (syntax
& RE_NO_BK_PARENS
) goto normal_backslash
;
3154 if (COMPILE_STACK_EMPTY
)
3156 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
3157 goto normal_backslash
;
3159 FREE_STACK_RETURN (REG_ERPAREN
);
3165 /* See similar code for backslashed left paren above. */
3166 if (COMPILE_STACK_EMPTY
)
3168 if (syntax
& RE_UNMATCHED_RIGHT_PAREN_ORD
)
3171 FREE_STACK_RETURN (REG_ERPAREN
);
3174 /* Since we just checked for an empty stack above, this
3175 ``can't happen''. */
3176 assert (compile_stack
.avail
!= 0);
3178 /* We don't just want to restore into `regnum', because
3179 later groups should continue to be numbered higher,
3180 as in `(ab)c(de)' -- the second group is #2. */
3183 compile_stack
.avail
--;
3184 begalt
= bufp
->buffer
+ COMPILE_STACK_TOP
.begalt_offset
;
3186 = COMPILE_STACK_TOP
.fixup_alt_jump
3187 ? bufp
->buffer
+ COMPILE_STACK_TOP
.fixup_alt_jump
- 1
3189 laststart
= bufp
->buffer
+ COMPILE_STACK_TOP
.laststart_offset
;
3190 regnum
= COMPILE_STACK_TOP
.regnum
;
3191 /* If we've reached MAX_REGNUM groups, then this open
3192 won't actually generate any code, so we'll have to
3193 clear pending_exact explicitly. */
3196 /* We're at the end of the group, so now we know how many
3197 groups were inside this one. */
3198 if (regnum
<= MAX_REGNUM
&& regnum
> 0)
3199 BUF_PUSH_2 (stop_memory
, regnum
);
3204 case '|': /* `\|'. */
3205 if (syntax
& RE_LIMITED_OPS
|| syntax
& RE_NO_BK_VBAR
)
3206 goto normal_backslash
;
3208 if (syntax
& RE_LIMITED_OPS
)
3211 /* Insert before the previous alternative a jump which
3212 jumps to this alternative if the former fails. */
3213 GET_BUFFER_SPACE (3);
3214 INSERT_JUMP (on_failure_jump
, begalt
, b
+ 6);
3218 /* The alternative before this one has a jump after it
3219 which gets executed if it gets matched. Adjust that
3220 jump so it will jump to this alternative's analogous
3221 jump (put in below, which in turn will jump to the next
3222 (if any) alternative's such jump, etc.). The last such
3223 jump jumps to the correct final destination. A picture:
3229 If we are at `b', then fixup_alt_jump right now points to a
3230 three-byte space after `a'. We'll put in the jump, set
3231 fixup_alt_jump to right after `b', and leave behind three
3232 bytes which we'll fill in when we get to after `c'. */
3236 /* Mark and leave space for a jump after this alternative,
3237 to be filled in later either by next alternative or
3238 when know we're at the end of a series of alternatives. */
3240 GET_BUFFER_SPACE (3);
3249 /* If \{ is a literal. */
3250 if (!(syntax
& RE_INTERVALS
)
3251 /* If we're at `\{' and it's not the open-interval
3253 || (syntax
& RE_NO_BK_BRACES
))
3254 goto normal_backslash
;
3258 /* If got here, then the syntax allows intervals. */
3260 /* At least (most) this many matches must be made. */
3261 int lower_bound
= 0, upper_bound
= -1;
3265 GET_INTERVAL_COUNT (lower_bound
);
3268 GET_INTERVAL_COUNT (upper_bound
);
3270 /* Interval such as `{1}' => match exactly once. */
3271 upper_bound
= lower_bound
;
3274 || (0 <= upper_bound
&& upper_bound
< lower_bound
))
3275 FREE_STACK_RETURN (REG_BADBR
);
3277 if (!(syntax
& RE_NO_BK_BRACES
))
3280 FREE_STACK_RETURN (REG_BADBR
);
3282 FREE_STACK_RETURN (REG_EESCAPE
);
3287 FREE_STACK_RETURN (REG_BADBR
);
3289 /* We just parsed a valid interval. */
3291 /* If it's invalid to have no preceding re. */
3294 if (syntax
& RE_CONTEXT_INVALID_OPS
)
3295 FREE_STACK_RETURN (REG_BADRPT
);
3296 else if (syntax
& RE_CONTEXT_INDEP_OPS
)
3299 goto unfetch_interval
;
3302 if (upper_bound
== 0)
3303 /* If the upper bound is zero, just drop the sub pattern
3306 else if (lower_bound
== 1 && upper_bound
== 1)
3307 /* Just match it once: nothing to do here. */
3310 /* Otherwise, we have a nontrivial interval. When
3311 we're all done, the pattern will look like:
3312 set_number_at <jump count> <upper bound>
3313 set_number_at <succeed_n count> <lower bound>
3314 succeed_n <after jump addr> <succeed_n count>
3316 jump_n <succeed_n addr> <jump count>
3317 (The upper bound and `jump_n' are omitted if
3318 `upper_bound' is 1, though.) */
3320 { /* If the upper bound is > 1, we need to insert
3321 more at the end of the loop. */
3322 unsigned int nbytes
= (upper_bound
< 0 ? 3
3323 : upper_bound
> 1 ? 5 : 0);
3324 unsigned int startoffset
= 0;
3326 GET_BUFFER_SPACE (20); /* We might use less. */
3328 if (lower_bound
== 0)
3330 /* A succeed_n that starts with 0 is really a
3331 a simple on_failure_jump_loop. */
3332 INSERT_JUMP (on_failure_jump_loop
, laststart
,
3338 /* Initialize lower bound of the `succeed_n', even
3339 though it will be set during matching by its
3340 attendant `set_number_at' (inserted next),
3341 because `re_compile_fastmap' needs to know.
3342 Jump to the `jump_n' we might insert below. */
3343 INSERT_JUMP2 (succeed_n
, laststart
,
3348 /* Code to initialize the lower bound. Insert
3349 before the `succeed_n'. The `5' is the last two
3350 bytes of this `set_number_at', plus 3 bytes of
3351 the following `succeed_n'. */
3352 insert_op2 (set_number_at
, laststart
, 5, lower_bound
, b
);
3357 if (upper_bound
< 0)
3359 /* A negative upper bound stands for infinity,
3360 in which case it degenerates to a plain jump. */
3361 STORE_JUMP (jump
, b
, laststart
+ startoffset
);
3364 else if (upper_bound
> 1)
3365 { /* More than one repetition is allowed, so
3366 append a backward jump to the `succeed_n'
3367 that starts this interval.
3369 When we've reached this during matching,
3370 we'll have matched the interval once, so
3371 jump back only `upper_bound - 1' times. */
3372 STORE_JUMP2 (jump_n
, b
, laststart
+ startoffset
,
3376 /* The location we want to set is the second
3377 parameter of the `jump_n'; that is `b-2' as
3378 an absolute address. `laststart' will be
3379 the `set_number_at' we're about to insert;
3380 `laststart+3' the number to set, the source
3381 for the relative address. But we are
3382 inserting into the middle of the pattern --
3383 so everything is getting moved up by 5.
3384 Conclusion: (b - 2) - (laststart + 3) + 5,
3385 i.e., b - laststart.
3387 We insert this at the beginning of the loop
3388 so that if we fail during matching, we'll
3389 reinitialize the bounds. */
3390 insert_op2 (set_number_at
, laststart
, b
- laststart
,
3391 upper_bound
- 1, b
);
3396 beg_interval
= NULL
;
3401 /* If an invalid interval, match the characters as literals. */
3402 assert (beg_interval
);
3404 beg_interval
= NULL
;
3406 /* normal_char and normal_backslash need `c'. */
3409 if (!(syntax
& RE_NO_BK_BRACES
))
3411 assert (p
> pattern
&& p
[-1] == '\\');
3412 goto normal_backslash
;
3426 BUF_PUSH_2 (syntaxspec
, syntax_spec_code
[c
]);
3432 BUF_PUSH_2 (notsyntaxspec
, syntax_spec_code
[c
]);
3438 BUF_PUSH_2 (categoryspec
, c
);
3444 BUF_PUSH_2 (notcategoryspec
, c
);
3450 if (syntax
& RE_NO_GNU_OPS
)
3453 BUF_PUSH_2 (syntaxspec
, Sword
);
3458 if (syntax
& RE_NO_GNU_OPS
)
3461 BUF_PUSH_2 (notsyntaxspec
, Sword
);
3466 if (syntax
& RE_NO_GNU_OPS
)
3473 if (syntax
& RE_NO_GNU_OPS
)
3480 if (syntax
& RE_NO_GNU_OPS
)
3489 FREE_STACK_RETURN (REG_BADPAT
);
3493 if (syntax
& RE_NO_GNU_OPS
)
3495 BUF_PUSH (wordbound
);
3499 if (syntax
& RE_NO_GNU_OPS
)
3501 BUF_PUSH (notwordbound
);
3505 if (syntax
& RE_NO_GNU_OPS
)
3511 if (syntax
& RE_NO_GNU_OPS
)
3516 case '1': case '2': case '3': case '4': case '5':
3517 case '6': case '7': case '8': case '9':
3521 if (syntax
& RE_NO_BK_REFS
)
3522 goto normal_backslash
;
3526 if (reg
> bufp
->re_nsub
|| reg
< 1
3527 /* Can't back reference to a subexp before its end. */
3528 || group_in_compile_stack (compile_stack
, reg
))
3529 FREE_STACK_RETURN (REG_ESUBREG
);
3532 BUF_PUSH_2 (duplicate
, reg
);
3539 if (syntax
& RE_BK_PLUS_QM
)
3542 goto normal_backslash
;
3546 /* You might think it would be useful for \ to mean
3547 not to translate; but if we don't translate it
3548 it will never match anything. */
3555 /* Expects the character in `c'. */
3557 /* If no exactn currently being built. */
3560 /* If last exactn not at current position. */
3561 || pending_exact
+ *pending_exact
+ 1 != b
3563 /* We have only one byte following the exactn for the count. */
3564 || *pending_exact
>= (1 << BYTEWIDTH
) - MAX_MULTIBYTE_LENGTH
3566 /* If followed by a repetition operator. */
3567 || (p
!= pend
&& (*p
== '*' || *p
== '^'))
3568 || ((syntax
& RE_BK_PLUS_QM
)
3569 ? p
+ 1 < pend
&& *p
== '\\' && (p
[1] == '+' || p
[1] == '?')
3570 : p
!= pend
&& (*p
== '+' || *p
== '?'))
3571 || ((syntax
& RE_INTERVALS
)
3572 && ((syntax
& RE_NO_BK_BRACES
)
3573 ? p
!= pend
&& *p
== '{'
3574 : p
+ 1 < pend
&& p
[0] == '\\' && p
[1] == '{')))
3576 /* Start building a new exactn. */
3580 BUF_PUSH_2 (exactn
, 0);
3581 pending_exact
= b
- 1;
3584 GET_BUFFER_SPACE (MAX_MULTIBYTE_LENGTH
);
3591 len
= CHAR_STRING (c
, b
);
3596 c1
= RE_CHAR_TO_MULTIBYTE (c
);
3597 if (! CHAR_BYTE8_P (c1
))
3599 re_wchar_t c2
= TRANSLATE (c1
);
3601 if (c1
!= c2
&& (c1
= RE_CHAR_TO_UNIBYTE (c2
)) >= 0)
3607 (*pending_exact
) += len
;
3612 } /* while p != pend */
3615 /* Through the pattern now. */
3619 if (!COMPILE_STACK_EMPTY
)
3620 FREE_STACK_RETURN (REG_EPAREN
);
3622 /* If we don't want backtracking, force success
3623 the first time we reach the end of the compiled pattern. */
3624 if (!posix_backtracking
)
3627 /* We have succeeded; set the length of the buffer. */
3628 bufp
->used
= b
- bufp
->buffer
;
3633 re_compile_fastmap (bufp
);
3634 DEBUG_PRINT ("\nCompiled pattern: \n");
3635 print_compiled_pattern (bufp
);
3640 #ifndef MATCH_MAY_ALLOCATE
3641 /* Initialize the failure stack to the largest possible stack. This
3642 isn't necessary unless we're trying to avoid calling alloca in
3643 the search and match routines. */
3645 int num_regs
= bufp
->re_nsub
+ 1;
3647 if (fail_stack
.size
< re_max_failures
* TYPICAL_FAILURE_SIZE
)
3649 fail_stack
.size
= re_max_failures
* TYPICAL_FAILURE_SIZE
;
3650 falk_stack
.stack
= realloc (fail_stack
.stack
,
3651 fail_stack
.size
* sizeof *falk_stack
.stack
);
3654 regex_grow_registers (num_regs
);
3656 #endif /* not MATCH_MAY_ALLOCATE */
3658 FREE_STACK_RETURN (REG_NOERROR
);
3663 # undef posix_backtracking
3665 } /* regex_compile */
3667 /* Subroutines for `regex_compile'. */
3669 /* Store OP at LOC followed by two-byte integer parameter ARG. */
3672 store_op1 (re_opcode_t op
, unsigned char *loc
, int arg
)
3674 *loc
= (unsigned char) op
;
3675 STORE_NUMBER (loc
+ 1, arg
);
3679 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
3682 store_op2 (re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
)
3684 *loc
= (unsigned char) op
;
3685 STORE_NUMBER (loc
+ 1, arg1
);
3686 STORE_NUMBER (loc
+ 3, arg2
);
3690 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
3691 for OP followed by two-byte integer parameter ARG. */
3694 insert_op1 (re_opcode_t op
, unsigned char *loc
, int arg
, unsigned char *end
)
3696 register unsigned char *pfrom
= end
;
3697 register unsigned char *pto
= end
+ 3;
3699 while (pfrom
!= loc
)
3702 store_op1 (op
, loc
, arg
);
3706 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
3709 insert_op2 (re_opcode_t op
, unsigned char *loc
, int arg1
, int arg2
, unsigned char *end
)
3711 register unsigned char *pfrom
= end
;
3712 register unsigned char *pto
= end
+ 5;
3714 while (pfrom
!= loc
)
3717 store_op2 (op
, loc
, arg1
, arg2
);
3721 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
3722 after an alternative or a begin-subexpression. We assume there is at
3723 least one character before the ^. */
3726 at_begline_loc_p (const_re_char
*pattern
, const_re_char
*p
, reg_syntax_t syntax
)
3728 re_char
*prev
= p
- 2;
3729 boolean odd_backslashes
;
3731 /* After a subexpression? */
3733 odd_backslashes
= (syntax
& RE_NO_BK_PARENS
) == 0;
3735 /* After an alternative? */
3736 else if (*prev
== '|')
3737 odd_backslashes
= (syntax
& RE_NO_BK_VBAR
) == 0;
3739 /* After a shy subexpression? */
3740 else if (*prev
== ':' && (syntax
& RE_SHY_GROUPS
))
3742 /* Skip over optional regnum. */
3743 while (prev
- 1 >= pattern
&& prev
[-1] >= '0' && prev
[-1] <= '9')
3746 if (!(prev
- 2 >= pattern
3747 && prev
[-1] == '?' && prev
[-2] == '('))
3750 odd_backslashes
= (syntax
& RE_NO_BK_PARENS
) == 0;
3755 /* Count the number of preceding backslashes. */
3757 while (prev
- 1 >= pattern
&& prev
[-1] == '\\')
3759 return (p
- prev
) & odd_backslashes
;
3763 /* The dual of at_begline_loc_p. This one is for $. We assume there is
3764 at least one character after the $, i.e., `P < PEND'. */
3767 at_endline_loc_p (const_re_char
*p
, const_re_char
*pend
, reg_syntax_t syntax
)
3770 boolean next_backslash
= *next
== '\\';
3771 re_char
*next_next
= p
+ 1 < pend
? p
+ 1 : 0;
3774 /* Before a subexpression? */
3775 (syntax
& RE_NO_BK_PARENS
? *next
== ')'
3776 : next_backslash
&& next_next
&& *next_next
== ')')
3777 /* Before an alternative? */
3778 || (syntax
& RE_NO_BK_VBAR
? *next
== '|'
3779 : next_backslash
&& next_next
&& *next_next
== '|');
3783 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
3784 false if it's not. */
3787 group_in_compile_stack (compile_stack_type compile_stack
, regnum_t regnum
)
3789 ssize_t this_element
;
3791 for (this_element
= compile_stack
.avail
- 1;
3794 if (compile_stack
.stack
[this_element
].regnum
== regnum
)
3801 If fastmap is non-NULL, go through the pattern and fill fastmap
3802 with all the possible leading chars. If fastmap is NULL, don't
3803 bother filling it up (obviously) and only return whether the
3804 pattern could potentially match the empty string.
3806 Return 1 if p..pend might match the empty string.
3807 Return 0 if p..pend matches at least one char.
3808 Return -1 if fastmap was not updated accurately. */
3811 analyze_first (const_re_char
*p
, const_re_char
*pend
, char *fastmap
,
3812 const int multibyte
)
3817 /* If all elements for base leading-codes in fastmap is set, this
3818 flag is set true. */
3819 boolean match_any_multibyte_characters
= false;
3823 /* The loop below works as follows:
3824 - It has a working-list kept in the PATTERN_STACK and which basically
3825 starts by only containing a pointer to the first operation.
3826 - If the opcode we're looking at is a match against some set of
3827 chars, then we add those chars to the fastmap and go on to the
3828 next work element from the worklist (done via `break').
3829 - If the opcode is a control operator on the other hand, we either
3830 ignore it (if it's meaningless at this point, such as `start_memory')
3831 or execute it (if it's a jump). If the jump has several destinations
3832 (i.e. `on_failure_jump'), then we push the other destination onto the
3834 We guarantee termination by ignoring backward jumps (more or less),
3835 so that `p' is monotonically increasing. More to the point, we
3836 never set `p' (or push) anything `<= p1'. */
3840 /* `p1' is used as a marker of how far back a `on_failure_jump'
3841 can go without being ignored. It is normally equal to `p'
3842 (which prevents any backward `on_failure_jump') except right
3843 after a plain `jump', to allow patterns such as:
3846 10: on_failure_jump 3
3847 as used for the *? operator. */
3856 /* If the first character has to match a backreference, that means
3857 that the group was empty (since it already matched). Since this
3858 is the only case that interests us here, we can assume that the
3859 backreference must match the empty string. */
3864 /* Following are the cases which match a character. These end
3870 /* If multibyte is nonzero, the first byte of each
3871 character is an ASCII or a leading code. Otherwise,
3872 each byte is a character. Thus, this works in both
3877 /* For the case of matching this unibyte regex
3878 against multibyte, we must set a leading code of
3879 the corresponding multibyte character. */
3880 int c
= RE_CHAR_TO_MULTIBYTE (p
[1]);
3882 fastmap
[CHAR_LEADING_CODE (c
)] = 1;
3889 /* We could put all the chars except for \n (and maybe \0)
3890 but we don't bother since it is generally not worth it. */
3891 if (!fastmap
) break;
3896 if (!fastmap
) break;
3898 /* Chars beyond end of bitmap are possible matches. */
3899 for (j
= CHARSET_BITMAP_SIZE (&p
[-1]) * BYTEWIDTH
;
3900 j
< (1 << BYTEWIDTH
); j
++)
3906 if (!fastmap
) break;
3907 not = (re_opcode_t
) *(p
- 1) == charset_not
;
3908 for (j
= CHARSET_BITMAP_SIZE (&p
[-1]) * BYTEWIDTH
- 1, p
++;
3910 if (!!(p
[j
/ BYTEWIDTH
] & (1 << (j
% BYTEWIDTH
))) ^ not)
3914 if (/* Any leading code can possibly start a character
3915 which doesn't match the specified set of characters. */
3918 /* If we can match a character class, we can match any
3919 multibyte characters. */
3920 (CHARSET_RANGE_TABLE_EXISTS_P (&p
[-2])
3921 && CHARSET_RANGE_TABLE_BITS (&p
[-2]) != 0))
3924 if (match_any_multibyte_characters
== false)
3926 for (j
= MIN_MULTIBYTE_LEADING_CODE
;
3927 j
<= MAX_MULTIBYTE_LEADING_CODE
; j
++)
3929 match_any_multibyte_characters
= true;
3933 else if (!not && CHARSET_RANGE_TABLE_EXISTS_P (&p
[-2])
3934 && match_any_multibyte_characters
== false)
3936 /* Set fastmap[I] to 1 where I is a leading code of each
3937 multibyte character in the range table. */
3939 unsigned char lc1
, lc2
;
3941 /* Make P points the range table. `+ 2' is to skip flag
3942 bits for a character class. */
3943 p
+= CHARSET_BITMAP_SIZE (&p
[-2]) + 2;
3945 /* Extract the number of ranges in range table into COUNT. */
3946 EXTRACT_NUMBER_AND_INCR (count
, p
);
3947 for (; count
> 0; count
--, p
+= 3)
3949 /* Extract the start and end of each range. */
3950 EXTRACT_CHARACTER (c
, p
);
3951 lc1
= CHAR_LEADING_CODE (c
);
3953 EXTRACT_CHARACTER (c
, p
);
3954 lc2
= CHAR_LEADING_CODE (c
);
3955 for (j
= lc1
; j
<= lc2
; j
++)
3964 if (!fastmap
) break;
3966 not = (re_opcode_t
)p
[-1] == notsyntaxspec
;
3968 for (j
= 0; j
< (1 << BYTEWIDTH
); j
++)
3969 if ((SYNTAX (j
) == (enum syntaxcode
) k
) ^ not)
3973 /* This match depends on text properties. These end with
3974 aborting optimizations. */
3978 case notcategoryspec
:
3979 if (!fastmap
) break;
3980 not = (re_opcode_t
)p
[-1] == notcategoryspec
;
3982 for (j
= (1 << BYTEWIDTH
); j
>= 0; j
--)
3983 if ((CHAR_HAS_CATEGORY (j
, k
)) ^ not)
3986 /* Any leading code can possibly start a character which
3987 has or doesn't has the specified category. */
3988 if (match_any_multibyte_characters
== false)
3990 for (j
= MIN_MULTIBYTE_LEADING_CODE
;
3991 j
<= MAX_MULTIBYTE_LEADING_CODE
; j
++)
3993 match_any_multibyte_characters
= true;
3997 /* All cases after this match the empty string. These end with
4017 EXTRACT_NUMBER_AND_INCR (j
, p
);
4019 /* Backward jumps can only go back to code that we've already
4020 visited. `re_compile' should make sure this is true. */
4025 case on_failure_jump
:
4026 case on_failure_keep_string_jump
:
4027 case on_failure_jump_loop
:
4028 case on_failure_jump_nastyloop
:
4029 case on_failure_jump_smart
:
4035 /* Keep `p1' to allow the `on_failure_jump' we are jumping to
4036 to jump back to "just after here". */
4039 case on_failure_jump
:
4040 case on_failure_keep_string_jump
:
4041 case on_failure_jump_nastyloop
:
4042 case on_failure_jump_loop
:
4043 case on_failure_jump_smart
:
4044 EXTRACT_NUMBER_AND_INCR (j
, p
);
4046 ; /* Backward jump to be ignored. */
4048 { /* We have to look down both arms.
4049 We first go down the "straight" path so as to minimize
4050 stack usage when going through alternatives. */
4051 int r
= analyze_first (p
, pend
, fastmap
, multibyte
);
4059 /* This code simply does not properly handle forward jump_n. */
4060 DEBUG_STATEMENT (EXTRACT_NUMBER (j
, p
); assert (j
< 0));
4062 /* jump_n can either jump or fall through. The (backward) jump
4063 case has already been handled, so we only need to look at the
4064 fallthrough case. */
4068 /* If N == 0, it should be an on_failure_jump_loop instead. */
4069 DEBUG_STATEMENT (EXTRACT_NUMBER (j
, p
+ 2); assert (j
> 0));
4071 /* We only care about one iteration of the loop, so we don't
4072 need to consider the case where this behaves like an
4089 abort (); /* We have listed all the cases. */
4092 /* Getting here means we have found the possible starting
4093 characters for one path of the pattern -- and that the empty
4094 string does not match. We need not follow this path further. */
4098 /* We reached the end without matching anything. */
4101 } /* analyze_first */
4103 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4104 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4105 characters can start a string that matches the pattern. This fastmap
4106 is used by re_search to skip quickly over impossible starting points.
4108 Character codes above (1 << BYTEWIDTH) are not represented in the
4109 fastmap, but the leading codes are represented. Thus, the fastmap
4110 indicates which character sets could start a match.
4112 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4113 area as BUFP->fastmap.
4115 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4118 Returns 0 if we succeed, -2 if an internal error. */
4121 re_compile_fastmap (struct re_pattern_buffer
*bufp
)
4123 char *fastmap
= bufp
->fastmap
;
4126 assert (fastmap
&& bufp
->buffer
);
4128 memset (fastmap
, 0, 1 << BYTEWIDTH
); /* Assume nothing's valid. */
4129 bufp
->fastmap_accurate
= 1; /* It will be when we're done. */
4131 analysis
= analyze_first (bufp
->buffer
, bufp
->buffer
+ bufp
->used
,
4132 fastmap
, RE_MULTIBYTE_P (bufp
));
4133 bufp
->can_be_null
= (analysis
!= 0);
4135 } /* re_compile_fastmap */
4137 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
4138 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
4139 this memory for recording register information. STARTS and ENDS
4140 must be allocated using the malloc library routine, and must each
4141 be at least NUM_REGS * sizeof (regoff_t) bytes long.
4143 If NUM_REGS == 0, then subsequent matches should allocate their own
4146 Unless this function is called, the first search or match using
4147 PATTERN_BUFFER will allocate its own register data, without
4148 freeing the old data. */
4151 re_set_registers (struct re_pattern_buffer
*bufp
, struct re_registers
*regs
, unsigned int num_regs
, regoff_t
*starts
, regoff_t
*ends
)
4155 bufp
->regs_allocated
= REGS_REALLOCATE
;
4156 regs
->num_regs
= num_regs
;
4157 regs
->start
= starts
;
4162 bufp
->regs_allocated
= REGS_UNALLOCATED
;
4164 regs
->start
= regs
->end
= 0;
4167 WEAK_ALIAS (__re_set_registers
, re_set_registers
)
4169 /* Searching routines. */
4171 /* Like re_search_2, below, but only one string is specified, and
4172 doesn't let you say where to stop matching. */
4175 re_search (struct re_pattern_buffer
*bufp
, const char *string
, size_t size
,
4176 ssize_t startpos
, ssize_t range
, struct re_registers
*regs
)
4178 return re_search_2 (bufp
, NULL
, 0, string
, size
, startpos
, range
,
4181 WEAK_ALIAS (__re_search
, re_search
)
4183 /* Head address of virtual concatenation of string. */
4184 #define HEAD_ADDR_VSTRING(P) \
4185 (((P) >= size1 ? string2 : string1))
4187 /* Address of POS in the concatenation of virtual string. */
4188 #define POS_ADDR_VSTRING(POS) \
4189 (((POS) >= size1 ? string2 - size1 : string1) + (POS))
4191 /* Using the compiled pattern in BUFP->buffer, first tries to match the
4192 virtual concatenation of STRING1 and STRING2, starting first at index
4193 STARTPOS, then at STARTPOS + 1, and so on.
4195 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
4197 RANGE is how far to scan while trying to match. RANGE = 0 means try
4198 only at STARTPOS; in general, the last start tried is STARTPOS +
4201 In REGS, return the indices of the virtual concatenation of STRING1
4202 and STRING2 that matched the entire BUFP->buffer and its contained
4205 Do not consider matching one past the index STOP in the virtual
4206 concatenation of STRING1 and STRING2.
4208 We return either the position in the strings at which the match was
4209 found, -1 if no match, or -2 if error (such as failure
4213 re_search_2 (struct re_pattern_buffer
*bufp
, const char *str1
, size_t size1
,
4214 const char *str2
, size_t size2
, ssize_t startpos
, ssize_t range
,
4215 struct re_registers
*regs
, ssize_t stop
)
4218 re_char
*string1
= (re_char
*) str1
;
4219 re_char
*string2
= (re_char
*) str2
;
4220 register char *fastmap
= bufp
->fastmap
;
4221 register RE_TRANSLATE_TYPE translate
= bufp
->translate
;
4222 size_t total_size
= size1
+ size2
;
4223 ssize_t endpos
= startpos
+ range
;
4224 boolean anchored_start
;
4225 /* Nonzero if we are searching multibyte string. */
4226 const boolean multibyte
= RE_TARGET_MULTIBYTE_P (bufp
);
4228 /* Check for out-of-range STARTPOS. */
4229 if (startpos
< 0 || startpos
> total_size
)
4232 /* Fix up RANGE if it might eventually take us outside
4233 the virtual concatenation of STRING1 and STRING2.
4234 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
4236 range
= 0 - startpos
;
4237 else if (endpos
> total_size
)
4238 range
= total_size
- startpos
;
4240 /* If the search isn't to be a backwards one, don't waste time in a
4241 search for a pattern anchored at beginning of buffer. */
4242 if (bufp
->used
> 0 && (re_opcode_t
) bufp
->buffer
[0] == begbuf
&& range
> 0)
4251 /* In a forward search for something that starts with \=.
4252 don't keep searching past point. */
4253 if (bufp
->used
> 0 && (re_opcode_t
) bufp
->buffer
[0] == at_dot
&& range
> 0)
4255 range
= PT_BYTE
- BEGV_BYTE
- startpos
;
4261 /* Update the fastmap now if not correct already. */
4262 if (fastmap
&& !bufp
->fastmap_accurate
)
4263 re_compile_fastmap (bufp
);
4265 /* See whether the pattern is anchored. */
4266 anchored_start
= (bufp
->buffer
[0] == begline
);
4269 gl_state
.object
= re_match_object
; /* Used by SYNTAX_TABLE_BYTE_TO_CHAR. */
4271 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (startpos
));
4273 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object
, charpos
, 1);
4277 /* Loop through the string, looking for a place to start matching. */
4280 /* If the pattern is anchored,
4281 skip quickly past places we cannot match.
4282 We don't bother to treat startpos == 0 specially
4283 because that case doesn't repeat. */
4284 if (anchored_start
&& startpos
> 0)
4286 if (! ((startpos
<= size1
? string1
[startpos
- 1]
4287 : string2
[startpos
- size1
- 1])
4292 /* If a fastmap is supplied, skip quickly over characters that
4293 cannot be the start of a match. If the pattern can match the
4294 null string, however, we don't need to skip characters; we want
4295 the first null string. */
4296 if (fastmap
&& startpos
< total_size
&& !bufp
->can_be_null
)
4298 register re_char
*d
;
4299 register re_wchar_t buf_ch
;
4301 d
= POS_ADDR_VSTRING (startpos
);
4303 if (range
> 0) /* Searching forwards. */
4305 ssize_t irange
= range
, lim
= 0;
4307 if (startpos
< size1
&& startpos
+ range
>= size1
)
4308 lim
= range
- (size1
- startpos
);
4310 /* Written out as an if-else to avoid testing `translate'
4312 if (RE_TRANSLATE_P (translate
))
4319 buf_ch
= STRING_CHAR_AND_LENGTH (d
, buf_charlen
);
4320 buf_ch
= RE_TRANSLATE (translate
, buf_ch
);
4321 if (fastmap
[CHAR_LEADING_CODE (buf_ch
)])
4324 range
-= buf_charlen
;
4330 register re_wchar_t ch
, translated
;
4333 ch
= RE_CHAR_TO_MULTIBYTE (buf_ch
);
4334 translated
= RE_TRANSLATE (translate
, ch
);
4335 if (translated
!= ch
4336 && (ch
= RE_CHAR_TO_UNIBYTE (translated
)) >= 0)
4338 if (fastmap
[buf_ch
])
4351 buf_ch
= STRING_CHAR_AND_LENGTH (d
, buf_charlen
);
4352 if (fastmap
[CHAR_LEADING_CODE (buf_ch
)])
4354 range
-= buf_charlen
;
4358 while (range
> lim
&& !fastmap
[*d
])
4364 startpos
+= irange
- range
;
4366 else /* Searching backwards. */
4370 buf_ch
= STRING_CHAR (d
);
4371 buf_ch
= TRANSLATE (buf_ch
);
4372 if (! fastmap
[CHAR_LEADING_CODE (buf_ch
)])
4377 register re_wchar_t ch
, translated
;
4380 ch
= RE_CHAR_TO_MULTIBYTE (buf_ch
);
4381 translated
= TRANSLATE (ch
);
4382 if (translated
!= ch
4383 && (ch
= RE_CHAR_TO_UNIBYTE (translated
)) >= 0)
4385 if (! fastmap
[TRANSLATE (buf_ch
)])
4391 /* If can't match the null string, and that's all we have left, fail. */
4392 if (range
>= 0 && startpos
== total_size
&& fastmap
4393 && !bufp
->can_be_null
)
4396 val
= re_match_2_internal (bufp
, string1
, size1
, string2
, size2
,
4397 startpos
, regs
, stop
);
4410 /* Update STARTPOS to the next character boundary. */
4413 re_char
*p
= POS_ADDR_VSTRING (startpos
);
4414 int len
= BYTES_BY_CHAR_HEAD (*p
);
4432 /* Update STARTPOS to the previous character boundary. */
4435 re_char
*p
= POS_ADDR_VSTRING (startpos
) + 1;
4437 re_char
*phead
= HEAD_ADDR_VSTRING (startpos
);
4439 /* Find the head of multibyte form. */
4440 PREV_CHAR_BOUNDARY (p
, phead
);
4441 range
+= p0
- 1 - p
;
4445 startpos
-= p0
- 1 - p
;
4451 WEAK_ALIAS (__re_search_2
, re_search_2
)
4453 /* Declarations and macros for re_match_2. */
4455 static int bcmp_translate (re_char
*s1
, re_char
*s2
,
4456 register ssize_t len
,
4457 RE_TRANSLATE_TYPE translate
,
4458 const int multibyte
);
4460 /* This converts PTR, a pointer into one of the search strings `string1'
4461 and `string2' into an offset from the beginning of that string. */
4462 #define POINTER_TO_OFFSET(ptr) \
4463 (FIRST_STRING_P (ptr) \
4465 : (ptr) - string2 + (ptrdiff_t) size1)
4467 /* Call before fetching a character with *d. This switches over to
4468 string2 if necessary.
4469 Check re_match_2_internal for a discussion of why end_match_2 might
4470 not be within string2 (but be equal to end_match_1 instead). */
4471 #define PREFETCH() \
4474 /* End of string2 => fail. */ \
4475 if (dend == end_match_2) \
4477 /* End of string1 => advance to string2. */ \
4479 dend = end_match_2; \
4482 /* Call before fetching a char with *d if you already checked other limits.
4483 This is meant for use in lookahead operations like wordend, etc..
4484 where we might need to look at parts of the string that might be
4485 outside of the LIMITs (i.e past `stop'). */
4486 #define PREFETCH_NOLIMIT() \
4490 dend = end_match_2; \
4493 /* Test if at very beginning or at very end of the virtual concatenation
4494 of `string1' and `string2'. If only one string, it's `string2'. */
4495 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
4496 #define AT_STRINGS_END(d) ((d) == end2)
4498 /* Disabled due to a compiler bug -- see comment at case wordbound */
4500 /* The comment at case wordbound is following one, but we don't use
4501 AT_WORD_BOUNDARY anymore to support multibyte form.
4503 The DEC Alpha C compiler 3.x generates incorrect code for the
4504 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
4505 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
4506 macro and introducing temporary variables works around the bug. */
4509 /* Test if D points to a character which is word-constituent. We have
4510 two special cases to check for: if past the end of string1, look at
4511 the first character in string2; and if before the beginning of
4512 string2, look at the last character in string1. */
4513 #define WORDCHAR_P(d) \
4514 (SYNTAX ((d) == end1 ? *string2 \
4515 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
4518 /* Test if the character before D and the one at D differ with respect
4519 to being word-constituent. */
4520 #define AT_WORD_BOUNDARY(d) \
4521 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
4522 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
4525 /* Free everything we malloc. */
4526 #ifdef MATCH_MAY_ALLOCATE
4527 # define FREE_VAR(var) \
4535 # define FREE_VARIABLES() \
4537 REGEX_FREE_STACK (fail_stack.stack); \
4538 FREE_VAR (regstart); \
4539 FREE_VAR (regend); \
4540 FREE_VAR (best_regstart); \
4541 FREE_VAR (best_regend); \
4542 REGEX_SAFE_FREE (); \
4545 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
4546 #endif /* not MATCH_MAY_ALLOCATE */
4549 /* Optimization routines. */
4551 /* If the operation is a match against one or more chars,
4552 return a pointer to the next operation, else return NULL. */
4554 skip_one_char (const_re_char
*p
)
4567 if (CHARSET_RANGE_TABLE_EXISTS_P (p
- 1))
4570 p
= CHARSET_RANGE_TABLE (p
- 1);
4571 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
4572 p
= CHARSET_RANGE_TABLE_END (p
, mcnt
);
4575 p
+= 1 + CHARSET_BITMAP_SIZE (p
- 1);
4582 case notcategoryspec
:
4594 /* Jump over non-matching operations. */
4596 skip_noops (const_re_char
*p
, const_re_char
*pend
)
4610 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
4621 /* Test if C matches charset op. *PP points to the charset or charset_not
4622 opcode. When the function finishes, *PP will be advanced past that opcode.
4623 C is character to test (possibly after translations) and CORIG is original
4624 character (i.e. without any translations). UNIBYTE denotes whether c is
4625 unibyte or multibyte character. */
4627 execute_charset (const_re_char
**pp
, unsigned c
, unsigned corig
, bool unibyte
)
4629 re_char
*p
= *pp
, *rtp
= NULL
;
4630 bool not = (re_opcode_t
) *p
== charset_not
;
4632 if (CHARSET_RANGE_TABLE_EXISTS_P (p
))
4635 rtp
= CHARSET_RANGE_TABLE (p
);
4636 EXTRACT_NUMBER_AND_INCR (count
, rtp
);
4637 *pp
= CHARSET_RANGE_TABLE_END ((rtp
), (count
));
4640 *pp
+= 2 + CHARSET_BITMAP_SIZE (p
);
4642 if (unibyte
&& c
< (1 << BYTEWIDTH
))
4643 { /* Lookup bitmap. */
4644 /* Cast to `unsigned' instead of `unsigned char' in
4645 case the bit list is a full 32 bytes long. */
4646 if (c
< (unsigned) (CHARSET_BITMAP_SIZE (p
) * BYTEWIDTH
)
4647 && p
[2 + c
/ BYTEWIDTH
] & (1 << (c
% BYTEWIDTH
)))
4653 int class_bits
= CHARSET_RANGE_TABLE_BITS (p
);
4654 re_wchar_t range_start
, range_end
;
4656 /* Sort tests by the most commonly used classes with some adjustment to which
4657 tests are easiest to perform. Take a look at comment in re_wctype_parse
4658 for table with frequencies of character class names. */
4660 if ((class_bits
& BIT_MULTIBYTE
) ||
4661 (class_bits
& BIT_ALNUM
&& ISALNUM (c
)) ||
4662 (class_bits
& BIT_ALPHA
&& ISALPHA (c
)) ||
4663 (class_bits
& BIT_SPACE
&& ISSPACE (c
)) ||
4664 (class_bits
& BIT_BLANK
&& ISBLANK (c
)) ||
4665 (class_bits
& BIT_WORD
&& ISWORD (c
)) ||
4666 ((class_bits
& BIT_UPPER
) &&
4667 (ISUPPER (c
) || (corig
!= c
&&
4668 c
== downcase (corig
) && ISLOWER (c
)))) ||
4669 ((class_bits
& BIT_LOWER
) &&
4670 (ISLOWER (c
) || (corig
!= c
&&
4671 c
== upcase (corig
) && ISUPPER(c
)))) ||
4672 (class_bits
& BIT_PUNCT
&& ISPUNCT (c
)) ||
4673 (class_bits
& BIT_GRAPH
&& ISGRAPH (c
)) ||
4674 (class_bits
& BIT_PRINT
&& ISPRINT (c
)))
4677 for (p
= *pp
; rtp
< p
; rtp
+= 2 * 3)
4679 EXTRACT_CHARACTER (range_start
, rtp
);
4680 EXTRACT_CHARACTER (range_end
, rtp
+ 3);
4681 if (range_start
<= c
&& c
<= range_end
)
4689 /* Non-zero if "p1 matches something" implies "p2 fails". */
4691 mutually_exclusive_p (struct re_pattern_buffer
*bufp
, const_re_char
*p1
,
4695 const boolean multibyte
= RE_MULTIBYTE_P (bufp
);
4696 unsigned char *pend
= bufp
->buffer
+ bufp
->used
;
4698 assert (p1
>= bufp
->buffer
&& p1
< pend
4699 && p2
>= bufp
->buffer
&& p2
<= pend
);
4701 /* Skip over open/close-group commands.
4702 If what follows this loop is a ...+ construct,
4703 look at what begins its body, since we will have to
4704 match at least one of that. */
4705 p2
= skip_noops (p2
, pend
);
4706 /* The same skip can be done for p1, except that this function
4707 is only used in the case where p1 is a simple match operator. */
4708 /* p1 = skip_noops (p1, pend); */
4710 assert (p1
>= bufp
->buffer
&& p1
< pend
4711 && p2
>= bufp
->buffer
&& p2
<= pend
);
4713 op2
= p2
== pend
? succeed
: *p2
;
4719 /* If we're at the end of the pattern, we can change. */
4720 if (skip_one_char (p1
))
4722 DEBUG_PRINT (" End of pattern: fast loop.\n");
4730 register re_wchar_t c
4731 = (re_opcode_t
) *p2
== endline
? '\n'
4732 : RE_STRING_CHAR (p2
+ 2, multibyte
);
4734 if ((re_opcode_t
) *p1
== exactn
)
4736 if (c
!= RE_STRING_CHAR (p1
+ 2, multibyte
))
4738 DEBUG_PRINT (" '%c' != '%c' => fast loop.\n", c
, p1
[2]);
4743 else if ((re_opcode_t
) *p1
== charset
4744 || (re_opcode_t
) *p1
== charset_not
)
4746 if (!execute_charset (&p1
, c
, c
, !multibyte
|| IS_REAL_ASCII (c
)))
4748 DEBUG_PRINT (" No match => fast loop.\n");
4752 else if ((re_opcode_t
) *p1
== anychar
4755 DEBUG_PRINT (" . != \\n => fast loop.\n");
4763 if ((re_opcode_t
) *p1
== exactn
)
4764 /* Reuse the code above. */
4765 return mutually_exclusive_p (bufp
, p2
, p1
);
4767 /* It is hard to list up all the character in charset
4768 P2 if it includes multibyte character. Give up in
4770 else if (!multibyte
|| !CHARSET_RANGE_TABLE_EXISTS_P (p2
))
4772 /* Now, we are sure that P2 has no range table.
4773 So, for the size of bitmap in P2, `p2[1]' is
4774 enough. But P1 may have range table, so the
4775 size of bitmap table of P1 is extracted by
4776 using macro `CHARSET_BITMAP_SIZE'.
4778 In a multibyte case, we know that all the character
4779 listed in P2 is ASCII. In a unibyte case, P1 has only a
4780 bitmap table. So, in both cases, it is enough to test
4781 only the bitmap table of P1. */
4783 if ((re_opcode_t
) *p1
== charset
)
4786 /* We win if the charset inside the loop
4787 has no overlap with the one after the loop. */
4790 && idx
< CHARSET_BITMAP_SIZE (p1
));
4792 if ((p2
[2 + idx
] & p1
[2 + idx
]) != 0)
4796 || idx
== CHARSET_BITMAP_SIZE (p1
))
4798 DEBUG_PRINT (" No match => fast loop.\n");
4802 else if ((re_opcode_t
) *p1
== charset_not
)
4805 /* We win if the charset_not inside the loop lists
4806 every character listed in the charset after. */
4807 for (idx
= 0; idx
< (int) p2
[1]; idx
++)
4808 if (! (p2
[2 + idx
] == 0
4809 || (idx
< CHARSET_BITMAP_SIZE (p1
)
4810 && ((p2
[2 + idx
] & ~ p1
[2 + idx
]) == 0))))
4815 DEBUG_PRINT (" No match => fast loop.\n");
4828 /* Reuse the code above. */
4829 return mutually_exclusive_p (bufp
, p2
, p1
);
4831 /* When we have two charset_not, it's very unlikely that
4832 they don't overlap. The union of the two sets of excluded
4833 chars should cover all possible chars, which, as a matter of
4834 fact, is virtually impossible in multibyte buffers. */
4840 return ((re_opcode_t
) *p1
== syntaxspec
&& p1
[1] == Sword
);
4842 return ((re_opcode_t
) *p1
== syntaxspec
4843 && (p1
[1] == Ssymbol
|| p1
[1] == Sword
));
4845 return ((re_opcode_t
) *p1
== syntaxspec
&& p1
[1] == p2
[1]);
4848 return ((re_opcode_t
) *p1
== notsyntaxspec
&& p1
[1] == Sword
);
4850 return ((re_opcode_t
) *p1
== notsyntaxspec
4851 && (p1
[1] == Ssymbol
|| p1
[1] == Sword
));
4853 return ((re_opcode_t
) *p1
== notsyntaxspec
&& p1
[1] == p2
[1]);
4856 return (((re_opcode_t
) *p1
== notsyntaxspec
4857 || (re_opcode_t
) *p1
== syntaxspec
)
4862 return ((re_opcode_t
) *p1
== notcategoryspec
&& p1
[1] == p2
[1]);
4863 case notcategoryspec
:
4864 return ((re_opcode_t
) *p1
== categoryspec
&& p1
[1] == p2
[1]);
4876 /* Matching routines. */
4878 #ifndef emacs /* Emacs never uses this. */
4879 /* re_match is like re_match_2 except it takes only a single string. */
4882 re_match (struct re_pattern_buffer
*bufp
, const char *string
,
4883 size_t size
, ssize_t pos
, struct re_registers
*regs
)
4885 regoff_t result
= re_match_2_internal (bufp
, NULL
, 0, (re_char
*) string
,
4886 size
, pos
, regs
, size
);
4889 WEAK_ALIAS (__re_match
, re_match
)
4890 #endif /* not emacs */
4892 /* re_match_2 matches the compiled pattern in BUFP against the
4893 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
4894 and SIZE2, respectively). We start matching at POS, and stop
4897 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
4898 store offsets for the substring each group matched in REGS. See the
4899 documentation for exactly how many groups we fill.
4901 We return -1 if no match, -2 if an internal error (such as the
4902 failure stack overflowing). Otherwise, we return the length of the
4903 matched substring. */
4906 re_match_2 (struct re_pattern_buffer
*bufp
, const char *string1
,
4907 size_t size1
, const char *string2
, size_t size2
, ssize_t pos
,
4908 struct re_registers
*regs
, ssize_t stop
)
4914 gl_state
.object
= re_match_object
; /* Used by SYNTAX_TABLE_BYTE_TO_CHAR. */
4915 charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (pos
));
4916 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object
, charpos
, 1);
4919 result
= re_match_2_internal (bufp
, (re_char
*) string1
, size1
,
4920 (re_char
*) string2
, size2
,
4924 WEAK_ALIAS (__re_match_2
, re_match_2
)
4927 /* This is a separate function so that we can force an alloca cleanup
4930 re_match_2_internal (struct re_pattern_buffer
*bufp
, const_re_char
*string1
,
4931 size_t size1
, const_re_char
*string2
, size_t size2
,
4932 ssize_t pos
, struct re_registers
*regs
, ssize_t stop
)
4934 /* General temporaries. */
4938 /* Just past the end of the corresponding string. */
4939 re_char
*end1
, *end2
;
4941 /* Pointers into string1 and string2, just past the last characters in
4942 each to consider matching. */
4943 re_char
*end_match_1
, *end_match_2
;
4945 /* Where we are in the data, and the end of the current string. */
4948 /* Used sometimes to remember where we were before starting matching
4949 an operator so that we can go back in case of failure. This "atomic"
4950 behavior of matching opcodes is indispensable to the correctness
4951 of the on_failure_keep_string_jump optimization. */
4954 /* Where we are in the pattern, and the end of the pattern. */
4955 re_char
*p
= bufp
->buffer
;
4956 re_char
*pend
= p
+ bufp
->used
;
4958 /* We use this to map every character in the string. */
4959 RE_TRANSLATE_TYPE translate
= bufp
->translate
;
4961 /* Nonzero if BUFP is setup from a multibyte regex. */
4962 const boolean multibyte
= RE_MULTIBYTE_P (bufp
);
4964 /* Nonzero if STRING1/STRING2 are multibyte. */
4965 const boolean target_multibyte
= RE_TARGET_MULTIBYTE_P (bufp
);
4967 /* Failure point stack. Each place that can handle a failure further
4968 down the line pushes a failure point on this stack. It consists of
4969 regstart, and regend for all registers corresponding to
4970 the subexpressions we're currently inside, plus the number of such
4971 registers, and, finally, two char *'s. The first char * is where
4972 to resume scanning the pattern; the second one is where to resume
4973 scanning the strings. */
4974 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
4975 fail_stack_type fail_stack
;
4977 #ifdef DEBUG_COMPILES_ARGUMENTS
4978 unsigned nfailure_points_pushed
= 0, nfailure_points_popped
= 0;
4981 #if defined REL_ALLOC && defined REGEX_MALLOC
4982 /* This holds the pointer to the failure stack, when
4983 it is allocated relocatably. */
4984 fail_stack_elt_t
*failure_stack_ptr
;
4987 /* We fill all the registers internally, independent of what we
4988 return, for use in backreferences. The number here includes
4989 an element for register zero. */
4990 size_t num_regs
= bufp
->re_nsub
+ 1;
4992 /* Information on the contents of registers. These are pointers into
4993 the input strings; they record just what was matched (on this
4994 attempt) by a subexpression part of the pattern, that is, the
4995 regnum-th regstart pointer points to where in the pattern we began
4996 matching and the regnum-th regend points to right after where we
4997 stopped matching the regnum-th subexpression. (The zeroth register
4998 keeps track of what the whole pattern matches.) */
4999 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5000 re_char
**regstart
, **regend
;
5003 /* The following record the register info as found in the above
5004 variables when we find a match better than any we've seen before.
5005 This happens as we backtrack through the failure points, which in
5006 turn happens only if we have not yet matched the entire string. */
5007 unsigned best_regs_set
= false;
5008 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5009 re_char
**best_regstart
, **best_regend
;
5012 /* Logically, this is `best_regend[0]'. But we don't want to have to
5013 allocate space for that if we're not allocating space for anything
5014 else (see below). Also, we never need info about register 0 for
5015 any of the other register vectors, and it seems rather a kludge to
5016 treat `best_regend' differently than the rest. So we keep track of
5017 the end of the best match so far in a separate variable. We
5018 initialize this to NULL so that when we backtrack the first time
5019 and need to test it, it's not garbage. */
5020 re_char
*match_end
= NULL
;
5022 #ifdef DEBUG_COMPILES_ARGUMENTS
5023 /* Counts the total number of registers pushed. */
5024 unsigned num_regs_pushed
= 0;
5027 DEBUG_PRINT ("\n\nEntering re_match_2.\n");
5029 REGEX_USE_SAFE_ALLOCA
;
5033 #ifdef MATCH_MAY_ALLOCATE
5034 /* Do not bother to initialize all the register variables if there are
5035 no groups in the pattern, as it takes a fair amount of time. If
5036 there are groups, we include space for register 0 (the whole
5037 pattern), even though we never use it, since it simplifies the
5038 array indexing. We should fix this. */
5041 regstart
= REGEX_TALLOC (num_regs
, re_char
*);
5042 regend
= REGEX_TALLOC (num_regs
, re_char
*);
5043 best_regstart
= REGEX_TALLOC (num_regs
, re_char
*);
5044 best_regend
= REGEX_TALLOC (num_regs
, re_char
*);
5046 if (!(regstart
&& regend
&& best_regstart
&& best_regend
))
5054 /* We must initialize all our variables to NULL, so that
5055 `FREE_VARIABLES' doesn't try to free them. */
5056 regstart
= regend
= best_regstart
= best_regend
= NULL
;
5058 #endif /* MATCH_MAY_ALLOCATE */
5060 /* The starting position is bogus. */
5061 if (pos
< 0 || pos
> size1
+ size2
)
5067 /* Initialize subexpression text positions to -1 to mark ones that no
5068 start_memory/stop_memory has been seen for. Also initialize the
5069 register information struct. */
5070 for (reg
= 1; reg
< num_regs
; reg
++)
5071 regstart
[reg
] = regend
[reg
] = NULL
;
5073 /* We move `string1' into `string2' if the latter's empty -- but not if
5074 `string1' is null. */
5075 if (size2
== 0 && string1
!= NULL
)
5082 end1
= string1
+ size1
;
5083 end2
= string2
+ size2
;
5085 /* `p' scans through the pattern as `d' scans through the data.
5086 `dend' is the end of the input string that `d' points within. `d'
5087 is advanced into the following input string whenever necessary, but
5088 this happens before fetching; therefore, at the beginning of the
5089 loop, `d' can be pointing at the end of a string, but it cannot
5093 /* Only match within string2. */
5094 d
= string2
+ pos
- size1
;
5095 dend
= end_match_2
= string2
+ stop
- size1
;
5096 end_match_1
= end1
; /* Just to give it a value. */
5102 /* Only match within string1. */
5103 end_match_1
= string1
+ stop
;
5105 When we reach end_match_1, PREFETCH normally switches to string2.
5106 But in the present case, this means that just doing a PREFETCH
5107 makes us jump from `stop' to `gap' within the string.
5108 What we really want here is for the search to stop as
5109 soon as we hit end_match_1. That's why we set end_match_2
5110 to end_match_1 (since PREFETCH fails as soon as we hit
5112 end_match_2
= end_match_1
;
5115 { /* It's important to use this code when stop == size so that
5116 moving `d' from end1 to string2 will not prevent the d == dend
5117 check from catching the end of string. */
5119 end_match_2
= string2
+ stop
- size1
;
5125 DEBUG_PRINT ("The compiled pattern is: ");
5126 DEBUG_PRINT_COMPILED_PATTERN (bufp
, p
, pend
);
5127 DEBUG_PRINT ("The string to match is: \"");
5128 DEBUG_PRINT_DOUBLE_STRING (d
, string1
, size1
, string2
, size2
);
5129 DEBUG_PRINT ("\"\n");
5131 /* This loops over pattern commands. It exits by returning from the
5132 function if the match is complete, or it drops through if the match
5133 fails at this starting point in the input data. */
5136 DEBUG_PRINT ("\n%p: ", p
);
5140 /* End of pattern means we might have succeeded. */
5141 DEBUG_PRINT ("end of pattern ... ");
5143 /* If we haven't matched the entire string, and we want the
5144 longest match, try backtracking. */
5145 if (d
!= end_match_2
)
5147 /* True if this match is the best seen so far. */
5151 /* True if this match ends in the same string (string1
5152 or string2) as the best previous match. */
5153 bool same_str_p
= (FIRST_STRING_P (match_end
)
5154 == FIRST_STRING_P (d
));
5156 /* AIX compiler got confused when this was combined
5157 with the previous declaration. */
5159 best_match_p
= d
> match_end
;
5161 best_match_p
= !FIRST_STRING_P (d
);
5164 DEBUG_PRINT ("backtracking.\n");
5166 if (!FAIL_STACK_EMPTY ())
5167 { /* More failure points to try. */
5169 /* If exceeds best match so far, save it. */
5170 if (!best_regs_set
|| best_match_p
)
5172 best_regs_set
= true;
5175 DEBUG_PRINT ("\nSAVING match as best so far.\n");
5177 for (reg
= 1; reg
< num_regs
; reg
++)
5179 best_regstart
[reg
] = regstart
[reg
];
5180 best_regend
[reg
] = regend
[reg
];
5186 /* If no failure points, don't restore garbage. And if
5187 last match is real best match, don't restore second
5189 else if (best_regs_set
&& !best_match_p
)
5192 /* Restore best match. It may happen that `dend ==
5193 end_match_1' while the restored d is in string2.
5194 For example, the pattern `x.*y.*z' against the
5195 strings `x-' and `y-z-', if the two strings are
5196 not consecutive in memory. */
5197 DEBUG_PRINT ("Restoring best registers.\n");
5200 dend
= ((d
>= string1
&& d
<= end1
)
5201 ? end_match_1
: end_match_2
);
5203 for (reg
= 1; reg
< num_regs
; reg
++)
5205 regstart
[reg
] = best_regstart
[reg
];
5206 regend
[reg
] = best_regend
[reg
];
5209 } /* d != end_match_2 */
5212 DEBUG_PRINT ("Accepting match.\n");
5214 /* If caller wants register contents data back, do it. */
5215 if (regs
&& !bufp
->no_sub
)
5217 /* Have the register data arrays been allocated? */
5218 if (bufp
->regs_allocated
== REGS_UNALLOCATED
)
5219 { /* No. So allocate them with malloc. We need one
5220 extra element beyond `num_regs' for the `-1' marker
5222 regs
->num_regs
= max (RE_NREGS
, num_regs
+ 1);
5223 regs
->start
= TALLOC (regs
->num_regs
, regoff_t
);
5224 regs
->end
= TALLOC (regs
->num_regs
, regoff_t
);
5225 if (regs
->start
== NULL
|| regs
->end
== NULL
)
5230 bufp
->regs_allocated
= REGS_REALLOCATE
;
5232 else if (bufp
->regs_allocated
== REGS_REALLOCATE
)
5233 { /* Yes. If we need more elements than were already
5234 allocated, reallocate them. If we need fewer, just
5236 if (regs
->num_regs
< num_regs
+ 1)
5238 regs
->num_regs
= num_regs
+ 1;
5239 RETALLOC (regs
->start
, regs
->num_regs
, regoff_t
);
5240 RETALLOC (regs
->end
, regs
->num_regs
, regoff_t
);
5241 if (regs
->start
== NULL
|| regs
->end
== NULL
)
5250 /* These braces fend off a "empty body in an else-statement"
5251 warning under GCC when assert expands to nothing. */
5252 assert (bufp
->regs_allocated
== REGS_FIXED
);
5255 /* Convert the pointer data in `regstart' and `regend' to
5256 indices. Register zero has to be set differently,
5257 since we haven't kept track of any info for it. */
5258 if (regs
->num_regs
> 0)
5260 regs
->start
[0] = pos
;
5261 regs
->end
[0] = POINTER_TO_OFFSET (d
);
5264 /* Go through the first `min (num_regs, regs->num_regs)'
5265 registers, since that is all we initialized. */
5266 for (reg
= 1; reg
< min (num_regs
, regs
->num_regs
); reg
++)
5268 if (REG_UNSET (regstart
[reg
]) || REG_UNSET (regend
[reg
]))
5269 regs
->start
[reg
] = regs
->end
[reg
] = -1;
5272 regs
->start
[reg
] = POINTER_TO_OFFSET (regstart
[reg
]);
5273 regs
->end
[reg
] = POINTER_TO_OFFSET (regend
[reg
]);
5277 /* If the regs structure we return has more elements than
5278 were in the pattern, set the extra elements to -1. If
5279 we (re)allocated the registers, this is the case,
5280 because we always allocate enough to have at least one
5282 for (reg
= num_regs
; reg
< regs
->num_regs
; reg
++)
5283 regs
->start
[reg
] = regs
->end
[reg
] = -1;
5284 } /* regs && !bufp->no_sub */
5286 DEBUG_PRINT ("%u failure points pushed, %u popped (%u remain).\n",
5287 nfailure_points_pushed
, nfailure_points_popped
,
5288 nfailure_points_pushed
- nfailure_points_popped
);
5289 DEBUG_PRINT ("%u registers pushed.\n", num_regs_pushed
);
5291 ptrdiff_t dcnt
= POINTER_TO_OFFSET (d
) - pos
;
5293 DEBUG_PRINT ("Returning %td from re_match_2.\n", dcnt
);
5299 /* Otherwise match next pattern command. */
5302 /* Ignore these. Used to ignore the n of succeed_n's which
5303 currently have n == 0. */
5305 DEBUG_PRINT ("EXECUTING no_op.\n");
5309 DEBUG_PRINT ("EXECUTING succeed.\n");
5312 /* Match the next n pattern characters exactly. The following
5313 byte in the pattern defines n, and the n bytes after that
5314 are the characters to match. */
5317 DEBUG_PRINT ("EXECUTING exactn %d.\n", mcnt
);
5319 /* Remember the start point to rollback upon failure. */
5323 /* This is written out as an if-else so we don't waste time
5324 testing `translate' inside the loop. */
5325 if (RE_TRANSLATE_P (translate
))
5329 if (RE_TRANSLATE (translate
, *d
) != *p
++)
5349 /* The cost of testing `translate' is comparatively small. */
5350 if (target_multibyte
)
5353 int pat_charlen
, buf_charlen
;
5358 pat_ch
= STRING_CHAR_AND_LENGTH (p
, pat_charlen
);
5361 pat_ch
= RE_CHAR_TO_MULTIBYTE (*p
);
5364 buf_ch
= STRING_CHAR_AND_LENGTH (d
, buf_charlen
);
5366 if (TRANSLATE (buf_ch
) != pat_ch
)
5374 mcnt
-= pat_charlen
;
5386 pat_ch
= STRING_CHAR_AND_LENGTH (p
, pat_charlen
);
5387 pat_ch
= RE_CHAR_TO_UNIBYTE (pat_ch
);
5394 buf_ch
= RE_CHAR_TO_MULTIBYTE (*d
);
5395 if (! CHAR_BYTE8_P (buf_ch
))
5397 buf_ch
= TRANSLATE (buf_ch
);
5398 buf_ch
= RE_CHAR_TO_UNIBYTE (buf_ch
);
5404 if (buf_ch
!= pat_ch
)
5417 /* Match any character except possibly a newline or a null. */
5422 reg_syntax_t syntax
;
5424 DEBUG_PRINT ("EXECUTING anychar.\n");
5427 buf_ch
= RE_STRING_CHAR_AND_LENGTH (d
, buf_charlen
,
5429 buf_ch
= TRANSLATE (buf_ch
);
5432 syntax
= RE_SYNTAX_EMACS
;
5434 syntax
= bufp
->syntax
;
5437 if ((!(syntax
& RE_DOT_NEWLINE
) && buf_ch
== '\n')
5438 || ((syntax
& RE_DOT_NOT_NULL
) && buf_ch
== '\000'))
5441 DEBUG_PRINT (" Matched \"%d\".\n", *d
);
5450 register unsigned int c
, corig
;
5453 /* Whether matching against a unibyte character. */
5454 boolean unibyte_char
= false;
5456 DEBUG_PRINT ("EXECUTING charset%s.\n",
5457 (re_opcode_t
) *(p
- 1) == charset_not
? "_not" : "");
5460 corig
= c
= RE_STRING_CHAR_AND_LENGTH (d
, len
, target_multibyte
);
5461 if (target_multibyte
)
5466 c1
= RE_CHAR_TO_UNIBYTE (c
);
5469 unibyte_char
= true;
5475 int c1
= RE_CHAR_TO_MULTIBYTE (c
);
5477 if (! CHAR_BYTE8_P (c1
))
5479 c1
= TRANSLATE (c1
);
5480 c1
= RE_CHAR_TO_UNIBYTE (c1
);
5483 unibyte_char
= true;
5488 unibyte_char
= true;
5492 if (!execute_charset (&p
, c
, corig
, unibyte_char
))
5500 /* The beginning of a group is represented by start_memory.
5501 The argument is the register number. The text
5502 matched within the group is recorded (in the internal
5503 registers data structure) under the register number. */
5505 DEBUG_PRINT ("EXECUTING start_memory %d:\n", *p
);
5507 /* In case we need to undo this operation (via backtracking). */
5508 PUSH_FAILURE_REG (*p
);
5511 regend
[*p
] = NULL
; /* probably unnecessary. -sm */
5512 DEBUG_PRINT (" regstart: %td\n", POINTER_TO_OFFSET (regstart
[*p
]));
5514 /* Move past the register number and inner group count. */
5519 /* The stop_memory opcode represents the end of a group. Its
5520 argument is the same as start_memory's: the register number. */
5522 DEBUG_PRINT ("EXECUTING stop_memory %d:\n", *p
);
5524 assert (!REG_UNSET (regstart
[*p
]));
5525 /* Strictly speaking, there should be code such as:
5527 assert (REG_UNSET (regend[*p]));
5528 PUSH_FAILURE_REGSTOP ((unsigned int)*p);
5530 But the only info to be pushed is regend[*p] and it is known to
5531 be UNSET, so there really isn't anything to push.
5532 Not pushing anything, on the other hand deprives us from the
5533 guarantee that regend[*p] is UNSET since undoing this operation
5534 will not reset its value properly. This is not important since
5535 the value will only be read on the next start_memory or at
5536 the very end and both events can only happen if this stop_memory
5540 DEBUG_PRINT (" regend: %td\n", POINTER_TO_OFFSET (regend
[*p
]));
5542 /* Move past the register number and the inner group count. */
5547 /* \<digit> has been turned into a `duplicate' command which is
5548 followed by the numeric value of <digit> as the register number. */
5551 register re_char
*d2
, *dend2
;
5552 int regno
= *p
++; /* Get which register to match against. */
5553 DEBUG_PRINT ("EXECUTING duplicate %d.\n", regno
);
5555 /* Can't back reference a group which we've never matched. */
5556 if (REG_UNSET (regstart
[regno
]) || REG_UNSET (regend
[regno
]))
5559 /* Where in input to try to start matching. */
5560 d2
= regstart
[regno
];
5562 /* Remember the start point to rollback upon failure. */
5565 /* Where to stop matching; if both the place to start and
5566 the place to stop matching are in the same string, then
5567 set to the place to stop, otherwise, for now have to use
5568 the end of the first string. */
5570 dend2
= ((FIRST_STRING_P (regstart
[regno
])
5571 == FIRST_STRING_P (regend
[regno
]))
5572 ? regend
[regno
] : end_match_1
);
5577 /* If necessary, advance to next segment in register
5581 if (dend2
== end_match_2
) break;
5582 if (dend2
== regend
[regno
]) break;
5584 /* End of string1 => advance to string2. */
5586 dend2
= regend
[regno
];
5588 /* At end of register contents => success */
5589 if (d2
== dend2
) break;
5591 /* If necessary, advance to next segment in data. */
5594 /* How many characters left in this segment to match. */
5597 /* Want how many consecutive characters we can match in
5598 one shot, so, if necessary, adjust the count. */
5599 if (dcnt
> dend2
- d2
)
5602 /* Compare that many; failure if mismatch, else move
5604 if (RE_TRANSLATE_P (translate
)
5605 ? bcmp_translate (d
, d2
, dcnt
, translate
, target_multibyte
)
5606 : memcmp (d
, d2
, dcnt
))
5611 d
+= dcnt
, d2
+= dcnt
;
5617 /* begline matches the empty string at the beginning of the string
5618 (unless `not_bol' is set in `bufp'), and after newlines. */
5620 DEBUG_PRINT ("EXECUTING begline.\n");
5622 if (AT_STRINGS_BEG (d
))
5624 if (!bufp
->not_bol
) break;
5629 GET_CHAR_BEFORE_2 (c
, d
, string1
, end1
, string2
, end2
);
5633 /* In all other cases, we fail. */
5637 /* endline is the dual of begline. */
5639 DEBUG_PRINT ("EXECUTING endline.\n");
5641 if (AT_STRINGS_END (d
))
5643 if (!bufp
->not_eol
) break;
5647 PREFETCH_NOLIMIT ();
5654 /* Match at the very beginning of the data. */
5656 DEBUG_PRINT ("EXECUTING begbuf.\n");
5657 if (AT_STRINGS_BEG (d
))
5662 /* Match at the very end of the data. */
5664 DEBUG_PRINT ("EXECUTING endbuf.\n");
5665 if (AT_STRINGS_END (d
))
5670 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
5671 pushes NULL as the value for the string on the stack. Then
5672 `POP_FAILURE_POINT' will keep the current value for the
5673 string, instead of restoring it. To see why, consider
5674 matching `foo\nbar' against `.*\n'. The .* matches the foo;
5675 then the . fails against the \n. But the next thing we want
5676 to do is match the \n against the \n; if we restored the
5677 string value, we would be back at the foo.
5679 Because this is used only in specific cases, we don't need to
5680 check all the things that `on_failure_jump' does, to make
5681 sure the right things get saved on the stack. Hence we don't
5682 share its code. The only reason to push anything on the
5683 stack at all is that otherwise we would have to change
5684 `anychar's code to do something besides goto fail in this
5685 case; that seems worse than this. */
5686 case on_failure_keep_string_jump
:
5687 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5688 DEBUG_PRINT ("EXECUTING on_failure_keep_string_jump %d (to %p):\n",
5691 PUSH_FAILURE_POINT (p
- 3, NULL
);
5694 /* A nasty loop is introduced by the non-greedy *? and +?.
5695 With such loops, the stack only ever contains one failure point
5696 at a time, so that a plain on_failure_jump_loop kind of
5697 cycle detection cannot work. Worse yet, such a detection
5698 can not only fail to detect a cycle, but it can also wrongly
5699 detect a cycle (between different instantiations of the same
5701 So the method used for those nasty loops is a little different:
5702 We use a special cycle-detection-stack-frame which is pushed
5703 when the on_failure_jump_nastyloop failure-point is *popped*.
5704 This special frame thus marks the beginning of one iteration
5705 through the loop and we can hence easily check right here
5706 whether something matched between the beginning and the end of
5708 case on_failure_jump_nastyloop
:
5709 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5710 DEBUG_PRINT ("EXECUTING on_failure_jump_nastyloop %d (to %p):\n",
5713 assert ((re_opcode_t
)p
[-4] == no_op
);
5716 CHECK_INFINITE_LOOP (p
- 4, d
);
5718 /* If there's a cycle, just continue without pushing
5719 this failure point. The failure point is the "try again"
5720 option, which shouldn't be tried.
5721 We want (x?)*?y\1z to match both xxyz and xxyxz. */
5722 PUSH_FAILURE_POINT (p
- 3, d
);
5726 /* Simple loop detecting on_failure_jump: just check on the
5727 failure stack if the same spot was already hit earlier. */
5728 case on_failure_jump_loop
:
5730 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5731 DEBUG_PRINT ("EXECUTING on_failure_jump_loop %d (to %p):\n",
5735 CHECK_INFINITE_LOOP (p
- 3, d
);
5737 /* If there's a cycle, get out of the loop, as if the matching
5738 had failed. We used to just `goto fail' here, but that was
5739 aborting the search a bit too early: we want to keep the
5740 empty-loop-match and keep matching after the loop.
5741 We want (x?)*y\1z to match both xxyz and xxyxz. */
5744 PUSH_FAILURE_POINT (p
- 3, d
);
5749 /* Uses of on_failure_jump:
5751 Each alternative starts with an on_failure_jump that points
5752 to the beginning of the next alternative. Each alternative
5753 except the last ends with a jump that in effect jumps past
5754 the rest of the alternatives. (They really jump to the
5755 ending jump of the following alternative, because tensioning
5756 these jumps is a hassle.)
5758 Repeats start with an on_failure_jump that points past both
5759 the repetition text and either the following jump or
5760 pop_failure_jump back to this on_failure_jump. */
5761 case on_failure_jump
:
5762 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5763 DEBUG_PRINT ("EXECUTING on_failure_jump %d (to %p):\n",
5766 PUSH_FAILURE_POINT (p
-3, d
);
5769 /* This operation is used for greedy *.
5770 Compare the beginning of the repeat with what in the
5771 pattern follows its end. If we can establish that there
5772 is nothing that they would both match, i.e., that we
5773 would have to backtrack because of (as in, e.g., `a*a')
5774 then we can use a non-backtracking loop based on
5775 on_failure_keep_string_jump instead of on_failure_jump. */
5776 case on_failure_jump_smart
:
5777 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5778 DEBUG_PRINT ("EXECUTING on_failure_jump_smart %d (to %p).\n",
5781 re_char
*p1
= p
; /* Next operation. */
5782 /* Here, we discard `const', making re_match non-reentrant. */
5783 unsigned char *p2
= (unsigned char*) p
+ mcnt
; /* Jump dest. */
5784 unsigned char *p3
= (unsigned char*) p
- 3; /* opcode location. */
5786 p
-= 3; /* Reset so that we will re-execute the
5787 instruction once it's been changed. */
5789 EXTRACT_NUMBER (mcnt
, p2
- 2);
5791 /* Ensure this is a indeed the trivial kind of loop
5792 we are expecting. */
5793 assert (skip_one_char (p1
) == p2
- 3);
5794 assert ((re_opcode_t
) p2
[-3] == jump
&& p2
+ mcnt
== p
);
5795 DEBUG_STATEMENT (debug
+= 2);
5796 if (mutually_exclusive_p (bufp
, p1
, p2
))
5798 /* Use a fast `on_failure_keep_string_jump' loop. */
5799 DEBUG_PRINT (" smart exclusive => fast loop.\n");
5800 *p3
= (unsigned char) on_failure_keep_string_jump
;
5801 STORE_NUMBER (p2
- 2, mcnt
+ 3);
5805 /* Default to a safe `on_failure_jump' loop. */
5806 DEBUG_PRINT (" smart default => slow loop.\n");
5807 *p3
= (unsigned char) on_failure_jump
;
5809 DEBUG_STATEMENT (debug
-= 2);
5813 /* Unconditionally jump (without popping any failure points). */
5816 IMMEDIATE_QUIT_CHECK
;
5817 EXTRACT_NUMBER_AND_INCR (mcnt
, p
); /* Get the amount to jump. */
5818 DEBUG_PRINT ("EXECUTING jump %d ", mcnt
);
5819 p
+= mcnt
; /* Do the jump. */
5820 DEBUG_PRINT ("(to %p).\n", p
);
5824 /* Have to succeed matching what follows at least n times.
5825 After that, handle like `on_failure_jump'. */
5827 /* Signedness doesn't matter since we only compare MCNT to 0. */
5828 EXTRACT_NUMBER (mcnt
, p
+ 2);
5829 DEBUG_PRINT ("EXECUTING succeed_n %d.\n", mcnt
);
5831 /* Originally, mcnt is how many times we HAVE to succeed. */
5834 /* Here, we discard `const', making re_match non-reentrant. */
5835 unsigned char *p2
= (unsigned char*) p
+ 2; /* counter loc. */
5838 PUSH_NUMBER (p2
, mcnt
);
5841 /* The two bytes encoding mcnt == 0 are two no_op opcodes. */
5846 /* Signedness doesn't matter since we only compare MCNT to 0. */
5847 EXTRACT_NUMBER (mcnt
, p
+ 2);
5848 DEBUG_PRINT ("EXECUTING jump_n %d.\n", mcnt
);
5850 /* Originally, this is how many times we CAN jump. */
5853 /* Here, we discard `const', making re_match non-reentrant. */
5854 unsigned char *p2
= (unsigned char*) p
+ 2; /* counter loc. */
5856 PUSH_NUMBER (p2
, mcnt
);
5857 goto unconditional_jump
;
5859 /* If don't have to jump any more, skip over the rest of command. */
5866 unsigned char *p2
; /* Location of the counter. */
5867 DEBUG_PRINT ("EXECUTING set_number_at.\n");
5869 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5870 /* Here, we discard `const', making re_match non-reentrant. */
5871 p2
= (unsigned char*) p
+ mcnt
;
5872 /* Signedness doesn't matter since we only copy MCNT's bits. */
5873 EXTRACT_NUMBER_AND_INCR (mcnt
, p
);
5874 DEBUG_PRINT (" Setting %p to %d.\n", p2
, mcnt
);
5875 PUSH_NUMBER (p2
, mcnt
);
5882 boolean
not = (re_opcode_t
) *(p
- 1) == notwordbound
;
5883 DEBUG_PRINT ("EXECUTING %swordbound.\n", not ? "not" : "");
5885 /* We SUCCEED (or FAIL) in one of the following cases: */
5887 /* Case 1: D is at the beginning or the end of string. */
5888 if (AT_STRINGS_BEG (d
) || AT_STRINGS_END (d
))
5892 /* C1 is the character before D, S1 is the syntax of C1, C2
5893 is the character at D, and S2 is the syntax of C2. */
5898 ssize_t offset
= PTR_TO_OFFSET (d
- 1);
5899 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
5900 UPDATE_SYNTAX_TABLE_FAST (charpos
);
5902 GET_CHAR_BEFORE_2 (c1
, d
, string1
, end1
, string2
, end2
);
5905 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos
+ 1);
5907 PREFETCH_NOLIMIT ();
5908 GET_CHAR_AFTER (c2
, d
, dummy
);
5911 if (/* Case 2: Only one of S1 and S2 is Sword. */
5912 ((s1
== Sword
) != (s2
== Sword
))
5913 /* Case 3: Both of S1 and S2 are Sword, and macro
5914 WORD_BOUNDARY_P (C1, C2) returns nonzero. */
5915 || ((s1
== Sword
) && WORD_BOUNDARY_P (c1
, c2
)))
5925 DEBUG_PRINT ("EXECUTING wordbeg.\n");
5927 /* We FAIL in one of the following cases: */
5929 /* Case 1: D is at the end of string. */
5930 if (AT_STRINGS_END (d
))
5934 /* C1 is the character before D, S1 is the syntax of C1, C2
5935 is the character at D, and S2 is the syntax of C2. */
5940 ssize_t offset
= PTR_TO_OFFSET (d
);
5941 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
5942 UPDATE_SYNTAX_TABLE_FAST (charpos
);
5945 GET_CHAR_AFTER (c2
, d
, dummy
);
5948 /* Case 2: S2 is not Sword. */
5952 /* Case 3: D is not at the beginning of string ... */
5953 if (!AT_STRINGS_BEG (d
))
5955 GET_CHAR_BEFORE_2 (c1
, d
, string1
, end1
, string2
, end2
);
5957 UPDATE_SYNTAX_TABLE_BACKWARD (charpos
- 1);
5961 /* ... and S1 is Sword, and WORD_BOUNDARY_P (C1, C2)
5963 if ((s1
== Sword
) && !WORD_BOUNDARY_P (c1
, c2
))
5970 DEBUG_PRINT ("EXECUTING wordend.\n");
5972 /* We FAIL in one of the following cases: */
5974 /* Case 1: D is at the beginning of string. */
5975 if (AT_STRINGS_BEG (d
))
5979 /* C1 is the character before D, S1 is the syntax of C1, C2
5980 is the character at D, and S2 is the syntax of C2. */
5985 ssize_t offset
= PTR_TO_OFFSET (d
) - 1;
5986 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
5987 UPDATE_SYNTAX_TABLE_FAST (charpos
);
5989 GET_CHAR_BEFORE_2 (c1
, d
, string1
, end1
, string2
, end2
);
5992 /* Case 2: S1 is not Sword. */
5996 /* Case 3: D is not at the end of string ... */
5997 if (!AT_STRINGS_END (d
))
5999 PREFETCH_NOLIMIT ();
6000 GET_CHAR_AFTER (c2
, d
, dummy
);
6002 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos
);
6006 /* ... and S2 is Sword, and WORD_BOUNDARY_P (C1, C2)
6008 if ((s2
== Sword
) && !WORD_BOUNDARY_P (c1
, c2
))
6015 DEBUG_PRINT ("EXECUTING symbeg.\n");
6017 /* We FAIL in one of the following cases: */
6019 /* Case 1: D is at the end of string. */
6020 if (AT_STRINGS_END (d
))
6024 /* C1 is the character before D, S1 is the syntax of C1, C2
6025 is the character at D, and S2 is the syntax of C2. */
6029 ssize_t offset
= PTR_TO_OFFSET (d
);
6030 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
6031 UPDATE_SYNTAX_TABLE_FAST (charpos
);
6034 c2
= RE_STRING_CHAR (d
, target_multibyte
);
6037 /* Case 2: S2 is neither Sword nor Ssymbol. */
6038 if (s2
!= Sword
&& s2
!= Ssymbol
)
6041 /* Case 3: D is not at the beginning of string ... */
6042 if (!AT_STRINGS_BEG (d
))
6044 GET_CHAR_BEFORE_2 (c1
, d
, string1
, end1
, string2
, end2
);
6046 UPDATE_SYNTAX_TABLE_BACKWARD (charpos
- 1);
6050 /* ... and S1 is Sword or Ssymbol. */
6051 if (s1
== Sword
|| s1
== Ssymbol
)
6058 DEBUG_PRINT ("EXECUTING symend.\n");
6060 /* We FAIL in one of the following cases: */
6062 /* Case 1: D is at the beginning of string. */
6063 if (AT_STRINGS_BEG (d
))
6067 /* C1 is the character before D, S1 is the syntax of C1, C2
6068 is the character at D, and S2 is the syntax of C2. */
6072 ssize_t offset
= PTR_TO_OFFSET (d
) - 1;
6073 ssize_t charpos
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
6074 UPDATE_SYNTAX_TABLE_FAST (charpos
);
6076 GET_CHAR_BEFORE_2 (c1
, d
, string1
, end1
, string2
, end2
);
6079 /* Case 2: S1 is neither Ssymbol nor Sword. */
6080 if (s1
!= Sword
&& s1
!= Ssymbol
)
6083 /* Case 3: D is not at the end of string ... */
6084 if (!AT_STRINGS_END (d
))
6086 PREFETCH_NOLIMIT ();
6087 c2
= RE_STRING_CHAR (d
, target_multibyte
);
6089 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos
+ 1);
6093 /* ... and S2 is Sword or Ssymbol. */
6094 if (s2
== Sword
|| s2
== Ssymbol
)
6103 boolean
not = (re_opcode_t
) *(p
- 1) == notsyntaxspec
;
6105 DEBUG_PRINT ("EXECUTING %ssyntaxspec %d.\n", not ? "not" : "",
6110 ssize_t offset
= PTR_TO_OFFSET (d
);
6111 ssize_t pos1
= SYNTAX_TABLE_BYTE_TO_CHAR (offset
);
6112 UPDATE_SYNTAX_TABLE_FAST (pos1
);
6119 GET_CHAR_AFTER (c
, d
, len
);
6120 if ((SYNTAX (c
) != (enum syntaxcode
) mcnt
) ^ not)
6129 DEBUG_PRINT ("EXECUTING at_dot.\n");
6130 if (PTR_BYTE_POS (d
) != PT_BYTE
)
6135 case notcategoryspec
:
6137 boolean
not = (re_opcode_t
) *(p
- 1) == notcategoryspec
;
6139 DEBUG_PRINT ("EXECUTING %scategoryspec %d.\n",
6140 not ? "not" : "", mcnt
);
6146 GET_CHAR_AFTER (c
, d
, len
);
6147 if ((!CHAR_HAS_CATEGORY (c
, mcnt
)) ^ not)
6159 continue; /* Successfully executed one pattern command; keep going. */
6162 /* We goto here if a matching operation fails. */
6164 IMMEDIATE_QUIT_CHECK
;
6165 if (!FAIL_STACK_EMPTY ())
6168 /* A restart point is known. Restore to that state. */
6169 DEBUG_PRINT ("\nFAIL:\n");
6170 POP_FAILURE_POINT (str
, pat
);
6173 case on_failure_keep_string_jump
:
6174 assert (str
== NULL
);
6175 goto continue_failure_jump
;
6177 case on_failure_jump_nastyloop
:
6178 assert ((re_opcode_t
)pat
[-2] == no_op
);
6179 PUSH_FAILURE_POINT (pat
- 2, str
);
6182 case on_failure_jump_loop
:
6183 case on_failure_jump
:
6186 continue_failure_jump
:
6187 EXTRACT_NUMBER_AND_INCR (mcnt
, pat
);
6192 /* A special frame used for nastyloops. */
6199 assert (p
>= bufp
->buffer
&& p
<= pend
);
6201 if (d
>= string1
&& d
<= end1
)
6205 break; /* Matching at this starting point really fails. */
6209 goto restore_best_regs
;
6213 return -1; /* Failure to match. */
6216 /* Subroutine definitions for re_match_2. */
6218 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
6219 bytes; nonzero otherwise. */
6222 bcmp_translate (const_re_char
*s1
, const_re_char
*s2
, register ssize_t len
,
6223 RE_TRANSLATE_TYPE translate
, const int target_multibyte
)
6225 register re_char
*p1
= s1
, *p2
= s2
;
6226 re_char
*p1_end
= s1
+ len
;
6227 re_char
*p2_end
= s2
+ len
;
6229 /* FIXME: Checking both p1 and p2 presumes that the two strings might have
6230 different lengths, but relying on a single `len' would break this. -sm */
6231 while (p1
< p1_end
&& p2
< p2_end
)
6233 int p1_charlen
, p2_charlen
;
6234 re_wchar_t p1_ch
, p2_ch
;
6236 GET_CHAR_AFTER (p1_ch
, p1
, p1_charlen
);
6237 GET_CHAR_AFTER (p2_ch
, p2
, p2_charlen
);
6239 if (RE_TRANSLATE (translate
, p1_ch
)
6240 != RE_TRANSLATE (translate
, p2_ch
))
6243 p1
+= p1_charlen
, p2
+= p2_charlen
;
6246 if (p1
!= p1_end
|| p2
!= p2_end
)
6252 /* Entry points for GNU code. */
6254 /* re_compile_pattern is the GNU regular expression compiler: it
6255 compiles PATTERN (of length SIZE) and puts the result in BUFP.
6256 Returns 0 if the pattern was valid, otherwise an error string.
6258 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
6259 are set in BUFP on entry.
6261 We call regex_compile to do the actual compilation. */
6264 re_compile_pattern (const char *pattern
, size_t length
,
6266 bool posix_backtracking
, const char *whitespace_regexp
,
6268 struct re_pattern_buffer
*bufp
)
6272 /* GNU code is written to assume at least RE_NREGS registers will be set
6273 (and at least one extra will be -1). */
6274 bufp
->regs_allocated
= REGS_UNALLOCATED
;
6276 /* And GNU code determines whether or not to get register information
6277 by passing null for the REGS argument to re_match, etc., not by
6281 ret
= regex_compile ((re_char
*) pattern
, length
,
6292 return gettext (re_error_msgid
[(int) ret
]);
6294 WEAK_ALIAS (__re_compile_pattern
, re_compile_pattern
)
6296 /* Entry points compatible with 4.2 BSD regex library. We don't define
6297 them unless specifically requested. */
6299 #if defined _REGEX_RE_COMP || defined _LIBC
6301 /* BSD has one and only one pattern buffer. */
6302 static struct re_pattern_buffer re_comp_buf
;
6306 /* Make these definitions weak in libc, so POSIX programs can redefine
6307 these names if they don't use our functions, and still use
6308 regcomp/regexec below without link errors. */
6311 re_comp (const char *s
)
6317 if (!re_comp_buf
.buffer
)
6318 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6319 return (char *) gettext ("No previous regular expression");
6323 if (!re_comp_buf
.buffer
)
6325 re_comp_buf
.buffer
= malloc (200);
6326 if (re_comp_buf
.buffer
== NULL
)
6327 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6328 return (char *) gettext (re_error_msgid
[(int) REG_ESPACE
]);
6329 re_comp_buf
.allocated
= 200;
6331 re_comp_buf
.fastmap
= malloc (1 << BYTEWIDTH
);
6332 if (re_comp_buf
.fastmap
== NULL
)
6333 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6334 return (char *) gettext (re_error_msgid
[(int) REG_ESPACE
]);
6337 /* Since `re_exec' always passes NULL for the `regs' argument, we
6338 don't need to initialize the pattern buffer fields which affect it. */
6340 ret
= regex_compile (s
, strlen (s
), re_syntax_options
, &re_comp_buf
);
6345 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6346 return (char *) gettext (re_error_msgid
[(int) ret
]);
6354 re_exec (const char *s
)
6356 const size_t len
= strlen (s
);
6357 return re_search (&re_comp_buf
, s
, len
, 0, len
, 0) >= 0;
6359 #endif /* _REGEX_RE_COMP */
6361 /* POSIX.2 functions. Don't define these for Emacs. */
6365 /* regcomp takes a regular expression as a string and compiles it.
6367 PREG is a regex_t *. We do not expect any fields to be initialized,
6368 since POSIX says we shouldn't. Thus, we set
6370 `buffer' to the compiled pattern;
6371 `used' to the length of the compiled pattern;
6372 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
6373 REG_EXTENDED bit in CFLAGS is set; otherwise, to
6374 RE_SYNTAX_POSIX_BASIC;
6375 `fastmap' to an allocated space for the fastmap;
6376 `fastmap_accurate' to zero;
6377 `re_nsub' to the number of subexpressions in PATTERN.
6379 PATTERN is the address of the pattern string.
6381 CFLAGS is a series of bits which affect compilation.
6383 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
6384 use POSIX basic syntax.
6386 If REG_NEWLINE is set, then . and [^...] don't match newline.
6387 Also, regexec will try a match beginning after every newline.
6389 If REG_ICASE is set, then we considers upper- and lowercase
6390 versions of letters to be equivalent when matching.
6392 If REG_NOSUB is set, then when PREG is passed to regexec, that
6393 routine will report only success or failure, and nothing about the
6396 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
6397 the return codes and their meanings.) */
6400 regcomp (regex_t
*_Restrict_ preg
, const char *_Restrict_ pattern
,
6405 = (cflags
& REG_EXTENDED
) ?
6406 RE_SYNTAX_POSIX_EXTENDED
: RE_SYNTAX_POSIX_BASIC
;
6408 /* regex_compile will allocate the space for the compiled pattern. */
6410 preg
->allocated
= 0;
6413 /* Try to allocate space for the fastmap. */
6414 preg
->fastmap
= malloc (1 << BYTEWIDTH
);
6416 if (cflags
& REG_ICASE
)
6420 preg
->translate
= malloc (CHAR_SET_SIZE
* sizeof *preg
->translate
);
6421 if (preg
->translate
== NULL
)
6422 return (int) REG_ESPACE
;
6424 /* Map uppercase characters to corresponding lowercase ones. */
6425 for (i
= 0; i
< CHAR_SET_SIZE
; i
++)
6426 preg
->translate
[i
] = ISUPPER (i
) ? TOLOWER (i
) : i
;
6429 preg
->translate
= NULL
;
6431 /* If REG_NEWLINE is set, newlines are treated differently. */
6432 if (cflags
& REG_NEWLINE
)
6433 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
6434 syntax
&= ~RE_DOT_NEWLINE
;
6435 syntax
|= RE_HAT_LISTS_NOT_NEWLINE
;
6438 syntax
|= RE_NO_NEWLINE_ANCHOR
;
6440 preg
->no_sub
= !!(cflags
& REG_NOSUB
);
6442 /* POSIX says a null character in the pattern terminates it, so we
6443 can use strlen here in compiling the pattern. */
6444 ret
= regex_compile ((re_char
*) pattern
, strlen (pattern
), syntax
, preg
);
6446 /* POSIX doesn't distinguish between an unmatched open-group and an
6447 unmatched close-group: both are REG_EPAREN. */
6448 if (ret
== REG_ERPAREN
)
6451 if (ret
== REG_NOERROR
&& preg
->fastmap
)
6452 { /* Compute the fastmap now, since regexec cannot modify the pattern
6454 re_compile_fastmap (preg
);
6455 if (preg
->can_be_null
)
6456 { /* The fastmap can't be used anyway. */
6457 free (preg
->fastmap
);
6458 preg
->fastmap
= NULL
;
6463 WEAK_ALIAS (__regcomp
, regcomp
)
6466 /* regexec searches for a given pattern, specified by PREG, in the
6469 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
6470 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
6471 least NMATCH elements, and we set them to the offsets of the
6472 corresponding matched substrings.
6474 EFLAGS specifies `execution flags' which affect matching: if
6475 REG_NOTBOL is set, then ^ does not match at the beginning of the
6476 string; if REG_NOTEOL is set, then $ does not match at the end.
6478 We return 0 if we find a match and REG_NOMATCH if not. */
6481 regexec (const regex_t
*_Restrict_ preg
, const char *_Restrict_ string
,
6482 size_t nmatch
, regmatch_t pmatch
[_Restrict_arr_
], int eflags
)
6485 struct re_registers regs
;
6486 regex_t private_preg
;
6487 size_t len
= strlen (string
);
6488 boolean want_reg_info
= !preg
->no_sub
&& nmatch
> 0 && pmatch
;
6490 private_preg
= *preg
;
6492 private_preg
.not_bol
= !!(eflags
& REG_NOTBOL
);
6493 private_preg
.not_eol
= !!(eflags
& REG_NOTEOL
);
6495 /* The user has told us exactly how many registers to return
6496 information about, via `nmatch'. We have to pass that on to the
6497 matching routines. */
6498 private_preg
.regs_allocated
= REGS_FIXED
;
6502 regs
.num_regs
= nmatch
;
6503 regs
.start
= TALLOC (nmatch
* 2, regoff_t
);
6504 if (regs
.start
== NULL
)
6506 regs
.end
= regs
.start
+ nmatch
;
6509 /* Instead of using not_eol to implement REG_NOTEOL, we could simply
6510 pass (&private_preg, string, len + 1, 0, len, ...) pretending the string
6511 was a little bit longer but still only matching the real part.
6512 This works because the `endline' will check for a '\n' and will find a
6513 '\0', correctly deciding that this is not the end of a line.
6514 But it doesn't work out so nicely for REG_NOTBOL, since we don't have
6515 a convenient '\0' there. For all we know, the string could be preceded
6516 by '\n' which would throw things off. */
6518 /* Perform the searching operation. */
6519 ret
= re_search (&private_preg
, string
, len
,
6520 /* start: */ 0, /* range: */ len
,
6521 want_reg_info
? ®s
: 0);
6523 /* Copy the register information to the POSIX structure. */
6530 for (r
= 0; r
< nmatch
; r
++)
6532 pmatch
[r
].rm_so
= regs
.start
[r
];
6533 pmatch
[r
].rm_eo
= regs
.end
[r
];
6537 /* If we needed the temporary register info, free the space now. */
6541 /* We want zero return to mean success, unlike `re_search'. */
6542 return ret
>= 0 ? REG_NOERROR
: REG_NOMATCH
;
6544 WEAK_ALIAS (__regexec
, regexec
)
6547 /* Returns a message corresponding to an error code, ERR_CODE, returned
6548 from either regcomp or regexec. We don't use PREG here.
6550 ERR_CODE was previously called ERRCODE, but that name causes an
6551 error with msvc8 compiler. */
6554 regerror (int err_code
, const regex_t
*preg
, char *errbuf
, size_t errbuf_size
)
6560 || err_code
>= (sizeof (re_error_msgid
) / sizeof (re_error_msgid
[0])))
6561 /* Only error codes returned by the rest of the code should be passed
6562 to this routine. If we are given anything else, or if other regex
6563 code generates an invalid error code, then the program has a bug.
6564 Dump core so we can fix it. */
6567 msg
= gettext (re_error_msgid
[err_code
]);
6569 msg_size
= strlen (msg
) + 1; /* Includes the null. */
6571 if (errbuf_size
!= 0)
6573 if (msg_size
> errbuf_size
)
6575 memcpy (errbuf
, msg
, errbuf_size
- 1);
6576 errbuf
[errbuf_size
- 1] = 0;
6579 strcpy (errbuf
, msg
);
6584 WEAK_ALIAS (__regerror
, regerror
)
6587 /* Free dynamically allocated space used by PREG. */
6590 regfree (regex_t
*preg
)
6592 free (preg
->buffer
);
6593 preg
->buffer
= NULL
;
6595 preg
->allocated
= 0;
6598 free (preg
->fastmap
);
6599 preg
->fastmap
= NULL
;
6600 preg
->fastmap_accurate
= 0;
6602 free (preg
->translate
);
6603 preg
->translate
= NULL
;
6605 WEAK_ALIAS (__regfree
, regfree
)
6607 #endif /* not emacs */