Trait system rewrite

[aturon]

Point of contact

@nikomatsakis @aturon

Overview

The current trait system implementation is written in a "direct" style, where we perform search directly on impls and so on. While we've taken pains to keep this implementation clean, it's still quite complicated and ad hoc, and has a number of pitfalls:

• Performance is limited by the amount of caching we can perform. Caching currently takes into account irrelevant information, meaning that cache misses are more common than they should be. Changing this in the current setup is not easy.

• There are a lot of limitations around associated types and higher-ranked trait bounds, which again are hard to lift within the current setup.

• There are a number of extensions we'd like to make to the trait system, but doing so would require substantial refactorings.

We're now exploring a re-write based on logic programming, where we understand traits and impls as a logic program against which we can make queries. This should allow for a much more principled implementation, better caching, and easier extension to new features (like associated type constructors).

Status

The Chalk project is a standalone trait system/prolog engine, which serves as a prototype and specification for what we want in rustc itself. It's quite far along at this point, but is still missing a few crucial pieces (like specialization).

We're also doing some refactoring in rustc, ahead of the work to port Chalk's ideas into rustc proper.

In the long run, we'd like to have the ability to run Chalk side-by-side with rustc, as an addon to the compiler's test suite.

Blog posts:

• Lowering Rust traits to logic
• Unification in Chalk, part 1
• Unification in Chalk, part 2
• Negative reasoning in Chalk

[mrkgnao]

Something I noticed: @nikomatsakis' proposed "stages of typing" reminds me of how Haskell is compiled, especially in how they propose RFCs should be evaluated. The GHC section of The Architecture of Open Source Applications mentions something similar with respect to the GHC Core intermediate language that might be interesting to look at.

[aturon]

Note that ongoing work is happening in the Chalk repository. This is a standalone trait system/prolog engine, which we hope will double as an executable specification/test system for rustc. There are a few more major pieces to land here (e.g., specialization), and then we'll focus on porting the ideas to rustc proper.

[aturon]

Added links to blog posts.

[JoeyAcc]

Just out of curiosity:
Roughly how does Chalk perform, compared to the current Trait implementation?
I suppose what I'm really asking is: Can we, the rust community, expect any kind of significant performance delta in either direction once the switch is made to Chalk?

[steveklabnik]

My understanding is that Chalk is mostly about correctness and ease of adding things in the future, but also is supposed to perform better.

However, you gotta think about this in an Amdahls' law sense: figuring out what traits apply is rarely a significant part of compilation time, so even speeding it up a lot probably won't speed up compile times overall a ton.

I'm not on the compiler team though so I may be wrong about any part of this.

[jonathandturner]

@steveklabnik - iirc, @nikomatsakis mentioned at one point that the trait stuff is threaded through the typechecking so improvements in it may have some wall-clock improvement in compile time, though not sure what percent improvement it could reasonably give. Maybe he could speak to it?

[aturon]

figuring out what traits apply is rarely a significant part of compilation time

That's incorrect; it can be substantial. Chalk should help in part by providing a much better caching strategy.

[Kixunil]

Is this the correct issue to track if I'm interested in status of wiring Chalk into the compiler or is there something better?