JDK-7144488 : (coll) Infinite recursion for some equals tests in Collections
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 6u29
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: windows_7
  • CPU: x86
  • Submitted: 2012-02-10
  • Updated: 2012-10-08
  • Resolved: 2012-05-09
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 Availability Release.

To download the current JDK release, click here.
JDK 6 JDK 7 JDK 8
6u34Fixed 7u6Fixed 8 b29Fixed
Related Reports
Relates :  
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.6.0_29"
Java(TM) SE Runtime Environment (build 1.6.0_29-b11)
Java HotSpot(TM) 64-Bit Server VM (build 20.4-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]

A DESCRIPTION OF THE PROBLEM :
StackOverflowError occurres in the following code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List list = Collections.synchronizedList(new ArrayList());
        list.add(list);
        list.remove(list);
    }
}

Because ArrayList#remove(Object) is:

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { // call equals
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

Collections$SynchronizedList#equals(Object) is:

        public boolean equals(Object o) {
            synchronized(mutex) {return list.equals(o);}
        }

Variable list is actual instance of List. Variable o is instance of Collections$SynchronizedList.

Called AbstractList#equals(Object) is:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator e2 = ((List) o).listIterator();
        while(e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2))) // check each elements
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }

Variable o, o1 and o2 are instance of Collections$SynchronizedList. So this method call Collections$SynchronizedList#equals(Object).

And loop call AbstractList#equals(Object) and Collections$SynchronizedList#equals(Object).

REGRESSION.  Last worked in version 6u29

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and execute the following code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List list = Collections.synchronizedList(new ArrayList());
        list.add(list);
        list.remove(list);
    }
}


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
StackOverflowError does not occur.
ACTUAL -
StackOverflowError occurred.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Exception in thread "main" java.lang.StackOverflowError
	at java.util.LinkedList.listIterator(Unknown Source)
	at java.util.AbstractList.listIterator(Unknown Source)
	at java.util.Collections$SynchronizedList.listIterator(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Source)
	at java.util.AbstractList.equals(Unknown Source)
	at java.util.Collections$SynchronizedList.equals(Unknown Sour


( This report has more than 16,000 characters and has been truncated. )

Comments
EVALUATION In general there is no attempt to make self-containment work for collection classes. This was a deliberate design decision (ref: Doug Lea). In this particular case of the equals method there are two factors that make this worth fixing: 1. Having a check for o==this is idiomatic (see "Effective Java" Item 7) 2. Other wrappers (ie the CheckedXXX wrappers) already have equals methods of this form. So we now have consistent behaviour in this area.
23-02-2012

EVALUATION good catch from submitter. This is not a regression though. I can reproduce the issue in any JDK update. Will target for JDK6 updates and later JDK families.
10-02-2012

SUGGESTED FIX CUSTOMER SUBMITTED WORKAROUND : Change Collections$SynchronizedList#equals(Object) method like the following: public boolean equals(Object o) { synchronized(mutex) {return this == o ? true : list.equals(o);} }
10-02-2012