fdu_core/query/

query_selection.rs

//! Which retained entries a query considers, and how its results are shaped.
//!
//! Selection is evaluated at view time against the index that a scan already built, never
//! during the walk. That split is what makes filters cheap and the cache reusable: scope
//! decides what is observed and cached, so one snapshot answers every selection, and
//! changing `--include` never invalidates anything. It is the same reasoning as tagging
//! ignored entries rather than pruning them.

use std::path::Path;

use crate::engine_contract::{EntryKind, Error, Result};
use crate::query::query_glob::Pattern;

/// Which size metric a report answers in.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum SizeMetric {
    /// Bytes the file's contents occupy logically.
    Apparent,
    /// Bytes the filesystem allocated, which sparse files and clones make differ.
    Allocated,
}

impl SizeMetric {
    /// Stable label, the inverse of [`parse_size_metric`](crate::query::parse_size_metric).
    ///
    /// `const` so a surface can declare the default metric's spelling from the defaults
    /// table rather than writing the word out again: the command line's `--size` help said
    /// `allocated` in a literal of its own.
    pub const fn label(self) -> &'static str {
        match self {
            Self::Apparent => "apparent",
            Self::Allocated => "allocated",
        }
    }

    /// One entry's own size in this metric.
    pub(crate) const fn of(self, attrs: &crate::Attrs) -> u64 {
        match self {
            Self::Apparent => attrs.size,
            Self::Allocated => attrs.allocated,
        }
    }
}

/// Allocated, from the request model's defaults table.
///
/// Read from the table rather than declared here, because this was the one place the
/// default was apparent: every surface answered in allocated bytes, and a Rust caller or
/// an opened-root read that named no metric got a different answer to the same request.
impl Default for SizeMetric {
    fn default() -> Self {
        crate::query::Request::DEFAULTS.size
    }
}

/// Which key results are ordered by.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum SortKey {
    /// Bytes, in the selected metric.
    #[default]
    Size,
    /// Entry counts.
    Count,
    /// Newest modification time.
    Mtime,
    /// Path or name, lexicographically.
    Name,
    /// One numeric content metric named by the shared metric registry.
    Metric(&'static str),
}

/// An inclusive-start, exclusive-end window over modification times, in nanoseconds.
///
/// Half-open on purpose: `[since, before)` composes without double-counting when a caller
/// walks a tree in windows, and the inclusive start is the safe side for sync — a file
/// whose mtime equals the watermark re-lists, because duplicates are cheap and omissions
/// are not.
#[derive(Clone, Copy, Debug, Default)]
pub struct ModifiedWindow {
    /// Inclusive lower bound.
    pub since: Option<i64>,
    /// Exclusive upper bound.
    pub before: Option<i64>,
}

impl ModifiedWindow {
    /// Whether a modification time falls inside the window.
    pub fn contains(&self, mtime_ns: i64) -> bool {
        self.since.is_none_or(|since| mtime_ns >= since)
            && self.before.is_none_or(|before| mtime_ns < before)
    }

    /// Whether the window constrains anything at all.
    pub fn is_unbounded(&self) -> bool {
        self.since.is_none() && self.before.is_none()
    }
}

/// Which entries a query considers by their `.gitignore` classification.
///
/// Selection rather than scope, like every other filter: the scan classifies every entry
/// and the index keeps both partitions, so choosing one never costs a rescan. An ignored
/// directory's descendants are all ignored, so rejecting entries one at a time prunes
/// exactly the subtrees `git` would.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default, Hash)]
pub enum IgnoredEntries {
    /// Every entry, ignored or not. Rows carry their ignored share.
    #[default]
    Include,
    /// Only entries no `.gitignore` rule ignores.
    Exclude,
    /// Only entries a `.gitignore` rule ignores.
    Only,
}

impl IgnoredEntries {
    /// Whether an entry with this classification passes.
    pub const fn admits(self, ignored: bool) -> bool {
        match self {
            Self::Include => true,
            Self::Exclude => !ignored,
            Self::Only => ignored,
        }
    }

    /// Parse the library's spelling: `include`, `exclude`, or `only`.
    ///
    /// The expectation only, as [`crate::query::ViewSpec::parse`] returns it, so each
    /// surface names its own knob in front of it.
    pub fn parse(value: &str) -> std::result::Result<Self, String> {
        match value.trim().to_ascii_lowercase().as_str() {
            "include" => Ok(Self::Include),
            "exclude" => Ok(Self::Exclude),
            "only" => Ok(Self::Only),
            _ => Err("expected one of include, exclude, only".to_string()),
        }
    }

    /// Stable label, the inverse of [`Self::parse`].
    pub const fn label(self) -> &'static str {
        match self {
            Self::Include => "include",
            Self::Exclude => "exclude",
            Self::Only => "only",
        }
    }
}

/// A bound that may be unlimited.
///
/// `--depth all` and `-n all` are spelled the same way as their numeric forms rather than
/// as a separate flag, so "how deep" and "how many" stay single questions.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum Bound {
    /// No limit.
    #[default]
    All,
    /// At most this many.
    Limit(usize),
}

impl Bound {
    /// Whether a zero-based index is within the bound.
    pub fn admits(self, index: usize) -> bool {
        match self {
            Self::All => true,
            Self::Limit(limit) => index < limit,
        }
    }

    /// The bound as a count, when it has one.
    pub fn limit(self) -> Option<usize> {
        match self {
            Self::All => None,
            Self::Limit(limit) => Some(limit),
        }
    }
}

/// An exact decimal percentage used only to select displayed rows.
///
/// Digits are kept as entered so comparisons never round a 1% boundary through a
/// floating-point conversion, including on very large byte counts.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ShareThreshold {
    whole: u8,
    fractional: Vec<u8>,
}

impl ShareThreshold {
    /// The ordinary tree threshold.
    pub fn one_percent() -> Self {
        Self { whole: 1, fractional: Vec::new() }
    }
    /// Parse a finite percentage from 0% through 100%.
    pub fn parse(value: &str) -> Option<Self> {
        let digits = value.trim().strip_suffix('%')?;
        let (whole, fraction) = digits.split_once('.').unwrap_or((digits, ""));
        if whole.is_empty()
            || !whole.bytes().all(|byte| byte.is_ascii_digit())
            || !fraction.bytes().all(|byte| byte.is_ascii_digit())
            || (digits.contains('.') && fraction.is_empty())
        {
            return None;
        }
        let whole: u8 = whole.parse().ok()?;
        if whole > 100 || (whole == 100 && fraction.bytes().any(|digit| digit != b'0')) {
            return None;
        }
        Some(Self { whole, fractional: fraction.bytes().map(|digit| digit - b'0').collect() })
    }

    /// Whether `part` contributes at least this share of `whole`.
    pub fn admits(&self, part: u64, whole: u64) -> bool {
        if self.whole == 0 && self.fractional.iter().all(|digit| *digit == 0) {
            return true;
        }
        if whole == 0 {
            return false;
        }
        let numerator = u128::from(part) * 100;
        let denominator = u128::from(whole);
        let integral = numerator / denominator;
        if integral != u128::from(self.whole) {
            return integral > u128::from(self.whole);
        }
        let mut remainder = numerator % denominator;
        for digit in &self.fractional {
            remainder *= 10;
            let actual = remainder / denominator;
            if actual != u128::from(*digit) {
                return actual > u128::from(*digit);
            }
            remainder %= denominator;
        }
        true
    }

    /// At least as many parts as this threshold can admit out of one whole they partition,
    /// or `None` when it bounds nothing this arithmetic can state.
    ///
    /// Parts whose sum is at most the whole can each reach a share `s` at most `⌊100 / s⌋`
    /// times, and none can when the whole is zero ([`Self::admits`]), so every such
    /// partition has at most that many admitted parts. The bound returned is
    /// `⌈100 / s⌉` for a share of up to 18 decimal places; a finer share is read truncated
    /// to 18 places, a smaller share than it spells, whose bound is therefore larger and
    /// still holds. A zero share admits every part and bounds nothing, as does a share
    /// finer than 18 places that truncates to zero.
    ///
    /// This is what lets a one-shot tree retain only the largest files: every file it can
    /// show as a row is among them, since each is a part of the root total it is measured
    /// against.
    pub(crate) fn admitted_parts_bound(&self) -> Option<u64> {
        const PLACES: usize = 18;
        let places = self.fractional.len().min(PLACES);
        let scale = 10_u128.pow(u32::try_from(places).expect("at most 18 places"));
        let spelled = self.fractional[..places]
            .iter()
            .fold(u128::from(self.whole), |value, digit| value * 10 + u128::from(*digit));
        if spelled == 0 {
            return None;
        }
        // `100 / (spelled / scale)`, rounded up; at most 10^20, below u128's range.
        u64::try_from((100 * scale).div_ceil(spelled)).ok()
    }

    /// Stable spelling for request serialization.
    pub fn label(&self) -> String {
        let mut out = self.whole.to_string();
        if !self.fractional.is_empty() {
            out.push('.');
            for digit in &self.fractional {
                out.push(char::from(b'0' + *digit));
            }
        }
        out.push('%');
        out
    }
}

/// Which retained entries a query considers, and how its results are shaped.
#[derive(Clone, Debug, Default)]
pub struct Selection {
    /// Patterns an entry must match at least one of, when non-empty.
    pub include: Vec<Pattern>,
    /// Patterns that exclude an entry outright; exclusion wins over inclusion.
    pub exclude: Vec<Pattern>,
    /// Smallest size, in the selected metric, an entry may have.
    pub min_size: Option<u64>,
    /// Entry kinds to consider; empty means every kind.
    pub kinds: Vec<EntryKind>,
    /// Modification-time window.
    pub modified: ModifiedWindow,
    /// Entries to consider by `.gitignore` classification.
    ///
    /// Anything but [`IgnoredEntries::Include`] needs an index that observed control
    /// state; [`crate::query::Request::validate`] refuses it otherwise.
    pub ignored: IgnoredEntries,
    /// How deep a rendered tree descends, or `None` to let each view apply its own.
    ///
    /// Optional for the same reason `limit` and `sort` are. The depth that suits a tree
    /// is not the depth that suits a flat enumeration, and while this was a plain
    /// `Bound` the only default the library could offer was "unbounded" -- so the CLI
    /// declared `default_value = "2"` itself and every other caller silently got a
    /// different report for the same request.
    pub depth: Option<Bound>,
    /// Minimum displayed share of the selected root, as an exact percentage.
    pub min_share: Option<ShareThreshold>,
    /// Maximum immediate child rows displayed per directory.
    pub breadth: Option<Bound>,
    /// How many entries a view reports.
    /// Rows to keep, or `None` to let each view apply its own bound.
    ///
    /// Optional for the same reason `sort` is: a bound that suits a per-directory tree
    /// is not the bound that suits a complete enumeration, and a single shared default
    /// produced "the ten alphabetically-first entries" of a 192,871-entry tree.
    pub limit: Option<Bound>,
    /// Ordering key, or `None` to let each view apply its own default.
    ///
    /// Optional rather than defaulted here because the sensible default differs by view:
    /// a tree and a type breakdown rank by size, while a flat file listing reads in name
    /// order. One shared default would be wrong for one of them.
    pub sort: Option<SortKey>,
    /// Whether the ordering is reversed.
    pub reverse: bool,
    /// Which size metric the report answers in.
    pub size: SizeMetric,
}

/// The facts about one entry that selection examines.
///
/// Passing a small explicit record rather than an index handle keeps the predicate pure
/// and trivially testable, and keeps selection from reaching into index internals.
///
/// `relative` and `name` carry one spelling of the entry, and every name-shaped predicate
/// -- globs, exact names, extensions, terminal suffixes, ancestor names -- is evaluated
/// against that spelling. A one-shot report and a watch use the native path. An opened-root
/// read uses the portable path a page returns, so a caller filters by the names it was
/// shown: see [`EntrySelection`].
#[derive(Clone, Copy, Debug)]
pub struct Candidate<'a> {
    /// Path relative to the index root, in the spelling the selection is evaluated in.
    pub relative: &'a Path,
    /// Final path component, in the same spelling as `relative`.
    pub name: &'a str,
    /// What the entry is.
    pub kind: EntryKind,
    /// Apparent size in bytes.
    pub bytes: u64,
    /// Allocated size in bytes.
    pub allocated: u64,
    /// Modification time in nanoseconds since the Unix epoch.
    pub mtime_ns: i64,
    /// Whether a `.gitignore` rule ignores the entry, or an ancestor of it.
    ///
    /// `false` in an index that observed no control state, where no selection by it is
    /// accepted.
    pub ignored: bool,
}

/// Additive selection for portable opened-root entry projections.
///
/// The established [`Selection`] remains the shared one-shot query contract. This value
/// composes it instead of adding fields to that public struct, preserving source
/// compatibility for existing Rust callers while keeping interactive row predicates in
/// one pure engine-owned value.
///
/// **Every axis sees the portable identity.** Inside an opened-root read, the name, the
/// relative path an anchored glob matches, and every ancestor component are the canonical
/// escaped `/`-joined spelling a page row carries as `portable_path`, never the native
/// path. `100%.txt` is `100%25.txt` to every predicate, and a directory whose native name
/// is not UTF-8 is matched by its escaped name, which is the only spelling a caller could
/// have been shown. A path taken from a page can therefore be passed back into a filter
/// unchanged. The same rule governs the base [`Selection`] and a `Report` projection's
/// selection inside an opened read; one-shot reports and watches keep native names.
///
/// Terminal suffixes and ancestor names are validated where they are written, by
/// [`Self::admit_terminal_extension`] and [`Self::admit_ancestor_name`], and again by
/// [`Self::validate`] when a read receives the selection: every spelling that could only
/// ever match nothing is refused, the same set the `MetaBrowser` `CatalogQuery` contract
/// refuses, so the two providers reject the same values rather than one answering with an
/// empty page.
#[derive(Clone, Debug, Default)]
pub struct EntrySelection {
    /// Existing fdu query predicates.
    pub query: Selection,
    /// Largest size, inclusive, in the selected metric.
    ///
    /// A caller with an exclusive upper bound translates `less_than: n` to `n - 1`.
    pub max_size: Option<u64>,
    /// Exclude entries in the fixed ignored partition.
    pub exclude_ignored: bool,
    /// Logical extensions to admit, including the leading dot.
    ///
    /// This is name identity, not the registry's canonical classification bucket.
    pub logical_extensions: Vec<String>,
    /// Exact basenames to admit, compared case-insensitively.
    ///
    /// When either this or `logical_extensions` is nonempty, matching either admits the
    /// name. That represents one identity filter rather than two intersected filters.
    pub exact_names: Vec<String>,
    /// Lowercase terminal suffixes to admit, including the leading dot.
    ///
    /// Unlike a logical extension, only the final dotted component participates. Each
    /// entry is unique, starts with a dot, is lowercase, and is one suffix: `.rs`, never
    /// `rs`, `.RS`, `.`, `.tar.gz`, or a value holding a separator.
    pub terminal_extensions: Vec<String>,
    /// Exact ancestor path-component names to admit, as portable components.
    ///
    /// Each entry is unique and one whole component: never empty, `.`, `..`, or a value
    /// holding `/` or `\`.
    pub ancestor_names: Vec<String>,
}

/// Which spelling of an entry's path a selection is evaluated against.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum NameIdentity {
    /// The native path, as one-shot reports and watches match it.
    Native,
    /// The canonical escaped path, as every opened-root read matches it.
    Portable,
}

impl From<Selection> for EntrySelection {
    fn from(query: Selection) -> Self {
        Self { query, ..Self::default() }
    }
}

impl Selection {
    /// Heap payload retained when an opened-root continuation owns this selection.
    pub(crate) fn retained_heap_bytes(&self) -> usize {
        let pattern_bytes =
            self.include.iter().chain(&self.exclude).fold(0_usize, |total, pattern| {
                total.saturating_add(pattern.retained_heap_bytes())
            });
        self.include
            .capacity()
            .saturating_add(self.exclude.capacity())
            .saturating_mul(std::mem::size_of::<Pattern>())
            .saturating_add(pattern_bytes)
            .saturating_add(self.kinds.capacity().saturating_mul(std::mem::size_of::<EntryKind>()))
    }

    /// Whether this selection constrains which entries are considered.
    ///
    /// An unconstrained selection lets a view read pre-computed roll-up state directly
    /// instead of traversing entries, which is the difference between the two performance
    /// tiers a report can run in.
    pub fn is_unfiltered(&self) -> bool {
        self.include.is_empty()
            && self.exclude.is_empty()
            && self.min_size.is_none()
            && self.kinds.is_empty()
            && self.modified.is_unbounded()
            && self.ignored == IgnoredEntries::Include
    }

    /// Whether an entry passes every filter.
    pub fn admits(&self, candidate: &Candidate<'_>) -> bool {
        if !self.kinds.is_empty() && !self.kinds.contains(&candidate.kind) {
            return false;
        }
        if !self.ignored.admits(candidate.ignored) {
            return false;
        }
        if let Some(min_size) = self.min_size {
            if self.size_of(candidate) < min_size {
                return false;
            }
        }
        if !self.modified.contains(candidate.mtime_ns) {
            return false;
        }
        // Exclusion wins: a pattern the caller wrote to keep something out should not be
        // overridden by a broader pattern they wrote to let things in.
        if self.exclude.iter().any(|p| p.matches(candidate.relative, candidate.name)) {
            return false;
        }
        if self.include.is_empty() {
            return true;
        }
        self.include.iter().any(|p| p.matches(candidate.relative, candidate.name))
    }

    /// The size of an entry in the selected metric.
    pub fn size_of(&self, candidate: &Candidate<'_>) -> u64 {
        match self.size {
            SizeMetric::Apparent => candidate.bytes,
            SizeMetric::Allocated => candidate.allocated,
        }
    }
}

impl EntrySelection {
    /// Add one terminal suffix, refusing a spelling that could only ever match nothing.
    ///
    /// # Errors
    ///
    /// [`Error::InvalidValue`] for a duplicate, an undotted or non-lowercase suffix, a bare
    /// dot, a compound suffix such as `.tar.gz`, or a value holding a separator.
    pub fn admit_terminal_extension(&mut self, value: impl Into<String>) -> Result<()> {
        let value = value.into();
        if self.terminal_extensions.contains(&value) {
            return Err(refusal(TERMINAL_KIND, &value, TERMINAL_UNIQUE));
        }
        check_value(TERMINAL_KIND, &value, TERMINAL_RULES)?;
        self.terminal_extensions.push(value);
        Ok(())
    }

    /// Add one ancestor name, refusing a value that is not one whole path component.
    ///
    /// # Errors
    ///
    /// [`Error::InvalidValue`] for a duplicate, an empty name, `.` or `..`, or a value
    /// holding `/` or `\`.
    pub fn admit_ancestor_name(&mut self, value: impl Into<String>) -> Result<()> {
        let value = value.into();
        if self.ancestor_names.contains(&value) {
            return Err(refusal(ANCESTOR_KIND, &value, ANCESTOR_UNIQUE));
        }
        check_value(ANCESTOR_KIND, &value, ANCESTOR_RULES)?;
        self.ancestor_names.push(value);
        Ok(())
    }

    /// Check the axes a caller may have written straight into the public fields.
    ///
    /// The admitting constructors apply the same rules one value at a time; a read applies
    /// this to every selection it receives, so a hand-built value is refused the same way.
    ///
    /// # Errors
    ///
    /// The refusal `MetaBrowser`'s `CatalogQuery` and the Python `EntrySelection` raise
    /// first, in their order: terminal extensions before ancestor names, and within each
    /// list uniqueness first, then each rule across the whole list. A list wrong in two
    /// ways therefore gets the same message on every surface.
    pub fn validate(&self) -> Result<()> {
        check_list(TERMINAL_KIND, &self.terminal_extensions, TERMINAL_UNIQUE, TERMINAL_RULES)?;
        check_list(ANCESTOR_KIND, &self.ancestor_names, ANCESTOR_UNIQUE, ANCESTOR_RULES)
    }

    /// Heap payload retained when an opened-root continuation owns this selection.
    pub(crate) fn retained_heap_bytes(&self) -> usize {
        self.query
            .retained_heap_bytes()
            .saturating_add(retained_strings(
                &self.logical_extensions,
                self.logical_extensions.capacity(),
            ))
            .saturating_add(retained_strings(&self.exact_names, self.exact_names.capacity()))
            .saturating_add(retained_strings(
                &self.terminal_extensions,
                self.terminal_extensions.capacity(),
            ))
            .saturating_add(retained_strings(&self.ancestor_names, self.ancestor_names.capacity()))
    }

    /// Whether this portable entry selection constrains any row.
    pub fn is_unfiltered(&self) -> bool {
        self.query.is_unfiltered()
            && self.max_size.is_none()
            && !self.exclude_ignored
            && self.logical_extensions.is_empty()
            && self.exact_names.is_empty()
            && self.terminal_extensions.is_empty()
            && self.ancestor_names.is_empty()
    }

    /// Whether an entry passes the base query and every opened-row predicate.
    pub fn admits(&self, candidate: &Candidate<'_>) -> bool {
        if !self.query.admits(candidate) {
            return false;
        }
        if let Some(max_size) = self.max_size {
            if self.query.size_of(candidate) > max_size {
                return false;
            }
        }
        if self.exclude_ignored && candidate.ignored {
            return false;
        }
        if !self.logical_extensions.is_empty() || !self.exact_names.is_empty() {
            if candidate.kind != EntryKind::File {
                return false;
            }
            let extension_matches = crate::classify::logical_ext(candidate.name.as_ref())
                .is_some_and(|extension| {
                    self.logical_extensions
                        .iter()
                        .any(|expected| extension.eq_ignore_ascii_case(expected))
                });
            let name_matches = self
                .exact_names
                .iter()
                .any(|expected| candidate.name.eq_ignore_ascii_case(expected));
            if !extension_matches && !name_matches {
                return false;
            }
        }
        if !self.terminal_extensions.is_empty() {
            if candidate.kind != EntryKind::File {
                return false;
            }
            let Some(suffix) = terminal_suffix(candidate.name) else {
                return false;
            };
            if !self
                .terminal_extensions
                .iter()
                .any(|expected| suffix.eq_ignore_ascii_case(expected))
            {
                return false;
            }
        }
        if !self.ancestor_names.is_empty()
            && !candidate.relative.parent().is_some_and(|parent| {
                parent.components().any(|component| {
                    let std::path::Component::Normal(name) = component else {
                        return false;
                    };
                    self.ancestor_names.iter().any(|expected| name == expected.as_str())
                })
            })
        {
            return false;
        }
        true
    }
}

const TERMINAL_KIND: &str = "terminal extension";
const ANCESTOR_KIND: &str = "ancestor name";
const TERMINAL_UNIQUE: &str = "terminal_extensions entries must be unique";
const ANCESTOR_UNIQUE: &str = "ancestor_names entries must be unique";

/// One `CatalogQuery` rule: whether a value breaks it, and the message that says so.
type Rule = (fn(&str) -> bool, &'static str);

/// The `MetaBrowser` `CatalogQuery` rules for terminal suffixes, in its order.
///
/// Each rule may assume the ones before it held for every value in the list: the last
/// slices past a leading dot the first one proved.
const TERMINAL_RULES: &[Rule] = &[
    (undotted, "terminal_extensions entries must start with a dot"),
    (not_lowercase, "terminal_extensions entries must be lowercase"),
    (not_terminal_suffix, "terminal_extensions entries must be canonical terminal suffixes"),
];

/// The `MetaBrowser` `CatalogQuery` rule for ancestor names.
const ANCESTOR_RULES: &[Rule] =
    &[(not_path_component, "ancestor_names entries must be exact path-component names")];

fn undotted(value: &str) -> bool {
    !value.starts_with('.')
}

/// Unicode lowering, as the contract's `str.lower` check is: an uppercase letter outside
/// ASCII is refused too, even though matching folds only ASCII.
fn not_lowercase(value: &str) -> bool {
    value.to_lowercase() != value
}

fn not_terminal_suffix(value: &str) -> bool {
    value.chars().count() < 2 || value.contains(['/', '\\']) || value[1..].contains('.')
}

fn not_path_component(value: &str) -> bool {
    value.is_empty() || value == "." || value == ".." || value.contains(['/', '\\'])
}

fn refusal(kind: &'static str, value: &str, hint: &str) -> Error {
    Error::InvalidValue { kind, value: value.to_owned(), hint: hint.to_owned() }
}

/// Refuse one value by the first rule it breaks.
fn check_value(kind: &'static str, value: &str, rules: &[Rule]) -> Result<()> {
    match rules.iter().find(|(breaks, _)| breaks(value)) {
        Some((_, hint)) => Err(refusal(kind, value, hint)),
        None => Ok(()),
    }
}

/// Refuse a whole list the way `CatalogQuery.__post_init__` does: uniqueness first, then
/// each rule across every value before the next rule is tried.
fn check_list(kind: &'static str, values: &[String], unique: &str, rules: &[Rule]) -> Result<()> {
    let mut seen = std::collections::HashSet::with_capacity(values.len());
    if let Some(repeated) = values.iter().find(|value| !seen.insert(value.as_str())) {
        return Err(refusal(kind, repeated, unique));
    }
    for (breaks, hint) in rules {
        if let Some(value) = values.iter().find(|value| breaks(value)) {
            return Err(refusal(kind, value, hint));
        }
    }
    Ok(())
}

fn retained_strings(values: &[String], capacity: usize) -> usize {
    capacity.saturating_mul(std::mem::size_of::<String>()).saturating_add(
        values.iter().fold(0_usize, |total, value| total.saturating_add(value.capacity())),
    )
}

fn terminal_suffix(name: &str) -> Option<&str> {
    let dot = name.rfind('.')?;
    (dot > 0 && dot + 1 < name.len()).then_some(&name[dot..])
}

#[cfg(test)]
mod tests {
    #[test]
    fn decimal_shares_compare_exactly_at_and_below_a_boundary() {
        use super::ShareThreshold;
        let share = ShareThreshold::parse("1%").expect("percentage");
        assert!(share.admits(1, 100));
        assert!(!share.admits(1, 101));
        assert!(share.admits(u64::MAX / 100, u64::MAX / 100));
        assert!(!share.admits(0, 0));
        assert!(ShareThreshold::parse("0%").expect("zero").admits(0, 0));
        assert!(
            ShareThreshold::parse("0.0000000000000000001%")
                .expect("fine precision")
                .admits(1, u64::MAX)
        );
        for invalid in ["-1%", "101%", "100.1%", "NaN%", "1", "1.%", "1e1%"] {
            assert!(ShareThreshold::parse(invalid).is_none(), "{invalid}");
        }
    }

    /// The bound is `⌈100 / share⌉` wherever the share is spelled exactly, and no partition
    /// of a whole ever has more admitted parts than it: checked exhaustively over every
    /// multiset of parts of small wholes, at shares on and off an exact divisor.
    #[test]
    fn no_partition_admits_more_parts_than_the_share_bounds() {
        use super::ShareThreshold;

        /// Every multiset of at most 12 parts summing to at most `whole`, largest first.
        fn partitions(whole: u64, largest: u64, prefix: &mut Vec<u64>, out: &mut Vec<Vec<u64>>) {
            out.push(prefix.clone());
            if prefix.len() == 12 {
                return;
            }
            for part in (0..=largest.min(whole)).rev() {
                prefix.push(part);
                partitions(whole - part, part, prefix, out);
                prefix.pop();
            }
        }

        let bound =
            |share: &str| ShareThreshold::parse(share).expect("percentage").admitted_parts_bound();
        for (share, expected) in [
            ("100%", Some(1)),
            ("10%", Some(10)),
            ("3%", Some(34)),
            ("1%", Some(100)),
            ("1.0%", Some(100)),
            ("0.5%", Some(200)),
            ("0.01%", Some(10_000)),
            ("0.00152587890625%", Some(65_536)),
            ("0.0015258%", Some(65_540)),
            ("0%", None),
            ("0.000%", None),
            ("0.0000000000000000001%", None),
        ] {
            assert_eq!(bound(share), expected, "{share}");
        }
        // Past 18 places the share is read truncated, so the bound is at least the true one.
        assert_eq!(bound("0.0010000000000000000001%"), Some(100_000));

        for share in ["100%", "50%", "33%", "33.4%", "25%", "12.5%", "10%", "9.99%"] {
            let threshold = ShareThreshold::parse(share).expect("percentage");
            let bound = threshold.admitted_parts_bound().expect("a positive share bounds parts");
            for whole in 0..=12 {
                let mut all = Vec::new();
                partitions(whole, whole, &mut Vec::new(), &mut all);
                for parts in all {
                    let total = parts.iter().sum::<u64>();
                    let admitted =
                        parts.iter().filter(|part| threshold.admits(**part, total)).count();
                    assert!(
                        u64::try_from(admitted).expect("small") <= bound,
                        "{share}: {parts:?} admits {admitted} > {bound}"
                    );
                }
            }
        }
    }
    use super::*;
    use std::path::PathBuf;

    fn candidate(path: &str, kind: EntryKind, bytes: u64, mtime_ns: i64) -> (PathBuf, String) {
        let relative = PathBuf::from(path);
        let name = relative
            .file_name()
            .map(|name| name.to_string_lossy().into_owned())
            .unwrap_or_default();
        let _ = (kind, bytes, mtime_ns);
        (relative, name)
    }

    fn entry_admits(
        selection: &EntrySelection,
        path: &str,
        kind: EntryKind,
        bytes: u64,
        mtime: i64,
        ignored: bool,
    ) -> bool {
        let (relative, name) = candidate(path, kind, bytes, mtime);
        selection.admits(&Candidate {
            relative: &relative,
            name: &name,
            kind,
            bytes,
            allocated: bytes.div_ceil(512) * 512,
            mtime_ns: mtime,
            ignored,
        })
    }

    fn admits(selection: &Selection, path: &str, kind: EntryKind, bytes: u64, mtime: i64) -> bool {
        classified_admits(selection, path, kind, bytes, mtime, false)
    }

    fn classified_admits(
        selection: &Selection,
        path: &str,
        kind: EntryKind,
        bytes: u64,
        mtime: i64,
        ignored: bool,
    ) -> bool {
        let (relative, name) = candidate(path, kind, bytes, mtime);
        selection.admits(&Candidate {
            relative: &relative,
            name: &name,
            kind,
            bytes,
            allocated: bytes.div_ceil(512) * 512,
            mtime_ns: mtime,
            ignored,
        })
    }

    fn pattern(source: &str) -> Pattern {
        Pattern::parse(source).expect("pattern compiles")
    }

    #[test]
    fn a_default_selection_admits_everything_and_reads_the_fast_tier() {
        let selection = Selection::default();
        assert!(selection.is_unfiltered());
        assert!(admits(&selection, "src/main.rs", EntryKind::File, 10, 5));
        assert!(admits(&selection, "src", EntryKind::Dir, 0, 5));
    }

    #[test]
    fn include_patterns_narrow_and_exclude_patterns_win() {
        let mut selection = Selection { include: vec![pattern("*.rs")], ..Selection::default() };
        assert!(!selection.is_unfiltered());
        assert!(admits(&selection, "src/main.rs", EntryKind::File, 10, 5));
        assert!(!admits(&selection, "src/main.toml", EntryKind::File, 10, 5));

        // An exclusion beats a matching inclusion, so a narrowing rule cannot be undone
        // by a broader one written elsewhere on the command line.
        selection.exclude.push(pattern("**/generated/**"));
        assert!(!admits(&selection, "src/generated/api.rs", EntryKind::File, 10, 5));
        assert!(admits(&selection, "src/hand/api.rs", EntryKind::File, 10, 5));
    }

    #[test]
    fn min_size_follows_the_selected_metric() {
        let apparent = Selection { min_size: Some(600), ..Selection::default() };
        // 100 apparent bytes occupy 512 allocated bytes: neither reaches 600.
        assert!(!admits(&apparent, "a.bin", EntryKind::File, 100, 0));

        let allocated =
            Selection { min_size: Some(600), size: SizeMetric::Allocated, ..Selection::default() };
        // 600 apparent bytes occupy 1024 allocated bytes, which does reach 600.
        assert!(admits(&allocated, "a.bin", EntryKind::File, 600, 0));
        assert!(!admits(&allocated, "b.bin", EntryKind::File, 100, 0));
    }

    #[test]
    fn the_modified_window_is_half_open() {
        let selection = Selection {
            modified: ModifiedWindow { since: Some(100), before: Some(200) },
            ..Selection::default()
        };
        // Inclusive start: a file at exactly the watermark re-lists, because for sync a
        // duplicate is safe and an omission is not.
        assert!(admits(&selection, "a", EntryKind::File, 1, 100));
        assert!(admits(&selection, "b", EntryKind::File, 1, 150));
        // Exclusive end.
        assert!(!admits(&selection, "c", EntryKind::File, 1, 200));
        assert!(!admits(&selection, "d", EntryKind::File, 1, 99));
    }

    #[test]
    fn kinds_filter_and_an_empty_list_means_every_kind() {
        let files = Selection { kinds: vec![EntryKind::File], ..Selection::default() };
        assert!(admits(&files, "a.rs", EntryKind::File, 1, 0));
        assert!(!admits(&files, "src", EntryKind::Dir, 0, 0));

        let both =
            Selection { kinds: vec![EntryKind::File, EntryKind::Dir], ..Selection::default() };
        assert!(admits(&both, "src", EntryKind::Dir, 0, 0));
        assert!(!admits(&both, "link", EntryKind::Symlink, 0, 0));
    }

    /// Selecting by ignored state is a filter like any other: it forces the traversal tier,
    /// and each mode admits exactly its partition.
    #[test]
    fn ignored_entries_select_one_partition_or_both() {
        let include = Selection::default();
        let exclude = Selection { ignored: IgnoredEntries::Exclude, ..Selection::default() };
        let only = Selection { ignored: IgnoredEntries::Only, ..Selection::default() };
        assert!(!exclude.is_unfiltered() && !only.is_unfiltered());
        for (selection, admits_unignored, admits_ignored) in
            [(&include, true, true), (&exclude, true, false), (&only, false, true)]
        {
            assert_eq!(
                classified_admits(selection, "src/lib.rs", EntryKind::File, 1, 0, false),
                admits_unignored,
                "{:?} on an unignored entry",
                selection.ignored
            );
            assert_eq!(
                classified_admits(selection, "dist", EntryKind::Dir, 0, 0, true),
                admits_ignored,
                "{:?} on an ignored entry",
                selection.ignored
            );
        }
        for mode in [IgnoredEntries::Include, IgnoredEntries::Exclude, IgnoredEntries::Only] {
            assert_eq!(IgnoredEntries::parse(mode.label()), Ok(mode));
        }
        assert_eq!(
            IgnoredEntries::parse("some"),
            Err("expected one of include, exclude, only".to_string())
        );
    }

    #[test]
    fn portable_catalog_predicates_compose_without_client_side_filtering() {
        let selection = EntrySelection {
            // Apparent, so the bound reads the sizes written below rather than their blocks.
            query: Selection { size: SizeMetric::Apparent, ..Selection::default() },
            max_size: Some(10),
            exclude_ignored: true,
            terminal_extensions: vec![".rs".to_string(), ".md".to_string()],
            ancestor_names: vec!["src".to_string(), "docs".to_string()],
            ..EntrySelection::default()
        };
        assert!(entry_admits(&selection, "src/lib.rs", EntryKind::File, 10, 0, false));
        assert!(entry_admits(&selection, "docs/readme.md", EntryKind::File, 9, 0, false));
        assert!(!entry_admits(&selection, "src/lib.RS", EntryKind::File, 11, 0, false));
        assert!(!entry_admits(&selection, "tests/lib.rs", EntryKind::File, 9, 0, false));
        assert!(!entry_admits(&selection, "src/lib.rs", EntryKind::File, 9, 0, true));
        assert!(!entry_admits(&selection, "src/.gitignore", EntryKind::File, 1, 0, false));
    }

    #[test]
    fn logical_extensions_and_exact_names_form_one_name_identity_filter() {
        let selection = EntrySelection {
            logical_extensions: vec![".v2.zip".to_string()],
            exact_names: vec!["makefile".to_string()],
            ..EntrySelection::default()
        };
        assert!(entry_admits(&selection, "release.v2.zip", EntryKind::File, 1, 0, false));
        assert!(entry_admits(&selection, "Makefile", EntryKind::File, 1, 0, false));
        assert!(!entry_admits(&selection, "plain.zip", EntryKind::File, 1, 0, false));
        assert!(!entry_admits(&selection, "README", EntryKind::File, 1, 0, false));
    }

    #[test]
    fn terminal_extensions_and_ancestor_names_refuse_what_could_never_match() {
        let refused = |hint: &str, outcome: Result<()>| match outcome {
            Err(Error::InvalidValue { hint: actual, .. }) => {
                assert!(actual.contains(hint), "{actual:?} names {hint:?}");
            }
            other => panic!("expected a refusal naming {hint:?}, got {other:?}"),
        };
        for (value, hint) in [
            ("rs", "start with a dot"),
            (".RS", "lowercase"),
            (".Ée", "lowercase"),
            (".", "canonical terminal suffixes"),
            (".tar.gz", "canonical terminal suffixes"),
            ("..", "canonical terminal suffixes"),
            (".a/b", "canonical terminal suffixes"),
            (".a\\b", "canonical terminal suffixes"),
        ] {
            let mut selection = EntrySelection::default();
            refused(hint, selection.admit_terminal_extension(value));
            assert!(selection.terminal_extensions.is_empty(), "{value:?} was not added");
            let written = EntrySelection {
                terminal_extensions: vec![value.to_string()],
                ..Default::default()
            };
            refused(hint, written.validate());
        }
        for value in ["", ".", "..", "a/b", "a\\b"] {
            let mut selection = EntrySelection::default();
            refused("exact path-component names", selection.admit_ancestor_name(value));
            let written =
                EntrySelection { ancestor_names: vec![value.to_string()], ..Default::default() };
            refused("exact path-component names", written.validate());
        }

        let mut selection = EntrySelection::default();
        selection.admit_terminal_extension(".rs").expect("a canonical suffix");
        selection.admit_terminal_extension(".c++").expect("a non-alphanumeric suffix");
        refused("unique", selection.admit_terminal_extension(".rs"));
        selection.admit_ancestor_name("src").expect("a component");
        selection.admit_ancestor_name("x%FF").expect("an escaped component");
        selection.admit_ancestor_name("..foo").expect("dots inside a name");
        refused("unique", selection.admit_ancestor_name("src"));
        assert_eq!(selection.terminal_extensions, [".rs", ".c++"]);
        assert_eq!(selection.ancestor_names, ["src", "x%FF", "..foo"]);
        selection.validate().expect("admitted values validate");
        refused(
            "unique",
            EntrySelection {
                terminal_extensions: vec![".md".to_string(), ".md".to_string()],
                ..Default::default()
            }
            .validate(),
        );
        refused(
            "unique",
            EntrySelection {
                ancestor_names: vec!["docs".to_string(), "docs".to_string()],
                ..Default::default()
            }
            .validate(),
        );
    }

    /// A list wrong in two ways gets the refusal `CatalogQuery` and the Python
    /// `EntrySelection` raise, so every surface names the same fault: uniqueness before
    /// shape, and each rule across the whole list before the next rule.
    #[test]
    fn a_list_wrong_twice_is_refused_in_the_catalog_query_order() {
        let hint_of = |selection: EntrySelection| match selection.validate() {
            Err(Error::InvalidValue { hint, .. }) => hint,
            other => panic!("expected a refusal, got {other:?}"),
        };
        let terminal = |values: &[&str]| EntrySelection {
            terminal_extensions: values.iter().map(ToString::to_string).collect(),
            ..Default::default()
        };
        let ancestors = |values: &[&str]| EntrySelection {
            ancestor_names: values.iter().map(ToString::to_string).collect(),
            ..Default::default()
        };
        for (selection, hint) in [
            (terminal(&["rs", "rs"]), TERMINAL_UNIQUE),
            (terminal(&[".RS", ".RS"]), TERMINAL_UNIQUE),
            (terminal(&[".RS", "rs"]), "terminal_extensions entries must start with a dot"),
            (terminal(&[".tar.gz", ".RS"]), "terminal_extensions entries must be lowercase"),
            (ancestors(&["..", ".."]), ANCESTOR_UNIQUE),
            (
                EntrySelection {
                    terminal_extensions: vec!["rs".to_string()],
                    ancestor_names: vec!["src".to_string(), "src".to_string()],
                    ..Default::default()
                },
                "terminal_extensions entries must start with a dot",
            ),
        ] {
            assert_eq!(hint_of(selection), hint);
        }
    }

    #[test]
    fn bounds_admit_by_index_and_report_their_limit() {
        assert!(Bound::All.admits(1_000_000));
        assert_eq!(Bound::All.limit(), None);
        assert!(Bound::Limit(2).admits(0));
        assert!(Bound::Limit(2).admits(1));
        assert!(!Bound::Limit(2).admits(2));
        assert_eq!(Bound::Limit(2).limit(), Some(2));
        // `--depth 0` keeps du's meaning: root totals only, nothing below.
        assert!(!Bound::Limit(0).admits(0));
    }

    #[test]
    fn an_unbounded_window_does_not_constrain() {
        assert!(ModifiedWindow::default().is_unbounded());
        assert!(ModifiedWindow::default().contains(i64::MIN));
        assert!(ModifiedWindow::default().contains(i64::MAX));
    }
}