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