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