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