FlattenedTreeIterator. draft
authorEmilio Cobos Álvarez <emilio@crisal.io>
Mon, 25 Jun 2018 10:37:44 +0200
changeset 810135 6ece2cf8ccc38205f9825ec20dcf46c202e003d8
parent 810134 9ef7d1f391695788c597b75041d6b4ae719cd59e
child 810136 9e656d327d9f8eb72756da15ca47b78e78e65976
push id113905
push userbmo:emilio@crisal.io
push dateMon, 25 Jun 2018 12:31:46 +0000
milestone62.0a1
FlattenedTreeIterator. MozReview-Commit-ID: IxYIqhRDLo4
dom/base/nsFocusManager.cpp
--- a/dom/base/nsFocusManager.cpp
+++ b/dom/base/nsFocusManager.cpp
@@ -3048,16 +3048,119 @@ nsFocusManager::DetermineElementToMoveFo
     // to, so just break out
     if (startContent == originalStartContent)
       break;
   }
 
   return NS_OK;
 }
 
+class MOZ_STACK_CLASS FlattenedTreeIterator
+{
+  enum class Direction
+  {
+    Forward,
+    Backwards,
+  };
+
+  template<Direction aDirection>
+  nsIContent* GetNextChild(FlattenedChildIterator& aIter)
+  {
+    return aDirection == Direction::Forward
+      ? aIter.GetNextChild()
+      : aIter.GetPreviousChild();
+  }
+
+  template<Direction> inline void Advance();
+  template<Direction> inline void AdvanceSkippingChildren();
+
+public:
+  explicit FlattenedTreeIterator(nsIContent& aRoot)
+    : mCurrent(&aRoot)
+  {
+  }
+
+  nsIContent* GetCurrent() const
+  {
+    return mCurrent;
+  }
+
+  inline nsIContent* GetNext();
+  inline nsIContent* GetNextSkippingChildren();
+  inline nsIContent* GetPrev();
+  inline nsIContent* GetPrevSkippingChildren();
+
+private:
+  nsIContent* mCurrent;
+  AutoTArray<FlattenedChildIterator, 30> mParentIterators;
+};
+
+template<FlattenedTreeIterator::Direction aDirection>
+inline void
+FlattenedTreeIterator::AdvanceSkippingChildren()
+{
+  while (true) {
+    if (MOZ_UNLIKELY(mParentIterators.IsEmpty())) {
+      mCurrent = nullptr;
+      return;
+    }
+
+    if (nsIContent* nextSibling =
+          GetNextChild<aDirection>(mParentIterators.LastElement())) {
+      mCurrent = nextSibling;
+      return;
+    }
+    mParentIterators.RemoveLastElement();
+  }
+}
+
+template<FlattenedTreeIterator::Direction aDirection>
+inline void
+FlattenedTreeIterator::Advance()
+{
+  MOZ_ASSERT(mCurrent);
+  const bool startAtBeginning = aDirection == Direction::Forward;
+  FlattenedChildIterator children(mCurrent, startAtBeginning);
+  if (nsIContent* first = GetNextChild<aDirection>(children)) {
+    mCurrent = first;
+    mParentIterators.AppendElement(std::move(children));
+    return;
+  }
+
+  AdvanceSkippingChildren<aDirection>();
+}
+
+inline nsIContent*
+FlattenedTreeIterator::GetNext()
+{
+  Advance<Direction::Forward>();
+  return GetCurrent();
+}
+
+inline nsIContent*
+FlattenedTreeIterator::GetPrev()
+{
+  Advance<Direction::Backwards>();
+  return GetCurrent();
+}
+
+inline nsIContent*
+FlattenedTreeIterator::GetNextSkippingChildren()
+{
+  AdvanceSkippingChildren<Direction::Forward>();
+  return GetCurrent();
+}
+
+inline nsIContent*
+FlattenedTreeIterator::GetPrevSkippingChildren()
+{
+  AdvanceSkippingChildren<Direction::Backwards>();
+  return GetCurrent();
+}
+
 // Helper class to iterate contents in scope by traversing flattened tree
 // in tree order
 class MOZ_STACK_CLASS ScopedContentTraversal
 {
 public:
   ScopedContentTraversal(nsIContent* aStartContent, nsIContent* aOwner)
     : mCurrent(aStartContent)
     , mOwner(aOwner)