AccueilTPs solveur:TP4: Refactoring 1TP5: Refactoring 2TP6: Refactoring 3Comment rendre ?Questions / réponsesAmetice

TP 4 : 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 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 domaines 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 du domaine en explorant un arbre.
  • 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.

Notre outil de résolution de contraintes

Travail à faire :
  • Ce projet comporte un test d'intégration TestSolver. Utilisez-le et analysez les cas 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 d'addition, de soustraction, de multiplication et de division.
  • 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 :
    • Commencez, dans la classe de test, par définir la méthode ci-dessous qui va calculer l'intervalle des valeurs possibles de la fonction operation pour toutes les valeurs possibles de a et b. 
      private Interval exploreBiFunction(//
        BiFunction<Integer, Integer, Integer> operation, //
        Interval a, Interval b) {
    ...
}
    • Testez cette méthode avec l'addition et deux intervalles pour a et b.
    • Vous pouvez maintenant définir un nouveau test qui va
      • énumérer tous les intervalles a inclus dans [-8, 8] puis tous les intervalles b inclus dans [-8, 8] ;
      • pour chaque couple a,b vérifier que l'intervalle calculé par l'exploration (exploreBiFunction) est le même que celui renvoyé par la méthode add de la classe Interval.
    • 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. Vous pourrez ainsi, en quatre lignes, vérifier l'addition, la soustraction, la multiplication et la division.
  • 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) (attention : vous devez d'abord renommer les méthodes getXXX pour faciliter cette étape).

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. Isoler les méthodes de création du problème dans une nouvelle classe Builder (factory-method). Prévoir également un test unitaire pour cette classe.
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 trois variables (à vérifier avec un TU).
  • Modifiez l'analyseur afin qu'il évite de créer des variables et des contraintes qui ne sont pas nécessaires. Vérifiez cette amélioration avec le test unitaire. Vous allez devoir éliminer des variables anonymes au profit d'une autre. Cela consiste à (1) les rechercher et les remplacer dans les contraintes, (2)  fixer leur domaine un 0.
  • L'amélioration précédente a-t-elle un impact sur les problèmes résolus dans TestSolver ?
  • 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.