12.4 KiB, 8 runs
created by r2848102244:391, 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 | //! What the operations say the files are, and where a working copy would put |
| 2 | //! them. |
| 3 | //! |
| 4 | //! The engine names a file by the identity of the operation that created it, and |
| 5 | //! renders the whole repository in one pass: one [`Sequence`] takes every record |
| 6 | //! whatever it says, and `Sequence::render_with` returns a [`Repo`] holding every |
| 7 | //! file the operations describe. Nothing here decides which operation belongs to |
| 8 | //! which file, because nothing can: a file is a subtree of the forest the render |
| 9 | //! lays out, so the association is read off the render rather than guessed at |
| 10 | //! from a path. This module is therefore a view over a render, and nothing else. |
| 11 | //! |
| 12 | //! # A path is not a name |
| 13 | //! |
| 14 | //! A path is metadata a rename may change, and it is bytes rather than a string, |
| 15 | //! because a path is not required to be UTF-8. Two live files may hold one path |
| 16 | //! -- that is what two branches independently creating the same path leaves |
| 17 | //! behind, and both files keep their bytes -- so the repository's answer to "what |
| 18 | //! is at `notes.md`" is a list. |
| 19 | //! |
| 20 | //! Which of them a working copy writes under the shared name is a policy, and |
| 21 | //! that policy is [`Layout`]: the file highest in op order keeps the name, and |
| 22 | //! every other materialises under a derived one. The crate reports the clash; the |
| 23 | //! decision to act on it is the caller's. |
| 24 | //! |
| 25 | //! # Why the policy lives here |
| 26 | //! |
| 27 | //! Because it must not drift. The command line tool puts these names on a disk |
| 28 | //! and the forge shows the same names on a page, and a reader who has seen one |
| 29 | //! must not have to learn a second vocabulary for the same fact. Two |
| 30 | //! implementations of one policy were carried for a while and are not carried any |
| 31 | //! more: this is the one, and both callers read it. |
| 32 | //! |
| 33 | //! What is deliberately **not** here is anything that touches a filesystem. |
| 34 | //! Writing a laid-out tree into a working copy, reading one back, and setting a |
| 35 | //! file's mode are the command line tool's, because only a tool with a working |
| 36 | //! copy has any use for them. |
| 37 | |
| 38 | use oxedyne_fe2o3_core::prelude::*; |
| 39 | use oxedyne_fe2o3_ore::id::OpId; |
| 40 | use oxedyne_fe2o3_ore::log::{ |
| 41 | Causality, |
| 42 | OpLog, |
| 43 | }; |
| 44 | use oxedyne_fe2o3_ore::op::{ |
| 45 | Mode, |
| 46 | Op, |
| 47 | Record, |
| 48 | }; |
| 49 | use oxedyne_fe2o3_ore::seq::render::{ |
| 50 | Rendered, |
| 51 | Repo, |
| 52 | }; |
| 53 | use oxedyne_fe2o3_ore::seq::{ |
| 54 | OpOrder, |
| 55 | Sequence, |
| 56 | }; |
| 57 | |
| 58 | use std::collections::{ |
| 59 | BTreeMap, |
| 60 | BTreeSet, |
| 61 | }; |
| 62 | |
| 63 | |
| 64 | /// What a file's derived name begins with when it has lost a clash. |
| 65 | pub const CLASH_MARK: &str = ".clash-"; |
| 66 | |
| 67 | |
| 68 | /// Returns a path as text, with anything that is not valid UTF-8 replaced. |
| 69 | /// |
| 70 | /// For messages and for display only. The bytes are the record, and every |
| 71 | /// decision is made on them. |
| 72 | pub fn shown(path: &[u8]) -> String { |
| 73 | String::from_utf8_lossy(path).into_owned() |
| 74 | } |
| 75 | |
| 76 | |
| 77 | /// Every file a set of operations describes, and what the renderer noticed. |
| 78 | /// |
| 79 | /// One name for the rendered repository, so that a repository on disk and the |
| 80 | /// repository the operations describe are never the same word. |
| 81 | #[derive(Debug, Default)] |
| 82 | pub struct Tree { |
| 83 | /// The repository as the render produced it. |
| 84 | pub repo: Repo, |
| 85 | } |
| 86 | |
| 87 | impl Tree { |
| 88 | |
| 89 | /// Builds the tree from records in append order, rendering the repository |
| 90 | /// against the causal graph those records form. |
| 91 | /// |
| 92 | /// Conservation is checked in every build and not only in a debug one, for |
| 93 | /// the reason it always was: a caller that quietly served a tree missing |
| 94 | /// bytes would be the worst of all the ways this could fail, and a structural |
| 95 | /// fault that shows up only under `cargo test` is a fault nobody meets. The |
| 96 | /// check is no longer made here, because `render_with` now makes it while it |
| 97 | /// still holds the atoms and the tombstones the check reads; asking a second |
| 98 | /// time rebuilt both, and a whole trial layout beside them, for the same |
| 99 | /// answer. |
| 100 | pub fn of(recs: &[&Record]) |
| 101 | -> Outcome<Self> |
| 102 | { |
| 103 | let mut seq = Sequence::new(); |
| 104 | for rec in recs { |
| 105 | res!(seq.apply_record(rec)); |
| 106 | } |
| 107 | let cause = Causality::new(recs.iter().map(|r| (r.head.id(), r.parents()))); |
| 108 | let repo = match seq.render_with(&cause) { |
| 109 | Ok(r) => r, |
| 110 | Err(e) => return Err(err!(e, |
| 111 | "The {} operations of this history could not be rendered.", recs.len(); |
| 112 | Invalid, Data)), |
| 113 | }; |
| 114 | Ok(Self { repo }) |
| 115 | } |
| 116 | |
| 117 | /// Returns one file by identity, whether or not it is still live. |
| 118 | pub fn get(&self, file: OpId) |
| 119 | -> Option<&Rendered> |
| 120 | { |
| 121 | self.repo.file(file) |
| 122 | } |
| 123 | |
| 124 | /// Returns the live files, in ascending order of path and then of identity. |
| 125 | pub fn live(&self) -> Vec<&Rendered> { |
| 126 | self.repo.live() |
| 127 | } |
| 128 | |
| 129 | /// Decides where every live file goes in a working copy. |
| 130 | pub fn layout(&self) |
| 131 | -> Outcome<Layout> |
| 132 | { |
| 133 | Layout::of(&self.repo) |
| 134 | } |
| 135 | |
| 136 | /// Returns the bytes of every live file, by the path it materialises under. |
| 137 | pub fn contents(&self) |
| 138 | -> Outcome<BTreeMap<Vec<u8>, Vec<u8>>> |
| 139 | { |
| 140 | let layout = res!(self.layout()); |
| 141 | let mut out = BTreeMap::new(); |
| 142 | for (path, file) in &layout.at { |
| 143 | let view = match self.repo.file(*file) { |
| 144 | Some(v) => v, |
| 145 | None => return Err(err!( |
| 146 | "The layout places the file {}, which the render does not hold.", |
| 147 | file; |
| 148 | Bug, Missing)), |
| 149 | }; |
| 150 | out.insert(path.clone(), view.bytes().to_vec()); |
| 151 | } |
| 152 | Ok(out) |
| 153 | } |
| 154 | |
| 155 | /// Returns what every live file is, by the path it materialises under. |
| 156 | pub fn modes(&self) |
| 157 | -> Outcome<BTreeMap<Vec<u8>, Mode>> |
| 158 | { |
| 159 | let layout = res!(self.layout()); |
| 160 | let mut out = BTreeMap::new(); |
| 161 | for (path, file) in &layout.at { |
| 162 | let view = match self.repo.file(*file) { |
| 163 | Some(v) => v, |
| 164 | None => return Err(err!( |
| 165 | "The layout places the file {}, which the render does not hold.", |
| 166 | file; |
| 167 | Bug, Missing)), |
| 168 | }; |
| 169 | out.insert(path.clone(), view.mode()); |
| 170 | } |
| 171 | Ok(out) |
| 172 | } |
| 173 | } |
| 174 | |
| 175 | |
| 176 | /// One path two or more live files claim, and what was done about it. |
| 177 | #[derive(Clone, Debug)] |
| 178 | pub struct Clash { |
| 179 | /// The path they claim. |
| 180 | pub path: Vec<u8>, |
| 181 | /// The file that keeps it, which is the highest of them in op order. |
| 182 | pub kept: OpId, |
| 183 | /// The files that had to go elsewhere, each with the name it took. |
| 184 | pub moved: Vec<(OpId, Vec<u8>)>, |
| 185 | } |
| 186 | |
| 187 | |
| 188 | /// Where each live file goes in a working copy. |
| 189 | /// |
| 190 | /// # The clash policy |
| 191 | /// |
| 192 | /// Two live files may hold one path. When they do, the one whose identity is |
| 193 | /// highest in **op order** -- the Lamport counter first, the replica second, |
| 194 | /// which is the order every tie in the engine is broken by -- keeps the path, and |
| 195 | /// every other takes the derived name |
| 196 | /// |
| 197 | /// ```text |
| 198 | /// <path>.clash-r<replica>-<counter> |
| 199 | /// ``` |
| 200 | /// |
| 201 | /// where the replica and the counter are the losing *file's* identity, which is |
| 202 | /// the identity of the operation that created it. The name is therefore a |
| 203 | /// function of the operation set and of nothing else: two replicas holding the |
| 204 | /// same history lay out the same working copy, and the name a file takes does not |
| 205 | /// change when a third file is added or removed elsewhere. |
| 206 | #[derive(Default)] |
| 207 | pub struct Layout { |
| 208 | /// Every live file, by the path it materialises under. |
| 209 | pub at: BTreeMap<Vec<u8>, OpId>, |
| 210 | /// The clashes, in ascending order of path. |
| 211 | pub clashes: Vec<Clash>, |
| 212 | } |
| 213 | |
| 214 | impl Layout { |
| 215 | |
| 216 | /// Decides where every live file of a render goes. |
| 217 | pub fn of(repo: &Repo) |
| 218 | -> Outcome<Self> |
| 219 | { |
| 220 | let mut out = Self::default(); |
| 221 | // The paths more than one live file claims, which the render works out for |
| 222 | // itself: the repository's answer is that both files exist. |
| 223 | let contested: BTreeMap<Vec<u8>, Vec<OpId>> = repo.clashes() |
| 224 | .into_iter() |
| 225 | .map(|(path, ids)| (path.to_vec(), ids)) |
| 226 | .collect(); |
| 227 | for file in repo.live() { |
| 228 | let path = file.path().to_vec(); |
| 229 | let ids = match contested.get(&path) { |
| 230 | None => { |
| 231 | res!(out.place(path, file.file())); |
| 232 | continue; |
| 233 | }, |
| 234 | Some(ids) => ids, |
| 235 | }; |
| 236 | // Every file of a contested path is placed when the first of them is |
| 237 | // reached, so the second finds the work done. |
| 238 | if out.clashes.iter().any(|c| c.path == path) { |
| 239 | continue; |
| 240 | } |
| 241 | let kept = match ids.iter().copied().max_by_key(|id| OpOrder::of(id)) { |
| 242 | Some(id) => id, |
| 243 | None => return Err(err!( |
| 244 | "The render reports a clash at {:?} between no files.", shown(&path); |
| 245 | Bug, Missing)), |
| 246 | }; |
| 247 | let mut moved: Vec<(OpId, Vec<u8>)> = Vec::new(); |
| 248 | for id in ids { |
| 249 | if *id == kept { |
| 250 | continue; |
| 251 | } |
| 252 | let derived = derived_name(&path, *id); |
| 253 | res!(out.place(derived.clone(), *id)); |
| 254 | moved.push((*id, derived)); |
| 255 | } |
| 256 | res!(out.place(path.clone(), kept)); |
| 257 | out.clashes.push(Clash { path, kept, moved }); |
| 258 | } |
| 259 | out.clashes.sort_by(|a, b| a.path.cmp(&b.path)); |
| 260 | Ok(out) |
| 261 | } |
| 262 | |
| 263 | /// Gives a path to a file, refusing to give one path to two. |
| 264 | fn place(&mut self, path: Vec<u8>, file: OpId) |
| 265 | -> Outcome<()> |
| 266 | { |
| 267 | if let Some(seen) = self.at.insert(path.clone(), file) { |
| 268 | return Err(err!( |
| 269 | "The files {} and {} both materialise as {:?}; one of them is a file \ |
| 270 | whose derived clash name is another file's real path, and the working \ |
| 271 | copy cannot hold both.", seen, file, shown(&path); |
| 272 | Invalid, Data, Conflict)); |
| 273 | } |
| 274 | Ok(()) |
| 275 | } |
| 276 | |
| 277 | /// Returns the file that materialises under a path, if one does. |
| 278 | pub fn file_at(&self, path: &[u8]) |
| 279 | -> Option<OpId> |
| 280 | { |
| 281 | self.at.get(path).copied() |
| 282 | } |
| 283 | |
| 284 | /// Returns the path a file materialises under, if it is live. |
| 285 | pub fn path_of(&self, file: OpId) |
| 286 | -> Option<&[u8]> |
| 287 | { |
| 288 | self.at.iter().find(|(_, id)| **id == file).map(|(path, _)| path.as_slice()) |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | /// Returns the name a file takes when it has lost a clash. |
| 293 | pub fn derived_name(path: &[u8], file: OpId) -> Vec<u8> { |
| 294 | let mut out = path.to_vec(); |
| 295 | out.extend_from_slice(fmt!("{}{}-{}", CLASH_MARK, file.replica, file.counter).as_bytes()); |
| 296 | out |
| 297 | } |
| 298 | |
| 299 | |
| 300 | /// Builds the tree of the whole log, rendered. |
| 301 | pub fn whole(log: &OpLog) |
| 302 | -> Outcome<Tree> |
| 303 | { |
| 304 | let recs: Vec<&Record> = log.iter().collect(); |
| 305 | Tree::of(&recs) |
| 306 | } |
| 307 | |
| 308 | /// Returns the records a frontier was written in knowledge of, the frontier's |
| 309 | /// own included, in append order. |
| 310 | /// |
| 311 | /// The result is causally closed by construction, which is what rendering |
| 312 | /// requires: a set missing a parent cannot say what was concurrent with what. |
| 313 | /// An empty frontier is the state before anything at all, and yields nothing. |
| 314 | pub fn ancestry<'a>(log: &'a OpLog, frontier: &[OpId]) |
| 315 | -> Outcome<Vec<&'a Record>> |
| 316 | { |
| 317 | let mut want: BTreeSet<OpId> = BTreeSet::new(); |
| 318 | let mut stack: Vec<OpId> = frontier.to_vec(); |
| 319 | while let Some(next) = stack.pop() { |
| 320 | if !want.insert(next) { |
| 321 | continue; |
| 322 | } |
| 323 | let rec = match log.get(&next) { |
| 324 | Some(r) => r, |
| 325 | None => return Err(err!( |
| 326 | "The log does not hold the operation {}, which the history names.", |
| 327 | next; |
| 328 | Invalid, Input, Missing)), |
| 329 | }; |
| 330 | for p in rec.parents() { |
| 331 | stack.push(*p); |
| 332 | } |
| 333 | } |
| 334 | Ok(log.iter().filter(|r| want.contains(&r.head.id())).collect()) |
| 335 | } |
| 336 | |
| 337 | /// Builds the tree as it stood at a frontier, rendered. |
| 338 | pub fn at(log: &OpLog, frontier: &[OpId]) |
| 339 | -> Outcome<Tree> |
| 340 | { |
| 341 | let recs = res!(ancestry(log, frontier)); |
| 342 | Tree::of(&recs) |
| 343 | } |
| 344 | |
| 345 | |
| 346 | /// Returns the file one operation reached, where it reached one. |
| 347 | /// |
| 348 | /// Three questions were being asked separately, in two places, in two orders, |
| 349 | /// and this is the one question they were all trying to ask. They are asked in |
| 350 | /// this order because they are answered with decreasing certainty: |
| 351 | /// |
| 352 | /// 1. A lifecycle operation -- a delete, a rename, a mode change -- **names** the |
| 353 | /// file it acts on, so the record settles it and no render is needed. |
| 354 | /// 2. Anything that places content is associated with a file by the render, and |
| 355 | /// by nothing else: a splice names content, and which file that content is in |
| 356 | /// is a fact the layout of the whole repository decides. |
| 357 | /// 3. A file's creation is the file. It is normally answered by the render too, |
| 358 | /// since the origin anchor a creation mints is seeded into its own file, but |
| 359 | /// it is answered here as well so that a creation whose content the render |
| 360 | /// dropped is still named by the file it made rather than by nothing. |
| 361 | /// |
| 362 | /// `None` means the operation reached no file at all, which is what a mark is. |
| 363 | pub fn file_reached(repo: &Repo, rec: &Record) |
| 364 | -> Option<OpId> |
| 365 | { |
| 366 | if let Some(file) = rec.op.names_file() { |
| 367 | return Some(file); |
| 368 | } |
| 369 | if let Some(file) = repo.file_of(&rec.id()) { |
| 370 | return Some(file); |
| 371 | } |
| 372 | match &rec.op { |
| 373 | Op::FileCreate { .. } => Some(rec.id()), |
| 374 | _ => None, |
| 375 | } |
| 376 | } |
| 377 | |
| 378 | |
| 379 | #[cfg(test)] |
| 380 | mod tests { |
| 381 | use super::*; |
| 382 | |
| 383 | use oxedyne_fe2o3_ore::id::ReplicaId; |
| 384 | |
| 385 | |
| 386 | /// A file identifier. |
| 387 | fn fid(replica: u64, counter: u64) -> OpId { |
| 388 | OpId::new(ReplicaId::new(replica), counter) |
| 389 | } |
| 390 | |
| 391 | /// The derived name a clash produces names the losing file and nothing else, |
| 392 | /// so two replicas holding one history lay out one tree. |
| 393 | #[test] |
| 394 | fn a_clash_name_is_a_function_of_the_file() -> Outcome<()> { |
| 395 | assert_eq!( |
| 396 | derived_name(b"notes.md", fid(3, 17)), |
| 397 | b"notes.md.clash-r3-17".to_vec(), |
| 398 | ); |
| 399 | Ok(()) |
| 400 | } |
| 401 | } |