crates/oxy-core/src/rewrite.rs at 6caacfff1d4f · andymccall/oxygen

# 6caacfff1d4f oxygen / crates / oxy-core / src / rewrite.rs
26.9 KiB · Rust · last changed Store large inserts as text blobs (change format 2) 1 month ago source blame history raw
//! Rewrite propagation (spec §8.4): when change `old` is replaced by `new`,
//! every change that depends on `old` is rewritten with its references
//! translated through a correspondence from `old`'s atoms and tree operations
//! to `new`'s. Rewritten changes keep their ChangeIds.
//!
//! Where a reference has no counterpart it is reified rather than refused:
//! an insert anchor moves to the nearest surviving atom of the same insert
//! chain in `old`, else to that chain's own anchors (an order conflict then
//! arises naturally if `new` placed other content there); deletions of
//! vanished atoms are dropped; operations and edits on nodes that vanished
//! are dropped. Every such adjustment is reported as a note.

use crate::hash::ChangeHash;
use crate::objects::{AtomRange, AtomRef, Change, Edit, OpRef, TreeOp};
use crate::state::State;
use std::collections::{BTreeSet, HashMap};

/// How `old`'s atoms and tree operations map onto `new`'s.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Correspondence {
    /// `(node, old atom index)` → new atom index. Absent means the atom no
    /// longer exists.
    pub atoms: HashMap<(crate::ids::NodeId, u32), u32>,
    /// Old tree-op index → new tree-op index.
    pub ops: HashMap<u32, u32>,
}

impl Correspondence {
    /// Every atom and operation keeps its index: `new` has the same edits as `old`.
    pub fn identity(change: &Change) -> Correspondence {
        let mut atoms = HashMap::new();
        let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();
        for e in &change.edits {
            if let Edit::Insert { node, lines, .. } = e {
                let idx = per_node.entry(*node).or_default();
                for _ in lines {
                    atoms.insert((*node, *idx), *idx);
                    *idx += 1;
                }
            }
        }
        let ops = (0..change.tree_ops.len() as u32).map(|i| (i, i)).collect();
        Correspondence { atoms, ops }
    }

    /// Match `old`'s atoms to `new`'s by content, per node, in order (the
    /// correspondence of a re-derived change, spec §8.5); operations match
    /// by node and variant.
    pub fn by_content(old: &Change, new: &Change) -> Correspondence {
        let lines_of = |c: &Change| -> HashMap<crate::ids::NodeId, Vec<Vec<u8>>> {
            let mut m: HashMap<crate::ids::NodeId, Vec<Vec<u8>>> = HashMap::new();
            for e in &c.edits {
                if let Edit::Insert { node, lines, .. } = e {
                    m.entry(*node).or_default().extend(lines.iter().cloned());
                }
            }
            m
        };
        let (a, b) = (lines_of(old), lines_of(new));
        let mut atoms = HashMap::new();
        for (node, olds) in &a {
            let Some(news) = b.get(node) else { continue };
            let mut j = 0usize;
            for (i, line) in olds.iter().enumerate() {
                while j < news.len() && news[j] != *line {
                    j += 1;
                }
                if j < news.len() {
                    atoms.insert((*node, i as u32), j as u32);
                    j += 1;
                }
            }
        }
        let mut ops = HashMap::new();
        for (i, op) in old.tree_ops.iter().enumerate() {
            if let Some(j) = new.tree_ops.iter().position(|n| {
                n.node() == op.node() && std::mem::discriminant(n) == std::mem::discriminant(op)
            }) {
                ops.insert(i as u32, j as u32);
            }
        }
        Correspondence { atoms, ops }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
pub enum RewriteError {
    #[error("change {0} is not in the state")]
    Missing(ChangeHash),
}

/// The result of propagating a rewrite.
#[derive(Clone, Debug, Default)]
pub struct Propagation {
    /// `(old hash, rewritten change)` in dependency order.
    pub changes: Vec<(ChangeHash, Change)>,
    /// Human-readable descriptions of reified orphaned references.
    pub notes: Vec<String>,
}

/// Where each atom of a change was inserted: the chain it belongs to.
struct Chain {
    node: crate::ids::NodeId,
    first: u32,
    last: u32,
    after: AtomRef,
    before: AtomRef,
}

fn chains_of(c: &Change) -> Vec<Chain> {
    let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();
    let mut out = Vec::new();
    for e in &c.edits {
        if let Edit::Insert {
            node,
            after,
            before,
            lines,
        } = e
        {
            let idx = per_node.entry(*node).or_default();
            out.push(Chain {
                node: *node,
                first: *idx,
                last: *idx + lines.len() as u32 - 1,
                after: *after,
                before: *before,
            });
            *idx += lines.len() as u32;
        }
    }
    out
}

/// What a rewritten change was replaced by.
#[derive(Clone, Debug)]
enum Replacement {
    Change(ChangeHash),
    /// Removed: dependents inherit these dependencies instead.
    Removed(Vec<ChangeHash>),
}

/// Rewrite every change in `state` that depends on `old`, given `new` (or
/// `None` when `old` is removed) and the correspondence between them.
/// The result lists `(old hash, rewritten change)` pairs in dependency
/// order, not including `old` → `new` itself, plus notes about reified
/// orphaned references.
///
/// `load` fetches a change's full object (a state keeps only metadata).
pub fn propagate(
    state: &State,
    old: ChangeHash,
    new: Option<&Change>,
    corr: &Correspondence,
    load: &dyn Fn(&ChangeHash) -> Option<Change>,
) -> Result<Propagation, RewriteError> {
    let old_meta = state.get(&old).ok_or(RewriteError::Missing(old))?;
    let old_full = load(&old);
    let mut mapping: HashMap<ChangeHash, Replacement> = HashMap::new();
    mapping.insert(
        old,
        match new {
            Some(n) => Replacement::Change(n.hash()),
            None => Replacement::Removed(old_meta.deps.clone()),
        },
    );
    let mut corrs: HashMap<ChangeHash, Correspondence> = HashMap::new();
    corrs.insert(old, corr.clone());
    // Chains of the rewritten change, for re-anchoring; vanished nodes.
    let chains: HashMap<ChangeHash, Vec<Chain>> = old_full
        .as_ref()
        .map(|c| (old, chains_of(c)))
        .into_iter()
        .collect();
    let mut vanished_nodes: BTreeSet<crate::ids::NodeId> = BTreeSet::new();
    if let Some(c) = &old_full {
        for (i, op) in c.tree_ops.iter().enumerate() {
            if let TreeOp::AddNode { node, .. } = op {
                let survives = new.is_some() && corr.ops.contains_key(&(i as u32));
                if !survives {
                    vanished_nodes.insert(*node);
                }
            }
        }
    }
    let mut notes = Vec::new();

    // Dependents in topological order: every change whose closure has `old`,
    // sorted so that dependencies come first.
    let mut dependents: Vec<ChangeHash> = state
        .changes()
        .filter(|(h, _)| **h != old && state.closure(h).contains(&old))
        .map(|(h, _)| *h)
        .collect();
    dependents.sort_by_key(|h| (state.closure(h).len(), *h));

    let mut out = Vec::new();
    for h in dependents {
        let c = load(&h).ok_or(RewriteError::Missing(h))?;
        let rewritten = rewrite_one(
            &h,
            &c,
            &mapping,
            &corrs,
            &chains,
            &vanished_nodes,
            &mut notes,
        );
        let rh = rewritten.hash();
        corrs.insert(h, Correspondence::identity(&rewritten));
        mapping.insert(h, Replacement::Change(rh));
        out.push((h, rewritten));
    }
    Ok(Propagation {
        changes: out,
        notes,
    })
}

/// Re-anchor a reference to a vanished atom of `change`: the nearest
/// surviving atom of its chain (before it for `after` anchors, after it for
/// `before` anchors), else the chain's own anchor.
fn reanchor(
    change: &ChangeHash,
    index: u32,
    want_after: bool,
    mapping: &HashMap<ChangeHash, Replacement>,
    corrs: &HashMap<ChangeHash, Correspondence>,
    chains: &HashMap<ChangeHash, Vec<Chain>>,
) -> AtomRef {
    let corr = corrs.get(change);
    let chain = chains
        .get(change)
        .and_then(|cs| cs.iter().find(|ch| ch.first <= index && index <= ch.last));
    if let (Some(Replacement::Change(nh)), Some(corr), Some(ch)) =
        (mapping.get(change), corr, chain)
    {
        let candidates: Box<dyn Iterator<Item = u32>> = if want_after {
            Box::new((ch.first..index).rev())
        } else {
            Box::new(index + 1..=ch.last)
        };
        for j in candidates {
            if let Some(nj) = corr.atoms.get(&(ch.node, j)) {
                return AtomRef::Atom {
                    change: *nh,
                    index: *nj,
                };
            }
        }
    }
    match chain {
        Some(ch) => {
            if want_after {
                ch.after
            } else {
                ch.before
            }
        }
        None => {
            if want_after {
                AtomRef::Start
            } else {
                AtomRef::End
            }
        }
    }
}

fn rewrite_one(
    hash: &ChangeHash,
    c: &Change,
    mapping: &HashMap<ChangeHash, Replacement>,
    corrs: &HashMap<ChangeHash, Correspondence>,
    chains: &HashMap<ChangeHash, Vec<Chain>>,
    vanished_nodes: &BTreeSet<crate::ids::NodeId>,
    notes: &mut Vec<String>,
) -> Change {
    let short = hash.short(12);
    // An anchor: translate, or re-anchor when its counterpart is gone.
    let map_anchor = |r: AtomRef,
                      node: &crate::ids::NodeId,
                      want_after: bool,
                      notes: &mut Vec<String>|
     -> AtomRef {
        match r {
            AtomRef::Atom { change, index } => match mapping.get(&change) {
                Some(Replacement::Change(nh)) => match corrs[&change].atoms.get(&(*node, index)) {
                    Some(idx) => AtomRef::Atom {
                        change: *nh,
                        index: *idx,
                    },
                    None => {
                        notes.push(format!("change {short}: an anchor line of the rewritten change vanished; re-anchored to its nearest neighbour"));
                        reanchor(&change, index, want_after, mapping, corrs, chains)
                    }
                },
                Some(Replacement::Removed(_)) => {
                    notes.push(format!("change {short}: an anchor line of the removed change vanished; re-anchored to its neighbours"));
                    reanchor(&change, index, want_after, mapping, corrs, chains)
                }
                None => r,
            },
            other => other,
        }
    };
    // A tree-operation reference: translate, or `None` when gone.
    let map_op = |r: OpRef| -> Option<OpRef> {
        match mapping.get(&r.change) {
            Some(Replacement::Change(nh)) => corrs[&r.change].ops.get(&r.index).map(|idx| OpRef {
                change: *nh,
                index: *idx,
            }),
            Some(Replacement::Removed(_)) => None,
            None => Some(r),
        }
    };
    let mut out = c.clone();
    let mut deps: BTreeSet<ChangeHash> = BTreeSet::new();
    for d in &c.deps {
        match mapping.get(d) {
            Some(Replacement::Change(nh)) => {
                deps.insert(*nh);
            }
            Some(Replacement::Removed(inherited)) => deps.extend(inherited.iter().copied()),
            None => {
                deps.insert(*d);
            }
        }
    }
    out.deps = deps.into_iter().collect();
    let mut ops = Vec::new();
    for op in &out.tree_ops {
        let node = op.node();
        if vanished_nodes.contains(&node)
            || matches!(op, TreeOp::AddNode { parent, .. } if vanished_nodes.contains(parent))
        {
            notes.push(format!("change {short}: an operation on a file that vanished with the rewritten change was dropped"));
            continue;
        }
        match op {
            TreeOp::RemoveNode { node, placement } => match map_op(*placement) {
                Some(p) => ops.push(TreeOp::RemoveNode {
                    node: *node,
                    placement: p,
                }),
                None => notes.push(format!(
                    "change {short}: removal of a placement that vanished was dropped"
                )),
            },
            TreeOp::Move {
                node,
                old,
                parent,
                name,
            } => match map_op(*old) {
                Some(o) => ops.push(TreeOp::Move {
                    node: *node,
                    old: o,
                    parent: *parent,
                    name: name.clone(),
                }),
                None => notes.push(format!(
                    "change {short}: a move of {name} lost its origin and was dropped"
                )),
            },
            TreeOp::SetMode { node, old, mode } => match map_op(*old) {
                Some(o) => ops.push(TreeOp::SetMode {
                    node: *node,
                    old: o,
                    mode: *mode,
                }),
                None => notes.push(format!(
                    "change {short}: a mode change lost its origin and was dropped"
                )),
            },
            add @ TreeOp::AddNode { .. } => ops.push(add.clone()),
        }
    }
    out.tree_ops = ops;
    let mut edits = Vec::new();
    for e in &out.edits {
        if vanished_nodes.contains(&e.node()) {
            notes.push(format!("change {short}: an edit of a file that vanished with the rewritten change was dropped"));
            continue;
        }
        match e {
            Edit::Insert {
                node,
                after,
                before,
                lines,
            } => edits.push(Edit::Insert {
                node: *node,
                after: map_anchor(*after, node, true, notes),
                before: map_anchor(*before, node, false, notes),
                lines: lines.clone(),
            }),
            Edit::Delete { node, atoms } => {
                let mut mapped: Vec<(ChangeHash, u32)> = Vec::new();
                let mut dropped = 0;
                for r in atoms.iter() {
                    for i in r.from..r.to {
                        match mapping.get(&r.change) {
                            Some(Replacement::Change(nh)) => {
                                match corrs[&r.change].atoms.get(&(*node, i)) {
                                    Some(idx) => mapped.push((*nh, *idx)),
                                    None => dropped += 1,
                                }
                            }
                            Some(Replacement::Removed(_)) => dropped += 1,
                            None => mapped.push((r.change, i)),
                        }
                    }
                }
                if dropped > 0 {
                    notes.push(format!(
                        "change {short}: {dropped} deletion(s) of lines that vanished were dropped"
                    ));
                }
                let mut ranges: Vec<AtomRange> = Vec::new();
                for (ch, i) in mapped {
                    match ranges.last_mut() {
                        Some(r) if r.change == ch && r.to == i => r.to = i + 1,
                        _ => ranges.push(AtomRange {
                            change: ch,
                            from: i,
                            to: i + 1,
                        }),
                    }
                }
                if !ranges.is_empty() {
                    edits.push(Edit::Delete {
                        node: *node,
                        atoms: ranges,
                    });
                }
            }
            other => edits.push(other.clone()),
        }
    }
    out.edits = edits;
    out.normalize();
    out
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hash::ObjectRef;
    use crate::ids::{ChangeId, NodeId};
    use crate::objects::{ChangeKind, Hlc, Mode, NodeKind};
    use crate::state::FileContent;

    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>, msg: &str) -> Change {
        let mut c = Change {
            version: crate::objects::CHANGE_VERSION,
            change_id: ChangeId::random(),
            deps,
            author: ObjectRef::ZERO,
            hlc: Hlc {
                wall_ms: 1,
                logical: 0,
            },
            message: msg.into(),
            tree_ops,
            edits,
            kind: ChangeKind::Normal,
        };
        c.normalize();
        c
    }

    #[test]
    fn describe_propagates_through_dependents() {
        let mut st = State::new();
        let f = NodeId::random();
        let c1 = change(
            vec![],
            vec![TreeOp::AddNode {
                node: f,
                kind: NodeKind::File,
                mode: Mode::TEXT,
                parent: NodeId::ROOT,
                name: "f".into(),
            }],
            vec![Edit::Insert {
                node: f,
                after: AtomRef::Start,
                before: AtomRef::End,
                lines: vec![b"a\n".to_vec(), b"b\n".to_vec()],
            }],
            "one",
        );
        let h1 = st.add(c1.clone()).unwrap();
        let c2 = change(
            vec![h1],
            vec![],
            vec![
                Edit::Delete {
                    node: f,
                    atoms: vec![AtomRange {
                        change: h1,
                        from: 0,
                        to: 1,
                    }],
                },
                Edit::Insert {
                    node: f,
                    after: AtomRef::Atom {
                        change: h1,
                        index: 1,
                    },
                    before: AtomRef::End,
                    lines: vec![b"c\n".to_vec()],
                },
            ],
            "two",
        );
        let h2 = st.add(c2.clone()).unwrap();
        let c3 = change(
            vec![h2],
            vec![TreeOp::SetMode {
                node: f,
                old: OpRef {
                    change: h1,
                    index: 0,
                },
                mode: Mode {
                    exec: true,
                    opaque: false,
                },
            }],
            vec![Edit::Insert {
                node: f,
                after: AtomRef::Atom {
                    change: h2,
                    index: 0,
                },
                before: AtomRef::End,
                lines: vec![b"d\n".to_vec()],
            }],
            "three",
        );
        let h3 = st.add(c3.clone()).unwrap();
        let before = st.materialize();

        // Rewrite c1's message; everything downstream follows.
        let mut n1 = c1.clone();
        n1.message = "one, described".into();
        let all: HashMap<ChangeHash, Change> =
            [(h1, c1.clone()), (h2, c2.clone()), (h3, c3.clone())]
                .into_iter()
                .collect();
        let load = |h: &ChangeHash| all.get(h).cloned();
        let rewritten = propagate(&st, h1, Some(&n1), &Correspondence::identity(&c1), &load)
            .unwrap()
            .changes;
        assert_eq!(
            rewritten.iter().map(|(h, _)| *h).collect::<Vec<_>>(),
            vec![h2, h3]
        );
        let mut st2 = State::new();
        st2.add(n1.clone()).unwrap();
        for (_, c) in &rewritten {
            st2.add(c.clone()).unwrap();
        }
        assert_eq!(st2.len(), 3);
        let after = st2.materialize();
        assert_eq!(after.files["f"].mode, before.files["f"].mode);
        match (&after.files["f"].content, &before.files["f"].content) {
            (FileContent::Text { bytes: a, .. }, FileContent::Text { bytes: b, .. }) => {
                assert_eq!(a, b)
            }
            _ => panic!(),
        }
        assert!(
            matches!(&after.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"b\nc\nd\n")
        );
        // ChangeIds survive; hashes change; deps point at the new hashes.
        assert_eq!(rewritten[0].1.change_id, c2.change_id);
        assert_eq!(rewritten[0].1.deps, vec![n1.hash()]);
        assert_ne!(rewritten[0].1.hash(), h2);
        assert_eq!(rewritten[1].1.deps, vec![rewritten[0].1.hash()]);
    }

    #[test]
    fn missing_counterpart_is_reanchored() {
        let mut st = State::new();
        let f = NodeId::random();
        let c1 = change(
            vec![],
            vec![TreeOp::AddNode {
                node: f,
                kind: NodeKind::File,
                mode: Mode::TEXT,
                parent: NodeId::ROOT,
                name: "f".into(),
            }],
            vec![Edit::Insert {
                node: f,
                after: AtomRef::Start,
                before: AtomRef::End,
                lines: vec![b"a\n".to_vec(), b"b\n".to_vec()],
            }],
            "one",
        );
        let h1 = st.add(c1.clone()).unwrap();
        let c2 = change(
            vec![h1],
            vec![],
            vec![Edit::Insert {
                node: f,
                after: AtomRef::Atom {
                    change: h1,
                    index: 1,
                },
                before: AtomRef::End,
                lines: vec![b"c\n".to_vec()],
            }],
            "two",
        );
        let h2 = st.add(c2.clone()).unwrap();
        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2)].into_iter().collect();
        let load = |h: &ChangeHash| all.get(h).cloned();
        // The rewritten c1 drops line "b": atom 1 has no counterpart, so c2's
        // insert after "b" is re-anchored after "a", the nearest survivor.
        let mut n1 = c1.clone();
        n1.edits = vec![Edit::Insert {
            node: f,
            after: AtomRef::Start,
            before: AtomRef::End,
            lines: vec![b"a\n".to_vec()],
        }];
        let corr = Correspondence {
            atoms: [((f, 0), 0)].into_iter().collect(),
            ops: [(0, 0)].into_iter().collect(),
        };
        let p = propagate(&st, h1, Some(&n1), &corr, &load).unwrap();
        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);
        let n1h = n1.hash();
        assert!(
            matches!(p.changes[0].1.edits[0], Edit::Insert { after: AtomRef::Atom { change, index: 0 }, before: AtomRef::End, .. } if change == n1h)
        );
        let mut st2 = State::new();
        st2.add(n1.clone()).unwrap();
        st2.add(p.changes[0].1.clone()).unwrap();
        let m = st2.materialize();
        assert!(!m.is_conflicted());
        assert!(
            matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"a\nc\n")
        );
        assert_eq!(
            propagate(&st, ObjectRef([9; 32]), Some(&n1), &corr, &load).unwrap_err(),
            RewriteError::Missing(ObjectRef([9; 32]))
        );

        // Removing c1 altogether: f vanishes with it, so c2's edit is dropped.
        let p = propagate(&st, h1, None, &Correspondence::default(), &load).unwrap();
        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);
        assert!(p.changes[0].1.edits.is_empty() && p.changes[0].1.deps.is_empty());

        // Rewriting c1 to keep the file but none of its lines: c2's line goes
        // to c1's chain anchors (START, END).
        let mut n2 = c1.clone();
        n2.edits = vec![];
        let corr = Correspondence {
            atoms: HashMap::new(),
            ops: [(0, 0)].into_iter().collect(),
        };
        let p = propagate(&st, h1, Some(&n2), &corr, &load).unwrap();
        assert!(matches!(
            p.changes[0].1.edits[0],
            Edit::Insert {
                after: AtomRef::Start,
                before: AtomRef::End,
                ..
            }
        ));
        let mut st3 = State::new();
        st3.add(n2.clone()).unwrap();
        st3.add(p.changes[0].1.clone()).unwrap();
        let m = st3.materialize();
        assert!(!m.is_conflicted());
        assert!(
            matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"c\n")
        );
    }

    #[test]
    fn removal_rewires_dependencies_or_fails_on_references() {
        let mut st = State::new();
        let f = NodeId::random();
        let g = NodeId::random();
        let c1 = change(
            vec![],
            vec![TreeOp::AddNode {
                node: f,
                kind: NodeKind::File,
                mode: Mode::TEXT,
                parent: NodeId::ROOT,
                name: "f".into(),
            }],
            vec![],
            "one",
        );
        let h1 = st.add(c1.clone()).unwrap();
        // c2 merely depends on c1 explicitly (touches another file).
        let c2 = change(
            vec![h1],
            vec![TreeOp::AddNode {
                node: g,
                kind: NodeKind::File,
                mode: Mode::TEXT,
                parent: NodeId::ROOT,
                name: "g".into(),
            }],
            vec![],
            "two",
        );
        let h2 = st.add(c2.clone()).unwrap();
        let c3 = change(
            vec![h2],
            vec![],
            vec![Edit::Insert {
                node: g,
                after: AtomRef::Start,
                before: AtomRef::End,
                lines: vec![b"x\n".to_vec()],
            }],
            "three",
        );
        let h3 = st.add(c3.clone()).unwrap();
        let mut all: HashMap<ChangeHash, Change> =
            [(h1, c1), (h2, c2), (h3, c3)].into_iter().collect();
        let load_all = all.clone();
        let load = move |h: &ChangeHash| load_all.get(h).cloned();
        // Removing c2 (an explicit-only dependency of nothing that references it) works: c3 inherits h1.
        let out = propagate(&st, h2, None, &Correspondence::default(), &load)
            .unwrap()
            .changes;
        assert_eq!(out.len(), 1);
        assert_eq!(out[0].0, h3);
        assert_eq!(out[0].1.deps, vec![h1]);
        // Removing c1 fails: c2 does not reference c1 (only an explicit dep), but
        // nothing else does either, so it succeeds and c2 inherits no deps.
        let out = propagate(&st, h1, None, &Correspondence::default(), &load)
            .unwrap()
            .changes;
        assert!(out.iter().any(|(h, c)| *h == h2 && c.deps.is_empty()));
        // Removing c2, which created g: c3's edit of g and c4's removal of g's
        // placement are dropped with notes, since the file no longer exists.
        let c4 = change(
            vec![h2],
            vec![TreeOp::RemoveNode {
                node: g,
                placement: OpRef {
                    change: h2,
                    index: 0,
                },
            }],
            vec![],
            "four",
        );
        let h4 = st.add(c4.clone()).unwrap();
        all.insert(h4, c4);
        let load2 = |h: &ChangeHash| all.get(h).cloned();
        let p = propagate(&st, h2, None, &Correspondence::default(), &load2).unwrap();
        assert_eq!(p.notes.len(), 2, "{:?}", p.notes);
        for (_, c) in &p.changes {
            assert!(c.edits.is_empty() && c.tree_ops.is_empty());
        }
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
