DIP38

DIP38: Safe references and rvalue references without runtime checks.

Title:	Safe references and rvalue references without runtime checks
DIP:	38
Version:	1
Status:	Draft
Created:	2013-05-06
Last Modified:	2013-05-06
Author:	Timothee Cour
Links:

Abstract

In short, the compiler internally annotates ref-return functions with ref(i1,...,iN) indicating that the function may return argument j (j=i1...iN) by reference (possibly via field accesses), where j is also a ref input argument. This list can be empty, and if the function is a method or internal function, argument 0 refers to implicit 'this' parameter. These annotations are used to validate/invalidate ref return functions that call such a ref return function. These annotations are also written in the automatically generated di interface files.

Internal Compiler Annotation

Dconf13 introduced safe references enabled by a runtime check (see email thread from Walter: 'Rvalue references - The resolution'). I propose a formulation that is safe, yet doesn't require any runtime check. The compiler automatically annotates any return by ref function with a dependency on input arguments:

eg:

struct U{T x;}
ref T foo(ref T a, ref T b, ref U c){
  static T d;
  if(condition)
    return a;
  else if(condition(b))
    return c.x;
  else
     return d;
}

will be rewritten internally by the compiler as having the signature:

ref(0,2) T foo(ref T a, ref T b, ref U c);

indicating that ref depends on ref arguments 0(a) and 2 (c) (dependency on c is via field access). The other arguments are not in the list because they're not input ref arguments, or not returned.

Second example: when the function is a member (say of a struct), the 'this' parameter is implicitly argument number 0, but the same rules apply:

struct S { T t; ref T fooc(ref T a) { if(condition) return t; else return a;} }

will be rewritten internally by the compiler as having the signature:

struct S { T t; ref(0,1) T fooc(ref T a); }

because there's a ref dependency on 0(this) and 1(a).

Note, if there's no dependency on input ref arguments (for example, it returns by ref a global), then the ref list is empty, ie ref().

The di files will have to write those annotations written down, which shall be done automatically.

Safe ref validation at compile time

Given those compiler generated annotations, it is easy to validate/invalidate ref safety: the rule is: in any return statement of a ref-return function, the ref dependency list can only refer to: A) global variables (gc-alloced, static etc) B) ref inputs This excludes locals.

Examples: taken from Walter's above mentioned email:

//Case A:
    ref T fooa(ref T t) { return t; }
    //=> ref(0) T fooa(ref T t);
    ref T bar() { T t; return fooa(t); } // error since 0 refers to t which is a local

//Case B:
    ref T foob(ref U u) { return u.t; } 
//=>ref(0) T foob(ref U u) { return u.t; } 
    ref U bar() { T t; return foob(t); } // error since 0 refers to t which is a local

//Case C:
    struct S { T t; ref T fooc() { return t; } }
//=>struct S { T t; ref(0) T fooc(); } //0 refers to 'this'
    ref T bar() { S s; return s.fooc(); } // error since 0 refers to this = s, which is local

//Case D:
    Returning ref to uplevel local:

    ref T food() {
        T t;
        ref T bar() { return t; }
//=>ref(0) T bar(); // 0 here indicates an implicit 'this' pointing to local stack allocated variables (wouldn't be the case if t were static variable)
        return bar(); //error since 0 refers to local stack
    }

//case E:
    Transitively calling other functions:

    ref T fooe(T t) { return ref  fooa(t); } //error since we have the compiler rewrite 'ref(0) T fooa(ref T t);' and 0 refers to t, a local variable (t is not a ref variable in fooe).

Corner case: mutually recursive ref return functions with ref arguments

There is a remaining (arguably rare) case not treated above: the case of mutually recursive ref return functions.

    ref T foo1(ref T a, T b, ref T c) { if(...) return foo2(a,0,c); else return a; }
    ref T foo2(ref T a, T b, ref T c) { if(...) return foo1(a,1,c); else return c; }

In this case, the compiler cannot directly annotate foo1 since it depends recursively on foo2 and vice versa. In this case, we could fall back to the runtime check on return addresses as proposed in Dconf13, although there is probably a label propagation algorithm that can infer at compile time the correct ref dependencies (will think about it).

Note, this does NOT require inter-procedure analysis, as only function signatures (with internal annotation) of functions called in a return statement is required when considering a function's ref dependencies.

Rvalue references

As for rvalue references, the compiler shall introduce a temporary variable before calling the ref function as has been discussed elsewhere. The same rules apply.

Copyright

This document has been placed in the Public Domain.