graph_process_manager_core 0.4.0

/*
Copyright 2020 Erwan Mahe (github.com/erwanM974)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/


/*
 * Integration tests for GenericProcessManager.
 *
 * Test graph (node values 0-6, letters for readability):
 *
 *        A(0)
 *       /    \
 *     B(1)  C(2)
 *     / \   / \
 *   D(3) E(4) F(5)
 *          |
 *         G(6)
 *
 * Edges: A→B, A→C, B→D, B→E, C→E, C→F, E→G.
 * D, F, G are terminal.
 * E is reachable from both B and C - the shared node that tests memoization.
 *
 * Queue internals: collect_next_steps returns children left→right; each parent's
 * children are stored in a Vec and dequeued via pop() - i.e. *last child first*.
 * BFS pops from the front of its outer VecDeque; DFS pops from the back.
 * This determines the exact traversal orders asserted below.
 */

use std::collections::HashSet;

use graph_process_manager_core::process::config::AbstractProcessConfiguration;
use graph_process_manager_core::process::event::ExplorationEvent;
use graph_process_manager_core::process::filter::{
    AbstractNodePostFilter, AbstractNodePreFilter, AbstractStepFilter, GenericFiltersManager,
};
use graph_process_manager_core::process::manager::GenericProcessManager;
use graph_process_manager_core::process::persistent_state::AbstractProcessMutablePersistentState;
use graph_process_manager_core::queue::priorities::{AbstractPriorities, GenericProcessPriorities};
use graph_process_manager_core::queue::strategy::QueueSearchStrategy;

// === Domain types ============================================================

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Node(u8);

#[derive(Debug, Clone, PartialEq, Eq)]
struct Step(u8); // target node value

// === Process configuration ===================================================

struct GraphConf;

impl AbstractProcessConfiguration for GraphConf {
    type ContextAndParameterization = ();
    type DomainSpecificNode = Node;
    type DomainSpecificStep = Step;
    type Priorities = FlatPriorities;
    type MutablePersistentState = TrackingState;
    type FiltrationResult = ();

    fn process_new_step(
        _ctx: &(),
        _state: &mut TrackingState,
        _parent: &Node,
        step: &Step,
    ) -> Node {
        Node(step.0)
    }

    fn collect_next_steps(_ctx: &(), _state: &TrackingState, parent: &Node) -> Vec<Step> {
        match parent.0 {
            0 => vec![Step(1), Step(2)], // A → B, C
            1 => vec![Step(3), Step(4)], // B → D, E
            2 => vec![Step(4), Step(5)], // C → E, F
            4 => vec![Step(6)],          // E → G
            _ => vec![],                 // D, F, G are terminal
        }
    }
}

// === Priorities (flat - all steps equal) =====================================

struct FlatPriorities;

impl AbstractPriorities<Step> for FlatPriorities {
    fn get_priority_of_step(&self, _step: &Step) -> i32 {
        0
    }
}

// === Persistent state ========================================================

/// Records the sequence of node values as they are reached, and optionally
/// triggers early termination when a target node is found.
#[derive(Default)]
struct TrackingState {
    visited_sequence: Vec<u8>,
    terminate_on: Option<u8>,
}

impl AbstractProcessMutablePersistentState<GraphConf> for TrackingState {
    fn get_initial_state(_ctx: &(), _initial_node: &Node) -> Self {
        TrackingState::default()
    }

    fn update_on_node_reached(&mut self, _ctx: &(), node: &Node) {
        self.visited_sequence.push(node.0);
    }

    fn update_on_next_steps_collected_reached(&mut self, _ctx: &(), _node: &Node, _steps: &[Step]) {}

    fn update_on_filtered(&mut self, _ctx: &(), _node: &Node, _result: &()) {}

    fn warrants_termination_of_the_process(&self, _ctx: &()) -> bool {
        self.terminate_on
            .map_or(false, |t| self.visited_sequence.contains(&t))
    }
}

// === Helpers =================================================================

fn make_manager(
    strategy: QueueSearchStrategy,
    memoized: bool,
    pre: Vec<Box<dyn AbstractNodePreFilter<GraphConf>>>,
    post: Vec<Box<dyn AbstractNodePostFilter<GraphConf>>>,
    step: Vec<Box<dyn AbstractStepFilter<GraphConf>>>,
) -> GenericProcessManager<GraphConf> {
    GenericProcessManager::new(
        (),
        strategy,
        GenericProcessPriorities::new(FlatPriorities, false),
        GenericFiltersManager::new(pre, post, step),
        memoized,
        Node(0),
    )
}

/// Collect all NewNode values in the order they are emitted.
fn new_node_sequence(manager: GenericProcessManager<GraphConf>) -> Vec<u8> {
    manager
        .filter_map(|ev| match ev {
            ExplorationEvent::NewNode { node, .. } => Some(node.0),
            _ => None,
        })
        .collect()
}

fn collect_events(manager: GenericProcessManager<GraphConf>) -> Vec<ExplorationEvent<GraphConf>> {
    manager.collect()
}

// === Traversal order tests ====================================================

#[test]
fn bfs_node_discovery_order_no_memo() {
    // BFS visits last child first within each parent (inner Vec::pop), and the
    // outer VecDeque front gives breadth-first ordering across parents.
    // Expected: A(0), C(2), B(1), F(5), E(4)[fromC], E(4)[fromB], D(3), G(6)[fromC-E], G(6)[fromB-E]
    let seq = new_node_sequence(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));
    assert_eq!(seq, vec![0, 2, 1, 5, 4, 4, 3, 6, 6]);
}

#[test]
fn dfs_node_discovery_order_no_memo() {
    // DFS: last child first, stack-based → explores the rightmost branch deepest first.
    // Expected: A(0), C(2), F(5), E(4)[fromC], G(6)[fromC-E], B(1), E(4)[fromB], G(6)[fromB-E], D(3)
    let seq = new_node_sequence(make_manager(QueueSearchStrategy::DFS, false, vec![], vec![], vec![]));
    assert_eq!(seq, vec![0, 2, 5, 4, 6, 1, 4, 6, 3]);
}

#[test]
fn hcs_node_discovery_order_no_memo() {
    // HCS: BFS when last reached was terminal, DFS otherwise.
    // Expected: A(0), C(2)[BFS], F(5)[DFS-terminal→BFS next], B(1)[BFS],
    //           E(4)[DFS], G(6)[DFS-terminal→BFS next], E(4)[BFS], G(6)[DFS-terminal→BFS next], D(3)[BFS]
    let seq = new_node_sequence(make_manager(QueueSearchStrategy::HCS, false, vec![], vec![], vec![]));
    assert_eq!(seq, vec![0, 2, 5, 1, 4, 6, 4, 6, 3]);
}

#[test]
fn all_strategies_differ() {
    let bfs = new_node_sequence(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));
    let dfs = new_node_sequence(make_manager(QueueSearchStrategy::DFS, false, vec![], vec![], vec![]));
    let hcs = new_node_sequence(make_manager(QueueSearchStrategy::HCS, false, vec![], vec![], vec![]));
    assert_ne!(bfs, dfs);
    assert_ne!(bfs, hcs);
    assert_ne!(dfs, hcs);
}

// === Memoization tests ========================================================

#[test]
fn memo_reaches_same_set_of_nodes_as_no_memo() {
    let with_memo = new_node_sequence(make_manager(QueueSearchStrategy::BFS, true, vec![], vec![], vec![]));
    let no_memo   = new_node_sequence(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));

    let set_memo: HashSet<u8> = with_memo.into_iter().collect();
    let set_no_memo: HashSet<u8> = no_memo.into_iter().collect();

    assert_eq!(set_memo, set_no_memo);
    assert_eq!(set_memo, HashSet::from([0, 1, 2, 3, 4, 5, 6]));
}

#[test]
fn memo_visits_each_node_exactly_once() {
    for strategy in [QueueSearchStrategy::BFS, QueueSearchStrategy::DFS, QueueSearchStrategy::HCS] {
        let seq = new_node_sequence(make_manager(strategy, true, vec![], vec![], vec![]));
        let unique: HashSet<u8> = seq.iter().copied().collect();
        assert_eq!(seq.len(), unique.len(), "duplicate nodes with {:?}", strategy);
        assert_eq!(unique, HashSet::from([0, 1, 2, 3, 4, 5, 6]));
    }
}

#[test]
fn no_memo_visits_shared_nodes_multiple_times() {
    // E(4) and G(6) are each reachable via two paths; without memo both appear twice.
    let seq = new_node_sequence(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));
    assert_eq!(seq.iter().filter(|&&v| v == 4).count(), 2, "E should appear twice");
    assert_eq!(seq.iter().filter(|&&v| v == 6).count(), 2, "G should appear twice");
}

#[test]
fn memo_step_targets_already_known_node() {
    // With memoization, the second path to E must produce a NewStep pointing to the
    // *same id* that was assigned when E was first discovered.
    let mut id_of_e: Option<u32> = None;
    let mut second_e_target: Option<u32> = None;
    let mut e_count = 0u32;

    let manager = make_manager(QueueSearchStrategy::BFS, true, vec![], vec![], vec![]);
    for ev in manager {
        match ev {
            ExplorationEvent::NewNode { id, node } if node.0 == 4 => {
                e_count += 1;
                if e_count == 1 { id_of_e = Some(id); }
            }
            ExplorationEvent::NewStep { step, target_node_id, .. } if step.0 == 4 => {
                if e_count >= 1 && id_of_e.is_some() && second_e_target.is_none() {
                    // This is the second time we see a step toward E.
                    // It should point to the already-known id.
                    second_e_target = Some(target_node_id);
                }
            }
            _ => {}
        }
    }

    assert_eq!(e_count, 1, "E should be discovered (NewNode) exactly once with memo");
    assert_eq!(
        second_e_target,
        id_of_e,
        "second step to E should target the memoized id"
    );
}

// === Filter tests =============================================================

// Pre-filter: prune node B(1) before collecting its children.
struct PruneNodeB;

impl AbstractNodePreFilter<GraphConf> for PruneNodeB {
    fn apply_pre_filter(&self, _ctx: &(), _state: &TrackingState, node: &Node) -> Option<()> {
        if node.0 == 1 { Some(()) } else { None }
    }
}

#[test]
fn pre_filter_prunes_subtree() {
    let manager = make_manager(
        QueueSearchStrategy::BFS,
        false,
        vec![Box::new(PruneNodeB)],
        vec![],
        vec![],
    );
    let events: Vec<_> = collect_events(manager);

    let nodes: Vec<u8> = events.iter().filter_map(|e| match e {
        ExplorationEvent::NewNode { node, .. } => Some(node.0),
        _ => None,
    }).collect();

    // B is discovered (NewNode emitted) but then filtered - its children D and E are never reached.
    // E is still reachable via C, and G via C→E.
    assert!(nodes.contains(&1), "B should still appear as a NewNode (filter fires after)");
    assert!(!nodes.contains(&3), "D should not be visited (child of pruned B)");

    let filtered_count = events.iter().filter(|e| matches!(e, ExplorationEvent::Filtered { .. })).count();
    assert_eq!(filtered_count, 1, "exactly one Filtered event for B");

    // E and G are still reachable via C.
    assert!(nodes.contains(&4), "E reachable via C");
    assert!(nodes.contains(&6), "G reachable via C→E");
}

// Post-filter: prune any node whose next-step set includes a step to G(6).
// Only E(4) has G as a child, so E is explored (collect_next_steps runs) but then filtered,
// preventing G from ever being reached.
struct PruneIfChildIsG;

impl AbstractNodePostFilter<GraphConf> for PruneIfChildIsG {
    fn apply_post_filter(
        &self,
        _ctx: &(),
        _state: &TrackingState,
        _node: &Node,
        steps: &[Step],
    ) -> Option<()> {
        if steps.iter().any(|s| s.0 == 6) { Some(()) } else { None }
    }
}

#[test]
fn post_filter_prunes_after_step_collection() {
    let manager = make_manager(
        QueueSearchStrategy::BFS,
        false,
        vec![],
        vec![Box::new(PruneIfChildIsG)],
        vec![],
    );
    let events: Vec<_> = collect_events(manager);

    let nodes: Vec<u8> = events.iter().filter_map(|e| match e {
        ExplorationEvent::NewNode { node, .. } => Some(node.0),
        _ => None,
    }).collect();

    // E is discovered (NewNode) but post-filtered, so G is never reached.
    assert!(nodes.contains(&4), "E is reached and emits NewNode");
    assert!(!nodes.contains(&6), "G is never reached");

    // There are two E nodes without memo (one from C, one from B), both post-filtered.
    let filtered_count = events.iter().filter(|e| matches!(e, ExplorationEvent::Filtered { .. })).count();
    assert_eq!(filtered_count, 2, "both copies of E should be post-filtered");
}

// Step filter: prune any step leading to E(4).
struct PruneStepToE;

impl AbstractStepFilter<GraphConf> for PruneStepToE {
    fn apply_step_filter(
        &self,
        _ctx: &(),
        _state: &TrackingState,
        _parent: &Node,
        step: &Step,
    ) -> Option<()> {
        if step.0 == 4 { Some(()) } else { None }
    }
}

#[test]
fn step_filter_prevents_transition() {
    let manager = make_manager(
        QueueSearchStrategy::BFS,
        false,
        vec![],
        vec![],
        vec![Box::new(PruneStepToE)],
    );
    let events: Vec<_> = collect_events(manager);

    let nodes: Vec<u8> = events.iter().filter_map(|e| match e {
        ExplorationEvent::NewNode { node, .. } => Some(node.0),
        _ => None,
    }).collect();

    // E(4) and G(6) are unreachable once all steps to E are pruned.
    assert!(!nodes.contains(&4), "E should not be reached");
    assert!(!nodes.contains(&6), "G should not be reached");
    // A, B, C, D, F are still reached.
    assert_eq!(
        nodes.iter().copied().collect::<HashSet<u8>>(),
        HashSet::from([0, 1, 2, 3, 5])
    );

    // Two step-filter events: B→E and C→E.
    let filtered_count = events.iter().filter(|e| matches!(e, ExplorationEvent::Filtered { .. })).count();
    assert_eq!(filtered_count, 2);
}

// === Termination test ========================================================

#[test]
fn early_termination_on_target_node() {
    // TrackingState stops the process as soon as G(6) is reached.
    // Under DFS the path A→C→E→G is explored before any other deep path,
    // so exploration halts after G is first seen.
    let mut manager = make_manager(QueueSearchStrategy::DFS, false, vec![], vec![], vec![]);
    manager.global_state.terminate_on = Some(6);

    let nodes: Vec<u8> = manager
        .filter_map(|ev| match ev {
            ExplorationEvent::NewNode { node, .. } => Some(node.0),
            _ => None,
        })
        .collect();

    // DFS reaches: A→C→F→... wait: DFS order is A,C,F,E,G - terminates at G.
    assert!(nodes.contains(&6), "G should be reached before termination");
    // D, B are deeper/later in DFS and should not be reached.
    assert!(!nodes.contains(&3), "D should not be reached after early termination");
    assert!(!nodes.contains(&1), "B should not be reached after early termination");
    // G must be the last node in the sequence (process stops immediately after).
    assert_eq!(*nodes.last().unwrap(), 6);
}

// === Event structure tests ====================================================

#[test]
fn new_node_always_precedes_its_new_step() {
    // For every NewStep event, a NewNode for the target must have been emitted earlier
    // (unless memoization caused a back-edge, in which case the target was seen even earlier).
    let events = collect_events(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));
    let mut known_ids: HashSet<u32> = HashSet::new();
    for ev in &events {
        match ev {
            ExplorationEvent::NewNode { id, .. } => { known_ids.insert(*id); }
            ExplorationEvent::NewStep { target_node_id, .. } => {
                assert!(
                    known_ids.contains(target_node_id),
                    "NewStep target {} seen before its NewNode",
                    target_node_id
                );
            }
            _ => {}
        }
    }
}

#[test]
fn all_children_processed_fires_after_last_child_step() {
    // AllChildrenProcessed(p) must come after all NewStep events that have origin p.
    let events = collect_events(make_manager(QueueSearchStrategy::BFS, false, vec![], vec![], vec![]));
    let mut last_step_pos: std::collections::HashMap<u32, usize> = std::collections::HashMap::new();
    let mut all_children_pos: std::collections::HashMap<u32, usize> = std::collections::HashMap::new();
    for (i, ev) in events.iter().enumerate() {
        match ev {
            ExplorationEvent::NewStep { origin_node_id, .. } |
            ExplorationEvent::Filtered { parent_node_id: origin_node_id, .. } => {
                last_step_pos.insert(*origin_node_id, i);
            }
            ExplorationEvent::AllChildrenProcessed { parent_node_id } => {
                all_children_pos.insert(*parent_node_id, i);
            }
            _ => {}
        }
    }
    for (parent_id, acp_pos) in &all_children_pos {
        if let Some(last_pos) = last_step_pos.get(parent_id) {
            assert!(
                acp_pos > last_pos,
                "AllChildrenProcessed({}) at {} must come after last step at {}",
                parent_id, acp_pos, last_pos
            );
        }
    }
}

#[test]
fn terminal_nodes_emit_node_without_children() {
    let events = collect_events(make_manager(QueueSearchStrategy::BFS, true, vec![], vec![], vec![]));
    let terminal_node_values: HashSet<u8> = events.iter().filter_map(|e| match e {
        ExplorationEvent::NodeWithoutChildren { node_id } => {
            // find the value of this node from a prior NewNode event
            events.iter().find_map(|e2| match e2 {
                ExplorationEvent::NewNode { id, node } if id == node_id => Some(node.0),
                _ => None,
            })
        }
        _ => None,
    }).collect();

    assert_eq!(terminal_node_values, HashSet::from([3, 5, 6]), "D, F, G are the terminal nodes");
}

#[test]
fn total_event_count_matches_expected_with_memo() {
    // With memoization and BFS: 7 NewNode + 7 NewStep (6 tree edges + 1 back-edge to memoized E)
    // + 4 AllChildrenProcessed (A,B,C,E) + 3 NodeWithoutChildren (D,F,G) = 21 events.
    let events = collect_events(make_manager(QueueSearchStrategy::BFS, true, vec![], vec![], vec![]));

    let new_nodes  = events.iter().filter(|e| matches!(e, ExplorationEvent::NewNode { .. })).count();
    let new_steps  = events.iter().filter(|e| matches!(e, ExplorationEvent::NewStep { .. })).count();
    let no_child   = events.iter().filter(|e| matches!(e, ExplorationEvent::NodeWithoutChildren { .. })).count();
    let all_done   = events.iter().filter(|e| matches!(e, ExplorationEvent::AllChildrenProcessed { .. })).count();
    let filtered   = events.iter().filter(|e| matches!(e, ExplorationEvent::Filtered { .. })).count();

    assert_eq!(new_nodes, 7);
    assert_eq!(new_steps, 7);
    assert_eq!(no_child,  3);
    assert_eq!(all_done,  4);
    assert_eq!(filtered,  0);
}