Rationale of restrictive rules for extract and re-insert with map

Question

Since C++17, associative containers support the extraction of a node and its re-insertion (possibly into another container of the same type). The object returned by extract(key) is a node_handle, which is move-only and for map containers has member functions

key_type &key() const;
mapped_type &mapped() const;

which allow to alter not only the mapped type, but also the key. This can be used to change the key without re-allocation (example taken from the documentation for map::extract()):

std::map<int, std::string> map{{1,"mango"}, {2,"papaya"}, {3,"guava"}};
auto handle = map.extract(2);
handle.key() = 4;
map.insert(move(handle));

As far as I understand, map is implemented as binary-search tree, while map::extract() un-links a node from the tree and returns a pointer to it via the node-handle, which takes over the ownership. Upon map::insert(), the node is re-linked into the tree and ownership is taken over by the map again.

Thus, the node (and the stored key and mapped_type) are not re-allocated, moved, or copied in the process. The standard says (my high lighting):

The extract members invalidate only iterators to the removed element; pointers and references to the removed element remain valid. However, accessing the element through such pointers and references while the element is owned by a node_­type is undefined behavior. References and pointers to an element obtained while it is owned by a node_­type are invalidated if the element is successfully inserted.

My question: what is the rationale behind (1) making it UB to access an extracted element by its address and (2) invalidating upon insertion the address taken in the extracted state?

IMHO, this extract-and-insert idiom can be implemented in a way that keeps the address of the element valid at all times (until destruction, which may occur before map-destruction if the element is never re-inserted). The following code

#include <map>
#include <string>
#include <iostream>

struct immovable_string : std::string
{
    immovable_string(const char*s) : std::string(s) {}
    immovable_string() = default;
    immovable_string(immovable_string const&) = delete;
    immovable_string(immovable_string &&) = delete;
    immovable_string&operator=(immovable_string const&) = delete;
    immovable_string&operator=(immovable_string &&) = delete;
};

int main()
{
    std::map<int,immovable_string> map;

    map.emplace(1,"mango");
    map.emplace(2,"papaya");
    map.emplace(3,"guava");

    std::cout << "initially:     "
              << " address=" << std::addressof(map[2])
              << " value=" << map[2] <<'\n';

    auto handle = map.extract(2);

    std::cout << "after extract: "
              << " address=" << std::addressof(handle.mapped())
              << " value=" << handle.mapped() <<'\n';

    handle.key() = 4;
    map.insert(move(handle));

    std::cout << "after insert:  "
              << " address=" << std::addressof(map[4])
              << " value=" << map[4] <<'\n';
}

compiles (with gcc 8.2.0 using -std=c++17) and gives output

initially:      address=0x7f9e06c02738 value=papaya
after extract:  address=0x7f9e06c02738 value=papaya
after insert:   address=0x7f9e06c02738 value=papaya

as expected (the same results are obtained for std::string in place of immovable_string and/or unordered_map instead of map).

---

Edit

Note that I'm not asking about issues related to modifying the key (map stores pair<const Key,T>).

My question is solely about restrictions for access to the mapped element via pointers or references. The whole idea of the extract-and-insert idiom makes only sense if the element is not moved/copied, i.e. if its address remains valid at all times (which in fact is specified by the standard). Rendering access to the element whilst in the extracted state UB seems strange and renders the extract-and-insert mechanism less useful: think about multi-threaded code with one thread accessing an element whilst another extracts and re-inserts it. This can be implemented w/o any issue yet may invoke UB -- WHY?

Here is a UB scenario (which IMHO is perfectly fine, no UB required):

void somefunc(object*ptr) { ptr->do_something(); }
void re_key(map<int,object> &M, int oldKey, int newKey)
{
    if(M.find(0)!=M.end() && M.find(newKey)==M.end()) {
        auto handle = M.extract(0);
        handle.key() = newKey;
        M.insert(std::move(handle));
    }
}

map<int,object> M = fillMap();
auto ptr = addressof(M[0]);     // takes initial address
thread t1(somefunc,ptr);        // uses said address to access object
thread t2(re_key,M,7);          // extracts and inserts an object 

Of course, if the insert() fails, the handle is destroyed and the address invalidated. That's obvious, but the user can to something about that.

Answer 1

I'm just following up on Kerrek SB's answer in the hope to explain the issue in more detail (and hence a bit more convincingly). The adopted revision 3 of the paper in question (P0083R3) mentions the std::pair<const Key, Mapped> vs std::pair<Key, Mapped> conundrum, and that "The conversion between these can be effected safely using a technique similar to that used by std::launder on extraction and reinsertion."

IOW, extraction and reinsertion are safe from optimizations related to type punning by invoking "implementation 'magic'" (this is the explicit wording in the paper) to resolve any possible aliasing problems within the container code itself, and insofar as user code abides by the restrictions you mentioned.

This raises the question of why this "magic" cannot be extended to cover also cases where user code accesses the Mapped element of a dissociated node through a pointer that was obtained while the node still belonged to a container. The reason for this is that the scope of implementing such "magic" is considerably greater than the scope of implementing the limited magic that applies only to node extraction and insertion.

Consider e.g., trivially, this function:

int f(std::pair<const int, int> &a, const std::pair<int, int> &b)
{
    a.second = 5;
    return b.second;
}

As per the restrictions on type aliasing, the implementation is allowed to assume that a and b cannot reside at the same memory location. Therefore, the implementation is also allowed to assume that a.second and b.second do not reside at the same memory location, even though they have the same type. Therefore, an implementation is entitled to some very basic code generation freedoms such as performing the load of b.second before the store to a.second, without needing to actually compare the addresses of a and b first.

Now assume that the restrictions on map splicing were not as you have mentioned. Then, it would be possible to do the following:

int g()
{
    std::map<int, int> m{{1, 1}};
    auto &r = m[1];
    auto node = m.extract(1);
    return f(r, node.value());
}

Because of the type punning restrictions, clearly this is UB. Now, hold on, I know you want to protest because:

1. The node_type for a std::map does not have a value() method.
2. Even if it did, the node_type is supposed to std::launder (or something roughly equivalent) the value.

However, these points do not provide an actual remedy. As far as the first point is concerned, consider this minor variation:

int f(std::pair<const int, int> &a, const int &b)
{
    a.second = 5;
    return b;
}

int g()
{
    std::map<int, int> m{{1, 1}};
    auto &r = m[1];
    auto node = m.extract(1);
    return f(r, node.mapped());
}

Now, peephole optimization into f does not give the compiler sufficient information to rule out aliasing. However, let's assume that the compiler is able to inline both node.mapped() (and therefore, the compiler can establish that it returns a reference to the second of a std::pair<int, int>), and f. Suddenly, the compiler may once more feel entitled to a dangerous optimization.

But what about the laundering? First of all, this does not apply here, because the information regarding extract and the laundering done within it may be in a different translation unit altogether than node_type::mapped(). This needs emphasizing: With the tight restrictions that were standardized, the laundering can be done during extraction, it does not have to be done on every call to value(), which is also clearly the intent expressed in the quote I provided at the beginning. The main issue, however, is that laundering cannot prevent UB here, even if it were done inside node_type::mapped(). In fact, the following code has undefined behavior (example assumes that sizeof(int) <= sizeof(float)):

float g()
{
    float value = 0.0f; // deliberate separate initialization, see below
    value = 3.14f;
    int *intp = std::launder(reinterpret_cast<int *>(&value));
    *intp = 1;
    return value + *intp;
}

This is because using std::launder does not give the user permission to type punning at all. Instead, std::launder only allows reusing the memory of value by establishing a lifetime dependency between the float that lives at &value initially and the int that lives there after the std::launder. In fact, as far as the standard is concerned, value and *intp cannot possibly be alive at the same time precisely because they have pointer-incompatible types and the same memory location.

(What std::launder does achieve, here, is e.g. to prevent reordering of value = 3.14f; to after *intp = 1. Simply put, the compiler is not allowed to reorder writes to after the std::launder, nor reads from a laundered pointer to before the std::launder, unless it can prove that the memory locations do not in fact overlap, and this is true even if pointer-incompatible types are involved. I used a separate assignment so that I could make this point more clearly.)

What this finally boils down to, is that, to safely support the usage you envision, implementations would have to add additional magic on top of that mentioned in the paper (and the latter is largely implemented already because it is at least very similar to the effects of std::launder). Not only would this have caused additional effort, but it could also have had the side effect of preventing certain optimizations in cases where the user voluntarily abides by the restrictions as standardized. Judgment calls like this are made all the time in standardizing C++, or pretty much anything, where the experts try to weigh the projected costs against certain or at least probable benefits. If you still need to know more, you'd likely have to approach some of the CWG members directly, because this is where the request to apply these restrictions was made, and as mentioned in the paper linked above.

Hope this helps to clear things up a bit, even if you still disagree with the resolution taken.

As a final note, I highly recommend you to watch some of the great talks on C++ UB if you haven't already, for instance Undefined Behavior is Awesome by Piotr Padlewski, or Garbage In, Garbage Out… by Chandler Carruth.

Answer 2

I think the predominant subtlety in the "extraction" system is that the value_type of a map<K, T> is pair<const K, T> — note the const!

Modifying a const object causes undefined behaviour, so you need to be very careful not to modify something that's known to be const. While the node is part of any map, the key is const. The "magic" of the extraction machinery (and the reason it took so long to specify) is that while the node is extracted, the key is not const.

This basically requires you to look at the problem really hard and convince yourself that a pair<const K, T> can sometimes be interpreted as a pair<K, T> (and bear in mind that pair is a template that users are permitted to specialize!). So to avoid any potential for const objects being modified, there must be a clear sequencing of inserted and extracted states for any node.

There is standard wording to help with the specialization issue in [container.node.overview]p4:

If a user-defined specialization of pair exists for pair<const Key, T> or pair<Key, T>, where Key is the container’s key_type and T is the container’s mapped_type, the behavior of operations involving node handles is undefined.