android/guava-tests/test/com/google/common/util/concurrent/CycleDetectingLockFactoryTest.java - platform/external/guava - Git at Google

 /*
  * 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 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;
 import junit.framework.TestCase;

 /**
  * 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);
     }
   }
 }
	/*
	* 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 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;
	import junit.framework.TestCase;

	/**
	* 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);
	}
	}
	}