Tracking issue for shared type library

[nikomatsakis]

This is a tracking issue for the goal of creating a shared library that represents Rust types. This library should be used by rustc, chalk, and rust-analyzer, and would permit us to pass data and goals between rustc and chalk without any "bridging" cost. It will also permit one to write type-based analyses (like chalk itself!) that do not depend on rustc internals.

What follows is a list of steps to be taken. Those steps with open issues are actionable and ready to go. Those without open issues may be uncertain or maybe we just didn't write up any notes yet -- feel free to ping on Zulip to inquire after the status.

General work items

• Initial design meeting proposal
• Propose renaming "type fold" to "type map" (in both rustc/chalk)
• Propose renaming "type visitor" to "type folder" (in both rustc/chalk, although we don't have a trait like this in chalk yet)
• Complete comparison spreadsheet that describes names for things in rustc, chalk and what should go into shared library

Rust work items

• Refactor code in rustc using ty.kind to use a method ty.kind(tcx) (but see bikeshed point above)
• Extend rustc's Binder type to contain a list of "kinds" for the bound items (discussion)
• return TyKind by value (maybe) as proposed in Make TyKind Copy and change ty.kind() to return TyKind instead of &TyKind compiler-team#363
• Extend rustc's late-bound types to contain an index
• Start to move types into library to figure out what is missing
• Introduce custom derive for Fold trait
• Extend Rustc's folder trait to have a Result associated type
• Extend Rustc's visit trait to not hard-code a boolean result?
• Extend Rustc's TyKind variant to collapse the various scalars into one

Chalk work items

• Rename TyData to TyKind in Chalk
• Count binders, not variables
• Extend TypeName with variants representing scalar types (e.g., bool, u32, i32) and other rust "application types" extend chalk TypeName with builtin types chalk#368
• Introduce Interner associated type for all vectors that appear in chalk_ir types (e.g., Vec<QuantifiedWhereClause>, Vec<ParameterKind>, etc) as well as Arc or Box move remaining vectors, boxes in chalk-ir into associated types on Interner chalk#369
• Convert parameters field of Fn type to use Substitution instead of a Vec
• Introduce a Visit trait in chalk introduce a Visit trait to go with Fold chalk#333
• Refactor Binders API to have private values field -- refactor Binders API to have a private value field chalk#375
• Add "flags" to the Ty type and friends and integrate some of those flags into folders add flags to InternedTy and InternedRegion types chalk#627
  • Add
  • Integrate -- not really a blocker
• Optimize folding over slices to avoid "reinterning" them when not needed
• Experiment with removing Apply and TypeName and inlining those as distinct variants in chalk's type

Things to explore

• Align on a single model of canonicalization -- what gets canonicalized? What about universe canonicalization?

XXX hackmd where sketched a plan, need to incorporate above

[jackh726]

Michael has made many PRs towards this effort!:
rust-lang/rust#116828
rust-lang/rust#116912
rust-lang/rust#116946
rust-lang/rust#116951
rust-lang/rust#116993
rust-lang/rust#117008
rust-lang/rust#117578
rust-lang/rust#117580
rust-lang/rust#117582
rust-lang/rust#117851