Unit Testing a large method

Question

Following Test-Driven Development that is.

I've recently implemented a algorithm (A*) that required a clean interface. By clean all I want is a couple of properties and a single search method.

What I've found hard is testing the search method. It contains around five steps but I'm essentially forced to code this method in one big go which makes things hard.

Is there any advice for this?

Edit

I'm using C#. No I don't have the code at hand at the moment. My problem relies in the fact a test only passes after implementing the whole search method - rather than a step in the algorithm. I naturally refactored the code after but it was implementing I found hard.

Answer 1

You might consider Texttest (http://texttest.carmen.se/) as a way of testing "under the interface".

It allows you to check behavior by examining logged data to verify behavior, rather than purely black-box-style testing on arguments and method results.

DISCLAIMER: I've heard a presentation on Texttest, and looked at the docs, but haven't yet had the time to try it out in a serious application.

Answer 2

Refactor your big method into smaller, private methods. Use reflection, or another mechanism available in your language, to test the smaller methods independently. Worst case -- if you don't have access to reflection or friends, make the methods protected and have your test class inherit from the main class so it can have access to them.

Update: I should also clarify that simply refactoring to private methods doesn't necessarily imply that you need to create tests specific to those methods. If you are thoroughly testing the public methods that rely on the private methods, you may not need to test the private methods directly. This is probably the general case. There are times when it does make sense to test private methods directly (say when it simplifies or reduces the number of test cases needed for public methods), but I wouldn't consider it a requirement to create tests simply because you refactor to a private method implementation.

Answer 3

If your steps are large enough (or are meaningful in their own right) you should consider delegating them to other smaller classes and test the interaction between your class and them. For example if you have a parsing step followed by a sorting step followed by a searching step it could be meaningful to have a parser class, a sorter class, etc. You would then use TDD on each of those.

No idea which language you're using, but if you're in the .net world you could make these classes internal and then expose them to your test class with "internals visible to" which would keep them hidden.

If the steps are small AND meaningless on their own then tvanfosson's suggestions are the way to go.

Answer 4

I'm assuming that A* means the search algorithm (e.g. http://en.wikipedia.org/wiki/A*_search_algorithm). If so, I understand your problem as we have similar requirements. Here's the WP algorithm, and I'll comment below:

---

Pseudo code

 function A*(start,goal)
     closedset := the empty set                 % The set of nodes already evaluated.     
     openset := set containing the initial node % The set of tentative nodes to be evaluated.
     g_score[start] := 0                        % Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           % Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from,goal)
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)

             if y not in openset
                 add y to openset

                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
     return failure

 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return the empty path

The closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower f value than at any previous iteration.

---

First, and I'm not being frivolous, it depends whether you understand the algorithm - it sounds as if you do. It would also be possible to transcribe the algorithm above - hoping it worked) and give it a number of tests. That's what I would do as I suspect that the authors of WP are better than me!. The large-scale tests would exercise edge cases such as no node, one node, two nodes+no edge, etc... If they all passed I would sleep happy. But if they failed there is no choice but to understand the algorithm.

If so I think you have to construct tests for the data structures. These are (at least) set, distance, score, etc. You have to create these objects and test them. What is the expected distance for case 1,2,3... write tests. What is the effect of adding A to set Z? needs a test. For this algorithm you need to test heuristic_estimate_of_distance and so on. It's a lot of work.

One approach may be to find an implementation in another language and interrogate it to find the values in the data structures. Of course if you are modifying the algorithm you are on your own!

There's one thing even worse than this - numerical algorithms. Diagonalizing matrices - do we actually get the right answers. I worked with one scientist writing 3rd derivative matrices - it would terrify me...

Answer 5

An important thing to remember when employing TDD is that tests don't need to live forever.

In your example you know you're going to provide a clean interface, and much of the operation will be delegated to private methods. I think it's the assumption that these methods have to be created as private, and stay that way, that causes the most bother. Also the assumption that the tests must stay around once you've developed them.

My advice for this scenario would be to:

• Sketch the skeleton of the large method in terms of new methods, so you have a series of steps which make sense to test individually.
• Make these new methods public by default, and begin to develop them using TDD.
• Then once you have all the parts tested, write another which tests the entire method. Ensuring that if any of the smaller, delegated parts are broken this new test will fail.
• At this point the big method works, and is covered by tests, you can now begin to refactor. I'd recommend, as FinnNk does, trying to extract the smaller methods into classes of their own. If this doesn't make sense, or if it would take too much time, I'd recommend something others may not agree with: change the small methods into private ones and delete the tests for them.

The result is that you have used TDD to create the entire method, the method is still covered by the tests, and the API is exactly the one you want to present.

A lot of confusion comes from the idea that once you've written a test, you always have to keep it, and that is not necessarily the case. However, if you are sentimental, there are ways unit tests for private methods can be achieved in Java, perhaps there are similar constructs in C#.