import graph


class InterferenceGraphNode(graph.Node):
    def __init__(self, g, varname):
        super().__init__(g)
        self.varname = varname

    def __repr__(self):
        return '{}'.format(self.varname)


class InterferenceGraph(graph.Graph):
    """
        Interference graph.
    """
    def __init__(self, flowgraph):
        """ 
            Create a new interference graph from a flowgraph 
        """
        super().__init__(False)
        # Mapping from node to live set
        self.liveMap = {}
        self.tempMap = {}
        # 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):
        if tmp not in self.tempMap:
            self.tempMap[tmp] = self.newNode(tmp)
        return self.tempMap[tmp]

    def newNode(self, varname):
        n = InterferenceGraphNode(self, varname)
        self.addNode(n)
        return n

    def combine(self, n, m):
        self.nodes.remove(m)
        n.varnames.extend(m.varnames)