path: root/src/gtkext/graph/layout.c

/* Chrysalide - Outil d'analyse de fichiers binaires
 * layout.c - mise en place de graphique
 *
 * Copyright (C) 2009-2014 Cyrille Bagard
 *
 *  This file is part of Chrysalide.
 *
 *  OpenIDA 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.
 *
 *  OpenIDA 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 Foobar.  If not, see <http://www.gnu.org/licenses/>.
 */


#include "layout.h"


#include <malloc.h>
#include <stdlib.h>


#include "node.h"
#include "ranks.h"
#include "nodes/flow.h"
#include "nodes/virtual.h"



/* Mise en disposition de blocs en graphique (instance) */
struct _GGraphLayout
{
    GObject parent;                         /* A laisser en premier        */

    GGraphNode *nodes;                      /* Noeuds graphiques gérés     */
    GGraphRanks *ranks;                     /* Classement en rangs         */

    GGraphEdge **edges;                     /* Liens entre les noeuds      */
    size_t edges_count;                     /* Quantité de ces liens       */

};

/* Mise en disposition de blocs en graphique (classe) */
struct _GGraphLayoutClass
{
    GObjectClass parent;                    /* A laisser en premier        */

};


/* Initialise la classe des mises en disposition graphique. */
static void g_graph_layout_class_init(GGraphLayoutClass *);

/* Initialise une mise en disposition de blocs en graphique. */
static void g_graph_layout_init(GGraphLayout *);

/* Supprime toutes les références externes. */
static void g_graph_layout_dispose(GGraphLayout *);

/* Procède à la libération totale de la mémoire. */
static void g_graph_layout_finalize(GGraphLayout *);



/* Indique le type définit par la GLib pour les mises en disposition graphique. */
G_DEFINE_TYPE(GGraphLayout, g_graph_layout, G_TYPE_OBJECT);


/******************************************************************************
*                                                                             *
*  Paramètres  : klass = classe à initialiser.                                *
*                                                                             *
*  Description : Initialise la classe des mises en disposition graphique.     *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_graph_layout_class_init(GGraphLayoutClass *klass)
{
    GObjectClass *object;                   /* Autre version de la classe  */

    object = G_OBJECT_CLASS(klass);

    object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_layout_dispose;
    object->finalize = (GObjectFinalizeFunc)g_graph_layout_finalize;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = instance à initialiser.                             *
*                                                                             *
*  Description : Initialise une mise en disposition de blocs en graphique.    *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_graph_layout_init(GGraphLayout *layout)
{

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = instance d'objet GLib à traiter.                      *
*                                                                             *
*  Description : Supprime toutes les références externes.                     *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_graph_layout_dispose(GGraphLayout *layout)
{
    g_object_unref(G_OBJECT(layout->nodes));
    g_object_unref(G_OBJECT(layout->ranks));

    G_OBJECT_CLASS(g_graph_layout_parent_class)->dispose(G_OBJECT(layout));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = instance d'objet GLib à traiter.                    *
*                                                                             *
*  Description : Procède à la libération totale de la mémoire.                *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_graph_layout_finalize(GGraphLayout *layout)
{
    G_OBJECT_CLASS(g_graph_layout_parent_class)->finalize(G_OBJECT(layout));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : blocks = ensemble des blocs basiques déjà découpés.          *
*                views  = morceaux de code à afficher de façon organisée.     *
*                count  = quantité de ces morceaux de code.                   *
*                                                                             *
*  Description : Construit un graphique à partir de blocs basiques.           *
*                                                                             *
*  Retour      : Adresse de la structure mise en place.                       *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/
#include "../../arch/instruction-int.h" // REMME
#include "nodes/flow.h"
GGraphLayout *g_graph_layout_new(GInstrBlock *blocks, GtkBufferView **views, size_t count)
{
    GGraphLayout *result;                   /* Structure à retourner       */

    result = g_object_new(G_TYPE_GRAPH_LAYOUT, NULL);

    result->nodes = convert_blocks_into_nodes(blocks, views, count);

    result->ranks = g_graph_ranks_new(count);

    /* Situations verticales grossières */

    bool _register_cb(GFlowNode *node, GNodeVisitState state, GGraphLayout *layout)
    {
        if (state == GVS_NODE)
            g_flow_node_link(node, layout, layout->nodes);
        return true;
    }

    g_graph_node_visit_nodes(result->nodes, (graph_node_visitor_cb)_register_cb, result);

    bool _print_dbg_cb(GFlowNode *node, GNodeVisitState state, int *depth)
    {
        int i;

        if (state == GVS_ENTER || state == GVS_NODE)
        {
            for (i = 0; i < *depth; i++)
                printf("   ");

            printf("- %p\n", node);

        }

        if (state == GVS_ENTER) (*depth)++;
        else if (state == GVS_EXIT) (*depth)--;

        return true;

    }

    printf("==== graph ====\n");
    g_graph_node_visit_nodes(result->nodes, (graph_node_visitor_cb)_print_dbg_cb, (int []){ 0 });
    printf("\n");

    /* Actualisation... */

    g_graph_layout_refresh(result);

    bool _print_dbg_ext_cb(GGraphNode *node, GNodeVisitState state, int *depth)
    {
        int i;
        PendingPositionFlags pending_flag;
        char *flags;
        GtkAllocation alloc;
        GArchInstruction *first;
        GArchInstruction *last;

        char *flags_list[] = {
            "NONE",
            "DIRECT_X",
            "LEFT_MARGIN",
            "RIGHT_MARGIN",
            "LEFT_NODE",
            "RIGHT_NODE"
        };  


        if (state == GVS_ENTER || state == GVS_NODE)
        {



            for (i = 0; i < *depth; i++)
                printf("   ");

            g_graph_node_get_pending_position(node, &pending_flag, NULL);
            flags = flags_list[pending_flag];

            alloc = g_graph_node_get_allocation(node);
            printf("- %p -  \"%s\"  -  (%d ; %d) - (%d ; %d)", node,
                   flags,
                   alloc.x, alloc.y,
                   alloc.width, alloc.height);

            if (G_IS_FLOW_NODE(node))
            {
                printf("  - rank = %u  -", g_graph_node_get_rank(node));

                g_flow_block_get_boundary(g_flow_node_get_block(G_FLOW_NODE(node)), &first, &last);
                printf("  - 0x%08x <-> 0x%08x", first->range.addr.virtual, last->range.addr.virtual);
            }

            printf("\n");

        }

        if (state == GVS_ENTER) (*depth)++;
        else if (state == GVS_EXIT) (*depth)--;

        return true;

    }

    printf("==== graph ====\n");
    g_graph_node_visit_nodes(result->nodes, (graph_node_visitor_cb)_print_dbg_ext_cb, (int []){ 0 });
    printf("\n");

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = disposition en graphique à compléter.               *
*                edge   = lien entre noeuds à conserver.                      *
*                                                                             *
*  Description : Ajoute un lien entre deux noeuds au graphique.               *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_layout_add_edge(GGraphLayout *layout, GGraphEdge *edge)
{
    layout->edges = (GGraphEdge **)realloc(layout->edges,
                                           ++layout->edges_count * sizeof(GGraphEdge *));

    layout->edges[layout->edges_count - 1] = edge;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = graphique à mettre à jour.                          *
*                                                                             *
*  Description : Met à jour les positions des différents noeuds.              *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/
#include "node-int.h"
void g_graph_layout_refresh(GGraphLayout *layout)
{
    size_t i;                               /* Boucle de parcours          */


    int counter = 0;


 restart:

    g_graph_ranks_reset_reservations(layout->ranks);

    bool _reset_cb(GGraphNode *node, GNodeVisitState state, void *unused)
    {
        g_graph_node_reset_position(node);
        if (state == GVS_NODE)
            g_flow_node_register_rank(G_FLOW_NODE(node), layout->ranks);
        return true;
    }

    g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_reset_cb, NULL);

    /* Traitement des positions horizontales */

    for (i = 0; i < layout->edges_count; i++)
        g_graph_edge_reserve_vertical_space(layout->edges[i], layout->nodes, layout->ranks);

    /* Traitement des positions horizontales */

    g_graph_node_set_x_position(layout->nodes, GRAPH_HORIZONTAL_MARGIN);

    g_graph_node_prepare_x_line(layout->nodes, layout->nodes);
    g_graph_node_apply_position(layout->nodes);



    bool _reorder_cb(GGraphNode *node, GNodeVisitState state, GGraphNode *nodes)
    {
        if (state == GVS_NODE)
            g_flow_node_reorder_slots(G_FLOW_NODE(node), nodes);
        return true;
    }

    //qsort(layout->edges, layout->edges_count, sizeof(GGraphEdge *), (__compar_fn_t)g_graph_edge_compare);



    if (counter++ == 0)
    {
    g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_reorder_cb, layout->nodes);
    goto restart;
    }

    /*
    bool _rinint_cb(GGraphNode *node, GNodeVisitState state, GGraphNode *nodes)
    {
        node->alloc.x = UNINITIALIZED_NODE_POS;
        node->alloc.y = UNINITIALIZED_NODE_POS;
        return true;
    }

    g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_rinint_cb, layout->nodes);


    g_graph_node_apply_position(layout->nodes);
    */

    qsort(layout->edges, layout->edges_count, sizeof(GGraphEdge *), (__compar_fn_t)g_graph_edge_compare);



    for (i = 0; i < layout->edges_count; i++)
        g_graph_edge_reserve_horizontal_space(layout->edges[i], layout->ranks);

    /* Traitement des positions verticales */

    g_graph_ranks_compute_y_line(layout->ranks);

    bool _apply_cb(GFlowNode *node, GNodeVisitState state, GGraphRanks *ranks)
    {
        if (state == GVS_NODE)
            g_flow_node_apply_rank(node, ranks);
        return true;
    }

    g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_apply_cb, layout->ranks);

    /* Mise en place des liens */

    for (i = 0; i < layout->edges_count; i++)
        g_graph_edge_compute(layout->edges[i], layout->ranks);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = disposition en graphique prête.                     *
*                view   = support de destination finale.                      *
*                                                                             *
*  Description : Dispose chaque noeud sur la surface de destination donnée.   *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_layout_place(GGraphLayout *layout, GtkGraphView *view)
{
    bool _place_cb(GFlowNode *node, GNodeVisitState state, GtkGraphView *view)
    {
        if (state == GVS_NODE)
            g_flow_node_place(node, view);
        return true;
    }

    g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_place_cb, view);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout      = graphique constitué à consulter.               *
*                requisition = dimensions souhaitées. [OUT]                   *
*                                                                             *
*  Description : Fournit la taille requise pour un plein rendu du graphique.  *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_layout_size_request(const GGraphLayout *layout, GtkRequisition *requisition)
{
    GtkAllocation alloc;                    /* Largeur totale requise      */

    alloc = g_graph_node_get_allocation(layout->nodes);
    requisition->width = alloc.width + 2 * GRAPH_HORIZONTAL_MARGIN;

    requisition->height = g_graph_ranks_get_height(layout->ranks);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : layout = graphique à représenter.                            *
*                cairo  = assistant pour le rendu graphique.                  *
*                arrow  = indique le besoin en flèche à l'arrivée.            *
*                                                                             *
*  Description : Dessine les liens graphiques enregistrés dans le moteur.     *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_layout_draw(const GGraphLayout *layout, cairo_t *cairo, bool arrow)
{
    size_t i;                               /* Boucle de parcours          */

    for (i = 0; i < layout->edges_count; i++)
        g_graph_edge_draw(layout->edges[i], cairo, arrow);

}