Using topological sort to order rules in rules engines

In this post Ruby-on-Rails, convention over configuration world that we live in, its a natty technique to write a rules engine to help keep your code decoupled and easy to work with.

A typical example might be a global exception handling system. Suppose we want to return a message instead of a YSOD when Application_Error fires. Suppose we have the following code:

public interface IExceptionHandler

{

    bool HandleException(HttpContextBase httpContext, Exception ex);

}

class LogErrorExceptionHandler : IExceptionHandler

{

    public bool HandleException(HttpContextBase httpContext, Exception ex)

    {

        //log the exception somehow!  

        return false;

    }

}

class UnknownExceptionHandler : IExceptionHandler

{

    public bool HandleException(HttpContextBase httpContext, Exception ex)

    {

        httpContext.Response.Clear();

        httpContext.Response.Status = "500";

        httpContext.Response.TrySkipIisCustomErrors = true;

        httpContext.Response.Write("There was an error :(");

        return true;            

    }

}

In our global.asax we have something like so:

protected void Application_Error()

{

    Exception unhandledException = Server.GetLastError().GetBaseException();

    IEnumerable<IExceptionHandler> handlers = SL.Current.GetAll<IExceptionHandler>();

    foreach (var exceptionHandler in handlers)

    {

        if (exceptionHandler.HandleException(new HttpContextWrapper(HttpContext.Current), unhandledException))

        {

            break;

        }

    }

}

As you can see, we loop through all the IExceptionHandlers in a chain of responsibility, resolved from our IOC container. If one of them handles the error, we stop. Another example of an exception handler might be one that looked at the exception type, and, if it is a ValidationException, it returns a summary of the validation errors that occurred. Remember though, this is just an example, and you can use a rules engine like this for just about anything (determining discounts or picking notification services or running NHibernate automapping rules)

This is all fine and dandy, but there is a flaw. What order are the handlers going to be executed in? If the logging handler or the validation handler are after the UnknownExceptionHandler, they wont be executed! We need to instill some order in our rules.

Suppose we now create a marker interface IRunAfter<T> and mark up our UnknownExceptionHandler like so:

class UnknownExceptionHandler : IExceptionHandler, IRunAfter<LogErrorExceptionHandler>

{

    ...

}

By marking up our classes with the IRunAfter class, we can add ordering to our handlers. We need a function to sort them. This type of sort is called a topological sort – essentially turning the IEnumerable into a graph. I did a little hacking on Patrick Dewane’s sort function, and came up with TopologicalSort.cs. The function has this signature:

public delegate IEnumerable<T> GetDependentTypes<T>(T item, IEnumerable<T> potentialDependencies);

public static IEnumerable<T> PerformTopoSort<T>(IEnumerable<T> items, GetDependentTypes<T> getDependentTypes) { ... }

Now, when we resolve our enumerable of IExceptionHandlers, we can call the sort function and get our handlers into the right order.

TopologicalSort.GetDependentTypes<Type> getDependentTypes =

    (t, potentialTypes) => potentialTypes.Where(pt => typeof(IRunAfter<>).MakeGenericType(t).IsAssignableFrom(pt));

var handlers = TopologicalSort.PerformTopoSort(SL.Current.GetAll<IExceptionHandler>(), getDependentTypes);

Of course, you can define your own rules for determining getDependentTypes instead of IRunAfter. You can even have it determine the rules at runtime, just by using a different implementation of getDependentTypes. Now that the rules are sorted, we can use them. Good times!