rumdl_lib/utils/

line_ending.rs

use std::borrow::Cow;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LineEnding {
    Lf,
    Crlf,
    Mixed,
}

/// Maps byte offsets in LF-normalized content back to the original input.
///
/// rumdl normalizes CRLF to LF while linting. Machine-readable fixes, however,
/// must address the bytes supplied by the caller, including mixed-line-ending
/// input. Each entry records the normalized offset of a newline whose preceding
/// carriage return was removed.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct NormalizedLineEndingMap {
    crlf_newline_offsets: Vec<usize>,
    /// Normalized offsets of the newlines that were a bare LF, recorded only
    /// when the original mixes line endings: text written into such a file
    /// takes the ending of the line it follows.
    mixed_lf_newline_offsets: Vec<usize>,
    /// Whether every line of the original ends in CRLF, so text written into it
    /// takes CRLF as well.
    all_crlf: bool,
}

impl NormalizedLineEndingMap {
    pub fn new(original: &str) -> Self {
        // Ordinary LF input needs neither a map nor a vector of LF offsets.
        if !original.contains('\r') {
            return Self::default();
        }
        let bytes = original.as_bytes();
        let mut crlf_newline_offsets = Vec::new();
        let mut lf_newline_offsets = Vec::new();
        for (offset, _) in original.match_indices('\n') {
            let normalized_offset = offset - crlf_newline_offsets.len();
            if offset > 0 && bytes[offset - 1] == b'\r' {
                crlf_newline_offsets.push(normalized_offset - 1);
            } else {
                lf_newline_offsets.push(normalized_offset);
            }
        }

        let all_crlf = !crlf_newline_offsets.is_empty() && lf_newline_offsets.is_empty();
        if crlf_newline_offsets.is_empty() {
            lf_newline_offsets.clear();
        }
        Self {
            crlf_newline_offsets,
            mixed_lf_newline_offsets: lf_newline_offsets,
            all_crlf,
        }
    }

    fn is_mixed(&self) -> bool {
        !self.mixed_lf_newline_offsets.is_empty()
    }

    /// Text to insert into the original input at `normalized_offset`:
    /// LF-normalized `text` with the line ending `fmt` would give it there.
    /// That is the file's own ending, or in a file with mixed endings the
    /// ending of the line the insertion follows.
    pub fn original_text_at<'a>(&self, text: &'a str, normalized_offset: usize) -> Cow<'a, str> {
        if !text.contains('\n') {
            return Cow::Borrowed(text);
        }
        if self.all_crlf {
            return normalize_line_ending(text, LineEnding::Crlf);
        }
        if self.is_mixed() && self.ending_before(normalized_offset) == "\r\n" {
            return normalize_line_ending(text, LineEnding::Crlf);
        }
        Cow::Borrowed(text)
    }

    /// The ending of the line holding the byte before `normalized_offset`, or
    /// of the first line at the start of the text. An unterminated last line
    /// has none of its own and gives the ending of the line before it.
    fn ending_before(&self, normalized_offset: usize) -> &'static str {
        let position = normalized_offset.saturating_sub(1);
        let next = |offsets: &[usize]| {
            offsets
                .get(offsets.partition_point(|&offset| offset < position))
                .copied()
        };
        match (next(&self.crlf_newline_offsets), next(&self.mixed_lf_newline_offsets)) {
            (Some(crlf), Some(lf)) => {
                if crlf < lf {
                    "\r\n"
                } else {
                    "\n"
                }
            }
            (Some(_), None) => "\r\n",
            (None, Some(_)) => "\n",
            (None, None) => {
                if self.crlf_newline_offsets.last() > self.mixed_lf_newline_offsets.last() {
                    "\r\n"
                } else {
                    "\n"
                }
            }
        }
    }

    /// Write `fixed`, the LF-normalized content after fixes, back in the line
    /// endings of the original this map was built from. `normalized_original`
    /// is the LF-normalized original the fixes started from.
    ///
    /// A file with one line ending gets it throughout. In a file with mixed
    /// endings, a diff of the two texts decides each line ending: a newline the
    /// fixes kept keeps its original ending, and a newline they inserted takes
    /// the ending of the line it was inserted into, the same ending
    /// [`Self::original_text_at`] gives a JSON fix inserting it there. A line
    /// diff finds the changed regions and a byte diff aligns the newlines
    /// inside each one, so the cost follows the size of the edits.
    pub fn restore_fixed<'a>(&self, normalized_original: &str, fixed: &'a str) -> Cow<'a, str> {
        if self.all_crlf {
            return normalize_line_ending(fixed, LineEnding::Crlf);
        }
        if !self.is_mixed() {
            return Cow::Borrowed(fixed);
        }

        let old: Vec<&str> = normalized_original.split_inclusive('\n').collect();
        let new: Vec<&str> = fixed.split_inclusive('\n').collect();
        let line_starts = |lines: &[&str]| {
            let mut starts = Vec::with_capacity(lines.len() + 1);
            starts.push(0);
            for line in lines {
                starts.push(starts.last().unwrap() + line.len());
            }
            starts
        };
        let old_starts = line_starts(&old);
        let new_starts = line_starts(&new);

        // The ending of each newline in `fixed`, in order.
        let mut endings: Vec<&'static str> = Vec::with_capacity(new.len());
        // A newline kept from the original at `offset`, or inserted at `offset`.
        let kept = |offset: usize| self.ending_before(offset + 1);
        let inserted = |offset: usize| self.ending_before(offset);
        let newlines = |text: &str| text.bytes().filter(|&b| b == b'\n').count();

        for op in similar::capture_diff_slices(similar::Algorithm::Myers, &old, &new) {
            match op {
                similar::DiffOp::Equal { old_index, len, .. } => {
                    for line in old_index..old_index + len {
                        if old[line].ends_with('\n') {
                            endings.push(kept(old_starts[line + 1] - 1));
                        }
                    }
                }
                similar::DiffOp::Delete { .. } => {}
                similar::DiffOp::Insert {
                    old_index,
                    new_index,
                    new_len,
                } => {
                    let at = inserted(old_starts[old_index]);
                    let count = newlines(&fixed[new_starts[new_index]..new_starts[new_index + new_len]]);
                    endings.extend(std::iter::repeat_n(at, count));
                }
                similar::DiffOp::Replace {
                    old_index,
                    old_len,
                    new_index,
                    new_len,
                } => {
                    let base = old_starts[old_index];
                    let old_bytes = &normalized_original.as_bytes()[base..old_starts[old_index + old_len]];
                    let new_bytes = &fixed.as_bytes()[new_starts[new_index]..new_starts[new_index + new_len]];
                    for byte_op in similar::capture_diff_slices(similar::Algorithm::Myers, old_bytes, new_bytes) {
                        let (old_at, new_range, is_kept) = match byte_op {
                            similar::DiffOp::Equal {
                                old_index,
                                new_index,
                                len,
                            } => (old_index, new_index..new_index + len, true),
                            similar::DiffOp::Delete { .. } => continue,
                            similar::DiffOp::Insert {
                                old_index,
                                new_index,
                                new_len,
                            }
                            | similar::DiffOp::Replace {
                                old_index,
                                new_index,
                                new_len,
                                ..
                            } => (old_index, new_index..new_index + new_len, false),
                        };
                        for (k, &byte) in new_bytes[new_range].iter().enumerate() {
                            if byte == b'\n' {
                                endings.push(if is_kept {
                                    kept(base + old_at + k)
                                } else {
                                    inserted(base + old_at)
                                });
                            }
                        }
                    }
                }
            }
        }

        let mut restored = String::with_capacity(fixed.len() + endings.len());
        let mut endings = endings.into_iter();
        for line in &new {
            match line.strip_suffix('\n') {
                Some(body) => {
                    restored.push_str(body);
                    restored.push_str(endings.next().unwrap_or("\n"));
                }
                None => restored.push_str(line),
            }
        }
        Cow::Owned(restored)
    }

    /// Convert a byte boundary in normalized content to the corresponding byte
    /// boundary in the original input.
    pub fn original_offset(&self, normalized_offset: usize) -> usize {
        normalized_offset
            + self
                .crlf_newline_offsets
                .partition_point(|newline_offset| *newline_offset < normalized_offset)
    }

    /// The original input, rebuilt from the LF-normalized content this map was
    /// built from by putting back each carriage return normalization removed.
    /// Exact for any input, mixed line endings included, where re-normalizing to
    /// the detected line ending is not.
    pub fn restore(&self, normalized: &str) -> String {
        let mut restored = String::with_capacity(normalized.len() + self.crlf_newline_offsets.len());
        let mut copied = 0;
        for &newline_offset in &self.crlf_newline_offsets {
            restored.push_str(&normalized[copied..newline_offset]);
            restored.push('\r');
            copied = newline_offset;
        }
        restored.push_str(&normalized[copied..]);
        restored
    }
}

/// The line ending text inserted at byte `offset` of `content` takes, by the
/// rule `NormalizedLineEndingMap::original_text_at` applies to normalized
/// offsets: the ending of the line holding the byte before `offset` (the first
/// line at offset 0), or for an unterminated last line the ending before it.
/// `\n` when `content` has no line ending at all.
pub fn line_ending_before(content: &str, offset: usize) -> &'static str {
    let bytes = content.as_bytes();
    let position = offset.saturating_sub(1).min(bytes.len());
    let newline = bytes[position..]
        .iter()
        .position(|&b| b == b'\n')
        .map(|found| position + found)
        .or_else(|| bytes.iter().rposition(|&b| b == b'\n'));
    match newline {
        Some(newline) if newline > 0 && bytes[newline - 1] == b'\r' => "\r\n",
        _ => "\n",
    }
}

pub fn detect_line_ending_enum(content: &str) -> LineEnding {
    let bytes = content.as_bytes();
    // LF is the common case. Search for CR before examining each newline.
    if memchr::memchr(b'\r', bytes).is_none() {
        return LineEnding::Lf;
    }
    let mut crlf = false;
    let mut lf = false;
    for newline in memchr::memchr_iter(b'\n', bytes) {
        if newline > 0 && bytes[newline - 1] == b'\r' {
            crlf = true;
        } else {
            lf = true;
        }
        if crlf && lf {
            return LineEnding::Mixed;
        }
    }
    if crlf { LineEnding::Crlf } else { LineEnding::Lf }
}

pub fn detect_line_ending(content: &str) -> &'static str {
    // Compatibility function matching the old signature
    let crlf_count = content.matches("\r\n").count();
    let lf_count = content.matches('\n').count() - crlf_count;

    if crlf_count > lf_count { "\r\n" } else { "\n" }
}

pub fn normalize_line_ending<'a>(content: &'a str, target: LineEnding) -> Cow<'a, str> {
    match target {
        LineEnding::Lf => {
            if !content.contains('\r') {
                Cow::Borrowed(content)
            } else {
                Cow::Owned(content.replace("\r\n", "\n"))
            }
        }
        LineEnding::Crlf => {
            // First normalize everything to LF, then convert to CRLF
            let normalized = content.replace("\r\n", "\n");
            Cow::Owned(normalized.replace('\n', "\r\n"))
        }
        LineEnding::Mixed => Cow::Borrowed(content),
    }
}

pub fn ensure_consistent_line_endings(original: &str, modified: &str) -> String {
    LineEndingPolicy::new(original).apply(modified).into_owned()
}

/// The native ending policy of one immutable source revision. A rule that
/// emits several block edits computes it once, rather than rereading the
/// entire document for every replacement.
pub(crate) struct LineEndingPolicy(LineEnding);

impl LineEndingPolicy {
    pub(crate) fn new(original: &str) -> Self {
        let ending = detect_line_ending_enum(original);
        let target = if ending == LineEnding::Mixed {
            let bytes = original.as_bytes();
            let mut crlf = 0;
            let mut lf = 0;
            for newline in memchr::memchr_iter(b'\n', bytes) {
                if newline > 0 && bytes[newline - 1] == b'\r' {
                    crlf += 1;
                } else {
                    lf += 1;
                }
            }
            if crlf > lf { LineEnding::Crlf } else { LineEnding::Lf }
        } else {
            ending
        };
        Self(target)
    }

    fn apply<'a>(&self, modified: &'a str) -> Cow<'a, str> {
        if self.0 == detect_line_ending_enum(modified) {
            Cow::Borrowed(modified)
        } else {
            normalize_line_ending(modified, self.0)
        }
    }

    pub(crate) fn apply_owned(&self, modified: String) -> String {
        match self.apply(&modified) {
            Cow::Borrowed(_) => modified,
            Cow::Owned(normalized) => normalized,
        }
    }

    pub(crate) fn apply_to(&self, modified: &str) -> String {
        self.apply(modified).into_owned()
    }
}

pub fn get_line_ending_str(ending: LineEnding) -> &'static str {
    match ending {
        LineEnding::Lf => "\n",
        LineEnding::Crlf => "\r\n",
        LineEnding::Mixed => "\n", // Default to LF for mixed
    }
}

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

    fn native_ending(content: &str) -> LineEnding {
        let mut crlf = 0;
        let mut lf = 0;
        let bytes = content.as_bytes();
        for (i, &byte) in bytes.iter().enumerate() {
            if byte == b'\n' {
                if i > 0 && bytes[i - 1] == b'\r' {
                    crlf += 1
                } else {
                    lf += 1
                }
            }
        }
        match (crlf > 0, lf > 0) {
            (true, true) => LineEnding::Mixed,
            (true, false) => LineEnding::Crlf,
            _ => LineEnding::Lf,
        }
    }

    proptest! {
        #[test]
        fn source_policy_matches_native_endings_and_replacements(
            old in prop::collection::vec(prop_oneof![Just('\r'), Just('\n'), any::<char>()], 0..300),
            new in prop::collection::vec(prop_oneof![Just('\r'), Just('\n'), any::<char>()], 0..300),
        ) {
            let old: String = old.into_iter().collect();
            let new: String = new.into_iter().collect();
            prop_assert_eq!(detect_line_ending_enum(&old), native_ending(&old));
            let target = match native_ending(&old) {
                LineEnding::Mixed => {
                    let crlf = old.matches("\r\n").count();
                    if crlf > old.matches('\n').count() - crlf { LineEnding::Crlf } else { LineEnding::Lf }
                },
                ending => ending,
            };
            let expected = if target == native_ending(&new) {
                new.clone()
            } else {
                match target {
                    LineEnding::Lf => new.replace("\r\n", "\n"),
                    LineEnding::Crlf => new.replace("\r\n", "\n").replace('\n', "\r\n"),
                    LineEnding::Mixed => unreachable!(),
                }
            };
            let policy = LineEndingPolicy::new(&old);
            prop_assert_eq!(&policy.apply_to(&new), &expected);
            prop_assert_eq!(&policy.apply_owned(new.clone()), &expected);
            prop_assert_eq!(ensure_consistent_line_endings(&old, &new), expected);
        }
    }

    proptest! {
        #[test]
        fn mapping_matches_original_byte_walk(
            parts in prop::collection::vec(prop_oneof![
                Just("\r".to_string()), Just("\n".to_string()),
                Just("\r\n".to_string()), any::<char>().prop_map(|c| c.to_string()),
            ], 0..200)
        ) {
            let original = parts.concat();
            let mut expected = NormalizedLineEndingMap::default();
            let mut lfs = Vec::new();
            let mut bytes = original.bytes().peekable();
            let mut normalized = 0;
            while let Some(byte) = bytes.next() {
                if byte == b'\r' && bytes.peek() == Some(&b'\n') {
                    expected.crlf_newline_offsets.push(normalized);
                    bytes.next();
                } else if byte == b'\n' {
                    lfs.push(normalized);
                }
                normalized += 1;
            }
            expected.all_crlf = !expected.crlf_newline_offsets.is_empty() && lfs.is_empty();
            if !expected.crlf_newline_offsets.is_empty() {
                expected.mixed_lf_newline_offsets = lfs;
            }
            prop_assert_eq!(NormalizedLineEndingMap::new(&original), expected);
        }
    }

    #[test]
    fn test_detect_line_ending_enum() {
        assert_eq!(detect_line_ending_enum("hello\nworld"), LineEnding::Lf);
        assert_eq!(detect_line_ending_enum("hello\r\nworld"), LineEnding::Crlf);
        assert_eq!(detect_line_ending_enum("hello\r\nworld\nmixed"), LineEnding::Mixed);
        assert_eq!(detect_line_ending_enum("no line endings"), LineEnding::Lf);
    }

    #[test]
    fn normalized_line_ending_map_handles_mixed_input() {
        let original = "a\r\nb\nc\r\n";
        let map = NormalizedLineEndingMap::new(original);

        // Boundaries surrounding the two CRLF sequences gain one byte each,
        // while the standalone LF does not.
        assert_eq!(map.original_offset(1), 1);
        assert_eq!(map.original_offset(2), 3);
        assert_eq!(map.original_offset(4), 5);
        assert_eq!(map.original_offset(6), 8);
    }

    #[test]
    fn normalized_line_ending_map_writes_text_with_the_ending_fmt_writes() {
        let crlf = NormalizedLineEndingMap::new("a\r\nb\r\n");
        assert_eq!(crlf.original_text_at("x\n\ny\n", 2), "x\r\n\r\ny\r\n");
        assert_eq!(crlf.original_text_at("no newline", 2), "no newline");

        for original in ["a\nb\n", ""] {
            let map = NormalizedLineEndingMap::new(original);
            assert_eq!(map.original_text_at("x\n", 0), "x\n", "{original:?}");
        }

        // In a mixed file, inserted lines take the ending of the line the
        // insertion follows, as `fmt` writes them. Normalized "a\nb\nc" has
        // its newlines at offsets 1 (CRLF) and 3 (LF).
        let mixed = NormalizedLineEndingMap::new("a\r\nb\nc");
        assert_eq!(
            mixed.original_text_at("x\n", 0),
            "x\r\n",
            "start of file: first line's ending"
        );
        assert_eq!(mixed.original_text_at("x\n", 1), "x\r\n", "end of line a");
        assert_eq!(
            mixed.original_text_at("x\n", 2),
            "x\r\n",
            "start of line b, after a's CRLF"
        );
        assert_eq!(mixed.original_text_at("x\n", 3), "x\n", "end of line b");
        assert_eq!(mixed.original_text_at("x\n", 4), "x\n", "start of line c, after b's LF");
        assert_eq!(
            mixed.original_text_at("x\n", 5),
            "x\n",
            "unterminated last line: the ending before it"
        );
    }

    #[test]
    fn line_ending_before_agrees_with_the_map_at_every_offset() {
        for original in ["a\r\nb\nc", "a\nb\r\n", "\r\n\n\r\nxy\n", "é\r\n日本\nz"] {
            let map = NormalizedLineEndingMap::new(original);
            let normalized = normalize_line_ending(original, LineEnding::Lf);
            for offset in 0..=normalized.len() {
                assert_eq!(
                    line_ending_before(original, map.original_offset(offset)),
                    map.ending_before(offset),
                    "{original:?} at normalized offset {offset}"
                );
            }
        }
        assert_eq!(line_ending_before("no newline", 3), "\n");
    }

    #[test]
    fn restore_fixed_keeps_uniform_endings_uniform() {
        let crlf = NormalizedLineEndingMap::new("# A\r\ntext\r\n");
        assert_eq!(
            crlf.restore_fixed("# A\ntext\n", "# A\n\ntext\n"),
            "# A\r\n\r\ntext\r\n"
        );
        let lf = NormalizedLineEndingMap::new("# A\ntext\n");
        assert_eq!(lf.restore_fixed("# A\ntext\n", "# A\n\ntext\n"), "# A\n\ntext\n");
    }

    /// `restore_fixed` on a mixed original, given as (original, fixed LF text, expected).
    fn assert_mixed_restore(original: &str, fixed: &str, expected: &str) {
        let map = NormalizedLineEndingMap::new(original);
        let normalized = normalize_line_ending(original, LineEnding::Lf);
        assert_eq!(
            map.restore_fixed(&normalized, fixed),
            expected,
            "{original:?} -> {fixed:?}"
        );
    }

    #[test]
    fn restore_fixed_keeps_each_untouched_lines_ending_in_a_mixed_file() {
        // Unchanged content comes back byte-identical.
        assert_mixed_restore("# T\r\nText\n## N\r\n", "# T\nText\n## N\n", "# T\r\nText\n## N\r\n");
        // Inserted lines take the ending of the line before them.
        assert_mixed_restore(
            "# T\r\nText\n## N\r\n",
            "# T\n\nText\n\n## N\n",
            "# T\r\n\r\nText\n\n## N\r\n",
        );
        // An edited line keeps the ending of the line it replaces.
        assert_mixed_restore("a  \r\nb\nc  \r\n", "a\nb\nc\n", "a\r\nb\nc\r\n");
        // A deleted line takes its ending with it.
        assert_mixed_restore("a\r\nx\ny\r\nb\n", "a\nb\n", "a\r\nb\n");
        // A blank line inserted before an edited line takes the ending of the
        // line before it; the edited line keeps its own.
        assert_mixed_restore(
            "More\n```\r\ncode\n",
            "More\n\n```text\ncode\n",
            "More\n\n```text\r\ncode\n",
        );
        // A line inserted at the start takes the first line's ending.
        assert_mixed_restore("text\r\nmore\n", "# T\n\ntext\nmore\n", "# T\r\n\r\ntext\r\nmore\n");
        // A final newline added to an unterminated last line takes the ending
        // of the line before it.
        assert_mixed_restore("a\n# b\r\nc", "a\n# b\nc\n", "a\n# b\r\nc\r\n");
        // A line split in two: the inserted break takes the ending of the line
        // it splits, and the second part keeps that line's own.
        assert_mixed_restore("x\nlong line\r\ny\n", "x\nlong\nline\ny\n", "x\nlong\r\nline\r\ny\n");
    }

    #[test]
    fn normalized_line_ending_map_restores_the_original_bytes() {
        for original in [
            "",
            "no newline",
            "a\nb\n",
            "a\r\nb\r\n",
            "a\r\nb\nc\r\n",
            "a\nb\r\nc",
            "\r\n\r\n\n",
            "lone\rcarriage\r\nreturn\r",
            "é\r\n日本\n",
        ] {
            let normalized = normalize_line_ending(original, LineEnding::Lf);
            let map = NormalizedLineEndingMap::new(original);
            assert_eq!(map.restore(&normalized), original, "{original:?}");
        }
    }

    #[test]
    fn test_detect_line_ending() {
        assert_eq!(detect_line_ending("hello\nworld"), "\n");
        assert_eq!(detect_line_ending("hello\r\nworld"), "\r\n");
        assert_eq!(detect_line_ending("hello\r\nworld\nmixed"), "\n"); // More LF than CRLF
        assert_eq!(detect_line_ending("no line endings"), "\n");
    }

    #[test]
    fn test_normalize_line_ending() {
        assert_eq!(normalize_line_ending("hello\r\nworld", LineEnding::Lf), "hello\nworld");
        assert_eq!(
            normalize_line_ending("hello\nworld", LineEnding::Crlf),
            "hello\r\nworld"
        );
        assert_eq!(
            normalize_line_ending("hello\r\nworld\nmixed", LineEnding::Lf),
            "hello\nworld\nmixed"
        );
    }

    #[test]
    fn test_ensure_consistent_line_endings() {
        let original = "hello\r\nworld";
        let modified = "hello\nworld\nextra";
        assert_eq!(
            ensure_consistent_line_endings(original, modified),
            "hello\r\nworld\r\nextra"
        );

        let original = "hello\nworld";
        let modified = "hello\r\nworld\r\nextra";
        assert_eq!(
            ensure_consistent_line_endings(original, modified),
            "hello\nworld\nextra"
        );
    }
}