Restriction du dictionnaire

À l'épisode précédent, je terminais en disant que le code de la restriction du dictionnaire n'était pas encore disponible. Il l'est à présent sur GitHub à la révision 20d8c96…

Dans cet épisode, je vais montrer comment j'ai ajouté la fonctionnalité de filtre au dictionnaire et expliquer les choix.

Mais avant d'aller plus loin, regardons un peu comment est architecturé le dictionnaire dans La Grille.

• Dictionary : c'est l'interface d'un dictionnaire. On peut ajouter et enlever des mots, vérifier qu'un mot est valide, connaître le nombre de mots stockés et y chercher un mot à partir d'un mot incomplet (PartialWord). Connaître le nombre de mots servent pour les tests unitaire. Nous verrons plus tard à quoi sert d'enlever un mot.
• DicionarySimpleImpl : c'est une implémentation simpliste de Dictionary et la seule qui existe pour le moment dans le programme. Le dictionnaire est stocké comme un vecteur de chaînes de caractères. La recherche d'un mot se fait en consultant la liste entière et vérifiant la validité de chaque mot. L'intérêt : le développement de ce dictionnaire s'est fait en un rien de temps et a permis de valider le fonctionnement du programme. L'inconvénient : on l'a déjà vu, cette implémentation est probablement la pire possible en terme de rapidité.
• DictionaryLog : toujours le même principe dans La Grille pour les logs pendant la recherche, le DictionaryLog se contente de déléguer à un autre dictionnaire les vrais traitement et se contente d'espionner ce qu'il se passe.

Du dictionnaire en lui-même est séparé le chargeur du dictionnaire. Par principe de séparation des responsabilités, un dictionnaire (Dictionary) ne doit pas s'occuper de charger lui-même ses données. Pourquoi en effet manipuler pendant la recherche un objet qui est capable de charger des données, alors que cela est fait au début du programme ? Et de manière plus générale, cette séparation permet d'appliquer n'importe quelle méthode de chargement à n'importe quel dictionnaire.

Actuellement, il n'y a qu'une méthode de chargement et qu'une implémentation de dictionnaire, cela peut donc sembler un peu théorique. Mais rapidement, je vais ajouter un autre dictionnaire, on a vu que celui-ci était bien trop lent. On pourrait alors se dire qu'il suffit de changer le code du dictionnaire actuel pour le rendre plus rapide, cela n'empêchera pas un dictionnaire de charger ses données.

Je ne ferrai pas comme ça. DictionarySimpleImpl existe et fonctionne. Ajouter un nouveau dictionnaire en changeant son code est une mauvaise méthode. En effet, tant que le nouveau dictionnaire ne sera pas fonctionnel, il sera impossible de l'utiliser mais tout aussi impossible d'utiliser l'ancien. Dans le cadre de La Grille, cela ne poserait pas beaucoup de soucis, mais dans un développement plus conséquent, il n'est pas souhaitable de rendre instable ou non livrable des fonctionnalités déjà utilisées.

Puisque DictionarySimpleImpl existe et qu'une interface de dictionnaire (Dictionary) existe, le mieux est d'écrire, à côté et avec un autre nom, un autre dictionnaire. Pendant le développement, puis lorsqu'il sera livré, il sera alors simple de changer d'implémentation utilisée. On pourra en outre comparer l'efficacité des implémentations.

Si dans le futur, DictionarySimpleImpl devient encombrant et qu'il n'a plus aucun intérêt, il pourra être enlevé sans douleur.

Tout cela pour revenir sur le fait que le chargement du dictionnaire doit se situer dans une autre classe. Le chargeur pourra s'appliquer à n'importe quelle implémentation de Dictionary et, de même qu'avec un dictionnaire, on pourra changer la méthode de chargement par une nouvelle sans impact sur le programme existant. On peut même imaginer des chargeurs de dictionnaire allant chercher différent formats.

• DictionaryReader : c'est donc l'interface d'un chargeur de dictionnaire. Sa seule méthode (abstraite) est Read, qui provoque le chargement. À vrai dire, il n'est même pas question de dictionnaire. L'interface est assez minimaliste et pourrait s'appeler Reader.
• OneWordByLineReader : c'est le chargeur actuel. Il prend à la construction un dictionnaire et un input stream. Le Read provoque le remplissage du dictionnaire depuis l'input stream en considérant que celui-ci est une liste de mots séparés par un retour à la ligne.

Si vous voyez SetFilter dans votre dépôt, c'est que vous avez la dernière version. C'est la méthode ajoutée pour la restriction du dictionnaire. Je la laisse de côté pour le moment. Mettez-vous plutôt sur la première révision du fichier (git checkout 80ad111efba33db71a8d14b29d0f05f08299c8fe).

Vous pouvez voir que le chargement du dictionnaire est on ne peut plus simple. Il repose sur la stl et sur boost pour qu'à chaque ligne, le mot soit envoyé à la fonction addToDictionary.

Où placer le filtre, dans le dictionnaire, dans le chargeur, ailleurs ?

S'il était dans le dictionnaire, cela signifierait que lors de l'insertion d'un mot, le dictionnaire devrait vérifier qu'il correspond bien aux demandes du filtre. C'est une responsabilité en plus et une responsabilité qui ne sert à rien pendant la recherche. Une fois le dictionnaire en place, il ne bouge plus.

On pourrait imaginer une façon de faire comme avec le principe des logs dans La Grille, avec un chaînage de classe. Malheureusement, le design des chargeurs ne le permettent pas facilement : un chargeur agrège un dictionnaire pour le remplir, il ne connait pas d'autre chargeur.

Le chargeur semble donc être l'endroit approprié. On peut imaginer qu'un chargeur connait le principe de filtre : une fonction qui recevra une chaîne de caractère et répondra vrai si celle-ci est un mot acceptable.

La Grille est développé en Test Driven Developent, ou développement piloté par les tests est une méthode de développement que j'utilise tous les jours. Je la trouve confortable et très efficace.

Très brièvement, le TDD impose qu'un test de ce que l'on attend soit écrit avant d'écrire le code qui répond au test. Pour plus de renseignements, allez voir sur le lien précédent. Vous en apprendrez aussi en continuant à lire les articles de ce site.

Puisque c'est le chargeur de dictionnaire qui va être modifié, c'est dans tests/testwordgrid/TestOneWordByLineReader.cpp que cela se passe. À l'origine, il n'y a qu'un seul test : when_read_calls_dictionary. Ce test construit un stream de mots, une doublure de dictionnaire, initialise le chargeur avec ceux-ci, lance la lecture, et vérifie que l'ajout d'un mot dans le dictionnaire a été appelé autant de fois qu'il y avait de mot.

J'aurais pu aussi vérifier que les mots envoyés au dictionnaire étaient bien les bons. Je m'en suis passé.

À propos de la doublure de dictionnaire : en anglais fake object ou mock object (ces derniers sont un peu plus sophistiqués), ces objets simulent le comportement d'un objet réel. En effet, dans un test unitaire, nous ne voulons tester qu'une seule chose à la fois. Si le chargeur utilisait un vrai dictionnaire, alors le test serait en train de tester le chargeur et le dictionnaire. Le MockDictionary du test (le mock est utilisé ici par abus de langage) est là pour se mettre à la place d'un vrai dictionnaire. Tout ce que cet objet fait, c'est compter les appels à InsertWord.

Il y avait trois mots dans le stream du test d'origine. J'en ajoute un quatrième, de taille différente, afin d'avoir un mot de 3 lettres, un de 4, un de 5 et un de 6.

Puis j'écris le code tel que je voudrais qu'il soit si j'avais à l'utiliser (puisque cela sera le cas). Je me positionne du côté client (certes, ça sera moi…). Je veux donc un filtre qui prendrait un nombre de lettre minimum et maximum (Filter::MinMax filter(3,4);) et je renseigne le chargeur avec ce filtre (reader.SetFilter(filter);). Je lance la lecture et je vérifie que InsertWord n'a été appelé que deux fois.

Et je compile (scons tests).

Bien entendu, ça ne compile pas du tout. Filter::MinMax n'existe pas, de même que SetFilter sur un chargeur. J'écris donc les squelettes de ce qui manque pour que cela compile. Une méthode SetFilter qui prend en paramètre une interface de type Filter et une implémentation de filtre se nommant MinMax.

À présent, ça compile, mais le test échoue en disant que 4 mots ont été insérés dans le dictionnaire, pas deux.

C'est bien normal, le code ajouté ne fait rien.

Pour cela, il faut modifier (par exemple) la fonction addToDictionary dans OneWordByLineReader.cpp en lui ajoutant un pointeur sur un filtre. L'ajout au dictionnaire ne se fait que si le pointeur est non nul et qu'il répond vrai lorsqu'on lui passe le mot.

Puis on remonte : puisqu'il faut passer un filtre à addToDictionary, il faut que Read accède à une instance de filtre et il faut aussi modifier l'appel à boost::bind pour y ajouter ce filtre. Cela nécessite donc que le chargeur ait pour membre un pointeur sur filtre, initialisé à NULL et mis à jour par un appel à SetFilter.

Une fois tout cela écrit, le test échoue toujours. C'est normal, puisque le filtre n'est pas écrit. Mais lancer les tests permet de s'assurer que ce qu'on a écrit compile bien. D'ailleurs, ça ne compile pas car l'interface Filter ne défini pas d'opérateur () utilisé dans addToDictionary.

En fait, il manque une étape dans le code archivé. Initialement, j'avais écrit localement au test un filtre qui ne filtrait rien, mais qui vérifiait qu'il était appelé. Petit à petit, ce filtre est devenu le filtre MinMax et a eu droit à son fichier personnel, extrait du test. Ce texte n'existe donc plus et seul le test de MinMax est resté en place.

Reste donc à écrire le filtre. Très simple, il est dans ReaderFilter.cpp. À noter qu'il n'a pas été testé directement, ce qui n'est pas conforme au TDD. Tant pis, c'est une petite liberté que je prends.

Je ne m'étendrai pas sur l'utilisation du filtre. J'ai ajouté deux options à la ligne de commande dans Options.cpp et je les utilise dans SolverFactory.cpp pour créer le filtre.

Ces fichiers ayant été fait très rapidement, sans une architecture correcte, j'y reviendrai peut-être une autre fois.

C'est tout pour le moment.

À bientôt.