// 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 2016 WebAssembly Community Group participants
// Counterpart: src/passes/MemoryPacking.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 memory_packing_summary() -> String {
  "Pack active and passive data segments around profitable zero ranges while preserving segment-user semantics."
}

///|
priv struct MpRange {
  is_zero : Bool
  start : Int32
  end_ : Int32
}

///|
fn MpRange::new(is_zero : Bool, start : Int32, end_ : Int32) -> MpRange {
  { is_zero, start, end_, }
}

///|
priv struct MpSpan {
  start : UInt64
  end_ : UInt64
  end_at_limit : Bool
}

///|
fn MpSpan::new(start : UInt64, end_ : UInt64, end_at_limit : Bool) -> MpSpan {
  { start, end_, end_at_limit, }
}

///|
priv enum MpBaseOffset {
  I32(UInt32)
  I64(UInt64)
}

///|
priv enum MpMemoryAddressType {
  I32Address
  I64Address
}

///|
fn mp_memory_address_type(mod_ : @lib.Module) -> MpMemoryAddressType? {
  match mp_sole_memory_type(mod_) {
    Some((@lib.MemType(@lib.I32Limits(_, _), _), _)) =>
      Some(MpMemoryAddressType::I32Address)
    Some((@lib.MemType(@lib.I64Limits(_, _), _), _)) =>
      Some(MpMemoryAddressType::I64Address)
    None => None
  }
}

///|
fn mp_address_val_type(address_type : MpMemoryAddressType) -> @lib.ValType {
  match address_type {
    I32Address => @lib.ValType::i32()
    I64Address => @lib.ValType::i64()
  }
}

///|
fn mp_address_const(
  address_type : MpMemoryAddressType,
  value : Int32,
) -> @lib.Instruction {
  match address_type {
    I32Address => @lib.Instruction::i32_const(@lib.I32(value))
    I64Address => @lib.Instruction::i64_const(@lib.I64(value.to_int64()))
  }
}

///|
fn mp_append_address_add(
  out : Array[@lib.Instruction],
  address_type : MpMemoryAddressType,
) -> Unit {
  match address_type {
    I32Address => out.push(@lib.Instruction::i32_add())
    I64Address => out.push(@lib.Instruction::i64_add())
  }
}

///|
fn mp_append_address_gt_u(
  out : Array[@lib.Instruction],
  address_type : MpMemoryAddressType,
) -> Unit {
  match address_type {
    I32Address => out.push(@lib.Instruction::i32_gt_u())
    I64Address => out.push(@lib.Instruction::i64_gt_u())
  }
}

///|
priv struct MpDataUsage {
  has_non_drop : Bool
  has_drop : Bool
}

///|
fn MpDataUsage::new(has_non_drop : Bool, has_drop : Bool) -> MpDataUsage {
  { has_non_drop, has_drop, }
}

///|
fn mp_imported_mem_count(mod_ : @lib.Module) -> Int32 {
  let mut count = 0
  match mod_.import_sec {
    Some(@lib.ImportSec(imports)) =>
      for import_ in imports {
        match import_ {
          @lib.Import(_, _, @lib.MemExternType(_)) => count += 1
          _ => ()
        }
      }
    None => ()
  }
  count
}

///|
fn mp_defined_mem_count(mod_ : @lib.Module) -> Int32 {
  match mod_.mem_sec {
    Some(@lib.MemSec(mems)) => mems.length()
    None => 0
  }
}

///|
fn mp_sole_memory_type(mod_ : @lib.Module) -> (@lib.MemType, Bool)? {
  match mod_.mem_sec {
    Some(@lib.MemSec([mem_type])) => return Some((mem_type, false))
    Some(_) => return None
    None => ()
  }
  let mut found : @lib.MemType? = None
  match mod_.import_sec {
    Some(@lib.ImportSec(imports)) =>
      for import_ in imports {
        match import_ {
          @lib.Import(_, _, @lib.MemExternType(mem_type)) =>
            match found {
              Some(_) => return None
              None => found = Some(mem_type)
            }
          _ => ()
        }
      }
    None => ()
  }
  match found {
    Some(mem_type) => Some((mem_type, true))
    None => None
  }
}

///|
fn mp_memory_initial_pages(mem_type : @lib.MemType) -> UInt64 {
  match mem_type {
    @lib.MemType(@lib.I32Limits(initial, _), _) => initial.to_uint64()
    @lib.MemType(@lib.I64Limits(initial, _), _) => initial
  }
}

///|
fn mp_provably_in_bounds(
  mem_type : @lib.MemType,
  offset : UInt64,
  size : Int32,
) -> Bool {
  let size_u = size.reinterpret_as_uint().to_uint64()
  let end_ = offset + size_u
  let initial_pages = mp_memory_initial_pages(mem_type)
  if end_ < offset {
    return end_ == 0UL && initial_pages == 1UL << 48
  }
  let mut end_pages = end_ >> 16
  if (end_ & 0xffffUL) != 0UL {
    end_pages += 1UL
  }
  end_pages <= initial_pages
}

///|
fn mp_parse_base_offset(expr : @lib.Expr) -> MpBaseOffset? {
  match expr {
    @lib.Expr([@lib.I32Const(@lib.I32(value))]) =>
      Some(MpBaseOffset::I32(value.reinterpret_as_uint()))
    @lib.Expr([@lib.I64Const(@lib.I64(value))]) =>
      Some(MpBaseOffset::I64(value.reinterpret_as_uint64()))
    _ => None
  }
}

///|
fn mp_base_offset_u64(base : MpBaseOffset) -> UInt64 {
  match base {
    I32(value) => value.to_uint64()
    I64(value) => value
  }
}

///|
// The active rewrite proves that every retained byte offset is representable.
fn mp_shift_base_offset(base : MpBaseOffset, delta : Int32) -> @lib.Expr {
  match base {
    I32(value) => {
      let shifted = value.to_uint64() + delta.reinterpret_as_uint().to_uint64()
      @lib.Expr::new([
        @lib.Instruction::i32_const(
          @lib.I32(shifted.to_uint().reinterpret_as_int()),
        ),
      ])
    }
    I64(value) =>
      @lib.Expr::new([
        @lib.Instruction::i64_const(
          @lib.I64(
            (value + delta.reinterpret_as_uint().to_uint64()).reinterpret_as_int64(),
          ),
        ),
      ])
  }
}

///|
fn mp_slice_bytes(bytes : Bytes, start : Int32, end_ : Int32) -> Bytes {
  let out = @buffer.new(size_hint=end_ - start)
  for i = start; i < end_; i = i + 1 {
    out.write_byte(bytes[i])
  }
  out.to_bytes()
}

///|
fn mp_collect_ranges(bytes : Bytes) -> Array[MpRange] {
  let ranges : Array[MpRange] = []
  let mut start = 0
  while start < bytes.length() {
    let mut end_ = start
    while end_ < bytes.length() && bytes[end_] == 0 {
      end_ += 1
    }
    if end_ > start {
      ranges.push(MpRange::new(true, start, end_))
      start = end_
    }
    while end_ < bytes.length() && bytes[end_] != 0 {
      end_ += 1
    }
    if end_ > start {
      ranges.push(MpRange::new(false, start, end_))
      start = end_
    }
  }
  ranges
}

///|
fn mp_merge_small_zero_ranges(
  ranges : Array[MpRange],
  threshold : Int32,
) -> Array[MpRange] {
  if ranges.is_empty() {
    return []
  }
  let merged : Array[MpRange] = [ranges[0]]
  let mut idx = 1
  while idx < ranges.length() {
    if idx + 1 < ranges.length() {
      let curr = ranges[idx]
      if curr.is_zero && curr.end_ - curr.start <= threshold {
        let left = merged[merged.length() - 1]
        let right = ranges[idx + 1]
        merged[merged.length() - 1] = MpRange::new(
          left.is_zero,
          left.start,
          right.end_,
        )
        idx += 2
        continue
      }
    }
    merged.push(ranges[idx])
    idx += 1
  }
  merged
}

///|
fn mp_preserve_trapping_top_byte(
  ranges : Array[MpRange],
  size : Int32,
) -> Array[MpRange] {
  if ranges.is_empty() {
    return ranges
  }
  let preserved : Array[MpRange] = []
  for range in ranges {
    preserved.push(range)
  }
  let last_idx = preserved.length() - 1
  let last = preserved[last_idx]
  if last.is_zero {
    preserved[last_idx] = MpRange::new(true, last.start, last.end_ - 1)
    preserved.push(MpRange::new(false, size - 1, size))
  }
  preserved
}

///|
fn mp_should_preserve_trap(
  mod_ : @lib.Module,
  base : MpBaseOffset,
  size : Int32,
) -> Bool {
  match mp_sole_memory_type(mod_) {
    Some((mem_type, _)) =>
      !mp_provably_in_bounds(mem_type, mp_base_offset_u64(base), size)
    None => true
  }
}

///|
fn mp_active_rewrite_fast_single_range(
  mem_idx : @lib.MemIdx,
  base : MpBaseOffset,
  bytes : Bytes,
  preserve_trap : Bool,
) -> Array[@lib.Data]? {
  let mut first = -1
  let mut last = -1
  let mut idx = 0
  while idx < bytes.length() {
    if bytes[idx] != 0 {
      if first < 0 {
        first = idx
      }
      last = idx
    }
    idx += 1
  }
  if first < 0 {
    if preserve_trap {
      return Some([
        @lib.Data::new(
          @lib.DataMode::active(
            mem_idx,
            mp_shift_base_offset(base, bytes.length() - 1),
          ),
          b"\x00",
        ),
      ])
    }
    return Some([])
  }

  let threshold = 8
  let mut zero_run = 0
  idx = first
  while idx <= last {
    if bytes[idx] == 0 {
      zero_run += 1
      if zero_run > threshold {
        return None
      }
    } else {
      zero_run = 0
    }
    idx += 1
  }

  let rewritten : Array[@lib.Data] = [
    @lib.Data::new(
      @lib.DataMode::active(mem_idx, mp_shift_base_offset(base, first)),
      mp_slice_bytes(bytes, first, last + 1),
    ),
  ]
  if preserve_trap && last + 1 < bytes.length() {
    rewritten.push(
      @lib.Data::new(
        @lib.DataMode::active(
          mem_idx,
          mp_shift_base_offset(base, bytes.length() - 1),
        ),
        b"\x00",
      ),
    )
  }
  Some(rewritten)
}

///|
fn mp_active_rewrite(
  mod_ : @lib.Module,
  mem_idx : @lib.MemIdx,
  expr : @lib.Expr,
  bytes : Bytes,
  traps_never_happen : Bool,
) -> Array[@lib.Data] {
  if bytes.length() == 0 {
    return [@lib.Data::new(@lib.DataMode::active(mem_idx, expr), bytes)]
  }
  let base = match mp_parse_base_offset(expr) {
    Some(base) => base
    None => return [@lib.Data::new(@lib.DataMode::active(mem_idx, expr), bytes)]
  }
  // Every retained byte address must be representable without wrapping or clamping.
  let max_offset = match base {
    I32(_) => 0xffff_ffffUL
    I64(_) => 0xffff_ffff_ffff_ffffUL
  }
  if (bytes.length() - 1).to_uint64() > max_offset - mp_base_offset_u64(base) {
    return [@lib.Data::new(@lib.DataMode::active(mem_idx, expr), bytes)]
  }
  let preserve_trap = !traps_never_happen &&
    mp_should_preserve_trap(mod_, base, bytes.length())
  // An imported memory remains observable after failed instantiation. Splitting
  // a possibly out-of-bounds segment must not write a prefix before its final
  // range check traps; the original segment checks its entire range first.
  let preserve_atomic_init = preserve_trap && mp_imported_mem_count(mod_) != 0
  match
    mp_active_rewrite_fast_single_range(mem_idx, base, bytes, preserve_trap) {
    Some(rewritten) if !preserve_atomic_init || rewritten.length() <= 1 =>
      return rewritten
    Some(_) | None if preserve_atomic_init =>
      return [@lib.Data::new(@lib.DataMode::active(mem_idx, expr), bytes)]
    _ => ()
  }
  let ranges = mp_collect_ranges(bytes)
  if ranges.is_empty() {
    return [@lib.Data::new(@lib.DataMode::active(mem_idx, expr), bytes)]
  }
  let mut merged = mp_merge_small_zero_ranges(ranges, 8)
  if preserve_trap {
    merged = mp_preserve_trapping_top_byte(merged, bytes.length())
  }
  let rewritten : Array[@lib.Data] = []
  for range in merged {
    if range.is_zero || range.end_ <= range.start {
      continue
    }
    rewritten.push(
      @lib.Data::new(
        @lib.DataMode::active(mem_idx, mp_shift_base_offset(base, range.start)),
        mp_slice_bytes(bytes, range.start, range.end_),
      ),
    )
  }
  rewritten
}

///|
fn mp_active_span(start : UInt64, size : Int32) -> MpSpan? {
  if size == 0 {
    return None
  }
  let end_ = start + size.reinterpret_as_uint().to_uint64()
  if end_ < start {
    if end_ == 0UL {
      Some(MpSpan::new(start, end_, true))
    } else {
      None
    }
  } else {
    Some(MpSpan::new(start, end_, false))
  }
}

///|
fn mp_active_span_order(lhs : MpSpan, rhs : MpSpan) -> Int32 {
  if lhs.start < rhs.start {
    -1
  } else if lhs.start > rhs.start {
    1
  } else if lhs.end_at_limit && !rhs.end_at_limit {
    1
  } else if !lhs.end_at_limit && rhs.end_at_limit {
    -1
  } else if lhs.end_ < rhs.end_ {
    -1
  } else if lhs.end_ > rhs.end_ {
    1
  } else {
    0
  }
}

///|
fn mp_active_spans_are_disjoint(spans : Array[MpSpan]) -> Bool {
  if spans.length() <= 1 {
    return true
  }
  spans.sort_by(mp_active_span_order)
  let mut covered_end = spans[0].end_
  let mut covered_to_limit = spans[0].end_at_limit
  let mut idx = 1
  while idx < spans.length() {
    let curr = spans[idx]
    if covered_to_limit || curr.start < covered_end {
      return false
    }
    covered_end = curr.end_
    covered_to_limit = curr.end_at_limit
    idx += 1
  }
  true
}

///|
fn mp_trampled_overlap_range(
  earlier_start : UInt64,
  earlier_size : Int32,
  later_start : UInt64,
  later_size : Int32,
) -> (Int32, Int32)? {
  let earlier_size_u = earlier_size.reinterpret_as_uint().to_uint64()
  let later_size_u = later_size.reinterpret_as_uint().to_uint64()
  let (overlap_start_u, overlap_size_u) = if later_start >= earlier_start {
    let delta = later_start - earlier_start
    if delta >= earlier_size_u {
      return None
    }
    let available = earlier_size_u - delta
    (delta, if later_size_u < available { later_size_u } else { available })
  } else {
    let delta = earlier_start - later_start
    if delta >= later_size_u {
      return None
    }
    let available = later_size_u - delta
    (0UL, if earlier_size_u < available { earlier_size_u } else { available })
  }
  if overlap_size_u == 0UL {
    return None
  }
  let overlap_start = overlap_start_u.to_int()
  let overlap_end = overlap_start + overlap_size_u.to_int()
  Some((overlap_start, overlap_end))
}

///|
fn mp_zero_out_trampled_data_pairwise(datas : Array[@lib.Data]) -> Unit {
  for earlier_idx = datas.length() - 1
      earlier_idx >= 0
      earlier_idx = earlier_idx - 1 {
    let (mode, start, original) = match datas[earlier_idx] {
      @lib.Data(mode, bytes) =>
        match mode {
          @lib.DataMode::Active(@lib.MemIdx(0U), expr) => {
            let base = match mp_parse_base_offset(expr) {
              Some(base) => base
              None => continue
            }
            (mode, mp_base_offset_u64(base), bytes)
          }
          _ => continue
        }
    }
    let mut rewritten : Array[Byte]? = None
    for later_idx = earlier_idx + 1
        later_idx < datas.length()
        later_idx = later_idx + 1 {
      match datas[later_idx] {
        @lib.Data(@lib.Active(@lib.MemIdx(0U), expr), later_bytes) => {
          let later_base = match mp_parse_base_offset(expr) {
            Some(base) => base
            None => continue
          }
          match
            mp_trampled_overlap_range(
              start,
              original.length(),
              mp_base_offset_u64(later_base),
              later_bytes.length(),
            ) {
            Some((overlap_start, overlap_end)) => {
              let bytes = match rewritten {
                Some(bytes) => bytes
                None => {
                  let bytes = original.to_array()
                  rewritten = Some(bytes)
                  bytes
                }
              }
              for idx = overlap_start; idx < overlap_end; idx = idx + 1 {
                bytes[idx] = (0).to_byte()
              }
              if overlap_start == 0 && overlap_end == original.length() {
                break
              }
            }
            None => ()
          }
        }
        _ => ()
      }
    }
    datas[earlier_idx] = @lib.Data::new(
      mode,
      match rewritten {
        Some(bytes) => Bytes::from_array(bytes)
        None => original
      },
    )
  }
}

///|
fn mp_span_reaches(span : MpSpan, start : UInt64) -> Bool {
  span.end_at_limit || span.end_ >= start
}

///|
fn mp_span_merge(lhs : MpSpan, rhs : MpSpan) -> MpSpan {
  let start = if lhs.start < rhs.start { lhs.start } else { rhs.start }
  if lhs.end_at_limit || rhs.end_at_limit {
    MpSpan::new(start, 0UL, true)
  } else {
    MpSpan::new(
      start,
      if lhs.end_ > rhs.end_ {
        lhs.end_
      } else {
        rhs.end_
      },
      false,
    )
  }
}

///|
priv struct MpSpanUnion {
  spans : Array[MpSpan]
  left : Array[Int32]
  right : Array[Int32]
  height : Array[Int32]
  mut root : Int32
}

///|
fn MpSpanUnion::new() -> MpSpanUnion {
  { spans: [], left: [], right: [], height: [], root: -1, }
}

///|
fn mp_span_union_height(union : MpSpanUnion, node : Int32) -> Int32 {
  if node < 0 {
    0
  } else {
    union.height[node]
  }
}

///|
fn mp_span_union_update_height(union : MpSpanUnion, node : Int32) -> Unit {
  let left_height = mp_span_union_height(union, union.left[node])
  let right_height = mp_span_union_height(union, union.right[node])
  union.height[node] = 1 +
    (if left_height > right_height { left_height } else { right_height })
}

///|
fn mp_span_union_rotate_left(union : MpSpanUnion, node : Int32) -> Int32 {
  let pivot = union.right[node]
  union.right[node] = union.left[pivot]
  union.left[pivot] = node
  mp_span_union_update_height(union, node)
  mp_span_union_update_height(union, pivot)
  pivot
}

///|
fn mp_span_union_rotate_right(union : MpSpanUnion, node : Int32) -> Int32 {
  let pivot = union.left[node]
  union.left[node] = union.right[pivot]
  union.right[pivot] = node
  mp_span_union_update_height(union, node)
  mp_span_union_update_height(union, pivot)
  pivot
}

///|
fn mp_span_union_rebalance(union : MpSpanUnion, node : Int32) -> Int32 {
  if node < 0 {
    return node
  }
  mp_span_union_update_height(union, node)
  let balance = mp_span_union_height(union, union.left[node]) -
    mp_span_union_height(union, union.right[node])
  if balance > 1 {
    let left = union.left[node]
    if mp_span_union_height(union, union.left[left]) <
      mp_span_union_height(union, union.right[left]) {
      union.left[node] = mp_span_union_rotate_left(union, left)
    }
    return mp_span_union_rotate_right(union, node)
  }
  if balance < -1 {
    let right = union.right[node]
    if mp_span_union_height(union, union.right[right]) <
      mp_span_union_height(union, union.left[right]) {
      union.right[node] = mp_span_union_rotate_right(union, right)
    }
    return mp_span_union_rotate_left(union, node)
  }
  node
}

///|
fn mp_span_union_insert_node(
  union : MpSpanUnion,
  root : Int32,
  node : Int32,
) -> Int32 {
  if root < 0 {
    return node
  }
  if union.spans[node].start < union.spans[root].start {
    union.left[root] = mp_span_union_insert_node(union, union.left[root], node)
  } else {
    union.right[root] = mp_span_union_insert_node(
      union,
      union.right[root],
      node,
    )
  }
  mp_span_union_rebalance(union, root)
}

///|
fn mp_span_union_min_node(union : MpSpanUnion, root : Int32) -> Int32 {
  let mut node = root
  while union.left[node] >= 0 {
    node = union.left[node]
  }
  node
}

///|
fn mp_span_union_delete_node(
  union : MpSpanUnion,
  root : Int32,
  start : UInt64,
) -> Int32 {
  if root < 0 {
    return root
  }
  if start < union.spans[root].start {
    union.left[root] = mp_span_union_delete_node(union, union.left[root], start)
  } else if start > union.spans[root].start {
    union.right[root] = mp_span_union_delete_node(
      union,
      union.right[root],
      start,
    )
  } else if union.left[root] < 0 {
    return union.right[root]
  } else if union.right[root] < 0 {
    return union.left[root]
  } else {
    let successor = mp_span_union_min_node(union, union.right[root])
    union.spans[root] = union.spans[successor]
    union.right[root] = mp_span_union_delete_node(
      union,
      union.right[root],
      union.spans[successor].start,
    )
  }
  mp_span_union_rebalance(union, root)
}

///|
fn mp_span_union_lower_bound(union : MpSpanUnion, start : UInt64) -> Int32 {
  let mut node = union.root
  let mut best = -1
  while node >= 0 {
    if union.spans[node].start >= start {
      best = node
      node = union.left[node]
    } else {
      node = union.right[node]
    }
  }
  best
}

///|
fn mp_span_union_predecessor(union : MpSpanUnion, start : UInt64) -> Int32 {
  let mut node = union.root
  let mut best = -1
  while node >= 0 {
    if union.spans[node].start < start {
      best = node
      node = union.right[node]
    } else {
      node = union.left[node]
    }
  }
  best
}

///|
fn mp_span_union_successor(union : MpSpanUnion, start : UInt64) -> Int32 {
  let mut node = union.root
  let mut best = -1
  while node >= 0 {
    if union.spans[node].start > start {
      best = node
      node = union.left[node]
    } else {
      node = union.right[node]
    }
  }
  best
}

///|
fn mp_span_union_first_overlap(union : MpSpanUnion, span : MpSpan) -> Int32 {
  let predecessor = mp_span_union_predecessor(union, span.start)
  if predecessor >= 0 {
    let candidate = union.spans[predecessor]
    if candidate.end_at_limit || candidate.end_ > span.start {
      return predecessor
    }
  }
  mp_span_union_lower_bound(union, span.start)
}

///|
fn mp_span_union_insert(covered : MpSpanUnion, span : MpSpan) -> Unit {
  let mut merged = span
  let predecessor = mp_span_union_predecessor(covered, merged.start)
  if predecessor >= 0 &&
    mp_span_reaches(covered.spans[predecessor], merged.start) {
    let predecessor_start = covered.spans[predecessor].start
    merged = mp_span_merge(covered.spans[predecessor], merged)
    covered.root = mp_span_union_delete_node(
      covered,
      covered.root,
      predecessor_start,
    )
  }
  let mut next = mp_span_union_lower_bound(covered, merged.start)
  while next >= 0 && mp_span_reaches(merged, covered.spans[next].start) {
    let next_start = covered.spans[next].start
    merged = mp_span_merge(merged, covered.spans[next])
    covered.root = mp_span_union_delete_node(covered, covered.root, next_start)
    next = mp_span_union_lower_bound(covered, merged.start)
  }
  let node = covered.spans.length()
  covered.spans.push(merged)
  covered.left.push(-1)
  covered.right.push(-1)
  covered.height.push(1)
  covered.root = mp_span_union_insert_node(covered, covered.root, node)
}

///|
fn mp_zero_out_trampled_data(datas : Array[@lib.Data]) -> Unit {
  if datas.length() < 8 {
    mp_zero_out_trampled_data_pairwise(datas)
    return
  }
  let spans : Array[MpSpan?] = []
  for data in datas {
    match data {
      @lib.Data(@lib.Active(@lib.MemIdx(0U), expr), bytes) =>
        match mp_parse_base_offset(expr) {
          Some(base) => {
            let span = mp_active_span(mp_base_offset_u64(base), bytes.length())
            if span is None && !bytes.is_empty() {
              mp_zero_out_trampled_data_pairwise(datas)
              return
            }
            spans.push(span)
          }
          None => spans.push(None)
        }
      _ => spans.push(None)
    }
  }
  let covered = MpSpanUnion::new()
  for earlier_idx = datas.length() - 1
      earlier_idx >= 0
      earlier_idx = earlier_idx - 1 {
    let span = match spans[earlier_idx] {
      Some(span) => span
      None => continue
    }
    let (mode, original) = match datas[earlier_idx] {
      @lib.Data(mode, bytes) => (mode, bytes)
    }
    let mut at = mp_span_union_first_overlap(covered, span)
    let mut rewritten : Array[Byte]? = None
    let original_size = original.length().reinterpret_as_uint().to_uint64()
    while at >= 0 {
      let overlap = covered.spans[at]
      let first = if overlap.start > span.start {
        overlap.start - span.start
      } else {
        0UL
      }
      if first >= original_size {
        break
      }
      let last = if overlap.end_at_limit {
        original_size
      } else {
        let delta = overlap.end_ - span.start
        if delta < original_size {
          delta
        } else {
          original_size
        }
      }
      if first < last {
        let bytes = match rewritten {
          Some(bytes) => bytes
          None => {
            let bytes = original.to_array()
            rewritten = Some(bytes)
            bytes
          }
        }
        for idx = first.to_int(); idx < last.to_int(); idx = idx + 1 {
          bytes[idx] = (0).to_byte()
        }
      }
      at = mp_span_union_successor(covered, overlap.start)
    }
    datas[earlier_idx] = @lib.Data::new(
      mode,
      match rewritten {
        Some(bytes) => Bytes::from_array(bytes)
        None => original
      },
    )
    mp_span_union_insert(covered, span)
  }
}

///|
fn mp_can_optimize(
  mod_ : @lib.Module,
  datas : Array[@lib.Data],
  zero_filled_memory : Bool,
) -> Bool {
  let imported_mem_count = mp_imported_mem_count(mod_)
  if imported_mem_count != 0 && !zero_filled_memory {
    return false
  }
  if imported_mem_count + mp_defined_mem_count(mod_) != 1 {
    return false
  }
  if datas.length() <= 1 {
    return true
  }
  let spans : Array[MpSpan] = []
  for data in datas {
    match data {
      @lib.Data(@lib.Active(@lib.MemIdx(mem_idx), expr), bytes) => {
        if mem_idx != 0U {
          return false
        }
        let base = match mp_parse_base_offset(expr) {
          Some(base) => base
          None => return false
        }
        match mp_active_span(mp_base_offset_u64(base), bytes.length()) {
          Some(span) => spans.push(span)
          None => if !bytes.is_empty() { return false }
        }
      }
      @lib.Data(@lib.Passive, _) => ()
    }
  }
  if mp_active_spans_are_disjoint(spans) {
    return true
  }
  if imported_mem_count != 0 {
    let mem_type = match mp_sole_memory_type(mod_) {
      Some((mem_type, true)) => mem_type
      _ => return false
    }
    for data in datas {
      match data {
        @lib.Data(@lib.Active(@lib.MemIdx(0U), expr), bytes) => {
          let base = match mp_parse_base_offset(expr) {
            Some(base) => base
            None => return false
          }
          if !mp_provably_in_bounds(
              mem_type,
              mp_base_offset_u64(base),
              bytes.length(),
            ) {
            return false
          }
        }
        @lib.Data(@lib.Active(_, _), _) => return false
        @lib.Data(@lib.Passive, _) => ()
      }
    }
  }
  mp_zero_out_trampled_data(datas)
  true
}

///|
fn mp_data_idx_slot(idx : @lib.DataIdx) -> Int32 {
  let @lib.DataIdx(raw) = idx
  raw.reinterpret_as_int()
}

///|
fn mp_mark_data_non_drop(
  usages : Array[MpDataUsage],
  idx : @lib.DataIdx,
) -> Unit {
  let slot = mp_data_idx_slot(idx)
  if slot < 0 || slot >= usages.length() {
    return
  }
  let usage = usages[slot]
  usages[slot] = MpDataUsage::new(true, usage.has_drop)
}

///|
fn mp_mark_data_drop(usages : Array[MpDataUsage], idx : @lib.DataIdx) -> Unit {
  let slot = mp_data_idx_slot(idx)
  if slot < 0 || slot >= usages.length() {
    return
  }
  let usage = usages[slot]
  usages[slot] = MpDataUsage::new(usage.has_non_drop, true)
}

///|
fn mp_collect_data_usage_expr(
  expr : @lib.Expr,
  usages : Array[MpDataUsage],
) -> Unit {
  let @lib.Expr(instrs) = expr
  for instr in instrs {
    mp_collect_data_usage_instr(instr, usages)
  }
}

///|
fn mp_collect_data_usage_instr(
  instr : @lib.Instruction,
  usages : Array[MpDataUsage],
) -> Unit {
  match instr {
    @lib.Block(_, body) | @lib.Loop(_, body) =>
      mp_collect_data_usage_expr(body, usages)
    @lib.If(_, then_body, else_body) => {
      for nested in then_body {
        mp_collect_data_usage_instr(nested, usages)
      }
      match else_body {
        Some(body) =>
          for nested in body {
            mp_collect_data_usage_instr(nested, usages)
          }
        None => ()
      }
    }
    @lib.Try(_, body, catches, _) => {
      mp_collect_data_usage_expr(body, usages)
      for catch_ in catches {
        match catch_ {
          @lib.LegacyCatch(_, catch_body) | @lib.LegacyCatchAll(catch_body) =>
            mp_collect_data_usage_expr(catch_body, usages)
        }
      }
    }
    @lib.TryTable(_, _, body) => mp_collect_data_usage_expr(body, usages)
    @lib.ArrayNewData(_, idx)
    | @lib.ArrayInitData(_, idx)
    | @lib.MemoryInit(idx, _) => mp_mark_data_non_drop(usages, idx)
    @lib.DataDrop(idx) => mp_mark_data_drop(usages, idx)
    _ => ()
  }
}

///|
fn mp_collect_data_usages(
  mod_ : @lib.Module,
  data_count : Int32,
) -> Array[MpDataUsage] {
  let usages = Array::make(data_count, MpDataUsage::new(false, false))
  match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) =>
      for func_ in funcs {
        let @lib.Func(_, body) = func_
        mp_collect_data_usage_expr(body, usages)
      }
    None => ()
  }
  usages
}

///|
fn mp_data_segment_limit_exceeded(
  emitted_count : Int32,
  candidate_count : Int32,
  remaining_original_count : Int32,
) -> Bool {
  emitted_count + candidate_count + remaining_original_count > 100000
}

///|
fn mp_needs_data_usage_scan(datas : Array[@lib.Data]) -> Bool {
  for data in datas {
    match data {
      @lib.Data(@lib.Passive, _) => return true
      _ => ()
    }
  }
  false
}

///|
priv struct MpSplitPart {
  start : Int32
  end_ : Int32
  data_idx : Int32
}

///|
fn MpSplitPart::new(
  start : Int32,
  end_ : Int32,
  data_idx : Int32,
) -> MpSplitPart {
  { start, end_, data_idx, }
}

///|
priv struct MpSegmentPlan {
  remap : Int32
  split_parts : Array[MpSplitPart]
  is_active : Bool
  was_split : Bool
  needs_drop_state : Bool
  runtime_size : Int32
  mut drop_state_offset : Int32
}

///|
fn MpSegmentPlan::new(
  remap : Int32,
  split_parts : Array[MpSplitPart],
  is_active : Bool,
  was_split : Bool,
  needs_drop_state : Bool,
  runtime_size : Int32,
) -> MpSegmentPlan {
  {
    remap,
    split_parts,
    is_active,
    was_split,
    needs_drop_state,
    runtime_size,
    drop_state_offset: 0,
  }
}

///|
priv struct MpPassiveUserScan {
  has_memory_init : Bool
  all_memory_init_const : Bool
  has_array_data : Bool
  memory_init_count : Int32
  data_drop_count : Int32
}

///|
fn MpPassiveUserScan::new(
  has_memory_init~ : Bool = false,
  all_memory_init_const~ : Bool = true,
  has_array_data~ : Bool = false,
  memory_init_count~ : Int32 = 0,
  data_drop_count~ : Int32 = 0,
) -> MpPassiveUserScan {
  {
    has_memory_init,
    all_memory_init_const,
    has_array_data,
    memory_init_count,
    data_drop_count,
  }
}

///|
fn mp_passive_scan_merge(
  lhs : MpPassiveUserScan,
  rhs : MpPassiveUserScan,
) -> MpPassiveUserScan {
  MpPassiveUserScan::new(
    has_memory_init=lhs.has_memory_init || rhs.has_memory_init,
    all_memory_init_const=lhs.all_memory_init_const && rhs.all_memory_init_const,
    has_array_data=lhs.has_array_data || rhs.has_array_data,
    memory_init_count=lhs.memory_init_count + rhs.memory_init_count,
    data_drop_count=lhs.data_drop_count + rhs.data_drop_count,
  )
}

///|
fn mp_instr_is_i32_const(instr : @lib.Instruction) -> Bool {
  match instr {
    @lib.I32Const(_) => true
    _ => false
  }
}

///|
fn mp_instr_i32_const_value(instr : @lib.Instruction) -> Int32? {
  match instr {
    @lib.I32Const(@lib.I32(value)) => Some(value)
    _ => None
  }
}

///|
fn mp_name_to_string(name : @lib.Name) -> String {
  let @lib.Name(text) = name
  text.to_owned()
}

///|
fn mp_string_starts_with(text : String, prefix : String) -> Bool {
  text.length() >= prefix.length() &&
  text.sub(start=0, end=prefix.length()).to_string() == prefix
}

///|
fn mp_data_names_by_idx(
  mod_ : @lib.Module,
  data_count : Int32,
) -> Array[@lib.Name?] {
  let names : Array[@lib.Name?] = Array::make(data_count, None)
  match mod_.name_sec {
    Some(name_sec) =>
      match name_sec.data_names {
        Some(@lib.NameMap(entries)) =>
          for entry in entries {
            let @lib.NameAssoc(raw_idx, name) = entry
            let idx = raw_idx.reinterpret_as_int()
            if idx >= 0 && idx < data_count && names[idx] is None {
              names[idx] = Some(name)
            }
          }
        None => ()
      }
    None => ()
  }
  names
}

///|
fn mp_data_name_has_prefix(name : @lib.Name?, prefix : String) -> Bool {
  match name {
    Some(name) => mp_string_starts_with(mp_name_to_string(name), prefix)
    None => false
  }
}

///|
fn mp_imported_global_count(mod_ : @lib.Module) -> Int32 {
  let mut count = 0
  match mod_.import_sec {
    Some(@lib.ImportSec(imports)) =>
      for import_ in imports {
        match import_ {
          @lib.Import(_, _, @lib.GlobalExternType(_)) => count += 1
          _ => ()
        }
      }
    None => ()
  }
  count
}

///|
fn mp_defined_global_count(mod_ : @lib.Module) -> Int32 {
  match mod_.global_sec {
    Some(@lib.GlobalSec(globals)) => globals.length()
    None => 0
  }
}

///|
fn mp_append_drop_state_global(
  mod_ : @lib.Module,
  need_drop_state : Int32,
) -> (@lib.GlobalSec?, @lib.GlobalIdx?) {
  if need_drop_state == 0 {
    return (mod_.global_sec, None)
  }
  let global_idx = @lib.GlobalIdx::new(
    (mp_imported_global_count(mod_) + mp_defined_global_count(mod_)).reinterpret_as_uint(),
  )
  let next_global = @lib.Global::new(
    @lib.GlobalType::new(@lib.ValType::i32(), true),
    @lib.Expr::new([@lib.Instruction::i32_const(@lib.I32(0))]),
  )
  let globals : Array[@lib.Global] = []
  match mod_.global_sec {
    Some(@lib.GlobalSec(existing)) =>
      for global in existing {
        globals.push(global)
      }
    None => ()
  }
  for i = 0; i < need_drop_state; i = i + 1 {
    globals.push(next_global)
  }
  (Some(@lib.GlobalSec::new(globals)), Some(global_idx))
}

///|
fn mp_type_idx_flat_slot(idx : @lib.TypeIdx) -> Int32? {
  match idx {
    @lib.TypeIdx(raw) => Some(raw.reinterpret_as_int())
    @lib.RecIdx(_) => None
  }
}

///|
fn mp_subtype_func_param_count(subtype : @lib.SubType) -> Int32? {
  match subtype {
    @lib.CompTypeSubType(_, @lib.FuncCompType(params, _)) =>
      Some(params.length())
    @lib.SubType(_, _, _, @lib.FuncCompType(params, _)) => Some(params.length())
    _ => None
  }
}

///|
fn mp_type_sec_func_param_count(
  type_sec : @lib.TypeSec?,
  type_idx : @lib.TypeIdx,
) -> Int32 {
  let target = match mp_type_idx_flat_slot(type_idx) {
    Some(slot) => slot
    None => return 0
  }
  let mut flat = 0
  match type_sec {
    Some(@lib.TypeSec(rec_types)) =>
      for rec in rec_types {
        match rec {
          @lib.SingleRecType(subtype) => {
            if flat == target {
              match mp_subtype_func_param_count(subtype) {
                Some(count) => return count
                None => return 0
              }
            }
            flat += 1
          }
          @lib.GroupRecType(subtypes) =>
            for subtype in subtypes {
              if flat == target {
                match mp_subtype_func_param_count(subtype) {
                  Some(count) => return count
                  None => return 0
                }
              }
              flat += 1
            }
        }
      }
    None => ()
  }
  0
}

///|
fn mp_defined_func_param_counts(mod_ : @lib.Module) -> Array[Int32] {
  let type_idxs = match mod_.func_sec {
    Some(@lib.FuncSec(type_idxs)) => type_idxs
    None => return []
  }
  if type_idxs.length() <= 1 {
    return type_idxs.map(fn(idx) {
      mp_type_sec_func_param_count(mod_.type_sec, idx)
    })
  }
  // Flatten only the referenced prefix, once for all defined functions.
  // Unreferenced type tails and absent function sections need no table.
  let mut last_slot = -1
  for idx in type_idxs {
    if mp_type_idx_flat_slot(idx) is Some(slot) && slot > last_slot {
      last_slot = slot
    }
  }
  let by_type : Array[Int32] = []
  match mod_.type_sec {
    Some(@lib.TypeSec(rec_types)) =>
      for rec in rec_types {
        if by_type.length() > last_slot {
          break
        }
        match rec {
          @lib.SingleRecType(subtype) =>
            by_type.push(mp_subtype_func_param_count(subtype).unwrap_or(0))
          @lib.GroupRecType(subtypes) =>
            for subtype in subtypes {
              if by_type.length() > last_slot {
                break
              }
              by_type.push(mp_subtype_func_param_count(subtype).unwrap_or(0))
            }
        }
      }
    None => ()
  }
  type_idxs.map(fn(idx) {
    match mp_type_idx_flat_slot(idx) {
      Some(slot) => by_type.get(slot).unwrap_or(0)
      None => 0
    }
  })
}

///|
fn mp_collect_segment_user_instrs(
  instrs : Array[@lib.Instruction],
  scans : Array[MpPassiveUserScan],
) -> Unit {
  fn record(idx : @lib.DataIdx, usage : MpPassiveUserScan) -> Unit {
    let slot = mp_data_idx_slot(idx)
    if slot >= 0 && slot < scans.length() {
      scans[slot] = mp_passive_scan_merge(scans[slot], usage)
    }
  }
  for i = 0; i < instrs.length(); i = i + 1 {
    match instrs[i] {
      @lib.MemoryInit(idx, _) =>
        record(
          idx,
          MpPassiveUserScan::new(
            has_memory_init=true,
            all_memory_init_const=i >= 2 &&
              mp_instr_is_i32_const(instrs[i - 2]) &&
              mp_instr_is_i32_const(instrs[i - 1]),
            memory_init_count=1,
          ),
        )
      @lib.DataDrop(idx) =>
        record(idx, MpPassiveUserScan::new(data_drop_count=1))
      @lib.ArrayNewData(_, idx) | @lib.ArrayInitData(_, idx) =>
        record(idx, MpPassiveUserScan::new(has_array_data=true))
      @lib.Block(_, @lib.Expr(body))
      | @lib.Loop(_, @lib.Expr(body))
      | @lib.TryTable(_, _, @lib.Expr(body)) =>
        mp_collect_segment_user_instrs(body, scans)
      @lib.Try(_, @lib.Expr(body), catches, _) => {
        mp_collect_segment_user_instrs(body, scans)
        for catch_ in catches {
          let body = match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(body))
            | @lib.LegacyCatchAll(@lib.Expr(body)) => body
          }
          mp_collect_segment_user_instrs(body, scans)
        }
      }
      @lib.If(_, then_body, else_body) => {
        mp_collect_segment_user_instrs(then_body, scans)
        if else_body is Some(body) {
          mp_collect_segment_user_instrs(body, scans)
        }
      }
      _ => ()
    }
  }
}

///|
// One complete traversal indexed by original segment, shared by eligibility,
// split profitability, and active GC-identity checks. Never rescan per segment.
fn mp_collect_segment_users(
  mod_ : @lib.Module,
  count : Int32,
) -> Array[MpPassiveUserScan] {
  let scans = Array::make(count, MpPassiveUserScan::new())
  if mod_.code_sec is Some(@lib.CodeSec(funcs)) {
    for func_ in funcs {
      let @lib.Func(_, @lib.Expr(body)) = func_
      mp_collect_segment_user_instrs(body, scans)
    }
  }
  scans
}

///|
fn mp_passive_split_parts(
  scan : MpPassiveUserScan,
  bytes : Bytes,
  first_new_idx : Int32,
) -> (Array[MpSplitPart], Bool) {
  if bytes.length() == 0 {
    return ([], false)
  }
  let threshold = 2 + scan.memory_init_count * 19 + scan.data_drop_count * 3
  let edge_threshold = scan.memory_init_count * 9
  let edge_merged = mp_collect_ranges(bytes)
  if edge_merged.length() >= 2 {
    let last_idx = edge_merged.length() - 1
    let last = edge_merged[last_idx]
    if last.is_zero && last.end_ - last.start <= edge_threshold {
      let previous = edge_merged[last_idx - 1]
      edge_merged[last_idx - 1] = MpRange::new(
        previous.is_zero,
        previous.start,
        last.end_,
      )
      ignore(edge_merged.remove(last_idx))
    }
  }
  if edge_merged.length() >= 2 {
    let first = edge_merged[0]
    if first.is_zero && first.end_ - first.start <= edge_threshold {
      let second = edge_merged[1]
      edge_merged[1] = MpRange::new(second.is_zero, first.start, second.end_)
      ignore(edge_merged.remove(0))
    }
  }
  let ranges = mp_merge_small_zero_ranges(edge_merged, threshold)
  let parts : Array[MpSplitPart] = []
  let mut omitted_zero = false
  for range in ranges {
    if range.is_zero {
      omitted_zero = true
    } else if range.end_ > range.start {
      parts.push(
        MpSplitPart::new(
          range.start,
          range.end_,
          first_new_idx + parts.length(),
        ),
      )
    }
  }
  (parts, omitted_zero)
}

///|
fn mp_name_map_from_entries(entries : Array[@lib.NameAssoc]) -> @lib.NameMap? {
  if entries.is_empty() {
    None
  } else {
    Some(@lib.NameMap::new(entries))
  }
}

///|
fn mp_imported_func_count(mod_ : @lib.Module) -> Int32 {
  let mut count = 0
  match mod_.import_sec {
    Some(@lib.ImportSec(imports)) =>
      for import_ in imports {
        match import_ {
          @lib.Import(_, _, @lib.FuncExternType(_)) => count += 1
          _ => ()
        }
      }
    None => ()
  }
  count
}

///|
fn mp_changed_defined_funcs(
  before : @lib.CodeSec?,
  after : @lib.CodeSec?,
  may_change : Array[Bool],
) -> Array[Bool] {
  match (before, after) {
    (Some(@lib.CodeSec(old_funcs)), Some(@lib.CodeSec(new_funcs))) => {
      let changed : Array[Bool] = []
      let count = old_funcs.length().min(new_funcs.length())
      for idx = 0; idx < count; idx = idx + 1 {
        changed.push(
          idx < may_change.length() &&
          may_change[idx] &&
          old_funcs[idx] != new_funcs[idx],
        )
      }
      changed
    }
    _ => []
  }
}

///|
fn mp_drop_touched_label_names(
  label_names : @lib.IndirectNameMap?,
  imported_funcs : Int32,
  changed_defined_funcs : Array[Bool],
) -> @lib.IndirectNameMap? {
  let entries = match label_names {
    Some(@lib.IndirectNameMap(entries)) => entries
    None => return None
  }
  let kept : Array[@lib.IndirectNameAssoc] = []
  for entry in entries {
    let @lib.IndirectNameAssoc(raw_func_idx, _) = entry
    let defined_idx = raw_func_idx.reinterpret_as_int() - imported_funcs
    if defined_idx < 0 ||
      defined_idx >= changed_defined_funcs.length() ||
      !changed_defined_funcs[defined_idx] {
      kept.push(entry)
    }
  }
  if kept.is_empty() {
    None
  } else {
    Some(@lib.IndirectNameMap::new(kept))
  }
}

///|
fn mp_suffixed_data_name(name : @lib.Name, suffix : Int32) -> @lib.Name {
  @lib.Name::from_string(mp_name_to_string(name) + "." + suffix.to_string())
}

///|
fn mp_append_data_name_entries(
  entries : Array[@lib.NameAssoc],
  name : @lib.Name?,
  first_new_idx : Int32,
  count : Int32,
) -> Unit {
  match name {
    Some(name) =>
      for suffix = 0; suffix < count; suffix = suffix + 1 {
        let next_name = if suffix == 0 {
          name
        } else {
          mp_suffixed_data_name(name, suffix)
        }
        entries.push(
          @lib.NameAssoc::new(
            (first_new_idx + suffix).reinterpret_as_uint(),
            next_name,
          ),
        )
      }
    None => ()
  }
}

///|
fn mp_rewrite_name_sec(
  name_sec : @lib.NameSec?,
  data_name_entries : Array[@lib.NameAssoc],
  imported_funcs : Int32,
  changed_defined_funcs : Array[Bool],
) -> @lib.NameSec? {
  match name_sec {
    Some(sec) => {
      let {
        module_name,
        func_names,
        local_names,
        label_names,
        type_names,
        table_names,
        memory_names,
        global_names,
        elem_names,
        data_names: _data_names,
        field_names,
        tag_names,
      } = sec
      let next = @lib.NameSec::new(
        module_name~,
        func_names~,
        local_names~,
        label_names=mp_drop_touched_label_names(
          label_names, imported_funcs, changed_defined_funcs,
        ),
        type_names~,
        table_names~,
        memory_names~,
        global_names~,
        elem_names~,
        data_names=mp_name_map_from_entries(data_name_entries),
        field_names~,
        tag_names~,
      )
      if next.module_name is None &&
        next.func_names is None &&
        next.local_names is None &&
        next.label_names is None &&
        next.type_names is None &&
        next.table_names is None &&
        next.memory_names is None &&
        next.global_names is None &&
        next.elem_names is None &&
        next.data_names is None &&
        next.field_names is None &&
        next.tag_names is None {
        None
      } else {
        Some(next)
      }
    }
    None => None
  }
}

///|
fn mp_plan_data_idx(
  idx : @lib.DataIdx,
  plans : Array[MpSegmentPlan],
) -> @lib.DataIdx {
  let slot = mp_data_idx_slot(idx)
  if slot < 0 || slot >= plans.length() {
    return idx
  }
  let next = plans[slot].remap
  if next < 0 {
    return idx
  }
  @lib.DataIdx::new(next.reinterpret_as_uint())
}

///|
fn mp_data_idx_from_int(idx : Int32) -> @lib.DataIdx {
  @lib.DataIdx::new(idx.reinterpret_as_uint())
}

///|
fn mp_local_idx_from_int(idx : Int32) -> @lib.LocalIdx {
  @lib.LocalIdx::new(idx.reinterpret_as_uint())
}

///|
fn mp_i32_const(value : Int32) -> @lib.Instruction {
  @lib.Instruction::i32_const(@lib.I32(value))
}

///|
fn mp_append_dest_with_delta(
  out : Array[@lib.Instruction],
  dest : @lib.Instruction,
  delta : Int32,
  tmp : @lib.LocalIdx?,
  address_type : MpMemoryAddressType,
) -> Unit {
  match tmp {
    Some(tmp_local) => out.push(@lib.Instruction::local_get(tmp_local))
    None =>
      match (address_type, dest) {
        (I32Address, @lib.I32Const(@lib.I32(value))) => {
          out.push(mp_i32_const(value + delta))
          return
        }
        (I64Address, @lib.I64Const(@lib.I64(value))) => {
          out.push(
            @lib.Instruction::i64_const(@lib.I64(value + delta.to_int64())),
          )
          return
        }
        _ => out.push(dest)
      }
  }
  if delta != 0 {
    out.push(mp_address_const(address_type, delta))
    mp_append_address_add(out, address_type)
  }
}

///|
fn mp_emit_drop_state_check(
  out : Array[@lib.Instruction],
  global_idx : @lib.GlobalIdx,
) -> Unit {
  out.push(@lib.Instruction::global_get(global_idx))
  out.push(
    @lib.Instruction::if_(
      @lib.BlockType::void_(),
      [@lib.Instruction::unreachable_()],
      None,
    ),
  )
}

///|
fn mp_emit_memory_fill(
  out : Array[@lib.Instruction],
  dest : @lib.Instruction,
  src_start : Int32,
  fill_start : Int32,
  fill_end : Int32,
  mem_idx : @lib.MemIdx,
  tmp : @lib.LocalIdx?,
  address_type : MpMemoryAddressType,
) -> Unit {
  let len = fill_end - fill_start
  if len <= 0 {
    return
  }
  mp_append_dest_with_delta(
    out,
    dest,
    fill_start - src_start,
    tmp,
    address_type,
  )
  out.push(mp_i32_const(0))
  out.push(mp_address_const(address_type, len))
  out.push(@lib.Instruction::memory_fill(mem_idx))
}

///|
fn mp_emit_memory_init_part(
  out : Array[@lib.Instruction],
  dest : @lib.Instruction,
  src_start : Int32,
  copy_start : Int32,
  copy_end : Int32,
  part : MpSplitPart,
  mem_idx : @lib.MemIdx,
  tmp : @lib.LocalIdx?,
  address_type : MpMemoryAddressType,
) -> Unit {
  let len = copy_end - copy_start
  if len <= 0 {
    return
  }
  mp_append_dest_with_delta(
    out,
    dest,
    copy_start - src_start,
    tmp,
    address_type,
  )
  out.push(mp_i32_const(copy_start - part.start))
  out.push(mp_i32_const(len))
  out.push(
    @lib.Instruction::memory_init(mp_data_idx_from_int(part.data_idx), mem_idx),
  )
}

///|
fn mp_plan_drop_global(
  plan : MpSegmentPlan,
  base : @lib.GlobalIdx?,
) -> @lib.GlobalIdx? {
  if !plan.needs_drop_state {
    return None
  }
  match base {
    Some(@lib.GlobalIdx(idx)) =>
      Some(@lib.GlobalIdx::new(idx + plan.drop_state_offset.to_uint()))
    None => None
  }
}

///|
// Compare pages plus the rounded-up intra-page end, never a wrapped byte size.
// low(dest) + size + 65535 fits unsigned i32 because source sizes fit Int.
fn mp_emit_destination_preflight(
  out : Array[@lib.Instruction],
  dest : @lib.Instruction,
  size : Int32,
  mem_idx : @lib.MemIdx,
  tmp : @lib.LocalIdx?,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> Unit {
  let constant_offset = match (tmp, dest) {
    (None, @lib.I32Const(@lib.I32(value))) =>
      Some(value.reinterpret_as_uint().to_uint64())
    (None, @lib.I64Const(@lib.I64(value))) =>
      Some(value.reinterpret_as_uint64())
    _ => None
  }
  if constant_offset is Some(offset) {
    let end_ = offset + size.to_uint64()
    // An endpoint of exactly 2^64 is valid only for a full Memory64 memory.
    // Any larger mathematical endpoint must trap, never wrap into low memory.
    if end_ < offset && end_ != 0UL {
      out.push(@lib.Instruction::unreachable_())
      return
    }
    let pages = if end_ < offset {
      1UL << 48
    } else {
      (end_ >> 16) + (if (end_ & 65535UL) == 0UL { 0UL } else { 1UL })
    }
    // Memory can grow but cannot shrink below its declared minimum.
    if pages <= initial_pages {
      return
    }
    match address_type {
      I32Address => out.push(mp_i32_const(pages.to_int()))
      I64Address =>
        out.push(
          @lib.Instruction::i64_const(@lib.I64(pages.reinterpret_as_int64())),
        )
    }
    out.push(@lib.Instruction::memory_size(mem_idx))
    mp_append_address_gt_u(out, address_type)
    out.push(
      @lib.Instruction::if_(
        @lib.BlockType::void_(),
        [@lib.Instruction::unreachable_()],
        None,
      ),
    )
    return
  }
  fn append_dest() -> Unit {
    match tmp {
      Some(idx) => out.push(@lib.Instruction::local_get(idx))
      None => out.push(dest)
    }
  }
  fn append_page() -> Unit {
    append_dest()
    out.push(mp_address_const(address_type, 16))
    match address_type {
      I32Address => out.push(@lib.Instruction::i32_shr_u())
      I64Address => out.push(@lib.Instruction::i64_shr_u())
    }
  }
  fn trap_if() -> Unit {
    out.push(
      @lib.Instruction::if_(
        @lib.BlockType::void_(),
        [@lib.Instruction::unreachable_()],
        None,
      ),
    )
  }
  append_page()
  out.push(@lib.Instruction::memory_size(mem_idx))
  mp_append_address_gt_u(out, address_type)
  trap_if()
  append_dest()
  out.push(mp_address_const(address_type, 65535))
  match address_type {
    I32Address => out.push(@lib.Instruction::i32_and())
    I64Address => out.push(@lib.Instruction::i64_and())
  }
  out.push(mp_address_const(address_type, size))
  mp_append_address_add(out, address_type)
  out.push(mp_address_const(address_type, 65535))
  mp_append_address_add(out, address_type)
  out.push(mp_address_const(address_type, 16))
  match address_type {
    I32Address => out.push(@lib.Instruction::i32_shr_u())
    I64Address => out.push(@lib.Instruction::i64_shr_u())
  }
  out.push(@lib.Instruction::memory_size(mem_idx))
  append_page()
  match address_type {
    I32Address => out.push(@lib.Instruction::i32_sub())
    I64Address => out.push(@lib.Instruction::i64_sub())
  }
  mp_append_address_gt_u(out, address_type)
  trap_if()
}

///|
fn mp_append_passive_memory_init_replacement(
  out : Array[@lib.Instruction],
  plan : MpSegmentPlan,
  dest : @lib.Instruction,
  src_start : Int32,
  size : Int32,
  mem_idx : @lib.MemIdx,
  tmp : @lib.LocalIdx?,
  global_idx : @lib.GlobalIdx?,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> Unit {
  if src_start != 0 || size != 0 {
    match global_idx {
      Some(gi) => mp_emit_drop_state_check(out, gi)
      None => {
        // Every retained part shares the original segment's drop lifetime.
        // A leading nonempty copy checks it before its first write. Otherwise
        // probe one-past-zero with length zero: valid live, trapping dropped,
        // and never a memory mutation (even when memory has zero pages).
        let starts_with_copy = size > 0 &&
          plan.split_parts.any(part => {
            part.start <= src_start && src_start < part.end_
          })
        if !starts_with_copy && !plan.split_parts.is_empty() {
          out.push(mp_address_const(address_type, 0))
          out.push(mp_i32_const(1))
          out.push(mp_i32_const(0))
          out.push(
            @lib.Instruction::memory_init(
              mp_data_idx_from_int(plan.split_parts[0].data_idx),
              mem_idx,
            ),
          )
        }
      }
    }
  }
  mp_emit_destination_preflight(
    out,
    dest,
    size,
    mem_idx,
    tmp,
    address_type,
    initial_pages~,
  )
  if size <= 0 {
    out.push(@lib.Instruction::nop())
    return
  }
  let src_end = src_start + size
  let mut cursor = src_start
  let mut emitted = false
  for part in plan.split_parts {
    if part.end_ <= src_start {
      continue
    }
    if part.start >= src_end {
      break
    }
    let fill_end = if part.start < src_end { part.start } else { src_end }
    if cursor < fill_end {
      mp_emit_memory_fill(
        out, dest, src_start, cursor, fill_end, mem_idx, tmp, address_type,
      )
      emitted = true
      cursor = fill_end
    }
    let copy_start = if cursor > part.start { cursor } else { part.start }
    let copy_end = if part.end_ < src_end { part.end_ } else { src_end }
    if copy_start < copy_end {
      mp_emit_memory_init_part(
        out, dest, src_start, copy_start, copy_end, part, mem_idx, tmp, address_type,
      )
      emitted = true
      cursor = copy_end
    }
  }
  if cursor < src_end {
    mp_emit_memory_fill(
      out, dest, src_start, cursor, src_end, mem_idx, tmp, address_type,
    )
    emitted = true
  }
  if !emitted {
    out.push(@lib.Instruction::nop())
  }
}

///|
priv struct MpMemoryInitOperands {
  dest_instrs : Array[@lib.Instruction]
  src_instr : @lib.Instruction
  size_instr : @lib.Instruction
}

///|
fn MpMemoryInitOperands::new(
  dest_instrs : Array[@lib.Instruction],
  src_instr : @lib.Instruction,
  size_instr : @lib.Instruction,
) -> MpMemoryInitOperands {
  { dest_instrs, src_instr, size_instr, }
}

///|
fn mp_block_type_result_count(block_type : @lib.BlockType) -> Int32? {
  match block_type {
    @lib.VoidBlockType => Some(0)
    @lib.ValTypeBlockType(_) => Some(1)
    @lib.TypeIdxBlockType(_) => None
  }
}

///|
fn mp_instr_stack_counts(instr : @lib.Instruction) -> (Int32, Int32)? {
  match instr {
    @lib.Nop => Some((0, 0))
    @lib.Unreachable => Some((0, 1))
    @lib.Block(block_type, _)
    | @lib.Loop(block_type, _)
    | @lib.Try(block_type, _, _, _)
    | @lib.TryTable(block_type, _, _) =>
      match mp_block_type_result_count(block_type) {
        Some(results) => Some((0, results))
        None => None
      }
    @lib.If(block_type, _, _) =>
      match mp_block_type_result_count(block_type) {
        Some(results) => Some((1, results))
        None => None
      }
    @lib.Drop => Some((1, 0))
    @lib.Select(_) => Some((3, 1))
    @lib.LocalGet(_)
    | @lib.GlobalGet(_)
    | @lib.MemorySize(_)
    | @lib.RefNull(_)
    | @lib.RefFunc(_)
    | @lib.StringConst(_)
    | @lib.I32Const(_)
    | @lib.I64Const(_)
    | @lib.F32Const(_)
    | @lib.F64Const(_)
    | @lib.V128Const(_, _, _, _, _, _, _, _, _, _, _, _, _, _, _, _) =>
      Some((0, 1))
    @lib.LocalSet(_) | @lib.GlobalSet(_) | @lib.BrIf(_) | @lib.BrOnNonNull(_) =>
      Some((1, 0))
    @lib.BrOnNull(_) => Some((1, 1))
    @lib.TableSet(_) => Some((2, 0))
    @lib.LocalTee(_)
    | @lib.MemoryGrow(_)
    | @lib.TableGet(_)
    | @lib.RefIsNull
    | @lib.RefAsNonNull
    | @lib.AnyConvertExtern
    | @lib.ExternConvertAny
    | @lib.RefI31
    | @lib.I31GetS
    | @lib.I31GetU
    | @lib.I32Eqz
    | @lib.I64Eqz
    | @lib.I32Clz
    | @lib.I32Ctz
    | @lib.I32Popcnt
    | @lib.I64Clz
    | @lib.I64Ctz
    | @lib.I64Popcnt
    | @lib.F32Abs
    | @lib.F32Neg
    | @lib.F32Ceil
    | @lib.F32Floor
    | @lib.F32Trunc
    | @lib.F32Nearest
    | @lib.F32Sqrt
    | @lib.F64Abs
    | @lib.F64Neg
    | @lib.F64Ceil
    | @lib.F64Floor
    | @lib.F64Trunc
    | @lib.F64Nearest
    | @lib.F64Sqrt
    | @lib.I32WrapI64
    | @lib.I32TruncF32S
    | @lib.I32TruncF32U
    | @lib.I32TruncF64S
    | @lib.I32TruncF64U
    | @lib.I64ExtendI32S
    | @lib.I64ExtendI32U
    | @lib.I64TruncF32S
    | @lib.I64TruncF32U
    | @lib.I64TruncF64S
    | @lib.I64TruncF64U
    | @lib.F32ConvertI32S
    | @lib.F32ConvertI32U
    | @lib.F32ConvertI64S
    | @lib.F32ConvertI64U
    | @lib.F32DemoteF64
    | @lib.F64ConvertI32S
    | @lib.F64ConvertI32U
    | @lib.F64ConvertI64S
    | @lib.F64ConvertI64U
    | @lib.F64PromoteF32
    | @lib.I32ReinterpretF32
    | @lib.I64ReinterpretF64
    | @lib.F32ReinterpretI32
    | @lib.F64ReinterpretI64
    | @lib.I32Extend8S
    | @lib.I32Extend16S
    | @lib.I64Extend8S
    | @lib.I64Extend16S
    | @lib.I64Extend32S
    | @lib.RefTest(_, _, _)
    | @lib.RefTestDesc(_, _)
    | @lib.RefCast(_, _, _)
    | @lib.I32TruncSatF32S
    | @lib.I32TruncSatF32U
    | @lib.I32TruncSatF64S
    | @lib.I32TruncSatF64U
    | @lib.I64TruncSatF32S
    | @lib.I64TruncSatF32U
    | @lib.I64TruncSatF64S
    | @lib.I64TruncSatF64U
    | @lib.I8x16Splat
    | @lib.I16x8Splat
    | @lib.I32x4Splat
    | @lib.I64x2Splat
    | @lib.F32x4Splat
    | @lib.F64x2Splat => Some((1, 1))
    @lib.I32Load(_)
    | @lib.I64Load(_)
    | @lib.F32Load(_)
    | @lib.F64Load(_)
    | @lib.I32Load8S(_)
    | @lib.I32Load8U(_)
    | @lib.I32Load16S(_)
    | @lib.I32Load16U(_)
    | @lib.I64Load8S(_)
    | @lib.I64Load8U(_)
    | @lib.I64Load16S(_)
    | @lib.I64Load16U(_)
    | @lib.I64Load32S(_)
    | @lib.I64Load32U(_)
    | @lib.I32AtomicLoad(_, _)
    | @lib.I64AtomicLoad(_, _)
    | @lib.I32AtomicLoad8U(_, _)
    | @lib.I32AtomicLoad16U(_, _)
    | @lib.I64AtomicLoad8U(_, _)
    | @lib.I64AtomicLoad16U(_, _)
    | @lib.I64AtomicLoad32U(_, _)
    | @lib.V128Load(_)
    | @lib.V128Load8x8S(_)
    | @lib.V128Load8x8U(_)
    | @lib.V128Load16x4S(_)
    | @lib.V128Load16x4U(_)
    | @lib.V128Load32x2S(_)
    | @lib.V128Load32x2U(_)
    | @lib.V128Load8Splat(_)
    | @lib.V128Load16Splat(_)
    | @lib.V128Load32Splat(_)
    | @lib.V128Load64Splat(_) => Some((1, 1))
    @lib.I32Eq
    | @lib.I32Ne
    | @lib.I32LtS
    | @lib.I32LtU
    | @lib.I32GtS
    | @lib.I32GtU
    | @lib.I32LeS
    | @lib.I32LeU
    | @lib.I32GeS
    | @lib.I32GeU
    | @lib.I64Eq
    | @lib.I64Ne
    | @lib.I64LtS
    | @lib.I64LtU
    | @lib.I64GtS
    | @lib.I64GtU
    | @lib.I64LeS
    | @lib.I64LeU
    | @lib.I64GeS
    | @lib.I64GeU
    | @lib.F32Eq
    | @lib.F32Ne
    | @lib.F32Lt
    | @lib.F32Gt
    | @lib.F32Le
    | @lib.F32Ge
    | @lib.F64Eq
    | @lib.F64Ne
    | @lib.F64Lt
    | @lib.F64Gt
    | @lib.F64Le
    | @lib.F64Ge
    | @lib.I32Add
    | @lib.I32Sub
    | @lib.I32Mul
    | @lib.I32DivS
    | @lib.I32DivU
    | @lib.I32RemS
    | @lib.I32RemU
    | @lib.I32And
    | @lib.I32Or
    | @lib.I32Xor
    | @lib.I32Shl
    | @lib.I32ShrS
    | @lib.I32ShrU
    | @lib.I32Rotl
    | @lib.I32Rotr
    | @lib.I64Add
    | @lib.I64Sub
    | @lib.I64Mul
    | @lib.I64DivS
    | @lib.I64DivU
    | @lib.I64RemS
    | @lib.I64RemU
    | @lib.I64And
    | @lib.I64Or
    | @lib.I64Xor
    | @lib.I64Shl
    | @lib.I64ShrS
    | @lib.I64ShrU
    | @lib.I64Rotl
    | @lib.I64Rotr
    | @lib.F32Add
    | @lib.F32Sub
    | @lib.F32Mul
    | @lib.F32Div
    | @lib.F32Min
    | @lib.F32Max
    | @lib.F32Copysign
    | @lib.F64Add
    | @lib.F64Sub
    | @lib.F64Mul
    | @lib.F64Div
    | @lib.F64Min
    | @lib.F64Max
    | @lib.F64Copysign
    | @lib.RefEq
    | @lib.RefCastDescEq(_, _, _) => Some((2, 1))
    @lib.I32Store(_)
    | @lib.I64Store(_)
    | @lib.F32Store(_)
    | @lib.F64Store(_)
    | @lib.I32Store8(_)
    | @lib.I32Store16(_)
    | @lib.I64Store8(_)
    | @lib.I64Store16(_)
    | @lib.I64Store32(_)
    | @lib.I32AtomicStore(_, _)
    | @lib.I64AtomicStore(_, _)
    | @lib.I32AtomicStore8(_, _)
    | @lib.I32AtomicStore16(_, _)
    | @lib.I64AtomicStore8(_, _)
    | @lib.I64AtomicStore16(_, _)
    | @lib.I64AtomicStore32(_, _)
    | @lib.V128Store(_) => Some((2, 0))
    @lib.MemoryFill(_)
    | @lib.MemoryInit(_, _)
    | @lib.ArrayFill(_)
    | @lib.ArrayInitData(_, _)
    | @lib.ArrayInitElem(_, _) => Some((3, 0))
    @lib.MemoryCopy(_, _) | @lib.TableCopy(_, _) => Some((3, 0))
    @lib.ArrayCopy(_, _) => Some((5, 0))
    @lib.DataDrop(_) | @lib.ElemDrop(_) | @lib.AtomicFence(_) => Some((0, 0))
    _ => None
  }
}

///|
fn mp_find_value_start(out : Array[@lib.Instruction], end_ : Int32) -> Int32? {
  let mut need = 1
  let mut idx = end_ - 1
  while idx >= 0 {
    let counts = match mp_instr_stack_counts(out[idx]) {
      Some(counts) => counts
      None => return None
    }
    let (params, results) = counts
    if results > need {
      return None
    }
    need = need - results + params
    if need == 0 {
      return Some(idx)
    }
    idx = idx - 1
  }
  None
}

///|
priv struct MpSegmentOpPreflight {
  mut rewritable : Bool
  mut has_data_ops : Bool
  func_has_data_ops : Array[Bool]
}

///|
fn MpSegmentOpPreflight::new(
  rewritable~ : Bool = true,
  has_data_ops~ : Bool = false,
) -> MpSegmentOpPreflight {
  { rewritable, has_data_ops, func_has_data_ops: [], }
}

///|
fn mp_segment_op_preflight_instrs(
  instrs : Array[@lib.Instruction],
  result : MpSegmentOpPreflight,
) -> Unit {
  for i = 0; i < instrs.length(); i = i + 1 {
    match instrs[i] {
      @lib.MemoryInit(_, _) => {
        result.has_data_ops = true
        if i < 2 ||
          mp_instr_i32_const_value(instrs[i - 2]) is None ||
          mp_instr_i32_const_value(instrs[i - 1]) is None ||
          mp_find_value_start(instrs, i - 2) is None {
          result.rewritable = false
          return
        }
      }
      @lib.DataDrop(_) | @lib.ArrayNewData(_, _) | @lib.ArrayInitData(_, _) =>
        result.has_data_ops = true
      @lib.Block(_, @lib.Expr(body))
      | @lib.Loop(_, @lib.Expr(body))
      | @lib.TryTable(_, _, @lib.Expr(body)) => {
        mp_segment_op_preflight_instrs(body, result)
        if !result.rewritable {
          return
        }
      }
      @lib.Try(_, @lib.Expr(body), catches, _) => {
        mp_segment_op_preflight_instrs(body, result)
        if !result.rewritable {
          return
        }
        for catch_ in catches {
          let catch_body = match catch_ {
            @lib.LegacyCatch(_, @lib.Expr(catch_body))
            | @lib.LegacyCatchAll(@lib.Expr(catch_body)) => catch_body
          }
          mp_segment_op_preflight_instrs(catch_body, result)
          if !result.rewritable {
            return
          }
        }
      }
      @lib.If(_, then_body, else_body) => {
        mp_segment_op_preflight_instrs(then_body, result)
        if !result.rewritable {
          return
        }
        match else_body {
          Some(body) => {
            mp_segment_op_preflight_instrs(body, result)
            if !result.rewritable {
              return
            }
          }
          None => ()
        }
      }
      _ => ()
    }
  }
}

///|
fn mp_module_segment_op_preflight(mod_ : @lib.Module) -> MpSegmentOpPreflight {
  let result = MpSegmentOpPreflight::new()
  match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) =>
      for func_ in funcs {
        let @lib.Func(_, @lib.Expr(body)) = func_
        let earlier_has_data_ops = result.has_data_ops
        result.has_data_ops = false
        mp_segment_op_preflight_instrs(body, result)
        let func_has_data_ops = result.has_data_ops
        result.func_has_data_ops.push(func_has_data_ops)
        result.has_data_ops = earlier_has_data_ops || func_has_data_ops
        if !result.rewritable {
          return result
        }
      }
    None => ()
  }
  result
}

///|
fn mp_pop_three_operands(
  out : Array[@lib.Instruction],
) -> MpMemoryInitOperands? {
  if out.length() < 3 {
    return None
  }
  let len = out.length()
  let src_instr = out[len - 2]
  let size_instr = out[len - 1]
  match
    (mp_instr_i32_const_value(src_instr), mp_instr_i32_const_value(size_instr)) {
    (Some(_), Some(_)) => ()
    _ => return None
  }
  let dest_start = match mp_find_value_start(out, len - 2) {
    Some(start) => start
    None => return None
  }
  let dest_instrs : Array[@lib.Instruction] = []
  for idx = dest_start; idx < len - 2; idx = idx + 1 {
    dest_instrs.push(out[idx])
  }
  while out.length() > dest_start {
    ignore(out.pop())
  }
  Some(MpMemoryInitOperands::new(dest_instrs, src_instr, size_instr))
}

///|
fn mp_append_memory_init_operand_eval(
  out : Array[@lib.Instruction],
  instrs : Array[@lib.Instruction],
) -> Unit {
  for instr in instrs {
    out.push(instr)
  }
  out.push(@lib.Instruction::drop())
}

///|
fn mp_append_consumed_memory_init_operands(
  out : Array[@lib.Instruction],
  operands : MpMemoryInitOperands,
) -> Unit {
  // Operand extraction admits only constant source and length operands. They
  // have no observable evaluation to preserve before a proven source trap.
  // Keep every dynamic destination operation, including its effects and traps.
  match operands.dest_instrs {
    [@lib.I32Const(_)] | [@lib.I64Const(_)] => ()
    _ => mp_append_memory_init_operand_eval(out, operands.dest_instrs)
  }
}

///|
fn mp_memory_init_dest_is_const(
  operands : MpMemoryInitOperands,
  address_type : MpMemoryAddressType,
) -> @lib.Instruction? {
  match operands.dest_instrs {
    [instr] =>
      match (address_type, instr) {
        (I32Address, @lib.I32Const(_)) | (I64Address, @lib.I64Const(_)) =>
          Some(instr)
        _ => None
      }
    _ => None
  }
}

///|
fn mp_memory_init_source_range_is_valid(
  src : Int32,
  size : Int32,
  runtime_size : Int32,
) -> Bool {
  if src < 0 || size < 0 {
    return false
  }
  let src_u = src.reinterpret_as_uint().to_uint64()
  let size_u = size.reinterpret_as_uint().to_uint64()
  let end_ = src_u + size_u
  end_ >= src_u && end_ <= runtime_size.reinterpret_as_uint().to_uint64()
}

///|
fn mp_memory_init_dest_is_trap_only(operands : MpMemoryInitOperands) -> Bool {
  let mut has_unreachable = false
  for instr in operands.dest_instrs {
    match instr {
      @lib.Unreachable => has_unreachable = true
      @lib.Drop | @lib.Nop => ()
      _ => return false
    }
  }
  has_unreachable
}

///|
fn mp_append_memory_init_dest(
  out : Array[@lib.Instruction],
  operands : MpMemoryInitOperands,
) -> Unit {
  for instr in operands.dest_instrs {
    out.push(instr)
  }
}

///|
fn mp_rewrite_active_memory_init(
  out : Array[@lib.Instruction],
  locals : @lib.Locals,
  param_count : Int32,
  mem_idx : @lib.MemIdx,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> Bool {
  let operands = match mp_pop_three_operands(out) {
    Some(operands) => operands
    None => return false
  }
  let src = match mp_instr_i32_const_value(operands.src_instr) {
    Some(value) => value
    None => abort("expected constant memory.init source operand")
  }
  let size = match mp_instr_i32_const_value(operands.size_instr) {
    Some(value) => value
    None => abort("expected constant memory.init size operand")
  }
  if mp_memory_init_dest_is_trap_only(operands) {
    out.push(@lib.Instruction::unreachable_())
    return true
  }
  // Instantiation drops active segments, independently of initialization bytes.
  if !mp_memory_init_source_range_is_valid(src, size, 0) {
    mp_append_consumed_memory_init_operands(out, operands)
    out.push(@lib.Instruction::unreachable_())
    return true
  }
  if mp_memory_init_dest_is_const(operands, address_type) is Some(dest) {
    mp_emit_destination_preflight(
      out,
      dest,
      0,
      mem_idx,
      None,
      address_type,
      initial_pages~,
    )
    return true
  }
  let tmp = mp_local_idx_from_int(param_count + locals.length())
  locals.push(mp_address_val_type(address_type))
  mp_append_memory_init_dest(out, operands)
  out.push(@lib.Instruction::local_set(tmp))
  mp_emit_destination_preflight(
    out,
    mp_address_const(address_type, 0),
    0,
    mem_idx,
    Some(tmp),
    address_type,
    initial_pages~,
  )
  true
}

///|
fn mp_rewrite_passive_split_memory_init(
  out : Array[@lib.Instruction],
  plan : MpSegmentPlan,
  locals : @lib.Locals,
  param_count : Int32,
  mem_idx : @lib.MemIdx,
  global_idx : @lib.GlobalIdx?,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> Bool {
  let operands = match mp_pop_three_operands(out) {
    Some(operands) => operands
    None => return false
  }
  let src = match mp_instr_i32_const_value(operands.src_instr) {
    Some(value) => value
    None => abort("expected constant memory.init source operand")
  }
  let size = match mp_instr_i32_const_value(operands.size_instr) {
    Some(value) => value
    None => abort("expected constant memory.init size operand")
  }
  if mp_memory_init_dest_is_trap_only(operands) {
    out.push(@lib.Instruction::unreachable_())
    return true
  }
  if !mp_memory_init_source_range_is_valid(src, size, plan.runtime_size) {
    mp_append_consumed_memory_init_operands(out, operands)
    out.push(@lib.Instruction::unreachable_())
    return true
  }
  let const_dest = mp_memory_init_dest_is_const(operands, address_type)
  let dest = match const_dest {
    Some(instr) => instr
    None => mp_address_const(address_type, 0)
  }
  let tmp = match const_dest {
    Some(_) => None
    None => {
      let tmp_local = mp_local_idx_from_int(param_count + locals.length())
      locals.push(mp_address_val_type(address_type))
      mp_append_memory_init_dest(out, operands)
      out.push(@lib.Instruction::local_set(tmp_local))
      Some(tmp_local)
    }
  }
  let effective_global = mp_plan_drop_global(plan, global_idx)
  mp_append_passive_memory_init_replacement(
    out,
    plan,
    dest,
    src,
    size,
    mem_idx,
    tmp,
    effective_global,
    address_type,
    initial_pages~,
  )
  true
}

///|
fn mp_append_split_data_drop(
  out : Array[@lib.Instruction],
  plan : MpSegmentPlan,
  global_idx : @lib.GlobalIdx?,
) -> Unit {
  let global_idx = mp_plan_drop_global(plan, global_idx)
  if plan.needs_drop_state {
    match global_idx {
      Some(gi) => {
        out.push(mp_i32_const(1))
        out.push(@lib.Instruction::global_set(gi))
      }
      None => ()
    }
  }
  if plan.split_parts.is_empty() {
    out.push(@lib.Instruction::nop())
    return
  }
  for part in plan.split_parts {
    out.push(@lib.Instruction::data_drop(mp_data_idx_from_int(part.data_idx)))
  }
}

///|
fn mp_rewrite_instrs_full(
  instrs : Array[@lib.Instruction],
  plans : Array[MpSegmentPlan],
  locals : @lib.Locals,
  param_count : Int32,
  global_idx : @lib.GlobalIdx?,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> Array[@lib.Instruction] {
  let out : Array[@lib.Instruction] = []
  for instr in instrs {
    match instr {
      @lib.Block(block_type, body) =>
        out.push(
          @lib.Instruction::block(
            block_type,
            mp_rewrite_expr_full(
              body,
              plans,
              locals,
              param_count,
              global_idx,
              address_type,
              initial_pages~,
            ),
          ),
        )
      @lib.Loop(block_type, body) =>
        out.push(
          @lib.Instruction::loop_(
            block_type,
            mp_rewrite_expr_full(
              body,
              plans,
              locals,
              param_count,
              global_idx,
              address_type,
              initial_pages~,
            ),
          ),
        )
      @lib.Try(block_type, body, catches, delegate) => {
        let rewritten_catches : Array[@lib.LegacyCatch] = []
        for catch_ in catches {
          match catch_ {
            @lib.LegacyCatch(tag_idx, catch_body) =>
              rewritten_catches.push(
                @lib.LegacyCatch::tagged(
                  tag_idx,
                  mp_rewrite_expr_full(
                    catch_body,
                    plans,
                    locals,
                    param_count,
                    global_idx,
                    address_type,
                    initial_pages~,
                  ),
                ),
              )
            @lib.LegacyCatchAll(catch_body) =>
              rewritten_catches.push(
                @lib.LegacyCatch::all(
                  mp_rewrite_expr_full(
                    catch_body,
                    plans,
                    locals,
                    param_count,
                    global_idx,
                    address_type,
                    initial_pages~,
                  ),
                ),
              )
          }
        }
        out.push(
          @lib.Instruction::try_(
            block_type,
            mp_rewrite_expr_full(
              body,
              plans,
              locals,
              param_count,
              global_idx,
              address_type,
              initial_pages~,
            ),
            rewritten_catches,
            delegate~,
          ),
        )
      }
      @lib.TryTable(block_type, catches, body) =>
        out.push(
          @lib.Instruction::try_table(
            block_type,
            catches,
            mp_rewrite_expr_full(
              body,
              plans,
              locals,
              param_count,
              global_idx,
              address_type,
              initial_pages~,
            ),
          ),
        )
      @lib.If(block_type, then_body, else_body) => {
        let rewritten_then = mp_rewrite_instrs_full(
          then_body,
          plans,
          locals,
          param_count,
          global_idx,
          address_type,
          initial_pages~,
        )
        let rewritten_else = match else_body {
          Some(body) =>
            Some(
              mp_rewrite_instrs_full(
                body,
                plans,
                locals,
                param_count,
                global_idx,
                address_type,
                initial_pages~,
              ),
            )
          None => None
        }
        out.push(
          @lib.Instruction::if_(block_type, rewritten_then, rewritten_else),
        )
      }
      @lib.ArrayNewData(type_idx, idx) =>
        out.push(
          @lib.Instruction::array_new_data(
            type_idx,
            mp_plan_data_idx(idx, plans),
          ),
        )
      @lib.ArrayInitData(type_idx, idx) =>
        out.push(
          @lib.Instruction::array_init_data(
            type_idx,
            mp_plan_data_idx(idx, plans),
          ),
        )
      @lib.MemoryInit(idx, mem_idx) => {
        let slot = mp_data_idx_slot(idx)
        if slot >= 0 && slot < plans.length() {
          let plan = plans[slot]
          if plan.is_active {
            if !mp_rewrite_active_memory_init(
                out,
                locals,
                param_count,
                mem_idx,
                address_type,
                initial_pages~,
              ) {
              out.push(
                @lib.Instruction::memory_init(
                  mp_plan_data_idx(idx, plans),
                  mem_idx,
                ),
              )
            }
          } else if plan.was_split {
            if !mp_rewrite_passive_split_memory_init(
                out,
                plan,
                locals,
                param_count,
                mem_idx,
                global_idx,
                address_type,
                initial_pages~,
              ) {
              out.push(
                @lib.Instruction::memory_init(
                  mp_plan_data_idx(idx, plans),
                  mem_idx,
                ),
              )
            }
          } else {
            out.push(
              @lib.Instruction::memory_init(
                mp_plan_data_idx(idx, plans),
                mem_idx,
              ),
            )
          }
        } else {
          out.push(instr)
        }
      }
      @lib.DataDrop(idx) => {
        let slot = mp_data_idx_slot(idx)
        if slot >= 0 && slot < plans.length() {
          let plan = plans[slot]
          if plan.is_active || (plan.remap < 0 && !plan.was_split) {
            out.push(@lib.Instruction::nop())
          } else if plan.was_split {
            mp_append_split_data_drop(out, plan, global_idx)
          } else {
            out.push(@lib.Instruction::data_drop(mp_plan_data_idx(idx, plans)))
          }
        } else {
          out.push(instr)
        }
      }
      _ => out.push(instr)
    }
  }
  out
}

///|
fn mp_rewrite_expr_full(
  expr : @lib.Expr,
  plans : Array[MpSegmentPlan],
  locals : @lib.Locals,
  param_count : Int32,
  global_idx : @lib.GlobalIdx?,
  address_type : MpMemoryAddressType,
  initial_pages~ : UInt64 = 0UL,
) -> @lib.Expr {
  let @lib.Expr(instrs) = expr
  @lib.Expr::new(
    mp_rewrite_instrs_full(
      instrs,
      plans,
      locals,
      param_count,
      global_idx,
      address_type,
      initial_pages~,
    ),
  )
}

///|
fn mp_rewrite_code_sec_full(
  mod_ : @lib.Module,
  plans : Array[MpSegmentPlan],
  global_idx : @lib.GlobalIdx?,
  address_type : MpMemoryAddressType,
  func_has_data_ops : Array[Bool],
  rebuilt_count~ : Array[Int32]? = None,
) -> @lib.CodeSec? {
  let initial_pages = match mp_sole_memory_type(mod_) {
    Some((mem_type, _)) => mp_memory_initial_pages(mem_type)
    None => 0UL
  }
  match mod_.code_sec {
    Some(@lib.CodeSec(funcs)) => {
      let param_counts = mp_defined_func_param_counts(mod_)
      let rewritten : Array[@lib.Func] = []
      for i = 0; i < funcs.length(); i = i + 1 {
        if i < func_has_data_ops.length() && !func_has_data_ops[i] {
          rewritten.push(funcs[i])
          continue
        }
        match rebuilt_count {
          Some(count) => count[0] = count[0] + 1
          None => ()
        }
        let @lib.Func(locals, body) = funcs[i]
        let next_locals = locals.copy()
        let param_count = if i < param_counts.length() {
          param_counts[i]
        } else {
          0
        }
        rewritten.push(
          @lib.Func::new(
            next_locals,
            mp_rewrite_expr_full(
              body,
              plans,
              next_locals,
              param_count,
              global_idx,
              address_type,
              initial_pages~,
            ),
          ),
        )
      }
      Some(@lib.CodeSec::new(rewritten))
    }
    None => None
  }
}

///|
fn mp_should_skip_data_rewrite(name : @lib.Name?) -> Bool {
  mp_data_name_has_prefix(name, "__llvm")
}

///|
pub fn memory_packing_run_module_pass(
  mod_ : @lib.Module,
  traps_never_happen~ : Bool = false,
  zero_filled_memory~ : Bool = false,
) -> @lib.Module {
  if pass_module_has_offset_sensitive_metadata(mod_) {
    return mod_
  }
  let datas = match mod_.data_sec {
    Some(@lib.DataSec(datas)) => datas.copy()
    None => return mod_
  }
  let segment_op_preflight = mp_module_segment_op_preflight(mod_)
  if !segment_op_preflight.rewritable {
    return mod_
  }
  if !mp_can_optimize(mod_, datas, zero_filled_memory) {
    return mod_
  }
  let address_type = match mp_memory_address_type(mod_) {
    Some(address_type) => address_type
    None => return mod_
  }
  let needs_data_usage_scan = mp_needs_data_usage_scan(datas)
  let usages = if needs_data_usage_scan {
    mp_collect_data_usages(mod_, datas.length())
  } else {
    Array::make(datas.length(), MpDataUsage::new(false, false))
  }
  let user_scans = if segment_op_preflight.has_data_ops {
    mp_collect_segment_users(mod_, datas.length())
  } else {
    Array::make(datas.length(), MpPassiveUserScan::new())
  }
  let data_remap = Array::make(datas.length(), -1)
  let plans = Array::make(
    datas.length(),
    MpSegmentPlan::new(-1, [], false, false, false, 0),
  )
  let data_names = mp_data_names_by_idx(mod_, datas.length())
  let rewritten : Array[@lib.Data] = []
  let data_name_entries : Array[@lib.NameAssoc] = []
  let mut changed = false
  let mut need_drop_state = 0

  for idx = 0; idx < datas.length(); idx = idx + 1 {
    let data = datas[idx]
    match data {
      @lib.Data(@lib.Active(mem_idx, expr), bytes) => {
        let next = if mp_should_skip_data_rewrite(data_names[idx]) ||
          (segment_op_preflight.has_data_ops && user_scans[idx].has_array_data) {
          [data]
        } else {
          mp_active_rewrite(mod_, mem_idx, expr, bytes, traps_never_happen)
        }
        let remaining_original_count = datas.length() - idx - 1
        let next = if mp_data_segment_limit_exceeded(
            rewritten.length(),
            next.length(),
            remaining_original_count,
          ) {
          [data]
        } else {
          next
        }
        if next.length() != 1 || next[0] != data {
          changed = true
        }
        let first_new_idx = rewritten.length()
        data_remap[idx] = if next.is_empty() { -1 } else { first_new_idx }
        plans[idx] = MpSegmentPlan::new(
          data_remap[idx],
          [],
          true,
          false,
          false,
          0,
        )
        for item in next {
          rewritten.push(item)
        }
        mp_append_data_name_entries(
          data_name_entries,
          data_names[idx],
          first_new_idx,
          next.length(),
        )
      }
      @lib.Data(@lib.Passive, bytes) => {
        let usage = usages[idx]
        if mp_should_skip_data_rewrite(data_names[idx]) {
          data_remap[idx] = rewritten.length()
          plans[idx] = MpSegmentPlan::new(
            data_remap[idx],
            [],
            false,
            false,
            false,
            bytes.length(),
          )
          rewritten.push(data)
          mp_append_data_name_entries(
            data_name_entries,
            data_names[idx],
            data_remap[idx],
            1,
          )
        } else if !usage.has_non_drop {
          changed = true
          plans[idx] = MpSegmentPlan::new(
            -1,
            [],
            false,
            false,
            false,
            bytes.length(),
          )
        } else if user_scans[idx].has_memory_init &&
          user_scans[idx].all_memory_init_const &&
          !user_scans[idx].has_array_data {
          let (parts, omitted_zero) = mp_passive_split_parts(
            user_scans[idx],
            bytes,
            rewritten.length(),
          )
          if omitted_zero &&
            !mp_data_segment_limit_exceeded(
              rewritten.length(),
              parts.length(),
              datas.length() - idx - 1,
            ) {
            changed = true
            data_remap[idx] = if parts.is_empty() {
              -1
            } else {
              parts[0].data_idx
            }
            plans[idx] = MpSegmentPlan::new(
              data_remap[idx],
              parts,
              false,
              true,
              parts.is_empty() && usage.has_drop,
              bytes.length(),
            )
            if plans[idx].needs_drop_state {
              plans[idx].drop_state_offset = need_drop_state
              need_drop_state += 1
            }
            let first_new_idx = rewritten.length()
            for part in plans[idx].split_parts {
              rewritten.push(
                @lib.Data::new(
                  @lib.DataMode::passive(),
                  mp_slice_bytes(bytes, part.start, part.end_),
                ),
              )
            }
            mp_append_data_name_entries(
              data_name_entries,
              data_names[idx],
              first_new_idx,
              parts.length(),
            )
          } else {
            data_remap[idx] = rewritten.length()
            plans[idx] = MpSegmentPlan::new(
              data_remap[idx],
              [],
              false,
              false,
              false,
              bytes.length(),
            )
            rewritten.push(data)
            mp_append_data_name_entries(
              data_name_entries,
              data_names[idx],
              data_remap[idx],
              1,
            )
          }
        } else {
          data_remap[idx] = rewritten.length()
          plans[idx] = MpSegmentPlan::new(
            data_remap[idx],
            [],
            false,
            false,
            false,
            bytes.length(),
          )
          rewritten.push(data)
          mp_append_data_name_entries(
            data_name_entries,
            data_names[idx],
            data_remap[idx],
            1,
          )
        }
      }
    }
  }

  let (next_global_sec, drop_state_global) = mp_append_drop_state_global(
    mod_, need_drop_state,
  )
  if need_drop_state > 0 {
    changed = true
  }
  let next_code_sec = if segment_op_preflight.has_data_ops {
    mp_rewrite_code_sec_full(
      mod_,
      plans,
      drop_state_global,
      address_type,
      segment_op_preflight.func_has_data_ops,
    )
  } else {
    mod_.code_sec
  }
  let changed_funcs = mp_changed_defined_funcs(
    mod_.code_sec,
    next_code_sec,
    segment_op_preflight.func_has_data_ops,
  )
  let mut code_changed = false
  for func_changed in changed_funcs {
    if func_changed {
      code_changed = true
      break
    }
  }
  if code_changed {
    changed = true
  }

  if !changed {
    return mod_
  }
  let next_data_sec = if rewritten.is_empty() {
    None
  } else {
    Some(@lib.DataSec::new(rewritten))
  }
  let next_data_cnt_sec = match (mod_.data_cnt_sec, next_data_sec) {
    (Some(_), Some(@lib.DataSec(datas))) =>
      Some(@lib.DataCntSec::new(@lib.U32(datas.length().reinterpret_as_uint())))
    (Some(_), None) => None
    (None, _) => None
  }
  let next_name_sec = mp_rewrite_name_sec(
    mod_.name_sec,
    data_name_entries,
    mp_imported_func_count(mod_),
    changed_funcs,
  )
  let invalidates_compiler_facts = code_changed ||
    next_global_sec != mod_.global_sec
  let candidate = @lib.Module::new(
    custom_secs=mod_.custom_secs,
    compiler_fact_custom_section=if invalidates_compiler_facts {
      None
    } else {
      mod_.compiler_fact_custom_section
    },
    type_sec=mod_.type_sec,
    import_sec=mod_.import_sec,
    func_annotation_sec=mod_.func_annotation_sec,
    func_sec=mod_.func_sec,
    table_sec=mod_.table_sec,
    mem_sec=mod_.mem_sec,
    tag_sec=mod_.tag_sec,
    stringrefs_sec=mod_.stringrefs_sec,
    global_sec=next_global_sec,
    export_sec=mod_.export_sec,
    start_sec=mod_.start_sec,
    elem_sec=mod_.elem_sec,
    data_cnt_sec=next_data_cnt_sec,
    code_sec=next_code_sec,
    data_sec=next_data_sec,
    name_sec=next_name_sec,
    raw_name_sec_payload=None,
  )
  // Range thresholds only admit a candidate. Retained names, rewritten code,
  // and body/section framing must still produce a strict complete-byte saving.
  // Discarded compiler facts cannot pay for an otherwise larger data rewrite.
  let baseline = if invalidates_compiler_facts &&
    mod_.compiler_fact_custom_section is Some(_) {
    mod_.without_compiler_fact_custom_section()
  } else {
    mod_
  }
  match @binary.encoded_module_sizes(baseline, candidate) {
    Ok((before, after)) if after < before => candidate
    _ => mod_
  }
}