🛠 use interned refs to goals/clauses instead of boxes

[nikomatsakis]

In #48985, @scalexm added types for goals/clauses to use in the experimental lowering. That code used a Box to enable recursion. The typical thing for us to do is to use interning, as described briefly in this comment. There are FIXMEs in the code.

[nikomatsakis]

Some notes:

The interners are defined in two places. First off, there is the GlobalArenas data structure:

rust/src/librustc/ty/context.rs

Lines 96 to 110 in 4bf76d6

	/// Internal storage
	pub struct GlobalArenas<'tcx> {
	// internings
	layout: TypedArena<LayoutDetails>,
	// references
	generics: TypedArena<ty::Generics>,
	trait_def: TypedArena<ty::TraitDef>,
	adt_def: TypedArena<ty::AdtDef>,
	steal_mir: TypedArena<Steal<Mir<'tcx>>>,
	mir: TypedArena<Mir<'tcx>>,
	tables: TypedArena<ty::TypeckTables<'tcx>>,
	/// miri allocations
	const_allocs: TypedArena<interpret::Allocation>,
	}

This contexts global data -- notably, these use TypedArena, which permits them to contain types with destructors (e.g., Vec or Box). Then, for each inference context (and, I think, for the global context), there are CtxtInterners:

rust/src/librustc/ty/context.rs

Lines 127 to 141 in 4bf76d6

	pub struct CtxtInterners<'tcx> {
	/// The arena that types, regions, etc are allocated from
	arena: &'tcx DroplessArena,
	/// Specifically use a speedy hash algorithm for these hash sets,
	/// they're accessed quite often.
	type_: RefCell<FxHashSet<Interned<'tcx, TyS<'tcx>>>>,
	type_list: RefCell<FxHashSet<Interned<'tcx, Slice<Ty<'tcx>>>>>,
	substs: RefCell<FxHashSet<Interned<'tcx, Substs<'tcx>>>>,
	canonical_var_infos: RefCell<FxHashSet<Interned<'tcx, Slice<CanonicalVarInfo>>>>,
	region: RefCell<FxHashSet<Interned<'tcx, RegionKind>>>,
	existential_predicates: RefCell<FxHashSet<Interned<'tcx, Slice<ExistentialPredicate<'tcx>>>>>,
	predicates: RefCell<FxHashSet<Interned<'tcx, Slice<Predicate<'tcx>>>>>,
	const_: RefCell<FxHashSet<Interned<'tcx, Const<'tcx>>>>,
	}

For these, all memory is stored in one DroplessArena. The hashsets are used to do interning (i.e., find duplicates).

The actual allocation is done in functions on the tcx. One example is intern_ty, but it's among the most complex. Still, you can see the basic structure:

• it checks whether this type belongs in the global arena
• allocates memory in the arena itself
• and then inserts into the hashset

The Interned type that is added to the interners is a kind of shim:

rust/src/librustc/ty/context.rs

Lines 1841 to 1842 in 4bf76d6

	/// An entry in an interner.
	struct Interned<'tcx, T: 'tcx+?Sized>(&'tcx T);

It compares and hashes its contents deeply, and it implements Borrow so that we can do a "lookup" in the set from a non-interned thing:

rust/src/librustc/ty/context.rs

Line 1859 in 4bf76d6

impl<'tcx: 'lcx, 'lcx> Borrow<TypeVariants<'lcx>> for Interned<'tcx, TyS<'tcx>> {

I think a good example case to use for Goal would probably be to look at how Region works. We would first rename the existing Goal enum to GoalKind. Then define a type alias Goal<'tcx>, rather like Region:

rust/src/librustc/ty/sty.rs

Line 943 in 4bf76d6

pub type Region<'tcx> = &'tcx RegionKind;

Then add a map to CtxtInterners like so:

rust/src/librustc/ty/context.rs

Line 137 in 4bf76d6

region: RefCell<FxHashSet<Interned<'tcx, RegionKind>>>,

Implement Borrow for the Interned type:

rust/src/librustc/ty/context.rs

Lines 1898 to 1902 in 4bf76d6

	impl<'tcx> Borrow<RegionKind> for Interned<'tcx, RegionKind> {
	fn borrow<'a>(&'a self) -> &'a RegionKind {
	&self.0
	}
	}

and add an entry to this direct_interners! macro:

rust/src/librustc/ty/context.rs

Lines 1998 to 2006 in 4bf76d6

	direct_interners!('tcx,
	region: mk_region(|r| {
	match r {
	&ty::ReVar(_) | &ty::ReSkolemized(..) => true,
	_ => false
	}
	}) -> RegionKind,
	const_: mk_const(|c: &Const| keep_local(&c.ty) || keep_local(&c.val)) -> Const<'tcx>
	);

That macro is a bit weird but it implements the "intern-in-global-tcx-else-local-tcx" pattern described above. You would probably want something like:

goal: mk_goal(|goal: &GoalKind| keep_local(goal)) -> Goal<'tcx>)

keep_local is a function defined here that checks for the KEEP_IN_LOCAL_TCX flag:

rust/src/librustc/ty/context.rs

Lines 1994 to 1996 in 4bf76d6

	pub fn keep_local<'tcx, T: ty::TypeFoldable<'tcx>>(x: &T) -> bool {
	x.has_type_flags(ty::TypeFlags::KEEP_IN_LOCAL_TCX)
	}

One complication is that Goal contains a Vec:

rust/src/librustc/traits/mod.rs

Line 284 in 4bf76d6

Implies(Vec<Clause<'tcx>>, Box<Goal<'tcx>>),

That has a dtor, so we would want to translate it to use a "slice interner", which will intern a slice of items like [Goal<'tcx>] leaving &'tcx [Goal<'tcx>] as the type to use instead of Vec. You can model this on how predicates are handled:

rust/src/librustc/ty/context.rs

Lines 2017 to 2022 in 4bf76d6

	slice_interners!(
	existential_predicates: _intern_existential_predicates(ExistentialPredicate),
	predicates: _intern_predicates(Predicate),
	type_list: _intern_type_list(Ty),
	substs: _intern_substs(Kind)
	);

[ishitatsuyuki]

Two questions:

• Should Vec<Clause<'tcx>> be interned?
• Should I intern Goal and Vec<Goal> separately or instead intern every time as slice and use length of 1 when there's single item?