diffs_rs/

projection.rs

use std::{num::NonZeroU32, ops::Range};

use crate::model::{
    Document, FileDiff, Kind, Row, RowKind, SourceLine, alignment_needed, alignment_offset,
};

mod storage;
use storage::{TableBuilder, Tables, compact_fits};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum BlockKind {
    Header,
    Hunk(usize),
    Gap,
    Metadata,
    Context { source_start: usize },
    Replacement(usize),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Block {
    start: [usize; 2],
    kind: BlockKind,
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct Replacement {
    old_start: usize,
    new_start: usize,
    end: usize,
    old_pad: usize,
    new_pad: usize,
}

impl Replacement {
    fn old_range(&self) -> Range<usize> {
        self.old_start..self.new_start
    }

    fn new_range(&self) -> Range<usize> {
        self.new_start..self.end
    }
}

const _: () = assert!(size_of::<Replacement>() == 5 * size_of::<usize>());

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SourceRun {
    start: usize,
    block: usize,
    ordinal: usize,
    old: Option<NonZeroU32>,
    new: Option<NonZeroU32>,
    kind: Kind,
}

#[derive(Debug)]
struct Marker {
    logical: usize,
    display: usize,
    left: bool,
    right: bool,
}

#[derive(Debug, Default)]
pub struct Projection {
    tables: Tables,
    markers: [Box<[Marker]>; 2],
    hunks: Box<[[usize; 2]]>,
    len: [usize; 2],
    source_len: usize,
}

impl Projection {
    pub fn new(parsed: &Document, meta: &FileDiff) -> Self {
        let base = meta.hunks.first().map_or(0, |h| h.lines.start);
        let end = meta.hunks.last().map_or(base, |h| h.lines.end);
        Self::build(
            parsed,
            meta,
            base,
            end,
            compact_fits(end - base, meta.hunks.len()),
        )
    }

    fn build(parsed: &Document, meta: &FileDiff, base: usize, end: usize, compact: bool) -> Self {
        let mut builder = Builder {
            tables: TableBuilder::new(compact),
            len: [0; 2],
        };
        builder.structural(BlockKind::Header);
        if meta.hunks.is_empty() {
            builder.structural(BlockKind::Metadata);
        }
        builder.file(parsed, meta, base);
        let mut projection = Self {
            tables: builder.tables.finish(),
            len: builder.len,
            source_len: end - base,
            ..Self::default()
        };
        for (layout, split) in [false, true].into_iter().enumerate() {
            let mut markers: Vec<Marker> = parsed.lines[base..end]
                .iter()
                .enumerate()
                .filter(|(_, line)| line.no_newline)
                .map(|(id, line)| Marker {
                    logical: projection.logical_source_row(id, split),
                    display: 0,
                    left: line.old.is_some(),
                    right: line.new.is_some(),
                })
                .collect();
            markers.sort_unstable_by_key(|m| m.logical);
            markers.dedup_by(|next, previous| {
                if next.logical != previous.logical {
                    return false;
                }
                previous.left |= next.left;
                previous.right |= next.right;
                true
            });
            for (n, marker) in markers.iter_mut().enumerate() {
                marker.display = marker.logical + n + 1;
            }
            projection.markers[layout] = markers.into_boxed_slice();
        }
        projection.hunks = (0..projection.tables.block_count())
            .map(|n| projection.tables.block(n))
            .filter(|b| matches!(b.kind, BlockKind::Hunk(_)))
            .map(|b| {
                [
                    projection.display_row(b.start[0], false),
                    projection.display_row(b.start[1], true),
                ]
            })
            .collect();
        projection
    }

    fn run(&self, id: usize) -> SourceRun {
        self.tables.run_at(id)
    }

    fn run_len(&self, index: usize) -> usize {
        self.tables.run_end(index, self.source_len) - self.tables.run(index).start
    }

    fn side_len(&self, side: &Range<usize>) -> usize {
        if side.is_empty() {
            0
        } else {
            let r = self.tables.side_run(side.end - 1);
            self.tables.run(r).ordinal + self.run_len(r)
        }
    }

    fn side_source(&self, side: &Range<usize>, ordinal: usize) -> Option<usize> {
        let r = self.tables.side_run_at(side.clone(), ordinal)?;
        let run = self.tables.run(r);
        let delta = ordinal - run.ordinal;
        (delta < self.run_len(r)).then_some(run.start + delta)
    }

    pub fn info(&self, id: usize) -> (Kind, Option<u32>, Option<u32>) {
        let run = self.run(id);
        let delta = (id - run.start) as u32;
        (
            run.kind,
            run.old.map(|n| n.get() + delta),
            run.new.map(|n| n.get() + delta),
        )
    }

    pub(crate) fn source_intervals(
        &self,
        old: bool,
    ) -> impl Iterator<Item = (Range<usize>, Option<u32>)> + '_ {
        (0..self.tables.run_count()).map(move |index| {
            let run = self.tables.run(index);
            let line = if old { run.old } else { run.new };
            (
                run.start..run.start + self.run_len(index),
                line.map(NonZeroU32::get),
            )
        })
    }

    fn logical_source_row(&self, id: usize, split: bool) -> usize {
        let run = self.run(id);
        let block = self.tables.block(run.block);
        let ordinal = run.ordinal + id - run.start;
        block.start[usize::from(split)]
            + match &block.kind {
                BlockKind::Context { source_start } => id - source_start,
                BlockKind::Replacement(r) => {
                    let r = self.tables.replacement(*r);
                    match (split, run.kind) {
                        (true, Kind::Deletion) => r.old_pad + ordinal,
                        (true, _) => r.new_pad + ordinal,
                        (false, Kind::Deletion) => ordinal,
                        (false, _) => self.side_len(&r.old_range()) + ordinal,
                    }
                }
                _ => unreachable!("A source run must belong to a source block"),
            }
    }

    fn display_row(&self, logical: usize, split: bool) -> usize {
        logical + self.markers[usize::from(split)].partition_point(|m| m.logical < logical)
    }

    pub fn row_for_source(&self, id: usize, split: bool) -> usize {
        self.display_row(self.logical_source_row(id, split), split)
    }

    pub(crate) fn hunk_row(&self, index: usize, split: bool) -> usize {
        self.hunks[index][usize::from(split)]
    }

    pub fn rows(&self, split: bool, file: usize, source_base: usize) -> Rows<'_> {
        Rows {
            projection: self,
            split,
            file,
            source_base,
        }
    }

    pub fn source_run_bytes(&self) -> usize {
        self.tables.source_run_bytes()
    }
    pub fn block_bytes(&self) -> usize {
        self.tables.block_bytes()
    }
    pub fn side_index_bytes(&self) -> usize {
        self.tables.side_index_bytes()
    }
    pub fn marker_bytes(&self) -> usize {
        self.markers
            .iter()
            .map(|m| m.len() * size_of::<Marker>())
            .sum()
    }
    pub fn boundary_bytes(&self) -> usize {
        self.hunks.len() * size_of::<[usize; 2]>()
    }
    pub fn bytes(&self) -> usize {
        self.source_run_bytes()
            + self.block_bytes()
            + self.side_index_bytes()
            + self.marker_bytes()
            + self.boundary_bytes()
    }
}

pub struct Rows<'a> {
    projection: &'a Projection,
    split: bool,
    file: usize,
    source_base: usize,
}

impl Rows<'_> {
    pub fn len(&self) -> usize {
        let layout = usize::from(self.split);
        self.projection.len[layout] + self.projection.markers[layout].len()
    }
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn get(&self, index: usize) -> Option<Row> {
        if index >= self.len() {
            return None;
        }
        let p = self.projection;
        let layout = usize::from(self.split);
        let markers = &p.markers[layout];
        let before = markers.partition_point(|m| m.display <= index);
        if let Some(marker) = before.checked_sub(1).map(|i| &markers[i])
            && marker.display == index
        {
            return Some(Row {
                file: self.file,
                kind: RowKind::NoNewline {
                    left: marker.left,
                    right: marker.right,
                },
            });
        }
        let logical = index - before;
        let block = p.tables.block_at(layout, logical);
        let ordinal = logical - block.start[layout];
        let kind = match &block.kind {
            BlockKind::Header => RowKind::Header,
            BlockKind::Hunk(h) => RowKind::Hunk(*h),
            BlockKind::Gap => RowKind::Gap,
            BlockKind::Metadata => RowKind::Metadata,
            BlockKind::Context { source_start } => RowKind::Code {
                left: Some(self.source_base + source_start + ordinal),
                right: Some(self.source_base + source_start + ordinal),
            },
            BlockKind::Replacement(r) => {
                let r = p.tables.replacement(*r);
                let (left, right) = if self.split {
                    (
                        ordinal
                            .checked_sub(r.old_pad)
                            .and_then(|n| p.side_source(&r.old_range(), n)),
                        ordinal
                            .checked_sub(r.new_pad)
                            .and_then(|n| p.side_source(&r.new_range(), n)),
                    )
                } else {
                    let old_len = p.side_len(&r.old_range());
                    if ordinal < old_len {
                        (p.side_source(&r.old_range(), ordinal), None)
                    } else {
                        (None, p.side_source(&r.new_range(), ordinal - old_len))
                    }
                };
                RowKind::Code {
                    left: left.map(|n| n + self.source_base),
                    right: right.map(|n| n + self.source_base),
                }
            }
        };
        Some(Row {
            file: self.file,
            kind,
        })
    }

    pub fn boundary(&self, index: usize, forward: bool, file: bool) -> Option<usize> {
        if file {
            return (!forward && index > 0).then_some(0);
        }
        let h = &self.projection.hunks;
        let layout = usize::from(self.split);
        if forward {
            h.get(h.partition_point(|b| b[layout] <= index))
                .map(|b| b[layout])
        } else {
            h.partition_point(|b| b[layout] < index)
                .checked_sub(1)
                .map(|i| h[i][layout])
        }
    }

    pub fn first_boundary(&self, forward: bool, file: bool) -> Option<usize> {
        if file {
            return Some(0);
        }
        let h = &self.projection.hunks;
        (if forward { h.first() } else { h.last() }).map(|b| b[usize::from(self.split)])
    }
}

struct Builder {
    tables: TableBuilder,
    len: [usize; 2],
}

impl Builder {
    fn structural(&mut self, kind: BlockKind) {
        self.tables.push_block(Block {
            start: self.len,
            kind,
        });
        self.len[0] += 1;
        self.len[1] += 1;
    }

    fn source_runs(
        &mut self,
        lines: &[SourceLine],
        base: usize,
        range: Range<usize>,
    ) -> Range<usize> {
        let first = self.tables.run_count();
        let mut old_ordinal = 0;
        let mut new_ordinal = 0;
        for i in range {
            let line = &lines[i];
            let local = i - base;
            if self
                .tables
                .run_count()
                .checked_sub(1)
                .map(|n| self.tables.run(n))
                .is_none_or(|r| {
                    let delta = u32::try_from(local - r.start).ok();
                    r.block != self.tables.block_count()
                        || r.kind != line.kind
                        || r.old.and_then(|n| n.get().checked_add(delta?)) != line.old
                        || r.new.and_then(|n| n.get().checked_add(delta?)) != line.new
                })
            {
                self.tables.push_run(SourceRun {
                    start: local,
                    block: self.tables.block_count(),
                    ordinal: if line.kind == Kind::Deletion {
                        old_ordinal
                    } else {
                        new_ordinal
                    },
                    old: line
                        .old
                        .map(|n| NonZeroU32::new(n).expect("Validated source line is positive")),
                    new: line
                        .new
                        .map(|n| NonZeroU32::new(n).expect("Validated source line is positive")),
                    kind: line.kind,
                });
            }
            old_ordinal += usize::from(line.old.is_some());
            new_ordinal += usize::from(line.new.is_some());
        }
        first..self.tables.run_count()
    }

    fn file(&mut self, parsed: &Document, file: &FileDiff, base: usize) {
        let (mut old_end, mut new_end) = (1, 1);
        for (h, hunk) in file.hunks.iter().enumerate() {
            if hunk.old_start > old_end || hunk.new_start > new_end {
                self.structural(BlockKind::Gap);
            }
            self.structural(BlockKind::Hunk(h));
            let mut i = hunk.lines.start;
            while i < hunk.lines.end {
                let start = i;
                let context = parsed.lines[i].kind == Kind::Context;
                while i < hunk.lines.end && (parsed.lines[i].kind == Kind::Context) == context {
                    i += 1;
                }
                let runs = self.source_runs(&parsed.lines, base, start..i);
                let (kind, split_len, unified_len) = if context {
                    (
                        BlockKind::Context {
                            source_start: start - base,
                        },
                        i - start,
                        i - start,
                    )
                } else {
                    let old_len = parsed.lines[start..i]
                        .iter()
                        .filter(|line| line.kind == Kind::Deletion)
                        .count();
                    let new_len = i - start - old_len;
                    let offset = if alignment_needed(old_len, new_len) {
                        let old: Vec<_> = (start..i)
                            .filter(|&id| parsed.lines[id].kind == Kind::Deletion)
                            .collect();
                        let new: Vec<_> = (start..i)
                            .filter(|&id| parsed.lines[id].kind == Kind::Addition)
                            .collect();
                        alignment_offset(&parsed.lines, &old, &new)
                    } else {
                        0
                    };
                    let old_pad = if new_len > old_len { offset } else { 0 };
                    let new_pad = if old_len > new_len { offset } else { 0 };
                    let side_start = self.tables.side_count();
                    for r in runs.clone() {
                        if self.tables.run(r).kind == Kind::Deletion {
                            self.tables.push_side(r);
                        }
                    }
                    let middle = self.tables.side_count();
                    for r in runs {
                        if self.tables.run(r).kind == Kind::Addition {
                            self.tables.push_side(r);
                        }
                    }
                    let replacement = self.tables.replacement_count();
                    self.tables.push_replacement(Replacement {
                        old_start: side_start,
                        new_start: middle,
                        end: self.tables.side_count(),
                        old_pad,
                        new_pad,
                    });
                    (
                        BlockKind::Replacement(replacement),
                        (old_len + old_pad).max(new_len + new_pad),
                        old_len + new_len,
                    )
                };
                self.tables.push_block(Block {
                    start: self.len,
                    kind,
                });
                self.len[0] += unified_len;
                self.len[1] += split_len;
            }
            for line in &parsed.lines[hunk.lines.clone()] {
                if let Some(n) = line.old {
                    old_end = n.saturating_add(1);
                }
                if let Some(n) = line.new {
                    new_end = n.saturating_add(1);
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::Projection;
    use crate::model::{Document, RowKind};

    #[test]
    fn both_storage_forms_preserve_parsed_views_and_wide_document_bases() {
        let patch = concat!(
            "diff --git a/review b/review\n--- a/review\n+++ b/review\n",
            "@@ -2,4 +2,5 @@\n head\n-let retries = 3;\n+// inserted\n+let retries = 5;\n-let delay = 10;\n+let delay = 20;\n tail\n",
            "@@ -20,5 +21,3 @@\n start\n-obsolete_one();\n-obsolete_two();\n-let retries = 3;\n+let retries = 5;\n end\n",
            "@@ -60,0 +62,2 @@\n+first addition\n+second addition\n",
            "@@ -80,2 +84,0 @@\n-first deletion\n-second deletion\n",
            "@@ -100,2 +102,2 @@\n-old one\n-old two\n+new one\n+new two\n",
            "@@ -120,2 +121,3 @@\n shared\n-old end\n\\ No newline at end of file\n+inserted\n+new end\n\\ No newline at end of file\n",
        ).as_bytes();
        let parsed = Document::parse(patch).unwrap();
        let file = &parsed.files[0];
        let compact = Projection::new(&parsed, file);
        let wide = Projection::build(&parsed, file, 0, parsed.lines.len(), false);
        assert!(compact.bytes() < wide.bytes());
        assert_eq!(compact.marker_bytes(), wide.marker_bytes());
        assert_eq!(compact.boundary_bytes(), wide.boundary_bytes());
        let base = usize::try_from(u64::from(u32::MAX) + 17).unwrap_or(17);
        for projection in [&compact, &wide] {
            assert_eq!(projection.tables.replacement(0).old_pad, 1);
            assert_eq!(projection.tables.replacement(1).new_pad, 2);
            assert!(projection.tables.replacement(2).old_range().is_empty());
            assert!(projection.tables.replacement(3).new_range().is_empty());
            for (id, line) in parsed.lines.iter().enumerate() {
                assert_eq!(projection.info(id), (line.kind, line.old, line.new));
            }
            for split in [false, true] {
                let rows = projection.rows(split, 7, base);
                let (expected, inverse) = if split {
                    (&parsed.split, &parsed.split_locations)
                } else {
                    (&parsed.unified, &parsed.unified_locations)
                };
                assert_eq!(rows.len(), expected.len());
                assert!(rows.get(expected.len()).is_none());
                for (n, expected) in expected.iter().enumerate() {
                    let actual = rows.get(n).unwrap();
                    let kind = match expected.kind {
                        RowKind::Code { left, right } => RowKind::Code {
                            left: left.map(|id| base + id),
                            right: right.map(|id| base + id),
                        },
                        kind => kind,
                    };
                    assert_eq!(actual.file, 7);
                    assert_eq!(actual.kind, kind);
                }
                for (id, &row) in inverse.iter().enumerate() {
                    assert_eq!(projection.row_for_source(id, split), row);
                }
                for file_boundary in [false, true] {
                    let boundaries: Vec<_> = expected
                        .iter()
                        .enumerate()
                        .filter_map(|(n, row)| {
                            (if file_boundary {
                                matches!(row.kind, RowKind::Header)
                            } else {
                                matches!(row.kind, RowKind::Hunk(_))
                            })
                            .then_some(n)
                        })
                        .collect();
                    for forward in [false, true] {
                        assert_eq!(
                            rows.first_boundary(forward, file_boundary),
                            if forward {
                                boundaries.first().copied()
                            } else {
                                boundaries.last().copied()
                            }
                        );
                        for n in 0..rows.len() {
                            let expected = if forward {
                                boundaries.iter().copied().find(|&b| b > n)
                            } else {
                                boundaries.iter().rev().copied().find(|&b| b < n)
                            };
                            assert_eq!(rows.boundary(n, forward, file_boundary), expected);
                        }
                    }
                }
            }
        }
    }

    #[test]
    fn source_runs_preserve_line_number_endpoints_and_absent_sides() {
        let patch = b"diff --git a/numbers b/numbers\n--- a/numbers\n+++ b/numbers\n@@ -1,4 +1,4 @@\n a\n-b\n-c\n+d\n+e\n f\n";
        for first in [1, u32::MAX - 3] {
            let mut parsed = Document::parse_file(patch).unwrap();
            for line in &mut parsed.lines {
                line.old = line.old.map(|n| first + (n - 1));
                line.new = line.new.map(|n| first + (n - 1));
            }
            let file = &mut parsed.files[0];
            file.hunks[0].old_start = first;
            file.hunks[0].new_start = first;
            let projection = Projection::new(&parsed, &parsed.files[0]);
            for (id, line) in parsed.lines.iter().enumerate() {
                assert_eq!(projection.info(id), (line.kind, line.old, line.new));
            }
            for (split, expected) in [
                (
                    true,
                    &[
                        (Some(0), Some(0)),
                        (Some(1), Some(3)),
                        (Some(2), Some(4)),
                        (Some(5), Some(5)),
                    ][..],
                ),
                (
                    false,
                    &[
                        (Some(0), Some(0)),
                        (Some(1), None),
                        (Some(2), None),
                        (None, Some(3)),
                        (None, Some(4)),
                        (Some(5), Some(5)),
                    ][..],
                ),
            ] {
                let rows = projection.rows(split, 0, 0);
                let start = 2 + usize::from(first > 1);
                assert_eq!(rows.len(), start + expected.len());
                for (offset, &(left, right)) in expected.iter().enumerate() {
                    let row = start + offset;
                    assert_eq!(rows.get(row).unwrap().kind, RowKind::Code { left, right });
                    for id in left.into_iter().chain(right) {
                        assert_eq!(projection.row_for_source(id, split), row);
                    }
                }
            }
        }
    }
}