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