Coverage for graphqler / chains / strategies / all_dependencies_strategy.py: 100%

1"""AllDependencies chain generation strategy.""" 

2 

3from typing import cast 

4 

5import networkx 

6 

7from graphqler.chains.chain import Chain 

8from graphqler.chains.strategies.base_strategy import BaseChainStrategy 

9from graphqler.graph.node import Node 

10 

11# Lower value = earlier in chain within a strongly connected component. 

12# Mutations typically CREATE objects, so they should run before Objects and Queries. 

13_GRAPHQL_TYPE_PRIORITY: dict[str, int] = {"Mutation": 0, "Object": 1, "Query": 2} 

14 

15 

16class AllDependenciesChainStrategy(BaseChainStrategy): 

17 """Generates one self-sufficient chain per node by including all transitive dependencies. 

18 

19 For every node N in topological order: 

20 

21 1. Compute ``networkx.ancestors(graph, N)`` — all transitive predecessors. 

22 2. Remove ancestors whose ``mutation_type`` is in *filter_mutation_type*. 

23 3. Build a subgraph view from ``valid_ancestors U {N}`` — the original edges 

24 between those nodes are preserved automatically by NetworkX. 

25 4. Topological-sort the subgraph using SCC condensation (handles cycles gracefully). 

26 

27 **Cycle handling:** Real-world GraphQL APIs produce cycles in the dependency graph 

28 (e.g. a ``restaurant`` query both *returns* and *requires* a ``Restaurant`` object). 

29 Plain ``topological_sort`` gives invalid orderings on cyclic graphs. This strategy 

30 uses ``networkx.condensation()`` to collapse each strongly-connected component (SCC) 

31 into a single node, topological-sorts the resulting DAG, then expands each SCC back 

32 to its member nodes sorted by type priority (Mutation → Object → Query). This 

33 ensures that CREATE mutations in the same SCC run before the objects they produce. 

34 

35 The resulting chain is **fully self-sufficient**: running it on a truly empty 

36 :class:`~graphqler.fuzzer.utils.objects_bucket.ObjectsBucket` will succeed 

37 because every prerequisite is created earlier in the same chain. 

38 

39 The *starter_nodes* parameter is accepted for interface compatibility but is 

40 ignored — every non-filtered node in the graph gets its own chain. 

41 """ 

42 

43 def generate(self, graph: networkx.DiGraph, starter_nodes: list[Node], 

44 filter_mutation_type: list[str] | None = None) -> list[Chain]: 

45 """Generate one self-sufficient chain per non-filtered node. 

46 

47 Args: 

48 graph (networkx.DiGraph): The dependency graph. 

49 starter_nodes (list[Node]): Accepted for interface compatibility; not used. 

50 filter_mutation_type (list[str] | None): Mutation types to exclude. 

51 Nodes with a ``mutation_type`` in this list are skipped entirely; 

52 they are also removed from ancestor sets of other chains. 

53 Pass ``None`` or ``[]`` to include all nodes. 

54 

55 Returns: 

56 list[Chain]: One chain per non-filtered node in stable order. 

57 """ 

58 excluded = set(filter_mutation_type) if filter_mutation_type else set() 

59 chains: list[Chain] = [] 

60 

61 for node in self._safe_topo_sort(graph): 

62 if node.mutation_type in excluded: 

63 continue 

64 

65 # All transitive predecessors, excluding filtered nodes 

66 ancestors = cast(set[Node], networkx.ancestors(graph, node)) 

67 valid_ancestors: set[Node] = { 

68 a for a in ancestors 

69 if a.mutation_type not in excluded 

70 } 

71 

72 chain_node_set = valid_ancestors | {node} 

73 subgraph = graph.subgraph(chain_node_set) 

74 sorted_nodes = self._safe_topo_sort(subgraph) 

75 

76 chains.append(Chain(nodes=sorted_nodes)) 

77 

78 return chains 

79 

80 def _safe_topo_sort(self, graph: networkx.DiGraph) -> list[Node]: 

81 """Topological sort that handles cycles via SCC condensation. 

82 

83 Uses ``networkx.condensation()`` to collapse cycles into single nodes 

84 (always a DAG), topological-sorts the condensation, then expands each 

85 SCC back to its member nodes sorted by ``graphql_type`` priority 

86 (Mutation → Object → Query) so that creators run before their products. 

87 

88 Args: 

89 graph (networkx.DiGraph): Any directed graph, cyclic or acyclic. 

90 

91 Returns: 

92 list[Node]: Nodes in a valid dependency order. 

93 """ 

94 condensation = networkx.condensation(graph) 

95 result: list[Node] = [] 

96 for cond_node in networkx.topological_sort(condensation): 

97 members: set[Node] = condensation.nodes[cond_node]["members"] 

98 ordered = sorted(members, key=lambda n: (_GRAPHQL_TYPE_PRIORITY.get(n.graphql_type, 1), n.name)) 

99 result.extend(ordered) 

100 return result 

101