layout/generic/nsLineBox.h

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