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