bug#27214: truncate_undo_list in undo.c: exclusions, warnings, documentation.

bug#27214: truncate_undo_list in undo.c: exclusions, warnings, documentation.

[Keith David Bershatsky]

In developing a fork of the popular undo-tree.el library (new features, enhancements, and bug-fixes), I found the following areas in `truncate_undo_list` that could use some improvements:

1.  User-defined exclusions; e.g., a list of elements that will not be truncated unless the user has crossed the `undo-outer-limit' threshold.

    EXAMPLE:

   (defvar truncate-undo-list-exclusions '(undo-tree-canary)
     "A list of user defined elements that will not be truncated during garbage
     collection unless the user has reached the `undo-outer-limit`, in which
     case ....")

2.  User-enabled messages/warnings when truncation is occurring due to the `undo-limit`, or the `undo-strong-limit`, and some type of indication as to what was thrown out.

    EXAMPLE:

   (defvar truncate-undo-list-warnings t
     "When non-nil, the internal function `truncate_undo_list' will generate
      messages letting the user know that he/she has crossed the `undo-limit`
      or `undo-strong-limit`, along with a shortened (redacted) list of
      what is being truncated (mentioning the specific limit crossed).)

3.  Some type of documentation system enabling a user to read about `truncate_undo_list'; e.g., consolidate the comments that are presently only visible if the user visits the source-code and add some additional information about the new features mentioned above.


BACKGROUND:  Here is a reprint of the thread that I launched on emacs.stackexchange.com explaining my use-case and thoughts about a potential workaround:

https://emacs.stackexchange.com/q/33248/2287

**Q**:  How to preserve the last entry in the `buffer-undo-list` when garbage collection occurs?

When using `undo-tree.el`, the library relies upon an `undo-tree-canary` being at the end of the `buffer-undo-list`.  Emacs performs garbage collection **before** the Lisp code in `undo-tree` does its thing -- i.e.,`truncate_undo_list` in `undo.c` is activated and sometimes the `undo-tree-canary` is truncated.  [A good example of this is where there is a programmatic `delete-region` followed by `insert` of significant amounts of different text, such as sorting certain sections of a buffer by `sort-reorder-buffer`, etc.]  The default behavior of `undo-tree` is to begin a new `buffer-undo-tree` when a canary cannot be found -- i.e., the user loses all prior saved history.  [See `undo-list-transfer-to-tree`.]

In looking at the C-source code in `truncate_undo_list` I see the following relevant section from a `while` loop that goes through the `buffer-undo-list` when figuring out whether to truncate before or after an undo-boundary (which is a `nil` entry):

         /* When we get to a boundary, decide whether to truncate
     either before or after it.  The lower threshold, undo_limit,
     tells us to truncate after it.  If its size pushes past
     the higher threshold undo_strong_limit, we truncate before it.  */
         if (NILP (elt))
    {
      if (size_so_far > undo_strong_limit)
        break;
      last_boundary = prev;
      if (size_so_far > undo_limit)
        break;
    }

The relevant default values are as follows:

`undo-limit`:  80000

`undo-strong-limit`:  120000

`undo-outer-limit`:  12000000

It looks like I may be able to set `undo-limit` to *the same value* as `undo-strong-limit` and thereby force truncation to always occur *before* the undo-boundary, but I'm not 100% certain that is the case.

Additionally, I am concerned that if I set `undo-limit` to *the same value* as `undo-strong-limit`, that the earliest entries in the `buffer-undo-list` will always be truncated before subsequent entries.  If that is the case, then this *may* be a bad thing ....

One drastic solution would be to modify `truncate_undo_list` to look for a `symbol` in the list and preserve it; however, that only benefits me if I run a custom version of Emacs.  I'm working on developing a fork of `undo-tree.el`, and I'd like a solution that other people can use with the stock version of Emacs.

[*CAVEAT*:  It is my assumption that the `buffer-undo-tree` that existed prior to garbage collection truncation as discussed above will still be usable after truncation occurs.  I hope this is the case, but if that is a wrong assumption on my part, then please let me know.  In my mind, I'm thinking of a major reorganization of the buffer where text is deleted and new text is inserted.]

bug#27214: truncate_undo_list in undo.c: exclusions, warnings, documentation.

[Keith David Bershatsky]

Here is an example of how I am modifying `undo.c` for my own usage, which is specifically tailored to the undo-tree.el library and also the fork that I am working on:


In the definition for `syms_of_undo`, add the following:

  DEFSYM (Qundo_tree_canary, "undo-tree-canary");


And, modify `truncate_undo_list` as follows -- the modified section is labeled with an "undo-tree" notation:

void
truncate_undo_list (struct buffer *b)
{
  Lisp_Object list;
  Lisp_Object prev, next, last_boundary;
  EMACS_INT size_so_far = 0;

  /* Make sure that calling undo-outer-limit-function
     won't cause another GC.  */
  ptrdiff_t count = inhibit_garbage_collection ();

  /* Make the buffer current to get its local values of variables such
     as undo_limit.  Also so that Vundo_outer_limit_function can
     tell which buffer to operate on.  */
  record_unwind_current_buffer ();
  set_buffer_internal (b);

  list = BVAR (b, undo_list);

  prev = Qnil;
  next = list;
  last_boundary = Qnil;

  /* If the first element is an undo boundary, skip past it.  */
  if (CONSP (next) && NILP (XCAR (next)))
    {
      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* Always preserve at least the most recent undo record
     unless it is really horribly big.

     Skip, skip, skip the undo, skip, skip, skip the undo,
     Skip, skip, skip the undo, skip to the undo bound'ry.  */

  while (CONSP (next) && ! NILP (XCAR (next)))
    {
      Lisp_Object elt;
      elt = XCAR (next);

      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);
      if (CONSP (elt))
	{
	  size_so_far += sizeof (struct Lisp_Cons);
	  if (STRINGP (XCAR (elt)))
	    size_so_far += (sizeof (struct Lisp_String) - 1
			    + SCHARS (XCAR (elt)));
	}

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* If by the first boundary we have already passed undo_outer_limit,
     we're heading for memory full, so offer to clear out the list.  */
  if (INTEGERP (Vundo_outer_limit)
      && size_so_far > XINT (Vundo_outer_limit)
      && !NILP (Vundo_outer_limit_function))
    {
      Lisp_Object tem;

      /* Normally the function this calls is undo-outer-limit-truncate.  */
      tem = call1 (Vundo_outer_limit_function, make_number (size_so_far));
      if (! NILP (tem))
	{
	  /* The function is responsible for making
	     any desired changes in buffer-undo-list.  */
	  unbind_to (count, Qnil);
	  return;
	}
    }

  if (CONSP (next))
    last_boundary = prev;

  /* Keep additional undo data, if it fits in the limits.  */
  while (CONSP (next))
    {
      Lisp_Object elt;
      elt = XCAR (next);

      /* When we get to a boundary, decide whether to truncate
	 either before or after it.  The lower threshold, undo_limit,
	 tells us to truncate after it.  If its size pushes past
	 the higher threshold undo_strong_limit, we truncate before it.  */
      if (NILP (elt))
	{
	  if (size_so_far > undo_strong_limit)
	    break;
	  last_boundary = prev;
	  if (size_so_far > undo_limit)
	    break;
	}

      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);
      if (CONSP (elt))
	{
	  size_so_far += sizeof (struct Lisp_Cons);
	  if (STRINGP (XCAR (elt)))
	    size_so_far += (sizeof (struct Lisp_String) - 1
			    + SCHARS (XCAR (elt)));
	}

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* If we scanned the whole list, it is short enough; don't change it.  */
  if (NILP (next))
    ;


/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */
/* undo-tree */

  /* Truncate at the boundary where we decided to truncate.  */
  else if (!NILP (last_boundary))
    {
    if (Fmemq (Qundo_tree_canary, last_boundary))
      {
        AUTO_STRING (my_string, "truncate_undo_list:  %s");
        CALLN (Fmessage, my_string, last_boundary);
      }
      else
        XSETCDR (last_boundary, Qnil);
    }

/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */


  /* There's nothing we decided to keep, so clear it out.  */
  else
    bset_undo_list (b, Qnil);

  unbind_to (count, Qnil);
}

bug#27214: truncate_undo_list in undo.c: exclusions, warnings, documentation.

[Keith David Bershatsky]

I opted to prevent truncate_undo_list from truncating the buffer-undo-list when undo-tree-canary is present, except if the undo-outer-limit is exceeded.  Here is the revision:

/* At garbage collection time, make an undo list shorter at the end,
   returning the truncated list.  How this is done depends on the
   variables undo-limit, undo-strong-limit and undo-outer-limit.
   In some cases this works by calling undo-outer-limit-function.  */

void
truncate_undo_list (struct buffer *b)
{
  Lisp_Object list;
  Lisp_Object prev, next, last_boundary;
  EMACS_INT size_so_far = 0;

  /* Make sure that calling undo-outer-limit-function
     won't cause another GC.  */
  ptrdiff_t count = inhibit_garbage_collection ();

  /* Make the buffer current to get its local values of variables such
     as undo_limit.  Also so that Vundo_outer_limit_function can
     tell which buffer to operate on.  */
  record_unwind_current_buffer ();
  set_buffer_internal (b);

  list = BVAR (b, undo_list);

  prev = Qnil;
  next = list;
  last_boundary = Qnil;

  /* If the first element is an undo boundary, skip past it.  */
  if (CONSP (next) && NILP (XCAR (next)))
    {
      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* Always preserve at least the most recent undo record
     unless it is really horribly big.

     Skip, skip, skip the undo, skip, skip, skip the undo,
     Skip, skip, skip the undo, skip to the undo bound'ry.  */

  while (CONSP (next) && ! NILP (XCAR (next)))
    {
      Lisp_Object elt;
      elt = XCAR (next);

      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);
      if (CONSP (elt))
	{
	  size_so_far += sizeof (struct Lisp_Cons);
	  if (STRINGP (XCAR (elt)))
	    size_so_far += (sizeof (struct Lisp_String) - 1
			    + SCHARS (XCAR (elt)));
	}

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* If by the first boundary we have already passed undo_outer_limit,
     we're heading for memory full, so offer to clear out the list.  */
  if (INTEGERP (Vundo_outer_limit)
      && size_so_far > XINT (Vundo_outer_limit)
      && !NILP (Vundo_outer_limit_function))
    {
      Lisp_Object tem;

      /* Normally the function this calls is undo-outer-limit-truncate.  */
      tem = call1 (Vundo_outer_limit_function, make_number (size_so_far));
      if (! NILP (tem))
	{
	  /* The function is responsible for making
	     any desired changes in buffer-undo-list.  */
	  unbind_to (count, Qnil);
	  return;
	}
    }


/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */
/* undo-tree */

  if (CONSP (list)
      && ! NILP (Fmemq (Qundo_tree_canary, list)))
    {
      unbind_to (count, Qnil);
      return;
    }

/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */


  if (CONSP (next))
    last_boundary = prev;

  /* Keep additional undo data, if it fits in the limits.  */
  while (CONSP (next))
    {
      Lisp_Object elt;
      elt = XCAR (next);

      /* When we get to a boundary, decide whether to truncate
	 either before or after it.  The lower threshold, undo_limit,
	 tells us to truncate after it.  If its size pushes past
	 the higher threshold undo_strong_limit, we truncate before it.  */
      if (NILP (elt))
	{
	  if (size_so_far > undo_strong_limit)
	    break;
	  last_boundary = prev;
	  if (size_so_far > undo_limit)
	    break;
	}

      /* Add in the space occupied by this element and its chain link.  */
      size_so_far += sizeof (struct Lisp_Cons);
      if (CONSP (elt))
	{
	  size_so_far += sizeof (struct Lisp_Cons);
	  if (STRINGP (XCAR (elt)))
	    size_so_far += (sizeof (struct Lisp_String) - 1
			    + SCHARS (XCAR (elt)));
	}

      /* Advance to next element.  */
      prev = next;
      next = XCDR (next);
    }

  /* If we scanned the whole list, it is short enough; don't change it.  */
  if (NILP (next))
    ;
  /* Truncate at the boundary where we decided to truncate.  */
  else if (!NILP (last_boundary))
    XSETCDR (last_boundary, Qnil);
  /* There's nothing we decided to keep, so clear it out.  */
  else
    bset_undo_list (b, Qnil);

  unbind_to (count, Qnil);
}

\f
void
syms_of_undo (void)
{


/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */
/* undo-tree */

  DEFSYM (Qundo_tree_canary, "undo-tree-canary");

/* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; */


* * *