Recursive Methods, Stack Overflow, IIS & FXCop

Had some serious issues lately around crashing IIS. The logs indicated a Stack Overflow Exception, error code 0x800703E9.

But it wasn't obvious what caused this, since no recent changes seemed to be the culprit, and developers seemed to be unaware of any recursion in our code.

Unfortunately, there is far too much code to aimlessly search through.

I identified the following possible cases where we may have introduced recursion:

1. Intended recursion, a method directly calling itself somewhere
2. Possibly intended recursion, a method indirectly calling itself via another method.
3. Unintended recursion when an overloaded method calls itself instead of one of the other overloads because of too many or few arguments.
4. Unintended recursion because of a typo in a property getter or setter
5. Unintended recursion because of a missing (T) cast when calling 'static bool T.Equals( T x, T y)' inside an 'override bool Equals(object obj)'
6. .Net library classes throwing this exception.


More info:

1.
This is straight forward enough... a method somewhere has a flaw either in the logic that identifies stopping conditions causing infinite recursion, or the depth of recursion depends on the inputs, and the method is processing inputs larger than the developer considered.

2.
See above.


3.
Overloading, without being careful with the arguments can mean a method calling itself instead of the other overload, e.g.

public class X
{
public int A( int f)
{
// infinite recursion - developer should have
// written 'return A(f, 0);'
return A(f);
}

public int A( int f, int g)
{
return f + g;
}
}


4.
The following two properties cause infinite recursion. The first has a typo in the getter, the second has a typo in the setter. (the case is incorrect)

private string abc;
public string Abc
{
get { return this.Abc; }
set { this.abc = value; }
}

private string xyz;
public string Xyz
{
get { return this.xyz; }
set { this.Xyz = value; }
}

5.
It is common practice to implement public override bool Equals(object obj) in classes that are used in collections. It is also not uncommon to implement public static bool Equals(T a, T b) in the same classes too (e.g. the System.string class)

However, if the overridden method directly calls the static method without both of it's arguments cast to the correct type (T), then recursion could result, e.g.
public class T
{
public override bool Equals(object obj)
{
return T.Equals(this, obj);
}

public static bool Equals(T a, T b)
{
return true;
}

}

The above code will cause infinite recursion, since the first method is actually calling static bool object.Equals(object a, object b), not static bool T.Equals(T a, T b) which will then call bool T.Equals( object obj) on each argument.

To fix this, object obj must be cast to type T before calling the static method:
public class T
{
public override bool Equals(object obj)
{
return T.Equals(this, (T)obj);
}

public static bool Equals(T a, T b)
{
return true;
}

}


6.
Possibly Linq to SQL issue?
http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=355026


But how to identify any methods like this in a large library of code? FXCop to the rescue.

This is my first time using FXCop, but I couldnt find any existing rules that would identify these cases, so I set about writing some custom rules ( Tutorial )

A. Identifying direct recursive methods ( covers cases 1, 3 & 4 above)

I based my custom rule on the "Callees" example class here, with the following 'Check' implementation:
public override ProblemCollection Check(Member member)
{
Method method = member as Method;
if (method != null)
{
string unmangledName = method.GetUnmangledNameWithTypeParameters();

IList callees = Callees.CalleesFor(method);
foreach (Method c in callees)
{
if (string.Equals(c.FullName, method.FullName) && string.Equals(c.GetUnmangledNameWithTypeParameters(), unmangledName) )
{
Resolution res;
if (c.Name.Name.StartsWith("get_") || c.Name.Name.StartsWith("set_"))
{
res = this.GetResolution();
res = new Resolution(string.Format("Check property name typo. {0}", res.Format), new string[] { c.FullName } );
}
else
{
res = this.GetResolution(new string[] { c.FullName });
}
Problems.Add( new Problem(res) );
}
}
}
return this.Problems;
}


B. Identifying indirect recursive methods ( covers case 2 above)

Here's my implementation:
public override ProblemCollection Check(Member member)
{
Method method = member as Method;
if (method != null)
{
//string unmangledName = method.GetUnmangledNameWithTypeParameters();
string fullName = method.FullName;
if (!string.IsNullOrEmpty(fullName) && !fullName.StartsWith("Microsoft.") && !fullName.StartsWith("System."))
{
List methodStack = new List();
methodStack.Add(fullName);

IList callees = Callees.CalleesFor(method);

TraverseCallees(methodStack, callees);
}
}
return this.Problems;
}


private void TraverseCallees(List methodStack, IList callees)
{
foreach (Method c in callees)
{
//string unmangledName = c.GetUnmangledNameWithTypeParameters();
string fullName = c.FullName;
if (!string.IsNullOrEmpty(fullName) && !fullName.StartsWith("Microsoft.") && !fullName.StartsWith("System."))
{
if (methodStack.Contains(fullName))
{
// only match against the head of the stack, since all methods will be processed as the head once
if (string.Equals(methodStack[0], fullName))
{
// only show indirect calls
if (methodStack.Count > 2)
{
StringBuilder callStackDescription = new StringBuilder();

//bool logStack = false;
foreach (string methodFullName in methodStack)
{
//if (!logStack && methodFullName.Equals(fullName))
//{
// logStack = true;
//}

//if (logStack)
//{
callStackDescription.AppendFormat("{0} -> ", methodFullName);
//}
}
callStackDescription.AppendFormat("{0}", fullName);

Resolution res = new Resolution(GetResolution().Format, new string[] { callStackDescription.ToString() });

Problems.Add(new Problem(res, c));
}
else
{
// ignore recursion, where it is a method directly calling itself
}
}
}
else
{
methodStack.Add(fullName);

IList nextCallees = Callees.CalleesFor(c);

TraverseCallees(methodStack, nextCallees);

methodStack.RemoveAt(methodStack.Count - 1);
}
}
}
}


C. Overridden T.Equals Calling Object.Equals ( covers case 5 above )

public override ProblemCollection Check(Member member)
{
Method method = member as Method;
if (method != null)
{
string fullName = method.FullName;
if (!string.IsNullOrEmpty(fullName) && !fullName.StartsWith("Microsoft.") && !fullName.StartsWith("System."))
{
// check of our 'Equals' overrides the defualt 'object.Equals(object obj)', since that may be called by 'static object.Equals(object, object_'
if (string.Equals(method.OverriddenMethod == null ? null : method.OverriddenMethod.FullName, "System.Object.Equals(System.Object)"))
{
IList callees = Callees.CalleesFor(method);

foreach (Method c in callees)
{
if( c.IsStatic && string.Equals( c.FullName, "System.Object.Equals(System.Object,System.Object)") &&
c.Parameters.Count == 2 &&
string.Equals( c.Parameters[0].Type.FullName, "System.Object" ) &&
string.Equals( c.Parameters[1].Type.FullName, "System.Object" ))
//TODO: also check the the VALUE of one of the arguments is really of the same type as the parent caller method
{
Problems.Add(new Problem(GetResolution(), c));
}
}
}
}
}
return this.Problems;
}


Sure enough, my custom rules found new examples of cases 1 and 3. And I am aware of cases 4 & 5 happening in the past, although luckily they were fixed during development.