Skip to main content

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}