Skip to content

Latest commit

 

History

History
779 lines (606 loc) · 26.7 KB

DIP1000.md

File metadata and controls

779 lines (606 loc) · 26.7 KB
Raw

Scoped Pointers

Section Value
DIP: 1000
Review Count: 1 Most Recent
Author: Marc Schütz, deadalnix, Andrei Alexandrescu, Walter Bright
Implementation:
Status: Superseded

Table of Contents

Abstract

A garbage collected language is inherently memory safe. References to data can be passed around without concern for ownership, lifetimes, etc. But this runs into difficulty when combined with other sorts of memory management, like stack allocation, malloc/free allocation, reference counting, etc.

Knowing when the lifetime of a reference is over is critical for safely implementing memory management schemes other than tracing garbage collection. It is also critical for the performance of reference counting systems, as it will expose opportunities for elision of the inc/dec operations.

scope provides a mechanism to guarantee that a reference cannot escape lexical scope.

This is a reboot of DIP69. It differs in that it builds on the success of DIP25 by using return scope to indicate scope parameters that can be returned by the function.

Links

Description

Benefits

  • References to stack variables can no longer escape.
  • Delegates currently defensively allocate closures with the GC. Few actually escape, and with scope only those that actually escape need to have the closures allocated.
  • @system code like std.internal.scopebuffer can be made @safe.
  • Reference counting systems need not adjust the count when passing references that do not escape.
  • Better self-documentation of encapsulation.

Definitions

Reachability vs. lifetime

For each value v within a program we define the notion of reachability denoted as reachability(v), akin to the lexical extent through which the value can be accessed.

  • For an rvalue, the reachability is the expression within which it is used.
  • For a named variable in a scope, the reachability is the lexical scope of the variable per the language rules.
  • For a module-level variable, reachability is considered infinite. Notation: reachability(v) = ∞.

Due to language scoping rules, reachabilities cannot partially intersect or "cross": for any two values, either they are not simultaneously reachable at all, or one's reachability is included within the other's. We define a partial order among reachabilities: reachability(v1) <= reachability(v2) if v2 is reachable through all portions of program when v1 is reachable (including the case where both values have infinite reachabilities). If two variables have disjoint reachabilities, they are unordered.

We also define lifetime for each value, which is the extent during which a value can be safely used.

  • For types without indirections such as int, reachability and lifetime are equal for rvalues and lvalues.
  • For all global and static variables, lifetime is infinite.
  • For values allocated on the garbage collected heap, lifetime is infinite whilst reachability is dependent on the references in the program bound to those values.
  • For an unrestricted pointer, reachability is dictated by the usual lexical scope rules. Lifetime, however is dictated by the lifetime of the data to which the pointer points to.

Examples:

void fun1() {
    int x; // starting here, x becomes reachable and also starts "living"
    int y = x + 42; // lifetime(42) and reachability(42) last through the initialization expression
    ...
   // lifetime(y) and reachability(y) end here, just before those of x
   // lifetime(x) and reachability(x) end here
}

void fun2() {
    int * p; // reachability(p) occurs from here through the end of the function
    // at this point lifetime(p) is infinite because it is null and lifetime(null) is infinite
    if (...) {
        int x;
        p = &x; // lifetime(p) is now equal to lifetime(x)
    }
    // here lifetime(p) may have ended but p is still reachable
}

If a value is reachable but its lifetime has ended, the program is in a dangerous, albeit not necessarily incorrect state. The program becomes undefined if the value of which lifetime has ended is actually used.

This proposal ensures statically that variables in @safe code with the scope storage class have a lifetime that includes their reachability, so they are safe to use at all times.

By consequence of the above, inside a function:

  • Parameters passed by scope are conservatively assumed to have lifetime somewhere in the caller's scope;
  • Parameters passed by value have shorter lifetime than those passed by passed by ref/out/scope, but longer than any locals defined by the function. The lifetimes of by-value parameters are ordered lexically.

Algebra of Lifetimes

Certain expressions create values of which lifetime is in relationship with the participating value lifetimes, as follows:

expression lifetime notes
&e lifetime(e)
&*e lifetime(e)
e + integer lifetime(e) Applies only when e is a pointer type
e - integer lifetime(e) Applies only when e is a pointer type
*e ∞ Lifetime is not transitive
e1, e2 lifetime(e2)
e1 op= e2 lifetime(e1)
e1 ? e2 : e3 min(lifetime(e2), lifetime(e3))
e++ lifetime(e) Applies only when e is a pointer type. This has academic value only because pointer increment is disallowed in @safe code.
e-- lifetime(e) Applies only when e is a pointer type. This has academic value only because pointer decrement is disallowed in @safe code.
cast(T) e lifetime(e) Applies only when both T and e have pointer type.
new ∞ Allocates on the GC heap.
e.field lifetime(e)
e.func(args) See section dedicated to discussing methods.
func(args) See section dedicated to discussing functions.
e[] lifetime(e)
e[i..j] lifetime(e)
&e[i] lifetime(e)
e[i] ∞
ArrayLiteral ∞ Array literals are allocated on the GC heap
ArrayLiteral[constant] ∞ Array literals are allocated on the GC heap

Aggregates

The following sections define scope working on primitive types (such as int) and pointers thereof (such as int*). This is without loss of generality because aggregates can be handled by decomposition as follows:

  • From a lifetime analysis viewpoint, a struct is considered a juxtaposition of its direct members. Passing a struct by value into a function is equivalent to passing each of its members by value. Passing a struct by ref is equivalent to passing each of its members by ref. Finally, passing a pointer to a struct is analyzed as passing a pointer to each of its members. Example:

    struct A { int x; float y; }
void fun(A a); // analyzed similarly to fun(int x, float y);
void gun(ref A a); // analyzed similarly to gun(ref int x, ref float y);
void hun(A* a); // analyzed similarly to hun(int* x, float* y);

  • Lifetimes of statically-sized arrays T[n] is analyzed as if the array were a struct with n fields, each of type T.

  • Lifetimes of built-in dynamically-sized slices T[] are analyzed as structs with two fields, one of type T* and the other of type size_t.

  • Analysis of lifetimes of class types is similar to analysis of pointers to struct types.

  • For struct members of aggregate type, decomposition may continue transitively.

Fundamentals of scope

The scope storage class ensures that the lifetime of a pointer/reference is shorter than the lifetime of the referred object. Dereferencing through a scope variable is guaranteed to be safe.

scope is a storage class, and affects declarations. It is not a type qualifier. There is no change to existing scope grammar. It fits in the grammar as a storage class.

scope affects:

  • local variables allocated on the stack
  • function parameters
  • non-static member functions (applying to the this implicit parameter)
  • delegates (applying to their implicit environment)
  • return value of functions

It is ignored for other declarations. It is ignored for declarations that have no indirections.

scope enum e = 3;  // ignored, no indirections
scope int i;       // ignored, no indirections

The scope storage class affects variables according to these rules:

  1. A scope variable can only be initialized and assigned from values that have lifetimes longer than the variable's lifetime. (As a consequence a scope variable can only be assigned to scope variables that have shorter lifetime.)
  2. A variable is inferred to be scope if it is initialized with a value that has a non-∞ lifetime.
  3. A scope variable cannot be initialized with the address of a scope variable. (If it did it would lose the scope attribute of the latter's contents.)
  4. A return scope parameter can be initialized with another return scope parameter—return scope is idempotent.

Examples for each rule:

int global_var;

void fun1() {
    scope int* a = &global_var; // OK per rule 1, lifetime(&global_var) > lifetime(a)
    a = &global_var;       // OK per rule 1, lifetime(&global_var) > lifetime(a)
    int b;
    a = &b; // Disallowed per rule 1, lifetime(&b) < lifetime(a)
    scope c = &b; // OK per rule 1, lifetime(&b) > lifetime(c)
    int* b;
    a = b; // Disallowed per rule 1, lifetime(b) < lifetime(a)
}

void fun2() {
    auto a = &global_var; // OK, a is a regular int*
    int b;
    auto c = &b; // Per rule 2, c has scope storage class
}

void fun3(scope int * p1) {
    scope int** p2 = &p1; // Disallowed per rule 3
    scope int* p3;
    scope int** p4 = &p3; // Disallowed per rule 3
}

void bar(scope int* input);

void fun4(scope int * p1) {
    bar(p1); // OK per rule 4
}

A few more examples combining the rules:

int global_var;

void bar(scope int* input);

void foo() {
    scope int* a;
    a = &global_var;       // Ok, `global_var` has a greater lifetime than `a`
    scope b = &global_var; // Ok, type deduction
    int c;

    if(...) {
        scope x = a;       // Ok, copy of reference,`x` has shorter lifetime than `a`
        scope y = &c;      // Ok, lifetime(y) < lifetime(& c)
        int z;
        b = &z;            // Error, `b` will outlive `z`
        int* d = a;        // Ok: d is inferred to be `scope`
    }

    bar(a);                // Ok, scoped pointer is passed to scoped parameter
    bar(&c);               // Ok, lifetime(parameter input) < lifetime(c)
    int* e;
    e = &c;                // Error, lifetime(e's view) is &infin; and is greater than lifetime(c)
    a = e;                 // Ok, lifetime(a) < lifetime(e)
    scope int** f = &a;    // Error, rule 4
    scope int** h = &e;    // Ok
    int* j = *h;           // Ok, scope is not transitive
}

int* global_ptr;

void abc() {
    scope int* a;
    int* b;
    scope int* c = a;      // Error, rule 5
    scope int* d = b;      // Ok
    int* i = a;            // Ok, scope is inferred for i
    global_ptr = d;        // Error, lifetime(d) < lifetime(global_ptr)
    global_ptr = i;        // Error, lifetime(i) < lifetime(global_ptr)
    int* j;
    global_ptr = j;        // Ok, j is not scope
}

Interaction of scope with the return Statement

A value containing indirections and annotated with scope cannot be returned from a function.

class C { ... }

C fun1() {
    scope C c;
    ...
    return c;   // Error
}

int fun2() {
    scope int i;
    ...
    return i;   // Ok, i has no indirections
}

scope int* fun3() {
    scope int* p;
    return p;   // Error
    return p+1; // Error, nice try!
    return &*p; // Error, won't work either
}

int* func(return scope int* r, scope int* s, int* t)
{
    return r; // Ok
    return s; // Error
    return t; // Ok
}

Functions

Inference

scope is inferred for function parameters if not specified, under the same circumstances as pure, nothrow, @nogc, and @safe are inferred. Scope is not inferred for virtual functions.

Overloading

scope does not affect overloading. If it did, then whether a variable was scope or not would affect the code path, making scope inference impractical. It also makes turning scope checking on/off impractical.

T func(scope T);
T func(T);

T t; func(t); // Error, ambiguous
scope T u; func(u); // Error, ambiguous

Implicit Conversion of Function Pointers and Delegates

scope can be added to parameters, but not removed.

alias T function(T) fp_t;
alias T function(scope T) fps_t;
alias T function(return scope T) fprs_t;

T foo(T);
T bar(scope T);
T abc(return scope T);

fp_t   fp = &foo;   // Ok
fp_t   fp = &bar;   // Ok
fp_t   fp = &abc;   // Error

fps_t  fp = &foo;   // Error
fps_t  fp = &bar;   // Ok
fps_t  fp = &abc;   // Error

fprs_t fp = &foo;   // Ok
fprs_t fp = &bar;   // Ok
fprs_t fp = &abc;   // Ok

Inheritance

Overriding functions inherit any scope annotations from their antecedents. Scope is covariant, meaning it can be added to overriding functions. In other words, overriding functions must be implicitly convertible to its antecedent.

class C
{
    T foo(T);
    T bar(scope T);
    T abc(return scope T);
}

class D : C
{
    override T foo(scope T);        // Ok, can add scope
    override T foo(return scope T); // Error

    override T bar(T);              // Error, cannot remove scope
    override T bar(return scope T); // Error

    override T abc(T);              // Ok
    override T abc(scope T);        // Ok
}

Mangling

In cases where scope is ignored, it does not contribute to the mangling. Scope parameters will be mangled with 'M'. return scope with 'MNk'.

Nested Functions

Nested functions have more objects available than just their arguments:

ref T foo() {
  T t;
  ref T func() { return t; }
  return func();  // disallowed
}

Nested functions are analyzed as if each variable accessed outside of its scope was passed as a ref parameter. All parameters have scope inferred from how they are used in the function body.

Pointers

Escaping via Return

The simple cases of this are already disallowed prior to this DIP:

T* func(T t) {
  T u;
  return &t; // Error: escaping reference to local t
  return &u; // Error: escaping reference to local u
}

But are easily circumvented:

T* func(T t) {
  T* p = &t;
  return p;  // no error detected
}

@safe currently deals with this by preventing taking the address of a local:

T* func(T t) @safe {
  T* p = &t; // Error: cannot take address of parameter t in @safe function func
  return p;
}

This is restrictive. The scope storage class was introduced which annotates the pointer. scope can only appear in certain contexts, in particular function parameters and local variables.

Scope can be passed down to functions:

void func(scope T* t) @safe;
void bar(scope T* t) @safe {
   func(t); // ok
}

But the following idiom is far too useful to be disallowed:

T* func(T* t) {
  return t; // ok
}

And if it is misused it can result in stack corruption:

T* foo() {
  T t;
  return func(&t); // currently, no error detected, despite returning pointer to t
}

The:

return func(&t);

case is detected by all of the following conditions being true:

  • foo() returns a pointer
  • func() returns a pointer
  • func() has one or more parameters that are pointers
  • 1 or more of the arguments to those parameters are scope objects local to foo()
  • Those arguments can be @safe-ly converted from the parameter to the return type.

For example, if the return type is larger than the parameter type, the return type cannot be a reference to the argument. If the return type is a pointer, and the parameter type is a size_t, it cannot be a reference to the argument. The larger a list of these cases can be made, the more code will pass @safe checks without requiring further annotation.

returning scope

The above solution is correct, but a bit restrictive. After all, func(t, u) could be returning a pointer to non-local u, not local t, and so should work. To fix this, introduce the concept of return scope:

T* func(scope T* t, T* u) {
  return t; // Error: escaping scope t
  return u; // ok
}

Scope means that the pointer is guaranteed not to escape.

T* u;
T* foo() @safe {
  T t;
  return func(&t, u); // Ok, u is not local
  return func(u, &t); // Error: escaping scope t
}

This minimizes the number of scope annotations required.

Scope Function Returns

scope can be applied to function return values (even though it is not a type qualifier). It must be applied to the left of the declaration, in the same way ref is:

int* foo() scope;     // applies to 'this' reference
scope: int* foo();    // applies to 'this' reference
scope { int* foo(); } // applies to 'this' reference
scope int* foo();     // applies to return value

The lifetime of a scope return value is the lifetime of an rvalue. It may not be copied in a way that extends its life.

int* bar(scope int*);
scope int* foo();
...
return foo();         // Error, lifetime(return) > lifetime(foo())
int* p = foo();       // Error, lifetime(p) is &infin;
bar(foo());           // Ok, lifetime(foo()) > lifetime(bar())
scope int* q = foo(); // error, lifetime(q) > lifetime(rvalue)

This enables scope return values to be safely chained from function to function; in particular it also allows a ref counted struct to safely expose a reference to its wrapped type.

A parameter can be marked as return scope meaning that parameter may be returned by the function. The return value is treated as if the function were annotated with scope.

Classes

Scope class semantics are equivalent to a pointer to a struct.

Static Arrays

Scope static array semantics are equivalent to a scope struct:

T[3] a;
struct A { T t0, t1, t2; } A a;

@safe

Errors for scope violations are only reported in @safe code.

Major Idioms Enabled

Identity function

T identity(T)(T x) { return x; } // overload 1
ref T identity(T)(ref T x) { return x; } // overload 2

Even if the body of identity weren't available, the compiler can infer it is escaping its parameter.

If identity is applied to a scope variable (including scope ref parameters), then overload 2 is not a match because per the rules scope ref cannot bind to ref. Therefore, overload 1 will match. Example:

void fun(int a, ref int b, scope ref int c) {
    auto x = identity(42); // rvalue, overload 1 matches
    auto y = identity(a); // lvalue, overload 2 matches
    auto z = identity(c); // scope ref value, overload 1 matches
}

In fact both overloads can be integrated in a single signature:

auto ref T identity(T)(auto ref T x) { return x; }

Owning Containers

Containers that own their data will be able to give access to elements by scope ref. The compiler ensures that the references returned never outlive the container. Therefore, the container can deallocate its payload (subject to control of multiple container copies, e.g. by means of reference counting). A basic outline of a reference counted slice is shown below:

@safe struct RefCountedSlice(T) {
	private T[] payload;
	private uint* count;

	this(size_t initialSize) {
		payload = new T[initialSize];
		count = new size_t;
		*count = 1;
	}

	this(this) {
		if (count) ++*count;
	}

	// Prevent reassignment as references to payload may still exist
	@system opAssign(RefCountedSlice rhs) {
		this.__dtor();
		payload = rhs.payload;
		count = rhs.count;
		++*count;
	}

    // Interesting fact #1: destructor can be @trusted
	@trusted ~this() {
		if (count && !--*count) {
			delete payload;
			delete count;
		}
	}

    // Interesting fact #2: references to internals can be given away
	scope ref T opIndex(size_t i) {
		return payload[i];
	}

	// ...
}

// Prevent premature destruction as references to payload may still exist
// (defined in object.d)
@system void destroy(T)(ref RefCountedSlice!T rcs);

RefCountedSlice mimics the semantics of T[] with the notable difference that the payload is deallocated automatically when it is no longer used. It is usable in @safe code because the compiler ensures statically a ref to an element may never outlive the slice.

Note: This DIP does not attempt to allow opAssign and destroy to be @safe. Those cases will be covered by a separate Reference Counting DIP. The following test demonstrates why those cases are disallowed in @safe code:

@safe unittest
{
    alias RCS = RefCountedSlice!int;
    static fun(ref RCS rc, ref int ri)
    {
        rc = rc.init; // Error: can't call opAssign in @safe code
        rc.destroy;   // Error: can't call destroy(RCS) in @safe code
        ri++;         // would have been unsafe
    }
    auto rc = RCS(1);
    fun(rc, rc[0]);
    assert(rc[0] == 1);
}

Breaking changes / deprecation process

Some code will no longer work. Although inference will take care of a lot of cases, there are still some that will fail.

int i,j;
int* p = &i;  // Ok, scope is inferred for p
int* q;
q = &i;   // Error: too late to infer scope for q

Currently, scope is ignored except that a new class use to initialize a scope variable allocates the class instance on the stack. Fortunately, this can work with this new proposal, with an optimization that recognizes that if a new class is unique, and assigned to a scope variable, then that instance can be placed on the stack.

Implementation Plan

Turning this on may cause significant breakage, and may also be found to be an unworkable design. Therefore, implementation stages will be:

  • enable new behavior with a compiler switch -scope
  • issue deprecations for code which would stop compiling in -scope
  • replace deprecaton messages with warnings
  • replace warnings with errors
  • make -scope behaviour the default and actual CLI flag no-op and undocumented

Copyright & License

Copyright (c) 2016 by the D Language Foundation

Licensed under Creative Commons Zero 1.0

Reviews

Addendum

This DIP did not complete the review process. It was left in Draft status for an extended period. During that time, an implementation of the proposal was released. It diverged significantly enough from the proposal that the decsion was made by the Language Maintainers, who are also coauthors of the DIP, to retire the DIP as "Superseded" rather than rewriting it.