Algorithme pour trouver les dépendances

Le problème exposé dans ce sujet a été résolu.

Bonjour,
J’écris en ce moment un générateur de code Ada pour de l’embarqué. Il permet de générer la description de messages (des types Ada) reçus et envoyés par un microcontrôleur dont le logiciel est fait en Ada.

Les messages sont des records (dans d’autre langage appelé "struct") qui ont des champs qui possèdes tous un type. Ça peut être des tableaux de records, des entiers…

Chaque type est donné dans un fichier. Par exemple un type allant de 0 à 127 appelé A, sera dans un fichier A.range.yaml. Un autre type B qui est un tableau de 15 éléments de type A sera dans un autre fichier B.array.yaml. Les fichiers YAML étant les points d’entrés du logiciel.

Pour cet exemple, il faut que mon logiciel me sorte comme fichier ads le fichier suivant :

type A_T is range 0 .. 127;

type B_Index_T is range 1 .. 15;
type B_T is array (B_Index_T) of A_T;

Dans ce cas là c’est assez simple, A n’ayant pas de dépendance par définition se retrouve forcément au début du fichier, suivi de B qui a forcément une dépendance (par définition encore une fois).

Mais si je prends un cas plus complexe, avec une structure qui contient des tableaux et ces tableaux qui contiennent d’autres structures avec eux-mêmes d’autres types composés… La question se pose alors :

Comment déterminer l’ordre dans lequel le générateur doit définir les types pour que le fichier Ada compile ?

J’imagine qu’il faut se pencher sur les graphs… Mais j’avoue être complètement novice dans ce vaste domaine. Auriez-vous des pistes ? Ou mêmes des idées d’algorithmes ?

Je vous remercie.

Salut,

Normalement, ton graphe de dépendance devrait être orienté et acyclique (donc sans boucle). Dans ce cas-là, on peut obtenir assez facilement un tri topologique, qui est le résultat que tu cherches à obtenir. C’est une liste linéaire des noeuds du graphe de dépendance qui respecte les relations de dépendances.

Ce n’est pas très compliqué à programmer, puisqu’on peut obtenir un tri topologique avec un algo proche d’un parcours en profondeur. Voir par exemple ce qu’on trouve sur Wikipédia à ce sujet.

Je fais aussi ma publicité au passage, puisque j’ai écrit un article sur un sujet proche : S’habiller dans le bon ordre grâce aux mathématiques. Dans cet article, j’utilise l’algorithme de Kahn.

+1 -0

Bonjour,

Ta problématique est en effet plus lié à un problème de graphe de dépendance que d’Ada. Comme le dit @Aabu, l’emploi d’un algorithme de tri topologique semble être la meilleure option ici.

Sinon, tu génères un .ads par type, et comme tu sais pour un type nn de qui il dépend, tu as juste à faire les with …; qui correspond au début de ton unité de compilation.

Par curiosité, tu fais de l’Ada en pro ou en perso ?

+0 -0

@Aabu, merci c’est exactement ce que je cherchais ! En plus un paquet python existe déjà dans la std pour faire ça : graphlib (même si tu dis que ce n’est pas trop compliqué, c’est toujours ça de moins à faire) :)

Par curiosité, tu fais de l’Ada en pro ou en perso ?

Heziode

Les deux ! J’ai la chance d’avoir trouvé un travail qui me permet de faire de l’Ada tous les jours comme langage principal et je continue à explorer ses possibilités et son efficacité à la maison.

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte