[cfe-dev] Bug in MapVector::erase ?

[Yaron Keren]

Hi Oliver,

There would be no problem if both the Map and the Vector indeed contained
(Key,Value) pairs.

To save space, Map entries do not contain Value but instead an unsigned
index into the Vector:

/// The values are kept in a std::vector and the
/// mapping is done with DenseMap from Keys to indexes in that vector.

After an element is erased from the Vector all indices greater than the
removed index are one too large.

That's probably the reason why Mapvector did not have erase before. See

  http://llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h

...and it doesn't support removing elements.

To correct this erase needs to decrement all vector indices in the Map
which are larger than the removed index.

Note that pop_back() does not have this problem as there are no indices
following the last one.

Yaron



2014-07-15 17:35 GMT+03:00 Oliver Stannard <oliver.stannard at arm.com>:

> Do you have a reproducer for this problem? MapVector::erase removes the
> value from both the Vector and the Map, so it should not suffer from this
> problem.
>
>
>
> Oliver
>
>
>
> *From:* Yaron Keren [mailto:yaron.keren at gmail.com]
> *Sent:* 15 July 2014 15:18
> *To:* cfe-dev at cs.uiuc.edu Developers; llvmdev at cs.uiuc.edu; Oliver Stannard
> *Subject:* Re: Bug in MapVector::erase ?
>
>
>
> +llvmdev +Oliver. MapVector::erase was added in r211273.
>
>
>
> To avoid duplications, MapVector stores Values inside the vector only,
> while the map caches key->indices to the vector.
>
>
> When a value is erased from the MapVector, it is removed from the vector,
> invalidating the cached vector indices stored in the map, so the map points
> to wrong locations and the MapVector is corrupted.
> --
> Yaron
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140715/6984990d/attachment.html>