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