United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-7144488 (coll) Infinite recursion for some equals tests in Collections
JDK-7144488 : (coll) Infinite recursion for some equals tests in Collections

Details
Type:
Bug
Submit Date:
2012-02-10
Status:
Closed
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2012-05-09
Component:
core-libs
OS:
windows_7
Sub-Component:
java.util:collections
CPU:
x86
Priority:
P3
Resolution:
Fixed
Affected Versions:
6u29
Fixed Versions:

Related Reports
Backport:
Backport:
Relates:
Relates:

Sub Tasks

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

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.
                                     
2012-02-10
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);}
    }
                                     
2012-02-10
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.
                                     
2012-02-23



Hardware and Software, Engineered to Work Together