// Copyright 2024 Google LLC
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use crate::Ext4;
use crate::block_index::{FileBlockIndex, FsBlockIndex};
use crate::checksum::Checksum;
use crate::error::{CorruptKind, Ext4Error};
use crate::extent::Extent;
use crate::inode::{Inode, InodeIndex};
use crate::util::{
    read_u16le, read_u32le, u64_from_hilo, u64_to_hilo, usize_from_u32,
};
use alloc::vec;
use alloc::vec::Vec;
use core::num::NonZeroU32;

/// Find the child index to descend into for `block_index`.
///
/// Returns the index of the last internal node with `block_within_file <= block_index`.
fn find_child_index(
    nodes: &[ExtentInternalNode],
    block_index: FileBlockIndex,
) -> Option<usize> {
    let mut best_index = None;
    for (i, node) in nodes.iter().enumerate() {
        if node.block_within_file > block_index {
            break;
        }
        best_index = Some(i);
    }
    best_index
}

/// Size of each entry within an extent node (including the header
/// entry).
const ENTRY_SIZE_IN_BYTES: usize = 12;

const EXTENT_MAGIC: u16 = 0xf30a;

/// Header at the start of a node in an extent tree.
///
/// An extent tree is made up of nodes. Each node may be internal or
/// leaf. Leaf nodes contain `Extent`s. Internal nodes point at other
/// nodes.
///
/// Each node starts with a `NodeHeader` that includes the node's depth
/// (depth 0 is a leaf node) and the number of entries in the node.
#[derive(Copy, Clone)]
struct NodeHeader {
    /// Number of entries in this node, not including the header.
    num_entries: u16,

    /// Maximum number of entries in this node, not including the header.
    max_entries: u16,

    /// Depth of this node in the tree. Zero means it's a leaf node. The
    /// maximum depth is five.
    depth: u16,

    /// The generation number of this node. Used by lustre
    generation: u32,
}

/// Returns `(n + 1) * ENTRY_SIZE_IN_BYTES`.
///
/// The maximum value this returns is 786432.
fn add_one_mul_entry_size(n: u16) -> usize {
    // OK to unwrap: the maximum value of `n` is `2^16-1`, so the
    // maximum value of this sum is `2^16`. That fits in a `u32`, and we
    // assume `usize` is at least as big as a `u32`.
    let n_plus_one = usize::from(n).checked_add(1).unwrap();
    // OK to unwrap: `n_plus_one` is at most `2^16` and
    // `ENTRY_SIZE_IN_BYTES` is 12, so the maximum product is 786432,
    // which fits in a `u32`. We assume `usize` is at least as big as a
    // `u32`.
    n_plus_one.checked_mul(ENTRY_SIZE_IN_BYTES).unwrap()
}

impl NodeHeader {
    /// Size of the node, including the header.
    fn node_size_in_bytes(&self) -> usize {
        add_one_mul_entry_size(self.num_entries)
    }

    /// Offset of the node's extent data.
    ///
    /// Per `add_one_mul_entry_size`, the maximum value this returns is
    /// 786432.
    fn checksum_offset(&self) -> usize {
        add_one_mul_entry_size(self.max_entries)
    }
}

impl NodeHeader {
    /// Read a `NodeHeader` from a byte slice.
    fn from_bytes(data: &[u8], inode: InodeIndex) -> Result<Self, Ext4Error> {
        if data.len() < ENTRY_SIZE_IN_BYTES {
            return Err(CorruptKind::ExtentNotEnoughData(inode).into());
        }

        let eh_magic = read_u16le(data, 0);
        let eh_entries = read_u16le(data, 2);
        let eh_max = read_u16le(data, 4);
        let eh_depth = read_u16le(data, 6);
        let eh_generation = read_u32le(data, 8);

        if eh_magic != EXTENT_MAGIC {
            return Err(CorruptKind::ExtentMagic(inode).into());
        }

        if eh_depth > 5 {
            return Err(CorruptKind::ExtentDepth(inode).into());
        }

        Ok(Self {
            depth: eh_depth,
            num_entries: eh_entries,
            max_entries: eh_max,
            generation: eh_generation,
        })
    }

    fn to_bytes(self) -> [u8; ENTRY_SIZE_IN_BYTES] {
        let mut bytes = [0u8; ENTRY_SIZE_IN_BYTES];
        bytes[0..2].copy_from_slice(&EXTENT_MAGIC.to_le_bytes());
        bytes[2..4].copy_from_slice(&self.num_entries.to_le_bytes());
        bytes[4..6].copy_from_slice(&self.max_entries.to_le_bytes());
        bytes[6..8].copy_from_slice(&self.depth.to_le_bytes());
        bytes[8..12].copy_from_slice(&self.generation.to_le_bytes());
        bytes
    }
}

#[derive(Copy, Clone)]
struct ExtentInternalNode {
    /// Offset of the block within the file.
    pub(crate) block_within_file: FileBlockIndex,

    /// This is the actual block within the filesystem.
    pub(crate) block: FsBlockIndex,
}

impl ExtentInternalNode {
    pub(crate) fn from_bytes(
        data: &[u8],
        inode: InodeIndex,
    ) -> Result<Self, Ext4Error> {
        if data.len() < ENTRY_SIZE_IN_BYTES {
            return Err(CorruptKind::ExtentNotEnoughData(inode).into());
        }

        let ei_block = read_u32le(data, 0);
        let (ei_start_lo, ei_start_hi) =
            (read_u32le(data, 4), read_u16le(data, 8));
        let ei_start = u64_from_hilo(u32::from(ei_start_hi), ei_start_lo);

        Ok(Self {
            block_within_file: ei_block,
            block: ei_start,
        })
    }

    pub(crate) fn to_bytes(self) -> [u8; 12] {
        let mut bytes = [0u8; 12];
        bytes[0..4].copy_from_slice(&self.block_within_file.to_le_bytes());
        let (ei_start_hi, ei_start_lo) = u64_to_hilo(self.block);
        let ei_start_hi =
            u16::try_from(ei_start_hi).expect("block must fit in 48 bits");
        bytes[4..8].copy_from_slice(&ei_start_lo.to_le_bytes());
        bytes[8..10].copy_from_slice(&ei_start_hi.to_le_bytes());
        // The last two bytes are unused.
        bytes
    }
}

#[derive(Clone)]
enum ExtentNodeEntries {
    Internal(Vec<ExtentInternalNode>),
    Leaf(Vec<Extent>),
}

impl ExtentNodeEntries {
    fn from_bytes(
        data: &[u8],
        header: &NodeHeader,
        inode: InodeIndex,
    ) -> Result<Self, Ext4Error> {
        if header.depth == 0 {
            let mut entries = Vec::with_capacity(usize_from_u32(u32::from(
                header.num_entries,
            )));
            for i in 0..header.num_entries {
                let offset = add_one_mul_entry_size(i);
                let entry = Extent::from_bytes(
                    &data[offset
                        ..offset.checked_add(ENTRY_SIZE_IN_BYTES).unwrap()],
                );
                entries.push(entry);
            }
            Ok(Self::Leaf(entries))
        } else {
            let mut entries = Vec::with_capacity(usize_from_u32(u32::from(
                header.num_entries,
            )));
            for i in 0..header.num_entries {
                let offset = add_one_mul_entry_size(i);
                let entry = ExtentInternalNode::from_bytes(
                    &data[offset
                        ..offset.checked_add(ENTRY_SIZE_IN_BYTES).unwrap()],
                    inode,
                )?;
                entries.push(entry);
            }
            Ok(Self::Internal(entries))
        }
    }
}

#[derive(Clone)]
pub(crate) struct ExtentNode {
    block: Option<FsBlockIndex>,
    header: NodeHeader,
    entries: ExtentNodeEntries,
}

impl ExtentNode {
    fn from_bytes(
        block: Option<FsBlockIndex>,
        data: &[u8],
        inode: InodeIndex,
        checksum_base: Checksum,
        ext4: &Ext4,
    ) -> Result<Self, Ext4Error> {
        let header = NodeHeader::from_bytes(data, inode)?;
        let entries = ExtentNodeEntries::from_bytes(data, &header, inode)?;
        if ext4.has_metadata_checksums() {
            let checksum_offset = header.checksum_offset();
            if data.len() < checksum_offset.checked_add(4).unwrap() {
                return Err(CorruptKind::ExtentNotEnoughData(inode).into());
            }
            let expected_checksum = read_u32le(data, checksum_offset);
            let mut checksum = checksum_base.clone();
            checksum.update(&data[..checksum_offset]);
            if checksum.finalize() != expected_checksum {
                return Err(CorruptKind::ExtentChecksum(inode).into());
            }
        }
        Ok(Self {
            block,
            header,
            entries,
        })
    }

    pub(crate) fn to_bytes(
        &self,
        checksum_base: Option<Checksum>,
    ) -> Result<Vec<u8>, Ext4Error> {
        let mut bytes = Vec::with_capacity(
            self.header.checksum_offset().checked_add(4).unwrap(),
        );
        bytes.extend_from_slice(&self.header.to_bytes());
        match &self.entries {
            ExtentNodeEntries::Leaf(extents) => {
                for extent in extents {
                    bytes.extend_from_slice(&extent.to_bytes()?);
                }
            }
            ExtentNodeEntries::Internal(internal_nodes) => {
                for internal_node in internal_nodes {
                    bytes.extend_from_slice(&internal_node.to_bytes());
                }
            }
        }
        if let Some(checksum_base) = checksum_base {
            let mut checksum = checksum_base.clone();
            checksum.update(&bytes);
            bytes.extend_from_slice(&checksum.finalize().to_le_bytes());
        }
        Ok(bytes)
    }

    pub(crate) fn push_extent(&mut self, extent: Extent) -> Result<(), ()> {
        match &mut self.entries {
            ExtentNodeEntries::Leaf(extents) => {
                if extents.len()
                    >= usize_from_u32(u32::from(self.header.max_entries))
                {
                    return Err(());
                }
                extents.push(extent);
                self.header.num_entries =
                    self.header.num_entries.checked_add(1).unwrap();
                Ok(())
            }
            ExtentNodeEntries::Internal(_) => Err(()),
        }
    }

    #[maybe_async::maybe_async]
    pub(crate) async fn write(&self, ext4: &Ext4) -> Result<(), Ext4Error> {
        if let Some(block) = self.block {
            let bytes = self.to_bytes(None)?;
            ext4.write_to_block(block, 0, &bytes).await?;
        }
        Ok(())
    }
}

/// Iterator of an inode's extent tree.
pub(crate) struct ExtentTree {
    ext4: Ext4,
    inode: InodeIndex,
    node: ExtentNode,
    checksum_base: Checksum,
}

impl ExtentTree {
    pub(crate) fn initialize(
        inode: &Inode,
        ext4: Ext4,
    ) -> Result<Self, Ext4Error> {
        // TODO: linux claims some initial blocks for the extent tree
        Ok(Self {
            ext4,
            inode: inode.index,
            node: ExtentNode {
                block: None,
                header: NodeHeader {
                    num_entries: 0,
                    max_entries: 4,
                    depth: 0,
                    generation: 0,
                },
                entries: ExtentNodeEntries::Leaf(vec![]),
            },
            checksum_base: inode.checksum_base().clone(),
        })
    }

    pub(crate) fn to_bytes(&self) -> Result<[u8; 60], Ext4Error> {
        let bytes = self.node.to_bytes(None)?;
        let mut result = [0u8; 60];
        result[..bytes.len()].copy_from_slice(&bytes);
        Ok(result)
    }

    pub(crate) fn from_inode(
        inode: &Inode,
        ext4: Ext4,
    ) -> Result<Self, Ext4Error> {
        let header = NodeHeader::from_bytes(&inode.inline_data(), inode.index)?;
        let entries = ExtentNodeEntries::from_bytes(
            &inode.inline_data(),
            &header,
            inode.index,
        )?;
        assert_eq!(header.max_entries, 4);
        Ok(Self {
            ext4,
            inode: inode.index,
            node: ExtentNode {
                block: None,
                header,
                entries,
            },
            checksum_base: inode.checksum_base().clone(),
        })
    }

    /// Get the extent that contains the given block index, if any.
    #[maybe_async::maybe_async]
    pub(crate) async fn find_extent(
        &self,
        block_index: FileBlockIndex,
    ) -> Result<Option<Extent>, Ext4Error> {
        let mut node = self.node.clone();
        loop {
            match &node.entries {
                ExtentNodeEntries::Leaf(extents) => {
                    for extent in extents {
                        if block_index >= extent.block_within_file
                            && block_index
                                < extent
                                    .block_within_file
                                    .checked_add(FileBlockIndex::from(
                                        extent.num_blocks,
                                    ))
                                    .unwrap()
                        {
                            return Ok(Some(*extent));
                        }
                    }
                    return Ok(None);
                }
                ExtentNodeEntries::Internal(internal_nodes) => {
                    let next_node_index =
                        match find_child_index(internal_nodes, block_index) {
                            Some(i) => i,
                            None => return Ok(None),
                        };
                    let next_node_block = internal_nodes[next_node_index].block;
                    let next_node_data =
                        self.ext4.read_block(next_node_block).await?;
                    node = ExtentNode::from_bytes(
                        Some(next_node_block),
                        &next_node_data,
                        self.inode,
                        self.checksum_base.clone(),
                        &self.ext4,
                    )?;
                }
            }
        }
    }

    #[maybe_async::maybe_async]
    pub(crate) async fn get_block(
        &self,
        block_index: FileBlockIndex,
    ) -> Result<FsBlockIndex, Ext4Error> {
        if let Some(extent) = self.find_extent(block_index).await? {
            let offset_within_extent =
                block_index.checked_sub(extent.block_within_file).unwrap();
            Ok(extent
                .start_block
                .checked_add(FsBlockIndex::from(offset_within_extent))
                .unwrap())
        } else {
            Ok(0)
        }
    }

    #[maybe_async::maybe_async]
    pub(crate) async fn allocate_block(
        &mut self,
        block_index: FileBlockIndex,
        inode_index: InodeIndex,
    ) -> Result<(FsBlockIndex, u32), Ext4Error> {
        if let Some(extent) = self.find_extent(block_index).await? {
            let offset_within_extent =
                block_index.checked_sub(extent.block_within_file).unwrap();
            return Ok((
                extent
                    .start_block
                    .checked_add(FsBlockIndex::from(offset_within_extent))
                    .unwrap(),
                0,
            ));
        }

        let new_block =
            self.ext4.alloc_block(NonZeroU32::new(1).unwrap()).await?;

        let extent = Extent {
            block_within_file: block_index,
            num_blocks: 1,
            start_block: new_block,
            is_initialized: true,
        };

        let metadata_blocks = match self.insert_extent(extent).await {
            Ok(metadata_blocks) => metadata_blocks,
            Err(e) => {
                self.ext4.free_block(new_block).await?;
                return Err(e);
            }
        };

        Ok((new_block, metadata_blocks))
    }

    /// Find the previous/next extents that border a block.
    ///
    /// Extents cover half-open ranges: `[start, start + num_blocks)`.
    ///
    /// Returns:
    /// - If `block_index` lies inside an extent, returns `(Some(extent), Some(extent))`.
    /// - Otherwise, `prev` is the last extent with `end <= block_index` and `next` is the first
    ///   extent with `start > block_index`.
    #[maybe_async::maybe_async]
    async fn find_prev_next(
        &self,
        block_index: FileBlockIndex,
    ) -> Result<(Option<Extent>, Option<Extent>), Ext4Error> {
        fn leaf_prev_next(
            extents: &[Extent],
            block_index: FileBlockIndex,
        ) -> (Option<Extent>, Option<Extent>) {
            let mut prev: Option<Extent> = None;
            let mut next: Option<Extent> = None;

            for extent in extents {
                let start = extent.block_within_file;
                let end = start
                    .checked_add(FileBlockIndex::from(extent.num_blocks))
                    .unwrap();

                if block_index >= start && block_index < end {
                    return (Some(*extent), Some(*extent));
                }

                if end <= block_index {
                    prev = Some(*extent);
                    continue;
                }

                if start > block_index {
                    next = Some(*extent);
                    break;
                }
            }

            (prev, next)
        }

        #[maybe_async::maybe_async]
        async fn leftmost_leaf_first_extent(
            tree: &ExtentTree,
            mut node: ExtentNode,
        ) -> Result<Option<Extent>, Ext4Error> {
            loop {
                match &node.entries {
                    ExtentNodeEntries::Leaf(extents) => {
                        return Ok(extents.first().copied());
                    }
                    ExtentNodeEntries::Internal(internal_nodes) => {
                        if internal_nodes.is_empty() {
                            return Ok(None);
                        }
                        let next_node_block = internal_nodes[0].block;
                        let next_node_data =
                            tree.ext4.read_block(next_node_block).await?;
                        node = ExtentNode::from_bytes(
                            Some(next_node_block),
                            &next_node_data,
                            tree.inode,
                            tree.checksum_base.clone(),
                            &tree.ext4,
                        )?;
                    }
                }
            }
        }

        #[maybe_async::maybe_async]
        async fn rightmost_leaf_last_extent(
            tree: &ExtentTree,
            mut node: ExtentNode,
        ) -> Result<Option<Extent>, Ext4Error> {
            loop {
                match &node.entries {
                    ExtentNodeEntries::Leaf(extents) => {
                        return Ok(extents.last().copied());
                    }
                    ExtentNodeEntries::Internal(internal_nodes) => {
                        if internal_nodes.is_empty() {
                            return Ok(None);
                        }
                        let next_node_block =
                            internal_nodes.last().unwrap().block;
                        let next_node_data =
                            tree.ext4.read_block(next_node_block).await?;
                        node = ExtentNode::from_bytes(
                            Some(next_node_block),
                            &next_node_data,
                            tree.inode,
                            tree.checksum_base.clone(),
                            &tree.ext4,
                        )?;
                    }
                }
            }
        }

        // Descend to the leaf that would contain `block_index`, tracking the path of internal
        // nodes so we can find the adjacent leaf if the neighbor is not in this leaf.
        let mut node = self.node.clone();
        let mut internal_path: Vec<(ExtentNode, usize)> = Vec::new();
        loop {
            match &node.entries {
                ExtentNodeEntries::Leaf(extents) => {
                    if extents.is_empty() {
                        return Ok((None, None));
                    }

                    let (mut prev, mut next) =
                        leaf_prev_next(extents, block_index);

                    // If we found the containing extent, we’re done.
                    if matches!((&prev, &next), (Some(p), Some(n)) if p == n) {
                        return Ok((prev, next));
                    }

                    // If a neighbor is missing, attempt to find it in an adjacent leaf by walking
                    // up the internal path and choosing a sibling subtree.
                    if prev.is_none() {
                        // Find previous leaf: go up until we can take a left sibling.
                        let mut i = internal_path.len();
                        while i > 0 {
                            i = i.checked_sub(1).unwrap();
                            let (parent, child_index) =
                                internal_path[i].clone();
                            if let ExtentNodeEntries::Internal(internal_nodes) =
                                &parent.entries
                            {
                                if child_index > 0 {
                                    let sibling_block = internal_nodes
                                        [child_index.checked_sub(1).unwrap()]
                                    .block;
                                    let sibling_data = self
                                        .ext4
                                        .read_block(sibling_block)
                                        .await?;
                                    let sibling_node = ExtentNode::from_bytes(
                                        Some(sibling_block),
                                        &sibling_data,
                                        self.inode,
                                        self.checksum_base.clone(),
                                        &self.ext4,
                                    )?;
                                    prev = rightmost_leaf_last_extent(
                                        self,
                                        sibling_node,
                                    )
                                    .await?;
                                    break;
                                }
                            }
                        }
                    }

                    if next.is_none() {
                        // Find next leaf: go up until we can take a right sibling.
                        let mut i = internal_path.len();
                        while i > 0 {
                            i = i.checked_sub(1).unwrap();
                            let (parent, child_index) =
                                internal_path[i].clone();
                            if let ExtentNodeEntries::Internal(internal_nodes) =
                                &parent.entries
                            {
                                if child_index.checked_add(1).unwrap()
                                    < internal_nodes.len()
                                {
                                    let sibling_block = internal_nodes
                                        [child_index.checked_add(1).unwrap()]
                                    .block;
                                    let sibling_data = self
                                        .ext4
                                        .read_block(sibling_block)
                                        .await?;
                                    let sibling_node = ExtentNode::from_bytes(
                                        Some(sibling_block),
                                        &sibling_data,
                                        self.inode,
                                        self.checksum_base.clone(),
                                        &self.ext4,
                                    )?;
                                    next = leftmost_leaf_first_extent(
                                        self,
                                        sibling_node,
                                    )
                                    .await?;
                                    break;
                                }
                            }
                        }
                    }

                    return Ok((prev, next));
                }
                ExtentNodeEntries::Internal(internal_nodes) => {
                    let next_node_index =
                        match find_child_index(internal_nodes, block_index) {
                            Some(i) => i,
                            None => {
                                // Per `find_extent`, if there is no internal node key <= block, we
                                // treat as “not found”. We can still provide `next` by taking the first
                                // extent in the leftmost subtree.
                                let next =
                                    leftmost_leaf_first_extent(self, node)
                                        .await?;
                                return Ok((None, next));
                            }
                        };

                    internal_path.push((node.clone(), next_node_index));

                    let next_node_block = internal_nodes[next_node_index].block;
                    let next_node_data =
                        self.ext4.read_block(next_node_block).await?;
                    node = ExtentNode::from_bytes(
                        Some(next_node_block),
                        &next_node_data,
                        self.inode,
                        self.checksum_base.clone(),
                        &self.ext4,
                    )?;
                }
            }
        }
    }

    /// Insert a new extent. The new extent must not overlap existing extents.
    /// This will error if the new extent overlaps existing extents.
    #[maybe_async::maybe_async]
    pub(crate) async fn insert_extent(
        &mut self,
        new_extent: Extent,
    ) -> Result<u32, Ext4Error> {
        // Only handle the simplest case for now: the root node is an inline leaf.
        if self.node.header.depth != 0 {
            todo!()
        }

        let ExtentNodeEntries::Leaf(extents) = &mut self.node.entries else {
            unreachable!();
        };

        // Empty tree: just insert.
        if extents.is_empty() {
            if 1 > usize_from_u32(u32::from(self.node.header.max_entries)) {
                return Err(Ext4Error::NoSpace);
            }
            extents.push(new_extent);
            self.node.header.num_entries = 1;
            return Ok(0);
        }

        let new_start = new_extent.block_within_file;
        let new_end = new_start
            .checked_add(FileBlockIndex::from(new_extent.num_blocks))
            .unwrap();

        // Find insertion index (keep sorted by file-block start).
        let mut insert_at = extents.len();
        for (i, e) in extents.iter().enumerate() {
            if e.block_within_file > new_start {
                insert_at = i;
                break;
            }
        }

        // Check overlap with previous extent.
        if insert_at > 0 {
            let prev = extents[insert_at.checked_sub(1).unwrap()];
            let prev_start = prev.block_within_file;
            let prev_end = prev_start
                .checked_add(FileBlockIndex::from(prev.num_blocks))
                .unwrap();
            if new_start < prev_end {
                return Err(CorruptKind::ExtentBlock(self.inode).into());
            }
        }

        // Check overlap with next extent.
        if insert_at < extents.len() {
            let next = extents[insert_at];
            let next_start = next.block_within_file;
            if new_end > next_start {
                return Err(CorruptKind::ExtentBlock(self.inode).into());
            }
        }

        // If we can't merge with a neighbor, we need an extra slot.
        let can_merge_left = if insert_at > 0 {
            let left = extents[insert_at.checked_sub(1).unwrap()];
            let left_end = left
                .block_within_file
                .checked_add(FileBlockIndex::from(left.num_blocks))
                .unwrap();
            let left_phys_end = left
                .start_block
                .checked_add(FsBlockIndex::from(u32::from(left.num_blocks)))
                .unwrap();
            left_end == new_start
                && left_phys_end == new_extent.start_block
                && left.is_initialized == new_extent.is_initialized
        } else {
            false
        };

        let can_merge_right = if insert_at < extents.len() {
            let right = extents[insert_at];
            let phys_end = new_extent
                .start_block
                .checked_add(FsBlockIndex::from(u32::from(
                    new_extent.num_blocks,
                )))
                .unwrap();
            new_end == right.block_within_file
                && phys_end == right.start_block
                && right.is_initialized == new_extent.is_initialized
        } else {
            false
        };

        let max_entries =
            usize_from_u32(u32::from(self.node.header.max_entries));
        let needs_new_slot = !can_merge_left && !can_merge_right;
        if needs_new_slot && extents.len() >= max_entries {
            return Err(Ext4Error::NoSpace);
        }

        // Apply: merge where possible, otherwise insert.
        if can_merge_left {
            // Extend left to include new_extent.
            // Copy out the right neighbor (if any) before we take a mutable borrow of `extents`.
            let right_for_possible_merge = if can_merge_right {
                Some(extents[insert_at])
            } else {
                None
            };

            let left = &mut extents[insert_at.checked_sub(1).unwrap()];
            let new_len = (u32::from(left.num_blocks))
                .checked_add(u32::from(new_extent.num_blocks))
                .ok_or(Ext4Error::NoSpace)?;
            left.num_blocks = u16::try_from(new_len)
                .map_err(|_| CorruptKind::ExtentBlock(self.inode))?;

            // Maybe also merge with right neighbor now.
            if let Some(right) = right_for_possible_merge {
                // After merging into left, right is still at index insert_at.
                let left_phys_end = left
                    .start_block
                    .checked_add(FsBlockIndex::from(u32::from(left.num_blocks)))
                    .unwrap();
                let left_end = left
                    .block_within_file
                    .checked_add(FileBlockIndex::from(left.num_blocks))
                    .unwrap();
                if left_end == right.block_within_file
                    && left_phys_end == right.start_block
                    && left.is_initialized == right.is_initialized
                {
                    let combined = (u32::from(left.num_blocks))
                        .checked_add(u32::from(right.num_blocks))
                        .ok_or(Ext4Error::NoSpace)?;
                    left.num_blocks = u16::try_from(combined)
                        .map_err(|_| CorruptKind::ExtentBlock(self.inode))?;
                    extents.remove(insert_at);
                }
            }
        } else if can_merge_right {
            // Merge into right by extending it to the left.
            let right = &mut extents[insert_at];
            right.block_within_file = new_start;
            right.start_block = new_extent.start_block;
            let new_len = (u32::from(right.num_blocks))
                .checked_add(u32::from(new_extent.num_blocks))
                .ok_or(Ext4Error::NoSpace)?;
            right.num_blocks = u16::try_from(new_len)
                .map_err(|_| CorruptKind::ExtentBlock(self.inode))?;
        } else {
            extents.insert(insert_at, new_extent);
        }

        self.node.header.num_entries = u16::try_from(extents.len()).unwrap();
        Ok(0)
    }

    /// Remove all extents that overlap file-block range [start, start+num_blocks)
    /// and return any freed [`FsBlockIndex`] ranges (so caller can free blocks).
    #[maybe_async::maybe_async]
    pub(crate) async fn remove_extent_range(
        &mut self,
        start: FileBlockIndex,
        num_blocks: u32,
    ) -> Result<Vec<(FsBlockIndex, u32)>, Ext4Error> {
        if num_blocks == 0 {
            return Ok(Vec::new());
        }

        // Ensure the range boundaries align with extent boundaries so we can
        // remove whole extents safely.
        let end = start.checked_add(num_blocks).ok_or(Ext4Error::NoSpace)?;
        // Splitting at `start` is needed if we’re removing from the middle of an extent.
        // Splitting at `end` is needed if we’re removing the tail of an extent.
        // If there is no extent at those positions, split is a no-op.
        let _ = self.split_extent_at(start).await;
        let _ = self.split_extent_at(end).await;

        // Current implementation supports the inline root leaf case, which is
        // what this crate currently constructs (max_entries=4, depth=0).
        if self.node.header.depth != 0 {
            // Conservative: avoid corrupting on-disk structures until full tree
            // editing supports internal nodes.
            todo!("remove_extent_range for non-leaf extent trees");
        }

        let ExtentNodeEntries::Leaf(extents) = &mut self.node.entries else {
            unreachable!();
        };

        let mut freed: Vec<(FsBlockIndex, u32)> = Vec::new();

        // Remove any extents that overlap [start, end).
        let mut i = 0usize;
        while i < extents.len() {
            let e = extents[i];
            let e_start = e.block_within_file;
            let e_end = e_start
                .checked_add(FileBlockIndex::from(e.num_blocks))
                .unwrap();

            let overlaps = e_start < end && e_end > start;
            if overlaps {
                // After splitting above, any overlap should be full containment.
                // Still be defensive: compute the intersection and only free that.
                let inter_start = core::cmp::max(e_start, start);
                let inter_end = core::cmp::min(e_end, end);
                let inter_len = inter_end.checked_sub(inter_start).unwrap();
                let phys_start = e
                    .start_block
                    .checked_add(FsBlockIndex::from(
                        inter_start.checked_sub(e_start).unwrap(),
                    ))
                    .unwrap();
                freed.push((phys_start, inter_len));

                // If the whole extent lies inside the removal range, drop it.
                // With boundary splits, that should be the common case.
                if e_start >= start && e_end <= end {
                    extents.remove(i);
                    continue;
                }
            }
            i = i.checked_add(1).unwrap();
        }

        self.node.header.num_entries = u16::try_from(extents.len()).unwrap();
        Ok(freed)
    }

    /// Split an existing extent so that there's a boundary at `split_block_within_file`.
    /// If split_block equals extent.block_within_file or end, it's a no-op.
    /// Returns Err if extent not found.
    #[maybe_async::maybe_async]
    async fn split_extent_at(
        &mut self,
        split_block_within_file: FileBlockIndex,
    ) -> Result<(), Ext4Error> {
        /// Split an extent within a leaf vector.
        /// Returns (did_split, leaf_first_extent_may_have_changed).
        fn split_in_leaf(
            inode: InodeIndex,
            max_entries: u16,
            extents: &mut Vec<Extent>,
            split_block_within_file: FileBlockIndex,
        ) -> Result<(bool, bool), Ext4Error> {
            // Find the extent containing the split point.
            let mut extent_index: Option<usize> = None;
            for (i, extent) in extents.iter().enumerate() {
                let start = extent.block_within_file;
                let end = start
                    .checked_add(FileBlockIndex::from(extent.num_blocks))
                    .unwrap();
                if split_block_within_file >= start
                    && split_block_within_file < end
                {
                    extent_index = Some(i);
                    break;
                }
            }
            let Some(i) = extent_index else {
                return Err(CorruptKind::ExtentBlock(inode).into());
            };

            let old = extents[i];
            let start = old.block_within_file;
            let end = start
                .checked_add(FileBlockIndex::from(old.num_blocks))
                .unwrap();

            // No-op at boundaries.
            if split_block_within_file == start
                || split_block_within_file == end
            {
                return Ok((false, false));
            }

            if extents.len() >= usize_from_u32(u32::from(max_entries)) {
                return Err(Ext4Error::NoSpace);
            }

            let left_len_u32 =
                split_block_within_file.checked_sub(start).unwrap();
            let right_len_u32 =
                end.checked_sub(split_block_within_file).unwrap();
            let left_len: u16 = u16::try_from(left_len_u32)
                .map_err(|_| CorruptKind::ExtentBlock(inode))?;
            let right_len: u16 = u16::try_from(right_len_u32)
                .map_err(|_| CorruptKind::ExtentBlock(inode))?;

            let left = Extent {
                block_within_file: old.block_within_file,
                start_block: old.start_block,
                num_blocks: left_len,
                is_initialized: old.is_initialized,
            };
            let right = Extent {
                block_within_file: split_block_within_file,
                start_block: old
                    .start_block
                    .checked_add(FsBlockIndex::from(left_len_u32))
                    .unwrap(),
                num_blocks: right_len,
                is_initialized: old.is_initialized,
            };

            extents[i] = left;
            extents.insert(i.checked_add(1).unwrap(), right);

            Ok((true, i == 0))
        }

        // Root inline leaf: update in-place.
        if self.node.header.depth == 0 {
            let ExtentNodeEntries::Leaf(extents) = &mut self.node.entries
            else {
                unreachable!();
            };
            let (did_split, _first_changed) = split_in_leaf(
                self.inode,
                self.node.header.max_entries,
                extents,
                split_block_within_file,
            )?;
            if did_split {
                self.node.header.num_entries =
                    u16::try_from(extents.len()).unwrap();
            }
            return Ok(());
        }

        // Non-root: descend to leaf, keeping a path to allow parent key updates.
        // Each path entry is (node, chosen_child_index_within_node).
        let mut node = self.node.clone();
        let mut path: Vec<(ExtentNode, usize)> = Vec::new();

        loop {
            match &node.entries {
                ExtentNodeEntries::Leaf(_) => break,
                ExtentNodeEntries::Internal(internal_nodes) => {
                    let next_node_index = match find_child_index(
                        internal_nodes,
                        split_block_within_file,
                    ) {
                        Some(i) => i,
                        None => {
                            return Err(
                                CorruptKind::ExtentBlock(self.inode).into()
                            );
                        }
                    };
                    path.push((node.clone(), next_node_index));
                    let next_node_block = internal_nodes[next_node_index].block;
                    let next_node_data =
                        self.ext4.read_block(next_node_block).await?;
                    node = ExtentNode::from_bytes(
                        Some(next_node_block),
                        &next_node_data,
                        self.inode,
                        self.checksum_base.clone(),
                        &self.ext4,
                    )?;
                }
            }
        }

        // `node` is now the leaf node that should contain the extent.
        let leaf_block =
            node.block.ok_or(CorruptKind::ExtentBlock(self.inode))?;

        let old_first = match &node.entries {
            ExtentNodeEntries::Leaf(extents) => extents.first().copied(),
            _ => None,
        };

        // Split while holding a mutable borrow, but extract any info we need before writing.
        let (did_split, first_changed, new_first) = {
            let ExtentNodeEntries::Leaf(ref mut leaf_extents) = node.entries
            else {
                unreachable!();
            };

            let (did_split, first_changed) = split_in_leaf(
                self.inode,
                node.header.max_entries,
                leaf_extents,
                split_block_within_file,
            )?;

            if !did_split {
                (false, false, None)
            } else {
                node.header.num_entries =
                    u16::try_from(leaf_extents.len()).unwrap();
                (true, first_changed, leaf_extents.first().copied())
            }
        };

        if !did_split {
            return Ok(());
        }

        node.write(&self.ext4).await?;

        // If the first extent in the leaf changed, we may need to update the key in the parent.
        // In ext4, internal node keys are the first file-block in the child subtree.
        if first_changed {
            match (old_first, new_first) {
                (Some(old_f), Some(new_f))
                    if old_f.block_within_file != new_f.block_within_file =>
                {
                    // Update the parent's entry for this leaf.
                    if let Some((mut parent, child_index)) = path.pop() {
                        if let ExtentNodeEntries::Internal(
                            ref mut internal_nodes,
                        ) = parent.entries
                        {
                            internal_nodes[child_index].block_within_file =
                                new_f.block_within_file;
                        }
                        parent.write(&self.ext4).await?;

                        // If we updated index 0, that may affect the parent's first key, so bubble up.
                        let mut changed_block_within_file = if child_index == 0
                        {
                            Some(new_f.block_within_file)
                        } else {
                            None
                        };

                        // Bubble key changes to ancestors if we changed the first entry.
                        while let (
                            Some(new_key),
                            Some((mut ancestor, ancestor_child_index)),
                        ) = (changed_block_within_file, path.pop())
                        {
                            if let ExtentNodeEntries::Internal(
                                ref mut internal_nodes,
                            ) = ancestor.entries
                            {
                                internal_nodes[ancestor_child_index]
                                    .block_within_file = new_key;
                            }
                            ancestor.write(&self.ext4).await?;

                            changed_block_within_file =
                                if ancestor_child_index == 0 {
                                    Some(new_key)
                                } else {
                                    None
                                };
                        }
                    }
                }
                _ => {}
            }
        }

        Ok(())
    }

    /// Mark a (contiguous) file-block range as initialized. Internally this may
    /// split extents and flip `is_initialized` flags for affected extents/blocks.
    #[maybe_async::maybe_async]
    async fn mark_initialized(
        &mut self,
        start: FileBlockIndex,
        num_blocks: u32,
    ) -> Result<(), Ext4Error> {
        todo!()
    }

    /// Try to merge adjacency-eligible extents (same start_block+num or both initialized/uninitialized adjacent)
    /// starting at `hint_block` to reduce fragmentation.
    #[maybe_async::maybe_async]
    pub(crate) async fn try_merge_adjacent(
        &mut self,
        hint_block: FileBlockIndex,
    ) -> Result<(), Ext4Error> {
        let mut node = self.node.clone();
        loop {
            match &mut node.entries {
                ExtentNodeEntries::Leaf(extents) => {
                    let idx = extents.iter().position(|e| {
                        hint_block >= e.block_within_file
                            && hint_block
                                < e.block_within_file
                                    .checked_add(FileBlockIndex::from(
                                        e.num_blocks,
                                    ))
                                    .unwrap()
                    });

                    if let Some(idx) = idx {
                        let mut modified = false;

                        // Try merge with next
                        if idx.checked_add(1).unwrap() < extents.len() {
                            let curr = extents[idx];
                            let next = extents[idx.checked_add(1).unwrap()];
                            if Self::can_merge(&curr, &next) {
                                extents[idx].num_blocks = curr
                                    .num_blocks
                                    .checked_add(next.num_blocks)
                                    .unwrap();
                                extents.remove(idx.checked_add(1).unwrap());
                                modified = true;
                            }
                        }

                        // Try merge with prev
                        if idx > 0 {
                            let curr = extents[idx];
                            let prev = extents[idx.checked_sub(1).unwrap()];
                            if Self::can_merge(&prev, &curr) {
                                extents[idx.checked_sub(1).unwrap()]
                                    .num_blocks = prev
                                    .num_blocks
                                    .checked_add(curr.num_blocks)
                                    .unwrap();
                                extents.remove(idx);
                                modified = true;
                            }
                        }

                        if modified {
                            node.header.num_entries =
                                u16::try_from(extents.len()).unwrap();
                            if let Some(block) = node.block {
                                let bytes = node.to_bytes(Some(
                                    self.checksum_base.clone(),
                                ))?;
                                self.ext4
                                    .write_to_block(block, 0, &bytes)
                                    .await?;
                            } else {
                                self.node = node;
                            }
                        }
                    }
                    return Ok(());
                }
                ExtentNodeEntries::Internal(internal_nodes) => {
                    let next_node_index =
                        match find_child_index(internal_nodes, hint_block) {
                            Some(i) => i,
                            None => return Ok(()),
                        };
                    let next_node_block = internal_nodes[next_node_index].block;
                    let next_node_data =
                        self.ext4.read_block(next_node_block).await?;
                    node = ExtentNode::from_bytes(
                        Some(next_node_block),
                        &next_node_data,
                        self.inode,
                        self.checksum_base.clone(),
                        &self.ext4,
                    )?;
                }
            }
        }
    }

    fn can_merge(left: &Extent, right: &Extent) -> bool {
        // Logical continuity
        if left
            .block_within_file
            .checked_add(FileBlockIndex::from(left.num_blocks))
            .unwrap()
            != right.block_within_file
        {
            return false;
        }

        // Physical continuity
        if left
            .start_block
            .checked_add(FsBlockIndex::from(left.num_blocks))
            .unwrap()
            != right.start_block
        {
            return false;
        }

        // State
        if left.is_initialized != right.is_initialized {
            return false;
        }

        // Length limit (32768 blocks = 2^15)
        if (u32::from(left.num_blocks).checked_add(u32::from(right.num_blocks)))
            .unwrap()
            > 32768
        {
            return false;
        }

        true
    }
}

#[cfg(all(test, feature = "std"))]
mod tests {
    use crate::block_index::FileBlockIndex;
    use crate::block_index::FsBlockIndex;
    use crate::file_blocks::extent_tree::ExtentTree;
    use crate::inode::Inode;
    use crate::test_util::load_test_disk1_rw;

    use super::{
        CorruptKind, ENTRY_SIZE_IN_BYTES, Ext4, Ext4Error, ExtentInternalNode,
        ExtentNode, ExtentNodeEntries, NodeHeader,
    };
    use crate::error::Corrupt;
    use maybe_async::maybe_async;
    use std::num::NonZeroU32;

    #[maybe_async::test(
        feature = "sync",
        async(not(feature = "sync"), tokio::test)
    )]
    async fn test_extent_tree() {
        let fs = load_test_disk1_rw().await;
        let root_inode = fs.read_root_inode().await.unwrap();
        let mut tree =
            ExtentTree::from_inode(&root_inode, fs.0.clone()).unwrap();
        let extent = tree.find_extent(0).await.unwrap().unwrap();
        assert_eq!(extent.block_within_file, 0);
    }

    #[maybe_async::maybe_async]
    async fn root_inode_as_extent_tree(ext4: &Ext4) -> Inode {
        ext4.read_root_inode().await.unwrap()
    }

    /// Build a depth-1 extent tree (internal root -> 2 leaf nodes) written to disk.
    ///
    /// Layout:
    /// - leaf0: contains one extent covering file blocks [0, 2)
    /// - leaf1: contains one extent covering file blocks [10, 12)
    /// - root: internal node with two entries keyed at 0 and 10 pointing to the leaf blocks.
    #[maybe_async::maybe_async]
    async fn build_depth1_tree(
        ext4: &Ext4,
        inode: &Inode,
    ) -> (ExtentTree, FsBlockIndex, FsBlockIndex) {
        use crate::extent::Extent;

        let checksum_base = inode.checksum_base().clone();
        let checksum_base_opt =
            ext4.has_metadata_checksums().then(|| checksum_base.clone());

        // Allocate blocks for the 2 leaf nodes.
        let leaf0_block = ext4
            .alloc_contiguous_blocks(inode.index, NonZeroU32::new(1).unwrap())
            .await
            .unwrap();
        let leaf1_block = ext4
            .alloc_contiguous_blocks(inode.index, NonZeroU32::new(1).unwrap())
            .await
            .unwrap();

        // Construct leaf nodes.
        let leaf0 = ExtentNode {
            block: Some(leaf0_block),
            header: NodeHeader {
                num_entries: 1,
                max_entries: 4,
                depth: 0,
                generation: 0,
            },
            entries: ExtentNodeEntries::Leaf(vec![Extent {
                block_within_file: 0,
                start_block: 100,
                num_blocks: 2,
                is_initialized: true,
            }]),
        };
        let leaf1 = ExtentNode {
            block: Some(leaf1_block),
            header: NodeHeader {
                num_entries: 1,
                max_entries: 4,
                depth: 0,
                generation: 0,
            },
            entries: ExtentNodeEntries::Leaf(vec![Extent {
                block_within_file: 10,
                start_block: 200,
                num_blocks: 2,
                is_initialized: true,
            }]),
        };

        ext4.write_to_block(
            leaf0_block,
            0,
            &leaf0.to_bytes(checksum_base_opt.clone()).unwrap(),
        )
        .await
        .unwrap();
        ext4.write_to_block(
            leaf1_block,
            0,
            &leaf1.to_bytes(checksum_base_opt.clone()).unwrap(),
        )
        .await
        .unwrap();

        // Construct an internal root node that points to the two leaf blocks.
        let root = ExtentNode {
            block: None,
            header: NodeHeader {
                num_entries: 2,
                max_entries: 4,
                depth: 1,
                generation: 0,
            },
            entries: ExtentNodeEntries::Internal(vec![
                ExtentInternalNode {
                    block_within_file: 0,
                    block: leaf0_block,
                },
                ExtentInternalNode {
                    block_within_file: 10,
                    block: leaf1_block,
                },
            ]),
        };

        let tree = ExtentTree {
            ext4: ext4.clone(),
            inode: inode.index,
            node: root,
            checksum_base,
        };

        (tree, leaf0_block, leaf1_block)
    }

    #[maybe_async::test(
        feature = "sync",
        async(not(feature = "sync"), tokio::test)
    )]
    #[ignore]
    async fn test_extent_tree_internal_nodes_find_extent_and_get_block() {
        let fs = load_test_disk1_rw().await;
        let ext4 = fs.0.clone();
        let inode = root_inode_as_extent_tree(&fs).await;

        let (tree, _leaf0, _leaf1) = build_depth1_tree(&ext4, &inode).await;

        // Within leaf0 extent.
        let e0 = tree.find_extent(0).await.unwrap().unwrap();
        assert_eq!(e0.block_within_file, 0);
        let block = tree.get_block(0).await.unwrap();
        assert_eq!(block, 100);
        let block = tree.get_block(1).await.unwrap();
        assert_eq!(block, 101);
        let extent = tree.find_extent(2).await;
        assert_eq!(extent.unwrap(), None);

        // Hole before leaf1.
        let extent = tree.find_extent(9).await.unwrap();
        assert_eq!(extent, None);

        // Within leaf1 extent.
        let e1 = tree.find_extent(10).await.unwrap().unwrap();
        assert_eq!(e1.block_within_file, 10);
        let block = tree.get_block(10).await.unwrap();
        assert_eq!(block, 200);
        let block = tree.get_block(11).await.unwrap();
        assert_eq!(block, 201);
        let extent = tree.find_extent(12).await.unwrap();
        assert_eq!(extent, None);
    }

    #[maybe_async::test(
        feature = "sync",
        async(not(feature = "sync"), tokio::test)
    )]
    #[ignore]
    async fn test_extent_tree_internal_nodes_selection_boundary_conditions() {
        let fs = load_test_disk1_rw().await;
        let ext4 = fs.0.clone();
        let inode = root_inode_as_extent_tree(&fs).await;

        let (tree, _leaf0, _leaf1) = build_depth1_tree(&ext4, &inode).await;

        // Querying before the first internal key should behave like `find_extent`: returns None.
        let extent = tree.find_extent(u32::MAX).await.unwrap();
        assert_eq!(extent, None);
        // block_index < 0 is not possible; instead validate that blocks smaller than first key 0
        // are handled via the 0 key. (0 selects child 0)
        let extent = tree.find_extent(0).await.unwrap();
        assert!(extent.is_some());

        // Exactly at the second internal key should descend into leaf1.
        let e = tree.find_extent(10).await.unwrap().unwrap();
        assert_eq!(e.block_within_file, 10);
    }

    #[maybe_async::test(
        feature = "sync",
        async(not(feature = "sync"), tokio::test)
    )]
    async fn test_extent_tree_internal_nodes_checksum_mismatch_is_detected() {
        let fs = load_test_disk1_rw().await;
        let ext4 = fs.0.clone();
        if !ext4.has_metadata_checksums() {
            // If the test image doesn't have metadata checksums enabled, there's nothing to test.
            return;
        }

        let inode = root_inode_as_extent_tree(&fs).await;
        let (tree, leaf0_block, _leaf1_block) =
            build_depth1_tree(&ext4, &inode).await;

        // Corrupt one byte in leaf0 so its checksum no longer matches.
        let mut bytes = ext4.read_block(leaf0_block).await.unwrap();
        // Flip a byte in the extent payload (not the checksum itself) so we avoid accidental fixups.
        bytes[ENTRY_SIZE_IN_BYTES] ^= 0x01;
        ext4.write_to_block(leaf0_block, 0, &bytes).await.unwrap();

        // Accessing an extent that forces reading leaf0 should return an error.
        let err = tree.find_extent(0).await.unwrap_err();
        if err != CorruptKind::ExtentChecksum(tree.inode) {
            panic!("unexpected error: {err:?}");
        }
    }

    #[maybe_async::test(
        feature = "sync",
        async(not(feature = "sync"), tokio::test)
    )]
    async fn test_merge_adjacent() {
        use crate::extent::Extent;

        let fs = load_test_disk1_rw().await;
        let ext4 = fs.0.clone();
        let inode = root_inode_as_extent_tree(&fs).await;

        let mut tree = ExtentTree::from_inode(&inode, ext4.clone()).unwrap();

        // Start with an empty leaf (root)
        tree.node.entries = ExtentNodeEntries::Leaf(vec![
            Extent {
                block_within_file: 0,
                start_block: 100,
                num_blocks: 5,
                is_initialized: true,
            },
            Extent {
                block_within_file: 5,
                start_block: 105,
                num_blocks: 5,
                is_initialized: true,
            },
        ]);
        tree.node.header.num_entries = 2;

        // Merge logical [0,5) and [5,10) -> [0,10)
        tree.try_merge_adjacent(0).await.unwrap();

        let ExtentNodeEntries::Leaf(extents) = &tree.node.entries else {
            panic!("expected leaf");
        };
        assert_eq!(extents.len(), 1);
        assert_eq!(extents[0].block_within_file, 0);
        assert_eq!(extents[0].num_blocks, 10);
        assert_eq!(extents[0].start_block, 100);

        // Try merge unmergeable (physically non-contiguous)
        tree.node.entries = ExtentNodeEntries::Leaf(vec![
            Extent {
                block_within_file: 0,
                start_block: 100,
                num_blocks: 5,
                is_initialized: true,
            },
            Extent {
                block_within_file: 5,
                start_block: 200, // Gap
                num_blocks: 5,
                is_initialized: true,
            },
        ]);
        tree.node.header.num_entries = 2;

        tree.try_merge_adjacent(0).await.unwrap();
        let ExtentNodeEntries::Leaf(extents) = &tree.node.entries else {
            panic!("expected leaf");
        };
        assert_eq!(extents.len(), 2);
    }
}
