Visitar URL original
Fixed a potential `NullPointerException` in `ImmutableMap.Builder` on… · google/guava@70a9811 · GitHub
Skip to content

Commit 70a9811

Browse files
Jesse SterrGoogle Java Core Libraries
Jesse Sterr
authored and
Google Java Core Libraries
committed
Fixed a potential NullPointerException in ImmutableMap.Builder on a rare code path.
When the `Builder` entries length does not match the `size` and `orderEntriesByValue` is used in combination with `buildKeepingLast` and there are no duplicate keys, then the size used for sorting incorrectly becomes the length of the entries array instead of the size tracked by the `Builder`. This can lead to the `sort` method trying to access null entries from the array. RELNOTES=`collect`: Fixed a potential `NullPointerException` in `ImmutableMap.Builder` on a rare code path. PiperOrigin-RevId: 629407343
1 parent e075e89 commit 70a9811

3 files changed

Lines changed: 33 additions & 3 deletions

File tree

‎android/guava-tests/test/com/google/common/collect/ImmutableMapTest.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -262,6 +262,16 @@ public void testBuilder_orderEntriesByValue_keepingLast() {
262262
}
263263
}
264264

265+
@GwtIncompatible // we haven't implemented this
266+
public void testBuilder_orderEntriesByValueAfterExactSizeBuild_keepingLastWithoutDuplicates() {
267+
ImmutableMap.Builder<String, Integer> builder =
268+
new Builder<String, Integer>(3)
269+
.orderEntriesByValue(Ordering.natural())
270+
.put("three", 3)
271+
.put("one", 1);
272+
assertMapEquals(builder.buildKeepingLast(), "one", 1, "three", 3);
273+
}
274+
265275
@GwtIncompatible // we haven't implemented this
266276
public void testBuilder_orderEntriesByValue_keepingLast_builderSizeFieldPreserved() {
267277
ImmutableMap.Builder<String, Integer> builder =

‎guava-tests/test/com/google/common/collect/ImmutableMapTest.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -289,6 +289,16 @@ public void testBuilder_orderEntriesByValue_keepingLast() {
289289
}
290290
}
291291

292+
@GwtIncompatible // we haven't implemented this
293+
public void testBuilder_orderEntriesByValueAfterExactSizeBuild_keepingLastWithoutDuplicates() {
294+
ImmutableMap.Builder<String, Integer> builder =
295+
new Builder<String, Integer>(3)
296+
.orderEntriesByValue(Ordering.natural())
297+
.put("three", 3)
298+
.put("one", 1);
299+
assertMapEquals(builder.buildKeepingLast(), "one", 1, "three", 3);
300+
}
301+
292302
@GwtIncompatible // we haven't implemented this
293303
public void testBuilder_orderEntriesByValue_keepingLast_builderSizeFieldPreserved() {
294304
ImmutableMap.Builder<String, Integer> builder =

‎guava/src/com/google/common/collect/ImmutableMap.java‎

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -562,8 +562,11 @@ private ImmutableMap<K, V> build(boolean throwIfDuplicateKeys) {
562562
if (!throwIfDuplicateKeys) {
563563
// We want to retain only the last-put value for any given key, before sorting.
564564
// This could be improved, but orderEntriesByValue is rather rarely used anyway.
565-
nonNullEntries = lastEntryForEachKey(nonNullEntries, size);
566-
localSize = nonNullEntries.length;
565+
Entry<K, V>[] lastEntryForEachKey = lastEntryForEachKey(nonNullEntries, size);
566+
if (lastEntryForEachKey != null) {
567+
nonNullEntries = lastEntryForEachKey;
568+
localSize = lastEntryForEachKey.length;
569+
}
567570
}
568571
Arrays.sort(
569572
nonNullEntries,
@@ -640,6 +643,13 @@ ImmutableMap<K, V> buildJdkBacked() {
640643
}
641644
}
642645

646+
/**
647+
* Scans the first {@code size} elements of {@code entries} looking for duplicate keys. If
648+
* duplicates are found, a new correctly-sized array is returned with the same elements (up to
649+
* {@code size}), except containing only the last occurrence of each duplicate key. Otherwise
650+
* {@code null} is returned.
651+
*/
652+
@CheckForNull
643653
private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) {
644654
Set<K> seen = new HashSet<>();
645655
BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key
@@ -649,7 +659,7 @@ private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, i
649659
}
650660
}
651661
if (dups.isEmpty()) {
652-
return entries;
662+
return null;
653663
}
654664
@SuppressWarnings({"rawtypes", "unchecked"})
655665
Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()];

0 commit comments

Comments
 (0)