1 // Copyright 2017 The PDFium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7 #ifndef XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_ 8 #define XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_ 9 10 #include "core/fxcrt/unowned_ptr.h" 11 #include "v8/include/cppgc/macros.h" 12 13 template <class NodeType, 14 class TraverseStrategy, 15 typename HolderType = UnownedPtr<NodeType>> 16 class CXFA_NodeIteratorTemplate { 17 CPPGC_STACK_ALLOCATED(); // Allows Raw/Unowned |HolderType|. 18 19 public: CXFA_NodeIteratorTemplate(NodeType * pRoot)20 explicit CXFA_NodeIteratorTemplate(NodeType* pRoot) 21 : m_pRoot(pRoot), m_pCurrent(pRoot) {} 22 GetRoot()23 NodeType* GetRoot() const { return static_cast<NodeType*>(m_pRoot); } GetCurrent()24 NodeType* GetCurrent() const { return static_cast<NodeType*>(m_pCurrent); } 25 Reset()26 void Reset() { m_pCurrent = m_pRoot; } SetCurrent(NodeType * pNode)27 bool SetCurrent(NodeType* pNode) { 28 if (!RootReachableFromNode(pNode)) { 29 m_pCurrent = nullptr; 30 return false; 31 } 32 m_pCurrent = pNode; 33 return true; 34 } 35 MoveToPrev()36 NodeType* MoveToPrev() { 37 if (!m_pRoot) 38 return nullptr; 39 if (!m_pCurrent) { 40 m_pCurrent = LastDescendant(static_cast<NodeType*>(m_pRoot)); 41 return static_cast<NodeType*>(m_pCurrent); 42 } 43 NodeType* pSibling = 44 PreviousSiblingWithinSubtree(static_cast<NodeType*>(m_pCurrent)); 45 if (pSibling) { 46 m_pCurrent = LastDescendant(pSibling); 47 return static_cast<NodeType*>(m_pCurrent); 48 } 49 NodeType* pParent = ParentWithinSubtree(static_cast<NodeType*>(m_pCurrent)); 50 if (pParent) 51 m_pCurrent = pParent; 52 return pParent; 53 } 54 MoveToNext()55 NodeType* MoveToNext() { 56 if (!m_pRoot || !m_pCurrent) 57 return nullptr; 58 NodeType* pChild = 59 TraverseStrategy::GetFirstChild(static_cast<NodeType*>(m_pCurrent)); 60 if (pChild) { 61 m_pCurrent = pChild; 62 return pChild; 63 } 64 return SkipChildrenAndMoveToNext(); 65 } 66 SkipChildrenAndMoveToNext()67 NodeType* SkipChildrenAndMoveToNext() { 68 if (!m_pRoot) 69 return nullptr; 70 NodeType* pNode = static_cast<NodeType*>(m_pCurrent); 71 while (pNode) { 72 NodeType* pSibling = NextSiblingWithinSubtree(pNode); 73 if (pSibling) { 74 m_pCurrent = pSibling; 75 return pSibling; 76 } 77 pNode = ParentWithinSubtree(pNode); 78 } 79 m_pCurrent = nullptr; 80 return nullptr; 81 } 82 83 private: RootReachableFromNode(NodeType * pNode)84 bool RootReachableFromNode(NodeType* pNode) { 85 return pNode && (pNode == m_pRoot || 86 RootReachableFromNode(TraverseStrategy::GetParent(pNode))); 87 } 88 ParentWithinSubtree(NodeType * pNode)89 NodeType* ParentWithinSubtree(NodeType* pNode) { 90 return pNode && pNode != m_pRoot ? TraverseStrategy::GetParent(pNode) 91 : nullptr; 92 } 93 NextSiblingWithinSubtree(NodeType * pNode)94 NodeType* NextSiblingWithinSubtree(NodeType* pNode) { 95 return pNode != m_pRoot ? TraverseStrategy::GetNextSibling(pNode) : nullptr; 96 } 97 PreviousSiblingWithinSubtree(NodeType * pNode)98 NodeType* PreviousSiblingWithinSubtree(NodeType* pNode) { 99 NodeType* pParent = ParentWithinSubtree(pNode); 100 if (!pParent) 101 return nullptr; 102 NodeType* pCurrent = TraverseStrategy::GetFirstChild(pParent); 103 NodeType* pPrevious = nullptr; 104 while (pCurrent != pNode) { 105 pPrevious = pCurrent; 106 pCurrent = TraverseStrategy::GetNextSibling(pCurrent); 107 } 108 return pPrevious; 109 } 110 LastChild(NodeType * pNode)111 NodeType* LastChild(NodeType* pNode) { 112 NodeType* pPrevious = nullptr; 113 NodeType* pChild = TraverseStrategy::GetFirstChild(pNode); 114 while (pChild) { 115 pPrevious = pChild; 116 pChild = NextSiblingWithinSubtree(pChild); 117 } 118 return pPrevious; 119 } 120 LastDescendant(NodeType * pNode)121 NodeType* LastDescendant(NodeType* pNode) { 122 NodeType* pChild = LastChild(pNode); 123 return pChild ? LastDescendant(pChild) : pNode; 124 } 125 126 HolderType m_pRoot; 127 HolderType m_pCurrent; 128 }; 129 130 #endif // XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_ 131