Category Archives: Java

StackOverflowException in java.util.ArrayList due to subList()

We have experienced a problem with a StackOverflowException when calling ArrayList.add(). The application added data to the end of a list to find different possible solutions. Attempts that lead to a dead end are then truncated from the list with a call to List.subList(). This might appear like a good way of reusing the data which is still valid.

The problem arises when we do something similar to:

List list = new ArrayList();
// try solution x
list.addAll(someRangeX);
list = list.subList(0, x);
// try solution y
list.addAll(someRangeY);
list = list.subList(0, y);
// try solution z
list.addAll(someRangeZ);
list = list.subList(0, z);
// repeat for thousands of solutions

//…
list.addAll(someRangeXYZ);
// -> StackOverflowException is thrown

The answer to why this is a problem is in the first words of the JavaDoc for List.subList(). “Returns a view of a potion of the list”. The method subList() will return a new object, which has a reference back to the original list. So every time we modify the list, we have to update the parent, parents parent, parents parents parent, and so on. Enough calls to subList() will give us such a deep recursion within ArrayList that we get a StackOverflowException (at java.util.ArrayList$Sublist.add(ArrayList:1005))

This is what the code looks like in ArrayList:


public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}

Out solution is to instantiate a new List containing the sub-list elements, but no reference back to the original list.

Check Java version in class files

Java classes can be compiled for different target platforms. You could e.g. compile with JDK 7 creating class files for Java 6. The target version is encoded in the beginning of the class files.

The major version of the different Java releases are:
Java 8 = 52 (0x34)
Java 7 = 51 (0x33)
Java 6 = 50 (0x32)
Java 5 = 49 (0x31)

So the class files for Java 6 starts with

0xCA 0xFE 0xBA 0xBE 0x00 0x00 0x00 0x32

We can use the following command to find e.g. all Java 6 classes.

find . -name \*.class -exec grep -P "^\xca\xfe\xba\xbe\x00\x00\x00\x32" {} \;

Or better still, just checking first line:
find . -name \*.class -exec sh -c 'head -1 {} | grep -P "^\xca\xfe\xba\xbe\x00\x00\x00\x32" {}' \;

However, it might be more interesting to find if any of the files we compile is NOT Java 6. This might happen when compiling with JDK 7, but forgetting to set Java 1.6 as target.

find . -name \*.class -exec sh -c 'head -1 {} | grep -v -q -P "^\xca\xfe\xba\xbe\x00\x00\x00\x32" && echo "Java version is not 0x32 in file {}" &' \;

Java encoding of source files

I got a problem with some java source files, which javac couldn’t compile, because the file encoding was correct. The source files did include some Swedish UTF-8 characters.

unmappable character for encoding ASCII

So I checked what my ant environment looked like:

$ ant -diagnostics|grep encoding
file.encoding.pkg : sun.io
sun.jnu.encoding : ANSI_X3.4-1968
file.encoding : ANSI_X3.4-1968
sun.io.unicode.encoding : UnicodeLittle

Definitely not the UTF-8 encoding I desired.

Checked my environment

$ locale
locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=en_US.UTF-8
LANGUAGE=en_US:
LC_CTYPE=”en_US.UTF-8″
LC_NUMERIC=sv_SE.UTF-8
LC_TIME=sv_SE.UTF-8
LC_COLLATE=”en_US.UTF-8″
LC_MONETARY=sv_SE.UTF-8
LC_MESSAGES=”en_US.UTF-8″
LC_PAPER=sv_SE.UTF-8
LC_NAME=sv_SE.UTF-8
LC_ADDRESS=sv_SE.UTF-8
LC_TELEPHONE=sv_SE.UTF-8
LC_MEASUREMENT=sv_SE.UTF-8
LC_IDENTIFICATION=sv_SE.UTF-8
LC_ALL=

And then:

$ locale -a
C
C.UTF-8
en_AG
en_AG.utf8
en_AU.utf8
en_BW.utf8
en_CA.utf8
en_DK.utf8
en_GB.utf8
en_HK.utf8
en_IE.utf8
en_IN
en_IN.utf8
en_NG
en_NG.utf8
en_NZ.utf8
en_PH.utf8
en_SG.utf8
en_US.utf8
en_ZA.utf8
en_ZM
en_ZM.utf8
en_ZW.utf8
POSIX

Notice that sv_SE.UTF-8 is missing.

$ sudo locale-gen sv_SE.UTF-8

$ sudo dpkg-reconfigure locales

Check java file encoding again:

$ ant -diagnostics|grep encoding
file.encoding.pkg : sun.io
sun.jnu.encoding : UTF-8
file.encoding : UTF-8
sun.io.unicode.encoding : UnicodeLittle

I’m running Ubuntu 12.04 Server and the previous command worked fine the other day. I guess that there was some Ubuntu update which destroyed my environment.