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