Changeset 150187 in webkit


Ignore:
Timestamp:
May 16, 2013 11:04:13 AM (11 years ago)
Author:
rniwa@webkit.org
Message:

DocumentOrderedMap doesn't need to have two HashMaps
​https://bugs.webkit.org/show_bug.cgi?id=116167

Reviewed by Geoffrey Garen.

Previously, we had two hash maps: m_map and m_duplicateCounts in DocumentOrderedMap to keep track
of the first element and the number of duplicates for a given name. This patch simplifies this structure
by having a single hash map that contains both the pointer and the number of duplicates.

In addition, this patch fixes a regression introduced in r149652 that window and document name maps
were not updated for some elements inside a SVG use element, and makes use of the newly added list of
the matching elements in SelectorQuery.

  • dom/DocumentOrderedMap.cpp:

(WebCore::DocumentOrderedMap::clear): Updated to use the new hash map.
(WebCore::DocumentOrderedMap::add): Ditto.
(WebCore::DocumentOrderedMap::remove): Ditto.
(WebCore::DocumentOrderedMap::get): Ditto.
(WebCore::DocumentOrderedMap::getAllElementsById): Added.

  • dom/DocumentOrderedMap.h:

(WebCore::DocumentOrderedMap::MapEntry::MapEntry): Added.
(WebCore::DocumentOrderedMap::containsSingle): Updated to use new hash map.
(WebCore::DocumentOrderedMap::contains): Ditto.
(WebCore::DocumentOrderedMap::containsMultiple): Ditto.

  • dom/Element.cpp:

(WebCore::Element::insertedInto): This function didn't add this element to window and document's name maps
if the element had already been inserted into a tree scope, and the current call was inserting an ancestor
of the tree scope into the document. We were exiting early per scope != treeScope().

Fixed the bug by splitting updateId into two functions updateIdForTreeScope and updateIdForDocument.
The former is called when this element is inserted into a new tree scope, and the latter is called when
this element is inserted into a HTML document even if it had already been inside some tree scope.

(WebCore::Element::removedFrom): This function didn't remove this element from tree scope's id maps if
the tree scope wasn't a document. Fixed the bug by simply checking that the removal happens beneath the
current tree scope.
(WebCore::Element::updateName):
(WebCore::Element::updateNameForTreeScope): Renamed from updateName.
(WebCore::Element::updateNameForDocument): Extracted from updateName.
(WebCore::Element::updateId):
(WebCore::Element::updateIdForTreeScope): Renamed from updateId.
(WebCore::Element::updateIdForDocument): Extracted from updateId.

  • dom/Element.h:
  • dom/SelectorQuery.cpp:

(WebCore::SelectorDataList::canUseIdLookup): Refactored to return the id subselector instead of checking if
the first subselector happens to be matching an id.
(WebCore::SelectorDataList::execute): Use the subselector canUseIdLookup returned. Also make use of newly
added getAllElementsById when there are multiple matching elements for a given id.

  • dom/SelectorQuery.h:
  • dom/TreeScope.cpp:

(WebCore::TreeScope::getAllElementsById): Added.

  • dom/TreeScope.h:
Location:
trunk/Source/WebCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r150183 r150187  
     12013-05-15  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        DocumentOrderedMap doesn't need to have two HashMaps
     4        https://bugs.webkit.org/show_bug.cgi?id=116167
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        Previously, we had two hash maps: m_map and m_duplicateCounts in DocumentOrderedMap to keep track
     9        of the first element and the number of duplicates for a given name. This patch simplifies this structure
     10        by having a single hash map that contains both the pointer and the number of duplicates.
     11
     12        In addition, this patch fixes a regression introduced in r149652 that window and document name maps
     13        were not updated for some elements inside a SVG use element, and makes use of the newly added list of
     14        the matching elements in SelectorQuery.
     15
     16        * dom/DocumentOrderedMap.cpp:
     17        (WebCore::DocumentOrderedMap::clear): Updated to use the new hash map.
     18        (WebCore::DocumentOrderedMap::add): Ditto.
     19        (WebCore::DocumentOrderedMap::remove): Ditto.
     20        (WebCore::DocumentOrderedMap::get): Ditto.
     21        (WebCore::DocumentOrderedMap::getAllElementsById): Added.
     22
     23        * dom/DocumentOrderedMap.h:
     24
     25        (WebCore::DocumentOrderedMap::MapEntry::MapEntry): Added.
     26        (WebCore::DocumentOrderedMap::containsSingle): Updated to use new hash map.
     27        (WebCore::DocumentOrderedMap::contains): Ditto.
     28        (WebCore::DocumentOrderedMap::containsMultiple): Ditto.
     29
     30        * dom/Element.cpp:
     31        (WebCore::Element::insertedInto): This function didn't add this element to window and document's name maps
     32        if the element had already been inserted into a tree scope, and the current call was inserting an ancestor
     33        of the tree scope into the document. We were exiting early per scope != treeScope().
     34
     35        Fixed the bug by splitting updateId into two functions updateIdForTreeScope and updateIdForDocument.
     36        The former is called when this element is inserted into a new tree scope, and the latter is called when
     37        this element is inserted into a HTML document even if it had already been inside some tree scope.
     38
     39        (WebCore::Element::removedFrom): This function didn't remove this element from tree scope's id maps if
     40        the tree scope wasn't a document. Fixed the bug by simply checking that the removal happens beneath the
     41        current tree scope.
     42        (WebCore::Element::updateName):
     43        (WebCore::Element::updateNameForTreeScope): Renamed from updateName.
     44        (WebCore::Element::updateNameForDocument): Extracted from updateName.
     45        (WebCore::Element::updateId):
     46        (WebCore::Element::updateIdForTreeScope): Renamed from updateId.
     47        (WebCore::Element::updateIdForDocument): Extracted from updateId.
     48
     49        * dom/Element.h:
     50
     51        * dom/SelectorQuery.cpp:
     52        (WebCore::SelectorDataList::canUseIdLookup): Refactored to return the id subselector instead of checking if
     53        the first subselector happens to be matching an id.
     54        (WebCore::SelectorDataList::execute): Use the subselector canUseIdLookup returned. Also make use of newly
     55        added getAllElementsById when there are multiple matching elements for a given id.
     56
     57        * dom/SelectorQuery.h:
     58
     59        * dom/TreeScope.cpp:
     60        (WebCore::TreeScope::getAllElementsById): Added.
     61
     62        * dom/TreeScope.h:
     63
    1642013-05-15  Darin Adler  <darin@apple.com>
    265

  • trunk/Source/WebCore/dom/DocumentOrderedMap.cpp

    r149652 r150187  
    8181{
    8282    m_map.clear();
    83     m_duplicateCounts.clear();
    8483}
    8584
    … …  
    8988    ASSERT(element);
    9089
    91     if (!m_duplicateCounts.contains(key)) {
    92         // Fast path. The key is not already in m_duplicateCounts, so we assume that it's
    93         // also not already in m_map and try to add it. If that add succeeds, we're done.
    94         Map::AddResult addResult = m_map.add(key, element);
    95         if (addResult.isNewEntry)
    96             return;
    97 
    98         // The add failed, so this key was already cached in m_map.
    99         // There are multiple elements with this key. Remove the m_map
    100         // cache for this key so get searches for it next time it is called.
    101         m_map.remove(addResult.iterator);
    102         m_duplicateCounts.add(key);
     90    Map::AddResult addResult = m_map.add(key, MapEntry(element));
     91    if (addResult.isNewEntry)
     92        return;
     93
     94    MapEntry& entry = addResult.iterator->value;
     95    ASSERT(entry.count);
     96    entry.element = 0;
     97    entry.count++;
     98    entry.orderedList.clear();
     99}
     100
     101void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
     102{
     103    ASSERT(key);
     104    ASSERT(element);
     105
     106    m_map.checkConsistency();
     107    Map::iterator it = m_map.find(key);
     108    ASSERT(it != m_map.end());
     109    MapEntry& entry = it->value;
     110
     111    ASSERT(entry.count);
     112    if (entry.count == 1) {
     113        ASSERT(!entry.element || entry.element == element);
     114        m_map.remove(it);
    103115    } else {
    104         // There are multiple elements with this key. Remove the m_map
    105         // cache for this key so get will search for it next time it is called.
    106         Map::iterator cachedItem = m_map.find(key);
    107         if (cachedItem != m_map.end()) {
    108             m_map.remove(cachedItem);
    109             m_duplicateCounts.add(key);
    110         }
     116        if (entry.element == element)
     117            entry.element = 0;
     118        entry.count--;
     119        entry.orderedList.clear(); // FIXME: Remove the element instead if there are only few items left.
    111120    }
    112 
    113     m_duplicateCounts.add(key);
    114 }
    115 
    116 void DocumentOrderedMap::remove(AtomicStringImpl* key, Element* element)
    117 {
    118     ASSERT(key);
    119     ASSERT(element);
    120 
    121     m_map.checkConsistency();
    122     Map::iterator cachedItem = m_map.find(key);
    123     if (cachedItem != m_map.end() && cachedItem->value == element)
    124         m_map.remove(cachedItem);
    125     else
    126         m_duplicateCounts.remove(key);
    127121}
    128122
    … …  
    135129    m_map.checkConsistency();
    136130
    137     Element* element = m_map.get(key);
    138     if (element)
     131    Map::iterator it = m_map.find(key);
     132    if (it == m_map.end())
     133        return 0;
     134
     135    MapEntry& entry = it->value;
     136    ASSERT(entry.count);
     137    if (entry.element)
     138        return entry.element;
     139
     140    // We know there's at least one node that matches; iterate to find the first one.
     141    for (Element* element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
     142        if (!keyMatches(key, element))
     143            continue;
     144        entry.element = element;
    139145        return element;
    140 
    141     if (m_duplicateCounts.contains(key)) {
    142         // We know there's at least one node that matches; iterate to find the first one.
    143         for (element = ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
    144             if (!keyMatches(key, element))
     146    }
     147    ASSERT_NOT_REACHED();
     148    return 0;
     149}
     150
     151Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const
     152{
     153    return get<keyMatchesId>(key, scope);
     154}
     155
     156Element* DocumentOrderedMap::getElementByName(AtomicStringImpl* key, const TreeScope* scope) const
     157{
     158    return get<keyMatchesName>(key, scope);
     159}
     160
     161Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const
     162{
     163    return get<keyMatchesMapName>(key, scope);
     164}
     165
     166Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const
     167{
     168    return get<keyMatchesLowercasedMapName>(key, scope);
     169}
     170
     171Element* DocumentOrderedMap::getElementByLabelForAttribute(AtomicStringImpl* key, const TreeScope* scope) const
     172{
     173    return get<keyMatchesLabelForAttribute>(key, scope);
     174}
     175
     176Element* DocumentOrderedMap::getElementByWindowNamedItem(AtomicStringImpl* key, const TreeScope* scope) const
     177{
     178    return get<keyMatchesWindowNamedItem>(key, scope);
     179}
     180
     181Element* DocumentOrderedMap::getElementByDocumentNamedItem(AtomicStringImpl* key, const TreeScope* scope) const
     182{
     183    return get<keyMatchesDocumentNamedItem>(key, scope);
     184}
     185
     186const Vector<Element*>* DocumentOrderedMap::getAllElementsById(AtomicStringImpl* key, const TreeScope* scope) const
     187{
     188    ASSERT(key);
     189    ASSERT(scope);
     190
     191    m_map.checkConsistency();
     192
     193    Map::iterator it = m_map.find(key);
     194    if (it == m_map.end())
     195        return 0;
     196
     197    MapEntry& entry = it->value;
     198    ASSERT(entry.count);
     199    if (!entry.count)
     200        return 0;
     201
     202    if (entry.orderedList.isEmpty()) {
     203        entry.orderedList.reserveCapacity(entry.count);
     204        for (Element* element = entry.element ? entry.element : ElementTraversal::firstWithin(scope->rootNode()); element; element = ElementTraversal::next(element)) {
     205            if (!keyMatchesId(key, element))
    145206                continue;
    146             m_duplicateCounts.remove(key);
    147             m_map.set(key, element);
    148             return element;
     207            entry.orderedList.append(element);
    149208        }
    150         ASSERT_NOT_REACHED();
     209        ASSERT(entry.orderedList.size() == entry.count);
    151210    }
    152211
    153     return 0;
    154 }
    155 
    156 Element* DocumentOrderedMap::getElementById(AtomicStringImpl* key, const TreeScope* scope) const
    157 {
    158     return get<keyMatchesId>(key, scope);
    159 }
    160 
    161 Element* DocumentOrderedMap::getElementByName(AtomicStringImpl* key, const TreeScope* scope) const
    162 {
    163     return get<keyMatchesName>(key, scope);
    164 }
    165 
    166 Element* DocumentOrderedMap::getElementByMapName(AtomicStringImpl* key, const TreeScope* scope) const
    167 {
    168     return get<keyMatchesMapName>(key, scope);
    169 }
    170 
    171 Element* DocumentOrderedMap::getElementByLowercasedMapName(AtomicStringImpl* key, const TreeScope* scope) const
    172 {
    173     return get<keyMatchesLowercasedMapName>(key, scope);
    174 }
    175 
    176 Element* DocumentOrderedMap::getElementByLabelForAttribute(AtomicStringImpl* key, const TreeScope* scope) const
    177 {
    178     return get<keyMatchesLabelForAttribute>(key, scope);
    179 }
    180 
    181 Element* DocumentOrderedMap::getElementByWindowNamedItem(AtomicStringImpl* key, const TreeScope* scope) const
    182 {
    183     return get<keyMatchesWindowNamedItem>(key, scope);
    184 }
    185 
    186 Element* DocumentOrderedMap::getElementByDocumentNamedItem(AtomicStringImpl* key, const TreeScope* scope) const
    187 {
    188     return get<keyMatchesDocumentNamedItem>(key, scope);
     212    return &entry.orderedList;
    189213}
    190214

  • trunk/Source/WebCore/dom/DocumentOrderedMap.h

    r149652 r150187  
    3434#include <wtf/HashCountedSet.h>
    3535#include <wtf/HashMap.h>
     36#include <wtf/Vector.h>
    3637#include <wtf/text/AtomicStringImpl.h>
    3738
    … …  
    5051    bool containsSingle(AtomicStringImpl*) const;
    5152    bool containsMultiple(AtomicStringImpl*) const;
     53
    5254    // concrete instantiations of the get<>() method template
    5355    Element* getElementById(AtomicStringImpl*, const TreeScope*) const;
    … …  
    5961    Element* getElementByDocumentNamedItem(AtomicStringImpl*, const TreeScope*) const;
    6062
     63    const Vector<Element*>* getAllElementsById(AtomicStringImpl*, const TreeScope*) const;
     64
    6165    void checkConsistency() const;
    6266
    … …  
    6468    template<bool keyMatches(AtomicStringImpl*, Element*)> Element* get(AtomicStringImpl*, const TreeScope*) const;
    6569
    66     typedef HashMap<AtomicStringImpl*, Element*> Map;
     70    struct MapEntry {
     71        MapEntry()
     72            : element(0)
     73            , count(0)
     74        { }
     75        explicit MapEntry(Element* firstElement)
     76            : element(firstElement)
     77            , count(1)
     78        { }
    6779
    68     // We maintain the invariant that m_duplicateCounts is the count of all elements with a given key
    69     // excluding the one referenced in m_map, if any. This means it one less than the total count
    70     // when the first node with a given key is cached, otherwise the same as the total count.
     80        Element* element;
     81        unsigned count;
     82        Vector<Element*> orderedList;
     83    };
     84
     85    typedef HashMap<AtomicStringImpl*, MapEntry> Map;
     86
    7187    mutable Map m_map;
    72     mutable HashCountedSet<AtomicStringImpl*> m_duplicateCounts;
    7388};
    7489
    7590inline bool DocumentOrderedMap::containsSingle(AtomicStringImpl* id) const
    7691{
    77     return (m_map.contains(id) ? 1 : 0) + m_duplicateCounts.count(id) == 1;
     92    Map::const_iterator it = m_map.find(id);
     93    return it != m_map.end() && it->value.count == 1;
    7894}
    7995
    8096inline bool DocumentOrderedMap::contains(AtomicStringImpl* id) const
    8197{
    82     return m_map.contains(id) || m_duplicateCounts.contains(id);
     98    return m_map.contains(id);
    8399}
    84100
    85101inline bool DocumentOrderedMap::containsMultiple(AtomicStringImpl* id) const
    86102{
    87     return (m_map.contains(id) ? 1 : 0) + m_duplicateCounts.count(id) > 1;
     103    Map::const_iterator it = m_map.find(id);
     104    return it != m_map.end() && it->value.count > 1;
    88105}
    89106

  • trunk/Source/WebCore/dom/Element.cpp

    r150072 r150187  
    11511151Node::InsertionNotificationRequest Element::insertedInto(ContainerNode* insertionPoint)
    11521152{
     1153    bool wasInDocument = inDocument();
    11531154    // need to do superclass processing first so inDocument() is true
    11541155    // by the time we reach updateId
    11551156    ContainerNode::insertedInto(insertionPoint);
     1157    ASSERT(!wasInDocument || inDocument());
    11561158
    11571159#if ENABLE(FULLSCREEN_API)
    … …  
    11721174        elementRareData()->clearClassListValueForQuirksMode();
    11731175
    1174     TreeScope* scope = insertionPoint->treeScope();
    1175     if (scope != treeScope())
    1176         return InsertionDone;
     1176    TreeScope* newScope = insertionPoint->treeScope();
     1177    HTMLDocument* newDocument = !wasInDocument && inDocument() && newScope->documentScope()->isHTMLDocument() ? toHTMLDocument(newScope->documentScope()) : 0;
     1178    if (newScope != treeScope())
     1179        newScope = 0;
    11771180
    11781181    const AtomicString& idValue = getIdAttribute();
    1179     if (!idValue.isNull())
    1180         updateId(scope, nullAtom, idValue, AlwaysUpdateHTMLDocumentNamedItemMaps);
     1182    if (!idValue.isNull()) {
     1183        if (newScope)
     1184            updateIdForTreeScope(newScope, nullAtom, idValue);
     1185        if (newDocument)
     1186            updateIdForDocument(newDocument, nullAtom, idValue, AlwaysUpdateHTMLDocumentNamedItemMaps);
     1187    }
    11811188
    11821189    const AtomicString& nameValue = getNameAttribute();
    1183     if (!nameValue.isNull())
    1184         updateName(scope, nullAtom, nameValue);
    1185 
    1186     if (hasTagName(labelTag)) {
    1187         if (scope->shouldCacheLabelsByForAttribute())
    1188             updateLabel(scope, nullAtom, fastGetAttribute(forAttr));
     1190    if (!nameValue.isNull()) {
     1191        if (newScope)
     1192            updateNameForTreeScope(newScope, nullAtom, nameValue);
     1193        if (newDocument)
     1194            updateNameForDocument(newDocument, nullAtom, nameValue);
     1195    }
     1196
     1197    if (newScope && hasTagName(labelTag)) {
     1198        if (newScope->shouldCacheLabelsByForAttribute())
     1199            updateLabel(newScope, nullAtom, fastGetAttribute(forAttr));
    11891200    }
    11901201
    … …  
    12181229    setSavedLayerScrollOffset(IntSize());
    12191230
    1220     if (insertionPoint->isInTreeScope() && treeScope() == document()) {
     1231    if (insertionPoint->isInTreeScope()) {
     1232        TreeScope* oldScope = insertionPoint->treeScope();
     1233        HTMLDocument* oldDocument = inDocument() && oldScope->documentScope()->isHTMLDocument() ? toHTMLDocument(oldScope->documentScope()) : 0;
     1234        if (oldScope != treeScope())
     1235            oldScope = 0;
     1236
    12211237        const AtomicString& idValue = getIdAttribute();
    1222         if (!idValue.isNull())
    1223             updateId(insertionPoint->treeScope(), idValue, nullAtom, AlwaysUpdateHTMLDocumentNamedItemMaps);
     1238        if (!idValue.isNull()) {
     1239            if (oldScope)
     1240                updateIdForTreeScope(oldScope, idValue, nullAtom);
     1241            if (oldDocument)
     1242                updateIdForDocument(oldDocument, idValue, nullAtom, AlwaysUpdateHTMLDocumentNamedItemMaps);
     1243        }
    12241244
    12251245        const AtomicString& nameValue = getNameAttribute();
    1226         if (!nameValue.isNull())
    1227             updateName(insertionPoint->treeScope(), nameValue, nullAtom);
    1228 
    1229         if (hasTagName(labelTag)) {
    1230             TreeScope* treeScope = insertionPoint->treeScope();
    1231             if (treeScope->shouldCacheLabelsByForAttribute())
    1232                 updateLabel(treeScope, fastGetAttribute(forAttr), nullAtom);
     1246        if (!nameValue.isNull()) {
     1247            if (oldScope)
     1248                updateNameForTreeScope(oldScope, nameValue, nullAtom);
     1249            if (oldDocument)
     1250                updateNameForDocument(oldDocument, nameValue, nullAtom);
     1251        }
     1252
     1253        if (oldScope && hasTagName(labelTag)) {
     1254            if (oldScope->shouldCacheLabelsByForAttribute())
     1255                updateLabel(oldScope, fastGetAttribute(forAttr), nullAtom);
    12331256        }
    12341257    }
    … …  
    26312654        return;
    26322655
    2633     updateName(treeScope(), oldName, newName);
    2634 }
    2635 
    2636 void Element::updateName(TreeScope* scope, const AtomicString& oldName, const AtomicString& newName)
     2656    updateNameForTreeScope(treeScope(), oldName, newName);
     2657
     2658    if (!inDocument())
     2659        return;
     2660    Document* htmlDocument = document();
     2661    if (!htmlDocument->isHTMLDocument())
     2662        return;
     2663    updateNameForDocument(toHTMLDocument(htmlDocument), oldName, newName);
     2664}
     2665
     2666void Element::updateNameForTreeScope(TreeScope* scope, const AtomicString& oldName, const AtomicString& newName)
    26372667{
    26382668    ASSERT(isInTreeScope());
    … …  
    26432673    if (!newName.isEmpty())
    26442674        scope->addElementByName(newName, this);
    2645 
    2646     if (!inDocument())
    2647         return;
    2648    
    2649     Document* ownerDocument = document();
    2650     if (!ownerDocument->isHTMLDocument())
    2651         return;
     2675}
     2676
     2677void Element::updateNameForDocument(HTMLDocument* document, const AtomicString& oldName, const AtomicString& newName)
     2678{
     2679    ASSERT(inDocument());
     2680    ASSERT(oldName != newName);
    26522681
    26532682    if (WindowNameCollection::nodeMatchesIfNameAttributeMatch(this)) {
    26542683        const AtomicString& id = WindowNameCollection::nodeMatchesIfIdAttributeMatch(this) ? getIdAttribute() : nullAtom;
    26552684        if (!oldName.isEmpty() && oldName != id)
    2656             toHTMLDocument(ownerDocument)->windowNamedItemMap().remove(oldName.impl(), this);
     2685            document->windowNamedItemMap().remove(oldName.impl(), this);
    26572686        if (!newName.isEmpty() && newName != id)
    2658             toHTMLDocument(ownerDocument)->windowNamedItemMap().add(newName.impl(), this);
     2687            document->windowNamedItemMap().add(newName.impl(), this);
    26592688    }
    26602689
    … …  
    26622691        const AtomicString& id = DocumentNameCollection::nodeMatchesIfIdAttributeMatch(this) ? getIdAttribute() : nullAtom;
    26632692        if (!oldName.isEmpty() && oldName != id)
    2664             toHTMLDocument(ownerDocument)->documentNamedItemMap().remove(oldName.impl(), this);
     2693            document->documentNamedItemMap().remove(oldName.impl(), this);
    26652694        if (!newName.isEmpty() && newName != id)
    2666             toHTMLDocument(ownerDocument)->documentNamedItemMap().add(newName.impl(), this);
     2695            document->documentNamedItemMap().add(newName.impl(), this);
    26672696    }
    26682697}
    … …  
    26762705        return;
    26772706
    2678     updateId(treeScope(), oldId, newId, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute);
    2679 }
    2680 
    2681 void Element::updateId(TreeScope* scope, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition condition)
     2707    updateIdForTreeScope(treeScope(), oldId, newId);
     2708
     2709    if (!inDocument())
     2710        return;
     2711    Document* htmlDocument = document();
     2712    if (!htmlDocument->isHTMLDocument())
     2713        return;
     2714    updateIdForDocument(toHTMLDocument(htmlDocument), oldId, newId, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute);
     2715}
     2716
     2717void Element::updateIdForTreeScope(TreeScope* scope, const AtomicString& oldId, const AtomicString& newId)
    26822718{
    26832719    ASSERT(isInTreeScope());
    … …  
    26882724    if (!newId.isEmpty())
    26892725        scope->addElementById(newId, this);
    2690 
    2691     if (!inDocument())
    2692         return;
    2693 
    2694     Document* ownerDocument = document();
    2695     if (!ownerDocument->isHTMLDocument())
    2696         return;
     2726}
     2727
     2728void Element::updateIdForDocument(HTMLDocument* document, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition condition)
     2729{
     2730    ASSERT(inDocument());
     2731    ASSERT(oldId != newId);
    26972732
    26982733    if (WindowNameCollection::nodeMatchesIfIdAttributeMatch(this)) {
    26992734        const AtomicString& name = condition == UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute && WindowNameCollection::nodeMatchesIfNameAttributeMatch(this) ? getNameAttribute() : nullAtom;
    27002735        if (!oldId.isEmpty() && oldId != name)
    2701             toHTMLDocument(ownerDocument)->windowNamedItemMap().remove(oldId.impl(), this);
     2736            document->windowNamedItemMap().remove(oldId.impl(), this);
    27022737        if (!newId.isEmpty() && newId != name)
    2703             toHTMLDocument(ownerDocument)->windowNamedItemMap().add(newId.impl(), this);
     2738            document->windowNamedItemMap().add(newId.impl(), this);
    27042739    }
    27052740
    … …  
    27072742        const AtomicString& name = condition == UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute && DocumentNameCollection::nodeMatchesIfNameAttributeMatch(this) ? getNameAttribute() : nullAtom;
    27082743        if (!oldId.isEmpty() && oldId != name)
    2709             toHTMLDocument(ownerDocument)->documentNamedItemMap().remove(oldId.impl(), this);
     2744            document->documentNamedItemMap().remove(oldId.impl(), this);
    27102745        if (!newId.isEmpty() && newId != name)
    2711             toHTMLDocument(ownerDocument)->documentNamedItemMap().add(newId.impl(), this);
     2746            document->documentNamedItemMap().add(newId.impl(), this);
    27122747    }
    27132748}

  • trunk/Source/WebCore/dom/Element.h

    r150072 r150187  
    4343class ElementRareData;
    4444class ElementShadow;
     45class HTMLDocument;
    4546class ShareableElementData;
    4647class IntSize;
    … …  
    675676    void synchronizeAttribute(const AtomicString& localName) const;
    676677
     678    void updateName(const AtomicString& oldName, const AtomicString& newName);
     679    void updateNameForTreeScope(TreeScope*, const AtomicString& oldName, const AtomicString& newName);
     680    void updateNameForDocument(HTMLDocument*, const AtomicString& oldName, const AtomicString& newName);
    677681    void updateId(const AtomicString& oldId, const AtomicString& newId);
     682    void updateIdForTreeScope(TreeScope*, const AtomicString& oldId, const AtomicString& newId);
    678683    enum HTMLDocumentNamedItemMapsUpdatingCondition { AlwaysUpdateHTMLDocumentNamedItemMaps, UpdateHTMLDocumentNamedItemMapsOnlyIfDiffersFromNameAttribute };
    679     void updateId(TreeScope*, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition);
    680     void updateName(const AtomicString& oldName, const AtomicString& newName);
    681     void updateName(TreeScope*, const AtomicString& oldName, const AtomicString& newName);
     684    void updateIdForDocument(HTMLDocument*, const AtomicString& oldId, const AtomicString& newId, HTMLDocumentNamedItemMapsUpdatingCondition);
    682685    void updateLabel(TreeScope*, const AtomicString& oldForAttributeValue, const AtomicString& newForAttributeValue);
    683686

  • trunk/Source/WebCore/dom/SelectorQuery.cpp

    r150099 r150187  
    9999}
    100100
    101 bool SelectorDataList::canUseIdLookup(Node* rootNode) const
     101const CSSSelector* SelectorDataList::selectorForIdLookup(Node* rootNode) const
    102102{
    103103    // We need to return the matches in document order. To use id lookup while there is possiblity of multiple matches
    104104    // we would need to sort the results. For now, just traverse the document in that case.
    105105    if (m_selectors.size() != 1)
    106         return false;
    107     if (m_selectors[0].selector->m_match != CSSSelector::Id)
    108         return false;
     106        return 0;
    109107    if (!rootNode->inDocument())
    110         return false;
     108        return 0;
    111109    if (rootNode->document()->inQuirksMode())
    112         return false;
    113     if (rootNode->document()->containsMultipleElementsWithId(m_selectors[0].selector->value()))
    114         return false;
    115     return true;
     110        return 0;
     111    for (const CSSSelector* selector = m_selectors[0].selector; selector; selector = selector->tagHistory()) {
     112        if (selector->m_match == CSSSelector::Id)
     113            return selector;
     114        if (selector->relation() != CSSSelector::SubSelector)
     115            break;
     116    }
     117    return 0;
    116118}
    117119
    … …  
    125127void SelectorDataList::execute(Node* rootNode, Vector<RefPtr<Node> >& matchedElements) const
    126128{
    127     if (canUseIdLookup(rootNode)) {
     129    if (const CSSSelector* idSelector = selectorForIdLookup(rootNode)) {
    128130        ASSERT(m_selectors.size() == 1);
    129         const CSSSelector* selector = m_selectors[0].selector;
    130         Element* element = rootNode->treeScope()->getElementById(selector->value());
     131        const AtomicString& idToMatch = idSelector->value();
     132        if (UNLIKELY(rootNode->treeScope()->containsMultipleElementsWithId(idToMatch))) {
     133            const Vector<Element*>* elements = rootNode->treeScope()->getAllElementsById(idToMatch);
     134            ASSERT(elements);
     135            size_t count = elements->size();
     136            for (size_t i = 0; i < count; ++i) {
     137                Element* element = elements->at(i);
     138                if (selectorMatches(m_selectors[0], element, rootNode)) {
     139                    matchedElements.append(element);
     140                    if (firstMatchOnly)
     141                        return;
     142                }
     143            }
     144            return;
     145        }
     146        Element* element = rootNode->treeScope()->getElementById(idToMatch);
    131147        if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)))
    132148            return;

  • trunk/Source/WebCore/dom/SelectorQuery.h

    r148984 r150187  
    5959
    6060    bool selectorMatches(const SelectorData&, Element*, const Node*) const;
    61     bool canUseIdLookup(Node* rootNode) const;
     61    const CSSSelector* selectorForIdLookup(Node* rootNode) const;
    6262    template <bool firstMatchOnly>
    6363    void execute(Node* rootNode, Vector<RefPtr<Node> >&) const;

  • trunk/Source/WebCore/dom/TreeScope.cpp

    r149652 r150187  
    150150}
    151151
     152const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& elementId) const
     153{
     154    if (elementId.isEmpty())
     155        return 0;
     156    if (!m_elementsById)
     157        return 0;
     158    return m_elementsById->getAllElementsById(elementId.impl(), this);
     159}
     160
    152161void TreeScope::addElementById(const AtomicString& elementId, Element* element)
    153162{

  • trunk/Source/WebCore/dom/TreeScope.h

    r149652 r150187  
    5757    Node* focusedNode();
    5858    Element* getElementById(const AtomicString&) const;
     59    const Vector<Element*>* getAllElementsById(const AtomicString&) const;
    5960    bool hasElementWithId(AtomicStringImpl* id) const;
    6061    bool containsMultipleElementsWithId(const AtomicString& id) const;
Note: See TracChangeset for help on using the changeset viewer.