a54f4e198f
shardtree: Add test exposing `ShardTree::prune_excess_checkpoints` bug
2023-07-05 21:16:22 +00:00
7643b16261
Add TRACE-level logging to `shardtree` internals
2023-07-05 21:04:02 +00:00
8c927ce11e
Merge pull request #80 from zingolabs/clarify_position_is_leaf
...
Fix doc comments to clarify that positions are always leaves, not inner nodes
2023-07-05 14:02:54 -06:00
2d86458e1e
Merge pull request #81 from zcash/refactor
...
Refactor codebase into submodules
2023-07-05 14:02:39 -06:00
46592bf466
Move `accumulate_result_with` helper function into `prunable` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 19:24:57 +00:00
4152961f77
Move `testing` submodule into a separate file
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 19:23:21 +00:00
f2d2bd3719
Move `MemoryShardStore` into `memory` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 19:18:41 +00:00
e9c32bf3dd
Move `LocatedPrunableTree` and its helper types into `prunable` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 19:11:54 +00:00
0d531d9309
Move `LocatedTree` into `tree` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 19:04:40 +00:00
b0328a3637
Fix doc comments to clarify that positions are always leaves, not inner nodes
2023-07-05 15:58:44 -03:00
0f15a57cb5
Move `PrunableTree` and `RetentionFlags` into `prunable` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 18:57:06 +00:00
3b05192538
Move `Node` and `Tree` into `tree` submodule
...
Co-authored-by: Kris Nuttycombe <kris@nutty.land>
2023-07-05 18:50:37 +00:00
109f805fdf
Merge pull request #79 from zancas/tweak_docs
...
allowing level 0 nodes means that Addresses are used for non-internal…
2023-07-05 12:32:01 -06:00
313c072afb
Merge pull request #69 from nuttycom/cap_cache
...
Add support for tracking legacy frontiers and witnesses in `ShardTree` instances.
2023-07-03 11:27:57 -06:00
5c14ab8882
allowing level 0 nodes means that Addresses are used for non-internal nodes
2023-06-30 18:25:50 -06:00
082109deac
Add tests to verify frontier & witness insertion behavior for sub-shard-sized values.
2023-06-29 15:30:21 -06:00
701d3e6311
Apply suggestions from code review.
2023-06-29 15:26:56 -06:00
30c592a0b3
Add tests that verify `ShardTree` state post-truncation.
2023-06-29 14:52:57 -06:00
3c4a660c86
Add `shardtree::LocatedTree::take_root`
2023-06-22 19:18:57 -06:00
00eb47f391
Replace `put_root` with single-node insertion.
2023-06-22 14:46:30 -06:00
accb8d7d8d
Refactor to make shardtree tests reusable for checking ShardStore impls.
2023-06-22 08:25:42 -06:00
f5889dffa5
Address comments from code review.
2023-06-16 17:12:55 -06:00
6d6f3fd4e3
Merge pull request #78 from nathan-at-least/api-docs-for-location-and-node-relations
...
`incrementalmerkletree` API docs for location and node relations.
2023-06-16 16:31:25 -06:00
d9fbd00e91
Wrap long lines & fix emmer/ommer typo.
2023-06-16 16:30:42 -06:00
964e71b79d
Clarify the ommer-path context for `ommers`.
2023-06-16 16:30:42 -06:00
cb8ef79648
Generalize remaining tests to arbitrary checkpoint id types.
2023-06-16 13:53:24 -06:00
33ad80814f
Generalize `check_remove_mark` and `check_checkpoint_rewind`
2023-06-16 12:59:55 -06:00
405f1100da
Generalize `check_witnesses`
2023-06-16 12:59:55 -06:00
527f561816
Generalize `check_append` and `check_root_hashes`.
2023-06-16 12:59:55 -06:00
614079271a
Improve error reporting from the `Tree` impl for `ShardTree`
2023-06-16 12:59:55 -06:00
456102b2ad
Make the `Tree` impl for `ShardTree` available under `test-dependencies`
2023-06-15 19:05:45 -06:00
6dd0c175b0
Bugfix: shard roots should be at level SHARD_HEIGHT, not SHARD_HEIGHT - 1
...
The intent of SHARD_HEIGHT is that each subtree should contain
2^SHARD_HEIGHT nodes. The `ShardTree::subtree_level` function was
incorrectly computing the level of the root address, and consequently
the resulting subtrees were too small.
2023-06-15 09:43:38 -06:00
dbc46b1157
Add shardtree::Checkpoint::from_parts
2023-06-15 09:43:38 -06:00
7617a5574f
Add ability to truncate `ShardTree` to a checkpoint by identifier.
2023-06-06 16:50:27 -06:00
e2d59d42e1
Do comment line-wrapping at ~100 columns.
2023-06-06 16:50:27 -06:00
c0b8c4d783
Fix all `cargo doc` warnings about dangling refs.
2023-06-06 16:50:27 -06:00
6e5c50d149
Add shardtree::testing::arb_prunable_tree
2023-06-06 16:50:27 -06:00
4a871a5840
Add LocatedTree::from_parts
2023-06-06 16:50:27 -06:00
a397ba9d46
There is no longer a distinction between `ShardTree::empty` and `ShardTree::load`.
2023-06-06 16:50:27 -06:00
1721d46571
Wrap ShardTree errors explicitly, instead of relying on `From` impls.
...
This introduces a `ShardTreeError` type that is used to wrap errors
that arise from the undelying `ShardStore` when used in `ShardTree`
methods. The previous approach that relied on `From<QueryError> +
From<InsertionError>` bounds resulted in a situation where the shard
store error was forced to encompass the bounds of these types, even
though the methods on the `ShardStore` itself could never generate them.
This resulted in a number of awkward problems for error conversion.
2023-06-06 16:50:27 -06:00
290b66d5c8
Add caching of the "cap" to root & witness computation.
2023-06-06 16:50:27 -06:00
f8c13d17de
Add insertion of legacy incremental witness data to `ShardTree`
2023-06-06 16:50:27 -06:00
f5b06c8e8b
Add construction of `LocatedPrunableTree` from `IncrementalWitness`
2023-06-06 16:50:27 -06:00
d350d43fd7
Add "shardtree cap" support to `ShardStore` and `ShardTree`.
...
The cap is a truncated tree that can be used to cache precomputed
subtree roots at tree heights greater than `SHARD_HEIGHT`. Only roots
whose hashes cannot be altered by rewinds or by the addition of data to
the tree may be persisted to the cap.
2023-06-06 16:50:27 -06:00
19c514b8cf
Add insertion of frontier nodes into a `ShardTree`
2023-06-06 16:50:27 -06:00
aab7c969b3
Add a mechanism to insert the nodes from a `Frontier` into a `LocatedPrunableTree`
2023-06-06 16:50:27 -06:00
75cd519646
Merge pull request #77 from zcash/release-incrementalmerkletree-v0.4.0
...
Release incrementalmerkletree v0.4.0 & bridgetree v0.3.0
2023-06-06 10:05:52 -06:00
e8dcfe5b4c
Update changelog for bridgetree-v0.3.0 release
2023-06-06 09:20:39 -06:00
4c79a7d065
Release incrementalmerkletree-v0.4.0 and bridgetree-v0.3.0
2023-06-05 19:39:49 -06:00
66cf091b97
Merge branch 'release-bridgetree-v0.2.1' into HEAD
2023-06-05 19:39:43 -06:00
Jack Grigg
Kris Nuttycombe
Hazel OHearn
zancas
Nate Wilcox