///|
priv struct SavedRegister {
  reg : @vcode.PhysicalReg
  offset : Int
}

///|
priv struct StackObjectArea {
  offset : Int
  size : Int
  alignment : Int
}

///|
priv struct StackObjectRequirements {
  size : Int
  alignment : Int
  offsets : Array[Int]
}

///|
priv struct ResultArea {
  offset : Int
  size : Int
}

///|
priv struct TailCallFramePlan {
  stack_argument_size : Int
  stack_argument_base : Int
  synthetic_return_size : Int
  alignment_padding : Int
  transfer_size : Int
  thunk_cleanup_size : Int
}

///|
pub struct X64Frame {
  priv layout : @vcode.FrameLayout
  priv has_setup_area : Bool
  priv local_size : Int
  priv incoming_args_size : Int
  priv tail_args_size : Int
  priv outgoing_args_size : Int
  priv result_area : ResultArea?
  priv stack_objects : StackObjectArea?
  priv stack_object_offsets : Array[Int]
  priv emergency_move_offset : Int?
  priv requires_emergency_moves : Bool
  priv allocation_edit_count : Int
  priv slots : Array[(@vcode.StackSlot, Int)]
  priv saved_registers : Array[SavedRegister]
}

///|
pub suberror X64FrameError {
  InvalidAllocation(cause~ : X64AllocationError)
  InvalidGenericFrame(cause~ : @vcode.FrameVerifyError)
  InvalidSavedRegister(reg~ : @vcode.PhysicalReg, offset~ : Int)
  InvalidStackSlot(slot~ : @vcode.StackSlot)
  OutgoingAreaMismatch(expected~ : Int, actual~ : Int)
  ResultAreaMismatch(expected~ : Int, actual~ : Int)
  TailAreaMismatch(
    expected_incoming~ : Int,
    actual_incoming~ : Int,
    expected_tail~ : Int,
    actual_tail~ : Int
  )
  InvalidStackObjectArea(message~ : String)
  MovePlanningFailed(cause~ : @vcode.MoveResolveError)
  InvalidEmergencyMoveArea(offset~ : Int?)
  StaleAllocation(expected_edits~ : Int, actual_edits~ : Int)
  SavedRegisterSetMismatch
} derive(Debug)

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

///|
fn is_callee_saved(reg : @vcode.PhysicalReg) -> Bool {
  match reg.class {
    Int => reg.id == 3 || (reg.id >= 12 && reg.id <= 15)
    Float | Vector | FpVector => false
  }
}

///|
fn register_save_size(reg : @vcode.PhysicalReg) -> Int {
  ignore(reg)
  8
}

///|
fn used_callee_saved_registers(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
) -> Array[@vcode.PhysicalReg] {
  let regs : Array[@vcode.PhysicalReg] = []
  fn record(
    regs : Array[@vcode.PhysicalReg],
    reg : @vcode.PhysicalReg,
  ) -> Unit {
    if is_callee_saved(reg) && !regs.contains(reg) {
      regs.push(reg)
    }
  }
  for index in 0.. record(regs, reg)
      Move(from~, to~, ..) => {
        record(regs, from)
        record(regs, to)
      }
      EdgeMove(from~, to~, ..) => {
        if from is Register(reg) {
          record(regs, reg)
        }
        if to is Register(reg) {
          record(regs, reg)
        }
      }
    }
  }
  regs.sort_by(fn(left, right) {
    let class_order = match (left.class, right.class) {
      (Int, FpVector) => -1
      (FpVector, Int) => 1
      _ => 0
    }
    if class_order != 0 {
      class_order
    } else {
      left.id.compare(right.id)
    }
  })
  regs
}

///|
fn maximum_outgoing_args_size(function : @vcode.Function[X64Inst]) -> Int {
  let mut maximum = 0
  for index in 0.. maximum {
        maximum = size
      }
    } else if function.instruction(instruction)
      is Some(InternalCall(_, _, plan)) &&
      plan.stack_size > maximum {
      maximum = plan.stack_size
    } else if function.instruction(instruction)
      is Some(InternalCallIndirect(_, plan)) &&
      plan.stack_size > maximum {
      maximum = plan.stack_size
    }
  }
  maximum
}

///|
fn function_has_calls(function : @vcode.Function[X64Inst]) -> Bool {
  for index in 0.. Int {
  let mut maximum = incoming_stack_capacity(function)
  for index in 0..
        plan.stack_size
      _ => 0
    }
    if size > maximum {
      maximum = size
    }
  }
  maximum
}

///|
fn maximum_result_area_size(function : @vcode.Function[X64Inst]) -> Int {
  let mut maximum = 0
  for index in 0..
        plan.result_area_size
      _ => 0
    }
    if size > maximum {
      maximum = size
    }
  }
  maximum
}

///|
fn stack_object_area_requirements(
  function : @vcode.Function[X64Inst],
) -> StackObjectRequirements? raise X64FrameError {
  let objects : Array[X64StackObject?] = []
  for index in 0..
          raise InvalidStackObjectArea(
            message="stack-object id has conflicting size or alignment",
          )
        None => objects[object.id] = Some(object)
        _ => ()
      }
    }
  }
  if objects.is_empty() {
    return None
  }
  let offsets : Array[Int] = []
  let mut cursor = 0
  let mut area_alignment = 1
  for object in objects {
    guard object is Some(object) else {
      raise InvalidStackObjectArea(
        message="stack-object ids must be dense within one function",
      )
    }
    cursor = align_up(cursor, object.alignment)
    offsets.push(cursor)
    cursor += object.size
    if object.alignment > area_alignment {
      area_alignment = object.alignment
    }
  }
  Some({
    size: align_up(cursor, area_alignment),
    alignment: area_alignment,
    offsets,
  })
}

///|
fn moves_require_emergency(
  moves : Array[@vcode.ParallelMove],
) -> Bool raise X64FrameError {
  @vcode.plan_parallel_moves(
    moves,
    int_transfer_scratch(),
    fp_transfer_scratch(),
  ).requires_emergency catch {
    error => raise MovePlanningFailed(cause=error)
  }
}

///|
fn instruction_edits_require_emergency(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
  instruction : @vcode.Instruction,
  placement : @vcode.PointPlacement,
) -> Bool raise X64FrameError {
  if allocation.edits_at(instruction, placement).is_empty() {
    return false
  }
  moves_require_emergency(
    edit_parallel_moves(function, allocation, instruction, placement),
  )
}

///|
fn edge_edits_require_emergency(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
  block : @vcode.Block,
  successor_index : Int,
) -> Bool raise X64FrameError {
  if allocation.edge_edits_at(block, successor_index).is_empty() {
    return false
  }
  moves_require_emergency(
    edge_parallel_moves(function, allocation, block, successor_index),
  )
}

///|
fn requires_emergency_move_area(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
) -> Bool raise X64FrameError {
  for block in function.layout() {
    for instruction in function.block_body(block) {
      if !is_abi_materialization(function.instruction(instruction).unwrap()) {
        if instruction_edits_require_emergency(
            function,
            allocation,
            instruction,
            Before,
          ) ||
          instruction_edits_require_emergency(
            function,
            allocation,
            instruction,
            After,
          ) {
          return true
        }
      }
    }
    let terminator = function.block_terminator(block).unwrap()
    if instruction_edits_require_emergency(
        function,
        allocation,
        terminator,
        Before,
      ) ||
      instruction_edits_require_emergency(
        function,
        allocation,
        terminator,
        After,
      ) {
      return true
    }
    for successor_index in 0.. Int {
  if self.has_setup_area {
    self.layout.frame_size() + 8
  } else {
    self.layout.frame_size()
  }
}

///|
fn X64Frame::allocation_size(self : X64Frame) -> Int {
  self.layout.frame_size()
}

///|
fn X64Frame::has_setup_area(self : X64Frame) -> Bool {
  self.has_setup_area
}

///|
pub fn X64Frame::incoming_args_size(self : X64Frame) -> Int {
  self.incoming_args_size
}

///|
pub fn X64Frame::tail_args_size(self : X64Frame) -> Int {
  self.tail_args_size
}

///|
fn X64Frame::tail_call_plan(
  self : X64Frame,
  callee_args_size : Int,
) -> TailCallFramePlan {
  if callee_args_size <= self.incoming_args_size {
    {
      stack_argument_size: callee_args_size,
      stack_argument_base: self.frame_size() + 8,
      synthetic_return_size: 0,
      alignment_padding: 0,
      transfer_size: 0,
      thunk_cleanup_size: 0,
    }
  } else {
    let synthetic_return_size = 8
    let transfer_size = align_up(synthetic_return_size + callee_args_size, 16)
    let alignment_padding = transfer_size -
      synthetic_return_size -
      callee_args_size
    {
      stack_argument_size: callee_args_size,
      stack_argument_base: self.frame_size() +
      synthetic_return_size -
      transfer_size,
      synthetic_return_size,
      alignment_padding,
      transfer_size,
      thunk_cleanup_size: transfer_size - synthetic_return_size,
    }
  }
}

///|
fn X64Frame::valid_tail_call_plan(
  self : X64Frame,
  plan : TailCallFramePlan,
) -> Bool {
  if plan.stack_argument_size <= self.incoming_args_size {
    return plan.stack_argument_base == self.frame_size() + 8 &&
      plan.synthetic_return_size == 0 &&
      plan.alignment_padding == 0 &&
      plan.transfer_size == 0 &&
      plan.thunk_cleanup_size == 0
  }
  plan.stack_argument_size % 16 == 0 &&
  plan.synthetic_return_size == 8 &&
  plan.alignment_padding >= 0 &&
  plan.synthetic_return_size + plan.stack_argument_size + plan.alignment_padding ==
  plan.transfer_size &&
  plan.transfer_size % 16 == 0 &&
  plan.stack_argument_base ==
  self.frame_size() + plan.synthetic_return_size - plan.transfer_size &&
  plan.thunk_cleanup_size + plan.synthetic_return_size == plan.transfer_size
}

///|
fn tail_argument_staging_size(
  incoming_args_size : Int,
  tail_args_size : Int,
) -> Int {
  if tail_args_size > incoming_args_size {
    tail_args_size
  } else {
    0
  }
}

///|
pub fn X64Frame::alignment(self : X64Frame) -> Int {
  self.layout.alignment()
}

///|
pub fn X64Frame::outgoing_args_size(self : X64Frame) -> Int {
  self.outgoing_args_size
}

///|
fn X64Frame::result_area_offset(self : X64Frame) -> Int? {
  self.result_area.map(area => area.offset)
}

///|
pub fn X64Frame::emergency_move_offset(self : X64Frame) -> Int? {
  self.emergency_move_offset
}

///|
pub fn X64Frame::stack_object_offset(
  self : X64Frame,
  object : X64StackObject,
) -> Int? {
  match self.stack_objects {
    Some(area) if object.is_valid() &&
      object.id < self.stack_object_offsets.length() =>
      Some(area.offset + self.stack_object_offsets[object.id])
    _ => None
  }
}

///|
pub fn X64Frame::slot_offset(self : X64Frame, slot : @vcode.StackSlot) -> Int? {
  self.layout.slot_offset(slot)
}

///|
pub fn X64Frame::saved_registers(
  self : X64Frame,
) -> Array[(@vcode.PhysicalReg, Int)] {
  self.saved_registers.map(saved => (saved.reg, saved.offset))
}

///|
pub fn X64Frame::summary(self : X64Frame) -> String {
  let mut output = "x64 frame size=\{self.frame_size()} align=\{self.alignment()}\n"
  if self.tail_args_size > self.incoming_args_size {
    let plan = self.tail_call_plan(self.tail_args_size)
    output += "  tail-args \{plan.stack_argument_size} bytes at sp+\{plan.stack_argument_base}\n"
    output += "  tail-transfer return=\{plan.synthetic_return_size} padding=\{plan.alignment_padding} adjust=\{plan.transfer_size} cleanup=\{plan.thunk_cleanup_size}\n"
  }
  if self.outgoing_args_size > 0 {
    output += "  outgoing \{self.outgoing_args_size} bytes at sp+0\n"
  }
  if self.result_area is Some(area) {
    output += "  call-results \{area.size} bytes at sp+\{area.offset}\n"
  }
  if self.stack_objects is Some(area) {
    output += "  stack-objects \{area.size} bytes at sp+\{area.offset}\n"
  }
  if self.emergency_move_offset is Some(offset) {
    output += "  emergency-move 16 bytes at sp+\{offset}\n"
  }
  for entry in self.slots {
    let (slot, offset) = entry
    output += "  place \{Repr(slot)} at sp+\{offset}\n"
  }
  for saved in self.saved_registers {
    output += "  save \{Repr(saved.reg)} at sp+\{saved.offset}\n"
  }
  output
}

///|
pub fn verify_frame(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
  frame : X64Frame,
) -> Unit raise X64FrameError {
  verify_allocation(function, allocation) catch {
    error => raise InvalidAllocation(cause=error)
  }
  @vcode.verify_framed(function, allocation, frame.layout) catch {
    error => raise InvalidGenericFrame(cause=error)
  }
  verify_target_frame(function, allocation, frame)
}

///|
fn verify_target_frame(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
  frame : X64Frame,
) -> Unit raise X64FrameError {
  let actual_edit_count = allocation.edit_count()
  if frame.allocation_edit_count != actual_edit_count {
    raise StaleAllocation(
      expected_edits=frame.allocation_edit_count,
      actual_edits=actual_edit_count,
    )
  }
  let expected_outgoing = maximum_outgoing_args_size(function)
  if frame.outgoing_args_size != expected_outgoing {
    raise OutgoingAreaMismatch(
      expected=expected_outgoing,
      actual=frame.outgoing_args_size,
    )
  }
  let expected_incoming = incoming_stack_capacity(function)
  let expected_tail = if function.protocol() == Internal {
    maximum_tail_args_size(function)
  } else {
    expected_incoming
  }
  let expected_tail_area = tail_argument_staging_size(
    expected_incoming, expected_tail,
  )
  if frame.incoming_args_size != expected_incoming ||
    frame.tail_args_size != expected_tail ||
    frame.local_size + expected_tail_area != frame.allocation_size() {
    raise TailAreaMismatch(
      expected_incoming~,
      actual_incoming=frame.incoming_args_size,
      expected_tail~,
      actual_tail=frame.tail_args_size,
    )
  }
  for index in 0..
        Some(plan.stack_size)
      _ => None
    }
    if stack_arguments is Some(size) &&
      !frame.valid_tail_call_plan(frame.tail_call_plan(size)) {
      raise TailAreaMismatch(
        expected_incoming~,
        actual_incoming=frame.incoming_args_size,
        expected_tail=size,
        actual_tail=frame.tail_args_size,
      )
    }
  }
  let expected_result_area = maximum_result_area_size(function)
  let actual_result_area = frame.result_area.map(area => area.size).unwrap_or(0)
  if actual_result_area != expected_result_area {
    raise ResultAreaMismatch(
      expected=expected_result_area,
      actual=actual_result_area,
    )
  }
  if frame.result_area is Some(area) &&
    (
      area.offset < frame.outgoing_args_size ||
      area.offset % 16 != 0 ||
      area.offset + area.size > frame.local_size
    ) {
    raise ResultAreaMismatch(expected=expected_result_area, actual=area.size)
  }
  let expected_stack_objects = stack_object_area_requirements(function)
  let reserved_call_area_end = match frame.result_area {
    Some(area) => area.offset + area.size
    None => frame.outgoing_args_size
  }
  match (expected_stack_objects, frame.stack_objects) {
    (None, None) => ()
    (Some(requirements), Some(area)) =>
      if area.size != requirements.size ||
        area.alignment != requirements.alignment ||
        area.offset < reserved_call_area_end ||
        area.offset % requirements.alignment != 0 ||
        area.offset + requirements.size > frame.local_size ||
        frame.stack_object_offsets != requirements.offsets {
        raise InvalidStackObjectArea(
          message="planned stack-object area does not satisfy target requirements",
        )
      }
    _ =>
      raise InvalidStackObjectArea(
        message="planned stack-object area presence does not match target VCode",
      )
  }
  let reserved_object_area_end = match frame.stack_objects {
    Some(area) => area.offset + area.size
    None => reserved_call_area_end
  }
  match (frame.requires_emergency_moves, frame.emergency_move_offset) {
    (false, None) => ()
    (true, Some(offset)) =>
      if offset < reserved_object_area_end ||
        offset % 16 != 0 ||
        offset + 16 > frame.local_size {
        raise InvalidEmergencyMoveArea(offset=Some(offset))
      }
    _ => raise InvalidEmergencyMoveArea(offset=frame.emergency_move_offset)
  }
  let expected = used_callee_saved_registers(function, allocation)
  if frame.saved_registers.map(saved => saved.reg) != expected {
    raise SavedRegisterSetMismatch
  }
  let occupied : Array[(Int, Int)] = []
  if frame.outgoing_args_size > 0 {
    occupied.push((0, frame.outgoing_args_size))
  }
  if frame.result_area is Some(area) {
    occupied.push((area.offset, area.offset + area.size))
  }
  if frame.stack_objects is Some(area) {
    occupied.push((area.offset, area.offset + area.size))
  }
  if frame.emergency_move_offset is Some(offset) {
    occupied.push((offset, offset + 16))
  }
  for index in 0.. frame.local_size {
      raise InvalidStackSlot(slot~)
    }
    occupied.push((offset, offset + allocation.stack_slot_size(slot).unwrap()))
  }
  for saved in frame.saved_registers {
    let size = register_save_size(saved.reg)
    if saved.offset < 0 ||
      saved.offset % size != 0 ||
      saved.offset + size > frame.local_size {
      raise InvalidSavedRegister(reg=saved.reg, offset=saved.offset)
    }
    for range in occupied {
      if saved.offset < range.1 && range.0 < saved.offset + size {
        raise InvalidSavedRegister(reg=saved.reg, offset=saved.offset)
      }
    }
    occupied.push((saved.offset, saved.offset + size))
  }
}

///|
fn plan_frame_verified(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
) -> X64Frame raise X64FrameError {
  let outgoing_args_size = maximum_outgoing_args_size(function)
  let mut offset = outgoing_args_size
  let result_area_size = maximum_result_area_size(function)
  let result_area = if result_area_size > 0 {
    offset = align_up(offset, 16)
    let area = { offset, size: result_area_size, }
    offset += result_area_size
    Some(area)
  } else {
    None
  }
  let stack_object_requirements = stack_object_area_requirements(function)
  let stack_objects = match stack_object_requirements {
    Some(requirements) => {
      offset = align_up(offset, requirements.alignment)
      let area = {
        offset,
        size: requirements.size,
        alignment: requirements.alignment,
      }
      offset += requirements.size
      Some(area)
    }
    None => None
  }
  let requires_emergency_moves = requires_emergency_move_area(
    function, allocation,
  )
  let emergency_move_offset = if requires_emergency_moves {
    offset = align_up(offset, 16)
    let emergency_offset = offset
    offset += 16
    Some(emergency_offset)
  } else {
    None
  }
  let slot_offsets : Array[Int] = []
  for index in 0.. ignore
  }
  let slots = Array::makei(slot_offsets.length(), index => {
    (allocation.stack_slot_at(index).unwrap(), slot_offsets[index])
  })
  let frame = {
    layout,
    has_setup_area: allocation_size > 0 || function_has_calls(function),
    local_size,
    incoming_args_size,
    tail_args_size,
    outgoing_args_size,
    result_area,
    stack_objects,
    stack_object_offsets: match stack_object_requirements {
      Some(requirements) => requirements.offsets
      None => []
    },
    emergency_move_offset,
    requires_emergency_moves,
    allocation_edit_count: allocation.edit_count(),
    slots,
    saved_registers,
  }
  verify_target_frame(function, allocation, frame)
  frame
}

///|
pub fn plan_frame(
  function : @vcode.Function[X64Inst],
  allocation : @vcode.Allocation,
) -> X64Frame raise X64FrameError {
  verify_allocation(function, allocation) catch {
    error => raise InvalidAllocation(cause=error)
  }
  plan_frame_verified(function, allocation)
}