Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/stage2.rs

8.5 KiB, 1 run

created by r2848102244:97, 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 two: randomised convergence over simulated replicas.
2//!
3//! Read the caveat in the results note before reading anything into a pass.
4//! Applying an operation in this prototype is set insertion, so two replicas
5//! that hold the same operation set are guaranteed the same render by
6//! construction and the delivery-order check is close to vacuous. What the
7//! stage does earn is the conservation invariant -- every byte ever created,
8//! less the tombstoned ones, appears exactly once -- and the fact that the
9//! renderer neither panics nor fails to resolve an anchor over a wide spread of
10//! operation sets.
11
12use crate::doc::{
13 Bind,
14 Doc,
15 Mode,
16};
17use crate::id::OpId;
18use crate::op::Op;
19use crate::random::Rng;
20use crate::replica::Replica;
21
22use std::collections::HashSet;
23
24use oxedyne_fe2o3_core::prelude::*;
25
26/// The opening text every trial starts from.
27const OPENER: &[u8] = b"alpha bravo charlie delta echo foxtrot\n";
28
29/// What one trial measured.
30#[derive(Clone, Debug)]
31pub struct TrialOut {
32 /// Seed, so that a failure can be replayed.
33 pub seed: u64,
34 /// Operations generated, including the opening splice.
35 pub ops: usize,
36 /// How many of those were moves.
37 pub moves: usize,
38 /// Length of the converged render.
39 pub len: usize,
40 /// Delivery orders checked.
41 pub orders: usize,
42 /// Moves flagged torn.
43 pub torn: usize,
44 /// Anchors demoted by the cycle rule.
45 pub demoted: usize,
46 /// Anchors dropped because demotion did not break the cycle.
47 pub dropped: usize,
48}
49
50/// Generates one random operation on a replica.
51fn random_op(r: &mut Replica, rng: &mut Rng, moves: bool) -> Outcome<Option<Op>> {
52 let v = res!(r.view());
53 let n = v.prov.len();
54 let pick = rng.below(if moves { 10 } else { 7 });
55 if pick < 4 || n < 4 {
56 // Insert a short run.
57 let len = rng.between(1, 6);
58 let mut bytes = Vec::with_capacity(len);
59 for _ in 0..len {
60 bytes.push(b'a' + rng.below(26) as u8);
61 }
62 let at = rng.below(n + 1);
63 return Ok(Some(res!(r.insert(at, &bytes))));
64 }
65 if pick < 6 {
66 // Delete a short run.
67 let len = rng.between(1, 4).min(n);
68 let at = rng.below(n - len + 1);
69 return Ok(Some(res!(r.delete(at, len))));
70 }
71 if pick < 7 {
72 // Replace a short run.
73 let len = rng.between(1, 3).min(n);
74 let at = rng.below(n - len + 1);
75 let mut bytes = Vec::with_capacity(3);
76 for _ in 0..rng.between(1, 3) {
77 bytes.push(b'A' + rng.below(26) as u8);
78 }
79 return Ok(Some(res!(r.replace(at, len, &bytes))));
80 }
81 // Move a run.
82 let len = rng.between(1, 8).min(n);
83 let at = rng.below(n - len + 1);
84 let dest = rng.below(n + 1);
85 Ok(Some(res!(r.move_range(at, len, dest))))
86}
87
88/// Generates the operation set of a trial without checking anything, so that a
89/// failing seed can be picked apart.
90pub fn collect(
91 seed: u64,
92 mode: Mode,
93 bind: Bind,
94 replicas: usize,
95 rounds: usize,
96 per_round: usize,
97 moves: bool,
98)
99 -> Outcome<Vec<Op>>
100{
101 let (_, all, _) = res!(generate(seed, mode, bind, replicas, rounds, per_round, moves));
102 Ok(all)
103}
104
105/// Runs the replicas, generating and delivering operations.
106fn generate(
107 seed: u64,
108 mode: Mode,
109 bind: Bind,
110 replicas: usize,
111 rounds: usize,
112 per_round: usize,
113 moves: bool,
114)
115 -> Outcome<(Vec<Replica>, Vec<Op>, usize)>
116{
117 let mut rng = Rng::new(seed);
118 let mut reps: Vec<Replica> = (0..replicas)
119 .map(|i| Replica::with_bind(i as u32, mode, bind))
120 .collect();
121 let opener = res!(reps[0].insert(0, OPENER));
122 for r in reps.iter_mut().skip(1) {
123 r.recv(opener.clone());
124 }
125 let mut all: Vec<Op> = vec![opener];
126 let mut outbox: Vec<(usize, Op, HashSet<OpId>)> = Vec::new();
127 let mut move_count = 0usize;
128
129 for _ in 0..rounds {
130 for i in 0..replicas {
131 for _ in 0..per_round {
132 if !rng.chance(3, 4) {
133 continue;
134 }
135 if let Some(op) = res!(random_op(&mut reps[i], &mut rng, moves)) {
136 if op.is_move() {
137 move_count += 1;
138 }
139 // An operation's causal dependencies are whatever its
140 // author had applied when it generated the operation.
141 let deps: HashSet<OpId> = reps[i].doc.seen()
142 .into_iter()
143 .filter(|d| *d != op.id())
144 .collect();
145 for j in 0..replicas {
146 if j != i {
147 outbox.push((j, op.clone(), deps.clone()));
148 }
149 }
150 all.push(op);
151 }
152 }
153 }
154 // Deliver a random share of the outbox, in a random order but never
155 // ahead of an operation's causal dependencies.
156 rng.shuffle(&mut outbox);
157 let take = rng.below(outbox.len() + 1);
158 let mut batch: Vec<(usize, Op, HashSet<OpId>)> = outbox.drain(..take).collect();
159 deliver(&mut reps, &mut batch);
160 outbox.extend(batch);
161 }
162 // Deliver everything that is left.
163 rng.shuffle(&mut outbox);
164 deliver(&mut reps, &mut outbox);
165 if !outbox.is_empty() {
166 return Err(err!(
167 "Seed {}: {} operations were never deliverable.",
168 seed, outbox.len(); Bug));
169 }
170 Ok((reps, all, move_count))
171}
172
173/// Runs one randomised trial.
174pub fn trial(
175 seed: u64,
176 mode: Mode,
177 bind: Bind,
178 replicas: usize,
179 rounds: usize,
180 per_round: usize,
181 moves: bool,
182)
183 -> Outcome<TrialOut>
184{
185 let (reps, all, move_count) = res!(
186 generate(seed, mode, bind, replicas, rounds, per_round, moves));
187 let mut rng = Rng::new(seed ^ 0xDEAD_BEEF);
188
189 // Every replica must now render the same bytes.
190 let first = res!(reps[0].view());
191 for (i, r) in reps.iter().enumerate().skip(1) {
192 let v = res!(r.view());
193 if v.bytes != first.bytes {
194 return Err(err!(
195 "Seed {}: replica 0 and replica {} disagree:\n {:?}\n {:?}",
196 seed, i, first.text(), v.text(); Mismatch, Data));
197 }
198 }
199
200 // Conservation: every byte ever created, less the tombstoned ones, appears
201 // exactly once.
202 let expect = first.stats.atom_bytes as i64 - first.stats.dead_entries as i64;
203 if first.bytes.len() as i64 != expect || first.flags.duplicated != 0 {
204 return Err(err!(
205 "Seed {}: rendered {} bytes against {} live, {} duplicated.",
206 seed, first.bytes.len(), expect, first.flags.duplicated; Mismatch, Data));
207 }
208
209 // A shuffled operation vector must render identically.
210 let mut orders = 1usize;
211 let mut shuffled = all.clone();
212 for _ in 0..8 {
213 rng.shuffle(&mut shuffled);
214 let mut d = Doc::with_bind(mode, bind);
215 for op in &shuffled {
216 d.apply(op.clone());
217 }
218 let v = res!(d.render());
219 orders += 1;
220 if v.bytes != first.bytes {
221 return Err(err!(
222 "Seed {}: a shuffled operation vector rendered differently:\n \
223 {:?}\n {:?}", seed, first.text(), v.text(); Mismatch, Data));
224 }
225 }
226
227 Ok(TrialOut {
228 seed,
229 ops: all.len(),
230 moves: move_count,
231 len: first.bytes.len(),
232 orders,
233 torn: first.flags.torn.len(),
234 demoted: first.flags.demoted.len(),
235 dropped: first.flags.dropped.len(),
236 })
237}
238
239/// Delivers everything in the batch that is causally ready, repeatedly, and
240/// leaves the rest in place.
241fn deliver(reps: &mut [Replica], batch: &mut Vec<(usize, Op, HashSet<OpId>)>) {
242 loop {
243 let mut moved = false;
244 let mut held: Vec<(usize, Op, HashSet<OpId>)> = Vec::new();
245 for (j, op, deps) in batch.drain(..) {
246 if deps.iter().all(|d| reps[j].doc.has(d)) {
247 reps[j].recv(op);
248 moved = true;
249 } else {
250 held.push((j, op, deps));
251 }
252 }
253 *batch = held;
254 if !moved || batch.is_empty() {
255 return;
256 }
257 }
258}
259
260/// Runs a small trial and checks every permutation of the delivery order.
261pub fn exhaustive(
262 seed: u64,
263 mode: Mode,
264 bind: Bind,
265 replicas: usize,
266 extra_ops: usize,
267 moves: bool,
268)
269 -> Outcome<usize>
270{
271 let mut rng = Rng::new(seed);
272 let mut reps: Vec<Replica> = (0..replicas)
273 .map(|i| Replica::with_bind(i as u32, mode, bind))
274 .collect();
275 let opener = res!(reps[0].insert(0, OPENER));
276 for r in reps.iter_mut().skip(1) {
277 r.recv(opener.clone());
278 }
279 let mut all: Vec<Op> = vec![opener];
280 for k in 0..extra_ops {
281 let i = k % replicas;
282 if let Some(op) = res!(random_op(&mut reps[i], &mut rng, moves)) {
283 for j in 0..replicas {
284 if j != i {
285 reps[j].recv(op.clone());
286 }
287 }
288 all.push(op);
289 }
290 }
291 let mut idx: Vec<usize> = (0..all.len()).collect();
292 let mut orders: Vec<Vec<usize>> = Vec::new();
293 permute(&mut idx, 0, &mut orders);
294 let mut first: Option<Vec<u8>> = None;
295 for ord in &orders {
296 let mut d = Doc::with_bind(mode, bind);
297 for i in ord {
298 d.apply(all[*i].clone());
299 }
300 let v = res!(d.render());
301 match &first {
302 None => first = Some(v.bytes),
303 Some(f) => {
304 if *f != v.bytes {
305 return Err(err!(
306 "Seed {}: permutation {:?} rendered differently.",
307 seed, ord; Mismatch, Data));
308 }
309 },
310 }
311 }
312 Ok(orders.len())
313}
314
315/// Generates every permutation of `idx`.
316fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
317 if k == idx.len() {
318 out.push(idx.clone());
319 return;
320 }
321 for i in k..idx.len() {
322 idx.swap(k, i);
323 permute(idx, k + 1, out);
324 idx.swap(k, i);
325 }
326}