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