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.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 java.util.function.BooleanSupplier;
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 final ReentrantLock lock = new ReentrantLock();
125 *   private final Condition valuePresent = lock.newCondition();
126 *   private final Condition valueAbsent = lock.newCondition();
127 *   private V value;
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 final Monitor monitor = new Monitor();
170 *   private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
171 *     public boolean isSatisfied() {
172 *       return value != null;
173 *     }
174 *   };
175 *   private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
176 *     public boolean isSatisfied() {
177 *       return value == null;
178 *     }
179 *   };
180 *   private V value;
181 *
182 *   public V get() throws InterruptedException {
183 *     monitor.enterWhen(valuePresent);
184 *     try {
185 *       V result = value;
186 *       value = null;
187 *       return result;
188 *     } finally {
189 *       monitor.leave();
190 *     }
191 *   }
192 *
193 *   public void set(V newValue) throws InterruptedException {
194 *     monitor.enterWhen(valueAbsent);
195 *     try {
196 *       value = newValue;
197 *     } finally {
198 *       monitor.leave();
199 *     }
200 *   }
201 * }
202 * }</pre>
203 *
204 * @author Justin T. Sampson
205 * @author Martin Buchholz
206 * @since 10.0
207 */
208@Beta
209@GwtIncompatible
210@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
211public final class Monitor {
212  // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
213  // TODO(user): "Port" jsr166 tests for ReentrantLock.
214  //
215  // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
216  //    by making the monitor implicit, and to eliminate other sources of IMSE.
217  //    Imagine:
218  //    guard.lock();
219  //    try { /* monitor locked and guard satisfied here */ }
220  //    finally { guard.unlock(); }
221  // Here are Justin's design notes about this:
222  //
223  // This idea has come up from time to time, and I think one of my
224  // earlier versions of Monitor even did something like this. I ended
225  // up strongly favoring the current interface.
226  //
227  // I probably can't remember all the reasons (it's possible you
228  // could find them in the code review archives), but here are a few:
229  //
230  // 1. What about leaving/unlocking? Are you going to do
231  //    guard.enter() paired with monitor.leave()? That might get
232  //    confusing. It's nice for the finally block to look as close as
233  //    possible to the thing right before the try. You could have
234  //    guard.leave(), but that's a little odd as well because the
235  //    guard doesn't have anything to do with leaving. You can't
236  //    really enforce that the guard you're leaving is the same one
237  //    you entered with, and it doesn't actually matter.
238  //
239  // 2. Since you can enter the monitor without a guard at all, some
240  //    places you'll have monitor.enter()/monitor.leave() and other
241  //    places you'll have guard.enter()/guard.leave() even though
242  //    it's the same lock being acquired underneath. Always using
243  //    monitor.enterXXX()/monitor.leave() will make it really clear
244  //    which lock is held at any point in the code.
245  //
246  // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
247  //
248  // TODO(user): Implement ReentrantLock features:
249  //    - toString() method
250  //    - getOwner() method
251  //    - getQueuedThreads() method
252  //    - getWaitingThreads(Guard) method
253  //    - implement Serializable
254  //    - redo the API to be as close to identical to ReentrantLock as possible,
255  //      since, after all, this class is also a reentrant mutual exclusion lock!?
256
257  /*
258   * One of the key challenges of this class is to prevent lost signals, while trying hard to
259   * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter
260   * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the
261   * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This
262   * includes exceptional exits, so all control paths involving signalling must be protected by a
263   * finally block.
264   *
265   * Further optimizations of this algorithm become increasingly subtle. A wait that terminates
266   * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit
267   * the monitor without signalling. If it timed out without being signalled, it does not need to
268   * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been
269   * satisfied at the time of signal, and has since been modified by some other thread to be
270   * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility
271   * of signaling the next waiter.
272   *
273   * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be
274   * lost, because the signal may be sent to a condition whose sole waiter has just been
275   * interrupted.
276   *
277   * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards,
278   * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions
279   * need to be signalled because it is not known which if any of them have waiters (and hasWaiters
280   * can't be used reliably because of a check-then-act race). With our Monitor guards, we only
281   * signal the first active guard that is satisfied. But the corresponding thread may have already
282   * been interrupted and is waiting to reacquire the lock while still registered in activeGuards,
283   * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted
284   * threads take special action by participating in the signal-passing game.
285   */
286
287  /*
288   * Timeout handling is intricate, especially given our ambitious goals:
289   * - Avoid underflow and overflow of timeout values when specified timeouts are close to
290   *   Long.MIN_VALUE or Long.MAX_VALUE.
291   * - Favor responding to interrupts over timeouts.
292   * - System.nanoTime() is expensive enough that we want to call it the minimum required number of
293   *   times, typically once before invoking a blocking method. This often requires keeping track of
294   *   the first time in a method that nanoTime() has been invoked, for which the special value 0L
295   *   is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be
296   *   called.
297   * - Keep behavior of fair and non-fair instances consistent.
298   */
299
300  /**
301   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
302   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
303   * the monitor, so code should not be written to rely on how often a guard might or might not be
304   * checked.
305   *
306   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
307   * associated with, an {@link IllegalMonitorStateException} is thrown.
308   *
309   * @since 10.0
310   */
311  @Beta
312  public abstract static class Guard {
313
314    @Weak final Monitor monitor;
315    final Condition condition;
316
317    @GuardedBy("monitor.lock")
318    int waiterCount = 0;
319
320    /** The next active guard */
321    @GuardedBy("monitor.lock")
322    Guard next;
323
324    protected Guard(Monitor monitor) {
325      this.monitor = checkNotNull(monitor, "monitor");
326      this.condition = monitor.lock.newCondition();
327    }
328
329    /**
330     * Evaluates this guard's boolean condition. This method is always called with the associated
331     * monitor already occupied. Implementations of this method must depend only on state protected
332     * by the associated monitor, and must not modify that state.
333     */
334    public abstract boolean isSatisfied();
335  }
336
337  /** Whether this monitor is fair. */
338  private final boolean fair;
339
340  /** The lock underlying this monitor. */
341  private final ReentrantLock lock;
342
343  /**
344   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
345   * A linked list threaded through the Guard.next field.
346   */
347  @GuardedBy("lock")
348  private Guard activeGuards = null;
349
350  /**
351   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
352   * Monitor(false)}.
353   */
354  public Monitor() {
355    this(false);
356  }
357
358  /**
359   * Creates a monitor with the given ordering policy.
360   *
361   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
362   *     fast) one
363   */
364  public Monitor(boolean fair) {
365    this.fair = fair;
366    this.lock = new ReentrantLock(fair);
367  }
368
369  /**
370   * Creates a new {@link Guard} for {@code this} monitor. @Param isSatisfied The guards boolean
371   * condition. See {@link Guard#isSatisfied}.
372   */
373  public Guard newGuard(final BooleanSupplier isSatisfied) {
374    checkNotNull(isSatisfied, "isSatisfied");
375    return new Guard(this) {
376      @Override
377      public boolean isSatisfied() {
378        return isSatisfied.getAsBoolean();
379      }
380    };
381  }
382
383  /** Enters this monitor. Blocks indefinitely. */
384  public void enter() {
385    lock.lock();
386  }
387
388  /**
389   * Enters this monitor. Blocks indefinitely, but may be interrupted.
390   *
391   * @throws InterruptedException if interrupted while waiting
392   */
393  public void enterInterruptibly() throws InterruptedException {
394    lock.lockInterruptibly();
395  }
396
397  /**
398   * Enters this monitor. Blocks at most the given time.
399   *
400   * @return whether the monitor was entered
401   */
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 at most the given time, and may be interrupted.
428   *
429   * @return whether the monitor was entered
430   * @throws InterruptedException if interrupted while waiting
431   */
432  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
433    return lock.tryLock(time, unit);
434  }
435
436  /**
437   * Enters this monitor if it is possible to do so immediately. Does not block.
438   *
439   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
440   *
441   * @return whether the monitor was entered
442   */
443  public boolean tryEnter() {
444    return lock.tryLock();
445  }
446
447  /**
448   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
449   *
450   * @throws InterruptedException if interrupted while waiting
451   */
452  public void enterWhen(Guard guard) throws InterruptedException {
453    if (guard.monitor != this) {
454      throw new IllegalMonitorStateException();
455    }
456    final ReentrantLock lock = this.lock;
457    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
458    lock.lockInterruptibly();
459
460    boolean satisfied = false;
461    try {
462      if (!guard.isSatisfied()) {
463        await(guard, signalBeforeWaiting);
464      }
465      satisfied = true;
466    } finally {
467      if (!satisfied) {
468        leave();
469      }
470    }
471  }
472
473  /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */
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  /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */
831  public void leave() {
832    final ReentrantLock lock = this.lock;
833    try {
834      // No need to signal if we will still be holding the lock when we return
835      if (lock.getHoldCount() == 1) {
836        signalNextWaiter();
837      }
838    } finally {
839      lock.unlock(); // Will throw IllegalMonitorStateException if not held
840    }
841  }
842
843  /** Returns whether this monitor is using a fair ordering policy. */
844  public boolean isFair() {
845    return fair;
846  }
847
848  /**
849   * Returns whether this monitor is occupied by any thread. This method is designed for use in
850   * monitoring of the system state, not for synchronization control.
851   */
852  public boolean isOccupied() {
853    return lock.isLocked();
854  }
855
856  /**
857   * Returns whether the current thread is occupying this monitor (has entered more times than it
858   * has left).
859   */
860  public boolean isOccupiedByCurrentThread() {
861    return lock.isHeldByCurrentThread();
862  }
863
864  /**
865   * Returns the number of times the current thread has entered this monitor in excess of the number
866   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
867   */
868  public int getOccupiedDepth() {
869    return lock.getHoldCount();
870  }
871
872  /**
873   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
874   * an estimate because the number of threads may change dynamically while this method traverses
875   * internal data structures. This method is designed for use in monitoring of the system state,
876   * not for synchronization control.
877   */
878  public int getQueueLength() {
879    return lock.getQueueLength();
880  }
881
882  /**
883   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
884   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
885   * enter this monitor. This method is designed primarily for use in monitoring of the system
886   * state.
887   */
888  public boolean hasQueuedThreads() {
889    return lock.hasQueuedThreads();
890  }
891
892  /**
893   * Queries whether the given thread is waiting to enter this monitor. Note that because
894   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
895   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
896   * system state.
897   */
898  public boolean hasQueuedThread(Thread thread) {
899    return lock.hasQueuedThread(thread);
900  }
901
902  /**
903   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
904   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
905   * that the guard becoming satisfied in the future will awaken any threads. This method is
906   * designed primarily for use in monitoring of the system state.
907   */
908  public boolean hasWaiters(Guard guard) {
909    return getWaitQueueLength(guard) > 0;
910  }
911
912  /**
913   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
914   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
915   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
916   * the system state, not for synchronization control.
917   */
918  public int getWaitQueueLength(Guard guard) {
919    if (guard.monitor != this) {
920      throw new IllegalMonitorStateException();
921    }
922    lock.lock();
923    try {
924      return guard.waiterCount;
925    } finally {
926      lock.unlock();
927    }
928  }
929
930  /**
931   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
932   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
933   * Actually waiting for more than 219 years is not supported!
934   */
935  private static long toSafeNanos(long time, TimeUnit unit) {
936    long timeoutNanos = unit.toNanos(time);
937    return (timeoutNanos <= 0L)
938        ? 0L
939        : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos;
940  }
941
942  /**
943   * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
944   * timeout has already elapsed.
945   */
946  private static long initNanoTime(long timeoutNanos) {
947    if (timeoutNanos <= 0L) {
948      return 0L;
949    } else {
950      long startTime = System.nanoTime();
951      return (startTime == 0L) ? 1L : startTime;
952    }
953  }
954
955  /**
956   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
957   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
958   */
959  private static long remainingNanos(long startTime, long timeoutNanos) {
960    // assert timeoutNanos == 0L || startTime != 0L;
961
962    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
963    // if (true) return timeoutNanos;
964    // ONLY 2 TESTS FAIL IF WE DO:
965    // if (true) return 0;
966
967    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
968  }
969
970  /**
971   * Signals some other thread waiting on a satisfied guard, if one exists.
972   *
973   * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a
974   * signal, which is the classic problem of this kind of concurrency construct. We must signal if
975   * the current thread is about to relinquish the lock and may have changed the state protected by
976   * the monitor, thereby causing some guard to be satisfied.
977   *
978   * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the
979   * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
980   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
981   * since the concurrency control must manage multiple Conditions. So this method must generally be
982   * called when waits are interrupted.
983   *
984   * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not
985   * satisfied, it does *not* need to call this method before returning to wait. This can only
986   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
987   * current thread can and returning the guard to the unsatisfied state. In the latter case the
988   * other thread (last thread modifying the state protected by the monitor) takes over the
989   * responsibility of signalling the next waiter.
990   *
991   * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
992   * the current thread's guard might be mistakenly signalled, leading to a lost signal.
993   */
994  @GuardedBy("lock")
995  private void signalNextWaiter() {
996    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
997      if (isSatisfied(guard)) {
998        guard.condition.signal();
999        break;
1000      }
1001    }
1002  }
1003
1004  /**
1005   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
1006   * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
1007   * optimization for the case that guardToSkip.isSatisfied() may be expensive.
1008   *
1009   * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very
1010   * cheap (typically one field read). Resurrect this method if you find that not to be true.
1011   */
1012  //   @GuardedBy("lock")
1013  //   private void signalNextWaiterSkipping(Guard guardToSkip) {
1014  //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1015  //       if (guard != guardToSkip && isSatisfied(guard)) {
1016  //         guard.condition.signal();
1017  //         break;
1018  //       }
1019  //     }
1020  //   }
1021
1022  /**
1023   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
1024   * unlikely) event that isSatisfied() throws.
1025   */
1026  @GuardedBy("lock")
1027  private boolean isSatisfied(Guard guard) {
1028    try {
1029      return guard.isSatisfied();
1030    } catch (Throwable throwable) {
1031      signalAllWaiters();
1032      throw Throwables.propagate(throwable);
1033    }
1034  }
1035
1036  /** Signals all threads waiting on guards. */
1037  @GuardedBy("lock")
1038  private void signalAllWaiters() {
1039    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1040      guard.condition.signalAll();
1041    }
1042  }
1043
1044  /** Records that the current thread is about to wait on the specified guard. */
1045  @GuardedBy("lock")
1046  private void beginWaitingFor(Guard guard) {
1047    int waiters = guard.waiterCount++;
1048    if (waiters == 0) {
1049      // push guard onto activeGuards
1050      guard.next = activeGuards;
1051      activeGuards = guard;
1052    }
1053  }
1054
1055  /** Records that the current thread is no longer waiting on the specified guard. */
1056  @GuardedBy("lock")
1057  private void endWaitingFor(Guard guard) {
1058    int waiters = --guard.waiterCount;
1059    if (waiters == 0) {
1060      // unlink guard from activeGuards
1061      for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
1062        if (p == guard) {
1063          if (pred == null) {
1064            activeGuards = p.next;
1065          } else {
1066            pred.next = p.next;
1067          }
1068          p.next = null; // help GC
1069          break;
1070        }
1071      }
1072    }
1073  }
1074
1075  /*
1076   * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
1077   * this fact so that other threads know to check our guard and signal us. It's caller's
1078   * responsibility to ensure that the guard is *not* currently satisfied.
1079   */
1080
1081  @GuardedBy("lock")
1082  private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
1083    if (signalBeforeWaiting) {
1084      signalNextWaiter();
1085    }
1086    beginWaitingFor(guard);
1087    try {
1088      do {
1089        guard.condition.await();
1090      } while (!guard.isSatisfied());
1091    } finally {
1092      endWaitingFor(guard);
1093    }
1094  }
1095
1096  @GuardedBy("lock")
1097  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1098    if (signalBeforeWaiting) {
1099      signalNextWaiter();
1100    }
1101    beginWaitingFor(guard);
1102    try {
1103      do {
1104        guard.condition.awaitUninterruptibly();
1105      } while (!guard.isSatisfied());
1106    } finally {
1107      endWaitingFor(guard);
1108    }
1109  }
1110
1111  /** Caller should check before calling that guard is not satisfied. */
1112  @GuardedBy("lock")
1113  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1114      throws InterruptedException {
1115    boolean firstTime = true;
1116    try {
1117      do {
1118        if (nanos <= 0L) {
1119          return false;
1120        }
1121        if (firstTime) {
1122          if (signalBeforeWaiting) {
1123            signalNextWaiter();
1124          }
1125          beginWaitingFor(guard);
1126          firstTime = false;
1127        }
1128        nanos = guard.condition.awaitNanos(nanos);
1129      } while (!guard.isSatisfied());
1130      return true;
1131    } finally {
1132      if (!firstTime) {
1133        endWaitingFor(guard);
1134      }
1135    }
1136  }
1137}