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