bug#13271: primitive-undo in Lisp

[Aaron S. Hawley]

At Stefan's request, I'm submitting a patch to convert
`primitive-undo' from C to Lisp.  I had originally submitted a version
of this code to gnu-emacs-sources.

http://lists.gnu.org/archive/html/gnu-emacs-sources/2012-11/msg00026.html

This function is the engine behind the `undo' command in Emacs -- C-/,
C-x u and so on.  I've purposely cargo-culted the original C version,
including carrying over the comments and the parts that I believe are
vestigial.  I've been using and maintaining this code since 2010 and
haven't had any issues.

In the while-loop over buffer-undo-list, Stefan suggested adding a new
error condition for unrecognized entries.  I've added such an error.
Using this code daily I have not reached the error condition.  Only
with the unit tests that purposely fubar the contents of
buffer-undo-list is the error reached.

This patch is against trunk.  I did not compile and test the C
changes.  And I've only tested the it in a pretest release for 24.2,
not what is in trunk.  I'm confident it should work given there are no
differences in undo.c.  To make up for these sins, I'm submitting unit
tests.

I wrote 6 tests that cover most of the execution paths and behavior.
These tests call `primitive-undo' 27 times.  I've benchmarked the Lisp
and C versions using benchmark.el end `elp-instrument-function' by
running the tests 100 times.  The elapsed time of these tests on my
computer for both versions of `primitive-undo' is approximately 300
seconds.

(benchmark 100 '(let ((undo-test5-error nil)) (undo-test-all)))
=> Elapsed time: 305.218000s (104.841000s in 14804 GCs)
(benchmark 100 '(undo-test-all)) ;; Lisp `primitive-undo'
=> Elapsed time: 295.974000s (104.582000s in 14704 GCs)

Out of those 3 minutes, less than 4 seconds is attributable to
`primitive-undo'.  They average 1/700th (0.0014) of a second per call
of `primitive-undo' for both versions.

Function Name        Call Count  Elapsed Time  Average Time
=============        ==========  ============  ============
primitive-undo C     2600        3.4889999999  0.0013419230
primitive-undo Lisp  2700        3.6869999999  0.0013655555

I've added these results to the unit tests source file for posterity.
aaron

-- 
In general, we reserve the right to have a poor
memory--the computer, however, is supposed to
remember!  Poor computer.  -- Guy Lewis Steele Jr.

primundo.diff
Description: Binary data