Chalk and Specialization


  • Overall plan around specialization:
  • Given that one impl A specializes another impl B
  • adjust the rules around projection so that “B wins”
  • adjust the rules for impl A — any default type

impl Iterator for Foo<T> { // impl A
  default type Item = u32; // associated-type-value with id V0
impl Iterator for Foo<String> { // impl B
  type Item = char; // associated-type-value with id V1
For impl A:
forall<T> {
  Normalize(<Foo<T> as Iterator>::Item -> u32) :-
    not { Overrides[V0](Foo<T>: Iterator) }
For impl B:
Overrides[V0](Foo<String>: Iterator).

Normalize(<Foo<String> as Iterator>::Item -> u32).

  • Overrides[ID](Foo<T>: Iterator) — when do these get generated?
  • when impl B specializes impl A:
  • let TraitRefB be the trait ref from impl B
  • for each type in impl B:
  • let ID_A be the id of the associated type in impl A
  • Overrides[ID_A](TraitRefB) :- WhereClausesB
  • in the case of the example above:
  • Overrides[V0](Foo<String>: Iterator)

  • program_clauses_for_goal
  • when the goal is Overrides[V] for some V:
  • needs to walk all impls that potentially override the impl containing V
  • and for each of their associated types, generate clauses
  • “children in the specialization tree”
  • So this function needs access to the specialization tree
  • CoherenceSolver has the specialization forest buildeer
  • want some way for the program clauses code to invoke the specialization clauses code
  • not directly, but through a trait
  • option A:
  • we probably want to extend RustIrDatabase trait
  • add a specialization_tree(&self, trait_id: TraitId) -> SpecializationPriorities method
  • in the chalk-integration crate, this will be mapped to a salsa query that invokes the code from chalk_solve::coherence module
  • chalk_solve::clauses invokes 
  • specialization_tree trait method