| // Copyright 2023 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 static com.google.common.base.Preconditions.checkNotNull; |
| |
| import com.google.common.collect.ImmutableMap; |
| import com.google.common.collect.Iterables; |
| import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingInvalidationState; |
| import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingInvalidationState; |
| import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState; |
| import com.google.devtools.build.skyframe.QueryableGraph.Reason; |
| import java.util.HashMap; |
| import java.util.Iterator; |
| import java.util.LinkedHashSet; |
| import java.util.Map; |
| import java.util.Map.Entry; |
| import java.util.Set; |
| |
| /** |
| * Partial implementation of {@link MemoizingEvaluator} with expanded support for incremental and |
| * non-incremental evaluations on an {@link InMemoryGraph}. |
| */ |
| public abstract class AbstractIncrementalInMemoryMemoizingEvaluator |
| extends AbstractInMemoryMemoizingEvaluator { |
| |
| protected final ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions; |
| protected final DirtyTrackingProgressReceiver progressReceiver; |
| |
| // State related to invalidation and deletion. |
| protected Set<SkyKey> valuesToDelete = new LinkedHashSet<>(); |
| private Set<SkyKey> valuesToDirty = new LinkedHashSet<>(); |
| protected Map<SkyKey, SkyValue> valuesToInject = new HashMap<>(); |
| private final DeletingInvalidationState deleterState = new DeletingInvalidationState(); |
| protected final Differencer differencer; |
| protected final GraphInconsistencyReceiver graphInconsistencyReceiver; |
| protected final EventFilter eventFilter; |
| |
| // Keep edges in graph. Can be false to save memory, in which case incremental builds are |
| // not possible. |
| private final boolean keepEdges; |
| |
| // Values that the caller explicitly specified are assumed to be changed -- they will be |
| // re-evaluated even if none of their children are changed. |
| private final InvalidationState invalidatorState = new DirtyingInvalidationState(); |
| |
| final EmittedEventState emittedEventState; |
| |
| protected IntVersion lastGraphVersion = null; |
| |
| protected AbstractIncrementalInMemoryMemoizingEvaluator( |
| ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions, |
| Differencer differencer, |
| DirtyTrackingProgressReceiver dirtyTrackingProgressReceiver, |
| EventFilter eventFilter, |
| EmittedEventState emittedEventState, |
| GraphInconsistencyReceiver graphInconsistencyReceiver, |
| boolean keepEdges) { |
| this.skyFunctions = checkNotNull(skyFunctions); |
| this.differencer = checkNotNull(differencer); |
| this.progressReceiver = checkNotNull(dirtyTrackingProgressReceiver); |
| this.emittedEventState = checkNotNull(emittedEventState); |
| this.eventFilter = checkNotNull(eventFilter); |
| this.graphInconsistencyReceiver = checkNotNull(graphInconsistencyReceiver); |
| this.keepEdges = keepEdges; |
| } |
| |
| protected void invalidate(Iterable<SkyKey> diff) { |
| Iterables.addAll(valuesToDirty, diff); |
| } |
| |
| /** |
| * Removes entries in {@code valuesToInject} whose values are equal to the present values in the |
| * graph. |
| */ |
| protected void pruneInjectedValues(Map<SkyKey, SkyValue> valuesToInject) { |
| for (Iterator<Entry<SkyKey, SkyValue>> it = valuesToInject.entrySet().iterator(); |
| it.hasNext(); ) { |
| Map.Entry<SkyKey, SkyValue> entry = it.next(); |
| SkyKey key = entry.getKey(); |
| SkyValue newValue = entry.getValue(); |
| NodeEntry prevEntry = getInMemoryGraph().get(null, Reason.OTHER, key); |
| if (prevEntry != null && prevEntry.isDone()) { |
| if (keepEdges) { |
| try { |
| if (!prevEntry.hasAtLeastOneDep()) { |
| if (newValue.equals(prevEntry.getValue()) |
| && !valuesToDirty.contains(key) |
| && !valuesToDelete.contains(key)) { |
| it.remove(); |
| } |
| } else { |
| // Rare situation of an injected dep that depends on another node. Usually the dep is |
| // the error transience node. When working with external repositories, it can also be |
| // an external workspace file. Don't bother injecting it, just invalidate it. |
| // We'll wastefully evaluate the node freshly during evaluation, but this happens very |
| // rarely. |
| valuesToDirty.add(key); |
| it.remove(); |
| } |
| } catch (InterruptedException e) { |
| throw new IllegalStateException( |
| "InMemoryGraph does not throw: " + entry + ", " + prevEntry, e); |
| } |
| } else { |
| // No incrementality. Just delete the old value from the graph. The new value is about to |
| // be injected. |
| getInMemoryGraph().remove(key); |
| } |
| } |
| } |
| } |
| |
| /** Injects values in {@code valuesToInject} into the graph. */ |
| protected void injectValues(IntVersion version) { |
| if (valuesToInject.isEmpty()) { |
| return; |
| } |
| try { |
| ParallelEvaluator.injectValues(valuesToInject, version, getInMemoryGraph(), progressReceiver); |
| } catch (InterruptedException e) { |
| throw new IllegalStateException("InMemoryGraph doesn't throw interrupts", e); |
| } |
| // Start with a new map to avoid bloat since clear() does not downsize the map. |
| valuesToInject = new HashMap<>(); |
| } |
| |
| protected void performInvalidation() throws InterruptedException { |
| EagerInvalidator.delete( |
| getInMemoryGraph(), valuesToDelete, progressReceiver, deleterState, keepEdges); |
| // Note that clearing the valuesToDelete would not do an internal resizing. Therefore, if any |
| // build has a large set of dirty values, subsequent operations (even clearing) will be slower. |
| // Instead, just start afresh with a new LinkedHashSet. |
| valuesToDelete = new LinkedHashSet<>(); |
| |
| EagerInvalidator.invalidate( |
| getInMemoryGraph(), valuesToDirty, progressReceiver, invalidatorState); |
| // Ditto. |
| valuesToDirty = new LinkedHashSet<>(); |
| } |
| } |