* bug#16411: undo-only bugs @ 2014-01-10 22:33 Barry OReilly 2014-01-10 23:54 ` Stefan Monnier ` (5 more replies) 0 siblings, 6 replies; 27+ messages in thread From: Barry OReilly @ 2014-01-10 22:33 UTC (permalink / raw To: 16411 [-- Attachment #1: Type: text/plain, Size: 3936 bytes --] Looking over the code for the undo system, I found two bugs and constructed recipes to demonstrate. For these, each "insert" should be exactly one change group or the recipes may not work. I use Evil so it's easy to arrange for that. Recipe 1: • Insert "aaa" • Insert "bbb" • Undo • Insert "ccc" • Insert "ddd" • Undo • Undo-only with prefix arg 2 • Expected: none of the above insertions are in the buffer • Actual: buffer has aaa and bbb insertions Reason is that undo-only skips "redo records" prior to calling undo-more through recursive lookup in undo-equiv-table. However, it doesn't reference undo-equiv-table again as it iterates prefix-arg times, so it may undo redo records after the first correct undo. In this case, it redoes bbb. I think the solution entails moving this sort of thing into a loop in undo-more: (when (and (consp equiv) undo-no-redo) ;; The equiv entry might point to another redo record if we have done ;; undo-redo-undo-redo-... so skip to the very last equiv. (while (let ((next (gethash equiv undo-equiv-table))) (if next (setq equiv next)))) (setq pending-undo-list equiv)) Recipe 2: • Insert "aaa" • Insert "bbb" • Mark region around "aaa" but not "bbb" • Undo (in region) • Mark region around "bbb" and where "aaa" used to be • Undo-only • Expected: none of the above insertions are in the buffer • Actual: buffer has aaa and bbb insertions The code appears to simply punt on undo-only in region and behaves like ordinary undo. Thus it undoes the redo record to bring back bbb. One idea I have to solve bug 2 is to extend undo-equiv-table or create another redo-record-table weak hash table with the same key type as the undo-equiv-table: a "redo record" as a cons of buffer-undo-list. The value would have prefix-arg number of "undone records" which that redo record undid. When undo-only in region using the redo-record-table the algorithm would go roughly like: While pending-undo-list non nil: Pop undo-i from pending-undo-list: If undo-i is a redo record (exists in the table): Remove undo-i's undone records from pending-undo-list (or otherwise arrange to skip it) Else: Undo undo-i If "undo undo-i" was done prefix-arg times: Break (finished) Reached end of undo history As a non rigorous example, if there is an undo A of an undo B of an edit C in the region: • When undo-i is A, B is removed from consideration • With B gone, undo-i never becomes B, so C remains in pending-undo-list. A and B effectively cancelled each other out • C is correctly picked for the undo-only The reason undo-equiv-table is insufficient is because its value is the change group *after* the undone record. That change group may have been filtered out of pending-undo-list. OTOH, replacing existing usage of undo-equiv-table with the proposed redo-record-table is straight forward: go one change group forward to get the same value as the undo-equiv-table. Thus undo-equiv-table could be phased out in favor of using the redo-record-table. Another issue is that for both recipes, Emacs echos "Undo!". For bug 2, it does not match what Emacs actually did. For bug 1, it is partly incorrect because Emacs did an undo and a redo. Perhaps when (< 1 prefix-arg), the echo message should convey more. Possible messages might be "Undo, redo!" and "Redo, undo, undo! No further undo information" The reason I'm looking at this code at all is that I am investigating Stefan's guidance [1] about better integrating undo-tree with the builtin undo system. I think redo-record-table may help to this end, but I'll elaborate on that at later time. No later than the time I would submit a patch for bug 2, if welcome. [1] http://lists.gnu.org/archive/html/gnu-emacs-sources/2009-11/msg00010.html [-- Attachment #2: Type: text/html, Size: 4501 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly @ 2014-01-10 23:54 ` Stefan Monnier 2014-01-11 3:48 ` Barry OReilly 2014-02-14 22:29 ` Barry OReilly ` (4 subsequent siblings) 5 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-01-10 23:54 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > I think the solution entails moving this sort of thing into a loop in > undo-more: > (when (and (consp equiv) undo-no-redo) > ;; The equiv entry might point to another redo record if we have done > ;; undo-redo-undo-redo-... so skip to the very last equiv. > (while (let ((next (gethash equiv undo-equiv-table))) > (if next (setq equiv next)))) > (setq pending-undo-list equiv)) Indeed. Or, equivalently, changing `undo' so it only calls undo-more with argument 1 (and use the above while loop between each call to undo-more). > Recipe 2: > • Insert "aaa" > • Insert "bbb" > • Mark region around "aaa" but not "bbb" > • Undo (in region) > • Mark region around "bbb" and where "aaa" used to be > • Undo-only > • Expected: none of the above insertions are in the buffer > • Actual: buffer has aaa and bbb insertions > The code appears to simply punt on undo-only in region and behaves > like ordinary undo. Thus it undoes the redo record to bring back bbb. undo-in-region does not implement undo-only, indeed. I think the way to implement undo-only is to change undo-make-selective-list so it also skips redo entries (depending on undo-no-redo, obviously) using the above while loop. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 23:54 ` Stefan Monnier @ 2014-01-11 3:48 ` Barry OReilly 2014-01-11 4:29 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-01-11 3:48 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 782 bytes --] > undo-in-region does not implement undo-only, indeed. I think the way > to implement undo-only is to change undo-make-selective-list so it > also skips redo entries (depending on undo-no-redo, obviously) using > the above while loop. I don't see how that's a correct solution in the face of arbitrary regional undos and prefix args. Would you have the redo records resulting from regional undos still map to t in the undo-equiv-table? How does your solution account for redo records that undid several because of prefix-arg? undo-equiv-table only maps to the change group after the last undone record without information about the (1- prefix-arg) others. My proposition accounts for these considerations and I think is correct. If not I hope to find out when I start hacking it. [-- Attachment #2: Type: text/html, Size: 876 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-11 3:48 ` Barry OReilly @ 2014-01-11 4:29 ` Stefan Monnier 2014-01-11 5:09 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-01-11 4:29 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 >> undo-in-region does not implement undo-only, indeed. I think the way >> to implement undo-only is to change undo-make-selective-list so it >> also skips redo entries (depending on undo-no-redo, obviously) using >> the above while loop. > I don't see how that's a correct solution in the face of arbitrary > regional undos and prefix args. Would you have the redo records > resulting from regional undos still map to t in the undo-equiv-table? I was talking about simply making undo-in-region properly skip the previous undos (presuming they don't themselves come from an undo-in-region). IIUC, you're talking of skipping (e.g. in a non-region undo) the undos that took place during undo-in-region, right? If so, I don't have an answer for how we could do that, in general. In your pseudo-code: While pending-undo-list non nil: Pop undo-i from pending-undo-list: If undo-i is a redo record (exists in the table): Remove undo-i's undone records from pending-undo-list (or otherwise arrange to skip it) Else: Undo undo-i If "undo undo-i" was done prefix-arg times: Break (finished) Reached end of undo history I have no idea how to implement the part: Remove undo-i's undone records from pending-undo-list (or otherwise arrange to skip it) I guess I do have some idea how to do it, but it looks like a lot of work, since we have to adjust the positions in the rest of pending-undo-list. Other than that I don't understand what your redo-record-table does. AFAICT the test "undo-i is a redo record" can be performed with undo-equiv-table. > How does your solution account for redo records that undid several > because of prefix-arg? As you have discovered the current code does not even try to account for prefix args. > undo-equiv-table only maps to the change group > after the last undone record without information about the (1- > prefix-arg) others. Right: the loop that undoes N steps (either in undo-more or in undo if we change undo to only call undo-more with a 1) needs not only to use undo-equiv-table at each iteration to skip redo entries, but it also needs to add an entry in undo-equiv-table at each iteration. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-11 4:29 ` Stefan Monnier @ 2014-01-11 5:09 ` Barry OReilly 2014-01-14 0:49 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-01-11 5:09 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 1127 bytes --] > I guess I do have some idea how to do it, but it looks like a lot of > work, since we have to adjust the positions in the rest of > pending-undo-list. Are you saying the buffer positions in the undo data become invalidated? That could indeed be a detail I missed. Let me take a closer look. > Right: the loop that undoes N steps (either in undo-more or in undo > if we change undo to only call undo-more with a 1) needs not only to > use undo-equiv-table at each iteration to skip redo entries, but it > also needs to add an entry in undo-equiv-table at each iteration. And recall that these N are rolled into one redo record. So a redo record needs to reference N records it undid. That means undo-equiv-table's value type has a new format that could conceivably break user code, so let's name it something different: redo-record-table. Now the only difference with redo-record-table as I described it earlier is the off-by-one-change-group difference. Actually, this makes me realize the solution to bug 1 is inadequate. Calling (undo-primitive 1) N times creates N redo records whereas (undo-primitive N) creates one. [-- Attachment #2: Type: text/html, Size: 1262 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-11 5:09 ` Barry OReilly @ 2014-01-14 0:49 ` Stefan Monnier 2014-01-14 1:52 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-01-14 0:49 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 >> I guess I do have some idea how to do it, but it looks like a lot of >> work, since we have to adjust the positions in the rest of >> pending-undo-list. > Are you saying the buffer positions in the undo data become > invalidated? That could indeed be a detail I missed. Let me take a > closer look. Not exactly invalidated, but we can't just skip an undo-record without adjusting the subsequent records. We can skip a bunch of undo-record specified via undo-equiv-table because that table stores pairs of undo states that correspond to the exact same buffer, so the "adjustment" is a no-op. >> Right: the loop that undoes N steps (either in undo-more or in undo >> if we change undo to only call undo-more with a 1) needs not only to >> use undo-equiv-table at each iteration to skip redo entries, but it >> also needs to add an entry in undo-equiv-table at each iteration. > And recall that these N are rolled into one redo record. Not sure what you mean here. > So a redo record needs to reference N records it undid. I'm even more confused. > Actually, this makes me realize the solution to bug 1 is inadequate. > Calling (undo-primitive 1) N times creates N redo records whereas > (undo-primitive N) creates one. No, primitive-undo does not add any undo boundary. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-14 0:49 ` Stefan Monnier @ 2014-01-14 1:52 ` Stefan Monnier 2014-01-14 14:00 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-01-14 1:52 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 >> Actually, this makes me realize the solution to bug 1 is inadequate. >> Calling (undo-primitive 1) N times creates N redo records whereas >> (undo-primitive N) creates one. > No, primitive-undo does not add any undo boundary. Actually, now I'm not sure what you meant by "redo records". (primitive-undo N) will undo all the M "records" that appear before the next Nth undo boundary, and will correspondingly add M redo "records", but no boundary. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-14 1:52 ` Stefan Monnier @ 2014-01-14 14:00 ` Barry OReilly 2014-01-19 0:58 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-01-14 14:00 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 560 bytes --] > >> Actually, this makes me realize the solution to bug 1 is > >> inadequate. Calling (undo-primitive 1) N times creates N redo > >> records whereas (undo-primitive N) creates one. > > No, primitive-undo does not add any undo boundary. > Actually, now I'm not sure what you meant by "redo records". > (primitive-undo N) will undo all the M "records" that appear before > the next Nth undo boundary, and will correspondingly add M redo > "records", but no boundary. I took another look at the code and see I was mistaken on this point. I'll work on a patch. [-- Attachment #2: Type: text/html, Size: 708 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-14 14:00 ` Barry OReilly @ 2014-01-19 0:58 ` Barry OReilly 2014-01-19 3:18 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-01-19 0:58 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 3493 bytes --] After looking at and considering more of the undo code, here's my current thinking about how to solve bug 2. The Elisp manual states that undo elements of buffer-undo-list can be of the form: (apply delta beg end funname . args) Define a "redo element" as an element of buffer-undo-list created because of an undo command. Suppose we change the way redo elements are represented to: (apply delta beg end 'undo-redo . (undone-element undo-delta)) Where: • delta, beg, end are as documented. • undo-redo is a new function that copies undone-element, applies undo-delta, then calls primitive-undo on it. • undone-element is the undone element of buffer-undo-list. • undo-delta is (position . offset) indicating how undo-redo should modify a copy of undone-element in order to carry out the redo. When executing undo-only: • Assume pending-undo-list can be lazily computed • Let undo-skip-set be an empty set of undo elements to skip • Iterate over pending-undo-list until prefix-arg undos complete: • If the element is in undo-skip-set: • Remove it from undo-skip-set • Continue loop • If the element is of the form for a redo element: • Insert its undone-element in the undo-skip-set • Else undo the element Using a BST for the undo-skip-set would be appropriate, but I don't see that one is available to core Elisp code. A skip list data structure would be a simple option with similar performance characteristics. Note: this is a different kind of "skip", you can duckduckgo "skip lists". In your earlier reply, you hinted that switching undo-only from using the undo-equiv-table to calling undo-make-selective-list might create a noticable performance regression. The latter is O(N*N) for N sized undo history! I would expect undo-only will generally have an element to find, in which case, being able to compute next elements of pending-undo-list as needed instead of in full upfront may be a sufficient solution. If it isn't sufficient, I can also make the algorithm O(N*log(N)). One way to do this is using another skip list to store the undo-deltas: sort by position, and at each node store the sum of the offsets over the skip interval following that node. The analogous thing can be done with a BST: put the sum of a subtree's offsets at each node. This is more complex in part because the sums need to be updated during tree rotations. There's another benefit to my proposed representation for redo elements. Consider the use case: • Delete text X bytes large • Do Y cycles of undo and redo As I understand the current code, the size of undo history grows by approximately X*Y. With this new way to represent redo elements, undo history grows approximately Y instead. This proposal implies recursive calls to primitive-undo. The size of the Lisp call stack would be a function of how deep redo records refer to undone redo records. Maybe there are reasonable ways to deal with that or maybe it's a non issue. Are there examples of existing code putting (apply delta beg end funname . args) into the buffer-undo-list? I want to see what the options might be for pushing redo elements in that format. The best I can think of right now is a dynamically bound variable set only during an undo and examined in record functions in undo.c. There's more I could say about other details, but I'll stop now to get feedback on the overall idea. [-- Attachment #2: Type: text/html, Size: 3770 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-19 0:58 ` Barry OReilly @ 2014-01-19 3:18 ` Stefan Monnier 2014-01-19 16:57 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-01-19 3:18 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > Where: > • delta, beg, end are as documented. > • undo-redo is a new function that copies undone-element, applies > undo-delta, then calls primitive-undo on it. > • undone-element is the undone element of buffer-undo-list. > • undo-delta is (position . offset) indicating how undo-redo should > modify a copy of undone-element in order to carry out the redo. > When executing undo-only: > • Assume pending-undo-list can be lazily computed > • Let undo-skip-set be an empty set of undo elements to skip > • Iterate over pending-undo-list until prefix-arg undos complete: > • If the element is in undo-skip-set: > • Remove it from undo-skip-set > • Continue loop > • If the element is of the form for a redo element: > • Insert its undone-element in the undo-skip-set > • Else undo the element In which way would this help fixing bug 2 (I thought we had already understood how to fix bug 2, BTW)? More problematic: the step "Insert its undone-element in the undo-skip-set" means that we skip this "redo" element, which means that all the subsequent elements (until the matching undone-element) may have incorrect buffer positions. Luckily, you probably won't bump into any problem because all these intermediate elements will themselves be redo elements or be in undo-skip-set. But it's still dangerous and wasteful (why not skip all these elements in one swoop as we currently do with undo-equiv-table). Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-19 3:18 ` Stefan Monnier @ 2014-01-19 16:57 ` Barry OReilly 2014-02-14 18:51 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-01-19 16:57 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 3175 bytes --] > (I thought we had already understood how to fix bug 2, BTW) No, we both agreed about how to fix bug 1, which isn't too hard or intrusive. I'm talking about bug 2 now. I appreciate you taking the time to discuss it with me. You said about it: > IIUC, you're talking of skipping (e.g. in a non-region undo) the > undos that took place during undo-in-region, right? If so, I don't > have an answer for how we could do that, in general. If you require the solution use undo-equiv-table, then I would have to also admit to not having an answer. > why not skip all these elements in one swoop as we currently do with > undo-equiv-table Because it would not be correct. I constructed recipe 2 in order to demonstrate the incorrectness. > In which way would this help fixing bug 2 Recipe 2 used an undo-in-region to trick the current undo-only behavior into finding the wrong element to undo. Under my proposed solution, undo-in-region creates a change group of redo elements, each with a reference to its undone-element. This allows undo-only to find the correct element to undo per the algorithm I described. Why is it correct? undo-only wishes to find the most recent non redo element A which is currently in the buffer (ie the net effect is it's not undone). If A is reachable through an odd number of hops across undo-element references, then it is undone, if even it is not undone. If there exist paths to A both even and odd in length, then something strange has happened to the undo history. The effect of skipping undo elements as I described it is to exclude the ones with odd length paths. For example, consider: A1 undoes A2 undoes A3 undoes A4 undoes A5 A2 and A4 will find themselves in the undo-skip-set, the others won't. undo-only correctly finds A5 as the element to undo. B1 undoes B2 undoes B3 undoes B4 undoes B5 undoes B6 B2, B4, B6 will be skipped, so undo-only will have to find some other non B element to undo, as it should in this case. > the step "Insert its undone-element in the undo-skip-set" means that > we skip this "redo" element, which means that all the subsequent > elements (until the matching undone-element) may have incorrect > buffer positions. I explained this: I would rework the pending-undo-list computation to be lazier, perhaps creating a get-next-pending-undo function instead of computing the entire pending-undo-list upfront. undo-only would use this function to get the next copy of an element of buffer-undo-list, with positions adjusted using an index of undo-delta sums. get-next-pending-undo would be part of "Iterate over pending-undo-list", which means we are adjusting positions whether the element will be skipped or not. This rework to use a new get-next-pending-undo can be a self contained patch which would benefit undo in region's performance right away, even if undo-only doesn't use it after just the first patch. > But it's still dangerous and wasteful By dangerous do you mean incorrect? By wasteful do you mean non performant? Maybe the discussion will be less confusing if we focus on correctness first, then move to performance? Could you describe what part of my proposal is incorrect? [-- Attachment #2: Type: text/html, Size: 3540 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-19 16:57 ` Barry OReilly @ 2014-02-14 18:51 ` Barry OReilly 0 siblings, 0 replies; 27+ messages in thread From: Barry OReilly @ 2014-02-14 18:51 UTC (permalink / raw Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 1190 bytes --] Here's another bug with recipe. Again, each "insert" should be a change group. * ./src/emacs -Q * In *scratch* at least twice: * Insert "aaa" * Undo * Select the entire buffer * Undo in region with prefix-arg 4 * Observe the wrongful deletion of the string: "fer." in the Lisp comment. undo-elt-in-region has a discrepency between whether (TEXT . POSITION) and (BEGIN . END) are in the region: ;; (BEGIN . END) (and (>= (car undo-elt) start) (<= (cdr undo-elt) end)) ^^ ;; (TEXT . POSITION) (and (>= (abs (cdr undo-elt)) start) (< (abs (cdr undo-elt)) end)) ^ One is compared to the end by <= and the other by <. Consequently, (192 . 195) is deemed in the region, (aaa . 192) outside the region. With (aaa . 192) outside the region, all subsequent positions of undo-list-copy are decremented by three, including the next (192 . 195) which becomes (189 . 192). (189 . 192) is deemed in the region, but that's not valid given the restoration of "aaa" was just excluded. It's now pear shaped. I'm collecting these bugs related to the undo system in one bug report because that is the most organized way for me to address them. [-- Attachment #2: Type: text/html, Size: 1661 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly 2014-01-10 23:54 ` Stefan Monnier @ 2014-02-14 22:29 ` Barry OReilly 2014-02-18 17:40 ` Barry OReilly ` (3 subsequent siblings) 5 siblings, 0 replies; 27+ messages in thread From: Barry OReilly @ 2014-02-14 22:29 UTC (permalink / raw To: 16411 [-- Attachment #1: Type: text/plain, Size: 429 bytes --] > * ./src/emacs -Q > * In *scratch* at least twice: > * Insert "aaa" > * Undo > * Select the entire buffer > * Undo in region with prefix-arg 4 > * Observe the wrongful deletion of the string: "fer." in the Lisp > comment. A more concise recipe: * ./src/emacs -Q * In *scratch* insert "aaa" * Undo * Select the entire buffer * Undo in region * Observe the wrongful deletion of the period in the Lisp comment. [-- Attachment #2: Type: text/html, Size: 690 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly 2014-01-10 23:54 ` Stefan Monnier 2014-02-14 22:29 ` Barry OReilly @ 2014-02-18 17:40 ` Barry OReilly 2014-02-26 15:20 ` bug#16411: undo in region corrupts existing text Barry OReilly ` (2 subsequent siblings) 5 siblings, 0 replies; 27+ messages in thread From: Barry OReilly @ 2014-02-18 17:40 UTC (permalink / raw To: 16411 [-- Attachment #1: Type: text/plain, Size: 2943 bytes --] > ;; (BEGIN . END) > (and (>= (car undo-elt) start) > (<= (cdr undo-elt) end)) > ^^ > > ;; (TEXT . POSITION) > (and (>= (abs (cdr undo-elt)) start) > (< (abs (cdr undo-elt)) end)) > ^ Using 'git log -L' on these two code fragments, I found the (BEGIN . END) case changed in this commit to "Fix one-off error at END". commit 9debee7a5e6ebc0c32141619248e7390f1476946 Author: Richard M. Stallman <rms@gnu.org> Date: Mon Sep 9 00:27:30 2002 +0000 (undo-elt-in-region): Fix one-off error at END. (forward-visible-line): Handle invisibility by ignoring invisible newlines. Also include entire invisible lines beyond the stopping point. diff --git a/lisp/simple.el b/lisp/simple.el index bfef653..d9ae114 100644 --- a/lisp/simple.el +++ b/lisp/simple.el @@ -1089,7 +1089,7 @@ we stop and ignore all further elements." If it crosses the edge, we return nil." (cond ((integerp undo-elt) (and (>= undo-elt start) - (< undo-elt end))) + (<= undo-elt end))) ((eq undo-elt nil) t) ((atom undo-elt) @@ -1109,16 +1109,16 @@ If it crosses the edge, we return nil." (cons alist-elt undo-adjusted-markers))) (and (cdr alist-elt) (>= (cdr alist-elt) start) - (< (cdr alist-elt) end)))) + (<= (cdr alist-elt) end)))) ((null (car undo-elt)) ;; (nil PROPERTY VALUE BEG . END) (let ((tail (nthcdr 3 undo-elt))) (and (>= (car tail) start) - (< (cdr tail) end)))) + (<= (cdr tail) end)))) ((integerp (car undo-elt)) ;; (BEGIN . END) (and (>= (car undo-elt) start) - (< (cdr undo-elt) end))))) + (<= (cdr undo-elt) end))))) (defun undo-elt-crosses-region (undo-elt start end) "Test whether UNDO-ELT crosses one edge of that region START ... END. This didn't change the (TEXT . POSITION) case, which hasn't changed since 1998 when it was first introduced. Maybe it was forgotten in the above 2002 change? Anyway, I made this change locally: diff --git a/lisp/simple.el b/lisp/simple.el index b90382d..01d4f19 100644 --- a/lisp/simple.el +++ b/lisp/simple.el @@ -2434,7 +2434,7 @@ If it crosses the edge, we return nil." ((stringp (car undo-elt)) ;; (TEXT . POSITION) (and (>= (abs (cdr undo-elt)) start) - (< (abs (cdr undo-elt)) end))) + (<= (abs (cdr undo-elt)) end))) ((and (consp undo-elt) (markerp (car undo-elt))) ;; This is a marker-adjustment element (MARKER . ADJUSTMENT). ;; See if MARKER is inside the region. and I didn't witness the incorrect behavior from undo in region. Another justification for this change, in addition to fixing the buffer corruption my recipe demonstrates, is that without it, a deletion at the EOB is inaccessible via undo in region. [-- Attachment #2: Type: text/html, Size: 3419 bytes --] ^ permalink raw reply related [flat|nested] 27+ messages in thread
* bug#16411: undo in region corrupts existing text 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly ` (2 preceding siblings ...) 2014-02-18 17:40 ` Barry OReilly @ 2014-02-26 15:20 ` Barry OReilly 2014-02-27 5:02 ` Stefan Monnier 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly 2014-05-14 13:32 ` Barry OReilly 5 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-02-26 15:20 UTC (permalink / raw To: 16411 [-- Attachment #1: Type: text/plain, Size: 699 bytes --] Ping. Is my fix to the bug described at http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#38 acceptable to install? Here is the patch again: diff --git a/lisp/simple.el b/lisp/simple.el index b90382d..01d4f19 100644 --- a/lisp/simple.el +++ b/lisp/simple.el @@ -2434,7 +2434,7 @@ If it crosses the edge, we return nil." ((stringp (car undo-elt)) ;; (TEXT . POSITION) (and (>= (abs (cdr undo-elt)) start) - (< (abs (cdr undo-elt)) end))) + (<= (abs (cdr undo-elt)) end))) ((and (consp undo-elt) (markerp (car undo-elt))) ;; This is a marker-adjustment element (MARKER . ADJUSTMENT). ;; See if MARKER is inside the region. [-- Attachment #2: Type: text/html, Size: 865 bytes --] ^ permalink raw reply related [flat|nested] 27+ messages in thread
* bug#16411: undo in region corrupts existing text 2014-02-26 15:20 ` bug#16411: undo in region corrupts existing text Barry OReilly @ 2014-02-27 5:02 ` Stefan Monnier 0 siblings, 0 replies; 27+ messages in thread From: Stefan Monnier @ 2014-02-27 5:02 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > Ping. Is my fix to the bug described at > http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#38 acceptable to > install? Here is the patch again: I think so, yes, but please add a corresponding ERT test case. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly ` (3 preceding siblings ...) 2014-02-26 15:20 ` bug#16411: undo in region corrupts existing text Barry OReilly @ 2014-05-13 15:01 ` Barry OReilly 2014-05-14 18:06 ` Stefan Monnier ` (2 more replies) 2014-05-14 13:32 ` Barry OReilly 5 siblings, 3 replies; 27+ messages in thread From: Barry OReilly @ 2014-05-13 15:01 UTC (permalink / raw To: 16411, Stefan Monnier I am pursuing a solution more like the first one I suggested in bug 16411 and have a preliminary patch I would like to get some feedback on. undo-tests pass but the patch does not fix the bug yet. The patch does two major things: 1: Defines and populates a new undo-redo-table 2: Uses closures to lazily compute pending undo elements Item 1 is the crucial one. The undo-redo-table is somewhat like undo-equiv-table, except that instead of mapping equal buffer states, it maps undo elements to what they undid. This conveys better information. Mapping equal buffer states with undo-equiv-table is not workable, because undos in region generally don't return the user to a buffer state that actually existed before. Consider: insert A, insert B, undo in region of A. The buffer has just B for the first time. Existing use of undo-equiv-table can readily switch to use undo-redo-table, as described in the obsoletion note of the patch. The converse, using undo-equiv-table instead of undo-redo-table, would require traversing backwards in the singly linked list. The reason undo-redo-table maps at the element level, as opposed to the change group level, is because in the case of undo in region with a prefix arg, the newly created change group needs to reference subsets of potentially many prior change groups. Having undo elements reference what they undid would help solve several issues: 1: undo-only in region doesn't work. 2: Normal undo-only after an undo in region doesn't work. I've previously outlined how the solution would use the undo-redo-table. 3: Undo in region has counter intuitive behavior as described in the FIXME of simple.el describing undo in region. 4: Deleting X bytes, then doing Y iterations of undo and redo causes undo history to grow about X*Y. To grow proportional to Y should be achievable: set undo-in-progress to the in progress element, and the C level undo recording to use it and undo-redo-table to find the eq Lisp_String. 5: Undo Tree should more tightly integrate with the builtin undo system. To do so, it needs sufficient information to visualize the buffer-undo-list as a tree. Undo Tree has a means to visualize undo in regions, so undo-equiv-table is inadequate. There are variations on how elements could reference what they undid, but fundamentally I think it is essential. I wish to know how you like the direction the patch is going as I proceed to solve some problems building upon it. The patch ignores whitespace. diff --git a/lisp/simple.el b/lisp/simple.el index 1484339..09b3a5f 100644 --- a/lisp/simple.el +++ b/lisp/simple.el @@ -2054,20 +2054,32 @@ Go to the history element by the absolute history position HIST-POS." ;Put this on C-x u, so we can force that rather than C-_ into startup msg (define-obsolete-function-alias 'advertised-undo 'undo "23.2") +(defvar undo-redo-table (make-hash-table :test 'eq :weakness t) + "Hash table mapping undo elements created by an undo command to +the undo element they undid. Specifically, the keys and values +are eq to cons of buffer-undo-list. The hash table is weak so as +truncated undo elements can be garbage collected.") (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t) "Table mapping redo records to the corresponding undo one. A redo record for undo-in-region maps to t. A redo record for ordinary undo maps to the following (earlier) undo.") +(make-obsolete-variable + 'undo-equiv-table + "Use undo-redo-table instead. For non regional undos, (gethash +k undo-equiv-table) is the same as taking (gethash k +undo-redo-table) and scanning forward one change group." + "24.5") (defvar undo-in-region nil - "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.") + "Non-nil during an undo in region.") (defvar undo-no-redo nil "If t, `undo' doesn't go through redo entries.") (defvar pending-undo-list nil - "Within a run of consecutive undo commands, list remaining to be undone. -If t, we undid all the way to the end of it.") + "Within a run of consecutive undo commands, is a tail of +buffer-undo-list for remaining undo elements, or a closure to +generate them. If t, there is no more to undo.") (defun undo (&optional arg) "Undo some previous changes. @@ -2115,9 +2127,10 @@ as an argument limits undo to changes within the current region." (undo-more 1)) ;; If we got this far, the next command should be a consecutive undo. (setq this-command 'undo) - ;; Check to see whether we're hitting a redo record, and if - ;; so, ask the user whether she wants to skip the redo/undo pair. - (let ((equiv (gethash pending-undo-list undo-equiv-table))) + ;; Check to see whether we're hitting a redo record + (let ((equiv (if (functionp pending-undo-list) + t + (gethash pending-undo-list undo-equiv-table)))) (or (eq (selected-window) (minibuffer-window)) (setq message (format "%s%s!" (if (or undo-no-redo (not equiv)) @@ -2202,40 +2215,48 @@ Some change-hooks test this variable to do something different.") "Undo back N undo-boundaries beyond what was already undone recently. Call `undo-start' to get ready to undo recent changes, then call `undo-more' one or more times to undo them." - (or (listp pending-undo-list) + (when (eq pending-undo-list t) (user-error (concat "No further undo information" (and undo-in-region " for region")))) (let ((undo-in-progress t)) - ;; Note: The following, while pulling elements off - ;; `pending-undo-list' will call primitive change functions which - ;; will push more elements onto `buffer-undo-list'. - (setq pending-undo-list (primitive-undo n pending-undo-list)) - (if (null pending-undo-list) + ;; Note: The following changes the buffer, and so calls primitive + ;; change functions that push more elements onto + ;; `buffer-undo-list'. + (unless (if (functionp pending-undo-list) + (undo-using-generator pending-undo-list n) + (setq pending-undo-list + (primitive-undo n pending-undo-list))) + ;; Reached the end of undo history (setq pending-undo-list t)))) (defun primitive-undo (n list) - "Undo N records from the front of the list LIST. + "Undo N change groups from the front of the list LIST. Return what remains of the list." + (undo-using-generator + (lambda (&optional option) + (prog1 (cons (car list) list) + (unless (eq option 'peek) (pop list)))) + n) + list) - ;; This is a good feature, but would make undo-start - ;; unable to do what is expected. - ;;(when (null (car (list))) - ;; ;; If the head of the list is a boundary, it is the boundary - ;; ;; preceding this command. Get rid of it and don't count it. - ;; (setq list (cdr list)))) - +(defun undo-using-generator (generator n) + "Undo N change groups using a GENERATOR closure to get +successive undo elements. Return the last association returned +from GENERATOR or nil if the end of undo history was reached." (let ((arg n) ;; In a writable buffer, enable undoing read-only text that is ;; so because of text properties. (inhibit-read-only t) ;; Don't let `intangible' properties interfere with undo. (inhibit-point-motion-hooks t) - ;; We use oldlist only to check for EQ. ++kfs - (oldlist buffer-undo-list) - (did-apply nil) - (next nil)) + next-assoc) (while (> arg 0) - (while (setq next (pop list)) ;Exit inner loop at undo boundary. + ;; Exit this inner loop at an undo boundary, which would be + ;; next-assoc of (nil . nil). + (while (car (setq next-assoc (funcall generator))) + (let ((next (car next-assoc)) + (orig-tail (cdr next-assoc)) + (prior-undo-list buffer-undo-list)) ;; Handle an integer by setting point to that value. (pcase next ((pred integerp) (goto-char next)) @@ -2289,21 +2310,27 @@ Return what remains of the list." (apply fun-args)) (unless (eq currbuff (current-buffer)) (error "Undo function switched buffer")) - (setq did-apply t))) + ;; Make sure an apply entry produces at least one undo entry, + ;; so the test in `undo' for continuing an undo series + ;; will work right. + (when (eq prior-undo-list buffer-undo-list) + (push (list 'apply 'cdr nil) buffer-undo-list)))) ;; Element (STRING . POS) means STRING was deleted. (`(,(and string (pred stringp)) . ,(and pos (pred integerp))) (when (let ((apos (abs pos))) (or (< apos (point-min)) (> apos (point-max)))) (error "Changes to be undone are outside visible portion of buffer")) - (let (valid-marker-adjustments) + (let (valid-marker-adjustments + ahead) ;; Check that marker adjustments which were recorded ;; with the (STRING . POS) record are still valid, ie ;; the markers haven't moved. We check their validity ;; before reinserting the string so as we don't need to ;; mind marker insertion-type. - (while (and (markerp (car-safe (car list))) - (integerp (cdr-safe (car list)))) - (let* ((marker-adj (pop list)) + (while (and (setq ahead (funcall generator 'peek)) + (markerp (car-safe (car ahead))) + (integerp (cdr-safe (car ahead)))) + (let* ((marker-adj (car (funcall generator))) (m (car marker-adj))) (and (eq (marker-buffer m) (current-buffer)) (= pos m) @@ -2331,16 +2358,13 @@ Return what remains of the list." (set-marker marker (- marker offset) (marker-buffer marker)))) - (_ (error "Unrecognized entry in undo list %S" next)))) + (_ (error "Unrecognized entry in undo list %S" next))) + ;; Map the new undo element to what it undid. Not aware yet + ;; of cases where we want to map all new elements. + (unless (eq prior-undo-list buffer-undo-list) + (puthash buffer-undo-list orig-tail undo-redo-table)))) (setq arg (1- arg))) - ;; Make sure an apply entry produces at least one undo entry, - ;; so the test in `undo' for continuing an undo series - ;; will work right. - (if (and did-apply - (eq oldlist buffer-undo-list)) - (setq buffer-undo-list - (cons (list 'apply 'cdr nil) buffer-undo-list)))) - list) + next-assoc)) ;; Deep copy of a list (defun undo-copy-list (list) @@ -2353,16 +2377,16 @@ Return what remains of the list." elt)) (defun undo-start (&optional beg end) - "Set `pending-undo-list' to the front of the undo list. -The next call to `undo-more' will undo the most recently made change. -If BEG and END are specified, then only undo elements -that apply to text between BEG and END are used; other undo elements -are ignored. If BEG and END are nil, all undo elements are used." + "Set `pending-undo-list' to begin a run of undos. The next +call to `undo-more' will undo the next change group. If BEG and +END are specified, then only undo elements that apply to text +between BEG and END are used; other undo elements are ignored. +If BEG and END are nil, all undo elements are used." (if (eq buffer-undo-list t) (user-error "No undo information in this buffer")) (setq pending-undo-list (if (and beg end (not (= beg end))) - (undo-make-selective-list (min beg end) (max beg end)) + (undo-make-regional-generator (min beg end) (max beg end)) buffer-undo-list))) ;; The positions given in elements of the undo list are the positions @@ -2424,30 +2448,39 @@ are ignored. If BEG and END are nil, all undo elements are used." ;; "ccaabad", as though the first "d" became detached from the ;; original "ddd" insertion. This quirk is a FIXME. -(defun undo-make-selective-list (start end) - "Return a list of undo elements for the region START to END. -The elements come from `buffer-undo-list', but we keep only the -elements inside this region, and discard those outside this -region. The elements' positions are adjusted so as the returned -list can be applied to the current buffer." +(defun undo-make-regional-generator (start end) + "Make a closure that will return the next undo element +association in the region START to END each time it is called, in +the form (ADJUSTED-ELT . ORIG-UNDO-LIST). ADJUSTED-ELT is an +undo element with adjusted positions and ORIG-UNDO-LIST is a cons +of buffer-undo-list whose car is the original unadjusted undo +element. ADJUSTED-ELT may or may not be eq to (car +ORIG-UNDO-LIST). + +The use of a closure allows for lazy adjustment of elements of +the buffer-undo-list as needed for successive undo commands." (let ((ulist buffer-undo-list) - ;; A list of position adjusted undo elements in the region. - (selective-list (list nil)) + ;; (ADJUSTED-ELT . ORIG-UNDO-LIST) associations to be returned + ;; from closure + (selective-list (list (cons nil nil))) + prev-assoc ;; A list of undo-deltas for out of region undo elements. - undo-deltas - undo-elt) - (while ulist - (setq undo-elt (car ulist)) + undo-deltas) + (lambda (&optional option) + ;; Update selective-list with potential returns if necessary + (while (and ulist (not selective-list)) + (let ((undo-elt (car ulist))) (cond ((null undo-elt) - ;; Don't put two nils together in the list - (when (car selective-list) - (push nil selective-list))) + ;; Don't put two undo boundaries, represented as (nil + ;; . nil), together in the list + (unless (equal (cons nil nil) prev-assoc) + (push (cons nil nil) selective-list))) ((and (consp undo-elt) (eq (car undo-elt) t)) ;; This is a "was unmodified" element. Keep it ;; if we have kept everything thus far. (when (not undo-deltas) - (push undo-elt selective-list))) + (push (cons undo-elt ulist) selective-list))) ;; Skip over marker adjustments, instead relying ;; on finding them after (TEXT . POS) elements ((markerp (car-safe undo-elt)) @@ -2458,19 +2491,37 @@ list can be applied to the current buffer." (if (undo-elt-in-region adjusted-undo-elt start end) (progn (setq end (+ end (cdr (undo-delta adjusted-undo-elt)))) - (push adjusted-undo-elt selective-list) + (push (cons adjusted-undo-elt ulist) selective-list) ;; Keep (MARKER . ADJUSTMENT) if their (TEXT . POS) was ;; kept. primitive-undo may discard them later. (when (and (stringp (car-safe adjusted-undo-elt)) (integerp (cdr-safe adjusted-undo-elt))) (let ((list-i (cdr ulist))) (while (markerp (car-safe (car list-i))) - (push (pop list-i) selective-list))))) + (let ((marker-adj (pop list-i))) + (push (cons marker-adj marker-adj) + selective-list)))) + (setq selective-list (nreverse selective-list)))) (let ((delta (undo-delta undo-elt))) (when (/= 0 (cdr delta)) - (push delta undo-deltas))))))) + (push delta undo-deltas)))))))) (pop ulist)) + (if (eq option 'peek) + (car selective-list) + (setq prev-assoc (pop selective-list)))))) + +(defun undo-make-selective-list (start end) + "Realize a full selective undo list per +undo-make-regional-generator." + (let ((selective-list nil) + (gen (undo-make-regional-generator start end)) + elt) + (while (setq elt (funcall gen)) + (push selective-list (car elt))) (nreverse selective-list))) +(make-obsolete 'undo-make-selective-list + "Use undo-make-regional-generator instead." + "24.5") (defun undo-elt-in-region (undo-elt start end) "Determine whether UNDO-ELT falls inside the region START ... END. ^ permalink raw reply related [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly @ 2014-05-14 18:06 ` Stefan Monnier 2014-05-14 18:45 ` Stefan Monnier 2014-05-14 19:55 ` Stefan Monnier 2 siblings, 0 replies; 27+ messages in thread From: Stefan Monnier @ 2014-05-14 18:06 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > 1: undo-only in region doesn't work. At least this should be working now. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly 2014-05-14 18:06 ` Stefan Monnier @ 2014-05-14 18:45 ` Stefan Monnier 2014-05-14 19:55 ` Stefan Monnier 2 siblings, 0 replies; 27+ messages in thread From: Stefan Monnier @ 2014-05-14 18:45 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > Item 1 is the crucial one. The undo-redo-table is somewhat like > undo-equiv-table, except that instead of mapping equal buffer states, > it maps undo elements to what they undid. I'm having trouble understanding it (I guess it's just that my mind i caught in a rut, after having come up with undo-equiv-table). > +(defvar undo-redo-table (make-hash-table :test 'eq :weakness t) > + "Hash table mapping undo elements created by an undo command to > +the undo element they undid. Specifically, the keys and values > +are eq to cons of buffer-undo-list. The hash table is weak so as > +truncated undo elements can be garbage collected.") [ Nitpick: the first line of the docstring should stand on its own. ] You talk here about "undo element", but AFAICT this actually points to "a list of undo elements" (where the first element of that list is presumably the "undo element" you mean). Please clarify. It's hard for me to really understand how this undo-redo-table would work without seeing it in use. My guess is that the "undo-only" case would skip redo entries in much the same way as undo-in-region skips "out of bounds" entries (i.e. in a fairly expensive way, adjusting all subsequent elements). Combined with the fact that undo-redo-table contains entries for every redo element rather than for every redo group, I'm slightly worried about the resource use, but I guess that since undo-in-region is fast enough, that won't be a problem. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly 2014-05-14 18:06 ` Stefan Monnier 2014-05-14 18:45 ` Stefan Monnier @ 2014-05-14 19:55 ` Stefan Monnier 2014-05-14 21:56 ` Barry OReilly 2 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-05-14 19:55 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > Having undo elements reference what they undid would help solve > several issues: > 1: undo-only in region doesn't work. > 2: Normal undo-only after an undo in region doesn't work. I've > previously outlined how the solution would use the > undo-redo-table. > 3: Undo in region has counter intuitive behavior as described in > the FIXME of simple.el describing undo in region. > 4: Deleting X bytes, then doing Y iterations of undo and redo > causes undo history to grow about X*Y. To grow proportional to Y > should be achievable: set undo-in-progress to the in progress > element, and the C level undo recording to use it and > undo-redo-table to find the eq Lisp_String. > 5: Undo Tree should more tightly integrate with the builtin undo > system. To do so, it needs sufficient information to visualize > the buffer-undo-list as a tree. Undo Tree has a means to > visualize undo in regions, so undo-equiv-table is inadequate. IIUC this undo-redo-table business is only necessary because of undo-in-region. So I think we should strive to minimize the changes to the way undo works in the absence of undo-in-region. I understand that the change can't be all localized in undo-in-region (because of the need to skip "redo-in-region" during normal undo-only, basically), but we still should try to aim in that direction. > There are variations on how elements could reference what they undid, > but fundamentally I think it is essential. I wish to know how you like > the direction the patch is going as I proceed to solve some problems > building upon it. I think we should try to keep the "one entry per undo boundary" rather than go for "one entry per undo element". > The reason undo-redo-table maps at the element level, as opposed to > the change group level, is because in the case of undo in region with > a prefix arg, the newly created change group needs to reference > subsets of potentially many prior change groups. IIUC the crux of the matter is how to record the redo data for an undo-in-region. The way I see it, for such a "redo-in-region" group, we indeed need to remember which elements it undid (and which ones it skipped instead), but we could store that info as a single entry in an undo-redo/equiv-table. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-14 19:55 ` Stefan Monnier @ 2014-05-14 21:56 ` Barry OReilly 2014-05-15 2:23 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-05-14 21:56 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 3596 bytes --] > You talk here about "undo element", but AFAICT this actually points > to "a list of undo elements" (where the first element of that list > is presumably the "undo element" you mean). Please clarify. Yes, that's right. The first element is the "undo element" referred to. The cons is put in the hash table to facilitate recursive lookup. > My guess is that the "undo-only" case would skip redo entries in > much the same way as undo-in-region skips "out of bounds" entries > (i.e. in a fairly expensive way, adjusting all subsequent elements). Sort of, but some of those skipped elements will cancel each other out rather than adjust positions. See http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16411#5 . It's worth noting that undo-only might have to "mop up" a change group partially undone by a prior undo in region, so a non regional undo-only might also reference a partial change group. > Combined with the fact that undo-redo-table contains entries for > every redo element rather than for every redo group, I'm slightly > worried about the resource use I mulled over the same concern. undo-redo-table would probably be larger than undo-equiv-table, though still a constant factor of undo limit, IIUC. Implementing the "Y undo-redos of X" optimization is a mitigating benefit. I considered having the undo elements themselves reference what they undid. Unfortunately, this approach would probably break current undo-tree. Also, the references need to be weak, and I can only think to do that by wrapping them in one element weak hash tables, defeating the point. > [ Nitpick: the first line of the docstring should stand on its own. ] I don't understand, I thought I formatted the docstring like others, and did M-q it. > IIUC this undo-redo-table business is only necessary because of > undo-in-region. So I think we should strive to minimize the changes > to the way undo works in the absence of undo-in-region. I understand > that the change can't be all localized in undo-in-region (because of > the need to skip "redo-in-region" during normal undo-only, > basically), but we still should try to aim in that direction. I think you're saying to not pursue the use of a closure to generate successive undo elements as needed? I'm fine with that, but I did so because: • I'm trying to prevent a performance regression of the undo-only command. Given the performance of undo in region with the default undo limit, maybe that's not a big concern. • I'm concerned that undo-make-selective-list's O(N**2) algorithm is unfriendly to those who want to increase the undo limit. The generator allows for minimal processing of the history as needed. Admittedly, I have not experimented with greater undo limits. • I have to muck with the interfaces regardless -- undo-make-selective-list still needs to deliver both the adjusted element and the orig-tail to the higher undo code. > IIUC the crux of the matter is how to record the redo data for an > undo-in-region. The way I see it, for such a "redo-in-region" group, > we indeed need to remember which elements it undid (and which ones > it skipped instead), but we could store that info as a single entry > in an undo-redo/equiv-table. I originally set out to do this, but making the weak references work seemed overly tricky to me. The value stored in undo-redo-table would need to be non weak with weak references to undo elements. I supposed this would mean many one element weak hash tables. That seems dodgy. [-- Attachment #2: Type: text/html, Size: 4100 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-14 21:56 ` Barry OReilly @ 2014-05-15 2:23 ` Stefan Monnier 2014-05-15 3:51 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-05-15 2:23 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 >> You talk here about "undo element", but AFAICT this actually points >> to "a list of undo elements" (where the first element of that list >> is presumably the "undo element" you mean). Please clarify. > Yes, that's right. The first element is the "undo element" referred > to. The cons is put in the hash table to facilitate recursive lookup. Makes sense, but please change the docstring to make it clear. > Implementing the "Y undo-redos of X" optimization is a > mitigating benefit. I've never heard anyone bump into this "Y undo-redos of X" problem, so I don't think optimizing it is worth the trouble. If anything should be done with it, I think it'd be to *cut* the extra undo/redo pairs. >> [ Nitpick: the first line of the docstring should stand on its own. ] > I don't understand, I thought I formatted the docstring like others, > and did M-q it. "Stands on its own" basically mean "doesn't end in the middle of a sentence". Some commands only display the first line of a docstring. > I think you're saying to not pursue the use of a closure to generate > successive undo elements as needed? Actually, I didn't really mean to say that. I'm not completely convinced that this generator is worthwhile (i.e. my first reaction was to try and see how to get rid of it), but I then decided not to say anything about it yet ;-) > • I'm trying to prevent a performance regression of the undo-only > command. Given the performance of undo in region with the default > undo limit, maybe that's not a big concern. One way to avoid the performance regression is to use undo-equiv-table for normal undo and only use undo-redo-table for undo-in-region (by "use" I mean "add elements to", since both tables need to be looked up when performing either undo). > • I'm concerned that undo-make-selective-list's O(N**2) algorithm is > unfriendly to those who want to increase the undo limit. The > generator allows for minimal processing of the history as needed. > Admittedly, I have not experimented with greater undo limits. The old code was no faster (neither constant-factor-wise nor algorithmically, IIUC), and it hasn't appeared as a problem so far, so maybe it's not worth worrying about it. I agree that doing it lazily sounds attractive, but let's keep it for later. I.e. the first patch should focus on fixing "undo-only of redo-in-region". > • I have to muck with the interfaces regardless -- > undo-make-selective-list still needs to deliver both the adjusted > element and the orig-tail to the higher undo code. Some change will be needed, indeed. Backward compatibility is important, but we should first come up with an "ideal" design, and only then can we try and figure out which parts need to be adjusted to better preserve compatibility. >> IIUC the crux of the matter is how to record the redo data for an >> undo-in-region. The way I see it, for such a "redo-in-region" group, >> we indeed need to remember which elements it undid (and which ones >> it skipped instead), but we could store that info as a single entry >> in an undo-redo/equiv-table. > I originally set out to do this, but making the weak references work > seemed overly tricky to me. The value stored in undo-redo-table would > need to be non weak with weak references to undo elements. I supposed > this would mean many one element weak hash tables. That seems dodgy. Hmm... that's a very good point. Worth mentioning in a comment. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-15 2:23 ` Stefan Monnier @ 2014-05-15 3:51 ` Barry OReilly 2014-05-15 13:00 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-05-15 3:51 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1: Type: text/plain, Size: 1037 bytes --] > I've never heard anyone bump into this "Y undo-redos of X" problem, > so I don't think optimizing it is worth the trouble. Happens to me all the time. > If anything should be done with it, I think it'd be to *cut* the > extra undo/redo pairs. No complaint from me. That would change the behavior of ordinary undo command, which you just said you don't want to change. > I'm not completely convinced that this generator is worthwhile Ok, I'll lose it then. >> I originally set out to do this, but making the weak references >> work seemed overly tricky to me. The value stored in >> undo-redo-table would need to be non weak with weak references to >> undo elements. I supposed this would mean many one element weak >> hash tables. That seems dodgy. > Hmm... that's a very good point. Worth mentioning in a comment. You actually want me to do that? That is: wrap every referenced element in a size 1 weak hash table. Are you sure that gives the memory savings over the element level mapping of the undo-redo-table in the patch? [-- Attachment #2: Type: text/html, Size: 1239 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-15 3:51 ` Barry OReilly @ 2014-05-15 13:00 ` Stefan Monnier 2014-05-28 18:42 ` Barry OReilly 0 siblings, 1 reply; 27+ messages in thread From: Stefan Monnier @ 2014-05-15 13:00 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 >> If anything should be done with it, I think it'd be to *cut* the >> extra undo/redo pairs. > No complaint from me. That would change the behavior of ordinary undo > command, Yes. And I think that's what we want: as a user, having to wade through N repetitions of redo/undo is a pain. Those that suffer often from it probably switched to undo-tree. The idea of cutting the extra undo-redo pairs follows the following principle: an undo-redo pair gives you access to 1 past buffer state, but if the earlier undo elements already made you go through an identical state, then this undo-redo pair is superfluous. I'm sure this can be generalized for undo-in-region (where an undo-redo pair may not bring you exactly to the same state, but still gives you access to a change you've already seen earlier in the undo list), but I'm sure you can define it more easily than I. > which you just said you don't want to change. So far there was no discussion of changing behavior: only fixing bugs and changing implementation. >> I'm not completely convinced that this generator is worthwhile > Ok, I'll lose it then. We may want to (re)introduce it later, tho. >>> I originally set out to do this, but making the weak references >>> work seemed overly tricky to me. The value stored in >>> undo-redo-table would need to be non weak with weak references to >>> undo elements. I supposed this would mean many one element weak >>> hash tables. That seems dodgy. >> Hmm... that's a very good point. Worth mentioning in a comment. > You actually want me to do that? That is: wrap every referenced > element in a size 1 weak hash table. God no! I'm saying that I agree with your justification for the design of undo-redo-table keeping mappings for every undo-element rather than one per undo group; but that you need to put a comment in the code explaining why it's done this way. Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-15 13:00 ` Stefan Monnier @ 2014-05-28 18:42 ` Barry OReilly 2014-06-19 21:35 ` Stefan Monnier 0 siblings, 1 reply; 27+ messages in thread From: Barry OReilly @ 2014-05-28 18:42 UTC (permalink / raw To: Stefan Monnier; +Cc: 16411 [-- Attachment #1.1: Type: text/plain, Size: 601 bytes --] I have attached a patch against trunk which omits the generators, changes the data format of pending-undo-list, and addresses other comments. The undo-tests pass with this patch. As with the last patch, it doesn't solve an actual bug yet, but that is forthcoming. Since undo-tree uses primitive-undo, I think it must remain compatible. To do this and not duplicate code, I split individual element logic out to an undo-primitive-elt function and moved the look ahead at marker adjustments to undo-more. Since the latter is recent functionality, I doubt undo-tree relies on primitive-undo doing that. [-- Attachment #1.2: Type: text/html, Size: 672 bytes --] [-- Attachment #2: undone-undos.diff --] [-- Type: text/plain, Size: 24516 bytes --] diff --git a/lisp/simple.el b/lisp/simple.el index af8e47c..9b47ccb 100644 --- a/lisp/simple.el +++ b/lisp/simple.el @@ -2054,20 +2054,50 @@ Go to the history element by the absolute history position HIST-POS." ;Put this on C-x u, so we can force that rather than C-_ into startup msg (define-obsolete-function-alias 'advertised-undo 'undo "23.2") +;; Note: We considered a design whereby one entry in the +;; undo-redo-table maps a change group to a list of undone elements or +;; groups. This design does not work because the value stored in +;; undo-redo-table would need to be a non weak list with weak +;; references into buffer-undo-list. Currently Elisp only features +;; weak references when they are directly keys or values of a weak +;; hash table, so a list containing weak references is not supported. +(defvar undo-redo-table (make-hash-table :test 'eq :weakness t) + "Hash table mapping undos to what they undid. + +Specifically, the keys and values are eq to a cons of +buffer-undo-list such that the car of the key is an undo element +and the car of the value is the undone element. + +The hash table is weak so as truncated undo elements can be +garbage collected.") (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t) "Table mapping redo records to the corresponding undo one. A redo record for undo-in-region maps to t. A redo record for ordinary undo maps to the following (earlier) undo.") +(make-obsolete-variable + 'undo-equiv-table + "Use undo-redo-table instead. For non regional undos, (gethash +k undo-equiv-table) is the same as taking (gethash k +undo-redo-table) and scanning forward one change group." + "24.5") (defvar undo-in-region nil - "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.") + "Non-nil during an undo in region.") (defvar undo-no-redo nil "If t, `undo' doesn't go through redo entries.") (defvar pending-undo-list nil - "Within a run of consecutive undo commands, list remaining to be undone. -If t, we undid all the way to the end of it.") + "The pending undo elements in a run of consecutive undo commands. + +Specifically, this is a list of assocations of the +form (ADJUSTED-ELT . ORIG-UNDO-LIST). ADJUSTED-ELT is an undo +element with adjusted positions and ORIG-UNDO-LIST is a cons of +buffer-undo-list whose car is the original unadjusted undo +element. ADJUSTED-ELT may or may not be eq to (car +ORIG-UNDO-LIST). + +If t, there is no more to undo.") (defun undo (&optional arg) "Undo some previous changes. @@ -2115,9 +2145,8 @@ as an argument limits undo to changes within the current region." (undo-more 1)) ;; If we got this far, the next command should be a consecutive undo. (setq this-command 'undo) - ;; Check to see whether we're hitting a redo record, and if - ;; so, ask the user whether she wants to skip the redo/undo pair. - (let ((equiv (gethash pending-undo-list undo-equiv-table))) + ;; Check to see whether we're hitting a redo record + (let ((equiv (gethash (cdr-safe pending-undo-list) undo-equiv-table))) (or (eq (selected-window) (minibuffer-window)) (setq message (format "%s%s!" (if (or undo-no-redo (not equiv)) @@ -2128,7 +2157,7 @@ as an argument limits undo to changes within the current region." ;; undo-redo-undo-redo-... so skip to the very last equiv. (while (let ((next (gethash equiv undo-equiv-table))) (if next (setq equiv next)))) - (setq pending-undo-list equiv))) + (setq pending-undo-list (cons (car equiv) equiv)))) (undo-more (if (numberp arg) (prefix-numeric-value arg) @@ -2138,18 +2167,20 @@ as an argument limits undo to changes within the current region." ;; In the ordinary case (not within a region), map the redo ;; record to the following undos. ;; I don't know how to do that in the undo-in-region case. - (let ((list buffer-undo-list)) + (let ((list buffer-undo-list) + (new-equiv (cdr-safe pending-undo-list))) ;; Strip any leading undo boundaries there might be, like we do ;; above when checking. (while (eq (car list) nil) (setq list (cdr list))) - (puthash list - ;; Prevent identity mapping. This can happen if - ;; consecutive nils are erroneously in undo list. - (if (or undo-in-region (eq list pending-undo-list)) - t - pending-undo-list) - undo-equiv-table)) + (when new-equiv + (puthash list + ;; Prevent identity mapping. This can happen if + ;; consecutive nils are erroneously in undo list. + (if (or undo-in-region (eq list new-equiv)) + t + new-equiv) + undo-equiv-table))) ;; Don't specify a position in the undo record for the undo command. ;; Instead, undoing this should move point to where the change is. (let ((tail buffer-undo-list) @@ -2202,145 +2233,152 @@ Some change-hooks test this variable to do something different.") "Undo back N undo-boundaries beyond what was already undone recently. Call `undo-start' to get ready to undo recent changes, then call `undo-more' one or more times to undo them." - (or (listp pending-undo-list) - (user-error (concat "No further undo information" - (and undo-in-region " for region")))) - (let ((undo-in-progress t)) - ;; Note: The following, while pulling elements off - ;; `pending-undo-list' will call primitive change functions which - ;; will push more elements onto `buffer-undo-list'. - (setq pending-undo-list (primitive-undo n pending-undo-list)) - (if (null pending-undo-list) - (setq pending-undo-list t)))) + (when (eq pending-undo-list t) + (user-error (concat "No further undo information" + (and undo-in-region " for region")))) + (let ((undo-in-progress t) + (group n) + assoc) + (while (> group 0) + (while (car (setq assoc (pop pending-undo-list))) + (let ((elt (car assoc)) + (orig-tail (cdr assoc)) + valid-marker-adjustments) + (when (and (stringp (car-safe elt)) + (integerp (cdr-safe elt))) + ;; Check that marker adjustments which were recorded with + ;; the (STRING . POS) record are still valid, ie the + ;; markers haven't moved. We check their validity before + ;; reinserting the string so as we don't need to mind + ;; marker insertion-type. + (while (and (markerp (car-safe (caar pending-undo-list))) + (integerp (cdr-safe (caar pending-undo-list)))) + (let* ((marker-adj (car (pop pending-undo-list))) + (m (car marker-adj))) + (and (eq (marker-buffer m) (current-buffer)) + (= (cdr elt) m) + (push marker-adj valid-marker-adjustments))))) + (when (markerp (car-safe elt)) + ;; Note: even though these elements are not expected in + ;; the undo list, adjust them to be conservative for the + ;; 24.4 release. (Bug#16818) + (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry" + elt)) + ;; Note: The following changes the buffer, and so calls + ;; primitive change functions that push more elements onto + ;; `buffer-undo-list'. + (when (undo-primitive-elt elt) + ;; Map the new undo element to what it undid. Not aware + ;; yet of cases where we want to map all new elements. + (puthash buffer-undo-list orig-tail undo-redo-table)) + ;; Adjust the valid marker adjustments + (dolist (adj valid-marker-adjustments) + (undo-primitive-elt adj)))) + (setq group (1- group))) + ;; Reached the end of undo history + (unless pending-undo-list (setq pending-undo-list t)))) (defun primitive-undo (n list) - "Undo N records from the front of the list LIST. + "Undo N change groups from the front of the list LIST. Return what remains of the list." + (let ((arg n) + (next nil)) + (while (> arg 0) + (while (setq next (pop list)) ;Exit inner loop at undo boundary. + (undo-primitive-elt next)) + (setq arg (1- arg))))) - ;; This is a good feature, but would make undo-start - ;; unable to do what is expected. - ;;(when (null (car (list))) - ;; ;; If the head of the list is a boundary, it is the boundary - ;; ;; preceding this command. Get rid of it and don't count it. - ;; (setq list (cdr list)))) +(defun undo-primitive-elt (next) + "Undo the element NEXT and return non nil if changes were made. - (let ((arg n) - ;; In a writable buffer, enable undoing read-only text that is +NEXT is one of the valid forms documented in the Undo section of +the Elisp manual." + (let (;; In a writable buffer, enable undoing read-only text that is ;; so because of text properties. (inhibit-read-only t) ;; Don't let `intangible' properties interfere with undo. (inhibit-point-motion-hooks t) ;; We use oldlist only to check for EQ. ++kfs - (oldlist buffer-undo-list) - (did-apply nil) - (next nil)) - (while (> arg 0) - (while (setq next (pop list)) ;Exit inner loop at undo boundary. - ;; Handle an integer by setting point to that value. - (pcase next - ((pred integerp) (goto-char next)) - ;; Element (t . TIME) records previous modtime. - ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or - ;; UNKNOWN_MODTIME_NSECS. - (`(t . ,time) - ;; If this records an obsolete save - ;; (not matching the actual disk file) - ;; then don't mark unmodified. - (when (or (equal time (visited-file-modtime)) - (and (consp time) - (equal (list (car time) (cdr time)) - (visited-file-modtime)))) - (when (fboundp 'unlock-buffer) - (unlock-buffer)) - (set-buffer-modified-p nil))) - ;; Element (nil PROP VAL BEG . END) is property change. - (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare)) - (when (or (> (point-min) beg) (< (point-max) end)) - (error "Changes to be undone are outside visible portion of buffer")) - (put-text-property beg end prop val)) - ;; Element (BEG . END) means range was inserted. - (`(,(and beg (pred integerp)) . ,(and end (pred integerp))) - ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp))) - ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end)) - (when (or (> (point-min) beg) (< (point-max) end)) - (error "Changes to be undone are outside visible portion of buffer")) - ;; Set point first thing, so that undoing this undo - ;; does not send point back to where it is now. - (goto-char beg) - (delete-region beg end)) - ;; Element (apply FUN . ARGS) means call FUN to undo. - (`(apply . ,fun-args) - (let ((currbuff (current-buffer))) - (if (integerp (car fun-args)) - ;; Long format: (apply DELTA START END FUN . ARGS). - (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args) - (start-mark (copy-marker start nil)) - (end-mark (copy-marker end t))) - (when (or (> (point-min) start) (< (point-max) end)) - (error "Changes to be undone are outside visible portion of buffer")) - (apply fun args) ;; Use `save-current-buffer'? - ;; Check that the function did what the entry - ;; said it would do. - (unless (and (= start start-mark) - (= (+ delta end) end-mark)) - (error "Changes to be undone by function different than announced")) - (set-marker start-mark nil) - (set-marker end-mark nil)) - (apply fun-args)) - (unless (eq currbuff (current-buffer)) - (error "Undo function switched buffer")) - (setq did-apply t))) - ;; Element (STRING . POS) means STRING was deleted. - (`(,(and string (pred stringp)) . ,(and pos (pred integerp))) - (when (let ((apos (abs pos))) - (or (< apos (point-min)) (> apos (point-max)))) - (error "Changes to be undone are outside visible portion of buffer")) - (let (valid-marker-adjustments) - ;; Check that marker adjustments which were recorded - ;; with the (STRING . POS) record are still valid, ie - ;; the markers haven't moved. We check their validity - ;; before reinserting the string so as we don't need to - ;; mind marker insertion-type. - (while (and (markerp (car-safe (car list))) - (integerp (cdr-safe (car list)))) - (let* ((marker-adj (pop list)) - (m (car marker-adj))) - (and (eq (marker-buffer m) (current-buffer)) - (= pos m) - (push marker-adj valid-marker-adjustments)))) - ;; Insert string and adjust point - (if (< pos 0) - (progn - (goto-char (- pos)) - (insert string)) - (goto-char pos) - (insert string) - (goto-char pos)) - ;; Adjust the valid marker adjustments - (dolist (adj valid-marker-adjustments) - (set-marker (car adj) - (- (car adj) (cdr adj)))))) - ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET. - (`(,(and marker (pred markerp)) . ,(and offset (pred integerp))) - (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry" - next) - ;; Even though these elements are not expected in the undo - ;; list, adjust them to be conservative for the 24.4 - ;; release. (Bug#16818) - (when (marker-buffer marker) - (set-marker marker - (- marker offset) - (marker-buffer marker)))) - (_ (error "Unrecognized entry in undo list %S" next)))) - (setq arg (1- arg))) - ;; Make sure an apply entry produces at least one undo entry, - ;; so the test in `undo' for continuing an undo series - ;; will work right. - (if (and did-apply - (eq oldlist buffer-undo-list)) - (setq buffer-undo-list - (cons (list 'apply 'cdr nil) buffer-undo-list)))) - list) + (oldlist buffer-undo-list)) + ;; Handle an integer by setting point to that value. + (pcase next + ((pred integerp) (goto-char next)) + ;; Element (t . TIME) records previous modtime. + ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or + ;; UNKNOWN_MODTIME_NSECS. + (`(t . ,time) + ;; If this records an obsolete save + ;; (not matching the actual disk file) + ;; then don't mark unmodified. + (when (or (equal time (visited-file-modtime)) + (and (consp time) + (equal (list (car time) (cdr time)) + (visited-file-modtime)))) + (when (fboundp 'unlock-buffer) + (unlock-buffer)) + (set-buffer-modified-p nil))) + ;; Element (nil PROP VAL BEG . END) is property change. + (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare)) + (when (or (> (point-min) beg) (< (point-max) end)) + (error "Changes to be undone are outside visible portion of buffer")) + (put-text-property beg end prop val)) + ;; Element (BEG . END) means range was inserted. + (`(,(and beg (pred integerp)) . ,(and end (pred integerp))) + ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp))) + ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end)) + (when (or (> (point-min) beg) (< (point-max) end)) + (error "Changes to be undone are outside visible portion of buffer")) + ;; Set point first thing, so that undoing this undo + ;; does not send point back to where it is now. + (goto-char beg) + (delete-region beg end)) + ;; Element (apply FUN . ARGS) means call FUN to undo. + (`(apply . ,fun-args) + (let ((currbuff (current-buffer))) + (if (integerp (car fun-args)) + ;; Long format: (apply DELTA START END FUN . ARGS). + (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args) + (start-mark (copy-marker start nil)) + (end-mark (copy-marker end t))) + (when (or (> (point-min) start) (< (point-max) end)) + (error "Changes to be undone are outside visible portion of buffer")) + (apply fun args) ;; Use `save-current-buffer'? + ;; Check that the function did what the entry + ;; said it would do. + (unless (and (= start start-mark) + (= (+ delta end) end-mark)) + (error "Changes to be undone by function different than announced")) + (set-marker start-mark nil) + (set-marker end-mark nil)) + (apply fun-args)) + (unless (eq currbuff (current-buffer)) + (error "Undo function switched buffer")) + ;; Make sure an apply entry produces at least one undo entry, + ;; so the test in `undo' for continuing an undo series + ;; will work right. + (when (eq oldlist buffer-undo-list) + (push (list 'apply 'cdr nil) buffer-undo-list)))) + ;; Element (STRING . POS) means STRING was deleted. + (`(,(and string (pred stringp)) . ,(and pos (pred integerp))) + (when (let ((apos (abs pos))) + (or (< apos (point-min)) (> apos (point-max)))) + (error "Changes to be undone are outside visible portion of buffer")) + ;; Insert string and adjust point + (if (< pos 0) + (progn + (goto-char (- pos)) + (insert string)) + (goto-char pos) + (insert string) + (goto-char pos))) + ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET. + (`(,(and marker (pred markerp)) . ,(and offset (pred integerp))) + (when (marker-buffer marker) + (set-marker marker + (- marker offset) + (marker-buffer marker)))) + (_ (error "Unrecognized entry in undo list %S" next))) + (not (eq oldlist buffer-undo-list)))) ;; Deep copy of a list (defun undo-copy-list (list) @@ -2353,17 +2391,22 @@ Return what remains of the list." elt)) (defun undo-start (&optional beg end) - "Set `pending-undo-list' to the front of the undo list. -The next call to `undo-more' will undo the most recently made change. -If BEG and END are specified, then only undo elements -that apply to text between BEG and END are used; other undo elements -are ignored. If BEG and END are nil, all undo elements are used." + "Set `pending-undo-list' to begin a run of undos. The next +call to `undo-more' will undo the next change group. If BEG and +END are specified, then only undo elements that apply to text +between BEG and END are used; other undo elements are ignored. +If BEG and END are nil, all undo elements are used." (if (eq buffer-undo-list t) (user-error "No undo information in this buffer")) (setq pending-undo-list (if (and beg end (not (= beg end))) - (undo-make-selective-list (min beg end) (max beg end)) - buffer-undo-list))) + (undo-make-regional-list (min beg end) (max beg end)) + (let ((list-i buffer-undo-list) + assoc-list) + (while list-i + (push (cons (car list-i) list-i) assoc-list) + (pop list-i)) + (nreverse assoc-list))))) ;; The positions given in elements of the undo list are the positions ;; as of the time that element was recorded to undo history. In @@ -2424,15 +2467,17 @@ are ignored. If BEG and END are nil, all undo elements are used." ;; "ccaabad", as though the first "d" became detached from the ;; original "ddd" insertion. This quirk is a FIXME. -(defun undo-make-selective-list (start end) - "Return a list of undo elements for the region START to END. -The elements come from `buffer-undo-list', but we keep only the -elements inside this region, and discard those outside this -region. The elements' positions are adjusted so as the returned -list can be applied to the current buffer." +(defun undo-make-regional-list (start end) + "Return a list of undo associations for the region START to END, + +The undo associations are of the form (ADJUSTED-ELT +. ORIG-UNDO-LIST) and are as documented for +pending-undo-list. Only associations for elements lying inside +the region are included. Their positions are adjusted based on +the discarded elements not fully in the region." (let ((ulist buffer-undo-list) - ;; A list of position adjusted undo elements in the region. - (selective-list (list nil)) + ;; The list of (ADJUSTED-ELT . ORIG-UNDO-LIST) to return + (selective-list (list (cons nil nil))) ;; A list of undo-deltas for out of region undo elements. undo-deltas undo-elt) @@ -2443,14 +2488,16 @@ list can be applied to the current buffer." (setq undo-elt (car ulist)) (cond ((null undo-elt) - ;; Don't put two nils together in the list - (when (car selective-list) - (push nil selective-list))) + (let (;; Undo boundary representation + (boundary (cons nil nil))) + ;; Don't put two undo boundaries together in the list + (unless (equal boundary (car selective-list)) + (push boundary selective-list)))) ((and (consp undo-elt) (eq (car undo-elt) t)) ;; This is a "was unmodified" element. Keep it ;; if we have kept everything thus far. (when (not undo-deltas) - (push undo-elt selective-list))) + (push (cons undo-elt ulist) selective-list))) ;; Skip over marker adjustments, instead relying ;; on finding them after (TEXT . POS) elements ((markerp (car-safe undo-elt)) @@ -2461,20 +2508,30 @@ list can be applied to the current buffer." (if (undo-elt-in-region adjusted-undo-elt start end) (progn (setq end (+ end (cdr (undo-delta adjusted-undo-elt)))) - (push adjusted-undo-elt selective-list) + (push (cons adjusted-undo-elt ulist) selective-list) ;; Keep (MARKER . ADJUSTMENT) if their (TEXT . POS) was ;; kept. primitive-undo may discard them later. (when (and (stringp (car-safe adjusted-undo-elt)) (integerp (cdr-safe adjusted-undo-elt))) (let ((list-i (cdr ulist))) (while (markerp (car-safe (car list-i))) - (push (pop list-i) selective-list))))) + (let ((marker-adj (pop list-i))) + (push (cons marker-adj marker-adj) + selective-list)))))) (let ((delta (undo-delta undo-elt))) (when (/= 0 (cdr delta)) (push delta undo-deltas))))))) (pop ulist)) (nreverse selective-list))) +(defun undo-make-selective-list (start end) + "Realize a full selective undo list per +undo-make-regional-generator." + (mapcar #'car (undo-make-regional-list start end))) +(make-obsolete 'undo-make-selective-list + "Use undo-make-regional-list instead." + "24.5") + (defun undo-elt-in-region (undo-elt start end) "Determine whether UNDO-ELT falls inside the region START ... END. If it crosses the edge, we return nil. ^ permalink raw reply related [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-05-28 18:42 ` Barry OReilly @ 2014-06-19 21:35 ` Stefan Monnier 0 siblings, 0 replies; 27+ messages in thread From: Stefan Monnier @ 2014-06-19 21:35 UTC (permalink / raw To: Barry OReilly; +Cc: 16411 > + "The pending undo elements in a run of consecutive undo commands. > +Specifically, this is a list of assocations of the > +form (ADJUSTED-ELT . ORIG-UNDO-LIST). ADJUSTED-ELT is an undo [...] > - (let ((equiv (gethash pending-undo-list undo-equiv-table))) > + ;; Check to see whether we're hitting a redo record > + (let ((equiv (gethash (cdr-safe pending-undo-list) undo-equiv-table))) Why take the cdr of pending-undo-list? IOW why skip the first element? Oh, and please punctuate your comments. > - (setq pending-undo-list equiv))) > + (setq pending-undo-list (cons (car equiv) equiv)))) I guess this brings the same question as above. > + (let ((list buffer-undo-list) > + (new-equiv (cdr-safe pending-undo-list))) And same here. > + (when (undo-primitive-elt elt) > + ;; Map the new undo element to what it undid. Not aware > + ;; yet of cases where we want to map all new elements. > + (puthash buffer-undo-list orig-tail undo-redo-table)) We should only do that in those cases where undo-equiv-table can't be used. Also, why did you have to move the valid-marker-adjustments thingy out of undo-primitive-elt? Stefan ^ permalink raw reply [flat|nested] 27+ messages in thread
* bug#16411: undo-only bugs 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly ` (4 preceding siblings ...) 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly @ 2014-05-14 13:32 ` Barry OReilly 5 siblings, 0 replies; 27+ messages in thread From: Barry OReilly @ 2014-05-14 13:32 UTC (permalink / raw To: 16411, Stefan Monnier [-- Attachment #1: Type: text/plain, Size: 208 bytes --] > 1: undo-only in region doesn't work. +2014-05-13 Stefan Monnier <monnier@iro.umontreal.ca> + + * simple.el (undo-make-selective-list): Obey undo-no-redo. Right, this one didn't need the refactor. Thanks. [-- Attachment #2: Type: text/html, Size: 319 bytes --] ^ permalink raw reply [flat|nested] 27+ messages in thread
end of thread, other threads:[~2014-06-19 21:35 UTC | newest] Thread overview: 27+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2014-01-10 22:33 bug#16411: undo-only bugs Barry OReilly 2014-01-10 23:54 ` Stefan Monnier 2014-01-11 3:48 ` Barry OReilly 2014-01-11 4:29 ` Stefan Monnier 2014-01-11 5:09 ` Barry OReilly 2014-01-14 0:49 ` Stefan Monnier 2014-01-14 1:52 ` Stefan Monnier 2014-01-14 14:00 ` Barry OReilly 2014-01-19 0:58 ` Barry OReilly 2014-01-19 3:18 ` Stefan Monnier 2014-01-19 16:57 ` Barry OReilly 2014-02-14 18:51 ` Barry OReilly 2014-02-14 22:29 ` Barry OReilly 2014-02-18 17:40 ` Barry OReilly 2014-02-26 15:20 ` bug#16411: undo in region corrupts existing text Barry OReilly 2014-02-27 5:02 ` Stefan Monnier 2014-05-13 15:01 ` bug#16411: undo-only bugs Barry OReilly 2014-05-14 18:06 ` Stefan Monnier 2014-05-14 18:45 ` Stefan Monnier 2014-05-14 19:55 ` Stefan Monnier 2014-05-14 21:56 ` Barry OReilly 2014-05-15 2:23 ` Stefan Monnier 2014-05-15 3:51 ` Barry OReilly 2014-05-15 13:00 ` Stefan Monnier 2014-05-28 18:42 ` Barry OReilly 2014-06-19 21:35 ` Stefan Monnier 2014-05-14 13:32 ` Barry OReilly
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.