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