Selecting Denormalized Child Nodes and Parents From Tree with Linq

August 5th, 2009

Problem: You have a collection of objects.  Each object has a number of children.  You want all the children matching a criteria, AND the parent.  The child does not reference the parent.

Solution: You can use Linq to

  1. From the context of all the parents, select all the children with the “SelectMany” method.
  2. Construct and select instances of an anonymous type combining the parent and child.  (You can do this because the context is that of the parent.)
  3. Apply your filtering criteria.

Example: Select the five most recently modified children (and parent)

class Program
{
    static void Main()
    {
        var allParents = new StupidFactory().ConstructParents(100);

        var fiveMostRecentChildrenAndParent = allParents
            .SelectMany(parent => parent.Children)
            .Select(child => new { Child = child, Parent = allParents.Where(parent => parent.Children.Contains(child)).Single() })
            .OrderByDescending(anonymousCombo => anonymousCombo.Child.LastModified)
            .Take(5);

        foreach (var childAndParent in fiveMostRecentChildrenAndParent)
        {
            Console.WriteLine("{0} modified on {1} (belongs to {2})", childAndParent.Child.Name, childAndParent.Child.LastModified.ToShortDateString(), childAndParent.Parent.Name);
        }
    }
}

public abstract class Entity
{
    public string Name;
}

public class Parent : Entity
{
    public List<Child> Children = new List<Child>();
}

public class Child : Entity
{
    public DateTime LastModified;
}

public class StupidFactory
{
    private readonly Random _random = new Random();
    private int _childCount;
    private int _parentCount;

    private Child ConstructChild()
    {
        return new Child { Name = "Child_" + _childCount++, LastModified = DateTime.Now.AddDays(-_random.Next(0, 365)) };
    }

    private Parent ConstructParent()
    {
        var result = new Parent { Name = "Parent_" + _parentCount++ };
        var childCount = _random.Next(0, 11);
        for (var i = 0; i < childCount; i++)
        {
            result.Children.Add(ConstructChild());
        }
        return result;
    }

    public IList<Parent> ConstructParents(int count)
    {
        var result = new List<Parent>();
        for (var i = 0; i < count; i++)
        {
            result.Add(ConstructParent());
        }
        return result;
    }
}

John McDowall

Caching the Result of Arbitrary Function Calls

August 5th, 2009

Here is the approach I took to performing the result of a method call, which is done in a reusable way which may be interesting.

Instead of calling my method normally like this:

var service = new MyService();
var time = service.GetTime();

I wrap that call in a call to the cache:

var service = new MyService();
var time = cache.Get(x => x.GetTime(), service, tenSeconds);

Inside the Cache implementation I have a method Get, which wraps up the method call in a wrapping function, then passes this parcel to the InvokeOrGetFromCache method:

There is a variant of “Get” for every variant of Func<>.

The InvokeOrGetFromCache is the meat of the cache class.  It controls access two the actual store of objects (a dictionary of function to result), and a collection of pending functions (a hashset).

When requesting a result for a function from the cache, the pending set is first checked.  If the job is already pending, the requesting thread yields until the job is done.

When a function’s result is not present in the cache, it is added to the pending functions set.  The function is invoked, its result is added to the cache, then the function is removed from the pending set.

NB As you can see, the key to the cache is just the function itself – this means that calls with different instances/values will result in the same result.  This is fine for my purposes, but may not be OK for you.  In this case it would be fairly straightforward to build a new key which incorporated the values as well as the function itself.

John McDowall

public class Cache
{
    private readonly IDictionary<object, CachedItem> _registry = new Dictionary<object, CachedItem>();
    private readonly ICollection<object> _pending = new HashSet<object>();

    public TResult Get<T, TResult>(Func<T, TResult> func, T t, TimeSpan maximumAge)
    {
        return InvokeOrGetFromCache(func, maximumAge, () => func.Invoke(t));
    }

    public TResult Get<T1, T2, TResult>(Func<T1, T2, TResult> func, T1 t1, T2 t2, TimeSpan maximumAge)
    {
        return InvokeOrGetFromCache(func, maximumAge, () => func.Invoke(t1, t2));
    }

    public TResult Get<T1, T2, T3, TResult>(Func<T1, T2, T3, TResult> func, T1 t1, T2 t2, T3 t3, TimeSpan maximumAge)
    {
        return InvokeOrGetFromCache(func, maximumAge, () => func.Invoke(t1, t2, t3));
    }

    public TResult Get<T1, T2, T3, T4, TResult>(Func<T1, T2, T3, T4, TResult> func, T1 t1, T2 t2, T3 t3, T4 t4, TimeSpan maximumAge)
    {
        return InvokeOrGetFromCache(func, maximumAge, () => func.Invoke(t1, t2, t3, t4));
    }

    private TResult InvokeOrGetFromCache<TResult>(object cacheKey, TimeSpan maximumAge, Func<TResult> wrapperFunc)
    {
        var now = DateTime.Now;

        WaitForPendingInvokeToComplete(cacheKey);

        lock(_registry)
        {
            if (_registry.ContainsKey(cacheKey))
            {
                var result = _registry[cacheKey];
                if (result.TimeOfConstruction.Add(maximumAge) > now)
                {
                    return (TResult) result.Value;
                }
            }
        }

        return Invoke(cacheKey, now, wrapperFunc);
    }

    private TResult Invoke<TResult>(object cacheKey, DateTime now, Func<TResult> wrapperFunc)
    {
        _pending.Add(cacheKey);
        var value = wrapperFunc.Invoke();
        _registry[cacheKey] = new CachedItem(now, value);
        _pending.Remove(cacheKey);
        return value;
    }

    private void WaitForPendingInvokeToComplete(object cacheKey)
    {
        while (_pending.Contains(cacheKey))
        {
            Thread.Sleep(0);
        }
    }

    private class CachedItem
    {
        public CachedItem(DateTime timeOfConstruction, object value)
        {
            TimeOfConstruction = timeOfConstruction;
            Value = value;
        }

        public DateTime TimeOfConstruction { get; private set; }
        public object Value { get; private set; }
    }
}

Using Expression Trees to Avoid String Literal References

July 27th, 2009

Often a developer will want to mirror the names of properties or methods of a class in some related dynamic resource that needs to bind to named members of the class.  This happens a lot in user interface and serialization scenarios.

For example, a user interface may need to populate the value of a text-box with a value dynamically looked up from a property on an instance of a class.  Typically, this is done with a hard-coded string literal.

To avoid using hard-coded member names, expression trees can be used to define members, then utility code can translate that tree to a string.  The advantage here is that refactoring is pretty much guaranteed to work, and you get compile time checking.

So, lets say I have the following class, and I am interested in writing the the names of the members to the console.

class MyType
{
    public string AStringProperty { get; set; } 

    public object GetAnObject()
    {
        return new object();
    }

    public int GetAnInt(string a1, string a2)
    {
        return 0;
    }
}

With a small amount of utility code, I can achieve my goal without string literals or resorting to reflection.

Console.WriteLine(Name.Of<MyType>(x => x.AStringProperty));
Console.WriteLine(Name.Of<MyType>(x => x.GetAnObject()));
Console.WriteLine(Name.Of<MyType>(x => x.GetAnInt(null, null)));

Which results in console output:

AStringProperty

GetAnObject

GetAnInt

Utility Code

The “Name” class has a single static method “Of”, which uses another the "”ExpressionFinder” class to work out the member or method.

class Name
{
    public static string Of<T>(Expression<Func<T, object>> expr)
    {
        return ExpressionMemberFinder.FindMemberOrNull(expr).Name;
    }
}

class ExpressionMemberFinder
{
    public static MemberInfo FindMemberOrNull(Expression expression)
    {
        switch (expression.NodeType)
        {
            case ExpressionType.Convert:
                return FindMemberOrNull(((UnaryExpression)expression).Operand);
            case ExpressionType.Lambda:
                return FindMemberOrNull(((LambdaExpression)expression).Body);
            case ExpressionType.Call:
                return ((MethodCallExpression)expression).Method;
            case ExpressionType.MemberAccess:
                return ((MemberExpression)expression).Member;
            default:
                return null;
        }
    }
}

It’s worth noting that the only type of expression tree we can work on is one that ends in a single method-call or member-access.  It doesn’t make any sense to work on a tree with branches or multiple leaf nodes.

Lets examine what happens in the FindMemberOrNull method by looking at three kinds of tree that we can handle.

Behaviour #1, Finding a Property Access

Name.Of<MyType>(x => x.AStringProperty));
  1. FindMemberOrNull is called with a lambda {x => x.AStringProperty}
  2. FindMemberOrNull is called from within itself with the lambda’s body, a member-expression {x => x.AStringProperty}
  3. The member-expression’s member is returned

Behaviour #2, Finding a Method That Returns an Object

Name.Of<MyType>(x => x.GetAnObject()));
  1. FindMemberOrNull is called with a lambda {x => x.GetAnObject() }
  2. FindMemberOrNull is called from within itself with the lambda’s body, a method-call-expression {x => x.GetAnObject()}
  3. The method-call-expression’s method is returned

Behaviour #3, Finding a Method That Returns an Something Other Than an Object

Name.Of<MyType>(x.GetAnInt(null, null)));

Slightly more interesting behaviour here.  As the FindMemberOrNull method accepts a expression describing a function that returns System.Object, the compiler automatically wraps the expression in a unary-expression which converts from Expression<Func<MyType, int>> to Expression<Func<MyType, object>>.  NICE!

  1. FindMemberOrNull is called with a lambda {x => Convert(x.GetAnInt(null, null))}
  2. FindMemberOrNull is called from within itself with the lambda’s body, a unary-expression {x =>Convert(x.GetAnInt(null, null))}
  3. FindMemberOrNull is called from within itself with the unary-expression’s operand, a method-call-expression {x => x.GetAnInt(null, null)}
  4. The method-call-expression’s method is returned

John McDowall

Death to Object Initializers

May 11th, 2009

Recap: Object initializers were introduced in C# version 3, they allow the client of a class to construct an instance of that class and initialize properties in one step.

The code

    var person = new Person { Name = new Name { First = "John", Second = "McDowall" }, Employer = "Storm ID" };

is equivalent to

    var name = new Name();

    name.First = "John";

    name.Second = "McDowall";

    var person = new Person();

    person.Name = name;

    person.Employer = "Storm ID";

 

The object initializer cuts down the amount of code I have to write to create an instance of the Person class, which is good.

The problem here is that I have no idea which properties of the Person or Name class need to be present for my object to be valid and useful.  The only constraint that is enforced is that the default constructor is called.

Now consider the situation where I add a property to an existing class.  I’d like to update the places where this class is instantiated, but because object initializers are used "to make things easier", I have to pore through each one, making sure my new property is set.

Object initializers make it easy for programmers to write a class, not bothering to validate its state, but the real work is pushed onto the clients of that class.  And that work is duplicated wherever the initializer is used.

The real solution is to write proper class constructors.  The constructor provides the contract.  The contract can be re-factored when adding properties.  The contract gives you confidence that after the constructor has been invoked the object is valid and ready for use.

A constructor call will be *less* verbose than an object initializer call.

So, down with this:

    var person = new Person { Name = new Name { First = "John", Second = "McDowall" }, Employer = "Storm ID" };

and up with this:

    var name = new Name("John", "McDowall");

    var person = new Person(name, "Storm ID");

 

Object initializers definitely have a place, for instance initializing dictionaries in test code or struct type classes, but they are harmful when constructing domain classes.

 

John McDowall

Automatic Model Validation with ASP.NET MVC, xVal, Castle and a Custom Binder

May 11th, 2009

There are several stages at which you can, and possibly should, validate data inputted to your application.  This post deals with server-side validation of user input before it reaches the controller.  It’s arguably not the controller’s responsibility to validate user input, and it’s nice to have a clean controller that can focus on it’s responsibility.  In this solution we tap into the ASP.NET MVC Model Binder framework so our controllers can count on the model having been validated before any of the action methods are called.

xVal is a nice validation framework written by Steve Sanderson.  It can work with a bunch of server-side and client-side validation products.  I this case I’m going to use the server-side Castle Validator (just because I like it).

Once you have downloaded and referenced xVal and Castle Validator, you can decorate your model properties with attributes like so:

 

using System;

using Castle.Components.Validator;

 

namespace Wow.MvcApplication.Models

{

    public class Person

    {

        [ValidateNonEmpty]

        public string FirstName { get; set; }

 

        public string MiddleName { get; set; }

 

        [ValidateNonEmpty]

        public string LastName { get; set; }

 

        [ValidateDate]

        public DateTime Dob { get; set; }

    }

}

 

Now we implement the validation runner that wraps up the Castle runner and returns validation data in xVal form:

 

using System.Collections.Generic;

using System.Linq;

using Castle.Components.Validator;

using xVal.ServerSide;

 

namespace SomeMvcApplication

{

    public class CastleValidationRunner

    {

        private static readonly CachedValidationRegistry registry = new CachedValidationRegistry();

 

        public static IList<ErrorInfo> GetErrors(object instance)

        {

            var result = new List<ErrorInfo>();

            var runner = new ValidatorRunner(registry);

            if (instance != null && !runner.IsValid(instance))

            {

                var errorSummary = runner.GetErrorSummary(instance);

                var errorInfos = errorSummary.InvalidProperties.SelectMany(

                    prop => errorSummary.GetErrorsForProperty(prop),

                    (prop, err) => new ErrorInfo(prop, err));

                result.AddRange(errorInfos);

            }

            return result;

        }

    }

}

 

Create a Model Binder that uses the new validation runner to populate ModelState:

 

using System.Web.Mvc;

 

namespace SomeMvcApplication

{

    public class ValidatingModelBinder : DefaultModelBinder

    {

        public override object BindModel(ControllerContext controllerContext, ModelBindingContext bindingContext)

        {

            var model = base.BindModel(controllerContext, bindingContext);

            var errors = CastleValidationRunner.GetErrors(model);

            foreach (var error in errors)

            {

                var propertyName = error.PropertyName;

                var name = bindingContext.ModelName + "." + propertyName;

                bindingContext.ModelState.AddModelError(name, error.ErrorMessage);

            }

            return model;

        }

    }

}

 

Now hook up our new Model Binder in Global.ascx.cs:

 

protected void Application_Start()

{       

    ModelBinders.Binders.DefaultBinder = new ValidatingModelBinder();

}

 

And we are done.  Controllers can now count on validated models like so:

 

[AcceptVerbs(HttpVerbs.Post)]

public ActionResult Edit(Person model)

{

    if (!ModelState.IsValid)

    {

        return View(model);

    }

    // In real life, map the model to domain, then save

}

 

John McDowall

I Don’t Like Paging

May 11th, 2009

The problem of how to display arbitrary sized data on a fixed sized view was solved many years ago with the invention of scrolling viewports and scrollbars.

The advent of the web brought new challenges. All the data for a web page had to be delivered to the user in one chunk.  You want to see some more data?  Then make another page request.  This lead to the development of the concept of paging.

Everybody knows and tolerates paging, maybe even without noticing it.  It’s an ugly way to navigate lists, without any nice way to quickly look at two items that are far apart.

Surely paging is just a kluge to get round the limitations of early web browsers, and with the arrival of smarter clients and more powerful tools (e.g. Ajax), we could do away with paging in non-legacy systems.

paging 

Down with this sort of thing!

You keep the concept of paging, but you hide it from your end user.  When the user indicates a need to see more data than is on the screen you use Ajax to append a new "page" of data to the existing view.  The user can signal that they need more data either implicitly through scrolling, or explicitly (e.g. through a click of a button or link).

If you end up showing the user a set of data that is too big to manage, then you need to provide better tools to filter that data.

Simple Example

An initial search shows a list of results.  Instead of a list of page numbers, you get a link to append more results:

initial

Loading more just appends to the original list:

secondary

Which, in my opinion, is a nicer user experience nicer than flicking through whole page refreshes.

You can have a play with the demo here: http://nopagingdemo.demo.stormid.com/ 

NB this demo deliberately has a simulated back end written in JavaScript, so interested parties can view the whole source easily.  The whole source is in the index.html file, apart from the JQuery library.

John McDowall

Sync’ed Enumeration

June 28th, 2008

This afternoon I was writing a test; I had two IEnumerables that I wanted to examine together, so I encapsulated the enumerable synchronization to another class leaving the test nice and light:

[Test]
public void the_results_refer_to_the_correct_objects()
{
    var relationship = new SyncedEnumerable<FileSystemItem, LoadResult>(_directory.FilesContained, _result);

    foreach (var item in relationship)
    {
        Assert.AreSame(item.FirstValue, item.SecondValue.FileSystemItem,
            "Expected result item {0} to match filesystem", item.Index);
    }
}

Basically I wrap two enumerators in another generic one using composition. Maybe this code would be useful to others; here it is:

public class SyncedEnumerable<T1, T2> : IEnumerable<SyncedEnumerable<T1, T2>.Item>
{
    private readonly IEnumerable<T1> _firstEnumerable;
    private readonly IEnumerable<T2> _secondEnumerable;

    public SyncedEnumerable(IEnumerable<T1> firstEnumerable, IEnumerable<T2> secondEnumerable)
    {
        _firstEnumerable = firstEnumerable;
        _secondEnumerable = secondEnumerable;
    }

    private class SyncedEnumerator : IEnumerator<Item>
    {
        private int _index;
        private readonly IEnumerator<T1> _firstEnumerator;
        private readonly IEnumerator<T2> _secondEnumerator;

        public SyncedEnumerator(IEnumerable<T1> firstEnumerable, IEnumerable<T2> secondEnumerable)
        {
            _index = 0;
            _firstEnumerator = firstEnumerable.GetEnumerator();
            _secondEnumerator = secondEnumerable.GetEnumerator();
        }

        public void Dispose()
        {
            _firstEnumerator.Dispose();
        }

        public bool MoveNext()
        {
            var firstResult = _firstEnumerator.MoveNext();
            var secondResult = _secondEnumerator.MoveNext();

            if (firstResult != secondResult)
            {
                if (firstResult)
                {
                    throw new ArgumentException("First enumerable yields more items than the second.");
                }
                throw new ArgumentException("Second enumerable yields more items than the first.");
            }

            if (firstResult)
            {
                _index++;
            }

            return firstResult;
        }

        public void Reset()
        {
            _index = 0;
            _firstEnumerator.Reset();
            _secondEnumerator.Reset();
        }

        public Item Current
        {
            get { return new Item(_index, _firstEnumerator.Current, _secondEnumerator.Current); }
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }
    }

    public IEnumerator<Item> GetEnumerator()
    {
        return new SyncedEnumerator(_firstEnumerable, _secondEnumerable);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public class Item
    {
        private readonly int _index;
        private readonly T1 _firstValue;
        private readonly T2 _secondValue;

        public Item(int index, T1 firstItem, T2 secondItem)
        {
            _index = index;
            _firstValue = firstItem;
            _secondValue = secondItem;
        }

        public int Index
        {
            get { return _index; }
        }

        public T2 SecondValue
        {
            get { return _secondValue; }
        }

        public T1 FirstValue
        {
            get { return _firstValue; }
        }
    }
}

Consistent UI Controls

June 18th, 2008

Window Controls

Yeah, nice one.  All windows are Microsoft products, except the bottommost.

Why bother trying to fit in with existing stuff?  Just ignore it and write any old rubbish you feel like.

“yield” gotcha

May 20th, 2008

I am a big fan of the yield keyword in C#, but you have to keep in mind that using it will return an anonymous method that is executed every time you enumerate your IEnumerable<>.  This is very elegant, and the late execution has advantages, but it can trick you.  I found some code this morning that was running very slow.  It went a little like this:

static void Main(string[] args)
{
    IEnumerable<string> strings = GetOneHundredStrings();
    for (int i = 0; i < 100; i++)
    {
        foreach (string s in strings)
        {
            // something
        }
    }
}

private static IEnumerable<string> GetOneHundredStrings()
{
    for (int i = 0; i < 100; i++)
    {
        yield return i.ToString();
    }
}

The thing to note here is that every time “foreach (string s in strings)” is executed, the anonymous method that creates the IEnumerable<string> is executed - meaning way more iterations than required, so replace the”GetOneHundredStrings” method with something that returns an actual collection:

private static IEnumerable<string> GetOneHundredStrings()
{
    IList<string> result  = new List<string>();
    for (int i = 0; i < 100; i++)
    {
        result.Add(i.ToString());
    }
    return result;
}

Invoking an operator via reflection

April 5th, 2008

Given a class with a conversion operator like so:

public class Colour
{
public static implicit operator Colour(string colourName)
{
return new Colour();
}
}

You can invoke via reflection like so:

typeof(Colour).GetMethod(”op_Implicit”).Invoke(null, new[]{”Black”})