import instrs
from util import PyntoException

class BasicBlock:

    """ A Basic Block is defined in every compiler textbook. Ours is
    no different.  It contains a list of instructions and links to
    other basic blocks.  All control flow other than straight-forward
    fall through is encoded in basic blocks.

    In addition, the basic block has a few pieces of miscellaneous data
    that are used in other passes:

    1. It has a visit tag.  In conjunction with
    Compiler.get_visit_tag(), this allows programs to quickly
    ascertain if they have visited a block in a depth first search or
    something similar.  """

    def __init__ (self):
        self.instrs = []   # list of instructions
        self.succs = []    # list of blocks
        self.preds = []    # list of (block, idx) pairs
        self.visit_tag = None
        return

    # Visit Tags
    # ----------

    def visit (self, tag):
        self.visit_tag = tag
        return

    def visited (self, tag):
        return self.visit_tag is tag

    # Instruction List
    # ----------------

    def last_instr (self):
        return self.instrs[-1]

    def add_instr (self, instr):
        assert self.get_num_successors() == 1
        assert not self.succs
        self.instrs.append (instr)
        instr.set_block (self)
        return
    
    def get_instrs (self):
        return self.instrs

    def has_phis (self):
        """ Returns True if this block has any Phi instructions in the
        beginning of it. """
        return self.instrs and \
               isinstance (self.instrs[0], instrs.PhiInstruction)
        
    # Control Flow
    # ------------

    def set_successor (self, idx, block):

        """ Sets successor #idx to be block.  If this was already set to
        a different block, clears that setting and returns the index that
        we used to occupy in that block's pred list. """

        retval = None
        assert idx < self.get_num_successors()

        # if we don't have enough entry in our list yet, pad it with Nones
        while len (self.succs) <= idx: self.succs.append (None)

        # now, if we were already connected, remove ourselves from the
        # list of preds.  Otherwise, connect and add ourselves to the
        # list of preds.
        oldsblk = self.succs[idx]
        if oldsblk:
            retval = oldsblk.preds.index ((self,idx))
            del oldsblk.preds[retval]
            pass
        self.succs[idx] = block
        if block: block.preds.append ( (self, idx) )
        return retval

    def shortcircuit (self, idx):

        """ Used when the last instruction of the block is changed
        from one with many branches to one w/o branches.  Takes
        successor #idx from the old list of successors (from before
        last instruction changed) and uses it as the only successor in
        the new list. """
        
        assert self.get_num_successors () == 1
        succ = self.succs[idx]
        self.succs = [ succ ]
        return

    def get_predecessors (self):

        """ Returns a list of (block, idx) pairs of blocks that point at us """
        
        return self.preds

    def strip_predecessors (self, indices):

        """ Removes the set of specified predecessors from the list of
        preds for this block; the list should be given in the form of
        a list of indices sorted in ascending order. """
        
        newpreds = []
        lastidx = 0
        for idx in indices:
            newpreds += self.preds[lastidx:idx]
            lastidx = idx
            pass
        self.preds = newpreds
        return

    def get_successors (self):
        return self.succs

    def get_num_successors (self):
        if not self.instrs: return 1
        return self.last_instr().get_successors()

    def terminate (self):

        """ Normally a basic block is used until we get to an
        instruction which branches; however, if the next instruction
        is a jump target, we have to terminate the current basic block
        and begin a new one, since all branching must target a basic
        block.  This routine creates a successor basic block and
        returns it; however, if the current block is empty it just
        returns self.

        It always attaches to instrs.Instruction.FALLTHROUGH, so it can
        be used with branch instructions to. """
        
        if not self.instrs: return self
        succ = BasicBlock ()
        self.set_successor (instrs.Instruction.FALLTHROUGH, succ)
        return succ

    pass