KHtml

dom_nodelistimpl.cpp
1 /*
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 1999 Lars Knoll ([email protected])
5  * (C) 1999 Antti Koivisto ([email protected])
6  * (C) 2001 Dirk Mueller ([email protected])
7  * (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
8  * (C) 2005, 2009, 2010 Maksim Orlovich ([email protected])
9  * (C) 2006 Allan Sandfeld Jensen ([email protected])
10  * (C) 2007 David Smith ([email protected])
11  *
12  * This library is free software; you can redistribute it and/or
13  * modify it under the terms of the GNU Library General Public
14  * License as published by the Free Software Foundation; either
15  * version 2 of the License, or (at your option) any later version.
16  *
17  * This library is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20  * Library General Public License for more details.
21  *
22  * You should have received a copy of the GNU Library General Public License
23  * along with this library; see the file COPYING.LIB. If not, write to
24  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
25  * Boston, MA 02110-1301, USA.
26  *
27  *
28  * The code for ClassNodeListImpl was originally licensed under the following terms
29  * (but in this version is available only as above):
30  * Redistribution and use in source and binary forms, with or without
31  * modification, are permitted provided that the following conditions
32  * are met:
33  *
34  * 1. Redistributions of source code must retain the above copyright
35  * notice, this list of conditions and the following disclaimer.
36  * 2. Redistributions in binary form must reproduce the above copyright
37  * notice, this list of conditions and the following disclaimer in the
38  * documentation and/or other materials provided with the distribution.
39  * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
40  * its contributors may be used to endorse or promote products derived
41  * from this software without specific prior written permission.
42  *
43  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
44  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
45  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
46  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
47  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
48  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
49  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
50  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
51  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
52  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
53  */
54 
55 #include "dom_nodelistimpl.h"
56 #include "dom_nodeimpl.h"
57 #include "dom_docimpl.h"
58 
59 using namespace DOM;
60 using namespace khtml;
61 
62 NodeImpl *DynamicNodeListImpl::item(unsigned long index) const
63 {
64  unsigned long requestIndex = index;
65 
66  m_cache->updateNodeListInfo(m_refNode->document());
67 
68  NodeImpl *n = nullptr;
69  bool usedCache = false;
70  if (m_cache->current.node) {
71  //Compute distance from the requested index to the cache node
72  unsigned long cacheDist = qAbs(long(index) - long(m_cache->position));
73 
74  if (cacheDist < (unsigned long)index) { //Closer to the cached position
75  usedCache = true;
76  if (index >= m_cache->position) { //Go ahead
77  unsigned long relIndex = index - m_cache->position;
78  n = recursiveItem(m_refNode, m_cache->current.node, relIndex);
79  } else { //Go backwards
80  unsigned long relIndex = m_cache->position - index;
81  n = recursiveItemBack(m_refNode, m_cache->current.node, relIndex);
82  }
83  }
84  }
85 
86  if (!usedCache) {
87  n = recursiveItem(m_refNode, m_refNode->firstChild(), index);
88  }
89 
90  //We always update the cache state, to make starting iteration
91  //where it was left off easy.
92  m_cache->current.node = n;
93  m_cache->position = requestIndex;
94  return n;
95 }
96 
97 unsigned long DynamicNodeListImpl::length() const
98 {
99  m_cache->updateNodeListInfo(m_refNode->document());
100  if (!m_cache->hasLength) {
101  m_cache->length = calcLength(m_refNode);
102  m_cache->hasLength = true;
103  }
104  return m_cache->length;
105 }
106 
107 unsigned long DynamicNodeListImpl::calcLength(NodeImpl *start) const
108 {
109  unsigned long len = 0;
110  for (NodeImpl *n = start->firstChild(); n != nullptr; n = n->nextSibling()) {
111  bool recurse = true;
112  if (nodeMatches(n, recurse)) {
113  len++;
114  }
115  if (recurse) {
116  len += DynamicNodeListImpl::calcLength(n);
117  }
118  }
119 
120  return len;
121 }
122 
123 DynamicNodeListImpl::DynamicNodeListImpl(NodeImpl *n, int type, CacheFactory *factory)
124 {
125  m_refNode = n;
126  m_refNode->ref();
127 
128  m_cache = m_refNode->document()->acquireCachedNodeListInfo(
129  factory, n, type);
130 }
131 
132 DynamicNodeListImpl::~DynamicNodeListImpl()
133 {
134  m_refNode->document()->releaseCachedNodeListInfo(m_cache);
135  m_refNode->deref();
136 }
137 
142 static NodeImpl *helperNext(NodeImpl *node, NodeImpl *absStart)
143 {
144  //Walk up until we wind a sibling to go to.
145  while (!node->nextSibling() && node != absStart) {
146  node = node->parentNode();
147  }
148 
149  if (node != absStart) {
150  return node->nextSibling();
151  } else {
152  return nullptr;
153  }
154 }
155 
156 NodeImpl *DynamicNodeListImpl::recursiveItem(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const
157 {
158  for (NodeImpl *n = start; n != nullptr; n = helperNext(n, absStart)) {
159  bool recurse = true;
160  if (nodeMatches(n, recurse))
161  if (!offset--) {
162  return n;
163  }
164 
165  NodeImpl *depthSearch = recurse ? recursiveItem(n, n->firstChild(), offset) : nullptr;
166  if (depthSearch) {
167  return depthSearch;
168  }
169  }
170 
171  return nullptr; // no matching node in this subtree
172 }
173 
174 NodeImpl *DynamicNodeListImpl::recursiveItemBack(NodeImpl *absStart, NodeImpl *start, unsigned long &offset) const
175 {
176  //### it might be cleaner/faster to split nodeMatches and recursion
177  //filtering.
178  bool dummy = true;
179  NodeImpl *n = start;
180 
181  do {
182  bool recurse = true;
183 
184  //Check whether the current node matches.
185  if (nodeMatches(n, dummy))
186  if (!offset--) {
187  return n;
188  }
189 
190  if (n->previousSibling()) {
191  //Move to the last node of this whole subtree that we should recurse into
192  n = n->previousSibling();
193  recurse = true;
194 
195  while (n->lastChild()) {
196  (void)nodeMatches(n, recurse);
197  if (!recurse) {
198  break; //Don't go there
199  }
200  n = n->lastChild();
201  }
202  } else {
203  //We're done with this whole subtree, so move up
204  n = n->parentNode();
205  }
206  } while (n && n != absStart);
207 
208  return nullptr;
209 }
210 
211 // ---------------------------------------------------------------------------
212 
213 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeStructuralOnly()
214 {
215  return new Cache(DocumentImpl::TV_Structural); // will check the same ver twice
216 }
217 
218 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeNameOrID()
219 {
220  return new Cache(DocumentImpl::TV_IDNameHref);
221 }
222 
223 DynamicNodeListImpl::Cache *DynamicNodeListImpl::Cache::makeClassName()
224 {
225  return new Cache(DocumentImpl::TV_Class);
226 }
227 
228 DynamicNodeListImpl::Cache::Cache(unsigned short relSecondaryVer): relevantSecondaryVer(relSecondaryVer)
229 {}
230 
231 DynamicNodeListImpl::Cache::~Cache()
232 {}
233 
234 void DynamicNodeListImpl::Cache::clear(DocumentImpl *doc)
235 {
236  hasLength = false;
237  current.node = nullptr;
238  version = doc->domTreeVersion(DocumentImpl::TV_Structural);
239  secondaryVersion = doc->domTreeVersion(relevantSecondaryVer);
240 }
241 
242 void DynamicNodeListImpl::Cache::updateNodeListInfo(DocumentImpl *doc)
243 {
244  //If version doesn't match, clear
245  if (doc->domTreeVersion(DocumentImpl::TV_Structural) != version ||
246  doc->domTreeVersion(relevantSecondaryVer) != secondaryVersion) {
247  clear(doc);
248  }
249 }
250 
251 // ---------------------------------------------------------------------------
252 ChildNodeListImpl::ChildNodeListImpl(NodeImpl *n): DynamicNodeListImpl(n, CHILD_NODES, DynamicNodeListImpl::Cache::makeStructuralOnly)
253 {}
254 
255 bool ChildNodeListImpl::nodeMatches(NodeImpl * /*testNode*/, bool &doRecurse) const
256 {
257  doRecurse = false;
258  return true;
259 }
260 
261 // ---------------------------------------------------------------------------
262 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, NamespaceName namespaceName, LocalName localName, PrefixName prefix)
263  : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly),
264  m_namespaceAware(false)
265 {
266  m_namespace = namespaceName;
267  m_localName = localName;
268  m_prefix = prefix;
269 }
270 
271 TagNodeListImpl::TagNodeListImpl(NodeImpl *n, const DOMString &namespaceURI, const DOMString &localName)
272  : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeStructuralOnly),
273  m_namespaceAware(true)
274 {
275  if (namespaceURI == "*") {
276  m_namespace = NamespaceName::fromId(anyNamespace);
277  } else {
278  m_namespace = NamespaceName::fromString(namespaceURI);
279  }
280  if (localName == "*") {
281  m_localName = LocalName::fromId(anyLocalName);
282  } else {
283  m_localName = LocalName::fromString(localName);
284  }
285  m_prefix = PrefixName::fromId(emptyPrefix);
286 }
287 
288 bool TagNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const
289 {
290  if (testNode->nodeType() != Node::ELEMENT_NODE) {
291  return false;
292  }
293 
294  if (m_namespaceAware) {
295  return (m_namespace.id() == anyNamespace || m_namespace.id() == namespacePart(testNode->id())) &&
296  (m_localName.id() == anyLocalName || m_localName.id() == localNamePart(testNode->id()));
297  } else {
298  return (m_localName.id() == anyLocalName) || (m_localName.id() == localNamePart(testNode->id()) &&
299  m_prefix == static_cast<ElementImpl *>(testNode)->prefixName());
300  }
301 }
302 
303 // ---------------------------------------------------------------------------
304 NameNodeListImpl::NameNodeListImpl(NodeImpl *n, const DOMString &t)
305  : DynamicNodeListImpl(n, UNCACHEABLE, DynamicNodeListImpl::Cache::makeNameOrID),
306  nodeName(t)
307 {}
308 
309 bool NameNodeListImpl::nodeMatches(NodeImpl *testNode, bool & /*doRecurse*/) const
310 {
311  if (testNode->nodeType() != Node::ELEMENT_NODE) {
312  return false;
313  }
314  return static_cast<ElementImpl *>(testNode)->getAttribute(ATTR_NAME) == nodeName;
315 }
316 
317 // ---------------------------------------------------------------------------
318 ClassNodeListImpl::ClassNodeListImpl(NodeImpl *rootNode, const DOMString &classNames)
319  : DynamicNodeListImpl(rootNode, UNCACHEABLE, DynamicNodeListImpl::Cache::makeClassName)
320 {
321  m_classNames.parseClassAttribute(classNames, m_refNode->document()->inCompatMode());
322 }
323 
324 bool ClassNodeListImpl::nodeMatches(NodeImpl *testNode, bool &doRecurse) const
325 {
326  if (!testNode->isElementNode()) {
327  doRecurse = false;
328  return false;
329  }
330 
331  if (!testNode->hasClass()) {
332  return false;
333  }
334 
335  if (!m_classNames.size()) {
336  return false;
337  }
338 
339  const ClassNames &classes = static_cast<ElementImpl *>(testNode)->classNames();
340  for (size_t i = 0; i < m_classNames.size(); ++i) {
341  if (!classes.contains(m_classNames[i])) {
342  return false;
343  }
344  }
345 
346  return true;
347 }
348 
349 // ---------------------------------------------------------------------------
350 
351 StaticNodeListImpl::StaticNodeListImpl():
352  m_knownNormalization(DocumentOrder) // true vacuously
353 {}
354 
355 StaticNodeListImpl::~StaticNodeListImpl() {}
356 
357 void StaticNodeListImpl::append(NodeImpl *n)
358 {
359  assert(n);
360  m_kids.append(n);
361  m_knownNormalization = Unnormalized;
362 }
363 
364 NodeImpl *StaticNodeListImpl::item(unsigned long index) const
365 {
366  return index < m_kids.size() ? m_kids[index].get() : nullptr;
367 }
368 
369 unsigned long StaticNodeListImpl::length() const
370 {
371  return m_kids.size();
372 }
373 
374 static bool nodeLess(const SharedPtr<NodeImpl> &n1, const SharedPtr<DOM::NodeImpl> &n2)
375 {
376  return n1->compareDocumentPosition(n2.get()) & Node::DOCUMENT_POSITION_FOLLOWING;
377 }
378 
379 void StaticNodeListImpl::normalizeUpto(NormalizationKind kind)
380 {
381  if (m_knownNormalization == kind || m_knownNormalization == DocumentOrder) {
382  return;
383  }
384 
385  if (kind == Unnormalized) {
386  return;
387  }
388 
389  // First sort.
390  std::sort(m_kids.begin(), m_kids.end(), nodeLess);
391 
392  // Now get rid of dupes.
393  DOM::NodeImpl *last = nullptr;
394  unsigned out = 0;
395  for (unsigned in = 0; in < m_kids.size(); ++in) {
396  DOM::NodeImpl *cur = m_kids[in].get();
397  if (cur != last) {
398  m_kids[out] = cur;
399  ++out;
400  }
401 
402  last = cur;
403  }
404  m_kids.resize(out);
405 
406  m_knownNormalization = DocumentOrder;
407 }
408 
409 void StaticNodeListImpl::setKnownNormalization(NormalizationKind kind)
410 {
411  m_knownNormalization = kind;
412 }
413 
414 StaticNodeListImpl::NormalizationKind StaticNodeListImpl::knownNormalization() const
415 {
416  return m_knownNormalization;
417 }
418 
This file is part of the HTML rendering engine for KDE.
This class implements the basic string we use in the DOM.
Definition: dom_string.h:44
This library provides a full-featured HTML parser and widget.
KDB_EXPORT KDbVersionInfo version()
This file is part of the KDE documentation.
Documentation copyright © 1996-2020 The KDE developers.
Generated on Sat Jul 11 2020 22:45:23 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.