regexp.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:32k
源码类别:

MySQL数据库

开发平台:

Visual C++

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