zccache 1.12.16

//! Core dependency graph.
//!
//! Two-map design:
//! - `files`: shared file nodes (one per unique path, across all contexts)
//! - `contexts`: per-compilation-context entries with resolved include lists
//!
//! The implementation is split across several files for the LOC guard:
//! - `register` — context registration (`register*`, `register_context_entry`, `is_cold`).
//! - `check` — verdict computation (`check`, `check_diagnostic`, `try_fast_hit`).
//! - `update` — post-compile include-list + artifact-key recording.
//! - `maintenance` — `trim`, `clear`, stats, accessors, `ingest_compile_commands`.

mod check;
mod maintenance;
mod register;
mod update;

use std::path::Path;
use std::sync::atomic::AtomicU64;
use std::sync::Arc;
use std::time::Instant;

use dashmap::DashMap;
use crate::core::NormalizedPath;
use crate::hash::{ContentHash, StreamHasher};

use super::context::{ArtifactKey, CompileContext, ContextKey};
use super::scanner::IncludeDirective;

/// A file node in the graph. Shared across all contexts.
#[derive(Debug, Clone)]
pub struct FileEntry {
    /// Raw `#include` directives found in this file.
    pub includes: Vec<IncludeDirective>,
    /// When this file was last scanned for includes.
    pub scanned_at: Instant,
}

/// State of a compilation context in the graph.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ContextState {
    /// No include list yet — needs full recursive scan.
    Cold,
    /// Include list populated and believed current.
    Warm,
    /// Something changed — needs partial or full rescan.
    Stale,
}

/// A compilation context entry in the graph.
#[derive(Debug, Clone)]
pub struct ContextEntry {
    /// Root-normalized identity used for content-addressed artifact keys.
    pub logical_key: ContextKey,
    /// The compilation context (source + flags).
    pub context: CompileContext,
    /// Optional root used to normalize project-local paths in cache keys.
    pub key_root: Option<NormalizedPath>,
    /// Flat list of all transitive resolved headers (absolute paths).
    pub resolved_includes: Vec<NormalizedPath>,
    /// Include names that could not be resolved to any file.
    pub unresolved_includes: Vec<String>,
    /// True if any `#include MACRO` was found during scanning.
    pub has_computed_includes: bool,
    /// Last computed artifact key.
    pub artifact_key: Option<ArtifactKey>,
    /// File hashes from the last update() — used for drift diagnostics.
    pub last_file_hashes: Vec<(NormalizedPath, ContentHash)>,
    /// When this entry was last accessed (for trimming).
    pub last_accessed: Instant,
    /// Current state.
    pub state: ContextState,
}

/// Checkout-specific identity for mutable dependency-graph state.
///
/// Its logical component remains root-normalized for artifact sharing. Its
/// concrete component is deliberately excluded from artifact-key computation.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct ContextInstanceKey {
    logical: ContextKey,
    concrete: ContentHash,
}

impl ContextInstanceKey {
    #[must_use]
    pub fn logical(self) -> ContextKey {
        self.logical
    }

    #[must_use]
    pub fn concrete(self) -> ContentHash {
        self.concrete
    }

    pub(crate) fn new(
        logical: ContextKey,
        source_file: &NormalizedPath,
        key_root: Option<&NormalizedPath>,
    ) -> Self {
        let mut hash = StreamHasher::new();
        hash.update(b"zccache-context-instance-v1\0");
        hash.update(logical.hash().as_bytes());
        hash.update(source_file.case_key().unwrap_or_default().as_bytes());
        hash.update(b"\0");
        match key_root {
            Some(root) => hash.update(root.case_key().unwrap_or_default().as_bytes()),
            None => hash.update(b"no-key-root"),
        };
        Self {
            logical,
            concrete: hash.finalize(),
        }
    }

    #[must_use]
    pub fn map_key(self) -> ContextKey {
        ContextKey::from_raw(*self.concrete.as_bytes())
    }
}

/// Result of checking a context against the file cache.
#[derive(Debug, Clone)]
pub enum CacheVerdict {
    /// All files fresh, artifact key valid. Use cached object.
    Hit { artifact_key: ArtifactKey },
    /// Source changed but headers are fresh. New artifact key computed.
    SourceChanged { artifact_key: ArtifactKey },
    /// One or more headers changed. Rescan needed.
    HeadersChanged { changed: Vec<NormalizedPath> },
    /// No include list yet. Full scan required.
    Cold,
    /// Contains `#include MACRO`. Needs preprocessor fallback.
    NeedsPreprocessor,
}

/// Statistics about the dependency graph.
#[derive(Debug, Clone)]
pub struct DepGraphStats {
    /// Number of unique files tracked.
    pub file_count: usize,
    /// Number of compilation contexts tracked.
    pub context_count: usize,
    /// Number of check() calls.
    pub checks: u64,
    /// Number of cache hits (ultra-fast + fast path).
    pub hits: u64,
    /// Number of cache misses.
    pub misses: u64,
}

/// The core dependency graph.
impl std::fmt::Debug for DepGraph {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("DepGraph")
            .field("files", &self.files.len())
            .field("contexts", &self.contexts.len())
            .finish()
    }
}

pub struct DepGraph {
    /// Shared file nodes: path → scanned includes.
    pub(super) files: Box<DashMap<NormalizedPath, FileEntry>>,
    /// Per-context entries: context key → include list + state.
    pub(super) contexts: DashMap<ContextKey, ContextEntry>,
    /// Rustc-only extern inputs keyed by context.
    ///
    /// These are tracked outside `ContextEntry::resolved_includes` because
    /// their paths are output-placement state. Their content hashes affect the
    /// rustc artifact key by crate name, but target-dir path prefixes must not.
    pub(super) rustc_externs: DashMap<ContextKey, Vec<(String, NormalizedPath)>>,
    /// Rustc env-dep snapshots keyed by context (zccache#1021).
    ///
    /// rustc records every `env!()`/`option_env!()` read as a
    /// `# env-dep:NAME[=value]` line in its dep-info. We store, per
    /// context, the read variable NAMES with the blake3 hash of the value
    /// each had at the last successful compile (`None` = the variable was
    /// unset). Check paths re-resolve the CURRENT values via a
    /// caller-supplied lookup and fold them into the artifact key, so a
    /// changed `cargo:rustc-env` value (vergen `VERGEN_GIT_SHA` etc.)
    /// misses instead of serving an artifact with the stale value baked
    /// in. Non-rustc contexts never have an entry here.
    pub(super) rustc_env_deps: DashMap<ContextKey, Vec<(String, Option<ContentHash>)>>,
    /// Rustc check/build metadata compatibility alias.
    ///
    /// Keyed by the checkout-specific form of
    /// `RustcCompileContext::check_metadata_compat_key_with_root`.
    /// Values are exact build-style instance keys that can supply `.rmeta`
    /// and dep-info outputs to a check-style request.
    pub(super) rustc_check_metadata_compat: DashMap<ContextKey, ContextKey>,
    /// Issue #550: cached normalize_key_path results, keyed by
    /// (path, key_root_identity). The `update()` hot loop calls
    /// `normalize_key_path` once per resolved include header (typically
    /// 200-500 entries for a C++ compile pulling `<iostream>`). The
    /// normalization itself allocates a `String` per call; caching the
    /// `Arc<str>` result lets subsequent compiles in the same daemon
    /// session reuse the work — measured at ~2 ms saved per cpp-inline
    /// cold compile after the cache is warm. Capped to bound memory.
    pub(super) indexes: Box<GraphIndexes>,
    /// Stats counters.
    pub(super) checks: AtomicU64,
    pub(super) hits: AtomicU64,
    pub(super) misses: AtomicU64,
}

/// Cache key for `path_key_cache`. `(header_path, key_root_or_none)`.
/// Different `key_root` values produce different normalized output
/// (project-relative vs absolute), so the cache must scope by root.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub(super) struct PathKeyCacheKey {
    pub(super) path: NormalizedPath,
    pub(super) key_root: Option<NormalizedPath>,
}

/// Heap-owned auxiliary indexes so their growth does not enlarge `DepGraph`
/// values carried by the persisted-load result enum.
pub(super) struct GraphIndexes {
    pub(super) equivalent_contexts: DashMap<ContextKey, Vec<ContextKey>>,
    pub(super) path_key_cache: DashMap<PathKeyCacheKey, Arc<str>>,
}

impl GraphIndexes {
    fn new() -> Self {
        Self {
            equivalent_contexts: DashMap::new(),
            path_key_cache: DashMap::new(),
        }
    }
}

#[derive(Debug, Clone, Copy)]
pub struct ContextRegistration {
    /// Root-normalized key used only for content-addressed artifact identity.
    pub key: ContextKey,
    /// Checkout-specific key used for all mutable dependency-graph access.
    pub map_key: ContextKey,
    pub instance: ContextInstanceKey,
    /// Checkout-specific metadata-compatibility alias, when rustc registered
    /// one. The public compatibility key remains root-normalized, while this
    /// map key prevents one checkout from replacing another's alias target.
    pub metadata_compat_map_key: Option<ContextKey>,
    pub rebased_from_equivalent_root: bool,
}

/// Issue #582: cached check for `ZCCACHE_PROFILE_CC_MISS` so
/// `DepGraph::update`'s sub-phase emit doesn't pay an env-lookup
/// syscall on every call. Read once on first access.
pub(super) fn depgraph_update_profile_enabled() -> bool {
    use std::sync::OnceLock;
    static FLAG: OnceLock<bool> = OnceLock::new();
    *FLAG.get_or_init(|| std::env::var_os("ZCCACHE_PROFILE_CC_MISS").is_some())
}

pub(super) fn rebase_project_path(
    path: &NormalizedPath,
    old_root: Option<&NormalizedPath>,
    new_root: Option<&NormalizedPath>,
) -> NormalizedPath {
    match (old_root, new_root) {
        (Some(old_root), Some(new_root)) => path
            .strip_prefix(old_root)
            .map(|relative| new_root.join(relative))
            .unwrap_or_else(|_| path.clone()),
        _ => path.clone(),
    }
}

pub(super) fn collect_rustc_extern_hashes<G>(
    rustc_externs: &[(String, NormalizedPath)],
    get_hash: &G,
) -> Option<Vec<(String, ContentHash)>>
where
    G: Fn(&Path) -> Option<ContentHash>,
{
    let mut extern_hashes = Vec::with_capacity(rustc_externs.len());
    for (name, path) in rustc_externs {
        extern_hashes.push((name.clone(), get_hash(path)?));
    }
    Some(extern_hashes)
}

/// Hash an env-dep value for the artifact key (zccache#1021).
/// `None` (variable unset) stays `None` — the key fold encodes it as a
/// distinct "unset" marker.
pub fn hash_env_dep_value(value: Option<&str>) -> Option<ContentHash> {
    value.map(|v| crate::hash::hash_bytes(v.as_bytes()))
}

/// Resolve the CURRENT `(name, value_hash)` pairs for a recorded env-dep
/// name set via the caller-supplied env lookup.
pub(super) fn collect_rustc_env_hashes<E>(
    names: &[(String, Option<ContentHash>)],
    env_value: &E,
) -> Vec<(String, Option<ContentHash>)>
where
    E: Fn(&str) -> Option<String>,
{
    names
        .iter()
        .map(|(name, _recorded)| {
            let current = env_value(name);
            (name.clone(), hash_env_dep_value(current.as_deref()))
        })
        .collect()
}

/// Files whose content hash has drifted relative to the hashes captured by
/// the most recent `update()` — either a tracked path now reports a
/// different hash, or a path appears in the current set that wasn't in
/// `last_file_hashes` (membership shifted, e.g. a new transitive include).
///
/// Returns an empty `Vec` when `last_file_hashes` is empty (the entry has
/// never been hashed) so callers can distinguish "no drift signal
/// available" from "drift confirmed clean."
///
/// Issue #449: even when the journal misses a watcher event and reports
/// the file as fresh, a hash mismatch here is the ground-truth signal
/// that the source state moved — and that the cached
/// `entry.resolved_includes` set may no longer reflect the file's
/// transitive deps. Returning the drifted paths to the caller lets
/// `check` / `check_diagnostic` downgrade what would otherwise have been
/// a `Hit` with a stale-prediction `artifact_key` into a
/// `HeadersChanged` verdict that forces a fresh scan.
pub(super) fn drifted_paths<'a, I, P>(
    last_file_hashes: &[(NormalizedPath, ContentHash)],
    current: I,
) -> Vec<NormalizedPath>
where
    I: IntoIterator<Item = (P, &'a ContentHash)>,
    P: AsRef<Path>,
{
    if last_file_hashes.is_empty() {
        return Vec::new();
    }
    let old_map: std::collections::HashMap<&Path, &ContentHash> = last_file_hashes
        .iter()
        .map(|(p, h)| (p.as_path(), h))
        .collect();
    let mut drifted: Vec<NormalizedPath> = Vec::new();
    for (path, new_hash) in current {
        let p = path.as_ref();
        match old_map.get(p) {
            Some(old_hash) if old_hash != &new_hash => {
                drifted.push(p.into());
            }
            None => {
                // Membership drift: a path that wasn't in last_file_hashes
                // is now present. Treat as a changed dependency.
                drifted.push(p.into());
            }
            _ => {}
        }
    }
    drifted
}

/// Format a drift list for the diagnostic session log: at most 5 file
/// names, comma-separated, prefixed with `, drifted=[…]`. Empty input
/// yields an empty string so the caller can splat it into a `format!`
/// without conditional logic.
pub(super) fn format_drift_for_log(drifted: &[NormalizedPath]) -> String {
    if drifted.is_empty() {
        return String::new();
    }
    let names: Vec<String> = drifted
        .iter()
        .take(5)
        .map(|p| {
            p.file_name()
                .map(|n| n.to_string_lossy().into_owned())
                .unwrap_or_else(|| p.display().to_string())
        })
        .collect();
    format!(", drifted=[{}]", names.join(","))
}

impl DepGraph {
    /// Create a new empty dependency graph.
    #[must_use]
    pub fn new() -> Self {
        Self {
            files: Box::new(DashMap::new()),
            contexts: DashMap::new(),
            rustc_externs: DashMap::new(),
            rustc_env_deps: DashMap::new(),
            rustc_check_metadata_compat: DashMap::new(),
            indexes: Box::new(GraphIndexes::new()),
            checks: AtomicU64::new(0),
            hits: AtomicU64::new(0),
            misses: AtomicU64::new(0),
        }
    }

    /// Cached version of [`crate::depgraph::context::normalize_key_path`].
    ///
    /// Looks up `(path, key_root)` in `path_key_cache`. On hit, returns
    /// the cached `Arc<str>` without re-running the underlying normalization.
    /// On miss, computes via `normalize_key_path` and inserts (subject to
    /// the `PATH_KEY_CACHE_MAX_ENTRIES` cap — past the cap, the result is
    /// returned without caching so memory stays bounded).
    ///
    /// Issue #550 — the `compute_artifact_key` hot loop's per-header
    /// allocation hotspot.
    pub fn cached_normalize_key_path(&self, path: &Path, key_root: Option<&Path>) -> Arc<str> {
        // Issue #588: the path_key_cache was net-negative. Each lookup
        // allocated 4 owned objects (two NormalizedPaths) to construct
        // the DashMap key, saving only ~1 normalize_for_key allocation.
        // The diagnostic data from #584 confirmed `artifact_key_compute_ns`
        // didn't move when the cache was bypassed (#587 fast path).
        //
        // Inline normalize_key_path with zero cache overhead. The Arc<str>
        // conversion from String reuses the heap allocation — one alloc
        // per call total, vs the prior four.
        //
        // The path_key_cache field is retained for backward-compat with
        // tests and to keep the API surface stable; new calls bypass it.
        crate::depgraph::context::normalize_key_path(path, key_root).into()
    }

    /// Number of cached entries in `path_key_cache`. Test-only.
    #[cfg(test)]
    pub fn path_key_cache_len(&self) -> usize {
        self.indexes.path_key_cache.len()
    }

    pub(super) fn rustc_extern_inputs(
        &self,
        key: &ContextKey,
    ) -> Option<Vec<(String, NormalizedPath)>> {
        self.rustc_externs.get(key).map(|externs| externs.clone())
    }

    /// Recorded env-dep snapshot for a context (zccache#1021): the env
    /// variable names the crate read via `env!()`/`option_env!()` with the
    /// value hash each had at the last compile (`None` = unset). `None`
    /// result = the context has no recorded env-deps (the common case).
    pub(super) fn rustc_env_dep_inputs(
        &self,
        key: &ContextKey,
    ) -> Option<Vec<(String, Option<ContentHash>)>> {
        self.rustc_env_deps.get(key).map(|deps| deps.clone())
    }

    /// Resolve a public logical key only when it identifies one safe mutable
    /// instance. Callers that hold a registration pass its instance map key,
    /// which takes the first branch. Ambiguous legacy lookups conservatively
    /// miss instead of selecting another checkout's state.
    pub(super) fn resolve_instance_key(&self, key: &ContextKey) -> Option<ContextKey> {
        if self.contexts.contains_key(key) {
            return Some(*key);
        }
        let instances = self.indexes.equivalent_contexts.get(key)?;
        (instances.len() == 1).then_some(instances[0])
    }

    /// Construct a `DepGraph` from pre-built maps, including rustc extern
    /// inputs and env-dep snapshots (zccache#1021).
    pub(crate) fn from_maps_with_rustc_externs_and_env_deps(
        files: DashMap<NormalizedPath, FileEntry>,
        contexts: DashMap<ContextKey, ContextEntry>,
        rustc_externs: DashMap<ContextKey, Vec<(String, NormalizedPath)>>,
        rustc_env_deps: DashMap<ContextKey, Vec<(String, Option<ContentHash>)>>,
    ) -> Self {
        Self {
            files: Box::new(files),
            contexts,
            rustc_externs,
            rustc_env_deps,
            rustc_check_metadata_compat: DashMap::new(),
            indexes: Box::new(GraphIndexes::new()),
            checks: AtomicU64::new(0),
            hits: AtomicU64::new(0),
            misses: AtomicU64::new(0),
        }
    }
}

impl Default for DepGraph {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests;
#[cfg(test)]
#[path = "tests/worktree_variants.rs"]
mod worktree_variants;