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