/* Chrysalide - Outil d'analyse de fichiers binaires
* cluster.c - mise en place de graphiques
*
* Copyright (C) 2016-2017 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Chrysalide is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Chrysalide. If not, see .
*/
#include "cluster.h"
#include
#include
#include
#include
#include "../gtkblockdisplay.h"
#include "../gtkbufferdisplay.h"
#include "../gtkdisplaypanel.h"
#include "../../common/sort.h"
#include "../../glibext/gloadedpanel.h"
/* ------------------------- LIEN SORTANT D'UN BLOC DE CODE ------------------------- */
/* Détails sur le départ d'un lien */
typedef struct _leaving_link_t
{
GGraphCluster *owner; /* Propriétés du lien */
GdkPoint start[2]; /* Point de départ d'un lien */
size_t index; /* Indice sur ligne de départ */
} leaving_link_t;
/* Crée un point d'attache pour un lien sortant. */
static leaving_link_t *create_leaving_link(GGraphCluster *, size_t);
/* Détruit un point d'attache pour un lien sortant. */
static void delete_leaving_link(leaving_link_t *);
/* Calcule l'abscisse d'un lien à son départ d'un bloc. */
static gint compute_leaving_link_position(const leaving_link_t *);
/* ------------------------- LIEN ENTRANT D'UN BLOC DE CODE ------------------------- */
/* Définition du tracé d'un lien */
typedef struct _incoming_link_t
{
GGraphCluster *owner; /* Propriétés du lien */
InstructionLinkType type; /* Complexité du tracé */
const size_t *hslot; /* Couche horizontale réservée */
GdkPoint end[2]; /* Point d'arrivée final */
GGraphEdge *edge; /* Lien complet en préparation */
leaving_link_t *other; /* Autre extrémité du lien */
} incoming_link_t;
/* Crée un point d'attache pour un lien entrant simple. */
static incoming_link_t *create_incoming_link(GGraphCluster *, InstructionLinkType, leaving_link_t *);
/* Crée un point d'attache pour un lien entrant de boucle. */
static incoming_link_t *create_incoming_loop_link(GGraphCluster *, const GdkPoint *, leaving_link_t *);
/* Détruit un point d'attache pour un lien entrant. */
static void delete_incoming_link(incoming_link_t *);
/* Compare deux liens entrants. */
static int cmp_incoming_links(const incoming_link_t **, const incoming_link_t **);
/* ---------------------- DESCENDANTS DIRECTS CLASSES PAR RANG ---------------------- */
/* Réservation pour les lignes horizontales */
typedef struct _hspace_booking
{
gint start; /* Abscisse de départ de ligne */
size_t index; /* Indice de rangée verticale */
} hspace_booking;
/* Prépare une réservation d'espace pour ligne horizontale. */
static hspace_booking *create_hspace_booking(gint);
/* Compare deux réservations d'espace. */
static int cmp_hspace_booking_r2l(const hspace_booking **, const hspace_booking **);
/* Compare deux réservations d'espace. */
static int cmp_hspace_booking_l2r(const hspace_booking **, const hspace_booking **);
/* Découpage vertical */
typedef struct _graph_rank_t
{
hspace_booking **right2left; /* Réservations de D -> G */
size_t r2l_count; /* Quantité de ces réservations*/
hspace_booking **left2right; /* Réservations de G -> D */
size_t l2r_count; /* Quantité de ces réservations*/
GGraphCluster **clusters; /* Ensembles de blocs */
size_t count; /* Nombre de ces ensembles */
} graph_rank_t;
/* Initialise la gestion d'un ensemble de blocs de même rang. */
static void init_graph_rank(graph_rank_t *, GGraphCluster *);
/* Termine la gestion d'un ensemble de blocs de même rang. */
static void exit_graph_rank(graph_rank_t *);
/* Assigne à un ensemble de blocs un emplacement initial. */
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 *);
/* Etend un ensemble de blocs de même rang. */
static void extend_graph_rank(graph_rank_t *, GGraphCluster *);
/* Etablit les connexions entre blocs selon les rangs. */
static bool setup_graph_rank_link_for_target(const graph_rank_t *, GGraphCluster *, GGraphCluster *, leaving_link_t *);
/* Détermine l'emplacement requis d'un ensemble de blocs. */
static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *);
/* Affine l'abscisse d'un ensemble de blocs de même rang. */
static void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int);
/* Organise la disposition d'un ensemble de blocs basiques. */
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(const graph_rank_t *);
/* Décale vers la droite un ensemble de blocs basiques. */
static void offset_x_graph_rank(const graph_rank_t *, gint);
/* Décale vers le bas un ensemble de blocs basiques. */
static void set_y_for_graph_rank(const graph_rank_t *, gint *);
/* ------------------------ ENCADREMENTS D'ESPACES VERTICAUX ------------------------ */
/* Réservations d'espaces latéraux */
typedef struct _vspace_booking_t
{
leaving_link_t *from; /* Bloc de départ du lien */
incoming_link_t *to; /* Bloc d'arrivée du lien */
GdkPoint *pts; /* Coordonnées des points */
} vspace_booking_t;
/* Réservations d'espaces latéraux */
typedef struct _vspace_manager_t
{
vspace_booking_t *pending; /* Besoins exprimés */
size_t pending_count; /* Nombre de ces besoins */
vspace_booking_t **left; /* Lignes disposées à gauche */
size_t left_count; /* Quantité de ces lignes */
vspace_booking_t **right; /* Lignes disposées à droite */
size_t right_count; /* Quantité de ces lignes */
} vspace_manager_t;
/* Initialise les réservations liens verticaux. */
static void init_vspace_manager(vspace_manager_t *);
/* Termine les réservations liens verticaux. */
static void exit_vspace_manager(vspace_manager_t *);
/* Inscrit une nouvelle réservation d'espace latéral. */
static void extend_vspace_manager(vspace_manager_t *, leaving_link_t *, incoming_link_t *, GdkPoint *);
/* Détermine l'emplacement requis pour les espaces latéraux. */
static void compute_vspace_manager_needed_alloc(const vspace_manager_t *, bool, bool, GtkAllocation *);
/* Réorganise au besoin les liens de boucle entre blocs. */
static void sort_incoming_links_for_vspace_manager(vspace_manager_t *);
/* Détermine les abscisses de tous les liens en place. */
static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *, bool, GGraphCluster *);
/* Détermine les ordonnées de tous les liens en place. */
static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *, GGraphCluster *);
/* -------------------------- DEFINITION D'UN CHEF DE FILE -------------------------- */
/* Mise en disposition de blocs en graphique (instance) */
struct _GGraphCluster
{
GObject parent; /* A laisser en premier */
GGraphCluster *owner; /* Ensemble lié parent */
size_t *parent_index; /* Indice du lien au départ */
////////////////////////////////////////
gint top_margin[2]; /* Espaces gauches et droites */
gint left_margin; /* Espaces remontant à gauche */
gint right_margin; /* Espaces remontant à droite */
////////////////////////////////////////
incoming_link_t **top_anchors; /* Accroches supérieures */
size_t ta_count; /* Quantité de ces accroches */
GCodeBlock *block; /* Bloc d'origine représenté */
GtkWidget *display; /* Vue graphique associée */
GtkAllocation alloc; /* Emplacement final du bloc */
leaving_link_t **bottom_anchors; /* Accroches inférieures */
size_t ba_count; /* Quantité de ces accroches */
bool has_straight; /* Présence d'une ligne droite */
size_t straight_level; /* Rang atteint en ligne droite*/
size_t straight_index; /* Indice du lien vertical */
graph_rank_t *ranks; /* Répartition verticale */
size_t ranks_count; /* Nombre de divisions */
vspace_manager_t vspaces; /* Gestion des liens latéraux */
};
/* Mise en disposition de blocs en graphique (classe) */
struct _GGraphClusterClass
{
GObjectClass parent; /* A laisser en premier */
};
/* Espace minimal horizontal entre les blocs */
#define HORIZONTAL_MARGIN 20
/* Espace minimal vertical entre les blocs */
#define VERTICAL_MARGIN 15
/* Espace minimal entre les liens */
#define LINK_MARGIN 10
/* Initialise la classe des mises en disposition graphique. */
static void g_graph_cluster_class_init(GGraphClusterClass *);
/* Initialise une mise en disposition de blocs en graphique. */
static void g_graph_cluster_init(GGraphCluster *);
/* Supprime toutes les références externes. */
static void g_graph_cluster_dispose(GGraphCluster *);
/* Procède à la libération totale de la mémoire. */
static void g_graph_cluster_finalize(GGraphCluster *);
/* Assigne à un bloc et son ensemble un emplacement initial. */
static void g_graph_cluster_reset_allocation(GGraphCluster *);
/* Complète un graphique avec un sous-ensemble de blocs. */
static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *);
/* Met en place les embryons de liens nécessaires. */
static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
/* Organise la disposition d'un ensemble de blocs basiques. */
static void g_graph_cluster_dispatch_x(GGraphCluster *);
/* Réorganise au besoin les liens entrants d'un bloc. */
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écale vers la droite un ensemble de blocs basiques. */
static void g_graph_cluster_offset_x(GGraphCluster *, gint);
/* Décale vers le bas un ensemble de blocs basiques. */
static void g_graph_cluster_set_y(GGraphCluster *, gint);
/* Calcule l'abscisse d'un lien pour un bloc. */
static gint _g_graph_cluster_compute_link_position(const GGraphCluster *, size_t, size_t, bool);
/* Calcule l'abscisse d'un lien à son départ d'un bloc. */
static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *, size_t);
/* Calcule l'abscisse d'un lien à son arrivée à un bloc. */
static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *, size_t);
/* Détermine les abscisses des liens de boucle en place. */
static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *);
/* Détermine les abscisses de tous les liens en place. */
static void g_graph_cluster_compute_link_x_positions(GGraphCluster *);
/* Réserve de l'espace vertical pour les lignes horizontales. */
static void g_graph_cluster_book_hspace_for_links(GGraphCluster *);
/* Détermine les ordonnées de tous les liens en place. */
static void g_graph_cluster_compute_link_y_positions(GGraphCluster *);
/* Applique les positions calculées pour chaque lien graphique. */
static void g_graph_cluster_resolve_links(const GGraphCluster *);
/* ------------------------- CALCUL DE REPARTITION DE BLOCS ------------------------- */
/* Liste de blocs restants à traiter */
typedef struct _pending_blocks
{
size_t count; /* Taille de la liste */
GCodeBlock *list[0]; /* Liste de blocs à traiter */
} pending_blocks;
/* Met en place un ensemble de blocs sous forme graphique. */
static GGraphCluster *setup_graph_clusters(GLoadedBinary *, const GBlockList *, size_t , segcnt_list *, pending_blocks *, GHashTable *);
/* ---------------------------------------------------------------------------------- */
/* LIEN SORTANT D'UN BLOC DE CODE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : owner = propriétaire du bloc de rattachement. *
* index = indice dans les liens de sortie. *
* *
* Description : Crée un point d'attache pour un lien sortant. *
* *
* Retour : Structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index)
{
leaving_link_t *result; /* Structure à retourner */
result = malloc(sizeof(leaving_link_t));
result->owner = owner;
result->index = index;
return result;
}
/******************************************************************************
* *
* Paramètres : link = structure à libérer de la mémoire. *
* *
* Description : Détruit un point d'attache pour un lien sortant. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void delete_leaving_link(leaving_link_t *link)
{
free(link);
}
/******************************************************************************
* *
* Paramètres : link = information sur un lien à consulter. *
* *
* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. *
* *
* Retour : Abscisse à attribuer à un départ de lien. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint compute_leaving_link_position(const leaving_link_t *link)
{
gint result; /* Position à retourner */
result = g_graph_cluster_compute_leaving_link_position(link->owner, link->index);
return result;
}
/* ---------------------------------------------------------------------------------- */
/* LIEN ENTRANT D'UN BLOC DE CODE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : owner = propriétaire du bloc de rattachement. *
* type = type de lien simple attendu. *
* other = point de départ du lien formé. *
* *
* Description : Crée un point d'attache pour un lien entrant simple. *
* *
* Retour : Structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLinkType type, leaving_link_t *other)
{
incoming_link_t *result; /* Structure à retourner */
result = malloc(sizeof(incoming_link_t));
result->owner = owner;
result->type = type;
if (type == ILT_JUMP_IF_TRUE)
result->edge = g_graph_edge_new_true(&other->start[0], &other->start[1], &result->end[0], &result->end[1]);
else if (type == ILT_JUMP_IF_FALSE)
result->edge = g_graph_edge_new_false(&other->start[0], &other->start[1], &result->end[0], &result->end[1]);
else
result->edge = g_graph_edge_new(&other->start[0], &other->start[1], &result->end[0], &result->end[1]);
result->other = other;
return result;
}
/******************************************************************************
* *
* Paramètres : owner = propriétaire du bloc de rattachement. *
* other = point de départ du lien formé. *
* *
* Description : Crée un point d'attache pour un lien entrant de boucle. *
* *
* Retour : Structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const GdkPoint *midpts, leaving_link_t *other)
{
incoming_link_t *result; /* Structure à retourner */
result = malloc(sizeof(incoming_link_t));
result->owner = owner;
result->type = ILT_LOOP;
result->edge = g_graph_edge_new_loop(&other->start[0], &other->start[1],
&midpts[0], &midpts[1],
&result->end[0], &result->end[1]);
result->other = other;
return result;
}
/******************************************************************************
* *
* Paramètres : link = structure à libérer de la mémoire. *
* *
* Description : Détruit un point d'attache pour un lien entrant. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void delete_incoming_link(incoming_link_t *link)
{
free(link);
}
/******************************************************************************
* *
* Paramètres : a = premier lien entrant à comparer. *
* b = second lien entrant à comparer. *
* *
* Description : Compare deux liens entrants. *
* *
* Retour : Bilan de comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
static int cmp_incoming_links(const incoming_link_t **a, const incoming_link_t **b)
{
int result; /* Bilan à retourner */
gint pos_a; /* Point de départ pour A */
gint pos_b; /* Point de départ pour B */
pos_a = compute_leaving_link_position((*a)->other);
pos_b = compute_leaving_link_position((*b)->other);
if (pos_a < pos_b)
result = -1;
else if (pos_a > pos_b)
result = 1;
else
result = 0;
return result;
}
/* ---------------------------------------------------------------------------------- */
/* DESCENDANTS DIRECTS CLASSES PAR RANG */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : start = abscisse de départ de ligne. *
* *
* Description : Prépare une réservation d'espace pour ligne horizontale. *
* *
* Retour : Structure mise en place pour la conservation d'informations. *
* *
* Remarques : - *
* *
******************************************************************************/
static hspace_booking *create_hspace_booking(gint start)
{
hspace_booking *result; /* Structure à retourner */
result = malloc(sizeof(hspace_booking));
result->start = start;
return result;
}
/******************************************************************************
* *
* Paramètres : a = première réservation d'espace à comparer. *
* b = seconde réservation d'espace à comparer. *
* *
* Description : Compare deux réservations d'espace. *
* *
* Retour : Bilan de comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
static int cmp_hspace_booking_r2l(const hspace_booking **a, const hspace_booking **b)
{
int result; /* Bilan à retourner */
if ((*a)->start > (*b)->start)
result = -1;
else if ((*a)->start < (*b)->start)
result = 1;
else
{
assert(false);
result = 0;
}
return result;
}
/******************************************************************************
* *
* Paramètres : a = première réservation d'espace à comparer. *
* b = seconde réservation d'espace à comparer. *
* *
* Description : Compare deux réservations d'espace. *
* *
* Retour : Bilan de comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
static int cmp_hspace_booking_l2r(const hspace_booking **a, const hspace_booking **b)
{
int result; /* Bilan à retourner */
if ((*a)->start < (*b)->start)
result = -1;
else if ((*a)->start > (*b)->start)
result = 1;
else
{
assert(false);
result = 0;
}
return result;
}
/******************************************************************************
* *
* Paramètres : grank = structure à initialiser. [OUT] *
* cluster = chef de file d'un ensemble de blocs. *
* *
* Description : Initialise la gestion d'un ensemble de blocs de même rang. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_graph_rank(graph_rank_t *grank, GGraphCluster *cluster)
{
grank->right2left = NULL;
grank->r2l_count = 0;
grank->left2right = NULL;
grank->l2r_count = 0;
grank->clusters = malloc(sizeof(GGraphCluster *));
grank->count = 1;
grank->clusters[0] = cluster;
}
/******************************************************************************
* *
* Paramètres : grank = structure à vider. *
* *
* Description : Termine la gestion d'un ensemble de blocs de même rang. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void exit_graph_rank(graph_rank_t *grank)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < grank->r2l_count; i++)
free(grank->right2left[i]);
if (grank->right2left != NULL)
free(grank->right2left);
for (i = 0; i < grank->l2r_count; i++)
free(grank->left2right[i]);
if (grank->left2right != NULL)
free(grank->left2right);
assert(grank->clusters != NULL);
free(grank->clusters);
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de même rang à consulter. *
* *
* Description : Assigne à un ensemble de blocs un emplacement initial. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void reset_graph_rank_allocation(const graph_rank_t *grank)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < grank->count; i++)
g_graph_cluster_reset_allocation(grank->clusters[i]);
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de même rang à consulter. *
* *
* Description : Fournit le rang d'un ensemble de blocs. *
* *
* Retour : Rang d'un ensemble de blocs de même rang. *
* *
* Remarques : - *
* *
******************************************************************************/
static size_t get_graph_rank(const graph_rank_t *grank)
{
size_t result; /* Rang à retourner */
result = g_code_block_get_rank(grank->clusters[0]->block);
return result;
}
/******************************************************************************
* *
* Paramètres : a = premier ensemble de même rang à comparer. *
* b = second ensemble de même rang à comparer. *
* *
* Description : Compare deux rangées de blocs de code. *
* *
* Retour : Bilan de comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
static int cmp_graph_rank(const graph_rank_t *a, const graph_rank_t *b)
{
int result; /* Bilan à retourner */
size_t level_a; /* Niveau de l'ensemble A */
size_t level_b; /* Niveau de l'ensemble B */
level_a = get_graph_rank(a);
level_b = get_graph_rank(b);
if (level_a < level_b)
result = -1;
else if (level_a > level_b)
result = 1;
else
result = 0;
return result;
}
/******************************************************************************
* *
* Paramètres : grank = structure à compléter. *
* cluster = chef de file d'un ensemble de blocs. *
* *
* Description : Etend un ensemble de blocs de même rang. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void extend_graph_rank(graph_rank_t *grank, GGraphCluster *cluster)
{
grank->count++;
grank->clusters = realloc(grank->clusters, sizeof(GGraphCluster *) * grank->count);
grank->clusters[grank->count - 1] = cluster;
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de descendants d'un même rang. *
* source = bloc courant ou NULL pour limiter les calculs. *
* target = bloc ciblé pour l'arrivée d'un lien. *
* leaving = représentation d'un lien sortant. *
* *
* Description : Etablit les connexions entre blocs selon les rangs. *
* *
* Retour : true si la cible a été rencontrée. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool setup_graph_rank_link_for_target(const graph_rank_t *grank, GGraphCluster *source, GGraphCluster *target, leaving_link_t *leaving)
{
bool result; /* Bilan à retourner */
size_t level; /* Niveau du nouvel ensemble */
size_t i; /* Boucle de parcours */
size_t target_level; /* Rang du bloc ciblé */
result = false;
if (source != NULL)
level = g_code_block_get_rank(source->block);
for (i = 0; i < grank->count && !result; i++)
if (grank->clusters[i] == target)
{
result = true;
target->parent_index = &leaving->index;
if (source != NULL)
{
target_level = get_graph_rank(grank);
/* Est-ce un lien qui doit être vertical ? */
if (target_level > (level + 1) && target_level > source->straight_level)
{
source->has_straight = true;
source->straight_level = target_level;
source->straight_index = source->ba_count - 1;
}
}
}
return result;
}
/******************************************************************************
* *
* 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] *
* *
* Description : Détermine l'emplacement requis d'un ensemble de blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void compute_graph_rank_needed_alloc(const graph_rank_t *grank, bool last, GtkAllocation *alloc)
{
GtkAllocation needed; /* Taille requise */
switch (grank->count)
{
case 1:
g_graph_cluster_compute_needed_alloc(grank->clusters[0], &needed);
if (needed.x < alloc->x)
{
alloc->width += (alloc->x - needed.x);
alloc->x = needed.x;
}
if ((needed.x + needed.width) > (alloc->x + alloc->width))
alloc->width += needed.x + needed.width - alloc->x - alloc->width;
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if (last)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
break;
default:
assert(grank->count >= 2);
g_graph_cluster_compute_needed_alloc(grank->clusters[0], &needed);
if (needed.x < alloc->x)
{
alloc->width += (alloc->x - needed.x);
alloc->x = needed.x;
}
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if (last)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
g_graph_cluster_compute_needed_alloc(grank->clusters[grank->count - 1], &needed);
if ((needed.x + needed.width) > (alloc->x + alloc->width))
alloc->width += needed.x + needed.width - alloc->x - alloc->width;
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if (last)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
break;
}
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de descendants d'un même rang. *
* *
* Description : Indique si un espace horizontal final est prévu en bas. *
* *
* Retour : true si l'étage comporte une zone pour liens de boucle. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool has_graph_rank_ending_vspace(const graph_rank_t *grank)
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
GGraphCluster *cluster; /* Bloc à analyser */
result = false;
for (i = 0; i < grank->count && !result; i++)
{
cluster = grank->clusters[i];
result = (cluster->vspaces.pending_count > 0);
}
return result;
}
/******************************************************************************
* *
* Paramètres : iter = début de la boucle de parcours. *
* loop = nombre d'itérations à mener. *
* base = position de base sur l'axe des abscisses. *
* dir = direction du parcours. *
* *
* Description : Affine l'abscisse d'un ensemble de blocs de même rang. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void _place_graph_rank_clusters(GGraphCluster **iter, size_t loop, gint base, int dir)
{
size_t i; /* Boucle de parcours */
GtkAllocation needed; /* Taille requise */
assert(dir == -1 || dir == 1);
for (i = 0; i < loop; i++, iter += dir)
{
g_graph_cluster_dispatch_x(*iter);
g_graph_cluster_compute_needed_alloc(*iter, &needed);
if (dir > 0)
g_graph_cluster_offset_x(*iter, base - needed.x);
else
g_graph_cluster_offset_x(*iter, base - needed.x - needed.width);
base += dir * (needed.width + HORIZONTAL_MARGIN);
}
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de blocs de même rang à manipuler. *
* *
* Description : Organise la disposition d'un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void dispatch_x_graph_rank(const graph_rank_t *grank)
{
size_t mid; /* Position centrale de départ */
gint start; /* Position initiale de départ */
if (grank->count % 2 == 1)
{
if (grank->count > 1)
{
mid = grank->count / 2;
start = grank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
_place_graph_rank_clusters(grank->clusters + mid - 1, mid, start, -1);
start *= -1;
_place_graph_rank_clusters(grank->clusters + mid + 1, mid, start, 1);
}
else
g_graph_cluster_dispatch_x(grank->clusters[0]);
}
else
{
mid = grank->count / 2 - 1;
start = - HORIZONTAL_MARGIN / 2;
_place_graph_rank_clusters(grank->clusters + mid, mid + 1, start, -1);
start *= -1;
_place_graph_rank_clusters(grank->clusters + mid + 1, mid + 1, start, 1);
}
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
* *
* Description : Réorganise au besoin les liens entrants un ensemble de blocs.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void sort_graph_rank_incoming_links(const graph_rank_t *grank)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < grank->count; i++)
g_graph_cluster_sort_incoming_links(grank->clusters[i]);
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
* offset = décalage à appliquer. *
* *
* Description : Décale vers la droite un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void offset_x_graph_rank(const graph_rank_t *grank, gint offset)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < grank->count; i++)
g_graph_cluster_offset_x(grank->clusters[i], offset);
}
/******************************************************************************
* *
* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
* base = position ordonnée à appliquer. *
* *
* Description : Décale vers le bas un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void set_y_for_graph_rank(const graph_rank_t *grank, gint *base)
{
gint max; /* Hauteur maximale rencontrée */
size_t i; /* Boucle de parcours */
GGraphCluster *sub; /* Sous-ensemble traité */
GtkAllocation alloc; /* Allocation courante */
/* On ajoute l'espace vertical pour les lignes horizontales */
if (grank->r2l_count > grank->l2r_count)
max = grank->r2l_count;
else
max = grank->l2r_count;
*base += VERTICAL_MARGIN;
/**
* Comme les liens purement verticaux n'entrainent pas de réservation,
* il n'y a potentiellement pas toujours d'espace à ajouter.
*/
if (max > 0)
{
*base += ((max - 1) * LINK_MARGIN);
*base += VERTICAL_MARGIN;
}
/* On ajoute l'espace requis pour l'affichage des blocs */
max = 0;
for (i = 0; i < grank->count; i++)
{
sub = grank->clusters[i];
g_graph_cluster_set_y(sub, *base);
g_graph_cluster_compute_needed_alloc(sub, &alloc);
if ((alloc.y + alloc.height) > max)
max = alloc.y + alloc.height;
}
*base = max;
}
/* ---------------------------------------------------------------------------------- */
/* ENCADREMENTS D'ESPACES VERTICAUX */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : manager = structure à initialiser. *
* *
* Description : Initialise les réservations liens verticaux. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_vspace_manager(vspace_manager_t *manager)
{
manager->pending = NULL;
manager->pending_count = 0;
manager->left = NULL;
manager->left_count = 0;
manager->right = NULL;
manager->right_count = 0;
}
/******************************************************************************
* *
* Paramètres : manager = structure à vider. *
* *
* Description : Termine les réservations liens verticaux. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void exit_vspace_manager(vspace_manager_t *manager)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < manager->pending_count; i++)
free(manager->pending[i].pts);
if (manager->pending != NULL)
free(manager->pending);
if (manager->left != NULL)
free(manager->left);
if (manager->right != NULL)
free(manager->right);
}
/******************************************************************************
* *
* Paramètres : manager = structure à compléter. *
* from = point de départ du lien concerné. *
* to = point d'arrivée du lien concerné. *
* pts = points intermédiaires du tracé complet final. *
* *
* Description : Inscrit une nouvelle réservation d'espace latéral. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void extend_vspace_manager(vspace_manager_t *manager, leaving_link_t *from, incoming_link_t *to, GdkPoint *pts)
{
vspace_booking_t *new; /* Réservation à constituer */
manager->pending = realloc(manager->pending, ++manager->pending_count * sizeof(vspace_booking_t));
new = &manager->pending[manager->pending_count - 1];
new->from = from;
new->to = to;
new->pts = pts;
}
/******************************************************************************
* *
* Paramètres : manager = gestion des espaces latéraux à consulter. *
* top = le bloc courant est-il le principal ? *
* concat = la zone inférieuse s'ajoute à une similaire ? *
* alloc = emplacement idéal pour l'affichage. [OUT] *
* *
* Description : Détermine l'emplacement requis pour les espaces latéraux. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void compute_vspace_manager_needed_alloc(const vspace_manager_t *manager, bool top, bool concat, GtkAllocation *alloc)
{
gint width; /* Largeur supplémentaire */
/* Extension de la largeur */
width = 0;
if (manager->left_count > 0)
{
if (!top)
width += HORIZONTAL_MARGIN;
width += (manager->left_count - 1) * LINK_MARGIN;
width += HORIZONTAL_MARGIN;
}
if (manager->right_count > 0)
{
width += HORIZONTAL_MARGIN;
width += (manager->right_count - 1) * LINK_MARGIN;
if (!top)
width += HORIZONTAL_MARGIN;
}
alloc->x -= width / 2;
alloc->width += width;
/* Extension de la hauteur */
if (manager->pending_count > 0)
{
if (!concat)
alloc->height += VERTICAL_MARGIN;
alloc->height += (manager->pending_count - 1) * LINK_MARGIN;
alloc->height += VERTICAL_MARGIN;
}
}
/******************************************************************************
* *
* Paramètres : manager = gestion d'espaces latéraux à manipuler. *
* *
* Description : Réorganise au besoin les liens de boucle entre blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void sort_incoming_links_for_vspace_manager(vspace_manager_t *manager)
{
size_t i; /* Boucle de parcours */
vspace_booking_t *pending; /* Elément traité */
gint x1; /* Abscisse de départ de lien */
size_t idx; /* Indice du lien entrant */
gint x2; /* Abscisse d'arrivée de lien */
for (i = 0; i < manager->pending_count; i++)
{
pending = &manager->pending[i];
x1 = g_graph_cluster_compute_leaving_link_position(pending->from->owner, pending->from->index);
idx = g_graph_cluster_find_incoming_link(pending->to->owner, pending->from);
x2 = g_graph_cluster_compute_incoming_link_position(pending->to->owner, idx);
if (x1 < x2)
{
manager->left = realloc(manager->left, ++manager->left_count * sizeof(vspace_booking_t *));
manager->left[manager->left_count - 1] = pending;
}
else
{
manager->right = realloc(manager->right, ++manager->right_count * sizeof(vspace_booking_t *));
manager->right[manager->right_count - 1] = pending;
}
}
}
/******************************************************************************
* *
* Paramètres : manager = structure à consulter. *
* top = le bloc courant est-il le principal ? *
* cluster = graphique de blocs sur lequel s'appuyer. *
* *
* Description : Détermine les abscisses de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *manager, bool top, GGraphCluster *cluster)
{
GtkAllocation needed; /* Espace nécessaire et alloué */
size_t i; /* Boucle de parcours */
vspace_booking_t *booking; /* Réservation à traiter */
gint x; /* Position à appliquer */
g_graph_cluster_compute_needed_alloc(cluster, &needed);
for (i = 0; i < manager->left_count; i++)
{
booking = manager->left[i];
x = i * LINK_MARGIN;
if (!top)
x += HORIZONTAL_MARGIN;
booking->pts[0].x = needed.x + x;
booking->pts[1].x = needed.x + x;
}
if (manager->left_count > 0)
{
if (!top)
x = HORIZONTAL_MARGIN;
else
x = 0;
x += (manager->left_count - 1) * LINK_MARGIN;
x += HORIZONTAL_MARGIN;
/**
* Si la routine est une boucle sans fin,
* alors la boucle peut renvoyer vers le premier bloc.
*/
if (cluster->owner != NULL)
g_graph_cluster_offset_x(cluster->owner, x);
}
for (i = 0; i < manager->right_count; i++)
{
booking = manager->right[i];
x = HORIZONTAL_MARGIN + i * LINK_MARGIN;
booking->pts[0].x = x;
booking->pts[1].x = x;
}
}
/******************************************************************************
* *
* Paramètres : manager = structure à consulter. *
* cluster = graphique de blocs sur lequel s'appuyer. *
* *
* Description : Détermine les ordonnées de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *manager, GGraphCluster *cluster)
{
GtkAllocation needed; /* Espace nécessaire et alloué */
size_t i; /* Boucle de parcours */
vspace_booking_t *booking; /* Réservation à traiter */
g_graph_cluster_compute_needed_alloc(cluster, &needed);
for (i = 0; i < manager->pending_count; i++)
{
booking = &manager->pending[i];
/**
* On corrige le raccourci pris sans distinction de type de lien dans
* la fonction g_graph_cluster_compute_link_y_positions().
*/
booking->from->start[1].y = needed.y + needed.height - VERTICAL_MARGIN;
/* Définition de l'ordonnée des points du lien */
booking->pts[0].y = booking->from->start[1].y;
booking->pts[1].y = booking->to->end[0].y;
}
}
/* ---------------------------------------------------------------------------------- */
/* DEFINITION D'UN CHEF DE FILE */
/* ---------------------------------------------------------------------------------- */
/* Indique le type défini par la GLib pour les mises en disposition graphique. */
G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des mises en disposition graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_class_init(GGraphClusterClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose;
object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize;
}
/******************************************************************************
* *
* Paramètres : cluster = instance à initialiser. *
* *
* Description : Initialise une mise en disposition de blocs en graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_init(GGraphCluster *cluster)
{
init_vspace_manager(&cluster->vspaces);
}
/******************************************************************************
* *
* Paramètres : cluster = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_dispose(GGraphCluster *cluster)
{
g_clear_object(&cluster->block);
g_clear_object(&cluster->display);
G_OBJECT_CLASS(g_graph_cluster_parent_class)->dispose(G_OBJECT(cluster));
}
/******************************************************************************
* *
* Paramètres : cluster = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_finalize(GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < cluster->ta_count; i++)
delete_incoming_link(cluster->top_anchors[i]);
if (cluster->top_anchors != NULL)
free(cluster->top_anchors);
for (i = 0; i < cluster->ba_count; i++)
delete_leaving_link(cluster->bottom_anchors[i]);
if (cluster->bottom_anchors != NULL)
free(cluster->bottom_anchors);
for (i = 0; i < cluster->ranks_count; i++)
exit_graph_rank(&cluster->ranks[i]);
if (cluster->ranks != NULL)
free(cluster->ranks);
exit_vspace_manager(&cluster->vspaces);
G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster));
}
/******************************************************************************
* *
* Paramètres : block = premier bloc du groupe. *
* highlighted = gestionnaire de surbrillance pour segments. *
* binary = binaire charger dont le code est à représenter.*
* *
* Description : *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, GLoadedBinary *binary)
{
GGraphCluster *result; /* Structure à retourner */
GBufferView *view; /* Partie affichée du tampon */
result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL);
/* Encapsulation du bloc d'entrée */
result->block = block;
g_object_ref(G_OBJECT(block));
view = g_code_block_get_view(result->block, highlighted);
result->display = gtk_block_display_new(view);
gtk_widget_show(result->display);
g_loaded_panel_set_content(G_LOADED_PANEL(result->display), G_LOADED_CONTENT(binary));
gtk_block_display_override_view_index(GTK_BLOCK_DISPLAY(result->display), BVW_GRAPH);
gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true);
g_graph_cluster_reset_allocation(result);
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à compléter. *
* *
* Description : Assigne à un bloc et son ensemble un emplacement initial. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_reset_allocation(GGraphCluster *cluster)
{
GtkRequisition requisition; /* Taille à l'écran actuelle */
size_t i; /* Boucle de parcours */
/* Détermination d'une position initiale centrée */
gtk_widget_get_preferred_size(cluster->display, NULL, &requisition);
cluster->alloc.x = -requisition.width / 2;
cluster->alloc.y = 0;
cluster->alloc.width = requisition.width;
cluster->alloc.height = requisition.height;
/* Propagation aux sous-blocs */
for (i = 0; i < cluster->ranks_count; i++)
reset_graph_rank_allocation(&cluster->ranks[i]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à compléter. *
* sub = sous-ensemble à intégrer. *
* *
* Description : Complète un graphique avec un sous-ensemble de blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub)
{
size_t level; /* Niveau du nouvel ensemble */
size_t i; /* Boucle de parcours */
graph_rank_t new; /* Nouvel étage à insérer */
level = g_code_block_get_rank(sub->block);
for (i = 0; i < cluster->ranks_count; i++)
if (get_graph_rank(&cluster->ranks[i]) == level)
break;
if (i == cluster->ranks_count)
{
init_graph_rank(&new, sub);
cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count,
sizeof(graph_rank_t), (__compar_fn_t)cmp_graph_rank, &new);
}
else
extend_graph_rank(&cluster->ranks[i], sub);
sub->owner = cluster;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* all = table regroupant tous les groupes créés. *
* *
* Description : Met en place les embryons de liens nécessaires. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all)
{
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
const block_link_t *dest; /* Bloc visé par une 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 */
g_code_block_lock_dest(cluster->block);
dcount = g_code_block_count_destinations(cluster->block);
for (i = 0; i < dcount; i++)
{
dest = g_code_block_get_destination(cluster->block, i);
switch (dest->type)
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked));
assert(target != NULL);
/* Point de départ */
leaving = create_leaving_link(cluster, cluster->ba_count);
cluster->bottom_anchors = realloc(cluster->bottom_anchors,
++cluster->ba_count * sizeof(leaving_link_t *));
cluster->bottom_anchors[cluster->ba_count - 1] = leaving;
/* Point d'arrivée */
incoming = create_incoming_link(target, dest->type, leaving);
target->top_anchors = realloc(target->top_anchors,
++target->ta_count * sizeof(incoming_link_t *));
target->top_anchors[target->ta_count - 1] = incoming;
/* Etablissement d'un embryon de lien */
for (j = 0; j < cluster->ranks_count; j++)
if (setup_graph_rank_link_for_target(&cluster->ranks[j], cluster, target, leaving))
break;
break;
case ILT_LOOP:
target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked));
assert(target != NULL);
/* Point de départ */
leaving = create_leaving_link(cluster, cluster->ba_count);
cluster->bottom_anchors = realloc(cluster->bottom_anchors,
++cluster->ba_count * sizeof(leaving_link_t *));
cluster->bottom_anchors[cluster->ba_count - 1] = leaving;
/* Point d'arrivée */
midpts = malloc(2 * sizeof(GdkPoint));
midpts = calloc(2, sizeof(GdkPoint));//////////////// REMME
incoming = create_incoming_loop_link(target, midpts, leaving);
target->top_anchors = realloc(target->top_anchors,
++target->ta_count * sizeof(incoming_link_t *));
target->top_anchors[target->ta_count - 1] = incoming;
/* Réservation d'un espace latéral */
extend_vspace_manager(&target->vspaces, leaving, incoming, midpts);
/* Etablissement d'un embryon de lien */
for (j = 0; j < cluster->ranks_count; j++)
if (setup_graph_rank_link_for_target(&cluster->ranks[j], NULL, target, leaving))
break;
break;
default:
break;
}
unref_block_link(dest);
}
g_code_block_unlock_dest(cluster->block);
/* Doit-on forcer un lien strictement vertical ? */
if (cluster->ba_count == 1)
{
assert(!cluster->has_straight);
/**
* Attention : les boucles aussi ont un seul lien sortant !
*
* S'il n'y a qu'un seul lien, on peut s'appuyer sur la variable 'incoming'
* manipulée dans la boucle : c'est forcément elle qui a été mise en place.
*
* Même chose pour 'target'.
*/
if (incoming->type != ILT_LOOP)
{
cluster->has_straight = true;
cluster->straight_level = g_code_block_get_rank(target->block);
cluster->straight_index = 0;
}
}
/* Déplacement d'un éventuel lien central en position centrale */
if (cluster->has_straight)
{
size_t center;
leaving_link_t *tmp;
if (cluster->ba_count % 2 == 0)
center = cluster->ba_count / 2 - 1;
else
center = cluster->ba_count / 2;
if (cluster->straight_index < center)
{
tmp = cluster->bottom_anchors[cluster->straight_index];
memmove(cluster->bottom_anchors + cluster->straight_index,
cluster->bottom_anchors + cluster->straight_index + 1,
(center - cluster->straight_index) * sizeof(leaving_link_t *));
cluster->bottom_anchors[center] = tmp;
for (i = cluster->straight_index; i <= center; i++)
cluster->bottom_anchors[i]->index = i;
cluster->straight_index = center;
}
else if (cluster->straight_index > center)
{
tmp = cluster->bottom_anchors[cluster->straight_index];
memmove(cluster->bottom_anchors + center + 1,
cluster->bottom_anchors + center,
(cluster->straight_index - center) * sizeof(leaving_link_t *));
cluster->bottom_anchors[center] = tmp;
for (i = center; i <= cluster->straight_index ; i++)
cluster->bottom_anchors[i]->index = i;
cluster->straight_index = center;
}
}
/* 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);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à manipuler. *
* *
* Description : Organise la disposition d'un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
{
size_t k; /* Boucle de parcours #1 */
const graph_rank_t *rank; /* Accès confortable au rang */
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 */
/**
* A ce point, tous les blocs parents 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
* de la gauche ne doit pas arriver tout à droite !
*/
//qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
/**
* Il est désormais temps de placer tous les blocs de code inférieurs.
*/
for (k = 0; k < cluster->ranks_count; k++)
{
rank = &cluster->ranks[k];
/* Répartition autour d'une ligne verticale */
if (cluster->has_straight)
{
start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index);
if (get_graph_rank(rank) < cluster->straight_level)
{
/* Répartition à gauche du lien */
for (j = rank->count; j > 0; j--)
if (*rank->clusters[j - 1]->parent_index < cluster->straight_index)
break;
start -= HORIZONTAL_MARGIN / 2;
_place_graph_rank_clusters(rank->clusters, j, start, -1);
/* Répartition à droite du lien */
for (j = 0; j < rank->count; j++)
if (*rank->clusters[j]->parent_index > cluster->straight_index)
break;
start += HORIZONTAL_MARGIN;
_place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1);
}
else if (get_graph_rank(rank) == cluster->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);
target = rank->clusters[0];
idx = g_graph_cluster_find_incoming_link(target, cluster->bottom_anchors[cluster->straight_index]);
end = g_graph_cluster_compute_incoming_link_position(target, idx);
g_graph_cluster_offset_x(target, start - end);
dispatch_x_graph_rank(rank);
}
else
dispatch_x_graph_rank(rank);
}
/* Répartition homogène */
else
dispatch_x_graph_rank(rank);
}
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à manipuler. *
* *
* Description : Réorganise au besoin les liens entrants d'un bloc. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static 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++)
sort_graph_rank_incoming_links(&cluster->ranks[i]);
sort_incoming_links_for_vspace_manager(&cluster->vspaces);
}
/******************************************************************************
* *
* 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 : - *
* *
******************************************************************************/
static 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(cluster->ta_count);
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* offset = décalage à appliquer. *
* *
* Description : Décale vers la droite un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset)
{
size_t i; /* Boucle de parcours */
cluster->alloc.x += offset;
for (i = 0; i < cluster->ranks_count; i++)
offset_x_graph_rank(&cluster->ranks[i], offset);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* base = position ordonnée à appliquer. *
* *
* Description : Décale vers le bas un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base)
{
size_t i; /* Boucle de parcours */
cluster->alloc.y = base;
base += cluster->alloc.height;
for (i = 0; i < cluster->ranks_count; i++)
set_y_for_graph_rank(&cluster->ranks[i], &base);
}
/******************************************************************************
* *
* Paramètres : cluster = encapsulation à consulter. *
* alloc = emplacement idéal pour l'affichage. *
* *
* Description : Détermine l'emplacement requis d'un ensemble de blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc)
{
size_t i; /* Boucle de parcours */
size_t level; /* Niveau du nouvel ensemble */
bool concat; /* Redondance des espaces ? */
*alloc = cluster->alloc;
for (i = 0; i < cluster->ranks_count; i++)
compute_graph_rank_needed_alloc(&cluster->ranks[i], (i + 1) == cluster->ranks_count, alloc);
level = g_code_block_get_rank(cluster->block);
if (cluster->ranks_count == 0)
concat = false;
else
concat = has_graph_rank_ending_vspace(&cluster->ranks[cluster->ranks_count - 1]);
compute_vspace_manager_needed_alloc(&cluster->vspaces, level == 0, concat, alloc);
}
/******************************************************************************
* *
* Paramètres : cluster = encapsulation à consulter. *
* *
* Description : Fournit le composant graphique principal du groupe. *
* *
* Retour : Composant graphique principal utilisé. *
* *
* Remarques : - *
* *
******************************************************************************/
GtkWidget *g_graph_cluster_get_widget(GGraphCluster *cluster)
{
GtkWidget *result;
result = cluster->display;
g_object_ref(G_OBJECT(result));
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = encapsulation à traiter. *
* display = support de destination finale. *
* *
* Description : Dispose chaque noeud sur la surface de destination donnée. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
g_object_ref(G_OBJECT(cluster->display));
gtk_graph_display_put(display, cluster->display, &cluster->alloc);
for (i = 0; i < cluster->ta_count; i++)
{
g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge));
gtk_graph_display_add_edge(display, cluster->top_anchors[i]->edge);
}
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_place(cluster->ranks[i].clusters[j], display);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* index = indice du lien à considérer. *
* half = moitié du nombre de liens en présence. *
* odd = le nombre de liens considérés est-il impair ? *
* *
* Description : Calcule l'abscisse d'un lien pour un bloc. *
* *
* Retour : Abscisse à attribuer au lien. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint _g_graph_cluster_compute_link_position(const GGraphCluster *cluster, size_t index, size_t half, bool odd)
{
gint result; /* Position à retourner */
gint mid_x; /* Abscisse centrale */
mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
if (odd)
{
if (index < half)
result = mid_x - (half - index) * LINK_MARGIN;
else if (index == half)
result = mid_x;
else
result = mid_x + (index - half) * LINK_MARGIN;
}
else
{
if (index < half)
result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN;
else
result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN;
}
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* index = indice du lien à considérer. *
* *
* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. *
* *
* Retour : Abscisse à attribuer à un départ de lien. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index)
{
gint result; /* Position à retourner */
size_t half; /* Indice de répartition égale */
bool odd; /* Partité du nombre de liens */
assert(index < cluster->ba_count);
half = cluster->ba_count / 2;
odd = (cluster->ba_count % 2 == 1);
result = _g_graph_cluster_compute_link_position(cluster, index, half, odd);
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* index = indice du lien à considérer. *
* *
* Description : Calcule l'abscisse d'un lien à son arrivée à un bloc. *
* *
* Retour : Abscisse à attribuer à une arrivée de lien. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *cluster, size_t index)
{
gint result; /* Position à retourner */
size_t half; /* Indice de répartition égale */
bool odd; /* Partité du nombre de liens */
assert(index < cluster->ta_count);
half = cluster->ta_count / 2;
odd = (cluster->ta_count % 2 == 1);
result = _g_graph_cluster_compute_link_position(cluster, index, half, odd);
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Détermine les abscisses des liens de boucle en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
/* Liens de boucle */
compute_loop_link_x_with_vspace_manager(&cluster->vspaces, false /* FIXME */, cluster);
/* Propagation des déterminations */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_compute_loop_link_x_positions(cluster->ranks[i].clusters[j]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Détermine les abscisses de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster)
{
gint mid_x; /* Abscisse centrale */
size_t i; /* Boucle de parcours #1 */
size_t half; /* Indice de répartition égale */
GdkPoint *pt; /* Point à actualiser */
size_t j; /* Boucle de parcours #2 */
mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
/* Du côté des départs... */
if (cluster->ba_count > 0)
for (i = 0; i < cluster->ba_count; i++)
{
pt = &cluster->bottom_anchors[i]->start[0];
pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i);
cluster->bottom_anchors[i]->start[1].x = pt->x;
}
/* Du côté des arrivées... */
if (cluster->ta_count > 0)
{
half = cluster->ta_count / 2;
if (cluster->ta_count % 2 == 1)
{
for (i = half; i > 0; i--)
{
pt = &cluster->top_anchors[i - 1]->end[1];
pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
}
cluster->top_anchors[half]->end[1].x = mid_x;
for (i = half + 1; i < cluster->ta_count; i++)
{
pt = &cluster->top_anchors[i]->end[1];
pt->x = mid_x + (i - half) * LINK_MARGIN;
}
}
else
{
for (i = half; i > 0; i--)
{
pt = &cluster->top_anchors[i - 1]->end[1];
pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
}
for (i = half; i < cluster->ta_count; i++)
{
pt = &cluster->top_anchors[i]->end[1];
pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
}
}
}
for (i = 0; i < cluster->ta_count; i++)
cluster->top_anchors[i]->end[0].x = cluster->top_anchors[i]->end[1].x;
/* Propagation des déterminations */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_compute_link_x_positions(cluster->ranks[i].clusters[j]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à traiter. *
* *
* Description : Réserve de l'espace vertical pour les lignes horizontales. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours #1 */
graph_rank_t *rank; /* Rangée à manipuler */
size_t j; /* Boucle de parcours #2 */
GGraphCluster *sub; /* Bloc inférieur à manipuler */
size_t k; /* Boucle de parcours #3 */
gint x1; /* Abscisse de départ de lien */
gint x2; /* Abscisse d'arrivée de lien */
hspace_booking *new; /* Nouvelle réservation */
for (i = 0; i < cluster->ranks_count; i++)
{
rank = &cluster->ranks[i];
/* Enregistrement des besoins */
for (j = 0; j < rank->count; j++)
{
sub = rank->clusters[j];
for (k = 0; k < sub->ta_count; k++)
{
g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2);
new = create_hspace_booking(x1);
sub->top_anchors[k]->hslot = &new->index;
if (x1 > x2)
rank->right2left = qinsert(rank->right2left, &rank->r2l_count,
sizeof(hspace_booking *),
(__compar_fn_t)cmp_hspace_booking_r2l, &new);
else if (x1 < x2)
rank->left2right = qinsert(rank->left2right, &rank->l2r_count,
sizeof(hspace_booking *),
(__compar_fn_t)cmp_hspace_booking_l2r, &new);
else
sub->top_anchors[k]->hslot = NULL;
}
}
/* Définition des couches */
for (j = 0; j < rank->r2l_count; j++)
rank->right2left[j]->index = j;
for (j = 0; j < rank->l2r_count; j++)
rank->left2right[j]->index = j;
/* Propagation des déterminations */
for (j = 0; j < rank->count; j++)
g_graph_cluster_book_hspace_for_links(rank->clusters[j]);
}
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Détermine les ordonnées de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster)
{
gint y; /* Ordonnée d'application */
size_t i; /* Boucle de parcours #1 */
incoming_link_t *incoming; /* Raccourci pour le confort */
size_t j; /* Boucle de parcours #2 */
/* Du côté des départs... */
if (cluster->ba_count > 0)
{
y = cluster->alloc.y + cluster->alloc.height;
for (i = 0; i < cluster->ba_count; i++)
cluster->bottom_anchors[i]->start[0].y = y;
}
/* Du côté des arrivées... */
if (cluster->ta_count > 0)
{
y = cluster->alloc.y;
for (i = 0; i < cluster->ta_count; i++)
{
incoming = cluster->top_anchors[i];
incoming->end[1].y = y;
incoming->end[0].y = incoming->end[1].y - VERTICAL_MARGIN;
if (incoming->hslot != NULL)
incoming->end[0].y -= *incoming->hslot * LINK_MARGIN;
incoming->other->start[1].y = incoming->end[0].y;
}
}
/* Définition des liens de boucle */
compute_loop_link_y_with_vspace_manager(&cluster->vspaces, cluster);
/* Propagation des déterminations */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_compute_link_y_positions(cluster->ranks[i].clusters[j]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* *
* Description : Applique les positions calculées pour chaque lien graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_resolve_links(const GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
for (i = 0; i < cluster->ta_count; i++)
g_graph_edge_resolve(cluster->top_anchors[i]->edge);
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_resolve_links(cluster->ranks[i].clusters[j]);
}
/* ---------------------------------------------------------------------------------- */
/* CALCUL DE REPARTITION DE BLOCS */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : binary = binaire charger dont le code est à représenter.*
* list = ensemble de blocs basiques à manipuler. *
* index = indice du bloc principal à mettre en place. *
* highlighted = gestionnaire de surbrillance pour segments. *
* pending = liste de blocs restant à traiter. [OUT] *
* all = table regroupant tous les groupes créés. *
* *
* Description : Met en place un ensemble de blocs sous forme graphique. *
* *
* Retour : Ensemble de blocs mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockList *list, size_t index, segcnt_list *highlighted, pending_blocks *pending, GHashTable *all)
{
GGraphCluster *result; /* Instance nouvelle à renvoyer*/
GCodeBlock *block; /* Bloc à manipuler */
#ifndef NDEBUG
gboolean new; /* Bloc déjà traité ? */
#endif
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
const block_link_t *dest; /* Bloc visé par une autre */
size_t j; /* Boucle de parcours #2 */
bool changed; /* Un ajout a été effectué ? */
const bitfield_t *dominators; /* Blocs dominant ce même bloc */
size_t next; /* Indice du prochain bloc */
GGraphCluster *sub; /* Sous-ensemble à intégrer */
block = g_block_list_get_block(list, index);
result = g_graph_cluster_new(block, highlighted, binary);
#ifndef NDEBUG
new = g_hash_table_insert(all, block, result);
assert(new);
#else
g_hash_table_insert(all, block, result);
#endif
/* Détermination des blocs suivants */
g_code_block_lock_dest(block);
dcount = g_code_block_count_destinations(block);
for (i = 0; i < dcount; i++)
{
dest = g_code_block_get_destination(block, i);
switch (dest->type)
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
for (j = 0; j < pending->count; j++)
if (pending->list[j] == dest->linked)
break;
if (j == pending->count)
{
/**
* Il faut vérifier ici si la destination n'a pas déjà été
* empruntée, sauf peine de faire réagir l'assertion plus
* haut au moment de l'insertion.
*
* Le type de code à problème est le suivant :
*
* ...
* if (...)
* ...
* ...
*
* Le code suivant le bloc conditionnel a deux origines,
* qui vont chacune poursuivre le traitement vers ce code
* commun.
*
* Et comme les origines ne sont pas dominantes, on utilise
* la table globale.
*/
if (!g_hash_table_contains(all, dest->linked))
{
g_object_ref(G_OBJECT(dest->linked));
assert((pending->count + 1) < g_block_list_count_blocks(list));
pending->list[pending->count++] = dest->linked;
}
}
break;
default:
break;
}
unref_block_link(dest);
}
g_code_block_unlock_dest(block);
g_object_unref(G_OBJECT(block));
/* Intégration de tous les blocs en attente */
do
{
changed = false;
for (i = 0; i < pending->count && !changed; i++)
{
block = pending->list[i];
dominators = g_code_block_get_domination(block);
if (test_in_bit_field(dominators, index))
{
/* Dépilement */
changed = true;
if ((i + 1) < pending->count)
memmove(&pending->list[i], &pending->list[i + 1],
(pending->count - i - 1) * sizeof(GCodeBlock *));
pending->count--;
/* Intégration */
next = g_code_block_get_index(block);
assert(next < g_block_list_count_blocks(list));
sub = setup_graph_clusters(binary, list, next, highlighted, pending, all);
g_graph_cluster_add_sub(result, sub);
}
g_object_ref(G_OBJECT(block));
}
}
while (changed);
return result;
}
/******************************************************************************
* *
* Paramètres : binary = binaire charger dont le code est à représenter.*
* list = ensemble de blocs basiques à manipuler. *
* highlighted = gestionnaire de surbrillance pour segments. *
* *
* Description : Construit un graphique à partir de blocs basiques. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *list, segcnt_list *highlighted)
{
GGraphCluster *result; /* Structure à retourner */
GHashTable *all; /* Collection des créations */
size_t count; /* Taille de la liste de blocs */
pending_blocks *pending; /* Suivi des blocs à traiter */
GtkAllocation needed; /* Taille requise */
/* Création des éléments */
all = g_hash_table_new(NULL, NULL);
count = g_block_list_count_blocks(list);
pending = malloc(sizeof(pending_blocks) + count * sizeof(GCodeBlock *));
pending->count = 0;
result = setup_graph_clusters(binary, list, 0, highlighted, pending, all);
free(pending);
g_graph_cluster_define_links(result, all);
/* Positionnements dans l'espace */
g_graph_cluster_dispatch_x(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
* de la gauche ne doit pas arriver tout à droite !
*
* Cette consigne est valable pour les liens de boucle également, dont
* l'origine est toujours dans un bloc inférieur au bloc de destination.
* Le premier étant traité après le second, cela oblige à appeler
* g_graph_cluster_dispatch_x() deux fois donc, car on ne peut effectuer
* le tri des liens au début de cette fonction comme c'était fait
* dans les premières versions du code.
*/
g_graph_cluster_sort_incoming_links(result);
g_graph_cluster_reset_allocation(result);
g_graph_cluster_dispatch_x(result);
/* Réajustement vers la droite */
g_graph_cluster_compute_needed_alloc(result, &needed);
g_graph_cluster_offset_x(result, -needed.x);
/* Application finale sur les liens */
/**
* Comme g_graph_cluster_offset_x() n'agit que sur les abscisses et non sur
* les largeurs, on ne peut pas définir les positions pour les liens de boucle
* en amont et les décaler ensuite.
*
* Et comme la mise en place de ce type de lien peut déplacer le bloc parent,
* ses repères pour ses propres liens peuvent être décaler. Il faut ainsi
* une procédure distincte de g_graph_cluster_compute_link_x_positions().
*
* On définit donc l'abscisse de ces liens ici, en redécalant encore un peu
* les blocs au besoin.
*/
g_graph_cluster_compute_loop_link_x_positions(result);
g_graph_cluster_compute_link_x_positions(result);
g_graph_cluster_book_hspace_for_links(result);
g_graph_cluster_set_y(result, 0);
g_graph_cluster_compute_link_y_positions(result);
g_graph_cluster_resolve_links(result);
g_hash_table_unref(all);
return result;
}