""" cgraph.py: contains the ConflictGraph data structure, used during
code generation. """

import util

class ConflictGraph:
    
    """ The Conflict Graph is a data structure used during code
    generation.  It maintains a list of which Values conflict with each
    other.

    The challenge for the conflict graph is as follows: we are going
    to be doing a liveness analysis for the graph right before code
    generation.  For each Value that turns out to be live, we'll also
    want to know later what over Values were simultaneously live so we
    can avoid assigning them to the same locations.  Technically,
    we're actually only interested in Global Values, which are Values
    that are live in more than one basic block.

    Now, as we do the liveness analysis we'll also be determining the
    set of global values (when a Value exits a block and is live, then
    it is global).  So we need the conflict graph to be able to have
    new members added to it.  It also needs to be able to record which
    members conflict with what other members: unfortunately, it needs
    to be able to quickly determine if members A and B conflict but
    also to quickly obtain a list of all members that conflict with A.
    These two goals are often at ends (the first is well suited to a
    hashtable, the latter to a list).

    The structure that we'll be using is in fact a hodge podge of both
    of them.  First, each value that has been added to the cgraph will
    have stored on it a cgraph identifier.  This identifier is just a
    numeric index.  When we are told that A and B conflict, we will
    look up their indices (idx(A) and idx(B)).  To determine if A and
    B already conflict, we can use whichever index is lower to index
    into a sequence of bit sets.  For the purposes of exposition, say
    that idx(B) > idx(A).

    In that case, the list self.conflicts will contain at index idx(A)
    a util.BitSet object.  That object will contain the value (idx(B)
    - idx(A)) if the two are already recorded as conflicting.  If they
    are not, the value will be added and A will be added to a list of
    conflicting objects maintained for B, and vice versa.

    As written, any object can be used with the cgraph.  When you create
    one you simply provide two lambdas, one that gets and one that sets an
    attribute named cgraph_index.

    In the current compiler this is implemented for Value objects as updating
    a field of the instance, but in the case of low level Operands it uses
    a hashtable lookup so as to avoid modifying the Operand objects.
    
    """

    def __init__ (self, getidx, setidx, log, prefix):
        
        """ Debug messages will come out on log, prefixed by 'prefix',
        at level low """
        
        self.item_data = []
        self.log = log
        self.prefix = prefix
        self.getidx = getidx
        self.setidx = setidx
        pass

    def _index (self, item):

        """ Internal: returns the index associated with a particular
        item, adding it if necessary.  """

        idx = self.getidx (item)
        if idx is not None: return idx

        idx = len (self.item_data)
        self.setidx (item, idx)
        self.item_data.append ( (util.BitSet(), []) )

        if self.log:
            self.log.low ('%snew index:%d item:%s', self.prefix, idx, item)
            pass

        return idx

    def make_conflict (self, a, b):
        
        """ Ensures that 'a' and 'b' conflict with each other.  No effect if
        they already do.  Returns true if this is a new conflict. """
        
        if a is b: return False
        aidx = self._index (a)
        bidx = self._index (b)
        if aidx >= bidx: return self._make_conflict (bidx, b, aidx, a)
        return self._make_conflict (aidx, a, bidx, b)

    def _make_conflict (self, minidx, min, maxidx, max):

        """ Internal: Helper for self.make_conflict().  min must have
        a lower index (minidx) than max (maxidx). """
        
        bitset = self.item_data [ minidx ] [0]
        diff = maxidx - minidx
        if diff not in bitset:
            bitset.append (diff)
            assert diff in bitset
            self.item_data[minidx][1].append (max)
            self.item_data[maxidx][1].append (min)
            if self.log:
                self.log.low ('%snew entry: diff:%x minidx:%x min:%s maxidx:%x max:%s',
                              self.prefix, diff, minidx, min, maxidx, max)
            return True
        elif self.log:
            self.log.low ('%salready conflicts: diff:%x minidx:%x min:%s maxidx:%x max:%s',
                          self.prefix, diff, minidx, min, maxidx, max)
            pass
        return False

    def conflicting_items (self, a):
        
        """ Returns the set of items that conflict with 'a'. """

        aidx = self._index (a)
        return self.item_data[aidx][1]

    pass