face_core/

strategy.rs

//! Grouping axes and per-axis strategies (§5 and §7's `result.axes[]`).
//!
//! [`Axis`] describes one level of grouping: a field path, the strategy
//! applied to that field, and whether the strategy was auto-picked.
//! [`Strategy`] is the tagged enum of strategies the public surface
//! recognizes today, including the explicit algorithmic similarity
//! strategies from §5.4.

use serde::{Deserialize, Serialize};

/// One axis of grouping (§5, §7 `result.axes[]`).
///
/// Serializes with the strategy tag and payload flattened directly into
/// the axis JSON object so the wire form matches §7's example:
/// `{ "field": "data.path.text", "strategy": "exact", "auto": true }`.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
#[non_exhaustive]
pub struct Axis {
    /// Field path being grouped on (e.g. `data.path.text`).
    pub field: String,
    /// Strategy applied to this axis.
    #[serde(flatten)]
    pub strategy: Strategy,
    /// `true` when the strategy was auto-picked rather than user-supplied.
    pub auto: bool,
}

/// Strategy applied to one axis.
///
/// # Examples
///
/// ```
/// use face_core::Strategy;
///
/// assert!(Strategy::Quantiles { count: 4 }.is_buffered());
/// assert!(!Strategy::Exact.is_buffered());
/// ```
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
#[serde(tag = "strategy", rename_all = "lowercase")]
#[non_exhaustive]
pub enum Strategy {
    /// One cluster per distinct value (§5.3).
    Exact,
    /// Path / namespace grouping by directory depth (§5.3).
    Prefix {
        /// Optional fixed prefix depth; `None` means auto-pick.
        #[serde(skip_serializing_if = "Option::is_none", default)]
        depth: Option<u8>,
    },
    /// Top-N by frequency plus a synthetic `(other)` cluster (§5.3).
    Top {
        /// How many top buckets to keep.
        n: u32,
    },
    /// Equal-width bands over the numeric range (§5.2).
    Bands {
        /// Number of bands.
        count: u8,
    },
    /// Equal-population quantile buckets (§5.2). Buffered (§12).
    Quantiles {
        /// Number of quantile buckets.
        count: u8,
    },
    /// One-dimensional Jenks natural breaks (§5.2). Buffered (§12).
    Natural {
        /// Number of natural-break buckets.
        count: u8,
    },
    /// Algorithmic free-form string clustering (§5.4). Buffered.
    Similar {
        /// Similarity algorithm to use.
        algorithm: SimilarAlgorithm,
    },
}

/// Algorithm used by [`Strategy::Similar`].
#[derive(Debug, Clone, Copy, Serialize, Deserialize, PartialEq, Eq, Hash)]
#[serde(rename_all = "lowercase")]
#[non_exhaustive]
pub enum SimilarAlgorithm {
    /// Token-set Jaccard similarity.
    Token,
    /// Character trigram Jaccard similarity.
    Ngram,
    /// Normalized Levenshtein similarity.
    Edit,
    /// Token-set locality-sensitive bucketing approximation.
    Lsh,
    /// Token simhash near-duplicate detection.
    Simhash,
}

impl SimilarAlgorithm {
    /// Parse a CLI payload such as `token` or `simhash`.
    pub fn from_name(name: &str) -> Option<Self> {
        match name.to_ascii_lowercase().as_str() {
            "token" => Some(Self::Token),
            "ngram" => Some(Self::Ngram),
            "edit" => Some(Self::Edit),
            "lsh" => Some(Self::Lsh),
            "simhash" => Some(Self::Simhash),
            _ => None,
        }
    }

    /// Lowercase wire-form name.
    pub fn name(self) -> &'static str {
        match self {
            Self::Token => "token",
            Self::Ngram => "ngram",
            Self::Edit => "edit",
            Self::Lsh => "lsh",
            Self::Simhash => "simhash",
            #[expect(
                unreachable_patterns,
                reason = "guard for `#[non_exhaustive]` variants added in future slices"
            )]
            _ => "unknown",
        }
    }

    /// Whether `candidate` belongs with `representative` for this
    /// algorithm. This is intentionally deterministic and local; §5.4
    /// excludes neural/embedding clustering.
    pub fn matches(self, candidate: &str, representative: &str) -> bool {
        let candidate = normalize(candidate);
        let representative = normalize(representative);
        if candidate.is_empty() || representative.is_empty() {
            return candidate == representative;
        }
        if candidate == representative {
            return true;
        }
        match self {
            Self::Token => token_jaccard(&candidate, &representative) >= 0.5,
            Self::Ngram => ngram_jaccard(&candidate, &representative) >= 0.45,
            Self::Edit => normalized_edit_similarity(&candidate, &representative) >= 0.8,
            Self::Lsh => token_jaccard(&candidate, &representative) >= 0.5,
            Self::Simhash => simhash_distance(&candidate, &representative) <= 12,
            #[expect(
                unreachable_patterns,
                reason = "guard for `#[non_exhaustive]` variants added in future slices"
            )]
            _ => false,
        }
    }
}

impl Strategy {
    /// Whether this strategy requires buffering all input before
    /// emitting clusters (§12 memory model).
    ///
    /// `Quantiles` and `Natural` need the full distribution; everything
    /// else can stream.
    pub fn is_buffered(&self) -> bool {
        matches!(
            self,
            Strategy::Quantiles { .. } | Strategy::Natural { .. } | Strategy::Similar { .. }
        )
    }

    /// Lowercase wire-form name of this strategy, matching the serde
    /// tag used in the §7 envelope (`exact`, `prefix`, `top`, `bands`,
    /// `quantiles`, `natural`).
    ///
    /// `Strategy` is `#[non_exhaustive]`; future variants added before
    /// their dispatch arms land here will return `"unknown"` until the
    /// arm is filled in.
    ///
    /// # Examples
    ///
    /// ```
    /// use face_core::Strategy;
    ///
    /// assert_eq!(Strategy::Exact.name(), "exact");
    /// assert_eq!(Strategy::Bands { count: 5 }.name(), "bands");
    /// ```
    pub fn name(&self) -> &'static str {
        match self {
            Strategy::Exact => "exact",
            Strategy::Prefix { .. } => "prefix",
            Strategy::Top { .. } => "top",
            Strategy::Bands { .. } => "bands",
            Strategy::Quantiles { .. } => "quantiles",
            Strategy::Natural { .. } => "natural",
            Strategy::Similar { .. } => "similar",
            // `#[non_exhaustive]` guard for variants added in future
            // slices.
            #[expect(
                unreachable_patterns,
                reason = "guard for `#[non_exhaustive]` variants added in future slices"
            )]
            _ => "unknown",
        }
    }
}

fn normalize(value: &str) -> String {
    value
        .chars()
        .map(|ch| {
            if ch.is_alphanumeric() {
                ch.to_ascii_lowercase()
            } else {
                ' '
            }
        })
        .collect::<String>()
        .split_whitespace()
        .collect::<Vec<_>>()
        .join(" ")
}

fn tokens(value: &str) -> std::collections::BTreeSet<&str> {
    value.split_whitespace().collect()
}

fn token_jaccard(a: &str, b: &str) -> f64 {
    let a = tokens(a);
    let b = tokens(b);
    jaccard(&a, &b)
}

fn ngrams(value: &str) -> std::collections::BTreeSet<String> {
    let chars = value.chars().collect::<Vec<_>>();
    if chars.len() <= 3 {
        return std::iter::once(value.to_string()).collect();
    }
    chars.windows(3).map(|w| w.iter().collect()).collect()
}

fn ngram_jaccard(a: &str, b: &str) -> f64 {
    let a = ngrams(a);
    let b = ngrams(b);
    jaccard(&a, &b)
}

fn jaccard<T: Ord>(a: &std::collections::BTreeSet<T>, b: &std::collections::BTreeSet<T>) -> f64 {
    if a.is_empty() && b.is_empty() {
        return 1.0;
    }
    let intersection = a.intersection(b).count() as f64;
    let union = a.union(b).count() as f64;
    intersection / union
}

fn normalized_edit_similarity(a: &str, b: &str) -> f64 {
    let a_chars = a.chars().collect::<Vec<_>>();
    let b_chars = b.chars().collect::<Vec<_>>();
    let max_len = a_chars.len().max(b_chars.len());
    if max_len == 0 {
        return 1.0;
    }
    let distance = levenshtein(&a_chars, &b_chars);
    1.0 - (distance as f64 / max_len as f64)
}

fn levenshtein(a: &[char], b: &[char]) -> usize {
    let mut prev = (0..=b.len()).collect::<Vec<_>>();
    let mut curr = vec![0usize; b.len() + 1];
    for (i, ca) in a.iter().enumerate() {
        curr[0] = i + 1;
        for (j, cb) in b.iter().enumerate() {
            let cost = usize::from(ca != cb);
            curr[j + 1] = (curr[j] + 1).min(prev[j + 1] + 1).min(prev[j] + cost);
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[b.len()]
}

fn simhash_distance(a: &str, b: &str) -> u32 {
    (simhash(a) ^ simhash(b)).count_ones()
}

fn simhash(value: &str) -> u64 {
    let mut weights = [0i32; 64];
    for token in value.split_whitespace() {
        let hash = stable_hash(token);
        for (bit, weight) in weights.iter_mut().enumerate() {
            if (hash >> bit) & 1 == 1 {
                *weight += 1;
            } else {
                *weight -= 1;
            }
        }
    }
    let mut out = 0u64;
    for (bit, weight) in weights.iter().enumerate() {
        if *weight >= 0 {
            out |= 1u64 << bit;
        }
    }
    out
}

fn stable_hash(value: &str) -> u64 {
    let mut hash = 0xcbf29ce484222325u64;
    for byte in value.bytes() {
        hash ^= u64::from(byte);
        hash = hash.wrapping_mul(0x100000001b3);
    }
    hash
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn exact_serializes_to_strategy_tag_only() {
        let s = serde_json::to_value(Strategy::Exact).unwrap();
        assert_eq!(s, serde_json::json!({ "strategy": "exact" }));
    }

    #[test]
    fn bands_serializes_with_count() {
        let s = serde_json::to_value(Strategy::Bands { count: 5 }).unwrap();
        assert_eq!(s, serde_json::json!({ "strategy": "bands", "count": 5 }));
    }

    #[test]
    fn similar_serializes_with_algorithm() {
        let s = serde_json::to_value(Strategy::Similar {
            algorithm: SimilarAlgorithm::Token,
        })
        .unwrap();
        assert_eq!(
            s,
            serde_json::json!({ "strategy": "similar", "algorithm": "token" })
        );
    }

    #[test]
    fn quantiles_is_buffered() {
        assert!(Strategy::Quantiles { count: 4 }.is_buffered());
        assert!(
            Strategy::Similar {
                algorithm: SimilarAlgorithm::Token
            }
            .is_buffered()
        );
        assert!(!Strategy::Exact.is_buffered());
    }

    #[test]
    fn axis_round_trip_matches_design_example() {
        let axis = Axis {
            field: "data.path.text".into(),
            strategy: Strategy::Exact,
            auto: true,
        };
        let v = serde_json::to_value(&axis).unwrap();
        assert_eq!(
            v,
            serde_json::json!({
                "field": "data.path.text",
                "strategy": "exact",
                "auto": true,
            })
        );
        let back: Axis = serde_json::from_value(v).unwrap();
        assert_eq!(back, axis);
    }

    #[test]
    fn token_similarity_matches_reordered_terms() {
        assert!(SimilarAlgorithm::Token.matches("fix login bug", "login bug fix"));
        assert!(!SimilarAlgorithm::Token.matches("fix login bug", "render chart"));
    }
}