June, 2009

  • Kirill Osenkov

    New CodePlex project: a simple Undo/Redo framework

    • 57 Comments

    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

  • Kirill Osenkov

    Visual Studio 2010 Beta1 + TFS + HTTPS (TF31001): The ServicePointManager does not support proxies with the https scheme.

    • 1 Comments

    This is just a little note to myself and others who might run into this. I was using Visual Studio 2010 and Team Foundation Client to access a CodePlex project over HTTPS (port 443), and got this error message:

    ---------------------------
    Microsoft Visual Studio
    ---------------------------
    Microsoft Visual Studio

    TF31001: Cannot connect to Team Foundation Server at tfs07.codeplex.com. The server returned the following error: The ServicePointManager does not support proxies with the https scheme.
    ---------------------------
    OK   Help  
    ---------------------------

    By the way, did you know that you can press Ctrl+C to copy the contents of a message box dialog to clipboard? (Well, at least in Visual Studio message boxes).

    Anyway, it turns out this is a known bug: https://connect.microsoft.com/VisualStudio/feedback/Workaround.aspx?FeedbackID=453677

    The workaround so far is to create a couple of string values in the registry:

    This problem it seams is to do with the way Visual Studio 2010 connects to your TFS server over HTTPS. The default value for “BypassProxyOnLocal” in Visual Studio 2008 was “False”, but it has been changed to “True” for Visual Studio 2010 Beta 1.

    You can fix this by adding the following registry keys and restarting Visual Studio 2010:

    You need to add a “RequestSettings” key to both of the following location that contains a string value pair of “BypassProxyOnLocal=’False’”.

    32bit OS Key Locations:
    HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\TeamFoundationServer\10.0\RequestSettings
    HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\VisualStudio\10.0\TeamFoundation\RequestSettings

    64bit key locations:
    HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\TeamFoundationServer\10.0\RequestSettings
    HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\VisualStudio\10.0\TeamFoundation\RequestSettings

    How to: Change the BypassProxyOnLocal Configuration: http://msdn.microsoft.com/en-us/library/bb909716(loband).aspx

    Update: I just noticed Aaron Block has also blogged about this.

  • Kirill Osenkov

    VS Project, C++ and Editor team blogs

    • 0 Comments

    This is just a quick announcement about some Visual Studio team blogs that might be really worth checking out.

  • Kirill Osenkov

    Algorithms in C#: shortest path around a polygon (polyline routing)

    • 14 Comments

    Suppose you have to build a road to connect two cities on different sides of a lake. How would you plan the road to make it as short as possible?

    To simplify the problem statement, a lake is sufficiently well modeled by a polygon, and the cities are just two points. The polygon does not have self-intersections and the endpoints are both outside the polygon. If you have Silverlight installed, you can use drag and drop on the points below to experiment:

    Get Microsoft Silverlight

    Solution description

    A shortest path between two points is a segment that connects them. It’s clear that our route consists of segments (if a part of the path was a curve other than a segment, we could straighten it and get better results). Moreover, those segments (which are part of the route) have their endpoints either on polygon vertices or the start or end point. Again, if this were not the case, we would be able to make the path shorter by routing via the nearest polygon vertex.

    Armed with this knowledge, let’s consider all possible segments that connect the start and end point and all polygon vertices that don’t intersect the polygon. Let’s then construct a graph out of these segments. Now we can use Dijkstra’s algorithm (or any other path finding algorithm such as A*) to find the shortest route in the graph between start and endpoints. Note how any shortest path algorithm can essentially boil down to a path finding in a graph, because a graph is a very good representation for a lot of situations.

    From the implementation perspective, I used my dynamic geometry library and Silverlight to create a simple demo project that lets you drag the start and end points as well as polygon vertices. You can also drag the polygon and the plane itself. I also added rounded corners to the resulting path and made it avoid polygon vertices to make it look better.

    Here is the source code for the sample. Here’s the main algorithm. It defines a data structure to describe a Graph that provides the ShortestPath method, which is the actual implementation of the Dijkstra’s algorithm. ConstructGraph takes care of adding all possible edges to the graph that do not intersect our polygon. SegmentIntersectsPolygon also determines what the name suggests.

    I hope to post more about polygon routing in the future and do let me know if you have any questions.

  • Kirill Osenkov

    yield return and Continuation-Passing Style

    • 5 Comments

    Someone was recently porting some C# code to VB and had a question about how to convert the C# yield return iterator methods to VB (VB currently doesn’t support iterators).

    There were a lot of replies like “use Reflector on a compiled binary and copy-paste the generated state machine code”. The problem with the Reflector approach is that you go one step down the abstraction ladder and lose the high-level intent expressed in the original code. Resulting code will be surely harder to read and maintain.

    Surprisingly, no one mentioned CPS. But before applying continuation-passing style, let’s first look at the nature of yield return. It’s essentially a producer-consumer model where the producer is a state machine where transitions are triggered by the MoveNext calls and current state is saved in the Current property. On the consumer side there is eventually almost always a foreach loop with some logic in the body, and this logic only requests the next element (and triggers a state machine transition) after it’s done processing the current element.

    It turns out, we can preserve the algorithm encoded in the iterator and avoid using yield return and thus having the compiler to generate the state machine code for us. To achieve this, we pass the logic that used to be in the consumer foreach loop (a continuation) directly into the iterator.

    Here’s an example with yield return that we want to convert:

    using System;
    using System.Collections.Generic;
    
    class Node<T>
    {
        public Node<T> Left { get; set; }
        public T Value { get; set; }
        public Node<T> Right { get; set; }
    
        public IEnumerable<T> Traverse()
        {
            if (Left != null)
            {
                foreach (var item in Left.Traverse())
                {
                    yield return item;
                }
            }
            yield return Value;
            if (Right != null)
            {
                foreach (var item in Right.Traverse())
                {
                    yield return item;
                }
            }
        }
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            Node<int> tree = new Node<int>()
            {
                Left = new Node<int>()
                {
                    Value = 1,
                    Right = new Node<int>()
                    {
                        Value = 2
                    }
                },
                Value = 3,
                Right = new Node<int>()
                {
                    Value = 4
                }
            };
    
            foreach (var item in tree.Traverse())
            {
                Console.WriteLine(item);
            }
        }
    }

    Now, the trick is to pass the “continuation”, which is the code that processes the results, directly into the iterator method (using first-class functions AKA delegates):

    public IEnumerable<T> Traverse()
    {
        List<T> result = new List<T>();
        TraverseInner(this, result.Add);
        return result;
    }
    
    void TraverseInner(Node<T> root, Action<T> collector)
    {
        if (root == null) return;
        TraverseInner(root.Left, collector);
        collector(root.Value);
        TraverseInner(root.Right, collector);
    }

    Note how we created an internal helper that actually does the traversing and how the logic of the traversal is even shorter than in the original method. We don’t use yield return and still maintain a high level of abstraction. Where was yield return, now is a call to the helper method. Otherwise, the control flow is the same.

    The downside of this approach though is that we lose laziness, which means, that once requested, we eagerly calculate all the results and return them at once. This is the price that we pay for losing the state machine that can store intermediate results for us.

    If we remove the limitation of having to return IEnumerable<T>, we can directly consume the helper method without having to write a foreach loop:

    TraverseInner(tree, Console.WriteLine);

    Here we’re passing the “continuation” (which is the Console.WriteLine method) directly inside the iterator. Note how the consumer side became shorter as well because we don’t have to write a foreach loop.

    Note: a while ago I blogged about yield foreach which would allow to get rid of foreach statements in the iterator scenario as well.

    Note 2: I’m guessing it’s possible to get rid of yield return and still keep the laziness, I just need to do more homework on Push LINQ and similar to find a nice solution to this.

Page 1 of 1 (5 items)