Modern IDB: Make in-memory ObjectStore cursors work

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Brady Eidson]

Modern IDB: Make cursors functional

[Brady Eidson]

Rename: Modern IDB:Make in-memory Index cursors work

[Brady Eidson]

Created attachment 265534 [details]
Patch v1

[Darin Adler]

Comment on attachment 265534 [details]
Patch v1

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

Why this use of std::set? Is this the right data structure to use? Is both memory use and speed acceptable?

> Source/WebCore/Modules/indexeddb/client/TransactionOperation.cpp:43
> +    if (const auto* cursor = request.pendingCursor())

The "const" here has no effect. I suggest just "auto*".

> Source/WebCore/Modules/indexeddb/server/IDBBackingStore.h:75
> +    virtual IDBError iterateCursor(const IDBResourceIdentifier& transactionIdentifier, const IDBResourceIdentifier& cursorIdentifier, const IDBKeyData&, unsigned long count, IDBGetResult& outResult) = 0;

Type here should be unsigned, not unsigned long. See comment elsewhere explaining why I think this happened.

> Source/WebCore/Modules/indexeddb/server/MemoryBackingStoreTransaction.cpp:127
> +    m_clearedOrderedKeys.set(&objectStore, WTF::move(orderedKeys));

The add function is slightly more efficient than the set function, and they do the same thing when the map doesn’t already contain an entry for this key. So I suggest use of add here.

> Source/WebCore/Modules/indexeddb/server/MemoryBackingStoreTransaction.cpp:205
> +            std::unique_ptr<std::set<IDBKeyData>> orderedKeys = m_clearedOrderedKeys.take(objectStore);
> +            ASSERT(orderedKeys);
> +            objectStore->replaceKeyValueStore(WTF::move(clearedKeyValueMap), WTF::move(orderedKeys));

I think this reads more nicely with auto rather than writing out the type. But if it was me, I would write:

    ASSERT(m_clearedOrderedKeys.contains(objectStore));
    objectStore->replaceKeyValueStore(WTF::move(clearedKeyValueMap), m_clearedOrderedKeys.take(objectStore));

Or:

    ASSERT(m_clearedOrderedKeys.get(objectStore));
    objectStore->replaceKeyValueStore(WTF::move(clearedKeyValueMap), m_clearedOrderedKeys.take(objectStore));

> Source/WebCore/Modules/indexeddb/server/MemoryCursor.cpp:49
> +    cursorMap().set(m_info.identifier(), this);

Same comment about add vs. set. Should use add here.

> Source/WebCore/Modules/indexeddb/server/MemoryCursor.h:47
> +    virtual void iterate(const IDBKeyData&, unsigned long count, IDBGetResult&) = 0;

The type here should be unsigned, not unsigned long.

I believe there are a lot of things that are typed unsigned long because there are arguments with the type unsigned long in the IDL. But, confusingly, unsigned long in IDL means specifically 32-bit, and we use unsigned (or uint32_t) for that in actual C++ code. I believe this mistake has been made throughout quite a bit of IDB code, and so we are doing 64-bit operations for no good reason; the bindings will accept only 32-bit integers, but we then extend them to 64-bit and keep them as such throughout the C++ code on 64-bit platforms, but not on 32-bit platforms.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:341
> +        return IDBError(IDBExceptionCode::Unknown, WTF::ASCIILiteral("No backing store transaction found in which to open a cursor"));

I’m pretty sure this just needs to be ASCIILiteral, not WTF::ASCIILiteral. Throughout this file.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:343
> +    IDBError resultError;

Probably wouldn’t need this local variable if we instead have all errors exit with return as the case above does.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:344
> +    MemoryCursor* cursor = nullptr;

No reason to define this out here. I suggest defining it where it is set below.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:350
> +            resultError = IDBError(IDBExceptionCode::Unknown, WTF::ASCIILiteral("No backing store object store found"));

I’d like this better as a return.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:356
> +            resultError = IDBError(IDBExceptionCode::Unknown, WTF::ASCIILiteral("Could not create object store cursor in backing store"));

I’d like this better as a return.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:364
> +        resultError = IDBError(IDBExceptionCode::Unknown, WTF::ASCIILiteral("Index cursors not yet supported"));

I’d like this better as a return.

> Source/WebCore/Modules/indexeddb/server/MemoryIDBBackingStore.cpp:370
> +IDBError MemoryIDBBackingStore::iterateCursor(const IDBResourceIdentifier& transactionIdentifier, const IDBResourceIdentifier& cursorIdentifier, const IDBKeyData& key, unsigned long count, IDBGetResult& outData)

Type here should be unsigned, not unsigned long. See comment elsewhere explaining why I think this happened.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStore.cpp:385
> +    auto result = m_cursors.add(info.identifier(), MemoryObjectStoreCursor::create(*this, info));
> +    if (!result.isNewEntry)
> +        return nullptr;
> +
> +    return result.iterator->value.get();

This is inefficient when the cursor already exists. It allocates and destroys a cursor that is never used for anything. It would be more efficient and more conventional to write it like this:

    auto result = m_cursors.add(info.identifier(), nullptr);
    if (!result.isNewEntry)
        return nullptr;

    result.iterator->value = MemoryObjectStoreCursor::create(*this, info);
    return result.iterator->value.get();

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:48
> +    std::set<IDBKeyData>* orderedKeys = objectStore.orderedKeys();

I think this reads better with auto*.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:90
> +    ASSERT(set);

An assertion like this one typically indicates that the function should be a taking a reference rather than a pointer. I suggest making that change here.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:110
> +    ASSERT(set);

An assertion like this one typically indicates that the function should be a taking a reference rather than a pointer. I suggest making that change here.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:123
> +    if (m_remainingRange.lowerOpen && *lowest == m_remainingRange.lowerKey)
> +        ++lowest;
> +
> +    if (lowest == set->end())
> +        return lowest;

I suggest nesting the second if statement inside the first.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:138
> +    ASSERT(set);

An assertion like this one typically indicates that the function should be a taking a reference rather than a pointer. I suggest making that change here.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:44
> +    static std::unique_ptr<MemoryObjectStoreCursor> create(MemoryObjectStore&, const IDBCursorInfo&);

In cases like this where create is simply a call to make_unique, I am not sure we need to write a create function. At the call site we should just write:

    auto cursor = std::make_unique<MemoryObjectStoreCursor>(store, info);

Further, I am not sure we need the constructor to be private. Is there harm in allocating one of these that is not on the heap? For reference counted objects there is, and that’s why the create pattern exists for them. But for single ownership objects it’s typically not important to make the constructor private, even if in practice we always allocate them on the heap.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:47
> +    virtual void currentData(IDBGetResult&) override final;
> +    virtual void iterate(const IDBKeyData&, unsigned long count, IDBGetResult&) override final;

Any reason to not have these overrides be private?

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:61
> +    void incrementForwardIterator(const IDBKeyData&, unsigned long count);
> +    void incrementReverseIterator(const IDBKeyData&, unsigned long count);

Type here should be unsigned, not unsigned long. See comment elsewhere explaining why I think this happened.

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:69
> +    std::set<IDBKeyData>::iterator m_forwardIterator;
> +    std::set<IDBKeyData>::reverse_iterator m_reverseIterator;

I’m slightly concerned at the use of long-lived std::set iterators and reverse iterators. Does the std::set implementation we are using on major platforms include checks on iterators like the ones we have in HashMap?

> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:70
> +    bool m_iteratorsUndefined { true };

Another way to do this is to use Optional for the iterators. Could even put them in a struct and use Optional on the struct. Makes it clearer how the boolean relates to the iterators.

> Source/WebCore/Modules/indexeddb/shared/IDBRequestData.cpp:94
> +    RELEASE_ASSERT(m_cursorIdentifier);

Why do we need a RELEASE_ASSERT here? Normally those are done because of security concerns, or because we have some critical need to learn about failures that otherwise would create confusing crash reports, but I don’t think either criterion applies here. I don’t think an assertion failure will give a better result than a null-dereference.

We should use RELEASE_ASSERT sparingly, and I don’t think this is a place where it’s called for.

[Brady Eidson]

Most of your comments are concise suggestions that require no further discussion, and I will address them in the patch.

Others I will address in comment replies here:

(In reply to comment #3)
> Comment on attachment 265534 [details]
> Patch v1
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=265534&action=review
> 
> Why this use of std::set? Is this the right data structure to use? Is both
> memory use and speed acceptable?

The requirements are for an ordered (based on a comparison operator) set.

The closest we have in WTF is list (based on insertion order) set.

Additionally, while not a strict requirement, it is immensely convenient to have iterators into the data structure not be invalidated by changes to other records in the set, which std::set also provides.

I've discussed the use of std::set with Geoff and a few others and no better alternative has come up.

> > Source/WebCore/Modules/indexeddb/server/MemoryCursor.h:47
> > +    virtual void iterate(const IDBKeyData&, unsigned long count, IDBGetResult&) = 0;
> 
> The type here should be unsigned, not unsigned long.
> 
> I believe there are a lot of things that are typed unsigned long because
> there are arguments with the type unsigned long in the IDL. But,
> confusingly, unsigned long in IDL means specifically 32-bit, and we use
> unsigned (or uint32_t) for that in actual C++ code. I believe this mistake
> has been made throughout quite a bit of IDB code, and so we are doing 64-bit
> operations for no good reason; the bindings will accept only 32-bit
> integers, but we then extend them to 64-bit and keep them as such throughout
> the C++ code on 64-bit platforms, but not on 32-bit platforms.

This is good to know - I was not aware of this meaning in the IDL.

I'll try to not perpetuate that mistake in this patch, and filed https://bugs.webkit.org/show_bug.cgi?id=151296 to pass through all of Modern IDB later.

> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStore.cpp:385
> > +    auto result = m_cursors.add(info.identifier(), MemoryObjectStoreCursor::create(*this, info));
> > +    if (!result.isNewEntry)
> > +        return nullptr;
> > +
> > +    return result.iterator->value.get();
> 
> This is inefficient when the cursor already exists. It allocates and
> destroys a cursor that is never used for anything. It would be more
> efficient and more conventional to write it like this:
> 
>     auto result = m_cursors.add(info.identifier(), nullptr);
>     if (!result.isNewEntry)
>         return nullptr;
> 
>     result.iterator->value = MemoryObjectStoreCursor::create(*this, info);
>     return result.iterator->value.get();

Du
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:48
> > +    std::set<IDBKeyData>* orderedKeys = objectStore.orderedKeys();
> 
> I think this reads better with auto*.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:90
> > +    ASSERT(set);
> 
> An assertion like this one typically indicates that the function should be a
> taking a reference rather than a pointer. I suggest making that change here.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:110
> > +    ASSERT(set);
> 
> An assertion like this one typically indicates that the function should be a
> taking a reference rather than a pointer. I suggest making that change here.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:123
> > +    if (m_remainingRange.lowerOpen && *lowest == m_remainingRange.lowerKey)
> > +        ++lowest;
> > +
> > +    if (lowest == set->end())
> > +        return lowest;
> 
> I suggest nesting the second if statement inside the first.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.cpp:138
> > +    ASSERT(set);
> 
> An assertion like this one typically indicates that the function should be a
> taking a reference rather than a pointer. I suggest making that change here.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:44
> > +    static std::unique_ptr<MemoryObjectStoreCursor> create(MemoryObjectStore&, const IDBCursorInfo&);
> 
> In cases like this where create is simply a call to make_unique, I am not
> sure we need to write a create function. At the call site we should just
> write:
> 
>     auto cursor = std::make_unique<MemoryObjectStoreCursor>(store, info);
> 
> Further, I am not sure we need the constructor to be private. Is there harm
> in allocating one of these that is not on the heap? For reference counted
> objects there is, and that’s why the create pattern exists for them. But for
> single ownership objects it’s typically not important to make the
> constructor private, even if in practice we always allocate them on the heap.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:47
> > +    virtual void currentData(IDBGetResult&) override final;
> > +    virtual void iterate(const IDBKeyData&, unsigned long count, IDBGetResult&) override final;
> 
> Any reason to not have these overrides be private?
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:61
> > +    void incrementForwardIterator(const IDBKeyData&, unsigned long count);
> > +    void incrementReverseIterator(const IDBKeyData&, unsigned long count);
> 
> Type here should be unsigned, not unsigned long. See comment elsewhere
> explaining why I think this happened.
> 
> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:69
> > +    std::set<IDBKeyData>::iterator m_forwardIterator;
> > +    std::set<IDBKeyData>::reverse_iterator m_reverseIterator;
> 
> I’m slightly concerned at the use of long-lived std::set iterators and
> reverse iterators. Does the std::set implementation we are using on major
> platforms include checks on iterators like the ones we have in HashMap?

C++ 11 requires the appropriate iterator behavior. The only sticking point is/was the requirement of the "undefined iterator" bool mentioned in the next comment...

> > Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:70
> > +    bool m_iteratorsUndefined { true };
> 
> Another way to do this is to use Optional for the iterators. Could even put
> them in a struct and use Optional on the struct. Makes it clearer how the
> boolean relates to the iterators.

This, of course, makes perfect sense for getting rid of the ugly bool.

Thanks for the thorough review!

[Brady Eidson]

Created attachment 265606 [details]
Patch for landing

[Build Bot]

Comment on attachment 265606 [details]
Patch for landing

Attachment 265606 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.webkit.org/results/438205

New failing tests:
storage/indexeddb/modern/cursor-2.html

[Build Bot]

Created attachment 265610 [details]
Archive of layout-test-results from ews102 for mac-mavericks

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews102  Port: mac-mavericks  Platform: Mac OS X 10.9.5

[Brady Eidson]

Created attachment 265612 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 265612 [details]
Patch for landing

Clearing flags on attachment: 265612

Committed r192490: <http://trac.webkit.org/changeset/192490>

[Ryan Haddad]

storage/indexeddb/modern/cursor-2.html is flakily timing out on El Capitan Debug WK1: <https://build.webkit.org/builders/Apple%20El%20Capitan%20Debug%20WK1%20(Tests)/builds/1177>

[Darin Adler]

Comment on attachment 265534 [details]
Patch v1

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

>> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:44
>> +    static std::unique_ptr<MemoryObjectStoreCursor> create(MemoryObjectStore&, const IDBCursorInfo&);
> 
> In cases like this where create is simply a call to make_unique, I am not sure we need to write a create function. At the call site we should just write:
> 
>     auto cursor = std::make_unique<MemoryObjectStoreCursor>(store, info);
> 
> Further, I am not sure we need the constructor to be private. Is there harm in allocating one of these that is not on the heap? For reference counted objects there is, and that’s why the create pattern exists for them. But for single ownership objects it’s typically not important to make the constructor private, even if in practice we always allocate them on the heap.

This is the one comment from the patch that I didn’t see addressed in the what you finally landed, nor did you respond and say “I decided not to do this”. I’d love to discuss it at some point, although it’s not urgent.

[Brady Eidson]

(In reply to comment #11)
> Comment on attachment 265534 [details]
> Patch v1
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=265534&action=review
> 
> >> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:44
> >> +    static std::unique_ptr<MemoryObjectStoreCursor> create(MemoryObjectStore&, const IDBCursorInfo&);
> > 
> > In cases like this where create is simply a call to make_unique, I am not sure we need to write a create function. At the call site we should just write:
> > 
> >     auto cursor = std::make_unique<MemoryObjectStoreCursor>(store, info);
> > 
> > Further, I am not sure we need the constructor to be private. Is there harm in allocating one of these that is not on the heap? For reference counted objects there is, and that’s why the create pattern exists for them. But for single ownership objects it’s typically not important to make the constructor private, even if in practice we always allocate them on the heap.
> 
> This is the one comment from the patch that I didn’t see addressed in the
> what you finally landed, nor did you respond and say “I decided not to do
> this”. I’d love to discuss it at some point, although it’s not urgent.

I don't think there's anything to discuss. I meant to do it, and at one point in my final cleanup had done it, but it got lost in some reshuffling and git frustration.

I will follow up shortly.

[Brady Eidson]

(In reply to comment #12)
> (In reply to comment #11)
> > Comment on attachment 265534 [details]
> > Patch v1
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=265534&action=review
> > 
> > >> Source/WebCore/Modules/indexeddb/server/MemoryObjectStoreCursor.h:44
> > >> +    static std::unique_ptr<MemoryObjectStoreCursor> create(MemoryObjectStore&, const IDBCursorInfo&);
> > > 
> > > In cases like this where create is simply a call to make_unique, I am not sure we need to write a create function. At the call site we should just write:
> > > 
> > >     auto cursor = std::make_unique<MemoryObjectStoreCursor>(store, info);
> > > 
> > > Further, I am not sure we need the constructor to be private. Is there harm in allocating one of these that is not on the heap? For reference counted objects there is, and that’s why the create pattern exists for them. But for single ownership objects it’s typically not important to make the constructor private, even if in practice we always allocate them on the heap.
> > 
> > This is the one comment from the patch that I didn’t see addressed in the
> > what you finally landed, nor did you respond and say “I decided not to do
> > this”. I’d love to discuss it at some point, although it’s not urgent.
> 
> I don't think there's anything to discuss. I meant to do it, and at one
> point in my final cleanup had done it, but it got lost in some reshuffling
> and git frustration.
> 
> I will follow up shortly.

Addressed in https://trac.webkit.org/changeset/192694