Bonjour !

Après bien plus qu'une semaine, voici enfin le nouveau solveur de Setup en état de marche, après maintes péripéties, décrites ici.

Tout d'abord, pour ceux qui n'ont pas lu les précédentes news, j'ai refait le solveur de Setup car l'ancien, bien qu'élégant et intéressant (de par son utilisation de branches), avait quelques problèmes : occupation de mémoire pouvant exploser, possibilités ignorées. Malgré ces problèmes, il était déjà très bien placé dans la liste des solveurs de dépendances existants.

Constat et premier essai

Le 15 mai, alors que j'empaquette des paquets pour Logram, je me rends compte que le solveur plante dans certains cas (mise à jour avec beaucoup de possibilités). Je rédige alors ce journal présentant un nouveau concept de résolution des dépendances.

Je m'arme alors de courage et commence à coder ce solveur. Hélas, je me rends rapidement compte que ce que je présente ne fonctionne pas et pose bien trop de problèmes. Par exemple, il est impossible de faire se rejoindre les différentes branches quand elles ont des paquets en commun, alors que le reste de l'algo s'appuie dessus.

Deuxième essai et codage

Finalement, je me décide pour une solution «basique» : résoudre les dépendances au sens propre du terme. Le solveur est alors chargé d'explorer récursivement les paquets, et de construire un arbre avec leurs dépendances.

Problème, une dépendance peut proposer un choix (A dépend de B qui existe en deux versions, on peut choisir). Le graphe est adapté pour gérer tout ça, avec un système d'enfants ayant un ou plusieurs noeuds.

Cette transformation a la propriété, contre laquelle je me batterai jusqu'à ce que le solveur soit terminé, de transformé mon graphe en hypergraphe, une structure de donnée très obscure et qui a toujours été évitée. Je me lance donc dans l'inconnu inexploré même des plus grands mathématiciens.

Finalement, la construction du graphe se passe bien, et je rédige une news décrivant ce que j'ai fait.

Première difficulté : le pesage

Peser chaque noeud du graphe est assez facile. Maintenant, il faut propager ce poids. Cette action consiste, pour chaque noeud, à trouver son poids maximum et minimum en fonction de ses enfants et de leurs choix.

Première tentative : ça marche ! Je teste avec quelques choix et un graphe complet, ça ne marche plus .

Je réfléchis encore un peu (beaucoup), et coupe ma fonction de poids en deux : une fonction minMaxWeight qui s'appelle récursivement et qui appelle weightChildren, qui s'appelle elle-aussi récursivement.

Voici comment ces fonctions agissent :

• minMaxWeight ne fait pas grand-chose. Elle contente de s'appeler récursivement sur les noeuds enfants du noeud qu'on lui passe. Ainsi, l'arbre est exploré. Une fois les noeuds appelés, elle trouve également, pour chaque choix, quel enfant est le plus léger ou le plus lourd. C'est la clé de la fonctionnalité «Installation entre 67 Kio et 3 Mio».
• weightChildren prend comme paramètres un noeud principal et un noeud enfant. Son principe est assez simple : ajouter le poids du noeud enfant au noeud principal, puis s'appeler récursivement pour chaque enfant du noeud enfant, en passant le même noeud principal. Cette fonction permet, pour chaque noeud, de trouver le poids total que son installation ou suppression engendre. Cette fonction est appelée deux fois par minMaxWeight, une fois pour trouver le poids maximum, une fois pour le minimum.

Finalement, l'arbre est impeccablement pesé. J'y apporte encore quelques modifications, pour gérer les noeuds «non-voulus» (par exemple, A est en conflit avec B. On ajoute B comme paquet à supprimer. Mais si B n'est pas installé, il n'est pas voulu, et on ne doit pas afficher ça à l'utilisateur).

Exploration du graphe

Une fois l'arbre construit, et pesé, il faut le présenter à l'utilisateur. La complexité vient du fait que ce ne sont pas simplement des listes, où on prend la plus légère, agréamenté d'un système de «Suivant/Précédant» comme c'était le cas avant.

Ici, l'utilisateur construit lui-même sa liste. Il a plus de maîtrise, mais il doit aussi plus réfléchir. Heureusement, Setup s'occupe de faire en sorte que tout soit le plus simple possible. Il essaie de limiter les choix quand ils sont évidents, et fait en sorte qu'appuyer répétitivement sur ENTER donne la meilleure solution.

Cette partie a également posé quelques problèmes. En effet, tout cela est géré par une fonction récursive. Problème, quand on a un choix à faire, il faut quitter la fonction et demander à l'utilisateur de choisir.

Ok, mais une fois qu'il a choisi, comment on recommence ? Ah ben bien, c'est assez complexe.

La solution retenue est de stocker dans les noeuds des informations sur leurs récursions. Par exemple, quand la fonction entre dans un noeud, elle regarde si ce noeud est «neuf» (il n'a jamais été exploré), où s'il l'a déjà été, mais qu'un choix s'est proposé. Dans ce dernier cas, on continue là où on l'a laissé :

• exploreNode est la fonction récursive. Elle place ended à false si un choix se présente
• Ligne 709, on commence par ajouter le noeud à la liste des noeuds que l'utilisateur a choisi, s'il ne l'est pas déjà (et si ce n'est pas le noeud principal, qui est ignoré).
• Ligne 717, on quitte la fonction si le noeud n'est pas voulu (déjà installé, déjà supprimé, etc). On fait ça après l'ajout dans la liste car on a besoin des noeuds non-voulus pour gérer quelques cas de conflits.
• Ligne 726, un for qui ne contient pas d'initialisation. Quand on crée le noeud (ou qu'on remonte d'un choix, j'explique plus loin), currentChild est mis à 0. Si on retourne dans un noeud après avoir quitté une première fois cette fonction, à cause d'un choix, currentChild est comme on l'avait laissé . L'exploration peut alors continuer.
• Ligne 761, on regarde si l'utilisateur a choisi une possibilité. Si oui, on la prend. Si non, on essaie d'être intelligent, et de ne lui proposer un choix que si c'est vraiment nécessaire.
• Finalement, la fonction se termine avec une petite protection contre les récursions infinies.

Ouf ! Une belle fonction pas spécialement longue, mais assez complexe, où chaque ligne est influencée et influence au moins la moitié du code du solveur.

Le résultat

Assez bavardé, passons aux screenshots, et aux chiffres.

D'abord les chiffres, qui montrent l'ampleur du chantier :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

buildserver/worker.cpp       |    4 +-
libpackage/package.cpp       |   15 +-
libpackage/prackage.h         |    1 +
libpackage/packagelist.cpp   |  104 +---
libpackage/packagelist.h     |   29 +-
libpackage/packagesystem.cpp |   31 +-
libpackage/solver.cpp        | 1814 ++++++++++++++++++++++++++++++------------
libpackage/solver.h          |  109 +++-
libpackage/solver_p.h        |  106 +++
libpackage/weight.qs         |   75 ++-
setup/app.cpp                |   85 ++-
setup/app.h                  |   13 +-
setup/package.cpp            |  574 +++++++++-----
13 files changed, 2039 insertions(+), 921 deletions(-)

Et encore, ça n'est que le diff final. J'ai plusieurs fois refait des parties du solveur.

Les screens maintenant. Tout d'abord, voici ce que Setup présente lors d'une simple installation, sans choix. Ça n'a pas changé, vous êtes rassurés :

Ensuite, ça se complique. Less existe en deux versions, une installée, une non. Je demande à Setup d'installer «less». Il me propose le choix entre les deux versions, sachant qu'une des versions est déjà installée. Je choisis d'installer la mise à jour. Setup me détecte que c'est une mise à jour, et affiche la liste complète :

Ça peut paraître idiot, mais ça m'a pris près d'une heure de correction de bugs pour que ceci fonctionne : la suppression de la libc alors qu'on a des trucs installés qui en dépendent :

Petits problèmes

Le code marche, mais n'a pas un bon niveau de finition. Il y a encore quelques imperfections :

• Le serveur de construction est cassé, il utilise encore l'ancienne API du solveur. Ça ne prendra normalement pas trop de temps à corriger, mais je suis occupé pour le moment (début des examens).
• L'utilisateur doit plus réfléchir. Au lieu de choisir «Suivant» jusqu'à ce que ça lui plaise, il doit faire des choix, qui peuvent parfois mener à des erreurs. Je pense implémenter une vérification : explorer les choix et voir ceux qui mènent à un problème, pour le signaler à l'utilisateur (en éliminant aussi des choix, si par exemple il n'en reste plus qu'un de bon).
• Une belle gestion des erreurs manque encore. Normalement, tout est bon, mais c'est très peu testé.
• Le code du solveur est quasiment du C pur, sans utiliser les types de Qt. C'est excellent car très très rapide, mais il faut partir à la chasse aux leaks.

Voilà, bons tests.