concurrent/ArrayBlockingQueue/WhiteBox.java

/*
 * 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.
 *
 * 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.
 */

/*
 * This file is available under and governed by the GNU General Public
 * License version 2 only, as published by the Free Software Foundation.
 * However, the following notice accompanied the original version of this
 * file:
 *
 * Written by Martin Buchholz with assistance from members of JCP
 * JSR-166 Expert Group and released to the public domain, as
 * explained at http://creativecommons.org/publicdomain/zero/1.0/
 */

/*
 * @test
 * @modules java.base/java.util.concurrent:open
 * @run testng WhiteBox
 * @summary White box tests of implementation details
 */

import static org.testng.Assert.*;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import java.lang.ref.WeakReference;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.function.BooleanSupplier;

@Test
public class WhiteBox {
    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    final MethodHandles.Lookup lookup = MethodHandles.lookup();
    final VarHandle ITRS, ITEMS, TAKEINDEX, PUTINDEX, COUNT, HEAD, NEXT, PREVTAKEINDEX;

    WhiteBox() throws ReflectiveOperationException {
        Class<?> qClass = ArrayBlockingQueue.class;
        Class<?> itrClass  = Class.forName(qClass.getName() + "$Itr");
        Class<?> itrsClass = Class.forName(qClass.getName() + "$Itrs");
        Class<?> nodeClass = Class.forName(itrsClass.getName() + "$Node");
        ITRS      = findVarHandle(qClass, "itrs", itrsClass);
        ITEMS     = findVarHandle(qClass, "items", Object[].class);
        TAKEINDEX = findVarHandle(qClass, "takeIndex", int.class);
        PUTINDEX  = findVarHandle(qClass, "putIndex", int.class);
        COUNT     = findVarHandle(qClass, "count", int.class);
        HEAD      = findVarHandle(itrsClass, "head", nodeClass);
        NEXT      = findVarHandle(nodeClass, "next", nodeClass);
        PREVTAKEINDEX = findVarHandle(itrClass, "prevTakeIndex", int.class);
    }

    VarHandle findVarHandle(Class<?> recv, String name, Class<?> type)
        throws ReflectiveOperationException {
        return MethodHandles.privateLookupIn(recv, lookup)
            .findVarHandle(recv, name, type);
    }

    Object itrs(ArrayBlockingQueue q) { return ITRS.get(q); }
    Object[] items(ArrayBlockingQueue q) { return (Object[]) ITEMS.get(q); }
    int takeIndex(ArrayBlockingQueue q) { return (int) TAKEINDEX.get(q); }
    int putIndex(ArrayBlockingQueue q) { return (int) PUTINDEX.get(q); }
    int count(ArrayBlockingQueue q) { return (int) COUNT.get(q); }
    Object head(Object itrs) { return HEAD.get(itrs); }
    Object next(Object node) { return NEXT.get(node); }
    int prevTakeIndex(Iterator itr) { return (int) PREVTAKEINDEX.get(itr); }

    boolean isDetached(Iterator it) {
        return prevTakeIndex(it) < 0;
    }

    void assertIteratorExhausted(Iterator it) {
        if (rnd.nextBoolean()) {
            assertTrue(!it.hasNext());
            assertTrue(isDetached(it));
        }
        if (rnd.nextBoolean()) {
            it.forEachRemaining(e -> { throw new AssertionError(); });
            assertTrue(isDetached(it));
        }
        if (rnd.nextBoolean())
            try { it.next(); fail("should throw"); }
            catch (NoSuchElementException success) {}
    }

    List<Iterator> trackedIterators(ArrayBlockingQueue q) {
        List<Iterator> its = new ArrayList<>();
        Object itrs = itrs(q);
        if (itrs != null) {
            for (Object p = head(itrs); p != null; p = next(p))
                its.add(((WeakReference<Iterator>)(p)).get());
            Collections.reverse(its);
        }
        return its;
    }

    List<Iterator> attachedIterators(ArrayBlockingQueue q) {
        List<Iterator> its = new ArrayList<>();
        Object itrs = itrs(q);
        if (itrs != null) {
            for (Object p = head(itrs); p != null; p = next(p)) {
                Iterator it = ((WeakReference<Iterator>)(p)).get();
                if (it != null && !isDetached(it))
                    its.add(it);
            }
            Collections.reverse(its);
        }
        return its;
    }

    void assertRemoveThrowsISE(Iterator it) {
        if (rnd.nextBoolean())
            try { it.remove(); fail("should throw"); }
            catch (IllegalStateException success) {}
    }

    void assertRemoveHasNoEffect(Iterator it, Collection c) {
        if (rnd.nextBoolean()) {
            int size = c.size();
            it.remove(); // no effect
            assertEquals(c.size(), size);
            assertRemoveThrowsISE(it);
        }
    }

    void checkIterationSanity(Queue q) {
        if (rnd.nextBoolean())
            return;
        int size = q.size();
        Object[] a = q.toArray();
        Object[] b = new Object[size+2];
        Arrays.fill(b, Boolean.TRUE);
        Object[] c = q.toArray(b);
        assertEquals(a.length, size);
        assertSame(b, c);
        assertNull(b[size]);
        assertSame(b[size+1], Boolean.TRUE);
        assertEquals(q.toString(), Arrays.toString(a));
        Integer[] xx = null, yy = null;
        if (size > 0) {
            xx = new Integer[size - 1];
            Arrays.fill(xx, 42);
            yy = ((Queue<Integer>)q).toArray(xx);
            for (Integer zz : xx)
                assertEquals(42, (int) zz);
        }
        Iterator it = q.iterator();
        for (int i = 0; i < size; i++) {
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            Object x = it.next();
            assertSame(x, a[i]);
            assertSame(x, b[i]);
            if (xx != null) assertSame(x, yy[i]);
        }
        if (rnd.nextBoolean()) assertTrue(!it.hasNext());
    }

    /**
     * Instead of having putIndex (and takeIndex) at the initial
     * default of 0, move them to a random location.
     */
    void randomizePutIndex(ArrayBlockingQueue q) {
        assertTrue(q.isEmpty());
        int capacity = q.remainingCapacity();
        int n = rnd.nextInt(capacity + 1);
        int putIndex = putIndex(q);
        for (int i = n; i-->0; ) q.add(Boolean.TRUE);
        for (int i = n; i-->0; ) q.remove();
        assertEquals(putIndex(q), (putIndex + n) % items(q).length);
    }

    /** No guarantees, but effective in practice. */
    static void forceFullGc() {
        CountDownLatch finalizeDone = new CountDownLatch(1);
        WeakReference<?> ref = new WeakReference<Object>(new Object() {
            protected void finalize() { finalizeDone.countDown(); }});
        try {
            for (int i = 0; i < 10; i++) {
                System.gc();
                if (finalizeDone.await(1L, TimeUnit.SECONDS) && ref.get() == null) {
                    System.runFinalization(); // try to pick up stragglers
                    return;
                }
            }
        } catch (InterruptedException unexpected) {
            throw new AssertionError("unexpected InterruptedException");
        }
        throw new AssertionError("failed to do a \"full\" gc");
    }

    static void gcAwait(BooleanSupplier s) {
        for (int i = 0; i < 10; i++) {
            if (s.getAsBoolean())
                return;
            forceFullGc();
        }
        throw new AssertionError("failed to satisfy condition");
    }

    public void clear_willClearItrs() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(2, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            assertTrue(q.add(i));
        assertNull(itrs(q));
        for (int i = 0; i < capacity; i++) {
            its.add(q.iterator());
            assertEquals(trackedIterators(q), its);
            q.poll();
            q.add(capacity + i);
        }
        q.clear();
        assertNull(itrs(q));
        int j = 0;
        for (Iterator it : its) {
            assertTrue(isDetached(it));
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            if (rnd.nextBoolean()) {
                assertEquals(it.next(), j);
                assertIteratorExhausted(it);
            }
            j++;
        }
    }

    public void queueEmptyingWillClearItrs() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(2, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            q.add(i);
        assertNull(itrs(q));
        for (int i = 0; i < capacity; i++) {
            its.add(q.iterator());
            assertEquals(trackedIterators(q), its);
            q.poll();
            q.add(capacity+i);
        }
        for (int i = 0; i < capacity; i++)
            q.poll();
        assertNull(itrs(q));
        int j = 0;
        for (Iterator it : its) {
            assertTrue(isDetached(it));
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            if (rnd.nextBoolean()) {
                assertEquals(it.next(), j);
                assertIteratorExhausted(it);
            }
            j++;
        }
    }

    public void advancing2CyclesWillRemoveIterators() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(2, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            q.add(i);
        assertNull(itrs(q));
        for (int i = capacity; i < 3 * capacity; i++) {
            its.add(q.iterator());
            assertEquals(trackedIterators(q), its);
            q.poll();
            q.add(i);
        }
        for (int i = 3 * capacity; i < 4 * capacity; i++) {
            assertEquals(trackedIterators(q), its.subList(capacity,2*capacity));
            q.poll();
            q.add(i);
        }
        assertNull(itrs(q));
        int j = 0;
        for (Iterator it : its) {
            assertTrue(isDetached(it));
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            if (rnd.nextBoolean()) {
                assertEquals(it.next(), j);
                assertIteratorExhausted(it);
            }
            j++;
        }
    }

    /**
     * Interior removal of elements used by an iterator will cause it
     * to be untracked.
     */
    public void interiorRemovalOfElementsUsedByIterator() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        q.add(0);
        for (int i = 1; i < 2 * capacity; i++) {
            q.add(i);
            Integer[] elts = { -1, -2, -3 };
            for (Integer elt : elts) q.add(elt);
            assertEquals(q.remove(), i - 1);
            Iterator it = q.iterator();
            assertEquals(it.next(), i);
            assertEquals(it.next(), elts[0]);
            Collections.shuffle(Arrays.asList(elts));
            assertTrue(q.remove(elts[0]));
            assertTrue(q.remove(elts[1]));
            assertEquals(trackedIterators(q), Collections.singletonList(it));
            assertTrue(q.remove(elts[2]));
            assertNull(itrs(q));
            assertEquals(it.next(), -2);
            assertIteratorExhausted(it);
            assertTrue(isDetached(it));
        }
    }

    public void iteratorsOnEmptyQueue() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(1, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        for (int i = 0; i < 4; i++) {
            Iterator it = q.iterator();
            assertNull(itrs(q));
            assertIteratorExhausted(it);
            assertTrue(isDetached(it));
            assertRemoveThrowsISE(it);
        }
    }

    public void interiorRemovalOfIteratorsLastElement() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(3, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            q.add(i);
        for (int i = 0; i < capacity; i++) {
            Iterator it = q.iterator();
            its.add(it);
            for (int j = 0; j < i; j++)
                assertEquals(j, it.next());
            assertEquals(attachedIterators(q), its);
        }
        q.remove(capacity - 1);
        assertEquals(attachedIterators(q), its);
        for (int i = 1; i < capacity - 1; i++) {
            q.remove(capacity - i - 1);
            Iterator it = its.get(capacity - i);
            assertTrue(isDetached(it));
            assertEquals(attachedIterators(q), its.subList(0, capacity - i));
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            assertEquals(it.next(), capacity - i);
            assertIteratorExhausted(it);
        }
        assertEquals(attachedIterators(q), its.subList(0, 2));
        q.remove(0);
        assertTrue(q.isEmpty());
        assertNull(itrs(q));
        Iterator it = its.get(0);
        assertEquals(it.next(), 0);
        assertRemoveHasNoEffect(it, q);
        assertIteratorExhausted(it);
        assertTrue(isDetached(it));
        assertRemoveHasNoEffect(its.get(1), q);
    }

    /**
     * Checks "interior" removal of alternating elements, straddling 2 cycles
     */
    public void interiorRemovalOfAlternatingElements() {
        boolean fair = rnd.nextBoolean();
        int capacity = 2 * rnd.nextInt(2, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        List<Iterator> its = new ArrayList<>();
        // Move takeIndex to middle
        for (int i = 0; i < capacity/2; i++) {
            assertTrue(q.add(i));
            assertEquals(q.poll(), i);
        }
        assertEquals(takeIndex(q), capacity/2);
        for (int i = 0; i < capacity; i++)
            q.add(i);
        for (int i = 0; i < capacity; i++) {
            Iterator it = q.iterator();
            its.add(it);
            for (int j = 0; j < i; j++)
                assertEquals(j, it.next());
            assertEquals(attachedIterators(q), its);
        }

        // Remove all even elements, in either direction, using
        // q.remove(), or iterator.remove()
        switch (rnd.nextInt(3)) {
        case 0:
            for (int i = 0; i < capacity; i+=2) assertTrue(q.remove(i));
            break;
        case 1:
            for (int i = capacity - 2; i >= 0; i-=2) assertTrue(q.remove(i));
            break;
        case 2:
            Iterator it = q.iterator();
            while (it.hasNext()) {
                int i = (Integer) it.next();
                if ((i & 1) == 0)
                    it.remove();
            }
            break;
        default: throw new AssertionError();
        }
        assertEquals(attachedIterators(q), its);

        for (int i = 0; i < capacity; i++) {
            Iterator it = its.get(i);
            boolean even = ((i & 1) == 0);
            if (even) {
                if (rnd.nextBoolean()) assertTrue(it.hasNext());
                assertEquals(i, it.next());
                for (int j = i+1; j < capacity; j += 2)
                    assertEquals(j, it.next());
                assertTrue(!isDetached(it));
                assertTrue(!it.hasNext());
                assertTrue(isDetached(it));
            } else { /* odd */
                if (rnd.nextBoolean()) assertTrue(it.hasNext());
                assertRemoveHasNoEffect(it, q);
                assertEquals(i, it.next());
                for (int j = i+2; j < capacity; j += 2)
                    assertEquals(j, it.next());
                assertTrue(!isDetached(it));
                assertTrue(!it.hasNext());
                assertTrue(isDetached(it));
            }
        }
        assertEquals(trackedIterators(q), Collections.emptyList());
        assertNull(itrs(q));
    }

    public void garbageCollectionOfUnreachableIterators() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(1, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++) q.add(i);
        for (int i = 0; i < capacity; i++) its.add(q.iterator());
        assertEquals(attachedIterators(q), its);
        its = null;
        gcAwait(() -> {
            List<Iterator> trackedIterators = trackedIterators(q);
            assertEquals(trackedIterators.size(), capacity);
            for (Iterator x : trackedIterators)
                if (x != null) return false;
            return true;
        });
        Iterator it = q.iterator(); //
        assertEquals(trackedIterators(q), Collections.singletonList(it));
    }

    public void garbageCollectionOfUnreachableIteratorsWithRandomlyRetainedSubset() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        List<Iterator> its = new ArrayList<>();
        List<Iterator> retained = new ArrayList<>();
        final int size = 1 + rnd.nextInt(capacity);
        for (int i = 0; i < size; i++) q.add(i);
        for (int i = 0; i < size; i++) its.add(q.iterator());
        assertEquals(attachedIterators(q), its);
        // Leave sufficient gaps in retained
        for (int i = 0; i < size; i+= 2+rnd.nextInt(3))
            retained.add(its.get(i));
        its = null;
        gcAwait(() -> {
            List<Iterator> trackedIterators = trackedIterators(q);
            assertEquals(trackedIterators.size(), size);
            for (Iterator it : trackedIterators)
                if ((it != null) ^ retained.contains(it)) return false;
            return true;
        });
        Iterator it = q.iterator(); // trigger another sweep
        retained.add(it);
        assertEquals(trackedIterators(q), retained);
    }

    /**
     * Checks incremental sweeping of unreachable iterators.
     * Excessively white box?!
     */
    public void incrementalSweepingOfUnreachableIterators() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        final int SHORT_SWEEP_PROBES = 4;
        final int LONG_SWEEP_PROBES = 16;
        final int PROBE_HOP = LONG_SWEEP_PROBES + 6 * SHORT_SWEEP_PROBES;
        final int PROBE_HOP_COUNT = 10;
        // Expect around 8 sweeps per PROBE_HOP
        final int SWEEPS_PER_PROBE_HOP = 8;
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            q.add(i);
        for (int i = 0; i < PROBE_HOP_COUNT * PROBE_HOP; i++)
            its.add(q.iterator());
        assertEquals(attachedIterators(q), its);
        // make some garbage, separated by PROBE_HOP
        for (int i = 0; i < its.size(); i += PROBE_HOP)
            its.set(i, null);
        its.removeIf(it -> it == null);
        forceFullGc();
        int retries;
        for (retries = 0;
             trackedIterators(q).contains(null) && retries < 1000;
             retries++)
            // one round of sweeping
            its.add(q.iterator());
        assertTrue(retries >= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP - 2));
        assertTrue(retries <= PROBE_HOP_COUNT * (SWEEPS_PER_PROBE_HOP + 2));
        assertEquals(trackedIterators(q), its);
    }

    public void Iterator_remove_safetyWhileInDetachedMode() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity/2; i++) {
            q.add(i);
            q.remove();
        }
        assertEquals(takeIndex(q), capacity/2);
        for (int i = 0; i < capacity; i++)
            q.add(i);
        for (int i = 0; i < capacity; i++) {
            Iterator it = q.iterator();
            its.add(it);
            for (int j = 0; j < i; j++)
                assertEquals(j, it.next());
        }
        assertEquals(attachedIterators(q), its);
        for (int i = capacity - 1; i >= 0; i--) {
            Iterator it = its.get(i);
            assertEquals(i, it.next()); // last element
            assertTrue(!isDetached(it));
            assertTrue(!it.hasNext()); // first hasNext failure
            assertTrue(isDetached(it));
            int size = q.size();
            assertTrue(q.contains(i));
            switch (rnd.nextInt(3)) {
            case 0:
                it.remove();
                assertTrue(!q.contains(i));
                assertEquals(q.size(), size - 1);
                break;
            case 1:
                // replace i with impostor
                if (q.remainingCapacity() == 0) {
                    assertTrue(q.remove(i));
                    assertTrue(q.add(-1));
                } else {
                    assertTrue(q.add(-1));
                    assertTrue(q.remove(i));
                }
                it.remove(); // should have no effect
                assertEquals(size, q.size());
                assertTrue(q.contains(-1));
                assertTrue(q.remove(-1));
                break;
            case 2:
                // replace i with true impostor
                if (i != 0) {
                    assertTrue(q.remove(i));
                    assertTrue(q.add(i));
                }
                it.remove();
                assertTrue(!q.contains(i));
                assertEquals(q.size(), size - 1);
                break;
            default: throw new AssertionError();
            }
            assertRemoveThrowsISE(it);
            assertTrue(isDetached(it));
            assertTrue(!trackedIterators(q).contains(it));
        }
        assertTrue(q.isEmpty());
        assertNull(itrs(q));
        for (Iterator it : its)
            assertIteratorExhausted(it);
    }

    /**
     * Checks dequeues bypassing iterators' current positions.
     */
    public void dequeuesBypassingIteratorCurrentPositions() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        Queue<Iterator> its0 = new ArrayDeque<>();
        Queue<Iterator> itsMid = new ArrayDeque<>();
        List<Iterator> its = new ArrayList<>();
        for (int i = 0; i < capacity; i++)
            q.add(i);
        for (int i = 0; i < 2 * capacity + 1; i++) {
            Iterator it = q.iterator();
            its.add(it);
            its0.add(it);
        }
        for (int i = 0; i < 2 * capacity + 1; i++) {
            Iterator it = q.iterator();
            for (int j = 0; j < capacity/2; j++)
                assertEquals(j, it.next());
            its.add(it);
            itsMid.add(it);
        }
        for (int i = capacity; i < 3 * capacity; i++) {
            Iterator it;

            it = its0.remove();
            assertRemoveThrowsISE(it);
            if (rnd.nextBoolean()) assertTrue(it.hasNext());
            assertEquals(0, it.next());
            int victim = i - capacity;
            for (int j = victim + (victim == 0 ? 1 : 0); j < i; j++) {
                if (rnd.nextBoolean()) assertTrue(it.hasNext());
                assertEquals(j, it.next());
            }
            assertIteratorExhausted(it);

            it = itsMid.remove();
            if (victim >= capacity/2)
                assertRemoveHasNoEffect(it, q);
            assertEquals(capacity/2, it.next());
            if (victim > capacity/2)
                assertRemoveHasNoEffect(it, q);
            for (int j = Math.max(victim, capacity/2 + 1); j < i; j++) {
                if (rnd.nextBoolean()) assertTrue(it.hasNext());
                assertEquals(j, it.next());
            }
            assertIteratorExhausted(it);

            if (rnd.nextBoolean()) {
                assertEquals(victim, q.remove());
            } else {
                ArrayList list = new ArrayList(1);
                q.drainTo(list, 1);
                assertEquals(list.size(), 1);
                assertEquals(victim, list.get(0));
            }
            assertTrue(q.add(i));
        }
        // takeIndex has wrapped twice.
        Iterator it0 = its0.remove();
        Iterator itMid = itsMid.remove();
        assertTrue(isDetached(it0));
        assertTrue(isDetached(itMid));
        if (rnd.nextBoolean()) assertTrue(it0.hasNext());
        if (rnd.nextBoolean()) assertTrue(itMid.hasNext());
        assertRemoveThrowsISE(it0);
        assertRemoveHasNoEffect(itMid, q);
        if (rnd.nextBoolean()) assertEquals(0, it0.next());
        if (rnd.nextBoolean()) assertEquals(capacity/2, itMid.next());
        assertTrue(isDetached(it0));
        assertTrue(isDetached(itMid));
        assertEquals(capacity, q.size());
        assertEquals(0, q.remainingCapacity());
    }

    /**
     * Checks collective sanity of iteration, toArray() and toString().
     */
    public void collectiveSanity() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(10, 20);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        for (int i = 0; i < capacity; i++) {
            checkIterationSanity(q);
            assertEquals(capacity, q.size() + q.remainingCapacity());
            q.add(i);
        }
        for (int i = 0; i < (capacity + (capacity >> 1)); i++) {
            checkIterationSanity(q);
            assertEquals(capacity, q.size() + q.remainingCapacity());
            assertEquals(i, q.peek());
            assertEquals(i, q.poll());
            checkIterationSanity(q);
            assertEquals(capacity, q.size() + q.remainingCapacity());
            q.add(capacity + i);
        }
        for (int i = 0; i < capacity; i++) {
            checkIterationSanity(q);
            assertEquals(capacity, q.size() + q.remainingCapacity());
            int expected = i + capacity + (capacity >> 1);
            assertEquals(expected, q.peek());
            assertEquals(expected, q.poll());
        }
        checkIterationSanity(q);
    }

    public void iteratorsDetachedWhenExhaustedAndLastRetRemoved() {
        boolean fair = rnd.nextBoolean();
        int capacity = rnd.nextInt(2, 10);
        ArrayBlockingQueue q = new ArrayBlockingQueue(capacity, fair);
        randomizePutIndex(q);
        int size = rnd.nextInt(1, capacity + 1);
        for (int i = 0; i < size; i++) q.add(i);
        Iterator it = q.iterator();
        for (int i = 0; i < size - 1; i++) assertEquals(i, it.next());
        assertEquals(trackedIterators(q), Collections.singletonList(it));
        assertFalse(isDetached(it));
        switch (rnd.nextInt(2)) {
        case 0: assertTrue(q.remove(size - 1)); break;
        case 1: assertTrue(q.removeIf(e -> e.equals(size - 1))); break;
        default: throw new AssertionError();
        }
        assertEquals(size - 1, it.next()); // should trigger detach
        assertNull(itrs(q));
        assertTrue(isDetached(it));
        assertRemoveHasNoEffect(it, q);
    }
}