Reasons for unsafe cast in Maps.asMap.get

[Michael Hixson]

Hello,

I noticed an unsafe cast in Guava's source code and I'm wondering if
the authors have any thoughts to share on it. I think I understand
the reasoning behind it. I'm running into the same issue now in a
different context.

The code is from the implementation behind Maps.asMap(Set, Function):

https://github.com/google/guava/blob/43804c29191423a33e5cf24a36ae7920a64ddad6/guava/src/com/google/common/collect/Maps.java#L795-L804

@Override
public V get(@Nullable Object key) {
if (Collections2.safeContains(backingSet(), key)) {
@SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
K k = (K) key;
return function.apply(k);
} else {
return null;
}
}

That unsafe cast can result in a ClassCastException when the function
is applied. Triggering that behavior doesn't require any unsafe
casts, broken Set.contains(Object), or broken element.equals(Object)
in the calling code. Here's an example:

List<String> elements = ImmutableList.of("a", "b");
Map<LinkedList<String>, String> map = Maps.asMap(
ImmutableSet.of(new LinkedList<>(elements)),
LinkedList::getFirst);
map.get(elements); // ClassCastException

If Guava did not override Map.get(Object) in that code, it would not
trigger that exception. It would inherit the get(Object)
implementation from AbstractMap, which iterates over the entries in
the map looking for one whose key matches the argument. That would
not involve an unsafe cast because the existing key would be provided
to the mapping function instead of the caller-provided key.

However, that would run in linear time. The unsafe, overridden
version is instant.

Is that basically what motivated your decision? That linear
get(Object) would be unacceptable? That the likelihood of users
encountering ClassCastException would be small?

It seems like a Set.get(Object) method would have helped. That
theoretical method would return the existing element in the set that
is equal to the argument. I was looking around for people with
similar issues, but I don't think the proposed solutions help in
Guava's case (or mine):

http://stackoverflow.com/questions/7283338/getting-an-element-from-a-set

http://stackoverflow.com/questions/861296/why-does-the-java-util-setv-interface-not-provide-a-getobject-o-method

For Maps.asMap(Set, Function), wrapping the provided set in a Map<Set,
Set> isn't desirable because the map is supposed to be a live view,
not its own storage. I have the same conflict of interests in my own
code.

Is there a solution here that I'm missing?

Now that we have default methods in the language, do you think a
Set.get(Object) method (by whatever name) would be a good addition to
the JDK? HashSet and RegularImmutableSet look amenable to the change.
Their contains(Object) code essentially has the matching element in
hand before returning true.

Is there a different change in the Java language or libraries that
would solve this problem better?

-Michael

[Louis Wasserman]

On Wed, Jul 15, 2015 at 10:37 PM Michael Hixson <michael...@gmail.com> wrote:

Hello,

I noticed an unsafe cast in Guava's source code and I'm wondering if
the authors have any thoughts to share on it.  I think I understand
the reasoning behind it.  I'm running into the same issue now in a
different context.

Note the docs:

Warning: This method assumes that for any instance k of key type K, k.equals(k2) implies that k2 is also of type K. Using a key type for which this may not hold, such as ArrayList, may risk a ClassCastExceptionwhen calling methods on the resulting map view. 

Is that basically what motivated your decision?  That linear
get(Object) would be unacceptable?  That the likelihood of users
encountering ClassCastException would be small?

Certainly O(n) get implementations are unacceptable, and the Javadoc makes clear the consequences of that issue. 

Now that we have default methods in the language, do you think a
Set.get(Object) method (by whatever name) would be a good addition to
the JDK?  HashSet and RegularImmutableSet look amenable to the change.
Their contains(Object) code essentially has the matching element in
hand before returning true.

I'd be extremely nervous about the fact that any default implementation would have to be O(n); I don't think it'd be worth it.  Map<E, E> does a good enough job when you actually need that behavior.

[Michael Hixson]

Thanks, Louis. It sounds like whether to make the cast wasn't a
difficult choice for you after all. Fair enough.

Over the weekend I looked into what it would take to fully support
Set.get(Object) in the JDK. I think it ends up touching every
concrete Set and Map implementation, and all the keySet() and
entrySet()s, and probably the Map interface as well. It was...
impressive. I agree now: not worth it. :)

-Michael