Skip to content
CFG.java 3.92 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;
Javier Costa's avatar
Javier Costa committed
import com.github.javaparser.ast.stmt.EmptyStmt;
Javier Costa's avatar
Javier Costa committed
import edg.graphlib.Arrow;
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

/**
 * The <b>Control Flow Graph</b> represents the statements of a method in
 * a graph, displaying the connections between each statement and the ones that
 * may follow it. You can build one manually or use the {@link tfm.visitors.cfg.CFGBuilder CFGBuilder}.
 * The variations of the CFG are implemented as child classes.
 * @see ControlFlowArc
 */
public class CFG extends Graph {
Javier Costa's avatar
Javier Costa committed

    public CFG() {
Javier Costa's avatar
Javier Costa committed
        super();
Javier Costa's avatar
Javier Costa committed
        setRootVertex(new GraphNode<>(getNextVertexId(), getRootNodeData(), new EmptyStmt()));
Javier Costa's avatar
Javier Costa committed
    }

    @Override
Javier Costa's avatar
Javier Costa committed
    public <ASTNode extends Node> GraphNode<ASTNode> addNode(String instruction, ASTNode node) {
        GraphNode<ASTNode> vertex = new GraphNode<>(getNextVertexId(), instruction, node);
Javier Costa's avatar
Javier Costa committed
        this.addVertex(vertex);

        return vertex;
    }

Javier Costa's avatar
Javier Costa committed

    protected String getRootNodeData() {
        return "Start";
    }
Javier Costa's avatar
Javier Costa committed

    public void addControlFlowEdge(GraphNode<?> from, GraphNode<?> to) {
        addControlFlowEdge(from, to, true);
    }

Javier Costa's avatar
Javier Costa committed
    @SuppressWarnings("unchecked")
    protected void addControlFlowEdge(GraphNode<?> from, GraphNode<?> to, boolean executable) {
        if (executable)
            super.addEdge((Arrow) new ControlFlowArc(from, to));
        else
            super.addEdge((Arrow) new ControlFlowArc.NonExecutable(from, to));
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 =
                getArrows().stream()
                        .sorted(Comparator.comparingInt(arrow -> ((GraphNode<?>) arrow.getFrom()).getId()))
                        .map(arrow -> ((Arc<?>) arrow).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 Set<GraphNode<?>> findLastDefinitionsFrom(GraphNode<?> startNode, String variable) {
        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());
        Set<GraphNode<?>> res = new HashSet<>();

        for (Arc<?> arc : currentNode.getIncomingArcs()) {
            ControlFlowArc controlFlowArc = (ControlFlowArc) arc;
            // Ignore non-executable edges when computing data dependence.
            if (arc instanceof ControlFlowArc.NonExecutable)
                continue;
Javier Costa's avatar
Javier Costa committed

            GraphNode<?> from = controlFlowArc.getFromNode();

            if (!Objects.equals(startNode, from) && visited.contains(from.getId())) {
                continue;
            }

            if (from.getDefinedVariables().contains(variable)) {
                res.add(from);
            } else {
                res.addAll(findLastDefinitionsFrom(visited, startNode, from, variable));
            }
        }

        return res;
    }

    public static class ACFG extends CFG {
        public void addNonExecutableControlFlowEdge(GraphNode<?> from, GraphNode<?> to) {
            addControlFlowEdge(from, to, false);
        }
    }
Javier Costa's avatar
Javier Costa committed
}