layout/generic/nsFrameList.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is Mozilla Communicator client code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1998
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Pierre Phaneuf <pp@ludusdesign.com>
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #include "nsFrameList.h"
  40 #include "nsIFrame.h"
  41 #include "nsLayoutUtils.h"
  42
  43 #ifdef IBMBIDI
  44 #include "nsCOMPtr.h"
  45 #include "nsGkAtoms.h"
  46 #include "nsILineIterator.h"
  47 #include "nsBidiPresUtils.h"
  48 #endif // IBMBIDI
  49
  50 const nsFrameList* nsFrameList::sEmptyList;
  51
  52 /* static */
  53 nsresult
  54 nsFrameList::Init()
  55 {
  56   NS_PRECONDITION(!sEmptyList, "Shouldn't be allocated");
  57
  58   sEmptyList = new nsFrameList();
  59   if (!sEmptyList)
  60     return NS_ERROR_OUT_OF_MEMORY;
  61
  62   return NS_OK;
  63 }
  64
  65 void
  66 nsFrameList::Destroy()
  67 {
  68   NS_PRECONDITION(this != sEmptyList, "Shouldn't Destroy() sEmptyList");
  69
  70   DestroyFrames();
  71   delete this;
  72 }
  73
  74 void
  75 nsFrameList::DestroyFrom(nsIFrame* aDestructRoot)
  76 {
  77   NS_PRECONDITION(this != sEmptyList, "Shouldn't Destroy() sEmptyList");
  78
  79   DestroyFramesFrom(aDestructRoot);
  80   delete this;
  81 }
  82
  83 void
  84 nsFrameList::DestroyFrames()
  85 {
  86   while (nsIFrame* frame = RemoveFirstChild()) {
  87     frame->Destroy();
  88   }
  89   mLastChild = nsnull;
  90 }
  91
  92 void
  93 nsFrameList::DestroyFramesFrom(nsIFrame* aDestructRoot)
  94 {
  95   NS_PRECONDITION(aDestructRoot, "Missing destruct root");
  96
  97   while (nsIFrame* frame = RemoveFirstChild()) {
  98     frame->DestroyFrom(aDestructRoot);
  99   }
 100   mLastChild = nsnull;
 101 }
 102
 103 void
 104 nsFrameList::SetFrames(nsIFrame* aFrameList)
 105 {
 106   NS_PRECONDITION(!mFirstChild, "Losing frames");
 107
 108   mFirstChild = aFrameList;
 109   mLastChild = nsLayoutUtils::GetLastSibling(mFirstChild);
 110 }
 111
 112 void
 113 nsFrameList::RemoveFrame(nsIFrame* aFrame)
 114 {
 115   NS_PRECONDITION(aFrame, "null ptr");
 116 #ifdef DEBUG_FRAME_LIST
 117   // ContainsFrame is O(N)
 118   NS_PRECONDITION(ContainsFrame(aFrame), "wrong list");
 119 #endif
 120
 121   nsIFrame* nextFrame = aFrame->GetNextSibling();
 122   if (aFrame == mFirstChild) {
 123     mFirstChild = nextFrame;
 124     aFrame->SetNextSibling(nsnull);
 125     if (!nextFrame) {
 126       mLastChild = nsnull;
 127     }
 128   }
 129   else {
 130     nsIFrame* prevSibling = aFrame->GetPrevSibling();
 131     NS_ASSERTION(prevSibling && prevSibling->GetNextSibling() == aFrame,
 132                  "Broken frame linkage");
 133     prevSibling->SetNextSibling(nextFrame);
 134     aFrame->SetNextSibling(nsnull);
 135     if (!nextFrame) {
 136       mLastChild = prevSibling;
 137     }
 138   }
 139 }
 140
 141 PRBool
 142 nsFrameList::RemoveFrameIfPresent(nsIFrame* aFrame)
 143 {
 144   NS_PRECONDITION(aFrame, "null ptr");
 145
 146   for (Enumerator e(*this); !e.AtEnd(); e.Next()) {
 147     if (e.get() == aFrame) {
 148       RemoveFrame(aFrame);
 149       return PR_TRUE;
 150     }
 151   }
 152   return PR_FALSE;
 153 }
 154
 155 nsFrameList
 156 nsFrameList::RemoveFramesAfter(nsIFrame* aAfterFrame)
 157 {
 158   NS_PRECONDITION(NotEmpty(), "illegal operation on empty list");
 159 #ifdef DEBUG_FRAME_LIST
 160   NS_PRECONDITION(ContainsFrame(aAfterFrame), "wrong list");
 161 #endif
 162
 163   nsIFrame* tail = aAfterFrame->GetNextSibling();
 164   // if (!tail) return EmptyList();  -- worth optimizing this case?
 165   nsIFrame* oldLastChild = mLastChild;
 166   mLastChild = aAfterFrame;
 167   aAfterFrame->SetNextSibling(nsnull);
 168   return nsFrameList(tail, tail ? oldLastChild : nsnull);
 169 }
 170
 171 nsIFrame*
 172 nsFrameList::RemoveFirstChild()
 173 {
 174   if (mFirstChild) {
 175     nsIFrame* firstChild = mFirstChild;
 176     RemoveFrame(firstChild);
 177     return firstChild;
 178   }
 179   return nsnull;
 180 }
 181
 182 void
 183 nsFrameList::DestroyFrame(nsIFrame* aFrame)
 184 {
 185   NS_PRECONDITION(aFrame, "null ptr");
 186   RemoveFrame(aFrame);
 187   aFrame->Destroy();
 188 }
 189
 190 PRBool
 191 nsFrameList::DestroyFrameIfPresent(nsIFrame* aFrame)
 192 {
 193   NS_PRECONDITION(aFrame, "null ptr");
 194
 195   if (RemoveFrameIfPresent(aFrame)) {
 196     aFrame->Destroy();
 197     return PR_TRUE;
 198   }
 199   return PR_FALSE;
 200 }
 201
 202 nsFrameList::Slice
 203 nsFrameList::InsertFrames(nsIFrame* aParent, nsIFrame* aPrevSibling,
 204                           nsFrameList& aFrameList)
 205 {
 206   NS_PRECONDITION(aFrameList.NotEmpty(), "Unexpected empty list");
 207
 208   if (aParent) {
 209     aFrameList.ApplySetParent(aParent);
 210   }
 211
 212   NS_ASSERTION(IsEmpty() ||
 213                FirstChild()->GetParent() == aFrameList.FirstChild()->GetParent(),
 214                "frame to add has different parent");
 215   NS_ASSERTION(!aPrevSibling ||
 216                aPrevSibling->GetParent() == aFrameList.FirstChild()->GetParent(),
 217                "prev sibling has different parent");
 218 #ifdef DEBUG_FRAME_LIST
 219   // ContainsFrame is O(N)
 220   NS_ASSERTION(!aPrevSibling || ContainsFrame(aPrevSibling),
 221                "prev sibling is not on this list");
 222 #endif
 223
 224   nsIFrame* firstNewFrame = aFrameList.FirstChild();
 225   nsIFrame* nextSibling;
 226   if (aPrevSibling) {
 227     nextSibling = aPrevSibling->GetNextSibling();
 228     aPrevSibling->SetNextSibling(firstNewFrame);
 229   }
 230   else {
 231     nextSibling = mFirstChild;
 232     mFirstChild = firstNewFrame;
 233   }
 234
 235   nsIFrame* lastNewFrame = aFrameList.LastChild();
 236   lastNewFrame->SetNextSibling(nextSibling);
 237   if (!nextSibling) {
 238     mLastChild = lastNewFrame;
 239   }
 240
 241   VerifyList();
 242
 243   aFrameList.Clear();
 244   return Slice(*this, firstNewFrame, nextSibling);
 245 }
 246
 247 nsFrameList
 248 nsFrameList::ExtractHead(FrameLinkEnumerator& aLink)
 249 {
 250   NS_PRECONDITION(&aLink.List() == this, "Unexpected list");
 251   NS_PRECONDITION(!aLink.PrevFrame() ||
 252                   aLink.PrevFrame()->GetNextSibling() ==
 253                     aLink.NextFrame(),
 254                   "Unexpected PrevFrame()");
 255   NS_PRECONDITION(aLink.PrevFrame() ||
 256                   aLink.NextFrame() == FirstChild(),
 257                   "Unexpected NextFrame()");
 258   NS_PRECONDITION(!aLink.PrevFrame() ||
 259                   aLink.NextFrame() != FirstChild(),
 260                   "Unexpected NextFrame()");
 261   NS_PRECONDITION(aLink.mEnd == nsnull,
 262                   "Unexpected mEnd for frame link enumerator");
 263
 264   nsIFrame* prev = aLink.PrevFrame();
 265   nsIFrame* newFirstFrame = nsnull;
 266   if (prev) {
 267     // Truncate the list after |prev| and hand the first part to our new list.
 268     prev->SetNextSibling(nsnull);
 269     newFirstFrame = mFirstChild;
 270     mFirstChild = aLink.NextFrame();
 271     if (!mFirstChild) { // we handed over the whole list
 272       mLastChild = nsnull;
 273     }
 274
 275     // Now make sure aLink doesn't point to a frame we no longer have.
 276     aLink.mPrev = nsnull;
 277   }
 278   // else aLink is pointing to before our first frame.  Nothing to do.
 279
 280   return nsFrameList(newFirstFrame, prev);
 281 }
 282
 283 nsFrameList
 284 nsFrameList::ExtractTail(FrameLinkEnumerator& aLink)
 285 {
 286   NS_PRECONDITION(&aLink.List() == this, "Unexpected list");
 287   NS_PRECONDITION(!aLink.PrevFrame() ||
 288                   aLink.PrevFrame()->GetNextSibling() ==
 289                     aLink.NextFrame(),
 290                   "Unexpected PrevFrame()");
 291   NS_PRECONDITION(aLink.PrevFrame() ||
 292                   aLink.NextFrame() == FirstChild(),
 293                   "Unexpected NextFrame()");
 294   NS_PRECONDITION(!aLink.PrevFrame() ||
 295                   aLink.NextFrame() != FirstChild(),
 296                   "Unexpected NextFrame()");
 297   NS_PRECONDITION(aLink.mEnd == nsnull,
 298                   "Unexpected mEnd for frame link enumerator");
 299
 300   nsIFrame* prev = aLink.PrevFrame();
 301   nsIFrame* newFirstFrame;
 302   nsIFrame* newLastFrame;
 303   if (prev) {
 304     // Truncate the list after |prev| and hand the second part to our new list
 305     prev->SetNextSibling(nsnull);
 306     newFirstFrame = aLink.NextFrame();
 307     newLastFrame = newFirstFrame ? mLastChild : nsnull;
 308     mLastChild = prev;
 309   } else {
 310     // Hand the whole list over to our new list
 311     newFirstFrame = mFirstChild;
 312     newLastFrame = mLastChild;
 313     Clear();
 314   }
 315
 316   // Now make sure aLink doesn't point to a frame we no longer have.
 317   aLink.mFrame = nsnull;
 318
 319   NS_POSTCONDITION(aLink.AtEnd(), "What's going on here?");
 320
 321   return nsFrameList(newFirstFrame, newLastFrame);
 322 }
 323
 324 nsIFrame*
 325 nsFrameList::FrameAt(PRInt32 aIndex) const
 326 {
 327   NS_PRECONDITION(aIndex >= 0, "invalid arg");
 328   if (aIndex < 0) return nsnull;
 329   nsIFrame* frame = mFirstChild;
 330   while ((aIndex-- > 0) && frame) {
 331     frame = frame->GetNextSibling();
 332   }
 333   return frame;
 334 }
 335
 336 PRInt32
 337 nsFrameList::IndexOf(nsIFrame* aFrame) const
 338 {
 339   PRInt32 count = 0;
 340   for (nsIFrame* f = mFirstChild; f; f = f->GetNextSibling()) {
 341     if (f == aFrame)
 342       return count;
 343     ++count;
 344   }
 345   return -1;
 346 }
 347
 348 PRBool
 349 nsFrameList::ContainsFrame(const nsIFrame* aFrame) const
 350 {
 351   NS_PRECONDITION(aFrame, "null ptr");
 352
 353   nsIFrame* frame = mFirstChild;
 354   while (frame) {
 355     if (frame == aFrame) {
 356       return PR_TRUE;
 357     }
 358     frame = frame->GetNextSibling();
 359   }
 360   return PR_FALSE;
 361 }
 362
 363 PRBool
 364 nsFrameList::ContainsFrameBefore(const nsIFrame* aFrame, const nsIFrame* aEnd) const
 365 {
 366   NS_PRECONDITION(aFrame, "null ptr");
 367
 368   nsIFrame* frame = mFirstChild;
 369   while (frame) {
 370     if (frame == aEnd) {
 371       return PR_FALSE;
 372     }
 373     if (frame == aFrame) {
 374       return PR_TRUE;
 375     }
 376     frame = frame->GetNextSibling();
 377   }
 378   return PR_FALSE;
 379 }
 380
 381 PRInt32
 382 nsFrameList::GetLength() const
 383 {
 384   PRInt32 count = 0;
 385   nsIFrame* frame = mFirstChild;
 386   while (frame) {
 387     count++;
 388     frame = frame->GetNextSibling();
 389   }
 390   return count;
 391 }
 392
 393 static int CompareByContentOrder(const nsIFrame* aF1, const nsIFrame* aF2)
 394 {
 395   if (aF1->GetContent() != aF2->GetContent()) {
 396     return nsLayoutUtils::CompareTreePosition(aF1->GetContent(), aF2->GetContent());
 397   }
 398
 399   if (aF1 == aF2) {
 400     return 0;
 401   }
 402
 403   const nsIFrame* f;
 404   for (f = aF2; f; f = f->GetPrevInFlow()) {
 405     if (f == aF1) {
 406       // f1 comes before f2 in the flow
 407       return -1;
 408     }
 409   }
 410   for (f = aF1; f; f = f->GetPrevInFlow()) {
 411     if (f == aF2) {
 412       // f1 comes after f2 in the flow
 413       return 1;
 414     }
 415   }
 416
 417   NS_ASSERTION(PR_FALSE, "Frames for same content but not in relative flow order");
 418   return 0;
 419 }
 420
 421 class CompareByContentOrderComparator
 422 {
 423   public:
 424   PRBool Equals(const nsIFrame* aA, const nsIFrame* aB) const {
 425     return aA == aB;
 426   }
 427   PRBool LessThan(const nsIFrame* aA, const nsIFrame* aB) const {
 428     return CompareByContentOrder(aA, aB) < 0;
 429   }
 430 };
 431
 432 void
 433 nsFrameList::SortByContentOrder()
 434 {
 435   if (IsEmpty())
 436     return;
 437
 438   nsAutoTArray<nsIFrame*, 8> array;
 439   nsIFrame* f;
 440   for (f = mFirstChild; f; f = f->GetNextSibling()) {
 441     array.AppendElement(f);
 442   }
 443   array.Sort(CompareByContentOrderComparator());
 444   f = mFirstChild = array.ElementAt(0);
 445   for (PRUint32 i = 1; i < array.Length(); ++i) {
 446     nsIFrame* ff = array.ElementAt(i);
 447     f->SetNextSibling(ff);
 448     f = ff;
 449   }
 450   f->SetNextSibling(nsnull);
 451   mLastChild = f;
 452 }
 453
 454 void
 455 nsFrameList::ApplySetParent(nsIFrame* aParent) const
 456 {
 457   NS_ASSERTION(aParent, "null ptr");
 458
 459   for (nsIFrame* f = FirstChild(); f; f = f->GetNextSibling()) {
 460     f->SetParent(aParent);
 461   }
 462 }
 463
 464 #ifdef DEBUG
 465 void
 466 nsFrameList::List(FILE* out) const
 467 {
 468   fputs("<\n", out);
 469   for (nsIFrame* frame = mFirstChild; frame;
 470        frame = frame->GetNextSibling()) {
 471     frame->List(out, 1);
 472   }
 473   fputs(">\n", out);
 474 }
 475 #endif
 476
 477 #ifdef IBMBIDI
 478 nsIFrame*
 479 nsFrameList::GetPrevVisualFor(nsIFrame* aFrame) const
 480 {
 481   if (!mFirstChild)
 482     return nsnull;
 483
 484   nsIFrame* parent = mFirstChild->GetParent();
 485   if (!parent)
 486     return aFrame ? aFrame->GetPrevSibling() : LastChild();
 487
 488   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
 489   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 490
 491   nsAutoLineIterator iter = parent->GetLineIterator();
 492   if (!iter) {
 493     // Parent is not a block Frame
 494     if (parent->GetType() == nsGkAtoms::lineFrame) {
 495       // Line frames are not bidi-splittable, so need to consider bidi reordering
 496       if (baseLevel == NSBIDI_LTR) {
 497         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
 498       } else { // RTL
 499         return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
 500       }
 501     } else {
 502       // Just get the next or prev sibling, depending on block and frame direction.
 503       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
 504       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
 505         return aFrame ? aFrame->GetPrevSibling() : LastChild();
 506       } else {
 507         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 508       }
 509     }
 510   }
 511
 512   // Parent is a block frame, so use the LineIterator to find the previous visual
 513   // sibling on this line, or the last one on the previous line.
 514
 515   PRInt32 thisLine;
 516   if (aFrame) {
 517     thisLine = iter->FindLineContaining(aFrame);
 518     if (thisLine < 0)
 519       return nsnull;
 520   } else {
 521     thisLine = iter->GetNumLines();
 522   }
 523
 524   nsIFrame* frame = nsnull;
 525   nsIFrame* firstFrameOnLine;
 526   PRInt32 numFramesOnLine;
 527   nsRect lineBounds;
 528   PRUint32 lineFlags;
 529
 530   if (aFrame) {
 531     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 532
 533     if (baseLevel == NSBIDI_LTR) {
 534       frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
 535     } else { // RTL
 536       frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
 537     }
 538   }
 539
 540   if (!frame && thisLine > 0) {
 541     // Get the last frame of the previous line
 542     iter->GetLine(thisLine - 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 543
 544     if (baseLevel == NSBIDI_LTR) {
 545       frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
 546     } else { // RTL
 547       frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
 548     }
 549   }
 550   return frame;
 551 }
 552
 553 nsIFrame*
 554 nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const
 555 {
 556   if (!mFirstChild)
 557     return nsnull;
 558
 559   nsIFrame* parent = mFirstChild->GetParent();
 560   if (!parent)
 561     return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
 562
 563   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
 564   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 565
 566   nsAutoLineIterator iter = parent->GetLineIterator();
 567   if (!iter) {
 568     // Parent is not a block Frame
 569     if (parent->GetType() == nsGkAtoms::lineFrame) {
 570       // Line frames are not bidi-splittable, so need to consider bidi reordering
 571       if (baseLevel == NSBIDI_LTR) {
 572         return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
 573       } else { // RTL
 574         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
 575       }
 576     } else {
 577       // Just get the next or prev sibling, depending on block and frame direction.
 578       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
 579       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
 580         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 581       } else {
 582         return aFrame ? aFrame->GetPrevSibling() : LastChild();
 583       }
 584     }
 585   }
 586
 587   // Parent is a block frame, so use the LineIterator to find the next visual
 588   // sibling on this line, or the first one on the next line.
 589
 590   PRInt32 thisLine;
 591   if (aFrame) {
 592     thisLine = iter->FindLineContaining(aFrame);
 593     if (thisLine < 0)
 594       return nsnull;
 595   } else {
 596     thisLine = -1;
 597   }
 598
 599   nsIFrame* frame = nsnull;
 600   nsIFrame* firstFrameOnLine;
 601   PRInt32 numFramesOnLine;
 602   nsRect lineBounds;
 603   PRUint32 lineFlags;
 604
 605   if (aFrame) {
 606     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 607
 608     if (baseLevel == NSBIDI_LTR) {
 609       frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
 610     } else { // RTL
 611       frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
 612     }
 613   }
 614
 615   PRInt32 numLines = iter->GetNumLines();
 616   if (!frame && thisLine < numLines - 1) {
 617     // Get the first frame of the next line
 618     iter->GetLine(thisLine + 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 619
 620     if (baseLevel == NSBIDI_LTR) {
 621       frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
 622     } else { // RTL
 623       frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
 624     }
 625   }
 626   return frame;
 627 }
 628 #endif
 629
 630 #ifdef DEBUG_FRAME_LIST
 631 void
 632 nsFrameList::VerifyList() const
 633 {
 634   NS_ASSERTION((mFirstChild == nsnull) == (mLastChild == nsnull),
 635                "bad list state");
 636
 637   if (IsEmpty()) {
 638     return;
 639   }
 640
 641   // Simple algorithm to find a loop in a linked list -- advance pointers
 642   // through it at speeds of 1 and 2, and if they ever get to be equal bail
 643   nsIFrame *first = mFirstChild, *second = mFirstChild;
 644   do {
 645     first = first->GetNextSibling();
 646     second = second->GetNextSibling();
 647     if (!second) {
 648       break;
 649     }
 650     second = second->GetNextSibling();
 651     if (first == second) {
 652       // Loop detected!  Since second advances faster, they can't both be null;
 653       // we would have broken out of the loop long ago.
 654       NS_ERROR("loop in frame list.  This will probably hang soon.");
 655       return;
 656     }
 657   } while (first && second);
 658
 659   NS_ASSERTION(mLastChild == nsLayoutUtils::GetLastSibling(mFirstChild),
 660                "bogus mLastChild");
 661   // XXX we should also assert that all GetParent() are either null or
 662   // the same non-null value, but nsCSSFrameConstructor::nsFrameItems
 663   // prevents that, e.g. table captions.
 664 }
 665 #endif