370a612603daa79f35dafa86097602e8457a2f99
[kopensolaris-gnu/glibc.git] / posix / regex.c
1 /* Extended regular expression matching and search library,
2    version 0.12.
3    (Implements POSIX draft P10003.2/D11.2, except for
4    internationalization features.)
5
6    Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
7
8    This file is part of the GNU C Library.  Its master source is NOT part of
9    the C library, however.  The master source lives in /gd/gnu/lib.
10
11    The GNU C Library is free software; you can redistribute it and/or
12    modify it under the terms of the GNU Library General Public License as
13    published by the Free Software Foundation; either version 2 of the
14    License, or (at your option) any later version.
15
16    The GNU C Library is distributed in the hope that it will be useful,
17    but WITHOUT ANY WARRANTY; without even the implied warranty of
18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19    Library General Public License for more details.
20
21    You should have received a copy of the GNU Library General Public
22    License along with the GNU C Library; see the file COPYING.LIB.  If not,
23    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24    Boston, MA 02111-1307, USA.  */
25
26 /* AIX requires this to be the first thing in the file. */
27 #if defined (_AIX) && !defined (REGEX_MALLOC)
28   #pragma alloca
29 #endif
30
31 #undef  _GNU_SOURCE
32 #define _GNU_SOURCE
33
34 #ifdef HAVE_CONFIG_H
35 #include <config.h>
36 #endif
37
38 /* 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 /* 4400 was enough to cause a crash on Alpha OSF/1,
1015    whose default stack limit is 2mb.  */
1016 int re_max_failures = 4000;
1017 #else
1018 int re_max_failures = 2000;
1019 #endif
1020
1021 union fail_stack_elt
1022 {
1023   unsigned char *pointer;
1024   int integer;
1025 };
1026
1027 typedef union fail_stack_elt fail_stack_elt_t;
1028
1029 typedef struct
1030 {
1031   fail_stack_elt_t *stack;
1032   unsigned size;
1033   unsigned avail;                       /* Offset of next open position.  */
1034 } fail_stack_type;
1035
1036 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
1037 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1038 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
1039
1040
1041 /* Define macros to initialize and free the failure stack.
1042    Do `return -2' if the alloc fails.  */
1043
1044 #ifdef MATCH_MAY_ALLOCATE
1045 #define INIT_FAIL_STACK()                                               \
1046   do {                                                                  \
1047     fail_stack.stack = (fail_stack_elt_t *)                             \
1048       REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));    \
1049                                                                         \
1050     if (fail_stack.stack == NULL)                                       \
1051       return -2;                                                        \
1052                                                                         \
1053     fail_stack.size = INIT_FAILURE_ALLOC;                               \
1054     fail_stack.avail = 0;                                               \
1055   } while (0)
1056
1057 #define RESET_FAIL_STACK()  REGEX_FREE_STACK (fail_stack.stack)
1058 #else
1059 #define INIT_FAIL_STACK()                                               \
1060   do {                                                                  \
1061     fail_stack.avail = 0;                                               \
1062   } while (0)
1063
1064 #define RESET_FAIL_STACK()
1065 #endif
1066
1067
1068 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1069
1070    Return 1 if succeeds, and 0 if either ran out of memory
1071    allocating space for it or it was already too large.
1072
1073    REGEX_REALLOCATE_STACK requires `destination' be declared.   */
1074
1075 #define DOUBLE_FAIL_STACK(fail_stack)                                   \
1076   ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1077    ? 0                                                                  \
1078    : ((fail_stack).stack = (fail_stack_elt_t *)                         \
1079         REGEX_REALLOCATE_STACK ((fail_stack).stack,                     \
1080           (fail_stack).size * sizeof (fail_stack_elt_t),                \
1081           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),        \
1082                                                                         \
1083       (fail_stack).stack == NULL                                        \
1084       ? 0                                                               \
1085       : ((fail_stack).size <<= 1,                                       \
1086          1)))
1087
1088
1089 /* Push pointer POINTER on FAIL_STACK.
1090    Return 1 if was able to do so and 0 if ran out of memory allocating
1091    space to do so.  */
1092 #define PUSH_PATTERN_OP(POINTER, FAIL_STACK)                            \
1093   ((FAIL_STACK_FULL ()                                                  \
1094     && !DOUBLE_FAIL_STACK (FAIL_STACK))                                 \
1095    ? 0                                                                  \
1096    : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER,       \
1097       1))
1098
1099 /* Push a pointer value onto the failure stack.
1100    Assumes the variable `fail_stack'.  Probably should only
1101    be called from within `PUSH_FAILURE_POINT'.  */
1102 #define PUSH_FAILURE_POINTER(item)                                      \
1103   fail_stack.stack[fail_stack.avail++].pointer = (unsigned char *) (item)
1104
1105 /* This pushes an integer-valued item onto the failure stack.
1106    Assumes the variable `fail_stack'.  Probably should only
1107    be called from within `PUSH_FAILURE_POINT'.  */
1108 #define PUSH_FAILURE_INT(item)                                  \
1109   fail_stack.stack[fail_stack.avail++].integer = (item)
1110
1111 /* Push a fail_stack_elt_t value onto the failure stack.
1112    Assumes the variable `fail_stack'.  Probably should only
1113    be called from within `PUSH_FAILURE_POINT'.  */
1114 #define PUSH_FAILURE_ELT(item)                                  \
1115   fail_stack.stack[fail_stack.avail++] =  (item)
1116
1117 /* These three POP... operations complement the three PUSH... operations.
1118    All assume that `fail_stack' is nonempty.  */
1119 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1120 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1121 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1122
1123 /* Used to omit pushing failure point id's when we're not debugging.  */
1124 #ifdef DEBUG
1125 #define DEBUG_PUSH PUSH_FAILURE_INT
1126 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1127 #else
1128 #define DEBUG_PUSH(item)
1129 #define DEBUG_POP(item_addr)
1130 #endif
1131
1132
1133 /* Push the information about the state we will need
1134    if we ever fail back to it.
1135
1136    Requires variables fail_stack, regstart, regend, reg_info, and
1137    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
1138    declared.
1139
1140    Does `return FAILURE_CODE' if runs out of memory.  */
1141
1142 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
1143   do {                                                                  \
1144     char *destination;                                                  \
1145     /* Must be int, so when we don't save any registers, the arithmetic \
1146        of 0 + -1 isn't done as unsigned.  */                            \
1147     unsigned this_reg;                                                  \
1148                                                                         \
1149     DEBUG_STATEMENT (failure_id++);                                     \
1150     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1151     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1152     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1153     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1154                                                                         \
1155     DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);           \
1156     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1157                                                                         \
1158     /* Ensure we have enough space allocated for what we will push.  */ \
1159     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1160       {                                                                 \
1161         if (!DOUBLE_FAIL_STACK (fail_stack))                            \
1162           return failure_code;                                          \
1163                                                                         \
1164         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1165                        (fail_stack).size);                              \
1166         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1167       }                                                                 \
1168                                                                         \
1169     /* Push the info, starting with the registers.  */                  \
1170     DEBUG_PRINT1 ("\n");                                                \
1171                                                                         \
1172     if (1)                                                              \
1173       for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1174            this_reg++)                                                  \
1175         {                                                               \
1176           DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);               \
1177           DEBUG_STATEMENT (num_regs_pushed++);                          \
1178                                                                         \
1179           DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);       \
1180           PUSH_FAILURE_POINTER (regstart[this_reg]);                    \
1181                                                                         \
1182           DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);           \
1183           PUSH_FAILURE_POINTER (regend[this_reg]);                      \
1184                                                                         \
1185           DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);  \
1186           DEBUG_PRINT2 (" match_null=%d",                               \
1187                         REG_MATCH_NULL_STRING_P (reg_info[this_reg]));  \
1188           DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));  \
1189           DEBUG_PRINT2 (" matched_something=%d",                        \
1190                         MATCHED_SOMETHING (reg_info[this_reg]));        \
1191           DEBUG_PRINT2 (" ever_matched=%d",                             \
1192                         EVER_MATCHED_SOMETHING (reg_info[this_reg]));   \
1193           DEBUG_PRINT1 ("\n");                                          \
1194           PUSH_FAILURE_ELT (reg_info[this_reg].word);                   \
1195         }                                                               \
1196                                                                         \
1197     DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
1198     PUSH_FAILURE_INT (lowest_active_reg);                               \
1199                                                                         \
1200     DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
1201     PUSH_FAILURE_INT (highest_active_reg);                              \
1202                                                                         \
1203     DEBUG_PRINT2 ("  Pushing pattern 0x%x: ", pattern_place);           \
1204     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1205     PUSH_FAILURE_POINTER (pattern_place);                               \
1206                                                                         \
1207     DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);            \
1208     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1209                                  size2);                                \
1210     DEBUG_PRINT1 ("'\n");                                               \
1211     PUSH_FAILURE_POINTER (string_place);                                \
1212                                                                         \
1213     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1214     DEBUG_PUSH (failure_id);                                            \
1215   } while (0)
1216
1217 /* This is the number of items that are pushed and popped on the stack
1218    for each register.  */
1219 #define NUM_REG_ITEMS  3
1220
1221 /* Individual items aside from the registers.  */
1222 #ifdef DEBUG
1223 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1224 #else
1225 #define NUM_NONREG_ITEMS 4
1226 #endif
1227
1228 /* We push at most this many items on the stack.  */
1229 /* We used to use (num_regs - 1), which is the number of registers
1230    this regexp will save; but that was changed to 5
1231    to avoid stack overflow for a regexp with lots of parens.  */
1232 #define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1233
1234 /* We actually push this many items.  */
1235 #define NUM_FAILURE_ITEMS                               \
1236   (((0                                                  \
1237      ? 0 : highest_active_reg - lowest_active_reg + 1)  \
1238     * NUM_REG_ITEMS)                                    \
1239    + NUM_NONREG_ITEMS)
1240
1241 /* How many items can still be added to the stack without overflowing it.  */
1242 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1243
1244
1245 /* Pops what PUSH_FAIL_STACK pushes.
1246
1247    We restore into the parameters, all of which should be lvalues:
1248      STR -- the saved data position.
1249      PAT -- the saved pattern position.
1250      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1251      REGSTART, REGEND -- arrays of string positions.
1252      REG_INFO -- array of information about each subexpression.
1253
1254    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1255    `pend', `string1', `size1', `string2', and `size2'.  */
1256
1257 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1258 {                                                                       \
1259   DEBUG_STATEMENT (fail_stack_elt_t failure_id;)                        \
1260   unsigned this_reg;                                                    \
1261   const unsigned char *string_temp;                                     \
1262                                                                         \
1263   assert (!FAIL_STACK_EMPTY ());                                        \
1264                                                                         \
1265   /* Remove failure points and point to how many regs pushed.  */       \
1266   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1267   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1268   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1269                                                                         \
1270   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1271                                                                         \
1272   DEBUG_POP (&failure_id);                                              \
1273   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1274                                                                         \
1275   /* If the saved string location is NULL, it came from an              \
1276      on_failure_keep_string_jump opcode, and we want to throw away the  \
1277      saved NULL, thus retaining our current position in the string.  */ \
1278   string_temp = POP_FAILURE_POINTER ();                                 \
1279   if (string_temp != NULL)                                              \
1280     str = (const char *) string_temp;                                   \
1281                                                                         \
1282   DEBUG_PRINT2 ("  Popping string 0x%x: `", str);                       \
1283   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1284   DEBUG_PRINT1 ("'\n");                                                 \
1285                                                                         \
1286   pat = (unsigned char *) POP_FAILURE_POINTER ();                       \
1287   DEBUG_PRINT2 ("  Popping pattern 0x%x: ", pat);                       \
1288   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1289                                                                         \
1290   /* Restore register info.  */                                         \
1291   high_reg = (unsigned) POP_FAILURE_INT ();                             \
1292   DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);           \
1293                                                                         \
1294   low_reg = (unsigned) POP_FAILURE_INT ();                              \
1295   DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);            \
1296                                                                         \
1297   if (1)                                                                \
1298     for (this_reg = high_reg; this_reg >= low_reg; this_reg--)          \
1299       {                                                                 \
1300         DEBUG_PRINT2 ("    Popping reg: %d\n", this_reg);               \
1301                                                                         \
1302         reg_info[this_reg].word = POP_FAILURE_ELT ();                   \
1303         DEBUG_PRINT2 ("      info: 0x%x\n", reg_info[this_reg]);        \
1304                                                                         \
1305         regend[this_reg] = (const char *) POP_FAILURE_POINTER ();       \
1306         DEBUG_PRINT2 ("      end: 0x%x\n", regend[this_reg]);           \
1307                                                                         \
1308         regstart[this_reg] = (const char *) POP_FAILURE_POINTER ();     \
1309         DEBUG_PRINT2 ("      start: 0x%x\n", regstart[this_reg]);       \
1310       }                                                                 \
1311   else                                                                  \
1312     {                                                                   \
1313       for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1314         {                                                               \
1315           reg_info[this_reg].word.integer = 0;                          \
1316           regend[this_reg] = 0;                                         \
1317           regstart[this_reg] = 0;                                       \
1318         }                                                               \
1319       highest_active_reg = high_reg;                                    \
1320     }                                                                   \
1321                                                                         \
1322   set_regs_matched_done = 0;                                            \
1323   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1324 } /* POP_FAILURE_POINT */
1325
1326
1327 \f
1328 /* Structure for per-register (a.k.a. per-group) information.
1329    Other register information, such as the
1330    starting and ending positions (which are addresses), and the list of
1331    inner groups (which is a bits list) are maintained in separate
1332    variables.
1333
1334    We are making a (strictly speaking) nonportable assumption here: that
1335    the compiler will pack our bit fields into something that fits into
1336    the type of `word', i.e., is something that fits into one item on the
1337    failure stack.  */
1338
1339 typedef union
1340 {
1341   fail_stack_elt_t word;
1342   struct
1343   {
1344       /* This field is one if this group can match the empty string,
1345          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1346 #define MATCH_NULL_UNSET_VALUE 3
1347     unsigned match_null_string_p : 2;
1348     unsigned is_active : 1;
1349     unsigned matched_something : 1;
1350     unsigned ever_matched_something : 1;
1351   } bits;
1352 } register_info_type;
1353
1354 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1355 #define IS_ACTIVE(R)  ((R).bits.is_active)
1356 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1357 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1358
1359
1360 /* Call this when have matched a real character; it sets `matched' flags
1361    for the subexpressions which we are currently inside.  Also records
1362    that those subexprs have matched.  */
1363 #define SET_REGS_MATCHED()                                              \
1364   do                                                                    \
1365     {                                                                   \
1366       if (!set_regs_matched_done)                                       \
1367         {                                                               \
1368           unsigned r;                                                   \
1369           set_regs_matched_done = 1;                                    \
1370           for (r = lowest_active_reg; r <= highest_active_reg; r++)     \
1371             {                                                           \
1372               MATCHED_SOMETHING (reg_info[r])                           \
1373                 = EVER_MATCHED_SOMETHING (reg_info[r])                  \
1374                 = 1;                                                    \
1375             }                                                           \
1376         }                                                               \
1377     }                                                                   \
1378   while (0)
1379
1380 /* Registers are set to a sentinel when they haven't yet matched.  */
1381 static char reg_unset_dummy;
1382 #define REG_UNSET_VALUE (&reg_unset_dummy)
1383 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1384 \f
1385 /* Subroutine declarations and macros for regex_compile.  */
1386
1387 static void store_op1 (), store_op2 ();
1388 static void insert_op1 (), insert_op2 ();
1389 static boolean at_begline_loc_p (), at_endline_loc_p ();
1390 static boolean group_in_compile_stack ();
1391 static reg_errcode_t compile_range ();
1392
1393 /* Fetch the next character in the uncompiled pattern---translating it
1394    if necessary.  Also cast from a signed character in the constant
1395    string passed to us by the user to an unsigned char that we can use
1396    as an array index (in, e.g., `translate').  */
1397 #ifndef PATFETCH
1398 #define PATFETCH(c)                                                     \
1399   do {if (p == pend) return REG_EEND;                                   \
1400     c = (unsigned char) *p++;                                           \
1401     if (translate) c = (unsigned char) translate[c];                    \
1402   } while (0)
1403 #endif
1404
1405 /* Fetch the next character in the uncompiled pattern, with no
1406    translation.  */
1407 #define PATFETCH_RAW(c)                                                 \
1408   do {if (p == pend) return REG_EEND;                                   \
1409     c = (unsigned char) *p++;                                           \
1410   } while (0)
1411
1412 /* Go backwards one character in the pattern.  */
1413 #define PATUNFETCH p--
1414
1415
1416 /* If `translate' is non-null, return translate[D], else just D.  We
1417    cast the subscript to translate because some data is declared as
1418    `char *', to avoid warnings when a string constant is passed.  But
1419    when we use a character as a subscript we must make it unsigned.  */
1420 #ifndef TRANSLATE
1421 #define TRANSLATE(d) \
1422   (translate ? (char) translate[(unsigned char) (d)] : (d))
1423 #endif
1424
1425
1426 /* Macros for outputting the compiled pattern into `buffer'.  */
1427
1428 /* If the buffer isn't allocated when it comes in, use this.  */
1429 #define INIT_BUF_SIZE  32
1430
1431 /* Make sure we have at least N more bytes of space in buffer.  */
1432 #define GET_BUFFER_SPACE(n)                                             \
1433     while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated)  \
1434       EXTEND_BUFFER ()
1435
1436 /* Make sure we have one more byte of buffer space and then add C to it.  */
1437 #define BUF_PUSH(c)                                                     \
1438   do {                                                                  \
1439     GET_BUFFER_SPACE (1);                                               \
1440     *b++ = (unsigned char) (c);                                         \
1441   } while (0)
1442
1443
1444 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
1445 #define BUF_PUSH_2(c1, c2)                                              \
1446   do {                                                                  \
1447     GET_BUFFER_SPACE (2);                                               \
1448     *b++ = (unsigned char) (c1);                                        \
1449     *b++ = (unsigned char) (c2);                                        \
1450   } while (0)
1451
1452
1453 /* As with BUF_PUSH_2, except for three bytes.  */
1454 #define BUF_PUSH_3(c1, c2, c3)                                          \
1455   do {                                                                  \
1456     GET_BUFFER_SPACE (3);                                               \
1457     *b++ = (unsigned char) (c1);                                        \
1458     *b++ = (unsigned char) (c2);                                        \
1459     *b++ = (unsigned char) (c3);                                        \
1460   } while (0)
1461
1462
1463 /* Store a jump with opcode OP at LOC to location TO.  We store a
1464    relative address offset by the three bytes the jump itself occupies.  */
1465 #define STORE_JUMP(op, loc, to) \
1466   store_op1 (op, loc, (to) - (loc) - 3)
1467
1468 /* Likewise, for a two-argument jump.  */
1469 #define STORE_JUMP2(op, loc, to, arg) \
1470   store_op2 (op, loc, (to) - (loc) - 3, arg)
1471
1472 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
1473 #define INSERT_JUMP(op, loc, to) \
1474   insert_op1 (op, loc, (to) - (loc) - 3, b)
1475
1476 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
1477 #define INSERT_JUMP2(op, loc, to, arg) \
1478   insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
1479
1480
1481 /* This is not an arbitrary limit: the arguments which represent offsets
1482    into the pattern are two bytes long.  So if 2^16 bytes turns out to
1483    be too small, many things would have to change.  */
1484 #define MAX_BUF_SIZE (1L << 16)
1485
1486
1487 /* Extend the buffer by twice its current size via realloc and
1488    reset the pointers that pointed into the old block to point to the
1489    correct places in the new one.  If extending the buffer results in it
1490    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
1491 #define EXTEND_BUFFER()                                                 \
1492   do {                                                                  \
1493     unsigned char *old_buffer = bufp->buffer;                           \
1494     if (bufp->allocated == MAX_BUF_SIZE)                                \
1495       return REG_ESIZE;                                                 \
1496     bufp->allocated <<= 1;                                              \
1497     if (bufp->allocated > MAX_BUF_SIZE)                                 \
1498       bufp->allocated = MAX_BUF_SIZE;                                   \
1499     bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
1500     if (bufp->buffer == NULL)                                           \
1501       return REG_ESPACE;                                                \
1502     /* If the buffer moved, move all the pointers into it.  */          \
1503     if (old_buffer != bufp->buffer)                                     \
1504       {                                                                 \
1505         b = (b - old_buffer) + bufp->buffer;                            \
1506         begalt = (begalt - old_buffer) + bufp->buffer;                  \
1507         if (fixup_alt_jump)                                             \
1508           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
1509         if (laststart)                                                  \
1510           laststart = (laststart - old_buffer) + bufp->buffer;          \
1511         if (pending_exact)                                              \
1512           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
1513       }                                                                 \
1514   } while (0)
1515
1516
1517 /* Since we have one byte reserved for the register number argument to
1518    {start,stop}_memory, the maximum number of groups we can report
1519    things about is what fits in that byte.  */
1520 #define MAX_REGNUM 255
1521
1522 /* But patterns can have more than `MAX_REGNUM' registers.  We just
1523    ignore the excess.  */
1524 typedef unsigned regnum_t;
1525
1526
1527 /* Macros for the compile stack.  */
1528
1529 /* Since offsets can go either forwards or backwards, this type needs to
1530    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
1531 typedef int pattern_offset_t;
1532
1533 typedef struct
1534 {
1535   pattern_offset_t begalt_offset;
1536   pattern_offset_t fixup_alt_jump;
1537   pattern_offset_t inner_group_offset;
1538   pattern_offset_t laststart_offset;
1539   regnum_t regnum;
1540 } compile_stack_elt_t;
1541
1542
1543 typedef struct
1544 {
1545   compile_stack_elt_t *stack;
1546   unsigned size;
1547   unsigned avail;                       /* Offset of next open position.  */
1548 } compile_stack_type;
1549
1550
1551 #define INIT_COMPILE_STACK_SIZE 32
1552
1553 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
1554 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
1555
1556 /* The next available element.  */
1557 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1558
1559
1560 /* Set the bit for character C in a list.  */
1561 #define SET_LIST_BIT(c)                               \
1562   (b[((unsigned char) (c)) / BYTEWIDTH]               \
1563    |= 1 << (((unsigned char) c) % BYTEWIDTH))
1564
1565
1566 /* Get the next unsigned number in the uncompiled pattern.  */
1567 #define GET_UNSIGNED_NUMBER(num)                                        \
1568   { if (p != pend)                                                      \
1569      {                                                                  \
1570        PATFETCH (c);                                                    \
1571        while (ISDIGIT (c))                                              \
1572          {                                                              \
1573            if (num < 0)                                                 \
1574               num = 0;                                                  \
1575            num = num * 10 + c - '0';                                    \
1576            if (p == pend)                                               \
1577               break;                                                    \
1578            PATFETCH (c);                                                \
1579          }                                                              \
1580        }                                                                \
1581     }
1582
1583 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
1584
1585 #define IS_CHAR_CLASS(string)                                           \
1586    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
1587     || STREQ (string, "lower") || STREQ (string, "digit")               \
1588     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
1589     || STREQ (string, "space") || STREQ (string, "print")               \
1590     || STREQ (string, "punct") || STREQ (string, "graph")               \
1591     || STREQ (string, "cntrl") || STREQ (string, "blank"))
1592 \f
1593 #ifndef MATCH_MAY_ALLOCATE
1594
1595 /* If we cannot allocate large objects within re_match_2_internal,
1596    we make the fail stack and register vectors global.
1597    The fail stack, we grow to the maximum size when a regexp
1598    is compiled.
1599    The register vectors, we adjust in size each time we
1600    compile a regexp, according to the number of registers it needs.  */
1601
1602 static fail_stack_type fail_stack;
1603
1604 /* Size with which the following vectors are currently allocated.
1605    That is so we can make them bigger as needed,
1606    but never make them smaller.  */
1607 static int regs_allocated_size;
1608
1609 static const char **     regstart, **     regend;
1610 static const char ** old_regstart, ** old_regend;
1611 static const char **best_regstart, **best_regend;
1612 static register_info_type *reg_info;
1613 static const char **reg_dummy;
1614 static register_info_type *reg_info_dummy;
1615
1616 /* Make the register vectors big enough for NUM_REGS registers,
1617    but don't make them smaller.  */
1618
1619 static
1620 regex_grow_registers (num_regs)
1621      int num_regs;
1622 {
1623   if (num_regs > regs_allocated_size)
1624     {
1625       RETALLOC_IF (regstart,     num_regs, const char *);
1626       RETALLOC_IF (regend,       num_regs, const char *);
1627       RETALLOC_IF (old_regstart, num_regs, const char *);
1628       RETALLOC_IF (old_regend,   num_regs, const char *);
1629       RETALLOC_IF (best_regstart, num_regs, const char *);
1630       RETALLOC_IF (best_regend,  num_regs, const char *);
1631       RETALLOC_IF (reg_info,     num_regs, register_info_type);
1632       RETALLOC_IF (reg_dummy,    num_regs, const char *);
1633       RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
1634
1635       regs_allocated_size = num_regs;
1636     }
1637 }
1638
1639 #endif /* not MATCH_MAY_ALLOCATE */
1640 \f
1641 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1642    Returns one of error codes defined in `regex.h', or zero for success.
1643
1644    Assumes the `allocated' (and perhaps `buffer') and `translate'
1645    fields are set in BUFP on entry.
1646
1647    If it succeeds, results are put in BUFP (if it returns an error, the
1648    contents of BUFP are undefined):
1649      `buffer' is the compiled pattern;
1650      `syntax' is set to SYNTAX;
1651      `used' is set to the length of the compiled pattern;
1652      `fastmap_accurate' is zero;
1653      `re_nsub' is the number of subexpressions in PATTERN;
1654      `not_bol' and `not_eol' are zero;
1655
1656    The `fastmap' and `newline_anchor' fields are neither
1657    examined nor set.  */
1658
1659 /* Return, freeing storage we allocated.  */
1660 #define FREE_STACK_RETURN(value)                \
1661   return (free (compile_stack.stack), value)
1662
1663 static reg_errcode_t
1664 regex_compile (pattern, size, syntax, bufp)
1665      const char *pattern;
1666      int size;
1667      reg_syntax_t syntax;
1668      struct re_pattern_buffer *bufp;
1669 {
1670   /* We fetch characters from PATTERN here.  Even though PATTERN is
1671      `char *' (i.e., signed), we declare these variables as unsigned, so
1672      they can be reliably used as array indices.  */
1673   register unsigned char c, c1;
1674
1675   /* A random temporary spot in PATTERN.  */
1676   const char *p1;
1677
1678   /* Points to the end of the buffer, where we should append.  */
1679   register unsigned char *b;
1680
1681   /* Keeps track of unclosed groups.  */
1682   compile_stack_type compile_stack;
1683
1684   /* Points to the current (ending) position in the pattern.  */
1685   const char *p = pattern;
1686   const char *pend = pattern + size;
1687
1688   /* How to translate the characters in the pattern.  */
1689   RE_TRANSLATE_TYPE translate = bufp->translate;
1690
1691   /* Address of the count-byte of the most recently inserted `exactn'
1692      command.  This makes it possible to tell if a new exact-match
1693      character can be added to that command or if the character requires
1694      a new `exactn' command.  */
1695   unsigned char *pending_exact = 0;
1696
1697   /* Address of start of the most recently finished expression.
1698      This tells, e.g., postfix * where to find the start of its
1699      operand.  Reset at the beginning of groups and alternatives.  */
1700   unsigned char *laststart = 0;
1701
1702   /* Address of beginning of regexp, or inside of last group.  */
1703   unsigned char *begalt;
1704
1705   /* Place in the uncompiled pattern (i.e., the {) to
1706      which to go back if the interval is invalid.  */
1707   const char *beg_interval;
1708
1709   /* Address of the place where a forward jump should go to the end of
1710      the containing expression.  Each alternative of an `or' -- except the
1711      last -- ends with a forward jump of this sort.  */
1712   unsigned char *fixup_alt_jump = 0;
1713
1714   /* Counts open-groups as they are encountered.  Remembered for the
1715      matching close-group on the compile stack, so the same register
1716      number is put in the stop_memory as the start_memory.  */
1717   regnum_t regnum = 0;
1718
1719 #ifdef DEBUG
1720   DEBUG_PRINT1 ("\nCompiling pattern: ");
1721   if (debug)
1722     {
1723       unsigned debug_count;
1724
1725       for (debug_count = 0; debug_count < size; debug_count++)
1726         putchar (pattern[debug_count]);
1727       putchar ('\n');
1728     }
1729 #endif /* DEBUG */
1730
1731   /* Initialize the compile stack.  */
1732   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1733   if (compile_stack.stack == NULL)
1734     return REG_ESPACE;
1735
1736   compile_stack.size = INIT_COMPILE_STACK_SIZE;
1737   compile_stack.avail = 0;
1738
1739   /* Initialize the pattern buffer.  */
1740   bufp->syntax = syntax;
1741   bufp->fastmap_accurate = 0;
1742   bufp->not_bol = bufp->not_eol = 0;
1743
1744   /* Set `used' to zero, so that if we return an error, the pattern
1745      printer (for debugging) will think there's no pattern.  We reset it
1746      at the end.  */
1747   bufp->used = 0;
1748
1749   /* Always count groups, whether or not bufp->no_sub is set.  */
1750   bufp->re_nsub = 0;
1751
1752 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1753   /* Initialize the syntax table.  */
1754    init_syntax_once ();
1755 #endif
1756
1757   if (bufp->allocated == 0)
1758     {
1759       if (bufp->buffer)
1760         { /* If zero allocated, but buffer is non-null, try to realloc
1761              enough space.  This loses if buffer's address is bogus, but
1762              that is the user's responsibility.  */
1763           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1764         }
1765       else
1766         { /* Caller did not allocate a buffer.  Do it for them.  */
1767           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1768         }
1769       if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE);
1770
1771       bufp->allocated = INIT_BUF_SIZE;
1772     }
1773
1774   begalt = b = bufp->buffer;
1775
1776   /* Loop through the uncompiled pattern until we're at the end.  */
1777   while (p != pend)
1778     {
1779       PATFETCH (c);
1780
1781       switch (c)
1782         {
1783         case '^':
1784           {
1785             if (   /* If at start of pattern, it's an operator.  */
1786                    p == pattern + 1
1787                    /* If context independent, it's an operator.  */
1788                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1789                    /* Otherwise, depends on what's come before.  */
1790                 || at_begline_loc_p (pattern, p, syntax))
1791               BUF_PUSH (begline);
1792             else
1793               goto normal_char;
1794           }
1795           break;
1796
1797
1798         case '$':
1799           {
1800             if (   /* If at end of pattern, it's an operator.  */
1801                    p == pend
1802                    /* If context independent, it's an operator.  */
1803                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1804                    /* Otherwise, depends on what's next.  */
1805                 || at_endline_loc_p (p, pend, syntax))
1806                BUF_PUSH (endline);
1807              else
1808                goto normal_char;
1809            }
1810            break;
1811
1812
1813         case '+':
1814         case '?':
1815           if ((syntax & RE_BK_PLUS_QM)
1816               || (syntax & RE_LIMITED_OPS))
1817             goto normal_char;
1818         handle_plus:
1819         case '*':
1820           /* If there is no previous pattern... */
1821           if (!laststart)
1822             {
1823               if (syntax & RE_CONTEXT_INVALID_OPS)
1824                 FREE_STACK_RETURN (REG_BADRPT);
1825               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1826                 goto normal_char;
1827             }
1828
1829           {
1830             /* Are we optimizing this jump?  */
1831             boolean keep_string_p = false;
1832
1833             /* 1 means zero (many) matches is allowed.  */
1834             char zero_times_ok = 0, many_times_ok = 0;
1835
1836             /* If there is a sequence of repetition chars, collapse it
1837                down to just one (the right one).  We can't combine
1838                interval operators with these because of, e.g., `a{2}*',
1839                which should only match an even number of `a's.  */
1840
1841             for (;;)
1842               {
1843                 zero_times_ok |= c != '+';
1844                 many_times_ok |= c != '?';
1845
1846                 if (p == pend)
1847                   break;
1848
1849                 PATFETCH (c);
1850
1851                 if (c == '*'
1852                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1853                   ;
1854
1855                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
1856                   {
1857                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
1858
1859                     PATFETCH (c1);
1860                     if (!(c1 == '+' || c1 == '?'))
1861                       {
1862                         PATUNFETCH;
1863                         PATUNFETCH;
1864                         break;
1865                       }
1866
1867                     c = c1;
1868                   }
1869                 else
1870                   {
1871                     PATUNFETCH;
1872                     break;
1873                   }
1874
1875                 /* If we get here, we found another repeat character.  */
1876                }
1877
1878             /* Star, etc. applied to an empty pattern is equivalent
1879                to an empty pattern.  */
1880             if (!laststart)
1881               break;
1882
1883             /* Now we know whether or not zero matches is allowed
1884                and also whether or not two or more matches is allowed.  */
1885             if (many_times_ok)
1886               { /* More than one repetition is allowed, so put in at the
1887                    end a backward relative jump from `b' to before the next
1888                    jump we're going to put in below (which jumps from
1889                    laststart to after this jump).
1890
1891                    But if we are at the `*' in the exact sequence `.*\n',
1892                    insert an unconditional jump backwards to the .,
1893                    instead of the beginning of the loop.  This way we only
1894                    push a failure point once, instead of every time
1895                    through the loop.  */
1896                 assert (p - 1 > pattern);
1897
1898                 /* Allocate the space for the jump.  */
1899                 GET_BUFFER_SPACE (3);
1900
1901                 /* We know we are not at the first character of the pattern,
1902                    because laststart was nonzero.  And we've already
1903                    incremented `p', by the way, to be the character after
1904                    the `*'.  Do we have to do something analogous here
1905                    for null bytes, because of RE_DOT_NOT_NULL?  */
1906                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
1907                     && zero_times_ok
1908                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
1909                     && !(syntax & RE_DOT_NEWLINE))
1910                   { /* We have .*\n.  */
1911                     STORE_JUMP (jump, b, laststart);
1912                     keep_string_p = true;
1913                   }
1914                 else
1915                   /* Anything else.  */
1916                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
1917
1918                 /* We've added more stuff to the buffer.  */
1919                 b += 3;
1920               }
1921
1922             /* On failure, jump from laststart to b + 3, which will be the
1923                end of the buffer after this jump is inserted.  */
1924             GET_BUFFER_SPACE (3);
1925             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
1926                                        : on_failure_jump,
1927                          laststart, b + 3);
1928             pending_exact = 0;
1929             b += 3;
1930
1931             if (!zero_times_ok)
1932               {
1933                 /* At least one repetition is required, so insert a
1934                    `dummy_failure_jump' before the initial
1935                    `on_failure_jump' instruction of the loop. This
1936                    effects a skip over that instruction the first time
1937                    we hit that loop.  */
1938                 GET_BUFFER_SPACE (3);
1939                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
1940                 b += 3;
1941               }
1942             }
1943           break;
1944
1945
1946         case '.':
1947           laststart = b;
1948           BUF_PUSH (anychar);
1949           break;
1950
1951
1952         case '[':
1953           {
1954             boolean had_char_class = false;
1955
1956             if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
1957
1958             /* Ensure that we have enough space to push a charset: the
1959                opcode, the length count, and the bitset; 34 bytes in all.  */
1960             GET_BUFFER_SPACE (34);
1961
1962             laststart = b;
1963
1964             /* We test `*p == '^' twice, instead of using an if
1965                statement, so we only need one BUF_PUSH.  */
1966             BUF_PUSH (*p == '^' ? charset_not : charset);
1967             if (*p == '^')
1968               p++;
1969
1970             /* Remember the first position in the bracket expression.  */
1971             p1 = p;
1972
1973             /* Push the number of bytes in the bitmap.  */
1974             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
1975
1976             /* Clear the whole map.  */
1977             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
1978
1979             /* charset_not matches newline according to a syntax bit.  */
1980             if ((re_opcode_t) b[-2] == charset_not
1981                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
1982               SET_LIST_BIT ('\n');
1983
1984             /* Read in characters and ranges, setting map bits.  */
1985             for (;;)
1986               {
1987                 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
1988
1989                 PATFETCH (c);
1990
1991                 /* \ might escape characters inside [...] and [^...].  */
1992                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
1993                   {
1994                     if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
1995
1996                     PATFETCH (c1);
1997                     SET_LIST_BIT (c1);
1998                     continue;
1999                   }
2000
2001                 /* Could be the end of the bracket expression.  If it's
2002                    not (i.e., when the bracket expression is `[]' so
2003                    far), the ']' character bit gets set way below.  */
2004                 if (c == ']' && p != p1 + 1)
2005                   break;
2006
2007                 /* Look ahead to see if it's a range when the last thing
2008                    was a character class.  */
2009                 if (had_char_class && c == '-' && *p != ']')
2010                   FREE_STACK_RETURN (REG_ERANGE);
2011
2012                 /* Look ahead to see if it's a range when the last thing
2013                    was a character: if this is a hyphen not at the
2014                    beginning or the end of a list, then it's the range
2015                    operator.  */
2016                 if (c == '-'
2017                     && !(p - 2 >= pattern && p[-2] == '[')
2018                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2019                     && *p != ']')
2020                   {
2021                     reg_errcode_t ret
2022                       = compile_range (&p, pend, translate, syntax, b);
2023                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2024                   }
2025
2026                 else if (p[0] == '-' && p[1] != ']')
2027                   { /* This handles ranges made up of characters only.  */
2028                     reg_errcode_t ret;
2029
2030                     /* Move past the `-'.  */
2031                     PATFETCH (c1);
2032
2033                     ret = compile_range (&p, pend, translate, syntax, b);
2034                     if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2035                   }
2036
2037                 /* See if we're at the beginning of a possible character
2038                    class.  */
2039
2040                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2041                   { /* Leave room for the null.  */
2042                     char str[CHAR_CLASS_MAX_LENGTH + 1];
2043
2044                     PATFETCH (c);
2045                     c1 = 0;
2046
2047                     /* If pattern is `[[:'.  */
2048                     if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2049
2050                     for (;;)
2051                       {
2052                         PATFETCH (c);
2053                         if (c == ':' || c == ']' || p == pend
2054                             || c1 == CHAR_CLASS_MAX_LENGTH)
2055                           break;
2056                         str[c1++] = c;
2057                       }
2058                     str[c1] = '\0';
2059
2060                     /* If isn't a word bracketed by `[:' and:`]':
2061                        undo the ending character, the letters, and leave
2062                        the leading `:' and `[' (but set bits for them).  */
2063                     if (c == ':' && *p == ']')
2064                       {
2065                         int ch;
2066                         boolean is_alnum = STREQ (str, "alnum");
2067                         boolean is_alpha = STREQ (str, "alpha");
2068                         boolean is_blank = STREQ (str, "blank");
2069                         boolean is_cntrl = STREQ (str, "cntrl");
2070                         boolean is_digit = STREQ (str, "digit");
2071                         boolean is_graph = STREQ (str, "graph");
2072                         boolean is_lower = STREQ (str, "lower");
2073                         boolean is_print = STREQ (str, "print");
2074                         boolean is_punct = STREQ (str, "punct");
2075                         boolean is_space = STREQ (str, "space");
2076                         boolean is_upper = STREQ (str, "upper");
2077                         boolean is_xdigit = STREQ (str, "xdigit");
2078
2079                         if (!IS_CHAR_CLASS (str))
2080                           FREE_STACK_RETURN (REG_ECTYPE);
2081
2082                         /* Throw away the ] at the end of the character
2083                            class.  */
2084                         PATFETCH (c);
2085
2086                         if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2087
2088                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
2089                           {
2090                             /* This was split into 3 if's to
2091                                avoid an arbitrary limit in some compiler.  */
2092                             if (   (is_alnum  && ISALNUM (ch))
2093                                 || (is_alpha  && ISALPHA (ch))
2094                                 || (is_blank  && ISBLANK (ch))
2095                                 || (is_cntrl  && ISCNTRL (ch)))
2096                               SET_LIST_BIT (ch);
2097                             if (   (is_digit  && ISDIGIT (ch))
2098                                 || (is_graph  && ISGRAPH (ch))
2099                                 || (is_lower  && ISLOWER (ch))
2100                                 || (is_print  && ISPRINT (ch)))
2101                               SET_LIST_BIT (ch);
2102                             if (   (is_punct  && ISPUNCT (ch))
2103                                 || (is_space  && ISSPACE (ch))
2104                                 || (is_upper  && ISUPPER (ch))
2105                                 || (is_xdigit && ISXDIGIT (ch)))
2106                               SET_LIST_BIT (ch);
2107                           }
2108                         had_char_class = true;
2109                       }
2110                     else
2111                       {
2112                         c1++;
2113                         while (c1--)
2114                           PATUNFETCH;
2115                         SET_LIST_BIT ('[');
2116                         SET_LIST_BIT (':');
2117                         had_char_class = false;
2118                       }
2119                   }
2120                 else
2121                   {
2122                     had_char_class = false;
2123                     SET_LIST_BIT (c);
2124                   }
2125               }
2126
2127             /* Discard any (non)matching list bytes that are all 0 at the
2128                end of the map.  Decrease the map-length byte too.  */
2129             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
2130               b[-1]--;
2131             b += b[-1];
2132           }
2133           break;
2134
2135
2136         case '(':
2137           if (syntax & RE_NO_BK_PARENS)
2138             goto handle_open;
2139           else
2140             goto normal_char;
2141
2142
2143         case ')':
2144           if (syntax & RE_NO_BK_PARENS)
2145             goto handle_close;
2146           else
2147             goto normal_char;
2148
2149
2150         case '\n':
2151           if (syntax & RE_NEWLINE_ALT)
2152             goto handle_alt;
2153           else
2154             goto normal_char;
2155
2156
2157         case '|':
2158           if (syntax & RE_NO_BK_VBAR)
2159             goto handle_alt;
2160           else
2161             goto normal_char;
2162
2163
2164         case '{':
2165            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
2166              goto handle_interval;
2167            else
2168              goto normal_char;
2169
2170
2171         case '\\':
2172           if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2173
2174           /* Do not translate the character after the \, so that we can
2175              distinguish, e.g., \B from \b, even if we normally would
2176              translate, e.g., B to b.  */
2177           PATFETCH_RAW (c);
2178
2179           switch (c)
2180             {
2181             case '(':
2182               if (syntax & RE_NO_BK_PARENS)
2183                 goto normal_backslash;
2184
2185             handle_open:
2186               bufp->re_nsub++;
2187               regnum++;
2188
2189               if (COMPILE_STACK_FULL)
2190                 {
2191                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
2192                             compile_stack_elt_t);
2193                   if (compile_stack.stack == NULL) return REG_ESPACE;
2194
2195                   compile_stack.size <<= 1;
2196                 }
2197
2198               /* These are the values to restore when we hit end of this
2199                  group.  They are all relative offsets, so that if the
2200                  whole pattern moves because of realloc, they will still
2201                  be valid.  */
2202               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
2203               COMPILE_STACK_TOP.fixup_alt_jump
2204                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
2205               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
2206               COMPILE_STACK_TOP.regnum = regnum;
2207
2208               /* We will eventually replace the 0 with the number of
2209                  groups inner to this one.  But do not push a
2210                  start_memory for groups beyond the last one we can
2211                  represent in the compiled pattern.  */
2212               if (regnum <= MAX_REGNUM)
2213                 {
2214                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
2215                   BUF_PUSH_3 (start_memory, regnum, 0);
2216                 }
2217
2218               compile_stack.avail++;
2219
2220               fixup_alt_jump = 0;
2221               laststart = 0;
2222               begalt = b;
2223               /* If we've reached MAX_REGNUM groups, then this open
2224                  won't actually generate any code, so we'll have to
2225                  clear pending_exact explicitly.  */
2226               pending_exact = 0;
2227               break;
2228
2229
2230             case ')':
2231               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
2232
2233               if (COMPILE_STACK_EMPTY)
2234                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2235                   goto normal_backslash;
2236                 else
2237                   FREE_STACK_RETURN (REG_ERPAREN);
2238
2239             handle_close:
2240               if (fixup_alt_jump)
2241                 { /* Push a dummy failure point at the end of the
2242                      alternative for a possible future
2243                      `pop_failure_jump' to pop.  See comments at
2244                      `push_dummy_failure' in `re_match_2'.  */
2245                   BUF_PUSH (push_dummy_failure);
2246
2247                   /* We allocated space for this jump when we assigned
2248                      to `fixup_alt_jump', in the `handle_alt' case below.  */
2249                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
2250                 }
2251
2252               /* See similar code for backslashed left paren above.  */
2253               if (COMPILE_STACK_EMPTY)
2254                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2255                   goto normal_char;
2256                 else
2257                   FREE_STACK_RETURN (REG_ERPAREN);
2258
2259               /* Since we just checked for an empty stack above, this
2260                  ``can't happen''.  */
2261               assert (compile_stack.avail != 0);
2262               {
2263                 /* We don't just want to restore into `regnum', because
2264                    later groups should continue to be numbered higher,
2265                    as in `(ab)c(de)' -- the second group is #2.  */
2266                 regnum_t this_group_regnum;
2267
2268                 compile_stack.avail--;
2269                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
2270                 fixup_alt_jump
2271                   = COMPILE_STACK_TOP.fixup_alt_jump
2272                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1
2273                     : 0;
2274                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
2275                 this_group_regnum = COMPILE_STACK_TOP.regnum;
2276                 /* If we've reached MAX_REGNUM groups, then this open
2277                    won't actually generate any code, so we'll have to
2278                    clear pending_exact explicitly.  */
2279                 pending_exact = 0;
2280
2281                 /* We're at the end of the group, so now we know how many
2282                    groups were inside this one.  */
2283                 if (this_group_regnum <= MAX_REGNUM)
2284                   {
2285                     unsigned char *inner_group_loc
2286                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
2287
2288                     *inner_group_loc = regnum - this_group_regnum;
2289                     BUF_PUSH_3 (stop_memory, this_group_regnum,
2290                                 regnum - this_group_regnum);
2291                   }
2292               }
2293               break;
2294
2295
2296             case '|':                                   /* `\|'.  */
2297               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
2298                 goto normal_backslash;
2299             handle_alt:
2300               if (syntax & RE_LIMITED_OPS)
2301                 goto normal_char;
2302
2303               /* Insert before the previous alternative a jump which
2304                  jumps to this alternative if the former fails.  */
2305               GET_BUFFER_SPACE (3);
2306               INSERT_JUMP (on_failure_jump, begalt, b + 6);
2307               pending_exact = 0;
2308               b += 3;
2309
2310               /* The alternative before this one has a jump after it
2311                  which gets executed if it gets matched.  Adjust that
2312                  jump so it will jump to this alternative's analogous
2313                  jump (put in below, which in turn will jump to the next
2314                  (if any) alternative's such jump, etc.).  The last such
2315                  jump jumps to the correct final destination.  A picture:
2316                           _____ _____
2317                           |   | |   |
2318                           |   v |   v
2319                          a | b   | c
2320
2321                  If we are at `b', then fixup_alt_jump right now points to a
2322                  three-byte space after `a'.  We'll put in the jump, set
2323                  fixup_alt_jump to right after `b', and leave behind three
2324                  bytes which we'll fill in when we get to after `c'.  */
2325
2326               if (fixup_alt_jump)
2327                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2328
2329               /* Mark and leave space for a jump after this alternative,
2330                  to be filled in later either by next alternative or
2331                  when know we're at the end of a series of alternatives.  */
2332               fixup_alt_jump = b;
2333               GET_BUFFER_SPACE (3);
2334               b += 3;
2335
2336               laststart = 0;
2337               begalt = b;
2338               break;
2339
2340
2341             case '{':
2342               /* If \{ is a literal.  */
2343               if (!(syntax & RE_INTERVALS)
2344                      /* If we're at `\{' and it's not the open-interval
2345                         operator.  */
2346                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
2347                   || (p - 2 == pattern  &&  p == pend))
2348                 goto normal_backslash;
2349
2350             handle_interval:
2351               {
2352                 /* If got here, then the syntax allows intervals.  */
2353
2354                 /* At least (most) this many matches must be made.  */
2355                 int lower_bound = -1, upper_bound = -1;
2356
2357                 beg_interval = p - 1;
2358
2359                 if (p == pend)
2360                   {
2361                     if (syntax & RE_NO_BK_BRACES)
2362                       goto unfetch_interval;
2363                     else
2364                       FREE_STACK_RETURN (REG_EBRACE);
2365                   }
2366
2367                 GET_UNSIGNED_NUMBER (lower_bound);
2368
2369                 if (c == ',')
2370                   {
2371                     GET_UNSIGNED_NUMBER (upper_bound);
2372                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
2373                   }
2374                 else
2375                   /* Interval such as `{1}' => match exactly once. */
2376                   upper_bound = lower_bound;
2377
2378                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
2379                     || lower_bound > upper_bound)
2380                   {
2381                     if (syntax & RE_NO_BK_BRACES)
2382                       goto unfetch_interval;
2383                     else
2384                       FREE_STACK_RETURN (REG_BADBR);
2385                   }
2386
2387                 if (!(syntax & RE_NO_BK_BRACES))
2388                   {
2389                     if (c != '\\') FREE_STACK_RETURN (REG_EBRACE);
2390
2391                     PATFETCH (c);
2392                   }
2393
2394                 if (c != '}')
2395                   {
2396                     if (syntax & RE_NO_BK_BRACES)
2397                       goto unfetch_interval;
2398                     else
2399                       FREE_STACK_RETURN (REG_BADBR);
2400                   }
2401
2402                 /* We just parsed a valid interval.  */
2403
2404                 /* If it's invalid to have no preceding re.  */
2405                 if (!laststart)
2406                   {
2407                     if (syntax & RE_CONTEXT_INVALID_OPS)
2408                       FREE_STACK_RETURN (REG_BADRPT);
2409                     else if (syntax & RE_CONTEXT_INDEP_OPS)
2410                       laststart = b;
2411                     else
2412                       goto unfetch_interval;
2413                   }
2414
2415                 /* If the upper bound is zero, don't want to succeed at
2416                    all; jump from `laststart' to `b + 3', which will be
2417                    the end of the buffer after we insert the jump.  */
2418                  if (upper_bound == 0)
2419                    {
2420                      GET_BUFFER_SPACE (3);
2421                      INSERT_JUMP (jump, laststart, b + 3);
2422                      b += 3;
2423                    }
2424
2425                  /* Otherwise, we have a nontrivial interval.  When
2426                     we're all done, the pattern will look like:
2427                       set_number_at <jump count> <upper bound>
2428                       set_number_at <succeed_n count> <lower bound>
2429                       succeed_n <after jump addr> <succeed_n count>
2430                       <body of loop>
2431                       jump_n <succeed_n addr> <jump count>
2432                     (The upper bound and `jump_n' are omitted if
2433                     `upper_bound' is 1, though.)  */
2434                  else
2435                    { /* If the upper bound is > 1, we need to insert
2436                         more at the end of the loop.  */
2437                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
2438
2439                      GET_BUFFER_SPACE (nbytes);
2440
2441                      /* Initialize lower bound of the `succeed_n', even
2442                         though it will be set during matching by its
2443                         attendant `set_number_at' (inserted next),
2444                         because `re_compile_fastmap' needs to know.
2445                         Jump to the `jump_n' we might insert below.  */
2446                      INSERT_JUMP2 (succeed_n, laststart,
2447                                    b + 5 + (upper_bound > 1) * 5,
2448                                    lower_bound);
2449                      b += 5;
2450
2451                      /* Code to initialize the lower bound.  Insert
2452                         before the `succeed_n'.  The `5' is the last two
2453                         bytes of this `set_number_at', plus 3 bytes of
2454                         the following `succeed_n'.  */
2455                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
2456                      b += 5;
2457
2458                      if (upper_bound > 1)
2459                        { /* More than one repetition is allowed, so
2460                             append a backward jump to the `succeed_n'
2461                             that starts this interval.
2462
2463                             When we've reached this during matching,
2464                             we'll have matched the interval once, so
2465                             jump back only `upper_bound - 1' times.  */
2466                          STORE_JUMP2 (jump_n, b, laststart + 5,
2467                                       upper_bound - 1);
2468                          b += 5;
2469
2470                          /* The location we want to set is the second
2471                             parameter of the `jump_n'; that is `b-2' as
2472                             an absolute address.  `laststart' will be
2473                             the `set_number_at' we're about to insert;
2474                             `laststart+3' the number to set, the source
2475                             for the relative address.  But we are
2476                             inserting into the middle of the pattern --
2477                             so everything is getting moved up by 5.
2478                             Conclusion: (b - 2) - (laststart + 3) + 5,
2479                             i.e., b - laststart.
2480
2481                             We insert this at the beginning of the loop
2482                             so that if we fail during matching, we'll
2483                             reinitialize the bounds.  */
2484                          insert_op2 (set_number_at, laststart, b - laststart,
2485                                      upper_bound - 1, b);
2486                          b += 5;
2487                        }
2488                    }
2489                 pending_exact = 0;
2490                 beg_interval = NULL;
2491               }
2492               break;
2493
2494             unfetch_interval:
2495               /* If an invalid interval, match the characters as literals.  */
2496                assert (beg_interval);
2497                p = beg_interval;
2498                beg_interval = NULL;
2499
2500                /* normal_char and normal_backslash need `c'.  */
2501                PATFETCH (c);
2502
2503                if (!(syntax & RE_NO_BK_BRACES))
2504                  {
2505                    if (p > pattern  &&  p[-1] == '\\')
2506                      goto normal_backslash;
2507                  }
2508                goto normal_char;
2509
2510 #ifdef emacs
2511             /* There is no way to specify the before_dot and after_dot
2512                operators.  rms says this is ok.  --karl  */
2513             case '=':
2514               BUF_PUSH (at_dot);
2515               break;
2516
2517             case 's':
2518               laststart = b;
2519               PATFETCH (c);
2520               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
2521               break;
2522
2523             case 'S':
2524               laststart = b;
2525               PATFETCH (c);
2526               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
2527               break;
2528 #endif /* emacs */
2529
2530
2531             case 'w':
2532               laststart = b;
2533               BUF_PUSH (wordchar);
2534               break;
2535
2536
2537             case 'W':
2538               laststart = b;
2539               BUF_PUSH (notwordchar);
2540               break;
2541
2542
2543             case '<':
2544               BUF_PUSH (wordbeg);
2545               break;
2546
2547             case '>':
2548               BUF_PUSH (wordend);
2549               break;
2550
2551             case 'b':
2552               BUF_PUSH (wordbound);
2553               break;
2554
2555             case 'B':
2556               BUF_PUSH (notwordbound);
2557               break;
2558
2559             case '`':
2560               BUF_PUSH (begbuf);
2561               break;
2562
2563             case '\'':
2564               BUF_PUSH (endbuf);
2565               break;
2566
2567             case '1': case '2': case '3': case '4': case '5':
2568             case '6': case '7': case '8': case '9':
2569               if (syntax & RE_NO_BK_REFS)
2570                 goto normal_char;
2571
2572               c1 = c - '0';
2573
2574               if (c1 > regnum)
2575                 FREE_STACK_RETURN (REG_ESUBREG);
2576
2577               /* Can't back reference to a subexpression if inside of it.  */
2578               if (group_in_compile_stack (compile_stack, c1))
2579                 goto normal_char;
2580
2581               laststart = b;
2582               BUF_PUSH_2 (duplicate, c1);
2583               break;
2584
2585
2586             case '+':
2587             case '?':
2588               if (syntax & RE_BK_PLUS_QM)
2589                 goto handle_plus;
2590               else
2591                 goto normal_backslash;
2592
2593             default:
2594             normal_backslash:
2595               /* You might think it would be useful for \ to mean
2596                  not to translate; but if we don't translate it
2597                  it will never match anything.  */
2598               c = TRANSLATE (c);
2599               goto normal_char;
2600             }
2601           break;
2602
2603
2604         default:
2605         /* Expects the character in `c'.  */
2606         normal_char:
2607               /* If no exactn currently being built.  */
2608           if (!pending_exact
2609
2610               /* If last exactn not at current position.  */
2611               || pending_exact + *pending_exact + 1 != b
2612
2613               /* We have only one byte following the exactn for the count.  */
2614               || *pending_exact == (1 << BYTEWIDTH) - 1
2615
2616               /* If followed by a repetition operator.  */
2617               || *p == '*' || *p == '^'
2618               || ((syntax & RE_BK_PLUS_QM)
2619                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
2620                   : (*p == '+' || *p == '?'))
2621               || ((syntax & RE_INTERVALS)
2622                   && ((syntax & RE_NO_BK_BRACES)
2623                       ? *p == '{'
2624                       : (p[0] == '\\' && p[1] == '{'))))
2625             {
2626               /* Start building a new exactn.  */
2627
2628               laststart = b;
2629
2630               BUF_PUSH_2 (exactn, 0);
2631               pending_exact = b - 1;
2632             }
2633
2634           BUF_PUSH (c);
2635           (*pending_exact)++;
2636           break;
2637         } /* switch (c) */
2638     } /* while p != pend */
2639
2640
2641   /* Through the pattern now.  */
2642
2643   if (fixup_alt_jump)
2644     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2645
2646   if (!COMPILE_STACK_EMPTY)
2647     FREE_STACK_RETURN (REG_EPAREN);
2648
2649   /* If we don't want backtracking, force success
2650      the first time we reach the end of the compiled pattern.  */
2651   if (syntax & RE_NO_POSIX_BACKTRACKING)
2652     BUF_PUSH (succeed);
2653
2654   free (compile_stack.stack);
2655
2656   /* We have succeeded; set the length of the buffer.  */
2657   bufp->used = b - bufp->buffer;
2658
2659 #ifdef DEBUG
2660   if (debug)
2661     {
2662       DEBUG_PRINT1 ("\nCompiled pattern: \n");
2663       print_compiled_pattern (bufp);
2664     }
2665 #endif /* DEBUG */
2666
2667 #ifndef MATCH_MAY_ALLOCATE
2668   /* Initialize the failure stack to the largest possible stack.  This
2669      isn't necessary unless we're trying to avoid calling alloca in
2670      the search and match routines.  */
2671   {
2672     int num_regs = bufp->re_nsub + 1;
2673
2674     /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
2675        is strictly greater than re_max_failures, the largest possible stack
2676        is 2 * re_max_failures failure points.  */
2677     if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
2678       {
2679         fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
2680
2681 #ifdef emacs
2682         if (! fail_stack.stack)
2683           fail_stack.stack
2684             = (fail_stack_elt_t *) xmalloc (fail_stack.size
2685                                             * sizeof (fail_stack_elt_t));
2686         else
2687           fail_stack.stack
2688             = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
2689                                              (fail_stack.size
2690                                               * sizeof (fail_stack_elt_t)));
2691 #else /* not emacs */
2692         if (! fail_stack.stack)
2693           fail_stack.stack
2694             = (fail_stack_elt_t *) malloc (fail_stack.size
2695                                            * sizeof (fail_stack_elt_t));
2696         else
2697           fail_stack.stack
2698             = (fail_stack_elt_t *) realloc (fail_stack.stack,
2699                                             (fail_stack.size
2700                                              * sizeof (fail_stack_elt_t)));
2701 #endif /* not emacs */
2702       }
2703
2704     regex_grow_registers (num_regs);
2705   }
2706 #endif /* not MATCH_MAY_ALLOCATE */
2707
2708   return REG_NOERROR;
2709 } /* regex_compile */
2710 \f
2711 /* Subroutines for `regex_compile'.  */
2712
2713 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
2714
2715 static void
2716 store_op1 (op, loc, arg)
2717     re_opcode_t op;
2718     unsigned char *loc;
2719     int arg;
2720 {
2721   *loc = (unsigned char) op;
2722   STORE_NUMBER (loc + 1, arg);
2723 }
2724
2725
2726 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
2727
2728 static void
2729 store_op2 (op, loc, arg1, arg2)
2730     re_opcode_t op;
2731     unsigned char *loc;
2732     int arg1, arg2;
2733 {
2734   *loc = (unsigned char) op;
2735   STORE_NUMBER (loc + 1, arg1);
2736   STORE_NUMBER (loc + 3, arg2);
2737 }
2738
2739
2740 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2741    for OP followed by two-byte integer parameter ARG.  */
2742
2743 static void
2744 insert_op1 (op, loc, arg, end)
2745     re_opcode_t op;
2746     unsigned char *loc;
2747     int arg;
2748     unsigned char *end;
2749 {
2750   register unsigned char *pfrom = end;
2751   register unsigned char *pto = end + 3;
2752
2753   while (pfrom != loc)
2754     *--pto = *--pfrom;
2755
2756   store_op1 (op, loc, arg);
2757 }
2758
2759
2760 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
2761
2762 static void
2763 insert_op2 (op, loc, arg1, arg2, end)
2764     re_opcode_t op;
2765     unsigned char *loc;
2766     int arg1, arg2;
2767     unsigned char *end;
2768 {
2769   register unsigned char *pfrom = end;
2770   register unsigned char *pto = end + 5;
2771
2772   while (pfrom != loc)
2773     *--pto = *--pfrom;
2774
2775   store_op2 (op, loc, arg1, arg2);
2776 }
2777
2778
2779 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
2780    after an alternative or a begin-subexpression.  We assume there is at
2781    least one character before the ^.  */
2782
2783 static boolean
2784 at_begline_loc_p (pattern, p, syntax)
2785     const char *pattern, *p;
2786     reg_syntax_t syntax;
2787 {
2788   const char *prev = p - 2;
2789   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2790
2791   return
2792        /* After a subexpression?  */
2793        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2794        /* After an alternative?  */
2795     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2796 }
2797
2798
2799 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
2800    at least one character after the $, i.e., `P < PEND'.  */
2801
2802 static boolean
2803 at_endline_loc_p (p, pend, syntax)
2804     const char *p, *pend;
2805     int syntax;
2806 {
2807   const char *next = p;
2808   boolean next_backslash = *next == '\\';
2809   const char *next_next = p + 1 < pend ? p + 1 : 0;
2810
2811   return
2812        /* Before a subexpression?  */
2813        (syntax & RE_NO_BK_PARENS ? *next == ')'
2814         : next_backslash && next_next && *next_next == ')')
2815        /* Before an alternative?  */
2816     || (syntax & RE_NO_BK_VBAR ? *next == '|'
2817         : next_backslash && next_next && *next_next == '|');
2818 }
2819
2820
2821 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
2822    false if it's not.  */
2823
2824 static boolean
2825 group_in_compile_stack (compile_stack, regnum)
2826     compile_stack_type compile_stack;
2827     regnum_t regnum;
2828 {
2829   int this_element;
2830
2831   for (this_element = compile_stack.avail - 1;
2832        this_element >= 0;
2833        this_element--)
2834     if (compile_stack.stack[this_element].regnum == regnum)
2835       return true;
2836
2837   return false;
2838 }
2839
2840
2841 /* Read the ending character of a range (in a bracket expression) from the
2842    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
2843    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
2844    Then we set the translation of all bits between the starting and
2845    ending characters (inclusive) in the compiled pattern B.
2846
2847    Return an error code.
2848
2849    We use these short variable names so we can use the same macros as
2850    `regex_compile' itself.  */
2851
2852 static reg_errcode_t
2853 compile_range (p_ptr, pend, translate, syntax, b)
2854     const char **p_ptr, *pend;
2855     RE_TRANSLATE_TYPE translate;
2856     reg_syntax_t syntax;
2857     unsigned char *b;
2858 {
2859   unsigned this_char;
2860
2861   const char *p = *p_ptr;
2862   unsigned int range_start, range_end;
2863
2864   if (p == pend)
2865     return REG_ERANGE;
2866
2867   /* Even though the pattern is a signed `char *', we need to fetch
2868      with unsigned char *'s; if the high bit of the pattern character
2869      is set, the range endpoints will be negative if we fetch using a
2870      signed char *.
2871
2872      We also want to fetch the endpoints without translating them; the
2873      appropriate translation is done in the bit-setting loop below.  */
2874   /* The SVR4 compiler on the 3B2 had trouble with unsigned const char *.  */
2875   range_start = ((const unsigned char *) p)[-2];
2876   range_end   = ((const unsigned char *) p)[0];
2877
2878   /* Have to increment the pointer into the pattern string, so the
2879      caller isn't still at the ending character.  */
2880   (*p_ptr)++;
2881
2882   /* If the start is after the end, the range is empty.  */
2883   if (range_start > range_end)
2884     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2885
2886   /* Here we see why `this_char' has to be larger than an `unsigned
2887      char' -- the range is inclusive, so if `range_end' == 0xff
2888      (assuming 8-bit characters), we would otherwise go into an infinite
2889      loop, since all characters <= 0xff.  */
2890   for (this_char = range_start; this_char <= range_end; this_char++)
2891     {
2892       SET_LIST_BIT (TRANSLATE (this_char));
2893     }
2894
2895   return REG_NOERROR;
2896 }
2897 \f
2898 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2899    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
2900    characters can start a string that matches the pattern.  This fastmap
2901    is used by re_search to skip quickly over impossible starting points.
2902
2903    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2904    area as BUFP->fastmap.
2905
2906    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2907    the pattern buffer.
2908
2909    Returns 0 if we succeed, -2 if an internal error.   */
2910
2911 int
2912 re_compile_fastmap (bufp)
2913      struct re_pattern_buffer *bufp;
2914 {
2915   int j, k;
2916 #ifdef MATCH_MAY_ALLOCATE
2917   fail_stack_type fail_stack;
2918 #endif
2919 #ifndef REGEX_MALLOC
2920   char *destination;
2921 #endif
2922   /* We don't push any register information onto the failure stack.  */
2923   unsigned num_regs = 0;
2924
2925   register char *fastmap = bufp->fastmap;
2926   unsigned char *pattern = bufp->buffer;
2927   unsigned long size = bufp->used;
2928   unsigned char *p = pattern;
2929   register unsigned char *pend = pattern + size;
2930
2931   /* This holds the pointer to the failure stack, when
2932      it is allocated relocatably.  */
2933   fail_stack_elt_t *failure_stack_ptr;
2934
2935   /* Assume that each path through the pattern can be null until
2936      proven otherwise.  We set this false at the bottom of switch
2937      statement, to which we get only if a particular path doesn't
2938      match the empty string.  */
2939   boolean path_can_be_null = true;
2940
2941   /* We aren't doing a `succeed_n' to begin with.  */
2942   boolean succeed_n_p = false;
2943
2944   assert (fastmap != NULL && p != NULL);
2945
2946   INIT_FAIL_STACK ();
2947   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
2948   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
2949   bufp->can_be_null = 0;
2950
2951   while (1)
2952     {
2953       if (p == pend || *p == succeed)
2954         {
2955           /* We have reached the (effective) end of pattern.  */
2956           if (!FAIL_STACK_EMPTY ())
2957             {
2958               bufp->can_be_null |= path_can_be_null;
2959
2960               /* Reset for next path.  */
2961               path_can_be_null = true;
2962
2963               p = fail_stack.stack[--fail_stack.avail].pointer;
2964
2965               continue;
2966             }
2967           else
2968             break;
2969         }
2970
2971       /* We should never be about to go beyond the end of the pattern.  */
2972       assert (p < pend);
2973
2974       switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
2975         {
2976
2977         /* I guess the idea here is to simply not bother with a fastmap
2978            if a backreference is used, since it's too hard to figure out
2979            the fastmap for the corresponding group.  Setting
2980            `can_be_null' stops `re_search_2' from using the fastmap, so
2981            that is all we do.  */
2982         case duplicate:
2983           bufp->can_be_null = 1;
2984           goto done;
2985
2986
2987       /* Following are the cases which match a character.  These end
2988          with `break'.  */
2989
2990         case exactn:
2991           fastmap[p[1]] = 1;
2992           break;
2993
2994
2995         case charset:
2996           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2997             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
2998               fastmap[j] = 1;
2999           break;
3000
3001
3002         case charset_not:
3003           /* Chars beyond end of map must be allowed.  */
3004           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
3005             fastmap[j] = 1;
3006
3007           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
3008             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
3009               fastmap[j] = 1;
3010           break;
3011
3012
3013         case wordchar:
3014           for (j = 0; j < (1 << BYTEWIDTH); j++)
3015             if (SYNTAX (j) == Sword)
3016               fastmap[j] = 1;
3017           break;
3018
3019
3020         case notwordchar:
3021           for (j = 0; j < (1 << BYTEWIDTH); j++)
3022             if (SYNTAX (j) != Sword)
3023               fastmap[j] = 1;
3024           break;
3025
3026
3027         case anychar:
3028           {
3029             int fastmap_newline = fastmap['\n'];
3030
3031             /* `.' matches anything ...  */
3032             for (j = 0; j < (1 << BYTEWIDTH); j++)
3033               fastmap[j] = 1;
3034
3035             /* ... except perhaps newline.  */
3036             if (!(bufp->syntax & RE_DOT_NEWLINE))
3037               fastmap['\n'] = fastmap_newline;
3038
3039             /* Return if we have already set `can_be_null'; if we have,
3040                then the fastmap is irrelevant.  Something's wrong here.  */
3041             else if (bufp->can_be_null)
3042               goto done;
3043
3044             /* Otherwise, have to check alternative paths.  */
3045             break;
3046           }
3047
3048 #ifdef emacs
3049         case syntaxspec:
3050           k = *p++;
3051           for (j = 0; j < (1 << BYTEWIDTH); j++)
3052             if (SYNTAX (j) == (enum syntaxcode) k)
3053               fastmap[j] = 1;
3054           break;
3055
3056
3057         case notsyntaxspec:
3058           k = *p++;
3059           for (j = 0; j < (1 << BYTEWIDTH); j++)
3060             if (SYNTAX (j) != (enum syntaxcode) k)
3061               fastmap[j] = 1;
3062           break;
3063
3064
3065       /* All cases after this match the empty string.  These end with
3066          `continue'.  */
3067
3068
3069         case before_dot:
3070         case at_dot:
3071         case after_dot:
3072           continue;
3073 #endif /* emacs */
3074
3075
3076         case no_op:
3077         case begline:
3078         case endline:
3079         case begbuf:
3080         case endbuf:
3081         case wordbound:
3082         case notwordbound:
3083         case wordbeg:
3084         case wordend:
3085         case push_dummy_failure:
3086           continue;
3087
3088
3089         case jump_n:
3090         case pop_failure_jump:
3091         case maybe_pop_jump:
3092         case jump:
3093         case jump_past_alt:
3094         case dummy_failure_jump:
3095           EXTRACT_NUMBER_AND_INCR (j, p);
3096           p += j;
3097           if (j > 0)
3098             continue;
3099
3100           /* Jump backward implies we just went through the body of a
3101              loop and matched nothing.  Opcode jumped to should be
3102              `on_failure_jump' or `succeed_n'.  Just treat it like an
3103              ordinary jump.  For a * loop, it has pushed its failure
3104              point already; if so, discard that as redundant.  */
3105           if ((re_opcode_t) *p != on_failure_jump
3106               && (re_opcode_t) *p != succeed_n)
3107             continue;
3108
3109           p++;
3110           EXTRACT_NUMBER_AND_INCR (j, p);
3111           p += j;
3112
3113           /* If what's on the stack is where we are now, pop it.  */
3114           if (!FAIL_STACK_EMPTY ()
3115               && fail_stack.stack[fail_stack.avail - 1].pointer == p)
3116             fail_stack.avail--;
3117
3118           continue;
3119
3120
3121         case on_failure_jump:
3122         case on_failure_keep_string_jump:
3123         handle_on_failure_jump:
3124           EXTRACT_NUMBER_AND_INCR (j, p);
3125
3126           /* For some patterns, e.g., `(a?)?', `p+j' here points to the
3127              end of the pattern.  We don't want to push such a point,
3128              since when we restore it above, entering the switch will
3129              increment `p' past the end of the pattern.  We don't need
3130              to push such a point since we obviously won't find any more
3131              fastmap entries beyond `pend'.  Such a pattern can match
3132              the null string, though.  */
3133           if (p + j < pend)
3134             {
3135               if (!PUSH_PATTERN_OP (p + j, fail_stack))
3136                 {
3137                   RESET_FAIL_STACK ();
3138                   return -2;
3139                 }
3140             }
3141           else
3142             bufp->can_be_null = 1;
3143
3144           if (succeed_n_p)
3145             {
3146               EXTRACT_NUMBER_AND_INCR (k, p);   /* Skip the n.  */
3147               succeed_n_p = false;
3148             }
3149
3150           continue;
3151
3152
3153         case succeed_n:
3154           /* Get to the number of times to succeed.  */
3155           p += 2;
3156
3157           /* Increment p past the n for when k != 0.  */
3158           EXTRACT_NUMBER_AND_INCR (k, p);
3159           if (k == 0)
3160             {
3161               p -= 4;
3162               succeed_n_p = true;  /* Spaghetti code alert.  */
3163               goto handle_on_failure_jump;
3164             }
3165           continue;
3166
3167
3168         case set_number_at:
3169           p += 4;
3170           continue;
3171
3172
3173         case start_memory:
3174         case stop_memory:
3175           p += 2;
3176           continue;
3177
3178
3179         default:
3180           abort (); /* We have listed all the cases.  */
3181         } /* switch *p++ */
3182
3183       /* Getting here means we have found the possible starting
3184          characters for one path of the pattern -- and that the empty
3185          string does not match.  We need not follow this path further.
3186          Instead, look at the next alternative (remembered on the
3187          stack), or quit if no more.  The test at the top of the loop
3188          does these things.  */
3189       path_can_be_null = false;
3190       p = pend;
3191     } /* while p */
3192
3193   /* Set `can_be_null' for the last path (also the first path, if the
3194      pattern is empty).  */
3195   bufp->can_be_null |= path_can_be_null;
3196
3197  done:
3198   RESET_FAIL_STACK ();
3199   return 0;
3200 } /* re_compile_fastmap */
3201 \f
3202 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
3203    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
3204    this memory for recording register information.  STARTS and ENDS
3205    must be allocated using the malloc library routine, and must each
3206    be at least NUM_REGS * sizeof (regoff_t) bytes long.
3207
3208    If NUM_REGS == 0, then subsequent matches should allocate their own
3209    register data.
3210
3211    Unless this function is called, the first search or match using
3212    PATTERN_BUFFER will allocate its own register data, without
3213    freeing the old data.  */
3214
3215 void
3216 re_set_registers (bufp, regs, num_regs, starts, ends)
3217     struct re_pattern_buffer *bufp;
3218     struct re_registers *regs;
3219     unsigned num_regs;
3220     regoff_t *starts, *ends;
3221 {
3222   if (num_regs)
3223     {
3224       bufp->regs_allocated = REGS_REALLOCATE;
3225       regs->num_regs = num_regs;
3226       regs->start = starts;
3227       regs->end = ends;
3228     }
3229   else
3230     {
3231       bufp->regs_allocated = REGS_UNALLOCATED;
3232       regs->num_regs = 0;
3233       regs->start = regs->end = (regoff_t *) 0;
3234     }
3235 }
3236 \f
3237 /* Searching routines.  */
3238
3239 /* Like re_search_2, below, but only one string is specified, and
3240    doesn't let you say where to stop matching. */
3241
3242 int
3243 re_search (bufp, string, size, startpos, range, regs)
3244      struct re_pattern_buffer *bufp;
3245      const char *string;
3246      int size, startpos, range;
3247      struct re_registers *regs;
3248 {
3249   return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
3250                       regs, size);
3251 }
3252
3253
3254 /* Using the compiled pattern in BUFP->buffer, first tries to match the
3255    virtual concatenation of STRING1 and STRING2, starting first at index
3256    STARTPOS, then at STARTPOS + 1, and so on.
3257
3258    STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
3259
3260    RANGE is how far to scan while trying to match.  RANGE = 0 means try
3261    only at STARTPOS; in general, the last start tried is STARTPOS +
3262    RANGE.
3263
3264    In REGS, return the indices of the virtual concatenation of STRING1
3265    and STRING2 that matched the entire BUFP->buffer and its contained
3266    subexpressions.
3267
3268    Do not consider matching one past the index STOP in the virtual
3269    concatenation of STRING1 and STRING2.
3270
3271    We return either the position in the strings at which the match was
3272    found, -1 if no match, or -2 if error (such as failure
3273    stack overflow).  */
3274
3275 int
3276 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
3277      struct re_pattern_buffer *bufp;
3278      const char *string1, *string2;
3279      int size1, size2;
3280      int startpos;
3281      int range;
3282      struct re_registers *regs;
3283      int stop;
3284 {
3285   int val;
3286   register char *fastmap = bufp->fastmap;
3287   register RE_TRANSLATE_TYPE translate = bufp->translate;
3288   int total_size = size1 + size2;
3289   int endpos = startpos + range;
3290
3291   /* Check for out-of-range STARTPOS.  */
3292   if (startpos < 0 || startpos > total_size)
3293     return -1;
3294
3295   /* Fix up RANGE if it might eventually take us outside
3296      the virtual concatenation of STRING1 and STRING2.
3297      Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE.  */
3298   if (endpos < 0)
3299     range = 0 - startpos;
3300   else if (endpos > total_size)
3301     range = total_size - startpos;
3302
3303   /* If the search isn't to be a backwards one, don't waste time in a
3304      search for a pattern that must be anchored.  */
3305   if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
3306     {
3307       if (startpos > 0)