/__w/smoldot/smoldot/repo/lib/src/executor/trie_root_calculator/tests.rs

Source (jump to first uncovered line)
// Smoldot
// Copyright (C) 2023  Pierre Krieger
// SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#![cfg(test)]

use super::{trie_root_calculator, Config, InProgress, TrieEntryVersion};
use crate::{executor::storage_diff::TrieDiff, trie};
use core::{iter, ops};

use rand::distributions::{Distribution as _, Uniform};

#[test]
fn empty_trie_works() {
    let mut calculation = trie_root_calculator(Config {
        diff: TrieDiff::empty(),
        diff_trie_entries_version: TrieEntryVersion::V0,
        max_trie_recalculation_depth_hint: 8,
    });

    loop {
        match calculation {
            InProgress::Finished { trie_root_hash } => {
                assert_eq!(trie_root_hash, trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE);
                return;
            }
            InProgress::ClosestDescendant(req) => {
                calculation = req.inject(None::<iter::Empty<_>>);
            }
            InProgress::ClosestDescendantMerkleValue(req) => {
                calculation = req.resume_unknown();
            }
            InProgress::StorageValue(req) => {
                calculation = req.inject_value(None);
            }
            InProgress::TrieNodeInsertUpdateEvent(ev) => calculation = ev.resume(),
            InProgress::TrieNodeRemoveEvent(ev) => calculation = ev.resume(),
        }
    }
}

#[test]
fn one_inserted_node_in_diff() {
    let mut diff = TrieDiff::empty();
    diff.diff_insert(vec![0xaa, 0xaa], b"foo".to_vec(), ());

    let mut calculation = trie_root_calculator(Config {
        diff,
        diff_trie_entries_version: TrieEntryVersion::V0,
        max_trie_recalculation_depth_hint: 8,
    });

    loop {
        match calculation {
            InProgress::Finished { trie_root_hash } => {
                let expected = trie::trie_node::calculate_merkle_value(
                    trie::trie_node::Decoded {
                        children: [None::<&'static [u8]>; 16],
                        partial_key: trie::bytes_to_nibbles(vec![0xaa, 0xaa].into_iter()),
                        storage_value: trie::trie_node::StorageValue::Unhashed(b"foo"),
                    },
                    trie::HashFunction::Blake2,
                    true,
                )
                .unwrap();

                assert_eq!(trie_root_hash, expected.as_ref());
                return;
            }
            InProgress::ClosestDescendant(req) => {
                calculation = req.inject(None::<iter::Empty<_>>);
            }
            InProgress::ClosestDescendantMerkleValue(req) => {
                calculation = req.resume_unknown();
            }
            InProgress::StorageValue(req) => {
                calculation = req.inject_value(None);
            }
            InProgress::TrieNodeInsertUpdateEvent(ev) => calculation = ev.resume(),
            InProgress::TrieNodeRemoveEvent(ev) => calculation = ev.resume(),
        }
    }
}

#[test]
fn fuzzing() {
    fn uniform_sample(min: u8, max: u8) -> u8 {
        Uniform::new_inclusive(min, max).sample(&mut rand::thread_rng())
    }

    // We run the test multiple times because of randomness.
    for _ in 0..32768 {
        // Create a random trie.
        // Each node contains a `Some` with the storage value or `None` for branch nodes, plus its
        // Merkle value as `Some` if already calculated.
        let mut trie_before_diff = trie::trie_structure::TrieStructure::<(
            Option<(Vec<u8>, TrieEntryVersion)>,
            Option<trie::trie_node::MerkleValueOutput>,
        )>::new();

        let mut list = vec![Vec::new()];
        for elem in list.clone().into_iter() {
            for _ in 0..uniform_sample(0, 4) {
                let mut elem = elem.clone();
                for _ in 0..uniform_sample(0, 3) {
                    elem.push(uniform_sample(0, 255));
                }
                list.push(elem);
            }
        }
        for elem98.4k in list {
            let mut storage_value = Vec::new();
            for _ in 0..uniform_sample(0, 24) {
                storage_value.push(uniform_sample(0, 255));
            }

            let trie_entry_version = if rand::random::<bool>() {
                TrieEntryVersion::V1
            } else {
                TrieEntryVersion::V0
            };

            match trie_before_diff.node(trie::bytes_to_nibbles(elem.iter().copied())) {
                trie::trie_structure::Entry::Vacant(e) => {
                    e.insert_storage_value().insert(
                        (Some((storage_value, trie_entry_version)), None),
                        (None, None),
                    );
                }
                trie::trie_structure::Entry::Occupied(
                    trie::trie_structure::NodeAccess::Branch(mut e),
                ) => {
                    *e.user_data() = (Some((storage_value, trie_entry_version)), None);
                    e.insert_storage_value();
                }
                trie::trie_structure::Entry::Occupied(
                    trie::trie_structure::NodeAccess::Storage(_),
                ) => {}
            }
        }

        // Clone the trie and apply modifications to it. These modifications are also registered
        // in a diff.
        let mut trie_after_diff = trie_before_diff.clone();
        let mut diff = TrieDiff::empty();
        let diff_trie_entries_version = if rand::random::<bool>() {
            TrieEntryVersion::V1
        } else {
            TrieEntryVersion::V0
        };

        for _ in 0..5 {
            let mut list = vec![Vec::new()];
            for elem in list.clone().into_iter() {
                for _ in 0..uniform_sample(0, 4) {
                    let mut elem = elem.clone();
                    for _ in 0..uniform_sample(0, 3) {
                        elem.push(uniform_sample(0, 255));
                    }
                    list.push(elem);
                }
            }
            for elem490k in list {
                let mut storage_value = Vec::new();
                for _ in 0..uniform_sample(0, 24) {
                    storage_value.push(uniform_sample(0, 255));
                }

                match trie_after_diff.node(trie::bytes_to_nibbles(elem.iter().copied())) {
                    trie::trie_structure::Entry::Occupied(
                        trie::trie_structure::NodeAccess::Storage(mut e),
                    ) => {
                        if rand::random::<bool>() {
                            // Update storage value.
                            *e.user_data() = (
                                Some((storage_value.clone(), diff_trie_entries_version)),
                                None,
                            );
                            diff.diff_insert(elem, storage_value, ());
                        } else {
                            // Erase node.
                            e.user_data().0 = None;
                            e.remove();
                            diff.diff_insert_erase(elem, ());
                        }
                    }
                    trie::trie_structure::Entry::Occupied(
                        trie::trie_structure::NodeAccess::Branch(mut e),
                    ) => {
                        *e.user_data() = (
                            Some((storage_value.clone(), diff_trie_entries_version)),
                            None,
                        );
                        e.insert_storage_value();
                        diff.diff_insert(elem, storage_value, ());
                    }
                    trie::trie_structure::Entry::Vacant(e) => {
                        e.insert_storage_value().insert(
                            (
                                Some((storage_value.clone(), diff_trie_entries_version)),
                                None,
                            ),
                            (None, None),
                        );
                        diff.diff_insert(elem, storage_value, ());
                    }
                }
            }
        }

        // Calculate the Merkle values of the nodes of `trie_before_diff` and `trie_after_diff`.
        for trie in [&mut trie_before_diff, &mut trie_after_diff32.7k] {
            for node_index in trie.iter_ordered().collect::<Vec<_>>().into_iter().rev()65.5k {
                let mut node_access = trie.node_by_index(node_index).unwrap();

                let children = core::array::from_fn::<_, 16, _>(|n| {
                    node_access
                        .child(trie::Nibble::try_from(u8::try_from(n).unwrap()).unwrap())
                        .map(|mut child| child.user_data().1.as_ref().unwrap().clone()402k)
                });

                let is_root_node = node_access.is_root_node();
                let partial_key = node_access.partial_key().collect::<Vec<_>>().into_iter();

                // We have to hash the storage value ahead of time if necessary due to borrow
                // checking difficulties.
                let storage_value_hashed = match node_access.user_data().0.as_ref() {
                    Some((v, TrieEntryVersion::V1)) => {
                        if v.len() >= 33 {
                            Some(blake2_rfc::blake2b::blake2b(32, &[], v))
                        } else {
                            None
                        }
                    }
                    _ => None,
                };
                let storage_value = match (
                    node_access.user_data().0.as_ref(),
                    storage_value_hashed.as_ref(),
                ) {
                    (_, Some(storage_value_hashed)) => trie::trie_node::StorageValue::Hashed(
                        <&[u8; 32]>::try_from(storage_value_hashed.as_bytes()).unwrap(),
                    ),
                    (Some((v, _)), None) => trie::trie_node::StorageValue::Unhashed(&v[..]),
                    (None, _) => trie::trie_node::StorageValue::None,
                };

                let merkle_value = trie::trie_node::calculate_merkle_value(
                    trie::trie_node::Decoded {
                        children,
                        partial_key,
                        storage_value,
                    },
                    trie::HashFunction::Blake2,
                    is_root_node,
                )
                .unwrap();

                node_access.into_user_data().1 = Some(merkle_value);
            }
        }

        // Build alternative linear versions of the two tries.
        let mut trie_map = trie_before_diff
            .iter_ordered()
            .collect::<Vec<_>>()
            .into_iter()
            .map(|n| {
                (
                    trie_before_diff
                        .node_full_key_by_index(n)
                        .unwrap()
                        .collect::<Vec<_>>(),
                    trie_before_diff[n].1.clone().unwrap().as_ref().to_vec(),
                )
            })
            .collect::<hashbrown::HashMap<_, _, fnv::FnvBuildHasher>>();
        let trie_after_diff_map = trie_after_diff
            .iter_ordered()
            .collect::<Vec<_>>()
            .into_iter()
            .map(|n| {
                (
                    trie_after_diff
                        .node_full_key_by_index(n)
                        .unwrap()
                        .collect::<Vec<_>>(),
                    trie_after_diff[n].1.clone().unwrap().as_ref().to_vec(),
                )
            })
            .collect::<hashbrown::HashMap<_, _, fnv::FnvBuildHasher>>();

        // Use the trie_root_calculator to calculate the root of `trie_after_diff`.
        let obtained_hash = {
            let mut calculator = trie_root_calculator(Config {
                diff: diff.clone(),
                diff_trie_entries_version,
                max_trie_recalculation_depth_hint: 8,
            });

            loop {
                match calculator {
                    InProgress::Finished { trie_root_hash } => break trie_root_hash,
                    InProgress::ClosestDescendant(req) => {
                        let mut next_node = trie_before_diff
                            .range_iter(
                                ops::Bound::Included(req.key_as_vec().into_iter()),
                                ops::Bound::Unbounded::<iter::Empty<trie::Nibble>>,
                            )
                            .next();
                        // Set `next_node` to `None` if it isn't a descendant of the demanded key.
                        if next_node.map_or(false, |n| {
                            !trie_before_diff
                                .node_full_key_by_index(n)
                                .unwrap()
                                .collect::<Vec<_>>()
                                .starts_with(&req.key_as_vec())
                        }) {
                            next_node = None;
                        }
                        calculator = req.inject(
                            next_node.map(|n| trie_before_diff.node_full_key_by_index(n).unwrap()83.5k),
                        );
                    }
                    InProgress::ClosestDescendantMerkleValue(req) => {
                        if rand::random::<bool>() {
                            let mut next_node = trie_before_diff
                                .range_iter(
                                    ops::Bound::Included(req.key_as_vec().into_iter()),
                                    ops::Bound::Unbounded::<iter::Empty<trie::Nibble>>,
                                )
                                .next();
                            // Set `next_node` to `None` if it isn't a descendant of the demanded key.
                            if next_node.map_or(false, |n| {
                                !trie_before_diff
                                    .node_full_key_by_index(n)
                                    .unwrap()
                                    .collect::<Vec<_>>()
                                    .starts_with(&req.key_as_vec())
                            }) {
                                next_node = None;
                            }

                            if let Some(next_node16.2k) = next_node {
                                calculator = req.inject_merkle_value(
                                    trie_before_diff
                                        .node_by_index(next_node)
                                        .unwrap()
                                        .into_user_data()
                                        .1
                                        .as_ref()
                                        .unwrap()
                                        .clone()
                                        .as_ref(),
                                );
                            } else {
                                calculator = req.resume_unknown();
                            }
                        } else {
                            calculator = req.resume_unknown()
                        }
                    }
                    InProgress::StorageValue(req) => {
                        let value = if let trie::trie_structure::Entry::Occupied(
                            trie::trie_structure::NodeAccess::Storage(e),
                        ) = trie_before_diff.node(req.key_as_vec().into_iter())
                        {
                            Some(e.into_user_data().0.as_ref().unwrap().clone())
                        } else {
                            None
                        };

                        calculator =
                            req.inject_value(value.as_ref().map(|(val, vers)| (&val[..], *vers)65.2k));
                    }
                    InProgress::TrieNodeInsertUpdateEvent(ev) => {
                        trie_map.insert(
                            ev.key()
                                .flat_map(crate::util::as_ref_iter)
                                .collect::<Vec<_>>(),
                            ev.merkle_value().to_vec(),
                        );
                        calculator = ev.resume();
                    }
                    InProgress::TrieNodeRemoveEvent(ev) => {
                        let was_in = trie_map.remove(
                            &ev.key()
                                .flat_map(crate::util::as_ref_iter)
                                .collect::<Vec<_>>(),
                        );
                        assert!(was_in.is_some());
                        calculator = ev.resume();
                    }
                }
            }
        };

        // Actual test is here.
        let expected_hash = trie_after_diff
            .root_user_data()
            .map(|n| *<&[u8; 32]>::try_from(n.1.as_ref().unwrap().as_ref()).unwrap()32.7k)
            .unwrap_or(trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE);
        if obtained_hash != expected_hash {
            panic!(
                "\nexpected = {:?}\ncalculated = {:?}\ntrie_before = {:?}\ndiff = {:?}",
                expected_hash, obtained_hash, trie_before_diff, diff
            );
        }
        if trie_map != trie_after_diff_map {
            panic!(
                "\nexpected = {:?}\ncalculated = {:?}\ntrie_before = {:?}\ndiff = {:?}",
                trie_after_diff_map, trie_map, trie_before_diff, diff
            );
        }
    }
}

Coverage Report

Created: 2024-05-16 12:16

Line	Count	Source (jump to first uncovered line)
1		// Smoldot
2		// Copyright (C) 2023 Pierre Krieger
3		// SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0
4
5		// This program is free software: you can redistribute it and/or modify
6		// it under the terms of the GNU General Public License as published by
7		// the Free Software Foundation, either version 3 of the License, or
8		// (at your option) any later version.
9
10		// This program is distributed in the hope that it will be useful,
11		// but WITHOUT ANY WARRANTY; without even the implied warranty of
12		// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13		// GNU General Public License for more details.
14
15		// You should have received a copy of the GNU General Public License
16		// along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18		#![cfg(test)]
19
20		use super::{trie_root_calculator, Config, InProgress, TrieEntryVersion};
21		use crate::{executor::storage_diff::TrieDiff, trie};
22		use core::{iter, ops};
23
24		use rand::distributions::{Distribution as _, Uniform};
25
26		#[test]
27	1	fn empty_trie_works() {
28	1	let mut calculation = trie_root_calculator(Config {
29	1	diff: TrieDiff::empty(),
30	1	diff_trie_entries_version: TrieEntryVersion::V0,
31	1	max_trie_recalculation_depth_hint: 8,
32	1	});
33
34	3	loop {
35	3	match calculation {
36	1	InProgress::Finished { trie_root_hash } => {
37	1	assert_eq!(trie_root_hash, trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE);
38	1	return;
39		}
40	1	InProgress::ClosestDescendant(req) => {
41	1	calculation = req.inject(None::<iter::Empty<_>>);
42	1	}
43	1	InProgress::ClosestDescendantMerkleValue(req) => {
44	1	calculation = req.resume_unknown();
45	1	}
46	0	InProgress::StorageValue(req) => {
47	0	calculation = req.inject_value(None);
48	0	}
49	0	InProgress::TrieNodeInsertUpdateEvent(ev) => calculation = ev.resume(),
50	0	InProgress::TrieNodeRemoveEvent(ev) => calculation = ev.resume(),
51		}
52		}
53	1	}
54
55		#[test]
56	1	fn one_inserted_node_in_diff() {
57	1	let mut diff = TrieDiff::empty();
58	1	diff.diff_insert(vec![0xaa, 0xaa], b"foo".to_vec(), ());
59	1
60	1	let mut calculation = trie_root_calculator(Config {
61	1	diff,
62	1	diff_trie_entries_version: TrieEntryVersion::V0,
63	1	max_trie_recalculation_depth_hint: 8,
64	1	});
65
66	20	loop {
67	20	match calculation {
68	1	InProgress::Finished { trie_root_hash } => {
69	1	let expected = trie::trie_node::calculate_merkle_value(
70	1	trie::trie_node::Decoded {
71	1	children: [None::<&'static [u8]>; 16],
72	1	partial_key: trie::bytes_to_nibbles(vec![0xaa, 0xaa].into_iter()),
73	1	storage_value: trie::trie_node::StorageValue::Unhashed(b"foo"),
74	1	},
75	1	trie::HashFunction::Blake2,
76	1	true,
77	1	)
78	1	.unwrap();
79	1
80	1	assert_eq!(trie_root_hash, expected.as_ref());
81	1	return;
82		}
83	17	InProgress::ClosestDescendant(req) => {
84	17	calculation = req.inject(None::<iter::Empty<_>>);
85	17	}
86	0	InProgress::ClosestDescendantMerkleValue(req) => {
87	0	calculation = req.resume_unknown();
88	0	}
89	1	InProgress::StorageValue(req) => {
90	1	calculation = req.inject_value(None);
91	1	}
92	1	InProgress::TrieNodeInsertUpdateEvent(ev) => calculation = ev.resume(),
93	0	InProgress::TrieNodeRemoveEvent(ev) => calculation = ev.resume(),
94		}
95		}
96	1	}
97
98		#[test]
99	1	fn fuzzing() {
100	8.84M	fn uniform_sample(min: u8, max: u8) -> u8 {
101	8.84M	Uniform::new_inclusive(min, max).sample(&mut rand::thread_rng())
102	8.84M	}
103
104		// We run the test multiple times because of randomness.
105	32.7k	for _ in 0..32768 {
106		// Create a random trie.
107		// Each node contains a `Some` with the storage value or `None` for branch nodes, plus its
108		// Merkle value as `Some` if already calculated.
109	32.7k	let mut trie_before_diff = trie::trie_structure::TrieStructure::<(
110	32.7k	Option<(Vec<u8>, TrieEntryVersion)>,
111	32.7k	Option<trie::trie_node::MerkleValueOutput>,
112	32.7k	)>::new();
113	32.7k
114	32.7k	let mut list = vec![Vec::new()];
115	32.7k	for elem in list.clone().into_iter() {
116	32.7k	for _ in 0..uniform_sample(0, 4) {
117	65.7k	let mut elem = elem.clone();
118	98.9k	for _ in 0..uniform_sample(0, 3) {
119	98.9k	elem.push(uniform_sample(0, 255));
120	98.9k	}
121	65.7k	list.push(elem);
122		}
123		}
124	131k	for elem98.4k in list {
125	98.4k	let mut storage_value = Vec::new();
126	1.18M	for _ in 0..uniform_sample(0, 24) {
127	1.18M	storage_value.push(uniform_sample(0, 255));
128	1.18M	}
129
130	98.4k	let trie_entry_version = if rand::random::<bool>() {
131	49.4k	TrieEntryVersion::V1
132		} else {
133	49.0k	TrieEntryVersion::V0
134		};
135
136	98.4k	match trie_before_diff.node(trie::bytes_to_nibbles(elem.iter().copied())) {
137	82.1k	trie::trie_structure::Entry::Vacant(e) => {
138	82.1k	e.insert_storage_value().insert(
139	82.1k	(Some((storage_value, trie_entry_version)), None),
140	82.1k	(None, None),
141	82.1k	);
142	82.1k	}
143		trie::trie_structure::Entry::Occupied(
144	0	trie::trie_structure::NodeAccess::Branch(mut e),
145	0	) => {
146	0	*e.user_data() = (Some((storage_value, trie_entry_version)), None);
147	0	e.insert_storage_value();
148	0	}
149		trie::trie_structure::Entry::Occupied(
150		trie::trie_structure::NodeAccess::Storage(_),
151	16.3k	) => {}
152		}
153		}
154
155		// Clone the trie and apply modifications to it. These modifications are also registered
156		// in a diff.
157	32.7k	let mut trie_after_diff = trie_before_diff.clone();
158	32.7k	let mut diff = TrieDiff::empty();
159	32.7k	let diff_trie_entries_version = if rand::random::<bool>() {
160	16.2k	TrieEntryVersion::V1
161		} else {
162	16.5k	TrieEntryVersion::V0
163		};
164
165	196k	for _ in 0..5 {
166	163k	let mut list = vec![Vec::new()];
167	163k	for elem in list.clone().into_iter() {
168	163k	for _ in 0..uniform_sample(0, 4) {
169	326k	let mut elem = elem.clone();
170	490k	for _ in 0..uniform_sample(0, 3) {
171	490k	elem.push(uniform_sample(0, 255));
172	490k	}
173	326k	list.push(elem);
174		}
175		}
176	654k	for elem490k in list {
177	490k	let mut storage_value = Vec::new();
178	5.89M	for _ in 0..uniform_sample(0, 24) {
179	5.89M	storage_value.push(uniform_sample(0, 255));
180	5.89M	}
181
182	490k	match trie_after_diff.node(trie::bytes_to_nibbles(elem.iter().copied())) {
183		trie::trie_structure::Entry::Occupied(
184	171k	trie::trie_structure::NodeAccess::Storage(mut e),
185	171k	) => {
186	171k	if rand::random::<bool>() {
187	85.3k	// Update storage value.
188	85.3k	*e.user_data() = (
189	85.3k	Some((storage_value.clone(), diff_trie_entries_version)),
190	85.3k	None,
191	85.3k	);
192	85.3k	diff.diff_insert(elem, storage_value, ());
193	85.8k	} else {
194	85.8k	// Erase node.
195	85.8k	e.user_data().0 = None;
196	85.8k	e.remove();
197	85.8k	diff.diff_insert_erase(elem, ());
198	85.8k	}
199		}
200		trie::trie_structure::Entry::Occupied(
201	66.5k	trie::trie_structure::NodeAccess::Branch(mut e),
202	66.5k	) => {
203	66.5k	*e.user_data() = (
204	66.5k	Some((storage_value.clone(), diff_trie_entries_version)),
205	66.5k	None,
206	66.5k	);
207	66.5k	e.insert_storage_value();
208	66.5k	diff.diff_insert(elem, storage_value, ());
209	66.5k	}
210	252k	trie::trie_structure::Entry::Vacant(e) => {
211	252k	e.insert_storage_value().insert(
212	252k	(
213	252k	Some((storage_value.clone(), diff_trie_entries_version)),
214	252k	None,
215	252k	),
216	252k	(None, None),
217	252k	);
218	252k	diff.diff_insert(elem, storage_value, ());
219	252k	}
220		}
221		}
222		}
223
224		// Calculate the Merkle values of the nodes of `trie_before_diff` and `trie_after_diff`.
225	65.5k	for trie in [ &mut trie_before_diff, &mut trie_after_diff32.7k ] {
226	467k	for node_index in trie.iter_ordered().collect::<Vec<_>>().into_iter().rev()65.5k {
227	467k	let mut node_access = trie.node_by_index(node_index).unwrap();
228	467k
229	7.48M	let children = core::array::from_fn::<_, 16, _>(\|n\| {
230	7.48M	node_access
231	7.48M	.child(trie::Nibble::try_from(u8::try_from(n).unwrap()).unwrap())
232	7.48M	.map(\|mut child\| child.user_data().1.as_ref().unwrap().clone()402k )
233	7.48M	});
234	467k
235	467k	let is_root_node = node_access.is_root_node();
236	467k	let partial_key = node_access.partial_key().collect::<Vec<_>>().into_iter();
237
238		// We have to hash the storage value ahead of time if necessary due to borrow
239		// checking difficulties.
240	467k	let storage_value_hashed = match node_access.user_data().0.as_ref() {
241	198k	Some((v, TrieEntryVersion::V1)) => {
242	198k	if v.len() >= 33 {
243	0	Some(blake2_rfc::blake2b::blake2b(32, &[], v))
244		} else {
245	198k	None
246		}
247		}
248	269k	_ => None,
249		};
250	467k	let storage_value = match (
251	467k	node_access.user_data().0.as_ref(),
252	467k	storage_value_hashed.as_ref(),
253		) {
254	0	(_, Some(storage_value_hashed)) => trie::trie_node::StorageValue::Hashed(
255	0	<&[u8; 32]>::try_from(storage_value_hashed.as_bytes()).unwrap(),
256	0	),
257	397k	(Some((v, _)), None) => trie::trie_node::StorageValue::Unhashed(&v[..]),
258	69.7k	(None, _) => trie::trie_node::StorageValue::None,
259		};
260
261	467k	let merkle_value = trie::trie_node::calculate_merkle_value(
262	467k	trie::trie_node::Decoded {
263	467k	children,
264	467k	partial_key,
265	467k	storage_value,
266	467k	},
267	467k	trie::HashFunction::Blake2,
268	467k	is_root_node,
269	467k	)
270	467k	.unwrap();
271	467k
272	467k	node_access.into_user_data().1 = Some(merkle_value);
273		}
274		}
275
276		// Build alternative linear versions of the two tries.
277	32.7k	let mut trie_map = trie_before_diff
278	32.7k	.iter_ordered()
279	32.7k	.collect::<Vec<_>>()
280	32.7k	.into_iter()
281	84.2k	.map(\|n\| {
282	84.2k	(
283	84.2k	trie_before_diff
284	84.2k	.node_full_key_by_index(n)
285	84.2k	.unwrap()
286	84.2k	.collect::<Vec<_>>(),
287	84.2k	trie_before_diff[n].1.clone().unwrap().as_ref().to_vec(),
288	84.2k	)
289	84.2k	})
290	32.7k	.collect::<hashbrown::HashMap<_, _, fnv::FnvBuildHasher>>();
291	32.7k	let trie_after_diff_map = trie_after_diff
292	32.7k	.iter_ordered()
293	32.7k	.collect::<Vec<_>>()
294	32.7k	.into_iter()
295	383k	.map(\|n\| {
296	383k	(
297	383k	trie_after_diff
298	383k	.node_full_key_by_index(n)
299	383k	.unwrap()
300	383k	.collect::<Vec<_>>(),
301	383k	trie_after_diff[n].1.clone().unwrap().as_ref().to_vec(),
302	383k	)
303	383k	})
304	32.7k	.collect::<hashbrown::HashMap<_, _, fnv::FnvBuildHasher>>();
305
306		// Use the trie_root_calculator to calculate the root of `trie_after_diff`.
307	32.7k	let obtained_hash = {
308	32.7k	let mut calculator = trie_root_calculator(Config {
309	32.7k	diff: diff.clone(),
310	32.7k	diff_trie_entries_version,
311	32.7k	max_trie_recalculation_depth_hint: 8,
312	32.7k	});
313
314	7.50M	loop {
315	7.50M	match calculator {
316	32.7k	InProgress::Finished { trie_root_hash } => break trie_root_hash,
317	5.87M	InProgress::ClosestDescendant(req) => {
318	5.87M	let mut next_node = trie_before_diff
319	5.87M	.range_iter(
320	5.87M	ops::Bound::Included(req.key_as_vec().into_iter()),
321	5.87M	ops::Bound::Unbounded::<iter::Empty<trie::Nibble>>,
322	5.87M	)
323	5.87M	.next();
324	5.87M	// Set `next_node` to `None` if it isn't a descendant of the demanded key.
325	5.87M	if next_node.map_or(false, \|n\| {
326	2.87M	!trie_before_diff
327	2.87M	.node_full_key_by_index(n)
328	2.87M	.unwrap()
329	2.87M	.collect::<Vec<_>>()
330	2.87M	.starts_with(&req.key_as_vec())
331	5.87M	}) {
332	2.79M	next_node = None;
333	3.07M	}
334	5.87M	calculator = req.inject(
335	5.87M	next_node.map(\|n\| trie_before_diff.node_full_key_by_index(n).unwrap()83.5k ),
336	5.87M	);
337		}
338	869k	InProgress::ClosestDescendantMerkleValue(req) => {
339	869k	if rand::random::<bool>() {
340	434k	let mut next_node = trie_before_diff
341	434k	.range_iter(
342	434k	ops::Bound::Included(req.key_as_vec().into_iter()),
343	434k	ops::Bound::Unbounded::<iter::Empty<trie::Nibble>>,
344	434k	)
345	434k	.next();
346	434k	// Set `next_node` to `None` if it isn't a descendant of the demanded key.
347	434k	if next_node.map_or(false, \|n\| {
348	219k	!trie_before_diff
349	219k	.node_full_key_by_index(n)
350	219k	.unwrap()
351	219k	.collect::<Vec<_>>()
352	219k	.starts_with(&req.key_as_vec())
353	434k	}) {
354	203k	next_node = None;
355	231k	}
356
357	434k	if let Some( next_node16.2k ) = next_node {
358	16.2k	calculator = req.inject_merkle_value(
359	16.2k	trie_before_diff
360	16.2k	.node_by_index(next_node)
361	16.2k	.unwrap()
362	16.2k	.into_user_data()
363	16.2k	.1
364	16.2k	.as_ref()
365	16.2k	.unwrap()
366	16.2k	.clone()
367	16.2k	.as_ref(),
368	16.2k	);
369	418k	} else {
370	418k	calculator = req.resume_unknown();
371	418k	}
372		} else {
373	435k	calculator = req.resume_unknown()
374		}
375		}
376	366k	InProgress::StorageValue(req) => {
377	366k	let value = if let trie::trie_structure::Entry::Occupied(
378	65.2k	trie::trie_structure::NodeAccess::Storage(e),
379	366k	) = trie_before_diff.node(req.key_as_vec().into_iter())
380		{
381	65.2k	Some(e.into_user_data().0.as_ref().unwrap().clone())
382		} else {
383	300k	None
384		};
385
386	366k	calculator =
387	366k	req.inject_value(value.as_ref().map(\|(val, vers)\| (&val[..], *vers)65.2k ));
388		}
389	365k	InProgress::TrieNodeInsertUpdateEvent(ev) => {
390	365k	trie_map.insert(
391	365k	ev.key()
392	365k	.flat_map(crate::util::as_ref_iter)
393	365k	.collect::<Vec<_>>(),
394	365k	ev.merkle_value().to_vec(),
395	365k	);
396	365k	calculator = ev.resume();
397	365k	}
398	105	InProgress::TrieNodeRemoveEvent(ev) => {
399	105	let was_in = trie_map.remove(
400	105	&ev.key()
401	105	.flat_map(crate::util::as_ref_iter)
402	105	.collect::<Vec<_>>(),
403	105	);
404	105	assert!(was_in.is_some());
405	105	calculator = ev.resume();
406		}
407		}
408		}
409		};
410
411		// Actual test is here.
412	32.7k	let expected_hash = trie_after_diff
413	32.7k	.root_user_data()
414	32.7k	.map(\|n\| *<&[u8; 32]>::try_from(n.1.as_ref().unwrap().as_ref()).unwrap()32.7k )
415	32.7k	.unwrap_or(trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE);
416	32.7k	if obtained_hash != expected_hash {
417	0	panic!(
418	0	"\nexpected = {:?}\ncalculated = {:?}\ntrie_before = {:?}\ndiff = {:?}",
419	0	expected_hash, obtained_hash, trie_before_diff, diff
420	0	);
421	32.7k	}
422	32.7k	if trie_map != trie_after_diff_map {
423	0	panic!(
424	0	"\nexpected = {:?}\ncalculated = {:?}\ntrie_before = {:?}\ndiff = {:?}",
425	0	trie_after_diff_map, trie_map, trie_before_diff, diff
426	0	);
427	32.7k	}
428		}
429	1	}