HCoop / bpt / emacs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Fix comment for find_charset_in_text.
[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 }
3213
3214
3215 /* The dual of at_begline_loc_p. This one is for $. We assume there is
3216 at least one character after the $, i.e., `P < PEND'. */
3217
3218 static boolean
3219 at_endline_loc_p (p, pend, syntax)
3220 const unsigned char *p, *pend;
3221 reg_syntax_t syntax;
3222 {
3223 const unsigned char *next = p;
3224 boolean next_backslash = *next == '\\';
3225 const unsigned char *next_next = p + 1 < pend ? p + 1 : 0;
3226
3227 return
3228 /* Before a subexpression? */
3229 (syntax & RE_NO_BK_PARENS ? *next == ')'
3230 : next_backslash && next_next && *next_next == ')')
3231 /* Before an alternative? */
3232 || (syntax & RE_NO_BK_VBAR ? *next == '|'
3233 : next_backslash && next_next && *next_next == '|');
3234 }
3235
3236
3237 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
3238 false if it's not. */
3239
3240 static boolean
3241 group_in_compile_stack (compile_stack, regnum)
3242 compile_stack_type compile_stack;
3243 regnum_t regnum;
3244 {
3245 int this_element;
3246
3247 for (this_element = compile_stack.avail - 1;
3248 this_element >= 0;
3249 this_element--)
3250 if (compile_stack.stack[this_element].regnum == regnum)
3251 return true;
3252
3253 return false;
3254 }
3255 \f
3256 /* analyse_first.
3257 If fastmap is non-NULL, go through the pattern and fill fastmap
3258 with all the possible leading chars. If fastmap is NULL, don't
3259 bother filling it up (obviously) and only return whether the
3260 pattern could potentially match the empty string.
3261
3262 Return 1 if p..pend might match the empty string.
3263 Return 0 if p..pend matches at least one char.
3264 Return -1 if p..pend matches at least one char, but fastmap was not
3265 updated accurately.
3266 Return -2 if an error occurred. */
3267
3268 static int
3269 analyse_first (p, pend, fastmap, multibyte)
3270 unsigned char *p, *pend;
3271 char *fastmap;
3272 const int multibyte;
3273 {
3274 int j, k;
3275 boolean not;
3276 #ifdef MATCH_MAY_ALLOCATE
3277 fail_stack_type fail_stack;
3278 #endif
3279 #ifndef REGEX_MALLOC
3280 char *destination;
3281 #endif
3282
3283 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
3284 /* This holds the pointer to the failure stack, when
3285 it is allocated relocatably. */
3286 fail_stack_elt_t *failure_stack_ptr;
3287 #endif
3288
3289 /* Assume that each path through the pattern can be null until
3290 proven otherwise. We set this false at the bottom of switch
3291 statement, to which we get only if a particular path doesn't
3292 match the empty string. */
3293 boolean path_can_be_null = true;
3294
3295 /* If all elements for base leading-codes in fastmap is set, this
3296 flag is set true. */
3297 boolean match_any_multibyte_characters = false;
3298
3299 assert (p);
3300
3301 INIT_FAIL_STACK ();
3302
3303 /* The loop below works as follows:
3304 - It has a working-list kept in the PATTERN_STACK and which basically
3305 starts by only containing a pointer to the first operation.
3306 - If the opcode we're looking at is a match against some set of
3307 chars, then we add those chars to the fastmap and go on to the
3308 next work element from the worklist (done via `break').
3309 - If the opcode is a control operator on the other hand, we either
3310 ignore it (if it's meaningless at this point, such as `start_memory')
3311 or execute it (if it's a jump). If the jump has several destinations
3312 (i.e. `on_failure_jump'), then we push the other destination onto the
3313 worklist.
3314 We guarantee termination by ignoring backward jumps (more or less),
3315 so that `p' is monotonically increasing. More to the point, we
3316 never set `p' (or push) anything `<= p1'. */
3317
3318 /* If can_be_null is set, then the fastmap will not be used anyway. */
3319 while (1)
3320 {
3321 /* `p1' is used as a marker of how far back a `on_failure_jump'
3322 can go without being ignored. It is normally equal to `p'
3323 (which prevents any backward `on_failure_jump') except right
3324 after a plain `jump', to allow patterns such as:
3325 0: jump 10
3326 3..9: <body>
3327 10: on_failure_jump 3
3328 as used for the *? operator. */
3329 unsigned char *p1 = p;
3330
3331 if (p >= pend)
3332 {
3333 if (path_can_be_null)
3334 return (RESET_FAIL_STACK (), 1);
3335
3336 /* We have reached the (effective) end of pattern. */
3337 if (PATTERN_STACK_EMPTY ())
3338 return (RESET_FAIL_STACK (), 0);
3339
3340 p = (unsigned char*) POP_PATTERN_OP ();
3341 path_can_be_null = true;
3342 continue;
3343 }
3344
3345 /* We should never be about to go beyond the end of the pattern. */
3346 assert (p < pend);
3347
3348 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
3349 {
3350 case succeed:
3351 p = pend;
3352 continue;
3353
3354 case duplicate:
3355 /* If the first character has to match a backreference, that means
3356 that the group was empty (since it already matched). Since this
3357 is the only case that interests us here, we can assume that the
3358 backreference must match the empty string. */
3359 p++;
3360 continue;
3361
3362
3363 /* Following are the cases which match a character. These end
3364 with `break'. */
3365
3366 case exactn:
3367 if (fastmap) fastmap[p[1]] = 1;
3368 break;
3369
3370
3371 case anychar:
3372 /* We could put all the chars except for \n (and maybe \0)
3373 but we don't bother since it is generally not worth it. */
3374 if (!fastmap) break;
3375 return (RESET_FAIL_STACK (), -1);
3376
3377
3378 case charset_not:
3379 /* Chars beyond end of bitmap are possible matches.
3380 All the single-byte codes can occur in multibyte buffers.
3381 So any that are not listed in the charset
3382 are possible matches, even in multibyte buffers. */
3383 if (!fastmap) break;
3384 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH;
3385 j < (1 << BYTEWIDTH); j++)
3386 fastmap[j] = 1;
3387 /* Fallthrough */
3388 case charset:
3389 if (!fastmap) break;
3390 not = (re_opcode_t) *(p - 1) == charset_not;
3391 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++;
3392 j >= 0; j--)
3393 if (!!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) ^ not)
3394 fastmap[j] = 1;
3395
3396 if ((not && multibyte)
3397 /* Any character set can possibly contain a character
3398 which doesn't match the specified set of characters. */
3399 || (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
3400 && CHARSET_RANGE_TABLE_BITS (&p[-2]) != 0))
3401 /* If we can match a character class, we can match
3402 any character set. */
3403 {
3404 set_fastmap_for_multibyte_characters:
3405 if (match_any_multibyte_characters == false)
3406 {
3407 for (j = 0x80; j < 0xA0; j++) /* XXX */
3408 if (BASE_LEADING_CODE_P (j))
3409 fastmap[j] = 1;
3410 match_any_multibyte_characters = true;
3411 }
3412 }
3413
3414 else if (!not && CHARSET_RANGE_TABLE_EXISTS_P (&p[-2])
3415 && match_any_multibyte_characters == false)
3416 {
3417 /* Set fastmap[I] 1 where I is a base leading code of each
3418 multibyte character in the range table. */
3419 int c, count;
3420
3421 /* Make P points the range table. `+ 2' is to skip flag
3422 bits for a character class. */
3423 p += CHARSET_BITMAP_SIZE (&p[-2]) + 2;
3424
3425 /* Extract the number of ranges in range table into COUNT. */
3426 EXTRACT_NUMBER_AND_INCR (count, p);
3427 for (; count > 0; count--, p += 2 * 3) /* XXX */
3428 {
3429 /* Extract the start of each range. */
3430 EXTRACT_CHARACTER (c, p);
3431 j = CHAR_CHARSET (c);
3432 fastmap[CHARSET_LEADING_CODE_BASE (j)] = 1;
3433 }
3434 }
3435 break;
3436
3437 case syntaxspec:
3438 case notsyntaxspec:
3439 if (!fastmap) break;
3440 #ifndef emacs
3441 not = (re_opcode_t)p[-1] == notsyntaxspec;
3442 k = *p++;
3443 for (j = 0; j < (1 << BYTEWIDTH); j++)
3444 if ((SYNTAX (j) == (enum syntaxcode) k) ^ not)
3445 fastmap[j] = 1;
3446 break;
3447 #else /* emacs */
3448 /* This match depends on text properties. These end with
3449 aborting optimizations. */
3450 return (RESET_FAIL_STACK (), -1);
3451
3452 case categoryspec:
3453 case notcategoryspec:
3454 if (!fastmap) break;
3455 not = (re_opcode_t)p[-1] == notcategoryspec;
3456 k = *p++;
3457 for (j = 0; j < (1 << BYTEWIDTH); j++)
3458 if ((CHAR_HAS_CATEGORY (j, k)) ^ not)
3459 fastmap[j] = 1;
3460
3461 if (multibyte)
3462 /* Any character set can possibly contain a character
3463 whose category is K (or not). */
3464 goto set_fastmap_for_multibyte_characters;
3465 break;
3466
3467 /* All cases after this match the empty string. These end with
3468 `continue'. */
3469
3470 case before_dot:
3471 case at_dot:
3472 case after_dot:
3473 #endif /* !emacs */
3474 case no_op:
3475 case begline:
3476 case endline:
3477 case begbuf:
3478 case endbuf:
3479 case wordbound:
3480 case notwordbound:
3481 case wordbeg:
3482 case wordend:
3483 continue;
3484
3485
3486 case jump:
3487 EXTRACT_NUMBER_AND_INCR (j, p);
3488 if (j < 0)
3489 /* Backward jumps can only go back to code that we've already
3490 visited. `re_compile' should make sure this is true. */
3491 break;
3492 p += j;
3493 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
3494 {
3495 case on_failure_jump:
3496 case on_failure_keep_string_jump:
3497 case on_failure_jump_loop:
3498 case on_failure_jump_nastyloop:
3499 case on_failure_jump_smart:
3500 p++;
3501 break;
3502 default:
3503 continue;
3504 };
3505 /* Keep `p1' to allow the `on_failure_jump' we are jumping to
3506 to jump back to "just after here". */
3507 /* Fallthrough */
3508
3509 case on_failure_jump:
3510 case on_failure_keep_string_jump:
3511 case on_failure_jump_nastyloop:
3512 case on_failure_jump_loop:
3513 case on_failure_jump_smart:
3514 EXTRACT_NUMBER_AND_INCR (j, p);
3515 if (p + j <= p1)
3516 ; /* Backward jump to be ignored. */
3517 else if (!PUSH_PATTERN_OP (p + j, fail_stack))
3518 return (RESET_FAIL_STACK (), -2);
3519 continue;
3520
3521
3522 case jump_n:
3523 /* This code simply does not properly handle forward jump_n. */
3524 DEBUG_STATEMENT (EXTRACT_NUMBER (j, p); assert (j < 0));
3525 p += 4;
3526 /* jump_n can either jump or fall through. The (backward) jump
3527 case has already been handled, so we only need to look at the
3528 fallthrough case. */
3529 continue;
3530
3531 case succeed_n:
3532 /* If N == 0, it should be an on_failure_jump_loop instead. */
3533 DEBUG_STATEMENT (EXTRACT_NUMBER (j, p + 2); assert (j > 0));
3534 p += 4;
3535 /* We only care about one iteration of the loop, so we don't
3536 need to consider the case where this behaves like an
3537 on_failure_jump. */
3538 continue;
3539
3540
3541 case set_number_at:
3542 p += 4;
3543 continue;
3544
3545
3546 case start_memory:
3547 case stop_memory:
3548 p += 1;
3549 continue;
3550
3551
3552 default:
3553 abort (); /* We have listed all the cases. */
3554 } /* switch *p++ */
3555
3556 /* Getting here means we have found the possible starting
3557 characters for one path of the pattern -- and that the empty
3558 string does not match. We need not follow this path further.
3559 Instead, look at the next alternative (remembered on the
3560 stack), or quit if no more. The test at the top of the loop
3561 does these things. */
3562 path_can_be_null = false;
3563 p = pend;
3564 } /* while p */
3565
3566 return (RESET_FAIL_STACK (), 0);
3567 } /* analyse_first */
3568 \f
3569 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
3570 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
3571 characters can start a string that matches the pattern. This fastmap
3572 is used by re_search to skip quickly over impossible starting points.
3573
3574 Character codes above (1 << BYTEWIDTH) are not represented in the
3575 fastmap, but the leading codes are represented. Thus, the fastmap
3576 indicates which character sets could start a match.
3577
3578 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
3579 area as BUFP->fastmap.
3580
3581 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
3582 the pattern buffer.
3583
3584 Returns 0 if we succeed, -2 if an internal error. */
3585
3586 int
3587 re_compile_fastmap (bufp)
3588 struct re_pattern_buffer *bufp;
3589 {
3590 char *fastmap = bufp->fastmap;
3591 int analysis;
3592
3593 assert (fastmap && bufp->buffer);
3594
3595 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
3596 bufp->fastmap_accurate = 1; /* It will be when we're done. */
3597
3598 analysis = analyse_first (bufp->buffer, bufp->buffer + bufp->used,
3599 fastmap, RE_MULTIBYTE_P (bufp));
3600 if (analysis < -1)
3601 return analysis;
3602 bufp->can_be_null = (analysis != 0);
3603 return 0;
3604 } /* re_compile_fastmap */
3605 \f
3606 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
3607 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
3608 this memory for recording register information. STARTS and ENDS
3609 must be allocated using the malloc library routine, and must each
3610 be at least NUM_REGS * sizeof (regoff_t) bytes long.
3611
3612 If NUM_REGS == 0, then subsequent matches should allocate their own
3613 register data.
3614
3615 Unless this function is called, the first search or match using
3616 PATTERN_BUFFER will allocate its own register data, without
3617 freeing the old data. */
3618
3619 void
3620 re_set_registers (bufp, regs, num_regs, starts, ends)
3621 struct re_pattern_buffer *bufp;
3622 struct re_registers *regs;
3623 unsigned num_regs;
3624 regoff_t *starts, *ends;
3625 {
3626 if (num_regs)
3627 {
3628 bufp->regs_allocated = REGS_REALLOCATE;
3629 regs->num_regs = num_regs;
3630 regs->start = starts;
3631 regs->end = ends;
3632 }
3633 else
3634 {
3635 bufp->regs_allocated = REGS_UNALLOCATED;
3636 regs->num_regs = 0;
3637 regs->start = regs->end = (regoff_t *) 0;
3638 }
3639 }
3640 \f
3641 /* Searching routines. */
3642
3643 /* Like re_search_2, below, but only one string is specified, and
3644 doesn't let you say where to stop matching. */
3645
3646 int
3647 re_search (bufp, string, size, startpos, range, regs)
3648 struct re_pattern_buffer *bufp;
3649 const char *string;
3650 int size, startpos, range;
3651 struct re_registers *regs;
3652 {
3653 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
3654 regs, size);
3655 }
3656
3657 /* End address of virtual concatenation of string. */
3658 #define STOP_ADDR_VSTRING(P) \
3659 (((P) >= size1 ? string2 + size2 : string1 + size1))
3660
3661 /* Address of POS in the concatenation of virtual string. */
3662 #define POS_ADDR_VSTRING(POS) \
3663 (((POS) >= size1 ? string2 - size1 : string1) + (POS))
3664
3665 /* Using the compiled pattern in BUFP->buffer, first tries to match the
3666 virtual concatenation of STRING1 and STRING2, starting first at index
3667 STARTPOS, then at STARTPOS + 1, and so on.
3668
3669 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
3670
3671 RANGE is how far to scan while trying to match. RANGE = 0 means try
3672 only at STARTPOS; in general, the last start tried is STARTPOS +
3673 RANGE.
3674
3675 In REGS, return the indices of the virtual concatenation of STRING1
3676 and STRING2 that matched the entire BUFP->buffer and its contained
3677 subexpressions.
3678
3679 Do not consider matching one past the index STOP in the virtual
3680 concatenation of STRING1 and STRING2.
3681
3682 We return either the position in the strings at which the match was
3683 found, -1 if no match, or -2 if error (such as failure
3684 stack overflow). */
3685
3686 int
3687 re_search_2 (bufp, str1, size1, str2, size2, startpos, range, regs, stop)
3688 struct re_pattern_buffer *bufp;
3689 const char *str1, *str2;
3690 int size1, size2;
3691 int startpos;
3692 int range;
3693 struct re_registers *regs;
3694 int stop;
3695 {
3696 int val;
3697 re_char *string1 = (re_char*) str1;
3698 re_char *string2 = (re_char*) str2;
3699 register char *fastmap = bufp->fastmap;
3700 register RE_TRANSLATE_TYPE translate = bufp->translate;
3701 int total_size = size1 + size2;
3702 int endpos = startpos + range;
3703 int anchored_start = 0;
3704
3705 /* Nonzero if we have to concern multibyte character. */
3706 const boolean multibyte = RE_MULTIBYTE_P (bufp);
3707
3708 /* Check for out-of-range STARTPOS. */
3709 if (startpos < 0 || startpos > total_size)
3710 return -1;
3711
3712 /* Fix up RANGE if it might eventually take us outside
3713 the virtual concatenation of STRING1 and STRING2.
3714 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
3715 if (endpos < 0)
3716 range = 0 - startpos;
3717 else if (endpos > total_size)
3718 range = total_size - startpos;
3719
3720 /* If the search isn't to be a backwards one, don't waste time in a
3721 search for a pattern anchored at beginning of buffer. */
3722 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
3723 {
3724 if (startpos > 0)
3725 return -1;
3726 else
3727 range = 0;
3728 }
3729
3730 #ifdef emacs
3731 /* In a forward search for something that starts with \=.
3732 don't keep searching past point. */
3733 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
3734 {
3735 range = PT_BYTE - BEGV_BYTE - startpos;
3736 if (range < 0)
3737 return -1;
3738 }
3739 #endif /* emacs */
3740
3741 /* Update the fastmap now if not correct already. */
3742 if (fastmap && !bufp->fastmap_accurate)
3743 if (re_compile_fastmap (bufp) == -2)
3744 return -2;
3745
3746 /* See whether the pattern is anchored. */
3747 if (bufp->buffer[0] == begline)
3748 anchored_start = 1;
3749
3750 #ifdef emacs
3751 gl_state.object = re_match_object;
3752 {
3753 int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (startpos));
3754
3755 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
3756 }
3757 #endif
3758
3759 /* Loop through the string, looking for a place to start matching. */
3760 for (;;)
3761 {
3762 /* If the pattern is anchored,
3763 skip quickly past places we cannot match.
3764 We don't bother to treat startpos == 0 specially
3765 because that case doesn't repeat. */
3766 if (anchored_start && startpos > 0)
3767 {
3768 if (! (bufp->newline_anchor
3769 && ((startpos <= size1 ? string1[startpos - 1]
3770 : string2[startpos - size1 - 1])
3771 == '\n')))
3772 goto advance;
3773 }
3774
3775 /* If a fastmap is supplied, skip quickly over characters that
3776 cannot be the start of a match. If the pattern can match the
3777 null string, however, we don't need to skip characters; we want
3778 the first null string. */
3779 if (fastmap && startpos < total_size && !bufp->can_be_null)
3780 {
3781 register re_char *d;
3782 register unsigned int buf_ch;
3783
3784 d = POS_ADDR_VSTRING (startpos);
3785
3786 if (range > 0) /* Searching forwards. */
3787 {
3788 register int lim = 0;
3789 int irange = range;
3790
3791 if (startpos < size1 && startpos + range >= size1)
3792 lim = range - (size1 - startpos);
3793
3794 /* Written out as an if-else to avoid testing `translate'
3795 inside the loop. */
3796 if (RE_TRANSLATE_P (translate))
3797 {
3798 if (multibyte)
3799 while (range > lim)
3800 {
3801 int buf_charlen;
3802
3803 buf_ch = STRING_CHAR_AND_LENGTH (d, range - lim,
3804 buf_charlen);
3805
3806 buf_ch = RE_TRANSLATE (translate, buf_ch);
3807 if (buf_ch >= 0400
3808 || fastmap[buf_ch])
3809 break;
3810
3811 range -= buf_charlen;
3812 d += buf_charlen;
3813 }
3814 else
3815 while (range > lim
3816 && !fastmap[RE_TRANSLATE (translate, *d)])
3817 {
3818 d++;
3819 range--;
3820 }
3821 }
3822 else
3823 while (range > lim && !fastmap[*d])
3824 {
3825 d++;
3826 range--;
3827 }
3828
3829 startpos += irange - range;
3830 }
3831 else /* Searching backwards. */
3832 {
3833 int room = (startpos >= size1
3834 ? size2 + size1 - startpos
3835 : size1 - startpos);
3836 buf_ch = RE_STRING_CHAR (d, room);
3837 buf_ch = TRANSLATE (buf_ch);
3838
3839 if (! (buf_ch >= 0400
3840 || fastmap[buf_ch]))
3841 goto advance;
3842 }
3843 }
3844
3845 /* If can't match the null string, and that's all we have left, fail. */
3846 if (range >= 0 && startpos == total_size && fastmap
3847 && !bufp->can_be_null)
3848 return -1;
3849
3850 val = re_match_2_internal (bufp, string1, size1, string2, size2,
3851 startpos, regs, stop);
3852 #ifndef REGEX_MALLOC
3853 #ifdef C_ALLOCA
3854 alloca (0);
3855 #endif
3856 #endif
3857
3858 if (val >= 0)
3859 return startpos;
3860
3861 if (val == -2)
3862 return -2;
3863
3864 advance:
3865 if (!range)
3866 break;
3867 else if (range > 0)
3868 {
3869 /* Update STARTPOS to the next character boundary. */
3870 if (multibyte)
3871 {
3872 re_char *p = POS_ADDR_VSTRING (startpos);
3873 re_char *pend = STOP_ADDR_VSTRING (startpos);
3874 int len = MULTIBYTE_FORM_LENGTH (p, pend - p);
3875
3876 range -= len;
3877 if (range < 0)
3878 break;
3879 startpos += len;
3880 }
3881 else
3882 {
3883 range--;
3884 startpos++;
3885 }
3886 }
3887 else
3888 {
3889 range++;
3890 startpos--;
3891
3892 /* Update STARTPOS to the previous character boundary. */
3893 if (multibyte)
3894 {
3895 re_char *p = POS_ADDR_VSTRING (startpos);
3896 int len = 0;
3897
3898 /* Find the head of multibyte form. */
3899 while (!CHAR_HEAD_P (*p))
3900 p--, len++;
3901
3902 /* Adjust it. */
3903 #if 0 /* XXX */
3904 if (MULTIBYTE_FORM_LENGTH (p, len + 1) != (len + 1))
3905 ;
3906 else
3907 #endif
3908 {
3909 range += len;
3910 if (range > 0)
3911 break;
3912
3913 startpos -= len;
3914 }
3915 }
3916 }
3917 }
3918 return -1;
3919 } /* re_search_2 */
3920 \f
3921 /* Declarations and macros for re_match_2. */
3922
3923 static int bcmp_translate _RE_ARGS((re_char *s1, re_char *s2,
3924 register int len,
3925 RE_TRANSLATE_TYPE translate,
3926 const int multibyte));
3927
3928 /* This converts PTR, a pointer into one of the search strings `string1'
3929 and `string2' into an offset from the beginning of that string. */
3930 #define POINTER_TO_OFFSET(ptr) \
3931 (FIRST_STRING_P (ptr) \
3932 ? ((regoff_t) ((ptr) - string1)) \
3933 : ((regoff_t) ((ptr) - string2 + size1)))
3934
3935 /* Call before fetching a character with *d. This switches over to
3936 string2 if necessary.
3937 Check re_match_2_internal for a discussion of why end_match_2 might
3938 not be within string2 (but be equal to end_match_1 instead). */
3939 #define PREFETCH() \
3940 while (d == dend) \
3941 { \
3942 /* End of string2 => fail. */ \
3943 if (dend == end_match_2) \
3944 goto fail; \
3945 /* End of string1 => advance to string2. */ \
3946 d = string2; \
3947 dend = end_match_2; \
3948 }
3949
3950
3951 /* Test if at very beginning or at very end of the virtual concatenation
3952 of `string1' and `string2'. If only one string, it's `string2'. */
3953 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
3954 #define AT_STRINGS_END(d) ((d) == end2)
3955
3956
3957 /* Test if D points to a character which is word-constituent. We have
3958 two special cases to check for: if past the end of string1, look at
3959 the first character in string2; and if before the beginning of
3960 string2, look at the last character in string1. */
3961 #define WORDCHAR_P(d) \
3962 (SYNTAX ((d) == end1 ? *string2 \
3963 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
3964 == Sword)
3965
3966 /* Disabled due to a compiler bug -- see comment at case wordbound */
3967
3968 /* The comment at case wordbound is following one, but we don't use
3969 AT_WORD_BOUNDARY anymore to support multibyte form.
3970
3971 The DEC Alpha C compiler 3.x generates incorrect code for the
3972 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
3973 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
3974 macro and introducing temporary variables works around the bug. */
3975
3976 #if 0
3977 /* Test if the character before D and the one at D differ with respect
3978 to being word-constituent. */
3979 #define AT_WORD_BOUNDARY(d) \
3980 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
3981 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
3982 #endif
3983
3984 /* Free everything we malloc. */
3985 #ifdef MATCH_MAY_ALLOCATE
3986 #define FREE_VAR(var) if (var) { REGEX_FREE (var); var = NULL; } else
3987 #define FREE_VARIABLES() \
3988 do { \
3989 REGEX_FREE_STACK (fail_stack.stack); \
3990 FREE_VAR (regstart); \
3991 FREE_VAR (regend); \
3992 FREE_VAR (best_regstart); \
3993 FREE_VAR (best_regend); \
3994 } while (0)
3995 #else
3996 #define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
3997 #endif /* not MATCH_MAY_ALLOCATE */
3998
3999 \f
4000 /* Optimization routines. */
4001
4002 /* If the operation is a match against one or more chars,
4003 return a pointer to the next operation, else return NULL. */
4004 static unsigned char *
4005 skip_one_char (p)
4006 unsigned char *p;
4007 {
4008 switch (SWITCH_ENUM_CAST (*p++))
4009 {
4010 case anychar:
4011 break;
4012
4013 case exactn:
4014 p += *p + 1;
4015 break;
4016
4017 case charset_not:
4018 case charset:
4019 if (CHARSET_RANGE_TABLE_EXISTS_P (p - 1))
4020 {
4021 int mcnt;
4022 p = CHARSET_RANGE_TABLE (p - 1);
4023 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4024 p = CHARSET_RANGE_TABLE_END (p, mcnt);
4025 }
4026 else
4027 p += 1 + CHARSET_BITMAP_SIZE (p - 1);
4028 break;
4029
4030 case syntaxspec:
4031 case notsyntaxspec:
4032 #ifdef emacs
4033 case categoryspec:
4034 case notcategoryspec:
4035 #endif /* emacs */
4036 p++;
4037 break;
4038
4039 default:
4040 p = NULL;
4041 }
4042 return p;
4043 }
4044
4045
4046 /* Jump over non-matching operations. */
4047 static unsigned char *
4048 skip_noops (p, pend)
4049 unsigned char *p, *pend;
4050 {
4051 int mcnt;
4052 while (p < pend)
4053 {
4054 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
4055 {
4056 case start_memory:
4057 case stop_memory:
4058 p += 2; break;
4059 case no_op:
4060 p += 1; break;
4061 case jump:
4062 p += 1;
4063 EXTRACT_NUMBER_AND_INCR (mcnt, p);
4064 p += mcnt;
4065 break;
4066 default:
4067 return p;
4068 }
4069 }
4070 assert (p == pend);
4071 return p;
4072 }
4073
4074 /* Non-zero if "p1 matches something" implies "p2 fails". */
4075 static int
4076 mutually_exclusive_p (bufp, p1, p2)
4077 struct re_pattern_buffer *bufp;
4078 unsigned char *p1, *p2;
4079 {
4080 re_opcode_t op2;
4081 const boolean multibyte = RE_MULTIBYTE_P (bufp);
4082 unsigned char *pend = bufp->buffer + bufp->used;
4083
4084 assert (p1 >= bufp->buffer && p1 < pend
4085 && p2 >= bufp->buffer && p2 <= pend);
4086
4087 /* Skip over open/close-group commands.
4088 If what follows this loop is a ...+ construct,
4089 look at what begins its body, since we will have to
4090 match at least one of that. */
4091 p2 = skip_noops (p2, pend);
4092 /* The same skip can be done for p1, except that this function
4093 is only used in the case where p1 is a simple match operator. */
4094 /* p1 = skip_noops (p1, pend); */
4095
4096 assert (p1 >= bufp->buffer && p1 < pend
4097 && p2 >= bufp->buffer && p2 <= pend);
4098
4099 op2 = p2 == pend ? succeed : *p2;
4100
4101 switch (SWITCH_ENUM_CAST (op2))
4102 {
4103 case succeed:
4104 case endbuf:
4105 /* If we're at the end of the pattern, we can change. */
4106 if (skip_one_char (p1))
4107 {
4108 DEBUG_PRINT1 (" End of pattern: fast loop.\n");
4109 return 1;
4110 }
4111 break;
4112
4113 case endline:
4114 if (!bufp->newline_anchor)
4115 break;
4116 /* Fallthrough */
4117 case exactn:
4118 {
4119 register unsigned int c
4120 = (re_opcode_t) *p2 == endline ? '\n'
4121 : RE_STRING_CHAR(p2 + 2, pend - p2 - 2);
4122
4123 if ((re_opcode_t) *p1 == exactn)
4124 {
4125 if (c != RE_STRING_CHAR (p1 + 2, pend - p1 - 2))
4126 {
4127 DEBUG_PRINT3 (" '%c' != '%c' => fast loop.\n", c, p1[2]);
4128 return 1;
4129 }
4130 }
4131
4132 else if ((re_opcode_t) *p1 == charset
4133 || (re_opcode_t) *p1 == charset_not)
4134 {
4135 int not = (re_opcode_t) *p1 == charset_not;
4136
4137 /* Test if C is listed in charset (or charset_not)
4138 at `p1'. */
4139 if (SINGLE_BYTE_CHAR_P (c))
4140 {
4141 if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
4142 && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
4143 not = !not;
4144 }
4145 else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
4146 CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
4147
4148 /* `not' is equal to 1 if c would match, which means
4149 that we can't change to pop_failure_jump. */
4150 if (!not)
4151 {
4152 DEBUG_PRINT1 (" No match => fast loop.\n");
4153 return 1;
4154 }
4155 }
4156 else if ((re_opcode_t) *p1 == anychar
4157 && c == '\n')
4158 {
4159 DEBUG_PRINT1 (" . != \\n => fast loop.\n");
4160 return 1;
4161 }
4162 }
4163 break;
4164
4165 case charset:
4166 case charset_not:
4167 {
4168 if ((re_opcode_t) *p1 == exactn)
4169 /* Reuse the code above. */
4170 return mutually_exclusive_p (bufp, p2, p1);
4171
4172
4173 /* It is hard to list up all the character in charset
4174 P2 if it includes multibyte character. Give up in
4175 such case. */
4176 else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2))
4177 {
4178 /* Now, we are sure that P2 has no range table.
4179 So, for the size of bitmap in P2, `p2[1]' is
4180 enough. But P1 may have range table, so the
4181 size of bitmap table of P1 is extracted by
4182 using macro `CHARSET_BITMAP_SIZE'.
4183
4184 Since we know that all the character listed in
4185 P2 is ASCII, it is enough to test only bitmap
4186 table of P1. */
4187
4188 if (*p1 == *p2)
4189 {
4190 int idx;
4191 /* We win if the charset inside the loop
4192 has no overlap with the one after the loop. */
4193 for (idx = 0;
4194 (idx < (int) p2[1]
4195 && idx < CHARSET_BITMAP_SIZE (p1));
4196 idx++)
4197 if ((p2[2 + idx] & p1[2 + idx]) != 0)
4198 break;
4199
4200 if (idx == p2[1]
4201 || idx == CHARSET_BITMAP_SIZE (p1))
4202 {
4203 DEBUG_PRINT1 (" No match => fast loop.\n");
4204 return 1;
4205 }
4206 }
4207 else if ((re_opcode_t) *p1 == charset
4208 || (re_opcode_t) *p1 == charset_not)
4209 {
4210 int idx;
4211 /* We win if the charset_not inside the loop lists
4212 every character listed in the charset after. */
4213 for (idx = 0; idx < (int) p2[1]; idx++)
4214 if (! (p2[2 + idx] == 0
4215 || (idx < CHARSET_BITMAP_SIZE (p1)
4216 && ((p2[2 + idx] & ~ p1[2 + idx]) == 0))))
4217 break;
4218
4219 if (idx == p2[1])
4220 {
4221 DEBUG_PRINT1 (" No match => fast loop.\n");
4222 return 1;
4223 }
4224 }
4225 }
4226 }
4227
4228 case wordend:
4229 case notsyntaxspec:
4230 return ((re_opcode_t) *p1 == syntaxspec
4231 && p1[1] == (op2 == wordend ? Sword : p2[1]));
4232
4233 case wordbeg:
4234 case syntaxspec:
4235 return ((re_opcode_t) *p1 == notsyntaxspec
4236 && p1[1] == (op2 == wordend ? Sword : p2[1]));
4237
4238 case wordbound:
4239 return (((re_opcode_t) *p1 == notsyntaxspec
4240 || (re_opcode_t) *p1 == syntaxspec)
4241 && p1[1] == Sword);
4242
4243 #ifdef emacs
4244 case categoryspec:
4245 return ((re_opcode_t) *p1 == notcategoryspec && p1[1] == p2[1]);
4246 case notcategoryspec:
4247 return ((re_opcode_t) *p1 == categoryspec && p1[1] == p2[1]);
4248 #endif /* emacs */
4249
4250 default:
4251 ;
4252 }
4253
4254 /* Safe default. */
4255 return 0;
4256 }
4257
4258 \f
4259 /* Matching routines. */
4260
4261 #ifndef emacs /* Emacs never uses this. */
4262 /* re_match is like re_match_2 except it takes only a single string. */
4263
4264 int
4265 re_match (bufp, string, size, pos, regs)
4266 struct re_pattern_buffer *bufp;
4267 const char *string;
4268 int size, pos;
4269 struct re_registers *regs;
4270 {
4271 int result = re_match_2_internal (bufp, NULL, 0, string, size,
4272 pos, regs, size);
4273 alloca (0);
4274 return result;
4275 }
4276 #endif /* not emacs */
4277
4278 #ifdef emacs
4279 /* In Emacs, this is the string or buffer in which we
4280 are matching. It is used for looking up syntax properties. */
4281 Lisp_Object re_match_object;
4282 #endif
4283
4284 /* re_match_2 matches the compiled pattern in BUFP against the
4285 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
4286 and SIZE2, respectively). We start matching at POS, and stop
4287 matching at STOP.
4288
4289 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
4290 store offsets for the substring each group matched in REGS. See the
4291 documentation for exactly how many groups we fill.
4292
4293 We return -1 if no match, -2 if an internal error (such as the
4294 failure stack overflowing). Otherwise, we return the length of the
4295 matched substring. */
4296
4297 int
4298 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
4299 struct re_pattern_buffer *bufp;
4300 const char *string1, *string2;
4301 int size1, size2;
4302 int pos;
4303 struct re_registers *regs;
4304 int stop;
4305 {
4306 int result;
4307
4308 #ifdef emacs
4309 int charpos;
4310 gl_state.object = re_match_object;
4311 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (POS_AS_IN_BUFFER (pos));
4312 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1);
4313 #endif
4314
4315 result = re_match_2_internal (bufp, string1, size1, string2, size2,
4316 pos, regs, stop);
4317 alloca (0);
4318 return result;
4319 }
4320
4321 /* This is a separate function so that we can force an alloca cleanup
4322 afterwards. */
4323 static int
4324 re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
4325 struct re_pattern_buffer *bufp;
4326 re_char *string1, *string2;
4327 int size1, size2;
4328 int pos;
4329 struct re_registers *regs;
4330 int stop;
4331 {
4332 /* General temporaries. */
4333 int mcnt;
4334 boolean not;
4335 unsigned char *p1;
4336
4337 /* Just past the end of the corresponding string. */
4338 re_char *end1, *end2;
4339
4340 /* Pointers into string1 and string2, just past the last characters in
4341 each to consider matching. */
4342 re_char *end_match_1, *end_match_2;
4343
4344 /* Where we are in the data, and the end of the current string. */
4345 re_char *d, *dend;
4346
4347 /* Used sometimes to remember where we were before starting matching
4348 an operator so that we can go back in case of failure. This "atomic"
4349 behavior of matching opcodes is indispensable to the correctness
4350 of the on_failure_keep_string_jump optimization. */
4351 re_char *dfail;
4352
4353 /* Where we are in the pattern, and the end of the pattern. */
4354 unsigned char *p = bufp->buffer;
4355 register unsigned char *pend = p + bufp->used;
4356
4357 /* We use this to map every character in the string. */
4358 RE_TRANSLATE_TYPE translate = bufp->translate;
4359
4360 /* Nonzero if we have to concern multibyte character. */
4361 const boolean multibyte = RE_MULTIBYTE_P (bufp);
4362
4363 /* Failure point stack. Each place that can handle a failure further
4364 down the line pushes a failure point on this stack. It consists of
4365 regstart, and regend for all registers corresponding to
4366 the subexpressions we're currently inside, plus the number of such
4367 registers, and, finally, two char *'s. The first char * is where
4368 to resume scanning the pattern; the second one is where to resume
4369 scanning the strings. */
4370 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
4371 fail_stack_type fail_stack;
4372 #endif
4373 #ifdef DEBUG
4374 static unsigned failure_id = 0;
4375 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
4376 #endif
4377
4378 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
4379 /* This holds the pointer to the failure stack, when
4380 it is allocated relocatably. */
4381 fail_stack_elt_t *failure_stack_ptr;
4382 #endif
4383
4384 /* We fill all the registers internally, independent of what we
4385 return, for use in backreferences. The number here includes
4386 an element for register zero. */
4387 unsigned num_regs = bufp->re_nsub + 1;
4388
4389 /* Information on the contents of registers. These are pointers into
4390 the input strings; they record just what was matched (on this
4391 attempt) by a subexpression part of the pattern, that is, the
4392 regnum-th regstart pointer points to where in the pattern we began
4393 matching and the regnum-th regend points to right after where we
4394 stopped matching the regnum-th subexpression. (The zeroth register
4395 keeps track of what the whole pattern matches.) */
4396 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
4397 re_char **regstart, **regend;
4398 #endif
4399
4400 /* The following record the register info as found in the above
4401 variables when we find a match better than any we've seen before.
4402 This happens as we backtrack through the failure points, which in
4403 turn happens only if we have not yet matched the entire string. */
4404 unsigned best_regs_set = false;
4405 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
4406 re_char **best_regstart, **best_regend;
4407 #endif
4408
4409 /* Logically, this is `best_regend[0]'. But we don't want to have to
4410 allocate space for that if we're not allocating space for anything
4411 else (see below). Also, we never need info about register 0 for
4412 any of the other register vectors, and it seems rather a kludge to
4413 treat `best_regend' differently than the rest. So we keep track of
4414 the end of the best match so far in a separate variable. We
4415 initialize this to NULL so that when we backtrack the first time
4416 and need to test it, it's not garbage. */
4417 re_char *match_end = NULL;
4418
4419 #ifdef DEBUG
4420 /* Counts the total number of registers pushed. */
4421 unsigned num_regs_pushed = 0;
4422 #endif
4423
4424 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
4425
4426 INIT_FAIL_STACK ();
4427
4428 #ifdef MATCH_MAY_ALLOCATE
4429 /* Do not bother to initialize all the register variables if there are
4430 no groups in the pattern, as it takes a fair amount of time. If
4431 there are groups, we include space for register 0 (the whole
4432 pattern), even though we never use it, since it simplifies the
4433 array indexing. We should fix this. */
4434 if (bufp->re_nsub)
4435 {
4436 regstart = REGEX_TALLOC (num_regs, re_char *);
4437 regend = REGEX_TALLOC (num_regs, re_char *);
4438 best_regstart = REGEX_TALLOC (num_regs, re_char *);
4439 best_regend = REGEX_TALLOC (num_regs, re_char *);
4440
4441 if (!(regstart && regend && best_regstart && best_regend))
4442 {
4443 FREE_VARIABLES ();
4444 return -2;
4445 }
4446 }
4447 else
4448 {
4449 /* We must initialize all our variables to NULL, so that
4450 `FREE_VARIABLES' doesn't try to free them. */
4451 regstart = regend = best_regstart = best_regend = NULL;
4452 }
4453 #endif /* MATCH_MAY_ALLOCATE */
4454
4455 /* The starting position is bogus. */
4456 if (pos < 0 || pos > size1 + size2)
4457 {
4458 FREE_VARIABLES ();
4459 return -1;
4460 }
4461
4462 /* Initialize subexpression text positions to -1 to mark ones that no
4463 start_memory/stop_memory has been seen for. Also initialize the
4464 register information struct. */
4465 for (mcnt = 1; mcnt < num_regs; mcnt++)
4466 regstart[mcnt] = regend[mcnt] = REG_UNSET_VALUE;
4467
4468 /* We move `string1' into `string2' if the latter's empty -- but not if
4469 `string1' is null. */
4470 if (size2 == 0 && string1 != NULL)
4471 {
4472 string2 = string1;
4473 size2 = size1;
4474 string1 = 0;
4475 size1 = 0;
4476 }
4477 end1 = string1 + size1;
4478 end2 = string2 + size2;
4479
4480 /* `p' scans through the pattern as `d' scans through the data.
4481 `dend' is the end of the input string that `d' points within. `d'
4482 is advanced into the following input string whenever necessary, but
4483 this happens before fetching; therefore, at the beginning of the
4484 loop, `d' can be pointing at the end of a string, but it cannot
4485 equal `string2'. */
4486 if (pos >= size1)
4487 {
4488 /* Only match within string2. */
4489 d = string2 + pos - size1;
4490 dend = end_match_2 = string2 + stop - size1;
4491 end_match_1 = end1; /* Just to give it a value. */
4492 }
4493 else
4494 {
4495 if (stop <= size1)
4496 {
4497 /* Only match within string1. */
4498 end_match_1 = string1 + stop;
4499 /* BEWARE!
4500 When we reach end_match_1, PREFETCH normally switches to string2.
4501 But in the present case, this means that just doing a PREFETCH
4502 makes us jump from `stop' to `gap' within the string.
4503 What we really want here is for the search to stop as
4504 soon as we hit end_match_1. That's why we set end_match_2
4505 to end_match_1 (since PREFETCH fails as soon as we hit
4506 end_match_2). */
4507 end_match_2 = end_match_1;
4508 }
4509 else
4510 {
4511 end_match_1 = end1;
4512 end_match_2 = string2 + stop - size1;
4513 }
4514 d = string1 + pos;
4515 dend = end_match_1;
4516 }
4517
4518 DEBUG_PRINT1 ("The compiled pattern is: ");
4519 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
4520 DEBUG_PRINT1 ("The string to match is: `");
4521 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
4522 DEBUG_PRINT1 ("'\n");
4523
4524 /* This loops over pattern commands. It exits by returning from the
4525 function if the match is complete, or it drops through if the match
4526 fails at this starting point in the input data. */
4527 for (;;)
4528 {
4529 DEBUG_PRINT2 ("\n%p: ", p);
4530
4531 if (p == pend)
4532 { /* End of pattern means we might have succeeded. */
4533 DEBUG_PRINT1 ("end of pattern ... ");
4534
4535 /* If we haven't matched the entire string, and we want the
4536 longest match, try backtracking. */
4537 if (d != end_match_2)
4538 {
4539 /* 1 if this match ends in the same string (string1 or string2)
4540 as the best previous match. */
4541 boolean same_str_p = (FIRST_STRING_P (match_end)
4542 == FIRST_STRING_P (d));
4543 /* 1 if this match is the best seen so far. */
4544 boolean best_match_p;
4545
4546 /* AIX compiler got confused when this was combined
4547 with the previous declaration. */
4548 if (same_str_p)
4549 best_match_p = d > match_end;
4550 else
4551 best_match_p = !FIRST_STRING_P (d);
4552
4553 DEBUG_PRINT1 ("backtracking.\n");
4554
4555 if (!FAIL_STACK_EMPTY ())
4556 { /* More failure points to try. */
4557
4558 /* If exceeds best match so far, save it. */
4559 if (!best_regs_set || best_match_p)
4560 {
4561 best_regs_set = true;
4562 match_end = d;
4563
4564 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
4565
4566 for (mcnt = 1; mcnt < num_regs; mcnt++)
4567 {
4568 best_regstart[mcnt] = regstart[mcnt];
4569 best_regend[mcnt] = regend[mcnt];
4570 }
4571 }
4572 goto fail;
4573 }
4574
4575 /* If no failure points, don't restore garbage. And if
4576 last match is real best match, don't restore second
4577 best one. */
4578 else if (best_regs_set && !best_match_p)
4579 {
4580 restore_best_regs:
4581 /* Restore best match. It may happen that `dend ==
4582 end_match_1' while the restored d is in string2.
4583 For example, the pattern `x.*y.*z' against the
4584 strings `x-' and `y-z-', if the two strings are
4585 not consecutive in memory. */
4586 DEBUG_PRINT1 ("Restoring best registers.\n");
4587
4588 d = match_end;
4589 dend = ((d >= string1 && d <= end1)
4590 ? end_match_1 : end_match_2);
4591
4592 for (mcnt = 1; mcnt < num_regs; mcnt++)
4593 {
4594 regstart[mcnt] = best_regstart[mcnt];
4595 regend[mcnt] = best_regend[mcnt];
4596 }
4597 }
4598 } /* d != end_match_2 */
4599
4600 succeed_label:
4601 DEBUG_PRINT1 ("Accepting match.\n");
4602
4603 /* If caller wants register contents data back, do it. */
4604 if (regs && !bufp->no_sub)
4605 {
4606 /* Have the register data arrays been allocated? */
4607 if (bufp->regs_allocated == REGS_UNALLOCATED)
4608 { /* No. So allocate them with malloc. We need one
4609 extra element beyond `num_regs' for the `-1' marker
4610 GNU code uses. */
4611 regs->num_regs = MAX (RE_NREGS, num_regs + 1);
4612 regs->start = TALLOC (regs->num_regs, regoff_t);
4613 regs->end = TALLOC (regs->num_regs, regoff_t);
4614 if (regs->start == NULL || regs->end == NULL)
4615 {
4616 FREE_VARIABLES ();
4617 return -2;
4618 }
4619 bufp->regs_allocated = REGS_REALLOCATE;
4620 }
4621 else if (bufp->regs_allocated == REGS_REALLOCATE)
4622 { /* Yes. If we need more elements than were already
4623 allocated, reallocate them. If we need fewer, just
4624 leave it alone. */
4625 if (regs->num_regs < num_regs + 1)
4626 {
4627 regs->num_regs = num_regs + 1;
4628 RETALLOC (regs->start, regs->num_regs, regoff_t);
4629 RETALLOC (regs->end, regs->num_regs, regoff_t);
4630 if (regs->start == NULL || regs->end == NULL)
4631 {
4632 FREE_VARIABLES ();
4633 return -2;
4634 }
4635 }
4636 }
4637 else
4638 {
4639 /* These braces fend off a "empty body in an else-statement"
4640 warning under GCC when assert expands to nothing. */
4641 assert (bufp->regs_allocated == REGS_FIXED);
4642 }
4643
4644 /* Convert the pointer data in `regstart' and `regend' to
4645 indices. Register zero has to be set differently,
4646 since we haven't kept track of any info for it. */
4647 if (regs->num_regs > 0)
4648 {
4649 regs->start[0] = pos;
4650 regs->end[0] = POINTER_TO_OFFSET (d);
4651 }
4652
4653 /* Go through the first `min (num_regs, regs->num_regs)'
4654 registers, since that is all we initialized. */
4655 for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++)
4656 {
4657 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
4658 regs->start[mcnt] = regs->end[mcnt] = -1;
4659 else
4660 {
4661 regs->start[mcnt]
4662 = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
4663 regs->end[mcnt]
4664 = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
4665 }
4666 }
4667
4668 /* If the regs structure we return has more elements than
4669 were in the pattern, set the extra elements to -1. If
4670 we (re)allocated the registers, this is the case,
4671 because we always allocate enough to have at least one
4672 -1 at the end. */
4673 for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
4674 regs->start[mcnt] = regs->end[mcnt] = -1;
4675 } /* regs && !bufp->no_sub */
4676
4677 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
4678 nfailure_points_pushed, nfailure_points_popped,
4679 nfailure_points_pushed - nfailure_points_popped);
4680 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
4681
4682 mcnt = POINTER_TO_OFFSET (d) - pos;
4683
4684 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
4685
4686 FREE_VARIABLES ();
4687 return mcnt;
4688 }
4689
4690 /* Otherwise match next pattern command. */
4691 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
4692 {
4693 /* Ignore these. Used to ignore the n of succeed_n's which
4694 currently have n == 0. */
4695 case no_op:
4696 DEBUG_PRINT1 ("EXECUTING no_op.\n");
4697 break;
4698
4699 case succeed:
4700 DEBUG_PRINT1 ("EXECUTING succeed.\n");
4701 goto succeed_label;
4702
4703 /* Match the next n pattern characters exactly. The following
4704 byte in the pattern defines n, and the n bytes after that
4705 are the characters to match. */
4706 case exactn:
4707 mcnt = *p++;
4708 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
4709
4710 /* Remember the start point to rollback upon failure. */
4711 dfail = d;
4712
4713 /* This is written out as an if-else so we don't waste time
4714 testing `translate' inside the loop. */
4715 if (RE_TRANSLATE_P (translate))
4716 {
4717 if (multibyte)
4718 do
4719 {
4720 int pat_charlen, buf_charlen;
4721 unsigned int pat_ch, buf_ch;
4722
4723 PREFETCH ();
4724 pat_ch = STRING_CHAR_AND_LENGTH (p, pend - p, pat_charlen);
4725 buf_ch = STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen);
4726
4727 if (RE_TRANSLATE (translate, buf_ch)
4728 != pat_ch)
4729 {
4730 d = dfail;
4731 goto fail;
4732 }
4733
4734 p += pat_charlen;
4735 d += buf_charlen;
4736 mcnt -= pat_charlen;
4737 }
4738 while (mcnt > 0);
4739 else
4740 do
4741 {
4742 PREFETCH ();
4743 if (RE_TRANSLATE (translate, *d) != *p++)
4744 {
4745 d = dfail;
4746 goto fail;
4747 }
4748 d++;
4749 }
4750 while (--mcnt);
4751 }
4752 else
4753 {
4754 do
4755 {
4756 PREFETCH ();
4757 if (*d++ != *p++)
4758 {
4759 d = dfail;
4760 goto fail;
4761 }
4762 }
4763 while (--mcnt);
4764 }
4765 break;
4766
4767
4768 /* Match any character except possibly a newline or a null. */
4769 case anychar:
4770 {
4771 int buf_charlen;
4772 unsigned int buf_ch;
4773
4774 DEBUG_PRINT1 ("EXECUTING anychar.\n");
4775
4776 PREFETCH ();
4777 buf_ch = RE_STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen);
4778 buf_ch = TRANSLATE (buf_ch);
4779
4780 if ((!(bufp->syntax & RE_DOT_NEWLINE)
4781 && buf_ch == '\n')
4782 || ((bufp->syntax & RE_DOT_NOT_NULL)
4783 && buf_ch == '\000'))
4784 goto fail;
4785
4786 DEBUG_PRINT2 (" Matched `%d'.\n", *d);
4787 d += buf_charlen;
4788 }
4789 break;
4790
4791
4792 case charset:
4793 case charset_not:
4794 {
4795 register unsigned int c;
4796 boolean not = (re_opcode_t) *(p - 1) == charset_not;
4797 int len;
4798
4799 /* Start of actual range_table, or end of bitmap if there is no
4800 range table. */
4801 unsigned char *range_table;
4802
4803 /* Nonzero if there is a range table. */
4804 int range_table_exists;
4805
4806 /* Number of ranges of range table. This is not included
4807 in the initial byte-length of the command. */
4808 int count = 0;
4809
4810 DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
4811
4812 range_table_exists = CHARSET_RANGE_TABLE_EXISTS_P (&p[-1]);
4813
4814 if (range_table_exists)
4815 {
4816 range_table = CHARSET_RANGE_TABLE (&p[-1]); /* Past the bitmap. */
4817 EXTRACT_NUMBER_AND_INCR (count, range_table);
4818 }
4819
4820 PREFETCH ();
4821 c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
4822 c = TRANSLATE (c); /* The character to match. */
4823
4824 if (SINGLE_BYTE_CHAR_P (c))
4825 { /* Lookup bitmap. */
4826 /* Cast to `unsigned' instead of `unsigned char' in
4827 case the bit list is a full 32 bytes long. */
4828 if (c < (unsigned) (CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH)
4829 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
4830 not = !not;
4831 }
4832 #ifdef emacs
4833 else if (range_table_exists)
4834 {
4835 int class_bits = CHARSET_RANGE_TABLE_BITS (&p[-1]);
4836
4837 if ( (class_bits & BIT_ALNUM && ISALNUM (c))
4838 | (class_bits & BIT_ALPHA && ISALPHA (c))
4839 | (class_bits & BIT_ASCII && IS_REAL_ASCII (c))
4840 | (class_bits & BIT_GRAPH && ISGRAPH (c))
4841 | (class_bits & BIT_LOWER && ISLOWER (c))
4842 | (class_bits & BIT_MULTIBYTE && !ISUNIBYTE (c))
4843 | (class_bits & BIT_NONASCII && !IS_REAL_ASCII (c))
4844 | (class_bits & BIT_PRINT && ISPRINT (c))
4845 | (class_bits & BIT_PUNCT && ISPUNCT (c))
4846 | (class_bits & BIT_SPACE && ISSPACE (c))
4847 | (class_bits & BIT_UNIBYTE && ISUNIBYTE (c))
4848 | (class_bits & BIT_UPPER && ISUPPER (c))
4849 | (class_bits & BIT_WORD && ISWORD (c)))
4850 not = !not;
4851 else
4852 CHARSET_LOOKUP_RANGE_TABLE_RAW (not, c, range_table, count);
4853 }
4854 #endif /* emacs */
4855
4856 if (range_table_exists)
4857 p = CHARSET_RANGE_TABLE_END (range_table, count);
4858 else
4859 p += CHARSET_BITMAP_SIZE (&p[-1]) + 1;
4860
4861 if (!not) goto fail;
4862
4863 d += len;
4864 break;
4865 }
4866
4867
4868 /* The beginning of a group is represented by start_memory.
4869 The argument is the register number. The text
4870 matched within the group is recorded (in the internal
4871 registers data structure) under the register number. */
4872 case start_memory:
4873 DEBUG_PRINT2 ("EXECUTING start_memory %d:\n", *p);
4874
4875 /* In case we need to undo this operation (via backtracking). */
4876 PUSH_FAILURE_REG ((unsigned int)*p);
4877
4878 regstart[*p] = d;
4879 regend[*p] = REG_UNSET_VALUE; /* probably unnecessary. -sm */
4880 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
4881
4882 /* Move past the register number and inner group count. */
4883 p += 1;
4884 break;
4885
4886
4887 /* The stop_memory opcode represents the end of a group. Its
4888 argument is the same as start_memory's: the register number. */
4889 case stop_memory:
4890 DEBUG_PRINT2 ("EXECUTING stop_memory %d:\n", *p);
4891
4892 assert (!REG_UNSET (regstart[*p]));
4893 /* Strictly speaking, there should be code such as:
4894
4895 assert (REG_UNSET (regend[*p]));
4896 PUSH_FAILURE_REGSTOP ((unsigned int)*p);
4897
4898 But the only info to be pushed is regend[*p] and it is known to
4899 be UNSET, so there really isn't anything to push.
4900 Not pushing anything, on the other hand deprives us from the
4901 guarantee that regend[*p] is UNSET since undoing this operation
4902 will not reset its value properly. This is not important since
4903 the value will only be read on the next start_memory or at
4904 the very end and both events can only happen if this stop_memory
4905 is *not* undone. */
4906
4907 regend[*p] = d;
4908 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
4909
4910 /* Move past the register number and the inner group count. */
4911 p += 1;
4912 break;
4913
4914
4915 /* \<digit> has been turned into a `duplicate' command which is
4916 followed by the numeric value of <digit> as the register number. */
4917 case duplicate:
4918 {
4919 register re_char *d2, *dend2;
4920 int regno = *p++; /* Get which register to match against. */
4921 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
4922
4923 /* Can't back reference a group which we've never matched. */
4924 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
4925 goto fail;
4926
4927 /* Where in input to try to start matching. */
4928 d2 = regstart[regno];
4929
4930 /* Remember the start point to rollback upon failure. */
4931 dfail = d;
4932
4933 /* Where to stop matching; if both the place to start and
4934 the place to stop matching are in the same string, then
4935 set to the place to stop, otherwise, for now have to use
4936 the end of the first string. */
4937
4938 dend2 = ((FIRST_STRING_P (regstart[regno])
4939 == FIRST_STRING_P (regend[regno]))
4940 ? regend[regno] : end_match_1);
4941 for (;;)
4942 {
4943 /* If necessary, advance to next segment in register
4944 contents. */
4945 while (d2 == dend2)
4946 {
4947 if (dend2 == end_match_2) break;
4948 if (dend2 == regend[regno]) break;
4949
4950 /* End of string1 => advance to string2. */
4951 d2 = string2;
4952 dend2 = regend[regno];
4953 }
4954 /* At end of register contents => success */
4955 if (d2 == dend2) break;
4956
4957 /* If necessary, advance to next segment in data. */
4958 PREFETCH ();
4959
4960 /* How many characters left in this segment to match. */
4961 mcnt = dend - d;
4962
4963 /* Want how many consecutive characters we can match in
4964 one shot, so, if necessary, adjust the count. */
4965 if (mcnt > dend2 - d2)
4966 mcnt = dend2 - d2;
4967
4968 /* Compare that many; failure if mismatch, else move
4969 past them. */
4970 if (RE_TRANSLATE_P (translate)
4971 ? bcmp_translate (d, d2, mcnt, translate, multibyte)
4972 : bcmp (d, d2, mcnt))
4973 {
4974 d = dfail;
4975 goto fail;
4976 }
4977 d += mcnt, d2 += mcnt;
4978 }
4979 }
4980 break;
4981
4982
4983 /* begline matches the empty string at the beginning of the string
4984 (unless `not_bol' is set in `bufp'), and, if
4985 `newline_anchor' is set, after newlines. */
4986 case begline:
4987 DEBUG_PRINT1 ("EXECUTING begline.\n");
4988
4989 if (AT_STRINGS_BEG (d))
4990 {
4991 if (!bufp->not_bol) break;
4992 }
4993 else
4994 {
4995 unsigned char c;
4996 GET_CHAR_BEFORE_2 (c, d, string1, end1, string2, end2);
4997 if (c == '\n' && bufp->newline_anchor)
4998 break;
4999 }
5000 /* In all other cases, we fail. */
5001 goto fail;
5002
5003
5004 /* endline is the dual of begline. */
5005 case endline:
5006 DEBUG_PRINT1 ("EXECUTING endline.\n");
5007
5008 if (AT_STRINGS_END (d))
5009 {
5010 if (!bufp->not_eol) break;
5011 }
5012
5013 /* We have to ``prefetch'' the next character. */
5014 else if ((d == end1 ? *string2 : *d) == '\n'
5015 && bufp->newline_anchor)
5016 {
5017 break;
5018 }
5019 goto fail;
5020
5021
5022 /* Match at the very beginning of the data. */
5023 case begbuf:
5024 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
5025 if (AT_STRINGS_BEG (d))
5026 break;
5027 goto fail;
5028
5029
5030 /* Match at the very end of the data. */
5031 case endbuf:
5032 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
5033 if (AT_STRINGS_END (d))
5034 break;
5035 goto fail;
5036
5037
5038 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
5039 pushes NULL as the value for the string on the stack. Then
5040 `POP_FAILURE_POINT' will keep the current value for the
5041 string, instead of restoring it. To see why, consider
5042 matching `foo\nbar' against `.*\n'. The .* matches the foo;
5043 then the . fails against the \n. But the next thing we want
5044 to do is match the \n against the \n; if we restored the
5045 string value, we would be back at the foo.
5046
5047 Because this is used only in specific cases, we don't need to
5048 check all the things that `on_failure_jump' does, to make
5049 sure the right things get saved on the stack. Hence we don't
5050 share its code. The only reason to push anything on the
5051 stack at all is that otherwise we would have to change
5052 `anychar's code to do something besides goto fail in this
5053 case; that seems worse than this. */
5054 case on_failure_keep_string_jump:
5055 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5056 DEBUG_PRINT3 ("EXECUTING on_failure_keep_string_jump %d (to %p):\n",
5057 mcnt, p + mcnt);
5058
5059 PUSH_FAILURE_POINT (p - 3, NULL);
5060 break;
5061
5062 /* A nasty loop is introduced by the non-greedy *? and +?.
5063 With such loops, the stack only ever contains one failure point
5064 at a time, so that a plain on_failure_jump_loop kind of
5065 cycle detection cannot work. Worse yet, such a detection
5066 can not only fail to detect a cycle, but it can also wrongly
5067 detect a cycle (between different instantiations of the same
5068 loop.
5069 So the method used for those nasty loops is a little different:
5070 We use a special cycle-detection-stack-frame which is pushed
5071 when the on_failure_jump_nastyloop failure-point is *popped*.
5072 This special frame thus marks the beginning of one iteration
5073 through the loop and we can hence easily check right here
5074 whether something matched between the beginning and the end of
5075 the loop. */
5076 case on_failure_jump_nastyloop:
5077 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5078 DEBUG_PRINT3 ("EXECUTING on_failure_jump_nastyloop %d (to %p):\n",
5079 mcnt, p + mcnt);
5080
5081 assert ((re_opcode_t)p[-4] == no_op);
5082 CHECK_INFINITE_LOOP (p - 4, d);
5083 PUSH_FAILURE_POINT (p - 3, d);
5084 break;
5085
5086
5087 /* Simple loop detecting on_failure_jump: just check on the
5088 failure stack if the same spot was already hit earlier. */
5089 case on_failure_jump_loop:
5090 on_failure:
5091 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5092 DEBUG_PRINT3 ("EXECUTING on_failure_jump_loop %d (to %p):\n",
5093 mcnt, p + mcnt);
5094
5095 CHECK_INFINITE_LOOP (p - 3, d);
5096 PUSH_FAILURE_POINT (p - 3, d);
5097 break;
5098
5099
5100 /* Uses of on_failure_jump:
5101
5102 Each alternative starts with an on_failure_jump that points
5103 to the beginning of the next alternative. Each alternative
5104 except the last ends with a jump that in effect jumps past
5105 the rest of the alternatives. (They really jump to the
5106 ending jump of the following alternative, because tensioning
5107 these jumps is a hassle.)
5108
5109 Repeats start with an on_failure_jump that points past both
5110 the repetition text and either the following jump or
5111 pop_failure_jump back to this on_failure_jump. */
5112 case on_failure_jump:
5113 QUIT;
5114 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5115 DEBUG_PRINT3 ("EXECUTING on_failure_jump %d (to %p):\n",
5116 mcnt, p + mcnt);
5117
5118 PUSH_FAILURE_POINT (p -3, d);
5119 break;
5120
5121 /* This operation is used for greedy *.
5122 Compare the beginning of the repeat with what in the
5123 pattern follows its end. If we can establish that there
5124 is nothing that they would both match, i.e., that we
5125 would have to backtrack because of (as in, e.g., `a*a')
5126 then we can use a non-backtracking loop based on
5127 on_failure_keep_string_jump instead of on_failure_jump. */
5128 case on_failure_jump_smart:
5129 QUIT;
5130 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5131 DEBUG_PRINT3 ("EXECUTING on_failure_jump_smart %d (to %p).\n",
5132 mcnt, p + mcnt);
5133 {
5134 unsigned char *p1 = p; /* Next operation. */
5135 unsigned char *p2 = p + mcnt; /* Destination of the jump. */
5136
5137 p -= 3; /* Reset so that we will re-execute the
5138 instruction once it's been changed. */
5139
5140 EXTRACT_NUMBER (mcnt, p2 - 2);
5141
5142 /* Ensure this is a indeed the trivial kind of loop
5143 we are expecting. */
5144 assert (skip_one_char (p1) == p2 - 3);
5145 assert ((re_opcode_t) p2[-3] == jump && p2 + mcnt == p);
5146 DEBUG_STATEMENT (debug += 2);
5147 if (mutually_exclusive_p (bufp, p1, p2))
5148 {
5149 /* Use a fast `on_failure_keep_string_jump' loop. */
5150 DEBUG_PRINT1 (" smart exclusive => fast loop.\n");
5151 *p = (unsigned char) on_failure_keep_string_jump;
5152 STORE_NUMBER (p2 - 2, mcnt + 3);
5153 }
5154 else
5155 {
5156 /* Default to a safe `on_failure_jump' loop. */
5157 DEBUG_PRINT1 (" smart default => slow loop.\n");
5158 *p = (unsigned char) on_failure_jump;
5159 }
5160 DEBUG_STATEMENT (debug -= 2);
5161 }
5162 break;
5163
5164 /* Unconditionally jump (without popping any failure points). */
5165 case jump:
5166 unconditional_jump:
5167 QUIT;
5168 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
5169 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
5170 p += mcnt; /* Do the jump. */
5171 DEBUG_PRINT2 ("(to %p).\n", p);
5172 break;
5173
5174
5175 /* Have to succeed matching what follows at least n times.
5176 After that, handle like `on_failure_jump'. */
5177 case succeed_n:
5178 EXTRACT_NUMBER (mcnt, p + 2);
5179 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
5180
5181 assert (mcnt >= 0);
5182 /* Originally, this is how many times we HAVE to succeed. */
5183 if (mcnt > 0)
5184 {
5185 mcnt--;
5186 p += 2;
5187 STORE_NUMBER_AND_INCR (p, mcnt);
5188 DEBUG_PRINT3 (" Setting %p to %d.\n", p, mcnt);
5189 }
5190 else if (mcnt == 0)
5191 {
5192 DEBUG_PRINT2 (" Setting two bytes from %p to no_op.\n", p+2);
5193 p[2] = (unsigned char) no_op;
5194 p[3] = (unsigned char) no_op;
5195 goto on_failure;
5196 }
5197 break;
5198
5199 case jump_n:
5200 EXTRACT_NUMBER (mcnt, p + 2);
5201 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
5202
5203 /* Originally, this is how many times we CAN jump. */
5204 if (mcnt)
5205 {
5206 mcnt--;
5207 STORE_NUMBER (p + 2, mcnt);
5208 goto unconditional_jump;
5209 }
5210 /* If don't have to jump any more, skip over the rest of command. */
5211 else
5212 p += 4;
5213 break;
5214
5215 case set_number_at:
5216 {
5217 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
5218
5219 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5220 p1 = p + mcnt;
5221 EXTRACT_NUMBER_AND_INCR (mcnt, p);
5222 DEBUG_PRINT3 (" Setting %p to %d.\n", p1, mcnt);
5223 STORE_NUMBER (p1, mcnt);
5224 break;
5225 }
5226
5227 case wordbound:
5228 case notwordbound:
5229 not = (re_opcode_t) *(p - 1) == notwordbound;
5230 DEBUG_PRINT2 ("EXECUTING %swordbound.\n", not?"not":"");
5231
5232 /* We SUCCEED (or FAIL) in one of the following cases: */
5233
5234 /* Case 1: D is at the beginning or the end of string. */
5235 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
5236 not = !not;
5237 else
5238 {
5239 /* C1 is the character before D, S1 is the syntax of C1, C2
5240 is the character at D, and S2 is the syntax of C2. */
5241 int c1, c2, s1, s2;
5242 #ifdef emacs
5243 int offset = PTR_TO_OFFSET (d - 1);
5244 int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5245 UPDATE_SYNTAX_TABLE (charpos);
5246 #endif
5247 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
5248 s1 = SYNTAX (c1);
5249 #ifdef emacs
5250 UPDATE_SYNTAX_TABLE_FORWARD (charpos + 1);
5251 #endif
5252 PREFETCH ();
5253 c2 = RE_STRING_CHAR (d, dend - d);
5254 s2 = SYNTAX (c2);
5255
5256 if (/* Case 2: Only one of S1 and S2 is Sword. */
5257 ((s1 == Sword) != (s2 == Sword))
5258 /* Case 3: Both of S1 and S2 are Sword, and macro
5259 WORD_BOUNDARY_P (C1, C2) returns nonzero. */
5260 || ((s1 == Sword) && WORD_BOUNDARY_P (c1, c2)))
5261 not = !not;
5262 }
5263 if (not)
5264 break;
5265 else
5266 goto fail;
5267
5268 case wordbeg:
5269 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
5270
5271 /* We FAIL in one of the following cases: */
5272
5273 /* Case 1: D is at the end of string. */
5274 if (AT_STRINGS_END (d))
5275 goto fail;
5276 else
5277 {
5278 /* C1 is the character before D, S1 is the syntax of C1, C2
5279 is the character at D, and S2 is the syntax of C2. */
5280 int c1, c2, s1, s2;
5281 #ifdef emacs
5282 int offset = PTR_TO_OFFSET (d);
5283 int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5284 UPDATE_SYNTAX_TABLE (charpos);
5285 #endif
5286 PREFETCH ();
5287 c2 = RE_STRING_CHAR (d, dend - d);
5288 s2 = SYNTAX (c2);
5289
5290 /* Case 2: S2 is not Sword. */
5291 if (s2 != Sword)
5292 goto fail;
5293
5294 /* Case 3: D is not at the beginning of string ... */
5295 if (!AT_STRINGS_BEG (d))
5296 {
5297 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
5298 #ifdef emacs
5299 UPDATE_SYNTAX_TABLE_BACKWARD (charpos - 1);
5300 #endif
5301 s1 = SYNTAX (c1);
5302
5303 /* ... and S1 is Sword, and WORD_BOUNDARY_P (C1, C2)
5304 returns 0. */
5305 if ((s1 == Sword) && !WORD_BOUNDARY_P (c1, c2))
5306 goto fail;
5307 }
5308 }
5309 break;
5310
5311 case wordend:
5312 DEBUG_PRINT1 ("EXECUTING wordend.\n");
5313
5314 /* We FAIL in one of the following cases: */
5315
5316 /* Case 1: D is at the beginning of string. */
5317 if (AT_STRINGS_BEG (d))
5318 goto fail;
5319 else
5320 {
5321 /* C1 is the character before D, S1 is the syntax of C1, C2
5322 is the character at D, and S2 is the syntax of C2. */
5323 int c1, c2, s1, s2;
5324 #ifdef emacs
5325 int offset = PTR_TO_OFFSET (d) - 1;
5326 int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5327 UPDATE_SYNTAX_TABLE (charpos);
5328 #endif
5329 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2);
5330 s1 = SYNTAX (c1);
5331
5332 /* Case 2: S1 is not Sword. */
5333 if (s1 != Sword)
5334 goto fail;
5335
5336 /* Case 3: D is not at the end of string ... */
5337 if (!AT_STRINGS_END (d))
5338 {
5339 PREFETCH ();
5340 c2 = RE_STRING_CHAR (d, dend - d);
5341 #ifdef emacs
5342 UPDATE_SYNTAX_TABLE_FORWARD (charpos);
5343 #endif
5344 s2 = SYNTAX (c2);
5345
5346 /* ... and S2 is Sword, and WORD_BOUNDARY_P (C1, C2)
5347 returns 0. */
5348 if ((s2 == Sword) && !WORD_BOUNDARY_P (c1, c2))
5349 goto fail;
5350 }
5351 }
5352 break;
5353
5354 case syntaxspec:
5355 case notsyntaxspec:
5356 not = (re_opcode_t) *(p - 1) == notsyntaxspec;
5357 mcnt = *p++;
5358 DEBUG_PRINT3 ("EXECUTING %ssyntaxspec %d.\n", not?"not":"", mcnt);
5359 PREFETCH ();
5360 #ifdef emacs
5361 {
5362 int offset = PTR_TO_OFFSET (d);
5363 int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (offset);
5364 UPDATE_SYNTAX_TABLE (pos1);
5365 }
5366 #endif
5367 {
5368 int c, len;
5369
5370 c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
5371
5372 if ((SYNTAX (c) != (enum syntaxcode) mcnt) ^ not)
5373 goto fail;
5374 d += len;
5375 }
5376 break;
5377
5378 #ifdef emacs
5379 case before_dot:
5380 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
5381 if (PTR_BYTE_POS (d) >= PT_BYTE)
5382 goto fail;
5383 break;
5384
5385 case at_dot:
5386 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
5387 if (PTR_BYTE_POS (d) != PT_BYTE)
5388 goto fail;
5389 break;
5390
5391 case after_dot:
5392 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
5393 if (PTR_BYTE_POS (d) <= PT_BYTE)
5394 goto fail;
5395 break;
5396
5397 case categoryspec:
5398 case notcategoryspec:
5399 not = (re_opcode_t) *(p - 1) == notcategoryspec;
5400 mcnt = *p++;
5401 DEBUG_PRINT3 ("EXECUTING %scategoryspec %d.\n", not?"not":"", mcnt);
5402 PREFETCH ();
5403 {
5404 int c, len;
5405 c = RE_STRING_CHAR_AND_LENGTH (d, dend - d, len);
5406
5407 if ((!CHAR_HAS_CATEGORY (c, mcnt)) ^ not)
5408 goto fail;
5409 d += len;
5410 }
5411 break;
5412
5413 #endif /* emacs */
5414
5415 default:
5416 abort ();
5417 }
5418 continue; /* Successfully executed one pattern command; keep going. */
5419
5420
5421 /* We goto here if a matching operation fails. */
5422 fail:
5423 QUIT;
5424 if (!FAIL_STACK_EMPTY ())
5425 {
5426 re_char *str;
5427 unsigned char *pat;
5428 /* A restart point is known. Restore to that state. */
5429 DEBUG_PRINT1 ("\nFAIL:\n");
5430 POP_FAILURE_POINT (str, pat);
5431 switch (SWITCH_ENUM_CAST ((re_opcode_t) *pat++))
5432 {
5433 case on_failure_keep_string_jump:
5434 assert (str == NULL);
5435 goto continue_failure_jump;
5436
5437 case on_failure_jump_nastyloop:
5438 assert ((re_opcode_t)pat[-2] == no_op);
5439 PUSH_FAILURE_POINT (pat - 2, str);
5440 /* Fallthrough */
5441
5442 case on_failure_jump_loop:
5443 case on_failure_jump:
5444 case succeed_n:
5445 d = str;
5446 continue_failure_jump:
5447 EXTRACT_NUMBER_AND_INCR (mcnt, pat);
5448 p = pat + mcnt;
5449 break;
5450
5451 case no_op:
5452 /* A special frame used for nastyloops. */
5453 goto fail;
5454
5455 default:
5456 abort();
5457 }
5458
5459 assert (p >= bufp->buffer && p <= pend);
5460
5461 if (d >= string1 && d <= end1)
5462 dend = end_match_1;
5463 }
5464 else
5465 break; /* Matching at this starting point really fails. */
5466 } /* for (;;) */
5467
5468 if (best_regs_set)
5469 goto restore_best_regs;
5470
5471 FREE_VARIABLES ();
5472
5473 return -1; /* Failure to match. */
5474 } /* re_match_2 */
5475 \f
5476 /* Subroutine definitions for re_match_2. */
5477
5478 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
5479 bytes; nonzero otherwise. */
5480
5481 static int
5482 bcmp_translate (s1, s2, len, translate, multibyte)
5483 re_char *s1, *s2;
5484 register int len;
5485 RE_TRANSLATE_TYPE translate;
5486 const int multibyte;
5487 {
5488 register re_char *p1 = s1, *p2 = s2;
5489 re_char *p1_end = s1 + len;
5490 re_char *p2_end = s2 + len;
5491
5492 while (p1 != p1_end && p2 != p2_end)
5493 {
5494 int p1_charlen, p2_charlen;
5495 int p1_ch, p2_ch;
5496
5497 p1_ch = RE_STRING_CHAR_AND_LENGTH (p1, p1_end - p1, p1_charlen);
5498 p2_ch = RE_STRING_CHAR_AND_LENGTH (p2, p2_end - p2, p2_charlen);
5499
5500 if (RE_TRANSLATE (translate, p1_ch)
5501 != RE_TRANSLATE (translate, p2_ch))
5502 return 1;
5503
5504 p1 += p1_charlen, p2 += p2_charlen;
5505 }
5506
5507 if (p1 != p1_end || p2 != p2_end)
5508 return 1;
5509
5510 return 0;
5511 }
5512 \f
5513 /* Entry points for GNU code. */
5514
5515 /* re_compile_pattern is the GNU regular expression compiler: it
5516 compiles PATTERN (of length SIZE) and puts the result in BUFP.
5517 Returns 0 if the pattern was valid, otherwise an error string.
5518
5519 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
5520 are set in BUFP on entry.
5521
5522 We call regex_compile to do the actual compilation. */
5523
5524 const char *
5525 re_compile_pattern (pattern, length, bufp)
5526 const char *pattern;
5527 int length;
5528 struct re_pattern_buffer *bufp;
5529 {
5530 reg_errcode_t ret;
5531
5532 /* GNU code is written to assume at least RE_NREGS registers will be set
5533 (and at least one extra will be -1). */
5534 bufp->regs_allocated = REGS_UNALLOCATED;
5535
5536 /* And GNU code determines whether or not to get register information
5537 by passing null for the REGS argument to re_match, etc., not by
5538 setting no_sub. */
5539 bufp->no_sub = 0;
5540
5541 /* Match anchors at newline. */
5542 bufp->newline_anchor = 1;
5543
5544 ret = regex_compile (pattern, length, re_syntax_options, bufp);
5545
5546 if (!ret)
5547 return NULL;
5548 return gettext (re_error_msgid[(int) ret]);
5549 }
5550 \f
5551 /* Entry points compatible with 4.2 BSD regex library. We don't define
5552 them unless specifically requested. */
5553
5554 #if defined (_REGEX_RE_COMP) || defined (_LIBC)
5555
5556 /* BSD has one and only one pattern buffer. */
5557 static struct re_pattern_buffer re_comp_buf;
5558
5559 char *
5560 #ifdef _LIBC
5561 /* Make these definitions weak in libc, so POSIX programs can redefine
5562 these names if they don't use our functions, and still use
5563 regcomp/regexec below without link errors. */
5564 weak_function
5565 #endif
5566 re_comp (s)
5567 const char *s;
5568 {
5569 reg_errcode_t ret;
5570
5571 if (!s)
5572 {
5573 if (!re_comp_buf.buffer)
5574 return gettext ("No previous regular expression");
5575 return 0;
5576 }
5577
5578 if (!re_comp_buf.buffer)
5579 {
5580 re_comp_buf.buffer = (unsigned char *) malloc (200);
5581 if (re_comp_buf.buffer == NULL)
5582 return gettext (re_error_msgid[(int) REG_ESPACE]);
5583 re_comp_buf.allocated = 200;
5584
5585 re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
5586 if (re_comp_buf.fastmap == NULL)
5587 return gettext (re_error_msgid[(int) REG_ESPACE]);
5588 }
5589
5590 /* Since `re_exec' always passes NULL for the `regs' argument, we
5591 don't need to initialize the pattern buffer fields which affect it. */
5592
5593 /* Match anchors at newlines. */
5594 re_comp_buf.newline_anchor = 1;
5595
5596 ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
5597
5598 if (!ret)
5599 return NULL;
5600
5601 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
5602 return (char *) gettext (re_error_msgid[(int) ret]);
5603 }
5604
5605
5606 int
5607 #ifdef _LIBC
5608 weak_function
5609 #endif
5610 re_exec (s)
5611 const char *s;
5612 {
5613 const int len = strlen (s);
5614 return
5615 0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
5616 }
5617 #endif /* _REGEX_RE_COMP */
5618 \f
5619 /* POSIX.2 functions. Don't define these for Emacs. */
5620
5621 #ifndef emacs
5622
5623 /* regcomp takes a regular expression as a string and compiles it.
5624
5625 PREG is a regex_t *. We do not expect any fields to be initialized,
5626 since POSIX says we shouldn't. Thus, we set
5627
5628 `buffer' to the compiled pattern;
5629 `used' to the length of the compiled pattern;
5630 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
5631 REG_EXTENDED bit in CFLAGS is set; otherwise, to
5632 RE_SYNTAX_POSIX_BASIC;
5633 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
5634 `fastmap' and `fastmap_accurate' to zero;
5635 `re_nsub' to the number of subexpressions in PATTERN.
5636
5637 PATTERN is the address of the pattern string.
5638
5639 CFLAGS is a series of bits which affect compilation.
5640
5641 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
5642 use POSIX basic syntax.
5643
5644 If REG_NEWLINE is set, then . and [^...] don't match newline.
5645 Also, regexec will try a match beginning after every newline.
5646
5647 If REG_ICASE is set, then we considers upper- and lowercase
5648 versions of letters to be equivalent when matching.
5649
5650 If REG_NOSUB is set, then when PREG is passed to regexec, that
5651 routine will report only success or failure, and nothing about the
5652 registers.
5653
5654 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
5655 the return codes and their meanings.) */
5656
5657 int
5658 regcomp (preg, pattern, cflags)
5659 regex_t *preg;
5660 const char *pattern;
5661 int cflags;
5662 {
5663 reg_errcode_t ret;
5664 unsigned syntax
5665 = (cflags & REG_EXTENDED) ?
5666 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
5667
5668 /* regex_compile will allocate the space for the compiled pattern. */
5669 preg->buffer = 0;
5670 preg->allocated = 0;
5671 preg->used = 0;
5672
5673 /* Don't bother to use a fastmap when searching. This simplifies the
5674 REG_NEWLINE case: if we used a fastmap, we'd have to put all the
5675 characters after newlines into the fastmap. This way, we just try
5676 every character. */
5677 preg->fastmap = 0;
5678
5679 if (cflags & REG_ICASE)
5680 {
5681 unsigned i;
5682
5683 preg->translate
5684 = (RE_TRANSLATE_TYPE) malloc (CHAR_SET_SIZE
5685 * sizeof (*(RE_TRANSLATE_TYPE)0));
5686 if (preg->translate == NULL)
5687 return (int) REG_ESPACE;
5688
5689 /* Map uppercase characters to corresponding lowercase ones. */
5690 for (i = 0; i < CHAR_SET_SIZE; i++)
5691 preg->translate[i] = ISUPPER (i) ? tolower (i) : i;
5692 }
5693 else
5694 preg->translate = NULL;
5695
5696 /* If REG_NEWLINE is set, newlines are treated differently. */
5697 if (cflags & REG_NEWLINE)
5698 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
5699 syntax &= ~RE_DOT_NEWLINE;
5700 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
5701 /* It also changes the matching behavior. */
5702 preg->newline_anchor = 1;
5703 }
5704 else
5705 preg->newline_anchor = 0;
5706
5707 preg->no_sub = !!(cflags & REG_NOSUB);
5708
5709 /* POSIX says a null character in the pattern terminates it, so we
5710 can use strlen here in compiling the pattern. */
5711 ret = regex_compile (pattern, strlen (pattern), syntax, preg);
5712
5713 /* POSIX doesn't distinguish between an unmatched open-group and an
5714 unmatched close-group: both are REG_EPAREN. */
5715 if (ret == REG_ERPAREN) ret = REG_EPAREN;
5716
5717 return (int) ret;
5718 }
5719
5720
5721 /* regexec searches for a given pattern, specified by PREG, in the
5722 string STRING.
5723
5724 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
5725 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
5726 least NMATCH elements, and we set them to the offsets of the
5727 corresponding matched substrings.
5728
5729 EFLAGS specifies `execution flags' which affect matching: if
5730 REG_NOTBOL is set, then ^ does not match at the beginning of the
5731 string; if REG_NOTEOL is set, then $ does not match at the end.
5732
5733 We return 0 if we find a match and REG_NOMATCH if not. */
5734
5735 int
5736 regexec (preg, string, nmatch, pmatch, eflags)
5737 const regex_t *preg;
5738 const char *string;
5739 size_t nmatch;
5740 regmatch_t pmatch[];
5741 int eflags;
5742 {
5743 int ret;
5744 struct re_registers regs;
5745 regex_t private_preg;
5746 int len = strlen (string);
5747 boolean want_reg_info = !preg->no_sub && nmatch > 0;
5748
5749 private_preg = *preg;
5750
5751 private_preg.not_bol = !!(eflags & REG_NOTBOL);
5752 private_preg.not_eol = !!(eflags & REG_NOTEOL);
5753
5754 /* The user has told us exactly how many registers to return
5755 information about, via `nmatch'. We have to pass that on to the
5756 matching routines. */
5757 private_preg.regs_allocated = REGS_FIXED;
5758
5759 if (want_reg_info)
5760 {
5761 regs.num_regs = nmatch;
5762 regs.start = TALLOC (nmatch, regoff_t);
5763 regs.end = TALLOC (nmatch, regoff_t);
5764 if (regs.start == NULL || regs.end == NULL)
5765 return (int) REG_NOMATCH;
5766 }
5767
5768 /* Perform the searching operation. */
5769 ret = re_search (&private_preg, string, len,
5770 /* start: */ 0, /* range: */ len,
5771 want_reg_info ? &regs : (struct re_registers *) 0);
5772
5773 /* Copy the register information to the POSIX structure. */
5774 if (want_reg_info)
5775 {
5776 if (ret >= 0)
5777 {
5778 unsigned r;
5779
5780 for (r = 0; r < nmatch; r++)
5781 {
5782 pmatch[r].rm_so = regs.start[r];
5783 pmatch[r].rm_eo = regs.end[r];
5784 }
5785 }
5786
5787 /* If we needed the temporary register info, free the space now. */
5788 free (regs.start);
5789 free (regs.end);
5790 }
5791
5792 /* We want zero return to mean success, unlike `re_search'. */
5793 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
5794 }
5795
5796
5797 /* Returns a message corresponding to an error code, ERRCODE, returned
5798 from either regcomp or regexec. We don't use PREG here. */
5799
5800 size_t
5801 regerror (errcode, preg, errbuf, errbuf_size)
5802 int errcode;
5803 const regex_t *preg;
5804 char *errbuf;
5805 size_t errbuf_size;
5806 {
5807 const char *msg;
5808 size_t msg_size;
5809
5810 if (errcode < 0
5811 || errcode >= (sizeof (re_error_msgid) / sizeof (re_error_msgid[0])))
5812 /* Only error codes returned by the rest of the code should be passed
5813 to this routine. If we are given anything else, or if other regex
5814 code generates an invalid error code, then the program has a bug.
5815 Dump core so we can fix it. */
5816 abort ();
5817
5818 msg = gettext (re_error_msgid[errcode]);
5819
5820 msg_size = strlen (msg) + 1; /* Includes the null. */
5821
5822 if (errbuf_size != 0)
5823 {
5824 if (msg_size > errbuf_size)
5825 {
5826 strncpy (errbuf, msg, errbuf_size - 1);
5827 errbuf[errbuf_size - 1] = 0;
5828 }
5829 else
5830 strcpy (errbuf, msg);
5831 }
5832
5833 return msg_size;
5834 }
5835
5836
5837 /* Free dynamically allocated space used by PREG. */
5838
5839 void
5840 regfree (preg)
5841 regex_t *preg;
5842 {
5843 if (preg->buffer != NULL)
5844 free (preg->buffer);
5845 preg->buffer = NULL;
5846
5847 preg->allocated = 0;
5848 preg->used = 0;
5849
5850 if (preg->fastmap != NULL)
5851 free (preg->fastmap);
5852 preg->fastmap = NULL;
5853 preg->fastmap_accurate = 0;
5854
5855 if (preg->translate != NULL)
5856 free (preg->translate);
5857 preg->translate = NULL;
5858 }
5859
5860 #endif /* not emacs */
Unnamed repository; edit this file 'description' to name the repository.