A C++ Trick Question - Blog Post

[u/MegaGreenLightning]

https://greenlightning.eu/programming/cpp-trick-question/

[u/tuxwonder]

I understand why this happens, but it just feels like a very silly problem that should be solveable

[u/FickleQuail8944 → u/tuxwonder]

I wonder whether it could do tail call optimization, if it is the last member. But then the destructor cannot do anything.

You would have to find a way to destruct a graph by first moving out all shared_ptr members, destroying the object, and repeating.

``` shared_ptr<Node> root = ...; // maybe in the destructor based on type traits root.recursive_destruct();

void shared_ptr::recursive_destruct() { vector<shared_ptr<T>> refs; get()->move_refs(refs); destroy();

while (!refs.empty()) { shared_ptr<T> ref = std::move(refs.back()); refs.pop_back(); if (ref.ref_count() == 1) { ref->move_refs(refs); ref.destroy(); } } } ``` It is kind of ugly and not thread-safe. Maybe one could avoid the vector with shared pointer internals and also erase the type for collection.

[u/tuxwonder → u/FickleQuail8944]

• Tail-call recursion doesn't work because it's built on the premise that the recursive step is the very last thing that happens in your stack frame, but in destructors that's never true. The recursive auto-steps into member destructors is second-to-last, but the very last thing is the deallocation of "this"
• In your code example, you're allocating new heap memory to create the stack of objects to deallocate, but doing so will hurt perf unless you only do it for very deep destructor chains. However, this is probably the best viable option to fix this

[u/cdb_11 → u/tuxwonder]

It is. Replace recursion with iteration.

struct Node {
    std::shared_ptr<Node> next;

    ~Node() {
        auto node = std::move(next);
        while (node.use_count() == 1)
            node = std::move(node->next);
    }
};

[u/rbobby]

C++ is just a trick C question taken too far.

[u/AntimatterTNT]

absolutely not tricky. there's a reason you dont do shit like this

[u/FickleQuail8944 → u/AntimatterTNT]

Create reference chains with shared_ptr? It's normal to have recursive data structures.

[u/munchbunny → u/FickleQuail8944]

It is, but the "best practice" caveat is that you don't do recursion in general without first thinking through recursion limits or the maximum recursive depth your algorithm expects to see in the wild, precisely because recursion is probably the most common way to accidentally overflow your stack.

IMO this example is genuinely tricky (disagreeing with the grandparent post) because of the hidden recursion inside the destructor. Otherwise there really isn't a problem with a very long linked list. I'm quite rusty at C++, so maybe it's because I just haven't had to think about destructors for a long time (5 years, to be precise), but my mind didn't go anywhere near the issue of destructor recursion. I was in the right neighborhood regarding stack space, but I was trying to recall whether the code would result in stack allocations, which isn't the issue here.

[u/Plazmatic → u/AntimatterTNT]

This is a pretty common pattern that shows up in recursive descent parsers (or any kind of recursive parsers) in c++, you have expressions that themselves can be made up of themselves, usually indirectly.  The programmer represents terminals and expressions as a variant of pointers to expressions and value type terminals.  The pointer stops the variant/struct size from being incomputable, or resulting in stack overflows, but the destructor has the exact same issue as it does here.

[u/AntimatterTNT → u/Plazmatic]

sure you can write anything if you don't know what you're doing

[u/initcommit]

Oooo, technically interesting!

[u/obetu5432]

every c++ question is a trick question

[u/shunya_sekiguchi]

This is why code reviews exist. The moment someone introduces self-referencing shared_ptr chains without thinking about destruction depth, you know you're in for a fun debugging session.

[u/PandaWonder01]

This isn't a C++ question, it's a question about OS stack limits