Using id_map everywhere except testssyntax_id_on_vertex

7 files changed, 378 insertions, 256 deletions

diff --git a/src/diff/changes.rs b/src/diff/changes.rs
index dd6028079..e682d68bc 100644
--- a/src/diff/changes.rs
+++ b/src/diff/changes.rs
@@ -2,38 +2,42 @@
 
 use crate::{
     hash::DftHashMap,
-    parse::syntax::{Syntax, SyntaxId},
+    parse::syntax::{Syntax, SyntaxId, SyntaxIdMap},
 };
 
 #[derive(PartialEq, Eq, Clone, Copy)]
-pub(crate) enum ChangeKind<'a> {
-    Unchanged(&'a Syntax<'a>),
-    ReplacedComment(&'a Syntax<'a>, &'a Syntax<'a>),
-    ReplacedString(&'a Syntax<'a>, &'a Syntax<'a>),
+pub(crate) enum ChangeKind {
+    Unchanged(SyntaxId),
+    ReplacedComment(SyntaxId, SyntaxId),
+    ReplacedString(SyntaxId, SyntaxId),
     Novel,
 }
 
 #[derive(Debug, Default)]
-pub(crate) struct ChangeMap<'a> {
-    changes: DftHashMap<SyntaxId, ChangeKind<'a>>,
+pub(crate) struct ChangeMap {
+    changes: DftHashMap<SyntaxId, ChangeKind>,
 }
 
-impl<'a> ChangeMap<'a> {
-    pub(crate) fn insert(&mut self, node: &'a Syntax<'a>, ck: ChangeKind<'a>) {
-        self.changes.insert(node.id(), ck);
+impl ChangeMap {
+    pub(crate) fn insert(&mut self, node: SyntaxId, ck: ChangeKind) {
+        self.changes.insert(node, ck);
     }
 
-    pub(crate) fn get(&self, node: &Syntax<'a>) -> Option<ChangeKind<'a>> {
-        self.changes.get(&node.id()).copied()
+    pub(crate) fn get(&self, node: SyntaxId) -> Option<ChangeKind> {
+        self.changes.get(&node).copied()
     }
 }
 
-pub(crate) fn insert_deep_unchanged<'a>(
-    node: &'a Syntax<'a>,
-    opposite_node: &'a Syntax<'a>,
-    change_map: &mut ChangeMap<'a>,
+pub(crate) fn insert_deep_unchanged<'s>(
+    node_id: SyntaxId,
+    opposite_node_id: SyntaxId,
+    id_map: &SyntaxIdMap<'s>,
+    change_map: &mut ChangeMap,
 ) {
-    change_map.insert(node, ChangeKind::Unchanged(opposite_node));
+    let node = id_map[&node_id];
+    let opposite_node = id_map[&opposite_node_id];
+
+    change_map.insert(node_id, ChangeKind::Unchanged(opposite_node_id));
 
     match (node, opposite_node) {
         (
@@ -47,7 +51,7 @@ pub(crate) fn insert_deep_unchanged<'a>(
             },
         ) => {
             for (child, opposite_child) in node_children.iter().zip(opposite_children) {
-                insert_deep_unchanged(child, opposite_child, change_map);
+                insert_deep_unchanged(child.id(), opposite_child.id(), id_map, change_map);
             }
         }
         (Syntax::Atom { .. }, Syntax::Atom { .. }) => {}
@@ -55,12 +59,17 @@ pub(crate) fn insert_deep_unchanged<'a>(
     }
 }
 
-pub(crate) fn insert_deep_novel<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap<'a>) {
-    change_map.insert(node, ChangeKind::Novel);
+pub(crate) fn insert_deep_novel<'s>(
+    node_id: SyntaxId,
+    id_map: &SyntaxIdMap<'s>,
+    change_map: &mut ChangeMap,
+) {
+    change_map.insert(node_id, ChangeKind::Novel);
 
+    let node = id_map[&node_id];
     if let Syntax::List { children, .. } = node {
         for child in children.iter() {
-            insert_deep_novel(child, change_map);
+            insert_deep_novel(child.id(), id_map, change_map);
         }
     }
 }
diff --git a/src/diff/dijkstra.rs b/src/diff/dijkstra.rs
index 20efc4129..a0d97bb84 100644
--- a/src/diff/dijkstra.rs
+++ b/src/diff/dijkstra.rs
@@ -193,7 +193,7 @@ fn tree_count(root: Option<&Syntax>) -> u32 {
 pub(crate) fn mark_syntax<'a>(
     lhs_syntax_id: Option<SyntaxId>,
     rhs_syntax_id: Option<SyntaxId>,
-    change_map: &mut ChangeMap<'a>,
+    change_map: &mut ChangeMap,
     graph_limit: usize,
     id_map: &DftHashMap<NonZeroU32, &'a Syntax<'a>>,
 ) -> Result<(), ExceededGraphLimit> {
@@ -226,7 +226,7 @@ pub(crate) fn mark_syntax<'a>(
     // than graph_limit nodes.
     let size_hint = std::cmp::min(lhs_node_count * rhs_node_count, graph_limit);
 
-    let start = Vertex::new(lhs_syntax, rhs_syntax);
+    let start = Vertex::new(lhs_syntax.map(|n| n.id()), rhs_syntax.map(|n| n.id()));
     let vertex_arena = Bump::new();
 
     let route = shortest_path(start, &vertex_arena, size_hint, graph_limit, id_map)?;
@@ -245,9 +245,9 @@ pub(crate) fn mark_syntax<'a>(
                 format!(
                     "{:20} {:20} --- {:3} {:?}",
                     v.lhs_syntax
-                        .map_or_else(|| "None".into(), Syntax::dbg_content),
+                        .map_or_else(|| "None".into(), |id| Syntax::dbg_content(id_map[&id])),
                     v.rhs_syntax
-                        .map_or_else(|| "None".into(), Syntax::dbg_content),
+                        .map_or_else(|| "None".into(), |id| Syntax::dbg_content(id_map[&id])),
                     edge.cost(),
                     edge,
                 )
@@ -293,7 +293,7 @@ mod tests {
 
         let id_map = build_id_map(&[lhs], &[rhs]);
 
-        let start = Vertex::new(Some(lhs), Some(rhs));
+        let start = Vertex::new(Some(lhs.id()), Some(rhs.id()));
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -337,7 +337,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -381,7 +384,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -429,7 +435,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -472,7 +481,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -506,7 +518,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -548,7 +563,10 @@ mod tests {
 
         let id_map = build_id_map(&lhs, &rhs);
 
-        let start = Vertex::new(lhs.get(0).copied(), rhs.get(0).copied());
+        let start = Vertex::new(
+            lhs.get(0).copied().map(|n| n.id()),
+            rhs.get(0).copied().map(|n| n.id()),
+        );
         let vertex_arena = Bump::new();
         let route = shortest_path(start, &vertex_arena, 0, DEFAULT_GRAPH_LIMIT, &id_map).unwrap();
 
@@ -583,8 +601,14 @@ mod tests {
         )
         .unwrap();
 
-        assert_eq!(change_map.get(lhs), Some(ChangeKind::Unchanged(rhs)));
-        assert_eq!(change_map.get(rhs), Some(ChangeKind::Unchanged(lhs)));
+        assert_eq!(
+            change_map.get(lhs.id()),
+            Some(ChangeKind::Unchanged(rhs.id()))
+        );
+        assert_eq!(
+            change_map.get(rhs.id()),
+            Some(ChangeKind::Unchanged(lhs.id()))
+        );
     }
 
     #[test]
@@ -605,7 +629,7 @@ mod tests {
             &id_map,
         )
         .unwrap();
-        assert_eq!(change_map.get(lhs), Some(ChangeKind::Novel));
-        assert_eq!(change_map.get(rhs), Some(ChangeKind::Novel));
+        assert_eq!(change_map.get(lhs.id()), Some(ChangeKind::Novel));
+        assert_eq!(change_map.get(rhs.id()), Some(ChangeKind::Novel));
     }
 }
diff --git a/src/diff/graph.rs b/src/diff/graph.rs
index 7ea7ed38f..9b73c6c43 100644
--- a/src/diff/graph.rs
+++ b/src/diff/graph.rs
@@ -19,7 +19,7 @@ use crate::{
         stack::Stack,
     },
     hash::DftHashMap,
-    parse::syntax::{AtomKind, Syntax, SyntaxId},
+    parse::syntax::{AtomKind, Syntax, SyntaxId, SyntaxIdMap},
 };
 
 /// A vertex in a directed acyclic graph that represents a diff.
@@ -54,11 +54,9 @@ use crate::{
 pub(crate) struct Vertex<'s, 'b> {
     pub(crate) neighbours: RefCell<Option<&'b [(Edge, &'b Vertex<'s, 'b>)]>>,
     pub(crate) predecessor: Cell<Option<(u32, &'b Vertex<'s, 'b>)>>,
-    // TODO: experiment with storing SyntaxId only, and have a HashMap
-    // from SyntaxId to &Syntax.
-    pub(crate) lhs_syntax: Option<&'s Syntax<'s>>,
-    pub(crate) rhs_syntax: Option<&'s Syntax<'s>>,
-    parents: Stack<'b, EnteredDelimiter<'s, 'b>>,
+    pub(crate) lhs_syntax: Option<SyntaxId>,
+    pub(crate) rhs_syntax: Option<SyntaxId>,
+    parents: Stack<'b, EnteredDelimiter<'b>>,
     lhs_parent_id: Option<SyntaxId>,
     rhs_parent_id: Option<SyntaxId>,
 }
@@ -82,12 +80,12 @@ impl<'s, 'b> PartialEq for Vertex<'s, 'b> {
         // more vertices to be distinct, exponentially increasing
         // the graph size relative to tree depth.
         let b0 = match (self.lhs_syntax, other.lhs_syntax) {
-            (Some(s0), Some(s1)) => s0.id() == s1.id(),
+            (Some(s0), Some(s1)) => s0 == s1,
             (None, None) => self.lhs_parent_id == other.lhs_parent_id,
             _ => false,
         };
         let b1 = match (self.rhs_syntax, other.rhs_syntax) {
-            (Some(s0), Some(s1)) => s0.id() == s1.id(),
+            (Some(s0), Some(s1)) => s0 == s1,
             (None, None) => self.rhs_parent_id == other.rhs_parent_id,
             _ => false,
         };
@@ -105,8 +103,8 @@ impl<'s, 'b> Eq for Vertex<'s, 'b> {}
 
 impl<'s, 'b> Hash for Vertex<'s, 'b> {
     fn hash<H: Hasher>(&self, state: &mut H) {
-        self.lhs_syntax.map(|node| node.id()).hash(state);
-        self.rhs_syntax.map(|node| node.id()).hash(state);
+        self.lhs_syntax.hash(state);
+        self.rhs_syntax.hash(state);
 
         self.lhs_parent_id.hash(state);
         self.rhs_parent_id.hash(state);
@@ -116,12 +114,12 @@ impl<'s, 'b> Hash for Vertex<'s, 'b> {
 
 /// Tracks entering syntax List nodes.
 #[derive(Clone, PartialEq)]
-enum EnteredDelimiter<'s, 'b> {
+enum EnteredDelimiter<'b> {
     /// If we've entered the LHS or RHS separately, we can pop either
     /// side independently.
     ///
     /// Assumes that at least one stack is non-empty.
-    PopEither((Stack<'b, &'s Syntax<'s>>, Stack<'b, &'s Syntax<'s>>)),
+    PopEither((Stack<'b, SyntaxId>, Stack<'b, SyntaxId>)),
     /// If we've entered the LHS and RHS together, we must pop both
     /// sides together too. Otherwise we'd consider the following case to have no changes.
     ///
@@ -129,10 +127,10 @@ enum EnteredDelimiter<'s, 'b> {
     /// Old: (a b c)
     /// New: (a b) c
     /// ```
-    PopBoth((&'s Syntax<'s>, &'s Syntax<'s>)),
+    PopBoth((SyntaxId, SyntaxId)),
 }
 
-impl<'s, 'b> fmt::Debug for EnteredDelimiter<'s, 'b> {
+impl<'b> fmt::Debug for EnteredDelimiter<'b> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         let desc = match self {
             EnteredDelimiter::PopEither((lhs_delims, rhs_delims)) => {
@@ -148,12 +146,12 @@ impl<'s, 'b> fmt::Debug for EnteredDelimiter<'s, 'b> {
     }
 }
 
-fn push_both_delimiters<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
-    lhs_delim: &'s Syntax<'s>,
-    rhs_delim: &'s Syntax<'s>,
+fn push_both_delimiters<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
+    lhs_delim: SyntaxId,
+    rhs_delim: SyntaxId,
     alloc: &'b Bump,
-) -> Stack<'b, EnteredDelimiter<'s, 'b>> {
+) -> Stack<'b, EnteredDelimiter<'b>> {
     entered.push(EnteredDelimiter::PopBoth((lhs_delim, rhs_delim)), alloc)
 }
 
@@ -161,25 +159,21 @@ fn can_pop_either_parent(entered: &Stack<EnteredDelimiter>) -> bool {
     matches!(entered.peek(), Some(EnteredDelimiter::PopEither(_)))
 }
 
-fn try_pop_both<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
-) -> Option<(
-    &'s Syntax<'s>,
-    &'s Syntax<'s>,
-    Stack<'b, EnteredDelimiter<'s, 'b>>,
-)> {
+fn try_pop_both<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
+) -> Option<(SyntaxId, SyntaxId, Stack<'b, EnteredDelimiter<'b>>)> {
     match entered.peek() {
         Some(EnteredDelimiter::PopBoth((lhs_delim, rhs_delim))) => {
-            Some((lhs_delim, rhs_delim, entered.pop().unwrap()))
+            Some((*lhs_delim, *rhs_delim, entered.pop().unwrap()))
         }
         _ => None,
     }
 }
 
-fn try_pop_lhs<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
+fn try_pop_lhs<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
     alloc: &'b Bump,
-) -> Option<(&'s Syntax<'s>, Stack<'b, EnteredDelimiter<'s, 'b>>)> {
+) -> Option<(SyntaxId, Stack<'b, EnteredDelimiter<'b>>)> {
     match entered.peek() {
         Some(EnteredDelimiter::PopEither((lhs_delims, rhs_delims))) => match lhs_delims.peek() {
             Some(lhs_delim) => {
@@ -193,7 +187,7 @@ fn try_pop_lhs<'s, 'b>(
                     );
                 }
 
-                Some((lhs_delim, entered))
+                Some((*lhs_delim, entered))
             }
             None => None,
         },
@@ -201,10 +195,10 @@ fn try_pop_lhs<'s, 'b>(
     }
 }
 
-fn try_pop_rhs<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
+fn try_pop_rhs<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
     alloc: &'b Bump,
-) -> Option<(&'s Syntax<'s>, Stack<'b, EnteredDelimiter<'s, 'b>>)> {
+) -> Option<(SyntaxId, Stack<'b, EnteredDelimiter<'b>>)> {
     match entered.peek() {
         Some(EnteredDelimiter::PopEither((lhs_delims, rhs_delims))) => match rhs_delims.peek() {
             Some(rhs_delim) => {
@@ -218,7 +212,7 @@ fn try_pop_rhs<'s, 'b>(
                     );
                 }
 
-                Some((rhs_delim, entered))
+                Some((*rhs_delim, entered))
             }
             None => None,
         },
@@ -226,11 +220,11 @@ fn try_pop_rhs<'s, 'b>(
     }
 }
 
-fn push_lhs_delimiter<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
-    delimiter: &'s Syntax<'s>,
+fn push_lhs_delimiter<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
+    delimiter: SyntaxId,
     alloc: &'b Bump,
-) -> Stack<'b, EnteredDelimiter<'s, 'b>> {
+) -> Stack<'b, EnteredDelimiter<'b>> {
     match entered.peek() {
         Some(EnteredDelimiter::PopEither((lhs_delims, rhs_delims))) => entered.pop().unwrap().push(
             EnteredDelimiter::PopEither((lhs_delims.push(delimiter, alloc), rhs_delims.clone())),
@@ -243,11 +237,11 @@ fn push_lhs_delimiter<'s, 'b>(
     }
 }
 
-fn push_rhs_delimiter<'s, 'b>(
-    entered: &Stack<'b, EnteredDelimiter<'s, 'b>>,
-    delimiter: &'s Syntax<'s>,
+fn push_rhs_delimiter<'b>(
+    entered: &Stack<'b, EnteredDelimiter<'b>>,
+    delimiter: SyntaxId,
     alloc: &'b Bump,
-) -> Stack<'b, EnteredDelimiter<'s, 'b>> {
+) -> Stack<'b, EnteredDelimiter<'b>> {
     match entered.peek() {
         Some(EnteredDelimiter::PopEither((lhs_delims, rhs_delims))) => entered.pop().unwrap().push(
             EnteredDelimiter::PopEither((lhs_delims.clone(), rhs_delims.push(delimiter, alloc))),
@@ -265,10 +259,7 @@ impl<'s, 'b> Vertex<'s, 'b> {
         self.lhs_syntax.is_none() && self.rhs_syntax.is_none() && self.parents.is_empty()
     }
 
-    pub(crate) fn new(
-        lhs_syntax: Option<&'s Syntax<'s>>,
-        rhs_syntax: Option<&'s Syntax<'s>>,
-    ) -> Self {
+    pub(crate) fn new(lhs_syntax: Option<SyntaxId>, rhs_syntax: Option<SyntaxId>) -> Self {
         let parents = Stack::new();
         Vertex {
             neighbours: RefCell::new(None),
@@ -426,59 +417,64 @@ fn looks_like_punctuation(node: &Syntax) -> bool {
 /// Pop as many parents of `lhs_node` and `rhs_node` as
 /// possible. Return the new syntax nodes and parents.
 fn pop_all_parents<'s, 'b>(
-    lhs_node: Option<&'s Syntax<'s>>,
-    rhs_node: Option<&'s Syntax<'s>>,
+    lhs_node_id: Option<SyntaxId>,
+    rhs_node_id: Option<SyntaxId>,
     lhs_parent_id: Option<SyntaxId>,
     rhs_parent_id: Option<SyntaxId>,
-    parents: &Stack<'b, EnteredDelimiter<'s, 'b>>,
+    parents: &Stack<'b, EnteredDelimiter<'b>>,
     alloc: &'b Bump,
-    id_map: &DftHashMap<SyntaxId, &'s Syntax<'s>>,
+    id_map: &SyntaxIdMap<'s>,
 ) -> (
-    Option<&'s Syntax<'s>>,
-    Option<&'s Syntax<'s>>,
     Option<SyntaxId>,
     Option<SyntaxId>,
-    Stack<'b, EnteredDelimiter<'s, 'b>>,
+    Option<SyntaxId>,
+    Option<SyntaxId>,
+    Stack<'b, EnteredDelimiter<'b>>,
 ) {
-    let mut lhs_node = lhs_node;
-    let mut rhs_node = rhs_node;
-    let mut lhs_parent_id = lhs_parent_id;
-    let mut rhs_parent_id = rhs_parent_id;
+    let mut lhs_node_id: Option<SyntaxId> = lhs_node_id;
+    let mut rhs_node_id: Option<SyntaxId> = rhs_node_id;
+    let mut lhs_parent_id: Option<SyntaxId> = lhs_parent_id;
+    let mut rhs_parent_id: Option<SyntaxId> = rhs_parent_id;
     let mut parents = parents.clone();
 
     loop {
-        if lhs_node.is_none() {
-            if let Some((lhs_parent, parents_next)) = try_pop_lhs(&parents, alloc) {
+        if lhs_node_id.is_none() {
+            if let Some((lhs_parent_id_, parents_next)) = try_pop_lhs(&parents, alloc) {
+                let lhs_parent = id_map[&lhs_parent_id_];
                 // Move to next after LHS parent.
 
                 // Continue from sibling of parent.
-                lhs_node = lhs_parent.next_sibling();
-                lhs_parent_id = lhs_parent.parent().map(Syntax::id);
+                lhs_node_id = lhs_parent.next_sibling().map(|n| n.id());
+                lhs_parent_id = lhs_parent.parent().map(|n| n.id());
                 parents = parents_next;
                 continue;
             }
         }
 
-        if rhs_node.is_none() {
-            if let Some((rhs_parent, parents_next)) = try_pop_rhs(&parents, alloc) {
+        if rhs_node_id.is_none() {
+            if let Some((rhs_parent_id_, parents_next)) = try_pop_rhs(&parents, alloc) {
+                let rhs_parent = id_map[&rhs_parent_id_];
                 // Move to next after RHS parent.
 
                 // Continue from sibling of parent.
-                rhs_node = rhs_parent.next_sibling();
+                rhs_node_id = rhs_parent.next_sibling().map(|n| n.id());
                 rhs_parent_id = rhs_parent.parent().map(Syntax::id);
                 parents = parents_next;
                 continue;
             }
         }
 
-        if lhs_node.is_none() && rhs_node.is_none() {
+        if lhs_node_id.is_none() && rhs_node_id.is_none() {
             // We have exhausted all the nodes on both lists, so we can
             // move up to the parent node.
 
             // Continue from sibling of parent.
-            if let Some((lhs_parent, rhs_parent, parents_next)) = try_pop_both(&parents) {
-                lhs_node = lhs_parent.next_sibling();
-                rhs_node = rhs_parent.next_sibling();
+            if let Some((lhs_parent_id_, rhs_parent_id_, parents_next)) = try_pop_both(&parents) {
+                let lhs_parent = id_map[&lhs_parent_id_];
+                let rhs_parent = id_map[&rhs_parent_id_];
+
+                lhs_node_id = lhs_parent.next_sibling().map(|n| n.id());
+                rhs_node_id = rhs_parent.next_sibling().map(|n| n.id());
                 lhs_parent_id = lhs_parent.parent().map(Syntax::id);
                 rhs_parent_id = rhs_parent.parent().map(Syntax::id);
                 parents = parents_next;
@@ -489,7 +485,13 @@ fn pop_all_parents<'s, 'b>(
         break;
     }
 
-    (lhs_node, rhs_node, lhs_parent_id, rhs_parent_id, parents)
+    (
+        lhs_node_id,
+        rhs_node_id,
+        lhs_parent_id,
+        rhs_parent_id,
+        parents,
+    )
 }
 
 /// Compute the neighbours of `v` if we haven't previously done so,
@@ -498,7 +500,7 @@ pub(crate) fn set_neighbours<'s, 'b>(
     v: &Vertex<'s, 'b>,
     alloc: &'b Bump,
     seen: &mut DftHashMap<&Vertex<'s, 'b>, SmallVec<[&'b Vertex<'s, 'b>; 2]>>,
-    id_map: &DftHashMap<SyntaxId, &'s Syntax<'s>>,
+    id_map: &SyntaxIdMap<'s>,
 ) {
     if v.neighbours.borrow().is_some() {
         return;
@@ -507,7 +509,10 @@ pub(crate) fn set_neighbours<'s, 'b>(
     // There are only seven pushes in this function, so that's sufficient.
     let mut neighbours: Vec<(Edge, &Vertex)> = Vec::with_capacity(7);
 
-    if let (Some(lhs_syntax), Some(rhs_syntax)) = (&v.lhs_syntax, &v.rhs_syntax) {
+    if let (Some(lhs_syntax_id), Some(rhs_syntax_id)) = (&v.lhs_syntax, &v.rhs_syntax) {
+        let lhs_syntax = id_map[lhs_syntax_id];
+        let rhs_syntax = id_map[rhs_syntax_id];
+
         if lhs_syntax == rhs_syntax {
             let depth_difference = (lhs_syntax.num_ancestors() as i32
                 - rhs_syntax.num_ancestors() as i32)
@@ -517,8 +522,8 @@ pub(crate) fn set_neighbours<'s, 'b>(
 
             // Both nodes are equal, the happy case.
             let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) = pop_all_parents(
-                lhs_syntax.next_sibling(),
-                rhs_syntax.next_sibling(),
+                lhs_syntax.next_sibling().map(|n| n.id()),
+                rhs_syntax.next_sibling().map(|n| n.id()),
                 v.lhs_parent_id,
                 v.rhs_parent_id,
                 &v.parents,
@@ -568,7 +573,8 @@ pub(crate) fn set_neighbours<'s, 'b>(
                 let rhs_next = rhs_children.first().copied();
 
                 // TODO: be consistent between parents_next and next_parents.
-                let parents_next = push_both_delimiters(&v.parents, lhs_syntax, rhs_syntax, alloc);
+                let parents_next =
+                    push_both_delimiters(&v.parents, lhs_syntax.id(), rhs_syntax.id(), alloc);
 
                 let depth_difference = (lhs_syntax.num_ancestors() as i32
                     - rhs_syntax.num_ancestors() as i32)
@@ -578,8 +584,8 @@ pub(crate) fn set_neighbours<'s, 'b>(
                 // pop several levels if the list has no children.
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
-                        lhs_next,
-                        rhs_next,
+                        lhs_next.map(|n| n.id()),
+                        rhs_next.map(|n| n.id()),
                         Some(lhs_syntax.id()),
                         Some(rhs_syntax.id()),
                         &parents_next,
@@ -632,8 +638,8 @@ pub(crate) fn set_neighbours<'s, 'b>(
 
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
-                        lhs_syntax.next_sibling(),
-                        rhs_syntax.next_sibling(),
+                        lhs_syntax.next_sibling().map(|n| n.id()),
+                        rhs_syntax.next_sibling().map(|n| n.id()),
                         v.lhs_parent_id,
                         v.rhs_parent_id,
                         &v.parents,
@@ -660,13 +666,14 @@ pub(crate) fn set_neighbours<'s, 'b>(
         }
     }
 
-    if let Some(lhs_syntax) = &v.lhs_syntax {
+    if let Some(lhs_syntax_id) = &v.lhs_syntax {
+        let lhs_syntax = id_map[lhs_syntax_id];
         match lhs_syntax {
             // Step over this novel atom.
             Syntax::Atom { .. } => {
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
-                        lhs_syntax.next_sibling(),
+                        lhs_syntax.next_sibling().map(|n| n.id()),
                         v.rhs_syntax,
                         v.lhs_parent_id,
                         v.rhs_parent_id,
@@ -696,11 +703,11 @@ pub(crate) fn set_neighbours<'s, 'b>(
             Syntax::List { children, .. } => {
                 let lhs_next = children.first().copied();
 
-                let parents_next = push_lhs_delimiter(&v.parents, lhs_syntax, alloc);
+                let parents_next = push_lhs_delimiter(&v.parents, lhs_syntax.id(), alloc);
 
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
-                        lhs_next,
+                        lhs_next.map(|n| n.id()),
                         v.rhs_syntax,
                         Some(lhs_syntax.id()),
                         v.rhs_parent_id,
@@ -729,14 +736,15 @@ pub(crate) fn set_neighbours<'s, 'b>(
         }
     }
 
-    if let Some(rhs_syntax) = &v.rhs_syntax {
+    if let Some(rhs_syntax_id) = &v.rhs_syntax {
+        let rhs_syntax = id_map[rhs_syntax_id];
         match rhs_syntax {
             // Step over this novel atom.
             Syntax::Atom { .. } => {
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
                         v.lhs_syntax,
-                        rhs_syntax.next_sibling(),
+                        rhs_syntax.next_sibling().map(|n| n.id()),
                         v.lhs_parent_id,
                         v.rhs_parent_id,
                         &v.parents,
@@ -764,12 +772,12 @@ pub(crate) fn set_neighbours<'s, 'b>(
             // Step into this partially/fully novel list.
             Syntax::List { children, .. } => {
                 let rhs_next = children.first().copied();
-                let parents_next = push_rhs_delimiter(&v.parents, rhs_syntax, alloc);
+                let parents_next = push_rhs_delimiter(&v.parents, rhs_syntax.id(), alloc);
 
                 let (lhs_syntax, rhs_syntax, lhs_parent_id, rhs_parent_id, parents) =
                     pop_all_parents(
                         v.lhs_syntax,
-                        rhs_next,
+                        rhs_next.map(|n| n.id()),
                         v.lhs_parent_id,
                         Some(rhs_syntax.id()),
                         &parents_next,
@@ -807,8 +815,8 @@ pub(crate) fn set_neighbours<'s, 'b>(
 
 pub(crate) fn populate_change_map<'s, 'b>(
     route: &[(Edge, &'b Vertex<'s, 'b>)],
-    change_map: &mut ChangeMap<'s>,
-    id_map: &DftHashMap<SyntaxId, &'s Syntax<'s>>,
+    change_map: &mut ChangeMap,
+    id_map: &SyntaxIdMap<'s>,
 ) {
     for (e, v) in route {
         match e {
@@ -817,8 +825,8 @@ pub(crate) fn populate_change_map<'s, 'b>(
                 let lhs = v.lhs_syntax.unwrap();
                 let rhs = v.rhs_syntax.unwrap();
 
-                insert_deep_unchanged(lhs, rhs, change_map);
-                insert_deep_unchanged(rhs, lhs, change_map);
+                insert_deep_unchanged(lhs, rhs, id_map, change_map);
+                insert_deep_unchanged(rhs, lhs, id_map, change_map);
             }
             EnterUnchangedDelimiter { .. } => {
                 // No change on the outer delimiter, but children may
diff --git a/src/diff/sliders.rs b/src/diff/sliders.rs
index cd3da9892..fb9aa4253 100644
--- a/src/diff/sliders.rs
+++ b/src/diff/sliders.rs
@@ -33,20 +33,26 @@ use line_numbers::SingleLineSpan;
 
 use crate::{
     diff::changes::{insert_deep_novel, insert_deep_unchanged, ChangeKind::*, ChangeMap},
-    parse::guess_language,
-    parse::syntax::Syntax::{self, *},
+    parse::{
+        guess_language,
+        syntax::{
+            Syntax::{self, *},
+            SyntaxIdMap,
+        },
+    },
 };
 
 pub(crate) fn fix_all_sliders<'a>(
     language: guess_language::Language,
     nodes: &[&'a Syntax<'a>],
-    change_map: &mut ChangeMap<'a>,
+    id_map: &SyntaxIdMap<'a>,
+    change_map: &mut ChangeMap,
 ) {
     // TODO: fix sliders that require more than two steps.
-    fix_all_sliders_one_step(nodes, change_map);
-    fix_all_sliders_one_step(nodes, change_map);
+    fix_all_sliders_one_step(nodes, id_map, change_map);
+    fix_all_sliders_one_step(nodes, id_map, change_map);
 
-    fix_all_nested_sliders(language, nodes, change_map);
+    fix_all_nested_sliders(language, nodes, id_map, change_map);
 }
 
 /// Should nester slider correction prefer the inner or outer
@@ -72,13 +78,17 @@ fn prefer_outer_delimiter(language: guess_language::Language) -> bool {
     }
 }
 
-fn fix_all_sliders_one_step<'a>(nodes: &[&'a Syntax<'a>], change_map: &mut ChangeMap<'a>) {
+fn fix_all_sliders_one_step<'a>(
+    nodes: &[&'a Syntax<'a>],
+    id_map: &SyntaxIdMap<'a>,
+    change_map: &mut ChangeMap,
+) {
     for node in nodes {
         if let List { children, .. } = node {
-            fix_all_sliders_one_step(children, change_map);
+            fix_all_sliders_one_step(children, id_map, change_map);
         }
     }
-    fix_sliders(nodes, change_map);
+    fix_sliders(nodes, id_map, change_map);
 }
 
 /// Correct sliders in middle insertions.
@@ -100,7 +110,8 @@ fn fix_all_sliders_one_step<'a>(nodes: &[&'a Syntax<'a>], change_map: &mut Chang
 fn fix_all_nested_sliders<'a>(
     language: guess_language::Language,
     nodes: &[&'a Syntax<'a>],
-    change_map: &mut ChangeMap<'a>,
+    id_map: &SyntaxIdMap<'a>,
+    change_map: &mut ChangeMap,
 ) {
     let prefer_outer = prefer_outer_delimiter(language);
     for node in nodes {
@@ -115,10 +126,10 @@ fn fix_all_nested_sliders<'a>(
 /// When we see code of the form `(old-1 (novel (old-2)))`, prefer
 /// treating the outer delimiter as novel, so `(novel ...)` in this
 /// example.
-fn fix_nested_slider_prefer_outer<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap<'a>) {
+fn fix_nested_slider_prefer_outer<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap) {
     if let List { children, .. } = node {
         match change_map
-            .get(node)
+            .get(node.id())
             .expect("Changes should be set before slider correction")
         {
             Unchanged(_) => {
@@ -130,7 +141,7 @@ fn fix_nested_slider_prefer_outer<'a>(node: &'a Syntax<'a>, change_map: &mut Cha
                 // list has novel delimiters.
                 if let [candidate] = candidates[..] {
                     if matches!(candidate, List { .. })
-                        && matches!(change_map.get(candidate), Some(Novel))
+                        && matches!(change_map.get(candidate.id()), Some(Novel))
                     {
                         push_unchanged_to_descendant(node, candidate, change_map);
                     }
@@ -148,10 +159,10 @@ fn fix_nested_slider_prefer_outer<'a>(node: &'a Syntax<'a>, change_map: &mut Cha
 /// When we see code of the form `old1(novel(old2()))`, prefer
 /// treating the inner delimiter as novel, so `novel(...)` in this
 /// example.
-fn fix_nested_slider_prefer_inner<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap<'a>) {
+fn fix_nested_slider_prefer_inner<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap) {
     if let List { children, .. } = node {
         match change_map
-            .get(node)
+            .get(node.id())
             .expect("Changes should be set before slider correction")
         {
             Unchanged(_) => {}
@@ -176,7 +187,7 @@ fn fix_nested_slider_prefer_inner<'a>(node: &'a Syntax<'a>, change_map: &mut Cha
 fn unchanged_descendants<'a>(
     nodes: &[&'a Syntax<'a>],
     found: &mut Vec<&'a Syntax<'a>>,
-    change_map: &ChangeMap<'a>,
+    change_map: &ChangeMap,
 ) {
     // We're only interested if there is exactly one unchanged
     // descendant, so return early if we find 2 or more.
@@ -185,7 +196,7 @@ fn unchanged_descendants<'a>(
     }
 
     for node in nodes {
-        match change_map.get(node).unwrap() {
+        match change_map.get(node.id()).unwrap() {
             Unchanged(_) => {
                 found.push(node);
             }
@@ -212,7 +223,7 @@ fn unchanged_descendants<'a>(
 fn unchanged_descendants_for_outer_slider<'a>(
     nodes: &[&'a Syntax<'a>],
     found: &mut Vec<&'a Syntax<'a>>,
-    change_map: &ChangeMap<'a>,
+    change_map: &ChangeMap,
 ) {
     // We're only interested if there is exactly one unchanged
     // descendant, so return early if we find 2 or more.
@@ -221,7 +232,7 @@ fn unchanged_descendants_for_outer_slider<'a>(
     }
 
     for node in nodes {
-        let is_unchanged = matches!(change_map.get(node), Some(Unchanged(_)));
+        let is_unchanged = matches!(change_map.get(node.id()), Some(Unchanged(_)));
 
         match node {
             Atom { .. } => {
@@ -256,7 +267,7 @@ fn unchanged_descendants_for_outer_slider<'a>(
 
                     let has_unchanged_children = children
                         .iter()
-                        .any(|node| matches!(change_map.get(node), Some(Unchanged(_))));
+                        .any(|node| matches!(change_map.get(node.id()), Some(Unchanged(_))));
                     if has_unchanged_children {
                         // The list has unch