Oregami
Repositories/oxedyne/fe2o3

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

11.7 KiB, 37 runs

created by r1192329593:77871, 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//! Concurrent splices that make the same edit, rendered as the one edit they are.
2//!
3//! Two authors who add the same line at the same place, or make the same
4//! replacement, or the same deletion, write splices alike in everything but
5//! their identities: the same anchors, the same removals, the same bind and the
6//! same bytes. Rendered as two, an insertion appears twice and a removal is an
7//! overlap that one of them must yield; both misread what happened, which is that
8//! the two agreed. Git takes an identical change once, and so does this.
9//!
10//! A class of such splices, pairwise concurrent, is **folded** into its op-order
11//! maximum. The others leave the render's operation set, and every reference to
12//! their bytes -- an anchor, a removal, a move's source, a note -- is rewritten to
13//! name the same offset of the maximum's, so that a later edit inside either copy
14//! lands in the one that renders. The causal graph is read the same way for
15//! placement: having seen any member is having seen the class ([`Cause`]), so an
16//! edit made after one author's copy is not taken for a race with the other's.
17//! It is not read so for removal. An operation that takes bytes out of a class,
18//! or moves them, having seen only some of its copies, takes them from authors
19//! whose copies it never saw, and contends with each of those
20//! ([`Cause::takes`]); the flags go to them and not to the copies it saw.
21//!
22//! A forgotten splice keeps its shape but not its bytes, so it is never folded:
23//! nothing that keeps no bytes can say two were alike without being a test for
24//! the bytes. A forget is therefore authored over the whole class
25//! ([`crate::seq::render::Repo::twins_of`]), since either copy shows what was
26//! asked to go; a copy its author had not yet seen is another author's writing
27//! of those bytes, and is not forgotten with it.
28//!
29//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
30//! Anthropic Claude
31
32use crate::id::{
33 Anchor,
34 ContentId,
35 ContentRange,
36 OpId,
37};
38use crate::log::Causality;
39use crate::op::{
40 Bind,
41 Op,
42 Placing,
43};
44use crate::seq::OpOrder;
45use crate::seq::render::Flag;
46
47use oxedyne_fe2o3_core::prelude::*;
48
49use std::collections::BTreeMap;
50
51
52/// The folded classes of an operation set.
53#[derive(Clone, Debug, Default)]
54pub struct Twins {
55 into: BTreeMap<OpId, OpId>, // each folded splice, and the one it renders as
56 class: BTreeMap<OpId, Vec<OpId>>, // each kept splice with a class, kept one first
57}
58
59/// What makes two splices one edit: everything but their identities.
60type Key<'o> = (Option<Anchor>, Option<Anchor>, Option<Bind>, &'o [ContentRange], &'o [u8]);
61
62impl Twins {
63
64 /// Finds the classes in `ops`, which are in op order.
65 pub fn find(ops: &[(OpId, &Op)], graph: &Causality<'_>) -> Self {
66 let mut alike: BTreeMap<Key<'_>, Vec<OpId>> = BTreeMap::new();
67 for (id, op) in ops {
68 if let Op::Splice { left, right, remove, insert, bind } = op {
69 alike.entry((*left, *right, *bind, remove, insert)).or_default().push(*id);
70 }
71 }
72 let mut out = Self::default();
73 for ids in alike.into_values() {
74 if ids.len() < 2 {
75 continue;
76 }
77 // The maximum is kept; a member joins it only if concurrent with every
78 // member already in, so that a class is one event and never a sequence.
79 let mut class: Vec<OpId> = Vec::new();
80 for id in ids.iter().rev() {
81 if class.iter().all(|m| graph.concurrent(m, id)) {
82 class.push(*id);
83 }
84 }
85 if class.len() > 1 {
86 for m in &class[1..] {
87 out.into.insert(*m, class[0]);
88 }
89 out.class.insert(class[0], class);
90 }
91 }
92 out
93 }
94
95 pub fn is_empty(&self) -> bool {
96 self.into.is_empty()
97 }
98
99 /// Each folded splice, and the one it renders as.
100 pub fn folded(&self) -> &BTreeMap<OpId, OpId> {
101 &self.into
102 }
103
104 /// Each member of a folded class, and the whole class, kept member first.
105 pub fn by_member(&self) -> BTreeMap<OpId, Vec<OpId>> {
106 self.class.values()
107 .flat_map(|c| c.iter().map(move |m| (*m, c.clone())))
108 .collect()
109 }
110
111 /// The class an operation renders as one with, itself alone if none.
112 fn class<'s>(&'s self, id: &'s OpId) -> &'s [OpId] {
113 match self.class.get(id) {
114 Some(c) => c,
115 None => std::slice::from_ref(id),
116 }
117 }
118
119 /// Every operation that names a folded splice's bytes, rewritten to name the
120 /// kept one's.
121 pub fn rewrite(&self, ops: &[(OpId, &Op)])
122 -> Outcome<BTreeMap<OpId, Op>>
123 {
124 let mut out: BTreeMap<OpId, Op> = BTreeMap::new();
125 if self.is_empty() {
126 return Ok(out);
127 }
128 for (id, op) in ops {
129 if self.into.contains_key(id) || !self.names_folded(op) {
130 continue;
131 }
132 let made = match op {
133 Op::Splice { left, right, remove, insert, bind } => Op::Splice {
134 left: self.anchor(left),
135 right: self.anchor(right),
136 remove: res!(self.ranges(remove)),
137 insert: insert.clone(),
138 bind: *bind,
139 },
140 Op::Move { src, left, right, bind } => Op::Move {
141 src: res!(self.ranges(src)),
142 left: self.anchor(left),
143 right: self.anchor(right),
144 bind: *bind,
145 },
146 Op::Note { on, text } => Op::Note {
147 on: res!(self.ranges(on)),
148 text: text.clone(),
149 },
150 Op::Forgotten { placing: Placing::Splice { left, right, remove, len, bind } }
151 => Op::Forgotten { placing: Placing::Splice {
152 left: self.anchor(left),
153 right: self.anchor(right),
154 remove: res!(self.ranges(remove)),
155 len: *len,
156 bind: *bind,
157 }},
158 _ => continue,
159 };
160 out.insert(*id, made);
161 }
162 Ok(out)
163 }
164
165 /// The operation set the render reads: the folded splices gone, and every
166 /// operation that named one in its rewritten form.
167 pub fn fold<'o>(&self, ops: &[(OpId, &'o Op)], held: &'o BTreeMap<OpId, Op>)
168 -> Vec<(OpId, &'o Op)>
169 {
170 ops.iter()
171 .filter(|(id, _)| !self.into.contains_key(id))
172 .map(|(id, op)| (*id, held.get(id).unwrap_or(*op)))
173 .collect()
174 }
175
176 /// Does the operation name a folded splice's bytes?
177 fn names_folded(&self, op: &Op) -> bool {
178 let (l, r) = op.origins();
179 [l, r].iter().flatten().any(|a| self.into.contains_key(&a.content.op))
180 || op.regions().iter().chain(op.note_on()).any(|c| self.into.contains_key(&c.op()))
181 }
182
183 fn anchor(&self, a: &Option<Anchor>) -> Option<Anchor> {
184 a.map(|a| match self.into.get(&a.content.op) {
185 Some(k) => Anchor::new(ContentId::new(*k, a.content.off), a.side),
186 None => a,
187 })
188 }
189
190 fn ranges(&self, rs: &[ContentRange])
191 -> Outcome<Vec<ContentRange>>
192 {
193 let mut out = Vec::with_capacity(rs.len());
194 for r in rs {
195 out.push(match self.into.get(&r.op()) {
196 Some(k) => res!(ContentRange::new(*k, r.from(), r.to())),
197 None => *r,
198 });
199 }
200 Ok(out)
201 }
202}
203
204
205/// The causal graph as the render reads it, each folded class being one event:
206/// an operation has seen the class when it has seen any member, and the class
207/// has seen what any member saw.
208pub struct Cause<'c> {
209 graph: &'c Causality<'c>,
210 twins: &'c Twins,
211}
212
213impl<'c> Cause<'c> {
214
215 pub fn new(graph: &'c Causality<'c>, twins: &'c Twins) -> Self {
216 Self { graph, twins }
217 }
218
219 /// Was `from` written in knowledge of `target`, itself included?
220 pub fn reaches(&self, from: &OpId, target: &OpId) -> bool {
221 let to = self.twins.class(target);
222 self.twins.class(from).iter().any(|f| to.iter().any(|t| self.graph.reaches(f, t)))
223 }
224
225 /// Distinct, and neither written in knowledge of the other?
226 pub fn concurrent(&self, a: &OpId, b: &OpId) -> bool {
227 a != b && !self.reaches(a, b) && !self.reaches(b, a)
228 }
229
230 /// The class an operation renders as one with, itself alone if none.
231 pub fn class<'s>(&'s self, id: &'s OpId) -> &'s [OpId] {
232 self.twins.class(id)
233 }
234
235 /// The members of `target`'s class that no member of `from`'s was written in
236 /// knowledge of.
237 pub fn unseen(&self, from: &OpId, target: &OpId) -> Vec<OpId> {
238 let by = self.twins.class(from);
239 self.twins.class(target).iter()
240 .filter(|t| !by.iter().any(|f| self.graph.reaches(f, t)))
241 .copied()
242 .collect()
243 }
244
245 /// Each run of a class's bytes the operation removes or moves without having
246 /// seen every copy, with the kept splice it names. Its author saw the edit,
247 /// which places it; but the copies it never saw are other authors' bytes, and
248 /// it contends with each of them.
249 pub fn takes(&self, id: &OpId, op: &Op) -> Vec<(OpId, ContentRange)> {
250 op.regions().iter()
251 .filter(|r| !r.is_empty()
252 && self.twins.class.contains_key(&r.op())
253 && !self.unseen(id, &r.op()).is_empty())
254 .map(|r| (r.op(), *r))
255 .collect()
256 }
257
258 /// The flags, with each that a kept splice raises raised for every member of
259 /// its class as well: two authors wrote the one edit, and a yield, an overlap
260 /// or a stranding is news to each. An overlap or a yield between a class and
261 /// an operation that saw some of its copies is news only to the authors of
262 /// those it did not see, and its group names only those. A yield's group
263 /// otherwise names every member of every class in it; what prevailed is named
264 /// by the copy that renders.
265 pub fn spread(&self, flags: Vec<Flag>) -> Vec<Flag> {
266 if self.twins.is_empty() {
267 return flags;
268 }
269 let mut out: Vec<Flag> = Vec::with_capacity(flags.len());
270 for flag in flags {
271 match flag {
272 Flag::Overlap { ops, region } => match ops.as_slice() {
273 [a, b] => for x in self.unseen(b, a) {
274 for y in self.unseen(a, b) {
275 let mut pair = vec![x, y];
276 pair.sort();
277 out.push(Flag::Overlap { ops: pair, region });
278 }
279 },
280 _ => out.push(Flag::Overlap { ops, region }),
281 },
282 Flag::Abutting { ops, at } => match ops.as_slice() {
283 [a, b] => for x in self.unseen(b, a) {
284 for y in self.unseen(a, b) {
285 let mut pair = vec![x, y];
286 pair.sort();
287 out.push(Flag::Abutting { ops: pair, at });
288 }
289 },
290 _ => out.push(Flag::Abutting { ops, at }),
291 },
292 Flag::Yielded { op, to, group, through } => {
293 // A class the winner saw only part of contended by the copies it
294 // did not see; one it saw whole is its own, or in its past.
295 let mut all: Vec<OpId> = group.iter()
296 .flat_map(|g| match self.unseen(&to, g) {
297 u if u.is_empty() => self.class(g).to_vec(),
298 u => u,
299 })
300 .collect();
301 all.sort_by_key(OpOrder::of);
302 // News to each copy some other member took without having seen.
303 let mine = self.class(&op);
304 let mut told: Vec<OpId> = group.iter()
305 .filter(|g| !mine.contains(g))
306 .flat_map(|g| self.unseen(g, &op))
307 .collect();
308 told.sort_by_key(OpOrder::of);
309 told.dedup();
310 // Each copy is told of the highest member that took it unseen, which
311 // is `to` unless `to` had seen that copy.
312 for m in told {
313 let by = match self.graph.reaches(&to, &m) {
314 false => to,
315 true => group.iter()
316 .filter(|g| !mine.contains(g) && !self.graph.reaches(g, &m))
317 .copied()
318 .max_by_key(OpOrder::of)
319 .unwrap_or(to),
320 };
321 out.push(Flag::Yielded { op: m, to: by, group: all.clone(), through });
322 }
323 },
324 Flag::Stranded { op, by } => for m in self.class(&op) {
325 for d in self.class(&by) {
326 out.push(Flag::Stranded { op: *m, by: *d });
327 }
328 },
329 Flag::SplicedIntoDeleted { op, file, del } => for m in self.class(&op) {
330 out.push(Flag::SplicedIntoDeleted { op: *m, file, del });
331 },
332 Flag::Demoted { op, sub, origin } => for m in self.class(&op) {
333 out.push(Flag::Demoted { op: *m, sub, origin });
334 },
335 Flag::Dropped { op, sub, origin } => for m in self.class(&op) {
336 out.push(Flag::Dropped { op: *m, sub, origin });
337 },
338 Flag::Orphaned { op, sub } => for m in self.class(&op) {
339 out.push(Flag::Orphaned { op: *m, sub });
340 },
341 Flag::CrossedFile { op, sub, from, to } => for m in self.class(&op) {
342 out.push(Flag::CrossedFile { op: *m, sub, from, to });
343 },
344 // A move is never a twin.
345 other @ (Flag::Torn { .. }
346 | Flag::MovedIntoDeleted { .. }
347 | Flag::Confined { .. }
348 | Flag::Won { .. }) => out.push(other),
349 }
350 }
351 out
352 }
353}