Detects pure (side-effect-free) functions. A different implementation of "impurity".
- C/C++/ObjC: Experimental
- Java: Experimental
This is an experimental inter-procedural analysis that detects pure (side-effect free) functions. For each function, purity analysis keeps track of not only the purity of the function but also some additional information such as whether the function modifies a global variable or which of the parameters are modified. It models functions with no summary/model as modifying the global state (hence impure).
If the function is pure (i.e. doesn't modify any global state or its parameters and doesn't call any unknown functions), then it reports an
There are two issues with the existing purity analysis:
- In order to detect which parameters are modified, we need an alias analysis which is difficult to get right.
- Just keeping track of modified arguments doesn't suffice.
Too see the issue with the first point, consider the following simple program:
in order to determine that
foo is impure, we need to know that the write to
b's field is actually changing the function parameter
a, i.e. we need to check if
b is aliasing
a. This is known as alias analysis and is hard to get right in a scalable manner. When this analysis was being developed, Infer didn't have a unified alias analysis and using biabduction seemed like a too daunting task at the time. Hence, we relied on InferBo's aliasing mechanism which was easy to invoke and integrate with. However, InferBo's aliasing analysis is far from perfect and causes issues for purity.
To see the issue with the second point, consider the following program:
The existing purity analysis concludes that the above function
contains is impure because it calls an impure function
next() which modifies the iterator (hence it thinks it also modifies the
list). However, notice that
contains doesn't have an observable side-effect:
list.iterator() returns a new object,
equals() are pure, and
next() only modifies the fields of the fresh object
contains should be considered as pure.
The analysis is used by:
- Loop-hoisting analysis which identifies loop-invariant function calls, i.e. functions that are pure and have loop-invariant arguments.
- Cost analysis which identifies control variables in the loop that affect how many times a loop is executed. In this computation, we need to prune control variables that do not affect how many times a loop is executed. In this pruning step, we need to compute loop-invariant variables (which requires the above analysis).
List of Issue Types
The following issue types are reported by this checker: