United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-5045147 : (coll) Adding null key to empty TreeMap without Comparator should throw NPE

Details
Type:
Bug
Submit Date:
2004-05-11
Status:
Closed
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2011-04-27
Component:
core-libs
OS:
solaris_8,generic
Sub-Component:
java.util:collections
CPU:
sparc,generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
1.3.1_06,6
Fixed Versions:

Related Reports
Backport:
Duplicate:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:

Sub Tasks

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
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
CONVERTED DATA

BugTraq+ Release Management Values

COMMIT TO FIX:
dragon


                                     
2004-09-08
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
EVALUATION

Doug Lea is providing a fix as part of

6415641: (coll) Getting NavigableMap/NavigableSet right
                                     
2006-04-21
EVALUATION

Unfortunately, this fix exposed too many bugs in 
Other Peoples' Code, so backed out for now.
                                     
2006-06-10
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
PUBLIC COMMENTS

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



Hardware and Software, Engineered to Work Together