# Monday, September 08, 2008

The other day I stumbled on a first draft on a new book on algorithms (Data Structure and Algorithms). After taking a peak at the draft, I found some (hidden) motivation to finally write a decent binary heap for QuickGraph. A heap is a critical data structure for Dijkstra shortest path or Prim's minimum spanning tree algorithm, since it is used to build efficient priority queues.

In this post, we'll start building a binary heap using Test-Driven Development (write the tests first, etc...) and parameterized unit tests.

BinaryHeap?

The heap is a tree where each parent node has a value smaller or equal to the child nodes. The binary heap is a heap implemented through a binary tree, and to make things more interesting (and fast), the tree is usually mapped to an array using indexing magic:

  • parent node index: (index - 1) /2
  • left child node: 2*index + 1
  • right child node: 2*index + 2

The indexing magic is typically the kind of things that introduce bugs.

Let's write that first test

We start by writing a test that simply fills any binary heap with a number of entries. A possible test for this is written as follows:

[PexMethod]
public void Insert<TPriority, TValue>(
    [PexAssumeUnderTest]BinaryHeap<TPriority, TValue> target,
    [PexAssumeNotNull] KeyValuePair<TPriority, TValue>[] kvs)
{
    var count = target.Count;
    foreach (var kv in kvs) {
        target.Add(kv.Key, kv.Value);
        AssertInvariant<TPriority, TValue>(target);
    }
    Assert.IsTrue(count + kvs.Length == target.Count);
}

There are a number of unusual annotations in this test. Let's review all of them:

  • The test is generic: Pex supports generic unit tests. This is really convenient when testing a generic type.
  • PexAssumeUnderTest, PexAssumeNotNull: it basically tells Pex that we don't care about the case where kvs or target is null.
  • We've added a Add(TPriority priority, TValue value) method and Count property to the BinaryHeap

There are also two assertions in the test. Inlined in the loop, we check the invariant of the heap (AssertInvariant). We'll fill up this method as we go. At the end of the test, we check that the Count property.

BinaryHeap version #0

We start with a simple (broken) implementation that does nothing:

public class BinaryHeap<TPriority, TValue> {
    public void Add(TPriority priority, TValue value) { }
    public int Count { returnt 0; }
}

Now that the code compiles, we run Pex which quickly finds that a non-empty array breaks the count assertion.

image

BinaryHeap version #1

We have a failing test so let's fix the code by storing the items in a list:

public class BinaryHeap<TPriority, TValue> {
    List<KeyValuePair<TPriority, TValue>> items = new List<KeyValuePair<TPriority, TValue>>();
    public void Add(TPriority priority, TValue value) {
        this.items.Add(new KeyValuePair<TPriority, TValue>(priority, value));
    }
    public int Count {
        get { return this.items.Count; }
    }

We run Pex again and all the previous failing tests are now passing :)

image

There's a new object creation event that happened (bold events should be looked at). Remember that the test takes a binary heap as argument, well we probably need to tell Pex how to instantiate that class. In fact, this is exactly what happens when I click on the object creation button:

image

Pex tells me that it guessed how to create the binary heap instance and gives me the opportunity to save and edit the factory. The factory looks like this and get included automatically in the test project:

[PexFactoryClass]
public partial class BinaryHeapFactory {
    [PexFactoryMethod(typeof(BinaryHeap<int, int>))]
    public static BinaryHeap<int, int> Create() {
        BinaryHeap<int, int> binaryHeap = new BinaryHeap<int, int>();
        return binaryHeap;
    }
}

All our tests are passing, we can write the next test... but wait!

We have an invariant!

The nice thing about data structures is that they have fairly well defined invariants. These are very useful for testing!

In the case of the heap, we know that the parent node priority should always be less or equal to the priorities of both of his left and right children. Therefore, we can add a method to BinaryHeap that walks the array and checks this property on each node:

[Conditional("DEBUG")]
public void ObjectInvariant() {
    for (int index = 0; index < this.count; ++index) {
        var left = 2 * index + 1;
        Debug.Assert(left >= count || this.Less(index, left));
        var right = 2 * index + 2;
        Debug.Assert(right >= count || this.Less(index, right));
    }
}
private bool Less(int i, int j) { return false; }

Remember that AssertInvariant method, let's call ObjectInvariant in that method and run Pex again.

void AssertInvariant<TPriority,TValue>(BinaryHeap<TPriority,TValue> target) {
    target.ObjectInvariant();
}

Pex immediately finds an issue:

image

This assertion is due to our overly simplified implementation of Less, which always return false.

Fixing tests, and finding new failing tests

We have failing tests so it's time to fix the code again. Let's start fixing on the Less method by using a comparer:

readonly Comparison<TPriority> comparison =
    Comparer<TPriority>.Default.Compare;
private bool Less(int i, int j)
{
    return this.comparison(this.items[i].Key, this.items[j].Key) >= 0;
}

We run Pex and it comes back with the following tests:

image

Two interesting things happened here:

  • the previous failing test (with [0,0], [0,0]) was fixed by fixing Less
  • Pex found a new issue where the input array involves a small key (3584), then a larger key (4098). A correct heap implementation would have kept the smaller key at the first position.

The coolest part is we did not have to write any additional line of code to get to this point: Pex updated the previous tests and generated the new failure for us.

This is a new kind of flow that occurs when using Pex in TDD: a code update has fixed some issues but created new ones. We are still moving towards our goal but we did not have to pay the price of writing a new unit test.

In fact, to fulfill the invariant and make this test pass we will have to write a correct implementation of the Add method.... without writing a single additional line of test code :)

to be continued...

posted on Monday, September 08, 2008 10:39:35 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [1]
# Tuesday, August 26, 2008

Update: renamed project to YUnit to avoid clashing with other frameworks.

I've been playing with custom test types for team test lately and the result of this experiment is YUnit. A microscopic test framework that lets you write tests anywhere since it only uses the Conditional attribute. That's right, any public static parameterless method tagged with [Conditional("TEST")] becomes a test :)

If you've always dreamed of implementing your own custom test type, this sample could be helpful to you. Remember that this is only a sample and comes with no guarantees of support.

Sources and installer available at: http://code.msdn.microsoft.com/yunit.

 

posted on Tuesday, August 26, 2008 8:26:36 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]

It's that time of the year where a little refresh of QuickGraph (http://www.codeplex.com/quickgraph) is needed.

What's new?

  • New API to add and remove vertices from the graphs
  • Important bug fixes in the shortest path algorithms (oops!)
  • Support for MSAGL ( http://research.microsoft.com/research/msagl/ )
  • QuickGraph.Data, provides data structures build graphs of databases (given a DataSet)
  • QuickGraph.Heap, provides data structure to build graphs of SOS managed memory dumps (more later)

Enjoy.

 

posted on Tuesday, August 26, 2008 9:11:35 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Wednesday, August 06, 2008

Read on Nikolai's announcement on the latest drop of Pex.

posted on Wednesday, August 06, 2008 11:06:59 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
# Thursday, July 31, 2008

Alexander Nowak has started a blog post chronicle on Pex and already has 6 episodes to it!

  • Pex - test Case 5 (regular expressions)
  • Pex - test case 4 (strings and parameter validation)
  • Pex - Test case 3 (enums and business rules validation)
  • Pex - test case 2 
  • Pex - test case 1
  • Starting with Pex (Program Exploration)

    The posts give a nice point of view of Pex from a user perspective, and against classic testing techniques such as equivalence classes.

  • posted on Thursday, July 31, 2008 7:25:49 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Tuesday, July 29, 2008

    Linear programming problems are usually solved using the simplex algorithm. While it is easy to encode a constraint system of linear equalities and inequalities as a Parameterized Unit Test for Pex, there is currently no way to tell Pex that we want test inputs that are “minimal” according to a custom objective function. However, Pex can still generate *surprising* feasible solutions.

    Let's start with a simple set of linear inequalities that define our problem.

    [PexMethod]
    public int Test(int x, int y)
    {
    // PexAssume is used to add 'constraints' on the input
    // in this case, we simply encode the inequalities in a boolean formula PexAssume.IsTrue( x + y < 10 & // using bitwise & to avoid introducing branches 5 * x + 2 * y > 20 & -x + 2 * y > 0 & x > 0 & y > 0);
    // the profit is returned so that it is automatically logged by Pex return x + 4 * y; }

    After running Pex, we get one feasible solution. It is not optimal as expected since we don't apply the simplex algorithm.

    image

    Enter overflows

    Remember that .Net arithmetic operations will silently overflow unless you execute them in a checked context? Let's push our luck and try to force an overflow by changing x > 0 constraint to x > 1000:

    [PexMethod]
    public int Test(int x, int y)
    {
        PexAssume.IsTrue(
            x + y < 10 &
            5 * x + 2 * y > 20 &
            -x + 2 * y > 0 &
            x > 1000 & y > 0
        );
        return x + 4 * y;
    }

    Z3, the constraint solver that Pex uses to compute new test inputs, uses bitvector arithmetic to find a surprising solution that fulfills all the inequalities (our profit has just gone of the roof :)).

    image 

    Z3 is truly an astonishing tool!

    Checked context

    In order to avoid overflow, one should use a checked context. Let's update the parameterized unit test:

    [PexMethod]
    public int Test(int x, int y)
    {
        checked
        {
            PexAssume.IsTrue(
                x + y < 10 &
                5 * x + 2 * y > 20 &
                -x + 2 * y > 0 &
                x > 0 & y > 0
            );
        }
        return x + 4 * y;
    }

    In fact, in that case, Pex generates 2 test cases. One test that passes and the other test that triggers an OverflowException (implicit branch).

    image

    Stay tuned for more surprising discoveries using Pex.

    posted on Tuesday, July 29, 2008 6:35:31 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [2]
    # Thursday, July 03, 2008

    Brian Keller dropped by our offices to record a movie on Pex. A good old white board session to explain how pex works:

    http://channel9.msdn.com/posts/briankel/Pex-Automated-Exploratory-Testing-for-NET/

     

    posted on Thursday, July 03, 2008 11:21:54 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Monday, June 23, 2008

    We've added a little filter to Pex that flags potential testability issues in your source code (at least in the context of unit testing). The idea is simple: if your code logic branches over API that depends on the environment (file system, UI, network, time, etc...), you're not doing 'pure' unit testing anymore and it could be flagged as a testability issue.

    Why do we do this anyway?

    The problem is that Pex is very sensitive to those issues: it cannot control the environment. Let's take a look at a simple example where we write a custom stream class with a testability issue in one of the constructor:

    image

    The constructor checks that the file exists. In order to pass that point in the program, you would actually need to create or find an actual file in the file system. You're talking to the file system, this is already integration testing.

    Parameterized drama

    Let's be optimistic and write a parameterized unit test that reads a file:

    image

    Pex comes back with a single test, passing null as fileName (i.e. default(string)). Since Pex does not know how the file system works, it cannot create a valid file name, and that's where the story ends.

    image 

    Help is on the way

    To help you diagnose these issues, we've added specialized logging flags. Pex shows hints in the issue notification area:

    image

    Clicking on that event will give you additional important data: which API was called and the stacktrace at the time of the call :)

    image

    posted on Monday, June 23, 2008 11:08:33 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Wednesday, June 04, 2008

    Ever wonder what was happening inside the ResourceReader (where do those resources come from anyway!).... Check out Nikolai's post on using Pex to test this (complicated) class...

    posted on Wednesday, June 04, 2008 7:17:06 PM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]
    # Saturday, May 24, 2008

    If you're interrested on reading more about Pex, here are some online document that should get you satisfied:

    The tutorial contains hands-on labs and exercises to understand how Pex generates new test cases. Highly recommend if you're interrested on Pex.

    Happy reading!

    posted on Saturday, May 24, 2008 9:00:01 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]