OXYGENHUB
# c792033af344 oxygen / crates / oxy-core / src / rewrite.rs
22.5 KiB · Rust · last changed Squash and rebase (spec 0.8 section 8.5): squash folds a change into a dependency with dependents following its atoms; rebase re-derives a change against another base with content-matched correspondence; correspondences keyed by node; spec 0.8a and docs 1 month ago source blame history raw
1 
//! Rewrite propagation (spec §8.4): when change `old` is replaced by `new`,
2 
//! every change that depends on `old` is rewritten with its references
3 
//! translated through a correspondence from `old`'s atoms and tree operations
4 
//! to `new`'s. Rewritten changes keep their ChangeIds.
5 
//!
6 
//! Where a reference has no counterpart it is reified rather than refused:
7 
//! an insert anchor moves to the nearest surviving atom of the same insert
8 
//! chain in `old`, else to that chain's own anchors (an order conflict then
9 
//! arises naturally if `new` placed other content there); deletions of
10 
//! vanished atoms are dropped; operations and edits on nodes that vanished
11 
//! are dropped. Every such adjustment is reported as a note.
12
13 
use crate::hash::ChangeHash;
14 
use crate::objects::{AtomRange, AtomRef, Change, Edit, OpRef, TreeOp};
15 
use crate::state::State;
16 
use std::collections::{BTreeSet, HashMap};
17
18 
/// How `old`'s atoms and tree operations map onto `new`'s.
19 
#[derive(Clone, Debug, Default, PartialEq, Eq)]
20 
pub struct Correspondence {
21 
    /// `(node, old atom index)` → new atom index. Absent means the atom no
22 
    /// longer exists.
23 
    pub atoms: HashMap<(crate::ids::NodeId, u32), u32>,
24 
    /// Old tree-op index → new tree-op index.
25 
    pub ops: HashMap<u32, u32>,
26 
}
27
28 
impl Correspondence {
29 
    /// Every atom and operation keeps its index: `new` has the same edits as `old`.
30 
    pub fn identity(change: &Change) -> Correspondence {
31 
        let mut atoms = HashMap::new();
32 
        let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();
33 
        for e in &change.edits {
34 
            if let Edit::Insert { node, lines, .. } = e {
35 
                let idx = per_node.entry(*node).or_default();
36 
                for _ in lines {
37 
                    atoms.insert((*node, *idx), *idx);
38 
                    *idx += 1;
39 
                }
40 
            }
41 
        }
42 
        let ops = (0..change.tree_ops.len() as u32).map(|i| (i, i)).collect();
43 
        Correspondence { atoms, ops }
44 
    }
45
46 
    /// Match `old`'s atoms to `new`'s by content, per node, in order (the
47 
    /// correspondence of a re-derived change, spec §8.5); operations match
48 
    /// by node and variant.
49 
    pub fn by_content(old: &Change, new: &Change) -> Correspondence {
50 
        let lines_of = |c: &Change| -> HashMap<crate::ids::NodeId, Vec<Vec<u8>>> {
51 
            let mut m: HashMap<crate::ids::NodeId, Vec<Vec<u8>>> = HashMap::new();
52 
            for e in &c.edits {
53 
                if let Edit::Insert { node, lines, .. } = e {
54 
                    m.entry(*node).or_default().extend(lines.iter().cloned());
55 
                }
56 
            }
57 
            m
58 
        };
59 
        let (a, b) = (lines_of(old), lines_of(new));
60 
        let mut atoms = HashMap::new();
61 
        for (node, olds) in &a {
62 
            let Some(news) = b.get(node) else { continue };
63 
            let mut j = 0usize;
64 
            for (i, line) in olds.iter().enumerate() {
65 
                while j < news.len() && news[j] != *line {
66 
                    j += 1;
67 
                }
68 
                if j < news.len() {
69 
                    atoms.insert((*node, i as u32), j as u32);
70 
                    j += 1;
71 
                }
72 
            }
73 
        }
74 
        let mut ops = HashMap::new();
75 
        for (i, op) in old.tree_ops.iter().enumerate() {
76 
            if let Some(j) = new.tree_ops.iter().position(|n| n.node() == op.node() && std::mem::discriminant(n) == std::mem::discriminant(op)) {
77 
                ops.insert(i as u32, j as u32);
78 
            }
79 
        }
80 
        Correspondence { atoms, ops }
81 
    }
82 
}
83
84 
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
85 
pub enum RewriteError {
86 
    #[error("change {0} is not in the state")]
87 
    Missing(ChangeHash),
88 
}
89
90 
/// The result of propagating a rewrite.
91 
#[derive(Clone, Debug, Default)]
92 
pub struct Propagation {
93 
    /// `(old hash, rewritten change)` in dependency order.
94 
    pub changes: Vec<(ChangeHash, Change)>,
95 
    /// Human-readable descriptions of reified orphaned references.
96 
    pub notes: Vec<String>,
97 
}
98
99 
/// Where each atom of a change was inserted: the chain it belongs to.
100 
struct Chain {
101 
    node: crate::ids::NodeId,
102 
    first: u32,
103 
    last: u32,
104 
    after: AtomRef,
105 
    before: AtomRef,
106 
}
107
108 
fn chains_of(c: &Change) -> Vec<Chain> {
109 
    let mut per_node: HashMap<crate::ids::NodeId, u32> = HashMap::new();
110 
    let mut out = Vec::new();
111 
    for e in &c.edits {
112 
        if let Edit::Insert { node, after, before, lines } = e {
113 
            let idx = per_node.entry(*node).or_default();
114 
            out.push(Chain { node: *node, first: *idx, last: *idx + lines.len() as u32 - 1, after: *after, before: *before });
115 
            *idx += lines.len() as u32;
116 
        }
117 
    }
118 
    out
119 
}
120
121 
/// What a rewritten change was replaced by.
122 
#[derive(Clone, Debug)]
123 
enum Replacement {
124 
    Change(ChangeHash),
125 
    /// Removed: dependents inherit these dependencies instead.
126 
    Removed(Vec<ChangeHash>),
127 
}
128
129 
/// Rewrite every change in `state` that depends on `old`, given `new` (or
130 
/// `None` when `old` is removed) and the correspondence between them.
131 
/// The result lists `(old hash, rewritten change)` pairs in dependency
132 
/// order, not including `old` → `new` itself, plus notes about reified
133 
/// orphaned references.
134 
///
135 
/// `load` fetches a change's full object (a state keeps only metadata).
136 
pub fn propagate(state: &State, old: ChangeHash, new: Option<&Change>, corr: &Correspondence, load: &dyn Fn(&ChangeHash) -> Option<Change>) -> Result<Propagation, RewriteError> {
137 
    let old_meta = state.get(&old).ok_or(RewriteError::Missing(old))?;
138 
    let old_full = load(&old);
139 
    let mut mapping: HashMap<ChangeHash, Replacement> = HashMap::new();
140 
    mapping.insert(old, match new {
141 
        Some(n) => Replacement::Change(n.hash()),
142 
        None => Replacement::Removed(old_meta.deps.clone()),
143 
    });
144 
    let mut corrs: HashMap<ChangeHash, Correspondence> = HashMap::new();
145 
    corrs.insert(old, corr.clone());
146 
    // Chains of the rewritten change, for re-anchoring; vanished nodes.
147 
    let chains: HashMap<ChangeHash, Vec<Chain>> = old_full.as_ref().map(|c| (old, chains_of(c))).into_iter().collect();
148 
    let mut vanished_nodes: BTreeSet<crate::ids::NodeId> = BTreeSet::new();
149 
    if let Some(c) = &old_full {
150 
        for (i, op) in c.tree_ops.iter().enumerate() {
151 
            if let TreeOp::AddNode { node, .. } = op {
152 
                let survives = new.is_some() && corr.ops.contains_key(&(i as u32));
153 
                if !survives {
154 
                    vanished_nodes.insert(*node);
155 
                }
156 
            }
157 
        }
158 
    }
159 
    let mut notes = Vec::new();
160
161 
    // Dependents in topological order: every change whose closure has `old`,
162 
    // sorted so that dependencies come first.
163 
    let mut dependents: Vec<ChangeHash> = state.changes().filter(|(h, _)| **h != old && state.closure(h).contains(&old)).map(|(h, _)| *h).collect();
164 
    dependents.sort_by_key(|h| (state.closure(h).len(), *h));
165
166 
    let mut out = Vec::new();
167 
    for h in dependents {
168 
        let c = load(&h).ok_or(RewriteError::Missing(h))?;
169 
        let rewritten = rewrite_one(&h, &c, &mapping, &corrs, &chains, &vanished_nodes, &mut notes);
170 
        let rh = rewritten.hash();
171 
        corrs.insert(h, Correspondence::identity(&rewritten));
172 
        mapping.insert(h, Replacement::Change(rh));
173 
        out.push((h, rewritten));
174 
    }
175 
    Ok(Propagation { changes: out, notes })
176 
}
177
178 
/// Re-anchor a reference to a vanished atom of `change`: the nearest
179 
/// surviving atom of its chain (before it for `after` anchors, after it for
180 
/// `before` anchors), else the chain's own anchor.
181 
fn reanchor(change: &ChangeHash, index: u32, want_after: bool, mapping: &HashMap<ChangeHash, Replacement>, corrs: &HashMap<ChangeHash, Correspondence>, chains: &HashMap<ChangeHash, Vec<Chain>>) -> AtomRef {
182 
    let corr = corrs.get(change);
183 
    let chain = chains.get(change).and_then(|cs| cs.iter().find(|ch| ch.first <= index && index <= ch.last));
184 
    if let (Some(Replacement::Change(nh)), Some(corr), Some(ch)) = (mapping.get(change), corr, chain) {
185 
        let candidates: Box<dyn Iterator<Item = u32>> = if want_after { Box::new((ch.first..index).rev()) } else { Box::new(index + 1..=ch.last) };
186 
        for j in candidates {
187 
            if let Some(nj) = corr.atoms.get(&(ch.node, j)) {
188 
                return AtomRef::Atom { change: *nh, index: *nj };
189 
            }
190 
        }
191 
    }
192 
    match chain {
193 
        Some(ch) => if want_after { ch.after } else { ch.before },
194 
        None => if want_after { AtomRef::Start } else { AtomRef::End },
195 
    }
196 
}
197
198 
fn rewrite_one(
199 
    hash: &ChangeHash,
200 
    c: &Change,
201 
    mapping: &HashMap<ChangeHash, Replacement>,
202 
    corrs: &HashMap<ChangeHash, Correspondence>,
203 
    chains: &HashMap<ChangeHash, Vec<Chain>>,
204 
    vanished_nodes: &BTreeSet<crate::ids::NodeId>,
205 
    notes: &mut Vec<String>,
206 
) -> Change {
207 
    let short = hash.short(12);
208 
    // An anchor: translate, or re-anchor when its counterpart is gone.
209 
    let map_anchor = |r: AtomRef, node: &crate::ids::NodeId, want_after: bool, notes: &mut Vec<String>| -> AtomRef {
210 
        match r {
211 
            AtomRef::Atom { change, index } => match mapping.get(&change) {
212 
                Some(Replacement::Change(nh)) => match corrs[&change].atoms.get(&(*node, index)) {
213 
                    Some(idx) => AtomRef::Atom { change: *nh, index: *idx },
214 
                    None => {
215 
                        notes.push(format!("change {short}: an anchor line of the rewritten change vanished; re-anchored to its nearest neighbour"));
216 
                        reanchor(&change, index, want_after, mapping, corrs, chains)
217 
                    }
218 
                },
219 
                Some(Replacement::Removed(_)) => {
220 
                    notes.push(format!("change {short}: an anchor line of the removed change vanished; re-anchored to its neighbours"));
221 
                    reanchor(&change, index, want_after, mapping, corrs, chains)
222 
                }
223 
                None => r,
224 
            },
225 
            other => other,
226 
        }
227 
    };
228 
    // A tree-operation reference: translate, or `None` when gone.
229 
    let map_op = |r: OpRef| -> Option<OpRef> {
230 
        match mapping.get(&r.change) {
231 
            Some(Replacement::Change(nh)) => corrs[&r.change].ops.get(&r.index).map(|idx| OpRef { change: *nh, index: *idx }),
232 
            Some(Replacement::Removed(_)) => None,
233 
            None => Some(r),
234 
        }
235 
    };
236 
    let mut out = c.clone();
237 
    let mut deps: BTreeSet<ChangeHash> = BTreeSet::new();
238 
    for d in &c.deps {
239 
        match mapping.get(d) {
240 
            Some(Replacement::Change(nh)) => {
241 
                deps.insert(*nh);
242 
            }
243 
            Some(Replacement::Removed(inherited)) => deps.extend(inherited.iter().copied()),
244 
            None => {
245 
                deps.insert(*d);
246 
            }
247 
        }
248 
    }
249 
    out.deps = deps.into_iter().collect();
250 
    let mut ops = Vec::new();
251 
    for op in &out.tree_ops {
252 
        let node = op.node();
253 
        if vanished_nodes.contains(&node) || matches!(op, TreeOp::AddNode { parent, .. } if vanished_nodes.contains(parent)) {
254 
            notes.push(format!("change {short}: an operation on a file that vanished with the rewritten change was dropped"));
255 
            continue;
256 
        }
257 
        match op {
258 
            TreeOp::RemoveNode { node, placement } => match map_op(*placement) {
259 
                Some(p) => ops.push(TreeOp::RemoveNode { node: *node, placement: p }),
260 
                None => notes.push(format!("change {short}: removal of a placement that vanished was dropped")),
261 
            },
262 
            TreeOp::Move { node, old, parent, name } => match map_op(*old) {
263 
                Some(o) => ops.push(TreeOp::Move { node: *node, old: o, parent: *parent, name: name.clone() }),
264 
                None => notes.push(format!("change {short}: a move of {name} lost its origin and was dropped")),
265 
            },
266 
            TreeOp::SetMode { node, old, mode } => match map_op(*old) {
267 
                Some(o) => ops.push(TreeOp::SetMode { node: *node, old: o, mode: *mode }),
268 
                None => notes.push(format!("change {short}: a mode change lost its origin and was dropped")),
269 
            },
270 
            add @ TreeOp::AddNode { .. } => ops.push(add.clone()),
271 
        }
272 
    }
273 
    out.tree_ops = ops;
274 
    let mut edits = Vec::new();
275 
    for e in &out.edits {
276 
        if vanished_nodes.contains(&e.node()) {
277 
            notes.push(format!("change {short}: an edit of a file that vanished with the rewritten change was dropped"));
278 
            continue;
279 
        }
280 
        match e {
281 
            Edit::Insert { node, after, before, lines } => edits.push(Edit::Insert {
282 
                node: *node,
283 
                after: map_anchor(*after, node, true, notes),
284 
                before: map_anchor(*before, node, false, notes),
285 
                lines: lines.clone(),
286 
            }),
287 
            Edit::Delete { node, atoms } => {
288 
                let mut mapped: Vec<(ChangeHash, u32)> = Vec::new();
289 
                let mut dropped = 0;
290 
                for r in atoms.iter() {
291 
                    for i in r.from..r.to {
292 
                        match mapping.get(&r.change) {
293 
                            Some(Replacement::Change(nh)) => match corrs[&r.change].atoms.get(&(*node, i)) {
294 
                                Some(idx) => mapped.push((*nh, *idx)),
295 
                                None => dropped += 1,
296 
                            },
297 
                            Some(Replacement::Removed(_)) => dropped += 1,
298 
                            None => mapped.push((r.change, i)),
299 
                        }
300 
                    }
301 
                }
302 
                if dropped > 0 {
303 
                    notes.push(format!("change {short}: {dropped} deletion(s) of lines that vanished were dropped"));
304 
                }
305 
                let mut ranges: Vec<AtomRange> = Vec::new();
306 
                for (ch, i) in mapped {
307 
                    match ranges.last_mut() {
308 
                        Some(r) if r.change == ch && r.to == i => r.to = i + 1,
309 
                        _ => ranges.push(AtomRange { change: ch, from: i, to: i + 1 }),
310 
                    }
311 
                }
312 
                if !ranges.is_empty() {
313 
                    edits.push(Edit::Delete { node: *node, atoms: ranges });
314 
                }
315 
            }
316 
            other => edits.push(other.clone()),
317 
        }
318 
    }
319 
    out.edits = edits;
320 
    out.normalize();
321 
    out
322 
}
323
324 
#[cfg(test)]
325 
mod tests {
326 
    use super::*;
327 
    use crate::hash::ObjectRef;
328 
    use crate::ids::{ChangeId, NodeId};
329 
    use crate::objects::{ChangeKind, Hlc, Mode, NodeKind};
330 
    use crate::state::FileContent;
331
332 
    fn change(deps: Vec<ChangeHash>, tree_ops: Vec<TreeOp>, edits: Vec<Edit>, msg: &str) -> Change {
333 
        let mut c = Change { change_id: ChangeId::random(), deps, author: ObjectRef::ZERO, hlc: Hlc { wall_ms: 1, logical: 0 }, message: msg.into(), tree_ops, edits, kind: ChangeKind::Normal };
334 
        c.normalize();
335 
        c
336 
    }
337
338 
    #[test]
339 
    fn describe_propagates_through_dependents() {
340 
        let mut st = State::new();
341 
        let f = NodeId::random();
342 
        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");
343 
        let h1 = st.add(c1.clone()).unwrap();
344 
        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");
345 
        let h2 = st.add(c2.clone()).unwrap();
346 
        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");
347 
        let h3 = st.add(c3.clone()).unwrap();
348 
        let before = st.materialize();
349
350 
        // Rewrite c1's message; everything downstream follows.
351 
        let mut n1 = c1.clone();
352 
        n1.message = "one, described".into();
353 
        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2.clone()), (h3, c3.clone())].into_iter().collect();
354 
        let load = |h: &ChangeHash| all.get(h).cloned();
355 
        let rewritten = propagate(&st, h1, Some(&n1), &Correspondence::identity(&c1), &load).unwrap().changes;
356 
        assert_eq!(rewritten.iter().map(|(h, _)| *h).collect::<Vec<_>>(), vec![h2, h3]);
357 
        let mut st2 = State::new();
358 
        st2.add(n1.clone()).unwrap();
359 
        for (_, c) in &rewritten {
360 
            st2.add(c.clone()).unwrap();
361 
        }
362 
        assert_eq!(st2.len(), 3);
363 
        let after = st2.materialize();
364 
        assert_eq!(after.files["f"].mode, before.files["f"].mode);
365 
        match (&after.files["f"].content, &before.files["f"].content) {
366 
            (FileContent::Text { bytes: a, .. }, FileContent::Text { bytes: b, .. }) => assert_eq!(a, b),
367 
            _ => panic!(),
368 
        }
369 
        assert!(matches!(&after.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"b\nc\nd\n"));
370 
        // ChangeIds survive; hashes change; deps point at the new hashes.
371 
        assert_eq!(rewritten[0].1.change_id, c2.change_id);
372 
        assert_eq!(rewritten[0].1.deps, vec![n1.hash()]);
373 
        assert_ne!(rewritten[0].1.hash(), h2);
374 
        assert_eq!(rewritten[1].1.deps, vec![rewritten[0].1.hash()]);
375 
    }
376
377 
    #[test]
378 
    fn missing_counterpart_is_reanchored() {
379 
        let mut st = State::new();
380 
        let f = NodeId::random();
381 
        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");
382 
        let h1 = st.add(c1.clone()).unwrap();
383 
        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");
384 
        let h2 = st.add(c2.clone()).unwrap();
385 
        let all: HashMap<ChangeHash, Change> = [(h1, c1.clone()), (h2, c2)].into_iter().collect();
386 
        let load = |h: &ChangeHash| all.get(h).cloned();
387 
        // The rewritten c1 drops line "b": atom 1 has no counterpart, so c2's
388 
        // insert after "b" is re-anchored after "a", the nearest survivor.
389 
        let mut n1 = c1.clone();
390 
        n1.edits = vec![Edit::Insert { node: f, after: AtomRef::Start, before: AtomRef::End, lines: vec![b"a\n".to_vec()] }];
391 
        let corr = Correspondence { atoms: [((f, 0), 0)].into_iter().collect(), ops: [(0, 0)].into_iter().collect() };
392 
        let p = propagate(&st, h1, Some(&n1), &corr, &load).unwrap();
393 
        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);
394 
        let n1h = n1.hash();
395 
        assert!(matches!(p.changes[0].1.edits[0], Edit::Insert { after: AtomRef::Atom { change, index: 0 }, before: AtomRef::End, .. } if change == n1h));
396 
        let mut st2 = State::new();
397 
        st2.add(n1.clone()).unwrap();
398 
        st2.add(p.changes[0].1.clone()).unwrap();
399 
        let m = st2.materialize();
400 
        assert!(!m.is_conflicted());
401 
        assert!(matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"a\nc\n"));
402 
        assert_eq!(propagate(&st, ObjectRef([9; 32]), Some(&n1), &corr, &load).unwrap_err(), RewriteError::Missing(ObjectRef([9; 32])));
403
404 
        // Removing c1 altogether: f vanishes with it, so c2's edit is dropped.
405 
        let p = propagate(&st, h1, None, &Correspondence::default(), &load).unwrap();
406 
        assert_eq!(p.notes.len(), 1, "{:?}", p.notes);
407 
        assert!(p.changes[0].1.edits.is_empty() && p.changes[0].1.deps.is_empty());
408
409 
        // Rewriting c1 to keep the file but none of its lines: c2's line goes
410 
        // to c1's chain anchors (START, END).
411 
        let mut n2 = c1.clone();
412 
        n2.edits = vec![];
413 
        let corr = Correspondence { atoms: HashMap::new(), ops: [(0, 0)].into_iter().collect() };
414 
        let p = propagate(&st, h1, Some(&n2), &corr, &load).unwrap();
415 
        assert!(matches!(p.changes[0].1.edits[0], Edit::Insert { after: AtomRef::Start, before: AtomRef::End, .. }));
416 
        let mut st3 = State::new();
417 
        st3.add(n2.clone()).unwrap();
418 
        st3.add(p.changes[0].1.clone()).unwrap();
419 
        let m = st3.materialize();
420 
        assert!(!m.is_conflicted());
421 
        assert!(matches!(&m.files["f"].content, FileContent::Text { bytes, .. } if bytes == b"c\n"));
422 
    }
423
424 
    #[test]
425 
    fn removal_rewires_dependencies_or_fails_on_references() {
426 
        let mut st = State::new();
427 
        let f = NodeId::random();
428 
        let g = NodeId::random();
429 
        let c1 = change(vec![], vec![TreeOp::AddNode { node: f, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "f".into() }], vec![], "one");
430 
        let h1 = st.add(c1.clone()).unwrap();
431 
        // c2 merely depends on c1 explicitly (touches another file).
432 
        let c2 = change(vec![h1], vec![TreeOp::AddNode { node: g, kind: NodeKind::File, mode: Mode::TEXT, parent: NodeId::ROOT, name: "g".into() }], vec![], "two");
433 
        let h2 = st.add(c2.clone()).unwrap();
434 
        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");
435 
        let h3 = st.add(c3.clone()).unwrap();
436 
        let mut all: HashMap<ChangeHash, Change> = [(h1, c1), (h2, c2), (h3, c3)].into_iter().collect();
437 
        let load_all = all.clone();
438 
        let load = move |h: &ChangeHash| load_all.get(h).cloned();
439 
        // Removing c2 (an explicit-only dependency of nothing that references it) works: c3 inherits h1.
440 
        let out = propagate(&st, h2, None, &Correspondence::default(), &load).unwrap().changes;
441 
        assert_eq!(out.len(), 1);
442 
        assert_eq!(out[0].0, h3);
443 
        assert_eq!(out[0].1.deps, vec![h1]);
444 
        // Removing c1 fails: c2 does not reference c1 (only an explicit dep), but
445 
        // nothing else does either, so it succeeds and c2 inherits no deps.
446 
        let out = propagate(&st, h1, None, &Correspondence::default(), &load).unwrap().changes;
447 
        assert!(out.iter().any(|(h, c)| *h == h2 && c.deps.is_empty()));
448 
        // Removing c2, which created g: c3's edit of g and c4's removal of g's
449 
        // placement are dropped with notes, since the file no longer exists.
450 
        let c4 = change(vec![h2], vec![TreeOp::RemoveNode { node: g, placement: OpRef { change: h2, index: 0 } }], vec![], "four");
451 
        let h4 = st.add(c4.clone()).unwrap();
452 
        all.insert(h4, c4);
453 
        let load2 = |h: &ChangeHash| all.get(h).cloned();
454 
        let p = propagate(&st, h2, None, &Correspondence::default(), &load2).unwrap();
455 
        assert_eq!(p.notes.len(), 2, "{:?}", p.notes);
456 
        for (_, c) in &p.changes {
457 
            assert!(c.edits.is_empty() && c.tree_ops.is_empty());
458 
        }
459 
    }
460 
}