Source code

001package gudusoft.gsqlparser.analyzer.v2.callgraph;
002
003import gudusoft.gsqlparser.analyzer.v2.ETableAccessKind;
004import gudusoft.gsqlparser.ir.bound.*;
005
006import java.util.*;
007
008/**
009 * Call graph built from a {@link BoundProgram}.
010 * <p>
011 * Nodes represent routines; edges represent calls between routines.
012 * Table accesses are tracked per node. All traversal algorithms use
013 * iterative BFS (no recursion) to avoid stack overflow on deep graphs.
014 */
015public class CallGraph {
016
017    private final Map<String, CallGraphNode> nodes;
018    private final List<CallEdge> edges;
019    private final List<ExternalCallEdge> externalEdges;
020
021    // Adjacency lists for efficient queries
022    private final Map<String, List<CallEdge>> outgoing; // caller -> edges
023    private final Map<String, List<CallEdge>> incoming; // callee -> edges
024
025    private CallGraph() {
026        this.nodes = new LinkedHashMap<String, CallGraphNode>();
027        this.edges = new ArrayList<CallEdge>();
028        this.externalEdges = new ArrayList<ExternalCallEdge>();
029        this.outgoing = new HashMap<String, List<CallEdge>>();
030        this.incoming = new HashMap<String, List<CallEdge>>();
031    }
032
033    /**
034     * Builds a CallGraph from a BoundProgram.
035     */
036    public static CallGraph buildFrom(BoundProgram program) {
037        CallGraph graph = new CallGraph();
038
039        // Create nodes from routineIndex
040        for (Map.Entry<String, BoundRoutineSymbol> entry : program.getRoutineIndex().entrySet()) {
041            BoundRoutineSymbol sym = entry.getValue();
042            CallGraphNode node = new CallGraphNode(
043                    sym.getRoutineId(),
044                    sym.getRoutineName(),
045                    sym.getPackageName(),
046                    sym.getRoutineKind(),
047                    sym.getDeclarationAnchor());
048            graph.nodes.put(sym.getRoutineId(), node);
049        }
050
051        // Create edges from routine refs
052        for (BoundRoutineRef ref : program.getAllRoutineRefs()) {
053            String callerId = ref.getProperty("owningRoutineId");
054            if (callerId == null) {
055                continue;
056            }
057
058            // External dependency: create ExternalCallEdge, not a node
059            if (Boolean.TRUE.equals(ref.getProperty("externalDependency"))) {
060                String extName = ref.getProperty("externalName");
061                if (extName == null) extName = ref.getOriginalText();
062                String extType = ref.getProperty("externalType");
063                if (extType == null) extType = "BUILTIN_FUNCTION";
064                boolean secSensitive = Boolean.TRUE.equals(ref.getProperty("securitySensitive"));
065                graph.externalEdges.add(new ExternalCallEdge(
066                        callerId, extName, extType,
067                        ref.getSourceAnchor(), secSensitive));
068                continue;
069            }
070
071            String calleeId;
072            if (ref.getBindingStatus() == EBindingStatus.EXACT
073                    && ref.getResolvedRoutine() != null) {
074                calleeId = ref.getResolvedRoutine().getRoutineId();
075            } else {
076                // Create an external/unresolved node
077                calleeId = ref.getOriginalText();
078                if (!graph.nodes.containsKey(calleeId)) {
079                    CallGraphNode extNode = new CallGraphNode(
080                            calleeId, ref.getOriginalText(), null,
081                            ERoutineKind.PROCEDURE, null);
082                    graph.nodes.put(calleeId, extNode);
083                }
084            }
085
086            CallEdge edge = new CallEdge(
087                    callerId, calleeId,
088                    ref.getSourceAnchor(),
089                    ref.getEvidence(),
090                    ref.getConfidence());
091            graph.edges.add(edge);
092
093            if (!graph.outgoing.containsKey(callerId)) {
094                graph.outgoing.put(callerId, new ArrayList<CallEdge>());
095            }
096            graph.outgoing.get(callerId).add(edge);
097
098            if (!graph.incoming.containsKey(calleeId)) {
099                graph.incoming.put(calleeId, new ArrayList<CallEdge>());
100            }
101            graph.incoming.get(calleeId).add(edge);
102        }
103
104        // Assign table accesses from object refs
105        for (BoundObjectRef objRef : program.getAllObjectRefs()) {
106            String routineId = objRef.getProperty("owningRoutineId");
107            if (routineId == null) {
108                continue;
109            }
110            CallGraphNode node = graph.nodes.get(routineId);
111            if (node == null) {
112                continue;
113            }
114
115            ETableAccessKind accessKind = TableAccessExtractor.inferAccessKind(objRef);
116            node.addTableAccess(new TableAccess(
117                    objRef.getOriginalText(), accessKind, objRef.getSourceAnchor()));
118        }
119
120        return graph;
121    }
122
123    // ---- Query APIs ----
124
125    public Map<String, CallGraphNode> getNodes() {
126        return Collections.unmodifiableMap(nodes);
127    }
128
129    public List<CallEdge> getEdges() {
130        return Collections.unmodifiableList(edges);
131    }
132
133    public CallGraphNode getNode(String routineId) {
134        return nodes.get(routineId);
135    }
136
137    /**
138     * Returns the direct callees of the given routine.
139     */
140    public List<String> getDirectCallees(String routineId) {
141        List<CallEdge> out = outgoing.get(routineId);
142        if (out == null) {
143            return Collections.emptyList();
144        }
145        List<String> result = new ArrayList<String>();
146        for (CallEdge edge : out) {
147            if (!result.contains(edge.getCalleeRoutineId())) {
148                result.add(edge.getCalleeRoutineId());
149            }
150        }
151        return result;
152    }
153
154    /**
155     * Returns the direct callers of the given routine.
156     */
157    public List<String> getDirectCallers(String routineId) {
158        List<CallEdge> in = incoming.get(routineId);
159        if (in == null) {
160            return Collections.emptyList();
161        }
162        List<String> result = new ArrayList<String>();
163        for (CallEdge edge : in) {
164            if (!result.contains(edge.getCallerRoutineId())) {
165                result.add(edge.getCallerRoutineId());
166            }
167        }
168        return result;
169    }
170
171    /**
172     * Returns all transitively reachable callees using iterative BFS.
173     */
174    public Set<String> getTransitiveCallees(String routineId, int maxDepth) {
175        Set<String> visited = new LinkedHashSet<String>();
176        Deque<String> queue = new ArrayDeque<String>();
177        Map<String, Integer> depthMap = new HashMap<String, Integer>();
178
179        queue.add(routineId);
180        depthMap.put(routineId, 0);
181
182        while (!queue.isEmpty()) {
183            String current = queue.poll();
184            int currentDepth = depthMap.get(current);
185
186            if (currentDepth >= maxDepth) {
187                continue;
188            }
189
190            for (String callee : getDirectCallees(current)) {
191                if (!visited.contains(callee) && !callee.equals(routineId)) {
192                    visited.add(callee);
193                    if (!depthMap.containsKey(callee)) {
194                        depthMap.put(callee, currentDepth + 1);
195                        queue.add(callee);
196                    }
197                }
198            }
199        }
200        return visited;
201    }
202
203    /**
204     * Returns all transitive callers using iterative BFS.
205     */
206    public Set<String> getTransitiveCallers(String routineId, int maxDepth) {
207        Set<String> visited = new LinkedHashSet<String>();
208        Deque<String> queue = new ArrayDeque<String>();
209        Map<String, Integer> depthMap = new HashMap<String, Integer>();
210
211        queue.add(routineId);
212        depthMap.put(routineId, 0);
213
214        while (!queue.isEmpty()) {
215            String current = queue.poll();
216            int currentDepth = depthMap.get(current);
217
218            if (currentDepth >= maxDepth) {
219                continue;
220            }
221
222            for (String caller : getDirectCallers(current)) {
223                if (!visited.contains(caller) && !caller.equals(routineId)) {
224                    visited.add(caller);
225                    if (!depthMap.containsKey(caller)) {
226                        depthMap.put(caller, currentDepth + 1);
227                        queue.add(caller);
228                    }
229                }
230            }
231        }
232        return visited;
233    }
234
235    /**
236     * Finds all nodes that access a given table.
237     */
238    public List<CallGraphNode> getNodesAccessingTable(String tableName, ETableAccessKind filter) {
239        String normalizedSearch = TableAccessExtractor.normalizeTableName(tableName);
240        List<CallGraphNode> result = new ArrayList<CallGraphNode>();
241        for (CallGraphNode node : nodes.values()) {
242            for (TableAccess ta : node.getTableAccesses()) {
243                String normalizedTable = TableAccessExtractor.normalizeTableName(ta.getTableName());
244                if (normalizedTable.equals(normalizedSearch)) {
245                    if (filter == null || ta.getAccessKind() == filter
246                            || ta.getAccessKind() == ETableAccessKind.READ_WRITE) {
247                        result.add(node);
248                        break;
249                    }
250                }
251            }
252        }
253        return result;
254    }
255
256    // ---- External dependency APIs ----
257
258    /**
259     * Returns all external dependency edges.
260     */
261    public List<ExternalCallEdge> getExternalEdges() {
262        return Collections.unmodifiableList(externalEdges);
263    }
264
265    /**
266     * Returns external callees for a given routine.
267     */
268    public List<ExternalCallEdge> getExternalCallees(String routineId) {
269        List<ExternalCallEdge> result = new ArrayList<ExternalCallEdge>();
270        for (ExternalCallEdge edge : externalEdges) {
271            if (edge.getCallerRoutineId().equals(routineId)) {
272                result.add(edge);
273            }
274        }
275        return result;
276    }
277
278    /**
279     * Returns external callers of a given external name.
280     */
281    public List<ExternalCallEdge> getExternalCallers(String externalName) {
282        String upper = externalName.toUpperCase();
283        List<ExternalCallEdge> result = new ArrayList<ExternalCallEdge>();
284        for (ExternalCallEdge edge : externalEdges) {
285            if (edge.getExternalName().toUpperCase().equals(upper)) {
286                result.add(edge);
287            }
288        }
289        return result;
290    }
291
292    /**
293     * Returns a summary of external dependencies grouped by external name.
294     */
295    public Map<String, List<ExternalCallEdge>> getExternalDependencySummary() {
296        Map<String, List<ExternalCallEdge>> summary = new LinkedHashMap<String, List<ExternalCallEdge>>();
297        for (ExternalCallEdge edge : externalEdges) {
298            String key = edge.getExternalName().toUpperCase();
299            List<ExternalCallEdge> list = summary.get(key);
300            if (list == null) {
301                list = new ArrayList<ExternalCallEdge>();
302                summary.put(key, list);
303            }
304            list.add(edge);
305        }
306        return summary;
307    }
308
309}