Nico Golde:
[apps/madmutt.git] / regex.c
1 /* Extended regular expression matching and search library,
2  * version 0.12.
3  * (Implements POSIX draft P1003.2/D11.2, except for some of the
4  * internationalization features.)
5  * 
6  * Copyright (C) 1993, 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
7  * 
8  * This file is part of the GNU C Library.  Its master source is NOT part of
9  * the C library, however.  The master source lives in /gd/gnu/lib.
10  * 
11  * The GNU C Library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Library General Public License as
13  * published by the Free Software Foundation; either version 2 of the
14  * License, or (at your option) any later version.
15  * 
16  * The GNU C Library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19  * Library General Public License for more details.
20  * 
21  * You should have received a copy of the GNU Library General Public
22  * License along with the GNU C Library; see the file COPYING.LIB.  If not,
23  * write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24  * Boston, MA 02111-1307, USA.  
25  */
26
27 /*
28  * Modifications:
29  * 
30  * Use _regex.h instead of regex.h.  tlr, 1999-01-06
31  * Make REGEX_MALLOC depend on HAVE_ALLOCA &c.
32  *                                      tlr, 1999-02-14
33  * Don't switch on regex debugging when debugging mutt.
34  *                                      tlr, 1999-02-25
35  */
36
37 /* The following doesn't mix too well with autoconfiguring
38  * the use of alloca.  So let's disable it for AIX.
39  */
40
41 #if 0
42
43 /* AIX requires this to be the first thing in the file. */
44 # if defined (_AIX) && !defined (REGEX_MALLOC)
45 #  pragma alloca
46 # endif
47
48 #endif
49
50 #undef        _GNU_SOURCE
51 #define _GNU_SOURCE
52
53 #if HAVE_CONFIG_H
54 # include <config.h>
55 #endif
56
57 #undef DEBUG
58
59 #if (defined(HAVE_ALLOCA_H) && !defined(_AIX))
60 # include <alloca.h>
61 #endif
62
63 #if (!defined(HAVE_ALLOCA) || defined(_AIX))
64 # define REGEX_MALLOC
65 #endif
66
67 #if defined(STDC_HEADERS) && !defined(emacs)
68 #include <stddef.h>
69 #else
70 /* We need this for `regex.h', and perhaps for the Emacs include files.  */
71 #include <sys/types.h>
72 #endif
73
74 /* For platform which support the ISO C amendement 1 functionality we
75    support user defined character classes.  */
76 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
77 # include <wctype.h>
78 # include <wchar.h>
79 #endif
80
81 /* This is for other GNU distributions with internationalized messages.  */
82 #if HAVE_LIBINTL_H || defined (_LIBC)
83 # include <libintl.h>
84 #else
85 # define gettext(msgid) (msgid)
86 #endif
87
88 #ifndef gettext_noop
89 /* This define is so xgettext can find the internationalizable
90    strings.  */
91 #define gettext_noop(String) String
92 #endif
93
94 /* The `emacs' switch turns on certain matching commands
95    that make sense only in Emacs. */
96 #ifdef emacs
97
98 #include "lisp.h"
99 #include "buffer.h"
100 #include "syntax.h"
101 #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 == mutt_strcmp (name, "alnum"))
181     return MUTT_ALNUM;
182   if (0 == mutt_strcmp (name, "alpha"))
183     return MUTT_ALPHA;
184   if (0 == mutt_strcmp (name, "blank"))
185     return MUTT_BLANK;
186   if (0 == mutt_strcmp (name, "cntrl"))
187     return MUTT_CNTRL;
188   if (0 == mutt_strcmp (name, "digit"))
189     return MUTT_DIGIT;
190   if (0 == mutt_strcmp (name, "graph"))
191     return MUTT_GRAPH;
192   if (0 == mutt_strcmp (name, "lower"))
193     return MUTT_LOWER;
194   if (0 == mutt_strcmp (name, "print"))
195     return MUTT_PRINT;
196   if (0 == mutt_strcmp (name, "punct"))
197     return MUTT_PUNCT;
198   if (0 == mutt_strcmp (name, "space"))
199     return MUTT_SPACE;
200   if (0 == mutt_strcmp (name, "upper"))
201     return MUTT_UPPER;
202   if (0 == mutt_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_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_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_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_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_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) ((mutt_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_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 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       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           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               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           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             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               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             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               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               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               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                 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                 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                 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                 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         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             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             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               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               FREE_STACK_RETURN (REG_BADBR);
2581           }
2582
2583           if (!(syntax & RE_NO_BK_BRACES)) {
2584             if (c != '\\')
2585               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               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               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           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     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))