Best practice for Undo Redo implementation in C# [closed]

Question

I need to implement Undo/Redo frame work for my window application(editor like powerpoint), what should be the best practice to follow, how would be handle all property changes of my objects and it reflection on UI.

Depside

Probably helpful: "Multilevel Undo and Redo Implementation in C#" 1 and 2 – Conglutinate

Answer 1

There are two classic patterns to use. The first is the memento pattern which is used to store snapshots of your complete object state. This is perhaps more system intensive than the command pattern, but it allows rollback very simply to an older snapshot. You could store the snapshots on disk a la PaintShop/PhotoShop or keep them in memory for smaller objects that don't require persistence. What you're doing is exactly what this pattern was designed for, so it should fit the bill slightly better than the Command Pattern suggested by others.

Also, an additional note is that because it doesn't require you to have reciprocal commands to undo something that was previously done, it means that any potentially one way functions [such as hashing or encryption] which can't be undone trivially using reciprocal commands can still be undone very simply by just rolling back to an older snapshot.

Also as pointed out, the command pattern which is potentially less resource intensive, so I will concede that in specific cases where:

• There is a large object state to be persisted and/or
• There are no destructive methods and
• Where reciprocal commands can be used very trivially to reverse any action taken

the command pattern may be a better fit [but not necessarily, it will depend very much on the situation]. In other cases, I would use the memento pattern.

I would probably refrain from using a mashup of the two because I tend to care about the developer that's going to come in behind me and maintain my code as well as it being my ethical responsibility to my employer to make that process as simple and inexpensive as possible. I see a mashup of the two patterns easily becoming an unmaintainable rat hole of discomfort that would be expensive to maintain.

Lecturer

+1 If the state of your objects are not very large, this is drastically simpler to implement than the undo/redo command pattern which can get complex very easily. And often times you will have destructive commands that cannot be undone without a full state copy anyway. But for very large states, this can be impractical. – Reams

Take a look at purely functional data structures; they can give you considerable sharing between the current live data and the mementos. – Diplopod

Take a look at state diffing described in my answer. Might be the better alternative depending on your use case. – Vitiate

The link to the momento pattern is dead. – Leadwort

you could also go for a hybrid approach where commands can still be destructive, and the state is large, but you keep snapshots of the state every now and again. Meaning in order to undo one step you would revert to the last snapshot and then replay the commands until one step before the current. Then you can control a trade-off between memory consumption and a single undo operation performance, by choosing how often do you store a full snapshot. – Ecdysiast

Answer 2

There are three approaches here that are viable. Memento Pattern (Snapshots), Command Pattern and State Diffing. They all have advantages and disadvantages and it really comes down to your use case, what data you are working with and what you are willing to implement.

I would go with State Diffing if you can get away with it as it combines memory reduction with ease of implementation and maintainability.

I'm going to quote an article describing the three approaches (Reference below).

Note that VoxelShop mentioned in the article is open source. So you can take a look at the complexity of the command pattern here: https://github.com/simlu/voxelshop/tree/develop/src/main/java/com/vitco/app/core/data/history

Below is an adapted excerpt from the article. However I do recommend that you read it in full.

---

Memento Pattern

Each history state stores a full copy. An action creates a new state and a pointer is used to move between the states to allow for undo and redo.

Pros

• Implementation is independent of the applied action. Once implemented we can add actions without worrying about breaking history.
• It is fast to advance to a predefined position in history. This is interesting when the actions applied between current and desired history position are computationally expensive.

Cons

• Memory Requirements can be significantly higher compared to other approaches.
• Loading time can be slow if the snapshots are large.

Command Pattern

Similar to the Memento Pattern, but instead of storing the full state, only the difference between the states is stored. The difference is stored as actions that can be applied and un-applied. When introducing a new action, apply and un-apply need to be implemented.

Pros

• Memory footprint is small. We only need to store the changes to the model and if these are small, then the history stack is also small.

Cons

• We can not go to an arbitrary position directly, but rather need to un-apply the history stack until we get there. This can be time consuming.
• Every action and it's reverse needs to be encapsulated in an object. If your action is non trivial this can be difficult. Mistakes in the (reverse) action are really hard to debug and can easily result in fatal crashes. Even simple looking actions usually involve a good amount of complexity. E.g. in case of the 3D Editor, the object for adding to the model needs to store what was added, what color was currently selected, what was overwritten, if mirror mode active etc.
• Can be challenging to implement and memory intensive when actions do not have a simple reverse, e.g when blurring an image.

State Diffing

Similar to the Command Pattern, but the difference is stored independent of the action by simply xor-nig the states. Introducing a new action does not require any special considerations.

Pros

• Implementation is independent of the applied action. Once the history functionality is added we can add actions without worrying about breaking history.
• Memory Requirements is usually much lower than for the Snapshot approach and in a lot of cases comparable to the Command Pattern approach. However this highly depends on the type of actions applied. E.g. inverting the color of an image using the Command Pattern should be very cheap, while State Diffing would save the whole image. Conversely when drawing a long free-form line, the Command Pattern approach might use more memory if it chained history entries for each pixel.

Cons / Limitations

• We can not go to an arbitrary position directly, but rather need to un-apply the history stack until we get there.
• We need to compute the diff between states. This can be expensive.
• Implementing the xor diff between model states might be hard to implement depending on your data model.

Reference:

https://www.linkedin.com/pulse/solving-history-hard-problem-lukas-siemon

Vitiate

These down-votes without explanation are really discouraging :/ – Vitiate

I imagine it's because you aren't exactly explaining anything. OP specifically asked about best practices, whereas you're simply providing pros and cons without even summarizing these methodologies. – Hayfork

@b1nary.atr0phy Finally some constructive feedback! I've adjusted the answer and would appreciate if you could remove your down-vote! – Vitiate

Contextually speaking, this is miles better. Wish granted :) – Hayfork

I don't understand why this wasn't marked the correct answer. It provides nonpartisan pros and cons for all valid approaches that I'm aware of. BenAlabaster's answer omits the state diff approach and tends to be pretty self righteous towards the end. – Renitarenitent

Answer 3

The classic practice is to follow the Command Pattern.

You can encapsulate any object that performs an action with a command, and have it perform the reverse action with an Undo() method. You store all the actions in a stack for an easy way of rewinding through them.

Unsung

This doesn't allow for one way functions such as hashing or mathematical functions that can't be 'undone' using a reciprocal method. Therefore this pattern should be used with care for this approach. – Lecturer

That's quite true. For general UI stuff it goes a long way though. – Unsung

Random question from someone who never implemented one of those patterns: Couldn't the command pattern easily store a snapshot of the previous state it altered to facilitate undo? Kinda like an unholy alliance between Command and Memento? Especially if many commands can be trivially undone storing snapshots for every action might be a bit expensive. – Representation

@Johannes - I guess you could use a mashup, using the command pattern for trivial functions and the memento pattern for less trivial functions. It should perform well, but it could potentially be a headache to maintain. Considering the trivial cost of memory/disk space, I'd say go one way or the other. If you don't have one way functions, use the Command Pattern, if you do, use the Memento Pattern. – Lecturer

@Ben that's usually the case with the command approach. For each command, you need to store a little bit of state to undo the command. Take for example a DeleteSelectedTextCommand whose undo command would need the text that was deleted. In some cases the undo state just needs to include the whole state. But for most cases, I think your suggestion of always using full state copies is the most practical solution. – Reams

Answer 4

Take a look at the Command Pattern. You have to encapsulate every change to your model into separate command objects.

Trematode

See my comment on Womp's answer for using the command pattern for 'undo' mechanisms – Lecturer

Answer 5

I wrote a really flexible system to keep track of changes. I have a drawing program which implements 2 types of changes:

• add/remove a shape
• property change of a shape

Base class:

public abstract class Actie
{
    public Actie(Vorm[] Vormen)
    {
        vormen = Vormen;
    }

    private Vorm[] vormen = new Vorm[] { };
    public Vorm[] Vormen
    {
        get { return vormen; }
    }

    public abstract void Undo();
    public abstract void Redo();
}

Derived class for adding shapes:

public class VormenToegevoegdActie : Actie
{
    public VormenToegevoegdActie(Vorm[] Vormen, Tekening tek)
        : base(Vormen)
    {
        this.tek = tek;
    }

    private Tekening tek;
    public override void Redo()
    {
        tek.Vormen.CanRaiseEvents = false;
        tek.Vormen.AddRange(Vormen);
        tek.Vormen.CanRaiseEvents = true;
    }

    public override void Undo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Remove(v);
        tek.Vormen.CanRaiseEvents = true;
    }
}

Derived class for removing shapes:

public class VormenVerwijderdActie : Actie
{
    public VormenVerwijderdActie(Vorm[] Vormen, Tekening tek)
        : base(Vormen)
    {
        this.tek = tek;
    }

    private Tekening tek;
    public override void Redo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Remove(v);
        tek.Vormen.CanRaiseEvents = true;
    }

    public override void Undo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Add(v);
        tek.Vormen.CanRaiseEvents = true;
    }
}

Derived class for property changes:

public class PropertyChangedActie : Actie
{
    public PropertyChangedActie(Vorm[] Vormen, string PropertyName, object OldValue, object NewValue)
        : base(Vormen)
    {
        propertyName = PropertyName;
        oldValue = OldValue;
        newValue = NewValue;
    }

    private object oldValue;
    public object OldValue
    {
        get { return oldValue; }
    }

    private object newValue;
    public object NewValue
    {
        get { return newValue; }
    }

    private string propertyName;
    public string PropertyName
    {
        get { return propertyName; }
    }

    public override void Undo()
    {
        //Type t = base.Vorm.GetType();
        PropertyInfo info = Vormen.First().GetType().GetProperty(propertyName);
        foreach(Vorm v in Vormen)
        {
            v.CanRaiseVeranderdEvent = false;
            info.SetValue(v, oldValue, null);
            v.CanRaiseVeranderdEvent = true;
        }
    }
    public override void Redo()
    {
        //Type t = base.Vorm.GetType();
        PropertyInfo info = Vormen.First().GetType().GetProperty(propertyName);
        foreach(Vorm v in Vormen)
        {
            v.CanRaiseVeranderdEvent = false;
            info.SetValue(v, newValue, null);
            v.CanRaiseVeranderdEvent = true;
        }
    }
}

With each time Vormen = the array of items that are submitted to the change. And it should be used like this:

Declaration of the stacks:

Stack<Actie> UndoStack = new Stack<Actie>();
Stack<Actie> RedoStack = new Stack<Actie>();

Adding a new shape (eg. Point)

VormenToegevoegdActie vta = new VormenToegevoegdActie(new Vorm[] { NieuweVorm }, this);
UndoStack.Push(vta);
RedoStack.Clear();

Removing a selected shape

VormenVerwijderdActie vva = new VormenVerwijderdActie(to_remove, this);
UndoStack.Push(vva);
RedoStack.Clear();

Registering a property change

PropertyChangedActie ppa = new PropertyChangedActie(new Vorm[] { (Vorm)e.Object }, e.PropName, e.OldValue, e.NewValue);
UndoStack.Push(ppa);
RedoStack.Clear();

Finally the Undo/Redo action

public void Undo()
{
    Actie a = UndoStack.Pop();
    RedoStack.Push(a);
    a.Undo();
}

public void Redo()
{
    Actie a = RedoStack.Pop();
    UndoStack.Push(a);
    a.Redo();
}

I think this is the most effective way of implementing a undo-redo algorithm. For an example, look at this page on my website: DrawIt.

I implemented the undo redo stuff at around line 479 of the file Tekening.cs. You can download the source code. It can be implemented by any kind of application.

Touch

Please note if you want to promote your own product/blog you must disclose your affiliation in the answer, otherwise, your answer may be flagged as spam. If you are not affiliated with the site, I recommend you say so to prevent this. Please read How to not be a spammer – Nature