Change field map in graph lenses to be bidirectional
This simplifies the lenses and makes the 'originalFieldSignatures' obsolete.
Change-Id: Idf76b5a6c140a2b01486e5826159b374c2e368d7
diff --git a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
index 887f10d..559d2f2 100644
--- a/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/AppliedGraphLens.java
@@ -6,7 +6,8 @@
import com.android.tools.r8.graph.GraphLens.NonIdentityGraphLens;
import com.android.tools.r8.utils.MapUtils;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import com.google.common.collect.ImmutableList;
@@ -25,8 +26,8 @@
*/
public final class AppliedGraphLens extends NonIdentityGraphLens {
- private final BidirectionalManyToOneMap<DexType, DexType> renamedTypeNames =
- new BidirectionalManyToOneMap<>();
+ private final MutableBidirectionalManyToOneMap<DexType, DexType> renamedTypeNames =
+ new BidirectionalManyToOneHashMap<>();
private final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
private final BiMap<DexMethod, DexMethod> originalMethodSignatures = HashBiMap.create();
@@ -102,11 +103,8 @@
@Override
public Iterable<DexType> getOriginalTypes(DexType type) {
- Set<DexType> originalTypes = renamedTypeNames.getKeysOrNull(type);
- if (originalTypes == null) {
- return ImmutableList.of(type);
- }
- return originalTypes;
+ Set<DexType> originalTypes = renamedTypeNames.getKeys(type);
+ return originalTypes.isEmpty() ? ImmutableList.of(type) : originalTypes;
}
@Override
diff --git a/src/main/java/com/android/tools/r8/graph/GraphLens.java b/src/main/java/com/android/tools/r8/graph/GraphLens.java
index 5a10844..b2d04e8 100644
--- a/src/main/java/com/android/tools/r8/graph/GraphLens.java
+++ b/src/main/java/com/android/tools/r8/graph/GraphLens.java
@@ -15,10 +15,12 @@
import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.collections.BidirectionalManyToManyRepresentativeMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.HashBiMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
@@ -32,6 +34,7 @@
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
import java.util.function.Predicate;
+import java.util.stream.Collectors;
/**
* A GraphLens implements a virtual view on top of the graph, used to delay global rewrites until
@@ -65,6 +68,10 @@
return reference;
}
+ public R getRewrittenReference(BidirectionalManyToOneRepresentativeMap<R, R> rewritings) {
+ return rewritings.getOrDefault(reference, reference);
+ }
+
public R getRewrittenReference(Map<R, R> rewritings) {
return rewritings.getOrDefault(reference, reference);
}
@@ -77,6 +84,11 @@
return reboundReference;
}
+ public R getRewrittenReboundReference(
+ BidirectionalManyToOneRepresentativeMap<R, R> rewritings) {
+ return rewritings.getOrDefault(reboundReference, reboundReference);
+ }
+
public R getRewrittenReboundReference(Map<R, R> rewritings) {
return rewritings.getOrDefault(reboundReference, reboundReference);
}
@@ -228,10 +240,10 @@
protected final Map<DexType, DexType> typeMap = new IdentityHashMap<>();
protected final Map<DexMethod, DexMethod> methodMap = new IdentityHashMap<>();
- protected final Map<DexField, DexField> fieldMap = new IdentityHashMap<>();
+ protected final MutableBidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap =
+ new BidirectionalManyToOneRepresentativeHashMap<>();
- protected final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
- protected final BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures =
+ protected final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
new BidirectionalOneToOneHashMap<>();
public void map(DexType from, DexType to) {
@@ -248,13 +260,6 @@
methodMap.put(from, to);
}
- public void map(DexField from, DexField to) {
- if (from == to) {
- return;
- }
- fieldMap.put(from, to);
- }
-
public void move(DexMethod from, DexMethod to) {
if (from == to) {
return;
@@ -268,7 +273,6 @@
return;
}
fieldMap.put(from, to);
- originalFieldSignatures.put(to, from);
}
public GraphLens build(DexItemFactory dexItemFactory) {
@@ -283,7 +287,6 @@
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory);
@@ -963,11 +966,10 @@
protected final Map<DexType, DexType> typeMap;
protected final Map<DexMethod, DexMethod> methodMap;
- protected final Map<DexField, DexField> fieldMap;
+ protected final BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap;
- // Maps that store the original signature of fields and methods that have been affected, for
- // example, by vertical class merging. Needed to generate a correct Proguard map in the end.
- protected final BiMap<DexField, DexField> originalFieldSignatures;
+ // Map that store the original signature of methods that have been affected, for example, by
+ // vertical class merging. Needed to generate a correct Proguard map in the end.
protected BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod>
originalMethodSignatures;
@@ -980,8 +982,7 @@
public NestedGraphLens(
Map<DexType, DexType> typeMap,
Map<DexMethod, DexMethod> methodMap,
- Map<DexField, DexField> fieldMap,
- BiMap<DexField, DexField> originalFieldSignatures,
+ BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
BidirectionalManyToManyRepresentativeMap<DexMethod, DexMethod> originalMethodSignatures,
GraphLens previousLens,
DexItemFactory dexItemFactory) {
@@ -993,7 +994,6 @@
this.typeMap = typeMap.isEmpty() ? null : typeMap;
this.methodMap = methodMap;
this.fieldMap = fieldMap;
- this.originalFieldSignatures = originalFieldSignatures;
this.originalMethodSignatures = originalMethodSignatures;
this.dexItemFactory = dexItemFactory;
}
@@ -1022,10 +1022,7 @@
@Override
public DexField getOriginalFieldSignature(DexField field) {
- DexField originalField =
- originalFieldSignatures != null
- ? originalFieldSignatures.getOrDefault(field, field)
- : field;
+ DexField originalField = fieldMap.getRepresentativeKeyOrDefault(field, field);
return getPrevious().getOriginalFieldSignature(originalField);
}
@@ -1038,9 +1035,7 @@
@Override
public DexField getRenamedFieldSignature(DexField originalField) {
DexField renamedField = getPrevious().getRenamedFieldSignature(originalField);
- return originalFieldSignatures != null
- ? originalFieldSignatures.inverse().getOrDefault(renamedField, renamedField)
- : renamedField;
+ return fieldMap.getOrDefault(renamedField, renamedField);
}
@Override
@@ -1221,10 +1216,15 @@
builder.append(entry.getKey().toSourceString()).append(" -> ");
builder.append(entry.getValue().toSourceString()).append(System.lineSeparator());
}
- for (Map.Entry<DexField, DexField> entry : fieldMap.entrySet()) {
- builder.append(entry.getKey().toSourceString()).append(" -> ");
- builder.append(entry.getValue().toSourceString()).append(System.lineSeparator());
- }
+ fieldMap.forEachManyToOneMapping(
+ (keys, value) -> {
+ builder.append(
+ keys.stream()
+ .map(DexField::toSourceString)
+ .collect(Collectors.joining("," + System.lineSeparator())));
+ builder.append(" -> ");
+ builder.append(value.toSourceString()).append(System.lineSeparator());
+ });
builder.append(getPrevious().toString());
return builder.toString();
}
diff --git a/src/main/java/com/android/tools/r8/graph/classmerging/HorizontallyMergedLambdaClasses.java b/src/main/java/com/android/tools/r8/graph/classmerging/HorizontallyMergedLambdaClasses.java
index 0b5bc41..89f34d7 100644
--- a/src/main/java/com/android/tools/r8/graph/classmerging/HorizontallyMergedLambdaClasses.java
+++ b/src/main/java/com/android/tools/r8/graph/classmerging/HorizontallyMergedLambdaClasses.java
@@ -8,7 +8,9 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.optimize.lambda.LambdaGroup;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import java.util.Collections;
import java.util.Map;
import java.util.Set;
@@ -19,8 +21,10 @@
private final BidirectionalManyToOneMap<DexType, DexType> mergedClasses;
public HorizontallyMergedLambdaClasses(Map<DexType, LambdaGroup> lambdas) {
- this.mergedClasses = new BidirectionalManyToOneMap<>();
+ MutableBidirectionalManyToOneMap<DexType, DexType> mergedClasses =
+ new BidirectionalManyToOneHashMap<>();
lambdas.forEach((lambda, group) -> mergedClasses.put(lambda, group.getGroupClassType()));
+ this.mergedClasses = mergedClasses;
}
public static HorizontallyMergedLambdaClasses empty() {
@@ -29,7 +33,7 @@
@Override
public void forEachMergeGroup(BiConsumer<Set<DexType>, DexType> consumer) {
- mergedClasses.forEach(consumer);
+ mergedClasses.forEachManyToOneMapping(consumer);
}
@Override
diff --git a/src/main/java/com/android/tools/r8/graph/classmerging/StaticallyMergedClasses.java b/src/main/java/com/android/tools/r8/graph/classmerging/StaticallyMergedClasses.java
index 79e4ef7..0e1dbe5 100644
--- a/src/main/java/com/android/tools/r8/graph/classmerging/StaticallyMergedClasses.java
+++ b/src/main/java/com/android/tools/r8/graph/classmerging/StaticallyMergedClasses.java
@@ -8,7 +8,10 @@
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import java.util.Set;
import java.util.function.BiConsumer;
@@ -21,7 +24,7 @@
}
public static StaticallyMergedClasses empty() {
- return new StaticallyMergedClasses(BidirectionalManyToOneMap.empty());
+ return new StaticallyMergedClasses(new EmptyBidirectionalOneToOneMap<>());
}
public static Builder builder() {
@@ -30,7 +33,7 @@
@Override
public void forEachMergeGroup(BiConsumer<Set<DexType>, DexType> consumer) {
- mergedClasses.forEach(consumer);
+ mergedClasses.forEachManyToOneMapping(consumer);
}
@Override
@@ -45,8 +48,8 @@
public static class Builder {
- private final BidirectionalManyToOneMap<DexType, DexType> mergedClasses =
- new BidirectionalManyToOneMap<>();
+ private final MutableBidirectionalManyToOneMap<DexType, DexType> mergedClasses =
+ new BidirectionalManyToOneHashMap<>();
private Builder() {}
diff --git a/src/main/java/com/android/tools/r8/graph/classmerging/VerticallyMergedClasses.java b/src/main/java/com/android/tools/r8/graph/classmerging/VerticallyMergedClasses.java
index 6ba32e9..b9ab790 100644
--- a/src/main/java/com/android/tools/r8/graph/classmerging/VerticallyMergedClasses.java
+++ b/src/main/java/com/android/tools/r8/graph/classmerging/VerticallyMergedClasses.java
@@ -8,6 +8,7 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
import java.util.Collection;
import java.util.Map;
import java.util.Set;
@@ -22,12 +23,12 @@
}
public static VerticallyMergedClasses empty() {
- return new VerticallyMergedClasses(BidirectionalManyToOneMap.empty());
+ return new VerticallyMergedClasses(new EmptyBidirectionalOneToOneMap<>());
}
@Override
public void forEachMergeGroup(BiConsumer<Set<DexType>, DexType> consumer) {
- mergedClasses.forEach(consumer);
+ mergedClasses.forEachManyToOneMapping(consumer);
}
public Map<DexType, DexType> getForwardMap() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInstanceFieldsMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInstanceFieldsMerger.java
index 26ed21c..96282ee 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInstanceFieldsMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassInstanceFieldsMerger.java
@@ -5,11 +5,12 @@
package com.android.tools.r8.horizontalclassmerging;
import com.android.tools.r8.graph.DexEncodedField;
-import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.horizontalclassmerging.HorizontalClassMergerGraphLens.Builder;
+import com.android.tools.r8.utils.IterableUtils;
import com.android.tools.r8.utils.ListUtils;
+import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.Collection;
import java.util.IdentityHashMap;
@@ -50,20 +51,19 @@
}
}
- private void mergeField(DexEncodedField oldField, DexEncodedField newField) {
- if (newField.isFinal() && !oldField.isFinal()) {
+ private void fixAccessFlags(DexEncodedField newField, Collection<DexEncodedField> oldFields) {
+ if (newField.isFinal() && Iterables.any(oldFields, oldField -> !oldField.isFinal())) {
newField.getAccessFlags().demoteFromFinal();
}
- lensBuilder.moveField(oldField.field, newField.field);
}
- private void mergeFields(DexEncodedField newField, Collection<DexEncodedField> oldFields) {
- DexField newFieldReference = newField.getReference();
-
- lensBuilder.moveField(newFieldReference, newFieldReference);
- lensBuilder.setRepresentativeField(newFieldReference, newFieldReference);
-
- oldFields.forEach(oldField -> mergeField(oldField, newField));
+ private void mergeFields(DexEncodedField newField, List<DexEncodedField> oldFields) {
+ fixAccessFlags(newField, oldFields);
+ lensBuilder.recordNewFieldSignature(
+ Iterables.transform(
+ IterableUtils.append(oldFields, newField), DexEncodedField::getReference),
+ newField.getReference(),
+ newField.getReference());
}
public void merge() {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
index 7bc85d1..80180f6 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ClassStaticFieldsMerger.java
@@ -33,7 +33,7 @@
this.dexItemFactory = appView.dexItemFactory();
}
- private final boolean isFresh(DexField fieldReference) {
+ private boolean isFresh(DexField fieldReference) {
return !targetFields.containsKey(fieldReference);
}
@@ -48,7 +48,7 @@
field = field.toTypeSubstitutedField(newFieldReference);
targetFields.put(newFieldReference, field);
- lensBuilder.moveField(oldFieldReference, newFieldReference);
+ lensBuilder.recordNewFieldSignature(oldFieldReference, newFieldReference);
}
public void addFields(DexProgramClass toMerge) {
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
index 16f853e..9b472a4 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontalClassMergerGraphLens.java
@@ -13,8 +13,13 @@
import com.android.tools.r8.graph.RewrittenPrototypeDescription;
import com.android.tools.r8.ir.conversion.ExtraParameter;
import com.android.tools.r8.utils.IterableUtils;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneRepresentativeMap;
import com.google.common.collect.BiMap;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Streams;
import java.util.ArrayList;
import java.util.Collections;
import java.util.IdentityHashMap;
@@ -28,29 +33,24 @@
private final Map<DexMethod, List<ExtraParameter>> methodExtraParameters;
private final Map<DexMethod, DexMethod> extraOriginalMethodSignatures;
private final HorizontallyMergedClasses mergedClasses;
- private final Map<DexField, DexField> extraOriginalFieldSignatures;
private HorizontalClassMergerGraphLens(
AppView<?> appView,
HorizontallyMergedClasses mergedClasses,
Map<DexMethod, List<ExtraParameter>> methodExtraParameters,
- Map<DexField, DexField> fieldMap,
+ BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
Map<DexMethod, DexMethod> methodMap,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
Map<DexMethod, DexMethod> extraOriginalMethodSignatures,
- Map<DexField, DexField> extraOriginalFieldSignatures,
GraphLens previousLens) {
super(
mergedClasses.getForwardMap(),
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
appView.dexItemFactory());
this.methodExtraParameters = methodExtraParameters;
- this.extraOriginalFieldSignatures = extraOriginalFieldSignatures;
this.extraOriginalMethodSignatures = extraOriginalMethodSignatures;
this.mergedClasses = mergedClasses;
}
@@ -82,15 +82,6 @@
return getPrevious().getOriginalMethodSignature(originalConstructor);
}
- @Override
- public DexField getOriginalFieldSignature(DexField field) {
- DexField originalField = extraOriginalFieldSignatures.get(field);
- if (originalField == null) {
- return super.getOriginalFieldSignature(field);
- }
- return getPrevious().getOriginalFieldSignature(originalField);
- }
-
/**
* If an overloaded constructor is requested, add the constructor id as a parameter to the
* constructor. Otherwise return the lookup on the underlying graph lens.
@@ -111,7 +102,8 @@
}
public static class Builder {
- private ManyToOneMap<DexField, DexField> fieldMap = new ManyToOneMap<>();
+ private MutableBidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap =
+ new BidirectionalManyToOneRepresentativeHashMap<>();
private ManyToOneMap<DexMethod, DexMethod> methodMap = new ManyToOneMap<>();
private final Map<DexMethod, List<ExtraParameter>> methodExtraParameters =
new IdentityHashMap<>();
@@ -127,24 +119,14 @@
assert false;
return group.iterator().next();
});
- ManyToOneInverseMap<DexField, DexField> inverseFieldMap =
- fieldMap.inverse(
- group -> {
- // Every group should have a representative. Fail in debug mode.
- assert false;
- return group.iterator().next();
- });
-
return new HorizontalClassMergerGraphLens(
appView,
mergedClasses,
methodExtraParameters,
- fieldMap.getForwardMap(),
+ fieldMap,
methodMap.getForwardMap(),
- inverseFieldMap.getBiMap().getForwardBacking(),
inverseMethodMap.getBiMap(),
inverseMethodMap.getExtraMap(),
- inverseFieldMap.getExtraMap(),
appView.graphLens());
}
@@ -152,39 +134,51 @@
methodMap = methodMap.remap(remapMethods, Function.identity(), Function.identity());
}
- public void remapFields(BiMap<DexField, DexField> remapFields) {
- fieldMap = fieldMap.remap(remapFields, Function.identity(), Function.identity());
- }
-
- public Builder moveField(DexField from, DexField to) {
- fieldMap.put(from, to);
- fieldMap.putInverse(from, to);
+ Builder recordNewFieldSignature(DexField oldFieldSignature, DexField newFieldSignature) {
+ Set<DexField> originalFieldSignatures = fieldMap.removeValue(oldFieldSignature);
+ if (originalFieldSignatures.isEmpty()) {
+ fieldMap.put(oldFieldSignature, newFieldSignature);
+ } else if (originalFieldSignatures.size() == 1) {
+ fieldMap.put(originalFieldSignatures.iterator().next(), newFieldSignature);
+ } else {
+ for (DexField originalFieldSignature : originalFieldSignatures) {
+ fieldMap.put(originalFieldSignature, newFieldSignature);
+ }
+ DexField representative = fieldMap.removeRepresentativeFor(oldFieldSignature);
+ assert representative != null;
+ fieldMap.setRepresentative(newFieldSignature, representative);
+ }
return this;
}
- public Builder setRepresentativeField(DexField from, DexField to) {
- fieldMap.setRepresentative(from, to);
+ Builder recordNewFieldSignature(
+ Iterable<DexField> oldFieldSignatures,
+ DexField newFieldSignature,
+ DexField representative) {
+ assert Streams.stream(oldFieldSignatures).noneMatch(fieldMap::containsValue);
+ assert Iterables.contains(oldFieldSignatures, representative);
+ for (DexField oldFieldSignature : oldFieldSignatures) {
+ fieldMap.put(oldFieldSignature, newFieldSignature);
+ }
+ fieldMap.setRepresentative(newFieldSignature, representative);
return this;
}
/** Unidirectional mapping from one method to another. */
public Builder recordExtraOriginalSignature(DexMethod from, DexMethod to) {
methodMap.setRepresentative(from, to);
-
return this;
}
/** Unidirectional mapping from one method to another. */
public Builder mapMethod(DexMethod from, DexMethod to) {
methodMap.put(from, to);
-
return this;
}
/** Unidirectional mapping from one method to another. */
public Builder mapMethodInverse(DexMethod from, DexMethod to) {
methodMap.putInverse(from, to);
-
return this;
}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontallyMergedClasses.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontallyMergedClasses.java
index 4d6d93f..ff108a4 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontallyMergedClasses.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/HorizontallyMergedClasses.java
@@ -8,7 +8,10 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.classmerging.MergedClasses;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;
@@ -22,12 +25,12 @@
}
public static HorizontallyMergedClasses empty() {
- return new HorizontallyMergedClasses(new BidirectionalManyToOneMap<>());
+ return new HorizontallyMergedClasses(new EmptyBidirectionalOneToOneMap<>());
}
@Override
public void forEachMergeGroup(BiConsumer<Set<DexType>, DexType> consumer) {
- mergedClasses.forEach(consumer);
+ mergedClasses.forEachManyToOneMapping(consumer);
}
public DexType getMergeTargetOrDefault(DexType type) {
@@ -44,11 +47,11 @@
@Override
public boolean hasBeenMergedIntoDifferentType(DexType type) {
- return mergedClasses.hasKey(type);
+ return mergedClasses.containsKey(type);
}
public boolean isMergeTarget(DexType type) {
- return mergedClasses.hasValue(type);
+ return mergedClasses.containsValue(type);
}
public boolean hasBeenMergedOrIsMergeTarget(DexType type) {
@@ -71,8 +74,8 @@
}
public static class Builder {
- private final BidirectionalManyToOneMap<DexType, DexType> mergedClasses =
- new BidirectionalManyToOneMap<>();
+ private final MutableBidirectionalManyToOneMap<DexType, DexType> mergedClasses =
+ new BidirectionalManyToOneHashMap<>();
public HorizontallyMergedClasses build() {
return new HorizontallyMergedClasses(mergedClasses);
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneInverseMap.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneInverseMap.java
index 973162f..8cf8b2a 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneInverseMap.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneInverseMap.java
@@ -4,20 +4,20 @@
package com.android.tools.r8.horizontalclassmerging;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
import java.util.Map;
/** The inverse of a {@link ManyToOneMap} used for generating graph lens maps. */
public class ManyToOneInverseMap<K, V> {
- private final BidirectionalOneToOneHashMap<V, K> biMap;
+ private final BidirectionalOneToOneMap<V, K> biMap;
private final Map<V, K> extraMap;
- ManyToOneInverseMap(BidirectionalOneToOneHashMap<V, K> biMap, Map<V, K> extraMap) {
+ ManyToOneInverseMap(BidirectionalOneToOneMap<V, K> biMap, Map<V, K> extraMap) {
this.biMap = biMap;
this.extraMap = extraMap;
}
- public BidirectionalOneToOneHashMap<V, K> getBiMap() {
+ public BidirectionalOneToOneMap<V, K> getBiMap() {
return biMap;
}
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneMap.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneMap.java
index 5204021..f51dfd2 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneMap.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/ManyToOneMap.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.horizontalclassmerging;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import java.util.HashMap;
@@ -50,7 +51,7 @@
}
public ManyToOneInverseMap<K, V> inverse(Function<Set<K>, K> pickRepresentative) {
- BidirectionalOneToOneHashMap<V, K> biMap = new BidirectionalOneToOneHashMap<>();
+ MutableBidirectionalOneToOneMap<V, K> biMap = new BidirectionalOneToOneHashMap<>();
Map<V, K> extraMap = new HashMap<>();
for (Entry<V, Set<K>> entry : inverseMap.entrySet()) {
K representative = representativeMap.get(entry.getKey());
diff --git a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
index da61076..045a8b1 100644
--- a/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
+++ b/src/main/java/com/android/tools/r8/horizontalclassmerging/TreeFixer.java
@@ -46,7 +46,6 @@
private final AppView<AppInfoWithLiveness> appView;
private final DexItemFactory dexItemFactory;
private final BiMap<DexMethod, DexMethod> movedMethods = HashBiMap.create();
- private final BiMap<DexField, DexField> movedFields = HashBiMap.create();
private final SyntheticArgumentClass syntheticArgumentClass;
private final BiMap<DexMethodSignature, DexMethodSignature> reservedInterfaceSignatures =
HashBiMap.create();
@@ -130,7 +129,6 @@
}
lensBuilder.remapMethods(movedMethods);
- lensBuilder.remapFields(movedFields);
HorizontalClassMergerGraphLens lens = lensBuilder.build(appView, mergedClasses);
fieldAccessChangesBuilder.build(this::fixupMethodReference).modify(appView);
@@ -365,26 +363,26 @@
Set<DexField> existingFields = Sets.newIdentityHashSet();
for (int i = 0; i < fields.size(); i++) {
- DexEncodedField encodedField = fields.get(i);
- DexField field = encodedField.field;
- DexField newField = fixupFieldReference(field);
+ DexEncodedField oldField = fields.get(i);
+ DexField oldFieldReference = oldField.getReference();
+ DexField newFieldReference = fixupFieldReference(oldFieldReference);
// Rename the field if it already exists.
- if (!existingFields.add(newField)) {
- DexField template = newField;
- newField =
+ if (!existingFields.add(newFieldReference)) {
+ DexField template = newFieldReference;
+ newFieldReference =
dexItemFactory.createFreshMember(
tryName ->
Optional.of(template.withName(tryName, dexItemFactory))
.filter(tryMethod -> !existingFields.contains(tryMethod)),
- newField.name.toSourceString());
- boolean added = existingFields.add(newField);
+ newFieldReference.name.toSourceString());
+ boolean added = existingFields.add(newFieldReference);
assert added;
}
- if (newField != encodedField.field) {
- movedFields.put(field, newField);
- setter.setField(i, encodedField.toTypeSubstitutedField(newField));
+ if (newFieldReference != oldFieldReference) {
+ lensBuilder.recordNewFieldSignature(oldFieldReference, newFieldReference);
+ setter.setField(i, oldField.toTypeSubstitutedField(newFieldReference));
}
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
index abe232f..d73a7c1 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/InterfaceProcessor.java
@@ -49,8 +49,10 @@
import com.android.tools.r8.origin.SynthesizedOrigin;
import com.android.tools.r8.utils.Pair;
import com.android.tools.r8.utils.collections.BidirectionalManyToManyRepresentativeMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
-import com.google.common.collect.BiMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableList;
import java.util.ArrayDeque;
import java.util.ArrayList;
@@ -521,17 +523,15 @@
public InterfaceProcessorNestedGraphLens(
Map<DexType, DexType> typeMap,
Map<DexMethod, DexMethod> methodMap,
- Map<DexField, DexField> fieldMap,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> extraOriginalMethodSignatures,
+ BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> extraOriginalMethodSignatures,
GraphLens previousLens,
DexItemFactory dexItemFactory) {
super(
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory);
@@ -601,7 +601,7 @@
public static class Builder extends NestedGraphLens.Builder {
- private final BidirectionalOneToOneHashMap<DexMethod, DexMethod>
+ private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod>
extraOriginalMethodSignatures = new BidirectionalOneToOneHashMap<>();
public void recordCodeMovedToCompanionClass(DexMethod from, DexMethod to) {
@@ -613,7 +613,7 @@
@Override
public InterfaceProcessorNestedGraphLens build(
DexItemFactory dexItemFactory, GraphLens previousLens) {
- if (originalFieldSignatures.isEmpty()
+ if (fieldMap.isEmpty()
&& originalMethodSignatures.isEmpty()
&& extraOriginalMethodSignatures.isEmpty()) {
return null;
@@ -622,7 +622,6 @@
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
extraOriginalMethodSignatures,
previousLens,
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
index e4d6f65..fd4eede 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaRewriter.java
@@ -42,10 +42,10 @@
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.utils.DescriptorUtils;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
import com.google.common.base.Suppliers;
-import com.google.common.collect.BiMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
import java.util.ArrayList;
@@ -439,16 +439,14 @@
LambdaRewriterLens(
Map<DexType, DexType> typeMap,
Map<DexMethod, DexMethod> methodMap,
- Map<DexField, DexField> fieldMap,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
GraphLens previousLens,
DexItemFactory dexItemFactory) {
super(
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory);
@@ -479,7 +477,6 @@
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java b/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
index 8889ec2..12418b3 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/NestedPrivateMethodLens.java
@@ -12,7 +12,7 @@
import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
import com.android.tools.r8.graph.RewrittenPrototypeDescription;
import com.android.tools.r8.ir.code.Invoke.Type;
-import com.android.tools.r8.utils.collections.BidirectionalManyToManyRepresentativeMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableMap;
import java.util.IdentityHashMap;
import java.util.Map;
@@ -34,9 +34,8 @@
super(
ImmutableMap.of(),
methodMap,
- ImmutableMap.of(),
- null,
- BidirectionalManyToManyRepresentativeMap.empty(),
+ new EmptyBidirectionalOneToOneMap<>(),
+ new EmptyBidirectionalOneToOneMap<>(),
previousLens,
appView.dexItemFactory());
// No concurrent maps here, we do not want synchronization overhead.
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
index 48002cc..c681eaa 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UninstantiatedTypeOptimization.java
@@ -29,6 +29,9 @@
import com.android.tools.r8.utils.MethodSignatureEquivalence;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.BiMap;
import com.google.common.collect.ImmutableMap;
@@ -54,14 +57,13 @@
private final Map<DexMethod, ArgumentInfoCollection> removedArgumentsInfoPerMethod;
UninstantiatedTypeOptimizationGraphLens(
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMap,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> methodMap,
Map<DexMethod, ArgumentInfoCollection> removedArgumentsInfoPerMethod,
AppView<?> appView) {
super(
ImmutableMap.of(),
- methodMap,
- ImmutableMap.of(),
- null,
+ methodMap.getForwardMap(),
+ new EmptyBidirectionalOneToOneMap<>(),
methodMap.getInverseOneToOneMap(),
appView.graphLens(),
appView.dexItemFactory());
@@ -129,7 +131,7 @@
}
Map<Wrapper<DexMethod>, Set<DexType>> changedVirtualMethods = new HashMap<>();
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping =
+ MutableBidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping =
new BidirectionalOneToOneHashMap<>();
Map<DexMethod, ArgumentInfoCollection> removedArgumentsInfoPerMethod = new IdentityHashMap<>();
@@ -140,7 +142,7 @@
processClass(
clazz,
changedVirtualMethods,
- methodMapping.getForwardBacking(),
+ methodMapping.getForwardMap(),
methodPoolCollection,
removedArgumentsInfoPerMethod));
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
index 16fb558..ec1b904 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/UnusedArgumentsCollector.java
@@ -7,7 +7,6 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.ArgumentUse;
import com.android.tools.r8.graph.DexEncodedMethod;
-import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexProgramClass;
@@ -27,9 +26,10 @@
import com.android.tools.r8.utils.ThreadUtils;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.base.Equivalence.Wrapper;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.ImmutableBiMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Streams;
import java.util.BitSet;
@@ -48,7 +48,7 @@
private final AppView<AppInfoWithLiveness> appView;
private final MethodPoolCollection methodPoolCollection;
- private final BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping =
+ private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping =
new BidirectionalOneToOneHashMap<>();
private final Map<DexMethod, ArgumentInfoCollection> removedArguments = new IdentityHashMap<>();
@@ -57,19 +57,15 @@
private final Map<DexMethod, ArgumentInfoCollection> removedArguments;
UnusedArgumentsGraphLens(
- Map<DexType, DexType> typeMap,
Map<DexMethod, DexMethod> methodMap,
- Map<DexField, DexField> fieldMap,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
GraphLens previousLens,
DexItemFactory dexItemFactory,
Map<DexMethod, ArgumentInfoCollection> removedArguments) {
super(
- typeMap,
+ ImmutableMap.of(),
methodMap,
- fieldMap,
- originalFieldSignatures,
+ new EmptyBidirectionalOneToOneMap<>(),
originalMethodSignatures,
previousLens,
dexItemFactory);
@@ -108,10 +104,7 @@
if (!methodMapping.isEmpty()) {
return new UnusedArgumentsGraphLens(
- ImmutableMap.of(),
- methodMapping,
- ImmutableMap.of(),
- ImmutableBiMap.of(),
+ methodMapping.getForwardMap(),
methodMapping.getInverseOneToOneMap(),
appView.graphLens(),
appView.dexItemFactory(),
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java
index b6660fc..f230dda 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/enums/EnumUnboxingLens.java
@@ -13,8 +13,8 @@
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.utils.BooleanUtils;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.HashBiMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import java.util.IdentityHashMap;
@@ -29,9 +29,8 @@
EnumUnboxingLens(
Map<DexType, DexType> typeMap,
Map<DexMethod, DexMethod> methodMap,
- Map<DexField, DexField> fieldMap,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexField, DexField> fieldMap,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
GraphLens previousLens,
DexItemFactory dexItemFactory,
Map<DexMethod, RewrittenPrototypeDescription> prototypeChangesPerMethod,
@@ -40,7 +39,6 @@
typeMap,
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory);
@@ -76,8 +74,9 @@
static class Builder {
protected final Map<DexType, DexType> typeMap = new IdentityHashMap<>();
- protected final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
- protected final BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures =
+ protected final MutableBidirectionalOneToOneMap<DexField, DexField> newFieldSignatures =
+ new BidirectionalOneToOneHashMap<>();
+ protected final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
new BidirectionalOneToOneHashMap<>();
private Map<DexMethod, RewrittenPrototypeDescription> prototypeChangesPerMethod =
@@ -94,7 +93,7 @@
if (from == to) {
return;
}
- originalFieldSignatures.put(to, from);
+ newFieldSignatures.put(from, to);
}
public void move(DexMethod from, DexMethod to, boolean fromStatic, boolean toStatic) {
@@ -143,16 +142,13 @@
public EnumUnboxingLens build(
DexItemFactory dexItemFactory, GraphLens previousLens, Set<DexType> unboxedEnums) {
- if (typeMap.isEmpty()
- && originalFieldSignatures.isEmpty()
- && originalMethodSignatures.isEmpty()) {
+ if (typeMap.isEmpty() && newFieldSignatures.isEmpty() && originalMethodSignatures.isEmpty()) {
return null;
}
return new EnumUnboxingLens(
typeMap,
- originalMethodSignatures.getInverseOneToOneMap(),
- originalFieldSignatures.inverse(),
- originalFieldSignatures,
+ originalMethodSignatures.getInverseOneToOneMap().getForwardMap(),
+ newFieldSignatures,
originalMethodSignatures,
previousLens,
dexItemFactory,
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerGraphLens.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerGraphLens.java
index fbc4c12..75a78ab 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/ClassStaticizerGraphLens.java
@@ -9,21 +9,19 @@
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
import com.android.tools.r8.ir.code.Invoke.Type;
-import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
-import com.google.common.collect.BiMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
import com.google.common.collect.ImmutableMap;
class ClassStaticizerGraphLens extends NestedGraphLens {
ClassStaticizerGraphLens(
AppView<?> appView,
- BiMap<DexField, DexField> fieldMapping,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping) {
+ BidirectionalOneToOneMap<DexField, DexField> fieldMapping,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping) {
super(
ImmutableMap.of(),
- methodMapping,
+ methodMapping.getForwardMap(),
fieldMapping,
- fieldMapping.inverse(),
methodMapping.getInverseOneToOneMap(),
appView.graphLens(),
appView.dexItemFactory());
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
index 2313a5a..9d84c1f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/staticizer/StaticizingProcessor.java
@@ -47,10 +47,9 @@
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
import com.android.tools.r8.utils.collections.LongLivedProgramMethodSetBuilder;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
import com.android.tools.r8.utils.collections.SortedProgramMethodSet;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.HashBiMap;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
@@ -738,9 +737,10 @@
}
private ProgramMethodSet staticizeMethodSymbols() {
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping =
+ MutableBidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping =
new BidirectionalOneToOneHashMap<>();
- BiMap<DexField, DexField> fieldMapping = HashBiMap.create();
+ MutableBidirectionalOneToOneMap<DexField, DexField> fieldMapping =
+ new BidirectionalOneToOneHashMap<>();
ProgramMethodSet staticizedMethods = ProgramMethodSet.create();
for (CandidateInfo candidate : classStaticizer.candidates.values()) {
@@ -803,8 +803,8 @@
DexProgramClass candidateClass,
DexType hostType,
DexProgramClass hostClass,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping,
- BiMap<DexField, DexField> fieldMapping) {
+ MutableBidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping,
+ MutableBidirectionalOneToOneMap<DexField, DexField> fieldMapping) {
candidateToHostMapping.put(candidateClass.type, hostType);
// Process static fields.
diff --git a/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java b/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
index bd8db04..586e257 100644
--- a/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
@@ -10,23 +10,23 @@
import com.android.tools.r8.graph.GraphLens;
import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
import com.android.tools.r8.ir.code.Invoke.Type;
-import com.android.tools.r8.utils.collections.BidirectionalManyToManyRepresentativeMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeHashMap;
+import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
import java.util.Set;
final class PublicizerLens extends NestedGraphLens {
- private final AppView appView;
+ private final AppView<?> appView;
private final Set<DexMethod> publicizedMethods;
- private PublicizerLens(AppView appView, Set<DexMethod> publicizedMethods) {
+ private PublicizerLens(AppView<?> appView, Set<DexMethod> publicizedMethods) {
super(
ImmutableMap.of(),
ImmutableMap.of(),
- ImmutableMap.of(),
- null,
- BidirectionalManyToManyRepresentativeMap.empty(),
+ new BidirectionalManyToOneRepresentativeHashMap<>(),
+ new EmptyBidirectionalOneToOneMap<>(),
appView.graphLens(),
appView.dexItemFactory());
this.appView = appView;
diff --git a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoistingResult.java b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoistingResult.java
index 09a9b27..9353111 100644
--- a/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoistingResult.java
+++ b/src/main/java/com/android/tools/r8/optimize/bridgehoisting/BridgeHoistingResult.java
@@ -11,7 +11,8 @@
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.optimize.info.bridge.BridgeInfo;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import java.util.Set;
import java.util.function.BiConsumer;
@@ -20,8 +21,8 @@
private final AppView<AppInfoWithLiveness> appView;
// Mapping from non-hoisted bridge methods to hoisted bridge methods.
- private final BidirectionalManyToOneMap<DexMethod, DexMethod> bridgeToHoistedBridgeMap =
- new BidirectionalManyToOneMap<>();
+ private final MutableBidirectionalManyToOneMap<DexMethod, DexMethod> bridgeToHoistedBridgeMap =
+ new BidirectionalManyToOneHashMap<>();
// Mapping from non-hoisted bridge methods to the set of contexts in which they are accessed.
private final MethodAccessInfoCollection.IdentityBuilder bridgeMethodAccessInfoCollectionBuilder =
@@ -32,7 +33,7 @@
}
public void forEachHoistedBridge(BiConsumer<ProgramMethod, BridgeInfo> consumer) {
- bridgeToHoistedBridgeMap.forEach(
+ bridgeToHoistedBridgeMap.forEachManyToOneMapping(
(bridges, hoistedBridge) -> {
DexProgramClass clazz = appView.definitionForProgramType(hoistedBridge.getHolderType());
ProgramMethod method = hoistedBridge.lookupOnProgramClass(clazz);
diff --git a/src/main/java/com/android/tools/r8/repackaging/RepackagingLens.java b/src/main/java/com/android/tools/r8/repackaging/RepackagingLens.java
index b871193..0fe63b8 100644
--- a/src/main/java/com/android/tools/r8/repackaging/RepackagingLens.java
+++ b/src/main/java/com/android/tools/r8/repackaging/RepackagingLens.java
@@ -11,6 +11,8 @@
import com.android.tools.r8.graph.GraphLens.NestedGraphLens;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
@@ -20,14 +22,13 @@
private RepackagingLens(
AppView<AppInfoWithLiveness> appView,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexField, DexField> newFieldSignatures,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
BiMap<DexType, DexType> originalTypes) {
super(
originalTypes.inverse(),
- originalMethodSignatures.getInverseBacking(),
- originalFieldSignatures.inverse(),
- originalFieldSignatures,
+ originalMethodSignatures.getInverseOneToOneMap().getForwardMap(),
+ newFieldSignatures,
originalMethodSignatures,
appView.graphLens(),
appView.dexItemFactory());
@@ -48,12 +49,13 @@
public static class Builder {
protected final BiMap<DexType, DexType> originalTypes = HashBiMap.create();
- protected final BiMap<DexField, DexField> originalFieldSignatures = HashBiMap.create();
- protected final BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures =
+ protected final MutableBidirectionalOneToOneMap<DexField, DexField> newFieldSignatures =
+ new BidirectionalOneToOneHashMap<>();
+ protected final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
new BidirectionalOneToOneHashMap<>();
public void recordMove(DexField from, DexField to) {
- originalFieldSignatures.put(to, from);
+ newFieldSignatures.put(from, to);
}
public void recordMove(DexMethod from, DexMethod to) {
@@ -67,7 +69,7 @@
public RepackagingLens build(AppView<AppInfoWithLiveness> appView) {
assert !originalTypes.isEmpty();
return new RepackagingLens(
- appView, originalFieldSignatures, originalMethodSignatures, originalTypes);
+ appView, newFieldSignatures, originalMethodSignatures, originalTypes);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
index 58e85ff..33e64f0 100644
--- a/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/StaticClassMerger.java
@@ -24,10 +24,10 @@
import com.android.tools.r8.utils.SingletonEquivalence;
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.HashBiMap;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Multiset.Entry;
@@ -199,8 +199,9 @@
private final Map<MergeKey, Representative> representatives = new HashMap<>();
- private final BiMap<DexField, DexField> fieldMapping = HashBiMap.create();
- private final BidirectionalOneToOneHashMap<DexMethod, DexMethod> methodMapping =
+ private final MutableBidirectionalOneToOneMap<DexField, DexField> newFieldSignatures =
+ new BidirectionalOneToOneHashMap<>();
+ private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> methodMapping =
new BidirectionalOneToOneHashMap<>();
private int numberOfMergedClasses = 0;
@@ -222,27 +223,18 @@
public NestedGraphLens run() {
appView.appInfo().classesWithDeterministicOrder().forEach(this::merge);
- if (Log.ENABLED) {
- Log.info(
- getClass(),
- "Merged %s classes with %s members.",
- numberOfMergedClasses,
- fieldMapping.size() + methodMapping.size());
- }
appView.setStaticallyMergedClasses(mergedClassesBuilder.build());
return buildGraphLens();
}
private NestedGraphLens buildGraphLens() {
- if (!fieldMapping.isEmpty() || !methodMapping.isEmpty()) {
- BiMap<DexField, DexField> originalFieldSignatures = fieldMapping.inverse();
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures =
+ if (!newFieldSignatures.isEmpty() || !methodMapping.isEmpty()) {
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
methodMapping.getInverseOneToOneMap();
return new NestedGraphLens(
ImmutableMap.of(),
- methodMapping,
- fieldMapping,
- originalFieldSignatures,
+ methodMapping.getForwardMap(),
+ newFieldSignatures,
originalMethodSignatures,
appView.graphLens(),
appView.dexItemFactory());
@@ -501,7 +493,7 @@
DexMethod originalMethod =
methodMapping.getRepresentativeKeyOrDefault(sourceMethod.method, sourceMethod.method);
- methodMapping.forcePut(originalMethod, sourceMethodAfterMove.method);
+ methodMapping.put(originalMethod, sourceMethodAfterMove.method);
existingMethods.add(equivalence.wrap(sourceMethodAfterMove.method));
}
@@ -536,8 +528,8 @@
result[index++] = sourceFieldAfterMove;
DexField originalField =
- fieldMapping.inverse().getOrDefault(sourceField.field, sourceField.field);
- fieldMapping.forcePut(originalField, sourceFieldAfterMove.field);
+ newFieldSignatures.getRepresentativeKeyOrDefault(sourceField.field, sourceField.field);
+ newFieldSignatures.put(originalField, sourceFieldAfterMove.field);
existingFields.add(equivalence.wrap(sourceFieldAfterMove.field));
}
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
index 434b5d2..e5a4d6b 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMerger.java
@@ -58,7 +58,8 @@
import com.android.tools.r8.utils.OptionalBool;
import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.TraversalContinuation;
-import com.android.tools.r8.utils.collections.BidirectionalManyToOneMap;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneHashMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalManyToOneMap;
import com.google.common.base.Equivalence;
import com.google.common.base.Equivalence.Wrapper;
import com.google.common.collect.Iterables;
@@ -206,8 +207,8 @@
private final Set<DexProgramClass> mergeCandidates = new LinkedHashSet<>();
// Map from source class to target class.
- private final BidirectionalManyToOneMap<DexType, DexType> mergedClasses =
- new BidirectionalManyToOneMap<>();
+ private final MutableBidirectionalManyToOneMap<DexType, DexType> mergedClasses =
+ new BidirectionalManyToOneHashMap<>();
// Set of types that must not be merged into their subtype.
private final Set<DexType> pinnedTypes = Sets.newIdentityHashSet();
diff --git a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
index f634f48..008380c 100644
--- a/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
+++ b/src/main/java/com/android/tools/r8/shaking/VerticalClassMergerGraphLens.java
@@ -17,9 +17,10 @@
import com.android.tools.r8.graph.classmerging.VerticallyMergedClasses;
import com.android.tools.r8.ir.code.Invoke.Type;
import com.android.tools.r8.utils.IterableUtils;
+import com.android.tools.r8.utils.collections.BidirectionalManyToOneRepresentativeMap;
import com.android.tools.r8.utils.collections.BidirectionalOneToOneHashMap;
-import com.google.common.collect.BiMap;
-import com.google.common.collect.HashBiMap;
+import com.android.tools.r8.utils.collections.BidirectionalOneToOneMap;
+import com.android.tools.r8.utils.collections.MutableBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import java.util.Collection;
@@ -69,20 +70,18 @@
private VerticalClassMergerGraphLens(
AppView<?> appView,
VerticallyMergedClasses mergedClasses,
- Map<DexField, DexField> fieldMap,
+ BidirectionalManyToOneRepresentativeMap<DexField, DexField> fieldMap,
Map<DexMethod, DexMethod> methodMap,
Set<DexMethod> mergedMethods,
Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
contextualVirtualToDirectMethodMaps,
- BiMap<DexField, DexField> originalFieldSignatures,
- BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures,
+ BidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures,
Map<DexMethod, DexMethod> originalMethodSignaturesForBridges,
GraphLens previousLens) {
super(
mergedClasses.getForwardMap(),
methodMap,
fieldMap,
- originalFieldSignatures,
originalMethodSignatures,
previousLens,
appView.dexItemFactory());
@@ -166,13 +165,14 @@
private final DexItemFactory dexItemFactory;
- protected final BiMap<DexField, DexField> fieldMap = HashBiMap.create();
+ protected final MutableBidirectionalOneToOneMap<DexField, DexField> fieldMap =
+ new BidirectionalOneToOneHashMap<>();
protected final Map<DexMethod, DexMethod> methodMap = new IdentityHashMap<>();
private final ImmutableSet.Builder<DexMethod> mergedMethodsBuilder = ImmutableSet.builder();
private final Map<DexType, Map<DexMethod, GraphLensLookupResultProvider>>
contextualVirtualToDirectMethodMaps = new IdentityHashMap<>();
- private final BidirectionalOneToOneHashMap<DexMethod, DexMethod> originalMethodSignatures =
+ private final MutableBidirectionalOneToOneMap<DexMethod, DexMethod> originalMethodSignatures =
new BidirectionalOneToOneHashMap<>();
private final Map<DexMethod, DexMethod> originalMethodSignaturesForBridges =
new IdentityHashMap<>();
@@ -185,11 +185,10 @@
static Builder createBuilderForFixup(Builder builder, VerticallyMergedClasses mergedClasses) {
Builder newBuilder = new Builder(builder.dexItemFactory);
- for (Map.Entry<DexField, DexField> entry : builder.fieldMap.entrySet()) {
- newBuilder.map(
- entry.getKey(),
- builder.getFieldSignatureAfterClassMerging(entry.getValue(), mergedClasses));
- }
+ builder.fieldMap.forEach(
+ (key, value) ->
+ newBuilder.map(
+ key, builder.getFieldSignatureAfterClassMerging(value, mergedClasses)));
for (Map.Entry<DexMethod, DexMethod> entry : builder.methodMap.entrySet()) {
newBuilder.map(
entry.getKey(),
@@ -237,7 +236,6 @@
if (mergedClasses.isEmpty()) {
return null;
}
- BiMap<DexField, DexField> originalFieldSignatures = fieldMap.inverse();
// Build new graph lens.
return new VerticalClassMergerGraphLens(
appView,
@@ -246,7 +244,6 @@
methodMap,
mergedMethodsBuilder.build(),
contextualVirtualToDirectMethodMaps,
- originalFieldSignatures,
originalMethodSignatures,
originalMethodSignaturesForBridges,
appView.graphLens());
@@ -308,7 +305,7 @@
}
public boolean hasOriginalSignatureMappingFor(DexField field) {
- return fieldMap.inverse().containsKey(field);
+ return fieldMap.containsValue(field);
}
public boolean hasOriginalSignatureMappingFor(DexMethod method) {
diff --git a/src/main/java/com/android/tools/r8/utils/IterableUtils.java b/src/main/java/com/android/tools/r8/utils/IterableUtils.java
index aee34f6..871a7a5 100644
--- a/src/main/java/com/android/tools/r8/utils/IterableUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/IterableUtils.java
@@ -15,6 +15,10 @@
public class IterableUtils {
+ public static <T> Iterable<T> append(Iterable<T> iterable, T element) {
+ return Iterables.concat(iterable, singleton(element));
+ }
+
public static <T> List<T> ensureUnmodifiableList(Iterable<T> iterable) {
List<T> list;
if (iterable instanceof List<?>) {
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyMap.java
new file mode 100644
index 0000000..09b3c27
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyMap.java
@@ -0,0 +1,27 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+/** Interface that accommodates many-to-many mappings. */
+public interface BidirectionalManyToManyMap<K, V> {
+
+ boolean containsKey(K key);
+
+ boolean containsValue(V value);
+
+ void forEach(BiConsumer<? super K, ? super V> consumer);
+
+ void forEachKey(Consumer<? super K> consumer);
+
+ Set<K> getKeys(V value);
+
+ Set<V> getValues(K key);
+
+ boolean isEmpty();
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyRepresentativeMap.java
index a4878dc..773c066 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyRepresentativeMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToManyRepresentativeMap.java
@@ -4,91 +4,27 @@
package com.android.tools.r8.utils.collections;
-import java.util.Map;
+/**
+ * Interface that accommodates many-to-many mappings.
+ *
+ * <p>This interface additionally adds a "representative" for each one-to-many/many-to-one mapping.
+ * The representative for a given key is a value from {@link #getValues(K)}. The representative for
+ * a given value is a key from {@link #getKeys(V)}.
+ */
+public interface BidirectionalManyToManyRepresentativeMap<K, V>
+ extends BidirectionalManyToManyMap<K, V> {
-public abstract class BidirectionalManyToManyRepresentativeMap<K, V> {
+ K getRepresentativeKey(V value);
- public static <K, V> BidirectionalManyToManyRepresentativeMap<K, V> empty() {
- return new EmptyBidirectionalManyToManyRepresentativeMap<>();
- }
-
- public abstract boolean containsKey(K key);
-
- public abstract boolean containsValue(V value);
-
- public abstract Map<K, V> getForwardBacking();
-
- public abstract Map<V, K> getInverseBacking();
-
- public final Inverse getInverseManyToManyMap() {
- return new Inverse();
- }
-
- public abstract K getRepresentativeKey(V value);
-
- public final K getRepresentativeKeyOrDefault(V value, K defaultValue) {
+ default K getRepresentativeKeyOrDefault(V value, K defaultValue) {
K representativeKey = getRepresentativeKey(value);
return representativeKey != null ? representativeKey : defaultValue;
}
- public abstract V getRepresentativeValue(K key);
+ V getRepresentativeValue(K key);
- public final V getRepresentativeValueOrDefault(K key, V defaultValue) {
+ default V getRepresentativeValueOrDefault(K key, V defaultValue) {
V representativeValue = getRepresentativeValue(key);
return representativeValue != null ? representativeValue : defaultValue;
}
-
- public abstract Iterable<K> getKeys(V value);
-
- public abstract Iterable<V> getValues(K key);
-
- public abstract boolean isEmpty();
-
- public class Inverse extends BidirectionalManyToManyRepresentativeMap<V, K> {
-
- @Override
- public boolean containsKey(V key) {
- return BidirectionalManyToManyRepresentativeMap.this.containsValue(key);
- }
-
- @Override
- public boolean containsValue(K value) {
- return BidirectionalManyToManyRepresentativeMap.this.containsKey(value);
- }
-
- @Override
- public Map<V, K> getForwardBacking() {
- return BidirectionalManyToManyRepresentativeMap.this.getInverseBacking();
- }
-
- @Override
- public Map<K, V> getInverseBacking() {
- return BidirectionalManyToManyRepresentativeMap.this.getForwardBacking();
- }
-
- @Override
- public V getRepresentativeKey(K value) {
- return BidirectionalManyToManyRepresentativeMap.this.getRepresentativeValue(value);
- }
-
- @Override
- public K getRepresentativeValue(V key) {
- return BidirectionalManyToManyRepresentativeMap.this.getRepresentativeKey(key);
- }
-
- @Override
- public Iterable<V> getKeys(K value) {
- return BidirectionalManyToManyRepresentativeMap.this.getValues(value);
- }
-
- @Override
- public Iterable<K> getValues(V key) {
- return BidirectionalManyToManyRepresentativeMap.this.getKeys(key);
- }
-
- @Override
- public boolean isEmpty() {
- return BidirectionalManyToManyRepresentativeMap.this.isEmpty();
- }
- }
}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneHashMap.java
new file mode 100644
index 0000000..6d50046
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneHashMap.java
@@ -0,0 +1,126 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+public class BidirectionalManyToOneHashMap<K, V> implements MutableBidirectionalManyToOneMap<K, V> {
+
+ private final Map<K, V> backing;
+ private final Map<V, Set<K>> inverse;
+
+ public BidirectionalManyToOneHashMap() {
+ this(new IdentityHashMap<>(), new IdentityHashMap<>());
+ }
+
+ private BidirectionalManyToOneHashMap(Map<K, V> backing, Map<V, Set<K>> inverse) {
+ this.backing = backing;
+ this.inverse = inverse;
+ }
+
+ @Override
+ public boolean containsKey(K key) {
+ return backing.containsKey(key);
+ }
+
+ @Override
+ public boolean containsValue(V value) {
+ return inverse.containsKey(value);
+ }
+
+ @Override
+ public void forEach(BiConsumer<? super K, ? super V> consumer) {
+ backing.forEach(consumer);
+ }
+
+ @Override
+ public void forEachKey(Consumer<? super K> consumer) {
+ backing.keySet().forEach(consumer);
+ }
+
+ @Override
+ public void forEachManyToOneMapping(BiConsumer<? super Set<K>, V> consumer) {
+ inverse.forEach((value, keys) -> consumer.accept(keys, value));
+ }
+
+ @Override
+ public V get(Object key) {
+ return backing.get(key);
+ }
+
+ @Override
+ public V getOrDefault(Object key, V value) {
+ return backing.getOrDefault(key, value);
+ }
+
+ @Override
+ public Map<K, V> getForwardMap() {
+ return backing;
+ }
+
+ @Override
+ public Set<K> keySet() {
+ return backing.keySet();
+ }
+
+ @Override
+ public Set<K> getKeys(V value) {
+ return inverse.getOrDefault(value, Collections.emptySet());
+ }
+
+ @Override
+ public Set<V> getValues(K key) {
+ V value = get(key);
+ return value != null ? Collections.singleton(value) : Collections.emptySet();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return backing.isEmpty();
+ }
+
+ @Override
+ public V remove(K key) {
+ V value = backing.remove(key);
+ if (value != null) {
+ Set<K> keys = inverse.get(value);
+ keys.remove(key);
+ if (keys.isEmpty()) {
+ inverse.remove(value);
+ }
+ }
+ return value;
+ }
+
+ @Override
+ public Set<K> removeValue(V value) {
+ Set<K> keys = inverse.remove(value);
+ if (keys == null) {
+ return Collections.emptySet();
+ }
+ for (K key : keys) {
+ V removedValue = backing.remove(key);
+ assert removedValue == value;
+ }
+ return keys;
+ }
+
+ @Override
+ public void put(K key, V value) {
+ remove(key);
+ backing.put(key, value);
+ inverse.computeIfAbsent(value, ignore -> new LinkedHashSet<>()).add(key);
+ }
+
+ public Set<V> values() {
+ return inverse.keySet();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java
index 361b761..3ec2c15 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneMap.java
@@ -4,109 +4,25 @@
package com.android.tools.r8.utils.collections;
-import java.util.Collections;
-import java.util.IdentityHashMap;
-import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;
-public class BidirectionalManyToOneMap<K, V> {
+/**
+ * Interface that accommodates many-to-one mappings.
+ *
+ * <p>This interface inherits from {@link BidirectionalManyToManyMap} to allow implementing
+ * many-to-many mappings using many-to-one mappings.
+ */
+public interface BidirectionalManyToOneMap<K, V> extends BidirectionalManyToManyMap<K, V> {
- private final Map<K, V> backing;
- private final Map<V, Set<K>> inverse;
+ void forEachManyToOneMapping(BiConsumer<? super Set<K>, V> consumer);
- public BidirectionalManyToOneMap() {
- this(new IdentityHashMap<>(), new IdentityHashMap<>());
- }
+ V get(Object key);
- private BidirectionalManyToOneMap(Map<K, V> backing, Map<V, Set<K>> inverse) {
- this.backing = backing;
- this.inverse = inverse;
- }
+ V getOrDefault(Object key, V defaultValue);
- public static <K, V> BidirectionalManyToOneMap<K, V> empty() {
- return new BidirectionalManyToOneMap<>(Collections.emptyMap(), Collections.emptyMap());
- }
+ Map<K, V> getForwardMap();
- public boolean containsKey(K key) {
- return backing.containsKey(key);
- }
-
- public boolean containsValue(V value) {
- return inverse.containsKey(value);
- }
-
- public void forEach(BiConsumer<Set<K>, V> consumer) {
- inverse.forEach((value, keys) -> consumer.accept(keys, value));
- }
-
- public V get(K key) {
- return backing.get(key);
- }
-
- public V getOrDefault(K key, V value) {
- return backing.getOrDefault(key, value);
- }
-
- public Map<K, V> getForwardMap() {
- return backing;
- }
-
- public Set<K> keySet() {
- return backing.keySet();
- }
-
- public boolean hasKey(K key) {
- return backing.containsKey(key);
- }
-
- public boolean hasValue(V value) {
- return inverse.containsKey(value);
- }
-
- public Set<K> getKeys(V value) {
- return inverse.getOrDefault(value, Collections.emptySet());
- }
-
- public Set<K> getKeysOrNull(V value) {
- return inverse.get(value);
- }
-
- public boolean isEmpty() {
- return backing.isEmpty();
- }
-
- public void remove(K key) {
- V value = backing.remove(key);
- if (value != null) {
- Set<K> keys = inverse.get(value);
- keys.remove(key);
- if (keys.isEmpty()) {
- inverse.remove(value);
- }
- }
- }
-
- public Set<K> removeValue(V value) {
- Set<K> keys = inverse.remove(value);
- if (keys == null) {
- return Collections.emptySet();
- }
- for (K key : keys) {
- V removedValue = backing.remove(key);
- assert removedValue == value;
- }
- return keys;
- }
-
- public void put(K key, V value) {
- remove(key);
- backing.put(key, value);
- inverse.computeIfAbsent(value, ignore -> new LinkedHashSet<>()).add(key);
- }
-
- public Set<V> values() {
- return inverse.keySet();
- }
+ Set<K> keySet();
}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
new file mode 100644
index 0000000..8126051
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
@@ -0,0 +1,49 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
+
+public class BidirectionalManyToOneRepresentativeHashMap<K, V>
+ extends BidirectionalManyToOneHashMap<K, V>
+ implements MutableBidirectionalManyToOneRepresentativeMap<K, V> {
+
+ private final Map<V, K> representatives = new IdentityHashMap<>();
+
+ @Override
+ public K removeRepresentativeFor(V value) {
+ return representatives.remove(value);
+ }
+
+ @Override
+ public void setRepresentative(V value, K representative) {
+ representatives.put(value, representative);
+ }
+
+ @Override
+ public K getRepresentativeKey(V value) {
+ Set<K> keys = getKeys(value);
+ if (!keys.isEmpty()) {
+ return keys.size() == 1 ? keys.iterator().next() : representatives.get(value);
+ }
+ return null;
+ }
+
+ @Override
+ public V getRepresentativeValue(K key) {
+ return get(key);
+ }
+
+ @Override
+ public Set<V> getValues(K key) {
+ if (containsKey(key)) {
+ return Collections.singleton(get(key));
+ }
+ return Collections.emptySet();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeMap.java
new file mode 100644
index 0000000..3e7bf7b
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeMap.java
@@ -0,0 +1,14 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+/**
+ * Interface that accommodates many-to-one mappings.
+ *
+ * <p>This interface implicitly adds a "representative" for each many-to-one mapping by inheriting
+ * from {@link BidirectionalManyToManyRepresentativeMap}.
+ */
+public interface BidirectionalManyToOneRepresentativeMap<K, V>
+ extends BidirectionalManyToOneMap<K, V>, BidirectionalManyToManyRepresentativeMap<K, V> {}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneHashMap.java
index d618b52..90217df 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneHashMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneHashMap.java
@@ -4,15 +4,17 @@
package com.android.tools.r8.utils.collections;
-import com.android.tools.r8.utils.IterableUtils;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import java.util.Collection;
+import java.util.Collections;
import java.util.Map;
import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
public class BidirectionalOneToOneHashMap<K, V>
- extends BidirectionalManyToManyRepresentativeMap<K, V> implements Map<K, V> {
+ implements MutableBidirectionalOneToOneMap<K, V>, Map<K, V> {
private final BiMap<K, V> backing;
@@ -44,8 +46,19 @@
return backing.entrySet();
}
- public V forcePut(K key, V value) {
- return backing.forcePut(key, value);
+ @Override
+ public void forEach(BiConsumer<? super K, ? super V> consumer) {
+ backing.forEach(consumer);
+ }
+
+ @Override
+ public void forEachKey(Consumer<? super K> consumer) {
+ backing.keySet().forEach(consumer);
+ }
+
+ @Override
+ public void forEachManyToOneMapping(BiConsumer<? super Set<K>, V> consumer) {
+ backing.forEach((key, value) -> consumer.accept(Collections.singleton(key), value));
}
@Override
@@ -54,15 +67,17 @@
}
@Override
- public BiMap<K, V> getForwardBacking() {
+ public V getOrDefault(Object key, V defaultValue) {
+ V value = get(key);
+ return value != null ? value : defaultValue;
+ }
+
+ @Override
+ public BiMap<K, V> getForwardMap() {
return backing;
}
@Override
- public BiMap<V, K> getInverseBacking() {
- return backing.inverse();
- }
-
public BidirectionalOneToOneHashMap<V, K> getInverseOneToOneMap() {
return new BidirectionalOneToOneHashMap<>(backing.inverse());
}
@@ -78,19 +93,19 @@
}
@Override
- public Iterable<K> getKeys(V value) {
+ public Set<K> getKeys(V value) {
if (containsValue(value)) {
- return IterableUtils.singleton(getRepresentativeKey(value));
+ return Collections.singleton(getRepresentativeKey(value));
}
- return IterableUtils.empty();
+ return Collections.emptySet();
}
@Override
- public Iterable<V> getValues(K key) {
+ public Set<V> getValues(K key) {
if (containsKey(key)) {
- return IterableUtils.singleton(getRepresentativeValue(key));
+ return Collections.singleton(getRepresentativeValue(key));
}
- return IterableUtils.empty();
+ return Collections.emptySet();
}
@Override
@@ -105,11 +120,12 @@
@Override
public V put(K key, V value) {
- return backing.put(key, value);
+ return backing.forcePut(key, value);
}
- public void putAll(BidirectionalOneToOneHashMap<K, V> map) {
- putAll(map.backing);
+ @Override
+ public void putAll(BidirectionalManyToManyMap<K, V> map) {
+ map.forEach(this::put);
}
@Override
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneMap.java
new file mode 100644
index 0000000..e5085c2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToOneMap.java
@@ -0,0 +1,22 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import com.google.common.collect.BiMap;
+
+/**
+ * Interface that accommodates one-to-one mappings.
+ *
+ * <p>This interface inherits from {@link BidirectionalManyToManyRepresentativeMap} to allow
+ * implementing many-to-many mappings using one-to-one mappings.
+ */
+public interface BidirectionalOneToOneMap<K, V>
+ extends BidirectionalManyToOneRepresentativeMap<K, V> {
+
+ @Override
+ BiMap<K, V> getForwardMap();
+
+ BidirectionalOneToOneMap<V, K> getInverseOneToOneMap();
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalManyToManyRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalManyToManyRepresentativeMap.java
deleted file mode 100644
index dbcb753..0000000
--- a/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalManyToManyRepresentativeMap.java
+++ /dev/null
@@ -1,58 +0,0 @@
-// Copyright (c) 2020, 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.utils.collections;
-
-import com.android.tools.r8.utils.IterableUtils;
-import java.util.Collections;
-import java.util.Map;
-
-public class EmptyBidirectionalManyToManyRepresentativeMap<K, V>
- extends BidirectionalManyToManyRepresentativeMap<K, V> {
-
- @Override
- public boolean containsKey(K key) {
- return false;
- }
-
- @Override
- public boolean containsValue(V value) {
- return false;
- }
-
- @Override
- public Map<K, V> getForwardBacking() {
- return Collections.emptyMap();
- }
-
- @Override
- public Map<V, K> getInverseBacking() {
- return Collections.emptyMap();
- }
-
- @Override
- public K getRepresentativeKey(V value) {
- return null;
- }
-
- @Override
- public V getRepresentativeValue(K key) {
- return null;
- }
-
- @Override
- public Iterable<K> getKeys(V value) {
- return IterableUtils.empty();
- }
-
- @Override
- public Iterable<V> getValues(K key) {
- return IterableUtils.empty();
- }
-
- @Override
- public boolean isEmpty() {
- return true;
- }
-}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalOneToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalOneToOneMap.java
new file mode 100644
index 0000000..69a28e6
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/EmptyBidirectionalOneToOneMap.java
@@ -0,0 +1,93 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import com.google.common.collect.BiMap;
+import com.google.common.collect.HashBiMap;
+import java.util.Collections;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+
+public class EmptyBidirectionalOneToOneMap<K, V>
+ implements BidirectionalOneToOneMap<K, V>,
+ BidirectionalManyToOneRepresentativeMap<K, V>,
+ BidirectionalManyToManyRepresentativeMap<K, V> {
+
+ @Override
+ public boolean containsKey(K key) {
+ return false;
+ }
+
+ @Override
+ public boolean containsValue(V value) {
+ return false;
+ }
+
+ @Override
+ public void forEach(BiConsumer<? super K, ? super V> consumer) {
+ // Intentionally empty.
+ }
+
+ @Override
+ public void forEachKey(Consumer<? super K> consumer) {
+ // Intentionally empty.
+ }
+
+ @Override
+ public void forEachManyToOneMapping(BiConsumer<? super Set<K>, V> consumer) {
+ // Intentionally empty.
+ }
+
+ @Override
+ public V get(Object key) {
+ return null;
+ }
+
+ @Override
+ public V getOrDefault(Object key, V defaultValue) {
+ return defaultValue;
+ }
+
+ @Override
+ public BiMap<K, V> getForwardMap() {
+ return HashBiMap.create();
+ }
+
+ @Override
+ public K getRepresentativeKey(V value) {
+ return null;
+ }
+
+ @Override
+ public V getRepresentativeValue(K key) {
+ return null;
+ }
+
+ @Override
+ public Set<K> getKeys(V value) {
+ return Collections.emptySet();
+ }
+
+ @Override
+ public Set<V> getValues(K key) {
+ return Collections.emptySet();
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return true;
+ }
+
+ @Override
+ public Set<K> keySet() {
+ return Collections.emptySet();
+ }
+
+ @Override
+ public BidirectionalOneToOneMap<V, K> getInverseOneToOneMap() {
+ return new EmptyBidirectionalOneToOneMap<>();
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneMap.java
new file mode 100644
index 0000000..3e1a198
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneMap.java
@@ -0,0 +1,22 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+import java.util.Set;
+
+/**
+ * Interface that accommodates many-to-one mappings.
+ *
+ * <p>This interface inherits from {@link BidirectionalManyToManyMap} to allow implementing
+ * many-to-many mappings using many-to-one mappings.
+ */
+public interface MutableBidirectionalManyToOneMap<K, V> extends BidirectionalManyToOneMap<K, V> {
+
+ void put(K key, V value);
+
+ V remove(K key);
+
+ Set<K> removeValue(V value);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
new file mode 100644
index 0000000..defacae
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
@@ -0,0 +1,19 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+/**
+ * Interface that accommodates many-to-one mappings.
+ *
+ * <p>This interface implicitly adds a "representative" for each many-to-one mapping by inheriting
+ * from {@link BidirectionalManyToManyRepresentativeMap}.
+ */
+public interface MutableBidirectionalManyToOneRepresentativeMap<K, V>
+ extends MutableBidirectionalManyToOneMap<K, V>, BidirectionalManyToOneRepresentativeMap<K, V> {
+
+ K removeRepresentativeFor(V value);
+
+ void setRepresentative(V value, K representative);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToOneMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToOneMap.java
new file mode 100644
index 0000000..08ceee8
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToOneMap.java
@@ -0,0 +1,18 @@
+// Copyright (c) 2020, 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.utils.collections;
+
+/**
+ * Interface that accommodates one-to-one mappings.
+ *
+ * <p>This interface inherits from {@link BidirectionalManyToManyRepresentativeMap} to allow
+ * implementing many-to-many mappings using one-to-one mappings.
+ */
+public interface MutableBidirectionalOneToOneMap<K, V> extends BidirectionalOneToOneMap<K, V> {
+
+ V put(K key, V value);
+
+ void putAll(BidirectionalManyToManyMap<K, V> map);
+}
