chord.analyses.alias
Class CSCG

java.lang.Object
  chord.util.graph.AbstractGraph<Pair<Ctxt,joeq.Class.jq_Method>>
      chord.analyses.alias.CSCG

All Implemented Interfaces:

ICSCG, IGraph<Pair<Ctxt,joeq.Class.jq_Method>>, ILabeledGraph<Pair<Ctxt,joeq.Class.jq_Method>,joeq.Compiler.Quad.Quad>, java.io.Serializable

public class CSCG
extends AbstractGraph<Pair<Ctxt,joeq.Class.jq_Method>>
implements ICSCG

Implementation of a context-sensitive call graph.

Author:

Mayur Naik (mhn@cs.stanford.edu)

See Also:

Serialized Form

Field Summary

protected DomM	domM
protected ProgramRel	relCICM
protected ProgramRel	relCMCM
protected ProgramRel	relReachableCM
protected ProgramRel	relRootCM

Fields inherited from class chord.util.graph.AbstractGraph

cached

Constructor Summary

CSCG(DomM domM, ProgramRel relRootCM, ProgramRel relReachableCM, ProgramRel relCICM, ProgramRel relCMCM)

Method Summary

boolean	calls(Ctxt origCtxt, joeq.Compiler.Quad.Quad origInvk, Ctxt destCtxt, joeq.Class.jq_Method destMeth) /** Determines whether a given jq_Method invocation site in a given abstract context may call a given jq_Method in a given abstract context.
void	free() Frees relations used by this call graph if they are in memory.
java.util.Set<Pair<Ctxt,joeq.Compiler.Quad.Quad>>	getCallers(Ctxt ctxt, joeq.Class.jq_Method meth) Provides each jq_Method invocation site along with each abstract context from which it may call a given jq_Method in a given abstract context.
java.util.Set<Ctxt>	getContexts(joeq.Class.jq_Method jq_Method) Provides the set of all abstract contexts in which a given method may be reachable.
java.util.Set<joeq.Compiler.Quad.Quad>	getLabels(Pair<Ctxt,joeq.Class.jq_Method> origNode, Pair<Ctxt,joeq.Class.jq_Method> destNode) Provides the set of all labels on a given directed edge in the graph.
java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>>	getNodes() Provides all nodes in this graph.
java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>>	getPreds(Pair<Ctxt,joeq.Class.jq_Method> cm) Provides all immediate predecessors of a given node in this graph.
java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>>	getRoots() Provides all root nodes of this graph.
java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>>	getSuccs(Pair<Ctxt,joeq.Class.jq_Method> cm) Provides all immediate successors of a given node in this graph.
java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>>	getTargets(Ctxt ctxt, joeq.Compiler.Quad.Quad invk) Provides the set containing each method along with each abstract context in which it may be called by a given call site in a given abstract context.
boolean	hasEdge(Pair<Ctxt,joeq.Class.jq_Method> node1, Pair<Ctxt,joeq.Class.jq_Method> node2) Determines whether this graph contains a given directed edge.
boolean	hasNode(Pair<Ctxt,joeq.Class.jq_Method> node) Determines whether this graph contains a given node.
boolean	hasRoot(Pair<Ctxt,joeq.Class.jq_Method> node) Determines whether this graph contains a given node as a root node.
int	numNodes() Provides the total number of nodes in this graph.
int	numPreds(Pair<Ctxt,joeq.Class.jq_Method> node) Provides the number of immediate predecessors of a given node in this graph.
int	numRoots() Provides the total number of roots of this graph.
int	numSuccs(Pair<Ctxt,joeq.Class.jq_Method> node) Provides the number of immediate successors of a given node in this graph.

Methods inherited from class chord.util.graph.AbstractGraph

equals, evictCache, getAllPathsBuilder, getBackEdges, getNodeMap, getNodesInCycles, getNodesInRPO, getShortestPathsBuilder, getSimpleCycles, getTopSortedSCCs, hasCycles, hashCode, isConnected, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface chord.util.graph.IGraph

getAllPathsBuilder, getBackEdges, getNodeMap, getNodesInCycles, getNodesInRPO, getShortestPathsBuilder, getSimpleCycles, getTopSortedSCCs, hasCycles, isConnected

Field Detail

domM

protected DomM domM

relRootCM

protected ProgramRel relRootCM

relReachableCM

protected ProgramRel relReachableCM

relCICM

protected ProgramRel relCICM

relCMCM

protected ProgramRel relCMCM

Constructor Detail

CSCG

public CSCG(DomM domM,
            ProgramRel relRootCM,
            ProgramRel relReachableCM,
            ProgramRel relCICM,
            ProgramRel relCMCM)

Method Detail

getNodes

public java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>> getNodes()

Description copied from interface: IGraph

Provides all nodes in this graph.

Specified by:

getNodes in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Returns:

All nodes in this graph.

getRoots

public java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>> getRoots()

Description copied from interface: IGraph

Provides all root nodes of this graph.

Specified by:

getRoots in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Returns:

All root nodes of this graph.

getPreds

public java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>> getPreds(Pair<Ctxt,joeq.Class.jq_Method> cm)

Description copied from interface: IGraph

Provides all immediate predecessors of a given node in this graph.

Specified by:

getPreds in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

cm - A node.

Returns:

All immediate predecessors of the given node.

getSuccs

public java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>> getSuccs(Pair<Ctxt,joeq.Class.jq_Method> cm)

Description copied from interface: IGraph

Provides all immediate successors of a given node in this graph.

Specified by:

getSuccs in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

cm - A node.

Returns:

All immediate successors of the given node.

hasNode

public boolean hasNode(Pair<Ctxt,joeq.Class.jq_Method> node)

Description copied from interface: IGraph

Determines whether this graph contains a given node.

Specified by:

hasNode in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

node - A node.

Returns:

true if this graph contains the given node.

hasRoot

public boolean hasRoot(Pair<Ctxt,joeq.Class.jq_Method> node)

Description copied from interface: IGraph

Determines whether this graph contains a given node as a root node.

Specified by:

hasRoot in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

node - A node.

Returns:

true if this graph contains the given node as a root node.

numSuccs

public int numSuccs(Pair<Ctxt,joeq.Class.jq_Method> node)

Description copied from interface: IGraph

Provides the number of immediate successors of a given node in this graph.

Specified by:

numSuccs in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

node - A node.

Returns:

The number of immediate successors of the given node, if it exists in this graph, and 0 otherwise.

getContexts

public java.util.Set<Ctxt> getContexts(joeq.Class.jq_Method jq_Method)

Description copied from interface: ICSCG

Provides the set of all abstract contexts in which a given method may be reachable.

Specified by:

getContexts in interface ICSCG

Parameters:

jq_Method - A method.

Returns:

The set of all abstract contexts in which method meth may be reachable.

getCallers

public java.util.Set<Pair<Ctxt,joeq.Compiler.Quad.Quad>> getCallers(Ctxt ctxt,
                                                                    joeq.Class.jq_Method meth)

Description copied from interface: ICSCG

Provides each jq_Method invocation site along with each abstract context from which it may call a given jq_Method in a given abstract context.

Specified by:

getCallers in interface ICSCG

Parameters:

ctxt - An abstract context.

meth - A jq_Method.

Returns:

All (ctxt2, invk) pairs such that jq_Method invocation site invk in abstract context ctxt2 may call jq_Method meth in abstract context ctxt.

getTargets

public java.util.Set<Pair<Ctxt,joeq.Class.jq_Method>> getTargets(Ctxt ctxt,
                                                                 joeq.Compiler.Quad.Quad invk)

Description copied from interface: ICSCG

Provides the set containing each method along with each abstract context in which it may be called by a given call site in a given abstract context.

Specified by:

getTargets in interface ICSCG

Parameters:

ctxt - An abstract context.

invk - A call site.

Returns:

All (ctxt2, meth) pairs such that jq_Method meth may be called in abstract context ctxt2 from jq_Method invocation site invk in abstract context ctxt.

getLabels

public java.util.Set<joeq.Compiler.Quad.Quad> getLabels(Pair<Ctxt,joeq.Class.jq_Method> origNode,
                                                        Pair<Ctxt,joeq.Class.jq_Method> destNode)

Description copied from interface: ILabeledGraph

Provides the set of all labels on a given directed edge in the graph.

Specified by:

getLabels in interface ILabeledGraph<Pair<Ctxt,joeq.Class.jq_Method>,joeq.Compiler.Quad.Quad>

Parameters:

origNode - The source node of the edge.

destNode - The target node of the edge.

Returns:

The set of all labels on the edge from srcNode to dstNode in the graph. It is the empty set if either node does not exist, the edge does not exist, or no labels exist on the edge in the graph.

hasEdge

public boolean hasEdge(Pair<Ctxt,joeq.Class.jq_Method> node1,
                       Pair<Ctxt,joeq.Class.jq_Method> node2)

Description copied from interface: IGraph

Determines whether this graph contains a given directed edge.

Specified by:

hasEdge in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

node1 - A node.

node2 - A node.

Returns:

true if this graph contains a directed edge from node1 to node2.

numRoots

public int numRoots()

Description copied from interface: IGraph

Provides the total number of roots of this graph.

Specified by:

numRoots in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Returns:

The total number of roots of this graph.

numNodes

public int numNodes()

Description copied from interface: IGraph

Provides the total number of nodes in this graph.

Specified by:

numNodes in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Returns:

The total number of nodes in this graph.

numPreds

public int numPreds(Pair<Ctxt,joeq.Class.jq_Method> node)

Description copied from interface: IGraph

Provides the number of immediate predecessors of a given node in this graph.

Specified by:

numPreds in interface IGraph<Pair<Ctxt,joeq.Class.jq_Method>>

Parameters:

node - A node.

Returns:

The number of immediate predecessors of the given node, if it exists in this graph, and 0 otherwise.

calls

public boolean calls(Ctxt origCtxt,
                     joeq.Compiler.Quad.Quad origInvk,
                     Ctxt destCtxt,
                     joeq.Class.jq_Method destMeth)

Description copied from interface: ICSCG

/** Determines whether a given jq_Method invocation site in a given abstract context may call a given jq_Method in a given abstract context.

Specified by:

calls in interface ICSCG

Parameters:

origCtxt - An abstract context.

origInvk - A jq_Method invocation site.

destCtxt - An abstract context.

destMeth - A jq_Method.

Returns:

true iff jq_Method invocation site invk in abstract context ctxt1 may call jq_Method meth in abstract context ctxt2.

free

public void free()

Frees relations used by this call graph if they are in memory.

This jq_Method must be called after clients are done exercising the interface of this call graph.