face_core/

cluster_tree.rs

//! Execution coordinator: walks an [`AxisPlan`] and dispatches to the
//! per-strategy clusterers, recursing on `within` for two-axis (and
//! deeper) nesting (§5.5).
//!
//! Dispatch covers the categorical strategies [`Strategy::Exact`],
//! [`Strategy::Prefix`], [`Strategy::Top`], the numeric strategies
//! [`Strategy::Bands`], [`Strategy::Quantiles`], [`Strategy::Natural`],
//! and explicit algorithmic string clustering [`Strategy::Similar`].
//! The catchall [`FaceError::Unsupported`] arm remains as a
//! `#[non_exhaustive]` safety net for variants added later before their
//! dispatch arms land.
//!
//! # Memory model
//!
//! `build_tree` materializes the full record vector and clusters
//! synchronously. Streaming-eligible strategies (Exact, Prefix, Top,
//! Bands-with-fixed-thresholds per §12) could be lifted to a streaming
//! API later; the current API stays simple and buffered.

use crate::{Axis, Cluster, ClusterId, ClusterIdSegment, Diagnostics, FaceError, Record, Strategy};

/// One node in the user's grouping plan: an axis to cluster on, plus
/// a (possibly empty) list of sub-plans describing how to further
/// cluster the records that fall into each top-level cluster.
///
/// `--by FIELD,FIELD,...` builds a degenerate chain (each axis is the
/// only child of its parent). `--within` adds explicit children. The
/// runtime walks `within` recursively per cluster.
///
/// `AxisPlan` is `#[non_exhaustive]` — construct values via
/// [`AxisPlan::leaf`], [`AxisPlan::with`], or [`AxisPlan::with_many`].
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct AxisPlan {
    /// Axis to cluster on at this level.
    pub axis: Axis,
    /// Sub-plans applied to each cluster's record subset. Empty for
    /// leaf levels.
    pub within: Vec<AxisPlan>,
}

impl AxisPlan {
    /// A leaf plan with no sub-axes.
    ///
    /// # Examples
    ///
    /// ```
    /// use face_core::{Axis, AxisPlan};
    ///
    /// // `Axis` is `#[non_exhaustive]`; build it by deserializing the
    /// // wire form (the same shape `result.axes[]` carries in §7).
    /// let axis: Axis = serde_json::from_value(serde_json::json!({
    ///     "field": "kind",
    ///     "strategy": "exact",
    ///     "auto": false,
    /// })).unwrap();
    /// let plan = AxisPlan::leaf(axis);
    /// assert!(plan.within.is_empty());
    /// ```
    pub fn leaf(axis: Axis) -> Self {
        Self {
            axis,
            within: Vec::new(),
        }
    }

    /// A plan with one sub-axis.
    pub fn with(axis: Axis, within: AxisPlan) -> Self {
        Self {
            axis,
            within: vec![within],
        }
    }

    /// A plan with arbitrary children.
    pub fn with_many(axis: Axis, within: Vec<AxisPlan>) -> Self {
        Self { axis, within }
    }
}

/// Cluster `items` according to `plan`, dispatching per-axis to the
/// appropriate strategy and recursing on `within`.
///
/// All §5.2, §5.3, and explicit §5.4 strategies are implemented:
/// [`Strategy::Exact`], [`Strategy::Prefix`], [`Strategy::Top`],
/// [`Strategy::Bands`], [`Strategy::Quantiles`],
/// [`Strategy::Natural`], [`Strategy::Similar`]. Future variants added to the
/// `#[non_exhaustive]` enum surface as [`FaceError::Unsupported`] until
/// their dispatch arms land.
///
/// # Errors
///
/// Returns [`FaceError::Unsupported`] only when the plan references a
/// `Strategy` variant added after this build (the `#[non_exhaustive]`
/// catchall).
///
/// # Examples
///
/// ```
/// use face_core::{Axis, AxisPlan, NullDiagnostics, Record, build_tree};
/// use serde_json::json;
///
/// let axis: Axis = serde_json::from_value(json!({
///     "field": "kind",
///     "strategy": "exact",
///     "auto": false,
/// })).unwrap();
/// let plan = AxisPlan::leaf(axis);
///
/// let items = vec![json!({"kind": "a"}), json!({"kind": "b"}), json!({"kind": "a"})];
/// let records = Record::from_items(items, None);
///
/// let mut diag = NullDiagnostics;
/// let clusters = build_tree(&plan, records, &mut diag).unwrap();
///
/// assert_eq!(clusters.len(), 2);
/// // Sorted by count desc, label asc → "a" (2) before "b" (1).
/// assert_eq!(clusters[0].label, "a");
/// assert_eq!(clusters[0].total, 2);
/// assert_eq!(clusters[1].label, "b");
/// assert_eq!(clusters[1].total, 1);
/// ```
pub fn build_tree<D: Diagnostics + ?Sized>(
    plan: &AxisPlan,
    items: Vec<Record>,
    diag: &mut D,
) -> Result<Vec<Cluster>, FaceError> {
    build_tree_impl(plan, items, &ClusterId::new(Vec::new()), diag)
}

/// Internal recursion entry point. Crate-visible so `exact::cluster`
/// can recurse into `plan.within` with the cluster's id as the new
/// parent.
pub(crate) fn build_tree_impl<D: Diagnostics + ?Sized>(
    plan: &AxisPlan,
    items: Vec<Record>,
    parent: &ClusterId,
    diag: &mut D,
) -> Result<Vec<Cluster>, FaceError> {
    match &plan.axis.strategy {
        Strategy::Exact => exact::cluster(plan, items, parent, diag),
        Strategy::Prefix { .. } => prefix::cluster(plan, items, parent, diag),
        Strategy::Top { .. } => top::cluster(plan, items, parent, diag),
        Strategy::Bands { .. } => bands::cluster(plan, items, parent, diag),
        Strategy::Quantiles { .. } => quantiles::cluster(plan, items, parent, diag),
        Strategy::Natural { .. } => natural::cluster(plan, items, parent, diag),
        Strategy::Similar { .. } => similar::cluster(plan, items, parent, diag),
        // Catchall for future `#[non_exhaustive]` variants added
        // before their dispatch arm lands. Today every named variant
        // above has an implementation, so the compiler sees this as
        // unreachable from inside the crate; the arm exists so adding
        // a new `Strategy` variant in a follow-up slice cannot crash
        // the build before the new arm lands.
        #[expect(
            unreachable_patterns,
            reason = "guard for `#[non_exhaustive]` variants added in future slices"
        )]
        other => Err(FaceError::Unsupported {
            feature: format!("strategy `{}` unsupported by this build", other.name()),
        }),
    }
}

/// Compose a child [`ClusterId`] by extending a parent with one new
/// `axis:value` segment.
pub(crate) fn extend_id(parent: &ClusterId, axis: &str, value: &str) -> ClusterId {
    let mut segs = parent.segments().to_vec();
    segs.push(ClusterIdSegment {
        axis: axis.to_string(),
        value: value.to_string(),
    });
    ClusterId::new(segs)
}

mod bands;
mod exact;
mod natural;
mod prefix;
mod quantiles;
mod similar;
mod top;
mod util;

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

    use crate::{NullDiagnostics, VecDiagnostics};

    fn axis(field: &str, strategy: Strategy) -> Axis {
        Axis {
            field: field.into(),
            strategy,
            auto: false,
        }
    }

    fn records(items: Vec<serde_json::Value>) -> Vec<Record> {
        Record::from_items(items, None)
    }

    #[test]
    fn exact_single_axis_groups_by_value() {
        let plan = AxisPlan::leaf(axis("kind", Strategy::Exact));
        let items = vec![
            json!({"kind": "alpha"}),
            json!({"kind": "beta"}),
            json!({"kind": "alpha"}),
            json!({"kind": "alpha"}),
            json!({"kind": "beta"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = build_tree(&plan, records(items), &mut diag).unwrap();
        assert_eq!(clusters.len(), 2);
        // count desc, label asc.
        assert_eq!(clusters[0].label, "alpha");
        assert_eq!(clusters[0].total, 3);
        assert_eq!(clusters[1].label, "beta");
        assert_eq!(clusters[1].total, 2);
        // Each leaf has empty children.
        assert!(clusters[0].clusters.is_empty());
        assert!(clusters[1].clusters.is_empty());
    }

    #[test]
    fn exact_two_axis_via_within() {
        let plan = AxisPlan::with(
            axis("repo", Strategy::Exact),
            AxisPlan::leaf(axis("kind", Strategy::Exact)),
        );
        let items = vec![
            json!({"repo": "r1", "kind": "a"}),
            json!({"repo": "r1", "kind": "a"}),
            json!({"repo": "r1", "kind": "b"}),
            json!({"repo": "r2", "kind": "a"}),
        ];
        let mut diag = VecDiagnostics::default();
        let clusters = build_tree(&plan, records(items), &mut diag).unwrap();
        assert_eq!(clusters.len(), 2);

        // r1 has 3, r2 has 1. r1 comes first (count desc).
        assert_eq!(clusters[0].label, "r1");
        assert_eq!(clusters[0].total, 3);
        assert_eq!(clusters[0].clusters.len(), 2);
        // Inside r1: a (2) then b (1).
        assert_eq!(clusters[0].clusters[0].label, "a");
        assert_eq!(clusters[0].clusters[0].total, 2);
        assert_eq!(clusters[0].clusters[1].label, "b");
        assert_eq!(clusters[0].clusters[1].total, 1);

        // r2 has just one child.
        assert_eq!(clusters[1].label, "r2");
        assert_eq!(clusters[1].total, 1);
        assert_eq!(clusters[1].clusters.len(), 1);
        assert_eq!(clusters[1].clusters[0].label, "a");

        // Child id chains parent.
        let child_id = &clusters[0].clusters[0].id;
        assert_eq!(child_id.depth(), 2);
        assert_eq!(child_id.segments()[0].axis, "repo");
        assert_eq!(child_id.segments()[0].value, "r1");
        assert_eq!(child_id.segments()[1].axis, "kind");
        assert_eq!(child_id.segments()[1].value, "a");
    }

    #[test]
    fn bands_dispatches_to_numeric_clusterer() {
        // After slice 7, all six strategies dispatch successfully.
        // This test just confirms the dispatch wiring; the per-strategy
        // semantics live in the strategy modules' own test sections.
        let plan = AxisPlan::leaf(axis("score", Strategy::Bands { count: 5 }));
        let items = vec![json!({"score": 0.9})];
        let mut diag = NullDiagnostics;
        let clusters = build_tree(&plan, records(items), &mut diag).unwrap();
        // Single record → single cluster spanning [0.9, 0.9].
        assert_eq!(clusters.len(), 1);
        assert_eq!(clusters[0].total, 1);
    }

    #[test]
    fn exact_within_bands_recurses_into_numeric_axis() {
        // Top-level Exact, inner Bands. After slice 7 this composes
        // cleanly rather than tripping on recursion.
        let plan = AxisPlan::with(
            axis("kind", Strategy::Exact),
            AxisPlan::leaf(axis("score", Strategy::Bands { count: 5 })),
        );
        let items = vec![json!({"kind": "a", "score": 0.9})];
        let mut diag = NullDiagnostics;
        let clusters = build_tree(&plan, records(items), &mut diag).unwrap();
        assert_eq!(clusters.len(), 1);
        assert_eq!(clusters[0].label, "a");
        // Inner Bands cluster on the single-record `a` group.
        assert_eq!(clusters[0].clusters.len(), 1);
        assert_eq!(clusters[0].clusters[0].total, 1);
    }
}