Changeset 113862 in webkit


Ignore:
Timestamp:
Apr 11, 2012 8:20:04 AM (12 years ago)
Author:
arko@motorola.com
Message:

Microdata: Implement cache mechanism for HTMLPropertiesCollection.
​https://bugs.webkit.org/show_bug.cgi?id=80490

Reviewed by Ryosuke Niwa.

Implemented caching mechanism for HTMLPropertiesCollection.
propertyCache - contains microdata item properties.
itemRefElements - contains sorted microdata item and itemref elements.
propertyNames - contains microdata property names of the elements in the collection.
itemRefElementPosition - store the current position of itemRefElements.
hasItemRefElements - set to ture once we have sorted microdata item and itemref elements list i.e, itemRefElements.
Cache is invalidated only when dom tree modified. Whenever any query is made on HTMLPropertiesCollection,
result is returned from the cache. Earliar we used to calculate properties node list every time a query is made.

  • html/HTMLPropertiesCollection.cpp:

(WebCore):
(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
(WebCore::HTMLPropertiesCollection::invalidateCacheIfNeeded):
(WebCore::HTMLPropertiesCollection::updateRefElements): Appends microdata item element and elements which
are added through itemref attribute in itemRefElements (in tree order).
(WebCore::nextNodeWithProperty):
(WebCore::HTMLPropertiesCollection::itemAfter): Takes parent base and previous item property as argument.
Finds the next item property in base.
(WebCore::HTMLPropertiesCollection::calcLength): Calculates the length of properties collection if length
is not available in the cache.
(WebCore::HTMLPropertiesCollection::length):
(WebCore::HTMLPropertiesCollection::firstProperty): Returns the first property in the collection.
(WebCore::HTMLPropertiesCollection::item):
(WebCore::HTMLPropertiesCollection::findProperties): Finds microdata item properties in the base element.
Appends the properties in propertyCache and property names in propertyNames.
(WebCore::HTMLPropertiesCollection::updateNameCache): It updates the propertyCache and propertyNames if hasNameCache is false.
(WebCore::HTMLPropertiesCollection::names):
(WebCore::HTMLPropertiesCollection::namedItem):
(WebCore::HTMLPropertiesCollection::hasNamedItem):

  • html/HTMLPropertiesCollection.h:

(HTMLPropertiesCollection):

Location:
trunk/Source/WebCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r113859 r113862  
     12012-04-11   Arko Saha  <arko@motorola.com>
     2
     3        Microdata: Implement cache mechanism for HTMLPropertiesCollection.
     4        https://bugs.webkit.org/show_bug.cgi?id=80490
     5
     6        Reviewed by Ryosuke Niwa.
     7
     8        Implemented caching mechanism for HTMLPropertiesCollection.
     9        propertyCache - contains microdata item properties.
     10        itemRefElements - contains sorted microdata item and itemref elements.
     11        propertyNames - contains microdata property names of the elements in the collection.
     12        itemRefElementPosition - store the current position of itemRefElements.
     13        hasItemRefElements - set to ture once we have sorted microdata item and itemref elements list i.e, itemRefElements.
     14        Cache is invalidated only when dom tree modified. Whenever any query is made on HTMLPropertiesCollection,
     15        result is returned from the cache. Earliar we used to calculate properties node list every time a query is made.
     16
     17        * html/HTMLPropertiesCollection.cpp:
     18        (WebCore):
     19        (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
     20        (WebCore::HTMLPropertiesCollection::invalidateCacheIfNeeded):
     21        (WebCore::HTMLPropertiesCollection::updateRefElements): Appends microdata item element and elements which
     22        are added through itemref attribute in itemRefElements (in tree order).
     23        (WebCore::nextNodeWithProperty):
     24        (WebCore::HTMLPropertiesCollection::itemAfter): Takes parent base and previous item property as argument.
     25        Finds the next item property in base.
     26        (WebCore::HTMLPropertiesCollection::calcLength): Calculates the length of properties collection if length
     27        is not available in the cache.
     28        (WebCore::HTMLPropertiesCollection::length):
     29        (WebCore::HTMLPropertiesCollection::firstProperty): Returns the first property in the collection.
     30        (WebCore::HTMLPropertiesCollection::item):
     31        (WebCore::HTMLPropertiesCollection::findProperties): Finds microdata item properties in the base element.
     32        Appends the properties in propertyCache and property names in propertyNames.
     33        (WebCore::HTMLPropertiesCollection::updateNameCache):  It updates the propertyCache and propertyNames if hasNameCache is false.
     34        (WebCore::HTMLPropertiesCollection::names):
     35        (WebCore::HTMLPropertiesCollection::namedItem):
     36        (WebCore::HTMLPropertiesCollection::hasNamedItem):
     37        * html/HTMLPropertiesCollection.h:
     38        (HTMLPropertiesCollection):
     39
    1402012-04-10  Jocelyn Turcotte  <jocelyn.turcotte@nokia.com>
    241

  • trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp

    r109200 r113862  
    4646using namespace HTMLNames;
    4747
    48 static inline bool compareTreeOrder(Node* node1, Node* node2)
    49 {
    50     return (node2->compareDocumentPosition(node1) & (Node::DOCUMENT_POSITION_PRECEDING | Node::DOCUMENT_POSITION_DISCONNECTED)) == Node::DOCUMENT_POSITION_PRECEDING;
    51 }
    52 
    5348PassOwnPtr<HTMLPropertiesCollection> HTMLPropertiesCollection::create(Node* itemNode)
    5449{
    … …  
    5853HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
    5954    : HTMLCollection(itemNode, ItemProperties)
    60     , m_propertyNames(DOMStringList::create())
    6155{
    6256}
    … …  
    6660}
    6761
    68 void HTMLPropertiesCollection::findPropetiesOfAnItem(Node* root) const
    69 {
    70     // 5.2.5 Associating names with items.
    71     Vector<Node*> memory;
    72 
    73     memory.append(root);
    74 
    75     Vector<Node*> pending;
    76     // Add the child elements of root, if any, to pending.
    77     for (Node* child = root->firstChild(); child; child = child->nextSibling())
    78         if (child->isHTMLElement())
    79             pending.append(child);
    80 
    81     // If root has an itemref attribute, split the value of that itemref attribute on spaces.
    82     // For each resulting token ID, if there is an element in the home subtree of root with the ID ID,
    83     // then add the first such element to pending.
    84     if (toHTMLElement(root)->fastHasAttribute(itemrefAttr)) {
    85         DOMSettableTokenList* itemRef = root->itemRef();
    86 
    87         for (size_t i = 0; i < itemRef->length(); ++i) {
    88             AtomicString id = itemRef->item(i);
    89 
    90             Element* element = root->document()->getElementById(id);
    91             if (element && element->isHTMLElement())
    92                 pending.append(element);
    93         }
    94     }
    95 
    96     // Loop till we have processed all pending elements
    97     while (!pending.isEmpty()) {
    98 
    99         // Remove first element from pending and let current be that element.
    100         Node* current = pending[0];
    101         pending.remove(0);
    102 
    103         // If current is already in memory, there is a microdata error;
    104         if (memory.contains(current)) {
    105             // microdata error;
     62void HTMLPropertiesCollection::invalidateCacheIfNeeded() const
     63{
     64    uint64_t docversion = base()->document()->domTreeVersion();
     65
     66    if (m_cache.version == docversion)
     67        return;
     68
     69    m_cache.clear();
     70    m_cache.version = docversion;
     71}
     72
     73void HTMLPropertiesCollection::updateRefElements() const
     74{
     75    if (m_cache.hasItemRefElements)
     76        return;
     77
     78    Vector<Element*> itemRefElements;
     79    HTMLElement* baseElement = toHTMLElement(base());
     80
     81    if (!baseElement->fastHasAttribute(itemrefAttr)) {
     82        itemRefElements.append(baseElement);
     83        m_cache.setItemRefElements(itemRefElements);
     84        return;
     85    }
     86
     87    DOMSettableTokenList* itemRef = baseElement->itemRef();
     88    RefPtr<DOMSettableTokenList> processedItemRef = DOMSettableTokenList::create();
     89    Node* rootNode = baseElement->treeScope()->rootNode();
     90
     91    for (Node* current = rootNode->firstChild(); current; current = current->traverseNextNode(rootNode)) {
     92        if (!current->isHTMLElement())
    10693            continue;
    107         }
    108 
    109         memory.append(current);
    110 
    111         // If current does not have an itemscope attribute, then: add all the child elements of current to pending.
    11294        HTMLElement* element = toHTMLElement(current);
    113         if (!element->fastHasAttribute(itemscopeAttr)) {
    114             for (Node* child = current->firstChild(); child; child = child->nextSibling())
    115                 if (child->isHTMLElement())
    116                     pending.append(child);
    117         }
    118 
    119         // If current has an itemprop attribute specified, add it to results.
    120         if (element->fastHasAttribute(itempropAttr))
    121              m_properties.append(current);
    122     }
     95
     96        if (element == baseElement) {
     97            itemRefElements.append(element);
     98            continue;
     99        }
     100
     101        const AtomicString& id = element->getIdAttribute();
     102        if (!processedItemRef->tokens().contains(id) && itemRef->tokens().contains(id)) {
     103            processedItemRef->setValue(id);
     104            if (!element->isDescendantOf(baseElement))
     105                itemRefElements.append(element);
     106        }
     107    }
     108
     109    m_cache.setItemRefElements(itemRefElements);
     110}
     111
     112static Node* nextNodeWithProperty(Node* base, Node* node)
     113{
     114    // An Microdata item may contain properties which in turn are items themselves. Properties can
     115    // also themselves be groups of name-value pairs, by putting the itemscope attribute on the element
     116    // that declares the property. If the property has an itemscope attribute specified then we need
     117    // to traverse the next sibling.
     118    return node == base || (node->isHTMLElement() && !toHTMLElement(node)->fastHasAttribute(itemscopeAttr))
     119            ? node->traverseNextNode(base) : node->traverseNextSibling(base);
     120}
     121
     122Element* HTMLPropertiesCollection::itemAfter(Element* base, Element* previous) const
     123{
     124    Node* current;
     125    current = previous ? nextNodeWithProperty(base, previous) : base;
     126
     127    for (; current; current = nextNodeWithProperty(base, current)) {
     128        if (!current->isHTMLElement())
     129            continue;
     130        HTMLElement* element = toHTMLElement(current);
     131        if (element->fastHasAttribute(itempropAttr)) {
     132            return element;
     133        }
     134    }
     135
     136    return 0;
     137}
     138
     139unsigned HTMLPropertiesCollection::calcLength() const
     140{
     141    unsigned length = 0;
     142    updateRefElements();
     143
     144    const Vector<Element*>& itemRefElements = m_cache.getItemRefElements();
     145    for (unsigned i = 0; i < itemRefElements.size(); ++i) {
     146        for (Element* element = itemAfter(itemRefElements[i], 0); element; element = itemAfter(itemRefElements[i], element))
     147            ++length;
     148    }
     149
     150    return length;
    123151}
    124152
    125153unsigned HTMLPropertiesCollection::length() const
    126154{
    127     if (!base()->isHTMLElement() || !toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
     155    if (!toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
    128156        return 0;
    129157
    130     m_properties.clear();
    131     findPropetiesOfAnItem(base());
    132     return m_properties.size();
     158    invalidateCacheIfNeeded();
     159
     160    if (!m_cache.hasLength)
     161        m_cache.updateLength(calcLength());
     162
     163    return m_cache.length;
     164}
     165
     166Element* HTMLPropertiesCollection::firstProperty() const
     167{
     168    Element* element = 0;
     169    m_cache.resetPosition();
     170    const Vector<Element*>& itemRefElements = m_cache.getItemRefElements();
     171    for (unsigned i = 0; i < itemRefElements.size(); ++i) {
     172        element = itemAfter(itemRefElements[i], 0);
     173        if (element) {
     174            m_cache.itemRefElementPosition = i;
     175            break;
     176        }
     177    }
     178
     179    return element;
    133180}
    134181
    135182Node* HTMLPropertiesCollection::item(unsigned index) const
    136183{
    137     if (!base()->isHTMLElement() || !toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
     184    if (!toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
    138185        return 0;
    139186
    140     m_properties.clear();
    141     findPropetiesOfAnItem(base());
    142 
    143     if (m_properties.size() <= index)
     187    invalidateCacheIfNeeded();
     188    if (m_cache.current && m_cache.position == index)
     189        return m_cache.current;
     190
     191    if (m_cache.hasLength && m_cache.length <= index)
    144192        return 0;
    145193
    146     std::sort(m_properties.begin(), m_properties.end(), compareTreeOrder);
    147     return m_properties[index];
     194    updateRefElements();
     195    if (!m_cache.current || m_cache.position > index) {
     196        m_cache.current = firstProperty();
     197        if (!m_cache.current)
     198            return 0;
     199    }
     200
     201    unsigned currentPosition = m_cache.position;
     202    Element* element = m_cache.current;
     203    unsigned itemRefElementPos = m_cache.itemRefElementPosition;
     204    const Vector<Element*>& itemRefElements = m_cache.getItemRefElements();
     205
     206    bool found = (m_cache.position == index);
     207
     208    for (unsigned i = itemRefElementPos; i < itemRefElements.size() && !found; ++i) {
     209        while (currentPosition < index) {
     210            element = itemAfter(itemRefElements[i], element);
     211            if (!element)
     212                break;
     213            currentPosition++;
     214
     215            if (currentPosition == index) {
     216                found = true;
     217                itemRefElementPos = i;
     218                break;
     219            }
     220        }
     221    }
     222
     223    m_cache.updateCurrentItem(element, index, itemRefElementPos);
     224    return m_cache.current;
     225}
     226
     227void HTMLPropertiesCollection::findProperties(Element* base) const
     228{
     229    for (Element* element = itemAfter(base, 0); element; element = itemAfter(base, element)) {
     230        DOMSettableTokenList* itemProperty = element->itemProp();
     231        for (unsigned i = 0; i < itemProperty->length(); ++i)
     232            m_cache.updatePropertyCache(element, itemProperty->item(i));
     233    }
     234}
     235
     236void HTMLPropertiesCollection::updateNameCache() const
     237{
     238    invalidateCacheIfNeeded();
     239    if (m_cache.hasNameCache)
     240        return;
     241
     242    updateRefElements();
     243
     244    const Vector<Element*>& itemRefElements = m_cache.getItemRefElements();
     245    for (unsigned i = 0; i < itemRefElements.size(); ++i)
     246        findProperties(itemRefElements[i]);
     247
     248    m_cache.hasNameCache = true;
    148249}
    149250
    150251PassRefPtr<DOMStringList> HTMLPropertiesCollection::names() const
    151252{
    152     m_properties.clear();
    153     m_propertyNames->clear();
    154 
    155     if (!base()->isHTMLElement() || !toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
    156         return m_propertyNames;
    157 
    158     findPropetiesOfAnItem(base());
    159 
    160     std::sort(m_properties.begin(), m_properties.end(), compareTreeOrder);
    161 
    162     for (size_t i = 0; i < m_properties.size(); ++i) {
    163         // For each item properties, split the value of that itemprop attribute on spaces.
    164         // Add all tokens to property names, with the order preserved but with duplicates removed.
    165         DOMSettableTokenList* itemProperty = m_properties[i]->itemProp();
    166         for (size_t i = 0; i < itemProperty->length(); ++i) {
    167             AtomicString propertyName = itemProperty->item(i);
    168             if (m_propertyNames->isEmpty() || !m_propertyNames->contains(propertyName))
    169                 m_propertyNames->append(propertyName);
    170         }
    171     }
    172 
    173     return m_propertyNames;
     253    if (!toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
     254        return DOMStringList::create();
     255
     256    updateNameCache();
     257
     258    return m_cache.propertyNames;
    174259}
    175260
    176261PassRefPtr<NodeList> HTMLPropertiesCollection::namedItem(const String& name) const
    177262{
    178     if (!base()->isHTMLElement() || !toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
     263    if (!toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
    179264      return 0;
    180265
    181     m_properties.clear();
    182266    Vector<RefPtr<Node> > namedItems;
    183     findPropetiesOfAnItem(base());
    184 
    185     std::sort(m_properties.begin(), m_properties.end(), compareTreeOrder);
    186 
    187     // For each item properties, split the value of that itemprop attribute on spaces.
    188     // Add element to namedItem that contains a property named name, with the order preserved.
    189     for (size_t i = 0; i < m_properties.size(); ++i) {
    190         DOMSettableTokenList* itemProperty = m_properties[i]->itemProp();
    191         if (itemProperty->tokens().contains(name))
    192             namedItems.append(m_properties[i]);
    193     }
     267
     268    updateNameCache();
     269
     270    Vector<Element*>* propertyResults = m_cache.propertyCache.get(AtomicString(name).impl());
     271    for (unsigned i = 0; propertyResults && i < propertyResults->size(); ++i)
     272        namedItems.append(propertyResults->at(i));
    194273
    195274    // FIXME: HTML5 specifies that this should return PropertyNodeList.
    … …  
    199278bool HTMLPropertiesCollection::hasNamedItem(const AtomicString& name) const
    200279{
    201     if (!base()->isHTMLElement() || !toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
     280    if (!toHTMLElement(base())->fastHasAttribute(itemscopeAttr))
    202281        return false;
    203282
    204     m_properties.clear();
    205     findPropetiesOfAnItem(base());
    206 
    207     // For each item properties, split the value of that itemprop attribute on spaces.
    208     // Return true if element contains a property named name.
    209     for (size_t i = 0; i < m_properties.size(); ++i) {
    210         DOMSettableTokenList* itemProperty = m_properties[i]->itemProp();
    211         if (itemProperty->tokens().contains(name))
     283    updateNameCache();
     284
     285    if (Vector<Element*>* propertyCache = m_cache.propertyCache.get(name.impl())) {
     286        if (!propertyCache->isEmpty())
    212287            return true;
    213288    }

  • trunk/Source/WebCore/html/HTMLPropertiesCollection.h

    r109200 r113862  
    3434#if ENABLE(MICRODATA)
    3535
     36#include "DOMStringList.h"
    3637#include "HTMLCollection.h"
    3738
    … …  
    5758    HTMLPropertiesCollection(Node*);
    5859
    59     void findPropetiesOfAnItem(Node* current) const;
    60     void getNamedItems(Vector<RefPtr<Node> >&, const String&) const;
     60    unsigned calcLength() const;
     61    void findProperties(Element* base) const;
    6162
    62     mutable Vector<Node*> m_properties;
    63     mutable RefPtr<DOMStringList> m_propertyNames;
     63    Node* findRefElements(Node* previous) const;
     64
     65    Element* firstProperty() const;
     66    Element* itemAfter(Element* base, Element* previous) const;
     67
     68    void updateNameCache() const;
     69    void updateRefElements() const;
     70
     71    void invalidateCacheIfNeeded() const;
     72
     73    mutable struct {
     74        uint64_t version;
     75        Element* current;
     76        unsigned position;
     77        unsigned length;
     78        bool hasLength;
     79        bool hasNameCache;
     80        NodeCacheMap propertyCache;
     81        Vector<Element*> itemRefElements;
     82        RefPtr<DOMStringList> propertyNames;
     83        unsigned itemRefElementPosition;
     84        bool hasItemRefElements;
     85
     86        void clear()
     87        {
     88            version = 0;
     89            current = 0;
     90            position = 0;
     91            length = 0;
     92            hasLength = false;
     93            hasNameCache = false;
     94            propertyCache.clear();
     95            itemRefElements.clear();
     96            propertyNames.clear();
     97            itemRefElementPosition = 0;
     98            hasItemRefElements = false;
     99        }
     100
     101        void setItemRefElements(const Vector<Element*>& elements)
     102        {
     103            itemRefElements = elements;
     104            hasItemRefElements = true;
     105        }
     106
     107        const Vector<Element*>& getItemRefElements()
     108        {
     109            return itemRefElements;
     110        }
     111
     112        void updateLength(unsigned len)
     113        {
     114            length = len;
     115            hasLength = true;
     116        }
     117
     118        void updatePropertyCache(Element* element, const AtomicString& propertyName)
     119        {
     120            if (!propertyNames)
     121                propertyNames = DOMStringList::create();
     122
     123            if (!propertyNames->contains(propertyName))
     124                propertyNames->append(propertyName);
     125
     126            Vector<Element*>* propertyResults = propertyCache.get(propertyName.impl());
     127            if (!propertyResults || !propertyResults->contains(element))
     128                append(propertyCache, propertyName, element);
     129        }
     130
     131        void updateCurrentItem(Element* element, unsigned pos, unsigned itemRefElementPos)
     132        {
     133            current = element;
     134            position = pos;
     135            itemRefElementPosition = itemRefElementPos;
     136        }
     137
     138        void resetPosition()
     139        {
     140            current = 0;
     141            position = 0;
     142            itemRefElementPosition = 0;
     143        }
     144
     145    } m_cache;
     146
    64147};
    65148
Note: See TracChangeset for help on using the changeset viewer.