libgdx/libgdx

Remove item in ObjectMap can cause NPE

b3nk4n opened this issue · 5 comments

b3nk4n commented

Issue details

After upgrading my game from 1.9.10 to 1.12.1, I noticed that it was crashing from time to time in my postUpdate function here. After debugging a little bit, I noticed that this was not a bug in my game, but within LibGdx.

I know that in most implementations, removing an items while iterating a data structure is not always safe by default, but at least in LibGdx, the docs make me believe it is or should be:

Keys may only be in one of three locations in the backing array, allowing this map to perform very fast get, containsKey, and remove.
(source)

Returns an iterator for the values in the map. Remove is supported.
(source)

As since it worked well in version 1.9.10, I would guess there must have been a bug introduced somewhen after that version. Or the docs are not up to date anymore, which I doubt, as this would have been a backward incompatible change.

Reproduction steps/code

Using gdxVersion = '1.12.1', the following code ends up in a map that is not empty, and one item printed is unexpectedly null, which randomly caused a NPE in my games once more than one item is removed in a single iteration.

public static void main(String[] args) {
    ObjectMap<String, Integer> map = new ObjectMap<>();
    map.put("1", 1);
    map.put("2", 2);
    map.put("3", 3);
    map.put("4", 4);
    map.put("5", 5);
    map.put("6", 6);
    map.put("7", 7);
    map.put("8", 8);
    map.put("9", 9);
    map.put("10", 10);
    map.put("11", 11);
    map.put("12", 12);
    map.put("13", 13);
    map.put("14", 14);
    map.put("15", 15);
    map.put("16", 16);
    map.put("17", 17);
    map.put("18", 18);
    map.put("19", 19);
    map.put("20", 20); // < -- bug happens starting from 20 elements !? Not with 19 elements or below.

    // remove all
    for (Integer value : map.values()) {
        System.out.println(value);
        map.remove(String.valueOf(value));
    }

    System.out.println("size = " + map.size);
}

Output using version 1.12.1:

19
11
4
16
9
1
13
6
18
10
3
15
8
null
12
5
17
2
14
7
size = 1

(⚠️ please note the null value and the fact that the map is not empty after removing all items one by one!)

In the previous version 1.9.10, this bug is not happening:

Output using version 1.9.10:

10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
20
size = 0

Version of libGDX and/or relevant dependencies

  • But present in `gdxVersion = '1.12.1'
  • Bug not present in `gdxVersion = '1.9.10', which was the version I used before upgrading.

Please select the affected platforms

  • Android
  • iOS
  • HTML/GWT
  • Windows
  • Linux
  • macOS
b3nk4n commented

I could narrow it down a little that the bug must have been introduced in version 1.9.11. Bug starts appearing from that version.

b3nk4n commented

Same with deleting it via iterating ObjectMap#keys() instead, which also states the same in the docs to be remove-safe:

Returns an iterator for the keys in the map. Remove is supported.
(source)

for (String key : map.keys()) {
    System.out.println(key);
    map.remove(key);
}

Which again works fine in 1.9.10, but starting from 1.9.11 gives the following error:

Output:

19
11
4
16
9
1
Exception in thread "main" 13
java.lang.IllegalArgumentException: key cannot be null.
6
	at com.badlogic.gdx.utils.ObjectMap.locateKey(ObjectMap.java:128)
18
10
3
	at com.badlogic.gdx.utils.ObjectMap.remove(ObjectMap.java:188)
15
	at de.bsautermeister.test.game.GameScreen.main(GameScreen.java:99)
8
null
tommyettinger commented

Removing from a Map such as a HashMap while iterating over it is pretty much undefined behavior. If you were using a HashMap, you would just see an immediate crash due to a ConcurrentModificationException. When the docs say remove() is supported, they are referring to Iterator.remove(). I'll look into this a little, but removal during iteration is really only ever supported via the Iterator's remove() method, in libGDX and in the JDK itself.

tommyettinger commented

I wrote a test for this that checks libGDX ObjectMap, the related code in jdkgdxds for its ObjectObjectMap, and the standard JDK's HashMap, using your code extended out to number 29 instead of 20. ( tommyettinger/juniper@09d8a28 ). All three will not work with how you're trying to do this; HashMap crashes immediately with a ConcurrentModificationException, which could be argued would be the correct behavior for libGDX and jdkgdxds maps as well (it's just a pain to implement). All three do work if you remove via the Iterator, and you can see how that works in this linked test. Removal via the Iterator is the standard way of doing this in JDK collections, though it's understandable that libGDX types would seem different because they don't implement Map, Set, List, or other standard JDK interfaces. I'm surprised the 1.9.10 ObjectMap could remove during iteration more easily than the current ObjectMap, but that isn't something non-concurrent Maps are normally able to do, so I wouldn't be surprised if 1.9.10 suddenly failed to remove an entry.

I'm closing this because the desired behavior should not be supported anyway, and a fix has been provided. You can still comment here and I can reopen if a problem is found in the Iterator.remove() technique.

  • 👍1
b3nk4n commented

Thx for looking into this. Good to know I was just using it wrong 👍 .