Framework Bug: KeyedCollection<T>

[Chris Mullins [MVP]]

KeyedCollection is a very handy little class, that unforutnatly has a nasty
bug in it.

The bug (which I ran across) causes the following code to fail:

if (!rooms.Contains(room))
_rooms.Add(room);

The problem is that contains returns "false", but then Add throws an
exception because the item really is already in there.

The follow code illustrates the bug in the class:

static void Main(string[] args)
{
KeyTest foo = new KeyTest();
KeyedClass item1 = new KeyedClass("1", "99");
KeyedClass item2 = new KeyedClass("1", "99");
KeyedClass item3 = new KeyedClass("1", "100");

foo.Add(item1);

// this one fails
if (!foo.Contains(item2))
Console.WriteLine("Broken Based on Instancing!");

// this one fails
if (!foo.Contains(item3))
Console.WriteLine("Broken Based on Key Lookup!");

// this one works
if (!foo.Contains(item2.Key))
Console.WriteLine("Even Contains by Key Type is Broken");
}

class KeyTest : KeyedCollection<string, KeyedClass>
{
protected override string GetKeyForItem(KeyedClass item)
{
return item.Key;
}
}

class KeyedClass
{
public readonly string Key, Value;
public KeyedClass(string k, string v)
{
Key = k; Value = v;
}
}

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

[Chris Mullins [MVP]]

I should add that there's a straightforward workaround. Changing the
concrete KeyedCollection class to override the base Contains method works
pretty well. Unfortunatly, very few people are going to think to do this
every time they create a keyed collection class...

class KeyTest : KeyedCollection<string, KeyedClass>
{
protected override string GetKeyForItem(KeyedClass item)
{
return item.Key;
}

public new bool Contains(KeyedClass item)
{
return this.Contains(item.Key);
}
}

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

"Chris Mullins [MVP]" <cm******@yahoo.comwrote in message
news:u6**************@TK2MSFTNGP02.phx.gbl...

KeyedCollection is a very handy little class, that unforutnatly has a
nasty bug in it.

The bug (which I ran across) causes the following code to fail:

if (!rooms.Contains(room))
_rooms.Add(room);

The problem is that contains returns "false", but then Add throws an
exception because the item really is already in there.

The follow code illustrates the bug in the class:

static void Main(string[] args)
{
KeyTest foo = new KeyTest();
KeyedClass item1 = new KeyedClass("1", "99");
KeyedClass item2 = new KeyedClass("1", "99");
KeyedClass item3 = new KeyedClass("1", "100");

foo.Add(item1);

// this one fails
if (!foo.Contains(item2))
Console.WriteLine("Broken Based on Instancing!");

// this one fails
if (!foo.Contains(item3))
Console.WriteLine("Broken Based on Key Lookup!");

// this one works
if (!foo.Contains(item2.Key))
Console.WriteLine("Even Contains by Key Type is Broken");
}

class KeyTest : KeyedCollection<string, KeyedClass>
{
protected override string GetKeyForItem(KeyedClass item)
{
return item.Key;
}
}

class KeyedClass
{
public readonly string Key, Value;
public KeyedClass(string k, string v)
{
Key = k; Value = v;
}
}

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

[Jon Skeet [C# MVP]]

Chris Mullins [MVP] <cm******@yahoo.comwrote:

KeyedCollection is a very handy little class, that unforutnatly has a nasty
bug in it.

Hmm... I'm not sure.

The bug (which I ran across) causes the following code to fail:

if (!rooms.Contains(room))
_rooms.Add(room);

The problem is that contains returns "false", but then Add throws an
exception because the item really is already in there.

Indeed.

The Contains method is meant to check whether the given *key* is in the
collection. The docs say that GetKeyForItem is used to look up the key
for each element, but there's nothing that state it's used to get the
key for the argument you pass into Contains - that's meant to already
be a key. In your case, it isn't a key, it's an item.

On the other hand, I'm surprised this compiles, given that the type you
pass to Contains is meant to be of type TKey, and in your sample code
you're passing in an instance of TItem.

Hmm. Will look closer when I have more time.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Mattias Sjögren]

Chris,

>KeyedCollection is a very handy little class, that unforutnatly has a nasty
bug in it.

I don't think it's a bug. You have to override Equals in the
KeyedClass or provide a custom IEqualityComparer to the
KeyedCollection for Contains to work as expected.

Note that the first two calls to Contains end up calling
Collection<T>.Contains in the base class, which "determines whether an
element is in the Collection" (i.e. requires equality comparison). The
last call on the other hand is to KeyedCollection<TKey,
TItem>.Contains which "determines whether the collection contains an
element with the specified key".
Mattias

--
Mattias Sjögren [C# MVP] mattias @ mvps.org
http://www.msjogren.net/dotnet/ | http://www.dotnetinterop.com
Please reply only to the newsgroup.

[Chris Mullins [MVP]]

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP************************@msnews.microsoft.c om...

On the other hand, I'm surprised this compiles, given that the type you
pass to Contains is meant to be of type TKey, and in your sample code
you're passing in an instance of TItem.

That's acutally the underlying problem - The Contains<TItemis a public
method provided by the base Collection<Tclass. The Contains<TKeymethod
is provided by the KeyedCollection class.

This means there are two overloads in my sample:
Contains(string key)
Contains(KeyedClass item)

If I call the Contains(string) method, everything is fine - the keyed
collection does it's thing and it works properly. If I called the
Contains(KeyedClass) method, then the Collection<Tclass is called
(bypassing all the checked in the KeyedCollection class) and ends up doing a
List.Contains, which is the wrong thing altogether.

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

[Chris Mullins [MVP]]

I'm clear on the behavior as to what's really going on, but once I figured
out it works this way, I found buggy code all over the place.

In many spots, code written by pretty sharp folks was calling
if (items.Containts(Item)) { do something }

.... and it wasn't doing what they thought it would.

Based on "What should this do?", code that looks like (and common variations
on):
if (!rooms.Contains(room))
_rooms.Add(room);

.... really needs to work "right", and not throw an exception.

I realize overriding equals would do the trick here, but for a class called
"KeyedCollection", only the Key should need the equals operator.

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

"Mattias Sjögren" <ma********************@mvps.orgwrote in message
news:uS**************@TK2MSFTNGP03.phx.gbl...

Chris,

>>KeyedCollection is a very handy little class, that unforutnatly has a
nasty
bug in it.

I don't think it's a bug. You have to override Equals in the
KeyedClass or provide a custom IEqualityComparer to the
KeyedCollection for Contains to work as expected.

Note that the first two calls to Contains end up calling
Collection<T>.Contains in the base class, which "determines whether an
element is in the Collection" (i.e. requires equality comparison). The
last call on the other hand is to KeyedCollection<TKey,
TItem>.Contains which "determines whether the collection contains an
element with the specified key".
Mattias

--
Mattias Sjögren [C# MVP] mattias @ mvps.org
http://www.msjogren.net/dotnet/ | http://www.dotnetinterop.com
Please reply only to the newsgroup.

[Jon Skeet [C# MVP]]

Chris Mullins [MVP] <cm******@yahoo.comwrote:

"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP************************@msnews.microsoft.c om...

On the other hand, I'm surprised this compiles, given that the type you
pass to Contains is meant to be of type TKey, and in your sample code
you're passing in an instance of TItem.

That's acutally the underlying problem - The Contains<TItemis a public
method provided by the base Collection<Tclass. The Contains<TKeymethod
is provided by the KeyedCollection class.

Right. Fair enough.

This means there are two overloads in my sample:
Contains(string key)
Contains(KeyedClass item)

If I call the Contains(string) method, everything is fine - the keyed
collection does it's thing and it works properly. If I called the
Contains(KeyedClass) method, then the Collection<Tclass is called
(bypassing all the checked in the KeyedCollection class) and ends up doing a
List.Contains, which is the wrong thing altogether.

And once more, ill-thought-out inheritance strikes :(

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Chris Mullins [MVP]]

I submitted this as a bug to Microsoft, and they have verified it and
accepted it. It's Issue ID 271542, and can be tracked here:
http://connect.microsoft.com/VisualS...dbackID=271542

"We have reproduced this bug on WinXP pro SP2 and VSTS2005 SP1, and we are
sending this bug to the appropriate group within the Visual Studio Product
Team for triage and resolution."

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

"Chris Mullins [MVP]" <cm******@yahoo.comwrote in message
news:u6**************@TK2MSFTNGP02.phx.gbl...

KeyedCollection is a very handy little class, that unforutnatly has a
nasty bug in it.

The bug (which I ran across) causes the following code to fail:

if (!rooms.Contains(room))
_rooms.Add(room);

The problem is that contains returns "false", but then Add throws an
exception because the item really is already in there.

The follow code illustrates the bug in the class:

static void Main(string[] args)
{
KeyTest foo = new KeyTest();
KeyedClass item1 = new KeyedClass("1", "99");
KeyedClass item2 = new KeyedClass("1", "99");
KeyedClass item3 = new KeyedClass("1", "100");

foo.Add(item1);

// this one fails
if (!foo.Contains(item2))
Console.WriteLine("Broken Based on Instancing!");

// this one fails
if (!foo.Contains(item3))
Console.WriteLine("Broken Based on Key Lookup!");

// this one works
if (!foo.Contains(item2.Key))
Console.WriteLine("Even Contains by Key Type is Broken");
}

class KeyTest : KeyedCollection<string, KeyedClass>
{
protected override string GetKeyForItem(KeyedClass item)
{
return item.Key;
}
}

class KeyedClass
{
public readonly string Key, Value;
public KeyedClass(string k, string v)
{
Key = k; Value = v;
}
}

--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins

[MagicBox]

"Jon Skeet [C# MVP]" <sk***@pobox.comschreef in bericht
news:MP************************@msnews.microsoft.c om...

Chris Mullins [MVP] <cm******@yahoo.comwrote:

>"Jon Skeet [C# MVP]" <sk***@pobox.comwrote in message
news:MP************************@msnews.microsoft. com...

On the other hand, I'm surprised this compiles, given that the type you
pass to Contains is meant to be of type TKey, and in your sample code
you're passing in an instance of TItem.

That's acutally the underlying problem - The Contains<TItemis a public
method provided by the base Collection<Tclass. The Contains<TKey>
method
is provided by the KeyedCollection class.

Right. Fair enough.

>This means there are two overloads in my sample:
Contains(string key)
Contains(KeyedClass item)

If I call the Contains(string) method, everything is fine - the keyed
collection does it's thing and it works properly. If I called the
Contains(KeyedClass) method, then the Collection<Tclass is called
(bypassing all the checked in the KeyedCollection class) and ends up
doing a
List.Contains, which is the wrong thing altogether.

And once more, ill-thought-out inheritance strikes :(

Why would that be? Depending on the context of your quest for existance it's
good that both exist.
If you have two collections between which you move items based on user input
or whatever you want to do, you may want to check for existence of the item
reference rather than by key. Although checking for existence by key would
probably faster since the internal dictionairy then would be used. Though if
there are not enough items in the collection to have enabled the internal
dictionary, searching by reference would be faster.

>
--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Jon Skeet [C# MVP]]

<"MagicBox" <avh^at^runbox.com>wrote:

If I call the Contains(string) method, everything is fine - the keyed
collection does it's thing and it works properly. If I called the
Contains(KeyedClass) method, then the Collection<Tclass is called
(bypassing all the checked in the KeyedCollection class) and ends up
doing a
List.Contains, which is the wrong thing altogether.

And once more, ill-thought-out inheritance strikes :(

Why would that be? Depending on the context of your quest for existance it's
good that both exist.

Possibly - but the fact that they're both called the same thing makes
it confusing. Heck, if it can confuse Chris M, it can confuse anyone.

Chris's complaint that:

if (!rooms.Contains(room))
rooms.Add(room);

can break is a perfectly valid one, IMO. The type isn't clear whether
it views the collection as one of keys, or one of values, effectively.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Chris Mullins [MVP]]

"MagicBox" <avh^at^runbox.comwrote:

>And once more, ill-thought-out inheritance strikes :(

Why would that be? Depending on the context of your quest for existance
it's good that both exist.

The problem is that you have two overloads:
..Contains<T>(T)
..Contains(TKey)(TKey)

These two overloads have completly different behaviors. This runs contrary
to all expected behavior of overloaded methods.

In this case, it's simply an oversite by the Framework team. They forgot to
either:

1) Depricate the inherited Contains<Tmethod that coming from List<T>
2) Create their own Contains<Tmethod that calls Contains<TKey>
--
Chris Mullins, MCSD.NET, MCPD:Enterprise, Microsoft C# MVP
http://www.coversant.com/blogs/cmullins