use std::{io::BufRead, ops::Range};
use anyhow::{Context, Result, bail};
use git2::{Delta, Diff, Patch};
use serde::Serialize;
mod rename_names;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
pub enum Kind {
Context,
Addition,
Deletion,
}
#[derive(Debug, Serialize)]
pub struct SourceLine {
pub kind: Kind,
pub old: Option<u32>,
pub new: Option<u32>,
pub bytes: Vec<u8>,
pub no_newline: bool,
#[serde(skip)]
pub offset: usize,
}
#[derive(Debug, Serialize)]
pub struct Hunk {
pub header: String,
pub old_start: u32,
pub new_start: u32,
pub lines: Range<usize>,
}
#[derive(Debug, Serialize)]
pub struct FileDiff {
#[serde(skip)]
pub(crate) identity: PatchIdentity,
#[serde(skip)]
pub raw_path: Vec<u8>,
pub path: String,
pub old_path: String,
pub status: String,
pub old_mode: String,
pub new_mode: String,
pub additions: usize,
pub deletions: usize,
pub digits: usize,
pub hunks: Vec<Hunk>,
}
#[derive(Clone, Debug, Default)]
pub(crate) struct PatchIdentity {
pub old_path: Vec<u8>,
pub new_path: Vec<u8>,
pub old_oid: Option<git2::Oid>,
pub new_oid: Option<git2::Oid>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum RowKind<S = usize> {
Header,
Hunk(usize),
Gap,
Metadata,
Code { left: Option<S>, right: Option<S> },
NoNewline { left: bool, right: bool },
}
#[derive(Clone, Copy, Debug)]
pub struct Row<S = usize> {
pub file: usize,
pub kind: RowKind<S>,
}
impl<S> Row<S> {
pub fn map<T>(self, mut source: impl FnMut(S) -> T) -> Row<T> {
Row {
file: self.file,
kind: match self.kind {
RowKind::Header => RowKind::Header,
RowKind::Hunk(h) => RowKind::Hunk(h),
RowKind::Gap => RowKind::Gap,
RowKind::Metadata => RowKind::Metadata,
RowKind::Code { left, right } => RowKind::Code {
left: left.map(&mut source),
right: right.map(source),
},
RowKind::NoNewline { left, right } => RowKind::NoNewline { left, right },
},
}
}
}
#[derive(Debug, Default, Serialize)]
pub struct Document {
pub files: Vec<FileDiff>,
pub lines: Vec<SourceLine>,
#[serde(skip)]
pub split: Vec<Row>,
#[serde(skip)]
pub unified: Vec<Row>,
#[serde(skip)]
pub split_locations: Vec<usize>,
#[serde(skip)]
pub unified_locations: Vec<usize>,
}
impl Document {
pub fn parse(input: &[u8]) -> Result<Self> {
Self::read(std::io::Cursor::new(input))
}
pub fn read(input: impl BufRead) -> Result<Self> {
let mut doc = Self::default();
crate::ingest::visit_files(input, |_, unit| {
let mut part = Self::parse_file(unit)?;
let base = doc.lines.len();
for file in &mut part.files {
for hunk in &mut file.hunks {
hunk.lines = (hunk.lines.start + base)..(hunk.lines.end + base);
}
}
doc.lines.append(&mut part.lines);
doc.files.append(&mut part.files);
Ok(())
})?;
doc.index_rows();
Ok(doc)
}
pub fn parse_file(input: &[u8]) -> Result<Self> {
if input.iter().all(u8::is_ascii_whitespace) {
return Ok(Self::default());
}
if input
.split(|b| *b == b'\n')
.any(|l| l.starts_with(b"diff --cc ") || l.starts_with(b"diff --combined "))
{
bail!("Combined merge diffs are not supported. Supply a two-sided patch.");
}
let normalized = empty_file_headers(input);
let normalized = normalized.as_deref().unwrap_or(input);
let quoted = rename_names::quote_rename_names(normalized);
let diff = Diff::from_buffer(quoted.as_ref().map_or(normalized, |q| &q.bytes))
.context("Cannot parse this patch")?;
if diff.deltas().len() == 0 {
bail!("The input contains no recognized file changes.");
}
let mut doc = Self::default();
for (file_index, delta) in diff.deltas().enumerate() {
let old_path =
crate::text::safe_label(delta.old_file().path_bytes().unwrap_or(b"/dev/null"));
let path =
crate::text::safe_label(delta.new_file().path_bytes().unwrap_or(b"/dev/null"));
let mut file = FileDiff {
identity: PatchIdentity {
old_path: delta
.old_file()
.path_bytes()
.unwrap_or(b"/dev/null")
.to_vec(),
new_path: delta
.new_file()
.path_bytes()
.unwrap_or(b"/dev/null")
.to_vec(),
old_oid: (!delta.old_file().id().is_zero()).then(|| delta.old_file().id()),
new_oid: (!delta.new_file().id().is_zero()).then(|| delta.new_file().id()),
},
raw_path: if delta.status() == Delta::Deleted {
delta.old_file().path_bytes().unwrap_or(b"/dev/null")
} else {
delta.new_file().path_bytes().unwrap_or(b"/dev/null")
}
.to_vec(),
path: if delta.status() == Delta::Deleted {
old_path.clone()
} else {
path
},
old_path,
status: match delta.status() {
Delta::Added => "Added",
Delta::Deleted => "Deleted",
Delta::Renamed => "Renamed",
Delta::Copied => "Copied",
Delta::Typechange => "Type changed",
_ => "Modified",
}
.into(),
old_mode: format!("{:o}", u32::from(delta.old_file().mode())),
new_mode: format!("{:o}", u32::from(delta.new_file().mode())),
additions: 0,
deletions: 0,
digits: 3,
hunks: Vec::new(),
};
if let Some(patch) = Patch::from_diff(&diff, file_index)? {
let (mut old_end, mut new_end) = (0, 0);
for hunk_index in 0..patch.num_hunks() {
let (hunk, count) = patch.hunk(hunk_index)?;
let old_start = u64::from(hunk.old_start()) + u64::from(hunk.old_lines() == 0);
let new_start = u64::from(hunk.new_start()) + u64::from(hunk.new_lines() == 0);
if old_start < old_end || new_start < new_end {
bail!("Hunks overlap or appear out of source order");
}
old_end = old_start + u64::from(hunk.old_lines());
new_end = new_start + u64::from(hunk.new_lines());
let start = doc.lines.len();
let (mut old_count, mut new_count) = (0, 0);
for i in 0..count {
let line = patch.line_in_hunk(hunk_index, i)?;
let kind = match line.origin() {
' ' => Kind::Context,
'+' => Kind::Addition,
'-' => Kind::Deletion,
'=' | '<' | '>' => {
if doc.lines.len() == start {
bail!("Newline marker without a source line in this hunk");
}
let previous = doc
.lines
.last_mut()
.context("Newline marker without a source line")?;
previous.no_newline = true;
if previous.bytes.last() == Some(&b'\n') {
previous.bytes.pop();
}
continue;
}
c => bail!("Unsupported patch line type: {c:?}"),
};
let old = line.old_lineno();
let new = line.new_lineno();
if let Some(n) = old {
if n == 0 || Some(n) != hunk.old_start().checked_add(old_count) {
bail!("Non-contiguous old source line");
}
old_count += 1;
}
if let Some(n) = new {
if n == 0 || Some(n) != hunk.new_start().checked_add(new_count) {
bail!("Non-contiguous new source line");
}
new_count += 1;
}
file.additions += usize::from(kind == Kind::Addition);
file.deletions += usize::from(kind == Kind::Deletion);
let largest = old.unwrap_or(0).max(new.unwrap_or(0)).max(1);
file.digits = file.digits.max(largest.ilog10() as usize + 1);
let offset = usize::try_from(line.content_offset())?;
let offset = match "ed {
Some(quoted) => quoted.original_offset(offset),
None => Some(offset),
}
.and_then(|offset| offset.checked_add(1))
.context("Source offset overflow")?;
let end = offset
.checked_add(line.content().len())
.context("Source length overflow")?;
anyhow::ensure!(
input.get(offset..end) == Some(line.content()),
"Parser source offset does not match the supplied patch"
);
doc.lines.push(SourceLine {
kind,
old,
new,
bytes: line.content().to_vec(),
no_newline: false,
offset,
});
}
if old_count != hunk.old_lines() || new_count != hunk.new_lines() {
bail!("Hunk counts do not agree with its source lines");
}
file.hunks.push(Hunk {
header: crate::text::safe_label(
hunk.header().strip_suffix(b"\n").unwrap_or(hunk.header()),
),
old_start: hunk.old_start(),
new_start: hunk.new_start(),
lines: start..doc.lines.len(),
});
}
}
if delta.flags().is_binary() {
file.status = "Binary change".into();
}
doc.files.push(file);
}
Ok(doc)
}
fn push_both(&mut self, file: usize, kind: RowKind) {
self.split.push(Row { file, kind });
self.unified.push(Row { file, kind });
}
pub(crate) fn index_rows(&mut self) {
self.split_locations.resize(self.lines.len(), 0);
self.unified_locations.resize(self.lines.len(), 0);
for f in 0..self.files.len() {
self.push_both(f, RowKind::Header);
if self.files[f].hunks.is_empty() {
self.push_both(f, RowKind::Metadata);
}
let (mut old_end, mut new_end) = (1, 1);
for h in 0..self.files[f].hunks.len() {
let hunk = &self.files[f].hunks[h];
let range = hunk.lines.clone();
if hunk.old_start > old_end || hunk.new_start > new_end {
self.push_both(f, RowKind::Gap);
}
self.push_both(f, RowKind::Hunk(h));
let mut i = range.start;
while i < range.end {
if self.lines[i].kind == Kind::Context {
self.add_split(f, Some(i), Some(i));
self.add_unified(f, i);
i += 1;
} else {
let start = i;
while i < range.end && self.lines[i].kind != Kind::Context {
i += 1;
}
let left: Vec<_> = (start..i)
.filter(|n| self.lines[*n].kind == Kind::Deletion)
.collect();
let right: Vec<_> = (start..i)
.filter(|n| self.lines[*n].kind == Kind::Addition)
.collect();
for id in left.iter().chain(&right) {
self.add_unified(f, *id);
}
let offset = alignment_offset(&self.lines, &left, &right);
let left_pad = if right.len() > left.len() { offset } else { 0 };
let right_pad = if left.len() > right.len() { offset } else { 0 };
for row in 0..(left.len() + left_pad).max(right.len() + right_pad) {
let l = row.checked_sub(left_pad).and_then(|n| left.get(n)).copied();
let r = row
.checked_sub(right_pad)
.and_then(|n| right.get(n))
.copied();
self.add_split(f, l, r);
}
}
}
for line in &self.lines[range] {
if let Some(n) = line.old {
old_end = n.saturating_add(1);
}
if let Some(n) = line.new {
new_end = n.saturating_add(1);
}
}
}
}
}
fn add_split(&mut self, file: usize, left: Option<usize>, right: Option<usize>) {
for id in left.into_iter().chain(right) {
self.split_locations[id] = self.split.len();
}
self.split.push(Row {
file,
kind: RowKind::Code { left, right },
});
let l = left.is_some_and(|i| self.lines[i].no_newline);
let r = right.is_some_and(|i| self.lines[i].no_newline);
if l || r {
self.split.push(Row {
file,
kind: RowKind::NoNewline { left: l, right: r },
});
}
}
fn add_unified(&mut self, file: usize, id: usize) {
let line = &self.lines[id];
self.unified_locations[id] = self.unified.len();
let left = line.old.map(|_| id);
let right = line.new.map(|_| id);
self.unified.push(Row {
file,
kind: RowKind::Code { left, right },
});
if line.no_newline {
self.unified.push(Row {
file,
kind: RowKind::NoNewline {
left: left.is_some(),
right: right.is_some(),
},
});
}
}
}
fn empty_file_headers(input: &[u8]) -> Option<Vec<u8>> {
let mut lines = input.split_inclusive(|b| *b == b'\n');
let (header, mode, index) = (lines.next()?, lines.next()?, lines.next()?);
if lines.next().is_some() {
return None;
}
let added = mode.starts_with(b"new file mode ");
let deleted = mode.starts_with(b"deleted file mode ");
if !(added || deleted) || !index.starts_with(b"index ") {
return None;
}
let header = header.strip_prefix(b"diff --git ")?.strip_suffix(b"\n")?;
let (old, new) = split_identical_paths(header)?;
let ids = index.strip_prefix(b"index ")?.strip_suffix(b"\n")?;
let (old_id, new_id) = std::str::from_utf8(ids).ok()?.split_once("..")?;
let empty = "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391";
let matches_empty = |id: &str| id.len() >= 7 && empty.starts_with(id);
let zero = |id: &str| id.len() >= 7 && id.bytes().all(|b| b == b'0');
if !((added && zero(old_id) && matches_empty(new_id))
|| (deleted && matches_empty(old_id) && zero(new_id)))
{
return None;
}
let mut result = input.to_vec();
result.extend_from_slice(b"--- ");
result.extend_from_slice(if added { b"/dev/null" } else { old });
result.extend_from_slice(b"\n+++ ");
result.extend_from_slice(if deleted { b"/dev/null" } else { new });
result.extend_from_slice(b"\n");
Some(result)
}
fn split_identical_paths(header: &[u8]) -> Option<(&[u8], &[u8])> {
let middle = header.len() / 2;
if header.get(middle) != Some(&b' ') {
return None;
}
let (old, new) = (&header[..middle], &header[middle + 1..]);
let unquoted = old.strip_prefix(b"a/").zip(new.strip_prefix(b"b/"));
let quoted = old.strip_prefix(b"\"a/").zip(new.strip_prefix(b"\"b/"));
if unquoted.or(quoted).is_some_and(|(a, b)| a == b) {
Some((old, new))
} else {
None
}
}
pub(crate) fn alignment_offset(lines: &[SourceLine], left: &[usize], right: &[usize]) -> usize {
let pairs = left.len().min(right.len());
let extra = left.len().abs_diff(right.len());
if !alignment_needed(left.len(), right.len()) {
return 0;
}
if left
.iter()
.chain(right)
.any(|i| lines[*i].bytes.len() > 4096)
{
return 0;
}
let mut a = Vec::with_capacity(
left.iter()
.map(|&i| lines[i].bytes.len())
.max()
.unwrap_or(0),
);
let mut b = Vec::with_capacity(
right
.iter()
.map(|&i| lines[i].bytes.len())
.max()
.unwrap_or(0),
);
let mut score = |offset: usize| -> f64 {
(0..pairs)
.map(|p| {
let left_bytes =
&lines[left[p + if left.len() > right.len() { offset } else { 0 }]].bytes;
let right_bytes =
&lines[right[p + if right.len() > left.len() { offset } else { 0 }]].bytes;
a.clear();
b.clear();
a.extend(
left_bytes
.iter()
.copied()
.filter(|c| !c.is_ascii_whitespace()),
);
b.extend(
right_bytes
.iter()
.copied()
.filter(|c| !c.is_ascii_whitespace()),
);
let prefix = a.iter().zip(&b).take_while(|(x, y)| x == y).count();
let suffix = a[prefix..]
.iter()
.rev()
.zip(b[prefix..].iter().rev())
.take_while(|(x, y)| x == y)
.count();
(prefix + suffix) as f64 / a.len().max(b.len()).max(1) as f64
})
.sum()
};
let mut best = score(0) + pairs as f64 * 0.5;
let mut offset = 0;
for n in 1..=extra {
let s = score(n);
if s > best {
best = s;
offset = n;
}
}
offset
}
pub(crate) fn alignment_needed(old: usize, new: usize) -> bool {
let pairs = old.min(new);
let extra = old.abs_diff(new);
pairs != 0 && extra != 0 && pairs.saturating_mul(extra + 1) <= 4096
}