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 <type_traits> 11 #include "core/fxcrt/unowned_ptr.h" 12 #include "v8/include/cppgc/macros.h" 13 #include "v8/include/cppgc/type-traits.h" 14 15 template <class NodeType, 16 class TraverseStrategy, 17 typename HolderType = std::conditional_t< 18 cppgc::IsGarbageCollectedOrMixinTypeV<NodeType>, 19 NodeType*, 20 UnownedPtr<NodeType>>> 21 class CXFA_NodeIteratorTemplate { 22 CPPGC_STACK_ALLOCATED(); // Allows Raw/Unowned |HolderType|. 23 24 public: CXFA_NodeIteratorTemplate(NodeType * pRoot)25 explicit CXFA_NodeIteratorTemplate(NodeType* pRoot) 26 : m_pRoot(pRoot), m_pCurrent(pRoot) {} 27 GetRoot()28 NodeType* GetRoot() const { return static_cast<NodeType*>(m_pRoot); } GetCurrent()29 NodeType* GetCurrent() const { return static_cast<NodeType*>(m_pCurrent); } 30 Reset()31 void Reset() { m_pCurrent = m_pRoot; } SetCurrent(NodeType * pNode)32 bool SetCurrent(NodeType* pNode) { 33 if (!RootReachableFromNode(pNode)) { 34 m_pCurrent = nullptr; 35 return false; 36 } 37 m_pCurrent = pNode; 38 return true; 39 } 40 MoveToPrev()41 NodeType* MoveToPrev() { 42 if (!m_pRoot) 43 return nullptr; 44 if (!m_pCurrent) { 45 m_pCurrent = LastDescendant(static_cast<NodeType*>(m_pRoot)); 46 return static_cast<NodeType*>(m_pCurrent); 47 } 48 NodeType* pSibling = 49 PreviousSiblingWithinSubtree(static_cast<NodeType*>(m_pCurrent)); 50 if (pSibling) { 51 m_pCurrent = LastDescendant(pSibling); 52 return static_cast<NodeType*>(m_pCurrent); 53 } 54 NodeType* pParent = ParentWithinSubtree(static_cast<NodeType*>(m_pCurrent)); 55 if (pParent) 56 m_pCurrent = pParent; 57 return pParent; 58 } 59 MoveToNext()60 NodeType* MoveToNext() { 61 if (!m_pRoot || !m_pCurrent) 62 return nullptr; 63 NodeType* pChild = 64 TraverseStrategy::GetFirstChild(static_cast<NodeType*>(m_pCurrent)); 65 if (pChild) { 66 m_pCurrent = pChild; 67 return pChild; 68 } 69 return SkipChildrenAndMoveToNext(); 70 } 71 SkipChildrenAndMoveToNext()72 NodeType* SkipChildrenAndMoveToNext() { 73 if (!m_pRoot) 74 return nullptr; 75 NodeType* pNode = static_cast<NodeType*>(m_pCurrent); 76 while (pNode) { 77 NodeType* pSibling = NextSiblingWithinSubtree(pNode); 78 if (pSibling) { 79 m_pCurrent = pSibling; 80 return pSibling; 81 } 82 pNode = ParentWithinSubtree(pNode); 83 } 84 m_pCurrent = nullptr; 85 return nullptr; 86 } 87 88 private: RootReachableFromNode(NodeType * pNode)89 bool RootReachableFromNode(NodeType* pNode) { 90 return pNode && (pNode == m_pRoot || 91 RootReachableFromNode(TraverseStrategy::GetParent(pNode))); 92 } 93 ParentWithinSubtree(NodeType * pNode)94 NodeType* ParentWithinSubtree(NodeType* pNode) { 95 return pNode && pNode != m_pRoot ? TraverseStrategy::GetParent(pNode) 96 : nullptr; 97 } 98 NextSiblingWithinSubtree(NodeType * pNode)99 NodeType* NextSiblingWithinSubtree(NodeType* pNode) { 100 return pNode != m_pRoot ? TraverseStrategy::GetNextSibling(pNode) : nullptr; 101 } 102 PreviousSiblingWithinSubtree(NodeType * pNode)103 NodeType* PreviousSiblingWithinSubtree(NodeType* pNode) { 104 NodeType* pParent = ParentWithinSubtree(pNode); 105 if (!pParent) 106 return nullptr; 107 NodeType* pCurrent = TraverseStrategy::GetFirstChild(pParent); 108 NodeType* pPrevious = nullptr; 109 while (pCurrent != pNode) { 110 pPrevious = pCurrent; 111 pCurrent = TraverseStrategy::GetNextSibling(pCurrent); 112 } 113 return pPrevious; 114 } 115 LastChild(NodeType * pNode)116 NodeType* LastChild(NodeType* pNode) { 117 NodeType* pPrevious = nullptr; 118 NodeType* pChild = TraverseStrategy::GetFirstChild(pNode); 119 while (pChild) { 120 pPrevious = pChild; 121 pChild = NextSiblingWithinSubtree(pChild); 122 } 123 return pPrevious; 124 } 125 LastDescendant(NodeType * pNode)126 NodeType* LastDescendant(NodeType* pNode) { 127 NodeType* pChild = LastChild(pNode); 128 return pChild ? LastDescendant(pChild) : pNode; 129 } 130 131 HolderType m_pRoot; 132 HolderType m_pCurrent; 133 }; 134 135 #endif // XFA_FXFA_PARSER_CXFA_NODEITERATORTEMPLATE_H_ 136