Handling of delete of non-existent leaf
- Dominant language
- Rust
- Stars
- 109
- Forks
- 37
- PR merge metrics
- No merged PRs in 30d
Description
Consider the case where we issue a `set_values` with a delete of a leaf that is not in the triedb - is this a valid operation?
If it is a valid operation, it seems like it can fail to update branch pointers, like so:
* we traverse the trie and hit a branch node that shares path with the delete, the only item in changes: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/handlers.rs#L109
* the next hop is a different page: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/handlers.rs#L168C30-L168C48
* set_values_in_page clones the page: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/write.rs#L88
* set_values_in_cloned_page loads the node (an account leaf for example) and decides they have no shared prefix (since the delete was for a node that doesn't exist) - notably, changes_left and changes_right are both empty: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/write.rs#L192
* recursion happens and returns NoChange: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/write.rs#L170
* NoChange bubbles up, but the page change that `set_values_in_page` caused with the clone+orphan is forgotten: https://github.com/base/triedb/blob/66e5e076e6e02f3030e1ea16343e0aca97b39248/src/storage/engine/handlers.rs#L176
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reading the linked paths in src/storage/engine/handlers.rs and src/storage/engine/write.rs, especially set_values_in_page and set_values_in_cloned_page. Trace the described delete of a missing leaf through the existing tests or add a focused case for set_values. Done means the issue's validity question is resolved and branch-pointer behavior is covered for the chosen semantics.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100