?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix description of 'C-z' in User manual
[emacs.git] / src / regex.c
blob56b18e6b5bb1994eecb29d18131f2287e65dc2e2
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.)
4
5 Copyright (C) 1993-2016 Free Software Foundation, Inc.
6
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)
10 any later version.
11
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.
16
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/>. */
19
20 /* TODO:
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.
27 */
28
29 /* AIX requires this to be the first thing in the file. */
30 #if defined _AIX && !defined REGEX_MALLOC
31 #pragma alloca
32 #endif
33
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"
38 # ifndef emacs
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"
43 # endif
44 #endif
45
46 #if 4 < __GNUC__ + (6 <= __GNUC_MINOR__) && ! defined __clang__
47 # pragma GCC diagnostic ignored "-Wunused-but-set-variable"
48 #endif
49
50 #include <config.h>
51
52 #include <stddef.h>
53
54 #ifdef emacs
55 /* We need this for `regex.h', and perhaps for the Emacs include files. */
56 # include <sys/types.h>
57 #endif
58
59 /* Whether to use ISO C Amendment 1 wide char functions.
60 Those should not be used for Emacs since it uses its own. */
61 #if defined _LIBC
62 #define WIDE_CHAR_SUPPORT 1
63 #else
64 #define WIDE_CHAR_SUPPORT \
65 (HAVE_WCTYPE_H && HAVE_WCHAR_H && HAVE_BTOWC && !emacs)
66 #endif
67
68 /* For platform which support the ISO C amendment 1 functionality we
69 support user defined character classes. */
70 #if WIDE_CHAR_SUPPORT
71 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
72 # include <wchar.h>
73 # include <wctype.h>
74 #endif
75
76 #ifdef _LIBC
77 /* We have to keep the namespace clean. */
78 # define regfree(preg) __regfree (preg)
79 # define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
80 # define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
81 # define regerror(err_code, preg, errbuf, errbuf_size) \
82 __regerror (err_code, preg, errbuf, errbuf_size)
83 # define re_set_registers(bu, re, nu, st, en) \
84 __re_set_registers (bu, re, nu, st, en)
85 # define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
86 __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
87 # define re_match(bufp, string, size, pos, regs) \
88 __re_match (bufp, string, size, pos, regs)
89 # define re_search(bufp, string, size, startpos, range, regs) \
90 __re_search (bufp, string, size, startpos, range, regs)
91 # define re_compile_pattern(pattern, length, bufp) \
92 __re_compile_pattern (pattern, length, bufp)
93 # define re_set_syntax(syntax) __re_set_syntax (syntax)
94 # define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
95 __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
96 # define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
97
98 /* Make sure we call libc's function even if the user overrides them. */
99 # define btowc __btowc
100 # define iswctype __iswctype
101 # define wctype __wctype
102
103 # define WEAK_ALIAS(a,b) weak_alias (a, b)
104
105 /* We are also using some library internals. */
106 # include <locale/localeinfo.h>
107 # include <locale/elem-hash.h>
108 # include <langinfo.h>
109 #else
110 # define WEAK_ALIAS(a,b)
111 #endif
112
113 /* This is for other GNU distributions with internationalized messages. */
114 #if HAVE_LIBINTL_H || defined _LIBC
115 # include <libintl.h>
116 #else
117 # define gettext(msgid) (msgid)
118 #endif
119
120 #ifndef gettext_noop
121 /* This define is so xgettext can find the internationalizable
122 strings. */
123 # define gettext_noop(String) String
124 #endif
125
126 /* The `emacs' switch turns on certain matching commands
127 that make sense only in Emacs. */
128 #ifdef emacs
129
130 # include "lisp.h"
131 # include "character.h"
132 # include "buffer.h"
133
134 # include "syntax.h"
135 # include "category.h"
136
137 /* Make syntax table lookup grant data in gl_state. */
138 # define SYNTAX(c) syntax_property (c, 1)
139
140 # ifdef malloc
141 # undef malloc
142 # endif
143 # define malloc xmalloc
144 # ifdef realloc
145 # undef realloc
146 # endif
147 # define realloc xrealloc
148 # ifdef free
149 # undef free
150 # endif
151 # define free xfree
152
153 /* Converts the pointer to the char to BEG-based offset from the start. */
154 # define PTR_TO_OFFSET(d) POS_AS_IN_BUFFER (POINTER_TO_OFFSET (d))
155 /* Strings are 0-indexed, buffers are 1-indexed; we pun on the boolean
156 result to get the right base index. */
157 # define POS_AS_IN_BUFFER(p) ((p) + (NILP (re_match_object) || BUFFERP (re_match_object)))
158
159 # define RE_MULTIBYTE_P(bufp) ((bufp)->multibyte)
160 # define RE_TARGET_MULTIBYTE_P(bufp) ((bufp)->target_multibyte)
161 # define RE_STRING_CHAR(p, multibyte) \
162 (multibyte ? (STRING_CHAR (p)) : (*(p)))
163 # define RE_STRING_CHAR_AND_LENGTH(p, len, multibyte) \
164 (multibyte ? (STRING_CHAR_AND_LENGTH (p, len)) : ((len) = 1, *(p)))
165
166 # define RE_CHAR_TO_MULTIBYTE(c) UNIBYTE_TO_CHAR (c)
167
168 # define RE_CHAR_TO_UNIBYTE(c) CHAR_TO_BYTE_SAFE (c)
169
170 /* Set C a (possibly converted to multibyte) character before P. P
171 points into a string which is the virtual concatenation of STR1
172 (which ends at END1) or STR2 (which ends at END2). */
173 # define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
174 do { \
175 if (target_multibyte) \
176 { \
177 re_char *dtemp = (p) == (str2) ? (end1) : (p); \
178 re_char *dlimit = ((p) > (str2) && (p) <= (end2)) ? (str2) : (str1); \
179 while (dtemp-- > dlimit && !CHAR_HEAD_P (*dtemp)); \
180 c = STRING_CHAR (dtemp); \
181 } \
182 else \
183 { \
184 (c = ((p) == (str2) ? (end1) : (p))[-1]); \
185 (c) = RE_CHAR_TO_MULTIBYTE (c); \
186 } \
187 } while (0)
188
189 /* Set C a (possibly converted to multibyte) character at P, and set
190 LEN to the byte length of that character. */
191 # define GET_CHAR_AFTER(c, p, len) \
192 do { \
193 if (target_multibyte) \
194 (c) = STRING_CHAR_AND_LENGTH (p, len); \
195 else \
196 { \
197 (c) = *p; \
198 len = 1; \
199 (c) = RE_CHAR_TO_MULTIBYTE (c); \
200 } \
201 } while (0)
202
203 #else /* not emacs */
204
205 /* If we are not linking with Emacs proper,
206 we can't use the relocating allocator
207 even if config.h says that we can. */
208 # undef REL_ALLOC
209
210 # include <unistd.h>
211
212 /* When used in Emacs's lib-src, we need xmalloc and xrealloc. */
213
214 static void *
215 xmalloc (size_t size)
216 {
217 void *val = malloc (size);
218 if (!val && size)
219 {
220 write (2, "virtual memory exhausted\n", 25);
221 exit (1);
222 }
223 return val;
224 }
225
226 static void *
227 xrealloc (void *block, size_t size)
228 {
229 void *val;
230 /* We must call malloc explicitly when BLOCK is 0, since some
231 reallocs don't do this. */
232 if (! block)
233 val = malloc (size);
234 else
235 val = realloc (block, size);
236 if (!val && size)
237 {
238 write (2, "virtual memory exhausted\n", 25);
239 exit (1);
240 }
241 return val;
242 }
243
244 # ifdef malloc
245 # undef malloc
246 # endif
247 # define malloc xmalloc
248 # ifdef realloc
249 # undef realloc
250 # endif
251 # define realloc xrealloc
252
253 # include <stdbool.h>
254 # include <string.h>
255
256 /* Define the syntax stuff for \<, \>, etc. */
257
258 /* Sword must be nonzero for the wordchar pattern commands in re_match_2. */
259 enum syntaxcode { Swhitespace = 0, Sword = 1, Ssymbol = 2 };
260
261 /* Dummy macros for non-Emacs environments. */
262 # define MAX_MULTIBYTE_LENGTH 1
263 # define RE_MULTIBYTE_P(x) 0
264 # define RE_TARGET_MULTIBYTE_P(x) 0
265 # define WORD_BOUNDARY_P(c1, c2) (0)
266 # define BYTES_BY_CHAR_HEAD(p) (1)
267 # define PREV_CHAR_BOUNDARY(p, limit) ((p)--)
268 # define STRING_CHAR(p) (*(p))
269 # define RE_STRING_CHAR(p, multibyte) STRING_CHAR (p)
270 # define CHAR_STRING(c, s) (*(s) = (c), 1)
271 # define STRING_CHAR_AND_LENGTH(p, actual_len) ((actual_len) = 1, *(p))
272 # define RE_STRING_CHAR_AND_LENGTH(p, len, multibyte) STRING_CHAR_AND_LENGTH (p, len)
273 # define RE_CHAR_TO_MULTIBYTE(c) (c)
274 # define RE_CHAR_TO_UNIBYTE(c) (c)
275 # define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \
276 (c = ((p) == (str2) ? *((end1) - 1) : *((p) - 1)))
277 # define GET_CHAR_AFTER(c, p, len) \
278 (c = *p, len = 1)
279 # define CHAR_BYTE8_P(c) (0)
280 # define CHAR_LEADING_CODE(c) (c)
281
282 #endif /* not emacs */
283
284 #ifndef RE_TRANSLATE
285 # define RE_TRANSLATE(TBL, C) ((unsigned char)(TBL)[C])
286 # define RE_TRANSLATE_P(TBL) (TBL)
287 #endif
288 \f
289 /* Get the interface, including the syntax bits. */
290 #include "regex.h"
291
292 /* isalpha etc. are used for the character classes. */
293 #include <ctype.h>
294
295 #ifdef emacs
296
297 /* 1 if C is an ASCII character. */
298 # define IS_REAL_ASCII(c) ((c) < 0200)
299
300 /* 1 if C is a unibyte character. */
301 # define ISUNIBYTE(c) (SINGLE_BYTE_CHAR_P ((c)))
302
303 /* The Emacs definitions should not be directly affected by locales. */
304
305 /* In Emacs, these are only used for single-byte characters. */
306 # define ISDIGIT(c) ((c) >= '0' && (c) <= '9')
307 # define ISCNTRL(c) ((c) < ' ')
308 # define ISXDIGIT(c) (((c) >= '0' && (c) <= '9') \
309 || ((c) >= 'a' && (c) <= 'f') \
310 || ((c) >= 'A' && (c) <= 'F'))
311
312 /* This is only used for single-byte characters. */
313 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
314
315 /* The rest must handle multibyte characters. */
316
317 # define ISGRAPH(c) (SINGLE_BYTE_CHAR_P (c) \
318 ? (c) > ' ' && !((c) >= 0177 && (c) <= 0240) \
319 : graphicp (c))
320
321 # define ISPRINT(c) (SINGLE_BYTE_CHAR_P (c) \
322 ? (c) >= ' ' && !((c) >= 0177 && (c) <= 0237) \
323 : printablep (c))
324
325 # define ISALNUM(c) (IS_REAL_ASCII (c) \
326 ? (((c) >= 'a' && (c) <= 'z') \
327 || ((c) >= 'A' && (c) <= 'Z') \
328 || ((c) >= '0' && (c) <= '9')) \
329 : (alphabeticp (c) || decimalnump (c)))
330
331 # define ISALPHA(c) (IS_REAL_ASCII (c) \
332 ? (((c) >= 'a' && (c) <= 'z') \
333 || ((c) >= 'A' && (c) <= 'Z')) \
334 : alphabeticp (c))
335
336 # define ISLOWER(c) lowercasep (c)
337
338 # define ISPUNCT(c) (IS_REAL_ASCII (c) \
339 ? ((c) > ' ' && (c) < 0177 \
340 && !(((c) >= 'a' && (c) <= 'z') \
341 || ((c) >= 'A' && (c) <= 'Z') \
342 || ((c) >= '0' && (c) <= '9'))) \
343 : SYNTAX (c) != Sword)
344
345 # define ISSPACE(c) (SYNTAX (c) == Swhitespace)
346
347 # define ISUPPER(c) uppercasep (c)
348
349 # define ISWORD(c) (SYNTAX (c) == Sword)
350
351 #else /* not emacs */
352
353 /* 1 if C is an ASCII character. */
354 # define IS_REAL_ASCII(c) ((c) < 0200)
355
356 /* This distinction is not meaningful, except in Emacs. */
357 # define ISUNIBYTE(c) 1
358
359 # ifdef isblank
360 # define ISBLANK(c) isblank (c)
361 # else
362 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
363 # endif
364 # ifdef isgraph
365 # define ISGRAPH(c) isgraph (c)
366 # else
367 # define ISGRAPH(c) (isprint (c) && !isspace (c))
368 # endif
369
370 /* Solaris defines ISPRINT so we must undefine it first. */
371 # undef ISPRINT
372 # define ISPRINT(c) isprint (c)
373 # define ISDIGIT(c) isdigit (c)
374 # define ISALNUM(c) isalnum (c)
375 # define ISALPHA(c) isalpha (c)
376 # define ISCNTRL(c) iscntrl (c)
377 # define ISLOWER(c) islower (c)
378 # define ISPUNCT(c) ispunct (c)
379 # define ISSPACE(c) isspace (c)
380 # define ISUPPER(c) isupper (c)
381 # define ISXDIGIT(c) isxdigit (c)
382
383 # define ISWORD(c) ISALPHA (c)
384
385 # ifdef _tolower
386 # define TOLOWER(c) _tolower (c)
387 # else
388 # define TOLOWER(c) tolower (c)
389 # endif
390
391 /* How many characters in the character set. */
392 # define CHAR_SET_SIZE 256
393
394 # ifdef SYNTAX_TABLE
395
396 extern char *re_syntax_table;
397
398 # else /* not SYNTAX_TABLE */
399
400 static char re_syntax_table[CHAR_SET_SIZE];
401
402 static void
403 init_syntax_once (void)
404 {
405 register int c;
406 static int done = 0;
407
408 if (done)
409 return;
410
411 memset (re_syntax_table, 0, sizeof re_syntax_table);
412
413 for (c = 0; c < CHAR_SET_SIZE; ++c)
414 if (ISALNUM (c))
415 re_syntax_table[c] = Sword;
416
417 re_syntax_table['_'] = Ssymbol;
418
419 done = 1;
420 }
421
422 # endif /* not SYNTAX_TABLE */
423
424 # define SYNTAX(c) re_syntax_table[(c)]
425
426 #endif /* not emacs */
427 \f
428 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
429 \f
430 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
431 use `alloca' instead of `malloc'. This is because using malloc in
432 re_search* or re_match* could cause memory leaks when C-g is used in
433 Emacs; also, malloc is slower and causes storage fragmentation. On
434 the other hand, malloc is more portable, and easier to debug.
435
436 Because we sometimes use alloca, some routines have to be macros,
437 not functions -- `alloca'-allocated space disappears at the end of the
438 function it is called in. */
439
440 #ifdef REGEX_MALLOC
441
442 # define REGEX_ALLOCATE malloc
443 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
444 # define REGEX_FREE free
445
446 #else /* not REGEX_MALLOC */
447
448 /* Emacs already defines alloca, sometimes. */
449 # ifndef alloca
450
451 /* Make alloca work the best possible way. */
452 # ifdef __GNUC__
453 # define alloca __builtin_alloca
454 # else /* not __GNUC__ */
455 # ifdef HAVE_ALLOCA_H
456 # include <alloca.h>
457 # endif /* HAVE_ALLOCA_H */
458 # endif /* not __GNUC__ */
459
460 # endif /* not alloca */
461
462 # ifdef emacs
463 # define REGEX_USE_SAFE_ALLOCA USE_SAFE_ALLOCA
464 # define REGEX_SAFE_FREE() SAFE_FREE ()
465 # define REGEX_ALLOCATE SAFE_ALLOCA
466 # else
467 # define REGEX_ALLOCATE alloca
468 # endif
469
470 /* Assumes a `char *destination' variable. */
471 # define REGEX_REALLOCATE(source, osize, nsize) \
472 (destination = REGEX_ALLOCATE (nsize), \
473 memcpy (destination, source, osize))
474
475 /* No need to do anything to free, after alloca. */
476 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
477
478 #endif /* not REGEX_MALLOC */
479
480 #ifndef REGEX_USE_SAFE_ALLOCA
481 # define REGEX_USE_SAFE_ALLOCA ((void) 0)
482 # define REGEX_SAFE_FREE() ((void) 0)
483 #endif
484
485 /* Define how to allocate the failure stack. */
486
487 #if defined REL_ALLOC && defined REGEX_MALLOC
488
489 # define REGEX_ALLOCATE_STACK(size) \
490 r_alloc (&failure_stack_ptr, (size))
491 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
492 r_re_alloc (&failure_stack_ptr, (nsize))
493 # define REGEX_FREE_STACK(ptr) \
494 r_alloc_free (&failure_stack_ptr)
495
496 #else /* not using relocating allocator */
497
498 # define REGEX_ALLOCATE_STACK(size) REGEX_ALLOCATE (size)
499 # define REGEX_REALLOCATE_STACK(source, o, n) REGEX_REALLOCATE (source, o, n)
500 # define REGEX_FREE_STACK(ptr) REGEX_FREE (ptr)
501
502 #endif /* not using relocating allocator */
503
504
505 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
506 `string1' or just past its end. This works if PTR is NULL, which is
507 a good thing. */
508 #define FIRST_STRING_P(ptr) \
509 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
510
511 /* (Re)Allocate N items of type T using malloc, or fail. */
512 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
513 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
514 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
515
516 #define BYTEWIDTH 8 /* In bits. */
517
518 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
519
520 #ifndef emacs
521 # undef max
522 # undef min
523 # define max(a, b) ((a) > (b) ? (a) : (b))
524 # define min(a, b) ((a) < (b) ? (a) : (b))
525 #endif
526
527 /* Type of source-pattern and string chars. */
528 #ifdef _MSC_VER
529 typedef unsigned char re_char;
530 typedef const re_char const_re_char;
531 #else
532 typedef const unsigned char re_char;
533 typedef re_char const_re_char;
534 #endif
535
536 typedef char boolean;
537
538 static regoff_t re_match_2_internal (struct re_pattern_buffer *bufp,
539 re_char *string1, size_t size1,
540 re_char *string2, size_t size2,
541 ssize_t pos,
542 struct re_registers *regs,
543 ssize_t stop);
544 \f
545 /* These are the command codes that appear in compiled regular
546 expressions. Some opcodes are followed by argument bytes. A
547 command code can specify any interpretation whatsoever for its
548 arguments. Zero bytes may appear in the compiled regular expression. */
549
550 typedef enum
551 {
552 no_op = 0,
553
554 /* Succeed right away--no more backtracking. */
555 succeed,
556
557 /* Followed by one byte giving n, then by n literal bytes. */
558 exactn,
559
560 /* Matches any (more or less) character. */
561 anychar,
562
563 /* Matches any one char belonging to specified set. First
564 following byte is number of bitmap bytes. Then come bytes
565 for a bitmap saying which chars are in. Bits in each byte
566 are ordered low-bit-first. A character is in the set if its
567 bit is 1. A character too large to have a bit in the map is
568 automatically not in the set.
569
570 If the length byte has the 0x80 bit set, then that stuff
571 is followed by a range table:
572 2 bytes of flags for character sets (low 8 bits, high 8 bits)
573 See RANGE_TABLE_WORK_BITS below.
574 2 bytes, the number of pairs that follow (upto 32767)
575 pairs, each 2 multibyte characters,
576 each multibyte character represented as 3 bytes. */
577 charset,
578
579 /* Same parameters as charset, but match any character that is
580 not one of those specified. */
581 charset_not,
582
583 /* Start remembering the text that is matched, for storing in a
584 register. Followed by one byte with the register number, in
585 the range 0 to one less than the pattern buffer's re_nsub
586 field. */
587 start_memory,
588
589 /* Stop remembering the text that is matched and store it in a
590 memory register. Followed by one byte with the register
591 number, in the range 0 to one less than `re_nsub' in the
592 pattern buffer. */
593 stop_memory,
594
595 /* Match a duplicate of something remembered. Followed by one
596 byte containing the register number. */
597 duplicate,
598
599 /* Fail unless at beginning of line. */
600 begline,
601
602 /* Fail unless at end of line. */
603 endline,
604
605 /* Succeeds if at beginning of buffer (if emacs) or at beginning
606 of string to be matched (if not). */
607 begbuf,
608
609 /* Analogously, for end of buffer/string. */
610 endbuf,
611
612 /* Followed by two byte relative address to which to jump. */
613 jump,
614
615 /* Followed by two-byte relative address of place to resume at
616 in case of failure. */
617 on_failure_jump,
618
619 /* Like on_failure_jump, but pushes a placeholder instead of the
620 current string position when executed. */
621 on_failure_keep_string_jump,
622
623 /* Just like `on_failure_jump', except that it checks that we
624 don't get stuck in an infinite loop (matching an empty string
625 indefinitely). */
626 on_failure_jump_loop,
627
628 /* Just like `on_failure_jump_loop', except that it checks for
629 a different kind of loop (the kind that shows up with non-greedy
630 operators). This operation has to be immediately preceded
631 by a `no_op'. */
632 on_failure_jump_nastyloop,
633
634 /* A smart `on_failure_jump' used for greedy * and + operators.
635 It analyzes the loop before which it is put and if the
636 loop does not require backtracking, it changes itself to
637 `on_failure_keep_string_jump' and short-circuits the loop,
638 else it just defaults to changing itself into `on_failure_jump'.
639 It assumes that it is pointing to just past a `jump'. */
640 on_failure_jump_smart,
641
642 /* Followed by two-byte relative address and two-byte number n.
643 After matching N times, jump to the address upon failure.
644 Does not work if N starts at 0: use on_failure_jump_loop
645 instead. */
646 succeed_n,
647
648 /* Followed by two-byte relative address, and two-byte number n.
649 Jump to the address N times, then fail. */
650 jump_n,
651
652 /* Set the following two-byte relative address to the
653 subsequent two-byte number. The address *includes* the two
654 bytes of number. */
655 set_number_at,
656
657 wordbeg, /* Succeeds if at word beginning. */
658 wordend, /* Succeeds if at word end. */
659
660 wordbound, /* Succeeds if at a word boundary. */
661 notwordbound, /* Succeeds if not at a word boundary. */
662
663 symbeg, /* Succeeds if at symbol beginning. */
664 symend, /* Succeeds if at symbol end. */
665
666 /* Matches any character whose syntax is specified. Followed by
667 a byte which contains a syntax code, e.g., Sword. */
668 syntaxspec,
669
670 /* Matches any character whose syntax is not that specified. */
671 notsyntaxspec
672
673 #ifdef emacs
674 ,before_dot, /* Succeeds if before point. */
675 at_dot, /* Succeeds if at point. */
676 after_dot, /* Succeeds if after point. */
677
678 /* Matches any character whose category-set contains the specified
679 category. The operator is followed by a byte which contains a
680 category code (mnemonic ASCII character). */
681 categoryspec,
682
683 /* Matches any character whose category-set does not contain the
684 specified category. The operator is followed by a byte which
685 contains the category code (mnemonic ASCII character). */
686 notcategoryspec
687 #endif /* emacs */
688 } re_opcode_t;
689 \f
690 /* Common operations on the compiled pattern. */
691
692 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
693
694 #define STORE_NUMBER(destination, number) \
695 do { \
696 (destination)[0] = (number) & 0377; \
697 (destination)[1] = (number) >> 8; \
698 } while (0)
699
700 /* Same as STORE_NUMBER, except increment DESTINATION to
701 the byte after where the number is stored. Therefore, DESTINATION
702 must be an lvalue. */
703
704 #define STORE_NUMBER_AND_INCR(destination, number) \
705 do { \
706 STORE_NUMBER (destination, number); \
707 (destination) += 2; \
708 } while (0)
709
710 /* Put into DESTINATION a number stored in two contiguous bytes starting
711 at SOURCE. */
712
713 #define EXTRACT_NUMBER(destination, source) \
714 ((destination) = extract_number (source))
715
716 static int
717 extract_number (re_char *source)
718 {
719 unsigned leading_byte = SIGN_EXTEND_CHAR (source[1]);
720 return (leading_byte << 8) + source[0];
721 }
722
723 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
724 SOURCE must be an lvalue. */
725
726 #define EXTRACT_NUMBER_AND_INCR(destination, source) \
727 ((destination) = extract_number_and_incr (&source))
728
729 static int
730 extract_number_and_incr (re_char **source)
731 {
732 int num = extract_number (*source);
733 *source += 2;
734 return num;
735 }
736 \f
737 /* Store a multibyte character in three contiguous bytes starting
738 DESTINATION, and increment DESTINATION to the byte after where the
739 character is stored. Therefore, DESTINATION must be an lvalue. */
740
741 #define STORE_CHARACTER_AND_INCR(destination, character) \
742 do { \
743 (destination)[0] = (character) & 0377; \
744 (destination)[1] = ((character) >> 8) & 0377; \
745 (destination)[2] = (character) >> 16; \
746 (destination) += 3; \
747 } while (0)
748
749 /* Put into DESTINATION a character stored in three contiguous bytes
750 starting at SOURCE. */
751
752 #define EXTRACT_CHARACTER(destination, source) \
753 do { \
754 (destination) = ((source)[0] \
755 | ((source)[1] << 8) \
756 | ((source)[2] << 16)); \
757 } while (0)
758
759
760 /* Macros for charset. */
761
762 /* Size of bitmap of charset P in bytes. P is a start of charset,
763 i.e. *P is (re_opcode_t) charset or (re_opcode_t) charset_not. */
764 #define CHARSET_BITMAP_SIZE(p) ((p)[1] & 0x7F)
765
766 /* Nonzero if charset P has range table. */
767 #define CHARSET_RANGE_TABLE_EXISTS_P(p) ((p)[1] & 0x80)
768
769 /* Return the address of range table of charset P. But not the start
770 of table itself, but the before where the number of ranges is
771 stored. `2 +' means to skip re_opcode_t and size of bitmap,
772 and the 2 bytes of flags at the start of the range table. */
773 #define CHARSET_RANGE_TABLE(p) (&(p)[4 + CHARSET_BITMAP_SIZE (p)])
774
775 #ifdef emacs
776 /* Extract the bit flags that start a range table. */
777 #define CHARSET_RANGE_TABLE_BITS(p) \
778 ((p)[2 + CHARSET_BITMAP_SIZE (p)] \
779 + (p)[3 + CHARSET_BITMAP_SIZE (p)] * 0x100)
780 #endif
781
782 /* Return the address of end of RANGE_TABLE. COUNT is number of
783 ranges (which is a pair of (start, end)) in the RANGE_TABLE. `* 2'
784 is start of range and end of range. `* 3' is size of each start
785 and end. */
786 #define CHARSET_RANGE_TABLE_END(range_table, count) \
787 ((range_table) + (count) * 2 * 3)
788
789 /* Test if C is in RANGE_TABLE. A flag NOT is negated if C is in.
790 COUNT is number of ranges in RANGE_TABLE. */
791 #define CHARSET_LOOKUP_RANGE_TABLE_RAW(not, c, range_table, count) \
792 do \
793 { \
794 re_wchar_t range_start, range_end; \
795 re_char *rtp; \
796 re_char *range_table_end \
797 = CHARSET_RANGE_TABLE_END ((range_table), (count)); \
798 \
799 for (rtp = (range_table); rtp < range_table_end; rtp += 2 * 3) \
800 { \
801 EXTRACT_CHARACTER (range_start, rtp); \
802 EXTRACT_CHARACTER (range_end, rtp + 3); \
803 \
804 if (range_start <= (c) && (c) <= range_end) \
805 { \
806 (not) = !(not); \
807 break; \
808 } \
809 } \
810 } \
811 while (0)
812
813 /* Test if C is in range table of CHARSET. The flag NOT is negated if
814 C is listed in it. */
815 #define CHARSET_LOOKUP_RANGE_TABLE(not, c, charset) \
816 do \
817 { \
818 /* Number of ranges in range table. */ \
819 int count; \
820 re_char *range_table = CHARSET_RANGE_TABLE (charset); \
821 \
822 EXTRACT_NUMBER_AND_INCR (count, range_table); \
823 CHARSET_LOOKUP_RANGE_TABLE_RAW ((not), (c), range_table, count); \
824 } \
825 while (0)
826 \f
827 /* If DEBUG is defined, Regex prints many voluminous messages about what
828 it is doing (if the variable `debug' is nonzero). If linked with the
829 main program in `iregex.c', you can enter patterns and strings
830 interactively. And if linked with the main program in `main.c' and
831 the other test files, you can run the already-written tests. */
832
833 #ifdef DEBUG
834
835 /* We use standard I/O for debugging. */
836 # include <stdio.h>
837
838 /* It is useful to test things that ``must'' be true when debugging. */
839 # include <assert.h>
840
841 static int debug = -100000;
842
843 # define DEBUG_STATEMENT(e) e
844 # define DEBUG_PRINT(...) if (debug > 0) printf (__VA_ARGS__)
845 # define DEBUG_COMPILES_ARGUMENTS
846 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
847 if (debug > 0) print_partial_compiled_pattern (s, e)
848 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
849 if (debug > 0) print_double_string (w, s1, sz1, s2, sz2)
850
851
852 /* Print the fastmap in human-readable form. */
853
854 static void
855 print_fastmap (char *fastmap)
856 {
857 unsigned was_a_range = 0;
858 unsigned i = 0;
859
860 while (i < (1 << BYTEWIDTH))
861 {
862 if (fastmap[i++])
863 {
864 was_a_range = 0;
865 putchar (i - 1);
866 while (i < (1 << BYTEWIDTH) && fastmap[i])
867 {
868 was_a_range = 1;
869 i++;
870 }
871 if (was_a_range)
872 {
873 printf ("-");
874 putchar (i - 1);
875 }
876 }
877 }
878 putchar ('\n');
879 }
880
881
882 /* Print a compiled pattern string in human-readable form, starting at
883 the START pointer into it and ending just before the pointer END. */
884
885 static void
886 print_partial_compiled_pattern (re_char *start, re_char *end)
887 {
888 int mcnt, mcnt2;
889 re_char *p = start;
890 re_char *pend = end;
891
892 if (start == NULL)
893 {
894 fprintf (stderr, "(null)\n");
895 return;
896 }
897
898 /* Loop over pattern commands. */
899 while (p < pend)
900 {
901 fprintf (stderr, "%td:\t", p - start);
902
903 switch ((re_opcode_t) *p++)
904 {
905 case no_op:
906 fprintf (stderr, "/no_op");
907 break;
908
909 case succeed:
910 fprintf (stderr, "/succeed");
911 break;
912
913 case exactn:
914 mcnt = *p++;
915 fprintf (stderr, "/exactn/%d", mcnt);
916 do
917 {
918 fprintf (stderr, "/%c", *p++);
919 }
920 while (--mcnt);
921 break;
922
923 case start_memory:
924 fprintf (stderr, "/start_memory/%d", *p++);
925 break;
926
927 case stop_memory:
928 fprintf (stderr, "/stop_memory/%d", *p++);
929 break;
930
931 case duplicate:
932 fprintf (stderr, "/duplicate/%d", *p++);
933 break;
934
935 case anychar:
936 fprintf (stderr, "/anychar");
937 break;
938
939 case charset:
940 case charset_not:
941 {
942 register int c, last = -100;
943 register int in_range = 0;
944 int length = CHARSET_BITMAP_SIZE (p - 1);
945 int has_range_table = CHARSET_RANGE_TABLE_EXISTS_P (p - 1);
946
947 fprintf (stderr, "/charset [%s",
948 (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
949
950 if (p + *p >= pend)
951 fprintf (stderr, " !extends past end of pattern! ");
952
953 for (c = 0; c < 256; c++)
954 if (c / 8 < length
955 && (p[1 + (c/8)] & (1 << (c % 8))))
956 {
957 /* Are we starting a range? */
958 if (last + 1 == c && ! in_range)
959 {
960 fprintf (stderr, "-");
961 in_range = 1;
962 }
963 /* Have we broken a range? */
964 else if (last + 1 != c && in_range)
965 {
966 fprintf (stderr, "%c", last);
967 in_range = 0;
968 }
969
970 if (! in_range)
971 fprintf (stderr, "%c", c);
972
973 last = c;
974 }
975
976 if (in_range)
977 fprintf (stderr, "%c", last);
978
979 fprintf (stderr, "]");
980
981 p += 1 + length;
982
983 if (has_range_table)
984 {
985 int count;
986 fprintf (stderr, "has-range-table");
987
988 /* ??? Should print the range table; for now, just skip it. */
989 p += 2; /* skip range table bits */
990 EXTRACT_NUMBER_AND_INCR (count, p);
991 p = CHARSET_RANGE_TABLE_END (p, count);
992 }
993 }
994 break;
995
996 case begline:
997 fprintf (stderr, "/begline");
998 break;
999
1000 case endline:
1001 fprintf (stderr, "/endline");
1002 break;
1003
1004 case on_failure_jump:
1005 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1006 fprintf (stderr, "/on_failure_jump to %td", p + mcnt - start);
1007 break;
1008
1009 case on_failure_keep_string_jump:
1010 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1011 fprintf (stderr, "/on_failure_keep_string_jump to %td",
1012 p + mcnt - start);
1013 break;
1014
1015 case on_failure_jump_nastyloop:
1016 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1017 fprintf (stderr, "/on_failure_jump_nastyloop to %td",
1018 p + mcnt - start);
1019 break;
1020
1021 case on_failure_jump_loop:
1022 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1023 fprintf (stderr, "/on_failure_jump_loop to %td",
1024 p + mcnt - start);
1025 break;
1026
1027 case on_failure_jump_smart:
1028 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1029 fprintf (stderr, "/on_failure_jump_smart to %td",
1030 p + mcnt - start);
1031 break;
1032
1033 case jump:
1034 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1035 fprintf (stderr, "/jump to %td", p + mcnt - start);
1036 break;
1037
1038 case succeed_n:
1039 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1040 EXTRACT_NUMBER_AND_INCR (mcnt2, p);
1041 fprintf (stderr, "/succeed_n to %td, %d times",
1042 p - 2 + mcnt - start, mcnt2);
1043 break;
1044
1045 case jump_n:
1046 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1047 EXTRACT_NUMBER_AND_INCR (mcnt2, p);
1048 fprintf (stderr, "/jump_n to %td, %d times",
1049 p - 2 + mcnt - start, mcnt2);
1050 break;
1051
1052 case set_number_at:
1053 EXTRACT_NUMBER_AND_INCR (mcnt, p);
1054 EXTRACT_NUMBER_AND_INCR (mcnt2, p);
1055 fprintf (stderr, "/set_number_at location %td to %d",
1056 p - 2 + mcnt - start, mcnt2);
1057 break;
1058
1059 case wordbound:
1060 fprintf (stderr, "/wordbound");
1061 break;
1062
1063 case notwordbound:
1064 fprintf (stderr, "/notwordbound");
1065 break;
1066
1067 case wordbeg:
1068 fprintf (stderr, "/wordbeg");
1069 break;
1070
1071 case wordend:
1072 fprintf (stderr, "/wordend");
1073 break;
1074
1075 case symbeg:
1076 fprintf (stderr, "/symbeg");
1077 break;
1078
1079 case symend:
1080 fprintf (stderr, "/symend");
1081 break;
1082
1083 case syntaxspec:
1084 fprintf (stderr, "/syntaxspec");
1085 mcnt = *p++;
1086 fprintf (stderr, "/%d", mcnt);
1087 break;
1088
1089 case notsyntaxspec:
1090 fprintf (stderr, "/notsyntaxspec");
1091 mcnt = *p++;
1092 fprintf (stderr, "/%d", mcnt);
1093 break;
1094
1095 # ifdef emacs
1096 case before_dot:
1097 fprintf (stderr, "/before_dot");
1098 break;
1099
1100 case at_dot:
1101 fprintf (stderr, "/at_dot");
1102 break;
1103
1104 case after_dot:
1105 fprintf (stderr, "/after_dot");
1106 break;
1107
1108 case categoryspec:
1109 fprintf (stderr, "/categoryspec");
1110 mcnt = *p++;
1111 fprintf (stderr, "/%d", mcnt);
1112 break;
1113
1114 case notcategoryspec:
1115 fprintf (stderr, "/notcategoryspec");
1116 mcnt = *p++;
1117 fprintf (stderr, "/%d", mcnt);
1118 break;
1119 # endif /* emacs */
1120
1121 case begbuf:
1122 fprintf (stderr, "/begbuf");
1123 break;
1124
1125 case endbuf:
1126 fprintf (stderr, "/endbuf");
1127 break;
1128
1129 default:
1130 fprintf (stderr, "?%d", *(p-1));
1131 }
1132
1133 fprintf (stderr, "\n");
1134 }
1135
1136 fprintf (stderr, "%td:\tend of pattern.\n", p - start);
1137 }
1138
1139
1140 static void
1141 print_compiled_pattern (struct re_pattern_buffer *bufp)
1142 {
1143 re_char *buffer = bufp->buffer;
1144
1145 print_partial_compiled_pattern (buffer, buffer + bufp->used);
1146 printf ("%ld bytes used/%ld bytes allocated.\n",
1147 bufp->used, bufp->allocated);
1148
1149 if (bufp->fastmap_accurate && bufp->fastmap)
1150 {
1151 printf ("fastmap: ");
1152 print_fastmap (bufp->fastmap);
1153 }
1154
1155 printf ("re_nsub: %zu\t", bufp->re_nsub);
1156 printf ("regs_alloc: %d\t", bufp->regs_allocated);
1157 printf ("can_be_null: %d\t", bufp->can_be_null);
1158 printf ("no_sub: %d\t", bufp->no_sub);
1159 printf ("not_bol: %d\t", bufp->not_bol);
1160 printf ("not_eol: %d\t", bufp->not_eol);
1161 printf ("syntax: %lx\n", bufp->syntax);
1162 fflush (stdout);
1163 /* Perhaps we should print the translate table? */
1164 }
1165
1166
1167 static void
1168 print_double_string (re_char *where, re_char *string1, ssize_t size1,
1169 re_char *string2, ssize_t size2)
1170 {
1171 ssize_t this_char;
1172
1173 if (where == NULL)
1174 printf ("(null)");
1175 else
1176 {
1177 if (FIRST_STRING_P (where))
1178 {
1179 for (this_char = where - string1; this_char < size1; this_char++)
1180 putchar (string1[this_char]);
1181
1182 where = string2;
1183 }
1184
1185 for (this_char = where - string2; this_char < size2; this_char++)
1186 putchar (string2[this_char]);
1187 }
1188 }
1189
1190 #else /* not DEBUG */
1191
1192 # undef assert
1193 # define assert(e)
1194
1195 # define DEBUG_STATEMENT(e)
1196 # define DEBUG_PRINT(...)
1197 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1198 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1199
1200 #endif /* not DEBUG */
1201 \f
1202 /* Use this to suppress gcc's `...may be used before initialized' warnings. */
1203 #ifdef lint
1204 # define IF_LINT(Code) Code
1205 #else
1206 # define IF_LINT(Code) /* empty */
1207 #endif
1208 \f
1209 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1210 also be assigned to arbitrarily: each pattern buffer stores its own
1211 syntax, so it can be changed between regex compilations. */
1212 /* This has no initializer because initialized variables in Emacs
1213 become read-only after dumping. */
1214 reg_syntax_t re_syntax_options;
1215
1216
1217 /* Specify the precise syntax of regexps for compilation. This provides
1218 for compatibility for various utilities which historically have
1219 different, incompatible syntaxes.
1220
1221 The argument SYNTAX is a bit mask comprised of the various bits
1222 defined in regex.h. We return the old syntax. */
1223
1224 reg_syntax_t
1225 re_set_syntax (reg_syntax_t syntax)
1226 {
1227 reg_syntax_t ret = re_syntax_options;
1228
1229 re_syntax_options = syntax;
1230 return ret;
1231 }
1232 WEAK_ALIAS (__re_set_syntax, re_set_syntax)
1233
1234 /* Regexp to use to replace spaces, or NULL meaning don't. */
1235 static const_re_char *whitespace_regexp;
1236
1237 void
1238 re_set_whitespace_regexp (const char *regexp)
1239 {
1240 whitespace_regexp = (const_re_char *) regexp;
1241 }
1242 WEAK_ALIAS (__re_set_syntax, re_set_syntax)
1243 \f
1244 /* This table gives an error message for each of the error codes listed
1245 in regex.h. Obviously the order here has to be same as there.
1246 POSIX doesn't require that we do anything for REG_NOERROR,
1247 but why not be nice? */
1248
1249 static const char *re_error_msgid[] =
1250 {
1251 gettext_noop ("Success"), /* REG_NOERROR */
1252 gettext_noop ("No match"), /* REG_NOMATCH */
1253 gettext_noop ("Invalid regular expression"), /* REG_BADPAT */
1254 gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */
1255 gettext_noop ("Invalid character class name"), /* REG_ECTYPE */
1256 gettext_noop ("Trailing backslash"), /* REG_EESCAPE */
1257 gettext_noop ("Invalid back reference"), /* REG_ESUBREG */
1258 gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */
1259 gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */
1260 gettext_noop ("Unmatched \\{"), /* REG_EBRACE */
1261 gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */
1262 gettext_noop ("Invalid range end"), /* REG_ERANGE */
1263 gettext_noop ("Memory exhausted"), /* REG_ESPACE */
1264 gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */
1265 gettext_noop ("Premature end of regular expression"), /* REG_EEND */
1266 gettext_noop ("Regular expression too big"), /* REG_ESIZE */
1267 gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */
1268 gettext_noop ("Range striding over charsets") /* REG_ERANGEX */
1269 };
1270 \f
1271 /* Avoiding alloca during matching, to placate r_alloc. */
1272
1273 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1274 searching and matching functions should not call alloca. On some
1275 systems, alloca is implemented in terms of malloc, and if we're
1276 using the relocating allocator routines, then malloc could cause a
1277 relocation, which might (if the strings being searched are in the
1278 ralloc heap) shift the data out from underneath the regexp
1279 routines.
1280
1281 Here's another reason to avoid allocation: Emacs
1282 processes input from X in a signal handler; processing X input may
1283 call malloc; if input arrives while a matching routine is calling
1284 malloc, then we're scrod. But Emacs can't just block input while
1285 calling matching routines; then we don't notice interrupts when
1286 they come in. So, Emacs blocks input around all regexp calls
1287 except the matching calls, which it leaves unprotected, in the
1288 faith that they will not malloc. */
1289
1290 /* Normally, this is fine. */
1291 #define MATCH_MAY_ALLOCATE
1292
1293 /* The match routines may not allocate if (1) they would do it with malloc
1294 and (2) it's not safe for them to use malloc.
1295 Note that if REL_ALLOC is defined, matching would not use malloc for the
1296 failure stack, but we would still use it for the register vectors;
1297 so REL_ALLOC should not affect this. */
1298 #if defined REGEX_MALLOC && defined emacs
1299 # undef MATCH_MAY_ALLOCATE
1300 #endif
1301
1302 \f
1303 /* Failure stack declarations and macros; both re_compile_fastmap and
1304 re_match_2 use a failure stack. These have to be macros because of
1305 REGEX_ALLOCATE_STACK. */
1306
1307
1308 /* Approximate number of failure points for which to initially allocate space
1309 when matching. If this number is exceeded, we allocate more
1310 space, so it is not a hard limit. */
1311 #ifndef INIT_FAILURE_ALLOC
1312 # define INIT_FAILURE_ALLOC 20
1313 #endif
1314
1315 /* Roughly the maximum number of failure points on the stack. Would be
1316 exactly that if always used TYPICAL_FAILURE_SIZE items each time we failed.
1317 This is a variable only so users of regex can assign to it; we never
1318 change it ourselves. We always multiply it by TYPICAL_FAILURE_SIZE
1319 before using it, so it should probably be a byte-count instead. */
1320 # if defined MATCH_MAY_ALLOCATE
1321 /* Note that 4400 was enough to cause a crash on Alpha OSF/1,
1322 whose default stack limit is 2mb. In order for a larger
1323 value to work reliably, you have to try to make it accord
1324 with the process stack limit. */
1325 size_t re_max_failures = 40000;
1326 # else
1327 size_t re_max_failures = 4000;
1328 # endif
1329
1330 union fail_stack_elt
1331 {
1332 re_char *pointer;
1333 /* This should be the biggest `int' that's no bigger than a pointer. */
1334 long integer;
1335 };
1336
1337 typedef union fail_stack_elt fail_stack_elt_t;
1338
1339 typedef struct
1340 {
1341 fail_stack_elt_t *stack;
1342 size_t size;
1343 size_t avail; /* Offset of next open position. */
1344 size_t frame; /* Offset of the cur constructed frame. */
1345 } fail_stack_type;
1346
1347 #define FAIL_STACK_EMPTY() (fail_stack.frame == 0)
1348
1349
1350 /* Define macros to initialize and free the failure stack.
1351 Do `return -2' if the alloc fails. */
1352
1353 #ifdef MATCH_MAY_ALLOCATE
1354 # define INIT_FAIL_STACK() \
1355 do { \
1356 fail_stack.stack = \
1357 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * TYPICAL_FAILURE_SIZE \
1358 * sizeof (fail_stack_elt_t)); \
1359 \
1360 if (fail_stack.stack == NULL) \
1361 return -2; \
1362 \
1363 fail_stack.size = INIT_FAILURE_ALLOC; \
1364 fail_stack.avail = 0; \
1365 fail_stack.frame = 0; \
1366 } while (0)
1367 #else
1368 # define INIT_FAIL_STACK() \
1369 do { \
1370 fail_stack.avail = 0; \
1371 fail_stack.frame = 0; \
1372 } while (0)
1373
1374 # define RETALLOC_IF(addr, n, t) \
1375 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
1376 #endif
1377
1378
1379 /* Double the size of FAIL_STACK, up to a limit
1380 which allows approximately `re_max_failures' items.
1381
1382 Return 1 if succeeds, and 0 if either ran out of memory
1383 allocating space for it or it was already too large.
1384
1385 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1386
1387 /* Factor to increase the failure stack size by
1388 when we increase it.
1389 This used to be 2, but 2 was too wasteful
1390 because the old discarded stacks added up to as much space
1391 were as ultimate, maximum-size stack. */
1392 #define FAIL_STACK_GROWTH_FACTOR 4
1393
1394 #define GROW_FAIL_STACK(fail_stack) \
1395 (((fail_stack).size * sizeof (fail_stack_elt_t) \
1396 >= re_max_failures * TYPICAL_FAILURE_SIZE) \
1397 ? 0 \
1398 : ((fail_stack).stack \
1399 = REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1400 (fail_stack).size * sizeof (fail_stack_elt_t), \
1401 min (re_max_failures * TYPICAL_FAILURE_SIZE, \
1402 ((fail_stack).size * sizeof (fail_stack_elt_t) \
1403 * FAIL_STACK_GROWTH_FACTOR))), \
1404 \
1405 (fail_stack).stack == NULL \
1406 ? 0 \
1407 : ((fail_stack).size \
1408 = (min (re_max_failures * TYPICAL_FAILURE_SIZE, \
1409 ((fail_stack).size * sizeof (fail_stack_elt_t) \
1410 * FAIL_STACK_GROWTH_FACTOR)) \
1411 / sizeof (fail_stack_elt_t)), \
1412 1)))
1413
1414
1415 /* Push a pointer value onto the failure stack.
1416 Assumes the variable `fail_stack'. Probably should only
1417 be called from within `PUSH_FAILURE_POINT'. */
1418 #define PUSH_FAILURE_POINTER(item) \
1419 fail_stack.stack[fail_stack.avail++].pointer = (item)
1420
1421 /* This pushes an integer-valued item onto the failure stack.
1422 Assumes the variable `fail_stack'. Probably should only
1423 be called from within `PUSH_FAILURE_POINT'. */
1424 #define PUSH_FAILURE_INT(item) \
1425 fail_stack.stack[fail_stack.avail++].integer = (item)
1426
1427 /* These POP... operations complement the PUSH... operations.
1428 All assume that `fail_stack' is nonempty. */
1429 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1430 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1431
1432 /* Individual items aside from the registers. */
1433 #define NUM_NONREG_ITEMS 3
1434
1435 /* Used to examine the stack (to detect infinite loops). */
1436 #define FAILURE_PAT(h) fail_stack.stack[(h) - 1].pointer
1437 #define FAILURE_STR(h) (fail_stack.stack[(h) - 2].pointer)
1438 #define NEXT_FAILURE_HANDLE(h) fail_stack.stack[(h) - 3].integer
1439 #define TOP_FAILURE_HANDLE() fail_stack.frame
1440
1441
1442 #define ENSURE_FAIL_STACK(space) \
1443 while (REMAINING_AVAIL_SLOTS <= space) { \
1444 if (!GROW_FAIL_STACK (fail_stack)) \
1445 return -2; \
1446 DEBUG_PRINT ("\n Doubled stack; size now: %zd\n", (fail_stack).size);\
1447 DEBUG_PRINT (" slots available: %zd\n", REMAINING_AVAIL_SLOTS);\
1448 }
1449
1450 /* Push register NUM onto the stack. */
1451 #define PUSH_FAILURE_REG(num) \
1452 do { \
1453 char *destination; \
1454 long n = num; \
1455 ENSURE_FAIL_STACK(3); \
1456 DEBUG_PRINT (" Push reg %ld (spanning %p -> %p)\n", \
1457 n, regstart[n], regend[n]); \
1458 PUSH_FAILURE_POINTER (regstart[n]); \
1459 PUSH_FAILURE_POINTER (regend[n]); \
1460 PUSH_FAILURE_INT (n); \
1461 } while (0)
1462
1463 /* Change the counter's value to VAL, but make sure that it will
1464 be reset when backtracking. */
1465 #define PUSH_NUMBER(ptr,val) \
1466 do { \
1467 char *destination; \
1468 int c; \
1469 ENSURE_FAIL_STACK(3); \
1470 EXTRACT_NUMBER (c, ptr); \
1471 DEBUG_PRINT (" Push number %p = %d -> %d\n", ptr, c, val); \
1472 PUSH_FAILURE_INT (c); \
1473 PUSH_FAILURE_POINTER (ptr); \
1474 PUSH_FAILURE_INT (-1); \
1475 STORE_NUMBER (ptr, val); \
1476 } while (0)
1477
1478 /* Pop a saved register off the stack. */
1479 #define POP_FAILURE_REG_OR_COUNT() \
1480 do { \
1481 long pfreg = POP_FAILURE_INT (); \
1482 if (pfreg == -1) \
1483 { \
1484 /* It's a counter. */ \
1485 /* Here, we discard `const', making re_match non-reentrant. */ \
1486 unsigned char *ptr = (unsigned char*) POP_FAILURE_POINTER (); \
1487 pfreg = POP_FAILURE_INT (); \
1488 STORE_NUMBER (ptr, pfreg); \
1489 DEBUG_PRINT (" Pop counter %p = %ld\n", ptr, pfreg); \
1490 } \
1491 else \
1492 { \
1493 regend[pfreg] = POP_FAILURE_POINTER (); \
1494 regstart[pfreg] = POP_FAILURE_POINTER (); \
1495 DEBUG_PRINT (" Pop reg %ld (spanning %p -> %p)\n", \
1496 pfreg, regstart[pfreg], regend[pfreg]); \
1497 } \
1498 } while (0)
1499
1500 /* Check that we are not stuck in an infinite loop. */
1501 #define CHECK_INFINITE_LOOP(pat_cur, string_place) \
1502 do { \
1503 ssize_t failure = TOP_FAILURE_HANDLE (); \
1504 /* Check for infinite matching loops */ \
1505 while (failure > 0 \
1506 && (FAILURE_STR (failure) == string_place \
1507 || FAILURE_STR (failure) == NULL)) \
1508 { \
1509 assert (FAILURE_PAT (failure) >= bufp->buffer \
1510 && FAILURE_PAT (failure) <= bufp->buffer + bufp->used); \
1511 if (FAILURE_PAT (failure) == pat_cur) \
1512 { \
1513 cycle = 1; \
1514 break; \
1515 } \
1516 DEBUG_PRINT (" Other pattern: %p\n", FAILURE_PAT (failure)); \
1517 failure = NEXT_FAILURE_HANDLE(failure); \
1518 } \
1519 DEBUG_PRINT (" Other string: %p\n", FAILURE_STR (failure)); \
1520 } while (0)
1521
1522 /* Push the information about the state we will need
1523 if we ever fail back to it.
1524
1525 Requires variables fail_stack, regstart, regend and
1526 num_regs be declared. GROW_FAIL_STACK requires `destination' be
1527 declared.
1528
1529 Does `return FAILURE_CODE' if runs out of memory. */
1530
1531 #define PUSH_FAILURE_POINT(pattern, string_place) \
1532 do { \
1533 char *destination; \
1534 /* Must be int, so when we don't save any registers, the arithmetic \
1535 of 0 + -1 isn't done as unsigned. */ \
1536 \
1537 DEBUG_STATEMENT (nfailure_points_pushed++); \
1538 DEBUG_PRINT ("\nPUSH_FAILURE_POINT:\n"); \
1539 DEBUG_PRINT (" Before push, next avail: %zd\n", (fail_stack).avail); \
1540 DEBUG_PRINT (" size: %zd\n", (fail_stack).size);\
1541 \
1542 ENSURE_FAIL_STACK (NUM_NONREG_ITEMS); \
1543 \
1544 DEBUG_PRINT ("\n"); \
1545 \
1546 DEBUG_PRINT (" Push frame index: %zd\n", fail_stack.frame); \
1547 PUSH_FAILURE_INT (fail_stack.frame); \
1548 \
1549 DEBUG_PRINT (" Push string %p: \"", string_place); \
1550 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, size2);\
1551 DEBUG_PRINT ("\"\n"); \
1552 PUSH_FAILURE_POINTER (string_place); \
1553 \
1554 DEBUG_PRINT (" Push pattern %p: ", pattern); \
1555 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern, pend); \
1556 PUSH_FAILURE_POINTER (pattern); \
1557 \
1558 /* Close the frame by moving the frame pointer past it. */ \
1559 fail_stack.frame = fail_stack.avail; \
1560 } while (0)
1561
1562 /* Estimate the size of data pushed by a typical failure stack entry.
1563 An estimate is all we need, because all we use this for
1564 is to choose a limit for how big to make the failure stack. */
1565 /* BEWARE, the value `20' is hard-coded in emacs.c:main(). */
1566 #define TYPICAL_FAILURE_SIZE 20
1567
1568 /* How many items can still be added to the stack without overflowing it. */
1569 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1570
1571
1572 /* Pops what PUSH_FAIL_STACK pushes.
1573
1574 We restore into the parameters, all of which should be lvalues:
1575 STR -- the saved data position.
1576 PAT -- the saved pattern position.
1577 REGSTART, REGEND -- arrays of string positions.
1578
1579 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1580 `pend', `string1', `size1', `string2', and `size2'. */
1581
1582 #define POP_FAILURE_POINT(str, pat) \
1583 do { \
1584 assert (!FAIL_STACK_EMPTY ()); \
1585 \
1586 /* Remove failure points and point to how many regs pushed. */ \
1587 DEBUG_PRINT ("POP_FAILURE_POINT:\n"); \
1588 DEBUG_PRINT (" Before pop, next avail: %zd\n", fail_stack.avail); \
1589 DEBUG_PRINT (" size: %zd\n", fail_stack.size); \
1590 \
1591 /* Pop the saved registers. */ \
1592 while (fail_stack.frame < fail_stack.avail) \
1593 POP_FAILURE_REG_OR_COUNT (); \
1594 \
1595 pat = POP_FAILURE_POINTER (); \
1596 DEBUG_PRINT (" Popping pattern %p: ", pat); \
1597 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1598 \
1599 /* If the saved string location is NULL, it came from an \
1600 on_failure_keep_string_jump opcode, and we want to throw away the \
1601 saved NULL, thus retaining our current position in the string. */ \
1602 str = POP_FAILURE_POINTER (); \
1603 DEBUG_PRINT (" Popping string %p: \"", str); \
1604 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1605 DEBUG_PRINT ("\"\n"); \
1606 \
1607 fail_stack.frame = POP_FAILURE_INT (); \
1608 DEBUG_PRINT (" Popping frame index: %zd\n", fail_stack.frame); \
1609 \
1610 assert (fail_stack.avail >= 0); \
1611 assert (fail_stack.frame <= fail_stack.avail); \
1612 \
1613 DEBUG_STATEMENT (nfailure_points_popped++); \
1614 } while (0) /* POP_FAILURE_POINT */
1615
1616
1617 \f
1618 /* Registers are set to a sentinel when they haven't yet matched. */
1619 #define REG_UNSET(e) ((e) == NULL)
1620 \f
1621 /* Subroutine declarations and macros for regex_compile. */
1622
1623 static reg_errcode_t regex_compile (re_char *pattern, size_t size,
1624 reg_syntax_t syntax,
1625 struct re_pattern_buffer *bufp);
1626 static void store_op1 (re_opcode_t op, unsigned char *loc, int arg);
1627 static void store_op2 (re_opcode_t op, unsigned char *loc, int arg1, int arg2);
1628 static void insert_op1 (re_opcode_t op, unsigned char *loc,
1629 int arg, unsigned char *end);
1630 static void insert_op2 (re_opcode_t op, unsigned char *loc,
1631 int arg1, int arg2, unsigned char *end);
1632 static boolean at_begline_loc_p (re_char *pattern, re_char *p,
1633 reg_syntax_t syntax);
1634 static boolean at_endline_loc_p (re_char *p, re_char *pend,
1635 reg_syntax_t syntax);
1636 static re_char *skip_one_char (re_char *p);
1637 static int analyze_first (re_char *p, re_char *pend,
1638 char *fastmap, const int multibyte);
1639
1640 /* Fetch the next character in the uncompiled pattern, with no
1641 translation. */
1642 #define PATFETCH(c) \
1643 do { \
1644 int len; \
1645 if (p == pend) return REG_EEND; \
1646 c = RE_STRING_CHAR_AND_LENGTH (p, len, multibyte); \
1647 p += len; \
1648 } while (0)
1649
1650
1651 /* If `translate' is non-null, return translate[D], else just D. We
1652 cast the subscript to translate because some data is declared as
1653 `char *', to avoid warnings when a string constant is passed. But
1654 when we use a character as a subscript we must make it unsigned. */
1655 #ifndef TRANSLATE
1656 # define TRANSLATE(d) \
1657 (RE_TRANSLATE_P (translate) ? RE_TRANSLATE (translate, (d)) : (d))
1658 #endif
1659
1660
1661 /* Macros for outputting the compiled pattern into `buffer'. */
1662
1663 /* If the buffer isn't allocated when it comes in, use this. */
1664 #define INIT_BUF_SIZE 32
1665
1666 /* Make sure we have at least N more bytes of space in buffer. */
1667 #define GET_BUFFER_SPACE(n) \
1668 while ((size_t) (b - bufp->buffer + (n)) > bufp->allocated) \
1669 EXTEND_BUFFER ()
1670
1671 /* Make sure we have one more byte of buffer space and then add C to it. */
1672 #define BUF_PUSH(c) \
1673 do { \
1674 GET_BUFFER_SPACE (1); \
1675 *b++ = (unsigned char) (c); \
1676 } while (0)
1677
1678
1679 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
1680 #define BUF_PUSH_2(c1, c2) \
1681 do { \
1682 GET_BUFFER_SPACE (2); \
1683 *b++ = (unsigned char) (c1); \
1684 *b++ = (unsigned char) (c2); \
1685 } while (0)
1686
1687
1688 /* Store a jump with opcode OP at LOC to location TO. We store a
1689 relative address offset by the three bytes the jump itself occupies. */
1690 #define STORE_JUMP(op, loc, to) \
1691 store_op1 (op, loc, (to) - (loc) - 3)
1692
1693 /* Likewise, for a two-argument jump. */
1694 #define STORE_JUMP2(op, loc, to, arg) \
1695 store_op2 (op, loc, (to) - (loc) - 3, arg)
1696
1697 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
1698 #define INSERT_JUMP(op, loc, to) \
1699 insert_op1 (op, loc, (to) - (loc) - 3, b)
1700
1701 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
1702 #define INSERT_JUMP2(op, loc, to, arg) \
1703 insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
1704
1705
1706 /* This is not an arbitrary limit: the arguments which represent offsets
1707 into the pattern are two bytes long. So if 2^15 bytes turns out to
1708 be too small, many things would have to change. */
1709 # define MAX_BUF_SIZE (1L << 15)
1710
1711 /* Extend the buffer by twice its current size via realloc and
1712 reset the pointers that pointed into the old block to point to the
1713 correct places in the new one. If extending the buffer results in it
1714 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
1715 #if __BOUNDED_POINTERS__
1716 # define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
1717 # define MOVE_BUFFER_POINTER(P) \
1718 (__ptrlow (P) = new_buffer + (__ptrlow (P) - old_buffer), \
1719 SET_HIGH_BOUND (P), \
1720 __ptrvalue (P) = new_buffer + (__ptrvalue (P) - old_buffer))
1721 # define ELSE_EXTEND_BUFFER_HIGH_BOUND \
1722 else \
1723 { \
1724 SET_HIGH_BOUND (b); \
1725 SET_HIGH_BOUND (begalt); \
1726 if (fixup_alt_jump) \
1727 SET_HIGH_BOUND (fixup_alt_jump); \
1728 if (laststart) \
1729 SET_HIGH_BOUND (laststart); \
1730 if (pending_exact) \
1731 SET_HIGH_BOUND (pending_exact); \
1732 }
1733 #else
1734 # define MOVE_BUFFER_POINTER(P) ((P) = new_buffer + ((P) - old_buffer))
1735 # define ELSE_EXTEND_BUFFER_HIGH_BOUND
1736 #endif
1737 #define EXTEND_BUFFER() \
1738 do { \
1739 unsigned char *old_buffer = bufp->buffer; \
1740 if (bufp->allocated == MAX_BUF_SIZE) \
1741 return REG_ESIZE; \
1742 bufp->allocated <<= 1; \
1743 if (bufp->allocated > MAX_BUF_SIZE) \
1744 bufp->allocated = MAX_BUF_SIZE; \
1745 RETALLOC (bufp->buffer, bufp->allocated, unsigned char); \
1746 if (bufp->buffer == NULL) \
1747 return REG_ESPACE; \
1748 /* If the buffer moved, move all the pointers into it. */ \
1749 if (old_buffer != bufp->buffer) \
1750 { \
1751 unsigned char *new_buffer = bufp->buffer; \
1752 MOVE_BUFFER_POINTER (b); \
1753 MOVE_BUFFER_POINTER (begalt); \
1754 if (fixup_alt_jump) \
1755 MOVE_BUFFER_POINTER (fixup_alt_jump); \
1756 if (laststart) \
1757 MOVE_BUFFER_POINTER (laststart); \
1758 if (pending_exact) \
1759 MOVE_BUFFER_POINTER (pending_exact); \
1760 } \
1761 ELSE_EXTEND_BUFFER_HIGH_BOUND \
1762 } while (0)
1763
1764
1765 /* Since we have one byte reserved for the register number argument to
1766 {start,stop}_memory, the maximum number of groups we can report
1767 things about is what fits in that byte. */
1768 #define MAX_REGNUM 255
1769
1770 /* But patterns can have more than `MAX_REGNUM' registers. We just
1771 ignore the excess. */
1772 typedef int regnum_t;
1773
1774
1775 /* Macros for the compile stack. */
1776
1777 /* Since offsets can go either forwards or backwards, this type needs to
1778 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
1779 /* int may be not enough when sizeof(int) == 2. */
1780 typedef long pattern_offset_t;
1781
1782 typedef struct
1783 {
1784 pattern_offset_t begalt_offset;
1785 pattern_offset_t fixup_alt_jump;
1786 pattern_offset_t laststart_offset;
1787 regnum_t regnum;
1788 } compile_stack_elt_t;
1789
1790
1791 typedef struct
1792 {
1793 compile_stack_elt_t *stack;
1794 size_t size;
1795 size_t avail; /* Offset of next open position. */
1796 } compile_stack_type;
1797
1798
1799 #define INIT_COMPILE_STACK_SIZE 32
1800
1801 #define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
1802 #define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
1803
1804 /* The next available element. */
1805 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1806
1807 /* Explicit quit checking is needed for Emacs, which uses polling to
1808 process input events. */
1809 #ifdef emacs
1810 # define IMMEDIATE_QUIT_CHECK \
1811 do { \
1812 if (immediate_quit) QUIT; \
1813 } while (0)
1814 #else
1815 # define IMMEDIATE_QUIT_CHECK ((void)0)
1816 #endif
1817 \f
1818 /* Structure to manage work area for range table. */
1819 struct range_table_work_area
1820 {
1821 int *table; /* actual work area. */
1822 int allocated; /* allocated size for work area in bytes. */
1823 int used; /* actually used size in words. */
1824 int bits; /* flag to record character classes */
1825 };
1826
1827 #ifdef emacs
1828
1829 /* Make sure that WORK_AREA can hold more N multibyte characters.
1830 This is used only in set_image_of_range and set_image_of_range_1.
1831 It expects WORK_AREA to be a pointer.
1832 If it can't get the space, it returns from the surrounding function. */
1833
1834 #define EXTEND_RANGE_TABLE(work_area, n) \
1835 do { \
1836 if (((work_area).used + (n)) * sizeof (int) > (work_area).allocated) \
1837 { \
1838 extend_range_table_work_area (&work_area); \
1839 if ((work_area).table == 0) \
1840 return (REG_ESPACE); \
1841 } \
1842 } while (0)
1843
1844 #define SET_RANGE_TABLE_WORK_AREA_BIT(work_area, bit) \
1845 (work_area).bits |= (bit)
1846
1847 /* Set a range (RANGE_START, RANGE_END) to WORK_AREA. */
1848 #define SET_RANGE_TABLE_WORK_AREA(work_area, range_start, range_end) \
1849 do { \
1850 EXTEND_RANGE_TABLE ((work_area), 2); \
1851 (work_area).table[(work_area).used++] = (range_start); \
1852 (work_area).table[(work_area).used++] = (range_end); \
1853 } while (0)
1854
1855 #endif /* emacs */
1856
1857 /* Free allocated memory for WORK_AREA. */
1858 #define FREE_RANGE_TABLE_WORK_AREA(work_area) \
1859 do { \
1860 if ((work_area).table) \
1861 free ((work_area).table); \
1862 } while (0)
1863
1864 #define CLEAR_RANGE_TABLE_WORK_USED(work_area) ((work_area).used = 0, (work_area).bits = 0)
1865 #define RANGE_TABLE_WORK_USED(work_area) ((work_area).used)
1866 #define RANGE_TABLE_WORK_BITS(work_area) ((work_area).bits)
1867 #define RANGE_TABLE_WORK_ELT(work_area, i) ((work_area).table[i])
1868
1869 /* Bits used to implement the multibyte-part of the various character classes
1870 such as [:alnum:] in a charset's range table. The code currently assumes
1871 that only the low 16 bits are used. */
1872 #define BIT_WORD 0x1
1873 #define BIT_LOWER 0x2
1874 #define BIT_PUNCT 0x4
1875 #define BIT_SPACE 0x8
1876 #define BIT_UPPER 0x10
1877 #define BIT_MULTIBYTE 0x20
1878 #define BIT_ALPHA 0x40
1879 #define BIT_ALNUM 0x80
1880 #define BIT_GRAPH 0x100
1881 #define BIT_PRINT 0x200
1882 \f
1883
1884 /* Set the bit for character C in a list. */
1885 #define SET_LIST_BIT(c) (b[((c)) / BYTEWIDTH] |= 1 << ((c) % BYTEWIDTH))
1886
1887
1888 #ifdef emacs
1889
1890 /* Store characters in the range FROM to TO in the bitmap at B (for
1891 ASCII and unibyte characters) and WORK_AREA (for multibyte
1892 characters) while translating them and paying attention to the
1893 continuity of translated characters.
1894
1895 Implementation note: It is better to implement these fairly big
1896 macros by a function, but it's not that easy because macros called
1897 in this macro assume various local variables already declared. */
1898
1899 /* Both FROM and TO are ASCII characters. */
1900
1901 #define SETUP_ASCII_RANGE(work_area, FROM, TO) \
1902 do { \
1903 int C0, C1; \
1904 \
1905 for (C0 = (FROM); C0 <= (TO); C0++) \
1906 { \
1907 C1 = TRANSLATE (C0); \
1908 if (! ASCII_CHAR_P (C1)) \
1909 { \
1910 SET_RANGE_TABLE_WORK_AREA ((work_area), C1, C1); \
1911 if ((C1 = RE_CHAR_TO_UNIBYTE (C1)) < 0) \
1912 C1 = C0; \
1913 } \
1914 SET_LIST_BIT (C1); \
1915 } \
1916 } while (0)
1917
1918
1919 /* Both FROM and TO are unibyte characters (0x80..0xFF). */
1920
1921 #define SETUP_UNIBYTE_RANGE(work_area, FROM, TO) \
1922 do { \
1923 int C0, C1, C2, I; \
1924 int USED = RANGE_TABLE_WORK_USED (work_area); \
1925 \
1926 for (C0 = (FROM); C0 <= (TO); C0++) \
1927 { \
1928 C1 = RE_CHAR_TO_MULTIBYTE (C0); \
1929 if (CHAR_BYTE8_P (C1)) \
1930 SET_LIST_BIT (C0); \
1931 else \
1932 { \
1933 C2 = TRANSLATE (C1); \
1934 if (C2 == C1 \
1935 || (C1 = RE_CHAR_TO_UNIBYTE (C2)) < 0) \
1936 C1 = C0; \
1937 SET_LIST_BIT (C1); \
1938 for (I = RANGE_TABLE_WORK_USED (work_area) - 2; I >= USED; I -= 2) \
1939 { \
1940 int from = RANGE_TABLE_WORK_ELT (work_area, I); \
1941 int to = RANGE_TABLE_WORK_ELT (work_area, I + 1); \
1942 \
1943 if (C2 >= from - 1 && C2 <= to + 1) \
1944 { \
1945 if (C2 == from - 1) \
1946 RANGE_TABLE_WORK_ELT (work_area, I)--; \
1947 else if (C2 == to + 1) \
1948 RANGE_TABLE_WORK_ELT (work_area, I + 1)++; \
1949 break; \
1950 } \
1951 } \
1952 if (I < USED) \
1953 SET_RANGE_TABLE_WORK_AREA ((work_area), C2, C2); \
1954 } \
1955 } \
1956 } while (0)
1957
1958
1959 /* Both FROM and TO are multibyte characters. */
1960
1961 #define SETUP_MULTIBYTE_RANGE(work_area, FROM, TO) \
1962 do { \
1963 int C0, C1, C2, I, USED = RANGE_TABLE_WORK_USED (work_area); \
1964 \
1965 SET_RANGE_TABLE_WORK_AREA ((work_area), (FROM), (TO)); \
1966 for (C0 = (FROM); C0 <= (TO); C0++) \
1967 { \
1968 C1 = TRANSLATE (C0); \
1969 if ((C2 = RE_CHAR_TO_UNIBYTE (C1)) >= 0 \
1970 || (C1 != C0 && (C2 = RE_CHAR_TO_UNIBYTE (C0)) >= 0)) \
1971 SET_LIST_BIT (C2); \
1972 if (C1 >= (FROM) && C1 <= (TO)) \
1973 continue; \
1974 for (I = RANGE_TABLE_WORK_USED (work_area) - 2; I >= USED; I -= 2) \
1975 { \
1976 int from = RANGE_TABLE_WORK_ELT (work_area, I); \
1977 int to = RANGE_TABLE_WORK_ELT (work_area, I + 1); \
1978 \
1979 if (C1 >= from - 1 && C1 <= to + 1) \
1980 { \
1981 if (C1 == from - 1) \
1982 RANGE_TABLE_WORK_ELT (work_area, I)--; \
1983 else if (C1 == to + 1) \
1984 RANGE_TABLE_WORK_ELT (work_area, I + 1)++; \
1985 break; \
1986 } \
1987 } \
1988 if (I < USED) \
1989 SET_RANGE_TABLE_WORK_AREA ((work_area), C1, C1); \
1990 } \
1991 } while (0)
1992
1993 #endif /* emacs */
1994
1995 /* Get the next unsigned number in the uncompiled pattern. */
1996 #define GET_INTERVAL_COUNT(num) \
1997 do { \
1998 if (p == pend) \
1999 FREE_STACK_RETURN (REG_EBRACE); \
2000 else \
2001 { \
2002 PATFETCH (c); \
2003 while ('0' <= c && c <= '9') \
2004 { \
2005 if (num < 0) \
2006 num = 0; \
2007 if (RE_DUP_MAX / 10 - (RE_DUP_MAX % 10 < c - '0') < num) \
2008 FREE_STACK_RETURN (REG_BADBR); \
2009 num = num * 10 + c - '0'; \
2010 if (p == pend) \
2011 FREE_STACK_RETURN (REG_EBRACE); \
2012 PATFETCH (c); \
2013 } \
2014 } \
2015 } while (0)
2016 \f
2017 #if ! WIDE_CHAR_SUPPORT
2018
2019 /* Map a string to the char class it names (if any). */
2020 re_wctype_t
2021 re_wctype (const_re_char *str)
2022 {
2023 const char *string = (const char *) str;
2024 if (STREQ (string, "alnum")) return RECC_ALNUM;
2025 else if (STREQ (string, "alpha")) return RECC_ALPHA;
2026 else if (STREQ (string, "word")) return RECC_WORD;
2027 else if (STREQ (string, "ascii")) return RECC_ASCII;
2028 else if (STREQ (string, "nonascii")) return RECC_NONASCII;
2029 else if (STREQ (string, "graph")) return RECC_GRAPH;
2030 else if (STREQ (string, "lower")) return RECC_LOWER;
2031 else if (STREQ (string, "print")) return RECC_PRINT;
2032 else if (STREQ (string, "punct")) return RECC_PUNCT;
2033 else if (STREQ (string, "space")) return RECC_SPACE;
2034 else if (STREQ (string, "upper")) return RECC_UPPER;
2035 else if (STREQ (string, "unibyte")) return RECC_UNIBYTE;
2036 else if (STREQ (string, "multibyte")) return RECC_MULTIBYTE;
2037 else if (STREQ (string, "digit")) return RECC_DIGIT;
2038 else if (STREQ (string, "xdigit")) return RECC_XDIGIT;
2039 else if (STREQ (string, "cntrl")) return RECC_CNTRL;
2040 else if (STREQ (string, "blank")) return RECC_BLANK;
2041 else return 0;
2042 }
2043
2044 /* True if CH is in the char class CC. */
2045 boolean
2046 re_iswctype (int ch, re_wctype_t cc)
2047 {
2048 switch (cc)
2049 {
2050 case RECC_ALNUM: return ISALNUM (ch) != 0;
2051 case RECC_ALPHA: return ISALPHA (ch) != 0;
2052 case RECC_BLANK: return ISBLANK (ch) != 0;
2053 case RECC_CNTRL: return ISCNTRL (ch) != 0;
2054 case RECC_DIGIT: return ISDIGIT (ch) != 0;
2055 case RECC_GRAPH: return ISGRAPH (ch) != 0;
2056 case RECC_LOWER: return ISLOWER (ch) != 0;
2057 case RECC_PRINT: return ISPRINT (ch) != 0;
2058 case RECC_PUNCT: return ISPUNCT (ch) != 0;
2059 case RECC_SPACE: return ISSPACE (ch) != 0;
2060 case RECC_UPPER: return ISUPPER (ch) != 0;
2061 case RECC_XDIGIT: return ISXDIGIT (ch) != 0;
2062 case RECC_ASCII: return IS_REAL_ASCII (ch) != 0;
2063 case RECC_NONASCII: return !IS_REAL_ASCII (ch);
2064 case RECC_UNIBYTE: return ISUNIBYTE (ch) != 0;
2065 case RECC_MULTIBYTE: return !ISUNIBYTE (ch);
2066 case RECC_WORD: return ISWORD (ch) != 0;
2067 case RECC_ERROR: return false;
2068 default:
2069 abort ();
2070 }
2071 }
2072
2073 /* Return a bit-pattern to use in the range-table bits to match multibyte
2074 chars of class CC. */
2075 static int
2076 re_wctype_to_bit (re_wctype_t cc)
2077 {
2078 switch (cc)
2079 {
2080 case RECC_NONASCII:
2081 case RECC_MULTIBYTE: return BIT_MULTIBYTE;
2082 case RECC_ALPHA: return BIT_ALPHA;
2083 case RECC_ALNUM: return BIT_ALNUM;
2084 case RECC_WORD: return BIT_WORD;
2085 case RECC_LOWER: return BIT_LOWER;
2086 case RECC_UPPER: return BIT_UPPER;
2087 case RECC_PUNCT: return BIT_PUNCT;
2088 case RECC_SPACE: return BIT_SPACE;
2089 case RECC_GRAPH: return BIT_GRAPH;
2090 case RECC_PRINT: return BIT_PRINT;
2091 case RECC_ASCII: case RECC_DIGIT: case RECC_XDIGIT: case RECC_CNTRL:
2092 case RECC_BLANK: case RECC_UNIBYTE: case RECC_ERROR: return 0;
2093 default:
2094 abort ();
2095 }
2096 }
2097 #endif
2098 \f
2099 /* Filling in the work area of a range. */
2100
2101 /* Actually extend the space in WORK_AREA. */
2102
2103 static void
2104 extend_range_table_work_area (struct range_table_work_area *work_area)
2105 {
2106 work_area->allocated += 16 * sizeof (int);
2107 work_area->table = realloc (work_area->table, work_area->allocated);
2108 }
2109
2110 #if 0
2111 #ifdef emacs
2112
2113 /* Carefully find the ranges of codes that are equivalent
2114 under case conversion to the range start..end when passed through
2115 TRANSLATE. Handle the case where non-letters can come in between
2116 two upper-case letters (which happens in Latin-1).
2117 Also handle the case of groups of more than 2 case-equivalent chars.
2118
2119 The basic method is to look at consecutive characters and see
2120 if they can form a run that can be handled as one.
2121
2122 Returns -1 if successful, REG_ESPACE if ran out of space. */
2123
2124 static int
2125 set_image_of_range_1 (struct range_table_work_area *work_area,
2126 re_wchar_t start, re_wchar_t end,
2127 RE_TRANSLATE_TYPE translate)
2128 {
2129 /* `one_case' indicates a character, or a run of characters,
2130 each of which is an isolate (no case-equivalents).
2131 This includes all ASCII non-letters.
2132
2133 `two_case' indicates a character, or a run of characters,
2134 each of which has two case-equivalent forms.
2135 This includes all ASCII letters.
2136
2137 `strange' indicates a character that has more than one
2138 case-equivalent. */
2139
2140 enum case_type {one_case, two_case, strange};
2141
2142 /* Describe the run that is in progress,
2143 which the next character can try to extend.
2144 If run_type is strange, that means there really is no run.
2145 If run_type is one_case, then run_start...run_end is the run.
2146 If run_type is two_case, then the run is run_start...run_end,
2147 and the case-equivalents end at run_eqv_end. */
2148
2149 enum case_type run_type = strange;
2150 int run_start, run_end, run_eqv_end;
2151
2152 Lisp_Object eqv_table;
2153
2154 if (!RE_TRANSLATE_P (translate))
2155 {
2156 EXTEND_RANGE_TABLE (work_area, 2);
2157 work_area->table[work_area->used++] = (start);
2158 work_area->table[work_area->used++] = (end);
2159 return -1;
2160 }
2161
2162 eqv_table = XCHAR_TABLE (translate)->extras[2];
2163
2164 for (; start <= end; start++)
2165 {
2166 enum case_type this_type;
2167 int eqv = RE_TRANSLATE (eqv_table, start);
2168 int minchar, maxchar;
2169
2170 /* Classify this character */
2171 if (eqv == start)
2172 this_type = one_case;
2173 else if (RE_TRANSLATE (eqv_table, eqv) == start)
2174 this_type = two_case;
2175 else
2176 this_type = strange;
2177
2178 if (start < eqv)
2179 minchar = start, maxchar = eqv;
2180 else
2181 minchar = eqv, maxchar = start;
2182
2183 /* Can this character extend the run in progress? */
2184 if (this_type == strange || this_type != run_type
2185 || !(minchar == run_end + 1
2186 && (run_type == two_case
2187 ? maxchar == run_eqv_end + 1 : 1)))
2188 {
2189 /* No, end the run.
2190 Record each of its equivalent ranges. */
2191 if (run_type == one_case)
2192 {
2193 EXTEND_RANGE_TABLE (work_area, 2);
2194 work_area->table[work_area->used++] = run_start;
2195 work_area->table[work_area->used++] = run_end;
2196 }
2197 else if (run_type == two_case)
2198 {
2199 EXTEND_RANGE_TABLE (work_area, 4);
2200 work_area->table[work_area->used++] = run_start;
2201 work_area->table[work_area->used++] = run_end;
2202 work_area->table[work_area->used++]
2203 = RE_TRANSLATE (eqv_table, run_start);
2204 work_area->table[work_area->used++]
2205 = RE_TRANSLATE (eqv_table, run_end);
2206 }
2207 run_type = strange;
2208 }
2209
2210 if (this_type == strange)
2211 {
2212 /* For a strange character, add each of its equivalents, one
2213 by one. Don't start a range. */
2214 do
2215 {
2216 EXTEND_RANGE_TABLE (work_area, 2);
2217 work_area->table[work_area->used++] = eqv;
2218 work_area->table[work_area->used++] = eqv;
2219 eqv = RE_TRANSLATE (eqv_table, eqv);
2220 }
2221 while (eqv != start);
2222 }
2223
2224 /* Add this char to the run, or start a new run. */
2225 else if (run_type == strange)
2226 {
2227 /* Initialize a new range. */
2228 run_type = this_type;
2229 run_start = start;
2230 run_end = start;
2231 run_eqv_end = RE_TRANSLATE (eqv_table, run_end);
2232 }
2233 else
2234 {
2235 /* Extend a running range. */
2236 run_end = minchar;
2237 run_eqv_end = RE_TRANSLATE (eqv_table, run_end);
2238 }
2239 }
2240
2241 /* If a run is still in progress at the end, finish it now
2242 by recording its equivalent ranges. */
2243 if (run_type == one_case)
2244 {
2245 EXTEND_RANGE_TABLE (work_area, 2);
2246 work_area->table[work_area->used++] = run_start;
2247 work_area->table[work_area->used++] = run_end;
2248 }
2249 else if (run_type == two_case)
2250 {
2251 EXTEND_RANGE_TABLE (work_area, 4);
2252 work_area->table[work_area->used++] = run_start;
2253 work_area->table[work_area->used++] = run_end;
2254 work_area->table[work_area->used++]
2255 = RE_TRANSLATE (eqv_table, run_start);
2256 work_area->table[work_area->used++]
2257 = RE_TRANSLATE (eqv_table, run_end);
2258 }
2259
2260 return -1;
2261 }
2262
2263 #endif /* emacs */
2264
2265 /* Record the image of the range start..end when passed through
2266 TRANSLATE. This is not necessarily TRANSLATE(start)..TRANSLATE(end)
2267 and is not even necessarily contiguous.
2268 Normally we approximate it with the smallest contiguous range that contains
2269 all the chars we need. However, for Latin-1 we go to extra effort
2270 to do a better job.
2271
2272 This function is not called for ASCII ranges.
2273
2274 Returns -1 if successful, REG_ESPACE if ran out of space. */
2275
2276 static int
2277 set_image_of_range (struct range_table_work_area *work_area,
2278 re_wchar_t start, re_wchar_t end,
2279 RE_TRANSLATE_TYPE translate)
2280 {
2281 re_wchar_t cmin, cmax;
2282
2283 #ifdef emacs
2284 /* For Latin-1 ranges, use set_image_of_range_1
2285 to get proper handling of ranges that include letters and nonletters.
2286 For a range that includes the whole of Latin-1, this is not necessary.
2287 For other character sets, we don't bother to get this right. */
2288 if (RE_TRANSLATE_P (translate) && start < 04400
2289 && !(start < 04200 && end >= 04377))
2290 {
2291 int newend;
2292 int tem;
2293 newend = end;
2294 if (newend > 04377)
2295 newend = 04377;
2296 tem = set_image_of_range_1 (work_area, start, newend, translate);
2297 if (tem > 0)
2298 return tem;
2299
2300 start = 04400;
2301 if (end < 04400)
2302 return -1;
2303 }
2304 #endif
2305
2306 EXTEND_RANGE_TABLE (work_area, 2);
2307 work_area->table[work_area->used++] = (start);
2308 work_area->table[work_area->used++] = (end);
2309
2310 cmin = -1, cmax = -1;
2311
2312 if (RE_TRANSLATE_P (translate))
2313 {
2314 int ch;
2315
2316 for (ch = start; ch <= end; ch++)
2317 {
2318 re_wchar_t c = TRANSLATE (ch);
2319 if (! (start <= c && c <= end))
2320 {
2321 if (cmin == -1)
2322 cmin = c, cmax = c;
2323 else
2324 {
2325 cmin = min (cmin, c);
2326 cmax = max (cmax, c);
2327 }
2328 }
2329 }
2330
2331 if (cmin != -1)
2332 {
2333 EXTEND_RANGE_TABLE (work_area, 2);
2334 work_area->table[work_area->used++] = (cmin);
2335 work_area->table[work_area->used++] = (cmax);
2336 }
2337 }
2338
2339 return -1;
2340 }
2341 #endif /* 0 */
2342 \f
2343 #ifndef MATCH_MAY_ALLOCATE
2344
2345 /* If we cannot allocate large objects within re_match_2_internal,
2346 we make the fail stack and register vectors global.
2347 The fail stack, we grow to the maximum size when a regexp
2348 is compiled.
2349 The register vectors, we adjust in size each time we
2350 compile a regexp, according to the number of registers it needs. */
2351
2352 static fail_stack_type fail_stack;
2353
2354 /* Size with which the following vectors are currently allocated.
2355 That is so we can make them bigger as needed,
2356 but never make them smaller. */
2357 static int regs_allocated_size;
2358
2359 static re_char ** regstart, ** regend;
2360 static re_char **best_regstart, **best_regend;
2361
2362 /* Make the register vectors big enough for NUM_REGS registers,
2363 but don't make them smaller. */
2364
2365 static
2366 regex_grow_registers (int num_regs)
2367 {
2368 if (num_regs > regs_allocated_size)
2369 {
2370 RETALLOC_IF (regstart, num_regs, re_char *);
2371 RETALLOC_IF (regend, num_regs, re_char *);
2372 RETALLOC_IF (best_regstart, num_regs, re_char *);
2373 RETALLOC_IF (best_regend, num_regs, re_char *);
2374
2375 regs_allocated_size = num_regs;
2376 }
2377 }
2378
2379 #endif /* not MATCH_MAY_ALLOCATE */
2380 \f
2381 static boolean group_in_compile_stack (compile_stack_type compile_stack,
2382 regnum_t regnum);
2383
2384 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2385 Returns one of error codes defined in `regex.h', or zero for success.
2386
2387 Assumes the `allocated' (and perhaps `buffer') and `translate'
2388 fields are set in BUFP on entry.
2389
2390 If it succeeds, results are put in BUFP (if it returns an error, the
2391 contents of BUFP are undefined):
2392 `buffer' is the compiled pattern;
2393 `syntax' is set to SYNTAX;
2394 `used' is set to the length of the compiled pattern;
2395 `fastmap_accurate' is zero;
2396 `re_nsub' is the number of subexpressions in PATTERN;
2397 `not_bol' and `not_eol' are zero;
2398
2399 The `fastmap' field is neither examined nor set. */
2400
2401 /* Insert the `jump' from the end of last alternative to "here".
2402 The space for the jump has already been allocated. */
2403 #define FIXUP_ALT_JUMP() \
2404 do { \
2405 if (fixup_alt_jump) \
2406 STORE_JUMP (jump, fixup_alt_jump, b); \
2407 } while (0)
2408
2409
2410 /* Return, freeing storage we allocated. */
2411 #define FREE_STACK_RETURN(value) \
2412 do { \
2413 FREE_RANGE_TABLE_WORK_AREA (range_table_work); \
2414 free (compile_stack.stack); \
2415 return value; \
2416 } while (0)
2417
2418 static reg_errcode_t
2419 regex_compile (const_re_char *pattern, size_t size, reg_syntax_t syntax,
2420 struct re_pattern_buffer *bufp)
2421 {
2422 /* We fetch characters from PATTERN here. */
2423 register re_wchar_t c, c1;
2424
2425 /* Points to the end of the buffer, where we should append. */
2426 register unsigned char *b;
2427
2428 /* Keeps track of unclosed groups. */
2429 compile_stack_type compile_stack;
2430
2431 /* Points to the current (ending) position in the pattern. */
2432 #ifdef AIX
2433 /* `const' makes AIX compiler fail. */
2434 unsigned char *p = pattern;
2435 #else
2436 re_char *p = pattern;
2437 #endif
2438 re_char *pend = pattern + size;
2439
2440 /* How to translate the characters in the pattern. */
2441 RE_TRANSLATE_TYPE translate = bufp->translate;
2442
2443 /* Address of the count-byte of the most recently inserted `exactn'
2444 command. This makes it possible to tell if a new exact-match
2445 character can be added to that command or if the character requires
2446 a new `exactn' command. */
2447 unsigned char *pending_exact = 0;
2448
2449 /* Address of start of the most recently finished expression.
2450 This tells, e.g., postfix * where to find the start of its
2451 operand. Reset at the beginning of groups and alternatives. */
2452 unsigned char *laststart = 0;
2453
2454 /* Address of beginning of regexp, or inside of last group. */
2455 unsigned char *begalt;
2456
2457 /* Place in the uncompiled pattern (i.e., the {) to
2458 which to go back if the interval is invalid. */
2459 re_char *beg_interval;
2460
2461 /* Address of the place where a forward jump should go to the end of
2462 the containing expression. Each alternative of an `or' -- except the
2463 last -- ends with a forward jump of this sort. */
2464 unsigned char *fixup_alt_jump = 0;
2465
2466 /* Work area for range table of charset. */
2467 struct range_table_work_area range_table_work;
2468
2469 /* If the object matched can contain multibyte characters. */
2470 const boolean multibyte = RE_MULTIBYTE_P (bufp);
2471
2472 /* Nonzero if we have pushed down into a subpattern. */
2473 int in_subpattern = 0;
2474
2475 /* These hold the values of p, pattern, and pend from the main
2476 pattern when we have pushed into a subpattern. */
2477 re_char *main_p IF_LINT (= NULL);
2478 re_char *main_pattern IF_LINT (= NULL);
2479 re_char *main_pend IF_LINT (= NULL);
2480
2481 #ifdef DEBUG
2482 debug++;
2483 DEBUG_PRINT ("\nCompiling pattern: ");
2484 if (debug > 0)
2485 {
2486 unsigned debug_count;
2487
2488 for (debug_count = 0; debug_count < size; debug_count++)
2489 putchar (pattern[debug_count]);
2490 putchar ('\n');
2491 }
2492 #endif /* DEBUG */
2493
2494 /* Initialize the compile stack. */
2495 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2496 if (compile_stack.stack == NULL)
2497 return REG_ESPACE;
2498
2499 compile_stack.size = INIT_COMPILE_STACK_SIZE;
2500 compile_stack.avail = 0;
2501
2502 range_table_work.table = 0;
2503 range_table_work.allocated = 0;
2504
2505 /* Initialize the pattern buffer. */
2506 bufp->syntax = syntax;
2507 bufp->fastmap_accurate = 0;
2508 bufp->not_bol = bufp->not_eol = 0;
2509 bufp->used_syntax = 0;
2510
2511 /* Set `used' to zero, so that if we return an error, the pattern
2512 printer (for debugging) will think there's no pattern. We reset it
2513 at the end. */
2514 bufp->used = 0;
2515
2516 /* Always count groups, whether or not bufp->no_sub is set. */
2517 bufp->re_nsub = 0;
2518
2519 #if !defined emacs && !defined SYNTAX_TABLE
2520 /* Initialize the syntax table. */
2521 init_syntax_once ();
2522 #endif
2523
2524 if (bufp->allocated == 0)
2525 {
2526 if (bufp->buffer)
2527 { /* If zero allocated, but buffer is non-null, try to realloc
2528 enough space. This loses if buffer's address is bogus, but
2529 that is the user's responsibility. */
2530 RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
2531 }
2532 else
2533 { /* Caller did not allocate a buffer. Do it for them. */
2534 bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
2535 }
2536 if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE);
2537
2538 bufp->allocated = INIT_BUF_SIZE;
2539 }
2540
2541 begalt = b = bufp->buffer;
2542
2543 /* Loop through the uncompiled pattern until we're at the end. */
2544 while (1)
2545 {
2546 if (p == pend)
2547 {
2548 /* If this is the end of an included regexp,
2549 pop back to the main regexp and try again. */
2550 if (in_subpattern)
2551 {
2552 in_subpattern = 0;
2553 pattern = main_pattern;
2554 p = main_p;
2555 pend = main_pend;
2556 continue;
2557 }
2558 /* If this is the end of the main regexp, we are done. */
2559 break;
2560 }
2561
2562 PATFETCH (c);
2563
2564 switch (c)
2565 {
2566 case ' ':
2567 {
2568 re_char *p1 = p;
2569
2570 /* If there's no special whitespace regexp, treat
2571 spaces normally. And don't try to do this recursively. */
2572 if (!whitespace_regexp || in_subpattern)
2573 goto normal_char;
2574
2575 /* Peek past following spaces. */
2576 while (p1 != pend)
2577 {
2578 if (*p1 != ' ')
2579 break;
2580 p1++;
2581 }
2582 /* If the spaces are followed by a repetition op,
2583 treat them normally. */
2584 if (p1 != pend
2585 && (*p1 == '*' || *p1 == '+' || *p1 == '?'
2586 || (*p1 == '\\' && p1 + 1 != pend && p1[1] == '{')))
2587 goto normal_char;
2588
2589 /* Replace the spaces with the whitespace regexp. */
2590 in_subpattern = 1;
2591 main_p = p1;
2592 main_pend = pend;
2593 main_pattern = pattern;
2594 p = pattern = whitespace_regexp;
2595 pend = p + strlen ((const char *) p);
2596 break;
2597 }
2598
2599 case '^':
2600 {
2601 if ( /* If at start of pattern, it's an operator. */
2602 p == pattern + 1
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);
2608 else
2609 goto normal_char;
2610 }
2611 break;
2612
2613
2614 case '$':
2615 {
2616 if ( /* If at end of pattern, it's an operator. */
2617 p == pend
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);
2623 else
2624 goto normal_char;
2625 }
2626 break;
2627
2628
2629 case '+':
2630 case '?':
2631 if ((syntax & RE_BK_PLUS_QM)
2632 || (syntax & RE_LIMITED_OPS))
2633 goto normal_char;
2634 handle_plus:
2635 case '*':
2636 /* If there is no previous pattern... */
2637 if (!laststart)
2638 {
2639 if (syntax & RE_CONTEXT_INVALID_OPS)
2640 FREE_STACK_RETURN (REG_BADRPT);
2641 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2642 goto normal_char;
2643 }
2644
2645 {
2646 /* 1 means zero (many) matches is allowed. */
2647 boolean zero_times_ok = 0, many_times_ok = 0;
2648 boolean greedy = 1;
2649
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. */
2654
2655 for (;;)
2656 {
2657 if ((syntax & RE_FRUGAL)
2658 && c == '?' && (zero_times_ok || many_times_ok))
2659 greedy = 0;
2660 else
2661 {
2662 zero_times_ok |= c != '+';
2663 many_times_ok |= c != '?';
2664 }
2665
2666 if (p == pend)
2667 break;
2668 else if (*p == '*'
2669 || (!(syntax & RE_BK_PLUS_QM)
2670 && (*p == '+' || *p == '?')))
2671 ;
2672 else if (syntax & RE_BK_PLUS_QM && *p == '\\')
2673 {
2674 if (p+1 == pend)
2675 FREE_STACK_RETURN (REG_EESCAPE);
2676 if (p[1] == '+' || p[1] == '?')
2677 PATFETCH (c); /* Gobble up the backslash. */
2678 else
2679 break;
2680 }
2681 else
2682 break;
2683 /* If we get here, we found another repeat character. */
2684 PATFETCH (c);
2685 }
2686
2687 /* Star, etc. applied to an empty pattern is equivalent
2688 to an empty pattern. */
2689 if (!laststart || laststart == b)
2690 break;
2691
2692 /* Now we know whether or not zero matches is allowed
2693 and also whether or not two or more matches is allowed. */
2694 if (greedy)
2695 {
2696 if (many_times_ok)
2697 {
2698 boolean simple = skip_one_char (laststart) == b;
2699 size_t startoffset = 0;
2700 re_opcode_t ofj =
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);
2705
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;
2714 while (p2 < p1)
2715 *b++ = *p2++;
2716 zero_times_ok = 1;
2717 }
2718
2719 GET_BUFFER_SPACE (6);
2720 if (!zero_times_ok)
2721 /* A + loop. */
2722 STORE_JUMP (ofj, b, b + 6);
2723 else
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);
2730 b += 3;
2731 STORE_JUMP (jump, b, laststart + startoffset);
2732 b += 3;
2733 }
2734 else
2735 {
2736 /* A simple ? pattern. */
2737 assert (zero_times_ok);
2738 GET_BUFFER_SPACE (3);
2739 INSERT_JUMP (on_failure_jump, laststart, b + 3);
2740 b += 3;
2741 }
2742 }
2743 else /* not greedy */
2744 { /* I wish the greedy and non-greedy cases could be merged. */
2745
2746 GET_BUFFER_SPACE (7); /* We might use less. */
2747 if (many_times_ok)
2748 {
2749 boolean emptyp = analyze_first (laststart, b, NULL, 0);
2750
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);
2757 b += 3;
2758 if (zero_times_ok)
2759 {
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);
2764 b += 3;
2765 }
2766 }
2767 else
2768 {
2769 /* non-greedy a?? */
2770 INSERT_JUMP (jump, laststart, b + 3);
2771 b += 3;
2772 INSERT_JUMP (on_failure_jump, laststart, laststart + 6);
2773 b += 3;
2774 }
2775 }
2776 }
2777 pending_exact = 0;
2778 break;
2779
2780
2781 case '.':
2782 laststart = b;
2783 BUF_PUSH (anychar);
2784 break;
2785
2786
2787 case '[':
2788 {
2789 re_char *p1;
2790
2791 CLEAR_RANGE_TABLE_WORK_USED (range_table_work);
2792
2793 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2794
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);
2798
2799 laststart = b;
2800
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);
2804 if (*p == '^')
2805 p++;
2806
2807 /* Remember the first position in the bracket expression. */
2808 p1 = p;
2809
2810 /* Push the number of bytes in the bitmap. */
2811 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
2812
2813 /* Clear the whole map. */
2814 memset (b, 0, (1 << BYTEWIDTH) / BYTEWIDTH);
2815
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');
2820
2821 /* Read in characters and ranges, setting map bits. */
2822 for (;;)
2823 {
2824 boolean escaped_char = false;
2825 const unsigned char *p2 = p;
2826 re_wchar_t ch;
2827
2828 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2829
2830 /* Don't translate yet. The range TRANSLATE(X..Y) cannot
2831 always be determined from TRANSLATE(X) and TRANSLATE(Y)
2832 So the translation is done later in a loop. Example:
2833 (let ((case-fold-search t)) (string-match "[A-_]" "A")) */
2834 PATFETCH (c);
2835
2836 /* \ might escape characters inside [...] and [^...]. */
2837 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2838 {
2839 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2840
2841 PATFETCH (c);
2842 escaped_char = true;
2843 }
2844 else
2845 {
2846 /* Could be the end of the bracket expression. If it's
2847 not (i.e., when the bracket expression is `[]' so
2848 far), the ']' character bit gets set way below. */
2849 if (c == ']' && p2 != p1)
2850 break;
2851 }
2852
2853 /* See if we're at the beginning of a possible character
2854 class. */
2855
2856 if (!escaped_char &&
2857 syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2858 {
2859 /* Leave room for the null. */
2860 unsigned char str[CHAR_CLASS_MAX_LENGTH + 1];
2861 const unsigned char *class_beg;
2862
2863 PATFETCH (c);
2864 c1 = 0;
2865 class_beg = p;
2866
2867 /* If pattern is `[[:'. */
2868 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2869
2870 for (;;)
2871 {
2872 PATFETCH (c);
2873 if ((c == ':' && *p == ']') || p == pend)
2874 break;
2875 if (c1 < CHAR_CLASS_MAX_LENGTH)
2876 str[c1++] = c;
2877 else
2878 /* This is in any case an invalid class name. */
2879 str[0] = '\0';
2880 }
2881 str[c1] = '\0';
2882
2883 /* If isn't a word bracketed by `[:' and `:]':
2884 undo the ending character, the letters, and
2885 leave the leading `:' and `[' (but set bits for
2886 them). */
2887 if (c == ':' && *p == ']')
2888 {
2889 re_wctype_t cc = re_wctype (str);
2890
2891 if (cc == 0)
2892 FREE_STACK_RETURN (REG_ECTYPE);
2893
2894 /* Throw away the ] at the end of the character
2895 class. */
2896 PATFETCH (c);
2897
2898 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2899
2900 #ifndef emacs
2901 for (ch = 0; ch < (1 << BYTEWIDTH); ++ch)
2902 if (re_iswctype (btowc (ch), cc))
2903 {
2904 c = TRANSLATE (ch);
2905 if (c < (1 << BYTEWIDTH))
2906 SET_LIST_BIT (c);
2907 }
2908 #else /* emacs */
2909 /* Most character classes in a multibyte match
2910 just set a flag. Exceptions are is_blank,
2911 is_digit, is_cntrl, and is_xdigit, since
2912 they can only match ASCII characters. We
2913 don't need to handle them for multibyte.
2914 They are distinguished by a negative wctype. */
2915
2916 /* Setup the gl_state object to its buffer-defined
2917 value. This hardcodes the buffer-global
2918 syntax-table for ASCII chars, while the other chars
2919 will obey syntax-table properties. It's not ideal,
2920 but it's the way it's been done until now. */
2921 SETUP_BUFFER_SYNTAX_TABLE ();
2922
2923 for (ch = 0; ch < 256; ++ch)
2924 {
2925 c = RE_CHAR_TO_MULTIBYTE (ch);
2926 if (! CHAR_BYTE8_P (c)
2927 && re_iswctype (c, cc))
2928 {
2929 SET_LIST_BIT (ch);
2930 c1 = TRANSLATE (c);
2931 if (c1 == c)
2932 continue;
2933 if (ASCII_CHAR_P (c1))
2934 SET_LIST_BIT (c1);
2935 else if ((c1 = RE_CHAR_TO_UNIBYTE (c1)) >= 0)
2936 SET_LIST_BIT (c1);
2937 }
2938 }
2939 SET_RANGE_TABLE_WORK_AREA_BIT
2940 (range_table_work, re_wctype_to_bit (cc));
2941 #endif /* emacs */
2942 /* In most cases the matching rule for char classes
2943 only uses the syntax table for multibyte chars,
2944 so that the content of the syntax-table is not
2945 hardcoded in the range_table. SPACE and WORD are
2946 the two exceptions. */
2947 if ((1 << cc) & ((1 << RECC_SPACE) | (1 << RECC_WORD)))
2948 bufp->used_syntax = 1;
2949
2950 /* Repeat the loop. */
2951 continue;
2952 }
2953 else
2954 {
2955 /* Go back to right after the "[:". */
2956 p = class_beg;
2957 SET_LIST_BIT ('[');
2958
2959 /* Because the `:' may start the range, we
2960 can't simply set bit and repeat the loop.
2961 Instead, just set it to C and handle below. */
2962 c = ':';
2963 }
2964 }
2965
2966 if (p < pend && p[0] == '-' && p[1] != ']')
2967 {
2968
2969 /* Discard the `-'. */
2970 PATFETCH (c1);
2971
2972 /* Fetch the character which ends the range. */
2973 PATFETCH (c1);
2974 #ifdef emacs
2975 if (CHAR_BYTE8_P (c1)
2976 && ! ASCII_CHAR_P (c) && ! CHAR_BYTE8_P (c))
2977 /* Treat the range from a multibyte character to
2978 raw-byte character as empty. */
2979 c = c1 + 1;
2980 #endif /* emacs */
2981 }
2982 else
2983 /* Range from C to C. */
2984 c1 = c;
2985
2986 if (c > c1)
2987 {
2988 if (syntax & RE_NO_EMPTY_RANGES)
2989 FREE_STACK_RETURN (REG_ERANGEX);
2990 /* Else, repeat the loop. */
2991 }
2992 else
2993 {
2994 #ifndef emacs
2995 /* Set the range into bitmap */
2996 for (; c <= c1; c++)
2997 {
2998 ch = TRANSLATE (c);
2999 if (ch < (1 << BYTEWIDTH))
3000 SET_LIST_BIT (ch);
3001 }
3002 #else /* emacs */
3003 if (c < 128)
3004 {
3005 ch = min (127, c1);
3006 SETUP_ASCII_RANGE (range_table_work, c, ch);
3007 c = ch + 1;
3008 if (CHAR_BYTE8_P (c1))
3009 c = BYTE8_TO_CHAR (128);
3010 }
3011 if (c <= c1)
3012 {
3013 if (CHAR_BYTE8_P (c))
3014 {
3015 c = CHAR_TO_BYTE8 (c);
3016 c1 = CHAR_TO_BYTE8 (c1);
3017 for (; c <= c1; c++)
3018 SET_LIST_BIT (c);
3019 }
3020 else if (multibyte)
3021 {
3022 SETUP_MULTIBYTE_RANGE (range_table_work, c, c1);
3023 }
3024 else
3025 {
3026 SETUP_UNIBYTE_RANGE (range_table_work, c, c1);
3027 }
3028 }
3029 #endif /* emacs */
3030 }
3031 }
3032
3033 /* Discard any (non)matching list bytes that are all 0 at the
3034 end of the map. Decrease the map-length byte too. */
3035 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
3036 b[-1]--;
3037 b += b[-1];
3038
3039 /* Build real range table from work area. */
3040 if (RANGE_TABLE_WORK_USED (range_table_work)
3041 || RANGE_TABLE_WORK_BITS (range_table_work))
3042 {
3043 int i;
3044 int used = RANGE_TABLE_WORK_USED (range_table_work);
3045
3046 /* Allocate space for COUNT + RANGE_TABLE. Needs two
3047 bytes for flags, two for COUNT, and three bytes for
3048 each character. */
3049 GET_BUFFER_SPACE (4 + used * 3);
3050
3051 /* Indicate the existence of range table. */
3052 laststart[1] |= 0x80;
3053
3054 /* Store the character class flag bits into the range table.
3055 If not in emacs, these flag bits are always 0. */
3056 *b++ = RANGE_TABLE_WORK_BITS (range_table_work) & 0xff;
3057 *b++ = RANGE_TABLE_WORK_BITS (range_table_work) >> 8;
3058
3059 STORE_NUMBER_AND_INCR (b, used / 2);
3060 for (i = 0; i < used; i++)
3061 STORE_CHARACTER_AND_INCR
3062 (b, RANGE_TABLE_WORK_ELT (range_table_work, i));
3063 }
3064 }
3065 break;
3066
3067
3068 case '(':
3069 if (syntax & RE_NO_BK_PARENS)
3070 goto handle_open;
3071 else
3072 goto normal_char;
3073
3074
3075 case ')':
3076 if (syntax & RE_NO_BK_PARENS)
3077 goto handle_close;
3078 else
3079 goto normal_char;
3080
3081
3082 case '\n':
3083 if (syntax & RE_NEWLINE_ALT)
3084 goto handle_alt;
3085 else
3086 goto normal_char;
3087
3088
3089 case '|':
3090 if (syntax & RE_NO_BK_VBAR)
3091 goto handle_alt;
3092 else
3093 goto normal_char;
3094
3095
3096 case '{':
3097 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
3098 goto handle_interval;
3099 else
3100 goto normal_char;
3101
3102
3103 case '\\':
3104 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3105
3106 /* Do not translate the character after the \, so that we can
3107 distinguish, e.g., \B from \b, even if we normally would
3108 translate, e.g., B to b. */
3109 PATFETCH (c);
3110
3111 switch (c)
3112 {
3113 case '(':
3114 if (syntax & RE_NO_BK_PARENS)
3115 goto normal_backslash;
3116
3117 handle_open:
3118 {
3119 int shy = 0;
3120 regnum_t regnum = 0;
3121 if (p+1 < pend)
3122 {
3123 /* Look for a special (?...) construct */
3124 if ((syntax & RE_SHY_GROUPS) && *p == '?')
3125 {
3126 PATFETCH (c); /* Gobble up the '?'. */
3127 while (!shy)
3128 {
3129 PATFETCH (c);
3130 switch (c)
3131 {
3132 case ':': shy = 1; break;
3133 case '0':
3134 /* An explicitly specified regnum must start
3135 with non-0. */
3136 if (regnum == 0)
3137 FREE_STACK_RETURN (REG_BADPAT);
3138 case '1': case '2': case '3': case '4':
3139 case '5': case '6': case '7': case '8': case '9':
3140 regnum = 10*regnum + (c - '0'); break;
3141 default:
3142 /* Only (?:...) is supported right now. */
3143 FREE_STACK_RETURN (REG_BADPAT);
3144 }
3145 }
3146 }
3147 }
3148
3149 if (!shy)
3150 regnum = ++bufp->re_nsub;
3151 else if (regnum)
3152 { /* It's actually not shy, but explicitly numbered. */
3153 shy = 0;
3154 if (regnum > bufp->re_nsub)
3155 bufp->re_nsub = regnum;
3156 else if (regnum > bufp->re_nsub
3157 /* Ideally, we'd want to check that the specified
3158 group can't have matched (i.e. all subgroups
3159 using the same regnum are in other branches of
3160 OR patterns), but we don't currently keep track
3161 of enough info to do that easily. */
3162 || group_in_compile_stack (compile_stack, regnum))
3163 FREE_STACK_RETURN (REG_BADPAT);
3164 }
3165 else
3166 /* It's really shy. */
3167 regnum = - bufp->re_nsub;
3168
3169 if (COMPILE_STACK_FULL)
3170 {
3171 RETALLOC (compile_stack.stack, compile_stack.size << 1,
3172 compile_stack_elt_t);
3173 if (compile_stack.stack == NULL) return REG_ESPACE;
3174
3175 compile_stack.size <<= 1;
3176 }
3177
3178 /* These are the values to restore when we hit end of this
3179 group. They are all relative offsets, so that if the
3180 whole pattern moves because of realloc, they will still
3181 be valid. */
3182 COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
3183 COMPILE_STACK_TOP.fixup_alt_jump
3184 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
3185 COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
3186 COMPILE_STACK_TOP.regnum = regnum;
3187
3188 /* Do not push a start_memory for groups beyond the last one
3189 we can represent in the compiled pattern. */
3190 if (regnum <= MAX_REGNUM && regnum > 0)
3191 BUF_PUSH_2 (start_memory, regnum);
3192
3193 compile_stack.avail++;
3194
3195 fixup_alt_jump = 0;
3196 laststart = 0;
3197 begalt = b;
3198 /* If we've reached MAX_REGNUM groups, then this open
3199 won't actually generate any code, so we'll have to
3200 clear pending_exact explicitly. */
3201 pending_exact = 0;
3202 break;
3203 }
3204
3205 case ')':
3206 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
3207
3208 if (COMPILE_STACK_EMPTY)
3209 {
3210 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3211 goto normal_backslash;
3212 else
3213 FREE_STACK_RETURN (REG_ERPAREN);
3214 }
3215
3216 handle_close:
3217 FIXUP_ALT_JUMP ();
3218
3219 /* See similar code for backslashed left paren above. */
3220 if (COMPILE_STACK_EMPTY)
3221 {
3222 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3223 goto normal_char;
3224 else
3225 FREE_STACK_RETURN (REG_ERPAREN);
3226 }
3227
3228 /* Since we just checked for an empty stack above, this
3229 ``can't happen''. */
3230 assert (compile_stack.avail != 0);
3231 {
3232 /* We don't just want to restore into `regnum', because
3233 later groups should continue to be numbered higher,
3234 as in `(ab)c(de)' -- the second group is #2. */
3235 regnum_t regnum;
3236
3237 compile_stack.avail--;
3238 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
3239 fixup_alt_jump
3240 = COMPILE_STACK_TOP.fixup_alt_jump
3241 ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
3242 : 0;
3243 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
3244 regnum = COMPILE_STACK_TOP.regnum;
3245 /* If we've reached MAX_REGNUM groups, then this open
3246 won't actually generate any code, so we'll have to
3247 clear pending_exact explicitly. */
3248 pending_exact = 0;
3249
3250 /* We're at the end of the group, so now we know how many
3251 groups were inside this one. */
3252 if (regnum <= MAX_REGNUM && regnum > 0)
3253 BUF_PUSH_2 (stop_memory, regnum);
3254 }
3255 break;
3256
3257
3258 case '|': /* `\|'. */
3259 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
3260 goto normal_backslash;
3261 handle_alt:
3262 if (syntax & RE_LIMITED_OPS)
3263 goto normal_char;
3264
3265 /* Insert before the previous alternative a jump which
3266 jumps to this alternative if the former fails. */
3267 GET_BUFFER_SPACE (3);
3268 INSERT_JUMP (on_failure_jump, begalt, b + 6);
3269 pending_exact = 0;
3270 b += 3;
3271
3272 /* The alternative before this one has a jump after it
3273 which gets executed if it gets matched. Adjust that
3274 jump so it will jump to this alternative's analogous
3275 jump (put in below, which in turn will jump to the next
3276 (if any) alternative's such jump, etc.). The last such
3277 jump jumps to the correct final destination. A picture:
3278 _____ _____
3279 | | | |
3280 | v | v
3281 a | b | c
3282
3283 If we are at `b', then fixup_alt_jump right now points to a
3284 three-byte space after `a'. We'll put in the jump, set
3285 fixup_alt_jump to right after `b', and leave behind three
3286 bytes which we'll fill in when we get to after `c'. */
3287
3288 FIXUP_ALT_JUMP ();
3289
3290 /* Mark and leave space for a jump after this alternative,
3291 to be filled in later either by next alternative or
3292 when know we're at the end of a series of alternatives. */
3293 fixup_alt_jump = b;
3294 GET_BUFFER_SPACE (3);
3295 b += 3;
3296
3297 laststart = 0;
3298 begalt = b;
3299 break;
3300
3301
3302 case '{':
3303 /* If \{ is a literal. */
3304 if (!(syntax & RE_INTERVALS)
3305 /* If we're at `\{' and it's not the open-interval
3306 operator. */
3307 || (syntax & RE_NO_BK_BRACES))
3308 goto normal_backslash;
3309
3310 handle_interval:
3311 {
3312 /* If got here, then the syntax allows intervals. */
3313
3314 /* At least (most) this many matches must be made. */
3315 int lower_bound = 0, upper_bound = -1;
3316
3317 beg_interval = p;
3318
3319 GET_INTERVAL_COUNT (lower_bound);
3320
3321 if (c == ',')
3322 GET_INTERVAL_COUNT (upper_bound);
3323 else
3324 /* Interval such as `{1}' => match exactly once. */
3325 upper_bound = lower_bound;
3326
3327 if (lower_bound < 0
3328 || (0 <= upper_bound && upper_bound < lower_bound))
3329 FREE_STACK_RETURN (REG_BADBR);
3330
3331 if (!(syntax & RE_NO_BK_BRACES))
3332 {
3333 if (c != '\\')
3334 FREE_STACK_RETURN (REG_BADBR);
3335 if (p == pend)
3336 FREE_STACK_RETURN (REG_EESCAPE);
3337 PATFETCH (c);
3338 }
3339
3340 if (c != '}')
3341 FREE_STACK_RETURN (REG_BADBR);
3342
3343 /* We just parsed a valid interval. */
3344
3345 /* If it's invalid to have no preceding re. */
3346 if (!laststart)
3347 {
3348 if (syntax & RE_CONTEXT_INVALID_OPS)
3349 FREE_STACK_RETURN (REG_BADRPT);
3350 else if (syntax & RE_CONTEXT_INDEP_OPS)
3351 laststart = b;
3352 else
3353 goto unfetch_interval;
3354 }
3355
3356 if (upper_bound == 0)
3357 /* If the upper bound is zero, just drop the sub pattern
3358 altogether. */
3359 b = laststart;
3360 else if (lower_bound == 1 && upper_bound == 1)
3361 /* Just match it once: nothing to do here. */
3362 ;
3363
3364 /* Otherwise, we have a nontrivial interval. When
3365 we're all done, the pattern will look like:
3366 set_number_at <jump count> <upper bound>
3367 set_number_at <succeed_n count> <lower bound>
3368 succeed_n <after jump addr> <succeed_n count>
3369 <body of loop>
3370 jump_n <succeed_n addr> <jump count>
3371 (The upper bound and `jump_n' are omitted if
3372 `upper_bound' is 1, though.) */
3373 else
3374 { /* If the upper bound is > 1, we need to insert
3375 more at the end of the loop. */
3376 unsigned int nbytes = (upper_bound < 0 ? 3
3377 : upper_bound > 1 ? 5 : 0);
3378 unsigned int startoffset = 0;
3379
3380 GET_BUFFER_SPACE (20); /* We might use less. */
3381
3382 if (lower_bound == 0)
3383 {
3384 /* A succeed_n that starts with 0 is really a
3385 a simple on_failure_jump_loop. */
3386 INSERT_JUMP (on_failure_jump_loop, laststart,
3387 b + 3 + nbytes);
3388 b += 3;
3389 }
3390 else
3391 {
3392 /* Initialize lower bound of the `succeed_n', even
3393 though it will be set during matching by its
3394 attendant `set_number_at' (inserted next),
3395 because `re_compile_fastmap' needs to know.
3396 Jump to the `jump_n' we might insert below. */
3397 INSERT_JUMP2 (succeed_n, laststart,
3398 b + 5 + nbytes,
3399 lower_bound);
3400 b += 5;
3401
3402 /* Code to initialize the lower bound. Insert
3403 before the `succeed_n'. The `5' is the last two
3404 bytes of this `set_number_at', plus 3 bytes of
3405 the following `succeed_n'. */
3406 insert_op2 (set_number_at, laststart, 5, lower_bound, b);
3407 b += 5;
3408 startoffset += 5;
3409 }
3410
3411 if (upper_bound < 0)
3412 {
3413 /* A negative upper bound stands for infinity,
3414 in which case it degenerates to a plain jump. */
3415 STORE_JUMP (jump, b, laststart + startoffset);
3416 b += 3;
3417 }
3418 else if (upper_bound > 1)
3419 { /* More than one repetition is allowed, so
3420 append a backward jump to the `succeed_n'
3421 that starts this interval.
3422
3423 When we've reached this during matching,
3424 we'll have matched the interval once, so
3425 jump back only `upper_bound - 1' times. */
3426 STORE_JUMP2 (jump_n, b, laststart + startoffset,
3427 upper_bound - 1);
3428 b += 5;
3429
3430 /* The location we want to set is the second
3431 parameter of the `jump_n'; that is `b-2' as
3432 an absolute address. `laststart' will be
3433 the `set_number_at' we're about to insert;
3434 `laststart+3' the number to set, the source
3435 for the relative address. But we are
3436 inserting into the middle of the pattern --
3437 so everything is getting moved up by 5.
3438 Conclusion: (b - 2) - (laststart + 3) + 5,
3439 i.e., b - laststart.
3440
3441 We insert this at the beginning of the loop
3442 so that if we fail during matching, we'll
3443 reinitialize the bounds. */
3444 insert_op2 (set_number_at, laststart, b - laststart,
3445 upper_bound - 1, b);
3446 b += 5;
3447 }
3448 }
3449 pending_exact = 0;
3450 beg_interval = NULL;
3451 }
3452 break;
3453
3454 unfetch_interval:
3455 /* If an invalid interval, match the characters as literals. */
3456 assert (beg_interval);
3457 p = beg_interval;
3458 beg_interval = NULL;
3459
3460 /* normal_char and normal_backslash need `c'. */
3461 c = '{';
3462
3463 if (!(syntax & RE_NO_BK_BRACES))
3464 {
3465 assert (p > pattern && p[-1] == '\\');
3466 goto normal_backslash;
3467 }
3468 else
3469 goto normal_char;
3470
3471 #ifdef emacs
3472 /* There is no way to specify the before_dot and after_dot
3473 operators. rms says this is ok. --karl */
3474 case '=':
3475 laststart = b;
3476 BUF_PUSH (at_dot);
3477 break;
3478
3479 case 's':
3480 laststart = b;
3481 PATFETCH (c);
3482 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
3483 break;
3484
3485 case 'S':
3486 laststart = b;
3487 PATFETCH (c);
3488 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
3489 break;
3490
3491 case 'c':
3492 laststart = b;
3493 PATFETCH (c);
3494 BUF_PUSH_2 (categoryspec, c);
3495 break;
3496
3497 case 'C':
3498 laststart = b;
3499 PATFETCH (c);
3500 BUF_PUSH_2 (notcategoryspec, c);
3501 break;
3502 #endif /* emacs */
3503
3504
3505 case 'w':
3506 if (syntax & RE_NO_GNU_OPS)
3507 goto normal_char;
3508 laststart = b;
3509 BUF_PUSH_2 (syntaxspec, Sword);
3510 break;
3511
3512
3513 case 'W':
3514 if (syntax & RE_NO_GNU_OPS)
3515 goto normal_char;
3516 laststart = b;
3517 BUF_PUSH_2 (notsyntaxspec, Sword);
3518 break;
3519
3520
3521 case '<':
3522 if (syntax & RE_NO_GNU_OPS)
3523 goto normal_char;
3524 laststart = b;
3525 BUF_PUSH (wordbeg);
3526 break;
3527
3528 case '>':
3529 if (syntax & RE_NO_GNU_OPS)
3530 goto normal_char;
3531 laststart = b;
3532 BUF_PUSH (wordend);
3533 break;
3534
3535 case '_':
3536 if (syntax & RE_NO_GNU_OPS)
3537 goto normal_char;
3538 laststart = b;
3539 PATFETCH (c);
3540 if (c == '<')
3541 BUF_PUSH (symbeg);
3542 else if (c == '>')
3543 BUF_PUSH (symend);
3544 else
3545 FREE_STACK_RETURN (REG_BADPAT);
3546 break;
3547
3548 case 'b':
3549 if (syntax & RE_NO_GNU_OPS)
3550 goto normal_char;
3551 BUF_PUSH (wordbound);
3552 break;
3553
3554 case 'B':
3555 if (syntax & RE_NO_GNU_OPS)
3556 goto normal_char;
3557 BUF_PUSH (notwordbound);
3558 break;
3559
3560 case '`':
3561 if (syntax & RE_NO_GNU_OPS)
3562 goto normal_char;
3563 BUF_PUSH (begbuf);
3564 break;
3565
3566 case '\'':
3567 if (syntax & RE_NO_GNU_OPS)
3568 goto normal_char;
3569 BUF_PUSH (endbuf);
3570 break;
3571
3572 case '1': case '2': case '3': case '4': case '5':
3573 case '6': case '7': case '8': case '9':
3574 {
3575 regnum_t reg;
3576
3577 if (syntax & RE_NO_BK_REFS)
3578 goto normal_backslash;
3579
3580 reg = c - '0';
3581
3582 if (reg > bufp->re_nsub || reg < 1
3583 /* Can't back reference to a subexp before its end. */
3584 || group_in_compile_stack (compile_stack, reg))
3585 FREE_STACK_RETURN (REG_ESUBREG);
3586
3587 laststart = b;
3588 BUF_PUSH_2 (duplicate, reg);
3589 }
3590 break;
3591
3592
3593 case '+':
3594 case '?':
3595 if (syntax & RE_BK_PLUS_QM)
3596 goto handle_plus;
3597 else
3598 goto normal_backslash;
3599
3600 default:
3601 normal_backslash:
3602 /* You might think it would be useful for \ to mean
3603 not to translate; but if we don't translate it
3604 it will never match anything. */
3605 goto normal_char;
3606 }
3607 break;
3608
3609
3610 default:
3611 /* Expects the character in `c'. */
3612 normal_char:
3613 /* If no exactn currently being built. */
3614 if (!pending_exact
3615
3616 /* If last exactn not at current position. */
3617 || pending_exact + *pending_exact + 1 != b
3618
3619 /* We have only one byte following the exactn for the count. */
3620 || *pending_exact >= (1 << BYTEWIDTH) - MAX_MULTIBYTE_LENGTH
3621
3622 /* If followed by a repetition operator. */
3623 || (p != pend && (*p == '*' || *p == '^'))
3624 || ((syntax & RE_BK_PLUS_QM)
3625 ? p + 1 < pend && *p == '\\' && (p[1] == '+' || p[1] == '?')
3626 : p != pend && (*p == '+' || *p == '?'))
3627 || ((syntax & RE_INTERVALS)
3628 && ((syntax & RE_NO_BK_BRACES)
3629 ? p != pend && *p == '{'
3630 : p + 1 < pend && p[0] == '\\' && p[1] == '{')))
3631 {
3632 /* Start building a new exactn. */
3633
3634 laststart = b;
3635
3636 BUF_PUSH_2 (exactn, 0);
3637 pending_exact = b - 1;
3638 }
3639
3640 GET_BUFFER_SPACE (MAX_MULTIBYTE_LENGTH);
3641 {
3642 int len;
3643
3644 if (multibyte)
3645 {
3646 c = TRANSLATE (c);
3647 len = CHAR_STRING (c, b);
3648 b += len;
3649 }
3650 else
3651 {
3652 c1 = RE_CHAR_TO_MULTIBYTE (c);
3653 if (! CHAR_BYTE8_P (c1))
3654 {
3655 re_wchar_t c2 = TRANSLATE (c1);
3656
3657 if (c1 != c2 && (c1 = RE_CHAR_TO_UNIBYTE (c2)) >= 0)
3658 c = c1;
3659 }
3660 *b++ = c;
3661 len = 1;
3662 }
3663 (*pending_exact) += len;
3664 }
3665
3666 break;
3667 } /* switch (c) */
3668 } /* while p != pend */
3669
3670
3671 /* Through the pattern now. */
3672
3673 FIXUP_ALT_JUMP ();
3674
3675 if (!COMPILE_STACK_EMPTY)
3676 FREE_STACK_RETURN (REG_EPAREN);
3677
3678 /* If we don't want backtracking, force success
3679 the first time we reach the end of the compiled pattern. */
3680 if (syntax & RE_NO_POSIX_BACKTRACKING)
3681 BUF_PUSH (succeed);
3682
3683 /* We have succeeded; set the length of the buffer. */
3684 bufp->used = b - bufp->buffer;
3685
3686 #ifdef DEBUG
3687 if (debug > 0)
3688 {
3689 re_compile_fastmap (bufp);
3690 DEBUG_PRINT ("\nCompiled pattern: \n");
3691 print_compiled_pattern (bufp);
3692 }
3693 debug--;
3694 #endif /* DEBUG */
3695
3696 #ifndef MATCH_MAY_ALLOCATE
3697 /* Initialize the failure stack to the largest possible stack. This
3698 isn't necessary unless we're trying to avoid calling alloca in
3699 the search and match routines. */
3700 {
3701 int num_regs = bufp->re_nsub + 1;
3702
3703 if (fail_stack.size < re_max_failures * TYPICAL_FAILURE_SIZE)
3704 {
3705 fail_stack.size = re_max_failures * TYPICAL_FAILURE_SIZE;
3706 falk_stack.stack = realloc (fail_stack.stack,
3707 fail_stack.size * sizeof *falk_stack.stack);
3708 }
3709
3710 regex_grow_registers (num_regs);
3711 }
3712 #endif /* not MATCH_MAY_ALLOCATE */
3713
3714 FREE_STACK_RETURN (REG_NOERROR);
3715 } /* regex_compile */
3716 \f
3717 /* Subroutines for `regex_compile'. */
3718
3719 /* Store OP at LOC followed by two-byte integer parameter ARG. */
3720
3721 static void
3722 store_op1 (re_opcode_t op, unsigned char *loc, int arg)
3723 {
3724 *loc = (unsigned char) op;
3725 STORE_NUMBER (loc + 1, arg);
3726 }
3727
3728
3729 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
3730
3731 static void
3732 store_op2 (re_opcode_t op, unsigned char *loc, int arg1, int arg2)
3733 {
3734 *loc = (unsigned char) op;
3735 STORE_NUMBER (loc + 1, arg1);
3736 STORE_NUMBER (loc + 3, arg2);
3737 }
3738
3739
3740 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
3741 for OP followed by two-byte integer parameter ARG. */
3742
3743 static void
3744 insert_op1 (re_opcode_t op, unsigned char *loc, int arg, unsigned char *end)
3745 {
3746 register unsigned char *pfrom = end;
3747 register unsigned char *pto = end + 3;
3748
3749 while (pfrom != loc)
3750 *--pto = *--pfrom;
3751
3752 store_op1 (op, loc, arg);
3753 }
3754
3755
3756 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
3757
3758 static void
3759 insert_op2 (re_opcode_t op, unsigned char *loc, int arg1, int arg2, unsigned char *end)
3760 {
3761 register unsigned char *pfrom = end;
3762 register unsigned char *pto = end + 5;
3763
3764 while (pfrom != loc)
3765 *--pto = *--pfrom;
3766
3767 store_op2 (op, loc, arg1, arg2);
3768 }
3769
3770
3771 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
3772 after an alternative or a begin-subexpression. We assume there is at
3773 least one character before the ^. */
3774
3775 static boolean
3776 at_begline_loc_p (const_re_char *pattern, const_re_char *p, reg_syntax_t syntax)
3777 {
3778 re_char *prev = p - 2;
3779 boolean odd_backslashes;
3780
3781 /* After a subexpression? */
3782 if (*prev == '(')
3783 odd_backslashes = (syntax & RE_NO_BK_PARENS) == 0;
3784
3785 /* After an alternative? */
3786 else if (*prev == '|')
3787 odd_backslashes = (syntax & RE_NO_BK_VBAR) == 0;
3788
3789 /* After a shy subexpression? */
3790 else if (*prev == ':' && (syntax & RE_SHY_GROUPS))
3791 {
3792 /* Skip over optional regnum. */
3793 while (prev - 1 >= pattern && prev[-1] >= '0' && prev[-1] <= '9')
3794 --prev;
3795
3796 if (!(prev - 2 >= pattern
3797 && prev[-1] == '?' && prev[-2] == '('))
3798 return false;
3799 prev -= 2;
3800 odd_backslashes = (syntax & RE_NO_BK_PARENS) == 0;
3801 }
3802 else
3803 return false;
3804
3805 /* Count the number of preceding backslashes. */
3806 p = prev;
3807 while (prev - 1 >= pattern && prev[-1] == '\\')
3808 --prev;
3809 return (p - prev) & odd_backslashes;
3810 }
3811
3812
3813 /* The dual of at_begline_loc_p. This one is for $. We assume there is
3814 at least one character after the $, i.e., `P < PEND'. */
3815
3816 static boolean
3817 at_endline_loc_p (const_re_char *p, const_re_char *pend, reg_syntax_t syntax)
3818 {
3819 re_char *next = p;
3820 boolean next_backslash = *next == '\\';
3821 re_char *next_next = p + 1 < pend ? p + 1 : 0;
3822
3823 return
3824 /* Before a subexpression? */
3825 (syntax & RE_NO_BK_PARENS ? *next == ')'
3826 : next_backslash && next_next && *next_next == ')')
3827 /* Before an alternative? */
3828 || (syntax & RE_NO_BK_VBAR ? *next == '|'
3829 : next_backslash && next_next && *next_next == '|');
3830 }
3831
3832
3833 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
3834 false if it's not. */
3835
3836 static boolean
3837 group_in_compile_stack (compile_stack_type compile_stack, regnum_t regnum)
3838 {
3839 ssize_t this_element;
3840
3841 for (this_element = compile_stack.avail - 1;
3842 this_element >= 0;
3843 this_element--)
3844 if (compile_stack.stack[this_element].regnum == regnum)
3845 return true;
3846
3847 return false;
3848 }
3849 \f
3850 /* analyze_first.
3851 If fastmap is non-NULL, go through the pattern and fill fastmap
3852 with all the possible leading chars. If fastmap is NULL, don't
3853 bother filling it up (obviously) and only return whether the
3854 pattern could potentially match the empty string.
3855
3856 Return 1 if p..pend might match the empty string.
3857 Return 0 if p..pend matches at least one char.
3858 Return -1 if fastmap was not updated accurately. */
3859
3860 static int
3861 analyze_first (const_re_char *p, const_re_char *pend, char *fastmap,
3862 const int multibyte)
3863 {
3864 int j, k;
3865 boolean not;
3866
3867 /* If all elements for base leading-codes in fastmap is set, this
3868 flag is set true. */
3869 boolean match_any_multibyte_characters = false;
3870
3871 assert (p);
3872
3873 /* The loop below works as follows:
3874 - It has a working-list kept in the PATTERN_STACK and which basically
3875 starts by only containing a pointer to the first operation.
3876 - If the opcode we're looking at is a match against some set of
3877 chars, then we add those chars to the fastmap and go on to the
3878 next work element from the worklist (done via `break').
3879 - If the opcode is a control operator on the other hand, we either
3880 ignore it (if it's meaningless at this point, such as `start_memory')
3881 or execute it (if it's a jump). If the jump has several destinations
3882 (i.e. `on_failure_jump'), then we push the other destination onto the
3883 worklist.
3884 We guarantee termination by ignoring backward jumps (more or less),
3885 so that `p' is monotonically increasing. More to the point, we
3886 never set `p' (or push) anything `<= p1'. */
3887
3888 while (p < pend)
3889 {
3890 /* `p1' is used as a marker of how far back a `on_failure_jump'
3891 can go without being ignored. It is normally equal to `p'
3892 (which prevents any backward `on_failure_jump') except right
3893 after a plain `jump', to allow patterns such as:
3894 0: jump 10
3895 3..9: <body>
3896 10: on_failure_jump 3
3897 as used for the *? operator. */
3898 re_char *p1 = p;
3899
3900 switch (*p++)
3901 {
3902 case succeed:
3903 return 1;
3904
3905 case duplicate:
3906 /* If the first character has to match a backreference, that means
3907 that the group was empty (since it already matched). Since this
3908 is the only case that interests us here, we can assume that the
3909 backreference must match the empty string. */
3910 p++;
3911 continue;
3912
3913
3914 /* Following are the cases which match a character. These end
3915 with `break'. */
3916
3917 case exactn:
3918 if (fastmap)
3919 {
3920 /* If multibyte is nonzero, the first byte of each
3921 character is an ASCII or a leading code. Otherwise,
3922 each byte is a character. Thus, this works in both
3923 cases. */
3924 fastmap[p[1]] = 1;
3925 if (! multibyte)
3926 {
3927 /* For the case of matching this unibyte regex
3928 against multibyte, we must set a leading code of
3929 the corresponding multibyte character. */
3930 int c = RE_CHAR_TO_MULTIBYTE (p[1]);
3931
3932 fastmap[CHAR_LEADING_CODE (c)] = 1;
3933 }
3934 }
3935 break;
3936
3937
3938 case anychar:
3939 /* We could put all the chars except for \n (and maybe \0)
3940 but we don't bother since it is generally not worth it. */
3941 if (!fastmap) break;
3942 return -1;
3943
3944
3945 case charset_not:
3946 if (!fastmap) break;
3947 {
3948 /* Chars beyond end of bitmap are possible matches. */
3949 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH;
3950 j < (1 << BYTEWIDTH); j++)
3951 fastmap[j] = 1;
3952 }
3953
3954 /* Fallthrough */
3955 case charset:
3956 if (!fastmap) break;
3957 not = (re_opcode_t) *(p - 1) == charset_not;
3958 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++;
3959 j >= 0; j--)
3960 if (!!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) ^ not)
3961 fastmap[j] = 1;
3962
3963 #ifdef emacs
3964 if (/* Any leading code can possibly start a character
3965 which doesn't match the specified set of characters. */
3966 not
3967 ||
3968 /* If we can match a character class, we can match any
3969 multibyte characters. */
3970 (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
3971 && CHARSET_RANGE_TABLE_BITS (&p[-2]) != 0))
3972
3973 {
3974 if (match_any_multibyte_characters == false)
3975 {
3976 for (j = MIN_MULTIBYTE_LEADING_CODE;
3977 j <= MAX_MULTIBYTE_LEADING_CODE; j++)
3978 fastmap[j] = 1;
3979 match_any_multibyte_characters = true;
3980 }
3981 }
3982
3983 else if (!not && CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
3984 && match_any_multibyte_characters == false)
3985 {
3986 /* Set fastmap[I] to 1 where I is a leading code of each
3987 multibyte character in the range table. */
3988 int c, count;
3989 unsigned char lc1, lc2;
3990
3991 /* Make P points the range table. `+ 2' is to skip flag
3992 bits for a character class. */
3993 p += CHARSET_BITMAP_SIZE (&p[-2]) + 2;
3994
3995 /* Extract the number of ranges in range table into COUNT. */
3996 EXTRACT_NUMBER_AND_INCR (count, p);
3997 for (; count > 0; count--, p += 3)
3998 {
3999 /* Extract the start and end of each range. */
4000 EXTRACT_CHARACTER (c, p);
4001 lc1 = CHAR_LEADING_CODE (c);
4002 p += 3;
4003 EXTRACT_CHARACTER (c, p);
4004 lc2 = CHAR_LEADING_CODE (c);
4005 for (j = lc1; j <= lc2; j++)
4006 fastmap[j] = 1;
4007 }
4008 }
4009 #endif
4010 break;
4011
4012 case syntaxspec:
4013 case notsyntaxspec:
4014 if (!fastmap) break;
4015 #ifndef emacs
4016 not = (re_opcode_t)p[-1] == notsyntaxspec;
4017 k = *p++;
4018 for (j = 0; j < (1 << BYTEWIDTH); j++)
4019 if ((SYNTAX (j) == (enum syntaxcode) k) ^ not)
4020 fastmap[j] = 1;
4021 break;
4022 #else /* emacs */
4023 /* This match depends on text properties. These end with
4024 aborting optimizations. */
4025 return -1;
4026
4027 case categoryspec:
4028 case notcategoryspec:
4029 if (!fastmap) break;
4030 not = (re_opcode_t)p[-1] == notcategoryspec;
4031 k = *p++;
4032 for (j = (1 << BYTEWIDTH); j >= 0; j--)
4033 if ((CHAR_HAS_CATEGORY (j, k)) ^ not)
4034 fastmap[j] = 1;
4035
4036 /* Any leading code can possibly start a character which
4037 has or doesn't has the specified category. */
4038 if (match_any_multibyte_characters == false)
4039 {
4040 for (j = MIN_MULTIBYTE_LEADING_CODE;
4041 j <= MAX_MULTIBYTE_LEADING_CODE; j++)
4042 fastmap[j] = 1;
4043 match_any_multibyte_characters = true;
4044 }
4045 break;
4046
4047 /* All cases after this match the empty string. These end with
4048 `continue'. */
4049
4050 case before_dot:
4051 case at_dot:
4052 case after_dot:
4053 #endif /* !emacs */
4054 case no_op:
4055 case begline:
4056 case endline:
4057 case begbuf:
4058 case endbuf:
4059 case wordbound:
4060 case notwordbound:
4061 case wordbeg:
4062 case wordend:
4063 case symbeg:
4064 case symend:
4065 continue;
4066
4067
4068 case jump:
4069 EXTRACT_NUMBER_AND_INCR (j, p);
4070 if (j < 0)
4071 /* Backward jumps can only go back to code that we've already
4072 visited. `re_compile' should make sure this is true. */
4073 break;
4074 p += j;
4075 switch (*p)
4076 {
4077 case on_failure_jump:
4078 case on_failure_keep_string_jump:
4079 case on_failure_jump_loop:
4080 case on_failure_jump_nastyloop:
4081 case on_failure_jump_smart:
4082 p++;
4083 break;
4084 default:
4085 continue;
4086 };
4087 /* Keep `p1' to allow the `on_failure_jump' we are jumping to
4088 to jump back to "just after here". */
4089 /* Fallthrough */
4090
4091 case on_failure_jump:
4092 case on_failure_keep_string_jump:
4093 case on_failure_jump_nastyloop:
4094 case on_failure_jump_loop:
4095 case on_failure_jump_smart:
4096 EXTRACT_NUMBER_AND_INCR (j, p);
4097 if (p + j <= p1)
4098 ; /* Backward jump to be ignored. */
4099 else
4100 { /* We have to look down both arms.
4101 We first go down the "straight" path so as to minimize
4102 stack usage when going through alternatives. */
4103 int r = analyze_first (p, pend, fastmap, multibyte);
4104 if (r) return r;
4105 p += j;
4106 }
4107 continue;
4108
4109
4110 case jump_n:
4111 /* This code simply does not properly handle forward jump_n. */
4112 DEBUG_STATEMENT (EXTRACT_NUMBER (j, p); assert (j < 0));
4113 p += 4;
4114 /* jump_n can either jump or fall through. The (backward) jump
4115 case has already been handled, so we only need to look at the
4116 fallthrough case. */
4117 continue;
4118
4119 case succeed_n:
4120 /* If N == 0, it should be an on_failure_jump_loop instead. */
4121 DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); assert (j > 0));
4122 p += 4;
4123 /* We only care about one iteration of the loop, so we don't
4124 need to consider the case where this behaves like an
4125 on_failure_jump. */
4126 continue;
4127
4128
4129 case set_number_at:
4130 p += 4;
4131 continue;
4132
4133
4134 case start_memory:
4135 case stop_memory:
4136 p += 1;
4137 continue;
4138
4139
4140 default:
4141 abort (); /* We have listed all the cases. */
4142 } /* switch *p++ */
4143
4144 /* Getting here means we have found the possible starting
4145 characters for one path of the pattern -- and that the empty
4146 string does not match. We need not follow this path further. */
4147 return 0;
4148 } /* while p */
4149
4150 /* We reached the end without matching anything. */
4151 return 1;
4152
4153 } /* analyze_first */
4154 \f
4155 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4156 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4157 characters can start a string that matches the pattern. This fastmap
4158 is used by re_search to skip quickly over impossible starting points.
4159
4160 Character codes above (1 << BYTEWIDTH) are not represented in the
4161 fastmap, but the leading codes are represented. Thus, the fastmap
4162 indicates which character sets could start a match.
4163
4164 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4165 area as BUFP->fastmap.
4166
4167 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4168 the pattern buffer.
4169
4170 Returns 0 if we succeed, -2 if an internal error. */
4171
4172 int
4173 re_compile_fastmap (struct re_pattern_buffer *bufp)
4174 {
4175 char *fastmap = bufp->fastmap;
4176 int analysis;
4177
4178 assert (fastmap && bufp->buffer);
4179
4180 memset (fastmap, 0, 1 << BYTEWIDTH); /* Assume nothing's valid. */
4181 bufp->fastmap_accurate = 1; /* It will be when we're done. */
4182
4183 analysis = analyze_first (bufp->buffer, bufp->buffer + bufp->used,
4184 fastmap, RE_MULTIBYTE_P (bufp));
4185 bufp->can_be_null = (analysis != 0);
4186 return 0;
4187 } /* re_compile_fastmap */
4188 \f
4189 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
4190 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
4191 this memory for recording register information. STARTS and ENDS
4192 must be allocated using the malloc library routine, and must each
4193 be at least NUM_REGS * sizeof (regoff_t) bytes long.
4194
4195 If NUM_REGS == 0, then subsequent matches should allocate their own
4196 register data.
4197
4198 Unless this function is called, the first search or match using
4199 PATTERN_BUFFER will allocate its own register data, without
4200 freeing the old data. */
4201
4202 void
4203 re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs, unsigned int num_regs, regoff_t *starts, regoff_t *ends)
4204 {
4205 if (num_regs)
4206 {
4207 bufp->regs_allocated = REGS_REALLOCATE;
4208 regs->num_regs = num_regs;
4209 regs->start = starts;
4210 regs->end = ends;
4211 }
4212 else
4213 {
4214 bufp->regs_allocated = REGS_UNALLOCATED;
4215 regs->num_regs = 0;
4216 regs->start = regs->end = 0;
4217 }
4218 }
4219 WEAK_ALIAS (__re_set_registers, re_set_registers)
4220 \f
4221 /* Searching routines. */
4222
4223 /* Like re_search_2, below, but only one string is specified, and
4224 doesn't let you say where to stop matching. */
4225
4226 regoff_t
4227 re_search (struct re_pattern_buffer *bufp, const char *string, size_t size,
4228 ssize_t startpos, ssize_t range, struct re_registers *regs)
4229 {
4230 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
4231 regs, size);
4232 }
4233 WEAK_ALIAS (__re_search, re_search)
4234
4235 /* Head address of virtual concatenation of string. */
4236 #define HEAD_ADDR_VSTRING(P) \
4237 (((P) >= size1 ? string2 : string1))
4238
4239 /* Address of POS in the concatenation of virtual string. */
4240 #define POS_ADDR_VSTRING(POS) \
4241 (((POS) >= size1 ? string2 - size1 : string1) + (POS))
4242
4243 /* Using the compiled pattern in BUFP->buffer, first tries to match the
4244 virtual concatenation of STRING1 and STRING2, starting first at index
4245 STARTPOS, then at STARTPOS + 1, and so on.
4246
4247 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
4248
4249 RANGE is how far to scan while trying to match. RANGE = 0 means try
4250 only at STARTPOS; in general, the last start tried is STARTPOS +
4251 RANGE.
4252
4253 In REGS, return the indices of the virtual concatenation of STRING1
4254 and STRING2 that matched the entire BUFP->buffer and its contained
4255 subexpressions.
4256
4257 Do not consider matching one past the index STOP in the virtual
4258 concatenation of STRING1 and STRING2.
4259
4260 We return either the position in the strings at which the match was
4261 found, -1 if no match, or -2 if error (such as failure
4262 stack overflow). */
4263
4264 regoff_t
4265 re_search_2 (struct re_pattern_buffer *bufp, const char *str1, size_t size1,
4266 const char *str2, size_t size2, ssize_t startpos, ssize_t range,
4267 struct re_registers *regs, ssize_t stop)
4268 {
4269 regoff_t val;
4270 re_char *string1 = (re_char*) str1;
4271 re_char *string2 = (re_char*) str2;
4272 register char *fastmap = bufp->fastmap;
4273 register RE_TRANSLATE_TYPE translate = bufp->translate;
4274 size_t total_size = size1 + size2;
4275 ssize_t endpos = startpos + range;
4276 boolean anchored_start;
4277 /* Nonzero if we are searching multibyte string. */
4278 const boolean multibyte = RE_TARGET_MULTIBYTE_P (bufp);
4279
4280 /* Check for out-of-range STARTPOS. */
4281 if (startpos < 0 || startpos > total_size)
4282 return -1;
4283
4284 /* Fix up RANGE if it might eventually take us outside
4285 the virtual concatenation of STRING1 and STRING2.
4286 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
4287 if (endpos < 0)
4288 range = 0 - startpos;
4289 else if (endpos > total_size)
4290 range = total_size - startpos;
4291
4292 /* If the search isn't to be a backwards one, don't waste time in a
4293 search for a pattern anchored at beginning of buffer. */
4294 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
4295 {
4296 if (startpos > 0)
4297 return -1;
4298 else
4299 range = 0;
4300 }
4301
4302 #ifdef emacs
4303 /* In a forward search for something that starts with \=.
4304 don't keep searching past point. */
4305 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
4306 {
4307 range = PT_BYTE - BEGV_BYTE - startpos;
4308 if (range < 0)
4309 return -1;
4310 }
4311 #endif /* emacs */
4312
4313 /* Update the fastmap now if not correct already. */
4314 if (fastmap && !bufp->fastmap_accurate)
4315 re_compile_fastmap (bufp);
4316
4317 /* See whether the pattern is anchored. */
4318 anchored_start = (bufp->buffer[0] == begline);
4319
4320 #ifdef emacs
4321 gl_state.object = re_match_object; /* Used by SYNTAX_TABLE_BYTE_TO_CHAR. */
4322 {
4323 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (startpos));
4324
4325 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
4326 }
4327 #endif
4328
4329 /* Loop through the string, looking for a place to start matching. */
4330 for (;;)
4331 {
4332 /* If the pattern is anchored,
4333 skip quickly past places we cannot match.
4334 We don't bother to treat startpos == 0 specially
4335 because that case doesn't repeat. */
4336 if (anchored_start && startpos > 0)
4337 {
4338 if (! ((startpos <= size1 ? string1[startpos - 1]
4339 : string2[startpos - size1 - 1])
4340 == '\n'))
4341 goto advance;
4342 }
4343
4344 /* If a fastmap is supplied, skip quickly over characters that
4345 cannot be the start of a match. If the pattern can match the
4346 null string, however, we don't need to skip characters; we want
4347 the first null string. */
4348 if (fastmap && startpos < total_size && !bufp->can_be_null)
4349 {
4350 register re_char *d;
4351 register re_wchar_t buf_ch;
4352
4353 d = POS_ADDR_VSTRING (startpos);
4354
4355 if (range > 0) /* Searching forwards. */
4356 {
4357 ssize_t irange = range, lim = 0;
4358
4359 if (startpos < size1 && startpos + range >= size1)
4360 lim = range - (size1 - startpos);
4361
4362 /* Written out as an if-else to avoid testing `translate'
4363 inside the loop. */
4364 if (RE_TRANSLATE_P (translate))
4365 {
4366 if (multibyte)
4367 while (range > lim)
4368 {
4369 int buf_charlen;
4370
4371 buf_ch = STRING_CHAR_AND_LENGTH (d, buf_charlen);
4372 buf_ch = RE_TRANSLATE (translate, buf_ch);
4373 if (fastmap[CHAR_LEADING_CODE (buf_ch)])
4374 break;
4375
4376 range -= buf_charlen;
4377 d += buf_charlen;
4378 }
4379 else
4380 while (range > lim)
4381 {
4382 register re_wchar_t ch, translated;
4383
4384 buf_ch = *d;
4385 ch = RE_CHAR_TO_MULTIBYTE (buf_ch);
4386 translated = RE_TRANSLATE (translate, ch);
4387 if (translated != ch
4388 && (ch = RE_CHAR_TO_UNIBYTE (translated)) >= 0)
4389 buf_ch = ch;
4390 if (fastmap[buf_ch])
4391 break;
4392 d++;
4393 range--;
4394 }
4395 }
4396 else
4397 {
4398 if (multibyte)
4399 while (range > lim)
4400 {
4401 int buf_charlen;
4402
4403 buf_ch = STRING_CHAR_AND_LENGTH (d, buf_charlen);
4404 if (fastmap[CHAR_LEADING_CODE (buf_ch)])
4405 break;
4406 range -= buf_charlen;
4407 d += buf_charlen;
4408 }
4409 else
4410 while (range > lim && !fastmap[*d])
4411 {
4412 d++;
4413 range--;
4414 }
4415 }
4416 startpos += irange - range;
4417 }
4418 else /* Searching backwards. */
4419 {
4420 if (multibyte)
4421 {
4422 buf_ch = STRING_CHAR (d);
4423 buf_ch = TRANSLATE (buf_ch);
4424 if (! fastmap[CHAR_LEADING_CODE (buf_ch)])
4425 goto advance;
4426 }
4427 else
4428 {
4429 register re_wchar_t ch, translated;
4430
4431 buf_ch = *d;
4432 ch = RE_CHAR_TO_MULTIBYTE (buf_ch);
4433 translated = TRANSLATE (ch);
4434 if (translated != ch
4435 && (ch = RE_CHAR_TO_UNIBYTE (translated)) >= 0)
4436 buf_ch = ch;
4437 if (! fastmap[TRANSLATE (buf_ch)])
4438 goto advance;
4439 }
4440 }
4441 }
4442
4443 /* If can't match the null string, and that's all we have left, fail. */
4444 if (range >= 0 && startpos == total_size && fastmap
4445 && !bufp->can_be_null)
4446 return -1;
4447
4448 val = re_match_2_internal (bufp, string1, size1, string2, size2,
4449 startpos, regs, stop);
4450
4451 if (val >= 0)
4452 return startpos;
4453
4454 if (val == -2)
4455 return -2;
4456
4457 advance:
4458 if (!range)
4459 break;
4460 else if (range > 0)
4461 {
4462 /* Update STARTPOS to the next character boundary. */
4463 if (multibyte)
4464 {
4465 re_char *p = POS_ADDR_VSTRING (startpos);
4466 int len = BYTES_BY_CHAR_HEAD (*p);
4467
4468 range -= len;
4469 if (range < 0)
4470 break;
4471 startpos += len;
4472 }
4473 else
4474 {
4475 range--;
4476 startpos++;
4477 }
4478 }
4479 else
4480 {
4481 range++;
4482 startpos--;
4483
4484 /* Update STARTPOS to the previous character boundary. */
4485 if (multibyte)
4486 {
4487 re_char *p = POS_ADDR_VSTRING (startpos) + 1;
4488 re_char *p0 = p;
4489 re_char *phead = HEAD_ADDR_VSTRING (startpos);
4490
4491 /* Find the head of multibyte form. */
4492 PREV_CHAR_BOUNDARY (p, phead);
4493 range += p0 - 1 - p;
4494 if (range > 0)
4495 break;
4496
4497 startpos -= p0 - 1 - p;
4498 }
4499 }
4500 }
4501 return -1;
4502 } /* re_search_2 */
4503 WEAK_ALIAS (__re_search_2, re_search_2)
4504 \f
4505 /* Declarations and macros for re_match_2. */
4506
4507 static int bcmp_translate (re_char *s1, re_char *s2,
4508 register ssize_t len,
4509 RE_TRANSLATE_TYPE translate,
4510 const int multibyte);
4511
4512 /* This converts PTR, a pointer into one of the search strings `string1'
4513 and `string2' into an offset from the beginning of that string. */
4514 #define POINTER_TO_OFFSET(ptr) \
4515 (FIRST_STRING_P (ptr) \
4516 ? (ptr) - string1 \
4517 : (ptr) - string2 + (ptrdiff_t) size1)
4518
4519 /* Call before fetching a character with *d. This switches over to
4520 string2 if necessary.
4521 Check re_match_2_internal for a discussion of why end_match_2 might
4522 not be within string2 (but be equal to end_match_1 instead). */
4523 #define PREFETCH() \
4524 while (d == dend) \
4525 { \
4526 /* End of string2 => fail. */ \
4527 if (dend == end_match_2) \
4528 goto fail; \
4529 /* End of string1 => advance to string2. */ \
4530 d = string2; \
4531 dend = end_match_2; \
4532 }
4533
4534 /* Call before fetching a char with *d if you already checked other limits.
4535 This is meant for use in lookahead operations like wordend, etc..
4536 where we might need to look at parts of the string that might be
4537 outside of the LIMITs (i.e past `stop'). */
4538 #define PREFETCH_NOLIMIT() \
4539 if (d == end1) \
4540 { \
4541 d = string2; \
4542 dend = end_match_2; \
4543 } \
4544
4545 /* Test if at very beginning or at very end of the virtual concatenation
4546 of `string1' and `string2'. If only one string, it's `string2'. */
4547 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
4548 #define AT_STRINGS_END(d) ((d) == end2)
4549
4550 /* Disabled due to a compiler bug -- see comment at case wordbound */
4551
4552 /* The comment at case wordbound is following one, but we don't use
4553 AT_WORD_BOUNDARY anymore to support multibyte form.
4554
4555 The DEC Alpha C compiler 3.x generates incorrect code for the
4556 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
4557 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
4558 macro and introducing temporary variables works around the bug. */
4559
4560 #if 0
4561 /* Test if D points to a character which is word-constituent. We have
4562 two special cases to check for: if past the end of string1, look at
4563 the first character in string2; and if before the beginning of
4564 string2, look at the last character in string1. */
4565 #define WORDCHAR_P(d) \
4566 (SYNTAX ((d) == end1 ? *string2 \
4567 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
4568 == Sword)
4569
4570 /* Test if the character before D and the one at D differ with respect
4571 to being word-constituent. */
4572 #define AT_WORD_BOUNDARY(d) \
4573 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
4574 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
4575 #endif
4576
4577 /* Free everything we malloc. */
4578 #ifdef MATCH_MAY_ALLOCATE
4579 # define FREE_VAR(var) \
4580 do { \
4581 if (var) \
4582 { \
4583 REGEX_FREE (var); \
4584 var = NULL; \
4585 } \
4586 } while (0)
4587 # define FREE_VARIABLES() \
4588 do { \
4589 REGEX_FREE_STACK (fail_stack.stack); \
4590 FREE_VAR (regstart); \
4591 FREE_VAR (regend); \
4592 FREE_VAR (best_regstart); \
4593 FREE_VAR (best_regend); \
4594 REGEX_SAFE_FREE (); \
4595 } while (0)
4596 #else
4597 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
4598 #endif /* not MATCH_MAY_ALLOCATE */
4599
4600 \f
4601 /* Optimization routines. */
4602
4603 /* If the operation is a match against one or more chars,
4604 return a pointer to the next operation, else return NULL. */
4605 static re_char *
4606 skip_one_char (const_re_char *p)
4607 {
4608 switch (*p++)
4609 {
4610 case anychar:
4611 break;
4612
4613 case exactn:
4614 p += *p + 1;
4615 break;
4616
4617 case charset_not:
4618 case charset:
4619 if (CHARSET_RANGE_TABLE_EXISTS_P (p - 1))
4620 {
4621 int mcnt;
4622 p = CHARSET_RANGE_TABLE (p - 1);
4623 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4624 p = CHARSET_RANGE_TABLE_END (p, mcnt);
4625 }
4626 else
4627 p += 1 + CHARSET_BITMAP_SIZE (p - 1);
4628 break;
4629
4630 case syntaxspec:
4631 case notsyntaxspec:
4632 #ifdef emacs
4633 case categoryspec:
4634 case notcategoryspec:
4635 #endif /* emacs */
4636 p++;
4637 break;
4638
4639 default:
4640 p = NULL;
4641 }
4642 return p;
4643 }
4644
4645
4646 /* Jump over non-matching operations. */
4647 static re_char *
4648 skip_noops (const_re_char *p, const_re_char *pend)
4649 {
4650 int mcnt;
4651 while (p < pend)
4652 {
4653 switch (*p)
4654 {
4655 case start_memory:
4656 case stop_memory:
4657 p += 2; break;
4658 case no_op:
4659 p += 1; break;
4660 case jump:
4661 p += 1;
4662 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4663 p += mcnt;
4664 break;
4665 default:
4666 return p;
4667 }
4668 }
4669 assert (p == pend);
4670 return p;
4671 }
4672
4673 /* Non-zero if "p1 matches something" implies "p2 fails". */
4674 static int
4675 mutually_exclusive_p (struct re_pattern_buffer *bufp, const_re_char *p1,
4676 const_re_char *p2)
4677 {
4678 re_opcode_t op2;
4679 const boolean multibyte = RE_MULTIBYTE_P (bufp);
4680 unsigned char *pend = bufp->buffer + bufp->used;
4681
4682 assert (p1 >= bufp->buffer && p1 < pend
4683 && p2 >= bufp->buffer && p2 <= pend);
4684
4685 /* Skip over open/close-group commands.
4686 If what follows this loop is a ...+ construct,
4687 look at what begins its body, since we will have to
4688 match at least one of that. */
4689 p2 = skip_noops (p2, pend);
4690 /* The same skip can be done for p1, except that this function
4691 is only used in the case where p1 is a simple match operator. */
4692 /* p1 = skip_noops (p1, pend); */
4693
4694 assert (p1 >= bufp->buffer && p1 < pend
4695 && p2 >= bufp->buffer && p2 <= pend);
4696
4697 op2 = p2 == pend ? succeed : *p2;
4698
4699 switch (op2)
4700 {
4701 case succeed:
4702 case endbuf:
4703 /* If we're at the end of the pattern, we can change. */
4704 if (skip_one_char (p1))
4705 {
4706 DEBUG_PRINT (" End of pattern: fast loop.\n");
4707 return 1;
4708 }
4709 break;
4710
4711 case endline:
4712 case exactn:
4713 {
4714 register re_wchar_t c
4715 = (re_opcode_t) *p2 == endline ? '\n'
4716 : RE_STRING_CHAR (p2 + 2, multibyte);
4717
4718 if ((re_opcode_t) *p1 == exactn)
4719 {
4720 if (c != RE_STRING_CHAR (p1 + 2, multibyte))
4721 {
4722 DEBUG_PRINT (" '%c' != '%c' => fast loop.\n", c, p1[2]);
4723 return 1;
4724 }
4725 }
4726
4727 else if ((re_opcode_t) *p1 == charset
4728 || (re_opcode_t) *p1 == charset_not)
4729 {
4730 int not = (re_opcode_t) *p1 == charset_not;
4731
4732 /* Test if C is listed in charset (or charset_not)
4733 at `p1'. */
4734 if (! multibyte || IS_REAL_ASCII (c))
4735 {
4736 if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
4737 && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
4738 not = !not;
4739 }
4740 else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
4741 CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
4742
4743 /* `not' is equal to 1 if c would match, which means
4744 that we can't change to pop_failure_jump. */
4745 if (!not)
4746 {
4747 DEBUG_PRINT (" No match => fast loop.\n");
4748 return 1;
4749 }
4750 }
4751 else if ((re_opcode_t) *p1 == anychar
4752 && c == '\n')
4753 {
4754 DEBUG_PRINT (" . != \\n => fast loop.\n");
4755 return 1;
4756 }
4757 }
4758 break;
4759
4760 case charset:
4761 {
4762 if ((re_opcode_t) *p1 == exactn)
4763 /* Reuse the code above. */
4764 return mutually_exclusive_p (bufp, p2, p1);
4765
4766 /* It is hard to list up all the character in charset
4767 P2 if it includes multibyte character. Give up in
4768 such case. */
4769 else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2))
4770 {
4771 /* Now, we are sure that P2 has no range table.
4772 So, for the size of bitmap in P2, `p2[1]' is
4773 enough. But P1 may have range table, so the
4774 size of bitmap table of P1 is extracted by
4775 using macro `CHARSET_BITMAP_SIZE'.
4776
4777 In a multibyte case, we know that all the character
4778 listed in P2 is ASCII. In a unibyte case, P1 has only a
4779 bitmap table. So, in both cases, it is enough to test
4780 only the bitmap table of P1. */
4781
4782 if ((re_opcode_t) *p1 == charset)
4783 {
4784 int idx;
4785 /* We win if the charset inside the loop
4786 has no overlap with the one after the loop. */
4787 for (idx = 0;
4788 (idx < (int) p2[1]
4789 && idx < CHARSET_BITMAP_SIZE (p1));
4790 idx++)
4791 if ((p2[2 + idx] & p1[2 + idx]) != 0)
4792 break;
4793
4794 if (idx == p2[1]
4795 || idx == CHARSET_BITMAP_SIZE (p1))
4796 {
4797 DEBUG_PRINT (" No match => fast loop.\n");
4798 return 1;
4799 }
4800 }
4801 else if ((re_opcode_t) *p1 == charset_not)
4802 {
4803 int idx;
4804 /* We win if the charset_not inside the loop lists
4805 every character listed in the charset after. */
4806 for (idx = 0; idx < (int) p2[1]; idx++)
4807 if (! (p2[2 + idx] == 0
4808 || (idx < CHARSET_BITMAP_SIZE (p1)
4809 && ((p2[2 + idx] & ~ p1[2 + idx]) == 0))))
4810 break;
4811
4812 if (idx == p2[1])
4813 {
4814 DEBUG_PRINT (" No match => fast loop.\n");
4815 return 1;
4816 }
4817 }
4818 }
4819 }
4820 break;
4821
4822 case charset_not:
4823 switch (*p1)
4824 {
4825 case exactn:
4826 case charset:
4827 /* Reuse the code above. */
4828 return mutually_exclusive_p (bufp, p2, p1);
4829 case charset_not:
4830 /* When we have two charset_not, it's very unlikely that
4831 they don't overlap. The union of the two sets of excluded
4832 chars should cover all possible chars, which, as a matter of
4833 fact, is virtually impossible in multibyte buffers. */
4834 break;
4835 }
4836 break;
4837
4838 case wordend:
4839 return ((re_opcode_t) *p1 == syntaxspec && p1[1] == Sword);
4840 case symend:
4841 return ((re_opcode_t) *p1 == syntaxspec
4842 && (p1[1] == Ssymbol || p1[1] == Sword));
4843 case notsyntaxspec:
4844 return ((re_opcode_t) *p1 == syntaxspec && p1[1] == p2[1]);
4845
4846 case wordbeg:
4847 return ((re_opcode_t) *p1 == notsyntaxspec && p1[1] == Sword);
4848 case symbeg:
4849 return ((re_opcode_t) *p1 == notsyntaxspec
4850 && (p1[1] == Ssymbol || p1[1] == Sword));
4851 case syntaxspec:
4852 return ((re_opcode_t) *p1 == notsyntaxspec && p1[1] == p2[1]);
4853
4854 case wordbound:
4855 return (((re_opcode_t) *p1 == notsyntaxspec
4856 || (re_opcode_t) *p1 == syntaxspec)
4857 && p1[1] == Sword);
4858
4859 #ifdef emacs
4860 case categoryspec:
4861 return ((re_opcode_t) *p1 == notcategoryspec && p1[1] == p2[1]);
4862 case notcategoryspec:
4863 return ((re_opcode_t) *p1 == categoryspec && p1[1] == p2[1]);
4864 #endif /* emacs */
4865
4866 default:
4867 ;
4868 }
4869
4870 /* Safe default. */
4871 return 0;
4872 }
4873
4874 \f
4875 /* Matching routines. */
4876
4877 #ifndef emacs /* Emacs never uses this. */
4878 /* re_match is like re_match_2 except it takes only a single string. */
4879
4880 regoff_t
4881 re_match (struct re_pattern_buffer *bufp, const char *string,
4882 size_t size, ssize_t pos, struct re_registers *regs)
4883 {
4884 regoff_t result = re_match_2_internal (bufp, NULL, 0, (re_char*) string,
4885 size, pos, regs, size);
4886 return result;
4887 }
4888 WEAK_ALIAS (__re_match, re_match)
4889 #endif /* not emacs */
4890
4891 #ifdef emacs
4892 /* In Emacs, this is the string or buffer in which we are matching.
4893 See the declaration in regex.h for details. */
4894 Lisp_Object re_match_object;
4895 #endif
4896
4897 /* re_match_2 matches the compiled pattern in BUFP against the
4898 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
4899 and SIZE2, respectively). We start matching at POS, and stop
4900 matching at STOP.
4901
4902 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
4903 store offsets for the substring each group matched in REGS. See the
4904 documentation for exactly how many groups we fill.
4905
4906 We return -1 if no match, -2 if an internal error (such as the
4907 failure stack overflowing). Otherwise, we return the length of the
4908 matched substring. */
4909
4910 regoff_t
4911 re_match_2 (struct re_pattern_buffer *bufp, const char *string1,
4912 size_t size1, const char *string2, size_t size2, ssize_t pos,
4913 struct re_registers *regs, ssize_t stop)
4914 {
4915 regoff_t result;
4916
4917 #ifdef emacs
4918 ssize_t charpos;
4919 gl_state.object = re_match_object; /* Used by SYNTAX_TABLE_BYTE_TO_CHAR. */
4920 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (pos));
4921 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
4922 #endif
4923
4924 result = re_match_2_internal (bufp, (re_char*) string1, size1,
4925 (re_char*) string2, size2,
4926 pos, regs, stop);
4927 return result;
4928 }
4929 WEAK_ALIAS (__re_match_2, re_match_2)
4930
4931
4932 /* This is a separate function so that we can force an alloca cleanup
4933 afterwards. */
4934 static regoff_t
4935 re_match_2_internal (struct re_pattern_buffer *bufp, const_re_char *string1,
4936 size_t size1, const_re_char *string2, size_t size2,
4937 ssize_t pos, struct re_registers *regs, ssize_t stop)
4938 {
4939 /* General temporaries. */
4940 int mcnt;
4941 size_t reg;
4942
4943 /* Just past the end of the corresponding string. */
4944 re_char *end1, *end2;
4945
4946 /* Pointers into string1 and string2, just past the last characters in
4947 each to consider matching. */
4948 re_char *end_match_1, *end_match_2;
4949
4950 /* Where we are in the data, and the end of the current string. */
4951 re_char *d, *dend;
4952
4953 /* Used sometimes to remember where we were before starting matching
4954 an operator so that we can go back in case of failure. This "atomic"
4955 behavior of matching opcodes is indispensable to the correctness
4956 of the on_failure_keep_string_jump optimization. */
4957 re_char *dfail;
4958
4959 /* Where we are in the pattern, and the end of the pattern. */
4960 re_char *p = bufp->buffer;
4961 re_char *pend = p + bufp->used;
4962
4963 /* We use this to map every character in the string. */
4964 RE_TRANSLATE_TYPE translate = bufp->translate;
4965
4966 /* Nonzero if BUFP is setup from a multibyte regex. */
4967 const boolean multibyte = RE_MULTIBYTE_P (bufp);
4968
4969 /* Nonzero if STRING1/STRING2 are multibyte. */
4970 const boolean target_multibyte = RE_TARGET_MULTIBYTE_P (bufp);
4971
4972 /* Failure point stack. Each place that can handle a failure further
4973 down the line pushes a failure point on this stack. It consists of
4974 regstart, and regend for all registers corresponding to
4975 the subexpressions we're currently inside, plus the number of such
4976 registers, and, finally, two char *'s. The first char * is where
4977 to resume scanning the pattern; the second one is where to resume
4978 scanning the strings. */
4979 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
4980 fail_stack_type fail_stack;
4981 #endif
4982 #ifdef DEBUG_COMPILES_ARGUMENTS
4983 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
4984 #endif
4985
4986 #if defined REL_ALLOC && defined REGEX_MALLOC
4987 /* This holds the pointer to the failure stack, when
4988 it is allocated relocatably. */
4989 fail_stack_elt_t *failure_stack_ptr;
4990 #endif
4991
4992 /* We fill all the registers internally, independent of what we
4993 return, for use in backreferences. The number here includes
4994 an element for register zero. */
4995 size_t num_regs = bufp->re_nsub + 1;
4996
4997 /* Information on the contents of registers. These are pointers into
4998 the input strings; they record just what was matched (on this
4999 attempt) by a subexpression part of the pattern, that is, the
5000 regnum-th regstart pointer points to where in the pattern we began
5001 matching and the regnum-th regend points to right after where we
5002 stopped matching the regnum-th subexpression. (The zeroth register
5003 keeps track of what the whole pattern matches.) */
5004 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5005 re_char **regstart, **regend;
5006 #endif
5007
5008 /* The following record the register info as found in the above
5009 variables when we find a match better than any we've seen before.
5010 This happens as we backtrack through the failure points, which in
5011 turn happens only if we have not yet matched the entire string. */
5012 unsigned best_regs_set = false;
5013 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5014 re_char **best_regstart, **best_regend;
5015 #endif
5016
5017 /* Logically, this is `best_regend[0]'. But we don't want to have to
5018 allocate space for that if we're not allocating space for anything
5019 else (see below). Also, we never need info about register 0 for
5020 any of the other register vectors, and it seems rather a kludge to
5021 treat `best_regend' differently than the rest. So we keep track of
5022 the end of the best match so far in a separate variable. We
5023 initialize this to NULL so that when we backtrack the first time
5024 and need to test it, it's not garbage. */
5025 re_char *match_end = NULL;
5026
5027 #ifdef DEBUG_COMPILES_ARGUMENTS
5028 /* Counts the total number of registers pushed. */
5029 unsigned num_regs_pushed = 0;
5030 #endif
5031
5032 DEBUG_PRINT ("\n\nEntering re_match_2.\n");
5033
5034 REGEX_USE_SAFE_ALLOCA;
5035
5036 INIT_FAIL_STACK ();
5037
5038 #ifdef MATCH_MAY_ALLOCATE
5039 /* Do not bother to initialize all the register variables if there are
5040 no groups in the pattern, as it takes a fair amount of time. If
5041 there are groups, we include space for register 0 (the whole
5042 pattern), even though we never use it, since it simplifies the
5043 array indexing. We should fix this. */
5044 if (bufp->re_nsub)
5045 {
5046 regstart = REGEX_TALLOC (num_regs, re_char *);
5047 regend = REGEX_TALLOC (num_regs, re_char *);
5048 best_regstart = REGEX_TALLOC (num_regs, re_char *);
5049 best_regend = REGEX_TALLOC (num_regs, re_char *);
5050
5051 if (!(regstart && regend && best_regstart && best_regend))
5052 {
5053 FREE_VARIABLES ();
5054 return -2;
5055 }
5056 }
5057 else
5058 {
5059 /* We must initialize all our variables to NULL, so that
5060 `FREE_VARIABLES' doesn't try to free them. */
5061 regstart = regend = best_regstart = best_regend = NULL;
5062 }
5063 #endif /* MATCH_MAY_ALLOCATE */
5064
5065 /* The starting position is bogus. */
5066 if (pos < 0 || pos > size1 + size2)
5067 {
5068 FREE_VARIABLES ();
5069 return -1;
5070 }
5071
5072 /* Initialize subexpression text positions to -1 to mark ones that no
5073 start_memory/stop_memory has been seen for. Also initialize the
5074 register information struct. */
5075 for (reg = 1; reg < num_regs; reg++)
5076 regstart[reg] = regend[reg] = NULL;
5077
5078 /* We move `string1' into `string2' if the latter's empty -- but not if
5079 `string1' is null. */
5080 if (size2 == 0 && string1 != NULL)
5081 {
5082 string2 = string1;
5083 size2 = size1;
5084 string1 = 0;
5085 size1 = 0;
5086 }
5087 end1 = string1 + size1;
5088 end2 = string2 + size2;
5089
5090 /* `p' scans through the pattern as `d' scans through the data.
5091 `dend' is the end of the input string that `d' points within. `d'
5092 is advanced into the following input string whenever necessary, but
5093 this happens before fetching; therefore, at the beginning of the
5094 loop, `d' can be pointing at the end of a string, but it cannot
5095 equal `string2'. */
5096 if (pos >= size1)
5097 {
5098 /* Only match within string2. */
5099 d = string2 + pos - size1;
5100 dend = end_match_2 = string2 + stop - size1;
5101 end_match_1 = end1; /* Just to give it a value. */
5102 }
5103 else
5104 {
5105 if (stop < size1)
5106 {
5107 /* Only match within string1. */
5108 end_match_1 = string1 + stop;
5109 /* BEWARE!
5110 When we reach end_match_1, PREFETCH normally switches to string2.
5111 But in the present case, this means that just doing a PREFETCH
5112 makes us jump from `stop' to `gap' within the string.
5113 What we really want here is for the search to stop as
5114 soon as we hit end_match_1. That's why we set end_match_2
5115 to end_match_1 (since PREFETCH fails as soon as we hit
5116 end_match_2). */
5117 end_match_2 = end_match_1;
5118 }
5119 else
5120 { /* It's important to use this code when stop == size so that
5121 moving `d' from end1 to string2 will not prevent the d == dend
5122 check from catching the end of string. */
5123 end_match_1 = end1;
5124 end_match_2 = string2 + stop - size1;
5125 }
5126 d = string1 + pos;
5127 dend = end_match_1;
5128 }
5129
5130 DEBUG_PRINT ("The compiled pattern is: ");
5131 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
5132 DEBUG_PRINT ("The string to match is: \"");
5133 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
5134 DEBUG_PRINT ("\"\n");
5135
5136 /* This loops over pattern commands. It exits by returning from the
5137 function if the match is complete, or it drops through if the match
5138 fails at this starting point in the input data. */
5139 for (;;)
5140 {
5141 DEBUG_PRINT ("\n%p: ", p);
5142
5143 if (p == pend)
5144 {
5145 ptrdiff_t dcnt;
5146
5147 /* End of pattern means we might have succeeded. */
5148 DEBUG_PRINT ("end of pattern ... ");
5149
5150 /* If we haven't matched the entire string, and we want the
5151 longest match, try backtracking. */
5152 if (d != end_match_2)
5153 {
5154 /* 1 if this match ends in the same string (string1 or string2)
5155 as the best previous match. */
5156 boolean same_str_p = (FIRST_STRING_P (match_end)
5157 == FIRST_STRING_P (d));
5158 /* 1 if this match is the best seen so far. */
5159 boolean best_match_p;
5160
5161 /* AIX compiler got confused when this was combined
5162 with the previous declaration. */
5163 if (same_str_p)
5164 best_match_p = d > match_end;
5165 else
5166 best_match_p = !FIRST_STRING_P (d);
5167
5168 DEBUG_PRINT ("backtracking.\n");
5169
5170 if (!FAIL_STACK_EMPTY ())
5171 { /* More failure points to try. */
5172
5173 /* If exceeds best match so far, save it. */
5174 if (!best_regs_set || best_match_p)
5175 {
5176 best_regs_set = true;
5177 match_end = d;
5178
5179 DEBUG_PRINT ("\nSAVING match as best so far.\n");
5180
5181 for (reg = 1; reg < num_regs; reg++)
5182 {
5183 best_regstart[reg] = regstart[reg];
5184 best_regend[reg] = regend[reg];
5185 }
5186 }
5187 goto fail;
5188 }
5189
5190 /* If no failure points, don't restore garbage. And if
5191 last match is real best match, don't restore second
5192 best one. */
5193 else if (best_regs_set && !best_match_p)
5194 {
5195 restore_best_regs:
5196 /* Restore best match. It may happen that `dend ==
5197 end_match_1' while the restored d is in string2.
5198 For example, the pattern `x.*y.*z' against the
5199 strings `x-' and `y-z-', if the two strings are
5200 not consecutive in memory. */
5201 DEBUG_PRINT ("Restoring best registers.\n");
5202
5203 d = match_end;
5204 dend = ((d >= string1 && d <= end1)
5205 ? end_match_1 : end_match_2);
5206
5207 for (reg = 1; reg < num_regs; reg++)
5208 {
5209 regstart[reg] = best_regstart[reg];
5210 regend[reg] = best_regend[reg];
5211 }
5212 }
5213 } /* d != end_match_2 */
5214
5215 succeed_label:
5216 DEBUG_PRINT ("Accepting match.\n");
5217
5218 /* If caller wants register contents data back, do it. */
5219 if (regs && !bufp->no_sub)
5220 {
5221 /* Have the register data arrays been allocated? */
5222 if (bufp->regs_allocated == REGS_UNALLOCATED)
5223 { /* No. So allocate them with malloc. We need one
5224 extra element beyond `num_regs' for the `-1' marker
5225 GNU code uses. */
5226 regs->num_regs = max (RE_NREGS, num_regs + 1);
5227 regs->start = TALLOC (regs->num_regs, regoff_t);
5228 regs->end = TALLOC (regs->num_regs, regoff_t);
5229 if (regs->start == NULL || regs->end == NULL)
5230 {
5231 FREE_VARIABLES ();
5232 return -2;
5233 }
5234 bufp->regs_allocated = REGS_REALLOCATE;
5235 }
5236 else if (bufp->regs_allocated == REGS_REALLOCATE)
5237 { /* Yes. If we need more elements than were already
5238 allocated, reallocate them. If we need fewer, just
5239 leave it alone. */
5240 if (regs->num_regs < num_regs + 1)
5241 {
5242 regs->num_regs = num_regs + 1;
5243 RETALLOC (regs->start, regs->num_regs, regoff_t);
5244 RETALLOC (regs->end, regs->num_regs, regoff_t);
5245 if (regs->start == NULL || regs->end == NULL)
5246 {
5247 FREE_VARIABLES ();
5248 return -2;
5249 }
5250 }
5251 }
5252 else
5253 {
5254 /* These braces fend off a "empty body in an else-statement"
5255 warning under GCC when assert expands to nothing. */
5256 assert (bufp->regs_allocated == REGS_FIXED);
5257 }
5258
5259 /* Convert the pointer data in `regstart' and `regend' to
5260 indices. Register zero has to be set differently,
5261 since we haven't kept track of any info for it. */
5262 if (regs->num_regs > 0)
5263 {
5264 regs->start[0] = pos;
5265 regs->end[0] = POINTER_TO_OFFSET (d);
5266 }
5267
5268 /* Go through the first `min (num_regs, regs->num_regs)'
5269 registers, since that is all we initialized. */
5270 for (reg = 1; reg < min (num_regs, regs->num_regs); reg++)
5271 {
5272 if (REG_UNSET (regstart[reg]) || REG_UNSET (regend[reg]))
5273 regs->start[reg] = regs->end[reg] = -1;
5274 else
5275 {
5276 regs->start[reg] = POINTER_TO_OFFSET (regstart[reg]);
5277 regs->end[reg] = POINTER_TO_OFFSET (regend[reg]);
5278 }
5279 }
5280
5281 /* If the regs structure we return has more elements than
5282 were in the pattern, set the extra elements to -1. If
5283 we (re)allocated the registers, this is the case,
5284 because we always allocate enough to have at least one
5285 -1 at the end. */
5286 for (reg = num_regs; reg < regs->num_regs; reg++)
5287 regs->start[reg] = regs->end[reg] = -1;
5288 } /* regs && !bufp->no_sub */
5289
5290 DEBUG_PRINT ("%u failure points pushed, %u popped (%u remain).\n",
5291 nfailure_points_pushed, nfailure_points_popped,
5292 nfailure_points_pushed - nfailure_points_popped);
5293 DEBUG_PRINT ("%u registers pushed.\n", num_regs_pushed);
5294
5295 dcnt = POINTER_TO_OFFSET (d) - pos;
5296
5297 DEBUG_PRINT ("Returning %td from re_match_2.\n", dcnt);
5298
5299 FREE_VARIABLES ();
5300 return dcnt;
5301 }
5302
5303 /* Otherwise match next pattern command. */
5304 switch (*p++)
5305 {
5306 /* Ignore these. Used to ignore the n of succeed_n's which
5307 currently have n == 0. */
5308 case no_op:
5309 DEBUG_PRINT ("EXECUTING no_op.\n");
5310 break;
5311
5312 case succeed:
5313 DEBUG_PRINT ("EXECUTING succeed.\n");
5314 goto succeed_label;
5315
5316 /* Match the next n pattern characters exactly. The following
5317 byte in the pattern defines n, and the n bytes after that
5318 are the characters to match. */
5319 case exactn:
5320 mcnt = *p++;
5321 DEBUG_PRINT ("EXECUTING exactn %d.\n", mcnt);
5322
5323 /* Remember the start point to rollback upon failure. */
5324 dfail = d;
5325
5326 #ifndef emacs
5327 /* This is written out as an if-else so we don't waste time
5328 testing `translate' inside the loop. */
5329 if (RE_TRANSLATE_P (translate))
5330 do
5331 {
5332 PREFETCH ();
5333 if (RE_TRANSLATE (translate, *d) != *p++)
5334 {
5335 d = dfail;
5336 goto fail;
5337 }
5338 d++;
5339 }
5340 while (--mcnt);
5341 else
5342 do
5343 {
5344 PREFETCH ();
5345 if (*d++ != *p++)
5346 {
5347 d = dfail;
5348 goto fail;
5349 }
5350 }
5351 while (--mcnt);
5352 #else /* emacs */
5353 /* The cost of testing `translate' is comparatively small. */
5354 if (target_multibyte)
5355 do
5356 {
5357 int pat_charlen, buf_charlen;
5358 int pat_ch, buf_ch;
5359
5360 PREFETCH ();
5361 if (multibyte)
5362 pat_ch = STRING_CHAR_AND_LENGTH (p, pat_charlen);
5363 else
5364 {
5365 pat_ch = RE_CHAR_TO_MULTIBYTE (*p);
5366 pat_charlen = 1;
5367 }
5368 buf_ch = STRING_CHAR_AND_LENGTH (d, buf_charlen);
5369
5370 if (TRANSLATE (buf_ch) != pat_ch)
5371 {
5372 d = dfail;
5373 goto fail;
5374 }
5375
5376 p += pat_charlen;
5377 d += buf_charlen;
5378 mcnt -= pat_charlen;
5379 }
5380 while (mcnt > 0);
5381 else
5382 do
5383 {
5384 int pat_charlen;
5385 int pat_ch, buf_ch;
5386
5387 PREFETCH ();
5388 if (multibyte)
5389 {
5390 pat_ch = STRING_CHAR_AND_LENGTH (p, pat_charlen);
5391 pat_ch = RE_CHAR_TO_UNIBYTE (pat_ch);
5392 }
5393 else
5394 {
5395 pat_ch = *p;
5396 pat_charlen = 1;
5397 }
5398 buf_ch = RE_CHAR_TO_MULTIBYTE (*d);
5399 if (! CHAR_BYTE8_P (buf_ch))
5400 {
5401 buf_ch = TRANSLATE (buf_ch);
5402 buf_ch = RE_CHAR_TO_UNIBYTE (buf_ch);
5403 if (buf_ch < 0)
5404 buf_ch = *d;
5405 }
5406 else
5407 buf_ch = *d;
5408 if (buf_ch != pat_ch)
5409 {
5410 d = dfail;
5411 goto fail;
5412 }
5413 p += pat_charlen;
5414 d++;
5415 }
5416 while (--mcnt);
5417 #endif
5418 break;
5419
5420
5421 /* Match any character except possibly a newline or a null. */
5422 case anychar:
5423 {
5424 int buf_charlen;
5425 re_wchar_t buf_ch;
5426
5427 DEBUG_PRINT ("EXECUTING anychar.\n");
5428
5429 PREFETCH ();
5430 buf_ch = RE_STRING_CHAR_AND_LENGTH (d, buf_charlen,
5431 target_multibyte);
5432 buf_ch = TRANSLATE (buf_ch);
5433
5434 if ((!(bufp->syntax & RE_DOT_NEWLINE)
5435 && buf_ch == '\n')
5436 || ((bufp->syntax & RE_DOT_NOT_NULL)
5437 && buf_ch == '\000'))
5438 goto fail;
5439
5440 DEBUG_PRINT (" Matched \"%d\".\n", *d);
5441 d += buf_charlen;
5442 }
5443 break;
5444
5445
5446 case charset:
5447 case charset_not:
5448 {
5449 register unsigned int c, corig;
5450 boolean not = (re_opcode_t) *(p - 1) == charset_not;
5451 int len;
5452
5453 /* Start of actual range_table, or end of bitmap if there is no
5454 range table. */
5455 re_char *range_table IF_LINT (= NULL);
5456
5457 /* Nonzero if there is a range table. */
5458 int range_table_exists;
5459
5460 /* Number of ranges of range table. This is not included
5461 in the initial byte-length of the command. */
5462 int count = 0;
5463
5464 /* Whether matching against a unibyte character. */
5465 boolean unibyte_char = false;
5466
5467 DEBUG_PRINT ("EXECUTING charset%s.\n", not ? "_not" : "");
5468
5469 range_table_exists = CHARSET_RANGE_TABLE_EXISTS_P (&p[-1]);
5470
5471 if (range_table_exists)
5472 {
5473 range_table = CHARSET_RANGE_TABLE (&p[-1]); /* Past the bitmap. */
5474 EXTRACT_NUMBER_AND_INCR (count, range_table);
5475 }
5476
5477 PREFETCH ();
5478 corig = c = RE_STRING_CHAR_AND_LENGTH (d, len, target_multibyte);
5479 if (target_multibyte)
5480 {
5481 int c1;
5482
5483 c = TRANSLATE (c);
5484 c1 = RE_CHAR_TO_UNIBYTE (c);
5485 if (c1 >= 0)
5486 {
5487 unibyte_char = true;
5488 c = c1;
5489 }
5490 }
5491 else
5492 {
5493 int c1 = RE_CHAR_TO_MULTIBYTE (c);
5494
5495 if (! CHAR_BYTE8_P (c1))
5496 {
5497 c1 = TRANSLATE (c1);
5498 c1 = RE_CHAR_TO_UNIBYTE (c1);
5499 if (c1 >= 0)
5500 {
5501 unibyte_char = true;
5502 c = c1;
5503 }
5504 }
5505 else
5506 unibyte_char = true;
5507 }
5508
5509 if (unibyte_char && c < (1 << BYTEWIDTH))
5510 { /* Lookup bitmap. */
5511 /* Cast to `unsigned' instead of `unsigned char' in
5512 case the bit list is a full 32 bytes long. */
5513 if (c < (unsigned) (CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH)
5514 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
5515 not = !not;
5516 }
5517 #ifdef emacs
5518 else if (range_table_exists)
5519 {
5520 int class_bits = CHARSET_RANGE_TABLE_BITS (&p[-1]);
5521
5522 if ( (class_bits & BIT_LOWER
5523 && (ISLOWER (c)
5524 || (corig != c
5525 && c == upcase (corig) && ISUPPER(c))))
5526 | (class_bits & BIT_MULTIBYTE)
5527 | (class_bits & BIT_PUNCT && ISPUNCT (c))
5528 | (class_bits & BIT_SPACE && ISSPACE (c))
5529 | (class_bits & BIT_UPPER
5530 && (ISUPPER (c)
5531 || (corig != c
5532 && c == downcase (corig) && ISLOWER (c))))
5533 | (class_bits & BIT_WORD && ISWORD (c))
5534 | (class_bits & BIT_ALPHA && ISALPHA (c))
5535 | (class_bits & BIT_ALNUM && ISALNUM (c))
5536 | (class_bits & BIT_GRAPH && ISGRAPH (c))
5537 | (class_bits & BIT_PRINT && ISPRINT (c)))
5538 not = !not;
5539 else
5540 CHARSET_LOOKUP_RANGE_TABLE_RAW (not, c, range_table, count);
5541 }
5542 #endif /* emacs */
5543
5544 if (range_table_exists)
5545 p = CHARSET_RANGE_TABLE_END (range_table, count);
5546 else
5547 p += CHARSET_BITMAP_SIZE (&p[-1]) + 1;
5548
5549 if (!not) goto fail;
5550
5551 d += len;
5552 }
5553 break;
5554
5555
5556 /* The beginning of a group is represented by start_memory.
5557 The argument is the register number. The text
5558 matched within the group is recorded (in the internal
5559 registers data structure) under the register number. */
5560 case start_memory:
5561 DEBUG_PRINT ("EXECUTING start_memory %d:\n", *p);
5562
5563 /* In case we need to undo this operation (via backtracking). */
5564 PUSH_FAILURE_REG (*p);
5565
5566 regstart[*p] = d;
5567 regend[*p] = NULL; /* probably unnecessary. -sm */
5568 DEBUG_PRINT (" regstart: %td\n", POINTER_TO_OFFSET (regstart[*p]));
5569
5570 /* Move past the register number and inner group count. */
5571 p += 1;
5572 break;
5573
5574
5575 /* The stop_memory opcode represents the end of a group. Its
5576 argument is the same as start_memory's: the register number. */
5577 case stop_memory:
5578 DEBUG_PRINT ("EXECUTING stop_memory %d:\n", *p);
5579
5580 assert (!REG_UNSET (regstart[*p]));
5581 /* Strictly speaking, there should be code such as:
5582
5583 assert (REG_UNSET (regend[*p]));
5584 PUSH_FAILURE_REGSTOP ((unsigned int)*p);
5585
5586 But the only info to be pushed is regend[*p] and it is known to
5587 be UNSET, so there really isn't anything to push.
5588 Not pushing anything, on the other hand deprives us from the
5589 guarantee that regend[*p] is UNSET since undoing this operation
5590 will not reset its value properly. This is not important since
5591 the value will only be read on the next start_memory or at
5592 the very end and both events can only happen if this stop_memory
5593 is *not* undone. */
5594
5595 regend[*p] = d;
5596 DEBUG_PRINT (" regend: %td\n", POINTER_TO_OFFSET (regend[*p]));
5597
5598 /* Move past the register number and the inner group count. */
5599 p += 1;
5600 break;
5601
5602
5603 /* \<digit> has been turned into a `duplicate' command which is
5604 followed by the numeric value of <digit> as the register number. */
5605 case duplicate:
5606 {
5607 register re_char *d2, *dend2;
5608 int regno = *p++; /* Get which register to match against. */
5609 DEBUG_PRINT ("EXECUTING duplicate %d.\n", regno);
5610
5611 /* Can't back reference a group which we've never matched. */
5612 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
5613 goto fail;
5614
5615 /* Where in input to try to start matching. */
5616 d2 = regstart[regno];
5617
5618 /* Remember the start point to rollback upon failure. */
5619 dfail = d;
5620
5621 /* Where to stop matching; if both the place to start and
5622 the place to stop matching are in the same string, then
5623 set to the place to stop, otherwise, for now have to use
5624 the end of the first string. */
5625
5626 dend2 = ((FIRST_STRING_P (regstart[regno])
5627 == FIRST_STRING_P (regend[regno]))
5628 ? regend[regno] : end_match_1);
5629 for (;;)
5630 {
5631 ptrdiff_t dcnt;
5632
5633 /* If necessary, advance to next segment in register
5634 contents. */
5635 while (d2 == dend2)
5636 {
5637 if (dend2 == end_match_2) break;
5638 if (dend2 == regend[regno]) break;
5639
5640 /* End of string1 => advance to string2. */
5641 d2 = string2;
5642 dend2 = regend[regno];
5643 }
5644 /* At end of register contents => success */
5645 if (d2 == dend2) break;
5646
5647 /* If necessary, advance to next segment in data. */
5648 PREFETCH ();
5649
5650 /* How many characters left in this segment to match. */
5651 dcnt = dend - d;
5652
5653 /* Want how many consecutive characters we can match in
5654 one shot, so, if necessary, adjust the count. */
5655 if (dcnt > dend2 - d2)
5656 dcnt = dend2 - d2;
5657
5658 /* Compare that many; failure if mismatch, else move
5659 past them. */
5660 if (RE_TRANSLATE_P (translate)
5661 ? bcmp_translate (d, d2, dcnt, translate, target_multibyte)
5662 : memcmp (d, d2, dcnt))
5663 {
5664 d = dfail;
5665 goto fail;
5666 }
5667 d += dcnt, d2 += dcnt;
5668 }
5669 }
5670 break;
5671
5672
5673 /* begline matches the empty string at the beginning of the string
5674 (unless `not_bol' is set in `bufp'), and after newlines. */
5675 case begline:
5676 DEBUG_PRINT ("EXECUTING begline.\n");
5677
5678 if (AT_STRINGS_BEG (d))
5679 {
5680 if (!bufp->not_bol) break;
5681 }
5682 else
5683 {
5684 unsigned c;
5685 GET_CHAR_BEFORE_2 (c, d, string1, end1, string2, end2);
5686 if (c == '\n')
5687 break;
5688 }
5689 /* In all other cases, we fail. */
5690 goto fail;
5691
5692
5693 /* endline is the dual of begline. */
5694 case endline:
5695 DEBUG_PRINT ("EXECUTING endline.\n");
5696
5697 if (AT_STRINGS_END (d))
5698 {
5699 if (!bufp->not_eol) break;
5700 }
5701 else
5702 {
5703 PREFETCH_NOLIMIT ();
5704 if (*d == '\n')
5705 break;
5706 }
5707 goto fail;
5708
5709
5710 /* Match at the very beginning of the data. */
5711 case begbuf:
5712 DEBUG_PRINT ("EXECUTING begbuf.\n");
5713 if (AT_STRINGS_BEG (d))
5714 break;
5715 goto fail;
5716
5717
5718 /* Match at the very end of the data. */
5719 case endbuf:
5720 DEBUG_PRINT ("EXECUTING endbuf.\n");
5721 if (AT_STRINGS_END (d))
5722 break;
5723 goto fail;
5724
5725
5726 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
5727 pushes NULL as the value for the string on the stack. Then
5728 `POP_FAILURE_POINT' will keep the current value for the
5729 string, instead of restoring it. To see why, consider
5730 matching `foo\nbar' against `.*\n'. The .* matches the foo;
5731 then the . fails against the \n. But the next thing we want
5732 to do is match the \n against the \n; if we restored the
5733 string value, we would be back at the foo.
5734
5735 Because this is used only in specific cases, we don't need to
5736 check all the things that `on_failure_jump' does, to make
5737 sure the right things get saved on the stack. Hence we don't
5738 share its code. The only reason to push anything on the
5739 stack at all is that otherwise we would have to change
5740 `anychar's code to do something besides goto fail in this
5741 case; that seems worse than this. */
5742 case on_failure_keep_string_jump:
5743 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5744 DEBUG_PRINT ("EXECUTING on_failure_keep_string_jump %d (to %p):\n",
5745 mcnt, p + mcnt);
5746
5747 PUSH_FAILURE_POINT (p - 3, NULL);
5748 break;
5749
5750 /* A nasty loop is introduced by the non-greedy *? and +?.
5751 With such loops, the stack only ever contains one failure point
5752 at a time, so that a plain on_failure_jump_loop kind of
5753 cycle detection cannot work. Worse yet, such a detection
5754 can not only fail to detect a cycle, but it can also wrongly
5755 detect a cycle (between different instantiations of the same
5756 loop).
5757 So the method used for those nasty loops is a little different:
5758 We use a special cycle-detection-stack-frame which is pushed
5759 when the on_failure_jump_nastyloop failure-point is *popped*.
5760 This special frame thus marks the beginning of one iteration
5761 through the loop and we can hence easily check right here
5762 whether something matched between the beginning and the end of
5763 the loop. */
5764 case on_failure_jump_nastyloop:
5765 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5766 DEBUG_PRINT ("EXECUTING on_failure_jump_nastyloop %d (to %p):\n",
5767 mcnt, p + mcnt);
5768
5769 assert ((re_opcode_t)p[-4] == no_op);
5770 {
5771 int cycle = 0;
5772 CHECK_INFINITE_LOOP (p - 4, d);
5773 if (!cycle)
5774 /* If there's a cycle, just continue without pushing
5775 this failure point. The failure point is the "try again"
5776 option, which shouldn't be tried.
5777 We want (x?)*?y\1z to match both xxyz and xxyxz. */
5778 PUSH_FAILURE_POINT (p - 3, d);
5779 }
5780 break;
5781
5782 /* Simple loop detecting on_failure_jump: just check on the
5783 failure stack if the same spot was already hit earlier. */
5784 case on_failure_jump_loop:
5785 on_failure:
5786 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5787 DEBUG_PRINT ("EXECUTING on_failure_jump_loop %d (to %p):\n",
5788 mcnt, p + mcnt);
5789 {
5790 int cycle = 0;
5791 CHECK_INFINITE_LOOP (p - 3, d);
5792 if (cycle)
5793 /* If there's a cycle, get out of the loop, as if the matching
5794 had failed. We used to just `goto fail' here, but that was
5795 aborting the search a bit too early: we want to keep the
5796 empty-loop-match and keep matching after the loop.
5797 We want (x?)*y\1z to match both xxyz and xxyxz. */
5798 p += mcnt;
5799 else
5800 PUSH_FAILURE_POINT (p - 3, d);
5801 }
5802 break;
5803
5804
5805 /* Uses of on_failure_jump:
5806
5807 Each alternative starts with an on_failure_jump that points
5808 to the beginning of the next alternative. Each alternative
5809 except the last ends with a jump that in effect jumps past
5810 the rest of the alternatives. (They really jump to the
5811 ending jump of the following alternative, because tensioning
5812 these jumps is a hassle.)
5813
5814 Repeats start with an on_failure_jump that points past both
5815 the repetition text and either the following jump or
5816 pop_failure_jump back to this on_failure_jump. */
5817 case on_failure_jump:
5818 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5819 DEBUG_PRINT ("EXECUTING on_failure_jump %d (to %p):\n",
5820 mcnt, p + mcnt);
5821
5822 PUSH_FAILURE_POINT (p -3, d);
5823 break;
5824
5825 /* This operation is used for greedy *.
5826 Compare the beginning of the repeat with what in the
5827 pattern follows its end. If we can establish that there
5828 is nothing that they would both match, i.e., that we
5829 would have to backtrack because of (as in, e.g., `a*a')
5830 then we can use a non-backtracking loop based on
5831 on_failure_keep_string_jump instead of on_failure_jump. */
5832 case on_failure_jump_smart:
5833 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5834 DEBUG_PRINT ("EXECUTING on_failure_jump_smart %d (to %p).\n",
5835 mcnt, p + mcnt);
5836 {
5837 re_char *p1 = p; /* Next operation. */
5838 /* Here, we discard `const', making re_match non-reentrant. */
5839 unsigned char *p2 = (unsigned char*) p + mcnt; /* Jump dest. */
5840 unsigned char *p3 = (unsigned char*) p - 3; /* opcode location. */
5841
5842 p -= 3; /* Reset so that we will re-execute the
5843 instruction once it's been changed. */
5844
5845 EXTRACT_NUMBER (mcnt, p2 - 2);
5846
5847 /* Ensure this is a indeed the trivial kind of loop
5848 we are expecting. */
5849 assert (skip_one_char (p1) == p2 - 3);
5850 assert ((re_opcode_t) p2[-3] == jump && p2 + mcnt == p);
5851 DEBUG_STATEMENT (debug += 2);
5852 if (mutually_exclusive_p (bufp, p1, p2))
5853 {
5854 /* Use a fast `on_failure_keep_string_jump' loop. */
5855 DEBUG_PRINT (" smart exclusive => fast loop.\n");
5856 *p3 = (unsigned char) on_failure_keep_string_jump;
5857 STORE_NUMBER (p2 - 2, mcnt + 3);
5858 }
5859 else
5860 {
5861 /* Default to a safe `on_failure_jump' loop. */
5862 DEBUG_PRINT (" smart default => slow loop.\n");
5863 *p3 = (unsigned char) on_failure_jump;
5864 }
5865 DEBUG_STATEMENT (debug -= 2);
5866 }
5867 break;
5868
5869 /* Unconditionally jump (without popping any failure points). */
5870 case jump:
5871 unconditional_jump:
5872 IMMEDIATE_QUIT_CHECK;
5873 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
5874 DEBUG_PRINT ("EXECUTING jump %d ", mcnt);
5875 p += mcnt; /* Do the jump. */
5876 DEBUG_PRINT ("(to %p).\n", p);
5877 break;
5878
5879
5880 /* Have to succeed matching what follows at least n times.
5881 After that, handle like `on_failure_jump'. */
5882 case succeed_n:
5883 /* Signedness doesn't matter since we only compare MCNT to 0. */
5884 EXTRACT_NUMBER (mcnt, p + 2);
5885 DEBUG_PRINT ("EXECUTING succeed_n %d.\n", mcnt);
5886
5887 /* Originally, mcnt is how many times we HAVE to succeed. */
5888 if (mcnt != 0)
5889 {
5890 /* Here, we discard `const', making re_match non-reentrant. */
5891 unsigned char *p2 = (unsigned char*) p + 2; /* counter loc. */
5892 mcnt--;
5893 p += 4;
5894 PUSH_NUMBER (p2, mcnt);
5895 }
5896 else
5897 /* The two bytes encoding mcnt == 0 are two no_op opcodes. */
5898 goto on_failure;
5899 break;
5900
5901 case jump_n:
5902 /* Signedness doesn't matter since we only compare MCNT to 0. */
5903 EXTRACT_NUMBER (mcnt, p + 2);
5904 DEBUG_PRINT ("EXECUTING jump_n %d.\n", mcnt);
5905
5906 /* Originally, this is how many times we CAN jump. */
5907 if (mcnt != 0)
5908 {
5909 /* Here, we discard `const', making re_match non-reentrant. */
5910 unsigned char *p2 = (unsigned char*) p + 2; /* counter loc. */
5911 mcnt--;
5912 PUSH_NUMBER (p2, mcnt);
5913 goto unconditional_jump;
5914 }
5915 /* If don't have to jump any more, skip over the rest of command. */
5916 else
5917 p += 4;
5918 break;
5919
5920 case set_number_at:
5921 {
5922 unsigned char *p2; /* Location of the counter. */
5923 DEBUG_PRINT ("EXECUTING set_number_at.\n");
5924
5925 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5926 /* Here, we discard `const', making re_match non-reentrant. */
5927 p2 = (unsigned char*) p + mcnt;
5928 /* Signedness doesn't matter since we only copy MCNT's bits. */
5929 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5930 DEBUG_PRINT (" Setting %p to %d.\n", p2, mcnt);
5931 PUSH_NUMBER (p2, mcnt);
5932 break;
5933 }
5934
5935 case wordbound:
5936 case notwordbound:
5937 {
5938 boolean not = (re_opcode_t) *(p - 1) == notwordbound;
5939 DEBUG_PRINT ("EXECUTING %swordbound.\n", not ? "not" : "");
5940
5941 /* We SUCCEED (or FAIL) in one of the following cases: */
5942
5943 /* Case 1: D is at the beginning or the end of string. */
5944 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
5945 not = !not;
5946 else
5947 {
5948 /* C1 is the character before D, S1 is the syntax of C1, C2
5949 is the character at D, and S2 is the syntax of C2. */
5950 re_wchar_t c1, c2;
5951 int s1, s2;
5952 int dummy;
5953 #ifdef emacs
5954 ssize_t offset = PTR_TO_OFFSET (d - 1);
5955 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5956 UPDATE_SYNTAX_TABLE_FAST (charpos);
5957 #endif
5958 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
5959 s1 = SYNTAX (c1);
5960 #ifdef emacs
5961 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos + 1);
5962 #endif
5963 PREFETCH_NOLIMIT ();
5964 GET_CHAR_AFTER (c2, d, dummy);
5965 s2 = SYNTAX (c2);
5966
5967 if (/* Case 2: Only one of S1 and S2 is Sword. */
5968 ((s1 == Sword) != (s2 == Sword))
5969 /* Case 3: Both of S1 and S2 are Sword, and macro
5970 WORD_BOUNDARY_P (C1, C2) returns nonzero. */
5971 || ((s1 == Sword) && WORD_BOUNDARY_P (c1, c2)))
5972 not = !not;
5973 }
5974 if (not)
5975 break;
5976 else
5977 goto fail;
5978 }
5979
5980 case wordbeg:
5981 DEBUG_PRINT ("EXECUTING wordbeg.\n");
5982
5983 /* We FAIL in one of the following cases: */
5984
5985 /* Case 1: D is at the end of string. */
5986 if (AT_STRINGS_END (d))
5987 goto fail;
5988 else
5989 {
5990 /* C1 is the character before D, S1 is the syntax of C1, C2
5991 is the character at D, and S2 is the syntax of C2. */
5992 re_wchar_t c1, c2;
5993 int s1, s2;
5994 int dummy;
5995 #ifdef emacs
5996 ssize_t offset = PTR_TO_OFFSET (d);
5997 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5998 UPDATE_SYNTAX_TABLE_FAST (charpos);
5999 #endif
6000 PREFETCH ();
6001 GET_CHAR_AFTER (c2, d, dummy);
6002 s2 = SYNTAX (c2);
6003
6004 /* Case 2: S2 is not Sword. */
6005 if (s2 != Sword)
6006 goto fail;
6007
6008 /* Case 3: D is not at the beginning of string ... */
6009 if (!AT_STRINGS_BEG (d))
6010 {
6011 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
6012 #ifdef emacs
6013 UPDATE_SYNTAX_TABLE_BACKWARD (charpos - 1);
6014 #endif
6015 s1 = SYNTAX (c1);
6016
6017 /* ... and S1 is Sword, and WORD_BOUNDARY_P (C1, C2)
6018 returns 0. */
6019 if ((s1 == Sword) && !WORD_BOUNDARY_P (c1, c2))
6020 goto fail;
6021 }
6022 }
6023 break;
6024
6025 case wordend:
6026 DEBUG_PRINT ("EXECUTING wordend.\n");
6027
6028 /* We FAIL in one of the following cases: */
6029
6030 /* Case 1: D is at the beginning of string. */
6031 if (AT_STRINGS_BEG (d))
6032 goto fail;
6033 else
6034 {
6035 /* C1 is the character before D, S1 is the syntax of C1, C2
6036 is the character at D, and S2 is the syntax of C2. */
6037 re_wchar_t c1, c2;
6038 int s1, s2;
6039 int dummy;
6040 #ifdef emacs
6041 ssize_t offset = PTR_TO_OFFSET (d) - 1;
6042 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
6043 UPDATE_SYNTAX_TABLE_FAST (charpos);
6044 #endif
6045 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
6046 s1 = SYNTAX (c1);
6047
6048 /* Case 2: S1 is not Sword. */
6049 if (s1 != Sword)
6050 goto fail;
6051
6052 /* Case 3: D is not at the end of string ... */
6053 if (!AT_STRINGS_END (d))
6054 {
6055 PREFETCH_NOLIMIT ();
6056 GET_CHAR_AFTER (c2, d, dummy);
6057 #ifdef emacs
6058 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos);
6059 #endif
6060 s2 = SYNTAX (c2);
6061
6062 /* ... and S2 is Sword, and WORD_BOUNDARY_P (C1, C2)
6063 returns 0. */
6064 if ((s2 == Sword) && !WORD_BOUNDARY_P (c1, c2))
6065 goto fail;
6066 }
6067 }
6068 break;
6069
6070 case symbeg:
6071 DEBUG_PRINT ("EXECUTING symbeg.\n");
6072
6073 /* We FAIL in one of the following cases: */
6074
6075 /* Case 1: D is at the end of string. */
6076 if (AT_STRINGS_END (d))
6077 goto fail;
6078 else
6079 {
6080 /* C1 is the character before D, S1 is the syntax of C1, C2
6081 is the character at D, and S2 is the syntax of C2. */
6082 re_wchar_t c1, c2;
6083 int s1, s2;
6084 #ifdef emacs
6085 ssize_t offset = PTR_TO_OFFSET (d);
6086 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
6087 UPDATE_SYNTAX_TABLE_FAST (charpos);
6088 #endif
6089 PREFETCH ();
6090 c2 = RE_STRING_CHAR (d, target_multibyte);
6091 s2 = SYNTAX (c2);
6092
6093 /* Case 2: S2 is neither Sword nor Ssymbol. */
6094 if (s2 != Sword && s2 != Ssymbol)
6095 goto fail;
6096
6097 /* Case 3: D is not at the beginning of string ... */
6098 if (!AT_STRINGS_BEG (d))
6099 {
6100 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
6101 #ifdef emacs
6102 UPDATE_SYNTAX_TABLE_BACKWARD (charpos - 1);
6103 #endif
6104 s1 = SYNTAX (c1);
6105
6106 /* ... and S1 is Sword or Ssymbol. */
6107 if (s1 == Sword || s1 == Ssymbol)
6108 goto fail;
6109 }
6110 }
6111 break;
6112
6113 case symend:
6114 DEBUG_PRINT ("EXECUTING symend.\n");
6115
6116 /* We FAIL in one of the following cases: */
6117
6118 /* Case 1: D is at the beginning of string. */
6119 if (AT_STRINGS_BEG (d))
6120 goto fail;
6121 else
6122 {
6123 /* C1 is the character before D, S1 is the syntax of C1, C2
6124 is the character at D, and S2 is the syntax of C2. */
6125 re_wchar_t c1, c2;
6126 int s1, s2;
6127 #ifdef emacs
6128 ssize_t offset = PTR_TO_OFFSET (d) - 1;
6129 ssize_t charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
6130 UPDATE_SYNTAX_TABLE_FAST (charpos);
6131 #endif
6132 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
6133 s1 = SYNTAX (c1);
6134
6135 /* Case 2: S1 is neither Ssymbol nor Sword. */
6136 if (s1 != Sword && s1 != Ssymbol)
6137 goto fail;
6138
6139 /* Case 3: D is not at the end of string ... */
6140 if (!AT_STRINGS_END (d))
6141 {
6142 PREFETCH_NOLIMIT ();
6143 c2 = RE_STRING_CHAR (d, target_multibyte);
6144 #ifdef emacs
6145 UPDATE_SYNTAX_TABLE_FORWARD_FAST (charpos + 1);
6146 #endif
6147 s2 = SYNTAX (c2);
6148
6149 /* ... and S2 is Sword or Ssymbol. */
6150 if (s2 == Sword || s2 == Ssymbol)
6151 goto fail;
6152 }
6153 }
6154 break;
6155
6156 case syntaxspec:
6157 case notsyntaxspec:
6158 {
6159 boolean not = (re_opcode_t) *(p - 1) == notsyntaxspec;
6160 mcnt = *p++;
6161 DEBUG_PRINT ("EXECUTING %ssyntaxspec %d.\n", not ? "not" : "",
6162 mcnt);
6163 PREFETCH ();
6164 #ifdef emacs
6165 {
6166 ssize_t offset = PTR_TO_OFFSET (d);
6167 ssize_t pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
6168 UPDATE_SYNTAX_TABLE_FAST (pos1);
6169 }
6170 #endif
6171 {
6172 int len;
6173 re_wchar_t c;
6174
6175 GET_CHAR_AFTER (c, d, len);
6176 if ((SYNTAX (c) != (enum syntaxcode) mcnt) ^ not)
6177 goto fail;
6178 d += len;
6179 }
6180 }
6181 break;
6182
6183 #ifdef emacs
6184 case before_dot:
6185 DEBUG_PRINT ("EXECUTING before_dot.\n");
6186 if (PTR_BYTE_POS (d) >= PT_BYTE)
6187 goto fail;
6188 break;
6189
6190 case at_dot:
6191 DEBUG_PRINT ("EXECUTING at_dot.\n");
6192 if (PTR_BYTE_POS (d) != PT_BYTE)
6193 goto fail;
6194 break;
6195
6196 case after_dot:
6197 DEBUG_PRINT ("EXECUTING after_dot.\n");
6198 if (PTR_BYTE_POS (d) <= PT_BYTE)
6199 goto fail;
6200 break;
6201
6202 case categoryspec:
6203 case notcategoryspec:
6204 {
6205 boolean not = (re_opcode_t) *(p - 1) == notcategoryspec;
6206 mcnt = *p++;
6207 DEBUG_PRINT ("EXECUTING %scategoryspec %d.\n",
6208 not ? "not" : "", mcnt);
6209 PREFETCH ();
6210
6211 {
6212 int len;
6213 re_wchar_t c;
6214 GET_CHAR_AFTER (c, d, len);
6215 if ((!CHAR_HAS_CATEGORY (c, mcnt)) ^ not)
6216 goto fail;
6217 d += len;
6218 }
6219 }
6220 break;
6221
6222 #endif /* emacs */
6223
6224 default:
6225 abort ();
6226 }
6227 continue; /* Successfully executed one pattern command; keep going. */
6228
6229
6230 /* We goto here if a matching operation fails. */
6231 fail:
6232 IMMEDIATE_QUIT_CHECK;
6233 if (!FAIL_STACK_EMPTY ())
6234 {
6235 re_char *str, *pat;
6236 /* A restart point is known. Restore to that state. */
6237 DEBUG_PRINT ("\nFAIL:\n");
6238 POP_FAILURE_POINT (str, pat);
6239 switch (*pat++)
6240 {
6241 case on_failure_keep_string_jump:
6242 assert (str == NULL);
6243 goto continue_failure_jump;
6244
6245 case on_failure_jump_nastyloop:
6246 assert ((re_opcode_t)pat[-2] == no_op);
6247 PUSH_FAILURE_POINT (pat - 2, str);
6248 /* Fallthrough */
6249
6250 case on_failure_jump_loop:
6251 case on_failure_jump:
6252 case succeed_n:
6253 d = str;
6254 continue_failure_jump:
6255 EXTRACT_NUMBER_AND_INCR (mcnt, pat);
6256 p = pat + mcnt;
6257 break;
6258
6259 case no_op:
6260 /* A special frame used for nastyloops. */
6261 goto fail;
6262
6263 default:
6264 abort ();
6265 }
6266
6267 assert (p >= bufp->buffer && p <= pend);
6268
6269 if (d >= string1 && d <= end1)
6270 dend = end_match_1;
6271 }
6272 else
6273 break; /* Matching at this starting point really fails. */
6274 } /* for (;;) */
6275
6276 if (best_regs_set)
6277 goto restore_best_regs;
6278
6279 FREE_VARIABLES ();
6280
6281 return -1; /* Failure to match. */
6282 }
6283 \f
6284 /* Subroutine definitions for re_match_2. */
6285
6286 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
6287 bytes; nonzero otherwise. */
6288
6289 static int
6290 bcmp_translate (const_re_char *s1, const_re_char *s2, register ssize_t len,
6291 RE_TRANSLATE_TYPE translate, const int target_multibyte)
6292 {
6293 register re_char *p1 = s1, *p2 = s2;
6294 re_char *p1_end = s1 + len;
6295 re_char *p2_end = s2 + len;
6296
6297 /* FIXME: Checking both p1 and p2 presumes that the two strings might have
6298 different lengths, but relying on a single `len' would break this. -sm */
6299 while (p1 < p1_end && p2 < p2_end)
6300 {
6301 int p1_charlen, p2_charlen;
6302 re_wchar_t p1_ch, p2_ch;
6303
6304 GET_CHAR_AFTER (p1_ch, p1, p1_charlen);
6305 GET_CHAR_AFTER (p2_ch, p2, p2_charlen);
6306
6307 if (RE_TRANSLATE (translate, p1_ch)
6308 != RE_TRANSLATE (translate, p2_ch))
6309 return 1;
6310
6311 p1 += p1_charlen, p2 += p2_charlen;
6312 }
6313
6314 if (p1 != p1_end || p2 != p2_end)
6315 return 1;
6316
6317 return 0;
6318 }
6319 \f
6320 /* Entry points for GNU code. */
6321
6322 /* re_compile_pattern is the GNU regular expression compiler: it
6323 compiles PATTERN (of length SIZE) and puts the result in BUFP.
6324 Returns 0 if the pattern was valid, otherwise an error string.
6325
6326 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
6327 are set in BUFP on entry.
6328
6329 We call regex_compile to do the actual compilation. */
6330
6331 const char *
6332 re_compile_pattern (const char *pattern, size_t length,
6333 struct re_pattern_buffer *bufp)
6334 {
6335 reg_errcode_t ret;
6336
6337 /* GNU code is written to assume at least RE_NREGS registers will be set
6338 (and at least one extra will be -1). */
6339 bufp->regs_allocated = REGS_UNALLOCATED;
6340
6341 /* And GNU code determines whether or not to get register information
6342 by passing null for the REGS argument to re_match, etc., not by
6343 setting no_sub. */
6344 bufp->no_sub = 0;
6345
6346 ret = regex_compile ((re_char*) pattern, length, re_syntax_options, bufp);
6347
6348 if (!ret)
6349 return NULL;
6350 return gettext (re_error_msgid[(int) ret]);
6351 }
6352 WEAK_ALIAS (__re_compile_pattern, re_compile_pattern)
6353 \f
6354 /* Entry points compatible with 4.2 BSD regex library. We don't define
6355 them unless specifically requested. */
6356
6357 #if defined _REGEX_RE_COMP || defined _LIBC
6358
6359 /* BSD has one and only one pattern buffer. */
6360 static struct re_pattern_buffer re_comp_buf;
6361
6362 char *
6363 # ifdef _LIBC
6364 /* Make these definitions weak in libc, so POSIX programs can redefine
6365 these names if they don't use our functions, and still use
6366 regcomp/regexec below without link errors. */
6367 weak_function
6368 # endif
6369 re_comp (const char *s)
6370 {
6371 reg_errcode_t ret;
6372
6373 if (!s)
6374 {
6375 if (!re_comp_buf.buffer)
6376 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6377 return (char *) gettext ("No previous regular expression");
6378 return 0;
6379 }
6380
6381 if (!re_comp_buf.buffer)
6382 {
6383 re_comp_buf.buffer = malloc (200);
6384 if (re_comp_buf.buffer == NULL)
6385 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6386 return (char *) gettext (re_error_msgid[(int) REG_ESPACE]);
6387 re_comp_buf.allocated = 200;
6388
6389 re_comp_buf.fastmap = malloc (1 << BYTEWIDTH);
6390 if (re_comp_buf.fastmap == NULL)
6391 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6392 return (char *) gettext (re_error_msgid[(int) REG_ESPACE]);
6393 }
6394
6395 /* Since `re_exec' always passes NULL for the `regs' argument, we
6396 don't need to initialize the pattern buffer fields which affect it. */
6397
6398 ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
6399
6400 if (!ret)
6401 return NULL;
6402
6403 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
6404 return (char *) gettext (re_error_msgid[(int) ret]);
6405 }
6406
6407
6408 int
6409 # ifdef _LIBC
6410 weak_function
6411 # endif
6412 re_exec (const char *s)
6413 {
6414 const size_t len = strlen (s);
6415 return re_search (&re_comp_buf, s, len, 0, len, 0) >= 0;
6416 }
6417 #endif /* _REGEX_RE_COMP */
6418 \f
6419 /* POSIX.2 functions. Don't define these for Emacs. */
6420
6421 #ifndef emacs
6422
6423 /* regcomp takes a regular expression as a string and compiles it.
6424
6425 PREG is a regex_t *. We do not expect any fields to be initialized,
6426 since POSIX says we shouldn't. Thus, we set
6427
6428 `buffer' to the compiled pattern;
6429 `used' to the length of the compiled pattern;
6430 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
6431 REG_EXTENDED bit in CFLAGS is set; otherwise, to
6432 RE_SYNTAX_POSIX_BASIC;
6433 `fastmap' to an allocated space for the fastmap;
6434 `fastmap_accurate' to zero;
6435 `re_nsub' to the number of subexpressions in PATTERN.
6436
6437 PATTERN is the address of the pattern string.
6438
6439 CFLAGS is a series of bits which affect compilation.
6440
6441 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
6442 use POSIX basic syntax.
6443
6444 If REG_NEWLINE is set, then . and [^...] don't match newline.
6445 Also, regexec will try a match beginning after every newline.
6446
6447 If REG_ICASE is set, then we considers upper- and lowercase
6448 versions of letters to be equivalent when matching.
6449
6450 If REG_NOSUB is set, then when PREG is passed to regexec, that
6451 routine will report only success or failure, and nothing about the
6452 registers.
6453
6454 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
6455 the return codes and their meanings.) */
6456
6457 reg_errcode_t
6458 regcomp (regex_t *_Restrict_ preg, const char *_Restrict_ pattern,
6459 int cflags)
6460 {
6461 reg_errcode_t ret;
6462 reg_syntax_t syntax
6463 = (cflags & REG_EXTENDED) ?
6464 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
6465
6466 /* regex_compile will allocate the space for the compiled pattern. */
6467 preg->buffer = 0;
6468 preg->allocated = 0;
6469 preg->used = 0;
6470
6471 /* Try to allocate space for the fastmap. */
6472 preg->fastmap = malloc (1 << BYTEWIDTH);
6473
6474 if (cflags & REG_ICASE)
6475 {
6476 unsigned i;
6477
6478 preg->translate = malloc (CHAR_SET_SIZE * sizeof *preg->translate);
6479 if (preg->translate == NULL)
6480 return (int) REG_ESPACE;
6481
6482 /* Map uppercase characters to corresponding lowercase ones. */
6483 for (i = 0; i < CHAR_SET_SIZE; i++)
6484 preg->translate[i] = ISUPPER (i) ? TOLOWER (i) : i;
6485 }
6486 else
6487 preg->translate = NULL;
6488
6489 /* If REG_NEWLINE is set, newlines are treated differently. */
6490 if (cflags & REG_NEWLINE)
6491 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
6492 syntax &= ~RE_DOT_NEWLINE;
6493 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
6494 }
6495 else
6496 syntax |= RE_NO_NEWLINE_ANCHOR;
6497
6498 preg->no_sub = !!(cflags & REG_NOSUB);
6499
6500 /* POSIX says a null character in the pattern terminates it, so we
6501 can use strlen here in compiling the pattern. */
6502 ret = regex_compile ((re_char*) pattern, strlen (pattern), syntax, preg);
6503
6504 /* POSIX doesn't distinguish between an unmatched open-group and an
6505 unmatched close-group: both are REG_EPAREN. */
6506 if (ret == REG_ERPAREN)
6507 ret = REG_EPAREN;
6508
6509 if (ret == REG_NOERROR && preg->fastmap)
6510 { /* Compute the fastmap now, since regexec cannot modify the pattern
6511 buffer. */
6512 re_compile_fastmap (preg);
6513 if (preg->can_be_null)
6514 { /* The fastmap can't be used anyway. */
6515 free (preg->fastmap);
6516 preg->fastmap = NULL;
6517 }
6518 }
6519 return ret;
6520 }
6521 WEAK_ALIAS (__regcomp, regcomp)
6522
6523
6524 /* regexec searches for a given pattern, specified by PREG, in the
6525 string STRING.
6526
6527 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
6528 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
6529 least NMATCH elements, and we set them to the offsets of the
6530 corresponding matched substrings.
6531
6532 EFLAGS specifies `execution flags' which affect matching: if
6533 REG_NOTBOL is set, then ^ does not match at the beginning of the
6534 string; if REG_NOTEOL is set, then $ does not match at the end.
6535
6536 We return 0 if we find a match and REG_NOMATCH if not. */
6537
6538 reg_errcode_t
6539 regexec (const regex_t *_Restrict_ preg, const char *_Restrict_ string,
6540 size_t nmatch, regmatch_t pmatch[_Restrict_arr_], int eflags)
6541 {
6542 regoff_t ret;
6543 struct re_registers regs;
6544 regex_t private_preg;
6545 size_t len = strlen (string);
6546 boolean want_reg_info = !preg->no_sub && nmatch > 0 && pmatch;
6547
6548 private_preg = *preg;
6549
6550 private_preg.not_bol = !!(eflags & REG_NOTBOL);
6551 private_preg.not_eol = !!(eflags & REG_NOTEOL);
6552
6553 /* The user has told us exactly how many registers to return
6554 information about, via `nmatch'. We have to pass that on to the
6555 matching routines. */
6556 private_preg.regs_allocated = REGS_FIXED;
6557
6558 if (want_reg_info)
6559 {
6560 regs.num_regs = nmatch;
6561 regs.start = TALLOC (nmatch * 2, regoff_t);
6562 if (regs.start == NULL)
6563 return REG_NOMATCH;
6564 regs.end = regs.start + nmatch;
6565 }
6566
6567 /* Instead of using not_eol to implement REG_NOTEOL, we could simply
6568 pass (&private_preg, string, len + 1, 0, len, ...) pretending the string
6569 was a little bit longer but still only matching the real part.
6570 This works because the `endline' will check for a '\n' and will find a
6571 '\0', correctly deciding that this is not the end of a line.
6572 But it doesn't work out so nicely for REG_NOTBOL, since we don't have
6573 a convenient '\0' there. For all we know, the string could be preceded
6574 by '\n' which would throw things off. */
6575
6576 /* Perform the searching operation. */
6577 ret = re_search (&private_preg, string, len,
6578 /* start: */ 0, /* range: */ len,
6579 want_reg_info ? &regs : 0);
6580
6581 /* Copy the register information to the POSIX structure. */
6582 if (want_reg_info)
6583 {
6584 if (ret >= 0)
6585 {
6586 unsigned r;
6587
6588 for (r = 0; r < nmatch; r++)
6589 {
6590 pmatch[r].rm_so = regs.start[r];
6591 pmatch[r].rm_eo = regs.end[r];
6592 }
6593 }
6594
6595 /* If we needed the temporary register info, free the space now. */
6596 free (regs.start);
6597 }
6598
6599 /* We want zero return to mean success, unlike `re_search'. */
6600 return ret >= 0 ? REG_NOERROR : REG_NOMATCH;
6601 }
6602 WEAK_ALIAS (__regexec, regexec)
6603
6604
6605 /* Returns a message corresponding to an error code, ERR_CODE, returned
6606 from either regcomp or regexec. We don't use PREG here.
6607
6608 ERR_CODE was previously called ERRCODE, but that name causes an
6609 error with msvc8 compiler. */
6610
6611 size_t
6612 regerror (int err_code, const regex_t *preg, char *errbuf, size_t errbuf_size)
6613 {
6614 const char *msg;
6615 size_t msg_size;
6616
6617 if (err_code < 0
6618 || err_code >= (sizeof (re_error_msgid) / sizeof (re_error_msgid[0])))
6619 /* Only error codes returned by the rest of the code should be passed
6620 to this routine. If we are given anything else, or if other regex
6621 code generates an invalid error code, then the program has a bug.
6622 Dump core so we can fix it. */
6623 abort ();
6624
6625 msg = gettext (re_error_msgid[err_code]);
6626
6627 msg_size = strlen (msg) + 1; /* Includes the null. */
6628
6629 if (errbuf_size != 0)
6630 {
6631 if (msg_size > errbuf_size)
6632 {
6633 memcpy (errbuf, msg, errbuf_size - 1);
6634 errbuf[errbuf_size - 1] = 0;
6635 }
6636 else
6637 strcpy (errbuf, msg);
6638 }
6639
6640 return msg_size;
6641 }
6642 WEAK_ALIAS (__regerror, regerror)
6643
6644
6645 /* Free dynamically allocated space used by PREG. */
6646
6647 void
6648 regfree (regex_t *preg)
6649 {
6650 free (preg->buffer);
6651 preg->buffer = NULL;
6652
6653 preg->allocated = 0;
6654 preg->used = 0;
6655
6656 free (preg->fastmap);
6657 preg->fastmap = NULL;
6658 preg->fastmap_accurate = 0;
6659
6660 free (preg->translate);
6661 preg->translate = NULL;
6662 }
6663 WEAK_ALIAS (__regfree, regfree)
6664
6665 #endif /* not emacs */
Emacs repository mirror