Bug 80224

Summary:	DocumentOrderedMap::containsMultiple can incorrectly return true after an item is removed
Product:	WebKit	Reporter:	Darin Adler <darin>
Component:	DOM	Assignee:	Darin Adler <darin>
Status:	RESOLVED FIXED
Severity:	Normal	CC:	ap, dglazkov, rniwa, rolandsteiner
Priority:	P2
Version:	528+ (Nightly build)
Hardware:	Unspecified
OS:	Unspecified

Description Darin Adler 2012-03-04 12:10:21 PST

There are two related design problems in DocumentOrderedMap.

A

There is a bug: DocumentOrderedMap::containsMultiple will return an incorrect result in the following case:

1) There are two elements in the map.
2) The first element is removed.
3) containsMultiple will return true, but it should return false.

This bug can’t be fixed because containsMultiple does not know which key match function to use.

B

If a caller uses the wrong “get” function on the DocumentOrderedMap, then the map will have incorrect contents. The key matching function is implicit in which of the three get functions is called.

It’s not immediately obvious how to solve these problems. One way to fix problem A is to make three different containsMultiple functions for each of the three different key types. One way to fix both problems is to make DocumentOrderedMap be a class template and make the type of key (id, map name, lowercased map name) be a template argument. There might be even better solutions.

Comment 1 Darin Adler 2012-03-04 12:13:50 PST

It looks like these problems date back to when I first created the class and were not introduced when moving it to a separate file.

Comment 2 Darin Adler 2012-03-04 12:14:19 PST

But the fact that the key matching functions are “baked into the class” are part of moving this to a separate file, and those did make problem B worse.

Comment 3 Darin Adler 2012-03-04 12:23:21 PST

A is not really a design problem!

The question can be correctly answered with a different implementation.

Comment 4 Darin Adler 2012-03-04 12:23:36 PST

I am going to repurpose this to just deal with the correctness problem.

Comment 5 Dimitri Glazkov (Google) 2012-03-04 12:24:02 PST

(In reply to comment #4)
> I am going to repurpose this to just deal with the correctness problem.

I love it when you get back into coding.

Comment 6 Darin Adler 2012-03-04 12:24:31 PST

(In reply to comment #5)
> I love it when you get back into coding.

I only wish I had more time for it.

Comment 7 Ryosuke Niwa 2013-05-15 22:01:08 PDT

(In reply to comment #0)
> There are two related design problems in DocumentOrderedMap.
>
> There is a bug: DocumentOrderedMap::containsMultiple will return an incorrect result in the following case:
> 
> 1) There are two elements in the map.
> 2) The first element is removed.
> 3) containsMultiple will return true, but it should return false.

I'm certain http://trac.webkit.org/changeset/149652/trunk/Source/WebCore/dom/DocumentOrderedMap.h addressed this issue.