.ds RH The Types of Coverage
.bp
.sp
.ce
.ps 16
The Types of Coverage
.ps 12
.XS
The Types of Coverage
.XE
.NH 1
Changes to Multicondition Coverage
.LP
When multicondition coverage is selected alongside weak mutation
coverage, it applies to more operators.  The complete set of operators
is
.TS
center allbox tab(#) ;
c c 
l l .
Tree type # Point of instrumentation
and#&&
or#||
bitwise and#&
bitwise or#|
bitwise exclusive or#^
.TE
As before, both the left-hand and right-hand sides must be both 0 and
non-zero.
.LP
Similarly, the set of operators that yield "boolean" values has been
expanded:

.TS
center box tab(#) ;
l l l l l l l .
<#<=#>#>=#==#!=
&#|#^#&&#||#~#!
&=#|=#^=
.TE
.LP
These operators must yield both zero and non-zero when used as the
argument to \fHreturn\fR or an assignment statement.
.LP
.LP
Further, these kinds of assignment statements must yield both zero and
non-zero values:
.TS
center box tab(#) ;
l l l .
&=#|=#^=
.TE
.LP
These extensions seldom add much cost to testing, since the operators
are not commonly used, and the coverage conditions are often ruled out
without your ever seeing them.  Still, it's doubtful they add much
benefit, and they may disappear in a later release.  Your opinion is
welcome.

.NH 1
Operator Coverage
.LP
All operator coverage is expressed in terms of a hypothesized correct
operation that can't be ruled out.  Suppose we have the following code:
.nf

    if (a + b < c + d )

.fi
To rule out the fault where the first \fH+\fR should have been a
\fH-\fR, \fHB\fR must not be 0, (since \fHa+0=a-0\fR).
For the same reason, \fHD\fR must not be 0.
To rule out
the fault where < might be <=, there must be a case where A+B==C+D.
If a fault is ruled out, 
nothing regarding it will appear
in the report unless the \fB-all\fR option is given.  
.LP
A report will look like:
.nf

"example1.c", line 9: operator + might be -.
"example1.c", line 9: operator < might be <=.
"example1.c", line 9: operator + (2) might be -.

.fi
If -all is used, the number of times the condition is satisfied is
reported:
.nf

"lc.c", line 275: operator <= might be >=  [1]
"lc.c", line 275: operator <= might be <.  [3]

.fi
.NH 2
The Point of Instrumentation
.LP
In all cases, the point of instrumentation is the operator itself.
.NH 2
Arithmetic Operators
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 + expr2
Alternate # Rule out with
-#expr2!=0
*#expr1+expr2!=expr1*expr2
.TE
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 - expr2
Alternate # Rule out with
+#expr2!=0
.TE
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 * expr2
Alternate # Rule out with
+#expr1+expr2!=expr1*expr2
.TE
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 / expr2
Alternate # Rule out with
%#expr1 / expr2 != expr1 % expr2
.TE
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 % expr2
Alternate # Rule out with
/#expr1 / expr2 != expr1 % expr2
.TE
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
- expr1
Alternate # Rule out with
non-negated expression#expr1!=0
.TE
.bp
.NH 2
Boolean Operators
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 && expr2
Alternate # Rule out with
||#expr1&&expr2 != expr1||expr2
.TE
.LP
Ruling out & is too hard to satisfy, so that coverage condition is
omitted.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 || expr2
Alternate # Rule out with
&&#expr1 || expr2 != expr1 && expr2
.TE
.LP
Ruling out | is, again, too hard to satisfy.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
!expr
Alternate # Rule out with
~#!expr != ~expr
.TE
.LP
The only case that does \fInot\fR rule out ! is a word with all ones.
.bp
.NH 2
Bitwise Operators
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 & expr2
Alternate # Rule out with
|#expr1!=expr2
&&#!!(expr&expr2) != expr && expr2
.TE
.LP
In the second case, notice that the \fItruth value\fR of
expr1&expr2 must be distinguishable from expr1&&expr2.  
The weaker condition (expr1&expr2 != expr1 && expr2)
would be satisfied by
.nf

	expr1 = 0x5, expr2 = 0x3

.fi
The differences between the original expression and the variant are
more likely to cause a noticeable effect if one of them is forced to 0.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 | expr2
Alternate # Rule out with
&#expr1!=expr2
||#(expr1 | expr2) != (expr1 || expr2)
.TE
.LP
Unlike the previous case, the truth value of the left hand side is not used -- it
always has the same value as the right hand side.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 ^ expr2
Alternate # Rule out with
|#expr1|expr2!=expr1^expr2
&#expr1^expr2!=expr1&expr2
.TE
.LP
The second case is used because &-for-^ is a likely typo -- the
two keys are next to each other on the keyboard.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
~ expr
Alternate # Rule out with
!#~expr != !expr
.TE
.LP
The only case that does \fInot\fR rule out ! is a word with all ones.
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
expr1 << expr2, expr1 >> expr2
Alternate # Rule out with
each other#expr1!=0
.TE
.bp
.NH 2
Assignment
.LP
Coverage conditions rule out alternate operators, as usual.  They also
force test cases in which the assignment statement makes a change
in the program state.  For example, if, in "A = B", A and B always
have the same value, perhaps the assignment statement is never needed.
.LP
In the descriptions of how to rule out alternates, \fIlval_new\fR
refers to the post-assignment value of the variable on the
left-hand-side of the assignment statement.  \fIlval_old\fR refers to
its pre-assignment value.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval = expr
Alternate # Rule out with
never needed#lval_old!=lval_new
==#(!!lval_new) != (lval_old == expr)
.TE
The double negation converts the value of the assignment statement
into a truth value, which must be different from the truth value of
the expression gotten when = is replaced with ==.  This is because
this fault is often found in expressions like:
.nf

	if (a = b)	/* Meant a == b */

.fi
and the comparison of truth values forces the other branch to be
taken, making it more likely that the effect is observable.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval += expr
Alternate # Rule out with
-=, never needed#lval_old!=lval_new
*#lval_new != lval_old*expr
==#(!!lval_new) != (lval_old == expr)
.TE
.LP
== is used because it's a likely typo.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval -= expr
Alternate # Rule out with
+=, never needed#lval_old!=lval_new
.TE
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval *= expr
Alternate # Rule out with
/=, never needed#lval_old!=lval_new
+=#lval_new != lval_old + expr
&=lval_new != lval_old & expr
.TE
.LP
&= is used because it's a likely typo.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval /= expr
Alternate # Rule out with
*=, never needed#lval_old!=lval_new
%=#lval_new != lval_old % expr
.TE
.bp
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval %= expr
Alternate # Rule out with
never needed#lval_old!=lval_new
/=#lval_new != lval_old / expr
^=#lval_new != lval_old ^ expr
.TE
.LP
^= is a likely typo.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval <<= expr, lval >>= expr
Alternate # Rule out with
the other, never needed#lval_old!=lval_new
.TE
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval &= expr
Alternate # Rule out with
never needed#lval_old!=lval_new
|=#lval_new != lval_old | expr
*=#lval_new != lval_old * expr
^=#lval_new != lval_old ^ expr
.TE
.LP
^= and *= are likely typos.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval |= expr
Alternate # Rule out with
never needed#lval_old!=lval_new
&=#lval_new != lval_old & expr
+=#lval_new != lval_old + expr
.TE
.LP
+= is a likely typo.
.TS
center allbox tab(#) ;
c s
c c 
l l. 
lval ^= expr
Alternate # Rule out with
never needed#lval_old!=lval_new
|=#lval_new != lval_old | expr
%=#expr == 0 || (lval_new != lval_old % expr) 
&=#lval_new != lval_old & expr
.TE
.LP
%= and &= are likely typos.
.LP
expr == 0 rules out the %-substitution because such an alternate
program would get a divide-by-zero error and hence could not be
correct.
.LP
.TS
center allbox tab(#) ;
c s
c c .
lval++, lval--, ++lval, --lval
Alternate # Rule out with
.TE
.LP
There is no instrumentation.  Any evaluation of these expressions has
a different value from any of the others; hence, simple execution
rules out those substitutions.
.LP
Similarly, any evaluation of --lval is distinguishable from -lval
because the value of lval is different.
.bp
.NH 2
Flow of Control
.LP
.TS
center allbox tab(#) ;
c s
c c 
l l. 
while
Alternate # Rule out with
if # two or more loop executions
.TE
.LP
In the current implementation, operand coverage for \fHwhile\fR statements is 
the same as loop coverage.  The \fBgreport\fR message is the same:
.nf

"example1.c", line 9: loop zero times: 1, one time: 0, many times: 0.

.fi
Executing the \fHwhile\fR test more than once rules out the possibility that it
should have been an \fHif\fR.
.LP
Unfortunately, there's no equivalent condition that rules out the more
common fault where an \fHif\fR should have been a \fHwhile\fR.
.LP
.TS
center allbox tab(#) ;
c s
c c .
goto, continue, break
Alternate # Rule out with
.TE
.LP
There is no instrumentation for \fHgoto\fR; if the \fHgoto\fR target is incorrect, the
error will likely be detected by a test that executes the \fHgoto\fR, which
branch coverage requires.
.LP
Similarly, the error where a \fHcontinue\fR should have been a \fHbreak\fR, or a
\fHbreak\fR a \fHcontinue\fR, will likely be detected if executed, especially if
loop coverage is required.
.NH 1
Operand Coverage
.LP
In operand coverage, values of variables or constants are compared against each other.
The following are all operands:
.nf

	A
	1
	Array[1]
	Array[1+1]
	S.field
	S->field
	*ptr
	*(ptr+S.field)

.fi
Operand coverage is a requirement on pairs of operands.  Suppose we
have a program containing this code:
.nf

	function(A);

.fi
Operand coverage might require the following:
.nf

	A != B
	A != C
	A != D

.fi
This could be accomplished in one test in which the variables had
these values:
.nf

	A == 0, B == 1, C == 1, D == 1

.fi
or it might take three tests:
.nf

	A == 0, B == 1, C == 0, D == 0	=> Rules out B (A!=B).
	A == 1, B == 0, C == 1, D == 0  => Rules out B (A!=B) and D (A!=D).
	A == 0, B == 0, C == 1, D == 0  => Rules out C (A!=C).

.fi
The idea of operand coverage is that if a particular operand has the
same value as another in every test, we have no evidence that the
correct program shouldn't use the other operand.  (Of course, if the
operand has the same value in every possible execution, it doesn't
matter which we use.)
.LP
Output is in terms of the existing operand and the hypothesized
substitution.  For example, given
.nf

if (A < F(5, A))

.fi
output might be 
.nf

"example1.c", line 9: operand A might be B.
"example1.c", line 9: operand A might be C.
"example1.c", line 9: operand A might be constant.
"example1.c", line 9: operand 5 might be A.
"example1.c", line 9: operand A (2) might be B.

.fi
(In the third line, notice that there is no way to indicate which
constant A might be.)
.NH 2
Compatibility
.LP
A pair of operands can be compared only if C defines inequality
between them.  For example, integers can be compared to floats, but
floats cannot be compared to whole structures.  (There is almost no
circumstance in which a float should have been a structure without
generating a compiler error or warning.)
.LP
This is not ideal.  For example, consider the following code:
.nf

   func(s1, s2)
   char *s1, *s2;

   if (func2(s1))
	return 5;
   ...

.fi
GCT will rule out the substitution of S2 for S1 if S2!=S1.  However,
this comparison of pointers is not optimal.  In this context, S1 and
S2 are intended to be strings.  A better comparison would be to rule
out the substitution if
.nf

	string_not_equal(s1, s2)

.fi
However, this cannot be done automatically, since GCT has no way of
knowing that these character pointers represent null-terminated
strings.  
.NH 2
Selecting Alternates
.LP
There may still be an infinite number of type-compatible operands.
How are alternates selected?  For example, should A be compared to all
of these possible operands?
.nf

	Array[0]
	Array[1]
	Array[2]
	...
	Array[A]
	Array[B]
	Array[C]
	...
	Array[A+B]
	...

.fi
Clearly, this is not useful.  GCT uses two general rules to pick
alternate operands.  Each kind of operand (e.g., array references,
pointer dereferences) extends, restricts, or
modifies the set of alternates produced by those two rules.
.IP \fBconstants\fR
For any operand, all constants of a compatible type are potential
alternates.  
(For variables, this
infinite set of comparisons can be implemented by requiring that the
variable actually take on at least two values.)
.IP "\fBlocal variables\fR"
All variables of a compatible type, defined in the same function, are
potential alternates.  Global variables are \fInot\fR alternates.
There are often a surprising number of them (hidden in include
files) and not testing for them doesn't (yet) seem to lead to any
loss of effectiveness.
.sp
For the example above, A would be compared to B, C, D, but not to any
array reference.  An array reference like Array[A] would be compared
to A, B, C, D, etc., but not to any other array reference.
(Under this rule -- we'll see in the section after next how comparisons
between array references are generated.)
.NH 2
Weak Sufficiency
.LP
It's not always enough just to check for differing values.  Consider,
for example,
.nf

    if (var1 == var2)

.fi
Suppose \fHvar2\fR should be \fHvar3\fR.  Suppose further that \fHvar1 == 1\fR, \fHvar2 ==
2\fR, and \fHvar3 == 3\fR.  \fHvar2!=var3\fR, so operand coverage is satisfied.
However, the \fHif\fR statement has the same value in both cases, so the
fault might quickly "damp out" and become unlikely to be detected.  We
really want the relational expression to take on a different value.
.LP
Consequently, if a variable comparison is made when the variable in
question is the ENTIRE right-hand or left-hand side of a relational
expression, then not only must the comparison reveal a difference, but
the results of the relational operator must be different.
.LP
This rule, whose technical name is \fIweak sufficiency\fR [Marick91b], will
certainly cause you confusion at first.  You will have an expression
like
.nf
	
	f(a, b, c)
	{
   	   if (a < b)
	   ...

.fi
and see this message from \fBgreport\fR
.nf

"example1.c", line 9: operand B might be C.

.fi
and say, "That's impossible -- the test case was F(1, 2, 3) and
2!=3", having forgotten that, because of weak sufficiency, you must
instead satisfy this coverage condition:
.nf

	(a < b) != (a < c)

.fi
The early annoyance will pay off in better tests.
.LP
.NH 2
Weak Sufficiency for Compound Operands
.LP
Weak sufficiency also applies to compound operands like array
references, structure field references, and so forth.  The rule is
similar: Whenever an operand is immediately contained in a larger
operand, the entire containing operand must have a different value
from the operand formed by substituting the alternate contained
operand.  Some examples will make this clear:
.sp
Array[A] must differ from Array[B].  It is not enough for A to differ
from B.
.sp
Array[Array2[A]] must differ from Array[Array2[B]].
.sp
*PTR must differ from *PTR2.  It is not enough for PTR to differ from
PTR2.
.sp
However, in the case of *(ptr+1), we only require PTR to differ from
PTR2.  We do \fBnot\fR require *(PTR+1) to differ from *(PTR2+1), 
because PTR is not immediately contained in the dereference.
(The increased difficulty of devising test cases for such comparisons
doesn't seem to be worthwhile.)
.fi
.NH 2
Refinements for Particular Kinds of Operands
.NH 3 
Constants
.LP
Constants follow the general local variable rule.  Thus, you might
expect to see messages like
.nf

"lc.c", line 153: operand 3 might be c. 
"lc.c", line 252: operand '{' might be index. 
"lc.c", line 919: operand "panic: %s" might be reason. 

.fi
The constant rule would seem to be unneeded:  what's the point of
comparing a constant to another constant?  In general, none.  But
there is a point when weak sufficiency holds.  Consider
.nf

if (a < 5)

.fi
GCT will generate tests that require you to demonstrate that no other
constant but 5 would do.  In this case, setting A==5 rules out any
constant greater than 5.  (If 5 should have been 6, say, the if
statement would branch the other way.)  Setting A=4 rules out any
constant less than 4.  (If 5 should have been 4, the if statement
would again branch the other way.)  Hence, 5 is likely to be correct.
.LP
In such cases, the message from \fBgreport\fR will be "5 might be
another constant".  Here are the various cases, and coverage conditions
that will eliminate them:
.nf

	A < 5
		A==4
		A==5
	A <= 5
		A==6
		A==5
	A > 5
		A==6
		A==5
	A >= 5
		A==4
		A==5
	A != 5
		A==5
	A == 5
		A==5

.fi
.NH 3 
Sizeof
.LP
The \fIsizeof\fR operator is a constant.  
Constant substitutions are done for \fIsizeof\fR operators used in
relational expressions.
Variable substitution tests
aren't done -- it's unlikely that a sizeof expression should have been
a variable.
.NH 3
Array References
.LP
The usual constant and variable substitution tests are used for array
references.  Expect to see messages like
.nf

"lc.c", line 869: operand chars[...] might be ch.
"lc.c", line 869: operand chars[...] might be constant.

.fi
.LP
For an operand like Array[A] you will also see messages like
.nf

"lc.c", line 869: operand A might be B.

.fi
As discussed in section 4.6.4, this means that Array[A] must differ
from Array[B].  Notice, however, that GCT cannot blindly insert such
comparisons: suppose B had the value -100,000,000?  They are made only
if 0 <= B < A.  Expect to be confused several times because you know
that B is different from A, but you still get the \fBgreport\fR
message that A might be B.  You've forgotten that B must both be
different than A and also safe as an index.
.LP
GCT will also consider B ruled out if B<0, though this is less reliable.
.LP
For any array reference, GCT also requires a test case in which
Array[A] differs from Array[A-1].  This encourages non-homogeneous
test arrays, which are much more likely to find faults.  Of course,
such a test can only be made if A>0.
.LP
GCT also requires test cases where Array[5] differs from Array2[5] (or
Array2 is null).  These test cases are dangerous if Array2 is
uninitialized.  The \fB-array-substitutions\fR or \fB-dereference\fR
options turn them off.
.NH 3
FIELD REFERENCES
.LP
This discussion applies to both references of the form A.field and
also P->field.
.LP
The usual constant and variable substitution tests are used, so you'll
see messages like
.nf

"lc.c", line 476: operand name_tally->pure_code might be constant.
"lc.c", line 476: operand name_tally->pure_code might be B.

.fi
In addition, the tests must rule out substitutions of a different
field in the same structure.  For example, if the structure is defined
as 
.nf

	struct S
	{
	   int field1;
	   int field2;
	};

an operand like p->field1 will yield this message:

"lc.c", line 476: operand p->field1 might use field field2.

.fi
The normal variable substitution on P, when combined with weak
sufficiency, will require that you rule out possible substitutions
like
.nf

	q->field1

.fi
Failing to do so will yield a message like
.nf

"lc.c", line 476: operand p might be q.

.fi
.LP
Notice that 
.nf

	p->field is compared with p->field2
and
	p->field is compared with q->field
but
	p->field is \fInot\fR compared with q->field2.

.fi
Double typos of this sort are rare and are likely to be caught by 
tests adequate for single typos [Offutt92].
.NH 3
Dereferences
.LP
Pointer dereferences use the standard constancy and variable
substitution tests.  Expect to see messages like:
.nf

"lc.c", line 250: operand *p might be argc.
"lc.c", line 250: operand *p might be constant.

.fi
You will also see messages like
.nf

"lc.c", line 250: operand p might be q.

.fi
Because of weak sufficiency, you must construct test cases such that 
*p != *q.
.NH 2
Miscellaneous
.LP
There is no instrumentation for the address-of operator.  Any likely
alternate operand for &var (such as &var2) will almost always
yield a different value; hence, merely executing the expression is
enough of a coverage condition.
.LP
There is no instrumentation for casts.  Although there are faults
associated with cases, I don't have enough of them yet.
