Confusion about Maps and generics

Question

I just made an odd discovery and was wondering why it works this way. The following code throws a compiler error:

interface A
class B: A
val mapOfA: Map<A,A>
val mapOfB = mapOf<B,B>()
mapOfA = mapOfB

You get

Type mismatch.
   Required: Map<A, A>
   Found: Map<B, B>

But this code works.

val mapOfA: Map<A,A>
val mapOfB = mapOf<B,B>()
mapOfA = mapOfB.toMap()

The only difference is now I'm calling mapOfB.toMap(). mapOfB is already a Map so why does that change anything? I'm using Kotlin version 1.5.10. What's going on here?

Oh darn, forgot to put that detail in. Just updated the question to show that. — J-bob, Oct 19 '21 at 18:30

Louis Wasserman · Answer 1 · 2021-10-19T18:38:48.727

2

Consider mapOfB.get. This accepts a B and only a B.

It is quite possible to have an implementation of mapOfB that cannot support get(A), that has no implementation for it. For example, imagine B is Int, and A is Number. Imagine mapOfB is actually implemented in terms of an array. mapOfA.get(3.14159) certainly can't look up the non-Int key in an array, since arrays are indexed by Ints.

(Kotlin chose this design in contrast to Java's design, which I'm not convinced was the right move -- but it's what they chose. Java's choice was for get, containsKey, and the like to take an Object argument, which results in questions like this.)

This is specifically specified in the definition of Map<K, out V>: upcasting V is allowed, but not K.

edited Oct 19 '21 at 18:38

answered Oct 19 '21 at 18:33

Louis Wasserman

191,574
25
345
413

Correct me if I'm wrong, but although Java allows Object keys as method parameters, the key type is still invariant (and the value type too since there is no declaration-site variance), so you still can't assign a `Map` to a `Map` variable, only a `Map extends A, ? extends A>` variable. But unfortunately, doing the equivalent in Kotlin `Map` renders your map useless for retrieving values. – Tenfour04 Oct 19 '21 at 18:45
That's about mutability, really. The equivalent in Java would be wrapping in [`Collections.unmodifiableMap`](https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#unmodifiableMap(java.util.Map)), which _is_ variant for keys. – Louis Wasserman Oct 19 '21 at 19:12

Tenfour04 · Answer 2 · 2021-10-19T18:59:13.433

The type of a Map's key is invariant. That means a Map<B, B> is not a Map<A, B> or Map<A, A> because you cannot upcast an invariant type. Theoretically, the implementation of the Map interface being used could crash when passing it the wrong type of key, like if you passed it some subtype of A that is not a B.

When you call toMap, it creates a new Map, for which it is known to be safe to use the supertype A as a Key, so it can upcast the type safely. Under the hood, it is transferring each entry to a new map, so it's basically up-casting each of the keys to type A.

Here's an example of what the type safety protects you from:

interface A
class B(val name: String): A
class C: A

class MyMap: HashMap<B, B>() {
    override fun get(key: B): B? {
        println("I'm returning ${key.name}")
        return super.get(key)
    }
}

If you now did this and the compiler let you:

val a = Map<A, A>
val b: Map<B, B> = MyMap()
a = b // imagine this is allowed.
val x = a[C()] // Crash. C cannot be cast to B inside the MyMap.get() function

If you use toMap(), a new Map is being created from scratch and it will not have this problem so it is safe for the compiler to upcast the key type.

Java doesn't have this problem because get and contains, etc. do not take argument types of the key type, but accept anything. There are pros and cons to the two approaches. They each protect you from different types of bugs.

broot · Accepted Answer · 2021-10-19T18:45:11.590

0

This is related to types variance. Consider this example:

val mapOfA: Map<A,A>
val mapOfB = mapOf<B,B>()
mapOfA = mapOfB // assume this is allowed

val item = mapOfA.get(A())

We did something weird here. Both variables point at the same map, so we just asked mapOfB for its A item. But mapOfB does not really know anything about A keys. It was supposed to work with B keys. It requires B in its get(), but we provided A. Therefore, we just broke the type-safety. This is why this is not allowed.

But why toMap() works properly? Because it creates a copy of the map. Now, asking mapOfA for A key asks only this copy, not map of B's. So this is allowed.

edited Oct 19 '21 at 18:45

answered Oct 19 '21 at 18:37

broot

21,588
3
30
35

Interesting. So what are the compile-time mechanics that make this work? As far as I understand, static type analysis doesn't consider if two variables actually reference the same object. It just considers the *declared type* of each object, right? – J-bob Oct 19 '21 at 18:46
Also I'm still confused because if you call `mapOfB.toMap()` it's still a map with `B` objects that `mapOfA` is being set to. So how does this still not create an issue? – J-bob Oct 19 '21 at 18:47
No, this is not handled by tracking references. This is handled by the type system. When you assign `mapOfB` to `mapOfA` you need to cast the map. And depending on the variance it may be allowed or not. For example, `List` can be safely cast to `List`, because any `B` item we got from it is at the same `A`. But we can't cast `MutableList` to `MutableList`, because it would allow to put `A` items into the list of `B` items. In maps parameter `K` is invariant - meaning, that it can't be safely cast to any other type. – broot Oct 19 '21 at 18:55
1

And yes, the copy of the map will still contain only `B` keys. But this is not really related to true contents of a variable, but rather to what you explicitly allowed it to store. When you create `Map` this is like saying: "I forbid anyone to ever use my map with any other key than `B`". When you create a copy of the map, this new map is free of this constraint and you can change its type. Also, imagine you implemented your own `Map` class which can only work with `B` keys. After copying it, the copy (probably `HashMap`) is no longer limited by your implementation and can store `A`'s. – broot Oct 19 '21 at 19:01

Confusion about Maps and generics

3 Answers3