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 | |
| 32 | use crate::id::{ |
| 33 | Anchor, |
| 34 | ContentId, |
| 35 | ContentRange, |
| 36 | OpId, |
| 37 | }; |
| 38 | use crate::log::Causality; |
| 39 | use crate::op::{ |
| 40 | Bind, |
| 41 | Op, |
| 42 | Placing, |
| 43 | }; |
| 44 | use crate::seq::OpOrder; |
| 45 | use crate::seq::render::Flag; |
| 46 | |
| 47 | use oxedyne_fe2o3_core::prelude::*; |
| 48 | |
| 49 | use std::collections::BTreeMap; |
| 50 | |
| 51 | |
| 52 | /// The folded classes of an operation set. |
| 53 | #[derive(Clone, Debug, Default)] |
| 54 | pub 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. |
| 60 | type Key<'o> = (Option<Anchor>, Option<Anchor>, Option<Bind>, &'o [ContentRange], &'o [u8]); |
| 61 | |
| 62 | impl 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. |
| 208 | pub struct Cause<'c> { |
| 209 | graph: &'c Causality<'c>, |
| 210 | twins: &'c Twins, |
| 211 | } |
| 212 | |
| 213 | impl<'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 | } |