Arbres de librairies - Page 1

j'ai un algo à trouver mais j'ai peur de tomber dans des boucles sans fin.

Le problème est le suivant

j'ai N librairies (N connu et fixe)

chaque librairie peut déclarer avoir besoin d'utiliser une ou plusieurs autres librairies (mais pas elle même)

L'idée serait de proposer une représentation "graphique"

genre

LIB1
-LIB2
--LIB3
---LIB4
--LIB5
-LIB6
LIB7
-LIB5

pour
LIB1 n'utilisant rien,
LIB2 utilisant LIB1,
LIB3 utilisant LIB2,
LIB4 utilisant LIB3 et LIB1,
LIB5 utilisant LIB2 et LIB7,
LIB6 utilisant LIB1 et enfin
LIB7 n'utilisant rien

grâce à cet algo, en plus d'organiser les librairies pour un affichage amélioré, il serait intéressant de supprimer les liens redondants (par exemple : ici LIB4 utilise LIB3 donc ce n'est pas la peine de spécifier qu'il utilise LIB1)

Le gros problème c'est que les librairies à traiter peuvent faire des croisement/bouclages (LIB1 utilise LIB2, LIB2 utilise LIB3, LIB3 utilise LIB1). Le but serait de les identifier eux aussi.

Si vous connaissez un algo générique capable de gérer ça, je suis preneur.

pour le coup de "supprimer les flèches en trop", [google]algorithme graphe "reduction transitive"[/google].
pour le dessin, graphviz n'est pas mal.

[cross]

donc tu as bien un graphe acyclique au début ?

je vois à peu près ce que tu veux, mais il y a une ambiguïté dans tes specs qui n'apparaît pas dans ton exemple : est-ce que tu veux

LIB1
-LIB2
--LIB3
LIB4
-LIB2
--LIB3

ou

LIB1
-LIB2
--LIB3
LIB4
-LIB2

ou

LIB1
-LIB2
LIB4
-LIB2
LIB2
-LIB3

?

à vrai dire, je ne sais pas, actuellement j'ai une simple liste lib1..N avec pour chaque lib une popup qui affiche les autres libs utilisées.

Ensuite le vrai problème c'est quand on a une utilisation croisée de deux ou plus de librairies

L'objectif à terme est d'optimiser l'organisation du projet et l'ordre de génération des librairies (actuellement, pour contourner, on fait en deux passes, la premier avec un link open et la seconde avec un vrai link)

PS : ça me servirait aussi pour le taf

ok ben si c'est juste pour une visualisation "à la main" le mieux ce serait plutôt de faire comme le dit bookeldor avec une lib graphique

ce n'est pas juste pour ça, c'est aussi (et en fait avant tout) pour optimiser les générations/compilations

Pollux (./3) :
donc tu as bien un graphe acyclique au début ?

Non :

vince (./1) :
Le gros problème c'est que les librairies à traiter peuvent faire des croisement/bouclages (LIB1 utilise LIB2, LIB2 utilise LIB3, LIB3 utilise LIB1). Le but serait de les identifier eux aussi.

ah oui

vince (./7) :
ce n'est pas juste pour ça, c'est aussi (et en fait avant tout) pour optimiser les générations/compilations

ie le but serait d'accélérer le linking en mettant les libs dans un ordre qui minimise le nb de dépendances non résolues à chaque instant du linking, ou c'est plus compliqué que ça ?
j'avais tapé "en même temps" à la place de "en mettant", c'est grave docteur ?

c'est ça

dans l'absolu si on pouvait arriver à ordonancer les opérations pour faire le link en une seule passe ça serait idéal

le link se fait en plusieurs passes ?

actuellement oui

(l'opération compil&link n'est pas dissociable)

on fait un link "non bloquant" capable de se linker sur des objets manquants lors de la première passe

le projet n'est pas fonctionnel mais chaque librairie a désormais son objet correspondant, la seconde passe permet de se linker comme il faut

d'accord, mais du coup le link peut se faire en une seule passe seulement si chaque lib n'utilise que les libs avant elle dans la ligne de commande ? ou c'est possible aussi avec des dépendances circulaires du moment que les dépendances non encore résolues tiennent dans la RAM ?

réponse A

si il y a dépendance circulaire, il faudra faire deux passes, pas d'autre choix.

l'objectif est donc double :
- pouvoir générer en une passe (sauf si bouclage)
- pouvoir identifier les éventuelles boucles

alors dans ce cas-là il te suffit peut-être de faire un truc du style :

void print(LIB *lib) {
  if (lib->printed)
    return;
  if (lib->printing)
    erreur("pas possible en une passe");
  lib->printing = true;
  foreach (LIB *lib2 in lib->dependencies)
    print(lib2);
  printf("%s\n",lib->name);
  lib->printing = false;
  lib->printed = true;
}

?

je comprends peut être mal mais en quoi ton algo permet il de réordonner la passe ? (en supposant qu'il n'y ait pas de boucle)

ben il affiche toujours les dépendances de la lib avant la lib elle-même ^^

ah d'accord, j'avais pas envisagé ça comme ça.

bon, y'a plus qu'à voir si le bordel accepte la réentrance dans les fonctions de scripts...