dom/base/ChildIterator.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "ChildIterator.h"
   8 #include "nsContentUtils.h"
   9 #include "mozilla/dom/Document.h"
  10 #include "mozilla/dom/HTMLSlotElement.h"
  11 #include "mozilla/dom/ShadowRoot.h"
  12 #include "nsIAnonymousContentCreator.h"
  13 #include "nsIFrame.h"
  14 #include "nsCSSAnonBoxes.h"
  15 #include "nsLayoutUtils.h"
  16
  17 namespace mozilla::dom {
  18
  19 FlattenedChildIterator::FlattenedChildIterator(const nsIContent* aParent,
  20                                                bool aStartAtBeginning)
  21     : mParent(aParent), mOriginalParent(aParent), mIsFirst(aStartAtBeginning) {
  22   if (!mParent->IsElement()) {
  23     // TODO(emilio): I think it probably makes sense to only allow constructing
  24     // FlattenedChildIterators with Element.
  25     return;
  26   }
  27
  28   if (ShadowRoot* shadow = mParent->AsElement()->GetShadowRoot()) {
  29     mParent = shadow;
  30     mShadowDOMInvolved = true;
  31     return;
  32   }
  33
  34   if (const auto* slot = HTMLSlotElement::FromNode(mParent)) {
  35     if (!slot->AssignedNodes().IsEmpty()) {
  36       mParentAsSlot = slot;
  37       if (!aStartAtBeginning) {
  38         mIndexInInserted = slot->AssignedNodes().Length();
  39       }
  40       mShadowDOMInvolved = true;
  41     }
  42   }
  43 }
  44
  45 nsIContent* FlattenedChildIterator::GetNextChild() {
  46   // If we're already in the inserted-children array, look there first
  47   if (mParentAsSlot) {
  48     const nsTArray<RefPtr<nsINode>>& assignedNodes =
  49         mParentAsSlot->AssignedNodes();
  50     if (mIsFirst) {
  51       mIsFirst = false;
  52       MOZ_ASSERT(mIndexInInserted == 0);
  53       mChild = assignedNodes[0]->AsContent();
  54       return mChild;
  55     }
  56     MOZ_ASSERT(mIndexInInserted <= assignedNodes.Length());
  57     if (mIndexInInserted + 1 >= assignedNodes.Length()) {
  58       mIndexInInserted = assignedNodes.Length();
  59       return nullptr;
  60     }
  61     mChild = assignedNodes[++mIndexInInserted]->AsContent();
  62     return mChild;
  63   }
  64
  65   if (mIsFirst) {  // at the beginning of the child list
  66     mChild = mParent->GetFirstChild();
  67     mIsFirst = false;
  68   } else if (mChild) {  // in the middle of the child list
  69     mChild = mChild->GetNextSibling();
  70   }
  71
  72   return mChild;
  73 }
  74
  75 bool FlattenedChildIterator::Seek(const nsIContent* aChildToFind) {
  76   if (!mParentAsSlot && aChildToFind->GetParent() == mParent &&
  77       !aChildToFind->IsRootOfNativeAnonymousSubtree()) {
  78     // Fast path: just point ourselves to aChildToFind, which is a
  79     // normal DOM child of ours.
  80     mChild = const_cast<nsIContent*>(aChildToFind);
  81     mIndexInInserted = 0;
  82     mIsFirst = false;
  83     return true;
  84   }
  85
  86   // Can we add more fast paths here based on whether the parent of aChildToFind
  87   // is a This version can take shortcuts that the two-argument version
  88   // can't, so can be faster (and in fact cshadow insertion point or content
  89   // insertion point?
  90
  91   // It would be nice to assert that we find aChildToFind, but bz thinks that
  92   // we might not find aChildToFind when called from ContentInserted
  93   // if first-letter frames are about.
  94   while (nsIContent* child = GetNextChild()) {
  95     if (child == aChildToFind) {
  96       return true;
  97     }
  98   }
  99
 100   return false;
 101 }
 102
 103 nsIContent* FlattenedChildIterator::GetPreviousChild() {
 104   if (mIsFirst) {  // at the beginning of the child list
 105     return nullptr;
 106   }
 107   if (mParentAsSlot) {
 108     const nsTArray<RefPtr<nsINode>>& assignedNodes =
 109         mParentAsSlot->AssignedNodes();
 110     MOZ_ASSERT(mIndexInInserted <= assignedNodes.Length());
 111     if (mIndexInInserted == 0) {
 112       mIsFirst = true;
 113       return nullptr;
 114     }
 115     mChild = assignedNodes[--mIndexInInserted]->AsContent();
 116     return mChild;
 117   }
 118   if (mChild) {  // in the middle of the child list
 119     mChild = mChild->GetPreviousSibling();
 120   } else {  // at the end of the child list
 121     mChild = mParent->GetLastChild();
 122   }
 123   if (!mChild) {
 124     mIsFirst = true;
 125   }
 126
 127   return mChild;
 128 }
 129
 130 nsIContent* AllChildrenIterator::Get() const {
 131   switch (mPhase) {
 132     case eAtMarkerKid: {
 133       Element* marker = nsLayoutUtils::GetMarkerPseudo(Parent());
 134       MOZ_ASSERT(marker, "No content marker frame at eAtMarkerKid phase");
 135       return marker;
 136     }
 137
 138     case eAtBeforeKid: {
 139       Element* before = nsLayoutUtils::GetBeforePseudo(Parent());
 140       MOZ_ASSERT(before, "No content before frame at eAtBeforeKid phase");
 141       return before;
 142     }
 143
 144     case eAtFlatTreeKids:
 145       return FlattenedChildIterator::Get();
 146
 147     case eAtAnonKids:
 148       return mAnonKids[mAnonKidsIdx];
 149
 150     case eAtAfterKid: {
 151       Element* after = nsLayoutUtils::GetAfterPseudo(Parent());
 152       MOZ_ASSERT(after, "No content after frame at eAtAfterKid phase");
 153       return after;
 154     }
 155
 156     default:
 157       return nullptr;
 158   }
 159 }
 160
 161 bool AllChildrenIterator::Seek(const nsIContent* aChildToFind) {
 162   if (mPhase == eAtBegin || mPhase == eAtMarkerKid) {
 163     Element* markerPseudo = nsLayoutUtils::GetMarkerPseudo(Parent());
 164     if (markerPseudo && markerPseudo == aChildToFind) {
 165       mPhase = eAtMarkerKid;
 166       return true;
 167     }
 168     mPhase = eAtBeforeKid;
 169   }
 170   if (mPhase == eAtBeforeKid) {
 171     Element* beforePseudo = nsLayoutUtils::GetBeforePseudo(Parent());
 172     if (beforePseudo && beforePseudo == aChildToFind) {
 173       return true;
 174     }
 175     mPhase = eAtFlatTreeKids;
 176   }
 177
 178   if (mPhase == eAtFlatTreeKids) {
 179     if (FlattenedChildIterator::Seek(aChildToFind)) {
 180       return true;
 181     }
 182     mPhase = eAtAnonKids;
 183   }
 184
 185   nsIContent* child = nullptr;
 186   do {
 187     child = GetNextChild();
 188   } while (child && child != aChildToFind);
 189
 190   return child == aChildToFind;
 191 }
 192
 193 void AllChildrenIterator::AppendNativeAnonymousChildren() {
 194   nsContentUtils::AppendNativeAnonymousChildren(Parent(), mAnonKids, mFlags);
 195 }
 196
 197 nsIContent* AllChildrenIterator::GetNextChild() {
 198   if (mPhase == eAtBegin) {
 199     mPhase = eAtMarkerKid;
 200     if (Element* markerContent = nsLayoutUtils::GetMarkerPseudo(Parent())) {
 201       return markerContent;
 202     }
 203   }
 204
 205   if (mPhase == eAtMarkerKid) {
 206     mPhase = eAtBeforeKid;
 207     if (Element* beforeContent = nsLayoutUtils::GetBeforePseudo(Parent())) {
 208       return beforeContent;
 209     }
 210   }
 211
 212   if (mPhase == eAtBeforeKid) {
 213     // Advance into our explicit kids.
 214     mPhase = eAtFlatTreeKids;
 215   }
 216
 217   if (mPhase == eAtFlatTreeKids) {
 218     if (nsIContent* kid = FlattenedChildIterator::GetNextChild()) {
 219       return kid;
 220     }
 221     mPhase = eAtAnonKids;
 222   }
 223
 224   if (mPhase == eAtAnonKids) {
 225     if (mAnonKids.IsEmpty()) {
 226       MOZ_ASSERT(mAnonKidsIdx == UINT32_MAX);
 227       AppendNativeAnonymousChildren();
 228       mAnonKidsIdx = 0;
 229     } else {
 230       if (mAnonKidsIdx == UINT32_MAX) {
 231         mAnonKidsIdx = 0;
 232       } else {
 233         mAnonKidsIdx++;
 234       }
 235     }
 236
 237     if (mAnonKidsIdx < mAnonKids.Length()) {
 238       return mAnonKids[mAnonKidsIdx];
 239     }
 240
 241     mPhase = eAtAfterKid;
 242     if (Element* afterContent = nsLayoutUtils::GetAfterPseudo(Parent())) {
 243       return afterContent;
 244     }
 245   }
 246
 247   mPhase = eAtEnd;
 248   return nullptr;
 249 }
 250
 251 nsIContent* AllChildrenIterator::GetPreviousChild() {
 252   if (mPhase == eAtEnd) {
 253     MOZ_ASSERT(mAnonKidsIdx == mAnonKids.Length());
 254     mPhase = eAtAnonKids;
 255     Element* afterContent = nsLayoutUtils::GetAfterPseudo(Parent());
 256     if (afterContent) {
 257       mPhase = eAtAfterKid;
 258       return afterContent;
 259     }
 260   }
 261
 262   if (mPhase == eAtAfterKid) {
 263     mPhase = eAtAnonKids;
 264   }
 265
 266   if (mPhase == eAtAnonKids) {
 267     if (mAnonKids.IsEmpty()) {
 268       AppendNativeAnonymousChildren();
 269       mAnonKidsIdx = mAnonKids.Length();
 270     }
 271
 272     // If 0 then it turns into UINT32_MAX, which indicates the iterator is
 273     // before the anonymous children.
 274     --mAnonKidsIdx;
 275     if (mAnonKidsIdx < mAnonKids.Length()) {
 276       return mAnonKids[mAnonKidsIdx];
 277     }
 278     mPhase = eAtFlatTreeKids;
 279   }
 280
 281   if (mPhase == eAtFlatTreeKids) {
 282     if (nsIContent* kid = FlattenedChildIterator::GetPreviousChild()) {
 283       return kid;
 284     }
 285
 286     Element* beforeContent = nsLayoutUtils::GetBeforePseudo(Parent());
 287     if (beforeContent) {
 288       mPhase = eAtBeforeKid;
 289       return beforeContent;
 290     }
 291   }
 292
 293   if (mPhase == eAtFlatTreeKids || mPhase == eAtBeforeKid) {
 294     Element* markerContent = nsLayoutUtils::GetMarkerPseudo(Parent());
 295     if (markerContent) {
 296       mPhase = eAtMarkerKid;
 297       return markerContent;
 298     }
 299   }
 300
 301   mPhase = eAtBegin;
 302   return nullptr;
 303 }
 304
 305 }  // namespace mozilla::dom