llvm dev - Jul 2014 - [LLVMdev] [cfe-dev] Bug in MapVector::erase ?

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/llvm-dev/attachments/20140715/6984990d/attachment.html>

Sounds pretty clearly buggy, and against the original design of the
ADT (as pointed out by the documentation quotation). When was erase
functionality added to MapVector? Can/should it be removed (and the
use case changed to use some other container)

Making erase linear time sounds... not ideal, but possibly its
sufficient for some/current use cases. Or we could consider other
solutions to the use cases.

I see this was added in r211273 for the purposes of MCDwarf section
range handling. Perhaps instead of removing empty ranges, they could
just be omitted when emitting ranges. finalizeDwarfRanges could return
the count of non-empty ranges, and use that to decide whether to emit
any ranges, whether to emit it as ranges or just low_pc/high_pc in
MCGenDwarfInfo::Emit, and add a conditional (checking for a non-null
end symbol) in EmitGenDwarfRanges.

Further: I'd really like to see the range building/emission code
refactored into a common utility between MCDwarf and AsmPrinter DWARF
handling (similar to what I've done with the line table
emission/handling). I'm not sure if this would address the problem
too.

On Tue, Jul 15, 2014 at 7:57 AM, Yaron Keren <yaron.keren at gmail.com>
wrote:
> 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
>>
>>
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>

> On 2014-Jul-15, at 08:29, David Blaikie <dblaikie at gmail.com>
wrote:
> 
> Sounds pretty clearly buggy, and against the original design of the
> ADT (as pointed out by the documentation quotation). When was erase
> functionality added to MapVector? Can/should it be removed (and the
> use case changed to use some other container)
> 
> Making erase linear time sounds... not ideal, but possibly its
> sufficient for some/current use cases. Or we could consider other
> solutions to the use cases.
Heh -- it's already linear.  It erases from the middle of a vector.

At the least, if erasing is kept (and fixed), someone needs to update the
docs and add a unit test.

One way of speeding this up would be to erase a set of values in bulk.  I
think we could easily add a `remove_if()` function that deleted a set of
matching items in linear time, using a linear-size auxiliary array of
indices to keep state.

I'd be happy to implement this if there's a need (if you can easily
design
it out, that's better).