layout/generic/nsLineBox.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 /* representation of one line within a block frame, a CSS line box */
   8
   9 #include "nsLineBox.h"
  10
  11 #include "mozilla/ArenaObjectID.h"
  12 #include "mozilla/Assertions.h"
  13 #include "mozilla/Likely.h"
  14 #include "mozilla/PresShell.h"
  15 #include "mozilla/Sprintf.h"
  16 #include "mozilla/WritingModes.h"
  17 #include "nsBidiPresUtils.h"
  18 #include "nsFrame.h"
  19 #include "nsIFrameInlines.h"
  20 #include "nsPresArena.h"
  21 #include "nsPrintfCString.h"
  22 #include "nsWindowSizes.h"
  23
  24 #ifdef DEBUG
  25 static int32_t ctorCount;
  26 int32_t nsLineBox::GetCtorCount() { return ctorCount; }
  27 #endif
  28
  29 #ifndef _MSC_VER
  30 // static nsLineBox constant; initialized in the header file.
  31 const uint32_t nsLineBox::kMinChildCountForHashtable;
  32 #endif
  33
  34 using namespace mozilla;
  35
  36 nsLineBox::nsLineBox(nsIFrame* aFrame, int32_t aCount, bool aIsBlock)
  37     : mFirstChild(aFrame),
  38       mWritingMode(),
  39       mContainerSize(-1, -1),
  40       mBounds(WritingMode()),  // mBounds will be initialized with the correct
  41                                // writing mode when it is set
  42       mFrames(),
  43       mAscent(),
  44       mAllFlags(0),
  45       mData(nullptr) {
  46   // Assert that the union elements chosen for initialisation are at
  47   // least as large as all other elements in their respective unions, so
  48   // as to ensure that no parts are missed.
  49   static_assert(sizeof(mFrames) >= sizeof(mChildCount), "nsLineBox init #1");
  50   static_assert(sizeof(mAllFlags) >= sizeof(mFlags), "nsLineBox init #2");
  51   static_assert(sizeof(mData) >= sizeof(mBlockData), "nsLineBox init #3");
  52   static_assert(sizeof(mData) >= sizeof(mInlineData), "nsLineBox init #4");
  53
  54   MOZ_COUNT_CTOR(nsLineBox);
  55 #ifdef DEBUG
  56   ++ctorCount;
  57   NS_ASSERTION(!aIsBlock || aCount == 1, "Blocks must have exactly one child");
  58   nsIFrame* f = aFrame;
  59   for (int32_t n = aCount; n > 0; f = f->GetNextSibling(), --n) {
  60     NS_ASSERTION(aIsBlock == f->IsBlockOutside(), "wrong kind of child frame");
  61   }
  62 #endif
  63   static_assert(static_cast<int>(StyleClear::Max) <= 15,
  64                 "FlagBits needs more bits to store the full range of "
  65                 "break type ('clear') values");
  66   mChildCount = aCount;
  67   MarkDirty();
  68   mFlags.mBlock = aIsBlock;
  69 }
  70
  71 nsLineBox::~nsLineBox() {
  72   MOZ_COUNT_DTOR(nsLineBox);
  73   if (MOZ_UNLIKELY(mFlags.mHasHashedFrames)) {
  74     delete mFrames;
  75   }
  76   Cleanup();
  77 }
  78
  79 nsLineBox* NS_NewLineBox(PresShell* aPresShell, nsIFrame* aFrame,
  80                          bool aIsBlock) {
  81   return new (aPresShell) nsLineBox(aFrame, 1, aIsBlock);
  82 }
  83
  84 nsLineBox* NS_NewLineBox(PresShell* aPresShell, nsLineBox* aFromLine,
  85                          nsIFrame* aFrame, int32_t aCount) {
  86   nsLineBox* newLine = new (aPresShell) nsLineBox(aFrame, aCount, false);
  87   newLine->NoteFramesMovedFrom(aFromLine);
  88   newLine->mContainerSize = aFromLine->mContainerSize;
  89   return newLine;
  90 }
  91
  92 void nsLineBox::AddSizeOfExcludingThis(nsWindowSizes& aSizes) const {
  93   if (mFlags.mHasHashedFrames) {
  94     aSizes.mLayoutFramePropertiesSize +=
  95         mFrames->ShallowSizeOfIncludingThis(aSizes.mState.mMallocSizeOf);
  96   }
  97 }
  98
  99 void nsLineBox::StealHashTableFrom(nsLineBox* aFromLine,
 100                                    uint32_t aFromLineNewCount) {
 101   MOZ_ASSERT(!mFlags.mHasHashedFrames);
 102   MOZ_ASSERT(GetChildCount() >= int32_t(aFromLineNewCount));
 103   mFrames = aFromLine->mFrames;
 104   mFlags.mHasHashedFrames = 1;
 105   aFromLine->mFlags.mHasHashedFrames = 0;
 106   aFromLine->mChildCount = aFromLineNewCount;
 107   // remove aFromLine's frames that aren't on this line
 108   nsIFrame* f = aFromLine->mFirstChild;
 109   for (uint32_t i = 0; i < aFromLineNewCount; f = f->GetNextSibling(), ++i) {
 110     mFrames->RemoveEntry(f);
 111   }
 112 }
 113
 114 void nsLineBox::NoteFramesMovedFrom(nsLineBox* aFromLine) {
 115   uint32_t fromCount = aFromLine->GetChildCount();
 116   uint32_t toCount = GetChildCount();
 117   MOZ_ASSERT(toCount <= fromCount, "moved more frames than aFromLine has");
 118   uint32_t fromNewCount = fromCount - toCount;
 119   if (MOZ_LIKELY(!aFromLine->mFlags.mHasHashedFrames)) {
 120     aFromLine->mChildCount = fromNewCount;
 121     MOZ_ASSERT(toCount < kMinChildCountForHashtable);
 122   } else if (fromNewCount < kMinChildCountForHashtable) {
 123     // aFromLine has a hash table but will not have it after moving the frames
 124     // so this line can steal the hash table if it needs it.
 125     if (toCount >= kMinChildCountForHashtable) {
 126       StealHashTableFrom(aFromLine, fromNewCount);
 127     } else {
 128       delete aFromLine->mFrames;
 129       aFromLine->mFlags.mHasHashedFrames = 0;
 130       aFromLine->mChildCount = fromNewCount;
 131     }
 132   } else {
 133     // aFromLine still needs a hash table.
 134     if (toCount < kMinChildCountForHashtable) {
 135       // remove the moved frames from it
 136       nsIFrame* f = mFirstChild;
 137       for (uint32_t i = 0; i < toCount; f = f->GetNextSibling(), ++i) {
 138         aFromLine->mFrames->RemoveEntry(f);
 139       }
 140     } else if (toCount <= fromNewCount) {
 141       // This line needs a hash table, allocate a hash table for it since that
 142       // means fewer hash ops.
 143       nsIFrame* f = mFirstChild;
 144       for (uint32_t i = 0; i < toCount; f = f->GetNextSibling(), ++i) {
 145         aFromLine->mFrames->RemoveEntry(f);  // toCount RemoveEntry
 146       }
 147       SwitchToHashtable();  // toCount PutEntry
 148     } else {
 149       // This line needs a hash table, but it's fewer hash ops to steal
 150       // aFromLine's hash table and allocate a new hash table for that line.
 151       StealHashTableFrom(aFromLine, fromNewCount);  // fromNewCount RemoveEntry
 152       aFromLine->SwitchToHashtable();               // fromNewCount PutEntry
 153     }
 154   }
 155 }
 156
 157 void* nsLineBox::operator new(size_t sz, PresShell* aPresShell) {
 158   return aPresShell->AllocateByObjectID(eArenaObjectID_nsLineBox, sz);
 159 }
 160
 161 void nsLineBox::Destroy(PresShell* aPresShell) {
 162   this->nsLineBox::~nsLineBox();
 163   aPresShell->FreeByObjectID(eArenaObjectID_nsLineBox, this);
 164 }
 165
 166 void nsLineBox::Cleanup() {
 167   if (mData) {
 168     if (IsBlock()) {
 169       delete mBlockData;
 170     } else {
 171       delete mInlineData;
 172     }
 173     mData = nullptr;
 174   }
 175 }
 176
 177 #ifdef DEBUG_FRAME_DUMP
 178 static void ListFloats(FILE* out, const char* aPrefix,
 179                        const nsFloatCacheList& aFloats) {
 180   nsFloatCache* fc = aFloats.Head();
 181   while (fc) {
 182     nsCString str(aPrefix);
 183     nsIFrame* frame = fc->mFloat;
 184     str += nsPrintfCString("floatframe@%p ", static_cast<void*>(frame));
 185     if (frame) {
 186       nsAutoString frameName;
 187       frame->GetFrameName(frameName);
 188       str += NS_ConvertUTF16toUTF8(frameName).get();
 189     } else {
 190       str += "\n###!!! NULL out-of-flow frame";
 191     }
 192     fprintf_stderr(out, "%s\n", str.get());
 193     fc = fc->Next();
 194   }
 195 }
 196
 197 /* static */ const char* nsLineBox::BreakTypeToString(StyleClear aBreakType) {
 198   switch (aBreakType) {
 199     case StyleClear::None:
 200       return "nobr";
 201     case StyleClear::Left:
 202       return "leftbr";
 203     case StyleClear::Right:
 204       return "rightbr";
 205     case StyleClear::Both:
 206       return "leftbr+rightbr";
 207     case StyleClear::Line:
 208       return "linebr";
 209     case StyleClear::Max:
 210       return "leftbr+rightbr+linebr";
 211   }
 212   return "unknown";
 213 }
 214
 215 char* nsLineBox::StateToString(char* aBuf, int32_t aBufSize) const {
 216   snprintf(aBuf, aBufSize, "%s,%s,%s,%s,%s,before:%s,after:%s[0x%x]",
 217            IsBlock() ? "block" : "inline", IsDirty() ? "dirty" : "clean",
 218            IsPreviousMarginDirty() ? "prevmargindirty" : "prevmarginclean",
 219            IsImpactedByFloat() ? "impacted" : "not impacted",
 220            IsLineWrapped() ? "wrapped" : "not wrapped",
 221            BreakTypeToString(GetBreakTypeBefore()),
 222            BreakTypeToString(GetBreakTypeAfter()), mAllFlags);
 223   return aBuf;
 224 }
 225
 226 void nsLineBox::List(FILE* out, int32_t aIndent, uint32_t aFlags) const {
 227   nsCString str;
 228   while (aIndent-- > 0) {
 229     str += "  ";
 230   }
 231   List(out, str.get(), aFlags);
 232 }
 233
 234 void nsLineBox::List(FILE* out, const char* aPrefix, uint32_t aFlags) const {
 235   nsCString str(aPrefix);
 236   char cbuf[100];
 237   str += nsPrintfCString("line %p: count=%d state=%s ",
 238                          static_cast<const void*>(this), GetChildCount(),
 239                          StateToString(cbuf, sizeof(cbuf)));
 240   if (IsBlock() && !GetCarriedOutBEndMargin().IsZero()) {
 241     str += nsPrintfCString("bm=%d ", GetCarriedOutBEndMargin().get());
 242   }
 243   nsRect bounds = GetPhysicalBounds();
 244   str += nsPrintfCString("{%d,%d,%d,%d} ", bounds.x, bounds.y, bounds.width,
 245                          bounds.height);
 246   if (mWritingMode.IsVertical() || !mWritingMode.IsBidiLTR()) {
 247     str +=
 248         nsPrintfCString("{%s: %d,%d,%d,%d; cs=%d,%d} ",
 249                         mWritingMode.DebugString(), IStart(), BStart(), ISize(),
 250                         BSize(), mContainerSize.width, mContainerSize.height);
 251   }
 252   if (mData &&
 253       (!mData->mOverflowAreas.VisualOverflow().IsEqualEdges(bounds) ||
 254        !mData->mOverflowAreas.ScrollableOverflow().IsEqualEdges(bounds))) {
 255     str += nsPrintfCString("vis-overflow=%d,%d,%d,%d scr-overflow=%d,%d,%d,%d ",
 256                            mData->mOverflowAreas.VisualOverflow().x,
 257                            mData->mOverflowAreas.VisualOverflow().y,
 258                            mData->mOverflowAreas.VisualOverflow().width,
 259                            mData->mOverflowAreas.VisualOverflow().height,
 260                            mData->mOverflowAreas.ScrollableOverflow().x,
 261                            mData->mOverflowAreas.ScrollableOverflow().y,
 262                            mData->mOverflowAreas.ScrollableOverflow().width,
 263                            mData->mOverflowAreas.ScrollableOverflow().height);
 264   }
 265   fprintf_stderr(out, "%s<\n", str.get());
 266
 267   nsIFrame* frame = mFirstChild;
 268   int32_t n = GetChildCount();
 269   nsCString pfx(aPrefix);
 270   pfx += "  ";
 271   while (--n >= 0) {
 272     frame->List(out, pfx.get(), aFlags);
 273     frame = frame->GetNextSibling();
 274   }
 275
 276   if (HasFloats()) {
 277     fprintf_stderr(out, "%s> floats <\n", aPrefix);
 278     ListFloats(out, pfx.get(), mInlineData->mFloats);
 279   }
 280   fprintf_stderr(out, "%s>\n", aPrefix);
 281 }
 282
 283 nsIFrame* nsLineBox::LastChild() const {
 284   nsIFrame* frame = mFirstChild;
 285   int32_t n = GetChildCount() - 1;
 286   while (--n >= 0) {
 287     frame = frame->GetNextSibling();
 288   }
 289   return frame;
 290 }
 291 #endif
 292
 293 int32_t nsLineBox::IndexOf(nsIFrame* aFrame) const {
 294   int32_t i, n = GetChildCount();
 295   nsIFrame* frame = mFirstChild;
 296   for (i = 0; i < n; i++) {
 297     if (frame == aFrame) {
 298       return i;
 299     }
 300     frame = frame->GetNextSibling();
 301   }
 302   return -1;
 303 }
 304
 305 int32_t nsLineBox::RIndexOf(nsIFrame* aFrame,
 306                             nsIFrame* aLastFrameInLine) const {
 307   nsIFrame* frame = aLastFrameInLine;
 308   for (int32_t i = GetChildCount() - 1; i >= 0; --i) {
 309     MOZ_ASSERT(i != 0 || frame == mFirstChild,
 310                "caller provided incorrect last frame");
 311     if (frame == aFrame) {
 312       return i;
 313     }
 314     frame = frame->GetPrevSibling();
 315   }
 316   return -1;
 317 }
 318
 319 bool nsLineBox::IsEmpty() const {
 320   if (IsBlock()) return mFirstChild->IsEmpty();
 321
 322   int32_t n;
 323   nsIFrame* kid;
 324   for (n = GetChildCount(), kid = mFirstChild; n > 0;
 325        --n, kid = kid->GetNextSibling()) {
 326     if (!kid->IsEmpty()) return false;
 327   }
 328   if (HasMarker()) {
 329     return false;
 330   }
 331   return true;
 332 }
 333
 334 bool nsLineBox::CachedIsEmpty() {
 335   if (mFlags.mDirty) {
 336     return IsEmpty();
 337   }
 338
 339   if (mFlags.mEmptyCacheValid) {
 340     return mFlags.mEmptyCacheState;
 341   }
 342
 343   bool result;
 344   if (IsBlock()) {
 345     result = mFirstChild->CachedIsEmpty();
 346   } else {
 347     int32_t n;
 348     nsIFrame* kid;
 349     result = true;
 350     for (n = GetChildCount(), kid = mFirstChild; n > 0;
 351          --n, kid = kid->GetNextSibling()) {
 352       if (!kid->CachedIsEmpty()) {
 353         result = false;
 354         break;
 355       }
 356     }
 357     if (HasMarker()) {
 358       result = false;
 359     }
 360   }
 361
 362   mFlags.mEmptyCacheValid = true;
 363   mFlags.mEmptyCacheState = result;
 364   return result;
 365 }
 366
 367 void nsLineBox::DeleteLineList(nsPresContext* aPresContext, nsLineList& aLines,
 368                                nsIFrame* aDestructRoot, nsFrameList* aFrames,
 369                                PostDestroyData& aPostDestroyData) {
 370   PresShell* presShell = aPresContext->PresShell();
 371
 372   // Keep our line list and frame list up to date as we
 373   // remove frames, in case something wants to traverse the
 374   // frame tree while we're destroying.
 375   while (!aLines.empty()) {
 376     nsLineBox* line = aLines.front();
 377     if (MOZ_UNLIKELY(line->mFlags.mHasHashedFrames)) {
 378       line->SwitchToCounter();  // Avoid expensive has table removals.
 379     }
 380     while (line->GetChildCount() > 0) {
 381       nsIFrame* child = aFrames->RemoveFirstChild();
 382       MOZ_DIAGNOSTIC_ASSERT(child->PresContext() == aPresContext);
 383       MOZ_DIAGNOSTIC_ASSERT(child == line->mFirstChild, "Lines out of sync");
 384       line->mFirstChild = aFrames->FirstChild();
 385       line->NoteFrameRemoved(child);
 386       child->DestroyFrom(aDestructRoot, aPostDestroyData);
 387     }
 388     MOZ_DIAGNOSTIC_ASSERT(line == aLines.front(),
 389                           "destroying child frames messed up our lines!");
 390     aLines.pop_front();
 391     line->Destroy(presShell);
 392   }
 393 }
 394
 395 bool nsLineBox::RFindLineContaining(nsIFrame* aFrame,
 396                                     const nsLineList::iterator& aBegin,
 397                                     nsLineList::iterator& aEnd,
 398                                     nsIFrame* aLastFrameBeforeEnd,
 399                                     int32_t* aFrameIndexInLine) {
 400   MOZ_ASSERT(aFrame, "null ptr");
 401
 402   nsIFrame* curFrame = aLastFrameBeforeEnd;
 403   while (aBegin != aEnd) {
 404     --aEnd;
 405     NS_ASSERTION(aEnd->LastChild() == curFrame, "Unexpected curFrame");
 406     if (MOZ_UNLIKELY(aEnd->mFlags.mHasHashedFrames) &&
 407         !aEnd->Contains(aFrame)) {
 408       if (aEnd->mFirstChild) {
 409         curFrame = aEnd->mFirstChild->GetPrevSibling();
 410       }
 411       continue;
 412     }
 413     // i is the index of curFrame in aEnd
 414     int32_t i = aEnd->GetChildCount() - 1;
 415     while (i >= 0) {
 416       if (curFrame == aFrame) {
 417         *aFrameIndexInLine = i;
 418         return true;
 419       }
 420       --i;
 421       curFrame = curFrame->GetPrevSibling();
 422     }
 423     MOZ_ASSERT(!aEnd->mFlags.mHasHashedFrames, "Contains lied to us!");
 424   }
 425   *aFrameIndexInLine = -1;
 426   return false;
 427 }
 428
 429 nsCollapsingMargin nsLineBox::GetCarriedOutBEndMargin() const {
 430   NS_ASSERTION(IsBlock(), "GetCarriedOutBEndMargin called on non-block line.");
 431   return (IsBlock() && mBlockData) ? mBlockData->mCarriedOutBEndMargin
 432                                    : nsCollapsingMargin();
 433 }
 434
 435 bool nsLineBox::SetCarriedOutBEndMargin(nsCollapsingMargin aValue) {
 436   bool changed = false;
 437   if (IsBlock()) {
 438     if (!aValue.IsZero()) {
 439       if (!mBlockData) {
 440         mBlockData = new ExtraBlockData(GetPhysicalBounds());
 441       }
 442       changed = aValue != mBlockData->mCarriedOutBEndMargin;
 443       mBlockData->mCarriedOutBEndMargin = aValue;
 444     } else if (mBlockData) {
 445       changed = aValue != mBlockData->mCarriedOutBEndMargin;
 446       mBlockData->mCarriedOutBEndMargin = aValue;
 447       MaybeFreeData();
 448     }
 449   }
 450   return changed;
 451 }
 452
 453 void nsLineBox::MaybeFreeData() {
 454   nsRect bounds = GetPhysicalBounds();
 455   if (mData && mData->mOverflowAreas == nsOverflowAreas(bounds, bounds)) {
 456     if (IsInline()) {
 457       if (mInlineData->mFloats.IsEmpty()) {
 458         delete mInlineData;
 459         mInlineData = nullptr;
 460       }
 461     } else if (mBlockData->mCarriedOutBEndMargin.IsZero()) {
 462       delete mBlockData;
 463       mBlockData = nullptr;
 464     }
 465   }
 466 }
 467
 468 // XXX get rid of this???
 469 nsFloatCache* nsLineBox::GetFirstFloat() {
 470   MOZ_ASSERT(IsInline(), "block line can't have floats");
 471   return mInlineData ? mInlineData->mFloats.Head() : nullptr;
 472 }
 473
 474 // XXX this might be too eager to free memory
 475 void nsLineBox::FreeFloats(nsFloatCacheFreeList& aFreeList) {
 476   MOZ_ASSERT(IsInline(), "block line can't have floats");
 477   if (IsInline() && mInlineData) {
 478     if (mInlineData->mFloats.NotEmpty()) {
 479       aFreeList.Append(mInlineData->mFloats);
 480     }
 481     MaybeFreeData();
 482   }
 483 }
 484
 485 void nsLineBox::AppendFloats(nsFloatCacheFreeList& aFreeList) {
 486   MOZ_ASSERT(IsInline(), "block line can't have floats");
 487   if (IsInline()) {
 488     if (aFreeList.NotEmpty()) {
 489       if (!mInlineData) {
 490         mInlineData = new ExtraInlineData(GetPhysicalBounds());
 491       }
 492       mInlineData->mFloats.Append(aFreeList);
 493     }
 494   }
 495 }
 496
 497 bool nsLineBox::RemoveFloat(nsIFrame* aFrame) {
 498   MOZ_ASSERT(IsInline(), "block line can't have floats");
 499   if (IsInline() && mInlineData) {
 500     nsFloatCache* fc = mInlineData->mFloats.Find(aFrame);
 501     if (fc) {
 502       // Note: the placeholder is part of the line's child list
 503       // and will be removed later.
 504       mInlineData->mFloats.Remove(fc);
 505       delete fc;
 506       MaybeFreeData();
 507       return true;
 508     }
 509   }
 510   return false;
 511 }
 512
 513 void nsLineBox::SetFloatEdges(nscoord aStart, nscoord aEnd) {
 514   MOZ_ASSERT(IsInline(), "block line can't have float edges");
 515   if (!mInlineData) {
 516     mInlineData = new ExtraInlineData(GetPhysicalBounds());
 517   }
 518   mInlineData->mFloatEdgeIStart = aStart;
 519   mInlineData->mFloatEdgeIEnd = aEnd;
 520 }
 521
 522 void nsLineBox::ClearFloatEdges() {
 523   MOZ_ASSERT(IsInline(), "block line can't have float edges");
 524   if (mInlineData) {
 525     mInlineData->mFloatEdgeIStart = nscoord_MIN;
 526     mInlineData->mFloatEdgeIEnd = nscoord_MIN;
 527   }
 528 }
 529
 530 void nsLineBox::SetOverflowAreas(const nsOverflowAreas& aOverflowAreas) {
 531   NS_FOR_FRAME_OVERFLOW_TYPES(otype) {
 532     NS_ASSERTION(aOverflowAreas.Overflow(otype).width >= 0,
 533                  "illegal width for combined area");
 534     NS_ASSERTION(aOverflowAreas.Overflow(otype).height >= 0,
 535                  "illegal height for combined area");
 536   }
 537   nsRect bounds = GetPhysicalBounds();
 538   if (!aOverflowAreas.VisualOverflow().IsEqualInterior(bounds) ||
 539       !aOverflowAreas.ScrollableOverflow().IsEqualEdges(bounds)) {
 540     if (!mData) {
 541       if (IsInline()) {
 542         mInlineData = new ExtraInlineData(bounds);
 543       } else {
 544         mBlockData = new ExtraBlockData(bounds);
 545       }
 546     }
 547     mData->mOverflowAreas = aOverflowAreas;
 548   } else if (mData) {
 549     // Store away new value so that MaybeFreeData compares against
 550     // the right value.
 551     mData->mOverflowAreas = aOverflowAreas;
 552     MaybeFreeData();
 553   }
 554 }
 555
 556 //----------------------------------------------------------------------
 557
 558 static nsLineBox* gDummyLines[1];
 559
 560 nsLineIterator::nsLineIterator() {
 561   mLines = gDummyLines;
 562   mNumLines = 0;
 563   mIndex = 0;
 564   mRightToLeft = false;
 565 }
 566
 567 nsLineIterator::~nsLineIterator() {
 568   if (mLines != gDummyLines) {
 569     delete[] mLines;
 570   }
 571 }
 572
 573 /* virtual */
 574 void nsLineIterator::DisposeLineIterator() { delete this; }
 575
 576 nsresult nsLineIterator::Init(nsLineList& aLines, bool aRightToLeft) {
 577   mRightToLeft = aRightToLeft;
 578
 579   // Count the lines
 580   int32_t numLines = aLines.size();
 581   if (0 == numLines) {
 582     // Use gDummyLines so that we don't need null pointer checks in
 583     // the accessor methods
 584     mLines = gDummyLines;
 585     return NS_OK;
 586   }
 587
 588   // Make a linear array of the lines
 589   mLines = new nsLineBox*[numLines];
 590   if (!mLines) {
 591     // Use gDummyLines so that we don't need null pointer checks in
 592     // the accessor methods
 593     mLines = gDummyLines;
 594     return NS_ERROR_OUT_OF_MEMORY;
 595   }
 596   nsLineBox** lp = mLines;
 597   for (nsLineList::iterator line = aLines.begin(), line_end = aLines.end();
 598        line != line_end; ++line) {
 599     *lp++ = line;
 600   }
 601   mNumLines = numLines;
 602   return NS_OK;
 603 }
 604
 605 int32_t nsLineIterator::GetNumLines() { return mNumLines; }
 606
 607 bool nsLineIterator::GetDirection() { return mRightToLeft; }
 608
 609 NS_IMETHODIMP
 610 nsLineIterator::GetLine(int32_t aLineNumber, nsIFrame** aFirstFrameOnLine,
 611                         int32_t* aNumFramesOnLine, nsRect& aLineBounds) {
 612   NS_ENSURE_ARG_POINTER(aFirstFrameOnLine);
 613   NS_ENSURE_ARG_POINTER(aNumFramesOnLine);
 614
 615   if ((aLineNumber < 0) || (aLineNumber >= mNumLines)) {
 616     *aFirstFrameOnLine = nullptr;
 617     *aNumFramesOnLine = 0;
 618     aLineBounds.SetRect(0, 0, 0, 0);
 619     return NS_OK;
 620   }
 621   nsLineBox* line = mLines[aLineNumber];
 622   *aFirstFrameOnLine = line->mFirstChild;
 623   *aNumFramesOnLine = line->GetChildCount();
 624   aLineBounds = line->GetPhysicalBounds();
 625
 626   return NS_OK;
 627 }
 628
 629 int32_t nsLineIterator::FindLineContaining(nsIFrame* aFrame,
 630                                            int32_t aStartLine) {
 631   MOZ_ASSERT(aStartLine <= mNumLines, "Bogus line numbers");
 632   int32_t lineNumber = aStartLine;
 633   while (lineNumber != mNumLines) {
 634     nsLineBox* line = mLines[lineNumber];
 635     if (line->Contains(aFrame)) {
 636       return lineNumber;
 637     }
 638     ++lineNumber;
 639   }
 640   return -1;
 641 }
 642
 643 NS_IMETHODIMP
 644 nsLineIterator::CheckLineOrder(int32_t aLine, bool* aIsReordered,
 645                                nsIFrame** aFirstVisual,
 646                                nsIFrame** aLastVisual) {
 647   NS_ASSERTION(aLine >= 0 && aLine < mNumLines, "aLine out of range!");
 648   nsLineBox* line = mLines[aLine];
 649
 650   if (!line->mFirstChild) {  // empty line
 651     *aIsReordered = false;
 652     *aFirstVisual = nullptr;
 653     *aLastVisual = nullptr;
 654     return NS_OK;
 655   }
 656
 657   nsIFrame* leftmostFrame;
 658   nsIFrame* rightmostFrame;
 659   *aIsReordered =
 660       nsBidiPresUtils::CheckLineOrder(line->mFirstChild, line->GetChildCount(),
 661                                       &leftmostFrame, &rightmostFrame);
 662
 663   // map leftmost/rightmost to first/last according to paragraph direction
 664   *aFirstVisual = mRightToLeft ? rightmostFrame : leftmostFrame;
 665   *aLastVisual = mRightToLeft ? leftmostFrame : rightmostFrame;
 666
 667   return NS_OK;
 668 }
 669
 670 NS_IMETHODIMP
 671 nsLineIterator::FindFrameAt(int32_t aLineNumber, nsPoint aPos,
 672                             nsIFrame** aFrameFound,
 673                             bool* aPosIsBeforeFirstFrame,
 674                             bool* aPosIsAfterLastFrame) {
 675   MOZ_ASSERT(aFrameFound && aPosIsBeforeFirstFrame && aPosIsAfterLastFrame,
 676              "null OUT ptr");
 677
 678   if (!aFrameFound || !aPosIsBeforeFirstFrame || !aPosIsAfterLastFrame) {
 679     return NS_ERROR_NULL_POINTER;
 680   }
 681   if ((aLineNumber < 0) || (aLineNumber >= mNumLines)) {
 682     return NS_ERROR_INVALID_ARG;
 683   }
 684
 685   nsLineBox* line = mLines[aLineNumber];
 686   if (!line) {
 687     *aFrameFound = nullptr;
 688     *aPosIsBeforeFirstFrame = true;
 689     *aPosIsAfterLastFrame = false;
 690     return NS_OK;
 691   }
 692
 693   if (line->ISize() == 0 && line->BSize() == 0) return NS_ERROR_FAILURE;
 694
 695   nsIFrame* frame = line->mFirstChild;
 696   nsIFrame* closestFromStart = nullptr;
 697   nsIFrame* closestFromEnd = nullptr;
 698
 699   WritingMode wm = line->mWritingMode;
 700   nsSize containerSize = line->mContainerSize;
 701
 702   LogicalPoint pos(wm, aPos, containerSize);
 703
 704   int32_t n = line->GetChildCount();
 705   while (n--) {
 706     LogicalRect rect = frame->GetLogicalRect(wm, containerSize);
 707     if (rect.ISize(wm) > 0) {
 708       // If pos.I() is inside this frame - this is it
 709       if (rect.IStart(wm) <= pos.I(wm) && rect.IEnd(wm) > pos.I(wm)) {
 710         closestFromStart = closestFromEnd = frame;
 711         break;
 712       }
 713       if (rect.IStart(wm) < pos.I(wm)) {
 714         if (!closestFromStart ||
 715             rect.IEnd(wm) >
 716                 closestFromStart->GetLogicalRect(wm, containerSize).IEnd(wm))
 717           closestFromStart = frame;
 718       } else {
 719         if (!closestFromEnd ||
 720             rect.IStart(wm) <
 721                 closestFromEnd->GetLogicalRect(wm, containerSize).IStart(wm))
 722           closestFromEnd = frame;
 723       }
 724     }
 725     frame = frame->GetNextSibling();
 726   }
 727   if (!closestFromStart && !closestFromEnd) {
 728     // All frames were zero-width. Just take the first one.
 729     closestFromStart = closestFromEnd = line->mFirstChild;
 730   }
 731   *aPosIsBeforeFirstFrame = mRightToLeft ? !closestFromEnd : !closestFromStart;
 732   *aPosIsAfterLastFrame = mRightToLeft ? !closestFromStart : !closestFromEnd;
 733   if (closestFromStart == closestFromEnd) {
 734     *aFrameFound = closestFromStart;
 735   } else if (!closestFromStart) {
 736     *aFrameFound = closestFromEnd;
 737   } else if (!closestFromEnd) {
 738     *aFrameFound = closestFromStart;
 739   } else {  // we're between two frames
 740     nscoord delta =
 741         closestFromEnd->GetLogicalRect(wm, containerSize).IStart(wm) -
 742         closestFromStart->GetLogicalRect(wm, containerSize).IEnd(wm);
 743     if (pos.I(wm) <
 744         closestFromStart->GetLogicalRect(wm, containerSize).IEnd(wm) +
 745             delta / 2) {
 746       *aFrameFound = closestFromStart;
 747     } else {
 748       *aFrameFound = closestFromEnd;
 749     }
 750   }
 751   return NS_OK;
 752 }
 753
 754 NS_IMETHODIMP
 755 nsLineIterator::GetNextSiblingOnLine(nsIFrame*& aFrame, int32_t aLineNumber) {
 756   aFrame = aFrame->GetNextSibling();
 757   return NS_OK;
 758 }
 759
 760 //----------------------------------------------------------------------
 761
 762 #ifdef NS_BUILD_REFCNT_LOGGING
 763 nsFloatCacheList::nsFloatCacheList() : mHead(nullptr) {
 764   MOZ_COUNT_CTOR(nsFloatCacheList);
 765 }
 766 #endif
 767
 768 nsFloatCacheList::~nsFloatCacheList() {
 769   DeleteAll();
 770   MOZ_COUNT_DTOR(nsFloatCacheList);
 771 }
 772
 773 void nsFloatCacheList::DeleteAll() {
 774   nsFloatCache* c = mHead;
 775   while (c) {
 776     nsFloatCache* next = c->Next();
 777     delete c;
 778     c = next;
 779   }
 780   mHead = nullptr;
 781 }
 782
 783 nsFloatCache* nsFloatCacheList::Tail() const {
 784   nsFloatCache* fc = mHead;
 785   while (fc) {
 786     if (!fc->mNext) {
 787       break;
 788     }
 789     fc = fc->mNext;
 790   }
 791   return fc;
 792 }
 793
 794 void nsFloatCacheList::Append(nsFloatCacheFreeList& aList) {
 795   MOZ_ASSERT(aList.NotEmpty(), "Appending empty list will fail");
 796
 797   nsFloatCache* tail = Tail();
 798   if (tail) {
 799     NS_ASSERTION(!tail->mNext, "Bogus!");
 800     tail->mNext = aList.mHead;
 801   } else {
 802     NS_ASSERTION(!mHead, "Bogus!");
 803     mHead = aList.mHead;
 804   }
 805   aList.mHead = nullptr;
 806   aList.mTail = nullptr;
 807 }
 808
 809 nsFloatCache* nsFloatCacheList::Find(nsIFrame* aOutOfFlowFrame) {
 810   nsFloatCache* fc = mHead;
 811   while (fc) {
 812     if (fc->mFloat == aOutOfFlowFrame) {
 813       break;
 814     }
 815     fc = fc->Next();
 816   }
 817   return fc;
 818 }
 819
 820 nsFloatCache* nsFloatCacheList::RemoveAndReturnPrev(nsFloatCache* aElement) {
 821   nsFloatCache* fc = mHead;
 822   nsFloatCache* prev = nullptr;
 823   while (fc) {
 824     if (fc == aElement) {
 825       if (prev) {
 826         prev->mNext = fc->mNext;
 827       } else {
 828         mHead = fc->mNext;
 829       }
 830       return prev;
 831     }
 832     prev = fc;
 833     fc = fc->mNext;
 834   }
 835   return nullptr;
 836 }
 837
 838 //----------------------------------------------------------------------
 839
 840 #ifdef NS_BUILD_REFCNT_LOGGING
 841 nsFloatCacheFreeList::nsFloatCacheFreeList() : mTail(nullptr) {
 842   MOZ_COUNT_CTOR(nsFloatCacheFreeList);
 843 }
 844
 845 nsFloatCacheFreeList::~nsFloatCacheFreeList() {
 846   MOZ_COUNT_DTOR(nsFloatCacheFreeList);
 847 }
 848 #endif
 849
 850 void nsFloatCacheFreeList::Append(nsFloatCacheList& aList) {
 851   MOZ_ASSERT(aList.NotEmpty(), "Appending empty list will fail");
 852
 853   if (mTail) {
 854     NS_ASSERTION(!mTail->mNext, "Bogus");
 855     mTail->mNext = aList.mHead;
 856   } else {
 857     NS_ASSERTION(!mHead, "Bogus");
 858     mHead = aList.mHead;
 859   }
 860   mTail = aList.Tail();
 861   aList.mHead = nullptr;
 862 }
 863
 864 void nsFloatCacheFreeList::Remove(nsFloatCache* aElement) {
 865   nsFloatCache* prev = nsFloatCacheList::RemoveAndReturnPrev(aElement);
 866   if (mTail == aElement) {
 867     mTail = prev;
 868   }
 869 }
 870
 871 void nsFloatCacheFreeList::DeleteAll() {
 872   nsFloatCacheList::DeleteAll();
 873   mTail = nullptr;
 874 }
 875
 876 nsFloatCache* nsFloatCacheFreeList::Alloc(nsIFrame* aFloat) {
 877   MOZ_ASSERT(aFloat->GetStateBits() & NS_FRAME_OUT_OF_FLOW,
 878              "This is a float cache, why isn't the frame out-of-flow?");
 879
 880   nsFloatCache* fc = mHead;
 881   if (mHead) {
 882     if (mHead == mTail) {
 883       mHead = mTail = nullptr;
 884     } else {
 885       mHead = fc->mNext;
 886     }
 887     fc->mNext = nullptr;
 888   } else {
 889     fc = new nsFloatCache();
 890   }
 891   fc->mFloat = aFloat;
 892   return fc;
 893 }
 894
 895 void nsFloatCacheFreeList::Append(nsFloatCache* aFloat) {
 896   NS_ASSERTION(!aFloat->mNext, "Bogus!");
 897   aFloat->mNext = nullptr;
 898   if (mTail) {
 899     NS_ASSERTION(!mTail->mNext, "Bogus!");
 900     mTail->mNext = aFloat;
 901     mTail = aFloat;
 902   } else {
 903     NS_ASSERTION(!mHead, "Bogus!");
 904     mHead = mTail = aFloat;
 905   }
 906 }
 907
 908 //----------------------------------------------------------------------
 909
 910 nsFloatCache::nsFloatCache() : mFloat(nullptr), mNext(nullptr) {
 911   MOZ_COUNT_CTOR(nsFloatCache);
 912 }
 913
 914 #ifdef NS_BUILD_REFCNT_LOGGING
 915 nsFloatCache::~nsFloatCache() { MOZ_COUNT_DTOR(nsFloatCache); }
 916 #endif