Skip to content
PDGGraph.java 8.34 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.body.MethodDeclaration;
Javier Costa's avatar
Javier Costa committed
import com.github.javaparser.ast.stmt.EmptyStmt;
import edg.graphlib.Arrow;
Javier Costa's avatar
Javier Costa committed
import org.jetbrains.annotations.NotNull;
Javier Costa's avatar
Javier Costa committed
import tfm.arcs.Arc;
import tfm.arcs.pdg.ControlDependencyArc;
import tfm.arcs.pdg.DataDependencyArc;
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.ASTUtils;
import tfm.utils.Logger;
Javier Costa's avatar
Javier Costa committed
import tfm.utils.NodeNotFoundException;
import tfm.visitors.pdg.PDGBuilder;
Javier Costa's avatar
Javier Costa committed

Javier Costa's avatar
Javier Costa committed
import java.util.Comparator;
import java.util.HashSet;
import java.util.Optional;
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 PDGGraph extends Graph {
Javier Costa's avatar
Javier Costa committed

Javier Costa's avatar
Javier Costa committed
    private CFGGraph cfgGraph;

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

Javier Costa's avatar
Javier Costa committed
    public PDGGraph(CFGGraph cfgGraph) {
        this();
        this.cfgGraph = cfgGraph;
    }

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

Javier Costa's avatar
Javier Costa committed
    public GraphNode addNode(GraphNode<?> node) {
        GraphNode<?> vertex = new GraphNode<>(node);
Javier Costa's avatar
Javier Costa committed
        super.addVertex(vertex);

        return vertex;
    }

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) {
Javier Costa's avatar
Javier Costa committed
        return addNode(getNextVertexId(), instruction, node);
Javier Costa's avatar
Javier Costa committed
    }

Javier Costa's avatar
Javier Costa committed
    public <ASTNode extends Node> GraphNode<ASTNode> addNode(int id, String instruction, ASTNode node) {
        GraphNode<ASTNode> vertex = new GraphNode<>(id, instruction, node);
Javier Costa's avatar
Javier Costa committed
        super.addVertex(vertex);

        return vertex;
    }

    @SuppressWarnings("unchecked")
    private void addArc(Arc arc) {
        super.addEdge(arc);
    }

Javier Costa's avatar
Javier Costa committed
    public void addControlDependencyArc(GraphNode from, GraphNode to) {
Javier Costa's avatar
Javier Costa committed
        ControlDependencyArc controlDependencyArc = new ControlDependencyArc(from, to);

        this.addArc(controlDependencyArc);
    }

Javier Costa's avatar
Javier Costa committed
    public void addDataDependencyArc(GraphNode from, GraphNode to, String variable) {
Javier Costa's avatar
Javier Costa committed
        DataDependencyArc dataDataDependencyArc = new DataDependencyArc(from, to, variable);

        this.addArc(dataDataDependencyArc);
    }

Javier Costa's avatar
Javier Costa committed
    public Set<GraphNode> getNodesAtLevel(int level) {
Javier Costa's avatar
Javier Costa committed
        return getVerticies().stream()
Javier Costa's avatar
Javier Costa committed
                .map(vertex -> (GraphNode) vertex)
                .filter(node -> getLevelOf(node) == level)
Javier Costa's avatar
Javier Costa committed
                .collect(Collectors.toSet());
Javier Costa's avatar
Javier Costa committed
    }

    public int getLevels() {
        return getVerticies().stream()
Javier Costa's avatar
Javier Costa committed
                .map(vertex -> (GraphNode) vertex)
                .max(Comparator.comparingInt(this::getLevelOf))
                .map(node -> getLevelOf(node) + 1)
                .orElse(0);
    }

    public int getLevelOf(int nodeId) {
        return findNodeById(nodeId)
                .map(this::getLevelOf)
                .orElseThrow(() -> new NodeNotFoundException("Node with id " + nodeId + " not found in PDG graph"));
    }

    public int getLevelOf(@NotNull GraphNode<?> node) {
        Optional<ControlDependencyArc> optionalControlDependencyArc = node.getIncomingArcs().stream()
                .filter(Arc::isControlDependencyArrow)
                .findFirst()
                .map(arc -> (ControlDependencyArc) arc);

        if (!optionalControlDependencyArc.isPresent()) {
            return 0;
        }

        GraphNode<?> parent = optionalControlDependencyArc.get().getFromNode();

        return 1 + getLevelOf(parent);
Javier Costa's avatar
Javier Costa committed
    public void setCfgGraph(CFGGraph cfgGraph) {
        this.cfgGraph = cfgGraph;
    }

Javier Costa's avatar
Javier Costa committed
    @Override
    public String toGraphvizRepresentation() {
        String lineSep = System.lineSeparator();

Javier Costa's avatar
Javier Costa committed
        String nodesDeclaration = 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
        StringBuilder rankedNodes = new StringBuilder();

        // No level 0 is needed (only one node)
        for (int i = 0; i < getLevels(); i++) {
Javier Costa's avatar
Javier Costa committed
            Set<GraphNode> levelNodes = getNodesAtLevel(i);
Javier Costa's avatar
Javier Costa committed

            if (levelNodes.size() <= 1) {
                continue;
            }

            // rank same
            rankedNodes.append("{ rank = same; ")
                    .append(levelNodes.stream()
                        .map(node -> String.valueOf(node.getId()))
                        .collect(Collectors.joining(";")))
                    .append(" }")
                    .append(lineSep);

            // invisible arrows for ordering
            rankedNodes.append(levelNodes.stream()
Javier Costa's avatar
Javier Costa committed
                        .sorted(Comparator.comparingInt(GraphNode::getId))
Javier Costa's avatar
Javier Costa committed
                        .map(node -> String.valueOf(node.getId()))
                        .collect(Collectors.joining(" -> ")))
                    .append("[style = invis];")
                    .append(lineSep);
        }

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


        return "digraph g{" + lineSep +
                "splines=true;" + lineSep +
                nodesDeclaration + lineSep +
                arrows + lineSep +
                rankedNodes.toString() +
Javier Costa's avatar
Javier Costa committed
                "}";
    }
Javier Costa's avatar
Javier Costa committed
    public PDGGraph slice(SlicingCriterion slicingCriterion) {
Javier Costa's avatar
Javier Costa committed
        Optional<GraphNode<?>> optionalGraphNode = slicingCriterion.findNode(this);
Javier Costa's avatar
Javier Costa committed
        if (!optionalGraphNode.isPresent()) {
Javier Costa's avatar
Javier Costa committed
            throw new NodeNotFoundException(slicingCriterion);
        }
Javier Costa's avatar
Javier Costa committed
        GraphNode node = optionalGraphNode.get();
Javier Costa's avatar
Javier Costa committed
//        // DEPRECATED - Find CFGNode and find last definition of variable
//        CFGNode cfgNode = this.cfgGraph.findNodeByASTNode(node.getAstNode())
//                .orElseThrow(() -> new NodeNotFoundException("CFGNode not found"));
//
//        Set<CFGNode<?>> definitionNodes = Utils.findLastDefinitionsFrom(cfgNode, slicingCriterion.getVariable());
//
//        Logger.format("Slicing node: %s", node);
//
//        // Get slice nodes from definition nodes
//        Set<Integer> sliceNodes = definitionNodes.stream()
//                .flatMap(definitionNode -> getSliceNodes(new HashSet<>(), this.findNodeByASTNode(definitionNode.getAstNode()).get()).stream())
//                .collect(Collectors.toSet());
//
//        sliceNodes.add(node.getId());
Javier Costa's avatar
Javier Costa committed
        // Simply get slice nodes from GraphNode
Javier Costa's avatar
Javier Costa committed
        Set<Integer> sliceNodes = getSliceNodes(new HashSet<>(), node);
Javier Costa's avatar
Javier Costa committed
        PDGGraph sliceGraph = new PDGGraph();

Javier Costa's avatar
Javier Costa committed
        Node astCopy = ASTUtils.cloneAST(node.getAstNode());
Javier Costa's avatar
Javier Costa committed

        astCopy.accept(new PDGBuilder(sliceGraph), sliceGraph.getRootNode());
Javier Costa's avatar
Javier Costa committed
        for (GraphNode sliceNode : sliceGraph.getNodes()) {
Javier Costa's avatar
Javier Costa committed
            if (!sliceNodes.contains(sliceNode.getId())) {
Javier Costa's avatar
Javier Costa committed
                Logger.log("Removing node " + sliceNode.getId());
Javier Costa's avatar
Javier Costa committed
                sliceNode.getAstNode().removeForced();
Javier Costa's avatar
Javier Costa committed
                sliceGraph.removeNode(sliceNode);
Javier Costa's avatar
Javier Costa committed
            }
Javier Costa's avatar
Javier Costa committed
//        for (Arc arc : getArcs()) {
Javier Costa's avatar
Javier Costa committed
//            Optional<GraphNode> fromOptional = sliceGraph.findNodeById(arc.getFromNode().getId());
//            Optional<GraphNode> toOptional = sliceGraph.findNodeById(arc.getToNode().getId());
Javier Costa's avatar
Javier Costa committed
//
//            if (fromOptional.isPresent() && toOptional.isPresent()) {
Javier Costa's avatar
Javier Costa committed
//                GraphNode from = fromOptional.get();
//                GraphNode to = toOptional.get();
Javier Costa's avatar
Javier Costa committed
//
//                if (arc.isControlDependencyArrow()) {
//                    sliceGraph.addControlDependencyArc(from, to);
//                } else {
//                    DataDependencyArc dataDependencyArc = (DataDependencyArc) arc;
//                    sliceGraph.addDataDependencyArc(from, to, dataDependencyArc.getData().getVariables().get(0));
//                }
//            }
//        }
Javier Costa's avatar
Javier Costa committed

        return sliceGraph;
Javier Costa's avatar
Javier Costa committed
    private Set<Integer> getSliceNodes(Set<Integer> visited, GraphNode<?> root) {
Javier Costa's avatar
Javier Costa committed
        visited.add(root.getId());

Javier Costa's avatar
Javier Costa committed
        for (Arrow arrow : root.getIncomingArcs()) {
            Arc arc = (Arc) arrow;

Javier Costa's avatar
Javier Costa committed
            GraphNode<?> from = (GraphNode) arc.getFromNode();
Javier Costa's avatar
Javier Costa committed
            if (visited.contains(from.getId())) {
                continue;
            }

            getSliceNodes(visited, from);
        }

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

    public CFGGraph getCfgGraph() {
        return cfgGraph;
    }
Javier Costa's avatar
Javier Costa committed
}