Searching for Exceptions in .NET

I recently came across a rather interesting question on StackOverflow that posed the problem of discovering all the exceptions that a given method might throw under every circumstance.

Of course, in the great majority of situations, XML  documentation for the BCL (and ideally any third-party libraries too) should provide information about any exception that might be thrown and any potential reason for it. Indeed, thisthis is generally all one needs to write largely error-safe code. However, not every exception is documented in any case, and for production-quality applications, it is often desirable to insure that there is no realistic chance of an unhandled exception ocurring. For this reason, it is sometimes desirable to do a rigorous check for all exceptions. Clearly, an application-level unhandled (fatal) exception handler would do the job to some extent, and although this is always a good fallback feature to have, it is the least elegant solution to coping with exceptions.

After some consideration, it became quite apparent that the task reduces to the halting problem. However, with a few simplifications, the problem does become relatively solvable. Most importantly, complex logic that determines whether an exception will be thrown must be ignored, and one must simply assume that any throw statement within a given method could possibly cause an exception under certain conditions.

Here is the complete code for the algorithm I wrote. The GetAllExceptions method is an extension method that returns a read-only collection of exceptions, which makes it very straightforward and efficient to use.

Notably, the code detects all of

• instantiated exceptions,
• exceptions return from method/property calls,
• exceptions stored in fields (though if the method return type or field type is non-specific, i.e. a parent class of the actual exception type thrown), this is used instead.

Exceptions are only counted when the appropiate throw instruction is encountered at some level. Also, the stack and local variables are handled correctly, as far as I can tell, so this method should work soundly in pretty much all cases. (It has been tested with some a few quite complex methods within the BCL, as well as simpler user-defined ones.)

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using ClrTest.Reflection;

public static class ExceptionAnalyser
{
    public static ReadOnlyCollection<Type> GetAllExceptions(this MethodBase method)
    {
        var exceptionTypes = new HashSet<Type>();
        var visitedMethods = new HashSet<MethodBase>();
        var localVars = new Type[ushort.MaxValue];
        var stack = new Stack<Type>();
        GetAllExceptions(method, exceptionTypes, visitedMethods, localVars, stack, 0);

        return exceptionTypes.ToList().AsReadOnly();
    }

    public static void GetAllExceptions(MethodBase method, HashSet<Type> exceptionTypes,
        HashSet<MethodBase> visitedMethods, Type[] localVars, Stack<Type> stack, int depth)
    {
        var ilReader = new ILReader(method);
        var allInstructions = ilReader.ToArray();

        ILInstruction instruction;
        for (int i = 0; i < allInstructions.Length; i++)
        {
            instruction = allInstructions[i];

            if (instruction is InlineMethodInstruction)
            {
                var methodInstruction = (InlineMethodInstruction)instruction;

                if (!visitedMethods.Contains(methodInstruction.Method))
                {
                    visitedMethods.Add(methodInstruction.Method);
                    GetAllExceptions(methodInstruction.Method, exceptionTypes, visitedMethods,
                        localVars, stack, depth + 1);
                }

                var curMethod = methodInstruction.Method;
                if (curMethod is ConstructorInfo)
                    stack.Push(((ConstructorInfo)curMethod).DeclaringType);
                else if (method is MethodInfo)
                    stack.Push(((MethodInfo)curMethod).ReturnParameter.ParameterType);
            }
            else if (instruction is InlineFieldInstruction)
            {
                var fieldInstruction = (InlineFieldInstruction)instruction;
                stack.Push(fieldInstruction.Field.FieldType);
            }
            else if (instruction is ShortInlineBrTargetInstruction)
            {
            }
            else if (instruction is InlineBrTargetInstruction)
            {
            }
            else
            {
                switch (instruction.OpCode.Value)
                {
                    // ld*
                    case 0x06:
                        stack.Push(localVars[0]);
                        break;
                    case 0x07:
                        stack.Push(localVars[1]);
                        break;
                    case 0x08:
                        stack.Push(localVars[2]);
                        break;
                    case 0x09:
                        stack.Push(localVars[3]);
                        break;
                    case 0x11:
                        {
                            var index = (ushort)allInstructions[i + 1].OpCode.Value;
                            stack.Push(localVars[index]);
                            break;
                        }
                    // st*
                    case 0x0A:
                        localVars[0] = stack.Pop();
                        break;
                    case 0x0B:
                        localVars[1] = stack.Pop();
                        break;
                    case 0x0C:
                        localVars[2] = stack.Pop();
                        break;
                    case 0x0D:
                        localVars[3] = stack.Pop();
                        break;
                    case 0x13:
                        {
                            var index = (ushort)allInstructions[i + 1].OpCode.Value;
                            localVars[index] = stack.Pop();
                            break;
                        }
                    // throw
                    case 0x7A:
                        if (stack.Peek() == null)
                            break;

                        exceptionTypes.Add(stack.Pop());
                        break;
                    default:
                        switch (instruction.OpCode.StackBehaviourPop)
                        {
                            case StackBehaviour.Pop0:
                                break;
                            case StackBehaviour.Pop1:
                            case StackBehaviour.Popi:
                            case StackBehaviour.Popref:
                            case StackBehaviour.Varpop:
                                stack.Pop();
                                break;
                            case StackBehaviour.Pop1_pop1:
                            case StackBehaviour.Popi_pop1:
                            case StackBehaviour.Popi_popi:
                            case StackBehaviour.Popi_popi8:
                            case StackBehaviour.Popi_popr4:
                            case StackBehaviour.Popi_popr8:
                            case StackBehaviour.Popref_pop1:
                            case StackBehaviour.Popref_popi:
                                stack.Pop();
                                stack.Pop();
                                break;
                            case StackBehaviour.Popref_popi_pop1:
                            case StackBehaviour.Popref_popi_popi:
                            case StackBehaviour.Popref_popi_popi8:
                            case StackBehaviour.Popref_popi_popr4:
                            case StackBehaviour.Popref_popi_popr8:
                            case StackBehaviour.Popref_popi_popref:
                                stack.Pop();
                                stack.Pop();
                                stack.Pop();
                                break;
                        }

                        switch (instruction.OpCode.StackBehaviourPush)
                        {
                            case StackBehaviour.Push0:
                                break;
                            case StackBehaviour.Push1:
                            case StackBehaviour.Pushi:
                            case StackBehaviour.Pushi8:
                            case StackBehaviour.Pushr4:
                            case StackBehaviour.Pushr8:
                            case StackBehaviour.Pushref:
                            case StackBehaviour.Varpush:
                                stack.Push(null);
                                break;
                            case StackBehaviour.Push1_push1:
                                stack.Push(null);
                                stack.Push(null);
                                break;
                        }

                        break;
                }
            }
        }
    }
}

To be quite honest, I’m not sure whether I’ll need to use this code myself at any point, but I’ve posted it regardless for the benefit of anyone who might require such rigorous exception checking. It was definitely an interesting challenge, at the least.

Any further comments or suggestions would be welcome, as always.

Combining Ordered Lists in .NET

I recently came across an issue with LINQ involving the combination of ordered (sorted) lists. The problem does not seem to have a simple solution within the core libraries of .NET 3.5, so I decided to write my own (short) function to accomplish the task. Extensions methods and the static Enumerable class usually contain all the possible methods you might need for dealing with lists (or more generally enumerable collections). Combining ordered lists, however, isn’t quite so straightforward a process (to do efficiently) as it might first seem. Of course, you could simply do Enumerable.Concat(listA, listB).OrderBy(keySelector) but it should be apparent that this is very inefficient for large lists if you know your lists are already ordered. Moreover, the call will never return if either or both of the enumerable collections you pass are of infinite length. What you really want to do is select items from the lists by switching back and forth between them, picking whichever of the next items ought to come first (which is determined by the key selector and associated IComparable implementation).

public static IEnumerable<TSource> CombineOrdered<TSource, TKey>(this IEnumerable<TSource> first,
    IEnumerable<TSource> second, Func<TSource, TKey> keySelector) where TKey : IComparable<TKey>
{
    var firstEnumerator = first.GetEnumerator();
    var secondEnumerator = second.GetEnumerator();
    var firstCanAdvance = firstEnumerator.MoveNext();
    var secondCanAdvance = secondEnumerator.MoveNext();
    var firstCurKey = keySelector(firstEnumerator.Current);
    var secondCurKey = keySelector(secondEnumerator.Current);

    while (true)
    {
        if (firstCanAdvance && (!secondCanAdvance || firstCurKey.CompareTo(secondCurKey) <= 0))
        {
            yield return firstEnumerator.Current;
            firstCanAdvance = firstEnumerator.MoveNext();
            if (firstCanAdvance) firstCurKey = keySelector(firstEnumerator.Current);
        }
        else if (secondCanAdvance)
        {
            yield return secondEnumerator.Current;
            secondCanAdvance = secondEnumerator.MoveNext();
            if (secondCanAdvance) secondCurKey = keySelector(secondEnumerator.Current);
        }
        else
        {
            yield break;
        }
    }
}

To use the function, for example within a static class named Enumerable2, you can call it as such:

var combinedList = Enumerable2.CombineOrdered(listA, listB, keySelector);

Note: The given implementation needs to take lists sorted in an ascending order and returns a combined list in the same order. To sort descending, change the <= sign to a >= sign in the code and insure that you pass lists sorted in a descending order.