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