[cfe-dev] Proposal for Uniqueness Analysis

[Christian Wailes]

As things currently stand, there is a problem with some move-only classes
which model unique-ownership semantics: we are unable to determine which
methods are safe to call only before a move, or both before and after a
move.  An example of this is the std::unique_ptr class.  When a
std::unique_ptr object is managing a pointer to a valid region of memory
you may dereference it.  However, once the pointer has been moved to
another object a warning should be generated if it is dereferenced again,
e.g.:

int main(void) {

 std::unique_ptr<int> p0(new int);

 std::unique_ptr<int> p1();

 *p0 = 0;

 p1 = std::move(p0);

 // Dereferencing p0 is illegal here, as it has a null value.

 printf(“p0 points to %d\n”, *p0);

}

To address this problem for std::unique_ptr we propose a new set of
annotations and an analysis.  This work will later be applied to other use
cases, such as ensuring continuations are called and that files are closed
(and not accessed after they are closed).  We have designed the annotations
and analysis to be applicable to any class that implements move-only
unique-ownership semantics.  The std::unique_ptr class was chosen as the
first step in this work due to its immediate usefulness and the simplicity
of the analysis needed for this use case.

The analysis itself is a data-flow analysis, and borrows both terminology
and design aspects from literature on linear types [1,2].  It tracks the
state (consumed, unconsumed, or unknown) of a std::unique_ptr through its
lifetime by traversing the control flow graph (CFG).  A
std::unique_ptrstarts its lifetime in the
consumed state if it is initialized using the default constructor.  If the
non-default constructor is used it is considered to be in the
unconsumedstate.  Ownership of a value is transferred whenever a
std::unique_ptr is passed as an rvalue reference; this transitions the
object into a consumed state.  An object may also be transitioned into the
consumed state when certain, annotated, methods are called.

When a branch is encountered the state of the object is merged at the
branch’s join point.  If the object is in the unconsumed state along one
branch, and the consumed state along another branch the object will enter
the unknown state; any further uses of the object must be guarded by tests
for the object’s consumededness.

To provide useful warnings we must also annotate methods as being able to
be called only when the object is in the unconsumed state or callable when
the object is in any state.  Annotating the dereference operators for
std::unique_ptr as only being able to be called when the object is in the
unconsumed state would allow us to generate the correct warning in the
above example.

Future work would be to allow functions that take move-semantic objects as
parameters to specify the state that they expect the objects to be in;
unannotated functions that take std::unique_ptr object parameters currently
assume that the argument is in the unknown state.  If the same analysis is
desired for C code and non-class/struct types we could add additional
annotations and extend the analysis at a later date.

The proposed annotations, which may be changed, are TESTS_UNCONSUMED,
CALLABLE_ALWAYS, CALLABLE_WHEN_UNCONSUMED, and CONSUMES.  We are, of
course, open to suggestions for better/different names.  Any class that has
a method annotated with TESTS_UNCONSUMED, and either CALLABLE_ALWAYS or
CALLABLE_WHEN_UNCONSUMED is subject to our analysis.  A class may have its
methods annotated with either CALLABLE_ALWAYS or
CALLABLE_WHEN_UNCONSUMEDbut not both, as if one annotation is used the
other is assumed for all
unannotated functions.  A brief description of each of the annotations
follows:


   -

   TESTS_UNCONSUMED - Marks methods that return true when the object is in
   an unconsumed state.
   -

   CALLABLE_ALWAYS - Marks methods that can be called when the object is in
   any state.
   -

   CALLABLE_WHEN_UNCONSUMED - Marks methods that can be called only when
   the object is unconsumed.
   -

   CONSUMES - Marks a method that transitions an object from the
unconsumedto the
   consumed state.


Following shortly will be a patch that adds the appropriate annotations to
Clang.  Next, we will refactor the existing thread safety analysis
infrastructure to be usable for this analysis.  Following the refactoring
we will implement the analysis within AnalysisBasedWarnings.  Any comments,
questions, or concerns would be much appreciated.

- Chris


   1.

   Wadler, Philip. "Linear types can change the world." In IFIP TC, vol. 2,
   pp. 347-359. 1990.
   2.

   Kobayashi, Naoki. "Quasi-linear types." In Proceedings of the 26th ACM
   SIGPLAN-SIGACT symposium on Principles of programming languages, pp.
   29-42. ACM, 1999.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130710/905c7459/attachment.html>