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

[David Blaikie]

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
>