Bug 60746 – IndexedDB chooses wrong record on PREV_NO_DUPLICATE index cursor

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Mark Pilgrim (Google)]

Original test: http://mxr.mozilla.org/mozilla2.0/source/dom/indexedDB/test/test_indexes.html?force=1

This is an adapation of part of a test from Mozilla's IndexedDB test suite. It creates an object store with several rows, creates indexes on each key, and iterates through an index cursor from end to start using the PREV_NO_DUPLICATE flag. Of two records that contain the same key in the index, the cursor chooses the wrong one. Or, at least, a different one than Mozilla chooses. Here's the spec text that pertains to PREV_NO_DUPLICATE:

"""
PREV_NO_DUPLICATE of type unsigned short
indicates that this cursor should yield all records, not including duplicates and its direction is monotonically decreasing order of keys. For every key with duplicate values, only the first record is yielded.
"""

It's not clear whether "the first record" means "the first record in decreasing order" or "the first record in increasing order." Mozilla chooses one interpretation and WebKit chooses the other.

Test case attached.

[Mark Pilgrim (Google)]

Created attachment 93388 [details]
test case

[Mark Pilgrim (Google)]

In this test case, Joe and Pat have the same height. In an index cursor on the 'height' key, starting at the end and moving backward with PREV_NO_DUPLICATE, the test expects to find Joe, but WebKit finds Pat instead.

[Mark Pilgrim (Google)]

Created attachment 93785 [details]
Patch

[David Grogan]

Comment on attachment 93785 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=93785&action=review

It would be prudent to ask about this (and your other similar patch) on public-webapps but syncing our behavior with firefox is probably good enough.

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:62
> +        { name: "height", keyPath: "height", options: { } },

This test only uses the height index, right?

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:119
> +            if ('weight' in cursor.value) {

When doesn't it have a weight?

[Hans Wennborg]

Comment on attachment 93785 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=93785&action=review

> Source/WebCore/storage/IDBSQLiteBackingStore.cpp:972
> +        sql += "IndexData.keyString DESC, IndexData.keyDate DESC, IndexData.keyNumber DESC, IndexData.id ASC";

This will be hard to do for the LeveLDB back-end, and that makes me wonder if it's worth matching Mozilla on this if it's not specified how it should work.

Also, for an index cursor that allows duplicates, doesn't this change mean that the order in which a reverse iterator sees the keys is not the reverse of what a forwarding iterator would see? That seems a little bit odd to me at least.

[Mark Pilgrim (Google)]

Suspending this bug until I get an answer from public-webapps.

[Joshua Bell]

Consensus on the list: http://lists.w3.org/Archives/Public/public-webapps/2010OctDec/0599.html

Summary: PREV_NO_DUPLICATE should end up returning the same set of entries as NEXT_NO_DUPLICATE, just in reverse order. So PREV_NO_DUPLICATE should return the lowest (by primary key) of the duplicate entries.

[Alec Flett]

Created attachment 137106 [details]
Patch

[Alec Flett]

jsbell@ - quick review before off to webkit?

[Joshua Bell]

Comment on attachment 137106 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=137106&action=review

> Source/WebCore/ChangeLog:4
> +        https://bugs.webkit.org/show_bug.cgi?id=60746

This also fixes 60763 so mention that in the comment block and/or mark that bug as a duplicate if there's no distinct code/test.

> Source/WebCore/ChangeLog:10
> +        When iterating backwards with PREV_NO_DUPLICATE, keep walking past

These comments should appear before the Test: line(s)

> Source/WebCore/ChangeLog:12
> +        covers the index and non-index (objectStore) case.

Nit: just write "object store and index cases"

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1045
> +    RefPtr<IDBKey> previousDupKey;

Avoid abbreviations.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1058
> +                // We need to turn around because we hit the end of

"turn around" or simply "back up"? This doesn't appear to repeat or change the iteration direction.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1065
> +

Remove at least one of these blank lines

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1069
> +

Remove blank line.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1072
>          if (!m_transaction->get(m_iterator->key(), trash))

This implies that there are rows that should be skipped over during iteration. What happens if one of these is the last seen before the iterator ends (case above and case below) or a non-dupe is seen? Would the if (prevDupKey.get()) { m_iterator->next(); } cases back up to the row that can't be loaded? (In that case, the notion of "turning around" makes more sense as multiple next() calls may be necessary.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1112
> +                // We need to turn around because we hit the boundary

This comment seems to apply to the next if() block

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1120
> +                    //

Remove empty comment.

> LayoutTests/ChangeLog:4
> +        https://bugs.webkit.org/show_bug.cgi?id=60746

If not resolving 60763 as a duplicate, mention in the comment block.

> LayoutTests/ChangeLog:10
> +        * storage/indexeddb/cursor-reverse-bug-expected.txt:

Is there a cursor-reverse-bug.html that is missing from the patch?

> LayoutTests/storage/indexeddb/cursor-prev-no-duplicate-expected.txt:27
> +runTest(store.openCursor(IDBKeyRange.upperBound(7, false), 2)...

The setting up the test (starting the transaction, opening the cursor) and checking the results (cursor.key etc) are separated, which makes this logging not very useful in understanding the test. Either drop this logging or try and move the setup and results closer together (one transaction per test?)

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:20
> +<script>

Should the JS be factored out of this test to match the others?

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:6
> +description("Test IndexedDB keys ordering and readback from cursors.");

Description could be more specific.

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:59
> +    // help us distinguish the queuing of the tests from the execution

Restructure the tests so this isn't necessary, otherwise the logging isn't valuable.

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:63
> +

Too many blank lines.

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:67
> +    // upper bound is well out of range, results always the same,

Prefer debug() statements to script comments, so the intent of the test is captured in the log if it isn't inherently clear.

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:136
> +function makeOpenCursor(obj, upperBound, open, direction)

I think use of these functions make the test harder to read vs. just putting the string inline.

> LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:179
> +        debug("     cursor.key = " + cursor.key);

To make this take less space and improve the readability in the log, I've been using this style:
shouldBe("cursor.key", JSON.stringify(expectation.expectedKey));

> LayoutTests/storage/indexeddb/resources/shared.js:116
> +// take an unspecified number of callback-like objects, wait for each

Capitalize.
Also, I'd refer to these as "request-like" or "promise-like" or "future-like" rather than "callback-like". Probably settle on "request" since this is an IDB-specific utility file (even though the function is generic, it's a good name)

> LayoutTests/storage/indexeddb/resources/shared.js:119
> +// appropriate onerror/onabort immediately.

Will onerror/onabort be called more than once? (Looks like yes.) Do we care? (Probably not.)

> LayoutTests/storage/indexeddb/resources/shared.js:122
> +

Remove blank line.

> LayoutTests/storage/indexeddb/resources/shared.js:137
> +        var event = arguments[i];

I'd name this something other than event - request/future/promise.

> LayoutTests/storage/indexeddb/resources/shared.js:146
> +function waitFor_onsuccess(index, successes, eventResult)

Move this function inside the definition of waitFor() since it won't be called elsewhere.
If that is done, the successes argument can just become the progress var via the closure, and ditto for eventResult.

[Alec Flett]

Created attachment 137161 [details]
Patch

[Alec Flett]

Created attachment 137164 [details]
Patch

[Alec Flett]

jsbell@ - take two. We now do iterate back in the opposite direction (forward) rather than just calling m_iterator->next() once.

[Joshua Bell]

Comment on attachment 137164 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=137164&action=review

The logic looks sound to me now, just nitpicks.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1045
> +    RefPtr<IDBKey> prevDuplicateKey;

Suggest "lastDuplicateKey"

Also, the comment could be tightened up and include some of the rationale from the ChangeLog, e.g. "When iterating with PREV_NO_DUPLICATE the spec requires that the first duplicate (in forwards order) is yielded."

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1125
> +                // prevDuplicateKey == m_currentKey, so keep walking.

This is implied, no comment needed.

> Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp:1131
>  

Can we assert !prevDuplicateKey.get() || (forward && prevDuplicateKey->isEqual(m_currentKey.get())) ? before we return?

[Alec Flett]

*** Bug 60763 has been marked as a duplicate of this bug. ***

[Alec Flett]

Created attachment 137566 [details]
Patch

[Alec Flett]

jsbell@ - ok final issues addressed.

[Joshua Bell]

It looks like these issues still need addressing in the tests:

(In reply to comment #10)

> > LayoutTests/storage/indexeddb/cursor-prev-no-duplicate-expected.txt:27
> > +runTest(store.openCursor(IDBKeyRange.upperBound(7, false), 2)...
> 
> The setting up the test (starting the transaction, opening the cursor) and checking the results (cursor.key etc) are separated, which makes this logging not very useful in understanding the test. Either drop this logging or try and move the setup and results closer together (one transaction per test?)
> 
> > LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:20
> > +<script>
> 
> Should the JS be factored out of this test to match the others?
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:6
> > +description("Test IndexedDB keys ordering and readback from cursors.");
> 
> Description could be more specific.
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:59
> > +    // help us distinguish the queuing of the tests from the execution
> 
> Restructure the tests so this isn't necessary, otherwise the logging isn't valuable.
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:63
> > +
> 
> Too many blank lines.
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:67
> > +    // upper bound is well out of range, results always the same,
> 
> Prefer debug() statements to script comments, so the intent of the test is captured in the log if it isn't inherently clear.
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:136
> > +function makeOpenCursor(obj, upperBound, open, direction)
> 
> I think use of these functions make the test harder to read vs. just putting the string inline.
> 
> > LayoutTests/storage/indexeddb/resources/cursor-prev-no-duplicate.js:179
> > +        debug("     cursor.key = " + cursor.key);
> 
> To make this take less space and improve the readability in the log, I've been using this style:
> shouldBe("cursor.key", JSON.stringify(expectation.expectedKey));
> 
> > LayoutTests/storage/indexeddb/resources/shared.js:116
> > +// take an unspecified number of callback-like objects, wait for each
> 
> Capitalize.
> Also, I'd refer to these as "request-like" or "promise-like" or "future-like" rather than "callback-like". Probably settle on "request" since this is an IDB-specific utility file (even though the function is generic, it's a good name)
> 
> > LayoutTests/storage/indexeddb/resources/shared.js:119
> > +// appropriate onerror/onabort immediately.
> 
> Will onerror/onabort be called more than once? (Looks like yes.) Do we care? (Probably not.)
> 
> > LayoutTests/storage/indexeddb/resources/shared.js:122
> > +
> 
> Remove blank line.
> 
> > LayoutTests/storage/indexeddb/resources/shared.js:137
> > +        var event = arguments[i];
> 
> I'd name this something other than event - request/future/promise.
> 
> > LayoutTests/storage/indexeddb/resources/shared.js:146
> > +function waitFor_onsuccess(index, successes, eventResult)
> 
> Move this function inside the definition of waitFor() since it won't be called elsewhere.
> If that is done, the successes argument can just become the progress var via the closure, and ditto for eventResult.

[Alec Flett]

Created attachment 137609 [details]
Patch

[Alec Flett]

jsbell@ - ok, tests adjusted. I got rid of the waitFor() bit because of the totally async nature which, as you point out, makes the test output kind of hard to follow. I tried to make a generalized in-order mechanism but it got way more complicated, so I gave up. now all the test cases are just chained together.

[Joshua Bell]

Comment on attachment 137609 [details]
Patch

lgtm

[Ojan Vafai]

Comment on attachment 137609 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=137609&action=review

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:10
> +<link rel="stylesheet" href="../../../fast/js/resources/js-test-style.css">

Nit: you don't need this. js-test-pre inserts the stylesheet for you.

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:19
> +<p id="description"></p>
> +<div id="console"></div>

Nit: you don't need these elements. js-test-pre will insert them for you.

> LayoutTests/storage/indexeddb/mozilla/index-prev-no-duplicate.html:118
> +function testPrev() {

Nit: here and blow the style is inconsistent with the above. Curly brace should be on the next line.

[Alec Flett]

Created attachment 137624 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 137624 [details]
Patch for landing

Rejecting attachment 137624 [details] from commit-queue.

[e-mail] does not have committer permissions according to http://trac.webkit.org/browser/trunk/Tools/Scripts/webkitpy/common/config/committers.py.

- If you do not have committer rights please read http://webkit.org/coding/contributing.html for instructions on how to use bugzilla flags.

- If you have committer rights please correct the error in Tools/Scripts/webkitpy/common/config/committers.py by adding yourself to the file (no review needed).  The commit-queue restarts itself every 2 hours.  After restart the commit-queue will correctly respect your committer rights.

[WebKit Review Bot]

Comment on attachment 137624 [details]
Patch for landing

Clearing flags on attachment: 137624

Committed r114464: <http://trac.webkit.org/changeset/114464>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.