Unexpected return.type.incompatible: Set<V extends @KeyFor...> vs Set<V> on return map.keySet()

[vlsi]

Here's a part of the class in question

public class DefaultDirectedGraph<V, E extends DefaultEdge>
    implements DirectedGraph<V, E> {
  final Set<E> edges = new LinkedHashSet<>();
  final Map<V, VertexInfo<V, E>> vertexMap = new LinkedHashMap<>();
  final @NotOnlyInitialized EdgeFactory<V, E> edgeFactory;

  @Override public Set<V> vertexSet() { // implement DirectedGraph nethod
    return vertexMap.keySet();
  }

checker-framework issues error as follows:

calcite/core/src/main/java/org/apache/calcite/util/graph/DefaultDirectedGraph.java:161: error: [return.type.incompatible] incompatible types in return.
    return vertexMap.keySet();
                           ^
  type of expression: Set<V extends @KeyFor("this.vertexMap") Object>
  method return type: Set<V extends Object>

I think it might be related to #1653, however, the difference here is that Set<V> signature is specified for a public API.

The method itself looks very much java.util.Map<K, V>.keySet() which return Set<V>.

Does that mean the methods like that always have to suppress return.type.incompatible error?

[mernst]

Thanks for the bug report; we appreciate it. I'm sorry you are having trouble.

For future reference, you can help us by giving a complete test case. This one is missing import statements, so we cannot compile it. Your original code must have contained those. The bug report as written forces us to hunt around for DirectedGraph, DefaultEdge, VertexInfo, etc. We can figure all this out, but you can do it faster. We tend to deprioritize unreproducible bug reports like this one, so giving us a reproducible bug report is a way to get help sooner.

As a smaller issue, you can remove irrelevant fields like edges and edgeFactory.

Here is an example of a reproducible test case:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class DefaultDirectedGraph<V, E> implements DirectedGraph<V, E> {
  final Map<V, String> vertexMap = new LinkedHashMap<>();

  @Override
  public Set<V> vertexSet() { // implement DirectedGraph method
    return vertexMap.keySet();
  }
}

interface DirectedGraph<V, E> {
  Set<V> vertexSet();
}

Another essential part of a bug report is to explain why you think an error or warning is a false positive. Otherwise we have to guess at your intention or your confusion.

In general, the reported error indicates a potential bug, because Set<V extends Object> and Set<V extends @KeyFor("this.vertexMap") Object> are not related by subtyping. If your question is, "Why are those types not related by subtyping?", then consider this code:

Map<String, Integer> m = ...;
Set<@KeyFor("m") String> set1 = new HashSet<>(m.keySet());
Set<String> set2 = set1;  // illegal
set2.add(someRandomValue);

The type of set1 says it contains keys for m, but the last line violates this requirement.

Does that mean the methods like that always have to suppress return.type.incompatible error?

If you suppress warnings, there is the possibility of errors in your code, as shown above.

Could you clarify "methods like that"? I am not sure what you have in mind.

In the code snippet above, there is no possible error because of the unusual contract of keySet() that its return value does not support add. That could be a justification for suppressing a warning, but I don't know whether your full code contains other constructs where errors are possible

[vlsi]

Here's a related example.

Suppose there's a composite map that associates the same value for all the input keys:

package org;

import java.util.AbstractMap;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class CompositeMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
  private final List<K> keys;
  private final V value;

  public CompositeMap(V value, List<K> keys) {
    this.value = value;
    this.keys = keys;
  }

  @Override
  public Set<Entry<K, V>> entrySet() {
    Map<K, V> result = new HashMap<>();
    for (K key : keys) {
      result.put(key, value);
    }
    return result.entrySet();
  }

  public static void main(String[] args) {
    System.out.println("set = " +
        new CompositeMap<>(42, Arrays.asList("hello", "world")).entrySet()
    );
  }
}

Apparently that does not quite work because the method must return Set<Entry<K extends @KeyFor("this") Object, V extends Object>>

Ok, let me try to add types:

package org;

import org.checkerframework.checker.nullness.qual.KeyFor;

import java.util.AbstractMap;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class CompositeMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
  private final List<@KeyFor("this") K> keys;
  private final V value;

  public CompositeMap(V value, List<@KeyFor("this") K> keys) {
    this.value = value;
    this.keys = keys;
  }

  @Override
  public Set<Entry<@KeyFor("this") K, V>> entrySet() {
    Map<@KeyFor("this") K, V> result = new HashMap<>();
    for (@KeyFor("this") K key : keys) {
      result.put(key, value);
    }
    return result.entrySet();
  }

  public static void main(String[] args) {
    System.out.println("set = " +
        new CompositeMap<>(42, Arrays.asList("hello", "world")).entrySet()
    );
  }
}

It does not quite work, because, well, result.entrySet(); still returns @KeyFor("result"):

    return result.entrySet();
                          ^
  type of expression: Set<Entry<K extends @KeyFor("result") Object, V extends Object>>
  method return type: Set<Entry<@org.checkerframework.checker.nullness.qual.KeyFor({"this"}) K extends @KeyFor("this") Object, V extends Object>>

and, what is more important, the class does not work from the user perspective:

        new CompositeMap<>(42, Arrays.asList("hello", "world")).entrySet()
                                            ^
  found   : List<String>
  required: List<@KeyFor("this") String>

I read this as "ok user, you must provide only those strings that are the keys of the map" which is very hard (impossible?) to do.

[vlsi]

Map<String, Integer> m = ...;
Set<@KeyFor("m") String> set1 = new HashSet<>(m.keySet());
Set<String> set2 = set1;  // illegal
set2.add(someRandomValue);

Just in case, Map#entrySet() contract explicitly says that the set does not support add and addAll methods:

     * The set
     * supports element removal, which removes the corresponding
     * mapping from the map, via the <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
     * <tt>clear</tt> operations.  It does not support the
     * <tt>add</tt> or <tt>addAll</tt> operations.
     *
     * @return a set view of the mappings contained in this map
     */
    Set<Map.Entry<K, V>> entrySet();

The original code is indeed complicated, however, the intention and the reason I threat the warning as false positive is that entrySet() is built from an underlying collection, and I see no way I could convince checker that all the keys would become the true keys of the top-level data structure.

---

In other words, I think I understand how @KeyFor helps for map.get(..) scenarios, however, I miss samples for non-trivial Map implementation. It looks like the current @KeyFor requires putting it everywhere in the implementation with little to no gain :-/

I might reiterate on this topic a bit later. Calcite has ~5 or so keySet / entrySet methods only, so I suppressed them for now.