Thursday, October 30, 2008

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.

mergeddictionary

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.

5 comments:

Judah Himango said...

Cool to see how you can apply functional programming here.

In our .NET 2 codebase, we had a similar method to your Traverse method. We called it Flatten<T> and looked like:

public IEnumerable<T> Flatten<T>(IEnumerable<T> list, ChildFetcher childFetcher)

Interesting to see others have had the same idea.

Jim McCurdy said...

Jafar,

I have noticed that when using ISM, it does not style any control that already has a Style attribute defined. For example, if I use the Style attribute on my Button's to set a common Wdith or Margin, ISM does not apply its style to those Buttons. I realize that this is because the Style attibute can only be set one-time, but can you think of a workaround to accomplish this?

Jim McCurdy

Jafar Husain said...

jim: Sorry jim but this is a tough problem and I'm afraid I don't have any easy answers for you. You can always recreate the control and re-style it. Generally speaking this is a huge pain though because you have to ensure all the events get wired up again. It is nearly impossible to do in a generic way. The good news is that Silverlight will probably grow out of this in the future.

Jesse Chisholm said...

Instead of changing the "Style" of the control, how about changing the contents of the MergedDictionary so the "Style" is changed?

If, for example, your MergedDictionary contains a child Dictionary that defined everything you wanted for the Style "FancyButton", then deleting that child Dictionary and adding a new child with the same name ("FancyButton"), but different details; this should automagically change the style of every Button using the style "FancyButton". Without having to change any connections on the Button itself.

I should have said insert the new child before the old child then delete the old child. Wouldn't want to risk things reverting to system default during the transition. :)

-Jesse

Anonymous said...
This comment has been removed by a blog administrator.

About Me

My Photo
I'm a software developer who started programming at age 16 and never saw any reason to stop. I'm working on the Presentation Platform Controls team at Microsoft. My primary interests are functional programming, and Rich Internet Applications.