Delegation and generics craziness

[Sideswipe]

So,

I am trying to create a delegate Map that simply throws an exception
if an attempt to insert a duplicate key occurs. That code is simple.
However, the delegate code is not and I am getting compile errors with
regards to my generics. I make no claims to fully understand generics.
So, I present the work I have with the hopes someone can explain to me
why this won't work.

Christian
http://christan.bongiorno.org

public class ExceptionOnDuplicateKeyMap<K, V> implements Map<K,V> {
private final Map<? extends K, ? extends V> delegate;

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = delegate;
}

public void clear() {
delegate.clear();
}

public boolean containsKey(Object key) {
return delegate.containsKey(key);
}

public boolean containsValue(Object value) {
return delegate.containsValue(value);
}


public Set<Entry<K, V>> entrySet() {
return delegate.entrySet(); // error here
}

public V get(Object key) {
return delegate.get(key);
}

public boolean isEmpty() {
return delegate.isEmpty();
}

public Set<K> keySet() {
return delegate.keySet(); // error here
}

public V put(K key, V value) {
if(delegate.containsKey(key))
throw new IllegalArgumentException();
return delegate.put(key,value); // error here
}

public void putAll(Map<? extends K, ? extends V> m) {
for (Entry<? extends K, ? extends V> entry : m.entrySet())
put(entry.getKey(),entry.getValue());
}

public V remove(Object key) {
return delegate.remove(key);
}

public int size() {
return delegate.size();
}

public Collection<V> values() {
return delegate.values(); // error here
}

}

 

[Mark Space]

So,

I am trying to create a delegate Map that simply throws an exception
if an attempt to insert a duplicate key occurs. That code is simple.
However, the delegate code is not and I am getting compile errors with
regards to my generics. I make no claims to fully understand generics. ....
public class ExceptionOnDuplicateKeyMap<K, V> implements Map<K,V> {
private final Map<? extends K, ? extends V> delegate;

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = delegate;
}

Try this, see if it helps. If it does, consider picking up Effective
Java by Joshua Bloch. I also used _Learning Java_ by O'Reilly to puzzle
this out, but the relevant section is so short I'm not sure it's worth it.


class ExceptionOnDuplicateKeyMap<K, V> implements Map<K,V> {
private final Map<K,V> delegate;

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = (Map<K,V>) delegate;
}

 

[Mark Space]

But 'delegate' only takes B keys - 'A's are too general, and you're
trying to by-pass this restriction. The error is alerting you to this.

You may have to do something similar with V too; I haven't checked.

Yes, I think you do.

(You might be able to use <? super K>, but there are probably other
methods which simultaneously impose <? extends K> or even <K>, so
together they force you to use just <K>.)

I think the basic problem is that for a Map, K and V are both an input
and an output. (You can get the keys out as well as put them in.) And
<? extends X> doesn't work as an output. Semantically, it's just wrong.
Of course, <? super X> doesn't work as an input, so you're stuck.

The correct type of the delegate might be Map<?,?>, but I'm not
completely sure about that.

Fundamentally, as long as you can prove that only a certain type can go
into the delegate, it might be ok to use the raw type. But this is kind
of a no-no, so the <?,?> form might actually be the best, and equivalent
to the raw type in this instance.

I'm not 100% sure, but that was my quick, gut-level analysis of the problem.

 

[Tom Anderson]

I think the basic problem is that for a Map, K and V are both an input
and an output. (You can get the keys out as well as put them in.) And
<? extends X> doesn't work as an output. Semantically, it's just wrong.
Of course, <? super X> doesn't work as an input, so you're stuck.

The correct type of the delegate might be Map<?,?>, but I'm not
completely sure about that.

I may be missing something here, but why is it not just Map<K, V>?

tom

 

[Mark Space]

I may be missing something here, but why is it not just Map<K, V>?

tom

Well, I did that up thread, but I did it quickly and then thought about
it afterwards while I was finishing posting.

What the OP actually has is a constructor that says:

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = (Map<K,V>) delegate;
}

So to keep that, I had to cast. But even though the compiler accepted
it, I'm not sure it's correct. For example, if you have a
ExeptionOnDuplicateKeyMap of:

ExceptionOnDuplicateKeyMap<ParentA,ParentB> m //...

you can actually assign some other type with his constructor:

= new ExceptionOnDuplicateKeyMap<ParentA, ParentB>(
new ExceptionOnDuplicateKeyMap<ChildA, ChildB>() );

which doesn't seem kosher to me. (Assume there's a no argument
constructor for the above example to compile. I don't think that
changes anything.) The type of "m" seems like it should be
<ParentA,ParentB> exactly, and not any subclass, because generics don't
inherit. But that's actually what you have, a subclass of ParentA and
ParentB inside "m". So I was wondering if the internal (delegate) type
of Map<?,?> might actually be correct and more type safe. Rather than
what I posted initially.

Generics are weird enough that figuring out the semantics can be hard
for me even if the syntax is correct. They tend to have tricky corners.
I think the type of "m" should be a upper bound, because that what you
actually have, but that's not what the syntax says.

 

[Tom Anderson]

Well, I did that up thread, but I did it quickly and then thought about
it afterwards while I was finishing posting.

What the OP actually has is a constructor that says:

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V> delegate) {
this.delegate = (Map<K,V>) delegate;
}

So to keep that, I had to cast.

Okay, got it.

I think it has to be <K, V>, though. If the delegate map has keys which
are narrower than K (via <? extends K>), then your map lets someone put in
a K, which won't fit in the delegate. If, on the other hand, it has keys
which are wider than K (<? super K>), then if someone does keySet(), you
return a Set<K> which could actually contain things which are not K. Thus,
the key type of the delegate has to be exactly K. The same argument
applies to the values.

This is an example of good old covariance vs contravariance. In this case,
the type parameters are neither, but invariant.

But even though the compiler accepted it, I'm not sure it's correct.
For example, if you have a ExeptionOnDuplicateKeyMap of:

ExceptionOnDuplicateKeyMap<ParentA,ParentB> m //...

you can actually assign some other type with his constructor:

= new ExceptionOnDuplicateKeyMap<ParentA, ParentB>(
new ExceptionOnDuplicateKeyMap<ChildA, ChildB>() );

which doesn't seem kosher to me. (Assume there's a no argument
constructor for the above example to compile. I don't think that
changes anything.) The type of "m" seems like it should be
<ParentA,ParentB> exactly, and not any subclass, because generics don't
inherit. But that's actually what you have, a subclass of ParentA and
ParentB inside "m".

And if someone comes along and does put(k, foo), where k is an instance of
ParentA, but not ChildA? You're hosed.

So I was wondering if the internal (delegate) type of Map<?,?> might
actually be correct and more type safe. Rather than what I posted
initially.

I can't see how <?, ?> is going to solve anything. I guess it would force
you to cast everywhere, which would make all type mismatches immediately
obvious, but it doesn't buy you any static type safety.

Generics are weird enough that figuring out the semantics can be hard
for me even if the syntax is correct. They tend to have tricky corners.

That i certainly agree with!

I think the type of "m" should be a upper bound, because that what you
actually have, but that's not what the syntax says.

It has to be both an upper and a lower bound. That's the key thing (ha
ha).

tom

 

[Daniel Pitts]

Well, I did that up thread, but I did it quickly and then thought about
it afterwards while I was finishing posting.

What the OP actually has is a constructor that says:

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = (Map<K,V>) delegate;
}

And I believe that is a bug waiting to happen! Either the constructor
should accept a Map<K, V>, or you should use:
public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V> map) {
this.delegate = new HashMap<K, V>(map);
}

This gains you two things: One, type safety , two: It more closely
matches the semantics of other Map implementations (The map-accepting
constructor will copy the map, not create a view/shadow).

So to keep that, I had to cast. But even though the compiler accepted
it, I'm not sure it's correct. For example, if you have a

It isn't correct.
[snip]

Generics are weird enough that figuring out the semantics can be hard
for me even if the syntax is correct. They tend to have tricky corners.
I think the type of "m" should be a upper bound, because that what you
actually have, but that's not what the syntax says.

If you have to cast one generic type to another, then you've probably
done something wrong. If you have to cast a raw-type to a generic type
(or visa-versa) then you'd better be dealing with a legacy API or
writing a reflective framework.

 

[Mark Space]

And I believe that is a bug waiting to happen! Either the constructor
should accept a Map<K, V>

I think that the constructor parameter type should almost certainly be
Map<K,V>. I think he's confused about how generics actually work. I
can't figure out what the semantics of accepting a bound on a generic as
a constructor parameter actually mean. I was just trying to see what I
could do with the problem as stated.

That was a clever solution to use the existing Map constructor. I think
maybe too a solution would be to reify the class and keep type
information stored in it, and check them at runtime. At least, the OP's
intent would be clearer that way.

 

[Roedy Green]

public class ExceptionOnDuplicateKeyMap<K, V> implements Map<K,V> {
private final Map<? extends K, ? extends V> delegate;

public ExceptionOnDuplicateKeyMap(Map<? extends K, ? extends V>
delegate) {
this.delegate = delegate;
}

public void clear() {
delegate.clear();
}

public boolean containsKey(Object key) {
return delegate.containsKey(key);
}

public boolean containsValue(Object value) {
return delegate.containsValue(value);
}


public Set<Entry<K, V>> entrySet() {
return delegate.entrySet(); // error here
}

public V get(Object key) {
return delegate.get(key);
}

public boolean isEmpty() {
return delegate.isEmpty();
}

public Set<K> keySet() {
return delegate.keySet(); // error here
}

public V put(K key, V value) {
if(delegate.containsKey(key))
throw new IllegalArgumentException();
return delegate.put(key,value); // error here
}

public void putAll(Map<? extends K, ? extends V> m) {
for (Entry<? extends K, ? extends V> entry : m.entrySet())
put(entry.getKey(),entry.getValue());
}

public V remove(Object key) {
return delegate.remove(key);
}

public int size() {
return delegate.size();
}

public Collection<V> values() {
return delegate.values(); // error here
}

}

your first problem is you are missing your imports:
import java.util.Collection;
import java.util.Map;
import java.util.Set;

After you fix that you are left with:

ExceptionOnDuplicateKeyMap.java:33: incompatible types
found : java.util.Set<java.util.Map.Entry<capture#674 of ? extends
K,capture#787 of ? extends V>>
required: java.util.Set<java.util.Map.Entry<K,V>>
return delegate.entrySet(); // error here
^
ExceptionOnDuplicateKeyMap.java:48: incompatible types
found : java.util.Set<capture#774 of ? extends K>
required: java.util.Set<K>
return delegate.keySet(); // error here
^
ExceptionOnDuplicateKeyMap.java:55: put(capture#371 of ? extends
K,capture#681 of ? extends V) in ja
va.util.Map<capture#371 of ? extends K,capture#681 of ? extends V>
cannot be applied to (K,V)
return delegate.put(key,value); // error here
^
ExceptionOnDuplicateKeyMap.java:76: incompatible types
found : java.util.Collection<capture#972 of ? extends V>
required: java.util.Collection<V>
return delegate.values(); // error here
^
The mismatches are fairly obvious. The problem what do you do to fix
them. Have a look at source code for

/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient
to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}

It is similar to what you want to do.

 

[Daniel Pitts]

Using another Map's constructor totally defeats delegation. He puts
the delegate map into a hashmap. What if the delegate was my own
subclass of map that had it's own behavior? That would be totally lost
as the data would simply be copied into the hashmap

If the delegate needed to be backed by the actual map passed in, then
that would be a different problem to solve altogether, and the
constructor would have to accept a Map<K, V>, as that would be the only
correct type.