Merge branch 'change_state_outside'

7 files changed, 308 insertions, 237 deletions

diff --git a/src/changes.rs b/src/changes.rs
new file mode 100644
index 0000000000..1176971d5c
--- /dev/null
+++ b/src/changes.rs
@@ -0,0 +1,72 @@
+use std::num::NonZeroU32;
+
+use rustc_hash::FxHashMap;
+
+use crate::syntax::Syntax;
+
+#[derive(PartialEq, Eq, Clone, Copy)]
+pub enum ChangeKind<'a> {
+    Unchanged(&'a Syntax<'a>),
+    ReplacedComment(&'a Syntax<'a>, &'a Syntax<'a>),
+    Novel,
+}
+
+#[derive(Debug)]
+pub struct ChangeMap<'a> {
+    changes: FxHashMap<NonZeroU32, ChangeKind<'a>>,
+}
+
+impl<'a> Default for ChangeMap<'a> {
+    fn default() -> Self {
+        Self {
+            changes: Default::default(),
+        }
+    }
+}
+
+impl<'a> ChangeMap<'a> {
+    pub fn insert(&mut self, node: &'a Syntax<'a>, ck: ChangeKind<'a>) {
+        self.changes.insert(node.id(), ck);
+    }
+
+    pub fn get(&self, node: &Syntax<'a>) -> Option<ChangeKind<'a>> {
+        self.changes.get(&node.id()).copied()
+    }
+}
+
+pub fn insert_deep_unchanged<'a>(
+    node: &'a Syntax<'a>,
+    opposite_node: &'a Syntax<'a>,
+    change_map: &mut ChangeMap<'a>,
+) {
+    change_map.insert(node, ChangeKind::Unchanged(opposite_node));
+
+    match (node, opposite_node) {
+        (
+            Syntax::List {
+                children: node_children,
+                ..
+            },
+            Syntax::List {
+                children: opposite_children,
+                ..
+            },
+        ) => {
+            for (child, opposite_child) in node_children.iter().zip(opposite_children) {
+                insert_deep_unchanged(child, opposite_child, change_map);
+            }
+        }
+        (Syntax::Atom { .. }, Syntax::Atom { .. }) => {}
+        _ => unreachable!("Unchanged nodes should be both lists, or both atoms"),
+    }
+}
+
+pub fn insert_deep_novel<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap<'a>) {
+    change_map.insert(node, ChangeKind::Novel);
+
+    if let Syntax::List { children, .. } = node {
+        for child in children.iter() {
+            insert_deep_novel(child, change_map);
+        }
+    }
+}
diff --git a/src/dijkstra.rs b/src/dijkstra.rs
index e6b33a2a2f..289acf0ad9 100644
--- a/src/dijkstra.rs
+++ b/src/dijkstra.rs
@@ -4,7 +4,8 @@
 use std::{cmp::Reverse, env};
 
 use crate::{
-    graph::{mark_route, neighbours, Edge, Vertex},
+    changes::ChangeMap,
+    graph::{neighbours, populate_change_map, Edge, Vertex},
     syntax::Syntax,
 };
 use itertools::Itertools;
@@ -137,7 +138,11 @@ fn tree_count(root: Option<&Syntax>) -> u32 {
     count
 }
 
-pub fn mark_syntax<'a>(lhs_syntax: Option<&'a Syntax<'a>>, rhs_syntax: Option<&'a Syntax<'a>>) {
+pub fn mark_syntax<'a>(
+    lhs_syntax: Option<&'a Syntax<'a>>,
+    rhs_syntax: Option<&'a Syntax<'a>>,
+    change_map: &mut ChangeMap<'a>,
+) {
     info!(
         "LHS nodes: {} ({} toplevel), RHS nodes: {} ({} toplevel)",
         node_count(lhs_syntax),
@@ -148,16 +153,18 @@ pub fn mark_syntax<'a>(lhs_syntax: Option<&'a Syntax<'a>>, rhs_syntax: Option<&'
 
     let start = Vertex::new(lhs_syntax, rhs_syntax);
     let route = shortest_path(start);
-    mark_route(&route);
+
+    populate_change_map(&route, change_map)
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::{
+        changes::ChangeKind,
         graph::Edge::*,
         positions::SingleLineSpan,
-        syntax::{init_all_info, AtomKind, ChangeKind},
+        syntax::{init_all_info, AtomKind},
     };
 
     use itertools::Itertools;
@@ -556,9 +563,11 @@ mod tests {
         let rhs = Syntax::new_atom(&arena, pos_helper(1), "foo", AtomKind::Normal);
         init_all_info(&[lhs], &[rhs]);
 
-        mark_syntax(Some(lhs), Some(rhs));
-        assert_eq!(lhs.change(), Some(ChangeKind::Unchanged(rhs)));
-        assert_eq!(rhs.change(), Some(ChangeKind::Unchanged(lhs)));
+        let mut change_map = ChangeMap::default();
+        mark_syntax(Some(lhs), Some(rhs), &mut change_map);
+
+        assert_eq!(change_map.get(lhs), Some(ChangeKind::Unchanged(rhs)));
+        assert_eq!(change_map.get(rhs), Some(ChangeKind::Unchanged(lhs)));
     }
 
     #[test]
@@ -568,8 +577,9 @@ mod tests {
         let rhs = Syntax::new_atom(&arena, pos_helper(1), "bar", AtomKind::Normal);
         init_all_info(&[lhs], &[rhs]);
 
-        mark_syntax(Some(lhs), Some(rhs));
-        assert_eq!(lhs.change(), Some(ChangeKind::Novel));
-        assert_eq!(rhs.change(), Some(ChangeKind::Novel));
+        let mut change_map = ChangeMap::default();
+        mark_syntax(Some(lhs), Some(rhs), &mut change_map);
+        assert_eq!(change_map.get(lhs), Some(ChangeKind::Novel));
+        assert_eq!(change_map.get(rhs), Some(ChangeKind::Novel));
     }
 }
diff --git a/src/graph.rs b/src/graph.rs
index 2b1b273075..81440a5fb7 100644
--- a/src/graph.rs
+++ b/src/graph.rs
@@ -9,7 +9,8 @@ use std::{
 };
 use strsim::normalized_levenshtein;
 
-use crate::syntax::{AtomKind, ChangeKind, Syntax};
+use crate::changes::{insert_deep_unchanged, ChangeKind, ChangeMap};
+use crate::syntax::{AtomKind, Syntax};
 use Edge::*;
 
 /// A vertex in a directed acyclic graph that represents a diff.
@@ -588,7 +589,7 @@ pub fn neighbours<'a>(v: &Vertex<'a>, buf: &mut [Option<(Edge, Vertex<'a>)>]) {
     );
 }
 
-pub fn mark_route(route: &[(Edge, Vertex)]) {
+pub fn populate_change_map<'a>(route: &[(Edge, Vertex<'a>)], change_map: &mut ChangeMap<'a>) {
     for (e, v) in route {
         match e {
             ExitDelimiterBoth | ExitDelimiterLHS | ExitDelimiterRHS => {
@@ -598,36 +599,37 @@ pub fn mark_route(route: &[(Edge, Vertex)]) {
                 // No change on this node or its children.
                 let lhs = v.lhs_syntax.unwrap();
                 let rhs = v.rhs_syntax.unwrap();
-                lhs.set_change_deep(ChangeKind::Unchanged(rhs));
-                rhs.set_change_deep(ChangeKind::Unchanged(lhs));
+
+                insert_deep_unchanged(lhs, rhs, change_map);
+                insert_deep_unchanged(rhs, lhs, change_map);
             }
             EnterUnchangedDelimiter { .. } => {
                 // No change on the outer delimiter, but children may
                 // have changed.
                 let lhs = v.lhs_syntax.unwrap();
                 let rhs = v.rhs_syntax.unwrap();
-                lhs.set_change(ChangeKind::Unchanged(rhs));
-                rhs.set_change(ChangeKind::Unchanged(lhs));
+                change_map.insert(lhs, ChangeKind::Unchanged(rhs));
+                change_map.insert(rhs, ChangeKind::Unchanged(lhs));
             }
             ReplacedComment { levenshtein_pct } => {
                 let lhs = v.lhs_syntax.unwrap();
                 let rhs = v.rhs_syntax.unwrap();
 
                 if *levenshtein_pct > 40 {
-                    lhs.set_change(ChangeKind::ReplacedComment(lhs, rhs));
-                    rhs.set_change(ChangeKind::ReplacedComment(rhs, lhs));
+                    change_map.insert(lhs, ChangeKind::ReplacedComment(lhs, rhs));
+                    change_map.insert(rhs, ChangeKind::ReplacedComment(rhs, lhs));
                 } else {
-                    lhs.set_change(ChangeKind::Novel);
-                    rhs.set_change(ChangeKind::Novel);
+                    change_map.insert(lhs, ChangeKind::Novel);
+                    change_map.insert(rhs, ChangeKind::Novel);
                 }
             }
             NovelAtomLHS { .. } | EnterNovelDelimiterLHS { .. } => {
                 let lhs = v.lhs_syntax.unwrap();
-                lhs.set_change(ChangeKind::Novel);
+                change_map.insert(lhs, ChangeKind::Novel);
             }
             NovelAtomRHS { .. } | EnterNovelDelimiterRHS { .. } => {
                 let rhs = v.rhs_syntax.unwrap();
-                rhs.set_change(ChangeKind::Novel);
+                change_map.insert(rhs, ChangeKind::Novel);
             }
         }
     }
diff --git a/src/main.rs b/src/main.rs
index 612d96359e..7d35497758 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -13,6 +13,7 @@
 // the number of arguments and triggering this lint.
 #![allow(clippy::too_many_arguments)]
 
+mod changes;
 mod constants;
 mod context;
 mod dijkstra;
@@ -38,6 +39,7 @@ mod unchanged;
 extern crate log;
 
 use crate::hunks::{matched_pos_to_hunks, merge_adjacent};
+use changes::ChangeMap;
 use context::opposite_positions;
 use files::read_files_or_die;
 use guess_language::guess;
@@ -307,10 +309,11 @@ fn diff_file_content(
 
             init_all_info(&lhs, &rhs);
 
+            let mut change_map = ChangeMap::default();
             let possibly_changed = if env::var("DFT_DBG_KEEP_UNCHANGED").is_ok() {
                 vec![(lhs.clone(), rhs.clone())]
             } else {
-                unchanged::mark_unchanged(&lhs, &rhs)
+                unchanged::mark_unchanged(&lhs, &rhs, &mut change_map)
             };
 
             let possibly_changed_max = max_num_nodes(&possibly_changed);
@@ -335,15 +338,16 @@ fn diff_file_content(
                     mark_syntax(
                         lhs_section_nodes.get(0).copied(),
                         rhs_section_nodes.get(0).copied(),
+                        &mut change_map,
                     );
 
                     let language = language.unwrap();
-                    fix_all_sliders(language, &lhs_section_nodes);
-                    fix_all_sliders(language, &rhs_section_nodes);
+                    fix_all_sliders(language, &lhs_section_nodes, &mut change_map);
+                    fix_all_sliders(language, &rhs_section_nodes, &mut change_map);
                 }
 
-                let lhs_positions = syntax::change_positions(&lhs);
-                let rhs_positions = syntax::change_positions(&rhs);
+                let lhs_positions = syntax::change_positions(&lhs, &change_map);
+                let rhs_positions = syntax::change_positions(&rhs, &change_map);
                 (Some(ts_lang.name.into()), lhs_positions, rhs_positions)
             }
         }
diff --git a/src/sliders.rs b/src/sliders.rs
index 2e370e9a9e..131cf3e585 100644
--- a/src/sliders.rs
+++ b/src/sliders.rs
@@ -30,19 +30,24 @@
 //! (B in this example).
 
 use crate::{
+    changes::{insert_deep_novel, insert_deep_unchanged, ChangeKind::*, ChangeMap},
     guess_language,
     positions::SingleLineSpan,
-    syntax::{ChangeKind::*, Syntax},
+    syntax::Syntax,
 };
 use Syntax::*;
 
-pub fn fix_all_sliders<'a>(language: guess_language::Language, nodes: &[&'a Syntax<'a>]) {
+pub fn fix_all_sliders<'a>(
+    language: guess_language::Language,
+    nodes: &[&'a Syntax<'a>],
+    change_map: &mut ChangeMap<'a>,
+) {
     // TODO: fix sliders that require more than two steps.
-    fix_all_sliders_one_step(nodes);
-    fix_all_sliders_one_step(nodes);
+    fix_all_sliders_one_step(nodes, change_map);
+    fix_all_sliders_one_step(nodes, change_map);
 
     if !prefer_outer_delimiter(language) {
-        fix_all_nested_sliders(nodes);
+        fix_all_nested_sliders(nodes, change_map);
     }
 }
 
@@ -66,13 +71,13 @@ fn prefer_outer_delimiter(language: guess_language::Language) -> bool {
     }
 }
 
-fn fix_all_sliders_one_step<'a>(nodes: &[&'a Syntax<'a>]) {
+fn fix_all_sliders_one_step<'a>(nodes: &[&'a Syntax<'a>], change_map: &mut ChangeMap<'a>) {
     for node in nodes {
         if let List { children, .. } = node {
-            fix_all_sliders_one_step(children);
+            fix_all_sliders_one_step(children, change_map);
         }
     }
-    fix_sliders(nodes);
+    fix_sliders(nodes, change_map);
 }
 
 /// Correct sliders in middle insertions.
@@ -91,59 +96,67 @@ fn fix_all_sliders_one_step<'a>(nodes: &[&'a Syntax<'a>]) {
 ///
 /// For C-like languages, the first case matches human intuition much
 /// better. Fix the slider to make the inner delimiter novel.
-fn fix_all_nested_sliders<'a>(nodes: &[&'a Syntax<'a>]) {
+fn fix_all_nested_sliders<'a>(nodes: &[&'a Syntax<'a>], change_map: &mut ChangeMap<'a>) {
     for node in nodes {
-        fix_nested_slider(node);
+        fix_nested_slider(node, change_map);
     }
 }
 
-fn fix_nested_slider<'a>(node: &'a Syntax<'a>) {
+fn fix_nested_slider<'a>(node: &'a Syntax<'a>, change_map: &mut ChangeMap<'a>) {
     if let List { children, .. } = node {
-        match node
-            .change()
+        match change_map
+            .get(node)
             .expect("Changes should be set before slider correction")
         {
             Unchanged(_) => {
                 for child in children {
-                    fix_nested_slider(child);
+                    fix_nested_slider(child, change_map);
                 }
             }
             ReplacedComment(_, _) => {}
             Novel => {
                 let mut found_unchanged = vec![];
                 for child in children {
-                    unchanged_descendants(child, &mut found_unchanged);
+                    unchanged_descendants(child, &mut found_unchanged, change_map);
                 }
 
                 if let [List { .. }] = found_unchanged[..] {
-                    push_unchanged_to_ancestor(node, found_unchanged[0]);
+                    push_unchanged_to_ancestor(node, found_unchanged[0], change_map);
                 }
             }
         }
     }
 }
 
-fn unchanged_descendants<'a>(node: &'a Syntax<'a>, found: &mut Vec<&'a Syntax<'a>>) {
+fn unchanged_descendants<'a>(
+    node: &'a Syntax<'a>,
+    found: &mut Vec<&'a Syntax<'a>>,
+    change_map: &ChangeMap<'a>,
+) {
     if found.len() > 1 {
         return;
     }
 
-    match node.change().unwrap() {
+    match change_map.get(node).unwrap() {
         Unchanged(_) => {
             found.push(node);
         }
         Novel | ReplacedComment(_, _) => {
             if let List { children, .. } = node {
                 for child in children {
-                    unchanged_descendants(child, found);
+                    unchanged_descendants(child, found, change_map);
                 }
             }
         }
     }
 }
 
-fn push_unchanged_to_ancestor<'a>(root: &'a Syntax<'a>, inner: &'a Syntax<'a>) {
-    let inner_change = inner.change().expect("Node changes should be set");
+fn push_unchanged_to_ancestor<'a>(
+    root: &'a Syntax<'a>,
+    inner: &'a Syntax<'a>,
+    change_map: &mut ChangeMap<'a>,
+) {
+    let inner_change = change_map.get(inner).expect("Node changes should be set");
 
     let delimiters_match = match (root, inner) {
         (
@@ -162,26 +175,29 @@ fn push_unchanged_to_ancestor<'a>(root: &'a Syntax<'a>, inner: &'a Syntax<'a>) {
     };
 
     if delimiters_match {
-        root.set_change(inner_change);
-        inner.set_change(Novel);
+        change_map.insert(root, inner_change);
+        change_map.insert(inner, Novel);
     }
 }
 
-fn fix_sliders<'a>(nodes: &[&'a Syntax<'a>]) {
-    for (region_start, region_end) in novel_regions_after_unchanged(nodes) {
-        slide_to_prev_node(nodes, region_start, region_end);
+fn fix_sliders<'a>(nodes: &[&'a Syntax<'a>], change_map: &mut ChangeMap<'a>) {
+    for (region_start, region_end) in novel_regions_after_unchanged(nodes, change_map) {
+        slide_to_prev_node(nodes, change_map, region_start, region_end);
     }
-    for (region_start, region_end) in novel_regions_before_unchanged(nodes) {
-        slide_to_next_node(nodes, region_start, region_end);
+    for (region_start, region_end) in novel_regions_before_unchanged(nodes, change_map) {
+        slide_to_next_node(nodes, change_map, region_start, region_end);
     }
 }
 
-fn novel_regions_after_unchanged<'a>(nodes: &[&'a Syntax<'a>]) -> Vec<(usize, usize)> {
+fn novel_regions_after_unchanged<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &ChangeMap<'a>,
+) -> Vec<(usize, usize)> {
     let mut regions: Vec<Vec<usize>> = vec![];
     let mut region: Option<Vec<usize>> = None;
 
     for (i, node) in nodes.iter().enumerate() {
-        let change = node.change().expect("Node changes should be set");
+        let change = change_map.get(node).expect("Node changes should be set");
 
         match change {
             Unchanged(_) => {
@@ -221,12 +237,15 @@ fn novel_regions_after_unchanged<'a>(nodes: &[&'a Syntax<'a>]) -> Vec<(usize, us
         .collect()
 }
 
-fn novel_regions_before_unchanged<'a>(nodes: &[&'a Syntax<'a>]) -> Vec<(usize, usize)> {
+fn novel_regions_before_unchanged<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &ChangeMap<'a>,
+) -> Vec<(usize, usize)> {
     let mut regions: Vec<Vec<usize>> = vec![];
     let mut region: Option<Vec<usize>> = None;
 
     for (i, node) in nodes.iter().enumerate() {
-        let change = node.change().expect("Node changes should be set");
+        let change = change_map.get(node).expect("Node changes should be set");
 
         match change {
             Unchanged(_) => {
@@ -255,43 +274,48 @@ fn novel_regions_before_unchanged<'a>(nodes: &[&'a Syntax<'a>]) -> Vec<(usize, u
         .collect()
 }
 
-fn is_novel_deep(node: &Syntax) -> bool {
+fn is_novel_deep<'a>(node: &Syntax<'a>, change_map: &ChangeMap<'a>) -> bool {
     match node {
-        List { info, children, .. } => {
-            if !matches!(info.change.get(), Some(Novel)) {
+        List { children, .. } => {
+            if !matches!(change_map.get(node), Some(Novel)) {
                 return false;
             }
             for child in children {
-                if !is_novel_deep(child) {
+                if !is_novel_deep(child, change_map) {
                     return false;
                 }
             }
 
             true
         }
-        Atom { info, .. } => matches!(info.change.get(), Some(Novel)),
+        Atom { .. } => matches!(change_map.get(node), Some(Novel)),
     }
 }
 
-fn is_unchanged_deep(node: &Syntax) -> bool {
+fn is_unchanged_deep<'a>(node: &Syntax<'a>, change_map: &ChangeMap<'a>) -> bool {
     match node {
-        List { info, children, .. } => {
-            if !matches!(info.change.get(), Some(Unchanged(_))) {
+        List { children, .. } => {
+            if !matches!(change_map.get(node), Some(Unchanged(_))) {
                 return false;
             }
             for child in children {
-                if !is_unchanged_deep(child) {
+                if !is_unchanged_deep(child, change_map) {
                     return false;
                 }
             }
 
             true
         }
-        Atom { info, .. } => matches!(info.change.get(), Some(Unchanged(_))),
+        Atom { .. } => matches!(change_map.get(node), Some(Unchanged(_))),
     }
 }
 
-fn slide_to_prev_node<'a>(nodes: &[&'a Syntax<'a>], start_idx: usize, end_idx: usize) {
+fn slide_to_prev_node<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &mut ChangeMap<'a>,
+    start_idx: usize,
+    end_idx: usize,
+) {
     if start_idx == 0 {
         return;
     }
@@ -313,30 +337,35 @@ fn slide_to_prev_node<'a>(nodes: &[&'a Syntax<'a>], start_idx: usize, end_idx: u
 
     if distance_to_before_start <= distance_to_last {
         // Deep checks walk the whole tree, so do these last.
-        if !is_unchanged_deep(before_start_node) {
+        if !is_unchanged_deep(before_start_node, change_map) {
             return;
         }
         for node in &nodes[start_idx..=end_idx] {
-            if !is_novel_deep(node) {
+            if !is_novel_deep(node, change_map) {
                 return;
             }
         }
 
-        let opposite = match before_start_node
-            .change()
+        let opposite = match change_map
+            .get(before_start_node)
             .expect("Node changes should be set")
         {
             Unchanged(n) => n,
             _ => unreachable!(),
         };
 
-        before_start_node.set_change_deep(Novel);
-        last_node.set_change_deep(Unchanged(opposite));
-        opposite.set_change_deep(Unchanged(last_node));
+        insert_deep_novel(before_start_node, change_map);
+        insert_deep_unchanged(last_node, &opposite, change_map);
+        insert_deep_unchanged(&opposite, last_node, change_map);
     }
 }
 
-fn slide_to_next_node<'a>(nodes: &[&'a Syntax<'a>], start_idx: usize, end_idx: usize) {
+fn slide_to_next_node<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &mut ChangeMap<'a>,
+    start_idx: usize,
+    end_idx: usize,
+) {
     if end_idx == nodes.len() - 1 {
         return;
     }
@@ -358,26 +387,26 @@ fn slide_to_next_node<'a>(nodes: &[&'a Syntax<'a>], start_idx: usize, end_idx: u
 
     if distance_to_after_last < distance_to_start {
         // Deep checks walk the whole tree, so do these last.
-        if !is_unchanged_deep(after_last_node) {
+        if !is_unchanged_deep(after_last_node, change_map) {
             return;
         }
         for node in &nodes[start_idx..=end_idx] {
-            if !is_novel_deep(node) {
+            if !is_novel_deep(node, change_map) {
                 return;
             }
         }
 
-        let opposite = match after_last_node
-            .change()
+        let opposite = match change_map
+            .get(after_last_node)
             .expect("Node changes should be set")
         {
             Unchanged(n) => n,
             _ => unreachable!(),
         };
 
-        start_node.set_change_deep(Unchanged(opposite));
-        opposite.set_change_deep(Unchanged(start_node));
-        after_last_node.set_change_deep(Novel);
+        insert_deep_unchanged(start_node, &opposite, change_map);
+        insert_deep_unchanged(&opposite, start_node, change_map);
+        insert_deep_novel(after_last_node, change_map);
     }
 }
 
@@ -494,15 +523,16 @@ mod tests {
 
         init_all_info(&lhs, &rhs);
 
-        lhs[0].set_change(Unchanged(rhs[0]));
-        lhs[1].set_change(Novel);
-        lhs[2].set_change(Novel);
+        let mut change_map = ChangeMap::default();
+        change_map.insert(lhs[0], Unchanged(rhs[0]));
+        change_map.insert(lhs[1], Novel);
+        change_map.insert(lhs[2], Novel);
 
-        fix_all_sliders(guess_language::Language::EmacsLisp, &lhs);
-        assert_eq!(lhs[0].change(), Some(Novel));
-        assert_eq!(lhs[1].change(), Some(Novel));
-        assert_eq!(lhs[2].change(), Some(Unchanged(rhs[0])));
-        assert_eq!(rhs[0].change(), Some(Unchanged(lhs[2])));
+        fix_all_sliders(guess_language::Language::EmacsLisp, &lhs, &mut change_map);
+        assert_eq!(change_map.get(lhs[0]), Some(Novel));
+        assert_eq!(change_map.get(lhs[1]), Some(Novel));
+        assert_eq!(change_map.get(lhs[2]), Some(Unchanged(rhs[0])));
+        assert_eq!(change_map.get(rhs[0]), Some(Unchanged(lhs[2])));
     }
 
     /// Test that we slide at the end if the unchanged node is
@@ -542,15 +572,17 @@ mod tests {
 
         init_all_info(&lhs, &rhs);
 
-        lhs[0].set_change(Novel);
-        lhs[1].set_change(Novel);
-        lhs[2].set_change(Unchanged(rhs[0]));
+        let mut change_map = ChangeMap::default();
+        change_map.insert(lhs[0], Novel);
+        change_map.insert(lhs[1], Novel);
+        change_map.insert(lhs[2], Unchanged(rhs[0]));
 
-        fix_all_sliders(guess_language::Language::EmacsLisp, &lhs);
-        assert_eq!(rhs[0].change(), Some(Unchanged(lhs[0])));
-        assert_eq!(lhs[0].change(), Some(Unchanged(rhs[0])));
-        assert_eq!(lhs[1].change(), Some(Novel));
-        assert_eq!(lhs[2].change(), Some(Novel));
+        fix_all_sliders(guess_language::Language::EmacsLisp, &lhs, &mut change_map);
+
+        assert_eq!(change_map.get(rhs[0]), Some(Unchanged(lhs[0])));
+        assert_eq!(change_map.get(lhs[0]), Some(Unchanged(rhs[0])));
+        assert_eq!(change_map.get(lhs[1]), Some(Novel));
+        assert_eq!(change_map.get(lhs[2]), Some(Novel));
     }
     #[test]
     fn test_slider_two_steps() {
@@ -561,16 +593,17 @@ mod tests {
         let rhs = parse(&arena, "A B X\n A B", &config);
         init_all_info(&lhs, &rhs);
 
-        rhs[0].set_change(Unchanged(lhs[0]));
-        rhs[1].set_change(Unchanged(lhs[1]));
-        rhs[2].set_change(Novel);
-        rhs[3].set_change(Novel);
-        rhs[4].set_change(Novel);
-
-        fix_all_sliders(guess_language::Language::EmacsLisp, &rhs);
-        assert_eq!(rhs[0].change(), Some(Novel));
-        assert_eq!(rhs[1].change(), Some(Novel));
-        assert_eq!(rhs[2].change(), Some(Novel));
-        assert_eq!(rhs[3].change(), Some(Unchanged(rhs[0])));
+        let mut change_map = ChangeMap::default();
+        change_map.insert(rhs[0], Unchanged(lhs[0]));
+        change_map.insert(rhs[1], Unchanged(lhs[1]));
+        change_map.insert(rhs[2], Novel);
+        change_map.insert(rhs[3], Novel);
+        change_map.insert(rhs[4], Novel);
+
+        fix_all_sliders(guess_language::Language::EmacsLisp, &rhs, &mut change_map);
+        assert_eq!(change_map.get(rhs[0]), Some(Novel));
+        assert_eq!(change_map.get(rhs[1]), Some(Novel));
+        assert_eq!(change_map.get(rhs[2]), Some(Novel));
+        assert_eq!(change_map.get(rhs[3]), Some(Unchanged(rhs[0])));
     }
 }
diff --git a/src/syntax.rs b/src/syntax.rs
index 6bbb2df464..45ac725e8c 100644
--- a/src/syntax.rs
+++ b/src/syntax.rs
@@ -12,20 +12,14 @@ use std::{
 use typed_arena::Arena;
 
 use crate::{
+    changes::ChangeKind,
+    changes::{ChangeKind::*, ChangeMap},
     lines::{LineNumber, NewlinePositions},
     myers_diff,
     positions::SingleLineSpan,
 };
-use ChangeKind::*;
 use Syntax::*;
 
-#[derive(PartialEq, Eq, Clone, Copy)]
-pub enum ChangeKind<'a> {
-    Unchanged(&'a Syntax<'a>),
-    ReplacedComment(&'a Syntax<'a>, &'a Syntax<'a>),
-    Novel,
-}
-
 /// A Debug implementation that does not reucurse into the
 /// corresponding node mentioned for Unchanged. Otherwise we will
 /// infinitely loop on unchanged nodes, which both point to the other.
@@ -60,9 +54,6 @@ pub struct SyntaxInfo<'a> {
     /// Does the previous syntax node occur on the same line as the
     /// first line of this node?
     prev_is_contiguous: Cell<bool>,
-    /// Whether or not this syntax node has changed. This value is set
-    /// when computing the diff with another syntax tree.
-    pub change: Cell<Option<ChangeKind<'a>>>,
     /// The number of nodes that are ancestors of this one.
     num_ancestors: Cell<u32>,
     /// A number that uniquely identifies this syntax node.
@@ -83,7 +74,6 @@ impl<'a> SyntaxInfo<'a> {
             prev: Cell::new(None),
             parent: Cell::new(None),
             prev_is_contiguous: Cell::new(false),
-            change: Cell::new(None),
             num_ancestors: Cell::new(0),
             unique_id: Cell::new(NonZeroU32::new(u32::MAX).unwrap()),
             content_id: Cell::new(0),
@@ -151,8 +141,6 @@ impl<'a> fmt::Debug for Syntax<'a> {
                     .field("close_position", &dbg_pos(close_position));
 
                 if env::var("DFT_VERBOSE").is_ok() {
-                    ds.field("change", &info.change.get());
-
                     let next_sibling_s = match info.next_sibling.get() {
                         Some(List { .. }) => "Some(List)",
                         Some(Atom { .. }) => "Some(Atom)",
@@ -180,7 +168,6 @@ impl<'a> fmt::Debug for Syntax<'a> {
 
                 if env::var("DFT_VERBOSE").is_ok() {
                     ds.field("highlight", highlight);
-                    ds.field("change", &info.change.get());
                     let next_sibling_s = match info.next_sibling.get() {
                         Some(List { .. }) => "Some(List)",
                         Some(Atom { .. }) => "Some(Atom)",
@@ -333,36 +320,6 @@ impl<'a> Syntax<'a> {
         };
         position.last().map(|lp| lp.line)
     }
-
-    pub fn change(&'a self) -> Option<ChangeKind<'a>> {
-        self.info().change.get()
-    }
-
-    pub fn set_change(&self, ck: ChangeKind<'a>) {
-        self.info().change.set(Some(ck));
-    }
-
-    pub fn set_change_deep(&self, ck: ChangeKind<'a>) {
-        self.set_change(ck);
-
-        if let List { children, .. } = self {
-            // For unchanged lists, match up children with the
-            // unchanged children on the other side.
-            if let Unchanged(List {
-                children: other_children,
-                ..
-            }) = ck
-            {
-                for (child, other_child) in children.iter().zip(other_children) {
-                    child.set_change_deep(Unchanged(other_child));
-                }
-            } else {
-                for child in children {
-                    child.set_change_deep(ck);
-                }
-            };
-        }
-    }
 }
 
 /// Initialise all the fields in `SyntaxInfo`.
@@ -807,16 +764,23 @@ impl MatchedPos {
 }
 
 /// Walk `nodes` and return a vec of all the changed positions.
-pub fn change_positions<'a>(nodes: &[&'a Syntax<'a>]) -> Vec<MatchedPos> {
+pub fn change_positions<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &ChangeMap<'a>,
+) -> Vec<MatchedPos> {
     let mut positions = Vec::new();
-    change_positions_(nodes, &mut positions);
+    change_positions_(nodes, change_map, &mut positions);
     positions
 }
 
-fn change_positions_<'a>(nodes: &[&'a Syntax<'a>], positions: &mut Vec<MatchedPos>) {
+fn change_positions_<'a>(
+    nodes: &[&'a Syntax<'a>],
+    change_map: &ChangeMap<'a>,
+    positions: &mut Vec<MatchedPos>,
+) {
     for node in nodes {
-        let change = node
-            .change()
+        let change = change_map
+            .get(node)
             .unwrap_or_else(|| panic!("Should have changes set in all nodes: {:#?}", node));
 
         match node {
@@ -833,7 +797,7 @@ fn change_positions_<'a>(nodes: &[&'a Syntax<'a>], positions: &mut Vec<MatchedPo
                     false,
                 ));
 
-                change_positions_(children, positions);
+                change_positions_(children, change_map, positions);
 
                 positions.extend(MatchedPos::new(
                     change,
@@ -999,40 +963,6 @@ mod tests {
     }
 
     #[test]
-    fn test_atom_equality_ignores_change() {
-        let lhs = Atom {
-            info: SyntaxInfo {
-                change: Cell::new(Some(Novel)),
-                ..SyntaxInfo::default()
-            },
-
-            position: vec![SingleLineSpan {
-                line: 1.into(),
-                start_col: 2,
-                end_col: 3,
-            }],
-            content: "foo".into(),
-            kind: AtomKind::Normal,
-        };
-        let rhs = Atom {
-            info: SyntaxInfo {
-                change: Cell::new(None),
-                ..SyntaxInfo::default()
-            },
-            position: vec![SingleLineSpan {
-                line: 1.into(),
-                start_col: 2,
-                end_col: 3,
-            }],
-            content: "foo".into(),
-            kind: AtomKind::Normal,
-        };
-        init_all_info(&[&lhs], &[&rhs]);
-
-        assert_eq!(lhs, rhs);
-    }
-
-    #[test]
     fn test_split_comment_words_basic() {
         let content = "abc";
         let pos = SingleLineSpan {
diff --git a/src/unchanged.rs b/src/unchanged.rs
index ede5091dc6..cae4b0ebec 100644
--- a/src/unchanged.rs
+++ b/src/unchanged.rs
@@ -1,5 +1,7 @@
+use crate::changes::{insert_deep_unchanged, ChangeKind, ChangeMap};
 use crate::myers_diff;
-use crate::syntax::{ChangeKind, Syntax};
+
+use crate::syntax::Syntax;
 
 const TINY_TREE_THRESHOLD: u32 = 10;
 const MOSTLY_UNCHANGED_MIN_NODES: usize = 4;
@@ -10,13 +12,15 @@ const MOSTLY_UNCHANGED_MIN_COMMON_CHILDREN: usize = 4;
 pub fn mark_unchanged<'a>(
     lhs_nodes: &[&'a Syntax<'a>],
     rhs_nodes: &[&'a Syntax<'a>],
+    change_map: &mut ChangeMap<'a>,
 ) -> Vec<(Vec<&'a Syntax<'a>>, Vec<&'a Syntax<'a>>)> {
-    let (_, lhs_nodes, rhs_nodes) = shrink_unchanged_at_ends(lhs_nodes, rhs_nodes);
+    let (_, lhs_nodes, rhs_nodes) = shrink_unchanged_at_ends(lhs_nodes, rhs_nodes, change_map);
 
     let mut res = vec![];