Wasmtime: Cranelift: rename `PrimaryMap` and `SecondaryMap` to `FixedSizeVec` and `AutoResizeVec`

[julian-seward1]

The names PrimaryMap and SecondaryMap are misleading and un-descriptive. For the benefit of readers and maintainers of Cranelift, and especially newcomers, I propose we give them better names.

• The Map component is misleading. Neither type possesses what I think of as the primary characteristic of a map (in the sense of Rust HashMap, libstdc++ map, etc), which is O(1 + epsilon) access time for sparse keys. The new names shouldn't include the text Map.

• These types are in fact vectors, and you need to know that to use them reasonably (meaning, they only work well for dense zero-based key ranges) but there's nothing in the name to suggest that.

• Primary and Secondary suggest some relationship between individual maps which simply doesn't exist. This confused me for some time when I first came to the code base. I thought: how do I find all the SecondaryMaps associated with a PrimaryMap? Are they connected via some Rust type system magic? Or is it done at run time; if so is there some registry I should consult? This is of course totally irrelevant; there is no such connection.

I suggest to rename PrimaryMap to FixedSizeVec and SecondaryMap to AutoResizeVec:

• it doesn't claim they are maps, which they aren't

• it does claim they are vectors, which they are

• it doesn't claim any relationship between them, which there isn't

• it correctly summarises the essential difference between them: one is fixed size, the other resizes (upwards) on demand.

I believe that accurate naming is important, and this would be a small but important step in making Cranelift easier to understand. If there is general support I will happily prepare a patch.

[julian-seward1]

The change could be done incrementally, so as to avoid massive merge conflicts. First create the new names as (type) aliases of the old ones. Then we can incrementally move smaller sections of the code base to the new names, and remove the old ones when all sections have been changed.

[bjorn3]

it doesn't claim they are maps, which they aren't

It maps from a key (the index) to a value.

Primary and Secondary suggest some relationship between individual maps which simply doesn't exist.

To me a relationship does exists: A PrimaryMap contains entity definitions, while a SecundaryMap contains metadata about (some of) those definitions.

I thought: how do I find all the SecondaryMaps associated with a PrimaryMap?

Look at all SecundaryMaps with the same index type as the PrimaryMap.

[froydnj]

To me a relationship does exists: A PrimaryMap contains entity definitions, while a SecundaryMap contains metadata about (some of) those definitions.

I also found this naming convention confusing when trying to figure out the codebase. Maybe EntityMap and AttributeMap (or something like it) would be more evocative names, then?

[julian-seward1]

I thought: how do I find all the SecondaryMaps associated with a PrimaryMap?
Look at all SecundaryMaps with the same index type as the PrimaryMap.

But that's really something that just happens to mostly be true inside small sections of code, maybe a function or a group of functions, right? There's no particular reason why a PrimaryMap<K, U> should in general be interpreted as having a relationship with some other SecondaryMap<K, V>. It might, but it might not. If there is to be a relationship, that should be shown through the variable names, not the type names.

[sunfishcode]

The way we use PrimaryMap, we give it a distinct key type which identifies a conceptual index space. It isn't an arbitrary type that unrelated code might happen to use; it's a "newtype" created for a particular purpose which ensures that you don't accidentally use an index meant for one index space in another.

For example, anywhere in Cranelift you see a Value, it's related to Function's values PrimaryMap. We don't always make this explicit in variable names, because it's clear from the type. Similarly, anywhere you see a SecondaryMap<Value, Foo>, it's associating a Foo with each value in a function. The auto-resize behavior is almost an implementation detail which we don't currently have a way to fully hide -- we don't want PrimaryMaps to have to maintain lists of associated SecondaryMaps to update when they resize.

EntityMap and AttributeMap would also make sense to me.

[bnjbvr]

I like EntityMap and AttributeMap too. I think the original naming may come from the entity-component-system world, where "secondary" data structures hold external information about entities, as Dan describes.

(And a Vector is effectively one way to implement a Map of integer indexes to something, so the Map component in the name seems to make sense here.)