Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use DeBruijn indices for all type-level variables #361

Closed
Nadrieril opened this issue Sep 16, 2024 · 2 comments
Closed

Use DeBruijn indices for all type-level variables #361

Nadrieril opened this issue Sep 16, 2024 · 2 comments
Assignees

Comments

@Nadrieril
Copy link
Member

A few features involve nested binders:

  • for<'a> clauses and function pointer types;
  • GATs;
  • dyn Trait, which I would like to encode as exists<T> T: Trait<Vars..>;
  • closures, where I'd like to have one binder level per parent (to handle nested closures gracefully);
  • trait methods, where I would like to explicitly separate the parameters from the parents from those of the method; this is ilkely necessary for provided methods.

Today we use binder groups + DeBruijn indices (just like rustc) for lifetime parameters. To support all these features cleanly I would like to do the same for type, const and trait clause parameters.

@Nadrieril
Copy link
Member Author

Nadrieril commented Nov 25, 2024

Here's the current plan, from discussions with @sonmarcho:

  • All type-level variables (types, regions, const generics, trait clauses) get a De Bruijn index;
  • They share the binding depth: any binder level binds for all of them;
  • Just like for regions, a binder level can contain several variables. In fact the data of a binder is exactly a GenericParams;
  • Every one of our items carries a single top-level binder that contains all the variables bound in the signature (including trait/impl generics in the case of methods);

To link between methods and their trait/impl container, we do the following:

trait Trait<T> {
    fn method<U>();
}
impl<T> Trait<Foo<T>> for Bar<T> {
    fn method<U>() {}
}
// represented as:
fn impl#0::method<T, U>() {}
impl<T> Trait<Foo<T>> for Bar<T> {
    fn method = for<U> impl#0::method<T, U>
}

In other words, the method is translated to an ordinary freestanding function. The only way it knows it's a method is via FunDecl.kind, which contains information about the trait/impl it comes from, with appropriate generic arguments valid in its binding context (#468). The impl itself has a top-level binder as normal, and an inner binder for each funciton, that binds the variables that are local to the method. It then constructs the appropriate list of arguments to pass to the top-level function, thus collapsing two levels of binders into one.

This makes it possible to alter the generics of items locally without needing to split and merge lists of generics in error-prone ways. This is particularly important for #127. This does mean that to go from an impl to one of its methods, we need to do a bit of substitution.

The other places where we introduce new binder levels are GATs and dyn Trait, which we translate to something like exists<T: Trait> (). I don't know what to do about closures yet, this will depend on what usage we need; see #194.

@Nadrieril
Copy link
Member Author

Done in #491 and #492.

This was referenced Dec 11, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant