Repository: denoland/deno
Pull request: perf(lsp): replace dissimilar with imara-diff

## Summary

Addresses https://github.com/denoland/deno/pull/30644#issuecomment-4058350677

- Replaces `dissimilar` with `imara-diff` for computing LSP formatting text edits, unifying on a single diffing library across the codebase
- Removes the `dissimilar` dependency entirely from the workspace
- Diff granularity changes from character-level to line-level (standard for LSP implementations); edits are semantically equivalent

## Test plan

- [x] Unit tests in `cli/lsp/text.rs` updated and passing
- [ ] LSP integration tests updated to match line-level edit expectations
- [ ] CI passes

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Changed files:
filename: Cargo.lock
patch: @@ -1854,7 +1854,6 @@ dependencies = [
  "deno_tower_lsp",
  "deno_typescript_go_client_rust",
  "dhat",
- "dissimilar",
  "dprint-core",
  "dprint-plugin-json",
  "dprint-plugin-jupyter",
@@ -1869,6 +1868,7 @@ dependencies = [
  "http 1.4.0",
  "http-body 1.0.0",
  "http-body-util",
+ "imara-diff",
  "import_map",
  "indexmap 2.12.0",
  "jsonc-parser 0.28.0",
@@ -3910,12 +3910,6 @@ dependencies = [
  "syn 2.0.117",
 ]
 
-[[package]]
-name = "dissimilar"
-version = "1.0.9"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "59f8e79d1fbf76bdfbde321e902714bf6c49df88a7dda6fc682fc2979226962d"
-
 [[package]]
 name = "divan"
 version = "0.1.21"

filename: Cargo.toml
patch: @@ -354,7 +354,6 @@ clap_complete_fig = "=4.5.2"
 console_static_text = "=0.8.3"
 crossterm = "0.28.1"
 dhat = "0.3.3"
-dissimilar = "=1.0.9"
 dprint-core = "=0.67.4"
 dprint-plugin-json = "=0.21.1"
 dprint-plugin-jupyter = "=0.2.1"

filename: cli/Cargo.toml
patch: @@ -110,7 +110,6 @@ crossterm.workspace = true
 dashmap.workspace = true
 deno_dotenv.workspace = true
 dhat = { workspace = true, optional = true }
-dissimilar.workspace = true
 dprint-core.workspace = true
 dprint-plugin-json.workspace = true
 dprint-plugin-jupyter.workspace = true
@@ -125,6 +124,7 @@ fluent-uri.workspace = true
 http.workspace = true
 http-body.workspace = true
 http-body-util.workspace = true
+imara-diff.workspace = true
 import_map.workspace = true
 indexmap.workspace = true
 jsonc-parser = { workspace = true, features = ["cst", "serde"] }

filename: cli/lsp/text.rs
patch: @@ -1,8 +1,9 @@
 // Copyright 2018-2026 the Deno authors. MIT license.
 
 use deno_core::error::AnyError;
-use dissimilar::Chunk;
-use dissimilar::diff;
+use imara_diff::Algorithm;
+use imara_diff::Diff;
+use imara_diff::InternedInput;
 use text_size::TextRange;
 use text_size::TextSize;
 use tower_lsp::jsonrpc;
@@ -77,8 +78,8 @@ pub fn get_edits(a: &str, b: &str, line_index: &LineIndex) -> Vec<TextEdit> {
   if a == b {
     return vec![];
   }
-  // Heuristic to detect things like large JSON or minified files. `diff()` is
-  // expensive.
+  // Heuristic to detect things like large JSON or minified files. Diffing is
+  // expensive on very large inputs.
   let b_lines = b.chars().filter(|c| *c == '\n').count();
   if b_lines > 10000 || b_lines > line_index.inner.utf8_offsets_len() * 3 {
     return vec![TextEdit {
@@ -89,48 +90,44 @@ pub fn get_edits(a: &str, b: &str, line_index: &LineIndex) -> Vec<TextEdit> {
       new_text: b.to_string(),
     }];
   }
-  let chunks = diff(a, b);
+
+  let input = InternedInput::new(a, b);
+  let mut diff = Diff::compute(Algorithm::Histogram, &input);
+  diff.postprocess_lines(&input);
+
+  // Build a mapping from line index to utf16 offset for the original text.
+  // Line i starts at a_line_offsets[i] (in utf16 units).
+  let a_line_offsets: Vec<u32> = {
+    let mut offsets = vec![0u32];
+    let mut pos = 0u32;
+    for line_token in input.before.iter() {
+      let line_str = input.interner[*line_token];
+      pos += line_str.encode_utf16().count() as u32;
+      offsets.push(pos);
+    }
+    offsets
+  };
+
   let mut text_edits = Vec::<TextEdit>::new();
-  let mut iter = chunks.iter().peekable();
-  let mut a_pos = TextSize::from(0);
-  loop {
-    let chunk = iter.next();
-    match chunk {
-      None => break,
-      Some(Chunk::Equal(e)) => {
-        a_pos += TextSize::from(e.encode_utf16().count() as u32);
-      }
-      Some(Chunk::Delete(d)) => {
-        let start = line_index.position_utf16(a_pos);
-        a_pos += TextSize::from(d.encode_utf16().count() as u32);
-        let end = line_index.position_utf16(a_pos);
-        let range = lsp::Range { start, end };
-        match iter.peek() {
-          Some(Chunk::Insert(i)) => {
-            iter.next();
-            text_edits.push(TextEdit {
-              range,
-              new_text: i.to_string(),
-            });
-          }
-          _ => text_edits.push(TextEdit {
-            range,
-            new_text: "".to_string(),
-          }),
-        }
-      }
-      Some(Chunk::Insert(i)) => {
-        let pos = line_index.position_utf16(a_pos);
-        let range = lsp::Range {
-          start: pos,
-          end: pos,
-        };
-        text_edits.push(TextEdit {
-          range,
-          new_text: i.to_string(),
-        });
-      }
+
+  for hunk in diff.hunks() {
+    let del_start_line = hunk.before.start as usize;
+    let del_end_line = hunk.before.end as usize;
+
+    // Range in the original document being replaced
+    let start_offset = TextSize::from(a_line_offsets[del_start_line]);
+    let end_offset = TextSize::from(a_line_offsets[del_end_line]);
+    let start = line_index.position_utf16(start_offset);
+    let end = line_index.position_utf16(end_offset);
+    let range = lsp::Range { start, end };
+
+    // Build the replacement text from the "after" lines
+    let mut new_text = String::new();
+    for ins_idx in hunk.after.start..hunk.after.end {
+      new_text.push_str(input.interner[input.after[ins_idx as usize]]);
     }
+
+    text_edits.push(TextEdit { range, new_text });
   }
 
   text_edits
@@ -145,36 +142,22 @@ mod tests {
     let a = "abcdefg";
     let b = "a\nb\nchije\nfg\n";
     let actual = get_edits(a, b, &LineIndex::new(a));
+    // Line-level diff replaces the entire single-line input
     assert_eq!(
       actual,
-      vec![
-        TextEdit {
-          range: lsp::Range {
-            start: lsp::Position {
-              line: 0,
-              character: 1
-            },
-            end: lsp::Position {
-              line: 0,
-              character: 5
-            }
+      vec![TextEdit {
+        range: lsp::Range {
+          start: lsp::Position {
+            line: 0,
+            character: 0
           },
-          new_text: "\nb\nchije\n".to_string()
-        },
-        TextEdit {
-          range: lsp::Range {
-            start: lsp::Position {
-              line: 0,
-              character: 7
-            },
-            end: lsp::Position {
-              line: 0,
-              character: 7
-            }
-          },
-          new_text: "\n".to_string()
+          end: lsp::Position {
+            line: 0,
+            character: 7
+          }
         },
-      ]
+        new_text: "a\nb\nchije\nfg\n".to_string()
+      }]
     );
   }
 
@@ -183,36 +166,52 @@ mod tests {
     let a = "const bar = \"👍🇺🇸😃\";\nconsole.log('hello deno')\n";
     let b = "const bar = \"👍🇺🇸😃\";\nconsole.log(\"hello deno\");\n";
     let actual = get_edits(a, b, &LineIndex::new(a));
+    // Line-level diff replaces only the changed line
     assert_eq!(
       actual,
-      vec![
-        TextEdit {
-          range: lsp::Range {
-            start: lsp::Position {
-              line: 1,
-              character: 12
-            },
-            end: lsp::Position {
-              line: 1,
-              character: 13
-            }
+      vec![TextEdit {
+        range: lsp::Range {
+          start: lsp::Position {
+            line: 1,
+            character: 0
           },
-          new_text: "\"".to_string()
+          end: lsp::Position {
+            line: 2,
+            character: 0
+          }
         },
-        TextEdit {
-          range: lsp::Range {
-            start: lsp::Position {
-              line: 1,
-              character: 23
-            },
-            end: lsp::Position {
-              line: 1,
-              character: 25
-            }
+        new_text: "console.log(\"hello deno\");\n".to_string()
+      }]
+    )
+  }
+
+  #[test]
+  fn test_get_edits_no_changes() {
+    let a = "hello world\n";
+    let actual = get_edits(a, a, &LineIndex::new(a));
+    assert_eq!(actual, vec![]);
+  }
+
+  #[test]
+  fn test_get_edits_insert_line() {
+    let a = "line1\nline3\n";
+    let b = "line1\nline2\nline3\n";
+    let actual = get_edits(a, b, &LineIndex::new(a));
+    assert_eq!(
+      actual,
+      vec![TextEdit {
+        range: lsp::Range {
+          start: lsp::Position {
+            line: 1,
+            character: 0
           },
-          new_text: "\");".to_string()
+          end: lsp::Position {
+            line: 1,
+            character: 0
+          }
         },
-      ]
-    )
+        new_text: "line2\n".to_string()
+      }]
+    );
   }
 }

filename: tests/integration/lsp_tests.rs
patch: @@ -12326,28 +12326,10 @@ fn lsp_format_mbc(use_tsgo: bool) {
     res,
     json!([{
       "range": {
-        "start": { "line": 0, "character": 12 },
-        "end": { "line": 0, "character": 13 }
-      },
-      "newText": "\""
-    }, {
-      "range": {
-        "start": { "line": 0, "character": 21 },
-        "end": { "line": 0, "character": 22 }
-      },
-      "newText": "\";"
-    }, {
-      "range": {
-        "start": { "line": 1, "character": 12 },
-        "end": { "line": 1, "character": 13 }
-      },
-      "newText": "\""
-    }, {
-      "range": {
-        "start": { "line": 1, "character": 23 },
-        "end": { "line": 1, "character": 25 }
+        "start": { "line": 0, "character": 0 },
+        "end": { "line": 2, "character": 0 }
       },
-      "newText": "\");"
+      "newText": "const bar = \"👍🇺🇸😃\";\nconsole.log(\"hello deno\");\n"
     }])
   );
   client.shutdown();
@@ -12488,9 +12470,9 @@ fn lsp_format_untitled(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "console.log();\n",
       },
     ])
   );
@@ -12524,22 +12506,10 @@ fn lsp_format_json(use_tsgo: bool) {
     json!([
       {
         "range": {
-          "start": { "line": 0, "character": 1 },
-          "end": { "line": 0, "character": 1 }
-        },
-        "newText": " "
-      }, {
-        "range": {
-          "start": { "line": 0, "character": 7 },
-          "end": { "line": 0, "character": 7 }
-        },
-        "newText": " "
-      }, {
-        "range": {
-          "start": { "line": 0, "character": 14 },
+          "start": { "line": 0, "character": 0 },
           "end": { "line": 0, "character": 15 }
         },
-        "newText": " }\n"
+        "newText": "{ \"key\": \"value\" }\n"
       }
     ])
   );
@@ -12577,9 +12547,9 @@ fn lsp_format_vscode_userdata(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "// foo\n",
       },
     ]),
   );
@@ -12614,9 +12584,9 @@ fn lsp_format_editor_options(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 1, "character": 0 },
-          "end": { "line": 1, "character": 0 },
+          "end": { "line": 2, "character": 0 },
         },
-        "newText": "  ",
+        "newText": "    console.log();\n",
       },
     ])
   );
@@ -12638,9 +12608,9 @@ fn lsp_format_editor_options(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 1, "character": 0 },
-          "end": { "line": 1, "character": 2 },
+          "end": { "line": 2, "character": 0 },
         },
-        "newText": "\t",
+        "newText": "\tconsole.log();\n",
       },
     ])
   );
@@ -12745,16 +12715,10 @@ fn lsp_format_markdown(use_tsgo: bool) {
     json!([
       {
         "range": {
-          "start": { "line": 0, "character": 1 },
-          "end": { "line": 0, "character": 3 }
-        },
-        "newText": ""
-      }, {
-        "range": {
-          "start": { "line": 0, "character": 15 },
+          "start": { "line": 0, "character": 0 },
           "end": { "line": 0, "character": 15 }
         },
-        "newText": "\n"
+        "newText": "# Hello World\n"
       }
     ])
   );
@@ -12784,16 +12748,9 @@ fn lsp_format_html(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
-        },
-        "newText": "",
-      },
-      {
-        "range": {
-          "start": { "line": 0, "character": 15 },
           "end": { "line": 0, "character": 15 },
         },
-        "newText": "\n",
+        "newText": "<html></html>\n",
       },
     ]),
   );
@@ -12835,9 +12792,9 @@ fn lsp_format_css(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "foo {}\n",
       },
     ]),
   );
@@ -12857,9 +12814,9 @@ fn lsp_format_css(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "$font-stack: Helvetica, sans-serif;\n",
       },
     ]),
   );
@@ -12879,9 +12836,9 @@ fn lsp_format_css(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "$font-stack: Helvetica, sans-serif\n",
       },
     ]),
   );
@@ -12901,9 +12858,9 @@ fn lsp_format_css(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "@width: 10px;\n",
       },
     ]),
   );
@@ -12933,16 +12890,9 @@ fn lsp_format_yaml(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
-        },
-        "newText": "",
-      },
-      {
-        "range": {
-          "start": { "line": 0, "character": 8 },
           "end": { "line": 0, "character": 8 },
         },
-        "newText": "\n",
+        "newText": "foo: 1\n",
       },
     ]),
   );
@@ -12982,16 +12932,9 @@ fn lsp_format_sql(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
-        },
-        "newText": "",
-      },
-      {
-        "range": {
-          "start": { "line": 0, "character": 52 },
           "end": { "line": 0, "character": 52 },
         },
-        "newText": "\n",
+        "newText": "CREATE TABLE item (id int NOT NULL IDENTITY(1, 1))\n",
       },
     ]),
   );
@@ -13047,9 +12990,9 @@ fn lsp_format_component(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "<script module>\n",
       },
     ]),
   );
@@ -13069,9 +13012,9 @@ fn lsp_format_component(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "<script setup>\n",
       },
     ]),
   );
@@ -13091,9 +13034,9 @@ fn lsp_format_component(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "---\n",
       },
     ]),
   );
@@ -13113,9 +13056,9 @@ fn lsp_format_component(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "{{ layout \"foo.vto\" }}\n",
       },
     ]),
   );
@@ -13135,9 +13078,9 @@ fn lsp_format_component(use_tsgo: bool) {
       {
         "range": {
           "start": { "line": 0, "character": 0 },
-          "end": { "line": 0, "character": 2 },
+          "end": { "line": 1, "character": 0 },
         },
-        "newText": "",
+        "newText": "{% block header %}\n",
       },
     ]),
   );
@@ -13201,51 +13144,9 @@ fn lsp_format_with_config(use_tsgo: bool) {
     json!([{
         "range": {
           "start": { "line": 1, "character": 0 },
-          "end": { "line": 1, "character": 0 }
-        },
-        "newText": "\t"
-      }, {
-        "range": {
-          "start": { "line": 1, "character": 23 },
-          "end": { "line": 1, "character": 24 }
-        },
-        "newText": "\n\t\t'"
-      }, {
-        "range": {
-          "start": { "line": 1, "character": 73 },
-          "end": { "line": 1, "character": 74 }
-        },
-        "newText": "',\n\t"
-      }, {
-        "range": {
-          "start": { "line": 2, "character": 0 },
-          "end": { "line": 2, "character": 0 }
-        },
-        "newText": "\t"
-      }, {
-        "range": {
-          "start": { "line": 3, "character": 0 },
-          "end": { "line": 3, "character": 0 }
-        },
-        "newText": "\t"
-      }, {
-        "range": {
-          "start": { "line": 3, "character": 12 },
-          "end": { "line": 3, "character": 13 }
-        },
-        "newText": "'"
-      }, {
-        "range": {
-          "start": { "line": 3, "character": 22 },
-          "end": { "line": 3, "character": 24 }
-        },
-        "newText": "');"
-      }, {
-        "range": {
-          "start": { "line": 4, "character": 1 },
           "end": { "line": 4, "character": 1 }
         },
-        "newText": "\n"
+        "newText": "\tconst response = fetch(\n\t\t'http://localhost:4545/some/non/existent/path.json',\n\t);\n\tconsole.log(response.text());\n\tconsole.log('finished!');\n}\n"
       }]
     )
   );
@@ -16694,10 +16595,10 @@ fn lsp_deno_json_workspace_fmt_config(use_tsgo: bool) {
     res,
     json!([{
       "range": {
-        "start": { "line": 0, "character": 15 },
-        "end": { "line": 0, "character": 16 },
+        "start": { "line": 0, "character": 0 },
+        "end": { "line": 1, "character": 0 },
       },
-      "newText": "",
+      "newText": "console.log(\"\")\n",
     }])
   );
   client.did_open(json!({
@@ -16724,10 +16625,10 @@ fn lsp_deno_json_workspace_fmt_config(use_tsgo: bool) {
     res,
     json!([{
       "range": {
-        "start": { "line": 0, "character": 12 },
-        "end": { "line": 0, "character": 16 },
+        "start": { "line": 0, "character": 0 },
+        "end": { "line": 1, "character": 0 },
       },
-      "newText": "'')",
+      "newText": "console.log('')\n",
     }])
   );
   // `project2/file.ts` should use the fmt settings from `deno.json`, since it
@@ -16756,10 +16657,10 @@ fn lsp_deno_json_workspace_fmt_config(use_tsgo: bool) {
     res,
     json!([{
       "range": {
-        "start": { "line": 0, "character": 15 },
-        "end": { "line": 0, "character": 16 },
+        "start": { "line": 0, "character": 0 },
+        "end": { "line": 1, "character": 0 },
       },
-      "newText": "",
+      "newText": "console.log(\"\")\n",
     }])
   );
   client.shutdown();