Last time we talked about the broader problem that generators with references across yield points represent: self-referential structs. This time, I want to narrow in on the specific problem that needs to be solved to make generators work, and also discuss some ideas for solutions that I think are false starts.

(I still don’t have a proposal about what to do in this post, but it will come soon enough!)

What do generators require?

The generator feature is not as fully general as self-referential structs. Generators are functions that can yield their control flow; they are compiled into self-referential structs that fall into a particular pattern. This means that we don’t need to have the feature fully finished before we can ship generators; we just need to have a solution for the generator problem specifically which is forward compatible with general self-references.

In the reddit conversation around my previous post, jpernst made this astute observation:

The first step would be to borrow check the body of the generator/future as if it were a normal function (with possible extra consideration for the special semantics of yield, but even that might not be necessary). Once the body has been verified to be internally consistent, it can be lowered to a state machine enum.

If any self-ref lifetimes exist, then the state machine will be marked as an immovable type…

Setting aside any commentary about the exact mechanism, the core idea is this: you can basically ignore yields and borrow-check generators just as if they were normal functions; they will get compiled into an enum that may (if any of the lifetimes of references contained a yield statement) which is self-referential.

The major problem is then is what to do about your enum that may have self-references. jpernst proposes one solution: using the borrowchecker, check if the generator actually has self-references, and if it does, mark it as an immovable type. There are two steps to this proposal, and each raises a question:

1. Can we determine from the borrowchecker whether or not a generator contains self-references?
2. What does it mean for a type to be “immovable”?

Problem 1: Figuring out if a generator is self-referential

jpernst proposes a dynamic in which we borrowcheck a generator, and that gives us type information about whether or not the generator is immovable. This sounds great, unfortunately, it runs against how the compiler is actually implemented today.

rustc is designed around several phases. At a high level, first we parse, then we typecheck, then we borrowcheck, then we lower to LLVM’s representation. This property of immovability is a property of the value’s type, basing type information on the results of borrowcheck would be out of order.

In the limit, this may just not be possible - you may have a cyclic dependency, where borrowchecking needs to know if this type is immovable, but we don’t know if its immovable until we’ve finished borrowchecking.

More immediately, I promised that by the end of this series we’d have a solution that could be implemented this year. Determining if a generator is immovable from the borrowchecker, if its possible, requires significant rearchitecting of the compiler. That means its not possible to infer this fact in the near term.

The solution, then, is an annotation: depending on how the generator is annotated, we either disallow borrows across yields, or we treat the generator as immovable. Which type should be annotated vs default and what the annotation should be is a question for a later conversation, but this core insight remains: we need an annotation to distinguish movable and immovable generators.

Problem 2: Making a generator “immovable”

So we’ve determined that self-referential generator needs to be immovable, and we’ve even figured out that we need the compiler to know, up front, that the generators are immovable, based on some annotation. But we haven’t actually talked about what that means. What constraint would satisfy this immovability so that the generator works correctly?

As we discussed last time, the important problem we are trying to avoid is invalidating the references stored in the generator’s enum representation. If you call resume & it saves a reference, then you move the generator and call resume again, the reference has become invalidated and you’ve got some undefined behavior.

So whatever solution we need to find, the definition of immovability that it needs to satisfy is this: between the first time you call resume, and the time that resume “returns” (not “yields”), you can never move the generator.

That is to say, there is some “lifetime” for which the generator cannot move, and somehow the generator’s type signature needs to tie together that lifetime.

Solutions that haven’t panned out

Having laid out the problem precisely, I want to discusss some solutions that we’ve looked at, but which we are currently skeptical of. These solutions have seemed promising, and people have gotten quite excited by them, but right now we do not see them as a viable, near term resolution to the problem.

?Move

The solution that’s gotten the most attention is what’s called “question mark Move.” In this proposal, we would add a new trait to Rust called Move. Like Sized, types would implement this trait by default, and all type parameters would be implicitly bound T: Move.

Exactly what Move means is kind of confusing, and its actually the inversion of it !Move that is easier to explain: if a type does not implement Move, once you have taken a reference to it, it can never be moved from its current location until it is dropped. Types that implement Move do not have this restriction.

This restriction satisfied the requirement of immovable generators (its technically more strict than it needs to be, but once you’ve finished running a generator, there’s nothing to do wit it but drop it). That said, we’ve run into a few problems with ?Move that prevented it from being implemented, even exprimentally.

First, we are not certain that Rust can afford another of these question mark traits at all, in terms of complexity. This RFC issue lays out some of the reasoning. Question mark traits make a certain question everyone’s problem instead of only the people who care about it - now every time you use a type parameter, you have to ask: do I really need this type to be movable after it has been referenced? This is a pretty nuanced question to make every user ever ask about their generic parameters. It also means there is more superfluous data in the APIs of different libraries. Can we really afford for the Q parameter of HashMap::get to become Q: ?Sized + ?Move + Hash + Eq? The existence of the Q parameter at all is pretty confusing.

Second, even if you think - well, we already have Sized, what’s the harm in adding one more, there are real backwards compatibility problems for ?Move. The most pressing is the return type of functions and closures. Generators are written as functions that return a type that implements Generator. If this generator is immovable, it might not implement Move. This means that the associated Output type on the Fn traits must be bound ?Move, because some functions return types that don’t implement Move. Unfortunately, there is a lot of code that exists which currently assumes that they can move the return type of generic closures freely. This breakage seems far beyond the kind of bug fixes and type inference issues that we would normally abide, and it is the kind of core logic change that an epoch does not allow us to do.

Finally, Move is not really forward-looking to arbitrary self-references. As I noted earlier, there is in some sense a particular lifetime for which generators cannot be moved. For other self-referential types, they may follow a different pattern, in which that lifetime ends, but there are other things you can still do with them - in other words, they are locked in place only for a while, but can be moved again later. Move has no concept of a lifetime for its anchoring, its just anchored as soon as you ever observe the location of the type.

Offset-based solutions

Another solution - and I was surprised to discover last week that this solution is so popular - is to represent self-references as offsets, rather than addresses. Because the references are offsets relative to the address of the struct that contains them, this sidesteps the problem of immovability - you can move them, because that won’t invalidate the references. This solution sounds great at first, but we are extremely pessimistic about its general viability.

First, it is not just references we have to deal with, but any type that is parameterized by a lifetime. An Iter<'a, u8> pointing to an array in the same struct is just as self-referential as an &'a u8 pointing to that array. We would need to determine whether each lifetime is “self-referential,” then recompile every lifetime-parameterized type.

First, this is assuming that we can determine self-referential references based solely on their lifetime. This is uncertain. Consider subtyping, for example. A reference with this 'self lifetime could be coerced to any shorter lifetime inside the function, how do we keep tracking that this reference is self- referential once its been subtyped to a lifetime which is not 'self? Do we calculate the true address when we subtype? What if a reference that lives longer than 'self gets coerced down to 'self? What if a non-self-referential reference gets subtyped to 'self, then subtyped to a shorter non-self-referential lifetime?

But even if we could implement this technically, this would impact code gen. Currently, lifetimes are erased prior to code generation; this is important for implementation complexity, for guaranteeing logical parametricity of lifetimes, and for compile times and code size. Any one of these is a good reason not to do this, but looking at the last alone - this would mean anything with a lifetime parameter (such as a function that takes a reference) would have to be monomorphized after finding out if that lifetime is self-referential; very little code would avoid monomorphization in this situation.

This is not even getting into the problem with unsafe code. Today, it is perfectly valid to cast a reference to a raw pointer, manipulate it, and then cast back a reference to a different address. We have no idea if all the unsafe code that exists could be validly supported with this system, but we are doubtful that there is nothing widely used that would be invalidated by this.

Don’t get me wrong, we could probably have offset-based types. You could imagine an @T (no lifetime necessary) being an offset to a T inside the containing struct. But this doesn’t do anything to support generators, which use regular code with references and then compiles it a self-referential struct, and needs to support arbitrary reference-based code.

Conclusion

This post has been a bit pessimistic unfortunately, but its important to narrow down the problem and solution space before we go forward. We’ve got it down now to as small as it possibly could be: how do we handle a generator which cannot be moved while it is resuming? In the next post, I’ll get into how we could handle this problem in the near term.