"""TDD — Phase 1 of issue #40: walk_dag_async utility.

W1  Structural — walk_dag_async is an async generator
W2  Behavioural — BFS order: linear chain A→B→C yields A, B, C
W3  Behavioural — exclude set prevents visiting excluded nodes and subtrees
W4  Behavioural — max_nodes cap stops the walk after N nodes
W5  Behavioural — DFS order: linear chain yields depth-first (same for linear,
                  but diamond graph distinguishes BFS from DFS)
W6  Behavioural — multi-root start seeds from all roots simultaneously
W7  Behavioural — cycles handled: each node yielded at most once
"""
from __future__ import annotations

import inspect
import pytest

AdjGraph = dict[str, list[str]]

# ---------------------------------------------------------------------------
# Helpers
# ---------------------------------------------------------------------------

async def _adj(graph: AdjGraph) -> None:
    """Return an async adjacency function over an in-memory dict."""
    async def adjacency(node: str) -> list[str]:
        return graph.get(node, [])
    return adjacency


# ---------------------------------------------------------------------------
# W1  Structural — walk_dag_async is an async generator
# ---------------------------------------------------------------------------

def test_w1_walk_dag_async_is_async_generator() -> None:
    """walk_dag_async must return an async generator (async iterator)."""
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B"], "B": []}
    result = walk_dag_async("A", lambda n: _noop_adj(n, graph))

    assert hasattr(result, "__aiter__"), (
        "walk_dag_async must return an object with __aiter__ (async generator)"
    )
    assert hasattr(result, "__anext__"), (
        "walk_dag_async must return an object with __anext__ (async generator)"
    )


async def _noop_adj(node: str, graph: AdjGraph) -> list[str]:
    return graph.get(node, [])


# ---------------------------------------------------------------------------
# W2  Behavioural — BFS order: linear chain
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w2_bfs_linear_chain() -> None:
    """BFS on A→B→C yields nodes in breadth-first order: A, B, C."""
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B"], "B": ["C"], "C": []}

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    result = [n async for n in walk_dag_async("A", adj)]
    assert result == ["A", "B", "C"], f"Expected BFS order A→B→C, got {result}"


# ---------------------------------------------------------------------------
# W3  Behavioural — exclude set
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w3_exclude_set() -> None:
    """Nodes in exclude are not visited and their subtrees are not explored.

    Graph: A→B→C, A→D.  exclude={B}.
    Expected: A, D  (B and C skipped).
    """
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B", "D"], "B": ["C"], "C": [], "D": []}

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    result = [n async for n in walk_dag_async("A", adj, exclude={"B"})]
    assert "B" not in result, "B must not appear — it is in exclude"
    assert "C" not in result, "C must not appear — its only path goes through excluded B"
    assert "A" in result
    assert "D" in result


# ---------------------------------------------------------------------------
# W4  Behavioural — max_nodes cap
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w4_max_nodes_cap() -> None:
    """Walk stops after max_nodes nodes have been yielded."""
    from musehub.graph.walk import walk_dag_async

    # Linear chain of 10 nodes
    graph = {str(i): [str(i + 1)] for i in range(9)}
    graph["9"] = []

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    result = [n async for n in walk_dag_async("0", adj, max_nodes=3)]
    assert len(result) == 3, f"Expected exactly 3 nodes, got {len(result)}"


# ---------------------------------------------------------------------------
# W5  Behavioural — DFS order (diamond graph distinguishes from BFS)
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w5_dfs_order() -> None:
    """DFS on a diamond graph explores depth-first.

    Diamond: A → B, A → C; B → D; C → D.
    BFS order:  A B C D  (level-by-level)
    DFS order:  A B D C  (or A C D B — depends on stack direction)

    We assert the DFS result differs from BFS and D appears before C (or B).
    """
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    bfs_result = [n async for n in walk_dag_async("A", adj, order="bfs")]
    dfs_result = [n async for n in walk_dag_async("A", adj, order="dfs")]

    assert set(bfs_result) == {"A", "B", "C", "D"}, "BFS must visit all nodes"
    assert set(dfs_result) == {"A", "B", "C", "D"}, "DFS must visit all nodes"
    assert bfs_result != dfs_result, (
        "DFS and BFS must produce different orderings on a diamond graph"
    )
    # BFS: A B C D (level-by-level).
    # DFS with deque.pop() (LIFO): neighbours are appended in order [B, C],
    # so C is popped first → order is A C D B.  D must appear before B in DFS.
    assert dfs_result.index("D") < dfs_result.index("B"), (
        f"In DFS, D should be reached before B; got {dfs_result}"
    )


# ---------------------------------------------------------------------------
# W6  Behavioural — multi-root
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w6_multi_root() -> None:
    """Multi-root seeds the BFS from all start nodes simultaneously.

    Two disjoint chains: A→B and X→Y.
    Starting from [A, X], all four nodes must be yielded.
    """
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B"], "B": [], "X": ["Y"], "Y": []}

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    result = [n async for n in walk_dag_async(["A", "X"], adj)]
    assert set(result) == {"A", "B", "X", "Y"}, (
        f"Multi-root must reach all nodes; got {result}"
    )


# ---------------------------------------------------------------------------
# W7  Behavioural — cycle safety
# ---------------------------------------------------------------------------

@pytest.mark.asyncio
async def test_w7_cycle_safety() -> None:
    """Each node is yielded at most once even when the graph has cycles.

    Cycle: A→B→C→A.  Walk must terminate and yield each node once.
    """
    from musehub.graph.walk import walk_dag_async

    graph = {"A": ["B"], "B": ["C"], "C": ["A"]}

    async def adj(node: str) -> list[str]:
        return graph.get(node, [])

    result = [n async for n in walk_dag_async("A", adj)]
    assert sorted(result) == ["A", "B", "C"], (
        f"Each node must appear exactly once; got {result}"
    )
    assert len(result) == len(set(result)), "No node may be yielded twice"