Peli's Farm - Pex, Stubs, QuickGraph, MbUnit, Reflector Addins

Pex 0.14.040610.2: Fix Suggestions for Invariant Methods and Natural properties for Stubs.

Jonathan de Halleux — Fri, 12 Jun 2009 02:14:58 GMT

We have just released a new version of Pex, v0.14.040610.2. This version brings a range of Bug Fixes that were reported on the MSDN forums and a couple new features: Fix Suggestions for Invariant Methods and Natural properties for Stubs.

Fix Suggestions for Invariant Methods

When you use Code Contracts, then Pex can now help you to add missing invariants, just as Pex already inferred missing preconditions in the past. Take for example the ArrayList class that comes with the samples of our recently updated tutorial slide deck. This class has the following fields:

When you add an empty invariant method,

and enable Runtime Checking of contracts, then Pex will create instances of this class using reflection while making sure that the invariants holds (we announced this feature in the last release). However, with an empty invariant method, Pex will be able to create illegal states, e.g. where the _items array is null, which may cause a NullReferenceException, and other issues. To get the following test cases, we let Pex explore the Add method of our ArrayList class:

When you look at the details of the failing test cases, then you will see that Pex now offers the option to add invariants directly into your [ContractInvariantMethod]:

Natural Properties for Stubs

The logic to handle properties with setters and getters generated by Stubs has been slightly improved so that it is possible to force properties to have as if they had a backing field.

When a getter or a setter of a property is invoked, Stubs checks whether the getter delegate or the setter delegates have been set. If not, i.e. no custom user behavior, it queries the fallback behavior for an initial value of the property. If the fallback behavior successfully returns a value, Stubs generates a closure and binds the getter and setter.

For example, here’s a simple IFoo interface with a Bar property:

One could write the following parameterized unit test:

Since we expect the Bar property to behave as it was wrapping a field, we don’t expect the assertion to be raised. When we execute this test with Pex, and the Pex fallback behavior, Pex will choose a value for ‘Bar’, and this value will be ‘stored’ the property. Therefore, we get as expected 2 test cases:

Non default constructor support for Stubs

In previous versions, Stubs could not generate stubs for classes with no default constructor. This is no longer the case, Stubs will generate one public constructor for each public or protected base constructor.

Bug Fixes

Various code generation tweaks to make StyleCop happier
Visual Studio addin crashes when loading in VS2010
Visual Studio addin does not find attributes when they are globally qualified
Added missing substitutions for System.Threading.Interlocked members
Stubs automatically imports missing references
When an object has an invariant method (from Code Contracts), Pex would emit assertions using the private fields
Editorial issues to patterns paper
Contracts no longer kill the process when the runtime rewriter was not executed (.net 4.0)
Fixed bug in generic type guesser
Fixed samples for the latest version of Stubs

As always, don’t hesitate to send us your feedback, good or bad, through our MSDN forums.

Specifying Inversion of Control through Contracts for Interfaces

Jonathan de Halleux — Wed, 03 Jun 2009 00:14:03 GMT

Inversion of Control (IoC) is a very important practice to make code testable. It usually relies on defining interfaces for each external dependency. Various frameworks and techniques, i.e. Dependency Injection (DI), Service Locator, exist to bind the interface implementations to the components. In this blog post, we will *not* focus on this aspects of IoC but rather on it’s main building block: interfaces. This article describes how Contracts for interfaces improves IoC… regardless of which DI framework/technique you are using. The Contracts for interfaces are a feature of the Code Contracts for .Net tool.

Interfaces are not Contracts

Interfaces are often referred to as Contracts in the context of IoC: they define the methods and properties that a service should implement and are a key factor in achieving the loose coupling: one can build the code against the interface and can plug in various implementation with no risks.

Unfortunately, interfaces are not contracts: while they specify how the methods signatures should be, interfaces do not specify the functional behavior. To illustrate this, let’s take a look at a well-known simple interface of the BCL:

For this interface, I could naively implement as follows:

While my implementation is really really wrong, it fulfills all requirements of the IServiceProvider interface: a method GetService that returns object. Of course, if I would have read the MSDN documentation of GetService, I would have known that object should implement serviceType. Unfortunately, the interface did not tell me anything about that and compilers don’t understand MSDN documentation either.

Contracts for interfaces

Code Contracts provides an API for design-by-contracts (pre-condition, post-condition, etc…). It also supports defining contracts for interface or abstract classes. Contracts for interfaces can be used to specify the functional behavior of interface members. While they also serve as documentation, those contracts can also be turned into runtime checks or leveraged by static checkers.

since interface members cannot have method bodies, the contracts are stored in a ‘buddy’ type.
The [ContractClass]/[ContractClassFor] attributes bind the interface type and the contract type together.
Contract.Result<object>() is a helper method to refer to the result value, since this is not supported in C#.

Let’s take a closer look at the body of IServiceProviderContract.GetService. It contains a pre-condition (Requires) that the serviceType should not be null and a post-condition (Ensures) that the return value should be null or should be assignable to the serviceType:

In this simple case, the contracts captured precisely the specification that we found in MSDN. The critical difference is that they are stored in a format that compilers and runtimes know pretty well: MSIL byte code. The benefits are huge:

documentation: the contracts are stored in a programming-language agnostic format that mined and rendered for your favorite programming language,
static checking: static analysis tools can (and will) use contract to try to find bugs before you execute the code, or prove that it is correct with respect to the contracts,
runtime checking: the runtime checker will instrument all implementations of the interface with the interface contracts automatically. Once you’ve specified how an interface should behave, you do not have to repeat yourself when re-implementing it, the re-writer takes care of that.
automated white box testing: tools like Pex can leverage the runtime contract checks to try to find inputs that violate the contracts.
IoC/DI framework agnostic: It does not matter which DI framework you use, as soon as you use interface, you could also provide contracts for it.

Taming the Pex beast: Well-behaved enums, multi-dimensional arrays and booleans

Jonathan de Halleux — Fri, 29 May 2009 00:06:06 GMT

We’ve just released the Pex 0.13.40528.2 (Nikolai has all the details about the new features). In this release, a number of attributes were added to force Pex produce more friendly inputs.

The problem with Enums

When you apply Pex to code that uses Enumerations, you quickly learn something: the CLR does not constraints the enumeration values to be defined. This means than whenever you take an Enum as a parameter, you should validate it is properly defined:

void Test(SomeEnum e) {
if (!Enum.IsDefined(typeof(SomeEnum), e)) throw new ArgumentException(“…”);
}

Look at the BCL code, they actually do this kind of validation. For good or bad, some of our users have been complaining that Pex should restrict the enumeration to defined values, in fact considering the generated failing test case as noise. To restrict generated enumartion values to be defined, you can add the [PexEnumValuesDefined(typeof(SomeEnum))] attribute on your test/fixture/assembly. Internally, this attribute attaches an invariant to the given enumeration type that tells Z3 the allowed values for that type.

What about multi-dimensional arrays?

Ever wakened a day wanting to iterate arrays starting from –12345? Well you can with multidimensional arrays… The Array.CreateInstance method has an overload that takes length and lower bounds to instantiate multidimensional arrays:

int[,] array = (int[,])Array.CreateInstance(typeof(int),
    new int[] {10, 10}, // lengths
    new int[] {–12345, – 789} // lower bounds
    );
a[-12345, –789] = –1;

Of course, this feels a bit weird because most languages won’t allow to create such arrays, but the Array.CreateInstance method is still available nonetheless. It feels a bit weird but this behavior is perfectly valid from the runtime point of view. To restrict Pex from generating such bounds, you can add the [PexZeroMdArrayLowerBounds(0)] attribute (one attribute per dimension).

What about Booleans?

Booleans is another interesting citizen of the CLR. At the MSIL level, the Boolean type is really a byte, widened as an integer when on the stack. Compilers try really hard to keep Booleans as 0 or 1 but… it is possible to craft Boolean values anywhere the byte range using safe MSIL code (not from C# though or any BCL method I know of). The implication of this are quite disturbing, for example, consider the following parameterized test:

[PexMethod] {
void BooleanMadness(bool a, bool b) {
if (a && b && a != b)
throw new Exception(“this is madness!”);
}

Clearly, in a word of Booleans constrained to 0 or 1, the branch that throws the exception should be unreachable. If you execute Pex on this test, it will generate 4 test one of which raises the exception:

Notice the actual values (0x02, 0x03) of the Booleans in the pretty printing. If you want Pex to generate Boolean that are restricted to 0 or 1, use the [PexBooleanAsZeroOrOne] attribute. This attribute forces Z3 to pick boolean values as 0 or 1. Btw, there’s already a connect bug for this behavior.

Presenting Pex to your co-workers? Use our slide decks…

Jonathan de Halleux — Tue, 26 May 2009 05:54:47 GMT

If you’ve been thinking about presenting Pex to your co-workers or your local .NET community, you can use our slide decks at http://research.microsoft.com/en-us/projects/pex/documentation.aspx . The slide decks are there to help you, don’t hesitate to shuffle them, cut them or pick whatever you need in them (and of course, tell us about it).

Cheers, Peli.

Blogging about Pex, let us know!

Jonathan de Halleux — Wed, 20 May 2009 14:26:22 GMT

If you are (or you've been) blogging about Pex, let us know and drop the link in this following forum thread:

http://social.msdn.microsoft.com/Forums/en-US/pex/thread/7e6c26df-ccfb-48a4-878d-b3b01f5ba8d5

We are building a list of links that will be hosted our project web site.

find me at http://twitter.com/pelikhan

Jonathan de Halleux — Sat, 16 May 2009 13:06:55 GMT

Not sure what’s going to come up at of this but you can find me on twitter at http://twitter.com/pelikhan.

Stubs as Parameterized Models with Contracts

Jonathan de Halleux — Sat, 02 May 2009 17:19:16 GMT

This is a cool new feature that builds on Stubs, Pex and Code Contracts (in fact, it is really just a consequence of the interaction of the 3 technologies): stubs that act as parameterized models while complying to the interface contracts.

Code Contracts provide contracts for interfaces. All implementations of that particular interface will be instrumented with the runtime checks by the rewriter at compile time.
Stubs is really just a code generator that provides a minimal implementation of interfaces and relies on the C# compiler to build the code. Therefore, if a stub implements an interface with contracts, it will automatically be instrumented by the runtime rewriter as well.
Pex choices (i.e. dynamic parameter generation) may be used as the fallback behavior of stubs. In other words, whenever a stubbed method without user-defined behavior is called, Pex gets to pick the return value. Since the stub implementation itself may have been instrumented with contracts, we’ve added special handling code so that post-condition violation coming from a stub are considered as an assumption. This effectively forces Pex to generate values that comply with the interface contracts.

Let’s see how this works with an example. The IFoo interface contains a single ‘GetName’ method. This method has one precondition, i should be positive and one postcondition, the result is non null. Since interfaces cannot have a method body, we use a ‘buddy’ class to express those contracts and bind both classes using the [ContractClass] and [ContractClassFor] attributes:

We then turn on runtime rewriting for both the project under test and the test project (Project properties –> Code Contracts –> Runtime checks). As a result, the stub of IFoo automatically gets instrumented with the contracts. We can clearly see that from the generated code of GetName in Reflector below:

The last step is to write a test for IFoo. In this case, we write a parameterized unit test that takes an IFoo instance and an integer, then simply call GetName.

Since the contracts of IFoo.GetName specifies that the result should not be null, we should not see any assertion violation in this test. Moreover, we should see a test for the precondition considered as an expected exception:

Note that all those behaviors rely on extensions to Pex that the wizard automatically inserted in the PexAssemblyInfo.cs file:

where

[PexAssumeContractEnsuresFailureAtStubSurface] filters post-condition violations in stubs as assumptions,
[PexChooseAsStubFallbackBehavior] installs Pex choices as the fallback behavior of stubs,
[PexStubsPackage] load the stubs package (this is a standard procedure for Pex packages),
[PexUseStubsFromTestAssembly] specifies to Pex that it should considers stub types when trying to test interfaces or abstract classes.

Pex 0.12.40430.3 : Exploration Tree View, Partial Stubs…

Jonathan de Halleux — Fri, 01 May 2009 20:28:25 GMT

We just made a quick release to fix another installer issue related to missing packages. Along the way, we’ve added an Exploration Tree View and Partial Stubs support.

Exploration Tree View

The exploration tree view displays the list of explorations to be executed, running and finished. It serves as a progress indicator but also as a smooth result explorer. When browsing through the tree, Pex will synchronize the exploration result view and the tree view.

The tree view populates each namespace with the fixture types and exploration methods, and provide a visual feedback on the progress of Pex.

When you browse through the exploration and generated test nodes, Pex automatically synchronizes the exploration result display. This makes it really easy to start from an high-level view of the failures and drill into a particular generated test, with stack trace and parameter table.

Partial Stubs

Stubs lets you call the base class implementation of methods as a fallback behavior. This functionality is commonly referred as Partial Mocks or Partial Stubs and is useful to test abstract classes in isolation. Stubs inheriting from classes have a “CallBase” property that can turn this mode on and off.

Let see this with the RhinoMocks example on partial mocks. Given an abstract ProcessorBase class,

we write a test for the Inc method. To do so, we provide a stub implementation of Add that simply increment a counter.

Miscellaneous

PexAssume/PexAssert.EnumIsDefine checks that a particular value is defined in an enum.
Missing OpenMP files in the installer break Pex.

Poll: should we skip 0.13 and go straight for 0.14? :)

Design By Contracts meets Automated White box Testing

Jonathan de Halleux — Sun, 26 Apr 2009 04:09:57 GMT

I recorded a Channel9 video last week with Manuel Fahndrich on the interaction of Code Contracts and Pex. The demo gives a glimpse at the nice interaction between Contracts (design by contracts) and Pex (automated white box).

Code Contracts gives you a great way to specify what your code is supposed to do. These contracts can be leverage for documentation, static checkers but also – tada – by Pex! Contracts can also be turned into runtime checks which Pex will try to explore. Pex will try to cover the post conditions, assertions or in other words, find inputs that violates of your contracts etc… By adding contracts to your code, you give Pex a ‘direction’ to search for (and a test oracle).

Drop me a note if you want more of those movies.

Stubs: Comparison with other mocking frameworks

Jonathan de Halleux — Thu, 23 Apr 2009 04:58:03 GMT

Update: Andrew Kazyrevich does the final performance analysis on his blog.
Update II: Stubs v0.12.40430.3 has Partial Stubs support.

Stubs is a lightweight stub framework that is entirely based on delegates. We designed it so that it brings as little overhead as possible, and as a side effect, is very effective with Pex. In this post, we’ll see how Stubs ‘look’ with respect to other frameworks.

Mocking-framework-compare

Andrew Kazyrevich started a project, mocking-framework-compare, back in February that compared Moq, Rhino, NMock2 and Isolator. This is project compares various ‘mocking scenarios’ across all those frameworks. I added Stubs to the mix today (go check it out).

What’s a stub in Stubs anyway?

Before we dig in, let’s recap how stubs look like when you use Stubs. Stubs uses delegate to ‘hook’ behavior to interface members. For every stubbed interface and class, code is generated at a compile time: One stub class per interface and class. For each stubbed method, the stub class contains a field. The field has a delegate type matching the stubbed method. As a user, you can simply attach delegates (or lambdas) to the delegate fields to assign*any* behavior to each member. If no user delegate is set, Stubs calls into a fallback behavior, i.e. throw or return the default value.

Let’s take one of the examples of mocking-framework-compare. The little snippet below ‘stubs’ the TouchIron() method (which is implemented explicitly) by attaching a lambda to the TouchIron field.

SIHand is the stub type of the IHand interface, it was generated at compile time by the Stubs framework. Its implementation looks more or less like this:

The TouchIron methods really shows the main idea behind stubs: delegates are all we need to move behavior around.

Stubs: relying on the language rather than an API

One of the differences of Stubs with other mock frameworks is that Stubs does not have any API: delegates, lambdas, closures are all features of the programming language, while assertions are part of the test framework. This is quite obvious when we compare the BrainTest using Moq and using Stubs. In this test, we need to ensure that the brain coordinates the hand and the mouth so that when a hot iron is touched by the hand, the mouth yells.

Moq: we set up the hand to throw a burn exception when touched with a hot iron and verify that the mouth yelled.

Moq, as Rhino or Isolate, make smart use of expression trees and/or Reflection.Emit to define the mock behavior. The expectation and behavior are set through nice and fluent APIs which really make the developer’s life’s easier.

Stubs: same scenario, we attach a lambda that throws if iron is hot and use a local to verify that Yell is called (this local is pushed to the heap by the compiler).

Stubs does not have any API. It relies on lambdas (to define new behaviors), closures (to track side effects) which are given for free by the C# 3.0 language.

Performance numbers

Does performance matter when it comes to mocking? It’s not really the question we are trying to answer here. We’re just looking at the benchmark results from the mocking-framework-compare project. When looking at the results, you’ll notice that Stubs may be 100x to 1000x faster than other frameworks. This is no surprise since stubs boil down to a virtual method call, while other frameworks do much more work (in fact we expected worse numbers).

Data units of msec resolution = 0.394937 usec

Mocking methods.
Moq      : 100 repeats: 37.471 +- 12%   msec
Rhino    : 100 repeats: 38.030 +- 7%    msec
NMock2   : 100 repeats: 24.035 +- 4%    msec
Stubs    : 100 repeats:   0.115 +- 8%    msec

Mocking events.
Moq      : 100 repeats: 86.913 +- 7%    msec
Rhino    : 100 repeats: 61.142 +- 6%    msec
NMock2   : 100 repeats: 27.378 +- 6%    msec
Stubs    : 100 repeats:   0.071 +- 6%    msec

Mocking properties.
Moq      : 100 repeats: 82.434 +- 6%    msec
Rhino    : 100 repeats: 47.471 +- 5%    msec
NMock2   : 100 repeats: 11.334 +- 10%   msec
Stubs    : 100 repeats:   0.042 +- 15%   msec

Mocking method arguments.
Moq      : 100 repeats: 142.668 +- 4%    msec
Rhino    : 100 repeats: 45.118 +- 5%    msec
NMock2   : 100 repeats: 22.344 +- 7%    msec
Stubs    : 100 repeats:   0.078 +- 4%    msec

Partial mocks.
Moq      : 100 repeats: 117.581 +- 5%    msec
Rhino    : 100 repeats: 58.827 +- 6%    msec
Stubs : 100 repeats:   0.054 +- 6%    msec

Recursive mocks.
Moq      : 100 repeats: 92.482 +- 4%    msec
Rhino    : 100 repeats: 40.921 +- 3%    msec
Stubs    : 100 repeats:   0.493 +- 18%   msec
Press any key to continue . . .

Stubs limitations

There are many areas where the Stubs fall short or simply don’t support it. Currently, Stubs are only emitted for C# and partial mocks will be supported in the next version.

Getting started with Stubs

Stubs comes with the Pex installer. If you’re interested on using it, check out the getting started page on the Stubs project page where you can also download the full Stubs primer.

Cheers, Peli

Pex v0.11.40421.0 : Delegates As Parameters, Exception Tree View, Better Stubs.

Jonathan de Halleux — Wed, 22 Apr 2009 00:10:17 GMT

Nikolai just announced the latest drop of Pex, 0.11.40421.0. Get all the details on his blog.

Read, morph, tweak, write MSIL with CCI (open source)

Jonathan de Halleux — Thu, 16 Apr 2009 03:51:23 GMT

For the last couple of weeks, I given on helping hand to Herman Venter to set up the open-source-MS-PL-super-cool-Common Compiler Infrastructure (CCI) project.

You’ve may have heard and probably used different incarnations of the CCI in the past: the FxCop introspection engine, ILMerge, Spec# or Code Contracts use CCI in same ways. CCI is a set of tools and components that are useful to build compilers: readers and writers for MSIL and symbol files, and more. With CCI, you can now easily write your own crazy aspect oriented programming framework, inspect assemblies without reflection etc… Just sync the sources, build it, tweak it, etc… It’s all there on codeplex at http://ccimetadata.codeplex.com.

Pex v0.10.40408.0: NUnit, MbUnit, xUnit.Net, Visual Basic.NET, F# and more…

Jonathan de Halleux — Fri, 10 Apr 2009 19:06:31 GMT

Download the new version!

Today we’ve released a new release of Pex on DevLabs and on our academic downloads. This highlights of this release are: NUnit, MbUnit and xUnit.net support out of the box, writing parameterized unit tests in VisualBasic.NET and F#, better Code Contracts support. As always, if we encourage you to send us feedback, bugs, stories on our forums at http://social.msdn.microsoft.com/Forums/en-US/pex/threads/ .

NUnit, MbUnit and xUnit.net supported out of the box

Pex now supports MSTest, NUnit, MbUnit and xUnit.net out of the box. Pex will automatically detect which framework you are using by inspecting the assembly reference list, and automatically save the generated tests decorated with the correct attributes for that framework.

The default test framework can also be specified through the global options (Tools –> Options –> Pex –> enter the test framework name in TestFramework).

Writing Parameterized Unit Tests in VisualBasic.NET

While the Pex white box analysis engine works at the MSIL level, Pex only emits C# code for now. In previous releases, this limitation made it impossible to use Pex parameterized unit tests from non-C# code. In this release, we have worked around this problem by automatically saving the generated tests in a ‘satellite’ C# project.

Let’s see this with an example. The screenshot below shows a single VisualBasic.NET test project with a Pex parameterized unit test:

We can right-click in the HelloTest.Hello method and select “Run Pex Explorations”:

At this point, Pex will start exploring the test in the background as usual. This is where the new support comes in: When a generated test comes back to Visual Studio, Pex will save it in a separate C# project automatically (after asking you where to drop the new project):

The generated tests are now ready to be run just as any other unit tests!

Writing Parameterized Unit Tests from F#

Similarly to VisualBasic.NET, we’ve made improvements in our infrastructure to enable writing parameterized unit tests in F#. Let’s see this with a familiar example. We have a single F# library that has xUnit.net unit tests and reference Microsoft.Pex.Framework (project Library2 below). In that project, we add a parameterized unit test (hello_test):

We can right-click on the test method name and Pex will start the exploration of that test in the background. Because of the limitations of the F# project system, you absolutely need to right-click on the method name in F# if you want contextual test selection to work. Because the project is already referencing xunit.dll, Pex will also automatically detect that you are using xUnit.net and use that framework. When the first test case comes back to VisualStudio, Pex saves it in a separate C# project:

The tests are saved in the generated test project and ready to be run by your favorite test runner!

PexObserve: Observing values, Asserting values

We’ve completely re-factored the way values can be logged on the table or saved as assertions in the generated tests. The following example shows various ways to log and assert values:

In the Observe method, we use the return value and out parameter output to automatically log and assert those values. Additionally, we add “view input” on the fly to the parameter table through the ValueForViewing method, and we add “check input” to be asserted through the ValueAtEndOfTest method. After running Pex, we get the following results:

As expected, input, ‘view input’, output and result show up in the parameter table.

In the generated test, we see assertions for the return value, out parameters and other values passed through the ValueAtEndOfTest method.

Code Contracts : Reproducible generated tests

When Pex generates a unit test that relied on a runtime contract, Pex also adds a check to the unit test which validates that the contracts have been injected into the code by the contracts rewriter. If the code is not rewritten when re-executing the unit test, it is marked as inconclusive. You will appreciate this behavior when you run your unit tests both in Release and in Debug builds, which usually differ in how contracts get injected.

Code Contracts: Automatic filtering of the contract violations

When Pex generates a test that violates a Code Contract pre-condition (i.e. Contract.Requires), there are basically two scenarios: the precondition was on top of the stack and should be considered as an expected exception; or it is a nested exception and should be considered as a bug. Pex provides a default exception filtering that implements this behavior.

Stubs: simplified syntax

We’ve considerably simplified the syntax of stubs by removing the ‘this’ parameter from the stub delegate definition. Let’s illustrate this with a test that stubs the ‘ReadAllText’ method of a fictitious ‘IFileSystem’ interface.

Stubs: generic methods

The Stubs framework now supports stubbing generic methods by providing particular instantiations of that method. In the following example, the generic Bar<T> method is stubbed for the particular Bar<int> instantiation:

Stubs and Pex: Pex will choose the stubs behavior by default

We provide a new custom attribute, PexChooseAsStubFallbackBehaviorAttribute, that hooks Pex choices to the Stub fallback behavior. To illustrate what this means, let’s modify slightly the example above by removing the stub of ReadAllText:

If this test was to be run without the PexChooseAsStubFallbackBehavior attribute, it would throw a StubNotImplementedException. However, with the PexChooseAsStubFallbackBehavior attribute, the fallback behavior calls into PexChoose to ask Pex for a new string. In this example in particular, on each call to ReadAllText, Pex will generate a new string for the result. You can see this string as a new parameter to the parameterized unit test. Therefore, when we run this test under Pex, we see different behavior happening, including the “hello world” file:

Note that all the necessary attributes are added at the assembly level by the Pex Wizard.

Miscellanous bug fixes and improvements

[fixed] Dialogs do not render correctly under high DPI
When a generic parameterized unit tests does not have any generic argument instantiations, Pex makes a guess for you.
When a test parameter is an interface or an abstract class, Pex now searches the known assemblies for implementations and concrete classes. In particular, that means that Pex will often automatically use the automatically generated Stubs implementations for interfaces or abstract classes.
Static parameterized unit tests are supported (if static tests are supported by your test framework)
Better solving of decimal and floating point constraints. We will report on the details later.

Breaking Changes

The PexFactoryClassAttribute is no longer needed and has been removed. Now, Pex will pick up object factory methods marked with the PexFactoryMethodAttribute from any static class in the test project containing the parameterized unit tests. If the generated tests are stored in a separate project, that project is not searched.
The PexStore API has been renamed to PexObserve.
Pex is compatible with Code Contracts versions strictly newer than v1.1.20309.13. Unfortunately, v1.1.20309.13 is the currently available version of Code Contracts. The Code Contracts team is planning on a release soon.

Happy Pexing!

QuickGraph for Silverlight (new release)

Jonathan de Halleux — Thu, 09 Apr 2009 12:29:58 GMT

I just released a new version of QuickGraph for Silverlight on http://quickgraph.codeplex.com . You can grad it to run your favorite graph algorithm in the silverlight browser!

TechDays Videos and Baltic Sea Swimming

Jonathan de Halleux — Fri, 20 Mar 2009 00:28:22 GMT

The videos of TechDays are up:

While attending TechDays Finland in Helsinki, I had the opportunity (thanks Vesa) to take a swim in the baltic frozen sea along with fellow Microsoftie Scott Galloway (i’ll spare you the video of the actual bath).

Great way to dust off the remaining of jetlag.

ps: Yes we are standing on the sea.

Moq 3.0 gets Pex friendly

Jonathan de Halleux — Sat, 07 Mar 2009 03:15:27 GMT

The next version of Moq 3.0 will work better for Pex:

http://www.clariusconsulting.net/blogs/kzu/archive/2009/03/05/120009.aspx

In the past, Pex would analyze the Moq ‘engine’ code and spend a large amount of time trying to understand the internals of that framework. In this release, Daniel has added special annotations (see extension writer Handbook) that shut down the Pex monitoring for certain areas of Moq which don’t matter to analyse the code under test.

QuickGraph on Code Contracts

Jonathan de Halleux — Sat, 28 Feb 2009 16:33:15 GMT

Ealier this week, we released the Code Contracts library for .NET. Since then, I’ve implemented a lot for contracts for the data structures in QuickGraph . In this post, I’ll talk about my experience with the contracts…

Walking through some contracts.

Let’s take a look at the contracts of AddEdge, a method that adds an edge to a graph. Adding an edge to a graph is certainly a fun adventure, when you write contracts for it. Let’s take a look:

public interface IMutableEdgeListGraph<TVertex,
TEdge> : ... where TEdge : IEdge<TVertex>
{ /// <summary> /// Adds
the edge to the graph /// </summary> /// <param
name="edge"></param> /// <returns>true
if the edge was added, otherwise false.</returns> bool AddEdge(TEdge
edge);

Interface contracts

Since IMutableEdgeListGraph is an interface, we need to store the contracts in separate class. To do so, we ‘bind’ the interface and the contract class to each other using the ContractClassForAttribute/ContractClassAttribute.

    [ContractClass(typeof(IMutableEdgeListGraphContract<,>))]  public
interface IMutableEdgeListGraph<TVertex,
TEdge> ...

    [ContractClassFor(typeof(IMutableEdgeListGraph<,>))]  sealed
class IMutableEdgeListGraphContract<TVertex,
TEdge> : IMutableEdgeListGraph<TVertex,
TEdge> where TEdge : IEdge<TVertex>

Once both types are bound, you can start implementing the contracts of the interface in the contract class. Note that the contract class must use explicit interface implementations for all methods.

Basic null checks

If you care about null references, the first contract will probably to ensure the edge is not null. To make it quick and painless, make sure you use the crn snippet. Note that since the method body of the contracts does not matter, we simply return the default value.

bool IMutableEdgeListGraph<TVertex,
TEdge>.AddEdge(TEdge e) {  Contract.Requires(e
!= null); return default(bool); }

More pre-conditions

One of the implicit requirement of AddEdge is that both vertices should already belong to the graph. We want to make this explicit as a pre-condition as well:

bool IMutableEdgeListGraph<TVertex,
TEdge>.AddEdge(TEdge e) { IMutableEdgeListGraph<TVertex,
TEdge> ithis = this; Contract.Requires(e
!= null);  Contract.Requires(ithis.ContainsVertex(e.Source)); Contract.Requires(ithis.ContainsVertex(e.Target));

There are two things to notice here: (1) we had to cast the “this” pointer to the interface we are writing contracts for, IMutableEdgeListGraph<,>. Because the methods in a contract class must be explicit interface implementations, we do not have access to the members of this interface from the “this” pointer, (2) ContainsVertex had to be annotated with [Pure], as any method called from a contract must be pure:

[Pure] bool ContainsVertex(TVertex
vertex);

What about post-conditions

One of my favorite feature of Code Contracts is to be able to state post-conditions. This is done by calling the Contracts.Ensures method. For example, we start by expressing that the edge must belong to the graph when we leave AddEdge:

bool IMutableEdgeListGraph<TVertex,
TEdge>.AddEdge(TEdge e) { IMutableEdgeListGraph<TVertex,
TEdge> ithis = this;

... 


Contract.Ensures(ithis.ContainsEdge(e));

Result and Old

Since the method returns a boolean, we should also state something about the result value. To refer to the result, one has to use the Contract.Result<T>() method. In this case, the method returns true if the edge was new, false if it was already in the graph. We can refer to a pre-state, i.e. the value of this.Contains(e) at the beginning of the method***:

Contract.Ensures(Contract.Result<bool>() 


== Contract.OldValue(!ithis.ContainsEdge(e)));

Lastly, we can also make sure the edge count has been incremented, if an edge was actually added (as you can see, we could use an implication operator in C#):

Contract.Ensures(ithis.EdgeCount
== Contract.OldValue(ithis.EdgeCount) + (Contract.Result<bool>() ? 1 : 0));

*** The OldState value is evaluated after the preconditions.

Where to go next?

In the next post, I’ll show how to leverage these Contracts with Pex…

Pex Europe Tour March’09

Jonathan de Halleux — Wed, 18 Feb 2009 06:45:33 GMT

I’ll be travelling in Europe next month and presenting Pex, Code Contracts and CHESS in various events. Don’t forget to swing by, shake a hand and talk about geek stuff.

March 5-6: TechDays Finland, in Helsinki,
March 9: The Netherlands .NET user group, in Amsterdam,
March 10: London .NET user group, in London of course,
March 11-12: TechDays Belgium, in Antwerp,
March 13: Katholieke Universiteit Leuven, in Leuven

See you there!

Ben Hall on Pex – DDD7 Video Posted

Jonathan de Halleux — Tue, 03 Feb 2009 16:38:53 GMT

Ben presented a talk on Pex a couple months ago at DDD7. The video of the talk is now up on the web. Check it out!

CHESS 0.1 released on Devlabs: Finding and Reproducing Heisenbugs in Concurrent Programs

Jonathan de Halleux — Fri, 30 Jan 2009 20:52:08 GMT

A while ago at PDC, a couple of my colleagues presented CHESS but unfortunately weren’t ready to release it. Well, you don’t have to wait anymore: CHESS is now available for download at DevLabs for Visual Studio 2008 Team Dev or Team Test. CHESS comes under the same pre-release license as Pex or under an academic license.

CHESS = Unit Testing of Concurrent Programs

CHESS is a tool that finds and reproduces “Heisenbugs” in concurrent programs (both Win32 and .NET)… You know those kind of bugs that do not reproduce under the debugger or only in production environment, the kind of bugs where you scratch your head for days in front of a process dump before giving up.

I also recently recorded a great ‘getting started’ CHESS tutorial for CHESS in Visual Studio Unit Test: you can take a unit test*** and turn it into a CHESS test by adding the [HostType(“Chess”)] attribute!

*** That unit test should involve threads, otherwise CHESS will have not effect.

CHESS and Pex

In order to control the scheduling of .NET programs, CHESS instruments the threading APIs using ExtendedReflection, the code instrumentation framework that was built for Pex. In the future, we would also like to combine both approach to explore data inputs and thread schedules together.

Well enough said… go and try it out!

Reflector’s Review’s Review

Jonathan de Halleux — Tue, 27 Jan 2009 21:24:08 GMT

Ben Hall wrote a review of my Reflector Review addin. Nice tutorial on how to use this little helper.

The Review addin lets you annotate and comments any metadata inside of Reflector.

Named Formats Pex Testimonium

Jonathan de Halleux — Fri, 16 Jan 2009 00:38:25 GMT

Phil Haacked has started an interresting discussion on the implementation of a named formatter whose format strings are of the form {name} instead of {0}. In fact, he started with 3 implementations and his reader submitted 2 more! Since Phil was kind enough to package all the implementations (and the unit tests) in a solution, I took the liberty to run Pex on them and see if there was any issue lurking out. The goal of this post is not really to show that those implementation are correct or not, but give you an idea where Pex could be applicable in your code.

But wait, it’s already Unit Tested!

Indeed, Phil diligently wrote a unit test suite that covers many different use cases. Does it mean you are done with testing? The named format syntax can be tricky since may involve escaping curly braces… What is the named format syntax anyway? It’s pretty obvious that it should let you write something like “{Name} is {Status}” instead of “{0} is {1}” but that still pretty vague. In particular, what are the syntactic rules for escaping curly braces (what’s the meaning {{}{}{{}}}, etc…) or is there even a grammar describing named formats.

As it is often the case, there is no clear and definitive answer – at least I could not find it –. In this post, I’ll show 2 techniques that can be used here out of the many patterns for Pex which we documented.

Technique 1: Explore for runtime errors (pattern 2.12 – parameterized stub)

The most basic way of running Pex is to simply apply Pex on a method without adding any assertions. At this point, you are looking for NullReferenceException, IndexOutOfRanceException or other violations of lower level APIs. Although this kind of testing won’t help you answer whether your code is correct, it may give you back instances where it is wrong. For example, by passing any format and object into the format method in a parameterized unit test; the code below is a parameterized unit test for which Pex can generate relevant inputs:

[PexMethod] public
void HenriFormat(string format, object o)
{ format.HenriFormat(o); }

Note that it took a couple runs of Pex to figure the right set of assemblies to be instrumented. Hopefully, this process is mostly automated and you simply have to apply the changes that Pex suggests.

The screenshot below shows the input generated by Pex. Intuitively, I would think that FormatException is expected and part of properly rejecting invalid inputs. However, there are ArgumentOutOfRanceExceptions triggered inside of the DataBinder code that probably should intercepted earlier. If this implementation uses the DataBinder code, it should make sure that it only gets acceptable values. Whether those issues are worth fixing is a tricky question: maybe the programmer intended to let this behavior happen.

Technique 2: Compare different implementations (pattern 2.7 – same observable behavior)

A second approach is to compare the output of the different implementations. Since all the implementations implement the same (underspecified) named format specification, their behavior should match with respect to any input. This property makes it really easy to write really powerful parameterized unit tests. For example, the following test asserts that the Haacked and Hanselman implementation have the same observable behavior, i.e. return the same string or throw the same exception type (PexAssert.AreBehaviorEqual takes care of asserting this):

[PexMethod] public
void HaackVsHansel(string format, object o)
{ PexAssert.AreBehaviorsEqual( () => format.HaackFormat(o),
() => format.HanselFormat(o) ); }

Again, this kind of testing will not help to answer if the code is correct but it will give you instance where the different implementations behave differently, which means one of the two (or even both) have a bug. This is a great technique to test a new implementation against an old (fully tested) implementation which can be used as oracle. We run the test and Pex comes back with this list of test cases. For example, the format string “\0\0{{{{“ leads to different output for both implementation. From the different outputs, “\0\0{{“ vs “\0\0{{{{“, it seems that curly braces are escaped differently. If I wanted to dig deeper, I could also simply debug the generated test case.

Comparing All Implementations

Now that we’ve seen that Phil and Scott were not agreeing, could we apply this to the other formatters. I quickly set up a T4 template to generate the code for all the parameterized unit tests between each formatters. Note that order matters for Pex: calling A then B might lead to a different test suite compared to B then A, just because Pex explores the code in different orders.

<#@ template language="C#" #>

<# string[] formatters = new string[] {
        "Hansel",
        "Henri",
        "James",
        "Oskar",
        "Haack"
    };
#>
using System; using Microsoft.Pex.Framework; using Microsoft.Pex.Framework.Validation;
using Microsoft.VisualStudio.TestTools.UnitTesting; using UnitTests; using StringLib;
namespace UnitTests { [TestClass] [PexClass(MaxConstraintSolverTime = 2, MaxRunsWithoutNewTests
= 200)] public partial class StringFormatterTestsTest { 
<# foreach(string left in formatters) { 
           foreach(string right in formatters) {
               if (left == right) continue;    
        #><#= left #><#= right #><#= left #><#= right #>
[PexMethod] public void Vs(string format, object o) { PexAssert.AreBehaviorsEqual(
() => format.Format(o), () => format.Format(o) ); } 
<#
           } 
        } #>
} }

The answer that Pex returns is interresting and scary: none of the implementation behaviors match. This is somewhat not surprising since they all use radically different approaches to solve this problem: regex vs string api etc…

Try it for yourself.

The full modified source is available for download here. You will need to install Pex from http://research.microsoft.com/pex/downloads.aspx to re-execute the parameterized unit tests.

Pex 0.9 released: Pre-Release license for VS2008, better Test Framework integration and partial support for Visual Basic.NET/F#.

Jonathan de Halleux — Wed, 14 Jan 2009 20:21:29 GMT

Today, we released the 0.9.40105.0 version of Pex. The major highlights of this release are: Pre-Release license for Visual Studio 2008, better test framework integration and partial support for Visual Basic.NET/F# (read the full release notes).

CHESS, another project from RiSE, also released it’s first public download today. CHESS finds and reproduces heisenbugs in concurrent programs. CHESS uses the Pex code instrumentation technology to monitor and control the .Net threading APIs, and one day we hope to combine Pex and CHESS…

Enjoy and don’t forget to give us your feedback through the MSDN forums.

Introduction to the Stubs Framework

Jonathan de Halleux — Sat, 10 Jan 2009 15:41:32 GMT

Stubs is a framework for generating stubs (that we announced earlier with Pex). The framework generates stubs (not mocks) that are

lightweight, i.e. relying on delegates only,
strongly typed, i.e. no magic strings – refactoring friendly,
source code generated, i.e. no dynamic code or expression trees,
great debugging experience, i.e. break and step through stubs,
minimalistic API (there is almost none),
friendly for Pex!

More details about Stubs are also available in the stubs reference document.

Quick Start

Let’s start from a simple interface IFileSystem for which we want to write stubs:

public interface IFileSystem { void WriteAllText(string fileName, string content); string ReadAllText(string fileName);
}

Stubs relies solely on delegates to attach behaviors, and leverages the lambda syntax from C# 3.0 to accomplish pretty much anything:

// SFileSystem was generated
by Stubs and stubs IFileSystem var stub = new SFileSystem(); //
always returns “...” stub.ReadAllText = (me, file) => "..."; //
expectations: checks file = “foo.txt” stub.ReadAllText = (me, file) => { Assert.AreEqual("foo.txt",
file); return "...";
}; // storing side effects in closures: written saves
content string written = null;
stub.WriteAllText = (me, file, content) => written = content; //
hey, we can do whatever we want! stub.ReadAllText = (me, file) => { if (file
== null) throw new ArgumentNullException(); return "...";
};

// downcast to the interface to use
it IFileSystem fs = stubs;

Anything is possible… as long as C# (or your favorite language) allows it.

Anatomy of a Stub

Each stubbed method has an associated field delegate that can be set freely (e.g. WriteAllText and ReadAllText). If this delegate field is set, it will used when the method is called; otherwize a default action occurs. Let’s see this with a simplified stub of the IFileSystem interface, SFileSystem, which shows how the IFileSystem.WriteAllText is implemented:

class SFileSystem : StubBase<SFileSystem>>
, IFileSystem { public Action<SFileSystem>, string, string>
WriteAllText; // attach here void IFileSystem.WriteAllText(string fileName, string content)
{ var stub = this.WriteAllText; if (stub
!= null) stub(this,
fileName, content); // your code executed here else this.DefaultStub.VoidResult(this);
} }

The actual generated code may look more complicated because it contains custom attributes for debugging, comments and globally qualified types to avoid name clashing:

Code generation: How does it work?

Stubs is a single file generator that pre-generates stubs to source code. Stubs also monitors the build and regenerates the source code when a change occurs.

The stub generation is configured through an XML file (.stubx file) that contains which code and how it should be generated. The generated code is saved in a ‘Designer’ file, similarly to other code generation tools (type dataset etc…).

Great debugging experience

A cool side effect of simply using delegates: you can step through and debug your stubs! This is usually not the case with mock framework using dynamic code. Below, you can see that one can set breakpoints in the body of a stub and debug as usual.

Where do I get it?

The Stubs framework comes with Pex but you can use it in any unit testing activity. It provides a simple lightweight alternative to define stub for testing. Pex can be downloaded from http://research.microsoft.com/pex .

Tarjan Offline Least Common Ancestor in C# (with QuickGraph)

Jonathan de Halleux — Thu, 08 Jan 2009 08:32:54 GMT

Following the implementation of the disjointset, another fun algorithm to implement was the offline least common ancestor problem. Tarjan proposed a algorithm based on the disjoint-set and a DFS traversal. Given that I now have all those ingredients in QuickGraph, it was just a matter of hooking together the implementation with the right events. The beef of the implementation looks as follows (and looks quite elegant to me):

var gpair = GraphExtensions.ToAdjacencyGraph(this.pairs);
// for fast lookup var disjointSet = new ForestDisjointSet

(); var vancestors = new Dictionary(); var dfs
= new DepthFirstSearchAlgorithm(this, this.VisitedGraph, new DictionaryGraphColor>>(this.VisitedGraph.VertexCount));
dfs.InitializeVertex += (sender, args) => disjointSet.MakeSet(args.Vertex); dfs.DiscoverVertex
+= (sender, args) => vancestors[args.Vertex] = args.Vertex; dfs.TreeEdge += (sender,
args) => { var edge = args.Edge; disjointSet.Union(edge.Source,
edge.Target); vancestors[disjointSet.FindSet(edge.Source)] = edge.Source; }; dfs.FinishVertex
+= (sender, args) => { foreach (var e in gpair.OutEdges(args.Vertex)) if (dfs.VertexColors[e.Target]
== GraphColor.Black) this.ancestors[EdgeExtensions.ToVertexPair(e)]
= vancestors[disjointSet.FindSet(e.Target)]; }; // go! dfs.Compute(root);

Enjoy!

A K-Shortest Path implementation in .Net

Jonathan de Halleux — Mon, 05 Jan 2009 07:05:14 GMT

The k-shortest paths computes the k first shortest path between two vertices in a directed graph. If you put this in the context of route planning, it gives you k alternative routes in case the shortest path is blocked by snow :) While the single source shortest path is well-known and implemented in many languages, there are not many implementations available for this problem, although it has been extensively studied. After looking around, I stumbled on a nice article comparing various approaches. The authors pointed out an algorithm from 1959 from Hoffman and Pavley that solved this problem (there are actually many others). This algorithm looked like a good fit:

it requires a single call to a single-source shortest path algorithm. Other approaches will require as much as kn calls to a shortest path algorithm.
it sounded simple and did not require new specialized data structures.

I want to try it!

The algorithm is available in QuickGraph 3.1.40104.00 and up. You can take a look at it at http://www.codeplex.com/quickgraph/SourceControl/changeset/view/29858#377982. To use it on a BidirectionalGraph,

IBidirectionalGraph<TVertex, TEdge> g = …;
foreach(IEnumerable<TEdge> path in g.RankedShortestPathHoffmanPavley(weights, source, goal, 4))
…

A glimpse at the Hoffmann-Pavley algorithm

The algorithm works in 2 phases.

On the first phase, we build a minimum ‘successor’ tree towards the goal vertex. This tree can be used to build a shortest path from any (reachable) vertex to the goal vertex. To build this tree, we can simply apply the Dijkstra shortest path algorithm on the reversed graph. This can be done in a couple lines with QuickGraph.

As for many other k-shortest path algorithm, phase works by building deviation path and picking the best one. In the case of the Hoffman-Pavley algorithm, it works as follows: pick the latest shortest path, for each vertex of this path, build a deviation path (more later) for each out-edge and add it to a priority queue. Then start again:

var queue = new PriorityQueue<Path>();
queue.Enqueue(shortestpath);
while(queue.Count > 0) {
    var path = queue.Dequeue();
    foreach(var vertex in path)
        foreach(var edge in graph.OutEdges(vertex))
             queue.Enqueue(CreateDeviation(path, vertex, edge));
}

A deviation path is composed of three parts:

the initial part of the ‘seeding’ path, i.e. the edges before the deviation edge,
the deviation edge
the remaining shortest path to the goal. When we build the deviation path, we also compute it’s weight. A nice property of the deviation paths is that they can be ‘built’ when needed. This saves a lot of space and computation as most deviation paths will probably not end up in the winning set of paths – instead of storing a full path, we store a path index and an edge index.

That’s it! The details contain more code to deal with self-edges and loops but the main idea is there. This is definitely a very elegant algorithm!

What about testing!

Algorithm authors usually illustrate their approach with an example. This is a good way to get started on a small graph example and ensure that the algorithm works as the original author expected. This is the kind of unit test I get started with.

The next step is to apply the algorithm to a large number of graph instances. Unfortunately, I do not have any other k-shortest path algorithm, so the oracle is harder to build here. Nevertheless, the result of the algorithm, i.e. the shortest path collection, has a couple of properties that should always be true:

the algorithm produces loopless paths,
path k is lower or equal to path k + 1.

The problem with this test is that it does not guarantee that some shortest path have been missed. At this point, I’m a bit puzzled on how to test that.

Testing Graph Algorithms With Optimal Solutions

Jonathan de Halleux — Thu, 01 Jan 2009 17:03:14 GMT

When you implement an algorithm that computes an optimal solution (i.e. minimum/maximum with respect to a cost function), how do you test that the solution is actually optimal?

This is the kind of question I face when implementing algorithms in QuickGraph. For example, I was recently looking at the minimum spanning tree of a graph (MST)? While checking that the result tree is a spanning tree is easy, checking that it is minimum is not obvious: nobody has written Assert.IsMinimum yet :). Here are a couple techniques that I found useful along the way:

Input-Output table

The most obvious approach is to pre-compute the result for a number of problems and assert the solution of the algorithm matches. In this MST case, use a small set of graphs for which the MST is well known, and check that the computed MST has the correct weight. This approach will take you only so far and requires a lot of manual work since you need to solve the problem (or find a known solution) for a number of representative cases.

Solution Perturbation

If the algorithm computes a solution that is minimal with respect to a cost function, one can try to perturbate the solution to see if there’s a smaller one. If so, it clearly violates the fact that the solution should be minimal, thus you just found a bug. In the case of MST, this would mean randomly picking edges that are not in the minimum spanning tree, swapping them and evaluate if the result tree is smaller.

This is kind of approach is actually used in optimization where the search space might have local minima (see simulated annealing).

Multiple Implementations

A nice thing about graph problems is that there are usually many (vastly) different ways to solve them. If multiple implementations are available, we can simply compare the result of each algorithm against each other and make sure that they match each other. Each algorithm might have bugs but it is unlikely that they share common ones. Since we have now a good oracle, we can apply this approach that a large number of inputs to increase our coverage.

In the MST case, two popular algorithms are Prim’s and Kruskal’s. Those are 2 different approaches: Prim is built on top of Dijkstra single source shortest path, while Kruskal is built on top of the disjoint-set data structure. By carefully picking the weights of the edges, we can assert different things:

if the edge weights are all equals, any spanning tree is minimal. So we can compare the result to a depth-first-search algorithm (which can easily compute a spanning tree).
if some edge weights are different, there may be many minimum spanning tree. In this case, we can still assert that weight of the tree is minimum.
if all the edge weights are different, then the MST is unique. This fact can be used to precisely pinpoint the differences in solution during testing.

There is a corner case that needs to be checked: if all algorithm are no-op, i.e. they don’t do anything. There solution will always match!

Happy New Year!

Writing a DisjointSet in C# with the help of Code Contracts and Pex.

Jonathan de Halleux — Tue, 30 Dec 2008 19:41:45 GMT

I recently implemented a Disjoint-Set data structure in QuickGraph, which is the main building block of the Kruskal’s minimum spanning tree algorithm. This is a fun data-structure to look at, as it purpose is quite different from the ‘main’ BCL collections. The disjoint-set is useful to partition elements into sets, and defines 2 main operation to that purpose: Find, finds the set an element belongs to (can be used to check if 2 elements are in the same set), Union merges two sets.

The source of the disjoint-set is in the QuickGraph source, if you are curious about the details.

Testing the disjoint-set

There is not much left to TDD when it comes to write data structure. Such data structure are usually described in details in an article, and you ‘just’ have to follow the authors instruction to implement. Nevertheless, unit testing is really critical to ensure that the implementation is correct – but there is a risk of having to re-implement the algorithm to test it.

For the disjoint-set, I used 2 tools developed at RiSE: Code Contracts and… Pex. When implementing data structure from the literature, I usually start ‘dumping’ the code and the contracts. As much as possible, any invariant or property that the author describes should be translated to contracts. It will give more opportunities for Pex to find bugs in my code.

Contracts First

For example, the contracts for the Union method look as follows:

private bool Union(Element left, Element right)
{ Contract.Requires(left != null); Contract.Requires(right
!= null); Contract.Ensures(Contract.Result<bool>()
? Contract.OldValue(this.SetCount)
- 1 == this.SetCount : Contract.OldValue(this.SetCount)
== this.SetCount ); Contract.Ensures(this.FindNoCompression(left)
== this.FindNoCompression(right));

The two first requires clauses do the usual null checks. The first ensures clause checks that if Union returns true, a merge has been done and the number of sets has decreased by 1. The last ensures checks that left and right belong to the same set at the end of the union.

Note that so far, I did not have to provide any kind of implementation details. The other methods in the implementation receive the same treatment.

A Parameterized Unit Test

I wrote a single parameterized unit test while writing/debugging the implementation of the forest. It could probably have been re-factored into many smaller tests, but for the sake of laziness, I used a single one.

The parameterized unit test implement a common scenario: add elements to the disjoint-set, then apply a bunch of union operations. Along the way, we can rely on test assertion and code contracts to check the correctness of our implementation.

Let’s start with the test method signature:

[PexMethod] public
void Unions(int elementCount, [PexAssumeNotNull]KeyValuePair<int,int>[]
unions) {

The test takes a number of element to add and a sequence of unions to apply. The input data as is needs to be refined to be useful. In that sense, we add assumptions, under the form of calls to PexAssume, to tell Pex ‘how it should shape’ the input data. In this case, we want to ensure that elementCount is positive and relatively small; and that the values in unions are within the [0…elementCount) range.

 PexAssume.IsTrue(0
< elementCount); PexSymbolicValue.Minimize(elementCount); PexAssume.TrueForAll(
unions, u => 0 <= u.Key && u.Key < elementCount && 0 <=
u.Value && u.Value < elementCount );

Now that we have some data, we can start writing the first part of the scenario: filling the disjoint-set. To do so, we simply add the integers from [0..elementCount). Along the way, we check that the Contains, ElementCount, SetCount all behave as expected:

 var target
= new ForestDisjointSet<int>(); //
fill up with 0..elementCount - 1 for (int i
= 0; i < elementCount; i++) { target.MakeSet(i); Assert.IsTrue(target.Contains(i)); Assert.AreEqual(i
+ 1, target.ElementCount); Assert.AreEqual(i +
1, target.SetCount); }

The second part gets more interesting. Each element of the unions array is a ‘union’ action between 2 elements:

 //
apply Union for pairs unions[i], unions[i+1] for (int i
= 0; i < unions.Length; i++) { var left = unions[i].Key; var right=
unions[i].Value; var setCount = target.SetCount; bool unioned
= target.Union(left, right);

There is 2 things we want to assert here: first, then left and right now belong to the same set. Secondly, that the SetCount has been updated correctly: if unioned is true, it should have decreased by one.

        // should be in the same set now
       Assert.IsTrue(target.AreInSameSet(left, right));
        // if unioned, the count decreased by 1
       PexAssert.ImpliesIsTrue(unioned, () => setCount - 1 == target.SetCount);
    }
}

From this parameterized unit test, I could work on the implementation, and refine again and again until it had all passing tests (I did not write any other test code).

Happy Ending

The resulting test suite generated by Pex is summarized in the screenshot below: the number of elements does not really matter, what is interesting is the sequence of unions performed. This test suite achieves 100% coverage of the methods under test :).

In fact, the Union method involved some tricky branches to cover, due to some optimization occurring in the disjoint-set. Pex managed to generate unit tests for each of the branches.

Thanks to the contracts, the test assertions, and the high code coverage of the generated test suite, I have now a good confidence that my code is properly tested. The End!

(Next time, we will talk about testing minimum spanning tree implementations…)

Welcome Emile de Halleux

Jonathan de Halleux — Fri, 19 Dec 2008 00:19:09 GMT

My second son Emile de Halleux was born on Monday with 4.204g and lots of hair. He and his mother are enjoying a nice hot fire while the winter storm is slamming Seattle (glad he decided to come out before the icy mess). Happy Holidays!

QuickGraph 3.1 – .net 2.0 support – Fibonacci Heap

Jonathan de Halleux — Thu, 04 Dec 2008 08:28:30 GMT

I just released a new version of QuickGraph. Among many small improvements here and there, the big news are:

.net 2.0 support is back! QuickGraph now builds both for .net 2.0 and .net 3.5 (with extension methods).
The Dijkstra algorithm use a Fibonacci Heap under the hood, which is way more efficient. Courtesy of Roy Williams!
better serialization support and other bug fixes.

Enjoy, Peli.