Understanding the GURQ Algorithm

Just wanted to make some notes on “Resolving the Great Undo-Redo Quandary”. It was high on HackerNews, but I missed the window to post.

Here’s my attempt to visualize what the author described. This is what the undo/redo stacks would look like in the standard case (and, I believe what emacs does).

| iter | undo               | redo  | display | action  |
|------|--------------------|-------|---------|---------|
| 1    | A                  |       | A       | Add 'A' |
| 2    | AB                 |       | AB      | Add 'B' |
| 3    | ABC                |       | ABC     | Add 'C' |
| 4    | AB                 | C     | AB      | Undo    |
| 5    | A                  | CB    | A       | Undo    |
| 6    | ABC(-C)(-B)D       |       | AD      | Add 'D' |
| 8    | ABC(-C)(-B)        | D     | A       | Undo    |
| 9    | ABC(-C)            | D(-B) | AB      | Undo    |
| 10   | ABC(-C)(-B)D(-D)BE |       | ABE     | Add 'E' |

Then, there is this optimization.

Third, although it isn’t strictly necessary, we can add a slight shortcut because of redundancies. In the A-B-C example above, B) is redundant with A), because one is just the other in reverse. When the butterfly is squashed and we create B, we mark its beginning and end as “instant”; whenever we later traverse onto either end of B), we proceed to the opposite end in one fell swoop to save the user some traversal time. All edit states are recoverable from A & C alone. Again, it’s strictly optional, but less cumbersome.

After confirming with the author (thanks, Troy!) I now understand the behavior described would be like this:

| iter | undo                   | redo       | display | action  |
|------|------------------------|------------|---------|---------|
| 1    | A                      |            | A       | Add 'A' |
| 2    | AB                     |            | AB      | Add 'B' |
| 3    | ABC                    |            | ABC     | Add 'C' |
| 4    | AB                     | C          | AB      | Undo    |
| 5    | A                      | CB         | A       | Undo    |
| 6    | ABC(-C)(-B)D           |            | AD      | Add 'D' |
| 8    | ABC(-C)(-B)            | D          | A       | Undo    |
| 9    | ABC                    | D(-B)(-C)  | ABC     | Undo    |
| 10   | AB                     | D(-B)(-C)C | AB      | Undo    |
| 11   | ABC(-C)(-B)D(-D)BC(-C) |            | ABE     | Add 'E' |

Note the “fast forward” in step 9, where we rewind through both (-B)(-C).

Posts from blogs I follow

Resilient LL Parsing Tutorial

In this tutorial, I will explain a particular approach to parsing, which gracefully handles syntax errors and is thus suitable for language servers, which, by their nature, have to handle incomplete and invalid code. Explaining the problem and the solution…

via matklad May 21, 2023

🤠 "Where have all the hackers gone?" + a way to discuss programming languages 👨‍🎤

🎵 The song for this post is CHEMICAL LOVE, by "Kaleb James and Chey" for the game Bust-a-Groove. 🎵 I'm talking with friends and coworkers about programming languages (surprise), and I'm landing on a rough shape that these conversations take. I'll share it …

via More Pablo: all May 15, 2023

The Perfect Weekend-Project, or You Should Build a Blog

The latest from atthis.link

via atthis.link May 12, 2023

Generated by openring-rs