src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtility.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.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;

 /**
  * A utility class that allows us to store reverse dependencies in a memory-efficient way. At the
  * same time it allows us to group the removals and uniqueness checks so that it also performs well.
  *
  * <p>The operations {@link #addReverseDep} and {@link #removeReverseDep} here are optimized for a
  * done entry. Done entries rarely have rdeps added and removed, but do have {@link Op#CHECK}
  * operations performed frequently. As well, done node entries may never have their data forcibly
  * consolidated, since their reverse deps will only be retrieved as a whole if they are marked
  * dirty. Thus, we consolidate periodically.
  *
  * <p>{@link IncrementalInMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty
  * or initially evaluating node itself, using similar logic tuned to those cases, and calls into
  * {@link #consolidateDataAndReturnNewElements} when transitioning to done.
  *
  * <p>The storage schema for reverse dependencies of done node entries is:
  *
  * <ul>
  *   <li>0 rdeps: empty {@link ImmutableList}
  *   <li>1 rdep: bare {@link SkyKey}
  *   <li>2-4 rdeps: {@code SkyKey[]} (no nulls)
  *   <li>5+ rdeps: an {@link ArrayList}
  * </ul>
  *
  * This strategy saves memory in the common case of few reverse deps while still supporting constant
  * time additions for nodes with many rdeps by dynamically switching to an {@link ArrayList}.
  */
 abstract class ReverseDepsUtility {

   /**
    * Returns the {@link Op} to store bare instead of wrapping in {@link KeyToConsolidate}.
    *
    * <p>We can store one type of operation bare in order to save memory. For nodes on their initial
    * build and nodes not keeping reverse deps, most operations are {@link Op#ADD}.
    *
    * <p>Done nodes have very few delayed ops - {@link Op#CHECK} is never stored on a done node and
    * {@link Op#ADD} is only delayed if there are already pending delayed ops. Returning {@link
    * Op#CHECK} in this case just makes it easy to distinguish from nodes on their initial build.
    */
   static Op getOpToStoreBare(AbstractInMemoryNodeEntry<?> entry) {
     DirtyBuildingState dirtyBuildingState = entry.dirtyBuildingState;
     if (dirtyBuildingState == null) {
       return Op.CHECK;
     }
     return dirtyBuildingState.isIncremental() ? Op.CHECK : Op.ADD;
   }

   private static void maybeDelayReverseDepOp(
       IncrementalInMemoryNodeEntry entry, SkyKey reverseDep, Op op) {
     List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
     int currentReverseDepSize = sizeOf(entry.getReverseDepsRawForReverseDepsUtil());
     if (consolidations == null) {
       consolidations = new ArrayList<>(currentReverseDepSize);
       entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations);
     }
     consolidations.add(KeyToConsolidate.create(reverseDep, op, entry));
     // TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
     if (consolidations.size() >= currentReverseDepSize) {
       consolidateData(entry);
     }
   }

   private static boolean isSingleReverseDep(Object raw) {
     return raw instanceof SkyKey;
   }

   @SuppressWarnings("unchecked")
   private static List<SkyKey> multipleAsList(Object raw) {
     return raw instanceof SkyKey[] ? Arrays.asList((SkyKey[]) raw) : (List<SkyKey>) raw;
   }

   private static int sizeOf(Object raw) {
     if (isSingleReverseDep(raw)) {
       return 1;
     }
     if (raw instanceof SkyKey[]) {
       return ((SkyKey[]) raw).length;
     }
     return ((List<?>) raw).size();
   }

   @SuppressWarnings("unchecked") // Cast to List<SkyKey>.
   static void addReverseDep(IncrementalInMemoryNodeEntry entry, SkyKey newReverseDep) {
     List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
     if (dataToConsolidate != null) {
       maybeDelayReverseDepOp(entry, newReverseDep, Op.ADD);
       return;
     }
     var raw = entry.getReverseDepsRawForReverseDepsUtil();
     int newSize = sizeOf(raw) + 1;
     if (newSize == 1) {
       entry.setReverseDepsForReverseDepsUtil(newReverseDep);
     } else if (newSize == 2) {
       entry.setReverseDepsForReverseDepsUtil(new SkyKey[] {(SkyKey) raw, newReverseDep});
     } else if (newSize <= 4) {
       SkyKey[] newArray = Arrays.copyOf((SkyKey[]) raw, newSize);
       newArray[newSize - 1] = newReverseDep;
       entry.setReverseDepsForReverseDepsUtil(newArray);
     } else if (newSize == 5) {
       List<SkyKey> newList = new ArrayList<>(8);
       Collections.addAll(newList, (SkyKey[]) raw);
       newList.add(newReverseDep);
       entry.setReverseDepsForReverseDepsUtil(newList);
     } else {
       ((List<SkyKey>) raw).add(newReverseDep);
     }
   }

   /** See {@link #addReverseDep} method. */
   static void removeReverseDep(IncrementalInMemoryNodeEntry entry, SkyKey reverseDep) {
     maybeDelayReverseDepOp(entry, reverseDep, Op.REMOVE);
   }

   static void removeReverseDepsMatching(
       IncrementalInMemoryNodeEntry entry, Set<SkyKey> deletedKeys) {
     consolidateData(entry);
     ImmutableSet<SkyKey> currentReverseDeps =
         ImmutableSet.copyOf(consolidateAndGetReverseDeps(entry, /* checkConsistency= */ true));
     writeReverseDepsSet(entry, Sets.difference(currentReverseDeps, deletedKeys));
   }

   static ImmutableCollection<SkyKey> consolidateAndGetReverseDeps(
       IncrementalInMemoryNodeEntry entry, boolean checkConsistency) {
     consolidateData(entry);

     // TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
     // wrt. thread-safety. The parents of a node get modified when any of the parents is deleted,
     // and we can't handle that right now.
     var raw = entry.getReverseDepsRawForReverseDepsUtil();
     if (isSingleReverseDep(raw)) {
       return ImmutableSet.of((SkyKey) raw);
     } else {
       List<SkyKey> reverseDeps = multipleAsList(raw);
       if (!checkConsistency) {
         return ImmutableList.copyOf(reverseDeps);
       }
       ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
       if (set.size() != reverseDeps.size()) {
         Set<SkyKey> seen = new HashSet<>();
         Set<SkyKey> duplicates = new HashSet<>();
         for (SkyKey key : reverseDeps) {
           if (seen.add(key)) {
             duplicates.add(key);
           }
         }
         throw new IllegalStateException(
             String.format("In node %s: duplicate reverse deps present: %s", entry, duplicates));
       }
       return set;
     }
   }

   static Set<SkyKey> returnNewElements(IncrementalInMemoryNodeEntry entry) {
     return consolidateDataAndReturnNewElements(entry, /* mutateObject= */ false);
   }

   private static Set<SkyKey> consolidateDataAndReturnNewElements(
       IncrementalInMemoryNodeEntry entry, boolean mutateObject) {
     List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
     if (dataToConsolidate == null) {
       return ImmutableSet.of();
     }

     // On a node's initial build (or if not keeping rdeps), we don't need to build up two different
     // sets for "all reverse deps" and "new reverse deps" - they are all new.
     Op opToStoreBare = getOpToStoreBare(entry);
     boolean allRdepsAreNew = opToStoreBare == Op.ADD;
     Set<SkyKey> allReverseDeps;
     Set<SkyKey> newReverseDeps;
     var raw = entry.getReverseDepsRawForReverseDepsUtil();
     if (isSingleReverseDep(raw)) {
       Preconditions.checkState(!allRdepsAreNew, entry);
       allReverseDeps = CompactHashSet.create((SkyKey) raw);
       newReverseDeps = CompactHashSet.create();
     } else {
       List<SkyKey> reverseDepsAsList = multipleAsList(raw);
       if (allRdepsAreNew) {
         Preconditions.checkState(reverseDepsAsList.isEmpty(), entry);
         allReverseDeps = null;
         newReverseDeps = CompactHashSet.createWithExpectedSize(dataToConsolidate.size());
       } else {
         allReverseDeps = getReverseDepsSet(entry, reverseDepsAsList);
         newReverseDeps = CompactHashSet.create();
       }
     }

     for (Object keyToConsolidate : dataToConsolidate) {
       SkyKey key = KeyToConsolidate.key(keyToConsolidate);
       switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) {
         case CHECK:
           Preconditions.checkState(!allRdepsAreNew, entry);
           Preconditions.checkState(
               allReverseDeps.contains(key),
               "Reverse dep not present: %s %s %s %s",
               keyToConsolidate,
               allReverseDeps,
               dataToConsolidate,
               entry);
           Preconditions.checkState(
               newReverseDeps.add(key),
               "Duplicate new reverse dep: %s %s %s %s",
               keyToConsolidate,
               allReverseDeps,
               dataToConsolidate,
               entry);
           break;
         case REMOVE:
           if (!allRdepsAreNew) {
             Preconditions.checkState(
                 allReverseDeps.remove(key),
                 "Reverse dep to be removed not present: %s %s %s %s",
                 keyToConsolidate,
                 allReverseDeps,
                 dataToConsolidate,
                 entry);
           }
           Preconditions.checkState(
               newReverseDeps.remove(key) || !allRdepsAreNew,
               "Reverse dep to be removed not present: %s %s %s %s",
               keyToConsolidate,
               newReverseDeps,
               dataToConsolidate,
               entry);
           break;
         case ADD:
           if (!allRdepsAreNew) {
             Preconditions.checkState(
                 allReverseDeps.add(key),
                 "Duplicate reverse deps: %s %s %s %s",
                 keyToConsolidate,
                 raw,
                 dataToConsolidate,
                 entry);
           }
           Preconditions.checkState(
               newReverseDeps.add(key),
               "Duplicate new reverse deps: %s %s %s %s",
               keyToConsolidate,
               raw,
               dataToConsolidate,
               entry);
           break;
       }
     }
     if (mutateObject) {
       entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
       writeReverseDepsSet(entry, allRdepsAreNew ? newReverseDeps : allReverseDeps);
     }
     return newReverseDeps;
   }

   @CanIgnoreReturnValue
   static Set<SkyKey> consolidateDataAndReturnNewElements(IncrementalInMemoryNodeEntry entry) {
     return consolidateDataAndReturnNewElements(entry, /* mutateObject= */ true);
   }

   static void consolidateData(IncrementalInMemoryNodeEntry entry) {
     List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
     if (dataToConsolidate == null) {
       return;
     }
     entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
     var raw = entry.getReverseDepsRawForReverseDepsUtil();
     if (isSingleReverseDep(raw)) {
       Preconditions.checkState(
           dataToConsolidate.size() == 1,
           "dataToConsolidate not size 1 even though only one rdep: %s %s %s",
           dataToConsolidate,
           raw,
           entry);
       Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
       SkyKey key = KeyToConsolidate.key(keyToConsolidate);
       Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
       switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
         case REMOVE:
           entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
           // Fall through to check.
         case CHECK:
           Preconditions.checkState(key.equals(raw), "%s %s %s", keyToConsolidate, raw, entry);
           break;
         case ADD:
           throw new IllegalStateException(
               "Shouldn't delay add if only one element: "
                   + keyToConsolidate
                   + ", "
                   + raw
                   + ", "
                   + entry);
       }
       return;
     }
     List<SkyKey> reverseDepsAsList = multipleAsList(raw);
     Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);

     Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
     for (Object keyToConsolidate : dataToConsolidate) {
       SkyKey key = KeyToConsolidate.key(keyToConsolidate);
       switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
         case CHECK:
           Preconditions.checkState(
               reverseDepsAsSet.contains(key),
               "%s %s %s %s",
               keyToConsolidate,
               reverseDepsAsSet,
               dataToConsolidate,
               entry);
           break;
         case REMOVE:
           Preconditions.checkState(
               reverseDepsAsSet.remove(key),
               "%s %s %s %s",
               keyToConsolidate,
               raw,
               dataToConsolidate,
               entry);
           break;
         case ADD:
           Preconditions.checkState(
               reverseDepsAsSet.add(key),
               "%s %s %s %s",
               keyToConsolidate,
               raw,
               dataToConsolidate,
               entry);
           break;
       }
     }
     writeReverseDepsSet(entry, reverseDepsAsSet);
   }

   private static void writeReverseDepsSet(
       IncrementalInMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) {
     if (!entry.keepsEdges() || reverseDepsAsSet.isEmpty()) {
       entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
     } else if (reverseDepsAsSet.size() == 1) {
       entry.setReverseDepsForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet));
     } else if (reverseDepsAsSet.size() <= 4) {
       entry.setReverseDepsForReverseDepsUtil(reverseDepsAsSet.toArray(SkyKey[]::new));
     } else {
       entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet));
     }
   }

   private static Set<SkyKey> getReverseDepsSet(
       IncrementalInMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) {
     Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList);
     checkForDuplicates(reverseDepsAsSet, reverseDepsAsList, entry);
     return reverseDepsAsSet;
   }

   static void checkForDuplicates(
       Set<SkyKey> reverseDepsAsSet, List<SkyKey> reverseDepsAsList, InMemoryNodeEntry entry) {
     if (reverseDepsAsSet.size() == reverseDepsAsList.size()) {
       return;
     }
     // We're about to crash. Try to print an informative error message.
     Set<SkyKey> seen = new HashSet<>();
     List<SkyKey> duplicates = new ArrayList<>();
     for (SkyKey key : reverseDepsAsList) {
       if (!seen.add(key)) {
         duplicates.add(key);
       }
     }
     throw new IllegalStateException(
         (reverseDepsAsList.size() - reverseDepsAsSet.size())
             + " duplicate reverse deps: "
             + duplicates
             + " for "
             + entry);
   }

   static String toString(IncrementalInMemoryNodeEntry entry) {
     return MoreObjects.toStringHelper("ReverseDeps")
         .add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil())
         .add("singleReverseDep", isSingleReverseDep(entry))
         .add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil())
         .toString();
   }

   private ReverseDepsUtility() {}
 }
	// 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.base.MoreObjects;
	import com.google.common.base.Preconditions;
	import com.google.common.collect.ImmutableCollection;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.ImmutableSet;
	import com.google.common.collect.Iterables;
	import com.google.common.collect.Sets;
	import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
	import com.google.devtools.build.skyframe.KeyToConsolidate.Op;
	import com.google.errorprone.annotations.CanIgnoreReturnValue;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;

	/**
	* A utility class that allows us to store reverse dependencies in a memory-efficient way. At the
	* same time it allows us to group the removals and uniqueness checks so that it also performs well.
	*
	* <p>The operations {@link #addReverseDep} and {@link #removeReverseDep} here are optimized for a
	* done entry. Done entries rarely have rdeps added and removed, but do have {@link Op#CHECK}
	* operations performed frequently. As well, done node entries may never have their data forcibly
	* consolidated, since their reverse deps will only be retrieved as a whole if they are marked
	* dirty. Thus, we consolidate periodically.
	*
	* <p>{@link IncrementalInMemoryNodeEntry} manages pending reverse dep operations on a marked-dirty
	* or initially evaluating node itself, using similar logic tuned to those cases, and calls into
	* {@link #consolidateDataAndReturnNewElements} when transitioning to done.
	*
	* <p>The storage schema for reverse dependencies of done node entries is:
	*
	* <ul>
	* <li>0 rdeps: empty {@link ImmutableList}
	* <li>1 rdep: bare {@link SkyKey}
	* <li>2-4 rdeps: {@code SkyKey[]} (no nulls)
	* <li>5+ rdeps: an {@link ArrayList}
	* </ul>
	*
	* This strategy saves memory in the common case of few reverse deps while still supporting constant
	* time additions for nodes with many rdeps by dynamically switching to an {@link ArrayList}.
	*/
	abstract class ReverseDepsUtility {

	/**
	* Returns the {@link Op} to store bare instead of wrapping in {@link KeyToConsolidate}.
	*
	* <p>We can store one type of operation bare in order to save memory. For nodes on their initial
	* build and nodes not keeping reverse deps, most operations are {@link Op#ADD}.
	*
	* <p>Done nodes have very few delayed ops - {@link Op#CHECK} is never stored on a done node and
	* {@link Op#ADD} is only delayed if there are already pending delayed ops. Returning {@link
	* Op#CHECK} in this case just makes it easy to distinguish from nodes on their initial build.
	*/
	static Op getOpToStoreBare(AbstractInMemoryNodeEntry<?> entry) {
	DirtyBuildingState dirtyBuildingState = entry.dirtyBuildingState;
	if (dirtyBuildingState == null) {
	return Op.CHECK;
	}
	return dirtyBuildingState.isIncremental() ? Op.CHECK : Op.ADD;
	}

	private static void maybeDelayReverseDepOp(
	IncrementalInMemoryNodeEntry entry, SkyKey reverseDep, Op op) {
	List<Object> consolidations = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
	int currentReverseDepSize = sizeOf(entry.getReverseDepsRawForReverseDepsUtil());
	if (consolidations == null) {
	consolidations = new ArrayList<>(currentReverseDepSize);
	entry.setReverseDepsDataToConsolidateForReverseDepsUtil(consolidations);
	}
	consolidations.add(KeyToConsolidate.create(reverseDep, op, entry));
	// TODO(janakr): Should we consolidate more aggressively? This threshold can be customized.
	if (consolidations.size() >= currentReverseDepSize) {
	consolidateData(entry);
	}
	}

	private static boolean isSingleReverseDep(Object raw) {
	return raw instanceof SkyKey;
	}

	@SuppressWarnings("unchecked")
	private static List<SkyKey> multipleAsList(Object raw) {
	return raw instanceof SkyKey[] ? Arrays.asList((SkyKey[]) raw) : (List<SkyKey>) raw;
	}

	private static int sizeOf(Object raw) {
	if (isSingleReverseDep(raw)) {
	return 1;
	}
	if (raw instanceof SkyKey[]) {
	return ((SkyKey[]) raw).length;
	}
	return ((List<?>) raw).size();
	}

	@SuppressWarnings("unchecked") // Cast to List<SkyKey>.
	static void addReverseDep(IncrementalInMemoryNodeEntry entry, SkyKey newReverseDep) {
	List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
	if (dataToConsolidate != null) {
	maybeDelayReverseDepOp(entry, newReverseDep, Op.ADD);
	return;
	}
	var raw = entry.getReverseDepsRawForReverseDepsUtil();
	int newSize = sizeOf(raw) + 1;
	if (newSize == 1) {
	entry.setReverseDepsForReverseDepsUtil(newReverseDep);
	} else if (newSize == 2) {
	entry.setReverseDepsForReverseDepsUtil(new SkyKey[] {(SkyKey) raw, newReverseDep});
	} else if (newSize <= 4) {
	SkyKey[] newArray = Arrays.copyOf((SkyKey[]) raw, newSize);
	newArray[newSize - 1] = newReverseDep;
	entry.setReverseDepsForReverseDepsUtil(newArray);
	} else if (newSize == 5) {
	List<SkyKey> newList = new ArrayList<>(8);
	Collections.addAll(newList, (SkyKey[]) raw);
	newList.add(newReverseDep);
	entry.setReverseDepsForReverseDepsUtil(newList);
	} else {
	((List<SkyKey>) raw).add(newReverseDep);
	}
	}

	/** See {@link #addReverseDep} method. */
	static void removeReverseDep(IncrementalInMemoryNodeEntry entry, SkyKey reverseDep) {
	maybeDelayReverseDepOp(entry, reverseDep, Op.REMOVE);
	}

	static void removeReverseDepsMatching(
	IncrementalInMemoryNodeEntry entry, Set<SkyKey> deletedKeys) {
	consolidateData(entry);
	ImmutableSet<SkyKey> currentReverseDeps =
	ImmutableSet.copyOf(consolidateAndGetReverseDeps(entry, /* checkConsistency= */ true));
	writeReverseDepsSet(entry, Sets.difference(currentReverseDeps, deletedKeys));
	}

	static ImmutableCollection<SkyKey> consolidateAndGetReverseDeps(
	IncrementalInMemoryNodeEntry entry, boolean checkConsistency) {
	consolidateData(entry);

	// TODO(bazel-team): Unfortunately, we need to make a copy here right now to be on the safe side
	// wrt. thread-safety. The parents of a node get modified when any of the parents is deleted,
	// and we can't handle that right now.
	var raw = entry.getReverseDepsRawForReverseDepsUtil();
	if (isSingleReverseDep(raw)) {
	return ImmutableSet.of((SkyKey) raw);
	} else {
	List<SkyKey> reverseDeps = multipleAsList(raw);
	if (!checkConsistency) {
	return ImmutableList.copyOf(reverseDeps);
	}
	ImmutableSet<SkyKey> set = ImmutableSet.copyOf(reverseDeps);
	if (set.size() != reverseDeps.size()) {
	Set<SkyKey> seen = new HashSet<>();
	Set<SkyKey> duplicates = new HashSet<>();
	for (SkyKey key : reverseDeps) {
	if (seen.add(key)) {
	duplicates.add(key);
	}
	}
	throw new IllegalStateException(
	String.format("In node %s: duplicate reverse deps present: %s", entry, duplicates));
	}
	return set;
	}
	}

	static Set<SkyKey> returnNewElements(IncrementalInMemoryNodeEntry entry) {
	return consolidateDataAndReturnNewElements(entry, /* mutateObject= */ false);
	}

	private static Set<SkyKey> consolidateDataAndReturnNewElements(
	IncrementalInMemoryNodeEntry entry, boolean mutateObject) {
	List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
	if (dataToConsolidate == null) {
	return ImmutableSet.of();
	}

	// On a node's initial build (or if not keeping rdeps), we don't need to build up two different
	// sets for "all reverse deps" and "new reverse deps" - they are all new.
	Op opToStoreBare = getOpToStoreBare(entry);
	boolean allRdepsAreNew = opToStoreBare == Op.ADD;
	Set<SkyKey> allReverseDeps;
	Set<SkyKey> newReverseDeps;
	var raw = entry.getReverseDepsRawForReverseDepsUtil();
	if (isSingleReverseDep(raw)) {
	Preconditions.checkState(!allRdepsAreNew, entry);
	allReverseDeps = CompactHashSet.create((SkyKey) raw);
	newReverseDeps = CompactHashSet.create();
	} else {
	List<SkyKey> reverseDepsAsList = multipleAsList(raw);
	if (allRdepsAreNew) {
	Preconditions.checkState(reverseDepsAsList.isEmpty(), entry);
	allReverseDeps = null;
	newReverseDeps = CompactHashSet.createWithExpectedSize(dataToConsolidate.size());
	} else {
	allReverseDeps = getReverseDepsSet(entry, reverseDepsAsList);
	newReverseDeps = CompactHashSet.create();
	}
	}

	for (Object keyToConsolidate : dataToConsolidate) {
	SkyKey key = KeyToConsolidate.key(keyToConsolidate);
	switch (KeyToConsolidate.op(keyToConsolidate, opToStoreBare)) {
	case CHECK:
	Preconditions.checkState(!allRdepsAreNew, entry);
	Preconditions.checkState(
	allReverseDeps.contains(key),
	"Reverse dep not present: %s %s %s %s",
	keyToConsolidate,
	allReverseDeps,
	dataToConsolidate,
	entry);
	Preconditions.checkState(
	newReverseDeps.add(key),
	"Duplicate new reverse dep: %s %s %s %s",
	keyToConsolidate,
	allReverseDeps,
	dataToConsolidate,
	entry);
	break;
	case REMOVE:
	if (!allRdepsAreNew) {
	Preconditions.checkState(
	allReverseDeps.remove(key),
	"Reverse dep to be removed not present: %s %s %s %s",
	keyToConsolidate,
	allReverseDeps,
	dataToConsolidate,
	entry);
	}
	Preconditions.checkState(
	newReverseDeps.remove(key) \|\| !allRdepsAreNew,
	"Reverse dep to be removed not present: %s %s %s %s",
	keyToConsolidate,
	newReverseDeps,
	dataToConsolidate,
	entry);
	break;
	case ADD:
	if (!allRdepsAreNew) {
	Preconditions.checkState(
	allReverseDeps.add(key),
	"Duplicate reverse deps: %s %s %s %s",
	keyToConsolidate,
	raw,
	dataToConsolidate,
	entry);
	}
	Preconditions.checkState(
	newReverseDeps.add(key),
	"Duplicate new reverse deps: %s %s %s %s",
	keyToConsolidate,
	raw,
	dataToConsolidate,
	entry);
	break;
	}
	}
	if (mutateObject) {
	entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
	writeReverseDepsSet(entry, allRdepsAreNew ? newReverseDeps : allReverseDeps);
	}
	return newReverseDeps;
	}

	@CanIgnoreReturnValue
	static Set<SkyKey> consolidateDataAndReturnNewElements(IncrementalInMemoryNodeEntry entry) {
	return consolidateDataAndReturnNewElements(entry, /* mutateObject= */ true);
	}

	static void consolidateData(IncrementalInMemoryNodeEntry entry) {
	List<Object> dataToConsolidate = entry.getReverseDepsDataToConsolidateForReverseDepsUtil();
	if (dataToConsolidate == null) {
	return;
	}
	entry.setReverseDepsDataToConsolidateForReverseDepsUtil(null);
	var raw = entry.getReverseDepsRawForReverseDepsUtil();
	if (isSingleReverseDep(raw)) {
	Preconditions.checkState(
	dataToConsolidate.size() == 1,
	"dataToConsolidate not size 1 even though only one rdep: %s %s %s",
	dataToConsolidate,
	raw,
	entry);
	Object keyToConsolidate = Iterables.getOnlyElement(dataToConsolidate);
	SkyKey key = KeyToConsolidate.key(keyToConsolidate);
	Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
	switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
	case REMOVE:
	entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
	// Fall through to check.
	case CHECK:
	Preconditions.checkState(key.equals(raw), "%s %s %s", keyToConsolidate, raw, entry);
	break;
	case ADD:
	throw new IllegalStateException(
	"Shouldn't delay add if only one element: "
	+ keyToConsolidate
	+ ", "
	+ raw
	+ ", "
	+ entry);
	}
	return;
	}
	List<SkyKey> reverseDepsAsList = multipleAsList(raw);
	Set<SkyKey> reverseDepsAsSet = getReverseDepsSet(entry, reverseDepsAsList);

	Preconditions.checkState(getOpToStoreBare(entry) == Op.CHECK, entry);
	for (Object keyToConsolidate : dataToConsolidate) {
	SkyKey key = KeyToConsolidate.key(keyToConsolidate);
	switch (KeyToConsolidate.op(keyToConsolidate, Op.CHECK)) {
	case CHECK:
	Preconditions.checkState(
	reverseDepsAsSet.contains(key),
	"%s %s %s %s",
	keyToConsolidate,
	reverseDepsAsSet,
	dataToConsolidate,
	entry);
	break;
	case REMOVE:
	Preconditions.checkState(
	reverseDepsAsSet.remove(key),
	"%s %s %s %s",
	keyToConsolidate,
	raw,
	dataToConsolidate,
	entry);
	break;
	case ADD:
	Preconditions.checkState(
	reverseDepsAsSet.add(key),
	"%s %s %s %s",
	keyToConsolidate,
	raw,
	dataToConsolidate,
	entry);
	break;
	}
	}
	writeReverseDepsSet(entry, reverseDepsAsSet);
	}

	private static void writeReverseDepsSet(
	IncrementalInMemoryNodeEntry entry, Set<SkyKey> reverseDepsAsSet) {
	if (!entry.keepsEdges() \|\| reverseDepsAsSet.isEmpty()) {
	entry.setReverseDepsForReverseDepsUtil(ImmutableList.of());
	} else if (reverseDepsAsSet.size() == 1) {
	entry.setReverseDepsForReverseDepsUtil(Iterables.getOnlyElement(reverseDepsAsSet));
	} else if (reverseDepsAsSet.size() <= 4) {
	entry.setReverseDepsForReverseDepsUtil(reverseDepsAsSet.toArray(SkyKey[]::new));
	} else {
	entry.setReverseDepsForReverseDepsUtil(new ArrayList<>(reverseDepsAsSet));
	}
	}

	private static Set<SkyKey> getReverseDepsSet(
	IncrementalInMemoryNodeEntry entry, List<SkyKey> reverseDepsAsList) {
	Set<SkyKey> reverseDepsAsSet = CompactHashSet.create(reverseDepsAsList);
	checkForDuplicates(reverseDepsAsSet, reverseDepsAsList, entry);
	return reverseDepsAsSet;
	}

	static void checkForDuplicates(
	Set<SkyKey> reverseDepsAsSet, List<SkyKey> reverseDepsAsList, InMemoryNodeEntry entry) {
	if (reverseDepsAsSet.size() == reverseDepsAsList.size()) {
	return;
	}
	// We're about to crash. Try to print an informative error message.
	Set<SkyKey> seen = new HashSet<>();
	List<SkyKey> duplicates = new ArrayList<>();
	for (SkyKey key : reverseDepsAsList) {
	if (!seen.add(key)) {
	duplicates.add(key);
	}
	}
	throw new IllegalStateException(
	(reverseDepsAsList.size() - reverseDepsAsSet.size())
	+ " duplicate reverse deps: "
	+ duplicates
	+ " for "
	+ entry);
	}

	static String toString(IncrementalInMemoryNodeEntry entry) {
	return MoreObjects.toStringHelper("ReverseDeps")
	.add("reverseDeps", entry.getReverseDepsRawForReverseDepsUtil())
	.add("singleReverseDep", isSingleReverseDep(entry))
	.add("dataToConsolidate", entry.getReverseDepsDataToConsolidateForReverseDepsUtil())
	.toString();
	}

	private ReverseDepsUtility() {}
	}