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 /* class for maintaining a linked list of child frames */
  40
  41 #include "nsFrameList.h"
  42 #ifdef NS_DEBUG
  43 #include "nsIFrameDebug.h"
  44 #endif
  45 #include "nsLayoutUtils.h"
  46
  47 #ifdef IBMBIDI
  48 #include "nsCOMPtr.h"
  49 #include "nsGkAtoms.h"
  50 #include "nsILineIterator.h"
  51 #include "nsBidiPresUtils.h"
  52 #endif // IBMBIDI
  53
  54 void
  55 nsFrameList::Destroy()
  56 {
  57   DestroyFrames();
  58   delete this;
  59 }
  60
  61 void
  62 nsFrameList::DestroyFrames()
  63 {
  64   nsIFrame* next;
  65   for (nsIFrame* frame = mFirstChild; frame; frame = next) {
  66     next = frame->GetNextSibling();
  67     frame->Destroy();
  68     mFirstChild = next;
  69   }
  70 }
  71
  72 void
  73 nsFrameList::AppendFrames(nsIFrame* aParent, nsIFrame* aFrameList)
  74 {
  75   NS_PRECONDITION(nsnull != aFrameList, "null ptr");
  76   if (nsnull != aFrameList) {
  77     nsIFrame* lastChild = LastChild();
  78     if (nsnull == lastChild) {
  79       mFirstChild = aFrameList;
  80     }
  81     else {
  82       lastChild->SetNextSibling(aFrameList);
  83     }
  84     if (aParent) {
  85       for (nsIFrame* frame = aFrameList; frame;
  86            frame = frame->GetNextSibling()) {
  87         frame->SetParent(aParent);
  88       }
  89     }
  90   }
  91 #ifdef DEBUG
  92   CheckForLoops();
  93 #endif
  94 }
  95
  96 void
  97 nsFrameList::AppendFrame(nsIFrame* aParent, nsIFrame* aFrame)
  98 {
  99   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 100   if (nsnull != aFrame) {
 101     NS_PRECONDITION(!aFrame->GetNextSibling(), "Can only append one frame here");
 102     nsIFrame* lastChild = LastChild();
 103     if (nsnull == lastChild) {
 104       mFirstChild = aFrame;
 105     }
 106     else {
 107       lastChild->SetNextSibling(aFrame);
 108     }
 109     if (nsnull != aParent) {
 110       aFrame->SetParent(aParent);
 111     }
 112   }
 113 #ifdef DEBUG
 114   CheckForLoops();
 115 #endif
 116 }
 117
 118 PRBool
 119 nsFrameList::RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint)
 120 {
 121   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 122   if (aFrame) {
 123     nsIFrame* nextFrame = aFrame->GetNextSibling();
 124     if (aFrame == mFirstChild) {
 125       mFirstChild = nextFrame;
 126       aFrame->SetNextSibling(nsnull);
 127       return PR_TRUE;
 128     }
 129     else {
 130       nsIFrame* prevSibling = aPrevSiblingHint;
 131       if (!prevSibling || prevSibling->GetNextSibling() != aFrame) {
 132         prevSibling = GetPrevSiblingFor(aFrame);
 133       }
 134       if (prevSibling) {
 135         prevSibling->SetNextSibling(nextFrame);
 136         aFrame->SetNextSibling(nsnull);
 137         return PR_TRUE;
 138       }
 139     }
 140   }
 141   // aFrame was not in the list.
 142   return PR_FALSE;
 143 }
 144
 145 PRBool
 146 nsFrameList::RemoveFirstChild()
 147 {
 148   if (mFirstChild) {
 149     nsIFrame* nextFrame = mFirstChild->GetNextSibling();
 150     mFirstChild->SetNextSibling(nsnull);
 151     mFirstChild = nextFrame;
 152     return PR_TRUE;
 153   }
 154   return PR_FALSE;
 155 }
 156
 157 PRBool
 158 nsFrameList::DestroyFrame(nsIFrame* aFrame)
 159 {
 160   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 161   if (RemoveFrame(aFrame)) {
 162     aFrame->Destroy();
 163     return PR_TRUE;
 164   }
 165   return PR_FALSE;
 166 }
 167
 168 void
 169 nsFrameList::InsertFrame(nsIFrame* aParent,
 170                          nsIFrame* aPrevSibling,
 171                          nsIFrame* aNewFrame)
 172 {
 173   NS_PRECONDITION(nsnull != aNewFrame, "null ptr");
 174   if (nsnull != aNewFrame) {
 175     if (aParent) {
 176       aNewFrame->SetParent(aParent);
 177     }
 178     if (nsnull == aPrevSibling) {
 179       aNewFrame->SetNextSibling(mFirstChild);
 180       mFirstChild = aNewFrame;
 181     }
 182     else {
 183       NS_ASSERTION(aNewFrame->GetParent() == aPrevSibling->GetParent(),
 184                    "prev sibling has different parent");
 185       nsIFrame* nextFrame = aPrevSibling->GetNextSibling();
 186       NS_ASSERTION(!nextFrame ||
 187                    aNewFrame->GetParent() == nextFrame->GetParent(),
 188                    "next sibling has different parent");
 189       aPrevSibling->SetNextSibling(aNewFrame);
 190       aNewFrame->SetNextSibling(nextFrame);
 191     }
 192   }
 193 #ifdef DEBUG
 194   CheckForLoops();
 195 #endif
 196 }
 197
 198 void
 199 nsFrameList::InsertFrames(nsIFrame* aParent,
 200                           nsIFrame* aPrevSibling,
 201                           nsIFrame* aFrameList)
 202 {
 203   NS_PRECONDITION(nsnull != aFrameList, "null ptr");
 204   if (nsnull != aFrameList) {
 205     nsIFrame* lastNewFrame = nsnull;
 206     if (aParent) {
 207       for (nsIFrame* frame = aFrameList; frame;
 208            frame = frame->GetNextSibling()) {
 209         frame->SetParent(aParent);
 210         lastNewFrame = frame;
 211       }
 212     }
 213
 214     // Get the last new frame if necessary
 215     if (!lastNewFrame) {
 216       nsFrameList tmp(aFrameList);
 217       lastNewFrame = tmp.LastChild();
 218     }
 219
 220     // Link the new frames into the child list
 221     if (nsnull == aPrevSibling) {
 222       lastNewFrame->SetNextSibling(mFirstChild);
 223       mFirstChild = aFrameList;
 224     }
 225     else {
 226       NS_ASSERTION(aFrameList->GetParent() == aPrevSibling->GetParent(),
 227                    "prev sibling has different parent");
 228       nsIFrame* nextFrame = aPrevSibling->GetNextSibling();
 229       NS_ASSERTION(!nextFrame ||
 230                    aFrameList->GetParent() == nextFrame->GetParent(),
 231                    "next sibling has different parent");
 232       aPrevSibling->SetNextSibling(aFrameList);
 233       lastNewFrame->SetNextSibling(nextFrame);
 234     }
 235   }
 236 #ifdef DEBUG
 237   CheckForLoops();
 238 #endif
 239 }
 240
 241 PRBool
 242 nsFrameList::Split(nsIFrame* aAfterFrame, nsIFrame** aNextFrameResult)
 243 {
 244   NS_PRECONDITION(nsnull != aAfterFrame, "null ptr");
 245   NS_PRECONDITION(nsnull != aNextFrameResult, "null ptr");
 246   NS_ASSERTION(ContainsFrame(aAfterFrame), "split after unknown frame");
 247
 248   if (aNextFrameResult && aAfterFrame) {
 249     nsIFrame* nextFrame = aAfterFrame->GetNextSibling();
 250     aAfterFrame->SetNextSibling(nsnull);
 251     *aNextFrameResult = nextFrame;
 252     return PR_TRUE;
 253   }
 254   return PR_FALSE;
 255 }
 256
 257 nsIFrame*
 258 nsFrameList::LastChild() const
 259 {
 260   nsIFrame* frame = mFirstChild;
 261   if (!frame) {
 262     return nsnull;
 263   }
 264
 265   nsIFrame* next = frame->GetNextSibling();
 266   while (next) {
 267     frame = next;
 268     next = frame->GetNextSibling();
 269   }
 270   return frame;
 271 }
 272
 273 nsIFrame*
 274 nsFrameList::FrameAt(PRInt32 aIndex) const
 275 {
 276   NS_PRECONDITION(aIndex >= 0, "invalid arg");
 277   if (aIndex < 0) return nsnull;
 278   nsIFrame* frame = mFirstChild;
 279   while ((aIndex-- > 0) && frame) {
 280     frame = frame->GetNextSibling();
 281   }
 282   return frame;
 283 }
 284
 285 PRBool
 286 nsFrameList::ContainsFrame(const nsIFrame* aFrame) const
 287 {
 288   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 289   nsIFrame* frame = mFirstChild;
 290   while (frame) {
 291     if (frame == aFrame) {
 292       return PR_TRUE;
 293     }
 294     frame = frame->GetNextSibling();
 295   }
 296   return PR_FALSE;
 297 }
 298
 299 PRBool
 300 nsFrameList::ContainsFrameBefore(const nsIFrame* aFrame, const nsIFrame* aEnd) const
 301 {
 302   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 303   nsIFrame* frame = mFirstChild;
 304   while (frame) {
 305     if (frame == aEnd) {
 306       return PR_FALSE;
 307     }
 308     if (frame == aFrame) {
 309       return PR_TRUE;
 310     }
 311     frame = frame->GetNextSibling();
 312   }
 313   return PR_FALSE;
 314 }
 315
 316 PRInt32
 317 nsFrameList::GetLength() const
 318 {
 319   PRInt32 count = 0;
 320   nsIFrame* frame = mFirstChild;
 321   while (frame) {
 322     count++;
 323     frame = frame->GetNextSibling();
 324   }
 325   return count;
 326 }
 327
 328 static int PR_CALLBACK CompareByContentOrder(const void* aF1, const void* aF2,
 329                                              void* aDummy)
 330 {
 331   const nsIFrame* f1 = static_cast<const nsIFrame*>(aF1);
 332   const nsIFrame* f2 = static_cast<const nsIFrame*>(aF2);
 333   if (f1->GetContent() != f2->GetContent()) {
 334     return nsLayoutUtils::CompareTreePosition(f1->GetContent(), f2->GetContent());
 335   }
 336
 337   if (f1 == f2) {
 338     return 0;
 339   }
 340
 341   const nsIFrame* f;
 342   for (f = f2; f; f = f->GetPrevInFlow()) {
 343     if (f == f1) {
 344       // f1 comes before f2 in the flow
 345       return -1;
 346     }
 347   }
 348   for (f = f1; f; f = f->GetPrevInFlow()) {
 349     if (f == f2) {
 350       // f1 comes after f2 in the flow
 351       return 1;
 352     }
 353   }
 354
 355   NS_ASSERTION(PR_FALSE, "Frames for same content but not in relative flow order");
 356   return 0;
 357 }
 358
 359 void
 360 nsFrameList::SortByContentOrder()
 361 {
 362   if (!mFirstChild)
 363     return;
 364
 365   nsAutoVoidArray array;
 366   nsIFrame* f;
 367   for (f = mFirstChild; f; f = f->GetNextSibling()) {
 368     array.AppendElement(f);
 369   }
 370   array.Sort(CompareByContentOrder, nsnull);
 371   f = mFirstChild = static_cast<nsIFrame*>(array.FastElementAt(0));
 372   for (PRInt32 i = 1; i < array.Count(); ++i) {
 373     nsIFrame* ff = static_cast<nsIFrame*>(array.FastElementAt(i));
 374     f->SetNextSibling(ff);
 375     f = ff;
 376   }
 377   f->SetNextSibling(nsnull);
 378 }
 379
 380 nsIFrame*
 381 nsFrameList::GetPrevSiblingFor(nsIFrame* aFrame) const
 382 {
 383   NS_PRECONDITION(nsnull != aFrame, "null ptr");
 384   if (aFrame == mFirstChild) {
 385     return nsnull;
 386   }
 387   nsIFrame* frame = mFirstChild;
 388   while (frame) {
 389     nsIFrame* next = frame->GetNextSibling();
 390     if (next == aFrame) {
 391       break;
 392     }
 393     frame = next;
 394   }
 395   return frame;
 396 }
 397
 398 void
 399 nsFrameList::VerifyParent(nsIFrame* aParent) const
 400 {
 401 #ifdef NS_DEBUG
 402   for (nsIFrame* frame = mFirstChild; frame;
 403        frame = frame->GetNextSibling()) {
 404     NS_ASSERTION(frame->GetParent() == aParent, "bad parent");
 405   }
 406 #endif
 407 }
 408
 409 #ifdef NS_DEBUG
 410 void
 411 nsFrameList::List(FILE* out) const
 412 {
 413   fputs("<\n", out);
 414   for (nsIFrame* frame = mFirstChild; frame;
 415        frame = frame->GetNextSibling()) {
 416     nsIFrameDebug*  frameDebug;
 417     if (NS_SUCCEEDED(frame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
 418       frameDebug->List(out, 1);
 419     }
 420   }
 421   fputs(">\n", out);
 422 }
 423 #endif
 424
 425 #ifdef IBMBIDI
 426 nsIFrame*
 427 nsFrameList::GetPrevVisualFor(nsIFrame* aFrame) const
 428 {
 429   nsCOMPtr<nsILineIterator> iter;
 430
 431   if (!mFirstChild)
 432     return nsnull;
 433
 434   nsIFrame* parent = mFirstChild->GetParent();
 435   if (!parent)
 436     return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
 437
 438   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
 439   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 440
 441   nsresult result = parent->QueryInterface(NS_GET_IID(nsILineIterator), getter_AddRefs(iter));
 442   if (NS_FAILED(result) || !iter) {
 443     // Parent is not a block Frame
 444     if (parent->GetType() == nsGkAtoms::lineFrame) {
 445       // Line frames are not bidi-splittable, so need to consider bidi reordering
 446       if (baseLevel == NSBIDI_LTR) {
 447         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
 448       } else { // RTL
 449         return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
 450       }
 451     } else {
 452       // Just get the next or prev sibling, depending on block and frame direction.
 453       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
 454       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
 455         return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
 456       } else {
 457         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 458       }
 459     }
 460   }
 461
 462   // Parent is a block frame, so use the LineIterator to find the previous visual
 463   // sibling on this line, or the last one on the previous line.
 464
 465   PRInt32 thisLine;
 466   if (aFrame) {
 467     result = iter->FindLineContaining(aFrame, &thisLine);
 468     if (NS_FAILED(result) || thisLine < 0)
 469       return nsnull;
 470   } else {
 471     iter->GetNumLines(&thisLine);
 472   }
 473
 474   nsIFrame* frame = nsnull;
 475   nsIFrame* firstFrameOnLine;
 476   PRInt32 numFramesOnLine;
 477   nsRect lineBounds;
 478   PRUint32 lineFlags;
 479
 480   if (aFrame) {
 481     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 482
 483     if (baseLevel == NSBIDI_LTR) {
 484       frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
 485     } else { // RTL
 486       frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
 487     }
 488   }
 489
 490   if (!frame && thisLine > 0) {
 491     // Get the last frame of the previous line
 492     iter->GetLine(thisLine - 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 493
 494     if (baseLevel == NSBIDI_LTR) {
 495       frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
 496     } else { // RTL
 497       frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
 498     }
 499   }
 500   return frame;
 501 }
 502
 503 nsIFrame*
 504 nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const
 505 {
 506   nsCOMPtr<nsILineIterator> iter;
 507
 508   if (!mFirstChild)
 509     return nsnull;
 510
 511   nsIFrame* parent = mFirstChild->GetParent();
 512   if (!parent)
 513     return aFrame ? GetPrevSiblingFor(aFrame) : mFirstChild;
 514
 515   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
 516   nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 517
 518   nsresult result = parent->QueryInterface(NS_GET_IID(nsILineIterator), getter_AddRefs(iter));
 519   if (NS_FAILED(result) || !iter) {
 520     // Parent is not a block Frame
 521     if (parent->GetType() == nsGkAtoms::lineFrame) {
 522       // Line frames are not bidi-splittable, so need to consider bidi reordering
 523       if (baseLevel == NSBIDI_LTR) {
 524         return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
 525       } else { // RTL
 526         return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
 527       }
 528     } else {
 529       // Just get the next or prev sibling, depending on block and frame direction.
 530       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
 531       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
 532         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
 533       } else {
 534         return aFrame ? GetPrevSiblingFor(aFrame) : LastChild();
 535       }
 536     }
 537   }
 538
 539   // Parent is a block frame, so use the LineIterator to find the next visual
 540   // sibling on this line, or the first one on the next line.
 541
 542   PRInt32 thisLine;
 543   if (aFrame) {
 544     result = iter->FindLineContaining(aFrame, &thisLine);
 545     if (NS_FAILED(result) || thisLine < 0)
 546       return nsnull;
 547   } else {
 548     thisLine = -1;
 549   }
 550
 551   nsIFrame* frame = nsnull;
 552   nsIFrame* firstFrameOnLine;
 553   PRInt32 numFramesOnLine;
 554   nsRect lineBounds;
 555   PRUint32 lineFlags;
 556
 557   if (aFrame) {
 558     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 559
 560     if (baseLevel == NSBIDI_LTR) {
 561       frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
 562     } else { // RTL
 563       frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
 564     }
 565   }
 566
 567   PRInt32 numLines;
 568   iter->GetNumLines(&numLines);
 569   if (!frame && thisLine < numLines - 1) {
 570     // Get the first frame of the next line
 571     iter->GetLine(thisLine + 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 572
 573     if (baseLevel == NSBIDI_LTR) {
 574       frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
 575     } else { // RTL
 576       frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
 577     }
 578   }
 579   return frame;
 580 }
 581 #endif
 582
 583 #ifdef DEBUG
 584 void
 585 nsFrameList::CheckForLoops()
 586 {
 587   if (!mFirstChild) {
 588     return;
 589   }
 590
 591   // Simple algorithm to find a loop in a linked list -- advance pointers
 592   // through it at speeds of 1 and 2, and if they ever get to be equal bail
 593   nsIFrame *first = mFirstChild, *second = mFirstChild;
 594   do {
 595     first = first->GetNextSibling();
 596     second = second->GetNextSibling();
 597     if (!second) {
 598       break;
 599     }
 600     second = second->GetNextSibling();
 601     if (first == second) {
 602       // Loop detected!  Since second advances faster, they can't both be null;
 603       // we would have broken out of the loop long ago.
 604       NS_ERROR("loop in frame list.  This will probably hang soon.");
 605       break;
 606     }
 607   } while (first && second);
 608 }
 609 #endif