skif-core 0.2.0

//! Deterministic collection of diagnostics with summary counts.

use std::cmp::Ordering;
use std::path::{Path, PathBuf};

use serde::{Deserialize, Serialize};

use crate::diagnostic::Diagnostic;
use crate::incomplete::IncompletePackage;
use crate::rule::Severity;

/// Aggregate counts over a report.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
#[non_exhaustive]
pub struct Summary {
    /// Diagnostics with [`Severity::Error`].
    pub errors: usize,
    /// Diagnostics with [`Severity::Warning`].
    pub warnings: usize,
    /// Diagnostics with [`Severity::Info`].
    pub infos: usize,
    /// Diagnostics that carry at least one fix.
    pub fixable: usize,
    /// Number of packages that were checked.
    pub packages: usize,
}

/// The complete result of a lint run.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "kebab-case")]
#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
#[non_exhaustive]
pub struct Report {
    /// Diagnostics sorted by path, span start, rule and message.
    pub diagnostics: Vec<Diagnostic>,
    /// Counts over `diagnostics`.
    pub summary: Summary,
    /// Packages whose entry files are not all known, so their files and dependencies were not judged unused; sorted
    /// by directory.
    #[serde(default, skip_serializing_if = "Vec::is_empty")]
    pub incomplete_packages: Vec<IncompletePackage>,
    /// Files of other projects (a directory below a package that holds a `package.json` of its own, such as a nested
    /// root) that the analysed code imports, relative to the workspace root and sorted. The run does not judge them;
    /// a multi-root host hands them to the root that owns them as extra entries
    /// (see `RunOptions::with_extra_entries` of the `skif` crate). Not rendered.
    #[serde(skip)]
    pub other_project_files: Vec<PathBuf>,
}

impl Report {
    /// Sorts `diagnostics` deterministically and computes the summary; `packages` is the number of packages checked.
    #[must_use]
    pub fn new(mut diagnostics: Vec<Diagnostic>, packages: usize) -> Self {
        sort(&mut diagnostics);
        let summary = diagnostics.iter().fold(
            Summary {
                packages,
                ..Summary::default()
            },
            count,
        );
        Self {
            diagnostics,
            summary,
            incomplete_packages: Vec::new(),
            other_project_files: Vec::new(),
        }
    }

    /// Sets the packages whose files and dependencies were not judged, sorted by directory then name.
    #[must_use]
    pub fn with_incomplete_packages(mut self, mut packages: Vec<IncompletePackage>) -> Self {
        packages.sort_by(|a, b| a.dir.cmp(&b.dir).then_with(|| a.name.cmp(&b.name)));
        self.incomplete_packages = packages;
        self
    }

    /// Sets the files of other projects the analysed code imports, sorted and without duplicates.
    #[must_use]
    pub fn with_other_project_files(mut self, mut files: Vec<PathBuf>) -> Self {
        files.sort();
        files.dedup();
        self.other_project_files = files;
        self
    }
}

/// Sorts `diagnostics` stably by path, span start, rule and message, exactly as a stable sort by [`compare`] would.
///
/// A report can hold tens of thousands of diagnostics of a few hundred bytes each, about a few thousand files. So the
/// order is worked out on indices, each distinct path is ranked once instead of being compared at every step, and the
/// diagnostics are then moved into place by swaps: sorting the diagnostics themselves moved each several times and
/// needed a scratch copy of the whole vector.
fn sort(diagnostics: &mut [Diagnostic]) {
    // Neighbours mostly share a file: each run of one path is ranked once.
    let mut runs: Vec<&Path> = Vec::new();
    let mut run_of: Vec<usize> = Vec::with_capacity(diagnostics.len());
    for diagnostic in diagnostics.iter() {
        let path = diagnostic.location.path.as_path();
        if runs.last().is_none_or(|last| last.as_os_str() != path.as_os_str()) {
            runs.push(path);
        }
        run_of.push(runs.len() - 1);
    }
    let mut by_path: Vec<usize> = (0..runs.len()).collect();
    if runs.iter().all(|path| is_plain(path)) {
        by_path.sort_unstable_by(|&a, &b| plain_cmp(runs[a], runs[b]));
    } else {
        by_path.sort_unstable_by(|&a, &b| runs[a].cmp(runs[b]));
    }
    // Equal paths share a rank: `Path` equality is by component, as its order is.
    let mut rank_of_run = vec![0_u32; runs.len()];
    let mut rank = 0_u32;
    for (index, &run) in by_path.iter().enumerate() {
        if index > 0 && runs[by_path[index - 1]] != runs[run] {
            rank += 1;
        }
        rank_of_run[run] = rank;
    }
    let keys: Vec<(u32, u32)> = diagnostics
        .iter()
        .zip(&run_of)
        .map(|(diagnostic, &run)| (rank_of_run[run], start(diagnostic)))
        .collect();
    let mut order: Vec<usize> = (0..diagnostics.len()).collect();
    order.sort_by(|&a, &b| {
        keys[a].cmp(&keys[b]).then_with(|| {
            let (a, b) = (&diagnostics[a], &diagnostics[b]);
            a.rule.cmp(&b.rule).then_with(|| a.message.cmp(&b.message))
        })
    });
    // Position `k` takes the diagnostic at `order[k]`; each cycle of the permutation is walked once.
    for first in 0..order.len() {
        let mut current = first;
        while order[current] != usize::MAX {
            let next = std::mem::replace(&mut order[current], usize::MAX);
            if next == first {
                break;
            }
            diagnostics.swap(current, next);
            current = next;
        }
    }
}

/// Whether `path` is spelled so that [`plain_cmp`] orders it as `Path` does: on a platform whose only separator is
/// `/`, without an empty (`a//b`, `a/`), `.` or `..` component, so its components are exactly its `/`-separated parts.
fn is_plain(path: &Path) -> bool {
    !cfg!(windows)
        && path
            .as_os_str()
            .as_encoded_bytes()
            .split(|&byte| byte == b'/')
            .enumerate()
            .all(|(index, part)| (index == 0 || !part.is_empty()) && part != b"." && part != b"..")
}

/// The order of two [plain](is_plain) paths by component, from their bytes: up to the first difference they share
/// their components, and there the one whose component ends (a `/`, or the end of the path) is the smaller.
fn plain_cmp(a: &Path, b: &Path) -> Ordering {
    let (a, b) = (a.as_os_str().as_encoded_bytes(), b.as_os_str().as_encoded_bytes());
    let key = |byte: u8| if byte == b'/' { 0 } else { u16::from(byte) + 1 };
    match a.iter().zip(b).position(|(x, y)| x != y) {
        Some(index) => key(a[index]).cmp(&key(b[index])),
        None => a.len().cmp(&b.len()),
    }
}

fn start(diagnostic: &Diagnostic) -> u32 {
    diagnostic.location.span.map_or(0, |span| span.start)
}

/// The order of a report, which [`sort`] computes faster; kept as the reference the tests hold it to.
#[cfg(test)]
fn compare(a: &Diagnostic, b: &Diagnostic) -> Ordering {
    a.location
        .path
        .cmp(&b.location.path)
        .then_with(|| start(a).cmp(&start(b)))
        .then_with(|| a.rule.cmp(&b.rule))
        .then_with(|| a.message.cmp(&b.message))
}

fn count(mut summary: Summary, diagnostic: &Diagnostic) -> Summary {
    match diagnostic.severity {
        Severity::Error => summary.errors += 1,
        Severity::Warning => summary.warnings += 1,
        Severity::Info => summary.infos += 1,
    }
    summary.fixable += usize::from(diagnostic.is_fixable());
    summary
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
    use super::*;
    use crate::fix::{Fix, FixOp, FixSafety};
    use crate::rule::RuleId;
    use crate::span::{Location, Span};

    fn diag(rule: &'static str, severity: Severity, path: &str, start: Option<u32>, fixable: bool) -> Diagnostic {
        let span = start.map(|s| Span {
            start: s,
            end: s + 1,
            start_line: 1,
            start_col: s + 1,
            end_line: 1,
            end_col: s + 2,
        });
        let fixes = if fixable {
            vec![Fix {
                title: "f".into(),
                safety: FixSafety::Safe,
                ops: vec![FixOp::DeleteFile { path: path.into() }],
                preference: None,
            }]
        } else {
            Vec::new()
        };
        Diagnostic {
            rule: RuleId::from_static(rule),
            severity,
            message: rule.to_owned(),
            help: None,
            location: Location {
                path: path.into(),
                span,
            },
            related: Vec::new(),
            package: None,
            package_id: None,
            dependency: None,
            specifier: None,
            default_severity: None,
            detail: None,
            fixes,
        }
    }

    fn order(report: &Report) -> Vec<(String, u32, String)> {
        report
            .diagnostics
            .iter()
            .map(|d| (d.location.path.display().to_string(), start(d), d.rule.to_string()))
            .collect()
    }

    fn input() -> Vec<Diagnostic> {
        vec![
            diag("b-rule", Severity::Warning, "z/package.json", Some(4), true),
            diag("a-rule", Severity::Error, "a/package.json", Some(9), false),
            diag("c-rule", Severity::Info, "a/package.json", Some(2), false),
            diag("b-rule", Severity::Error, "a/package.json", Some(9), true),
            diag("a-rule", Severity::Error, "a/package.json", None, false),
        ]
    }

    #[test]
    fn sorts_by_path_start_then_rule() {
        let expected = [
            ("a/package.json", 0, "a-rule"),
            ("a/package.json", 2, "c-rule"),
            ("a/package.json", 9, "a-rule"),
            ("a/package.json", 9, "b-rule"),
            ("z/package.json", 4, "b-rule"),
        ]
        .map(|(p, s, r)| (p.to_owned(), s, r.to_owned()));
        assert_eq!(order(&Report::new(input(), 3)), expected);
    }

    #[test]
    fn order_is_independent_of_input_order() {
        let forward = Report::new(input(), 3);
        let mut reversed = input();
        reversed.reverse();
        assert_eq!(Report::new(reversed, 3), forward);
    }

    #[test]
    fn sorts_as_a_stable_sort_by_compare() {
        // Paths that order differently by component than by bytes (`a-b`, `a.b` and `a/b`, `/` and relative), and a
        // second set with spellings of one path (`a//b`, `./a`) and `..`, which take the general comparison. Missing
        // spans and diagnostics equal in every sort key, told apart by their help, in a scrambled order.
        let plain = [
            "a/b/package.json",
            "a-b/package.json",
            "a.b/package.json",
            "a/package.json",
            "/a/package.json",
            "package.json",
            "a/b",
        ];
        let spelled = [
            "a/b/package.json",
            "a//b/package.json",
            "./a/package.json",
            "../a/package.json",
            "-a/x",
        ];
        for paths in [&plain[..], &spelled[..]] {
            let rules = ["a-rule", "b-rule"];
            let mut state: u32 = 7;
            let mut next = |bound: usize| {
                state = state.wrapping_mul(1_103_515_245).wrapping_add(12_345);
                usize::try_from(state >> 16).unwrap() % bound
            };
            let input: Vec<Diagnostic> = (0..400)
                .map(|index| {
                    let start = [None, Some(0), Some(3), Some(9)][next(4)];
                    let path = paths[next(paths.len())];
                    let mut diagnostic = diag(rules[next(2)], Severity::Error, path, start, false);
                    diagnostic.help = Some(index.to_string());
                    diagnostic
                })
                .collect();
            let mut expected = input.clone();
            expected.sort_by(compare);
            assert_eq!(Report::new(input, 1).diagnostics, expected, "{paths:?}");
        }
    }

    #[test]
    fn plain_paths_compare_by_component() {
        let paths = [
            "", "/a", "a", "a-b", "a.b", "a/b", "a/b/c", "a/bc", "ab", "b", "a/b-c", "a/b/-",
        ];
        if cfg!(windows) {
            // `\` is a separator too, so every path takes the `Path` order there.
            assert!(paths.iter().all(|path| !is_plain(Path::new(path))));
            return;
        }
        for a in paths {
            for b in paths {
                let (a, b) = (Path::new(a), Path::new(b));
                assert!(is_plain(a) && is_plain(b), "{a:?} {b:?}");
                assert_eq!(plain_cmp(a, b), a.cmp(b), "{a:?} {b:?}");
            }
        }
        for path in ["/", "a//b", "a/", "./a", "a/./b", "a/../b", ".."] {
            assert!(!is_plain(Path::new(path)), "{path}");
        }
    }

    #[test]
    fn counts_summary() {
        assert_eq!(
            Report::new(input(), 3).summary,
            Summary {
                errors: 3,
                warnings: 1,
                infos: 1,
                fixable: 2,
                packages: 3
            }
        );
    }

    #[test]
    fn empty_report_has_zero_counts() {
        let report = Report::new(Vec::new(), 7);
        assert_eq!(report.diagnostics, Vec::new());
        assert_eq!(
            report.summary,
            Summary {
                packages: 7,
                ..Summary::default()
            }
        );
    }

    #[test]
    fn summary_serializes_kebab_case() {
        let summary = Summary {
            errors: 1,
            warnings: 2,
            infos: 3,
            fixable: 4,
            packages: 5,
        };
        assert_eq!(
            serde_json::to_value(summary).unwrap(),
            serde_json::json!({ "errors": 1, "warnings": 2, "infos": 3, "fixable": 4, "packages": 5 })
        );
    }
    #[test]
    fn incomplete_packages_sort_by_directory_and_serialize_kebab_case() {
        use crate::incomplete::{IncompleteCause, IncompleteEntries};

        let reason = |cause, plugin: Option<&str>, file: Option<&str>| IncompleteEntries {
            cause,
            plugin: plugin.map(str::to_owned),
            file: file.map(std::path::PathBuf::from),
        };
        let report = Report::new(Vec::new(), 2).with_incomplete_packages(vec![
            IncompletePackage::new(
                "web".into(),
                "packages/web".into(),
                vec![reason(
                    IncompleteCause::UnknownSpread,
                    Some("vite"),
                    Some("packages/web/vite.config.ts"),
                )],
            ),
            IncompletePackage::new(
                "api".into(),
                "packages/api".into(),
                vec![reason(IncompleteCause::Unspecified, None, None)],
            ),
        ]);
        assert_eq!(
            serde_json::to_value(&report).unwrap()["incomplete-packages"],
            serde_json::json!([
                { "name": "api", "dir": "packages/api", "reasons": [{ "cause": "unspecified" }] },
                { "name": "web", "dir": "packages/web", "reasons": [
                    { "cause": "unknown-spread", "plugin": "vite", "file": "packages/web/vite.config.ts" }
                ] },
            ])
        );
        let empty = serde_json::to_value(Report::new(Vec::new(), 1)).unwrap();
        assert!(empty.get("incomplete-packages").is_none());
    }
}