Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_pearlite/src/collab/fold.rs

10.0 KiB, 35 runs

created by r1870400018:58596, 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//! Folding a document's operation stream into its annotation set, and materialising that set into a
2//! local `.prl`.
3//!
4//! # What the fold is handed
5//!
6//! Verified, attributed operations -- [`Opened`] values, each a record together with the key that
7//! signed it -- not a bare log. The signer is the operation's identity: the author a reader sees comes
8//! from the key by way of the document's [`Keyring`], never from a field in the body, which any key
9//! could fill with any name. An operation is folded under the document it was stamped for and no other.
10//!
11//! # Determinism
12//!
13//! Two replicas that hold the same operations must produce the same annotation set in the same order,
14//! however those operations arrived. So the fold does not walk in arrival order: it orders every
15//! operation by the author's clock reading and then, for a tie, by operation identifier -- a total
16//! order that is the same on every replica because it depends only on the operations themselves. An
17//! annotation's place in the result is the place of the proposal that opened it.
18//!
19//! # What the fold does with each operation
20//!
21//! - A proposal opens an annotation, keyed by its own identifier, attributed to its signer.
22//! - An amendment on that proposal replaces the annotation, but only from the proposal's own signer,
23//! and only while the proposal has not been withdrawn; processed in time order, the last one wins.
24//! - A settlement in the `Declined` state, from the proposal's own signer, withdraws the annotation and
25//! tombstones it, so that no later amendment can bring it back; any other state leaves it in.
26//! - A reply (`Said`) is threaded discussion, not a standalone annotation, so it does not add here.
27//!
28//! # Poison-proof
29//!
30//! A stored operation is forever: an append-only log cannot forget one, so a single malformed but
31//! validly-signed operation must never be able to make the whole fold fail for every reader. It cannot.
32//! An operation the fold cannot use -- a body that does not decode, a body stamped for another document,
33//! an amendment or settlement from someone other than the proposal's signer -- is skipped and reported,
34//! never fatal. The fold always returns the annotations it could establish.
35
36use crate::collab::{
37 op,
38 replica_of,
39 sign::Opened,
40 DocId,
41 Keyring,
42};
43
44use oxedyne_fe2o3_austenite::emit::pearl::{
45 Annotation,
46 PearlDoc,
47};
48use oxedyne_fe2o3_ore::{
49 id::OpId,
50 op::{
51 Op,
52 Settled,
53 },
54};
55
56use oxedyne_fe2o3_core::prelude::*;
57
58use std::collections::{
59 BTreeMap,
60 BTreeSet,
61};
62
63/// One operation the fold could not use, and why.
64///
65/// A skip is not an error: the fold went on and produced its result without it. It is reported so a
66/// caller can surface a malformed or unauthorised operation rather than have it vanish silently.
67#[derive(Clone, Debug, Eq, PartialEq)]
68pub struct Skipped {
69 pub id: OpId,
70 pub reason: String,
71}
72
73/// The result of a fold: the annotations that stand, and the operations that were passed over.
74#[derive(Clone, Debug, Default, Eq, PartialEq)]
75pub struct FoldReport {
76 pub annotations: Vec<Annotation>,
77 pub skipped: Vec<Skipped>,
78}
79
80/// Folds a document's verified operations into its annotation set, in deterministic order.
81///
82/// `opened` is every operation of the document, each already verified and bound to its signer by
83/// [`super::sign::open`]; `doc` is the document being folded, against which each operation's stamped
84/// document identity is checked; `keyring` names the signers for display. The fold never fails on a bad
85/// operation: see the module header. The result carries the annotations that stand once every amendment
86/// and withdrawal has been applied, ordered by their opening proposal's `(time, id)`, and beside them
87/// the operations that were skipped.
88pub fn fold(opened: &[Opened], doc: &DocId, keyring: &Keyring) -> FoldReport {
89 // Every operation, ordered by the author's clock and then by identifier, so the fold is the same
90 // on every replica whatever order the operations were assembled in.
91 let mut recs: Vec<&Opened> = opened.iter().collect();
92 recs.sort_by(|a, b| {
93 op::time_of(&a.record().op).cmp(&op::time_of(&b.record().op))
94 .then_with(|| a.record().id().cmp(&b.record().id()))
95 });
96
97 // Annotations keyed by their opening proposal's order key, so iterating the map yields them in
98 // `(time, id)` order; beside it, the order key and the signing key each proposal identifier maps
99 // to, so an amendment or a settlement can find the annotation it acts on and check it is acting on
100 // its own author's proposal; and the proposals a withdrawal has tombstoned, which no amendment may
101 // resurrect.
102 let mut anns: BTreeMap<(u64, OpId), Annotation> = BTreeMap::new();
103 let mut key_of: BTreeMap<OpId, (u64, OpId)> = BTreeMap::new();
104 let mut signer_of: BTreeMap<OpId, Vec<u8>> = BTreeMap::new();
105 let mut tombstoned: BTreeSet<OpId> = BTreeSet::new();
106 let mut skipped: Vec<Skipped> = Vec::new();
107
108 for opened in recs {
109 let rec = opened.record();
110 let id = rec.id();
111 let signer = opened.signer();
112 // Belt and braces to the ingest check: an [`Opened`] is meant to have been opened for this
113 // document, but the fold re-derives the binding rather than trust that it was, so an operation
114 // from another document -- a settlement or reply lifted across, which carries no body stamp --
115 // is skipped here even if it reached the set unopened for this document.
116 if rec.id().replica != replica_of(signer, doc) {
117 skipped.push(Skipped {
118 id,
119 reason: fmt!("its replica {} is not the one its signer derives under document {}; it \
120 belongs to another document and is not folded here", rec.id().replica, doc),
121 });
122 continue;
123 }
124 match &rec.op {
125 Op::Proposal { body, .. } => {
126 let ann = match decode_for_doc(body, doc) {
127 Ok(ann) => ann,
128 Err(reason) => {
129 skipped.push(Skipped { id, reason });
130 continue;
131 },
132 };
133 let key = (op::time_of(&rec.op), id);
134 key_of.insert(id, key);
135 signer_of.insert(id, signer.to_vec());
136 anns.insert(key, attribute(ann, signer, keyring));
137 },
138 Op::Amended { on, body, .. } => {
139 // An amendment on a proposal this fold has not seen names content outside what it
140 // holds; it is left for a later, causally complete fold rather than guessed at.
141 let key = match key_of.get(on) {
142 Some(key) => *key,
143 None => continue,
144 };
145 if tombstoned.contains(on) {
146 skipped.push(Skipped {
147 id,
148 reason: fmt!("amends the withdrawn proposal {}, which a withdrawal tombstones \
149 against resurrection", on),
150 });
151 continue;
152 }
153 // Only the proposal's own signer may restate it. An amendment from any other key is a
154 // stranger editing someone else's annotation, and is refused.
155 if signer_of.get(on).map(|s| s.as_slice()) != Some(signer) {
156 skipped.push(Skipped {
157 id,
158 reason: fmt!("amends the proposal {}, whose signer it does not match; an \
159 amendment is accepted only from the proposal's own signer", on),
160 });
161 continue;
162 }
163 let ann = match decode_for_doc(body, doc) {
164 Ok(ann) => ann,
165 Err(reason) => {
166 skipped.push(Skipped { id, reason });
167 continue;
168 },
169 };
170 anns.insert(key, attribute(ann, signer, keyring));
171 },
172 Op::Settled { on, state, .. } => {
173 let key = match key_of.get(on) {
174 Some(key) => *key,
175 None => continue,
176 };
177 // Only the proposal's own signer may settle it, for the reason an amendment is so
178 // confined: a stranger does not get to withdraw or resolve another author's annotation.
179 if signer_of.get(on).map(|s| s.as_slice()) != Some(signer) {
180 skipped.push(Skipped {
181 id,
182 reason: fmt!("settles the proposal {}, whose signer it does not match; a \
183 settlement is accepted only from the proposal's own signer", on),
184 });
185 continue;
186 }
187 if matches!(state, Settled::Declined) {
188 anns.remove(&key);
189 tombstoned.insert(*on);
190 }
191 },
192 // A reply or any non-annotation operation adds nothing to the materialised set.
193 _ => {},
194 }
195 }
196
197 FoldReport {
198 annotations: anns.into_values().collect(),
199 skipped,
200 }
201}
202
203/// Decodes an annotation body under the collaboration decode bounds and checks it was stamped for
204/// `doc`, returning a reason string on either failure so the fold can skip and report it.
205///
206/// A body stamped for another document, or for none, is a cross-document replay: a signed annotation
207/// lifted from document A and appended to document B, where the same block address happens to exist.
208/// Binding the fold to the stamped identity refuses it.
209fn decode_for_doc(body: &[u8], doc: &DocId) -> std::result::Result<Annotation, String> {
210 let ann = match op::annotation_from_body(body) {
211 Ok(ann) => ann,
212 Err(e) => return Err(fmt!("its body does not decode as an annotation: {}", e)),
213 };
214 match &ann.doc_id {
215 Some(id) if id == doc.as_str() => Ok(ann),
216 Some(id) => Err(fmt!(
217 "its body is stamped for document {:?}, not {:?}; it will not be folded here", id, doc.as_str())),
218 None => Err(fmt!(
219 "its body carries no document identity, so it cannot be confirmed to belong to {:?}",
220 doc.as_str())),
221 }
222}
223
224/// Sets an annotation's displayed author from the key that signed it, by way of the keyring, so the
225/// author a reader sees is the signer and never whatever the body claimed.
226fn attribute(mut ann: Annotation, signer: &[u8], keyring: &Keyring) -> Annotation {
227 ann.author = keyring.display(signer);
228 ann
229}
230
231/// Attaches a folded annotation set to a decoded `.prl`, through
232/// [`PearlDoc::add_annotation`](oxedyne_fe2o3_austenite::emit::pearl::PearlDoc::add_annotation).
233///
234/// An annotation whose anchor block is not in this particular document is skipped rather than
235/// refused: a fold drawn from the shared stream may carry annotations on content a given local file
236/// does not hold, and those simply have nothing to attach to here. The count returned is how many were
237/// attached.
238pub fn materialise(doc: &mut PearlDoc, anns: &[Annotation]) -> Outcome<usize> {
239 let mut attached = 0;
240 for ann in anns {
241 if res!(doc.has_block(&ann.anchor)) {
242 res!(doc.add_annotation(ann.clone()));
243 attached += 1;
244 }
245 }
246 Ok(attached)
247}