Remove the global hashtable for tracked fns with >1 argument

[nikomatsakis]

As described in this hackmd, we currently create an interned ingredient for every tracked function unless it has exactly 1 argument. This is wasteful. The reason we do this is because the memos for tracked functions are stored on salsa structs¹ and so we need to have a 1:1 relationship between a (salsa struct, tracked fn) pair and a memo.

We should refactor things so that:

• Every tracked function has as its first argument a salsa struct. If there are no arguments, we can add some kind of dummy interned struct in salsa like #[salsa::intern] struct Placeholder<'db>{ data: () } and redefine the argument as being called on a Placeholder<'db>, which we can trivially create (it'd also be nice to have a more optimized "global struct", maybe that's worth thinking about; even interning unit is more work than it really ought to be for this case).
• For tracked functions with >1 argument, when you index into the memo-table for a tracked struct, you would get back a DashMap instead of a single memo; the map would be keyed by the additional arguments.

Footnotes

1. (Salsa struct = input | tracked | interned) ↩

[nikomatsakis]

Mentoring instructions

To start, #600 might be a good first step.

Beyond that, but I can get you started with some pointers. Memos are stored in aMemoTable, defined here:

salsa/src/table/memo.rs

Lines 16 to 18 in 710691d

	pub(crate) struct MemoTable {
	memos: RwLock<Vec<MemoEntry>>,
	}

Right now, each tracked function gets a MemoEntry:

salsa/src/table/memo.rs

Line 30 in 710691d

data: Option<MemoEntryData>,

...which has an option, and thus can store 0 or 1 memos. The actual data is a MemoEntryData which uses some type-id tricks. The idea would be to change this option to something like a map.

The tricky part is that the keys of the map are the additional arguments and the type of memos is independent of those details. So you could package them up as an Arc<dyn Hash+Eq> or something like that (you'd have to define a trait like dyn MemoKey: Hash + Eq). The other part is that many tracked fns don't really want a map, because they only have exactly 1 argument.

I'm not sure the best shape for the result. One idea I am toying with is that instead of having MemoEntry store an Option<MemoEntryData> where the MemoEntryData can be downcast to the actual memotype via type-id, we have MemoEntry store a MemoryEntryMap which carries a type-id. Then the tracked function adding a memo "downcasts" it to the correct kind of map, which might be an Option (if there are no extra arguments) or a Map<K, V> where the K can actually be the right type now.