Probleme – Valider une dichotomie de bout en bout

1. Un jeu de tests couvrant les arcs. Il faut prendre les deux issues de la boucle, les deux issues du test d'égalité, et les deux issues de la comparaison.

assert(cherche(t, 5, 10) == 0);    /* premier element    */
assert(cherche(t, 5, 30) == 2);    /* element du milieu  */
assert(cherche(t, 5, 40) == 3);    /* branche « t[m] < v » */
assert(cherche(t, 5,  5) == -1);   /* absent, sortie de boucle */

La mesure, par gcc –coverage puis llvm-cov gcov -b :

Lines executed:       100.00% of 15
Branches executed:    100.00% of 6
Taken at least once:  100.00% of 6

    8:    5:    while (g <= d) {          branch 0 taken 88%  branch 1 taken 13%
    7:    7:        if (t[m] == v) ...    branch 0 taken 43%  branch 1 taken 57%
    4:    8:        if (t[m] < v) ...     branch 0 taken 25%  branch 1 taken 75%

2. Non. Les quatre assertions passent. Cent pour cent des instructions, cent pour cent des arcs, et la fonction boucle indéfiniment sur cherche(t, 5, 50).

3. Les entrées qui révèlent la faute. En balayant toutes les valeurs de $5$ à $55$ de $5$ en $5$, avec un garde-fou qui interrompt au-delà de mille tours :

  v | version correcte | version soumise
 10 |                0 | 0
 15 |               -1 | BOUCLE INFINIE
 20 |                1 | BOUCLE INFINIE
 25 |               -1 | BOUCLE INFINIE
 30 |                2 | 2
 35 |               -1 | BOUCLE INFINIE
 40 |                3 | 3
 45 |               -1 | BOUCLE INFINIE
 50 |                4 | BOUCLE INFINIE
 55 |               -1 | BOUCLE INFINIE

Sept valeurs sur onze révèlent la faute, et notre jeu de tests avait choisi trois des quatre qui ne la révèlent pas.

Le raisonnement qui les aurait fait choisir n'est pas un critère de couverture : c'est le variant. La faute est g = m au lieu de g = m + 1. Le variant $V=d-g+1$ ne décroît alors plus strictement : quand $d=g+1$, on a $m=g$, et g = m laisse $g$ inchangé — la boucle repart à l'identique. La faute se manifeste exactement quand l'intervalle se réduit à deux cases et que la valeur cherchée est dans la seconde.

Cela dicte les tests : la dernière case, et toute valeur qui force la recherche à droite. C'est le test des limites du programme officiel — la première case, la dernière, juste avant, juste après — et il attrape ici ce qu'aucune couverture n'attrapait.

4. La propriété générale. Un critère de couverture porte sur le texte du programme, jamais sur son domaine d'entrée. Il garantit qu'aucune ligne n'est restée inexplorée ; il ne garantit rien sur les valeurs pour lesquelles ces lignes ont été exécutées. Les deux notions sont orthogonales, et il faut les deux :

• la couverture assure qu'on n'a pas oublié un morceau de code ;
• le partitionnement et les limites assurent qu'on n'a pas oublié une classe de données.

Et au-dessus des deux, la preuve : ici, l'étude du variant désigne l'entrée fautive au lieu de la chercher. C'est la répartition annoncée par le chapitre : « la preuve donne la certitude sur l'algorithme, le test attrape les fautes de transcription ».

int tours = 0;
while (g <= d) {
    assert(++tours <= 64);      /* dichotomie : au plus log2(n) + 1 tours */
    ...
}