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