Entt: Heap corruption if destroying entity with component containing unordered_set

[jaspercb]

Was playing around with entt for a project and started getting segfaults immediately after/during destroying entities. I ended up isolating the problem in the following code segment. Switching the unordered set to a vector seems to fix the problem and is my local band-aid, but I just wanted to give a heads-up that the heap seems to get thoroughly thrashed if components contain unordered sets - likely also other data structures, haven't checked any other than unordered_set and vector. Apologies if this issue is already known/some arcane restriction of C++ that can't be worked around.

#include <unordered_set>
#include "entt/src/entt/entt.hpp"

typedef std::uint32_t Entity;

struct Collidable {
  std::unordered_set<Entity> ignored;
  void addIgnored(Entity other) {
    ignored.insert(other);
  }
};

int main() {
  entt::Registry<Entity> registry;
  auto one = registry.create();
  for (int i=0; i<100; i++) {
    auto ent = registry.create();
    auto &collide = registry.assign<Collidable>(ent);
    collide.addIgnored(one);
  }
  std::vector<Entity> toDestroy;
  registry.view<Collidable>().each(
    [&toDestroy](auto entity, const auto &collide) {
    toDestroy.push_back(entity);
  });

  for (auto i : toDestroy) {
    registry.destroy(i);
  }
}

[skypjack]

Is your snippet enough to reproduce the error?
How can I observe that _it ruins the heap_? I mean, does it crash? What else otherwise?

The code you posted looks perfectly fine. However, if it's enough to reproduce the error, it's almost solved.

If you didn't do it yet, compile your software in debug and run it. In case you are doing something wrong with identifiers, the registry will assert and give you the right line.

[skypjack]

Ok, nevermind, found it. Pretty interesting indeed.

Now I'm short in time. I'll put down all the details in a comment later.
Of course, the issue will be fixed upstream soon.
Thanks to @morbo84 that helped me to investigate the problem.

Thank you also for pointing it out.

[skypjack]

The problem is due to the fact that a destroy could perform a self assignment on components to reduce the number of operations.
It works fine as long as your components are trivial, even if the standard doesn't give you much guarantees actually. On the other side, it's all the way wrong when it comes to work with classes from the standard template library (as an example an std::unordered_set). See here for more details.
Ironically, the fact that _it works_ for you with an std::vector isn't a solution, it looks more like a lucky result that comes out from an UB under the hood. :-)

---

In other terms and to sum up, if set is an std::unordered_set, you cannot do this:

set = std::move(set);

Unfortunately, it can happen that the registry does something similar internally and under certain conditions.
You spotted exactly the case that triggers the problem fortunately, thank you very much.

---

I'll push the fix upstream as soon as possible, then I'll create a patch version for EnTT to use as a reference.

[skypjack]

To be clear, the issue can be reproduced with a shorter snippet:

entt::DefaultRegistry registry;
auto entity = registry.create();
registry.assign<std::unordered_set<int>>(entity).insert(42);
registry.destroy(entity);

[skypjack]

Fixed upstream. See v2.4.2 for more details.
Thanks once more to @morbo84 for the help.

Hope it works fine for you now.
Do not forget to star the project to help spreading it more and more.

[skypjack]

Another test done on the underlying data structures, probably better than testing the registry:

    entt::SparseSet<unsigned int, std::unordered_set<int>> set;
    set.construct(0).insert(42);
    set.destroy(0);

I'll push it with the snapshot branch. Until then, the one upstream does the job pretty well.