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