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