undo.c

VIM文本编辑器

/* vi:set ts=8 sts=4 sw=4:
 *
 * VIM - Vi IMproved	by Bram Moolenaar
 *
 * Do ":help uganda"  in Vim to read copying and usage conditions.
 * Do ":help credits" in Vim to see a list of people who contributed.
 */

/*
 * undo.c: multi level undo facility
 *
 * The saved lines are stored in a list of lists (one for each buffer):
 *
 * b_u_oldhead------------------------------------------------+
 *							      |
 *							      V
 *		  +--------------+    +--------------+	  +--------------+
 * b_u_newhead--->| u_header	 |    | u_header     |	  | u_header	 |
 *		  |	uh_next------>|     uh_next------>|	uh_next---->NULL
 *	   NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
 *		  |	uh_entry |    |     uh_entry |	  |	uh_entry |
 *		  +--------|-----+    +--------|-----+	  +--------|-----+
 *			   |		       |		   |
 *			   V		       V		   V
 *		  +--------------+    +--------------+	  +--------------+
 *		  | u_entry	 |    | u_entry      |	  | u_entry	 |
 *		  |	ue_next  |    |     ue_next  |	  |	ue_next  |
 *		  +--------|-----+    +--------|-----+	  +--------|-----+
 *			   |		       |		   |
 *			   V		       V		   V
 *		  +--------------+	      NULL		  NULL
 *		  | u_entry	 |
 *		  |	ue_next  |
 *		  +--------|-----+
 *			   |
 *			   V
 *			  etc.
 *
 * Each u_entry list contains the information for one undo or redo.
 * curbuf->b_u_curhead points to the header of the last undo (the next redo),
 * or is NULL if nothing has been undone.
 *
 * All data is allocated with u_alloc_line(), thus it will be freed as soon as
 * we switch files!
 */

#include "vim.h"

static void u_getbot __ARGS((void));
static int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
static void u_doit __ARGS((int count));
static void u_undoredo __ARGS((void));
static void u_undo_end __ARGS((void));
static void u_freelist __ARGS((struct u_header *));
static void u_freeentry __ARGS((struct u_entry *, long));

static char_u *u_blockalloc __ARGS((long_u));
static void u_free_line __ARGS((char_u *));
static char_u *u_alloc_line __ARGS((unsigned));
static char_u *u_save_line __ARGS((linenr_t));

static long	u_newcount, u_oldcount;

/*
 * When 'u' flag included in 'cpoptions', we behave like vi.  Need to remember
 * the action that "u" should do.
 */
static int	undo_undoes = FALSE;

/*
 * save the current line for both the "u" and "U" command
 */
    int
u_save_cursor()
{
    return (u_save((linenr_t)(curwin->w_cursor.lnum - 1),
				      (linenr_t)(curwin->w_cursor.lnum + 1)));
}

/*
 * Save the lines between "top" and "bot" for both the "u" and "U" command.
 * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
 * Returns FAIL when lines could not be saved, OK otherwise.
 */
    int
u_save(top, bot)
    linenr_t top, bot;
{
    if (undo_off)
	return OK;

    if (top > curbuf->b_ml.ml_line_count ||
			    top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
	return FALSE;	/* rely on caller to do error messages */

    if (top + 2 == bot)
	u_saveline((linenr_t)(top + 1));

    return (u_savecommon(top, bot, (linenr_t)0));
}

/*
 * save the line "lnum" (used by :s command)
 * The line is replaced, so the new bottom line is lnum + 1.
 */
    int
u_savesub(lnum)
    linenr_t	lnum;
{
    if (undo_off)
	return OK;

    return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
}

/*
 * a new line is inserted before line "lnum" (used by :s command)
 * The line is inserted, so the new bottom line is lnum + 1.
 */
    int
u_inssub(lnum)
    linenr_t	lnum;
{
    if (undo_off)
	return OK;

    return (u_savecommon(lnum - 1, lnum, lnum + 1));
}

/*
 * save the lines "lnum" - "lnum" + nlines (used by delete command)
 * The lines are deleted, so the new bottom line is lnum, unless the buffer
 * becomes empty.
 */
    int
u_savedel(lnum, nlines)
    linenr_t	lnum;
    long	nlines;
{
    if (undo_off)
	return OK;

    return (u_savecommon(lnum - 1, lnum + nlines,
			nlines == curbuf->b_ml.ml_line_count ? 2 : lnum));
}

    static int
u_savecommon(top, bot, newbot)
    linenr_t top, bot;
    linenr_t newbot;
{
    linenr_t	    lnum;
    long	    i;
    struct u_header *uhp;
    struct u_entry  *uep;
    long	    size;

    /*
     * if curbuf->b_u_synced == TRUE make a new header
     */
    if (curbuf->b_u_synced)
    {
	/*
	 * if we undid more than we redid, free the entry lists before and
	 * including curbuf->b_u_curhead
	 */
	while (curbuf->b_u_curhead != NULL)
	    u_freelist(curbuf->b_u_newhead);

	/*
	 * free headers to keep the size right
	 */
	while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
	    u_freelist(curbuf->b_u_oldhead);

	if (p_ul < 0)		/* no undo at all */
	    return OK;

	/*
	 * make a new header entry
	 */
	uhp = (struct u_header *)u_alloc_line((unsigned)
						     sizeof(struct u_header));
	if (uhp == NULL)
	    goto nomem;
	uhp->uh_prev = NULL;
	uhp->uh_next = curbuf->b_u_newhead;
	if (curbuf->b_u_newhead != NULL)
	    curbuf->b_u_newhead->uh_prev = uhp;
	uhp->uh_entry = NULL;
	uhp->uh_cursor = curwin->w_cursor;	/* save cursor pos. for undo */

	/* save changed and buffer empty flag for undo */
	uhp->uh_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
		       ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);

	/* save named marks for undo */
	mch_memmove(uhp->uh_namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS);
	curbuf->b_u_newhead = uhp;
	if (curbuf->b_u_oldhead == NULL)
	    curbuf->b_u_oldhead = uhp;
	++curbuf->b_u_numhead;
    }
    else    /* find line number for ue_bot for previous u_save() */
	u_getbot();

    size = bot - top - 1;
#if !defined(UNIX) && !defined(DJGPP) && !defined(WIN32) && !defined(__EMX__)
	/*
	 * With Amiga and MSDOS 16 bit we can't handle big undo's, because
	 * then u_alloc_line would have to allocate a block larger than 32K
	 */
    if (size >= 8000)
	goto nomem;
#endif

    /*
     * add lines in front of entry list
     */
    uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
    if (uep == NULL)
	goto nomem;

    uep->ue_size = size;
    uep->ue_top = top;
    uep->ue_lcount = 0;
    if (newbot)
	uep->ue_bot = newbot;
	/*
	 * Use 0 for ue_bot if bot is below last line.
	 * Otherwise we have to compute ue_bot later.
	 */
    else if (bot > curbuf->b_ml.ml_line_count)
	uep->ue_bot = 0;
    else
	uep->ue_lcount = curbuf->b_ml.ml_line_count;

    if (size)
    {
	if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
	{
	    u_freeentry(uep, 0L);
	    goto nomem;
	}
	for (i = 0, lnum = top + 1; i < size; ++i)
	{
	    if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
	    {
		u_freeentry(uep, i);
		goto nomem;
	    }
	}
    }
    uep->ue_next = curbuf->b_u_newhead->uh_entry;
    curbuf->b_u_newhead->uh_entry = uep;
    curbuf->b_u_synced = FALSE;
    undo_undoes = FALSE;

    return OK;

nomem:
    if (ask_yesno((char_u *)"No undo possible; continue anyway", TRUE) == 'y')
    {
	undo_off = TRUE;	    /* will be reset when character typed */
	return OK;
    }
    do_outofmem_msg();
    return FAIL;
}

/*
 * If 'cpoptions' contains 'u': Undo the previous undo or redo (vi compatible).
 * If 'cpoptions' does not contain 'u': Always undo.
 */
    void
u_undo(count)
    int count;
{
    /*
     * If we get an undo command while executing a macro, we behave like the
     * original vi. If this happens twice in one macro the result will not
     * be compatible.
     */
    if (curbuf->b_u_synced == FALSE)
    {
	u_sync();
	count = 1;
    }

    if (vim_strchr(p_cpo, CPO_UNDO) == NULL)
	undo_undoes = TRUE;
    else
	undo_undoes = !undo_undoes;
    u_doit(count);
}

/*
 * If 'cpoptions' contains 'u': Repeat the previous undo or redo.
 * If 'cpoptions' does not contain 'u': Always redo.
 */
    void
u_redo(count)
    int count;
{
    if (vim_strchr(p_cpo, CPO_UNDO) == NULL)
	undo_undoes = FALSE;
    u_doit(count);
}

/*
 * Undo or redo, depending on 'undo_undoes', 'count' times.
 */
    static void
u_doit(count)
    int count;
{
    u_newcount = 0;
    u_oldcount = 0;
    while (count--)
    {
	if (undo_undoes)
	{
	    if (curbuf->b_u_curhead == NULL)		/* first undo */
		curbuf->b_u_curhead = curbuf->b_u_newhead;
	    else if (p_ul > 0)				/* multi level undo */
		/* get next undo */
		curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;
	    /* nothing to undo */
	    if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)
	    {
		/* stick curbuf->b_u_curhead at end */
		curbuf->b_u_curhead = curbuf->b_u_oldhead;
		beep_flush();
		break;
	    }

	    u_undoredo();
	}
	else
	{
	    if (curbuf->b_u_curhead == NULL || p_ul <= 0)
	    {
		beep_flush();	/* nothing to redo */
		break;
	    }

	    u_undoredo();
	    /* advance for next redo */
	    curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;
	}
    }
    u_undo_end();
}

/*
 * u_undoredo: common code for undo and redo
 *
 * The lines in the file are replaced by the lines in the entry list at
 * curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
 * list for the next undo/redo.
 */
    static void
u_undoredo()
{
    char_u	**newarray = NULL;
    linenr_t	oldsize;
    linenr_t	newsize;
    linenr_t	top, bot;
    linenr_t	lnum;
    linenr_t	newlnum = MAXLNUM;
    long	i;
    struct u_entry *uep, *nuep;
    struct u_entry *newlist = NULL;
    int		old_flags;
    int		new_flags;
    FPOS	namedm[NMARKS];
    int		empty_buffer;		    /* buffer became empty */

    old_flags = curbuf->b_u_curhead->uh_flags;
    new_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
	       ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
    if (old_flags & UH_CHANGED)
	changed();
    else
	unchanged(curbuf, FALSE);
    setpcmark();
    changed_line_abv_curs();	/* need to recompute cursor posn on screen */

    /*
     * save marks before undo/redo
     */
    mch_memmove(namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS);
    curbuf->b_op_start.lnum = curbuf->b_ml.ml_line_count;
    curbuf->b_op_start.col = 0;
    curbuf->b_op_end.lnum = 0;
    curbuf->b_op_end.col = 0;

    for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
    {
	top = uep->ue_top;
	bot = uep->ue_bot;
	if (bot == 0)
	    bot = curbuf->b_ml.ml_line_count + 1;
	if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
	{
	    EMSG("u_undo: line numbers wrong");
	    changed();		/* don't want UNCHANGED now */
	    return;
	}

	if (top < newlnum)
	{
	    newlnum = top;
	    curwin->w_cursor.lnum = top + 1;
	}
	oldsize = bot - top - 1;    /* number of lines before undo */
	newsize = uep->ue_size;	    /* number of lines after undo */

	empty_buffer = FALSE;

	/* delete the lines between top and bot and save them in newarray */
	if (oldsize)
	{
	    if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
	    {
		do_outofmem_msg();
		/*
		 * We have messed up the entry list, repair is impossible.
		 * we have to free the rest of the list.
		 */
		while (uep != NULL)
		{
		    nuep = uep->ue_next;
		    u_freeentry(uep, uep->ue_size);
		    uep = nuep;
		}
		break;
	    }
	    /* delete backwards, it goes faster in most cases */
	    for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
	    {
		    /* what can we do when we run out of memory? */
		if ((newarray[i] = u_save_line(lnum)) == NULL)
		    do_outofmem_msg();
		    /* remember we deleted the last line in the buffer, and a
		     * dummy empty line will be inserted */
		if (curbuf->b_ml.ml_line_count == 1)
		    empty_buffer = TRUE;
		ml_delete(lnum, FALSE);
	    }
	}

	/* insert the lines in u_array between top and bot */
	if (newsize)
	{
	    for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
	    {
		/*
		 * If the file is empty, there is an empty line 1 that we
		 * should get rid of, by replacing it with the new line
		 */
		if (empty_buffer && lnum == 0)
		    ml_replace((linenr_t)1, uep->ue_array[i], TRUE);
		else
		    ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
		u_free_line(uep->ue_array[i]);
	    }
	    u_free_line((char_u *)uep->ue_array);
	}

	/* adjust marks */
	if (oldsize != newsize)
	{
	    mark_adjust(top + 1, top + oldsize, (linenr_t)MAXLNUM,
					       (long)newsize - (long)oldsize);
	    if (curbuf->b_op_start.lnum > top + oldsize)
		curbuf->b_op_start.lnum += newsize - oldsize;
	    if (curbuf->b_op_end.lnum > top + oldsize)
		curbuf->b_op_end.lnum += newsize - oldsize;
	}
	/* set '[ and '] mark */
	if (top + 1 < curbuf->b_op_start.lnum)
	    curbuf->b_op_start.lnum = top + 1;
	if (newsize == 0 && top + 1 > curbuf->b_op_end.lnum)
	    curbuf->b_op_end.lnum = top + 1;
	else if (top + newsize > curbuf->b_op_end.lnum)
	    curbuf->b_op_end.lnum = top + newsize;

	u_newcount += newsize;
	u_oldcount += oldsize;
	uep->ue_size = oldsize;
	uep->ue_array = newarray;
	uep->ue_bot = top + newsize + 1;

	/*
	 * insert this entry in front of the new entry list
	 */
	nuep = uep->ue_next;
	uep->ue_next = newlist;
	newlist = uep;
    }

    curbuf->b_u_curhead->uh_entry = newlist;
    curbuf->b_u_curhead->uh_flags = new_flags;
    if ((old_flags & UH_EMPTYBUF) && bufempty())
	curbuf->b_ml.ml_flags |= ML_EMPTY;

    /*
     * restore marks from before undo/redo
     */
    for (i = 0; i < NMARKS; ++i)
	if (curbuf->b_u_curhead->uh_namedm[i].lnum)
	{
	    curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
	    curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
	}

    /*
     * If the cursor is only off by one line, put it at the same position as
     * before starting the change (for the "o" command).
     * Otherwise the cursor should go to the first undone line.
     */
    if (curbuf->b_u_curhead->uh_cursor.lnum + 1 == curwin->w_cursor.lnum &&
						    curwin->w_cursor.lnum > 1)
	--curwin->w_cursor.lnum;
    if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
	curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
    else if (curwin->w_cursor.lnum <= curbuf->b_ml.ml_line_count)
	beginline(BL_SOL | BL_FIX);
    /* We still seem to need the case below because sometimes we get here with
     * the current cursor line being one past the end (eg after adding lines
     * at the end of the file, and then undoing it).  Is it fair enough that
     * this happens? -- webb
     */
    else
	curwin->w_cursor.col = 0;

    /* Make sure the cursor is on an existing line and column. */
    adjust_cursor();
}

/*
 * If we deleted or added lines, report the number of less/more lines.
 * Otherwise, report the number of changes (this may be incorrect
 * in some cases, but it's better than nothing).
 */
    static void
u_undo_end()
{
    if ((u_oldcount -= u_newcount) != 0)
	msgmore(-u_oldcount);
    else if (u_newcount > p_report)
	smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));

    update_topline();
    update_curbuf(NOT_VALID);	/* need to update all windows in this buffer */
}

/*
 * u_sync: stop adding to the current entry list
 */
    void