layout/generic/nsLineBox.cpp

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