// Licensing scope: see ../../LICENSE and this directory's LICENSE and NOTICE.
// Copyright 2023 WebAssembly Community Group participants.
// Retained historical upstream notice; current derivation remains unconfirmed.
// Conservative attribution from pinned Binaryen version_130 counterpart:
// Copyright 2015 WebAssembly Community Group participants
// Counterpart: src/passes/RemoveUnusedNames.cpp (5d704ad5); origin remains unconfirmed.
// Potentially incorporated Binaryen expression retains Apache-2.0 terms.
// Original Starshine contributions use the scoped MIT grant in ../../LICENSE.
// Modified for Starshine through 2026: implementation and validation use
// Starshine's representations and APIs; this is not an unchanged upstream file.
// Conservative notice retention does not establish copying or independence.

///|
pub fn remove_unused_names_descriptor() -> @ir.HotPassDescriptor {
  @ir.HotPassDescriptor::new("remove-unused-names", invalidates=[
    @ir.HotAnalysis::cfg(),
    @ir.HotAnalysis::dominance(),
    @ir.HotAnalysis::liveness(),
    @ir.HotAnalysis::use_def(),
    @ir.HotAnalysis::effects(),
    @ir.HotAnalysis::loop_info(),
    @ir.HotAnalysis::ssa(),
  ])
}

///|
pub fn remove_unused_names_summary() -> String {
  "Peel redundant same-typed block wrappers and demote loops whose labels have no remaining continue targets."
}

///|
fn remove_unused_names_control_block_type_for_ty(
  func : @ir.HotFunc,
  ty : Int32,
) -> @lib.BlockType {
  match @ir.hot_type_get(func, ty) {
    @ir.HotTypeInfo::BlockResult(block_type) => block_type
    @ir.HotTypeInfo::BlockResultResolved(block_type, _, _) => block_type
    _ => @lib.BlockType::void_()
  }
}

///|
fn remove_unused_names_loop_label_has_entry_params(
  func : @ir.HotFunc,
  node_id : Int32,
) -> Bool {
  let label_id = @ir.hot_control_node_label(func, node_id)
  if label_id < 0 {
    return false
  }
  let label = @ir.hot_label_get(func, label_id)
  if label.branch_arity > 0 {
    return true
  }
  match @ir.hot_type_get(func, label.result_type) {
    @ir.HotTypeInfo::BlockResultResolved(_, params, _) => !params.is_empty()
    @ir.HotTypeInfo::BlockResult(@lib.TypeIdxBlockType(_)) => true
    _ => false
  }
}

///|
fn remove_unused_names_label_in_controls(
  func : @ir.HotFunc,
  label_id : Int32,
  control_ids : Array[Int32],
) -> Bool {
  for control_id in control_ids {
    if @ir.hot_control_node_label(func, control_id) == label_id {
      return true
    }
  }
  false
}

///|
fn remove_unused_names_node_targets_any_control(
  func : @ir.HotFunc,
  node : @ir.HotNode,
  control_ids : Array[Int32],
) -> Bool {
  let targets_label = fn(label_id : Int32) {
    remove_unused_names_label_in_controls(func, label_id, control_ids)
  }
  match node.op {
    @ir.HotOp::Br
    | @ir.HotOp::BrIf
    | @ir.HotOp::BrOnNull
    | @ir.HotOp::BrOnNonNull
    | @ir.HotOp::BrOnCast
    | @ir.HotOp::BrOnCastFail
    | @ir.HotOp::Delegate => targets_label(node.imm0)
    @ir.HotOp::BrTable => {
      if targets_label(@ir.hot_branch_table_default_target(func, node.imm0)) {
        return true
      }
      for label_id in @ir.hot_branch_table_targets(func, node.imm0) {
        if targets_label(label_id) {
          return true
        }
      }
      false
    }
    @ir.HotOp::Continuation => {
      for label in @ir.hot_branch_table_targets(func, node.imm1) {
        if targets_label(label) {
          return true
        }
      }
      false
    }
    @ir.HotOp::TryTable => {
      let info = @ir.hot_catch_info_get(func, node.imm1)
      for catch_ in info.catches {
        let label_id = match catch_ {
          @ir.HotCatchArm::CatchArm(_, label_id)
          | @ir.HotCatchArm::CatchRefArm(_, label_id)
          | @ir.HotCatchArm::CatchAllArm(label_id)
          | @ir.HotCatchArm::CatchAllRefArm(label_id) => label_id
        }
        if targets_label(label_id) {
          return true
        }
      }
      false
    }
    _ => false
  }
}

///|
fn remove_unused_names_compute_live_label_uses(
  func : @ir.HotFunc,
) -> @bitset.BitSet {
  let used = @bitset.BitSet::new(func.labels.length())
  let seen = @bitset.BitSet::new(@ir.hot_node_count(func))
  let stack : Array[Int32] = []
  for slot = 0; slot < @ir.hot_root_count(func); slot = slot + 1 {
    stack.push(@ir.hot_root_get(func, slot))
  }
  let mark = fn(label_id : Int32) {
    if label_id >= 0 && label_id < used.length() {
      used[label_id] = true
    }
  }
  while !stack.is_empty() {
    let node_id = stack.pop().unwrap()
    if node_id < 0 ||
      node_id >= seen.length() ||
      seen[node_id] ||
      !@ir.hot_node_is_live(func, node_id) {
      continue
    }
    seen[node_id] = true
    let node = @ir.hot_node_get(func, node_id)
    match node.op {
      @ir.HotOp::Br
      | @ir.HotOp::BrIf
      | @ir.HotOp::BrOnNull
      | @ir.HotOp::BrOnNonNull
      | @ir.HotOp::BrOnCast
      | @ir.HotOp::BrOnCastFail
      | @ir.HotOp::Delegate => mark(node.imm0)
      @ir.HotOp::BrTable => {
        mark(@ir.hot_branch_table_default_target(func, node.imm0))
        for label_id in @ir.hot_branch_table_targets(func, node.imm0) {
          mark(label_id)
        }
      }
      @ir.HotOp::Continuation =>
        for label_id in @ir.hot_continuation_targets(func, node_id) {
          mark(label_id)
        }
      @ir.HotOp::TryTable => {
        let info = @ir.hot_catch_info_get(func, node.imm1)
        for catch_ in info.catches {
          let label_id = match catch_ {
            @ir.HotCatchArm::CatchArm(_, label_id)
            | @ir.HotCatchArm::CatchRefArm(_, label_id)
            | @ir.HotCatchArm::CatchAllArm(label_id)
            | @ir.HotCatchArm::CatchAllRefArm(label_id) => label_id
          }
          mark(label_id)
        }
      }
      _ => ()
    }
    for slot = 0; slot < @ir.hot_child_count(func, node_id); slot = slot + 1 {
      stack.push(@ir.hot_child_get(func, node_id, slot))
    }
  }
  used
}

///|
fn remove_unused_names_peel_same_typed_blocks(
  func : @ir.HotFunc,
  block_id : Int32,
  removed_ids : Array[Int32],
  roots : Array[Int32],
) -> Unit {
  removed_ids.clear()
  let block_ty = @ir.hot_node_get(func, block_id).ty
  let block_type = remove_unused_names_control_block_type_for_ty(func, block_ty)
  let mut region_ref = @ir.hot_region_body_ref(func, block_id)
  while @ir.hot_region_root_count(func, region_ref) == 1 {
    let child_id = @ir.hot_region_get(func, region_ref, 0)
    if child_id < 0 || !@ir.hot_node_is_live(func, child_id) {
      break
    }
    let child = @ir.hot_node_get(func, child_id)
    match child.op {
      @ir.HotOp::Block =>
        if child.ty != block_ty &&
          remove_unused_names_control_block_type_for_ty(func, child.ty) !=
          block_type {
          break
        }
      _ => break
    }
    removed_ids.push(child_id)
    region_ref = @ir.hot_region_body_ref(func, child_id)
  }
  if removed_ids.is_empty() {
    return
  }
  roots.clear()
  let root_count = @ir.hot_region_root_count(func, region_ref)
  for idx = 0; idx < root_count; idx = idx + 1 {
    roots.push(@ir.hot_region_get(func, region_ref, idx))
  }
}

///|
fn remove_unused_names_detach_peeled_blocks(
  func : @ir.HotFunc,
  removed_ids : Array[Int32],
) -> Unit {
  for removed_id in removed_ids {
    @ir.hot_region_replace_body(
      func,
      @ir.hot_region_body_ref(func, removed_id),
      [],
    )
  }
}

///|
fn remove_unused_names_replacement_label_for_controls(
  label_id : Int32,
  removed_labels : @bitset.BitSet,
  replacement_label : Int32,
) -> Int32 {
  if label_id >= 0 &&
    label_id < removed_labels.length() &&
    removed_labels[label_id] {
    replacement_label
  } else {
    label_id
  }
}

///|
fn remove_unused_names_retarget_node_labels(
  func : @ir.HotFunc,
  node_id : Int32,
  removed_labels : @bitset.BitSet,
  replacement_label : Int32,
) -> Bool {
  let node = @ir.hot_node_get(func, node_id)
  match node.op {
    @ir.HotOp::Br
    | @ir.HotOp::BrIf
    | @ir.HotOp::BrOnNull
    | @ir.HotOp::BrOnNonNull
    | @ir.HotOp::BrOnCast
    | @ir.HotOp::BrOnCastFail
    | @ir.HotOp::Delegate => {
      let next_label = remove_unused_names_replacement_label_for_controls(
        node.imm0,
        removed_labels,
        replacement_label,
      )
      if next_label != node.imm0 {
        @ir.hot_branch_target_set(func, node_id, next_label)
        true
      } else {
        false
      }
    }
    @ir.HotOp::BrTable => {
      let old_targets = @ir.hot_branch_table_targets(func, node.imm0)
      let old_default = @ir.hot_branch_table_default_target(func, node.imm0)
      let new_targets : Array[Int32] = []
      let mut changed = false
      for target in old_targets {
        let next_target = remove_unused_names_replacement_label_for_controls(
          target, removed_labels, replacement_label,
        )
        changed = changed || next_target != target
        new_targets.push(next_target)
      }
      let new_default = remove_unused_names_replacement_label_for_controls(
        old_default, removed_labels, replacement_label,
      )
      changed = changed || new_default != old_default
      if changed {
        @ir.hot_branch_table_set(func, node_id, new_targets, new_default)
      }
      changed
    }
    @ir.HotOp::Continuation => {
      let old_targets = @ir.hot_continuation_targets(func, node_id)
      let new_targets = old_targets.map(fn(label) {
        remove_unused_names_replacement_label_for_controls(
          label, removed_labels, replacement_label,
        )
      })
      if new_targets == old_targets {
        return false
      }
      @ir.hot_continuation_targets_set(func, node_id, new_targets)
      true
    }
    @ir.HotOp::TryTable => {
      let info = @ir.hot_catch_info_get(func, node.imm1)
      let new_catches : Array[@ir.HotCatchArm] = []
      let mut changed = false
      for catch_ in info.catches {
        let (old_label, make_catch) = match catch_ {
          @ir.HotCatchArm::CatchArm(tag_idx, label_id) =>
            (
              label_id,
              fn(next_label) { @ir.HotCatchArm::catch_(tag_idx, next_label) },
            )
          @ir.HotCatchArm::CatchRefArm(tag_idx, label_id) =>
            (
              label_id,
              fn(next_label) { @ir.HotCatchArm::catch_ref(tag_idx, next_label) },
            )
          @ir.HotCatchArm::CatchAllArm(label_id) =>
            (label_id, fn(next_label) { @ir.HotCatchArm::all(next_label) })
          @ir.HotCatchArm::CatchAllRefArm(label_id) =>
            (label_id, fn(next_label) { @ir.HotCatchArm::all_ref(next_label) })
        }
        let next_label = remove_unused_names_replacement_label_for_controls(
          old_label, removed_labels, replacement_label,
        )
        changed = changed || next_label != old_label
        new_catches.push(make_catch(next_label))
      }
      if changed {
        @ir.hot_try_table_catches_set(func, node_id, new_catches)
      }
      changed
    }
    _ => false
  }
}

///|
fn remove_unused_names_retarget_subtree_labels(
  func : @ir.HotFunc,
  node_id : Int32,
  removed_labels : @bitset.BitSet,
  replacement_label : Int32,
) -> Bool {
  let stack : Array[Int32] = [node_id]
  let mut changed = false
  while stack.length() > 0 {
    let current = stack.pop().unwrap()
    if current < 0 || !@ir.hot_node_is_live(func, current) {
      continue
    }
    changed = remove_unused_names_retarget_node_labels(
        func, current, removed_labels, replacement_label,
      ) ||
      changed
    for slot = 0; slot < @ir.hot_child_count(func, current); slot = slot + 1 {
      stack.push(@ir.hot_child_get(func, current, slot))
    }
  }
  changed
}

///|
fn remove_unused_names_retarget_region_labels(
  func : @ir.HotFunc,
  region_ref : @ir.HotRegionRef,
  removed_labels : @bitset.BitSet,
  replacement_label : Int32,
) -> Bool {
  let mut changed = false
  let root_count = @ir.hot_region_root_count(func, region_ref)
  for idx = 0; idx < root_count; idx = idx + 1 {
    changed = remove_unused_names_retarget_subtree_labels(
        func,
        @ir.hot_region_get(func, region_ref, idx),
        removed_labels,
        replacement_label,
      ) ||
      changed
  }
  changed
}

///|
fn remove_unused_names_visit_region(
  func : @ir.HotFunc,
  region_ref : @ir.HotRegionRef,
  removed_ids : Array[Int32],
  peeled_roots : Array[Int32],
  used_labels : @bitset.BitSet,
  removed_labels : @bitset.BitSet,
  touched_removed_labels : Array[Int32],
) -> Bool {
  let mut changed = false
  let root_count = @ir.hot_region_root_count(func, region_ref)
  let mut idx = 0
  while idx < root_count {
    let node_id = @ir.hot_region_get(func, region_ref, idx)
    if node_id >= 0 && @ir.hot_node_is_live(func, node_id) {
      let node = @ir.hot_node_get(func, node_id)
      match node.op {
        @ir.HotOp::Block
        | @ir.HotOp::Loop
        | @ir.HotOp::If
        | @ir.HotOp::Try
        | @ir.HotOp::TryTable =>
          changed = remove_unused_names_visit_control_node(
              func, node_id, node, removed_ids, peeled_roots, used_labels, removed_labels,
              touched_removed_labels,
            ) ||
            changed
        _ => ()
      }
    }
    idx = idx + 1
  }
  changed
}

///|
fn remove_unused_names_demote_loop(func : @ir.HotFunc, node_id : Int32) -> Unit {
  @ir.hot_control_demote_loop_to_block(func, node_id)
}

///|
fn remove_unused_names_visit_control_node(
  func : @ir.HotFunc,
  node_id : Int32,
  node : @ir.HotNode,
  removed_ids : Array[Int32],
  peeled_roots : Array[Int32],
  used_labels : @bitset.BitSet,
  removed_labels : @bitset.BitSet,
  touched_removed_labels : Array[Int32],
) -> Bool {
  let mut changed = false
  match node.op {
    @ir.HotOp::Block => {
      remove_unused_names_peel_same_typed_blocks(
        func, node_id, removed_ids, peeled_roots,
      )
      if !removed_ids.is_empty() {
        let replacement_label = @ir.hot_control_node_label(func, node_id)
        let body_ref = @ir.hot_region_body_ref(func, node_id)
        for label_id in touched_removed_labels {
          removed_labels[label_id] = false
        }
        touched_removed_labels.clear()
        for removed_id in removed_ids {
          let label_id = @ir.hot_control_node_label(func, removed_id)
          if label_id >= 0 && label_id < removed_labels.length() {
            if !removed_labels[label_id] {
              removed_labels[label_id] = true
              touched_removed_labels.push(label_id)
            }
          }
        }
        ignore(
          remove_unused_names_retarget_region_labels(
            func, body_ref, removed_labels, replacement_label,
          ),
        )
        @ir.hot_region_replace_body(func, body_ref, peeled_roots)
        remove_unused_names_detach_peeled_blocks(func, removed_ids)
        changed = true
      }
      removed_ids.clear()
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_body_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
    }
    @ir.HotOp::Loop => {
      removed_ids.clear()
      if !remove_unused_names_loop_label_has_entry_params(func, node_id) &&
        !pass_label_is_used(
          @ir.hot_control_node_label(func, node_id),
          used_labels,
        ) {
        remove_unused_names_demote_loop(func, node_id)
        changed = true
      }
      removed_ids.clear()
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_body_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
    }
    @ir.HotOp::If => {
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_then_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
      match @ir.hot_region_else_ref(func, node_id) {
        Some(else_region) =>
          changed = remove_unused_names_visit_region(
              func, else_region, removed_ids, peeled_roots, used_labels, removed_labels,
              touched_removed_labels,
            ) ||
            changed
        None => ()
      }
    }
    @ir.HotOp::Try => {
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_body_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
      match @ir.hot_region_catch_ref(func, node_id) {
        Some(catch_region) =>
          changed = remove_unused_names_visit_region(
              func, catch_region, removed_ids, peeled_roots, used_labels, removed_labels,
              touched_removed_labels,
            ) ||
            changed
        None => ()
      }
    }
    @ir.HotOp::TryTable => {
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_body_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
      changed = remove_unused_names_visit_region(
          func,
          @ir.hot_region_catch_list_ref(func, node_id),
          removed_ids,
          peeled_roots,
          used_labels,
          removed_labels,
          touched_removed_labels,
        ) ||
        changed
    }
    _ => return false
  }
  changed
}

///|
fn remove_unused_names_run(
  ctx : HotPassContext,
  func : @ir.HotFunc,
) -> HotPassResult {
  let removed_ids : Array[Int32] = []
  let peeled_roots : Array[Int32] = []
  let used_labels = remove_unused_names_compute_live_label_uses(func)
  let removed_labels = @bitset.BitSet::new(func.labels.length())
  let touched_removed_labels : Array[Int32] = []
  if !remove_unused_names_visit_region(
      func,
      @ir.HotRegionRef::root(),
      removed_ids,
      peeled_roots,
      used_labels,
      removed_labels,
      touched_removed_labels,
    ) {
    return HotPassResult::unchanged()
  }
  pass_mark_mutated(ctx, func)
  HotPassResult::changed()
}