Alternative to Rust's borrow checking and explicit lifetimes?

[Timon Gehr]

On 14.04.20 12:18, Walter Bright wrote:
> On 4/13/2020 11:18 PM, lstfmk wrote:
>> While learning Rust, I came up with an alternative strategy to prove 
>> memory safety. So I created this thread on the Rust user forums:
>> https://users.rust-lang.org/t/alternative-to-borrow-checking-and-explicit-lifetimes/40906 
>>
>>
>> The post is a rough sketch of my strategy and is certainly could be 
>> more thorough. It is intentionally so such that you get a gist of the 
>> strategy. Though I am certain D could not implement this without 
>> breaking backward compatibility by a huge margin, I post here just so 
>> that it could be at least considered as I've heard that work on a 
>> lifetime/borrowing system is going on to be included in D.
>>
>> My strategy doesn't impose any borrow restrictions and doesn't require 
>> explicit lifetime annotations at all, while seeming to provide the 
>> same guarantees that Rust's borrow checker currently provides. 
>> Currently, the borrow checker imposes the limit that you can have 
>> either one mutable reference to an object (or) multiple immutable 
>> references to the object. This exclusiveness currently makes Rust feel 
>> very restrictive, not to mention explicit lifetime annotations.
>>
>> Regarding analysis complexity, I suspect my strategy is much simpler 
>> than Rust's current borrow checker since it works with scope-based 
>> lifetimes very well. Rust's technique is to lower the Rust code to a 
>> middle-level IR to take into account what is called non-lexical 
>> lifetimes(NLL) which are inferred using some sort of liveness 
>> analysis. This NLL consideration was added 2 years ago before which 
>> Rust was even more restrictive.
> 
> Thank you for posting this, it's good to see more effort in this direction.
> 
> D's current Ownership/Borrowing system

I would not call it that. It does not currently enforce ownership or 
borrowing invariants.

> does do NLL, and uses Data Flow Analysis to achieve it.
> ...

Do you have an example where that helps? Testing with DMD 2.091.0, it 
does not seem possible to encode the simple examples on 
https://doc.rust-lang.org/edition-guide/rust-2018/ownership-and-lifetimes/non-lexical-lifetimes.html

void ignore(int* p){}
void main()@live{
     int x=5;
     auto p=&x;
     x=3; // should fail, but compiles
     *p=4;
     ignore(p); // not necessary in Rust
}

void ignore(int* p){}
void main()@live{
     int x=5;
     auto p=&x;
     *p=4;
     x=3;
     ignore(p); // not necessary in Rust
}

Maybe the problem is that taking a local variable's address results in 
an owning pointer instead of a borrowing pointer, but that would not 
make any sense. How can a pointer ever own stack memory? Also, it 
appears that in a @safe function, it is impossible to ever dispose of 
such a pointer as it is both `scope` and has to be freed explicitly.

@live also allows the address of the same local variable to be taken 
multiple times:

void main()@live{
     int x=5;
     auto p=&x;
     auto q=&x;
     *p=4;
     *q=5;
     writeln(*p," ",*q);
     ignore(p);
     ignore(q);
}

> Like Rust, D's O/B checking is done on a per-function as a whole basis, 
> and relies on the function signatures being correct.
> ...

Rust _checks_ that the function signatures are correct and lifetime 
annotations allow the analysis to remain precise when it crosses 
function boundaries.