Skip to content
CFGGraph.java 3.33 KiB
Newer Older
Javier Costa's avatar
Javier Costa committed
package tfm.graphs;
Javier Costa's avatar
Javier Costa committed

Javier Costa's avatar
Javier Costa committed
import com.github.javaparser.ast.Node;
import com.github.javaparser.ast.stmt.EmptyStmt;
Javier Costa's avatar
Javier Costa committed
import tfm.arcs.Arc;
Javier Costa's avatar
Javier Costa committed
import tfm.arcs.cfg.ControlFlowArc;
Javier Costa's avatar
Javier Costa committed
import tfm.nodes.GraphNode;
Javier Costa's avatar
Javier Costa committed
import tfm.slicing.SlicingCriterion;
Javier Costa's avatar
Javier Costa committed
import tfm.utils.NodeNotFoundException;
Javier Costa's avatar
Javier Costa committed

import java.util.Comparator;
Javier Costa's avatar
Javier Costa committed
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
Javier Costa's avatar
Javier Costa committed
import java.util.stream.Collectors;
Javier Costa's avatar
Javier Costa committed

public class CFGGraph extends GraphWithRootNode {
Javier Costa's avatar
Javier Costa committed

    public CFGGraph() {
        super();
    }

    @Override
    protected GraphNode<?> buildRootNode() {
        return new GraphNode<>(getNextVertexId(), "Start", new EmptyStmt());
Javier Costa's avatar
Javier Costa committed
    }

Javier Costa's avatar
Javier Costa committed
    public void addControlFlowEdge(GraphNode<?> from, GraphNode<?> to) {
        super.addEdge(from, to, new ControlFlowArc());
Javier Costa's avatar
Javier Costa committed
    }
Javier Costa's avatar
Javier Costa committed

    @Override
    public String toGraphvizRepresentation() {
        String lineSep = System.lineSeparator();

Javier Costa's avatar
Javier Costa committed
        String nodes = getNodes().stream()
Javier Costa's avatar
Javier Costa committed
                .sorted(Comparator.comparingInt(GraphNode::getId))
                .map(GraphNode::toGraphvizRepresentation)
Javier Costa's avatar
Javier Costa committed
                .collect(Collectors.joining(lineSep));

Javier Costa's avatar
Javier Costa committed
        String arrows =
Javier Costa's avatar
Javier Costa committed
                getArcs().stream()
                        .sorted(Comparator.comparingInt(arc -> this.getEdgeSource(arc).getId()))
                        .map(Arc::toGraphvizRepresentation)
Javier Costa's avatar
Javier Costa committed
                        .collect(Collectors.joining(lineSep));

        return "digraph g{" + lineSep +
Javier Costa's avatar
Javier Costa committed
                nodes + lineSep +
Javier Costa's avatar
Javier Costa committed
                arrows + lineSep +
                "}";
    }
Javier Costa's avatar
Javier Costa committed
    public Graph slice(SlicingCriterion slicingCriterion) {
Javier Costa's avatar
Javier Costa committed
        return this;
Javier Costa's avatar
Javier Costa committed

    public Set<GraphNode<?>> findLastDefinitionsFrom(GraphNode<?> startNode, String variable) {
//        Logger.log("=======================================================");
//        Logger.log("Starting from " + startNode);
//        Logger.log("Looking for variable " + variable);
//        Logger.log(cfgGraph.toString());
        
        if (!this.contains(startNode)) {
            throw new NodeNotFoundException(startNode, this);
        }
        
        return findLastDefinitionsFrom(new HashSet<>(), startNode, startNode, variable);
    }

    private Set<GraphNode<?>> findLastDefinitionsFrom(Set<Integer> visited, GraphNode<?> startNode, GraphNode<?> currentNode, String variable) {
        visited.add(currentNode.getId());

//        Logger.log("On " + currentNode);

        Set<GraphNode<?>> res = new HashSet<>();

Javier Costa's avatar
Javier Costa committed
        for (Arc arc : incomingEdgesOf(currentNode)) {
Javier Costa's avatar
Javier Costa committed
            ControlFlowArc controlFlowArc = (ControlFlowArc) arc;

Javier Costa's avatar
Javier Costa committed
            GraphNode<?> from = this.getEdgeSource(controlFlowArc);
Javier Costa's avatar
Javier Costa committed

//            Logger.log("Arrow from node: " + from);

            if (!Objects.equals(startNode, from) && visited.contains(from.getId())) {
//                Logger.log("It's already visited. Continuing...");
                continue;
            }

            if (from.getDefinedVariables().contains(variable)) {
//                Logger.log("Contains defined variable: " + variable);
                res.add(from);
            } else {
//                Logger.log("Doesn't contain the variable, searching inside it");
                res.addAll(findLastDefinitionsFrom(visited, startNode, from, variable));
            }
        }

//        Logger.format("Done with node %s", currentNode.getId());

        return res;
    }
Javier Costa's avatar
Javier Costa committed
}