from typing import List, Set, Tuple
from Lib.Errors import MiniCInternalError
from Lib import RiscV
from Lib.Graphes import DiGraph
from Lib.CFG import BlockInstr
from Lib.Operands import (Offset, Register, DataLocation, S)


def generate_smart_move(dest: DataLocation, src: DataLocation) -> List[BlockInstr]:
    """
    Generate a list of move, store and load instructions, depending if the
    operands are registers or memory locations.
    This is an helper function for `sequentialize_moves`.
    """
    instr: List[BlockInstr] = []
    tmp: Register = S[1]
    if(isinstance(dest,Offset) and isinstance(src,Offset)):
        # We read the source in tmp and write it to destination
        instr.append(RiscV.ld(tmp,src))
        instr.append(RiscV.sd(tmp,dest))
    elif(isinstance(dest,Offset) and isinstance(src,Register)):
        # We write the register to destination
        instr.append(RiscV.sd(src,dest))
    elif(isinstance(dest,Register) and isinstance(src,Offset)):
        # We read the source into the register
        instr.append(RiscV.ld(dest,src))
    elif(isinstance(dest,Register) and isinstance(src,Register)):
        # Classic move
        instr.append(RiscV.mv(dest,src))
    else:
        raise MiniCInternalError("Cannot generate smart move from parameters that are no Offset or Register:",src,dest)
    return instr


def sequentialize_moves(parallel_moves: Set[Tuple[DataLocation, DataLocation]]
                        ) -> List[BlockInstr]:
    """
    Take a set of parallel moves represented as (destination, source) pairs,
    and return a list of sequential moves which respect the cycles.
    Use the register `tmp` S2 for the cycles.
    Return a corresponding list of RiscV instructions.
    This is an helper function called during SSA exit.
    """
    tmp: Register = S[2]  # S2 is not a general purpose register
    # Build the graph of the moves
    move_graph: DiGraph = DiGraph()
    for dest, src in parallel_moves:
        move_graph.add_edge((src, dest))
    # List for the sequentialized moves to do
    # Convention: in moves we put (dest, src) for each move
    moves: List[Tuple[DataLocation, DataLocation]] = []
    # First iteratively remove all the vetices without successors
    vars_without_successor = {src
                              for src, dests in move_graph.neighbourhoods()
                              if len(dests) == 0}
    while vars_without_successor:
        head = vars_without_successor.pop()
        while(head is not None):
            preds = move_graph.pred(head)
            if(len(preds)==0):
                head = None
            else:
                pred = preds.pop()
                moves.append((head,pred))
                move_graph.delete_vertex(head)
                head = pred
    
    # Then handle the cycles
    cycles: List = move_graph.connected_components()
    for cycle in cycles:
        if(len(cycle)==1):
            # No moves to do
            pass
        else:
            head = cycle[0]
            moves.append((tmp,head))
            while True:
                pred = move_graph.pred(head).pop()
                if(pred==cycle[0]):
                    break
                moves.append((head,pred))
                head = pred
            moves.append((head,tmp))
    # Transform the moves to do in actual RiscV instructions
    moves_instr: List[BlockInstr] = []
    for dest, src in moves:
        instrs = generate_smart_move(dest, src)
        moves_instr.extend(instrs)
    return moves_instr