# Indirect borrows in generators **URL:** \ **Category:** language design\ **Created:** [March 29, 2023, 12:36am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594 "2023-03-29T00:36:53Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![davidlattimore](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/davidlattimore/32/5141_2.png) [@davidlattimore](https://internals.rust-lang.org/u/davidlattimore)\ **Post date:** [March 29, 2023, 12:36am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/1 "2023-03-29T00:36:53Z")
I read @withoutboats' [recent post about generators](https://without.boats/blog/generators/) and was thinking about cases where you might want to borrow over a yield point and what could be done about it. It seems to me that a lot of the cases that would be problematic would be when the generator owns some object that has data on the heap and wants to hold a non-consuming iterator over yield points. For example, you’ve got a String and want to hold a `Chars<'a>` iterator. e.g. ```rust gen fn foo(&self) -> Token { let s: String = self.to_string(); for ch in s.chars() { match ch { 'a' => yield Token::Something, … } } } ``` This isn’t valid because `s.chars()` returns a `Chars<'a>` which borrows `s` which is owned by the generator. However, it should actually be fine. Moving the generator will do nothing to the heap allocation of the `String` and we never mutate the String, so the references held by the `Chars<'a>` won’t be invalidated. What I’m wondering is, could the borrow checker be made smart enough to allow this? I was thinking of a special kind of “indirect borrow” that is like a regular borrow, but with the relaxation that a shared, indirect borrow can be held over a yield point. i.e. if `String::chars` returned a `Chars<'indirect a>` (or without a new keyword, `Chars<'*a>`) then the generator could be moved and the borrow over the yield permitted. Effectively, if the function passes the borrow checker as a regular (non-generator) function and also passes the additional requirement that only indirect borrows are held over yield points, then the generator passes the borrow checker. A fully general system (e.g. [this](https://internals.rust-lang.org/t/blog-post-indirect-ownership-shallow-borrow-and-self-referential-data-structures/16517)) that allowed arbitrary structs to take advantage of this in order to have self referential structs seems like it would add a lot more complexity to the syntax, but just limiting this to generators holding shared, indirect borrows seems more tractable to me. It would only require one new bit of syntax (declaring a lifetime as indirect). Changing an existing inherent method or function to mark its return lifetime as indirect, should I think be a non-breaking change. I guess one downside is that changing a trait method’s return type to an indirect lifetime would be a breaking change, so the return value from Deref::deref couldn’t be indirect - although you wouldn't want it to be indirect anyway, since that would prevent implementing Deref for anything that didn’t use heap allocation. If generators were stabilised with no support for borrowing over yields, something like this could be kept as a potential relaxation of that requirement if not allowing borrows over yields turned out to be too restrictive. ---
**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\ **Post date:** [March 29, 2023, 1:04am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/2 "2023-03-29T01:04:19Z")
One thing that would help here for `Deref` is "overconstrained impls," an RFC-accepted (IIRC, unfortunately don't have link) concept that you should be able to implement a trait with a stricter signature than the trait was declared with, and that users of the trait functionality on your concrete type can take advantage of that greater flexibility. Examples would be implementing an `unsafe` method as safe, returning `'static` instead of a limited lifetime, or this case of returning a heap borrow instead of an unrestricted borrow. Note I said heap borrow, though, instead of indirect; if you only require indirection, you run into the potential problem of smuggling through nonindirect borrows anyway, such as ```rust let x = ...; let a1 = &x; // direct borrow of x let a2 = &*a1; // indirect borrow through a1 ``` It _might_ be possible to track this properly, since a2 being live keeps a1 logically live. But it's complicated, because consider ```rust let x: String = ...; let a1 = &x; // direct borrow of x let a2 = String::chars(a1); // indirect borrow through a1 ``` This is exactly your example, but just the same involves taking an indirect borrow through a direct borrow. The difference is that the first case is (roughly) `&&T -> &T` where `T` is on the local stack, and the latter is (roughly) `&Box -> &T` and `T` is not on the local stack (it's on the heap). Then you also have the escape path of ```rust let x = ...; let a1 = Box::new(&x); let a2 = &*a1; let a3 = &**a2; ``` where you're putting a local reference onto the heap. So you're going to struggle with any methods on your indirectly borrowed structure, because its methods could potentially have access back to local data. At a minimum you'd need to extend lifetime subtyping such that `&'indirect short &'direct long _` cannot become `&'indirect short &'indirect short _` but only `&'direct short &'direct short _`. But this is a fractally complicated pit of edge cases that you need to find a system subset within that is probably sound. That's not going to be simple. ---
**Author:** ![cole-miller](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cole-miller/32/7607_2.png) [@cole-miller](https://internals.rust-lang.org/u/cole-miller)\ **Post date:** [March 29, 2023, 1:41am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/3 "2023-03-29T01:41:00Z")
> [@CAD97](#): > > One thing that would help here for `Deref` is "overconstrained impls," an RFC-accepted (IIRC, unfortunately don't have link) concept [RFC 3245](https://github.com/rust-lang/rfcs/pull/3245), right? ---
**Author:** ![davidlattimore](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/davidlattimore/32/5141_2.png) [@davidlattimore](https://internals.rust-lang.org/u/davidlattimore)\ **Post date:** [March 29, 2023, 1:46am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/4 "2023-03-29T01:46:39Z")
I was imagining that creating an indirect/heap borrow would be an unsafe operation and that it would only be done in low-level code. e.g. something like RawVec might provide a way to get a `&'heap a [T]`. Higher level APIs (in `Vec` and `String`) could then pass on that type. > So you're going to struggle with any methods on your indirectly borrowed structure, because its methods could potentially have access back to local data. Something like `Chars` holds no reference to the `String` that it came from - it only stores a slice into the String's heap allocation. So there would be no way for it to call methods on the `String`. If you did try to change `Chars` to hold a reference to the `String` as well as to the `String`'s heap storage, then the lifetime on the resulting `Chars` should have a regular, non-heap lifetime. ---
**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\ **Post date:** [March 29, 2023, 1:54am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/5 "2023-03-29T01:54:24Z")
> [@davidlattimore](#): > > Something like `Chars` holds no reference to the `String` that it came from - it only stores a slice into the String's heap allocation. This is true for this specific type, but it's only knowable because it's a completely concrete type. For something like `Box` you don't know what the `T` is, so you have to solve the problems there. Additionally, because covariant lifetimes can typically be collapsed together, most types will only carry multiple lifetimes if some of them are invariant (behind mut borrows). This means that most types won't be able to take advantage of indirect lifetimes without breaking changes to disentangle multiple disjoint borrows' lifetimes. > [@cole-miller](#): > > RFC 3245 That's the one, yep. ---
**Author:** ![davidlattimore](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/davidlattimore/32/5141_2.png) [@davidlattimore](https://internals.rust-lang.org/u/davidlattimore)\ **Post date:** [March 29, 2023, 1:56am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/6 "2023-03-29T01:56:38Z")
> [@CAD97](#): > > At a minimum you'd need to extend lifetime subtyping such that `&'indirect short &'direct long _` cannot become `&'indirect short &'indirect short _` but only `&'direct short &'direct short _`. I guess the simplest thing might be to say that the generator only allows `'indirect x` where `x` contains no non-static lifetimes. i.e. you can borrow data that's on the heap, but only if that data itself contains no further borrows. ---
**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\ **Post date:** [March 29, 2023, 3:05am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/7 "2023-03-29T03:05:23Z")
One more thought: this analysis already needs to basically exist at some basic level such that input references can be held over yield points. I don't recall whether the unstable semicoroutine syntax does this analysis (it supports defining both `static`/`!Unpin` and `Unpin` `impl Generator`), just trusts the developer to get it correct, or limits you even further to only `'static` types across `yield` points. ---
**Author:** ![withoutboats](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/withoutboats/32/4560_2.png) [@withoutboats](https://internals.rust-lang.org/u/withoutboats)\ **Post date:** [March 29, 2023, 10:46am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/8 "2023-03-29T10:46:37Z")
(NOT A CONTRIBUTION) > [@davidlattimore](#): > > What I’m wondering is, could the borrow checker be made smart enough to allow this? The answer is not necessarily "no" but it would require genuinely novel research. Right now the borrow checker does not have any notion of where a reference points, and has no real way to make the necessary distinction. > [@CAD97](#): > > One more thought: this analysis already needs to basically exist at some basic level such that input references can be held over yield points. I don't recall whether the unstable semicoroutine syntax does this analysis (it supports defining both `static`/`!Unpin` and `Unpin` `impl Generator`), just trusts the developer to get it correct, or limits you even further to only `'static` types across `yield` points. If the lifetime is external to the block it's permitted to be stored across yield points in a "static generator", but if it's a lifetime within the block it's not permitted. It's a really simple analysis today that could not support this. ---
**Author:** ![Jules-Bertholet](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jules-bertholet/32/10671_2.png) [@Jules-Bertholet](https://internals.rust-lang.org/u/Jules-Bertholet)\ **Post date:** [March 30, 2023, 3:52pm UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/9 "2023-03-30T15:52:22Z")
A related issue is how it's impossible to write a function that takes an exclusive borrow and returns a non-exclusive borrow. For example: ```rust fn to_shared(a: &mut u8) -> &u8 { a } fn main() { let mut i = 3; let mut ia = to_shared(&mut i); // There is no `&mut` around at this point, // but the following doesn't compile let mut ib = &i; dbg!(ia); } ``` ---
**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\ **Post date:** [March 30, 2023, 4:45pm UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/10 "2023-03-30T16:45:29Z")
This is just unsound, or you could call `get_mut` on a `RefCell`, convert that to a shared reference and then call `.borrow_mut()`, getting a shared and an exclusive reference at the same time. ---
**Author:** ![farnz](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/farnz/32/6587_2.png) [@farnz](https://internals.rust-lang.org/u/farnz)\ **Post date:** [March 30, 2023, 5:07pm UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/11 "2023-03-30T17:07:35Z")
Why would you be allowed to call `.borrow_mut()`? `get_mut` takes `&mut self`, and thus the lifetime analysis you'd need to do to make this even vaguely sound would say that the converted reference still has an exclusive borrow of the `RefCell` (but not of its contents), and thus you can't use the `&mut self` methods on `RefCell`. I'm not convinced that the analysis you'd have to do to have a sound way of doing this is worth doing (it's very non-trivial, and it runs the risk of breaking code that exploits the current rules), but you could do it soundly if you wanted to. ---
**Author:** ![davidlattimore](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/davidlattimore/32/5141_2.png) [@davidlattimore](https://internals.rust-lang.org/u/davidlattimore)\ **Post date:** [March 31, 2023, 12:04am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/12 "2023-03-31T00:04:34Z")
> [@withoutboats](#): > > The answer is not necessarily "no" but it would require genuinely novel research. Right now the borrow checker does not have any notion of where a reference points, and has no real way to make the necessary distinction. I wasn't imagining the borrow checker having to figure out where things point, so much as adding an extra boolean flag to borrows then making changes to the standard library to add that flag on selected borrows. The changes to the borrow checker would be around correctly handling supertype/subtype relationships between different borrows with and without that flag. > [@CAD97](#): > > ```rust > let x = ...; > let a1 = Box::new(&x); > let a2 = &*a1; > let a3 = &**a2; > > ``` Here's how I imagine that might work: ```rust let x = String::new(); let a1: Box<&'x String> = Box::new(&x); let a2: &'indirect(a1) &'x String = &*a1; let a3: &'x String = &**a2 ``` The type of `a2` says that it borrows the box (a1), but that it's indirect, so the Box can be moved (but not mutated) without invalidating `a2`. We've got a reference to a reference. The inner reference is what's in the box. The outer reference is pointing to the contents of the box. Nothing however is pointing at the `Box` itself, so moving the `Box` shouldn't be a problem for `a2`. We do however need to make sure that if we move the `Box`, that it continues to not be mutated, so wherever it gets moved would need to inherit the fact that there is a borrow of the Box's contents. In the case of generators, this can be achieved by running the borrow checker on the non-generator form of the generator function. `a3` however has dereferenced the indirect borrow, so now we only have the inner borrow, which isn't indirect. At that point only `x` is borrowed. ---
**Author:** ![crlf0710](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/crlf0710/32/1987_2.png) [@crlf0710](https://internals.rust-lang.org/u/crlf0710)\ **Post date:** [March 31, 2023, 11:05am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/13 "2023-03-31T11:05:38Z")
I believe this is a special case of lending generators(where the value yielded contains local borrows). Not sure what would it take to support this in the language, though. ---
**Author:** ![alice](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/alice/32/5044_2.png) [@alice](https://internals.rust-lang.org/u/alice)\ **Post date:** [April 3, 2023, 8:24am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/14 "2023-04-03T08:24:25Z")
> [@CAD97](#): > > One thing that would help here for `Deref` is "overconstrained impls," an RFC-accepted (IIRC, unfortunately don't have link) concept that you should be able to implement a trait with a stricter signature than the trait was declared with, and that users of the trait functionality on your concrete type can take advantage of that greater flexibility. Examples would be implementing an `unsafe` method as safe, returning `'static` instead of a limited lifetime, or this case of returning a heap borrow instead of an unrestricted borrow. Wait, hold on, this is already possible today with lifetimes. See [here](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=34f76543818d7b5ea17fce4f4fbf8dd1). ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [July 2, 2023, 8:25am UTC](https://internals.rust-lang.org/t/indirect-borrows-in-generators/18594/15 "2023-07-02T08:25:08Z")
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.