Reordered blocks in graph view to avoid edge crossing.

1 files changed, 302 insertions, 100 deletions

diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 5785251..801929e 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -701,7 +701,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
         {
             leaving->straight = true;
             leaving->straight_level = target_level;
-            continue;
         }
 
         /* Est-ce une sortie de cluster ? */
@@ -715,10 +714,7 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
                     break;
 
             if (k == container->ranks_count)
-            {
                 leaving->cluster_exit = true;
-                continue;
-            }
 
         }
 
@@ -741,7 +737,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
             {
                 leaving->forced_straight = true;
                 leaving->straight_level = target_level;
-                continue;
             }
 
         }
@@ -911,102 +906,267 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
+*  Paramètres  : cluster = graphique de blocs à analyser.                     *
+*                root    = élément à ne jamais croiser dans la paternité.     *
+*                dir     = préférence à actualiser si possible. [OUT]         *
 *                                                                             *
-*  Description : Réorganise au besoin les liens entrants d'un bloc.           *
+*  Description : Détermine une direction préférée pour la suite du bloc.      *
 *                                                                             *
-*  Retour      : -                                                            *
+*  Retour      : false si une incapacité de détermination a été rencontrée.   *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
+bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGraphCluster *root, LeavingLinkDir *dir)
 {
-    size_t i;                               /* Boucle de parcours          */
+    bool result;                            /* Bilan à renvoyer            */
+    size_t i;                               /* Boucle de parcours #1       */
+    const leaving_link_t *leaving;          /* Lien sortant à traiter      */
+    GGraphCluster *iter;                    /* Boucle de parcours #2       */
+    LeavingLinkDir pref;                    /* Préférence du lien courant  */
 
-    qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+    result = true;
 
-    for (i = 0; i < cluster->ranks_count; i++)
-        sort_graph_rank_incoming_links(&cluster->ranks[i]);
+    for (i = 0; i < cluster->ba_count && result; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
 
-    sort_incoming_links_for_vspace_manager(&cluster->self);
+        if (!leaving->cluster_exit)
+            continue;
+
+        /* Validation d'une sortie du cluster d'origine */
+
+        for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
+            if (iter == root)
+                break;
+
+        if (iter != NULL)
+            continue;
+
+        pref = get_leaving_link_direction(leaving);
+
+        /* Si la direction est claire... */
+        if (*dir == LLD_NO_PREF)
+            *dir = pref;
+
+        /* Multiples directions, on ne sait pas trancher ! */
+        else if (*dir != pref)
+            result = false;
+
+    }
+
+    for (i = 0; i < cluster->ranks_count && result; i++)
+        result = get_graph_rank_exit_direction(&cluster->ranks[i], root, dir);
+
+    return result;
 
 }
 
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster  = graphique de blocs à consulter.                   *
-*                incoming = adresse de l'autre bout du lien concerné.         *
+*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
 *                                                                             *
-*  Description : Retrouve l'indice d'un lien entrant donné pour un bloc.      *
+*  Description : Réorganise au besoin les liens sortants d'un bloc.           *
 *                                                                             *
-*  Retour      : Indice à priori toujours valide.                             *
+*  Retour      : -                                                            *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
 {
-    size_t result;                          /* Indice à retourner          */
+    size_t i;                               /* Boucle de parcours          */
+    leaving_link_t **left;                  /* Liens à placer à gauche     */
+    leaving_link_t **center;                /* Liens à placer au milieu    */
+    leaving_link_t **right;                 /* Liens à placer à droite     */
+    size_t left_count;                      /* Quantité de liens à gauche  */
+    size_t center_count;                    /* Quantité de liens au milieu */
+    size_t right_count;                     /* Quantité de liens à droite  */
+    leaving_link_t *leaving;                /* Lien sortant à traiter      */
+    LeavingLinkDir pref;                    /* Préférence du lien courant  */
 
-    for (result = 0; result < cluster->ta_count; result++)
-        if (cluster->top_anchors[result]->other == leaving)
-            break;
+    /**
+     * On n'intervient que s'il y a lieu de le faire, notamment si les sorties
+     * du groupe de blocs ont une direction claire.
+     */
 
-    assert(cluster->ta_count);
+    pref = LLD_NO_PREF;
 
-    return result;
+    if (!g_graph_cluster_get_exit_direction(cluster, cluster, &pref))
+        goto done;
+
+    if (cluster->ba_count < 2 || pref == LLD_NO_PREF)
+        goto done;
+
+    left = NULL;
+    center = NULL;
+    right = NULL;
+
+    left_count = 0;
+    center_count = 0;
+    right_count = 0;
+
+    /* Réorganisation des liens */
+
+    for (i = 0; i < cluster->ba_count; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
+
+        if (SHOULD_BE_VERTICAL(leaving))
+        {
+            if (leaving->cluster_exit)
+                pref = get_leaving_link_direction(leaving);
+
+            else
+                pref = LLD_NO_PREF;
+
+        }
+        else
+        {
+            pref = LLD_NO_PREF;
+
+            if (!g_graph_cluster_get_exit_direction(leaving->other->owner, leaving->other->owner, &pref))
+                pref = LLD_NO_PREF;
+
+        }
+
+        switch (pref)
+        {
+            case LLD_TO_LEFT:
+                left = realloc(left, ++left_count * sizeof(leaving_link_t *));
+                left[left_count - 1] = leaving;
+                break;
+
+            case LLD_NO_PREF:
+                center = realloc(center, ++center_count * sizeof(leaving_link_t *));
+                center[center_count - 1] = leaving;
+                break;
+
+            case LLD_TO_RIGHT:
+                right = realloc(right, ++right_count * sizeof(leaving_link_t *));
+                right[right_count - 1] = leaving;
+                break;
+
+        }
+
+    }
+
+    /* Sauvegarde du nouvel arrangement */
+
+    assert((left_count + center_count + right_count) == cluster->ba_count);
+
+    cluster->ba_count = 0;
+
+    if (left != NULL)
+    {
+        qsort_r(left, left_count, sizeof(leaving_link_t *),
+                (__compar_d_fn_t)cmp_leaving_links,
+                (LeavingLinkDir []) { LLD_TO_LEFT });
+
+        for (i = 0; i < left_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = left[i];
+
+        free(left);
+
+    }
+
+    if (center != NULL)
+    {
+        for (i = 0; i < center_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = center[i];
+
+        free(center);
+
+    }
+
+    if (right != NULL)
+    {
+        qsort_r(right, right_count, sizeof(leaving_link_t *),
+                (__compar_d_fn_t)cmp_leaving_links,
+                (LeavingLinkDir []) { LLD_TO_RIGHT });
+
+        for (i = 0; i < right_count; i++)
+            cluster->bottom_anchors[cluster->ba_count++] = right[i];
+
+        free(right);
+
+    }
+
+    assert((left_count + center_count + right_count) == cluster->ba_count);
+
+    for (i = 0; i < cluster->ba_count; i++)
+        cluster->bottom_anchors[i]->index = i;
+
+    /* Application de la nouvelle disposition */
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        reorder_graph_rank_clusters(&cluster->ranks[i], cluster);
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        reset_graph_rank_allocation(&cluster->ranks[i]);
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        offset_x_graph_rank(&cluster->ranks[i], cluster->alloc.x);
+
+    g_graph_cluster_dispatch_x(cluster);
+
+    g_graph_cluster_set_y(cluster, cluster->alloc.y);
+
+ done:
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        visit_graph_rank(&cluster->ranks[i], g_graph_cluster_sort_leaving_links);
 
 }
 
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à analyser.                     *
-*                l2r     = indique si le lien trouvé part vers à droite. [OUT]*
+*  Paramètres  : cluster = graphique de blocs à consulter.                    *
+*                pos     = ordonnées minimale et maximale en bout. [OUT]      *
 *                                                                             *
-*  Description : Détermine si un cluster possède un lien sortant.             *
+*  Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
 *                                                                             *
-*  Retour      : true si le chef de file à un lien qui sort de l'ensemble.    *
+*  Retour      : true si un lien sortant a été trouvé, false sinon.           *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
+bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint pos[2])
 {
     bool result;                            /* Bilan à retourner           */
     size_t i;                               /* Boucle de parcours          */
-    leaving_link_t *leaving;                /* Lien manipulé               */
-    gint x1;                                /* Abscisse de départ de lien  */
-    size_t idx;                             /* Indice du lien entrant      */
-    gint x2;                                /* Abscisse d'arrivée de lien  */
+    const leaving_link_t *leaving;          /* Lien sortant à traiter      */
+    gint y;                                 /* Ordonnée rencontrée         */
 
     result = false;
 
-    for (i = 0; i < cluster->ba_count && !result; i++)
+    for (i = 0; i < cluster->ba_count; i++)
     {
         leaving = cluster->bottom_anchors[i];
 
-        if (leaving->cluster_exit)
-        {
-            result = true;
-
-            x1 = compute_leaving_link_position(leaving);
+        if (!leaving->cluster_exit)
+            continue;
 
-            idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving);
+        result = true;
 
-            x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx);
+        y = leaving->other->owner->alloc.y;
 
-            *l2r = (x1 < x2);
+        if (y < pos[0])
+            pos[0] = y;
 
-        }
+        if (pos[1] < y)
+            pos[1] = y;
 
     }
 
+    for (i = 0; i < cluster->ranks_count; i++)
+        result |= compute_graph_rank_min_max_bottom(&cluster->ranks[i], pos);
+
     return result;
 
 }
@@ -1014,69 +1174,75 @@ bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = premier graphique de blocs à analyser.             *
-*                other   = second graphique de blocs à analyser.              *
-*                l2r     = indique si le lien trouvé part vers à droite.      *
+*  Paramètres  : cluster = graphique de blocs à analyser.                     *
+*                origin  = cluster d'origine à considérer.                    *
 *                                                                             *
-*  Description : Compare deux clusters avec lien sortant.                     *
+*  Description : Retrouve s'il existe un lien entrant vers un bloc d'origine. *
 *                                                                             *
-*  Retour      : Bilan de la comparaison.                                     *
+*  Retour      : Lien vers le bloc d'origine trouvé ou NULL.                  *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r)
+const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *cluster, const GGraphCluster *origin)
 {
-    int result;                             /* Bilan à renvoyer            */
+    const leaving_link_t *result;           /* Lien trouvé à renvoyer      */
     size_t i;                               /* Boucle de parcours          */
-    gint cluster_y;                         /* Position de la sortie #0    */
-    gint other_y;                           /* Position de la sortie #1    */
-    leaving_link_t *leaving;                /* Lien manipulé               */
 
-    cluster_y = 0;
-    other_y = 0;
+    result = NULL;
 
-    for (i = 0; i < (*cluster)->ba_count; i++)
-    {
-        leaving = (*cluster)->bottom_anchors[i];
+    for (i = 0; i < cluster->ta_count && result == NULL; i++)
+        if (cluster->top_anchors[i]->other->owner == origin)
+            result = cluster->top_anchors[i]->other;
 
-        if (leaving->cluster_exit)
-        {
-            cluster_y = leaving->other->owner->alloc.y;
-            break;
-        }
+    return result;
 
-    }
+}
 
-    assert(i < (*cluster)->ba_count);
 
-    for (i = 0; i < (*other)->ba_count; i++)
-    {
-        leaving = (*other)->bottom_anchors[i];
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = premier graphique de blocs à analyser.             *
+*                other   = second graphique de blocs à analyser.              *
+*                origin  = cluster d'origine à considérer.                    *
+*                                                                             *
+*  Description : Compare deux clusters selon un de leurs liens d'origine.     *
+*                                                                             *
+*  Retour      : Bilan de la comparaison.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
 
-        if (leaving->cluster_exit)
-        {
-            other_y = leaving->other->owner->alloc.y;
-            break;
-        }
+int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGraphCluster **other, const GGraphCluster *origin)
+{
+    int result;                             /* Bilan à renvoyer            */
+    const leaving_link_t *leaving;          /* Accès au lien manipulé      */
+    gint x0;                                /* Première abscisse à traiter */
+    gint x1;                                /* Seconde abscisse à traiter  */
 
-    }
+    leaving = g_graph_cluster_has_origin(*cluster, origin);
+
+    assert(leaving != NULL);
+
+    x0 = compute_leaving_link_position(leaving);
+
+    leaving = g_graph_cluster_has_origin(*other, origin);
+
+    assert(leaving != NULL);
 
-    assert(i < (*other)->ba_count);
+    x1 = compute_leaving_link_position(leaving);
 
-    if (cluster_y < other_y)
+    if (x0 < x1)
         result = -1;
 
-    else if (cluster_y > other_y)
+    else if (x0 > x1)
         result = 1;
 
     else
         result = 0;
 
-    if (*l2r)
-        result *= -1;
-
     return result;
 
 }
@@ -1084,9 +1250,9 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
 *                                                                             *
-*  Description : Réordonne les blocs sortant du cluster au mieux.             *
+*  Description : Réorganise au besoin les liens entrants d'un bloc.           *
 *                                                                             *
 *  Retour      : -                                                            *
 *                                                                             *
@@ -1094,12 +1260,44 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
 *                                                                             *
 ******************************************************************************/
 
-void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster)
+void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
 {
     size_t i;                               /* Boucle de parcours          */
 
+    qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+
     for (i = 0; i < cluster->ranks_count; i++)
-        reorder_graph_rank_exit_blocks(&cluster->ranks[i]);
+        sort_graph_rank_incoming_links(&cluster->ranks[i]);
+
+    sort_incoming_links_for_vspace_manager(&cluster->self);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster  = graphique de blocs à consulter.                   *
+*                incoming = adresse de l'autre bout du lien concerné.         *
+*                                                                             *
+*  Description : Retrouve l'indice d'un lien entrant donné pour un bloc.      *
+*                                                                             *
+*  Retour      : Indice à priori toujours valide.                             *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+{
+    size_t result;                          /* Indice à retourner          */
+
+    for (result = 0; result < cluster->ta_count; result++)
+        if (cluster->top_anchors[result]->other == leaving)
+            break;
+
+    assert(result < cluster->ta_count);
+
+    return result;
 
 }
 
@@ -2256,6 +2454,25 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
     g_graph_cluster_dispatch_x(result);
 
     /**
+     * Une première passe d'organisation horizontale est réalisée.
+     *
+     * A ce point, en proposant des emplacements verticaux en complément,
+     * on est en mesure de déterminer si les liens qui sortent de leur
+     * conteneur vont en croiser d'autres.
+     *
+     * On réorganise ainsi au besoin les différents blocs pour éviter ce cas
+     * de figure. Les blocs sont replacés à une nouvelle position horizontale
+     * au besoin.
+     *
+     * Une illustration concrête de la nécessité de cette opération est la
+     * fonction test_ite_2() de la suite de tests.
+     */
+
+    g_graph_cluster_set_y(result, 0);
+
+    g_graph_cluster_sort_leaving_links(result);
+
+    /**
      * A ce point, tous les blocs sont placés.
      * On est donc en mesure de réorganiser les points d'arrivée
      * des liens afin d'éviter les croisements : un lien qui vient
@@ -2272,21 +2489,6 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
     g_graph_cluster_sort_incoming_links(result);
 
     /**
-     * Comme des profondeurs de rang identiques peuvent renvoyer à des
-     * positions verticales différentes selon les chemins présents,
-     * on lance ici une réorganisation des blocs qui ont une sortie fuyante
-     * de leur ensemble parent en plaçant, même de façon parcellaire, l'ensemble
-     * des blocs.
-     *
-     * Une illustration concrête de cette nécessité est la fonction test_ite_2()
-     * de la suite de tests.
-     */
-
-    g_graph_cluster_set_y(result, 0);
-
-    g_graph_cluster_reorder_exit_blocks(result);
-
-    /**
      * Même s'ils ne sont pas encore entièrement tracés, les liens de boucle
      * voient désormais leurs positions d'arrivée et de départ définies.
      *