src/main/java/com/google/devtools/build/lib/bazel/rules/ninja/actions/NinjaPhonyTargetsUtil.java

// Copyright 2020 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.devtools.build.lib.bazel.rules.ninja.actions;

import static com.google.common.base.Preconditions.checkState;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSortedMap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.bazel.rules.ninja.file.GenericParsingException;
import com.google.devtools.build.lib.bazel.rules.ninja.parser.NinjaTarget;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;

/**
 * An utility class for gathering non-phony input dependencies of phony {@link NinjaTarget} objects
 * from some Ninja file.
 *
 * <p>Cycles are detected and {@link GenericParsingException} is thrown in that case.
 */
public class NinjaPhonyTargetsUtil {

  private NinjaPhonyTargetsUtil() {}

  @VisibleForTesting
  public static ImmutableSortedMap<PathFragment, PhonyTarget> getPhonyPathsMap(
      ImmutableSortedMap<PathFragment, NinjaTarget> phonyTargets) throws GenericParsingException {
    // There is always a DAG (or forest) of phony targets (as item can be included into several
    // phony targets).
    // This gives us the idea that we can compute any subgraph in the DAG independently, and
    // later include that subgraph into the parent DAG.
    // In the list 'topoOrderedTargets' we will put all the NinjaTargets from the phonyTargets,
    // in the following order: all nodes from a node's subtree are preceding it in a list.
    // This way we can later visit the list "topoOrderedTargets", computing the input files
    // for targets, and for each target K the results for all the phony targets from a subgraph of K
    // will be already computed.
    // The sorting is linear, as we are only checking each input of each node once (we use already).
    List<NinjaTarget> topoOrderedTargets = Lists.newArrayListWithCapacity(phonyTargets.size());
    Set<NinjaTarget> alreadyVisited = Sets.newHashSet();
    for (Map.Entry<PathFragment, NinjaTarget> entry : phonyTargets.entrySet()) {
      NinjaTarget target = entry.getValue();
      topoOrderedTargets.addAll(topoOrderSubGraph(phonyTargets, alreadyVisited, target));
    }

    checkState(topoOrderedTargets.size() == phonyTargets.size());

    SortedMap<PathFragment, PhonyTarget> result = Maps.newTreeMap();
    for (NinjaTarget target : topoOrderedTargets) {
      PathFragment onlyOutput = Iterables.getOnlyElement(target.getAllOutputs());
      ImmutableList.Builder<PathFragment> phonyNames = ImmutableList.builder();
      ImmutableList.Builder<PathFragment> directInputs = ImmutableList.builder();
      Collection<PathFragment> allInputs = target.getAllInputs();
      boolean isAlwaysDirty = allInputs.isEmpty();
      for (PathFragment input : allInputs) {
        NinjaTarget phonyInput = phonyTargets.get(input);
        if (phonyInput != null) {
          // The input is the other phony target.
          // Phony target must have only one output (alias); it is checked during parsing.
          PathFragment phonyName = Iterables.getOnlyElement(phonyInput.getAllOutputs());
          PhonyTarget alreadyComputed = result.get(phonyName);
          Preconditions.checkNotNull(alreadyComputed);
          isAlwaysDirty |= alreadyComputed.isAlwaysDirty();
          phonyNames.add(Iterables.getOnlyElement(phonyInput.getAllOutputs()));
        } else {
          // The input is the usual file.
          directInputs.add(input);
        }
      }
      result.put(
          onlyOutput, new PhonyTarget(phonyNames.build(), directInputs.build(), isAlwaysDirty));
    }

    return ImmutableSortedMap.copyOf(result);
  }

  /**
   * For the given phony NinjaTarget, return a list of all phony NinjaTargets, composing its subtree
   * (direct and transitive inputs). The list is ordered from leaves to their dependents; for any
   * node all its direct and transitive inputs are preceding it in the list.
   *
   * <p>Function does DFS starting from the NinjaTarget, with two phases: in initial processing: 1)
   * if the target was already computed, nothing happens 2) the target is checked for cycle and
   * marked in cycleProtection set, its phony inputs are queued (put in the beginning of the queue)
   * for initial processing 3) the target is queued after its inputs for post-processing in
   * post-processing, the target is recorded into resulting list; all its inputs should have been
   * already written to that list on the previous steps
   */
  private static List<NinjaTarget> topoOrderSubGraph(
      ImmutableSortedMap<PathFragment, NinjaTarget> phonyTargets,
      Set<NinjaTarget> alreadyVisited,
      NinjaTarget target)
      throws GenericParsingException {
    Set<NinjaTarget> cycleProtection = Sets.newHashSet();
    List<NinjaTarget> fragment = Lists.newArrayList();
    ArrayDeque<Pair<NinjaTarget, Boolean>> queue = new ArrayDeque<>();
    queue.add(Pair.of(target, true));
    while (!queue.isEmpty()) {
      Pair<NinjaTarget, Boolean> pair = queue.remove();
      NinjaTarget currentTarget = pair.getFirst();
      if (pair.getSecond()) {
        // Initial processing: checking all the phony inputs of the current target.
        if (alreadyVisited.contains(currentTarget)) {
          continue;
        }
        if (!cycleProtection.add(currentTarget)) {
          throw new GenericParsingException(
              String.format(
                  "Detected a dependency cycle involving the phony target '%s'",
                  Iterables.getOnlyElement(currentTarget.getAllOutputs())));
        }
        // Adding <phony-inputs-of-current-target> for initial processing in front of
        // <current-target>
        // for post-processing into the queue.
        queue.addFirst(Pair.of(currentTarget, false));
        for (PathFragment input : currentTarget.getAllInputs()) {
          NinjaTarget phonyInput = phonyTargets.get(input);
          if (phonyInput != null) {
            queue.addFirst(Pair.of(phonyInput, true));
          }
        }
      } else {
        // Post processing: all inputs should have been processed and added to fragment.
        cycleProtection.remove(currentTarget);
        alreadyVisited.add(currentTarget);
        fragment.add(currentTarget);
      }
    }
    return fragment;
  }
}