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