use std::path::{Path, PathBuf};
use std::sync::Arc;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StreamToken {
pub spelling: Box<str>,
pub file: Option<Arc<Path>>,
pub line: Option<u32>,
}
impl StreamToken {
pub fn new(spelling: impl Into<Box<str>>, file: Option<Arc<Path>>, line: Option<u32>) -> Self {
StreamToken {
spelling: spelling.into(),
file,
line,
}
}
pub fn origin(&self) -> String {
match (&self.file, self.line) {
(Some(path), Some(line)) => format!("{}:{line}", path.display()),
(Some(path), None) => path.display().to_string(),
(None, Some(line)) => format!("line {line}"),
(None, None) => "?".to_string(),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Side {
Ours,
Theirs,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Difference {
pub at: usize,
pub ours: Option<StreamToken>,
pub theirs: Option<StreamToken>,
pub run: usize,
pub run_ours: usize,
pub run_theirs: usize,
}
impl Difference {
pub fn side(&self) -> Side {
if self.ours.is_some() {
Side::Ours
} else {
Side::Theirs
}
}
pub fn is_isolated(&self) -> bool {
self.run <= 1
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum Reason {
UnexpandedMacro,
MissingExpansion,
ConditionDisagreement,
BranchDisagreement,
ExpansionDisagreement,
MissingHeader,
Unknown,
}
impl Reason {
pub fn advice(&self) -> &'static str {
match self {
Reason::UnexpandedMacro => {
"a name survived into our stream: the expander had no body for it (see `Configuration`) \
or the invocation did not parse as a call"
}
Reason::MissingExpansion => {
"the compiler expanded something we never had: the file that defines it is not in our closure \
(an unresolved include, or a header we read as empty)"
}
Reason::ConditionDisagreement => {
"the two readings took different branches of an `#if`: a predefined macro is missing from our \
table, or one of them evaluated to the wrong value"
}
Reason::BranchDisagreement => {
"a whole region moved, not one token: an `#if` was decided the other way, so look for the \
predefined macro it asks about before looking at the parser"
}
Reason::ExpansionDisagreement => {
"one name on one side and its replacement list on the other: the expander had no body for it, or \
substituted differently —compare the two tables for the name quoted"
}
Reason::MissingHeader => {
"the compiler read a header this reading never entered: the include resolver could not find it"
}
Reason::Unknown => {
"the shape of the pair does not identify a mechanism; read the quoted tokens"
}
}
}
}
impl Difference {
pub fn reason(&self, our_files: &std::collections::HashSet<&Path>) -> Reason {
let is_a_name = |token: &Option<StreamToken>| {
token.as_ref().is_some_and(|token| {
let mut characters = token.spelling.chars();
characters
.next()
.is_some_and(|first| first == '_' || first.is_alphabetic())
})
};
let is_a_number = |token: &Option<StreamToken>| {
token
.as_ref()
.is_some_and(|token| token.spelling.starts_with(|c: char| c.is_ascii_digit()))
};
if let Some(theirs) = &self.theirs
&& let Some(file) = &theirs.file
&& !our_files.contains(file.as_ref())
{
return Reason::MissingHeader;
}
if self.run_ours == 1 && self.run_theirs == 0 && is_a_name(&self.ours) {
return Reason::UnexpandedMacro;
}
if self.run_ours == 0 && self.run_theirs == 1 && is_a_name(&self.theirs) {
return Reason::MissingExpansion;
}
if self.run_ours == 0 || self.run_theirs == 0 {
return Reason::BranchDisagreement;
}
if self.run_ours != self.run_theirs {
return Reason::ExpansionDisagreement;
}
if is_a_name(&self.ours) != is_a_name(&self.theirs)
&& (is_a_number(&self.ours) || is_a_number(&self.theirs))
{
return Reason::ConditionDisagreement;
}
Reason::Unknown
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Alignment {
pub differences: Vec<Difference>,
pub matched: usize,
pub truncated: bool,
}
impl Alignment {
pub fn by_reason(&self, our_files: &std::collections::HashSet<&Path>) -> Vec<(Reason, usize)> {
let mut counts: std::collections::BTreeMap<Reason, usize> =
std::collections::BTreeMap::new();
for difference in &self.differences {
*counts.entry(difference.reason(our_files)).or_default() += 1;
}
let mut counted: Vec<(Reason, usize)> = counts.into_iter().collect();
counted.sort_by(|(left_reason, left), (right_reason, right)| {
right.cmp(left).then_with(|| left_reason.cmp(right_reason))
});
counted
}
pub fn agrees(&self) -> bool {
self.differences.is_empty() && !self.truncated
}
pub fn headers_we_never_entered(
&self,
our_files: &std::collections::HashSet<&Path>,
) -> Vec<&Path> {
let mut missing: Vec<&Path> = self
.differences
.iter()
.filter(|difference| difference.reason(our_files) == Reason::MissingHeader)
.filter_map(|difference| difference.theirs.as_ref()?.file.as_deref())
.collect();
missing.sort_unstable();
missing.dedup();
missing
}
}
pub const MAX_EDIT_DISTANCE: usize = 4096;
pub fn align(ours: &[StreamToken], theirs: &[StreamToken]) -> Alignment {
let mut alignment = Alignment::default();
let mut prefix = 0usize;
while prefix < ours.len()
&& prefix < theirs.len()
&& ours[prefix].spelling == theirs[prefix].spelling
{
prefix += 1;
}
let mut suffix = 0usize;
while suffix < ours.len() - prefix
&& suffix < theirs.len() - prefix
&& ours[ours.len() - 1 - suffix].spelling == theirs[theirs.len() - 1 - suffix].spelling
{
suffix += 1;
}
alignment.matched = 0;
let our_middle = &ours[prefix..ours.len() - suffix];
let their_middle = &theirs[prefix..theirs.len() - suffix];
let (edits, truncated) = anchored_edit_script(our_middle, their_middle, 0);
alignment.truncated = truncated;
for (at, ours_at, theirs_at) in edits {
alignment.differences.push(Difference {
at: prefix + at,
ours: ours_at.map(|index| our_middle[index].clone()),
theirs: theirs_at.map(|index| their_middle[index].clone()),
run: 1,
run_ours: 0,
run_theirs: 0,
});
}
alignment
.differences
.sort_by_key(|difference| difference.at);
alignment.matched = ours.len()
- alignment
.differences
.iter()
.filter(|difference| difference.ours.is_some())
.count();
group_into_runs(&mut alignment.differences);
alignment
}
fn group_into_runs(differences: &mut [Difference]) {
let mut start = 0usize;
while start < differences.len() {
let mut end = start + 1;
while end < differences.len() && differences[end].at == differences[end - 1].at + 1 {
end += 1;
}
let run = end - start;
let out = differences[start..end]
.iter()
.filter(|difference| difference.ours.is_some())
.count();
let added = differences[start..end]
.iter()
.filter(|difference| difference.theirs.is_some())
.count();
for difference in &mut differences[start..end] {
difference.run = run;
difference.run_ours = out;
difference.run_theirs = added;
}
start = end;
}
}
const ANCHOR_WIDTHS: [usize; 4] = [24, 12, 6, 3];
fn anchored_edit_script(
ours: &[StreamToken],
theirs: &[StreamToken],
width_index: usize,
) -> (Vec<(usize, Option<usize>, Option<usize>)>, bool) {
if ours.len().saturating_mul(theirs.len()) <= MAX_DP_CELLS || width_index >= ANCHOR_WIDTHS.len()
{
return shortest_edit_script(ours, theirs);
}
let width = ANCHOR_WIDTHS[width_index];
let anchors = unique_anchors(ours, theirs, width);
if anchors.is_empty() {
return anchored_edit_script(ours, theirs, width_index + 1);
}
let mut edits = Vec::new();
let mut truncated = false;
let (mut our_cursor, mut their_cursor) = (0usize, 0usize);
let mut gap = |our_from: usize, our_to: usize, their_from: usize, their_to: usize| {
let (found, cut) = anchored_edit_script(
&ours[our_from..our_to],
&theirs[their_from..their_to],
width_index + 1,
);
truncated |= cut;
for (at, our_index, their_index) in found {
edits.push((
at + our_from,
our_index.map(|index| index + our_from),
their_index.map(|index| index + their_from),
));
}
};
for (our_at, their_at) in anchors {
if our_at < our_cursor || their_at < their_cursor {
continue;
}
gap(our_cursor, our_at, their_cursor, their_at);
our_cursor = our_at + width;
their_cursor = their_at + width;
while our_cursor < ours.len()
&& their_cursor < theirs.len()
&& ours[our_cursor].spelling == theirs[their_cursor].spelling
{
our_cursor += 1;
their_cursor += 1;
}
}
gap(our_cursor, ours.len(), their_cursor, theirs.len());
(edits, truncated)
}
fn unique_anchors(
ours: &[StreamToken],
theirs: &[StreamToken],
width: usize,
) -> Vec<(usize, usize)> {
use std::collections::HashMap;
if ours.len() < width || theirs.len() < width {
return Vec::new();
}
let windows = |tokens: &[StreamToken]| -> HashMap<u64, Option<usize>> {
let mut seen: HashMap<u64, Option<usize>> = HashMap::new();
for (start, window) in tokens.windows(width).enumerate() {
seen.entry(hash_window(window))
.and_modify(|entry| *entry = None)
.or_insert(Some(start));
}
seen
};
let theirs_windows = windows(theirs);
let ours_windows = windows(ours);
let mut pairs: Vec<(usize, usize)> = ours_windows
.iter()
.filter_map(|(hash, ours_at)| {
let (ours_at, theirs_at) = ((*ours_at)?, (*theirs_windows.get(hash)?)?);
let same = ours[ours_at..ours_at + width]
.iter()
.zip(&theirs[theirs_at..theirs_at + width])
.all(|(one, other)| one.spelling == other.spelling);
same.then_some((ours_at, theirs_at))
})
.collect();
pairs.sort_unstable();
let mut tails: Vec<usize> = Vec::new();
let mut previous: Vec<Option<usize>> = vec![None; pairs.len()];
for index in 0..pairs.len() {
let theirs_at = pairs[index].1;
let slot = tails.partition_point(|&tail| pairs[tail].1 < theirs_at);
previous[index] = slot.checked_sub(1).map(|before| tails[before]);
if slot == tails.len() {
tails.push(index);
} else {
tails[slot] = index;
}
}
let mut chain = Vec::with_capacity(tails.len());
let mut at = tails.last().copied();
while let Some(index) = at {
chain.push(pairs[index]);
at = previous[index];
}
chain.reverse();
chain
}
fn hash_window(window: &[StreamToken]) -> u64 {
use std::hash::{Hash, Hasher};
let mut hasher = std::collections::hash_map::DefaultHasher::new();
for token in window {
token.spelling.hash(&mut hasher);
}
hasher.finish()
}
const MAX_DP_CELLS: usize = 4_000_000;
fn shortest_edit_script(
ours: &[StreamToken],
theirs: &[StreamToken],
) -> (Vec<(usize, Option<usize>, Option<usize>)>, bool) {
let (n, m) = (ours.len(), theirs.len());
if n == 0 && m == 0 {
return (Vec::new(), false);
}
if n == 0 {
return ((0..m).map(|at| (at, None, Some(at))).collect(), false);
}
if m == 0 {
return ((0..n).map(|at| (at, Some(at), None)).collect(), false);
}
if n.saturating_mul(m) > MAX_DP_CELLS {
let mut edits = Vec::with_capacity(n + m);
for at in 0..n {
edits.push((at, Some(at), None));
}
for at in 0..m {
edits.push((n + at, None, Some(at)));
}
return (edits, true);
}
let width = m + 1;
let mut lengths = vec![0u32; (n + 1) * width];
let cell = |row: usize, column: usize| row * width + column;
for i in (0..n).rev() {
for j in (0..m).rev() {
lengths[cell(i, j)] = if ours[i].spelling == theirs[j].spelling {
lengths[cell(i + 1, j + 1)] + 1
} else {
lengths[cell(i + 1, j)].max(lengths[cell(i, j + 1)])
};
}
}
let mut edits: Vec<(usize, Option<usize>, Option<usize>)> = Vec::new();
let mut queue: Vec<(bool, bool)> = Vec::new();
let (mut i, mut j) = (0usize, 0usize);
let mut matched = 0usize;
while i < n || j < m {
let same = i < n && j < m && ours[i].spelling == theirs[j].spelling;
if same {
flush(&mut edits, &mut queue, i, matched, i, j);
i += 1;
j += 1;
matched += 1;
continue;
}
let delete_ours = if i >= n {
false
} else if j >= m {
true
} else {
lengths[cell(i + 1, j)] >= lengths[cell(i, j + 1)]
};
if delete_ours {
queue.push((true, false));
i += 1;
} else {
queue.push((false, true));
j += 1;
}
}
flush(&mut edits, &mut queue, i, matched, i, j);
(edits, false)
}
fn flush(
edits: &mut Vec<(usize, Option<usize>, Option<usize>)>,
queue: &mut Vec<(bool, bool)>,
_cursor: usize,
_matched: usize,
our_run: usize,
their_run: usize,
) {
let deleted = queue.iter().filter(|(deleted, _)| *deleted).count();
let inserted = queue.iter().filter(|(_, inserted)| *inserted).count();
let our_first = our_run - deleted;
let their_first = their_run - inserted;
let from = our_first;
if deleted > 0 && inserted > 0 {
edits.push((from, Some(our_first), Some(their_first)));
for offset in 1..deleted {
edits.push((from + offset, Some(our_first + offset), None));
}
for offset in 1..inserted {
edits.push((from + offset, None, Some(their_first + offset)));
}
} else if deleted > 0 {
for offset in 0..deleted {
edits.push((from + offset, Some(our_first + offset), None));
}
} else {
for offset in 0..inserted {
edits.push((from + offset, None, Some(their_first + offset)));
}
}
queue.clear();
}
pub fn without_pragmas(tokens: &[StreamToken]) -> Vec<StreamToken> {
let mut kept = Vec::with_capacity(tokens.len());
let mut index = 0usize;
let same_line =
|one: &StreamToken, other: &StreamToken| one.file == other.file && one.line == other.line;
while index < tokens.len() {
let token = &tokens[index];
if &*token.spelling == "#"
&& tokens
.get(index + 1)
.is_some_and(|next| &*next.spelling == "pragma" && same_line(token, next))
{
index += 2;
while index < tokens.len() && same_line(token, &tokens[index]) {
index += 1;
}
continue;
}
if matches!(&*token.spelling, "_Pragma" | "__pragma")
&& tokens
.get(index + 1)
.is_some_and(|next| &*next.spelling == "(")
{
let mut depth = 0usize;
let mut end = index + 1;
while end < tokens.len() {
match &*tokens[end].spelling {
"(" => depth += 1,
")" => {
depth -= 1;
if depth == 0 {
break;
}
}
_ => {}
}
end += 1;
}
index = end + 1;
continue;
}
kept.push(token.clone());
index += 1;
}
kept
}
pub fn tokenize_preprocessed(text: &str) -> Vec<StreamToken> {
let (tokens, _) = cpp_parser::lex(text, &cpp_parser::LexerConfig::default());
let mut out: Vec<StreamToken> = Vec::with_capacity(tokens.len());
let mut file: Option<Arc<Path>> = None;
let mut marked_line: Option<u32> = None;
let mut newlines_since = 0u32;
let mut index = 0usize;
while index < tokens.len() {
let token = &tokens[index];
let start = token.range.start_offset;
if token.kind == cpp_parser::CppTokenKind::Newline {
newlines_since += 1;
index += 1;
continue;
}
let line_begin = text[..start].rfind('\n').map_or(0, |at| at + 1);
let is_first_on_its_line = text[line_begin..start].trim().is_empty();
if is_first_on_its_line
&& token.kind == cpp_parser::CppTokenKind::Hash
&& let Some(marker) = read_a_line_marker(text, &tokens, index)
{
if let Some(named) = marker.file {
file = Some(named);
}
marked_line = Some(marker.line);
newlines_since = 0;
index = tokens
.partition_point(|token| token.range.start_offset < marker.end)
.max(index + 1);
continue;
}
if !cpp_parser::is_trivia(token.kind) {
out.push(StreamToken {
spelling: text[start..token.range.end_offset()].into(),
file: file.clone(),
line: marked_line.map(|line| line + newlines_since.saturating_sub(1)),
});
}
index += 1;
}
out
}
struct LineMarker {
file: Option<Arc<Path>>,
line: u32,
end: usize,
}
fn read_a_line_marker(
text: &str,
tokens: &[cpp_parser::CppTokenData],
index: usize,
) -> Option<LineMarker> {
fn next_significant(
text: &str,
tokens: &[cpp_parser::CppTokenData],
from: usize,
) -> Option<usize> {
(from..tokens.len())
.find(|at| !cpp_parser::is_trivia(tokens[*at].kind))
.filter(|at| !text.is_empty() && *at < tokens.len())
}
let spelling_at = |at: usize| {
tokens
.get(at)
.map(|token| &text[token.range.start_offset..token.range.end_offset()])
};
let significance = |from: usize| next_significant(text, tokens, from);
let mut at = significance(index + 1)?;
if spelling_at(at) == Some("line") {
at = significance(at + 1)?;
}
let number: u32 = spelling_at(at)?
.trim_end_matches(['u', 'U', 'l', 'L'])
.parse()
.ok()?;
let mut file = None;
if let Some(path_at) = significance(at + 1)
&& let Some(named) = spelling_at(path_at).and_then(unquote)
{
file = Some(shared(Path::new(&named)));
}
let line_begin = text[..tokens[index].range.start_offset]
.rfind('\n')
.map_or(0, |at| at + 1);
let end = text[line_begin..]
.find('\n')
.map_or(text.len(), |at| line_begin + at);
Some(LineMarker {
file,
line: number,
end,
})
}
fn unquote(spelling: &str) -> Option<String> {
let body = spelling.strip_prefix('"')?.strip_suffix('"')?;
let mut out = String::with_capacity(body.len());
let mut characters = body.chars();
while let Some(character) = characters.next() {
if character != '\\' {
out.push(character);
continue;
}
match characters.next()? {
'\\' => out.push('\\'),
'"' => out.push('"'),
other => {
out.push('\\');
out.push(other);
}
}
}
Some(out)
}
pub fn files_of(stream: &[StreamToken]) -> std::collections::HashSet<&Path> {
stream
.iter()
.filter_map(|token| token.file.as_deref())
.collect()
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Report {
pub matched: usize,
pub ours: usize,
pub theirs: usize,
pub by_reason: Vec<(Reason, usize)>,
pub differences: Vec<Difference>,
pub truncated: bool,
}
const REPORTED_DIFFERENCES: usize = 40;
impl Report {
pub fn of(ours: &[StreamToken], theirs: &[StreamToken]) -> Report {
let alignment = align(ours, theirs);
let our_files = files_of(ours);
Report {
matched: alignment.matched,
ours: ours.len(),
theirs: theirs.len(),
by_reason: alignment.by_reason(&our_files),
differences: alignment
.differences
.iter()
.take(REPORTED_DIFFERENCES)
.cloned()
.collect(),
truncated: alignment.truncated,
}
}
pub fn agrees(&self) -> bool {
self.by_reason.is_empty() && !self.truncated
}
pub fn headers_we_never_entered(
&self,
our_files: &std::collections::HashSet<&Path>,
) -> Vec<&Path> {
let mut missing: Vec<&Path> = self
.differences
.iter()
.filter(|difference| difference.reason(our_files) == Reason::MissingHeader)
.filter_map(|difference| difference.theirs.as_ref()?.file.as_deref())
.collect();
missing.sort_unstable();
missing.dedup();
missing
}
pub fn render(&self) -> String {
let mut out = String::new();
out.push_str(&format!(
"ours {} tokens | theirs {} tokens | matched {} | differences {}{}\n",
self.ours,
self.theirs,
self.matched,
self.by_reason
.iter()
.map(|(_, count)| *count)
.sum::<usize>(),
if self.truncated {
" (the comparison stopped early, so this is a lower bound)"
} else {
""
}
));
if self.by_reason.is_empty() {
out.push_str(" the two streams agree\n");
return out;
}
out.push_str("by mechanism:\n");
for (reason, count) in &self.by_reason {
out.push_str(&format!(" {count:>7} {reason:?}\n"));
out.push_str(&format!(" {}\n", reason.advice()));
}
out.push_str("first differences:\n");
for difference in &self.differences {
let ours = difference.ours.as_ref().map_or_else(
|| "-".to_string(),
|token| format!("{} @ {}", token.spelling, token.origin()),
);
let theirs = difference.theirs.as_ref().map_or_else(
|| "-".to_string(),
|token| format!("{} @ {}", token.spelling, token.origin()),
);
out.push_str(&format!(
" #{} ours: {ours} theirs: {theirs}\n",
difference.at
));
}
if !self.truncated {
let total: usize = self.by_reason.iter().map(|(_, count)| *count).sum();
if total > self.differences.len() {
out.push_str(&format!(" —{} more\n", total - self.differences.len()));
}
}
out
}
}
pub fn shared(path: &Path) -> Arc<Path> {
Arc::from(normalized(path)) as Arc<Path>
}
pub fn normalized(path: &Path) -> PathBuf {
PathBuf::from(crate::file::paths::normalize_path(path, cfg!(windows)))
}
pub trait UnitTexts {
fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)>;
}
#[derive(Debug, Clone, Copy, Default)]
pub struct DiskTexts;
impl UnitTexts for DiskTexts {
fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)> {
let text = std::fs::read_to_string(path).ok()?;
let lines = cpp_parser::LineIndex::parse(&text);
Some((text, lines))
}
}
impl UnitTexts for std::collections::HashMap<PathBuf, String> {
fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)> {
let text = self.get(path)?;
Some((text.clone(), cpp_parser::LineIndex::parse(text)))
}
}
pub fn unit_tokens(unit: &crate::RenderedUnit, texts: &dyn UnitTexts) -> Vec<StreamToken> {
let held: Vec<Option<HeldFile>> = unit
.files
.iter()
.map(|path| {
texts.text_of(path).map(|(text, lines)| HeldFile {
lines,
text,
path: shared(path),
})
})
.collect();
unit.spans
.iter()
.map(|span| {
let file = held.get(span.file as usize).and_then(Option::as_ref);
StreamToken {
spelling: unit.text[span.cooked.start_offset..span.cooked.end_offset()].into(),
file: file.map(|file| Arc::clone(&file.path)),
line: file.and_then(|file| {
file.lines
.position_of(span.written.start_offset, &file.text)
.map(|(line, _)| line as u32 + 1)
}),
}
})
.collect()
}
struct HeldFile {
lines: cpp_parser::LineIndex,
text: String,
path: Arc<Path>,
}
#[cfg(test)]
mod tests {
use super::*;
use cpp_parser::SourceRange;
fn as_recorded(path: &str) -> String {
if cfg!(windows) {
path.to_lowercase()
} else {
path.to_string()
}
}
fn plain(spellings: &[&str]) -> Vec<StreamToken> {
spellings
.iter()
.map(|spelling| StreamToken::new(*spelling, None, None))
.collect()
}
fn spelled(stream: &[StreamToken]) -> Vec<&str> {
stream.iter().map(|token| &*token.spelling).collect()
}
fn reason_at(alignment: &Alignment, at: usize) -> Reason {
alignment
.differences
.iter()
.find(|difference| difference.at >= at)
.expect("there is a difference at or after this position")
.reason(&Default::default())
}
fn movements(alignment: &Alignment) -> usize {
let mut count = 0usize;
let mut previous: Option<usize> = None;
for difference in &alignment.differences {
if previous != Some(difference.at.wrapping_sub(1)) {
count += 1;
}
previous = Some(difference.at);
}
count
}
#[test]
fn two_spellings_of_one_path_are_one_file() {
let ours = vec![StreamToken::new(
"x",
Some(shared(Path::new("/p//a.h"))),
Some(1),
)];
let theirs = vec![StreamToken::new(
"x",
Some(shared(Path::new("/p/a.h"))),
Some(1),
)];
let our_files = files_of(&ours);
assert_eq!(
our_files.len(),
1,
"the two spellings collapse to one path: {our_files:?}"
);
assert!(
our_files.contains(Path::new("/p/a.h")),
"and it is the normalized spelling: {our_files:?}"
);
assert!(
align(&ours, &theirs).agrees(),
"the same file on both sides"
);
}
#[test]
fn two_streams_that_agree_have_no_differences() {
let ours = plain(&["int", "main", "(", ")", "{", "}"]);
let theirs = plain(&["int", "main", "(", ")", "{", "}"]);
let alignment = align(&ours, &theirs);
assert!(alignment.agrees(), "{alignment:?}");
assert_eq!(alignment.matched, 6, "every token is counted as agreed");
assert!(alignment.differences.is_empty());
}
#[test]
fn a_name_that_survived_where_the_compiler_expanded_it_is_one_difference() {
let ours = plain(&["int", "x", "=", "VALUE"]);
let theirs = plain(&["int", "x", "=", "42"]);
let alignment = align(&ours, &theirs);
assert_eq!(alignment.matched, 3, "everything but the last token agreed");
assert_eq!(
alignment.differences.len(),
1,
"{:?}",
alignment.differences
);
let difference = &alignment.differences[0];
assert_eq!(
difference.ours.as_ref().map(|it| &*it.spelling),
Some("VALUE")
);
assert_eq!(
difference.theirs.as_ref().map(|it| &*it.spelling),
Some("42")
);
assert_eq!(
difference.at, 3,
"and it is reported where it is in the stream"
);
assert!(difference.is_isolated(), "{difference:?}");
assert_eq!((difference.run_ours, difference.run_theirs), (1, 1));
assert_eq!(
difference.reason(&Default::default()),
Reason::ConditionDisagreement,
"a name against a number: this fixture is exactly that shape"
);
}
#[test]
fn a_stream_compared_against_itself_is_all_matches() {
let stream = plain(&["#", "define", "FLAG", "1", "int", "n", ";"]);
let alignment = align(&stream, &stream);
assert!(alignment.agrees(), "{alignment:?}");
assert_eq!(alignment.matched, 7);
assert!(alignment.differences.is_empty());
}
#[test]
fn a_region_present_on_one_side_only_is_counted_as_one_movement() {
let ours = plain(&["int", "a", ";", "int", "b", ";", "int", "c", ";"]);
let theirs = plain(&["int", "a", ";"]);
let alignment = align(&ours, &theirs);
assert_eq!(
alignment.differences.len(),
6,
"six edits: {:?}",
alignment.differences
);
assert_eq!(movements(&alignment), 1, "and one movement");
assert_eq!(reason_at(&alignment, 3), Reason::BranchDisagreement);
}
#[test]
fn the_differences_come_out_in_stream_order() {
let ours = plain(&["a", "b", "c", "d"]);
let alignment = align(&ours, &[]);
let positions: Vec<usize> = alignment
.differences
.iter()
.map(|difference| difference.at)
.collect();
assert_eq!(positions, vec![0, 1, 2, 3], "{:?}", alignment.differences);
assert_eq!(
movements(&alignment),
1,
"one region left, not four movements"
);
}
#[test]
fn one_macro_that_expands_to_several_tokens_is_one_movement() {
let ours = plain(&["int", "n", "=", "SIZE", ";"]);
let theirs = plain(&["int", "n", "=", "8", "*", "1024", ";"]);
let alignment = align(&ours, &theirs);
assert_eq!(
movements(&alignment),
1,
"one macro moved: {:#?}",
alignment.differences
);
assert!(
alignment
.differences
.iter()
.all(|difference| difference.run > 1),
"and every edit of it knows it is part of a run: {:?}",
alignment.differences
);
assert_eq!(
reason_at(&alignment, 3),
Reason::ExpansionDisagreement,
"one token out, three in: a replacement list, not a name that survived"
);
}
#[test]
fn a_name_alone_in_a_one_sided_run_is_reported_as_a_region() {
let ours = plain(&["void", "f", "(", ")", "{", "ONLY_HERE", "}", ";"]);
let theirs = plain(&["void", "f", "(", ")", "{", "}", ";"]);
let alignment = align(&ours, &theirs);
assert_eq!(movements(&alignment), 1);
assert_eq!(
reason_at(&alignment, 5),
Reason::UnexpandedMacro,
"one name on our side and nothing where theirs is: {:?}",
alignment.differences
);
}
#[test]
fn a_branch_taken_on_one_side_only_is_a_run_of_one_sided_differences() {
let ours = plain(&["int", "a", ";", "int", "b", ";"]);
let theirs = plain(&["int", "a", ";"]);
let alignment = align(&ours, &theirs);
assert_eq!(alignment.matched, 3);
assert_eq!(
alignment.differences.len(),
3,
"{:?}",
alignment.differences
);
assert!(
alignment
.differences
.iter()
.all(|difference| difference.theirs.is_none()),
"every difference is ours alone: {:?}",
alignment.differences
);
}
#[test]
fn a_substitution_is_one_difference_with_both_halves() {
let alignment = align(&plain(&["a", "OLD", "b"]), &plain(&["a", "NEW", "b"]));
assert_eq!(
alignment.differences.len(),
1,
"{:?}",
alignment.differences
);
assert!(
alignment.differences[0].ours.is_some() && alignment.differences[0].theirs.is_some()
);
}
#[test]
fn a_name_against_a_number_is_classified_as_a_condition_disagreement() {
let ours = plain(&["int", "n", "=", "WIDTH"]);
let theirs = plain(&["int", "n", "=", "19"]);
let alignment = align(&ours, &theirs);
assert_eq!(movements(&alignment), 1, "{:?}", alignment.differences);
assert_eq!(reason_at(&alignment, 3), Reason::ConditionDisagreement);
}
#[test]
fn a_token_from_a_file_we_never_read_is_a_missing_header() {
let ours = plain(&["int", "x", ";"]);
let theirs = vec![
StreamToken::new("int", Some(shared(Path::new("/p/a.cpp"))), None),
StreamToken::new("helper", Some(shared(Path::new("/missing/header.h"))), None),
StreamToken::new(";", Some(shared(Path::new("/p/a.cpp"))), None),
];
let our_files = files_of(&ours);
let reason = align(&ours, &theirs).differences[0].reason(&our_files);
assert_eq!(reason, Reason::MissingHeader);
}
#[test]
fn a_name_against_a_name_is_not_a_condition_disagreement() {
let ours = plain(&["int", "n", "=", "WIDTH"]);
let theirs = plain(&["int", "n", "=", "HEIGHT"]);
let alignment = align(&ours, &theirs);
assert_eq!(movements(&alignment), 1);
assert_eq!(
reason_at(&alignment, 3),
Reason::Unknown,
"the diff cannot say which mechanism moved two names: {:?}",
alignment.differences
);
}
#[test]
fn the_line_markers_of_a_preprocessed_file_are_read_for_position() {
let output = "# 1 \"C:/src/main.cpp\"\nint main ( ) { }\n# 1 \"C:/inc/xstring\" 1 3\nnamespace std {\n}\n# 7 \"C:/src/main.cpp\" 2\nreturn 0 ;\n";
let tokens = tokenize_preprocessed(output);
assert_eq!(
spelled(&tokens),
[
"int",
"main",
"(",
")",
"{",
"}",
"namespace",
"std",
"{",
"}",
"return",
"0",
";"
],
"the markers are not tokens: {tokens:?}"
);
assert_eq!(tokens[0].origin(), as_recorded("C:/src/main.cpp:1"));
assert_eq!(
tokens[6].origin(),
as_recorded("C:/inc/xstring:1"),
"the header's own tokens carry the header's name and line: {tokens:?}"
);
assert_eq!(
tokens[11].origin(),
as_recorded("C:/src/main.cpp:7"),
"and the file comes back when the marker says so"
);
}
#[test]
fn msvcs_line_marker_spelling_is_read_too() {
let output = "#line 12 \"C:\\\\src\\\\main.cpp\"\nint x ;\n";
let tokens = tokenize_preprocessed(output);
assert_eq!(spelled(&tokens), ["int", "x", ";"]);
assert_eq!(
tokens[0].origin(),
as_recorded("C:/src/main.cpp:12"),
"{tokens:?}"
);
}
#[test]
fn a_windows_path_that_is_not_a_c_string_keeps_its_backslashes() {
let output = "# 1 \"C:\\work\\src\\main.cpp\"\nint x ;\n";
let tokens = tokenize_preprocessed(output);
assert_eq!(
tokens[0].origin(),
as_recorded("C:/work/src/main.cpp:1"),
"the path survives with its separators, in the spelling comparisons are made in: {tokens:?}"
);
}
#[test]
fn a_pragma_line_survives_as_tokens() {
let output = "#pragma once\nint x ;\n";
let tokens = tokenize_preprocessed(output);
assert_eq!(spelled(&tokens), ["#", "pragma", "once", "int", "x", ";"]);
}
#[test]
fn comments_and_layout_are_not_part_of_the_comparison() {
let tokens = tokenize_preprocessed("int /* why */ x ;\n// and\nint y ;");
assert_eq!(spelled(&tokens), ["int", "x", ";", "int", "y", ";"]);
}
#[test]
fn a_comparison_that_ran_out_of_budget_says_so() {
let ours: Vec<StreamToken> = (0..MAX_EDIT_DISTANCE + 200)
.map(|at| StreamToken::new(format!("left{at}"), None, None))
.collect();
let theirs: Vec<StreamToken> = (0..MAX_EDIT_DISTANCE + 200)
.map(|at| StreamToken::new(format!("right{at}"), None, None))
.collect();
let alignment = align(&ours, &theirs);
assert!(
alignment.truncated,
"an unbounded diff must report that it stopped"
);
assert!(
!alignment.agrees(),
"and must not be mistaken for agreement"
);
}
#[test]
fn the_report_counts_differences_by_mechanism() {
let ours = plain(&[
"int", "n", "=", "WIDTH", ";", ";", "EXTRA", ";", ";", "A", "B", ]);
let theirs = plain(&[
"int", "n", "=", "19", ";", ";", ";", ";", "C", ]);
let report = Report::of(&ours, &theirs);
assert_eq!((report.ours, report.theirs), (11, 9));
assert!(!report.agrees());
assert!(!report.truncated, "a handful of edits: {report:?}");
let mut counted = report.by_reason.clone();
counted.sort_by_key(|(reason, _)| format!("{reason:?}"));
assert_eq!(
counted,
vec![
(Reason::ConditionDisagreement, 1),
(Reason::ExpansionDisagreement, 2),
(Reason::UnexpandedMacro, 1),
],
"one movement each, counted where it belongs: {report:?}"
);
assert!(
report.render().contains("by mechanism"),
"{}",
report.render()
);
}
#[test]
fn a_report_of_two_agreeing_streams_says_so() {
let report = Report::of(&plain(&["a", "b"]), &plain(&["a", "b"]));
assert!(report.agrees());
assert!(report.render().contains("agree"), "{}", report.render());
}
#[test]
fn our_tokens_take_their_line_from_the_file_not_from_the_rendering() {
let file = "/p/a.h";
let text = "\nint a;\nint b;\nint c;\nint d;\n";
let mut unit = crate::RenderedUnit {
files: vec![PathBuf::from(file)],
file_lengths: vec![text.len()],
..crate::RenderedUnit::default()
};
unit.push("int", 0, SourceRange::new(1, 3));
unit.push("a", 0, SourceRange::new(5, 1));
unit.push("int", 0, SourceRange::new(8, 3));
unit.push("c", 0, SourceRange::new(19, 1));
let texts: std::collections::HashMap<PathBuf, String> =
[(PathBuf::from(file), text.to_string())]
.into_iter()
.collect();
let tokens = unit_tokens(&unit, &texts);
let placed: Vec<(&str, u32)> = tokens
.iter()
.map(|token| {
(
&*token.spelling,
token.line.expect("the file's text was given"),
)
})
.collect();
assert_eq!(
placed,
vec![("int", 2), ("a", 2), ("int", 3), ("c", 4)],
"each token's line is where the file wrote it: {tokens:?}"
);
assert_eq!(
tokens[0].file.as_deref(),
Some(Path::new(file)),
"and its file is the one it stands in"
);
}
#[test]
fn a_file_nobody_has_the_text_of_yields_tokens_with_no_position() {
let mut unit = crate::RenderedUnit {
files: vec![PathBuf::from("/p/a.h")],
file_lengths: vec![0],
..crate::RenderedUnit::default()
};
unit.push("x", 0, SourceRange::new(0, 1));
let tokens = unit_tokens(&unit, &std::collections::HashMap::<PathBuf, String>::new());
assert_eq!(tokens.len(), 1);
assert!(tokens[0].file.is_none(), "{tokens:?}");
assert!(tokens[0].line.is_none(), "{tokens:?}");
assert_eq!(
tokens[0].origin(),
"?",
"and the report says so rather than guessing"
);
}
}