Code Contracts By Example

Earlier, I blogged about Code Contracts as a tool to help you specify and verify code behavior. Today let's have a closer look with a prac­tical example.

Say that we need to create a new class, a priority queue. We write the spec­i­fi­cation of the new class, natu­rally, as an interface to implement:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

namespace AdvancedCodeContracts
{
	/// <summary>
	/// Interface for priority queue classes.
	/// </summary>
	/// <typeparam name="T">Item type.</typeparam>
 
	public interface IPriorityQueue<T> where T : class
	{
		/// <summary>
		/// Gets the number of items in the queue.
		/// </summary>
		int Count { get; }
 
		/// <summary>
		/// Enqueues a new item with a priority (higher is better).
		/// </summary>
		/// <param name="priority">Priority between 1 and 100.</param>
		/// <param name="item">Item to enqueue.</param>
		void Enqueue(int priority, T item);
 
		/// <summary>
		/// Dequeues the item with the highest priority.
		/// </summary>
		/// <returns></returns>
		T Dequeue();
 
		/// <summary>
		/// Clears the queue.
		/// </summary>
		void Clear();
	}
}

This is a straight­forward, plain-​​vanilla priority queue as I'm sure we've all written at one stage or another. It is, of course, a Best Practice to imme­di­ately document the interface.

Now, can we already define what constraints to put on the implementation(s) of this interface? That is, can we write, per method and property, a set of pre– and post­con­di­tions that must be satisfied? Can we write an object invariant for the class?

Of course we can. We can also write unit tests for it. After all, we are all doing Test-​​Driven Development, aren't we?

So we must make a choice: either we write the contracts first, or the unit tests.

I think this choice is a matter of personal pref­erence. You have to write both before you do the imple­men­tation anyway… OK, true, you don't really have to, but it's a Best Practice to write code contracts before imple­men­tation, and it's another Best Practice to write unit tests before imple­men­tation. Why? Just because.

No, because this saves valuable devel­opment time as it cuts short debugging. It forces us as devel­opers to think about our approach before we start hacking away at the code.

OK, then, let's do those code contracts first.

But we don't have an imple­men­tation yet! So how do we approach this?

We can actually specify a code contract on an interface. Think inher­i­tance: all classes that implement the interface, inherit the code contract and thus must satisfy it. They can also extend the contract by adding extra post­con­di­tions to methods (not precon­di­tions) and extra object invariants. How cool is that?

So let's add a code contract to the interface. We start by adding a using and an attribute to the interface:

1
2
3

using System.Diagnostics.Contracts;
 
[ContractClass(typeof(IPriorityQueueContract<>))]

As you would imagine, this tells the compiler that there exists a class called IPriorityQueueContract that imple­ments a code contract on this interface. Notice the absence of the T in the attribute, though; you cannot use that syntax in an attribute, so you have to leave the generic T out. Believe it or not, this actually compiles, and it works, too.

Incidentally, if you are using .NET 4.0, you don't need to add any refer­ences to your project. The System.Diagnostics.Contracts name­space is included in mscorlib. But if you're old-​​school (still working with .NET Framework 3.5), you'll need to download the Code Contracts library and reference it.

OK, fine. Problem is of course that we don't have that class yet, so we create it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

using System;
using System.Diagnostics.Contracts;
 
namespace AdvancedCodeContracts
{
  [ContractClassFor(typeof(IPriorityQueue<>))]
  public class IPriorityQueueContract<T> : IPriorityQueue<T> where T : class
  {
    public int Count
    {
      get
      {
        return 0;
      }
    }
 
    public void Enqueue(int priority, T item)
    {
    }
 
    public T Dequeue()
    {
      return (T)new object();
    }
 
    public void Clear()
    {
    }
  }
}

It is my habit to call contract classes simply Contract. That is the convention I use, but you may have a policy against classes having names that start with I.

In this class, we specify that this is a contract class for the IPriorityQueue interface, and we actually implement that interface. That is why the Count property and the Dequeue() method are actually returning values; because we must implement the interface. The values that this class returns are irrel­evant and are ignored by the Code Contracts system.

Let's fill in the pre– and post­con­di­tions and the object invariant now:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

using System;
using System.Diagnostics.Contracts;
namespace AdvancedCodeContracts
{
 
  [ContractClassFor(typeof(IPriorityQueue<>))]
  public class IPriorityQueueContract<T> : IPriorityQueue<T> where T : class
  {
    [ContractInvariantMethod]
    void ObjectInvariant()
    {
      Contract.Invariant(this.Count >= 0);
    }
 
 
    // dummy implementation, we don't need a contract here
    public int Count
    {
      get
      {
        return 0;
      }
    }
 
 
    public void Enqueue(int priority, T item)
    {
      Contract.Requires<ArgumentOutOfRangeException>(priority >= 1 && priority <= 100);
      Contract.Requires<ArgumentNullException>(item != null);
      Contract.Ensures(this.Count == Contract.OldValue(this.Count) + 1);
    }
 
 
    public T Dequeue()
    {
      Contract.Requires<InvalidOperationException>(this.Count > 0);
      Contact.Ensures(Contract.Result<T>() != null);
      Contract.Ensures(this.Count == Contract.OldValue(this.Count) - 1);
      return (T)new object();
    }
 
 
    public void Clear()
    {
      Contract.Ensures(this.Count == 0);
    }
  }

In the object invariant, we say that the Count property must always return a positive number. Because we do so, we do not need to specify this again as a post­con­dition in the property itself.

The Enqueue() method lays down two preconditions:

• The priority para­meter must be between 1 and 100, inclusive;
• The item to enqueue may not be null.

The method further spec­ifies a post­con­dition that stip­u­lates that the Count property is increased by 1; so at the end of the method, the new value of Count must be the old value + 1. Note that currently, the Contract.OldValue() method is only valid inside a Contract.Ensures().

Next, we define a single precon­dition on Dequeue(): the queue may not be empty. We throw an InvalidOperationException if it is. We also specify two post­con­di­tions for this method:

• The result is never null. We can guar­antee this because we don't allow enqueing null in the first place.
• The Count property is always decreased by 1.

Finally, the Clear() method guar­antees, by means of a single post­con­dition, that the queue will be empty.

Are we having fun yet?

Note that all condi­tions in the code contract use public prop­erties or input para­meters only. There is no reference to any private vari­ables. This is logical even if the code contract is not just defined on an interface; it is a code contract after all, so its details must be visible outside of the implementation.

This code can compile, even though we don't have a concrete imple­men­tation of our priority queue yet.

So let's write a set of unit tests. Let's throw every­thing we can think of right now at that interface:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

using System;
using AdvancedCodeContracts;
using Microsoft.VisualStudio.TestTools.UnitTesting;
 
namespace AdvancedCodeContractsBlackboxTests
{
  [TestClass]
  public class PriorityQueueOfStringUnitTests
  {
    private IPriorityQueue<string> sut;
 
    [TestInitialize]
    public void TestInitialize()
    {
      sut = new PriorityQueue<string>();
    }
 
    [TestMethod]
    public void PriorityQueue_InitialState_Ok()
    {
      Assert.IsNotNull(sut);
      Assert.AreEqual(0, sut.Count);
    }
 
    [TestMethod]
    public void PriorityQueue_AddSingleItem_CountIs1()
    {
      sut.Enqueue(1, "This is one");
      Assert.AreEqual(1, sut.Count);
    }
 
    [TestMethod]
    public void PriorityQueue_AddSingleItemAndDequeue_Ok()
    {
      sut.Enqueue(1, "This is one");
      string result = sut.Dequeue();
      Assert.AreEqual(0, sut.Count);
      Assert.AreEqual("This is one", result);
    }
 
    [TestMethod]
    [ExpectedException(typeof (InvalidOperationException))]
    public void PriorityQueue_DequeueFromEmptyQueue_ThrowsInvalidOperationException()
    {
      string result = sut.Dequeue();
    }
 
    [TestMethod]
    [ExpectedException(typeof (ArgumentNullException))]
    public void PriorityQueue_EnqueueNull_ThrowsArgumentNullException()
    {
      sut.Enqueue(1, null);
    }
 
    [TestMethod]
    [ExpectedException(typeof (ArgumentOutOfRangeException))]
    public void PriorityQueue_EnqueuePriority0_ThrowsArgumentOutOfRangeException()
    {
      sut.Enqueue(0, "dummy");
    }
 
    [TestMethod]
    [ExpectedException(typeof (ArgumentOutOfRangeException))]
    public void PriorityQueue_EnqueuePriority101_ThrowsArgumentOutOfRangeException()
    {
      sut.Enqueue(101, "dummy");
    }
 
    [TestMethod]
    public void PriorityQueue_Clear_Ok()
    {
      sut.Enqueue(1, "One");
      sut.Enqueue(1, "Two");
      sut.Enqueue(1, "Three");
      sut.Clear();
 
      Assert.AreEqual(0, sut.Count);
    }
  }
}

Yes, the unit tests are written against an interface (IPriorityQueue). We do assume that we'll write a concrete class called PriorityQueue. We'll do that as the next step.

But first, let's look at these tests. They are of course quite straight­forward. Any class that satisfies these tests can right­fully be called a priority queue, even though in the TestInitialize() method, we instan­tiate our subject under test (sut) as an instance of the PriorityQueue class.

Convention Alert: I use the test naming convention _​_​. I find it makes for readable unit test code as well as readable test lists. Again, your mileage may vary.

Let's add a couple more tests just for fun:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

[TestMethod]
public void PriorityQueue_AddMultiplePrioritizedItemsAndDequeue_Ok()
{
  sut.Enqueue(1, "This is one");
  sut.Enqueue(2, "This is two");
  sut.Enqueue(5, "This is three");
  sut.Enqueue(3, "This is four");
  sut.Enqueue(4, "This is five");
  Assert.AreEqual(5, sut.Count);
 
  string result;
  result = sut.Dequeue();
  Assert.AreEqual(4, sut.Count);
  Assert.AreEqual("This is three", result);
 
  result = sut.Dequeue();
  Assert.AreEqual(3, sut.Count);
  Assert.AreEqual("This is five", result);
 
  result = sut.Dequeue();
  Assert.AreEqual(2, sut.Count);
  Assert.AreEqual("This is four", result);
 
  result = sut.Dequeue();
  Assert.AreEqual(1, sut.Count);
  Assert.AreEqual("This is two", result);
 
  result = sut.Dequeue();
  Assert.AreEqual(0, sut.Count);
  Assert.AreEqual("This is one", result);
}
 
[TestMethod]
public void PriorityQueue_EnqueueMultipleItemsWithSamePriority_Ok()
{
  sut.Enqueue(1, "One");
  sut.Enqueue(1, "Two");
  sut.Enqueue(1, "Three");
  Assert.AreEqual(3, sut.Count);
}
 
[TestMethod]
public void PriorityQueue_ClearOnEmptyQueue_Ok()
{
  sut.Clear();
  Assert.AreEqual(0, sut.Count);
}

Uh, those tests are actually necessary – not just fun. Good that we caught them before we started writing "real" code.

OK, now we're ready to actually write the implementation.

In case you've never done TDD before: how do you feel right now? Don't you feel pretty sure that whatever we'll come up with as code will be tested very well? And what are the odds that we'll come up with working code quickly, without too much "red" in our unit test results?

Here's a concrete, if simple, implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
 
namespace AdvancedCodeContracts
{
  public class PriorityQueue<T> : IPriorityQueue<T> where T : class
  {
    private List<Item> _list = new List<Item>();
 
    public int Count
    {
      get { return _list.Count; }
    }
 
    public void Enqueue(int priority, T toEnqueue)
    {
      Item item = new Item { Priority = priority, Object = toEnqueue };
      _list.Add(item);
    }
 
    public T Dequeue()
    {
      int highest = _list.Max(i => i.Priority);
      Item item = _list.First(i => i.Priority == highest);
      _list.Remove(item);
      return item.Object;
    }
 
    public void Clear()
    {
      _list.Clear();
    }
 
    [ContractInvariantMethod]
    void SpecificObjectInvariant()
    {
      Contract.Invariant(_list != null);
    }
 
    #region Nested type: Item
 
    private class Item
    {
      public int Priority { get; set; }
 
      public T Object { get; set; }
    }
 
    #endregion
  }
}

This is a correct imple­men­tation. How do I know? Because all unit tests run and the code contract is satisfied – otherwise at least one pre– and/​or post­con­dition and/​or object invariant would have failed.

Did you notice that this concrete imple­men­tation adds post­con­di­tions and a more specific object invariant to the contract? This is allowed because specific imple­men­ta­tions may offer extra output guar­antees (post­con­di­tions), and may include specific (read: private field/​property) invariants. Extra precon­di­tions are not allowed; as we inherit from a public interface or even a concrete imple­men­tation, we may not narrow the contract.

Next, we may modify the code for more perfor­mance, or better yet, write another imple­men­tation (say, a FastPriorityQueue) that imple­ments the same interface, and therefore the same code contract, and therefore – with one small change in TestInitialize() – the same unit tests.

Good code docu­ments and verifies itself. Code Contracts are the way to do it. Will they be part of your team's Quality Assurance arsenal too?