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.
Posted Date : 2005-08-22 22:36:37.0

N/A

(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.

  xxxxx@xxxxx   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.


  xxxxx@xxxxx   2004-05-30

Will be addressed as part of JSR166 maintenance.
  xxxxx@xxxxx   2005-03-09 03:10:31 GMT
Doug Lea is providing a fix as part of

6415641: (coll) Getting NavigableMap/NavigableSet right
Posted Date : 2006-04-21 22:54:53.0

Unfortunately, this fix exposed too many bugs in 
Other Peoples' Code, so backed out for now.
Posted Date : 2006-06-10 02:48:06.0

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