How to write a Mockist test of a recursive method

Question

If I have a method that calls itself under a certain condition, is it possible to write a test to verify the behavior? I'd love to see an example, I don't care about the mock framework or language. I'm using RhinoMocks in C# so I'm curious if it is a missing feature of the framework, or if I'm misunderstanding something fundamental, or if it is just an impossibility.

Answer 1

There isn't anything to monitor stack depth/number of (recursive) function calls in any mocking framework I'm aware of. However, unit testing that the proper mocked pre-conditions provide the correct outputs should be the same as mocking a non-recursive function.

Infinite recursion that leads to a stack overflow you'll have to debug separately, but unit tests and mocks have never gotten rid of that need in the first place.

Answer 2

Assuming you want to do something like get the filename from a complete path, for example:

c:/windows/awesome/lol.cs -> lol.cs
c:/windows/awesome/yeah/lol.cs -> lol.cs
lol.cs -> lol.cs

and you have:

public getFilename(String original) {
  var stripped = original;
  while(hasSlashes(stripped)) {
    stripped = stripped.substringAfterFirstSlash(); 
  }
  return stripped;
}

and you want to write:

public getFilename(String original) {
  if(hasSlashes(original)) {
    return getFilename(original.substringAfterFirstSlash()); 
  }
  return original;
}

Recursion here is an implementation detail and should not be tested for. You really want to be able to switch between the two implementations and verify that they produce the same result: both produce lol.cs for the three examples above.

That being said, because you are recursing by name, rather than saying thisMethod.again() etc., in Ruby you can alias the original method to a new name, redefine the method with the old name, invoke the new name and check whether you end up in the newly defined method.

def blah
  puts "in blah"
  blah
end

alias blah2 blah

def blah
  puts "new blah"
end

blah2

Answer 3

a method that calls itself under a certain condition, is it possible to write a test to verify the behavior?

Yes. However, if you need to test recursion you better separate the entry point into the recursion and the recursion step for testing purposes.

Anyway, here is the example how to test it if you cannot do that. You don't really need any mocking:

// Class under test
public class Factorial
{
    public virtual int Calculate(int number)
    {
        if (number < 2)
            return 1
        return Calculate(number-1) * number;
    }
}

// The helper class to test the recursion
public class FactorialTester : Factorial
{
    public int NumberOfCalls { get; set; }

    public override int Calculate(int number)
    {
        NumberOfCalls++;
        return base.Calculate(number)
    }
}    

// Testing
[Test]
public void IsCalledAtLeastOnce()
{
    var tester = new FactorialTester();
    tester.Calculate(1);
    Assert.GreaterOrEqual(1, tester.NumberOfCalls  );
}
[Test]
public void IsCalled3TimesForNumber3()
{
    var tester = new FactorialTester();
    tester.Calculate(3);
    Assert.AreEqual(3, tester.NumberOfCalls  );
}

Answer 4

You're misunderstanding the purpose of mock objects. Mocks (in the Mockist sense) are used to test behavioral interactions with dependencies of the system under test.

So, for instance, you might have something like this:

interface IMailOrder
{
   void OrderExplosives();
}

class Coyote
{
   public Coyote(IMailOrder mailOrder) {}

   public void CatchDinner() {}
}

Coyote depends on IMailOrder. In production code, an instance of Coyote would be passed an instance of Acme, which implements IMailOrder. (This might be done through manual Dependency Injection or via a DI framework.)

You want to test method CatchDinner and verify that it calls OrderExplosives. To do so, you:

1. Create a mock object that implements IMailOrder and create an instance of Coyote (the system under test) by passing the mock object to its constructor. (Arrange)
2. Call CatchDinner. (Act)
3. Ask the mock object to verify that a given expectation (OrderExplosives called) was met. (Assert)

When you setup the expectations on the mock object may depend on your mocking (isolation) framework.

If the class or method you're testing has no external dependencies, you don't need (or want) to use mock objects for that set of tests. It doesn't matter if the method is recursive or not.

You generally want to test boundary conditions, so you might test a call that should not be recursive, a call with a single recursive call, and a deeply-recursive call. (miaubiz has a good point about recursion being an implementation detail, though.)

EDIT: By "call" in the last paragraph I meant a call with parameters or object state that would trigger a given recursion depth. I'd also recommend reading The Art of Unit Testing.

EDIT 2: Example test code using Moq:

var mockMailOrder = new Mock<IMailOrder>();
var wily = new Coyote(mockMailOrder.Object);

wily.CatchDinner();

mockMailOrder.Verify(x => x.OrderExplosives());

Answer 5

Here's my 'peasant' approach (in Python, tested, see the comments for the rationale)

Note that implementation detail "exposure" is out of question here, since what you are testing is the underlying architecture which happens to be utilized by the "top-level" code. So, testing it is legitimate and well-behaved (I also hope, it's what you have in mind).

The code (the main idea is to go from a single but "untestable" recursive function to an equivalent pair of recursively dependent (and thus testable) functions):

def factorial(n):
    """Everyone knows this functions contract:)
    Internally designed to use 'factorial_impl' (hence recursion)."""
    return factorial_impl(n, factorial_impl)

def factorial_impl(n, fct=factorial):
    """This function's contract is
    to return 'n*fct(n-1)' for n > 1, or '1' otherwise.

    'fct' must be a function both taking and returning 'int'"""
    return n*fct(n - 1) if n > 1 else 1

The test:

import unittest

class TestFactorial(unittest.TestCase):

    def test_impl(self):
        """Test the 'factorial_impl' function,
        'wiring' it to a specially constructed 'fct'"""

        def fct(n):
            """To be 'injected'
            as a 'factorial_impl''s 'fct' parameter"""
            # Use a simple number, which will 'show' itself
            # in the 'factorial_impl' return value.
            return 100

        # Here we must get '1'.
        self.assertEqual(factorial_impl(1, fct), 1)
        # Here we must get 'n*100', note the ease of testing:)
        self.assertEqual(factorial_impl(2, fct), 2*100)
        self.assertEqual(factorial_impl(3, fct), 3*100)

    def test(self):
        """Test the 'factorial' function"""
        self.assertEqual(factorial(1), 1)
        self.assertEqual(factorial(2), 2)
        self.assertEqual(factorial(3), 6)

The output:

Finding files...
['...py'] ... done
Importing test modules ... done.

Test the 'factorial' function ... ok
Test the 'factorial_impl' function, ... ok

----------------------------------------------------------------------
Ran 2 tests in 0.000s

OK