layout/generic/nsLineBox.h

   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 #ifndef nsLineBox_h___
  10 #define nsLineBox_h___
  11
  12 #include "mozilla/Attributes.h"
  13 #include "mozilla/Likely.h"
  14
  15 #include "nsILineIterator.h"
  16 #include "nsIFrame.h"
  17 #include <algorithm>
  18
  19 class nsLineBox;
  20 class nsFloatCache;
  21 class nsFloatCacheList;
  22 class nsFloatCacheFreeList;
  23
  24 // State cached after reflowing a float. This state is used during
  25 // incremental reflow when we avoid reflowing a float.
  26 class nsFloatCache {
  27 public:
  28   nsFloatCache();
  29 #ifdef NS_BUILD_REFCNT_LOGGING
  30   ~nsFloatCache();
  31 #else
  32   ~nsFloatCache() { }
  33 #endif
  34
  35   nsFloatCache* Next() const { return mNext; }
  36
  37   nsIFrame* mFloat;                     // floating frame
  38
  39 protected:
  40   nsFloatCache* mNext;
  41
  42   friend class nsFloatCacheList;
  43   friend class nsFloatCacheFreeList;
  44 };
  45
  46 //----------------------------------------
  47
  48 class nsFloatCacheList {
  49 public:
  50 #ifdef NS_BUILD_REFCNT_LOGGING
  51   nsFloatCacheList();
  52 #else
  53   nsFloatCacheList() : mHead(nullptr) { }
  54 #endif
  55   ~nsFloatCacheList();
  56
  57   bool IsEmpty() const {
  58     return nullptr == mHead;
  59   }
  60
  61   bool NotEmpty() const {
  62     return nullptr != mHead;
  63   }
  64
  65   nsFloatCache* Head() const {
  66     return mHead;
  67   }
  68
  69   nsFloatCache* Tail() const;
  70
  71   void DeleteAll();
  72
  73   nsFloatCache* Find(nsIFrame* aOutOfFlowFrame);
  74
  75   // Remove a nsFloatCache from this list.  Deleting this nsFloatCache
  76   // becomes the caller's responsibility.
  77   void Remove(nsFloatCache* aElement) { RemoveAndReturnPrev(aElement); }
  78
  79   // Steal away aList's nsFloatCache objects and put them in this
  80   // list.  aList must not be empty.
  81   void Append(nsFloatCacheFreeList& aList);
  82
  83 protected:
  84   nsFloatCache* mHead;
  85
  86   // Remove a nsFloatCache from this list.  Deleting this nsFloatCache
  87   // becomes the caller's responsibility. Returns the nsFloatCache that was
  88   // before aElement, or nullptr if aElement was the first.
  89   nsFloatCache* RemoveAndReturnPrev(nsFloatCache* aElement);
  90
  91   friend class nsFloatCacheFreeList;
  92 };
  93
  94 //---------------------------------------
  95 // Like nsFloatCacheList, but with fast access to the tail
  96
  97 class nsFloatCacheFreeList : private nsFloatCacheList {
  98 public:
  99 #ifdef NS_BUILD_REFCNT_LOGGING
 100   nsFloatCacheFreeList();
 101   ~nsFloatCacheFreeList();
 102 #else
 103   nsFloatCacheFreeList() : mTail(nullptr) { }
 104   ~nsFloatCacheFreeList() { }
 105 #endif
 106
 107   // Reimplement trivial functions
 108   bool IsEmpty() const {
 109     return nullptr == mHead;
 110   }
 111
 112   nsFloatCache* Head() const {
 113     return mHead;
 114   }
 115
 116   nsFloatCache* Tail() const {
 117     return mTail;
 118   }
 119
 120   bool NotEmpty() const {
 121     return nullptr != mHead;
 122   }
 123
 124   void DeleteAll();
 125
 126   // Steal away aList's nsFloatCache objects and put them on this
 127   // free-list.  aList must not be empty.
 128   void Append(nsFloatCacheList& aList);
 129
 130   void Append(nsFloatCache* aFloatCache);
 131
 132   void Remove(nsFloatCache* aElement);
 133
 134   // Remove an nsFloatCache object from this list and return it, or create
 135   // a new one if this one is empty; Set its mFloat to aFloat.
 136   nsFloatCache* Alloc(nsIFrame* aFloat);
 137
 138 protected:
 139   nsFloatCache* mTail;
 140
 141   friend class nsFloatCacheList;
 142 };
 143
 144 //----------------------------------------------------------------------
 145
 146 #define LINE_MAX_BREAK_TYPE  ((1 << 4) - 1)
 147 #define LINE_MAX_CHILD_COUNT INT32_MAX
 148
 149 /**
 150  * Function to create a line box and initialize it with a single frame.
 151  * The allocation is infallible.
 152  * If the frame was moved from another line then you're responsible
 153  * for notifying that line using NoteFrameRemoved().  Alternatively,
 154  * it's better to use the next function that does that for you in an
 155  * optimal way.
 156  */
 157 nsLineBox* NS_NewLineBox(nsIPresShell* aPresShell, nsIFrame* aFrame,
 158                          bool aIsBlock);
 159 /**
 160  * Function to create a line box and initialize it with aCount frames
 161  * that are currently on aFromLine.  The allocation is infallible.
 162  */
 163 nsLineBox* NS_NewLineBox(nsIPresShell* aPresShell, nsLineBox* aFromLine,
 164                          nsIFrame* aFrame, int32_t aCount);
 165
 166 class nsLineList;
 167
 168 // don't use the following names outside of this file.  Instead, use
 169 // nsLineList::iterator, etc.  These are just here to allow them to
 170 // be specified as parameters to methods of nsLineBox.
 171 class nsLineList_iterator;
 172 class nsLineList_const_iterator;
 173 class nsLineList_reverse_iterator;
 174 class nsLineList_const_reverse_iterator;
 175
 176 /**
 177  * Users must have the class that is to be part of the list inherit
 178  * from nsLineLink.  If they want to be efficient, it should be the
 179  * first base class.  (This was originally nsCLink in a templatized
 180  * nsCList, but it's still useful separately.)
 181  */
 182
 183 class nsLineLink {
 184
 185   public:
 186     friend class nsLineList;
 187     friend class nsLineList_iterator;
 188     friend class nsLineList_reverse_iterator;
 189     friend class nsLineList_const_iterator;
 190     friend class nsLineList_const_reverse_iterator;
 191
 192   private:
 193     nsLineLink *_mNext; // or head
 194     nsLineLink *_mPrev; // or tail
 195
 196 };
 197
 198
 199 /**
 200  * The nsLineBox class represents a horizontal line of frames. It contains
 201  * enough state to support incremental reflow of the frames, event handling
 202  * for the frames, and rendering of the frames.
 203  */
 204 class nsLineBox MOZ_FINAL : public nsLineLink {
 205 private:
 206   nsLineBox(nsIFrame* aFrame, int32_t aCount, bool aIsBlock);
 207   ~nsLineBox();
 208
 209   // Overloaded new operator. Uses an arena (which comes from the presShell)
 210   // to perform the allocation.
 211   void* operator new(size_t sz, nsIPresShell* aPresShell) CPP_THROW_NEW;
 212   void operator delete(void* aPtr, size_t sz) = delete;
 213
 214 public:
 215   // Use these functions to allocate and destroy line boxes
 216   friend nsLineBox* NS_NewLineBox(nsIPresShell* aPresShell, nsIFrame* aFrame,
 217                                   bool aIsBlock);
 218   friend nsLineBox* NS_NewLineBox(nsIPresShell* aPresShell, nsLineBox* aFromLine,
 219                                   nsIFrame* aFrame, int32_t aCount);
 220   void Destroy(nsIPresShell* aPresShell);
 221
 222   // mBlock bit
 223   bool IsBlock() const {
 224     return mFlags.mBlock;
 225   }
 226   bool IsInline() const {
 227     return 0 == mFlags.mBlock;
 228   }
 229
 230   // mDirty bit
 231   void MarkDirty() {
 232     mFlags.mDirty = 1;
 233   }
 234   void ClearDirty() {
 235     mFlags.mDirty = 0;
 236   }
 237   bool IsDirty() const {
 238     return mFlags.mDirty;
 239   }
 240
 241   // mPreviousMarginDirty bit
 242   void MarkPreviousMarginDirty() {
 243     mFlags.mPreviousMarginDirty = 1;
 244   }
 245   void ClearPreviousMarginDirty() {
 246     mFlags.mPreviousMarginDirty = 0;
 247   }
 248   bool IsPreviousMarginDirty() const {
 249     return mFlags.mPreviousMarginDirty;
 250   }
 251
 252   // mHasClearance bit
 253   void SetHasClearance() {
 254     mFlags.mHasClearance = 1;
 255   }
 256   void ClearHasClearance() {
 257     mFlags.mHasClearance = 0;
 258   }
 259   bool HasClearance() const {
 260     return mFlags.mHasClearance;
 261   }
 262
 263   // mImpactedByFloat bit
 264   void SetLineIsImpactedByFloat(bool aValue) {
 265     mFlags.mImpactedByFloat = aValue;
 266   }
 267   bool IsImpactedByFloat() const {
 268     return mFlags.mImpactedByFloat;
 269   }
 270
 271   // mLineWrapped bit
 272   void SetLineWrapped(bool aOn) {
 273     mFlags.mLineWrapped = aOn;
 274   }
 275   bool IsLineWrapped() const {
 276     return mFlags.mLineWrapped;
 277   }
 278
 279   // mInvalidateTextRuns bit
 280   void SetInvalidateTextRuns(bool aOn) {
 281     mFlags.mInvalidateTextRuns = aOn;
 282   }
 283   bool GetInvalidateTextRuns() const {
 284     return mFlags.mInvalidateTextRuns;
 285   }
 286
 287   // mResizeReflowOptimizationDisabled bit
 288   void DisableResizeReflowOptimization() {
 289     mFlags.mResizeReflowOptimizationDisabled = true;
 290   }
 291   void EnableResizeReflowOptimization() {
 292     mFlags.mResizeReflowOptimizationDisabled = false;
 293   }
 294   bool ResizeReflowOptimizationDisabled() const {
 295     return mFlags.mResizeReflowOptimizationDisabled;
 296   }
 297
 298   // mHasBullet bit
 299   void SetHasBullet() {
 300     mFlags.mHasBullet = true;
 301     InvalidateCachedIsEmpty();
 302   }
 303   void ClearHasBullet() {
 304     mFlags.mHasBullet = false;
 305     InvalidateCachedIsEmpty();
 306   }
 307   bool HasBullet() const {
 308     return mFlags.mHasBullet;
 309   }
 310
 311   // mHadFloatPushed bit
 312   void SetHadFloatPushed() {
 313     mFlags.mHadFloatPushed = true;
 314   }
 315   void ClearHadFloatPushed() {
 316     mFlags.mHadFloatPushed = false;
 317   }
 318   bool HadFloatPushed() const {
 319     return mFlags.mHadFloatPushed;
 320   }
 321
 322 private:
 323   // Add a hash table for fast lookup when the line has more frames than this.
 324   static const uint32_t kMinChildCountForHashtable = 200;
 325
 326   /**
 327    * Take ownership of aFromLine's hash table and remove the frames that
 328    * stay on aFromLine from it, i.e. aFromLineNewCount frames starting with
 329    * mFirstChild.  This method is used to optimize moving a large number
 330    * of frames from one line to the next.
 331    */
 332   void StealHashTableFrom(nsLineBox* aFromLine, uint32_t aFromLineNewCount);
 333
 334   /**
 335    * Does the equivalent of this->NoteFrameAdded and aFromLine->NoteFrameRemoved
 336    * for each frame on this line, but in a optimized way.
 337    */
 338   void NoteFramesMovedFrom(nsLineBox* aFromLine);
 339
 340   void SwitchToHashtable()
 341   {
 342     MOZ_ASSERT(!mFlags.mHasHashedFrames);
 343     uint32_t count = GetChildCount();
 344     mFlags.mHasHashedFrames = 1;
 345     uint32_t minLength = std::max(kMinChildCountForHashtable,
 346                                   uint32_t(PL_DHASH_DEFAULT_INITIAL_LENGTH));
 347     mFrames = new nsTHashtable< nsPtrHashKey<nsIFrame> >(std::max(count, minLength));
 348     for (nsIFrame* f = mFirstChild; count-- > 0; f = f->GetNextSibling()) {
 349       mFrames->PutEntry(f);
 350     }
 351   }
 352   void SwitchToCounter() {
 353     MOZ_ASSERT(mFlags.mHasHashedFrames);
 354     uint32_t count = GetChildCount();
 355     delete mFrames;
 356     mFlags.mHasHashedFrames = 0;
 357     mChildCount = count;
 358   }
 359
 360 public:
 361   int32_t GetChildCount() const {
 362     return MOZ_UNLIKELY(mFlags.mHasHashedFrames) ? mFrames->Count() : mChildCount;
 363   }
 364
 365   /**
 366    * Register that aFrame is now on this line.
 367    */
 368   void NoteFrameAdded(nsIFrame* aFrame) {
 369     if (MOZ_UNLIKELY(mFlags.mHasHashedFrames)) {
 370       mFrames->PutEntry(aFrame);
 371     } else {
 372       if (++mChildCount >= kMinChildCountForHashtable) {
 373         SwitchToHashtable();
 374       }
 375     }
 376   }
 377
 378   /**
 379    * Register that aFrame is not on this line anymore.
 380    */
 381   void NoteFrameRemoved(nsIFrame* aFrame) {
 382     MOZ_ASSERT(GetChildCount() > 0);
 383     if (MOZ_UNLIKELY(mFlags.mHasHashedFrames)) {
 384       mFrames->RemoveEntry(aFrame);
 385       if (mFrames->Count() < kMinChildCountForHashtable) {
 386         SwitchToCounter();
 387       }
 388     } else {
 389       --mChildCount;
 390     }
 391   }
 392
 393   // mBreakType value
 394   // Break information is applied *before* the line if the line is a block,
 395   // or *after* the line if the line is an inline. Confusing, I know, but
 396   // using different names should help.
 397   bool HasBreakBefore() const {
 398     return IsBlock() && NS_STYLE_CLEAR_NONE != mFlags.mBreakType;
 399   }
 400   void SetBreakTypeBefore(uint8_t aBreakType) {
 401     NS_ASSERTION(IsBlock(), "Only blocks have break-before");
 402     NS_ASSERTION(aBreakType == NS_STYLE_CLEAR_NONE ||
 403                  aBreakType == NS_STYLE_CLEAR_LEFT ||
 404                  aBreakType == NS_STYLE_CLEAR_RIGHT ||
 405                  aBreakType == NS_STYLE_CLEAR_BOTH,
 406                  "Only float break types are allowed before a line");
 407     mFlags.mBreakType = aBreakType;
 408   }
 409   uint8_t GetBreakTypeBefore() const {
 410     return IsBlock() ? mFlags.mBreakType : NS_STYLE_CLEAR_NONE;
 411   }
 412
 413   bool HasBreakAfter() const {
 414     return !IsBlock() && NS_STYLE_CLEAR_NONE != mFlags.mBreakType;
 415   }
 416   void SetBreakTypeAfter(uint8_t aBreakType) {
 417     NS_ASSERTION(!IsBlock(), "Only inlines have break-after");
 418     NS_ASSERTION(aBreakType <= LINE_MAX_BREAK_TYPE, "bad break type");
 419     mFlags.mBreakType = aBreakType;
 420   }
 421   bool HasFloatBreakAfter() const {
 422     return !IsBlock() && (NS_STYLE_CLEAR_LEFT == mFlags.mBreakType ||
 423                           NS_STYLE_CLEAR_RIGHT == mFlags.mBreakType ||
 424                           NS_STYLE_CLEAR_BOTH == mFlags.mBreakType);
 425   }
 426   uint8_t GetBreakTypeAfter() const {
 427     return !IsBlock() ? mFlags.mBreakType : NS_STYLE_CLEAR_NONE;
 428   }
 429
 430   // mCarriedOutBEndMargin value
 431   nsCollapsingMargin GetCarriedOutBEndMargin() const;
 432   // Returns true if the margin changed
 433   bool SetCarriedOutBEndMargin(nsCollapsingMargin aValue);
 434
 435   // mFloats
 436   bool HasFloats() const {
 437     return (IsInline() && mInlineData) && mInlineData->mFloats.NotEmpty();
 438   }
 439   nsFloatCache* GetFirstFloat();
 440   void FreeFloats(nsFloatCacheFreeList& aFreeList);
 441   void AppendFloats(nsFloatCacheFreeList& aFreeList);
 442   bool RemoveFloat(nsIFrame* aFrame);
 443
 444   // Combined area is the area of the line that should influence the
 445   // overflow area of its parent block.  The combined area should be
 446   // used for painting-related things, but should never be used for
 447   // layout (except for handling of 'overflow').
 448   void SetOverflowAreas(const nsOverflowAreas& aOverflowAreas);
 449   nsRect GetOverflowArea(nsOverflowType aType) {
 450     return mData ? mData->mOverflowAreas.Overflow(aType) : GetPhysicalBounds();
 451   }
 452   nsOverflowAreas GetOverflowAreas() {
 453     if (mData) {
 454       return mData->mOverflowAreas;
 455     }
 456     nsRect bounds = GetPhysicalBounds();
 457     return nsOverflowAreas(bounds, bounds);
 458   }
 459   nsRect GetVisualOverflowArea()
 460     { return GetOverflowArea(eVisualOverflow); }
 461   nsRect GetScrollableOverflowArea()
 462     { return GetOverflowArea(eScrollableOverflow); }
 463
 464   void SlideBy(nscoord aDBCoord, nscoord aContainerWidth) {
 465     NS_ASSERTION(aContainerWidth == mContainerWidth || mContainerWidth == -1,
 466                  "container width doesn't match");
 467     mContainerWidth = aContainerWidth;
 468     mBounds.BStart(mWritingMode) += aDBCoord;
 469     if (mData) {
 470       nsPoint physicalDelta = mozilla::LogicalPoint(mWritingMode, 0, aDBCoord).
 471                                          GetPhysicalPoint(mWritingMode, 0);
 472       NS_FOR_FRAME_OVERFLOW_TYPES(otype) {
 473         mData->mOverflowAreas.Overflow(otype) += physicalDelta;
 474       }
 475     }
 476   }
 477
 478   // Container-width for the line is changing (and therefore if writing mode
 479   // was vertical-rl, the line will move physically; this is like SlideBy,
 480   // but it is the container width instead of the line's own logical coord
 481   // that is changing.
 482   nscoord UpdateContainerWidth(nscoord aNewContainerWidth)
 483   {
 484     NS_ASSERTION(mContainerWidth != -1, "container width not set");
 485     nscoord delta = mContainerWidth - aNewContainerWidth;
 486     mContainerWidth = aNewContainerWidth;
 487     // this has a physical-coordinate effect only in vertical-rl mode
 488     if (mWritingMode.IsVerticalRL() && mData) {
 489       nsPoint physicalDelta = mozilla::LogicalPoint(mWritingMode, 0, delta).
 490                                          GetPhysicalPoint(mWritingMode, 0);
 491       NS_FOR_FRAME_OVERFLOW_TYPES(otype) {
 492         mData->mOverflowAreas.Overflow(otype) += physicalDelta;
 493       }
 494     }
 495     return delta;
 496   }
 497
 498   void IndentBy(nscoord aDICoord, nscoord aContainerWidth) {
 499     NS_ASSERTION(aContainerWidth == mContainerWidth || mContainerWidth == -1,
 500                  "container width doesn't match");
 501     mContainerWidth = aContainerWidth;
 502     mBounds.IStart(mWritingMode) += aDICoord;
 503   }
 504
 505   void ExpandBy(nscoord aDISize, nscoord aContainerWidth) {
 506     NS_ASSERTION(aContainerWidth == mContainerWidth || mContainerWidth == -1,
 507                  "container width doesn't match");
 508     mContainerWidth = aContainerWidth;
 509     mBounds.ISize(mWritingMode) += aDISize;
 510   }
 511
 512   /**
 513    * The logical ascent (distance from block-start to baseline) of the
 514    * linebox is the logical ascent of the anonymous inline box (for
 515    * which we don't actually create a frame) that wraps all the
 516    * consecutive inline children of a block.
 517    *
 518    * This is currently unused for block lines.
 519    */
 520   nscoord GetLogicalAscent() const { return mAscent; }
 521   void SetLogicalAscent(nscoord aAscent) { mAscent = aAscent; }
 522
 523   nscoord BStart() const {
 524     return mBounds.BStart(mWritingMode);
 525   }
 526   nscoord BSize() const {
 527     return mBounds.BSize(mWritingMode);
 528   }
 529   nscoord BEnd() const {
 530     return mBounds.BEnd(mWritingMode);
 531   }
 532   nscoord IStart() const {
 533     return mBounds.IStart(mWritingMode);
 534   }
 535   nscoord ISize() const {
 536     return mBounds.ISize(mWritingMode);
 537   }
 538   nscoord IEnd() const {
 539     return mBounds.IEnd(mWritingMode);
 540   }
 541   void SetBoundsEmpty() {
 542     mBounds.IStart(mWritingMode) = 0;
 543     mBounds.ISize(mWritingMode) = 0;
 544     mBounds.BStart(mWritingMode) = 0;
 545     mBounds.BSize(mWritingMode) = 0;
 546   }
 547
 548   static void DeleteLineList(nsPresContext* aPresContext, nsLineList& aLines,
 549                              nsIFrame* aDestructRoot, nsFrameList* aFrames);
 550
 551   // search from end to beginning of [aBegin, aEnd)
 552   // Returns true if it found the line and false if not.
 553   // Moves aEnd as it searches so that aEnd points to the resulting line.
 554   // aLastFrameBeforeEnd is the last frame before aEnd (so if aEnd is
 555   // the end of the line list, it's just the last frame in the frame
 556   // list).
 557   static bool RFindLineContaining(nsIFrame* aFrame,
 558                                     const nsLineList_iterator& aBegin,
 559                                     nsLineList_iterator& aEnd,
 560                                     nsIFrame* aLastFrameBeforeEnd,
 561                                     int32_t* aFrameIndexInLine);
 562
 563 #ifdef DEBUG_FRAME_DUMP
 564   char* StateToString(char* aBuf, int32_t aBufSize) const;
 565
 566   void List(FILE* out, int32_t aIndent, uint32_t aFlags = 0) const;
 567   void List(FILE* out = stderr, const char* aPrefix = "", uint32_t aFlags = 0) const;
 568   nsIFrame* LastChild() const;
 569 #endif
 570
 571 private:
 572   int32_t IndexOf(nsIFrame* aFrame) const;
 573 public:
 574
 575   bool Contains(nsIFrame* aFrame) const {
 576     return MOZ_UNLIKELY(mFlags.mHasHashedFrames) ? mFrames->Contains(aFrame)
 577                                                 : IndexOf(aFrame) >= 0;
 578   }
 579
 580   // whether the line box is "logically" empty (just like nsIFrame::IsEmpty)
 581   bool IsEmpty() const;
 582
 583   // Call this only while in Reflow() for the block the line belongs
 584   // to, only between reflowing the line (or sliding it, if we skip
 585   // reflowing it) and the end of reflowing the block.
 586   bool CachedIsEmpty();
 587
 588   void InvalidateCachedIsEmpty() {
 589     mFlags.mEmptyCacheValid = false;
 590   }
 591
 592   // For debugging purposes
 593   bool IsValidCachedIsEmpty() {
 594     return mFlags.mEmptyCacheValid;
 595   }
 596
 597 #ifdef DEBUG
 598   static int32_t GetCtorCount();
 599 #endif
 600
 601   nsIFrame* mFirstChild;
 602
 603   mozilla::WritingMode mWritingMode;
 604
 605   // Physical width. Use only for physical <-> logical coordinate conversion.
 606   nscoord mContainerWidth;
 607
 608  private:
 609   mozilla::LogicalRect mBounds;
 610
 611  public:
 612   const mozilla::LogicalRect& GetBounds() { return mBounds; }
 613   nsRect GetPhysicalBounds() const
 614   {
 615     if (mBounds.IsAllZero()) {
 616       return nsRect(0, 0, 0, 0);
 617     }
 618
 619     NS_ASSERTION(mContainerWidth != -1, "mContainerWidth not initialized");
 620     return mBounds.GetPhysicalRect(mWritingMode, mContainerWidth);
 621   }
 622   void SetBounds(mozilla::WritingMode aWritingMode,
 623                  nscoord aIStart, nscoord aBStart,
 624                  nscoord aISize, nscoord aBSize,
 625                  nscoord aContainerWidth)
 626   {
 627     mWritingMode = aWritingMode;
 628     mContainerWidth = aContainerWidth;
 629     mBounds = mozilla::LogicalRect(aWritingMode, aIStart, aBStart,
 630                                    aISize, aBSize);
 631   }
 632   void SetBounds(mozilla::WritingMode aWritingMode,
 633                  nsRect aRect, nscoord aContainerWidth)
 634   {
 635     mWritingMode = aWritingMode;
 636     mContainerWidth = aContainerWidth;
 637     mBounds = mozilla::LogicalRect(aWritingMode, aRect, aContainerWidth);
 638   }
 639
 640   // mFlags.mHasHashedFrames says which one to use
 641   union {
 642     nsTHashtable< nsPtrHashKey<nsIFrame> >* mFrames;
 643     uint32_t mChildCount;
 644   };
 645
 646   struct FlagBits {
 647     uint32_t mDirty : 1;
 648     uint32_t mPreviousMarginDirty : 1;
 649     uint32_t mHasClearance : 1;
 650     uint32_t mBlock : 1;
 651     uint32_t mImpactedByFloat : 1;
 652     uint32_t mLineWrapped: 1;
 653     uint32_t mInvalidateTextRuns : 1;
 654     uint32_t mResizeReflowOptimizationDisabled: 1;  // default 0 = means that the opt potentially applies to this line. 1 = never skip reflowing this line for a resize reflow
 655     uint32_t mEmptyCacheValid: 1;
 656     uint32_t mEmptyCacheState: 1;
 657     // mHasBullet indicates that this is an inline line whose block's
 658     // bullet is adjacent to this line and non-empty.
 659     uint32_t mHasBullet : 1;
 660     // Indicates that this line *may* have a placeholder for a float
 661     // that was pushed to a later column or page.
 662     uint32_t mHadFloatPushed : 1;
 663     uint32_t mHasHashedFrames: 1;
 664     uint32_t mBreakType : 4;
 665   };
 666
 667   struct ExtraData {
 668     explicit ExtraData(const nsRect& aBounds) : mOverflowAreas(aBounds, aBounds) {
 669     }
 670     nsOverflowAreas mOverflowAreas;
 671   };
 672
 673   struct ExtraBlockData : public ExtraData {
 674     explicit ExtraBlockData(const nsRect& aBounds)
 675       : ExtraData(aBounds),
 676         mCarriedOutBEndMargin()
 677     {
 678     }
 679     nsCollapsingMargin mCarriedOutBEndMargin;
 680   };
 681
 682   struct ExtraInlineData : public ExtraData {
 683     explicit ExtraInlineData(const nsRect& aBounds) : ExtraData(aBounds) {
 684     }
 685     nsFloatCacheList mFloats;
 686   };
 687
 688 protected:
 689   nscoord mAscent;           // see |SetAscent| / |GetAscent|
 690   union {
 691     uint32_t mAllFlags;
 692     FlagBits mFlags;
 693   };
 694
 695   union {
 696     ExtraData* mData;
 697     ExtraBlockData* mBlockData;
 698     ExtraInlineData* mInlineData;
 699   };
 700
 701   void Cleanup();
 702   void MaybeFreeData();
 703 };
 704
 705 /**
 706  * A linked list type where the items in the list must inherit from
 707  * a link type to fuse allocations.
 708  *
 709  * API heavily based on the |list| class in the C++ standard.
 710  */
 711
 712 class nsLineList_iterator {
 713   public:
 714     friend class nsLineList;
 715     friend class nsLineList_reverse_iterator;
 716     friend class nsLineList_const_iterator;
 717     friend class nsLineList_const_reverse_iterator;
 718
 719     typedef nsLineList_iterator         iterator_self_type;
 720     typedef nsLineList_reverse_iterator iterator_reverse_type;
 721
 722     typedef nsLineBox&                  reference;
 723     typedef const nsLineBox&            const_reference;
 724
 725     typedef nsLineBox*                  pointer;
 726     typedef const nsLineBox*            const_pointer;
 727
 728     typedef uint32_t                    size_type;
 729     typedef int32_t                     difference_type;
 730
 731     typedef nsLineLink                  link_type;
 732
 733 #ifdef DEBUG
 734     nsLineList_iterator() { memset(&mCurrent, 0xcd, sizeof(mCurrent)); }
 735 #else
 736     // Auto generated default constructor OK.
 737 #endif
 738     // Auto generated copy-constructor OK.
 739
 740     inline iterator_self_type&
 741         operator=(const iterator_self_type& aOther);
 742     inline iterator_self_type&
 743         operator=(const iterator_reverse_type& aOther);
 744
 745     iterator_self_type& operator++()
 746     {
 747       mCurrent = mCurrent->_mNext;
 748       return *this;
 749     }
 750
 751     iterator_self_type operator++(int)
 752     {
 753       iterator_self_type rv(*this);
 754       mCurrent = mCurrent->_mNext;
 755       return rv;
 756     }
 757
 758     iterator_self_type& operator--()
 759     {
 760       mCurrent = mCurrent->_mPrev;
 761       return *this;
 762     }
 763
 764     iterator_self_type operator--(int)
 765     {
 766       iterator_self_type rv(*this);
 767       mCurrent = mCurrent->_mPrev;
 768       return rv;
 769     }
 770
 771     reference operator*()
 772     {
 773       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 774       return *static_cast<pointer>(mCurrent);
 775     }
 776
 777     pointer operator->()
 778     {
 779       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 780       return static_cast<pointer>(mCurrent);
 781     }
 782
 783     pointer get()
 784     {
 785       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 786       return static_cast<pointer>(mCurrent);
 787     }
 788
 789     operator pointer()
 790     {
 791       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 792       return static_cast<pointer>(mCurrent);
 793     }
 794
 795     const_reference operator*() const
 796     {
 797       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 798       return *static_cast<const_pointer>(mCurrent);
 799     }
 800
 801     const_pointer operator->() const
 802     {
 803       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 804       return static_cast<const_pointer>(mCurrent);
 805     }
 806
 807 #ifndef __MWERKS__
 808     operator const_pointer() const
 809     {
 810       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 811       return static_cast<const_pointer>(mCurrent);
 812     }
 813 #endif /* !__MWERKS__ */
 814
 815     iterator_self_type next()
 816     {
 817       iterator_self_type copy(*this);
 818       return ++copy;
 819     }
 820
 821     const iterator_self_type next() const
 822     {
 823       iterator_self_type copy(*this);
 824       return ++copy;
 825     }
 826
 827     iterator_self_type prev()
 828     {
 829       iterator_self_type copy(*this);
 830       return --copy;
 831     }
 832
 833     const iterator_self_type prev() const
 834     {
 835       iterator_self_type copy(*this);
 836       return --copy;
 837     }
 838
 839     // Passing by value rather than by reference and reference to const
 840     // to keep AIX happy.
 841     bool operator==(const iterator_self_type aOther) const
 842     {
 843       NS_ABORT_IF_FALSE(mListLink == aOther.mListLink, "comparing iterators over different lists");
 844       return mCurrent == aOther.mCurrent;
 845     }
 846     bool operator!=(const iterator_self_type aOther) const
 847     {
 848       NS_ABORT_IF_FALSE(mListLink == aOther.mListLink, "comparing iterators over different lists");
 849       return mCurrent != aOther.mCurrent;
 850     }
 851     bool operator==(const iterator_self_type aOther)
 852     {
 853       NS_ABORT_IF_FALSE(mListLink == aOther.mListLink, "comparing iterators over different lists");
 854       return mCurrent == aOther.mCurrent;
 855     }
 856     bool operator!=(const iterator_self_type aOther)
 857     {
 858       NS_ABORT_IF_FALSE(mListLink == aOther.mListLink, "comparing iterators over different lists");
 859       return mCurrent != aOther.mCurrent;
 860     }
 861
 862   private:
 863     link_type *mCurrent;
 864 #ifdef DEBUG
 865     link_type *mListLink; // the list's link, i.e., the end
 866 #endif
 867 };
 868
 869 class nsLineList_reverse_iterator {
 870
 871   public:
 872
 873     friend class nsLineList;
 874     friend class nsLineList_iterator;
 875     friend class nsLineList_const_iterator;
 876     friend class nsLineList_const_reverse_iterator;
 877
 878     typedef nsLineList_reverse_iterator iterator_self_type;
 879     typedef nsLineList_iterator         iterator_reverse_type;
 880
 881     typedef nsLineBox&                  reference;
 882     typedef const nsLineBox&            const_reference;
 883
 884     typedef nsLineBox*                  pointer;
 885     typedef const nsLineBox*            const_pointer;
 886
 887     typedef uint32_t                    size_type;
 888     typedef int32_t                     difference_type;
 889
 890     typedef nsLineLink                  link_type;
 891
 892 #ifdef DEBUG
 893     nsLineList_reverse_iterator() { memset(&mCurrent, 0xcd, sizeof(mCurrent)); }
 894 #else
 895     // Auto generated default constructor OK.
 896 #endif
 897     // Auto generated copy-constructor OK.
 898
 899     inline iterator_self_type&
 900         operator=(const iterator_reverse_type& aOther);
 901     inline iterator_self_type&
 902         operator=(const iterator_self_type& aOther);
 903
 904     iterator_self_type& operator++()
 905     {
 906       mCurrent = mCurrent->_mPrev;
 907       return *this;
 908     }
 909
 910     iterator_self_type operator++(int)
 911     {
 912       iterator_self_type rv(*this);
 913       mCurrent = mCurrent->_mPrev;
 914       return rv;
 915     }
 916
 917     iterator_self_type& operator--()
 918     {
 919       mCurrent = mCurrent->_mNext;
 920       return *this;
 921     }
 922
 923     iterator_self_type operator--(int)
 924     {
 925       iterator_self_type rv(*this);
 926       mCurrent = mCurrent->_mNext;
 927       return rv;
 928     }
 929
 930     reference operator*()
 931     {
 932       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 933       return *static_cast<pointer>(mCurrent);
 934     }
 935
 936     pointer operator->()
 937     {
 938       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 939       return static_cast<pointer>(mCurrent);
 940     }
 941
 942     pointer get()
 943     {
 944       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 945       return static_cast<pointer>(mCurrent);
 946     }
 947
 948     operator pointer()
 949     {
 950       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 951       return static_cast<pointer>(mCurrent);
 952     }
 953
 954     const_reference operator*() const
 955     {
 956       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 957       return *static_cast<const_pointer>(mCurrent);
 958     }
 959
 960     const_pointer operator->() const
 961     {
 962       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 963       return static_cast<const_pointer>(mCurrent);
 964     }
 965
 966 #ifndef __MWERKS__
 967     operator const_pointer() const
 968     {
 969       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
 970       return static_cast<const_pointer>(mCurrent);
 971     }
 972 #endif /* !__MWERKS__ */
 973
 974     // Passing by value rather than by reference and reference to const
 975     // to keep AIX happy.
 976     bool operator==(const iterator_self_type aOther) const
 977     {
 978       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
 979       return mCurrent == aOther.mCurrent;
 980     }
 981     bool operator!=(const iterator_self_type aOther) const
 982     {
 983       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
 984       return mCurrent != aOther.mCurrent;
 985     }
 986     bool operator==(const iterator_self_type aOther)
 987     {
 988       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
 989       return mCurrent == aOther.mCurrent;
 990     }
 991     bool operator!=(const iterator_self_type aOther)
 992     {
 993       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
 994       return mCurrent != aOther.mCurrent;
 995     }
 996
 997   private:
 998     link_type *mCurrent;
 999 #ifdef DEBUG
1000     link_type *mListLink; // the list's link, i.e., the end
1001 #endif
1002 };
1003
1004 class nsLineList_const_iterator {
1005   public:
1006
1007     friend class nsLineList;
1008     friend class nsLineList_iterator;
1009     friend class nsLineList_reverse_iterator;
1010     friend class nsLineList_const_reverse_iterator;
1011
1012     typedef nsLineList_const_iterator           iterator_self_type;
1013     typedef nsLineList_const_reverse_iterator   iterator_reverse_type;
1014     typedef nsLineList_iterator                 iterator_nonconst_type;
1015     typedef nsLineList_reverse_iterator         iterator_nonconst_reverse_type;
1016
1017     typedef nsLineBox&                  reference;
1018     typedef const nsLineBox&            const_reference;
1019
1020     typedef nsLineBox*                  pointer;
1021     typedef const nsLineBox*            const_pointer;
1022
1023     typedef uint32_t                    size_type;
1024     typedef int32_t                     difference_type;
1025
1026     typedef nsLineLink                  link_type;
1027
1028 #ifdef DEBUG
1029     nsLineList_const_iterator() { memset(&mCurrent, 0xcd, sizeof(mCurrent)); }
1030 #else
1031     // Auto generated default constructor OK.
1032 #endif
1033     // Auto generated copy-constructor OK.
1034
1035     inline iterator_self_type&
1036         operator=(const iterator_nonconst_type& aOther);
1037     inline iterator_self_type&
1038         operator=(const iterator_nonconst_reverse_type& aOther);
1039     inline iterator_self_type&
1040         operator=(const iterator_self_type& aOther);
1041     inline iterator_self_type&
1042         operator=(const iterator_reverse_type& aOther);
1043
1044     iterator_self_type& operator++()
1045     {
1046       mCurrent = mCurrent->_mNext;
1047       return *this;
1048     }
1049
1050     iterator_self_type operator++(int)
1051     {
1052       iterator_self_type rv(*this);
1053       mCurrent = mCurrent->_mNext;
1054       return rv;
1055     }
1056
1057     iterator_self_type& operator--()
1058     {
1059       mCurrent = mCurrent->_mPrev;
1060       return *this;
1061     }
1062
1063     iterator_self_type operator--(int)
1064     {
1065       iterator_self_type rv(*this);
1066       mCurrent = mCurrent->_mPrev;
1067       return rv;
1068     }
1069
1070     const_reference operator*() const
1071     {
1072       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1073       return *static_cast<const_pointer>(mCurrent);
1074     }
1075
1076     const_pointer operator->() const
1077     {
1078       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1079       return static_cast<const_pointer>(mCurrent);
1080     }
1081
1082     const_pointer get() const
1083     {
1084       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1085       return static_cast<const_pointer>(mCurrent);
1086     }
1087
1088 #ifndef __MWERKS__
1089     operator const_pointer() const
1090     {
1091       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1092       return static_cast<const_pointer>(mCurrent);
1093     }
1094 #endif /* !__MWERKS__ */
1095
1096     const iterator_self_type next() const
1097     {
1098       iterator_self_type copy(*this);
1099       return ++copy;
1100     }
1101
1102     const iterator_self_type prev() const
1103     {
1104       iterator_self_type copy(*this);
1105       return --copy;
1106     }
1107
1108     // Passing by value rather than by reference and reference to const
1109     // to keep AIX happy.
1110     bool operator==(const iterator_self_type aOther) const
1111     {
1112       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1113       return mCurrent == aOther.mCurrent;
1114     }
1115     bool operator!=(const iterator_self_type aOther) const
1116     {
1117       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1118       return mCurrent != aOther.mCurrent;
1119     }
1120     bool operator==(const iterator_self_type aOther)
1121     {
1122       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1123       return mCurrent == aOther.mCurrent;
1124     }
1125     bool operator!=(const iterator_self_type aOther)
1126     {
1127       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1128       return mCurrent != aOther.mCurrent;
1129     }
1130
1131   private:
1132     const link_type *mCurrent;
1133 #ifdef DEBUG
1134     const link_type *mListLink; // the list's link, i.e., the end
1135 #endif
1136 };
1137
1138 class nsLineList_const_reverse_iterator {
1139   public:
1140
1141     friend class nsLineList;
1142     friend class nsLineList_iterator;
1143     friend class nsLineList_reverse_iterator;
1144     friend class nsLineList_const_iterator;
1145
1146     typedef nsLineList_const_reverse_iterator   iterator_self_type;
1147     typedef nsLineList_const_iterator           iterator_reverse_type;
1148     typedef nsLineList_iterator                 iterator_nonconst_reverse_type;
1149     typedef nsLineList_reverse_iterator         iterator_nonconst_type;
1150
1151     typedef nsLineBox&                  reference;
1152     typedef const nsLineBox&            const_reference;
1153
1154     typedef nsLineBox*                  pointer;
1155     typedef const nsLineBox*            const_pointer;
1156
1157     typedef uint32_t                    size_type;
1158     typedef int32_t                     difference_type;
1159
1160     typedef nsLineLink                  link_type;
1161
1162 #ifdef DEBUG
1163     nsLineList_const_reverse_iterator() { memset(&mCurrent, 0xcd, sizeof(mCurrent)); }
1164 #else
1165     // Auto generated default constructor OK.
1166 #endif
1167     // Auto generated copy-constructor OK.
1168
1169     inline iterator_self_type&
1170         operator=(const iterator_nonconst_type& aOther);
1171     inline iterator_self_type&
1172         operator=(const iterator_nonconst_reverse_type& aOther);
1173     inline iterator_self_type&
1174         operator=(const iterator_self_type& aOther);
1175     inline iterator_self_type&
1176         operator=(const iterator_reverse_type& aOther);
1177
1178     iterator_self_type& operator++()
1179     {
1180       mCurrent = mCurrent->_mPrev;
1181       return *this;
1182     }
1183
1184     iterator_self_type operator++(int)
1185     {
1186       iterator_self_type rv(*this);
1187       mCurrent = mCurrent->_mPrev;
1188       return rv;
1189     }
1190
1191     iterator_self_type& operator--()
1192     {
1193       mCurrent = mCurrent->_mNext;
1194       return *this;
1195     }
1196
1197     iterator_self_type operator--(int)
1198     {
1199       iterator_self_type rv(*this);
1200       mCurrent = mCurrent->_mNext;
1201       return rv;
1202     }
1203
1204     const_reference operator*() const
1205     {
1206       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1207       return *static_cast<const_pointer>(mCurrent);
1208     }
1209
1210     const_pointer operator->() const
1211     {
1212       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1213       return static_cast<const_pointer>(mCurrent);
1214     }
1215
1216     const_pointer get() const
1217     {
1218       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1219       return static_cast<const_pointer>(mCurrent);
1220     }
1221
1222 #ifndef __MWERKS__
1223     operator const_pointer() const
1224     {
1225       NS_ABORT_IF_FALSE(mCurrent != mListLink, "running past end");
1226       return static_cast<const_pointer>(mCurrent);
1227     }
1228 #endif /* !__MWERKS__ */
1229
1230     // Passing by value rather than by reference and reference to const
1231     // to keep AIX happy.
1232     bool operator==(const iterator_self_type aOther) const
1233     {
1234       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1235       return mCurrent == aOther.mCurrent;
1236     }
1237     bool operator!=(const iterator_self_type aOther) const
1238     {
1239       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1240       return mCurrent != aOther.mCurrent;
1241     }
1242     bool operator==(const iterator_self_type aOther)
1243     {
1244       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1245       return mCurrent == aOther.mCurrent;
1246     }
1247     bool operator!=(const iterator_self_type aOther)
1248     {
1249       NS_ASSERTION(mListLink == aOther.mListLink, "comparing iterators over different lists");
1250       return mCurrent != aOther.mCurrent;
1251     }
1252
1253 //private:
1254     const link_type *mCurrent;
1255 #ifdef DEBUG
1256     const link_type *mListLink; // the list's link, i.e., the end
1257 #endif
1258 };
1259
1260 class nsLineList {
1261
1262   public:
1263
1264   friend class nsLineList_iterator;
1265   friend class nsLineList_reverse_iterator;
1266   friend class nsLineList_const_iterator;
1267   friend class nsLineList_const_reverse_iterator;
1268
1269   typedef uint32_t                    size_type;
1270   typedef int32_t                     difference_type;
1271
1272   typedef nsLineLink                  link_type;
1273
1274   private:
1275     link_type mLink;
1276
1277   public:
1278     typedef nsLineList                  self_type;
1279
1280     typedef nsLineBox&                  reference;
1281     typedef const nsLineBox&            const_reference;
1282
1283     typedef nsLineBox*                  pointer;
1284     typedef const nsLineBox*            const_pointer;
1285
1286     typedef nsLineList_iterator         iterator;
1287     typedef nsLineList_reverse_iterator reverse_iterator;
1288     typedef nsLineList_const_iterator   const_iterator;
1289     typedef nsLineList_const_reverse_iterator const_reverse_iterator;
1290
1291     nsLineList()
1292     {
1293       MOZ_COUNT_CTOR(nsLineList);
1294       clear();
1295     }
1296
1297     ~nsLineList()
1298     {
1299       MOZ_COUNT_DTOR(nsLineList);
1300     }
1301
1302     const_iterator begin() const
1303     {
1304       const_iterator rv;
1305       rv.mCurrent = mLink._mNext;
1306 #ifdef DEBUG
1307       rv.mListLink = &mLink;
1308 #endif
1309       return rv;
1310     }
1311
1312     iterator begin()
1313     {
1314       iterator rv;
1315       rv.mCurrent = mLink._mNext;
1316 #ifdef DEBUG
1317       rv.mListLink = &mLink;
1318 #endif
1319       return rv;
1320     }
1321
1322     iterator begin(nsLineBox* aLine)
1323     {
1324       iterator rv;
1325       rv.mCurrent = aLine;
1326 #ifdef DEBUG
1327       rv.mListLink = &mLink;
1328 #endif
1329       return rv;
1330     }
1331
1332     const_iterator end() const
1333     {
1334       const_iterator rv;
1335       rv.mCurrent = &mLink;
1336 #ifdef DEBUG
1337       rv.mListLink = &mLink;
1338 #endif
1339       return rv;
1340     }
1341
1342     iterator end()
1343     {
1344       iterator rv;
1345       rv.mCurrent = &mLink;
1346 #ifdef DEBUG
1347       rv.mListLink = &mLink;
1348 #endif
1349       return rv;
1350     }
1351
1352     const_reverse_iterator rbegin() const
1353     {
1354       const_reverse_iterator rv;
1355       rv.mCurrent = mLink._mPrev;
1356 #ifdef DEBUG
1357       rv.mListLink = &mLink;
1358 #endif
1359       return rv;
1360     }
1361
1362     reverse_iterator rbegin()
1363     {
1364       reverse_iterator rv;
1365       rv.mCurrent = mLink._mPrev;
1366 #ifdef DEBUG
1367       rv.mListLink = &mLink;
1368 #endif
1369       return rv;
1370     }
1371
1372     reverse_iterator rbegin(nsLineBox* aLine)
1373     {
1374       reverse_iterator rv;
1375       rv.mCurrent = aLine;
1376 #ifdef DEBUG
1377       rv.mListLink = &mLink;
1378 #endif
1379       return rv;
1380     }
1381
1382     const_reverse_iterator rend() const
1383     {
1384       const_reverse_iterator rv;
1385       rv.mCurrent = &mLink;
1386 #ifdef DEBUG
1387       rv.mListLink = &mLink;
1388 #endif
1389       return rv;
1390     }
1391
1392     reverse_iterator rend()
1393     {
1394       reverse_iterator rv;
1395       rv.mCurrent = &mLink;
1396 #ifdef DEBUG
1397       rv.mListLink = &mLink;
1398 #endif
1399       return rv;
1400     }
1401
1402     bool empty() const
1403     {
1404       return mLink._mNext == &mLink;
1405     }
1406
1407     // NOTE: O(N).
1408     size_type size() const
1409     {
1410       size_type count = 0;
1411       for (const link_type *cur = mLink._mNext;
1412            cur != &mLink;
1413            cur = cur->_mNext)
1414       {
1415         ++count;
1416       }
1417       return count;
1418     }
1419
1420     pointer front()
1421     {
1422       NS_ASSERTION(!empty(), "no element to return");
1423       return static_cast<pointer>(mLink._mNext);
1424     }
1425
1426     const_pointer front() const
1427     {
1428       NS_ASSERTION(!empty(), "no element to return");
1429       return static_cast<const_pointer>(mLink._mNext);
1430     }
1431
1432     pointer back()
1433     {
1434       NS_ASSERTION(!empty(), "no element to return");
1435       return static_cast<pointer>(mLink._mPrev);
1436     }
1437
1438     const_pointer back() const
1439     {
1440       NS_ASSERTION(!empty(), "no element to return");
1441       return static_cast<const_pointer>(mLink._mPrev);
1442     }
1443
1444     void push_front(pointer aNew)
1445     {
1446       aNew->_mNext = mLink._mNext;
1447       mLink._mNext->_mPrev = aNew;
1448       aNew->_mPrev = &mLink;
1449       mLink._mNext = aNew;
1450     }
1451
1452     void pop_front()
1453         // NOTE: leaves dangling next/prev pointers
1454     {
1455       NS_ASSERTION(!empty(), "no element to pop");
1456       link_type *newFirst = mLink._mNext->_mNext;
1457       newFirst->_mPrev = &mLink;
1458       // mLink._mNext->_mNext = nullptr;
1459       // mLink._mNext->_mPrev = nullptr;
1460       mLink._mNext = newFirst;
1461     }
1462
1463     void push_back(pointer aNew)
1464     {
1465       aNew->_mPrev = mLink._mPrev;
1466       mLink._mPrev->_mNext = aNew;
1467       aNew->_mNext = &mLink;
1468       mLink._mPrev = aNew;
1469     }
1470
1471     void pop_back()
1472         // NOTE: leaves dangling next/prev pointers
1473     {
1474       NS_ASSERTION(!empty(), "no element to pop");
1475       link_type *newLast = mLink._mPrev->_mPrev;
1476       newLast->_mNext = &mLink;
1477       // mLink._mPrev->_mPrev = nullptr;
1478       // mLink._mPrev->_mNext = nullptr;
1479       mLink._mPrev = newLast;
1480     }
1481
1482     // inserts x before position
1483     iterator before_insert(iterator position, pointer x)
1484     {
1485       // use |mCurrent| to prevent DEBUG_PASS_END assertions
1486       x->_mPrev = position.mCurrent->_mPrev;
1487       x->_mNext = position.mCurrent;
1488       position.mCurrent->_mPrev->_mNext = x;
1489       position.mCurrent->_mPrev = x;
1490       return --position;
1491     }
1492
1493     // inserts x after position
1494     iterator after_insert(iterator position, pointer x)
1495     {
1496       // use |mCurrent| to prevent DEBUG_PASS_END assertions
1497       x->_mNext = position.mCurrent->_mNext;
1498       x->_mPrev = position.mCurrent;
1499       position.mCurrent->_mNext->_mPrev = x;
1500       position.mCurrent->_mNext = x;
1501       return ++position;
1502     }
1503
1504     // returns iterator pointing to after the element
1505     iterator erase(iterator position)
1506         // NOTE: leaves dangling next/prev pointers
1507     {
1508       position->_mPrev->_mNext = position->_mNext;
1509       position->_mNext->_mPrev = position->_mPrev;
1510       return ++position;
1511     }
1512
1513     void swap(self_type& y)
1514     {
1515       link_type tmp(y.mLink);
1516       y.mLink = mLink;
1517       mLink = tmp;
1518
1519       if (!empty()) {
1520         mLink._mNext->_mPrev = &mLink;
1521         mLink._mPrev->_mNext = &mLink;
1522       }
1523
1524       if (!y.empty()) {
1525         y.mLink._mNext->_mPrev = &y.mLink;
1526         y.mLink._mPrev->_mNext = &y.mLink;
1527       }
1528     }
1529
1530     void clear()
1531         // NOTE:  leaves dangling next/prev pointers
1532     {
1533       mLink._mNext = &mLink;
1534       mLink._mPrev = &mLink;
1535     }
1536
1537     // inserts the conts of x before position and makes x empty
1538     void splice(iterator position, self_type& x)
1539     {
1540       // use |mCurrent| to prevent DEBUG_PASS_END assertions
1541       position.mCurrent->_mPrev->_mNext = x.mLink._mNext;
1542       x.mLink._mNext->_mPrev = position.mCurrent->_mPrev;
1543       x.mLink._mPrev->_mNext = position.mCurrent;
1544       position.mCurrent->_mPrev = x.mLink._mPrev;
1545       x.clear();
1546     }
1547
1548     // Inserts element *i from list x before position and removes
1549     // it from x.
1550     void splice(iterator position, self_type& x, iterator i)
1551     {
1552       NS_ASSERTION(!x.empty(), "Can't insert from empty list.");
1553       NS_ASSERTION(position != i && position.mCurrent != i->_mNext,
1554                    "We don't check for this case.");
1555
1556       // remove from |x|
1557       i->_mPrev->_mNext = i->_mNext;
1558       i->_mNext->_mPrev = i->_mPrev;
1559
1560       // use |mCurrent| to prevent DEBUG_PASS_END assertions
1561       // link into |this|, before-side
1562       i->_mPrev = position.mCurrent->_mPrev;
1563       position.mCurrent->_mPrev->_mNext = i.get();
1564
1565       // link into |this|, after-side
1566       i->_mNext = position.mCurrent;
1567       position.mCurrent->_mPrev = i.get();
1568     }
1569
1570     // Inserts elements in [|first|, |last|), which are in |x|,
1571     // into |this| before |position| and removes them from |x|.
1572     void splice(iterator position, self_type& x, iterator first,
1573                 iterator last)
1574     {
1575       NS_ASSERTION(!x.empty(), "Can't insert from empty list.");
1576
1577       if (first == last)
1578         return;
1579
1580       --last; // so we now want to move [first, last]
1581       // remove from |x|
1582       first->_mPrev->_mNext = last->_mNext;
1583       last->_mNext->_mPrev = first->_mPrev;
1584
1585       // use |mCurrent| to prevent DEBUG_PASS_END assertions
1586       // link into |this|, before-side
1587       first->_mPrev = position.mCurrent->_mPrev;
1588       position.mCurrent->_mPrev->_mNext = first.get();
1589
1590       // link into |this|, after-side
1591       last->_mNext = position.mCurrent;
1592       position.mCurrent->_mPrev = last.get();
1593     }
1594
1595 };
1596
1597
1598 // Many of these implementations of operator= don't work yet.  I don't
1599 // know why.
1600
1601 #ifdef DEBUG
1602
1603   // NOTE: ASSIGN_FROM is meant to be used *only* as the entire body
1604   // of a function and therefore lacks PR_{BEGIN,END}_MACRO
1605 #define ASSIGN_FROM(other_)          \
1606   mCurrent = other_.mCurrent;        \
1607   mListLink = other_.mListLink;      \
1608   return *this;
1609
1610 #else /* !NS_LINELIST_DEBUG_PASS_END */
1611
1612 #define ASSIGN_FROM(other_)          \
1613   mCurrent = other_.mCurrent;        \
1614   return *this;
1615
1616 #endif /* !NS_LINELIST_DEBUG_PASS_END */
1617
1618 inline
1619 nsLineList_iterator&
1620 nsLineList_iterator::operator=(const nsLineList_iterator& aOther)
1621 {
1622   ASSIGN_FROM(aOther)
1623 }
1624
1625 inline
1626 nsLineList_iterator&
1627 nsLineList_iterator::operator=(const nsLineList_reverse_iterator& aOther)
1628 {
1629   ASSIGN_FROM(aOther)
1630 }
1631
1632 inline
1633 nsLineList_reverse_iterator&
1634 nsLineList_reverse_iterator::operator=(const nsLineList_iterator& aOther)
1635 {
1636   ASSIGN_FROM(aOther)
1637 }
1638
1639 inline
1640 nsLineList_reverse_iterator&
1641 nsLineList_reverse_iterator::operator=(const nsLineList_reverse_iterator& aOther)
1642 {
1643   ASSIGN_FROM(aOther)
1644 }
1645
1646 inline
1647 nsLineList_const_iterator&
1648 nsLineList_const_iterator::operator=(const nsLineList_iterator& aOther)
1649 {
1650   ASSIGN_FROM(aOther)
1651 }
1652
1653 inline
1654 nsLineList_const_iterator&
1655 nsLineList_const_iterator::operator=(const nsLineList_reverse_iterator& aOther)
1656 {
1657   ASSIGN_FROM(aOther)
1658 }
1659
1660 inline
1661 nsLineList_const_iterator&
1662 nsLineList_const_iterator::operator=(const nsLineList_const_iterator& aOther)
1663 {
1664   ASSIGN_FROM(aOther)
1665 }
1666
1667 inline
1668 nsLineList_const_iterator&
1669 nsLineList_const_iterator::operator=(const nsLineList_const_reverse_iterator& aOther)
1670 {
1671   ASSIGN_FROM(aOther)
1672 }
1673
1674 inline
1675 nsLineList_const_reverse_iterator&
1676 nsLineList_const_reverse_iterator::operator=(const nsLineList_iterator& aOther)
1677 {
1678   ASSIGN_FROM(aOther)
1679 }
1680
1681 inline
1682 nsLineList_const_reverse_iterator&
1683 nsLineList_const_reverse_iterator::operator=(const nsLineList_reverse_iterator& aOther)
1684 {
1685   ASSIGN_FROM(aOther)
1686 }
1687
1688 inline
1689 nsLineList_const_reverse_iterator&
1690 nsLineList_const_reverse_iterator::operator=(const nsLineList_const_iterator& aOther)
1691 {
1692   ASSIGN_FROM(aOther)
1693 }
1694
1695 inline
1696 nsLineList_const_reverse_iterator&
1697 nsLineList_const_reverse_iterator::operator=(const nsLineList_const_reverse_iterator& aOther)
1698 {
1699   ASSIGN_FROM(aOther)
1700 }
1701
1702
1703 //----------------------------------------------------------------------
1704
1705 class nsLineIterator MOZ_FINAL : public nsILineIterator
1706 {
1707 public:
1708   nsLineIterator();
1709   ~nsLineIterator();
1710
1711   virtual void DisposeLineIterator() MOZ_OVERRIDE;
1712
1713   virtual int32_t GetNumLines() MOZ_OVERRIDE;
1714   virtual bool GetDirection() MOZ_OVERRIDE;
1715   NS_IMETHOD GetLine(int32_t aLineNumber,
1716                      nsIFrame** aFirstFrameOnLine,
1717                      int32_t* aNumFramesOnLine,
1718                      nsRect& aLineBounds) MOZ_OVERRIDE;
1719   virtual int32_t FindLineContaining(nsIFrame* aFrame, int32_t aStartLine = 0) MOZ_OVERRIDE;
1720   NS_IMETHOD FindFrameAt(int32_t aLineNumber,
1721                          nsPoint aPos,
1722                          nsIFrame** aFrameFound,
1723                          bool* aPosIsBeforeFirstFrame,
1724                          bool* aPosIsAfterLastFrame) MOZ_OVERRIDE;
1725
1726   NS_IMETHOD GetNextSiblingOnLine(nsIFrame*& aFrame, int32_t aLineNumber) MOZ_OVERRIDE;
1727   NS_IMETHOD CheckLineOrder(int32_t                  aLine,
1728                             bool                     *aIsReordered,
1729                             nsIFrame                 **aFirstVisual,
1730                             nsIFrame                 **aLastVisual) MOZ_OVERRIDE;
1731   nsresult Init(nsLineList& aLines, bool aRightToLeft);
1732
1733 private:
1734   nsLineBox* PrevLine() {
1735     if (0 == mIndex) {
1736       return nullptr;
1737     }
1738     return mLines[--mIndex];
1739   }
1740
1741   nsLineBox* NextLine() {
1742     if (mIndex >= mNumLines - 1) {
1743       return nullptr;
1744     }
1745     return mLines[++mIndex];
1746   }
1747
1748   nsLineBox* LineAt(int32_t aIndex) {
1749     if ((aIndex < 0) || (aIndex >= mNumLines)) {
1750       return nullptr;
1751     }
1752     return mLines[aIndex];
1753   }
1754
1755   nsLineBox** mLines;
1756   int32_t mIndex;
1757   int32_t mNumLines;
1758   bool mRightToLeft;
1759 };
1760
1761 #endif /* nsLineBox_h___ */