A madman's guide to variadic generics

language design
21

Fundamentally you've got the wrong model. You are trying to fit this into a single conceptual phase where in fact we ought to have multiple stages.

The Java model for example is multi-stage: The compiler reads the source code of program P1 (which is conceptually immutable!) and by running the annotation processing it produces program P2 which in turn could produce P3 and so forth.

I do not think that trying to find convergence or whatever is wise. Instead, we need to run additional trait solving phases as part of this compile time vs runtime divide.

22

In Java this works well because the new programs P2, P3, etc etc can't influence the compilation of the previous programs like P1. But in Rust adding a trait implementation can influence the previous compilation, in part because the previous metaprogramming steps may rely on a trait not being implemented, in part because type inference also relies on that as well. Consider for example Rust Playground

You're just describing a naive way to look for convergence though.

23

Philosophically this is not so different from cases where trait solving can already overflow, like:

trait Foo {}
impl<T> Foo for T where (T,): Foo {}

error[E0275]: overflow evaluating the requirement `(((((((...,),),),),),),): Sized`
 --> src/lib.rs:2:31
  |
2 | impl<T> Foo for T where (T,): Foo {}
  |                               ^^^
  |
  = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `(((((((((((((((((((((((((((((((((((...,),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),)` to implement `Foo`

…It's just that with reflection, the infinite cascade of "is this trait implemented?" queries would happen in user code rather than inside the compiler.

1 Like
24

Perhaps we could restrict using reflection for type construction in associated types since projections and queries waiting for resolution of them are something the trait solver already understands. This is closer to soqb's proposal, but replacing the ad-hoc syntax for type transformations with imperative code that is extensible.

E.g. to boxify a tuple it could be

trait Boxable {
   type Boxed
}

impl Boxable for (..T) {
   type Boxed = const { 
      let ty_in = Self.r#type;
      let mut ty_out = ().r#type;
      for f in ty_in.fields {
           let ty_field = field.r#type;
           ty_out = (Box<ty>, ..ty_out);
      }
      ty_out
   };
}

This allows more flexibility and can also be extended to work with other features that could be queried at construction time such as const generics, needs_drop, size_of, specialization, effects (e.g. an is_pure), etc. And since the constructions produce associated types those results in turn can be used in where clauses.

This could still result in cyclical dependencies (which we can already happen today as comex points out) but results should be idempotent and won't require the rerun-to-fixpoint dance. At least as long as there are no reflection queries in the form of "enumerate all types that fullfill condition X".

2 Likes
25

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.