[KeepAnno] Support for extracting rules with bindings.

This adds support for bindings with backrefs to classes. Methods
will be added in follow-up work.

Bug: b/248408342
Change-Id: Iedac2670f6c681e5a6dbbef606b89c6f765f3e93
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
index bb8dd5f..9fdf1f4 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeReader.java
@@ -22,6 +22,7 @@
 import com.android.tools.r8.keepanno.ast.KeepFieldPattern;
 import com.android.tools.r8.keepanno.ast.KeepFieldTypePattern;
 import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepItemReference;
 import com.android.tools.r8.keepanno.ast.KeepMemberPattern;
 import com.android.tools.r8.keepanno.ast.KeepMethodNamePattern;
 import com.android.tools.r8.keepanno.ast.KeepMethodParametersPattern;
@@ -694,18 +695,19 @@
   }
 
   private abstract static class KeepItemVisitorBase extends AnnotationVisitorBase {
-    private Parent<KeepItemPattern> parent;
+    private Parent<KeepItemReference> parent;
+    private String memberBindingReference = null;
     private final ClassDeclaration classDeclaration = new ClassDeclaration();
     private final ExtendsDeclaration extendsDeclaration = new ExtendsDeclaration();
     private final MemberDeclaration memberDeclaration = new MemberDeclaration();
 
-    public KeepItemVisitorBase(Parent<KeepItemPattern> parent) {
+    public KeepItemVisitorBase(Parent<KeepItemReference> parent) {
       setParent(parent);
     }
 
     public KeepItemVisitorBase() {}
 
-    void setParent(Parent<KeepItemPattern> parent) {
+    void setParent(Parent<KeepItemReference> parent) {
       assert parent != null;
       assert this.parent == null;
       this.parent = parent;
@@ -713,6 +715,10 @@
 
     @Override
     public void visit(String name, Object value) {
+      if (name.equals(Item.memberFromBinding) && value instanceof String) {
+        memberBindingReference = (String) value;
+        return;
+      }
       if (classDeclaration.tryParse(name, value)
           || extendsDeclaration.tryParse(name, value)
           || memberDeclaration.tryParse(name, value)) {
@@ -732,12 +738,23 @@
 
     @Override
     public void visitEnd() {
-      parent.accept(
-          KeepItemPattern.builder()
-              .setClassReference(classDeclaration.getValue())
-              .setExtendsPattern(extendsDeclaration.getValue())
-              .setMemberPattern(memberDeclaration.getValue())
-              .build());
+      if (memberBindingReference != null) {
+        if (!classDeclaration.getValue().equals(classDeclaration.getDefaultValue())
+            || !memberDeclaration.getValue().isNone()
+            || !extendsDeclaration.getValue().isAny()) {
+          throw new KeepEdgeException(
+              "Cannot define an item explicitly and via a member-binding reference");
+        }
+        parent.accept(KeepItemReference.fromBindingReference(memberBindingReference));
+      } else {
+        parent.accept(
+            KeepItemReference.fromItemPattern(
+                KeepItemPattern.builder()
+                    .setClassReference(classDeclaration.getValue())
+                    .setExtendsPattern(extendsDeclaration.getValue())
+                    .setMemberPattern(memberDeclaration.getValue())
+                    .build()));
+      }
     }
   }
 
@@ -749,7 +766,20 @@
 
     public KeepBindingVisitor(KeepBindings.Builder builder) {
       this.builder = builder;
-      setParent(item -> this.item = item);
+      setParent(
+          item -> {
+            // The language currently disallows aliasing bindings, thus a binding should directly be
+            // defined by a reference to another binding.
+            if (item.isBindingReference()) {
+              throw new KeepEdgeException(
+                  "Invalid binding reference to '"
+                      + item.asBindingReference()
+                      + "' in binding definition of '"
+                      + bindingName
+                      + "'");
+            }
+            this.item = item.asItemPattern();
+          });
     }
 
     @Override
@@ -835,7 +865,7 @@
     }
 
     private KeepTargetVisitor(Parent<KeepTarget> parent, KeepTarget.Builder builder) {
-      super(item -> parent.accept(builder.setItemPattern(item).build()));
+      super(item -> parent.accept(builder.setItemReference(item).build()));
       this.builder = builder;
     }
 
@@ -852,7 +882,7 @@
   private static class KeepConditionVisitor extends KeepItemVisitorBase {
 
     public KeepConditionVisitor(Parent<KeepCondition> parent) {
-      super(item -> parent.accept(KeepCondition.builder().setItemPattern(item).build()));
+      super(item -> parent.accept(KeepCondition.builder().setItemReference(item).build()));
     }
   }
 
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
index 337631d..21692c9 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
@@ -6,6 +6,8 @@
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
+import java.util.function.BiConsumer;
+import java.util.stream.Collectors;
 
 public class KeepBindings {
 
@@ -30,6 +32,46 @@
     return bindings.get(bindingReference);
   }
 
+  public int size() {
+    return bindings.size();
+  }
+
+  public boolean isEmpty() {
+    return bindings.isEmpty();
+  }
+
+  public void forEach(BiConsumer<String, KeepItemPattern> fn) {
+    bindings.forEach((name, binding) -> fn.accept(name, binding.getItem()));
+  }
+
+  public boolean isAny(KeepItemReference itemReference) {
+    return itemReference.isBindingReference()
+        ? isAny(get(itemReference.asBindingReference()).getItem())
+        : isAny(itemReference.asItemPattern());
+  }
+
+  public boolean isAny(KeepItemPattern itemPattern) {
+    return itemPattern.isAny(this::isAnyClassNamePattern);
+  }
+
+  // If the outer-most item has been judged to be "any" then we internally only need to check
+  // that the class-name pattern itself is "any". The class-name could potentially reference names
+  // of other item bindings so this is a recursive search.
+  private boolean isAnyClassNamePattern(String bindingName) {
+    KeepClassReference classReference = get(bindingName).getItem().getClassReference();
+    return classReference.isBindingReference()
+        ? isAnyClassNamePattern(classReference.asBindingReference())
+        : classReference.asClassNamePattern().isAny();
+  }
+
+  @Override
+  public String toString() {
+    return "{"
+        + bindings.entrySet().stream()
+            .map(e -> e.getKey() + "=" + e.getValue())
+            .collect(Collectors.joining(", "));
+  }
+
   /**
    * A unique binding.
    *
@@ -72,6 +114,11 @@
     public int hashCode() {
       return System.identityHashCode(this);
     }
+
+    @Override
+    public String toString() {
+      return item.toString();
+    }
   }
 
   public static class Builder {
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassReference.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassReference.java
index 699c5bb..7397be7 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassReference.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassReference.java
@@ -76,6 +76,11 @@
     public int hashCode() {
       return bindingReference.hashCode();
     }
+
+    @Override
+    public String toString() {
+      return bindingReference;
+    }
   }
 
   private static class SomeItem extends KeepClassReference {
@@ -112,5 +117,10 @@
     public int hashCode() {
       return classNamePattern.hashCode();
     }
+
+    @Override
+    public String toString() {
+      return classNamePattern.toString();
+    }
   }
 }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java
index 2a86cd7..6dfe7e4 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemPattern.java
@@ -27,6 +27,14 @@
     return new Builder();
   }
 
+  public boolean isClassItemPattern() {
+    return memberPattern.isNone();
+  }
+
+  public boolean isMemberItemPattern() {
+    return !memberPattern.isNone();
+  }
+
   public static class Builder {
 
     private KeepClassReference classReference =
@@ -36,6 +44,12 @@
 
     private Builder() {}
 
+    public Builder copyFrom(KeepItemPattern pattern) {
+      return setClassReference(pattern.getClassReference())
+          .setExtendsPattern(pattern.getExtendsPattern())
+          .setMemberPattern(pattern.getMemberPattern());
+    }
+
     public Builder any() {
       classReference = KeepClassReference.fromClassNamePattern(KeepQualifiedClassNamePattern.any());
       extendsPattern = KeepExtendsPattern.any();
@@ -85,7 +99,7 @@
   }
 
   public boolean isAny(Predicate<String> onReference) {
-    return classReference.isAny(onReference) && extendsPattern.isAny() && memberPattern.isAll();
+    return extendsPattern.isAny() && memberPattern.isAll() && classReference.isAny(onReference);
   }
 
   public KeepClassReference getClassReference() {
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemReference.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemReference.java
index aaf713d..63a111b 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemReference.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemReference.java
@@ -65,6 +65,11 @@
     public int hashCode() {
       return bindingReference.hashCode();
     }
+
+    @Override
+    public String toString() {
+      return "reference='" + bindingReference + "'";
+    }
   }
 
   private static class SomeItem extends KeepItemReference {
@@ -101,5 +106,10 @@
     public int hashCode() {
       return itemPattern.hashCode();
     }
+
+    @Override
+    public String toString() {
+      return itemPattern.toString();
+    }
   }
 }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeBindingMinimizer.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeBindingMinimizer.java
new file mode 100644
index 0000000..0d0b853
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeBindingMinimizer.java
@@ -0,0 +1,139 @@
+// Copyright (c) 2023, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno.keeprules;
+
+import com.android.tools.r8.keepanno.ast.KeepBindings;
+import com.android.tools.r8.keepanno.ast.KeepBindings.Builder;
+import com.android.tools.r8.keepanno.ast.KeepClassReference;
+import com.android.tools.r8.keepanno.ast.KeepCondition;
+import com.android.tools.r8.keepanno.ast.KeepConsequences;
+import com.android.tools.r8.keepanno.ast.KeepEdge;
+import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepItemReference;
+import com.android.tools.r8.keepanno.ast.KeepPreconditions;
+import com.android.tools.r8.keepanno.ast.KeepTarget;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Compute the minimal set of unique bindings.
+ *
+ * <p>This will check if two bindings define the same exact type in which case they can and will use
+ * the same binding definition.
+ *
+ * <p>TODO(b/248408342): Consider extending this to also identify aliased members.
+ */
+public class KeepEdgeBindingMinimizer {
+
+  public static KeepEdge run(KeepEdge edge) {
+    KeepEdgeBindingMinimizer minimizer = new KeepEdgeBindingMinimizer();
+    return minimizer.minimize(edge);
+  }
+
+  Map<String, List<String>> descriptorToUniqueBindings = new HashMap<>();
+  Map<String, String> aliases = new HashMap<>();
+
+  private KeepEdge minimize(KeepEdge edge) {
+    computeAliases(edge);
+    if (aliases.isEmpty()) {
+      return edge;
+    }
+    return KeepEdge.builder()
+        .setMetaInfo(edge.getMetaInfo())
+        .setBindings(computeNewBindings(edge.getBindings()))
+        .setPreconditions(computeNewPreconditions(edge.getPreconditions()))
+        .setConsequences(computeNewConsequences(edge.getConsequences()))
+        .build();
+  }
+
+  private void computeAliases(KeepEdge edge) {
+    edge.getBindings()
+        .forEach(
+            (name, pattern) -> {
+              if (pattern.isClassItemPattern()
+                  && pattern.getClassReference().asClassNamePattern().isExact()) {
+                String descriptor =
+                    pattern.getClassReference().asClassNamePattern().getExactDescriptor();
+                List<String> others =
+                    descriptorToUniqueBindings.computeIfAbsent(descriptor, k -> new ArrayList<>());
+                String alias = findEqualBinding(pattern, others, edge);
+                if (alias != null) {
+                  aliases.put(name, alias);
+                } else {
+                  others.add(name);
+                }
+              }
+            });
+  }
+
+  private String findEqualBinding(KeepItemPattern pattern, List<String> others, KeepEdge edge) {
+    for (String otherName : others) {
+      KeepItemPattern otherItem = edge.getBindings().get(otherName).getItem();
+      if (pattern.equals(otherItem)) {
+        return otherName;
+      }
+    }
+    return null;
+  }
+
+  private String getBinding(String bindingName) {
+    return aliases.getOrDefault(bindingName, bindingName);
+  }
+
+  private KeepBindings computeNewBindings(KeepBindings bindings) {
+    Builder builder = KeepBindings.builder();
+    bindings.forEach(
+        (name, item) -> {
+          if (!aliases.containsKey(name)) {
+            builder.addBinding(name, computeNewItemPattern(item));
+          }
+        });
+    return builder.build();
+  }
+
+  private KeepPreconditions computeNewPreconditions(KeepPreconditions preconditions) {
+    if (preconditions.isAlways()) {
+      return preconditions;
+    }
+    KeepPreconditions.Builder builder = KeepPreconditions.builder();
+    preconditions.forEach(
+        condition ->
+            builder.addCondition(
+                KeepCondition.builder()
+                    .setItemReference(computeNewItemReference(condition.getItem()))
+                    .build()));
+    return builder.build();
+  }
+
+  private KeepConsequences computeNewConsequences(KeepConsequences consequences) {
+    KeepConsequences.Builder builder = KeepConsequences.builder();
+    consequences.forEachTarget(
+        target ->
+            builder.addTarget(
+                KeepTarget.builder()
+                    .setOptions(target.getOptions())
+                    .setItemReference(computeNewItemReference(target.getItem()))
+                    .build()));
+    return builder.build();
+  }
+
+  private KeepItemReference computeNewItemReference(KeepItemReference item) {
+    return item.isBindingReference()
+        ? KeepItemReference.fromBindingReference(getBinding(item.asBindingReference()))
+        : KeepItemReference.fromItemPattern(computeNewItemPattern(item.asItemPattern()));
+  }
+
+  private KeepItemPattern computeNewItemPattern(KeepItemPattern pattern) {
+    String classBinding = pattern.getClassReference().asBindingReference();
+    if (classBinding == null) {
+      return pattern;
+    }
+    return KeepItemPattern.builder()
+        .copyFrom(pattern)
+        .setClassReference(KeepClassReference.fromBindingReference(getBinding(classBinding)))
+        .build();
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeNormalizer.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeNormalizer.java
new file mode 100644
index 0000000..5922be3
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeNormalizer.java
@@ -0,0 +1,164 @@
+// Copyright (c) 2023, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno.keeprules;
+
+import com.android.tools.r8.keepanno.ast.KeepBindings;
+import com.android.tools.r8.keepanno.ast.KeepClassReference;
+import com.android.tools.r8.keepanno.ast.KeepCondition;
+import com.android.tools.r8.keepanno.ast.KeepConsequences;
+import com.android.tools.r8.keepanno.ast.KeepEdge;
+import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepItemReference;
+import com.android.tools.r8.keepanno.ast.KeepPreconditions;
+import com.android.tools.r8.keepanno.ast.KeepTarget;
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * Normalize a keep edge with respect to its bindings. This will systematically introduce a binding
+ * for each item in the edge. It will also introduce a class binding for the holder of any member
+ * item. By introducing a binding for each item the binding can be used as item identity.
+ */
+public class KeepEdgeNormalizer {
+
+  private static final String syntheticBindingPrefix = "SyntheticBinding";
+  private static final char syntheticBindingSuffix = 'X';
+
+  public static KeepEdge normalize(KeepEdge edge) {
+    // Check that all referenced bindings are defined.
+    KeepEdgeNormalizer normalizer = new KeepEdgeNormalizer(edge);
+    KeepEdge normalized = normalizer.run();
+    KeepEdge minimized = KeepEdgeBindingMinimizer.run(normalized);
+    return minimized;
+  }
+
+  private final KeepEdge edge;
+
+  private String freshBindingNamePrefix;
+  private int nextFreshBindingNameIndex = 1;
+
+  private final KeepBindings.Builder bindingsBuilder = KeepBindings.builder();
+  private final KeepPreconditions.Builder preconditionsBuilder = KeepPreconditions.builder();
+  private final KeepConsequences.Builder consequencesBuilder = KeepConsequences.builder();
+
+  private KeepEdgeNormalizer(KeepEdge edge) {
+    this.edge = edge;
+    findValidFreshBindingPrefix();
+  }
+
+  private void findValidFreshBindingPrefix() {
+    List<String> existingSuffixes = new ArrayList<>();
+    edge.getBindings()
+        .forEach(
+            (name, ignore) -> {
+              if (name.startsWith(syntheticBindingPrefix)) {
+                existingSuffixes.add(name.substring(syntheticBindingPrefix.length()));
+              }
+            });
+    if (!existingSuffixes.isEmpty()) {
+      int suffixLength = 0;
+      for (String existingSuffix : existingSuffixes) {
+        suffixLength = Math.max(suffixLength, getRepeatedSuffixLength(existingSuffix));
+      }
+      StringBuilder suffix = new StringBuilder();
+      for (int i = 0; i <= suffixLength; i++) {
+        suffix.append(syntheticBindingSuffix);
+      }
+      freshBindingNamePrefix = syntheticBindingPrefix + suffix;
+    } else {
+      freshBindingNamePrefix = syntheticBindingPrefix;
+    }
+  }
+
+  private int getRepeatedSuffixLength(String string) {
+    int i = 0;
+    while (i < string.length() && string.charAt(i) == syntheticBindingSuffix) {
+      i++;
+    }
+    return i;
+  }
+
+  private String nextFreshBindingName() {
+    return freshBindingNamePrefix + (nextFreshBindingNameIndex++);
+  }
+
+  private KeepEdge run() {
+    edge.getBindings()
+        .forEach(
+            (name, pattern) -> {
+              bindingsBuilder.addBinding(name, normalizeItemPattern(pattern));
+            });
+    // TODO(b/248408342): Normalize the preconditions by identifying vacuously true conditions.
+    edge.getPreconditions()
+        .forEach(
+            condition ->
+                preconditionsBuilder.addCondition(
+                    KeepCondition.builder()
+                        .setItemReference(normalizeItem(condition.getItem()))
+                        .build()));
+    edge.getConsequences()
+        .forEachTarget(
+            target -> {
+              consequencesBuilder.addTarget(
+                  KeepTarget.builder()
+                      .setOptions(target.getOptions())
+                      .setItemReference(normalizeItem(target.getItem()))
+                      .build());
+            });
+    return KeepEdge.builder()
+        .setMetaInfo(edge.getMetaInfo())
+        .setBindings(bindingsBuilder.build())
+        .setPreconditions(preconditionsBuilder.build())
+        .setConsequences(consequencesBuilder.build())
+        .build();
+  }
+
+  private KeepItemReference normalizeItem(KeepItemReference item) {
+    if (item.isBindingReference()) {
+      return item;
+    }
+    KeepItemPattern newItemPattern = normalizeItemPattern(item.asItemPattern());
+    String bindingName = nextFreshBindingName();
+    bindingsBuilder.addBinding(bindingName, newItemPattern);
+    return KeepItemReference.fromBindingReference(bindingName);
+  }
+
+  private KeepItemPattern normalizeItemPattern(KeepItemPattern pattern) {
+    // If the pattern is just a class pattern it is in normal form.
+    if (pattern.isClassItemPattern()) {
+      return pattern;
+    }
+    KeepClassReference bindingReference = bindingForClassItem(pattern);
+    return getMemberItemPattern(pattern, bindingReference);
+  }
+
+  private KeepClassReference bindingForClassItem(KeepItemPattern pattern) {
+    KeepClassReference classReference = pattern.getClassReference();
+    if (classReference.isBindingReference()) {
+      // If the class is already defined via a binding then no need to introduce a new one and
+      // change the item.
+      return classReference;
+    }
+    String bindingName = nextFreshBindingName();
+    KeepClassReference bindingReference = KeepClassReference.fromBindingReference(bindingName);
+    KeepItemPattern newClassPattern = getClassItemPattern(pattern);
+    bindingsBuilder.addBinding(bindingName, newClassPattern);
+    return bindingReference;
+  }
+
+  private KeepItemPattern getClassItemPattern(KeepItemPattern fromPattern) {
+    return KeepItemPattern.builder()
+        .setClassReference(fromPattern.getClassReference())
+        .setExtendsPattern(fromPattern.getExtendsPattern())
+        .build();
+  }
+
+  private KeepItemPattern getMemberItemPattern(
+      KeepItemPattern fromPattern, KeepClassReference classReference) {
+    return KeepItemPattern.builder()
+        .setClassReference(classReference)
+        .setMemberPattern(fromPattern.getMemberPattern())
+        .build();
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeSplitter.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeSplitter.java
new file mode 100644
index 0000000..f565635
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepEdgeSplitter.java
@@ -0,0 +1,377 @@
+// Copyright (c) 2023, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno.keeprules;
+
+import com.android.tools.r8.keepanno.ast.KeepBindings;
+import com.android.tools.r8.keepanno.ast.KeepCondition;
+import com.android.tools.r8.keepanno.ast.KeepEdge;
+import com.android.tools.r8.keepanno.ast.KeepEdgeException;
+import com.android.tools.r8.keepanno.ast.KeepEdgeMetaInfo;
+import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepItemReference;
+import com.android.tools.r8.keepanno.ast.KeepMemberPattern;
+import com.android.tools.r8.keepanno.ast.KeepOptions;
+import com.android.tools.r8.keepanno.ast.KeepQualifiedClassNamePattern;
+import com.android.tools.r8.keepanno.ast.KeepTarget;
+import com.android.tools.r8.keepanno.keeprules.PgRule.PgConditionalClassRule;
+import com.android.tools.r8.keepanno.keeprules.PgRule.PgConditionalMemberRule;
+import com.android.tools.r8.keepanno.keeprules.PgRule.PgDependentClassRule;
+import com.android.tools.r8.keepanno.keeprules.PgRule.PgDependentMembersRule;
+import com.android.tools.r8.keepanno.keeprules.PgRule.PgUnconditionalClassRule;
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+
+/** Split a keep edge into multiple PG rules that over-approximate it. */
+public class KeepEdgeSplitter {
+
+  public static Collection<PgRule> split(KeepEdge edge) {
+    return doSplit(KeepEdgeNormalizer.normalize(edge));
+  }
+
+  /**
+   * Utility to package up a class binding with its name and item pattern.
+   *
+   * <p>This is useful as the normalizer will have introduced class reference indirections so a
+   * given item may need to.
+   */
+  public static class Holder {
+    final KeepItemPattern itemPattern;
+    final KeepQualifiedClassNamePattern namePattern;
+
+    static Holder create(String bindingName, KeepBindings bindings) {
+      KeepItemPattern itemPattern = bindings.get(bindingName).getItem();
+      assert itemPattern.isClassItemPattern();
+      KeepQualifiedClassNamePattern namePattern = getClassNamePattern(itemPattern, bindings);
+      return new Holder(itemPattern, namePattern);
+    }
+
+    private Holder(KeepItemPattern itemPattern, KeepQualifiedClassNamePattern namePattern) {
+      this.itemPattern = itemPattern;
+      this.namePattern = namePattern;
+    }
+  }
+
+  private static class BindingUsers {
+
+    final Holder holder;
+    final Set<String> conditionRefs = new HashSet<>();
+    final Map<KeepOptions, Set<String>> targetRefs = new HashMap<>();
+
+    static BindingUsers create(String bindingName, KeepBindings bindings) {
+      return new BindingUsers(Holder.create(bindingName, bindings));
+    }
+
+    private BindingUsers(Holder holder) {
+      this.holder = holder;
+    }
+
+    public void addCondition(KeepCondition condition) {
+      assert condition.getItem().isBindingReference();
+      conditionRefs.add(condition.getItem().asBindingReference());
+    }
+
+    public void addTarget(KeepTarget target) {
+      assert target.getItem().isBindingReference();
+      targetRefs
+          .computeIfAbsent(target.getOptions(), k -> new HashSet<>())
+          .add(target.getItem().asBindingReference());
+    }
+  }
+
+  private static Collection<PgRule> doSplit(KeepEdge edge) {
+    List<PgRule> rules = new ArrayList<>();
+
+    // First step after normalizing is to group up all conditions and targets on their target class.
+    // Here we use the normalized binding as the notion of identity on a class.
+    KeepBindings bindings = edge.getBindings();
+    Map<String, BindingUsers> bindingUsers = new HashMap<>();
+    edge.getPreconditions()
+        .forEach(
+            condition -> {
+              String classReference = getClassItemBindingReference(condition.getItem(), bindings);
+              assert classReference != null;
+              bindingUsers
+                  .computeIfAbsent(classReference, k -> BindingUsers.create(k, bindings))
+                  .addCondition(condition);
+            });
+    edge.getConsequences()
+        .forEachTarget(
+            target -> {
+              String classReference = getClassItemBindingReference(target.getItem(), bindings);
+              assert classReference != null;
+              bindingUsers
+                  .computeIfAbsent(classReference, k -> BindingUsers.create(k, bindings))
+                  .addTarget(target);
+            });
+
+    bindingUsers.forEach(
+        (targetBindingName, users) -> {
+          Holder targetHolder = users.holder;
+          if (!users.conditionRefs.isEmpty() && !users.targetRefs.isEmpty()) {
+            // The targets depend on the condition and thus we generate just the dependent edges.
+            users.targetRefs.forEach(
+                (options, targets) -> {
+                  createDependentRules(
+                      rules,
+                      targetHolder,
+                      edge.getMetaInfo(),
+                      bindings,
+                      options,
+                      users.conditionRefs,
+                      targets);
+                });
+          } else if (!users.targetRefs.isEmpty()) {
+            // The targets don't have a binding relation to any conditions, so we generate a rule
+            // per condition, or a single unconditional edge if no conditions exist.
+            if (edge.getPreconditions().isAlways()) {
+              users.targetRefs.forEach(
+                  ((options, targets) -> {
+                    createUnconditionalRules(
+                        rules, targetHolder, edge.getMetaInfo(), bindings, options, targets);
+                  }));
+            } else {
+              users.targetRefs.forEach(
+                  ((options, targets) -> {
+                    // Note that here we iterate over *all* non-empty conditions and create rules.
+                    bindingUsers.forEach(
+                        (conditionBindingName, conditionUsers) -> {
+                          if (!conditionUsers.conditionRefs.isEmpty()) {
+                            createConditionalRules(
+                                rules,
+                                edge.getMetaInfo(),
+                                conditionUsers.holder,
+                                targetHolder,
+                                bindings,
+                                options,
+                                conditionUsers.conditionRefs,
+                                targets);
+                          }
+                        });
+                  }));
+            }
+          }
+        });
+
+    assert !rules.isEmpty();
+    return rules;
+  }
+
+  private static List<String> computeConditions(
+      Set<String> conditions,
+      KeepBindings bindings,
+      Map<String, KeepMemberPattern> memberPatterns) {
+    List<String> conditionMembers = new ArrayList<>();
+    conditions.forEach(
+        conditionReference -> {
+          KeepItemPattern item = bindings.get(conditionReference).getItem();
+          if (item.isMemberItemPattern()) {
+            KeepMemberPattern old = memberPatterns.put(conditionReference, item.getMemberPattern());
+            conditionMembers.add(conditionReference);
+            assert old == null;
+          }
+        });
+    return conditionMembers;
+  }
+
+  private static void computeTargets(
+      Set<String> targets,
+      KeepBindings bindings,
+      Map<String, KeepMemberPattern> memberPatterns,
+      Runnable onKeepClass,
+      BiConsumer<Map<String, KeepMemberPattern>, List<String>> onKeepMembers) {
+    List<String> targetMembers = new ArrayList<>();
+    boolean keepClassTarget = false;
+    for (String targetReference : targets) {
+      KeepItemPattern item = bindings.get(targetReference).getItem();
+      if (item.isClassItemPattern() || bindings.isAny(item)) {
+        keepClassTarget = true;
+      }
+      if (item.isMemberItemPattern()) {
+        memberPatterns.putIfAbsent(targetReference, item.getMemberPattern());
+        targetMembers.add(targetReference);
+      }
+    }
+    if (keepClassTarget) {
+      onKeepClass.run();
+    }
+    if (!targetMembers.isEmpty()) {
+      onKeepMembers.accept(memberPatterns, targetMembers);
+    }
+  }
+
+  private static void createUnconditionalRules(
+      List<PgRule> rules,
+      Holder holder,
+      KeepEdgeMetaInfo metaInfo,
+      KeepBindings bindings,
+      KeepOptions options,
+      Set<String> targets) {
+    computeTargets(
+        targets,
+        bindings,
+        new HashMap<>(),
+        () -> {
+          rules.add(new PgUnconditionalClassRule(metaInfo, options, holder));
+        },
+        (memberPatterns, targetMembers) -> {
+          // Members are still dependent on the class, so they go to the implicitly dependent rule.
+          rules.add(
+              new PgDependentMembersRule(
+                  metaInfo,
+                  holder,
+                  options,
+                  memberPatterns,
+                  Collections.emptyList(),
+                  targetMembers));
+        });
+  }
+
+  private static void createConditionalRules(
+      List<PgRule> rules,
+      KeepEdgeMetaInfo metaInfo,
+      Holder conditionHolder,
+      Holder targetHolder,
+      KeepBindings bindings,
+      KeepOptions options,
+      Set<String> conditions,
+      Set<String> targets) {
+
+    Map<String, KeepMemberPattern> memberPatterns = new HashMap<>();
+    List<String> conditionMembers = computeConditions(conditions, bindings, memberPatterns);
+
+    computeTargets(
+        targets,
+        bindings,
+        memberPatterns,
+        () ->
+            rules.add(
+                new PgConditionalClassRule(
+                    metaInfo,
+                    options,
+                    conditionHolder,
+                    targetHolder,
+                    memberPatterns,
+                    conditionMembers)),
+        (ignore, targetMembers) ->
+            rules.add(
+                new PgConditionalMemberRule(
+                    metaInfo,
+                    options,
+                    conditionHolder,
+                    targetHolder,
+                    memberPatterns,
+                    conditionMembers,
+                    targetMembers)));
+  }
+
+  // For a conditional and dependent edge (e.g., the condition and target both reference holder X),
+  // we can assume the general form of:
+  //
+  //   { X, memberConds } -> { X, memberTargets }
+  //
+  // First, we assume that if memberConds=={} then X is in the conditions, otherwise the conditions
+  // are empty (i.e. always true) and this is not a dependent edge.
+  //
+  // Without change in meaning we can always assume X in conditions as it either was and if not then
+  // the condition on a member implicitly entails a condition on the holder.
+  //
+  // Next we can split any such edge into two edges:
+  //
+  //   { X, memberConds } -> { X }
+  //   { X, memberConds } -> { memberTargets }
+  //
+  // The first edge, if present, gives rise to the rule:
+  //
+  //   -if class X { memberConds } -keep class <1>
+  //
+  // The second rule only pertains to keeping member targets and those targets are kept as a
+  // -keepclassmembers such that they are still conditional on the holder being referenced/live.
+  // If the only precondition is the holder, then it can omitted, thus we generate:
+  // If memberConds={}:
+  //   -keepclassmembers class X { memberTargets }
+  // else:
+  //   -if class X { memberConds } -keepclassmembers X { memberTargets }
+  //
+  private static void createDependentRules(
+      List<PgRule> rules,
+      Holder holder,
+      KeepEdgeMetaInfo metaInfo,
+      KeepBindings bindings,
+      KeepOptions options,
+      Set<String> conditions,
+      Set<String> targets) {
+    Map<String, KeepMemberPattern> memberPatterns = new HashMap<>();
+    List<String> conditionMembers = computeConditions(conditions, bindings, memberPatterns);
+    computeTargets(
+        targets,
+        bindings,
+        memberPatterns,
+        () ->
+            rules.add(
+                new PgDependentClassRule(
+                    metaInfo, holder, options, memberPatterns, conditionMembers)),
+        (ignore, targetMembers) ->
+            rules.add(
+                new PgDependentMembersRule(
+                    metaInfo, holder, options, memberPatterns, conditionMembers, targetMembers)));
+  }
+
+  private static KeepQualifiedClassNamePattern getClassNamePattern(
+      KeepItemPattern itemPattern, KeepBindings bindings) {
+    return itemPattern.getClassReference().isClassNamePattern()
+        ? itemPattern.getClassReference().asClassNamePattern()
+        : getClassNamePattern(
+            bindings.get(itemPattern.getClassReference().asBindingReference()).getItem(), bindings);
+  }
+
+  private static String getClassItemBindingReference(
+      KeepItemReference itemReference, KeepBindings bindings) {
+    String classReference = null;
+    for (String reference : getTransitiveBindingReferences(itemReference, bindings)) {
+      if (bindings.get(reference).getItem().isClassItemPattern()) {
+        if (classReference != null) {
+          throw new KeepEdgeException("Unexpected reference to multiple class bindings");
+        }
+        classReference = reference;
+      }
+    }
+    return classReference;
+  }
+
+  private static Set<String> getTransitiveBindingReferences(
+      KeepItemReference itemReference, KeepBindings bindings) {
+    Set<String> references = new HashSet<>(2);
+    Deque<String> worklist = new ArrayDeque<>();
+    worklist.addAll(getBindingReference(itemReference));
+    while (!worklist.isEmpty()) {
+      String bindingReference = worklist.pop();
+      if (references.add(bindingReference)) {
+        worklist.addAll(getBindingReference(bindings.get(bindingReference).getItem()));
+      }
+    }
+    return references;
+  }
+
+  private static Collection<String> getBindingReference(KeepItemReference itemReference) {
+    if (itemReference.isBindingReference()) {
+      return Collections.singletonList(itemReference.asBindingReference());
+    }
+    return getBindingReference(itemReference.asItemPattern());
+  }
+
+  private static Collection<String> getBindingReference(KeepItemPattern itemPattern) {
+    return itemPattern.getClassReference().isBindingReference()
+        ? Collections.singletonList(itemPattern.getClassReference().asBindingReference())
+        : Collections.emptyList();
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepRuleExtractor.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepRuleExtractor.java
index db4362a..39ae46d 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepRuleExtractor.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/KeepRuleExtractor.java
@@ -3,9 +3,7 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.keeprules;
 
-import com.android.tools.r8.keepanno.ast.KeepBindings;
 import com.android.tools.r8.keepanno.ast.KeepClassReference;
-import com.android.tools.r8.keepanno.ast.KeepConsequences;
 import com.android.tools.r8.keepanno.ast.KeepEdge;
 import com.android.tools.r8.keepanno.ast.KeepEdgeException;
 import com.android.tools.r8.keepanno.ast.KeepEdgeMetaInfo;
@@ -14,7 +12,6 @@
 import com.android.tools.r8.keepanno.ast.KeepFieldNamePattern;
 import com.android.tools.r8.keepanno.ast.KeepFieldPattern;
 import com.android.tools.r8.keepanno.ast.KeepItemPattern;
-import com.android.tools.r8.keepanno.ast.KeepItemReference;
 import com.android.tools.r8.keepanno.ast.KeepMemberPattern;
 import com.android.tools.r8.keepanno.ast.KeepMethodAccessPattern;
 import com.android.tools.r8.keepanno.ast.KeepMethodNamePattern;
@@ -24,21 +21,16 @@
 import com.android.tools.r8.keepanno.ast.KeepOptions;
 import com.android.tools.r8.keepanno.ast.KeepOptions.KeepOption;
 import com.android.tools.r8.keepanno.ast.KeepPackagePattern;
-import com.android.tools.r8.keepanno.ast.KeepPreconditions;
 import com.android.tools.r8.keepanno.ast.KeepQualifiedClassNamePattern;
-import com.android.tools.r8.keepanno.ast.KeepTarget;
 import com.android.tools.r8.keepanno.ast.KeepTypePattern;
 import com.android.tools.r8.keepanno.ast.KeepUnqualfiedClassNamePattern;
 import com.android.tools.r8.keepanno.utils.Unimplemented;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
+import java.util.Collection;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.stream.Collectors;
 
+/** Extract out a sequence of Proguard keep rules that give a conservative over-approximation. */
 public class KeepRuleExtractor {
 
   private final Consumer<String> ruleConsumer;
@@ -48,18 +40,16 @@
   }
 
   public void extract(KeepEdge edge) {
-    List<ItemRule> consequentRules = getConsequentRules(edge.getConsequences());
-    printConditionalRules(
-        consequentRules, edge.getPreconditions(), edge.getMetaInfo(), edge.getBindings());
+    Collection<PgRule> rules = KeepEdgeSplitter.split(edge);
+    StringBuilder builder = new StringBuilder();
+    for (PgRule rule : rules) {
+      rule.printRule(builder);
+      builder.append("\n");
+    }
+    ruleConsumer.accept(builder.toString());
   }
 
-  private List<ItemRule> getConsequentRules(KeepConsequences consequences) {
-    List<ItemRule> consequentItems = new ArrayList<>();
-    consequences.forEachTarget(target -> consequentItems.add(new ItemRule(target)));
-    return consequentItems;
-  }
-
-  private void printHeader(StringBuilder builder, KeepEdgeMetaInfo metaInfo) {
+  public static void printHeader(StringBuilder builder, KeepEdgeMetaInfo metaInfo) {
     if (metaInfo.hasContext()) {
       builder.append("# context: ").append(metaInfo.getContextDescriptorString()).append('\n');
     }
@@ -69,7 +59,7 @@
     }
   }
 
-  private String escapeChar(char c) {
+  public static String escapeChar(char c) {
     if (c == '\n') {
       return "\\n";
     }
@@ -79,7 +69,7 @@
     return null;
   }
 
-  private String escapeLineBreaks(String string) {
+  public static String escapeLineBreaks(String string) {
     char[] charArray = string.toCharArray();
     for (int i = 0; i < charArray.length; i++) {
       // We don't expect escape chars, so wait with constructing a new string until found.
@@ -100,120 +90,37 @@
     return string;
   }
 
-  private void printConditionalRules(
-      List<ItemRule> consequentRules,
-      KeepPreconditions preconditions,
-      KeepEdgeMetaInfo metaInfo,
-      KeepBindings bindings) {
-    boolean[] hasAtLeastOneConditionalClause = new boolean[1];
-    preconditions.forEach(
-        condition -> {
-          if (condition.getItem().isBindingReference()) {
-            throw new Unimplemented();
-          }
-          KeepItemPattern conditionItem = condition.getItem().asItemPattern();
-          // If the conditions is "any" then we ignore it for now (identity of conjunction).
-          if (conditionItem.isAny(
-              // TODO(b/248408342): This can still be an unconditional precondition if the binding
-              //  is just not used in the conclusion. Get some tests and support that case.
-              binding -> false)) {
-            return;
-          }
-          hasAtLeastOneConditionalClause[0] = true;
-          consequentRules.forEach(
-              consequentItem -> {
-                // Since conjunctions are not supported in keep rules, we expand them into
-                // disjunctions so conservatively we keep the consequences if any one of
-                // the preconditions hold.
-                StringBuilder builder = new StringBuilder();
-                printHeader(builder, metaInfo);
-                Map<String, Integer> bindingToBackReference = new HashMap<>();
-                if (!consequentItem.isMemberOnlyConsequent()
-                    || !conditionItem.getMemberPattern().isNone()
-                    || !conditionItem
-                        .getClassReference()
-                        .equals(consequentItem.getHolderReference())) {
-                  builder.append("-if ");
-                  printItem(
-                      builder,
-                      conditionItem,
-                      (builder1, classRef) -> {
-                        if (classRef.isClassNamePattern()) {
-                          printClassName(builder, classRef.asClassNamePattern());
-                        } else {
-                          String bindingName = classRef.asBindingReference();
-                          builder.append("*");
-                          Integer old =
-                              bindingToBackReference.put(
-                                  bindingName, bindingToBackReference.size() + 1);
-                          if (old != null) {
-                            throw new KeepEdgeException(
-                                "Failure to extract rules. Duplicate binding for '"
-                                    + bindingName
-                                    + "'");
-                          }
-                        }
-                      });
-                  builder.append(' ');
-                }
-                printConsequentRule(builder, consequentItem, bindingToBackReference);
-                ruleConsumer.accept(builder.toString());
-              });
-        });
-    assert !(preconditions.isAlways() && hasAtLeastOneConditionalClause[0]);
-    if (!hasAtLeastOneConditionalClause[0]) {
-      // If there are no preconditions, print each consequent as is.
-      consequentRules.forEach(
-          r -> {
-            StringBuilder builder = new StringBuilder();
-            printHeader(builder, metaInfo);
-            ruleConsumer.accept(printConsequentRule(builder, r, Collections.emptyMap()).toString());
-          });
-    }
-  }
-
-  private static StringBuilder printConsequentRule(
-      StringBuilder builder, ItemRule rule, Map<String, Integer> bindingToBackReference) {
-    if (rule.isMemberOnlyConsequent()) {
-      builder.append("-keepclassmembers");
-    } else {
-      builder.append("-keep");
-    }
+  public static void printKeepOptions(StringBuilder builder, KeepOptions options) {
     for (KeepOption option : KeepOption.values()) {
-      if (rule.options.isAllowed(option)) {
+      if (options.isAllowed(option)) {
         builder.append(",allow").append(getOptionString(option));
       }
     }
-    return builder.append(" ").append(rule.getKeepRuleForItem(bindingToBackReference));
   }
 
-  private static StringBuilder printItem(
+  public static StringBuilder printClassHeader(
       StringBuilder builder,
-      KeepItemPattern clazzPattern,
+      KeepItemPattern classPattern,
       BiConsumer<StringBuilder, KeepClassReference> printClassReference) {
     builder.append("class ");
-    printClassReference.accept(builder, clazzPattern.getClassReference());
-    KeepExtendsPattern extendsPattern = clazzPattern.getExtendsPattern();
+    printClassReference.accept(builder, classPattern.getClassReference());
+    KeepExtendsPattern extendsPattern = classPattern.getExtendsPattern();
     if (!extendsPattern.isAny()) {
       builder.append(" extends ");
       printClassName(builder, extendsPattern.asClassNamePattern());
     }
-    KeepMemberPattern member = clazzPattern.getMemberPattern();
-    if (member.isNone()) {
-      return builder;
-    }
+    return builder;
+  }
+
+  public static StringBuilder printMemberClause(StringBuilder builder, KeepMemberPattern member) {
     if (member.isAll()) {
-      return builder.append(" { *; }");
+      return builder.append("*;");
     }
     if (member.isMethod()) {
-      builder.append(" {");
-      printMethod(builder.append(' '), member.asMethod());
-      return builder.append(" }");
+      return printMethod(builder, member.asMethod());
     }
     if (member.isField()) {
-      builder.append(" {");
-      printField(builder.append(' '), member.asField());
-      return builder.append(" }");
+      return printField(builder, member.asField());
     }
     throw new Unimplemented();
   }
@@ -301,7 +208,7 @@
     throw new Unimplemented();
   }
 
-  private static StringBuilder printClassName(
+  public static StringBuilder printClassName(
       StringBuilder builder, KeepQualifiedClassNamePattern classNamePattern) {
     if (classNamePattern.isAny()) {
       return builder.append('*');
@@ -411,67 +318,4 @@
     }
     throw new KeepEdgeException("Invalid array descriptor: " + descriptor);
   }
-
-  private static class ItemRule {
-    private final KeepTarget target;
-    private final KeepOptions options;
-    private String ruleLine = null;
-
-    public ItemRule(KeepTarget target) {
-      this.target = target;
-      this.options = target.getOptions();
-    }
-
-    public boolean isMemberOnlyConsequent() {
-      KeepItemReference item = target.getItem();
-      if (item.isBindingReference()) {
-        throw new Unimplemented();
-      }
-      KeepItemPattern itemPattern = item.asItemPattern();
-      if (itemPattern.getMemberPattern().isNone()) {
-        return false;
-      }
-      // If the item's class is a binding then it is not an "any" pattern.
-      return !itemPattern.isAny(classBinding -> true);
-    }
-
-    public KeepClassReference getHolderReference() {
-      if (target.getItem().isBindingReference()) {
-        throw new Unimplemented();
-      }
-      return target.getItem().asItemPattern().getClassReference();
-    }
-
-    public String getKeepRuleForItem(Map<String, Integer> bindingToBackReference) {
-      if (ruleLine == null) {
-        if (target.getItem().isBindingReference()) {
-          throw new Unimplemented();
-        }
-        KeepItemPattern item = target.getItem().asItemPattern();
-        ruleLine =
-            item.isAny(classBinding -> false)
-                ? "class * { *; }"
-                : printItem(
-                        new StringBuilder(),
-                        item,
-                        (builder, classRef) -> {
-                          if (classRef.isClassNamePattern()) {
-                            printClassName(builder, classRef.asClassNamePattern());
-                          } else {
-                            String bindingReference = classRef.asBindingReference();
-                            Integer backReference = bindingToBackReference.get(bindingReference);
-                            if (backReference == null) {
-                              throw new KeepEdgeException(
-                                  "Undefined back reference for binding: '"
-                                      + bindingReference
-                                      + "'");
-                            }
-                            builder.append('<').append(backReference).append('>');
-                          }
-                        })
-                    .toString();
-      }
-      return ruleLine;
-    }
-  }
 }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/PgRule.java b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/PgRule.java
new file mode 100644
index 0000000..9a9ccc0
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/keeprules/PgRule.java
@@ -0,0 +1,488 @@
+// Copyright (c) 2023, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno.keeprules;
+
+import com.android.tools.r8.keepanno.ast.KeepClassReference;
+import com.android.tools.r8.keepanno.ast.KeepEdgeException;
+import com.android.tools.r8.keepanno.ast.KeepEdgeMetaInfo;
+import com.android.tools.r8.keepanno.ast.KeepItemPattern;
+import com.android.tools.r8.keepanno.ast.KeepMemberPattern;
+import com.android.tools.r8.keepanno.ast.KeepOptions;
+import com.android.tools.r8.keepanno.ast.KeepPackagePattern;
+import com.android.tools.r8.keepanno.ast.KeepQualifiedClassNamePattern;
+import com.android.tools.r8.keepanno.ast.KeepUnqualfiedClassNamePattern;
+import com.android.tools.r8.keepanno.keeprules.KeepEdgeSplitter.Holder;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.function.BiConsumer;
+
+public abstract class PgRule {
+  private final KeepEdgeMetaInfo metaInfo;
+  private final KeepOptions options;
+
+  private PgRule(KeepEdgeMetaInfo metaInfo, KeepOptions options) {
+    this.metaInfo = metaInfo;
+    this.options = options;
+  }
+
+  // Helper to print the class-name pattern in a class-item.
+  // The item is assumed to either be a binding (where the binding is a class with
+  // the supplied class-name pattern), or a class-item that has the class-name pattern itself (e.g.,
+  // without a binding indirection).
+  public static BiConsumer<StringBuilder, KeepClassReference> classReferencePrinter(
+      KeepQualifiedClassNamePattern classNamePattern) {
+    return (StringBuilder builder, KeepClassReference classReference) -> {
+      assert classReference.isBindingReference()
+          || classReference.asClassNamePattern().equals(classNamePattern);
+      KeepRuleExtractor.printClassName(builder, classNamePattern);
+    };
+  }
+
+  void printKeepOptions(StringBuilder builder) {
+    KeepRuleExtractor.printKeepOptions(builder, options);
+  }
+
+  public void printRule(StringBuilder builder) {
+    KeepRuleExtractor.printHeader(builder, metaInfo);
+    printCondition(builder);
+    printConsequence(builder);
+  }
+
+  void printCondition(StringBuilder builder) {
+    if (hasCondition()) {
+      builder.append("-if ");
+      printConditionHolder(builder);
+      List<String> members = getConditionMembers();
+      if (!members.isEmpty()) {
+        builder.append(" {");
+        for (String member : members) {
+          builder.append(' ');
+          printConditionMember(builder, member);
+        }
+        builder.append(" }");
+      }
+      builder.append(' ');
+    }
+  }
+
+  void printConsequence(StringBuilder builder) {
+    builder.append(getConsequenceKeepType());
+    printKeepOptions(builder);
+    builder.append(' ');
+    printTargetHolder(builder);
+    List<String> members = getTargetMembers();
+    if (!members.isEmpty()) {
+      builder.append(" {");
+      for (String member : members) {
+        builder.append(' ');
+        printTargetMember(builder, member);
+      }
+      builder.append(" }");
+    }
+  }
+
+  boolean hasCondition() {
+    return false;
+  }
+  ;
+
+  List<String> getConditionMembers() {
+    throw new KeepEdgeException("Unreachable");
+  }
+
+  abstract String getConsequenceKeepType();
+
+  abstract List<String> getTargetMembers();
+
+  void printConditionHolder(StringBuilder builder) {
+    throw new KeepEdgeException("Unreachable");
+  }
+
+  void printConditionMember(StringBuilder builder, String member) {
+    throw new KeepEdgeException("Unreachable");
+  }
+
+  abstract void printTargetHolder(StringBuilder builder);
+
+  abstract void printTargetMember(StringBuilder builder, String member);
+
+  /**
+   * Representation of an unconditional rule to keep a class.
+   *
+   * <pre>
+   *   -keep class <holder>
+   * </pre>
+   *
+   * and with no dependencies / back-references.
+   */
+  static class PgUnconditionalClassRule extends PgRule {
+    final KeepQualifiedClassNamePattern holderNamePattern;
+    final KeepItemPattern holderPattern;
+
+    public PgUnconditionalClassRule(KeepEdgeMetaInfo metaInfo, KeepOptions options, Holder holder) {
+      super(metaInfo, options);
+      this.holderNamePattern = holder.namePattern;
+      this.holderPattern = holder.itemPattern;
+    }
+
+    @Override
+    String getConsequenceKeepType() {
+      return "-keep";
+    }
+
+    @Override
+    List<String> getTargetMembers() {
+      return Collections.emptyList();
+    }
+
+    @Override
+    void printTargetHolder(StringBuilder builder) {
+      KeepRuleExtractor.printClassHeader(
+          builder, holderPattern, classReferencePrinter(holderNamePattern));
+    }
+
+    @Override
+    void printTargetMember(StringBuilder builder, String memberReference) {
+      throw new KeepEdgeException("Unreachable");
+    }
+  }
+
+  abstract static class PgConditionalRuleBase extends PgRule {
+    final KeepItemPattern classCondition;
+    final KeepItemPattern classTarget;
+    final Map<String, KeepMemberPattern> memberPatterns;
+    final List<String> memberConditions;
+
+    public PgConditionalRuleBase(
+        KeepEdgeMetaInfo metaInfo,
+        KeepOptions options,
+        Holder classCondition,
+        Holder classTarget,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions) {
+      super(metaInfo, options);
+      this.classCondition = classCondition.itemPattern;
+      this.classTarget = classTarget.itemPattern;
+      this.memberPatterns = memberPatterns;
+      this.memberConditions = memberConditions;
+    }
+
+    @Override
+    boolean hasCondition() {
+      return true;
+    }
+
+    @Override
+    List<String> getConditionMembers() {
+      return memberConditions;
+    }
+
+    @Override
+    void printConditionHolder(StringBuilder builder) {
+      KeepRuleExtractor.printClassHeader(builder, classCondition, this::printClassName);
+    }
+
+    @Override
+    void printConditionMember(StringBuilder builder, String member) {
+      KeepMemberPattern memberPattern = memberPatterns.get(member);
+      KeepRuleExtractor.printMemberClause(builder, memberPattern);
+    }
+
+    @Override
+    void printTargetHolder(StringBuilder builder) {
+      KeepRuleExtractor.printClassHeader(builder, classTarget, this::printClassName);
+    }
+
+    void printClassName(StringBuilder builder, KeepClassReference clazz) {
+      KeepRuleExtractor.printClassName(builder, clazz.asClassNamePattern());
+    }
+  }
+
+  /**
+   * Representation of conditional rules but without dependencies between condition and target.
+   *
+   * <pre>
+   *   -if class <class-condition> { <member-conditions> }
+   *   -keep class <class-target>
+   * </pre>
+   *
+   * and with no dependencies / back-references.
+   */
+  static class PgConditionalClassRule extends PgConditionalRuleBase {
+
+    public PgConditionalClassRule(
+        KeepEdgeMetaInfo metaInfo,
+        KeepOptions options,
+        Holder classCondition,
+        Holder classTarget,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions) {
+      super(metaInfo, options, classCondition, classTarget, memberPatterns, memberConditions);
+    }
+
+    @Override
+    String getConsequenceKeepType() {
+      return "-keep";
+    }
+
+    @Override
+    List<String> getTargetMembers() {
+      return Collections.emptyList();
+    }
+
+    @Override
+    void printTargetMember(StringBuilder builder, String member) {
+      throw new KeepEdgeException("Unreachable");
+    }
+  }
+
+  /**
+   * Representation of conditional rules but without dependencies between condition and target.
+   *
+   * <pre>
+   *   -if class <class-condition> { <member-conditions> }
+   *   -keep[classmembers] class <class-target> { <member-targets> }
+   * </pre>
+   *
+   * and with no dependencies / back-references.
+   */
+  static class PgConditionalMemberRule extends PgConditionalRuleBase {
+
+    private final List<String> memberTargets;
+
+    public PgConditionalMemberRule(
+        KeepEdgeMetaInfo metaInfo,
+        KeepOptions options,
+        Holder classCondition,
+        Holder classTarget,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions,
+        List<String> memberTargets) {
+      super(metaInfo, options, classCondition, classTarget, memberPatterns, memberConditions);
+      this.memberTargets = memberTargets;
+    }
+
+    @Override
+    String getConsequenceKeepType() {
+      return "-keepclassmembers";
+    }
+
+    @Override
+    List<String> getTargetMembers() {
+      return memberTargets;
+    }
+
+    @Override
+    void printTargetMember(StringBuilder builder, String member) {
+      KeepMemberPattern memberPattern = memberPatterns.get(member);
+      KeepRuleExtractor.printMemberClause(builder, memberPattern);
+    }
+  }
+
+  abstract static class PgDependentRuleBase extends PgRule {
+
+    final KeepQualifiedClassNamePattern holderNamePattern;
+    final KeepItemPattern holderPattern;
+    final Map<String, KeepMemberPattern> memberPatterns;
+    final List<String> memberConditions;
+
+    public PgDependentRuleBase(
+        KeepEdgeMetaInfo metaInfo,
+        Holder holder,
+        KeepOptions options,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions) {
+      super(metaInfo, options);
+      this.holderNamePattern = holder.namePattern;
+      this.holderPattern = holder.itemPattern;
+      this.memberPatterns = memberPatterns;
+      this.memberConditions = memberConditions;
+    }
+
+    int nextBackReferenceNumber = 1;
+    String holderBackReferencePattern;
+    // TODO(b/248408342): Support back-ref to members too.
+
+    private StringBuilder addBackRef(StringBuilder backReferenceBuilder) {
+      return backReferenceBuilder.append('<').append(nextBackReferenceNumber++).append('>');
+    }
+
+    @Override
+    List<String> getConditionMembers() {
+      return memberConditions;
+    }
+
+    @Override
+    void printConditionHolder(StringBuilder b) {
+      KeepRuleExtractor.printClassHeader(
+          b,
+          holderPattern,
+          (builder, classReference) -> {
+            StringBuilder backReference = new StringBuilder();
+            if (holderNamePattern.isAny()) {
+              addBackRef(backReference);
+              builder.append('*');
+            } else {
+              printPackagePrefix(builder, holderNamePattern.getPackagePattern(), backReference);
+              printSimpleClassName(builder, holderNamePattern.getNamePattern(), backReference);
+            }
+            holderBackReferencePattern = backReference.toString();
+          });
+    }
+
+    @Override
+    void printConditionMember(StringBuilder builder, String member) {
+      // TODO(b/248408342): Support back-ref to member instances too.
+      KeepMemberPattern memberPattern = memberPatterns.get(member);
+      KeepRuleExtractor.printMemberClause(builder, memberPattern);
+    }
+
+    @Override
+    void printTargetHolder(StringBuilder builder) {
+      KeepRuleExtractor.printClassHeader(
+          builder,
+          holderPattern,
+          (b, reference) -> {
+            assert reference.isBindingReference()
+                || reference.asClassNamePattern().equals(holderNamePattern);
+            b.append(holderBackReferencePattern);
+          });
+    }
+
+    private StringBuilder printPackagePrefix(
+        StringBuilder builder,
+        KeepPackagePattern packagePattern,
+        StringBuilder backReferenceBuilder) {
+      if (packagePattern.isAny()) {
+        addBackRef(backReferenceBuilder).append('.');
+        return builder.append("**.");
+      }
+      if (packagePattern.isTop()) {
+        return builder;
+      }
+      assert packagePattern.isExact();
+      String exactPackage = packagePattern.getExactPackageAsString();
+      backReferenceBuilder.append(exactPackage).append('.');
+      return builder.append(exactPackage).append('.');
+    }
+
+    private StringBuilder printSimpleClassName(
+        StringBuilder builder,
+        KeepUnqualfiedClassNamePattern namePattern,
+        StringBuilder backReferenceBuilder) {
+      if (namePattern.isAny()) {
+        addBackRef(backReferenceBuilder);
+        return builder.append('*');
+      }
+      assert namePattern.isExact();
+      String exactName = namePattern.asExact().getExactNameAsString();
+      backReferenceBuilder.append(exactName);
+      return builder.append(exactName);
+    }
+  }
+
+  /**
+   * Representation of a conditional class rule that is match/instance dependent.
+   *
+   * <pre>
+   *   -if class <class-pattern> { <member-condition>* }
+   *   -keep class <class-backref>
+   * </pre>
+   */
+  static class PgDependentClassRule extends PgDependentRuleBase {
+
+    public PgDependentClassRule(
+        KeepEdgeMetaInfo metaInfo,
+        Holder holder,
+        KeepOptions options,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions) {
+      super(metaInfo, holder, options, memberPatterns, memberConditions);
+    }
+
+    @Override
+    String getConsequenceKeepType() {
+      return "-keep";
+    }
+
+    @Override
+    boolean hasCondition() {
+      return true;
+    }
+
+    @Override
+    List<String> getTargetMembers() {
+      return Collections.emptyList();
+    }
+
+    @Override
+    void printTargetMember(StringBuilder builder, String member) {
+      throw new KeepEdgeException("Unreachable");
+    }
+  }
+
+  /**
+   * Representation of a conditional member rule that is match/instance dependent.
+   *
+   * <pre>
+   *   -if class <class-pattern> { <member-condition>* }
+   *   -keepclassmembers class <class-backref> { <member-target | member-backref>* }
+   * </pre>
+   *
+   * or if the only condition is the class itself, just:
+   *
+   * <pre>
+   *   -keepclassmembers <class-pattern> { <member-target> }
+   * </pre>
+   */
+  static class PgDependentMembersRule extends PgDependentRuleBase {
+
+    final List<String> memberTargets;
+
+    public PgDependentMembersRule(
+        KeepEdgeMetaInfo metaInfo,
+        Holder holder,
+        KeepOptions options,
+        Map<String, KeepMemberPattern> memberPatterns,
+        List<String> memberConditions,
+        List<String> memberTargets) {
+      super(metaInfo, holder, options, memberPatterns, memberConditions);
+      assert !memberTargets.isEmpty();
+      this.memberTargets = memberTargets;
+    }
+
+    @Override
+    boolean hasCondition() {
+      return !memberConditions.isEmpty();
+    }
+
+    @Override
+    String getConsequenceKeepType() {
+      return "-keepclassmembers";
+    }
+
+    @Override
+    List<String> getTargetMembers() {
+      return memberTargets;
+    }
+
+    @Override
+    void printTargetHolder(StringBuilder builder) {
+      if (hasCondition()) {
+        super.printTargetHolder(builder);
+      } else {
+        KeepRuleExtractor.printClassHeader(
+            builder, holderPattern, classReferencePrinter(holderNamePattern));
+      }
+    }
+
+    @Override
+    void printTargetMember(StringBuilder builder, String member) {
+      // TODO(b/248408342): Support back-ref to member instances too.
+      KeepMemberPattern memberPattern = memberPatterns.get(member);
+      KeepRuleExtractor.printMemberClause(builder, memberPattern);
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepBindingTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepBindingTest.java
new file mode 100644
index 0000000..c83340f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepBindingTest.java
@@ -0,0 +1,156 @@
+// Copyright (c) 2023, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.keepanno;
+
+import static com.android.tools.r8.utils.codeinspector.Matchers.isAbsent;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.keepanno.annotations.KeepBinding;
+import com.android.tools.r8.keepanno.annotations.KeepCondition;
+import com.android.tools.r8.keepanno.annotations.KeepEdge;
+import com.android.tools.r8.keepanno.annotations.KeepTarget;
+import com.android.tools.r8.utils.AndroidApiLevel;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.google.common.collect.ImmutableList;
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+@RunWith(Parameterized.class)
+public class KeepBindingTest extends TestBase {
+
+  static final String EXPECTED = StringUtils.lines("A::foo");
+
+  private final TestParameters parameters;
+
+  @Parameterized.Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDefaultRuntimes().withApiLevel(AndroidApiLevel.B).build();
+  }
+
+  public KeepBindingTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testReference() throws Exception {
+    testForRuntime(parameters)
+        .addProgramClasses(getInputClasses())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED);
+  }
+
+  @Test
+  public void testWithRuleExtraction() throws Exception {
+    List<String> rules = getExtractedKeepRules();
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(getInputClassesWithoutAnnotations())
+        .addKeepRules(rules)
+        .addKeepClassRules(A.class, B.class)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(i -> checkOutput(i, true));
+  }
+
+  @Test
+  public void testWithRuleExtractionAndNoKeepOnClass() throws Exception {
+    List<String> rules = getExtractedKeepRules();
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(getInputClassesWithoutAnnotations())
+        .addKeepRules(rules)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(i -> checkOutput(i, false));
+  }
+
+  public List<Class<?>> getInputClasses() {
+    return ImmutableList.of(TestClass.class, A.class, B.class, C.class);
+  }
+
+  public List<byte[]> getInputClassesWithoutAnnotations() throws Exception {
+    return KeepEdgeAnnotationsTest.getInputClassesWithoutKeepAnnotations(getInputClasses());
+  }
+
+  public List<String> getExtractedKeepRules() throws Exception {
+    List<Class<?>> classes = getInputClasses();
+    List<String> rules = new ArrayList<>();
+    for (Class<?> clazz : classes) {
+      rules.addAll(KeepEdgeAnnotationsTest.getKeepRulesForClass(clazz));
+    }
+    return rules;
+  }
+
+  private void checkOutput(CodeInspector inspector, boolean expectB) {
+    assertThat(inspector.clazz(A.class), isPresent());
+    assertThat(inspector.clazz(A.class).uniqueMethodWithOriginalName("foo"), isPresent());
+    if (expectB) {
+      assertThat(inspector.clazz(B.class), isPresent());
+      assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("foo"), isAbsent());
+    } else {
+      assertThat(inspector.clazz(B.class), isAbsent());
+    }
+    assertThat(inspector.clazz(C.class), isAbsent());
+  }
+
+  static class A {
+    public void foo() throws Exception {
+      System.out.println("A::foo");
+    }
+
+    public void bar() throws Exception {
+      getClass().getDeclaredMethod("foo").invoke(this);
+    }
+  }
+
+  static class B {
+    public void foo() throws Exception {
+      System.out.println("B::foo");
+    }
+
+    public void bar() throws Exception {
+      getClass().getDeclaredMethod("foo").invoke(this);
+    }
+  }
+
+  static class C {
+    public void foo() throws Exception {
+      System.out.println("C::foo");
+    }
+
+    public void bar() throws Exception {
+      getClass().getDeclaredMethod("foo").invoke(this);
+    }
+  }
+
+  /**
+   * This conditional rule expresses that if any class in the program has a live "bar" method then
+   * that same classes "foo" method is to be kept. The binding(s) establishes the relation between
+   * the holder of the two methods.
+   */
+  @KeepEdge(
+      bindings = {
+        @KeepBinding(bindingName = "Holder"),
+        @KeepBinding(bindingName = "BarMethod", classFromBinding = "Holder", methodName = "bar"),
+        @KeepBinding(bindingName = "FooMethod", classFromBinding = "Holder", methodName = "foo")
+      },
+      preconditions = {@KeepCondition(memberFromBinding = "BarMethod")},
+      consequences = {@KeepTarget(memberFromBinding = "FooMethod")})
+  static class TestClass {
+
+    public static void main(String[] args) throws Exception {
+      new A().bar();
+    }
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java
index 61c1a49..74da176 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java
@@ -49,7 +49,6 @@
   @Test
   public void testWithRuleExtraction() throws Exception {
     List<String> rules = getExtractedKeepRules();
-    rules.forEach(System.out::println);
     testForR8(parameters.getBackend())
         .addProgramClassFileData(getInputClassesWithoutAnnotations())
         .addKeepRules(rules)
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java
index 5ce0f22..e43398a 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java
@@ -51,7 +51,6 @@
   @Test
   public void testWithRuleExtraction() throws Exception {
     List<String> rules = getExtractedKeepRules();
-    rules.forEach(System.out::println);
     testForR8(parameters.getBackend())
         .addProgramClassFileData(getInputClassesWithoutAnnotations())
         .addKeepRules(rules)
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepUsesReflectionAnnotationWithAdditionalPreconditionTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepUsesReflectionAnnotationWithAdditionalPreconditionTest.java
index 33f2531..a9dc1f7 100644
--- a/src/test/java/com/android/tools/r8/keepanno/KeepUsesReflectionAnnotationWithAdditionalPreconditionTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepUsesReflectionAnnotationWithAdditionalPreconditionTest.java
@@ -77,7 +77,6 @@
   }
 
   private void checkOutput(CodeInspector inspector) {
-    assertThat(inspector.clazz(A.class), isPresent());
     assertThat(inspector.clazz(B.class), isPresent());
     assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("<init>"), isPresent());
     assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("bar"), isPresent());
diff --git a/src/test/java/com/android/tools/r8/keepanno/ast/KeepEdgeAstTest.java b/src/test/java/com/android/tools/r8/keepanno/ast/KeepEdgeAstTest.java
index ba732f5..b85a41b 100644
--- a/src/test/java/com/android/tools/r8/keepanno/ast/KeepEdgeAstTest.java
+++ b/src/test/java/com/android/tools/r8/keepanno/ast/KeepEdgeAstTest.java
@@ -33,7 +33,7 @@
 
   public static String extract(KeepEdge edge) {
     StringBuilder builder = new StringBuilder();
-    KeepRuleExtractor extractor = new KeepRuleExtractor(rule -> builder.append(rule).append('\n'));
+    KeepRuleExtractor extractor = new KeepRuleExtractor(builder::append);
     extractor.extract(edge);
     return builder.toString();
   }
@@ -47,7 +47,8 @@
                     .addTarget(KeepTarget.builder().setItemPattern(KeepItemPattern.any()).build())
                     .build())
             .build();
-    assertEquals(StringUtils.unixLines("-keep class * { *; }"), extract(edge));
+    assertEquals(
+        StringUtils.unixLines("-keep class *", "-keepclassmembers class * { *; }"), extract(edge));
   }
 
   @Test
@@ -67,7 +68,13 @@
     List<String> options =
         ImmutableList.of("shrinking", "obfuscation", "accessmodification", "annotationremoval");
     String allows = String.join(",allow", options);
-    assertEquals(StringUtils.unixLines("-keep,allow" + allows + " class * { *; }"), extract(edge));
+    // The "any" item will be split in two rules, one for the targeted types and one for the
+    // targeted members.
+    assertEquals(
+        StringUtils.unixLines(
+            "-keep,allow" + allows + " class *",
+            "-keepclassmembers,allow" + allows + " class * { *; }"),
+        extract(edge));
   }
 
   @Test
@@ -86,7 +93,9 @@
             .build();
     // Allow is just the ordered list of options.
     assertEquals(
-        StringUtils.unixLines("-keep,allowshrinking,allowobfuscation class * { *; }"),
+        StringUtils.unixLines(
+            "-keep,allowshrinking,allowobfuscation class *",
+            "-keepclassmembers,allowshrinking,allowobfuscation class * { *; }"),
         extract(edge));
   }