Use settings.xml in jitpack build

Plus other tweaks.

documentation-support/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>documentation-support</artifactId>

error-prone-contrib/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>error-prone-contrib</artifactId>

jitpack.yml

@@ -0,0 +1,8 @@
+jdk:
+  - openjdk17
+before_install:
+  - sdk install maven 3.8.7
+  - mvn -v
+install:
+  - echo "Building with fork!"
+  - mvn clean install -DskipTests -Perror-prone-fork -s settings.xml

pom.xml

@@ -4,7 +4,7 @@
 
     <groupId>tech.picnic.error-prone-support</groupId>
     <artifactId>error-prone-support</artifactId>
-    <version>0.12.1-SNAPSHOT</version>
+    <version>0.13.2-SNAPSHOT</version>
     <packaging>pom</packaging>
 
     <name>Picnic :: Error Prone Support</name>
@@ -200,15 +200,29 @@
         <version.auto-service>1.1.1</version.auto-service>
         <version.auto-value>1.10.2</version.auto-value>
         <version.error-prone>${version.error-prone-orig}</version.error-prone>
-        <version.error-prone-fork>v${version.error-prone-orig}-picnic-1</version.error-prone-fork>
+        <version.error-prone-fork>gdejong~refaster-tree-tweaks-v2.3.4-g09ec60b-2072</version.error-prone-fork>
         <version.error-prone-orig>2.21.1</version.error-prone-orig>
         <version.error-prone-slf4j>0.1.20</version.error-prone-slf4j>
         <version.guava-beta-checker>1.0</version.guava-beta-checker>
         <version.jdk>11</version.jdk>
+        <version.jmh>1.35</version.jmh>
         <version.maven>3.8.7</version.maven>
         <version.mockito>5.4.0</version.mockito>
+        <!-- XXX: Consider providing our own implementation with similar
+        functionality, and designing it such that JMH classes would not need to
+        be annotated `@Open`. -->
+        <version.nopen>1.0.1</version.nopen>
         <version.nopen-checker>1.0.1</version.nopen-checker>
         <version.nullaway>0.10.12</version.nullaway>
+        <!-- XXX: Two other dependencies are potentially of interest:
+        `com.palantir.assertj-automation:assertj-refaster-rules` and
+        `com.palantir.baseline:baseline-refaster-rules` contain Refaster rules
+        that aren't currently applied. We should use
+        `RefasterRuleBuilderScanner` to convert those to `.refaster` files so
+        that we can pick them up. (But in case of `baseline-refaster-rules`
+        perhaps we can simply incorporate all of them.) -->
+        <version.palantir-assertj-automation>0.6.0</version.palantir-assertj-automation>
+        <version.palantir-baseline>4.145.0</version.palantir-baseline>
         <version.pitest-git>1.1.1</version.pitest-git>
         <version.surefire>3.1.2</version.surefire>
     </properties>
@@ -292,6 +306,11 @@
                 <artifactId>auto-value-annotations</artifactId>
                 <version>${version.auto-value}</version>
             </dependency>
+            <dependency>
+                <groupId>com.google.code.findbugs</groupId>
+                <artifactId>jsr305</artifactId>
+                <version>3.0.2</version>
+            </dependency>
             <dependency>
                 <groupId>com.google.googlejavaformat</groupId>
                 <artifactId>google-java-format</artifactId>
@@ -316,12 +335,10 @@
                 <artifactId>truth</artifactId>
                 <version>1.1.5</version>
             </dependency>
-            <!-- Specified as a workaround for
-            https://github.com/mojohaus/versions-maven-plugin/issues/244. -->
             <dependency>
                 <groupId>com.jakewharton.nopen</groupId>
-                <artifactId>nopen-checker</artifactId>
-                <version>${version.nopen-checker}</version>
+                <artifactId>nopen-annotations</artifactId>
+                <version>${version.nopen}</version>
             </dependency>
             <dependency>
                 <groupId>com.newrelic.agent.java</groupId>
@@ -456,6 +473,11 @@
                     </exclusion>
                 </exclusions>
             </dependency>
+            <dependency>
+                <groupId>org.openjdk.jmh</groupId>
+                <artifactId>jmh-core</artifactId>
+                <version>${version.jmh}</version>
+            </dependency>
             <dependency>
                 <groupId>org.slf4j</groupId>
                 <artifactId>slf4j-api</artifactId>
@@ -540,7 +562,6 @@
                     <configuration>
                         <bundledSignatures>
                             <bundledSignature>jdk-internal</bundledSignature>
-                            <bundledSignature>jdk-reflection</bundledSignature>
                             <bundledSignature>jdk-system-out</bundledSignature>
                             <!-- Other bundles are available but currently not
                             enabled:
@@ -550,6 +571,10 @@
                             - jdk-deprecated: we compile with `-Xlint:all`,
                               which causes the build to fail when _any_
                               deprecated method is called.
+                            - jdk-reflection: this bundle should probably be
+                              enabled, but currently
+                              `java.lang.reflect.AccessibleObject#setAccessible`
+                              is still called in various places.
                             - jdk-non-portable: the Error Prone integration
                               crucially relies on some of these APIs.
                             - jdk-unsafe: see
@@ -911,7 +936,7 @@
                             <path>
                                 <groupId>com.jakewharton.nopen</groupId>
                                 <artifactId>nopen-checker</artifactId>
-                                <version>${version.nopen-checker}</version>
+                                <version>${version.nopen}</version>
                             </path>
                             <path>
                                 <groupId>com.uber.nullaway</groupId>
@@ -928,6 +953,11 @@
                                 <artifactId>mockito-errorprone</artifactId>
                                 <version>${version.mockito}</version>
                             </path>
+                            <path>
+                                <groupId>org.openjdk.jmh</groupId>
+                                <artifactId>jmh-generator-annprocess</artifactId>
+                                <version>${version.jmh}</version>
+                            </path>
                         </annotationProcessorPaths>
                         <compilerArgs>
                             <arg>--add-exports=jdk.compiler/com.sun.tools.javac.api=ALL-UNNAMED</arg>
@@ -1213,6 +1243,11 @@
                     <artifactId>build-helper-maven-plugin</artifactId>
                     <version>3.4.0</version>
                 </plugin>
+                <plugin>
+                    <groupId>org.codehaus.mojo</groupId>
+                    <artifactId>exec-maven-plugin</artifactId>
+                    <version>3.1.0</version>
+                </plugin>
                 <plugin>
                     <groupId>org.codehaus.mojo</groupId>
                     <artifactId>license-maven-plugin</artifactId>
@@ -1287,6 +1322,7 @@
                                 <!-- -->
                                 GPL-2.0-with-classpath-exception
                                 | CDDL/GPLv2+CE
+                                | GNU General Public License (GPL), version 2, with the Classpath exception
                                 | GNU General Public License, version 2 (GPL2), with the classpath exception
                                 | GNU General Public License, version 2, with the Classpath Exception
                                 | GPL2 w/ CPE
@@ -1725,6 +1761,12 @@
                                     Prone bug pattern checkers, so we enable
                                     all and then selectively deactivate some. -->
                                     -XepAllDisabledChecksAsWarnings
+                                    <!-- Some generated classes violate Error
+                                    Prone bug patterns. We cannot in all cases
+                                    avoid that, so we simply tell Error Prone
+                                    not to warn about generated code. -->
+                                    -XepDisableWarningsInGeneratedCode
+                                    -XepExcludedPaths:\Q${project.build.directory}${file.separator}\E.*
                                     <!-- We don't target Android. -->
                                     -Xep:AndroidJdkLibsChecker:OFF
                                     <!-- XXX: Enable this once we open-source
@@ -1949,5 +1991,66 @@
                 </plugins>
             </build>
         </profile>
+        <profile>
+            <!-- Enables execution of a JMH benchmark. Given a benchmark class
+            `tech.picnic.MyBenchmark`, the following command (executed against
+            the (sub)module in which the benchmark resides) will compile and
+            execute said benchmark:
+
+              mvn process-test-classes -Dverification.skip \
+                -Djmh.run-benchmark=tech.picnic.MyBenchmark
+            -->
+            <id>run-jmh-benchmark</id>
+            <activation>
+                <property>
+                    <name>jmh.run-benchmark</name>
+                </property>
+            </activation>
+            <build>
+                <plugins>
+                    <plugin>
+                        <groupId>org.apache.maven.plugins</groupId>
+                        <artifactId>maven-dependency-plugin</artifactId>
+                        <executions>
+                            <execution>
+                                <id>build-jmh-runtime-classpath</id>
+                                <goals>
+                                    <goal>build-classpath</goal>
+                                </goals>
+                                <configuration>
+                                    <outputProperty>testClasspath</outputProperty>
+                                </configuration>
+                            </execution>
+                        </executions>
+                    </plugin>
+                    <plugin>
+                        <groupId>org.codehaus.mojo</groupId>
+                        <artifactId>exec-maven-plugin</artifactId>
+                        <executions>
+                            <execution>
+                                <id>run-jmh-benchmark</id>
+                                <goals>
+                                    <goal>java</goal>
+                                </goals>
+                                <phase>process-test-classes</phase>
+                                <configuration>
+                                    <classpathScope>test</classpathScope>
+                                    <mainClass>${jmh.run-benchmark}</mainClass>
+                                    <systemProperties>
+                                        <!-- The runtime classpath is defined
+                                        in this way so that any JVMs forked by
+                                        JMH will have the desired classpath. -->
+                                        <systemProperty>
+                                            <key>java.class.path</key>
+                                            <value>${project.build.testOutputDirectory}${path.separator}${project.build.outputDirectory}${path.separator}${testClasspath}</value>
+                                        </systemProperty>
+                                    </systemProperties>
+                                </configuration>
+                            </execution>
+                        </executions>
+                    </plugin>
+                </plugins>
+            </build>
+        </profile>
     </profiles>
 </project>

refaster-compiler/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>refaster-compiler</artifactId>
@@ -36,6 +36,11 @@
             <artifactId>auto-service-annotations</artifactId>
             <scope>provided</scope>
         </dependency>
+        <dependency>
+            <groupId>com.google.code.findbugs</groupId>
+            <artifactId>jsr305</artifactId>
+            <scope>provided</scope>
+        </dependency>
         <dependency>
             <groupId>com.google.guava</groupId>
             <artifactId>guava</artifactId>

refaster-runner/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>refaster-runner</artifactId>
@@ -29,6 +29,11 @@
             <artifactId>error_prone_check_api</artifactId>
             <scope>provided</scope>
         </dependency>
+        <dependency>
+            <groupId>${groupId.error-prone}</groupId>
+            <artifactId>error_prone_core</artifactId>
+            <scope>provided</scope>
+        </dependency>
         <dependency>
             <groupId>${groupId.error-prone}</groupId>
             <artifactId>error_prone_test_helpers</artifactId>
@@ -45,16 +50,33 @@
         <dependency>
             <groupId>${project.groupId}</groupId>
             <artifactId>refaster-support</artifactId>
-            <scope>runtime</scope>
+        </dependency>
+        <dependency>
+            <groupId>com.google.auto</groupId>
+            <artifactId>auto-common</artifactId>
+            <scope>provided</scope>
         </dependency>
         <dependency>
             <groupId>com.google.auto.service</groupId>
             <artifactId>auto-service-annotations</artifactId>
             <scope>provided</scope>
         </dependency>
+        <dependency>
+            <groupId>com.google.auto.value</groupId>
+            <artifactId>auto-value-annotations</artifactId>
+        </dependency>
+        <dependency>
+            <groupId>com.google.code.findbugs</groupId>
+            <artifactId>jsr305</artifactId>
+            <scope>provided</scope>
+        </dependency>
         <dependency>
             <groupId>com.google.guava</groupId>
             <artifactId>guava</artifactId>
+        </dependency>
+        <dependency>
+            <groupId>com.jakewharton.nopen</groupId>
+            <artifactId>nopen-annotations</artifactId>
             <scope>provided</scope>
         </dependency>
         <dependency>
@@ -87,6 +109,11 @@
             <artifactId>junit-jupiter-params</artifactId>
             <scope>test</scope>
         </dependency>
+        <dependency>
+            <groupId>org.openjdk.jmh</groupId>
+            <artifactId>jmh-core</artifactId>
+            <scope>test</scope>
+        </dependency>
     </dependencies>
 
     <build>

refaster-runner/src/main/java/tech/picnic/errorprone/refaster/runner/Node.java

@@ -0,0 +1,126 @@
+package tech.picnic.errorprone.refaster.runner;
+
+import static java.util.Comparator.comparingInt;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Maps;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+/**
+ * A node in an immutable tree.
+ *
+ * <p>The tree's edges are string-labeled, while its leaves store values of type {@code T}.
+ */
+@AutoValue
+abstract class Node<T> {
+  // XXX: Review: should this method accept a `SetMultimap<V, ? extends Set<String>>`, or should
+  // there be such an overload?
+  static <T> Node<T> create(
+      Set<T> values, Function<? super T, ? extends Set<? extends Set<String>>> pathExtractor) {
+    Builder<T> tree = Builder.create();
+    tree.register(values, pathExtractor);
+    return tree.build();
+  }
+
+  abstract ImmutableMap<String, Node<T>> children();
+
+  abstract ImmutableList<T> values();
+
+  // XXX: Consider having `RefasterRuleSelector` already collect the candidate edges into a
+  // `SortedSet`, as that would likely speed up `ImmutableSortedSet#copyOf`.
+  // XXX: If this ^ proves worthwhile, then the test code and benchmark should be updated
+  // accordingly.
+  void collectReachableValues(Set<String> candidateEdges, Consumer<T> sink) {
+    collectReachableValues(ImmutableSortedSet.copyOf(candidateEdges).asList(), sink);
+  }
+
+  private void collectReachableValues(ImmutableList<String> candidateEdges, Consumer<T> sink) {
+    values().forEach(sink);
+
+    if (candidateEdges.isEmpty() || children().isEmpty()) {
+      return;
+    }
+
+    /*
+     * For performance reasons we iterate over the smallest set of edges. In case there are fewer
+     * children than candidate edges we iterate over the former, at the cost of not pruning the set
+     * of candidate edges if a transition is made.
+     */
+    int candidateEdgeCount = candidateEdges.size();
+    if (children().size() < candidateEdgeCount) {
+      for (Map.Entry<String, Node<T>> e : children().entrySet()) {
+        if (candidateEdges.contains(e.getKey())) {
+          e.getValue().collectReachableValues(candidateEdges, sink);
+        }
+      }
+    } else {
+      for (int i = 0; i < candidateEdgeCount; i++) {
+        Node<T> child = children().get(candidateEdges.get(i));
+        if (child != null) {
+          child.collectReachableValues(candidateEdges.subList(i + 1, candidateEdgeCount), sink);
+        }
+      }
+    }
+  }
+
+  @AutoValue
+  @SuppressWarnings("AutoValueImmutableFields" /* Type is used only during `Node` construction. */)
+  abstract static class Builder<T> {
+    private static <T> Builder<T> create() {
+      return new AutoValue_Node_Builder<>(new HashMap<>(), new ArrayList<>());
+    }
+
+    abstract Map<String, Builder<T>> children();
+
+    abstract List<T> values();
+
+    /**
+     * Registers all paths to each of the given values.
+     *
+     * <p>Shorter paths are registered first, so that longer paths can be skipped if a strict prefix
+     * leads to the same value.
+     */
+    private void register(
+        Set<T> values, Function<? super T, ? extends Set<? extends Set<String>>> pathsExtractor) {
+      for (T value : values) {
+        List<? extends Set<String>> paths = new ArrayList<>(pathsExtractor.apply(value));
+        /*
+         * We sort paths by length ascending, so that in case of two paths where one is an initial
+         * prefix of the other, only the former is encoded (thus saving some space).
+         */
+        paths.sort(comparingInt(Set::size));
+        paths.forEach(path -> registerPath(value, ImmutableList.sortedCopyOf(path)));
+      }
+    }
+
+    private void registerPath(T value, ImmutableList<String> path) {
+      if (values().contains(value)) {
+        /* Another (shorter) path already leads to this value. */
+        return;
+      }
+
+      if (path.isEmpty()) {
+        values().add(value);
+      } else {
+        children()
+            .computeIfAbsent(path.get(0), k -> create())
+            .registerPath(value, path.subList(1, path.size()));
+      }
+    }
+
+    private Node<T> build() {
+      return new AutoValue_Node<>(
+          ImmutableMap.copyOf(Maps.transformValues(children(), Builder::build)),
+          ImmutableList.copyOf(values()));
+    }
+  }
+}

refaster-runner/src/main/java/tech/picnic/errorprone/refaster/runner/Refaster.java

@@ -21,7 +21,6 @@ import com.google.common.collect.TreeRangeSet;
 import com.google.errorprone.BugPattern;
 import com.google.errorprone.BugPattern.SeverityLevel;
 import com.google.errorprone.CodeTransformer;
-import com.google.errorprone.CompositeCodeTransformer;
 import com.google.errorprone.ErrorProneFlags;
 import com.google.errorprone.ErrorProneOptions.Severity;
 import com.google.errorprone.SubContext;
@@ -39,6 +38,7 @@ import java.util.Comparator;
 import java.util.List;
 import java.util.Map;
 import java.util.Optional;
+import java.util.Set;
 import java.util.regex.Pattern;
 import java.util.stream.Stream;
 import javax.inject.Inject;
@@ -64,8 +64,7 @@ public final class Refaster extends BugChecker implements CompilationUnitTreeMat
 
   private static final long serialVersionUID = 1L;
 
-  @SuppressWarnings({"java:S1948", "serial"} /* Concrete instance will be `Serializable`. */)
-  private final CodeTransformer codeTransformer;
+  private final RefasterRuleSelector ruleSelector;
 
   /** Instantiates a default {@link Refaster} instance. */
   public Refaster() {
@@ -80,23 +79,28 @@ public final class Refaster extends BugChecker implements CompilationUnitTreeMat
   @Inject
   @VisibleForTesting
   public Refaster(ErrorProneFlags flags) {
-    codeTransformer = createCompositeCodeTransformer(flags);
+    ruleSelector = createRefasterRuleSelector(flags);
   }
 
   @CanIgnoreReturnValue
   @Override
   public Description matchCompilationUnit(CompilationUnitTree tree, VisitorState state) {
+    Set<CodeTransformer> candidateTransformers = ruleSelector.selectCandidateRules(tree);
+
     /* First, collect all matches. */
+    SubContext context = new SubContext(state.context);
     List<Description> matches = new ArrayList<>();
-    try {
-      codeTransformer.apply(state.getPath(), new SubContext(state.context), matches::add);
-    } catch (LinkageError e) {
-      // XXX: This `try/catch` block handles the issue described and resolved in
-      // https://github.com/google/error-prone/pull/2456. Drop this block once that change is
-      // released.
-      // XXX: Find a way to identify that we're running Picnic's Error Prone fork and disable this
-      // fallback if so, as it might hide other bugs.
-      return Description.NO_MATCH;
+    for (CodeTransformer transformer : candidateTransformers) {
+      try {
+        transformer.apply(state.getPath(), context, matches::add);
+      } catch (LinkageError e) {
+        // XXX: This `try/catch` block handles the issue described and resolved in
+        // https://github.com/google/error-prone/pull/2456. Drop this block once that change is
+        // released.
+        // XXX: Find a way to identify that we're running Picnic's Error Prone fork and disable this
+        // fallback if so, as it might hide other bugs.
+        return Description.NO_MATCH;
+      }
     }
     /* Then apply them. */
     applyMatches(matches, ((JCCompilationUnit) tree).endPositions, state);
@@ -204,10 +208,12 @@ public final class Refaster extends BugChecker implements CompilationUnitTreeMat
     return description.fixes.stream().flatMap(fix -> fix.getReplacements(endPositions).stream());
   }
 
-  private static CodeTransformer createCompositeCodeTransformer(ErrorProneFlags flags) {
+  // XXX: Add a flag to disable the optimized `RefasterRuleSelector`. That would allow us to verify
+  // that we're not prematurely pruning rules.
+  private static RefasterRuleSelector createRefasterRuleSelector(ErrorProneFlags flags) {
     ImmutableListMultimap<String, CodeTransformer> allTransformers =
         CodeTransformers.getAllCodeTransformers();
-    return CompositeCodeTransformer.compose(
+    return RefasterRuleSelector.create(
         flags
             .get(INCLUDED_RULES_PATTERN_FLAG)
             .map(Pattern::compile)

refaster-runner/src/main/java/tech/picnic/errorprone/refaster/runner/RefasterRuleSelector.java

@@ -0,0 +1,550 @@
+package tech.picnic.errorprone.refaster.runner;
+
+import static com.google.common.collect.ImmutableSet.toImmutableSet;
+import static java.util.Collections.newSetFromMap;
+import static java.util.stream.Collectors.toCollection;
+
+import com.google.common.collect.ImmutableCollection;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.errorprone.CodeTransformer;
+import com.google.errorprone.CompositeCodeTransformer;
+import com.google.errorprone.refaster.BlockTemplate;
+import com.google.errorprone.refaster.ExpressionTemplate;
+import com.google.errorprone.refaster.RefasterRule;
+import com.google.errorprone.refaster.UAnyOf;
+import com.google.errorprone.refaster.UExpression;
+import com.google.errorprone.refaster.UStatement;
+import com.google.errorprone.refaster.UStaticIdent;
+import com.google.errorprone.refaster.annotation.BeforeTemplate;
+import com.sun.source.tree.AssignmentTree;
+import com.sun.source.tree.BinaryTree;
+import com.sun.source.tree.ClassTree;
+import com.sun.source.tree.CompilationUnitTree;
+import com.sun.source.tree.CompoundAssignmentTree;
+import com.sun.source.tree.ExpressionTree;
+import com.sun.source.tree.IdentifierTree;
+import com.sun.source.tree.MemberReferenceTree;
+import com.sun.source.tree.MemberSelectTree;
+import com.sun.source.tree.MethodTree;
+import com.sun.source.tree.PackageTree;
+import com.sun.source.tree.Tree;
+import com.sun.source.tree.UnaryTree;
+import com.sun.source.tree.VariableTree;
+import com.sun.source.util.TreeScanner;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.jspecify.annotations.Nullable;
+import tech.picnic.errorprone.refaster.AnnotatedCompositeCodeTransformer;
+
+// XXX: Add some examples of which source files would match what templates in the tree.
+// XXX: Consider this text in general.
+/**
+ * A {@link RefasterRuleSelector} algorithm that selects Refaster templates based on the content of
+ * a {@link CompilationUnitTree}.
+ *
+ * <p>The algorithm consists of the following steps:
+ *
+ * <ol>
+ *   <li>Create a {@link Node tree} structure based on the provided Refaster templates.
+ *       <ol>
+ *         <li>Extract all identifiers from the {@link BeforeTemplate}s.
+ *         <li>Sort identifiers lexicographically and collect into a set.
+ *         <li>Add a path to the tree based on the sorted identifiers.
+ *       </ol>
+ *   <li>Extract all identifiers from the {@link CompilationUnitTree} and sort them
+ *       lexicographically.
+ *   <li>Traverse the tree based on the identifiers from the {@link CompilationUnitTree}. Every node
+ *       can contain Refaster templates. Once a node is we found a candidate Refaster template that
+ *       might match some code and will therefore be added to the list of candidates.
+ * </ol>
+ *
+ * <p>This is an example to explain the algorithm. Consider the templates with identifiers; {@code
+ * T1 = [A, B, C]}, {@code T2 = [B]}, and {@code T3 = [B, D]}. This will result in the following
+ * tree structure:
+ *
+ * <pre>{@code
+ * <root>
+ *    ├── A
+ *    │   └── B
+ *    │       └── C -- T1
+ *    └── B         -- T2
+ *        └── D     -- T3
+ * }</pre>
+ *
+ * <p>The tree is traversed based on the identifiers in the {@link CompilationUnitTree}. When a node
+ * containing a template is reached, we can be certain that the identifiers from the {@link
+ * BeforeTemplate} are at least present in the {@link CompilationUnitTree}.
+ *
+ * <p>Since the identifiers are sorted, we can skip parts of the {@link Node tree} while we are
+ * traversing it. Instead of trying to match all Refaster templates against every expression in a
+ * {@link CompilationUnitTree} we now only matching a subset of the templates that at least have a
+ * chance of matching. As a result, the performance of Refaster increases significantly.
+ */
+final class RefasterRuleSelector {
+  private final Node<CodeTransformer> codeTransformers;
+
+  private RefasterRuleSelector(Node<CodeTransformer> codeTransformers) {
+    this.codeTransformers = codeTransformers;
+  }
+
+  /**
+   * Instantiates a new {@link RefasterRuleSelector} backed by the given {@link CodeTransformer}s.
+   */
+  static RefasterRuleSelector create(ImmutableCollection<CodeTransformer> refasterRules) {
+    Map<CodeTransformer, ImmutableSet<ImmutableSet<String>>> ruleIdentifiersByTransformer =
+        indexRuleIdentifiers(refasterRules);
+    return new RefasterRuleSelector(
+        Node.create(ruleIdentifiersByTransformer.keySet(), ruleIdentifiersByTransformer::get));
+  }
+
+  /**
+   * Retrieves a set of Refaster templates that can possibly match based on a {@link
+   * CompilationUnitTree}.
+   *
+   * @param tree The {@link CompilationUnitTree} for which candidate Refaster templates are
+   *     selected.
+   * @return Set of Refaster templates that can possibly match in the provided {@link
+   *     CompilationUnitTree}.
+   */
+  Set<CodeTransformer> selectCandidateRules(CompilationUnitTree tree) {
+    Set<CodeTransformer> candidateRules = newSetFromMap(new IdentityHashMap<>());
+    codeTransformers.collectReachableValues(extractSourceIdentifiers(tree), candidateRules::add);
+    return candidateRules;
+  }
+
+  private static Map<CodeTransformer, ImmutableSet<ImmutableSet<String>>> indexRuleIdentifiers(
+      ImmutableCollection<CodeTransformer> codeTransformers) {
+    IdentityHashMap<CodeTransformer, ImmutableSet<ImmutableSet<String>>> identifiers =
+        new IdentityHashMap<>();
+    for (CodeTransformer transformer : codeTransformers) {
+      collectRuleIdentifiers(transformer, identifiers);
+    }
+    return identifiers;
+  }
+
+  private static void collectRuleIdentifiers(
+      CodeTransformer codeTransformer,
+      Map<CodeTransformer, ImmutableSet<ImmutableSet<String>>> identifiers) {
+    if (codeTransformer instanceof CompositeCodeTransformer) {
+      for (CodeTransformer transformer :
+          ((CompositeCodeTransformer) codeTransformer).transformers()) {
+        collectRuleIdentifiers(transformer, identifiers);
+      }
+    } else if (codeTransformer instanceof AnnotatedCompositeCodeTransformer) {
+      AnnotatedCompositeCodeTransformer annotatedTransformer =
+          (AnnotatedCompositeCodeTransformer) codeTransformer;
+      for (Map.Entry<CodeTransformer, ImmutableSet<ImmutableSet<String>>> e :
+          indexRuleIdentifiers(annotatedTransformer.transformers()).entrySet()) {
+        identifiers.put(annotatedTransformer.withTransformer(e.getKey()), e.getValue());
+      }
+    } else if (codeTransformer instanceof RefasterRule) {
+      identifiers.put(
+          codeTransformer, extractRuleIdentifiers((RefasterRule<?, ?>) codeTransformer));
+    } else {
+      /* Unrecognized `CodeTransformer` types are indexed such that they always apply. */
+      identifiers.put(codeTransformer, ImmutableSet.of(ImmutableSet.of()));
+    }
+  }
+
+  // XXX: Consider decomposing `RefasterRule`s such that each rule has exactly one
+  // `@BeforeTemplate`.
+  private static ImmutableSet<ImmutableSet<String>> extractRuleIdentifiers(
+      RefasterRule<?, ?> refasterRule) {
+    ImmutableSet.Builder<ImmutableSet<String>> results = ImmutableSet.builder();
+
+    for (Object template : RefasterIntrospection.getBeforeTemplates(refasterRule)) {
+      if (template instanceof ExpressionTemplate) {
+        UExpression expr = RefasterIntrospection.getExpression((ExpressionTemplate) template);
+        results.addAll(extractRuleIdentifiers(ImmutableList.of(expr)));
+      } else if (template instanceof BlockTemplate) {
+        ImmutableList<UStatement> statements =
+            RefasterIntrospection.getTemplateStatements((BlockTemplate) template);
+        results.addAll(extractRuleIdentifiers(statements));
+      } else {
+        throw new IllegalStateException(
+            String.format("Unexpected template type '%s'", template.getClass()));
+      }
+    }
+
+    return results.build();
+  }
+
+  // XXX: Consider interning the strings (once a benchmark is in place).
+  private static ImmutableSet<ImmutableSet<String>> extractRuleIdentifiers(
+      ImmutableList<? extends Tree> trees) {
+    List<Set<String>> identifierCombinations = new ArrayList<>();
+    identifierCombinations.add(new HashSet<>());
+    RuleIdentifierExtractor.INSTANCE.scan(trees, identifierCombinations);
+    return identifierCombinations.stream().map(ImmutableSet::copyOf).collect(toImmutableSet());
+  }
+
+  private static Set<String> extractSourceIdentifiers(Tree tree) {
+    Set<String> identifiers = new HashSet<>();
+    SourceIdentifierExtractor.INSTANCE.scan(tree, identifiers);
+    return identifiers;
+  }
+
+  /**
+   * Returns a unique string representation of the given {@link Tree.Kind}.
+   *
+   * @return A string representation of the operator, if known
+   * @throws IllegalArgumentException If the given input is not supported.
+   */
+  // XXX: Extend list to cover remaining cases; at least for any `Kind` that may appear in a
+  // Refaster template. (E.g. keywords such as `if`, `instanceof`, `new`, ...)
+  private static String treeKindToString(Tree.Kind kind) {
+    switch (kind) {
+      case ASSIGNMENT:
+        return "=";
+      case POSTFIX_INCREMENT:
+        return "x++";
+      case PREFIX_INCREMENT:
+        return "++x";
+      case POSTFIX_DECREMENT:
+        return "x--";
+      case PREFIX_DECREMENT:
+        return "--x";
+      case UNARY_PLUS:
+        return "+x";
+      case UNARY_MINUS:
+        return "-x";
+      case BITWISE_COMPLEMENT:
+        return "~";
+      case LOGICAL_COMPLEMENT:
+        return "!";
+      case MULTIPLY:
+        return "*";
+      case DIVIDE:
+        return "/";
+      case REMAINDER:
+        return "%";
+      case PLUS:
+        return "+";
+      case MINUS:
+        return "-";
+      case LEFT_SHIFT:
+        return "<<";
+      case RIGHT_SHIFT:
+        return ">>";
+      case UNSIGNED_RIGHT_SHIFT:
+        return ">>>";
+      case LESS_THAN:
+        return "<";
+      case GREATER_THAN:
+        return ">";
+      case LESS_THAN_EQUAL:
+        return "<=";
+      case GREATER_THAN_EQUAL:
+        return ">=";
+      case EQUAL_TO:
+        return "==";
+      case NOT_EQUAL_TO:
+        return "!=";
+      case AND:
+        return "&";
+      case XOR:
+        return "^";
+      case OR:
+        return "|";
+      case CONDITIONAL_AND:
+        return "&&";
+      case CONDITIONAL_OR:
+        return "||";
+      case MULTIPLY_ASSIGNMENT:
+        return "*=";
+      case DIVIDE_ASSIGNMENT:
+        return "/=";
+      case REMAINDER_ASSIGNMENT:
+        return "%=";
+      case PLUS_ASSIGNMENT:
+        return "+=";
+      case MINUS_ASSIGNMENT:
+        return "-=";
+      case LEFT_SHIFT_ASSIGNMENT:
+        return "<<=";
+      case RIGHT_SHIFT_ASSIGNMENT:
+        return ">>=";
+      case UNSIGNED_RIGHT_SHIFT_ASSIGNMENT:
+        return ">>>=";
+      case AND_ASSIGNMENT:
+        return "&=";
+      case XOR_ASSIGNMENT:
+        return "^=";
+      case OR_ASSIGNMENT:
+        return "|=";
+      default:
+        throw new IllegalStateException("Cannot convert Tree.Kind to a String: " + kind);
+    }
+  }
+
+  private static final class RefasterIntrospection {
+    private static final String UCLASS_IDENT_FQCN = "com.google.errorprone.refaster.UClassIdent";
+    private static final Class<?> UCLASS_IDENT = getClass(UCLASS_IDENT_FQCN);
+    private static final Method METHOD_REFASTER_RULE_BEFORE_TEMPLATES =
+        getMethod(RefasterRule.class, "beforeTemplates");
+    private static final Method METHOD_EXPRESSION_TEMPLATE_EXPRESSION =
+        getMethod(ExpressionTemplate.class, "expression");
+    private static final Method METHOD_BLOCK_TEMPLATE_TEMPLATE_STATEMENTS =
+        getMethod(BlockTemplate.class, "templateStatements");
+    private static final Method METHOD_USTATIC_IDENT_CLASS_IDENT =
+        getMethod(UStaticIdent.class, "classIdent");
+    private static final Method METHOD_UCLASS_IDENT_GET_TOP_LEVEL_CLASS =
+        getMethod(UCLASS_IDENT, "getTopLevelClass");
+    private static final Method METHOD_UANY_OF_EXPRESSIONS = getMethod(UAnyOf.class, "expressions");
+
+    static boolean isUClassIdent(IdentifierTree tree) {
+      return UCLASS_IDENT.isAssignableFrom(tree.getClass());
+    }
+
+    static ImmutableList<?> getBeforeTemplates(RefasterRule<?, ?> refasterRule) {
+      return invokeMethod(METHOD_REFASTER_RULE_BEFORE_TEMPLATES, refasterRule);
+    }
+
+    static UExpression getExpression(ExpressionTemplate template) {
+      return invokeMethod(METHOD_EXPRESSION_TEMPLATE_EXPRESSION, template);
+    }
+
+    static ImmutableList<UStatement> getTemplateStatements(BlockTemplate template) {
+      return invokeMethod(METHOD_BLOCK_TEMPLATE_TEMPLATE_STATEMENTS, template);
+    }
+
+    static IdentifierTree getClassIdent(UStaticIdent tree) {
+      return invokeMethod(METHOD_USTATIC_IDENT_CLASS_IDENT, tree);
+    }
+
+    // Arguments to this method must actually be of the package-private type `UClassIdent`.
+    static String getTopLevelClass(IdentifierTree uClassIdent) {
+      return invokeMethod(METHOD_UCLASS_IDENT_GET_TOP_LEVEL_CLASS, uClassIdent);
+    }
+
+    static ImmutableList<UExpression> getExpressions(UAnyOf tree) {
+      return invokeMethod(METHOD_UANY_OF_EXPRESSIONS, tree);
+    }
+
+    private static Class<?> getClass(String fqcn) {
+      try {
+        return RefasterIntrospection.class.getClassLoader().loadClass(fqcn);
+      } catch (ClassNotFoundException e) {
+        throw new IllegalStateException(String.format("Failed to load class `%s`", fqcn), e);
+      }
+    }
+
+    private static Method getMethod(Class<?> clazz, String methodName) {
+      try {
+        Method method = clazz.getDeclaredMethod(methodName);
+        method.setAccessible(true);
+        return method;
+      } catch (NoSuchMethodException e) {
+        throw new IllegalStateException(
+            String.format("No method `%s` on class `%s`", methodName, clazz.getName()), e);
+      }
+    }
+
+    @SuppressWarnings({"TypeParameterUnusedInFormals", "unchecked"})
+    private static <T> T invokeMethod(Method method, Object instance) {
+      try {
+        return (T) method.invoke(instance);
+      } catch (IllegalAccessException | InvocationTargetException e) {
+        throw new IllegalStateException(String.format("Failed to invoke method `%s`", method), e);
+      }
+    }
+  }
+
+  private static final class RuleIdentifierExtractor
+      extends TreeScanner<@Nullable Void, List<Set<String>>> {
+    private static final RuleIdentifierExtractor INSTANCE = new RuleIdentifierExtractor();
+
+    @Override
+    public @Nullable Void visitIdentifier(
+        IdentifierTree node, List<Set<String>> identifierCombinations) {
+      // XXX: Also include the package name if not `java.lang`; it must be present.
+      if (RefasterIntrospection.isUClassIdent(node)) {
+        for (Set<String> ids : identifierCombinations) {
+          ids.add(getSimpleName(RefasterIntrospection.getTopLevelClass(node)));
+          ids.add(getIdentifier(node));
+        }
+      } else if (node instanceof UStaticIdent) {
+        IdentifierTree subNode = RefasterIntrospection.getClassIdent((UStaticIdent) node);
+        for (Set<String> ids : identifierCombinations) {
+          ids.add(getSimpleName(RefasterIntrospection.getTopLevelClass(subNode)));
+          ids.add(getIdentifier(subNode));
+          ids.add(node.getName().toString());
+        }
+      }
+
+      return null;
+    }
+
+    private static String getIdentifier(IdentifierTree tree) {
+      return getSimpleName(tree.getName().toString());
+    }
+
+    private static String getSimpleName(String fqcn) {
+      int index = fqcn.lastIndexOf('.');
+      return index < 0 ? fqcn : fqcn.substring(index + 1);
+    }
+
+    @Override
+    public @Nullable Void visitMemberReference(
+        MemberReferenceTree node, List<Set<String>> identifierCombinations) {
+      super.visitMemberReference(node, identifierCombinations);
+      String id = node.getName().toString();
+      identifierCombinations.forEach(ids -> ids.add(id));
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitMemberSelect(
+        MemberSelectTree node, List<Set<String>> identifierCombinations) {
+      super.visitMemberSelect(node, identifierCombinations);
+      String id = node.getIdentifier().toString();
+      identifierCombinations.forEach(ids -> ids.add(id));
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitAssignment(
+        AssignmentTree node, List<Set<String>> identifierCombinations) {
+      registerOperator(node, identifierCombinations);
+      return super.visitAssignment(node, identifierCombinations);
+    }
+
+    @Override
+    public @Nullable Void visitCompoundAssignment(
+        CompoundAssignmentTree node, List<Set<String>> identifierCombinations) {
+      registerOperator(node, identifierCombinations);
+      return super.visitCompoundAssignment(node, identifierCombinations);
+    }
+
+    @Override
+    public @Nullable Void visitUnary(UnaryTree node, List<Set<String>> identifierCombinations) {
+      registerOperator(node, identifierCombinations);
+      return super.visitUnary(node, identifierCombinations);
+    }
+
+    @Override
+    public @Nullable Void visitBinary(BinaryTree node, List<Set<String>> identifierCombinations) {
+      registerOperator(node, identifierCombinations);
+      return super.visitBinary(node, identifierCombinations);
+    }
+
+    private static void registerOperator(
+        ExpressionTree node, List<Set<String>> identifierCombinations) {
+      String id = treeKindToString(node.getKind());
+      identifierCombinations.forEach(ids -> ids.add(id));
+    }
+
+    @Override
+    public @Nullable Void visitOther(Tree node, List<Set<String>> identifierCombinations) {
+      if (node instanceof UAnyOf) {
+        List<Set<String>> base = copy(identifierCombinations);
+        identifierCombinations.clear();
+
+        for (UExpression expr : RefasterIntrospection.getExpressions((UAnyOf) node)) {
+          List<Set<String>> branch = copy(base);
+          scan(expr, branch);
+          identifierCombinations.addAll(branch);
+        }
+      }
+
+      return null;
+    }
+
+    private static List<Set<String>> copy(List<Set<String>> identifierCombinations) {
+      return identifierCombinations.stream()
+          .map(HashSet::new)
+          .collect(toCollection(ArrayList::new));
+    }
+  }
+
+  private static final class SourceIdentifierExtractor
+      extends TreeScanner<@Nullable Void, Set<String>> {
+    private static final SourceIdentifierExtractor INSTANCE = new SourceIdentifierExtractor();
+
+    @Override
+    public @Nullable Void visitPackage(PackageTree node, Set<String> identifiers) {
+      /* Refaster rules never match package declarations. */
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitClass(ClassTree node, Set<String> identifiers) {
+      /*
+       * Syntactic details of a class declaration other than the definition of its members do not
+       * need to be reflected in a Refaster rule for it to apply to the class's code.
+       */
+      return scan(node.getMembers(), identifiers);
+    }
+
+    @Override
+    public @Nullable Void visitMethod(MethodTree node, Set<String> identifiers) {
+      /*
+       * Syntactic details of a method declaration other than its body do not need to be reflected
+       * in a Refaster rule for it to apply to the method's code.
+       */
+      return scan(node.getBody(), identifiers);
+    }
+
+    @Override
+    public @Nullable Void visitVariable(VariableTree node, Set<String> identifiers) {
+      /* A variable's modifiers and name do not influence where a Refaster rule matches. */
+      return reduce(scan(node.getInitializer(), identifiers), scan(node.getType(), identifiers));
+    }
+
+    @Override
+    public @Nullable Void visitIdentifier(IdentifierTree node, Set<String> identifiers) {
+      identifiers.add(node.getName().toString());
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitMemberReference(MemberReferenceTree node, Set<String> identifiers) {
+      super.visitMemberReference(node, identifiers);
+      identifiers.add(node.getName().toString());
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitMemberSelect(MemberSelectTree node, Set<String> identifiers) {
+      super.visitMemberSelect(node, identifiers);
+      identifiers.add(node.getIdentifier().toString());
+      return null;
+    }
+
+    @Override
+    public @Nullable Void visitAssignment(AssignmentTree node, Set<String> identifiers) {
+      registerOperator(node, identifiers);
+      return super.visitAssignment(node, identifiers);
+    }
+
+    @Override
+    public @Nullable Void visitCompoundAssignment(
+        CompoundAssignmentTree node, Set<String> identifiers) {
+      registerOperator(node, identifiers);
+      return super.visitCompoundAssignment(node, identifiers);
+    }
+
+    @Override
+    public @Nullable Void visitUnary(UnaryTree node, Set<String> identifiers) {
+      registerOperator(node, identifiers);
+      return super.visitUnary(node, identifiers);
+    }
+
+    @Override
+    public @Nullable Void visitBinary(BinaryTree node, Set<String> identifiers) {
+      registerOperator(node, identifiers);
+      return super.visitBinary(node, identifiers);
+    }
+
+    private static void registerOperator(ExpressionTree node, Set<String> identifiers) {
+      identifiers.add(treeKindToString(node.getKind()));
+    }
+  }
+}

refaster-runner/src/test/java/tech/picnic/errorprone/refaster/runner/NodeBenchmark.java

@@ -0,0 +1,81 @@
+package tech.picnic.errorprone.refaster.runner;
+
+import static com.google.common.collect.ImmutableListMultimap.flatteningToImmutableListMultimap;
+import static java.util.function.Function.identity;
+
+import com.google.common.collect.ImmutableListMultimap;
+import com.jakewharton.nopen.annotation.Open;
+import java.util.Collection;
+import java.util.Map;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import java.util.regex.Pattern;
+import java.util.stream.Stream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+import org.openjdk.jmh.runner.Runner;
+import org.openjdk.jmh.runner.RunnerException;
+import org.openjdk.jmh.runner.options.OptionsBuilder;
+import tech.picnic.errorprone.refaster.runner.NodeTestCase.NodeTestCaseEntry;
+
+@Open
+@State(Scope.Benchmark)
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@Fork(jvmArgs = {"-Xms1G", "-Xmx1G"})
+@Warmup(iterations = 5)
+@Measurement(iterations = 10)
+public class NodeBenchmark {
+  @SuppressWarnings("NullAway" /* Initialized by `@Setup` method. */)
+  private ImmutableListMultimap<NodeTestCase<Integer>, NodeTestCaseEntry<Integer>> testCases;
+
+  public static void main(String[] args) throws RunnerException {
+    String testRegex = Pattern.quote(NodeBenchmark.class.getCanonicalName());
+    new Runner(new OptionsBuilder().include(testRegex).forks(1).build()).run();
+  }
+
+  @Setup
+  public final void setUp() {
+    Random random = new Random(0);
+
+    testCases =
+        Stream.of(
+                NodeTestCase.generate(100, 5, 10, 10, random),
+                NodeTestCase.generate(100, 5, 10, 100, random),
+                NodeTestCase.generate(100, 5, 10, 1000, random),
+                NodeTestCase.generate(1000, 10, 20, 10, random),
+                NodeTestCase.generate(1000, 10, 20, 100, random),
+                NodeTestCase.generate(1000, 10, 20, 1000, random),
+                NodeTestCase.generate(1000, 10, 20, 10000, random))
+            .collect(
+                flatteningToImmutableListMultimap(
+                    identity(), testCase -> testCase.generateTestCaseEntries(random)));
+  }
+
+  @Benchmark
+  public final void create(Blackhole bh) {
+    for (NodeTestCase<Integer> testCase : testCases.keySet()) {
+      bh.consume(testCase.buildTree());
+    }
+  }
+
+  @Benchmark
+  public final void collectReachableValues(Blackhole bh) {
+    for (Map.Entry<NodeTestCase<Integer>, Collection<NodeTestCaseEntry<Integer>>> e :
+        testCases.asMap().entrySet()) {
+      Node<Integer> tree = e.getKey().buildTree();
+      for (NodeTestCaseEntry<Integer> testCaseEntry : e.getValue()) {
+        tree.collectReachableValues(testCaseEntry.candidateEdges(), bh::consume);
+      }
+    }
+  }
+}

refaster-runner/src/test/java/tech/picnic/errorprone/refaster/runner/NodeTest.java

@@ -0,0 +1,47 @@
+package tech.picnic.errorprone.refaster.runner;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.junit.jupiter.params.provider.Arguments.arguments;
+
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Random;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+final class NodeTest {
+  private static Stream<Arguments> collectReachableValuesTestCases() {
+    Random random = new Random(0);
+
+    return Stream.of(
+            NodeTestCase.generate(0, 0, 0, 0, random),
+            NodeTestCase.generate(1, 1, 1, 1, random),
+            NodeTestCase.generate(2, 2, 2, 10, random),
+            NodeTestCase.generate(10, 2, 5, 10, random),
+            NodeTestCase.generate(10, 2, 5, 100, random),
+            NodeTestCase.generate(100, 5, 10, 100, random),
+            NodeTestCase.generate(100, 5, 10, 1000, random))
+        .flatMap(
+            testCase -> {
+              Node<Integer> tree = testCase.buildTree();
+              return testCase
+                  .generateTestCaseEntries(random)
+                  .map(e -> arguments(tree, e.candidateEdges(), e.reachableValues()));
+            });
+  }
+
+  @MethodSource("collectReachableValuesTestCases")
+  @ParameterizedTest
+  void collectReachableValues(
+      Node<Integer> tree,
+      ImmutableSet<String> candidateEdges,
+      Collection<Integer> expectedReachable) {
+    List<Integer> actualReachable = new ArrayList<>();
+    tree.collectReachableValues(candidateEdges, actualReachable::add);
+    assertThat(actualReachable).hasSameElementsAs(expectedReachable);
+  }
+}

refaster-runner/src/test/java/tech/picnic/errorprone/refaster/runner/NodeTestCase.java

@@ -0,0 +1,140 @@
+package tech.picnic.errorprone.refaster.runner;
+
+import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static com.google.common.collect.ImmutableSet.toImmutableSet;
+import static com.google.common.collect.ImmutableSetMultimap.flatteningToImmutableSetMultimap;
+import static java.util.function.Function.identity;
+import static java.util.stream.Collectors.collectingAndThen;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableCollection;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSetMultimap;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Optional;
+import java.util.Random;
+import java.util.stream.Stream;
+
+@AutoValue
+abstract class NodeTestCase<V> {
+  static NodeTestCase<Integer> generate(
+      int entryCount, int maxPathCount, int maxPathLength, int pathValueDomainSize, Random random) {
+    return random
+        .ints(entryCount)
+        .boxed()
+        .collect(
+            collectingAndThen(
+                flatteningToImmutableSetMultimap(
+                    identity(),
+                    i ->
+                        random
+                            .ints(random.nextInt(maxPathCount + 1))
+                            .mapToObj(
+                                p ->
+                                    random
+                                        .ints(
+                                            random.nextInt(maxPathLength + 1),
+                                            0,
+                                            pathValueDomainSize)
+                                        .mapToObj(String::valueOf)
+                                        .collect(toImmutableSet()))),
+                AutoValue_NodeTestCase::new));
+  }
+
+  abstract ImmutableSetMultimap<V, ImmutableSet<String>> input();
+
+  final Node<V> buildTree() {
+    return Node.create(input().keySet(), input()::get);
+  }
+
+  final Stream<NodeTestCaseEntry<V>> generateTestCaseEntries(Random random) {
+    return generatePathTestCases(input(), random);
+  }
+
+  private static <V> Stream<NodeTestCaseEntry<V>> generatePathTestCases(
+      ImmutableSetMultimap<V, ImmutableSet<String>> treeInput, Random random) {
+    ImmutableSet<String> allEdges =
+        treeInput.values().stream().flatMap(ImmutableSet::stream).collect(toImmutableSet());
+
+    return Stream.concat(
+            Stream.of(ImmutableSet.<String>of()), shuffle(treeInput.values(), random).stream())
+        // XXX: Use `random.nextInt(20, 100)` once we no longer target JDK 11. (And consider
+        // introducing a Refaster template for this case.)
+        .limit(20 + random.nextInt(80))
+        .flatMap(edges -> generateVariations(edges, allEdges, "unused", random))
+        .distinct()
+        .map(edges -> createTestCaseEntry(treeInput, edges));
+  }
+
+  private static <T> Stream<ImmutableSet<T>> generateVariations(
+      ImmutableSet<T> baseEdges, ImmutableSet<T> allEdges, T unusedEdge, Random random) {
+    Optional<T> knownEdge = selectRandomElement(allEdges, random);
+
+    return Stream.of(
+            random.nextBoolean() ? null : baseEdges,
+            random.nextBoolean() ? null : shuffle(baseEdges, random),
+            random.nextBoolean() ? null : insertValue(baseEdges, unusedEdge, random),
+            baseEdges.isEmpty() || random.nextBoolean()
+                ? null
+                : randomStrictSubset(baseEdges, random),
+            baseEdges.isEmpty() || random.nextBoolean()
+                ? null
+                : insertValue(randomStrictSubset(baseEdges, random), unusedEdge, random),
+            baseEdges.isEmpty() || random.nextBoolean()
+                ? null
+                : knownEdge
+                    .map(edge -> insertValue(randomStrictSubset(baseEdges, random), edge, random))
+                    .orElse(null))
+        .filter(Objects::nonNull);
+  }
+
+  private static <T> Optional<T> selectRandomElement(ImmutableSet<T> collection, Random random) {
+    return collection.isEmpty()
+        ? Optional.empty()
+        : Optional.of(collection.asList().get(random.nextInt(collection.size())));
+  }
+
+  private static <T> ImmutableSet<T> shuffle(ImmutableCollection<T> values, Random random) {
+    List<T> allValues = new ArrayList<>(values);
+    Collections.shuffle(allValues, random);
+    return ImmutableSet.copyOf(allValues);
+  }
+
+  private static <T> ImmutableSet<T> insertValue(
+      ImmutableSet<T> values, T extraValue, Random random) {
+    List<T> allValues = new ArrayList<>(values);
+    allValues.add(random.nextInt(values.size() + 1), extraValue);
+    return ImmutableSet.copyOf(allValues);
+  }
+
+  private static <T> ImmutableSet<T> randomStrictSubset(ImmutableSet<T> values, Random random) {
+    checkArgument(!values.isEmpty(), "Cannot select strict subset of random collection");
+
+    List<T> allValues = new ArrayList<>(values);
+    Collections.shuffle(allValues, random);
+    return ImmutableSet.copyOf(allValues.subList(0, random.nextInt(allValues.size())));
+  }
+
+  private static <V> NodeTestCaseEntry<V> createTestCaseEntry(
+      ImmutableSetMultimap<V, ImmutableSet<String>> treeInput, ImmutableSet<String> edges) {
+    return new AutoValue_NodeTestCase_NodeTestCaseEntry<>(
+        edges,
+        treeInput.asMap().entrySet().stream()
+            .filter(e -> e.getValue().stream().anyMatch(edges::containsAll))
+            .map(Map.Entry::getKey)
+            .collect(toImmutableList()));
+  }
+
+  @AutoValue
+  abstract static class NodeTestCaseEntry<V> {
+    abstract ImmutableSet<String> candidateEdges();
+
+    abstract ImmutableList<V> reachableValues();
+  }
+}

refaster-support/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>refaster-support</artifactId>
@@ -51,6 +51,11 @@
             <artifactId>auto-value-annotations</artifactId>
             <scope>provided</scope>
         </dependency>
+        <dependency>
+            <groupId>com.google.code.findbugs</groupId>
+            <artifactId>jsr305</artifactId>
+            <scope>provided</scope>
+        </dependency>
         <dependency>
             <groupId>com.google.guava</groupId>
             <artifactId>guava</artifactId>

refaster-support/src/main/java/tech/picnic/errorprone/refaster/AnnotatedCompositeCodeTransformer.java

@@ -46,7 +46,12 @@ public abstract class AnnotatedCompositeCodeTransformer implements CodeTransform
 
   abstract String packageName();
 
-  abstract ImmutableList<CodeTransformer> transformers();
+  /**
+   * Returns the {@link CodeTransformer}s to which actual code transformation is delegated.
+   *
+   * @return The transformers to which this instance's {@link #annotations() annotations} apply.
+   */
+  public abstract ImmutableList<CodeTransformer> transformers();
 
   @Override
   @SuppressWarnings("java:S3038" /* All AutoValue properties must be specified explicitly. */)
@@ -67,6 +72,19 @@ public abstract class AnnotatedCompositeCodeTransformer implements CodeTransform
     return new AutoValue_AnnotatedCompositeCodeTransformer(packageName, transformers, annotations);
   }
 
+  /**
+   * Creates a derivative {@link AnnotatedCompositeCodeTransformer} that wraps only the given
+   * transformer.
+   *
+   * @param transformer The {@link CodeTransformer} to which the new instance will delegate
+   *     transformations.
+   * @return A non-{@code null} {@link AnnotatedCompositeCodeTransformer} with the same {@link
+   *     #packageName() package name} and {@link #annotations() annotations} as this transformer.
+   */
+  public AnnotatedCompositeCodeTransformer withTransformer(CodeTransformer transformer) {
+    return create(packageName(), ImmutableList.of(transformer), annotations());
+  }
+
   @Override
   public final void apply(TreePath path, Context context, DescriptionListener listener) {
     for (CodeTransformer transformer : transformers()) {

refaster-support/src/main/java/tech/picnic/errorprone/refaster/ErrorProneFork.java

@@ -0,0 +1,45 @@
+package tech.picnic.errorprone.refaster;
+
+import com.google.errorprone.ErrorProneOptions;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.lang.reflect.Modifier;
+import java.util.Arrays;
+import java.util.Optional;
+
+/**
+ * Utility class that enables the runtime to determine whether Picnic's fork of Error Prone is on
+ * the classpath.
+ *
+ * @see <a href="https://github.com/PicnicSupermarket/error-prone">Picnic's Error Prone fork</a>
+ */
+public final class ErrorProneFork {
+  private static final Optional<Method> ERROR_PRONE_OPTIONS_IS_SUGGESTIONS_AS_WARNINGS_METHOD =
+      Arrays.stream(ErrorProneOptions.class.getDeclaredMethods())
+          .filter(m -> Modifier.isPublic(m.getModifiers()))
+          .filter(m -> "isSuggestionsAsWarnings".equals(m.getName()))
+          .findFirst();
+
+  private ErrorProneFork() {}
+
+  /**
+   * Tells whether the custom {@code -XepAllSuggestionsAsWarnings} flag is set.
+   *
+   * @param options The currently active Error Prone options.
+   * @return {@code true} iff the Error Prone fork is available and the aforementioned flag is set.
+   * @see <a href="https://github.com/google/error-prone/pull/3301">google/error-prone#3301</a>
+   */
+  public static boolean isSuggestionsAsWarningsEnabled(ErrorProneOptions options) {
+    return ERROR_PRONE_OPTIONS_IS_SUGGESTIONS_AS_WARNINGS_METHOD
+        .filter(m -> Boolean.TRUE.equals(invoke(m, options)))
+        .isPresent();
+  }
+
+  private static Object invoke(Method method, Object obj, Object... args) {
+    try {
+      return method.invoke(obj, args);
+    } catch (IllegalAccessException | InvocationTargetException e) {
+      throw new IllegalStateException(String.format("Failed to invoke method '%s'", method), e);
+    }
+  }
+}

refaster-support/src/test/java/tech/picnic/errorprone/refaster/ErrorProneForkTest.java

@@ -0,0 +1,55 @@
+package tech.picnic.errorprone.refaster;
+
+import static com.google.errorprone.BugPattern.SeverityLevel.ERROR;
+
+import com.google.errorprone.BugPattern;
+import com.google.errorprone.CompilationTestHelper;
+import com.google.errorprone.ErrorProneOptions;
+import com.google.errorprone.VisitorState;
+import com.google.errorprone.bugpatterns.BugChecker;
+import com.google.errorprone.bugpatterns.BugChecker.ClassTreeMatcher;
+import com.google.errorprone.matchers.Description;
+import com.sun.source.tree.ClassTree;
+import org.junit.jupiter.api.Test;
+
+final class ErrorProneForkTest {
+  @Test
+  void isSuggestionsAsWarningsEnabledWithoutFlag() {
+    CompilationTestHelper.newInstance(TestChecker.class, getClass())
+        .addSourceLines(
+            "A.java",
+            "// BUG: Diagnostic contains: Suggestions as warnings enabled: false",
+            "class A {}")
+        .doTest();
+  }
+
+  @Test
+  void isSuggestionsAsWarningsEnabledWithFlag() {
+    CompilationTestHelper.newInstance(TestChecker.class, getClass())
+        .setArgs("-XepAllSuggestionsAsWarnings")
+        .addSourceLines(
+            "A.java",
+            "// BUG: Diagnostic contains: Suggestions as warnings enabled: true",
+            "class A {}")
+        .doTest();
+  }
+
+  /**
+   * A {@link BugChecker} that reports the result of {@link
+   * ErrorProneFork#isSuggestionsAsWarningsEnabled(ErrorProneOptions)}.
+   */
+  @BugPattern(summary = "Flags classes with a custom error message", severity = ERROR)
+  public static final class TestChecker extends BugChecker implements ClassTreeMatcher {
+    private static final long serialVersionUID = 1L;
+
+    @Override
+    public Description matchClass(ClassTree tree, VisitorState state) {
+      return buildDescription(tree)
+          .setMessage(
+              String.format(
+                  "Suggestions as warnings enabled: %s",
+                  ErrorProneFork.isSuggestionsAsWarningsEnabled(state.errorProneOptions())))
+          .build();
+    }
+  }
+}

refaster-test-support/pom.xml

@@ -5,7 +5,7 @@
     <parent>
         <groupId>tech.picnic.error-prone-support</groupId>
         <artifactId>error-prone-support</artifactId>
-        <version>0.12.1-SNAPSHOT</version>
+        <version>0.13.2-SNAPSHOT</version>
     </parent>
 
     <artifactId>refaster-test-support</artifactId>