www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Alternative to Rust's borrow checking and explicit lifetimes?

reply lstfmk <manikandanm330b gmail.com> writes:
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.
Apr 13 2020
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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-expl
cit-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.
Apr 14 2020
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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-expl
cit-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.
Apr 15 2020
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Apr 16 2020
parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Apr 16 2020
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
https://issues.dlang.org/show_bug.cgi?id=20747
Apr 19 2020
parent Walter Bright <newshound2 digitalmars.com> writes:
On 4/19/2020 2:16 AM, Walter Bright wrote:

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


which was fixed
Apr 20 2020