Saved a first round to book extra space for straight edges if needed.

2 files changed, 180 insertions, 2 deletions

diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h
index 3121d64..9da1af2 100644
--- a/src/gtkext/graph/cluster-int.h
+++ b/src/gtkext/graph/cluster-int.h
@@ -64,6 +64,12 @@ const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GG
 /* Compare deux clusters selon un de leurs liens d'origine. */
 int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *);
 
+/* Calcule les abscisses extrèmes atteintes horizontalement. */
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *, const GGraphCluster *, gint [2]);
+
+/* S'assure que les liens verticaux ne traversent pas de bloc. */
+void g_graph_cluster_ensure_space_for_straight(GGraphCluster *);
+
 /* Réorganise au besoin les liens entrants d'un bloc. */
 void g_graph_cluster_sort_incoming_links(GGraphCluster *);
 
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 801929e..48ad9ca 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -65,6 +65,9 @@ struct _GGraphCluster
     GtkWidget *display;                     /* Vue graphique associée      */
     GtkAllocation alloc;                    /* Emplacement final du bloc   */
 
+    gint left_offset;                       /* Besoin d'espace à gauche    */
+    gint right_offset;                      /* Besoin d'espace à droite    */
+
     leaving_link_t **bottom_anchors;        /* Accroches inférieures       */
     size_t ba_count;                        /* Quantité de ces accroches   */
 
@@ -189,6 +192,9 @@ static void g_graph_cluster_init(GGraphCluster *cluster)
 {
     cluster->container = cluster;
 
+    cluster->left_offset = 0;
+    cluster->right_offset = 0;
+
     init_vspace_manager(&cluster->self);
 
 }
@@ -816,7 +822,7 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
                     if (*rank->clusters[j - 1]->parent_index < straight_index)
                         break;
 
-                start -= HORIZONTAL_MARGIN / 2;
+                start -= LINK_MARGIN;
 
                 _place_graph_rank_clusters(rank->clusters, j, start, -1);
 
@@ -826,7 +832,7 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
                     if (*rank->clusters[j]->parent_index > straight_index)
                         break;
 
-                start += HORIZONTAL_MARGIN;
+                start += 2 * LINK_MARGIN;
 
                 _place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1);
 
@@ -1250,6 +1256,148 @@ int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGrap
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : cluster = graphique de blocs à consulter.                    *
+*                stop    = chef de file marquant l'arrêt des consultations.   *
+*                pos     = ordonnées minimale et maximale en bout. [OUT]      *
+*                                                                             *
+*  Description : Calcule les abscisses extrèmes atteintes horizontalement.    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *cluster, const GGraphCluster *stop, gint pos[2])
+{
+    size_t i;                               /* Boucle de parcours          */
+    const leaving_link_t *leaving;          /* Lien sortant du bloc        */
+
+    if (cluster->alloc.y < stop->alloc.y)
+    {
+        if (cluster->alloc.x < pos[0])
+            pos[0] = cluster->alloc.x;
+
+        if ((cluster->alloc.x + cluster->alloc.width) > pos[1])
+            pos[1] = cluster->alloc.x + cluster->alloc.width;
+
+        for (i = 0; i < cluster->ba_count; i++)
+        {
+            leaving = cluster->bottom_anchors[i];
+
+            if (leaving->other->type == ILT_LOOP)
+                continue;
+
+            g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+
+        }
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à manipuler.                    *
+*                                                                             *
+*  Description : S'assure que les liens verticaux ne traversent pas de bloc.  *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void g_graph_cluster_ensure_space_for_straight(GGraphCluster *cluster)
+{
+    size_t i;                               /* Boucle de parcours          */
+    size_t first;                           /* Premier lien vertical       */
+    size_t last;                            /* Dernier lien vertical       */
+    size_t straight_level;                  /* Rang atteint en ligne droite*/
+    GGraphCluster *stop;                    /* Borne d'arrêt correspondante*/
+    const leaving_link_t *leaving;          /* Lien sortant du bloc        */
+    gint pos[2];                            /* Bornes horizontales         */
+    gint max;                               /* Borne horizontale           */
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        visit_graph_rank(&cluster->ranks[i], g_graph_cluster_ensure_space_for_straight);
+
+    first = cluster->ba_count;
+    last = 0;
+
+    straight_level = 0;
+    stop = NULL;
+
+    for (i = 0; i < cluster->ba_count; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
+
+        if (leaving->straight)
+        {
+            if (first == cluster->ba_count)
+                first = i;
+
+            last = i;
+
+            if (straight_level < leaving->straight_level)
+            {
+                straight_level = leaving->straight_level;
+                stop = leaving->other->owner;
+            }
+
+        }
+
+    }
+
+    if (stop != NULL)
+    {
+        if (first > 0)
+        {
+            pos[0] = G_MAXINT;
+            pos[1] = 0;
+
+            for (i = 0; i < first; i++)
+            {
+                leaving = cluster->bottom_anchors[i];
+                g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+            }
+
+            max = compute_leaving_link_position(cluster->bottom_anchors[first]);
+
+            if ((pos[1] + LINK_MARGIN) > max)
+            {
+                cluster->right_offset = (pos[0] + LINK_MARGIN) - max;
+                assert(false);
+            }
+
+        }
+
+        if ((last + 1) < cluster->ba_count)
+        {
+            pos[0] = G_MAXINT;
+            pos[1] = 0;
+
+            for (i = last + 1; i < cluster->ba_count; i++)
+            {
+                leaving = cluster->bottom_anchors[i];
+                g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+            }
+
+            max = compute_leaving_link_position(cluster->bottom_anchors[last]);
+
+            if ((max + LINK_MARGIN) > pos[0])
+                cluster->right_offset = (max + LINK_MARGIN) - pos[0];
+
+        }
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : cluster = graphique de blocs à manipuler.                    *
 *                                                                             *
 *  Description : Réorganise au besoin les liens entrants d'un bloc.           *
@@ -1546,6 +1694,8 @@ void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAlloc
 
         }
 
+    alloc->width += cluster->right_offset;
+
 }
 
 
@@ -2473,6 +2623,28 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
     g_graph_cluster_sort_leaving_links(result);
 
     /**
+     * On vérifie maintenant que les liens bien verticaux ne rencontrent pas
+     * de bloc de code.
+     *
+     * Pour celà, il faut disposer d'une cartographie complète :
+     *
+     *  - sur l'axe des abscisses pour les positions à compenser.
+     *  - sur l'axe des ordonnées pour borner les suivis de liens en profondeur.
+     */
+
+    g_graph_cluster_reset_allocation(result);
+
+    g_graph_cluster_dispatch_x(result);
+
+    g_graph_cluster_compute_needed_alloc(result, &needed);
+
+    g_graph_cluster_offset_x(result, -needed.x);
+
+    g_graph_cluster_set_y(result, 0);
+
+    g_graph_cluster_ensure_space_for_straight(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