vasco
Class ContextTransitionTable<M,N,A>

java.lang.Object
  vasco.ContextTransitionTable<M,N,A>

Type Parameters:

M - the type of a method

N - the type of a node in the CFG

A - the type of a data flow value

public class ContextTransitionTable<M,N,A>
extends Object

A record of transitions between contexts at call-sites.

The context transition table records a bidirectional one-to-many mapping of call-sites to called contexts parameterised by their methods.

If a call-site transition is not traversed in an analysis (e.g. a call to a native method) then it is listed as a "default site" which this table also records.

Author:

Rohan Padhye

Field Summary

protected Map<Context<M,N,A>,Set<CallSite<M,N,A>>>	callers A map from contexts to a set of call-sites that transition to it.
protected Map<Context<M,N,A>,Set<CallSite<M,N,A>>>	callSitesOfContexts A map of contexts to call-sites present within their method bodies.
protected Set<CallSite<M,N,A>>	defaultCallSites A set of call-sites from which transitions are unknown.
protected Map<CallSite<M,N,A>,Map<M,Context<M,N,A>>>	transitions A map from call-sites to contexts, parameterised by the called method.

Constructor Summary

ContextTransitionTable()
Constructs a new context transition table with no initial entries.

Method Summary

void	addTransition(CallSite<M,N,A> callSite, Context<M,N,A> targetContext) Adds a transition to the table.
Map<Context<M,N,A>,Set<CallSite<M,N,A>>>	getCallers() Returns an unmodifiable view of the mapping from contexts to their callers.
Set<CallSite<M,N,A>>	getCallers(Context<M,N,A> target) Returns the callers of a value context.
Map<Context<M,N,A>,Set<CallSite<M,N,A>>>	getCallSitesOfContexts() Returns an unmodifiable view of a mapping from calling contexts to all their call-sites.
Set<CallSite<M,N,A>>	getDefaultCallSites() Returns an unmodifiable view of the set of call-sites marked "default".
Map<M,Context<M,N,A>>	getTargets(CallSite<M,N,A> callSite) Returns the targets of a call-site.
Map<CallSite<M,N,A>,Map<M,Context<M,N,A>>>	getTransitions() Returns an unmodifiable view of context transitions.
Set<Context<M,N,A>>	reachableSet(Context<M,N,A> source, boolean ignoreFree) Computes a reachable set of value contexts from a particular source by traversing the context transition table.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

callers

protected Map<Context<M,N,A>,Set<CallSite<M,N,A>>> callers

A map from contexts to a set of call-sites that transition to it.

transitions

protected Map<CallSite<M,N,A>,Map<M,Context<M,N,A>>> transitions

A map from call-sites to contexts, parameterised by the called method.

callSitesOfContexts

protected Map<Context<M,N,A>,Set<CallSite<M,N,A>>> callSitesOfContexts

A map of contexts to call-sites present within their method bodies.

defaultCallSites

protected Set<CallSite<M,N,A>> defaultCallSites

A set of call-sites from which transitions are unknown.

Constructor Detail

ContextTransitionTable

public ContextTransitionTable()

Constructs a new context transition table with no initial entries.

Method Detail

addTransition

public void addTransition(CallSite<M,N,A> callSite,
                          Context<M,N,A> targetContext)

Adds a transition to the table.

If the target context is specified as null, the source call-site is considered a "default site" from which transitions are unknown. This is used to model unpredictable targets, for example, when encountering calls to native methods.

Any previous transitions from the source call site to other contexts of the same called method are deleted.

Parameters:

callSite - the call-site which is the source of the transition

targetContext - the value context which is the target of the call-site

getCallers

public Map<Context<M,N,A>,Set<CallSite<M,N,A>>> getCallers()

Returns an unmodifiable view of the mapping from contexts to their callers.

Returns:

an unmodifiable view of the mapping from contexts to their callers

getCallers

public Set<CallSite<M,N,A>> getCallers(Context<M,N,A> target)

Returns the callers of a value context.

Parameters:

target - the target value context

Returns:

a set of call-sites which transition to the given target context

getCallSitesOfContexts

public Map<Context<M,N,A>,Set<CallSite<M,N,A>>> getCallSitesOfContexts()

Returns an unmodifiable view of a mapping from calling contexts to all their call-sites.

Returns:

an unmodifiable view of a mapping from calling contexts to all their call-sites

getDefaultCallSites

public Set<CallSite<M,N,A>> getDefaultCallSites()

Returns an unmodifiable view of the set of call-sites marked "default".

Returns:

an unmodifiable view of the set of call-sites marked "default"

getTargets

public Map<M,Context<M,N,A>> getTargets(CallSite<M,N,A> callSite)

Returns the targets of a call-site.

Parameters:

callSite - the source of the transition

Returns:

a map of target methods to target contexts

getTransitions

public Map<CallSite<M,N,A>,Map<M,Context<M,N,A>>> getTransitions()

Returns an unmodifiable view of context transitions.

Returns:

an unmodifiable view of context transitions

reachableSet

public Set<Context<M,N,A>> reachableSet(Context<M,N,A> source,
                                        boolean ignoreFree)

Computes a reachable set of value contexts from a particular source by traversing the context transition table. Note that the source context itself is only reachable from itself if it there is a recursive call to it (i.e. a context is not reachable to itself by default).

Parameters:

source - the source context

Returns:

a set of contexts reachable from source