ImplicitStyleManager: Under the Hood

In this post I'll delve into the functional programming techniques that were used to develop ImplicitStyleManager.  If you want to know how to use ISM to add fresh new looks to your Silverlight applications take a look at this post.

ISM is a great candidate for a functional solution.  There is no unpredictable user inputs to muddy the waters which is rare for a control.  Following best practices I did my best to separate the functional task of generating a sequence of all elements to be styled from the imperative task of applying the styles to those elements.  I thought I'd share it with you because it's yet another example of how powerful and flexible functional programming can be.

Walking the Tree

The code required to generate the sequence (IEnumerable<T>) of tree nodes is actually very simple.  It traverses the logical tree and returns a flat sequence of elements, their merged dictionaries, and the style applicable to them (if found).

BaseMergedStyleDictionary initialDictionary = GetMergedStyleDictionary(element);

            // Create stream of elements and their base merged style 
            // dictionaries by traversing the logical tree.
            var elementDictionaryAndStyleTriples =
                FunctionalProgramming.Traverse(
                    // the head node
                    new { 
                        Element = element, 
                        ResourceDictionary = initialDictionary, 
                        Style = initialDictionary[element.GetType().FullName] as Style 
                    },
                    
                    // the function that accepts a node and returns all of its child nodes
                    (elementDictionaryAndStyleTriple) =>
                        from child in elementDictionaryAndStyleTriple.Element.GetLogicalChildrenDepthFirst()
                        let resourceDictionary = // create a merged resource dictionary for the current child node
                            (BaseMergedStyleDictionary) 
                            new MergedStyleResourceDictionary(
                                ImplicitStyleManager.GetExternalResourceDictionary(child) ?? child.Resources, // the resource dictionary of the current element
                                elementDictionaryAndStyleTriple.ResourceDictionary) // the resource dictionary of the parent
                        let style = resourceDictionary[child.GetType().FullName] as Style
                        select new { Element = child, ResourceDictionary = resourceDictionary, Style = style },
                    
                    // the predicate function that determines whether a node should be explored or not
                    (elementDictionaryAndStyleTriple) => 
                        recurse
                        || (ImplicitStyleManager.GetApplyMode(elementDictionaryAndStyleTriple.Element) != ImplicitStylesApplyMode.OneTime
                        || !ImplicitStyleManager.GetHasBeenStyled(elementDictionaryAndStyleTriple.Element)));

All of the work is done in one function: Traverse.  You won't believe how simple it is.  It takes an initial value (usually the head of the tree), a function which accepts a node and returns that node's children, and a predicate that determines whether to explore a node or not.

        /// <summary>
        /// Traverses a tree by accepting an initial value and a function that 
        /// retrieves the child nodes of a node.
        /// </summary>
        /// <typeparam name="T">The type of the stream.</typeparam>
        /// <param name="initialNode">The initial node.</param>
        /// <param name="getChildNodes">A function that retrieves the child
        /// nodes of a node.</param>
        /// <param name="traversePredicate">A predicate that evaluates a node
        /// and returns a value indicating whether that node and it's children
        /// should be traversed.</param>
        /// <returns>A stream of nodes.</returns>
        internal static IEnumerable<T> Traverse<T>(
            T initialNode,
            Func<T, IEnumerable<T>> getChildNodes,
            Func<T, bool> traversePredicate)
        {
            Stack<T> stack = new Stack<T>();
            stack.Push(initialNode);

            while (stack.Count > 0)
            {
                T node = stack.Pop();
                if (traversePredicate(node))
                {
                    yield return node;
                    IEnumerable<T> childNodes = getChildNodes(node);
                    foreach (T childNode in childNodes)
                    {
                        stack.Push(childNode);
                    }
                }
            }
        }

With this little function you can flatten almost any tree efficiently.   How sweet is that?  It's important to point out that although the functions that Linq provides are very powerful they are just primitives.  There are many functions like this one just waiting to be written so that Linq functions can be applied to more complex operations.

Building the Merged Dictionaries

You may have noticed that I'm not just returning the elements in the visual tree, I'm returning an anonymous struct that pairs each element with its merged resource dictionary as well as that element's applicable style, which is retrieved from its merged resource dictionary.  An element's merged dictionary is an object that has a pointer to the element's resource dictionary and its logical parent's merged dictionary.  If you attempt to look up the resource at a key in the dictionary it will first attempt to locate the key in its element's local resources and then in that of its parent.  The parent dictionary will do the same and the result is that we look up the logical tree backwards for a resource until we reach the root.

Merged dictionaries act like an immutable linked list.  Instead of physically merging dictionaries for each item (using valuable time and space) every child of a parent shares it's parent's merged dictionary but adds another node at the front - it's merged dictionary.  This is safe to do because the list is never changed.  Each child appears to have its own copy of the entire list but in reality it is sharing all previous elements with each of its siblings.  Immutable data structures and functional programming were made for each other.  You can read more about their benefits in Eric Lippert's "Immutability in C#" blog.

Filtering the Sequence

Now that we've flattened the tree we need to filter it so that we only apply styles to the elements that have an applicable style.  We also want to avoid applying styles to elements that are already styled which is not supported in Silverlight 2.  This is trivial now that we've expressed the tree traversal as a sequence.

            // filter out those elements that are already styled and those elements for which no style could be found
            var triplesThatShouldBeStyled = 
                elementDictionaryAndStyleTriples.Where(triple => triple.Element.Style == null && triple.Style != null);

Applying the Styles

Now that we've done all the hard work in the tree traversal this task is so small it barely deserves it's own section.  However I wanted to reemphasize that there is a clean separation between generating data and modifying it.

// Apply styles to elements in the sequence
            foreach (var elementToStyleAndDictionary in triplesThatShouldBeStyled)
            {
                elementToStyleAndDictionary.Element.Style = elementToStyleAndDictionary.Style;
                
                // If the element's ApplyMode is set to OneTime and it's been styled, note that to avoid restyling it
                if (ImplicitStyleManager.GetApplyMode(elementToStyleAndDictionary.Element) == ImplicitStylesApplyMode.OneTime
                    && (VisualTreeHelper.GetChildrenCount(elementToStyleAndDictionary.Element) > 0))
                {
                    ImplicitStyleManager.SetHasBeenStyled(elementToStyleAndDictionary.Element, true);
                }
            }

This code needs very little explanation.  It just applies each element's style and sets a flag to ensure that elements with their ApplyMode set to OneTime don't get traversed again later.

Why Separate Data Generation and Modification?

There are a lot of C# developers who have become accustomed to writing code in a more imperative style.  I might've written ISM with a series of foreach loops, applying styles to elements as they were retrieved.  Not only would such an approach be needlessly verbose and more complex it would be much more difficult to spread the work across multiple processors.  If you write your programs in a functional style you will be able to leverage the biggest advantage Silverlight has over its competitors in the RIA space:

Silverlight is a cross-platform version of the .NET Framework.

This fact is sometimes forgotten with all the focus on its whiz-bang vector graphics, flexible template model, and superior media codecs.  Because of the work done by the CLR team Silverlight is light-years ahead of its competitors when it comes to parallel processing.  Even the most sophisticated AJAX app can't max out your quad core.  The other major contender in the R.I.A. space can't even so much as spawn a thread.  The future is multi-core and Silverlight is ready.

To Sum Up

I think it's impressive how little code is actually required to add WPF-like implicit styling behavior to Sivlerlight.  The fact that I get to write code in a modern language like C# gives me a huge amount of job satisfaction.  I hope you guys have fun with ISM.

P.S. Some of you weisenheimers may have noticed that the code above uses both anonymous structs and query comprehensions even though I swore to avoid them on Silverlight.  As a matter of fact the actual source uses tuples and extension method calls instead.  I rewrote it to enhance the code's clarity for the purposes of this blog post.  If you're curious about my reasons for avoiding anonymous structs and query comprehensions in Siverlight check this post out.