///|
#derive(Eq, Debug)
pub struct ParallelMove {
  ty : ValueType
  from : Location
  to : Location
}

///|
pub fn ParallelMove::new(
  ty : ValueType,
  from : Location,
  to : Location,
) -> ParallelMove {
  { ty, from, to, }
}

///|
#derive(Eq, Debug)
pub(all) enum ResolvedMoveStep {
  Transfer(ParallelMove)
  SpillScratchToEmergency(ty~ : ValueType, scratch~ : PhysicalReg)
  ReloadScratchFromEmergency(ty~ : ValueType, scratch~ : PhysicalReg)
}

///|
#derive(Eq, Debug)
pub struct ResolvedMovePlan {
  steps : Array[ResolvedMoveStep]
  requires_emergency : Bool
}

///|
pub fn ResolvedMovePlan::empty() -> ResolvedMovePlan {
  { steps: [], requires_emergency: false, }
}

///|
#derive(Eq, Debug)
pub suberror MoveResolveError {
  MissingScratch(class~ : RegClass)
  InvalidScratch(reg~ : PhysicalReg, expected~ : RegClass)
  NoSafeCycleScratch(class~ : RegClass)
  BrokenCycle
}

///|
pub impl Show for MoveResolveError with fn output(self, logger) {
  logger.write_string(Repr(self).to_string())
}

///|
fn move_bank(ty : ValueType) -> RegClass {
  reg_class_for_value_type(ty)
}

///|
fn source_locations(moves : Array[ParallelMove]) -> Array[Location] {
  let sources : Array[Location] = []
  for transfer in moves {
    if !sources.contains(transfer.from) {
      sources.push(transfer.from)
    }
  }
  sources
}

///|
fn linearize_single_bank(
  moves : Array[ParallelMove],
  scratch : PhysicalReg,
) -> Array[ParallelMove] raise MoveResolveError {
  let pending : Array[ParallelMove] = []
  let scratch_location : Location = Register(scratch)
  for transfer in moves {
    if transfer.from != transfer.to && !pending.contains(transfer) {
      if move_bank(transfer.ty) != scratch.class {
        raise InvalidScratch(reg=scratch, expected=move_bank(transfer.ty))
      }
      if transfer.from == scratch_location || transfer.to == scratch_location {
        raise NoSafeCycleScratch(class=scratch.class)
      }
      pending.push(transfer)
    }
  }
  let result : Array[ParallelMove] = []
  while !pending.is_empty() {
    let sources = source_locations(pending)
    let mut ready : Int32? = None
    for index, transfer in pending {
      if !sources.contains(transfer.to) {
        ready = Some(index)
        break
      }
    }
    match ready {
      Some(index) => result.push(pending.remove(index))
      None => {
        let transfer = pending.remove(0)
        let mut saved_type : ValueType? = None
        for pending_move in pending {
          if pending_move.from == transfer.to {
            saved_type = Some(pending_move.ty)
            break
          }
        }
        guard saved_type is Some(saved_type) else { raise BrokenCycle }
        result.push(
          ParallelMove::new(saved_type, transfer.to, scratch_location),
        )
        for index in 0.. ResolvedMovePlan {
  let steps : Array[ResolvedMoveStep] = []
  let scratch_location : Location = Register(scratch)
  let mut live_cycle_type : ValueType? = None
  let mut requires_emergency = false
  for transfer in moves {
    if transfer.from is Stack(_) && transfer.to is Stack(_) {
      match live_cycle_type {
        Some(ty) => {
          steps.push(SpillScratchToEmergency(ty~, scratch~))
          requires_emergency = true
        }
        None => ()
      }
      steps.push(
        Transfer(
          ParallelMove::new(transfer.ty, transfer.from, scratch_location),
        ),
      )
      steps.push(
        Transfer(ParallelMove::new(transfer.ty, scratch_location, transfer.to)),
      )
      match live_cycle_type {
        Some(ty) => steps.push(ReloadScratchFromEmergency(ty~, scratch~))
        None => ()
      }
    } else {
      steps.push(Transfer(transfer))
      if transfer.to == scratch_location {
        live_cycle_type = Some(transfer.ty)
      } else if transfer.from == scratch_location {
        live_cycle_type = None
      }
    }
  }
  { steps, requires_emergency, }
}

///|
pub fn plan_parallel_moves(
  moves : Array[ParallelMove],
  scratch_int : PhysicalReg,
  scratch_fp : PhysicalReg,
) -> ResolvedMovePlan raise MoveResolveError {
  if scratch_int.class != Int {
    raise InvalidScratch(reg=scratch_int, expected=Int)
  }
  if scratch_fp.class != FpVector {
    raise InvalidScratch(reg=scratch_fp, expected=FpVector)
  }
  if moves.is_empty() {
    return ResolvedMovePlan::empty()
  }
  let int_moves : Array[ParallelMove] = []
  let fp_moves : Array[ParallelMove] = []
  for transfer in moves {
    if move_bank(transfer.ty) == Int {
      int_moves.push(transfer)
    } else {
      fp_moves.push(transfer)
    }
  }
  let int_plan = legalize_single_bank(
    linearize_single_bank(int_moves, scratch_int),
    scratch_int,
  )
  let fp_plan = legalize_single_bank(
    linearize_single_bank(fp_moves, scratch_fp),
    scratch_fp,
  )
  for step in fp_plan.steps {
    int_plan.steps.push(step)
  }
  {
    steps: int_plan.steps,
    requires_emergency: int_plan.requires_emergency ||
    fp_plan.requires_emergency,
  }
}