It is easy to break IR::IndexedVector using its iterators

[vlstill]

So the IR::IndexedVector does not do a good job of keeping its invariants, namely that it is properly indexed. This is (in part) because it exposed modifiable iterators. Therefore, it is possible to modify the objects by iterators (e.g. exchange them), without modifying the map. Example could be using std::remove_if on an indexed vector.

I think the best solution would be to not expose modifiable iterators at all. Of course, that could be a breaking change, but presumably it would only break code which is already buggy. Alternatively, we could offer a "heavyweight" modifiable iterator that actually causes the map to be updated on assignments, but I am not very keen on that.

[ChrisDodd]

. Therefore, it is possible to modify the objects by iterators (e.g. exchange them), without modifying the map. Example could be using std::remove_if on an indexed vector.

Is that actually incorrect, though? If you exchange two objects in the same Vector via iterators, they're both still in the vector (so the internal map does not need to be changed). So remove_if is actually correct since it doesn't actually remove objects (despite its name), it moves them to the end where they can easily be removed by an erase (which does remove them from the map).

The incorrect thing that might be of concern is if iterators are used to move/copy/swap objects between two different vectors.

[vlstill]

. Therefore, it is possible to modify the objects by iterators (e.g. exchange them), without modifying the map. Example could be using std::remove_if on an indexed vector.

Is that actually incorrect, though? If you exchange two objects in the same Vector via iterators, they're both still in the vector (so the internal map does not need to be changed). So remove_if is actually correct since it doesn't actually remove objects (despite its name), it moves them to the end where they can easily be removed by an erase (which does remove them from the map).

The incorrect thing that might be of concern is if iterators are used to move/copy/swap objects between two different vectors.

That would hold if std::remove/remove_if did swap on the elements, however, that is not the case:

Explanation

Removing is done by shifting the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range.

• Shifting is done by copy assignment(until C++11)move assignment(since C++11). [...]

... https://en.cppreference.com/w/cpp/algorithm/remove

So a latter element is moved "over" the "to-be-removed" element, which therefore ceases to exist. But in IndexedVector it is in the map still.

However, this is just an example, the point is that IndexedVector exposes seemingly simple & safe API that can very easily break it.

[fruffy]

Related IR::IndexVector issues: https://github.com/p4lang/p4c/issues/4117 https://github.com/p4lang/p4c/issues/43 One of the oldest issues still open.

[vlstill]

Related IR::IndexVector issues: #4117 #43 One of the oldest issues still open.

Yep, seems like this is a duplicate of #43.