///|
/// One record found inside the bins that the live key tree cannot reach.
pub(all) struct OrphanRecord {
  offset : Int32
  signature : String
  name : String
  deleted : Bool
}

///|
/// Reads the key name out of an nk or del payload.
fn orphan_name(bytes : Bytes, payload : Int32) -> String {
  let flags = read_u16_le(bytes, payload + 2).reinterpret_as_int()
  let length = read_u16_le(bytes, payload + 72).reinterpret_as_int()
  if length <= 0 || payload + 76 + length > bytes.length() {
    return ""
  }
  if (flags & 0x20) != 0 {
    decode_single_byte(bytes, payload + 76, length)
  } else {
    decode_utf16le(bytes, payload + 76, length / 2)
  }
}

///|
/// True when offset appears in the reachable set.
fn is_reachable(reachable : Array[Int32], offset : Int32) -> Bool {
  let mut index = 0
  while index < reachable.length() {
    if reachable[index] == offset {
      return true
    }
    index = index + 1
  }
  false
}

///|
/// Walks every allocated cell and reports the nk and del records that the
/// live tree does not reach.
///
/// Cells are walked from the first cell after each bin header: a bin starts
/// with a 32 byte hbin header, so the very first 32 bytes of every 4096 byte
/// bin are skipped instead of being read as a cell size.
pub fn scan_orphan_records(
  bytes : Bytes,
) -> Result[Array[OrphanRecord], RegfError] {
  let header = match parse_header(bytes) {
    Err(error) => return Err(error)
    Ok(parsed) => parsed
  }
  let reachable : Array[Int32] = []
  let entries = walk_key_tree(bytes, header.root_cell_offset, 64)
  let mut index = 0
  while index < entries.length() {
    reachable.push(entries[index].offset.reinterpret_as_int())
    index = index + 1
  }
  let out : Array[OrphanRecord] = []
  let limit = hive_bins_base + header.hive_bins_data_size.reinterpret_as_int()
  let stop = if limit > bytes.length() { bytes.length() } else { limit }
  let mut bin_start = hive_bins_base
  while bin_start + 32 <= stop {
    let declared = read_u32_le(bytes, bin_start + 8).reinterpret_as_int()
    let bin_bytes = if declared >= 4096 && bin_start + declared <= stop {
      declared
    } else {
      stop - bin_start
    }
    let bin_end = bin_start + bin_bytes
    let mut cursor = bin_start + 32
    while cursor + 8 <= bin_end {
      let raw_size = read_u32_le(bytes, cursor).reinterpret_as_int()
      let total = if raw_size < 0 { -raw_size } else { raw_size }
      if raw_size == 0 || total < 8 || cursor + total > bin_end {
        cursor = bin_end
      } else {
        let payload = cursor + 4
        let relative = cursor - hive_bins_base
        if raw_size < 0 && payload + 76 <= cursor + total {
          let first = bytes[payload].to_int()
          let second = bytes[payload + 1].to_int()
          let live = first == 0x6E && second == 0x6B
          let deleted = first == 0x64 &&
            second == 0x65 &&
            bytes[payload + 2].to_int() == 0x6C
          if (live || deleted) && !is_reachable(reachable, relative) {
            let record : OrphanRecord = {
              offset: relative,
              signature: if live {
                "nk"
              } else {
                "del"
              },
              name: orphan_name(bytes, payload),
              deleted,
            }
            out.push(record)
          }
        }
        cursor = cursor + total
      }
    }
    bin_start = bin_end
  }
  Ok(out)
}