qk_cache/

hash.rs

use std::collections::{BTreeMap, BTreeSet};
use std::ffi::OsString;
use std::fs::File;
use std::io::{Read, Write};
use std::path::{Path, PathBuf};
use std::sync::atomic::AtomicBool;
use std::sync::{Arc, Mutex};
use std::time::{Duration, Instant, SystemTime};

use anyhow::{Context, Result, bail};
use foldhash::{HashMap, HashMapExt, HashSet};
use qk_config::Workspace;
use qk_executor::{Capture, Display, Outcome, PreparedTask, execute_captured, read_capture};
use qk_graph::ProjectGraph;
use qk_lockfile::Lockfile;
use qk_taskgraph::{Task, TaskGraph};
use serde_json::{Value, json};

use crate::ignored::Group;
use crate::inputs::{
    Declared, Inferred, JsonFields, Resolved, TsConfig, manifest_for_dependents,
    workspace_without_resolution,
};
use crate::paths::{self, Outputs, Pattern};

pub fn digest_file(path: &Path) -> Result<String> {
    let mut hasher = blake3::Hasher::new();
    let mut reader = File::open(path)?;
    let mut buffer = [0; 64 * 1024];
    loop {
        let count = reader.read(&mut buffer)?;
        if count == 0 {
            break;
        }
        hasher.update(&buffer[..count]);
    }
    Ok(hasher.finalize().to_hex().to_string())
}

/// Metadata that changes whenever a file's content can have changed: size,
/// modification time and, on Unix, change time, inode and mode.
#[derive(Clone, PartialEq, serde::Serialize, serde::Deserialize)]
struct Stamp(Vec<i64>);

impl Stamp {
    fn new(metadata: &std::fs::Metadata) -> Self {
        let modified = metadata
            .modified()
            .ok()
            .and_then(|time| time.duration_since(SystemTime::UNIX_EPOCH).ok())
            .map_or(-1, |duration| duration.as_nanos() as i64);
        #[allow(unused_mut)]
        let mut values = vec![metadata.len() as i64, modified];
        #[cfg(unix)]
        {
            use std::os::unix::fs::MetadataExt;
            values.extend([
                metadata.ctime(),
                metadata.ctime_nsec(),
                metadata.ino() as i64,
                i64::from(metadata.mode()),
            ]);
        }
        Self(values)
    }

    /// Membership stamps also use change time: restoring a directory's mtime
    /// must not allow changes inside a coarse timestamp window to go unnoticed.
    fn membership_settled(&self) -> bool {
        #[cfg(unix)]
        let width = 6;
        #[cfg(not(unix))]
        let width = 2;
        self.0.chunks_exact(width).all(|values| {
            let modified = SystemTime::UNIX_EPOCH + Duration::from_nanos(values[1].max(0) as u64);
            let settled = |time| {
                SystemTime::now()
                    .duration_since(time)
                    .is_ok_and(|age| age > Duration::from_secs(2))
            };
            if values[1] < 0 || !settled(modified) {
                return false;
            }
            #[cfg(unix)]
            {
                let changed = SystemTime::UNIX_EPOCH
                    + Duration::new(values[2].max(0) as u64, values[3].max(0) as u32);
                values[2] >= 0 && settled(changed)
            }
            #[cfg(not(unix))]
            true
        })
    }

    /// A file written within the timestamp resolution window could change again
    /// without changing its stamp, so recent files are always re-read.
    fn settled(&self) -> bool {
        let modified = SystemTime::UNIX_EPOCH + Duration::from_nanos(self.0[1].max(0) as u64);
        self.0[1] >= 0
            && SystemTime::now()
                .duration_since(modified)
                .is_ok_and(|age| age > Duration::from_secs(2))
    }
}

/// Digests persisted between runs in the worktree's state, keyed by path and
/// stamp, so a warm run reads only the files that changed. Stamps include the
/// inode, so they belong to one worktree.
fn digests_path(root: &Path) -> PathBuf {
    paths::worktree_state(root).join("digests.json")
}

#[derive(PartialEq, Eq, Hash)]
struct RuntimeKey {
    command: String,
    environment: BTreeMap<OsString, OsString>,
}

/// Workspace state shared by every fingerprint in one run. Inspection uses the
/// initial candidate list; execution fingerprints refresh membership so files
/// added or removed during the run cannot escape input verification.
pub struct Snapshot {
    pub(crate) files: BTreeSet<String>,
    extra_candidates: BTreeSet<String>,
    membership: Mutex<Option<Arc<Membership>>>,
    membership_prefixes: Mutex<HashMap<String, Arc<Vec<PathBuf>>>>,
    source_exclusions: Vec<Outputs>,
    /// Every task's scratch directories, among `source_exclusions`, which no
    /// input reads, `includeIgnored` ones included.
    scratch: Vec<Outputs>,
    cache_relative: Option<PathBuf>,
    projects: ProjectGraph,
    /// Each project by its root, to find the project owning a file.
    roots: BTreeMap<String, String>,
    generated_tasks: Vec<(Task, Outputs)>,
    task_dependencies: BTreeMap<String, BTreeSet<String>>,
    /// Each task's servers, by project and declared inputs: see [`servers`].
    servers: BTreeMap<String, Vec<(String, Vec<Value>)>>,
    source_ignore: Arc<SourceIgnore>,
    canonical_root: PathBuf,
    workspace_prefix: Option<PathBuf>,
    patterns: Mutex<HashMap<(String, bool, bool), Arc<Pattern>>>,
    digests: Mutex<HashMap<String, (Stamp, String)>>,
    /// Files `includeIgnored` filesets read, whose digests are saved beside
    /// those of `files`, which may not list them.
    ignored_files: Mutex<BTreeSet<String>>,
    /// Whether `digests` gained entries worth saving.
    digests_changed: std::sync::atomic::AtomicBool,
    /// Directories already checked not to be symlinks.
    directories: Mutex<HashSet<PathBuf>>,
    /// Runtime input results by command and environment, computed once per run like Nx.
    runtime: Mutex<HashMap<RuntimeKey, Arc<Mutex<Option<Value>>>>>,
    /// The parsed pnpm lockfile, replaced whenever its content changes.
    lockfile: Mutex<Option<Arc<Installed>>>,
    /// Each dependency task's output files, listed when a task first asks and
    /// dropped once a task whose outputs overlap them is done.
    dependency_outputs: Mutex<HashMap<String, Arc<DependencyOutputs>>>,
    /// Counts drops, so a listing taken while a task finished is not kept.
    outputs_written: std::sync::atomic::AtomicU64,
}

/// Membership depends on directory entries and Git/ignore listing policy, not
/// on every source file's contents. Empty directories must also be watched.
#[derive(Clone)]
struct Membership {
    files: Arc<BTreeSet<String>>,
    source_ignore: Arc<SourceIgnore>,
    stamps: BTreeMap<PathBuf, Option<Stamp>>,
    directories: BTreeSet<PathBuf>,
    directory_entries: BTreeMap<PathBuf, BTreeSet<(OsString, u8)>>,
    root: PathBuf,
    outputs: Vec<Outputs>,
    output_anchors: BTreeMap<PathBuf, Vec<usize>>,
    excluded_roots: BTreeSet<PathBuf>,
    cache: Option<PathBuf>,
    policies: BTreeSet<PathBuf>,
    git_policies: BTreeSet<PathBuf>,
    ignore_contents: BTreeMap<PathBuf, String>,
    settled: bool,
    /// When the refresh that produced this inventory began listing.
    listed: Option<Instant>,
}

/// A candidate listing and the ignore policy captured with it. Keeping both
/// alive prevents a concurrent refresh from changing dependency-output selection.
#[derive(Clone)]
struct Candidates {
    files: Arc<BTreeSet<String>>,
    source_ignore: Arc<SourceIgnore>,
}

impl Membership {
    /// Inventory source directories and policy stamps before a new listing.
    fn new(
        root: &Path,
        files: &BTreeSet<String>,
        source_ignore: &Arc<SourceIgnore>,
        outputs: &[Outputs],
        cache: Option<&Path>,
        git_policies: Option<&BTreeSet<PathBuf>>,
    ) -> Result<Self> {
        let excluded: BTreeSet<_> = outputs
            .iter()
            .flat_map(Outputs::complete_roots)
            .map(PathBuf::from)
            .collect();
        let excluded_roots = excluded.clone();
        let walk_root = root.to_owned();
        let walk_cache = cache.map(PathBuf::from);
        let mut directories = BTreeSet::new();
        let mut stamps = BTreeMap::new();
        for entry in ignore::WalkBuilder::new(root)
            .hidden(false)
            .parents(false)
            .git_global(false)
            .require_git(false)
            .ignore(false)
            .git_ignore(false)
            .git_exclude(false)
            .follow_links(false)
            .filter_entry(move |entry| {
                let relative = entry
                    .path()
                    .strip_prefix(&walk_root)
                    .unwrap_or(entry.path());
                !matches!(
                    entry.file_name().to_str(),
                    Some(".git" | ".qk" | "node_modules")
                ) && walk_cache
                    .as_ref()
                    .is_none_or(|cache| !relative.starts_with(cache))
                    && !relative.ancestors().any(|path| excluded.contains(path))
            })
            .build()
        {
            let entry = entry?;
            if entry.file_type().is_some_and(|kind| kind.is_dir()) {
                let directory = entry.path().to_owned();
                stamps.insert(directory.clone(), membership_stamp(&directory)?);
                directories.insert(directory);
            }
        }
        // Git lists tracked files even beneath ignored directories. Watching
        // only the ignore walker would miss deletion/rename of those files.
        for path in files {
            for parent in Path::new(path).ancestors().skip(1) {
                let directory = root.join(parent);
                if directories.insert(directory.clone()) {
                    stamps.insert(directory.clone(), membership_stamp(&directory)?);
                }
            }
        }
        let mut policies = BTreeSet::new();
        for directory in &directories {
            for name in [".gitignore", ".nxignore"] {
                let path = directory.join(name);
                // Creation of a new ignore file changes its directory stamp.
                // Existing rules can be edited without changing the directory.
                if membership_stamp(&path)?.is_some() {
                    policies.insert(path);
                }
            }
        }
        for directory in root.ancestors() {
            policies.insert(directory.join(".gitignore"));
            // Also detect a newly initialized repository or changed worktree pointer.
            policies.insert(directory.join(".git"));
        }
        let git_policies = git_policies
            .cloned()
            .unwrap_or_else(|| git_membership_policies(root));
        policies.extend(git_policies.iter().cloned());
        for policy in &policies {
            stamps.insert(policy.clone(), membership_stamp(policy)?);
        }
        // Capture contents before listing, so a later policy change cannot be
        // mistaken for the rules that produced that listing.
        let mut ignore_contents = BTreeMap::new();
        for policy in &policies {
            if matches!(
                policy.file_name().and_then(|name| name.to_str()),
                Some(".gitignore" | ".nxignore")
            ) && let Some(content) = ignore_content(policy, &stamps[policy])?
            {
                ignore_contents.insert(policy.clone(), content);
            }
        }
        let mut output_anchors: BTreeMap<PathBuf, Vec<usize>> = BTreeMap::new();
        for (index, outputs) in outputs.iter().enumerate() {
            for anchor in outputs.anchors() {
                output_anchors
                    .entry(PathBuf::from(anchor))
                    .or_default()
                    .push(index);
            }
        }
        let mut membership = Self {
            files: Arc::new(BTreeSet::new()),
            source_ignore: source_ignore.clone(),
            stamps,
            directories,
            directory_entries: BTreeMap::new(),
            root: root.to_owned(),
            outputs: outputs.to_vec(),
            output_anchors,
            excluded_roots,
            cache: cache.map(PathBuf::from),
            policies,
            git_policies,
            ignore_contents,
            settled: false,
            listed: None,
        };
        for directory in &membership.directories {
            if let Some(entries) = membership.entries(directory)? {
                membership
                    .directory_entries
                    .insert(directory.clone(), entries);
            }
        }
        Ok(membership)
    }

    /// Names and types that can affect source membership in this directory.
    /// Output files may be skipped, but partially excluded output directories
    /// must remain visible because they can contain source files or ignore rules.
    fn entries(&self, directory: &Path) -> Result<Option<BTreeSet<(OsString, u8)>>> {
        let entries = match std::fs::read_dir(directory) {
            Ok(entries) => entries,
            Err(error)
                if matches!(
                    error.kind(),
                    std::io::ErrorKind::NotFound | std::io::ErrorKind::NotADirectory
                ) =>
            {
                return Ok(None);
            }
            Err(error) => return Err(error.into()),
        };
        let relative_directory = directory.strip_prefix(&self.root).unwrap_or(directory);
        let mut outputs = BTreeSet::new();
        for ancestor in relative_directory.ancestors() {
            if let Some(indices) = self.output_anchors.get(ancestor) {
                outputs.extend(indices.iter().copied());
            }
        }
        for (_, indices) in self
            .output_anchors
            .range(relative_directory.to_owned()..)
            .take_while(|(anchor, _)| anchor.starts_with(relative_directory))
        {
            outputs.extend(indices.iter().copied());
        }
        let mut names = BTreeSet::new();
        for entry in entries {
            let entry = entry?;
            let name = entry.file_name();
            let path = entry.path();
            let relative = path.strip_prefix(&self.root).unwrap_or(&path);
            if matches!(name.to_str(), Some(".git" | ".qk" | "node_modules"))
                || self
                    .cache
                    .as_ref()
                    .is_some_and(|cache| relative.starts_with(cache))
                || relative
                    .ancestors()
                    .any(|root| self.excluded_roots.contains(root))
            {
                continue;
            }
            // A policy created between policy discovery and name capture must
            // get its own stamp before its in-place edits can permit reuse.
            if matches!(name.to_str(), Some(".gitignore" | ".nxignore"))
                && !self.policies.contains(&path)
            {
                return Ok(None);
            }
            let kind = entry.file_type()?;
            // An empty directory created after the inventory walk would not
            // appear among source files. Never bless its parent signature until
            // that directory is itself watched by the inventory.
            if kind.is_dir() && !self.directories.contains(&path) {
                return Ok(None);
            }
            if !kind.is_dir()
                && !matches!(name.to_str(), Some(".gitignore" | ".nxignore"))
                && relative.to_str().is_some_and(|path| {
                    outputs
                        .iter()
                        .any(|index| self.outputs[*index].matches(path))
                })
            {
                continue;
            }
            names.insert((
                name,
                if kind.is_dir() {
                    1
                } else if kind.is_symlink() {
                    2
                } else {
                    0
                },
            ));
        }
        Ok(Some(names))
    }

    /// Check source-relevant directory membership and every listing policy.
    /// Recent directory stamps require fresh entry names; recent ignore files
    /// require matching contents, while other listing policies must settle.
    fn state(&self, prefixes: Option<&[PathBuf]>) -> Result<(bool, bool)> {
        let mut settled = true;
        let selected = prefixes.map(|prefixes| {
            let mut selected = BTreeSet::new();
            for prefix in prefixes {
                for ancestor in prefix.ancestors() {
                    if let Some(directory) = self.directories.get(ancestor) {
                        selected.insert(directory);
                    }
                }
                selected.extend(
                    self.directories
                        .range(prefix.clone()..)
                        .take_while(|directory| directory.starts_with(prefix)),
                );
            }
            selected
        });
        let paths: Box<dyn Iterator<Item = (&PathBuf, bool)>> = match selected {
            Some(selected) => Box::new(
                selected
                    .into_iter()
                    .map(|path| (path, true))
                    .chain(self.policies.iter().map(|path| (path, false))),
            ),
            None => Box::new(
                self.stamps
                    .keys()
                    .map(|path| (path, self.directories.contains(path))),
            ),
        };
        for (path, directory) in paths {
            let before = &self.stamps[path];
            let after = membership_stamp(path)?;
            if directory {
                if after.is_some() && !self.directory_entries.contains_key(path) {
                    return Ok((false, false));
                }
                // Output publication changes its parent's timestamp too. Check
                // source-relevant names rather than relisting the whole workspace.
                // Recent directories are always read, even with an equal stamp:
                // coarse timestamps can conceal an addition or removal.
                if *before != after
                    || after
                        .as_ref()
                        .is_some_and(|stamp| !stamp.membership_settled())
                {
                    let entries = self.entries(path)?;
                    if entries.as_ref() != self.directory_entries.get(path)
                        || membership_stamp(path)? != after
                    {
                        return Ok((false, false));
                    }
                }
            } else {
                let recent = after
                    .as_ref()
                    .is_some_and(|stamp| !stamp.membership_settled());
                if (*before != after || recent)
                    && let Some(content) = self.ignore_contents.get(path)
                {
                    if ignore_content(path, &after)?.as_ref() != Some(content) {
                        return Ok((false, false));
                    }
                    continue;
                }
                if *before != after {
                    return Ok((false, false));
                }
                settled &= !recent;
            }
        }
        Ok((true, settled))
    }

    /// Retain a matched listing and policy for use after releasing the lock.
    fn candidates(&self) -> Candidates {
        Candidates {
            files: self.files.clone(),
            source_ignore: self.source_ignore.clone(),
        }
    }
}

/// Find Git index, exclusion and config files that can change source visibility,
/// including absent policy files whose later creation must invalidate reuse.
fn git_membership_policies(root: &Path) -> BTreeSet<PathBuf> {
    let mut policies = BTreeSet::new();
    if let Ok(output) = paths::git(
        root,
        &[
            "rev-parse",
            "--path-format=absolute",
            "--git-path",
            "index",
            "--git-path",
            "info/exclude",
            "--git-path",
            "config",
            "--git-path",
            "config.worktree",
        ],
    ) && output.status.success()
        && let Ok(paths) = String::from_utf8(output.stdout)
    {
        policies.extend(paths.lines().map(PathBuf::from));
    }
    // Config can include other files. Track every origin used by Git, as
    // well as currently missing standard config and excludes files.
    if let Ok(output) = paths::git(root, &["config", "--null", "--show-origin", "--list"])
        && output.status.success()
    {
        // NUL mode emits raw origins, without Git's C-style path quoting,
        // and separates each origin from its key/newline/value record. Values
        // may themselves contain newlines (including include/excludes paths).
        let output = String::from_utf8_lossy(&output.stdout);
        let mut fields = output.split_terminator('\0');
        while let (Some(origin), Some(entry)) = (fields.next(), fields.next()) {
            if let Some(path) = origin.strip_prefix("file:") {
                let origin = root.join(path);
                if let Some((name, value)) = entry.split_once('\n')
                    && name.starts_with("include")
                    && name.ends_with(".path")
                {
                    let included = if let Some(relative) = value.strip_prefix("~/") {
                        std::env::var_os("HOME")
                            .map(PathBuf::from)
                            .unwrap_or_default()
                            .join(relative)
                    } else {
                        origin.parent().unwrap_or(root).join(value)
                    };
                    // Git omits missing includes from the origin listing, but
                    // creating one later can change core.excludesfile.
                    policies.insert(included);
                }
                policies.insert(origin);
            }
        }
    }
    if let Ok(output) = paths::git(
        root,
        &["config", "--null", "--path", "--get", "core.excludesfile"],
    ) && output.status.success()
        && let Ok(path) = String::from_utf8(output.stdout)
    {
        policies.insert(root.join(path.strip_suffix('\0').unwrap_or(&path)));
    }
    for variable in ["GIT_CONFIG_SYSTEM", "GIT_CONFIG_GLOBAL"] {
        if let Some(path) = std::env::var_os(variable) {
            policies.insert(PathBuf::from(path));
        }
    }
    policies.insert(PathBuf::from("/etc/gitconfig"));
    if let Some(home) = std::env::var_os("HOME") {
        let home = PathBuf::from(home);
        policies.insert(home.join(".gitconfig"));
        let config = std::env::var_os("XDG_CONFIG_HOME")
            .map(PathBuf::from)
            .unwrap_or_else(|| home.join(".config"));
        policies.insert(config.join("git/config"));
        policies.insert(config.join("git/ignore"));
    }
    policies
}

/// Read a regular ignore policy only when the captured metadata remains stable.
/// A digest read after a listing must never replace the pre-listing digest.
fn ignore_content(path: &Path, expected: &Option<Stamp>) -> Result<Option<String>> {
    if expected.is_none() || membership_stamp(path)? != *expected {
        return Ok(None);
    }
    match std::fs::symlink_metadata(path) {
        Ok(metadata) if metadata.is_file() => {}
        Ok(_) => return Ok(None),
        Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
        Err(error) => return Err(error.into()),
    }
    let content = match std::fs::read(path) {
        Ok(content) => content,
        Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
        Err(error) => return Err(error.into()),
    };
    Ok((membership_stamp(path)? == *expected).then(|| blake3::hash(&content).to_hex().to_string()))
}

/// Stamp a directory or listing policy, including a symlink's resolved target.
fn membership_stamp(path: &Path) -> Result<Option<Stamp>> {
    match std::fs::symlink_metadata(path) {
        Ok(metadata) => {
            let mut stamp = Stamp::new(&metadata);
            if metadata.is_symlink() {
                // Follow the current chain on every check. In-place target
                // edits or retargeted intermediate links can change policy.
                match std::fs::metadata(path) {
                    Ok(target) => stamp.0.extend(Stamp::new(&target).0),
                    Err(error) if error.kind() == std::io::ErrorKind::NotFound => stamp.0[1] = -1,
                    Err(error) => return Err(error.into()),
                }
            }
            Ok(Some(stamp))
        }
        Err(error)
            if matches!(
                error.kind(),
                std::io::ErrorKind::NotFound | std::io::ErrorKind::NotADirectory
            ) =>
        {
            Ok(None)
        }
        Err(error) => Err(error).with_context(|| format!("cannot inspect {}", path.display())),
    }
}

/// One dependency task's output files, and the value of each one a pattern
/// has selected so far.
struct DependencyOutputs {
    anchors: Vec<String>,
    files: Vec<String>,
    values: Mutex<HashMap<String, Value>>,
}

/// One revision of `pnpm-lock.yaml`, with digests of what it installs computed
/// once and shared by every task that asks.
struct Installed {
    content: String,
    /// `None` when the file cannot be read as a pnpm v9 lockfile.
    lockfile: Option<Lockfile>,
    digests: Mutex<HashMap<String, String>>,
}

impl Installed {
    fn digest(&self, key: &str, fingerprints: impl FnOnce() -> BTreeSet<String>) -> String {
        if let Some(digest) = self.digests.lock().unwrap().get(key) {
            return digest.clone();
        }
        let mut hasher = blake3::Hasher::new();
        for fingerprint in fingerprints() {
            hasher.update(fingerprint.as_bytes());
            hasher.update(b"\n");
        }
        let digest = hasher.finalize().to_hex().to_string();
        self.digests
            .lock()
            .unwrap()
            .insert(key.to_owned(), digest.clone());
        digest
    }
}

impl Snapshot {
    pub fn new(workspace: &Workspace, graph: &TaskGraph, cache_path: &Path) -> Result<Self> {
        // Every early task needs these, so loading saved digests and parsing
        // the lockfile overlap listing files.
        let canonical_root = workspace.root.canonicalize()?;
        let (files, lockfile, (digests, workspace_prefix)) = std::thread::scope(|scope| {
            let lockfile = scope.spawn(|| parse_lockfile(&workspace.root.join("pnpm-lock.yaml")));
            let digests = scope.spawn(|| {
                let digests = load_digests(&workspace.root);
                let workspace_prefix = paths::git_path(&workspace.root, "--show-toplevel")
                    .and_then(|root| root.canonicalize().ok())
                    .and_then(|root| canonical_root.strip_prefix(root).ok().map(PathBuf::from));
                (digests, workspace_prefix)
            });
            let files = source_files(&workspace.root);
            (
                files,
                lockfile.join().expect("lockfile thread panicked"),
                digests.join().expect("digest thread panicked"),
            )
        });
        let mut files = files?;
        let cache_relative = cache_path
            .strip_prefix(&workspace.root)
            .ok()
            .map(PathBuf::from);
        // Keep the patterns, not only the artifacts present at startup: new
        // outputs and warm scratch files must be excluded on every refresh.
        let mut source_exclusions: Vec<_> = graph
            .tasks
            .values()
            .filter_map(|task| Outputs::new(workspace, task).ok())
            .filter(Outputs::is_explicit)
            .collect();
        for task in graph.tasks.values() {
            let Ok(entries) = crate::warm::config(workspace, task) else {
                continue;
            };
            if let Ok(paths) = Outputs::from_paths(&crate::warm::kept_paths(&entries)) {
                source_exclusions.push(paths);
            }
        }
        // Scratch directories, which each run empties: what is in them is no
        // input, before or after the task runs.
        let mut scratch_paths = Vec::new();
        for task in graph.tasks.values() {
            let scratch: Vec<String> = crate::scratch::directories(workspace, task)
                .unwrap_or_default()
                .iter()
                .filter_map(|directory| {
                    let relative = directory.strip_prefix(&workspace.root).ok()?.to_str()?;
                    let named = crate::glob::escape(&relative.replace('\\', "/"));
                    Some([named.clone(), format!("{named}/**")])
                })
                .flatten()
                .collect();
            if !scratch.is_empty()
                && let Ok(paths) = Outputs::from_paths(&scratch)
            {
                source_exclusions.push(paths.clone());
                scratch_paths.push(paths);
            }
        }
        exclude_artifacts(&mut files, &source_exclusions, cache_relative.as_deref());
        Ok(Self {
            files,
            extra_candidates: BTreeSet::new(),
            membership: Mutex::default(),
            membership_prefixes: Mutex::default(),
            source_exclusions,
            scratch: scratch_paths,
            cache_relative,
            projects: ProjectGraph::build(workspace)?,
            roots: workspace
                .projects
                .values()
                .map(|project| (project.root.clone(), project.name.clone()))
                .collect(),
            source_ignore: Arc::new(SourceIgnore::new(&workspace.root)?),
            generated_tasks: graph
                .tasks
                .values()
                .filter_map(|task| {
                    let outputs = Outputs::new(workspace, task).ok()?;
                    outputs.is_explicit().then(|| (task.clone(), outputs))
                })
                .collect(),
            task_dependencies: graph
                .tasks
                .iter()
                .map(|(id, task)| (id.clone(), task.dependencies.clone()))
                .collect(),
            servers: graph
                .tasks
                .keys()
                .map(|id| (id.clone(), servers(graph, id)))
                .collect(),
            canonical_root,
            workspace_prefix,
            patterns: Mutex::default(),
            digests: Mutex::new(digests),
            digests_changed: Default::default(),
            ignored_files: Mutex::default(),
            directories: Mutex::default(),
            runtime: Mutex::default(),
            lockfile: Mutex::new(lockfile),
            dependency_outputs: Mutex::default(),
            outputs_written: Default::default(),
        })
    }

    /// Restrict directory checks to the positive fileset prefixes a task reads.
    fn membership_prefixes(&self, workspace: &Workspace, task: &Task) -> Result<Arc<Vec<PathBuf>>> {
        let mut prefixes = self.membership_prefixes.lock().unwrap();
        if let Some(prefixes) = prefixes.get(&task.id) {
            return Ok(prefixes.clone());
        }
        let empty = BTreeSet::new();
        let cancelled = AtomicBool::new(false);
        let mut resolver = Resolver::new(self, workspace, None, &cancelled, &empty);
        resolver.task_inputs(task)?;
        let paths = Arc::new(
            resolver
                .scopes
                .values()
                .flat_map(|scope| &scope.patterns)
                .filter(|pattern| !pattern.excluded)
                .map(|pattern| &pattern.prefix)
                .chain(resolver.json_globs.iter().map(|glob| &glob.prefix))
                .map(|prefix| workspace.root.join(prefix))
                .collect(),
        );
        prefixes.insert(task.id.clone(), Arc::clone(&paths));
        Ok(paths)
    }

    /// Reuse membership while source directories and listing policy are unchanged.
    /// Content changes are checked separately by the file digest cache.
    #[cfg(test)]
    fn current_files(&self, root: &Path) -> Result<Arc<BTreeSet<String>>> {
        Ok(self.current_files_for(root, None, "test")?.files)
    }

    /// Refresh candidates as needed, returning their policy in the same snapshot.
    fn current_files_for(
        &self,
        root: &Path,
        prefixes: Option<&[PathBuf]>,
        task: &str,
    ) -> Result<Candidates> {
        let requested = Instant::now();
        loop {
            let previous = self.membership.lock().unwrap().clone();
            // Immutable entries let independent fingerprints validate their
            // directory stamps concurrently. Only a refresh needs serialization.
            let (unchanged, settled) = match &previous {
                Some(entry) => entry.state(prefixes)?,
                None => (false, false),
            };
            if settled && previous.as_ref().unwrap().settled {
                return Ok(previous.as_ref().unwrap().candidates());
            }
            // A refresh holds this lock while it lists the workspace, so time
            // spent here is time waiting for another task's listing.
            let waiting = crate::profile::span(task, "inventory_wait");
            let mut cached = self.membership.lock().unwrap();
            drop(waiting);
            // A listing that began after this call reflects every change made
            // before it, so it is as current as one made now. Tasks queued
            // behind a refresh share the next one instead of each listing the
            // workspace in turn.
            if let Some(entry) = &*cached
                && entry.listed.is_some_and(|listed| listed >= requested)
            {
                return Ok(entry.candidates());
            }
            let current = match (&previous, &*cached) {
                (Some(previous), Some(current)) => Arc::ptr_eq(previous, current),
                (None, None) => true,
                _ => false,
            };
            if !current {
                // Another fingerprint refreshed while this one validated.
                // Recheck that newer inventory before making any replacement.
                continue;
            }
            drop(previous);
            let _listing = crate::profile::span(task, "inventory_list");
            let listed = Instant::now();
            // Recent listing policies may conceal edits on coarse filesystems.
            // Re-list sources while they settle, then rebuild the directory inventory
            // once before enabling reuse (including any newly created empty dirs).
            // Recent directories are checked by freshly reading their child names.
            let rebuilt = !unchanged || settled;
            let mut membership = if !rebuilt {
                Arc::unwrap_or_clone(cached.take().unwrap())
            } else {
                // Capture directories before listing files, then compare afterward.
                // An addition during listing must not hide behind a newer stamp.
                Membership::new(
                    root,
                    cached.as_ref().map_or(&self.files, |entry| &entry.files),
                    &self.source_ignore,
                    &self.source_exclusions,
                    self.cache_relative.as_deref(),
                    cached
                        .as_ref()
                        .filter(|entry| unchanged && entry.settled)
                        .map(|entry| &entry.git_policies),
                )?
            };
            let mut files = source_files(root)?;
            exclude_artifacts(
                &mut files,
                &self.source_exclusions,
                self.cache_relative.as_deref(),
            );
            let ignore = SourceIgnore::new(root)?;
            files.extend(
                self.extra_candidates
                    .iter()
                    .filter(|path| !ignore.matches(path))
                    .cloned(),
            );
            membership.source_ignore = Arc::new(ignore);
            membership.files = Arc::new(files);
            let candidates = membership.candidates();
            // An unstable inventory or recent policy never enables the fast path.
            // Keep candidates so a rebuild also watches tracked, ignored parents.
            let covered = candidates.files.iter().all(|path| {
                Path::new(path)
                    .ancestors()
                    .skip(1)
                    .all(|parent| membership.stamps.contains_key(&root.join(parent)))
            });
            membership.settled = rebuilt && covered && membership.state(None)?.1;
            membership.listed = Some(listed);
            *cached = Some(Arc::new(membership));
            return Ok(candidates);
        }
    }

    /// Saves the digests of files that still exist, for the next run.
    pub fn save_digests(&self, root: &Path) {
        if !self
            .digests_changed
            .load(std::sync::atomic::Ordering::Relaxed)
        {
            return;
        }
        let digests = self.digests.lock().unwrap();
        let ignored = self.ignored_files.lock().unwrap();
        let entries: BTreeMap<&String, (&Stamp, &String)> = digests
            .iter()
            .filter(|(path, _)| self.files.contains(*path) || ignored.contains(*path))
            .map(|(path, (stamp, digest))| (path, (stamp, digest)))
            .collect();
        let path = digests_path(root);
        let saved = (|| -> Result<()> {
            let directory = path.parent().context("digests have a directory")?;
            std::fs::create_dir_all(directory)?;
            let mut file = tempfile::NamedTempFile::new_in(directory)?;
            {
                let mut writer = std::io::BufWriter::new(file.as_file_mut());
                serde_json::to_writer(&mut writer, &json!({"version": 1, "entries": entries}))?;
                writer.flush()?;
            }
            file.persist(&path)?;
            Ok(())
        })();
        if let Err(error) = saved {
            qk_executor::status!("qk: could not save file digests: {error:#}");
        }
    }

    /// `paths::safe_parents`, checking each directory once per run.
    fn safe_parents(&self, root: &Path, path: &str) -> Result<()> {
        paths::validate_path(path)?;
        let mut current = root.to_owned();
        for part in Path::new(path)
            .parent()
            .into_iter()
            .flat_map(Path::components)
        {
            current.push(part);
            if self.directories.lock().unwrap().contains(&current) {
                continue;
            }
            match std::fs::symlink_metadata(&current) {
                Ok(metadata) if metadata.file_type().is_symlink() => {
                    bail!("input parent is a symlink: {}", current.display())
                }
                Ok(metadata) if !metadata.is_dir() => {
                    bail!("input parent is not a directory: {}", current.display())
                }
                Ok(_) => {
                    self.directories.lock().unwrap().insert(current.clone());
                }
                Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
                Err(error) => return Err(error.into()),
            }
        }
        Ok(())
    }

    fn installed(&self, root: &Path, task: &str) -> Result<Option<Arc<Installed>>> {
        let absolute = root.join("pnpm-lock.yaml");
        let Ok(metadata) = std::fs::symlink_metadata(&absolute) else {
            return Ok(None);
        };
        if !metadata.is_file() {
            return Ok(None);
        }
        let content = self.digest("pnpm-lock.yaml", &absolute, &metadata)?;
        let mut current = self.lockfile.lock().unwrap();
        if let Some(installed) = &*current
            && installed.content == content
        {
            return Ok(Some(installed.clone()));
        }
        let parsing = crate::profile::span(task, "lockfile_parse");
        let parsed = parse_lockfile(&absolute);
        drop(parsing);
        let Some(installed) = parsed else {
            return Ok(None);
        };
        *current = Some(installed.clone());
        Ok(Some(installed))
    }

    /// Adds paths to the candidate files, such as files deleted since a base
    /// revision.
    pub fn with_candidates(mut self, paths: &[String]) -> Self {
        self.files.extend(
            paths
                .iter()
                .filter(|path| !self.source_ignore.matches(path))
                .cloned(),
        );
        self.extra_candidates.extend(paths.iter().cloned());
        self
    }

    fn pattern(&self, pattern: &str, negated: bool) -> Result<Arc<Pattern>> {
        self.compiled(pattern, negated, false)
    }

    /// A fileset's pattern, see [`Pattern::fileset`].
    fn fileset_pattern(&self, pattern: &str, negated: bool) -> Result<Arc<Pattern>> {
        self.compiled(pattern, negated, true)
    }

    fn compiled(&self, pattern: &str, negated: bool, fileset: bool) -> Result<Arc<Pattern>> {
        let key = (pattern.to_owned(), negated, fileset);
        if let Some(pattern) = self.patterns.lock().unwrap().get(&key) {
            return Ok(pattern.clone());
        }
        let compiled = Arc::new(if fileset {
            Pattern::fileset(pattern, negated)?
        } else {
            Pattern::new(pattern, negated)?
        });
        self.patterns.lock().unwrap().insert(key, compiled.clone());
        Ok(compiled)
    }

    fn digest(&self, path: &str, absolute: &Path, metadata: &std::fs::Metadata) -> Result<String> {
        let stamp = Stamp::new(metadata);
        if let Some((known, digest)) = self.digests.lock().unwrap().get(path)
            && *known == stamp
        {
            return Ok(digest.clone());
        }
        let digest = digest_file(absolute)?;
        // Re-check after reading so a concurrent write is never recorded as settled.
        let after = Stamp::new(&std::fs::symlink_metadata(absolute)?);
        if after == stamp && stamp.settled() {
            self.digests
                .lock()
                .unwrap()
                .insert(path.to_owned(), (stamp, digest.clone()));
            self.digests_changed
                .store(true, std::sync::atomic::Ordering::Relaxed);
        }
        Ok(digest)
    }

    /// `task`'s output files that are not directories, as listed since the
    /// last task that could have written them was done.
    fn dependency_outputs(
        &self,
        workspace: &Workspace,
        task: &Task,
    ) -> Result<Arc<DependencyOutputs>> {
        if let Some(outputs) = self.dependency_outputs.lock().unwrap().get(&task.id) {
            return Ok(outputs.clone());
        }
        let written = self
            .outputs_written
            .load(std::sync::atomic::Ordering::SeqCst);
        let outputs = Arc::new(self.fresh_dependency_outputs(workspace, task)?);
        let mut listed = self.dependency_outputs.lock().unwrap();
        if self
            .outputs_written
            .load(std::sync::atomic::Ordering::SeqCst)
            != written
        {
            return Ok(outputs);
        }
        Ok(listed.entry(task.id.clone()).or_insert(outputs).clone())
    }

    /// Re-list artifacts for verification, without reusing earlier content values.
    fn fresh_dependency_outputs(
        &self,
        workspace: &Workspace,
        task: &Task,
    ) -> Result<DependencyOutputs> {
        let declared = Outputs::new(workspace, task)?;
        let mut files = Vec::new();
        for entry in declared.entries(&workspace.root)? {
            let (path, metadata) = entry?;
            if !metadata.is_dir() {
                files.push(path);
            }
        }
        Ok(DependencyOutputs {
            anchors: declared.anchors().map(str::to_owned).collect(),
            files,
            values: Mutex::default(),
        })
    }

    /// Drops the listings `task` may have changed, once it is done. Without
    /// its outputs, every listing goes.
    pub(crate) fn outputs_written(&self, workspace: &Workspace, task: &Task) {
        let anchors: Option<Vec<String>> = Outputs::new(workspace, task)
            .ok()
            .filter(Outputs::is_explicit)
            .map(|outputs| outputs.anchors().map(str::to_owned).collect());
        let overlap = |a: &str, b: &str| {
            a == b
                || b.strip_prefix(a).is_some_and(|rest| rest.starts_with('/'))
                || a.strip_prefix(b).is_some_and(|rest| rest.starts_with('/'))
        };
        let mut listed = self.dependency_outputs.lock().unwrap();
        self.outputs_written
            .fetch_add(1, std::sync::atomic::Ordering::SeqCst);
        listed.retain(|_, outputs| {
            anchors.as_ref().is_some_and(|written| {
                !written
                    .iter()
                    .any(|a| outputs.anchors.iter().any(|b| overlap(a, b)))
            })
        });
    }

    /// A file an `includeIgnored` fileset read, by the content it points to
    /// wherever that is, as Nx reads it; `None` when it is gone.
    fn ignored_value(&self, root: &Path, path: &str) -> Result<Option<Value>> {
        let absolute = root.join(path);
        let metadata = match std::fs::metadata(&absolute) {
            Ok(metadata) if metadata.is_file() => metadata,
            Ok(_) => return Ok(None),
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
            Err(error) => return Err(error.into()),
        };
        let mode = crate::store::mode(&metadata) & 0o111 != 0;
        self.ignored_files.lock().unwrap().insert(path.to_owned());
        Ok(Some(
            json!({"content":self.digest(path, &absolute, &metadata)?, "mode":mode}),
        ))
    }

    /// A file a recording read, keyed as an input file is.
    pub(crate) fn recorded_value(&self, root: &Path, path: &str) -> Result<Value> {
        self.file_value(root, path)
    }

    fn file_value(&self, root: &Path, path: &str) -> Result<Value> {
        self.file_value_with_links(root, path, &mut BTreeSet::new())
    }

    fn file_value_with_links(
        &self,
        root: &Path,
        path: &str,
        visiting: &mut BTreeSet<PathBuf>,
    ) -> Result<Value> {
        self.safe_parents(root, path)?;
        let absolute = root.join(path);
        let metadata = std::fs::symlink_metadata(&absolute)?;
        if metadata.file_type().is_symlink() {
            let target = std::fs::read_link(&absolute)?;
            // A dangling link is keyed as such, so the key changes once it resolves.
            let Ok(resolved) = absolute.canonicalize() else {
                return Ok(json!({"link":target, "dangling":true}));
            };
            let Ok(relative) = resolved.strip_prefix(&self.canonical_root) else {
                bail!("input symlink resolves outside the workspace: {path}");
            };
            if resolved.is_file() {
                let metadata = std::fs::metadata(&resolved)?;
                let key = paths::relative(Path::new(""), relative)?;
                return Ok(
                    json!({"link":target, "content":self.digest(&key, &resolved, &metadata)?,
                    "mode":crate::store::mode(&metadata) & 0o111 != 0}),
                );
            }
            let relative = paths::relative(Path::new(""), relative)?;
            if relative.is_empty() {
                bail!("input symlink resolves to the workspace root: {path}");
            }
            if !visiting.insert(resolved.clone()) {
                bail!("directory input symlink cycle: {path}");
            }
            let mut contents = BTreeMap::new();
            // Selecting the link explicitly reads its target, even when source
            // discovery ignores that target or another link is nested inside it.
            for entry in walkdir::WalkDir::new(&resolved).follow_links(false) {
                let entry = entry?;
                if entry.file_type().is_dir() {
                    continue;
                }
                let file = paths::relative(&self.canonical_root, entry.path())?;
                let value = self.file_value_with_links(&self.canonical_root, &file, visiting)?;
                contents.insert(
                    file.strip_prefix(&relative).unwrap_or(&file).to_owned(),
                    value,
                );
            }
            visiting.remove(&resolved);
            return Ok(json!({"link":target, "directory":contents}));
        }
        if !metadata.is_file() {
            bail!("input is not a regular file: {path}");
        }
        // Only the executable bit, which is all git records: other permission
        // bits follow the checkout's umask and would keep machines apart.
        let mode = crate::store::mode(&metadata) & 0o111 != 0;
        Ok(json!({"content":self.digest(path, &absolute, &metadata)?, "mode":mode}))
    }
}

/// Reads and parses a pnpm lockfile, `None` when there is none. One qk cannot
/// read is reported, and kept as unreadable so tasks key its whole content.
fn parse_lockfile(path: &Path) -> Option<Arc<Installed>> {
    let text = std::fs::read_to_string(path).ok()?;
    let lockfile = match Lockfile::parse(&text) {
        Ok(lockfile) => Some(lockfile),
        Err(error) => {
            qk_executor::status!("qk: pnpm-lock.yaml: keying tasks by the whole file ({error:#})");
            None
        }
    };
    Some(Arc::new(Installed {
        content: blake3::hash(text.as_bytes()).to_hex().to_string(),
        lockfile,
        digests: Mutex::default(),
    }))
}

fn load_digests(root: &Path) -> HashMap<String, (Stamp, String)> {
    #[derive(serde::Deserialize)]
    struct Saved {
        version: u32,
        entries: HashMap<String, (Stamp, String)>,
    }
    std::fs::read(digests_path(root))
        .ok()
        .and_then(|bytes| serde_json::from_slice::<Saved>(&bytes).ok())
        .filter(|saved| saved.version == 1)
        .map(|saved| saved.entries)
        .unwrap_or_default()
}

/// Apply the same source policy to startup and refreshed file membership.
/// Remove declared artifacts and cache storage from a refreshed source listing.
fn exclude_artifacts(files: &mut BTreeSet<String>, outputs: &[Outputs], cache: Option<&Path>) {
    let mut generated = BTreeSet::new();
    for outputs in outputs {
        for anchor in outputs.anchors() {
            generated.extend(
                under(files, anchor)
                    .filter(|path| outputs.matches(path))
                    .cloned(),
            );
        }
    }
    files.retain(|path| {
        !generated.contains(path) && cache.is_none_or(|cache| !Path::new(path).starts_with(cache))
    });
}

/// Files equal to `prefix` or below it, using the sorted order of the set.
impl Snapshot {
    /// The project whose root most specifically contains `path`, as Nx assigns
    /// files to projects.
    fn owner(&self, path: &str) -> Option<&str> {
        let mut path = path;
        loop {
            if let Some(project) = self.roots.get(path) {
                return Some(project);
            }
            match path.rfind('/') {
                Some(slash) => path = &path[..slash],
                None if path != "." => path = ".",
                None => return None,
            }
        }
    }
}

fn under<'a>(files: &'a BTreeSet<String>, prefix: &'a str) -> impl Iterator<Item = &'a String> {
    files
        .range::<str, _>((
            std::ops::Bound::Included(prefix),
            std::ops::Bound::Unbounded,
        ))
        .take_while(move |path| path.starts_with(prefix))
        .filter(move |path| path.len() == prefix.len() || path.as_bytes()[prefix.len()] == b'/')
}

/// Compiled root ignore rules used by input discovery and project watching.
pub struct SourceIgnore(ignore::gitignore::Gitignore);

impl SourceIgnore {
    /// Root ignore rules shared by caching and watch, including tracked files.
    pub fn new(root: &Path) -> Result<Self> {
        let mut builder = ignore::gitignore::GitignoreBuilder::new(root);
        for name in [".gitignore", ".nxignore"] {
            let path = root.join(name);
            if path.is_file()
                && let Some(error) = builder.add(path)
            {
                return Err(error.into());
            }
        }
        Ok(Self(builder.build()?))
    }

    fn matches_directory(&self, path: &str) -> bool {
        self.matches(path) || self.0.matched(path, true).is_ignore()
    }

    /// Whether a workspace-relative file or its parent is ignored.
    pub fn matches(&self, path: &str) -> bool {
        // A file whitelist cannot reinclude it beneath an excluded directory.
        Path::new(path)
            .ancestors()
            .skip(1)
            .take_while(|parent| !parent.as_os_str().is_empty())
            .any(|parent| self.0.matched(parent, true).is_ignore())
            || self.0.matched(path, false).is_ignore()
    }
}

/// Source files visible to Nx, with runner state and root ignore rules removed.
pub fn source_files(root: &Path) -> Result<BTreeSet<String>> {
    let lines =
        |output: std::io::Result<std::process::Output>| -> Option<Result<BTreeSet<String>>> {
            let output = output.ok().filter(|output| output.status.success())?;
            Some(
                output
                    .stdout
                    .split(|byte| *byte == 0)
                    .filter(|path| !path.is_empty())
                    .map(|path| {
                        String::from_utf8(path.to_vec()).context("input paths must be UTF-8")
                    })
                    .collect(),
            )
        };
    // Tracked files deleted from the working tree are listed as cached; git
    // names them in a second listing, which is cheaper than checking each file.
    // Skip-worktree entries are listed whether or not they are on disk and never
    // as deleted, so those few are checked; `-v` tags them `S`.
    let (listed, deleted) = if root.join(".nxignore").is_file() {
        // Nx negations can reinclude Git-ignored files, so this policy needs
        // the walker regardless of what Git lists. Avoid launching Git here.
        (None, None)
    } else {
        std::thread::scope(|scope| {
            let deleted =
                scope.spawn(|| paths::git(root, &["ls-files", "--deleted", "-z", "--", "."]));
            let listed = paths::git(
                root,
                &[
                    "ls-files",
                    "-v",
                    "--cached",
                    "--others",
                    "--exclude-standard",
                    "-z",
                    "--",
                    ".",
                ],
            );
            (
                lines(listed),
                lines(deleted.join().expect("git listing thread panicked")),
            )
        })
    };
    let candidates = match (listed, deleted) {
        (Some(listed), Some(deleted)) => {
            let deleted = deleted?;
            let mut files = BTreeSet::new();
            for entry in listed? {
                let Some((tag, path)) = entry.split_once(' ') else {
                    bail!("unexpected git ls-files entry {entry:?}");
                };
                let absent =
                    matches!(tag, "S" | "s") && std::fs::symlink_metadata(root.join(path)).is_err();
                if !absent && !deleted.contains(path) {
                    files.insert(path.to_owned());
                }
            }
            files
        }
        _ => {
            let mut files = BTreeSet::new();
            for entry in ignore::WalkBuilder::new(root)
                .hidden(false)
                .parents(false)
                .git_global(false)
                .require_git(false)
                .ignore(false)
                .add_custom_ignore_filename(".nxignore")
                .follow_links(false)
                .filter_entry(|entry| {
                    !matches!(
                        entry.file_name().to_str(),
                        Some(".git" | ".qk" | "node_modules")
                    )
                })
                .build()
            {
                let entry = entry?;
                if entry.file_type().is_some_and(|kind| !kind.is_dir()) {
                    files.insert(paths::relative(root, entry.path())?);
                }
            }
            files
        }
    };
    let ignore = SourceIgnore::new(root)?;
    Ok(candidates
        .into_iter()
        .filter(|path| {
            !ignore.matches(path)
                && !path
                    .split('/')
                    .any(|part| matches!(part, ".git" | ".qk" | "node_modules"))
        })
        .collect())
}

/// The text of `path` as a `json` input keys it: only `fields` when given,
/// without `exclude`. A `.yaml` or `.yml` file is read as YAML, and any other
/// as JSON or JSONC. `None` when it cannot be read so.
pub(crate) fn json_projection(path: &str, text: &str, fields: &JsonFields) -> Option<Value> {
    let mut value: Value = if path.ends_with(".yaml") || path.ends_with(".yml") {
        serde_yaml_ng::from_str(text).ok()?
    } else {
        jsonc_parser::parse_to_serde_value(text, &Default::default()).ok()?
    };
    if let Some(fields) = &fields.fields {
        let mut kept = json!({});
        for field in fields {
            if let Some(found) = json_path(&value, field) {
                set_json_path(&mut kept, field, found.clone());
            }
        }
        value = kept;
    }
    for field in &fields.exclude {
        remove_json_path(&mut value, field);
    }
    Some(value)
}

fn json_path<'v>(value: &'v Value, path: &str) -> Option<&'v Value> {
    path.split('.')
        .try_fold(value, |value, part| value.get(part))
}

fn set_json_path(target: &mut Value, path: &str, value: Value) {
    let mut parts = path.split('.').peekable();
    let mut current = target;
    while let Some(part) = parts.next() {
        let Value::Object(object) = current else {
            return;
        };
        if parts.peek().is_none() {
            object.insert(part.to_owned(), value);
            return;
        }
        current = object.entry(part).or_insert_with(|| json!({}));
    }
}

fn remove_json_path(target: &mut Value, path: &str) {
    let (parent, last) = match path.rsplit_once('.') {
        Some((parent, last)) => (Some(parent), last),
        None => (None, path),
    };
    let parent = match parent {
        Some(parent) => parent
            .split('.')
            .try_fold(&mut *target, |value, part| value.get_mut(part)),
        None => Some(target),
    };
    if let Some(Value::Object(object)) = parent {
        object.remove(last);
    }
}

struct FilePattern {
    matcher: Arc<Pattern>,
    prefix: String,
    /// The glob after `prefix`, the literal directory it starts with; `None`
    /// when the pattern names one path.
    rest: Option<String>,
    excluded: bool,
    /// The project a project fileset selects the files of.
    owner: Option<String>,
}

/// The patterns of a task's declared filesets, by the scope they select in:
/// kept to tell whether a file where there is none would be selected, as
/// [`Coverage`] asks.
#[derive(Default)]
pub struct Selection {
    scopes: Vec<Vec<FilePattern>>,
}

impl Selection {
    /// Whether a file at `path` would be selected, gitignore aside: an
    /// included pattern of a scope matches it, and none of that scope's
    /// exclusions does.
    fn selects(&self, snapshot: &Snapshot, path: &str) -> bool {
        let applies = |pattern: &FilePattern| {
            pattern.matcher.is_match(path)
                && (pattern.owner.is_none() || snapshot.owner(path) == pattern.owner.as_deref())
        };
        self.scopes.iter().any(|patterns| {
            patterns
                .iter()
                .any(|pattern| !pattern.excluded && applies(pattern))
                && !patterns
                    .iter()
                    .any(|pattern| pattern.excluded && applies(pattern))
        })
    }

    /// Whether every entry `directory` could hold, at any depth, would be
    /// selected, gitignore aside: an included pattern of a scope takes all of
    /// what is under a directory at or above it, and none of that scope's
    /// exclusions reaches into it. `""` is the workspace root.
    fn selects_every_entry(&self, snapshot: &Snapshot, directory: &str) -> bool {
        let within = |prefix: &str| {
            prefix.is_empty()
                || directory == prefix
                || directory
                    .strip_prefix(prefix)
                    .is_some_and(|rest| rest.starts_with('/'))
        };
        let reaches = |prefix: &str| {
            within(prefix)
                || directory.is_empty()
                || prefix
                    .strip_prefix(directory)
                    .is_some_and(|rest| rest.starts_with('/'))
        };
        let owner = snapshot.owner(if directory.is_empty() { "." } else { directory });
        self.scopes.iter().any(|patterns| {
            patterns.iter().any(|pattern| {
                !pattern.excluded
                    && within(&pattern.prefix)
                    && matches!(pattern.rest.as_deref(), Some("**" | "**/*"))
                    && (pattern.owner.is_none() || owner == pattern.owner.as_deref())
            }) && !patterns
                .iter()
                .any(|pattern| pattern.excluded && reaches(&pattern.prefix))
        })
    }
}

/// What a task's declared key holds of the workspace's files, to tell
/// whether it keys everything a recording says the task read, looked for
/// and listed: when it does, a result under the declared key is as sound as
/// qk's keys are without recordings. A file qk keys by part of its content,
/// such as a dependency's `package.json` or a `json` input, counts as keyed,
/// as it does for every task's key.
pub(crate) struct Coverage {
    resolved: Resolved,
    /// Each `dependentTasksOutputFiles` glob, with the declared outputs of
    /// the tasks it reads.
    dependency_outputs: Vec<(Arc<Pattern>, Vec<Outputs>)>,
}

/// What `task`'s declared key covers: see [`Coverage`].
pub(crate) fn coverage(
    snapshot: &Snapshot,
    workspace: &Workspace,
    graph: &TaskGraph,
    task: &Task,
    prepared: &PreparedTask,
    cancelled: &AtomicBool,
) -> Result<Coverage> {
    let resolved = resolve(snapshot, workspace, task, Some(prepared), cancelled)?;
    let selections: Vec<(String, bool)> = resolved
        .dependency_output_inputs()
        .map(|(pattern, transitive)| (pattern.to_owned(), transitive))
        .collect();
    let mut dependency_outputs = Vec::new();
    for (pattern, transitive) in selections {
        let matcher = snapshot.pattern(&pattern, false)?;
        let mut selected = task.dependencies.clone();
        if transitive {
            let mut pending = selected.clone();
            while let Some(id) = pending.pop_first() {
                for dependency in &graph.tasks[&id].dependencies {
                    if selected.insert(dependency.clone()) {
                        pending.insert(dependency.clone());
                    }
                }
            }
        }
        let mut outputs = Vec::new();
        for id in selected {
            let declared = Outputs::new(workspace, &graph.tasks[&id])?;
            if declared.declared() {
                outputs.push(declared);
            }
        }
        dependency_outputs.push((matcher, outputs));
    }
    Ok(Coverage {
        resolved,
        dependency_outputs,
    })
}

impl Coverage {
    /// Whether the declared key holds the content of the file at `path`, or
    /// what of it reaches tasks, by its declared inputs or by what qk adds.
    fn keyed(&self, path: &str) -> bool {
        let inferred = &self.resolved.inferred;
        self.resolved.is_whole_file(path)
            || self.resolved.is_json_input(path)
            || inferred.manifests.contains_key(path)
            || inferred.tsconfig.as_deref() == Some(path)
            || inferred.settings.contains(path)
            || inferred.project.contains(path)
            || (inferred.workspace_file && path == "pnpm-workspace.yaml")
            || (inferred.lockfile.is_some() && path == "pnpm-lock.yaml")
            || self.dependency_outputs.iter().any(|(matcher, outputs)| {
                matcher.is_match(path) && outputs.iter().any(|outputs| outputs.matches(path))
            })
    }

    /// Whether the declared key covers every path of `set`: each file read
    /// or found is keyed, or a directory found holds a keyed file, so that
    /// its going changes the key; a file created where one was looked for,
    /// or where one read is gone since, would be selected, and is neither
    /// gitignored nor a declared output;
    /// and every entry a listed directory could gain or lose that is not
    /// gitignored would be selected, the directory being no declared output.
    /// A declared output never enters the declared files, unless a
    /// `dependentTasksOutputFiles` input keys it.
    /// `output` says whether a path is a declared output of any target.
    pub(crate) fn covers(
        &self,
        snapshot: &Snapshot,
        root: &Path,
        set: &crate::recorded::PathSet,
        output: &dyn Fn(&str) -> bool,
    ) -> bool {
        self.uncovered(snapshot, root, set, output).next().is_none()
    }

    /// The paths of `set` the declared key does not cover, as
    /// [`Self::covers`] judges them, each with what the task did to it:
    /// `read`, `found`, `looked for` or `listed`.
    pub(crate) fn uncovered<'a>(
        &'a self,
        snapshot: &'a Snapshot,
        root: &'a Path,
        set: &'a crate::recorded::PathSet,
        output: &'a dyn Fn(&str) -> bool,
    ) -> impl Iterator<Item = (&'a str, &'static str)> + 'a {
        let selection = &self.resolved.declared.selection;
        fn directory(path: &str) -> &str {
            if path == "." { "" } else { path }
        }
        let holds_keyed = move |path: &str| {
            let path = directory(path);
            if path.is_empty() {
                return self.resolved.whole_files().next().is_some();
            }
            under(&self.resolved.declared.files, path).next().is_some()
                || under(&self.resolved.inferred.files, path).next().is_some()
        };
        // Whether a file created at `path` would enter the declared key.
        let selected = move |path: &str| {
            !snapshot.source_ignore.matches(path)
                && !output(path)
                && selection.selects(snapshot, path)
        };
        // A file the task read that is gone since is keyed as one it looked
        // for and did not find: its coming back changes the key. A path it
        // found may have been a directory, which the declared key leaves out
        // while empty, so its going is not judged so.
        let gone = move |path: &str| {
            root.join(path).symlink_metadata().is_err_and(|error| {
                matches!(
                    error.kind(),
                    std::io::ErrorKind::NotFound | std::io::ErrorKind::NotADirectory
                )
            })
        };
        let reads = set
            .reads
            .iter()
            .filter(move |path| !(self.keyed(path) || (gone(path) && selected(path))))
            .map(|path| (path.as_str(), "read"));
        let present = set
            .present
            .iter()
            .filter(move |path| {
                !(self.keyed(path) || (root.join(path).is_dir() && holds_keyed(path)))
            })
            .map(|path| (path.as_str(), "found"));
        let absent = set
            .absent
            .iter()
            .filter(move |path| !(self.keyed(path) || selected(path)))
            .map(|path| (path.as_str(), "looked for"));
        let listings = set
            .listings
            .iter()
            .filter(move |path| {
                let path = directory(path);
                !((path.is_empty() || !output(path))
                    && selection.selects_every_entry(snapshot, path))
            })
            .map(|path| (path.as_str(), "listed"));
        reads.chain(present).chain(absent).chain(listings)
    }
}

/// A `json` glob, kept to select dependency outputs once they are written.
struct JsonGlob {
    matcher: Arc<Pattern>,
    prefix: String,
    /// The project whose files it selects, or `None` for the workspace's.
    owner: Option<String>,
    fields: JsonFields,
}

#[derive(Default)]
struct FileSelection {
    patterns: Vec<FilePattern>,
    included: BTreeSet<String>,
    excluded: BTreeSet<String>,
}

#[derive(PartialEq, Eq, PartialOrd, Ord)]
enum FileScope {
    Workspace,
    Project(String),
}

struct Resolver<'a> {
    workspace: &'a Workspace,
    snapshot: &'a Snapshot,
    candidates: &'a BTreeSet<String>,
    selected: BTreeSet<String>,
    scopes: BTreeMap<FileScope, FileSelection>,
    values: BTreeMap<String, Value>,
    json_fields: BTreeMap<String, Vec<JsonFields>>,
    json_globs: Vec<JsonGlob>,
    named_stack: Vec<(String, String)>,
    /// Dependency named inputs already expanded for `^` inputs.
    expanded: BTreeSet<(String, String)>,
    external: BTreeSet<String>,
    /// `includeIgnored` globs, resolved, by the project that reads them and
    /// whether they came with `dependencies: true`: each is one group, whose
    /// negations filter all of its positives.
    ignored: BTreeMap<(String, bool), Vec<String>>,
    external_declared: bool,
    /// Every project whose inputs were read, as Nx hashes each one's
    /// configuration.
    projects: BTreeSet<String>,
    /// `None` resolves which inputs a task has without evaluating env or
    /// runtime inputs.
    prepared: Option<&'a PreparedTask>,
    cancelled: &'a AtomicBool,
}

impl<'a> Resolver<'a> {
    fn new(
        snapshot: &'a Snapshot,
        workspace: &'a Workspace,
        prepared: Option<&'a PreparedTask>,
        cancelled: &'a AtomicBool,
        candidates: &'a BTreeSet<String>,
    ) -> Self {
        Self {
            workspace,
            snapshot,
            candidates,
            selected: BTreeSet::new(),
            scopes: BTreeMap::new(),
            values: BTreeMap::new(),
            json_fields: BTreeMap::new(),
            json_globs: Vec::new(),
            named_stack: Vec::new(),
            expanded: BTreeSet::new(),
            external: BTreeSet::new(),
            ignored: BTreeMap::new(),
            external_declared: false,
            projects: BTreeSet::new(),
            prepared,
            cancelled,
        }
    }

    fn task_inputs(&mut self, task: &Task) -> Result<()> {
        self.projects.insert(task.project.clone());
        for input in declared_inputs(task) {
            self.input(&task.project, &input)?;
        }
        // As in Nx, a continuous task serving this one counts its own inputs
        // here.
        let snapshot = self.snapshot;
        for (project, inputs) in snapshot.servers.get(&task.id).into_iter().flatten() {
            for input in inputs {
                self.input(project, input)
                    .with_context(|| format!("inputs of {project}, which serves this task"))?;
            }
        }
        Ok(())
    }

    fn input(&mut self, project: &str, input: &Value) -> Result<()> {
        self.projects.insert(project.to_owned());
        // Nx 24's `always` keeps an input in a hash taken from an Ultracache
        // recording. qk hashes no recordings, so the input reads as without it.
        if let Value::Object(object) = input
            && let Some(always) = object.get("always")
        {
            // As in Nx, `always` keeps an input on purpose, so a project
            // pattern it selects nothing with is a mistake.
            if always.as_bool().context("input always must be boolean")?
                && let Some(Value::String(name)) = object.get("input")
                && let Some(projects) = object.get("projects")
            {
                let patterns: Vec<String> = match projects {
                    Value::String(pattern) => vec![pattern.clone()],
                    other => serde_json::from_value(other.clone())
                        .context("input projects must be a string or an array")?,
                };
                for pattern in patterns.iter().filter(|pattern| {
                    !pattern.starts_with('!')
                        && !matches!(pattern.as_str(), "self" | "dependencies")
                }) {
                    if qk_graph::select_projects(
                        &self.workspace.projects,
                        std::slice::from_ref(pattern),
                        &[],
                    )?
                    .is_empty()
                    {
                        bail!(
                            "the input {{\"input\": \"{name}\", \"projects\"}} with \"always\": true selects \"{pattern}\", which matches no project"
                        );
                    }
                }
            }
            let mut object = object.clone();
            object.remove("always");
            return self.input(project, &Value::Object(object));
        }
        match input {
            // As in Nx, `^{projectRoot}/…` and `^{workspaceRoot}/…` are a
            // fileset of every project the project depends on, directly or
            // not, and `^name` is `name` of each of them.
            Value::String(name)
                if name.starts_with("^{projectRoot}") || name.starts_with("^{workspaceRoot}") =>
            {
                self.dependency_fileset(project, &name[1..])?;
            }
            Value::String(name) if name.starts_with('^') => {
                self.dependencies_named(project, &name[1..])?;
            }
            // The object spellings of named inputs, as Nx reads them.
            Value::Object(object)
                if object.contains_key("input") && !object.contains_key("fileset") =>
            {
                let name = object["input"]
                    .as_str()
                    .context("input must name a named input")?;
                let projects = object.get("projects");
                let dependencies = object.get("dependencies") == Some(&json!(true))
                    || projects == Some(&json!("dependencies"));
                let listed = projects.filter(|projects| {
                    **projects != json!("self") && **projects != json!("dependencies")
                });
                if (dependencies || listed.is_some()) && !self.named_stack.is_empty() {
                    bail!("named inputs can only refer to named inputs of their own project");
                }
                if let Some(listed) = listed {
                    let patterns: Vec<String> = match listed {
                        Value::String(pattern) => vec![pattern.clone()],
                        other => serde_json::from_value(other.clone())
                            .context("input projects must be a string or an array")?,
                    };
                    // Nx's native hasher reads these patterns, not the
                    // `findMatchingProjects` the rest of Nx uses.
                    for selected in qk_config::find_matching_projects(
                        &patterns,
                        &self.workspace.projects,
                        qk_config::Reader::Native,
                    ) {
                        // As in Nx 24, `dependencies: true` beside `projects`
                        // is each selected project's `^name`, not its own.
                        if dependencies {
                            self.dependencies_named(&selected, name)?;
                        } else if self.expanded.insert((selected.clone(), name.to_owned())) {
                            self.named(&selected, name)?;
                        }
                    }
                } else if dependencies {
                    self.dependencies_named(project, name)?;
                } else {
                    self.named(project, name)?;
                }
            }
            Value::Object(object) if object.contains_key("fileset") => {
                if let Some(key) = object.keys().find(|key| {
                    !matches!(key.as_str(), "fileset" | "dependencies" | "includeIgnored")
                }) {
                    bail!("unsupported fileset input field {key:?}");
                }
                let flag = |name: &str| {
                    object
                        .get(name)
                        .map(|value| {
                            value
                                .as_bool()
                                .with_context(|| format!("{name} must be boolean"))
                        })
                        .transpose()
                        .map(Option::unwrap_or_default)
                };
                let (dependencies, include_ignored) =
                    (flag("dependencies")?, flag("includeIgnored")?);
                let pattern = object["fileset"]
                    .as_str()
                    .context("fileset input must be a glob")?
                    .to_owned();
                validate_fileset(&pattern)?;
                match (dependencies, include_ignored) {
                    (false, false) => self.fileset(project, &pattern)?,
                    (true, false) => self.dependency_fileset(project, &pattern)?,
                    (false, true) => self.ignored_fileset(project, &pattern, false),
                    (true, true) => {
                        if !self.named_stack.is_empty() {
                            bail!(
                                "named inputs can only refer to named inputs of their own project"
                            );
                        }
                        for dependency in self.dependency_closure(project) {
                            self.ignored_fileset(&dependency, &pattern, true);
                        }
                    }
                }
            }
            Value::Object(object)
                if object.len() == 1 && object.contains_key("workingDirectory") =>
            {
                let mode = object["workingDirectory"].as_str().unwrap_or_default();
                let directory = std::env::current_dir()?;
                let value = match mode {
                    "absolute" => directory.to_string_lossy().into_owned(),
                    "relative" => {
                        let root = self.workspace.root.canonicalize()?;
                        let directory = directory.canonicalize()?;
                        paths::relative(&root, &directory)
                            .unwrap_or_else(|_| directory.to_string_lossy().into_owned())
                    }
                    _ => bail!("workingDirectory must be \"relative\" or \"absolute\""),
                };
                self.values
                    .insert(format!("workingDirectory:{mode}"), json!(value));
            }
            Value::Object(object) if object.contains_key("json") => {
                self.json(project, object)?;
            }
            // As in Nx, a string names a named input when there is one, and is
            // a fileset otherwise.
            Value::String(name) if self.has_named(project, name) => self.named(project, name)?,
            Value::String(pattern) => {
                validate_fileset(pattern)?;
                self.fileset(project, pattern)?
            }
            Value::Object(object) if object.len() == 1 && object.contains_key("env") => {
                let name = object["env"]
                    .as_str()
                    .context("env input must name a variable")?;
                let Some(prepared) = self.prepared else {
                    self.values.insert(format!("env:{name}"), Value::Null);
                    return Ok(());
                };
                let value = prepared
                    .env
                    .get(std::ffi::OsStr::new(name))
                    .map(|value| {
                        value
                            .to_str()
                            .map(str::to_owned)
                            .context("declared env input must be UTF-8")
                    })
                    .transpose()?;
                self.values.insert(format!("env:{name}"), json!(value));
            }
            Value::Object(object) if object.len() == 1 && object.contains_key("runtime") => {
                let command = object["runtime"]
                    .as_str()
                    .context("runtime input must be a command")?;
                let Some(prepared) = self.prepared else {
                    self.values
                        .insert(format!("runtime:{command}"), Value::Null);
                    return Ok(());
                };
                let memo = RuntimeKey {
                    command: command.into(),
                    environment: prepared.runtime_env.clone(),
                };
                let slot = self
                    .snapshot
                    .runtime
                    .lock()
                    .unwrap()
                    .entry(memo)
                    .or_default()
                    .clone();
                let mut saved = slot.lock().unwrap();
                if let Some(value) = saved.as_ref() {
                    self.values
                        .insert(format!("runtime:{command}"), value.clone());
                    return Ok(());
                }
                let _profile = crate::profile::span(command, "runtime");
                let mut prepared = prepared.clone();
                prepared.env = prepared.runtime_env.clone();
                prepared.execution.clear();
                prepared.node_path = None;
                prepared.commands = vec![command.into()];
                prepared.cwd = self.workspace.root.clone();
                prepared.parallel = false;
                // Its output is hashed, so it must not depend on a terminal.
                prepared.pseudo_terminal = false;
                let log = tempfile::NamedTempFile::new()?;
                let capture = Capture::new(Some(log.as_file().try_clone()?), Display::Hidden);
                if execute_captured(&prepared, self.cancelled, Some(&capture))? != Outcome::Success
                {
                    bail!("runtime input did not succeed");
                }
                let mut stdout = blake3::Hasher::new();
                let mut stderr = blake3::Hasher::new();
                read_capture(File::open(log.path())?, |error, bytes| {
                    if error {
                        stderr.update(bytes);
                    } else {
                        stdout.update(bytes);
                    }
                    Ok(())
                })?;
                let value = json!([
                    stdout.finalize().to_hex().to_string(),
                    stderr.finalize().to_hex().to_string()
                ]);
                *saved = Some(value.clone());
                self.values.insert(format!("runtime:{command}"), value);
            }
            Value::Object(object) if object.contains_key("dependentTasksOutputFiles") => {
                if object
                    .keys()
                    .any(|key| !matches!(key.as_str(), "dependentTasksOutputFiles" | "transitive"))
                {
                    bail!("unsupported output input field");
                }
                let pattern = object["dependentTasksOutputFiles"]
                    .as_str()
                    .context("dependentTasksOutputFiles must be a glob")?;
                self.snapshot.pattern(pattern, false)?;
                let transitive = object
                    .get("transitive")
                    .map(|value| value.as_bool().context("transitive must be boolean"))
                    .transpose()?
                    .unwrap_or(false);
                // Resolved before execution too, so inspection can display the
                // selection without reading generated files. dependency_keys
                // hashes these files after the dependencies finish.
                let value = self
                    .values
                    .entry(format!("dependentTasksOutputFiles:{pattern}"))
                    .or_insert(json!(false));
                if transitive {
                    *value = json!(true);
                }
            }
            Value::Object(object)
                if object.len() == 1 && object.contains_key("externalDependencies") =>
            {
                let names: Vec<String> =
                    serde_json::from_value(object["externalDependencies"].clone())?;
                // As in Nx, a workspace project is no external dependency.
                if let Some(name) = names
                    .iter()
                    .find(|name| self.workspace.projects.contains_key(*name))
                {
                    if self.snapshot.projects.dependencies[project]
                        .iter()
                        .any(|edge| edge.target == *name)
                    {
                        bail!(
                            "the externalDependency {name:?} of {project} is not an external node and is already a dependency; remove it from the externalDependencies inputs"
                        );
                    }
                    bail!(
                        "the externalDependency {name:?} of {project} is not an external node; if it is a dependency, add it to the project's implicitDependencies"
                    );
                }
                self.external.extend(names);
                self.external_declared = true;
            }
            _ => bail!("unsupported task input declaration"),
        }
        Ok(())
    }

    fn fileset(&mut self, project: &str, pattern: &str) -> Result<()> {
        self.projects.insert(project.to_owned());
        let (exclude, pattern) = pattern
            .strip_prefix('!')
            .map(|pattern| (true, pattern))
            .unwrap_or((false, pattern));
        // Nx hashes workspace files and each project's files in separate
        // scopes, a project's being only the files it owns: those of a project
        // nested in its root are that project's. A fileset is the project's
        // when it starts from `{projectRoot}/`, and the workspace's otherwise,
        // where only one starting from `{workspaceRoot}/` selects anything.
        let (scope, owner) = if pattern.starts_with("{projectRoot}/") {
            (
                FileScope::Project(project.to_owned()),
                Some(project.to_owned()),
            )
        } else if pattern.starts_with("{workspaceRoot}/") {
            (FileScope::Workspace, None)
        } else {
            return Ok(());
        };
        let pattern = paths::expand_glob(self.workspace, project, pattern)?;
        let matcher = self.snapshot.fileset_pattern(&pattern, exclude)?;
        let (prefix, rest) = crate::ignored::partition(pattern.trim_end_matches('/'));
        let rest = rest.map(str::to_owned);
        let candidates: Box<dyn Iterator<Item = &String>> = if prefix.is_empty() {
            Box::new(self.candidates.iter())
        } else {
            Box::new(under(self.candidates, &prefix))
        };
        let snapshot = self.snapshot;
        let selection = self.scopes.entry(scope).or_default();
        let selected = if exclude {
            &mut selection.excluded
        } else {
            &mut selection.included
        };
        selected.extend(
            candidates
                .filter(|file| matcher.is_match(file))
                .filter(|file| owner.is_none() || snapshot.owner(file) == owner.as_deref())
                .cloned(),
        );
        selection.patterns.push(FilePattern {
            matcher,
            prefix,
            rest,
            excluded: exclude,
            owner,
        });
        Ok(())
    }

    /// An `includeIgnored` glob of `project`, with its tokens resolved as
    /// Nx's `resolve_files_glob` resolves them, to read from disk later.
    fn ignored_fileset(&mut self, project: &str, pattern: &str, dependencies: bool) {
        // The root and name go in escaped, as for every fileset; Nx inserts
        // them as they are.
        let root = &self.workspace.projects[project].root;
        let resolved = if root == "." {
            pattern.replace("{projectRoot}/", "")
        } else {
            pattern.replace("{projectRoot}", &crate::glob::escape(root))
        }
        .replace("{projectName}", &crate::glob::escape(project));
        let resolved = match resolved.strip_prefix("!{workspaceRoot}/") {
            Some(rest) => format!("!{rest}"),
            None => resolved
                .strip_prefix("{workspaceRoot}/")
                .map(str::to_owned)
                .unwrap_or(resolved),
        };
        self.ignored
            .entry((project.to_owned(), dependencies))
            .or_default()
            .push(resolved);
    }

    /// A fileset of every project `project` depends on, directly or not.
    fn dependency_fileset(&mut self, project: &str, pattern: &str) -> Result<()> {
        if !self.named_stack.is_empty() {
            bail!("named inputs can only refer to named inputs of their own project");
        }
        for dependency in self.dependency_closure(project) {
            self.fileset(&dependency, pattern)?;
        }
        Ok(())
    }

    /// Whether `name` names one of `project`'s named inputs.
    fn has_named(&self, project: &str, name: &str) -> bool {
        name == "default"
            || self.workspace.projects[project]
                .named_inputs
                .contains_key(name)
    }

    /// Every project `project` depends on, directly or not.
    fn dependency_closure(&self, project: &str) -> BTreeSet<String> {
        let mut closure = BTreeSet::new();
        let mut pending = vec![project.to_owned()];
        while let Some(current) = pending.pop() {
            for edge in &self.snapshot.projects.dependencies[&current] {
                if edge.target != project && closure.insert(edge.target.clone()) {
                    pending.push(edge.target.clone());
                }
            }
        }
        closure
    }

    /// As in Nx, `^name` is `name` of every project the project depends on.
    fn dependencies_named(&mut self, project: &str, name: &str) -> Result<()> {
        for dependency in self.dependency_closure(project) {
            if self.expanded.insert((dependency.clone(), name.to_owned())) {
                self.named(&dependency, name)?;
            }
        }
        Ok(())
    }

    /// A JSON input: the fields of a JSON file, rather than all of it, or of
    /// each file a glob selects. `fields` keeps only the named dotted paths;
    /// `excludeFields` removes them.
    fn json(&mut self, project: &str, object: &serde_json::Map<String, Value>) -> Result<()> {
        for key in object.keys() {
            if !matches!(key.as_str(), "json" | "fields" | "excludeFields") {
                bail!("unsupported json input field {key:?}");
            }
        }
        let declared = object["json"]
            .as_str()
            .context("json input must name a file")?;
        validate_fileset(declared)?;
        let path = paths::expand_glob(self.workspace, project, declared)?;
        let list = |name: &str| -> Result<Option<Vec<String>>> {
            object
                .get(name)
                .map(|value| {
                    serde_json::from_value(value.clone())
                        .with_context(|| format!("json input {name} must be an array of strings"))
                })
                .transpose()
        };
        let fields = JsonFields {
            fields: list("fields")?,
            exclude: list("excludeFields")?.unwrap_or_default(),
        };
        if crate::glob::names_a_path(&path) {
            let path = crate::glob::literal_path(&path);
            paths::validate_path(&path)?;
            return self.json_file(path, &fields);
        }
        // As in Nx, a glob selects the files a fileset from the same root
        // would: the project's own, or the workspace's.
        let owner = if declared.starts_with("{projectRoot}") {
            Some(project)
        } else if declared.starts_with("{workspaceRoot}/") {
            None
        } else {
            return Ok(());
        };
        let matcher = self.snapshot.pattern(&path, false)?;
        let snapshot = self.snapshot;
        let matched: Vec<String> = self
            .candidates
            .iter()
            .filter(|file| matcher.is_match(file))
            .filter(|file| owner.is_none() || snapshot.owner(file) == owner)
            .cloned()
            .collect();
        for file in matched {
            self.json_file(file, &fields)?;
        }
        self.json_globs.push(JsonGlob {
            matcher,
            prefix: crate::ignored::partition(&path).0,
            owner: owner.map(str::to_owned),
            fields,
        });
        Ok(())
    }

    /// One file a `json` input selects, keyed by its fields. Several inputs
    /// may select different fields of one file: each counts, as in Nx since
    /// 24.0.0-rc.0, where one used to replace the other.
    fn json_file(&mut self, path: String, fields: &JsonFields) -> Result<()> {
        let text = match std::fs::read_to_string(self.workspace.root.join(&path)) {
            Ok(text) => Some(text),
            Err(error) if error.kind() == std::io::ErrorKind::NotFound => None,
            Err(error) => return Err(error.into()),
        };
        let mut selections = self.json_fields.get(&path).cloned().unwrap_or_default();
        if !selections.contains(fields) {
            selections.push(fields.clone());
            // In one order, whichever input came first.
            selections.sort();
        }
        let mut values = Vec::new();
        for selection in &selections {
            values.push(match &text {
                Some(text) => match json_projection(&path, text, selection) {
                    Some(value) => value,
                    // As in Nx, a file it cannot read is keyed by its content,
                    // without the field filters. Nx reads no YAML, so it keys
                    // a YAML file whole where qk keys its fields.
                    None => {
                        self.selected.insert(path);
                        return Ok(());
                    }
                },
                None => Value::Null,
            });
        }
        // One selection keys its fields as before; several, each in turn.
        let value = if values.len() == 1 {
            values.remove(0)
        } else {
            Value::Array(values)
        };
        self.values.insert(format!("json:{path}"), value);
        self.json_fields.insert(path, selections);
        Ok(())
    }

    fn named(&mut self, project: &str, name: &str) -> Result<()> {
        let identity = (project.to_owned(), name.to_owned());
        if self.named_stack.contains(&identity) {
            bail!("named input cycle at {project}:{name}");
        }
        self.named_stack.push(identity);
        let inputs = self.workspace.projects[project]
            .named_inputs
            .get(name)
            .cloned()
            .or_else(|| (name == "default").then(|| vec![json!("{projectRoot}/**/*")]))
            .with_context(|| format!("unknown named input {name:?}"))?;
        for input in &inputs {
            self.input(project, input)?;
        }
        self.named_stack.pop();
        Ok(())
    }
}

/// As Nx's `validate_file_set`: a fileset starts from `{projectRoot}` or
/// `{workspaceRoot}`, after its `!`.
fn validate_fileset(fileset: &str) -> Result<()> {
    let body = fileset.strip_prefix('!').unwrap_or(fileset);
    if !body.starts_with("{projectRoot}") && !body.starts_with("{workspaceRoot}") {
        bail!(
            "{fileset:?} is an invalid fileset: filesets have to start with either {{workspaceRoot}} or {{projectRoot}}, and a named input must be defined"
        );
    }
    Ok(())
}

/// A task's declared inputs, or Nx's default when it declares none.
fn declared_inputs(task: &Task) -> Vec<Value> {
    task.definition
        .inputs
        .clone()
        .unwrap_or_else(|| vec![json!("default"), json!("^default")])
}

/// The continuous tasks serving a task, whose inputs count as its own, as Nx
/// hashes them: its continuous dependencies, theirs in turn, and so on, each
/// by its project and declared inputs. A dependency declared with
/// `inputs: false` is not followed, though a server it leads to still counts
/// when another way reaches it.
fn servers(graph: &TaskGraph, id: &str) -> Vec<(String, Vec<Value>)> {
    let mut servers = Vec::new();
    let mut visited = BTreeSet::from([id]);
    let mut pending = std::collections::VecDeque::from([id]);
    while let Some(current) = pending.pop_front() {
        let task = &graph.tasks[current];
        for dependency in &task.dependencies {
            let Some(server) = graph.tasks.get(dependency) else {
                continue;
            };
            if server.definition.continuous != Some(true)
                || !task.edge(dependency).inputs
                || !visited.insert(dependency)
            {
                continue;
            }
            servers.push((server.project.clone(), declared_inputs(server)));
            pending.push_back(dependency);
        }
    }
    servers
}

pub fn resolve(
    snapshot: &Snapshot,
    workspace: &Workspace,
    task: &Task,
    prepared: Option<&PreparedTask>,
    cancelled: &AtomicBool,
) -> Result<Resolved> {
    resolve_candidates(
        snapshot,
        workspace,
        task,
        prepared,
        cancelled,
        &snapshot.files,
        &snapshot.source_ignore,
    )
}

fn resolve_candidates(
    snapshot: &Snapshot,
    workspace: &Workspace,
    task: &Task,
    prepared: Option<&PreparedTask>,
    cancelled: &AtomicBool,
    candidates: &BTreeSet<String>,
    source_ignore: &SourceIgnore,
) -> Result<Resolved> {
    let mut resolver = Resolver::new(snapshot, workspace, prepared, cancelled, candidates);
    resolver.task_inputs(task)?;
    // Dependency outputs may also be declared sources, for filesets and `json`
    // globs alike. Downstream and unrelated
    // outputs remain artifacts, so producing them cannot invalidate an upstream task.
    let mut upstream = BTreeSet::new();
    let mut pending: Vec<_> = task.dependencies.iter().cloned().collect();
    while let Some(id) = pending.pop() {
        if upstream.insert(id.clone())
            && let Some(dependencies) = snapshot.task_dependencies.get(&id)
        {
            pending.extend(dependencies.iter().cloned());
        }
    }
    let own_outputs = Outputs::new(workspace, task)
        .ok()
        .filter(Outputs::is_explicit);
    let mut producers = BTreeSet::new();
    for (producer, declared) in &snapshot.generated_tasks {
        if producer.id == task.id || !upstream.contains(&producer.id) {
            continue;
        }
        let overlaps = |a: &str, b: &str| {
            a.is_empty()
                || a == b
                || a.strip_prefix(b).is_some_and(|rest| rest.starts_with('/'))
                || b.strip_prefix(a).is_some_and(|rest| rest.starts_with('/'))
        };
        let relevant = resolver
            .scopes
            .values()
            .flat_map(|scope| &scope.patterns)
            .filter(|pattern| !pattern.excluded)
            .map(|pattern| &pattern.prefix)
            .chain(resolver.json_globs.iter().map(|glob| &glob.prefix))
            .any(|prefix| {
                declared.anchors().any(|anchor| {
                    overlaps(prefix, anchor)
                        && (!source_ignore.matches_directory(anchor)
                            || !workspace.root.join(anchor).is_dir())
                })
            });
        if !relevant {
            continue;
        }
        producers.insert(producer.id.clone());
        let outputs = snapshot.dependency_outputs(workspace, producer)?;
        let mut json = Vec::new();
        for path in &outputs.files {
            if source_ignore.matches(path)
                || own_outputs.as_ref().is_some_and(|own| own.matches(path))
            {
                continue;
            }
            json.extend(
                resolver
                    .json_globs
                    .iter()
                    .filter(|glob| {
                        glob.matcher.is_match(path)
                            && (glob.owner.is_none()
                                || snapshot.owner(path) == glob.owner.as_deref())
                    })
                    .map(|glob| (path.clone(), glob.fields.clone())),
            );
            for selection in resolver.scopes.values_mut() {
                for pattern in &selection.patterns {
                    if pattern.matcher.is_match(path)
                        && (pattern.owner.is_none()
                            || snapshot.owner(path) == pattern.owner.as_deref())
                    {
                        if pattern.excluded {
                            selection.excluded.insert(path.clone());
                        } else {
                            selection.included.insert(path.clone());
                        }
                    }
                }
            }
        }
        for (path, fields) in json {
            resolver.json_file(path, &fields)?;
        }
    }
    // A changed file affected selection adds counts whatever produces it, as
    // in Nx, where a declared output is a file like any other.
    for selection in resolver.scopes.values() {
        resolver.selected.extend(
            selection
                .included
                .difference(&selection.excluded)
                .filter(|path| {
                    snapshot.extra_candidates.contains(*path)
                        || own_outputs.as_ref().is_none_or(|own| !own.matches(path))
                })
                .cloned(),
        );
    }
    // `includeIgnored` groups read the disk, gitignored files included, and
    // a changed path they name counts whether or not it is there. As in Nx,
    // one reading another task's declared outputs makes that task a producer.
    let mut ignored = BTreeSet::new();
    for ((project, _), globs) in &resolver.ignored {
        let group = Group::new(
            project,
            globs,
            workspace
                .projects
                .values()
                .map(|project| project.root.as_str()),
        )?;
        let found = group.expand(&workspace.root)?;
        ignored.extend(
            found
                .into_iter()
                .chain(
                    snapshot
                        .extra_candidates
                        .iter()
                        .filter(|path| group.matches(path))
                        .cloned(),
                )
                // A task's own outputs are no input of it, as for any fileset,
                // and no task's scratch is any task's.
                .filter(|path| own_outputs.as_ref().is_none_or(|own| !own.matches(path)))
                .filter(|path| !snapshot.scratch.iter().any(|scratch| scratch.matches(path))),
        );
        for (producer, declared) in &snapshot.generated_tasks {
            if producer.id != task.id
                && upstream.contains(&producer.id)
                && declared.declared()
                && reads_outputs(&group, declared)
            {
                producers.insert(producer.id.clone());
            }
        }
    }
    resolver.selected.extend(ignored.iter().cloned());
    let mut declared = Declared {
        files: resolver.selected,
        ignored,
        values: resolver.values,
        json_fields: resolver.json_fields,
        external: resolver.external,
        external_declared: resolver.external_declared,
        projects: resolver.projects,
        producers,
        selection: Selection {
            scopes: resolver
                .scopes
                .into_values()
                .map(|selection| selection.patterns)
                .collect(),
        },
    };
    // `dependentTasksOutputFiles` reads its direct dependencies' declared
    // outputs, or with `transitive` those of every task it depends on.
    let reads: Vec<bool> = declared
        .values
        .iter()
        .filter(|(name, _)| name.starts_with("dependentTasksOutputFiles:"))
        .map(|(_, transitive)| transitive == &Value::Bool(true))
        .collect();
    if !reads.is_empty() {
        let transitive = reads.contains(&true);
        for (producer, outputs) in &snapshot.generated_tasks {
            let read = if transitive {
                upstream.contains(&producer.id)
            } else {
                task.dependencies.contains(&producer.id)
            };
            if read && outputs.declared() {
                declared.producers.insert(producer.id.clone());
            }
        }
    }
    let mut inferred = infer(snapshot, workspace, task)?;
    // As in Nx, a task naming its external dependencies hashes those in place
    // of every installed package, so the root importer's installs count only
    // for the root project's own tasks.
    if declared.external_declared
        && let Some(importers) = &mut inferred.lockfile
    {
        let root = workspace.projects[&task.project].root == ".";
        if !root {
            importers.remove(".");
        }
    }
    Ok(join(declared, inferred))
}

/// Whether an `includeIgnored` group may read files `outputs` declares, as
/// Nx's `GlobShape::may_read` judges it from the globs alone: a positive's
/// directory and an output's meet, the one holding the other, unless the
/// output lies in a project the positive does not reach, and their
/// extensions, where both have one, agree.
fn reads_outputs(group: &Group, outputs: &Outputs) -> bool {
    let holds = |outer: &str, inner: &str| {
        outer.is_empty()
            || inner == outer
            || inner
                .strip_prefix(outer)
                .is_some_and(|rest| rest.starts_with('/'))
    };
    group.reads().any(|(root, extension)| {
        outputs.globs().iter().any(|output| {
            let (prefix, _) = crate::ignored::partition(output);
            (holds(root, &prefix) || holds(&prefix, root))
                && !group
                    .skipped_below(root)
                    .iter()
                    .any(|project| holds(project, &prefix))
                && match (extension, crate::ignored::extension(output)) {
                    (Some(read), Some(written)) => read == written,
                    _ => true,
                }
        })
    })
}

/// What qk adds to `task`'s key on its own, whatever its inputs declare.
fn infer(snapshot: &Snapshot, workspace: &Workspace, task: &Task) -> Result<Inferred> {
    let readable = snapshot
        .installed(&workspace.root, &task.id)?
        .is_some_and(|installed| installed.lockfile.is_some());
    let exists = |path: &str| {
        workspace.root.join(path).is_file() || snapshot.extra_candidates.contains(path)
    };
    let mut inferred = Inferred {
        lockfile_readable: readable,
        ..Inferred::default()
    };
    // Workspace resolution and configuration. Dotenv files are not keyed, as
    // in Nx: they hold per-machine values and credentials, and a task's `env`
    // inputs key the variables it declares. The root tsconfig, as Nx hashes it
    // into every task. The root package.json is not, as in Nx: what the root
    // importer installs counts for every task through the lockfile, and the
    // rest of it is the root project's manifest.
    inferred.tsconfig = crate::inputs::ROOT_TSCONFIG_FILES
        .into_iter()
        .find(|name| exists(name))
        .map(str::to_owned);
    // nx.json counts through what it changes: through the task's resolved
    // configuration, and by the settings that reach tasks otherwise. A tool
    // reading it itself declares it as an input, which keys the file whole.
    for path in ["nx.json", qk_config::LOCAL_WORKSPACE] {
        if exists(path) {
            inferred.settings.insert(path.into());
        }
    }
    if let Some(extended) = &workspace.extended {
        inferred.settings.insert(extended.clone());
    }
    for path in [
        ".gitignore",
        ".nxignore",
        "package-lock.json",
        "yarn.lock",
        "bun.lock",
    ] {
        if exists(path) {
            inferred.files.insert(path.into());
        }
    }
    // A pnpm lockfile qk can read is keyed by what the task's projects
    // install, and the workspace file without the resolution keys whose effect
    // lands in it.
    if exists("pnpm-workspace.yaml") {
        if readable {
            inferred.workspace_file = true;
        } else {
            inferred.files.insert("pnpm-workspace.yaml".into());
        }
    }
    if exists("pnpm-lock.yaml") && !readable {
        inferred.files.insert("pnpm-lock.yaml".into());
    }
    // The task's own package.json counts whole, its package scripts and
    // dependency declarations with it. A dependency's package.json counts by what it
    // decides for dependents, such as where their imports of it resolve; its
    // installs count through the lockfile.
    let mut packages = BTreeSet::from([task.project.clone()]);
    let mut pending = packages.clone();
    while let Some(project) = pending.pop_first() {
        for edge in &snapshot.projects.dependencies[&project] {
            if packages.insert(edge.target.clone()) {
                pending.insert(edge.target.clone());
            }
        }
    }
    for project in &packages {
        let own = *project == task.project;
        for name in ["project.json", qk_config::LOCAL_OVERRIDES, "package.json"] {
            if !own && name != "package.json" {
                continue;
            }
            let path = Path::new(&workspace.projects[project].root).join(name);
            let path = path.strip_prefix(".").unwrap_or(&path).to_owned();
            if !workspace.root.join(&path).is_file() {
                continue;
            }
            let path = path
                .to_str()
                .context("project path must be UTF-8")?
                .replace('\\', "/");
            // Its project.json and project.local.json are not added: what
            // they decide for the task counts through its resolved
            // configuration, and an input selecting them keys them as it
            // says.
            if own && name != "package.json" {
                inferred.project.insert(path);
                continue;
            }
            if own {
                inferred.files.insert(path);
                continue;
            }
            let text = std::fs::read_to_string(workspace.root.join(&path))
                .with_context(|| format!("cannot read {path}"))?;
            match manifest_for_dependents(&text, readable) {
                Some(value) => {
                    inferred.manifests.insert(path, value);
                }
                None => {
                    inferred.files.insert(path);
                }
            }
        }
    }
    if readable {
        // The root importer's packages resolve from every package in the
        // workspace, so they count for every task.
        inferred.lockfile = Some(
            std::iter::once(".".to_owned())
                .chain(
                    packages
                        .iter()
                        .map(|project| workspace.projects[project].root.clone()),
                )
                .collect(),
        );
    }
    Ok(inferred)
}

/// `declared` and `inferred` together. A file both select is left to the
/// declared inputs, which count all of it.
fn join(declared: Declared, mut inferred: Inferred) -> Resolved {
    let mut covered = BTreeSet::new();
    inferred.files.retain(|path| {
        let keep = !declared.files.contains(path);
        if !keep {
            covered.insert(path.clone());
        }
        keep
    });
    inferred.manifests.retain(|path, _| {
        let keep = !declared.files.contains(path);
        if !keep {
            covered.insert(path.clone());
        }
        keep
    });
    if inferred.lockfile.is_some() && declared.files.contains("pnpm-lock.yaml") {
        inferred.lockfile = None;
        covered.insert("pnpm-lock.yaml".into());
    }
    if inferred.workspace_file && declared.files.contains("pnpm-workspace.yaml") {
        inferred.workspace_file = false;
        covered.insert("pnpm-workspace.yaml".into());
    }
    if let Some(tsconfig) = inferred
        .tsconfig
        .take_if(|path| declared.files.contains(path))
    {
        covered.insert(tsconfig);
    }
    inferred.covered = covered;
    Resolved { declared, inferred }
}

/// What a task's key is computed from, as JSON: kept by the history so a
/// changed key can be explained.
pub fn inputs(
    snapshot: &Snapshot,
    workspace: &Workspace,
    task: &Task,
    prepared: &PreparedTask,
    dependencies: &BTreeMap<String, String>,
    cancelled: &AtomicBool,
) -> Result<Value> {
    let prefixes = snapshot.membership_prefixes(workspace, task)?;
    let candidates = snapshot.current_files_for(&workspace.root, Some(&prefixes), &task.id)?;
    let Resolved { declared, inferred } = resolve_candidates(
        snapshot,
        workspace,
        task,
        Some(prepared),
        cancelled,
        &candidates.files,
        &candidates.source_ignore,
    )?;
    let file_values = |paths: &BTreeSet<String>| {
        paths
            .iter()
            .map(|path| {
                let value = snapshot
                    .file_value(&workspace.root, path)
                    .with_context(|| format!("cannot read input {path}"))?;
                Ok((path.clone(), value))
            })
            .collect::<Result<BTreeMap<_, _>>>()
    };
    let mut files = file_values(&(&declared.files - &declared.ignored))?;
    for path in &declared.ignored {
        if let Some(value) = snapshot
            .ignored_value(&workspace.root, path)
            .with_context(|| format!("cannot read input {path}"))?
        {
            files.insert(path.clone(), value);
        }
    }
    let mut values = declared.values;
    // Left out without a declared environment, so other keys stay as they
    // were.
    if let Some(environment) = &prepared.environment {
        values.insert("environment".into(), environment.keyed());
    }
    let mut configuration = json!({
        "files": file_values(&inferred.files)?,
        "settings": workspace.config.keyed_settings(),
        "project": task_configuration(workspace, task),
    });
    let installed = snapshot.installed(&workspace.root, &task.id)?;
    if let (Some(importers), Some(installed)) = (&inferred.lockfile, &installed)
        && let Some(lockfile) = &installed.lockfile
    {
        let importers: BTreeMap<_, _> = importers
            .iter()
            .filter(|importer| lockfile.has_importer(importer))
            .map(|importer| {
                let digest = installed.digest(&format!("importer:{importer}"), || {
                    lockfile.installed(importer).unwrap_or_default()
                });
                (importer.clone(), digest)
            })
            .collect();
        configuration["lockfile"] = json!({
            "global": installed.digest("global", || BTreeSet::from([lockfile.global().to_string()])),
            "importers": importers,
        });
        // A lockfile keyed whole already covers the packages it installs.
        if !declared.external.is_empty() {
            let external: BTreeMap<_, _> = declared
                .external
                .iter()
                .map(|name| {
                    let digest =
                        installed.digest(&format!("package:{name}"), || lockfile.package(name));
                    // As in Nx, a package nothing installs is an error.
                    if digest == blake3::hash(b"").to_hex().as_str() {
                        bail!(
                            "the externalDependency {name:?} of {} could not be found",
                            task.id
                        );
                    }
                    Ok((name.clone(), digest))
                })
                .collect::<Result<_>>()?;
            values.insert("externalDependencies".into(), json!(external));
        }
    }
    if inferred.workspace_file {
        configuration["workspaceFile"] = match workspace_without_resolution(&workspace.root) {
            Some(value) => value,
            None => snapshot.file_value(&workspace.root, "pnpm-workspace.yaml")?,
        };
    }
    if !inferred.manifests.is_empty() {
        configuration["manifests"] = json!(inferred.manifests);
    }
    if let Some(path) = &inferred.tsconfig {
        let parsed = std::fs::read_to_string(workspace.root.join(path))
            .ok()
            .and_then(|text| TsConfig::parse(&text));
        configuration["tsconfig"] = match parsed {
            Some(tsconfig) if crate::inputs::selectively_hash_tsconfig(workspace) => json!({
                "rest": tsconfig.rest,
                "paths": tsconfig.paths_of(&declared.projects, |target| snapshot.owner(target)),
            }),
            Some(tsconfig) => json!({ "rest": tsconfig.rest }),
            None => snapshot.file_value(&workspace.root, path)?,
        };
    }
    let definition = keyed_definition(task);
    let hash = json!({
        "schema":"qk-local-v4", "qk":env!("CARGO_PKG_VERSION"),
        "platform":[std::env::consts::OS, std::env::consts::ARCH], "workspace":snapshot.workspace_prefix,
        "id":task.id, "args":task.args, "definition":definition, "packageManager":workspace.package_manager,
        "files":files, "values":values, "inferred":configuration, "dependencies":dependencies,
    });
    Ok(hash)
}

/// A task's definition as its key holds it. Warm state configuration never
/// changes a result, and as in Nx a target's metadata, such as the run
/// command shown for a script, is description only.
pub fn keyed_definition(task: &Task) -> qk_config::Target {
    let mut definition = task.definition.clone();
    definition.extra.remove("qk:warm");
    definition.extra.remove("qk:threads");
    definition.extra.remove("metadata");
    // What a recording keys is the recording's own concern.
    definition.extra.remove("qk:ultracache");
    definition
}

/// What a task's key holds of its project's configuration beside its
/// definition and resolved inputs: the project's keyed settings, such as its
/// root, the paths its outputs resolve to, which `{project.*}` tokens can
/// read from anywhere in the configuration, and all of the configuration
/// when a forwarded argument holds such a token, as the task reads it then.
pub fn task_configuration(workspace: &Workspace, task: &Task) -> Value {
    let project = &workspace.projects[&task.project];
    let mut value = json!({ "settings": project.keyed_settings() });
    if let Ok((outputs, _)) = paths::resolved_outputs(workspace, task) {
        value["outputs"] = json!(outputs);
    }
    if task.args.iter().any(|arg| arg.contains("{project")) {
        value["configuration"] = serde_json::to_value(project).unwrap_or_default();
    }
    value
}

/// The key for a task's inputs. Objects are keyed with their fields sorted,
/// so the order they were written in, which configuration keeps, does not
/// change the key.
pub fn key(inputs: &Value) -> Result<String> {
    Ok(blake3::hash(&serde_json::to_vec(&sorted(inputs))?)
        .to_hex()
        .to_string())
}

/// `value` with every object's fields in key order.
fn sorted(value: &Value) -> Value {
    match value {
        Value::Object(object) => {
            let mut fields: Vec<_> = object.iter().collect();
            fields.sort_unstable_by_key(|(name, _)| *name);
            Value::Object(
                fields
                    .into_iter()
                    .map(|(name, value)| (name.clone(), sorted(value)))
                    .collect(),
            )
        }
        Value::Array(items) => Value::Array(items.iter().map(sorted).collect()),
        other => other.clone(),
    }
}

pub fn fingerprint(
    snapshot: &Snapshot,
    workspace: &Workspace,
    task: &Task,
    prepared: &PreparedTask,
    dependencies: &BTreeMap<String, String>,
    cancelled: &AtomicBool,
) -> Result<String> {
    key(&inputs(
        snapshot,
        workspace,
        task,
        prepared,
        dependencies,
        cancelled,
    )?)
}

/// The key of a task keyed by its recordings, before its path set: `inputs`,
/// the task's key, without its declared file inputs, which a path set
/// replaces, but with its `"always": true` inputs, which count whatever it
/// read, and with what `ignoreReads` leaves out of its path sets.
#[allow(clippy::too_many_arguments)]
pub(crate) fn weak_key(
    snapshot: &Snapshot,
    workspace: &Workspace,
    graph: &TaskGraph,
    task: &Task,
    prepared: &PreparedTask,
    inputs: &Value,
    ignore_reads: &[String],
    ignored_within: &[(&str, bool)],
    cancelled: &AtomicBool,
) -> Result<String> {
    let mut weak = inputs.clone();
    let object = weak
        .as_object_mut()
        .context("a key's inputs are an object")?;
    object.remove("files");
    object.remove("dependencies");
    if let Some(Value::Object(values)) = object.get_mut("values") {
        values.retain(|name, _| {
            !name.starts_with("json:") && !name.starts_with("dependentTasksOutputFiles:")
        });
    }
    let mut always = task.clone();
    always.definition.inputs = Some(
        declared_inputs(task)
            .into_iter()
            .filter(|input| input.get("always") == Some(&Value::Bool(true)))
            .collect(),
    );
    let dependencies = dependency_keys(snapshot, workspace, graph, &always, cancelled)?;
    let always = self::inputs(
        snapshot,
        workspace,
        &always,
        prepared,
        &dependencies,
        cancelled,
    )?;
    object.insert(
        "always".into(),
        json!({"files": always["files"], "values": always["values"], "dependencies": always["dependencies"]}),
    );
    object.insert("schema".into(), json!("qk-weak-v1"));
    object.insert("ignoreReads".into(), json!(ignore_reads));
    // What its `^` entries match moves with the project graph, the projects
    // depended on and those nested in them that are not, so a path set
    // recorded under one never keys a task under another. Left out without
    // them, so other weak keys stay as they were.
    if !ignored_within.is_empty() {
        object.insert("ignoredWithin".into(), json!(ignored_within));
    }
    key(&weak)
}

/// The dependency outputs a task's `dependentTasksOutputFiles` inputs read,
/// as Nx hashes them: the files each glob selects of the declared outputs of
/// its direct dependencies, or with `transitive` of every task it depends on.
/// Nothing else about a dependency keys a task.
pub(crate) fn dependency_keys(
    snapshot: &Snapshot,
    workspace: &Workspace,
    graph: &TaskGraph,
    task: &Task,
    cancelled: &AtomicBool,
) -> Result<BTreeMap<String, String>> {
    dependency_keys_impl(snapshot, workspace, graph, task, cancelled, false)
}

/// Read dependency artifacts again before accepting an execution as unchanged.
pub(crate) fn recheck_dependency_keys(
    snapshot: &Snapshot,
    workspace: &Workspace,
    graph: &TaskGraph,
    task: &Task,
    cancelled: &AtomicBool,
) -> Result<BTreeMap<String, String>> {
    dependency_keys_impl(snapshot, workspace, graph, task, cancelled, true)
}

fn dependency_keys_impl(
    snapshot: &Snapshot,
    workspace: &Workspace,
    graph: &TaskGraph,
    task: &Task,
    cancelled: &AtomicBool,
    fresh: bool,
) -> Result<BTreeMap<String, String>> {
    let resolved = resolve(snapshot, workspace, task, None, cancelled)?;
    let selections: Vec<_> = resolved.dependency_output_inputs().collect();
    let mut keys = BTreeMap::new();
    let mut fresh_outputs = HashMap::new();
    for (pattern, transitive) in selections {
        let matcher = snapshot.pattern(pattern, false)?;
        let mut selected = task.dependencies.clone();
        if transitive {
            let mut pending = selected.clone();
            while let Some(id) = pending.pop_first() {
                for dependency in &graph.tasks[&id].dependencies {
                    if selected.insert(dependency.clone()) {
                        pending.insert(dependency.clone());
                    }
                }
            }
        }
        for id in selected {
            // As in Nx, a dependency without declared outputs offers none.
            if !Outputs::new(workspace, &graph.tasks[&id])?.declared() {
                continue;
            }
            let outputs = if fresh {
                if !fresh_outputs.contains_key(&id) {
                    fresh_outputs.insert(
                        id.clone(),
                        Arc::new(snapshot.fresh_dependency_outputs(workspace, &graph.tasks[&id])?),
                    );
                }
                fresh_outputs[&id].clone()
            } else {
                snapshot.dependency_outputs(workspace, &graph.tasks[&id])?
            };
            let mut files = BTreeMap::new();
            for path in outputs.files.iter().filter(|path| matcher.is_match(path)) {
                let known = outputs.values.lock().unwrap().get(path).cloned();
                let value = match known {
                    Some(value) => value,
                    None => {
                        let value = snapshot.file_value(&workspace.root, path)?;
                        // Links depend on paths outside the declared output roots.
                        if value.get("link").is_none() {
                            outputs
                                .values
                                .lock()
                                .unwrap()
                                .insert(path.clone(), value.clone());
                        }
                        value
                    }
                };
                files.insert(path.clone(), value);
            }
            keys.insert(format!("{id}:{pattern}"), key(&json!(files))?);
        }
    }
    Ok(keys)
}

/// What one task's `dependentTasksOutputFiles` glob selects of the outputs it
/// reads.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct DependencyGlob {
    pub task: String,
    pub pattern: String,
    pub selects: Selects,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Selects {
    /// None of the tasks it reads declares outputs, so nothing ever.
    NoDeclaredOutputs,
    /// Some of their outputs are not built, so it cannot be told.
    NotBuilt,
    /// None of the files their outputs hold now, this many.
    NoneOf(usize),
    /// Some of the files their outputs hold now.
    Some,
}

/// What each `dependentTasksOutputFiles` glob of `graph`'s tasks selects of
/// its dependencies' outputs as they are on disk, without running anything.
pub fn dependency_globs(workspace: &Workspace, graph: &TaskGraph) -> Result<Vec<DependencyGlob>> {
    let snapshot = Snapshot::new(workspace, graph, &paths::cache_location(workspace))?;
    let cancelled = AtomicBool::new(false);
    let mut globs = Vec::new();
    for task in graph.tasks.values() {
        // A task whose inputs cannot be resolved fails as it runs instead.
        let Ok(resolved) = resolve(&snapshot, workspace, task, None, &cancelled) else {
            continue;
        };
        for (pattern, transitive) in resolved.dependency_output_inputs() {
            let mut selected = task.dependencies.clone();
            if transitive {
                let mut pending = selected.clone();
                while let Some(id) = pending.pop_first() {
                    for dependency in &graph.tasks[&id].dependencies {
                        if selected.insert(dependency.clone()) {
                            pending.insert(dependency.clone());
                        }
                    }
                }
            }
            let matcher = snapshot.pattern(pattern, false)?;
            // A dependency not built yet may still produce what it matches.
            let (mut declared, mut files, mut matched, mut unbuilt) = (false, 0, false, false);
            for id in &selected {
                let dependency = &graph.tasks[id];
                if !Outputs::new(workspace, dependency)?.declared() {
                    continue;
                }
                declared = true;
                let outputs = snapshot.dependency_outputs(workspace, dependency)?;
                unbuilt |= outputs.files.is_empty();
                files += outputs.files.len();
                matched |= outputs.files.iter().any(|path| matcher.is_match(path));
            }
            globs.push(DependencyGlob {
                task: task.id.clone(),
                pattern: pattern.to_owned(),
                selects: match (declared, matched, unbuilt) {
                    (false, ..) => Selects::NoDeclaredOutputs,
                    (_, true, _) => Selects::Some,
                    (_, _, true) => Selects::NotBuilt,
                    _ => Selects::NoneOf(files),
                },
            });
        }
    }
    Ok(globs)
}

#[cfg(test)]
mod tests {

    /// Every file keyed by its whole content, declared or inferred.
    fn whole(resolved: &Resolved) -> BTreeSet<String> {
        resolved.whole_files().map(str::to_owned).collect()
    }
    use super::*;
    use qk_taskgraph::Request;

    fn fixture(outputs: Option<Value>) -> (tempfile::TempDir, Workspace, TaskGraph) {
        let root = tempfile::tempdir().unwrap();
        std::fs::write(root.path().join("nx.json"), "{}").unwrap();
        let mut post = json!({"command": "true"});
        if let Some(outputs) = outputs {
            post["outputs"] = outputs;
        }
        std::fs::write(root.path().join("project.json"), json!({"name":"app", "targets": {
            "gen": {"command":"true", "outputs":["{projectRoot}/generated"]},
            "post": post,
            "build": {"command":"true", "dependsOn":["gen", "post"], "inputs":[{"dependentTasksOutputFiles":"**/*"}]}
        }}).to_string()).unwrap();
        std::fs::create_dir(root.path().join("generated")).unwrap();
        std::fs::write(root.path().join("generated/value"), "one").unwrap();
        let workspace = Workspace::load(root.path()).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        (root, workspace, graph)
    }

    /// A `json` glob selects a dependency's declared outputs, keyed by their
    /// fields, and makes that dependency a producer, as a fileset does.

    #[test]
    fn keys_ignore_the_order_object_fields_were_written_in() {
        let written = json!({"options": {"cwd": "app", "command": "x"}, "args": ["a", "b"]});
        let reordered = json!({"args": ["a", "b"], "options": {"command": "x", "cwd": "app"}});
        assert_eq!(key(&written).unwrap(), key(&reordered).unwrap());
        let swapped = json!({"options": {"cwd": "app", "command": "x"}, "args": ["b", "a"]});
        assert_ne!(key(&written).unwrap(), key(&swapped).unwrap());
    }
    #[test]
    fn json_globs_select_dependency_outputs() {
        let root = tempfile::tempdir().unwrap();
        std::fs::write(root.path().join("nx.json"), "{}").unwrap();
        for (path, content) in [
            (
                "apps/app/project.json",
                json!({"name": "app", "implicitDependencies": ["lib"], "targets": {
                    "build": {"command": "true", "dependsOn": ["^build"], "inputs": [
                        {"json": "{workspaceRoot}/libs/lib/out/*.json", "fields": ["version"]}
                    ]}
                }}),
            ),
            (
                "libs/lib/project.json",
                json!({"name": "lib", "targets": {
                    "build": {"command": "true", "outputs": ["{projectRoot}/out"]}
                }}),
            ),
            (
                "libs/lib/out/meta.json",
                json!({"version": 2, "built": "now"}),
            ),
        ] {
            let path = root.path().join(path);
            std::fs::create_dir_all(path.parent().unwrap()).unwrap();
            std::fs::write(path, content.to_string()).unwrap();
        }
        let workspace = Workspace::load(root.path()).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let resolved = resolve(
            &snapshot,
            &workspace,
            &graph.tasks["app:build"],
            None,
            &AtomicBool::new(false),
        )
        .unwrap();
        assert_eq!(
            resolved.declared.values.get("json:libs/lib/out/meta.json"),
            Some(&json!({"version": 2}))
        );
        assert_eq!(
            resolved.declared.producers,
            BTreeSet::from(["lib:build".to_owned()])
        );
    }

    /// The declared key covers a recording when every file it read is keyed,
    /// every file it looked for would be selected and not gitignored, and
    /// every entry a directory it listed could hold would be selected.
    #[test]
    fn declared_inputs_cover_what_they_would_select_and_not_what_they_leave_out() {
        let root = tempfile::tempdir().unwrap();
        std::fs::write(root.path().join("nx.json"), "{}").unwrap();
        std::fs::write(
            root.path().join("project.json"),
            json!({"name": "app", "targets": {
                "build": {"command": "true", "inputs": [
                    "{projectRoot}/src/**/*", "!{projectRoot}/src/skip/**/*"
                ]},
                "gen": {"command": "true", "outputs": ["{projectRoot}/src/gen"]}
            }})
            .to_string(),
        )
        .unwrap();
        std::fs::write(root.path().join(".gitignore"), "src/secret.ts\n").unwrap();
        for path in [
            "src/a.ts",
            "src/lib/b.ts",
            "src/skip/c.ts",
            "src/gen/d.ts",
            "README.md",
        ] {
            let path = root.path().join(path);
            std::fs::create_dir_all(path.parent().unwrap()).unwrap();
            std::fs::write(path, "x").unwrap();
        }
        let workspace = Workspace::load(root.path()).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let task = &graph.tasks["app:build"];
        let prepared = qk_executor::prepare(&workspace, task, &BTreeMap::new()).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let coverage = coverage(
            &snapshot,
            &workspace,
            &graph,
            task,
            &prepared,
            &AtomicBool::new(false),
        )
        .unwrap();
        let set = |part: &str, path: &str| {
            let mut set = crate::recorded::PathSet::default();
            match part {
                "read" => &mut set.reads,
                "present" => &mut set.present,
                "absent" => &mut set.absent,
                _ => &mut set.listings,
            }
            .insert(path.to_owned());
            set
        };
        for (part, path, covered) in [
            ("read", "src/a.ts", true),
            ("read", "README.md", false),
            ("read", "src/skip/c.ts", false),
            ("present", "src/lib", true),
            ("absent", "src/new.ts", true),
            // Excluded, or gitignored: creating it would not change the key.
            ("absent", "src/skip/new.ts", false),
            ("absent", "src/secret.ts", false),
            ("absent", ".env.local", false),
            // Another target's output, which no declared key holds.
            ("absent", "src/gen/e.ts", false),
            ("listing", "src/gen", false),
            ("listing", "src/lib", true),
            // An exclusion reaches into it, or nothing selects all of it.
            ("listing", "src", false),
            ("listing", ".", false),
        ] {
            let generated = |path: &str| path == "src/gen" || path.starts_with("src/gen/");
            assert_eq!(
                coverage.covers(&snapshot, root.path(), &set(part, path), &generated),
                covered,
                "{part} {path}"
            );
        }
    }

    #[test]
    fn execution_fingerprints_refresh_sources_and_preserve_artifact_exclusions() {
        let (root, mut workspace, _) = fixture(Some(json!(["{projectRoot}/dist"])));
        let definition = workspace
            .projects
            .get_mut("app")
            .unwrap()
            .targets
            .get_mut("post")
            .unwrap();
        definition
            .extra
            .insert("qk:warm".into(), json!({"paths": ["scratch"]}));
        std::fs::write(root.path().join(".gitignore"), "ignored/\n").unwrap();
        std::fs::create_dir(root.path().join("src")).unwrap();
        std::fs::write(root.path().join("src/original"), "one").unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let task = &graph.tasks["app:post"];
        let prepared = qk_executor::prepare(&workspace, task, &BTreeMap::new()).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let inputs = || {
            super::inputs(
                &snapshot,
                &workspace,
                task,
                &prepared,
                &BTreeMap::new(),
                &AtomicBool::new(false),
            )
            .unwrap()
        };
        let before = inputs();
        // Artifacts created after startup must not change the execution key.
        for directory in ["generated", "dist", "scratch", "cache", "ignored"] {
            std::fs::create_dir_all(root.path().join(directory)).unwrap();
            std::fs::write(root.path().join(directory).join("new"), "artifact").unwrap();
        }
        assert_eq!(before, inputs());
        // This covers both post-execution verification and a later task's first
        // fingerprint against a snapshot created before this source existed.
        std::fs::write(root.path().join("src/added"), "two").unwrap();
        let after = inputs();
        assert!(after["files"].get("src/added").is_some());
        assert_ne!(key(&before).unwrap(), key(&after).unwrap());
        std::fs::remove_file(root.path().join("src/added")).unwrap();
        assert_eq!(before, inputs());
        std::fs::remove_file(root.path().join("src/original")).unwrap();
        assert!(inputs()["files"].get("src/original").is_none());
    }

    #[test]
    fn membership_reuses_settled_candidates_and_detects_directory_changes() {
        let mut fixtures = Vec::new();
        for git in [false, true] {
            let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
            for directory in ["src/empty", "dist", "cache", "ignored"] {
                std::fs::create_dir_all(root.path().join(directory)).unwrap();
            }
            std::fs::write(root.path().join(".gitignore"), "ignored/\n").unwrap();
            std::fs::write(root.path().join("src/original"), "one").unwrap();
            if git {
                assert!(
                    paths::git(root.path(), &["init", "-q"])
                        .unwrap()
                        .status
                        .success()
                );
                assert!(
                    paths::git(root.path(), &["add", "."])
                        .unwrap()
                        .status
                        .success()
                );
            }
            let snapshot =
                Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
            snapshot.current_files(root.path()).unwrap();
            fixtures.push((root, snapshot));
        }
        // Recent directory metadata deliberately uses the conservative listing
        // path. Waiting lets this test exercise the actual reuse path too.
        std::thread::sleep(Duration::from_millis(2100));
        for (root, snapshot) in fixtures {
            let files = || snapshot.current_files(root.path()).unwrap();
            let before = files();
            assert!(Arc::ptr_eq(&before, &files()));
            for directory in ["generated", "dist", "cache"] {
                std::fs::write(root.path().join(directory).join("new"), "artifact").unwrap();
            }
            assert!(Arc::ptr_eq(&before, &files()));
            std::fs::write(root.path().join("src/empty/added"), "two").unwrap();
            assert!(files().contains("src/empty/added"));
            std::fs::create_dir_all(root.path().join("src/new/nested")).unwrap();
            std::fs::write(root.path().join("src/new/nested/added"), "three").unwrap();
            assert!(files().contains("src/new/nested/added"));
            std::fs::rename(
                root.path().join("src/original"),
                root.path().join("src/renamed"),
            )
            .unwrap();
            let renamed = files();
            assert!(!renamed.contains("src/original"));
            assert!(renamed.contains("src/renamed"));
            std::fs::remove_file(root.path().join("src/renamed")).unwrap();
            assert!(!files().contains("src/renamed"));
            // Policy files must be checked even when directory entries do not
            // change (editing an existing ignore file in place).
            std::fs::write(root.path().join(".gitignore"), "ignored/\nsrc/empty/\n").unwrap();
            assert!(!files().contains("src/empty/added"));
            std::fs::write(root.path().join(".gitignore"), "ignored/\n").unwrap();
            assert!(files().contains("src/empty/added"));
        }
    }

    #[test]
    fn identical_ignore_rewrites_reuse_candidates_and_changed_rules_refresh() {
        for name in [".gitignore", ".nxignore"] {
            let (root, workspace, graph) = fixture(None);
            let policy = root.path().join(name);
            std::fs::write(root.path().join("alpha"), "a").unwrap();
            std::fs::write(root.path().join("bravo"), "b").unwrap();
            std::fs::write(&policy, "alpha\n").unwrap();
            let snapshot =
                Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
            let original = snapshot.current_files(root.path()).unwrap();
            assert!(!original.contains("alpha"));
            assert!(original.contains("bravo"));
            for _ in 0..3 {
                std::fs::write(&policy, "alpha\n").unwrap();
                assert!(Arc::ptr_eq(
                    &original,
                    &snapshot.current_files(root.path()).unwrap()
                ));
            }
            // Same-length content can change while coarse timestamps appear
            // identical. Recent policies must still compare their contents.
            std::fs::write(&policy, "bravo\n").unwrap();
            {
                let mut cached = snapshot.membership.lock().unwrap();
                Arc::make_mut(cached.as_mut().unwrap())
                    .stamps
                    .insert(policy.clone(), membership_stamp(&policy).unwrap());
            }
            let changed = snapshot.current_files(root.path()).unwrap();
            assert!(!Arc::ptr_eq(&original, &changed));
            assert!(changed.contains("alpha"));
            assert!(!changed.contains("bravo"));
            std::fs::remove_file(&policy).unwrap();
            assert!(
                snapshot
                    .current_files(root.path())
                    .unwrap()
                    .contains("bravo")
            );
        }
    }

    #[test]
    fn ignore_contents_changed_after_inventory_cannot_bless_a_listing() {
        let (root, workspace, graph) = fixture(None);
        let policy = root.path().join(".nxignore");
        std::fs::write(&policy, "alpha\n").unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(root.path()).unwrap();
        let membership = snapshot.membership.lock().unwrap().clone().unwrap();
        std::fs::write(&policy, "bravo\n").unwrap();
        assert!(!membership.state(None).unwrap().0);
    }

    #[test]
    fn a_directory_missed_by_the_inventory_cannot_enable_reuse() {
        let (root, workspace, graph) = fixture(None);
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(root.path()).unwrap();
        std::fs::create_dir(root.path().join("new-empty")).unwrap();
        let mut cached = snapshot.membership.lock().unwrap();
        let membership = Arc::make_mut(cached.as_mut().unwrap());
        // Model creation between the directory walk and child-name capture:
        // the new directory is in its parent's names but not in the inventory.
        membership
            .directory_entries
            .get_mut(root.path())
            .unwrap()
            .insert((OsString::from("new-empty"), 1));
        assert!(membership.entries(root.path()).unwrap().is_none());
        assert!(!membership.state(None).unwrap().0);
    }

    #[test]
    fn a_policy_missed_by_discovery_cannot_enable_reuse() {
        let (root, workspace, graph) = fixture(None);
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(root.path()).unwrap();
        std::fs::write(root.path().join(".nxignore"), "hidden\n").unwrap();
        let mut cached = snapshot.membership.lock().unwrap();
        let membership = Arc::make_mut(cached.as_mut().unwrap());
        // Model a new policy appearing after discovery but before capturing
        // its parent's entries; its content would otherwise have no stamp.
        membership
            .directory_entries
            .get_mut(root.path())
            .unwrap()
            .insert((OsString::from(".nxignore"), 0));
        assert!(membership.entries(root.path()).unwrap().is_none());
        assert!(!membership.state(None).unwrap().0);
    }

    #[test]
    fn output_publication_reuses_candidates_but_source_names_still_refresh() {
        for partial in [false, true] {
            let outputs = if partial {
                json!(["{projectRoot}/dist", "!{projectRoot}/dist/keep"])
            } else {
                json!(["{projectRoot}/dist"])
            };
            let (root, workspace, graph) = fixture(Some(outputs));
            std::fs::create_dir_all(root.path().join("src")).unwrap();
            std::fs::write(root.path().join("src/original"), "one").unwrap();
            if partial {
                std::fs::create_dir_all(root.path().join("dist/keep")).unwrap();
            }
            let snapshot =
                Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
            snapshot.current_files(root.path()).unwrap();
            // Policies retain their conservative timestamp window. Directory
            // names are freshly verified throughout the window instead.
            std::thread::sleep(Duration::from_millis(2100));
            let before = snapshot.current_files(root.path()).unwrap();
            std::fs::create_dir_all(root.path().join("dist")).unwrap();
            std::fs::write(root.path().join("dist/restored"), "artifact").unwrap();
            let restored = snapshot.current_files(root.path()).unwrap();
            assert!(Arc::ptr_eq(&before, &restored));
            std::fs::remove_file(root.path().join("dist/restored")).unwrap();
            assert!(Arc::ptr_eq(
                &before,
                &snapshot.current_files(root.path()).unwrap()
            ));
            let source = if partial { "dist/keep/new" } else { "src/new" };
            std::fs::write(root.path().join(source), "source").unwrap();
            let after = snapshot.current_files(root.path()).unwrap();
            assert!(after.contains(source));
            assert!(!Arc::ptr_eq(&before, &after));
            std::fs::remove_file(root.path().join(source)).unwrap();
            assert!(
                !snapshot
                    .current_files(root.path())
                    .unwrap()
                    .contains(source)
            );
        }
    }

    #[test]
    fn concurrent_fingerprints_refresh_without_replacing_newer_membership() {
        let (root, workspace, graph) = fixture(None);
        std::fs::create_dir_all(root.path().join("src")).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let original = snapshot.current_files(root.path()).unwrap();
        let barrier = std::sync::Barrier::new(9);
        std::thread::scope(|scope| {
            let workers: Vec<_> = (0..8)
                .map(|_| {
                    scope.spawn(|| {
                        let mut rounds = Vec::new();
                        for _ in 0..6 {
                            barrier.wait();
                            rounds.push(snapshot.current_files(root.path()));
                            barrier.wait();
                        }
                        rounds
                    })
                })
                .collect();
            for round in 0..6 {
                std::fs::write(root.path().join(format!("src/new{round}")), "source").unwrap();
                barrier.wait();
                barrier.wait();
            }
            // Assertions run after synchronization, so a failed membership
            // check cannot strand other workers at a barrier.
            for worker in workers {
                for (round, files) in worker.join().unwrap().into_iter().enumerate() {
                    let files = files.unwrap();
                    for added in 0..=round {
                        assert!(files.contains(&format!("src/new{added}")));
                    }
                }
            }
        });
        assert!(!original.contains("src/new0"));
        assert!(
            snapshot
                .current_files(root.path())
                .unwrap()
                .contains("src/new5")
        );
    }

    #[test]
    fn retained_candidates_keep_their_dependency_output_ignore_policy() {
        let (root, mut workspace, _) = fixture(None);
        workspace
            .projects
            .get_mut("app")
            .unwrap()
            .targets
            .get_mut("build")
            .unwrap()
            .inputs = Some(vec![json!("{workspaceRoot}/**/*.txt")]);
        std::fs::create_dir(root.path().join("src")).unwrap();
        for name in ["alpha", "beta", "gamma"] {
            for directory in ["src", "generated"] {
                std::fs::write(root.path().join(format!("{directory}/{name}.txt")), name).unwrap();
            }
        }
        let policy = |keep: &str| {
            let ignored: String = ["alpha", "beta", "gamma"]
                .into_iter()
                .filter(|name| *name != keep)
                .flat_map(|name| {
                    [
                        format!("src/{name}.txt\n"),
                        format!("generated/{name}.txt\n"),
                    ]
                })
                .collect();
            std::fs::write(root.path().join(".nxignore"), ignored).unwrap();
        };
        policy("alpha");
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &root.path().join("cache")).unwrap();
        let first = snapshot
            .current_files_for(root.path(), None, "test")
            .unwrap();
        policy("beta");
        let second = snapshot
            .current_files_for(root.path(), None, "test")
            .unwrap();
        policy("gamma");
        let third = snapshot
            .current_files_for(root.path(), None, "test")
            .unwrap();
        // Deterministically pause two fingerprints after candidate acquisition,
        // then let another fingerprint refresh policy twice before they resolve.
        let cancelled = AtomicBool::new(false);
        let expected = |name: &str| {
            BTreeSet::from([
                ".nxignore".into(),
                format!("src/{name}.txt"),
                format!("generated/{name}.txt"),
            ])
        };
        for (candidates, name) in [(first, "alpha"), (second, "beta"), (third, "gamma")] {
            let resolved = resolve_candidates(
                &snapshot,
                &workspace,
                &graph.tasks["app:build"],
                None,
                &cancelled,
                &candidates.files,
                &candidates.source_ignore,
            )
            .unwrap();
            assert_eq!(whole(&resolved), expected(name));
        }
        // Inspection still uses its original candidate list and original policy.
        let inspected = resolve(
            &snapshot,
            &workspace,
            &graph.tasks["app:build"],
            None,
            &cancelled,
        )
        .unwrap();
        assert_eq!(whole(&inspected), expected("alpha"));
    }

    #[test]
    fn scoped_membership_defers_unrelated_changes_until_a_matching_task_asks() {
        let (root, mut workspace, _) = fixture(Some(json!(["{projectRoot}/dist"])));
        let targets = &mut workspace.projects.get_mut("app").unwrap().targets;
        targets.get_mut("post").unwrap().inputs =
            Some(vec![json!("{workspaceRoot}/left/**/*.txt")]);
        targets.get_mut("gen").unwrap().inputs =
            Some(vec![json!("{workspaceRoot}/right/**/*.txt")]);
        targets.get_mut("build").unwrap().inputs = Some(vec![json!("{workspaceRoot}/**/*.txt")]);
        for directory in ["left/empty", "right/empty"] {
            std::fs::create_dir_all(root.path().join(directory)).unwrap();
        }
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(&workspace.root).unwrap();
        std::thread::sleep(Duration::from_millis(2100));
        let left = snapshot
            .membership_prefixes(&workspace, &graph.tasks["app:post"])
            .unwrap();
        let right = snapshot
            .membership_prefixes(&workspace, &graph.tasks["app:gen"])
            .unwrap();
        let all = snapshot
            .membership_prefixes(&workspace, &graph.tasks["app:build"])
            .unwrap();
        let before = snapshot
            .current_files_for(&workspace.root, Some(&left), "test")
            .unwrap();
        std::fs::write(root.path().join("right/empty/new.txt"), "right").unwrap();
        let unrelated = snapshot
            .current_files_for(&workspace.root, Some(&left), "test")
            .unwrap();
        assert!(Arc::ptr_eq(&before.files, &unrelated.files));
        assert!(!unrelated.files.contains("right/empty/new.txt"));
        assert!(
            snapshot
                .current_files_for(&workspace.root, Some(&right), "test")
                .unwrap()
                .files
                .contains("right/empty/new.txt")
        );
        std::fs::create_dir_all(root.path().join("left/empty/nested")).unwrap();
        std::fs::write(root.path().join("left/empty/nested/new.txt"), "left").unwrap();
        assert!(
            snapshot
                .current_files_for(&workspace.root, Some(&left), "test")
                .unwrap()
                .files
                .contains("left/empty/nested/new.txt")
        );
        std::fs::write(root.path().join("right/empty/another.txt"), "right").unwrap();
        assert!(
            snapshot
                .current_files_for(&workspace.root, Some(&all), "test")
                .unwrap()
                .files
                .contains("right/empty/another.txt")
        );
    }

    #[test]
    fn membership_watches_the_directories_json_globs_select_from() {
        let (root, mut workspace, _) = fixture(Some(json!(["{projectRoot}/dist"])));
        let targets = &mut workspace.projects.get_mut("app").unwrap().targets;
        targets.get_mut("build").unwrap().inputs = Some(vec![json!(
            {"json": "{workspaceRoot}/config/**/*.json", "fields": ["version"]}
        )]);
        std::fs::create_dir_all(root.path().join("config/empty")).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(&workspace.root).unwrap();
        std::thread::sleep(Duration::from_millis(2100));
        let prefixes = snapshot
            .membership_prefixes(&workspace, &graph.tasks["app:build"])
            .unwrap();
        snapshot
            .current_files_for(&workspace.root, Some(&prefixes), "test")
            .unwrap();
        std::fs::write(
            root.path().join("config/empty/new.json"),
            r#"{"version": 1}"#,
        )
        .unwrap();
        assert!(
            snapshot
                .current_files_for(&workspace.root, Some(&prefixes), "test")
                .unwrap()
                .files
                .contains("config/empty/new.json")
        );
    }

    #[test]
    fn membership_watches_git_ignored_tracked_parents_and_index_policy() {
        let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
        std::fs::create_dir_all(root.path().join("tracked/nested")).unwrap();
        std::fs::write(root.path().join("tracked/.gitignore"), "nested/\n").unwrap();
        std::fs::write(root.path().join("tracked/nested/source"), "one").unwrap();
        assert!(
            paths::git(root.path(), &["init", "-q"])
                .unwrap()
                .status
                .success()
        );
        assert!(
            paths::git(root.path(), &["add", "-f", "tracked/nested/source"])
                .unwrap()
                .status
                .success()
        );
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let files = || snapshot.current_files(root.path()).unwrap();
        assert!(files().contains("tracked/nested/source"));
        std::fs::remove_file(root.path().join("tracked/nested/source")).unwrap();
        assert!(!files().contains("tracked/nested/source"));
        std::fs::write(root.path().join("tracked/nested/another"), "two").unwrap();
        assert!(!files().contains("tracked/nested/another"));
        assert!(
            paths::git(root.path(), &["add", "-f", "tracked/nested/another"])
                .unwrap()
                .status
                .success()
        );
        assert!(files().contains("tracked/nested/another"));
        std::fs::write(root.path().join("untracked"), "three").unwrap();
        assert!(files().contains("untracked"));
        std::fs::write(root.path().join(".git/info/exclude"), "untracked\n").unwrap();
        assert!(!files().contains("untracked"));
    }

    #[test]
    fn a_new_git_config_include_invalidates_settled_listing_policy() {
        let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
        let policy = tempfile::tempdir().unwrap();
        let included = policy.path().join("included.config");
        let excludes = policy.path().join("excludes");
        std::fs::write(&excludes, "hidden\n").unwrap();
        std::fs::write(root.path().join("hidden"), "source").unwrap();
        assert!(
            paths::git(root.path(), &["init", "-q"])
                .unwrap()
                .status
                .success()
        );
        assert!(
            paths::git(
                root.path(),
                &["config", "include.path", included.to_str().unwrap()]
            )
            .unwrap()
            .status
            .success()
        );
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        snapshot.current_files(&workspace.root).unwrap();
        std::thread::sleep(Duration::from_millis(2100));
        let before = snapshot.current_files(&workspace.root).unwrap();
        assert!(before.contains("hidden"));
        assert!(Arc::ptr_eq(
            &before,
            &snapshot.current_files(&workspace.root).unwrap()
        ));
        assert!(
            paths::git(
                root.path(),
                &[
                    "config",
                    "--file",
                    included.to_str().unwrap(),
                    "core.excludesfile",
                    excludes.to_str().unwrap(),
                ]
            )
            .unwrap()
            .status
            .success()
        );
        assert!(
            !snapshot
                .current_files(&workspace.root)
                .unwrap()
                .contains("hidden")
        );
    }

    #[cfg(unix)]
    #[test]
    fn git_policy_paths_preserve_quoted_origins_and_multiline_values() {
        let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
        let policy = tempfile::tempdir().unwrap();
        // Git's text output C-quotes these origins and octal-escapes UTF-8.
        let included = policy.path().join("included\\é\t\n.config");
        let excludes = policy.path().join("excludes\\é\t\n");
        let replacement = policy.path().join("replacement\n");
        std::fs::write(&excludes, "hidden\n").unwrap();
        std::fs::write(&replacement, "visible\n").unwrap();
        for file in ["hidden", "visible"] {
            std::fs::write(root.path().join(file), "source").unwrap();
        }
        let git = |args: &[&str]| {
            let output = paths::git(root.path(), args).unwrap();
            assert!(output.status.success(), "{output:?}");
            output
        };
        git(&["init", "-q"]);
        git(&["config", "include.path", included.to_str().unwrap()]);
        git(&[
            "config",
            "--file",
            included.to_str().unwrap(),
            "core.excludesfile",
            excludes.to_str().unwrap(),
        ]);
        let text = git(&["config", "--show-origin", "--list"]);
        let text = String::from_utf8_lossy(&text.stdout);
        let quoted_origin = text
            .lines()
            .find_map(|line| {
                line.strip_prefix("file:\"")
                    .and_then(|_| line.split_once('\t'))
            })
            .unwrap()
            .0
            .strip_prefix("file:")
            .unwrap();
        let policies = git_membership_policies(root.path());
        assert!(!policies.contains(&root.path().join(quoted_origin)));
        assert!(policies.contains(&included));
        assert!(policies.contains(&excludes));
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        let initial = snapshot.current_files(&workspace.root).unwrap();
        assert!(!initial.contains("hidden"));
        assert!(initial.contains("visible"));
        std::thread::sleep(Duration::from_millis(2100));
        let settled = snapshot.current_files(&workspace.root).unwrap();
        assert!(Arc::ptr_eq(
            &settled,
            &snapshot.current_files(&workspace.root).unwrap()
        ));
        git(&[
            "config",
            "--file",
            included.to_str().unwrap(),
            "core.excludesfile",
            replacement.to_str().unwrap(),
        ]);
        let changed = snapshot.current_files(&workspace.root).unwrap();
        assert!(changed.contains("hidden"));
        assert!(!changed.contains("visible"));
        assert!(git_membership_policies(root.path()).contains(&replacement));
    }

    #[cfg(unix)]
    #[test]
    fn symlinked_ignore_policy_never_reuses_stale_membership() {
        let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
        let policy = tempfile::NamedTempFile::new().unwrap();
        std::fs::write(policy.path(), "hidden\n").unwrap();
        std::os::unix::fs::symlink(policy.path(), root.path().join(".gitignore")).unwrap();
        std::fs::write(root.path().join("hidden"), "source").unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &workspace.root.join("cache")).unwrap();
        assert!(
            !snapshot
                .current_files(root.path())
                .unwrap()
                .contains("hidden")
        );
        assert!(
            !snapshot
                .membership
                .lock()
                .unwrap()
                .as_ref()
                .unwrap()
                .settled
        );
        std::thread::sleep(Duration::from_millis(2100));
        let before = snapshot.current_files(root.path()).unwrap();
        assert!(Arc::ptr_eq(
            &before,
            &snapshot.current_files(root.path()).unwrap()
        ));
        std::fs::write(policy.path(), "").unwrap();
        assert!(
            snapshot
                .current_files(root.path())
                .unwrap()
                .contains("hidden")
        );
    }

    #[cfg(unix)]
    #[test]
    fn recent_change_time_prevents_membership_reuse_despite_old_mtime() {
        use std::os::unix::fs::MetadataExt;
        let root = tempfile::tempdir().unwrap();
        let old = SystemTime::UNIX_EPOCH + Duration::from_secs(1);
        File::open(root.path())
            .unwrap()
            .set_times(std::fs::FileTimes::new().set_modified(old))
            .unwrap();
        let metadata = std::fs::metadata(root.path()).unwrap();
        assert!(metadata.ctime() > 1);
        let stamp = Stamp::new(&metadata);
        assert!(stamp.settled());
        assert!(!stamp.membership_settled());
    }

    #[test]
    fn inspection_keeps_deleted_candidates() {
        let (root, workspace, graph) = fixture(Some(json!(["{projectRoot}/dist"])));
        let snapshot = Snapshot::new(&workspace, &graph, &root.path().join("cache"))
            .unwrap()
            .with_candidates(&["src/deleted".into()]);
        let resolved = resolve(
            &snapshot,
            &workspace,
            &graph.tasks["app:post"],
            None,
            &AtomicBool::new(false),
        )
        .unwrap();
        assert!(resolved.declared.files.contains("src/deleted"));
    }

    #[test]
    fn undeclared_writes_invalidate_dependency_values() {
        for outputs in [None, Some(json!(["{projectRoot}/generated"]))] {
            let (root, workspace, graph) = fixture(outputs);
            let snapshot = Snapshot::new(&workspace, &graph, &root.path().join("cache")).unwrap();
            let keys = || {
                dependency_keys(
                    &snapshot,
                    &workspace,
                    &graph,
                    &graph.tasks["app:build"],
                    &AtomicBool::new(false),
                )
                .unwrap()
            };
            let before = keys();
            std::fs::write(root.path().join("generated/value"), "different").unwrap();
            snapshot.outputs_written(&workspace, &graph.tasks["app:post"]);
            assert_ne!(before, keys());
        }
    }

    #[cfg(unix)]
    #[test]
    fn dependency_symlinks_recheck_targets_outside_output_roots() {
        let (root, mut workspace, _) = fixture(Some(json!(["{projectRoot}/generated"])));
        workspace
            .projects
            .get_mut("app")
            .unwrap()
            .targets
            .get_mut("gen")
            .unwrap()
            .outputs = Some(vec!["{projectRoot}/links".into()]);
        std::fs::create_dir(root.path().join("links")).unwrap();
        std::os::unix::fs::symlink("../generated/value", root.path().join("links/value")).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &root.path().join("cache")).unwrap();
        let keys = || {
            dependency_keys(
                &snapshot,
                &workspace,
                &graph,
                &graph.tasks["app:build"],
                &AtomicBool::new(false),
            )
            .unwrap()
        };
        let before = keys();
        std::fs::write(root.path().join("generated/value"), "different").unwrap();
        snapshot.outputs_written(&workspace, &graph.tasks["app:post"]);
        assert_ne!(before["app:gen:**/*"], keys()["app:gen:**/*"]);
    }
    /// The digest of a git-ignored file an `includeIgnored` fileset reads is
    /// saved with the others, so a warm run does not read it again.
    #[test]
    fn digests_of_ignored_files_read_by_include_ignored_are_saved() {
        let root = tempfile::tempdir().unwrap();
        std::fs::write(root.path().join("nx.json"), "{}").unwrap();
        std::fs::write(root.path().join(".gitignore"), "generated/\n").unwrap();
        std::fs::write(
            root.path().join("project.json"),
            json!({"name": "app", "targets": {"build": {"command": "true", "inputs": [
                {"fileset": "{projectRoot}/generated/**/*", "includeIgnored": true}
            ]}}})
            .to_string(),
        )
        .unwrap();
        std::fs::create_dir(root.path().join("generated")).unwrap();
        std::fs::write(root.path().join("generated/schema.json"), "{}").unwrap();
        // Digests are only saved for files old enough to have settled.
        let old = std::time::SystemTime::now() - std::time::Duration::from_secs(60);
        std::fs::File::options()
            .write(true)
            .open(root.path().join("generated/schema.json"))
            .unwrap()
            .set_times(std::fs::FileTimes::new().set_modified(old))
            .unwrap();
        let git = |args: &[&str]| assert!(paths::git(root.path(), args).unwrap().status.success());
        git(&["init", "--quiet"]);
        let workspace = Workspace::load(root.path()).unwrap();
        let graph = TaskGraph::build(&workspace, &[Request::parse("app:build").unwrap()]).unwrap();
        let snapshot = Snapshot::new(&workspace, &graph, &root.path().join("cache")).unwrap();
        assert!(!snapshot.files.contains("generated/schema.json"));
        let prepared =
            qk_executor::prepare(&workspace, &graph.tasks["app:build"], &BTreeMap::new()).unwrap();
        inputs(
            &snapshot,
            &workspace,
            &graph.tasks["app:build"],
            &prepared,
            &BTreeMap::new(),
            &AtomicBool::new(false),
        )
        .unwrap();
        snapshot.save_digests(root.path());
        assert!(load_digests(root.path()).contains_key("generated/schema.json"));
    }
}