cvs.zerfleddert.de Git - micropolis/blob

1 /*

2 * regcomp and regexec -- regsub and regerror are elsewhere

3 *

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 * *** NOTE: this code has been altered slightly for use in Tcl. ***

26 * *** The only change is to use ckalloc and ckfree instead of ***

27 * *** malloc and free. ***

28 */

29 #include "tclint.h"

31 /*

32 * The "internal use only" fields in regexp.h are present to pass info from

33 * compile to execute that permits the execute phase to run lots faster on

34 * simple cases. They are:

35 *

36 * regstart char that must begin a match; '\0' if none obvious

37 * reganch is the match anchored (at beginning-of-line only)?

38 * regmust string (pointer into program) that match must include, or NULL

39 * regmlen length of regmust string

40 *

41 * Regstart and reganch permit very fast decisions on suitable starting points

42 * for a match, cutting down the work a lot. Regmust permits fast rejection

43 * of lines that cannot possibly match. The regmust tests are costly enough

44 * that regcomp() supplies a regmust only if the r.e. contains something

45 * potentially expensive (at present, the only such thing detected is * or +

46 * at the start of the r.e., which can involve a lot of backup). Regmlen is

47 * supplied because the test in regexec() needs it and regcomp() is computing

48 * it anyway.

49 */

51 /*

52 * Structure for regexp "program". This is essentially a linear encoding

53 * of a nondeterministic finite-state machine (aka syntax charts or

54 * "railroad normal form" in parsing technology). Each node is an opcode

55 * plus a "next" pointer, possibly plus an operand. "Next" pointers of

56 * all nodes except BRANCH implement concatenation; a "next" pointer with

57 * a BRANCH on both ends of it is connecting two alternatives. (Here we

58 * have one of the subtle syntax dependencies: an individual BRANCH (as

59 * opposed to a collection of them) is never concatenated with anything

60 * because of operator precedence.) The operand of some types of node is

61 * a literal string; for others, it is a node leading into a sub-FSM. In

62 * particular, the operand of a BRANCH node is the first node of the branch.

63 * (NB this is *not* a tree structure: the tail of the branch connects

64 * to the thing following the set of BRANCHes.) The opcodes are:

65 */

67 /* definition number opnd? meaning */

68 #define END 0 /* no End of program. */

69 #define BOL 1 /* no Match "" at beginning of line. */

70 #define EOL 2 /* no Match "" at end of line. */

71 #define ANY 3 /* no Match any one character. */

72 #define ANYOF 4 /* str Match any character in this string. */

73 #define ANYBUT 5 /* str Match any character not in this string. */

74 #define BRANCH 6 /* node Match this alternative, or the next... */

75 #define BACK 7 /* no Match "", "next" ptr points backward. */

76 #define EXACTLY 8 /* str Match this string. */

77 #define NOTHING 9 /* no Match empty string. */

78 #define STAR 10 /* node Match this (simple) thing 0 or more times. */

79 #define PLUS 11 /* node Match this (simple) thing 1 or more times. */

80 #define OPEN 20 /* no Mark this point in input as start of #n. */

81 /* OPEN+1 is number 1, etc. */

82 #define CLOSE 30 /* no Analogous to OPEN. */

84 /*

85 * Opcode notes:

86 *

87 * BRANCH The set of branches constituting a single choice are hooked

88 * together with their "next" pointers, since precedence prevents

89 * anything being concatenated to any individual branch. The

90 * "next" pointer of the last BRANCH in a choice points to the

91 * thing following the whole choice. This is also where the

92 * final "next" pointer of each individual branch points; each

93 * branch starts with the operand node of a BRANCH node.

94 *

95 * BACK Normal "next" pointers all implicitly point forward; BACK

96 * exists to make loop structures possible.

97 *

98 * STAR,PLUS '?', and complex '*' and '+', are implemented as circular

99 * BRANCH structures using BACK. Simple cases (one character

100 * per match) are implemented with STAR and PLUS for speed

101 * and to minimize recursive plunges.

102 *

103 * OPEN,CLOSE ...are numbered at compile time.

104 */

105

106 /*

107 * A node is one char of opcode followed by two chars of "next" pointer.

108 * "Next" pointers are stored as two 8-bit pieces, high order first. The

109 * value is a positive offset from the opcode of the node containing it.

110 * An operand, if any, simply follows the node. (Note that much of the

111 * code generation knows about this implicit relationship.)

112 *

113 * Using two bytes for the "next" pointer is vast overkill for most things,

114 * but allows patterns to get big without disasters.

115 */

116 #define OP(p) (*(p))

117 #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))

118 #define OPERAND(p) ((p) + 3)

119

120 /*

121 * See regmagic.h for one further detail of program structure.

122 */

123

124

125 /*

126 * Utility definitions.

127 */

128 #ifndef CHARBITS

129 #define UCHARAT(p) ((int)*(unsigned char *)(p))

130 #else

131 #define UCHARAT(p) ((int)*(p)&CHARBITS)

132 #endif

133

134 #define FAIL(m) { regerror(m); return(NULL); }

 #define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')

 #define META    "^$.[()|?+*\\"

137

138 /*

139 * Flags to be passed up and down.

140 */

141 #define HASWIDTH 01 /* Known never to match null string. */

142 #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */

143 #define SPSTART 04 /* Starts with * or +. */

144 #define WORST 0 /* Worst case. */

145

146 /*

147 * Global work variables for regcomp().

148 */

149 static char *regparse; /* Input-scan pointer. */

150 static int regnpar; /* () count. */

151 static char regdummy;

152 static char *regcode; /* Code-emit pointer; &regdummy = don't. */

153 static long regsize; /* Code size. */

154

155 /*

156 * The first byte of the regexp internal "program" is actually this magic

157 * number; the start node begins in the second byte.

158 */

159 #define MAGIC 0234

160

161

162 /*

163 * Forward declarations for regcomp()'s friends.

164 */

165 #ifndef STATIC

166 #define STATIC static

167 #endif

168 STATIC char *reg();

169 STATIC char *regbranch();

170 STATIC char *regpiece();

171 STATIC char *regatom();

172 STATIC char *regnode();

173 STATIC char *regnext();

174 STATIC void regc();

175 STATIC void reginsert();

176 STATIC void regtail();

177 STATIC void regoptail();

178 #ifdef STRCSPN

179 STATIC int strcspn();

180 #endif

181

182 /*

183 - regcomp - compile a regular expression into internal code

184 *

185 * We can't allocate space until we know how big the compiled form will be,

186 * but we can't compile it (and thus know how big it is) until we've got a

187 * place to put the code. So we cheat: we compile it twice, once with code

188 * generation turned off and size counting turned on, and once "for real".

189 * This also means that we don't allocate space until we are sure that the

190 * thing really will compile successfully, and we never have to move the

191 * code and thus invalidate pointers into it. (Note that it has to be in

192 * one piece because free() must be able to free it all.)

193 *

194 * Beware that the optimization-preparation code in here knows about some

195 * of the structure of the compiled regexp.

196 */

197 regexp *

198 regcomp(exp)

199 char *exp;

200 {

201 register regexp *r;

202 register char *scan;

203 register char *longest;

204 register int len;

205 int flags;

206

207 if (exp == NULL)

208 FAIL("NULL argument");

209

210 /* First pass: determine size, legality. */

211 regparse = exp;

212 regnpar = 1;

213 regsize = 0L;

214 regcode = &regdummy;

215 regc(MAGIC);

         if (reg(0, &flags) == NULL)

217 return(NULL);

218

219 /* Small enough for pointer-storage convention? */

         if (regsize >= 32767L)          /* Probably could be 65535L. */

221 FAIL("regexp too big");

222

223 /* Allocate space. */

         r = (regexp *)ckalloc(sizeof(regexp) + (unsigned)regsize);

225 if (r == NULL)

226 FAIL("out of space");

227

228 /* Second pass: emit code. */

229 regparse = exp;

230 regnpar = 1;

231 regcode = r->program;

232 regc(MAGIC);

         if (reg(0, &flags) == NULL)

234 return(NULL);

235

236 /* Dig out information for optimizations. */

         r->regstart = '\0';     /* Worst-case defaults. */

238 r->reganch = 0;

239 r->regmust = NULL;

240 r->regmlen = 0;

         scan = r->program+1;                    /* First BRANCH. */

         if (OP(regnext(scan)) == END) {         /* Only one top-level choice. */

243 scan = OPERAND(scan);

244

245 /* Starting-point info. */

                 if (OP(scan) == EXACTLY)

                         r->regstart = *OPERAND(scan);

                 else if (OP(scan) == BOL)

249 r->reganch++;

250

251 /*

252 * If there's something expensive in the r.e., find the

253 * longest literal string that must appear and make it the

254 * regmust. Resolve ties in favor of later strings, since

255 * the regstart check works with the beginning of the r.e.

256 * and avoiding duplication strengthens checking. Not a

257 * strong reason, but sufficient in the absence of others.

258 */

259 if (flags&SPSTART) {

260 longest = NULL;

261 len = 0;

                         for (; scan != NULL; scan = regnext(scan))

                                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {

264 longest = OPERAND(scan);

                                         len = strlen(OPERAND(scan));

266 }

267 r->regmust = longest;

268 r->regmlen = len;

269 }

270 }

271

272 return(r);

273 }

274

275 /*

276 - reg - regular expression, i.e. main body or parenthesized thing

277 *

278 * Caller must absorb opening parenthesis.

279 *

280 * Combining parenthesis handling with the base level of regular expression

281 * is a trifle forced, but the need to tie the tails of the branches to what

282 * follows makes it hard to avoid.

283 */

284 static char *

285 reg(paren, flagp)

286 int paren; /* Parenthesized? */

287 int *flagp;

288 {

289 register char *ret;

290 register char *br;

291 register char *ender;

         register int parno = 0;

293 int flags;

294

295 *flagp = HASWIDTH; /* Tentatively. */

296

297 /* Make an OPEN node, if parenthesized. */

298 if (paren) {

299 if (regnpar >= NSUBEXP)

300 FAIL("too many ()");

301 parno = regnpar;

302 regnpar++;

                 ret = regnode(OPEN+parno);

304 } else

305 ret = NULL;

306

307 /* Pick up the branches, linking them together. */

308 br = regbranch(&flags);

309 if (br == NULL)

310 return(NULL);

311 if (ret != NULL)

                 regtail(ret, br);       /* OPEN -> first. */

313 else

314 ret = br;

315 if (!(flags&HASWIDTH))

316 *flagp &= ~HASWIDTH;

317 *flagp |= flags&SPSTART;

         while (*regparse == '|') {

319 regparse++;

320 br = regbranch(&flags);

321 if (br == NULL)

322 return(NULL);

                 regtail(ret, br);       /* BRANCH -> BRANCH. */

324 if (!(flags&HASWIDTH))

325 *flagp &= ~HASWIDTH;

326 *flagp |= flags&SPSTART;

327 }

328

329 /* Make a closing node, and hook it on the end. */

         ender = regnode((paren) ? CLOSE+parno : END);   

331 regtail(ret, ender);

332

333 /* Hook the tails of the branches to the closing node. */

         for (br = ret; br != NULL; br = regnext(br))

335 regoptail(br, ender);

336

337 /* Check for proper termination. */

         if (paren && *regparse++ != ')') {

339 FAIL("unmatched ()");

         } else if (!paren && *regparse != '\0') {

                 if (*regparse == ')') {

342 FAIL("unmatched ()");

343 } else

                         FAIL("junk on end");    /* "Can't happen". */

345 /* NOTREACHED */

346 }

347

348 return(ret);

349 }

350

351 /*

352 - regbranch - one alternative of an | operator

353 *

354 * Implements the concatenation operator.

355 */

356 static char *

357 regbranch(flagp)

358 int *flagp;

359 {

360 register char *ret;

361 register char *chain;

362 register char *latest;

363 int flags;

364

365 *flagp = WORST; /* Tentatively. */

366

367 ret = regnode(BRANCH);

368 chain = NULL;

         while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {

370 latest = regpiece(&flags);

371 if (latest == NULL)

372 return(NULL);

373 *flagp |= flags&HASWIDTH;

                 if (chain == NULL)      /* First piece. */

375 *flagp |= flags&SPSTART;

376 else

377 regtail(chain, latest);

378 chain = latest;

379 }

         if (chain == NULL)      /* Loop ran zero times. */

                 (void) regnode(NOTHING);

382

383 return(ret);

384 }

385

386 /*

387 - regpiece - something followed by possible [*+?]

388 *

389 * Note that the branching code sequences used for ? and the general cases

390 * of * and + are somewhat optimized: they use the same NOTHING node as

391 * both the endmarker for their branch list and the body of the last branch.

392 * It might seem that this node could be dispensed with entirely, but the

393 * endmarker role is not redundant.

394 */

395 static char *

396 regpiece(flagp)

397 int *flagp;

398 {

399 register char *ret;

400 register char op;

401 register char *next;

402 int flags;

403

404 ret = regatom(&flags);

405 if (ret == NULL)

406 return(NULL);

407

408 op = *regparse;

         if (!ISMULT(op)) {

410 *flagp = flags;

411 return(ret);

412 }

413

         if (!(flags&HASWIDTH) && op != '?')

415 FAIL("*+ operand could be empty");

         *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);

417

         if (op == '*' && (flags&SIMPLE))

419 reginsert(STAR, ret);

         else if (op == '*') {

421 /* Emit x* as (x&|), where & means "self". */

                 reginsert(BRANCH, ret);                 /* Either x */

                 regoptail(ret, regnode(BACK));          /* and loop */

                 regoptail(ret, ret);                    /* back */

                 regtail(ret, regnode(BRANCH));          /* or */

                 regtail(ret, regnode(NOTHING));         /* null. */

         } else if (op == '+' && (flags&SIMPLE))

428 reginsert(PLUS, ret);

         else if (op == '+') {

430 /* Emit x+ as x(&|), where & means "self". */

                 next = regnode(BRANCH);                 /* Either */

432 regtail(ret, next);

                 regtail(regnode(BACK), ret);            /* loop back */

                 regtail(next, regnode(BRANCH));         /* or */

                 regtail(ret, regnode(NOTHING));         /* null. */

         } else if (op == '?') {

437 /* Emit x? as (x|) */

                 reginsert(BRANCH, ret);                 /* Either x */

                 regtail(ret, regnode(BRANCH));          /* or */

                 next = regnode(NOTHING);                /* null. */

441 regtail(ret, next);

442 regoptail(ret, next);

443 }

444 regparse++;

         if (ISMULT(*regparse))

446 FAIL("nested *?+");

447

448 return(ret);

449 }

450

451 /*

452 - regatom - the lowest level

453 *

454 * Optimization: gobbles an entire sequence of ordinary characters so that

455 * it can turn them into a single node, which is smaller to store and

456 * faster to run. Backslashed characters are exceptions, each becoming a

457 * separate node; the code is simpler that way and it's not worth fixing.

458 */

459 static char *

460 regatom(flagp)

461 int *flagp;

462 {

463 register char *ret;

464 int flags;

465

466 *flagp = WORST; /* Tentatively. */

467

468 switch (*regparse++) {

469 case '^':

470 ret = regnode(BOL);

471 break;

472 case '$':

473 ret = regnode(EOL);

474 break;

475 case '.':

476 ret = regnode(ANY);

477 *flagp |= HASWIDTH|SIMPLE;

478 break;

479 case '[': {

480 register int clss;

481 register int classend;

482

                         if (*regparse == '^') { /* Complement of range. */

484 ret = regnode(ANYBUT);

485 regparse++;

486 } else

487 ret = regnode(ANYOF);

                         if (*regparse == ']' || *regparse == '-')

489 regc(*regparse++);

                         while (*regparse != '\0' && *regparse != ']') {

                                 if (*regparse == '-') {

492 regparse++;

                                         if (*regparse == ']' || *regparse == '\0')

494 regc('-');

495 else {

                                                 clss = UCHARAT(regparse-2)+1;

497 classend = UCHARAT(regparse);

                                                 if (clss > classend+1)

499 FAIL("invalid [] range");

                                                 for (; clss <= classend; clss++)

501 regc(clss);

502 regparse++;

503 }

504 } else

505 regc(*regparse++);

506 }

507 regc('\0');

                         if (*regparse != ']')

509 FAIL("unmatched []");

510 regparse++;

511 *flagp |= HASWIDTH|SIMPLE;

512 }

513 break;

514 case '(':

                 ret = reg(1, &flags);

516 if (ret == NULL)

517 return(NULL);

                 *flagp |= flags&(HASWIDTH|SPSTART);

519 break;

520 case '\0':

521 case '|':

522 case ')':

                 FAIL("internal urp");   /* Supposed to be caught earlier. */

524 /* NOTREACHED */

525 break;

526 case '?':

527 case '+':

528 case '*':

529 FAIL("?+* follows nothing");

530 /* NOTREACHED */

531 break;

         case '\\':

                 if (*regparse == '\0')

                         FAIL("trailing \\");

535 ret = regnode(EXACTLY);

536 regc(*regparse++);

537 regc('\0');

538 *flagp |= HASWIDTH|SIMPLE;

539 break;

540 default: {

541 register int len;

542 register char ender;

543

544 regparse--;

                         len = strcspn(regparse, META);

                         if (len <= 0)

547 FAIL("internal disaster");

548 ender = *(regparse+len);

                         if (len > 1 && ISMULT(ender))

550 len--; /* Back off clear of ?+* operand. */

551 *flagp |= HASWIDTH;

                         if (len == 1)

553 *flagp |= SIMPLE;

554 ret = regnode(EXACTLY);

                         while (len > 0) {

556 regc(*regparse++);

557 len--;

558 }

559 regc('\0');

560 }

561 break;

562 }

563

564 return(ret);

565 }

566

567 /*

568 - regnode - emit a node

569 */

570 static char * /* Location. */

571 regnode(op)

572 char op;

573 {

574 register char *ret;

575 register char *ptr;

576

577 ret = regcode;

578 if (ret == &regdummy) {

579 regsize += 3;

580 return(ret);

581 }

582

583 ptr = ret;

584 *ptr++ = op;

         *ptr++ = '\0';          /* Null "next" pointer. */

586 *ptr++ = '\0';

587 regcode = ptr;

588

589 return(ret);

590 }

591

592 /*

593 - regc - emit (if appropriate) a byte of code

594 */

595 static void

596 regc(b)

597 char b;

598 {

599 if (regcode != &regdummy)

600 *regcode++ = b;

601 else

602 regsize++;

603 }

604

605 /*

606 - reginsert - insert an operator in front of already-emitted operand

607 *

608 * Means relocating the operand.

609 */

610 static void

611 reginsert(op, opnd)

612 char op;

613 char *opnd;

614 {

615 register char *src;

616 register char *dst;

617 register char *place;

618

619 if (regcode == &regdummy) {

620 regsize += 3;

621 return;

622 }

623

624 src = regcode;

625 regcode += 3;

626 dst = regcode;

627 while (src > opnd)

628 *--dst = *--src;

629

630 place = opnd; /* Op node, where operand used to be. */

631 *place++ = op;

632 *place++ = '\0';

633 *place++ = '\0';

634 }

635

636 /*

637 - regtail - set the next-pointer at the end of a node chain

638 */

639 static void

640 regtail(p, val)

641 char *p;

642 char *val;

643 {

644 register char *scan;

645 register char *temp;

646 register int offset;

647

648 if (p == &regdummy)

649 return;

650

651 /* Find last node. */

652 scan = p;

653 for (;;) {

654 temp = regnext(scan);

655 if (temp == NULL)

656 break;

657 scan = temp;

658 }

659

         if (OP(scan) == BACK)

661 offset = scan - val;

662 else

663 offset = val - scan;

         *(scan+1) = (offset>>8)&0377;

         *(scan+2) = offset&0377;

666 }

667

668 /*

669 - regoptail - regtail on operand of first argument; nop if operandless

670 */

671 static void

672 regoptail(p, val)

673 char *p;

674 char *val;

675 {

676 /* "Operandless" and "op != BRANCH" are synonymous in practice. */

         if (p == NULL || p == &regdummy || OP(p) != BRANCH)

678 return;

         regtail(OPERAND(p), val);

680 }

681

682 /*

683 * regexec and friends

684 */

685

686 /*

687 * Global work variables for regexec().

688 */

689 static char *reginput; /* String-input pointer. */

690 static char *regbol; /* Beginning of input, for ^ check. */

691 static char **regstartp; /* Pointer to startp array. */

692 static char **regendp; /* Ditto for endp. */

693

694 /*

695 * Forwards.

696 */

697 STATIC int regtry();

698 STATIC int regmatch();

699 STATIC int regrepeat();

700

701 #ifdef DEBUG

702 int regnarrate = 0;

703 void regdump();

704 STATIC char *regprop();

705 #endif

706

707 /*

708 - regexec - match a regexp against a string

709 */

710 int

711 regexec(prog, string)

712 register regexp *prog;

713 register char *string;

714 {

715 register char *s;

716 #ifndef IS_LINUX

         extern char *strchr();

718 #endif

719

720 /* Be paranoid... */

         if (prog == NULL || string == NULL) {

722 regerror("NULL parameter");

723 return(0);

724 }

725

726 /* Check validity of program. */

         if (UCHARAT(prog->program) != MAGIC) {

728 regerror("corrupted program");

729 return(0);

730 }

731

732 /* If there is a "must appear" string, look for it. */

         if (prog->regmust != NULL) {

734 s = string;

                 while ((s = strchr(s, prog->regmust[0])) != NULL) {

                         if (strncmp(s, prog->regmust, prog->regmlen) == 0)

737 break; /* Found it. */

738 s++;

739 }

                 if (s == NULL)  /* Not present. */

741 return(0);

742 }

743

744 /* Mark beginning of line for ^ . */

745 regbol = string;

746

747 /* Simplest case: anchored match need be tried only once. */

748 if (prog->reganch)

                 return(regtry(prog, string));

750

751 /* Messy cases: unanchored match. */

752 s = string;

         if (prog->regstart != '\0')

754 /* We know what char it must start with. */

                 while ((s = strchr(s, prog->regstart)) != NULL) {

                         if (regtry(prog, s))

757 return(1);

758 s++;

759 }

760 else

761 /* We don't -- general case. */

762 do {

                         if (regtry(prog, s))

764 return(1);

                 } while (*s++ != '\0');

766

767 /* Failure. */

768 return(0);

769 }

770

771 /*

772 - regtry - try match at specific point

773 */

774 static int /* 0 failure, 1 success */

775 regtry(prog, string)

776 regexp *prog;

777 char *string;

778 {

779 register int i;

780 register char **sp;

781 register char **ep;

782

783 reginput = string;

784 regstartp = prog->startp;

785 regendp = prog->endp;

786

787 sp = prog->startp;

788 ep = prog->endp;

         for (i = NSUBEXP; i > 0; i--) {

790 *sp++ = NULL;

791 *ep++ = NULL;

792 }

         if (regmatch(prog->program + 1)) {

                 prog->startp[0] = string;

                 prog->endp[0] = reginput;

796 return(1);

797 } else

798 return(0);

799 }

800

801 /*

802 - regmatch - main matching routine

803 *

804 * Conceptually the strategy is simple: check to see whether the current

805 * node matches, call self recursively to see whether the rest matches,

806 * and then act accordingly. In practice we make some effort to avoid

807 * recursion, in particular by going through "ordinary" nodes (that don't

808 * need to know whether the rest of the match failed) by a loop instead of

809 * by recursion.

810 */

811 static int /* 0 failure, 1 success */

812 regmatch(prog)

813 char *prog;

814 {

         register char *scan;    /* Current node. */

816 char *next; /* Next node. */

817 #ifndef IS_LINUX

         extern char *strchr();

819 #endif

820

821 scan = prog;

822 #ifdef DEBUG

         if (scan != NULL && regnarrate)

                 fprintf(stderr, "%s(\n", regprop(scan));

825 #endif

826 while (scan != NULL) {

827 #ifdef DEBUG

828 if (regnarrate)

                         fprintf(stderr, "%s...\n", regprop(scan));

830 #endif

831 next = regnext(scan);

832

                 switch (OP(scan)) {

834 case BOL:

835 if (reginput != regbol)

836 return(0);

837 break;

838 case EOL:

                         if (*reginput != '\0')

840 return(0);

841 break;

842 case ANY:

                         if (*reginput == '\0')

844 return(0);

845 reginput++;

846 break;

847 case EXACTLY: {

848 register int len;

849 register char *opnd;

850

851 opnd = OPERAND(scan);

852 /* Inline the first character, for speed. */

853 if (*opnd != *reginput)

854 return(0);

855 len = strlen(opnd);

                                 if (len > 1 && strncmp(opnd, reginput, len) != 0)

857 return(0);

858 reginput += len;

859 }

860 break;

861 case ANYOF:

                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)

863 return(0);

864 reginput++;

865 break;

866 case ANYBUT:

                         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)

868 return(0);

869 reginput++;

870 break;

871 case NOTHING:

872 break;

873 case BACK:

874 break;

875 case OPEN+1:

876 case OPEN+2:

877 case OPEN+3:

878 case OPEN+4:

879 case OPEN+5:

880 case OPEN+6:

881 case OPEN+7:

882 case OPEN+8:

883 case OPEN+9: {

884 register int no;

885 register char *save;

886

                                 no = OP(scan) - OPEN;

888 save = reginput;

889

                                 if (regmatch(next)) {

891 /*

892 * Don't set startp if some later

893 * invocation of the same parentheses

894 * already has.

895 */

                                         if (regstartp[no] == NULL)

897 regstartp[no] = save;

898 return(1);

899 } else

900 return(0);

901 }

902 /* NOTREACHED */

903 break;

904 case CLOSE+1:

905 case CLOSE+2:

906 case CLOSE+3:

907 case CLOSE+4:

908 case CLOSE+5:

909 case CLOSE+6:

910 case CLOSE+7:

911 case CLOSE+8:

912 case CLOSE+9: {

913 register int no;

914 register char *save;

915

                                 no = OP(scan) - CLOSE;

917 save = reginput;

918

                                 if (regmatch(next)) {

920 /*

921 * Don't set endp if some later

922 * invocation of the same parentheses

923 * already has.

924 */

                                         if (regendp[no] == NULL)

926 regendp[no] = save;

927 return(1);

928 } else

929 return(0);

930 }

931 /* NOTREACHED */

932 break;

933 case BRANCH: {

934 register char *save;

935

                                 if (OP(next) != BRANCH)         /* No choice. */

                                         next = OPERAND(scan);   /* Avoid recursion. */

938 else {

939 do {

940 save = reginput;

                                                 if (regmatch(OPERAND(scan)))

942 return(1);

943 reginput = save;

944 scan = regnext(scan);

                                         } while (scan != NULL && OP(scan) == BRANCH);

946 return(0);

947 /* NOTREACHED */

948 }

949 }

950 /* NOTREACHED */

951 break;

952 case STAR:

953 case PLUS: {

954 register char nextch;

955 register int no;

956 register char *save;

957 register int min;

958

959 /*

960 * Lookahead to avoid useless match attempts

961 * when we know what character comes next.

962 */

963 nextch = '\0';

                                 if (OP(next) == EXACTLY)

965 nextch = *OPERAND(next);

                                 min = (OP(scan) == STAR) ? 0 : 1;

967 save = reginput;

                                 no = regrepeat(OPERAND(scan));

969 while (no >= min) {

970 /* If it could work, try it. */

                                         if (nextch == '\0' || *reginput == nextch)

                                                 if (regmatch(next))

973 return(1);

974 /* Couldn't or didn't -- back up. */

975 no--;

976 reginput = save + no;

977 }

978 return(0);

979 }

980 /* NOTREACHED */

981 break;

982 case END:

                         return(1);      /* Success! */

984 /* NOTREACHED */

985 break;

986 default:

987 regerror("memory corruption");

988 return(0);

989 /* NOTREACHED */

990 break;

991 }

992

993 scan = next;

994 }

995

996 /*

997 * We get here only if there's trouble -- normally "case END" is

998 * the terminating point.

999 */

1000 regerror("corrupted pointers");

1001 return(0);

1002 }

1003

1004 /*

1005 - regrepeat - repeatedly match something simple, report how many

1006 */

1007 static int

1008 regrepeat(p)

1009 char *p;

1010 {

         register int count = 0;

1012 register char *scan;

1013 register char *opnd;

1014

1015 scan = reginput;

1016 opnd = OPERAND(p);

         switch (OP(p)) {

1018 case ANY:

1019 count = strlen(scan);

1020 scan += count;

1021 break;

1022 case EXACTLY:

1023 while (*opnd == *scan) {

1024 count++;

1025 scan++;

1026 }

1027 break;

1028 case ANYOF:

                 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {

1030 count++;

1031 scan++;

1032 }

1033 break;

1034 case ANYBUT:

                 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {

1036 count++;

1037 scan++;

1038 }

1039 break;

1040 default: /* Oh dear. Called inappropriately. */

1041 regerror("internal foulup");

1042 count = 0; /* Best compromise. */

1043 break;

1044 }

1045 reginput = scan;

1046

1047 return(count);

1048 }

1049

1050 /*

1051 - regnext - dig the "next" pointer out of a node

1052 */

1053 static char *

1054 regnext(p)

1055 register char *p;

1056 {

1057 register int offset;

1058

1059 if (p == &regdummy)

1060 return(NULL);

1061

1062 offset = NEXT(p);

         if (offset == 0)

1064 return(NULL);

1065

         if (OP(p) == BACK)

1067 return(p-offset);

1068 else

1069 return(p+offset);

1070 }

1071

1072 #ifdef DEBUG

1073

1074 STATIC char *regprop();

1075

1076 /*

1077 - regdump - dump a regexp onto stdout in vaguely comprehensible form

1078 */

1079 void

1080 regdump(r)

1081 regexp *r;

1082 {

1083 register char *s;

         register char op = EXACTLY;     /* Arbitrary non-END op. */

1085 register char *next;

         extern char *strchr();

1087

1088

         s = r->program + 1;

         while (op != END) {     /* While that wasn't END last time... */

1091 op = OP(s);

                 printf("%2d%s", s-r->program, regprop(s));      /* Where, what. */

1093 next = regnext(s);

                 if (next == NULL)               /* Next ptr. */

1095 printf("(0)");

1096 else

                         printf("(%d)", (s-r->program)+(next-s));

1098 s += 3;

                 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {

1100 /* Literal string, where present. */

                         while (*s != '\0') {

1102 putchar(*s);

1103 s++;

1104 }

1105 s++;

1106 }

                 putchar('\n');

1108 }

1109

1110 /* Header fields of interest. */

         if (r->regstart != '\0')

                 printf("start `%c' ", r->regstart);

1113 if (r->reganch)

1114 printf("anchored ");

         if (r->regmust != NULL)

                 printf("must have \"%s\"", r->regmust);

         printf("\n");

1118 }

1119

1120 /*

1121 - regprop - printable representation of opcode

1122 */

1123 static char *

1124 regprop(op)

1125 char *op;

1126 {

1127 register char *p;

1128 static char buf[50];

1129

         (void) strcpy(buf, ":");

1131

         switch (OP(op)) {

1133 case BOL:

1134 p = "BOL";

1135 break;

1136 case EOL:

1137 p = "EOL";

1138 break;

1139 case ANY:

1140 p = "ANY";

1141 break;

1142 case ANYOF:

1143 p = "ANYOF";

1144 break;

1145 case ANYBUT:

1146 p = "ANYBUT";

1147 break;

1148 case BRANCH:

1149 p = "BRANCH";

1150 break;

1151 case EXACTLY:

1152 p = "EXACTLY";

1153 break;

1154 case NOTHING:

1155 p = "NOTHING";

1156 break;

1157 case BACK:

1158 p = "BACK";

1159 break;

1160 case END:

1161 p = "END";

1162 break;

1163 case OPEN+1:

1164 case OPEN+2:

1165 case OPEN+3:

1166 case OPEN+4:

1167 case OPEN+5:

1168 case OPEN+6:

1169 case OPEN+7:

1170 case OPEN+8:

1171 case OPEN+9:

                 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);

1173 p = NULL;

1174 break;

1175 case CLOSE+1:

1176 case CLOSE+2:

1177 case CLOSE+3:

1178 case CLOSE+4:

1179 case CLOSE+5:

1180 case CLOSE+6:

1181 case CLOSE+7:

1182 case CLOSE+8:

1183 case CLOSE+9:

                 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);

1185 p = NULL;

1186 break;

1187 case STAR:

1188 p = "STAR";

1189 break;

1190 case PLUS:

1191 p = "PLUS";

1192 break;

1193 default:

1194 regerror("corrupted opcode");

1195 break;

1196 }

1197 if (p != NULL)

                 (void) strcat(buf, p);

1199 return(buf);

1200 }

1201 #endif

1202

1203 /*

1204 * The following is provided for those people who do not have strcspn() in

1205 * their C libraries. They should get off their butts and do something

1206 * about it; at least one public-domain implementation of those (highly

1207 * useful) string routines has been published on Usenet.

1208 */

1209 #ifdef STRCSPN

1210 /*

1211 * strcspn - find length of initial segment of s1 consisting entirely

1212 * of characters not from s2

1213 */

1214

1215 static int

1216 strcspn(s1, s2)

1217 char *s1;

1218 char *s2;

1219 {

1220 register char *scan1;

1221 register char *scan2;

1222 register int count;

1223

1224 count = 0;

         for (scan1 = s1; *scan1 != '\0'; scan1++) {

                 for (scan2 = s2; *scan2 != '\0';)       /* ++ moved down. */

1227 if (*scan1 == *scan2++)

1228 return(count);

1229 count++;

1230 }

1231 return(count);

1232 }

1233 #endif