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
//! Deterministic cost counters of an edited tree's reads.
//!
//! The reads of an edited tree take two kinds of non-constant steps:
//!
//! * a **lookup**: an O(log) query of the overlay's maps (the runs by first
//! slot, the link overrides, the arenas by first slot) or a treap query
//! from the root (a prefix sum, a byte search);
//! * an **edge**: one move along a treap edge while stepping from a run to
//! the next or previous one (amortised O(1) per run over a traversal).
//!
//! Edits count a third kind, a **visit**: an entry a compaction of the
//! arena slab touches (compactions are paid for by the frees
//! that trigger them, so visits per edit stay bounded).
//!
//! Tests count them to state the cost of sequential reads independently
//! of the machine: a full read of a tree with R runs takes O(R) lookups and
//! edges, whatever the number of elements. In library builds `count` is an
//! empty inline function: no state exists outside `cfg(test)` (there is
//! no interior mutability in the tree; the test counters are thread-local,
//! never part of `SyntaxTree`).
/// A kind of step counted.
pub
thread_local!
/// Counts one step (tests only; nothing in library builds).
pub
/// The steps counted on this thread since the last call, as `(lookups,
/// edges)`, and resets them.
pub
/// The compaction visits counted on this thread since the last call, and
/// resets them.
pub