capability_grower_configuration_from_skeleton/

infer_level_skipping.rs

// ---------------- [ File: capability-grower-configuration-from-skeleton/src/infer_level_skipping.rs ]
crate::ix!();

pub trait TryInferLevelSkippingConfiguration {
    fn try_infer_level_skipping_configuration(&self) -> Option<LevelSkippingConfiguration>;
}

impl TryInferLevelSkippingConfiguration for Skeleton {
    fn try_infer_level_skipping_configuration(&self) -> Option<LevelSkippingConfiguration> {
        // Gather per‐level skipping stats
        let skipping_map = self.measure_tree_level_skipping();
        if skipping_map.is_empty() {
            return None;
        }

        // Determine highest level seen
        let max_level = skipping_map.keys().copied().max().unwrap_or(0);

        // Build the probability vector: leaf_count/total_nodes per level, raised to 1.2
        let mut skip_probs = Vec::with_capacity((max_level as usize) + 1);
        for lvl in 0..=max_level {
            let p = if let Some(stats) = skipping_map.get(&lvl) {
                let nc = *stats.total_node_count();
                let lc = *stats.total_leaf_count();
                if nc == 0 {
                    0.0
                } else {
                    (lc as f32 / nc as f32).powf(1.2)
                }
            } else {
                0.0
            };
            skip_probs.push(p);
        }

        // If we’ve saturated into the u8::MAX bucket, force that last slot to 1.0
        // so deep chains always end up with a full‐skip level.
        if max_level == u8::MAX {
            // safe because skip_probs.len() == 256 in this case
            if let Some(last) = skip_probs.last_mut() {
                *last = 1.0;
            }
        }

        // Build the configuration
        LevelSkippingConfigurationBuilder::default()
            .leaf_probability_per_level(skip_probs)
            .build()
            .ok()
    }
}

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

    /// 1) Empty skeleton → None
    #[traced_test]
    fn empty_skeleton_returns_none() {
        let skel = SkeletonBuilder::default().build().unwrap();
        assert!(skel.try_infer_level_skipping_configuration().is_none());
    }

    /// 2) Single leaf → level 0: skip=1.0
    #[traced_test]
    fn single_leaf_returns_full_probability() {
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .name("root")
            .original_key("root")
            .build(NodeKind::LeafHolder)
            .unwrap();
        let skel = SkeletonBuilder::default()
            .nodes(vec![n0])
            .root_id(Some(0_u16))
            .build()
            .unwrap();
        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let p = cfg.leaf_probability_per_level();
        assert_eq!(p.len(), 1);
        assert!((p[0] - 1.0).abs() < f32::EPSILON);
    }

    /// 3) Linear chain 0→1→2 → skip = [0.0, 0.0, 1.0]
    #[traced_test]
    fn linear_chain_three_levels() {

        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .name("n0")
            .original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .child_ids(vec![2_u16])
            .name("n1")
            .original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n2 = SkeletonNodeBuilder::default()
            .id(2_u16)
            .name("n2")
            .original_key("n2")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2])
            .root_id(Some(0_u16))
            .build()
            .unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs.len(), 3);
        assert!((probs[0] - 0.0).abs() < 1e-6);
        assert!((probs[1] - 0.0).abs() < 1e-6);
        assert!((probs[2] - 1.0).abs() < 1e-6);
    }

    /// 4) Root with two leaves → skip = [0.0, 1.0]
    #[traced_test]
    fn branch_with_two_leaves() {

        let root = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16,2_u16])
            .name("root")
            .original_key("root")
            .build(NodeKind::Dispatch)
            .unwrap();

        let c1   = SkeletonNodeBuilder::default()
            .id(1_u16)
            .name("c1")
            .original_key("c1")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let c2   = SkeletonNodeBuilder::default()
            .id(2_u16)
            .name("c2")
            .original_key("c2")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![root,c1,c2])
            .root_id(Some(0_u16)).build().unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs, &[0.0, 1.0]);
    }

    /// 5) No structural leaf (last child invalid) → all zeros
    #[traced_test]
    fn chain_with_no_structural_leaf() {
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .name("n0")
            .original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .child_ids(vec![2_u16])
            .name("n1")
            .original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n2 = SkeletonNodeBuilder::default()
            .id(2_u16)
            .child_ids(vec![99_u16])
            .name("n2")
            .original_key("n2")
            .build(NodeKind::Dispatch)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2])
            .root_id(Some(0_u16)).build().unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs.len(), 3);
        assert!(probs.iter().all(|&p| (p - 0.0).abs() < 1e-6));
    }

    /// 6) Disconnected orphan → ignored, so behave like simple branch
    #[traced_test]
    fn disconnected_leaf_ignored() {
        let root = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .name("root")
            .original_key("root")
            .build(NodeKind::Dispatch)
            .unwrap();

        let leaf = SkeletonNodeBuilder::default()
            .id(1_u16)
            .name("leaf")
            .original_key("leaf")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let orphan = SkeletonNodeBuilder::default()
            .id(2_u16)
            .name("orphan")
            .original_key("orphan")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![root,leaf,orphan])
            .root_id(Some(0_u16))
            .build()
            .unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs, &[0.0, 1.0]);
    }

    /// 7) Fractional skip: level 1 has 3 nodes of which 2 are leaves → (2/3)^1.2
    #[traced_test]
    fn fractional_skip_probability() {

        let root  = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16,2_u16,3_u16])
            .name("root")
            .original_key("root")
            .build(NodeKind::Dispatch)
            .unwrap();

        let leaf1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .name("l1")
            .original_key("l1")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let leaf2 = SkeletonNodeBuilder::default()
            .id(2_u16)
            .name("l2")
            .original_key("l2")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let mid   = SkeletonNodeBuilder::default()
            .id(3_u16)
            .child_ids(vec![4_u16])
            .name("m")
            .original_key("m")
            .build(NodeKind::Dispatch)
            .unwrap();

        let leaf3 = SkeletonNodeBuilder::default()
            .id(4_u16)
            .name("l3")
            .original_key("l3")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel  = SkeletonBuilder::default()
            .nodes(vec![root,leaf1,leaf2,mid,leaf3])
            .root_id(Some(0_u16))
            .build()
            .unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs.len(), 3);
        assert!((probs[0] - 0.0).abs() < 1e-6);
        let expected = (2.0_f32 / 3.0).powf(1.2);
        assert!((probs[1] - expected).abs() < 1e-5);
        assert!((probs[2] - 1.0).abs() < 1e-6);
    }

    // ────────────────────────────────
    // ── NEW EDGE & STRESS TESTS ───────────────────────────────────────────────
    // ──────────────────────────────────────────────────────────────────────────

    /// 8) Cycle in skeleton → no infinite loop, correct skip=[0.0,0.0]
    #[traced_test]
    fn cycle_does_not_loop_and_counts_correctly() {
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .name("n0")
            .original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .child_ids(vec![0_u16])
            .name("n1")
            .original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1])
            .root_id(Some(0_u16)).build().unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs, &[0.0,0.0]);
    }

    /// 9) Very deep chain → saturates levels at 255, skip at last = 1.0
    #[traced_test]
    fn deep_chain_saturates_and_last_is_full() {
        let nodes: Vec<SkeletonNode> = (0_u16..300).map(|i| {
            let mut b = SkeletonNodeBuilder::default()
                .id(i)
                .name(format!("n{}", i))
                .original_key(format!("n{}", i));
            if i < 299 {
                b = b.child_ids(vec![(i + 1)]);
            }

            b
                .build(NodeKind::Dispatch)
                .unwrap()

        }).collect();
        let skel = SkeletonBuilder::default()
            .nodes(nodes)
            .root_id(Some(0_u16)).build().unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs.len(), 256);
        assert!((probs[255] - 1.0).abs() < 1e-6);
    }

    /// 10) Uniform-invalid-children skeleton → only root visited → skip=[0.0]
    #[traced_test]
    fn uniform_invalid_children_skipping() {
        let nodes: Vec<SkeletonNode> = (0_u16..10).map(|i| {
            let children: Vec<u16> = (0_u16..5_u16).map(|c| 100_u16 + c).collect();
            SkeletonNodeBuilder::default()
                .id(i)
                .child_ids(children)
                .name(format!("n{}", i))
                .original_key(format!("n{}", i))
                .build(NodeKind::Dispatch)
                .unwrap()
        }).collect();
        let skel = SkeletonBuilder::default()
            .nodes(nodes)
            .root_id(Some(0_u16)).build().unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs, &[0.0]);
    }

    /// 11) `leaf_count` field is ignored: structural leaf only by `child_ids.is_empty()`
    #[traced_test]
    fn leaf_count_field_does_not_affect_skipping() {

        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .leaf_count(1000_u16)
            .name("n0")
            .original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .leaf_count(0_u16)
            .name("n1")
            .original_key("n1")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1])
            .root_id(Some(0_u16))
            .build()
            .unwrap();

        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert_eq!(probs, &[0.0, 1.0]);
    }

    #[traced_test]
    fn all_zero_stats_returns_some() {
        // Three nodes in a chain, but last node’s child reference (99) is invalid,
        // so no level yields any structural leaves → all probabilities should be 0.0
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16)
            .child_ids(vec![1_u16])
            .name("n0")
            .original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n1 = SkeletonNodeBuilder::default()
            .id(1_u16)
            .child_ids(vec![2_u16])
            .name("n1")
            .original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();

        let n2 = SkeletonNodeBuilder::default()
            .id(2_u16)
            .child_ids(vec![99_u16]) // invalid child ID
            .name("n2")
            .original_key("n2")
            .build(NodeKind::Dispatch)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0, n1, n2])
            .root_id(Some(0_u16))
            .build()
            .unwrap();

        // Bind the configuration so its internal Vec outlives the borrow
        let cfg = skel.try_infer_level_skipping_configuration().unwrap();
        let probs = cfg.leaf_probability_per_level();
        assert!(probs.iter().all(|&p| (p - 0.0).abs() < 1e-6),
        "Expected all skip probabilities to be 0.0 when there are no valid structural leaves");
    }
}