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