import graph


class InterferenceGraphNode(graph.Node):
    def __init__(self, g, varname):
        super().__init__(g)
        self.temps = [varname]
        self.moves = set()

    def __repr__(self):
        return 'IGN<{}>'.format(self.temps)


class InterferenceGraph(graph.Graph):
    """
        Interference graph.
    """
    def __init__(self, flowgraph):
        """ 
            Create a new interference graph from a flowgraph 
        """
        super().__init__()
        # Calculate liveness in CFG:
        ###
        # Liveness:
        #  in[n] = use[n] UNION (out[n] - def[n])
        #  out[n] = for s in n.succ in union in[s]
        ###
        for n in flowgraph.nodes:
            n.live_in = set()
            n.live_out = set()

        # Dataflow fixed point iteration:
        change = True
        while change:
            change = False
            for n in flowgraph.nodes:
                _in = n.live_in
                _out = n.live_out
                n.live_in = n.uses | (n.live_out - n.defs)
                if n.Succ:
                    n.live_out = set.union(*(s.live_in for s in n.Succ))
                else:
                    n.live_out = set()
                change = change or (_in != n.live_in) or (_out != n.live_out)

        # Construct interference graph:
        for n in flowgraph.nodes:
            for tmp in n.live_out:
                n1 = self.getNode(tmp)
                for tmp2 in (n.live_out - {tmp}):
                    n2 = self.getNode(tmp2)
                    self.addEdge(n1, n2)

    def getNode(self, tmp):
        # Linear search
        # TODO: can be improved for speed!
        for n in self.nodes:
            if tmp in n.temps:
                return n
        n = InterferenceGraphNode(self, tmp)
        self.addNode(n)
        return n

    def Combine(self, n, m):
        """ Combine n and m into n """
        n.temps.extend(m.temps)
        n.moves.update(m.moves)
        for t in m.Adjecent:
            self.addEdge(n, t)
        self.delNode(m)