2edcc42f8e6ef330cb0c853a39fd9b2301797a64
[gnulib.git] / lib / 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 Free Software Foundation, Inc.
7
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2, or (at your option)
11    any later version.
12
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
21
22 /* AIX requires this to be the first thing in the file. */
23 #if defined (_AIX) && !defined (REGEX_MALLOC)
24   #pragma alloca
25 #endif
26
27 #define _GNU_SOURCE
28
29 #ifdef HAVE_CONFIG_H
30 #if defined (emacs) || defined (CONFIG_BROKETS)
31 /* We use <config.h> instead of "config.h" so that a compilation
32    using -I. -I$srcdir will use ./config.h rather than $srcdir/config.h
33    (which it would do because it found this file in $srcdir).  */
34 #include <config.h>
35 #else
36 #include "config.h"
37 #endif
38 #endif
39
40 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
41 #include <sys/types.h>
42
43 /* The `emacs' switch turns on certain matching commands
44    that make sense only in Emacs. */
45 #ifdef emacs
46
47 #include "lisp.h"
48 #include "buffer.h"
49 #include "syntax.h"
50
51 /* Emacs uses `NULL' as a predicate.  */
52 #undef NULL
53
54 #else  /* not emacs */
55
56 #ifdef STDC_HEADERS
57 #include <stdlib.h>
58 #else
59 char *malloc ();
60 char *realloc ();
61 #endif
62
63
64 /* We used to test for `BSTRING' here, but only GCC and Emacs define
65    `BSTRING', as far as I know, and neither of them use this code.  */
66 #ifndef INHIBIT_STRING_HEADER
67 #if HAVE_STRING_H || STDC_HEADERS
68 #include <string.h>
69 #ifndef bcmp
70 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n))
71 #endif
72 #ifndef bcopy
73 #define bcopy(s, d, n)  memcpy ((d), (s), (n))
74 #endif
75 #ifndef bzero
76 #define bzero(s, n)     memset ((s), 0, (n))
77 #endif
78 #else
79 #include <strings.h>
80 #endif
81 #endif
82
83 /* Define the syntax stuff for \<, \>, etc.  */
84
85 /* This must be nonzero for the wordchar and notwordchar pattern
86    commands in re_match_2.  */
87 #ifndef Sword 
88 #define Sword 1
89 #endif
90
91 #ifdef SYNTAX_TABLE
92
93 extern char *re_syntax_table;
94
95 #else /* not SYNTAX_TABLE */
96
97 /* How many characters in the character set.  */
98 #define CHAR_SET_SIZE 256
99
100 static char re_syntax_table[CHAR_SET_SIZE];
101
102 static void
103 init_syntax_once ()
104 {
105    register int c;
106    static int done = 0;
107
108    if (done)
109      return;
110
111    bzero (re_syntax_table, sizeof re_syntax_table);
112
113    for (c = 'a'; c <= 'z'; c++)
114      re_syntax_table[c] = Sword;
115
116    for (c = 'A'; c <= 'Z'; c++)
117      re_syntax_table[c] = Sword;
118
119    for (c = '0'; c <= '9'; c++)
120      re_syntax_table[c] = Sword;
121
122    re_syntax_table['_'] = Sword;
123
124    done = 1;
125 }
126
127 #endif /* not SYNTAX_TABLE */
128
129 #define SYNTAX(c) re_syntax_table[c]
130
131 #endif /* not emacs */
132 \f
133 /* Get the interface, including the syntax bits.  */
134 #include "regex.h"
135
136 /* isalpha etc. are used for the character classes.  */
137 #include <ctype.h>
138
139 /* Jim Meyering writes:
140
141    "... Some ctype macros are valid only for character codes that
142    isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
143    using /bin/cc or gcc but without giving an ansi option).  So, all
144    ctype uses should be through macros like ISPRINT...  If
145    STDC_HEADERS is defined, then autoconf has verified that the ctype
146    macros don't need to be guarded with references to isascii. ...
147    Defining isascii to 1 should let any compiler worth its salt
148    eliminate the && through constant folding."  */
149
150 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
151 #define ISASCII(c) 1
152 #else
153 #define ISASCII(c) isascii(c)
154 #endif
155
156 #ifdef isblank
157 #define ISBLANK(c) (ISASCII (c) && isblank (c))
158 #else
159 #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
160 #endif
161 #ifdef isgraph
162 #define ISGRAPH(c) (ISASCII (c) && isgraph (c))
163 #else
164 #define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
165 #endif
166
167 #define ISPRINT(c) (ISASCII (c) && isprint (c))
168 #define ISDIGIT(c) (ISASCII (c) && isdigit (c))
169 #define ISALNUM(c) (ISASCII (c) && isalnum (c))
170 #define ISALPHA(c) (ISASCII (c) && isalpha (c))
171 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
172 #define ISLOWER(c) (ISASCII (c) && islower (c))
173 #define ISPUNCT(c) (ISASCII (c) && ispunct (c))
174 #define ISSPACE(c) (ISASCII (c) && isspace (c))
175 #define ISUPPER(c) (ISASCII (c) && isupper (c))
176 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
177
178 #ifndef NULL
179 #define NULL 0
180 #endif
181
182 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
183    since ours (we hope) works properly with all combinations of
184    machines, compilers, `char' and `unsigned char' argument types.
185    (Per Bothner suggested the basic approach.)  */
186 #undef SIGN_EXTEND_CHAR
187 #if __STDC__
188 #define SIGN_EXTEND_CHAR(c) ((signed char) (c))
189 #else  /* not __STDC__ */
190 /* As in Harbison and Steele.  */
191 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
192 #endif
193 \f
194 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
195    use `alloca' instead of `malloc'.  This is because using malloc in
196    re_search* or re_match* could cause memory leaks when C-g is used in
197    Emacs; also, malloc is slower and causes storage fragmentation.  On
198    the other hand, malloc is more portable, and easier to debug.  
199    
200    Because we sometimes use alloca, some routines have to be macros,
201    not functions -- `alloca'-allocated space disappears at the end of the
202    function it is called in.  */
203
204 #ifdef REGEX_MALLOC
205
206 #define REGEX_ALLOCATE malloc
207 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
208
209 #else /* not REGEX_MALLOC  */
210
211 /* Emacs already defines alloca, sometimes.  */
212 #ifndef alloca
213
214 /* Make alloca work the best possible way.  */
215 #ifdef __GNUC__
216 #define alloca __builtin_alloca
217 #else /* not __GNUC__ */
218 #if HAVE_ALLOCA_H
219 #include <alloca.h>
220 #else /* not __GNUC__ or HAVE_ALLOCA_H */
221 #ifndef _AIX /* Already did AIX, up at the top.  */
222 char *alloca ();
223 #endif /* not _AIX */
224 #endif /* not HAVE_ALLOCA_H */ 
225 #endif /* not __GNUC__ */
226
227 #endif /* not alloca */
228
229 #define REGEX_ALLOCATE alloca
230
231 /* Assumes a `char *destination' variable.  */
232 #define REGEX_REALLOCATE(source, osize, nsize)                          \
233   (destination = (char *) alloca (nsize),                               \
234    bcopy (source, destination, osize),                                  \
235    destination)
236
237 #endif /* not REGEX_MALLOC */
238
239
240 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
241    `string1' or just past its end.  This works if PTR is NULL, which is
242    a good thing.  */
243 #define FIRST_STRING_P(ptr)                                     \
244   (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
245
246 /* (Re)Allocate N items of type T using malloc, or fail.  */
247 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
248 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
249 #define RETALLOC_IF(addr, n, t) \
250   if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
251 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
252
253 #define BYTEWIDTH 8 /* In bits.  */
254
255 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
256
257 #undef MAX
258 #undef MIN
259 #define MAX(a, b) ((a) > (b) ? (a) : (b))
260 #define MIN(a, b) ((a) < (b) ? (a) : (b))
261
262 typedef char boolean;
263 #define false 0
264 #define true 1
265
266 static int re_match_2_internal ();
267 \f
268 /* These are the command codes that appear in compiled regular
269    expressions.  Some opcodes are followed by argument bytes.  A
270    command code can specify any interpretation whatsoever for its
271    arguments.  Zero bytes may appear in the compiled regular expression.
272
273    The value of `exactn' is needed in search.c (search_buffer) in Emacs.
274    So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
275    `exactn' we use here must also be 1.  */
276
277 typedef enum
278 {
279   no_op = 0,
280
281         /* Followed by one byte giving n, then by n literal bytes.  */
282   exactn = 1,
283
284         /* Matches any (more or less) character.  */
285   anychar,
286
287         /* Matches any one char belonging to specified set.  First
288            following byte is number of bitmap bytes.  Then come bytes
289            for a bitmap saying which chars are in.  Bits in each byte
290            are ordered low-bit-first.  A character is in the set if its
291            bit is 1.  A character too large to have a bit in the map is
292            automatically not in the set.  */
293   charset,
294
295         /* Same parameters as charset, but match any character that is
296            not one of those specified.  */
297   charset_not,
298
299         /* Start remembering the text that is matched, for storing in a
300            register.  Followed by one byte with the register number, in
301            the range 0 to one less than the pattern buffer's re_nsub
302            field.  Then followed by one byte with the number of groups
303            inner to this one.  (This last has to be part of the
304            start_memory only because we need it in the on_failure_jump
305            of re_match_2.)  */
306   start_memory,
307
308         /* Stop remembering the text that is matched and store it in a
309            memory register.  Followed by one byte with the register
310            number, in the range 0 to one less than `re_nsub' in the
311            pattern buffer, and one byte with the number of inner groups,
312            just like `start_memory'.  (We need the number of inner
313            groups here because we don't have any easy way of finding the
314            corresponding start_memory when we're at a stop_memory.)  */
315   stop_memory,
316
317         /* Match a duplicate of something remembered. Followed by one
318            byte containing the register number.  */
319   duplicate,
320
321         /* Fail unless at beginning of line.  */
322   begline,
323
324         /* Fail unless at end of line.  */
325   endline,
326
327         /* Succeeds if at beginning of buffer (if emacs) or at beginning
328            of string to be matched (if not).  */
329   begbuf,
330
331         /* Analogously, for end of buffer/string.  */
332   endbuf,
333  
334         /* Followed by two byte relative address to which to jump.  */
335   jump, 
336
337         /* Same as jump, but marks the end of an alternative.  */
338   jump_past_alt,
339
340         /* Followed by two-byte relative address of place to resume at
341            in case of failure.  */
342   on_failure_jump,
343         
344         /* Like on_failure_jump, but pushes a placeholder instead of the
345            current string position when executed.  */
346   on_failure_keep_string_jump,
347   
348         /* Throw away latest failure point and then jump to following
349            two-byte relative address.  */
350   pop_failure_jump,
351
352         /* Change to pop_failure_jump if know won't have to backtrack to
353            match; otherwise change to jump.  This is used to jump
354            back to the beginning of a repeat.  If what follows this jump
355            clearly won't match what the repeat does, such that we can be
356            sure that there is no use backtracking out of repetitions
357            already matched, then we change it to a pop_failure_jump.
358            Followed by two-byte address.  */
359   maybe_pop_jump,
360
361         /* Jump to following two-byte address, and push a dummy failure
362            point. This failure point will be thrown away if an attempt
363            is made to use it for a failure.  A `+' construct makes this
364            before the first repeat.  Also used as an intermediary kind
365            of jump when compiling an alternative.  */
366   dummy_failure_jump,
367
368         /* Push a dummy failure point and continue.  Used at the end of
369            alternatives.  */
370   push_dummy_failure,
371
372         /* Followed by two-byte relative address and two-byte number n.
373            After matching N times, jump to the address upon failure.  */
374   succeed_n,
375
376         /* Followed by two-byte relative address, and two-byte number n.
377            Jump to the address N times, then fail.  */
378   jump_n,
379
380         /* Set the following two-byte relative address to the
381            subsequent two-byte number.  The address *includes* the two
382            bytes of number.  */
383   set_number_at,
384
385   wordchar,     /* Matches any word-constituent character.  */
386   notwordchar,  /* Matches any char that is not a word-constituent.  */
387
388   wordbeg,      /* Succeeds if at word beginning.  */
389   wordend,      /* Succeeds if at word end.  */
390
391   wordbound,    /* Succeeds if at a word boundary.  */
392   notwordbound  /* Succeeds if not at a word boundary.  */
393
394 #ifdef emacs
395   ,before_dot,  /* Succeeds if before point.  */
396   at_dot,       /* Succeeds if at point.  */
397   after_dot,    /* Succeeds if after point.  */
398
399         /* Matches any character whose syntax is specified.  Followed by
400            a byte which contains a syntax code, e.g., Sword.  */
401   syntaxspec,
402
403         /* Matches any character whose syntax is not that specified.  */
404   notsyntaxspec
405 #endif /* emacs */
406 } re_opcode_t;
407 \f
408 /* Common operations on the compiled pattern.  */
409
410 /* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
411
412 #define STORE_NUMBER(destination, number)                               \
413   do {                                                                  \
414     (destination)[0] = (number) & 0377;                                 \
415     (destination)[1] = (number) >> 8;                                   \
416   } while (0)
417
418 /* Same as STORE_NUMBER, except increment DESTINATION to
419    the byte after where the number is stored.  Therefore, DESTINATION
420    must be an lvalue.  */
421
422 #define STORE_NUMBER_AND_INCR(destination, number)                      \
423   do {                                                                  \
424     STORE_NUMBER (destination, number);                                 \
425     (destination) += 2;                                                 \
426   } while (0)
427
428 /* Put into DESTINATION a number stored in two contiguous bytes starting
429    at SOURCE.  */
430
431 #define EXTRACT_NUMBER(destination, source)                             \
432   do {                                                                  \
433     (destination) = *(source) & 0377;                                   \
434     (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8;           \
435   } while (0)
436
437 #ifdef DEBUG
438 static void
439 extract_number (dest, source)
440     int *dest;
441     unsigned char *source;
442 {
443   int temp = SIGN_EXTEND_CHAR (*(source + 1)); 
444   *dest = *source & 0377;
445   *dest += temp << 8;
446 }
447
448 #ifndef EXTRACT_MACROS /* To debug the macros.  */
449 #undef EXTRACT_NUMBER
450 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src)
451 #endif /* not EXTRACT_MACROS */
452
453 #endif /* DEBUG */
454
455 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
456    SOURCE must be an lvalue.  */
457
458 #define EXTRACT_NUMBER_AND_INCR(destination, source)                    \
459   do {                                                                  \
460     EXTRACT_NUMBER (destination, source);                               \
461     (source) += 2;                                                      \
462   } while (0)
463
464 #ifdef DEBUG
465 static void
466 extract_number_and_incr (destination, source)
467     int *destination;
468     unsigned char **source;
469
470   extract_number (destination, *source);
471   *source += 2;
472 }
473
474 #ifndef EXTRACT_MACROS
475 #undef EXTRACT_NUMBER_AND_INCR
476 #define EXTRACT_NUMBER_AND_INCR(dest, src) \
477   extract_number_and_incr (&dest, &src)
478 #endif /* not EXTRACT_MACROS */
479
480 #endif /* DEBUG */
481 \f
482 /* If DEBUG is defined, Regex prints many voluminous messages about what
483    it is doing (if the variable `debug' is nonzero).  If linked with the
484    main program in `iregex.c', you can enter patterns and strings
485    interactively.  And if linked with the main program in `main.c' and
486    the other test files, you can run the already-written tests.  */
487
488 #ifdef DEBUG
489
490 /* We use standard I/O for debugging.  */
491 #include <stdio.h>
492
493 /* It is useful to test things that ``must'' be true when debugging.  */
494 #include <assert.h>
495
496 static int debug = 0;
497
498 #define DEBUG_STATEMENT(e) e
499 #define DEBUG_PRINT1(x) if (debug) printf (x)
500 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
501 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
502 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
503 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)                           \
504   if (debug) print_partial_compiled_pattern (s, e)
505 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)                  \
506   if (debug) print_double_string (w, s1, sz1, s2, sz2)
507
508
509 extern void printchar ();
510
511 /* Print the fastmap in human-readable form.  */
512
513 void
514 print_fastmap (fastmap)
515     char *fastmap;
516 {
517   unsigned was_a_range = 0;
518   unsigned i = 0;  
519   
520   while (i < (1 << BYTEWIDTH))
521     {
522       if (fastmap[i++])
523         {
524           was_a_range = 0;
525           printchar (i - 1);
526           while (i < (1 << BYTEWIDTH)  &&  fastmap[i])
527             {
528               was_a_range = 1;
529               i++;
530             }
531           if (was_a_range)
532             {
533               printf ("-");
534               printchar (i - 1);
535             }
536         }
537     }
538   putchar ('\n'); 
539 }
540
541
542 /* Print a compiled pattern string in human-readable form, starting at
543    the START pointer into it and ending just before the pointer END.  */
544
545 void
546 print_partial_compiled_pattern (start, end)
547     unsigned char *start;
548     unsigned char *end;
549 {
550   int mcnt, mcnt2;
551   unsigned char *p = start;
552   unsigned char *pend = end;
553
554   if (start == NULL)
555     {
556       printf ("(null)\n");
557       return;
558     }
559     
560   /* Loop over pattern commands.  */
561   while (p < pend)
562     {
563       printf ("%d:\t", p - start);
564
565       switch ((re_opcode_t) *p++)
566         {
567         case no_op:
568           printf ("/no_op");
569           break;
570
571         case exactn:
572           mcnt = *p++;
573           printf ("/exactn/%d", mcnt);
574           do
575             {
576               putchar ('/');
577               printchar (*p++);
578             }
579           while (--mcnt);
580           break;
581
582         case start_memory:
583           mcnt = *p++;
584           printf ("/start_memory/%d/%d", mcnt, *p++);
585           break;
586
587         case stop_memory:
588           mcnt = *p++;
589           printf ("/stop_memory/%d/%d", mcnt, *p++);
590           break;
591
592         case duplicate:
593           printf ("/duplicate/%d", *p++);
594           break;
595
596         case anychar:
597           printf ("/anychar");
598           break;
599
600         case charset:
601         case charset_not:
602           {
603             register int c, last = -100;
604             register int in_range = 0;
605
606             printf ("/charset [%s",
607                     (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
608             
609             assert (p + *p < pend);
610
611             for (c = 0; c < 256; c++)
612               if (c / 8 < *p
613                   && (p[1 + (c/8)] & (1 << (c % 8))))
614                 {
615                   /* Are we starting a range?  */
616                   if (last + 1 == c && ! in_range)
617                     {
618                       putchar ('-');
619                       in_range = 1;
620                     }
621                   /* Have we broken a range?  */
622                   else if (last + 1 != c && in_range)
623               {
624                       printchar (last);
625                       in_range = 0;
626                     }
627                 
628                   if (! in_range)
629                     printchar (c);
630
631                   last = c;
632               }
633
634             if (in_range)
635               printchar (last);
636
637             putchar (']');
638
639             p += 1 + *p;
640           }
641           break;
642
643         case begline:
644           printf ("/begline");
645           break;
646
647         case endline:
648           printf ("/endline");
649           break;
650
651         case on_failure_jump:
652           extract_number_and_incr (&mcnt, &p);
653           printf ("/on_failure_jump to %d", p + mcnt - start);
654           break;
655
656         case on_failure_keep_string_jump:
657           extract_number_and_incr (&mcnt, &p);
658           printf ("/on_failure_keep_string_jump to %d", p + mcnt - start);
659           break;
660
661         case dummy_failure_jump:
662           extract_number_and_incr (&mcnt, &p);
663           printf ("/dummy_failure_jump to %d", p + mcnt - start);
664           break;
665
666         case push_dummy_failure:
667           printf ("/push_dummy_failure");
668           break;
669           
670         case maybe_pop_jump:
671           extract_number_and_incr (&mcnt, &p);
672           printf ("/maybe_pop_jump to %d", p + mcnt - start);
673           break;
674
675         case pop_failure_jump:
676           extract_number_and_incr (&mcnt, &p);
677           printf ("/pop_failure_jump to %d", p + mcnt - start);
678           break;          
679           
680         case jump_past_alt:
681           extract_number_and_incr (&mcnt, &p);
682           printf ("/jump_past_alt to %d", p + mcnt - start);
683           break;          
684           
685         case jump:
686           extract_number_and_incr (&mcnt, &p);
687           printf ("/jump to %d", p + mcnt - start);
688           break;
689
690         case succeed_n: 
691           extract_number_and_incr (&mcnt, &p);
692           extract_number_and_incr (&mcnt2, &p);
693           printf ("/succeed_n to %d, %d times", p + mcnt - start, mcnt2);
694           break;
695         
696         case jump_n: 
697           extract_number_and_incr (&mcnt, &p);
698           extract_number_and_incr (&mcnt2, &p);
699           printf ("/jump_n to %d, %d times", p + mcnt - start, mcnt2);
700           break;
701         
702         case set_number_at: 
703           extract_number_and_incr (&mcnt, &p);
704           extract_number_and_incr (&mcnt2, &p);
705           printf ("/set_number_at location %d to %d", p + mcnt - start, mcnt2);
706           break;
707         
708         case wordbound:
709           printf ("/wordbound");
710           break;
711
712         case notwordbound:
713           printf ("/notwordbound");
714           break;
715
716         case wordbeg:
717           printf ("/wordbeg");
718           break;
719           
720         case wordend:
721           printf ("/wordend");
722           
723 #ifdef emacs
724         case before_dot:
725           printf ("/before_dot");
726           break;
727
728         case at_dot:
729           printf ("/at_dot");
730           break;
731
732         case after_dot:
733           printf ("/after_dot");
734           break;
735
736         case syntaxspec:
737           printf ("/syntaxspec");
738           mcnt = *p++;
739           printf ("/%d", mcnt);
740           break;
741           
742         case notsyntaxspec:
743           printf ("/notsyntaxspec");
744           mcnt = *p++;
745           printf ("/%d", mcnt);
746           break;
747 #endif /* emacs */
748
749         case wordchar:
750           printf ("/wordchar");
751           break;
752           
753         case notwordchar:
754           printf ("/notwordchar");
755           break;
756
757         case begbuf:
758           printf ("/begbuf");
759           break;
760
761         case endbuf:
762           printf ("/endbuf");
763           break;
764
765         default:
766           printf ("?%d", *(p-1));
767         }
768
769       putchar ('\n');
770     }
771
772   printf ("%d:\tend of pattern.\n", p - start);
773 }
774
775
776 void
777 print_compiled_pattern (bufp)
778     struct re_pattern_buffer *bufp;
779 {
780   unsigned char *buffer = bufp->buffer;
781
782   print_partial_compiled_pattern (buffer, buffer + bufp->used);
783   printf ("%ld bytes used/%ld bytes allocated.\n", bufp->used, bufp->allocated);
784
785   if (bufp->fastmap_accurate && bufp->fastmap)
786     {
787       printf ("fastmap: ");
788       print_fastmap (bufp->fastmap);
789     }
790
791   printf ("re_nsub: %d\t", bufp->re_nsub);
792   printf ("regs_alloc: %d\t", bufp->regs_allocated);
793   printf ("can_be_null: %d\t", bufp->can_be_null);
794   printf ("newline_anchor: %d\n", bufp->newline_anchor);
795   printf ("no_sub: %d\t", bufp->no_sub);
796   printf ("not_bol: %d\t", bufp->not_bol);
797   printf ("not_eol: %d\t", bufp->not_eol);
798   printf ("syntax: %d\n", bufp->syntax);
799   /* Perhaps we should print the translate table?  */
800 }
801
802
803 void
804 print_double_string (where, string1, size1, string2, size2)
805     const char *where;
806     const char *string1;
807     const char *string2;
808     int size1;
809     int size2;
810 {
811   unsigned this_char;
812   
813   if (where == NULL)
814     printf ("(null)");
815   else
816     {
817       if (FIRST_STRING_P (where))
818         {
819           for (this_char = where - string1; this_char < size1; this_char++)
820             printchar (string1[this_char]);
821
822           where = string2;    
823         }
824
825       for (this_char = where - string2; this_char < size2; this_char++)
826         printchar (string2[this_char]);
827     }
828 }
829
830 #else /* not DEBUG */
831
832 #undef assert
833 #define assert(e)
834
835 #define DEBUG_STATEMENT(e)
836 #define DEBUG_PRINT1(x)
837 #define DEBUG_PRINT2(x1, x2)
838 #define DEBUG_PRINT3(x1, x2, x3)
839 #define DEBUG_PRINT4(x1, x2, x3, x4)
840 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
841 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
842
843 #endif /* not DEBUG */
844 \f
845 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
846    also be assigned to arbitrarily: each pattern buffer stores its own
847    syntax, so it can be changed between regex compilations.  */
848 reg_syntax_t re_syntax_options = RE_SYNTAX_EMACS;
849
850
851 /* Specify the precise syntax of regexps for compilation.  This provides
852    for compatibility for various utilities which historically have
853    different, incompatible syntaxes.
854
855    The argument SYNTAX is a bit mask comprised of the various bits
856    defined in regex.h.  We return the old syntax.  */
857
858 reg_syntax_t
859 re_set_syntax (syntax)
860     reg_syntax_t syntax;
861 {
862   reg_syntax_t ret = re_syntax_options;
863   
864   re_syntax_options = syntax;
865   return ret;
866 }
867 \f
868 /* This table gives an error message for each of the error codes listed
869    in regex.h.  Obviously the order here has to be same as there.  */
870
871 static const char *re_error_msg[] =
872   { NULL,                                       /* REG_NOERROR */
873     "No match",                                 /* REG_NOMATCH */
874     "Invalid regular expression",               /* REG_BADPAT */
875     "Invalid collation character",              /* REG_ECOLLATE */
876     "Invalid character class name",             /* REG_ECTYPE */
877     "Trailing backslash",                       /* REG_EESCAPE */
878     "Invalid back reference",                   /* REG_ESUBREG */
879     "Unmatched [ or [^",                        /* REG_EBRACK */
880     "Unmatched ( or \\(",                       /* REG_EPAREN */
881     "Unmatched \\{",                            /* REG_EBRACE */
882     "Invalid content of \\{\\}",                /* REG_BADBR */
883     "Invalid range end",                        /* REG_ERANGE */
884     "Memory exhausted",                         /* REG_ESPACE */
885     "Invalid preceding regular expression",     /* REG_BADRPT */
886     "Premature end of regular expression",      /* REG_EEND */
887     "Regular expression too big",               /* REG_ESIZE */
888     "Unmatched ) or \\)",                       /* REG_ERPAREN */
889   };
890 \f
891 /* Avoiding alloca during matching, to placate r_alloc.  */
892
893 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
894    searching and matching functions should not call alloca.  On some
895    systems, alloca is implemented in terms of malloc, and if we're
896    using the relocating allocator routines, then malloc could cause a
897    relocation, which might (if the strings being searched are in the
898    ralloc heap) shift the data out from underneath the regexp
899    routines.
900
901    Here's another reason to avoid allocation: Emacs insists on
902    processing input from X in a signal handler; processing X input may
903    call malloc; if input arrives while a matching routine is calling
904    malloc, then we're scrod.  But Emacs can't just block input while
905    calling matching routines; then we don't notice interrupts when
906    they come in.  So, Emacs blocks input around all regexp calls
907    except the matching calls, which it leaves unprotected, in the
908    faith that they will not malloc.  */
909
910 /* Normally, this is fine.  */
911 #define MATCH_MAY_ALLOCATE
912
913 /* But under some circumstances, it's not.  */
914 #if defined (emacs) || (defined (REL_ALLOC) && defined (C_ALLOCA))
915 #undef MATCH_MAY_ALLOCATE
916 #endif
917
918 \f
919 /* Failure stack declarations and macros; both re_compile_fastmap and
920    re_match_2 use a failure stack.  These have to be macros because of
921    REGEX_ALLOCATE.  */
922    
923
924 /* Number of failure points for which to initially allocate space
925    when matching.  If this number is exceeded, we allocate more
926    space, so it is not a hard limit.  */
927 #ifndef INIT_FAILURE_ALLOC
928 #define INIT_FAILURE_ALLOC 5
929 #endif
930
931 /* Roughly the maximum number of failure points on the stack.  Would be
932    exactly that if always used MAX_FAILURE_SPACE each time we failed.
933    This is a variable only so users of regex can assign to it; we never
934    change it ourselves.  */
935 int re_max_failures = 2000;
936
937 typedef unsigned char *fail_stack_elt_t;
938
939 typedef struct
940 {
941   fail_stack_elt_t *stack;
942   unsigned size;
943   unsigned avail;                       /* Offset of next open position.  */
944 } fail_stack_type;
945
946 #define FAIL_STACK_EMPTY()     (fail_stack.avail == 0)
947 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
948 #define FAIL_STACK_FULL()      (fail_stack.avail == fail_stack.size)
949 #define FAIL_STACK_TOP()       (fail_stack.stack[fail_stack.avail])
950
951
952 /* Initialize `fail_stack'.  Do `return -2' if the alloc fails.  */
953
954 #ifdef MATCH_MAY_ALLOCATE
955 #define INIT_FAIL_STACK()                                               \
956   do {                                                                  \
957     fail_stack.stack = (fail_stack_elt_t *)                             \
958       REGEX_ALLOCATE (INIT_FAILURE_ALLOC * sizeof (fail_stack_elt_t));  \
959                                                                         \
960     if (fail_stack.stack == NULL)                                       \
961       return -2;                                                        \
962                                                                         \
963     fail_stack.size = INIT_FAILURE_ALLOC;                               \
964     fail_stack.avail = 0;                                               \
965   } while (0)
966 #else
967 #define INIT_FAIL_STACK()                                               \
968   do {                                                                  \
969     fail_stack.avail = 0;                                               \
970   } while (0)
971 #endif
972
973
974 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
975
976    Return 1 if succeeds, and 0 if either ran out of memory
977    allocating space for it or it was already too large.  
978    
979    REGEX_REALLOCATE requires `destination' be declared.   */
980
981 #define DOUBLE_FAIL_STACK(fail_stack)                                   \
982   ((fail_stack).size > re_max_failures * MAX_FAILURE_ITEMS              \
983    ? 0                                                                  \
984    : ((fail_stack).stack = (fail_stack_elt_t *)                         \
985         REGEX_REALLOCATE ((fail_stack).stack,                           \
986           (fail_stack).size * sizeof (fail_stack_elt_t),                \
987           ((fail_stack).size << 1) * sizeof (fail_stack_elt_t)),        \
988                                                                         \
989       (fail_stack).stack == NULL                                        \
990       ? 0                                                               \
991       : ((fail_stack).size <<= 1,                                       \
992          1)))
993
994
995 /* Push PATTERN_OP on FAIL_STACK. 
996
997    Return 1 if was able to do so and 0 if ran out of memory allocating
998    space to do so.  */
999 #define PUSH_PATTERN_OP(pattern_op, fail_stack)                         \
1000   ((FAIL_STACK_FULL ()                                                  \
1001     && !DOUBLE_FAIL_STACK (fail_stack))                                 \
1002     ? 0                                                                 \
1003     : ((fail_stack).stack[(fail_stack).avail++] = pattern_op,           \
1004        1))
1005
1006 /* This pushes an item onto the failure stack.  sizeof(ITEM) must be no
1007    larger than sizeof (unsigned char *).  Assumes the variable `fail_stack'.
1008    Probably should only be called from within `PUSH_FAILURE_POINT'.  */
1009 #define PUSH_FAILURE_ITEM(item)                                         \
1010   do                                                                    \
1011     {                                                                   \
1012       fail_stack.stack[fail_stack.avail++] = (fail_stack_elt_t) item;   \
1013     }                                                                   \
1014   while (0)                                                             \
1015
1016 /* The complement operation.  Assumes `fail_stack' is nonempty.  */
1017 #define POP_FAILURE_ITEM() fail_stack.stack[--fail_stack.avail]
1018
1019 /* Used to omit pushing failure point id's when we're not debugging.  */
1020 #ifdef DEBUG
1021 #define DEBUG_PUSH PUSH_FAILURE_ITEM
1022 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_ITEM ()
1023 #else
1024 #define DEBUG_PUSH(item)
1025 #define DEBUG_POP(item_addr)
1026 #endif
1027
1028
1029 /* Push the information about the state we will need
1030    if we ever fail back to it.  
1031    
1032    Requires variables fail_stack, regstart, regend, reg_info, and
1033    num_regs be declared.  DOUBLE_FAIL_STACK requires `destination' be
1034    declared.
1035    
1036    Does `return FAILURE_CODE' if runs out of memory.  */
1037
1038 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code)   \
1039   do {                                                                  \
1040     char *destination;                                                  \
1041     /* Must be int, so when we don't save any registers, the arithmetic \
1042        of 0 + -1 isn't done as unsigned.  */                            \
1043     int this_reg;                                                       \
1044                                                                         \
1045     DEBUG_STATEMENT (failure_id++);                                     \
1046     DEBUG_STATEMENT (nfailure_points_pushed++);                         \
1047     DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id);           \
1048     DEBUG_PRINT2 ("  Before push, next avail: %d\n", (fail_stack).avail);\
1049     DEBUG_PRINT2 ("                     size: %d\n", (fail_stack).size);\
1050                                                                         \
1051     DEBUG_PRINT2 ("  slots needed: %d\n", NUM_FAILURE_ITEMS);           \
1052     DEBUG_PRINT2 ("     available: %d\n", REMAINING_AVAIL_SLOTS);       \
1053                                                                         \
1054     /* Ensure we have enough space allocated for what we will push.  */ \
1055     while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS)                   \
1056       {                                                                 \
1057         if (!DOUBLE_FAIL_STACK (fail_stack))                    \
1058           return failure_code;                                          \
1059                                                                         \
1060         DEBUG_PRINT2 ("\n  Doubled stack; size now: %d\n",              \
1061                        (fail_stack).size);                              \
1062         DEBUG_PRINT2 ("  slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1063       }                                                                 \
1064                                                                         \
1065     /* Push the info, starting with the registers.  */                  \
1066     DEBUG_PRINT1 ("\n");                                                \
1067                                                                         \
1068     for (this_reg = lowest_active_reg; this_reg <= highest_active_reg;  \
1069          this_reg++)                                                    \
1070       {                                                                 \
1071         DEBUG_PRINT2 ("  Pushing reg: %d\n", this_reg);                 \
1072         DEBUG_STATEMENT (num_regs_pushed++);                            \
1073                                                                         \
1074         DEBUG_PRINT2 ("    start: 0x%x\n", regstart[this_reg]);         \
1075         PUSH_FAILURE_ITEM (regstart[this_reg]);                         \
1076                                                                         \
1077         DEBUG_PRINT2 ("    end: 0x%x\n", regend[this_reg]);             \
1078         PUSH_FAILURE_ITEM (regend[this_reg]);                           \
1079                                                                         \
1080         DEBUG_PRINT2 ("    info: 0x%x\n      ", reg_info[this_reg]);    \
1081         DEBUG_PRINT2 (" match_null=%d",                                 \
1082                       REG_MATCH_NULL_STRING_P (reg_info[this_reg]));    \
1083         DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg]));    \
1084         DEBUG_PRINT2 (" matched_something=%d",                          \
1085                       MATCHED_SOMETHING (reg_info[this_reg]));          \
1086         DEBUG_PRINT2 (" ever_matched=%d",                               \
1087                       EVER_MATCHED_SOMETHING (reg_info[this_reg]));     \
1088         DEBUG_PRINT1 ("\n");                                            \
1089         PUSH_FAILURE_ITEM (reg_info[this_reg].word);                    \
1090       }                                                                 \
1091                                                                         \
1092     DEBUG_PRINT2 ("  Pushing  low active reg: %d\n", lowest_active_reg);\
1093     PUSH_FAILURE_ITEM (lowest_active_reg);                              \
1094                                                                         \
1095     DEBUG_PRINT2 ("  Pushing high active reg: %d\n", highest_active_reg);\
1096     PUSH_FAILURE_ITEM (highest_active_reg);                             \
1097                                                                         \
1098     DEBUG_PRINT2 ("  Pushing pattern 0x%x: ", pattern_place);           \
1099     DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend);           \
1100     PUSH_FAILURE_ITEM (pattern_place);                                  \
1101                                                                         \
1102     DEBUG_PRINT2 ("  Pushing string 0x%x: `", string_place);            \
1103     DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2,   \
1104                                  size2);                                \
1105     DEBUG_PRINT1 ("'\n");                                               \
1106     PUSH_FAILURE_ITEM (string_place);                                   \
1107                                                                         \
1108     DEBUG_PRINT2 ("  Pushing failure id: %u\n", failure_id);            \
1109     DEBUG_PUSH (failure_id);                                            \
1110   } while (0)
1111
1112 /* This is the number of items that are pushed and popped on the stack
1113    for each register.  */
1114 #define NUM_REG_ITEMS  3
1115
1116 /* Individual items aside from the registers.  */
1117 #ifdef DEBUG
1118 #define NUM_NONREG_ITEMS 5 /* Includes failure point id.  */
1119 #else
1120 #define NUM_NONREG_ITEMS 4
1121 #endif
1122
1123 /* We push at most this many items on the stack.  */
1124 #define MAX_FAILURE_ITEMS ((num_regs - 1) * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1125
1126 /* We actually push this many items.  */
1127 #define NUM_FAILURE_ITEMS                                               \
1128   ((highest_active_reg - lowest_active_reg + 1) * NUM_REG_ITEMS         \
1129     + NUM_NONREG_ITEMS)
1130
1131 /* How many items can still be added to the stack without overflowing it.  */
1132 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1133
1134
1135 /* Pops what PUSH_FAIL_STACK pushes.
1136
1137    We restore into the parameters, all of which should be lvalues:
1138      STR -- the saved data position.
1139      PAT -- the saved pattern position.
1140      LOW_REG, HIGH_REG -- the highest and lowest active registers.
1141      REGSTART, REGEND -- arrays of string positions.
1142      REG_INFO -- array of information about each subexpression.
1143    
1144    Also assumes the variables `fail_stack' and (if debugging), `bufp',
1145    `pend', `string1', `size1', `string2', and `size2'.  */
1146
1147 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1148 {                                                                       \
1149   DEBUG_STATEMENT (fail_stack_elt_t failure_id;)                        \
1150   int this_reg;                                                         \
1151   const unsigned char *string_temp;                                     \
1152                                                                         \
1153   assert (!FAIL_STACK_EMPTY ());                                        \
1154                                                                         \
1155   /* Remove failure points and point to how many regs pushed.  */       \
1156   DEBUG_PRINT1 ("POP_FAILURE_POINT:\n");                                \
1157   DEBUG_PRINT2 ("  Before pop, next avail: %d\n", fail_stack.avail);    \
1158   DEBUG_PRINT2 ("                    size: %d\n", fail_stack.size);     \
1159                                                                         \
1160   assert (fail_stack.avail >= NUM_NONREG_ITEMS);                        \
1161                                                                         \
1162   DEBUG_POP (&failure_id);                                              \
1163   DEBUG_PRINT2 ("  Popping failure id: %u\n", failure_id);              \
1164                                                                         \
1165   /* If the saved string location is NULL, it came from an              \
1166      on_failure_keep_string_jump opcode, and we want to throw away the  \
1167      saved NULL, thus retaining our current position in the string.  */ \
1168   string_temp = POP_FAILURE_ITEM ();                                    \
1169   if (string_temp != NULL)                                              \
1170     str = (const char *) string_temp;                                   \
1171                                                                         \
1172   DEBUG_PRINT2 ("  Popping string 0x%x: `", str);                       \
1173   DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2);      \
1174   DEBUG_PRINT1 ("'\n");                                                 \
1175                                                                         \
1176   pat = (unsigned char *) POP_FAILURE_ITEM ();                          \
1177   DEBUG_PRINT2 ("  Popping pattern 0x%x: ", pat);                       \
1178   DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend);                       \
1179                                                                         \
1180   /* Restore register info.  */                                         \
1181   high_reg = (unsigned long) POP_FAILURE_ITEM ();                       \
1182   DEBUG_PRINT2 ("  Popping high active reg: %d\n", high_reg);           \
1183                                                                         \
1184   low_reg = (unsigned long) POP_FAILURE_ITEM ();                        \
1185   DEBUG_PRINT2 ("  Popping  low active reg: %d\n", low_reg);            \
1186                                                                         \
1187   for (this_reg = high_reg; this_reg >= low_reg; this_reg--)            \
1188     {                                                                   \
1189       DEBUG_PRINT2 ("    Popping reg: %d\n", this_reg);                 \
1190                                                                         \
1191       reg_info[this_reg].word = POP_FAILURE_ITEM ();                    \
1192       DEBUG_PRINT2 ("      info: 0x%x\n", reg_info[this_reg]);          \
1193                                                                         \
1194       regend[this_reg] = (const char *) POP_FAILURE_ITEM ();            \
1195       DEBUG_PRINT2 ("      end: 0x%x\n", regend[this_reg]);             \
1196                                                                         \
1197       regstart[this_reg] = (const char *) POP_FAILURE_ITEM ();          \
1198       DEBUG_PRINT2 ("      start: 0x%x\n", regstart[this_reg]);         \
1199     }                                                                   \
1200                                                                         \
1201   DEBUG_STATEMENT (nfailure_points_popped++);                           \
1202 } /* POP_FAILURE_POINT */
1203
1204
1205 \f
1206 /* Structure for per-register (a.k.a. per-group) information.
1207    This must not be longer than one word, because we push this value
1208    onto the failure stack.  Other register information, such as the
1209    starting and ending positions (which are addresses), and the list of
1210    inner groups (which is a bits list) are maintained in separate
1211    variables.  
1212    
1213    We are making a (strictly speaking) nonportable assumption here: that
1214    the compiler will pack our bit fields into something that fits into
1215    the type of `word', i.e., is something that fits into one item on the
1216    failure stack.  */
1217 typedef union
1218 {
1219   fail_stack_elt_t word;
1220   struct
1221   {
1222       /* This field is one if this group can match the empty string,
1223          zero if not.  If not yet determined,  `MATCH_NULL_UNSET_VALUE'.  */
1224 #define MATCH_NULL_UNSET_VALUE 3
1225     unsigned match_null_string_p : 2;
1226     unsigned is_active : 1;
1227     unsigned matched_something : 1;
1228     unsigned ever_matched_something : 1;
1229   } bits;
1230 } register_info_type;
1231
1232 #define REG_MATCH_NULL_STRING_P(R)  ((R).bits.match_null_string_p)
1233 #define IS_ACTIVE(R)  ((R).bits.is_active)
1234 #define MATCHED_SOMETHING(R)  ((R).bits.matched_something)
1235 #define EVER_MATCHED_SOMETHING(R)  ((R).bits.ever_matched_something)
1236
1237
1238 /* Call this when have matched a real character; it sets `matched' flags
1239    for the subexpressions which we are currently inside.  Also records
1240    that those subexprs have matched.  */
1241 #define SET_REGS_MATCHED()                                              \
1242   do                                                                    \
1243     {                                                                   \
1244       unsigned r;                                                       \
1245       for (r = lowest_active_reg; r <= highest_active_reg; r++)         \
1246         {                                                               \
1247           MATCHED_SOMETHING (reg_info[r])                               \
1248             = EVER_MATCHED_SOMETHING (reg_info[r])                      \
1249             = 1;                                                        \
1250         }                                                               \
1251     }                                                                   \
1252   while (0)
1253
1254
1255 /* Registers are set to a sentinel when they haven't yet matched.  */
1256 #define REG_UNSET_VALUE ((char *) -1)
1257 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1258
1259
1260 \f
1261 /* How do we implement a missing MATCH_MAY_ALLOCATE?
1262    We make the fail stack a global thing, and then grow it to
1263    re_max_failures when we compile.  */
1264 #ifndef MATCH_MAY_ALLOCATE
1265 static fail_stack_type fail_stack;
1266
1267 static const char **     regstart, **     regend;
1268 static const char ** old_regstart, ** old_regend;
1269 static const char **best_regstart, **best_regend;
1270 static register_info_type *reg_info; 
1271 static const char **reg_dummy;
1272 static register_info_type *reg_info_dummy;
1273 #endif
1274
1275 \f
1276 /* Subroutine declarations and macros for regex_compile.  */
1277
1278 static void store_op1 (), store_op2 ();
1279 static void insert_op1 (), insert_op2 ();
1280 static boolean at_begline_loc_p (), at_endline_loc_p ();
1281 static boolean group_in_compile_stack ();
1282 static reg_errcode_t compile_range ();
1283
1284 /* Fetch the next character in the uncompiled pattern---translating it 
1285    if necessary.  Also cast from a signed character in the constant
1286    string passed to us by the user to an unsigned char that we can use
1287    as an array index (in, e.g., `translate').  */
1288 #define PATFETCH(c)                                                     \
1289   do {if (p == pend) return REG_EEND;                                   \
1290     c = (unsigned char) *p++;                                           \
1291     if (translate) c = translate[c];                                    \
1292   } while (0)
1293
1294 /* Fetch the next character in the uncompiled pattern, with no
1295    translation.  */
1296 #define PATFETCH_RAW(c)                                                 \
1297   do {if (p == pend) return REG_EEND;                                   \
1298     c = (unsigned char) *p++;                                           \
1299   } while (0)
1300
1301 /* Go backwards one character in the pattern.  */
1302 #define PATUNFETCH p--
1303
1304
1305 /* If `translate' is non-null, return translate[D], else just D.  We
1306    cast the subscript to translate because some data is declared as
1307    `char *', to avoid warnings when a string constant is passed.  But
1308    when we use a character as a subscript we must make it unsigned.  */
1309 #define TRANSLATE(d) (translate ? translate[(unsigned char) (d)] : (d))
1310
1311
1312 /* Macros for outputting the compiled pattern into `buffer'.  */
1313
1314 /* If the buffer isn't allocated when it comes in, use this.  */
1315 #define INIT_BUF_SIZE  32
1316
1317 /* Make sure we have at least N more bytes of space in buffer.  */
1318 #define GET_BUFFER_SPACE(n)                                             \
1319     while (b - bufp->buffer + (n) > bufp->allocated)                    \
1320       EXTEND_BUFFER ()
1321
1322 /* Make sure we have one more byte of buffer space and then add C to it.  */
1323 #define BUF_PUSH(c)                                                     \
1324   do {                                                                  \
1325     GET_BUFFER_SPACE (1);                                               \
1326     *b++ = (unsigned char) (c);                                         \
1327   } while (0)
1328
1329
1330 /* Ensure we have two more bytes of buffer space and then append C1 and C2.  */
1331 #define BUF_PUSH_2(c1, c2)                                              \
1332   do {                                                                  \
1333     GET_BUFFER_SPACE (2);                                               \
1334     *b++ = (unsigned char) (c1);                                        \
1335     *b++ = (unsigned char) (c2);                                        \
1336   } while (0)
1337
1338
1339 /* As with BUF_PUSH_2, except for three bytes.  */
1340 #define BUF_PUSH_3(c1, c2, c3)                                          \
1341   do {                                                                  \
1342     GET_BUFFER_SPACE (3);                                               \
1343     *b++ = (unsigned char) (c1);                                        \
1344     *b++ = (unsigned char) (c2);                                        \
1345     *b++ = (unsigned char) (c3);                                        \
1346   } while (0)
1347
1348
1349 /* Store a jump with opcode OP at LOC to location TO.  We store a
1350    relative address offset by the three bytes the jump itself occupies.  */
1351 #define STORE_JUMP(op, loc, to) \
1352   store_op1 (op, loc, (to) - (loc) - 3)
1353
1354 /* Likewise, for a two-argument jump.  */
1355 #define STORE_JUMP2(op, loc, to, arg) \
1356   store_op2 (op, loc, (to) - (loc) - 3, arg)
1357
1358 /* Like `STORE_JUMP', but for inserting.  Assume `b' is the buffer end.  */
1359 #define INSERT_JUMP(op, loc, to) \
1360   insert_op1 (op, loc, (to) - (loc) - 3, b)
1361
1362 /* Like `STORE_JUMP2', but for inserting.  Assume `b' is the buffer end.  */
1363 #define INSERT_JUMP2(op, loc, to, arg) \
1364   insert_op2 (op, loc, (to) - (loc) - 3, arg, b)
1365
1366
1367 /* This is not an arbitrary limit: the arguments which represent offsets
1368    into the pattern are two bytes long.  So if 2^16 bytes turns out to
1369    be too small, many things would have to change.  */
1370 #define MAX_BUF_SIZE (1L << 16)
1371
1372
1373 /* Extend the buffer by twice its current size via realloc and
1374    reset the pointers that pointed into the old block to point to the
1375    correct places in the new one.  If extending the buffer results in it
1376    being larger than MAX_BUF_SIZE, then flag memory exhausted.  */
1377 #define EXTEND_BUFFER()                                                 \
1378   do {                                                                  \
1379     unsigned char *old_buffer = bufp->buffer;                           \
1380     if (bufp->allocated == MAX_BUF_SIZE)                                \
1381       return REG_ESIZE;                                                 \
1382     bufp->allocated <<= 1;                                              \
1383     if (bufp->allocated > MAX_BUF_SIZE)                                 \
1384       bufp->allocated = MAX_BUF_SIZE;                                   \
1385     bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\
1386     if (bufp->buffer == NULL)                                           \
1387       return REG_ESPACE;                                                \
1388     /* If the buffer moved, move all the pointers into it.  */          \
1389     if (old_buffer != bufp->buffer)                                     \
1390       {                                                                 \
1391         b = (b - old_buffer) + bufp->buffer;                            \
1392         begalt = (begalt - old_buffer) + bufp->buffer;                  \
1393         if (fixup_alt_jump)                                             \
1394           fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\
1395         if (laststart)                                                  \
1396           laststart = (laststart - old_buffer) + bufp->buffer;          \
1397         if (pending_exact)                                              \
1398           pending_exact = (pending_exact - old_buffer) + bufp->buffer;  \
1399       }                                                                 \
1400   } while (0)
1401
1402
1403 /* Since we have one byte reserved for the register number argument to
1404    {start,stop}_memory, the maximum number of groups we can report
1405    things about is what fits in that byte.  */
1406 #define MAX_REGNUM 255
1407
1408 /* But patterns can have more than `MAX_REGNUM' registers.  We just
1409    ignore the excess.  */
1410 typedef unsigned regnum_t;
1411
1412
1413 /* Macros for the compile stack.  */
1414
1415 /* Since offsets can go either forwards or backwards, this type needs to
1416    be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.  */
1417 typedef int pattern_offset_t;
1418
1419 typedef struct
1420 {
1421   pattern_offset_t begalt_offset;
1422   pattern_offset_t fixup_alt_jump;
1423   pattern_offset_t inner_group_offset;
1424   pattern_offset_t laststart_offset;  
1425   regnum_t regnum;
1426 } compile_stack_elt_t;
1427
1428
1429 typedef struct
1430 {
1431   compile_stack_elt_t *stack;
1432   unsigned size;
1433   unsigned avail;                       /* Offset of next open position.  */
1434 } compile_stack_type;
1435
1436
1437 #define INIT_COMPILE_STACK_SIZE 32
1438
1439 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
1440 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
1441
1442 /* The next available element.  */
1443 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
1444
1445
1446 /* Set the bit for character C in a list.  */
1447 #define SET_LIST_BIT(c)                               \
1448   (b[((unsigned char) (c)) / BYTEWIDTH]               \
1449    |= 1 << (((unsigned char) c) % BYTEWIDTH))
1450
1451
1452 /* Get the next unsigned number in the uncompiled pattern.  */
1453 #define GET_UNSIGNED_NUMBER(num)                                        \
1454   { if (p != pend)                                                      \
1455      {                                                                  \
1456        PATFETCH (c);                                                    \
1457        while (ISDIGIT (c))                                              \
1458          {                                                              \
1459            if (num < 0)                                                 \
1460               num = 0;                                                  \
1461            num = num * 10 + c - '0';                                    \
1462            if (p == pend)                                               \
1463               break;                                                    \
1464            PATFETCH (c);                                                \
1465          }                                                              \
1466        }                                                                \
1467     }           
1468
1469 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
1470
1471 #define IS_CHAR_CLASS(string)                                           \
1472    (STREQ (string, "alpha") || STREQ (string, "upper")                  \
1473     || STREQ (string, "lower") || STREQ (string, "digit")               \
1474     || STREQ (string, "alnum") || STREQ (string, "xdigit")              \
1475     || STREQ (string, "space") || STREQ (string, "print")               \
1476     || STREQ (string, "punct") || STREQ (string, "graph")               \
1477     || STREQ (string, "cntrl") || STREQ (string, "blank"))
1478 \f
1479 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
1480    Returns one of error codes defined in `regex.h', or zero for success.
1481
1482    Assumes the `allocated' (and perhaps `buffer') and `translate'
1483    fields are set in BUFP on entry.
1484
1485    If it succeeds, results are put in BUFP (if it returns an error, the
1486    contents of BUFP are undefined):
1487      `buffer' is the compiled pattern;
1488      `syntax' is set to SYNTAX;
1489      `used' is set to the length of the compiled pattern;
1490      `fastmap_accurate' is zero;
1491      `re_nsub' is the number of subexpressions in PATTERN;
1492      `not_bol' and `not_eol' are zero;
1493    
1494    The `fastmap' and `newline_anchor' fields are neither
1495    examined nor set.  */
1496
1497 static reg_errcode_t
1498 regex_compile (pattern, size, syntax, bufp)
1499      const char *pattern;
1500      int size;
1501      reg_syntax_t syntax;
1502      struct re_pattern_buffer *bufp;
1503 {
1504   /* We fetch characters from PATTERN here.  Even though PATTERN is
1505      `char *' (i.e., signed), we declare these variables as unsigned, so
1506      they can be reliably used as array indices.  */
1507   register unsigned char c, c1;
1508   
1509   /* A random temporary spot in PATTERN.  */
1510   const char *p1;
1511
1512   /* Points to the end of the buffer, where we should append.  */
1513   register unsigned char *b;
1514   
1515   /* Keeps track of unclosed groups.  */
1516   compile_stack_type compile_stack;
1517
1518   /* Points to the current (ending) position in the pattern.  */
1519   const char *p = pattern;
1520   const char *pend = pattern + size;
1521   
1522   /* How to translate the characters in the pattern.  */
1523   char *translate = bufp->translate;
1524
1525   /* Address of the count-byte of the most recently inserted `exactn'
1526      command.  This makes it possible to tell if a new exact-match
1527      character can be added to that command or if the character requires
1528      a new `exactn' command.  */
1529   unsigned char *pending_exact = 0;
1530
1531   /* Address of start of the most recently finished expression.
1532      This tells, e.g., postfix * where to find the start of its
1533      operand.  Reset at the beginning of groups and alternatives.  */
1534   unsigned char *laststart = 0;
1535
1536   /* Address of beginning of regexp, or inside of last group.  */
1537   unsigned char *begalt;
1538
1539   /* Place in the uncompiled pattern (i.e., the {) to
1540      which to go back if the interval is invalid.  */
1541   const char *beg_interval;
1542                 
1543   /* Address of the place where a forward jump should go to the end of
1544      the containing expression.  Each alternative of an `or' -- except the
1545      last -- ends with a forward jump of this sort.  */
1546   unsigned char *fixup_alt_jump = 0;
1547
1548   /* Counts open-groups as they are encountered.  Remembered for the
1549      matching close-group on the compile stack, so the same register
1550      number is put in the stop_memory as the start_memory.  */
1551   regnum_t regnum = 0;
1552
1553 #ifdef DEBUG
1554   DEBUG_PRINT1 ("\nCompiling pattern: ");
1555   if (debug)
1556     {
1557       unsigned debug_count;
1558       
1559       for (debug_count = 0; debug_count < size; debug_count++)
1560         printchar (pattern[debug_count]);
1561       putchar ('\n');
1562     }
1563 #endif /* DEBUG */
1564
1565   /* Initialize the compile stack.  */
1566   compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
1567   if (compile_stack.stack == NULL)
1568     return REG_ESPACE;
1569
1570   compile_stack.size = INIT_COMPILE_STACK_SIZE;
1571   compile_stack.avail = 0;
1572
1573   /* Initialize the pattern buffer.  */
1574   bufp->syntax = syntax;
1575   bufp->fastmap_accurate = 0;
1576   bufp->not_bol = bufp->not_eol = 0;
1577
1578   /* Set `used' to zero, so that if we return an error, the pattern
1579      printer (for debugging) will think there's no pattern.  We reset it
1580      at the end.  */
1581   bufp->used = 0;
1582   
1583   /* Always count groups, whether or not bufp->no_sub is set.  */
1584   bufp->re_nsub = 0;                            
1585
1586 #if !defined (emacs) && !defined (SYNTAX_TABLE)
1587   /* Initialize the syntax table.  */
1588    init_syntax_once ();
1589 #endif
1590
1591   if (bufp->allocated == 0)
1592     {
1593       if (bufp->buffer)
1594         { /* If zero allocated, but buffer is non-null, try to realloc
1595              enough space.  This loses if buffer's address is bogus, but
1596              that is the user's responsibility.  */
1597           RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char);
1598         }
1599       else
1600         { /* Caller did not allocate a buffer.  Do it for them.  */
1601           bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char);
1602         }
1603       if (!bufp->buffer) return REG_ESPACE;
1604
1605       bufp->allocated = INIT_BUF_SIZE;
1606     }
1607
1608   begalt = b = bufp->buffer;
1609
1610   /* Loop through the uncompiled pattern until we're at the end.  */
1611   while (p != pend)
1612     {
1613       PATFETCH (c);
1614
1615       switch (c)
1616         {
1617         case '^':
1618           {
1619             if (   /* If at start of pattern, it's an operator.  */
1620                    p == pattern + 1
1621                    /* If context independent, it's an operator.  */
1622                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1623                    /* Otherwise, depends on what's come before.  */
1624                 || at_begline_loc_p (pattern, p, syntax))
1625               BUF_PUSH (begline);
1626             else
1627               goto normal_char;
1628           }
1629           break;
1630
1631
1632         case '$':
1633           {
1634             if (   /* If at end of pattern, it's an operator.  */
1635                    p == pend 
1636                    /* If context independent, it's an operator.  */
1637                 || syntax & RE_CONTEXT_INDEP_ANCHORS
1638                    /* Otherwise, depends on what's next.  */
1639                 || at_endline_loc_p (p, pend, syntax))
1640                BUF_PUSH (endline);
1641              else
1642                goto normal_char;
1643            }
1644            break;
1645
1646
1647         case '+':
1648         case '?':
1649           if ((syntax & RE_BK_PLUS_QM)
1650               || (syntax & RE_LIMITED_OPS))
1651             goto normal_char;
1652         handle_plus:
1653         case '*':
1654           /* If there is no previous pattern... */
1655           if (!laststart)
1656             {
1657               if (syntax & RE_CONTEXT_INVALID_OPS)
1658                 return REG_BADRPT;
1659               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
1660                 goto normal_char;
1661             }
1662
1663           {
1664             /* Are we optimizing this jump?  */
1665             boolean keep_string_p = false;
1666             
1667             /* 1 means zero (many) matches is allowed.  */
1668             char zero_times_ok = 0, many_times_ok = 0;
1669
1670             /* If there is a sequence of repetition chars, collapse it
1671                down to just one (the right one).  We can't combine
1672                interval operators with these because of, e.g., `a{2}*',
1673                which should only match an even number of `a's.  */
1674
1675             for (;;)
1676               {
1677                 zero_times_ok |= c != '+';
1678                 many_times_ok |= c != '?';
1679
1680                 if (p == pend)
1681                   break;
1682
1683                 PATFETCH (c);
1684
1685                 if (c == '*'
1686                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
1687                   ;
1688
1689                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
1690                   {
1691                     if (p == pend) return REG_EESCAPE;
1692
1693                     PATFETCH (c1);
1694                     if (!(c1 == '+' || c1 == '?'))
1695                       {
1696                         PATUNFETCH;
1697                         PATUNFETCH;
1698                         break;
1699                       }
1700
1701                     c = c1;
1702                   }
1703                 else
1704                   {
1705                     PATUNFETCH;
1706                     break;
1707                   }
1708
1709                 /* If we get here, we found another repeat character.  */
1710                }
1711
1712             /* Star, etc. applied to an empty pattern is equivalent
1713                to an empty pattern.  */
1714             if (!laststart)  
1715               break;
1716
1717             /* Now we know whether or not zero matches is allowed
1718                and also whether or not two or more matches is allowed.  */
1719             if (many_times_ok)
1720               { /* More than one repetition is allowed, so put in at the
1721                    end a backward relative jump from `b' to before the next
1722                    jump we're going to put in below (which jumps from
1723                    laststart to after this jump).  
1724
1725                    But if we are at the `*' in the exact sequence `.*\n',
1726                    insert an unconditional jump backwards to the .,
1727                    instead of the beginning of the loop.  This way we only
1728                    push a failure point once, instead of every time
1729                    through the loop.  */
1730                 assert (p - 1 > pattern);
1731
1732                 /* Allocate the space for the jump.  */
1733                 GET_BUFFER_SPACE (3);
1734
1735                 /* We know we are not at the first character of the pattern,
1736                    because laststart was nonzero.  And we've already
1737                    incremented `p', by the way, to be the character after
1738                    the `*'.  Do we have to do something analogous here
1739                    for null bytes, because of RE_DOT_NOT_NULL?  */
1740                 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
1741                     && zero_times_ok
1742                     && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
1743                     && !(syntax & RE_DOT_NEWLINE))
1744                   { /* We have .*\n.  */
1745                     STORE_JUMP (jump, b, laststart);
1746                     keep_string_p = true;
1747                   }
1748                 else
1749                   /* Anything else.  */
1750                   STORE_JUMP (maybe_pop_jump, b, laststart - 3);
1751
1752                 /* We've added more stuff to the buffer.  */
1753                 b += 3;
1754               }
1755
1756             /* On failure, jump from laststart to b + 3, which will be the
1757                end of the buffer after this jump is inserted.  */
1758             GET_BUFFER_SPACE (3);
1759             INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
1760                                        : on_failure_jump,
1761                          laststart, b + 3);
1762             pending_exact = 0;
1763             b += 3;
1764
1765             if (!zero_times_ok)
1766               {
1767                 /* At least one repetition is required, so insert a
1768                    `dummy_failure_jump' before the initial
1769                    `on_failure_jump' instruction of the loop. This
1770                    effects a skip over that instruction the first time
1771                    we hit that loop.  */
1772                 GET_BUFFER_SPACE (3);
1773                 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6);
1774                 b += 3;
1775               }
1776             }
1777           break;
1778
1779
1780         case '.':
1781           laststart = b;
1782           BUF_PUSH (anychar);
1783           break;
1784
1785
1786         case '[':
1787           {
1788             boolean had_char_class = false;
1789
1790             if (p == pend) return REG_EBRACK;
1791
1792             /* Ensure that we have enough space to push a charset: the
1793                opcode, the length count, and the bitset; 34 bytes in all.  */
1794             GET_BUFFER_SPACE (34);
1795
1796             laststart = b;
1797
1798             /* We test `*p == '^' twice, instead of using an if
1799                statement, so we only need one BUF_PUSH.  */
1800             BUF_PUSH (*p == '^' ? charset_not : charset); 
1801             if (*p == '^')
1802               p++;
1803
1804             /* Remember the first position in the bracket expression.  */
1805             p1 = p;
1806
1807             /* Push the number of bytes in the bitmap.  */
1808             BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
1809
1810             /* Clear the whole map.  */
1811             bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
1812
1813             /* charset_not matches newline according to a syntax bit.  */
1814             if ((re_opcode_t) b[-2] == charset_not
1815                 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
1816               SET_LIST_BIT ('\n');
1817
1818             /* Read in characters and ranges, setting map bits.  */
1819             for (;;)
1820               {
1821                 if (p == pend) return REG_EBRACK;
1822
1823                 PATFETCH (c);
1824
1825                 /* \ might escape characters inside [...] and [^...].  */
1826                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
1827                   {
1828                     if (p == pend) return REG_EESCAPE;
1829
1830                     PATFETCH (c1);
1831                     SET_LIST_BIT (c1);
1832                     continue;
1833                   }
1834
1835                 /* Could be the end of the bracket expression.  If it's
1836                    not (i.e., when the bracket expression is `[]' so
1837                    far), the ']' character bit gets set way below.  */
1838                 if (c == ']' && p != p1 + 1)
1839                   break;
1840
1841                 /* Look ahead to see if it's a range when the last thing
1842                    was a character class.  */
1843                 if (had_char_class && c == '-' && *p != ']')
1844                   return REG_ERANGE;
1845
1846                 /* Look ahead to see if it's a range when the last thing
1847                    was a character: if this is a hyphen not at the
1848                    beginning or the end of a list, then it's the range
1849                    operator.  */
1850                 if (c == '-' 
1851                     && !(p - 2 >= pattern && p[-2] == '[') 
1852                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
1853                     && *p != ']')
1854                   {
1855                     reg_errcode_t ret
1856                       = compile_range (&p, pend, translate, syntax, b);
1857                     if (ret != REG_NOERROR) return ret;
1858                   }
1859
1860                 else if (p[0] == '-' && p[1] != ']')
1861                   { /* This handles ranges made up of characters only.  */
1862                     reg_errcode_t ret;
1863
1864                     /* Move past the `-'.  */
1865                     PATFETCH (c1);
1866                     
1867                     ret = compile_range (&p, pend, translate, syntax, b);
1868                     if (ret != REG_NOERROR) return ret;
1869                   }
1870
1871                 /* See if we're at the beginning of a possible character
1872                    class.  */
1873
1874                 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
1875                   { /* Leave room for the null.  */
1876                     char str[CHAR_CLASS_MAX_LENGTH + 1];
1877
1878                     PATFETCH (c);
1879                     c1 = 0;
1880
1881                     /* If pattern is `[[:'.  */
1882                     if (p == pend) return REG_EBRACK;
1883
1884                     for (;;)
1885                       {
1886                         PATFETCH (c);
1887                         if (c == ':' || c == ']' || p == pend
1888                             || c1 == CHAR_CLASS_MAX_LENGTH)
1889                           break;
1890                         str[c1++] = c;
1891                       }
1892                     str[c1] = '\0';
1893
1894                     /* If isn't a word bracketed by `[:' and:`]':
1895                        undo the ending character, the letters, and leave 
1896                        the leading `:' and `[' (but set bits for them).  */
1897                     if (c == ':' && *p == ']')
1898                       {
1899                         int ch;
1900                         boolean is_alnum = STREQ (str, "alnum");
1901                         boolean is_alpha = STREQ (str, "alpha");
1902                         boolean is_blank = STREQ (str, "blank");
1903                         boolean is_cntrl = STREQ (str, "cntrl");
1904                         boolean is_digit = STREQ (str, "digit");
1905                         boolean is_graph = STREQ (str, "graph");
1906                         boolean is_lower = STREQ (str, "lower");
1907                         boolean is_print = STREQ (str, "print");
1908                         boolean is_punct = STREQ (str, "punct");
1909                         boolean is_space = STREQ (str, "space");
1910                         boolean is_upper = STREQ (str, "upper");
1911                         boolean is_xdigit = STREQ (str, "xdigit");
1912                         
1913                         if (!IS_CHAR_CLASS (str)) return REG_ECTYPE;
1914
1915                         /* Throw away the ] at the end of the character
1916                            class.  */
1917                         PATFETCH (c);                                   
1918
1919                         if (p == pend) return REG_EBRACK;
1920
1921                         for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
1922                           {
1923                             if (   (is_alnum  && ISALNUM (ch))
1924                                 || (is_alpha  && ISALPHA (ch))
1925                                 || (is_blank  && ISBLANK (ch))
1926                                 || (is_cntrl  && ISCNTRL (ch))
1927                                 || (is_digit  && ISDIGIT (ch))
1928                                 || (is_graph  && ISGRAPH (ch))
1929                                 || (is_lower  && ISLOWER (ch))
1930                                 || (is_print  && ISPRINT (ch))
1931                                 || (is_punct  && ISPUNCT (ch))
1932                                 || (is_space  && ISSPACE (ch))
1933                                 || (is_upper  && ISUPPER (ch))
1934                                 || (is_xdigit && ISXDIGIT (ch)))
1935                             SET_LIST_BIT (ch);
1936                           }
1937                         had_char_class = true;
1938                       }
1939                     else
1940                       {
1941                         c1++;
1942                         while (c1--)    
1943                           PATUNFETCH;
1944                         SET_LIST_BIT ('[');
1945                         SET_LIST_BIT (':');
1946                         had_char_class = false;
1947                       }
1948                   }
1949                 else
1950                   {
1951                     had_char_class = false;
1952                     SET_LIST_BIT (c);
1953                   }
1954               }
1955
1956             /* Discard any (non)matching list bytes that are all 0 at the
1957                end of the map.  Decrease the map-length byte too.  */
1958             while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) 
1959               b[-1]--; 
1960             b += b[-1];
1961           }
1962           break;
1963
1964
1965         case '(':
1966           if (syntax & RE_NO_BK_PARENS)
1967             goto handle_open;
1968           else
1969             goto normal_char;
1970
1971
1972         case ')':
1973           if (syntax & RE_NO_BK_PARENS)
1974             goto handle_close;
1975           else
1976             goto normal_char;
1977
1978
1979         case '\n':
1980           if (syntax & RE_NEWLINE_ALT)
1981             goto handle_alt;
1982           else
1983             goto normal_char;
1984
1985
1986         case '|':
1987           if (syntax & RE_NO_BK_VBAR)
1988             goto handle_alt;
1989           else
1990             goto normal_char;
1991
1992
1993         case '{':
1994            if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
1995              goto handle_interval;
1996            else
1997              goto normal_char;
1998
1999
2000         case '\\':
2001           if (p == pend) return REG_EESCAPE;
2002
2003           /* Do not translate the character after the \, so that we can
2004              distinguish, e.g., \B from \b, even if we normally would
2005              translate, e.g., B to b.  */
2006           PATFETCH_RAW (c);
2007
2008           switch (c)
2009             {
2010             case '(':
2011               if (syntax & RE_NO_BK_PARENS)
2012                 goto normal_backslash;
2013
2014             handle_open:
2015               bufp->re_nsub++;
2016               regnum++;
2017
2018               if (COMPILE_STACK_FULL)
2019                 { 
2020                   RETALLOC (compile_stack.stack, compile_stack.size << 1,
2021                             compile_stack_elt_t);
2022                   if (compile_stack.stack == NULL) return REG_ESPACE;
2023
2024                   compile_stack.size <<= 1;
2025                 }
2026
2027               /* These are the values to restore when we hit end of this
2028                  group.  They are all relative offsets, so that if the
2029                  whole pattern moves because of realloc, they will still
2030                  be valid.  */
2031               COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer;
2032               COMPILE_STACK_TOP.fixup_alt_jump 
2033                 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0;
2034               COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer;
2035               COMPILE_STACK_TOP.regnum = regnum;
2036
2037               /* We will eventually replace the 0 with the number of
2038                  groups inner to this one.  But do not push a
2039                  start_memory for groups beyond the last one we can
2040                  represent in the compiled pattern.  */
2041               if (regnum <= MAX_REGNUM)
2042                 {
2043                   COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2;
2044                   BUF_PUSH_3 (start_memory, regnum, 0);
2045                 }
2046                 
2047               compile_stack.avail++;
2048
2049               fixup_alt_jump = 0;
2050               laststart = 0;
2051               begalt = b;
2052               /* If we've reached MAX_REGNUM groups, then this open
2053                  won't actually generate any code, so we'll have to
2054                  clear pending_exact explicitly.  */
2055               pending_exact = 0;
2056               break;
2057
2058
2059             case ')':
2060               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
2061
2062               if (COMPILE_STACK_EMPTY)
2063                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2064                   goto normal_backslash;
2065                 else
2066                   return REG_ERPAREN;
2067
2068             handle_close:
2069               if (fixup_alt_jump)
2070                 { /* Push a dummy failure point at the end of the
2071                      alternative for a possible future
2072                      `pop_failure_jump' to pop.  See comments at
2073                      `push_dummy_failure' in `re_match_2'.  */
2074                   BUF_PUSH (push_dummy_failure);
2075                   
2076                   /* We allocated space for this jump when we assigned
2077                      to `fixup_alt_jump', in the `handle_alt' case below.  */
2078                   STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
2079                 }
2080
2081               /* See similar code for backslashed left paren above.  */
2082               if (COMPILE_STACK_EMPTY)
2083                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
2084                   goto normal_char;
2085                 else
2086                   return REG_ERPAREN;
2087
2088               /* Since we just checked for an empty stack above, this
2089                  ``can't happen''.  */
2090               assert (compile_stack.avail != 0);
2091               {
2092                 /* We don't just want to restore into `regnum', because
2093                    later groups should continue to be numbered higher,
2094                    as in `(ab)c(de)' -- the second group is #2.  */
2095                 regnum_t this_group_regnum;
2096
2097                 compile_stack.avail--;          
2098                 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset;
2099                 fixup_alt_jump
2100                   = COMPILE_STACK_TOP.fixup_alt_jump
2101                     ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1 
2102                     : 0;
2103                 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset;
2104                 this_group_regnum = COMPILE_STACK_TOP.regnum;
2105                 /* If we've reached MAX_REGNUM groups, then this open
2106                    won't actually generate any code, so we'll have to
2107                    clear pending_exact explicitly.  */
2108                 pending_exact = 0;
2109
2110                 /* We're at the end of the group, so now we know how many
2111                    groups were inside this one.  */
2112                 if (this_group_regnum <= MAX_REGNUM)
2113                   {
2114                     unsigned char *inner_group_loc
2115                       = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset;
2116                     
2117                     *inner_group_loc = regnum - this_group_regnum;
2118                     BUF_PUSH_3 (stop_memory, this_group_regnum,
2119                                 regnum - this_group_regnum);
2120                   }
2121               }
2122               break;
2123
2124
2125             case '|':                                   /* `\|'.  */
2126               if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
2127                 goto normal_backslash;
2128             handle_alt:
2129               if (syntax & RE_LIMITED_OPS)
2130                 goto normal_char;
2131
2132               /* Insert before the previous alternative a jump which
2133                  jumps to this alternative if the former fails.  */
2134               GET_BUFFER_SPACE (3);
2135               INSERT_JUMP (on_failure_jump, begalt, b + 6);
2136               pending_exact = 0;
2137               b += 3;
2138
2139               /* The alternative before this one has a jump after it
2140                  which gets executed if it gets matched.  Adjust that
2141                  jump so it will jump to this alternative's analogous
2142                  jump (put in below, which in turn will jump to the next
2143                  (if any) alternative's such jump, etc.).  The last such
2144                  jump jumps to the correct final destination.  A picture:
2145                           _____ _____ 
2146                           |   | |   |   
2147                           |   v |   v 
2148                          a | b   | c   
2149
2150                  If we are at `b', then fixup_alt_jump right now points to a
2151                  three-byte space after `a'.  We'll put in the jump, set
2152                  fixup_alt_jump to right after `b', and leave behind three
2153                  bytes which we'll fill in when we get to after `c'.  */
2154
2155               if (fixup_alt_jump)
2156                 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2157
2158               /* Mark and leave space for a jump after this alternative,
2159                  to be filled in later either by next alternative or
2160                  when know we're at the end of a series of alternatives.  */
2161               fixup_alt_jump = b;
2162               GET_BUFFER_SPACE (3);
2163               b += 3;
2164
2165               laststart = 0;
2166               begalt = b;
2167               break;
2168
2169
2170             case '{': 
2171               /* If \{ is a literal.  */
2172               if (!(syntax & RE_INTERVALS)
2173                      /* If we're at `\{' and it's not the open-interval 
2174                         operator.  */
2175                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
2176                   || (p - 2 == pattern  &&  p == pend))
2177                 goto normal_backslash;
2178
2179             handle_interval:
2180               {
2181                 /* If got here, then the syntax allows intervals.  */
2182
2183                 /* At least (most) this many matches must be made.  */
2184                 int lower_bound = -1, upper_bound = -1;
2185
2186                 beg_interval = p - 1;
2187
2188                 if (p == pend)
2189                   {
2190                     if (syntax & RE_NO_BK_BRACES)
2191                       goto unfetch_interval;
2192                     else
2193                       return REG_EBRACE;
2194                   }
2195
2196                 GET_UNSIGNED_NUMBER (lower_bound);
2197
2198                 if (c == ',')
2199                   {
2200                     GET_UNSIGNED_NUMBER (upper_bound);
2201                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
2202                   }
2203                 else
2204                   /* Interval such as `{1}' => match exactly once. */
2205                   upper_bound = lower_bound;
2206
2207                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
2208                     || lower_bound > upper_bound)
2209                   {
2210                     if (syntax & RE_NO_BK_BRACES)
2211                       goto unfetch_interval;
2212                     else 
2213                       return REG_BADBR;
2214                   }
2215
2216                 if (!(syntax & RE_NO_BK_BRACES)) 
2217                   {
2218                     if (c != '\\') return REG_EBRACE;
2219
2220                     PATFETCH (c);
2221                   }
2222
2223                 if (c != '}')
2224                   {
2225                     if (syntax & RE_NO_BK_BRACES)
2226                       goto unfetch_interval;
2227                     else 
2228                       return REG_BADBR;
2229                   }
2230
2231                 /* We just parsed a valid interval.  */
2232
2233                 /* If it's invalid to have no preceding re.  */
2234                 if (!laststart)
2235                   {
2236                     if (syntax & RE_CONTEXT_INVALID_OPS)
2237                       return REG_BADRPT;
2238                     else if (syntax & RE_CONTEXT_INDEP_OPS)
2239                       laststart = b;
2240                     else
2241                       goto unfetch_interval;
2242                   }
2243
2244                 /* If the upper bound is zero, don't want to succeed at
2245                    all; jump from `laststart' to `b + 3', which will be
2246                    the end of the buffer after we insert the jump.  */
2247                  if (upper_bound == 0)
2248                    {
2249                      GET_BUFFER_SPACE (3);
2250                      INSERT_JUMP (jump, laststart, b + 3);
2251                      b += 3;
2252                    }
2253
2254                  /* Otherwise, we have a nontrivial interval.  When
2255                     we're all done, the pattern will look like:
2256                       set_number_at <jump count> <upper bound>
2257                       set_number_at <succeed_n count> <lower bound>
2258                       succeed_n <after jump addr> <succeed_n count>
2259                       <body of loop>
2260                       jump_n <succeed_n addr> <jump count>
2261                     (The upper bound and `jump_n' are omitted if
2262                     `upper_bound' is 1, though.)  */
2263                  else 
2264                    { /* If the upper bound is > 1, we need to insert
2265                         more at the end of the loop.  */
2266                      unsigned nbytes = 10 + (upper_bound > 1) * 10;
2267
2268                      GET_BUFFER_SPACE (nbytes);
2269
2270                      /* Initialize lower bound of the `succeed_n', even
2271                         though it will be set during matching by its
2272                         attendant `set_number_at' (inserted next),
2273                         because `re_compile_fastmap' needs to know.
2274                         Jump to the `jump_n' we might insert below.  */
2275                      INSERT_JUMP2 (succeed_n, laststart,
2276                                    b + 5 + (upper_bound > 1) * 5,
2277                                    lower_bound);
2278                      b += 5;
2279
2280                      /* Code to initialize the lower bound.  Insert 
2281                         before the `succeed_n'.  The `5' is the last two
2282                         bytes of this `set_number_at', plus 3 bytes of
2283                         the following `succeed_n'.  */
2284                      insert_op2 (set_number_at, laststart, 5, lower_bound, b);
2285                      b += 5;
2286
2287                      if (upper_bound > 1)
2288                        { /* More than one repetition is allowed, so
2289                             append a backward jump to the `succeed_n'
2290                             that starts this interval.
2291                             
2292                             When we've reached this during matching,
2293                             we'll have matched the interval once, so
2294                             jump back only `upper_bound - 1' times.  */
2295                          STORE_JUMP2 (jump_n, b, laststart + 5,
2296                                       upper_bound - 1);
2297                          b += 5;
2298
2299                          /* The location we want to set is the second
2300                             parameter of the `jump_n'; that is `b-2' as
2301                             an absolute address.  `laststart' will be
2302                             the `set_number_at' we're about to insert;
2303                             `laststart+3' the number to set, the source
2304                             for the relative address.  But we are
2305                             inserting into the middle of the pattern --
2306                             so everything is getting moved up by 5.
2307                             Conclusion: (b - 2) - (laststart + 3) + 5,
2308                             i.e., b - laststart.
2309                             
2310                             We insert this at the beginning of the loop
2311                             so that if we fail during matching, we'll
2312                             reinitialize the bounds.  */
2313                          insert_op2 (set_number_at, laststart, b - laststart,
2314                                      upper_bound - 1, b);
2315                          b += 5;
2316                        }
2317                    }
2318                 pending_exact = 0;
2319                 beg_interval = NULL;
2320               }
2321               break;
2322
2323             unfetch_interval:
2324               /* If an invalid interval, match the characters as literals.  */
2325                assert (beg_interval);
2326                p = beg_interval;
2327                beg_interval = NULL;
2328
2329                /* normal_char and normal_backslash need `c'.  */
2330                PATFETCH (c);    
2331
2332                if (!(syntax & RE_NO_BK_BRACES))
2333                  {
2334                    if (p > pattern  &&  p[-1] == '\\')
2335                      goto normal_backslash;
2336                  }
2337                goto normal_char;
2338
2339 #ifdef emacs
2340             /* There is no way to specify the before_dot and after_dot
2341                operators.  rms says this is ok.  --karl  */
2342             case '=':
2343               BUF_PUSH (at_dot);
2344               break;
2345
2346             case 's':   
2347               laststart = b;
2348               PATFETCH (c);
2349               BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
2350               break;
2351
2352             case 'S':
2353               laststart = b;
2354               PATFETCH (c);
2355               BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
2356               break;
2357 #endif /* emacs */
2358
2359
2360             case 'w':
2361               laststart = b;
2362               BUF_PUSH (wordchar);
2363               break;
2364
2365
2366             case 'W':
2367               laststart = b;
2368               BUF_PUSH (notwordchar);
2369               break;
2370
2371
2372             case '<':
2373               BUF_PUSH (wordbeg);
2374               break;
2375
2376             case '>':
2377               BUF_PUSH (wordend);
2378               break;
2379
2380             case 'b':
2381               BUF_PUSH (wordbound);
2382               break;
2383
2384             case 'B':
2385               BUF_PUSH (notwordbound);
2386               break;
2387
2388             case '`':
2389               BUF_PUSH (begbuf);
2390               break;
2391
2392             case '\'':
2393               BUF_PUSH (endbuf);
2394               break;
2395
2396             case '1': case '2': case '3': case '4': case '5':
2397             case '6': case '7': case '8': case '9':
2398               if (syntax & RE_NO_BK_REFS)
2399                 goto normal_char;
2400
2401               c1 = c - '0';
2402
2403               if (c1 > regnum)
2404                 return REG_ESUBREG;
2405
2406               /* Can't back reference to a subexpression if inside of it.  */
2407               if (group_in_compile_stack (compile_stack, c1))
2408                 goto normal_char;
2409
2410               laststart = b;
2411               BUF_PUSH_2 (duplicate, c1);
2412               break;
2413
2414
2415             case '+':
2416             case '?':
2417               if (syntax & RE_BK_PLUS_QM)
2418                 goto handle_plus;
2419               else
2420                 goto normal_backslash;
2421
2422             default:
2423             normal_backslash:
2424               /* You might think it would be useful for \ to mean
2425                  not to translate; but if we don't translate it
2426                  it will never match anything.  */
2427               c = TRANSLATE (c);
2428               goto normal_char;
2429             }
2430           break;
2431
2432
2433         default:
2434         /* Expects the character in `c'.  */
2435         normal_char:
2436               /* If no exactn currently being built.  */
2437           if (!pending_exact 
2438
2439               /* If last exactn not at current position.  */
2440               || pending_exact + *pending_exact + 1 != b
2441               
2442               /* We have only one byte following the exactn for the count.  */
2443               || *pending_exact == (1 << BYTEWIDTH) - 1
2444
2445               /* If followed by a repetition operator.  */
2446               || *p == '*' || *p == '^'
2447               || ((syntax & RE_BK_PLUS_QM)
2448                   ? *p == '\\' && (p[1] == '+' || p[1] == '?')
2449                   : (*p == '+' || *p == '?'))
2450               || ((syntax & RE_INTERVALS)
2451                   && ((syntax & RE_NO_BK_BRACES)
2452                       ? *p == '{'
2453                       : (p[0] == '\\' && p[1] == '{'))))
2454             {
2455               /* Start building a new exactn.  */
2456               
2457               laststart = b;
2458
2459               BUF_PUSH_2 (exactn, 0);
2460               pending_exact = b - 1;
2461             }
2462             
2463           BUF_PUSH (c);
2464           (*pending_exact)++;
2465           break;
2466         } /* switch (c) */
2467     } /* while p != pend */
2468
2469   
2470   /* Through the pattern now.  */
2471   
2472   if (fixup_alt_jump)
2473     STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
2474
2475   if (!COMPILE_STACK_EMPTY) 
2476     return REG_EPAREN;
2477
2478   free (compile_stack.stack);
2479
2480   /* We have succeeded; set the length of the buffer.  */
2481   bufp->used = b - bufp->buffer;
2482
2483 #ifdef DEBUG
2484   if (debug)
2485     {
2486       DEBUG_PRINT1 ("\nCompiled pattern: \n");
2487       print_compiled_pattern (bufp);
2488     }
2489 #endif /* DEBUG */
2490
2491 #ifndef MATCH_MAY_ALLOCATE
2492   /* Initialize the failure stack to the largest possible stack.  This
2493      isn't necessary unless we're trying to avoid calling alloca in
2494      the search and match routines.  */
2495   {
2496     int num_regs = bufp->re_nsub + 1;
2497
2498     /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
2499        is strictly greater than re_max_failures, the largest possible stack
2500        is 2 * re_max_failures failure points.  */
2501     if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
2502       {
2503         fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
2504
2505 #ifdef emacs
2506         if (! fail_stack.stack)
2507           fail_stack.stack
2508             = (fail_stack_elt_t *) xmalloc (fail_stack.size 
2509                                             * sizeof (fail_stack_elt_t));
2510         else
2511           fail_stack.stack
2512             = (fail_stack_elt_t *) xrealloc (fail_stack.stack,
2513                                              (fail_stack.size
2514                                               * sizeof (fail_stack_elt_t)));
2515 #else /* not emacs */
2516         if (! fail_stack.stack)
2517           fail_stack.stack
2518             = (fail_stack_elt_t *) malloc (fail_stack.size 
2519                                            * sizeof (fail_stack_elt_t));
2520         else
2521           fail_stack.stack
2522             = (fail_stack_elt_t *) realloc (fail_stack.stack,
2523                                             (fail_stack.size
2524                                              * sizeof (fail_stack_elt_t)));
2525 #endif /* not emacs */
2526       }
2527
2528     /* Initialize some other variables the matcher uses.  */
2529     RETALLOC_IF (regstart,       num_regs, const char *);
2530     RETALLOC_IF (regend,         num_regs, const char *);
2531     RETALLOC_IF (old_regstart,   num_regs, const char *);
2532     RETALLOC_IF (old_regend,     num_regs, const char *);
2533     RETALLOC_IF (best_regstart,  num_regs, const char *);
2534     RETALLOC_IF (best_regend,    num_regs, const char *);
2535     RETALLOC_IF (reg_info,       num_regs, register_info_type);
2536     RETALLOC_IF (reg_dummy,      num_regs, const char *);
2537     RETALLOC_IF (reg_info_dummy, num_regs, register_info_type);
2538   }
2539 #endif
2540
2541   return REG_NOERROR;
2542 } /* regex_compile */
2543 \f
2544 /* Subroutines for `regex_compile'.  */
2545
2546 /* Store OP at LOC followed by two-byte integer parameter ARG.  */
2547
2548 static void
2549 store_op1 (op, loc, arg)
2550     re_opcode_t op;
2551     unsigned char *loc;
2552     int arg;
2553 {
2554   *loc = (unsigned char) op;
2555   STORE_NUMBER (loc + 1, arg);
2556 }
2557
2558
2559 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2.  */
2560
2561 static void
2562 store_op2 (op, loc, arg1, arg2)
2563     re_opcode_t op;
2564     unsigned char *loc;
2565     int arg1, arg2;
2566 {
2567   *loc = (unsigned char) op;
2568   STORE_NUMBER (loc + 1, arg1);
2569   STORE_NUMBER (loc + 3, arg2);
2570 }
2571
2572
2573 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
2574    for OP followed by two-byte integer parameter ARG.  */
2575
2576 static void
2577 insert_op1 (op, loc, arg, end)
2578     re_opcode_t op;
2579     unsigned char *loc;
2580     int arg;
2581     unsigned char *end;    
2582 {
2583   register unsigned char *pfrom = end;
2584   register unsigned char *pto = end + 3;
2585
2586   while (pfrom != loc)
2587     *--pto = *--pfrom;
2588     
2589   store_op1 (op, loc, arg);
2590 }
2591
2592
2593 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2.  */
2594
2595 static void
2596 insert_op2 (op, loc, arg1, arg2, end)
2597     re_opcode_t op;
2598     unsigned char *loc;
2599     int arg1, arg2;
2600     unsigned char *end;    
2601 {
2602   register unsigned char *pfrom = end;
2603   register unsigned char *pto = end + 5;
2604
2605   while (pfrom != loc)
2606     *--pto = *--pfrom;
2607     
2608   store_op2 (op, loc, arg1, arg2);
2609 }
2610
2611
2612 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
2613    after an alternative or a begin-subexpression.  We assume there is at
2614    least one character before the ^.  */
2615
2616 static boolean
2617 at_begline_loc_p (pattern, p, syntax)
2618     const char *pattern, *p;
2619     reg_syntax_t syntax;
2620 {
2621   const char *prev = p - 2;
2622   boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
2623   
2624   return
2625        /* After a subexpression?  */
2626        (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
2627        /* After an alternative?  */
2628     || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
2629 }
2630
2631
2632 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
2633    at least one character after the $, i.e., `P < PEND'.  */
2634
2635 static boolean
2636 at_endline_loc_p (p, pend, syntax)
2637     const char *p, *pend;
2638     int syntax;
2639 {
2640   const char *next = p;
2641   boolean next_backslash = *next == '\\';
2642   const char *next_next = p + 1 < pend ? p + 1 : NULL;
2643   
2644   return
2645        /* Before a subexpression?  */
2646        (syntax & RE_NO_BK_PARENS ? *next == ')'
2647         : next_backslash && next_next && *next_next == ')')
2648        /* Before an alternative?  */
2649     || (syntax & RE_NO_BK_VBAR ? *next == '|'
2650         : next_backslash && next_next && *next_next == '|');
2651 }
2652
2653
2654 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and 
2655    false if it's not.  */
2656
2657 static boolean
2658 group_in_compile_stack (compile_stack, regnum)
2659     compile_stack_type compile_stack;
2660     regnum_t regnum;
2661 {
2662   int this_element;
2663
2664   for (this_element = compile_stack.avail - 1;  
2665        this_element >= 0; 
2666        this_element--)
2667     if (compile_stack.stack[this_element].regnum == regnum)
2668       return true;
2669
2670   return false;
2671 }
2672
2673
2674 /* Read the ending character of a range (in a bracket expression) from the
2675    uncompiled pattern *P_PTR (which ends at PEND).  We assume the
2676    starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
2677    Then we set the translation of all bits between the starting and
2678    ending characters (inclusive) in the compiled pattern B.
2679    
2680    Return an error code.
2681    
2682    We use these short variable names so we can use the same macros as
2683    `regex_compile' itself.  */
2684
2685 static reg_errcode_t
2686 compile_range (p_ptr, pend, translate, syntax, b)
2687     const char **p_ptr, *pend;
2688     char *translate;
2689     reg_syntax_t syntax;
2690     unsigned char *b;
2691 {
2692   unsigned this_char;
2693
2694   const char *p = *p_ptr;
2695   int range_start, range_end;
2696   
2697   if (p == pend)
2698     return REG_ERANGE;
2699
2700   /* Even though the pattern is a signed `char *', we need to fetch
2701      with unsigned char *'s; if the high bit of the pattern character
2702      is set, the range endpoints will be negative if we fetch using a
2703      signed char *.
2704
2705      We also want to fetch the endpoints without translating them; the 
2706      appropriate translation is done in the bit-setting loop below.  */
2707   range_start = ((unsigned char *) p)[-2];
2708   range_end   = ((unsigned char *) p)[0];
2709
2710   /* Have to increment the pointer into the pattern string, so the
2711      caller isn't still at the ending character.  */
2712   (*p_ptr)++;
2713
2714   /* If the start is after the end, the range is empty.  */
2715   if (range_start > range_end)
2716     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
2717
2718   /* Here we see why `this_char' has to be larger than an `unsigned
2719      char' -- the range is inclusive, so if `range_end' == 0xff
2720      (assuming 8-bit characters), we would otherwise go into an infinite
2721      loop, since all characters <= 0xff.  */
2722   for (this_char = range_start; this_char <= range_end; this_char++)
2723     {
2724       SET_LIST_BIT (TRANSLATE (this_char));
2725     }
2726   
2727   return REG_NOERROR;
2728 }
2729 \f
2730 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
2731    BUFP.  A fastmap records which of the (1 << BYTEWIDTH) possible
2732    characters can start a string that matches the pattern.  This fastmap
2733    is used by re_search to skip quickly over impossible starting points.
2734
2735    The caller must supply the address of a (1 << BYTEWIDTH)-byte data
2736    area as BUFP->fastmap.
2737    
2738    We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
2739    the pattern buffer.
2740
2741    Returns 0 if we succeed, -2 if an internal error.   */
2742
2743 int
2744 re_compile_fastmap (bufp)
2745      struct re_pattern_buffer *bufp;
2746 {
2747   int j, k;
2748 #ifdef MATCH_MAY_ALLOCATE
2749   fail_stack_type fail_stack;
2750 #endif
2751 #ifndef REGEX_MALLOC
2752   char *destination;
2753 #endif
2754   /* We don't push any register information onto the failure stack.  */
2755   unsigned num_regs = 0;
2756   
2757   register char *fastmap = bufp->fastmap;
2758   unsigned char *pattern = bufp->buffer;
2759   unsigned long size = bufp->used;
2760   unsigned char *p = pattern;
2761   register unsigned char *pend = pattern + size;
2762
2763   /* Assume that each path through the pattern can be null until
2764      proven otherwise.  We set this false at the bottom of switch
2765      statement, to which we get only if a particular path doesn't
2766      match the empty string.  */
2767   boolean path_can_be_null = true;
2768
2769   /* We aren't doing a `succeed_n' to begin with.  */
2770   boolean succeed_n_p = false;
2771
2772   assert (fastmap != NULL && p != NULL);
2773   
2774   INIT_FAIL_STACK ();
2775   bzero (fastmap, 1 << BYTEWIDTH);  /* Assume nothing's valid.  */
2776   bufp->fastmap_accurate = 1;       /* It will be when we're done.  */
2777   bufp->can_be_null = 0;
2778       
2779   while (p != pend || !FAIL_STACK_EMPTY ())
2780     {
2781       if (p == pend)
2782         {
2783           bufp->can_be_null |= path_can_be_null;
2784           
2785           /* Reset for next path.  */
2786           path_can_be_null = true;
2787           
2788           p = fail_stack.stack[--fail_stack.avail];
2789         }
2790
2791       /* We should never be about to go beyond the end of the pattern.  */
2792       assert (p < pend);
2793       
2794 #ifdef SWITCH_ENUM_BUG
2795       switch ((int) ((re_opcode_t) *p++))
2796 #else
2797       switch ((re_opcode_t) *p++)
2798 #endif
2799         {
2800
2801         /* I guess the idea here is to simply not bother with a fastmap
2802            if a backreference is used, since it's too hard to figure out
2803            the fastmap for the corresponding group.  Setting
2804            `can_be_null' stops `re_search_2' from using the fastmap, so
2805            that is all we do.  */
2806         case duplicate:
2807           bufp->can_be_null = 1;
2808           return 0;
2809
2810
2811       /* Following are the cases which match a character.  These end
2812          with `break'.  */
2813
2814         case exactn:
2815           fastmap[p[1]] = 1;
2816           break;
2817
2818
2819         case charset:
2820           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2821             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
2822               fastmap[j] = 1;
2823           break;
2824
2825
2826         case charset_not:
2827           /* Chars beyond end of map must be allowed.  */
2828           for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
2829             fastmap[j] = 1;
2830
2831           for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
2832             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
2833               fastmap[j] = 1;
2834           break;
2835
2836
2837         case wordchar:
2838           for (j = 0; j < (1 << BYTEWIDTH); j++)
2839             if (SYNTAX (j) == Sword)
2840               fastmap[j] = 1;
2841           break;
2842
2843
2844         case notwordchar:
2845           for (j = 0; j < (1 << BYTEWIDTH); j++)
2846             if (SYNTAX (j) != Sword)
2847               fastmap[j] = 1;
2848           break;
2849
2850
2851         case anychar:
2852           /* `.' matches anything ...  */
2853           for (j = 0; j < (1 << BYTEWIDTH); j++)
2854             fastmap[j] = 1;
2855
2856           /* ... except perhaps newline.  */
2857           if (!(bufp->syntax & RE_DOT_NEWLINE))
2858             fastmap['\n'] = 0;
2859
2860           /* Return if we have already set `can_be_null'; if we have,
2861              then the fastmap is irrelevant.  Something's wrong here.  */
2862           else if (bufp->can_be_null)
2863             return 0;
2864
2865           /* Otherwise, have to check alternative paths.  */
2866           break;
2867
2868
2869 #ifdef emacs
2870         case syntaxspec:
2871           k = *p++;
2872           for (j = 0; j < (1 << BYTEWIDTH); j++)
2873             if (SYNTAX (j) == (enum syntaxcode) k)
2874               fastmap[j] = 1;
2875           break;
2876
2877
2878         case notsyntaxspec:
2879           k = *p++;
2880           for (j = 0; j < (1 << BYTEWIDTH); j++)
2881             if (SYNTAX (j) != (enum syntaxcode) k)
2882               fastmap[j] = 1;
2883           break;
2884
2885
2886       /* All cases after this match the empty string.  These end with
2887          `continue'.  */
2888
2889
2890         case before_dot:
2891         case at_dot:
2892         case after_dot:
2893           continue;
2894 #endif /* not emacs */
2895
2896
2897         case no_op:
2898         case begline:
2899         case endline:
2900         case begbuf:
2901         case endbuf:
2902         case wordbound:
2903         case notwordbound:
2904         case wordbeg:
2905         case wordend:
2906         case push_dummy_failure:
2907           continue;
2908
2909
2910         case jump_n:
2911         case pop_failure_jump:
2912         case maybe_pop_jump:
2913         case jump:
2914         case jump_past_alt:
2915         case dummy_failure_jump:
2916           EXTRACT_NUMBER_AND_INCR (j, p);
2917           p += j;       
2918           if (j > 0)
2919             continue;
2920             
2921           /* Jump backward implies we just went through the body of a
2922              loop and matched nothing.  Opcode jumped to should be
2923              `on_failure_jump' or `succeed_n'.  Just treat it like an
2924              ordinary jump.  For a * loop, it has pushed its failure
2925              point already; if so, discard that as redundant.  */
2926           if ((re_opcode_t) *p != on_failure_jump
2927               && (re_opcode_t) *p != succeed_n)
2928             continue;
2929
2930           p++;
2931           EXTRACT_NUMBER_AND_INCR (j, p);
2932           p += j;               
2933           
2934           /* If what's on the stack is where we are now, pop it.  */
2935           if (!FAIL_STACK_EMPTY () 
2936               && fail_stack.stack[fail_stack.avail - 1] == p)
2937             fail_stack.avail--;
2938
2939           continue;
2940
2941
2942         case on_failure_jump:
2943         case on_failure_keep_string_jump:
2944         handle_on_failure_jump:
2945           EXTRACT_NUMBER_AND_INCR (j, p);
2946
2947           /* For some patterns, e.g., `(a?)?', `p+j' here points to the
2948              end of the pattern.  We don't want to push such a point,
2949              since when we restore it above, entering the switch will
2950              increment `p' past the end of the pattern.  We don't need
2951              to push such a point since we obviously won't find any more
2952              fastmap entries beyond `pend'.  Such a pattern can match
2953              the null string, though.  */
2954           if (p + j < pend)
2955             {
2956               if (!PUSH_PATTERN_OP (p + j, fail_stack))
2957                 return -2;
2958             }
2959           else
2960             bufp->can_be_null = 1;
2961
2962           if (succeed_n_p)
2963             {
2964               EXTRACT_NUMBER_AND_INCR (k, p);   /* Skip the n.  */
2965               succeed_n_p = false;
2966             }
2967
2968           continue;
2969
2970
2971         case succeed_n:
2972           /* Get to the number of times to succeed.  */
2973           p += 2;               
2974
2975           /* Increment p past the n for when k != 0.  */
2976           EXTRACT_NUMBER_AND_INCR (k, p);
2977           if (k == 0)
2978             {
2979               p -= 4;
2980               succeed_n_p = true;  /* Spaghetti code alert.  */
2981               goto handle_on_failure_jump;
2982             }
2983           continue;
2984
2985
2986         case set_number_at:
2987           p += 4;
2988           continue;
2989
2990
2991         case start_memory:
2992         case stop_memory:
2993           p += 2;
2994           continue;
2995
2996
2997         default:
2998           abort (); /* We have listed all the cases.  */
2999         } /* switch *p++ */
3000
3001       /* Getting here means we have found the possible starting
3002          characters for one path of the pattern -- and that the empty
3003          string does not match.  We need not follow this path further.
3004          Instead, look at the next alternative (remembered on the
3005          stack), or quit if no more.  The test at the top of the loop
3006          does these things.  */
3007       path_can_be_null = false;
3008       p = pend;
3009     } /* while p */
3010
3011   /* Set `can_be_null' for the last path (also the first path, if the
3012      pattern is empty).  */
3013   bufp->can_be_null |= path_can_be_null;
3014   return 0;
3015 } /* re_compile_fastmap */
3016 \f
3017 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
3018    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
3019    this memory for recording register information.  STARTS and ENDS
3020    must be allocated using the malloc library routine, and must each
3021    be at least NUM_REGS * sizeof (regoff_t) bytes long.
3022
3023    If NUM_REGS == 0, then subsequent matches should allocate their own
3024    register data.
3025
3026    Unless this function is called, the first search or match using
3027    PATTERN_BUFFER will allocate its own register data, without
3028    freeing the old data.  */
3029
3030 void
3031 re_set_registers (bufp, regs, num_regs, starts, ends)
3032     struct re_pattern_buffer *bufp;
3033     struct re_registers *regs;
3034     unsigned num_regs;
3035     regoff_t *starts, *ends;
3036 {
3037   if (num_regs)
3038     {
3039       bufp->regs_allocated = REGS_REALLOCATE;
3040       regs->num_regs = num_regs;
3041       regs->start = starts;
3042       regs->end = ends;
3043     }
3044   else
3045     {
3046       bufp->regs_allocated = REGS_UNALLOCATED;
3047       regs->num_regs = 0;
3048       regs->start = regs->end = (regoff_t *) 0;
3049     }
3050 }
3051 \f
3052 /* Searching routines.  */
3053
3054 /* Like re_search_2, below, but only one string is specified, and
3055    doesn't let you say where to stop matching. */
3056
3057 int
3058 re_search (bufp, string, size, startpos, range, regs)
3059      struct re_pattern_buffer *bufp;
3060      const char *string;
3061      int size, startpos, range;
3062      struct re_registers *regs;
3063 {
3064   return re_search_2 (bufp, NULL, 0, string, size, startpos, range, 
3065                       regs, size);
3066 }
3067
3068
3069 /* Using the compiled pattern in BUFP->buffer, first tries to match the
3070    virtual concatenation of STRING1 and STRING2, starting first at index
3071    STARTPOS, then at STARTPOS + 1, and so on.
3072    
3073    STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
3074    
3075    RANGE is how far to scan while trying to match.  RANGE = 0 means try
3076    only at STARTPOS; in general, the last start tried is STARTPOS +
3077    RANGE.
3078    
3079    In REGS, return the indices of the virtual concatenation of STRING1
3080    and STRING2 that matched the entire BUFP->buffer and its contained
3081    subexpressions.
3082    
3083    Do not consider matching one past the index STOP in the virtual
3084    concatenation of STRING1 and STRING2.
3085
3086    We return either the position in the strings at which the match was
3087    found, -1 if no match, or -2 if error (such as failure
3088    stack overflow).  */
3089
3090 int
3091 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
3092      struct re_pattern_buffer *bufp;
3093      const char *string1, *string2;
3094      int size1, size2;
3095      int startpos;
3096      int range;
3097      struct re_registers *regs;
3098      int stop;
3099 {
3100   int val;
3101   register char *fastmap = bufp->fastmap;
3102   register char *translate = bufp->translate;
3103   int total_size = size1 + size2;
3104   int endpos = startpos + range;
3105
3106   /* Check for out-of-range STARTPOS.  */
3107   if (startpos < 0 || startpos > total_size)
3108     return -1;
3109     
3110   /* Fix up RANGE if it might eventually take us outside
3111      the virtual concatenation of STRING1 and STRING2.  */
3112   if (endpos < -1)
3113     range = -1 - startpos;
3114   else if (endpos > total_size)
3115     range = total_size - startpos;
3116
3117   /* If the search isn't to be a backwards one, don't waste time in a
3118      search for a pattern that must be anchored.  */
3119   if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0)
3120     {
3121       if (startpos > 0)
3122         return -1;
3123       else
3124         range = 1;
3125     }
3126
3127   /* Update the fastmap now if not correct already.  */
3128   if (fastmap && !bufp->fastmap_accurate)
3129     if (re_compile_fastmap (bufp) == -2)
3130       return -2;
3131   
3132   /* Loop through the string, looking for a place to start matching.  */
3133   for (;;)
3134     { 
3135       /* If a fastmap is supplied, skip quickly over characters that
3136          cannot be the start of a match.  If the pattern can match the
3137          null string, however, we don't need to skip characters; we want
3138          the first null string.  */
3139       if (fastmap && startpos < total_size && !bufp->can_be_null)
3140         {
3141           if (range > 0)        /* Searching forwards.  */
3142             {
3143               register const char *d;
3144               register int lim = 0;
3145               int irange = range;
3146
3147               if (startpos < size1 && startpos + range >= size1)
3148                 lim = range - (size1 - startpos);
3149
3150               d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
3151    
3152               /* Written out as an if-else to avoid testing `translate'
3153                  inside the loop.  */
3154               if (translate)
3155                 while (range > lim
3156                        && !fastmap[(unsigned char)
3157                                    translate[(unsigned char) *d++]])
3158                   range--;
3159               else
3160                 while (range > lim && !fastmap[(unsigned char) *d++])
3161                   range--;
3162
3163               startpos += irange - range;
3164             }
3165           else                          /* Searching backwards.  */
3166             {
3167               register char c = (size1 == 0 || startpos >= size1
3168                                  ? string2[startpos - size1] 
3169                                  : string1[startpos]);
3170
3171               if (!fastmap[(unsigned char) TRANSLATE (c)])
3172                 goto advance;
3173             }
3174         }
3175
3176       /* If can't match the null string, and that's all we have left, fail.  */
3177       if (range >= 0 && startpos == total_size && fastmap
3178           && !bufp->can_be_null)
3179         return -1;
3180
3181       val = re_match_2_internal (bufp, string1, size1, string2, size2,
3182                                  startpos, regs, stop);
3183 #ifndef REGEX_MALLOC
3184 #ifdef C_ALLOCA
3185       alloca (0);
3186 #endif
3187 #endif
3188
3189       if (val >= 0)
3190         return startpos;
3191         
3192       if (val == -2)
3193         return -2;
3194
3195     advance:
3196       if (!range) 
3197         break;
3198       else if (range > 0) 
3199         {
3200           range--; 
3201           startpos++;
3202         }
3203       else
3204         {
3205           range++; 
3206           startpos--;
3207         }
3208     }
3209   return -1;
3210 } /* re_search_2 */
3211 \f
3212 /* Declarations and macros for re_match_2.  */
3213
3214 static int bcmp_translate ();
3215 static boolean alt_match_null_string_p (),
3216                common_op_match_null_string_p (),
3217                group_match_null_string_p ();
3218
3219 /* This converts PTR, a pointer into one of the search strings `string1'
3220    and `string2' into an offset from the beginning of that string.  */
3221 #define POINTER_TO_OFFSET(ptr)                  \
3222   (FIRST_STRING_P (ptr)                         \
3223    ? ((regoff_t) ((ptr) - string1))             \
3224    : ((regoff_t) ((ptr) - string2 + size1)))
3225
3226 /* Macros for dealing with the split strings in re_match_2.  */
3227
3228 #define MATCHING_IN_FIRST_STRING  (dend == end_match_1)
3229
3230 /* Call before fetching a character with *d.  This switches over to
3231    string2 if necessary.  */
3232 #define PREFETCH()                                                      \
3233   while (d == dend)                                                     \
3234     {                                                                   \
3235       /* End of string2 => fail.  */                                    \
3236       if (dend == end_match_2)                                          \
3237         goto fail;                                                      \
3238       /* End of string1 => advance to string2.  */                      \
3239       d = string2;                                                      \
3240       dend = end_match_2;                                               \
3241     }
3242
3243
3244 /* Test if at very beginning or at very end of the virtual concatenation
3245    of `string1' and `string2'.  If only one string, it's `string2'.  */
3246 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
3247 #define AT_STRINGS_END(d) ((d) == end2) 
3248
3249
3250 /* Test if D points to a character which is word-constituent.  We have
3251    two special cases to check for: if past the end of string1, look at
3252    the first character in string2; and if before the beginning of
3253    string2, look at the last character in string1.  */
3254 #define WORDCHAR_P(d)                                                   \
3255   (SYNTAX ((d) == end1 ? *string2                                       \
3256            : (d) == string2 - 1 ? *(end1 - 1) : *(d))                   \
3257    == Sword)
3258
3259 /* Test if the character before D and the one at D differ with respect
3260    to being word-constituent.  */
3261 #define AT_WORD_BOUNDARY(d)                                             \
3262   (AT_STRINGS_BEG (d) || AT_STRINGS_END (d)                             \
3263    || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
3264
3265
3266 /* Free everything we malloc.  */
3267 #ifdef MATCH_MAY_ALLOCATE
3268 #ifdef REGEX_MALLOC
3269 #define FREE_VAR(var) if (var) free (var); var = NULL
3270 #define FREE_VARIABLES()                                                \
3271   do {                                                                  \
3272     FREE_VAR (fail_stack.stack);                                        \
3273     FREE_VAR (regstart);                                                \
3274     FREE_VAR (regend);                                                  \
3275     FREE_VAR (old_regstart);                                            \
3276     FREE_VAR (old_regend);                                              \
3277     FREE_VAR (best_regstart);                                           \
3278     FREE_VAR (best_regend);                                             \
3279     FREE_VAR (reg_info);                                                \
3280     FREE_VAR (reg_dummy);                                               \
3281     FREE_VAR (reg_info_dummy);                                          \
3282   } while (0)
3283 #else /* not REGEX_MALLOC */
3284 /* This used to do alloca (0), but now we do that in the caller.  */
3285 #define FREE_VARIABLES() /* Nothing */
3286 #endif /* not REGEX_MALLOC */
3287 #else
3288 #define FREE_VARIABLES() /* Do nothing!  */
3289 #endif /* not MATCH_MAY_ALLOCATE */
3290
3291 /* These values must meet several constraints.  They must not be valid
3292    register values; since we have a limit of 255 registers (because
3293    we use only one byte in the pattern for the register number), we can
3294    use numbers larger than 255.  They must differ by 1, because of
3295    NUM_FAILURE_ITEMS above.  And the value for the lowest register must
3296    be larger than the value for the highest register, so we do not try
3297    to actually save any registers when none are active.  */
3298 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
3299 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
3300 \f
3301 /* Matching routines.  */
3302
3303 #ifndef emacs   /* Emacs never uses this.  */
3304 /* re_match is like re_match_2 except it takes only a single string.  */
3305
3306 int
3307 re_match (bufp, string, size, pos, regs)
3308      struct re_pattern_buffer *bufp;
3309      const char *string;
3310      int size, pos;
3311      struct re_registers *regs;
3312 {
3313   int result = re_match_2_internal (bufp, NULL, 0, string, size,
3314                                     pos, regs, size);
3315   alloca (0);
3316   return result;
3317 }
3318 #endif /* not emacs */
3319
3320
3321 /* re_match_2 matches the compiled pattern in BUFP against the
3322    the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
3323    and SIZE2, respectively).  We start matching at POS, and stop
3324    matching at STOP.
3325    
3326    If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
3327    store offsets for the substring each group matched in REGS.  See the
3328    documentation for exactly how many groups we fill.
3329
3330    We return -1 if no match, -2 if an internal error (such as the
3331    failure stack overflowing).  Otherwise, we return the length of the
3332    matched substring.  */
3333
3334 int
3335 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
3336      struct re_pattern_buffer *bufp;
3337      const char *string1, *string2;
3338      int size1, size2;
3339      int pos;
3340      struct re_registers *regs;
3341      int stop;
3342 {
3343   int result = re_match_2_internal (bufp, string1, size1, string2, size2,
3344                                     pos, regs, stop);
3345   alloca (0);
3346   return result;
3347 }
3348
3349 /* This is a separate function so that we can force an alloca cleanup
3350    afterwards.  */
3351 static int
3352 re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop)
3353      struct re_pattern_buffer *bufp;
3354      const char *string1, *string2;
3355      int size1, size2;
3356      int pos;
3357      struct re_registers *regs;
3358      int stop;
3359 {
3360   /* General temporaries.  */
3361   int mcnt;
3362   unsigned char *p1;
3363
3364   /* Just past the end of the corresponding string.  */
3365   const char *end1, *end2;
3366
3367   /* Pointers into string1 and string2, just past the last characters in
3368      each to consider matching.  */
3369   const char *end_match_1, *end_match_2;
3370
3371   /* Where we are in the data, and the end of the current string.  */
3372   const char *d, *dend;
3373   
3374   /* Where we are in the pattern, and the end of the pattern.  */
3375   unsigned char *p = bufp->buffer;
3376   register unsigned char *pend = p + bufp->used;
3377
3378   /* Mark the opcode just after a start_memory, so we can test for an
3379      empty subpattern when we get to the stop_memory.  */
3380   unsigned char *just_past_start_mem = 0;
3381
3382   /* We use this to map every character in the string.  */
3383   char *translate = bufp->translate;
3384
3385   /* Failure point stack.  Each place that can handle a failure further
3386      down the line pushes a failure point on this stack.  It consists of
3387      restart, regend, and reg_info for all registers corresponding to
3388      the subexpressions we're currently inside, plus the number of such
3389      registers, and, finally, two char *'s.  The first char * is where
3390      to resume scanning the pattern; the second one is where to resume
3391      scanning the strings.  If the latter is zero, the failure point is
3392      a ``dummy''; if a failure happens and the failure point is a dummy,
3393      it gets discarded and the next next one is tried.  */
3394 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.  */
3395   fail_stack_type fail_stack;
3396 #endif
3397 #ifdef DEBUG
3398   static unsigned failure_id = 0;
3399   unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
3400 #endif
3401
3402   /* We fill all the registers internally, independent of what we
3403      return, for use in backreferences.  The number here includes
3404      an element for register zero.  */
3405   unsigned num_regs = bufp->re_nsub + 1;
3406   
3407   /* The currently active registers.  */
3408   unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3409   unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3410
3411   /* Information on the contents of registers. These are pointers into
3412      the input strings; they record just what was matched (on this
3413      attempt) by a subexpression part of the pattern, that is, the
3414      regnum-th regstart pointer points to where in the pattern we began
3415      matching and the regnum-th regend points to right after where we
3416      stopped matching the regnum-th subexpression.  (The zeroth register
3417      keeps track of what the whole pattern matches.)  */
3418 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
3419   const char **regstart, **regend;
3420 #endif
3421
3422   /* If a group that's operated upon by a repetition operator fails to
3423      match anything, then the register for its start will need to be
3424      restored because it will have been set to wherever in the string we
3425      are when we last see its open-group operator.  Similarly for a
3426      register's end.  */
3427 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
3428   const char **old_regstart, **old_regend;
3429 #endif
3430
3431   /* The is_active field of reg_info helps us keep track of which (possibly
3432      nested) subexpressions we are currently in. The matched_something
3433      field of reg_info[reg_num] helps us tell whether or not we have
3434      matched any of the pattern so far this time through the reg_num-th
3435      subexpression.  These two fields get reset each time through any
3436      loop their register is in.  */
3437 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global.  */
3438   register_info_type *reg_info; 
3439 #endif
3440
3441   /* The following record the register info as found in the above
3442      variables when we find a match better than any we've seen before. 
3443      This happens as we backtrack through the failure points, which in
3444      turn happens only if we have not yet matched the entire string. */
3445   unsigned best_regs_set = false;
3446 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
3447   const char **best_regstart, **best_regend;
3448 #endif
3449   
3450   /* Logically, this is `best_regend[0]'.  But we don't want to have to
3451      allocate space for that if we're not allocating space for anything
3452      else (see below).  Also, we never need info about register 0 for
3453      any of the other register vectors, and it seems rather a kludge to
3454      treat `best_regend' differently than the rest.  So we keep track of
3455      the end of the best match so far in a separate variable.  We
3456      initialize this to NULL so that when we backtrack the first time
3457      and need to test it, it's not garbage.  */
3458   const char *match_end = NULL;
3459
3460   /* Used when we pop values we don't care about.  */
3461 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global.  */
3462   const char **reg_dummy;
3463   register_info_type *reg_info_dummy;
3464 #endif
3465
3466 #ifdef DEBUG
3467   /* Counts the total number of registers pushed.  */
3468   unsigned num_regs_pushed = 0;         
3469 #endif
3470
3471   DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
3472   
3473   INIT_FAIL_STACK ();
3474   
3475 #ifdef MATCH_MAY_ALLOCATE
3476   /* Do not bother to initialize all the register variables if there are
3477      no groups in the pattern, as it takes a fair amount of time.  If
3478      there are groups, we include space for register 0 (the whole
3479      pattern), even though we never use it, since it simplifies the
3480      array indexing.  We should fix this.  */
3481   if (bufp->re_nsub)
3482     {
3483       regstart = REGEX_TALLOC (num_regs, const char *);
3484       regend = REGEX_TALLOC (num_regs, const char *);
3485       old_regstart = REGEX_TALLOC (num_regs, const char *);
3486       old_regend = REGEX_TALLOC (num_regs, const char *);
3487       best_regstart = REGEX_TALLOC (num_regs, const char *);
3488       best_regend = REGEX_TALLOC (num_regs, const char *);
3489       reg_info = REGEX_TALLOC (num_regs, register_info_type);
3490       reg_dummy = REGEX_TALLOC (num_regs, const char *);
3491       reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type);
3492
3493       if (!(regstart && regend && old_regstart && old_regend && reg_info 
3494             && best_regstart && best_regend && reg_dummy && reg_info_dummy)) 
3495         {
3496           FREE_VARIABLES ();
3497           return -2;
3498         }
3499     }
3500 #if defined (REGEX_MALLOC)
3501   else
3502     {
3503       /* We must initialize all our variables to NULL, so that
3504          `FREE_VARIABLES' doesn't try to free them.  */
3505       regstart = regend = old_regstart = old_regend = best_regstart
3506         = best_regend = reg_dummy = NULL;
3507       reg_info = reg_info_dummy = (register_info_type *) NULL;
3508     }
3509 #endif /* REGEX_MALLOC */
3510 #endif /* MATCH_MAY_ALLOCATE */
3511
3512   /* The starting position is bogus.  */
3513   if (pos < 0 || pos > size1 + size2)
3514     {
3515       FREE_VARIABLES ();
3516       return -1;
3517     }
3518     
3519   /* Initialize subexpression text positions to -1 to mark ones that no
3520      start_memory/stop_memory has been seen for. Also initialize the
3521      register information struct.  */
3522   for (mcnt = 1; mcnt < num_regs; mcnt++)
3523     {
3524       regstart[mcnt] = regend[mcnt] 
3525         = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
3526         
3527       REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
3528       IS_ACTIVE (reg_info[mcnt]) = 0;
3529       MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3530       EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
3531     }
3532   
3533   /* We move `string1' into `string2' if the latter's empty -- but not if
3534      `string1' is null.  */
3535   if (size2 == 0 && string1 != NULL)
3536     {
3537       string2 = string1;
3538       size2 = size1;
3539       string1 = 0;
3540       size1 = 0;
3541     }
3542   end1 = string1 + size1;
3543   end2 = string2 + size2;
3544
3545   /* Compute where to stop matching, within the two strings.  */
3546   if (stop <= size1)
3547     {
3548       end_match_1 = string1 + stop;
3549       end_match_2 = string2;
3550     }
3551   else
3552     {
3553       end_match_1 = end1;
3554       end_match_2 = string2 + stop - size1;
3555     }
3556
3557   /* `p' scans through the pattern as `d' scans through the data. 
3558      `dend' is the end of the input string that `d' points within.  `d'
3559      is advanced into the following input string whenever necessary, but
3560      this happens before fetching; therefore, at the beginning of the
3561      loop, `d' can be pointing at the end of a string, but it cannot
3562      equal `string2'.  */
3563   if (size1 > 0 && pos <= size1)
3564     {
3565       d = string1 + pos;
3566       dend = end_match_1;
3567     }
3568   else
3569     {
3570       d = string2 + pos - size1;
3571       dend = end_match_2;
3572     }
3573
3574   DEBUG_PRINT1 ("The compiled pattern is: ");
3575   DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
3576   DEBUG_PRINT1 ("The string to match is: `");
3577   DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
3578   DEBUG_PRINT1 ("'\n");
3579   
3580   /* This loops over pattern commands.  It exits by returning from the
3581      function if the match is complete, or it drops through if the match
3582      fails at this starting point in the input data.  */
3583   for (;;)
3584     {
3585       DEBUG_PRINT2 ("\n0x%x: ", p);
3586
3587       if (p == pend)
3588         { /* End of pattern means we might have succeeded.  */
3589           DEBUG_PRINT1 ("end of pattern ... ");
3590           
3591           /* If we haven't matched the entire string, and we want the
3592              longest match, try backtracking.  */
3593           if (d != end_match_2)
3594             {
3595               DEBUG_PRINT1 ("backtracking.\n");
3596               
3597               if (!FAIL_STACK_EMPTY ())
3598                 { /* More failure points to try.  */
3599                   boolean same_str_p = (FIRST_STRING_P (match_end) 
3600                                         == MATCHING_IN_FIRST_STRING);
3601
3602                   /* If exceeds best match so far, save it.  */
3603                   if (!best_regs_set
3604                       || (same_str_p && d > match_end)
3605                       || (!same_str_p && !MATCHING_IN_FIRST_STRING))
3606                     {
3607                       best_regs_set = true;
3608                       match_end = d;
3609                       
3610                       DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
3611                       
3612                       for (mcnt = 1; mcnt < num_regs; mcnt++)
3613                         {
3614                           best_regstart[mcnt] = regstart[mcnt];
3615                           best_regend[mcnt] = regend[mcnt];
3616                         }
3617                     }
3618                   goto fail;           
3619                 }
3620
3621               /* If no failure points, don't restore garbage.  */
3622               else if (best_regs_set)   
3623                 {
3624                 restore_best_regs:
3625                   /* Restore best match.  It may happen that `dend ==
3626                      end_match_1' while the restored d is in string2.
3627                      For example, the pattern `x.*y.*z' against the
3628                      strings `x-' and `y-z-', if the two strings are
3629                      not consecutive in memory.  */
3630                   DEBUG_PRINT1 ("Restoring best registers.\n");
3631                   
3632                   d = match_end;
3633                   dend = ((d >= string1 && d <= end1)
3634                            ? end_match_1 : end_match_2);
3635
3636                   for (mcnt = 1; mcnt < num_regs; mcnt++)
3637                     {
3638                       regstart[mcnt] = best_regstart[mcnt];
3639                       regend[mcnt] = best_regend[mcnt];
3640                     }
3641                 }
3642             } /* d != end_match_2 */
3643
3644           DEBUG_PRINT1 ("Accepting match.\n");
3645
3646           /* If caller wants register contents data back, do it.  */
3647           if (regs && !bufp->no_sub)
3648             {
3649               /* Have the register data arrays been allocated?  */
3650               if (bufp->regs_allocated == REGS_UNALLOCATED)
3651                 { /* No.  So allocate them with malloc.  We need one
3652                      extra element beyond `num_regs' for the `-1' marker
3653                      GNU code uses.  */
3654                   regs->num_regs = MAX (RE_NREGS, num_regs + 1);
3655                   regs->start = TALLOC (regs->num_regs, regoff_t);
3656                   regs->end = TALLOC (regs->num_regs, regoff_t);
3657                   if (regs->start == NULL || regs->end == NULL)
3658                     return -2;
3659                   bufp->regs_allocated = REGS_REALLOCATE;
3660                 }
3661               else if (bufp->regs_allocated == REGS_REALLOCATE)
3662                 { /* Yes.  If we need more elements than were already
3663                      allocated, reallocate them.  If we need fewer, just
3664                      leave it alone.  */
3665                   if (regs->num_regs < num_regs + 1)
3666                     {
3667                       regs->num_regs = num_regs + 1;
3668                       RETALLOC (regs->start, regs->num_regs, regoff_t);
3669                       RETALLOC (regs->end, regs->num_regs, regoff_t);
3670                       if (regs->start == NULL || regs->end == NULL)
3671                         return -2;
3672                     }
3673                 }
3674               else
3675                 {
3676                   /* These braces fend off a "empty body in an else-statement"
3677                      warning under GCC when assert expands to nothing.  */
3678                   assert (bufp->regs_allocated == REGS_FIXED);
3679                 }
3680
3681               /* Convert the pointer data in `regstart' and `regend' to
3682                  indices.  Register zero has to be set differently,
3683                  since we haven't kept track of any info for it.  */
3684               if (regs->num_regs > 0)
3685                 {
3686                   regs->start[0] = pos;
3687                   regs->end[0] = (MATCHING_IN_FIRST_STRING
3688                                   ? ((regoff_t) (d - string1))
3689                                   : ((regoff_t) (d - string2 + size1)));
3690                 }
3691               
3692               /* Go through the first `min (num_regs, regs->num_regs)'
3693                  registers, since that is all we initialized.  */
3694               for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++)
3695                 {
3696                   if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
3697                     regs->start[mcnt] = regs->end[mcnt] = -1;
3698                   else
3699                     {
3700                       regs->start[mcnt]
3701                         = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
3702                       regs->end[mcnt]
3703                         = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
3704                     }
3705                 }
3706               
3707               /* If the regs structure we return has more elements than
3708                  were in the pattern, set the extra elements to -1.  If
3709                  we (re)allocated the registers, this is the case,
3710                  because we always allocate enough to have at least one
3711                  -1 at the end.  */
3712               for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++)
3713                 regs->start[mcnt] = regs->end[mcnt] = -1;
3714             } /* regs && !bufp->no_sub */
3715
3716           FREE_VARIABLES ();
3717           DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
3718                         nfailure_points_pushed, nfailure_points_popped,
3719                         nfailure_points_pushed - nfailure_points_popped);
3720           DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
3721
3722           mcnt = d - pos - (MATCHING_IN_FIRST_STRING 
3723                             ? string1 
3724                             : string2 - size1);
3725
3726           DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
3727
3728           return mcnt;
3729         }
3730
3731       /* Otherwise match next pattern command.  */
3732 #ifdef SWITCH_ENUM_BUG
3733       switch ((int) ((re_opcode_t) *p++))
3734 #else
3735       switch ((re_opcode_t) *p++)
3736 #endif
3737         {
3738         /* Ignore these.  Used to ignore the n of succeed_n's which
3739            currently have n == 0.  */
3740         case no_op:
3741           DEBUG_PRINT1 ("EXECUTING no_op.\n");
3742           break;
3743
3744
3745         /* Match the next n pattern characters exactly.  The following
3746            byte in the pattern defines n, and the n bytes after that
3747            are the characters to match.  */
3748         case exactn:
3749           mcnt = *p++;
3750           DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
3751
3752           /* This is written out as an if-else so we don't waste time
3753              testing `translate' inside the loop.  */
3754           if (translate)
3755             {
3756               do
3757                 {
3758                   PREFETCH ();
3759                   if (translate[(unsigned char) *d++] != (char) *p++)
3760                     goto fail;
3761                 }
3762               while (--mcnt);
3763             }
3764           else
3765             {
3766               do
3767                 {
3768                   PREFETCH ();
3769                   if (*d++ != (char) *p++) goto fail;
3770                 }
3771               while (--mcnt);
3772             }
3773           SET_REGS_MATCHED ();
3774           break;
3775
3776
3777         /* Match any character except possibly a newline or a null.  */
3778         case anychar:
3779           DEBUG_PRINT1 ("EXECUTING anychar.\n");
3780
3781           PREFETCH ();
3782
3783           if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
3784               || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
3785             goto fail;
3786
3787           SET_REGS_MATCHED ();
3788           DEBUG_PRINT2 ("  Matched `%d'.\n", *d);
3789           d++;
3790           break;
3791
3792
3793         case charset:
3794         case charset_not:
3795           {
3796             register unsigned char c;
3797             boolean not = (re_opcode_t) *(p - 1) == charset_not;
3798
3799             DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
3800
3801             PREFETCH ();
3802             c = TRANSLATE (*d); /* The character to match.  */
3803
3804             /* Cast to `unsigned' instead of `unsigned char' in case the
3805                bit list is a full 32 bytes long.  */
3806             if (c < (unsigned) (*p * BYTEWIDTH)
3807                 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
3808               not = !not;
3809
3810             p += 1 + *p;
3811
3812             if (!not) goto fail;
3813             
3814             SET_REGS_MATCHED ();
3815             d++;
3816             break;
3817           }
3818
3819
3820         /* The beginning of a group is represented by start_memory.
3821            The arguments are the register number in the next byte, and the
3822            number of groups inner to this one in the next.  The text
3823            matched within the group is recorded (in the internal
3824            registers data structure) under the register number.  */
3825         case start_memory:
3826           DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]);
3827
3828           /* Find out if this group can match the empty string.  */
3829           p1 = p;               /* To send to group_match_null_string_p.  */
3830           
3831           if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
3832             REG_MATCH_NULL_STRING_P (reg_info[*p]) 
3833               = group_match_null_string_p (&p1, pend, reg_info);
3834
3835           /* Save the position in the string where we were the last time
3836              we were at this open-group operator in case the group is
3837              operated upon by a repetition operator, e.g., with `(a*)*b'
3838              against `ab'; then we want to ignore where we are now in
3839              the string in case this attempt to match fails.  */
3840           old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3841                              ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
3842                              : regstart[*p];
3843           DEBUG_PRINT2 ("  old_regstart: %d\n", 
3844                          POINTER_TO_OFFSET (old_regstart[*p]));
3845
3846           regstart[*p] = d;
3847           DEBUG_PRINT2 ("  regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
3848
3849           IS_ACTIVE (reg_info[*p]) = 1;
3850           MATCHED_SOMETHING (reg_info[*p]) = 0;
3851           
3852           /* This is the new highest active register.  */
3853           highest_active_reg = *p;
3854           
3855           /* If nothing was active before, this is the new lowest active
3856              register.  */
3857           if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
3858             lowest_active_reg = *p;
3859
3860           /* Move past the register number and inner group count.  */
3861           p += 2;
3862           just_past_start_mem = p;
3863           break;
3864
3865
3866         /* The stop_memory opcode represents the end of a group.  Its
3867            arguments are the same as start_memory's: the register
3868            number, and the number of inner groups.  */
3869         case stop_memory:
3870           DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]);
3871              
3872           /* We need to save the string position the last time we were at
3873              this close-group operator in case the group is operated
3874              upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
3875              against `aba'; then we want to ignore where we are now in
3876              the string in case this attempt to match fails.  */
3877           old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
3878                            ? REG_UNSET (regend[*p]) ? d : regend[*p]
3879                            : regend[*p];
3880           DEBUG_PRINT2 ("      old_regend: %d\n", 
3881                          POINTER_TO_OFFSET (old_regend[*p]));
3882
3883           regend[*p] = d;
3884           DEBUG_PRINT2 ("      regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
3885
3886           /* This register isn't active anymore.  */
3887           IS_ACTIVE (reg_info[*p]) = 0;
3888           
3889           /* If this was the only register active, nothing is active
3890              anymore.  */
3891           if (lowest_active_reg == highest_active_reg)
3892             {
3893               lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3894               highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3895             }
3896           else
3897             { /* We must scan for the new highest active register, since
3898                  it isn't necessarily one less than now: consider
3899                  (a(b)c(d(e)f)g).  When group 3 ends, after the f), the
3900                  new highest active register is 1.  */
3901               unsigned char r = *p - 1;
3902               while (r > 0 && !IS_ACTIVE (reg_info[r]))
3903                 r--;
3904               
3905               /* If we end up at register zero, that means that we saved
3906                  the registers as the result of an `on_failure_jump', not
3907                  a `start_memory', and we jumped to past the innermost
3908                  `stop_memory'.  For example, in ((.)*) we save
3909                  registers 1 and 2 as a result of the *, but when we pop
3910                  back to the second ), we are at the stop_memory 1.
3911                  Thus, nothing is active.  */
3912               if (r == 0)
3913                 {
3914                   lowest_active_reg = NO_LOWEST_ACTIVE_REG;
3915                   highest_active_reg = NO_HIGHEST_ACTIVE_REG;
3916                 }
3917               else
3918                 highest_active_reg = r;
3919             }
3920           
3921           /* If just failed to match something this time around with a
3922              group that's operated on by a repetition operator, try to
3923              force exit from the ``loop'', and restore the register
3924              information for this group that we had before trying this
3925              last match.  */
3926           if ((!MATCHED_SOMETHING (reg_info[*p])
3927                || just_past_start_mem == p - 1)
3928               && (p + 2) < pend)              
3929             {
3930               boolean is_a_jump_n = false;
3931               
3932               p1 = p + 2;
3933               mcnt = 0;
3934               switch ((re_opcode_t) *p1++)
3935                 {
3936                   case jump_n:
3937                     is_a_jump_n = true;
3938                   case pop_failure_jump:
3939                   case maybe_pop_jump:
3940                   case jump:
3941                   case dummy_failure_jump:
3942                     EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3943                     if (is_a_jump_n)
3944                       p1 += 2;
3945                     break;
3946                   
3947                   default:
3948                     /* do nothing */ ;
3949                 }
3950               p1 += mcnt;
3951         
3952               /* If the next operation is a jump backwards in the pattern
3953                  to an on_failure_jump right before the start_memory
3954                  corresponding to this stop_memory, exit from the loop
3955                  by forcing a failure after pushing on the stack the
3956                  on_failure_jump's jump in the pattern, and d.  */
3957               if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
3958                   && (re_opcode_t) p1[3] == start_memory && p1[4] == *p)
3959                 {
3960                   /* If this group ever matched anything, then restore
3961                      what its registers were before trying this last
3962                      failed match, e.g., with `(a*)*b' against `ab' for
3963                      regstart[1], and, e.g., with `((a*)*(b*)*)*'
3964                      against `aba' for regend[3].
3965                      
3966                      Also restore the registers for inner groups for,
3967                      e.g., `((a*)(b*))*' against `aba' (register 3 would
3968                      otherwise get trashed).  */
3969                      
3970                   if (EVER_MATCHED_SOMETHING (reg_info[*p]))
3971                     {
3972                       unsigned r; 
3973         
3974                       EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
3975                       
3976                       /* Restore this and inner groups' (if any) registers.  */
3977                       for (r = *p; r < *p + *(p + 1); r++)
3978                         {
3979                           regstart[r] = old_regstart[r];
3980
3981                           /* xx why this test?  */
3982                           if (old_regend[r] >= regstart[r])
3983                             regend[r] = old_regend[r];
3984                         }     
3985                     }
3986                   p1++;
3987                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
3988                   PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
3989
3990                   goto fail;
3991                 }
3992             }
3993           
3994           /* Move past the register number and the inner group count.  */
3995           p += 2;
3996           break;
3997
3998
3999         /* \<digit> has been turned into a `duplicate' command which is
4000            followed by the numeric value of <digit> as the register number.  */
4001         case duplicate:
4002           {
4003             register const char *d2, *dend2;
4004             int regno = *p++;   /* Get which register to match against.  */
4005             DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
4006
4007             /* Can't back reference a group which we've never matched.  */
4008             if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
4009               goto fail;
4010               
4011             /* Where in input to try to start matching.  */
4012             d2 = regstart[regno];
4013             
4014             /* Where to stop matching; if both the place to start and
4015                the place to stop matching are in the same string, then
4016                set to the place to stop, otherwise, for now have to use
4017                the end of the first string.  */
4018
4019             dend2 = ((FIRST_STRING_P (regstart[regno]) 
4020                       == FIRST_STRING_P (regend[regno]))
4021                      ? regend[regno] : end_match_1);
4022             for (;;)
4023               {
4024                 /* If necessary, advance to next segment in register
4025                    contents.  */
4026                 while (d2 == dend2)
4027                   {
4028                     if (dend2 == end_match_2) break;
4029                     if (dend2 == regend[regno]) break;
4030
4031                     /* End of string1 => advance to string2. */
4032                     d2 = string2;
4033                     dend2 = regend[regno];
4034                   }
4035                 /* At end of register contents => success */
4036                 if (d2 == dend2) break;
4037
4038                 /* If necessary, advance to next segment in data.  */
4039                 PREFETCH ();
4040
4041                 /* How many characters left in this segment to match.  */
4042                 mcnt = dend - d;
4043                 
4044                 /* Want how many consecutive characters we can match in
4045                    one shot, so, if necessary, adjust the count.  */
4046                 if (mcnt > dend2 - d2)
4047                   mcnt = dend2 - d2;
4048                   
4049                 /* Compare that many; failure if mismatch, else move
4050                    past them.  */
4051                 if (translate 
4052                     ? bcmp_translate (d, d2, mcnt, translate) 
4053                     : bcmp (d, d2, mcnt))
4054                   goto fail;
4055                 d += mcnt, d2 += mcnt;
4056               }
4057           }
4058           break;
4059
4060
4061         /* begline matches the empty string at the beginning of the string
4062            (unless `not_bol' is set in `bufp'), and, if
4063            `newline_anchor' is set, after newlines.  */
4064         case begline:
4065           DEBUG_PRINT1 ("EXECUTING begline.\n");
4066           
4067           if (AT_STRINGS_BEG (d))
4068             {
4069               if (!bufp->not_bol) break;
4070             }
4071           else if (d[-1] == '\n' && bufp->newline_anchor)
4072             {
4073               break;
4074             }
4075           /* In all other cases, we fail.  */
4076           goto fail;
4077
4078
4079         /* endline is the dual of begline.  */
4080         case endline:
4081           DEBUG_PRINT1 ("EXECUTING endline.\n");
4082
4083           if (AT_STRINGS_END (d))
4084             {
4085               if (!bufp->not_eol) break;
4086             }
4087           
4088           /* We have to ``prefetch'' the next character.  */
4089           else if ((d == end1 ? *string2 : *d) == '\n'
4090                    && bufp->newline_anchor)
4091             {
4092               break;
4093             }
4094           goto fail;
4095
4096
4097         /* Match at the very beginning of the data.  */
4098         case begbuf:
4099           DEBUG_PRINT1 ("EXECUTING begbuf.\n");
4100           if (AT_STRINGS_BEG (d))
4101             break;
4102           goto fail;
4103
4104
4105         /* Match at the very end of the data.  */
4106         case endbuf:
4107           DEBUG_PRINT1 ("EXECUTING endbuf.\n");
4108           if (AT_STRINGS_END (d))
4109             break;
4110           goto fail;
4111
4112
4113         /* on_failure_keep_string_jump is used to optimize `.*\n'.  It
4114            pushes NULL as the value for the string on the stack.  Then
4115            `pop_failure_point' will keep the current value for the
4116            string, instead of restoring it.  To see why, consider
4117            matching `foo\nbar' against `.*\n'.  The .* matches the foo;
4118            then the . fails against the \n.  But the next thing we want
4119            to do is match the \n against the \n; if we restored the
4120            string value, we would be back at the foo.
4121            
4122            Because this is used only in specific cases, we don't need to
4123            check all the things that `on_failure_jump' does, to make
4124            sure the right things get saved on the stack.  Hence we don't
4125            share its code.  The only reason to push anything on the
4126            stack at all is that otherwise we would have to change
4127            `anychar's code to do something besides goto fail in this
4128            case; that seems worse than this.  */
4129         case on_failure_keep_string_jump:
4130           DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
4131           
4132           EXTRACT_NUMBER_AND_INCR (mcnt, p);
4133           DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
4134
4135           PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
4136           break;
4137
4138
4139         /* Uses of on_failure_jump:
4140         
4141            Each alternative starts with an on_failure_jump that points
4142            to the beginning of the next alternative.  Each alternative
4143            except the last ends with a jump that in effect jumps past
4144            the rest of the alternatives.  (They really jump to the
4145            ending jump of the following alternative, because tensioning
4146            these jumps is a hassle.)
4147
4148            Repeats start with an on_failure_jump that points past both
4149            the repetition text and either the following jump or
4150            pop_failure_jump back to this on_failure_jump.  */
4151         case on_failure_jump:
4152         on_failure:
4153           DEBUG_PRINT1 ("EXECUTING on_failure_jump");
4154
4155           EXTRACT_NUMBER_AND_INCR (mcnt, p);
4156           DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
4157
4158           /* If this on_failure_jump comes right before a group (i.e.,
4159              the original * applied to a group), save the information
4160              for that group and all inner ones, so that if we fail back
4161              to this point, the group's information will be correct.
4162              For example, in \(a*\)*\1, we need the preceding group,
4163              and in \(\(a*\)b*\)\2, we need the inner group.  */
4164
4165           /* We can't use `p' to check ahead because we push
4166              a failure point to `p + mcnt' after we do this.  */
4167           p1 = p;
4168
4169           /* We need to skip no_op's before we look for the
4170              start_memory in case this on_failure_jump is happening as
4171              the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
4172              against aba.  */
4173           while (p1 < pend && (re_opcode_t) *p1 == no_op)
4174             p1++;
4175
4176           if (p1 < pend && (re_opcode_t) *p1 == start_memory)
4177             {
4178               /* We have a new highest active register now.  This will
4179                  get reset at the start_memory we are about to get to,
4180                  but we will have saved all the registers relevant to
4181                  this repetition op, as described above.  */
4182               highest_active_reg = *(p1 + 1) + *(p1 + 2);
4183               if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
4184                 lowest_active_reg = *(p1 + 1);
4185             }
4186
4187           DEBUG_PRINT1 (":\n");
4188           PUSH_FAILURE_POINT (p + mcnt, d, -2);
4189           break;
4190
4191
4192         /* A smart repeat ends with `maybe_pop_jump'.
4193            We change it to either `pop_failure_jump' or `jump'.  */
4194         case maybe_pop_jump:
4195           EXTRACT_NUMBER_AND_INCR (mcnt, p);
4196           DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
4197           {
4198             register unsigned char *p2 = p;
4199
4200             /* Compare the beginning of the repeat with what in the
4201                pattern follows its end. If we can establish that there
4202                is nothing that they would both match, i.e., that we
4203                would have to backtrack because of (as in, e.g., `a*a')
4204                then we can change to pop_failure_jump, because we'll
4205                never have to backtrack.
4206                
4207                This is not true in the case of alternatives: in
4208                `(a|ab)*' we do need to backtrack to the `ab' alternative
4209                (e.g., if the string was `ab').  But instead of trying to
4210                detect that here, the alternative has put on a dummy
4211                failure point which is what we will end up popping.  */
4212
4213             /* Skip over open/close-group commands.
4214                If what follows this loop is a ...+ construct,
4215                look at what begins its body, since we will have to
4216                match at least one of that.  */
4217             while (1)
4218               {
4219                 if (p2 + 2 < pend
4220                     && ((re_opcode_t) *p2 == stop_memory
4221                         || (re_opcode_t) *p2 == start_memory))
4222                   p2 += 3;
4223                 else if (p2 + 6 < pend
4224                          && (re_opcode_t) *p2 == dummy_failure_jump)
4225                   p2 += 6;
4226                 else
4227                   break;
4228               }
4229
4230             p1 = p + mcnt;
4231             /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
4232                to the `maybe_finalize_jump' of this case.  Examine what 
4233                follows.  */
4234
4235             /* If we're at the end of the pattern, we can change.  */
4236             if (p2 == pend)
4237               {
4238                 /* Consider what happens when matching ":\(.*\)"
4239                    against ":/".  I don't really understand this code
4240                    yet.  */
4241                 p[-3] = (unsigned char) pop_failure_jump;
4242                 DEBUG_PRINT1
4243                   ("  End of pattern: change to `pop_failure_jump'.\n");
4244               }
4245
4246             else if ((re_opcode_t) *p2 == exactn
4247                      || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
4248               {
4249                 register unsigned char c
4250                   = *p2 == (unsigned char) endline ? '\n' : p2[2];
4251
4252                 if ((re_opcode_t) p1[3] == exactn && p1[5] != c)
4253                   {
4254                     p[-3] = (unsigned char) pop_failure_jump;
4255                     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
4256                                   c, p1[5]);
4257                   }
4258                   
4259                 else if ((re_opcode_t) p1[3] == charset
4260                          || (re_opcode_t) p1[3] == charset_not)
4261                   {
4262                     int not = (re_opcode_t) p1[3] == charset_not;
4263                     
4264                     if (c < (unsigned char) (p1[4] * BYTEWIDTH)
4265                         && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
4266                       not = !not;
4267
4268                     /* `not' is equal to 1 if c would match, which means
4269                         that we can't change to pop_failure_jump.  */
4270                     if (!not)
4271                       {
4272                         p[-3] = (unsigned char) pop_failure_jump;
4273                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
4274                       }
4275                   }
4276               }
4277             else if ((re_opcode_t) *p2 == charset)
4278               {
4279 #ifdef DEBUG
4280                 register unsigned char c
4281                   = *p2 == (unsigned char) endline ? '\n' : p2[2];
4282 #endif
4283
4284                 if ((re_opcode_t) p1[3] == exactn
4285                     && ! (p2[1] * BYTEWIDTH > p1[4]
4286                           && (p2[1 + p1[4] / BYTEWIDTH]
4287                               & (1 << (p1[4] % BYTEWIDTH)))))
4288                   {
4289                     p[-3] = (unsigned char) pop_failure_jump;
4290                     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
4291                                   c, p1[5]);
4292                   }
4293                   
4294                 else if ((re_opcode_t) p1[3] == charset_not)
4295                   {
4296                     int idx;
4297                     /* We win if the charset_not inside the loop
4298                        lists every character listed in the charset after.  */
4299                     for (idx = 0; idx < p2[1]; idx++)
4300                       if (! (p2[2 + idx] == 0
4301                              || (idx < p1[4]
4302                                  && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
4303                         break;
4304
4305                     if (idx == p2[1])
4306                       {
4307                         p[-3] = (unsigned char) pop_failure_jump;
4308                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
4309                       }
4310                   }
4311                 else if ((re_opcode_t) p1[3] == charset)
4312                   {
4313                     int idx;
4314                     /* We win if the charset inside the loop
4315                        has no overlap with the one after the loop.  */
4316                     for (idx = 0; idx < p2[1] && idx < p1[4]; idx++)
4317                       if ((p2[2 + idx] & p1[5 + idx]) != 0)
4318                         break;
4319
4320                     if (idx == p2[1] || idx == p1[4])
4321                       {
4322                         p[-3] = (unsigned char) pop_failure_jump;
4323                         DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
4324                       }
4325                   }
4326               }
4327           }
4328           p -= 2;               /* Point at relative address again.  */
4329           if ((re_opcode_t) p[-1] != pop_failure_jump)
4330             {
4331               p[-1] = (unsigned char) jump;
4332               DEBUG_PRINT1 ("  Match => jump.\n");
4333               goto unconditional_jump;
4334             }
4335         /* Note fall through.  */
4336
4337
4338         /* The end of a simple repeat has a pop_failure_jump back to
4339            its matching on_failure_jump, where the latter will push a
4340            failure point.  The pop_failure_jump takes off failure
4341            points put on by this pop_failure_jump's matching
4342            on_failure_jump; we got through the pattern to here from the
4343            matching on_failure_jump, so didn't fail.  */
4344         case pop_failure_jump:
4345           {
4346             /* We need to pass separate storage for the lowest and
4347                highest registers, even though we don't care about the
4348                actual values.  Otherwise, we will restore only one
4349                register from the stack, since lowest will == highest in
4350                `pop_failure_point'.  */
4351             unsigned long dummy_low_reg, dummy_high_reg;
4352             unsigned char *pdummy;
4353             const char *sdummy;
4354
4355             DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
4356             POP_FAILURE_POINT (sdummy, pdummy,
4357                                dummy_low_reg, dummy_high_reg,
4358                                reg_dummy, reg_dummy, reg_info_dummy);
4359           }
4360           /* Note fall through.  */
4361
4362           
4363         /* Unconditionally jump (without popping any failure points).  */
4364         case jump:
4365         unconditional_jump:
4366           EXTRACT_NUMBER_AND_INCR (mcnt, p);    /* Get the amount to jump.  */
4367           DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
4368           p += mcnt;                            /* Do the jump.  */
4369           DEBUG_PRINT2 ("(to 0x%x).\n", p);
4370           break;
4371
4372         
4373         /* We need this opcode so we can detect where alternatives end
4374            in `group_match_null_string_p' et al.  */
4375         case jump_past_alt:
4376           DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
4377           goto unconditional_jump;
4378
4379
4380         /* Normally, the on_failure_jump pushes a failure point, which
4381            then gets popped at pop_failure_jump.  We will end up at
4382            pop_failure_jump, also, and with a pattern of, say, `a+', we
4383            are skipping over the on_failure_jump, so we have to push
4384            something meaningless for pop_failure_jump to pop.  */
4385         case dummy_failure_jump:
4386           DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
4387           /* It doesn't matter what we push for the string here.  What
4388              the code at `fail' tests is the value for the pattern.  */
4389           PUSH_FAILURE_POINT (0, 0, -2);
4390           goto unconditional_jump;
4391
4392
4393         /* At the end of an alternative, we need to push a dummy failure
4394            point in case we are followed by a `pop_failure_jump', because
4395            we don't want the failure point for the alternative to be
4396            popped.  For example, matching `(a|ab)*' against `aab'
4397            requires that we match the `ab' alternative.  */
4398         case push_dummy_failure:
4399           DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
4400           /* See comments just above at `dummy_failure_jump' about the
4401              two zeroes.  */
4402           PUSH_FAILURE_POINT (0, 0, -2);
4403           break;
4404
4405         /* Have to succeed matching what follows at least n times.
4406            After that, handle like `on_failure_jump'.  */
4407         case succeed_n: 
4408           EXTRACT_NUMBER (mcnt, p + 2);
4409           DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
4410
4411           assert (mcnt >= 0);
4412           /* Originally, this is how many times we HAVE to succeed.  */
4413           if (mcnt > 0)
4414             {
4415                mcnt--;
4416                p += 2;
4417                STORE_NUMBER_AND_INCR (p, mcnt);
4418                DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p, mcnt);
4419             }
4420           else if (mcnt == 0)
4421             {
4422               DEBUG_PRINT2 ("  Setting two bytes from 0x%x to no_op.\n", p+2);
4423               p[2] = (unsigned char) no_op;
4424               p[3] = (unsigned char) no_op;
4425               goto on_failure;
4426             }
4427           break;
4428         
4429         case jump_n: 
4430           EXTRACT_NUMBER (mcnt, p + 2);
4431           DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
4432
4433           /* Originally, this is how many times we CAN jump.  */
4434           if (mcnt)
4435             {
4436                mcnt--;
4437                STORE_NUMBER (p + 2, mcnt);
4438                goto unconditional_jump;      
4439             }
4440           /* If don't have to jump any more, skip over the rest of command.  */
4441           else      
4442             p += 4;                  
4443           break;
4444         
4445         case set_number_at:
4446           {
4447             DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
4448
4449             EXTRACT_NUMBER_AND_INCR (mcnt, p);
4450             p1 = p + mcnt;
4451             EXTRACT_NUMBER_AND_INCR (mcnt, p);
4452             DEBUG_PRINT3 ("  Setting 0x%x to %d.\n", p1, mcnt);
4453             STORE_NUMBER (p1, mcnt);
4454             break;
4455           }
4456
4457         case wordbound:
4458           DEBUG_PRINT1 ("EXECUTING wordbound.\n");
4459           if (AT_WORD_BOUNDARY (d))
4460             break;
4461           goto fail;
4462
4463         case notwordbound:
4464           DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
4465           if (AT_WORD_BOUNDARY (d))
4466             goto fail;
4467           break;
4468
4469         case wordbeg:
4470           DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
4471           if (WORDCHAR_P (d) && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
4472             break;
4473           goto fail;
4474
4475         case wordend:
4476           DEBUG_PRINT1 ("EXECUTING wordend.\n");
4477           if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
4478               && (!WORDCHAR_P (d) || AT_STRINGS_END (d)))
4479             break;
4480           goto fail;
4481
4482 #ifdef emacs
4483         case before_dot:
4484           DEBUG_PRINT1 ("EXECUTING before_dot.\n");
4485           if (PTR_CHAR_POS ((unsigned char *) d) >= point)
4486             goto fail;
4487           break;
4488   
4489         case at_dot:
4490           DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4491           if (PTR_CHAR_POS ((unsigned char *) d) != point)
4492             goto fail;
4493           break;
4494   
4495         case after_dot:
4496           DEBUG_PRINT1 ("EXECUTING after_dot.\n");
4497           if (PTR_CHAR_POS ((unsigned char *) d) <= point)
4498             goto fail;
4499           break;
4500 #if 0 /* not emacs19 */
4501         case at_dot:
4502           DEBUG_PRINT1 ("EXECUTING at_dot.\n");
4503           if (PTR_CHAR_POS ((unsigned char *) d) + 1 != point)
4504             goto fail;
4505           break;
4506 #endif /* not emacs19 */
4507
4508         case syntaxspec:
4509           DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
4510           mcnt = *p++;
4511           goto matchsyntax;
4512
4513         case wordchar:
4514           DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
4515           mcnt = (int) Sword;
4516         matchsyntax:
4517           PREFETCH ();
4518           /* Can't use *d++ here; SYNTAX may be an unsafe macro.  */
4519           d++;
4520           if (SYNTAX (d[-1]) != (enum syntaxcode) mcnt)
4521             goto fail;
4522           SET_REGS_MATCHED ();
4523           break;
4524
4525         case notsyntaxspec:
4526           DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
4527           mcnt = *p++;
4528           goto matchnotsyntax;
4529
4530         case notwordchar:
4531           DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
4532           mcnt = (int) Sword;
4533         matchnotsyntax:
4534           PREFETCH ();
4535           /* Can't use *d++ here; SYNTAX may be an unsafe macro.  */
4536           d++;
4537           if (SYNTAX (d[-1]) == (enum syntaxcode) mcnt)
4538             goto fail;
4539           SET_REGS_MATCHED ();
4540           break;
4541
4542 #else /* not emacs */
4543         case wordchar:
4544           DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
4545           PREFETCH ();
4546           if (!WORDCHAR_P (d))
4547             goto fail;
4548           SET_REGS_MATCHED ();
4549           d++;
4550           break;
4551           
4552         case notwordchar:
4553           DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
4554           PREFETCH ();
4555           if (WORDCHAR_P (d))
4556             goto fail;
4557           SET_REGS_MATCHED ();
4558           d++;
4559           break;
4560 #endif /* not emacs */
4561           
4562         default:
4563           abort ();
4564         }
4565       continue;  /* Successfully executed one pattern command; keep going.  */
4566
4567
4568     /* We goto here if a matching operation fails. */
4569     fail:
4570       if (!FAIL_STACK_EMPTY ())
4571         { /* A restart point is known.  Restore to that state.  */
4572           DEBUG_PRINT1 ("\nFAIL:\n");
4573           POP_FAILURE_POINT (d, p,
4574                              lowest_active_reg, highest_active_reg,
4575                              regstart, regend, reg_info);
4576
4577           /* If this failure point is a dummy, try the next one.  */
4578           if (!p)
4579             goto fail;
4580
4581           /* If we failed to the end of the pattern, don't examine *p.  */
4582           assert (p <= pend);
4583           if (p < pend)
4584             {
4585               boolean is_a_jump_n = false;
4586               
4587               /* If failed to a backwards jump that's part of a repetition
4588                  loop, need to pop this failure point and use the next one.  */
4589               switch ((re_opcode_t) *p)
4590                 {
4591                 case jump_n:
4592                   is_a_jump_n = true;
4593                 case maybe_pop_jump:
4594                 case pop_failure_jump:
4595                 case jump:
4596                   p1 = p + 1;
4597                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4598                   p1 += mcnt;   
4599
4600                   if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
4601                       || (!is_a_jump_n
4602                           && (re_opcode_t) *p1 == on_failure_jump))
4603                     goto fail;
4604                   break;
4605                 default:
4606                   /* do nothing */ ;
4607                 }
4608             }
4609
4610           if (d >= string1 && d <= end1)
4611             dend = end_match_1;
4612         }
4613       else
4614         break;   /* Matching at this starting point really fails.  */
4615     } /* for (;;) */
4616
4617   if (best_regs_set)
4618     goto restore_best_regs;
4619
4620   FREE_VARIABLES ();
4621
4622   return -1;                            /* Failure to match.  */
4623 } /* re_match_2 */
4624 \f
4625 /* Subroutine definitions for re_match_2.  */
4626
4627
4628 /* We are passed P pointing to a register number after a start_memory.
4629    
4630    Return true if the pattern up to the corresponding stop_memory can
4631    match the empty string, and false otherwise.
4632    
4633    If we find the matching stop_memory, sets P to point to one past its number.
4634    Otherwise, sets P to an undefined byte less than or equal to END.
4635
4636    We don't handle duplicates properly (yet).  */
4637
4638 static boolean
4639 group_match_null_string_p (p, end, reg_info)
4640     unsigned char **p, *end;
4641     register_info_type *reg_info;
4642 {
4643   int mcnt;
4644   /* Point to after the args to the start_memory.  */
4645   unsigned char *p1 = *p + 2;
4646   
4647   while (p1 < end)
4648     {
4649       /* Skip over opcodes that can match nothing, and return true or
4650          false, as appropriate, when we get to one that can't, or to the
4651          matching stop_memory.  */
4652       
4653       switch ((re_opcode_t) *p1)
4654         {
4655         /* Could be either a loop or a series of alternatives.  */
4656         case on_failure_jump:
4657           p1++;
4658           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4659           
4660           /* If the next operation is not a jump backwards in the
4661              pattern.  */
4662
4663           if (mcnt >= 0)
4664             {
4665               /* Go through the on_failure_jumps of the alternatives,
4666                  seeing if any of the alternatives cannot match nothing.
4667                  The last alternative starts with only a jump,
4668                  whereas the rest start with on_failure_jump and end
4669                  with a jump, e.g., here is the pattern for `a|b|c':
4670
4671                  /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
4672                  /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
4673                  /exactn/1/c                                            
4674
4675                  So, we have to first go through the first (n-1)
4676                  alternatives and then deal with the last one separately.  */
4677
4678
4679               /* Deal with the first (n-1) alternatives, which start
4680                  with an on_failure_jump (see above) that jumps to right
4681                  past a jump_past_alt.  */
4682
4683               while ((re_opcode_t) p1[mcnt-3] == jump_past_alt)
4684                 {
4685                   /* `mcnt' holds how many bytes long the alternative
4686                      is, including the ending `jump_past_alt' and
4687                      its number.  */
4688
4689                   if (!alt_match_null_string_p (p1, p1 + mcnt - 3, 
4690                                                       reg_info))
4691                     return false;
4692
4693                   /* Move to right after this alternative, including the
4694                      jump_past_alt.  */
4695                   p1 += mcnt;   
4696
4697                   /* Break if it's the beginning of an n-th alternative
4698                      that doesn't begin with an on_failure_jump.  */
4699                   if ((re_opcode_t) *p1 != on_failure_jump)
4700                     break;
4701                 
4702                   /* Still have to check that it's not an n-th
4703                      alternative that starts with an on_failure_jump.  */
4704                   p1++;
4705                   EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4706                   if ((re_opcode_t) p1[mcnt-3] != jump_past_alt)
4707                     {
4708                       /* Get to the beginning of the n-th alternative.  */
4709                       p1 -= 3;
4710                       break;
4711                     }
4712                 }
4713
4714               /* Deal with the last alternative: go back and get number
4715                  of the `jump_past_alt' just before it.  `mcnt' contains
4716                  the length of the alternative.  */
4717               EXTRACT_NUMBER (mcnt, p1 - 2);
4718
4719               if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info))
4720                 return false;
4721
4722               p1 += mcnt;       /* Get past the n-th alternative.  */
4723             } /* if mcnt > 0 */
4724           break;
4725
4726           
4727         case stop_memory:
4728           assert (p1[1] == **p);
4729           *p = p1 + 2;
4730           return true;
4731
4732         
4733         default: 
4734           if (!common_op_match_null_string_p (&p1, end, reg_info))
4735             return false;
4736         }
4737     } /* while p1 < end */
4738
4739   return false;
4740 } /* group_match_null_string_p */
4741
4742
4743 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
4744    It expects P to be the first byte of a single alternative and END one
4745    byte past the last. The alternative can contain groups.  */
4746    
4747 static boolean
4748 alt_match_null_string_p (p, end, reg_info)
4749     unsigned char *p, *end;
4750     register_info_type *reg_info;
4751 {
4752   int mcnt;
4753   unsigned char *p1 = p;
4754   
4755   while (p1 < end)
4756     {
4757       /* Skip over opcodes that can match nothing, and break when we get 
4758          to one that can't.  */
4759       
4760       switch ((re_opcode_t) *p1)
4761         {
4762         /* It's a loop.  */
4763         case on_failure_jump:
4764           p1++;
4765           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4766           p1 += mcnt;
4767           break;
4768           
4769         default: 
4770           if (!common_op_match_null_string_p (&p1, end, reg_info))
4771             return false;
4772         }
4773     }  /* while p1 < end */
4774
4775   return true;
4776 } /* alt_match_null_string_p */
4777
4778
4779 /* Deals with the ops common to group_match_null_string_p and
4780    alt_match_null_string_p.  
4781    
4782    Sets P to one after the op and its arguments, if any.  */
4783
4784 static boolean
4785 common_op_match_null_string_p (p, end, reg_info)
4786     unsigned char **p, *end;
4787     register_info_type *reg_info;
4788 {
4789   int mcnt;
4790   boolean ret;
4791   int reg_no;
4792   unsigned char *p1 = *p;
4793
4794   switch ((re_opcode_t) *p1++)
4795     {
4796     case no_op:
4797     case begline:
4798     case endline:
4799     case begbuf:
4800     case endbuf:
4801     case wordbeg:
4802     case wordend:
4803     case wordbound:
4804     case notwordbound:
4805 #ifdef emacs
4806     case before_dot:
4807     case at_dot:
4808     case after_dot:
4809 #endif
4810       break;
4811
4812     case start_memory:
4813       reg_no = *p1;
4814       assert (reg_no > 0 && reg_no <= MAX_REGNUM);
4815       ret = group_match_null_string_p (&p1, end, reg_info);
4816       
4817       /* Have to set this here in case we're checking a group which
4818          contains a group and a back reference to it.  */
4819
4820       if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
4821         REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
4822
4823       if (!ret)
4824         return false;
4825       break;
4826           
4827     /* If this is an optimized succeed_n for zero times, make the jump.  */
4828     case jump:
4829       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4830       if (mcnt >= 0)
4831         p1 += mcnt;
4832       else
4833         return false;
4834       break;
4835
4836     case succeed_n:
4837       /* Get to the number of times to succeed.  */
4838       p1 += 2;          
4839       EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4840
4841       if (mcnt == 0)
4842         {
4843           p1 -= 4;
4844           EXTRACT_NUMBER_AND_INCR (mcnt, p1);
4845           p1 += mcnt;
4846         }
4847       else
4848         return false;
4849       break;
4850
4851     case duplicate: 
4852       if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
4853         return false;
4854       break;
4855
4856     case set_number_at:
4857       p1 += 4;
4858
4859     default:
4860       /* All other opcodes mean we cannot match the empty string.  */
4861       return false;
4862   }
4863
4864   *p = p1;
4865   return true;
4866 } /* common_op_match_null_string_p */
4867
4868
4869 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
4870    bytes; nonzero otherwise.  */
4871    
4872 static int
4873 bcmp_translate (s1, s2, len, translate)
4874      unsigned char *s1, *s2;
4875      register int len;
4876      char *translate;
4877 {
4878   register unsigned char *p1 = s1, *p2 = s2;
4879   while (len)
4880     {
4881       if (translate[*p1++] != translate[*p2++]) return 1;
4882       len--;
4883     }
4884   return 0;
4885 }
4886 \f
4887 /* Entry points for GNU code.  */
4888
4889 /* re_compile_pattern is the GNU regular expression compiler: it
4890    compiles PATTERN (of length SIZE) and puts the result in BUFP.
4891    Returns 0 if the pattern was valid, otherwise an error string.
4892    
4893    Assumes the `allocated' (and perhaps `buffer') and `translate' fields
4894    are set in BUFP on entry.
4895    
4896    We call regex_compile to do the actual compilation.  */
4897
4898 const char *
4899 re_compile_pattern (pattern, length, bufp)
4900      const char *pattern;
4901      int length;
4902      struct re_pattern_buffer *bufp;
4903 {
4904   reg_errcode_t ret;
4905   
4906   /* GNU code is written to assume at least RE_NREGS registers will be set
4907      (and at least one extra will be -1).  */
4908   bufp->regs_allocated = REGS_UNALLOCATED;
4909   
4910   /* And GNU code determines whether or not to get register information
4911      by passing null for the REGS argument to re_match, etc., not by
4912      setting no_sub.  */
4913   bufp->no_sub = 0;
4914   
4915   /* Match anchors at newline.  */
4916   bufp->newline_anchor = 1;
4917   
4918   ret = regex_compile (pattern, length, re_syntax_options, bufp);
4919
4920   return re_error_msg[(int) ret];
4921 }     
4922 \f
4923 /* Entry points compatible with 4.2 BSD regex library.  We don't define
4924    them if this is an Emacs or POSIX compilation.  */
4925
4926 #if !defined (emacs) && !defined (_POSIX_SOURCE)
4927
4928 /* BSD has one and only one pattern buffer.  */
4929 static struct re_pattern_buffer re_comp_buf;
4930
4931 char *
4932 re_comp (s)
4933     const char *s;
4934 {
4935   reg_errcode_t ret;
4936   
4937   if (!s)
4938     {
4939       if (!re_comp_buf.buffer)
4940         return "No previous regular expression";
4941       return 0;
4942     }
4943
4944   if (!re_comp_buf.buffer)
4945     {
4946       re_comp_buf.buffer = (unsigned char *) malloc (200);
4947       if (re_comp_buf.buffer == NULL)
4948         return "Memory exhausted";
4949       re_comp_buf.allocated = 200;
4950
4951       re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
4952       if (re_comp_buf.fastmap == NULL)
4953         return "Memory exhausted";
4954     }
4955
4956   /* Since `re_exec' always passes NULL for the `regs' argument, we
4957      don't need to initialize the pattern buffer fields which affect it.  */
4958
4959   /* Match anchors at newlines.  */
4960   re_comp_buf.newline_anchor = 1;
4961
4962   ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
4963   
4964   /* Yes, we're discarding `const' here.  */
4965   return (char *) re_error_msg[(int) ret];
4966 }
4967
4968
4969 int
4970 re_exec (s)
4971     const char *s;
4972 {
4973   const int len = strlen (s);
4974   return
4975     0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
4976 }
4977 #endif /* not emacs and not _POSIX_SOURCE */
4978 \f
4979 /* POSIX.2 functions.  Don't define these for Emacs.  */
4980
4981 #ifndef emacs
4982
4983 /* regcomp takes a regular expression as a string and compiles it.
4984
4985    PREG is a regex_t *.  We do not expect any fields to be initialized,
4986    since POSIX says we shouldn't.  Thus, we set
4987
4988      `buffer' to the compiled pattern;
4989      `used' to the length of the compiled pattern;
4990      `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
4991        REG_EXTENDED bit in CFLAGS is set; otherwise, to
4992        RE_SYNTAX_POSIX_BASIC;
4993      `newline_anchor' to REG_NEWLINE being set in CFLAGS;
4994      `fastmap' and `fastmap_accurate' to zero;
4995      `re_nsub' to the number of subexpressions in PATTERN.
4996
4997    PATTERN is the address of the pattern string.
4998
4999    CFLAGS is a series of bits which affect compilation.
5000
5001      If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
5002      use POSIX basic syntax.
5003
5004      If REG_NEWLINE is set, then . and [^...] don't match newline.
5005      Also, regexec will try a match beginning after every newline.
5006
5007      If REG_ICASE is set, then we considers upper- and lowercase
5008      versions of letters to be equivalent when matching.
5009
5010      If REG_NOSUB is set, then when PREG is passed to regexec, that
5011      routine will report only success or failure, and nothing about the
5012      registers.
5013
5014    It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for
5015    the return codes and their meanings.)  */
5016
5017 int
5018 regcomp (preg, pattern, cflags)
5019     regex_t *preg;
5020     const char *pattern; 
5021     int cflags;
5022 {
5023   reg_errcode_t ret;
5024   unsigned syntax
5025     = (cflags & REG_EXTENDED) ?
5026       RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
5027
5028   /* regex_compile will allocate the space for the compiled pattern.  */
5029   preg->buffer = 0;
5030   preg->allocated = 0;
5031   preg->used = 0;
5032   
5033   /* Don't bother to use a fastmap when searching.  This simplifies the
5034      REG_NEWLINE case: if we used a fastmap, we'd have to put all the
5035      characters after newlines into the fastmap.  This way, we just try
5036      every character.  */
5037   preg->fastmap = 0;
5038   
5039   if (cflags & REG_ICASE)
5040     {
5041       unsigned i;
5042       
5043       preg->translate = (char *) malloc (CHAR_SET_SIZE);
5044       if (preg->translate == NULL)
5045         return (int) REG_ESPACE;
5046
5047       /* Map uppercase characters to corresponding lowercase ones.  */
5048       for (i = 0; i < CHAR_SET_SIZE; i++)
5049         preg->translate[i] = ISUPPER (i) ? tolower (i) : i;
5050     }
5051   else
5052     preg->translate = NULL;
5053
5054   /* If REG_NEWLINE is set, newlines are treated differently.  */
5055   if (cflags & REG_NEWLINE)
5056     { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
5057       syntax &= ~RE_DOT_NEWLINE;
5058       syntax |= RE_HAT_LISTS_NOT_NEWLINE;
5059       /* It also changes the matching behavior.  */
5060       preg->newline_anchor = 1;
5061     }
5062   else
5063     preg->newline_anchor = 0;
5064
5065   preg->no_sub = !!(cflags & REG_NOSUB);
5066
5067   /* POSIX says a null character in the pattern terminates it, so we 
5068      can use strlen here in compiling the pattern.  */
5069   ret = regex_compile (pattern, strlen (pattern), syntax, preg);
5070   
5071   /* POSIX doesn't distinguish between an unmatched open-group and an
5072      unmatched close-group: both are REG_EPAREN.  */
5073   if (ret == REG_ERPAREN) ret = REG_EPAREN;
5074   
5075   return (int) ret;
5076 }
5077
5078
5079 /* regexec searches for a given pattern, specified by PREG, in the
5080    string STRING.
5081    
5082    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
5083    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
5084    least NMATCH elements, and we set them to the offsets of the
5085    corresponding matched substrings.
5086    
5087    EFLAGS specifies `execution flags' which affect matching: if
5088    REG_NOTBOL is set, then ^ does not match at the beginning of the
5089    string; if REG_NOTEOL is set, then $ does not match at the end.
5090    
5091    We return 0 if we find a match and REG_NOMATCH if not.  */
5092
5093 int
5094 regexec (preg, string, nmatch, pmatch, eflags)
5095     const regex_t *preg;
5096     const char *string; 
5097     size_t nmatch; 
5098     regmatch_t pmatch[]; 
5099     int eflags;
5100 {
5101   int ret;
5102   struct re_registers regs;
5103   regex_t private_preg;
5104   int len = strlen (string);
5105   boolean want_reg_info = !preg->no_sub && nmatch > 0;
5106
5107   private_preg = *preg;
5108   
5109   private_preg.not_bol = !!(eflags & REG_NOTBOL);
5110   private_preg.not_eol = !!(eflags & REG_NOTEOL);
5111   
5112   /* The user has told us exactly how many registers to return
5113      information about, via `nmatch'.  We have to pass that on to the
5114      matching routines.  */
5115   private_preg.regs_allocated = REGS_FIXED;
5116   
5117   if (want_reg_info)
5118     {
5119       regs.num_regs = nmatch;
5120       regs.start = TALLOC (nmatch, regoff_t);
5121       regs.end = TALLOC (nmatch, regoff_t);
5122       if (regs.start == NULL || regs.end == NULL)
5123         return (int) REG_NOMATCH;
5124     }
5125
5126   /* Perform the searching operation.  */
5127   ret = re_search (&private_preg, string, len,
5128                    /* start: */ 0, /* range: */ len,
5129                    want_reg_info ? &regs : (struct re_registers *) 0);
5130   
5131   /* Copy the register information to the POSIX structure.  */
5132   if (want_reg_info)
5133     {
5134       if (ret >= 0)
5135         {
5136           unsigned r;
5137
5138           for (r = 0; r < nmatch; r++)
5139             {
5140               pmatch[r].rm_so = regs.start[r];
5141               pmatch[r].rm_eo = regs.end[r];
5142             }
5143         }
5144
5145       /* If we needed the temporary register info, free the space now.  */
5146       free (regs.start);
5147       free (regs.end);
5148     }
5149
5150   /* We want zero return to mean success, unlike `re_search'.  */
5151   return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
5152 }
5153
5154
5155 /* Returns a message corresponding to an error code, ERRCODE, returned
5156    from either regcomp or regexec.   We don't use PREG here.  */
5157
5158 size_t
5159 regerror (errcode, preg, errbuf, errbuf_size)
5160     int errcode;
5161     const regex_t *preg;
5162     char *errbuf;
5163     size_t errbuf_size;
5164 {
5165   const char *msg;
5166   size_t msg_size;
5167
5168   if (errcode < 0
5169       || errcode >= (sizeof (re_error_msg) / sizeof (re_error_msg[0])))
5170     /* Only error codes returned by the rest of the code should be passed 
5171        to this routine.  If we are given anything else, or if other regex
5172        code generates an invalid error code, then the program has a bug.
5173        Dump core so we can fix it.  */
5174     abort ();
5175
5176   msg = re_error_msg[errcode];
5177
5178   /* POSIX doesn't require that we do anything in this case, but why
5179      not be nice.  */
5180   if (! msg)
5181     msg = "Success";
5182
5183   msg_size = strlen (msg) + 1; /* Includes the null.  */
5184   
5185   if (errbuf_size != 0)
5186     {
5187       if (msg_size > errbuf_size)
5188         {
5189           strncpy (errbuf, msg, errbuf_size - 1);
5190           errbuf[errbuf_size - 1] = 0;
5191         }
5192       else
5193         strcpy (errbuf, msg);
5194     }
5195
5196   return msg_size;
5197 }
5198
5199
5200 /* Free dynamically allocated space used by PREG.  */
5201
5202 void
5203 regfree (preg)
5204     regex_t *preg;
5205 {
5206   if (preg->buffer != NULL)
5207     free (preg->buffer);
5208   preg->buffer = NULL;
5209   
5210   preg->allocated = 0;
5211   preg->used = 0;
5212
5213   if (preg->fastmap != NULL)
5214     free (preg->fastmap);
5215   preg->fastmap = NULL;
5216   preg->fastmap_accurate = 0;
5217
5218   if (preg->translate != NULL)
5219     free (preg->translate);
5220   preg->translate = NULL;
5221 }
5222
5223 #endif /* not emacs  */
5224 \f
5225 /*
5226 Local variables:
5227 make-backup-files: t
5228 version-control: t
5229 trim-versions-without-asking: nil
5230 End:
5231 */