use std::{
    alloc::{self, handle_alloc_error, Layout},
    iter::Skip,
    marker::PhantomData,
    mem,
};

use event::{ChangelogEvent, MerkleTreeEvent};
use light_bounded_vec::{
    BoundedVec, BoundedVecMetadata, CyclicBoundedVec, CyclicBoundedVecIterator,
    CyclicBoundedVecMetadata,
};
pub use light_hasher;
use light_hasher::Hasher;

pub mod changelog;
pub mod copy;
pub mod errors;
pub mod event;
pub mod hash;
pub mod zero_copy;

use crate::{
    changelog::ChangelogEntry,
    errors::ConcurrentMerkleTreeError,
    event::PathNode,
    hash::{compute_parent_node, compute_root},
};

/// [Concurrent Merkle tree](https://drive.google.com/file/d/1BOpa5OFmara50fTvL0VIVYjtg-qzHCVc/view)
/// which allows for multiple requests of updating leaves, without making any
/// of the requests invalid, as long as they are not modyfing the same leaf.
///
/// When any of the above happens, some of the concurrent requests are going to
/// be invalid, forcing the clients to re-generate the Merkle proof. But that's
/// still better than having such a failure after any update happening in the
/// middle of requesting the update.
///
/// Due to ability to make a decent number of concurrent update requests to be
/// valid, no lock is necessary.
#[repr(C)]
#[derive(Debug)]
// TODO(vadorovsky): The only reason why are we still keeping `HEIGHT` as a
// const generic here is that removing it would require keeping a `BoundecVec`
// inside `CyclicBoundedVec`. Casting byte slices to such nested vector is not
// a trivial task, but we might eventually do it at some point.
pub struct ConcurrentMerkleTree<H, const HEIGHT: usize>
where
    H: Hasher,
{
    pub height: usize,
    pub canopy_depth: usize,

    pub next_index: *mut usize,
    pub sequence_number: *mut usize,
    pub rightmost_leaf: *mut [u8; 32],

    /// Hashes of subtrees.
    pub filled_subtrees: BoundedVec<[u8; 32]>,
    /// History of Merkle proofs.
    pub changelog: CyclicBoundedVec<ChangelogEntry<HEIGHT>>,
    /// History of roots.
    pub roots: CyclicBoundedVec<[u8; 32]>,
    /// Cached upper nodes.
    pub canopy: BoundedVec<[u8; 32]>,

    pub _hasher: PhantomData<H>,
}

pub type ConcurrentMerkleTree22<H> = ConcurrentMerkleTree<H, 22>;
pub type ConcurrentMerkleTree26<H> = ConcurrentMerkleTree<H, 26>;
pub type ConcurrentMerkleTree32<H> = ConcurrentMerkleTree<H, 32>;
pub type ConcurrentMerkleTree40<H> = ConcurrentMerkleTree<H, 40>;

impl<H, const HEIGHT: usize> ConcurrentMerkleTree<H, HEIGHT>
where
    H: Hasher,
{
    /// Number of nodes to include in canopy, based on `canopy_depth`.
    #[inline(always)]
    pub fn canopy_size(canopy_depth: usize) -> usize {
        (1 << (canopy_depth + 1)) - 2
    }

    /// Size of the struct **without** dynamically sized fields (`BoundedVec`,
    /// `CyclicBoundedVec`).
    pub fn non_dyn_fields_size() -> usize {
        // height
        mem::size_of::<usize>()
        // changelog_capacity
        + mem::size_of::<usize>()
        // next_index
        + mem::size_of::<usize>()
        // sequence_number
        + mem::size_of::<usize>()
        // rightmost_leaf
        + mem::size_of::<[u8; 32]>()
        // filled_subtrees (metadata)
        + mem::size_of::<BoundedVecMetadata>()
        // changelog (metadata)
        + mem::size_of::<CyclicBoundedVecMetadata>()
        // roots (metadata)
        + mem::size_of::<CyclicBoundedVecMetadata>()
        // canopy (metadata)
        + mem::size_of::<BoundedVecMetadata>()
    }

    // TODO(vadorovsky): Make a macro for that.
    pub fn size_in_account(
        height: usize,
        changelog_size: usize,
        roots_size: usize,
        canopy_depth: usize,
    ) -> usize {
        // non-dynamic fields
        Self::non_dyn_fields_size()
        // filled_subtrees
        + mem::size_of::<[u8; 32]>() * height
        // changelog
        + mem::size_of::<ChangelogEntry<HEIGHT>>() * changelog_size
        // roots
        + mem::size_of::<[u8; 32]>() * roots_size
        // canopy
        + mem::size_of::<[u8; 32]>() * Self::canopy_size(canopy_depth)
    }

    pub fn new(
        height: usize,
        changelog_size: usize,
        roots_size: usize,
        canopy_depth: usize,
    ) -> Result<Self, ConcurrentMerkleTreeError> {
        if height == 0 || HEIGHT == 0 {
            return Err(ConcurrentMerkleTreeError::HeightZero);
        }
        // Changelog needs to be at least 1, because it's used for storing
        // Merkle paths in `append`/`append_batch`.
        if changelog_size == 0 {
            return Err(ConcurrentMerkleTreeError::ChangelogZero);
        }
        if roots_size == 0 {
            return Err(ConcurrentMerkleTreeError::RootsZero);
        }

        let layout = Layout::new::<usize>();
        let next_index = unsafe { alloc::alloc(layout) as *mut usize };
        if next_index.is_null() {
            handle_alloc_error(layout);
        }
        unsafe { *next_index = 0 };

        let layout = Layout::new::<usize>();
        let sequence_number = unsafe { alloc::alloc(layout) as *mut usize };
        if sequence_number.is_null() {
            handle_alloc_error(layout);
        }
        unsafe { *sequence_number = 0 };

        let layout = Layout::new::<[u8; 32]>();
        let rightmost_leaf = unsafe { alloc::alloc(layout) as *mut [u8; 32] };
        if rightmost_leaf.is_null() {
            handle_alloc_error(layout);
        }
        unsafe { *rightmost_leaf = [0u8; 32] };

        Ok(Self {
            height,
            canopy_depth,

            next_index,
            sequence_number,
            rightmost_leaf,

            filled_subtrees: BoundedVec::with_capacity(height),
            changelog: CyclicBoundedVec::with_capacity(changelog_size),
            roots: CyclicBoundedVec::with_capacity(roots_size),
            canopy: BoundedVec::with_capacity(Self::canopy_size(canopy_depth)),

            _hasher: PhantomData,
        })
    }

    /// Initializes the Merkle tree.
    pub fn init(&mut self) -> Result<(), ConcurrentMerkleTreeError> {
        // Initialize root.
        let root = H::zero_bytes()[self.height];
        self.roots.push(root);

        // Initialize changelog.
        let path = std::array::from_fn(|i| H::zero_bytes()[i]);
        let changelog_entry = ChangelogEntry {
            root,
            path,
            index: 0,
        };
        self.changelog.push(changelog_entry);

        // Initialize filled subtrees.
        for i in 0..self.height {
            self.filled_subtrees.push(H::zero_bytes()[i]).unwrap();
        }

        // Initialize canopy.
        for level_i in 0..self.canopy_depth {
            let level_nodes = 1 << (level_i + 1);
            for _ in 0..level_nodes {
                let node = H::zero_bytes()[self.height - level_i - 1];
                self.canopy.push(node)?;
            }
        }

        Ok(())
    }

    /// Returns the index of the current changelog entry.
    pub fn changelog_index(&self) -> usize {
        self.changelog.last_index()
    }

    /// Returns the index of the current root in the tree's root buffer.
    pub fn root_index(&self) -> usize {
        self.roots.last_index()
    }

    /// Returns the current root.
    pub fn root(&self) -> [u8; 32] {
        // PANICS: This should never happen - there is always a root in the
        // tree and `self.root_index()` should always point to an existing index.
        self.roots[self.root_index()]
    }

    pub fn current_index(&self) -> usize {
        let next_index = self.next_index();
        if next_index > 0 {
            next_index - 1
        } else {
            next_index
        }
    }

    pub fn next_index(&self) -> usize {
        unsafe { *self.next_index }
    }

    fn inc_next_index(&mut self) -> Result<(), ConcurrentMerkleTreeError> {
        unsafe {
            *self.next_index = self
                .next_index()
                .checked_add(1)
                .ok_or(ConcurrentMerkleTreeError::IntegerOverflow)?;
        }
        Ok(())
    }

    pub fn sequence_number(&self) -> usize {
        unsafe { *self.sequence_number }
    }

    fn inc_sequence_number(&mut self) -> Result<(), ConcurrentMerkleTreeError> {
        unsafe {
            *self.sequence_number = self
                .sequence_number()
                .checked_add(1)
                .ok_or(ConcurrentMerkleTreeError::IntegerOverflow)?;
        }
        Ok(())
    }

    pub fn rightmost_leaf(&self) -> [u8; 32] {
        unsafe { *self.rightmost_leaf }
    }

    fn set_rightmost_leaf(&mut self, leaf: &[u8; 32]) {
        unsafe { *self.rightmost_leaf = *leaf };
    }

    pub fn update_proof_from_canopy(
        &self,
        leaf_index: usize,
        proof: &mut BoundedVec<[u8; 32]>,
    ) -> Result<(), ConcurrentMerkleTreeError> {
        let mut node_index = ((1 << self.height) + leaf_index) >> (self.height - self.canopy_depth);
        while node_index > 1 {
            // `node_index - 2` maps to the canopy index.
            let canopy_index = node_index - 2;
            let canopy_index = if canopy_index % 2 == 0 {
                canopy_index + 1
            } else {
                canopy_index - 1
            };
            proof.push(self.canopy[canopy_index])?;
            node_index >>= 1;
        }

        Ok(())
    }

    /// Returns an iterator with changelog entries newer than the requested
    /// `changelog_index`.
    pub fn changelog_entries(
        &self,
        changelog_index: usize,
    ) -> Result<Skip<CyclicBoundedVecIterator<'_, ChangelogEntry<HEIGHT>>>, ConcurrentMerkleTreeError>
    {
        // `CyclicBoundedVec::iter_from` returns an iterator which includes also
        // the element indicated by the provided index.
        //
        // However, we want to iterate only on changelog events **newer** than
        // the provided one.
        //
        // Calling `iter_from(changelog_index + 1)` wouldn't work. If
        // `changelog_index` points to the newest changelog entry,
        // `changelog_index + 1` would point to the **oldest** changelog entry.
        // That would result in iterating over the whole changelog - from the
        // oldest to the newest element.
        Ok(self.changelog.iter_from(changelog_index)?.skip(1))
    }

    /// Updates the given Merkle proof.
    ///
    /// The update is performed by checking whether there are any new changelog
    /// entries and whether they contain changes which affect the current
    /// proof. To be precise, for each changelog entry, it's done in the
    /// following steps:
    ///
    /// * Check if the changelog entry was directly updating the `leaf_index`
    ///   we are trying to update.
    ///   * If no (we check that condition first, since it's more likely),
    ///     it means that there is a change affecting the proof, but not the
    ///     leaf.
    ///     Check which element from our proof was affected by the change
    ///     (using the `critbit_index` method) and update it (copy the new
    ///     element from the changelog to our updated proof).
    ///   * If yes, it means that the same leaf we want to update was already
    ///     updated. In such case, updating the proof is not possible.
    pub fn update_proof_from_changelog(
        &self,
        changelog_index: usize,
        leaf_index: usize,
        proof: &mut BoundedVec<[u8; 32]>,
    ) -> Result<(), ConcurrentMerkleTreeError> {
        // Iterate over changelog entries starting from the requested
        // `changelog_index`.
        //
        // Since we are interested only in subsequent, new changelog entries,
        // skip the first result.
        for changelog_entry in self.changelog_entries(changelog_index)? {
            changelog_entry.update_proof(leaf_index, proof)?;
        }

        Ok(())
    }

    /// Checks whether the given Merkle `proof` for the given `node` (with index
    /// `i`) is valid. The proof is valid when computing parent node hashes using
    /// the whole path of the proof gives the same result as the given `root`.
    pub fn validate_proof(
        &self,
        leaf: &[u8; 32],
        leaf_index: usize,
        proof: &BoundedVec<[u8; 32]>,
    ) -> Result<(), ConcurrentMerkleTreeError> {
        let expected_root = self.root();
        let computed_root = compute_root::<H>(leaf, leaf_index, proof)?;
        if computed_root == expected_root {
            Ok(())
        } else {
            Err(ConcurrentMerkleTreeError::InvalidProof(
                expected_root,
                computed_root,
            ))
        }
    }

    /// Updates the leaf under `leaf_index` with the `new_leaf` value.
    ///
    /// 1. Computes the new path and root from `new_leaf` and Merkle proof
    ///    (`proof`).
    /// 2. Stores the new path as the latest changelog entry and increments the
    ///    latest changelog index.
    /// 3. Stores the latest root and increments the latest root index.
    /// 4. If new leaf is at the rightmost index, stores it as the new
    ///    rightmost leaft and stores the Merkle proof as the new rightmost
    ///    proof.
    ///
    /// # Validation
    ///
    /// This method doesn't validate the proof. Caller is responsible for
    /// doing that before.
    fn update_leaf_in_tree(
        &mut self,
        new_leaf: &[u8; 32],
        leaf_index: usize,
        proof: &BoundedVec<[u8; 32]>,
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        let mut current_node = *new_leaf;
        let mut changelog_path = [[0u8; 32]; HEIGHT];
        for (i, sibling) in proof.iter().enumerate() {
            changelog_path[i] = current_node;
            current_node = compute_parent_node::<H>(&current_node, sibling, leaf_index, i)?;
        }

        self.inc_sequence_number()?;

        let changelog_entry = ChangelogEntry::new(current_node, changelog_path, leaf_index);

        self.roots.push(current_node);

        // Check if the leaf is the last leaf in the tree.
        if self.next_index() < (1 << self.height) {
            changelog_entry.update_proof(self.next_index(), &mut self.filled_subtrees)?;
            // Check if we updated the rightmost leaf.
            if leaf_index >= self.current_index() {
                self.set_rightmost_leaf(new_leaf);
            }
        }
        self.changelog.push(changelog_entry);

        Ok((self.changelog.last_index(), self.sequence_number()))
    }

    /// Replaces the `old_leaf` under the `leaf_index` with a `new_leaf`, using
    /// the given `proof` and `changelog_index` (pointing to the changelog entry
    /// which was the newest at the time of preparing the proof).
    #[inline(never)]
    pub fn update(
        &mut self,
        changelog_index: usize,
        old_leaf: &[u8; 32],
        new_leaf: &[u8; 32],
        leaf_index: usize,
        proof: &mut BoundedVec<[u8; 32]>,
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        let expected_proof_len = self.height - self.canopy_depth;
        if proof.len() != expected_proof_len {
            return Err(ConcurrentMerkleTreeError::InvalidProofLength(
                expected_proof_len,
                proof.len(),
            ));
        }
        if leaf_index >= self.next_index() {
            return Err(ConcurrentMerkleTreeError::CannotUpdateEmpty);
        }

        if self.canopy_depth > 0 {
            self.update_proof_from_canopy(leaf_index, proof)?;
        }
        if changelog_index != self.changelog_index() {
            self.update_proof_from_changelog(changelog_index, leaf_index, proof)?;
        }
        self.validate_proof(old_leaf, leaf_index, proof)?;
        self.update_leaf_in_tree(new_leaf, leaf_index, proof)
    }

    /// Appends a new leaf to the tree.
    pub fn append(&mut self, leaf: &[u8; 32]) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        self.append_batch(&[leaf])
    }

    /// Appends a new leaf to the tree. Saves Merkle proof to the provided
    /// `proof` reference.
    pub fn append_with_proof(
        &mut self,
        leaf: &[u8; 32],
        proof: &mut BoundedVec<[u8; 32]>,
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        self.append_batch_with_proofs(&[leaf], &mut [proof])
    }

    /// Appends a batch of new leaves to the tree.
    pub fn append_batch(
        &mut self,
        leaves: &[&[u8; 32]],
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        self.append_batch_common::<false>(leaves, None)
    }

    /// Appends a batch of new leaves to the tree. Saves Merkle proofs to the
    /// provided `proofs` slice.
    pub fn append_batch_with_proofs(
        &mut self,
        leaves: &[&[u8; 32]],
        proofs: &mut [&mut BoundedVec<[u8; 32]>],
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        self.append_batch_common::<true>(leaves, Some(proofs))
    }

    /// Appends a batch of new leaves to the tree.
    ///
    /// This method contains the common logic and is not intended for external
    /// use. Callers should choose between [`append_batch`](ConcurrentMerkleTree::append_batch)
    /// and [`append_batch_with_proofs`](ConcurrentMerkleTree::append_batch_with_proofs).
    fn append_batch_common<
        // The only purpose of this const generic is to force compiler to
        // produce separate functions, with and without proof.
        //
        // Unfortunately, using `Option` is not enough:
        //
        // https://godbolt.org/z/fEMMfMdPc
        // https://godbolt.org/z/T3dxnjMzz
        //
        // Using the const generic helps and ends up generating two separate
        // functions:
        //
        // https://godbolt.org/z/zGnM7Ycn1
        const WITH_PROOFS: bool,
    >(
        &mut self,
        leaves: &[&[u8; 32]],
        // Slice for saving Merkle proofs.
        //
        // Currently it's used only for indexed Merkle trees.
        mut proofs: Option<&mut [&mut BoundedVec<[u8; 32]>]>,
    ) -> Result<(usize, usize), ConcurrentMerkleTreeError> {
        if leaves.is_empty() {
            return Err(ConcurrentMerkleTreeError::EmptyLeaves);
        }
        if (self.next_index() + leaves.len() - 1) >= 1 << self.height {
            return Err(ConcurrentMerkleTreeError::TreeFull);
        }
        if leaves.len() > self.changelog.capacity() {
            return Err(ConcurrentMerkleTreeError::BatchGreaterThanChangelog(
                leaves.len(),
                self.changelog.capacity(),
            ));
        }

        let first_leaf_index = self.next_index();
        let first_changelog_index = (self.changelog.last_index() + 1) % self.changelog.capacity();
        let first_sequence_number = self.sequence_number() + 1;

        for (leaf_i, leaf) in leaves.iter().enumerate() {
            self.changelog
                .push(ChangelogEntry::<HEIGHT>::default_with_index(
                    first_leaf_index + leaf_i,
                ));
            let changelog_index = self.changelog_index();

            let mut current_index = self.next_index();
            let mut current_node = **leaf;

            // Limit until which we fill up the current Merkle path.
            let fillup_index = if leaf_i < (leaves.len() - 1) {
                self.next_index().trailing_ones() as usize + 1
            } else {
                self.height
            };

            self.changelog[changelog_index].path[0] = **leaf;

            // Compute the whole Merkle path up to the `fillup_index`.
            //
            // On each iteration, we also fill up empty nodes of previous Merkle
            // paths with the nodes from the current path - this way we eventually
            // fill all the paths while avoiding to calculate too many hashes.
            //
            // `fillup_index` of the last iteration should be always equal to
            // the Merkle tree height. Therefore, after the last iteration, no
            // path is going to contain and empty node.
            for i in 0..fillup_index {
                let is_left = current_index % 2 == 0;

                if is_left {
                    // If the current node is on the left side:
                    //
                    //     U
                    //    / \
                    //  CUR  SIB
                    //  /     \
                    // N       N
                    //
                    // * The sibling (on the right) is a "zero node".
                    // * That "zero node" becomes a part of Merkle proof.
                    // * The upper (next current) node is `H(cur, Ø)`.
                    let empty_node = H::zero_bytes()[i];

                    if WITH_PROOFS {
                        // PANICS: `proofs` should be always `Some` at this point.
                        proofs.as_mut().unwrap()[leaf_i].push(empty_node)?;
                    }

                    self.filled_subtrees[i] = current_node;
                    current_node = H::hashv(&[&current_node, &empty_node])?;
                } else {
                    // If the current node is on the right side:
                    //
                    //     U
                    //    / \
                    //  SIB  CUR
                    //  /     \
                    // N       N
                    // * The sigling on the left is a "filled subtree".
                    // * That "filled subtree" becomes a part of Merkle proof.
                    // * The upper (next current) node is `H(sib, cur)`.

                    if WITH_PROOFS {
                        // PANICS: `proofs` should be always `Some` at this point.
                        proofs.as_mut().unwrap()[leaf_i].push(self.filled_subtrees[i])?;
                    }

                    current_node = H::hashv(&[&self.filled_subtrees[i], &current_node])?;
                }

                if i < self.height - 1 {
                    self.changelog[changelog_index].path[i + 1] = current_node;

                    for leaf_j in 0..leaf_i {
                        let changelog_index =
                            (first_changelog_index + leaf_j) % self.changelog.capacity();
                        if self.changelog[changelog_index].path[i + 1] == [0u8; 32] {
                            self.changelog[changelog_index].path[i + 1] = current_node;
                        }
                    }
                }

                current_index /= 2;
            }

            self.changelog[changelog_index].root = current_node;

            self.roots.push(current_node);

            self.inc_next_index()?;
            self.inc_sequence_number()?;

            self.set_rightmost_leaf(leaf);
        }

        if self.canopy_depth > 0 {
            self.update_canopy(first_changelog_index, leaves.len());
        }

        Ok((first_changelog_index, first_sequence_number))
    }

    fn update_canopy(&mut self, first_changelog_index: usize, num_leaves: usize) {
        for i in 0..num_leaves {
            let changelog_index = (first_changelog_index + i) % self.changelog.capacity();
            for (i, path_node) in self.changelog[changelog_index]
                .path
                .iter()
                .rev()
                .take(self.canopy_depth)
                .enumerate()
            {
                let level = self.height - i - 1;
                let index =
                    (1 << (self.height - level)) + (self.changelog[changelog_index].index >> level);
                // `index - 2` maps to the canopy index.
                self.canopy[(index - 2) as usize] = *path_node;
            }
        }
    }

    #[inline(never)]
    pub fn get_changelog_event(
        &self,
        merkle_tree_account_pubkey: [u8; 32],
        first_changelog_index: usize,
        first_sequence_number: usize,
        num_changelog_entries: usize,
    ) -> Result<MerkleTreeEvent, ConcurrentMerkleTreeError> {
        let mut paths = Vec::with_capacity(num_changelog_entries);
        for i in 0..num_changelog_entries {
            let changelog_index = (first_changelog_index + i) % self.changelog.capacity();
            let mut path = Vec::with_capacity(self.height);

            // Add all nodes from the changelog path.
            for (level, node) in self.changelog[changelog_index].path.iter().enumerate() {
                let level =
                    u32::try_from(level).map_err(|_| ConcurrentMerkleTreeError::IntegerOverflow)?;
                let index = (1 << (self.height as u32 - level))
                    + (self.changelog[changelog_index].index as u32 >> level);
                path.push(PathNode {
                    node: node.to_owned(),
                    index,
                });
            }

            // Add root.
            path.push(PathNode {
                node: self.changelog[changelog_index].root,
                index: 1,
            });

            paths.push(path);
        }

        let index: u32 = self.changelog[first_changelog_index]
            .index
            .try_into()
            .map_err(|_| ConcurrentMerkleTreeError::IntegerOverflow)?;
        Ok(MerkleTreeEvent::V1(ChangelogEvent {
            id: merkle_tree_account_pubkey,
            paths,
            seq: first_sequence_number as u64,
            index,
        }))
    }
}

impl<H, const HEIGHT: usize> Drop for ConcurrentMerkleTree<H, HEIGHT>
where
    H: Hasher,
{
    fn drop(&mut self) {
        let layout = Layout::new::<usize>();
        unsafe { alloc::dealloc(self.next_index as *mut u8, layout) };

        let layout = Layout::new::<usize>();
        unsafe { alloc::dealloc(self.sequence_number as *mut u8, layout) };

        let layout = Layout::new::<[u8; 32]>();
        unsafe { alloc::dealloc(self.rightmost_leaf as *mut u8, layout) };
    }
}

impl<H, const HEIGHT: usize> PartialEq for ConcurrentMerkleTree<H, HEIGHT>
where
    H: Hasher,
{
    fn eq(&self, other: &Self) -> bool {
        self.height.eq(&other.height)
            && self.canopy_depth.eq(&other.canopy_depth)
            && self.next_index().eq(&other.next_index())
            && self.sequence_number().eq(&other.sequence_number())
            && self.rightmost_leaf().eq(&other.rightmost_leaf())
            && self
                .filled_subtrees
                .as_slice()
                .eq(other.filled_subtrees.as_slice())
            && self.changelog.iter().eq(other.changelog.iter())
            && self.roots.iter().eq(other.roots.iter())
            && self.canopy.as_slice().eq(other.canopy.as_slice())
    }
}