Issue with lifetimes, HRTBs, and GATs

help
#1

This is a little different than other examples of such issues that I've seen. See the playground I put together for the actual code and compiler error I'm running into.

You'll notice that the error has to do with a set of chained passes which take as input a mutable reference to a Function struct, and return the same reference when done with it. If you modify those same passes to instead take a Function by-value, everything compiles and works happily, so the error seems to be related to an inability of the compiler to match the lifetime of the actual reference to that expected by the passes. Interestingly, this only seems to come up when chaining more than two passes, a single chain'd pass works fine, it just becomes an issue when further passes are chained.

For context, what I was trying to accomplish was a trait that could represent compiler passes in different stages of my compiler, with the following properties:

  • Can represent passes which operate on by-value or by-reference inputs/outputs. In the latter case, the lifetime of the inputs/outputs would all be the same (i.e. you aren't changing the lifetime across passes, but rather chaining together passes which will be given a reference to some value and every pass will operate on that one reference, or alternatively taking a value by-reference and returning a new type by-value).
  • Can represent passes whose input/output is the same type or different types (e.g. when lowering to another representation, you might take AstType as input, and return IrType as output.)
  • Can be chained together to form pipelines of passes where the output of a pass is passed as the input to the next. This would allow you to represent a compiler as a series of passes which successively transform the input to some final output form.

I've worked around the issue by defining a secondary trait that specifically represents passes that take a mutable reference to some input, since I don't have any cases where I'm chaining those kind of passes with others that operate by-value, but nevertheless, I'd really like to better understand why I can't represent those types of passes using the same trait. As far as I can tell, the compiler should be able to infer that the passes all expect a reference of the same lifetime, but after banging my head against it for days, I think I've lost the ability to reason about it further.

I suspect this is related to #30472, but I'm not 100% sure on that, and it isn't clear to me if what I was aiming for is something the Rust compiler is intended to support or not. Anyway, hope some of you all may have more insight into this than me!

Paul

#2

In the playground you posted, this (a single chain) does give an error:

        let mut pass = AnalyzeFunction
            .combine(TypeCheckFunction);

(I made some lifetimes more descriptive...)

error[E0308]: mismatched types
   --> src/main.rs:148:14
    |
148 |             .combine(TypeCheckFunction)
    |              ^^^^^^^ lifetime mismatch
    |
    = note: expected mutable reference `&'comb mut Function`
                            found type `&mut Function`
note: the lifetime requirement is introduced here
   --> src/main.rs:19:64
    |
19  |         P: for<'comb> Pass<Input<'comb> = Self::Output<'comb>, Output<'comb> = T>,
    |                                                                ^^^^^^^^^^^^^^^^^

And getting rid of the problematic T was the fix:

     /// Chains two passes together to form a new, fused pass
-    fn combine<P, T>(self, pass: P) -> Chain<Self, P>
+    fn combine<P>(self, pass: P) -> Chain<Self, P>
     where
         Self: Sized,
-        P: for<'comb> Pass<Input<'comb> = Self::Output<'comb>, Output<'comb> = T>,
+        P: for<'comb> Pass<Input<'comb> = Self::Output<'comb>>,
     {

Because, I think, defining T outside the for<'comb> made it unrestrained wrt. lifetimes.

That allows one call to chain, but not a second, which is what I expected from the beginning given your description. I'm still playing, but the discrepancy between your description and the behavior seemed worth noting in the meanwhile.

#3

@quinedot Ah, thanks for catching that, I had been fiddling with things a bit while constructing the playground example, and must've missed that change when testing things out, sorry about that! I've tried so many variations on solutions to this that it all kind of muddles together after a certain point :sweat_smile:

In any case, luckily you were able to reproduce the working code for a single chained pass with references, as well as the same error I was seeing when trying to chain another pass of the same type. That's really where I hit a dead end, and I think #34430 may be another issue which relates to this.

I think this is a compiler bug, or at least a gap in its current implementation of HRTBs + GATs. That said, I'm also not 100% confident that I haven't just missed something, or that it isn't just a misunderstanding on my part of how those two features interact.

#4

The implementation of Pass for Chain had the same general problem as was on combine. Just so you can see how I proceeded, I first tried this variation that, well, chains the lifetimes together more directly, hoping to guide the compiler:

impl<T, V, A, B> Pass for Chain<A, B>
where
    A: for<'a> Pass<Input<'a> = T>,
    B: for<'a> Pass<Input<'a> = <A as Pass>::Output<'a>, Output<'a> = V>,
{
    type Input<'inp> = <A as Pass>::Input<'inp>;
    type Output<'out> = <B as Pass>::Output<'out>;

    fn run<'a>(&mut self, input: Self::Input<'a>) -> Result<Self::Output<'a>, ()> {
        let u = self.a.run(input)?;
        self.b.run(u)
    }
}

The errors were reduced but we still get:

    = note: the following trait bounds were not satisfied:
            `<AnalyzeFunction as Pass>::Input<'a> = _`
            which is required by `Chain<AnalyzeFunction, TypeCheckFunction>: Pass`
            `<TypeCheckFunction as Pass>::Output<'a> = _`
            which is required by `Chain<AnalyzeFunction, TypeCheckFunction>: Pass`

And I think, basically, the compiler tries to find a single, static type for T and V here, and can't reconcile that with the GAT type constructor, just like with combine originally.

The fix is the same as with combine, get rid of these underconstrained(?) type parameters that you don't actually need (and I was no longer using in the intermediate attempt):

impl<A, B> Pass for Chain<A, B>
where
    A: for<'a> Pass,
    B: for<'a> Pass<Input<'a> = <A as Pass>::Output<'a>>,
{
    type Input<'inp> = <A as Pass>::Input<'inp>;
    type Output<'out> = <B as Pass>::Output<'out>;

    fn run<'a>(&mut self, input: Self::Input<'a>) -> Result<Self::Output<'a>, ()> {
        let u = self.a.run(input)?;
        self.b.run(u)
    }
}

Playground.

#5

In brief reflection, I'm going to posit a guideline here. The working implementation looked like so:

impl<A, B> Pass for Chain<A, B> where // ...

And the non-working ones looked like so:

impl<T, V, A, B> Pass for Chain<A, B> where // ...
impl<T, U, V, A, B> Pass for Chain<A, B> where // ...

The latter two were only allowed because the "extra" type parameters were constrained by being part of the associated types of A and B. That is, T and U were considered "outputs" of A, and U and V were considered "outputs" of B. Otherwise you would have gotten an error about an unconstrained type parameter on an implementation, because coherence wants at most one implementation per parameter-resolved trait+type:

error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predicates

And the guideline is -- if you can avoid such "extra" type parameters that are only bound under a GAT (vs. plain associated type), you should. Try to thread the information through the type parameters that are part of the trait or implementing type, like the solution here did. Otherwise you may be trying to pull information sensible within the GAT (where the GAT parameters are defined) to a level where they are not sensible (the entire implementation).

So I don't think this is actually a normalization issue, I think it's a problem of trying to use a type parameter (which represents a static type) when you need a type constructor (like a GAT is). More concretely, you have:

impl Pass for AnalyzeFunction {
    type Input<'a> = &'a mut Function;
    type Output<'a> = &'a mut Function;
}
impl Pass for TypeCheckFunction {
    type Input<'a> = &'a mut Function;
    type Output<'a> = &'a mut Function;
}

And while it's true that

// Made up syntax that does not compile for brevity
for<'any> AnalyzeFunction::Output<'any> = TypeCheckFunction::Input<'any>

There is no single T that can represent every possible &'? mut Function. This is definitely true when you look at something like

// Implied: T and V are each a single, static type
impl<T, V, A, B> Pass for Chain<A, B> where /* ... */ {
    type Input<'inp> = T;  // And thus these cannot differ based
    type Output<'out> = V; // on the lifetime parameter
}

But is unsatisfiable even when it's just part of a bound:

// Fails as `AnalyzeFunction` needs a different `T` for each `'a`
where A: for<'a> Pass<Input<'a> = T>,

For it to work, you'd need a "type constructor parameter" T<'a>, or higher-kinded types, or something like that.

Hopefully we get compiler diagnostics that point this out.

#6

@quinedot That actually makes a ton of sense, definitely see where my mental model had a gap around this. I had it in my head that those type parameters were needed and completely missed trying to thread them through the trait's associated types like you suggested, e.g. type Input<'a> = <A as Pass>::Input<'a>, likewise on the signature of combine. While I'd love better compiler diagnostics around this, I have to imagine it is non-trivial once you get into some of these corner cases, so I'm just happy to know how to reason about this stuff going forward, as well as help others who run into the same thing.

Thanks a ton for taking the time to help me crack this, and write it up so clearly - I owe you a beer/coffee/BOYC for sure :slight_smile:

1 Like
#7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.