Publié par
Il y a 8 mois · 12 minutes · Back

Testez vos invariants avec Scalacheck

Nous en sommes tous convaincus, le TDD, c’est bien ! Seulement, il nous arrive parfois de ne pas trouver la granularité de test adapté au besoin : 1 par cas d’utilisation, 1 par fonctionnalité… Existe-t-il un cas « nominal représentatif » ? Pour certains algorithmes, les tests unitaires « simples » ne suffisent pas. Je vous propose ici de découvrir une nouvelle approche du test unitaire : le « property-based testing » ou « test d’invariants ». C’est une forme de test répandue dans le monde de la programmation fonctionnelle grâce à son approche formelle.

Scalacheck est un framework de test de l’écosystème Scala. Il est le petit frère de Quickcheck, écrit en Haskell. Son approche de test n’est pas sans rappeler les tests paramétriques de JUnit. Il s’agit de créer des tests de « haut niveau » plutôt qu’un test unitaire par branche d’algorithme. Ces tests apportent une couverture plus élevée (voire exhaustive) et apportent un niveau de confiance élevé du code testé. Dans un objectif de documentation et même de spécification du code au travers de tests, le property-based testing apporte une nouvelle forme d’expressivité. On tentera de prouver la validité d’un algorithme non pas au travers de scénarios passants mais par le respect d’invariants.

Contrairement à JUnit, ScalaCheck vient avec une batterie de générateurs de valeurs pseudo-aléatoires. Cela donne la possibilité au développeur de générer des jeux de tests pour la description d’invariants.
Je vous propose ici un retour d’expérience sur l’utilisation de ce framework pour un projet qui gère des orchestrations de déploiement d’application.

Scalacheck est donc un outil de test capable de générer des valeurs et d’exprimer des contraintes afin de décrire des invariants. L’approche se nomme en anglais « property-based testing ». Par « propriété », il faut comprendre ici « invariant ». Un invariant est une règle intangible et assurée en toutes circonstances. Prenons pour exemple la fonction trim (suppression des espaces aux extrémités) sur une chaîne de caractères. Si on compare la longueur de la chaîne avant et après l’opération trim, il paraît logique de dire que la chaîne après l’opération est égale ou plus courte que sa source :

val s: String = ...
s.trim().length should be <= s.length

Nous voyons bien que cette règle doit tenir quelle que soit la valeur de s. La démarche ici s’apparente à la recherche de preuves en mathématiques. C’est une des raisons qui fait que ce type de tests existe dans l’univers Haskell.
Cela vient de la volonté de s’approcher d’une preuve formelle pour démontrer que l’algorithme fonctionne. Cette démarche est rendue possible si l’on respecte la « pureté » des fonctions. Cela a son importance, nous allons vite le voir.

Domaine de définition et preuve formelle

Le domaine de définition d’une fonction représente l’ensemble des valeurs possibles que la combinaison des paramètres en entrée peut prendre. L’ensemble des valeurs d’arrivée d’une fonction est appelé codomaine.

Prenons l’exemple d’une fonction pure qui prend en entrée un booléen. Un booléen possède deux valeurs, TRUE ou FALSE. Si cette fonction est dite « pure », sa valeur de sortie ne dépend que du paramètre en entrée. Il est donc trivial de mettre en place un test unitaire qui vérifie l’intégralité du domaine de définition de la fonction.
Le test de l’intégralité du domaine de définition nous apporte la preuve formelle que le code fonctionne comme attendu dans TOUS les cas possibles.

Si je travaille maintenant sur une fonction avec deux booléens en entrée, le domaine de définition comprend 4 valeurs qui sont toutes les combinaisons de deux booléens. Obtenir la preuve formelle reste accessible. Mais il faut bien dire qu’en dehors des types à faible cardinalité (Enum, Booléen…), la tâche est impossible.
Dans la pratique, on ne peut tester tous les cas possibles, on se contentera alors de prouver que la fonction n’est pas fausse pour une partie du domaine.

Prenons l’exemple d’une fonction de concaténation de chaînes de caractères. Ci-dessous un test unitaire tout à fait raisonnable :

test("concat"){
 val left = "abc"
 val right = "def"

 left + right should be("abcdef")
}

Le domaine de définition de la fonction est sans limite théorique à cause des chaînes de caractères. Avec ce test, j’ai prouvé que mon code n’est pas faux pour une seule combinaison ("abc";"def"). Impossible ici d’avoir la preuve formelle par un test automatisé que l’algorithme est correct. Mais que dire d’autres cas comme ("";""), ("a";""), ("";"1")…
Il y a bien sûr une infinité de combinaisons équivalentes qui n’ont pas d’influence sur l’algorithme. Mais ce qui est intéressant c’est l’étude de quelques cas aux limites. L’utilisation d’outils comme Scalacheck va permettre de systématiquement travailler sur les cas particuliers pour nous aider développer une implémentation correcte.

Comment tester les invariants

Le but de tester des invariants est de s’assurer que, pour un grand nombre d’exemples du domaine de définition d’une fonction, le code est correct. Pour ce faire, on va déléguer à Scalacheck le soin de générer des valeurs de test. Scalacheck fourni des générateurs prédéfinis pour les types de base, les chaînes de caractères en font partie.

Reprenons notre test de concaténation. On note rapidement que les valeurs dans left et right ne sont pas intéressantes pour la compréhension du test. Avec Scalacheck et son intégration dans l’excellent Scalatest, la structure du test ressemble à cela :

forAll(Gen.alphaStr: Gen[String], Gen.alphaStr: Gen[String]) {
  (left: String, right: String) =>
 //tester l'invariant ici
}

J’ai ajouté ici le type des variables pour expliquer le rôle de chacune. Gen.alphaStr est un générateur de chaines alpha-numériques. J’ai deux valeurs à tester, j’ai donc deux générateurs séparés. Les valeurs générées sont utilisables dans le corps de la fonction. Il suffit ensuite d’y implémenter notre test. On pourrait lire ce test en français :

*Pour toute chaîne de caractères «left» et toute chaîne de caractères «right», alors …*

Mais quelles sont les assertions? Il ne faut surtout pas réécrire l’implémentation dans le test. Il est donc interdit de concaténer les chaînes dans le code pour vérifier la valeur de la chaîne en sortie. Tester les invariants demande un peu plus de recul. Il faut plutôt se demander quelles propriétés sont continuellement admises par l’opération de concaténation. On peut tester que la longueur de la chaîne de résultat est strictement supérieure à la longueur de left, qu’elle commence bien par left, et se termine par right.

forAll(Gen.alphaStr, Gen.alphaStr) {
  (left, right) =>
    val result = left + right

    result should startWith(left)
    result should endWith(right)
    result.length should be > left.length
}

Au premier abord, cet invariant semble correct. Si je l’évalue de tête avec «abc» et «def», il fonctionne. Mais en le lançant, il échoue :

Message: 0 was not greater than 0
Occurred when passed generated values (
  arg0 = "",
  arg1 = ""
)

En effet, si « right » est vide, la troisième condition du test est fausse. Corrigeons le test :

forAll(Gen.alphaStr, Gen.alphaStr) {
  (left, right) =>
    val result = left + right

    result should startWith(left)
    result should endWith(right)
    result.length should be >= left.length
}

La démarche qu’impose Scalacheck permet de voir ses algorithmes d’une autre manière. Il tire vraiment toute sa puissance sur des structures de données plus complexes. Voyons comment le mettre en place sur un projet de la vraie vie.

Un cas de la vraie vie

Nous sommes dans le contexte d’une application de gestion de déploiement. Voici les grandes notions fonctionnelles :

  • un déploiement est un plan composé de blocs
  • un bloc est une structure composite qui peut contenir d’autres blocs (CompositeBlock) ou une liste de tâches (StepBlock)
  • une tâche (Task) est un script à exécuter

Cette structure composite nous permet de voir un déploiement comme un arbre. Les blocs sont des nœuds et les tâches des feuilles. Une tâche peut posséder un tag qui correspond à un groupe de serveurs sur lequel la tâche va être exécutée.

Pour des raisons d’optimisation de déploiement, on souhaite pouvoir envoyer sur le serveur le plus grand nombre de tâches consécutives en une seule fois. Pour cela, nous devons faire remonter les tags des tâches vers les blocs.

La story nous a été présentée avec deux cas fonctionnels différents :

  • Si toutes les tâches d’un même StepBlock contiennent le même tag, ce bloc porte lui aussi le tag
  • Si tous les blocs d’un même CompositeBlock possèdent le même tag, ce bloc porte lui aussi le tag

Les cas sont relativement simples mais la combinatoire est élevée de par la nature de la structure en arbre. Quels sont les invariants de ce système ? À partir des règles et du schéma ci-dessus on en trouve au moins deux :

  • Si un bloc a un tag, alors tous ses fils le possèdent aussi
  • Si un bloc n’a pas de tag, les fils ne possèdent pas de tag en commun

Il nous faut maintenant mettre en place les tests associés.

Développer un générateur personnalisé

Une instance de Task contient un attribut « tag » qui est une chaîne de caractères. Scalacheck vient avec plusieurs générateurs de base qu’il est possible de réutiliser. J’utilise donc ici un générateur de chaine de caractères pour le tag. En le combinant avec la méthode map, je crée un générateur de Task.

def tags: Gen[String] = Gen.listOfN(10, Gen.alphaNumChar).map(_.mkString)
def tasks: Gen[Task] = tags.map(tag => Task(tag))

tasks est un générateur de Task. Vous pouvez le tester en appelant tasks.sample. De la même manière, par composition, je peux avoir un générateur de StepBlock.

def stepBlocks: Gen[StepBlock] = Gen.nonEmptyListOf(tasks).map(taskList => StepBlock(taskList))

Pour un CompositeBlock, le cas est différent car la structure est récursive. Il nous faut un générateur de Block et de CompositeBlock, sachant qu’un CompositeBlock contient des Blocks.

def blocks: Gen[Block] = Gen.oneOf(stepBlocks, compositeBlocks)

def compositeBlocks: Gen[CompositeBlock] = Gen.nonEmptyListOf(blocks).map(blockList => CompositeBlock(blockList))

Mais un problème se pose. Cette génération pseudo-aléatoire a de fortes chances de ne jamais terminer à cause de cette récursion. Encore une fois, Scalacheck possède les bons outils. Il faut changer le générateur de CompositeBlock pour être sûr qu’il converge, car c’est lui qui porte la récursivité.

def compositeBlocks: Gen[CompositeBlock] = Gen.sized { size =>
  for {
    convergenceRate <- Gen.choose(0, size)
    nextIterationSize = size / Math.max(1, convergenceRate)
    convergingGenerator <- Gen.resize(nextIterationSize, blocks)
    blockList <- Gen.listOfN(size, convergingGenerator)
  } yield new CompositeBlock(blockList)
}

En assemblant toutes ces briques, j’ai maintenant à disposition un générateur évolué d’objets, capable de générer des cas de tests complexes et variés.
S’il est possible d’indiquer le nombre de valeurs générées souhaité, avec Gen.listOfN par exemple, il est souvent souhaitable de laisser Scalacheck proposer des valeurs sensibles. C’est ce qui a été fait dans l’exemple ci-dessus. En utilisant le combinateur Gen.sized, on peut récupérer le paramètre fourni par Scalacheck pour générer la liste de blocks. L’appel à Gen.resize(nextIterationSize, blocks) nous permet de mettre à jour ce paramètre de taille afin de le faire converger. On remarquera aussi que le facteur de convergence est choisi aléatoirement lui aussi afin de varier la forme et la profondeur de l’arbre.

Un petit exemple :

//Generating tasks
scala> tasks.sample.get
res2: Task = Task(nBsgcqhzex)

//Generating stepBlocks
scala> stepBlocks.sample.get
res9: Block = StepBlock(List(Task(7ldqHh2svr), Task(ndglgv8gtC), Task(xcwarjN3kj), Task(snc6eeyXul)))

//Generating blocks
scala> blocks.sample.get
res13: Block = StepBlock(List(Task(dpvKbGgoce))

scala> blocks.sample.get
res14: Block = 
CompositeBlock(
 List(
  StepBlock(List(Task(dpvKbGgoce))), 
  StepBlock(List(Task(iuqfaQIJSD),Task(qqsdqccgZE)))
 )
)

Reste maintenant à écrire notre test :

forAll(blocks)(checkTagRecursively)
 
private def checkTagRecursively(block: Block): Unit =
  block match {
    case CompositeBlock(blocks, Some(tag)) =>
      val blockTags = blocks.map(_.tag).toSet
      assertCommonTag(blockTags.flatten, tag)
      blocks.foreach(checkTagRecursively)

    case CompositeBlock(blocks, None) =>
      val blockTags = blocks.flatMap(_.tag).toSet
      assertNoCommonTag(blockTags)
      blocks.foreach(checkTagRecursively)

    case StepBlock(tasks, Some(tag)) =>
      val taskTags = tasks.map(_.tag).toSet
      assertCommonTag(taskTags, tag)

    case StepBlock(tasks, None) =>
      val taskTags = tasks.map(_.tag).toSet
      assertNoCommonTag(taskTags)
  }

private def assertCommonTag(tags: Set[String], tag: String): Unit =
  tags should be(Set(tag))

private def assertNoCommonTag(tags: Set[String]): Unit =
  tags.size should not be 1

Conclusion

Ce test nous a permis de tester un ensemble de règles sur des jeux de données variés. Hormis la construction du test, ce mode de pensée nous a amené à prendre du recul sur la fonctionnalité dans son ensemble et ainsi avoir une solution plus simple et plus complète qu’en accumulant les cas les uns après les autres.

Cependant, la courbe d’apprentissage du framework est plutôt difficile. Il faut se familiariser avec les différents générateurs de base et apprendre à les composer.

On notera également que la génération des valeurs n’est pas totalement aléatoire. Le moteur de Scalacheck choisit en effet des valeurs « remarquables » (chaine vide, 0, -1, Int.MAX_VALUE…) pour tester rapidement les cas aux limites. Les messages d’erreurs fournies sont parfois cryptiques mais fournissent le jeu de données (généré) qui a causé l’échec du test ce qui permettra de facilement le reproduire.

Ce type de test n’est pas applicable partout et ne devrait pas être utilisé systématiquement à cause de sa complexité accrue. Cependant, si vous sentez que les cas testés ne sont pas représentatifs de la fonctionnalité, il peut être intéressant de tenter une approche par test d’invariant.

Pour aller plus loin, je vous conseille vivement le livre suivant: Scalacheck: The Definitive Guide.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *