source: trunk/minix/commands/awk/regexp.c@ 9

Last change on this file since 9 was 9, checked in by Mattia Monga, 13 years ago

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