| // 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.skyframe; |
| |
| import com.google.common.collect.ImmutableSet; |
| import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; |
| import com.google.devtools.build.lib.supplier.InterruptibleSupplier; |
| import com.google.devtools.build.lib.supplier.MemoizingInterruptibleSupplier; |
| import com.google.devtools.build.lib.util.GroupedList; |
| import com.google.devtools.build.skyframe.NodeEntry.DirtyType; |
| import com.google.errorprone.annotations.CanIgnoreReturnValue; |
| import java.util.Map; |
| import java.util.Set; |
| import javax.annotation.Nullable; |
| |
| /** |
| * A graph that exposes its entries and structure, for use by classes that must traverse it. |
| * |
| * <p>Certain graph implementations can throw {@link InterruptedException} when trying to retrieve |
| * node entries. Such exceptions should not be caught locally -- they should be allowed to propagate |
| * up. |
| */ |
| @ThreadSafe |
| public interface QueryableGraph { |
| |
| /** |
| * Returns the node with the given {@code key}, or {@code null} if the node does not exist. |
| * |
| * @param requestor if non-{@code null}, the node on behalf of which {@code key} is being |
| * requested. |
| * @param reason the reason the node is being requested. |
| */ |
| @Nullable |
| NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key) throws InterruptedException; |
| |
| /** |
| * Fetches all the given nodes. Returns a {@link NodeBatch} {@code b} such that, for all {@code k} |
| * in {@code keys}, {@code b.get(k) == get(k)}. |
| * |
| * <p>Prefer calling this method over {@link #getBatchMap} if it is not necessary to represent the |
| * result as a {@link Map}, as it may be significantly more efficient. |
| * |
| * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are |
| * being requested. |
| * @param reason the reason the nodes are being requested. |
| */ |
| default NodeBatch getBatch( |
| @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) |
| throws InterruptedException { |
| return getBatchMap(requestor, reason, keys)::get; |
| } |
| |
| /** A hint about the most efficient way to look up a key in the graph. */ |
| enum LookupHint { |
| INDIVIDUAL, |
| BATCH |
| } |
| |
| /** |
| * Hints to the caller about the most efficient way to look up a key in this graph. |
| * |
| * <p>A return of {@link LookupHint#INDIVIDUAL} indicates that the given key can efficiently be |
| * looked up by calling {@link #get}. In such a case, it is not worth the effort to aggregate the |
| * key into a collection with other keys for a {@link #getBatch} call. |
| * |
| * <p>A return of {@link LookupHint#BATCH} indicates that the given key should ideally be |
| * requested with other keys as part of a call to {@link #getBatch}. This may be the case if, for |
| * example, the corresponding node is stored remotely, and requesting keys in a single batch |
| * reduces trips to remote storage. |
| */ |
| LookupHint getLookupHint(SkyKey key); |
| |
| /** |
| * A version of {@link #getBatch} that returns an {@link InterruptibleSupplier} to possibly |
| * retrieve the results later. |
| */ |
| @CanIgnoreReturnValue |
| default InterruptibleSupplier<NodeBatch> getBatchAsync( |
| @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) { |
| return MemoizingInterruptibleSupplier.of(() -> getBatch(requestor, reason, keys)); |
| } |
| |
| /** |
| * Fetches all the given nodes. Returns a map {@code m} such that, for all {@code k} in {@code |
| * keys}, {@code m.get(k) == get(k)} and {@code !m.containsKey(k)} iff {@code get(k) == null}. |
| * |
| * <p>Prefer calling {@link #getBatch} over this method if it is not necessary to represent the |
| * result as a {@link Map}, as it may be significantly more efficient. |
| * |
| * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are |
| * being requested. |
| * @param reason the reason the nodes are being requested. |
| */ |
| Map<SkyKey, ? extends NodeEntry> getBatchMap( |
| @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) |
| throws InterruptedException; |
| |
| /** |
| * A version of {@link #getBatchMap} that returns an {@link InterruptibleSupplier} to possibly |
| * retrieve the results later. |
| */ |
| @CanIgnoreReturnValue |
| default InterruptibleSupplier<Map<SkyKey, ? extends NodeEntry>> getBatchMapAsync( |
| @Nullable SkyKey requestor, Reason reason, Iterable<? extends SkyKey> keys) { |
| return MemoizingInterruptibleSupplier.of(() -> getBatchMap(requestor, reason, keys)); |
| } |
| |
| /** |
| * Optimistically prefetches dependencies. |
| * |
| * @param requestor the key whose deps to fetch |
| * @param oldDeps deps from the previous build |
| * @param previouslyRequestedDeps deps that have already been requested during this build and |
| * should not be prefetched because they will be subsequently fetched anyway |
| * @return {@code previouslyRequestedDeps} as a set if the implementation called {@link |
| * GroupedList#toSet} (so that the caller may reuse it), otherwise {@code null} |
| */ |
| @Nullable |
| default ImmutableSet<SkyKey> prefetchDeps( |
| SkyKey requestor, Set<SkyKey> oldDeps, GroupedList<SkyKey> previouslyRequestedDeps) |
| throws InterruptedException { |
| return null; |
| } |
| |
| default ImmutableSet<SkyKey> getAllKeysForTesting() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * The reason that a node is being looked up in the Skyframe graph. |
| * |
| * <p>Alternate graph implementations may wish to make use of this information. |
| */ |
| enum Reason { |
| /** |
| * The node is being fetched in order to see if it needs to be evaluated or because it was just |
| * evaluated, but *not* because it was just requested during evaluation of a SkyFunction |
| * (see {@link #DEP_REQUESTED}). |
| */ |
| PRE_OR_POST_EVALUATION, |
| |
| /** |
| * The node is being looked up as part of the prefetch step before evaluation of a SkyFunction. |
| */ |
| PREFETCH, |
| |
| /** |
| * The node is being fetched because it is about to be evaluated, but *not* because it was just |
| * requested during evaluation of a SkyFunction (see {@link #DEP_REQUESTED}). |
| */ |
| EVALUATION, |
| |
| /** The node is being looked up because it was requested during evaluation of a SkyFunction. */ |
| DEP_REQUESTED, |
| |
| /** The node is being looked up during the invalidation phase of Skyframe evaluation. */ |
| INVALIDATION, |
| |
| /** The node is being looked up during the cycle checking phase of Skyframe evaluation. */ |
| CYCLE_CHECKING, |
| |
| /** The node is being looked up so that an rdep can be added to it. */ |
| RDEP_ADDITION, |
| |
| /** The node is being looked up so that an rdep can be removed from it. */ |
| RDEP_REMOVAL, |
| |
| /** The node is being looked up for any graph clean-up effort that may be necessary. */ |
| CLEAN_UP, |
| |
| /** The node is being looked up so it can be enqueued for evaluation or change pruning. */ |
| ENQUEUING_CHILD, |
| |
| /** |
| * The node is being looked up so that it can be signaled that a dependency is now complete. |
| */ |
| SIGNAL_DEP, |
| |
| /** |
| * The node is being looking up as part of the error bubbling phase of fail-fast Skyframe |
| * evaluation. |
| */ |
| ERROR_BUBBLING, |
| |
| /** The node is being looked up merely for an existence check. */ |
| EXISTENCE_CHECKING, |
| |
| /** The node is being looked up merely to see if it is done or not. */ |
| DONE_CHECKING, |
| |
| /** |
| * The node is being looked up so that it can be {@linkplain DirtyType#FORCE_REBUILD force |
| * rebuilt} by rewinding. |
| */ |
| REWINDING, |
| |
| /** |
| * The node is being looked up to service {@link WalkableGraph#getValue}, |
| * {@link WalkableGraph#getException}, {@link WalkableGraph#getMissingAndExceptions}, or |
| * {@link WalkableGraph#getSuccessfulValues}. |
| */ |
| WALKABLE_GRAPH_VALUE, |
| |
| /** The node is being looked up to service {@link WalkableGraph#getDirectDeps}. */ |
| WALKABLE_GRAPH_DEPS, |
| |
| /** The node is being looked up to service {@link WalkableGraph#getReverseDeps}. */ |
| WALKABLE_GRAPH_RDEPS, |
| |
| /** The node is being looked up to service {@link WalkableGraph#getValueAndRdeps}. */ |
| WALKABLE_GRAPH_VALUE_AND_RDEPS, |
| |
| /** The node is being looked up to service another "graph lookup" function. */ |
| WALKABLE_GRAPH_OTHER, |
| |
| /** Some other reason than one of the above that needs the node's value and deps. */ |
| OTHER_NEEDING_VALUE_AND_DEPS, |
| |
| /** Some other reason than one of the above that needs the node's reverse deps. */ |
| OTHER_NEEDING_REVERSE_DEPS, |
| |
| /** Some other reason than one of the above that needs the node's value and reverse deps. */ |
| OTHER_NEEDING_VALUE_AND_REVERSE_DEPS, |
| |
| /** Some other reason than one of the above. */ |
| OTHER; |
| |
| public boolean isWalkable() { |
| return this == WALKABLE_GRAPH_VALUE |
| || this == WALKABLE_GRAPH_DEPS |
| || this == WALKABLE_GRAPH_RDEPS |
| || this == WALKABLE_GRAPH_VALUE_AND_RDEPS |
| || this == WALKABLE_GRAPH_OTHER; |
| } |
| } |
| } |