1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
//! What a store makes of histories, in a format every release of continuum keeps
//! (`continuum-party judge`; `docs/federation-tests.md`, Against released revisions), so
//! that a release judges the same histories as an earlier one, under every revision that
//! one knows. Never change the format: an earlier release prints it too.
//!
//! In, a history after another: `case <label>`, `root <hex>`, the bytes of its root, then
//! `event <hex>` for each of its events, in the order offered.
//!
//! Out, for each: `case <label>`; then `root none` where the root reads as none here, as
//! one of a revision this continuum doesn't know; else `became <ID> <kind>` for each event
//! in the order offered, what became of it by kind (never a refusal's words, which may
//! change), and `reads <JSON>`, what the store reads after: its checkpoint's ID, the
//! current version's hash, the values at places, the members, and the event it stopped
//! at.
use std::collections::BTreeMap;
use std::fmt::Write as _;
use super::fold::Federation;
use super::store::Id;
use super::store::memory::{Refusal, Store};
/// A history: its label, its root, and its events in the order offered.
pub(crate) struct History {
pub(crate) label: String,
pub(crate) root: Vec<u8>,
pub(crate) events: Vec<Vec<u8>>,
}
/// `histories` as `judge` reads them.
pub(crate) fn spelled(histories: &[History]) -> String {
let mut text = String::new();
for history in histories {
let _ = writeln!(text, "case {}", history.label);
let _ = writeln!(text, "root {}", hex(&history.root));
for event in &history.events {
let _ = writeln!(text, "event {}", hex(event));
}
}
text
}
/// The histories `text` spells (`spelled`).
pub(crate) fn read(text: &str) -> Result<Vec<History>, String> {
let mut histories: Vec<History> = Vec::new();
for line in text.lines() {
let (word, rest) = line.split_once(' ').unwrap_or((line, ""));
let bytes = || unhex(rest).ok_or_else(|| format!("no hex: {line:?}"));
match (word, histories.last_mut()) {
("case", _) => histories.push(History {
label: rest.to_owned(),
root: Vec::new(),
events: Vec::new(),
}),
("root", Some(history)) => history.root = bytes()?,
("event", Some(history)) => history.events.push(bytes()?),
_ => return Err(format!("no line of a history: {line:?}")),
}
}
Ok(histories)
}
fn hex(bytes: &[u8]) -> String {
bytes.iter().map(|byte| format!("{byte:02x}")).collect()
}
fn unhex(text: &str) -> Option<Vec<u8>> {
if !text.len().is_multiple_of(2) || !text.bytes().all(|byte| byte.is_ascii_hexdigit()) {
return None;
}
(0..text.len())
.step_by(2)
.map(|at| u8::from_str_radix(text.get(at..at + 2)?, 16).ok())
.collect()
}
/// What a store makes of `histories`, as the format says.
pub(crate) fn judge(histories: &[History]) -> String {
let mut text = String::new();
for history in histories {
let _ = writeln!(text, "case {}", history.label);
let Ok(mut store) = Store::<Federation>::new(history.root.clone(), Vec::new()) else {
text.push_str("root none\n");
continue;
};
for event in &history.events {
store.offer(event.clone());
}
for event in &history.events {
let id = Id::of(event);
let _ = writeln!(text, "became {id} {}", became(&store, &id));
}
let _ = writeln!(text, "reads {}", reads(&store));
}
text
}
/// What became of `id` in `store`, by kind.
fn became(store: &Store<Federation>, id: &Id) -> &'static str {
if store.stopped().is_some_and(|(at, ..)| at == id) {
return "stopped at";
}
if store.held_back().iter().any(|(held, _)| held == id) {
return "held back";
}
if store.holds(id) {
return "taken";
}
if store.get(id).is_some() {
return "kept";
}
match store.refusal(id) {
Some(Refusal::None) => "refused: none",
Some(Refusal::Judged(_)) => "refused: judged",
Some(Refusal::BuiltOn(_)) => "refused: built on a refused one",
Some(Refusal::NotAbove) => "refused: not above the checkpoint",
Some(Refusal::Own) => "refused: its own",
Some(Refusal::Dropped) => "refused: dropped",
None if store.is_waiting(id) => "waiting",
None => "gone with a move",
}
}
/// What `store` reads, a line of JSON.
fn reads(store: &Store<Federation>) -> String {
let state = store.state();
let values: BTreeMap<String, String> = state
.values()
.into_iter()
.map(|(path, value)| (path, String::from_utf8_lossy(&value.bytes()).into_owned()))
.collect();
serde_json::json!({
"checkpoint": Id::of(store.checkpoint()).to_string(),
"current": state.current().hash.to_string(),
"values": values,
"members": state.members(),
"stopped": store.stopped().map(|(id, ..)| id.to_string()),
})
.to_string()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::federation::attacks;
use crate::federation::harness::{self, Party, Spec};
use crate::federation::properties::{self, Kind};
use crate::federation::revision::Revision;
use crate::testrand::Rng;
/// Of each revision and kind, how many seeds' histories are written, times
/// `CONTINUUM_TEST_CASES`.
const CASES: u64 = 25;
/// Writes the histories to judge to the file `CONTINUUM_HISTORIES` names
/// (`scripts/federation-check`): of each revision this continuum knows and each kind
/// the properties generate, the histories of `CASES` seeds from `CONTINUUM_TEST_SEED`
/// on; and those the attack tests offer, where nothing but offers made them.
#[test]
#[ignore = "writes the file CONTINUUM_HISTORIES names: run by scripts/federation-check"]
fn write_histories() {
let path = std::env::var("CONTINUUM_HISTORIES").expect("CONTINUUM_HISTORIES: a file");
let env = |name: &str| {
std::env::var(name)
.ok()
.and_then(|value| value.parse::<u64>().ok())
};
let first = env("CONTINUUM_TEST_SEED").unwrap_or(0);
let cases = CASES.saturating_mul(env("CONTINUUM_TEST_CASES").unwrap_or(1));
let mut histories = Vec::new();
for revision in Revision::known() {
for adversary in [false, true] {
for checkpoints in [false, true] {
for unread in [false, true] {
let kind = Kind {
adversary,
checkpoints,
unread,
};
for seed in first..first.saturating_add(cases) {
let generated =
properties::generate_at(&mut Rng::new(seed), kind, Some(revision));
histories.push(History {
label: format!("{revision}, seed {seed}, {kind:?}"),
root: generated.root,
events: generated.events,
});
}
}
}
}
}
for (name, test) in attacks::TESTS {
for (n, recorded) in attacks::recording(*test).into_iter().enumerate() {
if recorded.offers_only {
histories.push(History {
label: format!("{name}, store {n}"),
root: recorded.root,
events: recorded.events,
});
}
}
}
std::fs::write(&path, spelled(&histories)).expect("the histories written");
}
/// Histories read back as spelled, and judged as the format says: an event taken, one
/// refused, and a root of a revision this continuum doesn't know read as none.
#[test]
fn histories_are_judged_as_the_format_says() {
let tv = Party::new("tv", 1);
let first = Spec::first(&[&tv, &Party::new("lass", 2)], &[]);
let root = first.root();
let write = tv.write(&[Id::of(&root)], "home/tv/a", harness::str("1"));
let unknown = String::from_utf8(root.clone()).expect("UTF-8").replacen(
r#""rules":"#,
&format!(r#""revision":"{}","rules":"#, Id::of(b"elsewhere")),
1,
);
let histories = vec![
History {
label: "one".to_owned(),
root: root.clone(),
events: vec![write.clone(), b"not an event".to_vec()],
},
History {
label: "unknown".to_owned(),
root: unknown.into_bytes(),
events: vec![write.clone()],
},
];
let again = read(&spelled(&histories)).expect("as spelled");
assert_eq!(again.len(), 2);
assert_eq!(again[0].events, histories[0].events);
let judged = judge(&again);
let lines: Vec<&str> = judged.lines().collect();
assert_eq!(lines[0], "case one");
assert_eq!(lines[1], format!("became {} taken", Id::of(&write)));
assert_eq!(
lines[2],
format!("became {} refused: none", Id::of(b"not an event"))
);
assert!(
lines[3].starts_with(r#"reads {"checkpoint":"#),
"{}",
lines[3]
);
assert!(lines[3].contains(r#""home/tv/a":"\"1\"""#), "{}", lines[3]);
assert_eq!(&lines[4..], ["case unknown", "root none"]);
assert!(read("nothing").is_err());
}
}
|