nereid 0.9.0

// SPDX-FileCopyrightText: 2026 Bruno Meilick
// SPDX-License-Identifier: LicenseRef-Nereid-FreeUse-NoCopy-NoDerivatives
//
// All rights reserved.
//
// This file is part of Nereid and is proprietary software.
// Unauthorized copying, modification, or distribution is prohibited.

//! Session-wide route finding over diagram structure and cross-diagram xrefs.
//!
//! Builds an undirected multigraph of `ObjectRef` nodes (flow/seq/class/er/gantt structure
//! plus session xrefs) for BFS shortest path and bounded multi-route search. Prefer
//! [`SessionRouteAdjacency::derive`] once when answering many queries against the same session.

use std::cmp::{Ordering, Reverse};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};

use crate::model::{CategoryPath, DiagramAst, DiagramId, ObjectId, ObjectRef, Session};

/// Precomputed adjacency over session diagrams and xrefs for route queries.
#[derive(Clone, Debug)]
pub struct SessionRouteAdjacency {
    adjacency: BTreeMap<ObjectRef, BTreeSet<ObjectRef>>,
}

impl SessionRouteAdjacency {
    /// Snapshot structural + xref neighbors from the current in-memory session.
    pub fn derive(session: &Session) -> Self {
        Self { adjacency: derive_adjacency(session) }
    }
}

fn flow_node_category() -> CategoryPath {
    CategoryPath::new(vec!["flow".to_owned(), "node".to_owned()]).expect("static category")
}

fn flow_edge_category() -> CategoryPath {
    CategoryPath::new(vec!["flow".to_owned(), "edge".to_owned()]).expect("static category")
}

fn seq_message_category() -> CategoryPath {
    CategoryPath::new(vec!["seq".to_owned(), "message".to_owned()]).expect("static category")
}

fn seq_participant_category() -> CategoryPath {
    CategoryPath::new(vec!["seq".to_owned(), "participant".to_owned()]).expect("static category")
}

fn seq_block_category() -> CategoryPath {
    CategoryPath::new(vec!["seq".to_owned(), "block".to_owned()]).expect("static category")
}

fn seq_section_category() -> CategoryPath {
    CategoryPath::new(vec!["seq".to_owned(), "section".to_owned()]).expect("static category")
}

fn flow_node_ref(diagram_id: &DiagramId, node_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), flow_node_category(), node_id.clone())
}

fn flow_edge_ref(diagram_id: &DiagramId, edge_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), flow_edge_category(), edge_id.clone())
}

fn cat(segments: &[&str]) -> CategoryPath {
    CategoryPath::new(segments.iter().map(|s| (*s).to_owned()).collect()).expect("static category")
}

fn class_node_ref(diagram_id: &DiagramId, class_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["class", "class"]), class_id.clone())
}

fn class_relation_ref(diagram_id: &DiagramId, rel_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["class", "relation"]), rel_id.clone())
}

fn er_entity_ref(diagram_id: &DiagramId, entity_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["er", "entity"]), entity_id.clone())
}

fn er_relationship_ref(diagram_id: &DiagramId, rel_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["er", "relationship"]), rel_id.clone())
}

fn gantt_task_ref(diagram_id: &DiagramId, task_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["gantt", "task"]), task_id.clone())
}

fn gantt_section_ref(diagram_id: &DiagramId, section_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["gantt", "section"]), section_id.clone())
}

fn gantt_lane_ref(diagram_id: &DiagramId, lane_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), cat(&["gantt", "lane"]), lane_id.clone())
}

/// Bidirectional node↔edge connectivity matching flowchart routes.
fn wire_node_edge_pair(
    adjacency: &mut BTreeMap<ObjectRef, BTreeSet<ObjectRef>>,
    from: ObjectRef,
    to: ObjectRef,
    edge_ref: ObjectRef,
) {
    insert_node(adjacency, edge_ref.clone());
    insert_node(adjacency, from.clone());
    insert_node(adjacency, to.clone());
    insert_edge(adjacency, from.clone(), to.clone());
    insert_edge(adjacency, from.clone(), edge_ref.clone());
    insert_edge(adjacency, to.clone(), edge_ref.clone());
    insert_edge(adjacency, edge_ref.clone(), from);
    insert_edge(adjacency, edge_ref, to);
}

fn seq_message_ref(diagram_id: &DiagramId, message_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), seq_message_category(), message_id.clone())
}

fn seq_participant_ref(diagram_id: &DiagramId, participant_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), seq_participant_category(), participant_id.clone())
}

fn seq_block_ref(diagram_id: &DiagramId, block_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), seq_block_category(), block_id.clone())
}

fn seq_section_ref(diagram_id: &DiagramId, section_id: &ObjectId) -> ObjectRef {
    ObjectRef::new(diagram_id.clone(), seq_section_category(), section_id.clone())
}

fn insert_node(adjacency: &mut BTreeMap<ObjectRef, BTreeSet<ObjectRef>>, node: ObjectRef) {
    adjacency.entry(node).or_default();
}

fn insert_edge(
    adjacency: &mut BTreeMap<ObjectRef, BTreeSet<ObjectRef>>,
    from: ObjectRef,
    to: ObjectRef,
) {
    adjacency.entry(from).or_default().insert(to);
}

fn derive_adjacency(session: &Session) -> BTreeMap<ObjectRef, BTreeSet<ObjectRef>> {
    let mut adjacency: BTreeMap<ObjectRef, BTreeSet<ObjectRef>> = BTreeMap::new();

    for diagram in session.diagrams().values() {
        let diagram_id = diagram.diagram_id();
        match diagram.ast() {
            DiagramAst::Flowchart(ast) => {
                for node_id in ast.nodes().keys() {
                    insert_node(&mut adjacency, flow_node_ref(diagram_id, node_id));
                }
                for (edge_id, edge) in ast.edges().iter() {
                    let edge_ref = flow_edge_ref(diagram_id, edge_id);
                    insert_node(&mut adjacency, edge_ref.clone());

                    let from = flow_node_ref(diagram_id, edge.from_node_id());
                    let to = flow_node_ref(diagram_id, edge.to_node_id());

                    insert_node(&mut adjacency, from.clone());
                    insert_node(&mut adjacency, to.clone());

                    insert_edge(&mut adjacency, from.clone(), to.clone());

                    insert_edge(&mut adjacency, from.clone(), edge_ref.clone());
                    insert_edge(&mut adjacency, to.clone(), edge_ref.clone());
                    insert_edge(&mut adjacency, edge_ref.clone(), from);
                    insert_edge(&mut adjacency, edge_ref, to);
                }
            }
            DiagramAst::Class(ast) => {
                for class_id in ast.classes().keys() {
                    insert_node(&mut adjacency, class_node_ref(diagram_id, class_id));
                }
                for (rel_id, rel) in ast.relations() {
                    wire_node_edge_pair(
                        &mut adjacency,
                        class_node_ref(diagram_id, rel.from_class_id()),
                        class_node_ref(diagram_id, rel.to_class_id()),
                        class_relation_ref(diagram_id, rel_id),
                    );
                }
            }
            DiagramAst::Er(ast) => {
                for id in ast.entities().keys() {
                    insert_node(&mut adjacency, er_entity_ref(diagram_id, id));
                }
                for (rel_id, rel) in ast.relationships() {
                    wire_node_edge_pair(
                        &mut adjacency,
                        er_entity_ref(diagram_id, rel.from_entity_id()),
                        er_entity_ref(diagram_id, rel.to_entity_id()),
                        er_relationship_ref(diagram_id, rel_id),
                    );
                }
            }
            DiagramAst::Gantt(ast) => {
                for id in ast.tasks().keys() {
                    insert_node(&mut adjacency, gantt_task_ref(diagram_id, id));
                }
                for section in ast.sections() {
                    let section_ref = gantt_section_ref(diagram_id, section.section_id());
                    insert_node(&mut adjacency, section_ref.clone());
                    for task_id in section.task_ids() {
                        if ast.tasks().contains_key(task_id) {
                            let task_ref = gantt_task_ref(diagram_id, task_id);
                            insert_edge(&mut adjacency, section_ref.clone(), task_ref.clone());
                            insert_edge(&mut adjacency, task_ref, section_ref.clone());
                        }
                    }
                }
                // Wire `after` dependency chains as undirected route hops.
                for (id, task) in ast.tasks() {
                    if let crate::model::GanttTaskStart::After(dep) = task.start() {
                        if ast.tasks().contains_key(dep) {
                            let from = gantt_task_ref(diagram_id, id);
                            let to = gantt_task_ref(diagram_id, dep);
                            insert_edge(&mut adjacency, from.clone(), to.clone());
                            insert_edge(&mut adjacency, to, from);
                        }
                    }
                }

                // Render-visible time lanes are first-class refs. Connect each lane to tasks whose
                // resolved windows overlap that lane's tick interval.
                let (windows, _) = ast.resolved_task_windows();
                let max_end = windows.values().map(|window| window.end).max().unwrap_or(1).max(1);
                let lane_days = ast
                    .lanes_with_days()
                    .into_iter()
                    .map(|(lane_id, day, _)| (lane_id, day))
                    .collect::<Vec<_>>();
                for (index, (lane_id, day)) in lane_days.iter().enumerate() {
                    let lane_ref = gantt_lane_ref(diagram_id, lane_id);
                    insert_node(&mut adjacency, lane_ref.clone());
                    let next_day = lane_days
                        .get(index + 1)
                        .map(|(_, next)| *next)
                        .unwrap_or(max_end)
                        .max(day.saturating_add(1));
                    for (task_id, window) in &windows {
                        if window.start < next_day && window.end > *day {
                            let task_ref = gantt_task_ref(diagram_id, task_id);
                            insert_edge(&mut adjacency, lane_ref.clone(), task_ref.clone());
                            insert_edge(&mut adjacency, task_ref, lane_ref.clone());
                        }
                    }
                }
            }
            DiagramAst::Sequence(ast) => {
                for participant_id in ast.participants().keys() {
                    insert_node(&mut adjacency, seq_participant_ref(diagram_id, participant_id));
                }

                let messages = ast.messages_in_order();

                let message_refs = messages
                    .iter()
                    .map(|msg| seq_message_ref(diagram_id, msg.message_id()))
                    .collect::<Vec<_>>();

                for reference in &message_refs {
                    insert_node(&mut adjacency, reference.clone());
                }

                for pair in message_refs.windows(2) {
                    let from = pair[0].clone();
                    let to = pair[1].clone();
                    insert_edge(&mut adjacency, from, to);
                }

                for msg in &messages {
                    let message_ref = seq_message_ref(diagram_id, msg.message_id());
                    let from_participant =
                        seq_participant_ref(diagram_id, msg.from_participant_id());
                    let to_participant = seq_participant_ref(diagram_id, msg.to_participant_id());

                    insert_node(&mut adjacency, message_ref.clone());
                    insert_node(&mut adjacency, from_participant.clone());
                    insert_node(&mut adjacency, to_participant.clone());

                    insert_edge(&mut adjacency, from_participant.clone(), message_ref.clone());
                    insert_edge(&mut adjacency, message_ref.clone(), from_participant);
                    insert_edge(&mut adjacency, to_participant.clone(), message_ref.clone());
                    insert_edge(&mut adjacency, message_ref, to_participant);
                }

                fn add_block(
                    diagram_id: &DiagramId,
                    block: &crate::model::seq_ast::SequenceBlock,
                    adjacency: &mut BTreeMap<ObjectRef, BTreeSet<ObjectRef>>,
                    parent: Option<ObjectRef>,
                ) {
                    let block_ref = seq_block_ref(diagram_id, block.block_id());
                    insert_node(adjacency, block_ref.clone());

                    if let Some(parent_ref) = parent.as_ref() {
                        insert_edge(adjacency, parent_ref.clone(), block_ref.clone());
                        insert_edge(adjacency, block_ref.clone(), parent_ref.clone());
                    }

                    for section in block.sections() {
                        let section_ref = seq_section_ref(diagram_id, section.section_id());
                        insert_node(adjacency, section_ref.clone());
                        insert_edge(adjacency, block_ref.clone(), section_ref.clone());
                        insert_edge(adjacency, section_ref.clone(), block_ref.clone());

                        for message_id in section.message_ids() {
                            let message_ref = seq_message_ref(diagram_id, message_id);
                            insert_node(adjacency, message_ref.clone());
                            insert_edge(adjacency, section_ref.clone(), message_ref.clone());
                            insert_edge(adjacency, message_ref, section_ref.clone());
                        }
                    }

                    for child in block.blocks() {
                        add_block(diagram_id, child, adjacency, Some(block_ref.clone()));
                    }
                }

                for block in ast.blocks() {
                    add_block(diagram_id, block, &mut adjacency, None);
                }
            }
        }
    }

    for xref in session.xrefs().values() {
        let a = xref.from().clone();
        let b = xref.to().clone();
        if !adjacency.contains_key(&a) || !adjacency.contains_key(&b) {
            continue;
        }
        insert_edge(&mut adjacency, a.clone(), b.clone());
        insert_edge(&mut adjacency, b, a);
    }

    adjacency
}

fn reconstruct_path(
    mut current: ObjectRef,
    start: &ObjectRef,
    previous: &BTreeMap<ObjectRef, ObjectRef>,
) -> Vec<ObjectRef> {
    let mut reversed = vec![current.clone()];
    while &current != start {
        let Some(prev) = previous.get(&current) else {
            break;
        };
        current = prev.clone();
        reversed.push(current.clone());
    }
    reversed.reverse();
    reversed
}

/// Ordering for multi-route results after exploration.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RoutesOrdering {
    /// Keep discovery order (heap expands fewest-hops first).
    FewestHops,
    /// Sort full paths lexicographically after collection.
    Lexicographic,
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct CandidateRoute {
    hops: u64,
    path: Vec<ObjectRef>,
}

impl Ord for CandidateRoute {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.hops, &self.path).cmp(&(other.hops, &other.path))
    }
}

impl PartialOrd for CandidateRoute {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Up to `limit` simple paths from `from` to `to` over a precomputed adjacency.
///
/// `max_hops` caps path length (edge hops); `None` means unbounded. Empty when either ref is
/// absent from the graph (except the zero-hop self route when `from == to` and present).
pub fn find_routes_with_adjacency(
    adjacency: &SessionRouteAdjacency,
    from: &ObjectRef,
    to: &ObjectRef,
    limit: u64,
    max_hops: Option<u64>,
    ordering: RoutesOrdering,
) -> Vec<Vec<ObjectRef>> {
    if limit == 0 {
        return Vec::new();
    }

    if from == to {
        return if adjacency.adjacency.contains_key(from) {
            vec![vec![from.clone()]]
        } else {
            Vec::new()
        };
    }

    let max_hops = max_hops.unwrap_or(u64::MAX);
    let mut candidates: BinaryHeap<Reverse<CandidateRoute>> = BinaryHeap::new();
    candidates.push(Reverse(CandidateRoute { hops: 0, path: vec![from.clone()] }));

    let mut routes = Vec::new();
    while let Some(Reverse(candidate)) = candidates.pop() {
        let Some(last) = candidate.path.last() else {
            continue;
        };

        if last == to {
            routes.push(candidate.path);
            if routes.len() as u64 >= limit {
                break;
            }
            continue;
        }

        if candidate.hops >= max_hops {
            continue;
        }

        let next_hops = candidate.hops + 1;
        for next in adjacency.adjacency.get(last).into_iter().flatten() {
            if candidate.path.contains(next) {
                continue;
            }

            let mut next_path = candidate.path.clone();
            next_path.push(next.clone());
            candidates.push(Reverse(CandidateRoute { hops: next_hops, path: next_path }));
        }
    }

    match ordering {
        RoutesOrdering::FewestHops => routes,
        RoutesOrdering::Lexicographic => {
            routes.sort();
            routes
        }
    }
}

/// [`find_routes_with_adjacency`] after deriving adjacency from `session` (one-shot).
pub fn find_routes(
    session: &Session,
    from: &ObjectRef,
    to: &ObjectRef,
    limit: u64,
    max_hops: Option<u64>,
    ordering: RoutesOrdering,
) -> Vec<Vec<ObjectRef>> {
    let adjacency = SessionRouteAdjacency::derive(session);
    find_routes_with_adjacency(&adjacency, from, to, limit, max_hops, ordering)
}

/// Shortest path (fewest hops) from `from` to `to`, or `None` if unreachable.
pub fn find_route_with_adjacency(
    adjacency: &SessionRouteAdjacency,
    from: &ObjectRef,
    to: &ObjectRef,
) -> Option<Vec<ObjectRef>> {
    if from == to {
        return adjacency.adjacency.contains_key(from).then(|| vec![from.clone()]);
    }

    let start = from.clone();
    let goal = to.clone();

    let mut visited: BTreeSet<ObjectRef> = BTreeSet::new();
    let mut previous: BTreeMap<ObjectRef, ObjectRef> = BTreeMap::new();
    let mut queue: VecDeque<ObjectRef> = VecDeque::new();

    visited.insert(start.clone());
    queue.push_back(start.clone());

    while let Some(node) = queue.pop_front() {
        for next in adjacency.adjacency.get(&node).into_iter().flatten() {
            if visited.contains(next) {
                continue;
            }

            visited.insert(next.clone());
            previous.insert(next.clone(), node.clone());

            if next == &goal {
                return Some(reconstruct_path(goal.clone(), &start, &previous));
            }

            queue.push_back(next.clone());
        }
    }

    None
}

/// [`find_route_with_adjacency`] after deriving adjacency from `session` (one-shot).
pub fn find_route(session: &Session, from: &ObjectRef, to: &ObjectRef) -> Option<Vec<ObjectRef>> {
    let adjacency = SessionRouteAdjacency::derive(session);
    find_route_with_adjacency(&adjacency, from, to)
}

#[cfg(test)]
mod tests {
    use super::{
        find_route, find_route_with_adjacency, find_routes, find_routes_with_adjacency,
        RoutesOrdering, SessionRouteAdjacency,
    };
    use crate::model::seq_ast::{
        SequenceBlock, SequenceBlockKind, SequenceSection, SequenceSectionKind,
    };
    use crate::model::{
        Diagram, DiagramAst, DiagramId, FlowEdge, FlowNode, FlowchartAst, ObjectRef, SequenceAst,
        SequenceMessage, SequenceMessageKind, Session, SessionId, XRef, XRefId, XRefStatus,
    };
    use crate::model::{ObjectId, SequenceParticipant};

    fn ref_strings(path: &[ObjectRef]) -> Vec<String> {
        path.iter().map(|r| r.to_string()).collect()
    }

    #[test]
    fn finds_simple_cross_diagram_route_via_xref() {
        let mut session = Session::new(SessionId::new("s1").expect("session id"));

        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        for node in ["n:a", "n:b"] {
            let node_id = ObjectId::new(node).expect("node id");
            flow_ast.nodes_mut().insert(node_id, FlowNode::new(node.to_uppercase()));
        }
        let edge_id = ObjectId::new("e:ab").expect("edge id");
        let from = ObjectId::new("n:a").expect("from node id");
        let to = ObjectId::new("n:b").expect("to node id");
        flow_ast.edges_mut().insert(edge_id, FlowEdge::new(from.clone(), to.clone()));

        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id.clone(), "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let seq_id = DiagramId::new("seq").expect("diagram id");
        let mut seq_ast = SequenceAst::default();
        let p1 = ObjectId::new("p:one").expect("participant id");
        let p2 = ObjectId::new("p:two").expect("participant id");
        seq_ast.participants_mut().insert(p1.clone(), SequenceParticipant::new("One"));
        seq_ast.participants_mut().insert(p2.clone(), SequenceParticipant::new("Two"));

        let m1 = ObjectId::new("m:1").expect("message id");
        let m2 = ObjectId::new("m:2").expect("message id");
        // Insert out of order to validate deterministic ordering by order_key + id.
        seq_ast.messages_mut().push(SequenceMessage::new(
            m2.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "Second",
            200,
        ));
        seq_ast.messages_mut().push(SequenceMessage::new(
            m1.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "First",
            100,
        ));

        session.diagrams_mut().insert(
            seq_id.clone(),
            Diagram::new(seq_id.clone(), "Seq", DiagramAst::Sequence(seq_ast)),
        );

        let xref_id = XRefId::new("x:1").expect("xref id");
        let xref_from: ObjectRef = "d:flow/flow/node/n:b".parse().expect("from ref");
        let xref_to: ObjectRef = "d:seq/seq/message/m:1".parse().expect("to ref");
        session
            .xrefs_mut()
            .insert(xref_id, XRef::new(xref_from, xref_to, "relates", XRefStatus::Ok));

        let start: ObjectRef = "d:flow/flow/node/n:a".parse().expect("start ref");
        let goal: ObjectRef = "d:seq/seq/message/m:2".parse().expect("goal ref");

        let route = find_route(&session, &start, &goal).expect("route");
        let adjacency = SessionRouteAdjacency::derive(&session);
        let cached_route =
            find_route_with_adjacency(&adjacency, &start, &goal).expect("cached route");
        assert_eq!(cached_route, route);

        assert_eq!(
            ref_strings(&route),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/node/n:b",
                "d:seq/seq/message/m:1",
                "d:seq/seq/message/m:2",
            ]
        );
    }

    #[test]
    fn dangling_xref_endpoints_do_not_create_phantom_route() {
        let mut session = Session::new(SessionId::new("s-dangling").expect("session id"));

        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        flow_ast.nodes_mut().insert(oid("n:a"), FlowNode::new("A"));
        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id.clone(), "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let x1_from: ObjectRef = "d:flow/flow/node/n:a".parse().expect("ref");
        let x1_to: ObjectRef = "d:flow/flow/node/n:gone".parse().expect("ref");
        session.xrefs_mut().insert(
            XRefId::new("x:1").expect("xref id"),
            XRef::new(x1_from, x1_to, "relates", XRefStatus::DanglingTo),
        );
        let x2_from: ObjectRef = "d:flow/flow/node/n:gone".parse().expect("ref");
        let x2_to: ObjectRef = "d:flow/flow/node/n:also_gone".parse().expect("ref");
        session.xrefs_mut().insert(
            XRefId::new("x:2").expect("xref id"),
            XRef::new(x2_from, x2_to, "relates", XRefStatus::DanglingFrom),
        );

        let start: ObjectRef = "d:flow/flow/node/n:a".parse().expect("start ref");
        let goal: ObjectRef = "d:flow/flow/node/n:also_gone".parse().expect("goal ref");

        assert_eq!(find_route(&session, &start, &goal), None);

        let adjacency = SessionRouteAdjacency::derive(&session);
        assert_eq!(find_route_with_adjacency(&adjacency, &start, &goal), None);
    }

    #[test]
    fn self_route_for_unknown_id_returns_no_route() {
        let session = Session::new(SessionId::new("s-empty").expect("session id"));
        let ghost: ObjectRef = "d:none/none/node/n:ghost".parse().expect("ghost ref");

        assert_eq!(find_route(&session, &ghost, &ghost), None);
        assert!(
            find_routes(&session, &ghost, &ghost, 1, None, RoutesOrdering::FewestHops).is_empty()
        );

        let adjacency = SessionRouteAdjacency::derive(&session);
        assert_eq!(find_route_with_adjacency(&adjacency, &ghost, &ghost), None);
        assert!(find_routes_with_adjacency(
            &adjacency,
            &ghost,
            &ghost,
            1,
            None,
            RoutesOrdering::FewestHops
        )
        .is_empty());
    }

    #[test]
    fn self_route_for_existing_id_returns_single_node() {
        let mut session = Session::new(SessionId::new("s-real").expect("session id"));
        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        flow_ast.nodes_mut().insert(oid("n:a"), FlowNode::new("A"));
        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id, "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let node: ObjectRef = "d:flow/flow/node/n:a".parse().expect("node ref");
        assert_eq!(find_route(&session, &node, &node), Some(vec![node.clone()]));
    }

    #[test]
    fn finds_flow_edge_and_endpoint_node_routes() {
        let mut session = Session::new(SessionId::new("s-edge").expect("session id"));

        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        for node in ["n:a", "n:b"] {
            let node_id = ObjectId::new(node).expect("node id");
            flow_ast.nodes_mut().insert(node_id, FlowNode::new(node.to_uppercase()));
        }

        flow_ast.edges_mut().insert(oid("e:ab"), FlowEdge::new(oid("n:a"), oid("n:b")));

        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id.clone(), "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let edge: ObjectRef = "d:flow/flow/edge/e:ab".parse().expect("edge ref");
        let from: ObjectRef = "d:flow/flow/node/n:a".parse().expect("from node ref");
        let to: ObjectRef = "d:flow/flow/node/n:b".parse().expect("to node ref");

        assert_eq!(
            ref_strings(&find_route(&session, &edge, &from).expect("edge->from route")),
            vec!["d:flow/flow/edge/e:ab", "d:flow/flow/node/n:a"]
        );
        assert_eq!(
            ref_strings(&find_route(&session, &edge, &to).expect("edge->to route")),
            vec!["d:flow/flow/edge/e:ab", "d:flow/flow/node/n:b"]
        );
        assert_eq!(
            ref_strings(&find_route(&session, &from, &edge).expect("from->edge route")),
            vec!["d:flow/flow/node/n:a", "d:flow/flow/edge/e:ab"]
        );
        assert_eq!(
            ref_strings(&find_route(&session, &to, &edge).expect("to->edge route")),
            vec!["d:flow/flow/node/n:b", "d:flow/flow/edge/e:ab"]
        );
    }

    #[test]
    fn finds_seq_participant_and_message_routes() {
        let mut session = Session::new(SessionId::new("s-participant").expect("session id"));

        let seq_id = DiagramId::new("seq").expect("diagram id");
        let mut seq_ast = SequenceAst::default();
        let p1 = ObjectId::new("p:one").expect("participant id");
        let p2 = ObjectId::new("p:two").expect("participant id");
        seq_ast.participants_mut().insert(p1.clone(), SequenceParticipant::new("One"));
        seq_ast.participants_mut().insert(p2.clone(), SequenceParticipant::new("Two"));

        let m1 = ObjectId::new("m:1").expect("message id");
        let m2 = ObjectId::new("m:2").expect("message id");
        seq_ast.messages_mut().push(SequenceMessage::new(
            m1.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "First",
            100,
        ));
        seq_ast.messages_mut().push(SequenceMessage::new(
            m2.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "Second",
            200,
        ));

        session.diagrams_mut().insert(
            seq_id.clone(),
            Diagram::new(seq_id.clone(), "Seq", DiagramAst::Sequence(seq_ast)),
        );

        let participant: ObjectRef =
            "d:seq/seq/participant/p:one".parse().expect("participant ref");
        let message: ObjectRef = "d:seq/seq/message/m:2".parse().expect("message ref");
        assert_eq!(
            ref_strings(
                &find_route(&session, &participant, &message).expect("participant->message route")
            ),
            vec!["d:seq/seq/participant/p:one", "d:seq/seq/message/m:2"]
        );

        let participant_to: ObjectRef =
            "d:seq/seq/participant/p:two".parse().expect("participant ref");
        let message_from: ObjectRef = "d:seq/seq/message/m:1".parse().expect("message ref");
        assert_eq!(
            ref_strings(
                &find_route(&session, &message_from, &participant_to)
                    .expect("message->participant route")
            ),
            vec!["d:seq/seq/message/m:1", "d:seq/seq/participant/p:two"]
        );
    }

    #[test]
    fn finds_seq_block_to_message_route() {
        let mut session = Session::new(SessionId::new("s-block-route").expect("session id"));

        let seq_id = DiagramId::new("seq").expect("diagram id");
        let mut seq_ast = SequenceAst::default();
        let p1 = ObjectId::new("p:one").expect("participant id");
        let p2 = ObjectId::new("p:two").expect("participant id");
        seq_ast.participants_mut().insert(p1.clone(), SequenceParticipant::new("One"));
        seq_ast.participants_mut().insert(p2.clone(), SequenceParticipant::new("Two"));

        let m1 = ObjectId::new("m:1").expect("message id");
        seq_ast.messages_mut().push(SequenceMessage::new(
            m1.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "First",
            100,
        ));

        seq_ast.blocks_mut().push(SequenceBlock::new(
            ObjectId::new("b:0000").expect("block id"),
            SequenceBlockKind::Alt,
            None,
            vec![SequenceSection::new(
                ObjectId::new("sec:0000:00").expect("section id"),
                SequenceSectionKind::Main,
                None,
                vec![m1.clone()],
            )],
            Vec::new(),
        ));

        session.diagrams_mut().insert(
            seq_id.clone(),
            Diagram::new(seq_id.clone(), "Seq", DiagramAst::Sequence(seq_ast)),
        );

        let block: ObjectRef = "d:seq/seq/block/b:0000".parse().expect("block ref");
        let message: ObjectRef = "d:seq/seq/message/m:1".parse().expect("message ref");
        assert_eq!(
            ref_strings(&find_route(&session, &block, &message).expect("block->message route")),
            vec![
                "d:seq/seq/block/b:0000",
                "d:seq/seq/section/sec:0000:00",
                "d:seq/seq/message/m:1",
            ]
        );
    }

    #[test]
    fn finds_cross_diagram_route_via_edge_and_participant_xref() {
        let mut session = Session::new(SessionId::new("s-xref").expect("session id"));

        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        for node in ["n:a", "n:b"] {
            let node_id = ObjectId::new(node).expect("node id");
            flow_ast.nodes_mut().insert(node_id, FlowNode::new(node.to_uppercase()));
        }
        flow_ast.edges_mut().insert(oid("e:ab"), FlowEdge::new(oid("n:a"), oid("n:b")));
        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id.clone(), "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let seq_id = DiagramId::new("seq").expect("diagram id");
        let mut seq_ast = SequenceAst::default();
        let p1 = ObjectId::new("p:one").expect("participant id");
        let p2 = ObjectId::new("p:two").expect("participant id");
        seq_ast.participants_mut().insert(p1.clone(), SequenceParticipant::new("One"));
        seq_ast.participants_mut().insert(p2.clone(), SequenceParticipant::new("Two"));

        let m1 = ObjectId::new("m:1").expect("message id");
        let m2 = ObjectId::new("m:2").expect("message id");
        seq_ast.messages_mut().push(SequenceMessage::new(
            m1.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "First",
            100,
        ));
        seq_ast.messages_mut().push(SequenceMessage::new(
            m2.clone(),
            p1.clone(),
            p2.clone(),
            SequenceMessageKind::Sync,
            "Second",
            200,
        ));

        session.diagrams_mut().insert(
            seq_id.clone(),
            Diagram::new(seq_id.clone(), "Seq", DiagramAst::Sequence(seq_ast)),
        );

        let xref_id = XRefId::new("x:1").expect("xref id");
        let xref_from: ObjectRef = "d:flow/flow/edge/e:ab".parse().expect("from ref");
        let xref_to: ObjectRef = "d:seq/seq/participant/p:one".parse().expect("to ref");
        session
            .xrefs_mut()
            .insert(xref_id, XRef::new(xref_from, xref_to, "relates", XRefStatus::Ok));

        let start: ObjectRef = "d:flow/flow/node/n:a".parse().expect("start ref");
        let goal: ObjectRef = "d:seq/seq/message/m:2".parse().expect("goal ref");
        let route = find_route(&session, &start, &goal).expect("route");
        assert_eq!(
            ref_strings(&route),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/edge/e:ab",
                "d:seq/seq/participant/p:one",
                "d:seq/seq/message/m:2",
            ]
        );
    }

    #[test]
    fn finds_multiple_routes_deterministically_and_supports_ordering() {
        let mut session = Session::new(SessionId::new("s2").expect("session id"));

        let flow_id = DiagramId::new("flow").expect("diagram id");
        let mut flow_ast = FlowchartAst::default();
        for node in ["n:a", "n:b", "n:c", "n:d"] {
            let node_id = ObjectId::new(node).expect("node id");
            flow_ast.nodes_mut().insert(node_id, FlowNode::new(node.to_uppercase()));
        }

        flow_ast.edges_mut().insert(oid("e:ab"), FlowEdge::new(oid("n:a"), oid("n:b")));
        flow_ast.edges_mut().insert(oid("e:ac"), FlowEdge::new(oid("n:a"), oid("n:c")));
        flow_ast.edges_mut().insert(oid("e:bd"), FlowEdge::new(oid("n:b"), oid("n:d")));
        flow_ast.edges_mut().insert(oid("e:cd"), FlowEdge::new(oid("n:c"), oid("n:d")));
        flow_ast.edges_mut().insert(oid("e:bc"), FlowEdge::new(oid("n:b"), oid("n:c")));

        session.diagrams_mut().insert(
            flow_id.clone(),
            Diagram::new(flow_id.clone(), "Flow", DiagramAst::Flowchart(flow_ast)),
        );

        let start: ObjectRef = "d:flow/flow/node/n:a".parse().expect("start ref");
        let goal: ObjectRef = "d:flow/flow/node/n:d".parse().expect("goal ref");

        let adjacency = SessionRouteAdjacency::derive(&session);
        let routes = find_routes_with_adjacency(
            &adjacency,
            &start,
            &goal,
            10,
            Some(3),
            RoutesOrdering::FewestHops,
        );
        let repeat = find_routes(&session, &start, &goal, 10, Some(3), RoutesOrdering::FewestHops);
        assert_eq!(routes, repeat);

        assert_eq!(routes.len(), 7);
        assert_eq!(
            ref_strings(&routes[0]),
            vec!["d:flow/flow/node/n:a", "d:flow/flow/node/n:b", "d:flow/flow/node/n:d",]
        );
        assert_eq!(
            ref_strings(&routes[1]),
            vec!["d:flow/flow/node/n:a", "d:flow/flow/node/n:c", "d:flow/flow/node/n:d",]
        );
        assert_eq!(
            ref_strings(&routes[2]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/edge/e:ab",
                "d:flow/flow/node/n:b",
                "d:flow/flow/node/n:d",
            ]
        );
        assert_eq!(
            ref_strings(&routes[3]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/edge/e:ac",
                "d:flow/flow/node/n:c",
                "d:flow/flow/node/n:d",
            ]
        );
        assert_eq!(
            ref_strings(&routes[4]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/node/n:b",
                "d:flow/flow/edge/e:bd",
                "d:flow/flow/node/n:d",
            ]
        );
        assert_eq!(
            ref_strings(&routes[5]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/node/n:b",
                "d:flow/flow/node/n:c",
                "d:flow/flow/node/n:d",
            ]
        );
        assert_eq!(
            ref_strings(&routes[6]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/node/n:c",
                "d:flow/flow/edge/e:cd",
                "d:flow/flow/node/n:d",
            ]
        );

        let lex_routes =
            find_routes(&session, &start, &goal, 10, Some(3), RoutesOrdering::Lexicographic);
        assert_eq!(
            ref_strings(&lex_routes[0]),
            vec![
                "d:flow/flow/node/n:a",
                "d:flow/flow/edge/e:ab",
                "d:flow/flow/node/n:b",
                "d:flow/flow/node/n:d",
            ]
        );
    }

    #[test]
    fn gantt_sections_lanes_and_after_dependencies_share_the_route_graph() {
        let mut session = Session::new(SessionId::new("s:gantt-routes").unwrap());
        let diagram_id = DiagramId::new("gantt").unwrap();
        let ast = crate::format::mermaid::parse_gantt_diagram(
            "gantt\ndateFormat YYYY-MM-DD\nsection Build\nFirst :a, 2026-01-01, 7d\nSecond :b, after a, 7d\n",
        )
        .unwrap();
        let section_id = ast.sections()[0].section_id().clone();
        let first_id = ast
            .tasks()
            .iter()
            .find(|(_, task)| task.name() == "First")
            .map(|(id, _)| id.clone())
            .unwrap();
        let second_id = ast
            .tasks()
            .iter()
            .find(|(_, task)| task.name() == "Second")
            .map(|(id, _)| id.clone())
            .unwrap();
        session.diagrams_mut().insert(
            diagram_id,
            Diagram::new(DiagramId::new("gantt").unwrap(), "Gantt", DiagramAst::Gantt(ast)),
        );

        let section: ObjectRef = format!("d:gantt/gantt/section/{section_id}").parse().unwrap();
        let lane: ObjectRef = "d:gantt/gantt/lane/lane:2026-01-01".parse().unwrap();
        let second: ObjectRef = format!("d:gantt/gantt/task/{second_id}").parse().unwrap();

        let to_lane = find_route(&session, &section, &lane).expect("section to lane route");
        assert_eq!(to_lane.len(), 3);
        assert_eq!(to_lane[1].object_id(), &first_id);

        let dependency = find_route(&session, &lane, &second).expect("lane to after task route");
        assert!(dependency.iter().any(|item| item.object_id() == &first_id));
    }

    fn oid(raw: &str) -> ObjectId {
        ObjectId::new(raw).expect("object id")
    }
}