Spaces:
Starting
Starting
File size: 1,781 Bytes
036a2db | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | """
blast_radius.py — Find all symbols transitively affected by a change.
Given a changed symbol, walks the REVERSE graph (callers) to find
everything that depends on it.
Performance fix: accept an optional pre-built reverse graph so the caller
can build it once and reuse it across multiple symbols instead of
rebuilding it O(N) times.
"""
from typing import Dict, List, Optional, Set
def build_reverse_graph(graph: Dict[str, List[str]]) -> Dict[str, Set[str]]:
"""Build the reverse (caller) graph once; reuse for many queries."""
reverse: Dict[str, Set[str]] = {}
for caller, callees in graph.items():
for callee in callees:
reverse.setdefault(callee, set()).add(caller)
return reverse
def get_blast_radius(
graph: Dict[str, List[str]],
changed_symbol: str,
reverse: Optional[Dict[str, Set[str]]] = None,
) -> List[str]:
"""
All functions that (transitively) call changed_symbol.
Args:
graph: Forward call graph (caller -> [callees]).
changed_symbol: The symbol whose blast radius we want.
reverse: Pre-built reverse graph. If None it is built here
(correct but wasteful when called in a loop).
Uses iterative DFS with cycle detection.
"""
if reverse is None:
reverse = build_reverse_graph(graph)
affected: List[str] = []
visited: Set[str] = set()
# Iterative DFS on reverse graph
stack = [changed_symbol]
visited.add(changed_symbol)
while stack:
current = stack.pop()
for caller in reverse.get(current, ()):
if caller not in visited:
visited.add(caller)
affected.append(caller)
stack.append(caller)
return affected
|