src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils/Fingerprinter.java - bazel - Git at Google

 // Copyright 2024 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.skyframe.serialization.testutils;

 import static com.google.common.base.Preconditions.checkState;
 import static com.google.common.hash.Hashing.murmur3_128;
 import static com.google.devtools.build.lib.skyframe.serialization.testutils.Dumper.getTypeName;
 import static com.google.devtools.build.lib.skyframe.serialization.testutils.Dumper.shouldInline;
 import static com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.getFieldInfo;
 import static java.lang.Math.min;

 import com.google.common.annotations.VisibleForTesting;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.FieldInfo;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.ObjectInfo;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.PrimitiveInfo;
 import java.lang.reflect.Array;
 import java.util.IdentityHashMap;
 import java.util.Map;
 import javax.annotation.Nullable;

 /**
  * Fingerprints arbitrary objects for serialization testing.
  *
  * <p>Like serialization, it skips {@code transient} fields.
  */
 final class Fingerprinter {
   private final IdentityHashMap<Object, String> fingerprints = new IdentityHashMap<>();

   /** Stack for detecting cyclic backreferences in depth-first traversal. */
   private final IdentityHashMap<Object, Integer> stack = new IdentityHashMap<>();

   private Fingerprinter() {}

   /**
    * Traverses {@code obj} and computes fingerprints for objects within.
    *
    * <p>Objects with cycles (or cyclic complexes) are handled in the following way. When a cycle is
    * encountered, logically, the first node encountered in the cycle becomes its owner. By
    * definition, every element of the cycle is reachable by a DFS traversal from the owner. The
    * cycle is fingerprinted with a DFS traversal using <em>relative</em> backreferences. Since these
    * backreferences only make sense locally, the fingerprints of the individual cycle elements are
    * not published. Only the owner's fingerprint is published.
    *
    * <p>This implies that if the same cycle is encountered, but the traversal starts at a different
    * node, it will receive a different fingerprint. A consequence of this is that deduplication of
    * cycles by fingerprint will be limited to only cycles that match on their owning nodes.
    *
    * <p>An alternative might be to fingerprint every cyclic complex starting from every node of the
    * complex and add those entries to the fingerprint map. That would make fingerprinting quadratic
    * in the size of the cyclic complex instead of the current, linear cost. As of 03/19/2024, there
    * is no evidence of that extra cost being necessary.
    */
   static IdentityHashMap<Object, String> computeFingerprints(Object obj) {
     StringBuilder fingerprintOut = new StringBuilder();
     Fingerprinter fingerprinter = new Fingerprinter();
     int unused = fingerprinter.outputFingerprintOrInlinedValue(obj, fingerprintOut);
     checkState(
         fingerprinter.stack.isEmpty(),
         "The stack should be empty after fingerprinting %s, but it was not. This means an"
             + " implementation bug.",
         obj);
     fingerprinter.fingerprints.put(obj, fingerprintOut.toString());
     return fingerprinter.fingerprints;
   }

   /**
    * Recursively computes the fingerprint of {@code obj} and outputs it to {@code fingerprintOut} or
    * when {@code obj} is an inlined type, outputs its value directly.
    *
    * @return the least backreferenced stack element index ({@code Integer.MAX_VALUE} if there were
    *     no backreferences). This corresponds to the highest cycle`s owner, if any.
    */
   private int outputFingerprintOrInlinedValue(@Nullable Object obj, StringBuilder fingerprintOut) {
     if (obj == null) {
       fingerprintOut.append("null");
       return Integer.MAX_VALUE;
     }

     { // Checks for an already computed fingerprint.
       String previousFingerprint = fingerprints.get(obj);
       if (previousFingerprint != null) {
         fingerprintOut.append(previousFingerprint);
         return Integer.MAX_VALUE;
       }
     }

     Class<?> type = obj.getClass();
     if (shouldInline(type)) {
       // Emits the type, even for inline values. This avoids a possible ambiguities. For example,
       // "-1" could be a backreference, String, Integer, or other things if there were no type
       // prefix.
       fingerprintOut.append(getTypeName(type)).append(':').append(obj);
       return Integer.MAX_VALUE;
     }

     {
       Integer cyclicBackReference = stack.get(obj);
       if (cyclicBackReference != null) {
         int currentIndex = stack.size() - 1;
         // Converts cyclic backreferences into a negative number, indicating how many levels up the
         // stack need to be traversed to reach the backreference.
         fingerprintOut.append(cyclicBackReference - currentIndex);
         return cyclicBackReference;
       }
     }

     StringBuilder textOut = new StringBuilder();
     int cycleOwnerIndex = outputObject(obj, type, textOut);

     String fingerprint = fingerprintString(textOut.toString());
     fingerprintOut.append(fingerprint);

     if (cycleOwnerIndex >= stack.size()) {
       // `obj` contains no backreferences to elements still on the stack so the fingerprint is
       // globally valid and can be published.
       fingerprints.put(obj, fingerprint);
     }
     return cycleOwnerIndex;
   }

   /**
    * Outputs a string representation of {@code obj} to {@code out}.
    *
    * <p>The string representation uses fingerprints anywhere a recursion occurs. The resulting
    * fingerprint should be unique for <em>equivalent</em> values.
    *
    * @return the least backreferenced stack element index
    */
   private int outputObject(Object obj, Class<?> type, StringBuilder out) {
     out.append(getTypeName(type)).append(": ["); // Emits a header.
     stack.put(obj, stack.size());
     try {
       if (type.isArray()) {
         return outputArrayElements(obj, out);
       }
       if (obj instanceof Map) {
         return outputMapEntries((Map<?, ?>) obj, out);
       }
       if (obj instanceof Iterable) {
         return outputIterableElements((Iterable<?>) obj, out);
       }
       return outputObjectFields(obj, out);
     } finally {
       stack.remove(obj);
       out.append(']');
     }
   }

   // The following output methods have the same return value contract as `outputObject`.

   private int outputArrayElements(Object arr, StringBuilder out) {
     var componentType = arr.getClass().getComponentType();
     if (componentType.equals(byte.class)) {
       // Byte arrays output as hex.
       for (byte b : (byte[]) arr) {
         out.append(String.format("%02X", b));
       }
       return Integer.MAX_VALUE;
     }

     if (shouldInline(componentType)) {
       // The component is an inlined type. Outputs elements delimited by commas.
       boolean isFirst = true;
       for (int i = 0; i < Array.getLength(arr); i++) {
         if (isFirst) {
           isFirst = false;
         } else {
           out.append(", ");
         }
         Object elt = Array.get(arr, i);
         if (elt != null) {
           out.append(getTypeName(elt.getClass())).append(':');
         }
         out.append(elt);
       }
       return Integer.MAX_VALUE;
     }

     // The component is some arbitrary type. Outputs the element fingerprints.
     int cycleOwnerIndex = Integer.MAX_VALUE;
     boolean isFirst = true;
     for (int i = 0; i < Array.getLength(arr); i++) {
       if (isFirst) {
         isFirst = false;
       } else {
         out.append(", ");
       }
       Object elt = Array.get(arr, i);
       cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(elt, out));
     }
     return cycleOwnerIndex;
   }

   private int outputMapEntries(Map<?, ?> map, StringBuilder out) {
     int cycleOwnerIndex = Integer.MAX_VALUE;
     boolean isFirst = true;
     for (Map.Entry<?, ?> entry : map.entrySet()) {
       if (isFirst) {
         isFirst = false;
       } else {
         out.append(", ");
       }
       out.append("key=");
       Object key = entry.getKey();
       cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(key, out));

       out.append(", value=");
       Object value = entry.getValue();
       cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(value, out));
     }
     return cycleOwnerIndex;
   }

   private int outputIterableElements(Iterable<?> iterable, StringBuilder out) {
     int cycleOwnerIndex = Integer.MAX_VALUE;
     boolean isFirst = true;
     for (Object elt : iterable) {
       if (isFirst) {
         isFirst = false;
       } else {
         out.append(", ");
       }
       cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(elt, out));
     }
     return cycleOwnerIndex;
   }

   private int outputObjectFields(Object obj, StringBuilder out) {
     int cycleOwnerIndex = Integer.MAX_VALUE;
     boolean isFirst = true;
     for (FieldInfo info : getFieldInfo(obj.getClass())) {
       if (isFirst) {
         isFirst = false;
       } else {
         out.append(", ");
       }
       switch (info) {
         case PrimitiveInfo primitiveInfo -> primitiveInfo.output(obj, out);
         case ObjectInfo objectInfo -> {
           out.append(objectInfo.name()).append('=');
           cycleOwnerIndex =
               min(
                   cycleOwnerIndex,
                   outputFingerprintOrInlinedValue(objectInfo.getFieldValue(obj), out));
         }
       }
     }
     return cycleOwnerIndex;
   }

   @VisibleForTesting // private
   static String fingerprintString(String text) {
     return murmur3_128().hashUnencodedChars(text).toString().intern();
   }
 }
	// Copyright 2024 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.skyframe.serialization.testutils;

	import static com.google.common.base.Preconditions.checkState;
	import static com.google.common.hash.Hashing.murmur3_128;
	import static com.google.devtools.build.lib.skyframe.serialization.testutils.Dumper.getTypeName;
	import static com.google.devtools.build.lib.skyframe.serialization.testutils.Dumper.shouldInline;
	import static com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.getFieldInfo;
	import static java.lang.Math.min;

	import com.google.common.annotations.VisibleForTesting;
	import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.FieldInfo;
	import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.ObjectInfo;
	import com.google.devtools.build.lib.skyframe.serialization.testutils.FieldInfoCache.PrimitiveInfo;
	import java.lang.reflect.Array;
	import java.util.IdentityHashMap;
	import java.util.Map;
	import javax.annotation.Nullable;

	/**
	* Fingerprints arbitrary objects for serialization testing.
	*
	* <p>Like serialization, it skips {@code transient} fields.
	*/
	final class Fingerprinter {
	private final IdentityHashMap<Object, String> fingerprints = new IdentityHashMap<>();

	/** Stack for detecting cyclic backreferences in depth-first traversal. */
	private final IdentityHashMap<Object, Integer> stack = new IdentityHashMap<>();

	private Fingerprinter() {}

	/**
	* Traverses {@code obj} and computes fingerprints for objects within.
	*
	* <p>Objects with cycles (or cyclic complexes) are handled in the following way. When a cycle is
	* encountered, logically, the first node encountered in the cycle becomes its owner. By
	* definition, every element of the cycle is reachable by a DFS traversal from the owner. The
	* cycle is fingerprinted with a DFS traversal using <em>relative</em> backreferences. Since these
	* backreferences only make sense locally, the fingerprints of the individual cycle elements are
	* not published. Only the owner's fingerprint is published.
	*
	* <p>This implies that if the same cycle is encountered, but the traversal starts at a different
	* node, it will receive a different fingerprint. A consequence of this is that deduplication of
	* cycles by fingerprint will be limited to only cycles that match on their owning nodes.
	*
	* <p>An alternative might be to fingerprint every cyclic complex starting from every node of the
	* complex and add those entries to the fingerprint map. That would make fingerprinting quadratic
	* in the size of the cyclic complex instead of the current, linear cost. As of 03/19/2024, there
	* is no evidence of that extra cost being necessary.
	*/
	static IdentityHashMap<Object, String> computeFingerprints(Object obj) {
	StringBuilder fingerprintOut = new StringBuilder();
	Fingerprinter fingerprinter = new Fingerprinter();
	int unused = fingerprinter.outputFingerprintOrInlinedValue(obj, fingerprintOut);
	checkState(
	fingerprinter.stack.isEmpty(),
	"The stack should be empty after fingerprinting %s, but it was not. This means an"
	+ " implementation bug.",
	obj);
	fingerprinter.fingerprints.put(obj, fingerprintOut.toString());
	return fingerprinter.fingerprints;
	}

	/**
	* Recursively computes the fingerprint of {@code obj} and outputs it to {@code fingerprintOut} or
	* when {@code obj} is an inlined type, outputs its value directly.
	*
	* @return the least backreferenced stack element index ({@code Integer.MAX_VALUE} if there were
	* no backreferences). This corresponds to the highest cycle`s owner, if any.
	*/
	private int outputFingerprintOrInlinedValue(@Nullable Object obj, StringBuilder fingerprintOut) {
	if (obj == null) {
	fingerprintOut.append("null");
	return Integer.MAX_VALUE;
	}

	{ // Checks for an already computed fingerprint.
	String previousFingerprint = fingerprints.get(obj);
	if (previousFingerprint != null) {
	fingerprintOut.append(previousFingerprint);
	return Integer.MAX_VALUE;
	}
	}

	Class<?> type = obj.getClass();
	if (shouldInline(type)) {
	// Emits the type, even for inline values. This avoids a possible ambiguities. For example,
	// "-1" could be a backreference, String, Integer, or other things if there were no type
	// prefix.
	fingerprintOut.append(getTypeName(type)).append(':').append(obj);
	return Integer.MAX_VALUE;
	}

	{
	Integer cyclicBackReference = stack.get(obj);
	if (cyclicBackReference != null) {
	int currentIndex = stack.size() - 1;
	// Converts cyclic backreferences into a negative number, indicating how many levels up the
	// stack need to be traversed to reach the backreference.
	fingerprintOut.append(cyclicBackReference - currentIndex);
	return cyclicBackReference;
	}
	}

	StringBuilder textOut = new StringBuilder();
	int cycleOwnerIndex = outputObject(obj, type, textOut);

	String fingerprint = fingerprintString(textOut.toString());
	fingerprintOut.append(fingerprint);

	if (cycleOwnerIndex >= stack.size()) {
	// `obj` contains no backreferences to elements still on the stack so the fingerprint is
	// globally valid and can be published.
	fingerprints.put(obj, fingerprint);
	}
	return cycleOwnerIndex;
	}

	/**
	* Outputs a string representation of {@code obj} to {@code out}.
	*
	* <p>The string representation uses fingerprints anywhere a recursion occurs. The resulting
	* fingerprint should be unique for <em>equivalent</em> values.
	*
	* @return the least backreferenced stack element index
	*/
	private int outputObject(Object obj, Class<?> type, StringBuilder out) {
	out.append(getTypeName(type)).append(": ["); // Emits a header.
	stack.put(obj, stack.size());
	try {
	if (type.isArray()) {
	return outputArrayElements(obj, out);
	}
	if (obj instanceof Map) {
	return outputMapEntries((Map<?, ?>) obj, out);
	}
	if (obj instanceof Iterable) {
	return outputIterableElements((Iterable<?>) obj, out);
	}
	return outputObjectFields(obj, out);
	} finally {
	stack.remove(obj);
	out.append(']');
	}
	}

	// The following output methods have the same return value contract as `outputObject`.

	private int outputArrayElements(Object arr, StringBuilder out) {
	var componentType = arr.getClass().getComponentType();
	if (componentType.equals(byte.class)) {
	// Byte arrays output as hex.
	for (byte b : (byte[]) arr) {
	out.append(String.format("%02X", b));
	}
	return Integer.MAX_VALUE;
	}

	if (shouldInline(componentType)) {
	// The component is an inlined type. Outputs elements delimited by commas.
	boolean isFirst = true;
	for (int i = 0; i < Array.getLength(arr); i++) {
	if (isFirst) {
	isFirst = false;
	} else {
	out.append(", ");
	}
	Object elt = Array.get(arr, i);
	if (elt != null) {
	out.append(getTypeName(elt.getClass())).append(':');
	}
	out.append(elt);
	}
	return Integer.MAX_VALUE;
	}

	// The component is some arbitrary type. Outputs the element fingerprints.
	int cycleOwnerIndex = Integer.MAX_VALUE;
	boolean isFirst = true;
	for (int i = 0; i < Array.getLength(arr); i++) {
	if (isFirst) {
	isFirst = false;
	} else {
	out.append(", ");
	}
	Object elt = Array.get(arr, i);
	cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(elt, out));
	}
	return cycleOwnerIndex;
	}

	private int outputMapEntries(Map<?, ?> map, StringBuilder out) {
	int cycleOwnerIndex = Integer.MAX_VALUE;
	boolean isFirst = true;
	for (Map.Entry<?, ?> entry : map.entrySet()) {
	if (isFirst) {
	isFirst = false;
	} else {
	out.append(", ");
	}
	out.append("key=");
	Object key = entry.getKey();
	cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(key, out));

	out.append(", value=");
	Object value = entry.getValue();
	cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(value, out));
	}
	return cycleOwnerIndex;
	}

	private int outputIterableElements(Iterable<?> iterable, StringBuilder out) {
	int cycleOwnerIndex = Integer.MAX_VALUE;
	boolean isFirst = true;
	for (Object elt : iterable) {
	if (isFirst) {
	isFirst = false;
	} else {
	out.append(", ");
	}
	cycleOwnerIndex = min(cycleOwnerIndex, outputFingerprintOrInlinedValue(elt, out));
	}
	return cycleOwnerIndex;
	}

	private int outputObjectFields(Object obj, StringBuilder out) {
	int cycleOwnerIndex = Integer.MAX_VALUE;
	boolean isFirst = true;
	for (FieldInfo info : getFieldInfo(obj.getClass())) {
	if (isFirst) {
	isFirst = false;
	} else {
	out.append(", ");
	}
	switch (info) {
	case PrimitiveInfo primitiveInfo -> primitiveInfo.output(obj, out);
	case ObjectInfo objectInfo -> {
	out.append(objectInfo.name()).append('=');
	cycleOwnerIndex =
	min(
	cycleOwnerIndex,
	outputFingerprintOrInlinedValue(objectInfo.getFieldValue(obj), out));
	}
	}
	}
	return cycleOwnerIndex;
	}

	@VisibleForTesting // private
	static String fingerprintString(String text) {
	return murmur3_128().hashUnencodedChars(text).toString().intern();
	}
	}