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