Customer request: Wildcard generics

[matanlurey]

Source: Wildcard (Java).

An internal customer wanted to make sure they had bound generics when creating pairs.

Example

its not var
var map = Map<?, List<?>>()
means a Map
where the value
is a list which contains elements
of the same type as the key

Workaround

See DartPad:

Make sure to enable strong mode.

Map<K, V> pairs<K, V extends List<K>>(Map<K, V> from) => from;

void main() {
  // OK.
  pairs({
    1: [1, 2, 3],
  });
  
  // Error.
  pairs({
    1: ['a', 'b', 'c'],
  });
  
  // Customer would like to be able to define this, i,e,:
  // typedef Pairs = Map<K, List<K>>
}

[matanlurey]

Counter-example where my workaround breaks down:

Map<K, V> pairs<K, V extends List<K>>(Map<K, V> from) => from;

void main() {
  // OK. Customer does not want it to be OK.
  var g = pairs({
    1: [1, 2, 3],
    'd': ['s']
  });
  
  g[44] = <String>['f'];
}

[leafpetersen]

As an aside, I don't think that in Java wildcards Map<?, List<?>> enforces equality between the two ? types does it?

For Dart, would a more generalized typedef solve the problem?

typedef Pairs<K> = Map<K, List<K>>

For your counter-example: Dart generics are covariant, and we allow inference to take advantage of this. That is, we generate subtype constraints rather than equality constraints. On the plus side, this means that we can infer List<num> for [1, 1.0], but the downside is that for things like your example, we can always infer Object. You could, of course, explicitly pass the type to enforce it. For example:

Map<K, List<K>> pairs<K>(Map<K, List<K>> from) => from;

void main() {
  var g = pairs<int>({
    1: [1, 2, 3],
    'd': ['s']  // Error
  });
  
  g[44] = <String>['f'];
}

[zelam]

The desired behavior I was thinking of was:

void main() {
var g = pairs({
1: [1, 2, 3],
'd': ['s'] // Should be good
});

g[44] = ['f']; //should error
}

And thinking further, I'm not sure this is actually doable in Java.

Although wildcards or use-site variance would be nice to have in Dart

[MichaelRFairhurst]

Yeah, this strikes me as an interesting request, but I think you can do it if you're willing to give up map syntax.

The problem is that I'm not sure if this can really be expressed as part of the generic itself, because the K and V for maps would be related in different ways. For some Map you're constraining to String pairs, or Int pairs:

  V get(K k); // V should extend K should extend Object
  void put (K, V); // K should extend V should extend Object
  forEach(void fn(K k, V v)); // K and V should be a supertype of Object

I think you would fundamentally have to control the definition of Map to do this.

Luckily, you can, if you are willing to give up map literals:

  class PairMap<T> {
    void put<P extends K>(P key, P value);
    P get<P extends K>(P key);
    void forEach(void fn(K key, K value));
  }

you can also define a Pair<T> for the construction,

  class Pair<T> {...}
  ...
    PairMap<T>(List<Pair<T>> pairs);

and you can override [] and []=

  P operator[]<P>(P key) => get(key);
  P operator[]=<P>(P key, P value) => put(key, value);

then initialize with

  new PairMap<Object>(new Pair<String>("foo", "bar"));

but unfortunately, not with

  new PairMap{"foo", "bar"};

or anything like that.

And, of course, PairMap<T> can't extend Map<T>, because then you could do (pairMap as Map).add(foo, bar).

Hmm, and thinking about it more, you have an issue where

  map["foo"] = 1;

will not have a type error, because it infers Object for P, and deems it all ok.

[leafpetersen]

I think in @MichaelRFairhurst's code PairMap<T> should be PairMap<K>? But otherwise pretty much what he said. You can basically enforce what you want using classes, but enforcing that directly on Maps... I don't know how to do that. It feels kind of dependent typeish.

First class existentials kind of get you something like what you want. Since Dart 2.0 has first class universals, you can actually define a type that corresponds to:

// Not really Dart
 typedef LinkedPair = Exists<T>.Pair<T, List<T>>

and then use an association list of LinkedPair objects instead of a map, or else use a map from keys to LinkedPair values, with the invariant that the first element of the LinkedPair is the same as the key, but that seems pretty convoluted.

So yeah, I'd say define a class.

[eernstg]

It's true that Java wildcards will not enforce the constraint that this customer wants ('Customer does not want it to be OK').

The point is that it would always be possible to create the relevant pair (for a Map it could be a LinkedHashMapCell<K, V>) with the most general type arguments allowed by the data structure. In the concrete examples those type arguments are inferred and could for instance have been Object, Object based on the context, but they would in any case have to be <S, T> where S is a supertype of int and String, and T is a supertype of List<int> and List<String>, so the "bad" pairing <int, List<String>> would inevitably be acceptable to the enclosing map.

What you are asking for is basically a guarantee that your pair has type arguments which are exactly the run-time types of the key and value in that pair. But we do not have the notion of constraining the run-time type of an object to be equal to a type annotation (that is, 'exact types') rather than having a subtype thereof.

Note that even an existential type is insufficient for that: Exists<K>.LinkedHashMapCell<K, List<K>> would still include LinkedHashMapCell<Object, List<Object>.

It is also true that the two occurrences of ? in a Java-ish wildcard type like Map<?, List<?>> are unrelated. You can introduce a name for an existential type using wildcards, that's known as wildcard capture:

void foo(List<X> xs) { X x; ... }
List<?> myList;
foo(myList);

However, that's not allowed when it gives the same name to multiple ?s, exactly because there is no reason to assume that they would stand for the same type. For a mutable variable it cannot even be assumed that the ? stands for the same type before and after one step of execution that might mutate it.

So wildcards and existentials won't do it without exactness.

Conversely, if you have exactness then you don't need the other two features (I'm just assuming that we write a data structure from scratch here; we can't impose the typing structure on an existing class like Map, e.g., it won't use exact for its key/value pairs):

class ElementToListPair<K> {
  exact K key;
  ExactList<K> value; // A list whose elements are exactly of type K.
}
class ElementToListMap<K> { ... }

For this to work, any method on ElementToListMap that needs to create an ElementToListPair (such as operator []=) would have to receive exactly typed arguments. This again implies that the types would have to be exactly-known statically (which is true for literals), or the arguments would have to be delivered in a coupled manner already:

class HoldPairs<T> {
  ExactSet<T> elements;
  ExactSet<ExactList<T>> lists;
}

We could now use some instances of HoldPairs<T> to populate an ElementToListMap<K>, only knowing that T <: K (and different hold-pairs may have different T, because they admit normal covariance). With each HoldPair<T> we could pick and choose some elements and some lists, and then we could (safely) add them to the given ElementToListMap<K>.

This means that we can maintain the precise relationship between each (element, list) pair in the map, and at the same time we are using normal subtype subsumption (and generic class covariance) to abstract away the precise dependency on which types it is that we are keeping under such tight control. It could be int and List<int> in some cases, String and List<String> in other cases, etc, but it won't ever be int and List<String>.

However, exactness will obviously propagate far away from the location where you wished to have it in the first place, and it quickly gets verbose and inconvenient.

It's even difficult to introduce generically: It may be possible to invent some clever technique such that we can express ExactList<T> as List<exact T>, but since that list must enforce that it never contains an element whose type is a proper subtype of T, it needs to have a different semantics for its add method than a normal list (for instance, we could invoke add dynamically, and even in that case it must enforce that it's argument's runtimeType is equal to the type argument, not just a subtype thereof). Hence, code generated for a normal list would certainly not work as-is for an exact list.

In summary, it wouldn't be impossible to introduce language support for maintaining a discipline of the kind that this customer wants, but it's heavy .. and not likely to happen.

[matanlurey]

This has come up a few times internally, mostly in the context of contravariant function types.

[lukepighetti]

Can this be closed now that we have non-function typedefs?

[eernstg]

Considering the title at first, the topic of wildcard generics is essentially covered by statically checked variance: Declaration-site variance in dart-lang/language#524, and use-site variance in dart-lang/language#753. So in that sense this issue is already a duplicate.

However, as the discussion above shows, Java style wildcarded types cannot be used to satisfy all the requirements that have been mentioned in this issue.

In particular, the interplay between subtyping and type inference implies that var map = {1: [1,2,3], 'a': ['a', 'b', 'c']} can be given the type Map<Object, List<Object>>, and then it won't be an error to do map[44] = ['d'] (and it was requested that this should be an error). As I mentioned, we could use exact types to eliminate subtyping in a controlled fashion, and that would make it possible to achieve a set of definitions such that map[44] = ['d'] is an error. However, that's a radical proposal; for instance, it would have to use a non-standard kind of lists. Also, eliminating subtyping is very anti-OO, because it eliminates the abstraction and implementation independence that we usually get in an OO language because an expression of type T could evaluate to a value of any subtype of T, and if it now must have type exactly T then we've tied ourselves up to a very specific set of implementation choices. So we just won't do that in real life.

The generalized typedef doesn't really make any difference, as far as I can see.

So the situation is that this issue raises all kinds of interesting type system considerations (and in that sense it is not resolved at all), but the topic (according to the title) is already covered pretty well elsewhere, and the discussions haven't produced anything really concrete and useful for Dart right now.

So I'll close the issue.

To anyone who thinks that there is a line of thinking in this issue that needs to be further developed: Please create a new issue on that, in the language repository! ;-)

[lukepighetti]

Appreciate the summary, I better understand the issue now. Thanks.