001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.util.concurrent;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.primitives.Longs;
022import com.google.errorprone.annotations.concurrent.GuardedBy;
023import com.google.j2objc.annotations.Weak;
024import java.util.concurrent.TimeUnit;
025import java.util.concurrent.locks.Condition;
026import java.util.concurrent.locks.ReentrantLock;
027import javax.annotation.CheckForNull;
028
029/**
030 * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
031 *
032 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
033 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
034 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
035 * evaluation and signaling of conditions. Signaling is entirely <a
036 * href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">implicit</a>. By
037 * eliminating explicit signaling, this class can guarantee that only one thread is awakened when a
038 * condition becomes true (no "signaling storms" due to use of {@link
039 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
040 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
041 * Condition.signal}).
042 *
043 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
044 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
045 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
046 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
047 * semantics as the built-in Java language synchronization primitives.
048 *
049 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
050 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
051 * monitor cleanly:
052 *
053 * <pre>{@code
054 * monitor.enter();
055 * try {
056 *   // do things while occupying the monitor
057 * } finally {
058 *   monitor.leave();
059 * }
060 * }</pre>
061 *
062 * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear
063 * as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that
064 * the current thread leaves the monitor cleanly:
065 *
066 * <pre>{@code
067 * if (monitor.tryEnter()) {
068 *   try {
069 *     // do things while occupying the monitor
070 *   } finally {
071 *     monitor.leave();
072 *   }
073 * } else {
074 *   // do other things since the monitor was not available
075 * }
076 * }</pre>
077 *
078 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
079 *
080 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
081 * {@link ReentrantLock}, and {@code Monitor}.
082 *
083 * <h3>{@code synchronized}</h3>
084 *
085 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
086 * is built into the language and runtime. But the programmer has to remember to avoid a couple of
087 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
088 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
089 * logical conditions being awaited.
090 *
091 * <pre>{@code
092 * public class SafeBox<V> {
093 *   private V value;
094 *
095 *   public synchronized V get() throws InterruptedException {
096 *     while (value == null) {
097 *       wait();
098 *     }
099 *     V result = value;
100 *     value = null;
101 *     notifyAll();
102 *     return result;
103 *   }
104 *
105 *   public synchronized void set(V newValue) throws InterruptedException {
106 *     while (value != null) {
107 *       wait();
108 *     }
109 *     value = newValue;
110 *     notifyAll();
111 *   }
112 * }
113 * }</pre>
114 *
115 * <h3>{@code ReentrantLock}</h3>
116 *
117 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
118 * from the need for the programmer to remember to use {@code while} instead of {@code if}. However,
119 * one advantage is that we can introduce two separate {@code Condition} objects, which allows us to
120 * use {@code signal()} instead of {@code signalAll()}, which may be a performance benefit.
121 *
122 * <pre>{@code
123 * public class SafeBox<V> {
124 *   private V value;
125 *   private final ReentrantLock lock = new ReentrantLock();
126 *   private final Condition valuePresent = lock.newCondition();
127 *   private final Condition valueAbsent = lock.newCondition();
128 *
129 *   public V get() throws InterruptedException {
130 *     lock.lock();
131 *     try {
132 *       while (value == null) {
133 *         valuePresent.await();
134 *       }
135 *       V result = value;
136 *       value = null;
137 *       valueAbsent.signal();
138 *       return result;
139 *     } finally {
140 *       lock.unlock();
141 *     }
142 *   }
143 *
144 *   public void set(V newValue) throws InterruptedException {
145 *     lock.lock();
146 *     try {
147 *       while (value != null) {
148 *         valueAbsent.await();
149 *       }
150 *       value = newValue;
151 *       valuePresent.signal();
152 *     } finally {
153 *       lock.unlock();
154 *     }
155 *   }
156 * }
157 * }</pre>
158 *
159 * <h3>{@code Monitor}</h3>
160 *
161 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
162 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
163 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
164 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
165 * remember to use {@code while} instead of {@code if}.
166 *
167 * <pre>{@code
168 * public class SafeBox<V> {
169 *   private V value;
170 *   private final Monitor monitor = new Monitor();
171 *   private final Monitor.Guard valuePresent = monitor.newGuard(() -> value != null);
172 *   private final Monitor.Guard valueAbsent = monitor.newGuard(() -> value == null);
173 *
174 *   public V get() throws InterruptedException {
175 *     monitor.enterWhen(valuePresent);
176 *     try {
177 *       V result = value;
178 *       value = null;
179 *       return result;
180 *     } finally {
181 *       monitor.leave();
182 *     }
183 *   }
184 *
185 *   public void set(V newValue) throws InterruptedException {
186 *     monitor.enterWhen(valueAbsent);
187 *     try {
188 *       value = newValue;
189 *     } finally {
190 *       monitor.leave();
191 *     }
192 *   }
193 * }
194 * }</pre>
195 *
196 * @author Justin T. Sampson
197 * @author Martin Buchholz
198 * @since 10.0
199 */
200@Beta
201@GwtIncompatible
202@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
203@ElementTypesAreNonnullByDefault
204public final class Monitor {
205  // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
206  // TODO(user): "Port" jsr166 tests for ReentrantLock.
207  //
208  // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
209  //    by making the monitor implicit, and to eliminate other sources of IMSE.
210  //    Imagine:
211  //    guard.lock();
212  //    try { /* monitor locked and guard satisfied here */ }
213  //    finally { guard.unlock(); }
214  // Here are Justin's design notes about this:
215  //
216  // This idea has come up from time to time, and I think one of my
217  // earlier versions of Monitor even did something like this. I ended
218  // up strongly favoring the current interface.
219  //
220  // I probably can't remember all the reasons (it's possible you
221  // could find them in the code review archives), but here are a few:
222  //
223  // 1. What about leaving/unlocking? Are you going to do
224  //    guard.enter() paired with monitor.leave()? That might get
225  //    confusing. It's nice for the finally block to look as close as
226  //    possible to the thing right before the try. You could have
227  //    guard.leave(), but that's a little odd as well because the
228  //    guard doesn't have anything to do with leaving. You can't
229  //    really enforce that the guard you're leaving is the same one
230  //    you entered with, and it doesn't actually matter.
231  //
232  // 2. Since you can enter the monitor without a guard at all, some
233  //    places you'll have monitor.enter()/monitor.leave() and other
234  //    places you'll have guard.enter()/guard.leave() even though
235  //    it's the same lock being acquired underneath. Always using
236  //    monitor.enterXXX()/monitor.leave() will make it really clear
237  //    which lock is held at any point in the code.
238  //
239  // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
240  //
241  // TODO(user): Implement ReentrantLock features:
242  //    - toString() method
243  //    - getOwner() method
244  //    - getQueuedThreads() method
245  //    - getWaitingThreads(Guard) method
246  //    - implement Serializable
247  //    - redo the API to be as close to identical to ReentrantLock as possible,
248  //      since, after all, this class is also a reentrant mutual exclusion lock!?
249
250  /*
251   * One of the key challenges of this class is to prevent lost signals, while trying hard to
252   * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter
253   * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the
254   * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This
255   * includes exceptional exits, so all control paths involving signalling must be protected by a
256   * finally block.
257   *
258   * Further optimizations of this algorithm become increasingly subtle. A wait that terminates
259   * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit
260   * the monitor without signalling. If it timed out without being signalled, it does not need to
261   * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been
262   * satisfied at the time of signal, and has since been modified by some other thread to be
263   * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility
264   * of signaling the next waiter.
265   *
266   * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be
267   * lost, because the signal may be sent to a condition whose sole waiter has just been
268   * interrupted.
269   *
270   * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards,
271   * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions
272   * need to be signalled because it is not known which if any of them have waiters (and hasWaiters
273   * can't be used reliably because of a check-then-act race). With our Monitor guards, we only
274   * signal the first active guard that is satisfied. But the corresponding thread may have already
275   * been interrupted and is waiting to reacquire the lock while still registered in activeGuards,
276   * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted
277   * threads take special action by participating in the signal-passing game.
278   */
279
280  /*
281   * Timeout handling is intricate, especially given our ambitious goals:
282   * - Avoid underflow and overflow of timeout values when specified timeouts are close to
283   *   Long.MIN_VALUE or Long.MAX_VALUE.
284   * - Favor responding to interrupts over timeouts.
285   * - System.nanoTime() is expensive enough that we want to call it the minimum required number of
286   *   times, typically once before invoking a blocking method. This often requires keeping track of
287   *   the first time in a method that nanoTime() has been invoked, for which the special value 0L
288   *   is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be
289   *   called.
290   * - Keep behavior of fair and non-fair instances consistent.
291   */
292
293  /**
294   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
295   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
296   * the monitor, so code should not be written to rely on how often a guard might or might not be
297   * checked.
298   *
299   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
300   * associated with, an {@link IllegalMonitorStateException} is thrown.
301   *
302   * @since 10.0
303   */
304  @Beta
305  public abstract static class Guard {
306
307    @Weak final Monitor monitor;
308    final Condition condition;
309
310    @GuardedBy("monitor.lock")
311    int waiterCount = 0;
312
313    /** The next active guard */
314    @GuardedBy("monitor.lock")
315    @CheckForNull
316    Guard next;
317
318    protected Guard(Monitor monitor) {
319      this.monitor = checkNotNull(monitor, "monitor");
320      this.condition = monitor.lock.newCondition();
321    }
322
323    /**
324     * Evaluates this guard's boolean condition. This method is always called with the associated
325     * monitor already occupied. Implementations of this method must depend only on state protected
326     * by the associated monitor, and must not modify that state.
327     */
328    public abstract boolean isSatisfied();
329  }
330
331  /** Whether this monitor is fair. */
332  private final boolean fair;
333
334  /** The lock underlying this monitor. */
335  private final ReentrantLock lock;
336
337  /**
338   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
339   * A linked list threaded through the Guard.next field.
340   */
341  @GuardedBy("lock")
342  @CheckForNull
343  private Guard activeGuards = null;
344
345  /**
346   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
347   * Monitor(false)}.
348   */
349  public Monitor() {
350    this(false);
351  }
352
353  /**
354   * Creates a monitor with the given ordering policy.
355   *
356   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
357   *     fast) one
358   */
359  public Monitor(boolean fair) {
360    this.fair = fair;
361    this.lock = new ReentrantLock(fair);
362  }
363
364  /** Enters this monitor. Blocks indefinitely. */
365  public void enter() {
366    lock.lock();
367  }
368
369  /**
370   * Enters this monitor. Blocks at most the given time.
371   *
372   * @return whether the monitor was entered
373   */
374  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
375  public boolean enter(long time, TimeUnit unit) {
376    final long timeoutNanos = toSafeNanos(time, unit);
377    final ReentrantLock lock = this.lock;
378    if (!fair && lock.tryLock()) {
379      return true;
380    }
381    boolean interrupted = Thread.interrupted();
382    try {
383      final long startTime = System.nanoTime();
384      for (long remainingNanos = timeoutNanos; ; ) {
385        try {
386          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
387        } catch (InterruptedException interrupt) {
388          interrupted = true;
389          remainingNanos = remainingNanos(startTime, timeoutNanos);
390        }
391      }
392    } finally {
393      if (interrupted) {
394        Thread.currentThread().interrupt();
395      }
396    }
397  }
398
399  /**
400   * Enters this monitor. Blocks indefinitely, but may be interrupted.
401   *
402   * @throws InterruptedException if interrupted while waiting
403   */
404  public void enterInterruptibly() throws InterruptedException {
405    lock.lockInterruptibly();
406  }
407
408  /**
409   * Enters this monitor. Blocks at most the given time, and may be interrupted.
410   *
411   * @return whether the monitor was entered
412   * @throws InterruptedException if interrupted while waiting
413   */
414  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
415  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
416    return lock.tryLock(time, unit);
417  }
418
419  /**
420   * Enters this monitor if it is possible to do so immediately. Does not block.
421   *
422   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
423   *
424   * @return whether the monitor was entered
425   */
426  public boolean tryEnter() {
427    return lock.tryLock();
428  }
429
430  /**
431   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
432   *
433   * @throws InterruptedException if interrupted while waiting
434   */
435  public void enterWhen(Guard guard) throws InterruptedException {
436    if (guard.monitor != this) {
437      throw new IllegalMonitorStateException();
438    }
439    final ReentrantLock lock = this.lock;
440    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
441    lock.lockInterruptibly();
442
443    boolean satisfied = false;
444    try {
445      if (!guard.isSatisfied()) {
446        await(guard, signalBeforeWaiting);
447      }
448      satisfied = true;
449    } finally {
450      if (!satisfied) {
451        leave();
452      }
453    }
454  }
455
456  /**
457   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
458   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
459   * interrupted.
460   *
461   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
462   * @throws InterruptedException if interrupted while waiting
463   */
464  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
465  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
466    final long timeoutNanos = toSafeNanos(time, unit);
467    if (guard.monitor != this) {
468      throw new IllegalMonitorStateException();
469    }
470    final ReentrantLock lock = this.lock;
471    boolean reentrant = lock.isHeldByCurrentThread();
472    long startTime = 0L;
473
474    locked:
475    {
476      if (!fair) {
477        // Check interrupt status to get behavior consistent with fair case.
478        if (Thread.interrupted()) {
479          throw new InterruptedException();
480        }
481        if (lock.tryLock()) {
482          break locked;
483        }
484      }
485      startTime = initNanoTime(timeoutNanos);
486      if (!lock.tryLock(time, unit)) {
487        return false;
488      }
489    }
490
491    boolean satisfied = false;
492    boolean threw = true;
493    try {
494      satisfied =
495          guard.isSatisfied()
496              || awaitNanos(
497                  guard,
498                  (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos),
499                  reentrant);
500      threw = false;
501      return satisfied;
502    } finally {
503      if (!satisfied) {
504        try {
505          // Don't need to signal if timed out, but do if interrupted
506          if (threw && !reentrant) {
507            signalNextWaiter();
508          }
509        } finally {
510          lock.unlock();
511        }
512      }
513    }
514  }
515
516  /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */
517  public void enterWhenUninterruptibly(Guard guard) {
518    if (guard.monitor != this) {
519      throw new IllegalMonitorStateException();
520    }
521    final ReentrantLock lock = this.lock;
522    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
523    lock.lock();
524
525    boolean satisfied = false;
526    try {
527      if (!guard.isSatisfied()) {
528        awaitUninterruptibly(guard, signalBeforeWaiting);
529      }
530      satisfied = true;
531    } finally {
532      if (!satisfied) {
533        leave();
534      }
535    }
536  }
537
538  /**
539   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
540   * the time to acquire the lock and the time to wait for the guard to be satisfied.
541   *
542   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
543   */
544  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
545  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
546    final long timeoutNanos = toSafeNanos(time, unit);
547    if (guard.monitor != this) {
548      throw new IllegalMonitorStateException();
549    }
550    final ReentrantLock lock = this.lock;
551    long startTime = 0L;
552    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
553    boolean interrupted = Thread.interrupted();
554    try {
555      if (fair || !lock.tryLock()) {
556        startTime = initNanoTime(timeoutNanos);
557        for (long remainingNanos = timeoutNanos; ; ) {
558          try {
559            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
560              break;
561            } else {
562              return false;
563            }
564          } catch (InterruptedException interrupt) {
565            interrupted = true;
566            remainingNanos = remainingNanos(startTime, timeoutNanos);
567          }
568        }
569      }
570
571      boolean satisfied = false;
572      try {
573        while (true) {
574          try {
575            if (guard.isSatisfied()) {
576              satisfied = true;
577            } else {
578              final long remainingNanos;
579              if (startTime == 0L) {
580                startTime = initNanoTime(timeoutNanos);
581                remainingNanos = timeoutNanos;
582              } else {
583                remainingNanos = remainingNanos(startTime, timeoutNanos);
584              }
585              satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
586            }
587            return satisfied;
588          } catch (InterruptedException interrupt) {
589            interrupted = true;
590            signalBeforeWaiting = false;
591          }
592        }
593      } finally {
594        if (!satisfied) {
595          lock.unlock(); // No need to signal if timed out
596        }
597      }
598    } finally {
599      if (interrupted) {
600        Thread.currentThread().interrupt();
601      }
602    }
603  }
604
605  /**
606   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
607   * not wait for the guard to be satisfied.
608   *
609   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
610   */
611  public boolean enterIf(Guard guard) {
612    if (guard.monitor != this) {
613      throw new IllegalMonitorStateException();
614    }
615    final ReentrantLock lock = this.lock;
616    lock.lock();
617
618    boolean satisfied = false;
619    try {
620      return satisfied = guard.isSatisfied();
621    } finally {
622      if (!satisfied) {
623        lock.unlock();
624      }
625    }
626  }
627
628  /**
629   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
630   * lock, but does not wait for the guard to be satisfied.
631   *
632   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
633   */
634  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
635  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
636    if (guard.monitor != this) {
637      throw new IllegalMonitorStateException();
638    }
639    if (!enter(time, unit)) {
640      return false;
641    }
642
643    boolean satisfied = false;
644    try {
645      return satisfied = guard.isSatisfied();
646    } finally {
647      if (!satisfied) {
648        lock.unlock();
649      }
650    }
651  }
652
653  /**
654   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
655   * not wait for the guard to be satisfied, and may be interrupted.
656   *
657   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
658   * @throws InterruptedException if interrupted while waiting
659   */
660  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
661    if (guard.monitor != this) {
662      throw new IllegalMonitorStateException();
663    }
664    final ReentrantLock lock = this.lock;
665    lock.lockInterruptibly();
666
667    boolean satisfied = false;
668    try {
669      return satisfied = guard.isSatisfied();
670    } finally {
671      if (!satisfied) {
672        lock.unlock();
673      }
674    }
675  }
676
677  /**
678   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
679   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
680   *
681   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
682   */
683  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
684  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
685      throws InterruptedException {
686    if (guard.monitor != this) {
687      throw new IllegalMonitorStateException();
688    }
689    final ReentrantLock lock = this.lock;
690    if (!lock.tryLock(time, unit)) {
691      return false;
692    }
693
694    boolean satisfied = false;
695    try {
696      return satisfied = guard.isSatisfied();
697    } finally {
698      if (!satisfied) {
699        lock.unlock();
700      }
701    }
702  }
703
704  /**
705   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
706   * block acquiring the lock and does not wait for the guard to be satisfied.
707   *
708   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
709   *
710   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
711   */
712  public boolean tryEnterIf(Guard guard) {
713    if (guard.monitor != this) {
714      throw new IllegalMonitorStateException();
715    }
716    final ReentrantLock lock = this.lock;
717    if (!lock.tryLock()) {
718      return false;
719    }
720
721    boolean satisfied = false;
722    try {
723      return satisfied = guard.isSatisfied();
724    } finally {
725      if (!satisfied) {
726        lock.unlock();
727      }
728    }
729  }
730
731  /**
732   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
733   * only by a thread currently occupying this monitor.
734   *
735   * @throws InterruptedException if interrupted while waiting
736   */
737  public void waitFor(Guard guard) throws InterruptedException {
738    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
739      throw new IllegalMonitorStateException();
740    }
741    if (!guard.isSatisfied()) {
742      await(guard, true);
743    }
744  }
745
746  /**
747   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
748   * be called only by a thread currently occupying this monitor.
749   *
750   * @return whether the guard is now satisfied
751   * @throws InterruptedException if interrupted while waiting
752   */
753  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
754  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
755    final long timeoutNanos = toSafeNanos(time, unit);
756    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
757      throw new IllegalMonitorStateException();
758    }
759    if (guard.isSatisfied()) {
760      return true;
761    }
762    if (Thread.interrupted()) {
763      throw new InterruptedException();
764    }
765    return awaitNanos(guard, timeoutNanos, true);
766  }
767
768  /**
769   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
770   * currently occupying this monitor.
771   */
772  public void waitForUninterruptibly(Guard guard) {
773    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
774      throw new IllegalMonitorStateException();
775    }
776    if (!guard.isSatisfied()) {
777      awaitUninterruptibly(guard, true);
778    }
779  }
780
781  /**
782   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
783   * thread currently occupying this monitor.
784   *
785   * @return whether the guard is now satisfied
786   */
787  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
788  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
789    final long timeoutNanos = toSafeNanos(time, unit);
790    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
791      throw new IllegalMonitorStateException();
792    }
793    if (guard.isSatisfied()) {
794      return true;
795    }
796    boolean signalBeforeWaiting = true;
797    final long startTime = initNanoTime(timeoutNanos);
798    boolean interrupted = Thread.interrupted();
799    try {
800      for (long remainingNanos = timeoutNanos; ; ) {
801        try {
802          return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
803        } catch (InterruptedException interrupt) {
804          interrupted = true;
805          if (guard.isSatisfied()) {
806            return true;
807          }
808          signalBeforeWaiting = false;
809          remainingNanos = remainingNanos(startTime, timeoutNanos);
810        }
811      }
812    } finally {
813      if (interrupted) {
814        Thread.currentThread().interrupt();
815      }
816    }
817  }
818
819  /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */
820  public void leave() {
821    final ReentrantLock lock = this.lock;
822    try {
823      // No need to signal if we will still be holding the lock when we return
824      if (lock.getHoldCount() == 1) {
825        signalNextWaiter();
826      }
827    } finally {
828      lock.unlock(); // Will throw IllegalMonitorStateException if not held
829    }
830  }
831
832  /** Returns whether this monitor is using a fair ordering policy. */
833  public boolean isFair() {
834    return fair;
835  }
836
837  /**
838   * Returns whether this monitor is occupied by any thread. This method is designed for use in
839   * monitoring of the system state, not for synchronization control.
840   */
841  public boolean isOccupied() {
842    return lock.isLocked();
843  }
844
845  /**
846   * Returns whether the current thread is occupying this monitor (has entered more times than it
847   * has left).
848   */
849  public boolean isOccupiedByCurrentThread() {
850    return lock.isHeldByCurrentThread();
851  }
852
853  /**
854   * Returns the number of times the current thread has entered this monitor in excess of the number
855   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
856   */
857  public int getOccupiedDepth() {
858    return lock.getHoldCount();
859  }
860
861  /**
862   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
863   * an estimate because the number of threads may change dynamically while this method traverses
864   * internal data structures. This method is designed for use in monitoring of the system state,
865   * not for synchronization control.
866   */
867  public int getQueueLength() {
868    return lock.getQueueLength();
869  }
870
871  /**
872   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
873   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
874   * enter this monitor. This method is designed primarily for use in monitoring of the system
875   * state.
876   */
877  public boolean hasQueuedThreads() {
878    return lock.hasQueuedThreads();
879  }
880
881  /**
882   * Queries whether the given thread is waiting to enter this monitor. Note that because
883   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
884   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
885   * system state.
886   */
887  public boolean hasQueuedThread(Thread thread) {
888    return lock.hasQueuedThread(thread);
889  }
890
891  /**
892   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
893   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
894   * that the guard becoming satisfied in the future will awaken any threads. This method is
895   * designed primarily for use in monitoring of the system state.
896   */
897  public boolean hasWaiters(Guard guard) {
898    return getWaitQueueLength(guard) > 0;
899  }
900
901  /**
902   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
903   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
904   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
905   * the system state, not for synchronization control.
906   */
907  public int getWaitQueueLength(Guard guard) {
908    if (guard.monitor != this) {
909      throw new IllegalMonitorStateException();
910    }
911    lock.lock();
912    try {
913      return guard.waiterCount;
914    } finally {
915      lock.unlock();
916    }
917  }
918
919  /**
920   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
921   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
922   * Actually waiting for more than 219 years is not supported!
923   */
924  private static long toSafeNanos(long time, TimeUnit unit) {
925    long timeoutNanos = unit.toNanos(time);
926    return Longs.constrainToRange(timeoutNanos, 0L, (Long.MAX_VALUE / 4) * 3);
927  }
928
929  /**
930   * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
931   * timeout has already elapsed.
932   */
933  private static long initNanoTime(long timeoutNanos) {
934    if (timeoutNanos <= 0L) {
935      return 0L;
936    } else {
937      long startTime = System.nanoTime();
938      return (startTime == 0L) ? 1L : startTime;
939    }
940  }
941
942  /**
943   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
944   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
945   */
946  private static long remainingNanos(long startTime, long timeoutNanos) {
947    // assert timeoutNanos == 0L || startTime != 0L;
948
949    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
950    // if (true) return timeoutNanos;
951    // ONLY 2 TESTS FAIL IF WE DO:
952    // if (true) return 0;
953
954    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
955  }
956
957  /**
958   * Signals some other thread waiting on a satisfied guard, if one exists.
959   *
960   * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a
961   * signal, which is the classic problem of this kind of concurrency construct. We must signal if
962   * the current thread is about to relinquish the lock and may have changed the state protected by
963   * the monitor, thereby causing some guard to be satisfied.
964   *
965   * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the
966   * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
967   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
968   * since the concurrency control must manage multiple Conditions. So this method must generally be
969   * called when waits are interrupted.
970   *
971   * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not
972   * satisfied, it does *not* need to call this method before returning to wait. This can only
973   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
974   * current thread can and returning the guard to the unsatisfied state. In the latter case the
975   * other thread (last thread modifying the state protected by the monitor) takes over the
976   * responsibility of signalling the next waiter.
977   *
978   * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
979   * the current thread's guard might be mistakenly signalled, leading to a lost signal.
980   */
981  @GuardedBy("lock")
982  private void signalNextWaiter() {
983    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
984      if (isSatisfied(guard)) {
985        guard.condition.signal();
986        break;
987      }
988    }
989  }
990
991  /**
992   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
993   * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
994   * optimization for the case that guardToSkip.isSatisfied() may be expensive.
995   *
996   * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very
997   * cheap (typically one field read). Resurrect this method if you find that not to be true.
998   */
999  //   @GuardedBy("lock")
1000  //   private void signalNextWaiterSkipping(Guard guardToSkip) {
1001  //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1002  //       if (guard != guardToSkip && isSatisfied(guard)) {
1003  //         guard.condition.signal();
1004  //         break;
1005  //       }
1006  //     }
1007  //   }
1008
1009  /**
1010   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
1011   * unlikely) event that isSatisfied() throws.
1012   */
1013  @GuardedBy("lock")
1014  private boolean isSatisfied(Guard guard) {
1015    try {
1016      return guard.isSatisfied();
1017    } catch (Throwable throwable) {
1018      signalAllWaiters();
1019      throw throwable;
1020    }
1021  }
1022
1023  /** Signals all threads waiting on guards. */
1024  @GuardedBy("lock")
1025  private void signalAllWaiters() {
1026    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1027      guard.condition.signalAll();
1028    }
1029  }
1030
1031  /** Records that the current thread is about to wait on the specified guard. */
1032  @GuardedBy("lock")
1033  private void beginWaitingFor(Guard guard) {
1034    int waiters = guard.waiterCount++;
1035    if (waiters == 0) {
1036      // push guard onto activeGuards
1037      guard.next = activeGuards;
1038      activeGuards = guard;
1039    }
1040  }
1041
1042  /** Records that the current thread is no longer waiting on the specified guard. */
1043  @GuardedBy("lock")
1044  private void endWaitingFor(Guard guard) {
1045    int waiters = --guard.waiterCount;
1046    if (waiters == 0) {
1047      // unlink guard from activeGuards
1048      for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
1049        if (p == guard) {
1050          if (pred == null) {
1051            activeGuards = p.next;
1052          } else {
1053            pred.next = p.next;
1054          }
1055          p.next = null; // help GC
1056          break;
1057        }
1058      }
1059    }
1060  }
1061
1062  /*
1063   * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
1064   * this fact so that other threads know to check our guard and signal us. It's caller's
1065   * responsibility to ensure that the guard is *not* currently satisfied.
1066   */
1067
1068  @GuardedBy("lock")
1069  private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
1070    if (signalBeforeWaiting) {
1071      signalNextWaiter();
1072    }
1073    beginWaitingFor(guard);
1074    try {
1075      do {
1076        guard.condition.await();
1077      } while (!guard.isSatisfied());
1078    } finally {
1079      endWaitingFor(guard);
1080    }
1081  }
1082
1083  @GuardedBy("lock")
1084  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1085    if (signalBeforeWaiting) {
1086      signalNextWaiter();
1087    }
1088    beginWaitingFor(guard);
1089    try {
1090      do {
1091        guard.condition.awaitUninterruptibly();
1092      } while (!guard.isSatisfied());
1093    } finally {
1094      endWaitingFor(guard);
1095    }
1096  }
1097
1098  /** Caller should check before calling that guard is not satisfied. */
1099  @GuardedBy("lock")
1100  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1101      throws InterruptedException {
1102    boolean firstTime = true;
1103    try {
1104      do {
1105        if (nanos <= 0L) {
1106          return false;
1107        }
1108        if (firstTime) {
1109          if (signalBeforeWaiting) {
1110            signalNextWaiter();
1111          }
1112          beginWaitingFor(guard);
1113          firstTime = false;
1114        }
1115        nanos = guard.condition.awaitNanos(nanos);
1116      } while (!guard.isSatisfied());
1117      return true;
1118    } finally {
1119      if (!firstTime) {
1120        endWaitingFor(guard);
1121      }
1122    }
1123  }
1124}