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