Cet article est disponible en Français.
The Traverse extension method in C#
Occasionally, you'll come across data structures that take the form of single linked lists, like for instance the MethodInfo class and its GetBaseDefinition method.
Let's say for a virtual method you want, for a specific type, discover which overriden method in the hierarchy is marked with a specific attribute.
I assume in this example that the expected attribute is not inheritable.
You could implement it like this :
private static MethodInfo GetTaggedMethod(MethodInfo info)
{
MethodInfo ret = null;
do
{
var attr = info.GetCustomAttributes(typeof(MyAttribute), false) as MyAttribute[];
if (attr.Length != 0)
return info;
ret = info;
info = info.GetBaseDefinition();
}
while (ret != info);
return null;
}
This method has two states variables and a loop, which makes it a bit harder to stabilize. This is a method that could easily be expressed as a LINQ query, but (as far as I know) there is no way to make a enumeration of a data structure which is part of a linked list.
To be able to do this, which is "traverse" a list of objects of the same type that are linked from one to the next, an extension method containing a generic iterator can be written like this :
public static class Extensions
{
public static IEnumerable<T> Traverse<T>(this T source, Func<T, T> next)
{
while (source != null)
{
yield return source;
source = next(source);
}
}
}
This is a really simple iterator method, which calls a method to get the next element using the current element and stops if the next value is null.
It can be used easily like this, using the GetBaseDefinition example :
var methodInfo = typeof(Dummy).GetMethod("Foo");
IEnumerable<MethodInfo> methods = methodInfo.Traverse(m => m != m.GetBaseDefinition() ? m.GetBaseDefinition() : null);
Just to be precise, the lambda is not exactly perfect, as it is calling GetBaseDefinition twice. It can definitely be optimised a bit.
Anyway, to go back at the first example, the GetTaggedMethod function can be written as a single LINQ query, using the Traverse extension :
private static MethodInfo GetTaggedMethod(MethodInfo info)
{
var methods = from m in methodInfo.Traverse(m => m != m.GetBaseDefinition() ? m.GetBaseDefinition() : null)
let attributes = m.GetCustomAttributes(typeof(MyAttribute), false)
where attributes.Length != 0
select m;
return methods.FirstOrDefault();
}
I, for one, find this code more readable... But this is a question of taste :)
Nonetheless, the MethodInfo linked-list is not the perfect example, because the end of the chain is not a null reference but rather the same method we're testing. Most of the time, a chain will end with a null, which is why the Traverse method uses null to end the enumeration. I've been using this method to perform queries on a hierarchy of objects that have parent objects of the same type, and the parent's root set to null. It has proven to be quite useful and concise when used in a LINQ query.
An F# Detour
As I was here, I also tried to find out what an F# version of this code would be. So, with the help of recursive functions, I came up with this :
let rec traverse(m, n) =
let next = n(m)
if next = null then
[m]
else
[m] @ traverse(next, n)
The interesting part here is that F# does not require to specify any type. "m" is actually an object, and "n" a (obj -> obj) function, but returns a list of objects. And it's used like this :
let testMethod = typeof<Dummy>.GetMethod("Foo")
for m in traverse(testMethod, fun x -> if x = x.GetBaseDefinition() then null else x.GetBaseDefinition()) do
Printf.printfn "%s.%s" m.DeclaringType.Name m.Name
Actually, the F# traverse method is not exactly like the C# traverse method, because it is not an extension method, and it is not lazily evaluated. It is also a bit more verbose, mainly because I did not find an equivalent of the ternary operator "?:".
After digging a bit in the F# language spec, I found out it exists an somehow equivalent to the yield keyword. It is used like this :
let rec traverse(m, n) =
seq {
let next = n(m)
if next = null then
yield m
else
yield m
yield! traverse(next, n)
}
It is used the same way, but the return value is not a list anymore but a sequence.
I also find interesting that F# is able to return tuples out of the box, and for my attribute lookup, I'd have the method and I'll also have the attribute instance that has been found. Umbrella also defines tuples useable from C#, but it's an addon.
F# is getting more and more interesting as I dig into its features and capabilities...