Saved extra code block reordering in the graph view.

1 files changed, 246 insertions, 4 deletions

diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 84f3b38..6284029 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -55,16 +55,16 @@ typedef struct _leaving_link_t
     size_t index;                           /* Indice sur ligne de départ  */
 
     bool straight;                          /* Présence d'une ligne droite */
+    bool forced_straight;                   /* Forçage de verticalité      */
     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)
+#define SHOULD_BE_VERTICAL(l) ((l)->straight || (l)->forced_straight || (l)->cluster_exit)
 
 
 /* Crée un point d'attache pour un lien sortant. */
@@ -249,6 +249,9 @@ static void dispatch_x_graph_rank(const graph_rank_t *);
 /* Réorganise au besoin les liens entrants un ensemble de blocs. */
 static void sort_graph_rank_incoming_links(graph_rank_t *);
 
+/* Réordonne les blocs sortant d'un ensemble. */
+static void reorder_graph_rank_exit_blocks(graph_rank_t *);
+
 /* Réordonne les blocs de départ de boucle d'un ensemble. */
 static void reorder_graph_rank_loop_blocks(graph_rank_t *);
 
@@ -373,6 +376,15 @@ static void g_graph_cluster_sort_incoming_links(GGraphCluster *);
 /* Retrouve l'indice d'un lien entrant donné pour un bloc. */
 static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *);
 
+/* Détermine si un cluster possède un lien sortant. */
+static bool g_graph_cluster_has_exit_link(GGraphCluster *, bool *);
+
+/* Compare deux clusters avec lien sortant. */
+static int g_graph_cluster_compare_by_exit(const GGraphCluster **, const GGraphCluster **, const bool *);
+
+/* Réordonne les blocs sortant du cluster au mieux. */
+static void g_graph_cluster_reorder_exit_blocks(GGraphCluster *);
+
 /* Réordonne les blocs de départ de boucle au mieux. */
 static void g_graph_cluster_reorder_loop_blocks(GGraphCluster *);
 
@@ -466,9 +478,9 @@ static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index)
     result->index = index;
 
     result->straight = false;
+    result->forced_straight = false;
     result->straight_level = SIZE_MAX;
     result->cluster_exit = false;
-    result->forced_straight = false;
 
     return result;
 
@@ -1596,7 +1608,81 @@ static void sort_graph_rank_incoming_links(graph_rank_t *grank)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : grank  = ensemble de blocs de même rang à actualiser.        *
+*  Paramètres  : grank = ensemble de blocs de même rang à actualiser.         *
+*                                                                             *
+*  Description : Réordonne les blocs sortant d'un ensemble.                   *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void reorder_graph_rank_exit_blocks(graph_rank_t *grank)
+{
+    GGraphCluster **exit_2_left;            /* Liste avec sortie à gauche  */
+    GGraphCluster **exit_2_right;           /* Liste avec sortie à droite  */
+    GGraphCluster **no_exit;                /* Liste sans sortie           */
+    size_t count_2_left;                    /* Quantité de présents        */
+    size_t count_2_right;                   /* Quantité de présents        */
+    size_t count_no;                        /* Quantité de présents        */
+    size_t i;                               /* Boucle de parcours          */
+    bool l2r;                               /* Détermination de catégorie  */
+
+    if (grank->count > 1)
+    {
+        exit_2_left = malloc(grank->count * sizeof(GGraphCluster *));
+        exit_2_right = malloc(grank->count * sizeof(GGraphCluster *));
+        no_exit = malloc(grank->count * sizeof(GGraphCluster *));
+
+        count_2_left = 0;
+        count_2_right = 0;
+        count_no = 0;
+
+        for (i = 0; i < grank->count; i++)
+        {
+            if (g_graph_cluster_has_exit_link(grank->clusters[i], &l2r))
+            {
+                if (l2r)
+                    exit_2_right[count_2_right++] = grank->clusters[i];
+                else
+                    exit_2_left[count_2_left++] = grank->clusters[i];
+            }
+            else
+                no_exit[count_no++] = grank->clusters[i];
+
+        }
+
+        assert((count_2_left + count_2_right + count_no) == grank->count);
+
+        qsort_r(exit_2_left, count_2_left, sizeof(GGraphCluster *),
+                (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ false });
+
+        qsort_r(exit_2_right, count_2_right, sizeof(GGraphCluster *),
+                (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ true });
+
+        grank->count = 0;
+
+        for (i = 0; i < count_2_left; i++)
+            grank->clusters[grank->count++] = exit_2_left[i];
+
+        for (i = 0; i < count_no; i++)
+            grank->clusters[grank->count++] = no_exit[i];
+
+        for (i = 0; i < count_2_right; i++)
+            grank->clusters[grank->count++] = exit_2_right[i];
+
+    }
+
+    for (i = 0; i < grank->count; i++)
+        g_graph_cluster_reorder_exit_blocks(grank->clusters[i]);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : grank = ensemble de blocs de même rang à actualiser.         *
 *                                                                             *
 *  Description : Réordonne les blocs de départ de boucle d'un ensemble.       *
 *                                                                             *
@@ -2744,6 +2830,147 @@ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, c
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : cluster = graphique de blocs à analyser.                     *
+*                l2r     = indique si le lien trouvé part vers à droite. [OUT]*
+*                                                                             *
+*  Description : Détermine si un cluster possède un lien sortant.             *
+*                                                                             *
+*  Retour      : true si le chef de file à un lien qui sort de l'ensemble.    *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
+{
+    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  */
+
+    result = false;
+
+    for (i = 0; i < cluster->ba_count && !result; i++)
+    {
+        leaving = cluster->bottom_anchors[i];
+
+        if (leaving->cluster_exit)
+        {
+            result = true;
+
+            x1 = compute_leaving_link_position(leaving);
+
+            idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving);
+
+            x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx);
+
+            *l2r = (x1 < x2);
+
+        }
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = premier graphique de blocs à analyser.             *
+*                other   = second graphique de blocs à analyser.              *
+*                l2r     = indique si le lien trouvé part vers à droite.      *
+*                                                                             *
+*  Description : Compare deux clusters avec lien sortant.                     *
+*                                                                             *
+*  Retour      : Bilan de la comparaison.                                     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r)
+{
+    int result;                             /* Bilan à 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;
+
+    for (i = 0; i < (*cluster)->ba_count; i++)
+    {
+        leaving = (*cluster)->bottom_anchors[i];
+
+        if (leaving->cluster_exit)
+        {
+            cluster_y = leaving->other->owner->alloc.y;
+            break;
+        }
+
+    }
+
+    assert(i < (*cluster)->ba_count);
+
+    for (i = 0; i < (*other)->ba_count; i++)
+    {
+        leaving = (*other)->bottom_anchors[i];
+
+        if (leaving->cluster_exit)
+        {
+            other_y = leaving->other->owner->alloc.y;
+            break;
+        }
+
+    }
+
+    assert(i < (*other)->ba_count);
+
+    if (cluster_y < other_y)
+        result = -1;
+
+    else if (cluster_y > other_y)
+        result = 1;
+
+    else
+        result = 0;
+
+    if (*l2r)
+        result *= -1;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : cluster = graphique de blocs à actualiser.                   *
+*                                                                             *
+*  Description : Réordonne les blocs sortant du cluster au mieux.             *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < cluster->ranks_count; i++)
+        reorder_graph_rank_exit_blocks(&cluster->ranks[i]);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : cluster = graphique de blocs à actualiser.                   *
 *                                                                             *
 *  Description : Réordonne les blocs de départ de boucle au mieux.            *
@@ -3910,6 +4137,21 @@ 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.
      *