Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/csweep.rs

10.3 KiB, 1 run

created by r2848102244:73, 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 five, part three: a sweep that plants cycles on purpose.
2//!
3//! The general sweep of `mstage.rs` moves uniformly at random between three
4//! small files, which produces cycles constantly and everything else constantly
5//! too, so the rules come out within a few per cent of each other and the
6//! difference is buried. This one generates the hazard instead of waiting for
7//! it: *k* files, *k* replicas, each moving a random block of one file into the
8//! next, which closes a loop whenever the destinations land inside the sources.
9//!
10//! The operation set is generated **once** and then rendered under every rule,
11//! so the comparison is exact: the same authors, the same intentions, the same
12//! bytes, and nothing varying but what the renderer does with the loop.
13
14use crate::id::ContentId;
15use crate::mrep::MRep;
16use crate::random::Rng;
17use crate::repo::{
18 CycleRule,
19 FileId,
20 Identity,
21 MOp,
22 Repo,
23 Shared,
24};
25
26use std::collections::BTreeSet;
27
28use oxedyne_fe2o3_core::prelude::*;
29
30/// What one planted trial measured, under one rule.
31#[derive(Clone, Default, Debug)]
32pub struct Planted {
33 /// Trials in which the anchor graph actually closed a loop.
34 pub cycles: usize,
35 /// Files that held content and render none, the content having moved out.
36 pub drained: usize,
37 /// Of those, the files whose content left for somewhere nobody named: a file
38 /// emptied by the renderer rather than by an author.
39 pub unasked: usize,
40 /// Planted moves that completed into a file their author did not name.
41 pub misplaced: usize,
42 /// Planted moves voided by a confinement rule.
43 pub voided: usize,
44 /// Planted moves that completed into the file their author named.
45 pub landed: usize,
46 /// Origins demoted.
47 pub demoted: usize,
48 /// Bytes rendered twice, which must be zero.
49 pub duplicated: usize,
50 /// Live bytes rendered nowhere, which must be zero.
51 pub lost: usize,
52 /// Concurrent edits inside a cycling block that did not render.
53 pub edits_lost: usize,
54 /// Delivery orders whose render disagreed, which must be zero.
55 pub diverged: usize,
56 /// Trials with no cycle in them where the rule rendered something other
57 /// than the status quo, which must be zero: a rule may only act on a cycle.
58 pub meddled: usize,
59}
60
61impl Planted {
62 /// Adds one trial's counts.
63 pub fn add(&mut self, other: &Planted) {
64 self.cycles += other.cycles;
65 self.drained += other.drained;
66 self.unasked += other.unasked;
67 self.misplaced += other.misplaced;
68 self.voided += other.voided;
69 self.landed += other.landed;
70 self.demoted += other.demoted;
71 self.duplicated += other.duplicated;
72 self.lost += other.lost;
73 self.edits_lost += other.edits_lost;
74 self.diverged += other.diverged;
75 self.meddled += other.meddled;
76 }
77}
78
79/// One planted operation set: the whole history, and what its authors meant.
80struct Plan {
81 /// Every operation, in the order it was authored.
82 ops: Vec<MOp>,
83 /// The files, in creation order.
84 files: Vec<FileId>,
85 /// The planted moves, each with the file its author aimed it at and the
86 /// first content id of the block it moved.
87 moves: Vec<(OpId, FileId, ContentId)>,
88 /// The content ids of every byte inserted into a cycling block.
89 edits: Vec<ContentId>,
90 /// The metadata table the replicas shared.
91 meta: Shared,
92}
93
94use crate::id::OpId;
95
96/// Builds one planted operation set.
97///
98/// Generated under the status quo, and rendered later under every rule. A
99/// replica sees only the initial files while it authors its move, so what it
100/// authors cannot depend on the rule -- which is what makes the comparison
101/// exact rather than approximate.
102fn plan(seed: u64, rng: &mut Rng) -> Outcome<Plan> {
103 let k = rng.between(2, 4);
104 let (mut reps, meta) = MRep::group((k + 1) as u32, Identity::Derived, CycleRule::Demote);
105 let mut ops: Vec<MOp> = Vec::new();
106 let mut files: Vec<FileId> = Vec::new();
107 let mut texts: Vec<Vec<u8>> = Vec::new();
108 {
109 let origin = &mut reps[0];
110 for i in 0..k {
111 let path = fmt!("f{}", i);
112 let (op, id) = res!(origin.create(path.as_bytes()));
113 ops.push(op);
114 files.push(id);
115 let len = rng.between(4, 10);
116 let mut text: Vec<u8> = Vec::with_capacity(len + 1);
117 for _ in 0..len {
118 text.push(b'a' + rng.below(26) as u8);
119 }
120 text.push(b'\n');
121 ops.push(res!(origin.insert(id, 0, &text)));
122 texts.push(text);
123 }
124 }
125 for i in 1..reps.len() {
126 for op in ops.clone() {
127 reps[i].recv(op);
128 }
129 }
130
131 // Replica i moves a block of file i into file i+1, at a random index. The
132 // loop closes when every destination falls inside the next author's source,
133 // which it does often and not always; the trials where it does not are the
134 // control.
135 let mut moves: Vec<(OpId, FileId, ContentId)> = Vec::new();
136 let mut ranges: Vec<(usize, usize)> = Vec::new();
137 for i in 0..k {
138 let n = texts[i].len();
139 let len = rng.between(1, n);
140 let at = rng.below(n - len + 1);
141 ranges.push((at, len));
142 }
143 for i in 0..k {
144 let to = (i + 1) % k;
145 let (at, len) = ranges[i];
146 let dest = rng.below(texts[to].len() + 1);
147 let op = res!(reps[i + 1].move_across(files[i], at, len, files[to], dest));
148 let first = match &op {
149 MOp::Move { src, .. } => match src.first() {
150 Some(r) => ContentId::new(r.op, r.from),
151 None => return Err(err!("A planted move named nothing."; Bug)),
152 },
153 _ => return Err(err!("A planted move is not a move."; Bug)),
154 };
155 moves.push((op.id(), files[to], first));
156 ops.push(op);
157 }
158
159 // Half the time, somebody edits inside one of the cycling blocks, having
160 // seen none of the moves.
161 let mut edits: Vec<ContentId> = Vec::new();
162 if rng.chance(1, 2) {
163 let i = rng.below(k);
164 let (at, len) = ranges[i];
165 let mut fresh = MRep::with_rule(
166 (k + 9) as u32, Identity::Derived, CycleRule::Demote, meta.clone());
167 for op in ops.iter().take(2 * k) {
168 fresh.recv(op.clone());
169 }
170 let op = res!(fresh.insert(files[i], at + len.min(1), b"!"));
171 if let MOp::Splice { id, .. } = &op {
172 edits.push(ContentId::new(*id, 0));
173 }
174 ops.push(op);
175 }
176
177 // A quarter of the time, one author receives the others and moves its own
178 // block again: the supersession case, where a rule must not void the second
179 // move for being in a cycle with the first.
180 if rng.chance(1, 4) {
181 let i = rng.below(k);
182 let to = (i + 1) % k;
183 for op in ops.clone() {
184 reps[i + 1].recv(op);
185 }
186 let n = res!(reps[i + 1].file_len(files[i]));
187 if n > 0 {
188 let (at, len) = ranges[i];
189 let at = at.min(n.saturating_sub(1));
190 let len = len.min(n - at);
191 let dest = res!(reps[i + 1].file_len(files[to]));
192 let op = res!(reps[i + 1].move_across(files[i], at, len, files[to], dest));
193 if let MOp::Move { src, .. } = &op {
194 if let Some(r) = src.first() {
195 moves.push((op.id(), files[to], ContentId::new(r.op, r.from)));
196 }
197 }
198 ops.push(op);
199 }
200 }
201 let _ = seed;
202 Ok(Plan { ops, files, moves, edits, meta })
203}
204
205/// Renders one planted operation set under one rule and measures the outcome.
206fn measure(p: &Plan, rule: CycleRule, rng: &mut Rng) -> Outcome<(Planted, String)> {
207 let mut repo = Repo::with_rule(Identity::Derived, rule, p.meta.clone());
208 for op in &p.ops {
209 repo.apply(op.clone());
210 }
211 let r = res!(repo.render());
212
213 // The same history with the moves taken out, which is where every byte was
214 // written and how a file that has been emptied by moving is told from one
215 // that was empty anyway.
216 let mut home = Repo::with_rule(Identity::Derived, rule, p.meta.clone());
217 for op in p.ops.iter().filter(|o| !o.is_move()) {
218 home.apply(op.clone());
219 }
220 let home = res!(home.render());
221
222 let mut out = Planted::default();
223 let cycled = !r.flags.demoted.is_empty() || !r.flags.confined.is_empty();
224 if cycled {
225 out.cycles = 1;
226 }
227 out.demoted = r.flags.demoted.len();
228 out.duplicated = r.flags.duplicated;
229 out.lost = r.stats.lost;
230 let voided: BTreeSet<OpId> = r.flags.confined.iter().map(|(m, _, _)| *m).collect();
231 let mut wrong: Vec<ContentId> = Vec::new();
232 for (id, want, first) in &p.moves {
233 if voided.contains(id) {
234 out.voided += 1;
235 continue;
236 }
237 match r.site.get(first) {
238 Some(got) if got == want => out.landed += 1,
239 Some(_) => {
240 out.misplaced += 1;
241 wrong.push(*first);
242 },
243 None => (),
244 }
245 }
246 for f in &p.files {
247 let held = home.file(*f).map(|x| !x.bytes.is_empty()).unwrap_or(false);
248 let now = r.file(*f).map(|x| x.bytes.is_empty()).unwrap_or(true);
249 if !held || !now {
250 continue;
251 }
252 out.drained += 1;
253 // The file was emptied. Was it emptied by somebody, or by the renderer?
254 // It was the renderer's doing if any of the blocks that left it went
255 // somewhere nobody named.
256 let born_here = |cid: &ContentId| home.file(*f)
257 .map(|x| x.prov.contains(cid))
258 .unwrap_or(false);
259 if wrong.iter().any(born_here) {
260 out.unasked += 1;
261 }
262 }
263 for cid in &p.edits {
264 let shown = r.files.iter().any(|f| f.prov.contains(cid));
265 if !shown {
266 out.edits_lost += 1;
267 }
268 }
269
270 // Eight shuffles of the operation vector, which must render identically.
271 let mut shuffled = p.ops.clone();
272 for _ in 0..8 {
273 rng.shuffle(&mut shuffled);
274 let mut other = Repo::with_rule(Identity::Derived, rule, p.meta.clone());
275 for op in &shuffled {
276 other.apply(op.clone());
277 }
278 let v = res!(other.render());
279 if v.listing() != r.listing() {
280 out.diverged += 1;
281 }
282 }
283 Ok((out, r.listing()))
284}
285
286/// Runs `trials` planted trials and returns one row per rule, in the order of
287/// [`crate::cyc::RULES`].
288pub fn sweep(trials: u64, rules: &[CycleRule]) -> Outcome<Vec<Planted>> {
289 let mut totals: Vec<Planted> = rules.iter().map(|_| Planted::default()).collect();
290 for seed in 0..trials {
291 let mut rng = Rng::new(0xC0FFEE ^ seed);
292 let p = res!(plan(seed, &mut rng));
293 // The status quo decides whether this trial closed a loop at all, so
294 // that every rule is scored over the same trials.
295 let mut shuffler = Rng::new(seed ^ 0xBEEF);
296 let (base, base_text) = res!(measure(&p, CycleRule::Demote, &mut shuffler));
297 let cycled = base.cycles > 0;
298 for (i, rule) in rules.iter().enumerate() {
299 let mut shuffler = Rng::new(seed ^ 0xBEEF);
300 let (one, text) = res!(measure(&p, *rule, &mut shuffler));
301 if !cycled {
302 // A trial with no cycle in it is the control: every rule must
303 // render exactly what the status quo renders.
304 let mut ctl = Planted::default();
305 ctl.diverged = one.diverged;
306 ctl.duplicated = one.duplicated;
307 ctl.lost = one.lost;
308 ctl.edits_lost = one.edits_lost;
309 if text != base_text {
310 ctl.meddled = 1;
311 }
312 totals[i].add(&ctl);
313 continue;
314 }
315 totals[i].add(&one);
316 }
317 }
318 Ok(totals)
319}