isomage 2.1.0

//! HFS+ (Mac OS Extended) filesystem reader (`hfsplus` feature).
//!
//! HFS+ is Apple's journaled filesystem introduced in Mac OS 8.1 and still
//! the default on macOS through 10.12. It stores a catalog B-tree (a sorted,
//! multi-level balanced tree) containing all file and directory metadata.
//!
//! All multi-byte fields are **big-endian** (§ references below are to the
//! Apple TN1150 "HFS Plus Volume Format" technical note, the de-facto spec).
//!
//! ## Scope of this implementation
//!
//! - Detects bare HFS+ and HFSX (case-sensitive HFS+) volumes by signature.
//! - Parses the volume header at byte offset 1024 (§4).
//! - Walks the catalog B-tree *leaf-node chain* (§4.3): starts at the first
//!   leaf node and follows `f_link` until the chain ends, collecting folder
//!   and file records. This avoids full B-tree traversal while still visiting
//!   every leaf record in key order.
//! - Decodes UTF-16 BE filenames (§2.1, HFSPlusUniStr255).
//! - Builds a [`TreeNode`] tree rooted at the HFS+ root folder (CNID 2).
//! - Does **not** read resource forks, extended attributes, or file data. The
//!   `file_location` field is populated for files whose data fork fits in a
//!   single contiguous extent so `cat_node` can serve it; multi-extent files
//!   get `file_location = None`.

use std::collections::HashMap;
use std::io::{Read, Seek, SeekFrom};

use crate::tree::TreeNode;

// ── Magic numbers (§4.2 Volume Header signature field) ─────────────────────

/// HFS+ signature: bytes 0x48 0x2B = 'H' '+' at the start of the volume header.
const HFS_PLUS_MAGIC: u16 = 0x482B;
/// HFSX (case-sensitive HFS+) signature: bytes 0x48 0x58 = 'H' 'X'.
const HFSX_MAGIC: u16 = 0x4858;

/// Volume header is always 512 bytes into the HFS+ volume, which itself
/// starts at byte offset 1024 from the beginning of the image (the first
/// 1024 bytes are the "boot blocks").
const VOLUME_HEADER_OFFSET: u64 = 1024;
const VOLUME_HEADER_SIZE: usize = 512;

// ── HFS+ catalog node ID (CNID) constants ──────────────────────────────────

/// CNID of the root folder. Children of the volume root have parent_cnid = 2.
const HFS_ROOT_FOLDER_CNID: u32 = 2;

// ── B-tree node kinds ──────────────────────────────────────────────────────

const BTREE_LEAF_NODE: u8 = 0xFF;
const BTREE_HEADER_NODE: u8 = 0x01;

// ── Catalog record types ───────────────────────────────────────────────────

const RECORD_TYPE_FOLDER: u16 = 0x0001;
const RECORD_TYPE_FILE: u16 = 0x0002;
const RECORD_TYPE_FOLDER_THREAD: u16 = 0x0003;
const RECORD_TYPE_FILE_THREAD: u16 = 0x0004;

// ── Error type ─────────────────────────────────────────────────────────────

/// Errors that can arise while detecting or parsing an HFS+ volume.
#[derive(Debug)]
pub enum Error {
    /// The image is too short to contain a valid HFS+ volume header.
    TooShort,
    /// The 2-byte signature at offset 1024 was not 0x482B or 0x4858.
    BadMagic,
    /// The volume header version field was not 4 (HFS+) or 5 (HFSX).
    BadVersion,
    /// The catalog B-tree structure is invalid (e.g. node 0 is not a
    /// header node, or the node size is below the minimum of 512 bytes).
    BadCatalog,
    /// The B-tree or catalog structure is too deeply nested for our
    /// recursion guard.
    TooDeep,
    /// An underlying I/O error occurred.
    Io(std::io::Error),
}

impl std::fmt::Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::TooShort => write!(f, "image too short for HFS+ volume header"),
            Error::BadMagic => write!(
                f,
                "HFS+ magic 0x482B or HFSX magic 0x4858 not found at offset 1024"
            ),
            Error::BadVersion => write!(f, "HFS+ version field is not 4 (HFS+) or 5 (HFSX)"),
            Error::BadCatalog => write!(f, "HFS+ catalog B-tree structure is invalid"),
            Error::TooDeep => write!(f, "HFS+ B-tree too deep to traverse"),
            Error::Io(e) => write!(f, "HFS+ I/O error: {e}"),
        }
    }
}

impl std::error::Error for Error {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Error::Io(e) => Some(e),
            _ => None,
        }
    }
}

impl From<std::io::Error> for Error {
    fn from(e: std::io::Error) -> Self {
        Error::Io(e)
    }
}

// ── On-disk structs (all fields big-endian) ────────────────────────────────

/// HFSPlusForkData (80 bytes, §2.4).
///
/// Describes one fork (data or resource) of a file, or one of the special
/// B-tree files embedded in the volume.
#[derive(Debug, Clone, Copy)]
pub struct ForkData {
    /// Logical byte length of the fork.
    pub logical_size: u64,
    /// Allocation block count.
    pub total_blocks: u32,
    /// Up to 8 extent descriptors: (start_block, block_count).
    pub extents: [(u32, u32); 8],
}

impl ForkData {
    /// Parse 80 bytes of ForkData from a buffer slice.
    fn from_bytes(b: &[u8]) -> Self {
        let logical_size = u64::from_be_bytes(b[0..8].try_into().unwrap());
        // clump_size at b[8..12] — not needed
        let total_blocks = u32::from_be_bytes(b[12..16].try_into().unwrap());
        let mut extents = [(0u32, 0u32); 8];
        for (i, ext) in extents.iter_mut().enumerate() {
            let off = 16 + i * 8;
            ext.0 = u32::from_be_bytes(b[off..off + 4].try_into().unwrap());
            ext.1 = u32::from_be_bytes(b[off + 4..off + 8].try_into().unwrap());
        }
        Self {
            logical_size,
            total_blocks,
            extents,
        }
    }

    /// Returns the byte offset of the first extent on-disk, given the
    /// allocation block size. Returns `None` if the fork is empty.
    fn first_extent_offset(&self, block_size: u64) -> Option<u64> {
        if self.extents[0].1 == 0 {
            return None;
        }
        Some(self.extents[0].0 as u64 * block_size)
    }

    /// Returns `true` if the entire fork fits in a single contiguous extent
    /// (i.e. only extents[0] is non-zero and covers all total_blocks).
    fn is_single_extent(&self) -> bool {
        if self.total_blocks == 0 {
            return false;
        }
        // extents[0] must cover all blocks, everything else must be zero.
        self.extents[0].1 == self.total_blocks && self.extents[1..].iter().all(|&(_, c)| c == 0)
    }
}

/// Parsed volume header fields we actually need (§4.2).
#[derive(Debug)]
pub struct VolumeHeader {
    /// HFS+ or HFSX.
    pub signature: u16,
    /// 4 = HFS+, 5 = HFSX.
    pub version: u16,
    /// Number of regular files on the volume (excluding directories).
    pub file_count: u32,
    /// Number of directories on the volume.
    pub folder_count: u32,
    /// Size of one allocation block in bytes.
    pub block_size: u32,
    /// The catalog B-tree's fork data — tells us where the catalog lives.
    pub cat_file: ForkData,
}

impl VolumeHeader {
    /// Parse a 512-byte volume header.
    fn from_bytes(b: &[u8]) -> Result<Self, Error> {
        if b.len() < VOLUME_HEADER_SIZE {
            return Err(Error::TooShort);
        }
        let signature = u16::from_be_bytes([b[0], b[1]]);
        if signature != HFS_PLUS_MAGIC && signature != HFSX_MAGIC {
            return Err(Error::BadMagic);
        }
        let version = u16::from_be_bytes([b[2], b[3]]);
        if version != 4 && version != 5 {
            return Err(Error::BadVersion);
        }
        let file_count = u32::from_be_bytes(b[32..36].try_into().unwrap());
        let folder_count = u32::from_be_bytes(b[36..40].try_into().unwrap());
        let block_size = u32::from_be_bytes(b[40..44].try_into().unwrap());
        // Catalog file fork: offset 272 in the header (§4.2).
        let cat_file = ForkData::from_bytes(&b[272..352]);
        Ok(Self {
            signature,
            version,
            file_count,
            folder_count,
            block_size,
            cat_file,
        })
    }
}

// ── B-tree header record (§4.3.1) ─────────────────────────────────────────

/// Subset of the B-tree header record we need to navigate the leaf chain.
struct BTreeHeader {
    node_size: u16,
    first_leaf_node: u32,
}

impl BTreeHeader {
    /// Parse from the 106-byte header record (first record in the header node).
    fn from_bytes(b: &[u8]) -> Self {
        // tree_depth at [0..2] — not needed
        // root_node  at [2..6] — not needed for leaf-chain walk
        // leaf_records at [6..10] — not needed
        let first_leaf_node = u32::from_be_bytes(b[10..14].try_into().unwrap());
        // last_leaf_node at [14..18] — not needed
        let node_size = u16::from_be_bytes(b[18..20].try_into().unwrap());
        Self {
            node_size,
            first_leaf_node,
        }
    }
}

// ── Catalog record types ───────────────────────────────────────────────────

/// One catalog leaf record, as we need it for tree construction.
#[derive(Debug)]
enum CatalogRecord {
    Folder {
        parent_cnid: u32,
        name: String,
        cnid: u32,
    },
    File {
        parent_cnid: u32,
        name: String,
        #[allow(dead_code)]
        cnid: u32,
        /// Logical length of the data fork in bytes.
        file_length: u64,
        /// Byte offset of the data fork, if it fits in one extent.
        file_location: Option<u64>,
    },
    /// Thread record — gives us name+parent for a CNID we already know.
    Thread {
        #[allow(dead_code)]
        cnid_key: u32, // the CNID this thread is for (from the key parent field)
        #[allow(dead_code)]
        record_type: u16,
    },
}

// ── Public API ─────────────────────────────────────────────────────────────

/// Detect whether the reader contains an HFS+ or HFSX volume.
///
/// Seeks to offset 1024, reads the 2-byte signature, then **restores the
/// cursor** to its position before the call. Returns `Ok(())` on a match.
pub fn detect<R: Read + Seek>(r: &mut R) -> Result<(), Error> {
    let saved = r.stream_position()?;
    let result = do_detect(r);
    let _ = r.seek(SeekFrom::Start(saved));
    result
}

fn do_detect<R: Read + Seek>(r: &mut R) -> Result<(), Error> {
    r.seek(SeekFrom::Start(VOLUME_HEADER_OFFSET))?;
    let mut sig = [0u8; 2];
    r.read_exact(&mut sig).map_err(|e| {
        if e.kind() == std::io::ErrorKind::UnexpectedEof {
            Error::TooShort
        } else {
            Error::Io(e)
        }
    })?;
    let sig_val = u16::from_be_bytes([sig[0], sig[1]]);
    if sig_val != HFS_PLUS_MAGIC && sig_val != HFSX_MAGIC {
        return Err(Error::BadMagic);
    }
    Ok(())
}

/// Read the volume header only (does not walk the catalog B-tree).
///
/// Exposed for unit tests and callers that only need top-level volume metadata.
pub fn parse_volume_header<R: Read + Seek>(r: &mut R) -> Result<VolumeHeader, Error> {
    r.seek(SeekFrom::Start(VOLUME_HEADER_OFFSET))?;
    let mut buf = [0u8; VOLUME_HEADER_SIZE];
    r.read_exact(&mut buf).map_err(|e| {
        if e.kind() == std::io::ErrorKind::UnexpectedEof {
            Error::TooShort
        } else {
            Error::Io(e)
        }
    })?;
    VolumeHeader::from_bytes(&buf)
}

/// Detect an HFS+ or HFSX volume, then parse its catalog B-tree into a
/// [`TreeNode`] tree.
///
/// The tree root is `"/"` (a directory), with one child per entry directly
/// under the volume root (CNID 2). Subdirectories are populated recursively.
/// Files get `file_location = Some(offset)` only when their data fork fits in
/// a single contiguous allocation-block extent; multi-extent files fall back
/// to `None`.
pub fn detect_and_parse<R: Read + Seek>(r: &mut R) -> Result<TreeNode, Error> {
    let header = parse_volume_header(r)?;
    let records = read_catalog_leaf_records(r, &header)?;
    Ok(build_tree(&records, header.block_size as u64))
}

// ── Catalog B-tree leaf-chain walker ──────────────────────────────────────

/// Read all leaf records from the catalog B-tree by following the forward
/// link chain rather than traversing the full tree top-down.
///
/// Strategy (§4.3.4):
/// 1. The catalog file extents in the volume header tell us the on-disk
///    position of the catalog B-tree data.
/// 2. Node 0 is always the B-tree header node; we read the B-tree header
///    record from it to get `node_size` and `first_leaf_node`.
/// 3. Leaf nodes form a doubly-linked list via their `f_link` field; we
///    follow `f_link` until it is 0.
/// 4. For each leaf node we parse every record: catalog key (parent_cnid,
///    name) + catalog data (record_type, CNID, fork data for files).
fn read_catalog_leaf_records<R: Read + Seek>(
    r: &mut R,
    header: &VolumeHeader,
) -> Result<Vec<CatalogRecord>, Error> {
    let block_size = header.block_size as u64;
    let cat = &header.cat_file;

    // If the catalog fork is empty (logical_size == 0 or no extents), there
    // are no records to read — return an empty list rather than an error.
    let cat_offset = match cat.first_extent_offset(block_size) {
        Some(off) => off,
        None => return Ok(Vec::new()),
    };

    // ── Step 1: Read the B-tree header node (node 0) ──
    // We read exactly 120 bytes (14-byte node descriptor + 106-byte BTHeaderRec).
    // Per the HFS+ spec (TN1150 §2.2), the B-tree header record ALWAYS begins
    // at byte 14 of the header node, immediately after the node descriptor.
    // We do not use the offset table to locate record 0 here because the offset
    // table lives at the END of the node — and we don't know node_size yet.
    r.seek(SeekFrom::Start(cat_offset))?;
    let mut header_node_buf = vec![0u8; 120]; // 14 (descriptor) + 106 (BTHeaderRec)
    r.read_exact(&mut header_node_buf).map_err(|e| {
        if e.kind() == std::io::ErrorKind::UnexpectedEof {
            Error::TooShort
        } else {
            Error::Io(e)
        }
    })?;

    // B-tree node descriptor is 14 bytes at the start of every node.
    let node_kind = header_node_buf[8];
    if node_kind != BTREE_HEADER_NODE {
        // Node 0 must be the header node.
        return Err(Error::BadCatalog);
    }
    let num_records_in_header = u16::from_be_bytes([header_node_buf[10], header_node_buf[11]]);
    if num_records_in_header < 1 {
        return Err(Error::TooShort);
    }

    // The BTHeaderRec starts at byte 14 (immediately after the node descriptor).
    let btree_header = BTreeHeader::from_bytes(&header_node_buf[14..]);

    let node_size = btree_header.node_size as u64;
    if node_size < 512 {
        return Err(Error::BadCatalog);
    }

    let mut first_leaf = btree_header.first_leaf_node;
    if first_leaf == 0 {
        // Empty catalog — no leaf nodes.
        return Ok(Vec::new());
    }

    // ── Step 2: Walk the leaf-node chain ──
    let mut records: Vec<CatalogRecord> = Vec::new();
    // Guard against corrupted or circular f_link chains.
    let max_nodes: u32 = (cat.logical_size / node_size).min(u32::MAX as u64) as u32 + 1;
    let mut visited = 0u32;

    loop {
        if visited > max_nodes {
            return Err(Error::TooDeep);
        }
        visited += 1;

        // Seek to the start of this leaf node.
        let node_offset = cat_offset + first_leaf as u64 * node_size;
        r.seek(SeekFrom::Start(node_offset))?;
        let mut node_buf = vec![0u8; node_size as usize];
        r.read_exact(&mut node_buf).map_err(|e| {
            if e.kind() == std::io::ErrorKind::UnexpectedEof {
                Error::TooShort
            } else {
                Error::Io(e)
            }
        })?;

        // Node descriptor (14 bytes).
        let f_link = u32::from_be_bytes(node_buf[0..4].try_into().unwrap());
        let kind = node_buf[8];
        let num_records = u16::from_be_bytes([node_buf[10], node_buf[11]]);

        if kind != BTREE_LEAF_NODE {
            // Should never happen in a healthy volume; tolerate it by skipping.
            if f_link == 0 {
                break;
            }
            first_leaf = f_link;
            continue;
        }

        // ── Parse each record in this leaf node ──
        parse_leaf_node_records(&node_buf, num_records, block_size, &mut records)?;

        if f_link == 0 {
            break;
        }
        first_leaf = f_link;
    }

    Ok(records)
}

/// Parse all catalog records from one leaf node's byte buffer.
fn parse_leaf_node_records(
    node_buf: &[u8],
    num_records: u16,
    block_size: u64,
    out: &mut Vec<CatalogRecord>,
) -> Result<(), Error> {
    let node_size = node_buf.len();

    for i in 0..num_records as usize {
        // The offset table is at the END of the node, one u16 per entry,
        // going backwards (§4.3.3). offset[i] is at:
        //   node_size - 2*(i+1)
        let off_idx = node_size.saturating_sub(2 * (i + 1));
        if off_idx + 2 > node_size {
            break;
        }
        let rec_start = u16::from_be_bytes([node_buf[off_idx], node_buf[off_idx + 1]]) as usize;
        if rec_start >= node_size {
            continue;
        }
        let rec_data = &node_buf[rec_start..];

        // ── Catalog key (§4.3.5) ──
        // [0..2] u16 key_length
        // [2..6] u32 parent_cnid (BE)
        // [6..8] u16 name.length (BE)
        // [8..8+2*name.length] UTF-16 BE code units
        if rec_data.len() < 6 {
            continue;
        }
        let key_length = u16::from_be_bytes([rec_data[0], rec_data[1]]) as usize;
        if key_length < 6 || rec_data.len() < 2 + key_length {
            continue;
        }
        let parent_cnid = u32::from_be_bytes(rec_data[2..6].try_into().unwrap());
        let name_len = u16::from_be_bytes([rec_data[6], rec_data[7]]) as usize;
        let name_bytes_len = name_len * 2;
        if rec_data.len() < 8 + name_bytes_len {
            continue;
        }
        let name = decode_utf16_be(&rec_data[8..8 + name_bytes_len]);

        // The catalog data starts immediately after the key, rounded up to
        // the next 2-byte boundary from the record start (§4.3.5).
        let raw_data_off = 2 + key_length; // key_length does NOT include the 2-byte key_length field itself
        let data_off = (raw_data_off + 1) & !1; // align to 2 bytes
        if rec_data.len() < data_off + 2 {
            continue;
        }
        let data = &rec_data[data_off..];
        let record_type = u16::from_be_bytes([data[0], data[1]]);

        match record_type {
            RECORD_TYPE_FOLDER => {
                // Folder record (248 bytes total, §4.3.6).
                // [8..12] u32 cnid
                if data.len() < 12 {
                    continue;
                }
                let cnid = u32::from_be_bytes(data[8..12].try_into().unwrap());
                out.push(CatalogRecord::Folder {
                    parent_cnid,
                    name,
                    cnid,
                });
            }
            RECORD_TYPE_FILE => {
                // File record (248 bytes total, §4.3.7).
                // [8..12]    u32 cnid
                // [88..168]  HFSPlusForkData data_fork (80 bytes)
                if data.len() < 168 {
                    continue;
                }
                let cnid = u32::from_be_bytes(data[8..12].try_into().unwrap());
                let data_fork = ForkData::from_bytes(&data[88..168]);
                let file_length = data_fork.logical_size;
                let file_location = if data_fork.is_single_extent() {
                    data_fork.first_extent_offset(block_size)
                } else {
                    None
                };
                out.push(CatalogRecord::File {
                    parent_cnid,
                    name,
                    cnid,
                    file_length,
                    file_location,
                });
            }
            RECORD_TYPE_FOLDER_THREAD | RECORD_TYPE_FILE_THREAD => {
                // Thread records are keyed by CNID; we don't need them for
                // tree construction since we already get names from the
                // corresponding folder/file records.
                out.push(CatalogRecord::Thread {
                    cnid_key: parent_cnid, // in thread records, the key parent field holds the CNID
                    record_type,
                });
            }
            _ => {
                // Unknown record type — skip.
            }
        }
    }

    Ok(())
}

// ── Tree construction ──────────────────────────────────────────────────────

/// Navigate a tree by a slice of directory-name segments and return a
/// mutable reference to the matching node, or `None` if not found.
fn find_by_path_mut<'a>(node: &'a mut TreeNode, path: &[String]) -> Option<&'a mut TreeNode> {
    if path.is_empty() {
        return Some(node);
    }
    for child in &mut node.children {
        if child.is_directory && child.name == path[0] {
            return find_by_path_mut(child, &path[1..]);
        }
    }
    None
}

/// Build the path (list of directory names from root) for a CNID by
/// following the `folder_map` chain.
fn cnid_path(cnid: u32, folder_map: &std::collections::HashMap<u32, (String, u32)>) -> Vec<String> {
    if cnid == HFS_ROOT_FOLDER_CNID {
        return vec![];
    }
    let mut path = Vec::new();
    let mut cur = cnid;
    let mut guard = 0usize;
    loop {
        guard += 1;
        if guard > 1000 {
            break; // cycle guard
        }
        match folder_map.get(&cur) {
            Some((name, parent)) => {
                path.push(name.clone());
                if *parent == HFS_ROOT_FOLDER_CNID || *parent == 0 {
                    break;
                }
                cur = *parent;
            }
            None => break,
        }
    }
    path.reverse();
    path
}

/// Build a [`TreeNode`] tree from the flat list of catalog records.
///
/// HFS+ uses catalog node IDs (CNIDs) as stable directory identifiers:
/// every record carries a `parent_cnid` linking it to its parent folder.
/// CNID 2 is the root folder; its children appear in the `"/"` node.
///
/// Algorithm:
/// 1. Index all folder CNIDs → mutable TreeNode placeholders.
/// 2. Walk records in order, attaching each file/folder to its parent.
/// 3. Return the root node (CNID 2) with `calculate_directory_size` applied.
fn build_tree(records: &[CatalogRecord], _block_size: u64) -> TreeNode {
    // ── Pass 1: collect all folder records ──
    // Map from CNID to (name, parent_cnid) for every folder.
    let mut folder_map: HashMap<u32, (String, u32)> = HashMap::new();
    folder_map.insert(HFS_ROOT_FOLDER_CNID, ("/".to_string(), 0));

    for rec in records {
        if let CatalogRecord::Folder {
            cnid,
            name,
            parent_cnid,
        } = rec
        {
            if *cnid != HFS_ROOT_FOLDER_CNID {
                folder_map.insert(*cnid, (name.clone(), *parent_cnid));
            }
        }
    }

    // ── Pass 2: build a flat map of TreeNodes, keyed by CNID ──
    let mut nodes: HashMap<u32, TreeNode> = HashMap::new();
    nodes.insert(
        HFS_ROOT_FOLDER_CNID,
        TreeNode::new_directory("/".to_string()),
    );
    for (&cnid, (name, _)) in &folder_map {
        if cnid != HFS_ROOT_FOLDER_CNID {
            nodes.insert(cnid, TreeNode::new_directory(name.clone()));
        }
    }

    // ── Pass 3: collect file nodes and their parent CNIDs ──
    let mut file_items: Vec<(u32, TreeNode)> = Vec::new();
    for rec in records {
        if let CatalogRecord::File {
            parent_cnid,
            name,
            file_length,
            file_location,
            ..
        } = rec
        {
            let node = if let Some(loc) = file_location {
                // Adjust file_location: the extent start_block is relative to
                // the beginning of the *volume*, which (for a bare HFS+ image)
                // starts at byte 0. block_size is already in bytes.
                // We pass it through as-is; the caller's image must be seekable
                // to this offset.
                TreeNode::new_file_with_location(name.clone(), *file_length, *loc, *file_length)
            } else {
                TreeNode::new_file(name.clone(), *file_length)
            };
            file_items.push((*parent_cnid, node));
        }
    }

    // ── Pass 4: attach children in parent-CNID order ──
    // We do this in two phases to avoid borrow-checker conflicts:
    // first collect (parent_cnid, child_cnid) pairs for dirs, then attach.
    let dir_children: Vec<(u32, u32)> = folder_map
        .iter()
        .filter(|(&cnid, _)| cnid != HFS_ROOT_FOLDER_CNID)
        .map(|(&cnid, (_, parent_cnid))| (*parent_cnid, cnid))
        .collect();

    // Build the tree bottom-up: repeatedly find directories whose parent
    // exists in `nodes` and whose children are all already there.
    // Because HFS+ catalogs are in key order (parent_cnid, name), the
    // simplest approach is a topological attachment by repeated passes.
    // For real-world volumes the depth is ≤ a few hundred at most.
    // We bound iterations at folder_map.len() + 1 to avoid infinite loops
    // on corrupted volumes.
    let mut remaining: Vec<(u32, u32)> = dir_children; // (parent_cnid, child_cnid)
    let max_iters = folder_map.len() + 1;
    for _ in 0..max_iters {
        if remaining.is_empty() {
            break;
        }
        let mut still_pending: Vec<(u32, u32)> = Vec::new();
        for (parent_cnid, child_cnid) in remaining.drain(..) {
            if nodes.contains_key(&child_cnid) && nodes.contains_key(&parent_cnid) {
                let child = nodes.remove(&child_cnid).unwrap();
                nodes.entry(parent_cnid).and_modify(|p| p.add_child(child));
            } else {
                still_pending.push((parent_cnid, child_cnid));
            }
        }
        remaining = still_pending;
    }

    // Attach files to their parents.  After Pass 4 only the root node
    // remains in `nodes`; subdirectory nodes were removed and nested
    // inside it.  Resolve each parent CNID to its path in the tree and
    // navigate there to attach the file.
    let root_node = nodes.get_mut(&HFS_ROOT_FOLDER_CNID).unwrap();
    for (parent_cnid, file_node) in file_items {
        let path = cnid_path(parent_cnid, &folder_map);
        if let Some(parent) = find_by_path_mut(root_node, &path) {
            parent.add_child(file_node);
        }
        // If path not found (orphan / corrupted image), silently drop.
    }

    // Sort children alphabetically to produce a stable output order.
    sort_children_recursive(nodes.get_mut(&HFS_ROOT_FOLDER_CNID).unwrap());

    let mut root = nodes
        .remove(&HFS_ROOT_FOLDER_CNID)
        .unwrap_or_else(|| TreeNode::new_directory("/".to_string()));
    root.calculate_directory_size();
    root
}

/// Sort a [`TreeNode`]'s children (and their children) alphabetically by name.
fn sort_children_recursive(node: &mut TreeNode) {
    node.children.sort_by(|a, b| a.name.cmp(&b.name));
    for child in &mut node.children {
        if child.is_directory {
            sort_children_recursive(child);
        }
    }
}

// ── UTF-16 BE decoding ─────────────────────────────────────────────────────

/// Decode a big-endian UTF-16 byte slice into a `String`.
///
/// HFS+ stores all filenames as UTF-16 BE (§2.1). Invalid surrogate pairs
/// and lone surrogates are replaced with U+FFFD to match the behaviour of
/// the existing GPT UTF-16LE decoder (`gpt::decode_utf16le`).
fn decode_utf16_be(bytes: &[u8]) -> String {
    let mut units: Vec<u16> = Vec::with_capacity(bytes.len() / 2);
    for chunk in bytes.chunks_exact(2) {
        let unit = u16::from_be_bytes([chunk[0], chunk[1]]);
        if unit == 0 {
            break;
        }
        units.push(unit);
    }
    String::from_utf16_lossy(&units)
}

// ── Unit tests ─────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Cursor;

    /// Build a minimal in-memory HFS+ image: 1024 bytes of zeros (boot
    /// blocks) followed by a valid volume header, with any remaining space
    /// zeroed. Enough to satisfy `detect` and `parse_volume_header`.
    fn make_volume_header_bytes(
        signature: u16,
        version: u16,
        file_count: u32,
        folder_count: u32,
        block_size: u32,
    ) -> Vec<u8> {
        let mut buf = vec![0u8; 1024 + VOLUME_HEADER_SIZE];
        let h = &mut buf[1024..1024 + VOLUME_HEADER_SIZE];
        h[0..2].copy_from_slice(&signature.to_be_bytes());
        h[2..4].copy_from_slice(&version.to_be_bytes());
        h[32..36].copy_from_slice(&file_count.to_be_bytes());
        h[36..40].copy_from_slice(&folder_count.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        // cat_file at offset 272 — all zeros is fine for unit tests that
        // don't walk the B-tree.
        buf
    }

    #[test]
    fn detect_hfsplus_signature() {
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 4, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        assert!(detect(&mut c).is_ok(), "should detect HFS+ magic 0x482B");
    }

    #[test]
    fn detect_hfsx_signature() {
        let buf = make_volume_header_bytes(HFSX_MAGIC, 5, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        assert!(detect(&mut c).is_ok(), "should detect HFSX magic 0x4858");
    }

    #[test]
    fn detect_rejects_bad_magic() {
        let buf = make_volume_header_bytes(0xDEAD, 4, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        assert!(
            matches!(detect(&mut c), Err(Error::BadMagic)),
            "should reject non-HFS+ signature"
        );
    }

    #[test]
    fn detect_restores_cursor() {
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 4, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        c.seek(SeekFrom::Start(42)).unwrap();
        let _ = detect(&mut c);
        assert_eq!(c.position(), 42, "detect must restore the cursor position");
    }

    #[test]
    fn parse_volume_header_fields() {
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 4, 100, 20, 4096);
        let mut c = Cursor::new(&buf);
        let vh = parse_volume_header(&mut c).expect("parse volume header");
        assert_eq!(vh.signature, HFS_PLUS_MAGIC);
        assert_eq!(vh.version, 4);
        assert_eq!(vh.file_count, 100);
        assert_eq!(vh.folder_count, 20);
        assert_eq!(vh.block_size, 4096);
    }

    #[test]
    fn parse_volume_header_rejects_bad_version() {
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 99, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        assert!(
            matches!(parse_volume_header(&mut c), Err(Error::BadVersion)),
            "version 99 should be rejected"
        );
    }

    #[test]
    fn decode_utf16_be_ascii() {
        // "Hello" in big-endian UTF-16.
        let bytes: Vec<u8> = "Hello"
            .encode_utf16()
            .flat_map(|u| u.to_be_bytes())
            .collect();
        assert_eq!(decode_utf16_be(&bytes), "Hello");
    }

    #[test]
    fn decode_utf16_be_stops_at_nul() {
        let mut bytes: Vec<u8> = "AB".encode_utf16().flat_map(|u| u.to_be_bytes()).collect();
        bytes.extend_from_slice(&[0x00, 0x00]); // NUL terminator
        bytes.extend_from_slice(&[0x00, 0x43]); // 'C' after NUL — should be ignored
        assert_eq!(decode_utf16_be(&bytes), "AB");
    }

    #[test]
    fn fork_data_single_extent_detection() {
        let mut b = [0u8; 80];
        // logical_size = 1024, total_blocks = 2, extent[0] = (start=10, count=2)
        b[0..8].copy_from_slice(&1024u64.to_be_bytes());
        b[12..16].copy_from_slice(&2u32.to_be_bytes());
        b[16..20].copy_from_slice(&10u32.to_be_bytes()); // start_block
        b[20..24].copy_from_slice(&2u32.to_be_bytes()); // block_count
        let fork = ForkData::from_bytes(&b);
        assert!(fork.is_single_extent(), "should be single-extent fork");
        assert_eq!(
            fork.first_extent_offset(512),
            Some(10 * 512),
            "offset = start_block * block_size"
        );
    }

    #[test]
    fn fork_data_multi_extent_not_single() {
        let mut b = [0u8; 80];
        // total_blocks = 4, two extents of 2 each
        b[12..16].copy_from_slice(&4u32.to_be_bytes());
        b[16..20].copy_from_slice(&10u32.to_be_bytes());
        b[20..24].copy_from_slice(&2u32.to_be_bytes());
        b[24..28].copy_from_slice(&20u32.to_be_bytes());
        b[28..32].copy_from_slice(&2u32.to_be_bytes());
        let fork = ForkData::from_bytes(&b);
        assert!(
            !fork.is_single_extent(),
            "two-extent fork should not be single-extent"
        );
    }

    #[test]
    fn detect_and_parse_empty_catalog() {
        // Build an image where the catalog file's logical_size is 0 (no records).
        // detect_and_parse should succeed and return an empty root.
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 4, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        let tree = detect_and_parse(&mut c).expect("parse empty HFS+ volume");
        assert_eq!(tree.name, "/");
        assert!(tree.is_directory);
        assert!(tree.children.is_empty(), "empty catalog → no children");
    }

    // ── build_tree ────────────────────────────────────────────────────────────

    #[test]
    fn build_tree_single_file_in_root() {
        let records = vec![CatalogRecord::File {
            parent_cnid: HFS_ROOT_FOLDER_CNID, // 2
            name: "hello.txt".to_string(),
            cnid: 10,
            file_length: 42,
            file_location: Some(4096),
        }];
        let root = build_tree(&records, 4096);
        assert_eq!(root.name, "/");
        assert_eq!(root.children.len(), 1);
        assert_eq!(root.children[0].name, "hello.txt");
        assert_eq!(root.children[0].size, 42);
    }

    #[test]
    fn build_tree_nested_directory() {
        let records = vec![
            CatalogRecord::Folder {
                parent_cnid: HFS_ROOT_FOLDER_CNID,
                name: "docs".to_string(),
                cnid: 20,
            },
            CatalogRecord::File {
                parent_cnid: 20, // child of "docs"
                name: "readme.txt".to_string(),
                cnid: 21,
                file_length: 100,
                file_location: None,
            },
        ];
        let root = build_tree(&records, 4096);
        assert_eq!(root.children.len(), 1);
        let docs = &root.children[0];
        assert_eq!(docs.name, "docs");
        assert!(docs.is_directory);
        assert_eq!(docs.children.len(), 1);
        assert_eq!(docs.children[0].name, "readme.txt");
    }

    #[test]
    fn build_tree_thread_record_ignored() {
        let records = vec![
            CatalogRecord::Thread {
                cnid_key: 5,
                record_type: 3,
            },
            CatalogRecord::File {
                parent_cnid: HFS_ROOT_FOLDER_CNID,
                name: "f.bin".to_string(),
                cnid: 5,
                file_length: 0,
                file_location: None,
            },
        ];
        let root = build_tree(&records, 4096);
        assert_eq!(root.children.len(), 1);
        assert_eq!(root.children[0].name, "f.bin");
    }

    #[test]
    fn build_tree_file_without_location() {
        let records = vec![CatalogRecord::File {
            parent_cnid: HFS_ROOT_FOLDER_CNID,
            name: "sparse.dat".to_string(),
            cnid: 30,
            file_length: 200,
            file_location: None,
        }];
        let root = build_tree(&records, 512);
        let node = &root.children[0];
        assert_eq!(node.name, "sparse.dat");
        assert!(node.file_location.is_none());
    }

    // ── parse_leaf_node_records ───────────────────────────────────────────────

    /// Build a minimal leaf node buffer with one catalog record at a given
    /// offset, plus the offset table at the end.
    fn make_leaf_node(key_data: &[u8], record_data: &[u8]) -> Vec<u8> {
        // Node size = 512 bytes (one sector).
        let node_size = 512usize;
        let mut node = vec![0u8; node_size];

        // Record starts at offset 14 (after the 14-byte node descriptor).
        let rec_start: u16 = 14;
        let rec_end = rec_start as usize + key_data.len() + record_data.len();

        node[rec_start as usize..rec_start as usize + key_data.len()].copy_from_slice(key_data);
        node[rec_start as usize + key_data.len()..rec_end].copy_from_slice(record_data);

        // Offset table: [node_size - 2] = rec_start (one record → one entry)
        let ot_idx = node_size - 2; // offset for record 0
        node[ot_idx..ot_idx + 2].copy_from_slice(&rec_start.to_be_bytes());

        node
    }

    /// Build a catalog key with the given parent_cnid and name (UTF-16 BE).
    fn make_catalog_key(parent_cnid: u32, name: &str) -> Vec<u8> {
        let name_utf16: Vec<u8> = name.encode_utf16().flat_map(|u| u.to_be_bytes()).collect();
        let name_len = name.encode_utf16().count() as u16;
        let key_length = (6 + name_utf16.len()) as u16; // parent(4) + name.length(2) + name
        let mut key = Vec::new();
        key.extend_from_slice(&key_length.to_be_bytes()); // key_length (2 bytes)
        key.extend_from_slice(&parent_cnid.to_be_bytes()); // parent_cnid (4 bytes)
        key.extend_from_slice(&name_len.to_be_bytes()); // name.length (2 bytes)
        key.extend_from_slice(&name_utf16); // name bytes
                                            // Pad key to even length if needed (data_off = (2 + key_length + 1) & !1)
        if key.len() % 2 != 0 {
            key.push(0);
        }
        key
    }

    #[test]
    fn parse_leaf_node_folder_record() {
        let key = make_catalog_key(HFS_ROOT_FOLDER_CNID, "subdir");
        // Folder record: type=0x0001, valence(ignored), cnid at offset 8
        let cnid: u32 = 100;
        let mut rec_data = vec![0u8; 248];
        rec_data[0..2].copy_from_slice(&RECORD_TYPE_FOLDER.to_be_bytes());
        rec_data[8..12].copy_from_slice(&cnid.to_be_bytes());

        let node = make_leaf_node(&key, &rec_data);
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();

        assert_eq!(out.len(), 1);
        if let CatalogRecord::Folder {
            parent_cnid,
            name,
            cnid: c,
        } = &out[0]
        {
            assert_eq!(*parent_cnid, HFS_ROOT_FOLDER_CNID);
            assert_eq!(name, "subdir");
            assert_eq!(*c, 100);
        } else {
            panic!("expected Folder record");
        }
    }

    #[test]
    fn parse_leaf_node_file_record() {
        let key = make_catalog_key(HFS_ROOT_FOLDER_CNID, "file.txt");
        let mut rec_data = vec![0u8; 248];
        rec_data[0..2].copy_from_slice(&RECORD_TYPE_FILE.to_be_bytes());
        // cnid at offset 8
        rec_data[8..12].copy_from_slice(&55u32.to_be_bytes());
        // data_fork at offset 88: logical_size=1024, total_blocks=1, extent[0]=(10,1)
        let fork_off = 88;
        rec_data[fork_off..fork_off + 8].copy_from_slice(&1024u64.to_be_bytes()); // logical_size
        rec_data[fork_off + 12..fork_off + 16].copy_from_slice(&1u32.to_be_bytes()); // total_blocks
        rec_data[fork_off + 16..fork_off + 20].copy_from_slice(&10u32.to_be_bytes()); // start_block
        rec_data[fork_off + 20..fork_off + 24].copy_from_slice(&1u32.to_be_bytes()); // block_count

        let node = make_leaf_node(&key, &rec_data);
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();

        assert_eq!(out.len(), 1);
        if let CatalogRecord::File {
            name,
            file_length,
            file_location,
            ..
        } = &out[0]
        {
            assert_eq!(name, "file.txt");
            assert_eq!(*file_length, 1024);
            // single extent → location = start_block * block_size = 10 * 4096
            assert_eq!(*file_location, Some(10 * 4096));
        } else {
            panic!("expected File record");
        }
    }

    #[test]
    fn parse_leaf_node_thread_record() {
        let key = make_catalog_key(HFS_ROOT_FOLDER_CNID, "");
        let mut rec_data = vec![0u8; 10];
        rec_data[0..2].copy_from_slice(&RECORD_TYPE_FOLDER_THREAD.to_be_bytes());

        let node = make_leaf_node(&key, &rec_data);
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert_eq!(out.len(), 1);
        assert!(matches!(out[0], CatalogRecord::Thread { .. }));
    }

    // ── Error Display / source ────────────────────────────────────────────────

    #[test]
    fn error_display_too_short() {
        let msg = format!("{}", Error::TooShort);
        assert!(
            msg.contains("HFS+") || msg.contains("short"),
            "unexpected: {msg}"
        );
    }

    #[test]
    fn error_display_bad_magic() {
        let msg = format!("{}", Error::BadMagic);
        assert!(
            msg.contains("magic") || msg.contains("HFS"),
            "unexpected: {msg}"
        );
    }

    #[test]
    fn error_display_bad_version() {
        let msg = format!("{}", Error::BadVersion);
        assert!(
            msg.contains("version") || msg.contains("HFS"),
            "unexpected: {msg}"
        );
    }

    #[test]
    fn error_display_bad_catalog() {
        let msg = format!("{}", Error::BadCatalog);
        assert!(
            msg.contains("catalog") || msg.contains("HFS"),
            "unexpected: {msg}"
        );
    }

    #[test]
    fn error_display_too_deep() {
        let msg = format!("{}", Error::TooDeep);
        assert!(
            msg.contains("deep") || msg.contains("HFS"),
            "unexpected: {msg}"
        );
    }

    #[test]
    fn error_display_io() {
        let io = std::io::Error::other("disk fail");
        let msg = format!("{}", Error::Io(io));
        assert!(msg.contains("disk fail"), "unexpected: {msg}");
    }

    #[test]
    fn error_source_io() {
        use std::error::Error as StdError;
        let io = std::io::Error::other("src");
        assert!(Error::Io(io).source().is_some());
    }

    #[test]
    fn error_source_non_io() {
        use std::error::Error as StdError;
        assert!(Error::TooShort.source().is_none());
        assert!(Error::BadMagic.source().is_none());
        assert!(Error::BadCatalog.source().is_none());
        assert!(Error::TooDeep.source().is_none());
    }

    // ── ForkData::first_extent_offset ────────────────────────────────────────

    #[test]
    fn fork_data_first_extent_offset_zero_block_count_returns_none() {
        // extents[0].1 == 0 (block count is zero) → returns None.
        let fd = ForkData {
            logical_size: 0,
            total_blocks: 0,
            extents: [
                (5, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
            ],
        };
        assert!(fd.first_extent_offset(4096).is_none());
    }

    #[test]
    fn fork_data_first_extent_offset_nonzero_block_count() {
        // extents[0] = (start=10, count=3): offset = 10 * block_size.
        let fd = ForkData {
            logical_size: 100,
            total_blocks: 3,
            extents: [
                (10, 3),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
                (0, 0),
            ],
        };
        assert_eq!(fd.first_extent_offset(4096), Some(10 * 4096));
    }

    // ── From<io::Error> ──────────────────────────────────────────────────────

    #[test]
    fn error_from_io_error() {
        let io = std::io::Error::other("disk");
        let err = Error::from(io);
        assert!(matches!(err, Error::Io(_)));
    }

    // ── VolumeHeader::from_bytes error paths ─────────────────────────────────

    #[test]
    fn volume_header_from_bytes_too_short() {
        assert!(matches!(
            VolumeHeader::from_bytes(&[0u8; 10]),
            Err(Error::TooShort)
        ));
    }

    #[test]
    fn volume_header_from_bytes_bad_magic() {
        let mut buf = vec![0u8; VOLUME_HEADER_SIZE];
        buf[0..2].copy_from_slice(&0x1234u16.to_be_bytes()); // wrong signature
        buf[2..4].copy_from_slice(&4u16.to_be_bytes()); // version=4
        assert!(matches!(
            VolumeHeader::from_bytes(&buf),
            Err(Error::BadMagic)
        ));
    }

    // ── ForkData::is_single_extent zero total_blocks ─────────────────────────

    #[test]
    fn fork_data_is_single_extent_zero_total_blocks_returns_false() {
        let fd = ForkData {
            logical_size: 0,
            total_blocks: 0,
            extents: [(0, 0); 8],
        };
        assert!(!fd.is_single_extent());
    }

    // ── BTreeHeader::from_bytes ───────────────────────────────────────────────

    #[test]
    fn btree_header_from_bytes_parses_fields() {
        let mut buf = vec![0u8; 106];
        buf[10..14].copy_from_slice(&42u32.to_be_bytes()); // first_leaf_node
        buf[18..20].copy_from_slice(&512u16.to_be_bytes()); // node_size
        let hdr = BTreeHeader::from_bytes(&buf);
        assert_eq!(hdr.first_leaf_node, 42);
        assert_eq!(hdr.node_size, 512);
    }

    // ── sort_children_recursive ───────────────────────────────────────────────

    #[test]
    fn sort_children_recursive_sorts_names() {
        let mut root = TreeNode::new_directory("/".to_string());
        root.add_child(TreeNode::new_file("z.txt".to_string(), 0));
        root.add_child(TreeNode::new_file("a.txt".to_string(), 0));
        root.add_child(TreeNode::new_file("m.txt".to_string(), 0));
        sort_children_recursive(&mut root);
        let names: Vec<&str> = root.children.iter().map(|c| c.name.as_str()).collect();
        assert_eq!(names, ["a.txt", "m.txt", "z.txt"]);
    }

    // ── detect / parse_volume_header: too-short image ─────────────────────────

    #[test]
    fn detect_too_short_image_returns_too_short() {
        // Image of exactly 1024 bytes; seek to 1024 succeeds but reading 2 bytes fails.
        let buf = vec![0u8; 1024];
        let mut c = Cursor::new(&buf);
        assert!(matches!(detect(&mut c), Err(Error::TooShort)));
    }

    #[test]
    fn parse_volume_header_too_short_image_returns_too_short() {
        let buf = vec![0u8; 1024];
        let mut c = Cursor::new(&buf);
        assert!(matches!(parse_volume_header(&mut c), Err(Error::TooShort)));
    }

    // ── detect_and_parse: empty catalog (no extents) ──────────────────────────

    #[test]
    fn detect_and_parse_empty_catalog_returns_empty_root() {
        // cat_file has all-zero extents → first_extent_offset returns None → empty tree.
        let buf = make_volume_header_bytes(HFS_PLUS_MAGIC, 4, 0, 0, 4096);
        let mut c = Cursor::new(&buf);
        let tree = detect_and_parse(&mut c).expect("empty catalog should succeed");
        assert_eq!(tree.name, "/");
        assert!(tree.children.is_empty());
    }

    // ── detect_and_parse: catalog B-tree header node validation ──────────────

    /// Build a minimal HFS+ image with a catalog file at block 4 (byte 2048),
    /// containing a 120-byte header node with configurable fields.
    fn make_hfsplus_with_btree_header(
        node_kind: u8,
        num_records: u16,
        btree_node_size: u16,
        first_leaf: u32,
    ) -> Vec<u8> {
        let block_size = 512u32;
        let cat_block = 4u32;
        let mut img = vec![0u8; 2168]; // 2048 + 120 bytes

        // Volume header at 1024
        let h = &mut img[1024..1536];
        h[0..2].copy_from_slice(&HFS_PLUS_MAGIC.to_be_bytes());
        h[2..4].copy_from_slice(&4u16.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        // cat_file.extents[0] at VH+272+16 and VH+272+20: (cat_block, 1)
        h[288..292].copy_from_slice(&cat_block.to_be_bytes()); // start_block
        h[292..296].copy_from_slice(&1u32.to_be_bytes()); // block_count

        // Catalog at byte 2048: 14-byte node descriptor + 106-byte BTHeaderRec
        let cat = &mut img[2048..2168];
        cat[8] = node_kind; // node_kind
        cat[10..12].copy_from_slice(&num_records.to_be_bytes()); // num_records
        cat[24..28].copy_from_slice(&first_leaf.to_be_bytes()); // BTHeaderRec.first_leaf_node
        cat[32..34].copy_from_slice(&btree_node_size.to_be_bytes()); // BTHeaderRec.node_size

        img
    }

    #[test]
    fn detect_and_parse_bad_catalog_node_kind_returns_error() {
        let img = make_hfsplus_with_btree_header(0x00, 1, 512, 0);
        let mut c = Cursor::new(&img);
        assert!(matches!(detect_and_parse(&mut c), Err(Error::BadCatalog)));
    }

    #[test]
    fn detect_and_parse_header_node_zero_records_returns_error() {
        let img = make_hfsplus_with_btree_header(BTREE_HEADER_NODE, 0, 512, 0);
        let mut c = Cursor::new(&img);
        assert!(matches!(detect_and_parse(&mut c), Err(Error::TooShort)));
    }

    #[test]
    fn detect_and_parse_catalog_node_size_too_small_returns_error() {
        let img = make_hfsplus_with_btree_header(BTREE_HEADER_NODE, 1, 256, 0);
        let mut c = Cursor::new(&img);
        assert!(matches!(detect_and_parse(&mut c), Err(Error::BadCatalog)));
    }

    #[test]
    fn detect_and_parse_empty_leaf_chain_returns_empty_root() {
        // first_leaf_node = 0 → empty catalog, returns empty tree immediately.
        let img = make_hfsplus_with_btree_header(BTREE_HEADER_NODE, 1, 512, 0);
        let mut c = Cursor::new(&img);
        let tree = detect_and_parse(&mut c).expect("empty leaf chain should succeed");
        assert!(tree.children.is_empty());
    }

    // ── parse_leaf_node_records: edge cases ───────────────────────────────────

    #[test]
    fn parse_leaf_node_unknown_record_type_skipped() {
        let key = make_catalog_key(HFS_ROOT_FOLDER_CNID, "x");
        let mut rec = vec![0u8; 20];
        rec[0..2].copy_from_slice(&0xFFFFu16.to_be_bytes()); // unknown record type
        let node = make_leaf_node(&key, &rec);
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty(), "unknown record type must be skipped");
    }

    #[test]
    fn parse_leaf_node_rec_start_past_node_size_skipped() {
        let mut node = vec![0u8; 512];
        // Offset table at node[510..512]; write rec_start = 600 (> 512 = node_size)
        node[510..512].copy_from_slice(&600u16.to_be_bytes());
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty(), "out-of-bounds rec_start must be skipped");
    }

    #[test]
    fn parse_leaf_node_rec_data_under_six_bytes_skipped() {
        let mut node = vec![0u8; 512];
        // rec_start = 508 → rec_data = node[508..] = 4 bytes < 6
        node[510..512].copy_from_slice(&508u16.to_be_bytes());
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty());
    }

    #[test]
    fn parse_leaf_node_key_length_under_six_skipped() {
        let mut node = vec![0u8; 512];
        // rec_start = 14; key_length = 3 < 6 → skip
        node[510..512].copy_from_slice(&14u16.to_be_bytes());
        node[14..16].copy_from_slice(&3u16.to_be_bytes()); // key_length
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty());
    }

    #[test]
    fn parse_leaf_node_folder_record_too_short_skipped() {
        // Place rec_start=500 so rec_data=node[500..512]=12 bytes.
        // key_length=6 (parent4+namelen2, name_len=0).
        // data_off=(2+6+1)&!1=8; data=rec_data[8..]=4 bytes < 12 → skip.
        let node_size = 512usize;
        let mut node = vec![0u8; node_size];
        let rec_start = 500usize;
        node[510..512].copy_from_slice(&(rec_start as u16).to_be_bytes());
        node[500..502].copy_from_slice(&6u16.to_be_bytes()); // key_length=6
        node[502..506].copy_from_slice(&HFS_ROOT_FOLDER_CNID.to_be_bytes()); // parent_cnid
                                                                             // name_length=0 at [506..508] (stays zero)
                                                                             // data at offset 8: node[508..512] = 4 bytes; record_type=FOLDER
        node[508..510].copy_from_slice(&RECORD_TYPE_FOLDER.to_be_bytes());
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty(), "short folder record data must be skipped");
    }

    #[test]
    fn parse_leaf_node_file_record_too_short_skipped() {
        // Place rec_start=490 so rec_data=node[490..512]=22 bytes.
        // key_length=6, data_off=8; data=rec_data[8..]=14 bytes < 168 → skip.
        let node_size = 512usize;
        let mut node = vec![0u8; node_size];
        let rec_start = 490usize;
        node[510..512].copy_from_slice(&(rec_start as u16).to_be_bytes());
        node[490..492].copy_from_slice(&6u16.to_be_bytes()); // key_length=6
        node[492..496].copy_from_slice(&HFS_ROOT_FOLDER_CNID.to_be_bytes()); // parent_cnid
                                                                             // name_length=0 at [496..498] (stays zero)
                                                                             // data at offset 8: node[498..512] = 14 bytes; record_type=FILE
        node[498..500].copy_from_slice(&RECORD_TYPE_FILE.to_be_bytes());
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty(), "short file record data must be skipped");
    }

    #[test]
    fn parse_leaf_node_file_multi_extent_no_location() {
        // File with two extents → is_single_extent() = false → file_location = None.
        let key = make_catalog_key(HFS_ROOT_FOLDER_CNID, "big.dat");
        let mut rec = vec![0u8; 248];
        rec[0..2].copy_from_slice(&RECORD_TYPE_FILE.to_be_bytes());
        rec[8..12].copy_from_slice(&99u32.to_be_bytes()); // cnid
        let fork_off = 88;
        rec[fork_off..fork_off + 8].copy_from_slice(&4096u64.to_be_bytes()); // logical_size
        rec[fork_off + 12..fork_off + 16].copy_from_slice(&4u32.to_be_bytes()); // total_blocks=4
        rec[fork_off + 16..fork_off + 20].copy_from_slice(&10u32.to_be_bytes()); // extent[0].start
        rec[fork_off + 20..fork_off + 24].copy_from_slice(&2u32.to_be_bytes()); // extent[0].count=2
        rec[fork_off + 24..fork_off + 28].copy_from_slice(&20u32.to_be_bytes()); // extent[1].start
        rec[fork_off + 28..fork_off + 32].copy_from_slice(&2u32.to_be_bytes()); // extent[1].count=2
        let node = make_leaf_node(&key, &rec);
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert_eq!(out.len(), 1);
        if let CatalogRecord::File { file_location, .. } = &out[0] {
            assert!(
                file_location.is_none(),
                "multi-extent file should have no location"
            );
        } else {
            panic!("expected File record");
        }
    }

    // ── build_tree: subdirectory and orphan paths ─────────────────────────────

    #[test]
    fn build_tree_file_in_subdirectory() {
        // File inside a subdirectory: covers cnid_path and find_by_path_mut.
        let records = vec![
            CatalogRecord::Folder {
                parent_cnid: HFS_ROOT_FOLDER_CNID,
                name: "docs".to_string(),
                cnid: 10,
            },
            CatalogRecord::File {
                parent_cnid: 10,
                name: "readme.txt".to_string(),
                cnid: 11,
                file_length: 42,
                file_location: Some(8192),
            },
        ];
        let root = build_tree(&records, 512);
        assert_eq!(root.children.len(), 1);
        let dir = &root.children[0];
        assert!(dir.is_directory);
        assert_eq!(dir.name, "docs");
        assert_eq!(dir.children.len(), 1);
        assert_eq!(dir.children[0].name, "readme.txt");
    }

    #[test]
    fn build_tree_orphan_directory_goes_to_pending() {
        // Folder with unknown parent → lands in still_pending, silently dropped.
        let records = vec![CatalogRecord::Folder {
            parent_cnid: 9999, // no such parent in records
            name: "orphan".to_string(),
            cnid: 50,
        }];
        let root = build_tree(&records, 512);
        // Orphan subdirectory not attached to root.
        assert!(root.children.is_empty());
    }

    // ── read_catalog_leaf_records: leaf-walk loop ─────────────────────────────

    /// Build an HFS+ image with a catalog at block 4 (byte 2048) and one leaf
    /// node at index `first_leaf` inside the catalog area.
    fn make_hfsplus_with_leaf_node(
        leaf_node_kind: u8,
        leaf_f_link: u32,
        leaf_num_records: u16,
    ) -> Vec<u8> {
        let block_size = 512u32;
        let cat_block = 4u32;
        let node_size = 512usize;
        // cat_offset=2048; header node at 2048..2560; leaf node at 2560..3072
        let mut img = vec![0u8; 3072];

        let h = &mut img[1024..1536];
        h[0..2].copy_from_slice(&HFS_PLUS_MAGIC.to_be_bytes());
        h[2..4].copy_from_slice(&4u16.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        h[288..292].copy_from_slice(&cat_block.to_be_bytes());
        h[292..296].copy_from_slice(&1u32.to_be_bytes()); // block_count=1

        // Header node at 2048: first 120 bytes are node descriptor + BTHeaderRec
        let cat = &mut img[2048..2168];
        cat[8] = BTREE_HEADER_NODE;
        cat[10..12].copy_from_slice(&1u16.to_be_bytes()); // num_records=1
        cat[24..28].copy_from_slice(&1u32.to_be_bytes()); // first_leaf=1
        cat[32..34].copy_from_slice(&(node_size as u16).to_be_bytes()); // node_size=512

        // Leaf node at 2048 + 512 = 2560 (node index 1)
        let leaf = &mut img[2560..3072];
        leaf[0..4].copy_from_slice(&leaf_f_link.to_be_bytes()); // f_link
        leaf[8] = leaf_node_kind;
        leaf[10..12].copy_from_slice(&leaf_num_records.to_be_bytes());

        img
    }

    #[test]
    fn detect_and_parse_single_leaf_node_walks_chain() {
        // first_leaf=1, BTREE_LEAF_NODE, f_link=0, num_records=0.
        // Exercises the entire read_catalog_leaf_records loop body.
        let img = make_hfsplus_with_leaf_node(BTREE_LEAF_NODE, 0, 0);
        let mut c = Cursor::new(&img);
        let tree = detect_and_parse(&mut c).expect("single leaf node walk should succeed");
        assert!(tree.children.is_empty());
    }

    #[test]
    fn detect_and_parse_non_leaf_kind_in_chain_breaks() {
        // first_leaf=1, kind=0x00 (not LEAF), f_link=0 → enters the
        // `kind != BTREE_LEAF_NODE` branch and breaks (no records, empty tree).
        let img = make_hfsplus_with_leaf_node(0x00, 0, 0);
        let mut c = Cursor::new(&img);
        let tree = detect_and_parse(&mut c).expect("non-leaf kind with f_link=0 should succeed");
        assert!(tree.children.is_empty());
    }

    #[test]
    fn detect_and_parse_non_leaf_then_leaf_follows_f_link() {
        // Node 1: kind=0x00 (non-leaf), f_link=2 → lines 429-431 (continue to node 2).
        // Node 2: kind=BTREE_LEAF_NODE, f_link=0 → normal leaf parse, break.
        // Image: header at 2048..2560, node1 at 2560..3072, node2 at 3072..3584.
        let block_size = 512u32;
        let cat_block = 4u32;
        let node_size = 512usize;
        let mut img = vec![0u8; 3584];

        let h = &mut img[1024..1536];
        h[0..2].copy_from_slice(&HFS_PLUS_MAGIC.to_be_bytes());
        h[2..4].copy_from_slice(&4u16.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        h[288..292].copy_from_slice(&cat_block.to_be_bytes());
        h[292..296].copy_from_slice(&1u32.to_be_bytes());

        let cat = &mut img[2048..2168];
        cat[8] = BTREE_HEADER_NODE;
        cat[10..12].copy_from_slice(&1u16.to_be_bytes());
        cat[24..28].copy_from_slice(&1u32.to_be_bytes()); // first_leaf=1
        cat[32..34].copy_from_slice(&(node_size as u16).to_be_bytes());

        // Node 1 at 2560: non-leaf kind, f_link=2
        let node1 = &mut img[2560..3072];
        node1[0..4].copy_from_slice(&2u32.to_be_bytes()); // f_link=2
        node1[8] = 0x00; // not a leaf

        // Node 2 at 3072: leaf, f_link=0
        let node2 = &mut img[3072..3584];
        node2[0..4].copy_from_slice(&0u32.to_be_bytes()); // f_link=0
        node2[8] = BTREE_LEAF_NODE;
        node2[10..12].copy_from_slice(&0u16.to_be_bytes()); // num_records=0

        let mut c = Cursor::new(&img);
        let tree = detect_and_parse(&mut c).expect("non-leaf then leaf should succeed");
        assert!(tree.children.is_empty());
    }

    // ── parse_leaf_node_records: remaining skip paths ─────────────────────────

    #[test]
    fn parse_leaf_node_records_tiny_node_breaks_early() {
        // node_size=1, num_records=1: off_idx=saturating_sub(2)=0, 0+2=2 > 1 → break.
        let mut out = Vec::new();
        parse_leaf_node_records(&[0u8], 1, 4096, &mut out).unwrap();
        assert!(out.is_empty());
    }

    #[test]
    fn parse_leaf_node_name_extends_past_rec_data_skipped() {
        // rec_start=490, rec_data=22 bytes. key_length=6, name_len=10 →
        // name_bytes_len=20, 8+20=28 > 22 → skip (line 485).
        let mut node = vec![0u8; 512];
        node[510..512].copy_from_slice(&490u16.to_be_bytes()); // offset table
        node[490..492].copy_from_slice(&6u16.to_be_bytes()); // key_length=6
        node[492..496].copy_from_slice(&HFS_ROOT_FOLDER_CNID.to_be_bytes()); // parent_cnid
        node[496..498].copy_from_slice(&10u16.to_be_bytes()); // name_len=10 (=20 bytes)
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty());
    }

    #[test]
    fn parse_leaf_node_data_off_past_end_skipped() {
        // rec_start=459, rec_data=53 bytes. key_length=50, name_len=0 →
        // data_off=(2+50+1)&!1=52, 53 < 52+2=54 → skip (line 494).
        let mut node = vec![0u8; 512];
        node[510..512].copy_from_slice(&459u16.to_be_bytes()); // offset table
        node[459..461].copy_from_slice(&50u16.to_be_bytes()); // key_length=50
        node[461..465].copy_from_slice(&HFS_ROOT_FOLDER_CNID.to_be_bytes()); // parent_cnid
                                                                             // name_len=0 at [465..467] (stays zero)
        let mut out = Vec::new();
        parse_leaf_node_records(&node, 1, 4096, &mut out).unwrap();
        assert!(out.is_empty());
    }

    // ── build_tree: orphaned file covers find_by_path_mut None path ───────────

    #[test]
    fn build_tree_file_with_orphaned_grandparent() {
        // Folder A (cnid=10) has parent 9999 which is not in folder_map.
        // A is orphaned in Pass 4 (never attached to root).
        // File (parent=10) → cnid_path: get(10)=Some(("A",9999)), push "A",
        // cur=9999 (line 590), get(9999)=None → break (line 592), path=["A"].
        // find_by_path_mut(root, ["A"]): root has child "B" but not "A"
        // → condition false (line 565) → return None (line 567). File dropped.
        let records = vec![
            CatalogRecord::Folder {
                parent_cnid: HFS_ROOT_FOLDER_CNID,
                name: "B".to_string(),
                cnid: 20,
            },
            CatalogRecord::Folder {
                parent_cnid: 9999,
                name: "A".to_string(),
                cnid: 10,
            },
            CatalogRecord::File {
                parent_cnid: 10,
                name: "x.txt".to_string(),
                cnid: 30,
                file_length: 1,
                file_location: None,
            },
        ];
        let root = build_tree(&records, 512);
        // "B" is attached to root; "A" and "x.txt" are silently dropped.
        assert_eq!(root.children.len(), 1);
        assert_eq!(root.children[0].name, "B");
    }

    // ── read_catalog_leaf_records: TooShort and TooDeep paths ─────────────────

    #[test]
    fn detect_and_parse_leaf_node_read_too_short_returns_error() {
        // Image just large enough for header node but NOT the leaf node:
        // cat_offset=2048, header_node at 2048..2560, leaf at 2560 but image ends at 2560.
        // read_exact for the leaf → UnexpectedEof → TooShort.
        let block_size = 512u32;
        let cat_block = 4u32;
        let node_size = 512usize;
        let mut img = vec![0u8; 2560]; // ends exactly where leaf would start

        let h = &mut img[1024..1536];
        h[0..2].copy_from_slice(&HFS_PLUS_MAGIC.to_be_bytes());
        h[2..4].copy_from_slice(&4u16.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        h[288..292].copy_from_slice(&cat_block.to_be_bytes());
        h[292..296].copy_from_slice(&1u32.to_be_bytes());

        let cat = &mut img[2048..2168];
        cat[8] = BTREE_HEADER_NODE;
        cat[10..12].copy_from_slice(&1u16.to_be_bytes());
        cat[24..28].copy_from_slice(&1u32.to_be_bytes()); // first_leaf=1
        cat[32..34].copy_from_slice(&(node_size as u16).to_be_bytes());

        let mut c = Cursor::new(&img);
        assert!(matches!(detect_and_parse(&mut c), Err(Error::TooShort)));
    }

    #[test]
    fn detect_and_parse_leaf_chain_too_deep_returns_error() {
        // Two-leaf circular chain with logical_size=0 (max_nodes=1).
        // Iteration 1: leaf1 (f_link=2, LEAF, num_records=0). first_leaf=2.
        // Iteration 2: leaf2 (f_link=0, LEAF, num_records=0). first_leaf… wait,
        // visited=2 > max_nodes=1 → TooDeep before reading leaf2!
        //
        // Image: 2048 + 512 (header) + 512 (leaf1) + 512 (leaf2) = 3584 bytes.
        let block_size = 512u32;
        let cat_block = 4u32;
        let node_size = 512usize;
        let mut img = vec![0u8; 3584];

        let h = &mut img[1024..1536];
        h[0..2].copy_from_slice(&HFS_PLUS_MAGIC.to_be_bytes());
        h[2..4].copy_from_slice(&4u16.to_be_bytes());
        h[40..44].copy_from_slice(&block_size.to_be_bytes());
        h[288..292].copy_from_slice(&cat_block.to_be_bytes());
        h[292..296].copy_from_slice(&1u32.to_be_bytes());
        // logical_size stays zero → max_nodes = (0/512).min(MAX) + 1 = 1

        // Header node at 2048 (cat_offset)
        let cat = &mut img[2048..2168];
        cat[8] = BTREE_HEADER_NODE;
        cat[10..12].copy_from_slice(&1u16.to_be_bytes());
        cat[24..28].copy_from_slice(&1u32.to_be_bytes()); // first_leaf=1
        cat[32..34].copy_from_slice(&(node_size as u16).to_be_bytes());

        // Leaf node 1 at 2048 + 512 = 2560 (index 1): f_link=2
        let leaf1 = &mut img[2560..3072];
        leaf1[0..4].copy_from_slice(&2u32.to_be_bytes()); // f_link=2
        leaf1[8] = BTREE_LEAF_NODE;
        leaf1[10..12].copy_from_slice(&0u16.to_be_bytes()); // num_records=0

        // Leaf node 2 at 2048 + 1024 = 3072 (index 2): f_link=3 (points beyond image).
        // Iteration 3 checks visited=2 > max_nodes=1 → TooDeep before seeking to node 3.
        let leaf2 = &mut img[3072..3584];
        leaf2[0..4].copy_from_slice(&3u32.to_be_bytes()); // f_link=3
        leaf2[8] = BTREE_LEAF_NODE;

        let mut c = Cursor::new(&img);
        assert!(matches!(detect_and_parse(&mut c), Err(Error::TooDeep)));
    }
}