KHtml

dom2_traversalimpl.cpp
1 /**
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 1999 Lars Knoll <[email protected]>
5  * Copyright (C) 2000 Frederik Holljen <[email protected]>
6  * Copyright (C) 2001 Peter Kelly <[email protected]>
7  * Copyright (C) 2008 Maksim Orlovich <[email protected]>
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Library General Public
11  * License as published by the Free Software Foundation; either
12  * version 2 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * Library General Public License for more details.
18  *
19  * You should have received a copy of the GNU Library General Public License
20  * along with this library; see the file COPYING.LIB. If not, write to
21  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22  * Boston, MA 02110-1301, USA.
23  */
24 
25 #include "dom/dom_exception.h"
26 #include "xml/dom_docimpl.h"
27 
28 /**
29  Robustness notes: we protect the object we hold on to, to
30  prevent crashes. To ensure termination in JS used, we propagate exceptions,
31  and rely on the JS CPU guard to set one to force us to bail out.
32 
33  ### TODO/CHECKONE
34 */
35 
36 using namespace DOM;
37 
38 NodeIteratorImpl::NodeIteratorImpl(NodeImpl *_root, unsigned long _whatToShow,
39  NodeFilterImpl *_filter, bool _entityReferenceExpansion)
40 {
41  m_root = _root;
42  m_whatToShow = _whatToShow;
43  m_filter = _filter;
44  m_expandEntityReferences = _entityReferenceExpansion;
45 
46  m_referenceNode = _root;
47  m_position = ITER_BEFORE_REF;
48 
49  m_doc = m_root->document();
50  m_doc->attachNodeIterator(this);
51  m_doc->ref();
52 
53  m_detached = false;
54 }
55 
56 NodeIteratorImpl::~NodeIteratorImpl()
57 {
58  m_doc->detachNodeIterator(this);
59  m_doc->deref();
60 }
61 
62 NodeImpl *NodeIteratorImpl::root()
63 {
64  return m_root.get();
65 }
66 
67 unsigned long NodeIteratorImpl::whatToShow()
68 {
69  return m_whatToShow;
70 }
71 
72 NodeFilterImpl *NodeIteratorImpl::filter()
73 {
74  return m_filter.get();
75 }
76 
77 bool NodeIteratorImpl::expandEntityReferences()
78 {
79  return m_expandEntityReferences;
80 }
81 
82 SharedPtr<NodeImpl> NodeIteratorImpl::nextNode(int &exceptioncode, void *&propagatedExceptionObject)
83 {
84  propagatedExceptionObject = nullptr;
85  if (m_detached) {
86  exceptioncode = DOMException::INVALID_STATE_ERR;
87  return nullptr;
88  }
89 
90  SharedPtr<NodeImpl> oldReferenceNode = m_referenceNode;
91  Position oldPosition = m_position;
92  while (true) {
93  SharedPtr<NodeImpl> cand = m_referenceNode;
94  // If we're before a node, it's the next node to return, and we'll
95  // be positioned after.
96  if (m_position == ITER_BEFORE_REF) {
97  m_position = ITER_AFTER_REF;
98  if (isAccepted(m_referenceNode.get(), propagatedExceptionObject) == NodeFilter::FILTER_ACCEPT) {
99  return cand;
100  }
101  if (propagatedExceptionObject) {
102  m_position = oldPosition;
103  m_referenceNode = oldReferenceNode;
104  return nullptr;
105  }
106  } else {
107  // Robustness note here: the filter could potentially yank any nodes out,
108  // so we can't keep any state in the temporaries. We hence always rely on
109  // m_referenceNode, which would be sync'd by the delete handler
110  cand = getNextNode(m_referenceNode.get());
111  if (!cand) {
112  return nullptr;
113  }
114  m_referenceNode = cand;
115  if (isAccepted(cand.get(), propagatedExceptionObject) == NodeFilter::FILTER_ACCEPT) {
116  return cand;
117  }
118  if (propagatedExceptionObject) {
119  m_position = oldPosition;
120  m_referenceNode = oldReferenceNode;
121  return nullptr;
122  }
123  }
124  }
125  return nullptr;
126 }
127 
128 SharedPtr<NodeImpl> NodeIteratorImpl::previousNode(int &exceptioncode, void *&propagatedExceptionObject)
129 {
130  propagatedExceptionObject = nullptr;
131  if (m_detached) {
132  exceptioncode = DOMException::INVALID_STATE_ERR;
133  return nullptr;
134  }
135 
136  SharedPtr<NodeImpl> oldReferenceNode = m_referenceNode;
137  Position oldPosition = m_position;
138  while (true) {
139  SharedPtr<NodeImpl> cand = m_referenceNode;
140  if (m_position == ITER_AFTER_REF) {
141  m_position = ITER_BEFORE_REF;
142  if (isAccepted(m_referenceNode.get(), propagatedExceptionObject) == NodeFilter::FILTER_ACCEPT) {
143  return cand;
144  }
145 
146  if (propagatedExceptionObject) {
147  m_position = oldPosition;
148  m_referenceNode = oldReferenceNode;
149  return nullptr;
150  }
151  } else {
152  cand = getPrevNode(m_referenceNode.get());
153  if (!cand) {
154  return nullptr;
155  }
156 
157  m_referenceNode = cand;
158  if (isAccepted(cand.get(), propagatedExceptionObject) == NodeFilter::FILTER_ACCEPT) {
159  return cand;
160  }
161  if (propagatedExceptionObject) {
162  m_position = oldPosition;
163  m_referenceNode = oldReferenceNode;
164  return nullptr;
165  }
166  }
167  }
168  return nullptr;
169 }
170 
171 NodeImpl *NodeIteratorImpl::getNextNode(NodeImpl *from)
172 {
173  return from->traverseNextNode(m_root.get());
174 }
175 
176 NodeImpl *NodeIteratorImpl::getPrevNode(NodeImpl *from)
177 {
178  if (from == m_root) {
179  return nullptr;
180  } else {
181  return from->traversePreviousNode();
182  }
183 }
184 
185 NodeImpl *NodeIteratorImpl::getLastNode(NodeImpl *in)
186 {
187  while (NodeImpl *cand = in->lastChild()) {
188  in = cand;
189  }
190  return in;
191 }
192 
193 void NodeIteratorImpl::detach(int &/*exceptioncode*/)
194 {
195  m_doc->detachNodeIterator(this);
196  m_detached = true;
197 }
198 
199 void NodeIteratorImpl::notifyBeforeNodeRemoval(NodeImpl *removed)
200 {
201  // We care about removals if they happen on the path between us and root,
202  // and not if it's just the root being yanked out.
203  if (removed == m_root) {
204  return;
205  }
206 
207  // Scan up from the reference node to root see if the removed node is there..
208  NodeImpl *c;
209  for (c = m_referenceNode.get(); c != m_root; c = c->parentNode()) {
210  if (c == removed) {
211  break;
212  }
213  }
214 
215  // If nothing was found, we were unaffected.
216  if (c == m_root) {
217  return;
218  }
219 
220  // Update the position.. Thankfully we don't have to call filters here.
221  if (m_position == ITER_BEFORE_REF) {
222  // We were positioned before some node in the removed subtree...
223  // We want to be positioned before the first node after the
224  // removed subtree.
225  NodeImpl *next = getNextNode(getLastNode(removed));
226  if (next) {
227  m_referenceNode = next;
228  } else {
229  // There is no where to go after this --- pick a node before the tree,
230  // which in preorder is the immediate pred. of the remove root.
231  m_position = ITER_AFTER_REF;
232  m_referenceNode = getPrevNode(removed);
233  }
234  } else { // Iterator after ref.
235  // We were after some node in the removed subtree, we want to be
236  // after the node immediately before it. There -must- be one,
237  // since at least the root preceeds it!
238  m_referenceNode = getPrevNode(removed);
239  }
240 }
241 
242 short NodeIteratorImpl::isAccepted(NodeImpl *n, void *&propagatedExceptionObject)
243 {
244  // if XML is implemented we have to check expandEntityRerefences in this function
245  if (((1 << (n->nodeType() - 1)) & m_whatToShow) != 0) {
246  if (!m_filter.isNull()) {
247  return m_filter->acceptNode(n, propagatedExceptionObject);
248  } else {
249  return NodeFilter::FILTER_ACCEPT;
250  }
251  }
252  return NodeFilter::FILTER_SKIP;
253 }
254 
255 // --------------------------------------------------------------
256 
257 NodeFilterImpl::NodeFilterImpl()
258 {
259  m_customNodeFilter = nullptr;
260 }
261 
262 NodeFilterImpl::~NodeFilterImpl()
263 {
264  if (m_customNodeFilter) {
265  m_customNodeFilter->deref();
266  }
267 }
268 
269 bool NodeFilterImpl::isJSFilter() const
270 {
271  return false;
272 }
273 
274 short NodeFilterImpl::acceptNode(const Node &n, void *& /*bindingsException*/)
275 {
276  if (m_customNodeFilter) {
277  return m_customNodeFilter->acceptNode(n);
278  } else {
279  return NodeFilter::FILTER_ACCEPT;
280  }
281 }
282 
283 void NodeFilterImpl::setCustomNodeFilter(CustomNodeFilter *custom)
284 {
285  m_customNodeFilter = custom;
286  if (m_customNodeFilter) {
287  m_customNodeFilter->ref();
288  }
289 }
290 
291 CustomNodeFilter *NodeFilterImpl::customNodeFilter()
292 {
293  return m_customNodeFilter;
294 }
295 
296 // --------------------------------------------------------------
297 
298 TreeWalkerImpl::TreeWalkerImpl(NodeImpl *n, long _whatToShow, NodeFilterImpl *f,
299  bool entityReferenceExpansion)
300 {
301  m_currentNode = n;
302  m_rootNode = n;
303  m_whatToShow = _whatToShow;
304  m_filter = f;
305  if (m_filter) {
306  m_filter->ref();
307  }
308  m_expandEntityReferences = entityReferenceExpansion;
309  m_doc = m_rootNode->document();
310  m_doc->ref();
311 }
312 
313 TreeWalkerImpl::~TreeWalkerImpl()
314 {
315  m_doc->deref();
316  if (m_filter) {
317  m_filter->deref();
318  }
319 }
320 
321 NodeImpl *TreeWalkerImpl::getRoot() const
322 {
323  return m_rootNode.get();
324 }
325 
326 unsigned long TreeWalkerImpl::getWhatToShow() const
327 {
328  return m_whatToShow;
329 }
330 
331 NodeFilterImpl *TreeWalkerImpl::getFilter() const
332 {
333  return m_filter;
334 }
335 
336 bool TreeWalkerImpl::getExpandEntityReferences() const
337 {
338  return m_expandEntityReferences;
339 }
340 
341 NodeImpl *TreeWalkerImpl::getCurrentNode() const
342 {
343  return m_currentNode.get();
344 }
345 
346 void TreeWalkerImpl::setWhatToShow(long _whatToShow)
347 {
348  // do some testing whether this is an accepted value
349  m_whatToShow = _whatToShow;
350 }
351 
352 void TreeWalkerImpl::setFilter(NodeFilterImpl *_filter)
353 {
354  m_filter->deref();
355  m_filter = _filter;
356  if (m_filter) {
357  m_filter->ref();
358  }
359 }
360 
361 void TreeWalkerImpl::setExpandEntityReferences(bool value)
362 {
363  m_expandEntityReferences = value;
364 }
365 
366 void TreeWalkerImpl::setCurrentNode(NodeImpl *n, int &exceptionCode)
367 {
368  if (n) {
369  m_currentNode = n;
370  } else {
371  exceptionCode = DOMException::NOT_SUPPORTED_ERR;
372  }
373 }
374 
375 NodeImpl *TreeWalkerImpl::parentNode(void *&filterException)
376 {
377  NodePtr n = getParentNode(m_currentNode, filterException);
378  if (n) {
379  m_currentNode = n;
380  }
381  return n.get();
382 }
383 
384 NodeImpl *TreeWalkerImpl::firstChild(void *&filterException)
385 {
386  NodePtr n = getFirstChild(m_currentNode, filterException);
387  if (n) {
388  m_currentNode = n;
389  }
390  return n.get();
391 }
392 
393 NodeImpl *TreeWalkerImpl::lastChild(void *&filterException)
394 {
395  NodePtr n = getLastChild(m_currentNode, filterException);
396  if (n) {
397  m_currentNode = n;
398  }
399  return n.get();
400 }
401 
402 NodeImpl *TreeWalkerImpl::previousSibling(void *&filterException)
403 {
404  NodePtr n = getPreviousSibling(m_currentNode, filterException);
405  if (n) {
406  m_currentNode = n;
407  }
408  return n.get();
409 }
410 
411 NodeImpl *TreeWalkerImpl::nextSibling(void *&filterException)
412 {
413  NodePtr n = getNextSibling(m_currentNode, filterException);
414  if (n) {
415  m_currentNode = n;
416  }
417  return n.get();
418 }
419 
420 NodeImpl *TreeWalkerImpl::nextNode(void *&filterException)
421 {
422  NodePtr n = getNextNode(filterException);
423  if (n) {
424  m_currentNode = n;
425  }
426  return n.get();
427 }
428 
429 NodeImpl *TreeWalkerImpl::previousNode(void *&filterException)
430 {
431  NodePtr n = getPreviousNode(filterException);
432  if (n) {
433  m_currentNode = n;
434  }
435  return n.get();
436 }
437 
438 TreeWalkerImpl::NodePtr TreeWalkerImpl::getPreviousNode(void *&filterException)
439 {
440  filterException = nullptr;
441  /* 1. last node in my previous sibling's subtree
442  * 2. my previous sibling (special case of the above)
443  * 3. my parent
444  */
445 
446  NodePtr n = getPreviousSibling(m_currentNode, filterException);
447  if (filterException) {
448  return nullptr;
449  }
450  if (n) {
451  // Find the last kid in the subtree's preorder traversal, if any,
452  // by following the lastChild links.
453  NodePtr desc = getLastChild(n, filterException);
454  if (filterException) {
455  return nullptr;
456  }
457  while (desc) {
458  n = desc;
459  desc = getLastChild(desc, filterException);
460  if (filterException) {
461  return nullptr;
462  }
463  }
464  return n;
465  }
466 
467  return getParentNode(m_currentNode, filterException);
468 }
469 
470 TreeWalkerImpl::NodePtr TreeWalkerImpl::getNextNode(void *&filterException)
471 {
472  filterException = nullptr;
473  /* 1. my first child
474  * 2. my next sibling
475  * 3. my parents sibling, or their parents sibling (loop)
476  * 4. not found
477  */
478 
479  NodePtr n = getFirstChild(m_currentNode, filterException);
480  if (filterException) {
481  return nullptr;
482  }
483  if (n) { // my first child
484  return n;
485  }
486 
487  n = getNextSibling(m_currentNode, filterException); // my next sibling
488  if (filterException) {
489  return nullptr;
490  }
491  if (n) {
492  return n;
493  }
494 
495  NodePtr parent = getParentNode(m_currentNode, filterException);
496  if (filterException) {
497  return nullptr;
498  }
499  while (parent) { // parent's sibling
500  n = getNextSibling(parent, filterException);
501  if (filterException) {
502  return nullptr;
503  }
504  if (n) {
505  return n;
506  }
507 
508  parent = getParentNode(parent, filterException);
509  if (filterException) {
510  return nullptr;
511  }
512  }
513  return nullptr;
514 }
515 
516 short TreeWalkerImpl::isAccepted(TreeWalkerImpl::NodePtr n, void *&filterException)
517 {
518  // if XML is implemented we have to check expandEntityRerefences in this function
519  if (((1 << (n->nodeType() - 1)) & m_whatToShow) != 0) {
520  if (m_filter) {
521  return m_filter->acceptNode(n.get(), filterException);
522  } else {
523  return NodeFilter::FILTER_ACCEPT;
524  }
525  }
526  return NodeFilter::FILTER_SKIP;
527 }
528 
529 /**
530  This is quite a bit more complicated than it would at first seem, due to the following note:
531  "Note that the structure of a TreeWalker's filtered view of a document may differ significantly from that of the document itself. For example, a TreeWalker with only SHOW_TEXT specified in its whatToShow parameter would present all the Text nodes as if they were siblings of each other yet had no parent."
532 
533  My read of this is that e.g. that when a node is FILTER_SKIP'd, its children are handled
534  as the children of its parent. -M.O.
535 */
536 
537 TreeWalkerImpl::NodePtr TreeWalkerImpl::getParentNode(TreeWalkerImpl::NodePtr n, void *&filterException)
538 {
539  filterException = nullptr;
540  // Already on top of root's subtree tree...
541  if (n == m_rootNode) {
542  return nullptr;
543  }
544 
545  // Walk up, to find the first visible node != n, until we run out of
546  // document or into the root (which we don't have to be inside of!)
547  NodePtr cursor = n->parentNode();
548  while (cursor) {
549  if (isAccepted(cursor, filterException) == NodeFilter::FILTER_ACCEPT) {
550  return cursor;
551  }
552  if (filterException) {
553  return nullptr;
554  }
555 
556  if (cursor == m_rootNode) { // We just checked root -- no where else to go up.
557  return nullptr;
558  }
559  cursor = cursor->parentNode();
560  }
561 
562  return nullptr;
563 }
564 
565 TreeWalkerImpl::NodePtr TreeWalkerImpl::getFirstChild(TreeWalkerImpl::NodePtr n, void *&filterException)
566 {
567  filterException = nullptr;
568  NodePtr cursor;
569  for (cursor = n->firstChild(); cursor; cursor = cursor->nextSibling()) {
570  switch (isAccepted(cursor, filterException)) {
571  case NodeFilter::FILTER_ACCEPT:
572  return cursor;
573  case NodeFilter::FILTER_SKIP: {
574  // We ignore this candidate proper, but perhaps it has a kid?
575  NodePtr cand = getFirstChild(cursor, filterException);
576  if (filterException) {
577  return nullptr;
578  }
579  if (cand) {
580  return cand;
581  }
582  break;
583  }
584  case NodeFilter::FILTER_REJECT:
585  // It effectively doesn't exist, or exception
586  if (filterException) {
587  return nullptr;
588  }
589  break;
590  }
591  // ### this is unclear: what should happen if we "pass through" the root??
592  }
593 
594  // Nothing found..
595  return nullptr;
596 }
597 
598 TreeWalkerImpl::NodePtr TreeWalkerImpl::getLastChild(TreeWalkerImpl::NodePtr n, void *&filterException)
599 {
600  filterException = nullptr;
601  TreeWalkerImpl::NodePtr cursor;
602  for (cursor = n->lastChild(); cursor; cursor = cursor->previousSibling()) {
603  switch (isAccepted(cursor, filterException)) {
604  case NodeFilter::FILTER_ACCEPT:
605  return cursor;
606  case NodeFilter::FILTER_SKIP: {
607  // We ignore this candidate proper, but perhaps it has a kid?
608  TreeWalkerImpl::NodePtr cand = getLastChild(cursor, filterException);
609  if (filterException) {
610  return nullptr;
611  }
612  if (cand) {
613  return cand;
614  }
615  break;
616  }
617  case NodeFilter::FILTER_REJECT:
618  // It effectively doesn't exist..
619  if (filterException) {
620  return nullptr;
621  }
622  break;
623  }
624  // ### this is unclear: what should happen if we "pass through" the root??
625  }
626 
627  // Nothing found..
628  return nullptr;
629 }
630 
631 TreeWalkerImpl::NodePtr TreeWalkerImpl::getNextSibling(TreeWalkerImpl::NodePtr n, void *&filterException)
632 {
633  filterException = nullptr;
634 
635  // If we're the root node, clearly we don't have any siblings.
636  if (n == m_rootNode) {
637  return nullptr;
638  }
639 
640  // What would can our siblings be? Well, they can be our actual siblings,
641  // or if those are 'skip' their first kid. We may also have to walk up
642  // through any skipped nodes.
643  NodePtr cursor;
644  for (cursor = n->nextSibling(); cursor; cursor = cursor->nextSibling()) {
645  switch (isAccepted(cursor, filterException)) {
646  case NodeFilter::FILTER_ACCEPT:
647  return cursor;
648  case NodeFilter::FILTER_SKIP: {
649  NodePtr cand = getFirstChild(cursor, filterException);
650  if (filterException) {
651  return nullptr;
652  }
653  if (cand) {
654  return cand;
655  }
656  break;
657  }
658  case NodeFilter::FILTER_REJECT:
659  if (filterException) {
660  return nullptr;
661  }
662  break;
663  }
664  }
665 
666  // Now, we have scanned through all of our parent's kids. Our siblings may also be
667  // above if we could have skipped the parent, and are not captured by it.
668  NodePtr parent = n->parentNode();
669  if (!parent || parent == m_rootNode) {
670  return nullptr;
671  }
672 
673  /* "In particular: If the currentNode becomes part of a subtree that would otherwise have
674  been Rejected by the filter, that entire subtree may be added as transient members of the
675  logical view. You will be able to navigate within that subtree (subject to all the usual
676  filtering) until you move upward past the Rejected ancestor. The behavior is as if the Rejected
677  node had only been Skipped (since we somehow wound up inside its subtree) until we leave it;
678  thereafter, standard filtering applies.*/
679  if (isAccepted(parent, filterException) == NodeFilter::FILTER_ACCEPT) {
680  return nullptr;
681  }
682  if (filterException) {
683  return nullptr;
684  }
685 
686  return getNextSibling(parent, filterException);
687 }
688 
689 TreeWalkerImpl::NodePtr TreeWalkerImpl::getPreviousSibling(TreeWalkerImpl::NodePtr n, void *&filterException)
690 {
691  filterException = nullptr;
692  // See the above for all the comments :-)
693  if (n == m_rootNode) {
694  return nullptr;
695  }
696 
697  NodePtr cursor;
698  for (cursor = n->previousSibling(); cursor; cursor = cursor->previousSibling()) {
699  switch (isAccepted(cursor, filterException)) {
700  case NodeFilter::FILTER_ACCEPT:
701  return cursor;
702  case NodeFilter::FILTER_SKIP: {
703  NodePtr cand = getLastChild(cursor, filterException);
704  if (filterException) {
705  return nullptr;
706  }
707  if (cand) {
708  return cand;
709  }
710  break;
711  }
712  case NodeFilter::FILTER_REJECT:
713  if (filterException) {
714  return nullptr;
715  }
716  break;
717  }
718  }
719 
720  NodePtr parent = n->parentNode();
721  if (!parent || parent == m_rootNode) {
722  return nullptr;
723  }
724 
725  if (isAccepted(parent, filterException) == NodeFilter::FILTER_ACCEPT) {
726  return nullptr;
727  }
728  if (filterException) {
729  return nullptr;
730  }
731 
732  return getPreviousSibling(parent, filterException);
733 }
734 
CustomNodeFilter can be used to define your own NodeFilter for use with NodeIterators and TreeWalkers...
The Node interface is the primary datatype for the entire Document Object Model.
Definition: dom_node.h:278
MESSAGECORE_EXPORT KMime::Content * next(KMime::Content *node, bool allowChildren=true)
This library provides a full-featured HTML parser and widget.
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Mon Oct 25 2021 22:48:13 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.