HTMLConverter::aggregatedAttributesForAncestors should cache intermediate results
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 9 Apr 2014 00:06:09 +0000 (00:06 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 9 Apr 2014 00:06:09 +0000 (00:06 +0000)
https://bugs.webkit.org/show_bug.cgi?id=131400

Reviewed by Sam Weinig.

Instead of accumulating attributes from a character node to the highest ancestor,
recursively call aggregatedAttributesForElementAndItsAncestors so that aggregated
attributes are cached on each ancestor to eliminate the old O(n^2) behavior.

* editing/cocoa/HTMLConverter.mm:
(HTMLConverter::aggregatedAttributesForAncestors):
(HTMLConverter::aggregatedAttributesForElementAndItsAncestors): Extracted from aggregatedAttributesForAncestors.

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

Source/WebCore/ChangeLog
Source/WebCore/editing/cocoa/HTMLConverter.mm

index 6dd117e4b466f6563463c8dee4e1187c49f72a2c..74162d18c2e3aa5ee17ebc7ffc036c4375ec9fc7 100644 (file)
@@ -1,3 +1,18 @@
+2014-04-08  Ryosuke Niwa  <rniwa@webkit.org>
+
+        HTMLConverter::aggregatedAttributesForAncestors should cache intermediate results
+        https://bugs.webkit.org/show_bug.cgi?id=131400
+
+        Reviewed by Sam Weinig.
+
+        Instead of accumulating attributes from a character node to the highest ancestor,
+        recursively call aggregatedAttributesForElementAndItsAncestors so that aggregated
+        attributes are cached on each ancestor to eliminate the old O(n^2) behavior.
+
+        * editing/cocoa/HTMLConverter.mm:
+        (HTMLConverter::aggregatedAttributesForAncestors):
+        (HTMLConverter::aggregatedAttributesForElementAndItsAncestors): Extracted from aggregatedAttributesForAncestors.
+
 2014-04-08  Jinwoo Song  <jinwoo7.song@samsung.com>
 
         Unreviewed CMake build fix after r166965.
index 0b26d862ec1c746354e1fbd4d5e99d0409f30b71..6d4d68ebcd8c033fee50c2ba5285879709bc89a4 100644 (file)
@@ -449,7 +449,7 @@ private:
     
     HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_attributesForElements;
     HashMap<RetainPtr<NSTextTable>, RefPtr<Element>> m_textTableFooters;
-    HashMap<RefPtr<Element>, RetainPtr<NSMutableDictionary>> m_aggregatedAttributesForElements;
+    HashMap<RefPtr<Element>, RetainPtr<NSDictionary>> m_aggregatedAttributesForElements;
 
     NSMutableAttributedString *_attrStr;
     NSMutableDictionary *_documentAttrs;
@@ -487,7 +487,8 @@ private:
     NSDictionary *computedAttributesForElement(Element&);
     NSDictionary *attributesForElement(Element&);
     NSDictionary *aggregatedAttributesForAncestors(CharacterData&);
-    
+    NSDictionary* aggregatedAttributesForElementAndItsAncestors(Element&);
+
     Element* _blockLevelElementForNode(Node*);
     
     void _newParagraphForElement(Element&, NSString *tag, BOOL flag, BOOL suppressTrailingSpace);
@@ -1357,25 +1358,32 @@ NSDictionary* HTMLConverter::aggregatedAttributesForAncestors(CharacterData& nod
         ancestor = ancestor->parentNode();
     if (!ancestor)
         return nullptr;
+    return aggregatedAttributesForElementAndItsAncestors(*toElement(ancestor));
+}
 
-    auto& attributes = m_aggregatedAttributesForElements.add(toElement(ancestor), nullptr).iterator->value;
-    if (!attributes) {
-        Vector<Element*, 16> ancestorElements;
-        ancestorElements.append(toElement(ancestor));
-        for (; ancestor; ancestor = ancestor->parentNode()) {
-            if (ancestor->isElementNode())
-                ancestorElements.append(toElement(ancestor));
-        }
+NSDictionary* HTMLConverter::aggregatedAttributesForElementAndItsAncestors(Element& element)
+{
+    auto& cachedAttributes = m_aggregatedAttributesForElements.add(&element, nullptr).iterator->value;
+    if (cachedAttributes)
+        return cachedAttributes.get();
 
-        attributes = [NSMutableDictionary dictionary];
-        // Fill attrs dictionary with attributes from the highest to the lowest, not overwriting ones deeper in the tree
-        for (unsigned index = ancestorElements.size(); index;) {
-            index--;
-            [attributes addEntriesFromDictionary:attributesForElement(*ancestorElements[index])];
-        }
+    NSDictionary* attributesForCurrentElement = attributesForElement(element);
+    ASSERT(attributesForCurrentElement);
+
+    Node* ancestor = element.parentNode();
+    while (ancestor && !ancestor->isElementNode())
+        ancestor = ancestor->parentNode();
+
+    if (!ancestor) {
+        cachedAttributes = attributesForCurrentElement;
+        return attributesForCurrentElement;
     }
 
-    return attributes.get();
+    RetainPtr<NSMutableDictionary> attributesForAncestors = adoptNS([aggregatedAttributesForElementAndItsAncestors(*toElement(ancestor)) mutableCopy]);
+    [attributesForAncestors addEntriesFromDictionary:attributesForCurrentElement];
+    m_aggregatedAttributesForElements.set(&element, attributesForAncestors);
+
+    return attributesForAncestors.get();
 }
 
 void HTMLConverter::_newParagraphForElement(Element& element, NSString *tag, BOOL flag, BOOL suppressTrailingSpace)