aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/main/java/com/google/devtools/build/lib/actions/Actions.java
blob: 8a49af4bade626d91349e953dd932f18ec14602d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
// 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.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Iterables;
import com.google.common.escape.Escaper;
import com.google.common.escape.Escapers;
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.util.Preconditions;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
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(ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
    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().equals(actionB.getKey())) {
      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 (!Iterables.elementsEqual(actionA.getMandatoryInputs(), actionB.getMandatoryInputs())) {
      return false;
    }
    if (!Iterables.elementsEqual(actionA.getOutputs(), actionB.getOutputs())) {
      return false;
    }
    return true;
  }

  /**
   * Finds action conflicts. An action conflict happens if two actions generate the same output
   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
   *
   * @param actions a list of actions to check for action conflicts
   * @return a structure giving the mapping between artifacts and generating actions, with a level
   *     of indirection.
   * @throws ActionConflictException iff there are two actions generate the same output
   */
  public static GeneratingActions findAndThrowActionConflict(List<ActionAnalysisMetadata> actions)
      throws ActionConflictException {
    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
        actions, /*allowSharedAction=*/ false);
  }

  /**
   * Finds action conflicts. An action conflict happens if two actions generate the same output
   * artifact. Shared actions are tolerated. See {@link #canBeShared} for details.
   *
   * @param actions a list of actions to check for action conflicts
   * @return a structure giving the mapping between artifacts and generating actions, with a level
   *     of indirection.
   * @throws ActionConflictException iff there are two unshareable actions generating the same
   *     output
   */
  public static GeneratingActions filterSharedActionsAndThrowActionConflict(
      List<ActionAnalysisMetadata> actions) throws ActionConflictException {
    return Actions.maybeFilterSharedActionsAndThrowIfConflict(
        actions, /*allowSharedAction=*/ true);
  }

  private static GeneratingActions maybeFilterSharedActionsAndThrowIfConflict(
      List<ActionAnalysisMetadata> actions, boolean allowSharedAction)
      throws ActionConflictException {
    Map<Artifact, Integer> generatingActions = new HashMap<>();
    int actionIndex = 0;
    for (ActionAnalysisMetadata action : actions) {
      for (Artifact artifact : action.getOutputs()) {
        Integer previousIndex = generatingActions.put(artifact, actionIndex);
        if (previousIndex != null && previousIndex != actionIndex) {
          if (!allowSharedAction || !Actions.canBeShared(actions.get(previousIndex), action)) {
            throw new ActionConflictException(artifact, actions.get(previousIndex), action);
          }
        }
      }
      actionIndex++;
    }
    return new GeneratingActions(actions, ImmutableMap.copyOf(generatingActions));
  }

  /**
   * 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 generatingActions a map between generated artifacts and their associated generating
   *     actions.
   * @return a map between actions that generated the conflicting artifacts and their associated
   *     {@link ArtifactPrefixConflictException}.
   */
  public static Map<ActionAnalysisMetadata, ArtifactPrefixConflictException>
      findArtifactPrefixConflicts(Map<Artifact, ActionAnalysisMetadata> generatingActions) {
    TreeMap<PathFragment, Artifact> artifactPathMap = new TreeMap();
    for (Artifact artifact : generatingActions.keySet()) {
      artifactPathMap.put(artifact.getExecPath(), artifact);
    }

    return findArtifactPrefixConflicts(
        new MapBasedImmutableActionGraph(generatingActions), artifactPathMap);
  }

  /**
   * 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
   * @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) {
    // 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 (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());
  }

  private static class MapBasedImmutableActionGraph implements ActionGraph {
    private final Map<Artifact, ActionAnalysisMetadata> generatingActions;

    MapBasedImmutableActionGraph(
        Map<Artifact, ActionAnalysisMetadata> generatingActions) {
      this.generatingActions = ImmutableMap.copyOf(generatingActions);
    }

    @Nullable
    public ActionAnalysisMetadata getGeneratingAction(Artifact artifact) {
      return generatingActions.get(artifact);
    }
  }

  /** Container class for actions and the artifacts they generate. */
  @VisibleForTesting
  public static class GeneratingActions {
    private final List<ActionAnalysisMetadata> actions;
    private final ImmutableMap<Artifact, Integer> generatingActionIndex;

    @VisibleForTesting
    public GeneratingActions(
        List<ActionAnalysisMetadata> actions,
        ImmutableMap<Artifact, Integer> generatingActionIndex) {
      this.actions = actions;
      this.generatingActionIndex = generatingActionIndex;
    }

    public ImmutableMap<Artifact, Integer> getGeneratingActionIndex() {
      return generatingActionIndex;
    }

    public List<ActionAnalysisMetadata> getActions() {
      return actions;
    }
  }
}