Clone

HTTPS: git clone https://vervis.peers.community/repos/yEzqv

SSH: git clone USERNAME@vervis.peers.community:yEzqv

Branches

master

undo.mdwn

I’m porting my CommandStack class, written in C++, to a Haskell module. Its current planned name is undo, and the module is Control.Undo. I’d like to have a page here which explains the theory of how the stack works. Maybe I’ll move this documentation to haddock later.

Document

State on which actions are performed.

Action

A modification over a document which can be performed and undone.

ActionManager

This is a class, an instance of which can be used by an application or any other kind of program to provide undo/redo functionality.

ActionStack

This is an instance of the ActionManager class, based on a bidirectional stack. This is where the theory part comes in. The diagram with the 2 markers.

Each stack element is a pair. The first item is the action. The second item is a Boolean which says whether the action is attached to the one before it (which means they get undone and redone together).

There are 2 markers pointing to positions in the stack. If the explanation here is confusing, just move on to the diagrams, which will hopefully make it easier to understand.

firstUndone: The oldest action in the stack which hasn’t been done. For example, suppose we ran 10 actions, numbered 1 to 10, in this order. Then we undid the last 3 actions. The oldest action that we didn’t do, i.e. undid, is number 8. Value examples, assuming a stack of 5 actions:
- 0 - All of the actions have been undone
- 3 - The first 3 actions (0, 1, 2) were run. The rest (3, 4) have been undone
- 5 - All 5 actions have been run, nothing is undone
firstUnsaved: The oldest action whose results aren’t stored. The meaning of stored is application specific. Some applications save models to files, some may send them over the network and so on. Value examples, assuming a stack of 5 actions:
- Nothing - None of the actions’ results are saved
- Just 0 - The state in which all actions are undone is saved
- Just 1 - The results of action 0, i.e. the first action, are saved
- Just 5 - The results of action 4, i.e. the fifth action, are saved. In other words, the state in which all 5 actions have been run is saved

We begin with an empty stack. R marks firstUndone and S marks firstUnsaved. The symbol (S) means the value is Nothing.

      .--------------------------------.
R (S) '--------------------------------' 0 bottom top

What it means is:

We didn’t run any actions
No state is considered saved

We’ll start adding actions, ignoring the attached feature until later. Its default value can be False for now.

Now suppose we run action A. The stack now looks like this:

   R                                     1 top
      .--------------------------------.
  (S) |       A       |      False     | 0 bottom
      '--------------------------------'

What the above means is:

We did action A
No state is considered saved

Let’s run actions B and C too:

   R                                     3 top
      .--------------------------------.
      |       C       |      False     | 2
      .--------------------------------.
      |       B       |      False     | 1
      .--------------------------------.
  (S) |       A       |      False     | 0 bottom
      '--------------------------------'

Now we press the Save key, and the application saves the document to a file:

R S                                    3 top
    .--------------------------------.
    |       C       |      False     | 2
    .--------------------------------.
    |       B       |      False     | 1
    .--------------------------------.
    |       A       |      False     | 0 bottom
    '--------------------------------'

The above means:

We did actions A, B, C
The state in which A, B and C are done, which is the current state, is considered saved. If we close the application now, there should be no “You have unsaved changes” warning. S exists precisely to allow applications to determine whether there are unsaved changes.

TODO next is: add 2 more actions, undo them, continue undoing, then start redoing

BidiStack

TODO write…

AnnotatedStack

NOTE: not used so far

This is a general-purpose concept, which ActionStack uses as its data backend. It can be implemented using lists, arrays, vectors and so on. Whatever is best. I don’t believe the data structure itself matters that much for efficiency, but perhaps the way data is copied around does matter, because Actions can hold a lot of data (e.g. a copy of a document’s previous state or a large edit).

An AnnotatedStack is basically a sequence container with two types of annotations. One type of annotation is attached to each sequence item, which means the container stored pairs - a value item and its annotation value. The second annotation type is a pointer to a sequence item. These pointers can be referred to be a type that’s part of the AnnotatedStack class. You can make it an enum (e.g. [[!format hs “data Annotation = MarkerA | MarkerB | MarkerC”]] or an Int which references a list or anything else you like.

[See repo JSON]