layout/generic/nsFrameList.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
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "nsFrameList.h"
   8
   9 #include "mozilla/intl/BidiEmbeddingLevel.h"
  10 #include "mozilla/ArenaObjectID.h"
  11 #include "mozilla/PresShell.h"
  12 #include "nsBidiPresUtils.h"
  13 #include "nsContainerFrame.h"
  14 #include "nsGkAtoms.h"
  15 #include "nsILineIterator.h"
  16 #include "nsLayoutUtils.h"
  17 #include "nsPresContext.h"
  18
  19 using namespace mozilla;
  20
  21 namespace mozilla {
  22 namespace detail {
  23 const AlignedFrameListBytes gEmptyFrameListBytes = {0};
  24 }  // namespace detail
  25 }  // namespace mozilla
  26
  27 void* nsFrameList::operator new(size_t sz, mozilla::PresShell* aPresShell) {
  28   return aPresShell->AllocateByObjectID(eArenaObjectID_nsFrameList, sz);
  29 }
  30
  31 void nsFrameList::Delete(mozilla::PresShell* aPresShell) {
  32   MOZ_ASSERT(this != &EmptyList(), "Shouldn't Delete() this list");
  33   NS_ASSERTION(IsEmpty(), "Shouldn't Delete() a non-empty list");
  34
  35   aPresShell->FreeByObjectID(eArenaObjectID_nsFrameList, this);
  36 }
  37
  38 void nsFrameList::DestroyFrames(FrameDestroyContext& aContext) {
  39   while (nsIFrame* frame = RemoveFirstChild()) {
  40     frame->Destroy(aContext);
  41   }
  42   mLastChild = nullptr;
  43 }
  44
  45 void nsFrameList::RemoveFrame(nsIFrame* aFrame) {
  46   MOZ_ASSERT(aFrame, "null ptr");
  47 #ifdef DEBUG_FRAME_LIST
  48   // ContainsFrame is O(N)
  49   MOZ_ASSERT(ContainsFrame(aFrame), "wrong list");
  50 #endif
  51
  52   nsIFrame* nextFrame = aFrame->GetNextSibling();
  53   if (aFrame == mFirstChild) {
  54     mFirstChild = nextFrame;
  55     aFrame->SetNextSibling(nullptr);
  56     if (!nextFrame) {
  57       mLastChild = nullptr;
  58     }
  59   } else {
  60     nsIFrame* prevSibling = aFrame->GetPrevSibling();
  61     NS_ASSERTION(prevSibling && prevSibling->GetNextSibling() == aFrame,
  62                  "Broken frame linkage");
  63     prevSibling->SetNextSibling(nextFrame);
  64     aFrame->SetNextSibling(nullptr);
  65     if (!nextFrame) {
  66       mLastChild = prevSibling;
  67     }
  68   }
  69 }
  70
  71 nsFrameList nsFrameList::TakeFramesAfter(nsIFrame* aFrame) {
  72   if (!aFrame) {
  73     return std::move(*this);
  74   }
  75
  76   MOZ_ASSERT(ContainsFrame(aFrame), "aFrame is not on this list!");
  77
  78   nsIFrame* newFirstChild = aFrame->GetNextSibling();
  79   if (!newFirstChild) {
  80     return nsFrameList();
  81   }
  82
  83   nsIFrame* newLastChild = mLastChild;
  84   mLastChild = aFrame;
  85   mLastChild->SetNextSibling(nullptr);
  86   return nsFrameList(newFirstChild, newLastChild);
  87 }
  88
  89 nsIFrame* nsFrameList::RemoveFirstChild() {
  90   if (mFirstChild) {
  91     nsIFrame* firstChild = mFirstChild;
  92     RemoveFrame(firstChild);
  93     return firstChild;
  94   }
  95   return nullptr;
  96 }
  97
  98 void nsFrameList::DestroyFrame(FrameDestroyContext& aContext,
  99                                nsIFrame* aFrame) {
 100   MOZ_ASSERT(aFrame, "null ptr");
 101   RemoveFrame(aFrame);
 102   aFrame->Destroy(aContext);
 103 }
 104
 105 nsFrameList::Slice nsFrameList::InsertFrames(nsContainerFrame* aParent,
 106                                              nsIFrame* aPrevSibling,
 107                                              nsFrameList&& aFrameList) {
 108   MOZ_ASSERT(aFrameList.NotEmpty(), "Unexpected empty list");
 109
 110   if (aParent) {
 111     aFrameList.ApplySetParent(aParent);
 112   }
 113
 114   NS_ASSERTION(IsEmpty() || FirstChild()->GetParent() ==
 115                                 aFrameList.FirstChild()->GetParent(),
 116                "frame to add has different parent");
 117   NS_ASSERTION(!aPrevSibling || aPrevSibling->GetParent() ==
 118                                     aFrameList.FirstChild()->GetParent(),
 119                "prev sibling has different parent");
 120 #ifdef DEBUG_FRAME_LIST
 121   // ContainsFrame is O(N)
 122   NS_ASSERTION(!aPrevSibling || ContainsFrame(aPrevSibling),
 123                "prev sibling is not on this list");
 124 #endif
 125
 126   nsIFrame* firstNewFrame = aFrameList.FirstChild();
 127   nsIFrame* nextSibling;
 128   if (aPrevSibling) {
 129     nextSibling = aPrevSibling->GetNextSibling();
 130     aPrevSibling->SetNextSibling(firstNewFrame);
 131   } else {
 132     nextSibling = mFirstChild;
 133     mFirstChild = firstNewFrame;
 134   }
 135
 136   nsIFrame* lastNewFrame = aFrameList.LastChild();
 137   lastNewFrame->SetNextSibling(nextSibling);
 138   if (!nextSibling) {
 139     mLastChild = lastNewFrame;
 140   }
 141
 142   VerifyList();
 143
 144   aFrameList.Clear();
 145   return Slice(firstNewFrame, nextSibling);
 146 }
 147
 148 nsFrameList nsFrameList::TakeFramesBefore(nsIFrame* aFrame) {
 149   if (!aFrame) {
 150     // We handed over the whole list.
 151     return std::move(*this);
 152   }
 153
 154   MOZ_ASSERT(ContainsFrame(aFrame), "aFrame is not on this list!");
 155
 156   if (aFrame == mFirstChild) {
 157     // aFrame is our first child. Nothing to extract.
 158     return nsFrameList();
 159   }
 160
 161   // Extract all previous siblings of aFrame as a new list.
 162   nsIFrame* prev = aFrame->GetPrevSibling();
 163   nsIFrame* newFirstChild = mFirstChild;
 164   nsIFrame* newLastChild = prev;
 165
 166   prev->SetNextSibling(nullptr);
 167   mFirstChild = aFrame;
 168
 169   return nsFrameList(newFirstChild, newLastChild);
 170 }
 171
 172 nsIFrame* nsFrameList::FrameAt(int32_t aIndex) const {
 173   MOZ_ASSERT(aIndex >= 0, "invalid arg");
 174   if (aIndex < 0) return nullptr;
 175   nsIFrame* frame = mFirstChild;
 176   while ((aIndex-- > 0) && frame) {
 177     frame = frame->GetNextSibling();
 178   }
 179   return frame;
 180 }
 181
 182 int32_t nsFrameList::IndexOf(nsIFrame* aFrame) const {
 183   int32_t count = 0;
 184   for (nsIFrame* f = mFirstChild; f; f = f->GetNextSibling()) {
 185     if (f == aFrame) return count;
 186     ++count;
 187   }
 188   return -1;
 189 }
 190
 191 bool nsFrameList::ContainsFrame(const nsIFrame* aFrame) const {
 192   MOZ_ASSERT(aFrame, "null ptr");
 193
 194   nsIFrame* frame = mFirstChild;
 195   while (frame) {
 196     if (frame == aFrame) {
 197       return true;
 198     }
 199     frame = frame->GetNextSibling();
 200   }
 201   return false;
 202 }
 203
 204 int32_t nsFrameList::GetLength() const {
 205   int32_t count = 0;
 206   nsIFrame* frame = mFirstChild;
 207   while (frame) {
 208     count++;
 209     frame = frame->GetNextSibling();
 210   }
 211   return count;
 212 }
 213
 214 void nsFrameList::ApplySetParent(nsContainerFrame* aParent) const {
 215   NS_ASSERTION(aParent, "null ptr");
 216
 217   for (nsIFrame* f = FirstChild(); f; f = f->GetNextSibling()) {
 218     f->SetParent(aParent);
 219   }
 220 }
 221
 222 /* static */
 223 void nsFrameList::UnhookFrameFromSiblings(nsIFrame* aFrame) {
 224   MOZ_ASSERT(aFrame->GetPrevSibling() && aFrame->GetNextSibling());
 225   nsIFrame* const nextSibling = aFrame->GetNextSibling();
 226   nsIFrame* const prevSibling = aFrame->GetPrevSibling();
 227   aFrame->SetNextSibling(nullptr);
 228   prevSibling->SetNextSibling(nextSibling);
 229   MOZ_ASSERT(!aFrame->GetPrevSibling() && !aFrame->GetNextSibling());
 230 }
 231
 232 #ifdef DEBUG_FRAME_DUMP
 233 void nsFrameList::List(FILE* out) const {
 234   fprintf_stderr(out, "<\n");
 235   for (nsIFrame* frame = mFirstChild; frame; frame = frame->GetNextSibling()) {
 236     frame->List(out, "  ");
 237   }
 238   fprintf_stderr(out, ">\n");
 239 }
 240 #endif
 241
 242 nsIFrame* nsFrameList::GetPrevVisualFor(nsIFrame* aFrame) const {
 243   if (!mFirstChild) return nullptr;
 244
 245   nsIFrame* parent = mFirstChild->GetParent();
 246   if (!parent) return aFrame ? aFrame->GetPrevSibling() : LastChild();
 247
 248   mozilla::intl::BidiDirection paraDir =
 249       nsBidiPresUtils::ParagraphDirection(mFirstChild);
 250
 251   AutoAssertNoDomMutations guard;
 252   nsILineIterator* iter = parent->GetLineIterator();
 253   if (!iter) {
 254     // Parent is not a block Frame
 255     if (parent->IsLineFrame()) {
 256       // Line frames are not bidi-splittable, so need to consider bidi
 257       // reordering
 258       if (paraDir == mozilla::intl::BidiDirection::LTR) {
 259         return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
 260       } else {  // RTL
 261         return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
 262       }
 263     } else {
 264       // Just get the next or prev sibling, depending on block and frame
 265       // direction.
 266       if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild)) {
 267         return aFrame ? aFrame->GetPrevSibling() : LastChild();
 268       } else {
 269         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 270       }
 271     }
 272   }
 273
 274   // Parent is a block frame, so use the LineIterator to find the previous
 275   // visual sibling on this line, or the last one on the previous line.
 276
 277   int32_t thisLine;
 278   if (aFrame) {
 279     thisLine = iter->FindLineContaining(aFrame);
 280     if (thisLine < 0) return nullptr;
 281   } else {
 282     thisLine = iter->GetNumLines();
 283   }
 284
 285   nsIFrame* frame = nullptr;
 286
 287   if (aFrame) {
 288     auto line = iter->GetLine(thisLine).unwrap();
 289
 290     if (paraDir == mozilla::intl::BidiDirection::LTR) {
 291       frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, line.mFirstFrameOnLine,
 292                                                 line.mNumFramesOnLine);
 293     } else {  // RTL
 294       frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, line.mFirstFrameOnLine,
 295                                                  line.mNumFramesOnLine);
 296     }
 297   }
 298
 299   if (!frame && thisLine > 0) {
 300     // Get the last frame of the previous line
 301     auto line = iter->GetLine(thisLine - 1).unwrap();
 302
 303     if (paraDir == mozilla::intl::BidiDirection::LTR) {
 304       frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, line.mFirstFrameOnLine,
 305                                                 line.mNumFramesOnLine);
 306     } else {  // RTL
 307       frame = nsBidiPresUtils::GetFrameToRightOf(
 308           nullptr, line.mFirstFrameOnLine, line.mNumFramesOnLine);
 309     }
 310   }
 311   return frame;
 312 }
 313
 314 nsIFrame* nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const {
 315   if (!mFirstChild) return nullptr;
 316
 317   nsIFrame* parent = mFirstChild->GetParent();
 318   if (!parent) return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
 319
 320   mozilla::intl::BidiDirection paraDir =
 321       nsBidiPresUtils::ParagraphDirection(mFirstChild);
 322
 323   AutoAssertNoDomMutations guard;
 324   nsILineIterator* iter = parent->GetLineIterator();
 325   if (!iter) {
 326     // Parent is not a block Frame
 327     if (parent->IsLineFrame()) {
 328       // Line frames are not bidi-splittable, so need to consider bidi
 329       // reordering
 330       if (paraDir == mozilla::intl::BidiDirection::LTR) {
 331         return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
 332       } else {  // RTL
 333         return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
 334       }
 335     } else {
 336       // Just get the next or prev sibling, depending on block and frame
 337       // direction.
 338       if (nsBidiPresUtils::IsFrameInParagraphDirection(mFirstChild)) {
 339         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 340       } else {
 341         return aFrame ? aFrame->GetPrevSibling() : LastChild();
 342       }
 343     }
 344   }
 345
 346   // Parent is a block frame, so use the LineIterator to find the next visual
 347   // sibling on this line, or the first one on the next line.
 348
 349   int32_t thisLine;
 350   if (aFrame) {
 351     thisLine = iter->FindLineContaining(aFrame);
 352     if (thisLine < 0) return nullptr;
 353   } else {
 354     thisLine = -1;
 355   }
 356
 357   nsIFrame* frame = nullptr;
 358
 359   if (aFrame) {
 360     auto line = iter->GetLine(thisLine).unwrap();
 361
 362     if (paraDir == mozilla::intl::BidiDirection::LTR) {
 363       frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, line.mFirstFrameOnLine,
 364                                                  line.mNumFramesOnLine);
 365     } else {  // RTL
 366       frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, line.mFirstFrameOnLine,
 367                                                 line.mNumFramesOnLine);
 368     }
 369   }
 370
 371   int32_t numLines = iter->GetNumLines();
 372   if (!frame && thisLine < numLines - 1) {
 373     // Get the first frame of the next line
 374     auto line = iter->GetLine(thisLine + 1).unwrap();
 375
 376     if (paraDir == mozilla::intl::BidiDirection::LTR) {
 377       frame = nsBidiPresUtils::GetFrameToRightOf(
 378           nullptr, line.mFirstFrameOnLine, line.mNumFramesOnLine);
 379     } else {  // RTL
 380       frame = nsBidiPresUtils::GetFrameToLeftOf(nullptr, line.mFirstFrameOnLine,
 381                                                 line.mNumFramesOnLine);
 382     }
 383   }
 384   return frame;
 385 }
 386
 387 #ifdef DEBUG_FRAME_LIST
 388 void nsFrameList::VerifyList() const {
 389   NS_ASSERTION((mFirstChild == nullptr) == (mLastChild == nullptr),
 390                "bad list state");
 391
 392   if (IsEmpty()) {
 393     return;
 394   }
 395
 396   // Simple algorithm to find a loop in a linked list -- advance pointers
 397   // through it at speeds of 1 and 2, and if they ever get to be equal bail
 398   NS_ASSERTION(!mFirstChild->GetPrevSibling(), "bad prev sibling pointer");
 399   nsIFrame *first = mFirstChild, *second = mFirstChild;
 400   for (;;) {
 401     first = first->GetNextSibling();
 402     second = second->GetNextSibling();
 403     if (!second) {
 404       break;
 405     }
 406     NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
 407                  "bad prev sibling pointer");
 408     second = second->GetNextSibling();
 409     if (first == second) {
 410       // Loop detected!  Since second advances faster, they can't both be null;
 411       // we would have broken out of the loop long ago.
 412       NS_ERROR("loop in frame list.  This will probably hang soon.");
 413       return;
 414     }
 415     if (!second) {
 416       break;
 417     }
 418     NS_ASSERTION(second->GetPrevSibling()->GetNextSibling() == second,
 419                  "bad prev sibling pointer");
 420   }
 421
 422   NS_ASSERTION(mLastChild == nsLayoutUtils::GetLastSibling(mFirstChild),
 423                "bogus mLastChild");
 424   // XXX we should also assert that all GetParent() are either null or
 425   // the same non-null value, but nsCSSFrameConstructor::nsFrameItems
 426   // prevents that, e.g. table captions.
 427 }
 428 #endif
 429
 430 namespace mozilla {
 431
 432 #ifdef DEBUG_FRAME_DUMP
 433 const char* ChildListName(FrameChildListID aListID) {
 434   switch (aListID) {
 435     case FrameChildListID::Principal:
 436       return "";
 437     case FrameChildListID::Popup:
 438       return "PopupList";
 439     case FrameChildListID::Caption:
 440       return "CaptionList";
 441     case FrameChildListID::ColGroup:
 442       return "ColGroupList";
 443     case FrameChildListID::Absolute:
 444       return "AbsoluteList";
 445     case FrameChildListID::Fixed:
 446       return "FixedList";
 447     case FrameChildListID::Overflow:
 448       return "OverflowList";
 449     case FrameChildListID::OverflowContainers:
 450       return "OverflowContainersList";
 451     case FrameChildListID::ExcessOverflowContainers:
 452       return "ExcessOverflowContainersList";
 453     case FrameChildListID::OverflowOutOfFlow:
 454       return "OverflowOutOfFlowList";
 455     case FrameChildListID::Float:
 456       return "FloatList";
 457     case FrameChildListID::Bullet:
 458       return "BulletList";
 459     case FrameChildListID::PushedFloats:
 460       return "PushedFloatsList";
 461     case FrameChildListID::Backdrop:
 462       return "BackdropList";
 463     case FrameChildListID::NoReflowPrincipal:
 464       return "NoReflowPrincipalList";
 465   }
 466
 467   MOZ_ASSERT_UNREACHABLE("unknown list");
 468   return "UNKNOWN_FRAME_CHILD_LIST";
 469 }
 470 #endif
 471
 472 AutoFrameListPtr::~AutoFrameListPtr() {
 473   if (mFrameList) {
 474     mFrameList->Delete(mPresContext->PresShell());
 475   }
 476 }
 477
 478 }  // namespace mozilla