4 ms·

The borrow checker within

201 points by yurivish 2y ago

yuvadam 2y ago
I really enjoyed this post, resonates with many small experiences I had learning the various patterns that do and don't work in Rust. Also blows my mind how crazy complex these language design topics are.
Animats 2y ago
Good to see this. "There is another theme running through here: moving the borrow checker analysis out from the compiler’s mind and into types that can be expressed. Right now, all types always represent fully initialized, unborrowed values. There is no way to express a type that captures the state of being in the midst of iterating over something or having moved one or two fields but not all of them. These changes address that gap." I have some misgivings about trying to do everything with types. That leads to having to perform complex, hard to understand operations on types, as you add and remove restrictions. Keeping borrowing orthogonal from types may be clearer. Not sure about this, though. I'd like to see back references addressed, so structs can have references to their owners. General concept: when possible, do statically what Rc, Weak, and .borrow() can do for backlinks at run time. Such static analysis seems possible for non-mutable references. Mutable is going to be tough, though. It's a lot like compile-time single-lock deadlock detection, where you try to check that the same lock is never locked twice in nested contexts.
- gpm 2y ago
  Immutable back references seem limiting... because how are you inserting things if you have a reference saying the thing you are inserting it into can't mutate. If you're willing to use locks or something for interior immutability though... I think it should already be possible. It works in a toy example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=faed8b1f5298ccf0f9a9a8f86bbbc6e1 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - Animats 2y ago
    Right. You can also do that with Rc and borrow. When nothing in the call tree is using the parent link, it should be OK to add children. That's potentially checkable at compile time.
    - Animats 2y ago
      Thinking about this some more, that example has a mutex in a single thread program. If it's ever reached while locked, the program is stuck. This is a demonstration that the backlink problem and single-thread deadlock detection are equivalent. Work on compile time deadlock detection for Rust is underway.[1] It's complicated, but do-able. [1] https://github.com/hlisdero/cargo-check-deadlock https://github.com/hlisdero/cargo-check-deadlock
- pas 2y ago
  As far as I understand lifetimes are already in the types, just elided most of the time. (That said, the type system is already full of marker traits, so keeping complexity from growing more and more is always an important goal. Hooweeever, this also means that people are pretty used to markers, so their individual cost is amortized over all of them basically. And adding one more might make sense, especially if it can be elided in general.)
Georgelemental 2y ago
Previously: https://news.ycombinator.com/item?id=40553643 https://news.ycombinator.com/item?id=40553643
tmpfs 2y ago
These are some really good suggestions. I think a "syntax for lifetimes on places" (2) is really neat and would make lifetimes much easier to reason about, by removing the indirection and being explicit about where the borrow is from in the declaration makes the intention much clearer. But my personal favorite is the point about "internal references" as I struggled with this a couple of times. I think this would be an excellent improvement. In the end I used ouroborous [1] to achieve this but having it built in to the language would be excellent. [1] https://docs.rs/ouroboros/latest/ouroboros/ https://docs.rs/ouroboros/latest/ouroboros/
aabhay 2y ago
It would be cool to annotate the lifetime using this syntax instead: -> &map’s mut V The apostrophe here matches the syntax of lifetimes roughly and to me makes it EXTREMELY clear whats going on.
superb_dev 2y ago
I wanted to share a technique I saw recently related to a post linked within this post: https://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/ https://smallcultfollowing.com/babysteps/blog/2015/04/06/mod... > The primary disadvantage comes about if you try to remove things from the graph. The problem then is that you must make a choice: either you reuse the node/edge indices, perhaps by keeping a free list, or else you leave a placeholder. There’s another option, called generational indices! I discovered this from the “generational_arena” crate: https://docs.rs/generational-arena/latest/generational_arena/ https://docs.rs/generational-arena/latest/generational_arena...
- alexisread 2y ago
  This looks the same as in Vale? I like this technique, and Vale tries to go further with index elision to remove the memory and checking overhead. https://verdagon.dev/grimoire/grimoire https://verdagon.dev/grimoire/grimoire
pjmlp 2y ago
While I welcome the effort going into improving the lifetimes experience in Rust, this also kind of reflects that the approach being taken by other languages, meaning keeping automatic memory management by default, and only enough affine/linear typing support for when performace really, really matters, is a more productive approach. Examples of that approach, D, Swift, Chapel, Linear Haskell, OCaml Effects. The changes on the article, while welcomed in the context of Rust typesystem, will make being aware of all borrow check rules even more complex, and back into language lawyers kind of C++ developer experience, unless backed up by IDE tooling, on when to write what suggestions.
- pornel 2y ago
  > Unfortunately, most people seem to have taken the wrong lesson from Rust. They see all of this business with lifetimes and ownership as a dirty mess that Rust has had to adopt because it wanted to avoid garbage collection. But this is completely backwards! Rust adopted rules around shared mutable state and this enabled it to avoid garbage collection. These rules are a good idea regardless https://without.boats/blog/references-are-like-jumps/ https://without.boats/blog/references-are-like-jumps/ Ownership and borrowing are very useful regardless of performance and memory management. They help to reason about the program, enabling local reasoning instead of global. When your function gets an owned object or exclusive reference, you know nothing else will mutate it (and you get that without resorting to purity/immutability). You don't need defensive copies. In your methods you can return temporary references to internal objects, and you don't have to worry that users will keep them too long (such as use a handle to a resource after you close/delete the resource). There are many useful patterns that can be expressed with control over sharing, copying, and mutability, and memory management is just one of them.
  - pjmlp 2y ago
    Hence why the sweet spot is to combine automatic resource management, with affine, linear, and effect type systems. As those languages are doing.
    - nequo 2y ago
IshKebab 2y ago
These would be very welcome changes. How do self references work when the struct is moved, given that they're pointers? Also I'm not sure about having a feature that only works for private functions. I can imagine that would be very weird and annoying. I think it would be fine if it were allowed for public functions too, we just need better built in tooling to warn you about API breaking changes. After all you can already break API compatibility in obvious and very subtle ways. It would be great if Rust said something like "this is an API incompatible change; you need to increase the version number". I think there are third party tools that try to do that but it would be great if it was first party.
- alkonaut 2y ago
  > How do self references work when the struct is moved, given that they're pointers? Are all references necessarily (global) pointers? Couldn't self references be offsets?
  - Rusky 2y ago
    Yes, they are necessarily global pointers. If a self reference is an offset, what happens when you take its address (and pass that somewhere else that doesn't know where it came from)? Now every "reference to a reference" (and similar things) can dynamically be a global pointer or a relative one, with no way to tell how to use it.
    - alkonaut 2y ago
      Am I necessarily always allowed to convert a reference to a numeric address?
      - Rusky 2y ago
        Yes, it's safe to cast a reference to a raw pointer and a raw pointer to an address. It might have been nicer in some ways if the language had restricted that a bit more up front, but it would probably have taken some design work to do that while still supporting a lot of the low-level stuff people need to do.
conaclos 2y ago
View types make me think of the modifies clause introduced by some verification tools and in an earlier specification of Eiffel [1]. Basically the clause allows you to list the fields that are affected by a function with mutations. [1] https://bertrandmeyer.com/2011/07/04/if-im-not-pure-at-least-my-functions-are/ https://bertrandmeyer.com/2011/07/04/if-im-not-pure-at-least...
cassepipe 2y ago
I am not well versed in Rust so I can't judge the design decisions fairly but I do find that cpp2's in, out, inout, move and forward keywords for functions arguments much easier to follow mentally that rust's lifetime annotations : https://youtu.be/6lurOCdaj0Y?feature=shared&t=3076 https://youtu.be/6lurOCdaj0Y?feature=shared&t=3076 We can do the same kind of (basic?) borrow checking with those can't we ?
- CryZe 2y ago
  No, from a quick glance those are only for moves of individual values. Lifetimes are something different. They are used for relating multiple (> 1) parameters / return values with each other. There is no way to have that without having a syntax for it. It's important to note that lifetimes are not just for the compiler. They are also documentation / API contracts: fn add_to_vec<'a>(element: &'a str, vec: &mut Vec<&'a str>) { ... } This documents that the vec passed into the function can't outlive the element that's passed in. That's because the string (a reference (pointer) to the string data) that's passed in gets stored in the vec. So freeing the string and then using the vec would result in a use after free. You can't have this power without a syntax for it. You could of course do some global analysis, but now you can't have API contracts like this anymore, which are important for semantic versioning. An alternative syntax a language could use would be to have arbitrary pre- and post-conditions that the compiler can verify, which would be a whole lot more powerful, but also a lot more wordy than the short lifetime "tags" that Rust uses.
- kibwen 2y ago
  Lifetimes in Rust are about giving you the ability to say "I have a reference, and I may not know exactly how long the underlying data may live for, but I do know that it will last for at least as long as this other thing". So for example: fn get_reference_to_first_element(x: &[u8]) -> &u8 { return &x[0] } There are lifetimes here that express that the reference that is returned from this function will live as long as the reference that was passed in. In cases like this where the association is obvious, the lifetimes are implied and you don't need to write them. The desugared form looks like this: fn get_reference_to_first_element<'a>(x: &'a [u8]) -> &'a u8 { return &x[0] } Lifetimes are present on structs for the same reason. A system that is limited to annotating only function input parameters would be limited to inferring the programmer's intent everywhere, which limits its utility to simple cases (which might be fine for some languages, but I suspect will not satisfy C++). In addition, from glancing briefly at that video, it seems as though those five keywords seem to be more concerned with ensuring use-after-initialization, whereas Rust's lifetime system is about preventing use-after-free.
yencabulator 2y ago
Leave it to emojis to ruin communication: // A thread to consume those values: std:<emoji here censored by hn>:spawn(move || {

201 points by yurivish 2y ago

I really enjoyed this post, resonates with many small experiences I had learning the various patterns that do and don't work in Rust. Also blows my mind how crazy complex these language design topics are.

Animats 2y ago

Good to see this. "There is another theme running through here: moving the borrow checker analysis out from the compiler’s mind and into types that can be expressed. Right now, all types always represent fully initialized, unborrowed values. There is no way to express a type that captures the state of being in the midst of iterating over something or having moved one or two fields but not all of them. These changes address that gap." I have some misgivings about trying to do everything with types. That leads to having to perform complex, hard to understand operations on types, as you add and remove restrictions. Keeping borrowing orthogonal from types may be clearer. Not sure about this, though. I'd like to see back references addressed, so structs can have references to their owners. General concept: when possible, do statically what Rc, Weak, and .borrow() can do for backlinks at run time. Such static analysis seems possible for non-mutable references. Mutable is going to be tough, though. It's a lot like compile-time single-lock deadlock detection, where you try to check that the same lock is never locked twice in nested contexts.

gpm 2y ago
Immutable back references seem limiting... because how are you inserting things if you have a reference saying the thing you are inserting it into can't mutate. If you're willing to use locks or something for interior immutability though... I think it should already be possible. It works in a toy example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=faed8b1f5298ccf0f9a9a8f86bbbc6e1 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- Animats 2y ago
  Right. You can also do that with Rc and borrow. When nothing in the call tree is using the parent link, it should be OK to add children. That's potentially checkable at compile time.
  - Animats 2y ago
    Thinking about this some more, that example has a mutex in a single thread program. If it's ever reached while locked, the program is stuck. This is a demonstration that the backlink problem and single-thread deadlock detection are equivalent. Work on compile time deadlock detection for Rust is underway.[1] It's complicated, but do-able. [1] https://github.com/hlisdero/cargo-check-deadlock https://github.com/hlisdero/cargo-check-deadlock
pas 2y ago
As far as I understand lifetimes are already in the types, just elided most of the time. (That said, the type system is already full of marker traits, so keeping complexity from growing more and more is always an important goal. Hooweeever, this also means that people are pretty used to markers, so their individual cost is amortized over all of them basically. And adding one more might make sense, especially if it can be elided in general.)

Georgelemental 2y ago

Previously: https://news.ycombinator.com/item?id=40553643 https://news.ycombinator.com/item?id=40553643

tmpfs 2y ago

These are some really good suggestions. I think a "syntax for lifetimes on places" (2) is really neat and would make lifetimes much easier to reason about, by removing the indirection and being explicit about where the borrow is from in the declaration makes the intention much clearer. But my personal favorite is the point about "internal references" as I struggled with this a couple of times. I think this would be an excellent improvement. In the end I used ouroborous [1] to achieve this but having it built in to the language would be excellent. [1] https://docs.rs/ouroboros/latest/ouroboros/ https://docs.rs/ouroboros/latest/ouroboros/

aabhay 2y ago

It would be cool to annotate the lifetime using this syntax instead: -> &map’s mut V The apostrophe here matches the syntax of lifetimes roughly and to me makes it EXTREMELY clear whats going on.

superb_dev 2y ago

I wanted to share a technique I saw recently related to a post linked within this post: https://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/ https://smallcultfollowing.com/babysteps/blog/2015/04/06/mod... > The primary disadvantage comes about if you try to remove things from the graph. The problem then is that you must make a choice: either you reuse the node/edge indices, perhaps by keeping a free list, or else you leave a placeholder. There’s another option, called generational indices! I discovered this from the “generational_arena” crate: https://docs.rs/generational-arena/latest/generational_arena/ https://docs.rs/generational-arena/latest/generational_arena...

alexisread 2y ago
This looks the same as in Vale? I like this technique, and Vale tries to go further with index elision to remove the memory and checking overhead. https://verdagon.dev/grimoire/grimoire https://verdagon.dev/grimoire/grimoire

pjmlp 2y ago

While I welcome the effort going into improving the lifetimes experience in Rust, this also kind of reflects that the approach being taken by other languages, meaning keeping automatic memory management by default, and only enough affine/linear typing support for when performace really, really matters, is a more productive approach. Examples of that approach, D, Swift, Chapel, Linear Haskell, OCaml Effects. The changes on the article, while welcomed in the context of Rust typesystem, will make being aware of all borrow check rules even more complex, and back into language lawyers kind of C++ developer experience, unless backed up by IDE tooling, on when to write what suggestions.

pornel 2y ago
> Unfortunately, most people seem to have taken the wrong lesson from Rust. They see all of this business with lifetimes and ownership as a dirty mess that Rust has had to adopt because it wanted to avoid garbage collection. But this is completely backwards! Rust adopted rules around shared mutable state and this enabled it to avoid garbage collection. These rules are a good idea regardless https://without.boats/blog/references-are-like-jumps/ https://without.boats/blog/references-are-like-jumps/ Ownership and borrowing are very useful regardless of performance and memory management. They help to reason about the program, enabling local reasoning instead of global. When your function gets an owned object or exclusive reference, you know nothing else will mutate it (and you get that without resorting to purity/immutability). You don't need defensive copies. In your methods you can return temporary references to internal objects, and you don't have to worry that users will keep them too long (such as use a handle to a resource after you close/delete the resource). There are many useful patterns that can be expressed with control over sharing, copying, and mutability, and memory management is just one of them.
- pjmlp 2y ago
  Hence why the sweet spot is to combine automatic resource management, with affine, linear, and effect type systems. As those languages are doing.
  - nequo 2y ago

IshKebab 2y ago

These would be very welcome changes. How do self references work when the struct is moved, given that they're pointers? Also I'm not sure about having a feature that only works for private functions. I can imagine that would be very weird and annoying. I think it would be fine if it were allowed for public functions too, we just need better built in tooling to warn you about API breaking changes. After all you can already break API compatibility in obvious and very subtle ways. It would be great if Rust said something like "this is an API incompatible change; you need to increase the version number". I think there are third party tools that try to do that but it would be great if it was first party.

alkonaut 2y ago
> How do self references work when the struct is moved, given that they're pointers? Are all references necessarily (global) pointers? Couldn't self references be offsets?
- Rusky 2y ago
  Yes, they are necessarily global pointers. If a self reference is an offset, what happens when you take its address (and pass that somewhere else that doesn't know where it came from)? Now every "reference to a reference" (and similar things) can dynamically be a global pointer or a relative one, with no way to tell how to use it.
  - alkonaut 2y ago
    Am I necessarily always allowed to convert a reference to a numeric address?
    - Rusky 2y ago
      Yes, it's safe to cast a reference to a raw pointer and a raw pointer to an address. It might have been nicer in some ways if the language had restricted that a bit more up front, but it would probably have taken some design work to do that while still supporting a lot of the low-level stuff people need to do.

conaclos 2y ago

View types make me think of the modifies clause introduced by some verification tools and in an earlier specification of Eiffel [1]. Basically the clause allows you to list the fields that are affected by a function with mutations. [1] https://bertrandmeyer.com/2011/07/04/if-im-not-pure-at-least-my-functions-are/ https://bertrandmeyer.com/2011/07/04/if-im-not-pure-at-least...

cassepipe 2y ago

I am not well versed in Rust so I can't judge the design decisions fairly but I do find that cpp2's in, out, inout, move and forward keywords for functions arguments much easier to follow mentally that rust's lifetime annotations : https://youtu.be/6lurOCdaj0Y?feature=shared&t=3076 https://youtu.be/6lurOCdaj0Y?feature=shared&t=3076 We can do the same kind of (basic?) borrow checking with those can't we ?

CryZe 2y ago
No, from a quick glance those are only for moves of individual values. Lifetimes are something different. They are used for relating multiple (> 1) parameters / return values with each other. There is no way to have that without having a syntax for it. It's important to note that lifetimes are not just for the compiler. They are also documentation / API contracts: fn add_to_vec<'a>(element: &'a str, vec: &mut Vec<&'a str>) { ... } This documents that the vec passed into the function can't outlive the element that's passed in. That's because the string (a reference (pointer) to the string data) that's passed in gets stored in the vec. So freeing the string and then using the vec would result in a use after free. You can't have this power without a syntax for it. You could of course do some global analysis, but now you can't have API contracts like this anymore, which are important for semantic versioning. An alternative syntax a language could use would be to have arbitrary pre- and post-conditions that the compiler can verify, which would be a whole lot more powerful, but also a lot more wordy than the short lifetime "tags" that Rust uses.
kibwen 2y ago
Lifetimes in Rust are about giving you the ability to say "I have a reference, and I may not know exactly how long the underlying data may live for, but I do know that it will last for at least as long as this other thing". So for example: fn get_reference_to_first_element(x: &[u8]) -> &u8 { return &x[0] } There are lifetimes here that express that the reference that is returned from this function will live as long as the reference that was passed in. In cases like this where the association is obvious, the lifetimes are implied and you don't need to write them. The desugared form looks like this: fn get_reference_to_first_element<'a>(x: &'a [u8]) -> &'a u8 { return &x[0] } Lifetimes are present on structs for the same reason. A system that is limited to annotating only function input parameters would be limited to inferring the programmer's intent everywhere, which limits its utility to simple cases (which might be fine for some languages, but I suspect will not satisfy C++). In addition, from glancing briefly at that video, it seems as though those five keywords seem to be more concerned with ensuring use-after-initialization, whereas Rust's lifetime system is about preventing use-after-free.

yencabulator 2y ago

Leave it to emojis to ruin communication: // A thread to consume those values: std:<emoji here censored by hn>:spawn(move || {