New CodePlex project: a simple Undo/Redo framework

New CodePlex project: a simple Undo/Redo framework

  • Comments 57

I just created a new CodePlex project: http://undo.codeplex.com

What

It's a simple framework to add Undo/Redo functionality to your applications, based on the classical Command design pattern. It supports merging actions, nested transactions, delayed execution (execution on top-level transaction commit) and possible non-linear undo history (where you can have a choice of multiple actions to redo).

The status of the project is Stable (released). I might add more stuff to it later, but right now it fully satisfies my needs. It's implemented in C# 3.0 (Visual Studio 2008) and I can build it for both desktop and Silverlight. The release has both binaries.

Existing Undo/Redo implementations

I do realize that my project is the reinvention of the wheel at its purest, existing implementations being most notably:

However I already have three projects that essentially share the exact same source code, so I decided that it would be good to at least extract this code into a reusable component, so perhaps not only me but someone else might find it useful too.

It's open-source and on CodePlex, so I also have a chance of benefiting from it if someone contributes to it :)

History

It all started in 2003 when I first added Undo/Redo support to the application that I was developing at that time. I followed the classical Command design pattern, together with Composite (for nested transactions) and Strategy (for plugging various, possibly non-linear undo buffers).

Then I needed Undo/Redo for my thesis, so I just took the source code and improved it a little bit. Then I started the Live Geometry project, took the same code and improved it there a little bit, fixing a couple of bugs. Now the mess is over, and I'm finally putting the code in one place :)

A good example of where this framework is used is the Live Geometry project (http://livegeometry.codeplex.com). It defines several actions such as AddFigureAction, RemoveFigureAction, MoveAction and SetPropertyAction.

Actions

Every action encapsulates a change to your domain model. The process of preparing the action is explicitly separated from executing it. The execution of an action might come at a much later stage after it's been prepared and scheduled.

Any action implements IAction and essentially provides two methods: one for actually doing the stuff, and another for undoing it.

/// <summary>
/// Encapsulates a user action (actually two actions: Do and Undo)
/// Can be anything.
/// You can give your implementation any information it needs to be able to
/// execute and rollback what it needs.
/// </summary>
public interface IAction
{
    /// <summary>
    /// Apply changes encapsulated by this object.
    /// </summary>
    void Execute();

    /// <summary>
    /// Undo changes made by a previous Execute call.
    /// </summary>
    void UnExecute();

    /// <summary>
    /// For most Actions, CanExecute is true when ExecuteCount = 0 (not yet executed)
    /// and false when ExecuteCount = 1 (already executed once)
    /// </summary>
    /// <returns>true if an encapsulated action can be applied</returns>
    bool CanExecute();

    /// <returns>true if an action was already executed and can be undone</returns>
    bool CanUnExecute();

    /// <summary>
    /// Attempts to take a new incoming action and instead of recording that one
    /// as a new action, just modify the current one so that it's summary effect is 
    /// a combination of both.
    /// </summary>
    /// <param name="followingAction"></param>
    /// <returns>true if the action agreed to merge, false if we want the followingAction
    /// to be tracked separately</returns>
    bool TryToMerge(IAction followingAction);

    /// <summary>
    /// Defines if the action can be merged with the previous one in the Undo buffer
    /// This is useful for long chains of consecutive operations of the same type,
    /// e.g. dragging something or typing some text
    /// </summary>
    bool AllowToMergeWithPrevious { get; set; }
}

Both methods share the same data required by the action implementation and are supplied when you create an action instance.

ActionManager

Your domain model (business objects) will likely have an instance of ActionManager that keeps track of the undo/redo buffer and provides the RecordAction(IAction) method. This method adds an action to the buffer and executes it. And then you have ActionManager.Undo(), ActionManager.Redo(), CanUndo(), CanRedo() and some more stuff.

As a rule, the thing that works for me is that I generally have two APIs: one that is public and lazy (i.e. it just creates an action and adds it to the buffer), and the other which is internal and eager, that does the actual work. Action implementation just calls into the eager API, while the public API is lazy and creates actions transparently for the consumer.

History

Right now I only have a SimpleHistory. Instead of having two stacks, I have a state machine, where Undo goes to the previous state and Redo goes to the next state, if available. Each graph edge stores an action (implementation of IAction). As the current state transitions along the graph edge, IAction.Execute or UnExecute is being called, depending on the direction in which we go (there is a logical "left" and "right" in this graph, which kind of represents "future" and "past").

 

image

It's possible for this linked list to become a tree, where you try something out (way1), don't like it, undo, try something else (way2), like it even less, undo, and choose to go back and redo way1. However this is not implemented yet.

Transactions

Transactions are groups of actions viewed as a single action (see Composite design pattern).

Here's a typical usage of a transaction:

public void Add(IEnumerable<IFigure> figures)
{
    using (Transaction.Create(ActionManager))
    {
        figures.ForEach(Add);
    }
}

If an action is recorded while a transaction is open (inside the using statement), it will be added to the transaction and executed only when the top-level transaction commits. This effectively delays all the lazy public API calls in the using statement until the transaction commits. You can specify that the actions are not delayed, but executed immediately - there is a corresponding overload of Transaction.Create specifically for that purpose.

Note that you can "misuse" this framework for purposes other than Undo/Redo: one prominent example is navigation with back/forward.

Update: I just posted some samples for the Undo Framework: http://blogs.msdn.com/kirillosenkov/archive/2009/07/02/samples-for-the-undo-framework.aspx

  • It's useful for me,

    can you put a demo project to the source code?or some unit tests,just for understand how to use it

  • Hi,

    I am looking for a application framework/architecture for winforms applications. I am planning to develop very small applications like customer address management/to do list etc., mostly they will be using access as back end and single user only.the framework/architecture i see in msdn suits for enterprise level development not for an hobbyist. can u guide on this perspective

  • Hi JimK,

    I added a couple of demo projects:

    http://blogs.msdn.com/kirillosenkov/archive/2009/07/02/samples-for-the-undo-framework.aspx

    Anandarajeshwaran:

    to be frank, I'm unaware of a good guidance for creating small scale WinForms client applications. Use your common sense, general design guidelines, design patterns and you'll be successful.

  • There is no need for undo-redo framework.

    All you need is purely functional

    data structures which provide

    multiple versions with efficient

    representation and update operatations.

    You history is then a list of

    (action-name, current-version).

    Design patterns are the wrong way

    to attack many problems.

  • I agree with Stefan...I am afraid you have just suffered death by patterns.

    Using the command pattern is a good start but not in the way you used it. A much better approach would be to use two stacks. The first stack contains the operations to be executed, whilst the second has undo operations. When adding a command to be executed, the undo method is also specified. Initially the undo stack would be empty whilst the execution stack contains the operations to be executed.

    When a command is executed sucessfully the undo operation is added to the undo stack. In the event of an exception, all methods in the undo stack would be executed ensuring the undo is in the same order as the normal execution.

    Of course to make this work you need to ensure that you have undo operations where required and that the undo methods work in the same order as the normal execution.

    I have some sample code if anyone is interested.

  • Stefan:

    I agree, immutability is the way to go. Undoing then is just bringing back a snapshot of your data-structure from back then.

    However there are a couple of points to keep in mind.

    1. There are existing projects out there that are not built in a functional way. A LOT of them. And they need guidance on how to implement Undo in their mutable world. I've seen applications where v1 allows undoing 1 step, and v2 is well advanced - it allows undoing 5 steps!!! Forget immutability, let's just start with not copying the whole world and being explicit about your operations.

    2. I believe that design patterns are something that every developer should know well. After getting to know them, one can decide for oneself - whether to use them or not, but this decision has to be conscious and weighted. I see that you probably know patterns very well and have chosen against them for "many problems". OK. Good for you. However my point is that one can't become a good developer (in the .NET world) without having a solid knowledge of patterns. If you decide to dump them in favor of functional style, LISP, DSLs, meta-programming or anything else - you're welcome. What I don't like is when someone critisizes patterns and doesn't know a thing about them (again, I'm sure you know your patterns well).

    David:

    That very well may be the case. I didn't promise my implementation is the best one.

    I'm very interested in your sample code :) Go ahead and share your experience with the rest of the world. http://code.msdn.com, or http://codeplex.com

  • David Myers: I am interested in your code. Do you have somewhere you could post it?

    Thanks

    Kevin

  • Its corporations and business who want you to think in design patterns, so that they can make money. In functional style a design pattern is simply a higher order function. Everything is much much much more light weight. Design patterns are not extensible

    and often non composable. One you choose to use one of them you are stuck, for the rest of the life of the application. Design patterns are top-down approach and therefore they "claim" they know the "future" of the application. Since no one can predict how an application will evolve, forget about top-down design and software architects. Software arichtects means incompetence. Use bottom-up and no-patterns. If you want to have persistance then simply use persistent data structures -- and you have a provable guarantee which you don't have an undo-redo framework. Persistance is composable -- undo-redo is not. You don't copy the whole structure upon update -- this is very important. Here is where algorithmics come into play. Simply google for "Purely functional data strucutres", read it and you

    have learned much much more than reading any design pattern book -- and you have learned something right.

    Using purely functional data structures, you simply don't have to solve any problem. Its very simple, all you effort is in algorithmic thinking -- how to design such a structure. But most of the purely functional data structures are out there -- simple lists, double ended queues, hash tables, trees -- the slow down and memory usage are usually logarithmic, in the size of the data structure -- which is nothing. Simply to keep a list of n operations is O(n). If one operation does an O(1) incremental update then you pay O(log(n)) in total -- its nothing compared to O(n) to keep a list of the names of the operations.

    The problem is not if your or mine code is good -- here the problem is fundamental -- it is what COMPUTING is all about -- coming up with simple solutions to complicated problems.

    Design patterns are complicated solution to compicated problems. I'm going to show you in a minute how design patterns are subsumed by functional programming.

  • Design Patterns is Software Developmment Done Wrong

    Design Patterns arise in the Object Oriented Programming Way

    The problem with OO style is first

     - mutability (small problem)

     - objects have multiple methods, this means that they are not built from the smallest attomic pieces (functions). Sometimes it is necessesary to have something like an OO-class (e.g. monads in functional programming -- a monad needs 3 functions), but in 90% it is not. This usually creates tight couping

     especially when combined with interfaces. Try changing the interface of IEnumerable for example and you have to change 90% of existing applications substantially.

     - top-down design (you need to draw your diagram before you begin coding -- need to know all about your application's future, but who can predict it?)

     - Object are non-composable (because of state and multiple methods and interfaces) without significant plannig -- this is the killer. A small change in the behavior of the program will imply a large change in the code)

     - Tight-copling -- this is also a killer

     - Non-cooperative components

    The biggest evil is on object-oriented thinking. Object orientedness lacks the following properties

    -- composability. Fix: use only simple functions. Use well-though-out and composable type-classes.

    -- non-intrusiveness: fix: templates (like C++) and generics, also static type classes

    Most design pattern solution actually propose either classes with state + multiple methods.

    Let's take a look at some desing patterns from wikipedia and

    show that those are either features of functional languages or

    a higher order function

    http://en.wikipedia.org/wiki/Design_pattern_(computer_science)

    Encapsulation and information hiding

    FP Solution: a closure

    Inheritance or subclassing

    A type class

    Many of those patterns are basically features of OO languages. They are not really design patterns...

    Let's look here: http://userpages.umbc.edu/~tarr/dp/fall00/cs491.html

    The observer pattern:

    Java example: a database connected to a graph view and a table view

    Solution: message passing Erlang-style

    Factory Pattern:

    Java Example: CreateDocument with methods open/close/save/revert

    Best solution is by type classes (in Haskell)

    However, this is not the best example for the factory pattern in func. prog. The best use case is a function returning a function

    Iterator Pattern:

    For example lists/streams with get_next()

    Solution: cons lists/delayed cons lists(streams)/yield (syntactic sugar)/higher order functions generating and consuming streams

    Facade Pattern

    Java Example: seal classes together

    Functional approach: modules

    The state pattern:

    A gui: object has a state and depending on actions and state change the state

    Functional approach: message passing with pattern matching. Also ability to pass closures and state, Best is to keep purely functional.

    Now those are the best:

    The Composite pattern: simply a dot in haskell and >> in F#

    Functors: a special type class in haskell (called Functor).

    Addapter patterns: a simple function, e.g. List.of_seq, Seq.of_list in (example in F#)

    The Decorator pattern: a function which wraps another function, e.g. read_only(takes as input a list) returns a read only list

    In conclusing, I would think again if I have to use OO and with it patterns.

    Recomendations: 1. avoid OO and especially OO design as much as possible. No big class diagrams, no UML, no type hierarchies.

                   If you have to design your program before you start coding

                   it then after a point the code will crumble against its weight. You cannot design against future/unknown requirements

                   so there is no point to try. Just make sure your code has two features: COMPOSABILITY and NON-Intrusiveness

                   2. Start simple. Usually programs are simply tranformations from one representations to another.

                   Use a library of higher order functions which can be composed together to make complicated transformations

                   Make a library of your own transformations if you want to avoid boiler plate code

                   3. Pass state around. Try to keep mutable state within a single function. For user interfaces use message

                   passing and monads(Haskell)/computation expressions(F#)/engines(Scheme)

    Gui Example (not compiled, but possible to write in this style):

    let db = open_db("...")

    let rec mygui = gui{

                       let state = get_state()

                       let t = state.num_tries

                       if (t > 0) then

                           do! mk_label "You tried too many times"

                       let! usernamebox = mk_textbox "User name:"

                       let! passwrdbox = mk_passwordbox "Password:"

                       do! button (fun msg ->

                                       match msg with

                                       | ButtonClicked -> let username = get_text usernamebox

                                                          let passwrd = get_text passwrdbox

                                                          if (lookup_db query{

                                                                           let! users = table db "users"

                                                                           filter(users, fun (this_user,this_passwrd -> username = username &&

                                                                                                                        this_passwrd = passwrd))

                                                                           |> count

                                                                        }) = 1 then

                                                                        //continue gui simply runs the next screen

                                                                        continue_gui nextgui (update_state state{user=username})

                                                           else                                                                    

                                                               continue_gui mygui (update_state state{num_tries = state.num_tries + 1})        

                   }                

    //run the initial screen

    continue_gui mygui mk_init_state()                

  • "Its corporations and business who want you to think in design patterns, so that they can make money."

    If that's true then thank you for warning me away from this functional stuff.  I'd hate to find myself using an approach that didn't lend itself to writing software that customers actually want to pay for.

  • There are two sides to this coin and the discussion seems to have diverted largely from the original intention of undo/redo.

    I think design patterns are a great tool such as a hammer however it is important that not everything is a nail.

  • Farid: you NAILED it!!! :)

  • Stefan: this deserves a separate blog post. Do you blog?

  • Stefan:

    I completely agree with you. I had been scratching my head with patterns before I came to know about functional world.

    I agree that the fundamental problem isn't that your code is good or mine, what should be the ideal pattern for a problem but The problem is how we think about problems and choose an appropriate solution. Functional programming is a natural way of computing. On the other hand, oop and design patterns give you a vocabulary at very high level to communicate about the problems and there solutions. I haven't seen anything like this in functional world. There are tradeoffs in each of the world. I'm still looking for some standard ways in functional world to design large scale systems and a higher level language to model (like design patterns).

  • Kirill: Stefan's posts regarding design patterns really should be a separate post/discussion. I would definitely be interested in hearing some of the opinions on both sides of the issue. I tend to agree with Stefan regarding design patterns, having seen them being misused repeatedly and turning relatively simple systems into a bloated, hard-to-maintain, ones. (p.s. I also hate the term "software architects" :-)

Page 1 of 4 (57 items) 1234
Leave a Comment
  • Please add 8 and 3 and type the answer here:
  • Post