Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_ore/src/seq/claim.rs

9.2 KiB, 81 runs

created by r1870400018:17910, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Who owns which byte, and which bytes are dead.
2//!
3//! Two interval structures over content-identifier space, and between them they
4//! settle every race a move can start.
5//!
6//! The claim register is a last-writer-wins register per byte, keyed by content
7//! identifier and valued by the operation whose slot shows that byte. An absent
8//! entry means the byte is still shown by the splice that created it, so
9//! unmoved content costs nothing to record. Because `max` over a total order is
10//! commutative, associative and idempotent, the register is a join-semilattice
11//! and needs no arbitration protocol; because the register is per byte rather
12//! than per element, a move can claim part of a run, which is what makes a range
13//! move expressible at all.
14//!
15//! The tombstone set is grow-only, so it commutes with everything including a
16//! move. A dead byte renders as nothing wherever it is, which is why move
17//! against delete needs no tie-break: the bytes move, and they are dead, and
18//! both are true at once.
19//!
20//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
21//! Anthropic Claude
22
23use crate::id::{
24 ContentId,
25 ContentRange,
26 OpId,
27};
28use crate::seq::atom::Atoms;
29use crate::op::{
30 Op,
31 Placing,
32};
33
34use oxedyne_fe2o3_core::prelude::*;
35use oxedyne_fe2o3_data::interval::IntervalMap;
36
37use std::collections::{
38 BTreeMap,
39 BTreeSet,
40};
41use std::ops::Range;
42
43
44/// Which operation's slot owns each byte that has ever been moved.
45///
46/// One interval line per atom, the line being offsets within that atom, so that
47/// a move of a contiguous run costs one interval however long the run is.
48#[derive(Clone, Debug, Default, Eq, PartialEq)]
49pub struct Claims {
50 map: BTreeMap<OpId, IntervalMap<OpId>>, // claimed offsets, by creating operation
51}
52
53impl Claims {
54
55 pub fn new() -> Self {
56 Self { map: BTreeMap::new() }
57 }
58
59 /// Builds the register from an operation set given **in ascending op
60 /// order**.
61 ///
62 /// Insertion into an interval map is last-writer-wins over the ground it
63 /// covers, so feeding the moves in op order leaves each byte claimed by the
64 /// highest mover in op order, which is the register's merge rule stated as a
65 /// loop.
66 pub fn build(ops: &[(OpId, &Op)])
67 -> Outcome<Self>
68 {
69 Self::build_without(ops, &BTreeSet::new())
70 }
71
72 /// Builds the register from an operation set given **in ascending op order**,
73 /// leaving out the moves named in `voided`.
74 ///
75 /// A voided move is one the cross-file cycle rule has confined, and confining
76 /// it is exactly this: its claims are not written, so its bytes are owned by
77 /// whoever owned them before it -- the previous claimant, or the splice that
78 /// created them -- and they render where they already were.
79 pub fn build_without(ops: &[(OpId, &Op)], voided: &BTreeSet<OpId>)
80 -> Outcome<Self>
81 {
82 let mut map: BTreeMap<OpId, IntervalMap<OpId>> = BTreeMap::new();
83 for (id, op) in ops {
84 if voided.contains(id) {
85 continue;
86 }
87 if let Op::Move { src, .. } = op {
88 for r in src {
89 if r.is_empty() {
90 continue;
91 }
92 res!(map.entry(r.op()).or_default().insert(r.offsets(), *id));
93 }
94 }
95 }
96 Ok(Self { map })
97 }
98
99 /// A byte no move has claimed is owned by the splice that created it.
100 pub fn owner(&self, cid: &ContentId) -> OpId {
101 self.map.get(&cid.op)
102 .and_then(|m| m.get(cid.off))
103 .copied()
104 .unwrap_or(cid.op)
105 }
106
107 /// The maximal runs of `range` and their owners, in ascending order of offset.
108 ///
109 /// Runs are maximal because a gap between claims is owned by the creating
110 /// splice, which is never a mover, so no two neighbouring runs can share an
111 /// owner.
112 pub fn runs(&self, range: &ContentRange)
113 -> Vec<(Range<u64>, OpId)>
114 {
115 let mut out: Vec<(Range<u64>, OpId)> = Vec::new();
116 let mut at = range.from();
117 if let Some(m) = self.map.get(&range.op()) {
118 for (iv, owner) in m.overlapping(range.offsets()) {
119 let from = iv.start.max(range.from());
120 let to = iv.end.min(range.to());
121 if from > at {
122 out.push((at..from, range.op()));
123 }
124 if to > from {
125 out.push((from..to, *owner));
126 at = to;
127 }
128 }
129 }
130 if at < range.to() {
131 out.push((at..range.to(), range.op()));
132 }
133 out
134 }
135
136 /// The cost of every move ever made, and of nothing else.
137 pub fn intervals(&self) -> usize {
138 self.map.values().map(|m| m.len()).sum()
139 }
140}
141
142
143/// The bytes that have been deleted.
144///
145/// A grow-only interval set: deleting a four hundred line block costs one entry,
146/// so the count tracks the number of edits rather than the volume of deleted
147/// text. Identifiers are kept even where bytes are not, because an anchor may
148/// name dead content and routinely does.
149#[derive(Clone, Debug, Default, Eq, PartialEq)]
150pub struct Dead {
151 map: BTreeMap<OpId, IntervalMap<()>>, // dead offsets, by creating operation
152}
153
154impl Dead {
155
156 pub fn new() -> Self {
157 Self { map: BTreeMap::new() }
158 }
159
160 /// Builds the tombstone set from an operation set, in any order.
161 ///
162 /// A file's creation buries the one byte it mints, that byte being the file's
163 /// origin anchor: it exists to be named and must never be seen.
164 pub fn build(ops: &[(OpId, &Op)])
165 -> Outcome<Self>
166 {
167 Self::build_without(ops, &BTreeSet::new())
168 }
169
170 /// Builds the tombstone set as [`Dead::build`] does, except that a splice named
171 /// in `yielded` buries its **own** insertion and none of what it removed.
172 ///
173 /// This is what yielding an overlap group is. A concurrent group of splices that
174 /// named overlapping content is arbitrated, the op-order maximum prevails, and
175 /// every member concurrent with it yields: within the contended region the file
176 /// then holds whole hunks rather than two authors' bytes interleaved.
177 ///
178 /// A confined *move* costs nothing, because its bytes fall back to a previous
179 /// owner. A splice's insertion has no previous owner, so declining to place its
180 /// slot would leave its bytes owned by nothing, which is [`crate::seq::render::Flag::Orphaned`]
181 /// and a fault. The mechanism that is already right is the tombstone: the
182 /// insertion is buried whole, the removals are dropped so that they do not bury,
183 /// and the slot itself is still placed, so anything anchored into the yielded
184 /// content still resolves against a target that is there.
185 ///
186 /// Yielding is therefore not only subtractive. Where the yielding splice deleted
187 /// text the prevailing one did not, that text comes back, and the arbitrating
188 /// render is *larger* than the unarbitrated one.
189 pub fn build_without(ops: &[(OpId, &Op)], yielded: &BTreeSet<OpId>)
190 -> Outcome<Self>
191 {
192 let mut map: BTreeMap<OpId, IntervalMap<()>> = BTreeMap::new();
193 for (id, op) in ops {
194 match op {
195 Op::FileCreate { .. } => {
196 res!(map.entry(*id).or_default().insert(0..1, ()));
197 },
198 Op::Splice { remove, insert, .. } => {
199 if yielded.contains(id) {
200 if !insert.is_empty() {
201 res!(map.entry(*id).or_default()
202 .insert(0..insert.len() as u64, ()));
203 }
204 continue;
205 }
206 for r in remove {
207 if r.is_empty() {
208 continue;
209 }
210 res!(map.entry(r.op()).or_default().insert(r.offsets(), ()));
211 }
212 },
213 // A forgotten file is dead from birth, as any file's origin byte
214 // is. A forgotten insertion is buried whole -- that is what
215 // forgetting is, in this structure -- and what it removed stays
216 // removed, since the removal was done and forgetting the bytes
217 // it brought does not bring back the bytes it took. Yielding
218 // changes nothing here: its insertion is buried already, and a
219 // yielded splice's removals would be dropped, so they are.
220 Op::Forgotten { placing: Placing::File } => {
221 res!(map.entry(*id).or_default().insert(0..1, ()));
222 },
223 Op::Forgotten { placing: Placing::Splice { remove, len, .. } } => {
224 if *len > 0 {
225 res!(map.entry(*id).or_default().insert(0..*len, ()));
226 }
227 if yielded.contains(id) {
228 continue;
229 }
230 for r in remove {
231 if r.is_empty() {
232 continue;
233 }
234 res!(map.entry(r.op()).or_default().insert(r.offsets(), ()));
235 }
236 },
237 _ => (),
238 }
239 }
240 Ok(Self { map })
241 }
242
243 pub fn is_dead(&self, cid: &ContentId) -> bool {
244 self.map.get(&cid.op).map(|m| m.contains(cid.off)).unwrap_or(false)
245 }
246
247 /// The live sub-runs of `span` within the atom created by `op`, ascending.
248 pub fn live_runs(&self, op: &OpId, span: Range<u64>)
249 -> Vec<Range<u64>>
250 {
251 let mut out: Vec<Range<u64>> = Vec::new();
252 let mut at = span.start;
253 if let Some(m) = self.map.get(op) {
254 for (iv, _) in m.overlapping(span.clone()) {
255 let from = iv.start.max(span.start);
256 let to = iv.end.min(span.end);
257 if from > at {
258 out.push(at..from);
259 }
260 at = at.max(to);
261 }
262 }
263 if at < span.end {
264 out.push(at..span.end);
265 }
266 out
267 }
268
269 /// The number of dead bytes lying within an atom the operation set holds.
270 ///
271 /// A tombstone naming content beyond the end of its atom, or naming an atom
272 /// that is not present, is not counted: it describes bytes this set cannot
273 /// account for, and the conservation check must not be told otherwise.
274 pub fn within(&self, atoms: &Atoms) -> u64 {
275 let mut total = 0u64;
276 for (op, m) in &self.map {
277 let len = atoms.run_len(op);
278 for (iv, _) in m.iter() {
279 let to = iv.end.min(len);
280 if to > iv.start {
281 total += to - iv.start;
282 }
283 }
284 }
285 total
286 }
287
288 pub fn intervals(&self) -> usize {
289 self.map.values().map(|m| m.len()).sum()
290 }
291}