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