The PickAkin Kata - testing

As I decided to "just invent a solution out of the blue" in the previous posting, we are now in classical software engineering: I'm of course obliged to test that solution (or rather, solution candidate). So let me do a quite formal example test case design - it's a good exercise for me, anyway.

The standard functional test concept is "equivalence class partitioning": It should help us to arrive at a finite set of test cases that somehow covers "sufficiently" the infinitely many possible inputs and outputs of our code. Interestingly, equivalence class partitioning is not at all obvious for our small problem! To tackle this nice testing problem, let's first clearly separate the "spaces" to be covered:

• Black box testing requires us to find a partitioning for the input space.
• Black box testing also requires us to find a partitioning for the output space.
• Finally, white box testing requires us to find a partitioning for any internal space created.

The input space consists of two sets. However, the problem groups items in each set according to their "DLQ" (the first letter of the strings, in our integration test) - so it is more appropriate to model each set as a bag of prefixes, i.e., a mapping from prefixes to non-negative integers. A set, and hence also a mapping, is typically covered by the 0-1-3 heuristics, i.e., we take the empty set, a singleton set, and a set with three elements for testing. Applied to our mappings, the patterns for one input set are therefore

    { }
    { . -> . }
    { . -> ., . -> ., . -> . }

On the left side of the mappings, we can take arbitrary prefixes. On the right side, we have to cover non-negative integers - again, we use the 0-1-3 heuristics. However, a mapping to 0 just means that the element is not present in the mapping - so we drop it. What do we get from our three "mapping templates"?

• The empty set just remains as it was:

    { } - case "0"

•     The single-element mapping can be expanded to two cases:

    { A -> 1 }  - case "1"
    { B -> 3 }  - case "3"

• For the three-element mapping, we could create 2^3 = 8 versions. We arbitrarily restrict ourselves to "pairwise coverage", i.e., each combination of the two cases "1" and "3" must occur once. This requires just two mappings, e.g.

    { D -> 1, E -> 1, F -> 3 }  - case "113"
    { G -> 3, H -> 3, I -> 1 }  - case "331"

(Each "pair" created from the set { 1, 3 } occurs: {1,1} for D, E; {1,3} e.g. for E, F or for G, I; and {3,3} for G, H).

Trivially multiplying these five cases for the two input sets would give us 25 cases for input coverage. However, we want to restrict this for two reasons:

• First, 25 cases is too much for the budget we have (says me).
• Second, this trivial multiplication does not consider the output coverage.

Therefore, let's now consider the output coverage! The result of Pick.Akin are three disjoint bags. Doing the same as on the input side, we end up with five cases for each mapping (or bag), which altogether results in 5*5*5 = 125 different cases - even more than the 25 on the input side! Again, we can try to mechanically apply "pairwise coverage" - but let's please make sure that a few "common sense" boundary cases are among the tests. I get lazy here and use a tool - PICT. The input model for PICT can be written as

    ceoListAfter:   e0, e1, e3, e113, e331
    akinList:       a0, a1, a2, a112, a221
    ctrlListAfter:  t0, t1, t3, t113, t331

We see the 5 possibilities for each bag, marked with a letter to distinguish the three bags (I varied the size "3" for the akinList to "2", just so). As "common sense" cases, we take set sizes of [0, 0, 0], [0, 1, 0], [1, 0, 1], and [3, 2, 3], which gives us a PICT seed file of

    ceoListAfter    akinList    ctrlListAfter
    e0    a0    t0
    e0    a1    t0
    e1    a0    t1
    e3    a2    t3

The PICT run yields a whopping 28 test cases:

    e0      a0      t0
    e0      a1      t0
    e1      a0      t1
    e3      a2      t3
    e331    a221    t113
    e0      a2      t331
    e0      a112    t113
    e113    a221    t0
    e331    a112    t331
    e113    a1      t3
    e0      a221    t3
    e1      a112    t3
    e1      a2      t0
    e113    a0      t331
    e1      a221    t331
    e3      a0      t113
    e1      a1      t113
    e3      a1      t331
    e3      a112    t1
    e0      a2      t1
    e3      a112    t0
    e3      a221    t1
    e113    a2      t113
    e331    a2      t3
    e331    a1      t1
    e113    a112    t1
    e331    a0      t0
    e0      a0      t3

What can we do? There are only two ways to go:

(a) We accept this as our work load (the 28 cases would at least harmonize quite well with the 25 input cases we wanted to cover!).
(b) We try to argue that there are no interferences between the results in the three output parameters ... but this is certainly not true: They are tightly coupled (e.g. by the requirement that the prefixes in them are disjoint!).

Mhm.

-----------------

The only idea I have to reduce our test work load is to replace the 0-1-3 heuristics for sets with a 0-3 heuristic: Empty set - not-empty set. So let's start from scratch:

The input space per set consists of

    { }
    { . -> ., . -> ., . -> . }

For these two "mapping templates", we get the following cases:

• For the empty case:

    { } - only case "0"   

• For the three-element mapping, using "pairwise coverage" again, we get:

    { D -> 1, E -> 1, F -> 3 }  - case "113"
    { G -> 3, H -> 3, I -> 1 }  - case "331"

For the input side, fully multiplying these cases would give us 9 test cases.

For the output side, we would get 3*3*3 = 27 cases for full multiplication. Pairwise coverage with PICT can be done with the following model:

    ceoListAfter:   e0, e113, e331
    akinList:       a0, a112, a221
    ctrlListAfter:  t0, t113, t331

We keep the four common sense testcases from above - however, three of them will not be created by these mappings (e0/a1/t0, e1/a0/t1, e3/a2/t3). With the following seed file,

    ceoListAfter    akinList    ctrlListAfter
    e0    a0    t0

PICT gives us the following ten test cases for the 3 output lists ceoListAfter, akinList, and ctrlListAfter:

    e0      a0      t0
    e113    a221    t0
    e331    a0      t113
    e113    a112    t331
    e0      a112    t113
    e331    a221    t113
    e331    a0      t331
    e331    a112    t0
    e0      a221    t331
    e113    a0      t113

Some of these cases are quite superfluous: E.g., we don't need both e113/a112/t331 and e331/a221/t113. Moreover, we can rely on the symmetric code and therefore remove cases that are symmetrical for ceoListAfter and ctrlListAfter. That would leave us with the following cases:

    e0      a0      t0
    e113    a221    t0
    e331    a0      t113
    e113    a112    t331

plus the three common sense test cases

    e0    a1    t0
    e1    a0    t1
    e3    a2    t3

and the acceptance test. The whole undertaking gets a little boring now, so I declare that I'm happy with these combinations, and we construct the test data:

    e0      a0      t0:

This can only result from two empty input sets. Thus, input combination [{ }, { }] is covered.     

    e113    a221    t0:

We need three prefixes that end up in the ceoListAfter, and 3 more that end up in akinList. Here are possible mappings:

            ceoList  { A->1, B->1, C->3, D->1, E->1, F->1 }
            ctrlList                   { D->1, E->1, F->... }

Mhm: How can we have a single element for prefix F in the akinList? After all, the akinList must contain one instance from the ceoList and one from the ctrlList! So maybe there is a restriction that in the akinList, the number of elements per prefix is always even? ... or not: Assume that both lists contain the string "F1" - is our akinList assumed to contain "F1" twice, or only once? I take a shortcut: The code will return only one (as the call to Distinct() does not distinguish "left" and "right" elements), and so I say this is right. As an exercise, we could try to implement a version that will behave exactly the other way round - this seems not that easy!

After this (typical) "specification detour," we can create matching input sets from the mappings:

            ceoList  { A1, B1, C1, C2, C3, D1, E1, F1 },
            ctrlList                     { D2, E2, F1 }

This covers input combination [not empty, not empty].      

    e331    a0      t113:

After that initial construction, it now gets easy:

    ceoList  { A1, A2, A3, B1, B2, B3, C1 }
    ctrlList                              { D1, E1, F1, F2, F3 }

Again, we have covered  input combination [not empty, not empty].

        e113    a112    t331:

          ceoList  { A1, B1, C1, C2, C3, D1, E1, F1 }
          ctrlList                     { D1, E1, F2, G1, G2, G3, H1, H2, H3, I1 }

From here on, we should modify the list order. E.g., in this test case we could reverse the lists. But we notice that we are not going to cover any more input combinations that way! So we add two more cases for input combinations [empty, not empty] and [not empty, empty]:      

    e0      a0      t22:
            ceoList  { }
            ctrlList   { D1, D2, E1, E2 }

and  

    e1      a0      t0:
            ceoList  { A1 }
            ctrlList      {  }

Finally, here are the common sense test cases:  

    e0    a1    t0
            ceoList  { A1 }
            ctrlList { A1 }
    e1    a0    t1
            ceoList  { A1 }
            ctrlList      { B1 }
    e3    a2    t3
            ceoList  { A1, A2, A3, B1, B2 }
            ctrlList             { B1, B2, C1, C2, C3 }
        or
            ceoList  { A1, A2, A3, B1 }
            ctrlList             { B2, C1, C2, C3 }

And this is it. A little boring, was that testing, altogether.