From 1dae3be2d0860b601d780583365ea7827a6a1be6 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Fri, 1 Mar 2019 11:25:14 +0100
Subject: Handled vertical lines in graph view with more care.

---
 src/gtkext/graph/cluster.c | 321 +++++++++++++++++++++++++++++++++++++++------
 1 file changed, 283 insertions(+), 38 deletions(-)

diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index e0d67eb..7872000 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -26,6 +26,7 @@
 
 #include <assert.h>
 #include <malloc.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -38,6 +39,10 @@
 
 
 
+/* Définition du tracé d'un lien */
+typedef struct _incoming_link_t incoming_link_t;
+
+
 /* ------------------------- LIEN SORTANT D'UN BLOC DE CODE ------------------------- */
 
 
@@ -49,9 +54,19 @@ typedef struct _leaving_link_t
     GdkPoint start[2];                      /* Point de départ d'un lien   */
     size_t index;                           /* Indice sur ligne de départ  */
 
+    bool straight;                          /* Présence d'une ligne droite */
+    size_t straight_level;                  /* Rang atteint en ligne droite*/
+    bool cluster_exit;                      /* Sortie du cluster d'origine */
+    bool forced_straight;                   /* Forçage de verticalité      */
+
+    incoming_link_t *other;                 /* Autre extrémité du lien     */
+
 } leaving_link_t;
 
 
+#define SHOULD_BE_VERTICAL(l) ((l)->straight || (l)->cluster_exit || (l)->forced_straight)
+
+
 /* Crée un point d'attache pour un lien sortant. */
 static leaving_link_t *create_leaving_link(GGraphCluster *, size_t);
 
@@ -67,7 +82,7 @@ static gint compute_leaving_link_position(const leaving_link_t *);
 
 
 /* Définition du tracé d'un lien */
-typedef struct _incoming_link_t
+struct _incoming_link_t
 {
     GGraphCluster *owner;                   /* Propriétaire du lien        */
 
@@ -80,7 +95,7 @@ typedef struct _incoming_link_t
 
     leaving_link_t *other;                  /* Autre extrémité du lien     */
 
-} incoming_link_t;
+};
 
 
 /* Crée un point d'attache pour un lien entrant simple. */
@@ -204,9 +219,6 @@ static void reset_graph_rank_allocation(const graph_rank_t *);
 /* Fournit le rang d'un ensemble de blocs. */
 static size_t get_graph_rank(const graph_rank_t *);
 
-/* Etend un ensemble de blocs de même rang. */
-static void extend_graph_rank(graph_rank_t *, GGraphCluster *);
-
 /* Compare deux rangées de blocs de code. */
 static int cmp_graph_rank(const graph_rank_t *, const graph_rank_t *);
 
@@ -219,6 +231,12 @@ static bool has_graph_rank_cluster(const graph_rank_t *, GGraphCluster *);
 /* Inscrit à l'endroit idéal une réservation d'espace latéral. */
 static bool extend_graph_rank_vspace_manager(graph_rank_t *, leaving_link_t *, incoming_link_t *, GdkPoint *, bool);
 
+/* Met en place les embryons de liens nécessaires. */
+static void define_graph_rank_links(const graph_rank_t *, GHashTable *);
+
+/* Repère les liens marquants à destination d'autres blocs. */
+static void setup_graph_rank_links(const graph_rank_t *);
+
 /* Détermine l'emplacement requis d'un ensemble de blocs. */
 static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *);
 
@@ -259,6 +277,8 @@ struct _GGraphCluster
     GGraphCluster *owner;                   /* Ensemble lié parent         */
     size_t *parent_index;                   /* Indice du lien au départ    */
 
+    GGraphCluster *container;               /* Conteneur de l'ensemble     */
+
     ////////////////////////////////////////
     gint top_margin[2];                     /* Espaces gauches et droites  */
     gint left_margin;                       /* Espaces remontant à gauche  */
@@ -329,6 +349,9 @@ static void g_graph_cluster_extend_vspace_manager(GGraphCluster *, leaving_link_
 /* Met en place les embryons de liens nécessaires. */
 static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
 
+/* Repère les liens marquants à destination d'autres blocs. */
+static void g_graph_cluster_setup_links(GGraphCluster *);
+
 /* Organise la disposition d'un ensemble de blocs basiques. */
 static void g_graph_cluster_dispatch_x(GGraphCluster *);
 
@@ -424,6 +447,11 @@ static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index)
 
     result->index = index;
 
+    result->straight = false;
+    result->straight_level = SIZE_MAX;
+    result->cluster_exit = false;
+    result->forced_straight = false;
+
     return result;
 
 }
@@ -1305,6 +1333,51 @@ static bool extend_graph_rank_vspace_manager(graph_rank_t *grank, leaving_link_t
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : grank = ensemble de descendants d'un même rang.              *
+*                all   = table regroupant tous les groupes créés.             *
+*                                                                             *
+*  Description : Met en place les embryons de liens nécessaires.              *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void define_graph_rank_links(const graph_rank_t *grank, GHashTable *all)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < grank->count; i++)
+        g_graph_cluster_define_links(grank->clusters[i], all);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank = ensemble de descendants d'un même rang.              *
+*                                                                             *
+*  Description : Repère les liens marquants à destination d'autres blocs.     *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void setup_graph_rank_links(const graph_rank_t *grank)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < grank->count; i++)
+        g_graph_cluster_setup_links(grank->clusters[i]);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank = ensemble de descendants d'un même rang.              *
 *                last  = indique s'il s'agit du dernier étage de l'ensemble.  *
 *                alloc = emplacement idéal pour l'affichage. [OUT]            *
 *                                                                             *
@@ -1761,6 +1834,8 @@ static void g_graph_cluster_class_init(GGraphClusterClass *klass)
 
 static void g_graph_cluster_init(GGraphCluster *cluster)
 {
+    cluster->container = cluster;
+
     init_vspace_manager(&cluster->self);
 
 }
@@ -1947,6 +2022,9 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub)
 
     sub->owner = cluster;
 
+    if (sub->ranks_count == 0)
+        sub->container = cluster;
+
 }
 
 
@@ -2035,7 +2113,6 @@ static void g_graph_cluster_extend_vspace_manager(GGraphCluster *target, leaving
 }
 
 
-
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : cluster = graphique de blocs à actualiser.                   *
@@ -2053,13 +2130,12 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 {
     size_t dcount;                          /* Nombre de liens de dest.    */
     block_link_t *links;                    /* Liens associés au bloc      */
-    size_t i;                               /* Boucle de parcours #1       */
+    size_t i;                               /* Boucle de parcours          */
     block_link_t *dest;                     /* Bloc visé par un autre      */
     GGraphCluster *target;                  /* Bloc ciblé par un lien      */
     leaving_link_t *leaving;                /* Point de départ d'un lien   */
     incoming_link_t *incoming;              /* Définitions d'arrivée       */
     GdkPoint *midpts;                       /* Points intermédiaires       */
-    size_t j;                               /* Boucle de parcours #2       */
 
     /* Au niveau du bloc courant */
 
@@ -2100,6 +2176,8 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
                 /* Etablissement d'un embryon de lien */
 
+                leaving->other = incoming;
+
                 g_graph_cluster_setup_link_for_target(cluster, target, leaving);
 
                 break;
@@ -2135,6 +2213,8 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
                 /* Etablissement d'un embryon de lien */
 
+                leaving->other = incoming;
+
                 g_graph_cluster_setup_link_for_target(NULL, target, leaving);
 
                 break;
@@ -2174,7 +2254,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
     /* Déplacement d'un éventuel lien central en position centrale */
 
-    if (cluster->has_straight)
+    if (0 && cluster->has_straight)
     {
         size_t center;
         leaving_link_t *tmp;
@@ -2223,8 +2303,102 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
     /* Propagation de la mise en place */
 
     for (i = 0; i < cluster->ranks_count; i++)
-        for (j = 0; j < cluster->ranks[i].count; j++)
-            g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all);
+        define_graph_rank_links(&cluster->ranks[i], all);
+
+}
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*                                                                             *
+*  Description : Repère les liens marquants à destination d'autres blocs.     *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_graph_cluster_setup_links(GGraphCluster *cluster)
+{
+    size_t i;                               /* Boucle de parcours #1       */
+    leaving_link_t *leaving;                /* Départ de lien              */
+    incoming_link_t *incoming;              /* Arrivée de lien             */
+    size_t level;                           /* Niveau du bloc courant      */
+    size_t target_level;                    /* Rang du bloc ciblé          */
+    GGraphCluster *container;               /* Conteneur parent à parcourir*/
+    size_t k;                               /* Boucle de parcours #2       */
+
+    for (i = 0; i < cluster->ba_count; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
+        incoming = leaving->other;
+
+        if (incoming->type == ILT_LOOP)
+            continue;
+
+        /* Est-ce un lien qui doit être vertical ? */
+
+        level = g_code_block_get_rank(leaving->owner->block);
+        target_level = g_code_block_get_rank(incoming->owner->block);
+
+        if (target_level > (level + 1))
+        {
+            leaving->straight = true;
+            leaving->straight_level = target_level;
+            continue;
+        }
+
+        /* Est-ce une sortie de cluster ? */
+
+        if (leaving->owner->container != incoming->owner->container)
+        {
+            container = leaving->owner->container;
+
+            for (k = 0; k < container->ranks_count; k++)
+                if (has_graph_rank_cluster(&container->ranks[k], incoming->owner))
+                    break;
+
+            if (k == container->ranks_count)
+            {
+                leaving->cluster_exit = true;
+                continue;
+            }
+
+        }
+
+        /* Doit-on forcer un lien strictement vertical ? */
+
+        if (cluster->ba_count == 1)
+        {
+            /**
+             * Attention : les boucles aussi ont un seul lien sortant !
+             * Le filtrage est cependant réalisé au début de l'itération.
+             */
+
+            container = leaving->owner->container;
+
+            for (k = 0; k < container->ranks_count; k++)
+                if (has_graph_rank_cluster(&container->ranks[k], incoming->owner))
+                    break;
+
+            if (k < container->ranks_count)
+            {
+                leaving->forced_straight = true;
+                leaving->straight_level = target_level;
+                continue;
+            }
+
+        }
+
+    }
+
+    /* Propagation de la mise en place */
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        setup_graph_rank_links(&cluster->ranks[i]);
 
 }
 
@@ -2243,33 +2417,55 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
 
 static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
 {
-    size_t k;                               /* Boucle de parcours #1       */
+    size_t i;                               /* Boucle de parcours #1       */
+    leaving_link_t *straight_leaving;       /* Lien à présenter vertical   */
+    size_t straight_index;                  /* Indice du lien vertical     */
+    gint straight_start;                    /* Position initiale de départ */
+    size_t straight_level;                  /* Rang atteint en ligne droite*/
     const graph_rank_t *rank;               /* Accès confortable au rang   */
+    gint start;                             /* Position initiale modifiable*/
     size_t j;                               /* Boucle de parcours #2       */
-    gint start;                             /* Position initiale de départ */
     GGraphCluster *target;                  /* Unique sous-bloc visé       */
     size_t idx;                             /* Indice du lien entrant      */
     gint end;                               /* Position initiale d'arrivée */
+    leaving_link_t *leaving;                /* Départ de lien              */
+
+    /* Recherche d'une limite verticale */
+
+    straight_leaving = NULL;
+
+    for (i = 0; i < cluster->ba_count; i++)
+        if (SHOULD_BE_VERTICAL(cluster->bottom_anchors[i]))
+        {
+            straight_leaving = cluster->bottom_anchors[i];
+            straight_index = i;
+
+            straight_start = g_graph_cluster_compute_leaving_link_position(cluster, i);
+            straight_level = straight_leaving->straight_level;
+
+            break;
+
+        }
 
     /**
      * Il est désormais temps de placer tous les blocs de code inférieurs.
      */
 
-    for (k = 0; k < cluster->ranks_count; k++)
+    for (i = 0; i < cluster->ranks_count; i++)
     {
-        rank = &cluster->ranks[k];
+        rank = &cluster->ranks[i];
 
         /* Répartition autour d'une ligne verticale */
-        if (cluster->has_straight)
+        if (straight_leaving != NULL)
         {
-            start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index);
-
-            if (get_graph_rank(rank) < cluster->straight_level)
+            if (get_graph_rank(rank) < straight_level)
             {
+                start = straight_start;
+
                 /* Répartition à gauche du lien */
 
                 for (j = rank->count; j > 0; j--)
-                    if (*rank->clusters[j - 1]->parent_index < cluster->straight_index)
+                    if (*rank->clusters[j - 1]->parent_index < straight_index)
                         break;
 
                 start -= HORIZONTAL_MARGIN / 2;
@@ -2279,7 +2475,7 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
                 /* Répartition à droite du lien */
 
                 for (j = 0; j < rank->count; j++)
-                    if (*rank->clusters[j]->parent_index > cluster->straight_index)
+                    if (*rank->clusters[j]->parent_index > straight_index)
                         break;
 
                 start += HORIZONTAL_MARGIN;
@@ -2288,38 +2484,73 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
 
             }
 
-            else if (get_graph_rank(rank) == cluster->straight_level)
+            else if (get_graph_rank(rank) == straight_level)
             {
-                /**
-                 * Si le bloc pointé en direct a plus d'un lien en entrée (comme
-                 * dans le cas d'un bloc qui assure un début de boucle par exemple),
-                 * le lien direct n'est pas centré sur le milieu de ce bloc pointé.
-                 *
-                 * On corrige ici le léger décalage.
-                 */
-                assert(rank->count == 1);
+                dispatch_x_graph_rank(rank);
 
-                target = rank->clusters[0];
+                if (straight_leaving->straight || straight_leaving->forced_straight)
+                {
+                    /**
+                     * Si le bloc pointé en direct a plus d'un lien en entrée (comme
+                     * dans le cas d'un bloc qui assure un début de boucle par exemple),
+                     * le lien direct n'est pas centré sur le milieu de ce bloc pointé.
+                     *
+                     * On corrige ici le léger décalage.
+                     */
+                    assert(rank->count == 1);
 
-                idx = g_graph_cluster_find_incoming_link(target, cluster->bottom_anchors[cluster->straight_index]);
+                    target = rank->clusters[0];
 
-                end = g_graph_cluster_compute_incoming_link_position(target, idx);
+                    idx = g_graph_cluster_find_incoming_link(target, straight_leaving);
 
-                g_graph_cluster_offset_x(target, start - end);
+                    end = g_graph_cluster_compute_incoming_link_position(target, idx);
 
-                dispatch_x_graph_rank(rank);
+                    g_graph_cluster_offset_x(target, straight_start - end);
+
+                }
+
+                straight_leaving = NULL;
+
+                goto look_for_forced;
 
             }
 
             else
-                dispatch_x_graph_rank(rank);
+                assert(false);
 
         }
 
         /* Répartition homogène */
         else
+        {
             dispatch_x_graph_rank(rank);
 
+ look_for_forced:
+
+            /* Lien vertical interne ? */
+
+            if (rank->count != 1)
+                continue;
+
+            target = rank->clusters[0];
+
+            if (target->ba_count != 1)
+                continue;
+
+            leaving = target->bottom_anchors[0];
+
+            if (leaving->forced_straight)
+            {
+                straight_leaving = leaving;
+                straight_index = 0;
+
+                straight_start = g_graph_cluster_compute_leaving_link_position(target, 0);
+                straight_level = leaving->straight_level;
+
+            }
+
+        }
+
     }
 
 }
@@ -2745,6 +2976,8 @@ static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *
 static void g_graph_cluster_insert_left_margin(GGraphCluster *cluster, gint margin)
 {
     GGraphCluster *container;               /* Parent direct à décaler     */
+    size_t i;                               /* Boucle de parcours          */
+    size_t straight_index;                  /* Indice du lien vertical     */
 
     if (margin > 0)
     {
@@ -2763,10 +2996,20 @@ static void g_graph_cluster_insert_left_margin(GGraphCluster *cluster, gint marg
              */
             while (container->owner != NULL)
             {
-                if (!container->owner->has_straight)
+                if (container->owner->ba_count == 0)
                     break;
 
-                if (container->owner->straight_index != *container->parent_index)
+                for (i = 0; i < container->owner->ba_count; i++)
+                    if (SHOULD_BE_VERTICAL(container->owner->bottom_anchors[i]))
+                    {
+                        straight_index = i;
+                        break;
+                    }
+
+                if (i == container->owner->ba_count)
+                    break;
+
+                if (straight_index != *container->parent_index)
                     break;
 
                 container = container->owner;
@@ -3322,6 +3565,8 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
 
     g_graph_cluster_define_links(result, all);
 
+    g_graph_cluster_setup_links(result);
+
     /* Positionnements dans l'espace */
 
     g_graph_cluster_dispatch_x(result);
-- 
cgit v0.11.2-87-g4458