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