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