grovedb 3.1.0

//! Tests

pub mod common;

mod query_tests;

mod sum_tree_tests;

mod count_sum_tree_tests;
mod count_tree_tests;
mod tree_hashes_tests;

use std::{
    ops::{Deref, DerefMut},
    option::Option::None,
};

use grovedb_version::version::GroveVersion;
use grovedb_visualize::{Drawer, Visualize};
use tempfile::TempDir;

use self::common::EMPTY_PATH;
use super::*;
use crate::{
    query_result_type::{QueryResultType, QueryResultType::QueryKeyElementPairResultType},
    reference_path::ReferencePathType,
    tests::common::compare_result_tuples,
};

pub const TEST_LEAF: &[u8] = b"test_leaf";

pub const ANOTHER_TEST_LEAF: &[u8] = b"test_leaf2";

const DEEP_LEAF: &[u8] = b"deep_leaf";

/// GroveDB wrapper to keep temp directory alive
pub struct TempGroveDb {
    _tmp_dir: TempDir,
    grove_db: GroveDb,
}

impl DerefMut for TempGroveDb {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.grove_db
    }
}

impl Deref for TempGroveDb {
    type Target = GroveDb;

    fn deref(&self) -> &Self::Target {
        &self.grove_db
    }
}

impl Visualize for TempGroveDb {
    fn visualize<W: std::io::Write>(&self, drawer: Drawer<W>) -> std::io::Result<Drawer<W>> {
        self.grove_db.visualize(drawer)
    }
}

/// A helper method to create an empty GroveDB
pub fn make_empty_grovedb() -> TempGroveDb {
    let tmp_dir = TempDir::new().unwrap();
    let db = GroveDb::open(tmp_dir.path()).unwrap();
    TempGroveDb {
        _tmp_dir: tmp_dir,
        grove_db: db,
    }
}

/// A helper method to create GroveDB with one leaf for a root tree
pub fn make_test_grovedb(grove_version: &GroveVersion) -> TempGroveDb {
    // Tree Structure
    // root
    //  test_leaf
    //  another_test_leaf
    let tmp_dir = TempDir::new().unwrap();
    let mut db = GroveDb::open(tmp_dir.path()).unwrap();
    add_test_leaves(&mut db, grove_version);
    TempGroveDb {
        _tmp_dir: tmp_dir,
        grove_db: db,
    }
}

fn add_test_leaves(db: &mut GroveDb, grove_version: &GroveVersion) {
    db.insert(
        EMPTY_PATH,
        TEST_LEAF,
        Element::empty_tree(),
        None,
        None,
        grove_version,
    )
    .unwrap()
    .expect("successful root tree leaf insert");
    db.insert(
        EMPTY_PATH,
        ANOTHER_TEST_LEAF,
        Element::empty_tree(),
        None,
        None,
        grove_version,
    )
    .unwrap()
    .expect("successful root tree leaf 2 insert");
}

pub fn make_deep_tree(grove_version: &GroveVersion) -> TempGroveDb {
    // Tree Structure
    // root
    //     test_leaf
    //         innertree
    //             k1,v1
    //             k2,v2
    //             k3,v3
    //         innertree4
    //             k4,v4
    //             k5,v5
    //     another_test_leaf
    //         innertree2
    //             k3,v3
    //         innertree3
    //             k4,v4
    //     deep_leaf
    //          deep_node_1
    //              deeper_1
    //                  k1,v1
    //                  k2,v2
    //                  k3,v3
    //              deeper_2
    //                  k4,v4
    //                  k5,v5
    //                  k6,v6
    //          deep_node_2
    //              deeper_3
    //                  k7,v7
    //                  k8,v8
    //                  k9,v9
    //              deeper_4
    //                  k10,v10
    //                  k11,v11
    //              deeper_5
    //                  k12,v12
    //                  k13,v13
    //                  k14,v14

    // Insert elements into grovedb instance
    let temp_db = make_test_grovedb(grove_version);

    // add an extra root leaf
    temp_db
        .insert(
            EMPTY_PATH,
            DEEP_LEAF,
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful root tree leaf insert");

    // Insert level 1 nodes
    temp_db
        .insert(
            [TEST_LEAF].as_ref(),
            b"innertree",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [TEST_LEAF].as_ref(),
            b"innertree4",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [ANOTHER_TEST_LEAF].as_ref(),
            b"innertree2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [ANOTHER_TEST_LEAF].as_ref(),
            b"innertree3",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF].as_ref(),
            b"deep_node_1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF].as_ref(),
            b"deep_node_2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    // Insert level 2 nodes
    temp_db
        .insert(
            [TEST_LEAF, b"innertree"].as_ref(),
            b"key1",
            Element::new_item(b"value1".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [TEST_LEAF, b"innertree"].as_ref(),
            b"key2",
            Element::new_item(b"value2".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [TEST_LEAF, b"innertree"].as_ref(),
            b"key3",
            Element::new_item(b"value3".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [TEST_LEAF, b"innertree4"].as_ref(),
            b"key4",
            Element::new_item(b"value4".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [TEST_LEAF, b"innertree4"].as_ref(),
            b"key5",
            Element::new_item(b"value5".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [ANOTHER_TEST_LEAF, b"innertree2"].as_ref(),
            b"key3",
            Element::new_item(b"value3".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [ANOTHER_TEST_LEAF, b"innertree3"].as_ref(),
            b"key4",
            Element::new_item(b"value4".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1"].as_ref(),
            b"deeper_1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1"].as_ref(),
            b"deeper_2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2"].as_ref(),
            b"deeper_3",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2"].as_ref(),
            b"deeper_4",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2"].as_ref(),
            b"deeper_5",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    // Insert level 3 nodes
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_1"].as_ref(),
            b"key1",
            Element::new_item(b"value1".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_1"].as_ref(),
            b"key2",
            Element::new_item(b"value2".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_1"].as_ref(),
            b"key3",
            Element::new_item(b"value3".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_2"].as_ref(),
            b"key4",
            Element::new_item(b"value4".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_2"].as_ref(),
            b"key5",
            Element::new_item(b"value5".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"deeper_2"].as_ref(),
            b"key6",
            Element::new_item(b"value6".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");

    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_3"].as_ref(),
            b"key7",
            Element::new_item(b"value7".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_3"].as_ref(),
            b"key8",
            Element::new_item(b"value8".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_3"].as_ref(),
            b"key9",
            Element::new_item(b"value9".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_4"].as_ref(),
            b"key10",
            Element::new_item(b"value10".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_4"].as_ref(),
            b"key11",
            Element::new_item(b"value11".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_5"].as_ref(),
            b"key12",
            Element::new_item(b"value12".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_5"].as_ref(),
            b"key13",
            Element::new_item(b"value13".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_2", b"deeper_5"].as_ref(),
            b"key14",
            Element::new_item(b"value14".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
    temp_db
}

pub fn make_deep_tree_with_sum_trees(grove_version: &GroveVersion) -> TempGroveDb {
    // Tree Structure
    // root
    //     deep_leaf
    //          deep_node_1
    //              "" -> "empty"
    //              a -> "storage"
    //              c
    //                  1 (sum tree)
    //                      [0;32], 1
    //                      [1;32], 1
    //              d
    //                  0,v1
    //                  1 (sum tree)
    //                      [0;32], 4
    //                      [1;32], 1
    //              e
    //                  0,v4
    //                  1 (sum tree)
    //                      [0;32], 1
    //                      [1;32], 4
    //              f
    //                  0,v1
    //                  1 (sum tree)
    //                      [0;32], 1
    //                      [1;32], 4
    //              g
    //                  0,v4
    //                  1 (sum tree)
    //                      [3;32], 4
    //                      [5;32], 4
    //              h -> "h"
    //              .. -> ..
    //              z -> "z"

    let temp_db = make_test_grovedb(grove_version);

    // Add deep_leaf to root
    temp_db
        .insert(
            EMPTY_PATH,
            DEEP_LEAF,
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful root tree leaf insert");

    // Add deep_node_1 to deep_leaf
    temp_db
        .insert(
            [DEEP_LEAF].as_ref(),
            b"deep_node_1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");

    // Add a -> "storage" to deep_node_1
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1"].as_ref(),
            b"",
            Element::new_item("empty".as_bytes().to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful item insert");

    // Add a -> "storage" to deep_node_1
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1"].as_ref(),
            b"a",
            Element::new_item("storage".as_bytes().to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful item insert");

    // Add c, d, e, f, g to deep_node_1
    for key in [b"c", b"d", b"e", b"f", b"g"].iter() {
        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1"].as_ref(),
                key.as_slice(),
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
    }

    // Add sum tree to c
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"c"].as_ref(),
            b"1",
            Element::new_sum_tree(None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful sum tree insert");

    // Add items to sum tree in c
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"c", b"1"].as_ref(),
            &[0; 32],
            Element::SumItem(1, None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful sum item insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"c", b"1"].as_ref(),
            &[1; 32],
            Element::SumItem(1, None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful sum item insert");

    // Add items to 4, 5, 6, 7
    for (key, value) in [(b"d", b"v1"), (b"e", b"v4"), (b"f", b"v1"), (b"g", b"v4")].iter() {
        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1", key.as_slice()].as_ref(),
                b"0",
                Element::new_item(value.to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful item insert");

        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1", key.as_slice()].as_ref(),
                b"1",
                Element::new_sum_tree(None),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful sum tree insert");
    }

    // Add items to sum trees in d, e, f
    for key in [b"d", b"e", b"f"].iter() {
        let (value1, value2) = if *key == b"d" { (4, 1) } else { (1, 4) };

        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1", key.as_slice(), b"1"].as_ref(),
                &[0; 32],
                Element::SumItem(value1, None),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful sum item insert");
        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1", key.as_slice(), b"1"].as_ref(),
                &[1; 32],
                Element::SumItem(value2, None),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful sum item insert");
    }

    // Add items to sum tree in 7
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"g", b"1"].as_ref(),
            &[3; 32],
            Element::SumItem(4, None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful sum item insert");
    temp_db
        .insert(
            [DEEP_LEAF, b"deep_node_1", b"g", b"1"].as_ref(),
            &[5; 32],
            Element::SumItem(4, None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful sum item insert");

    // Add entries for all letters from "h" to "z"
    for letter in b'h'..=b'z' {
        temp_db
            .insert(
                [DEEP_LEAF, b"deep_node_1"].as_ref(),
                &[letter],
                Element::new_item(vec![letter]),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect(&format!("successful item insert for {}", letter as char));
    }

    temp_db
}

mod tests {
    use batch::QualifiedGroveDbOp;
    use grovedb_merk::proofs::query::SubqueryBranch;

    use super::*;

    #[test]
    fn test_init() {
        let tmp_dir = TempDir::new().unwrap();
        GroveDb::open(tmp_dir).expect("empty tree is ok");
    }

    #[test]
    fn test_element_with_flags() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("should insert subtree successfully");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"elem1",
            Element::new_item(b"flagless".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("should insert subtree successfully");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"elem2",
            Element::new_item_with_flags(b"flagged".to_vec(), Some([4, 5, 6, 7, 8].to_vec())),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("should insert subtree successfully");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"elem3",
            Element::new_tree_with_flags(None, Some([1].to_vec())),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("should insert subtree successfully");
        db.insert(
            [TEST_LEAF, b"key1", b"elem3"].as_ref(),
            b"elem4",
            Element::new_reference_with_flags(
                ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    b"key1".to_vec(),
                    b"elem2".to_vec(),
                ]),
                Some([9].to_vec()),
            ),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("should insert subtree successfully");

        let element_without_flag = db
            .get([TEST_LEAF, b"key1"].as_ref(), b"elem1", None, grove_version)
            .unwrap()
            .expect("should get successfully");
        let element_with_flag = db
            .get([TEST_LEAF, b"key1"].as_ref(), b"elem2", None, grove_version)
            .unwrap()
            .expect("should get successfully");
        let tree_element_with_flag = db
            .get([TEST_LEAF, b"key1"].as_ref(), b"elem3", None, grove_version)
            .unwrap()
            .expect("should get successfully");
        let flagged_ref_follow = db
            .get(
                [TEST_LEAF, b"key1", b"elem3"].as_ref(),
                b"elem4",
                None,
                grove_version,
            )
            .unwrap()
            .expect("should get successfully");

        let mut query = Query::new();
        query.insert_key(b"elem4".to_vec());
        let path_query = PathQuery::new(
            vec![TEST_LEAF.to_vec(), b"key1".to_vec(), b"elem3".to_vec()],
            SizedQuery::new(query, None, None),
        );
        let (flagged_ref_no_follow, _) = db
            .query_raw(
                &path_query,
                true,
                true,
                true,
                QueryKeyElementPairResultType,
                None,
                grove_version,
            )
            .unwrap()
            .expect("should get successfully");

        assert_eq!(
            element_without_flag,
            Element::Item(b"flagless".to_vec(), None)
        );
        assert_eq!(
            element_with_flag,
            Element::Item(b"flagged".to_vec(), Some([4, 5, 6, 7, 8].to_vec()))
        );
        assert_eq!(tree_element_with_flag.get_flags(), &Some([1].to_vec()));
        assert_eq!(
            flagged_ref_follow,
            Element::Item(b"flagged".to_vec(), Some([4, 5, 6, 7, 8].to_vec()))
        );
        assert_eq!(
            flagged_ref_no_follow.to_key_elements()[0],
            (
                b"elem4".to_vec(),
                Element::Reference(
                    ReferencePathType::AbsolutePathReference(vec![
                        TEST_LEAF.to_vec(),
                        b"key1".to_vec(),
                        b"elem2".to_vec()
                    ]),
                    None,
                    Some([9].to_vec())
                )
            )
        );

        // Test proofs with flags
        let mut query = Query::new();
        query.insert_all();

        let path_query = PathQuery::new(
            vec![TEST_LEAF.to_vec(), b"key1".to_vec()],
            SizedQuery::new(query, None, None),
        );
        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .expect("should successfully create proof");
        let (root_hash, result_set) = GroveDb::verify_query_raw(&proof, &path_query, grove_version)
            .expect("should verify proof");
        assert_eq!(
            root_hash,
            db.grove_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);
        assert_eq!(
            Element::deserialize(&result_set[0].value, grove_version)
                .expect("should deserialize element"),
            Element::Item(b"flagless".to_vec(), None)
        );
        assert_eq!(
            Element::deserialize(&result_set[1].value, grove_version)
                .expect("should deserialize element"),
            Element::Item(b"flagged".to_vec(), Some([4, 5, 6, 7, 8].to_vec()))
        );
        assert_eq!(
            Element::deserialize(&result_set[2].value, grove_version)
                .expect("should deserialize element")
                .get_flags(),
            &Some([1].to_vec())
        );
    }

    #[test]
    fn test_cannot_update_populated_tree_item() {
        let grove_version = GroveVersion::latest();
        // This test shows that you cannot update a tree item
        // in a way that disconnects its root hash from that of
        // the merk it points to.
        let db = make_deep_tree(grove_version);

        let old_element = db
            .get([TEST_LEAF].as_ref(), b"innertree", None, grove_version)
            .unwrap()
            .expect("should fetch item");

        let new_element = Element::empty_tree();
        db.insert(
            [TEST_LEAF].as_ref(),
            b"innertree",
            new_element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect_err("should not override tree");

        let current_element = db
            .get([TEST_LEAF].as_ref(), b"innertree", None, grove_version)
            .unwrap()
            .expect("should fetch item");

        assert_eq!(current_element, old_element);
        assert_ne!(current_element, new_element);
    }

    #[test]
    fn test_changes_propagated() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let old_hash = db.root_hash(None, grove_version).unwrap().unwrap();
        let element = Element::new_item(b"ayy".to_vec());

        // Insert some nested subtrees
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");

        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 2 insert");

        db.insert(
            [TEST_LEAF, b"key1", b"key2"].as_ref(),
            b"key3",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        assert_eq!(
            db.get(
                [TEST_LEAF, b"key1", b"key2"].as_ref(),
                b"key3",
                None,
                grove_version
            )
            .unwrap()
            .expect("successful get"),
            element
        );
        assert_ne!(
            old_hash,
            db.root_hash(None, grove_version).unwrap().unwrap()
        );
    }

    // TODO: Add solid test cases to this

    #[test]
    fn test_references() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        db.insert(
            [TEST_LEAF].as_ref(),
            b"merk_1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        db.insert(
            [TEST_LEAF, b"merk_1"].as_ref(),
            b"key1",
            Element::new_item(b"value1".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        db.insert(
            [TEST_LEAF, b"merk_1"].as_ref(),
            b"key2",
            Element::new_item(b"value2".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");

        db.insert(
            [TEST_LEAF].as_ref(),
            b"merk_2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        // db.insert([TEST_LEAF, b"merk_2"].as_ref(), b"key2",
        // Element::new_item(b"value2".to_vec()), None).expect("successful subtree
        // insert");
        db.insert(
            [TEST_LEAF, b"merk_2"].as_ref(),
            b"key1",
            Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                TEST_LEAF.to_vec(),
                b"merk_1".to_vec(),
                b"key1".to_vec(),
            ])),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        db.insert(
            [TEST_LEAF, b"merk_2"].as_ref(),
            b"key2",
            Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                TEST_LEAF.to_vec(),
                b"merk_1".to_vec(),
                b"key2".to_vec(),
            ])),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        assert!(db
            .get([TEST_LEAF].as_ref(), b"merk_1", None, grove_version)
            .unwrap()
            .is_ok());
        assert!(db
            .get([TEST_LEAF].as_ref(), b"merk_2", None, grove_version)
            .unwrap()
            .is_ok());
    }

    #[test]
    fn test_follow_references() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let element = Element::new_item(b"ayy".to_vec());

        // Insert an item to refer to
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");
        db.insert(
            [TEST_LEAF, b"key2"].as_ref(),
            b"key3",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        // Insert a reference
        db.insert(
            [TEST_LEAF].as_ref(),
            b"reference_key",
            Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                TEST_LEAF.to_vec(),
                b"key2".to_vec(),
                b"key3".to_vec(),
            ])),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful reference insert");

        assert_eq!(
            db.get([TEST_LEAF].as_ref(), b"reference_key", None, grove_version)
                .unwrap()
                .expect("successful get"),
            element
        );
    }

    #[test]
    fn test_reference_must_point_to_item() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        let result = db
            .insert(
                [TEST_LEAF].as_ref(),
                b"reference_key_1",
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    b"reference_key_2".to_vec(),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap();

        dbg!(&result);

        assert!(matches!(
            result,
            Err(Error::CorruptedReferencePathKeyNotFound(_))
        ));
    }

    #[test]
    fn test_too_many_indirections() {
        let grove_version = GroveVersion::latest();
        use crate::operations::get::MAX_REFERENCE_HOPS;
        let db = make_test_grovedb(grove_version);

        let keygen = |idx| format!("key{}", idx).bytes().collect::<Vec<u8>>();

        db.insert(
            [TEST_LEAF].as_ref(),
            b"key0",
            Element::new_item(b"oops".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful item insert");

        for i in 1..=(MAX_REFERENCE_HOPS) {
            db.insert(
                [TEST_LEAF].as_ref(),
                &keygen(i),
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    keygen(i - 1),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful reference insert");
        }

        // Add one more reference
        let result = db
            .insert(
                [TEST_LEAF].as_ref(),
                &keygen(MAX_REFERENCE_HOPS + 1),
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    keygen(MAX_REFERENCE_HOPS),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap();

        assert!(matches!(result, Err(Error::ReferenceLimit)));
    }

    #[test]
    fn test_reference_value_affects_state() {
        let grove_version = GroveVersion::latest();
        let db_one = make_test_grovedb(grove_version);
        db_one
            .insert(
                [TEST_LEAF].as_ref(),
                b"key1",
                Element::new_item(vec![0]),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("should insert item");
        db_one
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"ref",
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    b"key1".to_vec(),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("should insert item");

        let db_two = make_test_grovedb(grove_version);
        db_two
            .insert(
                [TEST_LEAF].as_ref(),
                b"key1",
                Element::new_item(vec![0]),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("should insert item");
        db_two
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"ref",
                Element::new_reference(ReferencePathType::UpstreamRootHeightReference(
                    0,
                    vec![TEST_LEAF.to_vec(), b"key1".to_vec()],
                )),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("should insert item");

        assert_ne!(
            db_one
                .root_hash(None, grove_version)
                .unwrap()
                .expect("should return root hash"),
            db_two
                .root_hash(None, grove_version)
                .unwrap()
                .expect("should return toor hash")
        );
    }

    #[test]
    fn test_tree_structure_is_persistent() {
        let grove_version = GroveVersion::latest();
        let tmp_dir = TempDir::new().unwrap();
        let element = Element::new_item(b"ayy".to_vec());
        // Create a scoped GroveDB
        let prev_root_hash = {
            let mut db = GroveDb::open(tmp_dir.path()).unwrap();
            add_test_leaves(&mut db, grove_version);

            // Insert some nested subtrees
            db.insert(
                [TEST_LEAF].as_ref(),
                b"key1",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree 1 insert");
            db.insert(
                [TEST_LEAF, b"key1"].as_ref(),
                b"key2",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree 2 insert");
            // Insert an element into subtree
            db.insert(
                [TEST_LEAF, b"key1", b"key2"].as_ref(),
                b"key3",
                element.clone(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful value insert");
            assert_eq!(
                db.get(
                    [TEST_LEAF, b"key1", b"key2"].as_ref(),
                    b"key3",
                    None,
                    grove_version
                )
                .unwrap()
                .expect("successful get 1"),
                element
            );
            db.root_hash(None, grove_version).unwrap().unwrap()
        };
        // Open a persisted GroveDB
        let db = GroveDb::open(tmp_dir).unwrap();
        assert_eq!(
            db.get(
                [TEST_LEAF, b"key1", b"key2"].as_ref(),
                b"key3",
                None,
                grove_version
            )
            .unwrap()
            .expect("successful get 2"),
            element
        );
        assert!(db
            .get(
                [TEST_LEAF, b"key1", b"key2"].as_ref(),
                b"key4",
                None,
                grove_version
            )
            .unwrap()
            .is_err());
        assert_eq!(
            prev_root_hash,
            db.root_hash(None, grove_version).unwrap().unwrap()
        );
    }

    #[test]
    fn test_root_tree_leaves_are_noted() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let transaction = db.start_transaction();
        db.check_subtree_exists_path_not_found(
            [TEST_LEAF].as_ref().into(),
            &transaction,
            grove_version,
        )
        .unwrap()
        .expect("should exist");
        db.check_subtree_exists_path_not_found(
            [ANOTHER_TEST_LEAF].as_ref().into(),
            &transaction,
            grove_version,
        )
        .unwrap()
        .expect("should exist");
    }

    #[test]
    fn test_proof_for_invalid_path_root_key() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        let query = Query::new();
        let path_query = PathQuery::new_unsized(vec![b"invalid_path_key".to_vec()], query);

        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        assert_eq!(result_set.len(), 0);
    }

    #[test]
    fn test_proof_for_invalid_path() {
        let grove_version = GroveVersion::latest();
        let db = make_deep_tree(grove_version);

        let query = Query::new();
        let path_query =
            PathQuery::new_unsized(vec![b"deep_leaf".to_vec(), b"invalid_key".to_vec()], query);

        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        assert_eq!(result_set.len(), 0);

        let query = Query::new();
        let path_query = PathQuery::new_unsized(
            vec![
                b"deep_leaf".to_vec(),
                b"deep_node_1".to_vec(),
                b"invalid_key".to_vec(),
            ],
            query,
        );

        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        assert_eq!(result_set.len(), 0);

        let query = Query::new();
        let path_query = PathQuery::new_unsized(
            vec![
                b"deep_leaf".to_vec(),
                b"deep_node_1".to_vec(),
                b"deeper_1".to_vec(),
                b"invalid_key".to_vec(),
            ],
            query,
        );

        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        assert_eq!(result_set.len(), 0);

        let query = Query::new();
        let path_query = PathQuery::new_unsized(
            vec![
                b"deep_leaf".to_vec(),
                b"early_invalid_key".to_vec(),
                b"deeper_1".to_vec(),
                b"invalid_key".to_vec(),
            ],
            query,
        );

        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        assert_eq!(result_set.len(), 0);
    }

    #[test]
    fn test_proof_for_non_existent_data() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_test_grovedb(grove_version);

        let mut query = Query::new();
        query.insert_key(b"key1".to_vec());

        // path to empty subtree
        let path_query = PathQuery::new_unsized(vec![TEST_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 0);
    }

    #[test]
    fn test_path_query_proofs_without_subquery_with_reference() {
        let grove_version = GroveVersion::latest();
        // Tree Structure
        // root
        //     test_leaf
        //         innertree
        //             k1,v1
        //             k2,v2
        //             k3,v3
        //     another_test_leaf
        //         innertree2
        //             k3,v3
        //             k4, reference to k1 in innertree
        //             k5, reference to k4 in innertree3
        //         innertree3
        //             k4,v4

        // Insert elements into grovedb instance
        let temp_db = make_test_grovedb(grove_version);
        // Insert level 1 nodes
        temp_db
            .insert(
                [TEST_LEAF].as_ref(),
                b"innertree",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"innertree2",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"innertree3",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        // Insert level 2 nodes
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key1",
                Element::new_item(b"value1".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key2",
                Element::new_item(b"value2".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key3",
                Element::new_item(b"value3".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree2"].as_ref(),
                b"key3",
                Element::new_item(b"value3".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree2"].as_ref(),
                b"key4",
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    TEST_LEAF.to_vec(),
                    b"innertree".to_vec(),
                    b"key1".to_vec(),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree3"].as_ref(),
                b"key4",
                Element::new_item(b"value4".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree2"].as_ref(),
                b"key5",
                Element::new_reference(ReferencePathType::AbsolutePathReference(vec![
                    ANOTHER_TEST_LEAF.to_vec(),
                    b"innertree3".to_vec(),
                    b"key4".to_vec(),
                ])),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");

        // Single key query
        let mut query = Query::new();
        query.insert_range_from(b"key4".to_vec()..);

        let path_query = PathQuery::new_unsized(
            vec![ANOTHER_TEST_LEAF.to_vec(), b"innertree2".to_vec()],
            query,
        );

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        assert_eq!(
            hex::encode(&proof),
            "005e02cfb7d035b8f4a3631be46c597510a16770c15c74331b3dc8dcb577a206e49675040a746\
        573745f6c65616632000e02010a696e6e657274726565320049870f2813c0c3c5c105a988c0ef1\
        372178245152fa9a43b209a6b6d95589bdc11010a746573745f6c6561663258040a696e6e65727\
        47265653200080201046b657934008ba21f835b2ff60f16b7fccfbda107bec3da0c4709357d40d\
        e223d769547ec21013a090155ea7d14038c7062d94930798f885a19d6ebff8a87489a1debf6656\
        04711010a696e6e65727472656532850198ebd6dc7e1c82951c41fcfa6487711cac6a399ebb01b\
        b979cbe4a51e0b2f08d06046b6579340009000676616c75653100bf2f052b01c2bb83ff3a40504\
        d42b5b9141c582a3e0c98679189b33a24478a6f1006046b6579350009000676616c75653400f08\
        4ffdbc429a89c9b6620e7224d73c2ee505eb7e6fb5eb574e1a8dc8b0d0884110001"
        );
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        let r1 = Element::new_item(b"value1".to_vec())
            .serialize(grove_version)
            .unwrap();
        let r2 = Element::new_item(b"value4".to_vec())
            .serialize(grove_version)
            .unwrap();

        compare_result_tuples(
            result_set,
            vec![(b"key4".to_vec(), r1), (b"key5".to_vec(), r2)],
        );
    }

    #[test]
    fn test_path_query_proofs_without_subquery() {
        let grove_version = GroveVersion::latest();
        // Tree Structure
        // root
        //     test_leaf
        //         innertree
        //             k1,v1
        //             k2,v2
        //             k3,v3
        //     another_test_leaf
        //         innertree2
        //             k3,v3
        //         innertree3
        //             k4,v4

        // Insert elements into grovedb instance
        let temp_db = make_test_grovedb(grove_version);
        // Insert level 1 nodes
        temp_db
            .insert(
                [TEST_LEAF].as_ref(),
                b"innertree",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"innertree2",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF].as_ref(),
                b"innertree3",
                Element::empty_tree(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        // Insert level 2 nodes
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key1",
                Element::new_item(b"value1".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key2",
                Element::new_item(b"value2".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [TEST_LEAF, b"innertree"].as_ref(),
                b"key3",
                Element::new_item(b"value3".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree2"].as_ref(),
                b"key3",
                Element::new_item(b"value3".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");
        temp_db
            .insert(
                [ANOTHER_TEST_LEAF, b"innertree3"].as_ref(),
                b"key4",
                Element::new_item(b"value4".to_vec()),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("successful subtree insert");

        // Single key query
        let mut query = Query::new();
        query.insert_key(b"key1".to_vec());

        let path_query =
            PathQuery::new_unsized(vec![TEST_LEAF.to_vec(), b"innertree".to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        assert_eq!(
            hex::encode(proof.as_slice()),
            "005c0409746573745f6c656166000d020109696e6e65727472656500fafa16d06e8d8696dae443731\
        ae2a4eae521e4a9a79c331c8a7e22e34c0f1a6e01b55f830550604719833d54ce2bf139aff4bb699fa\
        4111b9741633554318792c5110109746573745f6c656166350409696e6e65727472656500080201046\
        b657932004910536da659a3dbdbcf68c4a6630e72de4ba20cfc60b08b3dd45b4225a599b60109696e6\
        e6572747265655503046b6579310009000676616c7565310002018655e18e4555b0b65bbcec64c749d\
        b6b9ad84231969fb4fbe769a3093d10f2100198ebd6dc7e1c82951c41fcfa6487711cac6a399ebb01b\
        b979cbe4a51e0b2f08d110001"
        );
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        let r1 = Element::new_item(b"value1".to_vec())
            .serialize(grove_version)
            .unwrap();
        compare_result_tuples(result_set, vec![(b"key1".to_vec(), r1)]);

        // Range query + limit
        let mut query = Query::new();
        query.insert_range_after(b"key1".to_vec()..);
        let path_query = PathQuery::new(
            vec![TEST_LEAF.to_vec(), b"innertree".to_vec()],
            SizedQuery::new(query, Some(1), None),
        );

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        let r1 = Element::new_item(b"value2".to_vec())
            .serialize(grove_version)
            .unwrap();
        compare_result_tuples(result_set, vec![(b"key2".to_vec(), r1)]);

        // Range query + direction + limit
        let mut query = Query::new_with_direction(false);
        query.insert_all();
        let path_query = PathQuery::new(
            vec![TEST_LEAF.to_vec(), b"innertree".to_vec()],
            SizedQuery::new(query, Some(2), None),
        );

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        let r1 = Element::new_item(b"value3".to_vec())
            .serialize(grove_version)
            .unwrap();
        let r2 = Element::new_item(b"value2".to_vec())
            .serialize(grove_version)
            .unwrap();
        compare_result_tuples(
            result_set,
            vec![(b"key3".to_vec(), r1), (b"key2".to_vec(), r2)],
        );
    }

    #[test]
    fn test_path_query_proofs_with_default_subquery() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![TEST_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 5);

        let keys = [
            b"key1".to_vec(),
            b"key2".to_vec(),
            b"key3".to_vec(),
            b"key4".to_vec(),
            b"key5".to_vec(),
        ];
        let values = [
            b"value1".to_vec(),
            b"value2".to_vec(),
            b"value3".to_vec(),
            b"value4".to_vec(),
            b"value5".to_vec(),
        ];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        let mut query = Query::new();
        query.insert_range_after(b"innertree".to_vec()..);

        let mut subq = Query::new();
        subq.insert_all();
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![TEST_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 2);

        let keys = [b"key4".to_vec(), b"key5".to_vec()];
        let values = [b"value4".to_vec(), b"value5".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // range subquery
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_range_after_to_inclusive(b"key1".to_vec()..=b"key4".to_vec());
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![TEST_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version).expect(
                "should
    execute proof",
            );

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);

        let keys = [b"key2".to_vec(), b"key3".to_vec(), b"key4".to_vec()];
        let values = [b"value2".to_vec(), b"value3".to_vec(), b"value4".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // deep tree test
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();

        let mut sub_subquery = Query::new();
        sub_subquery.insert_all();

        subq.set_subquery(sub_subquery);
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 14);

        let keys = [
            b"key1".to_vec(),
            b"key2".to_vec(),
            b"key3".to_vec(),
            b"key4".to_vec(),
            b"key5".to_vec(),
            b"key6".to_vec(),
            b"key7".to_vec(),
            b"key8".to_vec(),
            b"key9".to_vec(),
            b"key10".to_vec(),
            b"key11".to_vec(),
            b"key12".to_vec(),
            b"key13".to_vec(),
            b"key14".to_vec(),
        ];
        let values = [
            b"value1".to_vec(),
            b"value2".to_vec(),
            b"value3".to_vec(),
            b"value4".to_vec(),
            b"value5".to_vec(),
            b"value6".to_vec(),
            b"value7".to_vec(),
            b"value8".to_vec(),
            b"value9".to_vec(),
            b"value10".to_vec(),
            b"value11".to_vec(),
            b"value12".to_vec(),
            b"value13".to_vec(),
            b"value14".to_vec(),
        ];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);
    }

    #[test]
    fn test_path_query_proofs_with_subquery_path() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();

        query.set_subquery_key(b"deeper_1".to_vec());
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);

        let keys = [b"key1".to_vec(), b"key2".to_vec(), b"key3".to_vec()];
        let values = [b"value1".to_vec(), b"value2".to_vec(), b"value3".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // test subquery path with valid n > 1 valid translation
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();

        query.set_subquery_path(vec![b"deep_node_1".to_vec(), b"deeper_1".to_vec()]);
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![], query);
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");
        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);

        let keys = [b"key1".to_vec(), b"key2".to_vec(), b"key3".to_vec()];
        let values = [b"value1".to_vec(), b"value2".to_vec(), b"value3".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // test subquery path with empty subquery path
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();

        query.set_subquery_path(vec![]);
        query.set_subquery(subq);

        let path_query =
            PathQuery::new_unsized(vec![b"deep_leaf".to_vec(), b"deep_node_1".to_vec()], query);
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");
        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 6);

        let keys = [
            b"key1".to_vec(),
            b"key2".to_vec(),
            b"key3".to_vec(),
            b"key4".to_vec(),
            b"key5".to_vec(),
            b"key6".to_vec(),
        ];
        let values = [
            b"value1".to_vec(),
            b"value2".to_vec(),
            b"value3".to_vec(),
            b"value4".to_vec(),
            b"value5".to_vec(),
            b"value6".to_vec(),
        ];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // test subquery path with an invalid translation
        // should generate a valid absence proof with an empty result set
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new();
        subq.insert_all();

        query.set_subquery_path(vec![
            b"deep_node_1".to_vec(),
            b"deeper_10".to_vec(),
            b"another_invalid_key".to_vec(),
        ]);
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![], query);
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");
        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 0);
    }

    #[test]
    fn test_path_query_proofs_with_key_and_subquery() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        let mut query = Query::new();
        query.insert_key(b"deep_node_1".to_vec());

        let mut subq = Query::new();
        subq.insert_all();

        query.set_subquery_key(b"deeper_1".to_vec());
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);

        let keys = [b"key1".to_vec(), b"key2".to_vec(), b"key3".to_vec()];
        let values = [b"value1".to_vec(), b"value2".to_vec(), b"value3".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);
    }

    #[test]
    fn test_path_query_proofs_with_conditional_subquery() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        let mut query = Query::new();
        query.insert_all();

        let mut subquery = Query::new();
        subquery.insert_all();

        let mut final_subquery = Query::new();
        final_subquery.insert_all();

        subquery.add_conditional_subquery(
            QueryItem::Key(b"deeper_4".to_vec()),
            None,
            Some(final_subquery),
        );

        query.set_subquery(subquery);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );

        let keys = [
            b"deeper_1".to_vec(),
            b"deeper_2".to_vec(),
            b"deeper_3".to_vec(),
            b"key10".to_vec(),
            b"key11".to_vec(),
            b"deeper_5".to_vec(),
        ];
        assert_eq!(result_set.len(), keys.len());

        // TODO: Is this defined behaviour
        for (index, key) in keys.iter().enumerate() {
            assert_eq!(&result_set[index].key, key);
        }

        // Default + Conditional subquery
        let mut query = Query::new();
        query.insert_all();

        let mut subquery = Query::new();
        subquery.insert_all();

        let mut final_conditional_subquery = Query::new();
        final_conditional_subquery.insert_all();

        let mut final_default_subquery = Query::new();
        final_default_subquery.insert_range_inclusive(b"key3".to_vec()..=b"key6".to_vec());

        subquery.add_conditional_subquery(
            QueryItem::Key(b"deeper_4".to_vec()),
            None,
            Some(final_conditional_subquery),
        );
        subquery.set_subquery(final_default_subquery);

        query.set_subquery(subquery);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 6);

        let keys = [
            b"key3".to_vec(),
            b"key4".to_vec(),
            b"key5".to_vec(),
            b"key6".to_vec(),
            b"key10".to_vec(),
            b"key11".to_vec(),
        ];
        let values = [
            b"value3".to_vec(),
            b"value4".to_vec(),
            b"value5".to_vec(),
            b"value6".to_vec(),
            b"value10".to_vec(),
            b"value11".to_vec(),
        ];
        let elements = values
            .map(|x| Element::new_item(x).serialize(grove_version).unwrap())
            .to_vec();
        // compare_result_sets(&elements, &result_set);
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);
    }

    #[test]
    fn test_path_query_proofs_with_sized_query() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        let mut query = Query::new();
        query.insert_all();

        let mut subquery = Query::new();
        subquery.insert_all();

        let mut final_conditional_subquery = Query::new();
        final_conditional_subquery.insert_all();

        let mut final_default_subquery = Query::new();
        final_default_subquery.insert_range_inclusive(b"key4".to_vec()..=b"key6".to_vec());

        subquery.add_conditional_subquery(
            QueryItem::Key(b"deeper_4".to_vec()),
            None,
            Some(final_conditional_subquery),
        );
        subquery.set_subquery(final_default_subquery);

        query.set_subquery(subquery);

        let path_query = PathQuery::new(
            vec![DEEP_LEAF.to_vec()],
            SizedQuery::new(query, Some(5), None), /* we need to add a bigger limit because of
                                                    * empty proved subtrees */
        );
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 3);

        let keys = [b"key4".to_vec(), b"key5".to_vec(), b"key6".to_vec()];
        let values = [b"value4".to_vec(), b"value5".to_vec(), b"value6".to_vec()];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);
    }

    #[test]
    fn test_path_query_proof_with_range_subquery_and_limit() {
        let grove_version = GroveVersion::latest();
        let db = make_deep_tree(grove_version);

        // Create a path query with a range query, subquery, and limit
        let mut main_query = Query::new();
        main_query.insert_range_after(b"deeper_3".to_vec()..);

        let mut subquery = Query::new();
        subquery.insert_all();

        main_query.set_subquery(subquery);

        let path_query = PathQuery::new(
            vec![DEEP_LEAF.to_vec(), b"deep_node_2".to_vec()],
            SizedQuery::new(main_query.clone(), Some(3), None),
        );

        // Generate proof
        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();

        // Verify proof
        let verification_result = GroveDb::verify_query_raw(&proof, &path_query, grove_version);

        match verification_result {
            Ok((hash, result_set)) => {
                // Check if the hash matches the root hash
                assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
                // Check if we got the correct number of results
                assert_eq!(result_set.len(), 3, "Expected 3 results due to limit");
            }
            Err(e) => {
                panic!("Proof verification failed: {:?}", e);
            }
        }

        // Now test without a limit to compare
        let path_query_no_limit = PathQuery::new(
            vec![DEEP_LEAF.to_vec(), b"deep_node_2".to_vec()],
            SizedQuery::new(main_query.clone(), None, None),
        );

        let proof_no_limit = db
            .prove_query(&path_query_no_limit, None, grove_version)
            .unwrap()
            .unwrap();
        let verification_result_no_limit =
            GroveDb::verify_query_raw(&proof_no_limit, &path_query_no_limit, grove_version);

        match verification_result_no_limit {
            Ok((hash, result_set)) => {
                assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
                assert_eq!(result_set.len(), 5, "Expected 5 results without limit");
            }
            Err(e) => {
                panic!("Proof verification failed (no limit): {:?}", e);
            }
        }
    }

    #[test]
    fn test_path_query_proof_with_range_subquery_and_limit_with_sum_trees() {
        let grove_version = GroveVersion::latest();
        let db = make_deep_tree_with_sum_trees(grove_version);

        // Create a path query with a range query, subquery, and limit
        let mut main_query = Query::new();
        main_query.insert_key(b"a".to_vec());
        main_query.insert_range_after(b"b".to_vec()..);

        let mut subquery = Query::new();
        subquery.insert_all();

        main_query.set_subquery(subquery);

        main_query.add_conditional_subquery(QueryItem::Key(b"a".to_vec()), None, None);

        let path_query = PathQuery::new(
            vec![DEEP_LEAF.to_vec(), b"deep_node_1".to_vec()],
            SizedQuery::new(main_query.clone(), Some(3), None),
        );

        let non_proved_result_elements = db
            .query(
                &path_query,
                false,
                false,
                false,
                QueryResultType::QueryPathKeyElementTrioResultType,
                None,
                grove_version,
            )
            .unwrap()
            .expect("expected query to execute")
            .0;

        assert_eq!(
            non_proved_result_elements.len(),
            3,
            "Expected 3 results due to limit"
        );

        let key_elements = non_proved_result_elements.to_key_elements();

        assert_eq!(
            key_elements,
            vec![
                (vec![97], Element::new_item("storage".as_bytes().to_vec())),
                (vec![49], Element::SumTree(Some(vec![0; 32]), 2, None)),
                (vec![48], Element::new_item("v1".as_bytes().to_vec()))
            ]
        );

        // Generate proof
        let proof = db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();

        // Verify proof
        let (hash, result_set) = GroveDb::verify_query_raw(&proof, &path_query, grove_version)
            .expect("proof verification failed");

        // Check if the hash matches the root hash
        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
        // Check if we got the correct number of results
        assert_eq!(result_set.len(), 3, "Expected 3 results due to limit");

        // Now test without a limit to compare
        let path_query_no_limit = PathQuery::new(
            vec![DEEP_LEAF.to_vec(), b"deep_node_1".to_vec()],
            SizedQuery::new(main_query.clone(), None, None),
        );

        let proof_no_limit = db
            .prove_query(&path_query_no_limit, None, grove_version)
            .unwrap()
            .unwrap();
        let verification_result_no_limit =
            GroveDb::verify_query_raw(&proof_no_limit, &path_query_no_limit, grove_version);

        match verification_result_no_limit {
            Ok((hash, result_set)) => {
                assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());
                assert_eq!(result_set.len(), 29, "Expected 29 results without limit");
            }
            Err(e) => {
                panic!("Proof verification failed (no limit): {:?}", e);
            }
        }
    }

    #[test]
    fn test_path_query_proofs_with_direction() {
        let grove_version = GroveVersion::latest();
        let temp_db = make_deep_tree(grove_version);

        // root
        //     deep_leaf
        //          deep_node_1
        //              deeper_1
        //                  k1,v1
        //                  k2,v2
        //                  k3,v3
        //              deeper_2
        //                  k4,v4
        //                  k5,v5
        //                  k6,v6
        //          deep_node_2
        //              deeper_3
        //                  k7,v7
        //                  k8,v8
        //                  k9,v9
        //              deeper_4
        //                  k10,v10
        //                  k11,v11
        //              deeper_5
        //                  k12,v12
        //                  k13,v13
        //                  k14,v14

        let mut query = Query::new_with_direction(false);
        query.insert_all();

        let mut subquery = Query::new_with_direction(false);
        subquery.insert_all();

        let mut final_conditional_subquery = Query::new_with_direction(false);
        final_conditional_subquery.insert_all();

        let mut final_default_subquery = Query::new_with_direction(false);
        final_default_subquery.insert_range_inclusive(b"key3".to_vec()..=b"key6".to_vec());

        subquery.add_conditional_subquery(
            QueryItem::Key(b"deeper_4".to_vec()),
            None,
            Some(final_conditional_subquery),
        );
        subquery.set_subquery(final_default_subquery);

        query.set_subquery(subquery);

        let path_query = PathQuery::new(
            vec![DEEP_LEAF.to_vec()],
            SizedQuery::new(query, Some(6), None), /* we need 6 because of intermediate empty
                                                    * trees in proofs */
        );
        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 4);

        let keys = [
            b"key11".to_vec(),
            b"key10".to_vec(),
            b"key6".to_vec(),
            b"key5".to_vec(),
        ];
        let values = [
            b"value11".to_vec(),
            b"value10".to_vec(),
            b"value6".to_vec(),
            b"value5".to_vec(),
        ];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);

        // combined directions
        let mut query = Query::new();
        query.insert_all();

        let mut subq = Query::new_with_direction(false);
        subq.insert_all();

        let mut sub_subquery = Query::new();
        sub_subquery.insert_all();

        subq.set_subquery(sub_subquery);
        query.set_subquery(subq);

        let path_query = PathQuery::new_unsized(vec![DEEP_LEAF.to_vec()], query);

        let proof = temp_db
            .prove_query(&path_query, None, grove_version)
            .unwrap()
            .unwrap();
        let (hash, result_set) =
            GroveDb::verify_query_raw(proof.as_slice(), &path_query, grove_version)
                .expect("should execute proof");

        assert_eq!(
            hash,
            temp_db.root_hash(None, grove_version).unwrap().unwrap()
        );
        assert_eq!(result_set.len(), 14);

        let keys = [
            b"key4".to_vec(),
            b"key5".to_vec(),
            b"key6".to_vec(),
            b"key1".to_vec(),
            b"key2".to_vec(),
            b"key3".to_vec(),
            b"key12".to_vec(),
            b"key13".to_vec(),
            b"key14".to_vec(),
            b"key10".to_vec(),
            b"key11".to_vec(),
            b"key7".to_vec(),
            b"key8".to_vec(),
            b"key9".to_vec(),
        ];
        let values = [
            b"value4".to_vec(),
            b"value5".to_vec(),
            b"value6".to_vec(),
            b"value1".to_vec(),
            b"value2".to_vec(),
            b"value3".to_vec(),
            b"value12".to_vec(),
            b"value13".to_vec(),
            b"value14".to_vec(),
            b"value10".to_vec(),
            b"value11".to_vec(),
            b"value7".to_vec(),
            b"value8".to_vec(),
            b"value9".to_vec(),
        ];
        let elements = values.map(|x| Element::new_item(x).serialize(grove_version).unwrap());
        let expected_result_set: Vec<(Vec<u8>, Vec<u8>)> = keys.into_iter().zip(elements).collect();
        compare_result_tuples(result_set, expected_result_set);
    }

    #[test]
    fn test_checkpoint() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let element1 = Element::new_item(b"ayy".to_vec());

        db.insert(
            EMPTY_PATH,
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert a subtree 1 into GroveDB");
        db.insert(
            [b"key1".as_ref()].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert a subtree 2 into GroveDB");
        db.insert(
            [b"key1".as_ref(), b"key2".as_ref()].as_ref(),
            b"key3",
            element1.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert an item into GroveDB");

        assert_eq!(
            db.get(
                [b"key1".as_ref(), b"key2".as_ref()].as_ref(),
                b"key3",
                None,
                grove_version
            )
            .unwrap()
            .expect("cannot get from grovedb"),
            element1
        );

        let tempdir_parent = TempDir::new().expect("cannot open tempdir");
        let checkpoint_tempdir = tempdir_parent.path().join("checkpoint");
        db.create_checkpoint(&checkpoint_tempdir)
            .expect("cannot create checkpoint");

        let checkpoint_db =
            GroveDb::open(checkpoint_tempdir).expect("cannot open grovedb from checkpoint");

        assert_eq!(
            db.get(
                [b"key1".as_ref(), b"key2".as_ref()].as_ref(),
                b"key3",
                None,
                grove_version
            )
            .unwrap()
            .expect("cannot get from grovedb"),
            element1
        );
        assert_eq!(
            checkpoint_db
                .get(
                    [b"key1".as_ref(), b"key2".as_ref()].as_ref(),
                    b"key3",
                    None,
                    grove_version
                )
                .unwrap()
                .expect("cannot get from checkpoint"),
            element1
        );

        let element2 = Element::new_item(b"ayy2".to_vec());
        let element3 = Element::new_item(b"ayy3".to_vec());

        checkpoint_db
            .insert(
                [b"key1".as_ref()].as_ref(),
                b"key4",
                element2.clone(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("cannot insert into checkpoint");

        db.insert(
            [b"key1".as_ref()].as_ref(),
            b"key4",
            element3.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert into GroveDB");

        assert_eq!(
            checkpoint_db
                .get([b"key1".as_ref()].as_ref(), b"key4", None, grove_version)
                .unwrap()
                .expect("cannot get from checkpoint"),
            element2,
        );

        assert_eq!(
            db.get([b"key1".as_ref()].as_ref(), b"key4", None, grove_version)
                .unwrap()
                .expect("cannot get from GroveDB"),
            element3
        );

        checkpoint_db
            .insert(
                [b"key1".as_ref()].as_ref(),
                b"key5",
                element3.clone(),
                None,
                None,
                grove_version,
            )
            .unwrap()
            .expect("cannot insert into checkpoint");

        db.insert(
            [b"key1".as_ref()].as_ref(),
            b"key6",
            element3,
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert into GroveDB");

        assert!(matches!(
            checkpoint_db
                .get([b"key1".as_ref()].as_ref(), b"key6", None, grove_version)
                .unwrap(),
            Err(Error::PathKeyNotFound(_))
        ));

        assert!(matches!(
            db.get([b"key1".as_ref()].as_ref(), b"key5", None, grove_version)
                .unwrap(),
            Err(Error::PathKeyNotFound(_))
        ));
    }

    #[test]
    fn test_is_empty_tree() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        // Create an empty tree with no elements
        db.insert(
            [TEST_LEAF].as_ref(),
            b"innertree",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        assert!(db
            .is_empty_tree([TEST_LEAF, b"innertree"].as_ref(), None, grove_version)
            .unwrap()
            .expect("path is valid tree"));

        // add an element to the tree to make it non-empty
        db.insert(
            [TEST_LEAF, b"innertree"].as_ref(),
            b"key1",
            Element::new_item(b"hello".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();
        assert!(!db
            .is_empty_tree([TEST_LEAF, b"innertree"].as_ref(), None, grove_version)
            .unwrap()
            .expect("path is valid tree"));
    }

    #[test]
    fn transaction_should_be_aborted_when_rollback_is_called() {
        let grove_version = GroveVersion::latest();
        let item_key = b"key3";

        let db = make_test_grovedb(grove_version);
        let transaction = db.start_transaction();

        let element1 = Element::new_item(b"ayy".to_vec());

        let result = db
            .insert(
                [TEST_LEAF].as_ref(),
                item_key,
                element1,
                None,
                Some(&transaction),
                grove_version,
            )
            .unwrap();

        assert!(matches!(result, Ok(())));

        db.rollback_transaction(&transaction).unwrap();

        let result = db
            .get(
                [TEST_LEAF].as_ref(),
                item_key,
                Some(&transaction),
                grove_version,
            )
            .unwrap();
        assert!(matches!(result, Err(Error::PathKeyNotFound(_))));
    }

    #[test]
    fn transaction_should_be_aborted() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let transaction = db.start_transaction();

        let item_key = b"key3";
        let element = Element::new_item(b"ayy".to_vec());

        db.insert(
            [TEST_LEAF].as_ref(),
            item_key,
            element,
            None,
            Some(&transaction),
            grove_version,
        )
        .unwrap()
        .unwrap();

        drop(transaction);

        // Transactional data shouldn't be committed to the main database
        let result = db
            .get([TEST_LEAF].as_ref(), item_key, None, grove_version)
            .unwrap();
        assert!(matches!(result, Err(Error::PathKeyNotFound(_))));
    }

    #[test]
    fn test_subtree_pairs_iterator() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let element = Element::new_item(b"ayy".to_vec());
        let element2 = Element::new_item(b"lmao".to_vec());

        // Insert some nested subtrees
        db.insert(
            [TEST_LEAF].as_ref(),
            b"subtree1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");
        db.insert(
            [TEST_LEAF, b"subtree1"].as_ref(),
            b"subtree11",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 2 insert");
        // Insert an element into subtree
        db.insert(
            [TEST_LEAF, b"subtree1", b"subtree11"].as_ref(),
            b"key1",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        assert_eq!(
            db.get(
                [TEST_LEAF, b"subtree1", b"subtree11"].as_ref(),
                b"key1",
                None,
                grove_version
            )
            .unwrap()
            .expect("successful get 1"),
            element
        );
        db.insert(
            [TEST_LEAF, b"subtree1", b"subtree11"].as_ref(),
            b"key0",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF, b"subtree1"].as_ref(),
            b"subtree12",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 3 insert");
        db.insert(
            [TEST_LEAF, b"subtree1"].as_ref(),
            b"key1",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF, b"subtree1"].as_ref(),
            b"key2",
            element2.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        // Iterate over subtree1 to see if keys of other subtrees messed up
        // let mut iter = db
        //     .elements_iterator([TEST_LEAF, b"subtree1"].as_ref(), None)
        //     .expect("cannot create iterator");
        let transaction = db.grove_db.start_transaction();
        let storage_context = db
            .grove_db
            .db
            .get_transactional_storage_context(
                [TEST_LEAF, b"subtree1"].as_ref().into(),
                None,
                &transaction,
            )
            .unwrap();
        let mut iter = Element::iterator(storage_context.raw_iter()).unwrap();
        assert_eq!(
            iter.next_element(grove_version).unwrap().unwrap(),
            Some((b"key1".to_vec(), element))
        );
        assert_eq!(
            iter.next_element(grove_version).unwrap().unwrap(),
            Some((b"key2".to_vec(), element2))
        );
        let subtree_element = iter.next_element(grove_version).unwrap().unwrap().unwrap();
        assert_eq!(subtree_element.0, b"subtree11".to_vec());
        assert!(matches!(subtree_element.1, Element::Tree(..)));
        let subtree_element = iter.next_element(grove_version).unwrap().unwrap().unwrap();
        assert_eq!(subtree_element.0, b"subtree12".to_vec());
        assert!(matches!(subtree_element.1, Element::Tree(..)));
        assert!(matches!(
            iter.next_element(grove_version).unwrap(),
            Ok(None)
        ));
    }

    #[test]
    fn test_find_subtrees() {
        let grove_version = GroveVersion::latest();
        let element = Element::new_item(b"ayy".to_vec());
        let db = make_test_grovedb(grove_version);
        // Insert some nested subtrees
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 2 insert");
        // Insert an element into subtree
        db.insert(
            [TEST_LEAF, b"key1", b"key2"].as_ref(),
            b"key3",
            element,
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key4",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 3 insert");
        let subtrees = db
            .find_subtrees(&[TEST_LEAF].as_ref().into(), None, grove_version)
            .unwrap()
            .expect("cannot get subtrees");
        assert_eq!(
            vec![
                vec![TEST_LEAF],
                vec![TEST_LEAF, b"key1"],
                vec![TEST_LEAF, b"key4"],
                vec![TEST_LEAF, b"key1", b"key2"],
            ],
            subtrees
        );
    }

    #[test]
    fn test_root_subtree_has_root_key() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let transaction = db.start_transaction();

        let storage = db
            .db
            .get_transactional_storage_context(EMPTY_PATH, None, &transaction)
            .unwrap();
        let root_merk = Merk::open_base(
            storage,
            TreeType::NormalTree,
            Some(&Element::value_defined_cost_for_serialized_value),
            grove_version,
        )
        .unwrap()
        .expect("expected to get root merk");
        let (_, root_key, _) = root_merk
            .root_hash_key_and_aggregate_data()
            .unwrap()
            .expect("expected to get root hash, key and sum");
        assert!(root_key.is_some())
    }

    #[test]
    fn test_get_subtree() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let element = Element::new_item(b"ayy".to_vec());

        // Returns error is subtree is not valid
        {
            let subtree = db
                .get([TEST_LEAF].as_ref(), b"invalid_tree", None, grove_version)
                .unwrap();
            assert!(subtree.is_err());

            // Doesn't return an error for subtree that exists but empty
            let subtree = db.get(EMPTY_PATH, TEST_LEAF, None, grove_version).unwrap();
            assert!(subtree.is_ok());
        }

        // Insert some nested subtrees
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");

        let key1_tree = db
            .get(EMPTY_PATH, TEST_LEAF, None, grove_version)
            .unwrap()
            .expect("expected to get a root tree");

        assert!(
            matches!(key1_tree, Element::Tree(Some(_), _)),
            "{}",
            format!(
                "expected tree with root key, got {:?}",
                if let Element::Tree(tree, ..) = key1_tree {
                    format!("{:?}", tree)
                } else {
                    "not a tree".to_string()
                }
            )
        );

        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 2 insert");

        // Insert an element into subtree
        db.insert(
            [TEST_LEAF, b"key1", b"key2"].as_ref(),
            b"key3",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key4",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 3 insert");

        // Retrieve subtree instance
        // Check if it returns the same instance that was inserted
        {
            let transaction = db.grove_db.start_transaction();

            let subtree_storage = db
                .grove_db
                .db
                .get_transactional_storage_context(
                    [TEST_LEAF, b"key1", b"key2"].as_ref().into(),
                    None,
                    &transaction,
                )
                .unwrap();
            let subtree = Merk::open_layered_with_root_key(
                subtree_storage,
                Some(b"key3".to_vec()),
                TreeType::NormalTree,
                Some(&Element::value_defined_cost_for_serialized_value),
                grove_version,
            )
            .unwrap()
            .expect("cannot open merk");
            let result_element = Element::get(&subtree, b"key3", true, grove_version)
                .unwrap()
                .unwrap();
            assert_eq!(result_element, Element::new_item(b"ayy".to_vec()));

            db.grove_db
                .commit_transaction(transaction)
                .unwrap()
                .unwrap();
        }
        // Insert a new tree with transaction
        let transaction = db.start_transaction();

        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"innertree",
            Element::empty_tree(),
            None,
            Some(&transaction),
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");

        db.insert(
            [TEST_LEAF, b"key1", b"innertree"].as_ref(),
            b"key4",
            element,
            None,
            Some(&transaction),
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        // Retrieve subtree instance with transaction
        let subtree_storage = db
            .grove_db
            .db
            .get_transactional_storage_context(
                [TEST_LEAF, b"key1", b"innertree"].as_ref().into(),
                None,
                &transaction,
            )
            .unwrap();
        let subtree = Merk::open_layered_with_root_key(
            subtree_storage,
            Some(b"key4".to_vec()),
            TreeType::NormalTree,
            Some(&Element::value_defined_cost_for_serialized_value),
            grove_version,
        )
        .unwrap()
        .expect("cannot open merk");
        let result_element = Element::get(&subtree, b"key4", true, grove_version)
            .unwrap()
            .unwrap();
        assert_eq!(result_element, Element::new_item(b"ayy".to_vec()));

        // Should be able to retrieve instances created before transaction
        let subtree_storage = db
            .grove_db
            .db
            .get_transactional_storage_context(
                [TEST_LEAF, b"key1", b"key2"].as_ref().into(),
                None,
                &transaction,
            )
            .unwrap();
        let subtree = Merk::open_layered_with_root_key(
            subtree_storage,
            Some(b"key3".to_vec()),
            TreeType::NormalTree,
            Some(&Element::value_defined_cost_for_serialized_value),
            grove_version,
        )
        .unwrap()
        .expect("cannot open merk");
        let result_element = Element::get(&subtree, b"key3", true, grove_version)
            .unwrap()
            .unwrap();
        assert_eq!(result_element, Element::new_item(b"ayy".to_vec()));
    }

    #[test]
    fn test_get_full_query() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        // Insert a couple of subtrees first
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree insert");
        // Insert some elements into subtree
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key3",
            Element::new_item(b"ayya".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key4",
            Element::new_item(b"ayyb".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key5",
            Element::new_item(b"ayyc".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");
        db.insert(
            [TEST_LEAF, b"key2"].as_ref(),
            b"key6",
            Element::new_item(b"ayyd".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        //          Test_Leaf
        // ___________________________
        //         /        \
        //     key1           key2
        // ___________________________
        //      |              |
        //     key4          key6
        //     / \
        //   key3 key5
        //

        let path1 = vec![TEST_LEAF.to_vec(), b"key1".to_vec()];
        let path2 = vec![TEST_LEAF.to_vec(), b"key2".to_vec()];
        let mut query1 = Query::new();
        let mut query2 = Query::new();
        query1.insert_range_inclusive(b"key3".to_vec()..=b"key4".to_vec());
        query2.insert_key(b"key6".to_vec());

        let path_query1 = PathQuery::new_unsized(path1, query1);
        // should get back key3, key4
        let path_query2 = PathQuery::new_unsized(path2, query2);
        // should get back key6

        assert_eq!(
            db.query_many_raw(
                &[&path_query1, &path_query2],
                true,
                true,
                true,
                QueryKeyElementPairResultType,
                None,
                grove_version
            )
            .unwrap()
            .expect("expected successful get_query")
            .to_key_elements(),
            vec![
                (b"key3".to_vec(), Element::new_item(b"ayya".to_vec())),
                (b"key4".to_vec(), Element::new_item(b"ayyb".to_vec())),
                (b"key6".to_vec(), Element::new_item(b"ayyd".to_vec())),
            ]
        );
    }

    #[test]
    fn test_aux_uses_separate_cf() {
        let grove_version = GroveVersion::latest();
        let element = Element::new_item(b"ayy".to_vec());
        let db = make_test_grovedb(grove_version);
        // Insert some nested subtrees
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 1 insert");
        db.insert(
            [TEST_LEAF, b"key1"].as_ref(),
            b"key2",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful subtree 2 insert");
        // Insert an element into subtree
        db.insert(
            [TEST_LEAF, b"key1", b"key2"].as_ref(),
            b"key3",
            element.clone(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("successful value insert");

        db.put_aux(b"key1", b"a", None, None)
            .unwrap()
            .expect("cannot put aux");
        db.put_aux(b"key2", b"b", None, None)
            .unwrap()
            .expect("cannot put aux");
        db.put_aux(b"key3", b"c", None, None)
            .unwrap()
            .expect("cannot put aux");
        db.delete_aux(b"key3", None, None)
            .unwrap()
            .expect("cannot delete from aux");

        assert_eq!(
            db.get(
                [TEST_LEAF, b"key1", b"key2"].as_ref(),
                b"key3",
                None,
                grove_version
            )
            .unwrap()
            .expect("cannot get element"),
            element
        );
        assert_eq!(
            db.get_aux(b"key1", None)
                .unwrap()
                .expect("cannot get from aux"),
            Some(b"a".to_vec())
        );
        assert_eq!(
            db.get_aux(b"key2", None)
                .unwrap()
                .expect("cannot get from aux"),
            Some(b"b".to_vec())
        );
        assert_eq!(
            db.get_aux(b"key3", None)
                .unwrap()
                .expect("cannot get from aux"),
            None
        );
        assert_eq!(
            db.get_aux(b"key4", None)
                .unwrap()
                .expect("cannot get from aux"),
            None
        );
    }

    #[test]
    fn test_aux_with_transaction() {
        let grove_version = GroveVersion::latest();
        let element = Element::new_item(b"ayy".to_vec());
        let aux_value = b"ayylmao".to_vec();
        let key = b"key".to_vec();
        let db = make_test_grovedb(grove_version);
        let transaction = db.start_transaction();

        // Insert a regular data with aux data in the same transaction
        db.insert(
            [TEST_LEAF].as_ref(),
            &key,
            element,
            None,
            Some(&transaction),
            grove_version,
        )
        .unwrap()
        .expect("unable to insert");
        db.put_aux(&key, &aux_value, None, Some(&transaction))
            .unwrap()
            .expect("unable to insert aux value");
        assert_eq!(
            db.get_aux(&key, Some(&transaction))
                .unwrap()
                .expect("unable to get aux value"),
            Some(aux_value.clone())
        );
        // Cannot reach the data outside of transaction
        assert_eq!(
            db.get_aux(&key, None)
                .unwrap()
                .expect("unable to get aux value"),
            None
        );
        // And should be able to get data when committed
        db.commit_transaction(transaction)
            .unwrap()
            .expect("unable to commit transaction");
        assert_eq!(
            db.get_aux(&key, None)
                .unwrap()
                .expect("unable to get committed aux value"),
            Some(aux_value)
        );
    }

    #[test]
    fn test_root_hash() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        // Check hashes are different if tree is edited
        let old_root_hash = db.root_hash(None, grove_version).unwrap();
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key1",
            Element::new_item(b"ayy".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("unable to insert an item");
        assert_ne!(
            old_root_hash.unwrap(),
            db.root_hash(None, grove_version).unwrap().unwrap()
        );

        // Check isolation
        let transaction = db.start_transaction();

        db.insert(
            [TEST_LEAF].as_ref(),
            b"key2",
            Element::new_item(b"ayy".to_vec()),
            None,
            Some(&transaction),
            grove_version,
        )
        .unwrap()
        .expect("unable to insert an item");
        let root_hash_outside = db.root_hash(None, grove_version).unwrap().unwrap();
        assert_ne!(
            db.root_hash(Some(&transaction), grove_version)
                .unwrap()
                .unwrap(),
            root_hash_outside
        );

        assert_eq!(
            db.root_hash(None, grove_version).unwrap().unwrap(),
            root_hash_outside
        );
        db.commit_transaction(transaction).unwrap().unwrap();
        assert_ne!(
            db.root_hash(None, grove_version).unwrap().unwrap(),
            root_hash_outside
        );
    }

    #[test]
    fn test_get_non_existing_root_leaf() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        assert!(db
            .get(EMPTY_PATH, b"ayy", None, grove_version)
            .unwrap()
            .is_err());
    }

    #[test]
    fn test_check_subtree_exists_function() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key_scalar",
            Element::new_item(b"ayy".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key_subtree",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");

        // Empty tree path means root always exist
        assert!(db
            .check_subtree_exists_invalid_path(EMPTY_PATH, None, grove_version)
            .unwrap()
            .is_ok());

        // TEST_LEAF should be a tree
        assert!(db
            .check_subtree_exists_invalid_path([TEST_LEAF].as_ref().into(), None, grove_version)
            .unwrap()
            .is_ok());

        // TEST_LEAF.key_subtree should be a tree
        assert!(db
            .check_subtree_exists_invalid_path(
                [TEST_LEAF, b"key_subtree"].as_ref().into(),
                None,
                grove_version
            )
            .unwrap()
            .is_ok());

        // TEST_LEAF.key_scalar should NOT be a tree
        assert!(matches!(
            db.check_subtree_exists_invalid_path(
                [TEST_LEAF, b"key_scalar"].as_ref().into(),
                None,
                grove_version
            )
            .unwrap(),
            Err(Error::InvalidPath(_))
        ));
    }

    #[test]
    fn test_tree_value_exists_method_no_tx() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        // Test keys in non-root tree
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key",
            Element::new_item(b"ayy".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");
        assert!(db
            .has_raw([TEST_LEAF].as_ref(), b"key", None, grove_version)
            .unwrap()
            .unwrap());
        assert!(!db
            .has_raw([TEST_LEAF].as_ref(), b"badkey", None, grove_version)
            .unwrap()
            .unwrap());

        // Test keys for a root tree
        db.insert(
            EMPTY_PATH,
            b"leaf",
            Element::empty_tree(),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");

        assert!(db
            .has_raw(EMPTY_PATH, b"leaf", None, grove_version)
            .unwrap()
            .unwrap());
        assert!(db
            .has_raw(EMPTY_PATH, TEST_LEAF, None, grove_version)
            .unwrap()
            .unwrap());
        assert!(!db
            .has_raw(EMPTY_PATH, b"badleaf", None, grove_version)
            .unwrap()
            .unwrap());
    }

    #[test]
    fn test_tree_value_exists_method_tx() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let tx = db.start_transaction();
        // Test keys in non-root tree
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key",
            Element::new_item(b"ayy".to_vec()),
            None,
            Some(&tx),
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");
        assert!(db
            .has_raw([TEST_LEAF].as_ref(), b"key", Some(&tx), grove_version)
            .unwrap()
            .unwrap());
        assert!(!db
            .has_raw([TEST_LEAF].as_ref(), b"key", None, grove_version)
            .unwrap()
            .unwrap());

        // Test keys for a root tree
        db.insert(
            EMPTY_PATH,
            b"leaf",
            Element::empty_tree(),
            None,
            Some(&tx),
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");
        assert!(db
            .has_raw(EMPTY_PATH, b"leaf", Some(&tx), grove_version)
            .unwrap()
            .unwrap());
        assert!(!db
            .has_raw(EMPTY_PATH, b"leaf", None, grove_version)
            .unwrap()
            .unwrap());

        db.commit_transaction(tx)
            .unwrap()
            .expect("cannot commit transaction");
        assert!(db
            .has_raw([TEST_LEAF].as_ref(), b"key", None, grove_version)
            .unwrap()
            .unwrap());
        assert!(db
            .has_raw(EMPTY_PATH, b"leaf", None, grove_version)
            .unwrap()
            .unwrap());
    }

    #[test]
    fn test_storage_wipe() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);
        let _path = db._tmp_dir.path();

        // Test keys in non-root tree
        db.insert(
            [TEST_LEAF].as_ref(),
            b"key",
            Element::new_item(b"ayy".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .expect("cannot insert item");

        // retrieve key before wipe
        let elem = db
            .get(&[TEST_LEAF], b"key", None, grove_version)
            .unwrap()
            .unwrap();
        assert_eq!(elem, Element::new_item(b"ayy".to_vec()));

        // wipe the database
        db.grove_db.wipe().unwrap();

        // retrieve key after wipe
        let elem_result = db.get(&[TEST_LEAF], b"key", None, grove_version).unwrap();
        assert!(elem_result.is_err());
        assert!(matches!(
            elem_result,
            Err(Error::PathParentLayerNotFound(..))
        ));
    }

    #[test]
    fn test_grovedb_verify_corrupted_reference() {
        // This test is dedicated to a case when references are out of sync, but
        // `verify_grovedb` must detect this case as any other inconsistency

        let grove_version = GroveVersion::latest();
        let db = make_deep_tree(grove_version);

        // Insert a reference
        db.insert(
            &[TEST_LEAF, b"innertree"],
            b"ref",
            Element::Reference(
                ReferencePathType::AbsolutePathReference(vec![
                    ANOTHER_TEST_LEAF.to_vec(),
                    b"innertree2".to_vec(),
                    b"key3".to_vec(),
                ]),
                None,
                None,
            ),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        // Ensure we can prove and verify the inserted reference
        let query = PathQuery {
            path: vec![TEST_LEAF.to_vec(), b"innertree".to_vec()],
            query: SizedQuery {
                query: Query {
                    items: vec![QueryItem::Key(b"ref".to_vec())],
                    default_subquery_branch: SubqueryBranch {
                        subquery_path: None,
                        subquery: None,
                    },
                    conditional_subquery_branches: None,
                    left_to_right: true,
                    add_parent_tree_on_subquery: false,
                },
                limit: None,
                offset: None,
            },
        };
        let proof = db
            .prove_query(&query, None, grove_version)
            .unwrap()
            .unwrap();

        let (hash, _) = GroveDb::verify_query(&proof, &query, grove_version).unwrap();
        assert_eq!(hash, db.root_hash(None, grove_version).unwrap().unwrap());

        // Update referenced value to break things
        db.insert(
            &[ANOTHER_TEST_LEAF.to_vec(), b"innertree2".to_vec()],
            b"key3",
            Element::Item(b"idk something else i guess?".to_vec(), None),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        let proof = db
            .prove_query(&query, None, grove_version)
            .unwrap()
            .unwrap();

        assert!(matches!(
            GroveDb::verify_query(&proof, &query, grove_version),
            Err(_)
        ));

        // `verify_grovedb` must identify issues
        assert!(
            db.verify_grovedb(None, true, false, grove_version)
                .unwrap()
                .len()
                > 0
        );
    }

    #[test]
    fn test_verify_corrupted_long_reference() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        db.insert(
            &[TEST_LEAF],
            b"value",
            Element::new_item(b"hello".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        db.insert(
            &[TEST_LEAF],
            b"refc",
            Element::new_reference(ReferencePathType::SiblingReference(b"value".to_vec())),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        db.insert(
            &[TEST_LEAF],
            b"refb",
            Element::new_reference(ReferencePathType::SiblingReference(b"refc".to_vec())),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        db.insert(
            &[TEST_LEAF],
            b"refa",
            Element::new_reference(ReferencePathType::SiblingReference(b"refb".to_vec())),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        assert!(db
            .verify_grovedb(None, true, false, grove_version)
            .unwrap()
            .is_empty());

        // Breaking things there:
        db.insert(
            &[TEST_LEAF],
            b"value",
            Element::new_item(b"not hello >:(".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        assert!(!db
            .verify_grovedb(None, true, false, grove_version)
            .unwrap()
            .is_empty());
    }

    #[test]
    fn test_verify_corrupted_long_reference_batch() {
        let grove_version = GroveVersion::latest();
        let db = make_test_grovedb(grove_version);

        let ops = vec![
            QualifiedGroveDbOp::insert_or_replace_op(
                vec![TEST_LEAF.to_vec()],
                b"value".to_vec(),
                Element::new_item(b"hello".to_vec()),
            ),
            QualifiedGroveDbOp::insert_or_replace_op(
                vec![TEST_LEAF.to_vec()],
                b"refc".to_vec(),
                Element::new_reference(ReferencePathType::SiblingReference(b"value".to_vec())),
            ),
            QualifiedGroveDbOp::insert_or_replace_op(
                vec![TEST_LEAF.to_vec()],
                b"refb".to_vec(),
                Element::new_reference(ReferencePathType::SiblingReference(b"refc".to_vec())),
            ),
            QualifiedGroveDbOp::insert_or_replace_op(
                vec![TEST_LEAF.to_vec()],
                b"refa".to_vec(),
                Element::new_reference(ReferencePathType::SiblingReference(b"refb".to_vec())),
            ),
        ];

        db.apply_batch(ops, None, None, grove_version)
            .unwrap()
            .unwrap();

        assert!(db
            .verify_grovedb(None, true, false, grove_version)
            .unwrap()
            .is_empty());

        // Breaking things there:
        db.insert(
            &[TEST_LEAF],
            b"value",
            Element::new_item(b"not hello >:(".to_vec()),
            None,
            None,
            grove_version,
        )
        .unwrap()
        .unwrap();

        assert!(!db
            .verify_grovedb(None, true, false, grove_version)
            .unwrap()
            .is_empty());
    }
}