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