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

/* Chrysalide - Outil d'analyse de fichiers binaires
 * node.c - éléments de graphiques chez dot
 *
 * Copyright (C) 2009-2013 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 "node.h"


#include <assert.h>
#include <malloc.h>
#include <stdio.h>
#include <string.h>


#include "node-int.h"
#include "nodes/flow.h"
#include "nodes/virtual.h"
#include "../../common/extstr.h"



/* -------------------------- GESTION DES NOEUDS A L'UNITE -------------------------- */


/* Initialise la classe des intermédiaires avec les noeuds dot. */
static void g_graph_node_class_init(GGraphNodeClass *);

/* Initialise la classe des intermédiaires avec les noeuds dot. */
static void g_graph_node_init(GGraphNode *);

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

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



/* ---------------------------------------------------------------------------------- */
/*                            GESTION DES NOEUDS A L'UNITE                            */
/* ---------------------------------------------------------------------------------- */


/* Indique le type définit par la GLib pour le noeud. */
G_DEFINE_TYPE(GGraphNode, g_graph_node, G_TYPE_OBJECT);


/******************************************************************************
*                                                                             *
*  Paramètres  : klass = classe à initialiser.                                *
*                                                                             *
*  Description : Initialise la classe des intermédiaires avec les noeuds dot. *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

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

    object = G_OBJECT_CLASS(klass);

    object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_node_dispose;
    object->finalize = (GObjectFinalizeFunc)g_graph_node_finalize;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = instance à initialiser.                               *
*                                                                             *
*  Description : Initialise la classe des intermédiaires avec les noeuds dot. *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_graph_node_init(GGraphNode *node)
{
    node->alloc.x = UNINITIALIZED_NODE_POS;
    node->alloc.y = UNINITIALIZED_NODE_POS;

}


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

static void g_graph_node_dispose(GGraphNode *node)
{
    G_OBJECT_CLASS(g_graph_node_parent_class)->dispose(G_OBJECT(node));

}


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

static void g_graph_node_finalize(GGraphNode *node)
{
    G_OBJECT_CLASS(g_graph_node_parent_class)->finalize(G_OBJECT(node));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à consulter.                          *
*                                                                             *
*  Description : Fournit le rang du noeud dans le graphique.                  *
*                                                                             *
*  Retour      : Indice supérieur ou égal à zéro.                             *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

unsigned int g_graph_node_get_rank(const GGraphNode *node)
{
    return G_GRAPH_NODE_GET_CLASS(node)->get_rank(node);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                                                                             *
*  Description : Réinitialise la position d'un noeud de graphique.            *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_reset_position(GGraphNode *node)
{
    node->alloc.x = UNINITIALIZED_NODE_POS;
    node->alloc.y = UNINITIALIZED_NODE_POS;

    node->pending_flag = PPF_NONE;

    if (G_GRAPH_NODE_GET_CLASS(node)->reset_pos != NULL)
        G_GRAPH_NODE_GET_CLASS(node)->reset_pos(node);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à traiter.                     *
*                nodes = ensemble des noeuds en place.                        *
*                                                                             *
*  Description : Définit les abscisses relatives du contenu d'un noeud.       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_prepare_x_line(GGraphNode *node, GGraphNode *nodes)
{
    G_GRAPH_NODE_GET_CLASS(node)->prepare_x(node, nodes);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                                                                             *
*  Description : Applique une position finale au noeud.                       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_apply_position(GGraphNode *node)
{
    gint x_pos;                             /* Position de référence       */
    GGraphNode *ref;                        /* Accès rapide                */

    if (G_GRAPH_NODE_GET_CLASS(node)->apply_pos != NULL)
        G_GRAPH_NODE_GET_CLASS(node)->apply_pos(node);

    switch (node->pending_flag)
    {
        case PPF_DIRECT_X:
            assert(g_graph_node_has_x_position(node->pending_rel));
            g_graph_node_get_position(node->pending_rel, &x_pos, NULL);
            x_pos += node->pending_pos.direct_x;
            g_graph_node_set_x_position(node, x_pos);
            break;

        case PPF_LEFT_MARGIN:
            assert(g_graph_node_has_x_position(node->pending_rel));
            g_graph_node_get_position(node->pending_rel, &x_pos, NULL);
            x_pos += EDGE_SLOT_HORIZ_MARGIN + node->pending_pos.left_margin;
            g_graph_node_set_x_position(node, x_pos);
            break;

        case PPF_RIGHT_MARGIN:
            assert(g_graph_node_has_x_position(node->pending_rel));
            g_graph_node_get_position(node->pending_rel, &x_pos, NULL);
            x_pos += node->pending_pos.right_margin;
            x_pos -= (EDGE_SLOT_HORIZ_MARGIN + node->alloc.width);
            g_graph_node_set_x_position(node, x_pos);
            break;

        case PPF_LEFT_NODE:
            ref = node->pending_pos.left_node;
            x_pos = ref->alloc.x - NODE_HORIZONTAL_MARGIN - node->alloc.width;
            g_graph_node_set_x_position(node, x_pos);
            break;

        case PPF_RIGHT_NODE:
            ref = node->pending_pos.right_node;
            x_pos = ref->alloc.x + ref->alloc.width - NODE_HORIZONTAL_MARGIN;
            g_graph_node_set_x_position(node, x_pos);
            break;

        default:
            /* Position traitée par l'appelant */
            break;

    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*  Paramètres  : node   = noeud graphique à manipuler.                        *
*                x      = abscisse à intégrer.                                *
*                direct = indique un tracé direct éventuel.                   *
*                                                                             *
*  Description : Altère la position du noeud d'encapsulation.                 *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_set_x_position(GGraphNode *node, gint x)
{
    if (G_GRAPH_NODE_GET_CLASS(node)->set_pos != NULL && x != GRAPH_HORIZONTAL_MARGIN)
        G_GRAPH_NODE_GET_CLASS(node)->set_pos(node, x);

    node->alloc.x = x;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                flag = nature de l'indication à intégrer.                    *
*                pos  = argument supplémentaire à venir chercher.             *
*                rel  = éventuelle référence pour une relation relative.      *
*                                                                             *
*  Description : Prépare la position du noeud pour l'alignement des liens.    *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_set_pending_position(GGraphNode *node, PendingPositionFlags flag, pending_position pos, GGraphNode *rel)
{
    if (node->pending_flag != PPF_NONE)
        return;

    node->pending_pos = pos;
    node->pending_flag = flag;
    node->pending_rel = rel;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                flag = nature de l'indication à intégrer. [OUT]              *
*                pos  = argument supplémentaire à venir chercher. [OUT]       *
*                                                                             *
*  Description : Indique la position du noeud pour l'alignement des liens.    *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_get_pending_position(GGraphNode *node, PendingPositionFlags *flag, pending_position *pos)
{
    *pos = node->pending_pos;
    *flag = node->pending_flag;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à consulter.                          *
*                x    = éventuelle abscisse à recevoir ou NULL. [OUT]         *
*                y    = éventuelle ordonnée à recevoir ou NULL. [OUT]         *
*                                                                             *
*  Description : Fournit la position du noeud d'encapsulation.                *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_graph_node_get_position(const GGraphNode *node, gint *x, gint *y)
{
    if (x != NULL) *x = node->alloc.x;
    if (y != NULL) *y = node->alloc.y;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à consulter.                          *
*                                                                             *
*  Description : Indique l'espace requis pour un noeud d'encapsulation.       *
*                                                                             *
*  Retour      : Espace constitué, entièrement ou non.                        *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GtkAllocation g_graph_node_get_allocation(const GGraphNode *node)
{
    return node->alloc;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node     = noeud graphique démarrant la visite.              *
*                callback = ensemble de blocs à parcourir.                    *
*                data     = donnée utilisateur à associer au parcours.        *
*                                                                             *
*  Description : Parcourt tous les noeuds graphiques dans un ordre donné.     *
*                                                                             *
*  Retour      : true si le parcours a été jusqu'à son terme, false sinon.    *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

bool g_graph_node_visit_nodes(GGraphNode *node, graph_node_visitor_cb callback, void *data)
{
    return G_GRAPH_NODE_GET_CLASS(node)->visit(node, callback, data);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : nodes  = noeud au sommet de la hiérarchie.                   *
*                target = élément à retrouver dans l'ensemble de noeuds.      *
*                                                                             *
*  Description : Recherche le noeud contenant un autre noeud.                 *
*                                                                             *
*  Retour      : Noeud trouvé ou NULL si aucun.                               *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *g_graph_node_find_container(GGraphNode *nodes, GGraphNode *target)
{
    GGraphNode *result;                     /* Trouvaille à retourner      */

    result = NULL;

    if (G_GRAPH_NODE_GET_CLASS(nodes)->contain != NULL)
        result = G_GRAPH_NODE_GET_CLASS(nodes)->contain(nodes, target);

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : nodes  = noeud au sommet de la hiérarchie.                   *
*                ref    = noeud indiquant le niveau de référence.             *
*                target = élément à retrouver dans l'ensemble de noeuds.      *
*                                                                             *
*  Description : Recherche le noeud contenant un autre noeud à un même niveau.*
*                                                                             *
*  Retour      : Noeud trouvé ou NULL si aucun.                               *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *g_graph_node_find_container_at_same_level(GGraphNode *nodes, GGraphNode *ref, GGraphNode *target)
{
    GGraphNode *result;                     /* Trouvaille à retourner      */
    GGraphNode *level;                      /* Niveau de référence         */
    GGraphNode *container;                  /* Support de la cible         */

    result = NULL;

    level = g_graph_node_find_container(nodes, ref);

    container = g_graph_node_find_container(nodes, target);

    if (container == level)
        result = target;
    else
    {
        if (container == NULL)
            result = NULL;
        else
            result = g_graph_node_find_container_at_same_level(nodes, ref, container);
    }

    return result;

}



/* ---------------------------------------------------------------------------------- */
/*                         MANIPULATION D'ENSEMBLES DE NOEUDS                         */
/* ---------------------------------------------------------------------------------- */


/******************************************************************************
*                                                                             *
*  Paramètres  : views = liste de vues à parcourir.                           *
*                count = taille de la liste.                                  *
*                addrt = adresse de début du noeud recherché.                 *
*                                                                             *
*  Description : Recherche une vue donnée dans une série de vues.             *
*                                                                             *
*  Retour      : Vue trouvée ou NULL si aucun.                                *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GtkBufferView *find_graph_view_by_start_address(GtkBufferView **views, size_t count, const vmpa2t *addr)
{
    GtkBufferView *result;                  /* Trouvaille à remonter       */
    size_t i;                               /* Boucle de parcours          */
    GBufferView *buffer;                    /* Tampon d'une partie de code */
    vmpa2t start;                           /* Adresse de départ du tampon */

    result = NULL;

    for (i = 0; i < count && result == NULL; i++)
    {
        buffer = gtk_buffer_view_get_buffer(views[i]);
        g_buffer_view_get_restrictions(buffer, &start, NULL);

        if (cmp_vmpa(&start, addr) == 0)
            result = views[i];

    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : block = 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 : Réalise une conversion de blocs en noeuds.                   *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *convert_blocks_into_nodes(GInstrBlock *block, GtkBufferView **views, size_t count)
{
    GGraphNode *result;                     /* Instance nouvelle à renvoyer*/
    vmpa2t start;                           /* Adresse de départ           */
    GtkBufferView *view;                    /* Vue existante à retrouver   */
    size_t max;                             /* Nombre de blocs à gérer     */
    size_t i;                               /* Boucle de parcours          */
    GInstrBlock *sub_block;                 /* Sous-bloc intégré           */
    GGraphNode *child;                      /* Conversion à mémoriser      */

    result = NULL;

    if (G_IS_FLOW_BLOCK(block))
    {
        g_flow_block_get_boundary_addresses(G_FLOW_BLOCK(block), &start, NULL);
        view = find_graph_view_by_start_address(views, count, &start);

        result = g_flow_node_new(G_FLOW_BLOCK(block), view);

    }
    else if (G_IS_VIRTUAL_BLOCK(block))
    {
        result = g_virtual_node_new(G_VIRTUAL_BLOCK(block));

        max = g_virtual_block_count_children(G_VIRTUAL_BLOCK(block));

        for (i = 0; i < max; i++)
        {
            sub_block = g_virtual_block_get_child(G_VIRTUAL_BLOCK(block), i);
            child = convert_blocks_into_nodes(sub_block, views, count);

            g_virtual_node_add_child(G_VIRTUAL_NODE(result), child);

        }

    }
    /*else BUG_ON(1); */

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : nodes = noeud au sommet de la hiérarchie.                    *
*                instr = instruction à retrouver.                             *
*                entry = position de cette instruction : première ou dernière.*
*                                                                             *
*  Description : Recherche le noeud contenant une instruction donnée.         *
*                                                                             *
*  Retour      : Noeud trouvé ou NULL.                                        *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *_find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr, bool entry)
{
    GGraphNode *result;                     /* Trouvaille à retourner      */
    struct visit_params {
        GArchInstruction *instr;            /* Instruction recherchée      */
        bool entry;                         /* Première ou dernière ?      */
        GGraphNode *found;                  /* Remontée du noeud trouvé    */
    } params;                               /* Paramètres pour le parcours */

    params.instr = instr;
    params.entry = entry;
    params.found = NULL;

    bool _find_node_cb(GFlowNode *node, GNodeVisitState state, struct visit_params *params)
    {
        bool result;

        if (state == GVS_NODE)
        {
            if ((params->entry && g_flow_node_start_with(node, params->instr))
                || (!params->entry && g_flow_node_end_with(node, params->instr)))
            {
                params->found = G_GRAPH_NODE(node);
            }
            result = (params->found == NULL);
        }
        else result = true;

        return result;

    }

    g_graph_node_visit_nodes(nodes, (graph_node_visitor_cb)_find_node_cb, &params);

    result = params.found;

    return result;

}