home *** CD-ROM | disk | FTP | other *** search
/ vim.ftp.fu-berlin.de / 2015-02-03.vim.ftp.fu-berlin.de.tar / vim.ftp.fu-berlin.de / amiga / vim46src.lha / vim-4.6 / src / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-06  |  45.1 KB  |  1,922 lines
  1. /* vi:set 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.  * vim_regcomp and vim_regexec -- vim_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 vim_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@mbfys.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 "option.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 vim_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 vim_regexec() needs it and vim_regcomp() is
  79.  * computing 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 IDENT    14                /* no    Match identifier char */
  118. #define WORD    15                /* no    Match keyword char */
  119. #define FNAME   16                /* no    Match file name char */
  120. #define PRINT    17                /* no    Match printable char */
  121. #define SIDENT    18                /* no    Match identifier char but no digit */
  122. #define SWORD    19                /* no    Match word char but no digit */
  123. #define SFNAME    20                /* no    Match file name char but no digit */
  124. #define SPRINT    21                /* no    Match printable char but no digit */
  125. #define MOPEN    30                /* no    Mark this point in input as start of
  126.                                  *        #n. */
  127.  /* MOPEN+1 is number 1, etc. */
  128. #define MCLOSE    40                /* no    Analogous to MOPEN. */
  129. #define BACKREF    50                /* node Match same string again \1-\9 */
  130.  
  131. #define Magic(x)    ((x)|('\\'<<8))
  132.  
  133. /*
  134.  * Opcode notes:
  135.  *
  136.  * BRANCH        The set of branches constituting a single choice are hooked
  137.  *                together with their "next" pointers, since precedence prevents
  138.  *                anything being concatenated to any individual branch.  The
  139.  *                "next" pointer of the last BRANCH in a choice points to the
  140.  *                thing following the whole choice.  This is also where the
  141.  *                final "next" pointer of each individual branch points; each
  142.  *                branch starts with the operand node of a BRANCH node.
  143.  *
  144.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  145.  *                exists to make loop structures possible.
  146.  *
  147.  * STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
  148.  *                BRANCH structures using BACK.  Simple cases (one character
  149.  *                per match) are implemented with STAR and PLUS for speed
  150.  *                and to minimize recursive plunges.
  151.  *                Note: We would like to use "\?" instead of "\=", but a "\?"
  152.  *                can be part of a pattern to escape the special meaning of '?'
  153.  *                at the end of the pattern in "?pattern?e".
  154.  *
  155.  * MOPEN,MCLOSE    ...are numbered at compile time.
  156.  */
  157.  
  158. /*
  159.  * A node is one char of opcode followed by two chars of "next" pointer.
  160.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  161.  * value is a positive offset from the opcode of the node containing it.
  162.  * An operand, if any, simply follows the node.  (Note that much of the
  163.  * code generation knows about this implicit relationship.)
  164.  *
  165.  * Using two bytes for the "next" pointer is vast overkill for most things,
  166.  * but allows patterns to get big without disasters.
  167.  */
  168. #define OP(p)    (*(p))
  169. #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  170. #define OPERAND(p)        ((p) + 3)
  171.  
  172. /*
  173.  * Utility definitions.
  174.  */
  175. #ifndef CHARBITS
  176. #define UCHARAT(p)        ((int)*(unsigned char *)(p))
  177. #else
  178. #define UCHARAT(p)        ((int)*(p)&CHARBITS)
  179. #endif
  180.  
  181. #define EMSG_RETURN(m) { emsg(m); rc_did_emsg = TRUE; return NULL; }
  182.  
  183. static int ismult __ARGS((int));
  184. static char_u *cstrchr __ARGS((char_u *, int));
  185.  
  186.     static int
  187. ismult(c)
  188.     int c;
  189. {
  190.     return (c == Magic('*') || c == Magic('+') || c == Magic('='));
  191. }
  192.  
  193. /*
  194.  * Flags to be passed up and down.
  195.  */
  196. #define HASWIDTH        01        /* Known never to match null string. */
  197. #define SIMPLE            02        /* Simple enough to be STAR/PLUS operand. */
  198. #define SPSTART         04        /* Starts with * or +. */
  199. #define WORST            0        /* Worst case. */
  200.  
  201. /*
  202.  * The following allows empty REs, meaning "the same as the previous RE".
  203.  * per the ed(1) manual.
  204.  */
  205. /* #define EMPTY_RE */            /* this is done outside of regexp */
  206. #ifdef EMPTY_RE
  207. char_u           *reg_prev_re;
  208. #endif
  209.  
  210. #define TILDE
  211. #ifdef TILDE
  212. char_u           *reg_prev_sub;
  213. #endif
  214.  
  215. /*
  216.  * REGEXP_INRANGE contains all characters which are always special in a []
  217.  * range after '\'.
  218.  * REGEXP_ABBR contains all characters which act as abbreviations after '\'.
  219.  * These are:
  220.  *    \r    - New line (CR).
  221.  *    \t    - Tab (TAB).
  222.  *    \e    - Escape (ESC).
  223.  *    \b    - Backspace (Ctrl('H')).
  224.  */
  225. static char_u REGEXP_INRANGE[] = "]^-\\";
  226. static char_u REGEXP_ABBR[] = "rteb";
  227.  
  228. static int        backslash_trans __ARGS((int c));
  229. static char_u * skip_range __ARGS((char_u *p));
  230.  
  231.     static int
  232. backslash_trans(c)
  233.     int        c;
  234. {
  235.     switch (c)
  236.     {
  237.         case 'r':    return CR;
  238.         case 't':    return TAB;
  239.         case 'e':    return ESC;
  240.         case 'b':    return Ctrl('H');
  241.     }
  242.     return c;
  243. }
  244.  
  245. /*
  246.  * Skip over a "[]" range.
  247.  * "p" must point to the character after the '['.
  248.  * The returned pointer is on the matching ']', or the terminating NUL.
  249.  */
  250.     static char_u *
  251. skip_range(p)
  252.     char_u        *p;
  253. {
  254.     int                cpo_lit;        /* 'cpoptions' contains 'l' flag */
  255.  
  256.     cpo_lit = (vim_strchr(p_cpo, CPO_LITERAL) != NULL);
  257.  
  258.     if (*p == '^')     /* Complement of range. */
  259.         ++p;
  260.     if (*p == ']' || *p == '-')
  261.         ++p;
  262.     while (*p != NUL && *p != ']')
  263.     {
  264.         if (*p == '-')
  265.         {
  266.             ++p;
  267.             if (*p != ']' && *p != '\0')
  268.                 ++p;
  269.         }
  270.         else if (*p == '\\' &&
  271.                  (vim_strchr(REGEXP_INRANGE, p[1]) != NULL ||
  272.                   (!cpo_lit && vim_strchr(REGEXP_ABBR, p[1]) != NULL)))
  273.             p += 2;
  274.         else
  275.             ++p;
  276.     }
  277.  
  278.     return p;
  279. }
  280.  
  281. /*
  282.  * Global work variables for vim_regcomp().
  283.  */
  284.  
  285. static char_u    *regparse;    /* Input-scan pointer. */
  286. static int        regnpar;        /* () count. */
  287. static char_u     regdummy;
  288. static char_u   *regcode;        /* Code-emit pointer; ®dummy = don't. */
  289. static long     regsize;        /* Code size. */
  290. static char_u   **regendp;        /* Ditto for endp. */
  291.  
  292. /*
  293.  * META contains all characters that may be magic, except '^' and '$'.
  294.  * This depends on the configuration options TILDE, BACKREF.
  295.  * (could be done simpler for compilers that know string concatenation)
  296.  */
  297.  
  298. #ifdef TILDE
  299. # ifdef BACKREF
  300.        static char_u META[] = ".[()|=+*<>iIkKfFpP~123456789";
  301. # else
  302.        static char_u META[] = ".[()|=+*<>iIkKfFpP~";
  303. # endif
  304. #else
  305. # ifdef BACKREF
  306.        static char_u META[] = ".[()|=+*<>iIkKfFpP123456789";
  307. # else
  308.        static char_u META[] = ".[()|=+*<>iIkKfFpP";
  309. # endif
  310. #endif
  311.  
  312. /*
  313.  * Forward declarations for vim_regcomp()'s friends.
  314.  */
  315. static void        initchr __ARGS((char_u *));
  316. static int        getchr __ARGS((void));
  317. static int        peekchr __ARGS((void));
  318. #define PeekChr() curchr    /* shortcut only when last action was peekchr() */
  319. static int         curchr;
  320. static void        skipchr __ARGS((void));
  321. static void        ungetchr __ARGS((void));
  322. static char_u    *reg __ARGS((int, int *));
  323. static char_u    *regbranch __ARGS((int *));
  324. static char_u    *regpiece __ARGS((int *));
  325. static char_u    *regatom __ARGS((int *));
  326. static char_u    *regnode __ARGS((int));
  327. static char_u    *regnext __ARGS((char_u *));
  328. static void     regc __ARGS((int));
  329. static void     unregc __ARGS((void));
  330. static void     reginsert __ARGS((int, char_u *));
  331. static void     regtail __ARGS((char_u *, char_u *));
  332. static void     regoptail __ARGS((char_u *, char_u *));
  333.  
  334. #ifndef HAVE_STRCSPN
  335. static size_t    strcspn __ARGS((const char_u *, const char_u *));
  336. #endif
  337.  
  338. /*
  339.  * skip past regular expression
  340.  * stop at end of 'p' of where 'dirc' is found ('/', '?', etc)
  341.  * take care of characters with a backslash in front of it
  342.  * skip strings inside [ and ].
  343.  */
  344.     char_u *
  345. skip_regexp(p, dirc)
  346.     char_u    *p;
  347.     int        dirc;
  348. {
  349.     for (; p[0] != NUL; ++p)
  350.     {
  351.         if (p[0] == dirc)        /* found end of regexp */
  352.             break;
  353.         if ((p[0] == '[' && p_magic) ||
  354.                 (p[0] == '\\' && p[1] == '[' && !p_magic))
  355.             p = skip_range(p + 1);
  356.         else if (p[0] == '\\' && p[1] != NUL)
  357.             ++p;    /* skip next character */
  358.     }
  359.     return p;
  360. }
  361.  
  362. /*
  363.  - vim_regcomp - compile a regular expression into internal code
  364.  *
  365.  * We can't allocate space until we know how big the compiled form will be,
  366.  * but we can't compile it (and thus know how big it is) until we've got a
  367.  * place to put the code.  So we cheat:  we compile it twice, once with code
  368.  * generation turned off and size counting turned on, and once "for real".
  369.  * This also means that we don't allocate space until we are sure that the
  370.  * thing really will compile successfully, and we never have to move the
  371.  * code and thus invalidate pointers into it.  (Note that it has to be in
  372.  * one piece because vim_free() must be able to free it all.)
  373.  *
  374.  * Beware that the optimization-preparation code in here knows about some
  375.  * of the structure of the compiled regexp.
  376.  */
  377.     regexp           *
  378. vim_regcomp(exp)
  379.     char_u           *exp;
  380. {
  381.     register regexp *r;
  382.     register char_u  *scan;
  383.     register char_u  *longest;
  384.     register int    len;
  385.     int             flags;
  386. /*    extern char    *malloc();*/
  387.  
  388.     if (exp == NULL)
  389.         EMSG_RETURN(e_null);
  390.  
  391. #ifdef EMPTY_RE            /* this is done outside of regexp */
  392.     if (*exp == '\0')
  393.     {
  394.         if (reg_prev_re)
  395.             exp = reg_prev_re;
  396.         else
  397.             EMSG_RETURN(e_noprevre);
  398.     }
  399. #endif
  400.  
  401.     /* First pass: determine size, legality. */
  402.     initchr((char_u *)exp);
  403.     regnpar = 1;
  404.     regsize = 0L;
  405.     regcode = ®dummy;
  406.     regendp = NULL;
  407.     regc(MAGIC);
  408.     if (reg(0, &flags) == NULL)
  409.         return NULL;
  410.  
  411.     /* Small enough for pointer-storage convention? */
  412.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  413.         EMSG_RETURN(e_toolong);
  414.  
  415.     /* Allocate space. */
  416. /*    r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
  417.     r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
  418.     if (r == NULL)
  419.         return NULL;
  420.  
  421. #ifdef EMPTY_RE            /* this is done outside of regexp */
  422.     if (exp != reg_prev_re) {
  423.         vim_free(reg_prev_re);
  424.         if (reg_prev_re = alloc(STRLEN(exp) + 1))
  425.             STRCPY(reg_prev_re, exp);
  426.     }
  427. #endif
  428.  
  429.     /* Second pass: emit code. */
  430.     initchr((char_u *)exp);
  431.     regnpar = 1;
  432.     regcode = r->program;
  433.     regendp = r->endp;
  434.     regc(MAGIC);
  435.     if (reg(0, &flags) == NULL) {
  436.         vim_free(r);
  437.         return NULL;
  438.     }
  439.  
  440.     /* Dig out information for optimizations. */
  441.     r->regstart = '\0';         /* Worst-case defaults. */
  442.     r->reganch = 0;
  443.     r->regmust = NULL;
  444.     r->regmlen = 0;
  445.     scan = r->program + 1;        /* First BRANCH. */
  446.     if (OP(regnext(scan)) == END) {     /* Only one top-level choice. */
  447.         scan = OPERAND(scan);
  448.  
  449.         /* Starting-point info. */
  450.         if (OP(scan) == EXACTLY)
  451.             r->regstart = *OPERAND(scan);
  452.         else if (OP(scan) == BOL)
  453.             r->reganch++;
  454.  
  455.         /*
  456.          * If there's something expensive in the r.e., find the longest
  457.          * literal string that must appear and make it the regmust.  Resolve
  458.          * ties in favor of later strings, since the regstart check works
  459.          * with the beginning of the r.e. and avoiding duplication
  460.          * strengthens checking.  Not a strong reason, but sufficient in the
  461.          * absence of others.
  462.          */
  463.         /*
  464.          * When the r.e. starts with BOW, it is faster to look for a regmust
  465.          * first. Used a lot for "#" and "*" commands. (Added by mool).
  466.          */
  467.         if (flags & SPSTART || OP(scan) == BOW) {
  468.             longest = NULL;
  469.             len = 0;
  470.             for (; scan != NULL; scan = regnext(scan))
  471.                 if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len) {
  472.                     longest = OPERAND(scan);
  473.                     len = STRLEN(OPERAND(scan));
  474.                 }
  475.             r->regmust = longest;
  476.             r->regmlen = len;
  477.         }
  478.     }
  479. #ifdef DEBUG
  480.     regdump(r);
  481. #endif
  482.     return r;
  483. }
  484.  
  485. /*
  486.  - reg - regular expression, i.e. main body or parenthesized thing
  487.  *
  488.  * Caller must absorb opening parenthesis.
  489.  *
  490.  * Combining parenthesis handling with the base level of regular expression
  491.  * is a trifle forced, but the need to tie the tails of the branches to what
  492.  * follows makes it hard to avoid.
  493.  */
  494.     static char_u *
  495. reg(paren, flagp)
  496.     int             paren;        /* Parenthesized? */
  497.     int            *flagp;
  498. {
  499.     register char_u  *ret;
  500.     register char_u  *br;
  501.     register char_u  *ender;
  502.     register int    parno = 0;
  503.     int             flags;
  504.  
  505.     *flagp = HASWIDTH;            /* Tentatively. */
  506.  
  507.     /* Make an MOPEN node, if parenthesized. */
  508.     if (paren) {
  509.         if (regnpar >= NSUBEXP)
  510.             EMSG_RETURN(e_toombra);
  511.         parno = regnpar;
  512.         regnpar++;
  513.         ret = regnode(MOPEN + parno);
  514.         if (regendp)
  515.             regendp[parno] = NULL;    /* haven't seen the close paren yet */
  516.     } else
  517.         ret = NULL;
  518.  
  519.     /* Pick up the branches, linking them together. */
  520.     br = regbranch(&flags);
  521.     if (br == NULL)
  522.         return NULL;
  523.     if (ret != NULL)
  524.         regtail(ret, br);        /* MOPEN -> first. */
  525.     else
  526.         ret = br;
  527.     if (!(flags & HASWIDTH))
  528.         *flagp &= ~HASWIDTH;
  529.     *flagp |= flags & SPSTART;
  530.     while (peekchr() == Magic('|')) {
  531.         skipchr();
  532.         br = regbranch(&flags);
  533.         if (br == NULL)
  534.             return NULL;
  535.         regtail(ret, br);        /* BRANCH -> BRANCH. */
  536.         if (!(flags & HASWIDTH))
  537.             *flagp &= ~HASWIDTH;
  538.         *flagp |= flags & SPSTART;
  539.     }
  540.  
  541.     /* Make a closing node, and hook it on the end. */
  542.     ender = regnode((paren) ? MCLOSE + parno : END);
  543.     regtail(ret, ender);
  544.  
  545.     /* Hook the tails of the branches to the closing node. */
  546.     for (br = ret; br != NULL; br = regnext(br))
  547.         regoptail(br, ender);
  548.  
  549.     /* Check for proper termination. */
  550.     if (paren && getchr() != Magic(')'))
  551.         EMSG_RETURN(e_toombra)
  552.     else if (!paren && peekchr() != '\0')
  553.     {
  554.         if (PeekChr() == Magic(')'))
  555.             EMSG_RETURN(e_toomket)
  556.         else
  557.             EMSG_RETURN(e_trailing)        /* "Can't happen". */
  558.         /* NOTREACHED */
  559.     }
  560.     /*
  561.      * Here we set the flag allowing back references to this set of
  562.      * parentheses.
  563.      */
  564.     if (paren && regendp)
  565.         regendp[parno] = ender;    /* have seen the close paren */
  566.     return ret;
  567. }
  568.  
  569. /*
  570.  - regbranch - one alternative of an | operator
  571.  *
  572.  * Implements the concatenation operator.
  573.  */
  574.     static char_u    *
  575. regbranch(flagp)
  576.     int            *flagp;
  577. {
  578.     register char_u  *ret;
  579.     register char_u  *chain;
  580.     register char_u  *latest;
  581.     int             flags;
  582.  
  583.     *flagp = WORST;             /* Tentatively. */
  584.  
  585.     ret = regnode(BRANCH);
  586.     chain = NULL;
  587.     while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) {
  588.         latest = regpiece(&flags);
  589.         if (latest == NULL)
  590.             return NULL;
  591.         *flagp |= flags & HASWIDTH;
  592.         if (chain == NULL)        /* First piece. */
  593.             *flagp |= flags & SPSTART;
  594.         else
  595.             regtail(chain, latest);
  596.         chain = latest;
  597.     }
  598.     if (chain == NULL)            /* Loop ran zero times. */
  599.         (void) regnode(NOTHING);
  600.  
  601.     return ret;
  602. }
  603.  
  604. /*
  605.  - regpiece - something followed by possible [*+=]
  606.  *
  607.  * Note that the branching code sequences used for = and the general cases
  608.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  609.  * both the endmarker for their branch list and the body of the last branch.
  610.  * It might seem that this node could be dispensed with entirely, but the
  611.  * endmarker role is not redundant.
  612.  */
  613. static char_u    *
  614. regpiece(flagp)
  615.     int            *flagp;
  616. {
  617.     register char_u  *ret;
  618.     register int    op;
  619.     register char_u  *next;
  620.     int             flags;
  621.  
  622.     ret = regatom(&flags);
  623.     if (ret == NULL)
  624.         return NULL;
  625.  
  626.     op = peekchr();
  627.     if (!ismult(op)) {
  628.         *flagp = flags;
  629.         return ret;
  630.     }
  631.     if (!(flags & HASWIDTH) && op != Magic('='))
  632.         EMSG_RETURN((char_u *)"*+ operand could be empty");
  633.     *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH);
  634.  
  635.     if (op == Magic('*') && (flags & SIMPLE))
  636.         reginsert(STAR, ret);
  637.     else if (op == Magic('*')) {
  638.         /* Emit x* as (x&|), where & means "self". */
  639.         reginsert(BRANCH, ret); /* Either x */
  640.         regoptail(ret, regnode(BACK));    /* and loop */
  641.         regoptail(ret, ret);    /* back */
  642.         regtail(ret, regnode(BRANCH));    /* or */
  643.         regtail(ret, regnode(NOTHING)); /* null. */
  644.     } else if (op == Magic('+') && (flags & SIMPLE))
  645.         reginsert(PLUS, ret);
  646.     else if (op == Magic('+')) {
  647.         /* Emit x+ as x(&|), where & means "self". */
  648.         next = regnode(BRANCH); /* Either */
  649.         regtail(ret, next);
  650.         regtail(regnode(BACK), ret);    /* loop back */
  651.         regtail(next, regnode(BRANCH)); /* or */
  652.         regtail(ret, regnode(NOTHING)); /* null. */
  653.     } else if (op == Magic('=')) {
  654.         /* Emit x= as (x|) */
  655.         reginsert(BRANCH, ret); /* Either x */
  656.         regtail(ret, regnode(BRANCH));    /* or */
  657.         next = regnode(NOTHING);/* null. */
  658.         regtail(ret, next);
  659.         regoptail(ret, next);
  660.     }
  661.     skipchr();
  662.     if (ismult(peekchr()))
  663.         EMSG_RETURN((char_u *)"Nested *=+");
  664.  
  665.     return ret;
  666. }
  667.  
  668. /*
  669.  - regatom - the lowest level
  670.  *
  671.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  672.  * it can turn them into a single node, which is smaller to store and
  673.  * faster to run.
  674.  */
  675. static char_u    *
  676. regatom(flagp)
  677.     int            *flagp;
  678. {
  679.     register char_u  *ret;
  680.     int             flags;
  681.     int                cpo_lit;        /* 'cpoptions' contains 'l' flag */
  682.  
  683.     *flagp = WORST;             /* Tentatively. */
  684.     cpo_lit = (vim_strchr(p_cpo, CPO_LITERAL) != NULL);
  685.  
  686.     switch (getchr()) {
  687.       case Magic('^'):
  688.         ret = regnode(BOL);
  689.         break;
  690.       case Magic('$'):
  691.         ret = regnode(EOL);
  692.         break;
  693.       case Magic('<'):
  694.         ret = regnode(BOW);
  695.         break;
  696.       case Magic('>'):
  697.         ret = regnode(EOW);
  698.         break;
  699.       case Magic('.'):
  700.         ret = regnode(ANY);
  701.         *flagp |= HASWIDTH | SIMPLE;
  702.         break;
  703.       case Magic('i'):
  704.           ret = regnode(IDENT);
  705.         *flagp |= HASWIDTH | SIMPLE;
  706.         break;
  707.       case Magic('k'):
  708.           ret = regnode(WORD);
  709.         *flagp |= HASWIDTH | SIMPLE;
  710.         break;
  711.       case Magic('I'):
  712.           ret = regnode(SIDENT);
  713.         *flagp |= HASWIDTH | SIMPLE;
  714.         break;
  715.       case Magic('K'):
  716.           ret = regnode(SWORD);
  717.         *flagp |= HASWIDTH | SIMPLE;
  718.         break;
  719.       case Magic('f'):
  720.           ret = regnode(FNAME);
  721.         *flagp |= HASWIDTH | SIMPLE;
  722.         break;
  723.       case Magic('F'):
  724.           ret = regnode(SFNAME);
  725.         *flagp |= HASWIDTH | SIMPLE;
  726.         break;
  727.       case Magic('p'):
  728.           ret = regnode(PRINT);
  729.         *flagp |= HASWIDTH | SIMPLE;
  730.         break;
  731.       case Magic('P'):
  732.           ret = regnode(SPRINT);
  733.         *flagp |= HASWIDTH | SIMPLE;
  734.         break;
  735.       case Magic('('):
  736.         ret = reg(1, &flags);
  737.         if (ret == NULL)
  738.             return NULL;
  739.         *flagp |= flags & (HASWIDTH | SPSTART);
  740.         break;
  741.       case '\0':
  742.       case Magic('|'):
  743.       case Magic(')'):
  744.         EMSG_RETURN(e_internal)        /* Supposed to be caught earlier. */
  745.         /* NOTREACHED */
  746.       case Magic('='):
  747.         EMSG_RETURN((char_u *)"\\= follows nothing")
  748.         /* NOTREACHED */
  749.       case Magic('+'):
  750.         EMSG_RETURN((char_u *)"\\+ follows nothing")
  751.         /* NOTREACHED */
  752.       case Magic('*'):
  753.         if (reg_magic)
  754.             EMSG_RETURN((char_u *)"* follows nothing")
  755.         else
  756.             EMSG_RETURN((char_u *)"\\* follows nothing")
  757.         /* break; Not Reached */
  758. #ifdef TILDE
  759.       case Magic('~'):            /* previous substitute pattern */
  760.             if (reg_prev_sub) {
  761.                 register char_u *p;
  762.  
  763.                 ret = regnode(EXACTLY);
  764.                 p = reg_prev_sub;
  765.                 while (*p) {
  766.                     regc(*p++);
  767.                 }
  768.                 regc('\0');
  769.                 if (p - reg_prev_sub) {
  770.                     *flagp |= HASWIDTH;
  771.                     if ((p - reg_prev_sub) == 1)
  772.                         *flagp |= SIMPLE;
  773.                 }
  774.               } else
  775.                 EMSG_RETURN(e_nopresub);
  776.             break;
  777. #endif
  778. #ifdef BACKREF
  779.       case Magic('1'):
  780.       case Magic('2'):
  781.       case Magic('3'):
  782.       case Magic('4'):
  783.       case Magic('5'):
  784.       case Magic('6'):
  785.       case Magic('7'):
  786.       case Magic('8'):
  787.       case Magic('9'): {
  788.             int                refnum;
  789.  
  790.             ungetchr();
  791.             refnum = getchr() - Magic('0');
  792.             /*
  793.              * Check if the back reference is legal. We use the parentheses
  794.              * pointers to mark encountered close parentheses, but this
  795.              * is only available in the second pass. Checking opens is
  796.              * always possible.
  797.              * Should also check that we don't refer to something that
  798.              * is repeated (+*=): what instance of the repetition should
  799.              * we match? TODO.
  800.              */
  801.             if (refnum < regnpar &&
  802.                 (regendp == NULL || regendp[refnum] != NULL))
  803.                 ret = regnode(BACKREF + refnum);
  804.             else
  805.                 EMSG_RETURN((char_u *)"Illegal back reference");
  806.         }
  807.         break;
  808. #endif
  809.       case Magic('['):
  810.         {
  811.             char_u         *p;
  812.  
  813.             /*
  814.              * If there is no matching ']', we assume the '[' is a normal
  815.              * character. This makes ":help [" work.
  816.              */
  817.             p = skip_range(regparse);
  818.             if (*p == ']')        /* there is a matching ']' */
  819.             {
  820.                 /*
  821.                  * In a character class, different parsing rules apply.
  822.                  * Not even \ is special anymore, nothing is.
  823.                  */
  824.                 if (*regparse == '^') {     /* Complement of range. */
  825.                     ret = regnode(ANYBUT);
  826.                     regparse++;
  827.                 } else
  828.                     ret = regnode(ANYOF);
  829.                 if (*regparse == ']' || *regparse == '-')
  830.                     regc(*regparse++);
  831.                 while (*regparse != '\0' && *regparse != ']')
  832.                 {
  833.                     if (*regparse == '-') {
  834.                         regparse++;
  835.                         if (*regparse == ']' || *regparse == '\0')
  836.                             regc('-');
  837.                         else {
  838.                             register int    cclass;
  839.                             register int    cclassend;
  840.  
  841.                             cclass = UCHARAT(regparse - 2) + 1;
  842.                             cclassend = UCHARAT(regparse);
  843.                             if (cclass > cclassend + 1)
  844.                                 EMSG_RETURN(e_invrange);
  845.                             for (; cclass <= cclassend; cclass++)
  846.                                 regc(cclass);
  847.                             regparse++;
  848.                         }
  849.                     }
  850.  
  851.                     /*
  852.                      * Only "\]", "\^", "\]" and "\\" are special in Vi.  Vim
  853.                      * accepts "\t", "\e", etc., but only when the 'l' flag in
  854.                      * 'cpoptions' is not included.
  855.                      */
  856.                     else if (*regparse == '\\' &&
  857.                             (vim_strchr(REGEXP_INRANGE, regparse[1]) != NULL ||
  858.                              (!cpo_lit &&
  859.                                vim_strchr(REGEXP_ABBR, regparse[1]) != NULL)))
  860.                     {
  861.                         regparse++;
  862.                         regc(backslash_trans(*regparse++));
  863.                     } else
  864.                         regc(*regparse++);
  865.                 }
  866.                 regc('\0');
  867.                 if (*regparse != ']')
  868.                     EMSG_RETURN(e_toomsbra);
  869.                 skipchr();            /* let's be friends with the lexer again */
  870.                 *flagp |= HASWIDTH | SIMPLE;
  871.                 break;
  872.             }
  873.         }
  874.         /* FALLTHROUGH */
  875.  
  876.       default:
  877.         {
  878.             register int    len;
  879.             int                chr;
  880.  
  881.             ungetchr();
  882.             len = 0;
  883.             ret = regnode(EXACTLY);
  884.             /*
  885.              * Always take at least one character, for '[' without matching
  886.              * ']'.
  887.              */
  888.             while ((chr = peekchr()) != '\0' && (chr < Magic(0) || len == 0))
  889.             {
  890.                 regc(chr);
  891.                 skipchr();
  892.                 len++;
  893.             }
  894. #ifdef DEBUG
  895.             if (len == 0)
  896.                  EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
  897. #endif
  898.             /*
  899.              * If there is a following *, \+ or \= we need the character
  900.              * in front of it as a single character operand
  901.              */
  902.             if (len > 1 && ismult(chr))
  903.             {
  904.                 unregc();            /* Back off of *+= operand */
  905.                 ungetchr();            /* and put it back for next time */
  906.                 --len;
  907.             }
  908.             regc('\0');
  909.             *flagp |= HASWIDTH;
  910.             if (len == 1)
  911.                 *flagp |= SIMPLE;
  912.         }
  913.         break;
  914.     }
  915.  
  916.     return ret;
  917. }
  918.  
  919. /*
  920.  - regnode - emit a node
  921.  */
  922. static char_u    *                /* Location. */
  923. regnode(op)
  924.     int            op;
  925. {
  926.     register char_u  *ret;
  927.     register char_u  *ptr;
  928.  
  929.     ret = regcode;
  930.     if (ret == ®dummy) {
  931.         regsize += 3;
  932.         return ret;
  933.     }
  934.     ptr = ret;
  935.     *ptr++ = op;
  936.     *ptr++ = '\0';                /* Null "next" pointer. */
  937.     *ptr++ = '\0';
  938.     regcode = ptr;
  939.  
  940.     return ret;
  941. }
  942.  
  943. /*
  944.  - regc - emit (if appropriate) a byte of code
  945.  */
  946. static void
  947. regc(b)
  948.     int            b;
  949. {
  950.     if (regcode != ®dummy)
  951.         *regcode++ = b;
  952.     else
  953.         regsize++;
  954. }
  955.  
  956. /*
  957.  - unregc - take back (if appropriate) a byte of code
  958.  */
  959. static void
  960. unregc()
  961. {
  962.     if (regcode != ®dummy)
  963.         regcode--;
  964.     else
  965.         regsize--;
  966. }
  967.  
  968. /*
  969.  - reginsert - insert an operator in front of already-emitted operand
  970.  *
  971.  * Means relocating the operand.
  972.  */
  973. static void
  974. reginsert(op, opnd)
  975.     int            op;
  976.     char_u           *opnd;
  977. {
  978.     register char_u  *src;
  979.     register char_u  *dst;
  980.     register char_u  *place;
  981.  
  982.     if (regcode == ®dummy) {
  983.         regsize += 3;
  984.         return;
  985.     }
  986.     src = regcode;
  987.     regcode += 3;
  988.     dst = regcode;
  989.     while (src > opnd)
  990.         *--dst = *--src;
  991.  
  992.     place = opnd;                /* Op node, where operand used to be. */
  993.     *place++ = op;
  994.     *place++ = '\0';
  995.     *place = '\0';
  996. }
  997.  
  998. /*
  999.  - regtail - set the next-pointer at the end of a node chain
  1000.  */
  1001. static void
  1002. regtail(p, val)
  1003.     char_u           *p;
  1004.     char_u           *val;
  1005. {
  1006.     register char_u  *scan;
  1007.     register char_u  *temp;
  1008.     register int    offset;
  1009.  
  1010.     if (p == ®dummy)
  1011.         return;
  1012.  
  1013.     /* Find last node. */
  1014.     scan = p;
  1015.     for (;;) {
  1016.         temp = regnext(scan);
  1017.         if (temp == NULL)
  1018.             break;
  1019.         scan = temp;
  1020.     }
  1021.  
  1022.     if (OP(scan) == BACK)
  1023.         offset = (int)(scan - val);
  1024.     else
  1025.         offset = (int)(val - scan);
  1026.     *(scan + 1) = (char_u) ((offset >> 8) & 0377);
  1027.     *(scan + 2) = (char_u) (offset & 0377);
  1028. }
  1029.  
  1030. /*
  1031.  - regoptail - regtail on operand of first argument; nop if operandless
  1032.  */
  1033. static void
  1034. regoptail(p, val)
  1035.     char_u           *p;
  1036.     char_u           *val;
  1037. {
  1038.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  1039.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  1040.         return;
  1041.     regtail(OPERAND(p), val);
  1042. }
  1043.  
  1044. /*
  1045.  - getchr() - get the next character from the pattern. We know about
  1046.  * magic and such, so therefore we need a lexical analyzer.
  1047.  */
  1048.  
  1049. /* static int        curchr; */
  1050. static int        prevchr;
  1051. static int        nextchr;    /* used for ungetchr() */
  1052. /*
  1053.  * Note: prevchr is sometimes -1 when we are not at the start,
  1054.  * eg in /[ ^I]^ the pattern was never found even if it existed, because ^ was
  1055.  * taken to be magic -- webb
  1056.  */
  1057. static int        at_start;    /* True when we are on the first character */
  1058.  
  1059. static void
  1060. initchr(str)
  1061. char_u *str;
  1062. {
  1063.     regparse = str;
  1064.     curchr = prevchr = nextchr = -1;
  1065.     at_start = TRUE;
  1066. }
  1067.  
  1068. static int
  1069. peekchr()
  1070. {
  1071.     if (curchr < 0) {
  1072.         switch (curchr = regparse[0]) {
  1073.         case '.':
  1074.     /*    case '+':*/
  1075.     /*    case '=':*/
  1076.         case '[':
  1077.         case '~':
  1078.             if (reg_magic)
  1079.                 curchr = Magic(curchr);
  1080.             break;
  1081.         case '*':
  1082.             /* * is not magic as the very first character, eg "?*ptr" */
  1083.             if (reg_magic && !at_start)
  1084.                 curchr = Magic('*');
  1085.             break;
  1086.         case '^':
  1087.             /* ^ is only magic as the very first character */
  1088.             if (at_start)
  1089.                 curchr = Magic('^');
  1090.             break;
  1091.         case '$':
  1092.             /* $ is only magic as the very last character and in front of '\|' */
  1093.             if (regparse[1] == NUL || (regparse[1] == '\\' && regparse[2] == '|'))
  1094.                 curchr = Magic('$');
  1095.             break;
  1096.         case '\\':
  1097.             regparse++;
  1098.             if (regparse[0] == NUL)
  1099.             {
  1100.                 curchr = '\\';    /* trailing '\' */
  1101.                 --regparse;        /* there is no extra character to skip */
  1102.             }
  1103.             else if (vim_strchr(META, regparse[0]))
  1104.             {
  1105.                 /*
  1106.                  * META contains everything that may be magic sometimes, except
  1107.                  * ^ and $ ("\^" and "\$" are never magic).
  1108.                  * We now fetch the next character and toggle its magicness.
  1109.                  * Therefore, \ is so meta-magic that it is not in META.
  1110.                  */
  1111.                 curchr = -1;
  1112.                 at_start = FALSE;            /* We still want to be able to say "/\*ptr" */
  1113.                 peekchr();
  1114.                 curchr ^= Magic(0);
  1115.             }
  1116.             else if (vim_strchr(REGEXP_ABBR, regparse[0]))
  1117.             {
  1118.                 /*
  1119.                  * Handle abbreviations, like "\t" for TAB -- webb
  1120.                  */
  1121.                 curchr = backslash_trans(regparse[0]);
  1122.             }
  1123.             else
  1124.             {
  1125.                 /*
  1126.                  * Next character can never be (made) magic?
  1127.                  * Then backslashing it won't do anything.
  1128.                  */
  1129.                 curchr = regparse[0];
  1130.             }
  1131.             break;
  1132.         }
  1133.     }
  1134.  
  1135.     return curchr;
  1136. }
  1137.  
  1138. static void
  1139. skipchr()
  1140. {
  1141.     regparse++;
  1142.     at_start = FALSE;
  1143.     prevchr = curchr;
  1144.     curchr = nextchr;        /* use previously unget char, or -1 */
  1145.     nextchr = -1;
  1146. }
  1147.  
  1148. static int
  1149. getchr()
  1150. {
  1151.     int chr;
  1152.  
  1153.     chr = peekchr();
  1154.     skipchr();
  1155.  
  1156.     return chr;
  1157. }
  1158.  
  1159. /*
  1160.  * put character back. Works only once!
  1161.  */
  1162. static void
  1163. ungetchr()
  1164. {
  1165.     nextchr = curchr;
  1166.     curchr = prevchr;
  1167.     /*
  1168.      * Backup regparse as well; not because we will use what it points at,
  1169.      * but because skipchr() will bump it again.
  1170.      */
  1171.     regparse--;
  1172. }
  1173.  
  1174. /*
  1175.  * vim_regexec and friends
  1176.  */
  1177.  
  1178. /*
  1179.  * Global work variables for vim_regexec().
  1180.  */
  1181. static char_u    *reginput;        /* String-input pointer. */
  1182. static char_u    *regbol;         /* Beginning of input, for ^ check. */
  1183. static char_u   **regstartp;        /* Pointer to startp array. */
  1184. /* static char_u   **regendp;    */    /* Ditto for endp. */
  1185.  
  1186. /*
  1187.  * Forwards.
  1188.  */
  1189. static int        regtry __ARGS((regexp *, char_u *));
  1190. static int        regmatch __ARGS((char_u *));
  1191. static int        regrepeat __ARGS((char_u *));
  1192.  
  1193. #ifdef DEBUG
  1194. int             regnarrate = 1;
  1195. void            regdump __ARGS((regexp *));
  1196. static char_u    *regprop __ARGS((char_u *));
  1197. #endif
  1198.  
  1199. /*
  1200.  * vim_regexec - match a regexp against a string
  1201.  * Return non-zero if there is a match.
  1202.  */
  1203. int
  1204. vim_regexec(prog, string, at_bol)
  1205.     register regexp *prog;
  1206.     register char_u  *string;
  1207.     int             at_bol;
  1208. {
  1209.     register char_u  *s;
  1210.  
  1211.     /* Be paranoid... */
  1212.     if (prog == NULL || string == NULL) {
  1213.         emsg(e_null);
  1214.         rc_did_emsg = TRUE;
  1215.         return 0;
  1216.     }
  1217.     /* Check validity of program. */
  1218.     if (UCHARAT(prog->program) != MAGIC) {
  1219.         emsg(e_re_corr);
  1220.         rc_did_emsg = TRUE;
  1221.         return 0;
  1222.     }
  1223.     /* If there is a "must appear" string, look for it. */
  1224.     if (prog->regmust != NULL) {
  1225.         s = string;
  1226.         while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
  1227.             if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
  1228.                 break;            /* Found it. */
  1229.             s++;
  1230.         }
  1231.         if (s == NULL)            /* Not present. */
  1232.             return 0;
  1233.     }
  1234.     /* Mark beginning of line for ^ . */
  1235.     if (at_bol)
  1236.         regbol = string;        /* is possible to match bol */
  1237.     else
  1238.         regbol = NULL;            /* we aren't there, so don't match it */
  1239.  
  1240.     /* Simplest case:  anchored match need be tried only once. */
  1241.     if (prog->reganch)
  1242.         return regtry(prog, string);
  1243.  
  1244.     /* Messy cases:  unanchored match. */
  1245.     s = string;
  1246.     if (prog->regstart != '\0')
  1247.         /* We know what char it must start with. */
  1248.         while ((s = cstrchr(s, prog->regstart)) != NULL) {
  1249.             if (regtry(prog, s))
  1250.                 return 1;
  1251.             s++;
  1252.         }
  1253.     else
  1254.         /* We don't -- general case. */
  1255.         do {
  1256.             if (regtry(prog, s))
  1257.                 return 1;
  1258.         } while (*s++ != '\0');
  1259.  
  1260.     /* Failure. */
  1261.     return 0;
  1262. }
  1263.  
  1264. /*
  1265.  - regtry - try match at specific point
  1266.  */
  1267. static int                        /* 0 failure, 1 success */
  1268. regtry(prog, string)
  1269.     regexp           *prog;
  1270.     char_u           *string;
  1271. {
  1272.     register int    i;
  1273.     register char_u **sp;
  1274.     register char_u **ep;
  1275.  
  1276.     reginput = string;
  1277.     regstartp = prog->startp;
  1278.     regendp = prog->endp;
  1279.  
  1280.     sp = prog->startp;
  1281.     ep = prog->endp;
  1282.     for (i = NSUBEXP; i > 0; i--) {
  1283.         *sp++ = NULL;
  1284.         *ep++ = NULL;
  1285.     }
  1286.     if (regmatch(prog->program + 1)) {
  1287.         prog->startp[0] = string;
  1288.         prog->endp[0] = reginput;
  1289.         return 1;
  1290.     } else
  1291.         return 0;
  1292. }
  1293.  
  1294. /*
  1295.  - regmatch - main matching routine
  1296.  *
  1297.  * Conceptually the strategy is simple:  check to see whether the current
  1298.  * node matches, call self recursively to see whether the rest matches,
  1299.  * and then act accordingly.  In practice we make some effort to avoid
  1300.  * recursion, in particular by going through "ordinary" nodes (that don't
  1301.  * need to know whether the rest of the match failed) by a loop instead of
  1302.  * by recursion.
  1303.  */
  1304. static int                        /* 0 failure, 1 success */
  1305. regmatch(prog)
  1306.     char_u           *prog;
  1307. {
  1308.     register char_u  *scan;        /* Current node. */
  1309.     char_u           *next;        /* Next node. */
  1310.  
  1311.     scan = prog;
  1312. #ifdef DEBUG
  1313.     if (scan != NULL && regnarrate)
  1314.         fprintf(stderr, "%s(\n", regprop(scan));
  1315. #endif
  1316.     while (scan != NULL) {
  1317. #ifdef DEBUG
  1318.         if (regnarrate) {
  1319.             fprintf(stderr, "%s...\n", regprop(scan));
  1320.         }
  1321. #endif
  1322.         next = regnext(scan);
  1323.         switch (OP(scan)) {
  1324.           case BOL:
  1325.             if (reginput != regbol)
  1326.                 return 0;
  1327.             break;
  1328.           case EOL:
  1329.             if (*reginput != '\0')
  1330.                 return 0;
  1331.             break;
  1332.           case BOW:        /* \<word; reginput points to w */
  1333.               if (reginput != regbol && iswordchar(reginput[-1]))
  1334.                 return 0;
  1335.               if (!reginput[0] || !iswordchar(reginput[0]))
  1336.                 return 0;
  1337.             break;
  1338.           case EOW:        /* word\>; reginput points after d */
  1339.               if (reginput == regbol || !iswordchar(reginput[-1]))
  1340.                 return 0;
  1341.               if (reginput[0] && iswordchar(reginput[0]))
  1342.                 return 0;
  1343.             break;
  1344.           case ANY:
  1345.             if (*reginput == '\0')
  1346.                 return 0;
  1347.             reginput++;
  1348.             break;
  1349.           case IDENT:
  1350.               if (!isidchar(*reginput))
  1351.                 return 0;
  1352.             reginput++;
  1353.             break;
  1354.           case WORD:
  1355.               if (!iswordchar(*reginput))
  1356.                 return 0;
  1357.             reginput++;
  1358.             break;
  1359.           case FNAME:
  1360.               if (!isfilechar(*reginput))
  1361.                 return 0;
  1362.             reginput++;
  1363.             break;
  1364.           case PRINT:
  1365.               if (charsize(*reginput) != 1)
  1366.                 return 0;
  1367.             reginput++;
  1368.             break;
  1369.           case SIDENT:
  1370.               if (isdigit(*reginput) || !isidchar(*reginput))
  1371.                 return 0;
  1372.             reginput++;
  1373.             break;
  1374.           case SWORD:
  1375.               if (isdigit(*reginput) || !iswordchar(*reginput))
  1376.                 return 0;
  1377.             reginput++;
  1378.             break;
  1379.           case SFNAME:
  1380.               if (isdigit(*reginput) || !isfilechar(*reginput))
  1381.                 return 0;
  1382.             reginput++;
  1383.             break;
  1384.           case SPRINT:
  1385.               if (isdigit(*reginput) || charsize(*reginput) != 1)
  1386.                 return 0;
  1387.             reginput++;
  1388.             break;
  1389.           case EXACTLY:{
  1390.                 register int    len;
  1391.                 register char_u  *opnd;
  1392.  
  1393.                 opnd = OPERAND(scan);
  1394.                 /* Inline the first character, for speed. */
  1395.                 if (*opnd != *reginput && (!reg_ic || TO_UPPER(*opnd) != TO_UPPER(*reginput)))
  1396.                     return 0;
  1397.                 len = STRLEN(opnd);
  1398.                 if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
  1399.                     return 0;
  1400.                 reginput += len;
  1401.             }
  1402.             break;
  1403.           case ANYOF:
  1404.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
  1405.                 return 0;
  1406.             reginput++;
  1407.             break;
  1408.           case ANYBUT:
  1409.             if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
  1410.                 return 0;
  1411.             reginput++;
  1412.             break;
  1413.           case NOTHING:
  1414.             break;
  1415.           case BACK:
  1416.             break;
  1417.           case MOPEN + 1:
  1418.           case MOPEN + 2:
  1419.           case MOPEN + 3:
  1420.           case MOPEN + 4:
  1421.           case MOPEN + 5:
  1422.           case MOPEN + 6:
  1423.           case MOPEN + 7:
  1424.           case MOPEN + 8:
  1425.           case MOPEN + 9:{
  1426.                 register int    no;
  1427.                 register char_u  *save;
  1428.  
  1429.                 no = OP(scan) - MOPEN;
  1430.                 save = regstartp[no];
  1431.                 regstartp[no] = reginput; /* Tentatively */
  1432. #ifdef DEBUG
  1433.                 printf("MOPEN  %d pre  @'%s' ('%s' )'%s'\n",
  1434.                     no, save,
  1435.                     regstartp[no] ? regstartp[no] : "NULL",
  1436.                     regendp[no] ? regendp[no] : "NULL");
  1437. #endif
  1438.  
  1439.                 if (regmatch(next)) {
  1440. #ifdef DEBUG
  1441.                 printf("MOPEN  %d post @'%s' ('%s' )'%s'\n",
  1442.                     no, save,
  1443.                     regstartp[no] ? regstartp[no] : "NULL",
  1444.                     regendp[no] ? regendp[no] : "NULL");
  1445. #endif
  1446.                     return 1;
  1447.                 }
  1448.                 regstartp[no] = save;        /* We were wrong... */
  1449.                 return 0;
  1450.             }
  1451.             /* break; Not Reached */
  1452.           case MCLOSE + 1:
  1453.           case MCLOSE + 2:
  1454.           case MCLOSE + 3:
  1455.           case MCLOSE + 4:
  1456.           case MCLOSE + 5:
  1457.           case MCLOSE + 6:
  1458.           case MCLOSE + 7:
  1459.           case MCLOSE + 8:
  1460.           case MCLOSE + 9:{
  1461.                 register int    no;
  1462.                 register char_u  *save;
  1463.  
  1464.                 no = OP(scan) - MCLOSE;
  1465.                 save = regendp[no];
  1466.                 regendp[no] = reginput; /* Tentatively */
  1467. #ifdef DEBUG
  1468.                 printf("MCLOSE %d pre  @'%s' ('%s' )'%s'\n",
  1469.                     no, save,
  1470.                     regstartp[no] ? regstartp[no] : "NULL",
  1471.                     regendp[no] ? regendp[no] : "NULL");
  1472. #endif
  1473.  
  1474.                 if (regmatch(next)) {
  1475. #ifdef DEBUG
  1476.                 printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
  1477.                     no, save,
  1478.                     regstartp[no] ? regstartp[no] : "NULL",
  1479.                     regendp[no] ? regendp[no] : "NULL");
  1480. #endif
  1481.                     return 1;
  1482.                 }
  1483.                 regendp[no] = save;        /* We were wrong... */
  1484.                 return 0;
  1485.             }
  1486.             /* break; Not Reached */
  1487. #ifdef BACKREF
  1488.           case BACKREF + 1:
  1489.           case BACKREF + 2:
  1490.           case BACKREF + 3:
  1491.           case BACKREF + 4:
  1492.           case BACKREF + 5:
  1493.           case BACKREF + 6:
  1494.           case BACKREF + 7:
  1495.           case BACKREF + 8:
  1496.           case BACKREF + 9:{
  1497.                 register int    no;
  1498.                 int                len;
  1499.  
  1500.                 no = OP(scan) - BACKREF;
  1501.                 if (regendp[no] != NULL) {
  1502.                     len = (int)(regendp[no] - regstartp[no]);
  1503.                     if (cstrncmp(regstartp[no], reginput, len) != 0)
  1504.                         return 0;
  1505.                     reginput += len;
  1506.                 } else {
  1507.                     /*emsg("backref to 0-repeat");*/
  1508.                     /*return 0;*/
  1509.                 }
  1510.               }
  1511.             break;
  1512. #endif
  1513.           case BRANCH:{
  1514.                 register char_u  *save;
  1515.  
  1516.                 if (OP(next) != BRANCH) /* No choice. */
  1517.                     next = OPERAND(scan);        /* Avoid recursion. */
  1518.                 else {
  1519.                     do {
  1520.                         save = reginput;
  1521.                         if (regmatch(OPERAND(scan)))
  1522.                             return 1;
  1523.                         reginput = save;
  1524.                         scan = regnext(scan);
  1525.                     } while (scan != NULL && OP(scan) == BRANCH);
  1526.                     return 0;
  1527.                     /* NOTREACHED */
  1528.                 }
  1529.             }
  1530.             break;
  1531.           case STAR:
  1532.           case PLUS:{
  1533.                 register int    nextch;
  1534.                 register int    no;
  1535.                 register char_u  *save;
  1536.                 register int    min;
  1537.  
  1538.                 /*
  1539.                  * Lookahead to avoid useless match attempts when we know
  1540.                  * what character comes next.
  1541.                  */
  1542.                 nextch = '\0';
  1543.                 if (OP(next) == EXACTLY)
  1544.                 {
  1545.                     nextch = *OPERAND(next);
  1546.                     if (reg_ic)
  1547.                         nextch = TO_UPPER(nextch);
  1548.                 }
  1549.                 min = (OP(scan) == STAR) ? 0 : 1;
  1550.                 save = reginput;
  1551.                 no = regrepeat(OPERAND(scan));
  1552.                 while (no >= min)
  1553.                 {
  1554.                     /* If it could work, try it. */
  1555.                     if (nextch == '\0' || (*reginput == nextch ||
  1556.                                     (reg_ic && TO_UPPER(*reginput) == nextch)))
  1557.                         if (regmatch(next))
  1558.                             return 1;
  1559.                     /* Couldn't or didn't -- back up. */
  1560.                     no--;
  1561.                     reginput = save + no;
  1562.                 }
  1563.                 return 0;
  1564.             }
  1565.             /* break; Not Reached */
  1566.           case END:
  1567.             return 1;         /* Success! */
  1568.             /* break; Not Reached */
  1569.           default:
  1570.             emsg(e_re_corr);
  1571.             return 0;
  1572.             /* break; Not Reached */
  1573.         }
  1574.  
  1575.         scan = next;
  1576.     }
  1577.  
  1578.     /*
  1579.      * We get here only if there's trouble -- normally "case END" is the
  1580.      * terminating point.
  1581.      */
  1582.     emsg(e_re_corr);
  1583.     return 0;
  1584. }
  1585.  
  1586. /*
  1587.  - regrepeat - repeatedly match something simple, report how many
  1588.  */
  1589. static int
  1590. regrepeat(p)
  1591.     char_u           *p;
  1592. {
  1593.     register int    count = 0;
  1594.     register char_u  *scan;
  1595.     register char_u  *opnd;
  1596.  
  1597.     scan = reginput;
  1598.     opnd = OPERAND(p);
  1599.     switch (OP(p)) {
  1600.       case ANY:
  1601.         count = STRLEN(scan);
  1602.         scan += count;
  1603.         break;
  1604.       case IDENT:
  1605.         for (count = 0; isidchar(*scan); ++count)
  1606.             ++scan;
  1607.         break;
  1608.       case WORD:
  1609.         for (count = 0; iswordchar(*scan); ++count)
  1610.             ++scan;
  1611.         break;
  1612.       case FNAME:
  1613.         for (count = 0; isfilechar(*scan); ++count)
  1614.             ++scan;
  1615.         break;
  1616.       case PRINT:
  1617.         for (count = 0; charsize(*scan) == 1; ++count)
  1618.             ++scan;
  1619.         break;
  1620.       case SIDENT:
  1621.         for (count = 0; !isdigit(*scan) && isidchar(*scan); ++count)
  1622.             ++scan;
  1623.         break;
  1624.       case SWORD:
  1625.         for (count = 0; !isdigit(*scan) && iswordchar(*scan); ++count)
  1626.             ++scan;
  1627.         break;
  1628.       case SFNAME:
  1629.         for (count = 0; !isdigit(*scan) && isfilechar(*scan); ++count)
  1630.             ++scan;
  1631.         break;
  1632.       case SPRINT:
  1633.         for (count = 0; !isdigit(*scan) && charsize(*scan) == 1; ++count)
  1634.             ++scan;
  1635.         break;
  1636.       case EXACTLY:
  1637.         while (*opnd == *scan || (reg_ic && TO_UPPER(*opnd) == TO_UPPER(*scan)))
  1638.         {
  1639.             count++;
  1640.             scan++;
  1641.         }
  1642.         break;
  1643.       case ANYOF:
  1644.         while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
  1645.         {
  1646.             count++;
  1647.             scan++;
  1648.         }
  1649.         break;
  1650.       case ANYBUT:
  1651.         while (*scan != '\0' && cstrchr(opnd, *scan) == NULL) {
  1652.             count++;
  1653.             scan++;
  1654.         }
  1655.         break;
  1656.       default:                    /* Oh dear.  Called inappropriately. */
  1657.         emsg(e_re_corr);
  1658.         count = 0;                /* Best compromise. */
  1659.         break;
  1660.     }
  1661.     reginput = scan;
  1662.  
  1663.     return count;
  1664. }
  1665.  
  1666. /*
  1667.  - regnext - dig the "next" pointer out of a node
  1668.  */
  1669. static char_u    *
  1670. regnext(p)
  1671.     register char_u  *p;
  1672. {
  1673.     register int    offset;
  1674.  
  1675.     if (p == ®dummy)
  1676.         return NULL;
  1677.  
  1678.     offset = NEXT(p);
  1679.     if (offset == 0)
  1680.         return NULL;
  1681.  
  1682.     if (OP(p) == BACK)
  1683.         return p - offset;
  1684.     else
  1685.         return p + offset;
  1686. }
  1687.  
  1688. #ifdef DEBUG
  1689.  
  1690. /*
  1691.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1692.  */
  1693. void
  1694. regdump(r)
  1695.     regexp           *r;
  1696. {
  1697.     register char_u  *s;
  1698.     register int    op = EXACTLY;        /* Arbitrary non-END op. */
  1699.     register char_u  *next;
  1700.  
  1701.  
  1702.     s = r->program + 1;
  1703.     while (op != END) {         /* While that wasn't END last time... */
  1704.         op = OP(s);
  1705.         printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1706.         next = regnext(s);
  1707.         if (next == NULL)        /* Next ptr. */
  1708.             printf("(0)");
  1709.         else
  1710.             printf("(%d)", (s - r->program) + (next - s));
  1711.         s += 3;
  1712.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1713.             /* Literal string, where present. */
  1714.             while (*s != '\0') {
  1715.                 putchar(*s);
  1716.                 s++;
  1717.             }
  1718.             s++;
  1719.         }
  1720.         putchar('\n');
  1721.     }
  1722.  
  1723.     /* Header fields of interest. */
  1724.     if (r->regstart != '\0')
  1725.         printf("start `%c' ", r->regstart);
  1726.     if (r->reganch)
  1727.         printf("anchored ");
  1728.     if (r->regmust != NULL)
  1729.         printf("must have \"%s\"", r->regmust);
  1730.     printf("\n");
  1731. }
  1732.  
  1733. /*
  1734.  - regprop - printable representation of opcode
  1735.  */
  1736. static char_u    *
  1737. regprop(op)
  1738.     char_u           *op;
  1739. {
  1740.     register char_u  *p;
  1741.     static char_u     buf[50];
  1742.  
  1743.     (void) strcpy(buf, ":");
  1744.  
  1745.     switch (OP(op)) {
  1746.       case BOL:
  1747.         p = "BOL";
  1748.         break;
  1749.       case EOL:
  1750.         p = "EOL";
  1751.         break;
  1752.       case ANY:
  1753.         p = "ANY";
  1754.         break;
  1755.       case IDENT:
  1756.           p = "IDENT";
  1757.         break;
  1758.       case WORD:
  1759.           p = "WORD";
  1760.         break;
  1761.       case FNAME:
  1762.           p = "FNAME";
  1763.         break;
  1764.       case PRINT:
  1765.           p = "PRINT";
  1766.         break;
  1767.       case SIDENT:
  1768.           p = "SIDENT";
  1769.         break;
  1770.       case SWORD:
  1771.           p = "SWORD";
  1772.         break;
  1773.       case SFNAME:
  1774.           p = "SFNAME";
  1775.         break;
  1776.       case SPRINT:
  1777.           p = "SPRINT";
  1778.         break;
  1779.       case ANYOF:
  1780.         p = "ANYOF";
  1781.         break;
  1782.       case ANYBUT:
  1783.         p = "ANYBUT";
  1784.         break;
  1785.       case BRANCH:
  1786.         p = "BRANCH";
  1787.         break;
  1788.       case EXACTLY:
  1789.         p = "EXACTLY";
  1790.         break;
  1791.       case NOTHING:
  1792.         p = "NOTHING";
  1793.         break;
  1794.       case BACK:
  1795.         p = "BACK";
  1796.         break;
  1797.       case END:
  1798.         p = "END";
  1799.         break;
  1800.       case MOPEN + 1:
  1801.       case MOPEN + 2:
  1802.       case MOPEN + 3:
  1803.       case MOPEN + 4:
  1804.       case MOPEN + 5:
  1805.       case MOPEN + 6:
  1806.       case MOPEN + 7:
  1807.       case MOPEN + 8:
  1808.       case MOPEN + 9:
  1809.         sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
  1810.         p = NULL;
  1811.         break;
  1812.       case MCLOSE + 1:
  1813.       case MCLOSE + 2:
  1814.       case MCLOSE + 3:
  1815.       case MCLOSE + 4:
  1816.       case MCLOSE + 5:
  1817.       case MCLOSE + 6:
  1818.       case MCLOSE + 7:
  1819.       case MCLOSE + 8:
  1820.       case MCLOSE + 9:
  1821.         sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
  1822.         p = NULL;
  1823.         break;
  1824.       case BACKREF + 1:
  1825.       case BACKREF + 2:
  1826.       case BACKREF + 3:
  1827.       case BACKREF + 4:
  1828.       case BACKREF + 5:
  1829.       case BACKREF + 6:
  1830.       case BACKREF + 7:
  1831.       case BACKREF + 8:
  1832.       case BACKREF + 9:
  1833.         sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
  1834.         p = NULL;
  1835.         break;
  1836.       case STAR:
  1837.         p = "STAR";
  1838.         break;
  1839.       case PLUS:
  1840.         p = "PLUS";
  1841.         break;
  1842.       default:
  1843.         sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
  1844.         p = NULL;
  1845.         break;
  1846.     }
  1847.     if (p != NULL)
  1848.         (void) strcat(buf, p);
  1849.     return buf;
  1850. }
  1851. #endif
  1852.  
  1853. /*
  1854.  * The following is provided for those people who do not have strcspn() in
  1855.  * their C libraries.  They should get off their butts and do something
  1856.  * about it; at least one public-domain implementation of those (highly
  1857.  * useful) string routines has been published on Usenet.
  1858.  */
  1859. #ifndef HAVE_STRCSPN
  1860. /*
  1861.  * strcspn - find length of initial segment of s1 consisting entirely
  1862.  * of characters not from s2
  1863.  */
  1864.  
  1865.     static size_t
  1866. strcspn(s1, s2)
  1867.     const char_u           *s1;
  1868.     const char_u           *s2;
  1869. {
  1870.     register char_u  *scan1;
  1871.     register char_u  *scan2;
  1872.     register int    count;
  1873.  
  1874.     count = 0;
  1875.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1876.         for (scan2 = s2; *scan2 != '\0';)        /* ++ moved down. */
  1877.             if (*scan1 == *scan2++)
  1878.                 return count;
  1879.         count++;
  1880.     }
  1881.     return count;
  1882. }
  1883. #endif
  1884.  
  1885. /*
  1886.  * Compare two strings, ignore case if reg_ic set.
  1887.  * Return 0 if strings match, non-zero otherwise.
  1888.  */
  1889.     int
  1890. cstrncmp(s1, s2, n)
  1891.     char_u           *s1, *s2;
  1892.     int             n;
  1893. {
  1894.     if (!reg_ic)
  1895.         return STRNCMP(s1, s2, (size_t)n);
  1896.  
  1897.     return vim_strnicmp(s1, s2, (size_t)n);
  1898. }
  1899.  
  1900. /*
  1901.  * cstrchr: This function is used a lot for simple searches, keep it fast!
  1902.  */
  1903.     static char_u *
  1904. cstrchr(s, c)
  1905.     char_u           *s;
  1906.     register int    c;
  1907. {
  1908.     register char_u           *p;
  1909.  
  1910.     if (!reg_ic)
  1911.         return vim_strchr(s, c);
  1912.  
  1913.     c = TO_UPPER(c);
  1914.  
  1915.     for (p = s; *p; p++)
  1916.     {
  1917.         if (TO_UPPER(*p) == c)
  1918.             return p;
  1919.     }
  1920.     return NULL;
  1921. }
  1922.