Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/mstage.rs

10.5 KiB, 1 run

created by r2848102244:87, 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//! Stage four, part two: randomised multi-file convergence.
2//!
3//! The caveat of `stage2.rs` applies here unchanged and should be read before
4//! anything is read into a pass: applying an operation is set insertion, so two
5//! replicas holding the same operations render the same bytes by construction.
6//! What this stage earns is the repository-wide conservation invariant of design
7//! note section 4.8 -- no byte rendered in two files, no live byte rendered
8//! nowhere -- over operation sets nobody hand-wrote, and the fact that the
9//! renderer resolves every anchor across files it was never told about.
10
11use crate::mrep::MRep;
12use crate::random::Rng;
13use crate::repo::{
14 CycleRule,
15 FileId,
16 Identity,
17 MOp,
18 Repo,
19 RepoRender,
20 Shared,
21};
22
23use std::collections::HashSet;
24
25use oxedyne_fe2o3_core::prelude::*;
26
27use crate::id::OpId;
28
29/// What one trial measured.
30#[derive(Clone, Debug)]
31pub struct MTrialOut {
32 /// Seed, so that a failure can be replayed.
33 pub seed: u64,
34 /// Operations generated.
35 pub ops: usize,
36 /// How many were moves, and how many of those crossed a file boundary.
37 pub moves: usize,
38 /// Moves whose source and destination were different files.
39 pub cross: usize,
40 /// Files created.
41 pub files: usize,
42 /// Files still live at the end.
43 pub live: usize,
44 /// Bytes rendered across the whole repository.
45 pub rendered: usize,
46 /// Bytes held back by deleted files.
47 pub withheld: usize,
48 /// Delivery orders checked.
49 pub orders: usize,
50 /// Moves flagged torn.
51 pub torn: usize,
52 /// Anchors demoted by the cycle rule.
53 pub demoted: usize,
54 /// Anchors demoted because their target had left the file.
55 pub off_file: usize,
56 /// Anchors dropped entirely.
57 pub dropped: usize,
58 /// Live paths held by more than one file.
59 pub clashes: usize,
60 /// Moves voided by a confinement rule.
61 pub confined: usize,
62 /// Moves that won a cross-file cycle outright.
63 pub won: usize,
64 /// Demotions that carried content over a file boundary.
65 pub crossed: usize,
66 /// Live files that render nothing.
67 pub emptied: usize,
68 /// Live files that render nothing although they hold content that has never
69 /// been deleted: a file emptied by the renderer rather than by an author.
70 pub drained: usize,
71 /// Moves that completed into a file their author did not name.
72 pub misplaced: usize,
73 /// Cycles the rule declined: no move to void, nothing crossing, or every
74 /// member informed.
75 pub declined: [usize; 3],
76}
77
78/// Counts the moves that rendered somewhere their author did not name.
79///
80/// A voided move is not counted -- it did not complete at all, and the flag for
81/// it says so -- and neither is a move whose content is dead. What is left is
82/// the measurement the whole exercise turns on: a block that landed in a file
83/// nobody chose.
84fn misplaced(repo: &Repo, r: &RepoRender, meta: &Shared) -> usize {
85 let meta = meta.borrow();
86 let mut n = 0usize;
87 for op in repo.ops() {
88 let id = op.id();
89 if !op.is_move() || r.flags.confined.iter().any(|(m, _, _)| *m == id) {
90 continue;
91 }
92 let want = match meta.intent.get(&id) {
93 Some(f) => *f,
94 None => continue,
95 };
96 if let MOp::Move { src, .. } = op {
97 let first = match src.first() {
98 Some(x) => crate::id::ContentId::new(x.op, x.from),
99 None => continue,
100 };
101 if let Some(got) = r.site.get(&first) {
102 if *got != want {
103 n += 1;
104 }
105 }
106 }
107 }
108 n
109}
110
111/// The live files a replica can see, in identity order.
112fn live_files(r: &MRep) -> Outcome<Vec<FileId>> {
113 let v = res!(r.view());
114 Ok(v.files.iter().filter(|f| f.live).map(|f| f.file).collect())
115}
116
117/// How long a file is, in the replica's view.
118fn len_of(r: &MRep, f: FileId) -> Outcome<usize> {
119 let v = res!(r.view());
120 Ok(v.file(f).map(|x| x.bytes.len()).unwrap_or(0))
121}
122
123/// Generates one random operation on a replica.
124fn random_op(r: &mut MRep, rng: &mut Rng, cross: &mut usize)
125 -> Outcome<Option<MOp>>
126{
127 let files = res!(live_files(r));
128 if files.is_empty() {
129 let path = fmt!("f{}", rng.below(4));
130 let (op, _) = res!(r.create(path.as_bytes()));
131 return Ok(Some(op));
132 }
133 let pick = rng.below(20);
134 // A file lifecycle change, occasionally.
135 if pick < 1 {
136 let path = fmt!("f{}", rng.below(4));
137 let (op, _) = res!(r.create(path.as_bytes()));
138 return Ok(Some(op));
139 }
140 if pick < 2 && files.len() > 1 {
141 let f = files[rng.below(files.len())];
142 return Ok(Some(res!(r.remove(f))));
143 }
144 if pick < 3 {
145 let f = files[rng.below(files.len())];
146 let path = fmt!("f{}", rng.below(4));
147 return Ok(Some(res!(r.rename(f, path.as_bytes()))));
148 }
149 let f = files[rng.below(files.len())];
150 let n = res!(len_of(r, f));
151 if pick < 10 || n < 4 {
152 let len = rng.between(1, 6);
153 let mut bytes = Vec::with_capacity(len);
154 for _ in 0..len {
155 bytes.push(b'a' + rng.below(26) as u8);
156 }
157 let at = rng.below(n + 1);
158 return Ok(Some(res!(r.insert(f, at, &bytes))));
159 }
160 if pick < 12 {
161 let len = rng.between(1, 4).min(n);
162 let at = rng.below(n - len + 1);
163 return Ok(Some(res!(r.delete(f, at, len))));
164 }
165 if pick < 14 {
166 let len = rng.between(1, 3).min(n);
167 let at = rng.below(n - len + 1);
168 let mut bytes = Vec::with_capacity(3);
169 for _ in 0..rng.between(1, 3) {
170 bytes.push(b'A' + rng.below(26) as u8);
171 }
172 return Ok(Some(res!(r.replace(f, at, len, &bytes))));
173 }
174 // A move, within one file or across two.
175 let len = rng.between(1, 8).min(n);
176 let at = rng.below(n - len + 1);
177 let to = files[rng.below(files.len())];
178 if to != f {
179 *cross += 1;
180 }
181 let dest = rng.below(res!(len_of(r, to)) + 1);
182 Ok(Some(res!(r.move_across(f, at, len, to, dest))))
183}
184
185/// Runs one randomised trial.
186pub fn trial(
187 seed: u64,
188 ident: Identity,
189 replicas: usize,
190 files: usize,
191 rounds: usize,
192 per_round: usize,
193)
194 -> Outcome<MTrialOut>
195{
196 trial_under(seed, ident, CycleRule::Demote, replicas, files, rounds, per_round)
197}
198
199/// Runs one randomised trial under a named cycle rule.
200#[allow(clippy::too_many_arguments)]
201pub fn trial_under(
202 seed: u64,
203 ident: Identity,
204 rule: CycleRule,
205 replicas: usize,
206 files: usize,
207 rounds: usize,
208 per_round: usize,
209)
210 -> Outcome<MTrialOut>
211{
212 let mut rng = Rng::new(seed);
213 let (mut reps, meta) = MRep::group(replicas as u32, ident, rule);
214 let mut all: Vec<MOp> = Vec::new();
215 for k in 0..files {
216 let path = fmt!("f{}", k);
217 let (op, id) = res!(reps[0].create(path.as_bytes()));
218 all.push(op);
219 all.push(res!(reps[0].insert(id, 0, b"alpha bravo charlie\n")));
220 }
221 for r in reps.iter_mut().skip(1) {
222 for op in &all {
223 r.recv(op.clone());
224 }
225 }
226
227 let mut outbox: Vec<(usize, MOp, HashSet<OpId>)> = Vec::new();
228 let mut moves = 0usize;
229 let mut cross = 0usize;
230 for _ in 0..rounds {
231 for i in 0..replicas {
232 for _ in 0..per_round {
233 if !rng.chance(3, 4) {
234 continue;
235 }
236 if let Some(op) = res!(random_op(&mut reps[i], &mut rng, &mut cross)) {
237 if op.is_move() {
238 moves += 1;
239 }
240 let deps: HashSet<OpId> = reps[i].repo.ops()
241 .iter()
242 .map(|o| o.id())
243 .filter(|d| *d != op.id())
244 .collect();
245 for j in 0..replicas {
246 if j != i {
247 outbox.push((j, op.clone(), deps.clone()));
248 }
249 }
250 all.push(op);
251 }
252 }
253 }
254 rng.shuffle(&mut outbox);
255 let take = rng.below(outbox.len() + 1);
256 let mut batch: Vec<(usize, MOp, HashSet<OpId>)> = outbox.drain(..take).collect();
257 deliver(&mut reps, &mut batch);
258 outbox.extend(batch);
259 }
260 rng.shuffle(&mut outbox);
261 deliver(&mut reps, &mut outbox);
262 if !outbox.is_empty() {
263 return Err(err!(
264 "Seed {}: {} operations were never deliverable.",
265 seed, outbox.len(); Bug));
266 }
267
268 // Every replica renders the same repository.
269 let first = res!(reps[0].view());
270 for (i, r) in reps.iter().enumerate().skip(1) {
271 let v = res!(r.view());
272 if v.listing() != first.listing() {
273 return Err(err!(
274 "Seed {}: replica 0 and replica {} disagree:\n {}\n {}",
275 seed, i, first.listing(), v.listing(); Mismatch, Data));
276 }
277 }
278
279 // Conservation, over the whole repository.
280 if first.flags.duplicated != 0 {
281 return Err(err!(
282 "Seed {}: {} bytes rendered in more than one file.",
283 seed, first.flags.duplicated; Mismatch, Data));
284 }
285 if first.stats.lost != 0 {
286 return Err(err!(
287 "Seed {}: {} live bytes rendered nowhere.",
288 seed, first.stats.lost; Mismatch, Data));
289 }
290 if !first.flags.orphan.is_empty() {
291 return Err(err!(
292 "Seed {}: {} slots belong to no file.",
293 seed, first.flags.orphan.len(); Mismatch, Data));
294 }
295
296 // A shuffled operation vector renders identically, flags included.
297 let mut rng = Rng::new(seed ^ 0xF11E_1DEA);
298 let mut shuffled = all.clone();
299 let mut orders = 1usize;
300 for _ in 0..8 {
301 rng.shuffle(&mut shuffled);
302 let mut repo = Repo::with_rule(ident, rule, meta.clone());
303 for op in &shuffled {
304 repo.apply(op.clone());
305 }
306 let v = res!(repo.render());
307 orders += 1;
308 if v.listing() != first.listing() {
309 return Err(err!(
310 "Seed {}: a shuffled operation vector rendered differently:\n \
311 {}\n {}", seed, first.listing(), v.listing(); Mismatch, Data));
312 }
313 }
314
315 // What was emptied, and what was emptied although nobody deleted it.
316 let emptied = first.live().iter().filter(|f| f.bytes.is_empty()).count();
317 // The same repository with the moves taken out, which is where every byte
318 // was written. A file with content there and none here has been emptied by
319 // moving rather than by deleting, whoever's doing that was.
320 let mut home = Repo::with_rule(ident, rule, meta.clone());
321 for op in all.iter().filter(|o| !o.is_move()) {
322 home.apply(op.clone());
323 }
324 let home = res!(home.render());
325 let drained = first.live()
326 .iter()
327 .filter(|f| f.bytes.is_empty())
328 .filter(|f| home.file(f.file).map(|h| !h.bytes.is_empty()).unwrap_or(false))
329 .count();
330
331 Ok(MTrialOut {
332 seed,
333 ops: all.len(),
334 moves,
335 cross,
336 files: first.files.len(),
337 live: first.live().len(),
338 rendered: first.stats.rendered,
339 withheld: first.stats.withheld,
340 orders,
341 torn: first.flags.torn.len(),
342 demoted: first.flags.demoted.len(),
343 off_file: first.flags.off_file.len(),
344 dropped: first.flags.dropped.len(),
345 clashes: first.flags.path_clash.len(),
346 confined: first.flags.confined.len(),
347 won: first.flags.won.len(),
348 crossed: first.flags.crossed.len(),
349 emptied,
350 drained,
351 misplaced: misplaced(&reps[0].repo, &first, &meta),
352 declined: first.flags.declined,
353 })
354}
355
356/// Delivers everything in the batch that is causally ready, repeatedly.
357fn deliver(reps: &mut [MRep], batch: &mut Vec<(usize, MOp, HashSet<OpId>)>) {
358 loop {
359 let mut moved = false;
360 let mut held: Vec<(usize, MOp, HashSet<OpId>)> = Vec::new();
361 for (j, op, deps) in batch.drain(..) {
362 if deps.iter().all(|d| reps[j].repo.has(d)) {
363 reps[j].recv(op);
364 moved = true;
365 } else {
366 held.push((j, op, deps));
367 }
368 }
369 *batch = held;
370 if !moved || batch.is_empty() {
371 return;
372 }
373 }
374}