soot.jimple.toolkits.annotation.purity

Class PurityGraph

java.lang.Object

soot.jimple.toolkits.annotation.purity.PurityGraph

public class PurityGraph
extends java.lang.Object

Modifications with respect to the article: - "unanalizable call" are treated by first constructing a conservative calee graph where all parameters escape globally and return points to the global node, and then applying the standard analysable call construction - unanalysable calls add a mutation on the global node; the "field" is named "outside-world" and models the mutation of any static field, but also side-effects by native methods, such as I/O, that make methods impure (see below). - Whenever a method mutates the global node, it is marked as "impure" (this can be due to a side-effect or static field mutation), even if the global node is not rechable from parameter nodes through outside edges. It seems to me it was a defect from the article ? TODO: see if we must take the global node into account also when stating whether a parameter is read-only or safe. - "simplifyXXX" functions are experimental... they may be unsound, and thus, not used now. NOTE: A lot of precision degradation comes from sequences of the form this.field = y; z = this.field in initialisers: the second statement creates a load node because, as a parameter, this may have escaped and this.field may be externally modified in-between the two instructions. I am not sure this can actually happend in an initialiser... in a a function called directly and only by initialisers. For the moment, summary of unanalised methods are either pure, completely impure (modify args & side-effects) or partially impure (modify args but not the gloal node). We should really be able to specify more precisely which arguments are r/o or safe within this methods. E.g., the analysis java.lang.String: void getChars(int,int,char [],int) imprecisely finds that this is not safe (because of the internal call to System.arraycopy that, in general, may introduce aliases) => it pollutes many things (e.g., StringBuffer append(String), and thus, exception constructors, etc.)

Field Summary

Fields

Modifier and Type	Field and Description
protected MultiMap	backEdges
protected MultiMap	backLocals
static boolean	doCheck
protected MultiMap	edges
protected java.util.Set	globEscape
protected MultiMap	locals
protected MultiMap	mutated
protected java.util.Set	nodes
protected java.util.Set	paramNodes
protected java.util.Set	ret

Method Summary

Modifier and Type	Method and Description
java.lang.Object	clone()
static PurityGraph	conservativeGraph(SootMethod m, boolean withEffect) Conservative constructor for unanalysable calls.
boolean	equals(java.lang.Object o)
static PurityGraph	freshGraph(SootMethod m) Special constructor for "pure" methods returning a fresh object.
protected java.util.Set<PurityNode>	getEscaping()
int	hashCode()
protected int	internalParamStatus(PurityNode p)
protected void	internalPassEdges(java.util.Set toColor, java.util.Set<PurityNode> dest, boolean consider_inside)
protected void	internalPassNode(PurityNode node, java.util.Set<PurityNode> dest, boolean consider_inside)
protected void	internalPassNodes(java.util.Set toColor, java.util.Set<PurityNode> dest, boolean consider_inside)
boolean	isPure() Call this on the merge of graphs at all return points of a method to know whether the method is pure.
boolean	isPureConstructor() We use a less restrictive notion of purity for constructors: pure constructors can mutate fields of this.
protected boolean	localsPut(Local local, PurityNode node)
protected boolean	localsPutAll(Local local, java.util.Set nodes)
protected boolean	localsRemove(Local local)
protected void	mergeNodes(PurityNode src, PurityNode dst) Utility function to merge node src into dst; src is removed
int	paramStatus(int param) Call this on the merge of graphs at all return points of a method to know whether an object passed as method parameter is read only (PARAM_RO), read write (PARAM_RW), or safe (PARAM_SAFE).
protected void	removeNode(PurityNode n) Utility function to remove a node & all adjacent edges
protected void	sanityCheck() Sanity check.
int	thisStatus()

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Field Detail

doCheck

public static final boolean doCheck

See Also:

Constant Field Values

nodes

protected java.util.Set nodes

paramNodes

protected java.util.Set paramNodes

edges

protected MultiMap edges

locals

protected MultiMap locals

ret

protected java.util.Set ret

globEscape

protected java.util.Set globEscape

backEdges

protected MultiMap backEdges

backLocals

protected MultiMap backLocals

mutated

protected MultiMap mutated

Method Detail

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object

conservativeGraph

public static PurityGraph conservativeGraph(SootMethod m,
                                            boolean withEffect)

Conservative constructor for unanalysable calls.

Note: this gives a valid summary for all native methods, including Thread.start().

Parameters:

withEffect - add a mutated abstract field for the global node to account for side-effects in the environment (I/O, etc.).

freshGraph

public static PurityGraph freshGraph(SootMethod m)

Special constructor for "pure" methods returning a fresh object. (or simply pure if returns void or primitive).

sanityCheck

protected void sanityCheck()

Sanity check. Used internally for debugging!

internalPassEdges

protected void internalPassEdges(java.util.Set toColor,
                                 java.util.Set<PurityNode> dest,
                                 boolean consider_inside)

internalPassNode

protected void internalPassNode(PurityNode node,
                                java.util.Set<PurityNode> dest,
                                boolean consider_inside)

internalPassNodes

protected void internalPassNodes(java.util.Set toColor,
                                 java.util.Set<PurityNode> dest,
                                 boolean consider_inside)

getEscaping

protected java.util.Set<PurityNode> getEscaping()

isPure

public boolean isPure()

Call this on the merge of graphs at all return points of a method to know whether the method is pure.

isPureConstructor

public boolean isPureConstructor()

We use a less restrictive notion of purity for constructors: pure constructors can mutate fields of this.

See Also:

isPure

internalParamStatus

protected int internalParamStatus(PurityNode p)

paramStatus

public int paramStatus(int param)

Call this on the merge of graphs at all return points of a method to know whether an object passed as method parameter is read only (PARAM_RO), read write (PARAM_RW), or safe (PARAM_SAFE). Returns PARAM_RW for primitive-type parameters.

thisStatus

public int thisStatus()

See Also:

isParamReadOnly

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

localsRemove

protected final boolean localsRemove(Local local)

localsPut

protected final boolean localsPut(Local local,
                                  PurityNode node)

localsPutAll

protected final boolean localsPutAll(Local local,
                                     java.util.Set nodes)

removeNode

protected final void removeNode(PurityNode n)

Utility function to remove a node & all adjacent edges

mergeNodes

protected final void mergeNodes(PurityNode src,
                                PurityNode dst)

Utility function to merge node src into dst; src is removed