Testing a Longest-Common Prefix Implementation Using Model-Based Testing

15/05/2013

In  my last post I discussed how to implement a Longest-Common Prefix (LCP) algorithm in both an imperative and functional manner in C#.  I also mentioned the fact that for the imperative implementation I needed some to write some unit tests.  Here is the test code:

[TestClass]
public class LCPTests
{
    [TestMethod]
    public void Get_WithNoValues_ShouldReturnEmptyString()
    {
        string result = LCP.Get(new string[] {});
        Assert.AreEqual(0, result.Length);
    }

    [TestMethod]
    public void Get_WithOneValue_ShouldReturnTheValue()
    {
        string result = LCP.Get(new[] {"dir1/dir2/dir3"});
        Assert.AreEqual("dir1/dir2/dir3", result);
    }

    [TestMethod]
    public void Get_WithTwoValues_ShouldReturnTheLongestMatch()
    {
        string result = LCP.Get(new[] {"dir1/dir2/dir3", "dir1/dir2/dir4"});
        Assert.AreEqual("dir1/dir2", result);
    }
}

The idea for these tests is that we have a single test each for 3 equivalence classes – the case where the input to the LCP method is empty, the case where it contains exactly 1 directory and the case where it contains 2 or more directories.  These 3 tests pass and seem to cover everything they need to cover.  But 3 tests for all possible cases?  This doesn’t seem right.  How can we be sure that we’re not missing something?

The short answer is – we can’t, at least not with tests (recall that tests can only show the presence of – not the lack of – bugs).  With more tests we might be more confident that there aren’t any obvious bugs, but we can never be absolutely sure.  So – more tests it is.  But this seems like such a tedious job, going over a large number of cases and figuring out what the proper result should be.  At this point, it’s pretty obvious that the computer itself should somehow generate both the test data and the test results.  In fact, when we do this we have what is known as a Test Oracle.

So how to write an oracle? One way is by reaching for our trusted copy of Visual Studio 2010 that has the Spec Explorer 2010 extension installed.  If you’re not familiar with Spec Explorer, it’s a Model-Based Testing  (MBT) tool that’s integrated directly into Visual Studio.  You write your model’s rules using C# and define scenarios and model parameters using a concept known as machines

For our model we want the ability to determine how many directories are compared in the LCP method, and how many parts each directory contains.  The general idea is that we have an ‘initial’ directory that contains a predefined number of parts.  We then add a number of other directories, each with the same number of parts and finally run the method.  The model produces both the inputs (directory parts) and the output (the longest common prefix).  Based on the above two parameters we can decide how few or how many tests Spec Explorer generates.

Model Mechanics

Here’s the model code:

public static class ModelProgram
{
    public static int DirectoryPartCount = 1;
    public static int MaxNumberOfDirectories = 1;
        

    private static readonly SequenceContainer<string> FirstDirectoryParts = 
        new SequenceContainer<string>();


    private static readonly SequenceContainer<SequenceContainer<string>> 
        OtherDirectoryParts = new SequenceContainer<SequenceContainer<string>>();

    private static int _otherDirectoryPartsIndex;


    private static bool _needsInitialization = true;


    public static IEnumerable<string> ExistingValues
    {
        get { return FirstDirectoryParts; }
    }

    [AcceptingStateCondition]
    public static bool IsAcceptingState
    {
        get { return OtherDirectoryParts.All(x => x.Count == DirectoryPartCount); }
    }

    [Rule]
    public static void Initialize()
    {
        Condition.IsTrue(_needsInitialization);
        for (int partIndex = 0; partIndex < DirectoryPartCount; partIndex++)
            FirstDirectoryParts.Add("dir" + partIndex);
        _needsInitialization = false;

        OtherDirectoryParts.Add(new SequenceContainer<string>());
    }

    [Rule]
    public static void AddNewDirectoryToCompare()
    {
        Condition.IsFalse(_needsInitialization);
        Condition.IsTrue(OtherDirectoryParts.Count == 0 ||
            OtherDirectoryParts[_otherDirectoryPartsIndex].Count == 
            DirectoryPartCount);

        _otherDirectoryPartsIndex++;
        OtherDirectoryParts.Add(new SequenceContainer<string>());
    }


    [Rule]
    public static string AddDirectoryPart([Domain("ExistingValues")] string part)
    {
        Condition.IsFalse(_needsInitialization);
        Condition.IsTrue(OtherDirectoryParts.Count <= MaxNumberOfDirectories && 
            OtherDirectoryParts.Count > 0);
        Condition.IsFalse(OtherDirectoryParts[_otherDirectoryPartsIndex].Count == 
            DirectoryPartCount);


        OtherDirectoryParts[_otherDirectoryPartsIndex].Add(part);


        return GetCommonPrefix();
    }

    private static string GetCommonPrefix()
    {
        int numberOfMatchingParts = 0;
        int maxLength = OtherDirectoryParts.Min(x => x.Count);
        for (int i = 0; i < maxLength; i++)
        {
            if (OtherDirectoryParts.All(x => x[i].Equals(FirstDirectoryParts[i])))
                numberOfMatchingParts++;
            else
                break;

        }

        return String.Join("/", FirstDirectoryParts.Take(numberOfMatchingParts));
    }
}

Let’s start with the rules.  Rules are actions that affect the state of the model.  Spec Explorer uses rules to determine the valid states (as in state-machine) of the model and how it should behave (that is, what output it should produce) for a given set of inputs.  The LCP model has the following rules:

1.  Initialize – Only allowed to run when the _isInitialized flag is false.  This rule sets up the initial directory’s parts and prepares an empty directory that is ready to accept new parts.

2.  AddDirectoryParts – Only allowed to run when the _isInitialized flag is true, the number of ‘other’ directories is below the set threshold and that the current ‘other’ directory is not full (which requires that we set up another ‘other’ directory).  This rule adds another part to the current ‘other’ directory.  It is up to Spec Explorer to supply the values of these parts (with a little user assistance, of course, to give it the set of permissible values).  Finally, this rule is responsible for computing the value that should be returned by the actual LCP function (using a simplified imperative implementation).

3.  AddDirectoryForComparison – Only allowed to run when the _isInitialized flag is true and the current ‘other’ directory is full.  This rule adds a new ‘other’ directory and makes it the current one.

In addition to the rules, we have some private state variables and helper methods.  Something worth mentioning is the IsAcceptingState property that is decorated by a [AccptingStateCondition] attribute.  This property indicates to the model that it is in an ‘accepting’ state – i.e., a state that can be used by the test code generator to end the test.  We’ll see this again in a minute.

Let’s look now at the .cord (short for ‘coordination’ file).  This file sets up the test scenarios that we want to generate:

using LCP.Adapter;
using LCP.Model;
using Microsoft.Modeling;

config Main 
{
 
    action all LongestCommonPrefix;
    
    switch StateBound = 65536;
    switch StepBound = 65536;
    switch TestClassBase = "vs";
    switch GeneratedTestPath = "..\\MBT.TestSuite";
    switch GeneratedTestNamespace = "MBT.TestSuite";
    switch TestEnabled = false;
    switch ForExploration = true;
}



machine ModelProgram() : Main 
{
    construct model program from Main
}

machine ModelProgramWithParameters() : Main
{
    {. 
       ModelProgram.DirectoryPartCount = 3;
       ModelProgram.MaxNumberOfDirectories = 2;
     .}:
    ModelProgram
}


machine ModelProgramWithAcceptingStates() : Main
{
    construct accepting paths
    for ModelProgramWithParameters
} 

machine TestSuite() : Main where TestEnabled=true 
{
    construct test cases where Strategy="shorttests", StopAtAccepting=true
    for ModelProgramWithAcceptingStates
}

Inside the .cord file we have a config section that sets up some bounds on the exploration that the model performs and determines where the generated code goes.  Based on this configuration we have a number of machines:

1.  ModelProgram – This sets up a machine that is based on the model code and uses the configuration values from the Main config section.

2.  ModelProgramWithParameters – This machine uses the user-specified parameters for determining how much exploration the model will do.  This is where we determine how many tests the model will generate.

3.  ModelProgramWithAcceptingState – This machine ‘cuts off’ the paths generated by the ModelProgramWithParameters machine so that paths end with accepting states.  It is the basis for the test generation phase.

4.  TestSuite – This machine is used for generating the actual test suite.  It uses a ‘short test’ strategy which means that it produces a large number of short tests as opposed to a small number of long tests.

Results

Lets look at a part of the explored ModelProgramWithAcceptingState machine:

DirectoryPartCount = 2

MaxNumbrOfDirectories = 2

image

See how Spec Explorer products all possible values for the parts as well as the expected LCP output?

And this is a part of the explored TestSuite machine:

image

And finally, let’s see the results of running the tests:

DirectoryPartCount = 2

MaxNumbrOfDirectories = 2

image

DirectoryPartCount = 3

MaxNumbrOfDirectories = 2

image

DirectoryPartCount = 2

MaxNumbrOfDirectories = 3

image

(Yes, it’s the same number of tests as before, but trust me, they’re different).

Summary

So there we have it – many different cases for testing the LCP function.  Rather than writing test cases and computing the output values in a manual fashion, we used a model to generate them automatically.  At this point, we can be reasonably sure that our function is correct.

The code for this post is available here.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*