Type Members

1.  trait AggregatableValueProperty[S <: IndividualProperty[S, T], T <: AggregatedProperty[S, T]] extends Property

   A trait to conveniently implement properties that need aggregated values.

   A trait to conveniently implement properties that need aggregated values. Provides conversion between aggregated and individual variants.

   T

   Type of the property

2.  trait AggregatedProperty[S <: IndividualProperty[S, T], T <: AggregatedProperty[S, T]] extends AggregatableValueProperty[S, T]
3.  sealed abstract class AllocationFreeness extends OrderedProperty with IndividualProperty[AllocationFreeness, VirtualMethodAllocationFreeness] with AllocationFreenessPropertyMetaInformation

   Describes whether a org.opalj.br.DeclaredMethod or its (transitive) callees may allocate any objects/arrays.

4.  sealed trait AllocationFreenessPropertyMetaInformation extends PropertyMetaInformation
5.  case class AtMost extends EscapeProperty with Product with Serializable

   A refineable property that provides an upper bound.

   A refineable property that provides an upper bound. Only refinements to values below or equal to property are allowed to perform. This property should be used, if the analysis is not able to compute a more precise property.

6.  class CallStringContext extends Context

   A context that includes a call string

7.  class CallStringContexts extends AnyRef
8.  sealed abstract class ClassifiedImpure extends Purity

   Clients have to treat the method as impure.

   Clients have to treat the method as impure. If the property is refinable clients can keep the dependency.

9.  sealed abstract class CompileTimeConstancy extends OrderedProperty with CompileTimeConstancyPropertyMetaInformation

   Describes whether a org.opalj.br.Field is initialized deterministically to the same value on every execution of the program.

10.  sealed trait CompileTimeConstancyPropertyMetaInformation extends PropertyMetaInformation
11.  trait Context extends AnyRef

    Provides the context in which a method was invoked or an object was allocated.

12.  case class ContextuallyPure(modifiedParams: IntTrieSet) extends Purity with Product with Serializable

    The respective method may modify its parameters, but is pure otherwise.

    The respective method may modify its parameters, but is pure otherwise.

    A method calling a ContextuallyPure method can be Pure if the parameters of the call are confined inside that method.

    See also

    Purity for further details regarding the purity levels.

13.  case class ContextuallySideEffectFree(modifiedParams: IntTrieSet) extends Purity with Product with Serializable

    The respective method may modify its parameters, but otherwise it is side-effect free, i.e.

    The respective method may modify its parameters, but otherwise it is side-effect free, i.e. it does not have side effects but its results may still be non-deterministic.

    A method calling a ConteuxtuallySideEffectFree method can be SideEffectFree if the parameters of the call are confined inside that method.

    See also

    Purity for further details regarding the purity levels.

14.  case class DContextuallyPure(modifiedParams: IntTrieSet) extends Purity with Product with Serializable

    The respective method may perform actions that are generally considered impure or non-deterministic that some clients may wish to treat as pure and it may modify its parameters.

    The respective method may perform actions that are generally considered impure or non-deterministic that some clients may wish to treat as pure and it may modify its parameters. Otherwise it is pure.

    See also

    Purity for further details regarding the purity levels.

15.  case class DContextuallySideEffectFree(modifiedParams: IntTrieSet) extends Purity with Product with Serializable

    The respective method may perform actions that are generally considered impure that some clients may wish to treat as pure and it may modify its parameters.

    The respective method may perform actions that are generally considered impure that some clients may wish to treat as pure and it may modify its parameters. Otherwise it is side-effect free.

    See also

    Purity for further details regarding the purity levels.

16.  sealed abstract class EscapeProperty extends OrderedProperty with ExplicitlyNamedProperty with EscapePropertyMetaInformation

    Specifies the lifetime and accessability of object instance.

    Specifies the lifetime and accessability of object instance. This is classically used for compiler optimizations such as scalar replacement, stack allocation or removal of synchronization. However, other usages such as finding bugs or helping to identify immutable data-structures are also supported.

    Definitions in the Literature

    Choi et al. [1] describe two predicates that can be used to describe the properties relevant to escape information.

    "Let O be an object instance and M be a method invocation. O is said to escape M, denoted as Escapes(O, M), if the lifetime of O may exceed the lifetime of M."

    "Let O be an object instance and T be a thread (instance). O is said to escape T, again denoted as Escapes(O, T), if another thread, T’ != T, may access O."

    Furthermore it holds that "For any object O, !Escapes(O, M) implies !Escapes(O, T), where method M is invoked in thread T." [1]

    In contrast to this, Kotzmann and Mössenböck [2] describe the escape of an object with the access to this object from other methods or threads.

    Definition

    This EscapeProperty combines both concepts and is more specific about the reason why an object escapes to facilitate comprehension of the results.

    In the following, we provide further details about the different escape properties:

    NoEscape refers to the property of an object instance O created in method M for that it lifetime ends with the lifetime of M and no other method than M has access to O. This implies that there is no method M' != M that can access O (at least when disregarding reflection and native code). Objects with this property can be allocated at the stack or even scalar-replaced [2].

    An object instance O created in method M and thread T has the property EscapeInCallee, if its lifetime does not exceed the lifetime of M but M passes O as a parameter to a method which does not let O escape any further then EscapeInCallee. This implies that only M and methods M' that are (transitively) called by M have access to O. For objects that have the property EscapeInCallee no synchronization is needed and they can be allocated on the stack.

    For objects O, created in method M and thread T, whose lifetime exceeds its method of creation M and is (therefore) accessible by other methods, we provide seven different properties. For all of them we assume that M and all methods called by M do not let O escape the thread T. But it is not guaranteed that O will not escape T via a caller of M. The properties differ in the reason why the lifetime of O exceeds the lifetime of M. In case of EscapeViaReturn O is returned by M. If O has an exception type and is thrown in M, it has the property EscapeViaAbnormalReturn. For both of them it has no consequences if O escapes T via a caller of M. This is, because the execution ends with the (abnormal) return of O. All synchronization mechanisms inside of M or callees of M can be removed. The property EscapeViaParameter describes objects that gets assigned to a parameter of its method of creation (M). If O gets assigned to p.f for a parameter p of M, it could be the case that the actual parameter of p already escaped T. In this case O would also escape T directly via this assignment. Therefore no synchronization for O can be removed. As it could be also the case that O gets assigned to a parameter and returned by M, there are also properties representing the combinations of this kind of escapes. They are EscapeViaParameterAndAbnormalReturn, EscapeViaParameterAndReturn, EscapeViaNormalAndAbnormalReturn and EscapeViaParameterAndNormalAndAbnormalReturn.

    An object instance O created in method M and thread T has the property GlobalEscape, if its lifetime may exceed the lifetime of T (and another thread T'! = T gets access to O). For example, this is the case if O gets assigned to a static field (EscapeViaStaticField but also if assigned to a field of an object that has also GlobalEscape as property (EscapeViaHeapObject). Objects that have the property GlobalEscape have to be allocated on the heap and synchronization mechanisms can not be removed/proper synchronization is required if the object is accessed concurrently – the latter may be the goal of static analyses that find concurrency bugs). If the reason for the global escape is unspecified the case class GlobalEscape is used.

    The property values are partially ordered and form a lattice. The binary relation of the order is called lessOrEqualRestrictive and describes the restrictiveness of the scope in, which objects exists. The most restrictive (top) value is NoEscape and the least restrictive (bottom) one is GlobalEscape. A dot graph of the lattice can be found under br/src/main/resources/org/opalj/fpcf/properties.

    Algorithms are free to over approximate this property, i.e., for object instance O with actual property P it is okay to say O has property P' if P > P' (or in other words, P' is less restrictive than P).

    If they simply don't know the actual property they should use AtMost(NoEscape). If we know that the actual property is at most (i.e. not NoEscape), AtMost(EscapeInCallee) should be used. The same holds for every other non-bottom property. E.g. AtMost(EscapeViaParameter) should be used if we know that the actual property is at most EscapeViaParameter (i.e. neither NoEscape nor EscapeInCallee.

    org.opalj.ai.DefinitionSiteLike and org.opalj.br.analyses.VirtualFormalParameter are generally used as org.opalj.fpcf.Entity in combination with this property.

    VirtualMethodEscapeProperty provides a wrapper of this property addressing aggregated escape information for parameters of methods in a type hierarchy.

    [1] Choi, Jong-Deok, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. "Escape Analysis for Java." In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, 1–19. OOPSLA ’99. New York, NY, USA: ACM, 1999.

    [2] Kotzmann, Thomas, and Hanspeter Mössenböck. “Escape Analysis in the Context of Dynamic Compilation and Deoptimization.” In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments, 111–120. VEE ’05. New York, NY, USA: ACM, 2005.

17.  sealed trait EscapePropertyMetaInformation extends PropertyMetaInformation
18.  sealed abstract class FieldLocality extends Property with FieldLocalityMetaInformation

    Describe the lifetime of the values stored in an instance field.

    Describe the lifetime of the values stored in an instance field.

    LocalFields have a lifetime that is not longer than that of the field's owning instance. ExtensibleLocalFields provide the same guarantee only if the (dynamic) type of the owning instance is known not to extend java.lang.Cloneable. The lifetime of a value in a LocalFieldWithGetter can only be extended by it being returned by a method. I.e. if the caller of such method knows that it's receiver is fresh, the field's value may also be treated as fresh. ExtensibleLocalFieldWithGetter is used if both restrictions apply: The type type of the owning instance may not be cloneable and the value's lifetime could be extended by being returned by a method.

19.  sealed trait FieldLocalityMetaInformation extends PropertyMetaInformation
20.  sealed abstract class FinalEscapeProperty extends EscapeProperty
21.  trait GlobalEscape extends EscapeProperty

    The object escapes globally, typically because it is assigned to a static variable or to a field of a heap object.

    The object escapes globally, typically because it is assigned to a static variable or to a field of a heap object.

    This property should be used if and only if the analysis is conclusive and could determine that the value definitively escapes globally. If a more advanced analysis – potentially run later – could identify an object as only EscapeViaParameter, EscapeInCallee or even NoEscape then the refineable property AtMost(NoEscape) (or another non final property) should be used.

    Example:

    1. Given the following library code:

       public class X{
        public static Object o;
        public void m(boolean b) {
            Object o = new Object();        // ALLOCATION SITE
            if (b) X.o = o;
            return;
        }
       }

       An analysis is only expected to return EscapeViaStaticField for the object o instantiated in m, if the analyses knows that m is called and the parameter b is potentially true. If the above code is found in a library, it may very well be the case that certain parameter values/combinations will never be used in a certain setting and – therefore – o does not escape. However, from a pure technical point-of-view it may be useful/necessary to use GlobalEscape at some point to let depending computations know that no more changes will happen and therefore the dependencies can be deleted.

    See also

    EscapeProperty for further details.

22.  trait IndividualProperty[S <: IndividualProperty[S, T], T <: AggregatedProperty[S, T]] extends AggregatableValueProperty[S, T]
23.  case class MethodComplexity(value: Int) extends Property with MethodComplexityPropertyMetaInformation with Product with Serializable

    An upper bound for the maximum number of instructions that need to be evaluated when the method is executed/interpreted.

    An upper bound for the maximum number of instructions that need to be evaluated when the method is executed/interpreted. Using this property enables other analyses to make a decision whether to "inline" method calls or not. For example, to improve the precision of an analysis it may be very useful to inline short methods. Given the following code:

    def abs(i : Int) : Int = {
        if(i == Int.MinValue) Int.MaxValue // COND + RETURN
        else if(i < 0) -i // COND + RETURN
        else i // RETURN
    } // COMPLEXITY (BASED ON SOURCE CODE): 5
    
    def ratio(i : Int, j : Int) : Int = {
        abs(i) / abs(j) // HERE, when we do not inline abs calls, we have no idea about the final
                        // result; when we inline the abs calls, we can compute that the returned
                        // value will be positive or that the method throws a
                        // `DivisionByZeroException`.
    }

    In general, the control flow graph is analyzed to compute an upper bound for the number of evaluated instructions; as far as (easily) possible, loops are conceptually unrolled. If the uppper bound could not be determined, the method is rated as being maximally complex.

    The complexity of called methods is generally not taken into account. However, invoke instructions generally have a higher complexity than all other instructions to account for the fact that method calls are more expensive than all other types of instructions.

    If an upper bound of a method's complexity cannot be estimated, the method will have Int.MaxValue complexity.

    value

    The estimated complexity of a specific method ([0...Int.MaxMavlue])

24.  sealed trait MethodComplexityPropertyMetaInformation extends PropertyMetaInformation
25.  trait NoVaryingDataUse extends StaticDataUsage

    The method does not use static data that may change during one or between several program runs.

26.  sealed abstract class Purity extends IndividualProperty[Purity, VirtualMethodPurity] with PurityPropertyMetaInformation

    Describes the level of the purity of a org.opalj.br.DeclaredMethod.

    Describes the level of the purity of a org.opalj.br.DeclaredMethod.

    In general, a method is pure if its result only depends on its inputs and/or immutable global state and the execution of the method does not have any side effects; an instance method's inputs include the current object that is the receiver of the call.

    The description of the purity levels is inspired by the definition found on wikipedia:

    [...] a function may be considered a pure function if both of the following statements about the function hold:

    • The function always evaluates to the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change while program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.

    Hence, using true constants (e.g., Math.e) is not a problem as well as creating intermediate (mutable) data structures. More precisely, methods are pure if the values they refer to always (even across program runs) have an identical shape and the precise location in the heap is not relevant (e.g., java.lang.Object.hashCode() and ...toString() are not pure).

    • Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices. The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values. The function may return multiple result values and these conditions must apply to all returned values for the function to be considered pure. If an argument is "call-by-reference", any parameter mutation will alter the value of the argument outside the function, which will render the function impure.

    Given the preceding specification, the purity of a method is described by the subclasses of this property. In the following, the prefix of the names of the purity levels are used to identify the certainty of the computation of the purity; the letters have the following meaning:

    • LB = Lower Bound; the method is at least <PURITY_LEVEL>, but can still be even more pure.
    • C = Conditional; i.e., the current purity level depends on the purity level of other entities (These states are primarily used by the analysis to record the analysis progress.)
    • D = The method is <PURITY_LEVEL> if certain Domain-specific (non-pure) operations are ignored.

    ImpureByLackOfInformation methods have no constraints on their behavior. They may have side effect and depend on all accessible (global) state. Analyses can always return (LB)Impure as a safe default value - even if they are not able to prove that a method is indeed impure; however, in the latter case using ImpureByAnalysis is recommended as this enables subsequent analyses to refine the property. There are several implementations of ImpureByAnalysis which give additional reasoning why the analysis classified a method as impure.

    SideEffectFree methods may depend on all accessible (and mutable) state, but may not have any side effects. In single-threaded execution, this means that the object graph of the program may not have changed between invocation of the method and its return, except for potentially additional objects allocated by the method. For multi-threaded execution, the object graph may not change due to the invocation of the method, again except allocation of new objects. Note that the object graph may change during execution of the method due to other methods executing on concurrent threads. The method must not have any effects (besides consumption of resources like memory and processor time) on methods executing concurrently, in particular it may not acquire any locks on objects that concurrent methods could also try to acquire.

    Analyses may return SideEffectFree as a safe default value if they are unable to guarantee that a method is Pure, even if it is. However, to return SideEffectFree the analysis has to guarantee that the method does not have any side effects.

    Pure methods must be side effect free as described above and their result may only depend on their parameters (including the receiver object) and global constants. In particular, the result of a pure method must be structurally identical each time the method is invoked with structurally identical parameters. I.e., pure methods may depend on the aliasing relation between their parameters or between their parameters and global constants. E.g., the following method is pure:

    def cmp(s: String) : Boolean = {
         // Reference(!) comparison of s with the interned string "Demo":
         s eq "Demo";
    }

    In multi-threaded execution, pure methods can not depend on any mutable state of their parameters if that state might be mutated by concurrently executing methods.

    Analyses may return Pure only if they are able to guarantee that a method fulfills these requirements.

    CompileTimePure methods additionally may only use global state that is compile-time constant (i.e., deterministically initialized to the same value on every execution of the program). If their return value is of a reference type, they must return the same reference each time they are invoked with identical parameters.

    ExternallySideEffectFree and ExternallyPure methods are also similar to SideEffectFree and Pure methods, respectively, but may modify their receiver object. These properties may be used to detect changes that are confined because the receiver object is under the control of the caller.

    ContextuallySideEffectFree and ContextuallyPure methods may modifiy not only their receiver object but all of their parameters. Therefore, these properties can be used to detect confined changes because all parameters are under the control of the caller.

    DSideEffectFree and DPure methods may perform actions that are generally considered impure (or non-deterministic in the case of DPure), but that some clients may want to treat as pure. Such actions include, e.g. logging. A Rater is used to identify such actions and the properties contain a set of reasons assigned by the Rater.

    DExternallySideEffectFree and DExternallyPure methods are similar, but may again modify their receiver, while DContextuallySideEffectFree and DContextuallyPure methods may modify their parameters.

    ImpureByLackOfInformation is (also) used as the fallback value if no purity information could be computed for a method (no analysis is scheduled). Conceptually, clients must treat this in the same way as ImpureByAnalysis except that a future refinement may be possible in case of ImpureByAnalysis.

27.  sealed trait PurityPropertyMetaInformation extends PropertyMetaInformation
28.  sealed abstract class ReturnValueFreshness extends Property with ReturnValueFreshnessPropertyMetaInformation

    Describes whether a method returns a value that is allocated in that method or its callees and only has escape state EscapeViaReturn.

    Describes whether a method returns a value that is allocated in that method or its callees and only has escape state EscapeViaReturn.

    Values are FreshReturnValue for always freshly allocated return values, Getter for return values that can be treated as fresh if the methods's receiver is known to be fresh and ExtensibleGetter if additionally the method's receiver type must not implement java.lang.Cloneable. If the return value of a method may not be fresh, the method has NoFreshReturnValue. PrimitiveReturnValue is used for methods with a return type that is a base type or void. The return value freshness should never be relevant for such methods.

29.  sealed trait ReturnValueFreshnessPropertyMetaInformation extends PropertyMetaInformation
30.  sealed trait SelfReferenceLeakage extends Property

    Determines if an object potentially leaks its self reference (this) by passing assigning it to fields or passing it to methods which assign it to fields.

    Determines if an object potentially leaks its self reference (this) by passing assigning it to fields or passing it to methods which assign it to fields. Hence, it computes a special escape information.

    Here, the self-reference escapes the scope of a class if:

    • ... it is assigned to a (static) field,
    • ... it is passed to a method that assigns it to a field,
    • ... it is stored in an array,
    • ... it is returned (recall that constructors have a void return type),
    • ... if a superclass leaks the self reference.

    This property can be used as a foundation for an analysis that determines whether all instances created for a specific class never escape their creating methods and, hence, respective types cannot occur outside the respective contexts.

31.  case class SimpleContext extends Context with Product with Serializable

    A simple context that provides the bare minumum for context-insensitive analyses.

32.  class SimpleContexts extends AnyRef
33.  sealed abstract class StaticDataUsage extends OrderedProperty with IndividualProperty[StaticDataUsage, VirtualMethodStaticDataUsage] with StaticDataUsagePropertyMetaInformation

    Describes whether a org.opalj.br.DeclaredMethod uses static state and whether the used static state is compile-time constant.

34.  sealed trait StaticDataUsagePropertyMetaInformation extends PropertyMetaInformation
35.  class SystemProperties extends Property with SystemPropertiesPropertyMetaInformation
36.  sealed trait SystemPropertiesPropertyMetaInformation extends PropertyMetaInformation

    TODO Documentation

37.  case class ThrownExceptions(types: TypesSet) extends Property with ThrownExceptionsPropertyMetaInformation with Product with Serializable

    The set of exceptions that are potentially thrown by a specific method.

    The set of exceptions that are potentially thrown by a specific method. This includes the set of exceptions thrown by (transitively) called methods (if any). The property does not take the exceptions of methods which override the respective method into account. Nevertheless, in case of a method call all potential receiver methods are taken into consideration.

    Note that it may be possible to compute some meaningful upper type bound for the set of thrown exceptions even if methods are called for which the set of thrown exceptions is unknown. This is generally the case if those calls are all done in a try block but the catch/finally blocks only calls known methods - if any. An example is shown next and even if we assume that we don't know the exceptions potentially thrown by Class.forName, we could still determine that this method will never throw an exception.

    object Validator {
         def isAvailable(s : String) : Boolean = {
             try { Class.forName(s); true} finally {return false;}
         }
    }

    Information about ThrownExceptions is generally associated with DeclaredMethods. I.e., the information is not attached to Method objects!

    Note that the top-value of the lattice is the empty set and the bottom value is the set of all exceptions.

38.  case class ThrownExceptionsByOverridingMethods(exceptions: TypesSet = BRTypesSet.empty) extends Property with ThrownExceptionsByOverridingMethodsPropertyMetaInformation with Product with Serializable
39.  sealed trait ThrownExceptionsByOverridingMethodsPropertyMetaInformation extends PropertyMetaInformation
40.  class ThrownExceptionsFallback extends PropertyComputation[Method]
41.  sealed trait ThrownExceptionsPropertyMetaInformation extends PropertyMetaInformation
42.  sealed case class VirtualMethodAllocationFreeness(individualProperty: AllocationFreeness) extends AggregatedProperty[AllocationFreeness, VirtualMethodAllocationFreeness] with VirtualMethodAllocationFreenessPropertyMetaInformation with Product with Serializable

    Describes the aggregated allocation freeness for a virtual method.

43.  sealed trait VirtualMethodAllocationFreenessPropertyMetaInformation extends PropertyMetaInformation
44.  sealed case class VirtualMethodEscapeProperty(escapeProperty: EscapeProperty) extends Property with VirtualMethodEscapePropertyMetaInformation with Product with Serializable
45.  sealed trait VirtualMethodEscapePropertyMetaInformation extends PropertyMetaInformation
46.  sealed case class VirtualMethodPurity(individualProperty: Purity) extends AggregatedProperty[Purity, VirtualMethodPurity] with VirtualMethodPurityPropertyMetaInformation with Product with Serializable

    Describes the aggregated purity for a virtual method.

47.  sealed trait VirtualMethodPurityPropertyMetaInformation extends PropertyMetaInformation
48.  sealed abstract class VirtualMethodReturnValueFreshness extends Property with VirtualMethodReturnValueFreshnessMetaInformation

    Aggregate property for ReturnValueFreshness.

    Aggregate property for ReturnValueFreshness. Describes whether all methods that can be the target of a virtual method call will return fresh values.

49.  sealed trait VirtualMethodReturnValueFreshnessMetaInformation extends PropertyMetaInformation
50.  sealed case class VirtualMethodStaticDataUsage(individualProperty: StaticDataUsage) extends AggregatedProperty[StaticDataUsage, VirtualMethodStaticDataUsage] with VirtualMethodStaticDataUsagePropertyMetaInformation with Product with Serializable

    Describes the aggregated allocation freeness for a virtual method.

51.  sealed trait VirtualMethodStaticDataUsagePropertyMetaInformation extends PropertyMetaInformation