Request for review : 7121314 : Behavior mismatch between AbstractCollection.toArray(T[] ) and its spec
Ulf Zibis
Ulf.Zibis at gmx.de
Wed Mar 28 05:01:03 UTC 2012
Hi Sean,
Am 26.03.2012 07:02, schrieb Sean Chou:
>
> On Sat, Mar 24, 2012 at 5:09 AM, Ulf Zibis <Ulf.Zibis at gmx.de <mailto:Ulf.Zibis at gmx.de>> wrote:
>
> Will you please provide a jtreg style testcase with main method ?
>
> Well, as I'm missing your agreement, that David's test implementation doesn't guarantee to
> test the right toArray method of AbstractCollection as I explained before, I'm afraid that
> additional effort would be for garbage.
>
> Every testcase or fix goes this way, like the first testcase I provided. If your suggestion is
> valuable, I don't think it will be wasted.
Ok, here it is.
> Aside, as the instantiation of (several) ConcurrentHashMap subclassed test objects seems more
> expensive, I believe, my simple TestCollection would increase the performance of the testcases.
>
> What's the exact problem you want to fix in this case?
The execution time of jdk test cases.
-Ulf
-------------- next part --------------
import java.util.*;
/**
*
* @author Ulf Zibis
*/
public class TestCollection<E> extends AbstractCollection<E> {
private static final int[] DEFAULT_SIZES = new int[1];
private final E[] elements;
private int[] sizes;
private int nextSize;
public TestCollection(E[] elements) {
this.elements = elements;
DEFAULT_SIZES[0] = elements.length;
setPseudoConcurrentSizeCourse(DEFAULT_SIZES);
}
void setPseudoConcurrentSizeCourse(int... sizes) {
this.sizes = sizes;
nextSize = 0;
}
/** can change collection's size after each invocation */
@Override
public int size() {
return sizes[nextSize == sizes.length-1 ? nextSize : nextSize++];
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int pos = 0;
public boolean hasNext() {
return pos < sizes[nextSize];
}
public E next() {
return elements[pos++];
}
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
};
}
}
-------------- next part --------------
import java.util.Arrays;
/**
* @test
* @summary check result, especially if the collection concurrently changes size
* @bug 7121314
* @author Ulf Zibis
*/
public class ToArray extends InfraStructure {
static final Object[] OBJECTS = { new Object(), new Object(), new Object() };
static final TestCollection<?> CANDIDATE = new TestCollection<Object>(OBJECTS);
static final int SIZE = OBJECTS.length;
Object[] a;
Object[] res;
@Override
protected void test() throws Throwable {
// Check incompatible type of target array
try {
a = new String[SIZE];
res = CANDIDATE.toArray(a);
check(false);
} catch (Throwable t) {
check(t instanceof ArrayStoreException);
}
// Check more elements than a.length
a = new Object[SIZE-1]; // appears too small
res = CANDIDATE.toArray(a);
check(res != a);
check(res[SIZE-1] != null);
// Check equal elements as a.length
a = new Object[SIZE]; // appears to match
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] != null);
// Check equal elements as a.length
a = new Object[SIZE+1]; // appears too big
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] == null);
// Check less elements than expected, but more than a.length
a = new Object[SIZE-2]; // appears too small
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE, SIZE-1);
res = CANDIDATE.toArray(a);
check(res != a);
check(res.length == SIZE-1);
check(res[SIZE-2] != null);
// Check less elements than expected, but equal as a.length
a = Arrays.copyOf(OBJECTS, SIZE); // appears to match
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE, SIZE-1);
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] == null);
// Check more elements than expected and more than a.length
a = new Object[SIZE-1]; // appears to match
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE-1, SIZE);
res = CANDIDATE.toArray(a);
check(res != a);
check(res[SIZE-1] != null);
// Check more elements than expected, but equal as a.length
a = new Object[SIZE-1]; // appears to match
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE-2, SIZE-1);
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] != null);
// Check more elements than expected, but less than a.length
a = Arrays.copyOf(OBJECTS, SIZE); // appears to match
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE-2, SIZE-1);
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] == null);
test_7121314();
}
/**
* @bug 7121314
* @summary return the original array if the collection concurrently shrinks and will fit
*/
protected void test_7121314() throws Throwable {
// Check equal elements as a.length, but less than expected
a = new Object[SIZE-1]; // appears too small
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE, SIZE-1);
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] != null);
// Check less elements than a.length and less than expected
a = Arrays.copyOf(OBJECTS, SIZE-1); // appears too small
CANDIDATE.setPseudoConcurrentSizeCourse(SIZE, SIZE-2);
res = CANDIDATE.toArray(a);
check(res == a);
check(res[a.length-1] == null);
}
public static void main(String[] args) throws Throwable {
run(new ToArray());
}
}
-------------- next part --------------
/*
* Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package java.util;
/**
* This class provides a skeletal implementation of the <tt>Collection</tt>
* interface, to minimize the effort required to implement this interface. <p>
*
* To implement an unmodifiable collection, the programmer needs only to
* extend this class and provide implementations for the <tt>iterator</tt> and
* <tt>size</tt> methods. (The iterator returned by the <tt>iterator</tt>
* method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
*
* To implement a modifiable collection, the programmer must additionally
* override this class's <tt>add</tt> method (which otherwise throws an
* <tt>UnsupportedOperationException</tt>), and the iterator returned by the
* <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
* method.<p>
*
* The programmer should generally provide a void (no argument) and
* <tt>Collection</tt> constructor, as per the recommendation in the
* <tt>Collection</tt> interface specification.<p>
*
* The documentation for each non-abstract method in this class describes its
* implementation in detail. Each of these methods may be overridden if
* the collection being implemented admits a more efficient implementation.<p>
*
* This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @author Ulf Zibis
* @see Collection
* @since 1.2
*/
public abstract class AbstractCollection<E> implements Collection<E> {
/**
* Sole constructor. (For invocation by subclass constructors, typically
* implicit.)
*/
protected AbstractCollection() {
}
// Query Operations
/**
* Returns an iterator over the elements contained in this collection.
*
* @return an iterator over the elements contained in this collection
*/
public abstract Iterator<E> iterator();
public abstract int size();
/**
* {@inheritDoc}
*
* <p>This implementation returns <tt>size() == 0</tt>.
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over the elements in the collection,
* checking each element in turn for equality with the specified element.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
/**
* {@inheritDoc}
*
* <p>This implementation returns an array containing all the elements
* returned by this collection's iterator, in the same order, stored in
* consecutive elements of the array, starting with index {@code 0}.
* The length of the returned array is equal to the number of elements
* returned by the iterator, even if the size of this collection changes
* during iteration, as might happen if the collection permits
* concurrent modification during iteration. The {@code size} method is
* called only as an optimization hint; the correct result is returned
* even if the iterator returns a different number of elements.
*
* <p>This method is equivalent to:
*
* <pre> {@code
* List<E> list = new ArrayList<E>(size());
* for (E e : this)
* list.add(e);
* return list.toArray();
* }</pre>
*/
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
Iterator<E> it = iterator();
int i = 0;
while (i < r.length) {
if (!it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i++] = it.next();
}
return finishToArray(r, i, it);
}
/**
* {@inheritDoc}
*
* <p>This implementation returns an array containing all the elements
* returned by this collection's iterator in the same order, stored in
* consecutive elements of the array, starting with index {@code 0}.
* If the number of elements returned by the iterator is too large to
* fit into the specified array, then the elements are returned in a
* newly allocated array with length equal to the number of elements
* returned by the iterator, even if the size of this collection
* changes during iteration, as might happen if the collection permits
* concurrent modification during iteration. The {@code size} method is
* called only as an optimization hint; the correct result is returned
* even if the iterator returns a different number of elements.
*
* <p>This method is equivalent to:
*
* <pre> {@code
* List<E> list = new ArrayList<E>(size());
* for (E e : this)
* list.add(e);
* return list.toArray(a);
* }</pre>
*
* @throws ArrayStoreException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[]) java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
int i = 0;
while (i < r.length) {
if (!it.hasNext()) { // fewer elements than expected
if (a == r) {
a[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else { // Element r[i+1] is guaranteed to be null from array initialization.
System.arraycopy(r, 0, a, 0, a.length > i ? i+1 : i); // ensure null-termination
}
return a;
}
r[i++] = (T)it.next();
}
return finishToArray(r, i, it);
}
/**
* Reallocates the array being used within toArray when the iterator
* returned more elements than expected, and finishes filling it from
* the iterator.
*
* @param r the array, replete with previously stored elements
* @param i the current index, likewise capacity of r
* @param it the in-progress iterator over this collection
* @return array containing the elements in the given array, plus any
* further elements returned by the iterator, trimmed to size
*/
private <T> T[] finishToArray(T[] r, int i, Iterator<E> it) {
// if more elements than expected
for (int cap = i; it.hasNext(); i++) {
if (i == cap) {
cap = secureArraySize(i, (Math.max(0, size() - i) << 1) + 1);
//cap = secureArraySize(i, (i >> 4) + 1); // alternative !
r = Arrays.copyOf(r, cap);
}
r[i] = (T)it.next();
}
return (i == r.length) ? // trim if overallocated
r : Arrays.copyOf(r, i);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* @param old the current size of the array
* @param inc the requested increment
*/
private int secureArraySize(int old, int inc) {
// overflow-conscious code
if (old + inc - MAX_ARRAY_SIZE <= 0)
return old + inc;
if (++old < 0) // overflow
throw new OutOfMemoryError
("Required array size exceeds VM limit");
return (old > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// Modification Operations
/**
* {@inheritDoc}
*
* <p>This implementation always throws an
* <tt>UnsupportedOperationException</tt>.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @throws IllegalStateException {@inheritDoc}
*/
public boolean add(E e) {
throw new UnsupportedOperationException();
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over the collection looking for the
* specified element. If it finds the element, it removes the element
* from the collection using the iterator's remove method.
*
* <p>Note that this implementation throws an
* <tt>UnsupportedOperationException</tt> if the iterator returned by this
* collection's iterator method does not implement the <tt>remove</tt>
* method and this collection contains the specified object.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
// Bulk Operations
/**
* {@inheritDoc}
*
* <p>This implementation iterates over the specified collection,
* checking each element returned by the iterator in turn to see
* if it's contained in this collection. If all elements are so
* contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
*
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @see #contains(Object)
*/
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over the specified collection, and adds
* each object returned by the iterator to this collection, in turn.
*
* <p>Note that this implementation will throw an
* <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
* overridden (assuming the specified collection is non-empty).
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @throws IllegalStateException {@inheritDoc}
*
* @see #add(Object)
*/
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over this collection, checking each
* element returned by the iterator in turn to see if it's contained
* in the specified collection. If it's so contained, it's removed from
* this collection with the iterator's <tt>remove</tt> method.
*
* <p>Note that this implementation will throw an
* <tt>UnsupportedOperationException</tt> if the iterator returned by the
* <tt>iterator</tt> method does not implement the <tt>remove</tt> method
* and this collection contains one or more elements in common with the
* specified collection.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*
* @see #remove(Object)
* @see #contains(Object)
*/
public boolean removeAll(Collection<?> c) {
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over this collection, checking each
* element returned by the iterator in turn to see if it's contained
* in the specified collection. If it's not so contained, it's removed
* from this collection with the iterator's <tt>remove</tt> method.
*
* <p>Note that this implementation will throw an
* <tt>UnsupportedOperationException</tt> if the iterator returned by the
* <tt>iterator</tt> method does not implement the <tt>remove</tt> method
* and this collection contains one or more elements not present in the
* specified collection.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*
* @see #remove(Object)
* @see #contains(Object)
*/
public boolean retainAll(Collection<?> c) {
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
/**
* {@inheritDoc}
*
* <p>This implementation iterates over this collection, removing each
* element using the <tt>Iterator.remove</tt> operation. Most
* implementations will probably choose to override this method for
* efficiency.
*
* <p>Note that this implementation will throw an
* <tt>UnsupportedOperationException</tt> if the iterator returned by this
* collection's <tt>iterator</tt> method does not implement the
* <tt>remove</tt> method and this collection is non-empty.
*
* @throws UnsupportedOperationException {@inheritDoc}
*/
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
// String conversion
/**
* Returns a string representation of this collection. The string
* representation consists of a list of the collection's elements in the
* order they are returned by its iterator, enclosed in square brackets
* (<tt>"[]"</tt>). Adjacent elements are separated by the characters
* <tt>", "</tt> (comma and space). Elements are converted to strings as
* by {@link String#valueOf(Object)}.
*
* @return a string representation of this collection
*/
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
}
-------------- next part --------------
/**
*
* @author Ulf Zibis
*/
public abstract class InfraStructure {
private static volatile int passed = 0, failed = 0;
private static void pass() { passed++; }
private static void fail() { failed++; Thread.dumpStack(); }
private static void fail(String msg) { System.out.println(msg); fail(); }
private static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
static void check(boolean cond) { if (cond) pass(); else fail(); }
static void equals(Object x, Object y) {
if (x == null ? y == null : x.equals(y)) pass();
else {System.out.println(x + " not equal to " + y); fail(); }}
protected abstract void test() throws Throwable;
protected static void run(InfraStructure testcase) throws Throwable {
try { testcase.test(); } catch (Throwable t) { unexpected(t); }
System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
if (failed > 0) throw new Exception("Some tests failed");
}
}
More information about the core-libs-dev
mailing list