deno 2.7.13

// Copyright 2018-2026 the Deno authors. MIT license.

use deno_core::error::AnyError;
use imara_diff::Algorithm;
use imara_diff::Diff;
use imara_diff::InternedInput;
use text_size::TextRange;
use text_size::TextSize;
use tower_lsp::jsonrpc;
use tower_lsp::lsp_types as lsp;
use tower_lsp::lsp_types::TextEdit;

use crate::util::text_encoding::Utf16Map;

#[derive(Debug, Clone, Default, Eq, PartialEq)]
pub struct LineIndex {
  inner: Utf16Map,
}

impl LineIndex {
  pub fn new(text: &str) -> LineIndex {
    LineIndex {
      inner: Utf16Map::new(text),
    }
  }

  /// Convert a u16 based range to a u8 TextRange.
  pub fn get_text_range(
    &self,
    range: lsp::Range,
  ) -> Result<TextRange, AnyError> {
    let start = self.offset(range.start)?;
    let end = self.offset(range.end)?;
    Ok(TextRange::new(start, end))
  }

  /// Return a u8 offset based on a u16 position.
  pub fn offset(&self, position: lsp::Position) -> Result<TextSize, AnyError> {
    self.inner.offset(position.line, position.character)
  }

  /// Convert an lsp Position into a tsc/TypeScript "position", which is really
  /// an u16 byte offset from the start of the string represented as an u32.
  pub fn offset_tsc(&self, position: lsp::Position) -> jsonrpc::Result<u32> {
    self
      .inner
      .offset_utf16(position.line, position.character)
      .map(|ts| ts.into())
      .map_err(|err| jsonrpc::Error::invalid_params(err.to_string()))
  }

  /// Returns a u16 position based on a u16 offset, which TypeScript offsets are
  /// returned as u16.
  pub fn position_utf16(&self, offset: TextSize) -> lsp::Position {
    let lc = self.inner.position_utf16(offset);
    lsp::Position {
      line: lc.line_index as u32,
      character: lc.column_index as u32,
    }
  }

  pub fn line_length_utf16(&self, line: u32) -> TextSize {
    self.inner.line_length_utf16(line)
  }

  pub fn text_content_length_utf16(&self) -> TextSize {
    self.inner.text_content_length_utf16()
  }
}

/// Compare two strings and return a vector of text edit records which are
/// supported by the Language Server Protocol.
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. 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 {
      range: lsp::Range {
        start: lsp::Position::new(0, 0),
        end: line_index.position_utf16(TextSize::from(a.len() as u32)),
      },
      new_text: b.to_string(),
    }];
  }

  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();

  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
}

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_get_edits() {
    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: 0
          },
          end: lsp::Position {
            line: 0,
            character: 7
          }
        },
        new_text: "a\nb\nchije\nfg\n".to_string()
      }]
    );
  }

  #[test]
  fn test_get_edits_mbc() {
    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: 0
          },
          end: lsp::Position {
            line: 2,
            character: 0
          }
        },
        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
          },
          end: lsp::Position {
            line: 1,
            character: 0
          }
        },
        new_text: "line2\n".to_string()
      }]
    );
  }
}