1/* 2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) 3 * (C) 1999 Antti Koivisto (koivisto@kde.org) 4 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 5 * 6 * This library is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Library General Public 8 * License as published by the Free Software Foundation; either 9 * version 2 of the License, or (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 * Library General Public License for more details. 15 * 16 * You should have received a copy of the GNU Library General Public License 17 * along with this library; see the file COPYING.LIB. If not, write to 18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 19 * Boston, MA 02110-1301, USA. 20 * 21 */ 22 23#include "config.h" 24#include "HTMLCollection.h" 25 26#include "ElementTraversal.h" 27#include "HTMLDocument.h" 28#include "HTMLNameCollection.h" 29#include "HTMLNames.h" 30#include "HTMLObjectElement.h" 31#include "HTMLOptionElement.h" 32#include "NodeRareData.h" 33 34namespace WebCore { 35 36using namespace HTMLNames; 37 38static bool shouldOnlyIncludeDirectChildren(CollectionType type) 39{ 40 switch (type) { 41 case DocAll: 42 case DocAnchors: 43 case DocApplets: 44 case DocEmbeds: 45 case DocForms: 46 case DocImages: 47 case DocLinks: 48 case DocScripts: 49 case DocumentNamedItems: 50 case MapAreas: 51 case TableRows: 52 case SelectOptions: 53 case SelectedOptions: 54 case DataListOptions: 55 case WindowNamedItems: 56 case FormControls: 57 return false; 58 case NodeChildren: 59 case TRCells: 60 case TSectionRows: 61 case TableTBodies: 62 return true; 63 } 64 ASSERT_NOT_REACHED(); 65 return false; 66} 67 68static HTMLCollection::RootType rootTypeFromCollectionType(CollectionType type) 69{ 70 switch (type) { 71 case DocImages: 72 case DocApplets: 73 case DocEmbeds: 74 case DocForms: 75 case DocLinks: 76 case DocAnchors: 77 case DocScripts: 78 case DocAll: 79 case WindowNamedItems: 80 case DocumentNamedItems: 81 case FormControls: 82 return HTMLCollection::IsRootedAtDocument; 83 case NodeChildren: 84 case TableTBodies: 85 case TSectionRows: 86 case TableRows: 87 case TRCells: 88 case SelectOptions: 89 case SelectedOptions: 90 case DataListOptions: 91 case MapAreas: 92 return HTMLCollection::IsRootedAtNode; 93 } 94 ASSERT_NOT_REACHED(); 95 return HTMLCollection::IsRootedAtNode; 96} 97 98static NodeListInvalidationType invalidationTypeExcludingIdAndNameAttributes(CollectionType type) 99{ 100 switch (type) { 101 case DocImages: 102 case DocEmbeds: 103 case DocForms: 104 case DocScripts: 105 case DocAll: 106 case NodeChildren: 107 case TableTBodies: 108 case TSectionRows: 109 case TableRows: 110 case TRCells: 111 case SelectOptions: 112 case MapAreas: 113 return DoNotInvalidateOnAttributeChanges; 114 case DocApplets: 115 case SelectedOptions: 116 case DataListOptions: 117 // FIXME: We can do better some day. 118 return InvalidateOnAnyAttrChange; 119 case DocAnchors: 120 return InvalidateOnNameAttrChange; 121 case DocLinks: 122 return InvalidateOnHRefAttrChange; 123 case WindowNamedItems: 124 return InvalidateOnIdNameAttrChange; 125 case DocumentNamedItems: 126 return InvalidateOnIdNameAttrChange; 127 case FormControls: 128 return InvalidateForFormControls; 129 } 130 ASSERT_NOT_REACHED(); 131 return DoNotInvalidateOnAttributeChanges; 132} 133 134HTMLCollection::HTMLCollection(ContainerNode& ownerNode, CollectionType type, ElementTraversalType traversalType) 135 : m_ownerNode(ownerNode) 136 , m_indexCache(*this) 137 , m_collectionType(type) 138 , m_invalidationType(invalidationTypeExcludingIdAndNameAttributes(type)) 139 , m_rootType(rootTypeFromCollectionType(type)) 140 , m_shouldOnlyIncludeDirectChildren(shouldOnlyIncludeDirectChildren(type)) 141 , m_usesCustomForwardOnlyTraversal(traversalType == CustomForwardOnlyTraversal) 142{ 143 ASSERT(m_rootType == static_cast<unsigned>(rootTypeFromCollectionType(type))); 144 ASSERT(m_invalidationType == static_cast<unsigned>(invalidationTypeExcludingIdAndNameAttributes(type))); 145 ASSERT(m_collectionType == static_cast<unsigned>(type)); 146} 147 148PassRef<HTMLCollection> HTMLCollection::create(ContainerNode& base, CollectionType type) 149{ 150 return adoptRef(*new HTMLCollection(base, type)); 151} 152 153HTMLCollection::~HTMLCollection() 154{ 155 if (m_indexCache.hasValidCache(*this)) 156 document().unregisterCollection(*this); 157 if (hasNamedElementCache()) 158 document().collectionWillClearIdNameMap(*this); 159 // HTMLNameCollection removes cache by itself. 160 if (type() != WindowNamedItems && type() != DocumentNamedItems) 161 ownerNode().nodeLists()->removeCachedCollection(this); 162} 163 164ContainerNode& HTMLCollection::rootNode() const 165{ 166 if (isRootedAtDocument() && ownerNode().inDocument()) 167 return ownerNode().document(); 168 169 return ownerNode(); 170} 171 172inline bool isMatchingElement(const HTMLCollection& htmlCollection, Element& element) 173{ 174 CollectionType type = htmlCollection.type(); 175 if (!element.isHTMLElement() && !(type == DocAll || type == NodeChildren || type == WindowNamedItems)) 176 return false; 177 178 switch (type) { 179 case DocImages: 180 return element.hasTagName(imgTag); 181 case DocScripts: 182 return element.hasTagName(scriptTag); 183 case DocForms: 184 return element.hasTagName(formTag); 185 case TableTBodies: 186 return element.hasTagName(tbodyTag); 187 case TRCells: 188 return element.hasTagName(tdTag) || element.hasTagName(thTag); 189 case TSectionRows: 190 return element.hasTagName(trTag); 191 case SelectOptions: 192 return element.hasTagName(optionTag); 193 case SelectedOptions: 194 return element.hasTagName(optionTag) && toHTMLOptionElement(element).selected(); 195 case DataListOptions: 196 if (element.hasTagName(optionTag)) { 197 HTMLOptionElement& option = toHTMLOptionElement(element); 198 if (!option.isDisabledFormControl() && !option.value().isEmpty()) 199 return true; 200 } 201 return false; 202 case MapAreas: 203 return element.hasTagName(areaTag); 204 case DocApplets: 205 return element.hasTagName(appletTag) || (element.hasTagName(objectTag) && toHTMLObjectElement(element).containsJavaApplet()); 206 case DocEmbeds: 207 return element.hasTagName(embedTag); 208 case DocLinks: 209 return (element.hasTagName(aTag) || element.hasTagName(areaTag)) && element.fastHasAttribute(hrefAttr); 210 case DocAnchors: 211 return element.hasTagName(aTag) && element.fastHasAttribute(nameAttr); 212 case DocAll: 213 case NodeChildren: 214 return true; 215 case DocumentNamedItems: 216 return static_cast<const DocumentNameCollection&>(htmlCollection).nodeMatches(&element); 217 case WindowNamedItems: 218 return static_cast<const WindowNameCollection&>(htmlCollection).nodeMatches(&element); 219 case FormControls: 220 case TableRows: 221 break; 222 } 223 ASSERT_NOT_REACHED(); 224 return false; 225} 226 227static Element* previousElement(ContainerNode& base, Element* previous, bool onlyIncludeDirectChildren) 228{ 229 return onlyIncludeDirectChildren ? ElementTraversal::previousSibling(previous) : ElementTraversal::previous(previous, &base); 230} 231 232ALWAYS_INLINE Element* HTMLCollection::iterateForPreviousElement(Element* current) const 233{ 234 bool onlyIncludeDirectChildren = m_shouldOnlyIncludeDirectChildren; 235 ContainerNode& rootNode = this->rootNode(); 236 for (; current; current = previousElement(rootNode, current, onlyIncludeDirectChildren)) { 237 if (isMatchingElement(*this, *current)) 238 return current; 239 } 240 return nullptr; 241} 242 243inline Element* firstMatchingElement(const HTMLCollection& collection, ContainerNode& root) 244{ 245 Element* element = ElementTraversal::firstWithin(&root); 246 while (element && !isMatchingElement(collection, *element)) 247 element = ElementTraversal::next(element, &root); 248 return element; 249} 250 251inline Element* nextMatchingElement(const HTMLCollection& collection, Element* current, ContainerNode& root) 252{ 253 do { 254 current = ElementTraversal::next(current, &root); 255 } while (current && !isMatchingElement(collection, *current)); 256 return current; 257} 258 259unsigned HTMLCollection::length() const 260{ 261 return m_indexCache.nodeCount(*this); 262} 263 264Node* HTMLCollection::item(unsigned offset) const 265{ 266 return m_indexCache.nodeAt(*this, offset); 267} 268 269static inline bool nameShouldBeVisibleInDocumentAll(HTMLElement& element) 270{ 271 // The document.all collection returns only certain types of elements by name, 272 // although it returns any type of element by id. 273 return element.hasTagName(appletTag) 274 || element.hasTagName(embedTag) 275 || element.hasTagName(formTag) 276 || element.hasTagName(imgTag) 277 || element.hasTagName(inputTag) 278 || element.hasTagName(objectTag) 279 || element.hasTagName(selectTag); 280} 281 282inline Element* firstMatchingChildElement(const HTMLCollection& nodeList, ContainerNode& root) 283{ 284 Element* element = ElementTraversal::firstWithin(&root); 285 while (element && !isMatchingElement(nodeList, *element)) 286 element = ElementTraversal::nextSibling(element); 287 return element; 288} 289 290inline Element* nextMatchingSiblingElement(const HTMLCollection& nodeList, Element* current) 291{ 292 do { 293 current = ElementTraversal::nextSibling(current); 294 } while (current && !isMatchingElement(nodeList, *current)); 295 return current; 296} 297 298inline Element* HTMLCollection::firstElement(ContainerNode& root) const 299{ 300 if (usesCustomForwardOnlyTraversal()) 301 return customElementAfter(nullptr); 302 if (m_shouldOnlyIncludeDirectChildren) 303 return firstMatchingChildElement(*this, root); 304 return firstMatchingElement(*this, root); 305} 306 307inline Element* HTMLCollection::traverseForward(Element& current, unsigned count, unsigned& traversedCount, ContainerNode& root) const 308{ 309 Element* element = ¤t; 310 if (usesCustomForwardOnlyTraversal()) { 311 for (traversedCount = 0; traversedCount < count; ++traversedCount) { 312 element = customElementAfter(element); 313 if (!element) 314 return nullptr; 315 } 316 return element; 317 } 318 if (m_shouldOnlyIncludeDirectChildren) { 319 for (traversedCount = 0; traversedCount < count; ++traversedCount) { 320 element = nextMatchingSiblingElement(*this, element); 321 if (!element) 322 return nullptr; 323 } 324 return element; 325 } 326 for (traversedCount = 0; traversedCount < count; ++traversedCount) { 327 element = nextMatchingElement(*this, element, root); 328 if (!element) 329 return nullptr; 330 } 331 return element; 332} 333 334Element* HTMLCollection::collectionBegin() const 335{ 336 return firstElement(rootNode()); 337} 338 339Element* HTMLCollection::collectionLast() const 340{ 341 // FIXME: This should be optimized similarly to the forward case. 342 auto& root = rootNode(); 343 Element* last = m_shouldOnlyIncludeDirectChildren ? ElementTraversal::lastChild(&root) : ElementTraversal::lastWithin(&root); 344 return iterateForPreviousElement(last); 345} 346 347void HTMLCollection::collectionTraverseForward(Element*& current, unsigned count, unsigned& traversedCount) const 348{ 349 current = traverseForward(*current, count, traversedCount, rootNode()); 350} 351 352void HTMLCollection::collectionTraverseBackward(Element*& current, unsigned count) const 353{ 354 // FIXME: This should be optimized similarly to the forward case. 355 auto& root = rootNode(); 356 if (m_shouldOnlyIncludeDirectChildren) { 357 for (; count && current ; --count) 358 current = iterateForPreviousElement(ElementTraversal::previousSibling(current)); 359 return; 360 } 361 for (; count && current ; --count) 362 current = iterateForPreviousElement(ElementTraversal::previous(current, &root)); 363} 364 365void HTMLCollection::invalidateCache(Document& document) const 366{ 367 if (m_indexCache.hasValidCache(*this)) { 368 document.unregisterCollection(const_cast<HTMLCollection&>(*this)); 369 m_indexCache.invalidate(*this); 370 } 371 if (hasNamedElementCache()) 372 invalidateNamedElementCache(document); 373} 374 375void HTMLCollection::invalidateNamedElementCache(Document& document) const 376{ 377 ASSERT(hasNamedElementCache()); 378 document.collectionWillClearIdNameMap(*this); 379 m_namedElementCache = nullptr; 380} 381 382Node* HTMLCollection::namedItem(const AtomicString& name) const 383{ 384 // http://msdn.microsoft.com/workshop/author/dhtml/reference/methods/nameditem.asp 385 // This method first searches for an object with a matching id 386 // attribute. If a match is not found, the method then searches for an 387 // object with a matching name attribute, but only on those elements 388 // that are allowed a name attribute. 389 390 if (name.isEmpty()) 391 return 0; 392 393 ContainerNode& root = rootNode(); 394 if (!usesCustomForwardOnlyTraversal() && root.isInTreeScope()) { 395 TreeScope& treeScope = root.treeScope(); 396 Element* candidate = 0; 397 if (treeScope.hasElementWithId(*name.impl())) { 398 if (!treeScope.containsMultipleElementsWithId(name)) 399 candidate = treeScope.getElementById(name); 400 } else if (treeScope.hasElementWithName(*name.impl())) { 401 if (!treeScope.containsMultipleElementsWithName(name)) { 402 candidate = treeScope.getElementByName(name); 403 if (candidate && type() == DocAll && (!candidate->isHTMLElement() || !nameShouldBeVisibleInDocumentAll(toHTMLElement(*candidate)))) 404 candidate = 0; 405 } 406 } else 407 return 0; 408 409 if (candidate && isMatchingElement(*this, *candidate) 410 && (m_shouldOnlyIncludeDirectChildren ? candidate->parentNode() == &root : candidate->isDescendantOf(&root))) 411 return candidate; 412 } 413 414 // The pathological case. We need to walk the entire subtree. 415 updateNamedElementCache(); 416 ASSERT(m_namedElementCache); 417 418 if (const Vector<Element*>* idResults = m_namedElementCache->findElementsWithId(name)) { 419 if (idResults->size()) 420 return idResults->at(0); 421 } 422 423 if (const Vector<Element*>* nameResults = m_namedElementCache->findElementsWithName(name)) { 424 if (nameResults->size()) 425 return nameResults->at(0); 426 } 427 428 return 0; 429} 430 431void HTMLCollection::updateNamedElementCache() const 432{ 433 if (hasNamedElementCache()) 434 return; 435 436 437 auto cache = std::make_unique<CollectionNamedElementCache>(); 438 439 unsigned size = m_indexCache.nodeCount(*this); 440 for (unsigned i = 0; i < size; i++) { 441 Element* element = m_indexCache.nodeAt(*this, i); 442 ASSERT(element); 443 const AtomicString& idAttrVal = element->getIdAttribute(); 444 if (!idAttrVal.isEmpty()) 445 cache->appendIdCache(idAttrVal, element); 446 if (!element->isHTMLElement()) 447 continue; 448 const AtomicString& nameAttrVal = element->getNameAttribute(); 449 if (!nameAttrVal.isEmpty() && idAttrVal != nameAttrVal && (type() != DocAll || nameShouldBeVisibleInDocumentAll(toHTMLElement(*element)))) 450 cache->appendNameCache(nameAttrVal, element); 451 } 452 453 cache->didPopulate(); 454 setNameItemCache(WTF::move(cache)); 455} 456 457bool HTMLCollection::hasNamedItem(const AtomicString& name) const 458{ 459 // FIXME: We can do better when there are multiple elements of the same name. 460 return namedItem(name); 461} 462 463void HTMLCollection::namedItems(const AtomicString& name, Vector<Ref<Element>>& result) const 464{ 465 ASSERT(result.isEmpty()); 466 if (name.isEmpty()) 467 return; 468 469 updateNamedElementCache(); 470 ASSERT(m_namedElementCache); 471 472 const Vector<Element*>* idResults = m_namedElementCache->findElementsWithId(name); 473 const Vector<Element*>* nameResults = m_namedElementCache->findElementsWithName(name); 474 475 for (unsigned i = 0; idResults && i < idResults->size(); ++i) 476 result.append(*idResults->at(i)); 477 478 for (unsigned i = 0; nameResults && i < nameResults->size(); ++i) 479 result.append(*nameResults->at(i)); 480} 481 482PassRefPtr<NodeList> HTMLCollection::tags(const String& name) 483{ 484 return ownerNode().getElementsByTagName(name); 485} 486 487} // namespace WebCore 488