*       verified or created.
 *   <li>If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
 *       to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
 *       "safe" edge is created.
 *   <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
 *       deadlock situation, and the appropriate Policy is executed.
 * </ul>
 *

   *       number of nodes that have been seen but not yet visited, that is, the "horizon").
   * </ul>
   *
   * @param graph {@link SuccessorsFunction} representing a general graph that may have cycles.
   */
  public static <N> Traverser<N> forGraph(SuccessorsFunction<N> graph) {
    return new Traverser<N>(graph) {
      @Override
      Traversal<N> newTraversal() {
        return Traversal.inGraph(graph);

  public void testScanDirectory_symlinkCycle() throws IOException {
    if (isWindows()) {
      return; // TODO: b/136041958 - Can we detect cycles under Windows?
    }
    ClassLoader loader = ClassPathTest.class.getClassLoader();
    // directory with a cycle,
    // /root
    //    /left
    //       /[sibling -> right]
    //    /right
    //       /[sibling -> left]

     * cycles; otherwise symlinks are traversed.
     *
     * @param directory the root of the directory to scan
     * @param packagePrefix resource path prefix inside {@code classloader} for any files found
     *     under {@code directory}
     * @param currentPath canonical files already visited in the current directory tree path, for
     *     cycle elimination
     */

  }

  /**
   * Returns a fluent iterable whose {@code Iterator} cycles indefinitely over the elements of this
   * fluent iterable.
   *
   * <p>That iterator supports {@code remove()} if {@code iterable.iterator()} does. After {@code
   * remove()} is called, subsequent cycles omit the removed element, which is no longer in this

  }

  /**
   * Returns a fluent iterable whose {@code Iterator} cycles indefinitely over the elements of this
   * fluent iterable.
   *
   * <p>That iterator supports {@code remove()} if {@code iterable.iterator()} does. After {@code
   * remove()} is called, subsequent cycles omit the removed element, which is no longer in this

            if (headerNameIndex in 2..7) {
              // Only search a subset of the static header table. Most entries have an empty value, so
              // it's unnecessary to waste cycles looking at them. This check is built on the
              // observation that the header entries we care about are in adjacent pairs, and we
              // always know the first index of the pair.

  // Graph query methods

  /**
   * Returns true if {@code graph} has at least one cycle. A cycle is defined as a non-empty subset
   * of edges in a graph arranged to form a path (a sequence of adjacent outgoing edges) starting
   * and ending with the same node.
   *
   * <p>This method will detect any non-empty cycle, including self-loops (a cycle of length 1).
   */
  public static <N> boolean hasCycle(Graph<N> graph) {

  private void appendUserObject(StringBuilder builder, @Nullable Object o) {
    // This is some basic recursion detection for when people create cycles via set/setFuture or
    // when deep chains of futures exist resulting in a StackOverflowError. We could detect
    // arbitrary cycles using a thread local but this should be a good enough solution (it is also
    // what jdk collections do in these cases)
    try {

    // Under that assumption, the remaining references can be safely marked as @Weak.
    // Using @Weak is necessary to avoid retain-cycles between Node instances on iOS,
    // which would cause memory leaks when non-empty HashBiMap with cyclic Node
    // instances is deallocated.
    @Nullable Node<K, V> nextInKToVBucket;
    @Weak @Nullable Node<K, V> nextInVToKBucket;