/*

 * 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 Doug Lea 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/

 * Other contributors include Andrew Wright, Jeffrey Hayes,

 * Pat Fisher, Mike Judd.

 */

import static java.util.concurrent.TimeUnit.MILLISECONDS;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.HashSet;

import java.util.concurrent.CountDownLatch;

import java.util.concurrent.CyclicBarrier;

import java.util.concurrent.ThreadLocalRandom;

import java.util.concurrent.locks.Condition;

import java.util.concurrent.locks.ReentrantLock;

import junit.framework.Test;

import junit.framework.TestSuite;

@SuppressWarnings("WaitNotInLoop") // we implement spurious-wakeup freedom

public class ReentrantLockTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(ReentrantLockTest.class);

    }

    /**

     * A checked runnable calling lockInterruptibly

     */

    class InterruptibleLockRunnable extends CheckedRunnable {

        final ReentrantLock lock;

        InterruptibleLockRunnable(ReentrantLock lock) { this.lock = lock; }

        public void realRun() throws InterruptedException {

            lock.lockInterruptibly();

        }

    }

    /**

     * A checked runnable calling lockInterruptibly that expects to be

     * interrupted

     */

    class InterruptedLockRunnable extends CheckedInterruptedRunnable {

        final ReentrantLock lock;

        InterruptedLockRunnable(ReentrantLock lock) { this.lock = lock; }

        public void realRun() throws InterruptedException {

            lock.lockInterruptibly();

        }

    }

    /**

     * Subclass to expose protected methods

     */

    static class PublicReentrantLock extends ReentrantLock {

        PublicReentrantLock() { super(); }

        PublicReentrantLock(boolean fair) { super(fair); }

        public Thread getOwner() {

            return super.getOwner();

        }

        public Collection<Thread> getQueuedThreads() {

            return super.getQueuedThreads();

        }

        public Collection<Thread> getWaitingThreads(Condition c) {

            return super.getWaitingThreads(c);

        }

    }

    /**

     * Releases write lock, checking that it had a hold count of 1.

     */

    void releaseLock(PublicReentrantLock lock) {

        assertLockedByMoi(lock);

        lock.unlock();

        assertFalse(lock.isHeldByCurrentThread());

        assertNotLocked(lock);

    }

    /**

     * Spin-waits until lock.hasQueuedThread(t) becomes true.

     */

    void waitForQueuedThread(PublicReentrantLock lock, Thread t) {

        long startTime = System.nanoTime();

        while (!lock.hasQueuedThread(t)) {

            if (millisElapsedSince(startTime) > LONG_DELAY_MS)

            Thread.yield();

        }

        assertTrue(t.isAlive());

        assertNotSame(t, lock.getOwner());

    }

    /**

     * Checks that lock is not locked.

     */

    void assertNotLocked(PublicReentrantLock lock) {

        assertFalse(lock.isLocked());

        assertFalse(lock.isHeldByCurrentThread());

        assertNull(lock.getOwner());

        assertEquals(0, lock.getHoldCount());

    }

    /**

     * Checks that lock is locked by the given thread.

     */

    void assertLockedBy(PublicReentrantLock lock, Thread t) {

        assertTrue(lock.isLocked());

        assertSame(t, lock.getOwner());

        assertEquals(t == Thread.currentThread(),

                     lock.isHeldByCurrentThread());

        assertEquals(t == Thread.currentThread(),

                     lock.getHoldCount() > 0);

    }

    /**

     * Checks that lock is locked by the current thread.

     */

    void assertLockedByMoi(PublicReentrantLock lock) {

        assertLockedBy(lock, Thread.currentThread());

    }

    /**

     * Checks that condition c has no waiters.

     */

    void assertHasNoWaiters(PublicReentrantLock lock, Condition c) {

        assertHasWaiters(lock, c, new Thread[] {});

    }

    /**

     * Checks that condition c has exactly the given waiter threads.

     */

    void assertHasWaiters(PublicReentrantLock lock, Condition c,

                          Thread... threads) {

        lock.lock();

        assertEquals(threads.length > 0, lock.hasWaiters(c));

        assertEquals(threads.length, lock.getWaitQueueLength(c));

        assertEquals(threads.length == 0, lock.getWaitingThreads(c).isEmpty());

        assertEquals(threads.length, lock.getWaitingThreads(c).size());

        assertEquals(new HashSet<Thread>(lock.getWaitingThreads(c)),

                     new HashSet<Thread>(Arrays.asList(threads)));

        lock.unlock();

    }

    enum AwaitMethod { await, awaitTimed, awaitNanos, awaitUntil }

    static AwaitMethod randomAwaitMethod() {

        AwaitMethod[] awaitMethods = AwaitMethod.values();

        return awaitMethods[ThreadLocalRandom.current().nextInt(awaitMethods.length)];

    }

    /**

     * Awaits condition "indefinitely" using the specified AwaitMethod.

     */

    void await(Condition c, AwaitMethod awaitMethod)

            throws InterruptedException {

        long timeoutMillis = 2 * LONG_DELAY_MS;

        switch (awaitMethod) {

        case await:

            c.await();

            break;

        case awaitTimed:

            assertTrue(c.await(timeoutMillis, MILLISECONDS));

            break;

        case awaitNanos:

            long timeoutNanos = MILLISECONDS.toNanos(timeoutMillis);

            long nanosRemaining = c.awaitNanos(timeoutNanos);

            assertTrue(nanosRemaining > timeoutNanos / 2);

            assertTrue(nanosRemaining <= timeoutNanos);

            break;

        case awaitUntil:

            assertTrue(c.awaitUntil(delayedDate(timeoutMillis)));

            break;

        default:

            throw new AssertionError();

        }

    }

    /**

     * Constructor sets given fairness, and is in unlocked state

     */

    public void testConstructor() {

        PublicReentrantLock lock;

        lock = new PublicReentrantLock();

        assertFalse(lock.isFair());

        assertNotLocked(lock);

        lock = new PublicReentrantLock(true);

        assertTrue(lock.isFair());

        assertNotLocked(lock);

        lock = new PublicReentrantLock(false);

        assertFalse(lock.isFair());

        assertNotLocked(lock);

    }

    /**

     * locking an unlocked lock succeeds

     */

    public void testLock()      { testLock(false); }

    public void testLock_fair() { testLock(true); }

    public void testLock(boolean fair) {

        PublicReentrantLock lock = new PublicReentrantLock(fair);

        lock.lock();

        assertLockedByMoi(lock);

        releaseLock(lock);

    }

    /**

     * Unlocking an unlocked lock throws IllegalMonitorStateException

     */

    public void testUnlock_IMSE()      { testUnlock_IMSE(false); }

    public void testUnlock_IMSE_fair() { testUnlock_IMSE(true); }

    public void testUnlock_IMSE(boolean fair) {

        final ReentrantLock lock = new ReentrantLock(fair);

        try {

            lock.unlock();

            shouldThrow();

        } catch (IllegalMonitorStateException success) {}

    }

    /**

     * tryLock on an unlocked lock succeeds

     */

    public void testTryLock()      { testTryLock(false); }

    public void testTryLock_fair() { testTryLock(true); }

    public void testTryLock(boolean fair) {

        PublicReentrantLock lock = new PublicReentrantLock(fair);

        assertTrue(lock.tryLock());

        assertLockedByMoi(lock);

        assertTrue(lock.tryLock());

        assertLockedByMoi(lock);

        lock.unlock();

        releaseLock(lock);

    }

    /**

     * hasQueuedThreads reports whether there are waiting threads

     */

    public void testHasQueuedThreads()      { testHasQueuedThreads(false); }

    public void testHasQueuedThreads_fair() { testHasQueuedThreads(true); }

    public void testHasQueuedThreads(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        Thread t1 = new Thread(new InterruptedLockRunnable(lock));

        Thread t2 = new Thread(new InterruptibleLockRunnable(lock));

        assertFalse(lock.hasQueuedThreads());

        lock.lock();

        assertFalse(lock.hasQueuedThreads());

        t1.start();

        waitForQueuedThread(lock, t1);

        assertTrue(lock.hasQueuedThreads());

        t2.start();

        waitForQueuedThread(lock, t2);

        assertTrue(lock.hasQueuedThreads());

        t1.interrupt();

        awaitTermination(t1);

        assertTrue(lock.hasQueuedThreads());

        lock.unlock();

        awaitTermination(t2);

        assertFalse(lock.hasQueuedThreads());

    }

    /**

     * getQueueLength reports number of waiting threads

     */

    public void testGetQueueLength()      { testGetQueueLength(false); }

    public void testGetQueueLength_fair() { testGetQueueLength(true); }

    public void testGetQueueLength(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        Thread t1 = new Thread(new InterruptedLockRunnable(lock));

        Thread t2 = new Thread(new InterruptibleLockRunnable(lock));

        assertEquals(0, lock.getQueueLength());

        lock.lock();

        t1.start();

        waitForQueuedThread(lock, t1);

        assertEquals(1, lock.getQueueLength());

        t2.start();

        waitForQueuedThread(lock, t2);

        assertEquals(2, lock.getQueueLength());

        t1.interrupt();

        awaitTermination(t1);

        assertEquals(1, lock.getQueueLength());

        lock.unlock();

        awaitTermination(t2);

        assertEquals(0, lock.getQueueLength());

    }

    /**

     * hasQueuedThread(null) throws NPE

     */

    public void testHasQueuedThreadNPE()      { testHasQueuedThreadNPE(false); }

    public void testHasQueuedThreadNPE_fair() { testHasQueuedThreadNPE(true); }

    public void testHasQueuedThreadNPE(boolean fair) {

        final ReentrantLock lock = new ReentrantLock(fair);

        try {

            lock.hasQueuedThread(null);

            shouldThrow();

        } catch (NullPointerException success) {}

    }

    /**

     * hasQueuedThread reports whether a thread is queued

     */

    public void testHasQueuedThread()      { testHasQueuedThread(false); }

    public void testHasQueuedThread_fair() { testHasQueuedThread(true); }

    public void testHasQueuedThread(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        Thread t1 = new Thread(new InterruptedLockRunnable(lock));

        Thread t2 = new Thread(new InterruptibleLockRunnable(lock));

        assertFalse(lock.hasQueuedThread(t1));

        assertFalse(lock.hasQueuedThread(t2));

        lock.lock();

        t1.start();

        waitForQueuedThread(lock, t1);

        assertTrue(lock.hasQueuedThread(t1));

        assertFalse(lock.hasQueuedThread(t2));

        t2.start();

        waitForQueuedThread(lock, t2);

        assertTrue(lock.hasQueuedThread(t1));

        assertTrue(lock.hasQueuedThread(t2));

        t1.interrupt();

        awaitTermination(t1);

        assertFalse(lock.hasQueuedThread(t1));

        assertTrue(lock.hasQueuedThread(t2));

        lock.unlock();

        awaitTermination(t2);

        assertFalse(lock.hasQueuedThread(t1));

        assertFalse(lock.hasQueuedThread(t2));

    }

    /**

     * getQueuedThreads includes waiting threads

     */

    public void testGetQueuedThreads()      { testGetQueuedThreads(false); }

    public void testGetQueuedThreads_fair() { testGetQueuedThreads(true); }

    public void testGetQueuedThreads(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        Thread t1 = new Thread(new InterruptedLockRunnable(lock));

        Thread t2 = new Thread(new InterruptibleLockRunnable(lock));

        assertTrue(lock.getQueuedThreads().isEmpty());

        lock.lock();

        assertTrue(lock.getQueuedThreads().isEmpty());

        t1.start();

        waitForQueuedThread(lock, t1);

        assertEquals(1, lock.getQueuedThreads().size());

        assertTrue(lock.getQueuedThreads().contains(t1));

        t2.start();

        waitForQueuedThread(lock, t2);

        assertEquals(2, lock.getQueuedThreads().size());

        assertTrue(lock.getQueuedThreads().contains(t1));

        assertTrue(lock.getQueuedThreads().contains(t2));

        t1.interrupt();

        awaitTermination(t1);

        assertFalse(lock.getQueuedThreads().contains(t1));

        assertTrue(lock.getQueuedThreads().contains(t2));

        assertEquals(1, lock.getQueuedThreads().size());

        lock.unlock();

        awaitTermination(t2);

        assertTrue(lock.getQueuedThreads().isEmpty());

    }

    /**

     * timed tryLock is interruptible

     */

    public void testTryLock_Interruptible()      { testTryLock_Interruptible(false); }

    public void testTryLock_Interruptible_fair() { testTryLock_Interruptible(true); }

    public void testTryLock_Interruptible(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        lock.lock();

        Thread t = newStartedThread(new CheckedInterruptedRunnable() {

            public void realRun() throws InterruptedException {

                lock.tryLock(2 * LONG_DELAY_MS, MILLISECONDS);

            }});

        waitForQueuedThread(lock, t);

        t.interrupt();

        awaitTermination(t);

        releaseLock(lock);

    }

    /**

     * tryLock on a locked lock fails

     */

    public void testTryLockWhenLocked()      { testTryLockWhenLocked(false); }

    public void testTryLockWhenLocked_fair() { testTryLockWhenLocked(true); }

    public void testTryLockWhenLocked(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        lock.lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() {

                assertFalse(lock.tryLock());

            }});

        awaitTermination(t);

        releaseLock(lock);

    }

    /**

     * Timed tryLock on a locked lock times out

     */

    public void testTryLock_Timeout()      { testTryLock_Timeout(false); }

    public void testTryLock_Timeout_fair() { testTryLock_Timeout(true); }

    public void testTryLock_Timeout(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        final long timeoutMillis = timeoutMillis();

        lock.lock();

        Thread t = newStartedThread(new CheckedRunnable() {

            public void realRun() throws InterruptedException {

                long startTime = System.nanoTime();

                assertFalse(lock.tryLock(timeoutMillis, MILLISECONDS));

                assertTrue(millisElapsedSince(startTime) >= timeoutMillis);

            }});

        awaitTermination(t);

        releaseLock(lock);

    }

    /**

     * getHoldCount returns number of recursive holds

     */

    public void testGetHoldCount()      { testGetHoldCount(false); }

    public void testGetHoldCount_fair() { testGetHoldCount(true); }

    public void testGetHoldCount(boolean fair) {

        final ReentrantLock lock = new ReentrantLock(fair);

        for (int i = 1; i <= SIZE; i++) {

            lock.lock();

            assertEquals(i, lock.getHoldCount());

        }

        for (int i = SIZE; i > 0; i--) {

            lock.unlock();

            assertEquals(i - 1, lock.getHoldCount());

        }

    }

    /**

     * isLocked is true when locked and false when not

     */

    public void testIsLocked()      { testIsLocked(false); }

    public void testIsLocked_fair() { testIsLocked(true); }

    public void testIsLocked(boolean fair) {

        final ReentrantLock lock = new ReentrantLock(fair);

        try {

            assertFalse(lock.isLocked());

            lock.lock();

            assertTrue(lock.isLocked());

            lock.lock();

            assertTrue(lock.isLocked());

            lock.unlock();

            assertTrue(lock.isLocked());

            lock.unlock();

            assertFalse(lock.isLocked());

            final CyclicBarrier barrier = new CyclicBarrier(2);

            Thread t = newStartedThread(new CheckedRunnable() {

                    public void realRun() throws Exception {

                        lock.lock();

                        assertTrue(lock.isLocked());

                        barrier.await();

                        barrier.await();

                        lock.unlock();

                    }});

            barrier.await();

            assertTrue(lock.isLocked());

            barrier.await();

            awaitTermination(t);

            assertFalse(lock.isLocked());

        } catch (Exception fail) { threadUnexpectedException(fail); }

    }

    /**

     * lockInterruptibly succeeds when unlocked, else is interruptible

     */

    public void testLockInterruptibly()      { testLockInterruptibly(false); }

    public void testLockInterruptibly_fair() { testLockInterruptibly(true); }

    public void testLockInterruptibly(boolean fair) {

        final PublicReentrantLock lock = new PublicReentrantLock(fair);

        try {

            lock.lockInterruptibly();

        } catch (InterruptedException fail) { threadUnexpectedException(fail); }

        assertLockedByMoi(lock);

        Thread t = newStartedThread(new InterruptedLockRunnable(lock));

        waitForQueuedThread(lock, t);

        t.interrupt();

        assertTrue(lock.isLocked());

        assertTrue(lock.isHeldByCurrentThread());

        awaitTermination(t);

        releaseLock(lock);

    }

    /**

     * Calling await without holding lock throws IllegalMonitorStateException

     */

    public void testAwait_IMSE()      { testAwait_IMSE(false); }

    public void testAwait_IMSE_fair() { testAwait_IMSE(true); }

    public void testAwait_IMSE(boolean fair) {