[cfe-dev] [libc++] Implementation of std::map::erase() in libc++ doesn't match that in libstdc++

[Marshall Clow]

On Apr 11, 2014, at 9:35 AM, Nico Weber <thakis at chromium.org> wrote:

> On Fri, Apr 11, 2014 at 1:29 AM, Marshall Clow <mclow.lists at gmail.com> wrote:
> On Apr 8, 2014, at 1:47 PM, Alexander Potapenko <glider at google.com> wrote:
> 
> > Hi all,
> >
> > We've encountered an incompatibility between libc++ and libstdc++: for
> > std::map::erase(pos) libstdc++ (and MSVS as well) first removes the
> > item from a map (a) and then calls its destructor (b), while libc++
> > calls the destructor before changing the map structure.
> >
> > This results in a crash described at
> > https://code.google.com/p/chromium/issues/detail?id=358707: the item
> > that's being erased from the map queries that map in the destructor
> > calls some methods for the elements it finds. With libc++ that item
> > manages to find itself (in an inconsistent state, since it's in the
> > destructor already) and crashes.
> >
> > Does the standard specify the order of (a) and (b), or it's incorrect
> > to rely on the order provided by some of the libraries?
> 
> My belief is that the correct answer is (b).
> 
> As far as I can tell, the standard makes no mention of this.
> [ map::erase has no special requirements, and the general container requirements don’t say anything. ]
> 
> However, libc++’s behavior seems a bit odd to me, too.
> I committed revision 206024 to change this.
> 
> Speaking of spec-compliant-but-odd things: libc++'s std::random_shuffle walks the array backwards, while libstdc++ and msvs's implementation walk forward. We used to have code that called random_shuffle with a fixed generator and relied on that producing always the same shuffle, but libc++'s shuffle was different than the one produced by other standard libraries. Maybe you want to change this too.

That seems … wrong to me.

The only guarantee you get from random_shuffle is that any output is as likely to occur as any other output.
I suspect (but the standard doesn’t require, as far as I can tell), if you give it the same inputs, and a RNG that spits out the same random sequence, you should get the same output each time, but there’s nothing about a “correct” result.

> 
> (Not required for spec compliance, but it'd make libc++ less surprising. In Chromium, we've stopped using random_shuffle in this case since if we need this property and the spec doesn't guarantee it, relying on it seems like a pretty bad idea!

Exactly correct.

> But it might be nice for other projects.)

I’m less inclined to change this, since:
	1) There’s nothing in the standard that says anything about order of operations.
	2) random_shuffle is deprecated in C++14.

— Marshall

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20140415/1fd8ca85/attachment.html>