Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/trace.rs

8.9 KiB, 1 run

created by r2848102244:99, 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//! Reader and coarsener for the `automerge-perf` single-user editing trace.
2//!
3//! The trace is 259,778 single-character splices against a document that ends
4//! at 104,852 characters. The design assumes splice granularity, so the trace
5//! is coarsened before replay, and the coarsening policy is recorded because it
6//! is exactly the "frontend policy" that design note section 7.3 says the cost
7//! claim depends on.
8
9use crate::id::{
10 after,
11 before,
12 ContentId,
13 OpId,
14};
15use crate::op::Op;
16use crate::replica::coalesce;
17
18use oxedyne_fe2o3_core::prelude::*;
19
20/// One line of the trace.
21#[derive(Clone, Debug)]
22pub enum RawEdit {
23 /// Insert one character at an index.
24 Ins {
25 /// Index in the current text.
26 pos: usize,
27 /// The character's UTF-8 bytes.
28 ch: Vec<u8>,
29 },
30 /// Delete one character at an index.
31 Del {
32 /// Index in the current text.
33 pos: usize,
34 },
35}
36
37/// A coarsened edit: delete `del` bytes at `pos`, then insert `ins` there.
38#[derive(Clone, Debug)]
39pub struct Coarse {
40 /// Index in the current text.
41 pub pos: usize,
42 /// How many bytes die.
43 pub del: usize,
44 /// What is inserted.
45 pub ins: Vec<u8>,
46}
47
48/// Unescapes a JavaScript string literal body.
49fn unescape(src: &str) -> Outcome<String> {
50 let mut out = String::with_capacity(src.len());
51 let mut it = src.chars();
52 while let Some(c) = it.next() {
53 if c != '\\' {
54 out.push(c);
55 continue;
56 }
57 let e = match it.next() {
58 Some(e) => e,
59 None => return Err(err!("Trailing backslash in string literal."; Invalid, Input)),
60 };
61 match e {
62 'n' => out.push('\n'),
63 't' => out.push('\t'),
64 'r' => out.push('\r'),
65 'b' => out.push('\u{8}'),
66 'f' => out.push('\u{c}'),
67 'v' => out.push('\u{b}'),
68 '0' => out.push('\0'),
69 '\\' => out.push('\\'),
70 '"' => out.push('"'),
71 '\'' => out.push('\''),
72 '/' => out.push('/'),
73 'u' => {
74 let mut hex = String::new();
75 for _ in 0..4 {
76 match it.next() {
77 Some(h) => hex.push(h),
78 None => return Err(err!(
79 "Truncated \\u escape."; Invalid, Input)),
80 }
81 }
82 let n = res!(u32::from_str_radix(&hex, 16));
83 match char::from_u32(n) {
84 Some(c) => out.push(c),
85 None => return Err(err!(
86 "Bad code point {}.", n; Invalid, Input)),
87 }
88 },
89 _ => return Err(err!("Unknown escape \\{}.", e; Invalid, Input)),
90 }
91 }
92 Ok(out)
93}
94
95/// Reads `editing-trace.js` and returns the edits and the expected final text.
96pub fn parse(path: &str) -> Outcome<(Vec<RawEdit>, String)> {
97 let src = res!(std::fs::read_to_string(path));
98 let mut edits: Vec<RawEdit> = Vec::with_capacity(260_000);
99 let mut final_text: Option<String> = None;
100 for line in src.lines() {
101 if let Some(rest) = line.strip_prefix(" [") {
102 let body = match rest.strip_suffix("],") {
103 Some(b) => b,
104 None => rest.trim_end_matches(']'),
105 };
106 // `pos, 1` or `pos, 0, "c"`.
107 let (pos_s, tail) = match body.split_once(", ") {
108 Some(p) => p,
109 None => continue,
110 };
111 let pos: usize = res!(pos_s.trim().parse::<usize>());
112 if tail.trim() == "1" {
113 edits.push(RawEdit::Del { pos });
114 } else if let Some(q) = tail.find('"') {
115 let lit = &tail[q + 1..];
116 let lit = match lit.rfind('"') {
117 Some(e) => &lit[..e],
118 None => return Err(err!(
119 "Unterminated character literal in {}.", line; Invalid, Input)),
120 };
121 let s = res!(unescape(lit));
122 edits.push(RawEdit::Ins { pos, ch: s.into_bytes() });
123 } else {
124 return Err(err!("Unrecognised trace line: {}", line; Invalid, Input));
125 }
126 } else if let Some(rest) = line.strip_prefix("const finalText = \"") {
127 let body = match rest.rfind("\";") {
128 Some(e) => &rest[..e],
129 None => return Err(err!(
130 "Unterminated finalText literal."; Invalid, Input)),
131 };
132 final_text = Some(res!(unescape(body)));
133 }
134 }
135 let ft = match final_text {
136 Some(t) => t,
137 None => return Err(err!("No finalText in {}.", path; Missing, Input)),
138 };
139 Ok((edits, ft))
140}
141
142/// Coarsens single-character edits into splices.
143///
144/// The policy, stated so that the measured cost can be read against it:
145/// consecutive insertions at consecutive rising indices merge into one splice;
146/// consecutive deletions at one index, or at indices falling by one, merge into
147/// one removal; and a removal immediately followed by an insertion at the
148/// removal's final index merges into a single replacing splice.
149pub fn coarsen(edits: &[RawEdit]) -> Vec<Coarse> {
150 let mut out: Vec<Coarse> = Vec::new();
151 // Run state: an open coarse edit, plus the index at which the next
152 // single-character edit must land to extend it.
153 let mut open: Option<(Coarse, usize, bool)> = None; // (edit, next insert index, deleting)
154 for e in edits {
155 match e {
156 RawEdit::Ins { pos, ch } => {
157 let extend = match &open {
158 Some((_, next, _)) => *next == *pos,
159 None => false,
160 };
161 if extend {
162 if let Some((c, next, deleting)) = open.as_mut() {
163 c.ins.extend_from_slice(ch);
164 *next = *pos + ch.len();
165 *deleting = false;
166 }
167 } else {
168 if let Some((c, _, _)) = open.take() {
169 out.push(c);
170 }
171 open = Some((
172 Coarse { pos: *pos, del: 0, ins: ch.clone() },
173 *pos + ch.len(),
174 false,
175 ));
176 }
177 },
178 RawEdit::Del { pos } => {
179 // A deletion may extend an open run only if that run is itself
180 // a deletion run, at the same index (forward delete) or one
181 // index back (backspace).
182 let mode = match &open {
183 Some((c, _, true)) if c.pos == *pos => 1,
184 Some((c, _, true)) if c.pos == *pos + 1 => 2,
185 _ => 0,
186 };
187 match mode {
188 1 => {
189 if let Some((c, _, _)) = open.as_mut() {
190 c.del += 1;
191 }
192 },
193 2 => {
194 if let Some((c, next, _)) = open.as_mut() {
195 c.pos = *pos;
196 c.del += 1;
197 *next = *pos;
198 }
199 },
200 _ => {
201 if let Some((c, _, _)) = open.take() {
202 out.push(c);
203 }
204 open = Some((
205 Coarse { pos: *pos, del: 1, ins: Vec::new() },
206 *pos,
207 true,
208 ));
209 },
210 }
211 },
212 }
213 }
214 if let Some((c, _, _)) = open.take() {
215 out.push(c);
216 }
217 out
218}
219
220/// Turns each raw edit into its own splice, with no coarsening at all, so that
221/// the splice-granularity saving can be measured rather than assumed.
222pub fn fine(edits: &[RawEdit]) -> Vec<Coarse> {
223 edits.iter().map(|e| match e {
224 RawEdit::Ins { pos, ch } => Coarse { pos: *pos, del: 0, ins: ch.clone() },
225 RawEdit::Del { pos } => Coarse { pos: *pos, del: 1, ins: Vec::new() },
226 }).collect()
227}
228
229/// A gap buffer over `(byte, content id)` pairs, standing in for the editor's
230/// own text buffer. Without it the frontend, not the structure, is the
231/// bottleneck.
232struct GapBuf {
233 l: Vec<(u8, ContentId)>,
234 r: Vec<(u8, ContentId)>,
235}
236
237impl GapBuf {
238 fn new() -> Self {
239 Self { l: Vec::new(), r: Vec::new() }
240 }
241
242 fn len(&self) -> usize {
243 self.l.len() + self.r.len()
244 }
245
246 fn seek(&mut self, i: usize) {
247 while self.l.len() > i {
248 if let Some(x) = self.l.pop() {
249 self.r.push(x);
250 }
251 }
252 while self.l.len() < i {
253 if let Some(x) = self.r.pop() {
254 self.l.push(x);
255 } else {
256 break;
257 }
258 }
259 }
260
261 fn text(&self) -> Vec<u8> {
262 let mut v: Vec<u8> = self.l.iter().map(|(b, _)| *b).collect();
263 v.extend(self.r.iter().rev().map(|(b, _)| *b));
264 v
265 }
266}
267
268/// The outcome of replaying a coarsened trace through the frontend.
269pub struct Built {
270 /// The operations, in generation order.
271 pub ops: Vec<Op>,
272 /// The text as the frontend's own buffer sees it, a plain-array baseline.
273 pub baseline: Vec<u8>,
274 /// How many splices carry both a removal and an insertion.
275 pub replacing: usize,
276 /// Total inserted bytes.
277 pub inserted: usize,
278 /// Total removal intervals recorded.
279 pub remove_intervals: usize,
280}
281
282/// Turns coarsened edits into content-anchored splices.
283pub fn build_ops(edits: &[Coarse]) -> Outcome<Built> {
284 let mut buf = GapBuf::new();
285 let mut ops: Vec<Op> = Vec::with_capacity(edits.len());
286 let mut counter = 0u64;
287 let mut replacing = 0usize;
288 let mut inserted = 0usize;
289 let mut remove_intervals = 0usize;
290 for e in edits {
291 if e.pos > buf.len() {
292 return Err(err!("Coarse edit at {} beyond length {}.",
293 e.pos, buf.len(); Invalid, Input));
294 }
295 buf.seek(e.pos);
296 // Removal first, so that anchors bracket the gap left behind.
297 let mut removed: Vec<ContentId> = Vec::with_capacity(e.del);
298 for _ in 0..e.del {
299 match buf.r.pop() {
300 Some((_, cid)) => removed.push(cid),
301 None => return Err(err!(
302 "Deletion runs past the end of the text."; Invalid, Input)),
303 }
304 }
305 let remove = res!(coalesce(&removed));
306 remove_intervals += remove.len();
307 let left = buf.l.last().map(|(_, cid)| *cid).and_then(after);
308 let right = buf.r.last().map(|(_, cid)| *cid).and_then(before);
309 counter += 1;
310 let id = OpId::new(counter, 0);
311 if !e.ins.is_empty() && !remove.is_empty() {
312 replacing += 1;
313 }
314 inserted += e.ins.len();
315 for (k, b) in e.ins.iter().enumerate() {
316 buf.l.push((*b, ContentId::new(id, k as u32)));
317 }
318 ops.push(Op::Splice {
319 id,
320 left,
321 right,
322 remove,
323 insert: e.ins.clone(),
324 });
325 }
326 Ok(Built {
327 ops,
328 baseline: buf.text(),
329 replacing,
330 inserted,
331 remove_intervals,
332 })
333}