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