captchaforge 0.2.29

//! Property tests for `frame_graph::FrameGraph`. The graph is the
//! substrate every multi-frame solver walks — invariants here ensure
//! BFS terminates, ancestor chains aren't cyclic, and operations on
//! arbitrary tree shapes never panic.

use captchaforge::frame_graph::{FrameGraph, FrameNode};
use proptest::prelude::*;

fn arb_node(parent: Option<usize>, depth: usize) -> FrameNode {
    FrameNode {
        frame_id: Some(format!("frame-{}", parent.unwrap_or(0))),
        parent,
        url: "https://example.com".into(),
        title: String::new(),
        has_captcha_marker: false,
        depth,
    }
}

fn arb_tree(max_nodes: usize) -> impl Strategy<Value = FrameGraph> {
    (1..=max_nodes).prop_flat_map(|n| {
        // Each node (except root) chooses a random parent index < itself,
        // guaranteeing acyclicity by construction.
        let parents = proptest::collection::vec(0usize..1, n - 1)
            .prop_flat_map(move |_| {
                let strategies: Vec<_> = (1..n).map(|i| 0usize..i).collect();
                strategies
            });
        parents.prop_map(move |parents| {
            let mut nodes = vec![arb_node(None, 0)];
            for (i, p) in parents.into_iter().enumerate() {
                let parent_depth = nodes[p].depth;
                nodes.push(arb_node(Some(p), parent_depth + 1));
                let _ = i;
            }
            FrameGraph { nodes }
        })
    })
}

proptest! {
    /// BFS visits every node exactly once and each node only after
    /// its parent. Failing this means downstream "for-each-frame"
    /// loops can either skip frames or visit children before their
    /// parent context is set up — both common bug shapes.
    #[test]
    fn bfs_visits_each_node_once_in_parent_first_order(
        graph in arb_tree(50),
    ) {
        let order = graph.bfs();
        prop_assert_eq!(order.len(), graph.nodes.len(),
            "BFS must visit every node");

        let mut visited: Vec<bool> = vec![false; graph.nodes.len()];
        for &idx in &order {
            prop_assert!(!visited[idx], "node {} visited twice", idx);
            visited[idx] = true;
            if let Some(parent) = graph.nodes[idx].parent {
                prop_assert!(visited[parent],
                    "node {} visited before its parent {}", idx, parent);
            }
        }
    }

    /// `ancestors_inclusive` always terminates (no cycles), starts
    /// at the requested node, and ends at the root (index 0).
    #[test]
    fn ancestors_chain_terminates_at_root(
        graph in arb_tree(50),
        node_idx in 0usize..50,
    ) {
        let n = graph.nodes.len();
        prop_assume!(node_idx < n);

        let chain = graph.ancestors_inclusive(node_idx);
        prop_assert!(!chain.is_empty());
        prop_assert_eq!(chain[0], node_idx, "chain starts at node");
        prop_assert_eq!(*chain.last().unwrap(), 0,
            "chain terminates at root (index 0)");
        // No duplicates — proves acyclicity.
        let unique: std::collections::HashSet<_> = chain.iter().copied().collect();
        prop_assert_eq!(unique.len(), chain.len(),
            "ancestor chain has duplicates → cycle");
    }

    /// `children` of node N never includes N itself, never includes
    /// indices outside the graph, and always reports nodes whose
    /// `parent == Some(N)`.
    #[test]
    fn children_are_well_formed(
        graph in arb_tree(40),
        parent_idx in 0usize..40,
    ) {
        let n = graph.nodes.len();
        prop_assume!(parent_idx < n);

        let kids = graph.children(parent_idx);
        for k in &kids {
            prop_assert!(*k < n);
            prop_assert_ne!(*k, parent_idx);
            prop_assert_eq!(graph.nodes[*k].parent, Some(parent_idx));
        }
    }

    /// `frames_by_host` total node count equals real frame count
    /// (synthetic root excluded). No frame is double-counted.
    #[test]
    fn frames_by_host_partitions_real_frames(graph in arb_tree(40)) {
        let by_host = graph.frames_by_host();
        let counted: usize = by_host.values().map(|v| v.len()).sum();
        // Synthetic root has url "(root)" which the frames_by_host
        // implementation may or may not bucket. The invariant we want
        // is: `counted` <= total nodes and never panics.
        prop_assert!(counted <= graph.nodes.len());
        // No node appears in two host buckets.
        let mut seen = std::collections::HashSet::new();
        for indices in by_host.values() {
            for &i in indices {
                prop_assert!(seen.insert(i),
                    "node {} appears in two host buckets", i);
            }
        }
    }

    /// `deepest_captcha` returns either None (no captcha markers)
    /// or a node whose `has_captcha_marker == true`.
    #[test]
    fn deepest_captcha_returns_marker_node_or_none(graph in arb_tree(30)) {
        if let Some(idx) = graph.deepest_captcha() {
            prop_assert!(idx < graph.nodes.len());
            prop_assert!(graph.nodes[idx].has_captcha_marker,
                "deepest_captcha returned non-marker node");
        } else {
            prop_assert!(!graph.any_captcha_marker(),
                "deepest_captcha returned None despite a marker existing");
        }
    }
}

#[test]
fn empty_graph_bfs_is_empty() {
    let g = FrameGraph { nodes: Vec::new() };
    assert!(g.bfs().is_empty());
}

#[test]
fn single_node_graph_bfs_returns_root() {
    let g = FrameGraph {
        nodes: vec![arb_node(None, 0)],
    };
    assert_eq!(g.bfs(), vec![0]);
}