characterminator 0.1.2

find and eliminate characters outside an allowed set, per file type and per file, so text costs fewer tokens
Documentation
//! The smallest grant that covers a file type (V128): a greedy set cover
//! over the curated presets, then the CLDR locales the letters left are
//! written in, then `any`, said as such.

use crate::charset::{CharSet, SetCatalog, is_punctuation, locale_names};
use crate::rules::TEXT;
use std::collections::BTreeSet;

/// The function presets a draft may grant, in the order a tie goes to:
/// the presets `src/charset:V23` sizes for code and docs. The coarse
/// blocks and scripts are left out on purpose: V23 recommends them only
/// for multi-language data, which a locale answers better.
const PRESETS: &[&str] = &[
    "caveman",
    "typography",
    "math",
    "legal",
    "marks",
    "box",
    "emoji",
    "cr",
];

/// What a draft grants one file type.
#[derive(Debug, PartialEq, Eq)]
pub(super) enum Grant {
    /// Presets (and maybe one locale), each with what it covers.
    Sets(Vec<(String, Vec<char>)>),
    /// Nothing curated covers these; `any` is the honest grant.
    Any(Vec<char>),
}

/// The builtin sets, resolved once: the presets and every locale's letters.
/// A `typography-<code>` is a grant to ask for, never to draft (B84): a
/// locale is chosen as what the text is written in.
pub(super) struct Candidates {
    presets: Vec<CharSet>,
    locales: Vec<CharSet>,
}

impl Candidates {
    pub(super) fn builtin() -> Self {
        let catalog = SetCatalog::builtin();
        let resolve = |name: &str| catalog.resolve(name, TEXT).ok();
        let letters = locale_names().filter(|name| !is_punctuation(name));
        Self {
            presets: PRESETS.iter().filter_map(|name| resolve(name)).collect(),
            locales: letters.filter_map(resolve).collect(),
        }
    }

    /// The grant for `needed`: presets by greatest gain, then the locales
    /// for the letters left ([`Self::letters`]), else `any`.
    pub(super) fn cover(&self, needed: &BTreeSet<char>) -> Grant {
        let mut left = needed.clone();
        let mut chosen = self.presets_for(&mut left);
        if left.is_empty() {
            return Grant::Sets(chosen);
        }
        let Some(locales) = self.letters(&left) else {
            return Grant::Any(left.into_iter().collect());
        };
        for locale in locales {
            chosen.push(taken(locale, &mut left));
        }
        Grant::Sets(chosen)
    }

    /// Whether the line drafted for `grant` allows `c`: `any` allows
    /// everything, and a set chosen for one character holds others too
    /// (`kek` holds U+2019, which the builtin map rewrites).
    pub(super) fn allows(&self, grant: &Grant, c: char) -> bool {
        let Grant::Sets(sets) = grant else {
            return true;
        };
        let mut all = self.presets.iter().chain(&self.locales);
        all.any(|set| {
            set.contains(c) && sets.iter().any(|(n, _)| *n == set.name)
        })
    }

    /// The presets by greatest gain, each taking what it covers out of
    /// `left`.
    fn presets_for(
        &self,
        left: &mut BTreeSet<char>,
    ) -> Vec<(String, Vec<char>)> {
        let mut chosen = Vec::new();
        while let Some(best) = best(&self.presets, left) {
            chosen.push(taken(best, left));
        }
        chosen
    }

    /// One locale when English's loan letters or a base language hold all
    /// of `left`; else the base language holding the most, plus a locale
    /// for the rest (B80: Polish text with one U+00E9 drafted a Finnish
    /// auxiliary set that held both by accident); else any one locale
    /// that holds all of it.
    fn letters(&self, left: &BTreeSet<char>) -> Option<Vec<&CharSet>> {
        let whole = smallest_covering(&self.locales, left);
        if whole.is_some_and(|set| set.name == LOAN_LETTERS || is_base(set)) {
            return whole.map(|set| vec![set]);
        }
        self.split(left).or_else(|| whole.map(|set| vec![set]))
    }

    /// The base language holding the most of `left`, and the locale
    /// [`smallest_covering`] picks for what it leaves.
    fn split(&self, left: &BTreeSet<char>) -> Option<Vec<&CharSet>> {
        let first = best(self.locales.iter().filter(|set| is_base(set)), left)?;
        let rest = left.iter().copied().filter(|c| !first.contains(*c));
        let second = smallest_covering(&self.locales, &rest.collect())?;
        Some(vec![first, second])
    }
}

/// A language's own code (`pl`), not a variant or an auxiliary set
/// (`fi-FI-aux`): the code a reader takes as what the text is written in.
fn is_base(set: &CharSet) -> bool {
    !set.name.contains('-')
}

/// The preset covering the most of `left`; a tie goes to the smaller set,
/// then to the earlier in [`PRESETS`]. `None` once nothing gains.
fn best<'a>(
    sets: impl IntoIterator<Item = &'a CharSet>,
    left: &BTreeSet<char>,
) -> Option<&'a CharSet> {
    let gain =
        |set: &CharSet| left.iter().filter(|c| set.contains(**c)).count();
    let mut found: Option<(&CharSet, usize)> = None;
    for set in sets {
        let won = gain(set);
        let better = found.is_none_or(|(held, had)| {
            won > had || (won == had && size(set) < size(held))
        });
        if won > 0 && better {
            found = Some((set, won));
        }
    }
    found.map(|(set, _)| set)
}

/// The locale a draft tries FIRST: English's loan letters (`cafe` with
/// U+00E9, `naive` with U+00EF), the accents an English-language
/// repository actually holds. Without it the smallest covering set wins,
/// which for one U+00E9 is a language nobody in the repository writes.
const LOAN_LETTERS: &str = "en-aux";

/// `en-aux` when it holds all of `left`, else the best-ranked locale that
/// does ([`rank`]).
fn smallest_covering<'a>(
    locales: &'a [CharSet],
    left: &BTreeSet<char>,
) -> Option<&'a CharSet> {
    let covers = |set: &&CharSet| left.iter().all(|c| set.contains(*c));
    let covering = locales.iter().filter(covers);
    let loan = covering.clone().find(|set| set.name == LOAN_LETTERS);
    loan.or_else(|| covering.min_by(|a, b| rank(a).cmp(&rank(b))))
}

/// `set`'s name and what it takes out of `left`.
fn taken(set: &CharSet, left: &mut BTreeSet<char>) -> (String, Vec<char>) {
    let covered: Vec<char> =
        left.iter().copied().filter(|c| set.contains(*c)).collect();
    left.retain(|c| !set.contains(*c));
    (set.name.clone(), covered)
}

/// A base locale (`zh`) before a variant (`yue-Hans`), then the smaller,
/// then by name: deterministic, and the code a reader would write.
fn rank(set: &CharSet) -> (bool, u32, &str) {
    (!is_base(set), size(set), set.name.as_str())
}

/// How many code points a set holds, saturating.
fn size(set: &CharSet) -> u32 {
    set.ranges.iter().fold(0_u32, |sum, range| {
        let width = u32::from(range.end).saturating_sub(u32::from(range.start));
        sum.saturating_add(width).saturating_add(1)
    })
}