Panic in trie operation logic – Assertion Failure in `nibbleslice.rs:120:9`

[dmytro-his]

Description

Performing specific operations on TrieDBMut with a custom trie layout that uses nibbles (NoExtensionLayout) causes a panic. The issue occurs when attempting to remove non-existent key, triggering an assertion failure in nibble/nibbleslice.rs:120:9.

Code to Reproduce

/// This module contains test to showcase issue with trie
#[cfg(test)]
mod tests {
    use memory_db::{HashKey, MemoryDB};
    use reference_trie::{RefHasher, ReferenceNodeCodecNoExt};
    use trie_db::{TrieDBMutBuilder, TrieLayout, TrieMut};

    /// Custom Trie layout that does not use extensions.
    #[derive(Default)]
    pub struct NoExtensionLayout;

    impl TrieLayout for NoExtensionLayout {
        const USE_EXTENSION: bool = false;
        const ALLOW_EMPTY: bool = false;
        const MAX_INLINE_VALUE: Option<u32> = None;
        type Hash = RefHasher;
        type Codec = ReferenceNodeCodecNoExt<RefHasher>;
    }

    /// Reproduces panic issue in trie
    /// The panic occurs due to an assertion failure in `nibble/nibbleslice.rs:120:9`
    ///
    /// #### Related Error Message:
    /// ```
    /// assertion failed: self.len() >= i
    /// ```
    #[test]
    fn test_trie_panic() -> Result<(), Box<dyn std::error::Error>> {
        let pairs = [
            (hex::decode("ffff")?, hex::decode("0a")?),
            (hex::decode("feffe9")?, hex::decode("0b")?),
            (hex::decode("ffffff")?, hex::decode("0c")?),
            (hex::decode("ff")?, hex::decode("")?), // Removal of non-existent key triggers panic
        ];

        let mut memdb = MemoryDB::<_, HashKey<_>, _>::default();
        let mut root = Default::default();

        let mut trie = TrieDBMutBuilder::<NoExtensionLayout>::new(&mut memdb, &mut root).build();

        for (key, value) in &pairs {
            trie.insert(key, value)?;
        }

        Ok(())
    }
}

Cargo.toml

[package]
name = "trie_panic"
version = "0.1.0"
edition = "2021"

[dependencies]
hex = "0.4.3"
memory-db = "0.32.0"
reference-trie = "0.29.1"
trie-db = "0.27.0" # Using this version to match the older trie-db version used by reference-trie.

Expected Behavior

The trie should handle this scenario gracefully without triggering a panic.

Actual Behavior

The test fails with a panic at /trie-db-0.27.1/src/nibble/nibbleslice.rs:120:9, resulting in the following assertion error:

`assertion failed: self.len() >= i`

Additional Information

This issue has also been tested with the latest trie-db version (0.29.1), and the behavior remains the same