Find leaf nodes (nodes that no other nodes depend on) and build dependency trees showing the full dependency chain from each leaf back to the ultimate dependencies. The graph uses natural dependency direction: - If A depends on B, the graph has an edge A → B - Leaf nodes ar
(graph: Dict[str, Set[str]], components: Dict[str, Node])
| 269 | graph[comp_id] = set() |
| 270 | |
| 271 | # Add dependencies |
| 272 | for dep_id in component.depends_on: |
| 273 | # Only include dependencies that are actual components in our repository |
| 274 | if dep_id in components: |
| 275 | graph[comp_id].add(dep_id) |
| 276 | |
| 277 | return graph |
| 278 | |
| 279 | |
| 280 | def get_leaf_nodes(graph: dict[str, set[str]], components: dict[str, Node]) -> list[str]: |
| 281 | """ |
| 282 | Find leaf nodes (nodes that no other nodes depend on) and build dependency trees |
| 283 | showing the full dependency chain from each leaf back to the ultimate dependencies. |
| 284 | |
| 285 | The graph uses natural dependency direction: |
| 286 | - If A depends on B, the graph has an edge A → B |
| 287 | - Leaf nodes are nodes that appear in no other node's dependency set |
| 288 | - Each tree shows the dependency chain: leaf → its dependencies → their dependencies, etc. |
| 289 | |
| 290 | Args: |
| 291 | graph: A dependency graph with natural direction (A→B if A depends on B) |
| 292 | |
| 293 | Returns: |
| 294 | A list of leaf nodes |
| 295 | """ |
| 296 | # First, resolve cycles to ensure we have a DAG |
| 297 | acyclic_graph = resolve_cycles(graph) |
| 298 | |
| 299 | # Find leaf nodes (nodes that no other nodes depend on) |
| 300 | leaf_nodes = set(acyclic_graph.keys()) |
| 301 | |
| 302 | valid_types = compute_valid_leaf_types(components) |
| 303 | |
| 304 | def concise_node(leaf_nodes: set[str]) -> set[str]: |
| 305 | concise_leaf_nodes = set() |
| 306 | for node in leaf_nodes: |
| 307 | if node.endswith("__init__"): |
| 308 | # replace by class name |
| 309 | concise_leaf_nodes.add(node.replace(".__init__", "")) |
| 310 | else: |
| 311 | concise_leaf_nodes.add(node) |
| 312 | |
| 313 | return filter_leaf_nodes(concise_leaf_nodes, components, valid_types) |
| 314 | |
| 315 | concise_leaf_nodes = concise_node(leaf_nodes) |
| 316 | if len(concise_leaf_nodes) >= LEAF_REDUCTION_THRESHOLD: |
| 317 | count_before = len(concise_leaf_nodes) |
| 318 | logger.info( |
| 319 | "Leaf nodes are too many (%d >= %d); reducing to components " |
| 320 | "that nothing else depends on.", |
| 321 | count_before, |
| 322 | LEAF_REDUCTION_THRESHOLD, |
| 323 | ) |
| 324 | # Remove nodes that are dependencies of other nodes. Edges that start |
| 325 | # at an artifact node (a Dockerfile COPY, a CI `run:` line, a manifest |
| 326 | # entry point) are references, not calls: they must not demote the |
| 327 | # code component they point at. |
| 328 | for node, deps in acyclic_graph.items(): |
no test coverage detected