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