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