fix: correct request validation

[GG2002]

Please briefly answer these questions:

• what problem are you trying to solve? (or if there's no problem, what's the motivation for this change?)
  [Bug]: check_intervals will not validate correctly in certain nested txn scenarios #410
• what changes does this pull request make?
  Corrected the behavior of request validation. Please refer to this proposal for the general idea. The specific code behavior is slightly different from what is stated in the proposal, but the idea of finding out LCA is the same.
• are there any non-obvious implications of these changes? (does it break compatibility with previous versions, etc)
  No.

Let me explain what I do.

Firstly, we need to confirm that put and del/put on the same branch (success or failure) are prohibited from overlapping. Being on the same branch means that the LCA of put and del/put are the success or failure branch node, while not being on the same branch means that the LCA of put and del/put are the RequestTxn node. In fact, the LCA of put and del can only be on one of RequestTxn, success, or failure branch.

After understanding this, we can easily conclude that when the depth of LCA for two nodes % 2 == 0 means that these two nodes are on the same branch (this is also related to the code processing flow, because fn check_intervals initially receives the success or failure branch, not a RequestTxn. If it is the latter, then when LCA.depth % 2 == 1, it means that these two nodes are on the same branch).

The first step is fn build_interval_tree, which traverses the entire txn structure and represents each op with an LCA node (which records its parent and depth). It will establishe two data structures:

• dels contains all the LCA nodes of del op and their corresponding intervals
• puts contains all the LCA nodes of put op

Because the same interval may correspond to different LCA nodes, both data structures store vec<usize>. This step also checks whether different put overlap to return Err earlier. Note that even if all put do not overlap, HashMap<&[u8], vec<usize>> is still needed to store all put, because the second step is to iterate through all put to check if they intersect with del.

The second and final step is to directly iterate through puts and check whether all put intersect with the del in the dels. The detection rule is as described above.

Done.

[mergify]

@GG2002 Convert your pr to draft since CI failed

[codecov]

Codecov Report

Attention: Patch coverage is 91.11111% with 16 lines in your changes missing coverage. Please review.

Project coverage is 75.84%. Comparing base (e35b35a) to head (777bcf0).
Report is 191 commits behind head on master.

Files	Patch %	Lines
crates/xlineapi/src/request_validation.rs	87.95%	6 Missing and 4 partials ⚠️
crates/utils/src/lca_tree.rs	93.81%	5 Missing and 1 partial ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #942      +/-   ##
==========================================
+ Coverage   75.55%   75.84%   +0.28%     
==========================================
  Files         180      188       +8     
  Lines       26938    27990    +1052     
  Branches    26938    27990    +1052     
==========================================
+ Hits        20353    21228     +875     
- Misses       5366     5454      +88     
- Partials     1219     1308      +89     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[mergify]

@GG2002 Convert your pr to draft since CI failed

[mergify]

@GG2002 Your PR is in conflict and cannot be merged.