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