Diff
Modified: trunk/LayoutTests/ChangeLog (122659 => 122660)
--- trunk/LayoutTests/ChangeLog 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/LayoutTests/ChangeLog 2012-07-14 07:08:55 UTC (rev 122660)
@@ -1,3 +1,15 @@
+2012-07-13 Ryosuke Niwa <[email protected]>
+
+ Iterating backwards over HTMLCollection is O(n^2)
+ https://bugs.webkit.org/show_bug.cgi?id=91306
+
+ Reviewed by Anders Carlsson.
+
+ Add an asymptotic time complexity test.
+
+ * perf/htmlcollection-backwards-iteration-expected.txt: Added.
+ * perf/htmlcollection-backwards-iteration.html: Added.
+
2012-07-13 Kent Tamura <[email protected]>
Internals: Clean up the mock PagePopupDriver correctly.
Added: trunk/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt (0 => 122660)
--- trunk/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt (rev 0)
+++ trunk/LayoutTests/perf/htmlcollection-backwards-iteration-expected.txt 2012-07-14 07:08:55 UTC (rev 122660)
@@ -0,0 +1,3 @@
+Tests that iterating over HTMLCollection backwards is linear.
+PASS
+
Added: trunk/LayoutTests/perf/htmlcollection-backwards-iteration.html (0 => 122660)
--- trunk/LayoutTests/perf/htmlcollection-backwards-iteration.html (rev 0)
+++ trunk/LayoutTests/perf/htmlcollection-backwards-iteration.html 2012-07-14 07:08:55 UTC (rev 122660)
@@ -0,0 +1,28 @@
+<!DOCTYPE html>
+<body>
+<div id="container" style="display: none;"></div>
+<script src=""
+<script>
+
+var container = document.getElementById('container');
+
+function setupFunction(magnitude)
+{
+ container.innerHTML = '';
+ for (var i = 0; i < magnitude; i++)
+ container.appendChild(document.createElement('div'));
+}
+
+function test(magnitude)
+{
+ var children = container.children;
+ for (var i = children.length; i > 0;i--)
+ children[i - 1].class = 'hi';
+}
+
+Magnitude.description("Tests that iterating over HTMLCollection backwards is linear.");
+Magnitude.run(setupFunction, test, Magnitude.LINEAR);
+
+</script>
+</body>
+</html>
Modified: trunk/Source/WebCore/ChangeLog (122659 => 122660)
--- trunk/Source/WebCore/ChangeLog 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/ChangeLog 2012-07-14 07:08:55 UTC (rev 122660)
@@ -1,3 +1,65 @@
+2012-07-13 Ryosuke Niwa <[email protected]>
+
+ Iterating backwards over HTMLCollection is O(n^2)
+ https://bugs.webkit.org/show_bug.cgi?id=91306
+
+ Reviewed by Anders Carlsson.
+
+ 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):
+
2012-07-13 Eric Penner <[email protected]>
[chromium] Add 'self-managed' option to CCPrioritizedTexture to enable render-surface and canvas use cases.
Modified: trunk/Source/WebCore/dom/DynamicNodeList.h (122659 => 122660)
--- trunk/Source/WebCore/dom/DynamicNodeList.h 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/dom/DynamicNodeList.h 2012-07-14 07:08:55 UTC (rev 122660)
@@ -43,7 +43,13 @@
class DynamicNodeListCacheBase {
public:
- DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType = InvalidCollectionType)
+ enum ItemBeforeSupportType {
+ DoNotSupportItemBefore,
+ SupportItemBefore,
+ };
+
+ DynamicNodeListCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType,
+ CollectionType collectionType = InvalidCollectionType, ItemBeforeSupportType itemBeforeSupportType = DoNotSupportItemBefore)
: m_cachedItem(0)
, m_isLengthCacheValid(false)
, m_isItemCacheValid(false)
@@ -51,6 +57,7 @@
, m_invalidationType(invalidationType)
, m_isNameCacheValid(false)
, m_collectionType(collectionType)
+ , m_supportsItemBefore(itemBeforeSupportType == SupportItemBefore)
{
ASSERT(m_invalidationType == static_cast<unsigned>(invalidationType));
ASSERT(m_collectionType == static_cast<unsigned>(collectionType));
@@ -66,6 +73,8 @@
static bool shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType, const QualifiedName&);
protected:
+ bool supportsItemBefore() const { return m_supportsItemBefore; }
+
ALWAYS_INLINE bool isItemCacheValid() const { return m_isItemCacheValid; }
ALWAYS_INLINE Node* cachedItem() const { return m_cachedItem; }
ALWAYS_INLINE unsigned cachedItemOffset() const { return m_cachedItemOffset; }
@@ -79,7 +88,7 @@
}
ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const
{
- // FIXME: Assert that item is not null once we've updated DynamicNodeList.
+ ASSERT(item);
m_cachedItem = item;
m_cachedItemOffset = offset;
m_isItemCacheValid = true;
@@ -100,6 +109,7 @@
// From HTMLCollection
mutable unsigned m_isNameCacheValid : 1;
const unsigned m_collectionType : 5;
+ const unsigned m_supportsItemBefore : 1;
};
ALWAYS_INLINE bool DynamicNodeListCacheBase::shouldInvalidateTypeOnAttributeChange(NodeListInvalidationType type, const QualifiedName& attrName)
Modified: trunk/Source/WebCore/html/HTMLAllCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLAllCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLAllCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -36,7 +36,7 @@
}
HTMLAllCollection::HTMLAllCollection(Document* document)
- : HTMLCollection(document, DocAll)
+ : HTMLCollection(document, DocAll, SupportItemBefore)
{
}
Modified: trunk/Source/WebCore/html/HTMLCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -152,8 +152,8 @@
}
-HTMLCollection::HTMLCollection(Node* base, CollectionType type)
- : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type)
+HTMLCollection::HTMLCollection(Node* base, CollectionType type, ItemBeforeSupportType itemBeforeSupportType)
+ : HTMLCollectionCacheBase(rootTypeFromCollectionType(type), invalidationTypeExcludingIdAndNameAttributes(type), type, itemBeforeSupportType)
, m_base(base)
{
ASSERT(m_base);
@@ -162,7 +162,7 @@
PassRefPtr<HTMLCollection> HTMLCollection::create(Node* base, CollectionType type)
{
- return adoptRef(new HTMLCollection(base, type));
+ return adoptRef(new HTMLCollection(base, type, SupportItemBefore));
}
HTMLCollection::~HTMLCollection()
@@ -179,12 +179,12 @@
m_base->document()->unregisterNodeListCache(this);
}
-inline bool HTMLCollection::isAcceptableElement(Element* element) const
+static inline bool isAcceptableElement(CollectionType type, Element* element)
{
- if (!element->isHTMLElement() && !(type() == DocAll || type() == NodeChildren))
+ if (!element->isHTMLElement() && !(type == DocAll || type == NodeChildren))
return false;
- switch (type()) {
+ switch (type) {
case DocImages:
return element->hasLocalName(imgTag);
case DocScripts:
@@ -237,26 +237,54 @@
return false;
}
-static ALWAYS_INLINE Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
+template<bool forward>
+static Node* nextNode(Node* base, Node* previous, bool onlyIncludeDirectChildren)
{
- return onlyIncludeDirectChildren ? previous->traverseNextSibling(base) : previous->traverseNextNode(base);
+ if (forward)
+ return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
+ else
+ return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);
}
-Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+template<bool forward>
+static Element* itemBeforeOrAfter(CollectionType type, Node* base, unsigned& offsetInArray, Node* previous)
{
ASSERT_UNUSED(offsetInArray, !offsetInArray);
- bool _onlyIncludeDirectChildren_ = shouldOnlyIncludeDirectChildren(type());
- Node* rootNode = base();
- Node* current = previous ? nextNode(rootNode, previous, onlyIncludeDirectChildren) : m_base->firstChild();
+ bool _onlyIncludeDirectChildren_ = shouldOnlyIncludeDirectChildren(type);
+ Node* rootNode = base;
+ Node* current = previous ? nextNode<forward>(rootNode, previous, onlyIncludeDirectChildren) : (forward ? base->firstChild() : base->lastChild());
- for (; current; current = nextNode(rootNode, current, onlyIncludeDirectChildren)) {
- if (current->isElementNode() && isAcceptableElement(toElement(current)))
+ for (; current; current = nextNode<forward>(rootNode, current, onlyIncludeDirectChildren)) {
+ if (current->isElementNode() && isAcceptableElement(type, toElement(current)))
return toElement(current);
}
return 0;
}
+Element* HTMLCollection::itemBefore(unsigned& offsetInArray, Element* previous) const
+{
+ return itemBeforeOrAfter<false>(type(), base(), offsetInArray, previous);
+}
+
+Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+{
+ return itemBeforeOrAfter<true>(type(), base(), offsetInArray, previous);
+}
+
+bool ALWAYS_INLINE HTMLCollection::shouldSearchFromFirstItem(unsigned offset) const
+{
+ if (!isItemCacheValid())
+ return true;
+
+ ASSERT(offset != cachedItemOffset());
+ if (offset > cachedItemOffset())
+ return false;
+
+ unsigned distanceFromCachedItem = cachedItemOffset() - offset;
+ return !supportsItemBefore() || offset < distanceFromCachedItem;
+}
+
unsigned HTMLCollection::length() const
{
if (isLengthCacheValid())
@@ -272,18 +300,18 @@
unsigned offset = cachedItemOffset();
do {
offset++;
- } while (itemAfterCachedItem(offset));
+ } while (itemBeforeOrAfterCachedItem(offset));
setLengthCache(offset);
return offset;
}
-Node* HTMLCollection::item(unsigned index) const
+Node* HTMLCollection::item(unsigned offset) const
{
- if (isItemCacheValid() && cachedItemOffset() == index)
+ if (isItemCacheValid() && cachedItemOffset() == offset)
return cachedItem();
- if (isLengthCacheValid() && cachedLength() <= index)
+ if (isLengthCacheValid() && cachedLength() <= offset)
return 0;
#if ENABLE(MICRODATA)
@@ -291,7 +319,7 @@
static_cast<const HTMLPropertiesCollection*>(this)->updateRefElements();
#endif
- if (!isItemCacheValid() || cachedItemOffset() > index) {
+ if (shouldSearchFromFirstItem(offset)) {
unsigned offsetInArray = 0;
Node* firstItem = itemAfter(offsetInArray, 0);
if (!firstItem) {
@@ -300,30 +328,45 @@
}
setItemCache(firstItem, 0, offsetInArray);
ASSERT(!cachedItemOffset());
- if (!index)
+ if (!offset)
return cachedItem();
}
- return itemAfterCachedItem(index);
+ return itemBeforeOrAfterCachedItem(offset);
}
-Element* HTMLCollection::itemAfterCachedItem(unsigned index) const
+Element* HTMLCollection::itemBeforeOrAfterCachedItem(unsigned offset) const
{
- unsigned currentIndex = cachedItemOffset();
+ unsigned currentOffset = cachedItemOffset();
ASSERT(cachedItem()->isElementNode());
Element* currentItem = toElement(cachedItem());
- ASSERT(currentIndex < index);
+ ASSERT(currentOffset != offset);
unsigned offsetInArray = cachedElementsArrayOffset();
+
+ if (offset < cachedItemOffset()) {
+ ASSERT(supportsItemBefore());
+ while ((currentItem = itemBefore(offsetInArray, currentItem))) {
+ ASSERT(currentOffset);
+ currentOffset--;
+ if (currentOffset == offset) {
+ setItemCache(currentItem, currentOffset, offsetInArray);
+ return currentItem;
+ }
+ }
+ ASSERT_NOT_REACHED();
+ return 0;
+ }
+
while ((currentItem = itemAfter(offsetInArray, currentItem))) {
- currentIndex++;
- if (currentIndex == index) {
- setItemCache(currentItem, currentIndex, offsetInArray);
+ currentOffset++;
+ if (currentOffset == offset) {
+ setItemCache(currentItem, currentOffset, offsetInArray);
return currentItem;
}
}
- setLengthCache(currentIndex);
+ setLengthCache(currentOffset);
return 0;
}
Modified: trunk/Source/WebCore/html/HTMLCollection.h (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLCollection.h 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLCollection.h 2012-07-14 07:08:55 UTC (rev 122660)
@@ -39,8 +39,8 @@
class HTMLCollectionCacheBase : public DynamicNodeListCacheBase {
public:
- HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType)
- : DynamicNodeListCacheBase(rootType, invalidationType, collectionType)
+ HTMLCollectionCacheBase(NodeListRootType rootType, NodeListInvalidationType invalidationType, CollectionType collectionType, ItemBeforeSupportType itemBeforeSupportType)
+ : DynamicNodeListCacheBase(rootType, invalidationType, collectionType, itemBeforeSupportType)
, m_cachedElementsArrayOffset(0)
{
}
@@ -106,7 +106,7 @@
Node* base() const { return m_base.get(); }
protected:
- HTMLCollection(Node* base, CollectionType);
+ HTMLCollection(Node* base, CollectionType, ItemBeforeSupportType);
virtual void updateNameCache() const;
virtual Element* itemAfter(unsigned& offsetInArray, Element*) const;
@@ -114,8 +114,9 @@
private:
bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
- Element* itemAfterCachedItem(unsigned) const;
- bool isAcceptableElement(Element*) const;
+ Element* itemBefore(unsigned& offsetInArray, Element*) const;
+ bool shouldSearchFromFirstItem(unsigned offset) const;
+ Element* itemBeforeOrAfterCachedItem(unsigned offset) const;
RefPtr<Node> m_base;
};
Modified: trunk/Source/WebCore/html/HTMLFormCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLFormCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLFormCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -37,7 +37,7 @@
// calculation every time if anything has changed.
HTMLFormCollection::HTMLFormCollection(Element* base)
- : HTMLCollection(base, FormControls)
+ : HTMLCollection(base, FormControls, DoNotSupportItemBefore)
{
ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
}
Modified: trunk/Source/WebCore/html/HTMLNameCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLNameCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLNameCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -33,7 +33,7 @@
using namespace HTMLNames;
HTMLNameCollection::HTMLNameCollection(Document* document, CollectionType type, const AtomicString& name)
- : HTMLCollection(document, type)
+ : HTMLCollection(document, type, DoNotSupportItemBefore)
, m_name(name)
{
}
Modified: trunk/Source/WebCore/html/HTMLOptionsCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLOptionsCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLOptionsCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -28,7 +28,7 @@
namespace WebCore {
HTMLOptionsCollection::HTMLOptionsCollection(Element* select)
- : HTMLCollection(select, SelectOptions)
+ : HTMLCollection(select, SelectOptions, SupportItemBefore)
{
ASSERT(select->hasTagName(HTMLNames::selectTag));
}
Modified: trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -51,7 +51,7 @@
}
HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
- : HTMLCollection(itemNode, ItemProperties)
+ : HTMLCollection(itemNode, ItemProperties, DoNotSupportItemBefore)
, m_hasPropertyNameCache(false)
, m_hasItemRefElements(false)
{
Modified: trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp (122659 => 122660)
--- trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp 2012-07-14 03:45:48 UTC (rev 122659)
+++ trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp 2012-07-14 07:08:55 UTC (rev 122660)
@@ -152,7 +152,7 @@
// table to get at the collection cache. Order of argument evaluation is undefined and can
// differ between compilers.
HTMLTableRowsCollection::HTMLTableRowsCollection(Element* table)
- : HTMLCollection(table, TableRows)
+ : HTMLCollection(table, TableRows, DoNotSupportItemBefore)
{
ASSERT(table->hasTagName(tableTag));
}
