Iterating backwards over HTMLCollection is O(n^2)
https://bugs.webkit.org/show_bug.cgi?id=91306

Reviewed by Anders Carlsson.

Source/WebCore: 

Fixed the bug by introducing itemBefore that iterates nodes backwards to complement itemAfter.
Unfortunately, some HTML collections such as HTMLFormCollection and HTMLTableRowsCollection have
its own itemAfter function and writing an equivalent itemBefore is somewhat tricky. For now,
added a new boolean flag indicating whether a given HTML collection supports itemBefore or not,
and left those HTML collections that override itemAfter alone.

This also paves our way to share more code between DynamicNodeList and HTMLCollection.

Test: perf/htmlcollection-backwards-iteration.html

* dom/DynamicNodeList.h:
(WebCore::DynamicNodeListCacheBase::DynamicNodeListCacheBase): Takes ItemBeforeSupportType.
(WebCore::DynamicNodeListCacheBase::supportsItemBefore): Added.
(DynamicNodeListCacheBase):
(WebCore::DynamicNodeListCacheBase::setItemCache): Replaced a FIXME by an assertion now that
we can.
* html/HTMLAllCollection.cpp:
(WebCore::HTMLAllCollection::HTMLAllCollection): Supports itemBefore since it doesn't override
itemAfter.
* html/HTMLCollection.cpp:
(WebCore::HTMLCollection::HTMLCollection):
(WebCore::HTMLCollection::create):
(WebCore::isAcceptableElement): Made it a static local function instead of a static member.
(WebCore::nextNode): Templatized.
(WebCore::itemBeforeOrAfter): Extracted from itemAfter and templatized.
(WebCore::HTMLCollection::itemBefore): Added.
(WebCore::HTMLCollection::itemAfter):
(WebCore::HTMLCollection::shouldSearchFromFirstItem): Added. Determines whether we should reset
the item cache to the first item. We obviously do if the cache is invalid. If the target offset
is after the cached offset, then we shouldn't go back regardless of availability of itemBefore.
Otherwise, we go back to the first item iff itemBefore is not available or the distance from
the cached offset to the target offset is greater than the target offset itself.
(WebCore::HTMLCollection::length):
(WebCore::HTMLCollection::item): Use the term "offset" to match the terminology elsewhere.
(WebCore::HTMLCollection::itemBeforeOrAfterCachedItem): Ditto. Also added the logic to iterate
nodes backwards using itemBefore. Once we're in this branch, we should always find a matching
item since the target offset was less than the cached offset, and offsets are non-negative.
If we had ever reached the end of the loop without finding an item, it indicates that the cache
has been invalid and we have some serious bug elsewhere.
* html/HTMLCollection.h:
(WebCore::HTMLCollectionCacheBase::HTMLCollectionCacheBase):
(HTMLCollection):
* html/HTMLOptionsCollection.cpp:
(WebCore::HTMLOptionsCollection::HTMLOptionsCollection): Supports itemBefore since it doesn't
override itemAfter.
* html/HTMLFormCollection.cpp:
(WebCore::HTMLFormCollection::HTMLFormCollection): Doesn't support itemBefore as it overrides
itemAfter.
* html/HTMLNameCollection.cpp:
(WebCore::HTMLNameCollection::HTMLNameCollection): Ditto.
* html/HTMLPropertiesCollection.cpp:
(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
* html/HTMLTableRowsCollection.cpp:
(WebCore::HTMLTableRowsCollection::HTMLTableRowsCollection):

LayoutTests: 

Add an asymptotic time complexity test.

* perf/htmlcollection-backwards-iteration-expected.txt: Added.
* perf/htmlcollection-backwards-iteration.html: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122660 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Unreviewed GTK gardening, adding an image expectation for a test introduced
in r122651. Also creating platform-specific baselines for two File API tests
that behave differently because of function overloading problems but pass otherwise,
and skipping a test for correct viewport of sites with Mobile DTD which GTK port
does not (yet) support.

* platform/gtk/TestExpectations:
* platform/gtk/fast/files/create-blob-url-crash-expected.txt: Added.
* platform/gtk/fast/files/url-required-arguments-expected.txt: Added.


git-svn-id: http://svn.webkit.org/repository/webkit/trunk@122661 268f45cc-cd09-0410-ab3c-d52691b4dbfc