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