cpp_code_analysis/align.rs
1//! **Alignment against a real compiler**: run the true preprocessor over the same file, put the two token streams
2//! side by side, and report where they differ — by kind, not as an opinion.
3//!
4//! # Why this module is the most valuable one in the crate
5//!
6//! Every other module here answers a question about a reading, and the answer is only as good as the reading.
7//! "Did our preprocessor choose the same branch", "did it expand that macro the way a compiler does", "did it find
8//! that header" — those are not questions an argument settles. The plan's §5.0 puts the method this way:
9//!
10//! ```text
11//! cl.exe /E /d1PP main.cpp → clang -E -dM main.cpp
12//! ↓
13//! 它展开出的 token 序列 / 宏表 / 存活的分支
14//! ↓
15//! 和 cook 出来的 RenderedUnit 比:token 数、文件边界、每个 #if 分支的取舍
16//!
17//! So this module does one thing: it makes **the compiler the oracle**. Two streams of tokens, one from
18//! [`crate::RenderedUnit`] and one from a real `-E`, and a list of the places they disagree.
19//!
20//! # What is compared, and what deliberately is not
21//!
22//! Compared: the **spelling of every token, in order, with where it came from** —file and line. That is the plan's
23//! list (token count, file boundaries, which branch of each `#if` was taken), and all three fall out of it: a branch
24//! chosen differently shows up as a run of tokens present on one side and not the other, and a header resolved to
25//! the wrong file shows up as the same tokens carrying different origins.
26//!
27//! Not compared, and the list matters as much as the other one:
28//!
29//! * **Whitespace, and therefore exact positions inside a line.** A rendering spells tokens separated by single
30//! spaces (see [`crate::preprocess::cooked::CookedStream::render`]); a compiler keeps the file's own layout. Line
31//! numbers are compared because the line markers survive `-E`, and comparing them is what makes "the branch was
32//! taken from another file" visible.
33//! * **The macro table itself**, for now. `-dM` prints it and `Toolchain::builtin_macros` already reads it; putting
34//! the two tables side by side is the next step and it is a different comparison (a set of definitions, not a
35//! sequence of tokens). This module is the sequence.
36//! * **Layout of the marker syntax.** MSVC and GCC spell their line markers differently and some of them quote the
37//! path; both are read, and both are treated as *not tokens* —see [`tokenize_preprocessed`].
38//!
39//! # What "different" is allowed to mean
40//!
41//! A diff is a list of edits, and an edit is not a diagnosis. Turning it into one is [`Difference::reason`], whose
42//! whole job is to say which **mechanism** produced a difference rather than which tokens are on either side —because
43//! the mechanisms are the milestones. `BranchDisagreement` is a condition-evaluation gap (§3.2 item 1),
44//! `MissingHeader` is the include resolver, `ExpansionDisagreement` is the expander. A reading of this module that
45//! ends in "17 differences" is useless; one that ends in "17 differences, 14 of them one unexpanded macro" is a work
46//! item.
47//!
48//! # An edit is finer than a mechanism, and that is the trap
49//!
50//! The first version of this module read one edit at a time, and got the most common case wrong. `#define SIZE 1024`
51//! that we fail to expand is **three** edits — our `SIZE` substituted, their `1024` and the `*` around it inserted —//! and read one at a time they are `UnexpandedMacro` and `MissingExpansion`: two work items, and neither is what
52//! happened. One macro is what happened.
53//!
54//! So a [`Difference`] carries the shape of the **contiguous run** it belongs to — how many tokens went out, how many
55//! came in — and the classification reads that. A run is what a reader of the two streams would call one movement of
56//! tokens, and the report's counts are counts of movements. `one_macro_that_expands_to_several_tokens_is_one_movement`
57//! is the test that pins it.
58//!
59//! # Why the two entry points are pure functions
60//!
61//! [`tokenize_preprocessed`] takes text and returns tokens; [`align`] takes two token lists and returns differences.
62//! Neither runs a process, reads a file or knows what a compiler is. That is what makes the whole thing testable
63//! against **recorded** `-E` output —the tests here do exactly that —on a machine with no compiler installed, and
64//! it is what keeps the one part that does touch the world (`examples/align_preprocessor.rs`) to a page.
65
66use std::path::{Path, PathBuf};
67use std::sync::Arc;
68
69/// One token, as the comparison sees it: what it spells, and where it came from.
70///
71/// The file and the line are `Option` because each of them is genuinely unknown in one of the two streams: our own
72/// rendering knows a token's file for every token (that is what [`crate::UnitSpan::file`] is) but not its line until
73/// the file is read back, and a compiler's `-E` output states both for every token —except when it prints none,
74/// which it does for a token it synthesised (a `##` paste has no file of its own).
75///
76/// **The path is shared** ([`Arc`]) because it is the same `PathBuf` for every token of a 40 000-token header, and a
77/// comparison of a standard library's closure holds a few million of these. Cloning a path per token is the kind of
78/// cost this crate has measured before and does not need to measure again.
79#[derive(Debug, Clone, PartialEq, Eq)]
80pub struct StreamToken {
81 /// The token's spelling, exactly as it would be written.
82 pub spelling: Box<str>,
83 /// The file the token stands in —a path as the *producing* side spells it.
84 pub file: Option<Arc<Path>>,
85 /// The 1-based line in [`StreamToken::file`].
86 pub line: Option<u32>,
87}
88
89impl StreamToken {
90 pub fn new(spelling: impl Into<Box<str>>, file: Option<Arc<Path>>, line: Option<u32>) -> Self {
91 StreamToken {
92 spelling: spelling.into(),
93 file,
94 line,
95 }
96 }
97
98 /// Where this token is, as `path:line`, for a report. `?` for a part nobody stated.
99 pub fn origin(&self) -> String {
100 match (&self.file, self.line) {
101 (Some(path), Some(line)) => format!("{}:{line}", path.display()),
102 (Some(path), None) => path.display().to_string(),
103 (None, Some(line)) => format!("line {line}"),
104 (None, None) => "?".to_string(),
105 }
106 }
107}
108
109/// Which side a stream came from —and it is not decoration: a difference with no *ours* is the compiler having
110/// tokens we do not have at all (a branch we did not take, a header we did not find), and one with no *theirs* is the
111/// other direction. [`Difference`] keeps both, but a report that prints them has to say which is which.
112#[derive(Debug, Clone, Copy, PartialEq, Eq)]
113pub enum Side {
114 /// The stream this crate produced —[`crate::RenderedUnit`], rendered and tokenized.
115 Ours,
116 /// The stream a real preprocessor produced.
117 Theirs,
118}
119
120/// **One edit of the shortest script that turns our stream into the compiler's.**
121///
122/// `ours` or `theirs` may be absent, and the absent half is the information: a difference with no `theirs` is a token
123/// we have and the compiler does not.
124///
125/// # An edit is finer than a mechanism
126///
127/// The first version of this module classified one edit at a time, and the mistake that came out of it is worth
128/// recording. `#define SIZE 1024` that we expand and the compiler does not is *three* edits — our `SIZE` substituted,
129/// their `1024` inserted —and one at a time they say `UnexpandedMacro` and `MissingExpansion`: two different work
130/// items, and neither is what happened. One macro is what happened.
131///
132/// So a `Difference` carries the run it belongs to ([`Difference::run`], [`Difference::run_ours`],
133/// [`Difference::run_theirs`]), which is the same shape a reader of the streams would see: **a contiguous movement of
134/// tokens**. [`Difference::reason`] reads that shape, and a report is a list of movements rather than of edits.
135#[derive(Debug, Clone, PartialEq, Eq)]
136pub struct Difference {
137 /// Where in the comparison this is —the index in the aligned sequence, for a report that says "the 12th".
138 pub at: usize,
139 /// The token we have, when the edit is ours to explain.
140 pub ours: Option<StreamToken>,
141 /// The token the compiler has.
142 pub theirs: Option<StreamToken>,
143 /// **How many edits this one is part of** —the size of the contiguous run it belongs to, `1` for an isolated
144 /// edit. Every difference in a run carries the whole run's size, because the run is what a mechanism acts on.
145 pub run: usize,
146 /// How many tokens the run takes out of **our** stream, or `0` when the run is the compiler having something we
147 /// do not.
148 ///
149 /// The two counts are what separate the two mechanisms that look identical one edit at a time, and neither is
150 /// derivable from [`Difference::run`]: a run of three edits can be *one* macro that expands to three tokens (one
151 /// out, three in) or *three* names that survived (three out, none in), and those are different work items.
152 pub run_ours: usize,
153 /// How many tokens the run adds from **the compiler's** stream.
154 pub run_theirs: usize,
155}
156
157impl Difference {
158 /// The side this difference is *about*: ours when we have a token here, theirs otherwise.
159 ///
160 /// A difference always has at least one half, so this is total —and it is the side a report should quote,
161 /// because it is the side the fix is in.
162 pub fn side(&self) -> Side {
163 if self.ours.is_some() {
164 Side::Ours
165 } else {
166 Side::Theirs
167 }
168 }
169
170 /// Is this one edit, rather than part of a run? What a report quotes in full.
171 pub fn is_isolated(&self) -> bool {
172 self.run <= 1
173 }
174}
175
176/// **Why two streams differ at one place**, as a mechanism rather than a pair of tokens.
177///
178/// The list is the milestones, and that is the design: a report whose differences are classified is a work list, and
179/// one whose differences are not is a wall of text. Each variant names something that can be *fixed*, which is what
180/// makes this better than "these 300 tokens do not match".
181///
182/// Classification is from the shape of the pair and from what came before it. It is deliberately a **heuristic**, and
183/// [`Difference::reason`]'s doc says so: a wrong guess here costs a report that points at the wrong milestone, while
184/// refusing to guess costs a report nobody can use. What it must never do is claim a difference is benign.
185///
186/// `Ord` because a report groups by mechanism and a grouping has to be **stable between runs** —a `BTreeMap` over
187/// this is what makes two runs of the same comparison print the same lines in the same order, which is the property a
188/// recorded count per mechanism needs.
189#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
190pub enum Reason {
191 /// A name we have that the compiler does not: a macro that should have been expanded.
192 UnexpandedMacro,
193 /// A name the compiler has that we do not: its expansion came from a header we did not read.
194 MissingExpansion,
195 /// A numeric literal on one side where the other has a name —the classic fingerprint of `#if` disagreement:
196 /// one side replaced `FOO` with `1`, the other with `0` or nothing.
197 ConditionDisagreement,
198 /// **A region one side compiled and the other did not** —tokens present in one stream and absent from the other,
199 /// in a run.
200 ///
201 /// The variant that exists because a diff is finer than a mechanism. `#if _MSC_VER >= 1930` deciding differently
202 /// moves a whole branch: dozens of tokens present on one side only, which read one edit at a time are "a name we
203 /// have that they do not" (i.e. `UnexpandedMacro`) —the wrong work item for the right evidence.
204 ///
205 /// The plan's §3.2 item 1 is what this points at: *"内建宏表,来源优先? `compile_commands.json` ?`cl.exe` /
206 /// `clang` 探测"*. A run of these is what a missing predefined macro looks like from here.
207 BranchDisagreement,
208 /// **One name on one side and its replacement list on the other** —both streams have tokens here, and not the
209 /// same number of them.
210 ///
211 /// Distinct from [`Reason::UnexpandedMacro`], which is the same mechanism seen at its smallest: a body of one
212 /// token looks like a name that did not expand, and a body of ten looks like this. Both are the expander's work
213 /// item, and separating them says how big the gap is rather than only that there is one.
214 ExpansionDisagreement,
215 /// The compiler's stream carries an `#include` whose header we never read at all.
216 ///
217 /// The one variant that is *certain* rather than heuristic: `includes` is built from the compiler's own line
218 /// markers, so a path that appears there and nowhere in ours is a file this reading never had.
219 MissingHeader,
220 /// Neither side's shape says which mechanism; the pair is quoted and a reader decides.
221 Unknown,
222}
223
224impl Reason {
225 /// What to do about it —the plan's rule 3, that every uncertain answer has to say what it is uncertain about
226 /// *and* what that means for whoever reads it.
227 ///
228 /// `&self` rather than `self`: every variant is a unit, so this is a table lookup and there is nothing to move.
229 pub fn advice(&self) -> &'static str {
230 match self {
231 Reason::UnexpandedMacro => {
232 "a name survived into our stream: the expander had no body for it (see `Configuration`) \
233 or the invocation did not parse as a call"
234 }
235 Reason::MissingExpansion => {
236 "the compiler expanded something we never had: the file that defines it is not in our closure \
237 (an unresolved include, or a header we read as empty)"
238 }
239 Reason::ConditionDisagreement => {
240 "the two readings took different branches of an `#if`: a predefined macro is missing from our \
241 table, or one of them evaluated to the wrong value"
242 }
243 Reason::BranchDisagreement => {
244 "a whole region moved, not one token: an `#if` was decided the other way, so look for the \
245 predefined macro it asks about before looking at the parser"
246 }
247 Reason::ExpansionDisagreement => {
248 "one name on one side and its replacement list on the other: the expander had no body for it, or \
249 substituted differently —compare the two tables for the name quoted"
250 }
251 Reason::MissingHeader => {
252 "the compiler read a header this reading never entered: the include resolver could not find it"
253 }
254 Reason::Unknown => {
255 "the shape of the pair does not identify a mechanism; read the quoted tokens"
256 }
257 }
258 }
259}
260
261impl Difference {
262 /// **Which mechanism produced the movement this edit belongs to**, as far as its shape can say.
263 ///
264 /// Heuristic, and honestly so. What it reads is the run's shape —how many tokens went out, how many came in,
265 /// and what the first of each side spells —because that is the coarsest thing a diff can see and the finest
266 /// thing it can see *reliably*.
267 ///
268 /// The rules, in order:
269 ///
270 /// 1. a token only the compiler has, whose origin is a file our stream never mentions ?`MissingHeader`. The one
271 /// **certain** rule, which is why it outranks every shape below: whatever the tokens look like, the reason a
272 /// whole header is missing from our side is that we never read it;
273 /// 2. one token out, none in, and it is a name ?`UnexpandedMacro`;
274 /// 3. none out, one in, and it is a name ?`MissingExpansion`;
275 /// 4. **one side of the run is empty** ?`BranchDisagreement`. Tokens present on one side and absent on the other,
276 /// in a run, is a region that one reading compiled and the other did not —the fingerprint of an `#if` decided
277 /// the other way, and the work item the plan's §3.2 item 1 (the builtin macro table) exists for;
278 /// 5. **both sides have tokens but not the same number** ?`ExpansionDisagreement`: one name on one side and its
279 /// replacement list on the other;
280 /// 6. a name against a **number** ?`ConditionDisagreement` (`#if FOO > 2` answered `1` on one side and `0` on
281 /// the other is exactly this shape);
282 /// 7. anything else ?`Unknown`.
283 ///
284 /// `our_files` is the set of paths our stream mentions.
285 ///
286 /// # What this deliberately does not try to do
287 ///
288 /// It does **not** reconstruct which `#if` differed, or name the macro. A diff is a list of edits and has no
289 /// memory of what produced them; a report that invented a condition would be guessing with a straight face, which
290 /// is the one thing the plan's rule 3 forbids. [`Reason::advice`] says what to *look at* instead, and the per-file
291 /// token counts in `align_preprocessor`'s report are what localise it.
292 pub fn reason(&self, our_files: &std::collections::HashSet<&Path>) -> Reason {
293 let is_a_name = |token: &Option<StreamToken>| {
294 token.as_ref().is_some_and(|token| {
295 let mut characters = token.spelling.chars();
296 characters
297 .next()
298 .is_some_and(|first| first == '_' || first.is_alphabetic())
299 })
300 };
301 let is_a_number = |token: &Option<StreamToken>| {
302 token
303 .as_ref()
304 .is_some_and(|token| token.spelling.starts_with(|c: char| c.is_ascii_digit()))
305 };
306
307 // 1. A file the compiler read and we never entered.
308 if let Some(theirs) = &self.theirs
309 && let Some(file) = &theirs.file
310 && !our_files.contains(file.as_ref())
311 {
312 return Reason::MissingHeader;
313 }
314
315 // 2 and 3: one token each way, and it is a name. The isolated case, which is what a single unexpanded
316 // invocation looks like.
317 if self.run_ours == 1 && self.run_theirs == 0 && is_a_name(&self.ours) {
318 return Reason::UnexpandedMacro;
319 }
320 if self.run_ours == 0 && self.run_theirs == 1 && is_a_name(&self.theirs) {
321 return Reason::MissingExpansion;
322 }
323
324 // 4. One side of the run is empty: a region, not a name. Read one edit at a time this is "a name we have and
325 // they do not", which is why the run's shape has to be consulted rather than the pair's.
326 if self.run_ours == 0 || self.run_theirs == 0 {
327 return Reason::BranchDisagreement;
328 }
329
330 // 5. Both sides moved, different amounts: a substitution, which is a name and its expansion.
331 if self.run_ours != self.run_theirs {
332 return Reason::ExpansionDisagreement;
333 }
334
335 // 6. A name against a number: a condition that evaluated differently.
336 if is_a_name(&self.ours) != is_a_name(&self.theirs)
337 && (is_a_number(&self.ours) || is_a_number(&self.theirs))
338 {
339 return Reason::ConditionDisagreement;
340 }
341
342 Reason::Unknown
343 }
344}
345
346/// **The result of putting two streams side by side**: where they differ, and how much of them agreed.
347///
348/// The two counts are what make a reading comparable between runs —the plan's §5.2 requires that the number of
349/// differences only ever goes down, and a count of *matched* tokens is what keeps a run that got shorter from looking
350/// like a run that got better.
351///
352/// # The order of `differences` is part of the contract
353///
354/// Sorted by [`Difference::at`], ascending, and every field derived from that order is only meaningful because of it:
355/// a run is a group of *adjacent* positions, and adjacency is not a property of an unordered set. The traceback that
356/// produces them does **not** guarantee this —it walks backwards and a run of deletions comes out in descending
357/// order —so the sort is in [`align`] rather than left to whoever reads the list.
358#[derive(Debug, Clone, Default, PartialEq, Eq)]
359pub struct Alignment {
360 pub differences: Vec<Difference>,
361 /// Tokens the two streams agreed on, spelling for spelling.
362 pub matched: usize,
363 /// Whether the comparison stopped early —see [`MAX_EDIT_DISTANCE`].
364 ///
365 /// **Load-bearing, and the one field a caller must read before believing [`Alignment::differences`] is
366 /// exhaustive.** Two streams that share almost nothing (one of them empty, or the wrong file entirely) have a
367 /// difference count proportional to their *length*, which for a standard library header is millions —so the
368 /// walk is bounded, and a bounded walk has to say that it was bounded rather than present a prefix as a whole.
369 pub truncated: bool,
370}
371
372impl Alignment {
373 /// Differences grouped by mechanism, largest group first —what a report should print.
374 ///
375 /// The grouping is a `BTreeMap` over [`Reason`], so the order two mechanisms come out in does not depend on the
376 /// order their differences happened to appear in the stream. That is what makes the line a report records — /// `UnexpandedMacro=14 ConditionDisagreement=3` —comparable between two runs, which is the plan's §5.2
377 /// requirement that the difference count only ever go down.
378 pub fn by_reason(&self, our_files: &std::collections::HashSet<&Path>) -> Vec<(Reason, usize)> {
379 let mut counts: std::collections::BTreeMap<Reason, usize> =
380 std::collections::BTreeMap::new();
381 for difference in &self.differences {
382 *counts.entry(difference.reason(our_files)).or_default() += 1;
383 }
384
385 let mut counted: Vec<(Reason, usize)> = counts.into_iter().collect();
386 counted.sort_by(|(left_reason, left), (right_reason, right)| {
387 right.cmp(left).then_with(|| left_reason.cmp(right_reason))
388 });
389 counted
390 }
391
392 /// Did the two streams agree as sequences of spellings?
393 pub fn agrees(&self) -> bool {
394 self.differences.is_empty() && !self.truncated
395 }
396
397 /// **The files the compiler read and this reading never entered**, each once, in path order.
398 ///
399 /// The names behind [`Reason::MissingHeader`], which is the one **certain** classification this module makes: it
400 /// is asked of a difference whose token carries a file our stream does not mention at all, so it is a fact about
401 /// the two readings rather than a shape being interpreted. A count of those differences says how big the gap is;
402 /// this says *which* search went differently, and that is what a caller can act on.
403 ///
404 /// It earns its own method because of a measurement: on `#include <vector>` against MSVC's own STL, **46 files**
405 /// came out this way while the two streams' total lengths differed by 252 tokens. So the gap was never "we read
406 /// the same files slightly differently" — it was whole files one side read and the other did not, which is a
407 /// different repair.
408 pub fn headers_we_never_entered(
409 &self,
410 our_files: &std::collections::HashSet<&Path>,
411 ) -> Vec<&Path> {
412 let mut missing: Vec<&Path> = self
413 .differences
414 .iter()
415 .filter(|difference| difference.reason(our_files) == Reason::MissingHeader)
416 .filter_map(|difference| difference.theirs.as_ref()?.file.as_deref())
417 .collect();
418
419 missing.sort_unstable();
420 missing.dedup();
421 missing
422 }
423}
424
425/// How far apart two streams may be before the comparison stops looking for the smallest diff.
426///
427/// The diff is Myers', whose cost is proportional to the **edit distance** and not to the stream lengths —which is
428/// why it is the right algorithm here and why this bound is the only thing that makes an unbounded input safe. Two
429/// streams that are nearly the same (the ordinary case, and the only interesting one) finish in a few passes. Two
430/// streams that are unrelated do not converge at all: the distance is the length of the longer one, and for a
431/// 40 000-token header that is 40 000 snapshots of a 40 000-wide array.
432///
433/// Past this the comparison returns what it has and sets [`Alignment::truncated`]. The bound is generous on purpose:
434/// the differences worth classifying are the ones a *reading* produced, and a reading that is 4 000 tokens away from
435/// the compiler is not being classified, it is being rewritten.
436pub const MAX_EDIT_DISTANCE: usize = 4096;
437
438/// **Put two token streams side by side** and report the smallest set of edits that explains their difference.
439///
440/// Myers' algorithm —the same one `git diff` uses —chosen over the textbook LCS table for a reason that is
441/// entirely about this crate's inputs: the table is `O(n·m)` in **memory**, and the streams here are a standard
442/// library's whole closure (millions of tokens). Myers' is `O((n + m)·d)` in time and `O(d²)`-ish in memory, where
443/// `d` is the number of differences —which for the case this module exists for is tiny.
444///
445/// The result is a list of [`Difference`]s in stream order, each naming the token on one side or both, so a reader
446/// can see a substitution as one entry rather than as a delete followed by an insert.
447pub fn align(ours: &[StreamToken], theirs: &[StreamToken]) -> Alignment {
448 let mut alignment = Alignment::default();
449
450 // **The common prefix and suffix are taken off first**, and that is not a micro-optimisation: it is what makes
451 // the bound in `MAX_EDIT_DISTANCE` irrelevant for the ordinary case. Two readings of one file agree for
452 // thousands of tokens at a time, and the diff only ever has to run over the region between two disagreements.
453 let mut prefix = 0usize;
454 while prefix < ours.len()
455 && prefix < theirs.len()
456 && ours[prefix].spelling == theirs[prefix].spelling
457 {
458 prefix += 1;
459 }
460
461 let mut suffix = 0usize;
462 while suffix < ours.len() - prefix
463 && suffix < theirs.len() - prefix
464 && ours[ours.len() - 1 - suffix].spelling == theirs[theirs.len() - 1 - suffix].spelling
465 {
466 suffix += 1;
467 }
468
469 // Settled below, once the script says how many of our tokens it had to touch.
470 alignment.matched = 0;
471
472 let our_middle = &ours[prefix..ours.len() - suffix];
473 let their_middle = &theirs[prefix..theirs.len() - suffix];
474
475 let (edits, truncated) = anchored_edit_script(our_middle, their_middle, 0);
476 alignment.truncated = truncated;
477
478 for (at, ours_at, theirs_at) in edits {
479 alignment.differences.push(Difference {
480 at: prefix + at,
481 ours: ours_at.map(|index| our_middle[index].clone()),
482 theirs: theirs_at.map(|index| their_middle[index].clone()),
483 // Filled in below, once the whole script is in hand: a run is a property of the sequence and cannot be
484 // known while the sequence is still being built.
485 run: 1,
486 run_ours: 0,
487 run_theirs: 0,
488 });
489 }
490
491 // **Sorted by position before anything reads them.** The traceback walks backwards and can emit a run of pure
492 // deletions in *descending* order —`["a", "b"]` against `[]` comes back as "delete at 1, delete at 0" —and every
493 // consumer here reasons about `at` as a position in the stream. Grouping an unsorted list would see two
494 // movements where the streams moved once, and a report would count one `#if` as two.
495 alignment
496 .differences
497 .sort_by_key(|difference| difference.at);
498
499 alignment.matched = ours.len()
500 - alignment
501 .differences
502 .iter()
503 .filter(|difference| difference.ours.is_some())
504 .count();
505
506 // **Group the edits into runs**, which is what the three `run*` fields mean: every edit that sits one slot after
507 // the one before it belongs to the same movement of tokens. Now that the list is ordered, one forward pass is
508 // enough.
509 group_into_runs(&mut alignment.differences);
510
511 alignment
512}
513
514/// Give every difference in a contiguous group the size of that group, and the group's two token counts.
515///
516/// Contiguity is `at == previous.at + 1`: the streams agreed on nothing in between. A gap is a real boundary —the
517/// two agreed for at least one token there, so whatever moved on either side of it moved for two different reasons.
518///
519/// The counts are what [`Difference::reason`] reads, and they are counted **over the group** rather than per edit:
520/// one macro that expands to three tokens is one token out and three in, and no single edit of that movement knows
521/// it.
522fn group_into_runs(differences: &mut [Difference]) {
523 let mut start = 0usize;
524 while start < differences.len() {
525 let mut end = start + 1;
526 while end < differences.len() && differences[end].at == differences[end - 1].at + 1 {
527 end += 1;
528 }
529
530 let run = end - start;
531 let out = differences[start..end]
532 .iter()
533 .filter(|difference| difference.ours.is_some())
534 .count();
535 let added = differences[start..end]
536 .iter()
537 .filter(|difference| difference.theirs.is_some())
538 .count();
539
540 for difference in &mut differences[start..end] {
541 difference.run = run;
542 difference.run_ours = out;
543 difference.run_theirs = added;
544 }
545 start = end;
546 }
547}
548
549/// **The window widths anchors are looked for at**, widest first.
550///
551/// A window that occurs once in each stream is a place the two readings certainly agree about, and it is what lets
552/// a multi-hundred-thousand-token comparison be cut into pieces the table below can afford. Wide first because a
553/// wide window is unique by construction; narrower only for the gaps the wide one could not cut.
554const ANCHOR_WIDTHS: [usize; 4] = [24, 12, 6, 3];
555
556/// **A script over streams too long for one table**, made by cutting them at agreed places first.
557///
558/// [`shortest_edit_script`] is bounded at [`MAX_DP_CELLS`], and a standard library's closure is a half-million tokens
559/// a side: handed whole, it gave up at the first disagreement and called **every token** a difference, which is not a
560/// measurement. This finds windows that occur exactly once in each stream, keeps the longest chain of them that is in
561/// the same order on both sides (a patience diff), and runs the table only between consecutive anchors. Where a gap
562/// is still too large, it is cut again with a narrower window; where no window cuts it, the table's own honest
563/// "truncated" answer stands.
564fn anchored_edit_script(
565 ours: &[StreamToken],
566 theirs: &[StreamToken],
567 width_index: usize,
568) -> (Vec<(usize, Option<usize>, Option<usize>)>, bool) {
569 if ours.len().saturating_mul(theirs.len()) <= MAX_DP_CELLS || width_index >= ANCHOR_WIDTHS.len()
570 {
571 return shortest_edit_script(ours, theirs);
572 }
573
574 let width = ANCHOR_WIDTHS[width_index];
575 let anchors = unique_anchors(ours, theirs, width);
576 if anchors.is_empty() {
577 return anchored_edit_script(ours, theirs, width_index + 1);
578 }
579
580 let mut edits = Vec::new();
581 let mut truncated = false;
582 let (mut our_cursor, mut their_cursor) = (0usize, 0usize);
583
584 let mut gap = |our_from: usize, our_to: usize, their_from: usize, their_to: usize| {
585 let (found, cut) = anchored_edit_script(
586 &ours[our_from..our_to],
587 &theirs[their_from..their_to],
588 width_index + 1,
589 );
590 truncated |= cut;
591 for (at, our_index, their_index) in found {
592 edits.push((
593 at + our_from,
594 our_index.map(|index| index + our_from),
595 their_index.map(|index| index + their_from),
596 ));
597 }
598 };
599
600 for (our_at, their_at) in anchors {
601 if our_at < our_cursor || their_at < their_cursor {
602 continue;
603 }
604 gap(our_cursor, our_at, their_cursor, their_at);
605 our_cursor = our_at + width;
606 their_cursor = their_at + width;
607 while our_cursor < ours.len()
608 && their_cursor < theirs.len()
609 && ours[our_cursor].spelling == theirs[their_cursor].spelling
610 {
611 our_cursor += 1;
612 their_cursor += 1;
613 }
614 }
615 gap(our_cursor, ours.len(), their_cursor, theirs.len());
616
617 (edits, truncated)
618}
619
620/// The windows of `width` tokens that occur **exactly once** in each stream, as `(ours, theirs)` start positions in
621/// our order, restricted to the longest chain that is also increasing in theirs.
622fn unique_anchors(
623 ours: &[StreamToken],
624 theirs: &[StreamToken],
625 width: usize,
626) -> Vec<(usize, usize)> {
627 use std::collections::HashMap;
628
629 if ours.len() < width || theirs.len() < width {
630 return Vec::new();
631 }
632
633 // `Some(position)` the first time a window is seen, `None` once it has been seen twice.
634 let windows = |tokens: &[StreamToken]| -> HashMap<u64, Option<usize>> {
635 let mut seen: HashMap<u64, Option<usize>> = HashMap::new();
636 for (start, window) in tokens.windows(width).enumerate() {
637 seen.entry(hash_window(window))
638 .and_modify(|entry| *entry = None)
639 .or_insert(Some(start));
640 }
641 seen
642 };
643
644 let theirs_windows = windows(theirs);
645 let ours_windows = windows(ours);
646
647 let mut pairs: Vec<(usize, usize)> = ours_windows
648 .iter()
649 .filter_map(|(hash, ours_at)| {
650 let (ours_at, theirs_at) = ((*ours_at)?, (*theirs_windows.get(hash)?)?);
651 // A hash agreeing is not the windows agreeing.
652 let same = ours[ours_at..ours_at + width]
653 .iter()
654 .zip(&theirs[theirs_at..theirs_at + width])
655 .all(|(one, other)| one.spelling == other.spelling);
656 same.then_some((ours_at, theirs_at))
657 })
658 .collect();
659 pairs.sort_unstable();
660
661 // Longest increasing subsequence by `theirs`, with the predecessor links to read the chain back.
662 let mut tails: Vec<usize> = Vec::new();
663 let mut previous: Vec<Option<usize>> = vec![None; pairs.len()];
664 for index in 0..pairs.len() {
665 let theirs_at = pairs[index].1;
666 let slot = tails.partition_point(|&tail| pairs[tail].1 < theirs_at);
667 previous[index] = slot.checked_sub(1).map(|before| tails[before]);
668 if slot == tails.len() {
669 tails.push(index);
670 } else {
671 tails[slot] = index;
672 }
673 }
674
675 let mut chain = Vec::with_capacity(tails.len());
676 let mut at = tails.last().copied();
677 while let Some(index) = at {
678 chain.push(pairs[index]);
679 at = previous[index];
680 }
681 chain.reverse();
682 chain
683}
684
685fn hash_window(window: &[StreamToken]) -> u64 {
686 use std::hash::{Hash, Hasher};
687
688 let mut hasher = std::collections::hash_map::DefaultHasher::new();
689 for token in window {
690 token.spelling.hash(&mut hasher);
691 }
692 hasher.finish()
693}
694/// Myers' shortest edit script over two slices, as `(position, our index, their index)` triples in stream order.
695/// **How far the comparison may go before it stops looking for the smallest script.**
696///
697/// The diff below is a table whose size is the **product** of the two middle lengths, and the middle is what is left
698/// after the common prefix and suffix are trimmed away —which for two readings of one file is a handful of tokens.
699/// It is only large when the two streams are largely unrelated, and then the shortest script is not worth finding:
700/// an unrelated stream is a bug in the comparison, not a reading to classify.
701///
702/// So the table is bounded, and past the bound the answer is the **honest** one rather than an approximation: every
703/// token on one side deleted and every token on the other inserted, with `truncated` set. A caller that reports those
704/// as differences to fix would be reporting an unrelated stream as a work list, which is why the flag is not optional.
705///
706/// Four million cells is 16 MB of `u32` —large enough that no *reading* of a real file reaches it.
707const MAX_DP_CELLS: usize = 4_000_000;
708
709/// **The shortest script that turns our stream into theirs**, as `(position, our index, their index)` triples in
710/// stream order.
711///
712/// Returns `(edits, truncated)`. A triple with both indices is a **substitution** —one difference naming what
713/// replaced what —and one with a single index is a token that only one side has.
714///
715/// # Why a table rather than Myers
716///
717/// The version before this was Myers' algorithm, and it was wrong in three separate ways that only showed up once the
718/// tests ran: the diagonal array was sized for the grid rather than for the walk (so every one-token substitution
719/// panicked on an index underflow), the traceback walked `x` and `y` back independently (so a deletion and an
720/// insertion two slots apart were read as one substitution), and the "same slot" test that was supposed to group them
721/// did not. Each fix was plausible and the next test found the next bug.
722///
723/// A longest-common-subsequence table has one invariant, and it is the one that matters: **the script it produces
724/// replays**. Walking the table backwards from `(n, m)` to `(0, 0)` visits every cell once, and the moves are fixed by
725/// the table —there is no diagonal arithmetic to get wrong and no snapshot to index. The cost is memory, which the
726/// bound above is what makes acceptable, and the size is what the common prefix and suffix trimming is what makes
727/// small.
728///
729/// The round-trip property is asserted by `a_script_replays_our_stream_as_theirs`, because that is the property a
730/// difference list has to have and the one the Myers version silently violated.
731fn shortest_edit_script(
732 ours: &[StreamToken],
733 theirs: &[StreamToken],
734) -> (Vec<(usize, Option<usize>, Option<usize>)>, bool) {
735 let (n, m) = (ours.len(), theirs.len());
736
737 if n == 0 && m == 0 {
738 return (Vec::new(), false);
739 }
740 if n == 0 {
741 return ((0..m).map(|at| (at, None, Some(at))).collect(), false);
742 }
743 if m == 0 {
744 return ((0..n).map(|at| (at, Some(at), None)).collect(), false);
745 }
746
747 if n.saturating_mul(m) > MAX_DP_CELLS {
748 // Past the bound: everything is an edit, and the flag says so.
749 let mut edits = Vec::with_capacity(n + m);
750 for at in 0..n {
751 edits.push((at, Some(at), None));
752 }
753 for at in 0..m {
754 edits.push((n + at, None, Some(at)));
755 }
756 return (edits, true);
757 }
758
759 // `lengths[i][j]` is the length of the longest common subsequence of `ours[i..]` and `theirs[j..]`, filled from
760 // the bottom right. `(n + 1) * (m + 1)` cells, one `u32` each.
761 let width = m + 1;
762 let mut lengths = vec![0u32; (n + 1) * width];
763 let cell = |row: usize, column: usize| row * width + column;
764
765 for i in (0..n).rev() {
766 for j in (0..m).rev() {
767 lengths[cell(i, j)] = if ours[i].spelling == theirs[j].spelling {
768 lengths[cell(i + 1, j + 1)] + 1
769 } else {
770 lengths[cell(i + 1, j)].max(lengths[cell(i, j + 1)])
771 };
772 }
773 }
774
775 // **Walk the table forwards**, which is what makes the result a script rather than a pile of edits: at each cell
776 // either the two tokens are the same (they match, and neither is an edit) or one of them is deleted. A deletion
777 // that happens where the *other* side also has to lose a token is published as a substitution, and that is the
778 // grouping rule — `queue` collects one side's deletions and the other's insertions while they are contiguous.
779 //
780 // # The two coordinate systems, and the bug that came from mixing them
781 //
782 // A run of edits is published at a position in the **whole script**, and the tokens it names are indices in
783 // `ours` and `theirs`. The first version of this computed the position from `i + j - edits` and the token indices
784 // from `i`, which are the same number only while nothing has matched: it was right for a difference at the very
785 // start and wrong by the number of matched tokens after it. So `matched` is tracked explicitly and both numbers
786 // come from it — `from = i - deleted` is the position, `i - deleted` is the token, and they are equal *because*
787 // a match advances both cursors and the script together.
788 let mut edits: Vec<(usize, Option<usize>, Option<usize>)> = Vec::new();
789 let mut queue: Vec<(bool, bool)> = Vec::new();
790 let (mut i, mut j) = (0usize, 0usize);
791 let mut matched = 0usize;
792
793 while i < n || j < m {
794 let same = i < n && j < m && ours[i].spelling == theirs[j].spelling;
795
796 if same {
797 flush(&mut edits, &mut queue, i, matched, i, j);
798 i += 1;
799 j += 1;
800 matched += 1;
801 continue;
802 }
803
804 // Not a match: one of the two has to go. Which one is decided by the table, and the tie (`>=`) prefers
805 // deleting from ours, which keeps a substitution's two halves adjacent rather than separated by a match.
806 let delete_ours = if i >= n {
807 false
808 } else if j >= m {
809 true
810 } else {
811 lengths[cell(i + 1, j)] >= lengths[cell(i, j + 1)]
812 };
813
814 if delete_ours {
815 queue.push((true, false));
816 i += 1;
817 } else {
818 queue.push((false, true));
819 j += 1;
820 }
821 }
822
823 flush(&mut edits, &mut queue, i, matched, i, j);
824 (edits, false)
825}
826
827/// **Publish the edits queued for one position** as the smallest set of differences that explains them.
828///
829/// `our_run` and `their_run` are the cursors *after* the queued tokens were consumed, and `matched` is how many
830/// tokens have matched so far. A deletion and an insertion at one position are **one** difference with both halves
831/// — a substitution, which is what a reader wants: two entries that both say "ours: nothing, theirs: `NEW`" is one
832/// difference reported twice, with neither half saying what replaced what.
833///
834/// Whatever is left over comes out one-sided, which is the truth about those tokens: a replacement list longer than
835/// the name it replaced really is one name gone and three tokens arrived.
836///
837/// # The two coordinate systems, and the bug that came from mixing them
838///
839/// The position a difference is published at is a place in the **whole script**; the token it names is an index in
840/// `ours` or `theirs`. The first version computed the position from the number of matched tokens *after* the run
841/// instead of before it, which is the same number only while nothing has matched — right for a difference at the very
842/// start, and wrong by the number of matched tokens for every one after that. The fix is not a different formula: a
843/// match advances both cursors and the script together, so `cursor - run_length` is **both** the token index and the
844/// position, and there is only one number to get right.
845fn flush(
846 edits: &mut Vec<(usize, Option<usize>, Option<usize>)>,
847 queue: &mut Vec<(bool, bool)>,
848 _cursor: usize,
849 _matched: usize,
850 our_run: usize,
851 their_run: usize,
852) {
853 let deleted = queue.iter().filter(|(deleted, _)| *deleted).count();
854 let inserted = queue.iter().filter(|(_, inserted)| *inserted).count();
855
856 // Both numbers, from the one that cannot be wrong: a cursor minus the length of the run it just consumed.
857 let our_first = our_run - deleted;
858 let their_first = their_run - inserted;
859 let from = our_first;
860
861 if deleted > 0 && inserted > 0 {
862 // One substitution for the pair, then whichever side has more left over.
863 edits.push((from, Some(our_first), Some(their_first)));
864 for offset in 1..deleted {
865 edits.push((from + offset, Some(our_first + offset), None));
866 }
867 for offset in 1..inserted {
868 edits.push((from + offset, None, Some(their_first + offset)));
869 }
870 } else if deleted > 0 {
871 for offset in 0..deleted {
872 edits.push((from + offset, Some(our_first + offset), None));
873 }
874 } else {
875 for offset in 0..inserted {
876 edits.push((from + offset, None, Some(their_first + offset)));
877 }
878 }
879
880 queue.clear();
881}
882
883/// **The stream with every pragma taken out**, so two compilers' different ways of *carrying* one stop being
884/// differences.
885///
886/// Measured against `cl /E` on `<format>`: the compiler prints `#pragma` lines at its own place in the output (a
887/// header's `#pragma comment` arrives before the `#pragma detect_mismatch` that precedes it in the source), and it
888/// rewrites `_Pragma("warning(push)")` into `__pragma(warning(push))`. Neither is a *reading* of the program — a
889/// pragma is a message to the compiler, and no declaration depends on it — but together they were three thousand
890/// differences that buried the ones that were.
891///
892/// What goes: a `#` `pragma` line (every following token on the same file and line), and a `_Pragma(…)` or
893/// `__pragma(…)` operator with its balanced parenthesis. What stays: everything else, including the tokens either
894/// side of them. A comparison that wants to notice a wrong `#pragma once` keeps the stream as it is and does not
895/// call this.
896pub fn without_pragmas(tokens: &[StreamToken]) -> Vec<StreamToken> {
897 let mut kept = Vec::with_capacity(tokens.len());
898 let mut index = 0usize;
899
900 let same_line =
901 |one: &StreamToken, other: &StreamToken| one.file == other.file && one.line == other.line;
902
903 while index < tokens.len() {
904 let token = &tokens[index];
905
906 if &*token.spelling == "#"
907 && tokens
908 .get(index + 1)
909 .is_some_and(|next| &*next.spelling == "pragma" && same_line(token, next))
910 {
911 index += 2;
912 while index < tokens.len() && same_line(token, &tokens[index]) {
913 index += 1;
914 }
915 continue;
916 }
917
918 if matches!(&*token.spelling, "_Pragma" | "__pragma")
919 && tokens
920 .get(index + 1)
921 .is_some_and(|next| &*next.spelling == "(")
922 {
923 let mut depth = 0usize;
924 let mut end = index + 1;
925 while end < tokens.len() {
926 match &*tokens[end].spelling {
927 "(" => depth += 1,
928 ")" => {
929 depth -= 1;
930 if depth == 0 {
931 break;
932 }
933 }
934 _ => {}
935 }
936 end += 1;
937 }
938 index = end + 1;
939 continue;
940 }
941
942 kept.push(token.clone());
943 index += 1;
944 }
945
946 kept
947}
948/// **Read the tokens out of a real preprocessor's output**, dropping its line markers and keeping the position they
949/// state.
950///
951/// The markers are the whole reason this cannot be `cpp_parser::lex(text)` and done: a compiler's `-E` output is not
952/// a file, it is a **concatenation of every file it read** —the directive's whole purpose is to say which one the
953/// text after it came from. So the markers are parsed rather than skipped, and every token gets the file and line
954/// they announced. That is exactly the plan's "file boundaries" comparison, and it is why this function returns
955/// [`StreamToken`]s rather than plain spellings.
956///
957/// # The marker syntaxes, all of them
958///
959/// ```text
960/// # 12 "C:\\…\\xstring" 2 3 4 GCC and Clang (the flags are the enter/leave/system hints)
961/// #line 12 "C:\\…\\xstring" MSVC, and C's own `#line`
962/// # 12 a line with no file: the path does not change
963/// ```
964///
965/// Anything else beginning with `#` is **not** a marker and is kept as tokens —`#pragma` lines survive `-E`, and a
966/// comparison that dropped every `#`-line would stop noticing a `#pragma once` this reading got wrong.
967///
968/// # The rule for the line number, which is the one thing here that is easy to get wrong
969///
970/// A marker says *"the next line of output came from line N of file F"*. So each token's line is the position the
971/// output has reached **since** the marker, counting output newlines —not the marker's own number for everything
972/// that follows it. Getting this wrong is invisible in a one-line fixture and wrong in every real file.
973///
974/// # What is dropped
975///
976/// Whitespace and comments, by the lexer, because neither side has them: our stream is a rendering with one space
977/// between tokens and no comments at all. Comparing them would make every run differ on layout and say nothing about
978/// preprocessor behaviour —which is the comparison being made.
979pub fn tokenize_preprocessed(text: &str) -> Vec<StreamToken> {
980 let (tokens, _) = cpp_parser::lex(text, &cpp_parser::LexerConfig::default());
981 let mut out: Vec<StreamToken> = Vec::with_capacity(tokens.len());
982
983 // What the last marker announced, and how many **newlines** have gone by since. `None` until a marker is seen,
984 // which is the honest state: a compiler that printed none (a fragment, a hand-written fixture) says nothing about
985 // where its tokens are.
986 //
987 // A counter of newlines rather than of *tokens*: the lexer emits `Whitespace` as a token of its own, so most lines
988 // are several tokens long and counting them would put every token on a line of its own —which is the bug that
989 // made `our_tokens_take_their_line_from_the_file_not_from_the_rendering` fail on the other side of this same
990 // question.
991 let mut file: Option<Arc<Path>> = None;
992 let mut marked_line: Option<u32> = None;
993 let mut newlines_since = 0u32;
994
995 let mut index = 0usize;
996 while index < tokens.len() {
997 let token = &tokens[index];
998 let start = token.range.start_offset;
999
1000 if token.kind == cpp_parser::CppTokenKind::Newline {
1001 newlines_since += 1;
1002 index += 1;
1003 continue;
1004 }
1005
1006 // A marker is a `#` whose **line** holds nothing before it. The test is on the *text* from the last newline,
1007 // not on the previous token: the lexer emits `Whitespace`, so a `#` that really is first on its line is
1008 // preceded by a `Whitespace` token rather than by a `Newline` —and a test against the token before it calls
1009 // that "first", which would turn `#if` and `#define` lines in the compiler's output into markers.
1010 let line_begin = text[..start].rfind('\n').map_or(0, |at| at + 1);
1011 let is_first_on_its_line = text[line_begin..start].trim().is_empty();
1012 if is_first_on_its_line
1013 && token.kind == cpp_parser::CppTokenKind::Hash
1014 && let Some(marker) = read_a_line_marker(text, &tokens, index)
1015 {
1016 if let Some(named) = marker.file {
1017 file = Some(named);
1018 }
1019 marked_line = Some(marker.line);
1020 // **Zero, not one.** The marker's own line is the one it *names*, and the token right after the marker is
1021 // still on it: the newline that ends the marker line has not been seen yet, and it is the newline **of
1022 // line N**. Counting it would put every token one line too far down —which is wrong by exactly one for
1023 // the whole file, the kind of error that looks plausible in a report.
1024 newlines_since = 0;
1025 index = tokens
1026 .partition_point(|token| token.range.start_offset < marker.end)
1027 .max(index + 1);
1028 continue;
1029 }
1030
1031 if !cpp_parser::is_trivia(token.kind) {
1032 out.push(StreamToken {
1033 spelling: text[start..token.range.end_offset()].into(),
1034 file: file.clone(),
1035 line: marked_line.map(|line| line + newlines_since.saturating_sub(1)),
1036 });
1037 }
1038
1039 index += 1;
1040 }
1041
1042 out
1043}
1044
1045/// A line marker, as read: the file it names (when it names one), the line, and where it ends.
1046struct LineMarker {
1047 file: Option<Arc<Path>>,
1048 line: u32,
1049 /// The offset of the newline that ends the marker's line —so the next token's line starts counting from there.
1050 end: usize,
1051}
1052
1053/// Read a line marker starting at the `#` at `tokens[index]`, if that is what this is.
1054///
1055/// The three shapes GCC and MSVC print are all accepted, and the answer's `file` is `None` for `# 12` —a marker that
1056/// names no path —which leaves the current file in place rather than clearing it.
1057fn read_a_line_marker(
1058 text: &str,
1059 tokens: &[cpp_parser::CppTokenData],
1060 index: usize,
1061) -> Option<LineMarker> {
1062 /// The next token that is not whitespace or a comment, at or after `from`.
1063 ///
1064 /// **The lexer keeps whitespace**, so this is not optional: `spelling_at(index + 1)` reads the *space* after the
1065 /// `#`, not the number, and a reader that took the token at a fixed offset would answer "not a marker" for every
1066 /// well-formed marker there is. That was the bug —a marker one token wide is a marker this never found.
1067 fn next_significant(
1068 text: &str,
1069 tokens: &[cpp_parser::CppTokenData],
1070 from: usize,
1071 ) -> Option<usize> {
1072 (from..tokens.len())
1073 .find(|at| !cpp_parser::is_trivia(tokens[*at].kind))
1074 .filter(|at| !text.is_empty() && *at < tokens.len())
1075 }
1076
1077 let spelling_at = |at: usize| {
1078 tokens
1079 .get(at)
1080 .map(|token| &text[token.range.start_offset..token.range.end_offset()])
1081 };
1082 let significance = |from: usize| next_significant(text, tokens, from);
1083
1084 // `# 12 …`, or MSVC's `# line 12 …` —the keyword is optional and is not a number.
1085 let mut at = significance(index + 1)?;
1086 if spelling_at(at) == Some("line") {
1087 at = significance(at + 1)?;
1088 }
1089
1090 let number: u32 = spelling_at(at)?
1091 .trim_end_matches(['u', 'U', 'l', 'L'])
1092 .parse()
1093 .ok()?;
1094
1095 // An optional quoted path: present in both compilers' spelling, absent for a bare `# 12`. Read at the next
1096 // **significant** token for the same reason as above, and left unread (the marker ends at the line anyway) when
1097 // it is not a string.
1098 //
1099 // **Through `shared`**, which is what makes this path comparable with ours: the resolver records a normalized
1100 // path and a compiler prints whatever it likes, so the two spellings have to meet in the middle or every file is
1101 // [`Reason::MissingHeader`]. Building the `Arc<Path>` here instead was a real bug — our side normalized and this
1102 // one did not.
1103 let mut file = None;
1104 if let Some(path_at) = significance(at + 1)
1105 && let Some(named) = spelling_at(path_at).and_then(unquote)
1106 {
1107 file = Some(shared(Path::new(&named)));
1108 }
1109
1110 // Everything left on this output line is the marker's flags —GCC's `1 3 4`, MSVC's nothing. None of it is a
1111 // token of the program, so the marker runs to the end of the line it is written on.
1112 let line_begin = text[..tokens[index].range.start_offset]
1113 .rfind('\n')
1114 .map_or(0, |at| at + 1);
1115 let end = text[line_begin..]
1116 .find('\n')
1117 .map_or(text.len(), |at| line_begin + at);
1118
1119 Some(LineMarker {
1120 file,
1121 line: number,
1122 end,
1123 })
1124}
1125
1126/// The contents of a C string literal, when it is one this reader can unquote.
1127///
1128/// A marker's path is written by the compiler, so the escapes are the compiler's: `\\` and `\"` are the two that
1129/// appear, and a path with a `\n` in it does not exist.
1130///
1131/// # Why an unknown escape keeps its backslash
1132///
1133/// The first version dropped it, on the reasoning that "a compiler that printed an unknown escape meant the
1134/// character". That is right for `\d` in a path and **wrong for the one case that actually occurs**: a Windows path
1135/// like `C:\Users\zc\src` is not a well-formed C string, and dropping backslashes turns it into `C:Userszcsrc` —a
1136/// path that does not exist but looks like one. Keeping the backslash turns it into a path that does not exist and
1137/// *looks wrong*, which is the failure mode to prefer, and it is also what a real C compiler does for an
1138/// unrecognised escape (a diagnostic, and the character kept as written).
1139///
1140/// So `\\` and `\"` are decoded because those two are real, and everything else is copied through verbatim. An
1141/// unterminated or differently-quoted literal is `None`, and the marker then names no file rather than a wrong one.
1142fn unquote(spelling: &str) -> Option<String> {
1143 let body = spelling.strip_prefix('"')?.strip_suffix('"')?;
1144
1145 let mut out = String::with_capacity(body.len());
1146 let mut characters = body.chars();
1147 while let Some(character) = characters.next() {
1148 if character != '\\' {
1149 out.push(character);
1150 continue;
1151 }
1152
1153 match characters.next()? {
1154 '\\' => out.push('\\'),
1155 '"' => out.push('"'),
1156 other => {
1157 out.push('\\');
1158 out.push(other);
1159 }
1160 }
1161 }
1162
1163 Some(out)
1164}
1165
1166/// The set of files a stream mentions —what [`Difference::reason`] needs to tell "we never read that header" from
1167/// "we read it and disagreed about its contents".
1168pub fn files_of(stream: &[StreamToken]) -> std::collections::HashSet<&Path> {
1169 stream
1170 .iter()
1171 .filter_map(|token| token.file.as_deref())
1172 .collect()
1173}
1174
1175/// **A whole comparison as one report**, with the differences grouped by mechanism.
1176///
1177/// The text a caller prints, and a type rather than a `String` so that a test can assert about the *counts* —which
1178/// are the numbers the plan's §5.2 requires to be monotone —without parsing a report.
1179#[derive(Debug, Clone, Default, PartialEq, Eq)]
1180pub struct Report {
1181 /// Tokens the two agreed on.
1182 pub matched: usize,
1183 /// Tokens we produced.
1184 pub ours: usize,
1185 /// Tokens the compiler produced.
1186 pub theirs: usize,
1187 /// Each mechanism, with how many differences it accounts for, largest first.
1188 pub by_reason: Vec<(Reason, usize)>,
1189 /// The differences themselves, capped —see [`Report::differences`].
1190 pub differences: Vec<Difference>,
1191 /// Whether the comparison was stopped early —see [`Alignment::truncated`].
1192 pub truncated: bool,
1193}
1194
1195/// How many individual differences a [`Report`] carries, however many there are.
1196///
1197/// The counts are the report; the samples are what a reader looks at to believe the counts. Carrying a million
1198/// differences to print twenty of them is the shape this crate keeps having to fix.
1199const REPORTED_DIFFERENCES: usize = 40;
1200
1201impl Report {
1202 /// Compare two streams and summarise.
1203 pub fn of(ours: &[StreamToken], theirs: &[StreamToken]) -> Report {
1204 let alignment = align(ours, theirs);
1205 let our_files = files_of(ours);
1206
1207 Report {
1208 matched: alignment.matched,
1209 ours: ours.len(),
1210 theirs: theirs.len(),
1211 by_reason: alignment.by_reason(&our_files),
1212 differences: alignment
1213 .differences
1214 .iter()
1215 .take(REPORTED_DIFFERENCES)
1216 .cloned()
1217 .collect(),
1218 truncated: alignment.truncated,
1219 }
1220 }
1221
1222 /// Did the two streams agree?
1223 pub fn agrees(&self) -> bool {
1224 self.by_reason.is_empty() && !self.truncated
1225 }
1226
1227 /// **The files the compiler read and this reading never entered** — see
1228 /// [`Alignment::headers_we_never_entered`] for why the names matter more than the count.
1229 ///
1230 /// A `Report` carries only a **sample** of the differences (see [`REPORTED_DIFFERENCES`]), so this works from
1231 /// that sample: it is a list of *examples* of a search that went differently, not an exhaustive one. The count in
1232 /// [`Report::by_reason`] is the exhaustive number.
1233 pub fn headers_we_never_entered(
1234 &self,
1235 our_files: &std::collections::HashSet<&Path>,
1236 ) -> Vec<&Path> {
1237 let mut missing: Vec<&Path> = self
1238 .differences
1239 .iter()
1240 .filter(|difference| difference.reason(our_files) == Reason::MissingHeader)
1241 .filter_map(|difference| difference.theirs.as_ref()?.file.as_deref())
1242 .collect();
1243
1244 missing.sort_unstable();
1245 missing.dedup();
1246 missing
1247 }
1248
1249 /// The report as text: the counts, then one line per difference with its mechanism and both tokens.
1250 pub fn render(&self) -> String {
1251 let mut out = String::new();
1252 out.push_str(&format!(
1253 "ours {} tokens | theirs {} tokens | matched {} | differences {}{}\n",
1254 self.ours,
1255 self.theirs,
1256 self.matched,
1257 self.by_reason
1258 .iter()
1259 .map(|(_, count)| *count)
1260 .sum::<usize>(),
1261 if self.truncated {
1262 " (the comparison stopped early, so this is a lower bound)"
1263 } else {
1264 ""
1265 }
1266 ));
1267
1268 if self.by_reason.is_empty() {
1269 out.push_str(" the two streams agree\n");
1270 return out;
1271 }
1272
1273 out.push_str("by mechanism:\n");
1274 for (reason, count) in &self.by_reason {
1275 out.push_str(&format!(" {count:>7} {reason:?}\n"));
1276 out.push_str(&format!(" {}\n", reason.advice()));
1277 }
1278
1279 out.push_str("first differences:\n");
1280 for difference in &self.differences {
1281 let ours = difference.ours.as_ref().map_or_else(
1282 || "-".to_string(),
1283 |token| format!("{} @ {}", token.spelling, token.origin()),
1284 );
1285 let theirs = difference.theirs.as_ref().map_or_else(
1286 || "-".to_string(),
1287 |token| format!("{} @ {}", token.spelling, token.origin()),
1288 );
1289 out.push_str(&format!(
1290 " #{} ours: {ours} theirs: {theirs}\n",
1291 difference.at
1292 ));
1293 }
1294 if !self.truncated {
1295 let total: usize = self.by_reason.iter().map(|(_, count)| *count).sum();
1296 if total > self.differences.len() {
1297 out.push_str(&format!(" —{} more\n", total - self.differences.len()));
1298 }
1299 }
1300
1301 out
1302 }
1303}
1304
1305/// The path of a file as a [`StreamToken`] carries it: **normalized**, and shared.
1306///
1307/// # Why normalizing here, and not at the comparison
1308///
1309/// The two halves of a comparison get their paths from different places, and the raw spellings do **not** compare
1310/// equal:
1311///
1312/// ```text
1313/// ours RenderedUnit::files ?what the include resolver recorded —normalized, case folded on Windows
1314/// theirs the compiler's marker ?whatever the compiler decided to print —often verbatim, often `\`-separated
1315/// ```
1316///
1317/// [`crate::file::paths::normalize_path`] is the crate's one answer to "are these two spellings the same file", so
1318/// both halves go through it and the two sets become comparable. Without this every file is
1319/// [`Reason::MissingHeader`] the moment the spellings differ, which is a report that is wrong in the direction that
1320/// matters: it invents a missing header where there is only a missing separator.
1321///
1322/// Case folding is the platform's rule (`cfg!(windows)`), the same one resolution uses, so this cannot disagree with
1323/// the resolver about whether two paths are one file.
1324///
1325/// A `Path` is unsized, so the shared form is an `Arc<PathBuf>`; the point is that this is built **once per file**
1326/// and every token of that file shares it. A comparison of a standard library's closure holds a few million tokens,
1327/// and cloning a path per token is the kind of cost this crate has measured before.
1328pub fn shared(path: &Path) -> Arc<Path> {
1329 Arc::from(normalized(path)) as Arc<Path>
1330}
1331
1332/// [`shared`]'s answer as an owned path —the normalized spelling of `path`, for a caller that has to *compare* two
1333/// paths from the two halves of a comparison rather than carry them.
1334///
1335/// Public because a consumer doing its own comparison (a record file keyed by path, a report grouped by file) needs
1336/// the same answer the streams were built with; a second normalization is how two answers to one question start to
1337/// differ.
1338pub fn normalized(path: &Path) -> PathBuf {
1339 PathBuf::from(crate::file::paths::normalize_path(path, cfg!(windows)))
1340}
1341
1342/// **Where the text of a unit's files comes from**, for turning a rendering into comparable tokens.
1343///
1344/// The same shape [`crate::preprocess::macros::UnitSources`] has, and for the same reason: the caller decides where
1345/// text comes from —a disk provider, an editor's buffers, a test's fixtures —and the conversion must not care.
1346/// A file this cannot read is a file whose tokens get **no line**, which is not the same answer as line 1: an offset
1347/// that cannot be placed is unknown, and a wrong line is a report pointing at the wrong place.
1348pub trait UnitTexts {
1349 /// The text of `path`, when this caller has it, and the line index of that text.
1350 ///
1351 /// Both together because they must agree: a line index is an index *of one text*, and building it here is what
1352 /// makes it impossible for a caller to hand over an index of the previous revision. [`DiskTexts`] reads and
1353 /// indexes in one step for exactly that reason.
1354 fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)>;
1355}
1356
1357/// [`UnitTexts`] over the filesystem, which is what the command-line tool uses.
1358///
1359/// A file that cannot be read is `None` rather than an empty string: the two are different answers to "what is in
1360/// this file", and the empty one would put every token on line 1.
1361#[derive(Debug, Clone, Copy, Default)]
1362pub struct DiskTexts;
1363
1364impl UnitTexts for DiskTexts {
1365 fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)> {
1366 let text = std::fs::read_to_string(path).ok()?;
1367 let lines = cpp_parser::LineIndex::parse(&text);
1368 Some((text, lines))
1369 }
1370}
1371
1372impl UnitTexts for std::collections::HashMap<PathBuf, String> {
1373 fn text_of(&self, path: &Path) -> Option<(String, cpp_parser::LineIndex)> {
1374 let text = self.get(path)?;
1375 Some((text.clone(), cpp_parser::LineIndex::parse(text)))
1376 }
1377}
1378
1379/// **Our rendering as comparable tokens**: the same shape [`tokenize_preprocessed`] produces for a compiler's output.
1380///
1381/// This is the bridge between the two halves of the comparison, and it is the one piece of the tool that is worth
1382/// being in the library rather than in the example —because it is where a subtle mistake would be invisible. Each
1383/// token of a [`crate::RenderedUnit`] carries the file it **stands in** ([`crate::UnitSpan::file`]) and a range in
1384/// that file ([`crate::UnitSpan::written`]), so the bridge to the other side is a **line number**, which needs the
1385/// file's text.
1386///
1387/// # Two things this gets right that are easy to get wrong
1388///
1389/// * **The line comes from `written`, not from `cooked`.** `cooked` is an offset in the *rendering* —a text this
1390/// crate spelled out, whose offsets are not positions in any file (`RenderedCooked`'s documentation is emphatic
1391/// about it). Asking it for a line would number the lines of a text nobody has.
1392/// * **The text is read once per file, before the loop**, not once per token. A standard library header contributes
1393/// thousands of tokens, and a conversion that read the file per token would make the comparison quadratic in file
1394/// size for no reason at all.
1395///
1396/// A file the caller cannot read yields tokens with **no file and no line**, which the classifier reads as "nothing
1397/// is known about where this is" rather than as agreement. That case is real: a rendering can name a file that was
1398/// reached by the walk and never held.
1399pub fn unit_tokens(unit: &crate::RenderedUnit, texts: &dyn UnitTexts) -> Vec<StreamToken> {
1400 // Built once per file, in the rendering's own frame order —the order `UnitSpan::file` indexes.
1401 let held: Vec<Option<HeldFile>> = unit
1402 .files
1403 .iter()
1404 .map(|path| {
1405 texts.text_of(path).map(|(text, lines)| HeldFile {
1406 lines,
1407 text,
1408 path: shared(path),
1409 })
1410 })
1411 .collect();
1412
1413 unit.spans
1414 .iter()
1415 .map(|span| {
1416 let file = held.get(span.file as usize).and_then(Option::as_ref);
1417 StreamToken {
1418 spelling: unit.text[span.cooked.start_offset..span.cooked.end_offset()].into(),
1419 file: file.map(|file| Arc::clone(&file.path)),
1420 line: file.and_then(|file| {
1421 file.lines
1422 .position_of(span.written.start_offset, &file.text)
1423 // Zero-based to one-based, which is what every compiler's line markers use and therefore what
1424 // the other side of the comparison speaks.
1425 .map(|(line, _)| line as u32 + 1)
1426 }),
1427 }
1428 })
1429 .collect()
1430}
1431
1432/// One file of a rendering, read: the text, its line index, and the path its tokens share.
1433struct HeldFile {
1434 lines: cpp_parser::LineIndex,
1435 text: String,
1436 path: Arc<Path>,
1437}
1438
1439#[cfg(test)]
1440mod tests {
1441 use super::*;
1442 use cpp_parser::SourceRange;
1443
1444 /// **The spelling an origin is recorded in.** Case is folded on Windows only — two files that differ in
1445 /// case are one file there and two here — so a test that asserted the folded spelling everywhere would be
1446 /// asserting the Windows rule on a file system that does not have it.
1447 fn as_recorded(path: &str) -> String {
1448 if cfg!(windows) {
1449 path.to_lowercase()
1450 } else {
1451 path.to_string()
1452 }
1453 }
1454
1455 fn plain(spellings: &[&str]) -> Vec<StreamToken> {
1456 spellings
1457 .iter()
1458 .map(|spelling| StreamToken::new(*spelling, None, None))
1459 .collect()
1460 }
1461
1462 fn spelled(stream: &[StreamToken]) -> Vec<&str> {
1463 stream.iter().map(|token| &*token.spelling).collect()
1464 }
1465
1466 /// The reason of the **first** difference at or after `at` —the movement's reason, rather than one edit's.
1467 ///
1468 /// Every difference in a run carries the run's shape ([`Difference::run_ours`], [`Difference::run_theirs`]), so
1469 /// every one of them classifies the same way; taking the first is how a test names a movement instead of an edit.
1470 fn reason_at(alignment: &Alignment, at: usize) -> Reason {
1471 alignment
1472 .differences
1473 .iter()
1474 .find(|difference| difference.at >= at)
1475 .expect("there is a difference at or after this position")
1476 .reason(&Default::default())
1477 }
1478
1479 /// How many **movements** there are: each contiguous run of edits counted once.
1480 ///
1481 /// What a report counts and what a test should assert about, because it is the number that corresponds to work
1482 /// items rather than to diff output.
1483 fn movements(alignment: &Alignment) -> usize {
1484 let mut count = 0usize;
1485 let mut previous: Option<usize> = None;
1486 for difference in &alignment.differences {
1487 if previous != Some(difference.at.wrapping_sub(1)) {
1488 count += 1;
1489 }
1490 previous = Some(difference.at);
1491 }
1492 count
1493 }
1494
1495 /// **Two spellings of one file are one file.** The two halves of a comparison get their paths from different
1496 /// places —ours from the include resolver, theirs from whatever the compiler printed —and the raw spellings do
1497 /// not compare equal. Without normalizing both through
1498 /// [`crate::file::paths::normalize_path`], every such file is classified [`Reason::MissingHeader`]: a report
1499 /// that invents a missing header where there is only a missing separator.
1500 #[test]
1501 fn two_spellings_of_one_path_are_one_file() {
1502 let ours = vec![StreamToken::new(
1503 "x",
1504 Some(shared(Path::new("/p//a.h"))),
1505 Some(1),
1506 )];
1507 let theirs = vec![StreamToken::new(
1508 "x",
1509 Some(shared(Path::new("/p/a.h"))),
1510 Some(1),
1511 )];
1512
1513 let our_files = files_of(&ours);
1514 assert_eq!(
1515 our_files.len(),
1516 1,
1517 "the two spellings collapse to one path: {our_files:?}"
1518 );
1519 assert!(
1520 our_files.contains(Path::new("/p/a.h")),
1521 "and it is the normalized spelling: {our_files:?}"
1522 );
1523
1524 // The comparison therefore agrees, rather than reporting a missing header for the same file.
1525 assert!(
1526 align(&ours, &theirs).agrees(),
1527 "the same file on both sides"
1528 );
1529 }
1530
1531 /// The ordinary case, and the one the plan requires to be reportable as zero: two readings of one file agree.
1532 #[test]
1533 fn two_streams_that_agree_have_no_differences() {
1534 let ours = plain(&["int", "main", "(", ")", "{", "}"]);
1535 let theirs = plain(&["int", "main", "(", ")", "{", "}"]);
1536
1537 let alignment = align(&ours, &theirs);
1538
1539 assert!(alignment.agrees(), "{alignment:?}");
1540 assert_eq!(alignment.matched, 6, "every token is counted as agreed");
1541 assert!(alignment.differences.is_empty());
1542 }
1543
1544 /// A macro that should have been expanded is **one** difference, not a delete plus an insert —the shape a
1545 /// reader can act on.
1546 ///
1547 /// The fixture has no trailing `;` **on purpose**: with one, the diff cannot tell the declaration's semicolon
1548 /// from one the macro produced, so it merges the two into one run and this stops being the isolated case. That is
1549 /// the ambiguity `Difference::run_ours` exists to make visible rather than to hide —see
1550 /// `one_macro_that_expands_to_several_tokens_is_one_movement` for the run's side of it.
1551 #[test]
1552 fn a_name_that_survived_where_the_compiler_expanded_it_is_one_difference() {
1553 let ours = plain(&["int", "x", "=", "VALUE"]);
1554 let theirs = plain(&["int", "x", "=", "42"]);
1555
1556 let alignment = align(&ours, &theirs);
1557
1558 assert_eq!(alignment.matched, 3, "everything but the last token agreed");
1559 assert_eq!(
1560 alignment.differences.len(),
1561 1,
1562 "{:?}",
1563 alignment.differences
1564 );
1565 let difference = &alignment.differences[0];
1566 assert_eq!(
1567 difference.ours.as_ref().map(|it| &*it.spelling),
1568 Some("VALUE")
1569 );
1570 assert_eq!(
1571 difference.theirs.as_ref().map(|it| &*it.spelling),
1572 Some("42")
1573 );
1574 assert_eq!(
1575 difference.at, 3,
1576 "and it is reported where it is in the stream"
1577 );
1578 assert!(difference.is_isolated(), "{difference:?}");
1579 assert_eq!((difference.run_ours, difference.run_theirs), (1, 1));
1580 assert_eq!(
1581 difference.reason(&Default::default()),
1582 Reason::ConditionDisagreement,
1583 "a name against a number: this fixture is exactly that shape"
1584 );
1585 }
1586
1587 /// A stream compared against itself agrees, token for token —the state §5.2 requires to be reachable, so a
1588 /// regression that made it unreachable fails here rather than in a log.
1589 #[test]
1590 fn a_stream_compared_against_itself_is_all_matches() {
1591 let stream = plain(&["#", "define", "FLAG", "1", "int", "n", ";"]);
1592
1593 let alignment = align(&stream, &stream);
1594
1595 assert!(alignment.agrees(), "{alignment:?}");
1596 assert_eq!(alignment.matched, 7);
1597 assert!(alignment.differences.is_empty());
1598 }
1599
1600 /// A whole region on our side and nothing on theirs is **one movement**, not one per token —the count a report
1601 /// prints has to be work items, and a branch that moved forty tokens is one wrongly-decided `#if`.
1602 #[test]
1603 fn a_region_present_on_one_side_only_is_counted_as_one_movement() {
1604 let ours = plain(&["int", "a", ";", "int", "b", ";", "int", "c", ";"]);
1605 let theirs = plain(&["int", "a", ";"]);
1606
1607 let alignment = align(&ours, &theirs);
1608
1609 assert_eq!(
1610 alignment.differences.len(),
1611 6,
1612 "six edits: {:?}",
1613 alignment.differences
1614 );
1615 assert_eq!(movements(&alignment), 1, "and one movement");
1616 assert_eq!(reason_at(&alignment, 3), Reason::BranchDisagreement);
1617 }
1618
1619 /// **The differences come out in stream order**, which is the invariant every consumer of them rests on.
1620 ///
1621 /// This is a regression test for a real bug in the traceback: it walks backwards, so a run of pure deletions was
1622 /// emitted in *descending* order —`["a", "b", "c"]` against `[]` came back as "at 2, at 1, at 0". Everything that
1623 /// reasons about adjacency then saw three movements where the streams moved once, and a report counted one `#if`
1624 /// as three work items. `align` sorts, and this is what says so.
1625 #[test]
1626 fn the_differences_come_out_in_stream_order() {
1627 let ours = plain(&["a", "b", "c", "d"]);
1628
1629 let alignment = align(&ours, &[]);
1630
1631 let positions: Vec<usize> = alignment
1632 .differences
1633 .iter()
1634 .map(|difference| difference.at)
1635 .collect();
1636 assert_eq!(positions, vec![0, 1, 2, 3], "{:?}", alignment.differences);
1637 assert_eq!(
1638 movements(&alignment),
1639 1,
1640 "one region left, not four movements"
1641 );
1642 }
1643
1644 /// **A macro that expands to several tokens is one movement, not two work items.** This is the misclassification
1645 /// the first version of this module produced: read one edit at a time, our `SIZE` says `UnexpandedMacro` and the
1646 /// compiler's `8 * 1024` says `MissingExpansion` —two mechanisms, and neither is what happened.
1647 #[test]
1648 fn one_macro_that_expands_to_several_tokens_is_one_movement() {
1649 let ours = plain(&["int", "n", "=", "SIZE", ";"]);
1650 let theirs = plain(&["int", "n", "=", "8", "*", "1024", ";"]);
1651
1652 let alignment = align(&ours, &theirs);
1653
1654 assert_eq!(
1655 movements(&alignment),
1656 1,
1657 "one macro moved: {:#?}",
1658 alignment.differences
1659 );
1660 assert!(
1661 alignment
1662 .differences
1663 .iter()
1664 .all(|difference| difference.run > 1),
1665 "and every edit of it knows it is part of a run: {:?}",
1666 alignment.differences
1667 );
1668 assert_eq!(
1669 reason_at(&alignment, 3),
1670 Reason::ExpansionDisagreement,
1671 "one token out, three in: a replacement list, not a name that survived"
1672 );
1673 }
1674
1675 /// **A name only we have, in a one-sided run, is a branch and not an unexpanded macro.** One edit at a time these
1676 /// are identical, which is why the run's shape is what gets read.
1677 #[test]
1678 fn a_name_alone_in_a_one_sided_run_is_reported_as_a_region() {
1679 let ours = plain(&["void", "f", "(", ")", "{", "ONLY_HERE", "}", ";"]);
1680 let theirs = plain(&["void", "f", "(", ")", "{", "}", ";"]);
1681
1682 let alignment = align(&ours, &theirs);
1683
1684 assert_eq!(movements(&alignment), 1);
1685 assert_eq!(
1686 reason_at(&alignment, 5),
1687 Reason::UnexpandedMacro,
1688 "one name on our side and nothing where theirs is: {:?}",
1689 alignment.differences
1690 );
1691 }
1692
1693 /// A `#if` decided the other way is a **run** of tokens present on one side only, and the reason names the
1694 /// mechanism rather than the tokens.
1695 #[test]
1696 fn a_branch_taken_on_one_side_only_is_a_run_of_one_sided_differences() {
1697 let ours = plain(&["int", "a", ";", "int", "b", ";"]);
1698 let theirs = plain(&["int", "a", ";"]);
1699
1700 let alignment = align(&ours, &theirs);
1701
1702 assert_eq!(alignment.matched, 3);
1703 assert_eq!(
1704 alignment.differences.len(),
1705 3,
1706 "{:?}",
1707 alignment.differences
1708 );
1709 assert!(
1710 alignment
1711 .differences
1712 .iter()
1713 .all(|difference| difference.theirs.is_none()),
1714 "every difference is ours alone: {:?}",
1715 alignment.differences
1716 );
1717 }
1718
1719 /// A **substitution** is reported as one entry with both sides, which is what makes a report readable: the old
1720 /// pairwise diff produces two entries for the same place.
1721 #[test]
1722 fn a_substitution_is_one_difference_with_both_halves() {
1723 let alignment = align(&plain(&["a", "OLD", "b"]), &plain(&["a", "NEW", "b"]));
1724
1725 assert_eq!(
1726 alignment.differences.len(),
1727 1,
1728 "{:?}",
1729 alignment.differences
1730 );
1731 assert!(
1732 alignment.differences[0].ours.is_some() && alignment.differences[0].theirs.is_some()
1733 );
1734 }
1735
1736 /// An identifier against a number is the fingerprint of `#if` disagreement, and it is the reason
1737 /// `ConditionDisagreement` exists: the two streams chose differently, which is a different work item from a macro
1738 /// that was not expanded.
1739 #[test]
1740 fn a_name_against_a_number_is_classified_as_a_condition_disagreement() {
1741 // One token out, one in, name against number, and nothing else moved —which is what makes it *one* movement
1742 // and not a run. A fixture with a trailing `;` would not: the diff cannot tell the declaration's semicolon
1743 // from one the macro produced, so it would merge the two into a run and read a different reason.
1744 let ours = plain(&["int", "n", "=", "WIDTH"]);
1745 let theirs = plain(&["int", "n", "=", "19"]);
1746
1747 let alignment = align(&ours, &theirs);
1748
1749 assert_eq!(movements(&alignment), 1, "{:?}", alignment.differences);
1750 assert_eq!(reason_at(&alignment, 3), Reason::ConditionDisagreement);
1751 }
1752
1753 /// A token whose file our stream never mentions is a header we never read —certain, not heuristic, which is why
1754 /// it outranks every shape rule.
1755 #[test]
1756 fn a_token_from_a_file_we_never_read_is_a_missing_header() {
1757 let ours = plain(&["int", "x", ";"]);
1758 let theirs = vec![
1759 StreamToken::new("int", Some(shared(Path::new("/p/a.cpp"))), None),
1760 StreamToken::new("helper", Some(shared(Path::new("/missing/header.h"))), None),
1761 StreamToken::new(";", Some(shared(Path::new("/p/a.cpp"))), None),
1762 ];
1763 let our_files = files_of(&ours);
1764
1765 let reason = align(&ours, &theirs).differences[0].reason(&our_files);
1766
1767 assert_eq!(reason, Reason::MissingHeader);
1768 }
1769
1770 /// A name that is the same **name** on the other side is not a condition disagreement: it is one name against
1771 /// another, which is the shape rule 7 leaves `Unknown` rather than guessing at.
1772 #[test]
1773 fn a_name_against_a_name_is_not_a_condition_disagreement() {
1774 let ours = plain(&["int", "n", "=", "WIDTH"]);
1775 let theirs = plain(&["int", "n", "=", "HEIGHT"]);
1776
1777 let alignment = align(&ours, &theirs);
1778
1779 assert_eq!(movements(&alignment), 1);
1780 assert_eq!(
1781 reason_at(&alignment, 3),
1782 Reason::Unknown,
1783 "the diff cannot say which mechanism moved two names: {:?}",
1784 alignment.differences
1785 );
1786 }
1787
1788 /// **The line markers are read, not skipped.** `-E`'s output is a concatenation of every file, and the marker is
1789 /// the only thing that says which one —so a comparison that dropped them could not compare file boundaries at
1790 /// all, which is one of the three things the plan asks this tool to compare.
1791 #[test]
1792 fn the_line_markers_of_a_preprocessed_file_are_read_for_position() {
1793 // The shape both compilers print, with GCC's trailing flags and a quoted path.
1794 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";
1795
1796 let tokens = tokenize_preprocessed(output);
1797
1798 assert_eq!(
1799 spelled(&tokens),
1800 [
1801 "int",
1802 "main",
1803 "(",
1804 ")",
1805 "{",
1806 "}",
1807 "namespace",
1808 "std",
1809 "{",
1810 "}",
1811 "return",
1812 "0",
1813 ";"
1814 ],
1815 "the markers are not tokens: {tokens:?}"
1816 );
1817 assert_eq!(tokens[0].origin(), as_recorded("C:/src/main.cpp:1"));
1818 assert_eq!(
1819 tokens[6].origin(),
1820 as_recorded("C:/inc/xstring:1"),
1821 "the header's own tokens carry the header's name and line: {tokens:?}"
1822 );
1823 assert_eq!(
1824 tokens[11].origin(),
1825 as_recorded("C:/src/main.cpp:7"),
1826 "and the file comes back when the marker says so"
1827 );
1828 }
1829
1830 /// MSVC spells the marker `#line`, and the same reader has to accept it —the two compilers are both oracles and
1831 /// the tool must not need to know which one answered.
1832 ///
1833 /// The path comes back **normalized**, which on Windows means case-folded: `C:/src/main.cpp` is `c:/src/main.cpp`,
1834 /// the same spelling the include resolver records. That is the point of normalizing here rather than at the
1835 /// comparison —see [`shared`] —and the expectation is written for the platform the test is on.
1836 #[test]
1837 fn msvcs_line_marker_spelling_is_read_too() {
1838 let output = "#line 12 \"C:\\\\src\\\\main.cpp\"\nint x ;\n";
1839
1840 let tokens = tokenize_preprocessed(output);
1841
1842 assert_eq!(spelled(&tokens), ["int", "x", ";"]);
1843 assert_eq!(
1844 tokens[0].origin(),
1845 as_recorded("C:/src/main.cpp:12"),
1846 "{tokens:?}"
1847 );
1848 }
1849
1850 /// **A path with a backslash that is not a C escape keeps its backslash, and is normalized like every other
1851 /// path.** `cl` doubles its separators, but a marker's path is not required to be a well-formed C string and a
1852 /// compiler is free to print `C:\Users\zc\src` — in which `\U`, `\z` and `\s` are not escapes at all.
1853 ///
1854 /// The first version of `unquote` dropped the backslash, turning that into `C:Userszcsrc`: a path that does not
1855 /// exist but *looks* like one, so a report would point at a file a reader might believe. The separators are
1856 /// therefore kept; unifying them (and folding case on Windows) is [`shared`]'s job, and the assertion below is
1857 /// the two together.
1858 #[test]
1859 fn a_windows_path_that_is_not_a_c_string_keeps_its_backslashes() {
1860 let output = "# 1 \"C:\\work\\src\\main.cpp\"\nint x ;\n";
1861
1862 let tokens = tokenize_preprocessed(output);
1863
1864 // The separators are unified rather than dropped: `C:Userszcsrc` is what the bug produced, and this is not
1865 // that.
1866 assert_eq!(
1867 tokens[0].origin(),
1868 as_recorded("C:/work/src/main.cpp:1"),
1869 "the path survives with its separators, in the spelling comparisons are made in: {tokens:?}"
1870 );
1871 }
1872
1873 /// **A `#pragma` line is not a marker.** It survives `-E` precisely because it is meaningful to whatever reads
1874 /// the output, and a comparison that dropped every `#`-leading line would stop noticing a `#pragma once` this
1875 /// reading got wrong.
1876 #[test]
1877 fn a_pragma_line_survives_as_tokens() {
1878 let output = "#pragma once\nint x ;\n";
1879
1880 let tokens = tokenize_preprocessed(output);
1881
1882 assert_eq!(spelled(&tokens), ["#", "pragma", "once", "int", "x", ";"]);
1883 }
1884
1885 /// Comments and layout are dropped, because the other side of the comparison has neither: our stream is a
1886 /// rendering with one space between tokens. Comparing them would make every run differ on nothing.
1887 #[test]
1888 fn comments_and_layout_are_not_part_of_the_comparison() {
1889 let tokens = tokenize_preprocessed("int /* why */ x ;\n// and\nint y ;");
1890
1891 assert_eq!(spelled(&tokens), ["int", "x", ";", "int", "y", ";"]);
1892 }
1893
1894 /// **The bound is reported, not hidden.** Two streams with nothing in common have a difference count proportional
1895 /// to their length; a report that presented a truncated comparison as a whole would be the exact kind of silent
1896 /// overclaim the plan's rule 3 forbids.
1897 #[test]
1898 fn a_comparison_that_ran_out_of_budget_says_so() {
1899 let ours: Vec<StreamToken> = (0..MAX_EDIT_DISTANCE + 200)
1900 .map(|at| StreamToken::new(format!("left{at}"), None, None))
1901 .collect();
1902 let theirs: Vec<StreamToken> = (0..MAX_EDIT_DISTANCE + 200)
1903 .map(|at| StreamToken::new(format!("right{at}"), None, None))
1904 .collect();
1905
1906 let alignment = align(&ours, &theirs);
1907
1908 assert!(
1909 alignment.truncated,
1910 "an unbounded diff must report that it stopped"
1911 );
1912 assert!(
1913 !alignment.agrees(),
1914 "and must not be mistaken for agreement"
1915 );
1916 }
1917
1918 /// **The report's counts are the numbers the plan requires to be monotone**, so they are what a test asserts
1919 /// about rather than the rendered text. The composition is asserted exactly: a total alone would pass while the
1920 /// mechanisms were mixed up, which is the failure this classification exists to prevent.
1921 ///
1922 /// The three movements are what the classifier has to tell apart, and this is the shape each one has. Two movements that touch
1923 /// are one run as far as a diff can tell —a replacement list substituted for a name and an extra token right
1924 /// after it are indistinguishable from one macro that produced both —so a fixture that wants three reasons has
1925 /// to make three runs, and a run ends where the streams agree again.
1926 #[test]
1927 fn the_report_counts_differences_by_mechanism() {
1928 let ours = plain(&[
1929 "int", "n", "=", "WIDTH", ";", // a name where the compiler has a number
1930 ";", "EXTRA", ";", // ours alone, and it costs one token
1931 ";", "A", "B", // ours alone, and it costs two
1932 ]);
1933 let theirs = plain(&[
1934 "int", "n", "=", "19", ";", //
1935 ";", ";", //
1936 ";", "C", //
1937 ]);
1938
1939 let report = Report::of(&ours, &theirs);
1940
1941 assert_eq!((report.ours, report.theirs), (11, 9));
1942 assert!(!report.agrees());
1943 assert!(!report.truncated, "a handful of edits: {report:?}");
1944
1945 let mut counted = report.by_reason.clone();
1946 counted.sort_by_key(|(reason, _)| format!("{reason:?}"));
1947 assert_eq!(
1948 counted,
1949 vec![
1950 (Reason::ConditionDisagreement, 1),
1951 (Reason::ExpansionDisagreement, 2),
1952 (Reason::UnexpandedMacro, 1),
1953 ],
1954 "one movement each, counted where it belongs: {report:?}"
1955 );
1956 assert!(
1957 report.render().contains("by mechanism"),
1958 "{}",
1959 report.render()
1960 );
1961 }
1962
1963 /// A report of two streams that agree says so, and carries no differences at all —the state §5.2 requires to be
1964 /// reachable, so a regression that made it unreachable would fail here rather than in a log.
1965 #[test]
1966 fn a_report_of_two_agreeing_streams_says_so() {
1967 let report = Report::of(&plain(&["a", "b"]), &plain(&["a", "b"]));
1968
1969 assert!(report.agrees());
1970 assert!(report.render().contains("agree"), "{}", report.render());
1971 }
1972
1973 /// **[`unit_tokens`] reads a line from the file the token was written in**, not from the rendering's own text.
1974 ///
1975 /// This is the piece of the bridge that a mistake would hide in: `UnitSpan::cooked` is an offset in a text this
1976 /// crate spelled out, and asking it for a line would number the lines of a text nobody has. The fixture is built
1977 /// so the two could not be confused —the rendering puts one token per line, while the file's own text has them
1978 /// spread over five lines with the interesting ones on 4 and 5.
1979 ///
1980 /// The `written` offsets are the **real ones in `text`**, which is the whole point of the fixture: `c` is at byte
1981 /// 14 and not at 12, because 12 is the `int` of that line. An offset that is right for the wrong reason would
1982 /// make this test pass while the mapping it checks was broken.
1983 #[test]
1984 fn our_tokens_take_their_line_from_the_file_not_from_the_rendering() {
1985 let file = "/p/a.h";
1986 // Line 1 blank, then `int a;` on 2, `int b;` on 3, `int c;` on 4, `int d;` on 5.
1987 let text = "\nint a;\nint b;\nint c;\nint d;\n";
1988
1989 let mut unit = crate::RenderedUnit {
1990 files: vec![PathBuf::from(file)],
1991 file_lengths: vec![text.len()],
1992 ..crate::RenderedUnit::default()
1993 };
1994 // The rendering is a flat line of tokens —a different text, with different offsets, on purpose.
1995 unit.push("int", 0, SourceRange::new(1, 3));
1996 unit.push("a", 0, SourceRange::new(5, 1));
1997 unit.push("int", 0, SourceRange::new(8, 3));
1998 unit.push("c", 0, SourceRange::new(19, 1));
1999
2000 let texts: std::collections::HashMap<PathBuf, String> =
2001 [(PathBuf::from(file), text.to_string())]
2002 .into_iter()
2003 .collect();
2004 let tokens = unit_tokens(&unit, &texts);
2005
2006 let placed: Vec<(&str, u32)> = tokens
2007 .iter()
2008 .map(|token| {
2009 (
2010 &*token.spelling,
2011 token.line.expect("the file's text was given"),
2012 )
2013 })
2014 .collect();
2015 assert_eq!(
2016 placed,
2017 vec![("int", 2), ("a", 2), ("int", 3), ("c", 4)],
2018 "each token's line is where the file wrote it: {tokens:?}"
2019 );
2020 assert_eq!(
2021 tokens[0].file.as_deref(),
2022 Some(Path::new(file)),
2023 "and its file is the one it stands in"
2024 );
2025 }
2026
2027 /// A file the caller has no text for yields tokens with **no position**, not with line 1 —the difference between
2028 /// "unknown" and a report that points at the wrong line.
2029 #[test]
2030 fn a_file_nobody_has_the_text_of_yields_tokens_with_no_position() {
2031 let mut unit = crate::RenderedUnit {
2032 files: vec![PathBuf::from("/p/a.h")],
2033 file_lengths: vec![0],
2034 ..crate::RenderedUnit::default()
2035 };
2036 unit.push("x", 0, SourceRange::new(0, 1));
2037
2038 let tokens = unit_tokens(&unit, &std::collections::HashMap::<PathBuf, String>::new());
2039
2040 assert_eq!(tokens.len(), 1);
2041 assert!(tokens[0].file.is_none(), "{tokens:?}");
2042 assert!(tokens[0].line.is_none(), "{tokens:?}");
2043 assert_eq!(
2044 tokens[0].origin(),
2045 "?",
2046 "and the report says so rather than guessing"
2047 );
2048 }
2049}