soot.jimple.toolkits.annotation.purity
Class PurityGraph

java.lang.Object
  extended by soot.jimple.toolkits.annotation.purity.PurityGraph

public class PurityGraph
extends 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 experimiental... 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 statment 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
protected  MultiMap backEdges
           
protected  MultiMap backLocals
           
static boolean doCheck
           
protected  MultiMap edges
           
protected  Set globEscape
           
protected  MultiMap locals
           
protected  MultiMap mutated
           
protected  Set nodes
           
protected  Set paramNodes
           
protected  Set ret
           
 
Method Summary
 Object clone()
           
static PurityGraph conservativeGraph(SootMethod m, boolean withEffect)
          Conservative constructor for unanalysable calls.
 boolean equals(Object o)
           
static PurityGraph freshGraph(SootMethod m)
          Special constructor for "pure" methods returning a fresh object.
protected  Set<PurityNode> getEscaping()
           
 int hashCode()
           
protected  int internalParamStatus(PurityNode p)
           
protected  void internalPassEdges(Set toColor, Set<PurityNode> dest, boolean consider_inside)
           
protected  void internalPassNode(PurityNode node, Set<PurityNode> dest, boolean consider_inside)
           
protected  void internalPassNodes(Set toColor, 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, 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 Set nodes

paramNodes

protected Set paramNodes

edges

protected MultiMap edges

locals

protected MultiMap locals

ret

protected Set ret

globEscape

protected Set globEscape

backEdges

protected MultiMap backEdges

backLocals

protected MultiMap backLocals

mutated

protected MultiMap mutated
Method Detail

hashCode

public int hashCode()
Overrides:
hashCode in class Object

equals

public boolean equals(Object o)
Overrides:
equals in class 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(Set toColor,
                                 Set<PurityNode> dest,
                                 boolean consider_inside)

internalPassNode

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

internalPassNodes

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

getEscaping

protected 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 Object clone()
Overrides:
clone in class Object

localsRemove

protected final boolean localsRemove(Local local)

localsPut

protected final boolean localsPut(Local local,
                                  PurityNode node)

localsPutAll

protected final boolean localsPutAll(Local local,
                                     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