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