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