Bug 80224 - DocumentOrderedMap::containsMultiple can incorrectly return true after an item is removed
Summary: DocumentOrderedMap::containsMultiple can incorrectly return true after an ite...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Darin Adler
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-03-04 12:10 PST by Darin Adler
Modified: 2013-05-16 08:32 PDT (History)
4 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
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.