layout/generic/nsFrameList.cpp

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