My Reference Safety System (DIP???)

[Zach the Mystic via Digitalmars-d]

On Thursday, 26 February 2015 at 21:33:53 UTC, Marc Schütz wrote:
> On Thursday, 26 February 2015 at 17:56:14 UTC, Zach the Mystic 
> wrote:
>> On Wednesday, 25 February 2015 at 21:26:33 UTC, Marc Schütz 
>> wrote:
> struct A {
>     B* b;
>     ~this() {
>         b.doSomething();
>     }
> }
>
> struct B {
>     void doSomething();
> }
>
> void foo() {
>     A a;      // declscope(1)
>     B b;      // declscope(1)
>     a.b = &b; // refscope(1) <= declscope(1): OK
>     // end of scope:
>     // `b` is destroyed
>     // `a`'s destructor is called
>     // => your calling a method on a destroyed object
> }
>
> Basically, every variable needs to get its own declscope; all 
> declscopes form a strict hierarchy (no partial overlaps).

Well, technically you only need one per variable with a 
destructor. Fortunately, this doesn't seem hard to add. Just 
another few bits, allowing as many declarations with destructors 
as seem necessary (4 bits = 15 variables, 5 bits = 31 variables, 
etc.), with the last being treated conservatively as unsafe. (I 
think anyone declaring 31+ variables with destructors in a 
function, and taking the addresses of those variables has bigger 
problems than memory safety!)

>> I guess this is the "Language versus Legacy" issue. I think 
>> D's strength is in it's language, not its huge legacy 
>> codebase. Therefore, I find myself going with the 
>> #pleasebreakourcode crowd, for the sake of extending D's lead 
>> where it shines.
>
> I'm too, actually, but it would be a really hard sell.

But look, Walter and Andrei were fine with adding `return ref` 
parameters. There's hope yet!

>> I'm not sure all references in safe code need to be `scope` - 
>> that would break a lot of code unto itself, right?
>
> Not sure how much would be affected. I actually suspect that 
> most of it already behaves as if it were scope, with the 
> exception of newly allocated memory. But those should ideally 
> be "owned" instead.
>
> But your right, there still needs to be an opt-out possibility, 
> most likely static.

I don't even have a use for `scope` itself in my proposal. The 
only risk I'm running is a lot of false positives -- safe 
constructs which the detection mechanism conservatively treats as 
unsafe because it can't follow the program logic. Still, it's 
hard for me to imagine even these appearing very much. And they 
can be put into @trusted lambdas -- all @trusted functions are 
treated as if they copy no references, effectively canceling any 
parameter attributes to the contrary.

>> T* fun(T* a, T** b) {
>>  T* c = new T;
>>  c = a;
>>  *b = c;
>>  return c;
>> }
>
> Algorithm for inference of ref scopes (= parameter annotations):
>
> 1) Each variable, parameter, and the return value get a ref 
> scope (or ref depth). A ref scope can either be another 
> variable (including `return` and `this`) or `static`.
>
> 2) The initial ref scope of variables is themselves.

Actually, no. The *declaration* scope is themselves. The initial 
ref scope is whatever the variable is initialized with, or just 
null if nothing. We could even have a bit for "could be null". 
You might get some null-checking out of this for free. But then 
you'd need more attributes in the signature to indicate "could be 
null!" But crashing due to null is not considered a safety issue 
(I think!), so I haven't gone there yet.

> 3) Each time a variable (or something reachable through a 
> variable) is assigned (returning is assignment to the return 
> value), i.e. for each location in the function that an 
> assignment happens, the new scope ref will be:
>
> 3a) the scope of the source, if it is larger or equal to the 
> old scope

If scope depth is >= 1, you inherit the maximum of the source and 
the target. If it's 0, you do a bitwise OR on the mystery scopes 
(unless the compiler can easily prove it doesn't need to), so you 
can accumulate all possible origins of the assigned-to scope.

> 3b) otherwise (for disjunct scopes, or assignment from smaller 
> to larger scope), it is an error (could potentially violate 
> guarantees)

I don't have "disjunct scopes". There's just greater than and 
less than. The mystery scopes are for figuring out what the 
parameter attributes are, and in the absence of inference, 
causing errors in safe code for the parameters not being 
accurately marked.

> 4) If a source scope refers to a variable (apart from the 
> destination itself), for which not all assignments have been 
> processed yet, it is put into a queue, to be evaluated later. 
> For code like `a = b; b = a;` there can be dependency cycles. 
> Such code will be disallowed.

No, my system is simpler. I want to make this proposal appealing 
from the implementation side as well as from the language side. 
You analyze the code in lexical order:

T* dum(T* a) {
   T* b = a; // b accumulates a
   return b; // okay... lexical ordering, b has a only
   T c;
   b = &c; // now b accumulates scopedepth(1);
   return b; // error here, but *only* here
}

The whole process relies on accumulating the scopes as the 
compiler encounters them. There are cases of branching 
conditional, combined with goto labels, or the beginnings of 
loops, where the logical order could be different from the 
lexical order. Only *these* cases are pushed onto an array and 
revisited when the branching conditional is complete. Because 
it's more likely (possibly mathematically certain) to catch all 
problems, these statements are "reheated" in reverse order. My 
reasoning for this is to keep compiler passes to a minimum, to 
save compilation time. In theory, all the scope assignments could 
be traversed again and again, until no scope was left unturned, 
so to say, but I wanted to come up with something with what you 
call an O(1) compilation time.

Honestly, it's almost impossible to say what the tax in 
compilation time will be until something's implemented (something 
I learned from Walter).

> How exactly the scope of a complex expression has to be 
> computed is left open here.

If you call a function, the return value (if a reference) will 
have a scope which can be deduced from the function signature. 
You inherit the scope of what you pass accordingly, and pass 
those scopes on to the next function (if you're in a function 
chain), or the "out!" parameters, if need be:

T* fun(return T* a, T* b, out!b T** c); // signature only

void gun() {
   T e; // local
   T* f;
   T** g = new T*;
   f = fun(&e, f, g); // f inherits scope of(&e), g inherits f
}

The results of a called function are just inherited as indicated 
by the function signature. I don't know what other kinds of 
"complex expression" you are referring to.

> In the end, if there was no error, all variables, parameters 
> and the return value will have a minimum reference scope 
> assigned. If that scope is the variable itself, they can be 
> inferred as `scope`. If it is a parameter, that parameter get 
> an `out!identifier` or `return` annotation.

The function's final return scope is used to assign "return" to 
the parameter attributes for the final function signature, in the 
case of attribute inference, and the parameter attributes are 
used to deduce the return scope when the function is called.

> Note that the order in which the "assignments" occur inside the 
> function doesn't matter. This is more restrictive than strictly 
> necessary, but it's certainly ok in most cases, easy to work 
> around when not, and it doesn't require data/control flow 
> analysis.

This is different from my proposal. I aim to just go in lexical 
order, with a little extra work done in when lexical order is 
detected as possibly being different from the logical order (in a 
conditional inside a loop).

> (By the way: inference cannot work for recursive functions.)

I would like to see a "best effort" approach taken for solving 
the problem of recursive function inference. I think a function 
should be considered "innocent until proven guilty" as regards 
'pure', for example. It's one of those things which seems like 
it's really hard to screw up. How could a function which is 
otherwise pure become impure just because it calls itself?

T hun(...) {
   [no impure code]
   hun(...);
   [no impure code]
}

I may be wrong, but I can't figure out how this function could 
magically become impure just because it calls itself. The same 
goes for the other attributes. And you can use the same trick, of 
pushing questionable expressions onto a stack or array, and just 
revisiting them at the end of the function to check for attribute 
violations. But I admit I don't really understand why attributes 
can't be inferred with recursive calls in the general case. Maybe 
somebody can explain to me what I'm missing here.

> Your example:
>
> T* fun(T* a, T** b) {
>     // => S(a) = a
>     // => S(b) = b
>     // => S(return) = <doesn't matter>
>     T* c; // == (T*).init == null
>     // => S(c) = c
>     c = new T;
>     // `new` returns static, which is wider than c

`c's reference hasn't been assigned until now, so it's neither 
wider nor narrower. We're not tracking null references yet, so 
I'm just treating them like they're global.

>     // => S(c) = static
>     c = a;
>     // => invalid, narrowing not allowed
>     // (this is what I asked about, and now I
>     // see why it's necessary)

Actually this is fine, I think. Even if `c` inherited something 
narrower than "new T" (i.e. depth 1), it would be fine, because 
it would now be considered depth(1) and could no longer be copied 
to anything with depth <1. It might or might not store a global, 
but for safety reasons it must now be treated with the narrowest 
it could possibly have. The error now would be if you copied it 
*back* to a parameter or a global. (Difference between `c's 
declaration scope `&c` = (1), and its reference scope = null, 
until otherwise assigned.)

>     // let's assume it didn't happen, so that
>     // the next two statements work
>     *b = c;
>     // => S(b) = S(c) = static
>     return c;
>     // => S(return) = S(c) = static
> }

This would be fine, since your code only has a `new T` and a `T*` 
parameter copied to c so far. In the case of inference, the 
function now infers: "T fun(return T* a, out!a T** b)". In the 
absence of inference, it gives errors on both counts (in @safe 
code of course, as always). And we're not tracking null yet 
(which is a different issue), so I won't worry about that. Also, 
in non-branching code, the compiler could actually know that c 
was no longer null at this time.

> Something else that needs consideration: What happens when 
> parameters alias each other? I think it is ok, because the 
> checking phase will naturally prohibit calling functions in a 
> way that would break the guarantees, but I haven't thought it 
> through completely.

I'm not sure what you mean. I don't think it's a problem.

>> I'm actually thinking of reusing `noscope` as a function 
>> attribute (`@noscope` perhaps) which says that the function 
>> may return a heap or global reference. This is all that's 
>> necessary to complete an ownership system. If a scope has 
>> exactly 1 "mystery" bit set, and is known not to come from the 
>> heap or a global, then you know that it *must* contain a 
>> reference to exactly the parameter for which the mystery bit 
>> is set. You know exactly what it contains == ownership.
>
> I will have to think about this, but I believe you cannot 
> express such concepts as deadalnix's islands, or "const 
> borrowing". But maybe, if we're lucky, I'm wrong :-)

We'll see!