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

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 

8 

9import networkx as nx 

10 

11from datakiln.metadata.script import ScriptMeta, ScriptError 

12from datakiln.metadata.table import TableMeta 

13 

14 

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.""" 

19 

20 full_name: str 

21 

22 

23class DependencyGraph: 

24 # pylint: disable=too-few-public-methods 

25 """Directed Acyclic Graph for nodes that depend on one another. 

26 

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. 

32 

33 Nodes have a `full_name`, which tells them apart in errors. 

34 """ 

35 

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] 

42 

43 :param keep_unresolved: Keep required names that are not nodes as 

44 dependencies. 

45 :type keep_unresolved: bool 

46 

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 {} 

57 

58 self.unresolved: Set[Unresolved] = set() 

59 

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) 

74 

75 def dependencies(self, node: object) -> Set: 

76 """Nodes that a node needs directly. 

77 

78 :param node: Node of the graph. 

79 :type node: object 

80 

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)) 

86 

87 def _check_acyclic(self): 

88 """Checks that no node needs itself, directly or indirectly. 

89 

90 :raises ValueError: If the dependencies contain a cycle. 

91 """ 

92 if nx.is_directed_acyclic_graph(self.digraph): 

93 return 

94 

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)}") 

102 

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. 

107 

108 :raises ValueError: If the dependencies contain a cycle. 

109 """ 

110 self._check_acyclic() 

111 

112 sorter = TopologicalSorter() 

113 for node in self.digraph: 

114 sorter.add(node, *self.digraph.predecessors(node)) 

115 sorter.prepare() 

116 return sorter 

117 

118 def find(self, names: Iterable[str]) -> Set: 

119 """Nodes by name. 

120 

121 :param names: Names of nodes of the graph. 

122 :type names: Iterable[str] 

123 

124 :return: The nodes. 

125 :rtype: set[object] 

126 

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))}.") 

133 

134 found = set() 

135 for name in names: 

136 found.add(self.nodes[name]) 

137 return found 

138 

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. 

142 

143 :param nodes: Nodes of the graph. 

144 :type nodes: Iterable[object] 

145 

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 

154 

155 def affected(self, nodes: Iterable) -> Set: 

156 """Nodes that need any of the specified nodes, directly or 

157 indirectly. 

158 

159 :param nodes: Nodes of the graph. 

160 :type nodes: Iterable[object] 

161 

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 

169 

170 def sort(self) -> List: 

171 """Perform topological sort to determine execution order. 

172 

173 :return: Nodes ordered so that dependencies come first. Dependencies 

174 that are not nodes are not returned. 

175 :rtype: list 

176 

177 :raises ValueError: If the dependencies contain a cycle. 

178 """ 

179 self._check_acyclic() 

180 

181 ordered = [] 

182 for node in nx.topological_sort(self.digraph): 

183 if not isinstance(node, Unresolved): 

184 ordered.append(node) 

185 return ordered 

186 

187 

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.""" 

192 

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] 

198 

199 :param scripts: Scripts that create objects from the tables. 

200 :type scripts: list[ScriptMeta] 

201 

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 

209 

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 

217 

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) 

223 

224 super().__init__(list(created.values()), aliases=overloads) 

225 

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 

235 

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 

244 

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