Bonjour 
,
Le solveur actuel de Setup, basé sur un algorithme intéressant à base de branches, fonctionne très bien dans l'immense majorité des cas, en étant très rapide.
Malheureusement, il souffre de deux problèmes :
- Le code est difficilement maintenable, plein de petits hacks. Certains trucs marchent uniquement grâce à la chance, en particulier tout ce qui est gestion des branches. Il y a beaucoup de traces d'essais-erreurs, des hacks, etc.
- Cette qualité de code, une des pires dans tout Setup (voire la pire depuis que j'ai refait l'installation des paquets) provoque de gros blocages. Dans certaines conditions, le solveur s'emballe et consomme toute la RAM disponible, sans trouver de solution. C'est inacceptable pour quelque-chose qui doit «juste marcher» chez les gens.
J'ai donc réfléchi à une amélioration de l'algorithme actuel, et ai trouvé l'algo le plus simple et le plus évident qu'on puisse imaginer. Il tient en moins de 1000 lignes (mais n'est pas encore complet, loin de là).
L'algo
En quelques mots : créer un arbre de dépendances. Simple. Il suffit de parcourir la base de donnée, d'ajouter les dépendances, retirer les conflits. La bonne métode bien naïve. Quand il y a des choix, c'est simple aussi, on les enregistre.
Par exemple, si A dépend de B qui dépend de C ou D, on a un arbre comme ceci :
Le tout est implémenté en presque pur C, avec très peu de Qt-ismes (tout de la gestion des pointeurs, quasiment pas de QList et QHash, c'est bien plus léger qu'avant).
Bon, maintenant qu'on a un arbre, il y a des détails à régler. Tout d'abord, il faut le peser. C'est expliqué dans mon journal, que je vous invite à lire.
Ensuite, pour ce qui est des dépendances en boucle, c'est géré tout seul par un side-effect. Pour les autres vérifications (pas installer un conflit, etc), c'est prévu mais pas encore fait.
Nouvelles fonctionnalités
Comme c'était assez facile d'avoir une base d'algo qui marche, j'en ai profité pour développer des trucs autours :
- «setup -G add setup» génère le graphe (en utilisant graphviz) des dépendances de Setup qui doivent être installées.
- «setup -G -nI add setup» fait la même chose mais avec les dépendances complètes, donc pas seulement ce qui sera installé. On a donc tout l'arbre, jusqu'à la LibC (alors qu'il s'arrête à Qt si Qt est déjà installé, normalement).
- Le paramètre -nI ignore donc ce qui est déjà installé, ce qui permet de forcer une réinstallation de toutes les dépendances d'un paquet si la BDD est cassée.
- Le paramètre -nD ignore les dépendances (comme pacman -Rd). Ainsi, si quelque-chose est cassé, on peut forcer la main à Setup. -nI -nD permet de forcer la réinstallation d'un paquet .
Et voilà le travail (le rond bleu représente un choix) :
Et si vous voulez voir ce que donne «setup -G -nI add setup», voici (Root est le noeud racine qui dépend de ce qu'on a demandé d'installer 
) : Fichiers PDF parce que le PNG est trop gros.
Le code est dans Gitorious, mais ne mettez pas à jour si vous utilisez vraiment Setup, l'installation ne marche pas, on ne sait que générer des graphes.
