# -*- coding: utf-8 -*-

# This code is part of Amoco
# Copyright (C) 2006-2011 Axel Tillequin (bdcht3@gmail.com)
# published under GPLv2 license

"""
cfg.py
======

This module provides elements to define *control flow graphs* (CFG).
It is based essentially on classes provided by the `grandalf`_ package.

.. _grandalf: https://grandalf.readthedocs.io/

"""

from amoco.logger import Log

logger = Log(__name__)
logger.debug("loading module")

from grandalf.graphs import Vertex, Edge, Graph
from amoco.cas.mapper import mapper
from amoco.system.memory import MemoryZone
from collections import defaultdict
from amoco.code import _code_misc_default


# ------------------------------------------------------------------------------
class node(Vertex):
    """A node is a graph vertex that embeds a :mod:`code` object.
    It extends the :ref:`Vertex <grandalf:Vertex>` class in order to compare
    nodes by their data blocks rather than their id.

    Args:
        acode : an instance of :class:`block`, :class:`func` or :class:`xfunc`.

    Attributes:
        data : the reference to the ``acode`` argument above.
        e (list[link]): inherited from `grandalf`_, the list of edges with this
            node. In amoco, edges and vertices are called links and nodes.
        c (graph_core): reference to the connected component that contains this
            node.
        view: the block or func view object associated with our data.
        map(mapper): the map object associated with out data.

    Methods:
        cut(address): reduce the block size up to given address if data is block.
        deg(): returns the *degree* of this node (number of its links).

        N(dir=0): provides a list of *neighbor* nodes, all if *dir* parameter is 0,
            parent nodes if *dir<0*, children nodes if *dir>0*.

        e_dir(dir=0): provides a list of *links*, all if *dir* parameter is 0,
            incoming links if *dir<0*, outgoing links if *dir>0*.

        e_in(): a shortcut for ``e_dir(-1)``.

        e_out(): a shortcut for ``e_dir(+1)``.

        e_with(v): provides a *link* to or from v. Should be used with caution: if there is
            several links between current node and v this method gives the first one
            listed only, independently of the direction.

        e_to(v): provides the *link* from current node to node v.

        e_from(v): provides the *link* to current node from node v.

    """

    def __init__(self, acode):
        super().__init__(data=acode)
        pre = "blck_" if acode._is_block else "func_"
        self.name = "{}{}".format(pre, str(self.data.address))
        self._map = None
        self.misc = defaultdict(_code_misc_default)

    @property
    def view(self):
        """view : view property of the node's code object."""
        return self.data.view

    @property
    def map(self):
        if self._map:
            return self._map
        else:
            if self.data._is_block:
                self._map = mapper(self.data.instr)
            return self._map

    def cut(self, address):
        if self.data._is_block:
            nl = self.data.cut(address)
            self._map = None
            return nl
        logger.warning("cut: not a block")
        return None

    def __repr__(self):
        return "<%s [%s] at 0x%x>" % (self.__class__.__name__, self.name, id(self))

    def __hash__(self):
        return id(self)

    def __len__(self):
        return self.data.length

    def __eq__(self, n):
        return hash(self) == hash(n)

    def __lt__(self, n):
        return hash(self) < hash(n)

    def __getitem__(self, i):
        res = node(self.data.__getitem__(i))
        return res

    def __getstate__(self):
        return (self.index, self.data, self.name)

    def __setstate__(self, state):
        self.__index, self.data, self.name = state
        self._map = None
        self.c = None
        self.e = []


# ------------------------------------------------------------------------------
class link(Edge):
    """A directed edge between two nodes. It extends :ref:`Edge <grandalf:Edge>`
    class in order to compare edges based on their data rather than id.

    Args:
        x (node) : the source node.
        y (node) : the destination node.
        w (int)  : an optional weight value, default 1.
        data     : a list of conditional expressions associated with the link.
        connect  : a flag to indicate that a new node should be automatically
                   added to the connected component of its parent/child if it
                   is defined (default False).

    Attributes:
        name : the name property returns the string composed of source and
               destination node's *addresses*.
        deg (int): 1 if source and destination are the same node, 0 otherwise.
        v (tuple[node]): inherited from `grandalf`_, the 2-tuple (source,dest)
            nodes of the link.
        feedback: a flag indicating that this link is involved in a loop,
                  used internally by `grandalf`_ layout algorithm.

    Methods:
        attach(): add current link to its :attr:`node.e` attribute list.

        detach(): remove current link from its :attr:`node.e` attribute list.

    """

    def __str__(self):
        n0 = self.v[0].name
        n1 = self.v[1].name
        c = "?" if self.data else "-"
        return "%s -%s-> %s" % (n0, c, n1)

    def __repr__(self):
        return "<%s [%s] at 0x%x>" % (self.__class__.__name__, self.name, id(self))

    @property
    def name(self):
        n0 = self.v[0].name
        n1 = self.v[1].name
        return "%s -> %s" % (n0, n1)

    def __eq__(self, e):
        return hash(self) == hash(e)

    def __lt__(self, e):
        return hash(self) < hash(e)

    def __hash__(self):
        return hash(self.name)

    def __getstate__(self):
        xi, yi = (self.v[0].index, self.v[1].index)
        return (xi, yi, self.w, self.data, self.feedback)

    def __setstate__(self, state):
        xi, yi, self.w, self.data, self.feedback = state
        self._v = [xi, yi]
        self.deg = 0 if xi == yi else 1


# ------------------------------------------------------------------------------
class graph(Graph):
    """a :ref:`<grandalf:Graph>` that represents a set of functions as its
    individual connected components.

    Args:
        V (iterable[node]) : the set of (possibly detached) nodes.
        E (iterable[link]) : the set of links of this graph.

    Attributes:
        C : the list of :class:`graph_core <grandalf:graph_core>` connected
            components of the graph.
        support (:class:`~system.core.MemoryZone`): the abstract memory zone
            holding all nodes contained in this graph.
        overlay : defaults to None, another instance of MemoryZone
            with nodes of the graph that overlap other nodes already mapped
            in :attr:`support`.

    Methods:
        get_by_name(name): get the node with the given name (as string).

        get_with_address(vaddr): get the node that contains the given *vaddr*
            :class:`~cas.expressions.cst` expression.

        add_vertex(v,[support=None]): add node v to the graph and declare
            node support in the default MemoryZone or the overlay zone if
            provided as support argument. This method deals with a node v
            that cuts or swallows a previously added node.

        remove_vertex(v): remove node v from the graph.

        add_edge(e): add link to the graph as well as possible new nodes.

        remove_edge(e): remove the provided link.

        get_vertices_count(): a synonym for :meth:`order`.

        V(): generator of all nodes of the graph.

        E(): generator of all links of the graph.

        N(v,f_io=0): returns the neighbors of node v in direction f_io.

        path(x,y,f_io=0,hook=None):

        order(): number of nodes in the graph.

        norm(): number of links in the graph.

        deg_min(): minimum degree of nodes.

        deg_max(): maximum degree of nodes.

        deg_avg(): average degree of nodes.

        eps(): ratio of links over nodes (norm/order).

        connected(): boolean flag indicating that the graph as
            only one connected component.

        components(): synonym for attribute :attr:`C`.

    """

    def __init__(self, *args, **kargs):
        self.support = MemoryZone()
        self.overlay = None
        super(graph, self).__init__(*args, **kargs)

    def __cut_add_vertex(self, v, mz, vaddr, mo):
        oldnode = mo.data.val
        if oldnode == v:
            return oldnode
        # so v cuts an existing block:
        # if vaddr matches an oldblock instr, cut it:
        cutdone = oldnode.cut(vaddr)
        if not cutdone:
            if mz is self.overlay:
                logger.warning("double overlay block at %s" % vaddr)
                v = super(graph, self).add_vertex(v)
                v.misc["double-overlay"] = 1
                return v
            overlay = self.overlay or MemoryZone()
            return self.add_vertex(v, support=overlay)
        else:
            oldnode.misc["cut"] = cutdone
            v = super(graph, self).add_vertex(v)  # ! avoid recursion for add_edge
            mz.write(vaddr, v)
            self.add_edge(link(oldnode, v))
            for n in oldnode.N(+1):
                self.add_edge(link(v, n))
                self.remove_edge(oldnode.e_to(n))
            return v

    def add_vertex(self, v, support=None):
        if v.data._is_func:
            return super(graph, self).add_vertex(v)
        # insert block:
        vaddr = v.data.address
        if support is None:
            support = self.support
        else:
            logger.verbose("add overlay block at %s" % vaddr)
            self.overlay = support
        i = support.locate(vaddr)
        # check if block intersects others:
        if i is not None:
            mo = support._map[i]
            if vaddr in mo:
                return self.__cut_add_vertex(v, support, vaddr, mo)
            else:  # v does not cut an existing block,
                try:  # but may swallow next one...
                    nextmo = support._map[i + 1]
                except IndexError:
                    # no more nodes here so back to default case:
                    pass
                else:
                    nextnode = nextmo.data.val
                    if vaddr + len(v) > nextnode.data.address:
                        # nextnode is inside v...
                        # try to cut v at nextnode bound:
                        cutdone = v.cut(nextnode.data.address)
                        if not cutdone:
                            # nextnode address does not match an instruction in v...
                            # thats an overlay:
                            if support is self.overlay:
                                # we already are in overlay...
                                logger.warning("double overlay block at %s" % vaddr)
                                v = super(graph, self).add_vertex(v)
                                v.misc["double-overlay"] = 1
                                return v
                            support = self.overlay or MemoryZone()
        v = super(graph, self).add_vertex(v)  # before support write !!
        support.write(vaddr, v)
        return v

    def get_by_name(self, name):
        for v in self.V():
            if v.name == name:
                return v
        return None

    def get_with_address(self, vaddr):
        i = self.support.locate(vaddr)
        if i is not None:
            mo = self.support._map[i]
            if vaddr in mo:
                return mo.data.val
        return None

    def to_dot(self, name=None, full=True):
        dot = "digraph G {\n"
        dot += "    graph [orientation=landscape, labeljust=left];\n"
        dot += "    node [shape=box,fontname=monospace,fontsize=8];\n"
        if name:
            g = self.get_by_name(name).c
        else:
            g = self
        for v in g.V():
            txt = "%s" % v.data if full else "%s [%d]" % (v.name, len(v.data.instr))
            dot += '    "%s" [label="%s"];\n' % (id(v), txt)
        for e in g.E():
            dot += '    "%s" -> "%s"' % (id(e.v[0]), id(e.v[1]))
            dot += " [style=bold];\n" if e.feedback else ";\n"
        dot += "}\n"
        return dot
