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.

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 does do NLL, and uses Data Flow Analysis to achieve it.

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.

Your proposal requires tracking which pointers are heap-allocated and which are not. This would be quite difficult to do in D with its current design.

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.

On 4/15/2020 7:39 PM, Timon Gehr wrote:
> On 14.04.20 12:18, Walter Bright wrote:
>> does do NLL, and uses Data Flow Analysis to achieve it.
> Do you have an example where that helps?

int* malloc();
void free(int*);

@live void test()
{
    auto p = malloc(); // p is owner
    *p = 1;
    scope q = p; // q borrows p
    int x = *q;  // read from borrow
    *p = 2;      // using p again ends lifetime of q, even though q is in scope
    x = *q;      // error, q is no longer valid
    free(p);
}


> 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);
> }

You're right that taking the address of a local currently results in an owning pointer. I'll think about the best way to deal with this. Though note that if @safe is also added to the function, taking the address of a local is disallowed.

On 16.04.20 10:40, Walter Bright wrote:
> On 4/15/2020 7:39 PM, Timon Gehr wrote:
>> On 14.04.20 12:18, Walter Bright wrote:
>>> does do NLL, and uses Data Flow Analysis to achieve it.
>> Do you have an example where that helps?
> 
> int* malloc();
> void free(int*);
> 
> @live void test()
> {
>      auto p = malloc(); // p is owner
>      *p = 1;
>      scope q = p; // q borrows p
>      int x = *q;  // read from borrow
>      *p = 2;      // using p again ends lifetime of q, even though q is in scope
>      x = *q;      // error, q is no longer valid
>      free(p);
> }
> ...

Thanks! (However, this would still be so much better if ownership was opt-in at the type level instead of using function annotations.)

> 
>> 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);
>> }
> 
> You're right that taking the address of a local currently results in an owning pointer. I'll think about the best way to deal with this.

The owner is the local variable and the pointer should borrow from it.

> Though note that if @safe is also added to the function, taking the address of a local is disallowed.
> 

I assumed -dip1000. Anyway, if you add @safe, @live usually becomes essentially useless.

https://issues.dlang.org/show_bug.cgi?id=20747

On 4/19/2020 2:16 AM, Walter Bright wrote:
> https://issues.dlang.org/show_bug.cgi?id=20747

which was fixed