File indexing completed on 2024-04-28 11:39:36
0001 /* 0002 * This file is part of the DOM implementation for KDE. 0003 * 0004 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) 0005 * (C) 1999 Antti Koivisto (koivisto@kde.org) 0006 * (C) 2001 Dirk Mueller (mueller@kde.org) 0007 * (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved. 0008 * (C) 2005, 2009, 2010 Maksim Orlovich (maksim@kde.org) 0009 * (C) 2006 Allan Sandfeld Jensen (kde@carewolf.com) 0010 * (C) 2007 David Smith (catfish.man@gmail.com) 0011 * 0012 * This library is free software; you can redistribute it and/or 0013 * modify it under the terms of the GNU Library General Public 0014 * License as published by the Free Software Foundation; either 0015 * version 2 of the License, or (at your option) any later version. 0016 * 0017 * This library is distributed in the hope that it will be useful, 0018 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0020 * Library General Public License for more details. 0021 * 0022 * You should have received a copy of the GNU Library General Public License 0023 * along with this library; see the file COPYING.LIB. If not, write to 0024 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0025 * Boston, MA 02110-1301, USA. 0026 * 0027 * 0028 * The code for ClassNodeListImpl was originally licensed under the following terms 0029 * (but in this version is available only as above): 0030 * Redistribution and use in source and binary forms, with or without 0031 * modification, are permitted provided that the following conditions 0032 * are met: 0033 * 0034 * 1. Redistributions of source code must retain the above copyright 0035 * notice, this list of conditions and the following disclaimer. 0036 * 2. Redistributions in binary form must reproduce the above copyright 0037 * notice, this list of conditions and the following disclaimer in the 0038 * documentation and/or other materials provided with the distribution. 0039 * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 0040 * its contributors may be used to endorse or promote products derived 0041 * from this software without specific prior written permission. 0042 * 0043 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 0044 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 0045 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 0046 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 0047 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 0048 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 0049 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 0050 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 0051 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 0052 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 0053 */ 0054 0055 #include "dom_nodelistimpl.h" 0056 #include "dom_nodeimpl.h" 0057 #include "dom_docimpl.h" 0058 0059 using namespace DOM; 0060 using namespace khtml; 0061 0062 NodeImpl *DynamicNodeListImpl::item(unsigned long index) const 0063 { 0064 unsigned long requestIndex = index; 0065 0066 m_cache->updateNodeListInfo(m_refNode->document()); 0067 0068 NodeImpl *n = nullptr; 0069 bool usedCache = false; 0070 if (m_cache->current.node) { 0071 //Compute distance from the requested index to the cache node 0072 unsigned long cacheDist = qAbs(long(index) - long(m_cache->position)); 0073 0074 if (cacheDist < (unsigned long)index) { //Closer to the cached position 0075 usedCache = true; 0076 if (index >= m_cache->position) { //Go ahead 0077 unsigned long relIndex = index - m_cache->position; 0078 n = recursiveItem(m_refNode, m_cache->current.node, relIndex); 0079 } else { //Go backwards 0080 unsigned long relIndex = m_cache->position - index; 0081 n = recursiveItemBack(m_refNode, m_cache->current.node, relIndex); 0082 } 0083 } 0084 } 0085 0086 if (!usedCache) { 0087 n = recursiveItem(m_refNode, m_refNode->firstChild(), index); 0088 } 0089 0090 //We always update the cache state, to make starting iteration 0091 //where it was left off easy. 0092 m_cache->current.node = n; 0093 m_cache->position = requestIndex; 0094 return n; 0095 } 0096 0097 unsigned long DynamicNodeListImpl::length() const 0098 { 0099 m_cache->updateNodeListInfo(m_refNode->document()); 0100 if (!m_cache->hasLength) { 0101 m_cache->length = calcLength(m_refNode); 0102 m_cache->hasLength = true; 0103 } 0104 return m_cache->length; 0105 } 0106 0107 unsigned long DynamicNodeListImpl::calcLength(NodeImpl *start) const 0108 { 0109 unsigned long len = 0; 0110 for (NodeImpl *n = start->firstChild(); n != nullptr; n = n->nextSibling()) { 0111 bool recurse = true; 0112 if (nodeMatches(n, recurse)) { 0113 len++; 0114 } 0115 if (recurse) { 0116 len += DynamicNodeListImpl::calcLength(n); 0117 } 0118 } 0119 0120 return len; 0121 } 0122 0123 DynamicNodeListImpl::DynamicNodeListImpl(NodeImpl *n, int type, CacheFactory *factory) 0124 { 0125 m_refNode = n; 0126 m_refNode->ref(); 0127 0128 m_cache = m_refNode->document()->acquireCachedNodeListInfo( 0129 factory, n, type); 0130 } 0131 0132 DynamicNodeListImpl::~DynamicNodeListImpl() 0133 { 0134 m_refNode->document()->releaseCachedNodeListInfo(m_cache); 0135 m_refNode->deref(); 0136 } 0137 0138 /** 0139 Next item in the pre-order walk of tree from node, but not going outside 0140 absStart 0141 */ 0142 static NodeImpl *helperNext(NodeImpl *node, NodeImpl *absStart) 0143 { 0144 //Walk up until we wind a sibling to go to. 0145 while (!node->nextSibling() && node != absStart) { 0146 node = node->parentNode(); 0147 } 0148 0149 if (node != absStart) { 0150 return node->nextSibling(); 0151 } else { 0152 return nullptr; 0153 } 0154 } 0155 0156 NodeImpl *DynamicNodeListImpl::recursiveItem(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const 0157 { 0158 for (NodeImpl *n = start; n != nullptr; n = helperNext(n, absStart)) { 0159 bool recurse = true; 0160 if (nodeMatches(n, recurse)) 0161 if (!offset--) { 0162 return n; 0163 } 0164 0165 NodeImpl *depthSearch = recurse ? recursiveItem(n, n->firstChild(), offset) : nullptr; 0166 if (depthSearch) { 0167 return depthSearch; 0168 } 0169 } 0170 0171 return nullptr; // no matching node in this subtree 0172 } 0173 0174 NodeImpl *DynamicNodeListImpl::recursiveItemBack(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const 0175 { 0176 //### it might be cleaner/faster to split nodeMatches and recursion 0177 //filtering. 0178 bool dummy = true; 0179 NodeImpl *n = start; 0180 0181 do { 0182 bool recurse = true; 0183 0184 //Check whether the current node matches. 0185 if (nodeMatches(n, dummy)) 0186 if (!offset--) { 0187 return n; 0188 } 0189 0190 if (n->previousSibling()) { 0191 //Move to the last node of this whole subtree that we should recurse into 0192 n = n->previousSibling(); 0193 recurse = true; 0194 0195 while (n->lastChild()) { 0196 (void)nodeMatches(n, recurse); 0197 if (!recurse) { 0198 break; //Don't go there 0199 } 0200 n = n->lastChild(); 0201 } 0202 } else { 0203 //We're done with this whole subtree, so move up 0204 n = n->parentNode(); 0205 } 0206 } while (n && n != absStart); 0207 0208 return nullptr; 0209 } 0210 0211 // --------------------------------------------------------------------------- 0212 0213 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeStructuralOnly() 0214 { 0215 return new Cache(DocumentImpl::TV_Structural); // will check the same ver twice 0216 } 0217 0218 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeNameOrID() 0219 { 0220 return new Cache(DocumentImpl::TV_IDNameHref); 0221 } 0222 0223 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeClassName() 0224 { 0225 return new Cache(DocumentImpl::TV_Class); 0226 } 0227 0228 DynamicNodeListImpl::Cache::Cache(unsigned short relSecondaryVer): relevantSecondaryVer(relSecondaryVer) 0229 {} 0230 0231 DynamicNodeListImpl::Cache::~Cache() 0232 {} 0233 0234 void DynamicNodeListImpl::Cache::clear(DocumentImpl *doc) 0235 { 0236 hasLength = false; 0237 current.node = nullptr; 0238 version = doc->domTreeVersion(DocumentImpl::TV_Structural); 0239 secondaryVersion = doc->domTreeVersion(relevantSecondaryVer); 0240 } 0241 0242 void DynamicNodeListImpl::Cache::updateNodeListInfo(DocumentImpl *doc) 0243 { 0244 //If version doesn't match, clear 0245 if (doc->domTreeVersion(DocumentImpl::TV_Structural) != version || 0246 doc->domTreeVersion(relevantSecondaryVer) != secondaryVersion) { 0247 clear(doc); 0248 } 0249 } 0250 0251 // --------------------------------------------------------------------------- 0252 ChildNodeListImpl::ChildNodeListImpl(NodeImpl *n): DynamicNodeListImpl(n, CHILD_NODES, DynamicNodeListImpl::Cache::makeStructuralOnly) 0253 {} 0254 0255 bool ChildNodeListImpl::nodeMatches(NodeImpl * /*testNode*/, bool &doRecurse) const 0256 { 0257 doRecurse = false; 0258 return true; 0259 } 0260 0261 // --------------------------------------------------------------------------- 0262 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, NamespaceName namespaceName, LocalName localName, PrefixName prefix) 0263 : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly), 0264 m_namespaceAware(false) 0265 { 0266 m_namespace = namespaceName; 0267 m_localName = localName; 0268 m_prefix = prefix; 0269 } 0270 0271 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, const DOMString &namespaceURI, const DOMString &localName) 0272 : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly), 0273 m_namespaceAware(true) 0274 { 0275 if (namespaceURI == "*") { 0276 m_namespace = NamespaceName::fromId(anyNamespace); 0277 } else { 0278 m_namespace = NamespaceName::fromString(namespaceURI); 0279 } 0280 if (localName == "*") { 0281 m_localName = LocalName::fromId(anyLocalName); 0282 } else { 0283 m_localName = LocalName::fromString(localName); 0284 } 0285 m_prefix = PrefixName::fromId(emptyPrefix); 0286 } 0287 0288 bool TagNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const 0289 { 0290 if (testNode->nodeType() != Node::ELEMENT_NODE) { 0291 return false; 0292 } 0293 0294 if (m_namespaceAware) { 0295 return (m_namespace.id() == anyNamespace || m_namespace.id() == namespacePart(testNode->id())) && 0296 (m_localName.id() == anyLocalName || m_localName.id() == localNamePart(testNode->id())); 0297 } else { 0298 return (m_localName.id() == anyLocalName) || (m_localName.id() == localNamePart(testNode->id()) && 0299 m_prefix == static_cast<ElementImpl *>(testNode)->prefixName()); 0300 } 0301 } 0302 0303 // --------------------------------------------------------------------------- 0304 NameNodeListImpl::NameNodeListImpl(NodeImpl *n, const DOMString &t) 0305 : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeNameOrID), 0306 nodeName(t) 0307 {} 0308 0309 bool NameNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const 0310 { 0311 if (testNode->nodeType() != Node::ELEMENT_NODE) { 0312 return false; 0313 } 0314 return static_cast<ElementImpl *>(testNode)->getAttribute(ATTR_NAME) == nodeName; 0315 } 0316 0317 // --------------------------------------------------------------------------- 0318 ClassNodeListImpl::ClassNodeListImpl(NodeImpl *rootNode, const DOMString &classNames) 0319 : DynamicNodeListImpl(rootNode, UNCACHEABLE, DynamicNodeListImpl::Cache::makeClassName) 0320 { 0321 m_classNames.parseClassAttribute(classNames, m_refNode->document()->inCompatMode()); 0322 } 0323 0324 bool ClassNodeListImpl::nodeMatches(NodeImpl *testNode, bool &doRecurse) const 0325 { 0326 if (!testNode->isElementNode()) { 0327 doRecurse = false; 0328 return false; 0329 } 0330 0331 if (!testNode->hasClass()) { 0332 return false; 0333 } 0334 0335 if (!m_classNames.size()) { 0336 return false; 0337 } 0338 0339 const ClassNames &classes = static_cast<ElementImpl *>(testNode)->classNames(); 0340 for (size_t i = 0; i < m_classNames.size(); ++i) { 0341 if (!classes.contains(m_classNames[i])) { 0342 return false; 0343 } 0344 } 0345 0346 return true; 0347 } 0348 0349 // --------------------------------------------------------------------------- 0350 0351 StaticNodeListImpl::StaticNodeListImpl(): 0352 m_knownNormalization(DocumentOrder) // true vacuously 0353 {} 0354 0355 StaticNodeListImpl::~StaticNodeListImpl() {} 0356 0357 void StaticNodeListImpl::append(NodeImpl *n) 0358 { 0359 assert(n); 0360 m_kids.append(n); 0361 m_knownNormalization = Unnormalized; 0362 } 0363 0364 NodeImpl *StaticNodeListImpl::item(unsigned long index) const 0365 { 0366 return index < m_kids.size() ? m_kids[index].get() : nullptr; 0367 } 0368 0369 unsigned long StaticNodeListImpl::length() const 0370 { 0371 return m_kids.size(); 0372 } 0373 0374 static bool nodeLess(const SharedPtr<NodeImpl> &n1, const SharedPtr<DOM::NodeImpl> &n2) 0375 { 0376 return n1->compareDocumentPosition(n2.get()) & Node::DOCUMENT_POSITION_FOLLOWING; 0377 } 0378 0379 void StaticNodeListImpl::normalizeUpto(NormalizationKind kind) 0380 { 0381 if (m_knownNormalization == kind || m_knownNormalization == DocumentOrder) { 0382 return; 0383 } 0384 0385 if (kind == Unnormalized) { 0386 return; 0387 } 0388 0389 // First sort. 0390 std::sort(m_kids.begin(), m_kids.end(), nodeLess); 0391 0392 // Now get rid of dupes. 0393 DOM::NodeImpl *last = nullptr; 0394 unsigned out = 0; 0395 for (unsigned in = 0; in < m_kids.size(); ++in) { 0396 DOM::NodeImpl *cur = m_kids[in].get(); 0397 if (cur != last) { 0398 m_kids[out] = cur; 0399 ++out; 0400 } 0401 0402 last = cur; 0403 } 0404 m_kids.resize(out); 0405 0406 m_knownNormalization = DocumentOrder; 0407 } 0408 0409 void StaticNodeListImpl::setKnownNormalization(NormalizationKind kind) 0410 { 0411 m_knownNormalization = kind; 0412 } 0413 0414 StaticNodeListImpl::NormalizationKind StaticNodeListImpl::knownNormalization() const 0415 { 0416 return m_knownNormalization; 0417 } 0418