Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume44/vim/part11

Internet Message Format | 1994-08-16 | 68.2 KB

From: [e-mail] (Bram Moolenaar)
Newsgroups: comp.sources.misc
Subject: v44i030:  vim - Vi IMproved editor, v3.0, Part11/26
Date: 16 Aug 1994 21:18:18 -0500
Organization: Sterling Software
Sender: [e-mail]
Approved: [e-mail]
Message-ID: <32rs1a$[e-mail]>
X-Md4-Signature: 1d36337d58b209ff5cc0f9e9bdd3a745

Submitted-by: [e-mail] (Bram Moolenaar)
Posting-number: Volume 44, Issue 30
Archive-name: vim/part11
Environment: UNIX, AMIGA, MS-DOS, Windows NT
Supersedes: vim: Volume 41, Issue 50-75

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# Contents:  vim/src/regexp.c vim/src/undo.c
# Wrapped by kent@sparky on Mon Aug 15 21:44:05 1994
PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin:$PATH ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 11 (of 26)."'
if test -f 'vim/src/regexp.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'vim/src/regexp.c'\"
else
  echo shar: Extracting \"'vim/src/regexp.c'\" \(40070 characters\)
  sed "s/^X//" >'vim/src/regexp.c' <<'END_OF_FILE'
X/* vi:ts=4:sw=4
X * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
X *
X * This is NOT the original regular expression code as written by
X * Henry Spencer. This code has been modified specifically for use
X * with the VIM editor, and should not be used apart from compiling
X * VIM. If you want a good regular expression library, get the
X * original code. The copyright notice that follows is from the
X * original.
X *
X * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
X *
X *
X * regcomp and regexec -- regsub and regerror are elsewhere
X *
X *        Copyright (c) 1986 by University of Toronto.
X *        Written by Henry Spencer.  Not derived from licensed software.
X *
X *        Permission is granted to anyone to use this software for any
X *        purpose on any computer system, and to redistribute it freely,
X *        subject to the following restrictions:
X *
X *        1. The author is not responsible for the consequences of use of
X *                this software, no matter how awful, even if they arise
X *                from defects in it.
X *
X *        2. The origin of this software must not be misrepresented, either
X *                by explicit claim or by omission.
X *
X *        3. Altered versions must be plainly marked as such, and must not
X *                be misrepresented as being the original software.
X *
X * Beware that some of this code is subtly aware of the way operator
X * precedence is structured in regular expressions.  Serious changes in
X * regular-expression syntax might require a total rethink.
X *
X * $Log:        regexp.c,v $
X * Revision 1.2  88/04/28  08:09:45  tony
X * First modification of the regexp library. Added an external variable
X * 'reg_ic' which can be set to indicate that case should be ignored.
X * Added a new parameter to regexec() to indicate that the given string
X * comes from the beginning of a line and is thus eligible to match
X * 'beginning-of-line'.
X *
X * Revisions by Olaf 'Rhialto' Seibert, [e-mail]:
X * Changes for vi: (the semantics of several things were rather different)
X * - Added lexical analyzer, because in vi magicness of characters
X *   is rather difficult, and may change over time.
X * - Added support for \< \> \1-\9 and ~
X * - Left some magic stuff in, but only backslashed: \| \+
X * - * and \+ still work after \) even though they shouldn't.
X */
X#include "vim.h"
X#include "globals.h"
X#include "proto.h"
X#undef DEBUG
X
X#include <stdio.h>
X#include "regexp.h"
X#include "regmagic.h"
X#include "param.h"
X
X/*
X * The "internal use only" fields in regexp.h are present to pass info from
X * compile to execute that permits the execute phase to run lots faster on
X * simple cases.  They are:
X *
X * regstart     char that must begin a match; '\0' if none obvious
X * reganch        is the match anchored (at beginning-of-line only)?
X * regmust        string (pointer into program) that match must include, or NULL
X * regmlen        length of regmust string
X *
X * Regstart and reganch permit very fast decisions on suitable starting points
X * for a match, cutting down the work a lot.  Regmust permits fast rejection
X * of lines that cannot possibly match.  The regmust tests are costly enough
X * that regcomp() supplies a regmust only if the r.e. contains something
X * potentially expensive (at present, the only such thing detected is * or +
X * at the start of the r.e., which can involve a lot of backup).  Regmlen is
X * supplied because the test in regexec() needs it and regcomp() is computing
X * it anyway.
X */
X
X/*
X * Structure for regexp "program".    This is essentially a linear encoding
X * of a nondeterministic finite-state machine (aka syntax charts or
X * "railroad normal form" in parsing technology).  Each node is an opcode
X * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
X * all nodes except BRANCH implement concatenation; a "next" pointer with
X * a BRANCH on both ends of it is connecting two alternatives.    (Here we
X * have one of the subtle syntax dependencies:    an individual BRANCH (as
X * opposed to a collection of them) is never concatenated with anything
X * because of operator precedence.)  The operand of some types of node is
X * a literal string; for others, it is a node leading into a sub-FSM.  In
X * particular, the operand of a BRANCH node is the first node of the branch.
X * (NB this is *not* a tree structure:    the tail of the branch connects
X * to the thing following the set of BRANCHes.)  The opcodes are:
X */
X
X/* definition    number               opnd?    meaning */
X#define END     0                /* no    End of program. */
X#define BOL     1                /* no    Match "" at beginning of line. */
X#define EOL     2                /* no    Match "" at end of line. */
X#define ANY     3                /* no    Match any one character. */
X#define ANYOF    4                /* str    Match any character in this string. */
X#define ANYBUT    5                /* str    Match any character not in this
X                                 *        string. */
X#define BRANCH    6                /* node Match this alternative, or the
X                                 *        next... */
X#define BACK    7                /* no    Match "", "next" ptr points backward. */
X#define EXACTLY 8                /* str    Match this string. */
X#define NOTHING 9                /* no    Match empty string. */
X#define STAR    10                /* node Match this (simple) thing 0 or more
X                                 *        times. */
X#define PLUS    11                /* node Match this (simple) thing 1 or more
X                                 *        times. */
X#define BOW        12                /* no    Match "" after [^a-zA-Z0-9_] */
X#define EOW        13                /* no    Match "" at    [^a-zA-Z0-9_] */
X#define MOPEN    20                /* no    Mark this point in input as start of
X                                 *        #n. */
X /* MOPEN+1 is number 1, etc. */
X#define MCLOSE    30                /* no    Analogous to MOPEN. */
X#define BACKREF    40                /* node Match same string again \1-\9 */
X
X#define Magic(x)    ((x)|('\\'<<8))
X
X/*
X * Opcode notes:
X *
X * BRANCH        The set of branches constituting a single choice are hooked
X *                together with their "next" pointers, since precedence prevents
X *                anything being concatenated to any individual branch.  The
X *                "next" pointer of the last BRANCH in a choice points to the
X *                thing following the whole choice.  This is also where the
X *                final "next" pointer of each individual branch points; each
X *                branch starts with the operand node of a BRANCH node.
X *
X * BACK         Normal "next" pointers all implicitly point forward; BACK
X *                exists to make loop structures possible.
X *
X * STAR,PLUS    '=', and complex '*' and '+', are implemented as circular
X *                BRANCH structures using BACK.  Simple cases (one character
X *                per match) are implemented with STAR and PLUS for speed
X *                and to minimize recursive plunges.
X *
X * MOPEN,MCLOSE    ...are numbered at compile time.
X */
X
X/*
X * A node is one char of opcode followed by two chars of "next" pointer.
X * "Next" pointers are stored as two 8-bit pieces, high order first.  The
X * value is a positive offset from the opcode of the node containing it.
X * An operand, if any, simply follows the node.  (Note that much of the
X * code generation knows about this implicit relationship.)
X *
X * Using two bytes for the "next" pointer is vast overkill for most things,
X * but allows patterns to get big without disasters.
X */
X#define OP(p)    (*(p))
X#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
X#define OPERAND(p)        ((p) + 3)
X
X/*
X * See regmagic.h for one further detail of program structure.
X */
X
X
X/*
X * Utility definitions.
X */
X#ifndef CHARBITS
X#define UCHARAT(p)        ((int)*(unsigned char *)(p))
X#else
X#define UCHARAT(p)        ((int)*(p)&CHARBITS)
X#endif
X
X#define EMSG_RETURN(m) { emsg(m); return NULL; }
X
Xstatic int ismult __ARGS((int));
X
X    static int
Xismult(c)
X    int c;
X{
X    return (c == Magic('*') || c == Magic('+') || c == Magic('='));
X}
X
X/*
X * Flags to be passed up and down.
X */
X#define HASWIDTH        01        /* Known never to match null string. */
X#define SIMPLE            02        /* Simple enough to be STAR/PLUS operand. */
X#define SPSTART         04        /* Starts with * or +. */
X#define WORST            0        /* Worst case. */
X
X/*
X * The following allows empty REs, meaning "the same as the previous RE".
X * per the ed(1) manual.
X */
X/* #define EMPTY_RE */            /* this is done outside of regexp */
X#ifdef EMPTY_RE
Xchar_u           *reg_prev_re;
X#endif
X
X#define TILDE
X#ifdef TILDE
Xchar_u           *reg_prev_sub;
X#endif
X
X/*
X * This if for vi's "magic" mode. If magic is false, only ^$\ are magic.
X */
X
Xint                reg_magic = 1;
X
X/*
X * Global work variables for regcomp().
X */
X
Xstatic char_u    *regparse;    /* Input-scan pointer. */
Xstatic int        regnpar;        /* () count. */
Xstatic char_u     regdummy;
Xstatic char_u   *regcode;        /* Code-emit pointer; ®dummy = don't. */
Xstatic long     regsize;        /* Code size. */
Xstatic char_u   **regendp;        /* Ditto for endp. */
X
X/*
X * META contains all characters that may be magic, except '^' and '$'.
X * This depends on the configuration options TILDE, BACKREF.
X * (could be done simpler for compilers that know string concatenation)
X */
X
X#ifdef TILDE
X# ifdef BACKREF
X       static char_u META[] = ".[()|=+*<>~123456789";
X# else
X       static char_u META[] = ".[()|=+*<>~";
X# endif
X#else
X# ifdef BACKREF
X       static char_u META[] = ".[()|=+*<>123456789";
X# else
X       static char_u META[] = ".[()|=+*<>";
X# endif
X#endif
X
X/*
X * Forward declarations for regcomp()'s friends.
X */
Xstatic void        initchr __ARGS((char_u *));
Xstatic int        getchr __ARGS((void));
Xstatic int        peekchr __ARGS((void));
X#define PeekChr() curchr    /* shortcut only when last action was peekchr() */
Xstatic int         curchr;
Xstatic void        skipchr __ARGS((void));
Xstatic void        ungetchr __ARGS((void));
Xstatic char_u    *reg __ARGS((int, int *));
Xstatic char_u    *regbranch __ARGS((int *));
Xstatic char_u    *regpiece __ARGS((int *));
Xstatic char_u    *regatom __ARGS((int *));
Xstatic char_u    *regnode __ARGS((int));
Xstatic char_u    *regnext __ARGS((char_u *));
Xstatic void     regc __ARGS((int));
Xstatic void     unregc __ARGS((void));
Xstatic void     reginsert __ARGS((int, char_u *));
Xstatic void     regtail __ARGS((char_u *, char_u *));
Xstatic void     regoptail __ARGS((char_u *, char_u *));
X
X#undef STRCSPN
X#ifdef STRCSPN
Xstatic int        strcspn __ARGS((const char_u *, const char_u *));
X#endif
X
X/*
X * skip past regular expression
X * stop at end of 'p' of where 'dirc' is found ('/', '?', etc)
X * take care of characters with a backslash in front of it
X * skip strings inside [ and ].
X */
X    char_u *
Xskip_regexp(p, dirc)
X    char_u    *p;
X    int        dirc;
X{
X    int        in_range = FALSE;
X
X    for (; p[0] != NUL; ++p)
X    {
X        if (p[0] == dirc && !in_range)        /* found end of regexp */
X            break;
X        if ((p[0] == '[' && p_magic) || (p[0] == '\\' && p[1] == '[' && !p_magic))
X        {
X            in_range = TRUE;
X            if (p[0] == '\\')
X                ++p;
X                                /* "[^]" and "[]" are not the end of a range */
X            if (p[1] == '^')
X                ++p;
X            if (p[1] == ']')
X                ++p;
X        }
X        else if (p[0] == '\\' && p[1] != NUL)
X            ++p;    /* skip next character */
X        else if (p[0] == ']')
X            in_range = FALSE;
X    }
X    return p;
X}
X
X/*
X - regcomp - compile a regular expression into internal code
X *
X * We can't allocate space until we know how big the compiled form will be,
X * but we can't compile it (and thus know how big it is) until we've got a
X * place to put the code.  So we cheat:  we compile it twice, once with code
X * generation turned off and size counting turned on, and once "for real".
X * This also means that we don't allocate space until we are sure that the
X * thing really will compile successfully, and we never have to move the
X * code and thus invalidate pointers into it.  (Note that it has to be in
X * one piece because free() must be able to free it all.)
X *
X * Beware that the optimization-preparation code in here knows about some
X * of the structure of the compiled regexp.
X */
X    regexp           *
Xregcomp(exp)
X    char_u           *exp;
X{
X    register regexp *r;
X    register char_u  *scan;
X    register char_u  *longest;
X    register int    len;
X    int             flags;
X/*    extern char    *malloc();*/
X
X    if (exp == NULL) {
X        EMSG_RETURN(e_null);
X    }
X
X#ifdef EMPTY_RE            /* this is done outside of regexp */
X    if (*exp == '\0') {
X        if (reg_prev_re) {
X            exp = reg_prev_re;
X        } else {
X            EMSG_RETURN(e_noprevre);
X        }
X    }
X#endif
X
X    /* First pass: determine size, legality. */
X    initchr((char_u *)exp);
X    regnpar = 1;
X    regsize = 0L;
X    regcode = ®dummy;
X    regendp = NULL;
X    regc(MAGIC);
X    if (reg(0, &flags) == NULL)
X        return NULL;
X
X    /* Small enough for pointer-storage convention? */
X    if (regsize >= 32767L)        /* Probably could be 65535L. */
X        EMSG_RETURN(e_toolong);
X
X    /* Allocate space. */
X/*    r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
X    r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
X    if (r == NULL)
X        EMSG_RETURN(e_outofmem);
X
X#ifdef EMPTY_RE            /* this is done outside of regexp */
X    if (exp != reg_prev_re) {
X        free(reg_prev_re);
X        if (reg_prev_re = alloc(STRLEN(exp) + 1))
X            STRCPY(reg_prev_re, exp);
X    }
X#endif
X
X    /* Second pass: emit code. */
X    initchr((char_u *)exp);
X    regnpar = 1;
X    regcode = r->program;
X    regendp = r->endp;
X    regc(MAGIC);
X    if (reg(0, &flags) == NULL) {
X        free(r);
X        return NULL;
X    }
X
X    /* Dig out information for optimizations. */
X    r->regstart = '\0';         /* Worst-case defaults. */
X    r->reganch = 0;
X    r->regmust = NULL;
X    r->regmlen = 0;
X    scan = r->program + 1;        /* First BRANCH. */
X    if (OP(regnext(scan)) == END) {     /* Only one top-level choice. */
X        scan = OPERAND(scan);
X
X        /* Starting-point info. */
X        if (OP(scan) == EXACTLY)
X            r->regstart = *OPERAND(scan);
X        else if (OP(scan) == BOL)
X            r->reganch++;
X
X        /*
X         * If there's something expensive in the r.e., find the longest
X         * literal string that must appear and make it the regmust.  Resolve
X         * ties in favor of later strings, since the regstart check works
X         * with the beginning of the r.e. and avoiding duplication
X         * strengthens checking.  Not a strong reason, but sufficient in the
X         * absence of others.
X         */
X        /*
X         * When the r.e. starts with BOW, it is faster to look for a regmust
X         * first. Used a lot for "#" and "*" commands. (Added by mool).
X         */
X        if (flags & SPSTART || OP(scan) == BOW) {
X            longest = NULL;
X            len = 0;
X            for (; scan != NULL; scan = regnext(scan))
X                if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len) {
X                    longest = OPERAND(scan);
X                    len = STRLEN(OPERAND(scan));
X                }
X            r->regmust = longest;
X            r->regmlen = len;
X        }
X    }
X#ifdef DEBUG
X    regdump(r);
X#endif
X    return r;
X}
X
X/*
X - reg - regular expression, i.e. main body or parenthesized thing
X *
X * Caller must absorb opening parenthesis.
X *
X * Combining parenthesis handling with the base level of regular expression
X * is a trifle forced, but the need to tie the tails of the branches to what
X * follows makes it hard to avoid.
X */
X    static char_u *
Xreg(paren, flagp)
X    int             paren;        /* Parenthesized? */
X    int            *flagp;
X{
X    register char_u  *ret;
X    register char_u  *br;
X    register char_u  *ender;
X    register int    parno = 0;
X    int             flags;
X
X    *flagp = HASWIDTH;            /* Tentatively. */
X
X    /* Make an MOPEN node, if parenthesized. */
X    if (paren) {
X        if (regnpar >= NSUBEXP)
X            EMSG_RETURN(e_toombra);
X        parno = regnpar;
X        regnpar++;
X        ret = regnode(MOPEN + parno);
X        if (regendp)
X            regendp[parno] = NULL;    /* haven't seen the close paren yet */
X    } else
X        ret = NULL;
X
X    /* Pick up the branches, linking them together. */
X    br = regbranch(&flags);
X    if (br == NULL)
X        return NULL;
X    if (ret != NULL)
X        regtail(ret, br);        /* MOPEN -> first. */
X    else
X        ret = br;
X    if (!(flags & HASWIDTH))
X        *flagp &= ~HASWIDTH;
X    *flagp |= flags & SPSTART;
X    while (peekchr() == Magic('|')) {
X        skipchr();
X        br = regbranch(&flags);
X        if (br == NULL)
X            return NULL;
X        regtail(ret, br);        /* BRANCH -> BRANCH. */
X        if (!(flags & HASWIDTH))
X            *flagp &= ~HASWIDTH;
X        *flagp |= flags & SPSTART;
X    }
X
X    /* Make a closing node, and hook it on the end. */
X    ender = regnode((paren) ? MCLOSE + parno : END);
X    regtail(ret, ender);
X
X    /* Hook the tails of the branches to the closing node. */
X    for (br = ret; br != NULL; br = regnext(br))
X        regoptail(br, ender);
X
X    /* Check for proper termination. */
X    if (paren && getchr() != Magic(')')) {
X        EMSG_RETURN(e_toombra);
X    } else if (!paren && peekchr() != '\0') {
X        if (PeekChr() == Magic(')')) {
X            EMSG_RETURN(e_toomket);
X        } else
X            EMSG_RETURN(e_trailing);/* "Can't happen". */
X        /* NOTREACHED */
X    }
X    /*
X     * Here we set the flag allowing back references to this set of
X     * parentheses.
X     */
X    if (paren && regendp)
X        regendp[parno] = ender;    /* have seen the close paren */
X    return ret;
X}
X
X/*
X - regbranch - one alternative of an | operator
X *
X * Implements the concatenation operator.
X */
X    static char_u    *
Xregbranch(flagp)
X    int            *flagp;
X{
X    register char_u  *ret;
X    register char_u  *chain;
X    register char_u  *latest;
X    int             flags;
X
X    *flagp = WORST;             /* Tentatively. */
X
X    ret = regnode(BRANCH);
X    chain = NULL;
X    while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) {
X        latest = regpiece(&flags);
X        if (latest == NULL)
X            return NULL;
X        *flagp |= flags & HASWIDTH;
X        if (chain == NULL)        /* First piece. */
X            *flagp |= flags & SPSTART;
X        else
X            regtail(chain, latest);
X        chain = latest;
X    }
X    if (chain == NULL)            /* Loop ran zero times. */
X        (void) regnode(NOTHING);
X
X    return ret;
X}
X
X/*
X - regpiece - something followed by possible [*+=]
X *
X * Note that the branching code sequences used for = and the general cases
X * of * and + are somewhat optimized:  they use the same NOTHING node as
X * both the endmarker for their branch list and the body of the last branch.
X * It might seem that this node could be dispensed with entirely, but the
X * endmarker role is not redundant.
X */
Xstatic char_u    *
Xregpiece(flagp)
X    int            *flagp;
X{
X    register char_u  *ret;
X    register int    op;
X    register char_u  *next;
X    int             flags;
X
X    ret = regatom(&flags);
X    if (ret == NULL)
X        return NULL;
X
X    op = peekchr();
X    if (!ismult(op)) {
X        *flagp = flags;
X        return ret;
X    }
X    if (!(flags & HASWIDTH) && op != Magic('='))
X        EMSG_RETURN((char_u *)"*+ operand could be empty");
X    *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH);
X
X    if (op == Magic('*') && (flags & SIMPLE))
X        reginsert(STAR, ret);
X    else if (op == Magic('*')) {
X        /* Emit x* as (x&|), where & means "self". */
X        reginsert(BRANCH, ret); /* Either x */
X        regoptail(ret, regnode(BACK));    /* and loop */
X        regoptail(ret, ret);    /* back */
X        regtail(ret, regnode(BRANCH));    /* or */
X        regtail(ret, regnode(NOTHING)); /* null. */
X    } else if (op == Magic('+') && (flags & SIMPLE))
X        reginsert(PLUS, ret);
X    else if (op == Magic('+')) {
X        /* Emit x+ as x(&|), where & means "self". */
X        next = regnode(BRANCH); /* Either */
X        regtail(ret, next);
X        regtail(regnode(BACK), ret);    /* loop back */
X        regtail(next, regnode(BRANCH)); /* or */
X        regtail(ret, regnode(NOTHING)); /* null. */
X    } else if (op == Magic('=')) {
X        /* Emit x= as (x|) */
X        reginsert(BRANCH, ret); /* Either x */
X        regtail(ret, regnode(BRANCH));    /* or */
X        next = regnode(NOTHING);/* null. */
X        regtail(ret, next);
X        regoptail(ret, next);
X    }
X    skipchr();
X    if (ismult(peekchr()))
X        EMSG_RETURN((char_u *)"Nested *=+");
X
X    return ret;
X}
X
X/*
X - regatom - the lowest level
X *
X * Optimization:  gobbles an entire sequence of ordinary characters so that
X * it can turn them into a single node, which is smaller to store and
X * faster to run.
X */
Xstatic char_u    *
Xregatom(flagp)
X    int            *flagp;
X{
X    register char_u  *ret;
X    int             flags;
X
X    *flagp = WORST;             /* Tentatively. */
X
X    switch (getchr()) {
X      case Magic('^'):
X        ret = regnode(BOL);
X        break;
X      case Magic('$'):
X        ret = regnode(EOL);
X        break;
X      case Magic('<'):
X        ret = regnode(BOW);
X        break;
X      case Magic('>'):
X        ret = regnode(EOW);
X        break;
X      case Magic('.'):
X        ret = regnode(ANY);
X        *flagp |= HASWIDTH | SIMPLE;
X        break;
X      case Magic('['):{
X            /*
X             * In a character class, different parsing rules apply.
X             * Not even \ is special anymore, nothing is.
X             */
X            if (*regparse == '^') {     /* Complement of range. */
X                ret = regnode(ANYBUT);
X                regparse++;
X            } else
X                ret = regnode(ANYOF);
X            if (*regparse == ']' || *regparse == '-')
X                regc(*regparse++);
X            while (*regparse != '\0' && *regparse != ']') {
X                if (*regparse == '-') {
X                    regparse++;
X                    if (*regparse == ']' || *regparse == '\0')
X                        regc('-');
X                    else {
X                        register int    class;
X                        register int    classend;
X
X                        class = UCHARAT(regparse - 2) + 1;
X                        classend = UCHARAT(regparse);
X                        if (class > classend + 1)
X                            EMSG_RETURN(e_invrange);
X                        for (; class <= classend; class++)
X                            regc(class);
X                        regparse++;
X                    }
X                } else if (*regparse == '\\' && regparse[1]) {
X                    regparse++;
X                    regc(*regparse++);
X                } else
X                    regc(*regparse++);
X            }
X            regc('\0');
X            if (*regparse != ']')
X                EMSG_RETURN(e_toomsbra);
X            skipchr();            /* let's be friends with the lexer again */
X            *flagp |= HASWIDTH | SIMPLE;
X        }
X        break;
X      case Magic('('):
X        ret = reg(1, &flags);
X        if (ret == NULL)
X            return NULL;
X        *flagp |= flags & (HASWIDTH | SPSTART);
X        break;
X      case '\0':
X      case Magic('|'):
X      case Magic(')'):
X        EMSG_RETURN(e_internal);    /* Supposed to be caught earlier. */
X        /* break; Not Reached */
X      case Magic('='):
X      case Magic('+'):
X      case Magic('*'):
X        EMSG_RETURN((char_u *)"=+* follows nothing");
X        /* break; Not Reached */
X#ifdef TILDE
X      case Magic('~'):            /* previous substitute pattern */
X            if (reg_prev_sub) {
X                register char_u *p;
X
X                ret = regnode(EXACTLY);
X                p = reg_prev_sub;
X                while (*p) {
X                    regc(*p++);
X                }
X                regc('\0');
X                if (p - reg_prev_sub) {
X                    *flagp |= HASWIDTH;
X                    if ((p - reg_prev_sub) == 1)
X                        *flagp |= SIMPLE;
X                }
X              } else
X                EMSG_RETURN(e_nopresub);
X            break;
X#endif
X#ifdef BACKREF
X      case Magic('1'):
X      case Magic('2'):
X      case Magic('3'):
X      case Magic('4'):
X      case Magic('5'):
X      case Magic('6'):
X      case Magic('7'):
X      case Magic('8'):
X      case Magic('9'): {
X            int                refnum;
X
X            ungetchr();
X            refnum = getchr() - Magic('0');
X            /*
X             * Check if the back reference is legal. We use the parentheses
X             * pointers to mark encountered close parentheses, but this
X             * is only available in the second pass. Checking opens is
X             * always possible.
X             * Should also check that we don't refer to something that
X             * is repeated (+*=): what instance of the repetition should
X             * we match? TODO.
X             */
X            if (refnum < regnpar &&
X                (regendp == NULL || regendp[refnum] != NULL))
X                ret = regnode(BACKREF + refnum);
X            else
X                EMSG_RETURN((char_u *)"Illegal back reference");
X        }
X        break;
X#endif
X      default:{
X            register int    len;
X            int                chr;
X
X            ungetchr();
X            len = 0;
X            ret = regnode(EXACTLY);
X            while ((chr = peekchr()) != '\0' && (chr < Magic(0)))
X            {
X                regc(chr);
X                skipchr();
X                len++;
X            }
X#ifdef DEBUG
X            if (len == 0)
X                 EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
X#endif
X            /*
X             * If there is a following *, \+ or \= we need the character
X             * in front of it as a single character operand
X             */
X            if (len > 1 && ismult(chr))
X            {
X                unregc();            /* Back off of *+= operand */
X                ungetchr();            /* and put it back for next time */
X                --len;
X            }
X            regc('\0');
X            *flagp |= HASWIDTH;
X            if (len == 1)
X                *flagp |= SIMPLE;
X        }
X        break;
X    }
X
X    return ret;
X}
X
X/*
X - regnode - emit a node
X */
Xstatic char_u    *                /* Location. */
Xregnode(op)
X    int            op;
X{
X    register char_u  *ret;
X    register char_u  *ptr;
X
X    ret = regcode;
X    if (ret == ®dummy) {
X        regsize += 3;
X        return ret;
X    }
X    ptr = ret;
X    *ptr++ = op;
X    *ptr++ = '\0';                /* Null "next" pointer. */
X    *ptr++ = '\0';
X    regcode = ptr;
X
X    return ret;
X}
X
X/*
X - regc - emit (if appropriate) a byte of code
X */
Xstatic void
Xregc(b)
X    int            b;
X{
X    if (regcode != ®dummy)
X        *regcode++ = b;
X    else
X        regsize++;
X}
X
X/*
X - unregc - take back (if appropriate) a byte of code
X */
Xstatic void
Xunregc()
X{
X    if (regcode != ®dummy)
X        regcode--;
X    else
X        regsize--;
X}
X
X/*
X - reginsert - insert an operator in front of already-emitted operand
X *
X * Means relocating the operand.
X */
Xstatic void
Xreginsert(op, opnd)
X    int            op;
X    char_u           *opnd;
X{
X    register char_u  *src;
X    register char_u  *dst;
X    register char_u  *place;
X
X    if (regcode == ®dummy) {
X        regsize += 3;
X        return;
X    }
X    src = regcode;
X    regcode += 3;
X    dst = regcode;
X    while (src > opnd)
X        *--dst = *--src;
X
X    place = opnd;                /* Op node, where operand used to be. */
X    *place++ = op;
X    *place++ = '\0';
X    *place = '\0';
X}
X
X/*
X - regtail - set the next-pointer at the end of a node chain
X */
Xstatic void
Xregtail(p, val)
X    char_u           *p;
X    char_u           *val;
X{
X    register char_u  *scan;
X    register char_u  *temp;
X    register int    offset;
X
X    if (p == ®dummy)
X        return;
X
X    /* Find last node. */
X    scan = p;
X    for (;;) {
X        temp = regnext(scan);
X        if (temp == NULL)
X            break;
X        scan = temp;
X    }
X
X    if (OP(scan) == BACK)
X        offset = (int)(scan - val);
X    else
X        offset = (int)(val - scan);
X    *(scan + 1) = (char_u) ((offset >> 8) & 0377);
X    *(scan + 2) = (char_u) (offset & 0377);
X}
X
X/*
X - regoptail - regtail on operand of first argument; nop if operandless
X */
Xstatic void
Xregoptail(p, val)
X    char_u           *p;
X    char_u           *val;
X{
X    /* "Operandless" and "op != BRANCH" are synonymous in practice. */
X    if (p == NULL || p == ®dummy || OP(p) != BRANCH)
X        return;
X    regtail(OPERAND(p), val);
X}
X
X/*
X - getchr() - get the next character from the pattern. We know about
X * magic and such, so therefore we need a lexical analyzer.
X */
X
X/* static int        curchr; */
Xstatic int        prevchr;
Xstatic int        nextchr;    /* used for ungetchr() */
X
Xstatic void
Xinitchr(str)
Xchar_u *str;
X{
X    regparse = str;
X    curchr = prevchr = nextchr = -1;
X}
X
Xstatic int
Xpeekchr()
X{
X    if (curchr < 0) {
X        switch (curchr = regparse[0]) {
X        case '.':
X        case '*':
X    /*    case '+':*/
X    /*    case '=':*/
X        case '[':
X        case '~':
X            if (reg_magic)
X                curchr = Magic(curchr);
X            break;
X        case '^':
X            /* ^ is only magic as the very first character */
X            if (prevchr < 0)
X                curchr = Magic('^');
X            break;
X        case '$':
X            /* $ is only magic as the very last character and in front of '\|' */
X            if (regparse[1] == NUL || (regparse[1] == '\\' && regparse[2] == '|'))
X                curchr = Magic('$');
X            break;
X        case '\\':
X            regparse++;
X            if (regparse[0] == NUL)
X                curchr = '\\';    /* trailing '\' */
X            else if (STRCHR(META, regparse[0]))
X            {
X                /*
X                 * META contains everything that may be magic sometimes, except
X                 * ^ and $ ("\^" and "\$" are never magic).
X                 * We now fetch the next character and toggle its magicness.
X                 * Therefore, \ is so meta-magic that it is not in META.
X                 */
X                curchr = -1;
X                peekchr();
X                curchr ^= Magic(0);
X            }
X            else
X            {
X                /*
X                 * Next character can never be (made) magic?
X                 * Then backslashing it won't do anything.
X                 */
X                curchr = regparse[0];
X            }
X            break;
X        }
X    }
X
X    return curchr;
X}
X
Xstatic void
Xskipchr()
X{
X    regparse++;
X    prevchr = curchr;
X    curchr = nextchr;        /* use previously unget char, or -1 */
X    nextchr = -1;
X}
X
Xstatic int
Xgetchr()
X{
X    int chr;
X
X    chr = peekchr();
X    skipchr();
X
X    return chr;
X}
X
X/*
X * put character back. Works only once!
X */
Xstatic void
Xungetchr()
X{
X    nextchr = curchr;
X    curchr = prevchr;
X    /*
X     * Backup regparse as well; not because we will use what it points at,
X     * but because skipchr() will bump it again.
X     */
X    regparse--;
X}
X
X/*
X * regexec and friends
X */
X
X/*
X * Global work variables for regexec().
X */
Xstatic char_u    *reginput;        /* String-input pointer. */
Xstatic char_u    *regbol;         /* Beginning of input, for ^ check. */
Xstatic char_u   **regstartp;        /* Pointer to startp array. */
X/* static char_u   **regendp;    */    /* Ditto for endp. */
X
X/*
X * Forwards.
X */
Xstatic int        regtry __ARGS((regexp *, char_u *));
Xstatic int        regmatch __ARGS((char_u *));
Xstatic int        regrepeat __ARGS((char_u *));
X
X#ifdef DEBUG
Xint             regnarrate = 1;
Xvoid            regdump __ARGS((regexp *));
Xstatic char_u    *regprop __ARGS((char_u *));
X#endif
X
X/*
X - regexec - match a regexp against a string
X */
Xint
Xregexec(prog, string, at_bol)
X    register regexp *prog;
X    register char_u  *string;
X    int             at_bol;
X{
X    register char_u  *s;
X
X    /* Be paranoid... */
X    if (prog == NULL || string == NULL) {
X        emsg(e_null);
X        return 0;
X    }
X    /* Check validity of program. */
X    if (UCHARAT(prog->program) != MAGIC) {
X        emsg(e_re_corr);
X        return 0;
X    }
X    /* If there is a "must appear" string, look for it. */
X    if (prog->regmust != NULL) {
X        s = string;
X        while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
X            if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
X                break;            /* Found it. */
X            s++;
X        }
X        if (s == NULL)            /* Not present. */
X            return 0;
X    }
X    /* Mark beginning of line for ^ . */
X    if (at_bol)
X        regbol = string;        /* is possible to match bol */
X    else
X        regbol = NULL;            /* we aren't there, so don't match it */
X
X    /* Simplest case:  anchored match need be tried only once. */
X    if (prog->reganch)
X        return regtry(prog, string);
X
X    /* Messy cases:  unanchored match. */
X    s = string;
X    if (prog->regstart != '\0')
X        /* We know what char it must start with. */
X        while ((s = cstrchr(s, prog->regstart)) != NULL) {
X            if (regtry(prog, s))
X                return 1;
X            s++;
X        }
X    else
X        /* We don't -- general case. */
X        do {
X            if (regtry(prog, s))
X                return 1;
X        } while (*s++ != '\0');
X
X    /* Failure. */
X    return 0;
X}
X
X/*
X - regtry - try match at specific point
X */
Xstatic int                        /* 0 failure, 1 success */
Xregtry(prog, string)
X    regexp           *prog;
X    char_u           *string;
X{
X    register int    i;
X    register char_u **sp;
X    register char_u **ep;
X
X    reginput = string;
X    regstartp = prog->startp;
X    regendp = prog->endp;
X
X    sp = prog->startp;
X    ep = prog->endp;
X    for (i = NSUBEXP; i > 0; i--) {
X        *sp++ = NULL;
X        *ep++ = NULL;
X    }
X    if (regmatch(prog->program + 1)) {
X        prog->startp[0] = string;
X        prog->endp[0] = reginput;
X        return 1;
X    } else
X        return 0;
X}
X
X/*
X - regmatch - main matching routine
X *
X * Conceptually the strategy is simple:  check to see whether the current
X * node matches, call self recursively to see whether the rest matches,
X * and then act accordingly.  In practice we make some effort to avoid
X * recursion, in particular by going through "ordinary" nodes (that don't
X * need to know whether the rest of the match failed) by a loop instead of
X * by recursion.
X */
Xstatic int                        /* 0 failure, 1 success */
Xregmatch(prog)
X    char_u           *prog;
X{
X    register char_u  *scan;        /* Current node. */
X    char_u           *next;        /* Next node. */
X
X    scan = prog;
X#ifdef DEBUG
X    if (scan != NULL && regnarrate)
X        fprintf(stderr, "%s(\n", regprop(scan));
X#endif
X    while (scan != NULL) {
X#ifdef DEBUG
X        if (regnarrate) {
X            fprintf(stderr, "%s...\n", regprop(scan));
X        }
X#endif
X        next = regnext(scan);
X        switch (OP(scan)) {
X          case BOL:
X            if (reginput != regbol)
X                return 0;
X            break;
X          case EOL:
X            if (*reginput != '\0')
X                return 0;
X            break;
X          case BOW:        /* \<word; reginput points to w */
X#define isidchar(x)    (isalnum(x) || ((x) == '_'))
X              if (reginput != regbol && isidchar(reginput[-1]))
X                return 0;
X              if (!reginput[0] || !isidchar(reginput[0]))
X                return 0;
X            break;
X          case EOW:        /* word\>; reginput points after d */
X              if (reginput == regbol || !isidchar(reginput[-1]))
X                return 0;
X              if (reginput[0] && isidchar(reginput[0]))
X                return 0;
X            break;
X          case ANY:
X            if (*reginput == '\0')
X                return 0;
X            reginput++;
X            break;
X          case EXACTLY:{
X                register int    len;
X                register char_u  *opnd;
X
X                opnd = OPERAND(scan);
X                /* Inline the first character, for speed. */
X                if (*opnd != *reginput && (!reg_ic || TO_UPPER(*opnd) != TO_UPPER(*reginput)))
X                    return 0;
X                len = STRLEN(opnd);
X                if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
X                    return 0;
X                reginput += len;
X            }
X            break;
X          case ANYOF:
X            if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
X                return 0;
X            reginput++;
X            break;
X          case ANYBUT:
X            if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
X                return 0;
X            reginput++;
X            break;
X          case NOTHING:
X            break;
X          case BACK:
X            break;
X          case MOPEN + 1:
X          case MOPEN + 2:
X          case MOPEN + 3:
X          case MOPEN + 4:
X          case MOPEN + 5:
X          case MOPEN + 6:
X          case MOPEN + 7:
X          case MOPEN + 8:
X          case MOPEN + 9:{
X                register int    no;
X                register char_u  *save;
X
X                no = OP(scan) - MOPEN;
X                save = regstartp[no];
X                regstartp[no] = reginput; /* Tentatively */
X#ifdef DEBUG
X                printf("MOPEN  %d pre  @'%s' ('%s' )'%s'\n",
X                    no, save,
X                    regstartp[no] ? regstartp[no] : "NULL",
X                    regendp[no] ? regendp[no] : "NULL");
X#endif
X
X                if (regmatch(next)) {
X#ifdef DEBUG
X                printf("MOPEN  %d post @'%s' ('%s' )'%s'\n",
X                    no, save,
X                    regstartp[no] ? regstartp[no] : "NULL",
X                    regendp[no] ? regendp[no] : "NULL");
X#endif
X                    return 1;
X                }
X                regstartp[no] = save;        /* We were wrong... */
X                return 0;
X            }
X            /* break; Not Reached */
X          case MCLOSE + 1:
X          case MCLOSE + 2:
X          case MCLOSE + 3:
X          case MCLOSE + 4:
X          case MCLOSE + 5:
X          case MCLOSE + 6:
X          case MCLOSE + 7:
X          case MCLOSE + 8:
X          case MCLOSE + 9:{
X                register int    no;
X                register char_u  *save;
X
X                no = OP(scan) - MCLOSE;
X                save = regendp[no];
X                regendp[no] = reginput; /* Tentatively */
X#ifdef DEBUG
X                printf("MCLOSE %d pre  @'%s' ('%s' )'%s'\n",
X                    no, save,
X                    regstartp[no] ? regstartp[no] : "NULL",
X                    regendp[no] ? regendp[no] : "NULL");
X#endif
X
X                if (regmatch(next)) {
X#ifdef DEBUG
X                printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
X                    no, save,
X                    regstartp[no] ? regstartp[no] : "NULL",
X                    regendp[no] ? regendp[no] : "NULL");
X#endif
X                    return 1;
X                }
X                regendp[no] = save;        /* We were wrong... */
X                return 0;
X            }
X            /* break; Not Reached */
X#ifdef BACKREF
X          case BACKREF + 1:
X          case BACKREF + 2:
X          case BACKREF + 3:
X          case BACKREF + 4:
X          case BACKREF + 5:
X          case BACKREF + 6:
X          case BACKREF + 7:
X          case BACKREF + 8:
X          case BACKREF + 9:{
X                register int    no;
X                int                len;
X
X                no = OP(scan) - BACKREF;
X                if (regendp[no] != NULL) {
X                    len = (int)(regendp[no] - regstartp[no]);
X                    if (cstrncmp(regstartp[no], reginput, len) != 0)
X                        return 0;
X                    reginput += len;
X                } else {
X                    /*emsg("backref to 0-repeat");*/
X                    /*return 0;*/
X                }
X              }
X            break;
X#endif
X          case BRANCH:{
X                register char_u  *save;
X
X                if (OP(next) != BRANCH) /* No choice. */
X                    next = OPERAND(scan);        /* Avoid recursion. */
X                else {
X                    do {
X                        save = reginput;
X                        if (regmatch(OPERAND(scan)))
X                            return 1;
X                        reginput = save;
X                        scan = regnext(scan);
X                    } while (scan != NULL && OP(scan) == BRANCH);
X                    return 0;
X                    /* NOTREACHED */
X                }
X            }
X            break;
X          case STAR:
X          case PLUS:{
X                register int    nextch;
X                register int    no;
X                register char_u  *save;
X                register int    min;
X
X                /*
X                 * Lookahead to avoid useless match attempts when we know
X                 * what character comes next.
X                 */
X                nextch = '\0';
X                if (OP(next) == EXACTLY)
X                {
X                    nextch = *OPERAND(next);
X                    if (reg_ic)
X                        nextch = TO_UPPER(nextch);
X                }
X                min = (OP(scan) == STAR) ? 0 : 1;
X                save = reginput;
X                no = regrepeat(OPERAND(scan));
X                while (no >= min)
X                {
X                    /* If it could work, try it. */
X                    if (nextch == '\0' || (*reginput == nextch ||
X                                    (reg_ic && TO_UPPER(*reginput) == nextch)))
X                        if (regmatch(next))
X                            return 1;
X                    /* Couldn't or didn't -- back up. */
X                    no--;
X                    reginput = save + no;
X                }
X                return 0;
X            }
X            /* break; Not Reached */
X          case END:
X            return 1;         /* Success! */
X            /* break; Not Reached */
X          default:
X            emsg(e_re_corr);
X            return 0;
X            /* break; Not Reached */
X        }
X
X        scan = next;
X    }
X
X    /*
X     * We get here only if there's trouble -- normally "case END" is the
X     * terminating point.
X     */
X    emsg(e_re_corr);
X    return 0;
X}
X
X/*
X - regrepeat - repeatedly match something simple, report how many
X */
Xstatic int
Xregrepeat(p)
X    char_u           *p;
X{
X    register int    count = 0;
X    register char_u  *scan;
X    register char_u  *opnd;
X
X    scan = reginput;
X    opnd = OPERAND(p);
X    switch (OP(p)) {
X      case ANY:
X        count = STRLEN(scan);
X        scan += count;
X        break;
X      case EXACTLY:
X        while (*opnd == *scan || (reg_ic && TO_UPPER(*opnd) == TO_UPPER(*scan)))
X        {
X            count++;
X            scan++;
X        }
X        break;
X      case ANYOF:
X        while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
X        {
X            count++;
X            scan++;
X        }
X        break;
X      case ANYBUT:
X        while (*scan != '\0' && cstrchr(opnd, *scan) == NULL) {
X            count++;
X            scan++;
X        }
X        break;
X      default:                    /* Oh dear.  Called inappropriately. */
X        emsg(e_re_corr);
X        count = 0;                /* Best compromise. */
X        break;
X    }
X    reginput = scan;
X
X    return count;
X}
X
X/*
X - regnext - dig the "next" pointer out of a node
X */
Xstatic char_u    *
Xregnext(p)
X    register char_u  *p;
X{
X    register int    offset;
X
X    if (p == ®dummy)
X        return NULL;
X
X    offset = NEXT(p);
X    if (offset == 0)
X        return NULL;
X
X    if (OP(p) == BACK)
X        return p - offset;
X    else
X        return p + offset;
X}
X
X#ifdef DEBUG
X
X/*
X - regdump - dump a regexp onto stdout in vaguely comprehensible form
X */
Xvoid
Xregdump(r)
X    regexp           *r;
X{
X    register char_u  *s;
X    register int    op = EXACTLY;        /* Arbitrary non-END op. */
X    register char_u  *next;
X    /*extern char_u    *strchr();*/
X
X
X    s = r->program + 1;
X    while (op != END) {         /* While that wasn't END last time... */
X        op = OP(s);
X        printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
X        next = regnext(s);
X        if (next == NULL)        /* Next ptr. */
X            printf("(0)");
X        else
X            printf("(%d)", (s - r->program) + (next - s));
X        s += 3;
X        if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
X            /* Literal string, where present. */
X            while (*s != '\0') {
X                putchar(*s);
X                s++;
X            }
X            s++;
X        }
X        putchar('\n');
X    }
X
X    /* Header fields of interest. */
X    if (r->regstart != '\0')
X        printf("start `%c' ", r->regstart);
X    if (r->reganch)
X        printf("anchored ");
X    if (r->regmust != NULL)
X        printf("must have \"%s\"", r->regmust);
X    printf("\n");
X}
X
X/*
X - regprop - printable representation of opcode
X */
Xstatic char_u    *
Xregprop(op)
X    char_u           *op;
X{
X    register char_u  *p;
X    static char_u     buf[50];
X
X    (void) strcpy(buf, ":");
X
X    switch (OP(op)) {
X      case BOL:
X        p = "BOL";
X        break;
X      case EOL:
X        p = "EOL";
X        break;
X      case ANY:
X        p = "ANY";
X        break;
X      case ANYOF:
X        p = "ANYOF";
X        break;
X      case ANYBUT:
X        p = "ANYBUT";
X        break;
X      case BRANCH:
X        p = "BRANCH";
X        break;
X      case EXACTLY:
X        p = "EXACTLY";
X        break;
X      case NOTHING:
X        p = "NOTHING";
X        break;
X      case BACK:
X        p = "BACK";
X        break;
X      case END:
X        p = "END";
X        break;
X      case MOPEN + 1:
X      case MOPEN + 2:
X      case MOPEN + 3:
X      case MOPEN + 4:
X      case MOPEN + 5:
X      case MOPEN + 6:
X      case MOPEN + 7:
X      case MOPEN + 8:
X      case MOPEN + 9:
X        sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
X        p = NULL;
X        break;
X      case MCLOSE + 1:
X      case MCLOSE + 2:
X      case MCLOSE + 3:
X      case MCLOSE + 4:
X      case MCLOSE + 5:
X      case MCLOSE + 6:
X      case MCLOSE + 7:
X      case MCLOSE + 8:
X      case MCLOSE + 9:
X        sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
X        p = NULL;
X        break;
X      case BACKREF + 1:
X      case BACKREF + 2:
X      case BACKREF + 3:
X      case BACKREF + 4:
X      case BACKREF + 5:
X      case BACKREF + 6:
X      case BACKREF + 7:
X      case BACKREF + 8:
X      case BACKREF + 9:
X        sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
X        p = NULL;
X        break;
X      case STAR:
X        p = "STAR";
X        break;
X      case PLUS:
X        p = "PLUS";
X        break;
X      default:
X        sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
X        p = NULL;
X        break;
X    }
X    if (p != NULL)
X        (void) strcat(buf, p);
X    return buf;
X}
X#endif
X
X/*
X * The following is provided for those people who do not have strcspn() in
X * their C libraries.  They should get off their butts and do something
X * about it; at least one public-domain implementation of those (highly
X * useful) string routines has been published on Usenet.
X */
X#ifdef STRCSPN
X/*
X * strcspn - find length of initial segment of s1 consisting entirely
X * of characters not from s2
X */
X
Xstatic int
Xstrcspn(s1, s2)
X    const char_u           *s1;
X    const char_u           *s2;
X{
X    register char_u  *scan1;
X    register char_u  *scan2;
X    register int    count;
X
X    count = 0;
X    for (scan1 = s1; *scan1 != '\0'; scan1++) {
X        for (scan2 = s2; *scan2 != '\0';)        /* ++ moved down. */
X            if (*scan1 == *scan2++)
X                return count;
X        count++;
X    }
X    return count;
X}
X#endif
X
X/*
X * Compare two strings, ignore case if reg_ic set.
X * Return 0 if strings match, non-zero otherwise.
X */
X    int
Xcstrncmp(s1, s2, n)
X    char_u           *s1, *s2;
X    int             n;
X{
X    if (!reg_ic)
X        return STRNCMP(s1, s2, (size_t)n);
X
X    return vim_strnicmp(s1, s2, (size_t)n);
X}
X
X/*
X * cstrchr: This function is used a lot for simple searches, keep it fast!
X */
X    char_u *
Xcstrchr(s, c)
X    char_u           *s;
X    register int    c;
X{
X    register char_u           *p;
X
X    if (!reg_ic)
X        return STRCHR(s, c);
X
X    c = TO_UPPER(c);
X
X    for (p = s; *p; p++)
X    {
X        if (TO_UPPER(*p) == c)
X            return p;
X    }
X    return NULL;
X}
END_OF_FILE
  if test 40070 -ne `wc -c <'vim/src/regexp.c'`; then
    echo shar: \"'vim/src/regexp.c'\" unpacked with wrong size!
  fi
  # end of 'vim/src/regexp.c'
fi
if test -f 'vim/src/undo.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'vim/src/undo.c'\"
else
  echo shar: Extracting \"'vim/src/undo.c'\" \(24811 characters\)
  sed "s/^X//" >'vim/src/undo.c' <<'END_OF_FILE'
X/* vi:ts=4:sw=4
X *
X * VIM - Vi IMproved        by Bram Moolenaar
X *
X * Read the file "credits.txt" for a list of people who contributed.
X * Read the file "uganda.txt" for copying and usage conditions.
X */
X
X/*
X * undo.c: multi level undo facility
X *
X * The saved lines are stored in a list of lists (one for each buffer):
X *
X * b_u_oldhead------------------------------------------------+
X *                                                            |
X *                                                            V
X *                +--------------+    +--------------+    +--------------+
X * b_u_newhead--->| u_header     |    | u_header     |    | u_header     |
X *                |     uh_next------>|     uh_next------>|     uh_next---->NULL
X *         NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
X *                |     uh_entry |    |     uh_entry |    |     uh_entry |
X *                +--------|-----+    +--------|-----+    +--------|-----+
X *                         |                   |                   |
X *                         V                   V                   V
X *                +--------------+    +--------------+    +--------------+
X *                | u_entry      |    | u_entry      |    | u_entry      |
X *                |     ue_next  |    |     ue_next  |    |     ue_next  |
X *                +--------|-----+    +--------|-----+    +--------|-----+
X *                         |                   |                   |
X *                         V                   V                   V
X *                +--------------+            NULL                NULL
X *                | u_entry      |
X *                |     ue_next  |
X *                +--------|-----+
X *                         |
X *                         V
X *                        etc.
X *
X * Each u_entry list contains the information for one undo or redo.
X * curbuf->b_u_curhead points to the header of the last undo (the next redo), or is
X * NULL if nothing has been undone.
X *
X * All data is allocated with u_alloc_line(), thus it will be freed as soon as
X * we switch files!
X */
X
X#include "vim.h"
X#include "globals.h"
X#include "proto.h"
X#include "param.h"
X
Xstatic void u_getbot __ARGS((void));
Xstatic int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
Xstatic void u_undoredo __ARGS((void));
Xstatic void u_undo_end __ARGS((void));
Xstatic void u_freelist __ARGS((struct u_header *));
Xstatic void u_freeentry __ARGS((struct u_entry *, long));
X
Xstatic char_u *u_blockalloc __ARGS((long_u));
Xstatic void u_free_line __ARGS((char_u *));
Xstatic char_u *u_alloc_line __ARGS((unsigned));
Xstatic char_u *u_save_line __ARGS((linenr_t));
X
Xstatic long        u_newcount, u_oldcount;
X
X/*
X * save the current line for both the "u" and "U" command
X */
X    int
Xu_save_cursor()
X{
X    return (u_save((linenr_t)(curwin->w_cursor.lnum - 1), (linenr_t)(curwin->w_cursor.lnum + 1)));
X}
X
X/*
X * Save the lines between "top" and "bot" for both the "u" and "U" command.
X * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
X * Returns FALSE when lines could not be saved.
X */
X    int
Xu_save(top, bot)
X    linenr_t top, bot;
X{
X    if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
X        return FALSE;    /* rely on caller to do error messages */
X
X    if (top + 2 == bot)
X        u_saveline((linenr_t)(top + 1));
X
X    return (u_savecommon(top, bot, (linenr_t)0));
X}
X
X/*
X * save the line "lnum" (used by :s command)
X * The line is replaced, so the new bottom line is lnum + 1.
X */
X    int
Xu_savesub(lnum)
X    linenr_t    lnum;
X{
X    return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
X}
X
X/*
X * a new line is inserted before line "lnum" (used by :s command)
X * The line is inserted, so the new bottom line is lnum + 1.
X */
X     int
Xu_inssub(lnum)
X    linenr_t    lnum;
X{
X    return (u_savecommon(lnum - 1, lnum, lnum + 1));
X}
X
X/*
X * save the lines "lnum" - "lnum" + nlines (used by delete command)
X * The lines are deleted, so the new bottom line is lnum.
X */
X    int
Xu_savedel(lnum, nlines)
X    linenr_t    lnum;
X    long        nlines;
X{
X    return (u_savecommon(lnum - 1, lnum + nlines, lnum));
X}
X
X    static int
Xu_savecommon(top, bot, newbot)
X    linenr_t top, bot;
X    linenr_t newbot;
X{
X    linenr_t        lnum;
X    long            i;
X    struct u_header *uhp;
X    struct u_entry    *uep;
X    long            size;
X
X    /*
X     * if curbuf->b_u_synced == TRUE make a new header
X     */
X    if (curbuf->b_u_synced)
X    {
X        /*
X         * if we undid more than we redid, free the entry lists before and
X         * including curbuf->b_u_curhead
X         */
X        while (curbuf->b_u_curhead != NULL)
X            u_freelist(curbuf->b_u_newhead);
X
X        /*
X         * free headers to keep the size right
X         */
X        while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
X            u_freelist(curbuf->b_u_oldhead);
X
X        if (p_ul < 0)            /* no undo at all */
X            return TRUE;
X
X        /*
X         * make a new header entry
X         */
X        uhp = (struct u_header *)u_alloc_line((unsigned)sizeof(struct u_header));
X        if (uhp == NULL)
X            goto nomem;
X        uhp->uh_prev = NULL;
X        uhp->uh_next = curbuf->b_u_newhead;
X        if (curbuf->b_u_newhead != NULL)
X            curbuf->b_u_newhead->uh_prev = uhp;
X        uhp->uh_entry = NULL;
X        uhp->uh_cursor = curwin->w_cursor;        /* save cursor position for undo */
X        uhp->uh_changed = curbuf->b_changed;    /* save changed flag for undo */
X                                                /* save named marks for undo */
X        memmove((char *)uhp->uh_namedm, (char *)curbuf->b_namedm, sizeof(FPOS) * NMARKS);
X        curbuf->b_u_newhead = uhp;
X        if (curbuf->b_u_oldhead == NULL)
X            curbuf->b_u_oldhead = uhp;
X        ++curbuf->b_u_numhead;
X    }
X    else    /* find line number for ue_bot for previous u_save() */
X        u_getbot();
X
X    size = bot - top - 1;
X#ifndef UNIX
X        /*
X         * With Amiga and MSDOS we can't handle big undo's, because then
X         * u_alloc_line would have to allocate a block larger than 32K
X         */
X    if (size >= 8000)
X        goto nomem;
X#endif
X
X    /*
X     * add lines in front of entry list
X     */
X    uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
X    if (uep == NULL)
X        goto nomem;
X
X    uep->ue_size = size;
X    uep->ue_top = top;
X    uep->ue_lcount = 0;
X    if (newbot)
X        uep->ue_bot = newbot;
X        /*
X         * use 0 for ue_bot if bot is below last line or if the buffer is empty, in
X         * which case the last line may be replaced (e.g. with 'O' command).
X         */
X    else if (bot > curbuf->b_ml.ml_line_count || bufempty())
X        uep->ue_bot = 0;
X    else
X        uep->ue_lcount = curbuf->b_ml.ml_line_count;    /* we have to compute ue_bot later */
X
X    if (size)
X    {
X        if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
X        {
X            u_freeentry(uep, 0L);
X            goto nomem;
X        }
X        for (i = 0, lnum = top + 1; i < size; ++i)
X        {
X            if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
X            {
X                u_freeentry(uep, i);
X                goto nomem;
X            }
X        }
X    }
X    uep->ue_next = curbuf->b_u_newhead->uh_entry;
X    curbuf->b_u_newhead->uh_entry = uep;
X    curbuf->b_u_synced = FALSE;
X    return TRUE;
X
Xnomem:
X    if (ask_yesno((char_u *)"no undo possible; continue anyway") == 'y')
X        return TRUE;
X    return FALSE;
X}
X
X    void
Xu_undo(count)
X    int count;
X{
X    /*
X     * If we get an undo command while executing a macro, we behave like the
X     * original vi. If this happens twice in one macro the result will not
X     * be compatible.
X     */
X    if (curbuf->b_u_synced == FALSE)
X    {
X        u_sync();
X        count = 1;
X    }
X
X    curbuf->b_startop.lnum = 0;            /* unset '[ mark */
X    curbuf->b_endop.lnum = 0;                /* unset '] mark */
X    u_newcount = 0;
X    u_oldcount = 0;
X    while (count--)
X    {
X        if (curbuf->b_u_curhead == NULL)                        /* first undo */
X            curbuf->b_u_curhead = curbuf->b_u_newhead;
X        else if (p_ul > 0)                            /* multi level undo */
X            curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;            /* get next undo */
X
X        if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)    /* nothing to undo */
X        {
X            curbuf->b_u_curhead = curbuf->b_u_oldhead;                    /* stick curbuf->b_u_curhead at end */
X            beep();
X            break;
X        }
X
X        u_undoredo();
X    }
X    u_undo_end();
X}
X
X    void
Xu_redo(count)
X    int count;
X{
X    u_newcount = 0;
X    u_oldcount = 0;
X    while (count--)
X    {
X        if (curbuf->b_u_curhead == NULL || p_ul <= 0)        /* nothing to redo */
X        {
X            beep();
X            break;
X        }
X
X        u_undoredo();
X
X        curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;            /* advance for next redo */
X    }
X    u_undo_end();
X}
X
X/*
X * u_undoredo: common code for undo and redo
X *
X * The lines in the file are replaced by the lines in the entry list at curbuf->b_u_curhead.
X * The replaced lines in the file are saved in the entry list for the next undo/redo.
X */
X    static void
Xu_undoredo()
X{
X    char_u        **newarray = NULL;
X    linenr_t    oldsize;
X    linenr_t    newsize;
X    linenr_t    top, bot;
X    linenr_t    lnum;
X    linenr_t    newlnum = MAXLNUM;
X    long        i;
X    struct u_entry *uep, *nuep;
X    struct u_entry *newlist = NULL;
X    int            changed = curbuf->b_changed;
X    FPOS        namedm[NMARKS];
X
X    if (curbuf->b_u_curhead->uh_changed)
X        CHANGED;
X    else
X        UNCHANGED(curbuf);
X    /*
X     * save marks before undo/redo
X     */
X    memmove((char *)namedm, (char *)curbuf->b_namedm, sizeof(FPOS) * NMARKS);
X
X    for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
X    {
X        top = uep->ue_top;
X        bot = uep->ue_bot;
X        if (bot == 0)
X            bot = curbuf->b_ml.ml_line_count + 1;
X        if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
X        {
X            EMSG("u_undo: line numbers wrong");
X            CHANGED;        /* don't want UNCHANGED now */
X            return;
X        }
X
X        if (top < newlnum)
X        {
X            newlnum = top;
X            curwin->w_cursor.lnum = top + 1;
X        }
X        oldsize = bot - top - 1;    /* number of lines before undo */
X
X        newsize = uep->ue_size;        /* number of lines after undo */
X
X        /* delete the lines between top and bot and save them in newarray */
X        if (oldsize)
X        {
X            if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
X            {
X                /*
X                 * We have messed up the entry list, repair is impossible.
X                 * we have to free the rest of the list.
X                 */
X                while (uep != NULL)
X                {
X                    nuep = uep->ue_next;
X                    u_freeentry(uep, uep->ue_size);
X                    uep = nuep;
X                }
X                break;
X            }
X            /* delete backwards, it goes faster in most cases */
X            for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
X            {
X                newarray[i] = u_save_line(lnum);
X                ml_delete(lnum);
X            }
X        }
X
X        /* insert the lines in u_array between top and bot */
X        if (newsize)
X        {
X            for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
X            {
X                ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
X                u_free_line(uep->ue_array[i]);
X            }
X            u_free_line((char_u *)uep->ue_array);
X        }
X
X        /* adjust marks */
X        if (oldsize != newsize)
X        {
X            mark_adjust(top, top + oldsize - 1, MAXLNUM);
X            mark_adjust(top + oldsize, MAXLNUM, (long)newsize - (long)oldsize);
X        }
X
X        u_newcount += newsize;
X        u_oldcount += oldsize;
X        uep->ue_size = oldsize;
X        uep->ue_array = newarray;
X        uep->ue_bot = top + newsize + 1;
X
X        /*
X         * insert this entry in front of the new entry list
X         */
X        nuep = uep->ue_next;
X        uep->ue_next = newlist;
X        newlist = uep;
X    }
X
X    curbuf->b_u_curhead->uh_entry = newlist;
X    curbuf->b_u_curhead->uh_changed = changed;
X
X    /*
X     * restore marks from before undo/redo
X     */
X    for (i = 0; i < NMARKS; ++i)
X        if (curbuf->b_u_curhead->uh_namedm[i].lnum)
X        {
X            curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
X            curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
X        }
X
X    if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
X        curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
X    else
X        curwin->w_cursor.col = 0;
X}
X
X/*
X * If we deleted or added lines, report the number of less/more lines.
X * Otherwise, report the number of changes (this may be incorrect
X * in some cases, but it's better than nothing).
X */
X    static void
Xu_undo_end()
X{
X    if ((u_oldcount -= u_newcount) != 0)
X        msgmore(-u_oldcount);
X    else if (u_newcount > p_report)
X        smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));
X
X    updateScreen(CURSUPD);
X}
X
X/*
X * u_sync: stop adding to the current entry list
X */
X    void
Xu_sync()
X{
X    if (curbuf->b_u_synced)
X        return;                /* already synced */
X    u_getbot();                /* compute ue_bot of previous u_save */
X    curbuf->b_u_curhead = NULL;
X}
X
X/*
X * Called after writing the file and setting b_changed to FALSE.
X * Now an undo means that the buffer is modified.
X */
X    void
Xu_unchanged(buf)
X    BUF        *buf;
X{
X    register struct u_header *uh;
X
X    for (uh = buf->b_u_newhead; uh; uh = uh->uh_next)
X        uh->uh_changed = 1;
X    buf->b_did_warn = FALSE;
X}
X
X/*
X * u_getbot(): compute the line number of the previous u_save
X *                 It is called only when b_u_synced is FALSE.
X */
X    static void
Xu_getbot()
X{
X    register struct u_entry *uep;
X
X    if (curbuf->b_u_newhead == NULL || (uep = curbuf->b_u_newhead->uh_entry) == NULL)
X    {
X        EMSG("undo list corrupt");
X        return;
X    }
X
X    if (uep->ue_lcount != 0)
X    {
X        /*
X         * the new ue_bot is computed from the number of lines that has been
X         * inserted (0 - deleted) since calling u_save. This is equal to the old
X         * line count subtracted from the current line count.
X         */
X        uep->ue_bot = uep->ue_top + uep->ue_size + 1 + (curbuf->b_ml.ml_line_count - uep->ue_lcount);
X        if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count)
X        {
X            EMSG("undo line missing");
X            uep->ue_bot = uep->ue_top + 1;    /* assume all lines deleted, will get
X                                             * all the old lines back without
X                                             * deleting the current ones */
X        }
X        uep->ue_lcount = 0;
X    }
X
X    curbuf->b_u_synced = TRUE;
X}
X
X/*
X * u_freelist: free one entry list and adjust the pointers
X */
X    static void
Xu_freelist(uhp)
X    struct u_header *uhp;
X{
X    register struct u_entry *uep, *nuep;
X
X    for (uep = uhp->uh_entry; uep != NULL; uep = nuep)
X    {
X        nuep = uep->ue_next;
X        u_freeentry(uep, uep->ue_size);
X    }
X
X    if (curbuf->b_u_curhead == uhp)
X        curbuf->b_u_curhead = NULL;
X
X    if (uhp->uh_next == NULL)
X        curbuf->b_u_oldhead = uhp->uh_prev;
X    else
X        uhp->uh_next->uh_prev = uhp->uh_prev;
X
X    if (uhp->uh_prev == NULL)
X        curbuf->b_u_newhead = uhp->uh_next;
X    else
X        uhp->uh_prev->uh_next = uhp->uh_next;
X
X    u_free_line((char_u *)uhp);
X    --curbuf->b_u_numhead;
X}
X
X/*
X * free entry 'uep' and 'n' lines in uep->ue_array[]
X */
X    static void
Xu_freeentry(uep, n)
X    struct u_entry *uep;
X    register long n;
X{
X    while (n)
X        u_free_line(uep->ue_array[--n]);
X    u_free_line((char_u *)uep);
X}
X
X/*
X * invalidate the undo buffer; called when storage has already been released
X */
X    void
Xu_clearall(buf)
X    BUF        *buf;
X{
X    buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
X    buf->b_u_synced = TRUE;
X    buf->b_u_numhead = 0;
X    buf->b_u_line_ptr = NULL;
X    buf->b_u_line_lnum = 0;
X}
X
X/*
X * save the line "lnum" for the "U" command
X */
X    void
Xu_saveline(lnum)
X    linenr_t lnum;
X{
X    if (lnum == curbuf->b_u_line_lnum)        /* line is already saved */
X        return;
X    if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count)    /* should never happen */
X        return;
X    u_clearline();
X    curbuf->b_u_line_lnum = lnum;
X    if (curwin->w_cursor.lnum == lnum)
X        curbuf->b_u_line_colnr = curwin->w_cursor.col;
X    else
X        curbuf->b_u_line_colnr = 0;
X    curbuf->b_u_line_ptr = u_save_line(lnum);    /* when out of mem alloc() will give a warning */
X}
X
X/*
X * clear the line saved for the "U" command
X * (this is used externally for crossing a line while in insert mode)
X */
X    void
Xu_clearline()
X{
X    if (curbuf->b_u_line_ptr != NULL)
X    {
X        u_free_line(curbuf->b_u_line_ptr);
X        curbuf->b_u_line_ptr = NULL;
X        curbuf->b_u_line_lnum = 0;
X    }
X}
X
X/*
X * Implementation of the "U" command.
X * Differentiation from vi: "U" can be undone with the next "U".
X * We also allow the cursor to be in another line.
X */
X    void
Xu_undoline()
X{
X    colnr_t t;
X    char_u    *old;
X
X    if (curbuf->b_u_line_ptr == NULL || curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count)
X    {
X        beep();
X        return;
X    }
X        /* first save the line for the 'u' command */
X    u_savecommon(curbuf->b_u_line_lnum - 1, curbuf->b_u_line_lnum + 1, (linenr_t)0);
X    old = u_save_line(curbuf->b_u_line_lnum);
X    if (old == NULL)
X        return;
X    ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, TRUE);
X    u_free_line(curbuf->b_u_line_ptr);
X    curbuf->b_u_line_ptr = old;
X
X    t = curbuf->b_u_line_colnr;
X    if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
X        curbuf->b_u_line_colnr = curwin->w_cursor.col;
X    curwin->w_cursor.col = t;
X    curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
X    cursupdate();
X    updateScreen(VALID_TO_CURSCHAR);
X}
X
X/*
X * storage allocation for the undo lines and blocks of the current file
X */
X
X/*
X * Memory is allocated in relatively large blocks. These blocks are linked
X * in the allocated block list, headed by curbuf->b_block_head. They are all freed
X * when abandoning a file, so we don't have to free every single line. The
X * list is kept sorted on memory address.
X * block_alloc() allocates a block.
X * m_blockfree() frees all blocks.
X *
X * The available chunks of memory are kept in free chunk lists. There is
X * one free list for each block of allocated memory. The list is kept sorted
X * on memory address.
X * u_alloc_line() gets a chunk from the free lists.
X * u_free_line() returns a chunk to the free lists.
X * curbuf->b_m_search points to the chunk before the chunk that was
X * freed/allocated the last time.
X * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
X * points into the free list.
X *
X *
X *  b_block_head     /---> block #1     /---> block #2
X *       mb_next ---/       mb_next ---/       mb_next ---> NULL
X *       mb_info            mb_info            mb_info
X *          |                  |                  |
X *          V                  V                  V
X *        NULL          free chunk #1.1      free chunk #2.1
X *                             |                  |
X *                             V                  V
X *                      free chunk #1.2          NULL
X *                             |
X *                             V
X *                            NULL
X *
X * When a single free chunk list would have been used, it could take a lot
X * of time in u_free_line() to find the correct place to insert a chunk in the
X * free list. The single free list would become very long when many lines are
X * changed (e.g. with :%s/^M$//).
X */
X
X    /*
X     * this blocksize is used when allocating new lines
X     */
X#define MEMBLOCKSIZE 2044
X
X/*
X * The size field contains the size of the chunk, including the size field itself.
X *
X * When the chunk is not in-use it is preceded with the m_info structure.
X * The m_next field links it in one of the free chunk lists.
X *
X * On most unix systems structures have to be longword (32 or 64 bit) aligned.
X * On most other systems they are short (16 bit) aligned.
X */
X
X/* the structure definitions are now in structs.h */
X
X#ifdef ALIGN_LONG
X    /* size of m_size */
X# define M_OFFSET (sizeof(long_u))
X#else
X    /* size of m_size */
X# define M_OFFSET (sizeof(short_u))
X#endif
X
X/*
X * Allocate a block of memory and link it in the allocated block list.
X */
X    static char_u *
Xu_blockalloc(size)
X    long_u    size;
X{
X    struct m_block *p;
X    struct m_block *mp, *next;
X
X    p = (struct m_block *)lalloc(size + sizeof(struct m_block), TRUE);
X    if (p != NULL)
X    {
X         /* Insert the block into the allocated block list, keeping it
X                     sorted on address. */
X        for (mp = &curbuf->b_block_head; (next = mp->mb_next) != NULL && next < p; mp = next)
X            ;
X        p->mb_next = next;                /* link in block list */
X        mp->mb_next = p;
X        p->mb_info.m_next = NULL;        /* clear free list */
X        p->mb_info.m_size = 0;
X        curbuf->b_mb_current = p;        /* remember current block */
X        curbuf->b_m_search = NULL;
X        p++;                            /* return usable memory */
X    }
X    return (char_u *)p;
X}
X
X/*
X * free all allocated memory blocks for the buffer 'buf'
X */
X    void
Xu_blockfree(buf)
X    BUF        *buf;
X{
X    struct m_block    *p, *np;
X
X    for (p = buf->b_block_head.mb_next; p != NULL; p = np)
X    {
X        np = p->mb_next;
X        free(p);
X    }
X    buf->b_block_head.mb_next = NULL;
X    buf->b_m_search = NULL;
X    buf->b_mb_current = NULL;
X}
X
X/*
X * Free a chunk of memory.
X * Insert the chunk into the correct free list, keeping it sorted on address.
X */
X    static void
Xu_free_line(ptr)
X    char_u *ptr;
X{
X    register info_t        *next;
X    register info_t        *prev, *curr;
X    register info_t        *mp;
X    struct m_block        *nextb;
X
X    if (ptr == NULL || ptr == IObuff)
X        return;    /* illegal address can happen in out-of-memory situations */
X
X    mp = (info_t *)(ptr - M_OFFSET);
X
X        /* find block where chunk could be a part off */
X        /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
X    if (curbuf->b_mb_current == NULL || mp < (info_t *)curbuf->b_mb_current)
X    {
X        curbuf->b_mb_current = curbuf->b_block_head.mb_next;
X        curbuf->b_m_search = NULL;
X    }
X    if ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
X    {
X        curbuf->b_mb_current = nextb;
X        curbuf->b_m_search = NULL;
X    }
X    while ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
X        curbuf->b_mb_current = nextb;
X
X    curr = NULL;
X    /*
X     * If mp is smaller than curbuf->b_m_search->m_next go to the start of
X     * the free list
X     */
X    if (curbuf->b_m_search == NULL || mp < (curbuf->b_m_search->m_next))
X        next = &(curbuf->b_mb_current->mb_info);
X    else
X        next = curbuf->b_m_search;
X    /*
X     * The following loop is executed very often.
X     * Therefore it has been optimized at the cost of readability.
X     * Keep it fast!
X     */
X#ifdef SLOW_BUT_EASY_TO_READ
X    do
X    {
X        prev = curr;
X        curr = next;
X        next = next->m_next;
X    }
X    while (mp > next && next != NULL);
X#else
X    do                                        /* first, middle, last */
X    {
X        prev = next->m_next;                /* curr, next, prev */
X        if (prev == NULL || mp <= prev)
X        {
X            prev = curr;
X            curr = next;
X            next = next->m_next;
X            break;
X        }
X        curr = prev->m_next;                /* next, prev, curr */
X        if (curr == NULL || mp <= curr)
X        {
X            prev = next;
X            curr = prev->m_next;
X            next = curr->m_next;
X            break;
X        }
X        next = curr->m_next;                /* prev, curr, next */
X    }
X    while (mp > next && next != NULL);
X#endif
X
X/* if *mp and *next are concatenated, join them into one chunk */
X    if ((char_u *)mp + mp->m_size == (char_u *)next)
X    {
X        mp->m_size += next->m_size;
X        mp->m_next = next->m_next;
X    }
X    else
X        mp->m_next = next;
X
X/* if *curr and *mp are concatenated, join them */
X    if (prev != NULL && (char_u *)curr + curr->m_size == (char_u *)mp)
X    {
X        curr->m_size += mp->m_size;
X        curr->m_next = mp->m_next;
X        curbuf->b_m_search = prev;
X    }
X    else
X    {
X        curr->m_next = mp;
X        curbuf->b_m_search = curr;    /* put curbuf->b_m_search before freed chunk */
X    }
X}
X
X/*
X * Allocate and initialize a new line structure with room for at least
X * 'size' characters plus a terminating NUL.
X */
X    static char_u *
Xu_alloc_line(size)
X    register unsigned size;
X{
X    register info_t *mp, *mprev, *mp2;
X    struct m_block    *mbp;
X    int                 size_align;
X
X/*
X * Add room for size field and trailing NUL byte.
X * Adjust for minimal size (must be able to store info_t
X * plus a trailing NUL, so the chunk can be released again)
X */
X    size += M_OFFSET + 1;
X    if (size < sizeof(info_t) + 1)
X      size = sizeof(info_t) + 1;
X
X/*
X * round size up for alignment
X */
X    size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
X
X/*
X * If curbuf->b_m_search is NULL (uninitialized free list) start at
X * curbuf->b_block_head
X */
X    if (curbuf->b_mb_current == NULL || curbuf->b_m_search == NULL)
X    {
X        curbuf->b_mb_current = &curbuf->b_block_head;
X        curbuf->b_m_search = &(curbuf->b_block_head.mb_info);
X    }
X
X/* search for space in free list */
X    mprev = curbuf->b_m_search;
X    mbp = curbuf->b_mb_current;
X    mp = curbuf->b_m_search->m_next;
X    if (mp == NULL)
X    {
X        if (mbp->mb_next)
X            mbp = mbp->mb_next;
X        else
X            mbp = &curbuf->b_block_head;
X        mp = curbuf->b_m_search = &(mbp->mb_info);
X    }
X    while (mp->m_size < size)
X    {
X        if (mp == curbuf->b_m_search)        /* back where we started in free chunk list */
X        {
X            if (mbp->mb_next)
X                mbp = mbp->mb_next;
X            else
X                mbp = &curbuf->b_block_head;
X            mp = curbuf->b_m_search = &(mbp->mb_info);
X            if (mbp == curbuf->b_mb_current)    /* back where we started in block list */
X            {
X                int        n = (size_align > (MEMBLOCKSIZE / 4) ? size_align : MEMBLOCKSIZE);
X
X                mp = (info_t *)u_blockalloc((long_u)n);
X                if (mp == NULL)
X                    return (NULL);
X                mp->m_size = n;
X                u_free_line((char_u *)mp + M_OFFSET);
X                mp = curbuf->b_m_search;
X                mbp = curbuf->b_mb_current;
X            }
X        }
X        mprev = mp;
X        if ((mp = mp->m_next) == NULL)        /* at end of the list */
X            mp = &(mbp->mb_info);            /* wrap around to begin */
X    }
X
X/* if the chunk we found is large enough, split it up in two */
X    if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
X    {
X        mp2 = (info_t *)((char_u *)mp + size_align);
X        mp2->m_size = mp->m_size - size_align;
X        mp2->m_next = mp->m_next;
X        mprev->m_next = mp2;
X        mp->m_size = size_align;
X    }
X    else                    /* remove *mp from the free list */
X    {
X        mprev->m_next = mp->m_next;
X    }
X    curbuf->b_m_search = mprev;
X    curbuf->b_mb_current = mbp;
X
X    mp = (info_t *)((char_u *)mp + M_OFFSET);
X    *(char_u *)mp = NUL;                    /* set the first byte to NUL */
X
X    return ((char_u *)mp);
X}
X
X/*
X * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum' into it.
X */
X    static char_u *
Xu_save_line(lnum)
X    linenr_t    lnum;
X{
X    register char_u *src;
X    register char_u *dst;
X    register unsigned len;
X
X    src = ml_get(lnum);
X    len = STRLEN(src);
X    if ((dst = u_alloc_line(len)) != NULL)
X        memmove((char *)dst, (char *)src, (size_t)(len + 1));
X    return (dst);
X}
END_OF_FILE
  if test 24811 -ne `wc -c <'vim/src/undo.c'`; then
    echo shar: \"'vim/src/undo.c'\" unpacked with wrong size!
  fi
  # end of 'vim/src/undo.c'
fi
echo shar: End of archive 11 \(of 26\).
cp /dev/null ark11isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 26 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...