src/main/java/com/google/devtools/build/skyframe/SkyFunction.java - bazel - Git at Google

 // 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.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.graph.GraphBuilder;
 import com.google.common.graph.ImmutableGraph;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.util.GroupedList;
 import java.util.List;
 import java.util.Map;
 import javax.annotation.Nullable;

 /**
  * Machinery to evaluate a single value.
  *
  * <p>The SkyFunction {@link #compute} implementation is supposed to access only direct dependencies
  * of the value. However, the direct dependencies need not be known in advance. The implementation
  * can request arbitrary values using {@link Environment#getValue}. If the values are not ready, the
  * call will return {@code null}; in that case the implementation should just return {@code null},
  * in which case the missing dependencies will be computed and the {@link #compute} method will be
  * started again.
  */
 public interface SkyFunction {

   /**
    * When a value is requested, this method is called with the name of the value and a
    * dependency-tracking environment.
    *
    * <p>This method should return a non-{@code null} value, or {@code null} if any dependencies were
    * missing ({@link Environment#valuesMissing} was true before returning). In that case the missing
    * dependencies will be computed and the {@code compute} method called again.
    *
    * <p>This method should throw if it fails, or if one of its dependencies fails with an exception
    * and this method cannot recover. If one of its dependencies fails and this method can enrich the
    * exception with additional context, then this method should catch that exception and throw
    * another containing that additional context. If it has no such additional context, then it
    * should allow its dependency's exception to be thrown through it.
    *
    * <p>This method may return {@link Restart} in rare circumstances. See its docs. Do not return
    * values of this type unless you know exactly what you are doing.
    *
    * <p>If version information is discovered for the given {@code skyKey}, {@link
    * Environment#injectVersionForNonHermeticFunction(Version)} may be called on {@code env}.
    *
    * @throws SkyFunctionException on failure
    * @throws InterruptedException if interrupted
    */
   @ThreadSafe
   @Nullable
   SkyValue compute(SkyKey skyKey, Environment env)
       throws SkyFunctionException, InterruptedException;

   /**
    * Extracts a tag (target label) from a SkyKey if it has one. Otherwise return {@code null}.
    *
    * <p>The tag is used for filtering out non-error event messages that do not match --output_filter
    * flag. If a SkyFunction returns {@code null} in this method it means that all the info/warning
    * messages associated with this value will be shown, no matter what --output_filter says.
    */
   @Nullable
   String extractTag(SkyKey skyKey);

   /**
    * Sentinel {@link SkyValue} type for {@link #compute} to return, indicating that something went
    * wrong, and that the evaluation returning this value must be restarted, and the nodes associated
    * with other keys in {@link #rewindGraph()} (whose directed edges should correspond to the nodes'
    * direct dependencies) must also be restarted.
    *
    * <p>An intended cause for returning this is external data loss; e.g., if a dependency's
    * "done-ness" is intended to mean that certain data is available in an external system, but
    * during evaluation of a node that depends on that external data, that data has gone missing, and
    * reevaluation of the dependency is expected to repair the discrepancy.
    *
    * <p>Values of this type will <em>never</em> be returned by {@link Environment}'s getValue
    * methods or from {@link NodeEntry#getValue()}.
    *
    * <p>All {@link ListenableFuture}s used in calls to {@link Environment#dependOnFuture} which were
    * not already complete will be cancelled.
    *
    * <p>This may only be returned by {@link #compute} if {@link Environment#restartPermitted} is
    * true. If restarting is not permitted, {@link #compute} should throw an appropriate {@link
    * SkyFunctionException}.
    */
   interface Restart extends SkyValue {
     ImmutableGraph<SkyKey> EMPTY_SKYKEY_GRAPH =
         ImmutableGraph.copyOf(GraphBuilder.directed().allowsSelfLoops(false).build());

     Restart SELF = () -> EMPTY_SKYKEY_GRAPH;

     static Restart selfAnd(ImmutableGraph<SkyKey> rewindGraph) {
       Preconditions.checkArgument(
           rewindGraph.isDirected(), "rewindGraph undirected: %s", rewindGraph);
       Preconditions.checkArgument(
           !rewindGraph.allowsSelfLoops(), "rewindGraph allows self loops: %s", rewindGraph);
       return () -> rewindGraph;
     }

     ImmutableGraph<SkyKey> rewindGraph();
   }

   /**
    * The services provided to the {@link SkyFunction#compute} implementation by the Skyframe
    * evaluation framework.
    */
   interface Environment {
     /**
      * Returns a direct dependency. If the specified value is not in the set of already evaluated
      * direct dependencies, returns {@code null}. Also returns {@code null} if the specified value
      * has already been evaluated and found to be in error.
      *
      * <p>On a subsequent evaluation, if any of this value's dependencies have changed they will be
      * re-evaluated in the same order as originally requested by the {@code SkyFunction} using this
      * {@code getValue} call (see {@link #getValues} for when preserving the order is not
      * important).
      *
      * <p>This method and the ones below may throw {@link InterruptedException}. Such exceptions
      * must not be caught by the {@link SkyFunction#compute} implementation. Instead, they should be
      * propagated up to the caller of {@link SkyFunction#compute}.
      */
     @Nullable
     SkyValue getValue(SkyKey valueName) throws InterruptedException;

     /**
      * Returns a direct dependency. If the specified value is not in the set of already evaluated
      * direct dependencies, returns {@code null}. If the specified value has already been evaluated
      * and found to be in error, throws the exception coming from the error, so long as the
      * exception is of one of the specified types. SkyFunction implementations may use this method
      * to continue evaluation even if one of their dependencies is in error by catching the thrown
      * exception and proceeding. The caller must specify the exception type(s) that might be thrown
      * using the {@code exceptionClass} argument(s). If the dependency's exception is not an
      * instance of {@code exceptionClass}, {@code null} is returned.
      *
      * <p>The exception class given cannot be a supertype or a subtype of {@link RuntimeException},
      * or a subtype of {@link InterruptedException}. See {@link
      * SkyFunctionException#validateExceptionType} for details.
      */
     @Nullable
     <E extends Exception> SkyValue getValueOrThrow(SkyKey depKey, Class<E> exceptionClass)
         throws E, InterruptedException;

     @Nullable
     <E1 extends Exception, E2 extends Exception> SkyValue getValueOrThrow(
         SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
         throws E1, E2, InterruptedException;

     @Nullable
     <E1 extends Exception, E2 extends Exception, E3 extends Exception> SkyValue getValueOrThrow(
         SkyKey depKey,
         Class<E1> exceptionClass1,
         Class<E2> exceptionClass2,
         Class<E3> exceptionClass3)
         throws E1, E2, E3, InterruptedException;

     @Nullable
     <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
         SkyValue getValueOrThrow(
             SkyKey depKey,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4)
             throws E1, E2, E3, E4, InterruptedException;

     @Nullable
     <
             E1 extends Exception,
             E2 extends Exception,
             E3 extends Exception,
             E4 extends Exception,
             E5 extends Exception>
         SkyValue getValueOrThrow(
             SkyKey depKey,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4,
             Class<E5> exceptionClass5)
             throws E1, E2, E3, E4, E5, InterruptedException;

     /**
      * Requests {@code depKeys} "in parallel", independent of each others' values. These keys may be
      * thought of as a "dependency group" -- they are requested together by this value.
      *
      * <p>In general, if the result of one getValue call can affect the argument of a later getValue
      * call, the two calls cannot be merged into a single getValues call, since the result of the
      * first call might change on a later evaluation. Inversely, if the result of one getValue call
      * cannot affect the parameters of the next getValue call, the two keys can form a dependency
      * group and the two getValue calls should be merged into one getValues call. In the latter
      * case, if we fail to combine the _multiple_ getValue (or getValues) calls into one _single_
      * getValues call, it would result in multiple dependency groups with an implicit ordering
      * between them. This would unnecessarily cause sequential evaluations of these groups and could
      * impact overall performance.
      *
      * <p>On subsequent evaluations, when checking to see if dependencies require re-evaluation, all
      * the values within one group may be simultaneously checked. A SkyFunction should request a
      * dependency group if checking the deps serially on a subsequent evaluation would take too
      * long, and if the {@link #compute} method would request all deps anyway as long as no earlier
      * deps had changed. SkyFunction.Environment implementations may also choose to request these
      * deps in parallel on the first evaluation, potentially speeding it up.
      *
      * <p>While re-evaluating every value in the group may take longer than re-evaluating just the
      * first one and finding that it has changed, no extra work is done: the contract of the
      * dependency group means that the {@link #compute} method, when called to re-evaluate this
      * value, will request all values in the group again anyway, so they would have to have been
      * built in any case.
      *
      * <p>Example of when to use getValues: A ListProcessor value is built with key inputListRef.
      * The {@link #compute} method first calls getValue(InputList.key(inputListRef)), and retrieves
      * inputList. It then iterates through inputList, calling getValue on each input. Finally, it
      * processes the whole list and returns. Say inputList is (a, b, c). Since the {@link #compute}
      * method will unconditionally call getValue(a), getValue(b), and getValue (c), the {@link
      * #compute} method can instead just call getValues({a, b, c}). If the value is later dirtied
      * the evaluator will evaluate a, b, and c in parallel (assuming the inputList value was
      * unchanged), and re-evaluate the ListProcessor value only if at least one of them was changed.
      * On the other hand, if the InputList changes to be (a, b, d), then the evaluator will see that
      * the first dep has changed, and call the {@link #compute} method to re-evaluate from scratch,
      * without considering the dep group of {a, b, c}.
      *
      * <p>Example of when not to use getValues: A BestMatch value is built with key
      * &lt;potentialMatchesRef, matchCriterion&gt;. The {@link #compute} method first calls
      * getValue(PotentialMatches.key(potentialMatchesRef) and retrieves potentialMatches. It then
      * iterates through potentialMatches, calling getValue on each potential match until it finds
      * one that satisfies matchCriterion. In this case, if potentialMatches is (a, b, c), it would
      * be <i>incorrect</i> to call getValues({a, b, c}), because it is not known yet whether
      * requesting b or c will be necessary -- if a matches, then we will never call b or c.
      *
      * <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.containsKey(k)}
      * is {@code true}, and, {@code m.get(k) != null} iff the dependency was already evaluated and
      * was not in error.
      */
     Map<SkyKey, SkyValue> getValues(Iterable<? extends SkyKey> depKeys) throws InterruptedException;

     /**
      * Similar to getValues, but instead of returning a {@code Map<SkyKey, SkyValue>}, returns a
      * {@code List<SkyValue>} in the order of the input {@code Iterable<SkyKey>}. b/172462551
      */
     List<SkyValue> getOrderedValues(Iterable<? extends SkyKey> depKeys) throws InterruptedException;

     /**
      * Similar to {@link #getValues} but allows the caller to specify a set of types that are proper
      * subtypes of Exception (see {@link SkyFunctionException} for more details) to find out whether
      * any of the dependencies' evaluations resulted in exceptions of those types. The returned
      * objects may throw when attempting to retrieve their value.
      *
      * <p>Callers should prioritize their responsibility to detect and handle errors in the returned
      * map over their responsibility to return {@code null} if values are missing. This is because
      * in nokeep_going evaluations, an error from a low level dependency is given a chance to be
      * enriched by its reverse-dependencies, if possible. Callers should also prioritize throwing
      * exceptions over checking for {@link InterruptedException}, since during the error-bubbling
      * enrichment process, the SkyFunction is interrupted after it has received the exception to
      * prevent it from doing too much unnecessary work.
      *
      * <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.get(k) != null}.
      * For all {@code v} such that there is some {@code k} such that {@code m.get(k) == v}, the
      * following is true: {@code v.get() != null} iff the dependency {@code k} was already evaluated
      * and was not in error. {@code v.get()} throws {@code E} iff the dependency {@code k} was
      * already evaluated with an error in the specified set of {@link Exception} types.
      */
     <E extends Exception> Map<SkyKey, ValueOrException<E>> getValuesOrThrow(
         Iterable<? extends SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException;

     <E1 extends Exception, E2 extends Exception>
         Map<SkyKey, ValueOrException2<E1, E2>> getValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2)
             throws InterruptedException;

     <E1 extends Exception, E2 extends Exception, E3 extends Exception>
         Map<SkyKey, ValueOrException3<E1, E2, E3>> getValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3)
             throws InterruptedException;

     <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
         Map<SkyKey, ValueOrException4<E1, E2, E3, E4>> getValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4)
             throws InterruptedException;

     <
             E1 extends Exception,
             E2 extends Exception,
             E3 extends Exception,
             E4 extends Exception,
             E5 extends Exception>
         Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4,
             Class<E5> exceptionClass5)
             throws InterruptedException;

     /**
      * Similar to getValuesOrThrow, but instead of returning a {@code Map<SkyKey,
      * ValueOrException>}, returns a {@code List<SkyValue>} in the order of the input {@code
      * Iterable<SkyKey>}.
      */
     <E extends Exception> List<ValueOrException<E>> getOrderedValuesOrThrow(
         Iterable<? extends SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException;

     <E1 extends Exception, E2 extends Exception>
         List<ValueOrException2<E1, E2>> getOrderedValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2)
             throws InterruptedException;

     <E1 extends Exception, E2 extends Exception, E3 extends Exception>
         List<ValueOrException3<E1, E2, E3>> getOrderedValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3)
             throws InterruptedException;

     <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
         List<ValueOrException4<E1, E2, E3, E4>> getOrderedValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4)
             throws InterruptedException;

     <
             E1 extends Exception,
             E2 extends Exception,
             E3 extends Exception,
             E4 extends Exception,
             E5 extends Exception>
         List<ValueOrException5<E1, E2, E3, E4, E5>> getOrderedValuesOrThrow(
             Iterable<? extends SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4,
             Class<E5> exceptionClass5)
             throws InterruptedException;

     /**
      * Returns whether there was a previous getValue[s][OrThrow] that indicated a missing
      * dependency. Formally, returns true iff at least one of the following occurred:
      *
      * <ul>
      *   <li>getValue[OrThrow](k[, c]) returned {@code null} for some k
      *   <li>getValues(ks).get(k) == {@code null} for some ks and k such that ks.contains(k)
      *   <li>getValuesOrThrow(ks, c).get(k).get() == {@code null} for some ks and k such that
      *       ks.contains(k)
      * </ul>
      *
      * <p>If this returns true, the {@link SkyFunction} must return {@code null} or throw a {@link
      * SkyFunctionException} if it detected an error even with values missing.
      */
     boolean valuesMissing();

     /**
      * Returns the {@link ExtendedEventHandler} that a SkyFunction should use to print any errors,
      * warnings, or progress messages during execution of {@link SkyFunction#compute}.
      */
     ExtendedEventHandler getListener();

     /**
      * A live view of deps known to have already been requested either through an earlier call to
      * {@link SkyFunction#compute} or inferred during change pruning. Should return {@code null} if
      * unknown. Only for special use cases: do not use in general unless you know exactly what
      * you're doing!
      */
     @Nullable
     default GroupedList<SkyKey> getTemporaryDirectDeps() {
       return null;
     }

     /**
      * Injects non-hermetic {@link Version} information for this environment.
      *
      * <p>This may be called during the course of {@link SkyFunction#compute(SkyKey, Environment)}
      * if the function discovers version information for the {@link SkyKey}.
      *
      * <p>Environments that either do not need or wish to ignore non-hermetic version information
      * may keep the default no-op implementation.
      */
     default void injectVersionForNonHermeticFunction(Version version) {}

     /**
      * Register dependencies on keys without necessarily requiring their values.
      *
      * <p>WARNING: Dependencies here MUST be done! Only use this function if you know what you're
      * doing.
      *
      * <p>If the {@link EvaluationVersionBehavior} is {@link
      * EvaluationVersionBehavior#MAX_CHILD_VERSIONS} then this method may fall back to just doing a
      * {@link #getValues} call internally. Thus, any graph evaluations that require this method to
      * be performant <i>must</i> run with {@link EvaluationVersionBehavior#GRAPH_VERSION}.
      */
     default void registerDependencies(Iterable<SkyKey> keys) throws InterruptedException {
       getValues(keys);
     }

     /** Returns whether we are currently in error bubbling. */
     @VisibleForTesting
     boolean inErrorBubblingForTesting();

     /**
      * Adds a dependency on a Skyframe-external event. If the given future is already complete, this
      * method silently returns without doing anything (to avoid unnecessary function restarts).
      * Otherwise, Skyframe adds a listener to the passed-in future, and only re-enqueues the current
      * node after the future completes and all requested deps are done. The added listener will
      * perform the minimum amount of work on the thread completing the future necessary for Skyframe
      * bookkeeping.
      *
      * <p>Callers of this method must check {@link #valuesMissing} before returning {@code null}
      * from a {@link SkyFunction}.
      *
      * <p>This API is intended for performing async computations (e.g., remote execution) in another
      * thread pool without blocking the current Skyframe thread.
      */
     void dependOnFuture(ListenableFuture<?> future);

     /**
      * A {@link SkyFunction#compute} call may return {@link Restart} only if this returns {@code
      * true}.
      */
     boolean restartPermitted();
   }
 }
	// 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.annotations.VisibleForTesting;
	import com.google.common.base.Preconditions;
	import com.google.common.graph.GraphBuilder;
	import com.google.common.graph.ImmutableGraph;
	import com.google.common.util.concurrent.ListenableFuture;
	import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
	import com.google.devtools.build.lib.events.ExtendedEventHandler;
	import com.google.devtools.build.lib.util.GroupedList;
	import java.util.List;
	import java.util.Map;
	import javax.annotation.Nullable;

	/**
	* Machinery to evaluate a single value.
	*
	* <p>The SkyFunction {@link #compute} implementation is supposed to access only direct dependencies
	* of the value. However, the direct dependencies need not be known in advance. The implementation
	* can request arbitrary values using {@link Environment#getValue}. If the values are not ready, the
	* call will return {@code null}; in that case the implementation should just return {@code null},
	* in which case the missing dependencies will be computed and the {@link #compute} method will be
	* started again.
	*/
	public interface SkyFunction {

	/**
	* When a value is requested, this method is called with the name of the value and a
	* dependency-tracking environment.
	*
	* <p>This method should return a non-{@code null} value, or {@code null} if any dependencies were
	* missing ({@link Environment#valuesMissing} was true before returning). In that case the missing
	* dependencies will be computed and the {@code compute} method called again.
	*
	* <p>This method should throw if it fails, or if one of its dependencies fails with an exception
	* and this method cannot recover. If one of its dependencies fails and this method can enrich the
	* exception with additional context, then this method should catch that exception and throw
	* another containing that additional context. If it has no such additional context, then it
	* should allow its dependency's exception to be thrown through it.
	*
	* <p>This method may return {@link Restart} in rare circumstances. See its docs. Do not return
	* values of this type unless you know exactly what you are doing.
	*
	* <p>If version information is discovered for the given {@code skyKey}, {@link
	* Environment#injectVersionForNonHermeticFunction(Version)} may be called on {@code env}.
	*
	* @throws SkyFunctionException on failure
	* @throws InterruptedException if interrupted
	*/
	@ThreadSafe
	@Nullable
	SkyValue compute(SkyKey skyKey, Environment env)
	throws SkyFunctionException, InterruptedException;

	/**
	* Extracts a tag (target label) from a SkyKey if it has one. Otherwise return {@code null}.
	*
	* <p>The tag is used for filtering out non-error event messages that do not match --output_filter
	* flag. If a SkyFunction returns {@code null} in this method it means that all the info/warning
	* messages associated with this value will be shown, no matter what --output_filter says.
	*/
	@Nullable
	String extractTag(SkyKey skyKey);

	/**
	* Sentinel {@link SkyValue} type for {@link #compute} to return, indicating that something went
	* wrong, and that the evaluation returning this value must be restarted, and the nodes associated
	* with other keys in {@link #rewindGraph()} (whose directed edges should correspond to the nodes'
	* direct dependencies) must also be restarted.
	*
	* <p>An intended cause for returning this is external data loss; e.g., if a dependency's
	* "done-ness" is intended to mean that certain data is available in an external system, but
	* during evaluation of a node that depends on that external data, that data has gone missing, and
	* reevaluation of the dependency is expected to repair the discrepancy.
	*
	* <p>Values of this type will <em>never</em> be returned by {@link Environment}'s getValue
	* methods or from {@link NodeEntry#getValue()}.
	*
	* <p>All {@link ListenableFuture}s used in calls to {@link Environment#dependOnFuture} which were
	* not already complete will be cancelled.
	*
	* <p>This may only be returned by {@link #compute} if {@link Environment#restartPermitted} is
	* true. If restarting is not permitted, {@link #compute} should throw an appropriate {@link
	* SkyFunctionException}.
	*/
	interface Restart extends SkyValue {
	ImmutableGraph<SkyKey> EMPTY_SKYKEY_GRAPH =
	ImmutableGraph.copyOf(GraphBuilder.directed().allowsSelfLoops(false).build());

	Restart SELF = () -> EMPTY_SKYKEY_GRAPH;

	static Restart selfAnd(ImmutableGraph<SkyKey> rewindGraph) {
	Preconditions.checkArgument(
	rewindGraph.isDirected(), "rewindGraph undirected: %s", rewindGraph);
	Preconditions.checkArgument(
	!rewindGraph.allowsSelfLoops(), "rewindGraph allows self loops: %s", rewindGraph);
	return () -> rewindGraph;
	}

	ImmutableGraph<SkyKey> rewindGraph();
	}

	/**
	* The services provided to the {@link SkyFunction#compute} implementation by the Skyframe
	* evaluation framework.
	*/
	interface Environment {
	/**
	* Returns a direct dependency. If the specified value is not in the set of already evaluated
	* direct dependencies, returns {@code null}. Also returns {@code null} if the specified value
	* has already been evaluated and found to be in error.
	*
	* <p>On a subsequent evaluation, if any of this value's dependencies have changed they will be
	* re-evaluated in the same order as originally requested by the {@code SkyFunction} using this
	* {@code getValue} call (see {@link #getValues} for when preserving the order is not
	* important).
	*
	* <p>This method and the ones below may throw {@link InterruptedException}. Such exceptions
	* must not be caught by the {@link SkyFunction#compute} implementation. Instead, they should be
	* propagated up to the caller of {@link SkyFunction#compute}.
	*/
	@Nullable
	SkyValue getValue(SkyKey valueName) throws InterruptedException;

	/**
	* Returns a direct dependency. If the specified value is not in the set of already evaluated
	* direct dependencies, returns {@code null}. If the specified value has already been evaluated
	* and found to be in error, throws the exception coming from the error, so long as the
	* exception is of one of the specified types. SkyFunction implementations may use this method
	* to continue evaluation even if one of their dependencies is in error by catching the thrown
	* exception and proceeding. The caller must specify the exception type(s) that might be thrown
	* using the {@code exceptionClass} argument(s). If the dependency's exception is not an
	* instance of {@code exceptionClass}, {@code null} is returned.
	*
	* <p>The exception class given cannot be a supertype or a subtype of {@link RuntimeException},
	* or a subtype of {@link InterruptedException}. See {@link
	* SkyFunctionException#validateExceptionType} for details.
	*/
	@Nullable
	<E extends Exception> SkyValue getValueOrThrow(SkyKey depKey, Class<E> exceptionClass)
	throws E, InterruptedException;

	@Nullable
	<E1 extends Exception, E2 extends Exception> SkyValue getValueOrThrow(
	SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
	throws E1, E2, InterruptedException;

	@Nullable
	<E1 extends Exception, E2 extends Exception, E3 extends Exception> SkyValue getValueOrThrow(
	SkyKey depKey,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3)
	throws E1, E2, E3, InterruptedException;

	@Nullable
	<E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
	SkyValue getValueOrThrow(
	SkyKey depKey,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4)
	throws E1, E2, E3, E4, InterruptedException;

	@Nullable
	<
	E1 extends Exception,
	E2 extends Exception,
	E3 extends Exception,
	E4 extends Exception,
	E5 extends Exception>
	SkyValue getValueOrThrow(
	SkyKey depKey,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4,
	Class<E5> exceptionClass5)
	throws E1, E2, E3, E4, E5, InterruptedException;

	/**
	* Requests {@code depKeys} "in parallel", independent of each others' values. These keys may be
	* thought of as a "dependency group" -- they are requested together by this value.
	*
	* <p>In general, if the result of one getValue call can affect the argument of a later getValue
	* call, the two calls cannot be merged into a single getValues call, since the result of the
	* first call might change on a later evaluation. Inversely, if the result of one getValue call
	* cannot affect the parameters of the next getValue call, the two keys can form a dependency
	* group and the two getValue calls should be merged into one getValues call. In the latter
	* case, if we fail to combine the _multiple_ getValue (or getValues) calls into one _single_
	* getValues call, it would result in multiple dependency groups with an implicit ordering
	* between them. This would unnecessarily cause sequential evaluations of these groups and could
	* impact overall performance.
	*
	* <p>On subsequent evaluations, when checking to see if dependencies require re-evaluation, all
	* the values within one group may be simultaneously checked. A SkyFunction should request a
	* dependency group if checking the deps serially on a subsequent evaluation would take too
	* long, and if the {@link #compute} method would request all deps anyway as long as no earlier
	* deps had changed. SkyFunction.Environment implementations may also choose to request these
	* deps in parallel on the first evaluation, potentially speeding it up.
	*
	* <p>While re-evaluating every value in the group may take longer than re-evaluating just the
	* first one and finding that it has changed, no extra work is done: the contract of the
	* dependency group means that the {@link #compute} method, when called to re-evaluate this
	* value, will request all values in the group again anyway, so they would have to have been
	* built in any case.
	*
	* <p>Example of when to use getValues: A ListProcessor value is built with key inputListRef.
	* The {@link #compute} method first calls getValue(InputList.key(inputListRef)), and retrieves
	* inputList. It then iterates through inputList, calling getValue on each input. Finally, it
	* processes the whole list and returns. Say inputList is (a, b, c). Since the {@link #compute}
	* method will unconditionally call getValue(a), getValue(b), and getValue (c), the {@link
	* #compute} method can instead just call getValues({a, b, c}). If the value is later dirtied
	* the evaluator will evaluate a, b, and c in parallel (assuming the inputList value was
	* unchanged), and re-evaluate the ListProcessor value only if at least one of them was changed.
	* On the other hand, if the InputList changes to be (a, b, d), then the evaluator will see that
	* the first dep has changed, and call the {@link #compute} method to re-evaluate from scratch,
	* without considering the dep group of {a, b, c}.
	*
	* <p>Example of when not to use getValues: A BestMatch value is built with key
	* <potentialMatchesRef, matchCriterion>. The {@link #compute} method first calls
	* getValue(PotentialMatches.key(potentialMatchesRef) and retrieves potentialMatches. It then
	* iterates through potentialMatches, calling getValue on each potential match until it finds
	* one that satisfies matchCriterion. In this case, if potentialMatches is (a, b, c), it would
	* be <i>incorrect</i> to call getValues({a, b, c}), because it is not known yet whether
	* requesting b or c will be necessary -- if a matches, then we will never call b or c.
	*
	* <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.containsKey(k)}
	* is {@code true}, and, {@code m.get(k) != null} iff the dependency was already evaluated and
	* was not in error.
	*/
	Map<SkyKey, SkyValue> getValues(Iterable<? extends SkyKey> depKeys) throws InterruptedException;

	/**
	* Similar to getValues, but instead of returning a {@code Map<SkyKey, SkyValue>}, returns a
	* {@code List<SkyValue>} in the order of the input {@code Iterable<SkyKey>}. b/172462551
	*/
	List<SkyValue> getOrderedValues(Iterable<? extends SkyKey> depKeys) throws InterruptedException;

	/**
	* Similar to {@link #getValues} but allows the caller to specify a set of types that are proper
	* subtypes of Exception (see {@link SkyFunctionException} for more details) to find out whether
	* any of the dependencies' evaluations resulted in exceptions of those types. The returned
	* objects may throw when attempting to retrieve their value.
	*
	* <p>Callers should prioritize their responsibility to detect and handle errors in the returned
	* map over their responsibility to return {@code null} if values are missing. This is because
	* in nokeep_going evaluations, an error from a low level dependency is given a chance to be
	* enriched by its reverse-dependencies, if possible. Callers should also prioritize throwing
	* exceptions over checking for {@link InterruptedException}, since during the error-bubbling
	* enrichment process, the SkyFunction is interrupted after it has received the exception to
	* prevent it from doing too much unnecessary work.
	*
	* <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.get(k) != null}.
	* For all {@code v} such that there is some {@code k} such that {@code m.get(k) == v}, the
	* following is true: {@code v.get() != null} iff the dependency {@code k} was already evaluated
	* and was not in error. {@code v.get()} throws {@code E} iff the dependency {@code k} was
	* already evaluated with an error in the specified set of {@link Exception} types.
	*/
	<E extends Exception> Map<SkyKey, ValueOrException<E>> getValuesOrThrow(
	Iterable<? extends SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException;

	<E1 extends Exception, E2 extends Exception>
	Map<SkyKey, ValueOrException2<E1, E2>> getValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2)
	throws InterruptedException;

	<E1 extends Exception, E2 extends Exception, E3 extends Exception>
	Map<SkyKey, ValueOrException3<E1, E2, E3>> getValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3)
	throws InterruptedException;

	<E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
	Map<SkyKey, ValueOrException4<E1, E2, E3, E4>> getValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4)
	throws InterruptedException;

	<
	E1 extends Exception,
	E2 extends Exception,
	E3 extends Exception,
	E4 extends Exception,
	E5 extends Exception>
	Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4,
	Class<E5> exceptionClass5)
	throws InterruptedException;

	/**
	* Similar to getValuesOrThrow, but instead of returning a {@code Map<SkyKey,
	* ValueOrException>}, returns a {@code List<SkyValue>} in the order of the input {@code
	* Iterable<SkyKey>}.
	*/
	<E extends Exception> List<ValueOrException<E>> getOrderedValuesOrThrow(
	Iterable<? extends SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException;

	<E1 extends Exception, E2 extends Exception>
	List<ValueOrException2<E1, E2>> getOrderedValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2)
	throws InterruptedException;

	<E1 extends Exception, E2 extends Exception, E3 extends Exception>
	List<ValueOrException3<E1, E2, E3>> getOrderedValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3)
	throws InterruptedException;

	<E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
	List<ValueOrException4<E1, E2, E3, E4>> getOrderedValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4)
	throws InterruptedException;

	<
	E1 extends Exception,
	E2 extends Exception,
	E3 extends Exception,
	E4 extends Exception,
	E5 extends Exception>
	List<ValueOrException5<E1, E2, E3, E4, E5>> getOrderedValuesOrThrow(
	Iterable<? extends SkyKey> depKeys,
	Class<E1> exceptionClass1,
	Class<E2> exceptionClass2,
	Class<E3> exceptionClass3,
	Class<E4> exceptionClass4,
	Class<E5> exceptionClass5)
	throws InterruptedException;

	/**
	* Returns whether there was a previous getValue[s][OrThrow] that indicated a missing
	* dependency. Formally, returns true iff at least one of the following occurred:
	*
	* <ul>
	* <li>getValue[OrThrow](k[, c]) returned {@code null} for some k
	* <li>getValues(ks).get(k) == {@code null} for some ks and k such that ks.contains(k)
	* <li>getValuesOrThrow(ks, c).get(k).get() == {@code null} for some ks and k such that
	* ks.contains(k)
	* </ul>
	*
	* <p>If this returns true, the {@link SkyFunction} must return {@code null} or throw a {@link
	* SkyFunctionException} if it detected an error even with values missing.
	*/
	boolean valuesMissing();

	/**
	* Returns the {@link ExtendedEventHandler} that a SkyFunction should use to print any errors,
	* warnings, or progress messages during execution of {@link SkyFunction#compute}.
	*/
	ExtendedEventHandler getListener();

	/**
	* A live view of deps known to have already been requested either through an earlier call to
	* {@link SkyFunction#compute} or inferred during change pruning. Should return {@code null} if
	* unknown. Only for special use cases: do not use in general unless you know exactly what
	* you're doing!
	*/
	@Nullable
	default GroupedList<SkyKey> getTemporaryDirectDeps() {
	return null;
	}

	/**
	* Injects non-hermetic {@link Version} information for this environment.
	*
	* <p>This may be called during the course of {@link SkyFunction#compute(SkyKey, Environment)}
	* if the function discovers version information for the {@link SkyKey}.
	*
	* <p>Environments that either do not need or wish to ignore non-hermetic version information
	* may keep the default no-op implementation.
	*/
	default void injectVersionForNonHermeticFunction(Version version) {}

	/**
	* Register dependencies on keys without necessarily requiring their values.
	*
	* <p>WARNING: Dependencies here MUST be done! Only use this function if you know what you're
	* doing.
	*
	* <p>If the {@link EvaluationVersionBehavior} is {@link
	* EvaluationVersionBehavior#MAX_CHILD_VERSIONS} then this method may fall back to just doing a
	* {@link #getValues} call internally. Thus, any graph evaluations that require this method to
	* be performant <i>must</i> run with {@link EvaluationVersionBehavior#GRAPH_VERSION}.
	*/
	default void registerDependencies(Iterable<SkyKey> keys) throws InterruptedException {
	getValues(keys);
	}

	/** Returns whether we are currently in error bubbling. */
	@VisibleForTesting
	boolean inErrorBubblingForTesting();

	/**
	* Adds a dependency on a Skyframe-external event. If the given future is already complete, this
	* method silently returns without doing anything (to avoid unnecessary function restarts).
	* Otherwise, Skyframe adds a listener to the passed-in future, and only re-enqueues the current
	* node after the future completes and all requested deps are done. The added listener will
	* perform the minimum amount of work on the thread completing the future necessary for Skyframe
	* bookkeeping.
	*
	* <p>Callers of this method must check {@link #valuesMissing} before returning {@code null}
	* from a {@link SkyFunction}.
	*
	* <p>This API is intended for performing async computations (e.g., remote execution) in another
	* thread pool without blocking the current Skyframe thread.
	*/
	void dependOnFuture(ListenableFuture<?> future);

	/**
	* A {@link SkyFunction#compute} call may return {@link Restart} only if this returns {@code
	* true}.
	*/
	boolean restartPermitted();
	}
	}