Package com.tonic.analysis.pdg.slice

Class PDGSlicer

  • public class PDGSlicer
extends Object
    Intraprocedural slicer over a program dependence graph.

    • Constructor Detail

      • PDGSlicer

        public PDGSlicer​(PDG pdg)
        Creates a slicer following both control and data dependences.
        Parameters:
        pdg - the graph to slice

    • Method Detail

      • getPdg

        public PDG getPdg()
        Returns:
        the pdg

      • isIncludeControlDependencies

        public boolean isIncludeControlDependencies()
        Returns:
        whether include control dependencies

      • isIncludeDataDependencies

        public boolean isIncludeDataDependencies()
        Returns:
        whether include data dependencies

      • withControlDependencies

        public PDGSlicer withControlDependencies​(boolean include)
        Sets whether control dependence edges are traversed.
        Parameters:
        include - whether to follow control dependences
        Returns:
        this slicer

      • withDataDependencies

        public PDGSlicer withDataDependencies​(boolean include)
        Sets whether data dependence edges are traversed.
        Parameters:
        include - whether to follow data dependences
        Returns:
        this slicer

      • backwardSlice

        public SliceResult backwardSlice​(PDGNode criterion)
        Slices backwards from a single node.
        Parameters:
        criterion - the slicing criterion, may be null
        Returns:
        the nodes and edges that can affect the criterion, empty if it is null

      • backwardSlice

        public SliceResult backwardSlice​(Set<PDGNode> criterion)
        Walks incoming edges transitively from every criterion node.
        Parameters:
        criterion - the slicing criteria
        Returns:
        the nodes and edges that can affect the criteria

      • forwardSlice

        public SliceResult forwardSlice​(PDGNode criterion)
        Slices forwards from a single node.
        Parameters:
        criterion - the slicing criterion
        Returns:
        the nodes and edges the criterion can affect

      • forwardSlice

        public SliceResult forwardSlice​(Set<PDGNode> criterion)
        Walks outgoing edges transitively from every criterion node.
        Parameters:
        criterion - the slicing criteria
        Returns:
        the nodes and edges the criteria can affect

      • chop

        public SliceResult chop​(PDGNode source,
                        PDGNode sink)
        Intersects the forward slice of a source with the backward slice of a sink.
        Parameters:
        source - the node to slice forward from
        sink - the node to slice backward from
        Returns:
        the nodes on some dependence path from source to sink

      • chop

        public SliceResult chop​(Set<PDGNode> sources,
                        Set<PDGNode> sinks)
        Intersects the forward slice of the sources with the backward slice of the sinks.
        Parameters:
        sources - the nodes to slice forward from
        sinks - the nodes to slice backward from
        Returns:
        the nodes on some dependence path from a source to a sink

      • backwardSliceWithFilter

        public SliceResult backwardSliceWithFilter​(PDGNode criterion,
                                           Predicate<PDGNode> filter)
        Slices backwards, stopping the walk at any node the filter rejects.
        Parameters:
        criterion - the slicing criterion
        filter - predicate a node must satisfy to be kept and traversed through
        Returns:
        the accepted nodes and the edges between them

      • forwardSliceWithFilter

        public SliceResult forwardSliceWithFilter​(PDGNode criterion,
                                          Predicate<PDGNode> filter)
        Slices forwards, stopping the walk at any node the filter rejects.
        Parameters:
        criterion - the slicing criterion
        filter - predicate a node must satisfy to be kept and traversed through
        Returns:
        the accepted nodes and the edges between them

      • backwardSliceControlOnly

        public SliceResult backwardSliceControlOnly​(PDGNode criterion)
        Slices backwards over control dependences only, leaving this slicer's settings untouched.
        Parameters:
        criterion - the slicing criterion
        Returns:
        the control-only backward slice

      • backwardSliceDataOnly

        public SliceResult backwardSliceDataOnly​(PDGNode criterion)
        Slices backwards over data dependences only, leaving this slicer's settings untouched.
        Parameters:
        criterion - the slicing criterion
        Returns:
        the data-only backward slice

      • forwardSliceControlOnly

        public SliceResult forwardSliceControlOnly​(PDGNode criterion)
        Slices forwards over control dependences only, leaving this slicer's settings untouched.
        Parameters:
        criterion - the slicing criterion
        Returns:
        the control-only forward slice

      • forwardSliceDataOnly

        public SliceResult forwardSliceDataOnly​(PDGNode criterion)
        Slices forwards over data dependences only, leaving this slicer's settings untouched.
        Parameters:
        criterion - the slicing criterion
        Returns:
        the data-only forward slice

      • findAllPaths

        public List<List<PDGNode>> findAllPaths​(PDGNode source,
                                        PDGNode target,
                                        int maxDepth)
        Enumerates the simple dependence paths from source to target by depth-first search.
        Parameters:
        source - the start node
        target - the end node
        maxDepth - the maximum number of edges a path may use
        Returns:
        every path found, each as a node list from source to target

      • isReachable

        public boolean isReachable​(PDGNode source,
                           PDGNode target)
        Tests whether target appears in the forward slice of source.
        Parameters:
        source - the start node
        target - the node to look for
        Returns:
        whether a dependence path runs from source to target