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