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.