Edinburgh Speech Tools 2.4-release
 
Loading...
Searching...
No Matches
regexp.cc
1/*
2 * regcomp and regexec -- regsub and regerror are elsewhere
3 *
4 * Copyright (c) 1986 by University of Toronto.
5 * Written by Henry Spencer. Not derived from licensed software.
6 *
7 * Permission is granted to anyone to use this software for any
8 * purpose on any computer system, and to redistribute it freely,
9 * subject to the following restrictions:
10 *
11 * 1. The author is not responsible for the consequences of use of
12 * this software, no matter how awful, even if they arise
13 * from defects in it.
14 *
15 * 2. The origin of this software must not be misrepresented, either
16 * by explicit claim or by omission.
17 *
18 * 3. Altered versions must be plainly marked as such, and must not
19 * be misrepresented as being the original software.
20 *** THIS IS AN ALTERED VERSION. It was altered by John Gilmore,
21 *** hoptoad!gnu, on 27 Dec 1986, to add \n as an alternative to |
22 *** to assist in implementing egrep.
23 *** THIS IS AN ALTERED VERSION. It was altered by John Gilmore,
24 *** hoptoad!gnu, on 27 Dec 1986, to add < and > for word-matching
25 *** as in BSD grep and ex.
26 *** THIS IS AN ALTERED VERSION. It was altered by John Gilmore,
27 *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.
28 *** THIS IS AN ALTERED VERSION. It was altered by James A. Woods,
29 *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.
30 *
31 * Beware that some of this code is subtly aware of the way operator
32 * precedence is structured in regular expressions. Serious changes in
33 * regular-expression syntax might require a total rethink.
34 */
35#include <cstdio>
36#include <cctype>
37#include <cstdlib>
38#include <cstring>
39#include "regexp.h"
40#include "regmagic.h"
41
42/*
43 * The "internal use only" fields in regexp.h are present to pass info from
44 * compile to execute that permits the execute phase to run lots faster on
45 * simple cases. They are:
46 *
47 * regstart char that must begin a match; '\0' if none obvious
48 * reganch is the match anchored (at beginning-of-line only)?
49 * regmust string (pointer into program) that match must include, or NULL
50 * regmlen length of regmust string
51 *
52 * Regstart and reganch permit very fast decisions on suitable starting points
53 * for a match, cutting down the work a lot. Regmust permits fast rejection
54 * of lines that cannot possibly match. The regmust tests are costly enough
55 * that regcomp() supplies a regmust only if the r.e. contains something
56 * potentially expensive (at present, the only such thing detected is * or +
57 * at the start of the r.e., which can involve a lot of backup). Regmlen is
58 * supplied because the test in regexec() needs it and regcomp() is computing
59 * it anyway.
60 */
61
62/*
63 * Structure for regexp "program". This is essentially a linear encoding
64 * of a nondeterministic finite-state machine (aka syntax charts or
65 * "railroad normal form" in parsing technology). Each node is an opcode
66 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
67 * all nodes except BRANCH implement concatenation; a "next" pointer with
68 * a BRANCH on both ends of it is connecting two alternatives. (Here we
69 * have one of the subtle syntax dependencies: an individual BRANCH (as
70 * opposed to a collection of them) is never concatenated with anything
71 * because of operator precedence.) The operand of some types of node is
72 * a literal string; for others, it is a node leading into a sub-FSM. In
73 * particular, the operand of a BRANCH node is the first node of the branch.
74 * (NB this is *not* a tree structure: the tail of the branch connects
75 * to the thing following the set of BRANCHes.) The opcodes are:
76 */
77
78/* definition number opnd? meaning */
79#define END 0 /* no End of program. */
80#define BOL 1 /* no Match "" at beginning of line. */
81#define EOL 2 /* no Match "" at end of line. */
82#define ANY 3 /* no Match any one character. */
83#define ANYOF 4 /* str Match any character in this string. */
84#define ANYBUT 5 /* str Match any character not in this string. */
85#define BRANCH 6 /* node Match this alternative, or the next... */
86#define BACK 7 /* no Match "", "next" ptr points backward. */
87#define EXACTLY 8 /* str Match this string. */
88#define NOTHING 9 /* no Match empty string. */
89#define STAR 10 /* node Match this (simple) thing 0 or more times. */
90#define PLUS 11 /* node Match this (simple) thing 1 or more times. */
91#define WORDA 12 /* no Match "" at wordchar, where prev is nonword */
92#define WORDZ 13 /* no Match "" at nonwordchar, where prev is word */
93#define OPEN 20 /* no Mark this point in input as start of #n. */
94 /* OPEN+1 is number 1, etc. */
95#define CLOSE 30 /* no Analogous to OPEN. */
96
97/*
98 * Opcode notes:
99 *
100 * BRANCH The set of branches constituting a single choice are hooked
101 * together with their "next" pointers, since precedence prevents
102 * anything being concatenated to any individual branch. The
103 * "next" pointer of the last BRANCH in a choice points to the
104 * thing following the whole choice. This is also where the
105 * final "next" pointer of each individual branch points; each
106 * branch starts with the operand node of a BRANCH node.
107 *
108 * BACK Normal "next" pointers all implicitly point forward; BACK
109 * exists to make loop structures possible.
110 *
111 * STAR,PLUS '?', and complex '*' and '+', are implemented as circular
112 * BRANCH structures using BACK. Simple cases (one character
113 * per match) are implemented with STAR and PLUS for speed
114 * and to minimize recursive plunges.
115 *
116 * OPEN,CLOSE ...are numbered at compile time.
117 */
118
119/*
120 * A node is one char of opcode followed by two chars of "next" pointer.
121 * "Next" pointers are stored as two 8-bit pieces, high order first. The
122 * value is a positive offset from the opcode of the node containing it.
123 * An operand, if any, simply follows the node. (Note that much of the
124 * code generation knows about this implicit relationship.)
125 *
126 * Using two bytes for the "next" pointer is vast overkill for most things,
127 * but allows patterns to get big without disasters.
128 */
129#define OP(p) (*(p))
130#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
131#define OPERAND(p) ((p) + 3)
132
133/*
134 * See regmagic.h for one further detail of program structure.
135 */
136
137
138/*
139 * Utility definitions.
140 */
141#ifndef CHARBITS
142#define UCHARAT(p) ((int)*(unsigned char *)(p))
143#else
144#define UCHARAT(p) ((int)*(p)&CHARBITS)
145#endif
146
147#define FAIL(m) { hs_regerror(m); return(NULL); }
148#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
149
150/*
151 * Flags to be passed up and down.
152 */
153#define HASWIDTH 01 /* Known never to match null string. */
154#define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
155#define SPSTART 04 /* Starts with * or +. */
156#define WORST 0 /* Worst case. */
157
158/*
159 * Global work variables for regcomp().
160 */
161static const char *regparse; /* Input-scan pointer. */
162static int regnpar; /* () count. */
163static char regdummy;
164static char *regcode; /* Code-emit pointer; &regdummy = don't. */
165static long regsize; /* Code size. */
166
167/*
168 * Forward declarations for regcomp()'s friends.
169 */
170#ifndef STATIC
171#define STATIC static
172#endif
173STATIC char *reg(int paren, int *flagp);
174STATIC char *regbranch(int *flagp);
175STATIC char *regpiece(int *flagp);
176STATIC char *regatom(int *flagp);
177STATIC char *regnode(char op);
178STATIC char *regnext(register char *p);
179STATIC void regc(char b);
180STATIC void reginsert(char op, char *opnd);
181STATIC void regtail(char *p, char *val);
182STATIC void regoptail(char *p, char *val);
183#ifdef STRCSPN
184STATIC int strcspn();
185#endif
186
187/*
188 - regcomp - compile a regular expression into internal code
189 *
190 * We can't allocate space until we know how big the compiled form will be,
191 * but we can't compile it (and thus know how big it is) until we've got a
192 * place to put the code. So we cheat: we compile it twice, once with code
193 * generation turned off and size counting turned on, and once "for real".
194 * This also means that we don't allocate space until we are sure that the
195 * thing really will compile successfully, and we never have to move the
196 * code and thus invalidate pointers into it. (Note that it has to be in
197 * one piece because free() must be able to free it all.)
198 *
199 * Beware that the optimization-preparation code in here knows about some
200 * of the structure of the compiled regexp.
201 */
202hs_regexp *
203hs_regcomp(const char *exp)
204{
205 hs_regexp *r;
206 char *scan;
207 char *longest;
208 unsigned int len;
209 int flags;
210 if (exp == NULL)
211 FAIL("NULL argument");
212
213 /* First pass: determine size, legality. */
214#ifdef notdef
215 if (exp[0] == '.' && exp[1] == '*') exp += 2; /* aid grep */
216#endif
217 regparse = exp;
218 regnpar = 1;
219 regsize = 0L;
220 regcode = &regdummy;
221 regc(MAGIC);
222 if (reg(0, &flags) == NULL)
223 return(NULL);
224
225 /* Small enough for pointer-storage convention? */
226 if (regsize >= 32767L) /* Probably could be 65535L. */
227 FAIL("regexp too big");
228
229 /* Allocate space. */
230 r = (hs_regexp *)malloc(sizeof(hs_regexp) + (unsigned)regsize);
231 if (r == NULL)
232 FAIL("out of space");
233
234 /* Second pass: emit code. */
235 regparse = exp;
236 regnpar = 1;
237 regcode = r->program;
238 regc(MAGIC);
239 if (reg(0, &flags) == NULL)
240 return(NULL);
241
242 /* Dig out information for optimizations. */
243 r->regstart = '\0'; /* Worst-case defaults. */
244 r->reganch = 0;
245 r->regmust = NULL;
246 r->regmlen = 0;
247 scan = r->program+1; /* First BRANCH. */
248
249 if (OP(regnext(scan)) == END) { /* Only one top-level choice. */
250 scan = OPERAND(scan);
251
252 /* Starting-point info. */
253 if (OP(scan) == EXACTLY)
254 r->regstart = *OPERAND(scan);
255 else if (OP(scan) == BOL)
256 r->reganch++;
257
258 /*
259 * If there's something expensive in the r.e., find the
260 * longest literal string that must appear and make it the
261 * regmust. Resolve ties in favor of later strings, since
262 * the regstart check works with the beginning of the r.e.
263 * and avoiding duplication strengthens checking. Not a
264 * strong reason, but sufficient in the absence of others.
265 */
266 if (flags&SPSTART) {
267 longest = NULL;
268 len = 0;
269 for (; scan != NULL; scan = regnext(scan))
270 if ((OP(scan) == EXACTLY) &&
271 (strlen(OPERAND(scan)) >= len)) {
272 longest = OPERAND(scan);
273 len = strlen(OPERAND(scan));
274 }
275 r->regmust = longest;
276 r->regmlen = len;
277 }
278 }
279 return(r);
280
281}
282
283/*
284 - reg - regular expression, i.e. main body or parenthesized thing
285 *
286 * Caller must absorb opening parenthesis.
287 *
288 * Combining parenthesis handling with the base level of regular expression
289 * is a trifle forced, but the need to tie the tails of the branches to what
290 * follows makes it hard to avoid.
291 */
292static char *
293reg(int paren, int *flagp)
294 /* Parenthesized? */
295
296{
297 char *ret;
298 char *br;
299 char *ender;
300 int parno=0;
301 int flags;
302
303 *flagp = HASWIDTH; /* Tentatively. */
304
305 /* Make an OPEN node, if parenthesized. */
306 if (paren) {
307 if (regnpar >= NSUBEXP)
308 FAIL("too many ()");
309 parno = regnpar;
310 regnpar++;
311 ret = regnode(OPEN+parno);
312 } else
313 ret = NULL;
314
315 /* Pick up the branches, linking them together. */
316 br = regbranch(&flags);
317 if (br == NULL)
318 return(NULL);
319 if (ret != NULL)
320 regtail(ret, br); /* OPEN -> first. */
321 else
322 ret = br;
323 if (!(flags&HASWIDTH))
324 *flagp &= ~HASWIDTH;
325 *flagp |= flags&SPSTART;
326 while (*regparse == '|' || *regparse == '\n') {
327 regparse++;
328 br = regbranch(&flags);
329 if (br == NULL)
330 return(NULL);
331 regtail(ret, br); /* BRANCH -> BRANCH. */
332 if (!(flags&HASWIDTH))
333 *flagp &= ~HASWIDTH;
334 *flagp |= flags&SPSTART;
335 }
336
337 /* Make a closing node, and hook it on the end. */
338 ender = regnode((paren) ? CLOSE+parno : END);
339 regtail(ret, ender);
340
341 /* Hook the tails of the branches to the closing node. */
342 for (br = ret; br != NULL; br = regnext(br))
343 regoptail(br, ender);
344
345 /* Check for proper termination. */
346 if (paren && *regparse++ != ')') {
347 FAIL("unmatched ()");
348 } else if (!paren && *regparse != '\0') {
349 if (*regparse == ')') {
350 FAIL("unmatched ()");
351 } else
352 FAIL("junk on end"); /* "Can't happen". */
353 /* NOTREACHED */
354 }
355
356 return(ret);
357}
358
359/*
360 - regbranch - one alternative of an | operator
361 *
362 * Implements the concatenation operator.
363 */
364static char *
365regbranch(int *flagp)
366{
367 char *ret;
368 char *chain;
369 char *latest;
370 int flags;
371
372 *flagp = WORST; /* Tentatively. */
373
374 ret = regnode(BRANCH);
375 chain = NULL;
376 while (*regparse != '\0' && *regparse != ')' &&
377 *regparse != '\n' && *regparse != '|') {
378 latest = regpiece(&flags);
379 if (latest == NULL)
380 return(NULL);
381 *flagp |= flags&HASWIDTH;
382 if (chain == NULL) /* First piece. */
383 *flagp |= flags&SPSTART;
384 else
385 regtail(chain, latest);
386 chain = latest;
387 }
388 if (chain == NULL) /* Loop ran zero times. */
389 (void) regnode(NOTHING);
390
391 return(ret);
392}
393
394/*
395 - regpiece - something followed by possible [*+?]
396 *
397 * Note that the branching code sequences used for ? and the general cases
398 * of * and + are somewhat optimized: they use the same NOTHING node as
399 * both the endmarker for their branch list and the body of the last branch.
400 * It might seem that this node could be dispensed with entirely, but the
401 * endmarker role is not redundant.
402 */
403static char *
404regpiece(int *flagp)
405{
406 char *ret;
407 char op;
408 char *next;
409 int flags;
410
411 ret = regatom(&flags);
412 if (ret == NULL)
413 return(NULL);
414
415 op = *regparse;
416 if (!ISMULT(op)) {
417 *flagp = flags;
418 return(ret);
419 }
420
421 if (!(flags&HASWIDTH) && op != '?')
422 FAIL("*+ operand could be empty");
423 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
424
425 if (op == '*' && (flags&SIMPLE))
426 reginsert(STAR, ret);
427 else if (op == '*') {
428 /* Emit x* as (x&|), where & means "self". */
429 reginsert(BRANCH, ret); /* Either x */
430 regoptail(ret, regnode(BACK)); /* and loop */
431 regoptail(ret, ret); /* back */
432 regtail(ret, regnode(BRANCH)); /* or */
433 regtail(ret, regnode(NOTHING)); /* null. */
434 } else if (op == '+' && (flags&SIMPLE))
435 reginsert(PLUS, ret);
436 else if (op == '+') {
437 /* Emit x+ as x(&|), where & means "self". */
438 next = regnode(BRANCH); /* Either */
439 regtail(ret, next);
440 regtail(regnode(BACK), ret); /* loop back */
441 regtail(next, regnode(BRANCH)); /* or */
442 regtail(ret, regnode(NOTHING)); /* null. */
443 } else if (op == '?') {
444 /* Emit x? as (x|) */
445 reginsert(BRANCH, ret); /* Either x */
446 regtail(ret, regnode(BRANCH)); /* or */
447 next = regnode(NOTHING); /* null. */
448 regtail(ret, next);
449 regoptail(ret, next);
450 }
451 regparse++;
452 if (ISMULT(*regparse))
453 FAIL("nested *?+");
454
455 return(ret);
456}
457
458/*
459 - regatom - the lowest level
460 *
461 * Optimization: gobbles an entire sequence of ordinary characters so that
462 * it can turn them into a single node, which is smaller to store and
463 * faster to run. Backslashed characters are exceptions, each becoming a
464 * separate node; the code is simpler that way and it's not worth fixing.
465 */
466static char *
467regatom(int *flagp)
468{
469 char *ret;
470 int flags;
471
472 *flagp = WORST; /* Tentatively. */
473
474 switch (*regparse++) {
475 /* FIXME: these chars only have meaning at beg/end of pat? */
476 case '^':
477 ret = regnode(BOL);
478 break;
479 case '$':
480 ret = regnode(EOL);
481 break;
482 case '.':
483 ret = regnode(ANY);
484 *flagp |= HASWIDTH|SIMPLE;
485 break;
486 case '[': {
487 int class1;
488 int classend;
489
490 if (*regparse == '^') { /* Complement of range. */
491 ret = regnode(ANYBUT);
492 regparse++;
493 } else
494 ret = regnode(ANYOF);
495 if (*regparse == ']' || *regparse == '-')
496 regc(*regparse++);
497 while (*regparse != '\0' && *regparse != ']') {
498 if (*regparse == '-') {
499 regparse++;
500 if (*regparse == ']' || *regparse == '\0')
501 regc('-');
502 else {
503 class1 = UCHARAT(regparse-2)+1;
504 classend = UCHARAT(regparse);
505 if (class1 > classend+1)
506 FAIL("invalid [] range");
507 for (; class1 <= classend; class1++)
508 regc(class1);
509 regparse++;
510 }
511 } else
512 regc(*regparse++);
513 }
514 regc('\0');
515 if (*regparse != ']')
516 FAIL("unmatched []");
517 regparse++;
518 *flagp |= HASWIDTH|SIMPLE;
519 }
520 break;
521 case '(':
522 ret = reg(1, &flags);
523 if (ret == NULL)
524 return(NULL);
525 *flagp |= flags&(HASWIDTH|SPSTART);
526 break;
527 case '\0':
528 case '|':
529 case '\n':
530 case ')':
531 FAIL("internal urp"); /* Supposed to be caught earlier. */
532 break;
533 case '?':
534 case '+':
535 case '*':
536 FAIL("?+* follows nothing");
537 break;
538 case '\\':
539 switch (*regparse++) {
540 case '\0':
541 FAIL("trailing \\");
542 break;
543 case '<':
544 ret = regnode(WORDA);
545 break;
546 case '>':
547 ret = regnode(WORDZ);
548 break;
549 /* FIXME: Someday handle \1, \2, ... */
550 default:
551 /* Handle general quoted chars in exact-match routine */
552 goto de_fault;
553 }
554 break;
555 de_fault:
556 default:
557 /*
558 * Encode a string of characters to be matched exactly.
559 *
560 * This is a bit tricky due to quoted chars and due to
561 * '*', '+', and '?' taking the SINGLE char previous
562 * as their operand.
563 *
564 * On entry, the char at regparse[-1] is going to go
565 * into the string, no matter what it is. (It could be
566 * following a \ if we are entered from the '\' case.)
567 *
568 * Basic idea is to pick up a good char in ch and
569 * examine the next char. If it's *+? then we twiddle.
570 * If it's \ then we frozzle. If it's other magic char
571 * we push ch and terminate the string. If none of the
572 * above, we push ch on the string and go around again.
573 *
574 * regprev is used to remember where "the current char"
575 * starts in the string, if due to a *+? we need to back
576 * up and put the current char in a separate, 1-char, string.
577 * When regprev is NULL, ch is the only char in the
578 * string; this is used in *+? handling, and in setting
579 * flags |= SIMPLE at the end.
580 */
581 {
582 const char *regprev;
583 char ch = 0;
584
585 regparse--; /* Look at cur char */
586 ret = regnode(EXACTLY);
587 for ( regprev = 0 ; ; ) {
588 ch = *regparse++; /* Get current char */
589 switch (*regparse) { /* look at next one */
590
591 default:
592 regc(ch); /* Add cur to string */
593 break;
594
595 case '.': case '[': case '(':
596 case ')': case '|': case '\n':
597 case '$': case '^':
598 case '\0':
599 /* FIXME, $ and ^ should not always be magic */
600 magic:
601 regc(ch); /* dump cur char */
602 goto done; /* and we are done */
603
604 case '?': case '+': case '*':
605 if (!regprev) /* If just ch in str, */
606 goto magic; /* use it */
607 /* End mult-char string one early */
608 regparse = regprev; /* Back up parse */
609 goto done;
610
611 case '\\':
612 regc(ch); /* Cur char OK */
613 switch (regparse[1]){ /* Look after \ */
614 case '\0':
615 case '<':
616 case '>':
617 /* FIXME: Someday handle \1, \2, ... */
618 goto done; /* Not quoted */
619 default:
620 /* Backup point is \, scan * point is after it. */
621 regprev = regparse;
622 regparse++;
623 continue; /* NOT break; */
624 }
625 }
626 regprev = regparse; /* Set backup point */
627 }
628 done:
629 regc('\0');
630 *flagp |= HASWIDTH;
631 if (!regprev) /* One char? */
632 *flagp |= SIMPLE;
633 }
634 break;
635 }
636
637 return(ret);
638}
639
640/*
641 - regnode - emit a node
642 */
643static char * /* Location. */
644regnode(char op)
645{
646 char *ret;
647 char *ptr;
648
649 ret = regcode;
650 if (ret == &regdummy) {
651 regsize += 3;
652 return(ret);
653 }
654
655 ptr = ret;
656 *ptr++ = op;
657 *ptr++ = '\0'; /* Null "next" pointer. */
658 *ptr++ = '\0';
659 regcode = ptr;
660
661 return(ret);
662}
663
664/*
665 - regc - emit (if appropriate) a byte of code
666 */
667static void
668regc(char b)
669{
670 if (regcode != &regdummy)
671 *regcode++ = b;
672 else
673 regsize++;
674}
675
676/*
677 - reginsert - insert an operator in front of already-emitted operand
678 *
679 * Means relocating the operand.
680 */
681static void
682reginsert(char op, char *opnd)
683{
684 char *src;
685 char *dst;
686 char *place;
687
688 if (regcode == &regdummy) {
689 regsize += 3;
690 return;
691 }
692
693 src = regcode;
694 regcode += 3;
695 dst = regcode;
696 while (src > opnd)
697 *--dst = *--src;
698
699 place = opnd; /* Op node, where operand used to be. */
700 *place++ = op;
701 *place++ = '\0';
702 *place++ = '\0';
703}
704
705/*
706 - regtail - set the next-pointer at the end of a node chain
707 */
708static void
709regtail(char *p, char *val)
710{
711 char *scan;
712 char *temp;
713 int offset;
714
715 if (p == &regdummy)
716 return;
717
718 /* Find last node. */
719 scan = p;
720 for (;;) {
721 temp = regnext(scan);
722 if (temp == NULL)
723 break;
724 scan = temp;
725 }
726
727 if (OP(scan) == BACK)
728 offset = scan - val;
729 else
730 offset = val - scan;
731 *(scan+1) = (offset>>8)&0377;
732 *(scan+2) = offset&0377;
733}
734
735/*
736 - regoptail - regtail on operand of first argument; nop if operandless
737 */
738static void
739regoptail(char *p, char *val)
740{
741 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
742 if (p == NULL || p == &regdummy || OP(p) != BRANCH)
743 return;
744 regtail(OPERAND(p), val);
745}
746
747/*
748 * regexec and friends
749 */
750
751/*
752 * Global work variables for regexec().
753 */
754static const char *reginput; /* EST_String-input pointer. */
755static const char *regbol; /* Beginning of input, for ^ check. */
756static const char **regstartp; /* Pointer to startp array. */
757static const char **regendp; /* Ditto for endp. */
758
759/*
760 * Forwards.
761 */
762STATIC int regtry(hs_regexp *prog, const char *string);
763STATIC int regmatch(char *prog);
764STATIC int regrepeat(char *p);
765
766#ifdef DEBUG
767FILE *regnarrate = stdout;
768void regdump();
769STATIC char *regprop( char *scan);
770#endif
771
772/*
773 - regexec - match a regexp against a string
774 */
775int
776hs_regexec(const hs_regexp *prog, const char *string)
777{
778 char *s;
779
780 /* Be paranoid... */
781 if (prog == NULL || string == NULL) {
782 hs_regerror("NULL parameter");
783 return(0);
784 }
785
786 /* Check validity of program. */
787 if (UCHARAT(prog->program) != MAGIC) {
788 hs_regerror("corrupted program");
789 return(0);
790 }
791
792 /* If there is a "must appear" string, look for it. */
793 if (prog->regmust != NULL) {
794 s = (char *)string;
795 while ((s = strchr(s, prog->regmust[0])) != NULL) {
796 if (strncmp(s, prog->regmust, prog->regmlen) == 0)
797 break; /* Found it. */
798 s++;
799 }
800 if (s == NULL) /* Not present. */
801 return(0);
802 }
803
804 /* Mark beginning of line for ^ . */
805 regbol = (char *)string;
806
807 /* Simplest case: anchored match need be tried only once. */
808 if (prog->reganch)
809 return(regtry((hs_regexp *)prog, string));
810
811 /* Messy cases: unanchored match. */
812 s = (char *)string;
813 if (prog->regstart != '\0')
814 /* We know what char it must start with. */
815 while ((s = strchr(s, prog->regstart)) != NULL) {
816 if (regtry((hs_regexp *)prog, s))
817 return(1);
818 s++;
819 }
820 else
821 /* We don't -- general case. */
822 do {
823 if (regtry((hs_regexp *)prog, s))
824 return(1);
825 } while (*s++ != '\0');
826
827 /* Failure. */
828 return(0);
829}
830
831/*
832 - regtry - try match at specific point
833 */
834static int /* 0 failure, 1 success */
835regtry(hs_regexp *prog, const char *string)
836{
837 int i;
838 char **sp;
839 char **ep;
840
841 reginput = string;
842 regstartp = (const char **)prog->startp;
843 regendp = (const char **)prog->endp;
844
845 sp = prog->startp;
846 ep = prog->endp;
847 for (i = NSUBEXP; i > 0; i--) {
848 *sp++ = NULL;
849 *ep++ = NULL;
850 }
851 if (regmatch(prog->program + 1)) {
852 prog->startp[0] = (char *)string;
853 prog->endp[0] = (char *)reginput;
854 return(1);
855 } else
856 return(0);
857}
858
859/*
860 - regmatch - main matching routine
861 *
862 * Conceptually the strategy is simple: check to see whether the current
863 * node matches, call self recursively to see whether the rest matches,
864 * and then act accordingly. In practice we make some effort to avoid
865 * recursion, in particular by going through "ordinary" nodes (that don't
866 * need to know whether the rest of the match failed) by a loop instead of
867 * by recursion.
868 */
869static int /* 0 failure, 1 success */
870regmatch(char *prog)
871{
872 char *scan; /* Current node. */
873 char *next; /* Next node. */
874
875 scan = prog;
876#ifdef DEBUG
877 if (scan != NULL && regnarrate)
878 fprintf(regnarrate, "%s(\n", regprop(scan));
879#endif
880 while (scan != NULL) {
881#ifdef DEBUG
882 if (regnarrate)
883 fprintf(regnarrate, "%s...\n", regprop(scan));
884#endif
885 next = regnext(scan);
886
887 switch (OP(scan)) {
888 case BOL:
889 if (reginput != regbol)
890 return(0);
891 break;
892 case EOL:
893 if (*reginput != '\0')
894 return(0);
895 break;
896 case WORDA:
897 /* Must be looking at a letter, digit, or _ */
898 if ((!isalnum((int)*reginput)) && *reginput != '_')
899 return(0);
900 /* Prev must be BOL or nonword */
901 if (reginput > regbol &&
902 (isalnum((int)reginput[-1]) || reginput[-1] == '_'))
903 return(0);
904 break;
905 case WORDZ:
906 /* Must be looking at non letter, digit, or _ */
907 if (isalnum((int)*reginput) || *reginput == '_')
908 return(0);
909 /* We don't care what the previous char was */
910 break;
911 case ANY:
912 if (*reginput == '\0')
913 return(0);
914 reginput++;
915 break;
916 case EXACTLY: {
917 int len;
918 char *opnd;
919
920 opnd = OPERAND(scan);
921 /* Inline the first character, for speed. */
922 if (*opnd != *reginput)
923 return(0);
924 len = strlen(opnd);
925 if (len > 1 && strncmp(opnd, reginput, len) != 0)
926 return(0);
927 reginput += len;
928 }
929 break;
930 case ANYOF:
931 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
932 return(0);
933 reginput++;
934 break;
935 case ANYBUT:
936 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
937 return(0);
938 reginput++;
939 break;
940 case NOTHING:
941 break;
942 case BACK:
943 break;
944 case OPEN+1:
945 case OPEN+2:
946 case OPEN+3:
947 case OPEN+4:
948 case OPEN+5:
949 case OPEN+6:
950 case OPEN+7:
951 case OPEN+8:
952 case OPEN+9: {
953 int no;
954 const char *save;
955
956 no = OP(scan) - OPEN;
957 save = reginput;
958
959 if (regmatch(next)) {
960 /*
961 * Don't set startp if some later
962 * invocation of the same parentheses
963 * already has.
964 */
965 if (regstartp[no] == NULL)
966 regstartp[no] = save;
967 return(1);
968 } else
969 return(0);
970 }
971 break;
972 case CLOSE+1:
973 case CLOSE+2:
974 case CLOSE+3:
975 case CLOSE+4:
976 case CLOSE+5:
977 case CLOSE+6:
978 case CLOSE+7:
979 case CLOSE+8:
980 case CLOSE+9: {
981 int no;
982 const char *save;
983
984 no = OP(scan) - CLOSE;
985 save = reginput;
986
987 if (regmatch(next)) {
988 /*
989 * Don't set endp if some later
990 * invocation of the same parentheses
991 * already has.
992 */
993 if (regendp[no] == NULL)
994 regendp[no] = save;
995 return(1);
996 } else
997 return(0);
998 }
999 break;
1000 case BRANCH: {
1001 const char *save;
1002
1003 if (OP(next) != BRANCH) /* No choice. */
1004 next = OPERAND(scan); /* Avoid recursion. */
1005 else {
1006 do {
1007 save = reginput;
1008 if (regmatch(OPERAND(scan)))
1009 return(1);
1010 reginput = save;
1011 scan = regnext(scan);
1012 } while (scan != NULL && OP(scan) == BRANCH);
1013 return(0);
1014 /* NOTREACHED */
1015 }
1016 }
1017 break;
1018 case STAR:
1019 case PLUS: {
1020 char nextch;
1021 int no;
1022 const char *save;
1023 int min;
1024
1025 /*
1026 * Lookahead to avoid useless match attempts
1027 * when we know what character comes next.
1028 */
1029 nextch = '\0';
1030 if (OP(next) == EXACTLY)
1031 nextch = *OPERAND(next);
1032 min = (OP(scan) == STAR) ? 0 : 1;
1033 save = reginput;
1034
1035 no = regrepeat(OPERAND(scan));
1036 while (no >= min) {
1037 /* If it could work, try it. */
1038 if (nextch == '\0' || *reginput == nextch)
1039 {
1040 if (regmatch(next))
1041 return(1);
1042 }
1043 /* Couldn't or didn't -- back up. */
1044 no--;
1045 reginput = save + no;
1046 }
1047 return(0);
1048 }
1049 break;
1050 case END:
1051 return(1); /* Success! */
1052 break;
1053 default:
1054 hs_regerror("memory corruption");
1055 return(0);
1056 break;
1057 }
1058
1059 scan = next;
1060 }
1061
1062 /*
1063 * We get here only if there's trouble -- normally "case END" is
1064 * the terminating point.
1065 */
1066 hs_regerror("corrupted pointers");
1067 return(0);
1068}
1069
1070/*
1071 - regrepeat - repeatedly match something simple, report how many
1072 */
1073static int
1074regrepeat(char *p)
1075{
1076 int count = 0;
1077 const char *scan;
1078 char *opnd;
1079
1080 scan = reginput;
1081 opnd = OPERAND(p);
1082 switch (OP(p)) {
1083 case ANY:
1084 count = strlen(scan);
1085 scan += count;
1086 break;
1087 case EXACTLY:
1088 while (*opnd == *scan) {
1089 count++;
1090 scan++;
1091 }
1092 break;
1093 case ANYOF:
1094 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
1095 count++;
1096 scan++;
1097 }
1098 break;
1099 case ANYBUT:
1100 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
1101 count++;
1102 scan++;
1103 }
1104 break;
1105 default: /* Oh dear. Called inappropriately. */
1106 hs_regerror("internal foulup");
1107 count = 0; /* Best compromise. */
1108 break;
1109 }
1110 reginput = scan;
1111
1112 return(count);
1113}
1114
1115/*
1116 - regnext - dig the "next" pointer out of a node
1117 */
1118static char *
1119regnext(char *p)
1120{
1121 int offset;
1122
1123 if (p == &regdummy)
1124 return(NULL);
1125
1126 offset = NEXT(p);
1127 if (offset == 0)
1128 return(NULL);
1129
1130 if (OP(p) == BACK)
1131 return(p-offset);
1132 else
1133 return(p+offset);
1134}
1135
1136#ifdef DEBUG
1137
1138STATIC char *regprop(char *scan);
1139
1140/*
1141 - regdump - dump a regexp onto stdout in vaguely comprehensible form
1142 */
1143void
1144regdump(hs_regexp *r)
1145{
1146 char *s;
1147 char op = EXACTLY; /* Arbitrary non-END op. */
1148 char *next;
1149
1150 s = r->program + 1;
1151 while (op != END) { /* While that wasn't END last time... */
1152 op = OP(s);
1153 printf("%2d%s", s-r->program, regprop(s)); /* Where, what. */
1154 next = regnext(s);
1155 if (next == NULL) /* Next ptr. */
1156 printf("(0)");
1157 else
1158 printf("(%d)", (s-r->program)+(next-s));
1159 s += 3;
1160 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
1161 /* Literal string, where present. */
1162 while (*s != '\0') {
1163 putchar(*s);
1164 s++;
1165 }
1166 s++;
1167 }
1168 putchar('\n');
1169 }
1170
1171 /* Header fields of interest. */
1172 if (r->regstart != '\0')
1173 printf("start `%c' ", r->regstart);
1174 if (r->reganch)
1175 printf("anchored ");
1176 if (r->regmust != NULL)
1177 printf("must have \"%s\"", r->regmust);
1178 printf("\n");
1179}
1180
1181/*
1182 - regprop - printable representation of opcode
1183 */
1184static char *
1185regprop(char *op)
1186{
1187 char *p=NULL;
1188 static char buf[50];
1189
1190 (void) strcpy(buf, ":");
1191
1192 switch (OP(op)) {
1193 case BOL:
1194 p = "BOL";
1195 break;
1196 case EOL:
1197 p = "EOL";
1198 break;
1199 case ANY:
1200 p = "ANY";
1201 break;
1202 case ANYOF:
1203 p = "ANYOF";
1204 break;
1205 case ANYBUT:
1206 p = "ANYBUT";
1207 break;
1208 case BRANCH:
1209 p = "BRANCH";
1210 break;
1211 case EXACTLY:
1212 p = "EXACTLY";
1213 break;
1214 case NOTHING:
1215 p = "NOTHING";
1216 break;
1217 case BACK:
1218 p = "BACK";
1219 break;
1220 case END:
1221 p = "END";
1222 break;
1223 case OPEN+1:
1224 case OPEN+2:
1225 case OPEN+3:
1226 case OPEN+4:
1227 case OPEN+5:
1228 case OPEN+6:
1229 case OPEN+7:
1230 case OPEN+8:
1231 case OPEN+9:
1232 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
1233 p = NULL;
1234 break;
1235 case CLOSE+1:
1236 case CLOSE+2:
1237 case CLOSE+3:
1238 case CLOSE+4:
1239 case CLOSE+5:
1240 case CLOSE+6:
1241 case CLOSE+7:
1242 case CLOSE+8:
1243 case CLOSE+9:
1244 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
1245 p = NULL;
1246 break;
1247 case STAR:
1248 p = "STAR";
1249 break;
1250 case PLUS:
1251 p = "PLUS";
1252 break;
1253 case WORDA:
1254 p = "WORDA";
1255 break;
1256 case WORDZ:
1257 p = "WORDZ";
1258 break;
1259 default:
1260 hs_regerror("corrupted opcode");
1261 break;
1262 }
1263 if (p != NULL)
1264 (void) strcat(buf, p);
1265 return(buf);
1266}
1267#endif
1268
1269/*
1270 * The following is provided for those people who do not have strcspn() in
1271 * their C libraries. They should get off their butts and do something
1272 * about it; at least one public-domain implementation of those (highly
1273 * useful) string routines has been published on Usenet.
1274 */
1275#ifdef STRCSPN
1276/*
1277 * strcspn - find length of initial segment of s1 consisting entirely
1278 * of characters not from s2
1279 */
1280
1281static int
1282strcspn(s1, s2)
1283char *s1;
1284char *s2;
1285{
1286 char *scan1;
1287 char *scan2;
1288 int count;
1289
1290 count = 0;
1291 for (scan1 = s1; *scan1 != '\0'; scan1++) {
1292 for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */
1293 if (*scan1 == *scan2++)
1294 return(count);
1295 count++;
1296 }
1297 return(count);
1298}
1299#endif