src/main/java/com/android/tools/r8/algorithms/scc/SCC.java

// Copyright (c) 2020, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.algorithms.scc;

import com.android.tools.r8.utils.SetUtils;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Set;
import java.util.function.Function;

public class SCC<Node> {

  private int currentTime = 0;
  private final Reference2IntMap<Node> discoverTime = new Reference2IntOpenHashMap<>();
  private final Set<Node> unassignedSet = Sets.newIdentityHashSet();
  private final Deque<Node> unassignedStack = new ArrayDeque<>();
  private final Deque<Node> preorderStack = new ArrayDeque<>();
  private final List<Set<Node>> components = new ArrayList<>();

  private final Function<Node, Iterable<? extends Node>> successors;

  public SCC(Function<Node, Iterable<? extends Node>> successors) {
    this.successors = successors;
  }

  public List<Set<Node>> computeSCC(Node v) {
    assert currentTime == 0;
    dfs(v);
    return components;
  }

  private void dfs(Node value) {
    discoverTime.put(value, currentTime++);
    unassignedSet.add(value);
    unassignedStack.push(value);
    preorderStack.push(value);
    for (Node successor : successors.apply(value)) {
      if (!discoverTime.containsKey(successor)) {
        // If not seen yet, continue the search.
        dfs(successor);
      } else if (unassignedSet.contains(successor)) {
        // If seen already and the element is on the unassigned stack we have found a cycle.
        // Pop off everything discovered later than the target from the preorder stack. This may
        // not coincide with the cycle as an outer cycle may already have popped elements off.
        int discoverTimeOfPhi = discoverTime.getInt(successor);
        while (discoverTimeOfPhi < discoverTime.getInt(preorderStack.peek())) {
          preorderStack.pop();
        }
      }
    }
    if (preorderStack.peek() == value) {
      // If the current element is the top of the preorder stack, then we are at entry to a
      // strongly-connected component consisting of this element and every element above this
      // element on the stack.
      Set<Node> component = SetUtils.newIdentityHashSet(unassignedStack.size());
      while (true) {
        Node member = unassignedStack.pop();
        unassignedSet.remove(member);
        component.add(member);
        if (member == value) {
          components.add(component);
          break;
        }
      }
      preorderStack.pop();
    }
  }
}