[jdq]

The code in question is most certainly not TimSort, but the rangecheck() method within it, which is copied verbatim from arrays.java, which Bloch wrote while at Sun. It's what Oracle is using to show that Bloch did reference Sun code and Android is not a clean-room implementation. It's there in the Groklaw piece, but glanced over very quickly because, well it's groklaw.

"Q. Why did you use the same rangecheck() function in Timsort as was in arrays.java?

A. It's good software engineering to reuse an existing function.

Q. But why use the exact same code?

A. I copied rangecheck() as a temporary measure, assuming this would be merged into arrays.java and my version of rangecheck() would go away.

[Discussion of Timsort dates and Android work dates.]"

[protolif]

Is this rangecheck() function that we're debating critical to the Android platform? Is that the feature that made it so popular? Clearly not, or Oracle would have made smartphones already. I'm curious as to how many different ways a range check function can be written in Java. Can we reasonably expect Bloch to re-implement his own code in a slightly different way? Should Google have diff'd Android source against Java source? What does Open Source mean to you?

[nknight]

    private void RangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
    }

If this were the basis of Oracle's copyright claim, any judge in the country would have tossed the case on summary judgement.

[tryke]

It doesn't even check for underflow!

[SeanLuke]

To do so would be meaningless, since arrays already do that.

Fun fact: Java's ArrayList RangeCheck function has had a brutally stupid misfeature for over a decade (yes, I had posted it as a bug -- ignored) which prevented its add(), set(), and get() methods from being inlined. I kid you not.

To wit: these methods all call RangeCheck, which potentially throws an exception, along these lines (here's get(i) in pseudocode):

    RangeCheck(i)
        if (i >= maxLength) throw exception about i

    get(i)
       RangeCheck(i)
       return array[i]

Until recently methods which threw exceptions could not be inlined. Thus even if get(i) was inlined, you'd still have to call an uninlinable RangeCheck(i) call every time.

This was trivially fixable:

    ThrowException(i)
        throw exception about i

    get(i)
       if (i >= maxLength) ThrowException(i)
       return array[i]

This has never been fixed. Recent improvements in HotSpot have rendered it moot though, as HotSpot can now inline the RangeCheck call. But for almost a decade ArrayList has been approximately 1/4 the speed it should have been for most common calls.