Skip to main content

cellix_doc/
changes.rs

1//! Suggested edits kept in the text itself, so they survive any tool and travel with the file.
2//! Markdown uses CriticMarkup and a paper uses the `changes` package.
3
4/// How a document writes its changes.
5#[derive(Clone, Copy, Debug, PartialEq, Eq)]
6pub enum Syntax {
7    Critic,
8    Latex,
9}
10
11impl Syntax {
12    /// What opens and closes an insertion.
13    pub fn insertion(self) -> (&'static str, &'static str) {
14        match self {
15            Self::Critic => ("{++", "++}"),
16            Self::Latex => ("\\added{", "}"),
17        }
18    }
19
20    /// What opens and closes a deletion.
21    pub fn deletion(self) -> (&'static str, &'static str) {
22        match self {
23            Self::Critic => ("{--", "--}"),
24            Self::Latex => ("\\deleted{", "}"),
25        }
26    }
27}
28
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub enum Kind {
31    Insert,
32    Delete,
33    Replace,
34}
35
36/// One change, as a range of chars in the document.
37#[derive(Clone, Debug, PartialEq, Eq)]
38pub struct Change {
39    pub start: usize,
40    pub end: usize,
41    pub kind: Kind,
42    pub old: String,
43    pub new: String,
44}
45
46fn starts(chars: &[char], at: usize, text: &str) -> bool {
47    text.chars()
48        .enumerate()
49        .all(|(index, wanted)| chars.get(at + index) == Some(&wanted))
50}
51
52fn find_text(chars: &[char], from: usize, text: &str) -> Option<usize> {
53    (from..chars.len()).find(|at| starts(chars, *at, text))
54}
55
56fn string(chars: &[char]) -> String {
57    chars.iter().collect()
58}
59
60fn critic(chars: &[char]) -> Vec<Change> {
61    let mut found = Vec::new();
62    let mut at = 0;
63    while at + 2 < chars.len() {
64        // A code span's text is code, marks and all.
65        if chars[at] == '`'
66            && let Some(close) = chars[at + 1..].iter().position(|c| *c == '`')
67        {
68            at += close + 2;
69            continue;
70        }
71        let change = if starts(chars, at, "{++") {
72            find_text(chars, at + 3, "++}").map(|close| Change {
73                start: at,
74                end: close + 3,
75                kind: Kind::Insert,
76                old: String::new(),
77                new: string(&chars[at + 3..close]),
78            })
79        } else if starts(chars, at, "{--") {
80            find_text(chars, at + 3, "--}").map(|close| Change {
81                start: at,
82                end: close + 3,
83                kind: Kind::Delete,
84                old: string(&chars[at + 3..close]),
85                new: String::new(),
86            })
87        } else if starts(chars, at, "{~~") {
88            find_text(chars, at + 3, "~>").and_then(|arrow| {
89                let close = find_text(chars, arrow, "~~}")?;
90                Some(Change {
91                    start: at,
92                    end: close + 3,
93                    kind: Kind::Replace,
94                    old: string(&chars[at + 3..arrow]),
95                    new: string(&chars[arrow + 2..close]),
96                })
97            })
98        } else {
99            None
100        };
101        match change {
102            Some(change) => {
103                at = change.end;
104                found.push(change);
105            }
106            None => at += 1,
107        }
108    }
109    found
110}
111
112/// Where the brace opened at `open` closes.
113fn brace_end(chars: &[char], open: usize) -> Option<usize> {
114    let mut depth = 0;
115    for (index, c) in chars.iter().enumerate().skip(open) {
116        match c {
117            '{' => depth += 1,
118            '}' => {
119                depth -= 1;
120                if depth == 0 {
121                    return Some(index);
122                }
123            }
124            _ => {}
125        }
126    }
127    None
128}
129
130/// A brace argument after a command, stepping over any `[options]`.
131fn argument(chars: &[char], from: usize) -> Option<(usize, usize)> {
132    let mut open = from;
133    if chars.get(open) == Some(&'[') {
134        open += chars[open..].iter().position(|c| *c == ']')? + 1;
135    }
136    (chars.get(open) == Some(&'{')).then_some(())?;
137    Some((open, brace_end(chars, open)?))
138}
139
140fn latex(chars: &[char]) -> Vec<Change> {
141    let mut found = Vec::new();
142    let mut at = 0;
143    while at < chars.len() {
144        let change = if starts(chars, at, "\\added") {
145            argument(chars, at + 6).map(|(open, close)| Change {
146                start: at,
147                end: close + 1,
148                kind: Kind::Insert,
149                old: String::new(),
150                new: string(&chars[open + 1..close]),
151            })
152        } else if starts(chars, at, "\\deleted") {
153            argument(chars, at + 8).map(|(open, close)| Change {
154                start: at,
155                end: close + 1,
156                kind: Kind::Delete,
157                old: string(&chars[open + 1..close]),
158                new: String::new(),
159            })
160        } else if starts(chars, at, "\\replaced") {
161            argument(chars, at + 9).and_then(|(open, close)| {
162                let (second, end) = argument(chars, close + 1)?;
163                Some(Change {
164                    start: at,
165                    end: end + 1,
166                    kind: Kind::Replace,
167                    old: string(&chars[second + 1..end]),
168                    new: string(&chars[open + 1..close]),
169                })
170            })
171        } else {
172            None
173        };
174        match change {
175            Some(change) => {
176                at = change.end;
177                found.push(change);
178            }
179            None => at += 1,
180        }
181    }
182    found
183}
184
185pub fn find(text: &str, syntax: Syntax) -> Vec<Change> {
186    let chars: Vec<char> = text.chars().collect();
187    match syntax {
188        Syntax::Critic => critic(&chars),
189        Syntax::Latex => latex(&chars),
190    }
191}
192
193/// The document with every change kept or dropped.
194/// The change from `old` to `new` as suggestions in `old`, word by word, so whoever reviews it
195/// accepts or rejects each one. Accepting all of them gives `new` back.
196pub fn suggest(old: &str, new: &str, syntax: Syntax) -> String {
197    let diff = similar::TextDiff::from_words(old, new);
198    let mut out = String::with_capacity(new.len() + new.len() / 4);
199    let (mut gone, mut added) = (String::new(), String::new());
200    let flush = |out: &mut String, gone: &mut String, added: &mut String| {
201        // Space at a change's edges stays plain, so the marks sit on words.
202        let lead = common_lead(gone, added).len();
203        let trail = common_trail(&gone[lead..], &added[lead..]).len();
204        out.push_str(&gone[..lead]);
205        let (old, new) = (
206            &gone[lead..gone.len() - trail],
207            &added[lead..added.len() - trail],
208        );
209        out.push_str(&mark(old, new, syntax));
210        out.push_str(&gone[gone.len() - trail..]);
211        gone.clear();
212        added.clear();
213    };
214    for change in diff.iter_all_changes() {
215        match change.tag() {
216            similar::ChangeTag::Equal => {
217                if !gone.is_empty() || !added.is_empty() {
218                    flush(&mut out, &mut gone, &mut added);
219                }
220                out.push_str(change.value());
221            }
222            similar::ChangeTag::Delete => gone.push_str(change.value()),
223            similar::ChangeTag::Insert => added.push_str(change.value()),
224        }
225    }
226    if !gone.is_empty() || !added.is_empty() {
227        flush(&mut out, &mut gone, &mut added);
228    }
229    out
230}
231
232/// The change from `old` to `new` for reading, line by line: a line that went is struck, a
233/// line that came is marked new, and a line changed in place shows its words. No mark spans a
234/// line, so every one renders. Accepting it all doesn't give `new` back exactly; it's a view.
235pub fn compare(old: &str, new: &str) -> String {
236    let diff = similar::TextDiff::from_lines(old, new);
237    let mut out = String::new();
238    for op in diff.ops() {
239        let (gone, came) = (op.old_range(), op.new_range());
240        let old_lines: Vec<&str> = old.lines().collect();
241        let new_lines: Vec<&str> = new.lines().collect();
242        match op.tag() {
243            similar::DiffTag::Equal => {
244                for line in &new_lines[came] {
245                    out.push_str(line);
246                    out.push('\n');
247                }
248            }
249            _ => {
250                let (gone, came) = (&old_lines[gone], &new_lines[came]);
251                // Pairs read as edits in place, and what's over as lines that went or came.
252                let paired = gone.len().min(came.len());
253                for (a, b) in gone.iter().zip(came.iter()).take(paired) {
254                    out.push_str(&in_line(a, b));
255                    out.push('\n');
256                }
257                for line in &gone[paired..] {
258                    out.push_str(&whole(line, "{--", "--}"));
259                    out.push('\n');
260                }
261                for line in &came[paired..] {
262                    out.push_str(&whole(line, "{++", "++}"));
263                    out.push('\n');
264                }
265            }
266        }
267    }
268    out
269}
270
271/// A line wholly marked, keeping a list item's or heading's marker outside, so it still reads
272/// as one.
273fn whole(line: &str, open: &str, close: &str) -> String {
274    if line.trim().is_empty() {
275        return line.to_string();
276    }
277    let lead = line.len() - line.trim_start().len();
278    let body = &line[lead..];
279    let marker = ["- ", "* ", "+ ", "#"]
280        .iter()
281        .find(|m| body.starts_with(**m))
282        .map(|m| {
283            if *m == "#" {
284                body.len() - body.trim_start_matches('#').trim_start().len()
285            } else {
286                m.len()
287            }
288        })
289        .or_else(|| {
290            let digits = body.chars().take_while(char::is_ascii_digit).count();
291            (digits > 0 && body[digits..].starts_with(". ")).then_some(digits + 2)
292        })
293        .unwrap_or(0);
294    let (keep, rest) = body.split_at(marker);
295    format!("{}{keep}{open}{rest}{close}", &line[..lead])
296}
297
298/// One line changed in place, as word suggestions.
299fn in_line(old: &str, new: &str) -> String {
300    suggest(old, new, Syntax::Critic)
301}
302
303/// One suggestion in the document's own syntax.
304pub fn mark(old: &str, new: &str, syntax: Syntax) -> String {
305    match (syntax, old.is_empty(), new.is_empty()) {
306        (_, true, true) => String::new(),
307        (Syntax::Critic, true, false) => format!("{{++{new}++}}"),
308        (Syntax::Critic, false, true) => format!("{{--{old}--}}"),
309        (Syntax::Critic, false, false) => format!("{{~~{old}~>{new}~~}}"),
310        (Syntax::Latex, true, false) => format!("\\added{{{new}}}"),
311        (Syntax::Latex, false, true) => format!("\\deleted{{{old}}}"),
312        (Syntax::Latex, false, false) => format!("\\replaced{{{new}}}{{{old}}}"),
313    }
314}
315
316/// The whitespace both start with.
317fn common_lead<'a>(a: &'a str, b: &str) -> &'a str {
318    let n = a
319        .chars()
320        .zip(b.chars())
321        .take_while(|(x, y)| x == y && x.is_whitespace())
322        .map(|(x, _)| x.len_utf8())
323        .sum();
324    &a[..n]
325}
326
327/// The whitespace both end with.
328fn common_trail<'a>(a: &'a str, b: &str) -> &'a str {
329    let n: usize = a
330        .chars()
331        .rev()
332        .zip(b.chars().rev())
333        .take_while(|(x, y)| x == y && x.is_whitespace())
334        .map(|(x, _)| x.len_utf8())
335        .sum();
336    &a[a.len() - n..]
337}
338
339/// A paper with the `changes` package its marks print with, just before its document begins.
340/// None when it loads it already, or has no preamble to put it in. Comments don't count.
341pub fn with_package(text: &str) -> Option<String> {
342    let mut offset = 0;
343    let mut begin = None;
344    for line in text.split_inclusive('\n') {
345        let code = crate::paper::uncommented(line);
346        if loads_changes(code) {
347            return None;
348        }
349        if begin.is_none()
350            && let Some(at) = code.find("\\begin{document}")
351        {
352            begin = Some(offset + at);
353        }
354        offset += line.len();
355    }
356    let at = begin?;
357    Some(format!(
358        "{}\\usepackage{{changes}}\n{}",
359        &text[..at],
360        &text[at..]
361    ))
362}
363
364/// Whether a line, without its comment, loads `changes` with `\usepackage[...]{...}`.
365fn loads_changes(code: &str) -> bool {
366    let mut rest = code;
367    while let Some(at) = rest.find("\\usepackage") {
368        let mut after = rest[at + "\\usepackage".len()..].trim_start();
369        if after.starts_with('[') {
370            after = after
371                .find(']')
372                .map_or("", |end| after[end + 1..].trim_start());
373        }
374        if let Some(inner) = after.strip_prefix('{')
375            && let Some((names, _)) = inner.split_once('}')
376            && names.split(',').any(|name| name.trim() == "changes")
377        {
378            return true;
379        }
380        rest = &rest[at + 1..];
381    }
382    false
383}
384
385pub fn settle_all(text: &str, syntax: Syntax, accept: bool) -> String {
386    let chars: Vec<char> = text.chars().collect();
387    let mut out = String::with_capacity(text.len());
388    let mut from = 0;
389    for change in find(text, syntax) {
390        out.extend(&chars[from..change.start]);
391        out.push_str(if accept { &change.new } else { &change.old });
392        from = change.end;
393    }
394    out.extend(&chars[from..]);
395    out
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401    #[test]
402    fn inline_code_keeps_its_marks_as_code() {
403        let text = "Use `a {++b++} c` and {++d++}.";
404        assert_eq!(
405            settle_all(text, Syntax::Critic, true),
406            "Use `a {++b++} c` and d."
407        );
408    }
409
410    #[test]
411    fn a_plan_compare_never_marks_across_a_line() {
412        let old = "# Plan\n\n1. Add a clock.\n2. Make it injectable so tests pass.\n3. Drop the windows.\n";
413        let new = "# Plan\n\n1. Add a clock.\n2. Make the clock injectable.\n";
414        let shown = compare(old, new);
415        for line in shown.lines() {
416            let opens = line.matches("{~~").count()
417                + line.matches("{++").count()
418                + line.matches("{--").count();
419            let closes = line.matches("~~}").count()
420                + line.matches("++}").count()
421                + line.matches("--}").count();
422            assert_eq!(opens, closes, "a mark spans a line: {line:?}\n{shown}");
423        }
424        assert!(shown.contains("3. {--Drop the windows.--}"), "{shown}");
425        assert!(shown.contains("1. Add a clock."), "{shown}");
426    }
427
428    #[test]
429    fn an_edit_becomes_suggestions_that_accept_back_to_it() {
430        let old = "The cache goes first, then the index.\n";
431        let new = "The cache goes last, then the new index.\n";
432        let marked = suggest(old, new, Syntax::Critic);
433        assert_eq!(
434            marked,
435            "The cache goes {~~first,~>last,~~} then the {++new ++}index.\n"
436        );
437        assert_eq!(settle_all(&marked, Syntax::Critic, true), new);
438        assert_eq!(settle_all(&marked, Syntax::Critic, false), old);
439        let tex = suggest("A b c.\n", "A x c.\n", Syntax::Latex);
440        assert_eq!(tex, "A \\replaced{x}{b} c.\n");
441    }
442
443    #[test]
444    fn markdown_writes_its_changes_in_three_ways() {
445        let text = "a {++new++} b {--old--} c {~~was~>now~~} d";
446        let found = find(text, Syntax::Critic);
447        assert_eq!(found.len(), 3);
448        assert_eq!(found[0].kind, Kind::Insert);
449        assert_eq!(found[0].new, "new");
450        assert_eq!(found[1].old, "old");
451        assert_eq!(
452            (found[2].old.as_str(), found[2].new.as_str()),
453            ("was", "now")
454        );
455        assert_eq!(settle_all(text, Syntax::Critic, true), "a new b  c now d");
456        assert_eq!(settle_all(text, Syntax::Critic, false), "a  b old c was d");
457    }
458
459    #[test]
460    fn a_paper_uses_the_changes_package() {
461        let text = "x \\added{new} y \\deleted[id=a]{old} z \\replaced{now}{was {nested}}";
462        let found = find(text, Syntax::Latex);
463        assert_eq!(found.len(), 3);
464        assert_eq!(found[1].old, "old");
465        assert_eq!(found[2].old, "was {nested}");
466        assert_eq!(settle_all(text, Syntax::Latex, true), "x new y  z now");
467        assert_eq!(
468            settle_all(text, Syntax::Latex, false),
469            "x  y old z was {nested}"
470        );
471    }
472
473    #[test]
474    fn the_changes_package_goes_in_unless_it_is_really_loaded() {
475        let paper = |preamble: &str| {
476            format!(
477                "\\documentclass{{article}}\n{preamble}\\begin{{document}}\nx\n\\end{{document}}\n"
478            )
479        };
480        for loaded in [
481            "\\usepackage{changes}\n",
482            "\\usepackage[final]{changes}\n",
483            "\\usepackage [markup=underlined] {xcolor, changes}\n",
484        ] {
485            assert_eq!(with_package(&paper(loaded)), None, "{loaded}");
486        }
487        for not_loaded in [
488            "% \\usepackage{changes}\n",
489            "\\label{changes}\n",
490            "\\usepackage{changesets}\n",
491        ] {
492            let with = with_package(&paper(not_loaded)).expect(not_loaded);
493            assert!(
494                with.contains("\\usepackage{changes}\n\\begin{document}"),
495                "{with}"
496            );
497        }
498        let commented =
499            "\\documentclass{article}\n% \\begin{document} comes later\n\\begin{document}\nx\n";
500        assert_eq!(
501            with_package(commented).unwrap(),
502            "\\documentclass{article}\n% \\begin{document} comes later\n\\usepackage{changes}\n\\begin{document}\nx\n",
503            "after the comment, before the real one"
504        );
505        assert_eq!(
506            with_package("% \\begin{document}\nx\n"),
507            None,
508            "no preamble"
509        );
510    }
511
512    #[test]
513    fn places_count_chars_not_bytes() {
514        let text = "é {++ü++}";
515        let change = &find(text, Syntax::Critic)[0];
516        assert_eq!((change.start, change.end), (2, 9));
517    }
518
519    #[test]
520    fn an_unclosed_mark_is_just_text() {
521        assert!(find("a {++b", Syntax::Critic).is_empty());
522        assert_eq!(settle_all("a {++b", Syntax::Critic, true), "a {++b");
523    }
524}