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