static char rcsid[] = "$Id: undo.c,v 1.2 1992/11/11 20:39:26 mike Exp $";

/* $Log: undo.c,v $
 * Revision 1.2  1992/11/11  20:39:26  mike
 * - Fixed bug: Under certain circumstances the variable `qtr' in `open_bag'
 *   wasn't initialized. After an assignment to `drag' this caused strange
 *   things to happen when `drag->next' was assigned a value.
 *
 * Revision 1.1  1992/09/05  01:13:32  mike
 * Initial revision
 *
 */

/* 
 * Undo.c : 
 * Track changes to a buffer so that they may be reversed if somebody should
 *   desire to do so.
 * Only buffer CHANGES are tracked, not cursor movement, etc.
 * Undo events are stacked.
 * C Durland  1/91
 */

/* Copyright 1990, 1991, 1992 Craig Durland
 *   Distributed under the terms of the GNU General Public License.
 *   Distributed "as is", without warranties of any kind, but comments,
 *     suggestions and bug reports are welcome.
 */

/* Things to think about:
 *   Toggling the changed bit (like to get the modeline hook called).  Will
 *     this cause problems?
 *   Since can modify flags on other than current buffer, will lose undo
 *     events?
 *   Might want to put buffer change state into the sequence points.
 *   If diddle the middle of a block then delete the block (or clear the
 *     buffer), can't undo the diddle because marks don't point into the
 *     block anymore.  I think GNU can do this because they could queue the
 *     marks (offsets into the buffer) and never update them knowing that
 *     when undo() got to them, they would be correct (again).
 *   To fix above problem, might have to dump marks and track cursor
 *     movement.  next_char, next_line, goto_EoB, goto_BoB, goto_EoL,
 *     goto_BoB, probably others.  The stinkers are some of the window moves
 *     and how they affect the dot (sync_wdot) and the code in main()
 *     (sync_dot).
 *   Another solution is to keep track of the (line number,offset in line)
 *     pair for each insert, delete.  Then everything works ala buffer gap
 *     but sucks in that these unmarks have to be calculated at every
 *     insert, delete event.  It might be worth it to try and track these as
 *     much as possible and keep a global to indicate if they are insync.
 *     Note that you only have to track line changes because offset in the
 *     line is done already.
 *   Problem:  The save_for_undo() caller might lie about how much is going
 *     to be deleted.  This is a simple thing to check with buffer gap
 *     (buffer_size -dot) but time comsuming to do with linked list.  So
 *     with linked list, assume first and check after and if they lie, its
 *     their problem (the undo stack may be cleaned to make more room than
 *     was needed).
 *   A problem related to the don't-know-how-much-is-going-to-be-deleted
 *     problem is the clear-buffer problem.  With buffer gap, you know how
 *     much you are going to remove, with linked list, you don't.  So, I
 *     just clear the undo stack when the buffer is cleared because 1) most
 *     buffers will probably max the undo buffer anyway and cause it to be
 *     cleared and 2) buffer clears don't happen very often - usually for
 *     buffer deletes and file reads.
 *   How do I undo the change case commands?
 *   Rules for sequence points:
 *     A sequence point is a marker in the undo stack that marks when to
 *       stop undoing.
 *     Need sequence points so undoing stops at "natural, expected" places.
 *     Should stop where user explicitly marked the buffer as unchanged
 *       (like save buffer to disk).
 *     A string of self insert keys should undo as one.  Pretty annoying to
 *       have to hit undo 14 times to undo "this is a test".
 *     A word wrap or Return would break a character stream.  This would
 *     undo only back up a line at at time, probably better than undo an
 *       entire paragraph when only one line needed undoing.
 *     Commands, pgms, etc should undo as a unit.  ie if pressing a key
 *       caused a bunch of stuff to happen, pressing undo should undo all
 *       the stuff the key caused.
 *     Since rules can't cover all cases (like query replace), pgms need to
 *       be able to add sequence points.
 */

/* 
 * WARNINGS:
 *   do_undo flags MUST be maintained and current.  This implies that only
 *     use_buffer() can change the current buffer.
 */

#include "me2.h"

extern char *bag_text();

static int push_undo(), open_bag(), stuff_bag();
static void free_undo(), goto_unmark(), set_unmark(), pack_bag(), gc_undos();

int do_undo = FALSE; /* Global flag.  True if saving undo for current buffer */

int max_undos = 600, max_undo_saved = 6000;

/* ******************************************************************** */
/* ****************** Data structures ********************************* */
/* ******************************************************************** */

typedef struct
{
  int32 line;		/* the line that changed (first line is 1) */
  int offset;		/* offset in the line of the change */
} UnMark;

typedef struct Undo
{
  struct Undo *next;
  int type;
  UnMark mark;			/* where the event took place */
  int32 n;			/* number of characters involved */
  int text_offset;		/* offset into bag where deleted text saved */
} Undo;

typedef struct
{
  Undo *undo_stack;		/* where the undo events are */
  int undo_count;		/* number of undos in the stack */
  Bag *bag;			/* deleted text saved here */
  int valid_safe_point_in_stack;	/* last UNCHANGED matches disk */
} UndoHeader;

#define FIRST_UNDO(bp) ((UndoHeader *)bp->undos)->undo_stack
#define THE_BAG ((UndoHeader *)curbp->undos)->bag

/* ******************************************************************** */
/* ******************************************************************** */
/* ******************************************************************** */

    /* Undo something in the current buffer.
     * Returns:
     *   0 : Nothing happened (despite my best efforts)
     *   1 : Something happened (ie something was undid)
     *   2 : Problems
     * Notes:
     *   UNCHANGED is a no-op if the buffer is not modified.  This makes
     *   <save buffer><undo> work "nicer" and allows some other tricks.
     */
int undo()
{
  int undo_flag, num_events, something_happened, push_an_unchanged;
  Undo *ptr;

  thisflag |= CFUNDO;
  
  if (!do_undo	||			/* Undo turned off */
      !(ptr = FIRST_UNDO(curbp)))	/* or nothing to undo */
    return 0;

  undo_flag = do_undo; do_undo = FALSE;

  num_events = 0;
  something_happened = FALSE;
  push_an_unchanged = FALSE;

  for (; ptr; ptr = ptr->next)
  {
    num_events++;

    switch (ptr->type)
    {
      case BU_INSERT:		/* To undo: Delete inserted characters */
	something_happened = TRUE;
	goto_unmark(&ptr->mark);
  /* create an undo event? Let ldelete do it? */
	ldelete(ptr->n,FALSE);
	break;
      case BU_DELETE:		/* To undo: Insert deleted characters */
	something_happened = TRUE;
	goto_unmark(&ptr->mark);
/* create an redo event? or let insert (etc) do it? */
/* !!! error check (and do what?) */
	insert_block(bag_text(THE_BAG) +ptr->text_offset, ptr->n);
	break;
      case BU_UNCHANGED:    /* At this point, the buffer might be unchanged */
      {
	UndoHeader *header;

	header = curbp->undos;
	if (header->valid_safe_point_in_stack && is_buffer_modified(curbp))
	{
	  set_buffer_modified(curbp,FALSE);
          push_an_unchanged = TRUE;
	  something_happened = TRUE;
	}
	header->valid_safe_point_in_stack = FALSE;
      }
	/* fall through:  a BU_UNCHANGED also acts like a sequence point */
      case BU_SP:	/* Hit a sequence point, stop undoing */
	if (something_happened)
	{
	  ptr = ptr->next;	/* so I can check for empty stack */
	  goto done;
	}
	break;
    }
  }

done:

  gc_undos(num_events);

  do_undo = undo_flag;

  if (push_an_unchanged || (!ptr && !is_buffer_modified(curbp)))
	save_for_undo(BU_UNCHANGED,(int32)0);

  return something_happened;
}

    /* Call this before the action actually is done.
     * Event are to the current buffer at the dot.
     * Returns:
     *   TRUE:  everything went as expected.
     *   FALSE: out of mem or something and stopped undos or nuked this
     *     event or nuked the entire stack.
     */
save_for_undo(type,n) int type; int32 n;
{
  Undo undo, *ptr;
  UnMark mark;

  if (!do_undo) return TRUE;

#if 0	/* ??? */
  if (!(lastflag & UNDO)) pack_redos_with_undos();
  thisflag |= ???;
#endif

  ptr = FIRST_UNDO(curbp);

  switch (type)
  {
    case BU_INSERT:			/* Characters inserted */
      set_unmark(&mark);
      if (ptr && ptr->type == BU_INSERT &&
          ptr->mark.line == mark.line &&
	  ptr->mark.offset + ptr->n == mark.offset)
      {
	ptr->n += n;
	return TRUE;
      }
      undo.n = n;
      undo.mark = mark;
      break;
    case BU_DELETE:				/* Characters deleted */
    {
      Bag *bag;
      int z;
      UndoHeader *header;

      if (n == 0) return TRUE;		/* that was easy! */

      header = curbp->undos;
      bag = header->bag;
      set_unmark(&mark);

#if 0	/* don't pack undos - too big a pain */
      if (ptr && ptr->type == BU_DELETE &&
          ptr->mark.line == mark.line &&
	  ptr->mark.offset + ptr->n == mark.offset)
      {
	undo.n += n;
	s = stuff_bag(bag,n);
	if (s) { z = bag_size(bag) -z; ptr->n += z; }
	return s;
      }
#endif

      if (!open_bag(n)) return FALSE;

      z = bag_size(bag);

      undo.mark = mark;
      undo.text_offset = z;

      if (!stuff_bag(bag,n)) return FALSE;

      z = bag_size(bag) -z;
      undo.n = z;	/* in case of lies */

      break;
    }
    case BU_SP:					/* Set sequence point */
	   /* If last event is also a sequence point or buffer OK, ignore
	    * this one.
	    */
      if (ptr && (ptr->type == BU_SP || ptr->type == BU_UNCHANGED)) return TRUE;
      break;
    case BU_UNCHANGED:			/* Buffer has been marked safe */
    {
      UndoHeader *header;

		/* if last event is the same, ignore this one */
      if (ptr && ptr->type == BU_UNCHANGED) return TRUE;

      header = curbp->undos;
      header->valid_safe_point_in_stack = TRUE;

      break;
    }
  }

  undo.type = type;

  return push_undo(&undo);
}

/* ******************************************************************** */
/* ****************** Undo init and start up ************************** */
/* ******************************************************************** */

void init_buffer_undos(bp) Buffer *bp;
{
  bp->undos = NULL;
}

    /* Turn on undos for buffer bp.  Sets the buffer flags if successful.
     * Create a undo header and init it.
     * Returns:
     *   TRUE:  everything went as expected.
     *   FALSE: memory problem.
     */
alloc_buffer_undos(bp) Buffer *bp;
{
  UndoHeader *header;

  if (bp->b_flags & BFUNDO) return TRUE;	/* undo already turned on! */

  if (!(header = (UndoHeader *)malloc(sizeof(UndoHeader))))	return FALSE;
  if (!(header->bag = alloc_bag(TRUE))) { free((char *)header); return FALSE; }

  header->undo_count = 0;
  header->undo_stack = NULL;
  header->valid_safe_point_in_stack = FALSE;

  bp->undos = header;

  bp->b_flags |= BFUNDO;	/* This buffer now has undo */

  if (bp == curbp)
  {
    do_undo = TRUE;
    if (!is_buffer_modified(curbp)) save_for_undo(BU_UNCHANGED,(int32)0);
  }

  return TRUE;
}

void clear_undos(bp) Buffer *bp;
{
  Undo *ptr, *bu1;
  UndoHeader *header = bp->undos;

  if (!(bp->b_flags & BFUNDO)) return;		/* undo already turned off! */

  for (ptr = header->undo_stack; ptr; ptr = bu1)
  {
    bu1 = ptr->next;	/* since pointer is gone after free_undo() */
    free_undo(bp,ptr);
  }
  header->undo_count = 0;
  header->undo_stack = NULL;
  header->valid_safe_point_in_stack = FALSE;

  clear_bag(header->bag);
}

void free_buffer_undos(bp) Buffer *bp;
{
  if (!(bp->b_flags & BFUNDO)) return;		/* undo already turned off! */

  clear_undos(bp);

  {
    UndoHeader *header = bp->undos;

    free_bag(header->bag);
    free((char *)header);
  }

  if (bp == curbp) do_undo = FALSE;

  bp->b_flags &= ~BFUNDO;
}

/* ******************************************************************** */
/* ****************** UnMarks ***************************************** */
/* ******************************************************************** */

static void goto_unmark(mark) UnMark *mark;
{
  goto_line((int)mark->line);
  next_character(mark->offset);
}

#if 1
static void set_unmark(mark) UnMark *mark;
{
  register Line *lp, *dot_line;
  register int line;

  dot_line = the_dot->line;
  for (line = 1, lp = BUFFER_FIRST_LINE(curbp); lp != dot_line;
	lp = lp->l_next) 
    line++;

  mark->line = line;
  mark->offset = the_dot->offset;
}
#else
/* gotta reset dot_line at in use_buffer() */
Line *dot_line = NULL;
static void set_unmark(mark) UnMark *mark;
{
  static int line;

  register Line *lp;

  if (dot_line != the_dot->line)
  {
    dot_line = the_dot->line;
    for (line = 1, lp = BUFFER_FIRST_LINE(curbp); lp != dot_line;
	 lp = lp->l_next) 
      line++;
  }
  mark->line = line;
  mark->offset = the_dot->offset;
}
#endif

/* ******************************************************************** */
/* ************* Undo stack details *********************************** */
/* ******************************************************************** */

#define MNX 100
static Undo *freed_undos = NULL;

/* !!!  I could really use a generic linked list manager for:  marks,
 * buffers, windows and undos
 */

   /* Allocate a undo event.  You need to set the undo data.
    * Returns:
    *   Pointer to the allocated mark.
    *   NULL if can't malloc().
    */
#if 0

extern void *llist_alloc();
#define alloc_undo() llist_alloc(&freed_undos, sizeof(Undo), MNX)

#else

static Undo *alloc_undo()
{
  Undo *undo;

  if (freed_undos)		/* there are undos in the free pool */
  {
    undo = freed_undos;
    freed_undos = freed_undos->next;
  }
  else		/* malloc a bunch of undos and put extras in free list */
  {
    int j;
    Undo *ptr;

    if (!(undo = (Undo *)malloc(MNX * sizeof(Undo)))) return NULL;
    for (j = MNX-1, ptr = undo +1; j--; ptr++)
    {
      ptr->next = freed_undos;
      freed_undos = ptr;
    }
  }

  return undo;
}
#endif

    /* Free up resources used by a undo event and put it into the free pool.
     */
static void free_undo(bp,undo) Buffer *bp; Undo *undo;
{
  undo->next = freed_undos;
  freed_undos = undo;
}


    /* Allocate a undo event and push it onto the undo stack for the current
     *   buffer.  If the stack is at the max allowed size, remove the oldest
     *   event and reuse it.  Else actually allocate an event.  If
     *   allocation fails, we are probably out of memory so free the undo
     *   stack and turn off undos on the assumption that undo is not
     *   necessary and somebody else will need the memory more.
     * Returns:
     *   TRUE:  
     *   FALSE:  Ran out of memory, freed undo stack.
     */
static int push_undo(undo) Undo *undo;
{
  Undo *ptr;
  UndoHeader *header;

  header = curbp->undos;

  if (header->undo_count == max_undos)		/* remove 1 event */
  {
    Undo *qtr;

    for (ptr = header->undo_stack; ptr->next; ptr = ptr->next) qtr = ptr;
    qtr->next = NULL;
    if (ptr->type == BU_DELETE)
    {
      undo->text_offset -= (ptr->n);	/* adjust this event */
      pack_bag((int)ptr->n);		/* adjust the rest of the stack */
    }
  }
  else
  {
    if (!(ptr = alloc_undo()))
    {
      free_buffer_undos(curbp);
      mlwrite("Out of memory!  Undo turned off for buffer!");
      return FALSE;
    }
    header->undo_count++;
  }
  *ptr = *undo;

  ptr->next = header->undo_stack;
  header->undo_stack = ptr;

  return TRUE;
}

    /* Garbage collect num_events from the front of the undo stack ie pop
     *   num_events.  Pack the bag as needed.
     */
static void gc_undos(num_events)
{
  int n;
  Undo *ptr, *next;
  UndoHeader *header;

  header = curbp->undos;

  for (n = 0, ptr = header->undo_stack; ptr && num_events--; ptr = next)
  {
    next = ptr->next;

    header->undo_count--;
    if (ptr->type == BU_DELETE) n += ptr->n;
    free_undo(curbp,ptr);
  }

  header->undo_stack = ptr;
  if (n) trim_bag(header->bag,n);
}

    /* Check to see if space_needed is available in the bag.  If not, try
     *   and pack the bag and stack to make enough room.  If more space is
     *   requested than we allow, clear the stack because if we can't save
     *   this undo, every undo before this one is invalid.
     * Returns:
     *   TRUE:  Bag (now) has enough room.
     *   FALSE:  You want too much space and can't have it.  Undo stack
     *     cleared.  Try again with a more reasonable request.
     */
static int open_bag(space_needed) int32 space_needed;
{
  int tot, da_total, total_so_far;
  Undo *ptr, *next, *qtr, *da_winner, *drag;
  UndoHeader *header;

  header = curbp->undos;

  total_so_far = bag_size(header->bag);
  tot = space_needed -(max_undo_saved -total_so_far);

  if (tot <= 0) return TRUE;			/* Plenty of room! */

  if (space_needed > max_undo_saved)		/* You want too much! */
  {
    clear_undos(curbp);
    return FALSE;
  }

  qtr = NULL;
  da_winner = NULL;
  for (ptr = header->undo_stack; ptr; ptr = ptr->next)
  {
    if (ptr->type == BU_DELETE)
    {
      if (total_so_far >= tot)	/* found enough space here */
      {
	da_winner = ptr;
	da_total = total_so_far;
	drag = qtr;		/* won't do this until qtr is set */
      }
      else break;		/* the last one was the one we wanted */
      total_so_far -= ptr->n;
    }
    qtr = ptr;
  }

      /* We KNOW (and can prove it) that da_winner != NULL because
       *   bag_size >= tot > max - bag_size
       *   (from max_undo_saved >= space_needed > max_undo_saved -bag_size
       *   among other things).  Since bag_size is the sum of all the
       *   BU_DELETEs, there must be one or more events that are winners.
       */
  {
    for (ptr = da_winner; ptr; ptr = next)
    {
      next = ptr->next;
      header->undo_count--;
      free_undo(curbp,ptr);
    }
    if (drag != NULL)
      drag->next = NULL;
    pack_bag(da_total);
  }

  return TRUE;
}

/* ******************************************************************** */
/* ************* Gory details ***************************************** */
/* ******************************************************************** */

static int stuff_bag(bag,n) Bag *bag; int32 n;
{
  if (!copy_region_to_bag(the_dot,n, bag))	/* bag overflow */
  {
    free_buffer_undos(curbp);
    mlwrite("Out of memory!  Undo turned off for buffer!");
    return FALSE;
  }
  return TRUE;
}

    /* Go though the undo stack and adjust the text indices to reflect n
     * characters being removed from the front of the bag.  Shift n
     * characters off the front of the bag.
     */
static void pack_bag(n) int n;
{
  Undo *ptr;
  UndoHeader *header;

  header = curbp->undos;
  
  for (ptr = header->undo_stack; ptr; ptr = ptr->next)
    if (ptr->type == BU_DELETE)
    {
      ptr->text_offset -= n;
    }

  slide_bag(header->bag,n);
}