blob: 35d467059dbeffccdb5ab57318bc02a3d0f623a4 [file] [log] [blame]
// Copyright 2014 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.actions;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.escape.Escaper;
import com.google.common.escape.Escapers;
import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
import com.google.devtools.build.lib.actions.MutableActionGraph.ActionConflictException;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.packages.OutputFile;
import com.google.devtools.build.lib.vfs.OsPathPolicy;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.SortedMap;
import javax.annotation.Nullable;
/**
* Helper class for actions.
*/
@ThreadSafe
public final class Actions {
private static final Escaper PATH_ESCAPER = Escapers.builder()
.addEscape('_', "_U")
.addEscape('/', "_S")
.addEscape('\\', "_B")
.addEscape(':', "_C")
.build();
/**
* Checks if the two actions are equivalent. This method exists to support sharing actions between
* configured targets for cases where there is no canonical target that could own the action. In
* the action graph construction this case shows up as two actions generating the same output
* file.
*
* <p>This method implements an equivalence relationship across actions, based on the action
* class, the key, and the list of inputs and outputs.
*/
public static boolean canBeShared(
ActionKeyContext actionKeyContext, ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
if (!a.isShareable() || !b.isShareable()) {
return false;
}
if (!a.getMnemonic().equals(b.getMnemonic())) {
return false;
}
// Non-Actions cannot be shared.
if (!(a instanceof Action) || !(b instanceof Action)) {
return false;
}
Action actionA = (Action) a;
Action actionB = (Action) b;
if (!actionA.getKey(actionKeyContext).equals(actionB.getKey(actionKeyContext))) {
return false;
}
// Don't bother to check input and output counts first; the expected result for these tests is
// to always be true (i.e., that this method returns true).
if (!artifactsEqualWithoutOwner(
actionA.getMandatoryInputs().toList(), actionB.getMandatoryInputs().toList())) {
return false;
}
if (!artifactsEqualWithoutOwner(actionA.getOutputs(), actionB.getOutputs())) {
return false;
}
return true;
}
private static boolean artifactsEqualWithoutOwner(
Iterable<Artifact> iterable1, Iterable<Artifact> iterable2) {
if (iterable1 instanceof Collection && iterable2 instanceof Collection) {
Collection<?> collection1 = (Collection<?>) iterable1;
Collection<?> collection2 = (Collection<?>) iterable2;
if (collection1.size() != collection2.size()) {
return false;
}
}
Iterator<Artifact> iterator1 = iterable1.iterator();
Iterator<Artifact> iterator2 = iterable2.iterator();
while (iterator1.hasNext()) {
if (!iterator2.hasNext()) {
return false;
}
Artifact artifact1 = iterator1.next();
Artifact artifact2 = iterator2.next();
if (!artifact1.equalsWithoutOwner(artifact2)) {
return false;
}
}
return !iterator2.hasNext();
}
/**
* Assigns generating action keys to artifacts, and finds action conflicts. An action conflict
* happens if two actions generate the same output artifact. Shared actions are not allowed. See
* {@link #canBeShared} for details. Should only be called for special action lookup values: does
* not handle normal configured targets. In particular, {@link
* GeneratingActions#getArtifactsByOutputLabel} will be empty.
*
* @param actions a list of actions to check for action conflict.
* @return a structure giving the actions, with a level of indirection.
* @throws ActionConflictException iff there are two actions generate the same output
*/
public static GeneratingActions assignOwnersAndFindAndThrowActionConflict(
ActionKeyContext actionKeyContext,
ImmutableList<ActionAnalysisMetadata> actions,
ActionLookupValue.ActionLookupKey actionLookupKey)
throws ActionConflictException {
return Actions.assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
actionKeyContext,
actions,
actionLookupKey,
/*allowSharedAction=*/ false,
/*outputFiles=*/ null);
}
/**
* Assigns generating action keys to artifacts and finds action conflicts. An action conflict
* happens if two actions generate the same output artifact. Shared actions are tolerated. See
* {@link #canBeShared} for details. Should be called by a configured target/aspect on the actions
* it owns. Should not be used for "global" checks of multiple configured targets: use {@link
* #findArtifactPrefixConflicts} for that.
*
* @param actions a list of actions to check for action conflicts, all generated by the same
* configured target/aspect.
* @return a structure giving the actions, with a level of indirection.
* @throws ActionConflictException iff there are two unshareable actions generating the same
* output
*/
public static GeneratingActions assignOwnersAndFilterSharedActionsAndThrowActionConflict(
ActionKeyContext actionKeyContext,
ImmutableList<ActionAnalysisMetadata> actions,
ActionLookupKey actionLookupKey,
@Nullable Collection<OutputFile> outputFiles)
throws ActionConflictException {
return Actions.assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
actionKeyContext, actions, actionLookupKey, /*allowSharedAction=*/ true, outputFiles);
}
private static void verifyGeneratingActionKeys(
Artifact.DerivedArtifact output,
ActionLookupData otherKey,
boolean allowSharedAction,
ActionKeyContext actionKeyContext,
ImmutableList<ActionAnalysisMetadata> actions)
throws ActionConflictException {
ActionLookupData firstKey = output.getGeneratingActionKey();
Preconditions.checkState(
firstKey.getActionLookupKey().equals(otherKey.getActionLookupKey()),
"Mismatched lookup keys? %s %s %s",
output,
firstKey,
otherKey);
int actionIndex = firstKey.getActionIndex();
int otherIndex = otherKey.getActionIndex();
if (actionIndex != otherIndex
&& (!allowSharedAction
|| !Actions.canBeShared(
actionKeyContext, actions.get(actionIndex), actions.get(otherIndex)))) {
throw new ActionConflictException(
actionKeyContext, output, actions.get(actionIndex), actions.get(otherIndex));
}
}
/**
* Checks {@code actions} for conflicts and sets each artifact's generating action key.
*
* <p>Conflicts can happen in one of two ways: the same artifact can be the output of multiple
* unshareable actions (or shareable actions if {@code allowSharedAction} is false), or two
* artifacts with the same execPath can be the outputs of different unshareable actions.
*
* <p>If {@code outputFiles} is non-null, also builds a map of output-file labels to artifacts,
* for use by output file configured targets when they are retrieving their artifacts from this
* associated rule configured target.
*/
private static GeneratingActions assignOwnersAndMaybeFilterSharedActionsAndThrowIfConflict(
ActionKeyContext actionKeyContext,
ImmutableList<ActionAnalysisMetadata> actions,
ActionLookupKey actionLookupKey,
boolean allowSharedAction,
@Nullable Collection<OutputFile> outputFiles)
throws ActionConflictException {
Map<PathFragment, Artifact.DerivedArtifact> seenArtifacts = new HashMap<>();
@Nullable ImmutableMap<String, Label> outputFileNames = null;
if (outputFiles != null && !outputFiles.isEmpty()) {
ImmutableMap.Builder<String, Label> outputFileNamesBuilder =
ImmutableMap.builderWithExpectedSize(outputFiles.size());
outputFiles.forEach(o -> outputFileNamesBuilder.put(o.getLabel().getName(), o.getLabel()));
outputFileNames = outputFileNamesBuilder.build();
}
@Nullable
ImmutableMap.Builder<Label, Artifact> artifactsByOutputLabel =
outputFileNames != null ? ImmutableMap.builderWithExpectedSize(outputFiles.size()) : null;
@Nullable Label label = actionLookupKey.getLabel();
@Nullable
PathFragment packageDirectory =
outputFileNames != null
? Preconditions.checkNotNull(label, actionLookupKey)
.getPackageIdentifier()
.getSourceRoot()
: null;
// Loop over the actions, looking at all outputs for conflicts.
int actionIndex = 0;
for (ActionAnalysisMetadata action : actions) {
ActionLookupData generatingActionKey = ActionLookupData.create(actionLookupKey, actionIndex);
for (Artifact artifact : action.getOutputs()) {
Artifact.DerivedArtifact output = (Artifact.DerivedArtifact) artifact;
// Has an artifact with this execPath been seen before?
Artifact.DerivedArtifact equalOutput =
seenArtifacts.putIfAbsent(output.getExecPath(), output);
if (equalOutput != null) {
// Yes: assert that its generating action and this artifact's are compatible.
verifyGeneratingActionKeys(
equalOutput, generatingActionKey, allowSharedAction, actionKeyContext, actions);
} else {
// No: populate the output label map with this artifact if applicable: if this
// artifact corresponds to a target that is an OutputFile with associated rule this label.
PathFragment rootRelativePath = output.getRootRelativePath();
if (packageDirectory != null && rootRelativePath.startsWith(packageDirectory)) {
PathFragment packageRelativePath = rootRelativePath.relativeTo(packageDirectory);
Label outputLabel = outputFileNames.get(packageRelativePath.getPathString());
if (outputLabel != null) {
artifactsByOutputLabel.put(outputLabel, artifact);
}
}
}
// Was this output already seen, so it has a generating action key set?
if (!output.hasGeneratingActionKey()) {
// Common case: artifact hasn't been seen before.
output.setGeneratingActionKey(generatingActionKey);
} else {
// Key is already set: verify that the generating action and this action are compatible.
verifyGeneratingActionKeys(
output, generatingActionKey, allowSharedAction, actionKeyContext, actions);
}
}
actionIndex++;
}
return new GeneratingActions(
actions,
artifactsByOutputLabel != null ? artifactsByOutputLabel.build() : ImmutableMap.of());
}
/**
* Returns a comparator for use with {@link #findArtifactPrefixConflicts(ActionGraph, SortedMap,
* boolean)}.
*/
public static Comparator<PathFragment> comparatorForPrefixConflicts() {
return PathFragmentPrefixComparator.INSTANCE;
}
private static class PathFragmentPrefixComparator implements Comparator<PathFragment> {
private static final PathFragmentPrefixComparator INSTANCE = new PathFragmentPrefixComparator();
@Override
public int compare(PathFragment lhs, PathFragment rhs) {
// We need to use the OS path policy in case the OS is case insensitive.
OsPathPolicy os = OsPathPolicy.getFilePathOs();
String str1 = lhs.getPathString();
String str2 = rhs.getPathString();
int len1 = str1.length();
int len2 = str2.length();
int n = Math.min(len1, len2);
for (int i = 0; i < n; ++i) {
char c1 = str1.charAt(i);
char c2 = str2.charAt(i);
int res = os.compare(c1, c2);
if (res != 0) {
if (c1 == PathFragment.SEPARATOR_CHAR) {
return -1;
} else if (c2 == PathFragment.SEPARATOR_CHAR) {
return 1;
}
return res;
}
}
return len1 - len2;
}
}
/**
* Finds Artifact prefix conflicts between generated artifacts. An artifact prefix conflict
* happens if one action generates an artifact whose path is a prefix of another artifact's path.
* Those two artifacts cannot exist simultaneously in the output tree.
*
* @param actionGraph the {@link ActionGraph} to query for artifact conflicts
* @param artifactPathMap a map mapping generated artifacts to their exec paths. The map must be
* sorted using the comparator from {@link #comparatorForPrefixConflicts()}.
* @param strictConflictChecks report path prefix conflicts, regardless of
* shouldReportPathPrefixConflict().
* @return A map between actions that generated the conflicting artifacts and their associated
* {@link ArtifactPrefixConflictException}.
*/
public static Map<ActionAnalysisMetadata, ArtifactPrefixConflictException>
findArtifactPrefixConflicts(
ActionGraph actionGraph,
SortedMap<PathFragment, Artifact> artifactPathMap,
boolean strictConflictChecks) {
// You must construct the sorted map using this comparator for the algorithm to work.
// The algorithm requires subdirectories to immediately follow parent directories,
// before any files in that directory.
// Example: "foo", "foo.obj", foo/bar" must be sorted
// "foo", "foo/bar", foo.obj"
Preconditions.checkArgument(
artifactPathMap.comparator() instanceof PathFragmentPrefixComparator,
"artifactPathMap must be sorted with PathFragmentPrefixComparator");
// No actions in graph -- currently happens only in tests. Special-cased because .next() call
// below is unconditional.
if (artifactPathMap.isEmpty()) {
return ImmutableMap.<ActionAnalysisMetadata, ArtifactPrefixConflictException>of();
}
// Keep deterministic ordering of bad actions.
Map<ActionAnalysisMetadata, ArtifactPrefixConflictException> badActions = new LinkedHashMap<>();
Iterator<PathFragment> iter = artifactPathMap.keySet().iterator();
// Report an error for every derived artifact which is a prefix of another.
// If x << y << z (where x << y means "y starts with x"), then we only report (x,y), (x,z), but
// not (y,z).
for (PathFragment pathJ = iter.next(); iter.hasNext(); ) {
// For each comparison, we have a prefix candidate (pathI) and a suffix candidate (pathJ).
// At the beginning of the loop, we set pathI to the last suffix candidate, since it has not
// yet been tested as a prefix candidate, and then set pathJ to the paths coming after pathI,
// until we come to one that does not contain pathI as a prefix. pathI is then verified not to
// be the prefix of any path, so we start the next run of the loop.
PathFragment pathI = pathJ;
// Compare pathI to the paths coming after it.
while (iter.hasNext()) {
pathJ = iter.next();
if (pathJ.startsWith(pathI)) { // prefix conflict.
Artifact artifactI = Preconditions.checkNotNull(artifactPathMap.get(pathI), pathI);
Artifact artifactJ = Preconditions.checkNotNull(artifactPathMap.get(pathJ), pathJ);
// We ignore the artifact prefix conflict between a TreeFileArtifact and its parent
// TreeArtifact.
// We can only have such a conflict here if:
// 1. The TreeArtifact is generated by an ActionTemplate. And the TreeFileArtifact is
// generated by an expanded action created at execution time from the ActionTemplate.
// 2. This is an incremental build with invalidated configured targets. In this case,
// the action graph contains expanded actions from previous builds and they will be
// checked for artifact conflicts.
if (artifactJ.hasParent() && artifactJ.getParent().equals(artifactI)) {
continue;
}
ActionAnalysisMetadata actionI =
Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactI), artifactI);
ActionAnalysisMetadata actionJ =
Preconditions.checkNotNull(actionGraph.getGeneratingAction(artifactJ), artifactJ);
if (strictConflictChecks || actionI.shouldReportPathPrefixConflict(actionJ)) {
ArtifactPrefixConflictException exception = new ArtifactPrefixConflictException(pathI,
pathJ, actionI.getOwner().getLabel(), actionJ.getOwner().getLabel());
badActions.put(actionI, exception);
badActions.put(actionJ, exception);
}
} else { // pathJ didn't have prefix pathI, so no conflict possible for pathI.
break;
}
}
}
return ImmutableMap.copyOf(badActions);
}
/**
* Returns the escaped name for a given relative path as a string. This takes
* a short relative path and turns it into a string suitable for use as a
* filename. Invalid filename characters are escaped with an '_' + a single
* character token.
*/
public static String escapedPath(String path) {
return PATH_ESCAPER.escape(path);
}
/**
* Returns a string that is usable as a unique path component for a label. It is guaranteed
* that no other label maps to this string.
*/
public static String escapeLabel(Label label) {
return PATH_ESCAPER.escape(label.getPackageName() + ":" + label.getName());
}
/**
* Container class for actions, ensuring they have already been checked for conflicts and their
* generated artifacts have had owners assigned.
*/
public static class GeneratingActions {
public static final GeneratingActions EMPTY =
new GeneratingActions(ImmutableList.of(), ImmutableMap.of());
private final ImmutableList<ActionAnalysisMetadata> actions;
private final ImmutableMap<Label, Artifact> artifactsByOutputLabel;
private GeneratingActions(
ImmutableList<ActionAnalysisMetadata> actions,
ImmutableMap<Label, Artifact> artifactsByOutputLabel) {
this.actions = actions;
this.artifactsByOutputLabel = artifactsByOutputLabel;
}
/** Used only for the workspace status action. Does not handle duplicate artifacts. */
public static GeneratingActions fromSingleAction(
ActionAnalysisMetadata action, ActionLookupValue.ActionLookupKey actionLookupKey) {
Preconditions.checkState(actionLookupKey.getLabel() == null, actionLookupKey);
ActionLookupData generatingActionKey = ActionLookupData.create(actionLookupKey, 0);
for (Artifact output : action.getOutputs()) {
((Artifact.DerivedArtifact) output).setGeneratingActionKey(generatingActionKey);
}
return new GeneratingActions(ImmutableList.of(action), ImmutableMap.of());
}
public ImmutableList<ActionAnalysisMetadata> getActions() {
return actions;
}
public ImmutableMap<Label, Artifact> getArtifactsByOutputLabel() {
return artifactsByOutputLabel;
}
}
}