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