Testing, Debugging, and Verification | TDA567/DIT082, LP2, HT2015 |

Exercises week 2 - Specifications, Testing | |

You can download test cases for exercise sessions 1, 2, 3 and 5 here.
The test cases satisfy statement and branch coverage, but are otherwise minimal.
They are produced under Eclipse and can be easily imported there if desired
(File -> Import; Existing projects into workspace; Select Below we provide some solution notes to all exercises. Answers to questions that ask you to write specifications or to derive test cases from specifications should just be seen as possible examples, and not be taken too strictly. There are two extremes to specification: overspecification (when you disclose too much information about how things are implemented) and underspecification (being too vague on what the thing you are specifying does). What should drive you is mainly common sense. There can be different specifications to a method: whether they are good or not is a matter of context, and you should apply Occam's razor in order to guarantee precision and freedom for the implementors as well.
Consider this method: public static Object[] reverse(Object[] a) { if (a == null) return null; Object[] b = new Object[a.length]; for (int i = 0; i < a.length; i++) { b[i] = a[a.length - 1 - i]; } return b; } The method returns a new array where the order of the elements has been reversed. (Your specification should be more detailed than the previous sentence.)
specification for method reverserequires:nothing ensures: a is unchanged and returns null if a is null, otherwise an array of the same length n as a in which for all elements at index i it is equal (even identical) to a[ n-1-i]
- Types don't change, therefore there is no need to enforce in the specification that what you have remains of the same type
- The length of the input array does not change after the method returns, i.e. it has not to be ensured in the postcondition. In the case of Java, any assignment to a method's formal parameters does not change the actual parameters (because of how Java treats argument passing -- "call by value"). In the case of the array, then, the only thing that can change are the elements of the array, but not the array itself. (The same applies to any object: only its fields can be changed)
- The specification could also be divided in two separate contracts:
**specification for method reverse**
*requires:* a is null
*ensures:* returns null and
*requires:* a is not null
*ensures:* a is unchanged and returns an array of the same length*n*as a in which for all elements at index i it is equal (even identical) to a[*n*-1-i]
Statement coverage: -
`a = null`-- executes the then-part of the if statement. Result should be null. `a = new Object[] { new Object() }`-- array of size 1; executes the rest of the method (*including*the body of the loop). Result should be the same as a.
Branch coverage: The statement covering test cases also do full branch coverage (the second test case both enters and exits the for-loop).
- If each if/else statement has statements in both its then- and else-branch,
statement coverage implies branch coverage. If one of the branches is empty,
statement coverage does not imply branch coverage, such as:
... if(condition) { <statements_1> } <statements_2> ...
Consider this method: public static void vector_add(Float[] a, Float[] b) { for (int i = 0; i < a.length; i++) { a[i] += b[i]; } }
The method computes the vector addition of
specification for method addrequires:a and b are non-null and with non-null elements, the length of a and b is the same, a and b are different objects. ensures: when the method returns each index i in a and b, a[i] is equal to the sum of a[i] and b[i] before the method was called, and b is unchanged
- A possible precondition is that we can also say that
`a.length <= b.length`. The choice is made mainly on what you would expect the user to use the piece of software, but both are correct.
The specification does not contain any case distinctions; we can only distinguish between empty and non-empty arrays. This is what is called an implicit disjunction in the specification. The precondition rules out the cases in which the arguments have different lengths; therefore we could partition the input between zero length arrays, and a couple of non-zero length arrays (without null elements): -
`vector_add(new Float[]{}, new Float[]{})` Expected result:`a={},b={}`-- a and b have length 0 -
`vector_add(new Float[]{2.0f}, new Float[]{3.5f})` Expected result:`a={5.5f}, b = {3.5f}`-- a and b have length greater than 0 - ... more tests can be added
This exercise is about an implementation of a queue. We do this using the usual "rotating array" implementation. Furthermore, we are going to stress the fact that whether testing is successful or not depends on what we expect. Consider the following class for representing a queue: public class Queue { Object[] arr; int size; int first; int last; public Queue(int max) { arr = new Object[max]; size = 0; first = 0; last = 0; } public int size() { return size; } public int max() { return arr.length; } public void enqueue(Object x) { arr[last] = x; last++; if (last == arr.length) last = 0; size++; } public Object dequeue() { if (size == 0) return null; Object x = arr[first]; first++; if (first == arr.length) first = 0; size--; return x; } }
The specifications do not give full technical details of how the state of the instance
changes.
They only talk about how specification for constructor Queuerequires:max >= 0 ensures: internal state represents an empty queue (size = 0) specification for method sizerequires:nothing ensures: returns the length of the queue (size); the state of this instance is unchanged. specification for method maxrequires:nothing ensures: returns the maximum capacity of the queue specification for method enqueuerequires:queue is not yet full (size < length of arr) ensures: x is added to the queue (size increased by one) specification for method dequeuerequires:nothing ensures: if queue is empty (size = 0) then returns null, otherwise removes an object from the queue (size decreases by one) and returns that removed object In a more formal specification the specifier would have to express formally what changes to last, first and size in detail, making explicit how the specification maps to the implementation.
size we can indentify the following distinctions:
- (A) 0 = size = length of arr
- (B) 0 = size < length of arr
- (C) 0 < size < length of arr
- (D) 0 < size = length of arr
st={7,9}
means that the state correspond to the queue with the
objects 7 and 9 and for which 7 will be dequeued before 9.
Integers are used as objects in the queue.
Test cases for constructor:
Test cases for method size:
Test cases for method enqueue:
Test cases for method dequeue:
- Whenever you might have to test several things together, in designing tests you have a choice that must be driven by:
**Traceability**(from where did this defect came out?)**Readability**(will any other programmer be able to read and understand the tests and their meaning in a reasonable amount of time?)
- A good practice is to keep the number of assertions per test case as low as possible to enforce that what is said in the previous bullet. The ideal is to have one assertion per test case. Although this leads to lots of test methods, this is the ideal. Every test case tests a certain property, so if one case fails you know exactly which property failed.
**Scenarios in which multiple assertions are useful**.- Logical expressions that are evaluated together. Imagine you have to assert that
`a&&b&&c`is true. Then it makes sense to breakassert(a&&b&&c); inassert(a); assert(b); assert(c); since this will make any defect more traceable. -
Strong semantic coupling between expressions. You can have situations in which the multiple assertions make sense together because they prove a property. An example it could be proving that two queues have the same values with the exception of the last one in one of them: you can then factor the two assertion in a single method.
public void myAssertion(Queue a, Queue b){ assertEquals(a.size,b.size); a.dequeue(); assertEquals(a,b); } Obviously, assuming that`dequeue`is bug free and`Queue`implements`equals`.
- Logical expressions that are evaluated together. Imagine you have to assert that
**Expected clauses**. JUnit allows test-methods to fail with an exception, if it is explicitly is stated that this is expected to happen. So, if method`m`should throw a nullpointer exception if it gets the argument`null`as input, this can be tested with the test case:@Test(expected = NullPointerException.class) void testM() { m(null); }
Test cases for constructor:
Test cases for method size:
Test cases for method max:
Test cases for method enqueue:
Test cases for method dequeue:
class invariant for Queue: arr is non-null, and 0 <= size <= length of arr, and 0 <= first < length of arr, and 0 <= last < length of arr, and either last - first = size or length of arr + last - first = sizeThe last line of the invariant has two cases in order to deal with the situations where the queue wraps around the beginning and end of the array. It is interesting to see what happens if we keep invoking enqueue() on a certain queue:
q = new Queue(2) // size == 0, first == 0, last == 0 , q : [-,-] q.enqueue(1); // size == 1, first == 0, last == 1 , q : [1,-] q.enqueue(2); // size == 2, first == 0, last == 2 , q : [1,2] q.enqueue(3); // !! size == 3, first == 0, last == 0, q: [3,2]In the third enqueue, the method ends normally: there is no exception. But we broke the invariant, and the abstraction we built on the array and the pointers: dequequing now will not give 1 as we expected. An invariant is something the implementor has to assure that holds before and after the method has been executed. You could see it as a factoring out of things you would write in all the ensures and requires clauses of the specification. And, among the possible things that can happen after calling a method and not respecting its requirements, there can be even making false the invariant.
In exercise 2, try calling the method with two arrays of different lengths. Calling a method and not fulfilling the requires specification leads to an unpredictable behavior, not necessarily to the abrupt termination of your program.
Consider this method: public static void f(Object x, Object[] arr) { int i; boolean exists = false; for (i = 0; i < arr.length; i++) { // A1 if (x.equals(arr[i])) { // B1 exists = true; break; } // B2 } // A2 if (!exists) // C1 { for (i = 0;; i++) { // D1 if (arr[i] == null) { // E1 arr[i] = x; break; } // E2 } // D2 } // C2 }
Someone wrote this specification for specification for method frequires:x and arr are non-null and there is an element in arr which is null ensures: when f returns there is an element in arr which is equal to x
If there is already an element in arr which is equal to x, then there need not be a null in arr. So the precondition can be:
x and arr are non-null and there is EITHER an element in arr which is null OR an element in arr which is equal to x
This means that either arr has some null elements, or the array has an element that is equal to x. But not both: i.e.
x = new Integer(1); arr = new Integer[]{null,x}; f(x,arr)violates the precondition.
The elements which were previously in arr will still be there after the call. We can even say where x is inserted but let's keep the specification on a slightly more abstract level.
when f returns
x is unchanged, and if there was before an object equal to x in arr then arr is unchanged, otherwise arr contains the same non-null objects plus x and the rest is unchanged
Let's use these codes for referring to the different branch choices: - (A1) going into first for-loop
- (A2) skipping/exiting first for-loop
- (B1) going into if-statement in first for-loop
- (B2) skipping it
- (C1) going into if-statement after first for-loop
- (C2) skipping it
- (D1) going into second for-loop
- (D2) skipping/exiting second for-loop
- (E1) going into if-statement in second for-loop
- (E2) skipping it
Test cases for path coverage up to two repetitions of for-loops:
We are going to specify and test an implementation of an algorithm called "Dutch National Flag". The algorithm can sort arrays arr of integers coming from the set {1,2,3} in linear time. Example: Given the array arr = {2,3,3,3,1,1,2,3,2,2,1,1,1}the algorithm sorts the array, producing: arr = {1,1,1,1,1,2,2,2,2,3,3,3,3}When the array contains other numbers than 1, 2 or 3, the result is unpredictable. Here is the code: public static void dnfsort(int[] arr) { int a = 0, b = 0, c = arr.length; while (b < c) { if (arr[b] == 1){ arr[b] = arr[a]; arr[a] = 1; a = a+1; b = b+1; } else { if (arr[b] == 2) { b = b+1; } else // arr[b] should be 3 here { c = c-1; arr[b] = arr[c]; arr[c] = 3; } } } }
requires: arr is non null and all elements in arr are either 1,2 or 3
ensures:when dnfsort returns then for all pairs of adjecent elements, say arr[i] and arr[i+1], it holds that arr[i] is less than or equal to arr[i+1]. It says that the result is a sorted array, but not that the array contains the same elements as before the call. ensures:when dfsort returns then for all pairs of adjecent elements, say arr[i] and arr[i+1], it holds that arr[i] is less than or equal to arr[i+1] and the elements in arr is a permutation of the elements in arr before the call
The array arr can can be either empty or non-empty. Thinking about how sortedness and permutation is defined, this also motivates dividing the test cases into 1-element arrays and several element arrays. Also the precondition enumerates the numbers 1,2 and 3, so different combinations of these numbers should form different classes.
Statement coverage:
Branching points are the
Any path which repeats the while loop at least three times, e.g.: | |

Home | Course | Schedule | Exam | Exercises | Labs | Evaluation | Tools | Links | Atze van der Ploeg, Nov 4, 2015 |