JDK-5045147 : (coll) Adding null key to empty TreeMap without Comparator should throw NPE
  • Type: Bug
  • Status: Closed
  • Resolution: Fixed
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Priority: P3
  • Affected Version: 1.3.1_06,6
  • OS: generic,solaris_8
  • CPU: generic,sparc
  • Submit Date: 2004-05-11
  • Updated Date: 2017-05-16
  • Resolved Date: 2011-04-27
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
JDK 7
7 b136Fixed
Related Reports
Duplicate :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Description
Application receives NullPointerException at TreeSet.remove(TreeSet.java:206).

1. Stacktrace
-------------
 At the moment we just have a stacktrace:


05/10/2004 11:30:54 BST 2  41 [ExecuteThread: '12' for queue: 'default'] - EXCEPTION: com.sapient.framewor
k.presentation.servlet.event.InvalidObjectException; PARAMETER INFO: linkList; PREVIOUS EXCEPTION: (EXCEPT
ION: com.sapient.framework.util.InvocationTargetException; PARAMETER INFO: com.aegir.property.presentation
.ImageAddressModuleWrapper.getLinkList(0 args); PREVIOUS EXCEPTION: (java.lang.NullPointerException:
Start server side stack trace:
java.lang.NullPointerException
        at java.util.TreeMap.compare(TreeMap.java:1042)
        at java.util.TreeMap.getEntry(TreeMap.java:326)
        at java.util.TreeMap.remove(TreeMap.java:484)
        at java.util.TreeSet.remove(TreeSet.java:206)
        at com.sapient.framework.cache.MRUCache.remove(MRUCache.java:318)
        at com.sapient.framework.cache.MRUCache.removeLast(MRUCache.java:300)
        at com.sapient.framework.cache.MRUCache.put(MRUCache.java:294)
        at com.sapient.framework.cache.MRUCache.get(MRUCache.java:240)
...


2. Small Testcase
-----------------
 We can match this stacktrace to a small testcase:

% more Test.java
import java.util.*;

public class Test {

    public static void main(String args[]) {
        Set set = new HashSet();
        System.out.println(set.getClass());
        System.out.println(set);
        set.add(null);
        System.out.println(set);
        set.remove(null);
        System.out.println(set);

        set = new TreeSet();
        System.out.println(set.getClass());
        System.out.println(set);
        set.add(null);
        System.out.println(set);
        set.remove(null);
        System.out.println(set);
    }

}

% /j2sdk1_3_1_08/bin/javac Test.java
% /j2sdk1_3_1_08/bin/java Test
class java.util.HashSet
[]
[null]
[]
class java.util.TreeSet
[]
[null]
Exception in thread "main" java.lang.NullPointerException
        at java.util.TreeMap.compare(TreeMap.java:1042)
        at java.util.TreeMap.getEntry(TreeMap.java:326)
        at java.util.TreeMap.remove(TreeMap.java:484)
        at java.util.TreeSet.remove(TreeSet.java:206)
        at Test.main(Test.java:25)
% 

 A "null" value in the data-structure is able to produce the same effect.



3. "null values cannot be added programmatically in non-empty data-structure
"null values cannot be added programmatically via TreeSet.add() in a 
non-empty data-structure:

% more Test.java
import java.util.*;

public class Test {

    public static void main(String args[]) {
        Set set = new HashSet();
        System.out.println(set.getClass());
        set.add("1");
        System.out.println(set);
        set.add(null);
        System.out.println(set);
        set.remove("1");
        System.out.println(set);
        set.remove(null);
        System.out.println(set);

        set = new TreeSet();
        System.out.println(set.getClass());
        set.add("1");
        System.out.println(set);
        set.add(null);
        System.out.println(set);
        set.remove("1");
        System.out.println(set);
        set.remove(null);
        System.out.println(set);
    }

}
% /j2sdk1_3_1_08/bin/javac Test.java
% /j2sdk1_3_1_08/bin/java Test
class java.util.HashSet
[1]
[1, null]
[null]
[]
class java.util.TreeSet
[1]
Exception in thread "main" java.lang.NullPointerException
        at java.util.TreeMap.compare(TreeMap.java:1042)
        at java.util.TreeMap.put(TreeMap.java:444)
        at java.util.TreeSet.add(TreeSet.java:193)
        at Test.main(Test.java:21)
%

 Trying to add a "null" element results in a NullPointerException in 
 TreeSet.add().

 This is inconsistent behaviour compared to an empty data-structure.
The current TreeMap implementation has a long standing bug which allows a null key to be added to the map if, and only if, the map is empty. If the map is not empty then a null key cannot be added.

Once a null key has been added to the map other operations upon the map become likely to fail unexpectedly with NPE. The null key may not be removed except my TreeMap.clear()

TreeSet.add() is also impacted as it uses a TreeMap for it's implementation. This issue was originally reported against TreeSet but the problem is more properly with TreeMap.

Comments
PUBLIC COMMENTS http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bf37edb38fbb
2011-03-17

EVALUATION This can't be done without some kind of bug compatibility mode, for which there is currently no infrastructure. Closing as "Will Not Fix".
2006-06-13

EVALUATION Unfortunately, this fix exposed too many bugs in Other Peoples' Code, so backed out for now.
2006-06-10

EVALUATION Doug Lea is providing a fix as part of 6415641: (coll) Getting NavigableMap/NavigableSet right
2006-04-21

SUGGESTED FIX Doug Lea writes: "Thanks! I have a strong sense of deja vu that I've added this before(!) but Treemap.put should have the following trap added." public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { + if (key == null) { + if (comparator == null) + throw new NullPointerException(); + comparator.compare(key, key); + } incrementSize(); root = new Entry<K,V>(key, value, null); return null; } while (true) { int cmp = compare(key, t.key); if (cmp == 0) { return t.setValue(value); } else if (cmp < 0) { if (t.left != null) { t = t.left; } else { incrementSize(); t.left = new Entry<K,V>(key, value, t); fixAfterInsertion(t.left); return null; ###@###.### 2005-05-12 02:20:02 GMT
2005-05-12

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: dragon
2004-09-08

EVALUATION (1) The API specification for TreeSet should be clarified to say that a TreeSet constructed with a null comparator does not support null elements. This is a minor bug in the API documentation. (2) A TreeSet constructed with null comparator should throw a NullPointerException when null is added to the set. This exception is required by the contract for Set.add when the set does not support null elements. This bug appears because of a related bug in TreeMap. (3) An empty TreeMap that was constructed with a null comparator should throw a NullPointerException when TreeMap.put is called with a null key. We are missing this exception only when the tree is empty. The code to place the first node in an empty tree is simply missing this test. Fixing this bug will have the effect of fixing (2) as well. (4) A TreeSet constructed with null comparator should throw a NullPointerException when null is removed from the set. The test program that is the subject of this bug report demonstrates that we do properly issue this exception. In any case, the customer cannot expect to use a natural-ordered TreeSet to contain null elements. The application code will have to be rewritten to avoid that error. ---------------------------------------------- java.util.TreeMap.put(Object key, Object value) * @throws NullPointerException key is <tt>null</tt> and this map uses * natural order, or its comparator does not tolerate * <tt>null</tt> keys. */ There is a small window in TreeMap.put, when the data structure is empty, where null can be added to the map using natural ordering. I propose that we check the comparator and key before creating the root entry. ###@###.### 2004-05-25 ---------------------------------------------- The straightforward way to fix this is to add lines 438-439 to the following loop in TreeMap: 437 if (t == null) { 438 if (comparator == null && key == null) 439 throw new NullPointerException("Null key"); 440 incrementSize(); 441 root = new Entry(key, value, null); 442 return null; 443 } However, this does not entirely solve the problem. If a TreeSet/TreeMap map has an explicit Comparator that does not handle null elements/keys, one can still insert a null element/key so long as it is the first element/key inserted into the set/map. This could be fixed by comparing a key *to itself* if it is the first one to be inserted into a TreeMap: 437 if (t == null) { 438 compare(key, key); // Throw NullPointerException if appropriate 440 incrementSize(); 441 root = new Entry(key, value, null); 442 return null; 443 } That said, it should be noted that fixing this bug has the ability to "break" existing programs regardless of which of the two approaches is taken. To wit, programs that put a single null element/key into a TreeSet/TreeMap and don't do anything else with the TreeSet/Map will break. For example, this program runs now but won't after the fix is applied: import java.util.*; class Test { public static void main(String[] args) { Set s = new TreeSet(); s.add(null); } } This does not mean that this bug should not be fixed, but it does suggest that perhaps it's more appropriate for a major release than a maintenance release. ###@###.### 2004-05-30 Will be addressed as part of JSR166 maintenance. ###@###.### 2005-03-09 03:10:31 GMT
2004-05-30