Coverage for datakiln/metadata/graph.py: 52%
112 statements
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-16 23:23 +0000
« prev ^ index » next coverage.py v7.17.3, created at 2026-11-16 23:23 +0000
1"""
2Dependency graphs for metadata objects.
3"""
4from dataclasses import dataclass
5from functools import cached_property
6from typing import Dict, Iterable, List, Optional, Set
7from graphlib import TopologicalSorter
9import networkx as nx
11from datakiln.metadata.script import ScriptMeta, ScriptError
12from datakiln.metadata.table import TableMeta
15@dataclass(frozen=True)
16class Unresolved:
17 """Name that nodes require, which is not a node. Two with the same name are
18 the same dependency."""
20 full_name: str
23class DependencyGraph:
24 # pylint: disable=too-few-public-methods
25 """Directed Acyclic Graph for nodes that depend on one another.
27 Nodes list the names of the nodes they `requires`, which the graph turns
28 into the nodes themselves. Required names that are not nodes (e.g. tables
29 loaded elsewhere) are ignored, unless `keep_unresolved` is set, in which
30 case they become dependencies of the nodes that are `Unresolved` objects,
31 which are not part of the nodes.
33 Nodes have a `full_name`, which tells them apart in errors.
34 """
36 def __init__(self, nodes: List,
37 keep_unresolved: bool = False,
38 aliases: Optional[Dict[str, Set]] = None):
39 """
40 :param nodes: Nodes with a `full_name` and what they `requires`.
41 :type nodes: list[object]
43 :param keep_unresolved: Keep required names that are not nodes as
44 dependencies.
45 :type keep_unresolved: bool
47 :param aliases: Names that stand for several nodes, which are all
48 dependencies of the nodes requiring the name. A node
49 is never a dependency of itself this way.
50 :type aliases: dict[str, set[object]]
51 """
52 # By name, which is how what the nodes require is found
53 self.nodes: Dict[str, object] = {}
54 for node in nodes:
55 self.nodes[node.full_name] = node
56 aliases = aliases or {}
58 self.unresolved: Set[Unresolved] = set()
60 # An arrow goes from what is needed to what needs it
61 self.digraph = nx.DiGraph()
62 self.digraph.add_nodes_from(self.nodes.values())
63 for node in self.nodes.values():
64 for required in node.requires:
65 if required in self.nodes:
66 self.digraph.add_edge(self.nodes[required], node)
67 elif required in aliases:
68 for other in aliases[required] - {node}:
69 self.digraph.add_edge(other, node)
70 elif keep_unresolved:
71 unresolved = Unresolved(required)
72 self.unresolved.add(unresolved)
73 self.digraph.add_edge(unresolved, node)
75 def dependencies(self, node: object) -> Set:
76 """Nodes that a node needs directly.
78 :param node: Node of the graph.
79 :type node: object
81 :return: The nodes it needs, which include the dependencies that are
82 not nodes if they are kept.
83 :rtype: set[object]
84 """
85 return set(self.digraph.predecessors(node))
87 def _check_acyclic(self):
88 """Checks that no node needs itself, directly or indirectly.
90 :raises ValueError: If the dependencies contain a cycle.
91 """
92 if nx.is_directed_acyclic_graph(self.digraph):
93 return
95 # Read the arrows the other way, from a node to what it needs
96 cycle = nx.find_cycle(self.digraph.reverse(copy=False))
97 path = []
98 for node, _ in cycle:
99 path.append(node.full_name)
100 path.append(path[0])
101 raise ValueError(f"Circular dependency: {' -> '.join(path)}")
103 @property
104 def topological_sorter(self) -> TopologicalSorter:
105 """Returns a prepared TopologicalSorter for the graph, which gives the
106 nodes that can run as the ones they need are done.
108 :raises ValueError: If the dependencies contain a cycle.
109 """
110 self._check_acyclic()
112 sorter = TopologicalSorter()
113 for node in self.digraph:
114 sorter.add(node, *self.digraph.predecessors(node))
115 sorter.prepare()
116 return sorter
118 def find(self, names: Iterable[str]) -> Set:
119 """Nodes by name.
121 :param names: Names of nodes of the graph.
122 :type names: Iterable[str]
124 :return: The nodes.
125 :rtype: set[object]
127 :raises ValueError: If any of the names is not a node.
128 """
129 names = list(names)
130 unknown = set(names) - set(self.nodes)
131 if unknown:
132 raise ValueError(f"Not found: {', '.join(sorted(unknown))}.")
134 found = set()
135 for name in names:
136 found.add(self.nodes[name])
137 return found
139 def requirements(self, nodes: Iterable) -> Set:
140 """The specified nodes, with the nodes they need, directly or
141 indirectly. Names that are not nodes are left out.
143 :param nodes: Nodes of the graph.
144 :type nodes: Iterable[object]
146 :return: The nodes and what they need.
147 :rtype: set[object]
148 """
149 needed = set()
150 for node in nodes:
151 needed.add(node)
152 needed |= nx.ancestors(self.digraph, node)
153 return needed - self.unresolved
155 def affected(self, nodes: Iterable) -> Set:
156 """Nodes that need any of the specified nodes, directly or
157 indirectly.
159 :param nodes: Nodes of the graph.
160 :type nodes: Iterable[object]
162 :return: The nodes that need them.
163 :rtype: set[object]
164 """
165 affected = set()
166 for node in nodes:
167 affected |= nx.descendants(self.digraph, node)
168 return affected
170 def sort(self) -> List:
171 """Perform topological sort to determine execution order.
173 :return: Nodes ordered so that dependencies come first. Dependencies
174 that are not nodes are not returned.
175 :rtype: list
177 :raises ValueError: If the dependencies contain a cycle.
178 """
179 self._check_acyclic()
181 ordered = []
182 for node in nx.topological_sort(self.digraph):
183 if not isinstance(node, Unresolved):
184 ordered.append(node)
185 return ordered
188class DatabaseGraph(DependencyGraph):
189 # pylint: disable=too-few-public-methods
190 """Dependency graph for the tables (metadata) and the scripts (derive)
191 of a database."""
193 def __init__(self, tables: List, scripts: List[ScriptMeta],
194 external: Optional[List] = None):
195 """
196 :param tables: Table metadata.
197 :type tables: list[datakiln.metadata.table.TableMeta]
199 :param scripts: Scripts that create objects from the tables.
200 :type scripts: list[ScriptMeta]
202 :param external: Tables and scripts that other repos build, which the
203 tables and scripts can use. They are not built.
204 :type external: list
205 """
206 created = {}
207 for table in (external or []) + tables:
208 created[table.full_name] = table
210 overloads: Dict[str, Set] = {}
211 for script in scripts:
212 # An object can only be created once
213 if other := created.get(script.full_name):
214 creator = getattr(other, "path", "the metadata")
215 raise ScriptError(script.path, f"duplicate in {creator}.")
216 created[script.full_name] = script
218 # Calls do not tell which overload of a function is used, so they
219 # refer to all of them
220 function, parenthesis, _ = script.full_name.partition("(")
221 if parenthesis:
222 overloads.setdefault(function, set()).add(script)
224 super().__init__(list(created.values()), aliases=overloads)
226 @cached_property
227 def schemas(self) -> Set[str]:
228 """Schemas of the tables and scripts, in lower case, other than the
229 ones of the external objects. A function is in none."""
230 schemas = set()
231 for name, node in self.nodes.items():
232 if "(" not in name and not node.external:
233 schemas.add(name.partition(".")[0])
234 return schemas
236 @property
237 def tables(self) -> List:
238 """Tables to build, ordered so that referenced tables come first."""
239 tables = []
240 for node in self.sort():
241 if isinstance(node, TableMeta) and not node.external:
242 tables.append(node)
243 return tables
245 @property
246 def scripts(self) -> List[ScriptMeta]:
247 """Scripts to build, ordered so that the scripts creating the objects
248 they use come first."""
249 scripts = []
250 for node in self.sort():
251 if isinstance(node, ScriptMeta) and not node.external:
252 scripts.append(node)
253 return scripts