Prefer aligning blank lines in display0.23.0

After we've aligned lines based on diff results, we have intermediate
lines that we need to align somehow. Previously, we'd just take them
in order, aligning the first on the LHS with the first on the RHS and
so on.

If the intermediate lines start or end with a sequence of blank lines,
prefer aligning the blank lines. If we have both, arbitrarily choose
the ending blank lines.

This has produced better results in many of the sample files, although
in the case of slow_before.rs we've just changed from a leading blank
line alignment to a trailing blank line alignment.

4 files changed, 202 insertions, 12 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index b270c3531..e597c33fe 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -15,6 +15,9 @@ incorrectly marked as unchanged, producing non-optimal diffs.
 
 ### Display
 
+Display now prefers to align blank lines in the display, producing
+significantly better results in many cases.
+
 Fixed an issue where some lines in a hunk were not displayed.
 
 ## 0.22 (released 10th March 2022)
diff --git a/sample_files/compare.expected b/sample_files/compare.expected
index 071d9a746..46f315b01 100644
--- a/sample_files/compare.expected
+++ b/sample_files/compare.expected
@@ -8,7 +8,7 @@ sample_files/clojure_before.clj sample_files/clojure_after.clj
 8316bcd959ce706ac07011f6dc31c93a  -
 
 sample_files/comments_before.rs sample_files/comments_after.rs
-898ffdafebc08cdf4e9fe43cb3619e6c  -
+d899ce2b86f03851fa02823a1ff9aa3f  -
 
 sample_files/context_before.rs sample_files/context_after.rs
 5f8518317cbaa2920c9d8c86d060c84f  -
@@ -29,13 +29,13 @@ sample_files/hack_before.php sample_files/hack_after.php
 dee893339d9e746eabc3983eb7f37fe5  -
 
 sample_files/haskell_before.hs sample_files/haskell_after.hs
-744fda002baf0eff349942c58ce51ea5  -
+a2a8efc24e1262d09889e10bd14a77c1  -
 
 sample_files/helpful_before.el sample_files/helpful_after.el
 3c3dc4e230c748f62df050053a72163f  -
 
 sample_files/helpful-unit-test-before.el sample_files/helpful-unit-test-after.el
-a68a53ebaaa2651408540d23cd2dbe9a  -
+236758836c0fa82f0f0ed6b864e995d3  -
 
 sample_files/if_before.py sample_files/if_after.py
 49405c8bf3315d3d2a0d62aa9f0c326b  -
@@ -44,28 +44,28 @@ sample_files/java_before.java sample_files/java_after.java
 a6f23f8daf1334596df49da999d1b7b3  -
 
 sample_files/javascript_before.js sample_files/javascript_after.js
-6c7dca37aa14c7ab07ce072d1e8766f2  -
+12a609bbacf57cdae4bb9a812b966fa0  -
 
 sample_files/javascript_simple_before.js sample_files/javascript_simple_after.js
-58208dbd2347671a5eb068d775a5f4f9  -
+eba8ce51d3045e57b75dac86d71fc1b4  -
 
 sample_files/json_before.json sample_files/json_after.json
 559447b4a48066c2918502c4b0450f50  -
 
 sample_files/jsx_before.jsx sample_files/jsx_after.jsx
-5584ecaed7f41540d646afe39df31156  -
+e6333610ce3060df999a3199013a2fda  -
 
 sample_files/load_before.js sample_files/load_after.js
-bf8527f91baff9a5f56380784b2a438e  -
+ff099ac983e75c3cac59a086d63c8dd6  -
 
 sample_files/modules_before.ml sample_files/modules_after.ml
-d182f73a8729211cc41e297aeab8f7a9  -
+25118f4e0b2d5be687abed4ff3106d3d  -
 
 sample_files/multibyte_before.py sample_files/multibyte_after.py
 8a5e31775d5e788e9158bd4a36e03254  -
 
 sample_files/nest_before.rs sample_files/nest_after.rs
-791901de922abc7f24e5b9068706417d  -
+c36f2f545abee17589e2c18693ad5793  -
 
 sample_files/nesting_before.el sample_files/nesting_after.el
 c9b74f137aada068b0a317c09966e705  -
@@ -92,7 +92,7 @@ sample_files/slider_before.rs sample_files/slider_after.rs
 ab11d8dfc684921d85f49d3ec4dfeec4  -
 
 sample_files/slow_before.rs sample_files/slow_after.rs
-1f6176a6518e16eb8dfe32d7d81c63d9  -
+f2f30bc8d13a61227a78b6c9dd5c4683  -
 
 sample_files/small_before.js sample_files/small_after.js
 ee97a525a74be6dd18e959395d02265b  -
diff --git a/src/context.rs b/src/context.rs
index 232ae122c..27c592f65 100644
--- a/src/context.rs
+++ b/src/context.rs
@@ -19,10 +19,16 @@ pub const MAX_PADDING: usize = 3;
 pub fn all_matched_lines_filled(
     lhs_mps: &[MatchedPos],
     rhs_mps: &[MatchedPos],
+    lhs_lines: &[&str],
+    rhs_lines: &[&str],
 ) -> Vec<(Option<LineNumber>, Option<LineNumber>)> {
     let matched_lines = all_matched_lines(lhs_mps, rhs_mps);
 
-    compact_gaps(&ensure_contiguous(&matched_lines))
+    compact_gaps(&ensure_contiguous(&match_preceding_blanks(
+        &matched_lines,
+        lhs_lines,
+        rhs_lines,
+    )))
 }
 
 fn all_matched_lines(
@@ -120,6 +126,126 @@ fn merge_in_opposite_lines(
     res
 }
 
+/// If the lines immediately before `current` are blank on both sides,
+/// return the line numbers of those blank lines.
+fn match_blanks_between(
+    current: (LineNumber, LineNumber),
+    prev: (LineNumber, LineNumber),
+    lhs_lines: &[&str],
+    rhs_lines: &[&str],
+) -> Vec<(Option<LineNumber>, Option<LineNumber>)> {
+    let (mut current_lhs, mut current_rhs) = current;
+    if current_lhs.0 == 0 || current_rhs.0 == 0 {
+        return vec![];
+    }
+
+    current_lhs = (current_lhs.0 - 1).into();
+    current_rhs = (current_rhs.0 - 1).into();
+
+    let mut res = vec![];
+    while current_lhs > prev.0 && current_rhs > prev.1 {
+        if lhs_lines[current_lhs.0] == "" && rhs_lines[current_rhs.0] == "" {
+            res.push((Some(current_lhs), Some(current_rhs)));
+
+            current_lhs = (current_lhs.0 - 1).into();
+            current_rhs = (current_rhs.0 - 1).into();
+        } else {
+            break;
+        }
+    }
+
+    res.reverse();
+    res
+}
+
+fn match_blanks_before(
+    current: (LineNumber, LineNumber),
+    lhs_lines: &[&str],
+    rhs_lines: &[&str],
+) -> Vec<(Option<LineNumber>, Option<LineNumber>)> {
+    let (mut current_lhs, mut current_rhs) = current;
+    if current_lhs.0 == 0 || current_rhs.0 == 0 {
+        return vec![];
+    }
+
+    current_lhs = (current_lhs.0 - 1).into();
+    current_rhs = (current_rhs.0 - 1).into();
+
+    let mut res = vec![];
+    loop {
+        if lhs_lines[current_lhs.0] == "" && rhs_lines[current_rhs.0] == "" {
+            res.push((Some(current_lhs), Some(current_rhs)));
+
+            if current_lhs.0 == 0 || current_rhs.0 == 0 {
+                break;
+            }
+
+            current_lhs = (current_lhs.0 - 1).into();
+            current_rhs = (current_rhs.0 - 1).into();
+        } else {
+            break;
+        }
+    }
+
+    res.reverse();
+    res
+}
+
+/// For every line number pair, if there are blank lines preceding the
+/// pair, add those blank lines to the vec.
+///
+/// This substantially improves alignment, leading to more readable
+/// diffs.
+///
+/// We don't need to match blank lines following each pair. After
+/// matching up all the matching lines, we just display the remaining
+/// lines side-by-side regardless of content (see
+/// `ensure_contiguous`). If there are blank lines immediately
+/// following the pair, they will get aligned by this.
+fn match_preceding_blanks(
+    line_nums: &[(Option<LineNumber>, Option<LineNumber>)],
+    lhs_lines: &[&str],
+    rhs_lines: &[&str],
+) -> Vec<(Option<LineNumber>, Option<LineNumber>)> {
+    let mut prev_lhs = None;
+    let mut prev_rhs = None;
+
+    let mut res: Vec<(Option<LineNumber>, Option<LineNumber>)> = vec![];
+    for (lhs_line_num, rhs_line_num) in line_nums {
+        match (lhs_line_num, rhs_line_num, prev_lhs, prev_rhs) {
+            (Some(lhs_line_num), Some(rhs_line_num), None, None) => {
+                // The first pair.
+                res.append(&mut match_blanks_before(
+                    (*lhs_line_num, *rhs_line_num),
+                    lhs_lines,
+                    rhs_lines,
+                ));
+            }
+            (Some(lhs_line_num), Some(rhs_line_num), Some(prev_lhs), Some(prev_rhs)) => {
+                // Later pairs.
+                res.append(&mut match_blanks_between(
+                    (*lhs_line_num, *rhs_line_num),
+                    (prev_lhs, prev_rhs),
+                    lhs_lines,
+                    rhs_lines,
+                ));
+            }
+            _ => {}
+        }
+
+        res.push((*lhs_line_num, *rhs_line_num));
+
+        if lhs_line_num.is_some() {
+            prev_lhs = *lhs_line_num;
+        }
+        if rhs_line_num.is_some() {
+            prev_rhs = *rhs_line_num;
+        }
+    }
+
+    res
+}
+
 // TODO: use FxHashMap here.
 pub fn opposite_positions(mps: &[MatchedPos]) -> HashMap<LineNumber, HashSet<LineNumber>> {
     let mut res: HashMap<LineNumber, HashSet<LineNumber>> = HashMap::new();
@@ -721,4 +847,65 @@ mod tests {
             ]
         )
     }
+
+    #[test]
+    fn test_match_preceding_blanks() {
+        let lhs_lines = vec!["x", "", "", "y"];
+        let rhs_lines = vec!["x", "extra", "", "", "y"];
+
+        let res = match_preceding_blanks(
+            &[
+                (Some(0.into()), Some(0.into())),
+                (Some(3.into()), Some(4.into())),
+            ],
+            &lhs_lines,
+            &rhs_lines,
+        );
+        assert_eq!(
+            res,
+            vec![
+                (Some(0.into()), Some(0.into())),
+                (Some(1.into()), Some(2.into())),
+                (Some(2.into()), Some(3.into())),
+                (Some(3.into()), Some(4.into())),
+            ]
+        );
+    }
+
+    #[test]
+    fn test_match_preceding_blanks_first_pair() {
+        let lhs_lines = vec!["", "", "y"];
+        let rhs_lines = vec!["extra", "", "", "y"];
+
+        let res =
+            match_preceding_blanks(&[(Some(2.into()), Some(3.into()))], &lhs_lines, &rhs_lines);
+        assert_eq!(
+            res,
+            vec![
+                (Some(0.into()), Some(1.into())),
+                (Some(1.into()), Some(2.into())),
+                (Some(2.into()), Some(3.into())),
+            ]
+        );
+    }
+
+    #[test]
+    fn test_match_blanks_between() {
+        let lhs_lines = vec!["x", "", "", "y"];
+        let rhs_lines = vec!["x", "extra", "", "", "y"];
+
+        let res = match_blanks_between(
+            (3.into(), 4.into()),
+            (0.into(), 0.into()),
+            &lhs_lines,
+            &rhs_lines,
+        );
+        assert_eq!(
+            res,
+            vec![
+                (Some(1.into()), Some(2.into())),
+                (Some(2.into()), Some(3.into()))
+            ]
+        );
+    }
 }
diff --git a/src/side_by_side.rs b/src/side_by_side.rs
index 54cacf9a5..b592c924d 100644
--- a/src/side_by_side.rs
+++ b/src/side_by_side.rs
@@ -349,7 +349,7 @@ pub fn print(
     let mut prev_lhs_line_num = None;
     let mut prev_rhs_line_num = None;
 
-    let matched_lines = all_matched_lines_filled(lhs_mps, rhs_mps);
+    let matched_lines = all_matched_lines_filled(lhs_mps, rhs_mps, &lhs_lines, &rhs_lines);
 
     for (i, hunk) in hunks.iter().enumerate() {
         println!(