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