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