Add a mostly reflection-based object traversal mechanism. This will be used to report the set of objects associated for each SkyValue for profiling. RELNOTES: None. PiperOrigin-RevId: 612853094 Change-Id: If4746c5dfa03cb72f55cf26b999bf89e61c43391
diff --git a/src/main/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySet.java b/src/main/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySet.java new file mode 100644 index 0000000..deeefb1 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySet.java
@@ -0,0 +1,120 @@ +// 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.collect; + +import com.google.common.base.Preconditions; +import java.util.Arrays; + +/** + * A set that performs identity-based deduplication. + * + * <p>This class is thread-safe except as noted. + * + * <p>It optimistically performs lookups without locking and locks only when mutations are needed, + * possibly causing some operations to be retried. + * + * <p>This class uses closed hashing and thus does not need entry wrappers, making it + * memory-efficient. The memory savings compared to {@link + * com.google.common.collect.Sets#newConcurrentHashSet} is approximately 32 fewer bytes per entry. + */ +// TODO(b/17553173): Can this (perhaps with value equality) be used more widely to save memory? +public final class ConcurrentIdentitySet { + private volatile Object[] data; + private int size = 0; + + /** + * @param sizeHint how many elements to store without resizing + */ + public ConcurrentIdentitySet(int sizeHint) { + int size = 1; + while (size <= sizeHint) { + size *= 2; + } + this.data = new Object[size * 2]; + } + + /** + * Tries to add {@code obj} to the set of tracked identities. + * + * @return true if {@code obj} was absent and added to the set + */ + public boolean add(Object obj) { + Preconditions.checkNotNull(obj); + int hashCode = System.identityHashCode(obj); + while (true) { + Object[] snapshot = data; + int probe = hash(/* hashCode= */ hashCode, /* length= */ snapshot.length); + Object probedValue = snapshot[probe]; + while (true) { + if (probedValue != null) { + if (probedValue == obj) { + return false; // Duplicate found. + } + if (++probe == snapshot.length) { + probe = 0; + } + probedValue = snapshot[probe]; + continue; + } + // probe points to a likely empty slot + synchronized (this) { + if (snapshot != data) { + break; // Another thread updated the snapshot. + } + // Re-reads the probed value under lock. It's possible another thread updated it. + probedValue = snapshot[probe]; + if (probedValue != null) { + continue; + } + snapshot[probe] = obj; + if (++size * 2 >= snapshot.length) { + resize(); + } + } + return true; + } + } + } + + /** Not thread safe. */ + public void clear() { + Arrays.fill(data, null); + size = 0; + } + + /** Requires synchronized (this). */ + private void resize() { + Object[] newData = new Object[data.length * 2]; + for (Object obj : data) { + if (obj == null) { + continue; + } + int probe = hash(/*hashCode=*/ System.identityHashCode(obj), /*length=*/ newData.length); + while (newData[probe] != null) { + if (++probe == newData.length) { + probe = 0; + } + } + // No need to check for equality because all values are unique. + newData[probe] = obj; + } + data = newData; + } + + /** Copied from {@link java.util.IdentityHashMap}. */ + private static int hash(int hashCode, int length) { + return ((hashCode << 1) - (hashCode << 8)) & (length - 1); + } +}
diff --git a/src/main/java/com/google/devtools/build/lib/util/BUILD b/src/main/java/com/google/devtools/build/lib/util/BUILD index e47add9..5d90249 100644 --- a/src/main/java/com/google/devtools/build/lib/util/BUILD +++ b/src/main/java/com/google/devtools/build/lib/util/BUILD
@@ -152,6 +152,17 @@ ) java_library( + name = "object_graph_traverser", + srcs = ["ObjectGraphTraverser.java"], + deps = [ + "//src/main/java/com/google/devtools/build/lib/collect", + "//third_party:flogger", + "//third_party:guava", + "//third_party:jsr305", + ], +) + +java_library( name = "ram_resource_converter", srcs = [ "RamResourceConverter.java",
diff --git a/src/main/java/com/google/devtools/build/lib/util/ObjectGraphTraverser.java b/src/main/java/com/google/devtools/build/lib/util/ObjectGraphTraverser.java new file mode 100644 index 0000000..1a07af0 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/util/ObjectGraphTraverser.java
@@ -0,0 +1,443 @@ +// 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.util; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Maps; +import com.google.common.flogger.GoogleLogger; +import com.google.devtools.build.lib.collect.ConcurrentIdentitySet; +import java.lang.reflect.Array; +import java.lang.reflect.Field; +import java.lang.reflect.InaccessibleObjectException; +import java.lang.reflect.Modifier; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.List; +import java.util.Map; +import java.util.Queue; +import javax.annotation.Nullable; + +/** + * Traverses the Java object graph. + * + * <p>When given a Java object, it walks the objects reachable from it. Returns each object only + * once, regardless of the number of edges it is reachable through. + * + * <p>For each object and reference edge found, the appropriate method of {@link ObjectReceiver} is + * called. + * + * <p>The traversal is customizable by passing in {@link DomainSpecificTraverser} instances. Each + * object can choose to handle any given object instance; in that case, it should return the + * user-friendly "context" the object is encountered in and the outgoing edges in the object graph + * it has. + * + * <p>If an object is not handled by any domain-specific traverser, Java reflection is used to + * discover its outgoing references. In this case, domain-specific traversers are still consulted to + * learn whether any of the fields should be ignored. + * + * <p>The traversal stops at objects that: + * + * <ul> + * <li>Are in the {@code seenObjects} set passed into the constructor + * <li>For which at least one {@link DomainSpecificTraverser} returns false in {@link + * DomainSpecificTraverser#admit(Object)} + * </ul> + * + * <p>A traversal currently operates on a single thread. It's not an inherent limitation, it's just + * that it was found to be much faster than spawning a new Executor task for each Java object. + */ +public class ObjectGraphTraverser { + private static final GoogleLogger logger = GoogleLogger.forEnclosingClass(); + + /** + * Cache for traversal data by object type. + * + * <p>Not a static field because it depends on what domain-specific traversers there are. + */ + public static class FieldCache { + private final Map<Class<?>, List<Field>> fieldCache; + private final ImmutableList<DomainSpecificTraverser> domainSpecificTraversers; + + public FieldCache(ImmutableList<DomainSpecificTraverser> domainSpecificTraversers) { + this.fieldCache = Maps.newConcurrentMap(); + this.domainSpecificTraversers = domainSpecificTraversers; + } + } + + /** Domain-specific knowledge about classes to traverse. */ + public interface DomainSpecificTraverser { + + /** + * Called for each object to be traversed. + * + * <p>In order for the traversal of an object to be attempted, the {@link #admit(Object)} admit + * method of all domain-specific traversals must return true. + * + * <p>If the implementation knows how to traverse this object, it should return true and call + * methods on {@link Traversal} accordingly. + * + * <p>If not domain-specific traversal handles an object, its fields will be visited by Java + * reflection. + * + * @return true if the object is handled. + */ + boolean maybeTraverse(Object o, Traversal traversal); + + /** + * Called on each object to be traversed. + * + * <p>If the implementation thinks this instance should <b>not</b> be traversed, it should + * return false. An implementation may well allow traversing an object and yet decline to handle + * it in {@link #maybeTraverse(Object, Traversal)}; in that case, the default traversal will be + * applied to the object. + * + * @return false if the implementation wants to prohibit the traversal of this object. + */ + boolean admit(Object o); + + /** + * Compute the user-friendly context for an array item. + * + * <p>This is used to describe what an object is in a way that's more meaningful to the user + * than its raw class. Only called of {@code collectContext} is true. If multiple + * domain-specific traversals provide a context, the first one takes priority. + * + * <p>This method is not called for references reported by domain-specific traversers. + * + * @param from the array the reference originates from + * @param fromContext the context of the array the reference originates from + * @param to the referenced object + * @return the context of {@code to}, or null, if its class is enough + */ + @Nullable + String contextForArrayItem(Object from, String fromContext, Object to); + + /** + * Compute the user-friendly context for a field. + * + * <p>This is used to describe what an object is in a way that's more meaningful to the user + * than its raw class. Only called of {@code collectContext} is true. If multiple + * domain-specific traversals provide a context, the first one takes priority. + * + * <p>This method is not called for references reported by domain-specific traversers. + * + * @param from the object the reference originates from + * @param fromContext the context of the object the reference originates from + * @param field the field the reference is through + * @param to the referenced object + * @return the context of {@code to}, or null, if its class is enough + */ + @Nullable + String contextForField(Object from, String fromContext, Field field, Object to); + + /** + * Return the set of fields of a class that should be ignored. + * + * @return the set of ignored fields or null if the implementation doesn't know about the given + * class. + */ + @Nullable + ImmutableSet<String> ignoredFields(Class<?> clazz); + } + + /** + * Callback through which {@link DomainSpecificTraverser} returns what objects and edges it found. + */ + public interface Traversal { + /** + * Should be called when the domain-specific traverser finds an object. It should be called for + * every object for which {@link DomainSpecificTraverser#maybeTraverse(Object, Traversal)} + * returns true. + * + * @param o the object found + * @param context the context the object is in or null of its class is enough + */ + void objectFound(Object o, String context); + + /** + * Should be called for each outgoing reference in an object handled by the {@link + * DomainSpecificTraverser} implementation. + * + * <p>Objects reported through this method are subject to two kinds of filtering: each object is + * only processed once and domain-specific traversers can prohibit the traversal of any object + * by returning false from {@link DomainSpecificTraverser#admit(Object)}. + * + * @param to the object referenced + * @param context the context of the referenced object or null if its class is enough + */ + void edgeFound(Object to, String context); + } + + /** The type of an object graph edge. */ + public enum EdgeType { + /** An edge to an object discovered during this traversal. */ + CURRENT_TRAVERSAL, + + /** An edge to an object already seen in previous traversals. */ + ALREADY_SEEN + }; + + /** A callback where {@link ObjectGraphTraverser} reports the objects and edges encountered. */ + public interface ObjectReceiver { + /** Reports an object in a given context. */ + void objectFound(Object o, String context); + + /** Reports an edge in the object graph. */ + void edgeFound(Object from, Object to, String toContext, EdgeType edgeType); + } + + /** An object to be traversed in the queue. */ + private static class WorkItem { + private final Object object; + private final String context; + + private WorkItem(Object object, String context) { + this.object = object; + this.context = context; + } + } + + private final FieldCache fieldCache; + + private final boolean collectContext; + private final Traversal traversal; + private final ObjectReceiver receiver; + private final Object instanceId; + + private Object currentObject; + private final Queue<WorkItem> queue = new ArrayDeque<>(); + + private final ConcurrentIdentitySet localObjects; + private final ConcurrentIdentitySet seenObjects; + + /** + * Creates a new traverser. + * + * @param fieldCache the cache for reflection results. + * @param seenObjects the set of objects already seen. These are not traversed and references to + * them are reported as {@link EdgeType#ALREADY_SEEN} . + * @param collectContext whether to collect context for each object. Costs some CPU. + * @param receiver the object to report found objects and edges to. + * @param instanceId an object identifying this traversal. + */ + public ObjectGraphTraverser( + FieldCache fieldCache, + ConcurrentIdentitySet seenObjects, + boolean collectContext, + ObjectReceiver receiver, + Object instanceId) { + this.fieldCache = fieldCache; + this.seenObjects = seenObjects; + this.collectContext = collectContext; + this.receiver = receiver; + this.instanceId = instanceId; + this.traversal = + new Traversal() { + @Override + public void objectFound(Object o, String context) { + receiver.objectFound(o, context); + } + + @Override + public void edgeFound(Object to, String context) { + enqueueMaybe(to, context); + } + }; + + this.localObjects = new ConcurrentIdentitySet(64); + } + + /** + * Traverses a given object. + * + * <p>Can be called multiple times, but no two traversals should be active at the same time in a + * given {@link ObjectGraphTraverser} instance. + */ + public void traverse(Object o) { + queue.offer(new WorkItem(o, null)); + while (!queue.isEmpty()) { + WorkItem workItem = queue.remove(); + try { + process(workItem.object, workItem.context); + } catch (RuntimeException e) { + logger.atSevere().withCause(e).log("While walking object graph for key %s:", instanceId); + } + } + } + + private void enqueueMaybe(Object to, String toContext) { + if (to == null) { + return; + } + + if (to instanceof Integer + || to instanceof Long + || to instanceof Short + || to instanceof Byte + || to instanceof Float + || to instanceof Double + || to instanceof Character + || to instanceof Boolean) { + // Boxed primitive type + return; + } + + for (DomainSpecificTraverser traverser : fieldCache.domainSpecificTraversers) { + if (!traverser.admit(to)) { + return; + } + } + + if (!localObjects.add(to)) { + // A reference to an object visited during this traversal. + receiver.edgeFound(currentObject, to, toContext, EdgeType.CURRENT_TRAVERSAL); + return; + } + + if (!seenObjects.add(to)) { + // A reference to an object already seen, but not during this traversal. + receiver.edgeFound(currentObject, to, toContext, EdgeType.ALREADY_SEEN); + return; + } + + // A new object. + receiver.edgeFound(currentObject, to, toContext, EdgeType.CURRENT_TRAVERSAL); + + queue.offer(new WorkItem(to, toContext)); + } + + @Nullable + private String contextOrNull(String context, String defaultContext) { + if (!collectContext) { + return null; + } + + if (context != null) { + return context; + } + + return defaultContext; + } + + private void process(Object o, String context) { + currentObject = o; + + if (o instanceof String) { + traversal.objectFound(o, contextOrNull(context, "STRING")); + return; + } + + for (DomainSpecificTraverser traverser : fieldCache.domainSpecificTraversers) { + if (traverser.maybeTraverse(o, traversal)) { + return; + } + } + + if (o instanceof Class<?>) { + traversal.objectFound(o, contextOrNull(context, "CLASS")); + return; + } + + Class<?> clazz = o.getClass(); + if (clazz.isSynthetic() && !clazz.isLocalClass() && !clazz.isAnonymousClass()) { + // This is probably a lambda, ignore it for now + return; + } + + if (clazz.isArray()) { + traversal.objectFound(o, contextOrNull(context, "[] " + clazz.getComponentType().getName())); + + // We only care about objects + if (!clazz.getComponentType().isPrimitive()) { + for (int i = 0; i < Array.getLength(o); i++) { + Object to = Array.get(o, i); + String toContext = null; + if (collectContext) { + for (DomainSpecificTraverser traverser : fieldCache.domainSpecificTraversers) { + String candidate = traverser.contextForArrayItem(o, context, to); + if (candidate != null) { + toContext = candidate; + break; + } + } + } + + enqueueMaybe(to, toContext); + } + } + } else { + traversal.objectFound(o, context); + + List<Field> fields = fieldCache.fieldCache.computeIfAbsent(clazz, this::getFields); + for (Field field : fields) { + try { + Object to = field.get(o); + String toContext = null; + if (collectContext) { + for (DomainSpecificTraverser traverser : fieldCache.domainSpecificTraversers) { + String candidate = traverser.contextForField(o, context, field, to); + if (candidate != null) { + toContext = candidate; + break; + } + } + } + enqueueMaybe(to, toContext); + } catch (IllegalAccessException e) { + throw new IllegalStateException(e); + } + } + } + } + + private ImmutableList<Field> getFields(Class<?> clazz) { + ImmutableSet<String> ignoreSet = ImmutableSet.of(); + for (DomainSpecificTraverser traverser : fieldCache.domainSpecificTraversers) { + ImmutableSet<String> candidate = traverser.ignoredFields(clazz); + if (candidate != null) { + ignoreSet = candidate; + break; + } + } + + ArrayList<Field> fields = new ArrayList<>(); + for (Class<?> next = clazz; next != null; next = next.getSuperclass()) { + for (Field field : next.getDeclaredFields()) { + if ((field.getModifiers() & Modifier.STATIC) != 0) { + continue; // Skips static or transient fields. + } + if (ignoreSet.contains(field.getName())) { + continue; + } + + if (field.getType().isPrimitive()) { + // We only care about the object graph + continue; + } + + try { + field.setAccessible(true); + } catch (InaccessibleObjectException e) { + // Ignore this field then, dunno why this happens. + continue; + } + fields.add(field); + } + } + + return ImmutableList.copyOf(fields); + } +}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySetTest.java b/src/test/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySetTest.java new file mode 100644 index 0000000..5b626f3 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/collect/ConcurrentIdentitySetTest.java
@@ -0,0 +1,91 @@ +// 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.collect; + +import static com.google.common.truth.Truth.assertThat; + +import com.google.common.collect.ImmutableList; +import com.google.devtools.build.lib.testutil.TestUtils; +import java.util.ArrayList; +import java.util.Collections; +import java.util.concurrent.ForkJoinPool; +import java.util.concurrent.TimeUnit; +import java.util.concurrent.atomic.AtomicInteger; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +@RunWith(JUnit4.class) +public final class ConcurrentIdentitySetTest { + private static final int PARALLELISM = 12; + private static final int UNIQUE_ELEMENTS = 10000; + private static final ImmutableList<Object> TEST_DATA = createTestObjects(); + + /** Ensures that {@link #TEST_DATA} is populated before any test runs. */ + @BeforeClass + public static void warmup() { + for (Object obj : TEST_DATA) { + assertThat(obj).isNotNull(); + } + } + + @Test + public void testDedupe() { + ConcurrentIdentitySet deduper = new ConcurrentIdentitySet(/* sizeHint= */ UNIQUE_ELEMENTS); + assertThat(runDedup(deduper::add)).isEqualTo(UNIQUE_ELEMENTS); + } + + @Test + public void testResize() { + ConcurrentIdentitySet deduper = new ConcurrentIdentitySet(/* sizeHint= */ 0); + assertThat(runDedup(deduper::add)).isEqualTo(UNIQUE_ELEMENTS); + } + + private static int runDedup(BooleanFunction deduper) { + ForkJoinPool pool = new ForkJoinPool(PARALLELISM); + AtomicInteger nextUnused = new AtomicInteger(0); + AtomicInteger uniqueCount = new AtomicInteger(0); + for (int i = 0; i < PARALLELISM; ++i) { + pool.execute( + () -> { + int next = 0; + while ((next = nextUnused.getAndIncrement()) < TEST_DATA.size()) { + if (deduper.apply(TEST_DATA.get(next))) { + uniqueCount.incrementAndGet(); + } + } + }); + } + assertThat(pool.awaitQuiescence(TestUtils.WAIT_TIMEOUT_SECONDS, TimeUnit.SECONDS)).isTrue(); + return uniqueCount.get(); + } + + private static ImmutableList<Object> createTestObjects() { + ArrayList<Object> data = new ArrayList<>((UNIQUE_ELEMENTS * (UNIQUE_ELEMENTS + 1)) / 2); + for (int i = 1; i <= UNIQUE_ELEMENTS; ++i) { + Object next = new Object(); + for (int j = 0; j < i; ++j) { + data.add(next); + } + } + Collections.shuffle(data); + return ImmutableList.copyOf(data); + } + + private interface BooleanFunction { + boolean apply(Object obj); + } +}
diff --git a/src/test/java/com/google/devtools/build/lib/util/BUILD b/src/test/java/com/google/devtools/build/lib/util/BUILD index 49a910f..17796b9 100644 --- a/src/test/java/com/google/devtools/build/lib/util/BUILD +++ b/src/test/java/com/google/devtools/build/lib/util/BUILD
@@ -42,6 +42,7 @@ "//src/main/java/com/google/devtools/build/lib/bugreport", "//src/main/java/com/google/devtools/build/lib/clock", "//src/main/java/com/google/devtools/build/lib/cmdline", + "//src/main/java/com/google/devtools/build/lib/collect", "//src/main/java/com/google/devtools/build/lib/shell", "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/testutils", "//src/main/java/com/google/devtools/build/lib/util", @@ -54,6 +55,7 @@ "//src/main/java/com/google/devtools/build/lib/util:filetype", "//src/main/java/com/google/devtools/build/lib/util:hash_codes", "//src/main/java/com/google/devtools/build/lib/util:interrupted_failure_details", + "//src/main/java/com/google/devtools/build/lib/util:object_graph_traverser", "//src/main/java/com/google/devtools/build/lib/util:os", "//src/main/java/com/google/devtools/build/lib/util:resource_converter", "//src/main/java/com/google/devtools/build/lib/util:shallow_object_size_computer",
diff --git a/src/test/java/com/google/devtools/build/lib/util/ObjectGraphTraverserTest.java b/src/test/java/com/google/devtools/build/lib/util/ObjectGraphTraverserTest.java new file mode 100644 index 0000000..6be1411 --- /dev/null +++ b/src/test/java/com/google/devtools/build/lib/util/ObjectGraphTraverserTest.java
@@ -0,0 +1,316 @@ +// 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.util; + +import static com.google.common.truth.Truth.assertThat; +import static org.mockito.ArgumentMatchers.any; +import static org.mockito.ArgumentMatchers.refEq; +import static org.mockito.Mockito.mock; +import static org.mockito.Mockito.when; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.devtools.build.lib.collect.ConcurrentIdentitySet; +import com.google.devtools.build.lib.util.ObjectGraphTraverser.DomainSpecificTraverser; +import com.google.devtools.build.lib.util.ObjectGraphTraverser.EdgeType; +import com.google.devtools.build.lib.util.ObjectGraphTraverser.FieldCache; +import com.google.devtools.build.lib.util.ObjectGraphTraverser.Traversal; +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.function.Supplier; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.JUnit4; + +@RunWith(JUnit4.class) +public class ObjectGraphTraverserTest { + private static final class Edge { + private final Object from; + private final Object to; + private final EdgeType type; + + private Edge(Object from, Object to, EdgeType type) { + this.from = from; + this.to = to; + this.type = type; + } + + private static Edge of(Object from, Object to, EdgeType type) { + return new Edge(from, to, type); + } + + @Override + public boolean equals(Object o) { + if (!(o instanceof Edge)) { + return false; + } + + Edge that = (Edge) o; + return that.from == from && that.to == to && that.type == type; + } + + @Override + public int hashCode() { + return Objects.hash(System.identityHashCode(from), System.identityHashCode(to), type); + } + } + + private static final class LoggingObjectReceiver implements ObjectGraphTraverser.ObjectReceiver { + private List<Object> objects = new ArrayList<>(); + private Map<Object, String> objectContexts = new HashMap<>(); + private List<Edge> edges = new ArrayList<>(); + private Map<Edge, String> edgeContexts = new HashMap<>(); + + @Override + public void objectFound(Object o, String context) { + objects.add(o); + if (context != null) { + objectContexts.put(o, context); + } + } + + @Override + public void edgeFound(Object from, Object to, String toContext, EdgeType edgeType) { + Edge edge = Edge.of(from, to, edgeType); + + edges.add(edge); + if (toContext != null) { + edgeContexts.put(edge, toContext); + } + } + } + + private ObjectGraphTraverser createObjectGraphTraverser( + DomainSpecificTraverser domainSpecific, + ConcurrentIdentitySet seen, + LoggingObjectReceiver receiver, + boolean collectContext) { + ImmutableList<DomainSpecificTraverser> traversers = + domainSpecific == null ? ImmutableList.of() : ImmutableList.of(domainSpecific); + return new ObjectGraphTraverser( + new FieldCache(traversers), seen, collectContext, receiver, null); + } + + @Test + public void smoke() { + Object o1 = new Object(); + Object o2 = new Object(); + Object array = new Object[] {o2}; + Object pair = Pair.of(o1, array); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(null, seen, receiver, false); + cut.traverse(pair); + + assertThat(receiver.objects).containsExactly(o1, o2, array, pair); + assertThat(receiver.edges).hasSize(3); + } + + @Test + public void testAdmit() { + Object o1 = new Object(); + Object o2 = new Object(); + Object pair1 = Pair.of(o1, o1); + Object pair2 = Pair.of(o2, o2); + Object pair3 = Pair.of(pair1, pair2); + + DomainSpecificTraverser domainSpecific = mock(DomainSpecificTraverser.class); + when(domainSpecific.admit(any())).thenAnswer(i -> i.getArgument(0) != pair2); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(domainSpecific, seen, receiver, false); + cut.traverse(pair3); + + assertThat(receiver.objects).containsExactly(o1, pair1, pair3); + assertThat(receiver.edges).hasSize(3); + } + + @Test + public void testCustomTraversal() { + Object o1 = new Object(); + Object o2 = new Object(); + + DomainSpecificTraverser domainSpecific = mock(DomainSpecificTraverser.class); + when(domainSpecific.admit(any())).thenReturn(true); + when(domainSpecific.maybeTraverse(any(), any())) + .thenAnswer( + i -> { + Object arg = i.getArgument(0); + Traversal traversal = i.getArgument(1); + + if (arg != o1) { + return false; + } + + traversal.objectFound(o1, null); + traversal.edgeFound(o2, null); + return true; + }); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(domainSpecific, seen, receiver, false); + cut.traverse(o1); + + assertThat(receiver.objects).containsExactly(o1, o2); + assertThat(receiver.edges).containsExactly(Edge.of(o1, o2, EdgeType.CURRENT_TRAVERSAL)); + } + + @Test + public void testIgnoredFields() { + Object o1 = new Object(); + Object o2 = new Object(); + Object pair = Pair.of(o1, o2); + + DomainSpecificTraverser domainSpecific = mock(DomainSpecificTraverser.class); + when(domainSpecific.ignoredFields(Pair.class)).thenReturn(ImmutableSet.of("second")); + when(domainSpecific.admit(any())).thenReturn(true); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(domainSpecific, seen, receiver, false); + cut.traverse(pair); + + assertThat(receiver.objects).containsExactly(o1, pair); + assertThat(receiver.edges).containsExactly(Edge.of(pair, o1, EdgeType.CURRENT_TRAVERSAL)); + } + + @Test + public void testSeenObjects() { + Object o1 = new Object(); + Object o2 = new Object(); + Object pair = Pair.of(o1, o2); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + var unused = seen.add(o2); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(null, seen, receiver, false); + cut.traverse(pair); + + assertThat(receiver.objects).containsExactly(o1, pair); + assertThat(receiver.edges) + .containsExactly( + Edge.of(pair, o1, EdgeType.CURRENT_TRAVERSAL), + Edge.of(pair, o2, EdgeType.ALREADY_SEEN)); + } + + private static final class Outer { + private Inner createInner() { + return new Inner(); + } + + private class Inner { + // Java is clever and will optimize out the reference to Outer without this + @SuppressWarnings("unused") + private Outer getOuter() { + return Outer.this; + } + } + } + + @Test + public void testNonStaticClassTraversesEnclosingClass() { + Outer outer = new Outer(); + Outer.Inner inner = outer.createInner(); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(null, seen, receiver, false); + + cut.traverse(inner); + assertThat(receiver.objects).containsExactly(outer, inner); + } + + // Arguably, lambdas should not be ignored, nor should be the values they close over, but that's + // what the code does at the moment. + @Test + public void testLambdasIgnored() { + Object o1 = new Object(); + Object o2 = new Object(); + Supplier<Object> lambda = () -> o1; + Object pair = Pair.of(o2, lambda); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + ObjectGraphTraverser cut = createObjectGraphTraverser(null, seen, receiver, false); + + cut.traverse(pair); + assertThat(receiver.objects).containsExactly(pair, o2); + } + + @Test + public void testEdgeContexts() { + Object o1 = new Object(); + Object o2 = new Object(); + Object array = new Object[] {o2}; + Object pair = Pair.of(o1, array); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + DomainSpecificTraverser domainSpecific = mock(DomainSpecificTraverser.class); + when(domainSpecific.admit(any())).thenReturn(true); + when(domainSpecific.contextForField(refEq(pair), any(), any(), refEq(o1))) + .thenReturn("o1context"); + when(domainSpecific.contextForArrayItem(refEq(array), any(), refEq(o2))) + .thenReturn("o2context"); + ObjectGraphTraverser cut = createObjectGraphTraverser(domainSpecific, seen, receiver, true); + + cut.traverse(pair); + assertThat(receiver.edgeContexts) + .containsEntry(Edge.of(pair, o1, EdgeType.CURRENT_TRAVERSAL), "o1context"); + assertThat(receiver.edgeContexts) + .containsEntry(Edge.of(array, o2, EdgeType.CURRENT_TRAVERSAL), "o2context"); + assertThat(receiver.objectContexts).containsEntry(o1, "o1context"); + assertThat(receiver.objectContexts).containsEntry(o2, "o2context"); + } + + @Test + public void testObjectContexts() { + Object o1 = new Object(); + Object o2 = new Object(); + Object pair = Pair.of(o1, o2); + + ConcurrentIdentitySet seen = new ConcurrentIdentitySet(1); + LoggingObjectReceiver receiver = new LoggingObjectReceiver(); + DomainSpecificTraverser domainSpecific = mock(DomainSpecificTraverser.class); + when(domainSpecific.admit(any())).thenReturn(true); + when(domainSpecific.contextForField(refEq(pair), any(), any(), refEq(o1))).thenReturn("bad"); + when(domainSpecific.maybeTraverse(any(), any())) + .thenAnswer( + i -> { + Object o = i.getArgument(0); + Traversal traversal = i.getArgument(1); + if (o == o1) { + traversal.objectFound(o, "o1context"); + return true; + } else if (o == o2) { + traversal.objectFound(o, "o2context"); + return true; + } else { + return false; + } + }); + ObjectGraphTraverser cut = createObjectGraphTraverser(domainSpecific, seen, receiver, true); + + cut.traverse(pair); + assertThat(receiver.objectContexts).containsEntry(o1, "o1context"); // overrides edge context + assertThat(receiver.objectContexts).containsEntry(o2, "o2context"); + } +}