swap breaks unordered containers' stateSection: 23.2.8.2 [unord.req.except] Status: Open Submitter: Alisdair Meredith Opened: 2012-09-23 Last modified: 2019-07-22
Priority: 3
View all issues with Open status.
Discussion:
The hash functor and key-comparison functor of unordered containers are allowed to throw on swap.
23.2.8.2 [unord.req.except]p3 "For unordered associative containers, no swap function throws
an exception unless that exception is thrown by the swap of the container's Hash or Pred object (if any)."
In such a case we must offer the basic exception safety guarantee, where both objects are left in valid
but unspecified states, and no resources are leaked. This yields a corrupt, un-usable container if the
first swap succeeds, but the second fails by throwing, as the functors form a matched pair.
So our basic scenario is first, swap the allocators if the allocators propagate on swap, according to
allocator_traits. Next we swap the pointers to our internal hash table data structures, so that
they match the allocators that allocated them. (Typically, this operation cannot throw). Now our containers
are back in a safely destructible state if an exception follows.
Next, let's say we swap the hash functor, and that throws. We have a corrupt data structure, in that the buckets are not correctly indexed by the correct functors, lookups will give unpredicatable results etc. We can safely restore a usable state by forcibly clearing each container - which does not leak resources and leaves us with two (empty but) usable containers.
Now let us assume that the hasher swap succeeds. Next we swap the equality comparator functor, and this too could throw. The important point to bear in mind is that these two functors form an important pairing - two objects that compare equal by the equality functor must also hash to the same value. If we swap one without the other, we most likely leave the container in an unusable state, even if we clear out all elements.
1. A colleague pointed out that the solution for this is to dynamically allocate the two functors, and then
we need only swap pointers, which is not a throwing operation. And if we don't want to allocate on default
construction (a common QoI request), we might consider moving to a dynamically allocated functors whenever
swap is called, or on first insertion. Of course, allocating memory in swap is a whole
new can of worms, but this does not really sound like the design we had intended.
2. The simplest option is to say that we do not support hasher or equality functors that throw on ADL
swap. Note that the requirement is simply to not throw, rather than to be explicitly
marked as noexcept. Throwing functors are allowed, so long as we never use values that
would actually manifest a throw when used in an unordered container.
Pablo went on to give me several more options, to be sure we have a full set to consider:
3. Disallow one or the other functor from throwing. In that case, the possibly-throwing functor must be swapped first, then the other functor, the allocator, and the data pointer(s) afterwards (in any order -- there was a TC that allocator assignment and swap may not throw if the corresponding propagation trait is true.). Of course, the question becomes: which functor is allowed to throw and which one is not?
4. Require that any successful functor swap be reliably reversible.
This is very inventive. I know of no other place in the standard where
such a requirement is stated, though I have occasionally wanted such a
guarantee.
5. Allow a failed swap to leave the containers in a state where future insertions may fail for reasons other than is currently allowed. Specifically, if the hash and equality functors are out of sync, all insertions will fail. Presumably some "incompletely swapped" exception would be thrown. This is "slightly" inventive, although people have been discussing "radioactive" states for a while.
[2013-03-15 Issues Teleconference]
Moved to Open.
[2019 Cologne Wednesday night]
Billy to write resolution for option #2. This may require a paper.
Proposed resolution: