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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
extern crate alloc;
use alloc::vec::Vec;
use crate::metis::dot::Dot;
use crate::metis::{DotSet, DotStore};
use super::{Locus, Rhapsody};
/// The sequence store instance of the open [`DotStore`] axis.
///
/// [`dots`](DotStore::dots) is the *visible* dots (the causal coordinate the
/// survivor law governs); the skeleton is ordering state, not causal support.
/// [`is_bottom`](DotStore::is_bottom) is true only when the rhapsody has never
/// held anything: a fully deleted document (empty visible, non-empty
/// skeleton) is *not* bottom, because its skeleton is state a merge must
/// keep.
impl DotStore for Rhapsody {
fn dots(&self) -> impl Iterator<Item = Dot> + '_ {
// Visibility is the causal coordinate; the skeleton is order state.
self.visible.dots()
}
fn is_bottom(&self) -> bool {
self.visible.is_bottom() && self.skeleton.is_empty()
}
fn causal_merge(&self, self_context: &DotSet, other: &Self, other_context: &DotSet) -> Self {
// The skeleton is grow-only: union the two, keeping self's locus for
// a dot both carry (equal by the honest basis, trait law 3).
let mut skeleton = self.skeleton.clone();
skeleton.extend_ascending(other.skeleton.iter());
// Visibility rides the survivor law, the bare-store merge under the
// two pair contexts.
let visible = self
.visible
.causal_merge(self_context, &other.visible, other_context);
// `from_parts` materializes the child index for the merged skeleton
// once. This pure form pays a whole-skeleton clone plus a full index
// rebuild per fold, so the hot write paths run `causal_merge_from`
// below (S181 measured this form linear in the document per composed
// keystroke; S182 is the cure).
Self::from_plane(skeleton, visible)
}
fn causal_merge_from(&mut self, self_context: &DotSet, other: &Self, other_context: &DotSet) {
// The visibility deltas, gathered before the fold moves them: the
// survivor fold's own two residual arms (a held dot dies iff the
// other side saw it and dropped it; a foreign dot enters iff never
// seen here), each bounded by the delta, never the document. The
// order thread consumes them as visibility flips, so the
// positional aggregates ride the same delta-sized fold.
let expelled: Vec<Dot> = other_context
.difference(&other.visible)
.filter(|&dot| self.visible.contains(dot))
.collect();
let admitted: Vec<Dot> = other
.visible
.difference(self_context)
.filter(|&dot| !self.visible.contains(dot))
.collect();
// The same merge as edits against `self`: the grow-only skeleton
// gains exactly `other`'s novel loci, keeping self's locus for a
// dot both carry (equal by the honest basis, trait law 3, so
// or-insert and keep-self agree). No clone, no rebuild. Since
// R-19's run-grade arm, the ascending enumeration groups into
// maximal *novel chain runs* (consecutive same-station dots, each
// past the head anchored `After` its predecessor: a paste, an
// import, any bulk-typed span) and each run folds through the
// bulk machinery in one write; everything else, including every
// dot already held, takes the per-dot `record_locus` unchanged.
if other.skeleton.len() <= 1 {
// The keystroke shape, kept off the detector entirely: a
// singleton delta pays exactly the per-dot fold it always
// paid, no grouping state, no extra freshness probe.
for (dot, locus) in other.skeleton.iter() {
let _ = self.record_locus(dot, locus);
}
} else {
let mut run_first: Option<Dot> = None;
let mut run_prev: Option<Dot> = None;
let mut pending: Vec<crate::metis::Locus> = Vec::new();
for (dot, locus) in other.skeleton.iter() {
let extends = run_prev.is_some_and(|prev| {
prev.station() == dot.station()
&& prev.counter().checked_add(1) == Some(dot.counter())
&& locus.anchor == crate::metis::Anchor::After(prev.into())
});
if extends && !self.skeleton.contains(dot) {
pending.push(locus);
run_prev = Some(dot);
continue;
}
if let Some(first_dot) = run_first.take() {
self.absorb_novel_run(first_dot, &pending);
pending.clear();
}
run_prev = None;
if !self.skeleton.contains(dot) {
run_first = Some(dot);
run_prev = Some(dot);
pending.push(locus);
}
}
if let Some(first_dot) = run_first.take() {
self.absorb_novel_run(first_dot, &pending);
}
}
// Visibility rides the survivor law in place, under the same pair
// contexts the pure form threads.
self.visible
.causal_merge_from(self_context, &other.visible, other_context);
// The order thread already holds every newly placed region; apply
// the post-fold visibility residuals. An unplaced dot has no slot
// and refuses untouched.
self.settle_thread_after_merge(&expelled, &admitted);
}
fn restrict(&self, roster: impl IntoIterator<Item = u32>) -> Self {
// Fiber selection on BOTH coordinates: keep the roster stations'
// dots in the skeleton and in the visible set. Restriction can drop
// an anchor's station and strand its descendants unreachable in
// `order()` (the created-order hazard analog PRD 0017 records): an
// order verdict on a restriction is scoped to the roster, exactly as
// the survivor law's restriction verdicts are (PRD 0013 R2). The
// survivor-law commutation the axis requires holds because it is
// decided per dot on the visible coordinate, which `DotSet::restrict`
// selects fiber-wise.
let roster: alloc::collections::BTreeSet<u32> = roster.into_iter().collect();
let skeleton = self
.skeleton
.iter()
.filter(|entry| roster.contains(&entry.0.station()))
.collect();
let visible = self.visible.restrict(roster.iter().copied());
Self::from_parts(skeleton, visible)
}
fn support(&self) -> DotSet {
// The visible set IS the support in have-set form already: a compact
// clone instead of the default's per-dot re-fold (arc 10's survivor
// half, composed from shipped parts as the vision recorded).
self.visible.clone()
}
fn novel_to_witnessed(&self, context: &DotSet, recording: &DotSet) -> Self {
// Support selection is novel_to's, unchanged: the survivor law's
// novelty against the peer's context. The skeleton is selected by the
// WITNESS, not the context: possession claimed directly is exactly
// what coverage could not prove (the S190 outrun-heal law), so the
// sub-selection novel_to must refuse is sound here, and the owed
// recording state enumerates as the residual `woven \ recording`
// (bounded by what is owed, never the document). An under-claiming
// witness over-serves and the grow-only skeleton union absorbs the
// redundancy; an over-claiming one starves only the claimant, and
// only of TOMBSTONE loci: the second pass below keeps the fragment
// internally valid (every visible dot rides with its locus, the
// wire frame's own canonical-form law) against a witness that
// claims a live dot the peer's context disowns, a claim no honest
// witness can make (an honest woven set is covered by its own
// context) but a fragment must not be corrupted by. The pass is
// O(novel) and adds nothing for an honest witness (a novel dot is
// outside the peer's context, so an honest witness never claims it
// and its locus is already in the residual); the gate review of
// this slice supplied the counterexample it closes.
let visible = self.visible.novel_to(context);
let mut skeleton: alloc::collections::BTreeMap<Dot, Locus> = self
.woven
.difference(recording)
.filter_map(|dot| self.skeleton.get(&dot).map(|locus| (dot, locus)))
.collect();
for dot in visible.dots() {
if let Some(locus) = self.skeleton.get(&dot) {
let _ = skeleton.entry(dot).or_insert(locus);
}
}
Self::from_parts(skeleton, visible)
}
fn novel_to(&self, context: &DotSet) -> Self {
// Coverage selection on the SURVIVOR coordinate only: the visible
// fragment is the survivor-law novelty, but the skeleton ships
// whole, because a survivor context is no proxy for recording
// knowledge. A peer whose context covers a woven dot has proof the
// dot was superseded, not proof it ever held the dot's locus (a
// pure-context retract delta conveys coverage bare, and can outrun
// the weave delta that carries the place), and a missing tombstone
// locus strands every later element anchored to it: unreachable at
// the peer, placed at the writer, forever. So the only fragment the
// survivor context can soundly license is the full skeleton, the
// S113 `delta_for` correction one coordinate over (S190; the
// outrun-heal example test pins it). The fragment cost rides the
// anti-entropy path arc 10 already watches; the trait's support law
// is untouched (`dots()` is the visible coordinate, still exactly
// the novelty).
let visible = self.visible.novel_to(context);
Self::from_plane(self.skeleton.clone(), visible)
}
}