carbon-lang

carbon-lang copied to clipboard

This avoids reallocating the backing buffer in ValueStore so that references into the ValueStore are never invalidated when adding new values. This works especially well since we never delete values from a ValueStore.

The strategy used is to allocate chunks of a fixed size, and inserting into each chunk until it is full before allocating the next. The ValueStore starts with an initial allocated chunk in all cases, so that there is only a single indirection for adding and accessing values from this chunk. After it's full, additional chunks are allocated in a vector, so two indirections are required to add or access values in these chunks.

This obviates the need for https://github.com/carbon-language/carbon-lang/pull/5529 as we no longer need to worry about holding pointers into a ValueStore.

We introduce a Flatten operation for ranges. It flattens a "range over ranges over Ts" down to a "range over Ts". This allows us to make an range over the values in the ValueStore from a range over the chunks in the ValueStore. See https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#method.flatten for inspiration for this name choice. Flatten is used in one other case where we were writing two levels of for loops to do the same thing.

The array_ref() accessor is changed to values() and its now a range (typed as a ValueStoreRange) over all values as references (like ArrayRef was, but without random access).

As pointers to a ValueStore can no longer be invalidated, we remove the ASAN poisoning feature and support from ValueStore.