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