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