base / base/triedb

Handling of delete of non-existent leaf

Open
#189 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.