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 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Netscape Communications Corporation.
  20  * Portions created by the Initial Developer are Copyright (C) 1998
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   L. David Baron <dbaron@dbaron.org>
  25  *   Pierre Phaneuf <pp@ludusdesign.com>
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either of the GNU General Public License Version 2 or later (the "GPL"),
  29  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 /* representation of one line within a block frame, a CSS line box */
  42
  43 #include "nsLineBox.h"
  44 #include "nsSpaceManager.h"
  45 #include "nsLineLayout.h"
  46 #include "prprf.h"
  47 #include "nsBlockFrame.h"
  48 #include "nsGkAtoms.h"
  49 #include "nsFrameManager.h"
  50 #ifdef IBMBIDI
  51 #include "nsBidiPresUtils.h"
  52 #endif
  53
  54 #ifdef DEBUG
  55 static PRInt32 ctorCount;
  56 PRInt32 nsLineBox::GetCtorCount() { return ctorCount; }
  57 #endif
  58
  59 nsLineBox::nsLineBox(nsIFrame* aFrame, PRInt32 aCount, PRBool aIsBlock)
  60   : mFirstChild(aFrame),
  61     mBounds(0, 0, 0, 0),
  62     mData(nsnull)
  63 {
  64   MOZ_COUNT_CTOR(nsLineBox);
  65 #ifdef DEBUG
  66   ++ctorCount;
  67   NS_ASSERTION(!aIsBlock || aCount == 1, "Blocks must have exactly one child");
  68   nsIFrame* f = aFrame;
  69   for (PRInt32 n = aCount; n > 0; f = f->GetNextSibling(), --n) {
  70     NS_ASSERTION(aIsBlock == f->GetStyleDisplay()->IsBlockOutside(),
  71                  "wrong kind of child frame");
  72   }
  73 #endif
  74
  75   mAllFlags = 0;
  76 #if NS_STYLE_CLEAR_NONE > 0
  77   mFlags.mBreakType = NS_STYLE_CLEAR_NONE;
  78 #endif
  79   SetChildCount(aCount);
  80   MarkDirty();
  81   mFlags.mBlock = aIsBlock;
  82 }
  83
  84 nsLineBox::~nsLineBox()
  85 {
  86   MOZ_COUNT_DTOR(nsLineBox);
  87   Cleanup();
  88 }
  89
  90 nsLineBox*
  91 NS_NewLineBox(nsIPresShell* aPresShell, nsIFrame* aFrame,
  92               PRInt32 aCount, PRBool aIsBlock)
  93 {
  94   return new (aPresShell)nsLineBox(aFrame, aCount, aIsBlock);
  95 }
  96
  97 // Overloaded new operator. Uses an arena (which comes from the presShell)
  98 // to perform the allocation.
  99 void*
 100 nsLineBox::operator new(size_t sz, nsIPresShell* aPresShell) CPP_THROW_NEW
 101 {
 102   return aPresShell->AllocateFrame(sz);
 103 }
 104
 105 // Overloaded delete operator. Doesn't actually free the memory, because we
 106 // use an arena
 107 void
 108 nsLineBox::operator delete(void* aPtr, size_t sz)
 109 {
 110 }
 111
 112 void
 113 nsLineBox::Destroy(nsIPresShell* aPresShell)
 114 {
 115   // Destroy the object. This won't actually free the memory, though
 116   delete this;
 117
 118   // Have the pres shell recycle the memory
 119   aPresShell->FreeFrame(sizeof(*this), (void*)this);
 120 }
 121
 122 void
 123 nsLineBox::Cleanup()
 124 {
 125   if (mData) {
 126     if (IsBlock()) {
 127       delete mBlockData;
 128     }
 129     else {
 130       delete mInlineData;
 131     }
 132     mData = nsnull;
 133   }
 134 }
 135
 136 #ifdef DEBUG
 137 static void
 138 ListFloats(FILE* out, PRInt32 aIndent, const nsFloatCacheList& aFloats)
 139 {
 140   nsAutoString frameName;
 141   nsFloatCache* fc = aFloats.Head();
 142   while (fc) {
 143     nsFrame::IndentBy(out, aIndent);
 144     nsPlaceholderFrame* ph = fc->mPlaceholder;
 145     if (ph) {
 146       fprintf(out, "placeholder@%p ", static_cast<void*>(ph));
 147       nsIFrame* frame = ph->GetOutOfFlowFrame();
 148       if (frame) {
 149         nsIFrameDebug*  frameDebug;
 150
 151         if (NS_SUCCEEDED(frame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
 152           frameDebug->GetFrameName(frameName);
 153           fputs(NS_LossyConvertUTF16toASCII(frameName).get(), out);
 154         }
 155       }
 156       fprintf(out, " region={%d,%d,%d,%d}",
 157               fc->mRegion.x, fc->mRegion.y,
 158               fc->mRegion.width, fc->mRegion.height);
 159
 160       if (!frame) {
 161         fputs("\n###!!! NULL out-of-flow frame", out);
 162       }
 163       fprintf(out, "\n");
 164     }
 165     fc = fc->Next();
 166   }
 167 }
 168 #endif
 169
 170 #ifdef DEBUG
 171 const char *
 172 BreakTypeToString(PRUint8 aBreakType)
 173 {
 174   switch (aBreakType) {
 175   case NS_STYLE_CLEAR_NONE: return "nobr";
 176   case NS_STYLE_CLEAR_LEFT: return "leftbr";
 177   case NS_STYLE_CLEAR_RIGHT: return "rightbr";
 178   case NS_STYLE_CLEAR_LEFT_AND_RIGHT: return "leftbr+rightbr";
 179   case NS_STYLE_CLEAR_LINE: return "linebr";
 180   case NS_STYLE_CLEAR_BLOCK: return "blockbr";
 181   case NS_STYLE_CLEAR_COLUMN: return "columnbr";
 182   case NS_STYLE_CLEAR_PAGE: return "pagebr";
 183   default:
 184     break;
 185   }
 186   return "unknown";
 187 }
 188
 189 char*
 190 nsLineBox::StateToString(char* aBuf, PRInt32 aBufSize) const
 191 {
 192   PR_snprintf(aBuf, aBufSize, "%s,%s,%s,%s,%s,before:%s,after:%s[0x%x]",
 193               IsBlock() ? "block" : "inline",
 194               IsDirty() ? "dirty" : "clean",
 195               IsPreviousMarginDirty() ? "prevmargindirty" : "prevmarginclean",
 196               IsImpactedByFloat() ? "impacted" : "not impacted",
 197               IsLineWrapped() ? "wrapped" : "not wrapped",
 198               BreakTypeToString(GetBreakTypeBefore()),
 199               BreakTypeToString(GetBreakTypeAfter()),
 200               mAllFlags);
 201   return aBuf;
 202 }
 203
 204 void
 205 nsLineBox::List(FILE* out, PRInt32 aIndent) const
 206 {
 207   PRInt32 i;
 208
 209   for (i = aIndent; --i >= 0; ) fputs("  ", out);
 210   char cbuf[100];
 211   fprintf(out, "line %p: count=%d state=%s ",
 212           static_cast<const void*>(this), GetChildCount(),
 213           StateToString(cbuf, sizeof(cbuf)));
 214   if (IsBlock() && !GetCarriedOutBottomMargin().IsZero()) {
 215     fprintf(out, "bm=%d ", GetCarriedOutBottomMargin().get());
 216   }
 217   fprintf(out, "{%d,%d,%d,%d} ",
 218           mBounds.x, mBounds.y, mBounds.width, mBounds.height);
 219   if (mData) {
 220     fprintf(out, "ca={%d,%d,%d,%d} ",
 221             mData->mCombinedArea.x, mData->mCombinedArea.y,
 222             mData->mCombinedArea.width, mData->mCombinedArea.height);
 223   }
 224   fprintf(out, "<\n");
 225
 226   nsIFrame* frame = mFirstChild;
 227   PRInt32 n = GetChildCount();
 228   while (--n >= 0) {
 229     nsIFrameDebug*  frameDebug;
 230
 231     if (NS_SUCCEEDED(frame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
 232       frameDebug->List(out, aIndent + 1);
 233     }
 234     frame = frame->GetNextSibling();
 235   }
 236
 237   for (i = aIndent; --i >= 0; ) fputs("  ", out);
 238   if (HasFloats()) {
 239     fputs("> floats <\n", out);
 240     ListFloats(out, aIndent + 1, mInlineData->mFloats);
 241     for (i = aIndent; --i >= 0; ) fputs("  ", out);
 242   }
 243   fputs(">\n", out);
 244 }
 245 #endif
 246
 247 nsIFrame*
 248 nsLineBox::LastChild() const
 249 {
 250   nsIFrame* frame = mFirstChild;
 251   PRInt32 n = GetChildCount() - 1;
 252   while (--n >= 0) {
 253     frame = frame->GetNextSibling();
 254   }
 255   return frame;
 256 }
 257
 258 PRBool
 259 nsLineBox::IsLastChild(nsIFrame* aFrame) const
 260 {
 261   nsIFrame* lastFrame = LastChild();
 262   return aFrame == lastFrame;
 263 }
 264
 265 PRInt32
 266 nsLineBox::IndexOf(nsIFrame* aFrame) const
 267 {
 268   PRInt32 i, n = GetChildCount();
 269   nsIFrame* frame = mFirstChild;
 270   for (i = 0; i < n; i++) {
 271     if (frame == aFrame) {
 272       return i;
 273     }
 274     frame = frame->GetNextSibling();
 275   }
 276   return -1;
 277 }
 278
 279 PRBool
 280 nsLineBox::IsEmpty() const
 281 {
 282   if (IsBlock())
 283     return mFirstChild->IsEmpty();
 284
 285   PRInt32 n;
 286   nsIFrame *kid;
 287   for (n = GetChildCount(), kid = mFirstChild;
 288        n > 0;
 289        --n, kid = kid->GetNextSibling())
 290   {
 291     if (!kid->IsEmpty())
 292       return PR_FALSE;
 293   }
 294   return PR_TRUE;
 295 }
 296
 297 PRBool
 298 nsLineBox::CachedIsEmpty()
 299 {
 300   if (mFlags.mDirty) {
 301     return IsEmpty();
 302   }
 303
 304   if (mFlags.mEmptyCacheValid) {
 305     return mFlags.mEmptyCacheState;
 306   }
 307
 308   PRBool result;
 309   if (IsBlock()) {
 310     result = mFirstChild->CachedIsEmpty();
 311   } else {
 312     PRInt32 n;
 313     nsIFrame *kid;
 314     result = PR_TRUE;
 315     for (n = GetChildCount(), kid = mFirstChild;
 316          n > 0;
 317          --n, kid = kid->GetNextSibling())
 318       {
 319         if (!kid->CachedIsEmpty()) {
 320           result = PR_FALSE;
 321           break;
 322         }
 323       }
 324   }
 325
 326   mFlags.mEmptyCacheValid = PR_TRUE;
 327   mFlags.mEmptyCacheState = result;
 328   return result;
 329 }
 330
 331 void
 332 nsLineBox::DeleteLineList(nsPresContext* aPresContext, nsLineList& aLines)
 333 {
 334   if (! aLines.empty()) {
 335     // Delete our child frames before doing anything else. In particular
 336     // we do all of this before our base class releases it's hold on the
 337     // view.
 338     for (nsIFrame* child = aLines.front()->mFirstChild; child; ) {
 339       nsIFrame* nextChild = child->GetNextSibling();
 340       child->Destroy();
 341       child = nextChild;
 342     }
 343
 344     nsIPresShell *shell = aPresContext->PresShell();
 345
 346     do {
 347       nsLineBox* line = aLines.front();
 348       aLines.pop_front();
 349       line->Destroy(shell);
 350     } while (! aLines.empty());
 351   }
 352 }
 353
 354 nsLineBox*
 355 nsLineBox::FindLineContaining(nsLineList& aLines, nsIFrame* aFrame,
 356                               PRInt32* aFrameIndexInLine)
 357 {
 358   NS_PRECONDITION(aFrameIndexInLine && !aLines.empty() && aFrame, "null ptr");
 359   for (nsLineList::iterator line = aLines.begin(),
 360                             line_end = aLines.end();
 361        line != line_end;
 362        ++line)
 363   {
 364     PRInt32 ix = line->IndexOf(aFrame);
 365     if (ix >= 0) {
 366       *aFrameIndexInLine = ix;
 367       return line;
 368     }
 369   }
 370   *aFrameIndexInLine = -1;
 371   return nsnull;
 372 }
 373
 374 PRBool
 375 nsLineBox::RFindLineContaining(nsIFrame* aFrame,
 376                                const nsLineList::iterator& aBegin,
 377                                nsLineList::iterator& aEnd,
 378                                PRInt32* aFrameIndexInLine)
 379 {
 380   NS_PRECONDITION(aFrame, "null ptr");
 381   while (aBegin != aEnd) {
 382     --aEnd;
 383     PRInt32 ix = aEnd->IndexOf(aFrame);
 384     if (ix >= 0) {
 385       *aFrameIndexInLine = ix;
 386       return PR_TRUE;
 387     }
 388   }
 389   *aFrameIndexInLine = -1;
 390   return PR_FALSE;
 391 }
 392
 393 nsCollapsingMargin
 394 nsLineBox::GetCarriedOutBottomMargin() const
 395 {
 396   NS_ASSERTION(IsBlock(),
 397                "GetCarriedOutBottomMargin called on non-block line.");
 398   return (IsBlock() && mBlockData)
 399     ? mBlockData->mCarriedOutBottomMargin
 400     : nsCollapsingMargin();
 401 }
 402
 403 PRBool
 404 nsLineBox::SetCarriedOutBottomMargin(nsCollapsingMargin aValue)
 405 {
 406   PRBool changed = PR_FALSE;
 407   if (IsBlock()) {
 408     if (!aValue.IsZero()) {
 409       if (!mBlockData) {
 410         mBlockData = new ExtraBlockData(mBounds);
 411       }
 412       if (mBlockData) {
 413         changed = aValue != mBlockData->mCarriedOutBottomMargin;
 414         mBlockData->mCarriedOutBottomMargin = aValue;
 415       }
 416     }
 417     else if (mBlockData) {
 418       changed = aValue != mBlockData->mCarriedOutBottomMargin;
 419       mBlockData->mCarriedOutBottomMargin = aValue;
 420       MaybeFreeData();
 421     }
 422   }
 423   return changed;
 424 }
 425
 426 void
 427 nsLineBox::MaybeFreeData()
 428 {
 429   if (mData && (mData->mCombinedArea == mBounds)) {
 430     if (IsInline()) {
 431       if (mInlineData->mFloats.IsEmpty()) {
 432         delete mInlineData;
 433         mInlineData = nsnull;
 434       }
 435     }
 436     else if (mBlockData->mCarriedOutBottomMargin.IsZero()) {
 437       delete mBlockData;
 438       mBlockData = nsnull;
 439     }
 440   }
 441 }
 442
 443 // XXX get rid of this???
 444 nsFloatCache*
 445 nsLineBox::GetFirstFloat()
 446 {
 447   NS_ABORT_IF_FALSE(IsInline(), "block line can't have floats");
 448   return mInlineData ? mInlineData->mFloats.Head() : nsnull;
 449 }
 450
 451 // XXX this might be too eager to free memory
 452 void
 453 nsLineBox::FreeFloats(nsFloatCacheFreeList& aFreeList)
 454 {
 455   NS_ABORT_IF_FALSE(IsInline(), "block line can't have floats");
 456   if (IsInline() && mInlineData) {
 457     if (mInlineData->mFloats.NotEmpty()) {
 458       aFreeList.Append(mInlineData->mFloats);
 459     }
 460     MaybeFreeData();
 461   }
 462 }
 463
 464 void
 465 nsLineBox::AppendFloats(nsFloatCacheFreeList& aFreeList)
 466 {
 467   NS_ABORT_IF_FALSE(IsInline(), "block line can't have floats");
 468   if (IsInline()) {
 469     if (aFreeList.NotEmpty()) {
 470       if (!mInlineData) {
 471         mInlineData = new ExtraInlineData(mBounds);
 472       }
 473       if (mInlineData) {
 474         mInlineData->mFloats.Append(aFreeList);
 475       }
 476     }
 477   }
 478 }
 479
 480 PRBool
 481 nsLineBox::RemoveFloat(nsIFrame* aFrame)
 482 {
 483   NS_ABORT_IF_FALSE(IsInline(), "block line can't have floats");
 484   if (IsInline() && mInlineData) {
 485     nsFloatCache* fc = mInlineData->mFloats.Find(aFrame);
 486     if (fc) {
 487       // Note: the placeholder is part of the line's child list
 488       // and will be removed later.
 489       mInlineData->mFloats.Remove(fc);
 490       delete fc;
 491       MaybeFreeData();
 492       return PR_TRUE;
 493     }
 494   }
 495   return PR_FALSE;
 496 }
 497
 498 void
 499 nsLineBox::SetCombinedArea(const nsRect& aCombinedArea)
 500 {
 501   NS_ASSERTION(aCombinedArea.width >= 0, "illegal width for combined area");
 502   NS_ASSERTION(aCombinedArea.height >= 0, "illegal height for combined area");
 503   if (aCombinedArea != mBounds) {
 504     if (mData) {
 505       mData->mCombinedArea = aCombinedArea;
 506     }
 507     else {
 508       if (IsInline()) {
 509         mInlineData = new ExtraInlineData(aCombinedArea);
 510       }
 511       else {
 512         mBlockData = new ExtraBlockData(aCombinedArea);
 513       }
 514     }
 515   }
 516   else {
 517     if (mData) {
 518       // Store away new value so that MaybeFreeData compares against
 519       // the right value.
 520       mData->mCombinedArea = aCombinedArea;
 521     }
 522     MaybeFreeData();
 523   }
 524 }
 525
 526 //----------------------------------------------------------------------
 527
 528
 529 static nsLineBox* gDummyLines[1];
 530
 531 nsLineIterator::nsLineIterator()
 532 {
 533   mLines = gDummyLines;
 534   mNumLines = 0;
 535   mIndex = 0;
 536   mRightToLeft = PR_FALSE;
 537 }
 538
 539 nsLineIterator::~nsLineIterator()
 540 {
 541   if (mLines != gDummyLines) {
 542     delete [] mLines;
 543   }
 544 }
 545
 546 NS_IMPL_ISUPPORTS2(nsLineIterator, nsILineIterator, nsILineIteratorNavigator)
 547
 548 nsresult
 549 nsLineIterator::Init(nsLineList& aLines, PRBool aRightToLeft)
 550 {
 551   mRightToLeft = aRightToLeft;
 552
 553   // Count the lines
 554   PRInt32 numLines = aLines.size();
 555   if (0 == numLines) {
 556     // Use gDummyLines so that we don't need null pointer checks in
 557     // the accessor methods
 558     mLines = gDummyLines;
 559     return NS_OK;
 560   }
 561
 562   // Make a linear array of the lines
 563   mLines = new nsLineBox*[numLines];
 564   if (!mLines) {
 565     // Use gDummyLines so that we don't need null pointer checks in
 566     // the accessor methods
 567     mLines = gDummyLines;
 568     return NS_ERROR_OUT_OF_MEMORY;
 569   }
 570   nsLineBox** lp = mLines;
 571   for (nsLineList::iterator line = aLines.begin(), line_end = aLines.end() ;
 572        line != line_end;
 573        ++line)
 574   {
 575     *lp++ = line;
 576   }
 577   mNumLines = numLines;
 578   return NS_OK;
 579 }
 580
 581 NS_IMETHODIMP
 582 nsLineIterator::GetNumLines(PRInt32* aResult)
 583 {
 584   NS_PRECONDITION(aResult, "null OUT ptr");
 585   if (!aResult) {
 586     return NS_ERROR_NULL_POINTER;
 587   }
 588   *aResult = mNumLines;
 589   return NS_OK;
 590 }
 591
 592 NS_IMETHODIMP
 593 nsLineIterator::GetDirection(PRBool* aIsRightToLeft)
 594 {
 595   NS_PRECONDITION(aIsRightToLeft, "null OUT ptr");
 596   if (!aIsRightToLeft) {
 597     return NS_ERROR_NULL_POINTER;
 598   }
 599   *aIsRightToLeft = mRightToLeft;
 600   return NS_OK;
 601 }
 602
 603 NS_IMETHODIMP
 604 nsLineIterator::GetLine(PRInt32 aLineNumber,
 605                         nsIFrame** aFirstFrameOnLine,
 606                         PRInt32* aNumFramesOnLine,
 607                         nsRect& aLineBounds,
 608                         PRUint32* aLineFlags)
 609 {
 610   NS_ENSURE_ARG_POINTER(aFirstFrameOnLine);
 611   NS_ENSURE_ARG_POINTER(aNumFramesOnLine);
 612   NS_ENSURE_ARG_POINTER(aLineFlags);
 613
 614   if ((aLineNumber < 0) || (aLineNumber >= mNumLines)) {
 615     *aFirstFrameOnLine = nsnull;
 616     *aNumFramesOnLine = 0;
 617     aLineBounds.SetRect(0, 0, 0, 0);
 618     return NS_OK;
 619   }
 620   nsLineBox* line = mLines[aLineNumber];
 621   *aFirstFrameOnLine = line->mFirstChild;
 622   *aNumFramesOnLine = line->GetChildCount();
 623   aLineBounds = line->mBounds;
 624
 625   PRUint32 flags = 0;
 626   if (line->IsBlock()) {
 627     flags |= NS_LINE_FLAG_IS_BLOCK;
 628   }
 629   else {
 630     if (line->HasBreakAfter())
 631       flags |= NS_LINE_FLAG_ENDS_IN_BREAK;
 632   }
 633   *aLineFlags = flags;
 634
 635   return NS_OK;
 636 }
 637
 638 NS_IMETHODIMP
 639 nsLineIterator::FindLineContaining(nsIFrame* aFrame,
 640                                    PRInt32* aLineNumberResult)
 641 {
 642   nsLineBox* line = mLines[0];
 643   PRInt32 lineNumber = 0;
 644   while (lineNumber != mNumLines) {
 645     if (line->Contains(aFrame)) {
 646       *aLineNumberResult = lineNumber;
 647       return NS_OK;
 648     }
 649     line = mLines[++lineNumber];
 650   }
 651   *aLineNumberResult = -1;
 652   return NS_OK;
 653 }
 654
 655 NS_IMETHODIMP
 656 nsLineIterator::FindLineAt(nscoord aY,
 657                            PRInt32* aLineNumberResult)
 658 {
 659   nsLineBox* line = mLines[0];
 660   if (!line || (aY < line->mBounds.y)) {
 661     *aLineNumberResult = -1;
 662     return NS_OK;
 663   }
 664   PRInt32 lineNumber = 0;
 665   while (lineNumber != mNumLines) {
 666     if ((aY >= line->mBounds.y) && (aY < line->mBounds.YMost())) {
 667       *aLineNumberResult = lineNumber;
 668       return NS_OK;
 669     }
 670     line = mLines[++lineNumber];
 671   }
 672   *aLineNumberResult = mNumLines;
 673   return NS_OK;
 674 }
 675
 676 #ifdef IBMBIDI
 677 NS_IMETHODIMP
 678 nsLineIterator::CheckLineOrder(PRInt32                  aLine,
 679                                PRBool                   *aIsReordered,
 680                                nsIFrame                 **aFirstVisual,
 681                                nsIFrame                 **aLastVisual)
 682 {
 683   NS_ASSERTION (aLine >= 0 && aLine < mNumLines, "aLine out of range!");
 684   nsLineBox* line = mLines[aLine];
 685
 686   if (!line->mFirstChild) { // empty line
 687     *aIsReordered = PR_FALSE;
 688     *aFirstVisual = nsnull;
 689     *aLastVisual = nsnull;
 690     return NS_OK;
 691   }
 692
 693   nsPresContext* presContext = line->mFirstChild->PresContext();
 694
 695   nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
 696
 697   nsIFrame* leftmostFrame;
 698   nsIFrame* rightmostFrame;
 699   *aIsReordered = bidiUtils->CheckLineOrder(line->mFirstChild, line->GetChildCount(), &leftmostFrame, &rightmostFrame);
 700
 701   // map leftmost/rightmost to first/last according to paragraph direction
 702   *aFirstVisual = mRightToLeft ? rightmostFrame : leftmostFrame;
 703   *aLastVisual = mRightToLeft ? leftmostFrame : rightmostFrame;
 704
 705   return NS_OK;
 706 }
 707 #endif // IBMBIDI
 708
 709 NS_IMETHODIMP
 710 nsLineIterator::FindFrameAt(PRInt32 aLineNumber,
 711                             nscoord aX,
 712                             nsIFrame** aFrameFound,
 713                             PRBool* aXIsBeforeFirstFrame,
 714                             PRBool* aXIsAfterLastFrame)
 715 {
 716   NS_PRECONDITION(aFrameFound && aXIsBeforeFirstFrame && aXIsAfterLastFrame,
 717                   "null OUT ptr");
 718   if (!aFrameFound || !aXIsBeforeFirstFrame || !aXIsAfterLastFrame) {
 719     return NS_ERROR_NULL_POINTER;
 720   }
 721   if ((aLineNumber < 0) || (aLineNumber >= mNumLines)) {
 722     return NS_ERROR_INVALID_ARG;
 723   }
 724
 725   nsLineBox* line = mLines[aLineNumber];
 726   if (!line) {
 727     *aFrameFound = nsnull;
 728     *aXIsBeforeFirstFrame = PR_TRUE;
 729     *aXIsAfterLastFrame = PR_FALSE;
 730     return NS_OK;
 731   }
 732
 733   if (line->mBounds.width == 0 && line->mBounds.height == 0)
 734     return NS_ERROR_FAILURE;
 735
 736   nsIFrame* frame = line->mFirstChild;
 737   nsIFrame* closestFromLeft = nsnull;
 738   nsIFrame* closestFromRight = nsnull;
 739   PRInt32 n = line->GetChildCount();
 740   while (n--) {
 741     nsRect rect = frame->GetRect();
 742     if (rect.width > 0) {
 743       // If aX is inside this frame - this is it
 744       if (rect.x <= aX && rect.XMost() > aX) {
 745         closestFromLeft = closestFromRight = frame;
 746         break;
 747       }
 748       if (rect.x < aX) {
 749         if (!closestFromLeft ||
 750             rect.XMost() > closestFromLeft->GetRect().XMost())
 751           closestFromLeft = frame;
 752       }
 753       else {
 754         if (!closestFromRight ||
 755             rect.x < closestFromRight->GetRect().x)
 756           closestFromRight = frame;
 757       }
 758     }
 759     frame = frame->GetNextSibling();
 760   }
 761   if (!closestFromLeft && !closestFromRight) {
 762     // All frames were zero-width. Just take the first one.
 763     closestFromLeft = closestFromRight = line->mFirstChild;
 764   }
 765   *aXIsBeforeFirstFrame = mRightToLeft ? !closestFromRight : !closestFromLeft;
 766   *aXIsAfterLastFrame = mRightToLeft ? !closestFromLeft : !closestFromRight;
 767   if (closestFromLeft == closestFromRight) {
 768     *aFrameFound = closestFromLeft;
 769   }
 770   else if (!closestFromLeft) {
 771     *aFrameFound = closestFromRight;
 772   }
 773   else if (!closestFromRight) {
 774     *aFrameFound = closestFromLeft;
 775   }
 776   else { // we're between two frames
 777     nscoord delta = closestFromRight->GetRect().x - closestFromLeft->GetRect().XMost();
 778     if (aX < closestFromLeft->GetRect().XMost() + delta/2)
 779       *aFrameFound = closestFromLeft;
 780     else
 781       *aFrameFound = closestFromRight;
 782   }
 783   return NS_OK;
 784 }
 785
 786 NS_IMETHODIMP
 787 nsLineIterator::GetNextSiblingOnLine(nsIFrame*& aFrame, PRInt32 aLineNumber)
 788 {
 789   aFrame = aFrame->GetNextSibling();
 790   return NS_OK;
 791 }
 792
 793 //----------------------------------------------------------------------
 794
 795 #ifdef NS_BUILD_REFCNT_LOGGING
 796 nsFloatCacheList::nsFloatCacheList() :
 797   mHead(nsnull)
 798 {
 799   MOZ_COUNT_CTOR(nsFloatCacheList);
 800 }
 801 #endif
 802
 803 nsFloatCacheList::~nsFloatCacheList()
 804 {
 805   DeleteAll();
 806   MOZ_COUNT_DTOR(nsFloatCacheList);
 807 }
 808
 809 void
 810 nsFloatCacheList::DeleteAll()
 811 {
 812   nsFloatCache* c = mHead;
 813   while (c) {
 814     nsFloatCache* next = c->Next();
 815     delete c;
 816     c = next;
 817   }
 818   mHead = nsnull;
 819 }
 820
 821 nsFloatCache*
 822 nsFloatCacheList::Tail() const
 823 {
 824   nsFloatCache* fc = mHead;
 825   while (fc) {
 826     if (!fc->mNext) {
 827       break;
 828     }
 829     fc = fc->mNext;
 830   }
 831   return fc;
 832 }
 833
 834 void
 835 nsFloatCacheList::Append(nsFloatCacheFreeList& aList)
 836 {
 837   NS_PRECONDITION(aList.NotEmpty(), "Appending empty list will fail");
 838
 839   nsFloatCache* tail = Tail();
 840   if (tail) {
 841     NS_ASSERTION(!tail->mNext, "Bogus!");
 842     tail->mNext = aList.mHead;
 843   }
 844   else {
 845     NS_ASSERTION(!mHead, "Bogus!");
 846     mHead = aList.mHead;
 847   }
 848   aList.mHead = nsnull;
 849   aList.mTail = nsnull;
 850 }
 851
 852 nsFloatCache*
 853 nsFloatCacheList::Find(nsIFrame* aOutOfFlowFrame)
 854 {
 855   nsFloatCache* fc = mHead;
 856   while (fc) {
 857     if (fc->mPlaceholder->GetOutOfFlowFrame() == aOutOfFlowFrame) {
 858       break;
 859     }
 860     fc = fc->Next();
 861   }
 862   return fc;
 863 }
 864
 865 nsFloatCache*
 866 nsFloatCacheList::RemoveAndReturnPrev(nsFloatCache* aElement)
 867 {
 868   nsFloatCache* fc = mHead;
 869   nsFloatCache* prev = nsnull;
 870   while (fc) {
 871     if (fc == aElement) {
 872       if (prev) {
 873         prev->mNext = fc->mNext;
 874       } else {
 875         mHead = fc->mNext;
 876       }
 877       return prev;
 878     }
 879     prev = fc;
 880     fc = fc->mNext;
 881   }
 882   return nsnull;
 883 }
 884
 885 //----------------------------------------------------------------------
 886
 887 #ifdef NS_BUILD_REFCNT_LOGGING
 888 nsFloatCacheFreeList::nsFloatCacheFreeList() :
 889   mTail(nsnull)
 890 {
 891   MOZ_COUNT_CTOR(nsFloatCacheFreeList);
 892 }
 893
 894 nsFloatCacheFreeList::~nsFloatCacheFreeList()
 895 {
 896   MOZ_COUNT_DTOR(nsFloatCacheFreeList);
 897 }
 898 #endif
 899
 900 void
 901 nsFloatCacheFreeList::Append(nsFloatCacheList& aList)
 902 {
 903   NS_PRECONDITION(aList.NotEmpty(), "Appending empty list will fail");
 904
 905   if (mTail) {
 906     NS_ASSERTION(!mTail->mNext, "Bogus");
 907     mTail->mNext = aList.mHead;
 908   }
 909   else {
 910     NS_ASSERTION(!mHead, "Bogus");
 911     mHead = aList.mHead;
 912   }
 913   mTail = aList.Tail();
 914   aList.mHead = nsnull;
 915 }
 916
 917 void
 918 nsFloatCacheFreeList::Remove(nsFloatCache* aElement)
 919 {
 920   nsFloatCache* prev = nsFloatCacheList::RemoveAndReturnPrev(aElement);
 921   if (mTail == aElement) {
 922     mTail = prev;
 923   }
 924 }
 925
 926 void
 927 nsFloatCacheFreeList::DeleteAll()
 928 {
 929   nsFloatCacheList::DeleteAll();
 930   mTail = nsnull;
 931 }
 932
 933 nsFloatCache*
 934 nsFloatCacheFreeList::Alloc()
 935 {
 936   nsFloatCache* fc = mHead;
 937   if (mHead) {
 938     if (mHead == mTail) {
 939       mHead = mTail = nsnull;
 940     }
 941     else {
 942       mHead = fc->mNext;
 943     }
 944     fc->mNext = nsnull;
 945   }
 946   else {
 947     fc = new nsFloatCache();
 948   }
 949   return fc;
 950 }
 951
 952 void
 953 nsFloatCacheFreeList::Append(nsFloatCache* aFloat)
 954 {
 955   NS_ASSERTION(!aFloat->mNext, "Bogus!");
 956   aFloat->mNext = nsnull;
 957   if (mTail) {
 958     NS_ASSERTION(!mTail->mNext, "Bogus!");
 959     mTail->mNext = aFloat;
 960     mTail = aFloat;
 961   }
 962   else {
 963     NS_ASSERTION(!mHead, "Bogus!");
 964     mHead = mTail = aFloat;
 965   }
 966 }
 967
 968 //----------------------------------------------------------------------
 969
 970 nsFloatCache::nsFloatCache()
 971   : mPlaceholder(nsnull),
 972     mNext(nsnull)
 973 {
 974   MOZ_COUNT_CTOR(nsFloatCache);
 975 }
 976
 977 #ifdef NS_BUILD_REFCNT_LOGGING
 978 nsFloatCache::~nsFloatCache()
 979 {
 980   MOZ_COUNT_DTOR(nsFloatCache);
 981 }
 982 #endif