1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Copyright 2024 the Xilem Authors
// SPDX-License-Identifier: Apache-2.0
// After you edit the crate's doc comment, run this command, then check README.md for any missing links
// cargo rdme --workspace-project=tree_arena
//! This crate contains two implementations of a tree for use in [Masonry], one safe and the other unsafe. The safe tree is known to work, and serves as the baseline implementation and is used by default.
//! The unsafe tree leverages a hashmap as an arena and is designed for higher performance: it leverages unsafe code to achieve this. The unsafe tree is not yet fully tested, and is not used by default.
//!
//! The safe tree is the priority. This means:
//!
//! * The safe version may have features / APIs that the unsafe version doesn't yet have.
//!
//! * If both versions are at feature parity, [Masonry] can switch on the unsafe version for best performance.
//!
//! * Otherwise, [Masonry] uses the safe version.
//!
//! # Architecture
//!
//! ## Safe Tree
//!
//! The safe tree contains a root `TreeArena` which owns the root nodes as `Vec<TreeNode<T>>`, and a`parents_map` tracking the parent of every node.
//! Each `TreeNode` subsequently owns its own children as `Vec<TreeNode<T>>`. This model of ownership is thus checked by the rust compiler,
//! but has the downside of requiring passing through every ancestor node to access the descendant -
//! this requires an O(depth) determination of whether the node is a descendant, followed by O(children) time at each level to traverse the path to the child.
//!
//! ## Unsafe Tree
//!
//! The unsafe tree arena contains a `DataMap` which **owns** all nodes. The `DataMap` contains:
//!
//! * A `HashMap` associating `NodeId` with `Box<UnsafeCell<TreeNode<T>>>`, owning the node data, (boxed to prevent movement of the node when the `HashMap` is resized and `UnsafeCell` to express the interior mutability)
//!
//! * A `HashMap` associating `NodeId` with `Option<NodeId>`, containing the parent information for the nodes
//!
//! * `Box<UnsafeCell<Vec<NodeId>>>` containing the roots of the tree
//!
//! It is possible to get shared (immutable) access or exclusive (mutable) access to the tree. These return `ArenaRef<'arena, T>` or `ArenaMut<'arena, T>` respectively.
//! We do this by leveraging a hash map to store the nodes: from this we can obtain either shared or exclusive access to nodes.
//! To ensure that only one item is allowed to create new exclusive access to nodes, this action requires mutable access to the arena as a whole (and so is checked by the compiler) -
//! what the compiler cannot check is that the nodes accessed mutably are distinct from one another - this is done by only allowing access to descendants of the node being accessed mutably.
//! The aim of this is to reduce the time needed to access node, as given a node, we only need to determine whether it is a descendant of the node being accessed mutably,
//! and do not need to iterate over the children and to flatten the overall tree graph into a hash map.
//!
//! ### Shared References
//!
//! `ArenaRef<'arena, T>` contains the identity of the parent node, a reference to the node data, and `ArenaRefChildren<'arena, T>`.
//! The `ArenaRefChildren<'arena, T>` contains the ids of the children of the node, the id of the node, and a reference to the arena. From this `ArenaRefChildren<'arena, T>` it is possible to get shared access to children of the node.
//!
//! ### Exclusive References
//!
//! `ArenaMut<'arena, T>` contains the identity of the parent node, a mutable reference to the node data, and `ArenaMutChildren<'arena, T>`.
//! The `ArenaMutChildren<'arena, T>` contains the ids of the children of the node, the id of the node, and a mutable reference to the arena.
//! From this `ArenaMutChildren<'arena, T>` it is possible to get exclusive access to children of the node.
//!
//! ### Safety
//!
//! From the `ArenaMutChildren<'arena, T>`, it is important that we can only access descendants of that node,
//! such that we can only ever have exclusive mutable access to the contents of a node, and never have multiple mutable references.
//! This invariant is not checked by the compiler and thus relies on the logic to determine whether a node is a descendant being correct.
//!
//! ## Complexity
//!
//! |Operation | Safe | Unsafe |
//! | --- | --- | --- |
//! |Find child | O(Children) | O(1) |
//! |Descendant | O(Depth) | O(Depth) |
//! |From root | O(Depth) | O(1) |
//!
//! [Masonry]: https://crates.io/crates/masonry
type NodeId = u64;
// We instantiate both modules when `cfg(test)` is true.
// This tricks IDEs (at least VSCode) into always building both modules
// and giving us completions, jump to definition, etc, at all times.
// We make both modules `pub` and `doc(hidden)` so we don't get warnings about unused items.
pub use *;
pub use *;