rust_doctor/
delta.rs

1//! Which findings a branch introduced, which it inherited, and which it fixed.
2//!
3//! A baseline comparison is a multiset pairing between two independent
4//! scans, and the only thing it may not do is guess. Two diagnostics are the
5//! same finding when the code under them is the same code, so the identity this
6//! module builds is evidence first: the normalized source excerpt the span
7//! covers, hashed with the rule and the message. What a report publishes is not
8//! enough on its own, since a line number moves on every edit above it and a
9//! message states counts that the next commit changes.
10//!
11//! Four rules hold it together.
12//!
13//! A candidate is a diagnostic, not a row beside one. `Candidate` borrows the
14//! `Diagnostic` it speaks for, so the pairing cannot drift out of step with
15//! the report it is computed from. The two index-parallel slices it replaced
16//! were passed to the matcher as four separate arguments, kept aligned by
17//! nothing but the reader's attention, and every one of the ten places that
18//! walked them indexed a slice a length mismatch would have panicked on, in a
19//! crate that denies `panic`.
20//!
21//! Every pass is named, and the pass says what a match on it means. The four
22//! passes used to be four calls carrying six anonymous closures, two of them
23//! identical word for word, and a trailing positional `bool` announcing that the
24//! match was a move. Nothing tied that flag to the key: the key of the last
25//! pass omits the path, and `cross_file` said so a second time, so the count
26//! the report publishes could disagree with the pairing that produced it.
27//! The count is now the length of what the moved pass returned.
28//!
29//! A bound is a budget on work, never a filter on meaning. `SOURCE_BYTES_BUDGET`
30//! bounds what one comparison may read, `PROOF_BYTES_BUDGET` what it may
31//! normalize, `SOURCE_FILE_BYTES_LIMIT` and `PROOF_BYTES_LIMIT` what one file
32//! and one excerpt may contribute, and none of them decides which finding is
33//! matchable: a diagnostic whose evidence is out of budget falls back to its
34//! message rather than disappearing. The two budgets used to share one constant
35//! named for neither.
36//!
37//! The stage a failure names is this one. Refusing a comparison over
38//! `DIAGNOSTIC_LIMIT` diagnostics used to be reported with the git baseline's
39//! own failure, so a run that hit the diagnostic ceiling published
40//! `stage: "baseline"` and told the reader their snapshot exceeded a limit,
41//! which was true of nothing.
42
43use std::collections::{BTreeMap, VecDeque};
44use std::fs::{self, File};
45use std::io::Read;
46use std::path::{Path, PathBuf};
47
48use serde::Serialize;
49
50use crate::internal_error::InternalError;
51use crate::policy::Producer;
52use crate::report::{Diagnostic, DiagnosticSource, DiagnosticSpan};
53use crate::workspace_path;
54
55const STAGE: &str = "delta";
56pub(crate) const FINGERPRINT_VERSION: u8 = 1;
57pub(crate) const DIAGNOSTIC_LIMIT: usize = 50_000;
58const PROOF_BYTES_LIMIT: usize = 65_536;
59const SOURCE_FILE_BYTES_LIMIT: usize = 8 * 1024 * 1024;
60const SOURCE_BYTES_BUDGET: usize = 64 * 1024 * 1024;
61const PROOF_BYTES_BUDGET: usize = 64 * 1024 * 1024;
62const FINGERPRINT_DOMAIN: &str = "rust-doctor-delta-fingerprint-v1";
63
64#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
65pub struct DeltaReport {
66    pub fingerprint_version: u8,
67    pub base_diagnostics: usize,
68    pub current_diagnostics: usize,
69    pub introduced: Vec<String>,
70    pub pre_existing: Vec<DeltaMatch>,
71    pub fixed: Vec<Diagnostic>,
72    pub summary: DeltaSummary,
73}
74
75#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
76pub struct DeltaMatch {
77    pub current_id: String,
78    pub baseline_id: String,
79}
80
81#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
82pub struct DeltaSummary {
83    pub introduced: usize,
84    pub pre_existing: usize,
85    pub fixed: usize,
86    pub cross_file_matches: usize,
87}
88
89#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
90struct DeltaFingerprintV1([u8; 32]);
91
92/// What identifies a diagnostic when no proof could be read for it.
93///
94/// It borrows the diagnostic rather than copying it: a key lives for one pass
95/// and the diagnostics outlive every pass, so the four passes used to clone the
96/// message of every finding on both sides for nothing.
97#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
98struct FallbackKey<'a> {
99    source: DiagnosticSource,
100    code: Option<&'a str>,
101    message: &'a str,
102}
103
104/// One diagnostic and the strongest identity that could be built for it.
105#[derive(Debug)]
106struct Candidate<'a> {
107    diagnostic: &'a Diagnostic,
108    fingerprint: Option<DeltaFingerprintV1>,
109}
110
111impl<'a> Candidate<'a> {
112    fn new(diagnostic: &'a Diagnostic) -> Self {
113        Self {
114            diagnostic,
115            fingerprint: structural_identity(diagnostic).map(structural_fingerprint),
116        }
117    }
118
119    fn path(&self) -> Option<&'a str> {
120        self.diagnostic.path.as_deref()
121    }
122
123    fn fallback(&self) -> FallbackKey<'a> {
124        FallbackKey {
125            source: self.diagnostic.source,
126            code: self.diagnostic.code.as_deref(),
127            message: self.diagnostic.message.as_str(),
128        }
129    }
130}
131
132#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
133struct SourcePosition {
134    line: usize,
135    column: usize,
136}
137
138/// Where every line of a source file starts.
139///
140/// A span reports a 1-based line and a 1-based character column, and turning
141/// that into a byte offset is the only arithmetic the evidence needs. Building
142/// the index once per file answers every span of that file, which is what the
143/// sorted, deduplicated position set and the peekable state machine it replaced
144/// did at three functions and a helper mutating two collections at once.
145struct LineIndex(Vec<usize>);
146
147impl LineIndex {
148    fn of(source: &str) -> Self {
149        Self(
150            std::iter::once(0)
151                .chain(source.match_indices('\n').map(|(index, _)| index + 1))
152                .collect(),
153        )
154    }
155
156    /// Byte offset of a reported position, absent when the file does not reach
157    /// it.
158    ///
159    /// A line owns its terminator, so the column of the `\n` is the last one a
160    /// line answers. The position one past the final character of the file is
161    /// answered too, because that is what a span covering the last line of a
162    /// file with no trailing newline reports.
163    fn offset(&self, source: &str, position: SourcePosition) -> Option<usize> {
164        let start = *self.0.get(position.line.checked_sub(1)?)?;
165        let next_line = self.0.get(position.line).copied();
166        let line = source.get(start..next_line.unwrap_or(source.len()))?;
167        let column = position.column.checked_sub(1)?;
168        match line.char_indices().nth(column) {
169            Some((offset, _)) => start.checked_add(offset),
170            None if next_line.is_none() && column == line.chars().count() => Some(source.len()),
171            None => None,
172        }
173    }
174}
175
176/// Reads the scanned sources one comparison is allowed to read, and stamps the
177/// candidates it could build a proof for.
178struct EvidenceLoader {
179    root: Option<PathBuf>,
180    source_bytes_read: usize,
181    proof_bytes: usize,
182}
183
184impl EvidenceLoader {
185    fn new(root: &Path) -> Self {
186        Self {
187            root: root.canonicalize().ok(),
188            source_bytes_read: 0,
189            proof_bytes: 0,
190        }
191    }
192
193    fn populate<'a>(&mut self, candidates: &mut [Candidate<'a>]) {
194        let Some(root) = self.root.clone() else {
195            return;
196        };
197        let mut by_path = BTreeMap::<&'a str, Vec<usize>>::new();
198        for (index, candidate) in candidates.iter().enumerate() {
199            // A diagnostic that already carries an identity of its own needs no
200            // excerpt, and reading one for it would spend the evidence budget on
201            // a fingerprint it is not going to use.
202            if candidate.fingerprint.is_none()
203                && candidate.diagnostic.span.is_some()
204                && let Some(path) = candidate.path()
205            {
206                by_path.entry(path).or_default().push(index);
207            }
208        }
209
210        for (path, indexes) in by_path {
211            let Some(source) = self.read_source(&root, path) else {
212                continue;
213            };
214            let lines = LineIndex::of(&source);
215            for index in indexes {
216                let Some(diagnostic) = candidates.get(index).map(|candidate| candidate.diagnostic)
217                else {
218                    continue;
219                };
220                let Some(span) = diagnostic.span.as_ref() else {
221                    continue;
222                };
223                let Some(proof) = self.proof(&source, &lines, span) else {
224                    continue;
225                };
226                let fingerprint = stable_fingerprint(diagnostic, &proof);
227                if let Some(candidate) = candidates.get_mut(index) {
228                    candidate.fingerprint = Some(fingerprint);
229                }
230            }
231        }
232    }
233
234    fn read_source(&mut self, root: &Path, logical_path: &str) -> Option<String> {
235        let relative = workspace_path::decode_normalized_relative(logical_path)?;
236        let path = root.join(relative).canonicalize().ok()?;
237        if !path.starts_with(root) {
238            return None;
239        }
240        // Opening a path that is not a regular file is not merely useless:
241        // opening a named pipe blocks in the call itself, before any check on
242        // the handle could reject it.
243        let metadata = fs::symlink_metadata(&path).ok()?;
244        let length = usize::try_from(metadata.len()).ok()?;
245        if !metadata.is_file()
246            || length > SOURCE_FILE_BYTES_LIMIT
247            || self.source_bytes_read.checked_add(length)? > SOURCE_BYTES_BUDGET
248        {
249            return None;
250        }
251        self.source_bytes_read = self.source_bytes_read.checked_add(length)?;
252
253        // Canonicalizing and then opening has a replacement race, and the code
254        // frame closes it the same way: open the checked path, then confirm the
255        // handle and the live path still identify one file inside the workspace.
256        let file = File::open(&path).ok()?;
257        let opened = file.metadata().ok()?;
258        let revalidated = path.canonicalize().ok()?;
259        if !opened.is_file()
260            || !revalidated.starts_with(root)
261            || !workspace_path::same_file(&opened, &fs::metadata(&revalidated).ok()?)
262        {
263            return None;
264        }
265
266        let mut source = String::with_capacity(length);
267        file.take(SOURCE_FILE_BYTES_LIMIT as u64)
268            .read_to_string(&mut source)
269            .ok()?;
270        (source.len() == length).then_some(source)
271    }
272
273    fn proof(&mut self, source: &str, lines: &LineIndex, span: &DiagnosticSpan) -> Option<String> {
274        let remaining = PROOF_BYTES_BUDGET.checked_sub(self.proof_bytes)?;
275        if remaining == 0 {
276            return None;
277        }
278        let proof = extract_proof(source, lines, span, remaining)?;
279        self.proof_bytes = self.proof_bytes.checked_add(proof.len())?;
280        Some(proof)
281    }
282}
283
284pub(crate) fn compute(
285    baseline: &[Diagnostic],
286    current: &[Diagnostic],
287    baseline_root: &Path,
288    current_root: &Path,
289) -> Result<DeltaReport, InternalError> {
290    if baseline.len() > DIAGNOSTIC_LIMIT || current.len() > DIAGNOSTIC_LIMIT {
291        return Err(limit_exceeded());
292    }
293
294    let baseline_candidates = candidates(baseline, baseline_root);
295    let current_candidates = candidates(current, current_root);
296    Ok(match_candidates(&baseline_candidates, &current_candidates))
297}
298
299fn limit_exceeded() -> InternalError {
300    InternalError::new(
301        STAGE,
302        "delta-limit-exceeded",
303        format!("Baseline comparison exceeds {DIAGNOSTIC_LIMIT} diagnostics on one side."),
304    )
305}
306
307fn candidates<'a>(diagnostics: &'a [Diagnostic], root: &Path) -> Vec<Candidate<'a>> {
308    let mut candidates = diagnostics.iter().map(Candidate::new).collect::<Vec<_>>();
309    EvidenceLoader::new(root).populate(&mut candidates);
310    candidates
311}
312
313/// The identity a structural finding already publishes, when the diagnostic is
314/// one.
315///
316/// A structural finding is a family, and the identity the structural pass
317/// computes for it is the normalized content of that family: no span, no path,
318/// no measured count. That is what a pairing needs here, and it is what the
319/// message and the source excerpt below cannot give, because every structural
320/// message states a number the next edit moves: the line count of a file, the
321/// occurrence count of a clone family, the two complexity figures of a hotspot.
322/// Matched on those, a finding older than the branch reads as introduced by it,
323/// and the one it replaced reads as fixed.
324fn structural_identity(diagnostic: &Diagnostic) -> Option<&str> {
325    let definition = crate::policy::find(diagnostic.code.as_deref()?)?;
326    matches!(definition.producer, Producer::Structure).then_some(diagnostic.id.as_str())
327}
328
329fn structural_fingerprint(identity: &str) -> DeltaFingerprintV1 {
330    let mut hasher = blake3::Hasher::new();
331    hash_field(&mut hasher, FINGERPRINT_DOMAIN.as_bytes());
332    hash_field(&mut hasher, b"structure");
333    hash_field(&mut hasher, identity.as_bytes());
334    DeltaFingerprintV1(*hasher.finalize().as_bytes())
335}
336
337fn stable_fingerprint(diagnostic: &Diagnostic, proof: &str) -> DeltaFingerprintV1 {
338    let mut hasher = blake3::Hasher::new();
339    hash_field(&mut hasher, FINGERPRINT_DOMAIN.as_bytes());
340    hash_field(&mut hasher, diagnostic.source.as_str().as_bytes());
341    match diagnostic.code.as_deref() {
342        Some(code) => {
343            hasher.update(&[1]);
344            hash_field(&mut hasher, code.as_bytes());
345        }
346        None => {
347            hasher.update(&[0]);
348        }
349    }
350    hash_field(&mut hasher, diagnostic.message.as_bytes());
351    hash_field(&mut hasher, proof.as_bytes());
352    DeltaFingerprintV1(*hasher.finalize().as_bytes())
353}
354
355fn hash_field(hasher: &mut blake3::Hasher, value: &[u8]) {
356    hasher.update(&(value.len() as u64).to_le_bytes());
357    hasher.update(value);
358}
359
360fn extract_proof(
361    source: &str,
362    lines: &LineIndex,
363    span: &DiagnosticSpan,
364    remaining_budget: usize,
365) -> Option<String> {
366    let start = lines.offset(
367        source,
368        SourcePosition {
369            line: span.line_start,
370            column: span.column_start,
371        },
372    )?;
373    let end = lines.offset(
374        source,
375        SourcePosition {
376            line: span.line_end,
377            column: span.column_end,
378        },
379    )?;
380    if start > end || end.checked_sub(start)? > PROOF_BYTES_LIMIT {
381        return None;
382    }
383    normalize_proof(source.get(start..end)?, remaining_budget)
384}
385
386/// The excerpt reduced to its words, so reindenting a block does not read as
387/// rewriting it.
388///
389/// The budget is checked as the excerpt is built rather than measured first and
390/// built again: an excerpt that overruns answers `None` either way, and the
391/// caller has already bounded the input at `PROOF_BYTES_LIMIT`.
392fn normalize_proof(source: &str, remaining_budget: usize) -> Option<String> {
393    let bound = remaining_budget.min(PROOF_BYTES_LIMIT);
394    let mut normalized = String::with_capacity(source.len().min(bound));
395    for segment in source.split_whitespace() {
396        let separator = usize::from(!normalized.is_empty());
397        if normalized.len() + separator + segment.len() > bound {
398            return None;
399        }
400        if separator == 1 {
401            normalized.push(' ');
402        }
403        normalized.push_str(segment);
404    }
405    (!normalized.is_empty()).then_some(normalized)
406}
407
408/// Same file, same proof: the finding did not move and the code under it did
409/// not change.
410fn same_path_stable<'a>(
411    candidate: &Candidate<'a>,
412) -> Option<(Option<&'a str>, DeltaFingerprintV1)> {
413    Some((candidate.path(), candidate.fingerprint?))
414}
415
416/// Same file, same message, from a side that has no proof to offer.
417fn same_path_unproven<'a>(candidate: &Candidate<'a>) -> Option<(Option<&'a str>, FallbackKey<'a>)> {
418    candidate
419        .fingerprint
420        .is_none()
421        .then(|| (candidate.path(), candidate.fallback()))
422}
423
424/// Same file, same message, from a side that does carry a proof.
425fn same_path_proven<'a>(candidate: &Candidate<'a>) -> Option<(Option<&'a str>, FallbackKey<'a>)> {
426    candidate
427        .fingerprint
428        .is_some()
429        .then(|| (candidate.path(), candidate.fallback()))
430}
431
432/// Same file, same message, whatever proof the side carries.
433fn same_path_fallback<'a>(candidate: &Candidate<'a>) -> Option<(Option<&'a str>, FallbackKey<'a>)> {
434    Some((candidate.path(), candidate.fallback()))
435}
436
437/// Same proof, any file: the finding moved.
438fn moved_stable(candidate: &Candidate<'_>) -> Option<DeltaFingerprintV1> {
439    candidate.fingerprint
440}
441
442fn match_candidates(baseline: &[Candidate<'_>], current: &[Candidate<'_>]) -> DeltaReport {
443    let mut matching = Matching::new(baseline, current);
444
445    // A finding whose file and whose proof are both unchanged is the same
446    // finding. Nothing weaker is consulted while a pairing this strong is
447    // available, which is what keeps a copied line from consuming the original.
448    matching.pass(same_path_stable, same_path_stable);
449    // From here at least one side has no proof, so the message is all there is.
450    // The proofless baselines are spent first, which reserves a baseline that
451    // does carry a proof for a current that carries one too.
452    matching.pass(same_path_unproven, same_path_proven);
453    matching.pass(same_path_fallback, same_path_unproven);
454    // Same proof in another file: the finding moved. It runs last, so a message
455    // match on the original file wins over a proof match elsewhere. That is a
456    // product decision rather than a consequence, and
457    // `a_message_match_on_the_original_file_wins_over_a_moved_proof` is the
458    // input that puts the two in competition.
459    let moved = matching.pass(moved_stable, moved_stable);
460
461    debug_assert!(
462        moved.iter().all(|&(baseline_index, current_index)| {
463            baseline.get(baseline_index).map(Candidate::path)
464                != current.get(current_index).map(Candidate::path)
465        }),
466        "same-path stable candidates must be exhausted before cross-file matching"
467    );
468    matching.into_report(moved.len())
469}
470
471/// The state of one pairing: which baseline candidates are spent, and which
472/// baseline each current candidate was paired with.
473struct Matching<'a, 'd> {
474    baseline: &'a [Candidate<'d>],
475    current: &'a [Candidate<'d>],
476    consumed: Vec<bool>,
477    matched: Vec<Option<usize>>,
478}
479
480impl<'a, 'd> Matching<'a, 'd> {
481    fn new(baseline: &'a [Candidate<'d>], current: &'a [Candidate<'d>]) -> Self {
482        Self {
483            baseline,
484            current,
485            consumed: vec![false; baseline.len()],
486            matched: vec![None; current.len()],
487        }
488    }
489
490    /// Pairs what is still free on the key the two sides answer on, in index
491    /// order, and returns the pairs it made.
492    ///
493    /// A side that answers `None` sits the pass out. Both sides are walked in
494    /// index order and equal keys queue, so the same two scans always produce
495    /// the same pairing.
496    fn pass<Key: Ord>(
497        &mut self,
498        baseline_key: impl Fn(&Candidate<'d>) -> Option<Key>,
499        current_key: impl Fn(&Candidate<'d>) -> Option<Key>,
500    ) -> Vec<(usize, usize)> {
501        let (baseline, current) = (self.baseline, self.current);
502        let mut available = BTreeMap::<Key, VecDeque<usize>>::new();
503        for (index, candidate) in baseline.iter().enumerate() {
504            if self.consumed.get(index).is_some_and(|consumed| !consumed)
505                && let Some(key) = baseline_key(candidate)
506            {
507                available.entry(key).or_default().push_back(index);
508            }
509        }
510
511        let mut made = Vec::new();
512        for (current_index, candidate) in current.iter().enumerate() {
513            if self.matched.get(current_index).is_none_or(Option::is_some) {
514                continue;
515            }
516            let Some(key) = current_key(candidate) else {
517                continue;
518            };
519            let Some(baseline_index) = available.get_mut(&key).and_then(VecDeque::pop_front) else {
520                continue;
521            };
522            if let Some(consumed) = self.consumed.get_mut(baseline_index) {
523                *consumed = true;
524            }
525            if let Some(matched) = self.matched.get_mut(current_index) {
526                *matched = Some(baseline_index);
527            }
528            made.push((baseline_index, current_index));
529        }
530        made
531    }
532
533    fn into_report(self, cross_file_matches: usize) -> DeltaReport {
534        let introduced = self
535            .current
536            .iter()
537            .zip(&self.matched)
538            .filter(|(_, matched)| matched.is_none())
539            .map(|(candidate, _)| candidate.diagnostic.id.clone())
540            .collect::<Vec<_>>();
541        let pre_existing = self
542            .current
543            .iter()
544            .zip(&self.matched)
545            .filter_map(|(candidate, matched)| {
546                Some(DeltaMatch {
547                    current_id: candidate.diagnostic.id.clone(),
548                    baseline_id: self.baseline.get((*matched)?)?.diagnostic.id.clone(),
549                })
550            })
551            .collect::<Vec<_>>();
552        let fixed = self
553            .baseline
554            .iter()
555            .zip(&self.consumed)
556            .filter(|(_, consumed)| !**consumed)
557            .map(|(candidate, _)| candidate.diagnostic.clone())
558            .collect::<Vec<_>>();
559
560        DeltaReport {
561            fingerprint_version: FINGERPRINT_VERSION,
562            base_diagnostics: self.baseline.len(),
563            current_diagnostics: self.current.len(),
564            summary: DeltaSummary {
565                introduced: introduced.len(),
566                pre_existing: pre_existing.len(),
567                fixed: fixed.len(),
568                cross_file_matches,
569            },
570            introduced,
571            pre_existing,
572            fixed,
573        }
574    }
575}
576
577#[cfg(test)]
578mod tests;
rust_doctor/delta.rs

rust_doctor/
delta.rs
