Introduce a bidirectional one-to-many map for class initializer merging
The bidirectional one-to-many map will be used to represent the original method signatures for horizontally merged class initializers (where many are merged into a single).
This CL also adds a few extra methods for mutation the existing many-to-one collections.
Change-Id: I3f92f6b5f989feeac65979d27d13fb198f08c023
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 586e257..8ea4e1f 100644
--- a/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
+++ b/src/main/java/com/android/tools/r8/optimize/PublicizerLens.java
@@ -10,7 +10,6 @@
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.BidirectionalManyToOneRepresentativeHashMap;
import com.android.tools.r8.utils.collections.EmptyBidirectionalOneToOneMap;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
@@ -25,7 +24,7 @@
super(
ImmutableMap.of(),
ImmutableMap.of(),
- new BidirectionalManyToOneRepresentativeHashMap<>(),
+ new EmptyBidirectionalOneToOneMap<>(),
new EmptyBidirectionalOneToOneMap<>(),
appView.graphLens(),
appView.dexItemFactory());
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
index 599fddd..c217e91 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneHashMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneHashMap.java
@@ -27,6 +27,12 @@
}
@Override
+ public void clear() {
+ backing.clear();
+ inverse.clear();
+ }
+
+ @Override
public boolean containsKey(K key) {
return backing.containsKey(key);
}
@@ -101,6 +107,11 @@
}
@Override
+ public void removeAll(Iterable<K> keys) {
+ keys.forEach(this::remove);
+ }
+
+ @Override
public Set<K> removeValue(V value) {
Set<K> keys = inverse.remove(value);
if (keys == null) {
@@ -121,6 +132,11 @@
}
@Override
+ public void put(Iterable<K> keys, V value) {
+ keys.forEach(key -> put(key, value));
+ }
+
+ @Override
public Set<V> values() {
return inverse.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
index 8126051..15e1bec 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalManyToOneRepresentativeHashMap.java
@@ -16,6 +16,12 @@
private final Map<V, K> representatives = new IdentityHashMap<>();
@Override
+ public void clear() {
+ super.clear();
+ representatives.clear();
+ }
+
+ @Override
public K removeRepresentativeFor(V value) {
return representatives.remove(value);
}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyHashMap.java
new file mode 100644
index 0000000..552a406
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyHashMap.java
@@ -0,0 +1,137 @@
+// 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 BidirectionalOneToManyHashMap<K, V> implements MutableBidirectionalOneToManyMap<K, V> {
+
+ private final Map<K, Set<V>> backing;
+ private final Map<V, K> inverse;
+
+ public BidirectionalOneToManyHashMap() {
+ this(new IdentityHashMap<>(), new IdentityHashMap<>());
+ }
+
+ private BidirectionalOneToManyHashMap(Map<K, Set<V>> backing, Map<V, K> inverse) {
+ this.backing = backing;
+ this.inverse = inverse;
+ }
+
+ @Override
+ public void clear() {
+ backing.clear();
+ inverse.clear();
+ }
+
+ @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((key, values) -> values.forEach(value -> consumer.accept(key, value)));
+ }
+
+ @Override
+ public void forEachKey(Consumer<? super K> consumer) {
+ backing.keySet().forEach(consumer);
+ }
+
+ @Override
+ public void forEachOneToManyMapping(BiConsumer<K, Set<V>> consumer) {
+ backing.forEach(consumer);
+ }
+
+ @Override
+ public Set<V> get(Object key) {
+ return backing.get(key);
+ }
+
+ @Override
+ public Set<V> getOrDefault(Object key, Set<V> value) {
+ return backing.getOrDefault(key, value);
+ }
+
+ @Override
+ public K getKey(V value) {
+ return inverse.get(value);
+ }
+
+ @Override
+ public Set<K> getKeys(V value) {
+ K key = inverse.get(value);
+ return key != null ? Collections.singleton(key) : Collections.emptySet();
+ }
+
+ @Override
+ public Set<V> getValues(K key) {
+ return getOrDefault(key, Collections.emptySet());
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return backing.isEmpty();
+ }
+
+ public Set<K> keySet() {
+ return backing.keySet();
+ }
+
+ @Override
+ public Set<V> remove(K key) {
+ Set<V> values = backing.remove(key);
+ if (values == null) {
+ return Collections.emptySet();
+ }
+ for (V value : values) {
+ K removedKey = inverse.remove(value);
+ assert removedKey == key;
+ }
+ return values;
+ }
+
+ @Override
+ public void removeAll(Iterable<K> keys) {
+ keys.forEach(this::remove);
+ }
+
+ @Override
+ public K removeValue(V value) {
+ K key = inverse.remove(value);
+ if (key != null) {
+ Set<V> values = backing.get(key);
+ values.remove(value);
+ if (values.isEmpty()) {
+ backing.remove(key);
+ }
+ }
+ return key;
+ }
+
+ @Override
+ public void put(K key, V value) {
+ removeValue(value);
+ backing.computeIfAbsent(key, ignore -> new LinkedHashSet<>()).add(value);
+ inverse.put(value, key);
+ }
+
+ @Override
+ public void put(K key, Set<V> values) {
+ values.forEach(value -> put(key, value));
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyMap.java
new file mode 100644
index 0000000..addb1ed
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyMap.java
@@ -0,0 +1,25 @@
+// 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;
+
+/**
+ * Interface that accommodates many-to-many mappings.
+ *
+ * <p>This interface inherits from {@link BidirectionalManyToManyMap} to allow implementing
+ * many-to-many mappings using many-to-one mappings.
+ */
+public interface BidirectionalOneToManyMap<K, V> extends BidirectionalManyToManyMap<K, V> {
+
+ void forEachOneToManyMapping(BiConsumer<K, Set<V>> consumer);
+
+ Set<V> get(Object key);
+
+ Set<V> getOrDefault(Object key, Set<V> defaultValue);
+
+ K getKey(V value);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeHashMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeHashMap.java
new file mode 100644
index 0000000..93562e7
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeHashMap.java
@@ -0,0 +1,71 @@
+// 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.Streams;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Set;
+
+public class BidirectionalOneToManyRepresentativeHashMap<K, V>
+ extends BidirectionalOneToManyHashMap<K, V>
+ implements MutableBidirectionalOneToManyRepresentativeMap<K, V> {
+
+ private final Map<K, V> representatives = new IdentityHashMap<>();
+
+ @Override
+ public void clear() {
+ super.clear();
+ representatives.clear();
+ }
+
+ @Override
+ public K getRepresentativeKey(V value) {
+ return getKey(value);
+ }
+
+ @Override
+ public V getRepresentativeValue(K key) {
+ Set<V> values = getValues(key);
+ if (!values.isEmpty()) {
+ return values.size() == 1 ? values.iterator().next() : representatives.get(key);
+ }
+ return null;
+ }
+
+ @Override
+ public Set<V> remove(K key) {
+ Set<V> values = super.remove(key);
+ removeRepresentativeFor(key);
+ return values;
+ }
+
+ @Override
+ public void removeAll(Iterable<K> keys) {
+ super.removeAll(keys);
+ assert Streams.stream(keys).noneMatch(representatives::containsKey);
+ }
+
+ @Override
+ public V removeRepresentativeFor(K key) {
+ return representatives.remove(key);
+ }
+
+ @Override
+ public K removeValue(V value) {
+ K key = super.removeValue(value);
+ if (getValues(key).size() <= 1 || getRepresentativeValue(key) == value) {
+ removeRepresentativeFor(key);
+ }
+ return key;
+ }
+
+ @Override
+ public void setRepresentative(K key, V representative) {
+ assert getValues(key).size() > 1;
+ assert getValues(key).contains(representative);
+ representatives.put(key, representative);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeMap.java
new file mode 100644
index 0000000..557173c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/BidirectionalOneToManyRepresentativeMap.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 one-to-many mappings.
+ *
+ * <p>This interface implicitly adds a "representative" for each many-to-one mapping by inheriting
+ * from {@link BidirectionalManyToManyRepresentativeMap}.
+ */
+public interface BidirectionalOneToManyRepresentativeMap<K, V>
+ extends BidirectionalOneToManyMap<K, V>, BidirectionalManyToManyRepresentativeMap<K, V> {}
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
index 3e1a198..7953e91 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneMap.java
@@ -6,17 +6,18 @@
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.
- */
+/** Interface that provides mutable access to the implementation of a many-to-one mapping. */
public interface MutableBidirectionalManyToOneMap<K, V> extends BidirectionalManyToOneMap<K, V> {
+ void clear();
+
void put(K key, V value);
+ void put(Iterable<K> key, V value);
+
V remove(K key);
+ void removeAll(Iterable<K> keys);
+
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
index defacae..24f91ac 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalManyToOneRepresentativeMap.java
@@ -4,12 +4,7 @@
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}.
- */
+/** Interface that provides mutable access to the implementation of a many-to-one mapping. */
public interface MutableBidirectionalManyToOneRepresentativeMap<K, V>
extends MutableBidirectionalManyToOneMap<K, V>, BidirectionalManyToOneRepresentativeMap<K, V> {
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyMap.java
new file mode 100644
index 0000000..1b9d464
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyMap.java
@@ -0,0 +1,23 @@
+// 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 provides mutable access to the implementation of a one-to-many mapping. */
+public interface MutableBidirectionalOneToManyMap<K, V> extends BidirectionalOneToManyMap<K, V> {
+
+ void clear();
+
+ Set<V> remove(K key);
+
+ void removeAll(Iterable<K> keys);
+
+ K removeValue(V value);
+
+ void put(K key, V value);
+
+ void put(K key, Set<V> values);
+}
diff --git a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyRepresentativeMap.java b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyRepresentativeMap.java
new file mode 100644
index 0000000..987eb6f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToManyRepresentativeMap.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 provides mutable access to the implementation of a one-to-many mapping. */
+public interface MutableBidirectionalOneToManyRepresentativeMap<K, V>
+ extends MutableBidirectionalOneToManyMap<K, V>, BidirectionalOneToManyRepresentativeMap<K, V> {
+
+ V removeRepresentativeFor(K key);
+
+ void setRepresentative(K key, V 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
index 08ceee8..5e5f469 100644
--- a/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToOneMap.java
+++ b/src/main/java/com/android/tools/r8/utils/collections/MutableBidirectionalOneToOneMap.java
@@ -4,12 +4,7 @@
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.
- */
+/** Interface that provides mutable access to the implementation of a one-to-one mapping. */
public interface MutableBidirectionalOneToOneMap<K, V> extends BidirectionalOneToOneMap<K, V> {
V put(K key, V value);
