| // Copyright 2019 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.skyframe; |
| |
| import com.google.common.collect.Iterables; |
| import com.google.common.collect.Lists; |
| import com.google.common.collect.MapMaker; |
| import com.google.common.collect.Maps; |
| import com.google.devtools.build.lib.actions.ActionExecutionException; |
| import com.google.devtools.build.lib.actions.Artifact; |
| import com.google.devtools.build.lib.collect.nestedset.NestedSet; |
| import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; |
| import com.google.devtools.build.lib.util.Pair; |
| import com.google.devtools.build.skyframe.SkyFunction; |
| import com.google.devtools.build.skyframe.SkyFunctionException; |
| import com.google.devtools.build.skyframe.SkyKey; |
| import com.google.devtools.build.skyframe.SkyValue; |
| import com.google.devtools.build.skyframe.ValueOrException3; |
| import java.io.IOException; |
| import java.util.ArrayList; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.concurrent.ConcurrentMap; |
| |
| /** |
| * A builder of values for {@link ArtifactNestedSetKey}. |
| * |
| * <p>When an Action is executed with ActionExecutionFunction, the actions's input {@code |
| * NestedSet<Artifact>} could be evaluated as an {@link ArtifactNestedSetKey}[1]. |
| * |
| * <p>{@link ArtifactNestedSetFunction} then evaluates the {@link ArtifactNestedSetKey} by: |
| * |
| * <p>- Evaluating the directs elements as Artifacts. Commit the result into |
| * artifactSkyKeyToValueOrException. |
| * |
| * <p>- Evaluating the transitive elements as {@link ArtifactNestedSetKey}s. |
| * |
| * <p>ActionExecutionFunction can then access this map to get the Artifacts' values. |
| * |
| * <p>[1] Heuristic: If the size of the NestedSet exceeds a certain threshold, we evaluate it as an |
| * ArtifactNestedSetKey. |
| */ |
| final class ArtifactNestedSetFunction implements SkyFunction { |
| |
| /** |
| * A concurrent map from Artifacts' SkyKeys to their ValueOrException, for Artifacts that are part |
| * of NestedSets which were evaluated as {@link ArtifactNestedSetKey}. |
| * |
| * <p>Question: Why don't we clear artifactSkyKeyToValueOrException after each build? |
| * |
| * <p>The map maintains an invariant: if an ArtifactNestedSetKey exists on Skyframe, the SkyValues |
| * of its member Artifacts are available in artifactSkyKeyToValueOrException. |
| * |
| * <p>Example: Action A has as input NestedSet X, where X = (X1, X2), where X1 & X2 are 2 |
| * transitive NestedSets. |
| * |
| * <p>Run 0: Establish dependency from A to X and from X to X1 & X2. Artifacts from X1 & X2 have |
| * entries in artifactSkyKeyToValueOrException. |
| * |
| * <p>Run 1 (incremental): Some changes were made to an Artifact in X1 such that X1, X and A's |
| * SkyKeys are marked as dirty. A's ActionLookupData has to be re-evaluated. This involves asking |
| * Skyframe to compute SkyValues for its inputs. |
| * |
| * <p>However, X2 is not dirty, so Skyframe won't re-run ArtifactNestedSetFunction#compute for X2, |
| * therefore not populating artifactSkyKeyToValueOrException with X2's member Artifacts. Hence if |
| * we clear artifactSkyKeyToValueOrException between build 0 and 1, X2's member artifacts' |
| * SkyValues would not be available in the map. |
| * |
| * <p>We can't make this a: |
| * |
| * <p>- Weak-keyd map since ActionExecutionValue holds a reference to Artifact. |
| * |
| * <p>- Weak-valued map since there's nothing else holding on to ValueOrException and the entry |
| * will GCed immediately. // TODO(leba): Re-evaluate the above point about weak-valued map. |
| * |
| * <p>This map will be removed when --experimental_nsos_eval_keys_as_one_group is stable, and |
| * replaced by {@link #artifactSkyKeyToSkyValue}. |
| */ |
| private ConcurrentMap< |
| SkyKey, |
| ValueOrException3<IOException, ActionExecutionException, ArtifactNestedSetEvalException>> |
| artifactSkyKeyToValueOrException; |
| |
| /** |
| * A concurrent map from Artifacts' SkyKeys to their SkyValue, for Artifacts that are part of |
| * NestedSets which were evaluated as {@link ArtifactNestedSetKey}. This is expected to replace |
| * the above {@link #artifactSkyKeyToValueOrException}. |
| */ |
| private ConcurrentMap<SkyKey, SkyValue> artifactSkyKeyToSkyValue; |
| |
| /** |
| * Maps the NestedSets' underlying objects to the corresponding SkyKey. This is to avoid |
| * re-creating SkyKey for the same nested set upon reevaluation because of e.g. a missing value. |
| * |
| * <p>The map weakly references its values: when the ArtifactNestedSetKey becomes otherwise |
| * unreachable, the map entry is collected. |
| */ |
| private final ConcurrentMap<NestedSet.Node, ArtifactNestedSetKey> |
| nestedSetToSkyKey; // note: weak values! |
| |
| private static ArtifactNestedSetFunction singleton = null; |
| |
| private static Integer sizeThreshold = null; |
| |
| private static Boolean evalKeysAsOneGroup = null; |
| |
| private ArtifactNestedSetFunction() { |
| artifactSkyKeyToSkyValue = Maps.newConcurrentMap(); |
| artifactSkyKeyToValueOrException = Maps.newConcurrentMap(); |
| nestedSetToSkyKey = new MapMaker().weakValues().makeMap(); |
| } |
| |
| @Override |
| public SkyValue compute(SkyKey skyKey, Environment env) |
| throws InterruptedException, ArtifactNestedSetFunctionException { |
| |
| if (evalKeysAsOneGroup) { |
| return evalDepsInOneGroup(skyKey, env); |
| } |
| |
| ArtifactNestedSetKey key = (ArtifactNestedSetKey) skyKey; |
| Map< |
| SkyKey, |
| ValueOrException3< |
| IOException, ActionExecutionException, ArtifactNestedSetEvalException>> |
| directArtifactsEvalResult = |
| env.getValuesOrThrow( |
| Iterables.transform(key.getSet().getLeaves(), Artifact::key), |
| IOException.class, |
| ActionExecutionException.class, |
| ArtifactNestedSetEvalException.class); |
| |
| // Evaluate all children. |
| List<NestedSet<Artifact>> nonleaves = key.getSet().getNonLeaves(); |
| List<SkyKey> transitiveKeys = Lists.newArrayListWithCapacity(nonleaves.size()); |
| for (NestedSet<Artifact> nonleaf : nonleaves) { |
| transitiveKeys.add( |
| nestedSetToSkyKey.computeIfAbsent( |
| nonleaf.toNode(), (node) -> new ArtifactNestedSetKey(nonleaf, node))); |
| } |
| env.getValues(transitiveKeys); |
| |
| if (env.valuesMissing()) { |
| return null; |
| } |
| |
| // Only commit to the map when every value is present. |
| artifactSkyKeyToValueOrException.putAll(directArtifactsEvalResult); |
| return new ArtifactNestedSetValue(); |
| } |
| |
| /** The main path with --experimental_nsos_eval_keys_as_one_group. */ |
| private SkyValue evalDepsInOneGroup(SkyKey skyKey, Environment env) |
| throws InterruptedException, ArtifactNestedSetFunctionException { |
| NestedSet<Artifact> set = ((ArtifactNestedSetKey) skyKey).getSet(); |
| List<SkyKey> keys = new ArrayList<>(); |
| for (Artifact file : set.getLeaves()) { |
| keys.add(Artifact.key(file)); |
| } |
| for (NestedSet<Artifact> nonleaf : set.getNonLeaves()) { |
| keys.add( |
| nestedSetToSkyKey.computeIfAbsent( |
| nonleaf.toNode(), (node) -> new ArtifactNestedSetKey(nonleaf, node))); |
| } |
| Map< |
| SkyKey, |
| ValueOrException3< |
| IOException, ActionExecutionException, ArtifactNestedSetEvalException>> |
| depsEvalResult = |
| env.getValuesOrThrow( |
| keys, |
| IOException.class, |
| ActionExecutionException.class, |
| ArtifactNestedSetEvalException.class); |
| |
| NestedSetBuilder<Pair<SkyKey, Exception>> transitiveExceptionsBuilder = |
| NestedSetBuilder.stableOrder(); |
| |
| // Throw a SkyFunctionException when a dep evaluation results in an exception. |
| // Only non-null values should be committed to |
| // ArtifactNestedSetFunction#artifacSkyKeyToSkyValue. |
| for (Map.Entry< |
| SkyKey, |
| ValueOrException3< |
| IOException, ActionExecutionException, ArtifactNestedSetEvalException>> |
| entry : depsEvalResult.entrySet()) { |
| try { |
| // Trigger the exception, if any. |
| SkyValue value = entry.getValue().get(); |
| if (entry.getKey() instanceof ArtifactNestedSetKey || value == null) { |
| continue; |
| } |
| artifactSkyKeyToSkyValue.put(entry.getKey(), value); |
| } catch (IOException | ActionExecutionException e) { |
| transitiveExceptionsBuilder.add(Pair.of(entry.getKey(), e)); |
| } catch (ArtifactNestedSetEvalException e) { |
| transitiveExceptionsBuilder.addTransitive(e.getNestedExceptions()); |
| } |
| } |
| |
| if (!transitiveExceptionsBuilder.isEmpty()) { |
| NestedSet<Pair<SkyKey, Exception>> transitiveExceptions = transitiveExceptionsBuilder.build(); |
| throw new ArtifactNestedSetFunctionException( |
| new ArtifactNestedSetEvalException( |
| transitiveExceptions.memoizedFlattenAndGetSize() |
| + " error(s) encountered while evaluating NestedSet.", |
| transitiveExceptions), |
| skyKey); |
| } |
| |
| // This should only happen when all error handling is done. |
| if (env.valuesMissing()) { |
| return null; |
| } |
| return new ArtifactNestedSetValue(); |
| } |
| |
| static ArtifactNestedSetFunction getInstance() { |
| if (singleton == null) { |
| return createInstance(); |
| } |
| return singleton; |
| } |
| |
| /** |
| * Creates a new instance. Should only be used in {@code SkyframeExecutor#skyFunctions}. Keeping |
| * this method separated from {@code #getInstance} since sometimes we need to overwrite the |
| * existing instance. |
| */ |
| static ArtifactNestedSetFunction createInstance() { |
| singleton = new ArtifactNestedSetFunction(); |
| return singleton; |
| } |
| |
| /** Reset the various state-keeping maps of ArtifactNestedSetFunction. */ |
| void resetArtifactNestedSetFunctionMaps() { |
| artifactSkyKeyToValueOrException = Maps.newConcurrentMap(); |
| artifactSkyKeyToSkyValue = Maps.newConcurrentMap(); |
| } |
| |
| Map<SkyKey, SkyValue> getArtifactSkyKeyToSkyValue() { |
| return artifactSkyKeyToSkyValue; |
| } |
| |
| Map< |
| SkyKey, |
| ValueOrException3<IOException, ActionExecutionException, ArtifactNestedSetEvalException>> |
| getArtifactSkyKeyToValueOrException() { |
| return artifactSkyKeyToValueOrException; |
| } |
| |
| @Override |
| public String extractTag(SkyKey skyKey) { |
| return null; |
| } |
| |
| /** |
| * Get the threshold to which we evaluate a NestedSet as a Skykey. If sizeThreshold is unset, |
| * return the default value of 0. |
| */ |
| static int getSizeThreshold() { |
| return sizeThreshold == null ? 0 : sizeThreshold; |
| } |
| |
| static boolean evalKeysAsOneGroup() { |
| return evalKeysAsOneGroup; |
| } |
| |
| /** |
| * Updates the evalKeysAsOneGroup attr if the existing value differs from the new one. |
| * |
| * @return whether an update was made. |
| */ |
| static boolean evalKeysAsOneGroupUpdated(boolean newEvalKeysAsOneGroup) { |
| // If this is the first time the value is set, it's not considered "updated". |
| if (evalKeysAsOneGroup == null) { |
| evalKeysAsOneGroup = newEvalKeysAsOneGroup; |
| return false; |
| } |
| |
| if (evalKeysAsOneGroup != newEvalKeysAsOneGroup) { |
| evalKeysAsOneGroup = newEvalKeysAsOneGroup; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /** |
| * Updates the sizeThreshold value if the existing value differs from newValue. |
| * |
| * @param newValue The new value from --experimental_nested_set_as_skykey_threshold. |
| * @return whether an update was made. |
| */ |
| static boolean sizeThresholdUpdated(int newValue) { |
| // If this is the first time the value is set, it's not considered "updated". |
| if (sizeThreshold == null) { |
| sizeThreshold = newValue; |
| return false; |
| } |
| |
| if (sizeThreshold == newValue || (sizeThreshold <= 0 && newValue <= 0)) { |
| return false; |
| } |
| sizeThreshold = newValue; |
| return true; |
| } |
| |
| /** Mainly used for error bubbling when evaluating direct/transitive children. */ |
| private static final class ArtifactNestedSetFunctionException extends SkyFunctionException { |
| |
| ArtifactNestedSetFunctionException(ArtifactNestedSetEvalException e, SkyKey child) { |
| super(e, child); |
| } |
| |
| @Override |
| public boolean isCatastrophic() { |
| return false; |
| } |
| } |
| |
| /** Bundles the exceptions from the evaluation of the children keys together. */ |
| static final class ArtifactNestedSetEvalException extends Exception { |
| |
| private final NestedSet<Pair<SkyKey, Exception>> nestedExceptions; |
| |
| ArtifactNestedSetEvalException( |
| String message, NestedSet<Pair<SkyKey, Exception>> nestedExceptions) { |
| super(message); |
| this.nestedExceptions = nestedExceptions; |
| } |
| |
| NestedSet<Pair<SkyKey, Exception>> getNestedExceptions() { |
| return nestedExceptions; |
| } |
| } |
| } |