[KeepAnno] Add bindings to support condition and target dependencies.

This CL is primarly the annotation syntax and keep-edge AST. An
implementation to correctly extract rules will be added in follow-up
CLs.

Bug: b/248408342
Change-Id: Ib97c70b96e865ccedbe562ccfd4f2728f470e04e
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepBinding.java b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepBinding.java
new file mode 100644
index 0000000..b17a3e1
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepBinding.java
@@ -0,0 +1,39 @@
+// Copyright (c) 2022, 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.annotations;
+
+/**
+ * A binding of a keep item.
+ *
+ * <p>A binding allows referencing the exact instance of a match from a condition in other
+ * conditions and/or targets. It can also be used to reduce duplication of targets by sharing
+ * patterns.
+ *
+ * <p>See KeepTarget for documentation on specifying an item pattern.
+ */
+public @interface KeepBinding {
+
+  /** Name with which other bindings, conditions or targets can reference the bound item pattern. */
+  String bindingName();
+
+  String classFromBinding() default "";
+
+  String className() default "";
+
+  Class<?> classConstant() default Object.class;
+
+  String extendsClassName() default "";
+
+  Class<?> extendsClassConstant() default Object.class;
+
+  String methodName() default "";
+
+  String methodReturnType() default "";
+
+  String[] methodParameters() default {""};
+
+  String fieldName() default "";
+
+  String fieldType() default "";
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepCondition.java b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepCondition.java
index 2d5eb60..a0dbcf4 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepCondition.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepCondition.java
@@ -11,20 +11,14 @@
 /**
  * A condition for a keep edge.
  *
- * <p>The condition denotes a keep item:
- *
- * <ul>
- *   <li>a class, or pattern on classes;
- *   <li>a method, or pattern on methods; or
- *   <li>a field, or pattern on fields.
- * </ul>
- *
- * <p>The structure of a condition item is the same as for a target item but without a notion of
- * "keep options".
+ * <p>See KeepTarget for documentation on specifying an item pattern.
  */
 @Target(ElementType.ANNOTATION_TYPE)
 @Retention(RetentionPolicy.CLASS)
 public @interface KeepCondition {
+
+  String classFromBinding() default "";
+
   String className() default "";
 
   Class<?> classConstant() default Object.class;
@@ -33,6 +27,8 @@
 
   Class<?> extendsClassConstant() default Object.class;
 
+  String memberFromBinding() default "";
+
   String methodName() default "";
 
   String methodReturnType() default "";
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepConstants.java b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepConstants.java
index 02eb5df..1c7d3a5 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepConstants.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepConstants.java
@@ -33,6 +33,7 @@
     public static final Class<KeepEdge> CLASS = KeepEdge.class;
     public static final String DESCRIPTOR = getDescriptor(CLASS);
     public static final String description = "description";
+    public static final String bindings = "bindings";
     public static final String preconditions = "preconditions";
     public static final String consequences = "consequences";
   }
@@ -48,6 +49,9 @@
 
   // Implicit hidden item which is "super type" of Condition and Target.
   public static final class Item {
+    public static final String classFromBinding = "classFromBinding";
+    public static final String memberFromBinding = "memberFromBinding";
+
     public static final String className = "className";
     public static final String classConstant = "classConstant";
 
@@ -78,6 +82,12 @@
     public static final String fieldTypeDefaultValue = "";
   }
 
+  public static final class Binding {
+    public static final Class<KeepBinding> CLASS = KeepBinding.class;
+    public static final String DESCRIPTOR = getDescriptor(CLASS);
+    public static final String bindingName = "bindingName";
+  }
+
   public static final class Condition {
     public static final Class<KeepCondition> CLASS = KeepCondition.class;
     public static final String DESCRIPTOR = getDescriptor(CLASS);
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepEdge.java b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepEdge.java
index 329b153..fb2c560 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepEdge.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepEdge.java
@@ -13,6 +13,8 @@
 public @interface KeepEdge {
   String description() default "";
 
+  KeepBinding[] bindings() default {};
+
   KeepCondition[] preconditions() default {};
 
   KeepTarget[] consequences();
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepTarget.java b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepTarget.java
index e4cb263..be61b4a 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepTarget.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/annotations/KeepTarget.java
@@ -14,9 +14,9 @@
  * <p>The target denotes a keep item along with options for what to keep:
  *
  * <ul>
- *   <li>a class, or pattern on classes;
- *   <li>a method, or pattern on methods; or
- *   <li>a field, or pattern on fields.
+ *   <li>a pattern on classes;
+ *   <li>a pattern on methods; or
+ *   <li>a pattern on fields.
  * </ul>
  *
  * <p>The structure of a target item is the same as for a condition item but has the additional keep
@@ -26,29 +26,119 @@
 @Retention(RetentionPolicy.CLASS)
 public @interface KeepTarget {
 
-  // KeepTarget only content (keep options) =========
-
+  /**
+   * Define the options that do not need to be preserved for the target.
+   *
+   * <p>Mutually exclusive with `disallow`.
+   *
+   * <p>If none are specified the default is "allow none" / "disallow all".
+   */
   KeepOption[] allow() default {};
 
+  /**
+   * Define the options that *must* be preserved for the target.
+   *
+   * <p>Mutually exclusive with `allow`.
+   *
+   * <p>If none are specified the default is "allow none" / "disallow all".
+   */
   KeepOption[] disallow() default {};
 
-  // Shared KeepItem content ========================
+  /**
+   * Define the class-name pattern by reference to a binding.
+   *
+   * <p>Mutually exclusive with `className` and `classConstant`.
+   *
+   * <p>If none are specified the default is to match any class.
+   */
+  String classFromBinding() default "";
 
+  /**
+   * Define the class-name pattern by fully qualified class name.
+   *
+   * <p>Mutually exclusive with `classFromBinding` and `classConstant`.
+   *
+   * <p>If none are specified the default is to match any class.
+   */
   String className() default "";
 
+  /**
+   * Define the class-name pattern by reference to a Class constant.
+   *
+   * <p>Mutually exclusive with `classFromBinding` and `className`.
+   *
+   * <p>If none are specified the default is to match any class.
+   */
   Class<?> classConstant() default Object.class;
 
+  /**
+   * Define the extends pattern by fully qualified class name.
+   *
+   * <p>Mutually exclusive with `extendsClassConstant`.
+   *
+   * <p>If none are specified the default is to match any extends clause.
+   */
   String extendsClassName() default "";
 
+  /**
+   * Define the extends pattern by Class constant.
+   *
+   * <p>Mutually exclusive with `extendsClassName`.
+   *
+   * <p>If none are specified the default is to match any extends clause.
+   */
   Class<?> extendsClassConstant() default Object.class;
 
+  /**
+   * Define the member pattern in full by a reference to a binding.
+   *
+   * <p>Mutually exclusive with all other pattern properties. When a member binding is referenced
+   * this item is defined to be that item, including its class and member patterns.
+   */
+  String memberFromBinding() default "";
+
+  /**
+   * Define the method-name pattern by an exact method name.
+   *
+   * <p>Mutually exclusive with any field properties.
+   *
+   * <p>If none and other properties define this as a method the default matches any method name.
+   */
   String methodName() default "";
 
+  /**
+   * Define the method return-type pattern by a fully qualified type or 'void'.
+   *
+   * <p>Mutually exclusive with any field properties.
+   *
+   * <p>If none and other properties define this as a method the default matches any return type.
+   */
   String methodReturnType() default "";
 
+  /**
+   * Define the method parameters pattern by a list of fully qualified types.
+   *
+   * <p>Mutually exclusive with any field properties.
+   *
+   * <p>If none and other properties define this as a method the default matches any parameters.
+   */
   String[] methodParameters() default {""};
 
+  /**
+   * Define the field-name pattern by an exact field name.
+   *
+   * <p>Mutually exclusive with any method properties.
+   *
+   * <p>If none and other properties define this as a field the default matches any field name.
+   */
   String fieldName() default "";
 
+  /**
+   * Define the field-type pattern by a fully qualified type.
+   *
+   * <p>Mutually exclusive with any method properties.
+   *
+   * <p>If none and other properties define this as a field the default matches any field type.
+   */
   String fieldType() default "";
 }
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 5d23d5d..bb8dd5f 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
@@ -4,11 +4,14 @@
 package com.android.tools.r8.keepanno.asm;
 
 import com.android.tools.r8.keepanno.annotations.KeepConstants;
+import com.android.tools.r8.keepanno.annotations.KeepConstants.Binding;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Condition;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Edge;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Item;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Option;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Target;
+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;
@@ -278,6 +281,9 @@
 
     @Override
     public AnnotationVisitor visitArray(String name) {
+      if (name.equals(Edge.bindings)) {
+        return new KeepBindingsVisitor(builder::setBindings);
+      }
       if (name.equals(Edge.preconditions)) {
         return new KeepPreconditionsVisitor(builder::setPreconditions);
       }
@@ -304,7 +310,7 @@
         Consumer<KeepEdgeMetaInfo.Builder> addContext,
         KeepItemPattern context) {
       this.parent = parent;
-      preconditions.addCondition(KeepCondition.builder().setItem(context).build());
+      preconditions.addCondition(KeepCondition.builder().setItemPattern(context).build());
       addContext.accept(metaInfoBuilder);
     }
 
@@ -341,6 +347,28 @@
     }
   }
 
+  private static class KeepBindingsVisitor extends AnnotationVisitorBase {
+    private final Parent<KeepBindings> parent;
+    private final KeepBindings.Builder builder = KeepBindings.builder();
+
+    public KeepBindingsVisitor(Parent<KeepBindings> parent) {
+      this.parent = parent;
+    }
+
+    @Override
+    public AnnotationVisitor visitAnnotation(String name, String descriptor) {
+      if (descriptor.equals(KeepConstants.Binding.DESCRIPTOR)) {
+        return new KeepBindingVisitor(builder);
+      }
+      return super.visitAnnotation(name, descriptor);
+    }
+
+    @Override
+    public void visitEnd() {
+      parent.accept(builder.build());
+    }
+  }
+
   private static class KeepPreconditionsVisitor extends AnnotationVisitorBase {
     private final Parent<KeepPreconditions> parent;
     private final KeepPreconditions.Builder builder = KeepPreconditions.builder();
@@ -461,24 +489,31 @@
     }
   }
 
-  private static class ClassDeclaration extends SingleDeclaration<KeepQualifiedClassNamePattern> {
+  private static class ClassDeclaration extends SingleDeclaration<KeepClassReference> {
     @Override
     String kind() {
       return "class";
     }
 
-    @Override
-    KeepQualifiedClassNamePattern getDefaultValue() {
-      return KeepQualifiedClassNamePattern.any();
+    KeepClassReference wrap(KeepQualifiedClassNamePattern namePattern) {
+      return KeepClassReference.fromClassNamePattern(namePattern);
     }
 
     @Override
-    KeepQualifiedClassNamePattern parse(String name, Object value) {
+    KeepClassReference getDefaultValue() {
+      return wrap(KeepQualifiedClassNamePattern.any());
+    }
+
+    @Override
+    KeepClassReference parse(String name, Object value) {
+      if (name.equals(Item.classFromBinding) && value instanceof String) {
+        return KeepClassReference.fromBindingReference((String) value);
+      }
       if (name.equals(Item.classConstant) && value instanceof Type) {
-        return KeepQualifiedClassNamePattern.exact(((Type) value).getClassName());
+        return wrap(KeepQualifiedClassNamePattern.exact(((Type) value).getClassName()));
       }
       if (name.equals(Item.className) && value instanceof String) {
-        return KeepQualifiedClassNamePattern.exact(((String) value));
+        return wrap(KeepQualifiedClassNamePattern.exact(((String) value)));
       }
       return null;
     }
@@ -659,12 +694,20 @@
   }
 
   private abstract static class KeepItemVisitorBase extends AnnotationVisitorBase {
-    private final Parent<KeepItemPattern> parent;
+    private Parent<KeepItemPattern> parent;
     private final ClassDeclaration classDeclaration = new ClassDeclaration();
     private final ExtendsDeclaration extendsDeclaration = new ExtendsDeclaration();
     private final MemberDeclaration memberDeclaration = new MemberDeclaration();
 
     public KeepItemVisitorBase(Parent<KeepItemPattern> parent) {
+      setParent(parent);
+    }
+
+    public KeepItemVisitorBase() {}
+
+    void setParent(Parent<KeepItemPattern> parent) {
+      assert parent != null;
+      assert this.parent == null;
       this.parent = parent;
     }
 
@@ -691,13 +734,40 @@
     public void visitEnd() {
       parent.accept(
           KeepItemPattern.builder()
-              .setClassPattern(classDeclaration.getValue())
+              .setClassReference(classDeclaration.getValue())
               .setExtendsPattern(extendsDeclaration.getValue())
               .setMemberPattern(memberDeclaration.getValue())
               .build());
     }
   }
 
+  private static class KeepBindingVisitor extends KeepItemVisitorBase {
+
+    private final KeepBindings.Builder builder;
+    private String bindingName;
+    private KeepItemPattern item;
+
+    public KeepBindingVisitor(KeepBindings.Builder builder) {
+      this.builder = builder;
+      setParent(item -> this.item = item);
+    }
+
+    @Override
+    public void visit(String name, Object value) {
+      if (name.equals(Binding.bindingName) && value instanceof String) {
+        bindingName = (String) value;
+        return;
+      }
+      super.visit(name, value);
+    }
+
+    @Override
+    public void visitEnd() {
+      super.visitEnd();
+      builder.addBinding(bindingName, item);
+    }
+  }
+
   private static class StringArrayVisitor extends AnnotationVisitorBase {
 
     private final Consumer<List<String>> fn;
@@ -765,7 +835,7 @@
     }
 
     private KeepTargetVisitor(Parent<KeepTarget> parent, KeepTarget.Builder builder) {
-      super(item -> parent.accept(builder.setItem(item).build()));
+      super(item -> parent.accept(builder.setItemPattern(item).build()));
       this.builder = builder;
     }
 
@@ -782,7 +852,7 @@
   private static class KeepConditionVisitor extends KeepItemVisitorBase {
 
     public KeepConditionVisitor(Parent<KeepCondition> parent) {
-      super(item -> parent.accept(KeepCondition.builder().setItem(item).build()));
+      super(item -> parent.accept(KeepCondition.builder().setItemPattern(item).build()));
     }
   }
 
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeWriter.java b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeWriter.java
index a8f631a..774ea58 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeWriter.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/asm/KeepEdgeWriter.java
@@ -8,6 +8,7 @@
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Edge;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Item;
 import com.android.tools.r8.keepanno.annotations.KeepConstants.Target;
+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;
@@ -53,7 +54,10 @@
         condition -> {
           AnnotationVisitor conditionVisitor =
               arrayVisitor.visitAnnotation(ignoredArrayValueName, Condition.DESCRIPTOR);
-          writeItem(conditionVisitor, condition.getItemPattern());
+          if (condition.getItem().isBindingReference()) {
+            throw new Unimplemented();
+          }
+          writeItem(conditionVisitor, condition.getItem().asItemPattern());
         });
     arrayVisitor.visitEnd();
   }
@@ -70,16 +74,26 @@
           if (!target.getOptions().isKeepAll()) {
             throw new Unimplemented();
           }
-          writeItem(targetVisitor, target.getItem());
+          if (target.getItem().isBindingReference()) {
+            throw new Unimplemented();
+          }
+          writeItem(targetVisitor, target.getItem().asItemPattern());
         });
     arrayVisitor.visitEnd();
   }
 
   private void writeItem(AnnotationVisitor itemVisitor, KeepItemPattern item) {
-    if (item.isAny()) {
+    if (item.isAny(
+        binding -> {
+          throw new Unimplemented();
+        })) {
       throw new Unimplemented();
     }
-    KeepQualifiedClassNamePattern namePattern = item.getClassNamePattern();
+    KeepClassReference classReference = item.getClassReference();
+    if (classReference.isBindingReference()) {
+      throw new Unimplemented();
+    }
+    KeepQualifiedClassNamePattern namePattern = classReference.asClassNamePattern();
     if (namePattern.isExact()) {
       Type typeConstant = Type.getType(namePattern.getExactDescriptor());
       itemVisitor.visit(KeepConstants.Item.classConstant, typeConstant);
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
new file mode 100644
index 0000000..337631d
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepBindings.java
@@ -0,0 +1,122 @@
+// Copyright (c) 2022, 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.ast;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+public class KeepBindings {
+
+  public static Builder builder() {
+    return new Builder();
+  }
+
+  private static final KeepBindings NONE_INSTANCE = new KeepBindings(Collections.emptyMap());
+
+  private final Map<String, Binding> bindings;
+
+  private KeepBindings(Map<String, Binding> bindings) {
+    assert bindings != null;
+    this.bindings = bindings;
+  }
+
+  public static KeepBindings none() {
+    return NONE_INSTANCE;
+  }
+
+  public Binding get(String bindingReference) {
+    return bindings.get(bindingReference);
+  }
+
+  /**
+   * A unique binding.
+   *
+   * <p>The uniqueness / identity of a binding is critical as a binding denotes a concrete match in
+   * the precondition of a rule. In terms of proguard keep rules it provides the difference of:
+   *
+   * <pre>
+   *   -if class *Foo -keep class *Foo { void <init>(...); }
+   * </pre>
+   *
+   * and
+   *
+   * <pre>
+   *   -if class *Foo -keep class <1>Foo { void <init>(...); }
+   * </pre>
+   *
+   * The first case will keep all classes matching *Foo and there default constructors if any single
+   * live class matches. The second will keep the default constructors of the live classes that
+   * match.
+   *
+   * <p>This wrapper ensures that pattern equality does not imply binding equality.
+   */
+  public static class Binding {
+    private final KeepItemPattern item;
+
+    public Binding(KeepItemPattern item) {
+      this.item = item;
+    }
+
+    public KeepItemPattern getItem() {
+      return item;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return this == obj;
+    }
+
+    @Override
+    public int hashCode() {
+      return System.identityHashCode(this);
+    }
+  }
+
+  public static class Builder {
+    private final Map<String, KeepItemPattern> bindings = new HashMap<>();
+
+    public Builder addBinding(String name, KeepItemPattern itemPattern) {
+      if (name == null || itemPattern == null) {
+        throw new KeepEdgeException("Invalid binding of '" + name + "'");
+      }
+      KeepItemPattern old = bindings.put(name, itemPattern);
+      if (old != null) {
+        throw new KeepEdgeException("Multiple definitions for binding '" + name + "'");
+      }
+      return this;
+    }
+
+    public KeepBindings build() {
+      if (bindings.isEmpty()) {
+        return NONE_INSTANCE;
+      }
+      Map<String, Binding> definitions = new HashMap<>(bindings.size());
+      for (String name : bindings.keySet()) {
+        definitions.put(name, verifyAndCreateBinding(name));
+      }
+      return new KeepBindings(definitions);
+    }
+
+    private Binding verifyAndCreateBinding(String bindingDefinitionName) {
+      KeepItemPattern pattern = bindings.get(bindingDefinitionName);
+      for (String bindingReference : pattern.getBindingReferences()) {
+        // Currently, it is not possible to define mutually recursive items, so we only need
+        // to check against self.
+        if (bindingReference.equals(bindingDefinitionName)) {
+          throw new KeepEdgeException("Recursive binding for name '" + bindingReference + "'");
+        }
+        if (!bindings.containsKey(bindingReference)) {
+          throw new KeepEdgeException(
+              "Undefined binding for name '"
+                  + bindingReference
+                  + "' referenced in binding of '"
+                  + bindingDefinitionName
+                  + "'");
+        }
+      }
+      return new Binding(pattern);
+    }
+  }
+}
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
new file mode 100644
index 0000000..699c5bb
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepClassReference.java
@@ -0,0 +1,116 @@
+// Copyright (c) 2022, 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.ast;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.function.Predicate;
+
+public abstract class KeepClassReference {
+
+  public static KeepClassReference fromBindingReference(String bindingReference) {
+    return new BindingReference(bindingReference);
+  }
+
+  public static KeepClassReference fromClassNamePattern(
+      KeepQualifiedClassNamePattern classNamePattern) {
+    return new SomeItem(classNamePattern);
+  }
+
+  public boolean isBindingReference() {
+    return asBindingReference() != null;
+  }
+
+  public boolean isClassNamePattern() {
+    return asClassNamePattern() != null;
+  }
+
+  public String asBindingReference() {
+    return null;
+  }
+
+  public KeepQualifiedClassNamePattern asClassNamePattern() {
+    return null;
+  }
+
+  public abstract Collection<String> getBindingReferences();
+
+  public boolean isAny(Predicate<String> onReference) {
+    return isBindingReference()
+        ? onReference.test(asBindingReference())
+        : asClassNamePattern().isAny();
+  }
+
+  private static class BindingReference extends KeepClassReference {
+    private final String bindingReference;
+
+    private BindingReference(String bindingReference) {
+      assert bindingReference != null;
+      this.bindingReference = bindingReference;
+    }
+
+    @Override
+    public String asBindingReference() {
+      return bindingReference;
+    }
+
+    @Override
+    public Collection<String> getBindingReferences() {
+      return Collections.singletonList(bindingReference);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      BindingReference that = (BindingReference) o;
+      return bindingReference.equals(that.bindingReference);
+    }
+
+    @Override
+    public int hashCode() {
+      return bindingReference.hashCode();
+    }
+  }
+
+  private static class SomeItem extends KeepClassReference {
+    private final KeepQualifiedClassNamePattern classNamePattern;
+
+    private SomeItem(KeepQualifiedClassNamePattern classNamePattern) {
+      assert classNamePattern != null;
+      this.classNamePattern = classNamePattern;
+    }
+
+    @Override
+    public KeepQualifiedClassNamePattern asClassNamePattern() {
+      return classNamePattern;
+    }
+
+    @Override
+    public Collection<String> getBindingReferences() {
+      return Collections.emptyList();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      SomeItem someItem = (SomeItem) o;
+      return classNamePattern.equals(someItem.classNamePattern);
+    }
+
+    @Override
+    public int hashCode() {
+      return classNamePattern.hashCode();
+    }
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCondition.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCondition.java
index 9909097..de4b742 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCondition.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepCondition.java
@@ -19,29 +19,33 @@
 
   public static class Builder {
 
-    private KeepItemPattern itemPattern;
+    private KeepItemReference item;
 
     private Builder() {}
 
-    public Builder setItem(KeepItemPattern itemPattern) {
-      this.itemPattern = itemPattern;
+    public Builder setItemReference(KeepItemReference item) {
+      this.item = item;
       return this;
     }
 
+    public Builder setItemPattern(KeepItemPattern itemPattern) {
+      return setItemReference(KeepItemReference.fromItemPattern(itemPattern));
+    }
+
     public KeepCondition build() {
-      return new KeepCondition(itemPattern);
+      return new KeepCondition(item);
     }
   }
 
-  private final KeepItemPattern itemPattern;
+  private final KeepItemReference item;
 
-  private KeepCondition(KeepItemPattern itemPattern) {
-    assert itemPattern != null;
-    this.itemPattern = itemPattern;
+  private KeepCondition(KeepItemReference item) {
+    assert item != null;
+    this.item = item;
   }
 
-  public KeepItemPattern getItemPattern() {
-    return itemPattern;
+  public KeepItemReference getItem() {
+    return item;
   }
 
   @Override
@@ -53,16 +57,16 @@
       return false;
     }
     KeepCondition that = (KeepCondition) o;
-    return itemPattern.equals(that.itemPattern);
+    return item.equals(that.item);
   }
 
   @Override
   public int hashCode() {
-    return itemPattern.hashCode();
+    return item.hashCode();
   }
 
   @Override
   public String toString() {
-    return itemPattern.toString();
+    return item.toString();
   }
 }
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
index dbe52b0..8c890df 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepEdge.java
@@ -19,27 +19,40 @@
  * <p>TODO(b/248408342): Update the BNF and AST to be complete.
  *
  * <pre>
- *   EDGE ::= METAINFO PRECONDITIONS -> CONSEQUENCES
- *   METAINFO = [CONTEXT] [DESCRIPTION]
- *   CONTEXT = class-descriptor | method-descriptor | field-descriptor
- *   DESCRIPTION = string-content
+ *   EDGE ::= METAINFO BINDINGS PRECONDITIONS -> CONSEQUENCES
+ *   METAINFO ::= [CONTEXT] [DESCRIPTION]
+ *   CONTEXT ::= class-descriptor | method-descriptor | field-descriptor
+ *   DESCRIPTION ::= string-content
+ *
+ *   BINDINGS ::= (BINDING_NAME = ITEM_PATTERN)*
+ *   BINDING_NAME ::= string-content
+ *   BINDING_REFERENCE ::= BINDING_NAME
  *
  *   PRECONDITIONS ::= always | CONDITION+
- *   CONDITION ::= ITEM_PATTERN
+ *   CONDITION ::= ITEM_REFERENCE
  *
  *   CONSEQUENCES ::= TARGET+
- *   TARGET ::= OPTIONS ITEM_PATTERN
+ *   TARGET ::= OPTIONS ITEM_REFERENCE
  *   OPTIONS ::= keep-all | OPTION+
  *   OPTION ::= shrinking | optimizing | obfuscating | access-modification | annotation-removal
  *
+ *   ITEM_REFERENCE  ::= BINDING_REFERENCE | ITEM_PATTERN
+ *   CLASS_REFERENCE ::= BINDING_REFERENCE | QUALIFIED_CLASS_NAME_PATTERN
+ *
  *   ITEM_PATTERN
  *     ::= any
- *       | class QUALIFIED_CLASS_NAME_PATTERN extends EXTENDS_PATTERN { MEMBER_PATTERN }
+ *       | class CLASS_REFERENCE extends EXTENDS_PATTERN { MEMBER_PATTERN }
  *
  *   TYPE_PATTERN ::= any | exact type-descriptor
  *   PACKAGE_PATTERN ::= any | exact package-name
- *   QUALIFIED_CLASS_NAME_PATTERN ::= any | PACKAGE_PATTERN | UNQUALIFIED_CLASS_NAME_PATTERN
+ *
+ *   QUALIFIED_CLASS_NAME_PATTERN
+ *     ::= any
+ *       | PACKAGE_PATTERN UNQUALIFIED_CLASS_NAME_PATTERN
+ *       | BINDING_REFERENCE
+ *
  *   UNQUALIFIED_CLASS_NAME_PATTERN ::= any | exact simple-class-name
+ *
  *   EXTENDS_PATTERN ::= any | QUALIFIED_CLASS_NAME_PATTERN
  *
  *   MEMBER_PATTERN ::= none | all | FIELD_PATTERN | METHOD_PATTERN
@@ -65,11 +78,22 @@
 
   public static class Builder {
     private KeepEdgeMetaInfo metaInfo = KeepEdgeMetaInfo.none();
+    private KeepBindings bindings = KeepBindings.none();
     private KeepPreconditions preconditions = KeepPreconditions.always();
     private KeepConsequences consequences;
 
     private Builder() {}
 
+    public Builder setMetaInfo(KeepEdgeMetaInfo metaInfo) {
+      this.metaInfo = metaInfo;
+      return this;
+    }
+
+    public Builder setBindings(KeepBindings bindings) {
+      this.bindings = bindings;
+      return this;
+    }
+
     public Builder setPreconditions(KeepPreconditions preconditions) {
       this.preconditions = preconditions;
       return this;
@@ -80,16 +104,11 @@
       return this;
     }
 
-    public Builder setMetaInfo(KeepEdgeMetaInfo metaInfo) {
-      this.metaInfo = metaInfo;
-      return this;
-    }
-
     public KeepEdge build() {
       if (consequences.isEmpty()) {
         throw new KeepEdgeException("KeepEdge must have non-empty set of consequences.");
       }
-      return new KeepEdge(preconditions, consequences, metaInfo);
+      return new KeepEdge(metaInfo, bindings, preconditions, consequences);
     }
   }
 
@@ -98,23 +117,33 @@
   }
 
   private final KeepEdgeMetaInfo metaInfo;
+  private final KeepBindings bindings;
   private final KeepPreconditions preconditions;
   private final KeepConsequences consequences;
 
   private KeepEdge(
-      KeepPreconditions preconditions, KeepConsequences consequences, KeepEdgeMetaInfo metaInfo) {
+      KeepEdgeMetaInfo metaInfo,
+      KeepBindings bindings,
+      KeepPreconditions preconditions,
+      KeepConsequences consequences) {
+    assert metaInfo != null;
+    assert bindings != null;
     assert preconditions != null;
     assert consequences != null;
-    assert metaInfo != null;
+    this.metaInfo = metaInfo;
+    this.bindings = bindings;
     this.preconditions = preconditions;
     this.consequences = consequences;
-    this.metaInfo = metaInfo;
   }
 
   public KeepEdgeMetaInfo getMetaInfo() {
     return metaInfo;
   }
 
+  public KeepBindings getBindings() {
+    return bindings;
+  }
+
   public KeepPreconditions getPreconditions() {
     return preconditions;
   }
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 7f84090..2a86cd7 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
@@ -3,7 +3,9 @@
 // BSD-style license that can be found in the LICENSE file.
 package com.android.tools.r8.keepanno.ast;
 
+import java.util.Collection;
 import java.util.Objects;
+import java.util.function.Predicate;
 
 /**
  * A pattern for matching items in the program.
@@ -18,9 +20,7 @@
 public class KeepItemPattern {
 
   public static KeepItemPattern any() {
-    KeepItemPattern any = builder().any().build();
-    assert any.isAny();
-    return any;
+    return builder().any().build();
   }
 
   public static Builder builder() {
@@ -29,24 +29,29 @@
 
   public static class Builder {
 
-    private KeepQualifiedClassNamePattern classNamePattern = KeepQualifiedClassNamePattern.any();
+    private KeepClassReference classReference =
+        KeepClassReference.fromClassNamePattern(KeepQualifiedClassNamePattern.any());
     private KeepExtendsPattern extendsPattern = KeepExtendsPattern.any();
     private KeepMemberPattern memberPattern = KeepMemberPattern.none();
 
     private Builder() {}
 
     public Builder any() {
-      classNamePattern = KeepQualifiedClassNamePattern.any();
+      classReference = KeepClassReference.fromClassNamePattern(KeepQualifiedClassNamePattern.any());
       extendsPattern = KeepExtendsPattern.any();
       memberPattern = KeepMemberPattern.all();
       return this;
     }
 
-    public Builder setClassPattern(KeepQualifiedClassNamePattern qualifiedClassNamePattern) {
-      this.classNamePattern = qualifiedClassNamePattern;
+    public Builder setClassReference(KeepClassReference classReference) {
+      this.classReference = classReference;
       return this;
     }
 
+    public Builder setClassPattern(KeepQualifiedClassNamePattern qualifiedClassNamePattern) {
+      return setClassReference(KeepClassReference.fromClassNamePattern(qualifiedClassNamePattern));
+    }
+
     public Builder setExtendsPattern(KeepExtendsPattern extendsPattern) {
       this.extendsPattern = extendsPattern;
       return this;
@@ -58,33 +63,33 @@
     }
 
     public KeepItemPattern build() {
-      return new KeepItemPattern(classNamePattern, extendsPattern, memberPattern);
+      return new KeepItemPattern(classReference, extendsPattern, memberPattern);
     }
   }
 
-  private final KeepQualifiedClassNamePattern qualifiedClassPattern;
+  private final KeepClassReference classReference;
   private final KeepExtendsPattern extendsPattern;
   private final KeepMemberPattern memberPattern;
   // TODO: class annotations
 
   private KeepItemPattern(
-      KeepQualifiedClassNamePattern qualifiedClassPattern,
+      KeepClassReference classReference,
       KeepExtendsPattern extendsPattern,
       KeepMemberPattern memberPattern) {
-    assert qualifiedClassPattern != null;
+    assert classReference != null;
     assert extendsPattern != null;
     assert memberPattern != null;
-    this.qualifiedClassPattern = qualifiedClassPattern;
+    this.classReference = classReference;
     this.extendsPattern = extendsPattern;
     this.memberPattern = memberPattern;
   }
 
-  public boolean isAny() {
-    return qualifiedClassPattern.isAny() && extendsPattern.isAny() && memberPattern.isAll();
+  public boolean isAny(Predicate<String> onReference) {
+    return classReference.isAny(onReference) && extendsPattern.isAny() && memberPattern.isAll();
   }
 
-  public KeepQualifiedClassNamePattern getClassNamePattern() {
-    return qualifiedClassPattern;
+  public KeepClassReference getClassReference() {
+    return classReference;
   }
 
   public KeepExtendsPattern getExtendsPattern() {
@@ -95,6 +100,10 @@
     return memberPattern;
   }
 
+  public Collection<String> getBindingReferences() {
+    return classReference.getBindingReferences();
+  }
+
   @Override
   public boolean equals(Object obj) {
     if (this == obj) {
@@ -104,21 +113,21 @@
       return false;
     }
     KeepItemPattern that = (KeepItemPattern) obj;
-    return qualifiedClassPattern.equals(that.qualifiedClassPattern)
+    return classReference.equals(that.classReference)
         && extendsPattern.equals(that.extendsPattern)
         && memberPattern.equals(that.memberPattern);
   }
 
   @Override
   public int hashCode() {
-    return Objects.hash(qualifiedClassPattern, extendsPattern, memberPattern);
+    return Objects.hash(classReference, extendsPattern, memberPattern);
   }
 
   @Override
   public String toString() {
     return "KeepClassPattern{"
-        + "qualifiedClassPattern="
-        + qualifiedClassPattern
+        + "classReference="
+        + classReference
         + ", extendsPattern="
         + extendsPattern
         + ", memberPattern="
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
new file mode 100644
index 0000000..aaf713d
--- /dev/null
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepItemReference.java
@@ -0,0 +1,105 @@
+// Copyright (c) 2022, 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.ast;
+
+public abstract class KeepItemReference {
+
+  public static KeepItemReference fromBindingReference(String bindingReference) {
+    return new BindingReference(bindingReference);
+  }
+
+  public static KeepItemReference fromItemPattern(KeepItemPattern itemPattern) {
+    return new SomeItem(itemPattern);
+  }
+
+  public boolean isBindingReference() {
+    return asBindingReference() != null;
+  }
+
+  public boolean isItemPattern() {
+    return asItemPattern() != null;
+  }
+
+  public String asBindingReference() {
+    return null;
+  }
+
+  public KeepItemPattern asItemPattern() {
+    return null;
+  }
+
+  public abstract KeepItemPattern lookupItemPattern(KeepBindings bindings);
+
+  private static class BindingReference extends KeepItemReference {
+    private final String bindingReference;
+
+    private BindingReference(String bindingReference) {
+      assert bindingReference != null;
+      this.bindingReference = bindingReference;
+    }
+
+    @Override
+    public String asBindingReference() {
+      return bindingReference;
+    }
+
+    @Override
+    public KeepItemPattern lookupItemPattern(KeepBindings bindings) {
+      return bindings.get(bindingReference).getItem();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      BindingReference that = (BindingReference) o;
+      return bindingReference.equals(that.bindingReference);
+    }
+
+    @Override
+    public int hashCode() {
+      return bindingReference.hashCode();
+    }
+  }
+
+  private static class SomeItem extends KeepItemReference {
+    private final KeepItemPattern itemPattern;
+
+    private SomeItem(KeepItemPattern itemPattern) {
+      assert itemPattern != null;
+      this.itemPattern = itemPattern;
+    }
+
+    @Override
+    public KeepItemPattern asItemPattern() {
+      return itemPattern;
+    }
+
+    @Override
+    public KeepItemPattern lookupItemPattern(KeepBindings bindings) {
+      return asItemPattern();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      SomeItem someItem = (SomeItem) o;
+      return itemPattern.equals(someItem.itemPattern);
+    }
+
+    @Override
+    public int hashCode() {
+      return itemPattern.hashCode();
+    }
+  }
+}
diff --git a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTarget.java b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTarget.java
index 6b7a212..30af390 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTarget.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/ast/KeepTarget.java
@@ -9,16 +9,20 @@
 
   public static class Builder {
 
-    private KeepItemPattern item;
+    private KeepItemReference item;
     private KeepOptions options = KeepOptions.keepAll();
 
     private Builder() {}
 
-    public Builder setItem(KeepItemPattern item) {
+    public Builder setItemReference(KeepItemReference item) {
       this.item = item;
       return this;
     }
 
+    public Builder setItemPattern(KeepItemPattern itemPattern) {
+      return setItemReference(KeepItemReference.fromItemPattern(itemPattern));
+    }
+
     public Builder setOptions(KeepOptions options) {
       this.options = options;
       return this;
@@ -32,10 +36,10 @@
     }
   }
 
-  private final KeepItemPattern item;
+  private final KeepItemReference item;
   private final KeepOptions options;
 
-  private KeepTarget(KeepItemPattern item, KeepOptions options) {
+  private KeepTarget(KeepItemReference item, KeepOptions options) {
     assert item != null;
     assert options != null;
     this.item = item;
@@ -46,7 +50,7 @@
     return new Builder();
   }
 
-  public KeepItemPattern getItem() {
+  public KeepItemReference getItem() {
     return item;
   }
 
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 f5739e1..db4362a 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,6 +3,8 @@
 // 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;
@@ -12,6 +14,7 @@
 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;
@@ -28,7 +31,11 @@
 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.function.BiConsumer;
 import java.util.function.Consumer;
 import java.util.stream.Collectors;
 
@@ -42,7 +49,8 @@
 
   public void extract(KeepEdge edge) {
     List<ItemRule> consequentRules = getConsequentRules(edge.getConsequences());
-    printConditionalRules(consequentRules, edge.getPreconditions(), edge.getMetaInfo());
+    printConditionalRules(
+        consequentRules, edge.getPreconditions(), edge.getMetaInfo(), edge.getBindings());
   }
 
   private List<ItemRule> getConsequentRules(KeepConsequences consequences) {
@@ -93,13 +101,22 @@
   }
 
   private void printConditionalRules(
-      List<ItemRule> consequentRules, KeepPreconditions preconditions, KeepEdgeMetaInfo metaInfo) {
+      List<ItemRule> consequentRules,
+      KeepPreconditions preconditions,
+      KeepEdgeMetaInfo metaInfo,
+      KeepBindings bindings) {
     boolean[] hasAtLeastOneConditionalClause = new boolean[1];
     preconditions.forEach(
         condition -> {
-          KeepItemPattern conditionItem = condition.getItemPattern();
+          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()) {
+          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;
@@ -110,15 +127,36 @@
                 // the preconditions hold.
                 StringBuilder builder = new StringBuilder();
                 printHeader(builder, metaInfo);
+                Map<String, Integer> bindingToBackReference = new HashMap<>();
                 if (!consequentItem.isMemberOnlyConsequent()
+                    || !conditionItem.getMemberPattern().isNone()
                     || !conditionItem
-                        .getClassNamePattern()
-                        .equals(consequentItem.getHolderPattern())) {
+                        .getClassReference()
+                        .equals(consequentItem.getHolderReference())) {
                   builder.append("-if ");
-                  printItem(builder, conditionItem);
+                  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);
+                printConsequentRule(builder, consequentItem, bindingToBackReference);
                 ruleConsumer.accept(builder.toString());
               });
         });
@@ -129,12 +167,13 @@
           r -> {
             StringBuilder builder = new StringBuilder();
             printHeader(builder, metaInfo);
-            ruleConsumer.accept(printConsequentRule(builder, r).toString());
+            ruleConsumer.accept(printConsequentRule(builder, r, Collections.emptyMap()).toString());
           });
     }
   }
 
-  private static StringBuilder printConsequentRule(StringBuilder builder, ItemRule rule) {
+  private static StringBuilder printConsequentRule(
+      StringBuilder builder, ItemRule rule, Map<String, Integer> bindingToBackReference) {
     if (rule.isMemberOnlyConsequent()) {
       builder.append("-keepclassmembers");
     } else {
@@ -145,12 +184,15 @@
         builder.append(",allow").append(getOptionString(option));
       }
     }
-    return builder.append(" ").append(rule.getKeepRuleForItem());
+    return builder.append(" ").append(rule.getKeepRuleForItem(bindingToBackReference));
   }
 
-  private static StringBuilder printItem(StringBuilder builder, KeepItemPattern clazzPattern) {
+  private static StringBuilder printItem(
+      StringBuilder builder,
+      KeepItemPattern clazzPattern,
+      BiConsumer<StringBuilder, KeepClassReference> printClassReference) {
     builder.append("class ");
-    printClassName(builder, clazzPattern.getClassNamePattern());
+    printClassReference.accept(builder, clazzPattern.getClassReference());
     KeepExtendsPattern extendsPattern = clazzPattern.getExtendsPattern();
     if (!extendsPattern.isAny()) {
       builder.append(" extends ");
@@ -381,19 +423,53 @@
     }
 
     public boolean isMemberOnlyConsequent() {
-      KeepItemPattern item = target.getItem();
-      return !item.isAny() && !item.getMemberPattern().isNone();
+      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 KeepQualifiedClassNamePattern getHolderPattern() {
-      return target.getItem().getClassNamePattern();
+    public KeepClassReference getHolderReference() {
+      if (target.getItem().isBindingReference()) {
+        throw new Unimplemented();
+      }
+      return target.getItem().asItemPattern().getClassReference();
     }
 
-    public String getKeepRuleForItem() {
+    public String getKeepRuleForItem(Map<String, Integer> bindingToBackReference) {
       if (ruleLine == null) {
-        KeepItemPattern item = target.getItem();
+        if (target.getItem().isBindingReference()) {
+          throw new Unimplemented();
+        }
+        KeepItemPattern item = target.getItem().asItemPattern();
         ruleLine =
-            item.isAny() ? "class * { *; }" : printItem(new StringBuilder(), item).toString();
+            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/processor/KeepEdgeProcessor.java b/src/keepanno/java/com/android/tools/r8/keepanno/processor/KeepEdgeProcessor.java
index fe49466..80a6ec5 100644
--- a/src/keepanno/java/com/android/tools/r8/keepanno/processor/KeepEdgeProcessor.java
+++ b/src/keepanno/java/com/android/tools/r8/keepanno/processor/KeepEdgeProcessor.java
@@ -165,13 +165,13 @@
   private void processCondition(KeepCondition.Builder builder, AnnotationMirror mirror) {
     KeepItemPattern.Builder itemBuilder = KeepItemPattern.builder();
     processItem(itemBuilder, mirror);
-    builder.setItem(itemBuilder.build());
+    builder.setItemPattern(itemBuilder.build());
   }
 
   private void processTarget(KeepTarget.Builder builder, AnnotationMirror mirror) {
     KeepItemPattern.Builder itemBuilder = KeepItemPattern.builder();
     processItem(itemBuilder, mirror);
-    builder.setItem(itemBuilder.build());
+    builder.setItemPattern(itemBuilder.build());
   }
 
   private void processItem(KeepItemPattern.Builder builder, AnnotationMirror mirror) {
diff --git a/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java
new file mode 100644
index 0000000..61c1a49
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarAnyClassTest.java
@@ -0,0 +1,124 @@
+// Copyright (c) 2022, 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.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.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 KeepFooIfBarAnyClassTest 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 KeepFooIfBarAnyClassTest(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();
+    rules.forEach(System.out::println);
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(getInputClassesWithoutAnnotations())
+        .addKeepRules(rules)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(this::checkOutput);
+  }
+
+  public List<Class<?>> getInputClasses() {
+    return ImmutableList.of(TestClass.class, A.class, B.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) {
+    assertThat(inspector.clazz(A.class), isPresent());
+    assertThat(inspector.clazz(A.class).uniqueMethodWithOriginalName("foo"), isPresent());
+    assertThat(inspector.clazz(B.class), isPresent());
+    assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("foo"), isPresent());
+  }
+
+  @KeepEdge(consequences = {@KeepTarget(classConstant = A.class)})
+  static class A {
+    public void foo() throws Exception {
+      System.out.println("A::foo");
+    }
+
+    public void bar() throws Exception {
+      getClass().getDeclaredMethod("foo").invoke(this);
+    }
+  }
+
+  @KeepEdge(consequences = {@KeepTarget(classConstant = B.class)})
+  static class B {
+    public void foo() throws Exception {
+      System.out.println("B::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
+   * all methods named "foo" on *any class* are to be kept. This most definitely not the rule one
+   * would want but is here to contrast with a rule that expresses the relationship between the
+   * holder or the two methods.
+   */
+  @KeepEdge(
+      preconditions = {@KeepCondition(methodName = "bar")},
+      consequences = {@KeepTarget(methodName = "foo")})
+  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/KeepFooIfBarSameClassTest.java b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java
new file mode 100644
index 0000000..5ce0f22
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/keepanno/KeepFooIfBarSameClassTest.java
@@ -0,0 +1,129 @@
+// Copyright (c) 2022, 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 KeepFooIfBarSameClassTest 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 KeepFooIfBarSameClassTest(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();
+    rules.forEach(System.out::println);
+    testForR8(parameters.getBackend())
+        .addProgramClassFileData(getInputClassesWithoutAnnotations())
+        .addKeepRules(rules)
+        .addKeepMainRule(TestClass.class)
+        .setMinApi(parameters.getApiLevel())
+        .run(parameters.getRuntime(), TestClass.class)
+        .assertSuccessWithOutput(EXPECTED)
+        .inspect(this::checkOutput);
+  }
+
+  public List<Class<?>> getInputClasses() {
+    return ImmutableList.of(TestClass.class, A.class, B.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) {
+    assertThat(inspector.clazz(A.class), isPresent());
+    assertThat(inspector.clazz(A.class).uniqueMethodWithOriginalName("foo"), isPresent());
+    assertThat(inspector.clazz(B.class), isPresent());
+    assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("foo"), isAbsent());
+    assertThat(inspector.clazz(B.class).uniqueMethodWithOriginalName("bar"), isAbsent());
+    // TODO(b/248408342): R8 full is keeping the default constructor. Avoid that.
+    assertThat(inspector.clazz(B.class).uniqueInstanceInitializer(), isPresent());
+  }
+
+  @KeepEdge(consequences = {@KeepTarget(classConstant = A.class)})
+  static class A {
+    public void foo() throws Exception {
+      System.out.println("A::foo");
+    }
+
+    public void bar() throws Exception {
+      getClass().getDeclaredMethod("foo").invoke(this);
+    }
+  }
+
+  @KeepEdge(consequences = {@KeepTarget(classConstant = B.class)})
+  static class B {
+    public void foo() throws Exception {
+      System.out.println("B::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 establishes the relation between the
+   * holder of the two methods.
+   */
+  @KeepEdge(
+      bindings = {@KeepBinding(bindingName = "Holder")},
+      preconditions = {@KeepCondition(classFromBinding = "Holder", methodName = "bar")},
+      consequences = {@KeepTarget(classFromBinding = "Holder", methodName = "foo")})
+  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/ast/KeepEdgeAstTest.java b/src/test/java/com/android/tools/r8/keepanno/ast/KeepEdgeAstTest.java
index 0386448..ba732f5 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
@@ -44,7 +44,7 @@
         KeepEdge.builder()
             .setConsequences(
                 KeepConsequences.builder()
-                    .addTarget(KeepTarget.builder().setItem(KeepItemPattern.any()).build())
+                    .addTarget(KeepTarget.builder().setItemPattern(KeepItemPattern.any()).build())
                     .build())
             .build();
     assertEquals(StringUtils.unixLines("-keep class * { *; }"), extract(edge));
@@ -58,7 +58,7 @@
                 KeepConsequences.builder()
                     .addTarget(
                         KeepTarget.builder()
-                            .setItem(KeepItemPattern.any())
+                            .setItemPattern(KeepItemPattern.any())
                             .setOptions(KeepOptions.disallow(KeepOption.OPTIMIZING))
                             .build())
                     .build())
@@ -78,7 +78,7 @@
                 KeepConsequences.builder()
                     .addTarget(
                         KeepTarget.builder()
-                            .setItem(KeepItemPattern.any())
+                            .setItemPattern(KeepItemPattern.any())
                             .setOptions(
                                 KeepOptions.allow(KeepOption.OBFUSCATING, KeepOption.SHRINKING))
                             .build())
@@ -104,7 +104,7 @@
         KeepEdge.builder()
             .setPreconditions(
                 KeepPreconditions.builder()
-                    .addCondition(KeepCondition.builder().setItem(classItem(CLASS)).build())
+                    .addCondition(KeepCondition.builder().setItemPattern(classItem(CLASS)).build())
                     .build())
             .setConsequences(
                 KeepConsequences.builder()
@@ -126,7 +126,7 @@
         KeepEdge.builder()
             .setPreconditions(
                 KeepPreconditions.builder()
-                    .addCondition(KeepCondition.builder().setItem(classItem(CLASS)).build())
+                    .addCondition(KeepCondition.builder().setItemPattern(classItem(CLASS)).build())
                     .build())
             .setConsequences(KeepConsequences.builder().addTarget(target(classItem(CLASS))).build())
             .build();
@@ -140,7 +140,7 @@
         KeepEdge.builder()
             .setPreconditions(
                 KeepPreconditions.builder()
-                    .addCondition(KeepCondition.builder().setItem(classItem(CLASS)).build())
+                    .addCondition(KeepCondition.builder().setItemPattern(classItem(CLASS)).build())
                     .build())
             .setConsequences(
                 KeepConsequences.builder()
@@ -160,7 +160,7 @@
   }
 
   private KeepTarget target(KeepItemPattern item) {
-    return KeepTarget.builder().setItem(item).build();
+    return KeepTarget.builder().setItemPattern(item).build();
   }
 
   private KeepItemPattern classItem(String typeName) {
diff --git a/src/test/java/com/android/tools/r8/keepanno/testsource/KeepSourceEdges.java b/src/test/java/com/android/tools/r8/keepanno/testsource/KeepSourceEdges.java
index d4c7121..8958148 100644
--- a/src/test/java/com/android/tools/r8/keepanno/testsource/KeepSourceEdges.java
+++ b/src/test/java/com/android/tools/r8/keepanno/testsource/KeepSourceEdges.java
@@ -133,11 +133,11 @@
   }
 
   static KeepTarget mkTarget(KeepItemPattern item) {
-    return KeepTarget.builder().setItem(item).build();
+    return KeepTarget.builder().setItemPattern(item).build();
   }
 
   static KeepCondition mkCondition(KeepItemPattern item) {
-    return KeepCondition.builder().setItem(item).build();
+    return KeepCondition.builder().setItemPattern(item).build();
   }
 
   static KeepConsequences mkConsequences(KeepTarget... targets) {