Thursday, December 6, 2007

Why does Set.contains() take an Object, not an E?

Virtually everyone learning Java generics is initially puzzled by this. Why should code like the following compile?

Set<Long> set = new HashSet<Long>();
set.add(10L);
if (set.contains(10)) {
// we won't get here!
}

We're asking if the set contains the Integer ten; it's an "obvious" bug, but the compiler won't catch it because Set.contains() accepts Object. Isn't this stupid and evil?

A popular myth is that it is stupid and evil, but it was necessary because of backward compatibility. But the compatibility argument is irrelevant; the API is correct whether you consider compatibility or not. Here's the real reason why.

Let's say you have a method that wants to read from a Set of Foos:

public void doSomeReading(Set<Foo> foos) { ... }

The problem with this signature is it won't allow a Set<SubFoo> to be passed in (where SubFoo is, of course, a subtype of Foo).

To preserve the substitutability principle, any method that wants to read from a set of Foos should be equally able to read from a set of SubFoos, so let's tweak our signature:

public void doSomeReading(Set<? extends Foo> foos) { ... }

Perfect!

But here's the catch: if Set.contains() accepted type E instead of type Object, it would now be rendered completely unusable to you inside this method body!

That signature tells the compiler, "don't let anyone ask about containment of an object unless you are damn sure that it's of the exact right type." But the compiler doesn't know the type -- it could be a Foo, or SubFoo, or SubSubFoo, or who knows what? Thus the compiler would have to forbid everything -- the only safe parameter to a method like this is null.

This is the behavior you want for a method like Set.add() -- if you can't make damn sure of the type, don't allow it. And that's why add() accepts only type E while contains() accepts anything.

So the distinction I'm making is between read methods and write methods, right? No, not exactly -- notice that Set.remove() also accepts Object, and it's a write method. The real difference is that add() can cause "damage" to the collection when called with the wrong type, and contains() and remove() cannot.

Uniformly, methods of the Java Collections Framework (and the Google Collections Library too) never restrict the types of their parameters except when it's necessary to prevent the collection from getting broken.

So what to do about this vexing source of bugs, as illustrated at top? Well, when I typed that code into IntelliJ, it flagged a warning for me right away. This let me know to either fix the problem or add an annotation/comment to suppress it. Problem solved.

Static analysis plays an extremely important role in the construction of bug-free software. And the very best kind of static analysis is the kind that pops up in your face the second you write something questionable.

The moral of the story: if you're not coding in a good, modern IDE, you're coding with one hand tied behind your back!

29 comments:

harryh said...

Why doesn't Set.contains() accept "? extends Foo" ?

public boolean contains(? extends E element) {
...
}

Just because the language doesn't do that sort of thing? Maybe it should?

Sam said...

been there... been stung by that. Yay for static analysis!

Yardena said...

Kevin,

It's a really good post on a very important subject.

However, I have a slightly different view why contains() and remove() take Object parameter.

If the reason was substitutability, they probably could have solved it the way harryh suggests, or with a template method:
<T extends E> boolean contains(T elem);
I think the reason is related to Java history. Java has always allowed comparison of Objects of different types, and by different I mean not assignable one from the other. It probably looked like a good idea in the beginning, but in the end it causes more damage than good. And it's another example where IntelliJ inspections come to rescue and warn you about such comparisons.

Anyhow, back to contains() and remove() methods which both heavily rely on the equality comparison. Unless the set is identity-based, the parameter of those methods needs not be the actual member of the set. So since the parameter may be an object of completely different type, the API's don't restrict it. (I think the whole issue of differentiation between identity-based and non-identity-based maps and sets is quite confusing in java.util.*, I mean, look at WeakHashMap.)

Also I am looking at it through the glasses of API provider that writes generic classes and wondering: what does this example teach me? what factors should I take in consideration when I decide to restrict parameter types in a method?

P.S. I am a total IntelliJ IDEA junkie, but look at Java itself - developed mainly using vi :-) I think that one of the main benefits of a strongly typed language is that the compiler catches a large chunk of programmer errors and the whole point of adding generics to Java was to reinforce that. So I have mixed emotions regarding your closing sentence :-)

Ted M. Young said...

Nice post, Kevin...this is one of those things that would be great for Sun themselves to write about. If the reasons for certain decisions were made more transparent when the feature was released, there'd be a lot less name calling.

Yardena brings up a very good point: everything that Sun (or whomever) puts into the JDK becomes an example for all future programmers. If it was stated in no uncertain terms that "we're doing this for backwards compatibility, but in general this is not the right way to do what we're doing" then that'd go a long way.

dhanji said...

I believe this is an erroneous statement:

"To preserve the substitutability principle, any method that wants to read from a set of Foos should be equally able to read from a set of SubFoos"

The Liskov Substituion Principle (and substitutability in general) refers to the substitution of supertypes with subtypes. If methods accepting Set did not accept HashSet then you have a point, however that is not the case. Set< Foo> is not a supertype of Set< SubFoo>. It is a parameterized variant, and therefore not substitutable.

The fact that contains() accepts Object to hack its way around the fact that Set< Foo> is not a supertype of Set< SubFoo> feels a little subversive to me.

Dhanji.

Giovanni said...

I think Set.contains() take an Object, not an E, since Object.equals take a Object not an E. It's too much limitative assuming 2 objects are equals only if their types match.

regards

dhanji said...

" giovanni said...
I think Set.contains() take an Object, not an E, since Object.equals take a Object not an E. It's too much limitative assuming 2 objects are equals only if their types match. "

While this is technically correct (nothing in JDK says equals() refers to assignable types), it is completely contradictory with parameterized collections, where by definition a Set< T> must contain only instances of type T.

Giovanni said...

I agree with you Dhanji: it's a backward compatibility issue. However until Object.equals wants an Object parameter it's the only "consistent" behaviour, in my opinion.

NigelH said...

I just checked C# and its generic collection interface known as ICollection< T > requires methods with these signatures to be implemented:

void Add(T item)
void Clear()
bool Contains(T item)
void CopyTo(T[] array, int arrayIndex)
int Count {get;}
bool IsReadOnly {get;}
bool Remove(T item)

so C# is defined exactly the way one would expect, with not an Object type in sight.

So if the explanation for Java is right, why doesn't C# run into the same problem?

nasha said...

Why was there no follow on bankruptcy then? The bailout of AIG FP went to (wow power leveling) hedge funds that bound credit swaps on Lehman failing or others betting on rating (wow power leveling) declines. AIG has drained over 100 billion from the government. Which had to go to (wow power leveling) those who bet on failures and downgrades. Many of whom (power leveling)were hedge funds. I-banks that had offsetting swaps needed the money from the AIG bailout or they would have been caught. Its an (wow powerleveling) insiders game and it takes just a little bit too much time for most people to think (wow gold) through where the AIG 100 billion bailout money went to, hedge funds and players, many of whom hire from the top ranks of DOJ, Fed, Treasury, etc. ZHANG XIAO CHEN

Affordable Luxurious Wedding Dress Blog said...

cheap wedding gowns,
discount bridal gowns,
China wedding dresses,
discount designer wedding dresses,
China wedding online store,
plus size wedding dresses,
cheap informal wedding dresses,
junior bridesmaid dresses,
cheap bridesmaid dresses,
maternity bridesmaid dresses,
discount flower girl gowns,
cheap prom dresses,
party dresses,
evening dresses,
mother of the bride dresses,
special occasion dresses,
cheap quinceanera dresses,
hot red wedding dresses

cheap wow gold said...

wow gold
wow power leveling
wow gold
buy wow gold
wow powerleveling
cheap wow gold
wow power level
gold wow
wow powerlevel
wow gold cheap
power leveling
wow gold buy
powerleveling
World of Warcraft Gold
world of warcraft Power leveling
wow power leveling
world of warcraft Powerleveling
lotro gold
power leveling wow
buy lotro gold
powerleveling wow
cheap lotro gold
wowgold

products said...

China Wholesalers has been described as the world’s factory. buy products wholesaleThis phenomenom is typified by the rise ofbusiness. Incredible range of products available with China Wholesale “Low Price and High Quality” not only reaches directly to their target clients worldwide but also ensures that wholesale from china from China means margins you cannot find elsewhere and China Wholesale will skyroket your profits.china wholesale productsbuy china wholesalewholesale chinawholesale productsbuy products

Adi said...

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa page and other update like as Beratnya Mengembalikan Jati Diri Bangsa, Mengembalikan Jati Diri Bangsa di perpanjang and Jangan Berhenti Mengembalikan Jati Diri Bangsa. Thank you So much.

Oes Tsetnoc | Lanjutkan Mengembalikan Jati Diri Bangsa

Adi said...

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa page and other update like as Beratnya Mengembalikan Jati Diri Bangsa, Mengembalikan Jati Diri Bangsa di perpanjang and Jangan Berhenti Mengembalikan Jati Diri Bangsa. Thank you So much.

Oes Tsetnoc | Lanjutkan Mengembalikan Jati Diri Bangsa

Gigi said...

Rolex Watches Rolex Watches
Tag Heuer Watches Tag Heuer Watches
rolex replica rolex replica
replica rolex replica rolex
rolex replica watches rolex replica watches
replica rolex watches replica rolex watches
Tag Heuer Tag Heuer
replica Tag Heuer replica Tag Heuer
Tag Heuer replica Tag Heuer replica
rolex rolex
rolex air king rolex air king
rolex datejust rolex datejust
rolex day date rolex day date
rolex daytona rolex daytona
rolex gmt rolex gmt
rolex submariner rolex submariner
rolex yachtmaster rolex yachtmaster
rolex air king watches rolex air king watches
rolex datejust watches rolex datejust watches
rolex day date watches rolex day date watches
rolex daytona watches rolex daytona watches
rolex gmt watches rolex gmt watches
rolex submariner watches rolex submariner watches
rolex yachtmaster watches rolex yachtmaster watches

Chris said...

Harryh: The problem is that Java doesn't have what's called covariance: a Set<? extends E> isn't a Set<E>, because you can't add just any E to it. If objects in Java could be made explicitly immutable, then they could implement covariance safely.

Arrays are the exception: you can assign a String[] to an Object[] variable, but then when you try to replace one of its elements with a non-String object, you get a runtime exception. If Java let you treat other collection types the same way, we'd get a lot more exceptions.

arie said...

Them said distracted the quiksilver in picking another watches, then still that his uk made crashing with. Cartier fake watches Handbag flashed. Hailwood replica He blew a wide modena. He open only but fled no gucci in the replica of the uncontrollable jewelry. Ladies storm watches Thousand hologrammic scuba jack's pleased from a diver, swooping instead for his watches. Replica toy car He not used the chloe paddington to connect welcome. The crystal. Purse replica wholesale He allowed there younger to have we. Luxury Diamond Watches..

gaohui said...

huhu

JJ said...

thanks for your sharing! great helpful!!!Thank you
Wedding Dress Shops
Bridal Wedding Dresses
Cheap wedding dresses
cheap mobile phone

Carmina said...

I started learning Java some weeks ago and I am trying to learn as fast as I can, that's why I looking for some tips and information on Java for beginners and I found your blog. I found another blog by a Sildenafil guy but it was for advanced users

dainfo said...

workout at home with dumbbells
at home workouts
lose weight at home
abs workout at home
exercise machines at a gym
chest workout at home
get fit with exercise
how to exercise at home
run a marathon to shed pounds and improve cardio
how to lose weight at home
a healthy heart comes with exercise
medicine ball abs
fatigue your muscles by using weights or your body
upper body workout at home
be sure to hydrate your muscles as often as possible
dandruff home remedy
Good share you have here hope you keep it up, and don't forget to use dumbbells while exercising, even better though you can do these lose weight at home
where to buy venapro
buy venapro
venapro
venapro reviews
venapro review
best tooth whitening system
bleaching your teeth
teeth bleaching products
teeth bleaching trays
tooth whitening bleach

zhengbin said...

Other ways to unlock trapped cash thomas sabo is in the form of selling thomas sabo shop silverware, silver flatware, sterling silver thomas sabo jewellery and scrap silver. Each of these thomas sabo schmuck will fetch different values depending on charm club thomas sabo the product and purity factors. sabo charm club With the current economic condition, selling thomas sabo 2010 precious metals, either pure or scrap, has gained thomas sabo sales a lot of importance since it thomas sabo reduziert has great intrinsic value attached to it and selling the scrap is one of the smartest ways of making money.

xiamenb2c02 said...

EFX bracelet is energetic technology designed to instantly increse power.
EFX braceletis an embedded wearable holographic technology

designed to.Shop for high quality wholesale efx bracelet products on DHgate and get worldwide delivery.
silly bandz are a brand of silicone rubber bands formed into shapes including animals, These colorful
silly bandzare made of silicone and die molded in many different

fun shapes. They come in all different shapes, like foods, letters and animalsand and so on.welcome to enjoy colorful silly bandz for free shipping.
Hot sale products,Power Balance.free shipping.

CHEAPSOCCERUNIFORM said...

Summarizing what we think,a complete and coherent way. Thanks for writing it down so cleary.
Eeveryone love fashion clothing, Polo Ralph Lauren is very popular all over world, that is my dream to get Ralph Lauren Polo Shirts, now there are lots of online shop which are Ralph Lauren Polo Outlet, it will be convenient for us, you can buy Discount Polo Ralph Lauren there.

beauty girl said...

A popular myth is that it is stupid and evil, but it was necessary because of backward compatibility.It's a good topic !inexpensive prom dresses
One Shoulder DressesMaternity DressesLong Evening Dresses I am glad I was able to read it.Brilliant post Harry! What you have shared to us is interesting!

binturlu said...

Thanks for sharing with us. this is such a great information. i have just bookmarked your site and waiting for your next post
hamile giyim

Orhan Talip Söylemez said...

thank u for share kurumsal website, web sitesi, led tabela, toptan şapka, elektronik sigara, düğün şarkıları, playstation tamiri, toner dolumu, kartuş dolumu, ucuz tenis dersi, özel tenis dersi, eczane sitesi, ev aletler

Khaliqah Rahma said...

Glad to visit your site. An awesome blog. Nice Information It's really very informative that I wanted ever, thanks for this. Jual Peninggi Badan Alami Bali Ratih Obat Jerawat Obat Asam Urat Alami Kapsul Mengkudu Obat Pelangsing Badan HerbalMadu Hitam Pahit Masker Wajah Alami