Refactoring d'un composant logiciel (1/3)

Sommaire

Introduction

L'objet de cette séance est de vous faire travailler sur un système de résolution de contraintes (appelé solver) afin d'en améliorer la structure et de permettre ainsi de mieux le tester et de lui ajouter des fonctionnalités. C'est la base du processus de refactoring.

Résolution de contraintes

Le principe consiste à utiliser des variables entières associées à des intervalles et des contraintes qui définissent les solutions acceptables. Voila un exemple de problème à résoudre :

A dans [2, 5]
B dans [10, 13]
A+B = 14

qui admet les trois solutions ci-dessous

{A=2, B=12}
{A=3, B=11}
{A=4, B=10}

Les opérations disponibles sont l'addition, la soustraction, la multiplication et la division. Les relations possibles sont =, >, >=, <, <= et <> (la différence). La résolution de ce type de problème peut nécessiter l'exploration d'un espace assez vaste et des temps de calcul conséquents.

Note : La résolution passe par deux étapes :
  • Le solver tente d'affecter à chaque variable une des valeurs possibles en explorant un arbre. Il débute par les valeurs de A, puis, pour chaque valeur, il essaye les valeurs de B.
Arbre de recherche 
A = 2
    B = 10                impasse
    B = 11                impasse
    B = 12                <-- solution
    B = 13                impasse
A = 3
    B = 10                impasse
    B = 11                <-- solution
    B = 12                impasse
    B = 13                impasse
...
  • Après chaque affectation, les contraintes sont vérifiées par une étude des intervalles. Par exemple, avec A=5 et B dans [10,13] la contrainte A+B=14 n'a pas de solution. Donc A=5 est une impasse alors que nous n'avons pas affecté la variable B. Cette approche permet de réduire la taille de l'arbre de recherche.

Notre outil de résolution de contraintes

Travail à faire :
  • Clonez votre projet dans votre IDE.
  • Ce projet comporte un test d'intégration TestSolver. Utilisez-le et analysez les tests proposés (notamment TestABC). Ce dernier test va résoudre un cryptarithme classique (voir d'autres exemples).

Améliorer notre outil

Modéliser un petit problème

Travail à faire :
  • Choisissez un autre cryptarithme (simple) et essayez de le modéliser (le décrire) puis de le résoudre.
  • Le solver vous donne le nombre de solutions trouvées et de noeuds explorés dans la phase de recherche. Tentez la stratégie reduceAndCheckIntervalsStrategy pour obtenir une amélioration.

Mieux tester la classe Interval

Le coeur de notre solver est une classe de manipulation des intervalles d'entiers.

Travail à faire :
  • Analysez la classe de test associée.
  • Enrichissez cette classe de test afin de valider les opérations de soustraction, de multiplication et de division (sur quelques valeurs).
Tests exhaustifs. Nous devons avoir une confiance absolue dans les résultats des opérations sur les intervalles. Pour arriver à ce résultat, nous allons mettre en place un test exhaustive :


Étape 1 : Construire des intervalles par exploration.

  • Commencez, dans la classe de test, par définir la méthode ci-dessous. Elle va effectuer l'opération operation (doc sur BiFunction) pour toutes les valeurs possibles des intervalles a et b afin de déterminer le plus petit résultat et le plus grand. Elle pourra ainsi construire l'intervalle a renvoyer. 
    private Interval exploreOperation(//
        BiFunction<Integer, Integer, Integer> operation, //
        Interval a, Interval b) {
    ...
}
  • Testez cette méthode avec l'addition de [3,10] et [-5,0].
  • Améliorez cette méthode pour traiter l'opération de division sur les intervalles [-10,10] et [-2,2] (les opérations peuvent générer des exceptions qu'il faut masquer).
Étape 2 : Construire tous les intervalles possibles.
  • Continuez en définissant la méthode ci-dessous :
private List<Interval> buildAllNotEmptyIntervals(int min, int max) {
    ...
}
  • Testez-la sur l'intervalle [0,9], vous devriez obtenir 55 résultats.
Étape 3 : Faire le test exhaustif de l'addition.
  • Vous pouvez maintenant définir un nouveau test qui va
    • construire avec buildAllNotEmptyIntervals la liste de tous les intervalles inclus dans [-8,8] (profitez de cette étape pour ajouter l'intervalle vide) ;
    • pour chaque couple d'intervalles (a,b) vérifier que l'intervalle calculé par exploration (exploreOperation) est le même que celui renvoyé par la méthode add de la classe Interval.
Étape 4 : Généraliser aux autres opérations.
  • Vous pouvez maintenant paramétrer le test ci-dessus avec deux lambdas : l'opération sur les entiers et l'opération sur les intervalles (voir ci-dessous). Vous pourrez ainsi, en quatre lignes, vérifier l'addition, la soustraction, la multiplication et la division.
private void testBiOperation(//
                 BiFunction<Integer, Integer, Integer> intOp, //
                 BiFunction<Interval, Interval, Interval> intervalOp, //
                 String name) {
    ...
}
  • Quel est le taux de couverture de la classe Interval ? Améliorez ce taux (notamment en couvrant la méthode div).

Améliorer Constraint

Travail à faire :
  • Créez un fichier source spécifique pour la classe Constraint.
  • Transformez cette classe en record (classe non-modifiable).

Construire le problème à résoudre

Travail à faire :
  • Bien que le problème à résoudre soit au centre de notre problématique, il n'existe pas de classe pour le représenter (les données sont déclarées directement dans Solver). Prévoir un record pour définir le problème et utilisez-le.
  • L'étape de construction du problème n'est pas clairement isolée et ne peut donc pas être correctement testée.
    • Extraire et isoler les méthodes de création du problème dans une nouvelle classe ProblemBuilder (builder). Prévoir également un test unitaire pour cette classe.
    • Utiliser ProblemBuilder dans la classe Solver afin de continuer à offrir les méthodes de création. L'interface ISolver ne doit pas être modifiée.

Simplifier le problème à résoudre

Travail à faire : Vous remarquerez que le Builder inclut un analyseur d'expressions et de contraintes. Ce dernier est imparfait car l'expression A+2=B va nous donner deux contraintes et quatre variables (à vérifier avec un TU). 
                               | T1 dans [2,2]         T1 et T2 sont
A+2 = B  --> Construction -->  | T2 = A + T1           des variables anonymes
                               | T2 = B
  • Modifiez l'analyseur afin qu'il évite de créer des variables et des contraintes qui ne sont pas nécessaires. Vous allez devoir éliminer des variables anonymes au profit d'une autre. Cela consiste à (1) les rechercher, (2) les remplacer dans les contraintes, (3) les éliminer. Nous devrions obtenir le résultat ci-dessous. Vérifiez cette amélioration avec un test unitaire.
T2 est éliminée au profit de B 
A+2 = B  --> Construction -->  | T1 dans [2,2]        T1 est une variable
                               | B = A + T1           anonyme nécessaire
  • L'amélioration précédente a-t-elle un impact sur les problèmes résolus dans TestSolver (normalement oui) ?
  • Dans le même esprit, vous pouvez éviter de poser des contraintes pour les relations qui comportent une constante et faire la réduction directement sur le domaine de la variable (pour, par exemple, X > 10). Tester cette amélioration.