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