RuntimeError when using `.remove()` in `separate` in very uncommon circumstances

[aatle]

Circumstances:

1. During Space.step(), a shape is removed (such as from post_solve callback). The shape removal is automatically delayed until the step finishes.
2. After the step ends, the shape removal occurs and triggers a separate callback.
3. Inside the separate callback, an object is removed.

This leads to an error:

File "C:\...\site-packages\pymunk\space.py", line 590, in step
    for obj in self._remove_later:
RuntimeError: Set changed size during iteration

What happened was that while the space was iterating over the set of objects to be removed, there was a call to .remove() in separate. Since the space is locked during this, a new object is put into the set of objects to be removed, but this is illegal as the set is being iterated. This bug is minor, and I can't really think of a practical situation where this might possibly be encountered.
In Space.step():

pymunk/pymunk/space.py

Lines 588 to 592 in ce59f9a

	self.add(*self._add_later)
	self._add_later.clear()
	for obj in self._remove_later:
	self.remove(obj)
	self._remove_later.clear()

I'd recommend that any objects removed from these special separate calls also be removed immediately after since they can be.

Slightly related code improvement

It seems that _add_later and _remove_later are sets instead of lists which doesn't seem like a good choice. Not only does this forget the actual order and is slightly slower, it also allows duplicates (space.remove(body1, body1)) in a step but not outside a step. So, they should be lists instead.

Recommended fix, assuming above code improvement is applied

self.add(*self._add_later)
self._add_later.clear()
# A separate callback may remove objects
while self._remove_later:
    remove_later = self._remove_later
    self._remove_later = []
    self.remove(*remove_later)

With python >=3.8, a walrus operator may be used for the loop condition.

Minimal reproducible example

import pymunk as pm


space = pm.Space()

space.gravity = 0, -100

body1 = pm.Body()
shape1 = pm.Circle(body1, 20)
shape1.density = 5
shape1.collision_type = 111

floor1 = pm.Segment(space.static_body, (-100,-30), (100,-30), 1)

body2 = pm.Body()
body2.position = 500,0
shape2 = pm.Circle(body2, 20)
shape2.density = 5
shape2.collision_type = 222

floor2 = pm.Segment(space.static_body, (400,-30), (600,-30), 1)

space.add(body1, shape1, body2, shape2, floor1, floor2)


def separate(arbiter: pm.Arbiter, space: pm.Space, data):
  print('SEPARATE')
  print('REMOVE 2, remove any object')
  space.remove(floor2)


def post_solve(arbiter: pm.Arbiter, space: pm.Space, data):
  print('POST-SOLVE')
  if i == 30:
    print('REMOVE 1, causes separate during step')
    space.remove(shape1)
    # space.remove(shape1, shape1, shape1, shape1)


space.add_wildcard_collision_handler(111).separate = separate
space.add_wildcard_collision_handler(222).post_solve = post_solve


for i in range(60):
  print('step START', i)
  space.step(1/60)
  print('step END', i)

[viblo]

Thanks for the report, again very comprehensive!

I dont have it on top of my head now, but I think there were some reason for set. On the other hand, I do agree that it strange that you can add/remove the same thing twice as long as you do it in a callback during a single timestep, but not otherwise. And its unfortunate that a change would potentially break some code.. I will have to think a bit.

(the bug itself should be fixed regardless of course)

[viblo]

I had time to look some more on this today.

There's some tricky cases around this logic...
How can you check if you already removed something in the separate callback? If the separate method looks like this

def separate(arbiter: pm.Arbiter, space: pm.Space, data):
  if floor2 in space.shapes:
      space.remove(floor2)

And the separate is called twice during the same step, then both times the if statement will be true, and floor2 will be added two times to the internal list.. I think this is could be why I had it as set and not list from the beginning.

[aatle]

I see. There are probably better ways to mitigate that issue, but would require breaking existing code and/or adding new methods. Then, the only possible improvement is to use a dict instead of a set, with empty values similar to Space._constraints. This would at least preserve order, not break existing code, and probably have no performance difference.

Also, checking if something is already added to a space seems to be possibly very expensive since it performs both a copy and a linear time check, when it could possibly be just a constant time hash check. So, a convenient enhancement could perhaps be Space.__contains__, to efficiently allow a conditional check prior to Space.add or Space.remove. (Even though the Space will lack __iter__ and __len__.) Would need a separate issue if good idea.

[viblo]

Recently I started to add a benchmark suite to Pymunk, to help me optimize it and Chipmunk. So far its focused on the simulation itself, but as you found now other parts can potentially be optimized. I think the dict/list copy could (should) be removed.

I was thinking, maybe it could be enough to have a type hint to show it returns a abc.collections Collection or Set instead of a list copy, and then return the keys or values (for bodies/shapes). This way you get fast lookups and no copy, and some freedom to update in future. I did a quick test in one example (the colors), with iterating the underlying space._bodies set instead of space.bodies to draw, and once the simulation becomes stable it resulted in ~10-15% higher fps. Of course, this would break the API, but I wonder if anyone ever did something with the returned list except iterating or checking for contains... It feels mostly confusing that you today can add to that list, but it wont actually add anything to the space, just to the list copy.

[viblo]

As for the bug, I think this would fix it while not breaking any current behavior:

while self._remove_later:
    rl = self._remove_later.copy()
    self._remove_later = set()
    self.remove(*rl)
    self._remove_later.difference_update(rl)

[viblo]

A question, does it matter if it removes them in order (dict)? The only visible effect I can think of is the order that separate callbacks invoked by the removals are called.

[aatle]

It's probably not too important, but it would better match how it would go if the user had used post_step_callbacks instead, as those are ordered (though docs do not say). It is also more intuitive given that users that are calling remove multiple times may not know about the deferring of the remove or that it makes it unordered for the step.

[aatle]

Also, in my own package I often returned collections.abc.KeysView (which inherits from Set and MappingView). Though, ValuesView is not set-like and would incur linear time cost on contains operations.
The benefits are pretty good: no expensive copy, set-like for keysview, automatically reflects changes in the space, better matches underlying implementation. It also gives the decision to the user whether to copy it and also what type of collection is created. Also, the inherent nature of the space's collections are more set-like than list-like.

[viblo]

I think I fixed it all so it doesnt crash now.

• The new implementation will allow you to call remove several times for the same object if its within the deferred removal state.
• When calling remove, the removal still will not happen until after the step(), or after the separate(..) completes in case the separate is triggered by a call to remove(..).