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 >
Duncan P. N. Exon Smith
2014-Jul-15 16:31 UTC
[LLVMdev] [cfe-dev] Bug in MapVector::erase ?
> 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).