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