Grax Coding

Tuesday, July 29, 2014

Detecting infinite recursion

TLDR: Use ThreadStatic static variables for a performant recursion test.

As I was building fFastInjector, I found that it was fairly easy to create infinitely recursive configurations of the dependency injection.  As fFastInjector examines a constructor to determine what to inject, it calls itself to resolve those injections.

Injector.Resolve<MyConcreteClass>()
can generate a resolution function that looks like
new MyConcreteClass(Injector.Resolve<IMyService>(), Injector.Resolve<IMySecurity>())

A mis-configuration could cause an infinite loop if one of those resolutions pointed back to MyConcreteClass.  In order to detect this, I looked at a few options to determine if I was calling the Resolve method for a type that I was already in the middle of resolving.

First, I tried looking at caller information as shown at http://msdn.microsoft.com/en-us/library/hh534540.aspx.  I rejected that fairly quickly because I questioned how well it would perform and because I could lose track of the loop if the resolve method called another method that called another resolve method.   It was going to be very difficult to determine if I was calling the Resolve method that was in the middle of Resolving and basically involved reviewing the whole stack of calls.

I could set a static variable and then if it is already set when I enter the resolution function, I can throw the exception.

static bool isRecursionTestPending;

static T ResolveWithRecursionCheck()
{
 if (isRecursionTestPending)
 {
  throw new Exception("Recursion detected in type " + typeofT.Name);
 }
 isRecursionTestPending = true;
 
 var returnValue = ActiveResolverFunction.Invoke();
 
 isRecursionTestPending = false;
 
 return returnValue;
}

The problem with this is that if 2 Resolvers are called at the same time, the 2nd one will fail thinking we have a recursion error because the first one set the isRecursionTestPending variable.

The answer I found is similar to the above with one very important change.  As Philip Cox points out on his blog post, we can use a ThreadStatic variable to detect this recursion in a thread-safe way.

[ThreadStatic]
static bool isRecursionTestPending;

A thread static variable is a different variable on each of the threads it runs on.  So if Thread 1 starts to resolve MyConcreteClass, it will set the isRecursionTestPending variable to true for Thread 1.  If, in the course of executing the Resolve method, another call to Resolve<MyConcreteClass>() is discovered, the isRecursionTestPending variable will be true and an exception will be thrown.  If Thread 2 calls Resolve<MyConcreteClass>(), Thread 2 will have its own independent isRecursionTestPending variable.

In my case, this kind of recursion is not allowed, so a boolean is appropriate.  You could also use an int to allow recursion to a specific depth or just to track the depth you are at.