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