Trampoline Interceptor

Question

Aim

In C#, the following method will cause a StackOverFlowException if called with parameter 0:

int Recurse(int i)
{
    return i<100000 ? Recurse(i+1) : i;
}

However, this method actually uses tail-call recursion, meaning that if it ever performs a recursive call, that is always the last operation it performs. For this reason, if the language supported tail call recursion optimization, a stack overflow exception could be prevented by moving down by one stack frame before entering the recursive call. (Alternatively, it could be converted into a loop, but I won't be worrying about that)

While this is not supported by C# (see below), a method that uses tail-call recursion can use a construct called a "trampoline" to run a recursive method without growing the stack. My aim was to create a trampoline which:

• Requires minimal modification of the recursive method to be trampolined
• Has minimal performance impact

With the former being the much higher priority. For that reason I chose an interceptor as the trampoline construct, using Castle's dynamic proxies.

(EDIT: As pointed out in the comments, the CLR will sometimes optimize tail-call recursion and avoid stack overflows. However, my understanding is that it does not always do so, and makes no guarantee about ever doing so, and so it's generally not reliable enough to avoid exceptions in many situations)

The Code

public class TrampolineInterceptor : IInterceptor
{
    private readonly IMethodFilter _methodFilter;
    private static bool _inProgress = false;
    private static bool _invokeNext = false;
    private static bool _first = true;

    private static IInvocation _pending = null;
    private static object _dummyReturnValue = null;

    public TrampolineInterceptor(IMethodFilter methodFilter)
    {
        _methodFilter = methodFilter;
    }

    public void Intercept(IInvocation invocation)
    {
        if(!_methodFilter.ShouldIntercept(invocation))
            invocation.Proceed();
        else if(_first)
            OutermostLoop(invocation);
        else if(_invokeNext)
            ProceedWithInvocation(invocation);
        else
            StoreInvocation(invocation);
    }

    private static void OutermostLoop(IInvocation invocation)
    {
        _first = false;
        _pending = invocation;
        _inProgress = true;
        _dummyReturnValue = CreateDummyReturn(invocation.Method.ReturnType);

        while (_inProgress)
        {
            _invokeNext = true;
            _inProgress = false;
            _pending.Proceed();
        }

        _first = true;
        invocation.ReturnValue = _pending.ReturnValue;
    }

    private static void ProceedWithInvocation(IInvocation invocation)
    {
        _invokeNext = false;
        invocation.Proceed();
    }

    private static void StoreInvocation(IInvocation invocation)
    {
        _inProgress = true;
        _pending = invocation;
        invocation.ReturnValue = _dummyReturnValue;
    }

    private static object CreateDummyReturn(Type returnType)
    {
        var makeDefault = typeof(TrampolineInterceptor).GetMethod("GetDefault", BindingFlags.NonPublic | BindingFlags.Static);
        return makeDefault.MakeGenericMethod(returnType).Invoke(null, new object[] { });
    }

    private static T GetDefault<T>()
    {
        return default(T);
    }
}

public interface IMethodFilter
{
    bool ShouldIntercept(IInvocation method);
}

Logic

Since this is a bit unusual, a quick overview of what's happening. There are three main states the trampoline can be in, corresponding to the three methods that can get called from Intercept:

• Starting. This is when the trampoline isn't currently being used. The main bouncing loop starts, and the original invocation is set to be the first to be processed
• Bouncing. The invocation proceeds as usual, so that we can get to the next invocation in the chain. We're ascending up through the call chain
• Bounce apex. Instead of ascending forever, as we would if there was no interceptor at all, here we cut off the bounce. Instead of actually processing the invocation (which would take us into the interceptor for the next invocation), we store it and return a dummy value, letting us fall back down into our main loop.

Finally in addition to that we need a way to indicate when we're done, which is when while bouncing, instead of ascending to another invocation, we get a return value from our invocation.

Limitations

While this was a fun experiment, it has significant enough limitations that I doubt there will be many applications where it's really appropriate, especially since the alternative always exists of simply converting any tail recursive method into a loop. I'll list the main limitations here mainly so they don't get repeated in answers, but also in case anybody has any suggestions in alleviating any of them (which fit within the scope of a code review, anyway)

• If this interceptor intercepts a method that is not tail call recursive, it could cause all sorts of bizarre behaviour, and since there is no way to detect whether or not it is, there's no way to safely or gracefully handle these situations.
• No concurrency support, and no graceful handling of attempted concurrency
• This only works correctly if the proxy is generated through ProxyGenerator.CreateClassProxy. This means that the trampolined method must be virtual.
• The method also, of course, has to be public
• There are probably scenarios in which this would not play nice with other interceptors. I haven't given much thought to how likely this is to arise

Review focus

I'm interested in a general review, but points of particular interest would be:

• Logic simplification. The logic feels like it's overly complex. I'm especially unhappy with the need for three booleans.
• Naming. I had difficulty naming these methods, and I'm not very happy with what I ended up on. Although they're somewhat less serious sounding, I had considered alternatives including "Bounce", like BounceUp and BounceApex, which fit with the visual analogy of a trampoline well enough that they could potentially be clearer.

Answer 1

The logic feels like it's overly complex. I'm especially unhappy with the need for three booleans.

Yeah, I agree that especially the logic around _invokeNext is messy, but I think that's required due to the way Proceed() behaves (the invocation is intercepted again if it's not currently being intercepted). But in cases like these, it's important to document why you wrote it that way, for the benefit of any future readers of the code.

I also considered getting rid of _inProgress by setting _pending to null and then checking for that, but that would mean you would have to deal with the return value some other way, so I think it's not worth it.

---

I think your fields should not be static, that way invoking one tail-recursive method from another tail-recursive method could work, at least if each is on a different object and uses different instance of your interceptor. (To make it work for methods on the same object would require some additional logic in the interceptor.)

---

IMethodFilter _methodFilter

Why is this a custom interface and not a delegate (Func<IInvocation, bool> or Predicate<IInvocation>)? Is it because Dependency Injection?

---

if(!_methodFilter.ShouldIntercept(invocation))

Commonly, a space is written between if and (, since if is not a method.

---

makeDefault.MakeGenericMethod(returnType).Invoke(null, new object[] { });

Not sure why you're using an array initializer here, I think new object[0] is clearer. Also, according to the documentation, you can pass null instead of the empty array.