/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.util.concurrent;

import com.google.common.base.Joiner;
import com.google.common.util.concurrent.CycleDetectingLockFactory.Policies;
import com.google.common.util.concurrent.CycleDetectingLockFactory.Policy;
import com.google.common.util.concurrent.CycleDetectingLockFactory.PotentialDeadlockException;

import junit.framework.TestCase;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Unittests for {@link CycleDetectingLockFactory}.
 *
 * @author Darick Tong
 */
public class CycleDetectingLockFactoryTest extends TestCase {

  private ReentrantLock lockA;
  private ReentrantLock lockB;
  private ReentrantLock lockC;
  private ReentrantReadWriteLock.ReadLock readLockA;
  private ReentrantReadWriteLock.ReadLock readLockB;
  private ReentrantReadWriteLock.ReadLock readLockC;
  private ReentrantReadWriteLock.WriteLock writeLockA;
  private ReentrantReadWriteLock.WriteLock writeLockB;
  private ReentrantReadWriteLock.WriteLock writeLockC;
  private ReentrantLock lock1;
  private ReentrantLock lock2;
  private ReentrantLock lock3;
  private ReentrantLock lock01;
  private ReentrantLock lock02;
  private ReentrantLock lock03;

  @Override
  protected void setUp() throws Exception {
    super.setUp();
    CycleDetectingLockFactory factory =
        CycleDetectingLockFactory.newInstance(Policies.THROW);
    lockA = factory.newReentrantLock("LockA");
    lockB = factory.newReentrantLock("LockB");
    lockC = factory.newReentrantLock("LockC");
    ReentrantReadWriteLock readWriteLockA =
        factory.newReentrantReadWriteLock("ReadWriteA");
    ReentrantReadWriteLock readWriteLockB =
        factory.newReentrantReadWriteLock("ReadWriteB");
    ReentrantReadWriteLock readWriteLockC =
        factory.newReentrantReadWriteLock("ReadWriteC");
    readLockA = readWriteLockA.readLock();
    readLockB = readWriteLockB.readLock();
    readLockC = readWriteLockC.readLock();
    writeLockA = readWriteLockA.writeLock();
    writeLockB = readWriteLockB.writeLock();
    writeLockC = readWriteLockC.writeLock();

    CycleDetectingLockFactory.WithExplicitOrdering<MyOrder> factory2 =
        newInstanceWithExplicitOrdering(MyOrder.class, Policies.THROW);
    lock1 = factory2.newReentrantLock(MyOrder.FIRST);
    lock2 = factory2.newReentrantLock(MyOrder.SECOND);
    lock3 = factory2.newReentrantLock(MyOrder.THIRD);

    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory3 =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    lock01 = factory3.newReentrantLock(OtherOrder.FIRST);
    lock02 = factory3.newReentrantLock(OtherOrder.SECOND);
    lock03 = factory3.newReentrantLock(OtherOrder.THIRD);
  }

  // In the unittest, create each ordered factory with its own set of lock
  // graph nodes (as opposed to using the static per-Enum map) to avoid
  // conflicts across different test runs.
  private <E extends Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E>
      newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) {
    return new CycleDetectingLockFactory.WithExplicitOrdering<E>(
        policy, CycleDetectingLockFactory.createNodes(enumClass));
  }

  public void testDeadlock_twoLocks() {
    // Establish an acquisition order of lockA -> lockB.
    lockA.lock();
    lockB.lock();
    lockA.unlock();
    lockB.unlock();

    // The opposite order should fail (Policies.THROW).
    PotentialDeadlockException firstException = null;
    lockB.lock();
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> LockA", "LockA -> LockB");
      firstException = expected;
    }

    // Second time should also fail, with a cached causal chain.
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> LockA", "LockA -> LockB");
      // The causal chain should be cached.
      assertSame(firstException.getCause(), expected.getCause());
    }

    // lockA should work after lockB is released.
    lockB.unlock();
    lockA.lock();
  }

  // Tests transitive deadlock detection.
  public void testDeadlock_threeLocks() {
    // Establish an ordering from lockA -> lockB.
    lockA.lock();
    lockB.lock();
    lockB.unlock();
    lockA.unlock();

    // Establish an ordering from lockB -> lockC.
    lockB.lock();
    lockC.lock();
    lockB.unlock();

    // lockC -> lockA should fail.
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockC -> LockA", "LockB -> LockC", "LockA -> LockB");
    }
  }

  public void testReentrancy_noDeadlock() {
    lockA.lock();
    lockB.lock();
    lockA.lock();  // Should not assert on lockB -> reentrant(lockA)
  }

  public void testExplicitOrdering_noViolations() {
    lock1.lock();
    lock3.lock();
    lock3.unlock();
    lock2.lock();
    lock3.lock();
  }

  public void testExplicitOrdering_violations() {
    lock3.lock();
    try {
      lock2.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.THIRD -> MyOrder.SECOND");
    }

    try {
      lock1.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.THIRD -> MyOrder.FIRST");
    }

    lock3.unlock();
    lock2.lock();

    try {
      lock1.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "MyOrder.SECOND -> MyOrder.FIRST");
    }
  }

  public void testDifferentOrderings_noViolations() {
    lock3.lock();   // MyOrder, ordinal() == 3
    lock01.lock();  // OtherOrder, ordinal() == 1
  }

  public void testExplicitOrderings_generalCycleDetection() {
    lock3.lock();   // MyOrder, ordinal() == 3
    lock01.lock();  // OtherOrder, ordinal() == 1

    lock3.unlock();
    try {
      lock3.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "OtherOrder.FIRST -> MyOrder.THIRD",
          "MyOrder.THIRD -> OtherOrder.FIRST");
    }

    lockA.lock();
    lock01.unlock();
    lockB.lock();
    lockA.unlock();

    try {
      lock01.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "LockB -> OtherOrder.FIRST",
          "LockA -> LockB",
          "OtherOrder.FIRST -> LockA");
    }
  }

  public void testExplicitOrdering_cycleWithUnorderedLock() {
    Lock myLock = CycleDetectingLockFactory.newInstance(Policies.THROW)
        .newReentrantLock("MyLock");
    lock03.lock();
    myLock.lock();
    lock03.unlock();

    try {
      lock01.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "MyLock -> OtherOrder.FIRST",
          "OtherOrder.THIRD -> MyLock",
          "OtherOrder.FIRST -> OtherOrder.THIRD");
    }
  }

  public void testExplicitOrdering_reentrantAcquisition() {
    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    Lock lockA = factory.newReentrantReadWriteLock(OtherOrder.FIRST).readLock();
    Lock lockB = factory.newReentrantLock(OtherOrder.SECOND);

    lockA.lock();
    lockA.lock();
    lockB.lock();
    lockB.lock();
    lockA.unlock();
    lockA.unlock();
    lockB.unlock();
    lockB.unlock();
  }

  public void testExplicitOrdering_acquiringMultipleLocksWithSameRank() {
    CycleDetectingLockFactory.WithExplicitOrdering<OtherOrder> factory =
        newInstanceWithExplicitOrdering(OtherOrder.class, Policies.THROW);
    Lock lockA = factory.newReentrantLock(OtherOrder.FIRST);
    Lock lockB = factory.newReentrantReadWriteLock(OtherOrder.FIRST).readLock();

    lockA.lock();
    try {
      lockB.lock();
      fail("Expected IllegalStateException");
    } catch (IllegalStateException expected) {
    }

    lockA.unlock();
    lockB.lock();
  }

  public void testReadLock_deadlock() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB.
    lockB.lock();
    lockB.unlock();
    readLockA.unlock();

    lockB.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadLock_transitive() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB.
    lockB.lock();
    lockB.unlock();
    readLockA.unlock();

    // Establish an ordering from lockB -> readLockC.
    lockB.lock();
    readLockC.lock();
    lockB.unlock();
    readLockC.unlock();

    // readLockC -> readLockA
    readLockC.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "ReadWriteC -> ReadWriteA",
          "LockB -> ReadWriteC",
          "ReadWriteA -> LockB");
    }
  }

  public void testWriteLock_threeLockDeadLock() {
    // Establish an ordering from writeLockA -> writeLockB.
    writeLockA.lock();
    writeLockB.lock();
    writeLockB.unlock();
    writeLockA.unlock();

    // Establish an ordering from writeLockB -> writeLockC.
    writeLockB.lock();
    writeLockC.lock();
    writeLockB.unlock();

    // writeLockC -> writeLockA should fail.
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "ReadWriteC -> ReadWriteA",
          "ReadWriteB -> ReadWriteC",
          "ReadWriteA -> ReadWriteB");
    }
  }

  public void testWriteToReadLockDowngrading() {
    writeLockA.lock();  // writeLockA downgrades to readLockA
    readLockA.lock();
    writeLockA.unlock();

    lockB.lock();  // readLockA -> lockB
    readLockA.unlock();

    // lockB -> writeLockA should fail
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock() {
    writeLockA.lock();  // Establish an ordering from writeLockA -> lockB
    lockB.lock();
    writeLockA.unlock();
    lockB.unlock();

    // lockB -> readLockA should fail.
    lockB.lock();
    try {
      readLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "LockB -> ReadWriteA", "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock_transitive() {
    readLockA.lock();  // Establish an ordering from readLockA -> lockB
    lockB.lock();
    readLockA.unlock();
    lockB.unlock();

    // Establish an ordering from lockB -> lockC
    lockB.lock();
    lockC.lock();
    lockB.unlock();
    lockC.unlock();

    // lockC -> writeLockA should fail.
    lockC.lock();
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected,
          "LockC -> ReadWriteA",
          "LockB -> LockC",
          "ReadWriteA -> LockB");
    }
  }

  public void testReadWriteLockDeadlock_treatedEquivalently() {
    readLockA.lock();  // readLockA -> writeLockB
    writeLockB.lock();
    readLockA.unlock();
    writeLockB.unlock();

    // readLockB -> writeLockA should fail.
    readLockB.lock();
    try {
      writeLockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(
          expected, "ReadWriteB -> ReadWriteA", "ReadWriteA -> ReadWriteB");
    }
  }

  public void testDifferentLockFactories() {
    CycleDetectingLockFactory otherFactory =
        CycleDetectingLockFactory.newInstance(Policies.WARN);
    ReentrantLock lockD = otherFactory.newReentrantLock("LockD");

    // lockA -> lockD
    lockA.lock();
    lockD.lock();
    lockA.unlock();
    lockD.unlock();

    // lockD -> lockA should fail even though lockD is from a different factory.
    lockD.lock();
    try {
      lockA.lock();
      fail("Expected PotentialDeadlockException");
    } catch (PotentialDeadlockException expected) {
      checkMessage(expected, "LockD -> LockA", "LockA -> LockD");
    }
  }

  public void testDifferentLockFactories_policyExecution() {
    CycleDetectingLockFactory otherFactory =
        CycleDetectingLockFactory.newInstance(Policies.WARN);
    ReentrantLock lockD = otherFactory.newReentrantLock("LockD");

    // lockD -> lockA
    lockD.lock();
    lockA.lock();
    lockA.unlock();
    lockD.unlock();

    // lockA -> lockD should warn but otherwise succeed because lockD was
    // created by a factory with the WARN policy.
    lockA.lock();
    lockD.lock();
  }

  public void testReentrantLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(lockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(lockA.tryLock());

    thread.releaseLockAndFinish();
    assertTrue(lockA.tryLock());
  }

  public void testReentrantWriteLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(writeLockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(writeLockA.tryLock());
    assertFalse(readLockA.tryLock());

    thread.releaseLockAndFinish();
    assertTrue(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
  }

  public void testReentrantReadLock_tryLock() throws Exception {
    LockingThread thread = new LockingThread(readLockA);
    thread.start();

    thread.waitUntilHoldingLock();
    assertFalse(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
    readLockA.unlock();

    thread.releaseLockAndFinish();
    assertTrue(writeLockA.tryLock());
    assertTrue(readLockA.tryLock());
  }

  private static class LockingThread extends Thread {
    final CountDownLatch locked = new CountDownLatch(1);
    final CountDownLatch finishLatch = new CountDownLatch(1);
    final Lock lock;

    LockingThread(Lock lock) {
      this.lock = lock;
    }

    @Override
    public void run() {
      lock.lock();
      try {
        locked.countDown();
        finishLatch.await(1, TimeUnit.MINUTES);
      } catch (InterruptedException e) {
        fail(e.toString());
      } finally {
        lock.unlock();
      }
    }

    void waitUntilHoldingLock() throws InterruptedException {
      locked.await(1, TimeUnit.MINUTES);
    }

    void releaseLockAndFinish() throws InterruptedException {
      finishLatch.countDown();
      this.join(10000);
      assertFalse(this.isAlive());
    }
  }

  public void testReentrantReadWriteLock_implDoesNotExposeShadowedLocks() {
    assertEquals(
        "Unexpected number of public methods in ReentrantReadWriteLock. " +
        "The correctness of CycleDetectingReentrantReadWriteLock depends on " +
        "the fact that the shadowed ReadLock and WriteLock are never used or " +
        "exposed by the superclass implementation. If the implementation has " +
        "changed, the code must be re-inspected to ensure that the " +
        "assumption is still valid.",
        24, ReentrantReadWriteLock.class.getMethods().length);
  }

  private enum MyOrder {
    FIRST, SECOND, THIRD;
  }

  private enum OtherOrder {
    FIRST, SECOND, THIRD;
  }

  // Given a sequence of lock acquisition descriptions
  // (e.g. "LockA -> LockB", "LockB -> LockC", ...)
  // Checks that the exception.getMessage() matches a regex of the form:
  // "LockA -> LockB \b.*\b LockB -> LockC \b.*\b LockC -> LockA"
  private void checkMessage(
      IllegalStateException exception, String... expectedLockCycle) {
    String regex = Joiner.on("\\b.*\\b").join(expectedLockCycle);
    assertContainsRegex(regex, exception.getMessage());
  }

  // TODO(cpovirk): consider adding support for regex to Truth
  private static void assertContainsRegex(String expectedRegex, String actual) {
    Pattern pattern = Pattern.compile(expectedRegex);
    Matcher matcher = pattern.matcher(actual);
    if (!matcher.find()) {
      String actualDesc = (actual == null) ? "null" : ('<' + actual + '>');
      fail("expected to contain regex:<" + expectedRegex + "> but was:"
          + actualDesc);
    }
  }
}