b7c82f633eeb3b93638a46178c83c015420055ea
[kopensolaris-gnu/glibc.git] / posix / regex.c
1 /* Extended regular expression matching and search library,
2    version 0.12.
3    (Implements POSIX draft P10003.2/D11.2, except for
4    internationalization features.)
5
6    Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
7
8    This file is part of the GNU C Library.  Its master source is NOT part of
9    the C library, however.  The master source lives in /gd/gnu/lib.
10
11    The GNU C Library is free software; you can redistribute it and/or
12    modify it under the terms of the GNU Library General Public License as
13    published by the Free Software Foundation; either version 2 of the
14    License, or (at your option) any later version.
15
16    The GNU C Library is distributed in the hope that it will be useful,
17    but WITHOUT ANY WARRANTY; without even the implied warranty of
18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19    Library General Public License for more details.
20
21    You should have received a copy of the GNU Library General Public
22    License along with the GNU C Library; see the file COPYING.LIB.  If not,
23    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24    Boston, MA 02111-1307, USA.  */
25
26 /* AIX requires this to be the first thing in the file. */
27 #if defined (_AIX) && !defined (REGEX_MALLOC)
28   #pragma alloca
29 #endif
30
31 #undef  _GNU_SOURCE
32 #define _GNU_SOURCE
33
34 #ifdef HAVE_CONFIG_H
35 #include <config.h>
36 #endif
37
38 #if defined(STDC_HEADERS) && !defined(emacs)
39 #include <stddef.h>
40 #else
41 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
42 #include <sys/types.h>
43 #endif
44
45 /* This is for other GNU distributions with internationalized messages.  */
46 #if HAVE_LIBINTL_H || defined (_LIBC)
47 # include <libintl.h>
48 #else
49 # define gettext(msgid) (msgid)
50 #endif
51
52 #ifndef gettext_noop
53 /* This define is so xgettext can find the internationalizable
54    strings.  */
55 #define gettext_noop(String) String
56 #endif
57
58 /* The `emacs' switch turns on certain matching commands
59    that make sense only in Emacs. */
60 #ifdef emacs
61
62 #include "lisp.h"
63 #include "buffer.h"
64 #include "syntax.h"
65
66 #else  /* not emacs */
67
68 /* If we are not linking with Emacs proper,
69    we can't use the relocating allocator
70    even if config.h says that we can.  */
71 #undef REL_ALLOC
72
73 #if defined (STDC_HEADERS) || defined (_LIBC)
74 #include <stdlib.h>
75 #else
76 char *malloc ();
77 char *realloc ();
78 #endif
79
80 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
81    If nothing else has been done, use the method below.  */
82 #ifdef INHIBIT_STRING_HEADER
83 #if !(defined (HAVE_BZERO) && defined (HAVE_BCOPY))
84 #if !defined (bzero) && !defined (bcopy)
85 #undef INHIBIT_STRING_HEADER
86 #endif
87 #endif
88 #endif
89
90 /* This is the normal way of making sure we have a bcopy and a bzero.
91    This is used in most programs--a few other programs avoid this
92    by defining INHIBIT_STRING_HEADER.  */
93 #ifndef INHIBIT_STRING_HEADER
94 #if defined (HAVE_STRING_H) || defined (STDC_HEADERS) || defined (_LIBC)
95 #include <string.h>
96 #ifndef bcmp
97 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
98 #endif
99 #ifndef bcopy
100 #define bcopy(s, d, n)  memcpy ((d), (s), (n))
101 #endif
102 #ifndef bzero
103 #define bzero(s, n)     memset ((s), 0, (n))
104 #endif
105 #else
106 #include <strings.h>
107 #endif
108 #endif
109
110 /* Define the syntax stuff for \<, \>, etc.  */
111
112 /* This must be nonzero for the wordchar and notwordchar pattern
113    commands in re_match_2.  */
114 #ifndef Sword
115 #define Sword 1
116 #endif
117
118 #ifdef SWITCH_ENUM_BUG
119 #define SWITCH_ENUM_CAST(x) ((int)(x))
120 #else
121 #define SWITCH_ENUM_CAST(x) (x)
122 #endif
123
124 #ifdef SYNTAX_TABLE
125
126 extern char *re_syntax_table;
127
128 #else /* not SYNTAX_TABLE */
129
130 /* How many characters in the character set.  */
131 #define CHAR_SET_SIZE 256
132
133 static char re_syntax_table[CHAR_SET_SIZE];
134
135 static void
136 init_syntax_once ()
137 {
138    register int c;
139    static int done = 0;
140
141    if (done)
142      return;
143
144    bzero (re_syntax_table, sizeof re_syntax_table);
145
146    for (c = 'a'; c <= 'z'; c++)
147      re_syntax_table[c] = Sword;
148
149    for (c = 'A'; c <= 'Z'; c++)
150      re_syntax_table[c] = Sword;
151
152    for (c = '0'; c <= '9'; c++)
153      re_syntax_table[c] = Sword;
154
155    re_syntax_table['_'] = Sword;
156
157    done = 1;
158 }
159
160 #endif /* not SYNTAX_TABLE */
161
162 #define SYNTAX(c) re_syntax_table[c]
163
164 #endif /* not emacs */
165 \f
166 /* Get the interface, including the syntax bits.  */
167 #include "regex.h"
168
169 /* isalpha etc. are used for the character classes.  */
170 #include <ctype.h>
171
172 /* Jim Meyering writes:
173
174    "... Some ctype macros are valid only for character codes that
175    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
176    using /bin/cc or gcc but without giving an ansi option).  So, all
177    ctype uses should be through macros like ISPRINT...  If
178    STDC_HEADERS is defined, then autoconf has verified that the ctype
179    macros don't need to be guarded with references to isascii. ...
180    Defining isascii to 1 should let any compiler worth its salt
181    eliminate the && through constant folding."  */
182
183 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
184 #define ISASCII(c) 1
185 #else
186 #define ISASCII(c) isascii(c)
187 #endif
188
189 #ifdef isblank
190 #define ISBLANK(c) (ISASCII (c) && isblank (c))
191 #else
192 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
193 #endif
194 #ifdef isgraph
195 #define ISGRAPH(c) (ISASCII (c) && isgraph (c))
196 #else
197 #define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
198 #endif
199
200 #define ISPRINT(c) (ISASCII (c) && isprint (c))
201 #define ISDIGIT(c) (ISASCII (c) && isdigit (c))
202 #define ISALNUM(c) (ISASCII (c) && isalnum (c))
203 #define ISALPHA(c) (ISASCII (c) && isalpha (c))
204 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
205 #define ISLOWER(c) (ISASCII (c) && islower (c))
206 #define ISPUNCT(c) (ISASCII (c) && ispunct (c))
207 #define ISSPACE(c) (ISASCII (c) && isspace (c))
208 #define ISUPPER(c) (ISASCII (c) && isupper (c))
209 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
210
211 #ifndef NULL
212 #define NULL (void *)0
213 #endif
214
215 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
216    since ours (we hope) works properly with all combinations of
217    machines, compilers, `char' and `unsigned char' argument types.
218    (Per Bothner suggested the basic approach.)  */
219 #undef SIGN_EXTEND_CHAR
220 #if __STDC__
221 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
222 #else  /* not __STDC__ */
223 /* As in Harbison and Steele.  */
224 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
225 #endif
226 \f
227 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
228    use `alloca' instead of `malloc'.  This is because using malloc in
229    re_search* or re_match* could cause memory leaks when C-g is used in
230    Emacs; also, malloc is slower and causes storage fragmentation.  On
231    the other hand, malloc is more portable, and easier to debug.
232
233    Because we sometimes use alloca, some routines have to be macros,
234    not functions -- `alloca'-allocated space disappears at the end of the
235    function it is called in.  */
236
237 #ifdef REGEX_MALLOC
238
239 #define REGEX_ALLOCATE malloc
240 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
241 #define REGEX_FREE free
242
243 #else /* not REGEX_MALLOC  */
244
245 /* Emacs already defines alloca, sometimes.  */
246 #ifndef alloca
247
248 /* Make alloca work the best possible way.  */
249 #ifdef __GNUC__
250 #define alloca __builtin_alloca
251 #else /* not __GNUC__ */
252 #if HAVE_ALLOCA_H
253 #include <alloca.h>
254 #else /* not __GNUC__ or HAVE_ALLOCA_H */
255 #if 0 /* It is a bad idea to declare alloca.  We always cast the result.  */
256 #ifndef _AIX /* Already did AIX, up at the top.  */
257 char *alloca ();
258 #endif /* not _AIX */
259 #endif
260 #endif /* not HAVE_ALLOCA_H */
261 #endif /* not __GNUC__ */
262
263 #endif /* not alloca */
264
265 #define REGEX_ALLOCATE alloca
266
267 /* Assumes a `char *destination' variable.  */
268 #define REGEX_REALLOCATE(source, osize, nsize)                          \
269   (destination = (char *) alloca (nsize),                               \
270    bcopy (source, destination, osize),                                  \
271    destination)
272
273 /* No need to do anything to free, after alloca.  */
274 #define REGEX_FREE(arg) ((void)0) /* Do nothing!  But inhibit gcc warning.  */
275
276 #endif /* not REGEX_MALLOC */
277
278 /* Define how to allocate the failure stack.  */
279
280 #if defined (REL_ALLOC) && defined (REGEX_MALLOC)
281
282 #define REGEX_ALLOCATE_STACK(size)                              \
283   r_alloc (&failure_stack_ptr, (size))
284 #define REGEX_REALLOCATE_STACK(source, osize, nsize)            \
285   r_re_alloc (&failure_stack_ptr, (nsize))
286 #define REGEX_FREE_STACK(ptr)                                   \
287   r_alloc_free (&failure_stack_ptr)
288
289 #else /* not using relocating allocator */
290
291 #ifdef REGEX_MALLOC
292
293 #define REGEX_ALLOCATE_STACK malloc
294 #define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
295 #define REGEX_FREE_STACK free
296
297 #else /* not REGEX_MALLOC */
298
299 #define REGEX_ALLOCATE_STACK alloca
300
301 #define REGEX_REALLOCATE_STACK(source, osize, nsize)                    \
302    REGEX_REALLOCATE (source, osize, nsize)
303 /* No need to explicitly free anything.  */
304 #define REGEX_FREE_STACK(arg)
305
306 #endif /* not REGEX_MALLOC */
307 #endif /* not using relocating allocator */
308
309
310 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
311    `string1' or just past its end.  This works if PTR is NULL, which is
312    a good thing.  */
313 #define FIRST_STRING_P(ptr)                                     \
314   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
315
316 /* (Re)Allocate N items of type T using malloc, or fail.  */
317 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
318 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
319 #define RETALLOC_IF(addr, n, t) \
320   if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
321 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
322
323 #define BYTEWIDTH 8 /* In bits.  */
324
325 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
326
327 #undef MAX
328 #undef MIN
329 #define MAX(a, b) ((a) > (b) ? (a) : (b))
330 #define MIN(a, b) ((a) < (b) ? (a) : (b))
331
332 typedef char boolean;
333 #define false 0
334 #define true 1
335
336 static int re_match_2_internal ();
337 \f
338 /* These are the command codes that appear in compiled regular
339    expressions.  Some opcodes are followed by argument bytes.  A
340    command code can specify any interpretation whatsoever for its
341    arguments.  Zero bytes may appear in the compiled regular expression.  */
342
343 typedef enum
344 {
345   no_op = 0,
346
347   /* Succeed right away--no more backtracking.  */
348   succeed,
349
350         /* Followed by one byte giving n, then by n literal bytes.  */
351   exactn,
352
353         /* Matches any (more or less) character.  */
354   anychar,
355
356         /* Matches any one char belonging to specified set.  First
357            following byte is number of bitmap bytes.  Then come bytes
358            for a bitmap saying which chars are in.  Bits in each byte
359            are ordered low-bit-first.  A character is in the set if its
360            bit is 1.  A character too large to have a bit in the map is
361            automatically not in the set.  */
362   charset,
363
364         /* Same parameters as charset, but match any character that is
365            not one of those specified.  */
366   charset_not,
367
368         /* Start remembering the text that is matched, for storing in a
369            register.  Followed by one byte with the register number, in
370            the range 0 to one less than the pattern buffer's re_nsub
371            field.  Then followed by one byte with the number of groups
372            inner to this one.  (This last has to be part of the
373            start_memory only because we need it in the on_failure_jump
374            of re_match_2.)  */
375   start_memory,
376
377         /* Stop remembering the text that is matched and store it in a
378            memory register.  Followed by one byte with the register
379            number, in the range 0 to one less than `re_nsub' in the
380            pattern buffer, and one byte with the number of inner groups,
381            just like `start_memory'.  (We need the number of inner
382            groups here because we don't have any easy way of finding the
383            corresponding start_memory when we're at a stop_memory.)  */
384   stop_memory,
385
386         /* Match a duplicate of something remembered. Followed by one
387            byte containing the register number.  */
388   duplicate,
389
390         /* Fail unless at beginning of line.  */
391   begline,
392
393         /* Fail unless at end of line.  */
394   endline,
395
396         /* Succeeds if at beginning of buffer (if emacs) or at beginning
397            of string to be matched (if not).  */
398   begbuf,
399
400         /* Analogously, for end of buffer/string.  */
401   endbuf,
402
403         /* Followed by two byte relative address to which to jump.  */
404   jump,
405
406         /* Same as jump, but marks the end of an alternative.  */
407   jump_past_alt,
408
409         /* Followed by two-byte relative address of place to resume at
410            in case of failure.  */
411   on_failure_jump,
412
413         /* Like on_failure_jump, but pushes a placeholder instead of the
414            current string position when executed.  */
415   on_failure_keep_string_jump,
416
417         /* Throw away latest failure point and then jump to following
418            two-byte relative address.  */
419   pop_failure_jump,
420
421         /* Change to pop_failure_jump if know won't have to backtrack to
422            match; otherwise change to jump.  This is used to jump
423            back to the beginning of a repeat.  If what follows this jump
424            clearly won't match what the repeat does, such that we can be
425            sure that there is no use backtracking out of repetitions
426            already matched, then we change it to a pop_failure_jump.
427            Followed by two-byte address.  */
428   maybe_pop_jump,
429
430         /* Jump to following two-byte address, and push a dummy failure
431            point. This failure point will be thrown away if an attempt
432            is made to use it for a failure.  A `+' construct makes this
433            before the first repeat.  Also used as an intermediary kind
434            of jump when compiling an alternative.  */
435   dummy_failure_jump,
436
437         /* Push a dummy failure point and continue.  Used at the end of
438            alternatives.  */
439   push_dummy_failure,
440
441         /* Followed by two-byte relative address and two-byte number n.
442            After matching N times, jump to the address upon failure.  */
443   succeed_n,
444
445         /* Followed by two-byte relative address, and two-byte number n.
446            Jump to the address N times, then fail.  */
447   jump_n,
448
449         /* Set the following two-byte relative address to the
450            subsequent two-byte number.  The address *includes* the two
451            bytes of number.  */
452   set_number_at,
453
454   wordchar,     /* Matches any word-constituent character.  */
455   notwordchar,  /* Matches any char that is not a word-constituent.  */
456
457   wordbeg,      /* Succeeds if at word beginning.  */
458   wordend,      /* Succeeds if at word end.  */
459
460   wordbound,    /* Succeeds if at a word boundary.  */
461   notwordbound  /* Succeeds if not at a word boundary.  */
462
463 #ifdef emacs
464   ,before_dot,  /* Succeeds if before point.  */
465   at_dot,       /* Succeeds if at point.  */
466   after_dot,    /* Succeeds if after point.  */
467
468         /* Matches any character whose syntax is specified.  Followed by
469            a byte which contains a syntax code, e.g., Sword.  */
470   syntaxspec,
471
472         /* Matches any character whose syntax is not that specified.  */
473   notsyntaxspec
474 #endif /* emacs */
475 } re_opcode_t;
476 \f
477 /* Common operations on the compiled pattern.  */
478
479 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
480
481 #define STORE_NUMBER(destination, number)                               \
482   do {                                                                  \
483     (destination)[0] = (number) & 0377;                                 \
484     (destination)[1] = (number) >> 8;                                   \
485   } while (0)
486
487 /* Same as STORE_NUMBER, except increment DESTINATION to
488    the byte after where the number is stored.  Therefore, DESTINATION
489    must be an lvalue.  */
490
491 #define STORE_NUMBER_AND_INCR(destination, number)                      \
492   do {                                                                  \
493     STORE_NUMBER (destination, number);                                 \
494     (destination) += 2;                                                 \
495   } while (0)
496
497 /* Put into DESTINATION a number stored in two contiguous bytes starting
498    at SOURCE.  */
499
500 #define EXTRACT_NUMBER(destination, source)                             \
501   do {                                                                  \
502     (destination) = *(source) & 0377;                                   \
503     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;           \
504   } while (0)
505
506 #ifdef DEBUG
507 static void extract_number _RE_ARGS ((int *dest, unsigned char *source));
508 static void
509 extract_number (dest, source)
510     int *dest;
511     unsigned char *source;
512 {
513   int temp = SIGN_EXTEND_CHAR (*(source + 1));
514   *dest = *source & 0377;
515   *dest += temp << 8;
516 }
517
518 #ifndef EXTRACT_MACROS /* To debug the macros.  */
519 #undef EXTRACT_NUMBER
520 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
521 #endif /* not EXTRACT_MACROS */
522
523 #endif /* DEBUG */
524
525 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
526    SOURCE must be an lvalue.  */
527
528 #define EXTRACT_NUMBER_AND_INCR(destination, source)                    \
529   do {                                                                  \
530     EXTRACT_NUMBER (destination, source);                               \
531     (source) += 2;                                                      \
532   } while (0)
533
534 #ifdef DEBUG
535 static void extract_number_and_incr _RE_ARGS ((int *destination,
536                                                unsigned char **source));
537 static void
538 extract_number_and_incr (destination, source)
539     int *destination;
540     unsigned char **source;
541 {
542   extract_number (destination, *source);
543   *source += 2;
544 }
545
546 #ifndef EXTRACT_MACROS
547 #undef EXTRACT_NUMBER_AND_INCR
548 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
549   extract_number_and_incr (&dest, &src)
550 #endif /* not EXTRACT_MACROS */
551
552 #endif /* DEBUG */
553 \f
554 /* If DEBUG is defined, Regex prints many voluminous messages about what
555    it is doing (if the variable `debug' is nonzero).  If linked with the
556    main program in `iregex.c', you can enter patterns and strings
557    interactively.  And if linked with the main program in `main.c' and
558    the other test files, you can run the already-written tests.  */
559
560 #ifdef DEBUG
561
562 /* We use standard I/O for debugging.  */
563 #include <stdio.h>
564
565 /* It is useful to test things that ``must'' be true when debugging.  */
566 #include <assert.h>
567
568 static int debug = 0;
569
570 #define DEBUG_STATEMENT(e) e
571 #define DEBUG_PRINT1(x) if (debug) printf (x)
572 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
573 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
574 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
575 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)                           \
576   if (debug) print_partial_compiled_pattern (s, e)
577 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)                  \
578   if (debug) print_double_string (w, s1, sz1, s2, sz2)
579
580
581 /* Print the fastmap in human-readable form.  */
582
583 void
584 print_fastmap (fastmap)
585     char *fastmap;
586 {
587   unsigned was_a_range = 0;
588   unsigned i = 0;
589
590   while (i < (1 << BYTEWIDTH))
591     {
592       if (fastmap[i++])
593         {
594           was_a_range = 0;
595           putchar (i - 1);
596           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
597             {
598               was_a_range = 1;
599               i++;
600             }
601           if (was_a_range)
602             {
603               printf ("-");
604               putchar (i - 1);
605             }
606         }
607     }
608   putchar ('\n');
609 }
610
611
612 /* Print a compiled pattern string in human-readable form, starting at
613    the START pointer into it and ending just before the pointer END.  */
614
615 void
616 print_partial_compiled_pattern (start, end)
617     unsigned char *start;
618     unsigned char *end;
619 {
620   int mcnt, mcnt2;
621   unsigned char *p1;
622   unsigned char *p = start;
623   unsigned char *pend = end;
624
625   if (start == NULL)
626     {
627       printf ("(null)\n");
628       return;
629     }
630
631   /* Loop over pattern commands.  */
632   while (p < pend)
633     {
634       printf ("%d:\t", p - start);
635
636       switch ((re_opcode_t) *p++)
637         {
638         case no_op:
639           printf ("/no_op");
640           break;
641
642         case exactn:
643           mcnt = *p++;
644           printf ("/exactn/%d", mcnt);
645           do
646             {
647               putchar ('/');
648               putchar (*p++);
649             }
650           while (--mcnt);
651           break;
652
653         case start_memory:
654           mcnt = *p++;
655           printf ("/start_memory/%d/%d", mcnt, *p++);
656           break;
657
658         case stop_memory:
659           mcnt = *p++;
660           printf ("/stop_memory/%d/%d", mcnt, *p++);
661           break;
662
663         case duplicate:
664           printf ("/duplicate/%d", *p++);
665           break;
666
667         case anychar:
668           printf ("/anychar");
669           break;
670
671         case charset:
672         case charset_not:
673           {
674             register int c, last = -100;
675             register int in_range = 0;
676
677             printf ("/charset [%s",
678                     (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
679
680             assert (p + *p < pend);
681
682             for (c = 0; c < 256; c++)
683               if (c / 8 < *p
684                   && (p[1 + (c/8)] & (1 << (c % 8))))
685                 {
686                   /* Are we starting a range?  */
687                   if (last + 1 == c && ! in_range)
688                     {
689                       putchar ('-');
690                       in_range = 1;
691                     }
692                   /* Have we broken a range?  */
693                   else if (last + 1 != c && in_range)
694               {
695                       putchar (last);
696                       in_range = 0;
697                     }
698
699                   if (! in_range)
700                     putchar (c);
701
702                   last = c;
703               }
704
705             if (in_range)
706               putchar (last);
707
708             putchar (']');
709
710             p += 1 + *p;
711           }
712           break;
713
714         case begline:
715           printf ("/begline");
716           break;
717
718         case endline:
719           printf ("/endline");
720           break;
721
722         case on_failure_jump:
723           extract_number_and_incr (&mcnt, &p);
724           printf ("/on_failure_jump to %d", p + mcnt - start);
725           break;
726
727         case on_failure_keep_string_jump:
728           extract_number_and_incr (&mcnt, &p);
729           printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
730           break;
731
732         case dummy_failure_jump:
733           extract_number_and_incr (&mcnt, &p);
734           printf ("/dummy_failure_jump to %d", p + mcnt - start);
735           break;
736
737         case push_dummy_failure:
738           printf ("/push_dummy_failure");
739           break;
740
741         case maybe_pop_jump:
742           extract_number_and_incr (&mcnt, &p);
743           printf ("/maybe_pop_jump to %d", p + mcnt - start);
744           break;
745
746         case pop_failure_jump:
747           extract_number_and_incr (&mcnt, &p);
748           printf ("/pop_failure_jump to %d", p + mcnt - start);
749           break;
750
751         case jump_past_alt:
752           extract_number_and_incr (&mcnt, &p);
753           printf ("/jump_past_alt to %d", p + mcnt - start);
754           break;
755
756         case jump:
757           extract_number_and_incr (&mcnt, &p);
758           printf ("/jump to %d", p + mcnt - start);
759           break;
760
761         case succeed_n:
762           extract_number_and_incr (&mcnt, &p);
763           p1 = p + mcnt;
764           extract_number_and_incr (&mcnt2, &p);
765           printf ("/succeed_n to %d, %d times", p1 - start, mcnt2);
766           break;
767
768         case jump_n:
769           extract_number_and_incr (&mcnt, &p);
770           p1 = p + mcnt;
771           extract_number_and_incr (&mcnt2, &p);
772           printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
773           break;
774
775         case set_number_at:
776           extract_number_and_incr (&mcnt, &p);
777           p1 = p + mcnt;
778           extract_number_and_incr (&mcnt2, &p);
779           printf ("/set_number_at location %d to %d", p1 - start, mcnt2);
780           break;
781
782         case wordbound:
783           printf ("/wordbound");
784           break;
785
786         case notwordbound:
787           printf ("/notwordbound");
788           break;
789
790         case wordbeg:
791           printf ("/wordbeg");
792           break;
793
794         case wordend:
795           printf ("/wordend");
796
797 #ifdef emacs
798         case before_dot:
799           printf ("/before_dot");
800           break;
801
802         case at_dot:
803           printf ("/at_dot");
804           break;
805
806         case after_dot:
807           printf ("/after_dot");
808           break;
809
810         case syntaxspec:
811           printf ("/syntaxspec");
812           mcnt = *p++;
813           printf ("/%d", mcnt);
814           break;
815
816         case notsyntaxspec:
817           printf ("/notsyntaxspec");
818           mcnt = *p++;
819           printf ("/%d", mcnt);
820           break;
821 #endif /* emacs */
822
823         case wordchar:
824           printf ("/wordchar");
825           break;
826
827         case notwordchar:
828           printf ("/notwordchar");
829           break;
830
831         case begbuf:
832           printf ("/begbuf");
833           break;
834
835         case endbuf:
836           printf ("/endbuf");
837           break;
838
839         default:
840           printf ("?%d", *(p-1));
841         }
842
843       putchar ('\n');
844     }
845
846   printf ("%d:\tend of pattern.\n", p - start);
847 }
848
849
850 void
851 print_compiled_pattern (bufp)
852     struct re_pattern_buffer *bufp;
853 {
854   unsigned char *buffer = bufp->buffer;
855
856   print_partial_compiled_pattern (buffer, buffer + bufp->used);
857   printf ("%ld bytes used/%ld bytes allocated.\n",
858           bufp->used, bufp->allocated);
859
860   if (bufp->fastmap_accurate && bufp->fastmap)
861     {
862       printf ("fastmap: ");
863       print_fastmap (bufp->fastmap);
864     }
865
866   printf ("re_nsub: %d\t", bufp->re_nsub);
867   printf ("regs_alloc: %d\t", bufp->regs_allocated);
868   printf ("can_be_null: %d\t", bufp->can_be_null);
869   printf ("newline_anchor: %d\n", bufp->newline_anchor);
870   printf ("no_sub: %d\t", bufp->no_sub);
871   printf ("not_bol: %d\t", bufp->not_bol);
872   printf ("not_eol: %d\t", bufp->not_eol);
873   printf ("syntax: %lx\n", bufp->syntax);
874   /* Perhaps we should print the translate table?  */
875 }
876
877
878 void
879 print_double_string (where, string1, size1, string2, size2)
880     const char *where;
881     const char *string1;
882     const char *string2;
883     int size1;
884     int size2;
885 {
886   int this_char;
887
888   if (where == NULL)
889     printf ("(null)");
890   else
891     {
892       if (FIRST_STRING_P (where))
893         {
894           for (this_char = where - string1; this_char < size1; this_char++)
895             putchar (string1[this_char]);
896
897           where = string2;
898         }
899
900       for (this_char = where - string2; this_char < size2; this_char++)
901         putchar (string2[this_char]);
902     }
903 }
904
905 void
906 printchar (c)
907      int c;
908 {
909   putc (c, stderr);
910 }
911
912 #else /* not DEBUG */
913
914 #undef assert
915 #define assert(e)
916
917 #define DEBUG_STATEMENT(e)
918 #define DEBUG_PRINT1(x)
919 #define DEBUG_PRINT2(x1, x2)
920 #define DEBUG_PRINT3(x1, x2, x3)
921 #define DEBUG_PRINT4(x1, x2, x3, x4)
922 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
923 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
924
925 #endif /* not DEBUG */
926 \f
927 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
928    also be assigned to arbitrarily: each pattern buffer stores its own
929    syntax, so it can be changed between regex compilations.  */
930 /* This has no initializer because initialized variables in Emacs
931    become read-only after dumping.  */
932 reg_syntax_t re_syntax_options;
933
934
935 /* Specify the precise syntax of regexps for compilation.  This provides
936    for compatibility for various utilities which historically have
937    different, incompatible syntaxes.
938
939    The argument SYNTAX is a bit mask comprised of the various bits
940    defined in regex.h.  We return the old syntax.  */
941
942 reg_syntax_t
943 re_set_syntax (syntax)
944     reg_syntax_t syntax;
945 {
946   reg_syntax_t ret = re_syntax_options;
947
948   re_syntax_options = syntax;
949   return ret;
950 }
951 \f
952 /* This table gives an error message for each of the error codes listed
953    in regex.h.  Obviously the order here has to be same as there.
954    POSIX doesn't require that we do anything for REG_NOERROR,
955    but why not be nice?  */
956
957 static const char *re_error_msgid[] =
958   {
959     gettext_noop ("Success"),   /* REG_NOERROR */
960     gettext_noop ("No match"),  /* REG_NOMATCH */
961     gettext_noop ("Invalid regular expression"), /* REG_BADPAT */
962     gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */
963     gettext_noop ("Invalid character class name"), /* REG_ECTYPE */
964     gettext_noop ("Trailing backslash"), /* REG_EESCAPE */
965     gettext_noop ("Invalid back reference"), /* REG_ESUBREG */
966     gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */
967     gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */
968     gettext_noop ("Unmatched \\{"), /* REG_EBRACE */
969     gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */
970     gettext_noop ("Invalid range end"), /* REG_ERANGE */
971     gettext_noop ("Memory exhausted"), /* REG_ESPACE */
972     gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */
973     gettext_noop ("Premature end of regular expression"), /* REG_EEND */
974     gettext_noop ("Regular expression too big"), /* REG_ESIZE */
975     gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */
976   };
977 \f
978 /* Avoiding alloca during matching, to placate r_alloc.  */
979
980 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
981    searching and matching functions should not call alloca.  On some
982    systems, alloca is implemented in terms of malloc, and if we're
983    using the relocating allocator routines, then malloc could cause a
984    relocation, which might (if the strings being searched are in the
985    ralloc heap) shift the data out from underneath the regexp
986    routines.
987
988    Here's another reason to avoid allocation: Emacs
989    processes input from X in a signal handler; processing X input may
990    call malloc; if input arrives while a matching routine is calling
991    malloc, then we're scrod.  But Emacs can't just block input while
992    calling matching routines; then we don't notice interrupts when
993    they come in.  So, Emacs blocks input around all regexp calls
994    except the matching calls, which it leaves unprotected, in the
995    faith that they will not malloc.  */
996
997 /* Normally, this is fine.  */
998 #define MATCH_MAY_ALLOCATE
999
1000 /* When using GNU C, we are not REALLY using the C alloca, no matter
1001    what config.h may say.  So don't take precautions for it.  */
1002 #ifdef __GNUC__
1003 #undef C_ALLOCA
1004 #endif
1005
1006 /* The match routines may not allocate if (1) they would do it with malloc
1007    and (2) it's not safe for them to use malloc.
1008    Note that if REL_ALLOC is defined, matching would not use malloc for the
1009    failure stack, but we would still use it for the register vectors;
1010    so REL_ALLOC should not affect this.  */
1011 #if (defined (C_ALLOCA) || defined (REGEX_MALLOC)) && defined (emacs)
1012 #undef MATCH_MAY_ALLOCATE
1013 #endif
1014
1015 \f
1016 /* Failure stack declarations and macros; both re_compile_fastmap and
1017    re_match_2 use a failure stack.  These have to be macros because of
1018    REGEX_ALLOCATE_STACK.  */
1019
1020
1021 /* Number of failure points for which to initially allocate space
1022    when matching.  If this number is exceeded, we allocate more
1023    space, so it is not a hard limit.  */
1024 #ifndef INIT_FAILURE_ALLOC
1025 #define INIT_FAILURE_ALLOC 5
1026 #endif
1027
1028 /* Roughly the maximum number of failure points on the stack.  Would be
1029    exactly that if always used MAX_FAILURE_SPACE each time we failed.
1030    This is a variable only so users of regex can assign to it; we never
1031    change it ourselves.  */
1032
1033 #ifdef INT_IS_16BIT
1034
1035 #if defined (MATCH_MAY_ALLOCATE)
1036 long re_max_failures = 4000;
1037 #else
1038 long re_max_failures = 2000;
1039 #endif
1040
1041 union fail_stack_elt
1042 {
1043   unsigned char *pointer;
1044   long integer;
1045 };
1046
1047 typedef union fail_stack_elt fail_stack_elt_t;
1048
1049 typedef struct
1050 {
1051   fail_stack_elt_t *stack;
1052   unsigned long size;
1053   unsigned long avail;                 /* Offset of next open position.  */
1054 } fail_stack_type;
1055
1056 #else /* not INT_IS_16BIT */
1057
1058 #if defined (MATCH_MAY_ALLOCATE)
1059 /* 4400 was enough to cause a crash on Alpha OSF/1,
1060    whose default stack limit is 2mb.  */
1061 int re_max_failures = 4000;
1062 #else
1063 int re_max_failures = 2000;
1064 #endif
1065
1066 union fail_stack_elt
1067 {
1068   unsigned char *pointer;
1069   int integer;
1070 };
1071
1072 typedef union fail_stack_elt fail_stack_elt_t;
1073
1074 typedef struct
1075 {
1076   fail_stack_elt_t *stack;
1077   unsigned size;
1078   unsigned avail;                       /* Offset of next open position.  */
1079 } fail_stack_type;
1080
1081 #endif /* INT_IS_16BIT */
1082
1083 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
1084 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1085 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
1086
1087
1088 /* Define macros to initialize and free the failure stack.
1089    Do `return -2' if the alloc fails.  */
1090
1091 #ifdef MATCH_MAY_ALLOCATE
1092 #define INIT_FAIL_STACK()                                               \
1093   do {                                                                  \
1094     fail_stack.stack = (fail_stack_elt_t *)                             \
1095       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));    \
1096                                                                         \
1097     if (fail_stack.stack == NULL)                                       \
1098       return -2;                                                        \
1099                                                                         \
1100     fail_stack.size = INIT_FAILURE_ALLOC;                               \
1101     fail_stack.avail = 0;                                               \
1102   } while (0)
1103
1104 #define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
1105 #else
1106 #define INIT_FAIL_STACK()                                               \
1107   do {                                                                  \
1108     fail_stack.avail = 0;                                               \
1109   } while (0)
1110
1111 #define RESET_FAIL_STACK()
1112 #endif
1113
1114
1115 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1116
1117    Return 1 if succeeds, and 0 if either ran out of memory
1118    allocating space for it or it was already too large.
1119
1120    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
1121
1122 #define DOUBLE_FAIL_STACK(fail_stack)                                   \
1123   ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1124    ? 0                                                                  \
1125    : ((fail_stack).stack = (fail_stack_elt_t *)                         \
1126         REGEX_REALLOCATE_STACK ((fail_stack).stack,                     \
1127           (fail_stack).size * sizeof (fail_stack_elt_t),                \
1128           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),        \
1129                                                                         \
1130       (fail_stack).stack == NULL                                        \
1131       ? 0                                                               \
1132       : ((fail_stack).size <<= 1,                                       \
1133          1)))
1134
1135
1136 /* Push pointer POINTER on FAIL_STACK.
1137    Return 1 if was able to do so and 0 if ran out of memory allocating
1138    space to do so.  */
1139 #define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                            \
1140   ((FAIL_STACK_FULL ()                                                  \
1141     && !DOUBLE_FAIL_STACK (FAIL_STACK))                                 \
1142    ? 0                                                                  \
1143    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,       \
1144       1))
1145
1146 /* Push a pointer value onto the failure stack.
1147    Assumes the variable `fail_stack'.  Probably should only
1148    be called from within `PUSH_FAILURE_POINT'.  */
1149 #define PUSH_FAILURE_POINTER(item)                                      \
1150   fail_stack.stack[fail_stack.avail++].pointer = (unsigned char *) (item)
1151
1152 /* This pushes an integer-valued item onto the failure stack.
1153    Assumes the variable `fail_stack'.  Probably should only
1154    be called from within `PUSH_FAILURE_POINT'.  */
1155 #define PUSH_FAILURE_INT(item)                                  \
1156   fail_stack.stack[fail_stack.avail++].integer = (item)
1157
1158 /* Push a fail_stack_elt_t value onto the failure stack.
1159    Assumes the variable `fail_stack'.  Probably should only
1160    be called from within `PUSH_FAILURE_POINT'.  */
1161 #define PUSH_FAILURE_ELT(item)                                  \
1162   fail_stack.stack[fail_stack.avail++] =  (item)
1163
1164 /* These three POP... operations complement the three PUSH... operations.
1165    All assume that `fail_stack' is nonempty.  */
1166 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1167 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1168 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1169
1170 /* Used to omit pushing failure point id's when we're not debugging.  */
1171 #ifdef DEBUG
1172 #define DEBUG_PUSH PUSH_FAILURE_INT
1173 #define DEBUG_POP(item_addr) (item_addr)->integer = POP_FAILURE_INT ()
1174 #else
1175 #define DEBUG_PUSH(item)
1176 #define DEBUG_POP(item_addr)
1177 #endif
1178
1179
1180 /* Push the information about the state we will need
1181    if we ever fail back to it.
1182
1183    Requires variables fail_stack, regstart, regend, reg_info, and
1184    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
1185    declared.
1186
1187    Does `return FAILURE_CODE' if runs out of memory.  */
1188
1189 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
1190   do {                                                                  \
1191     char *destination;                                                  \
1192     /* Must be int, so when we don't save any registers, the arithmetic \
1193        of 0 + -1 isn't done as unsigned.  */                            \
1194     /* Can't be int, since there is not a shred of a guarantee that int \
1195        is wide enough to hold a value of something to which pointer can \
1196        be assigned */                                                   \
1197     s_reg_t this_reg;                                                   \
1198                                                                         \
1199     DEBUG_STATEMENT (failure_id++);                                     \
1200     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1201     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1202     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1203     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1204                                                                         \
1205     DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);           \
1206     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1207                                                                         \
1208     /* Ensure we have enough space allocated for what we will push.  */ \
1209     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1210       {                                                                 \
1211         if (!DOUBLE_FAIL_STACK (fail_stack))                            \
1212           return failure_code;                                          \
1213                                                                         \
1214         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1215                        (fail_stack).size);                              \
1216         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1217       }                                                                 \
1218                                                                         \
1219     /* Push the info, starting with the registers.  */                  \
1220     DEBUG_PRINT1 ("\n");                                                \
1221                                                                         \
1222     if (1)                                                              \
1223       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1224            this_reg++)                                                  \
1225         {                                                               \
1226           DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);               \
1227           DEBUG_STATEMENT (num_regs_pushed++);                          \
1228                                                                         \
1229           DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);       \
1230           PUSH_FAILURE_POINTER (regstart[this_reg]);                    \
1231                                                                         \
1232           DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);           \
1233           PUSH_FAILURE_POINTER (regend[this_reg]);                      \
1234                                                                         \
1235           DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);  \
1236           DEBUG_PRINT2 (" match_null=%d",                               \
1237                         REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
1238           DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
1239           DEBUG_PRINT2 (" matched_something=%d",                        \
1240                         MATCHED_SOMETHING (reg_info[this_reg]));        \
1241           DEBUG_PRINT2 (" ever_matched=%d",                             \
1242                         EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
1243           DEBUG_PRINT1 ("\n");                                          \
1244           PUSH_FAILURE_ELT (reg_info[this_reg].word);                   \
1245         }                                                               \
1246                                                                         \
1247     DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
1248     PUSH_FAILURE_INT (lowest_active_reg);                               \
1249                                                                         \
1250     DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
1251     PUSH_FAILURE_INT (highest_active_reg);                              \
1252                                                                         \
1253     DEBUG_PRINT2 ("  Pushing pattern 0x%x:\n", pattern_place);          \
1254     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1255     PUSH_FAILURE_POINTER (pattern_place);                               \
1256                                                                         \
1257     DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);            \
1258     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1259                                  size2);                                \
1260     DEBUG_PRINT1 ("'\n");                                               \
1261     PUSH_FAILURE_POINTER (string_place);                                \
1262                                                                         \
1263     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1264     DEBUG_PUSH (failure_id);                                            \
1265   } while (0)
1266
1267 /* This is the number of items that are pushed and popped on the stack
1268    for each register.  */
1269 #define NUM_REG_ITEMS  3
1270
1271 /* Individual items aside from the registers.  */
1272 #ifdef DEBUG
1273 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1274 #else
1275 #define NUM_NONREG_ITEMS 4
1276 #endif
1277
1278 /* We push at most this many items on the stack.  */
1279 /* We used to use (num_regs - 1), which is the number of registers
1280    this regexp will save; but that was changed to 5
1281    to avoid stack overflow for a regexp with lots of parens.  */
1282 #define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1283
1284 /* We actually push this many items.  */
1285 #define NUM_FAILURE_ITEMS                               \
1286   (((0                                                  \
1287      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
1288     * NUM_REG_ITEMS)                                    \
1289    + NUM_NONREG_ITEMS)
1290
1291 /* How many items can still be added to the stack without overflowing it.  */
1292 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1293
1294
1295 /* Pops what PUSH_FAIL_STACK pushes.
1296
1297    We restore into the parameters, all of which should be lvalues:
1298      STR -- the saved data position.
1299      PAT -- the saved pattern position.
1300      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1301      REGSTART, REGEND -- arrays of string positions.
1302      REG_INFO -- array of information about each subexpression.
1303
1304    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1305    `pend', `string1', `size1', `string2', and `size2'.  */
1306
1307 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1308 {                                                                       \
1309   DEBUG_STATEMENT (fail_stack_elt_t failure_id;)                        \
1310   s_reg_t this_reg;                                                     \
1311   const unsigned char *string_temp;                                     \
1312                                                                         \
1313   assert (!FAIL_STACK_EMPTY ());                                        \
1314                                                                         \
1315   /* Remove failure points and point to how many regs pushed.  */       \
1316   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1317   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1318   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1319                                                                         \
1320   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1321                                                                         \
1322   DEBUG_POP (&failure_id);                                              \
1323   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1324                                                                         \
1325   /* If the saved string location is NULL, it came from an              \
1326      on_failure_keep_string_jump opcode, and we want to throw away the  \
1327      saved NULL, thus retaining our current position in the string.  */ \
1328   string_temp = POP_FAILURE_POINTER ();                                 \
1329   if (string_temp != NULL)                                              \
1330     str = (const char *) string_temp;                                   \
1331                                                                         \
1332   DEBUG_PRINT2 ("  Popping string 0x%x: `", str);                       \
1333   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1334   DEBUG_PRINT1 ("'\n");                                                 \
1335                                                                         \
1336   pat = (unsigned char *) POP_FAILURE_POINTER ();                       \
1337   DEBUG_PRINT2 ("  Popping pattern 0x%x:\n", pat);                      \
1338   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1339                                                                         \
1340   /* Restore register info.  */                                         \
1341   high_reg = (active_reg_t) POP_FAILURE_INT ();                         \
1342   DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);           \
1343                                                                         \
1344   low_reg = (active_reg_t) POP_FAILURE_INT ();                          \
1345   DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);            \
1346                                                                         \
1347   if (1)                                                                \
1348     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)          \
1349       {                                                                 \
1350         DEBUG_PRINT2 ("    Popping reg: %d\n", this_reg);               \
1351                                                                         \
1352         reg_info[this_reg].word = POP_FAILURE_ELT ();                   \
1353         DEBUG_PRINT2 ("      info: 0x%x\n", reg_info[this_reg]);        \
1354                                                                         \
1355         regend[this_reg] = (const char *) POP_FAILURE_POINTER ();       \
1356         DEBUG_PRINT2 ("      end: 0x%x\n", regend[this_reg]);           \
1357                                                                         \
1358         regstart[this_reg] = (const char *) POP_FAILURE_POINTER ();     \
1359         DEBUG_PRINT2 ("      start: 0x%x\n", regstart[this_reg]);       \
1360       }                                                                 \
1361   else                                                                  \
1362     {                                                                   \
1363       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1364         {                                                               \
1365           reg_info[this_reg].word.integer = 0;                          \
1366           regend[this_reg] = 0;                                         \
1367           regstart[this_reg] = 0;                                       \
1368         }                                                               \
1369       highest_active_reg = high_reg;                                    \
1370     }                                                                   \
1371                                                                         \
1372   set_regs_matched_done = 0;                                            \
1373   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1374 } /* POP_FAILURE_POINT */
1375
1376
1377 \f
1378 /* Structure for per-register (a.k.a. per-group) information.
1379    Other register information, such as the
1380    starting and ending positions (which are addresses), and the list of
1381    inner groups (which is a bits list) are maintained in separate
1382    variables.
1383
1384    We are making a (strictly speaking) nonportable assumption here: that
1385    the compiler will pack our bit fields into something that fits into
1386    the type of `word', i.e., is something that fits into one item on the
1387    failure stack.  */
1388
1389
1390 /* Declarations and macros for re_match_2.  */
1391
1392 typedef union
1393 {
1394   fail_stack_elt_t word;
1395   struct
1396   {
1397       /* This field is one if this group can match the empty string,
1398          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1399 #define MATCH_NULL_UNSET_VALUE 3
1400     unsigned match_null_string_p : 2;
1401     unsigned is_active : 1;
1402     unsigned matched_something : 1;
1403     unsigned ever_matched_something : 1;
1404   } bits;
1405 } register_info_type;
1406
1407 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1408 #define IS_ACTIVE(R)  ((R).bits.is_active)
1409 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1410 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1411
1412
1413 /* Call this when have matched a real character; it sets `matched' flags
1414    for the subexpressions which we are currently inside.  Also records
1415    that those subexprs have matched.  */
1416 #define SET_REGS_MATCHED()                                              \
1417   do                                                                    \
1418     {                                                                   \
1419       if (!set_regs_matched_done)                                       \
1420         {                                                               \
1421           active_reg_t r;                                               \
1422           set_regs_matched_done = 1;                                    \
1423           for (r = lowest_active_reg; r <= highest_active_reg; r++)     \
1424             {                                                           \
1425               MATCHED_SOMETHING (reg_info[r])                           \
1426                 = EVER_MATCHED_SOMETHING (reg_info[r])                  \
1427                 = 1;                                                    \
1428             }                                                           \
1429         }                                                               \
1430     }                                                                   \
1431   while (0)
1432
1433 /* Registers are set to a sentinel when they haven't yet matched.  */
1434 static char reg_unset_dummy;
1435 #define REG_UNSET_VALUE (&reg_unset_dummy)
1436 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1437 \f
1438 /* Subroutine declarations and macros for regex_compile.  */
1439
1440 static reg_errcode_t regex_compile _RE_ARGS ((const char *pattern, size_t size,
1441                                               reg_syntax_t syntax,
1442                                               struct re_pattern_buffer *bufp));
1443 static void store_op1 _RE_ARGS ((re_opcode_t op, unsigned char *loc, int arg));
1444 static void store_op2 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1445                                  int arg1, int arg2));
1446 static void insert_op1 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1447                                   int arg, unsigned char *end));
1448 static void insert_op2 _RE_ARGS ((re_opcode_t op, unsigned char *loc,
1449                                   int arg1, int arg2, unsigned char *end));
1450 static boolean at_begline_loc_p _RE_ARGS ((const char *pattern, const char *p,
1451                                            reg_syntax_t syntax));
1452 static boolean at_endline_loc_p _RE_ARGS ((const char *p, const char *pend,
1453                                            reg_syntax_t syntax));
1454 static reg_errcode_t compile_range _RE_ARGS ((const char **p_ptr,
1455                                               const char *pend,
1456                                               char *translate,
1457                                               reg_syntax_t syntax,
1458                                               unsigned char *b));
1459
1460 /* Fetch the next character in the uncompiled pattern---translating it
1461    if necessary.  Also cast from a signed character in the constant
1462    string passed to us by the user to an unsigned char that we can use
1463    as an array index (in, e.g., `translate').  */
1464 #ifndef PATFETCH
1465 #define PATFETCH(c)                                                     \
1466   do {if (p == pend) return REG_EEND;                                   \
1467     c = (unsigned char) *p++;                                           \
1468     if (translate) c = (unsigned char) translate[c];                    \
1469   } while (0)
1470 #endif
1471
1472 /* Fetch the next character in the uncompiled pattern, with no
1473    translation.  */
1474 #define PATFETCH_RAW(c)                                                 \
1475   do {if (p == pend) return REG_EEND;                                   \
1476     c = (unsigned char) *p++;                                           \
1477   } while (0)
1478
1479 /* Go backwards one character in the pattern.  */
1480 #define PATUNFETCH p--
1481
1482
1483 /* If `translate' is non-null, return translate[D], else just D.  We
1484    cast the subscript to translate because some data is declared as
1485    `char *', to avoid warnings when a string constant is passed.  But
1486    when we use a character as a subscript we must make it unsigned.  */
1487 #ifndef TRANSLATE
1488 #define TRANSLATE(d) \
1489   (translate ? (char) translate[(unsigned char) (d)] : (d))
1490 #endif
1491
1492
1493 /* Macros for outputting the compiled pattern into `buffer'.  */
1494
1495 /* If the buffer isn't allocated when it comes in, use this.  */
1496 #define INIT_BUF_SIZE  32
1497
1498 /* Make sure we have at least N more bytes of space in buffer.  */
1499 #define GET_BUFFER_SPACE(n)                                             \
1500     while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)  \
1501       EXTEND_BUFFER ()
1502
1503 /* Make sure we have one more byte of buffer space and then add C to it.  */
1504 #define BUF_PUSH(c)                                                     \
1505   do {                                                                  \
1506     GET_BUFFER_SPACE (1);                                               \
1507     *b++ = (unsigned char) (c);                                         \
1508   } while (0)
1509
1510
1511 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
1512 #define BUF_PUSH_2(c1, c2)                                              \
1513   do {                                                                  \
1514     GET_BUFFER_SPACE (2);                                               \
1515     *b++ = (unsigned char) (c1);                                        \
1516     *b++ = (unsigned char) (c2);                                        \
1517   } while (0)
1518
1519
1520 /* As with BUF_PUSH_2, except for three bytes.  */
1521 #define BUF_PUSH_3(c1, c2, c3)                                          \
1522   do {                                                                  \
1523     GET_BUFFER_SPACE (3);                                               \
1524     *b++ = (unsigned char) (c1);                                        \
1525     *b++ = (unsigned char) (c2);                                        \
1526     *b++ = (unsigned char) (c3);                                        \
1527   } while (0)
1528
1529
1530 /* Store a jump with opcode OP at LOC to location TO.  We store a
1531    relative address offset by the three bytes the jump itself occupies.  */
1532 #define STORE_JUMP(op, loc, to) \
1533   store_op1 (op, loc, (int) ((to) - (loc) - 3))
1534
1535 /* Likewise, for a two-argument jump.  */
1536 #define STORE_JUMP2(op, loc, to, arg) \
1537   store_op2 (op, loc, (int) ((to) - (loc) - 3), arg)
1538
1539 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
1540 #define INSERT_JUMP(op, loc, to) \
1541   insert_op1 (op, loc, (int) ((to) - (loc) - 3), b)
1542
1543 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
1544 #define INSERT_JUMP2(op, loc, to, arg) \
1545   insert_op2 (op, loc, (int) ((to) - (loc) - 3), arg, b)
1546
1547
1548 /* This is not an arbitrary limit: the arguments which represent offsets
1549    into the pattern are two bytes long.  So if 2^16 bytes turns out to
1550    be too small, many things would have to change.  */
1551 /* Any other compiler which, like MSC, has allocation limit below 2^16
1552    bytes will have to use approach similar to what was done below for
1553    MSC and drop MAX_BUF_SIZE a bit.  Otherwise you may end up
1554    reallocating to 0 bytes.  Such thing is not going to work too well.
1555    You have been warned!!  */
1556 #ifdef _MSC_VER
1557 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
1558    The REALLOC define eliminates a flurry of conversion warnings,
1559    but is not required. */
1560 #define MAX_BUF_SIZE  65500L
1561 #define REALLOC(p,s) realloc ((p), (size_t) (s))
1562 #else
1563 #define MAX_BUF_SIZE (1L << 16)
1564 #define REALLOC(p,s) realloc ((p), (s))
1565 #endif
1566
1567 /* Extend the buffer by twice its current size via realloc and
1568    reset the pointers that pointed into the old block to point to the
1569    correct places in the new one.  If extending the buffer results in it
1570    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
1571 #define EXTEND_BUFFER()                                                 \
1572   do {                                                                  \
1573     unsigned char *old_buffer = bufp->buffer;                           \
1574     if (bufp->allocated == MAX_BUF_SIZE)                                \
1575       return REG_ESIZE;                                                 \
1576     bufp->allocated <<= 1;                                              \
1577     if (bufp->allocated > MAX_BUF_SIZE)                                 \
1578       bufp->allocated = MAX_BUF_SIZE;                                   \
1579     bufp->buffer = (unsigned char *) REALLOC (bufp->buffer, bufp->allocated);\
1580     if (bufp->buffer == NULL)                                           \
1581       return REG_ESPACE;                                                \
1582     /* If the buffer moved, move all the pointers into it.  */          \
1583     if (old_buffer != bufp->buffer)                                     \
1584       {                                                                 \
1585         b = (b - old_buffer) + bufp->buffer;                            \
1586         begalt = (begalt - old_buffer) + bufp->buffer;                  \
1587         if (fixup_alt_jump)                                             \
1588           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
1589         if (laststart)                                                  \
1590           laststart = (laststart - old_buffer) + bufp->buffer;          \
1591         if (pending_exact)                                              \
1592           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
1593       }                                                                 \
1594   } while (0)
1595
1596
1597 /* Since we have one byte reserved for the register number argument to
1598    {start,stop}_memory, the maximum number of groups we can report
1599    things about is what fits in that byte.  */
1600 #define MAX_REGNUM 255
1601
1602 /* But patterns can have more than `MAX_REGNUM' registers.  We just
1603    ignore the excess.  */
1604 typedef unsigned regnum_t;
1605
1606
1607 /* Macros for the compile stack.  */
1608
1609 /* Since offsets can go either forwards or backwards, this type needs to
1610    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
1611 /* int may be not enough when sizeof(int) == 2.  */
1612 typedef long pattern_offset_t;
1613
1614 typedef struct
1615 {
1616   pattern_offset_t begalt_offset;
1617   pattern_offset_t fixup_alt_jump;
1618   pattern_offset_t inner_group_offset;
1619   pattern_offset_t laststart_offset;
1620   regnum_t regnum;
1621 } compile_stack_elt_t;
1622
1623
1624 typedef struct
1625 {
1626   compile_stack_elt_t *stack;
1627   unsigned size;
1628   unsigned avail;                       /* Offset of next open position.  */
1629 } compile_stack_type;
1630
1631
1632 #define INIT_COMPILE_STACK_SIZE 32
1633
1634 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
1635 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
1636
1637 /* The next available element.  */
1638 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1639
1640
1641 /* Set the bit for character C in a list.  */
1642 #define SET_LIST_BIT(c)                               \
1643   (b[((unsigned char) (c)) / BYTEWIDTH]               \
1644    |= 1 << (((unsigned char) c) % BYTEWIDTH))
1645
1646
1647 /* Get the next unsigned number in the uncompiled pattern.  */
1648 #define GET_UNSIGNED_NUMBER(num)                                        \
1649   { if (p != pend)                                                      \
1650      {                                                                  \
1651        PATFETCH (c);                                                    \
1652        while (ISDIGIT (c))                                              \
1653          {                                                              \
1654            if (num < 0)                                                 \
1655               num = 0;                                                  \
1656            num = num * 10 + c - '0';                                    \
1657            if (p == pend)                                               \
1658               break;                                                    \
1659            PATFETCH (c);                                                \
1660          }                                                              \
1661        }                                                                \
1662     }
1663
1664 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
1665
1666 #define IS_CHAR_CLASS(string)                                           \
1667    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
1668     || STREQ (string, "lower") || STREQ (string, "digit")               \
1669     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
1670     || STREQ (string, "space") || STREQ (string, "print")               \
1671     || STREQ (string, "punct") || STREQ (string, "graph")               \
1672     || STREQ (string, "cntrl") || STREQ (string, "blank"))
1673 \f
1674 #ifndef MATCH_MAY_ALLOCATE
1675
1676 /* If we cannot allocate large objects within re_match_2_internal,
1677    we make the fail stack and register vectors global.
1678    The fail stack, we grow to the maximum size when a regexp
1679    is compiled.
1680    The register vectors, we adjust in size each time we
1681    compile a regexp, according to the number of registers it needs.  */
1682
1683 static fail_stack_type fail_stack;
1684
1685 /* Size with which the following vectors are currently allocated.
1686    That is so we can make them bigger as needed,
1687    but never make them smaller.  */
1688 static int regs_allocated_size;
1689
1690 static const char **     regstart, **     regend;
1691 static const char ** old_regstart, ** old_regend;
1692 static const char **best_regstart, **best_regend;
1693 static register_info_type *reg_info;
1694 static const char **reg_dummy;
1695 static register_info_type *reg_info_dummy;
1696
1697 /* Make the register vectors big enough for NUM_REGS registers,
1698    but don't make them smaller.  */
1699
1700 static
1701 regex_grow_registers (num_regs)
1702      int num_regs;
1703 {
1704   if (num_regs > regs_allocated_size)
1705     {
1706       RETALLOC_IF (regstart,     num_regs, const char *);
1707       RETALLOC_IF (regend,       num_regs, const char *);
1708       RETALLOC_IF (old_regstart, num_regs, const char *);
1709       RETALLOC_IF (old_regend,   num_regs, const char *);
1710       RETALLOC_IF (best_regstart, num_regs, const char *);
1711       RETALLOC_IF (best_regend,  num_regs, const char *);
1712       RETALLOC_IF (reg_info,     num_regs, register_info_type);
1713       RETALLOC_IF (reg_dummy,    num_regs, const char *);
1714       RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
1715
1716       regs_allocated_size = num_regs;
1717     }
1718 }
1719
1720 #endif /* not MATCH_MAY_ALLOCATE */
1721 \f
1722 static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
1723                                                  compile_stack,
1724                                                  regnum_t regnum));
1725
1726 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1727    Returns one of error codes defined in `regex.h', or zero for success.
1728
1729    Assumes the `allocated' (and perhaps `buffer') and `translate'
1730    fields are set in BUFP on entry.
1731
1732    If it succeeds, results are put in BUFP (if it returns an error, the
1733    contents of BUFP are undefined):
1734      `buffer' is the compiled pattern;
1735      `syntax' is set to SYNTAX;
1736      `used' is set to the length of the compiled pattern;
1737      `fastmap_accurate' is zero;
1738      `re_nsub' is the number of subexpressions in PATTERN;
1739      `not_bol' and `not_eol' are zero;
1740
1741    The `fastmap' and `newline_anchor' fields are neither
1742    examined nor set.  */
1743
1744 /* Return, freeing storage we allocated.  */
1745 #define FREE_STACK_RETURN(value)                \
1746   return (free (compile_stack.stack), value)
1747
1748 static reg_errcode_t
1749 regex_compile (pattern, size, syntax, bufp)
1750      const char *pattern;
1751      size_t size;
1752      reg_syntax_t syntax;
1753      struct re_pattern_buffer *bufp;
1754 {
1755   /* We fetch characters from PATTERN here.  Even though PATTERN is
1756      `char *' (i.e., signed), we declare these variables as unsigned, so
1757      they can be reliably used as array indices.  */
1758   register unsigned char c, c1;
1759
1760   /* A random temporary spot in PATTERN.  */
1761   const char *p1;
1762
1763   /* Points to the end of the buffer, where we should append.  */
1764   register unsigned char *b;
1765
1766   /* Keeps track of unclosed groups.  */
1767   compile_stack_type compile_stack;
1768
1769   /* Points to the current (ending) position in the pattern.  */
1770   const char *p = pattern;
1771   const char *pend = pattern + size;
1772
1773   /* How to translate the characters in the pattern.  */
1774   RE_TRANSLATE_TYPE translate = bufp->translate;
1775
1776   /* Address of the count-byte of the most recently inserted `exactn'
1777      command.  This makes it possible to tell if a new exact-match
1778      character can be added to that command or if the character requires
1779      a new `exactn' command.  */
1780   unsigned char *pending_exact = 0;
1781
1782   /* Address of start of the most recently finished expression.
1783      This tells, e.g., postfix * where to find the start of its
1784      operand.  Reset at the beginning of groups and alternatives.  */
1785   unsigned char *laststart = 0;
1786
1787   /* Address of beginning of regexp, or inside of last group.  */
1788   unsigned char *begalt;
1789
1790   /* Place in the uncompiled pattern (i.e., the {) to
1791      which to go back if the interval is invalid.  */
1792   const char *beg_interval;
1793
1794   /* Address of the place where a forward jump should go to the end of
1795      the containing expression.  Each alternative of an `or' -- except the
1796      last -- ends with a forward jump of this sort.  */
1797   unsigned char *fixup_alt_jump = 0;
1798
1799   /* Counts open-groups as they are encountered.  Remembered for the
1800      matching close-group on the compile stack, so the same register
1801      number is put in the stop_memory as the start_memory.  */
1802   regnum_t regnum = 0;
1803
1804 #ifdef DEBUG
1805   DEBUG_PRINT1 ("\nCompiling pattern: ");
1806   if (debug)
1807     {
1808       unsigned debug_count;
1809
1810       for (debug_count = 0; debug_count < size; debug_count++)
1811         putchar (pattern[debug_count]);
1812       putchar ('\n');
1813     }
1814 #endif /* DEBUG */
1815
1816   /* Initialize the compile stack.  */
1817   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1818   if (compile_stack.stack == NULL)
1819     return REG_ESPACE;
1820
1821   compile_stack.size = INIT_COMPILE_STACK_SIZE;
1822   compile_stack.avail = 0;
1823
1824   /* Initialize the pattern buffer.  */
1825   bufp->syntax = syntax;
1826   bufp->fastmap_accurate = 0;
1827   bufp->not_bol = bufp->not_eol = 0;
1828
1829   /* Set `used' to zero, so that if we return an error, the pattern
1830      printer (for debugging) will think there's no pattern.  We reset it
1831      at the end.  */
1832   bufp->used = 0;
1833
1834   /* Always count groups, whether or not bufp->no_sub is set.  */
1835   bufp->re_nsub = 0;
1836
1837 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1838   /* Initialize the syntax table.  */
1839    init_syntax_once ();
1840 #endif
1841
1842   if (bufp->allocated == 0)
1843     {
1844       if (bufp->buffer)
1845         { /* If zero allocated, but buffer is non-null, try to realloc
1846              enough space.  This loses if buffer's address is bogus, but
1847              that is the user's responsibility.  */
1848           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1849         }
1850       else
1851         { /* Caller did not allocate a buffer.  Do it for them.  */
1852           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1853         }
1854       if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE);
1855
1856       bufp->allocated = INIT_BUF_SIZE;
1857     }
1858
1859   begalt = b = bufp->buffer;
1860
1861   /* Loop through the uncompiled pattern until we're at the end.  */
1862   while (p != pend)
1863     {
1864       PATFETCH (c);
1865
1866       switch (c)
1867         {
1868         case '^':
1869           {
1870             if (   /* If at start of pattern, it's an operator.  */
1871                    p == pattern + 1
1872                    /* If context independent, it's an operator.  */
1873                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1874                    /* Otherwise, depends on what's come before.  */
1875                 || at_begline_loc_p (pattern, p, syntax))
1876               BUF_PUSH (begline);
1877             else
1878               goto normal_char;
1879           }
1880           break;
1881
1882
1883         case '$':
1884           {
1885             if (   /* If at end of pattern, it's an operator.  */
1886                    p == pend
1887                    /* If context independent, it's an operator.  */
1888                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1889                    /* Otherwise, depends on what's next.  */
1890                 || at_endline_loc_p (p, pend, syntax))
1891                BUF_PUSH (endline);
1892              else
1893                goto normal_char;
1894            }
1895            break;
1896
1897
1898         case '+':
1899         case '?':
1900           if ((syntax & RE_BK_PLUS_QM)
1901               || (syntax & RE_LIMITED_OPS))
1902             goto normal_char;
1903         handle_plus:
1904         case '*':
1905           /* If there is no previous pattern... */
1906           if (!laststart)
1907             {
1908               if (syntax & RE_CONTEXT_INVALID_OPS)
1909                 FREE_STACK_RETURN (REG_BADRPT);
1910               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1911                 goto normal_char;
1912             }
1913
1914           {
1915             /* Are we optimizing this jump?  */
1916             boolean keep_string_p = false;
1917
1918             /* 1 means zero (many) matches is allowed.  */
1919             char zero_times_ok = 0, many_times_ok = 0;
1920
1921             /* If there is a sequence of repetition chars, collapse it
1922                down to just one (the right one).  We can't combine
1923                interval operators with these because of, e.g., `a{2}*',
1924                which should only match an even number of `a's.  */
1925
1926             for (;;)
1927               {
1928                 zero_times_ok |= c != '+';
1929                 many_times_ok |= c != '?';
1930
1931                 if (p == pend)
1932                   break;
1933
1934                 PATFETCH (c);
1935
1936                 if (c == '*'
1937                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1938                   ;
1939
1940                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
1941                   {
1942                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
1943
1944                     PATFETCH (c1);
1945                     if (!(c1 == '+' || c1 == '?'))
1946                       {
1947                         PATUNFETCH;
1948                         PATUNFETCH;
1949                         break;
1950                       }
1951
1952                     c = c1;
1953                   }
1954                 else
1955                   {
1956                     PATUNFETCH;
1957                     break;
1958                   }
1959
1960                 /* If we get here, we found another repeat character.  */
1961                }
1962
1963             /* Star, etc. applied to an empty pattern is equivalent
1964                to an empty pattern.  */
1965             if (!laststart)
1966               break;
1967
1968             /* Now we know whether or not zero matches is allowed
1969                and also whether or not two or more matches is allowed.  */
1970             if (many_times_ok)
1971               { /* More than one repetition is allowed, so put in at the
1972                    end a backward relative jump from `b' to before the next
1973                    jump we're going to put in below (which jumps from
1974                    laststart to after this jump).
1975
1976                    But if we are at the `*' in the exact sequence `.*\n',
1977                    insert an unconditional jump backwards to the .,
1978                    instead of the beginning of the loop.  This way we only
1979                    push a failure point once, instead of every time
1980                    through the loop.  */
1981                 assert (p - 1 > pattern);
1982
1983                 /* Allocate the space for the jump.  */
1984                 GET_BUFFER_SPACE (3);
1985
1986                 /* We know we are not at the first character of the pattern,
1987                    because laststart was nonzero.  And we've already
1988                    incremented `p', by the way, to be the character after
1989                    the `*'.  Do we have to do something analogous here
1990                    for null bytes, because of RE_DOT_NOT_NULL?  */
1991                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
1992                     && zero_times_ok
1993                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
1994                     && !(syntax & RE_DOT_NEWLINE))
1995                   { /* We have .*\n.  */
1996                     STORE_JUMP (jump, b, laststart);
1997                     keep_string_p = true;
1998                   }
1999                 else
2000                   /* Anything else.  */
2001                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
2002
2003                 /* We've added more stuff to the buffer.  */
2004                 b += 3;
2005               }
2006
2007             /* On failure, jump from laststart to b + 3, which will be the
2008                end of the buffer after this jump is inserted.  */
2009             GET_BUFFER_SPACE (3);
2010             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2011                                        : on_failure_jump,
2012                          laststart, b + 3);
2013             pending_exact = 0;
2014             b += 3;
2015
2016             if (!zero_times_ok)
2017               {
2018                 /* At least one repetition is required, so insert a
2019                    `dummy_failure_jump' before the initial
2020                    `on_failure_jump' instruction of the loop. This
2021                    effects a skip over that instruction the first time
2022                    we hit that loop.  */
2023                 GET_BUFFER_SPACE (3);
2024                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
2025                 b += 3;
2026               }
2027             }
2028           break;
2029
2030
2031         case '.':
2032           laststart = b;
2033           BUF_PUSH (anychar);
2034           break;
2035
2036
2037         case '[':
2038           {
2039             boolean had_char_class = false;
2040
2041             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2042
2043             /* Ensure that we have enough space to push a charset: the
2044                opcode, the length count, and the bitset; 34 bytes in all.  */
2045             GET_BUFFER_SPACE (34);
2046
2047             laststart = b;
2048
2049             /* We test `*p == '^' twice, instead of using an if
2050                statement, so we only need one BUF_PUSH.  */
2051             BUF_PUSH (*p == '^' ? charset_not : charset);
2052             if (*p == '^')
2053               p++;
2054
2055             /* Remember the first position in the bracket expression.  */
2056             p1 = p;
2057
2058             /* Push the number of bytes in the bitmap.  */
2059             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
2060
2061             /* Clear the whole map.  */
2062             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
2063
2064             /* charset_not matches newline according to a syntax bit.  */
2065             if ((re_opcode_t) b[-2] == charset_not
2066                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2067               SET_LIST_BIT ('\n');
2068
2069             /* Read in characters and ranges, setting map bits.  */
2070             for (;;)
2071               {
2072                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2073
2074                 PATFETCH (c);
2075
2076                 /* \ might escape characters inside [...] and [^...].  */
2077                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2078                   {
2079                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2080
2081                     PATFETCH (c1);
2082                     SET_LIST_BIT (c1);
2083                     continue;
2084                   }
2085
2086                 /* Could be the end of the bracket expression.  If it's
2087                    not (i.e., when the bracket expression is `[]' so
2088                    far), the ']' character bit gets set way below.  */
2089                 if (c == ']' && p != p1 + 1)
2090                   break;
2091
2092                 /* Look ahead to see if it's a range when the last thing
2093                    was a character class.  */
2094                 if (had_char_class && c == '-' && *p != ']')
2095                   FREE_STACK_RETURN (REG_ERANGE);
2096
2097                 /* Look ahead to see if it's a range when the last thing
2098                    was a character: if this is a hyphen not at the
2099                    beginning or the end of a list, then it's the range
2100                    operator.  */
2101                 if (c == '-'
2102                     && !(p - 2 >= pattern && p[-2] == '[')
2103                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2104                     && *p != ']')
2105                   {
2106                     reg_errcode_t ret
2107                       = compile_range (&p, pend, translate, syntax, b);
2108                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2109                   }
2110
2111                 else if (p[0] == '-' && p[1] != ']')
2112                   { /* This handles ranges made up of characters only.  */
2113                     reg_errcode_t ret;
2114
2115                     /* Move past the `-'.  */
2116                     PATFETCH (c1);
2117
2118                     ret = compile_range (&p, pend, translate, syntax, b);
2119                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2120                   }
2121
2122                 /* See if we're at the beginning of a possible character
2123                    class.  */
2124
2125                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2126                   { /* Leave room for the null.  */
2127                     char str[CHAR_CLASS_MAX_LENGTH + 1];
2128
2129                     PATFETCH (c);
2130                     c1 = 0;
2131
2132                     /* If pattern is `[[:'.  */
2133                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2134
2135                     for (;;)
2136                       {
2137                         PATFETCH (c);
2138                         if (c == ':' || c == ']' || p == pend
2139                             || c1 == CHAR_CLASS_MAX_LENGTH)
2140                           break;
2141                         str[c1++] = c;
2142                       }
2143                     str[c1] = '\0';
2144
2145                     /* If isn't a word bracketed by `[:' and:`]':
2146                        undo the ending character, the letters, and leave
2147                        the leading `:' and `[' (but set bits for them).  */
2148                     if (c == ':' && *p == ']')
2149                       {
2150                         int ch;
2151                         boolean is_alnum = STREQ (str, "alnum");
2152                         boolean is_alpha = STREQ (str, "alpha");
2153                         boolean is_blank = STREQ (str, "blank");
2154                         boolean is_cntrl = STREQ (str, "cntrl");
2155                         boolean is_digit = STREQ (str, "digit");
2156                         boolean is_graph = STREQ (str, "graph");
2157                         boolean is_lower = STREQ (str, "lower");
2158                         boolean is_print = STREQ (str, "print");
2159                         boolean is_punct = STREQ (str, "punct");
2160                         boolean is_space = STREQ (str, "space");
2161                         boolean is_upper = STREQ (str, "upper");
2162                         boolean is_xdigit = STREQ (str, "xdigit");
2163
2164                         if (!IS_CHAR_CLASS (str))
2165                           FREE_STACK_RETURN (REG_ECTYPE);
2166
2167                         /* Throw away the ] at the end of the character
2168                            class.  */
2169                         PATFETCH (c);
2170
2171                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2172
2173                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
2174                           {
2175                             /* This was split into 3 if's to
2176                                avoid an arbitrary limit in some compiler.  */
2177                             if (   (is_alnum  && ISALNUM (ch))
2178                                 || (is_alpha  && ISALPHA (ch))
2179                                 || (is_blank  && ISBLANK (ch))
2180                                 || (is_cntrl  && ISCNTRL (ch)))
2181                               SET_LIST_BIT (ch);
2182                             if (   (is_digit  && ISDIGIT (ch))
2183                                 || (is_graph  && ISGRAPH (ch))
2184                                 || (is_lower  && ISLOWER (ch))
2185                                 || (is_print  && ISPRINT (ch)))
2186                               SET_LIST_BIT (ch);
2187                             if (   (is_punct  && ISPUNCT (ch))
2188                                 || (is_space  && ISSPACE (ch))
2189                                 || (is_upper  && ISUPPER (ch))
2190                                 || (is_xdigit && ISXDIGIT (ch)))
2191                               SET_LIST_BIT (ch);
2192                             if (   translate && (is_upper || is_lower)
2193                                 && (ISUPPER (ch) || ISLOWER (ch)))
2194                               SET_LIST_BIT (ch);
2195                           }
2196                         had_char_class = true;
2197                       }
2198                     else
2199                       {
2200                         c1++;
2201                         while (c1--)
2202                           PATUNFETCH;
2203                         SET_LIST_BIT ('[');
2204                         SET_LIST_BIT (':');
2205                         had_char_class = false;
2206                       }
2207                   }
2208                 else
2209                   {
2210                     had_char_class = false;
2211                     SET_LIST_BIT (c);
2212                   }
2213               }
2214
2215             /* Discard any (non)matching list bytes that are all 0 at the
2216                end of the map.  Decrease the map-length byte too.  */
2217             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
2218               b[-1]--;
2219             b += b[-1];
2220           }
2221           break;
2222
2223
2224         case '(':
2225           if (syntax & RE_NO_BK_PARENS)
2226             goto handle_open;
2227           else
2228             goto normal_char;
2229
2230
2231         case ')':
2232           if (syntax & RE_NO_BK_PARENS)
2233             goto handle_close;
2234           else
2235             goto normal_char;
2236
2237
2238         case '\n':
2239           if (syntax & RE_NEWLINE_ALT)
2240             goto handle_alt;
2241           else
2242             goto normal_char;
2243
2244
2245         case '|':
2246           if (syntax & RE_NO_BK_VBAR)
2247             goto handle_alt;
2248           else
2249             goto normal_char;
2250
2251
2252         case '{':
2253            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
2254              goto handle_interval;
2255            else
2256              goto normal_char;
2257
2258
2259         case '\\':
2260           if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2261
2262           /* Do not translate the character after the \, so that we can
2263              distinguish, e.g., \B from \b, even if we normally would
2264              translate, e.g., B to b.  */
2265           PATFETCH_RAW (c);
2266
2267           switch (c)
2268             {
2269             case '(':
2270               if (syntax & RE_NO_BK_PARENS)
2271                 goto normal_backslash;
2272
2273             handle_open:
2274               bufp->re_nsub++;
2275               regnum++;
2276
2277               if (COMPILE_STACK_FULL)
2278                 {
2279                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
2280                             compile_stack_elt_t);
2281                   if (compile_stack.stack == NULL) return REG_ESPACE;
2282
2283                   compile_stack.size <<= 1;
2284                 }
2285
2286               /* These are the values to restore when we hit end of this
2287                  group.  They are all relative offsets, so that if the
2288                  whole pattern moves because of realloc, they will still
2289                  be valid.  */
2290               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
2291               COMPILE_STACK_TOP.fixup_alt_jump
2292                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
2293               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
2294               COMPILE_STACK_TOP.regnum = regnum;
2295
2296               /* We will eventually replace the 0 with the number of
2297                  groups inner to this one.  But do not push a
2298                  start_memory for groups beyond the last one we can
2299                  represent in the compiled pattern.  */
2300               if (regnum <= MAX_REGNUM)
2301                 {
2302                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
2303                   BUF_PUSH_3 (start_memory, regnum, 0);
2304                 }
2305
2306               compile_stack.avail++;
2307
2308               fixup_alt_jump = 0;
2309               laststart = 0;
2310               begalt = b;
2311               /* If we've reached MAX_REGNUM groups, then this open
2312                  won't actually generate any code, so we'll have to
2313                  clear pending_exact explicitly.  */
2314               pending_exact = 0;
2315               break;
2316
2317
2318             case ')':
2319               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
2320
2321               if (COMPILE_STACK_EMPTY)
2322                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2323                   goto normal_backslash;
2324                 else
2325                   FREE_STACK_RETURN (REG_ERPAREN);
2326
2327             handle_close:
2328               if (fixup_alt_jump)
2329                 { /* Push a dummy failure point at the end of the
2330                      alternative for a possible future
2331                      `pop_failure_jump' to pop.  See comments at
2332                      `push_dummy_failure' in `re_match_2'.  */
2333                   BUF_PUSH (push_dummy_failure);
2334
2335                   /* We allocated space for this jump when we assigned
2336                      to `fixup_alt_jump', in the `handle_alt' case below.  */
2337                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
2338                 }
2339
2340               /* See similar code for backslashed left paren above.  */
2341               if (COMPILE_STACK_EMPTY)
2342                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2343                   goto normal_char;
2344                 else
2345                   FREE_STACK_RETURN (REG_ERPAREN);
2346
2347               /* Since we just checked for an empty stack above, this
2348                  ``can't happen''.  */
2349               assert (compile_stack.avail != 0);
2350               {
2351                 /* We don't just want to restore into `regnum', because
2352                    later groups should continue to be numbered higher,
2353                    as in `(ab)c(de)' -- the second group is #2.  */
2354                 regnum_t this_group_regnum;
2355
2356                 compile_stack.avail--;
2357                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
2358                 fixup_alt_jump
2359                   = COMPILE_STACK_TOP.fixup_alt_jump
2360                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
2361                     : 0;
2362                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
2363                 this_group_regnum = COMPILE_STACK_TOP.regnum;
2364                 /* If we've reached MAX_REGNUM groups, then this open
2365                    won't actually generate any code, so we'll have to
2366                    clear pending_exact explicitly.  */
2367                 pending_exact = 0;
2368
2369                 /* We're at the end of the group, so now we know how many
2370                    groups were inside this one.  */
2371                 if (this_group_regnum <= MAX_REGNUM)
2372                   {
2373                     unsigned char *inner_group_loc
2374                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
2375
2376                     *inner_group_loc = regnum - this_group_regnum;
2377                     BUF_PUSH_3 (stop_memory, this_group_regnum,
2378                                 regnum - this_group_regnum);
2379                   }
2380               }
2381               break;
2382
2383
2384             case '|':                                   /* `\|'.  */
2385               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
2386                 goto normal_backslash;
2387             handle_alt:
2388               if (syntax & RE_LIMITED_OPS)
2389                 goto normal_char;
2390
2391               /* Insert before the previous alternative a jump which
2392                  jumps to this alternative if the former fails.  */
2393               GET_BUFFER_SPACE (3);
2394               INSERT_JUMP (on_failure_jump, begalt, b + 6);
2395               pending_exact = 0;
2396               b += 3;
2397
2398               /* The alternative before this one has a jump after it
2399                  which gets executed if it gets matched.  Adjust that
2400                  jump so it will jump to this alternative's analogous
2401                  jump (put in below, which in turn will jump to the next
2402                  (if any) alternative's such jump, etc.).  The last such
2403                  jump jumps to the correct final destination.  A picture:
2404                           _____ _____
2405                           |   | |   |
2406                           |   v |   v
2407                          a | b   | c
2408
2409                  If we are at `b', then fixup_alt_jump right now points to a
2410                  three-byte space after `a'.  We'll put in the jump, set
2411                  fixup_alt_jump to right after `b', and leave behind three
2412                  bytes which we'll fill in when we get to after `c'.  */
2413
2414               if (fixup_alt_jump)
2415                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2416
2417               /* Mark and leave space for a jump after this alternative,
2418                  to be filled in later either by next alternative or
2419                  when know we're at the end of a series of alternatives.  */
2420               fixup_alt_jump = b;
2421               GET_BUFFER_SPACE (3);
2422               b += 3;
2423
2424               laststart = 0;
2425               begalt = b;
2426               break;
2427
2428
2429             case '{':
2430               /* If \{ is a literal.  */
2431               if (!(syntax & RE_INTERVALS)
2432                      /* If we're at `\{' and it's not the open-interval
2433                         operator.  */
2434                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
2435                   || (p - 2 == pattern  &&  p == pend))
2436                 goto normal_backslash;
2437
2438             handle_interval:
2439               {
2440                 /* If got here, then the syntax allows intervals.  */
2441
2442                 /* At least (most) this many matches must be made.  */
2443                 int lower_bound = -1, upper_bound = -1;
2444
2445                 beg_interval = p - 1;
2446
2447                 if (p == pend)
2448                   {
2449                     if (syntax & RE_NO_BK_BRACES)
2450                       goto unfetch_interval;
2451                     else
2452                       FREE_STACK_RETURN (REG_EBRACE);
2453                   }
2454
2455                 GET_UNSIGNED_NUMBER (lower_bound);
2456
2457                 if (c == ',')
2458                   {
2459                     GET_UNSIGNED_NUMBER (upper_bound);
2460                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
2461                   }
2462                 else
2463                   /* Interval such as `{1}' => match exactly once. */
2464                   upper_bound = lower_bound;
2465
2466                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
2467                     || lower_bound > upper_bound)
2468                   {
2469                     if (syntax & RE_NO_BK_BRACES)
2470                       goto unfetch_interval;
2471                     else
2472                       FREE_STACK_RETURN (REG_BADBR);
2473                   }
2474
2475                 if (!(syntax & RE_NO_BK_BRACES))
2476                   {
2477                     if (c != '\\') FREE_STACK_RETURN (REG_EBRACE);
2478
2479                     PATFETCH (c);
2480                   }
2481
2482                 if (c != '}')
2483                   {
2484                     if (syntax & RE_NO_BK_BRACES)
2485                       goto unfetch_interval;
2486                     else
2487                       FREE_STACK_RETURN (REG_BADBR);
2488                   }
2489
2490                 /* We just parsed a valid interval.  */
2491
2492                 /* If it's invalid to have no preceding re.  */
2493                 if (!laststart)
2494                   {
2495                     if (syntax & RE_CONTEXT_INVALID_OPS)
2496                       FREE_STACK_RETURN (REG_BADRPT);
2497                     else if (syntax & RE_CONTEXT_INDEP_OPS)
2498                       laststart = b;
2499                     else
2500                       goto unfetch_interval;
2501                   }
2502
2503                 /* If the upper bound is zero, don't want to succeed at
2504                    all; jump from `laststart' to `b + 3', which will be
2505                    the end of the buffer after we insert the jump.  */
2506                  if (upper_bound == 0)
2507                    {
2508                      GET_BUFFER_SPACE (3);
2509                      INSERT_JUMP (jump, laststart, b + 3);
2510                      b += 3;
2511                    }
2512
2513                  /* Otherwise, we have a nontrivial interval.  When
2514                     we're all done, the pattern will look like:
2515                       set_number_at <jump count> <upper bound>
2516                       set_number_at <succeed_n count> <lower bound>
2517                       succeed_n <after jump addr> <succeed_n count>
2518                       <body of loop>
2519                       jump_n <succeed_n addr> <jump count>
2520                     (The upper bound and `jump_n' are omitted if
2521                     `upper_bound' is 1, though.)  */
2522                  else
2523                    { /* If the upper bound is > 1, we need to insert
2524                         more at the end of the loop.  */
2525                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
2526
2527                      GET_BUFFER_SPACE (nbytes);
2528
2529                      /* Initialize lower bound of the `succeed_n', even
2530                         though it will be set during matching by its
2531                         attendant `set_number_at' (inserted next),
2532                         because `re_compile_fastmap' needs to know.
2533                         Jump to the `jump_n' we might insert below.  */
2534                      INSERT_JUMP2 (succeed_n, laststart,
2535                                    b + 5 + (upper_bound > 1) * 5,
2536                                    lower_bound);
2537                      b += 5;
2538
2539                      /* Code to initialize the lower bound.  Insert
2540                         before the `succeed_n'.  The `5' is the last two
2541                         bytes of this `set_number_at', plus 3 bytes of
2542                         the following `succeed_n'.  */
2543                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
2544                      b += 5;
2545
2546                      if (upper_bound > 1)
2547                        { /* More than one repetition is allowed, so
2548                             append a backward jump to the `succeed_n'
2549                             that starts this interval.
2550
2551                             When we've reached this during matching,
2552                             we'll have matched the interval once, so
2553                             jump back only `upper_bound - 1' times.  */
2554                          STORE_JUMP2 (jump_n, b, laststart + 5,
2555                                       upper_bound - 1);
2556                          b += 5;
2557
2558                          /* The location we want to set is the second
2559                             parameter of the `jump_n'; that is `b-2' as
2560                             an absolute address.  `laststart' will be
2561                             the `set_number_at' we're about to insert;
2562                             `laststart+3' the number to set, the source
2563                             for the relative address.  But we are
2564                             inserting into the middle of the pattern --
2565                             so everything is getting moved up by 5.
2566                             Conclusion: (b - 2) - (laststart + 3) + 5,
2567                             i.e., b - laststart.
2568
2569                             We insert this at the beginning of the loop
2570                             so that if we fail during matching, we'll
2571                             reinitialize the bounds.  */
2572                          insert_op2 (set_number_at, laststart, b - laststart,
2573                                      upper_bound - 1, b);
2574                          b += 5;
2575                        }
2576                    }
2577                 pending_exact = 0;
2578                 beg_interval = NULL;
2579               }
2580               break;
2581
2582             unfetch_interval:
2583               /* If an invalid interval, match the characters as literals.  */
2584                assert (beg_interval);
2585                p = beg_interval;
2586                beg_interval = NULL;
2587
2588                /* normal_char and normal_backslash need `c'.  */
2589                PATFETCH (c);
2590
2591                if (!(syntax & RE_NO_BK_BRACES))
2592                  {
2593                    if (p > pattern  &&  p[-1] == '\\')
2594                      goto normal_backslash;
2595                  }
2596                goto normal_char;
2597
2598 #ifdef emacs
2599             /* There is no way to specify the before_dot and after_dot
2600                operators.  rms says this is ok.  --karl  */
2601             case '=':
2602               BUF_PUSH (at_dot);
2603               break;
2604
2605             case 's':
2606               laststart = b;
2607               PATFETCH (c);
2608               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
2609               break;
2610
2611             case 'S':
2612               laststart = b;
2613               PATFETCH (c);
2614               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
2615               break;
2616 #endif /* emacs */
2617
2618
2619             case 'w':
2620               if (re_syntax_options & RE_NO_GNU_OPS)
2621                 goto normal_char;
2622               laststart = b;
2623               BUF_PUSH (wordchar);
2624               break;
2625
2626
2627             case 'W':
2628               if (re_syntax_options & RE_NO_GNU_OPS)
2629                 goto normal_char;
2630               laststart = b;
2631               BUF_PUSH (notwordchar);
2632               break;
2633
2634
2635             case '<':
2636               if (re_syntax_options & RE_NO_GNU_OPS)
2637                 goto normal_char;
2638               BUF_PUSH (wordbeg);
2639               break;
2640
2641             case '>':
2642               if (re_syntax_options & RE_NO_GNU_OPS)
2643                 goto normal_char;
2644               BUF_PUSH (wordend);
2645               break;
2646
2647             case 'b':
2648               if (re_syntax_options & RE_NO_GNU_OPS)
2649                 goto normal_char;
2650               BUF_PUSH (wordbound);
2651               break;
2652
2653             case 'B':
2654               if (re_syntax_options & RE_NO_GNU_OPS)
2655                 goto normal_char;
2656               BUF_PUSH (notwordbound);
2657               break;
2658
2659             case '`':
2660               if (re_syntax_options & RE_NO_GNU_OPS)
2661                 goto normal_char;
2662               BUF_PUSH (begbuf);
2663               break;
2664
2665             case '\'':
2666               if (re_syntax_options & RE_NO_GNU_OPS)
2667                 goto normal_char;
2668               BUF_PUSH (endbuf);
2669               break;
2670
2671             case '1': case '2': case '3': case '4': case '5':
2672             case '6': case '7': case '8': case '9':
2673               if (syntax & RE_NO_BK_REFS)
2674                 goto normal_char;
2675
2676               c1 = c - '0';
2677
2678               if (c1 > regnum)
2679                 FREE_STACK_RETURN (REG_ESUBREG);
2680
2681               /* Can't back reference to a subexpression if inside of it.  */
2682               if (group_in_compile_stack (compile_stack, (regnum_t) c1))
2683                 goto normal_char;
2684
2685               laststart = b;
2686               BUF_PUSH_2 (duplicate, c1);
2687               break;
2688
2689
2690             case '+':
2691             case '?':
2692               if (syntax & RE_BK_PLUS_QM)
2693                 goto handle_plus;
2694               else
2695                 goto normal_backslash;
2696
2697             default:
2698             normal_backslash:
2699               /* You might think it would be useful for \ to mean
2700                  not to translate; but if we don't translate it
2701                  it will never match anything.  */
2702               c = TRANSLATE (c);
2703               goto normal_char;
2704             }
2705           break;
2706
2707
2708         default:
2709         /* Expects the character in `c'.  */
2710         normal_char:
2711               /* If no exactn currently being built.  */
2712           if (!pending_exact
2713
2714               /* If last exactn not at current position.  */
2715               || pending_exact + *pending_exact + 1 != b
2716
2717               /* We have only one byte following the exactn for the count.  */
2718               || *pending_exact == (1 << BYTEWIDTH) - 1
2719
2720               /* If followed by a repetition operator.  */
2721               || *p == '*' || *p == '^'
2722               || ((syntax & RE_BK_PLUS_QM)
2723                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
2724                   : (*p == '+' || *p == '?'))
2725               || ((syntax & RE_INTERVALS)
2726                   && ((syntax & RE_NO_BK_BRACES)
2727                       ? *p == '{'
2728                       : (p[0] == '\\' && p[1] == '{'))))
2729             {
2730               /* Start building a new exactn.  */
2731
2732               laststart = b;
2733
2734               BUF_PUSH_2 (exactn, 0);
2735               pending_exact = b - 1;
2736             }
2737
2738           BUF_PUSH (c);
2739           (*pending_exact)++;
2740           break;
2741         } /* switch (c) */
2742     } /* while p != pend */
2743
2744
2745   /* Through the pattern now.  */
2746
2747   if (fixup_alt_jump)
2748     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2749
2750   if (!COMPILE_STACK_EMPTY)
2751     FREE_STACK_RETURN (REG_EPAREN);
2752
2753   /* If we don't want backtracking, force success
2754      the first time we reach the end of the compiled pattern.  */
2755   if (syntax & RE_NO_POSIX_BACKTRACKING)
2756     BUF_PUSH (succeed);
2757
2758   free (compile_stack.stack);
2759
2760   /* We have succeeded; set the length of the buffer.  */
2761   bufp->used = b - bufp->buffer;
2762
2763 #ifdef DEBUG
2764   if (debug)
2765     {
2766       DEBUG_PRINT1 ("\nCompiled pattern: \n");
2767       print_compiled_pattern (bufp);
2768     }
2769 #endif /* DEBUG */
2770
2771 #ifndef MATCH_MAY_ALLOCATE
2772   /* Initialize the failure stack to the largest possible stack.  This
2773      isn't necessary unless we're trying to avoid calling alloca in
2774      the search and match routines.  */
2775   {
2776     int num_regs = bufp->re_nsub + 1;
2777
2778     /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
2779        is strictly greater than re_max_failures, the largest possible stack
2780        is 2 * re_max_failures failure points.  */
2781     if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
2782       {
2783         fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
2784
2785 #ifdef emacs
2786         if (! fail_stack.stack)
2787           fail_stack.stack
2788             = (fail_stack_elt_t *) xmalloc (fail_stack.size
2789                                             * sizeof (fail_stack_elt_t));
2790         else
2791           fail_stack.stack
2792             = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
2793                                              (fail_stack.size
2794                                               * sizeof (fail_stack_elt_t)));
2795 #else /* not emacs */
2796         if (! fail_stack.stack)
2797           fail_stack.stack
2798             = (fail_stack_elt_t *) malloc (fail_stack.size
2799                                            * sizeof (fail_stack_elt_t));
2800         else
2801           fail_stack.stack
2802             = (fail_stack_elt_t *) realloc (fail_stack.stack,
2803                                             (fail_stack.size
2804                                              * sizeof (fail_stack_elt_t)));
2805 #endif /* not emacs */
2806       }
2807
2808     regex_grow_registers (num_regs);
2809   }
2810 #endif /* not MATCH_MAY_ALLOCATE */
2811
2812   return REG_NOERROR;
2813 } /* regex_compile */
2814 \f
2815 /* Subroutines for `regex_compile'.  */
2816
2817 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
2818
2819 static void
2820 store_op1 (op, loc, arg)
2821     re_opcode_t op;
2822     unsigned char *loc;
2823     int arg;
2824 {
2825   *loc = (unsigned char) op;
2826   STORE_NUMBER (loc + 1, arg);
2827 }
2828
2829
2830 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
2831
2832 static void
2833 store_op2 (op, loc, arg1, arg2)
2834     re_opcode_t op;
2835     unsigned char *loc;
2836     int arg1, arg2;
2837 {
2838   *loc = (unsigned char) op;
2839   STORE_NUMBER (loc + 1, arg1);
2840   STORE_NUMBER (loc + 3, arg2);
2841 }
2842
2843
2844 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2845    for OP followed by two-byte integer parameter ARG.  */
2846
2847 static void
2848 insert_op1 (op, loc, arg, end)
2849     re_opcode_t op;
2850     unsigned char *loc;
2851     int arg;
2852     unsigned char *end;
2853 {
2854   register unsigned char *pfrom = end;
2855   register unsigned char *pto = end + 3;
2856
2857   while (pfrom != loc)
2858     *--pto = *--pfrom;
2859
2860   store_op1 (op, loc, arg);
2861 }
2862
2863
2864 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
2865
2866 static void
2867 insert_op2 (op, loc, arg1, arg2, end)
2868     re_opcode_t op;
2869     unsigned char *loc;
2870     int arg1, arg2;
2871     unsigned char *end;
2872 {
2873   register unsigned char *pfrom = end;
2874   register unsigned char *pto = end + 5;
2875
2876   while (pfrom != loc)
2877     *--pto = *--pfrom;
2878
2879   store_op2 (op, loc, arg1, arg2);
2880 }
2881
2882
2883 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
2884    after an alternative or a begin-subexpression.  We assume there is at
2885    least one character before the ^.  */
2886
2887 static boolean
2888 at_begline_loc_p (pattern, p, syntax)
2889     const char *pattern, *p;
2890     reg_syntax_t syntax;
2891 {
2892   const char *prev = p - 2;
2893   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2894
2895   return
2896        /* After a subexpression?  */
2897        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2898        /* After an alternative?  */
2899     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2900 }
2901
2902
2903 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
2904    at least one character after the $, i.e., `P < PEND'.  */
2905
2906 static boolean
2907 at_endline_loc_p (p, pend, syntax)
2908     const char *p, *pend;
2909     reg_syntax_t syntax;
2910 {
2911   const char *next = p;
2912   boolean next_backslash = *next == '\\';
2913   const char *next_next = p + 1 < pend ? p + 1 : 0;
2914
2915   return
2916        /* Before a subexpression?  */
2917        (syntax & RE_NO_BK_PARENS ? *next == ')'
2918         : next_backslash && next_next && *next_next == ')')
2919        /* Before an alternative?  */
2920     || (syntax & RE_NO_BK_VBAR ? *next == '|'
2921         : next_backslash && next_next && *next_next == '|');
2922 }
2923
2924
2925 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2926    false if it's not.  */
2927
2928 static boolean
2929 group_in_compile_stack (compile_stack, regnum)
2930     compile_stack_type compile_stack;
2931     regnum_t regnum;
2932 {
2933   int this_element;
2934
2935   for (this_element = compile_stack.avail - 1;
2936        this_element >= 0;
2937        this_element--)
2938     if (compile_stack.stack[this_element].regnum == regnum)
2939       return true;
2940
2941   return false;
2942 }
2943
2944
2945 /* Read the ending character of a range (in a bracket expression) from the
2946    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
2947    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
2948    Then we set the translation of all bits between the starting and
2949    ending characters (inclusive) in the compiled pattern B.
2950
2951    Return an error code.
2952
2953    We use these short variable names so we can use the same macros as
2954    `regex_compile' itself.  */
2955
2956 static reg_errcode_t
2957 compile_range (p_ptr, pend, translate, syntax, b)
2958     const char **p_ptr, *pend;
2959     RE_TRANSLATE_TYPE translate;
2960     reg_syntax_t syntax;
2961     unsigned char *b;
2962 {
2963   unsigned this_char;
2964
2965   const char *p = *p_ptr;
2966   unsigned int range_start, range_end;
2967
2968   if (p == pend)
2969     return REG_ERANGE;
2970
2971   /* Even though the pattern is a signed `char *', we need to fetch
2972      with unsigned char *'s; if the high bit of the pattern character
2973      is set, the range endpoints will be negative if we fetch using a
2974      signed char *.
2975
2976      We also want to fetch the endpoints without translating them; the
2977      appropriate translation is done in the bit-setting loop below.  */
2978   /* The SVR4 compiler on the 3B2 had trouble with unsigned const char *.  */
2979   range_start = ((const unsigned char *) p)[-2];
2980   range_end   = ((const unsigned char *) p)[0];
2981
2982   /* Have to increment the pointer into the pattern string, so the
2983      caller isn't still at the ending character.  */
2984   (*p_ptr)++;
2985
2986   /* If the start is after the end, the range is empty.  */
2987   if (range_start > range_end)
2988     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2989
2990   /* Here we see why `this_char' has to be larger than an `unsigned
2991      char' -- the range is inclusive, so if `range_end' == 0xff
2992      (assuming 8-bit characters), we would otherwise go into an infinite
2993      loop, since all characters <= 0xff.  */
2994   for (this_char = range_start; this_char <= range_end; this_char++)
2995     {
2996       SET_LIST_BIT (TRANSLATE (this_char));
2997     }
2998
2999   return REG_NOERROR;
3000 }
3001 \f
3002 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
3003    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
3004    characters can start a string that matches the pattern.  This fastmap
3005    is used by re_search to skip quickly over impossible starting points.
3006
3007    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
3008    area as BUFP->fastmap.
3009
3010    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
3011    the pattern buffer.
3012
3013    Returns 0 if we succeed, -2 if an internal error.   */
3014
3015 int
3016 re_compile_fastmap (bufp)
3017      struct re_pattern_buffer *bufp;
3018 {
3019   int j, k;
3020 #ifdef MATCH_MAY_ALLOCATE
3021   fail_stack_type fail_stack;
3022 #endif
3023 #ifndef REGEX_MALLOC
3024   char *destination;
3025 #endif
3026   /* We don't push any register information onto the failure stack.  */
3027   unsigned num_regs = 0;
3028
3029   register char *fastmap = bufp->fastmap;
3030   unsigned char *pattern = bufp->buffer;
3031   unsigned char *p = pattern;
3032   register unsigned char *pend = pattern + bufp->used;
3033
3034 #ifdef REL_ALLOC
3035   /* This holds the pointer to the failure stack, when
3036      it is allocated relocatably.  */
3037   fail_stack_elt_t *failure_stack_ptr;
3038 #endif
3039
3040   /* Assume that each path through the pattern can be null until
3041      proven otherwise.  We set this false at the bottom of switch
3042      statement, to which we get only if a particular path doesn't
3043      match the empty string.  */
3044   boolean path_can_be_null = true;
3045
3046   /* We aren't doing a `succeed_n' to begin with.  */
3047   boolean succeed_n_p = false;
3048
3049   assert (fastmap != NULL && p != NULL);
3050
3051   INIT_FAIL_STACK ();
3052   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
3053   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
3054   bufp->can_be_null = 0;
3055
3056   while (1)
3057     {
3058       if (p == pend || *p == succeed)
3059         {
3060           /* We have reached the (effective) end of pattern.  */
3061           if (!FAIL_STACK_EMPTY ())
3062             {
3063               bufp->can_be_null |= path_can_be_null;
3064
3065               /* Reset for next path.  */
3066               path_can_be_null = true;
3067
3068               p = fail_stack.stack[--fail_stack.avail].pointer;
3069
3070               continue;
3071             }
3072           else
3073             break;
3074         }
3075
3076       /* We should never be about to go beyond the end of the pattern.  */
3077       assert (p < pend);
3078
3079       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
3080         {
3081
3082         /* I guess the idea here is to simply not bother with a fastmap
3083            if a backreference is used, since it's too hard to figure out
3084            the fastmap for the corresponding group.  Setting
3085            `can_be_null' stops `re_search_2' from using the fastmap, so
3086            that is all we do.  */
3087         case duplicate:
3088           bufp->can_be_null = 1;
3089           goto done;
3090
3091
3092       /* Following are the cases which match a character.  These end
3093          with `break'.  */
3094
3095         case exactn:
3096           fastmap[p[1]] = 1;
3097           break;
3098
3099
3100         case charset:
3101           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
3102             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
3103               fastmap[j] = 1;
3104           break;
3105
3106
3107         case charset_not:
3108           /* Chars beyond end of map must be allowed.  */
3109           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
3110             fastmap[j] = 1;
3111
3112           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
3113             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
3114               fastmap[j] = 1;
3115           break;
3116
3117
3118         case wordchar:
3119           for (j = 0; j < (1 << BYTEWIDTH); j++)
3120             if (SYNTAX (j) == Sword)
3121               fastmap[j] = 1;
3122           break;
3123
3124
3125         case notwordchar:
3126           for (j = 0; j < (1 << BYTEWIDTH); j++)
3127             if (SYNTAX (j) != Sword)
3128               fastmap[j] = 1;
3129           break;
3130
3131
3132         case anychar:
3133           {
3134             int fastmap_newline = fastmap['\n'];
3135
3136             /* `.' matches anything ...  */
3137             for (j = 0; j < (1 << BYTEWIDTH); j++)
3138               fastmap[j] = 1;
3139
3140             /* ... except perhaps newline.  */
3141             if (!(bufp->syntax & RE_DOT_NEWLINE))
3142               fastmap['\n'] = fastmap_newline;
3143
3144             /* Return if we have already set `can_be_null'; if we have,
3145                then the fastmap is irrelevant.  Something's wrong here.  */
3146             else if (bufp->can_be_null)
3147               goto done;
3148
3149             /* Otherwise, have to check alternative paths.  */
3150             break;
3151           }
3152
3153 #ifdef emacs
3154         case syntaxspec:
3155           k = *p++;
3156           for (j = 0; j < (1 << BYTEWIDTH); j++)
3157             if (SYNTAX (j) == (enum syntaxcode) k)
3158               fastmap[j] = 1;
3159           break;
3160
3161
3162         case notsyntaxspec:
3163           k = *p++;
3164           for (j = 0; j < (1 << BYTEWIDTH); j++)
3165             if (SYNTAX (j) != (enum syntaxcode) k)
3166               fastmap[j] = 1;
3167           break;
3168
3169
3170       /* All cases after this match the empty string.  These end with
3171          `continue'.  */
3172
3173
3174         case before_dot:
3175         case at_dot:
3176         case after_dot:
3177           continue;
3178 #endif /* emacs */
3179
3180
3181         case no_op:
3182         case begline:
3183         case endline:
3184         case begbuf:
3185         case endbuf:
3186         case wordbound:
3187         case notwordbound:
3188         case wordbeg:
3189         case wordend:
3190         case push_dummy_failure:
3191           continue;
3192
3193
3194         case jump_n:
3195         case pop_failure_jump:
3196         case maybe_pop_jump:
3197         case jump:
3198         case jump_past_alt:
3199         case dummy_failure_jump:
3200           EXTRACT_NUMBER_AND_INCR (j, p);
3201           p += j;
3202           if (j > 0)
3203             continue;
3204
3205           /* Jump backward implies we just went through the body of a
3206              loop and matched nothing.  Opcode jumped to should be
3207              `on_failure_jump' or `succeed_n'.  Just treat it like an
3208              ordinary jump.  For a * loop, it has pushed its failure
3209              point already; if so, discard that as redundant.  */
3210           if ((re_opcode_t) *p != on_failure_jump
3211               && (re_opcode_t) *p != succeed_n)
3212             continue;
3213
3214           p++;
3215           EXTRACT_NUMBER_AND_INCR (j, p);
3216           p += j;
3217
3218           /* If what's on the stack is where we are now, pop it.  */
3219           if (!FAIL_STACK_EMPTY ()
3220               && fail_stack.stack[fail_stack.avail - 1].pointer == p)
3221             fail_stack.avail--;
3222
3223           continue;
3224
3225
3226         case on_failure_jump:
3227         case on_failure_keep_string_jump:
3228         handle_on_failure_jump:
3229           EXTRACT_NUMBER_AND_INCR (j, p);
3230
3231           /* For some patterns, e.g., `(a?)?', `p+j' here points to the
3232              end of the pattern.  We don't want to push such a point,
3233              since when we restore it above, entering the switch will
3234              increment `p' past the end of the pattern.  We don't need
3235              to push such a point since we obviously won't find any more
3236              fastmap entries beyond `pend'.  Such a pattern can match
3237              the null string, though.  */
3238           if (p + j < pend)
3239             {
3240               if (!PUSH_PATTERN_OP (p + j, fail_stack))
3241                 {
3242                   RESET_FAIL_STACK ();
3243                   return -2;
3244                 }
3245             }
3246           else
3247             bufp->can_be_null = 1;
3248
3249           if (succeed_n_p)
3250             {
3251               EXTRACT_NUMBER_AND_INCR (k, p);   /* Skip the n.  */
3252               succeed_n_p = false;
3253             }
3254
3255           continue;
3256
3257
3258         case succeed_n:
3259           /* Get to the number of times to succeed.  */
3260           p += 2;
3261
3262           /* Increment p past the n for when k != 0.  */
3263           EXTRACT_NUMBER_AND_INCR (k, p);
3264           if (k == 0)
3265             {
3266               p -= 4;
3267               succeed_n_p = true;  /* Spaghetti code alert.  */
3268               goto handle_on_failure_jump;
3269             }
3270           continue;
3271
3272
3273         case set_number_at:
3274           p += 4;
3275           continue;
3276
3277
3278         case start_memory:
3279         case stop_memory:
3280           p += 2;
3281           continue;
3282
3283
3284         default:
3285           abort (); /* We have listed all the cases.  */
3286         } /* switch *p++ */
3287
3288       /* Getting here means we have found the possible starting
3289          characters for one path of the pattern -- and that the empty
3290          string does not match.  We need not follow this path further.
3291          Instead, look at the next alternative (remembered on the
3292 &nb