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