New CodePlex project: a simple Undo/Redo framework


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


Comments (58)

  1. JimK says:

    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

  2. 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

  3. Kirill Osenkov says:

    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.

  4. Stefan says:

    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.

  5. David Myers says:

    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.

  6. Kirill Osenkov says:

    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

  7. Kevin says:

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

    Thanks

    Kevin

  8. Stefan says:

    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.

  9. Stefan says:

    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()                

  10. NSFW says:

    "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.

  11. Farid Zakaria says:

    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.

  12. Kirill Osenkov says:

    Farid: you NAILED it!!! :)

  13. Kirill Osenkov says:

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

  14. Khurram says:

    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).

  15. M. Wernig says:

    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" :-)

  16. Dave says:

    Stefan:

    It looks like you apply the monolithic paradigm very well.  I’m sure the work you do has never made it beyond academia where everything is about the algorithms used in implementations, but in the real world, be it enterprise development, game development, or device driver development, the type of spaghetti code that your style of functional programming leads to never produces a complete solution that is useful or maintainable.  

    Even your example does not provide a solution on target with the Undo/Redo framework, instead providing a trite example of how much garbage you can shove into a function.  If you want to illustrate how much better functional programming can be, you should create a functional version of Kirill’s solution so we can understand the downfall of our foolish OO ways that we somehow managed to produce maintainable software.  This means you have to create a complete, buildable solution, not just throw up some theoretical code.  I would love to see it, rather than an academic example that is missing your functional tenants of simple and composable, even for the basic task of validating a login.

  17. Dave #2 says:

    @Dave:

    My thoughts exactly. I want to like functional software, but everything I see about it being "superior" is theoretical.

    Show me an enterprise level, distributed system, and then I can take you seriously.

  18. @Dave:

    Beautiful. Everything I’ve read on FP is academic, and they spend all their time trying to figure out how to make something like a Queue immutable. WTH!? Convince me of the BUSINESS VALUE of something, then I’ll look at it.

  19. Ben says:

    Don’t EVER listen to a compsci major / phd about anything real world..

  20. Christian says:

    @Bruce

    try to weigh everything with business value and you are stuck in repetition because looking outside the box is costly at first and who knows whether you are being rewarded.

    @Ben

    It is those majors/phds who add to the existing body of knowledge – or inversely without them you wouldn’t even be programming using punch cards. Clearly, not every aspect of theory has a direct application in the non-academic world but as Jeff Atwood has demonstrated recently, there is even practical value in the P=NP problem (http://www.codinghorror.com/blog/archives/001270.html).

    Now, I agree with that before before touting something without proof one should think carefully about the word one uses. However, I believe this form of discussion repeats itself (Assembler vs. C, C vs. C++, …). Clearly, (at the moment) functional programming languages can be used more efficiently (lines of code per hour/$) for certain classes of problems ("number crunching" if you will, etc.). For example, banks use FP in the development of risk assessment programs, chemical companies use FP in the development of gene/molecule sequencing programs. Routing algorithms, Spam filter, Machine Learning utilizing apps, …

    Now, if you consider the above type of applications as something of pure theoretical/ academic value, you are certainly right (but I believe then we might have a different interpretation of academic/theoretic).

    To make a long story short, if boundaries are not pushed there is no progress – and clearly I wouldn’t want to be a developer in a world where the same type of applications are developed using the same old-style methods (remember before the invention of quicksort there was only linear sort).

  21. Stefan says:

    Actually, all the possible project mentioneds:

    — Kiril’s live geometry project

    — Distributed systems

    have simpler (and beatiful) solutions by Functional Programming (that are more

    likely to work).

    Let me give you challenge: implement

    a parallel/distributed version of

    K-means clustering algorithm in 10 lines

    of code in OOP. Then we can talk.

    I choose this problem because it is just

    10 lines (matching my implementation). Kiril’s system would be more lines, that’s why I propose this.

  22. Dave #2 says:

    @Stefan,

    You prove my point exactly. An algorithm is the same kind of example I always see. An academic, but useless example.

    I issued the challenge initially:

    Show ME a an n-tier enterprise solution implemented with a functional language, then we can talk.

  23. Dave says:

    I’m not trying to pit OO against FP or C# against Lisp.  I think whatever technique and toolset makes the most sense for the solution is the best, and I’m sure there are some scenarios where FP makes great sense – I’m just not seeing it here.  Instead, I’ve seen a usable OO solution by Kirill for an Undo / Redo framework, followed by a diatribe by Stefan on how OO is terrible and an FP solution would be so much better.  But I don’t see an FP solution, and in my C# OO mind, or even in an IronPython blend of OO and FP, I’m having trouble conceptualizing how an FP solution would be better.  

    Again, I’d really like to see a complete FP solution to this problem, because I’m always a fan of applying different techniques.  I really don’t think Kirill posted this blog entry to discuss the merits of OOP, but rather to present an implementation of an Undo/Redo Framework using a design pattern.  The point of a design pattern isn’t to show off OOP skills but rather to communicate a software design using generally understood programming techniques.  I’m willing to bet there are FP design patterns as well, right?

    Stephan – rather than continuing to come up with new algorithmic challenges, why don’t you just take on the challenge Kirill did (staying with the topic of this blog) and create an FP version of the Undo/Redo Framework.  I’m sure if a parallel K-means clustering algorithm can be done in 10 lines of FP, then the Undo/Redo Framework is what, 3 or 4?  It sounds great!  Show me!

  24. Marjan says:

    FP is good for trying algorithms in a quick way. If you want to build system that will be extendable and modular FP fails.

    Also correcting mistakes and bugs is quite harder in FP than in OO, not to say communication between scenarios, n-tier architectures.

  25. Rajesh says:

    I gone though both the aspects of OO and FP. It all depends upon the organisation and implementation along with the past experince. Approach should be to make it workable and maintainable

  26. Catto says:

    Hey Now Kirill,

    That sure is a good project.

    Thx 4 the info,

    Catto

  27. Danny P says:

    A Design Pattern is not the way you should do things, but merely the way people do things already, but formally documented. This is why they don’t say you "invented" a pattern, but instead you "discovered" a pattern.

    I do agree there is a number of people out there trying use the wrong design pattern for their problems, or even using design patterns where none are required (just for the sake of using it). A good understanding of Design Patterns in the OOP world is crucial for good software design, for it provides you with toolset of solutions for problems you (we) oftenly bump into when building enterprise application.

    I believe FP has it’s applicability as much as Design Patterns. It all depends on the problem you’re trying to solve.

    I would also like to re-iterate the challange, and have the FP-defenders (that claim FP is "better" than Design Patterns), to come up with a better solution for the Undo/Redo problem. Also, please let us know on which aspects it tops the rival (performance, maintenability, testability, reusability, etc).

    If anyone is creating a forum discussion or a blog post based on the OOP x FP debate, please post the link here so we all can participate (and learn from it).

  28. Kirill:

    Thanks for sharing your work, its truely unfortunate that people have decided to turn your work in to a debate about FP vs OOP. I know how much effort it takes to prepare your work for public consumption, and I find it objectionable that its been turned into a meaningless debate and an attack on your work. Seriously if you dont like the implementation then dont use it.

    Its this type of mindless debate and criticism that prevents people posting their work.

  29. Kirill Osenkov says:

    Garry: thanks! To be frank, I totally don’t mind this discussion. It’s interesting to watch and it provokes thought. I might not agree with everything that has been said, but that’s fine. I only regret that I haven’t created a separate blog post in time to discuss FP vs. OOP – but I thought that would become just another holy war.

    Also I don’t perceive anything here as an attack – people can write whatever they want in a common process of "finding the truth". As long as there are a couple of people who find this framework/approach useful – I consider my job fulfilled.

    I’m also not afraid that Design Patterns critisism will scare people away from projects like these – one should be able to judge for oneself – if one likes it, one will use it regardless of what others say :)

    In any case, I might post a separate article on FP vs. OOP, but I’m not sure if it’s going to be fruitful.

    Take care,

    Kirill

  30. @Christian:

    What’s really funny about the "looking outside the box is costly" comment is that I remember back in the 90’s when managers and such were against OOP because it was costly and required more analysis, etc. This was back when I was programming configuration systems in Lisp, ironically. The pendulum truly does swing…

  31. Christian says:

    @Bruce

    must be interesting to have this kind of experience (enables one to smile some sort of when some people jump overly excited on the train of buzzwords and almost self-fulfilling prophecies).

    Now, with the recent convergence of functional and object-oriented languages (F# + OO constructs <–> C# + lambdas, …) there isn’t really one one beats it all programming language. Also, since many OO languages offer nothing more than syntactic suggar to coat the simple message sender-receiver paradigm, one may implement OO atop a lot languages (clearly not as beautiful and safe). For example, if one looks at the source code of Quake 1 one finds OO concepts embedded into C code.

    Lastly, thanks to Kirill for providing brain-food, because this is what it should be about (as it has been mentioned) get the mind to think about something beautiful – solving a problem (in one of many ways)!

  32. edmund yau says:

    very very good framework, i am using it, thank you for your great affort

    @@@@@@@@@@@@@@@@@@@@

    係IT super manager, 唔係super IT manager

    http://www.geocities.com/it_super_manager

    IT界最強技術王, 名字擬似:edmund yau

  33. Matt Ellen says:

    Hi Stephan,

    I’m not entirely sure you’ve grasped OO programming.

    The whole point is to allow programmers to think like people when writing programmes, rather than having to think like a computer.

    OO may take more code than FP code, but it is better code in terms of readability and maintainability.

    Anyone can think like a person (generally speaking 😉 ) but it takes a lot more restraint to think like a computer. Why restrain yourself like this when at the same time trying to be creative?

    Maybe you’ve been trying to apply OO techniques where they aren’t appropriate, and have come to the conclusion that FP trump OO in all cases.

    That said – I’d be very interested to see a FP version of undo/redo. If you have an example please post it so we can evaluate what you say.

    Regards,

    Matt

  34. MAMA Jack says:

    coolo, just what I might need if i was writing a professional app. A killer app, many would say it were.

  35. Brian says:

    Funniest quote of this whole thread:

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

    I work for a software development services company.  More often than not the companies we develop for have us maintain the apps we’ve written for them.  I can take a kid fresh out of college, plop him down in front of visual studio and with minimal instruction (though obviously heavy supervision for one fresh out of college) I can get him maintaining one of our customers apps.

    As Matt said, "OO may take more code than FP code, but it is better code in terms of readability and maintainability."  

    I’ve said in my blog, "Writing code is easy. Writing code cleanly, efficiently so it’s easy to maintain, now that takes some skill."

    From a business perspective FP doesn’t make a lot of sense.  I’m not saying FP doesn’t have it’s applications.  I’m saying that team development of large scale applications and the maintenance of those applications become so complex that I suspect a company wouldn’t make much money off of them.  With OO we can develop large scale applications and turn around a nice profit from the development and maintenance of those applications.

    FP might be fine for small projects with small maintenance tails and small teams.  The problem with large projects is that, though we tend to have low turn-around, turn-around happens.  With OO I can lead a team of ten engineers, lose one or two, drop one or two back in and there is minimal impact to the project.

    @Stefan:  What middle or large scale projects (which I would define as being developed by a team of 5 or more engineers, 100 person or more user base and a three to five year maintenance tail) are out there that are developed in FP and turning a profit for the company that developed it?

    I’m not opposed to the idea of FP, just this idea that is seems like you want to replace all OO with FP and that just seems like a bad application of FP.

    Back on topic, thanks for this code Kirill.  I’ve looked at both of the samples and everything seems fairly straight forward.  This will make my life easier.  Though the project I’m working on now is too far along in development to integrate your framework I’ll make sure whatever architect I’m working with on our next application is aware of the framework.  Integration from the beginning design phases seems key to any core framework.

    Thanks,

    Brian

  36. Randy says:

    Kirill, this is a nice implementation of undo/redo for mutable data structures.  I don’t want to throw fuel on the language/abstraction war, but immutable data structures do provide an easier/safer way to build undo/redo.  Given the use of a garbage collected language like c#, it is fairly easy to build immutable data structures, and is a technique that can be applied independently of functional programming.  Indeed it works quite well in an object-oriented design, too.

    For those who haven’t built large applications with undo/redo, a significant challenge is ensuring that your do/undo methods are perfect mirrors.  One helpful approach is to create a small library of "actions", and everything else is built as a combination of these small, proven actions, and therefore undoing a larger action is simply undoing the set of sub-actions in reverse order.

    The final plug for immutable data structures is if you have background processes that will operate on the document in parallel with the users changes (think text editor with background compilation or something similar).  With an immutable system, this can be done easily and safely (just restart the background process periodically if the document changes).  With mutable documents, all of the foreground (user) mutations must be synchronized with the background process.

    -Randy

  37. Spaceus says:

    Evolution is a bad thing or how am I to read this… A pattern well applied should as I see it hide the complexity of the problems your application handles. A way of getting to the core problem ( The part we get paid for). A pattern like the command pattern applied correctly would limit you app in anyway eventhough it evolves in ways you’ve never thought of..

    Just my 2 cents

  38. Philips says:

    I made the following change in TransactionBase. The problem is that if you rollback the transaction inside a using statement then it crashes.

           public virtual void Rollback()

           {

               if (ActionManager != null)

               {

                   ActionManager.RollBackTransaction();

                   Aborted = true;

               }

           }

           public bool Aborted { get; set; }

           public void Dispose()

           {

               if(!this.Aborted)

                   Commit();

           }

  39. Philips says:

    I think that inside public void RecordAction(IAction existingAction) the following two lines must be added:

               if (this.History.CurrentState.NextAction != null)

               this.History.Clear();

    i.e. if you are back to history and record a new action the history must be cleared

  40. Kirill Osenkov says:

    Thanks Philips, I’ve checked in your first change.

    About the second point though, if you’re back in history and record a new action, the old next action will get dereferenced and will be garbage collected. So no need for this code.

    If you still believe that there is bug in the code around RecordAction and clearing history, please provide a repro in terms of the MinimalConsole sample.

    Thanks!

    P.S. I should really add unit tests to this project.

  41. Anwar says:

    Hello,

    Can you post the Silverlight Application for this.

    I converted the existing winformsample application to Silverlight and the Redo functionality is not working as it working in winforms.

    Thanks,

    Anwar

  42. Ramesh says:

    Hi Kirill,

    i have used your Undo framework in my Application.

    I have one doubt….Actually my application is Big one, whether it gives me any issue iwth memory…if Actions are more

  43. Ramesh says:

    Hi Kirill,

    i have used your Undo framework in my Application.

    I have one doubt….Actually my application is Big one, whether it gives me any issue iwth memory…if Actions are more

  44. Kirill Osenkov says:

    Hi Ramesh,

    indeed, the Undo stack will keep references to your domain model’s old state, so the Garbage Collector will not collect them. This is something to be aware of.

    However any other Undo framework implementation will have the same limitation. You can use the profiler to measure the impact of keeping the undo history in memory.

    I’m afraid that the rest is specific to your particular application and there is no general advice that I can give. Just use the profiler when in doubt.

    One final point is that I found that Undo buffer in two of my projects contributed only insignificantly to the memory consumption, but it’s still worth checking.

    Thanks,

    Kirill

  45. Vikas says:

    Hi Kirill,

      What all I have to do if I want to limit 10 actions for Undo-Redo?

  46. Vikas says:

    Hi Kirill,

    Nevermind.  I’m not sure why I asked that.  I am not a baby.  I do not need you to hold my hand through every trivial thing.  You gave me an example and I should use my own brain to learn how to build upon that to create my own implementation.

  47. AliPST says:

    Hi Kirill

    Great work, thank you for sharing it and the participant in Informative discussion about it.

    I have some questions about details:

    1-In RecordAction function, the CheckNotRunningBeforeRecording(existingAction) called 2 times: first directly and second in RunActionDirectly(existingAction) function.

    Why?

    2-If I want to use this frame work in a composite application (like MS CAB+SCSF), what will be it’s role? As I understand it will become a central point that all the modules and work items should pass their command/action to it! this is not good, is it?

  48. AliPST says:

    And about memory:

    I run the winformsample, it start with about 18 mb  memory, and after a few changing in name & age field, consumed memory grow up to 21 mb! and I think it is relatively a big number, for one int and one string field!

    on the other hand, if you know Autodesk AutoCAD software, I run some test on it too, and I can not detect this behavior! it seems there is no growing  in memory consumption or it’s very small.

    Can you help me on this?

  49. Kirill Osenkov says:

    Hi Vikas,

    sorry for the delayed reply, I’m currently on vacation. No, the issue you mention is actually great feedback, so no worries here. I definitely need to look into adding a property to ActionManager saying MaxHistoryLength or something. BTW if you came up with a solution for this, you can send me a patch or a shelveset, if you feel like :)

    AliPst: this is a good find and is most likely a bug :) I’m now on vacation but once I get back I definitely will look into this. As for your second question, ActionManager should be a service that everyone consumes on an as needed basis. If you’re using a dependency injection container such as MEF, wherever you need to track undo changes, import an ActionManager or make it a singleton. It’s OK if a lot of things reference it. But of course, I can’t tell more without looking at your particular implementation. If you use this framework in a large project, I’d be happy to hear any reports or feedback.

    Also a note to everyone – the project is open source and if you’d like to send in an improvement, you’re welcome to do so. After one or two quality contributions I can add you as a developer to the project.

    AliPST, regarding your second message, it looks like a memory leak. I’ll take a look sometime later.

    Thanks,

    Kirill

  50. Kirill Osenkov says:

    Thanks all, I’ve logged 3 bugs in the project bug tracker: http://undo.codeplex.com/WorkItem/List.aspx

    I’ll deal with them whenever I have some time. Keep the great feedback coming!

    Thanks,

    Kirill

  51. Sergey Arhipenko says:

    Hi, Kirill

    Thanks for referencing to my DejaVu project.

    It exists for a long time but not many people know about it. DejaVu uses different approach and I am happy that I did not choose Command Pattern.

    Actually, I would not recomend to anyone to use Command Pattern for Undo/Redo implementation.

    The general point is: it should not be solved on business logic level – it should be solved on data level. If you use Command Pattern, complexity will grow exponentially when number of commands/data entities increased. Solving undo/redo on data level tames complexity on the same level – no matter how many commands/data do you have.

  52. Mark D says:

    Thanks for the code. It’s very well written and has saved me a lot of time starting from scratch. I’m in the process of converting this code to actionscript and using it in a Flex application I’m working on.  My application is a kind of rich text editor.  Things are going well, but I’m starting to think that I’m using transactions in a way that you may not have intended to, and I was wondering if you could give me your opinion on it.

    In my case, when you type a character, one of several actions can occur depending on different things.  For instance, inserting a text node with a value, or if the current node is currently a text node, adding a character to it and lastly moving the caret position to after the character.

    The way I implemented this is that I made actions for adding nodes, removing nodes, inserting characters into existing text nodes, and lastly moving the caret.

    I made use of the transaction and created a transaction at the highest level in my code as possible, basically in the keypress handler.  That way I didn’t have to concern myself with all the different permutations the code took when handling keypress.  All I cared about was at the end that if you undid the action, it would undo everything that was created during that keypress.

    This works fine, however, it totally disables the "merging" aspect of the framework.  It seems that the multiAction used in transactions will never attempt to merge.  The tryToMerge method returns false.

    I can kind of see why you did it this way since the "rules" for merging multiactions may be specific to the application.

    I’m considering altering this portion of the code to somehow iterate through the children in some systematic way to determine if things can be merged, but I have quite figured out how I’m going to do this.

    One way is to just look at the last guy in the multiaction, but that won’t help me since for me that’s usually a move caret action.  I need to look one more back into the multiaction to find the "insert text node" or the "insert character into a text node" actions.  In this case subsequent insert characters should merge with this.  This starts to get complicated though so I wonder if I’m looking at this the wrong way.

    If you have any insight into this, I would be interested to hear it.

    Thanks.

  53. Mark D says:

    I noticed that you have a property for AllowToMergeWithPrevious, but it doesn’t seem that it’s being used anywhere.

  54. Cooper M says:

    Krill, others, has this been integrated with the WPF and Silverlight DataGrid? I need to add undo ability in those controls and would love to get my hands on any such code out there.

    Thanks

  55. Kirill Osenkov says:

    Cooper M,

    sorry, I don't have it integrated with DataGrid. You're on your own there unfortunately. Good luck!

  56. Cooper M says:

    Krill, ok. Question for you. Normally, in controls like DataGrid, we would setup binding between the data properties and the editing controls (like TextBox, etc.). Now, we will have to somehow intercept/reroute this Binding to make it go through the Action implementations (so they can be undone/redone). Do you have a pattern that you can recommend for this?

    It would be ideal to not have to change the existing DataGrid column binding code and instead somehow intercept and inject Actions as the user edits values in cells.

    Thanks

  57. Sven says:

    Old, old thread I know…., but had Stefan published a functional undo/redo solution? I would be very interested. Or had he just a big mouth?