[prev in list] [next in list] [prev in thread] [next in thread] 

List:       sqlite-users
Subject:    Re: [sqlite] MC/DC coverage explained wrong in the home page?
From:       Richard Hipp <drh () sqlite ! org>
Date:       2011-09-23 15:16:37
Message-ID: CALwJ=Mwqbt2AQ2kgsWYUxho0X05Hv4Rp38cUHVLGyJVL9vXxEA () mail ! gmail ! com
[Download RAW message or body]

Opinions vary on the exact meaning of MC/DC for a language (such as C) that
has short-circuit boolean operators.  You are advocating a more rigorous
view of MC/DC that what I have heard before.  This is not to say it is
wrong, only different.

For a decision of the form:

     if( A && B )...

The test suite for SQLite tries at least three cases:

   (1)  A false
   (2)  A true and B false
   (3)  A true and B true

You seem to be saying that this is only MC/DC if we split case (1) into two
subcases:

   (1a) A false and B false
   (1b) A false and B true

There are problems with this view, though.  In many instances, B is
undefined when A is false.  In other words, if A is false, any attempt to
calculate B will give undefined results - possibly a segfault.  SQLite
really does use the fact that && is a short-circuit operator in C and so
when A is false, it is technically illegal to make any conjectures about the
value of B.

Your argument is that there might be redundancy; that if B is always false
when A is false, then it would be possible to simplify the decision to just:

    if( B )...

True enough.  But there are countless ways to refactor a boolean
expression.  I don't think that MC/DC has any requirement that the number of
conditions be minimized, does it?

Your objections would be understandable if SQLite where written in Pascal or
Ada where AND and OR operators are not short-circuit and where the compiler
is free to reorder them if it sees fit.  But in C/C++ where the && and ||
operators are short-circuit, and where the tests must occur in a
well-defined order, things are different.  It is as if the && and ||
operators really marked boundaries between decisions, not conditions.

But the | and & operators used inside a decision are *not* short-circuit,
and in those cases, your objections are valid.  But those cases are rare,
and we strive to demonstration independence of conditions there using
testcase() macros.

One of the key benefits we derive from testing SQLite to 100% branch
coverage is that we end up testing the object code, not the source code.  So
even if the compiler makes a mistake, we will still likely catch it.  I
don't think your more rigorous definition of MC/DC is necessary to achieve
that goal, is it?


On Wed, Sep 21, 2011 at 4:36 PM, Sami Liedes <sliedes@cc.hut.fi> wrote:

> Hi!
>
> Looking at
>
>   http://www.sqlite.org/testing.html
>
> it seems to me that MC/DC coverage is explained wrong there. This in
> turn makes me wonder if SQLite tests really have 100% MC/DC coverage
> or if this claim is just based on mistaken understanding of MC/DC.
>
> The page explains:
>
> ------------------------------------------------------------
> Wikipedia defines MC/DC as follows:
>
> * Each decision tries every possible outcome.
> * Each condition in a decision takes on every possible outcome.
> * Each entry and exit point is invoked.
> * Each condition in a decision is shown to independently affect the
>  outcome of the decision.
>
> In the C programming language where && and || are "short-circuit"
> operators, MC/DC and branch coverage are very nearly the same thing.
> The primary difference is in boolean vector tests. One can test for
> any of several bits in bit-vector and still obtain 100% branch test
> coverage even though the second element of MC/DC - the requirement
> that each condition in a decision take on every possible outcome -
> might not be satisfied.
>
> SQLite uses testcase() macros as described in the previous subsection
> to make sure that every condition in a bit-vector decision takes on
> every possible outcome. In this way, SQLite also achieves 100% MC/DC
> in addition to 100% branch coverage.
> ------------------------------------------------------------
>
> I don't think the operative, clever thing in MC/DC is the second
> requirement, but the fourth one, and in it the important word is
> "independently". Contrary to what seems to be claimed in the last
> paragraph, "mak[ing] sure that every condition in a bit-vector
> decision takes on every possible outcome" (the second requirement)
> expressly is *not* sufficient for MC/DC. In addition to that, you need
> to show that "each condition in a decision [...] independently
> affect[s] the outcome of the decision" (the fourth requirement).
>
> That is, if you have arbitrary boolean conditions A, B and C (not
> necessarily independent of each other), and you have a branch like
>
>  if (A op B op C)
>
> the second condition means that you have to give test cases for the
> positive and negative of each A, B and C, and this is what seems to be
> explained by the page. That is, if you could provide only two test
> cases, one with A && B && C and the other with !A && !B && !C, that
> would satisfy the second condition.
>
> But the fourth condition requires something more: That each decision
> is shown to *independently* affect the outcome of the decision. That
> is, for each condition of A, B and C, you have to give two test cases
> where the difference in the test case both flips that *and only that*
> condition of these three while at the same time changing the branch
> taken.
>
> This is a kind of dead code test; you prove that none of the
> conditions (A, B or C) are superfluous, in that each of them
> *independently* can affect the outcome of the branch operation. So
> given the branch condition of (A op B op C), you need to give at least
> six test cases to satisfy the fourth condition:
>
> 1. A
> 2. !A && (B and C take the same value as in (1)) && (the branch taken
>   differs from (1))
> 3. B
> 4. !B && (A and C take the same value as in (3)) && (the branch taken
>   differs from (3))
> 5. C
> 6. !C && (A and B take the same value as in (5)) && (the branch taken
>   differs from (5))
>
> So, is SQLite really tested up to this standard? If so, perhaps the
> description of MC/DC in the above page should be improved; I think
> it's really quite misleading now.
>
>        Sami
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
drh@sqlite.org
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
[prev in list] [next in list] [prev in thread] [next in thread]