1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
# Atelier Property-Based Testing
Ce répertoire est dédié à l'atelier Property-Based Testing de [Lambda Nantes](https://mobilizon.fr/@lambdanantes).
## Contenu
Le but de cet atelier est de mieux comprendre le _Test de propriétés_ ou _Property-Based Testing_ (PBT) en:
1. pratiquant sur des exemples concrets,
2. codant une implantation minimale de PBT dans un langage quelconque.
### Principaux concepts
* *Propriété*: une assertion qui doit être vraie pour un ensemble de cas de test
* *Cas de test*: une valeur pour laquelle la propriété doit être vérifiée
* *Générateur*: une fonction qui produit des cas de test de manière pseudo-aléatoire
* *Minimiseur*: une fonction pour produire un _contre-exemple minimal_ à partir d'un cas de test lorsqu'une propriété échoue
En pseudo-Javascript, la boucle principale d'un test de propriété ressemble à ceci:
```javascript
function testProperty(seed, property, generate, shrink) {
let gen = generate(seed);
for (let i = 0; i < MAX_SUCCESS; i++) {
let x = gen();
if (!property(x)) {
let y = findMinimalCounterExample(x, property, shrink);
return { success: false, counterExample: y , seed };
}
}
return { success: true, seed };
}
```
* `seed` est une graine pour le générateur pseudo-aléatoire contenu dans `generate`. Cela permet de garantir la reproducibilité des tests en cas d'échec, bien sûr dans l'hypothèse que la fonction `property` soit déterministe.
* `generate` est une fonction qui prend une graine et retourne une fonction qui génère des cas de test. Le générateur est spécifique aux cas de tests et à la propriété à tester.
* `shrink` est une fonction qui prend un cas de test et retourne une liste de cas de test plus petits, pour une définition appropriée de "plus petit"
* `MAX_SUCCESS` est un paramètre qui limite le nombre de cas de test générés avant de considérer la propriété comme vérifiée
La fonction `findMinimalCounterExample` peut s'exprimer récursivement comme suit:
```javascript
function findMinimalCounterExample(x, property, shrink, depth = 0) {
let xs = shrink(x);
let counterexample = x;
let shrinks = depth;
for (let x' of xs) {
if (!property(x')) {
let shrink = findMinimalCounterExample(x', property, shrink, depth + 1);
if(shrink.shrinks > depth) {
counterexample = shrink.counterexample;
shrinks = shrink.shrinks;
}
}
}
return {counterexample, shrinks};
}
```
## Ressources
Quelques liens intéressants glanés au fil de mes recherches sur le sujet :
* [QuickCheck](https://hackage.haskell.org/package/QuickCheck) : la bibliothèque originelle de PBT pour Haskell
* [Shrinking challenge](https://github.com/jlink/shrinking-challenge) : un répertoire de problèmes intéressants pour étudier le comportement des _minimiseurs_
* [arbtest](https://github.com/matklad/arbtest) : une bibliothèque minimale de PBT pour Rust
* [Hypothesis](https://hypothesis.readthedocs.io/en/latest/) : une bibliothèque de PBT pour Python
* [The sad state of property-based testing](https://stevana.github.io/the_sad_state_of_property-based_testing_libraries.html) : un historique et une réflexion approfondie sur l'état de l'art du PBT, le constat que les idées et outils "universitaires" sont toujours peu utilisés dans l'industrie, et des pistes pour améliorer la situation, avec une discussion intéressante sur [lobsters](https://lobste.rs/s/uutqvn/sad_state_property_based_testing)
* [Testing the hard stuff and staying sane](https://www.youtube.com/watch?v=zi0rHwfiX1Q) : une vidéo de John Hughes, l'inventeur de QuickCheck, qui explique les bases du PBT et du Model-Based Testing
* [quickcheck-dynamic](https://hackage.haskell.org/package/quickcheck-dynamic) : une bibliothèque de Model-Based Testing en Haskell basées sur QuickCheck
* [QuickCheck](https://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/quick.pdf) : l'article originel de John Hughes et Koen Claessen introduisant QuickCheck
* [Testing monadic code with QuickCheck](https://research.chalmers.se/publication/170517) : la suite du précédent article pour appliquer le PBT sur du code maintenant un état ou plus généralement produisant des effets de bord
* [Finding race conditions in Erlang with QuickCheck](https://smallbone.se/papers/finding-race-conditions.pdf) : l'application du PBT sur des problèmes de concurrence en Erlang, suivi de [Experiences with QuickCheck](https://publications.lib.chalmers.se/records/fulltext/232550/local_232550.pdf). Ces articles et d'autres cités dans _The sad state of property-based testing_ sont particulièrement intéressants pour les praticiens car ils détaillent des cas d'utilisation concrets et des retours d'expérience sur l'utilisation de QuickCheck dans un contexte industriel
* [Using relational problems to teach PBT](https://cs.brown.edu/~tbn/publications/wnk-pj20-pbt.pdf) : une étude sur l'impact de l'apprentissage du PBT (par exemple sur un [tri topologique](https://cs.brown.edu/courses/cs195y/2019/historical/oracle.pdf))
* [Choosing properties for PBT](https://fsharpforfunandprofit.com/posts/property-based-testing-2/)
* [PBT in practice](https://harrisongoldste.in/papers/icse24-pbt-in-practice.pdf): une étude à base d'entretiens sur l'efficacité _en pratique_ du PBT
* [Integrated vs. type-based shrinking](https://hypothesis.works/articles/integrated-shrinking/) : un post du créateur d'[hypothesis](https://hypothesis.works), outil de PBT en Python, justifiant la _minimisation intégrée_
* Une [présentation](https://slides.com/ktorz/deck-7b00fc) sur le PBT de Matthias Benkort aka. [KtorZ](https://x.com/_KtorZ_)
## Un exemple en Haskell
```haskell
module Table where
import Data.List (group)
import Test.QuickCheck (
ASCIIString (getASCIIString),
Arbitrary (..),
PrintableString (getPrintableString),
Property,
listOf,
oneof,
vectorOf,
(===),
(==>),
)
data Value = IntValue Int | StringValue String | BoolValue Bool
deriving (Show)
data Table = Table {rows :: [[Value]]}
deriving (Show)
instance Arbitrary Value where
arbitrary =
oneof
[ IntValue <$> arbitrary
, StringValue . getPrintableString <$> arbitrary
, BoolValue <$> arbitrary
]
instance Arbitrary Table where
arbitrary = do
rowLength <- arbitrary
Table <$> listOf (vectorOf rowLength arbitrary)
prop_table_are_matrices :: Table -> Property
prop_table_are_matrices (Table rows) =
(length rows > 100) ==>
let rowLengths = map length rows
in length (group rowLengths) === 1
```
## Bricoler son framework de PBT
Voir [ts](ts/README.md)
|
