layout/base/nsFrameManager.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim:cindent:ts=2:et:sw=2:
   3  *
   4  * This Source Code Form is subject to the terms of the Mozilla Public
   5  * License, v. 2.0. If a copy of the MPL was not distributed with this
   6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   7  *
   8  * This Original Code has been modified by IBM Corporation. Modifications made by IBM
   9  * described herein are Copyright (c) International Business Machines Corporation, 2000.
  10  * Modifications to Mozilla code or documentation identified per MPL Section 3.3
  11  *
  12  * Date             Modified by     Description of modification
  13  * 04/20/2000       IBM Corp.      OS/2 VisualAge build.
  14  */
  15
  16 /* storage of the frame tree and information about it */
  17
  18 #include "nscore.h"
  19 #include "nsIPresShell.h"
  20 #include "nsStyleContext.h"
  21 #include "nsCOMPtr.h"
  22 #include "plhash.h"
  23 #include "nsPlaceholderFrame.h"
  24 #include "nsGkAtoms.h"
  25 #include "nsILayoutHistoryState.h"
  26 #include "nsPresState.h"
  27 #include "mozilla/dom/Element.h"
  28 #include "nsIDocument.h"
  29
  30 #include "nsContentUtils.h"
  31 #include "nsError.h"
  32 #include "nsAutoPtr.h"
  33 #include "nsAbsoluteContainingBlock.h"
  34 #include "ChildIterator.h"
  35
  36 #include "nsFrameManager.h"
  37 #include "GeckoProfiler.h"
  38 #include "nsIStatefulFrame.h"
  39 #include "nsContainerFrame.h"
  40
  41   #ifdef DEBUG
  42     //#define DEBUG_UNDISPLAYED_MAP
  43     //#define DEBUG_DISPLAY_CONTENTS_MAP
  44   #else
  45     #undef DEBUG_UNDISPLAYED_MAP
  46     #undef DEBUG_DISPLAY_CONTENTS_MAP
  47   #endif
  48
  49 using namespace mozilla;
  50 using namespace mozilla::dom;
  51
  52 //----------------------------------------------------------------------
  53
  54 struct PlaceholderMapEntry : public PLDHashEntryHdr {
  55   // key (the out of flow frame) can be obtained through placeholder frame
  56   nsPlaceholderFrame *placeholderFrame;
  57 };
  58
  59 static bool
  60 PlaceholderMapMatchEntry(PLDHashTable *table, const PLDHashEntryHdr *hdr,
  61                          const void *key)
  62 {
  63   const PlaceholderMapEntry *entry =
  64     static_cast<const PlaceholderMapEntry*>(hdr);
  65   NS_ASSERTION(entry->placeholderFrame->GetOutOfFlowFrame() !=
  66                (void*)0xdddddddd,
  67                "Dead placeholder in placeholder map");
  68   return entry->placeholderFrame->GetOutOfFlowFrame() == key;
  69 }
  70
  71 static const PLDHashTableOps PlaceholderMapOps = {
  72   PL_DHashAllocTable,
  73   PL_DHashFreeTable,
  74   PL_DHashVoidPtrKeyStub,
  75   PlaceholderMapMatchEntry,
  76   PL_DHashMoveEntryStub,
  77   PL_DHashClearEntryStub,
  78   PL_DHashFinalizeStub,
  79   nullptr
  80 };
  81
  82 //----------------------------------------------------------------------
  83
  84 // XXXldb This seems too complicated for what I think it's doing, and it
  85 // should also be using pldhash rather than plhash to use less memory.
  86
  87 class nsFrameManagerBase::UndisplayedMap {
  88 public:
  89   explicit UndisplayedMap(uint32_t aNumBuckets = 16);
  90   ~UndisplayedMap(void);
  91
  92   UndisplayedNode* GetFirstNode(nsIContent* aParentContent);
  93
  94   nsresult AddNodeFor(nsIContent* aParentContent,
  95                                   nsIContent* aChild, nsStyleContext* aStyle);
  96
  97   void RemoveNodeFor(nsIContent* aParentContent,
  98                                  UndisplayedNode* aNode);
  99
 100   void RemoveNodesFor(nsIContent* aParentContent);
 101   UndisplayedNode* UnlinkNodesFor(nsIContent* aParentContent);
 102
 103   // Removes all entries from the hash table
 104   void  Clear(void);
 105
 106 protected:
 107   /**
 108    * Gets the entry for the provided parent content. If the content
 109    * is a <xbl:children> element, |**aParentContent| is set to
 110    * the parent of the children element.
 111    */
 112   PLHashEntry** GetEntryFor(nsIContent** aParentContent);
 113   void          AppendNodeFor(UndisplayedNode* aNode,
 114                                           nsIContent* aParentContent);
 115
 116   PLHashTable*  mTable;
 117   PLHashEntry** mLastLookup;
 118 };
 119
 120 //----------------------------------------------------------------------
 121
 122 nsFrameManager::~nsFrameManager()
 123 {
 124   NS_ASSERTION(!mPresShell, "nsFrameManager::Destroy never called");
 125 }
 126
 127 void
 128 nsFrameManager::Destroy()
 129 {
 130   NS_ASSERTION(mPresShell, "Frame manager already shut down.");
 131
 132   // Destroy the frame hierarchy.
 133   mPresShell->SetIgnoreFrameDestruction(true);
 134
 135   // Unregister all placeholders before tearing down the frame tree
 136   nsFrameManager::ClearPlaceholderFrameMap();
 137
 138   if (mRootFrame) {
 139     mRootFrame->Destroy();
 140     mRootFrame = nullptr;
 141   }
 142
 143   delete mUndisplayedMap;
 144   mUndisplayedMap = nullptr;
 145   delete mDisplayContentsMap;
 146   mDisplayContentsMap = nullptr;
 147
 148   mPresShell = nullptr;
 149 }
 150
 151 //----------------------------------------------------------------------
 152
 153 // Placeholder frame functions
 154 nsPlaceholderFrame*
 155 nsFrameManager::GetPlaceholderFrameFor(const nsIFrame* aFrame)
 156 {
 157   NS_PRECONDITION(aFrame, "null param unexpected");
 158
 159   if (mPlaceholderMap.ops) {
 160     PlaceholderMapEntry *entry = static_cast<PlaceholderMapEntry*>
 161                                             (PL_DHashTableLookup(const_cast<PLDHashTable*>(&mPlaceholderMap),
 162                                 aFrame));
 163     if (PL_DHASH_ENTRY_IS_BUSY(entry)) {
 164       return entry->placeholderFrame;
 165     }
 166   }
 167
 168   return nullptr;
 169 }
 170
 171 nsresult
 172 nsFrameManager::RegisterPlaceholderFrame(nsPlaceholderFrame* aPlaceholderFrame)
 173 {
 174   NS_PRECONDITION(aPlaceholderFrame, "null param unexpected");
 175   NS_PRECONDITION(nsGkAtoms::placeholderFrame == aPlaceholderFrame->GetType(),
 176                   "unexpected frame type");
 177   if (!mPlaceholderMap.ops) {
 178     PL_DHashTableInit(&mPlaceholderMap, &PlaceholderMapOps, nullptr,
 179                       sizeof(PlaceholderMapEntry));
 180   }
 181   PlaceholderMapEntry *entry = static_cast<PlaceholderMapEntry*>(PL_DHashTableAdd(&mPlaceholderMap,
 182                               aPlaceholderFrame->GetOutOfFlowFrame()));
 183   if (!entry)
 184     return NS_ERROR_OUT_OF_MEMORY;
 185
 186   NS_ASSERTION(!entry->placeholderFrame, "Registering a placeholder for a frame that already has a placeholder!");
 187   entry->placeholderFrame = aPlaceholderFrame;
 188
 189   return NS_OK;
 190 }
 191
 192 void
 193 nsFrameManager::UnregisterPlaceholderFrame(nsPlaceholderFrame* aPlaceholderFrame)
 194 {
 195   NS_PRECONDITION(aPlaceholderFrame, "null param unexpected");
 196   NS_PRECONDITION(nsGkAtoms::placeholderFrame == aPlaceholderFrame->GetType(),
 197                   "unexpected frame type");
 198
 199   if (mPlaceholderMap.ops) {
 200     PL_DHashTableRemove(&mPlaceholderMap,
 201                         aPlaceholderFrame->GetOutOfFlowFrame());
 202   }
 203 }
 204
 205 static PLDHashOperator
 206 UnregisterPlaceholders(PLDHashTable* table, PLDHashEntryHdr* hdr,
 207                        uint32_t number, void* arg)
 208 {
 209   PlaceholderMapEntry* entry = static_cast<PlaceholderMapEntry*>(hdr);
 210   entry->placeholderFrame->SetOutOfFlowFrame(nullptr);
 211   return PL_DHASH_NEXT;
 212 }
 213
 214 void
 215 nsFrameManager::ClearPlaceholderFrameMap()
 216 {
 217   if (mPlaceholderMap.ops) {
 218     PL_DHashTableEnumerate(&mPlaceholderMap, UnregisterPlaceholders, nullptr);
 219     PL_DHashTableFinish(&mPlaceholderMap);
 220     mPlaceholderMap.ops = nullptr;
 221   }
 222 }
 223
 224 //----------------------------------------------------------------------
 225
 226 /* static */ nsStyleContext*
 227 nsFrameManager::GetStyleContextInMap(UndisplayedMap* aMap, nsIContent* aContent)
 228 {
 229   if (!aContent) {
 230     return nullptr;
 231   }
 232   nsIContent* parent = aContent->GetParent();
 233   for (UndisplayedNode* node = aMap->GetFirstNode(parent);
 234          node; node = node->mNext) {
 235     if (node->mContent == aContent)
 236       return node->mStyle;
 237   }
 238
 239   return nullptr;
 240 }
 241
 242 /* static */ UndisplayedNode*
 243 nsFrameManager::GetAllUndisplayedNodesInMapFor(UndisplayedMap* aMap,
 244                                                nsIContent* aParentContent)
 245 {
 246   return aMap ? aMap->GetFirstNode(aParentContent) : nullptr;
 247 }
 248
 249 UndisplayedNode*
 250 nsFrameManager::GetAllUndisplayedContentIn(nsIContent* aParentContent)
 251 {
 252   return GetAllUndisplayedNodesInMapFor(mUndisplayedMap, aParentContent);
 253 }
 254
 255 /* static */ void
 256 nsFrameManager::SetStyleContextInMap(UndisplayedMap* aMap,
 257                                      nsIContent* aContent,
 258                                      nsStyleContext* aStyleContext)
 259 {
 260   NS_PRECONDITION(!aStyleContext->GetPseudo(),
 261                   "Should only have actual elements here");
 262
 263 #if defined(DEBUG_UNDISPLAYED_MAP) || defined(DEBUG_DISPLAY_BOX_CONTENTS_MAP)
 264   static int i = 0;
 265   printf("SetStyleContextInMap(%d): p=%p \n", i++, (void *)aContent);
 266 #endif
 267
 268   NS_ASSERTION(!GetStyleContextInMap(aMap, aContent),
 269                "Already have an entry for aContent");
 270
 271   nsIContent* parent = aContent->GetParent();
 272 #ifdef DEBUG
 273   nsIPresShell* shell = aStyleContext->PresContext()->PresShell();
 274   NS_ASSERTION(parent || (shell && shell->GetDocument() &&
 275                           shell->GetDocument()->GetRootElement() == aContent),
 276                "undisplayed content must have a parent, unless it's the root "
 277                "element");
 278 #endif
 279   aMap->AddNodeFor(parent, aContent, aStyleContext);
 280 }
 281
 282 void
 283 nsFrameManager::SetUndisplayedContent(nsIContent* aContent,
 284                                       nsStyleContext* aStyleContext)
 285 {
 286   if (!mUndisplayedMap) {
 287     mUndisplayedMap = new UndisplayedMap;
 288   }
 289   SetStyleContextInMap(mUndisplayedMap, aContent, aStyleContext);
 290 }
 291
 292 /* static */ void
 293 nsFrameManager::ChangeStyleContextInMap(UndisplayedMap* aMap,
 294                                         nsIContent* aContent,
 295                                         nsStyleContext* aStyleContext)
 296 {
 297   MOZ_ASSERT(aMap, "expecting a map");
 298
 299 #if defined(DEBUG_UNDISPLAYED_MAP) || defined(DEBUG_DISPLAY_BOX_CONTENTS_MAP)
 300    static int i = 0;
 301    printf("ChangeStyleContextInMap(%d): p=%p \n", i++, (void *)aContent);
 302 #endif
 303
 304   for (UndisplayedNode* node = aMap->GetFirstNode(aContent->GetParent());
 305          node; node = node->mNext) {
 306     if (node->mContent == aContent) {
 307       node->mStyle = aStyleContext;
 308       return;
 309     }
 310   }
 311
 312   MOZ_CRASH("couldn't find the entry to change");
 313 }
 314
 315 void
 316 nsFrameManager::ClearUndisplayedContentIn(nsIContent* aContent,
 317                                           nsIContent* aParentContent)
 318 {
 319 #ifdef DEBUG_UNDISPLAYED_MAP
 320   static int i = 0;
 321   printf("ClearUndisplayedContent(%d): content=%p parent=%p --> ", i++, (void *)aContent, (void*)aParentContent);
 322 #endif
 323
 324   if (mUndisplayedMap) {
 325     UndisplayedNode* node = mUndisplayedMap->GetFirstNode(aParentContent);
 326     while (node) {
 327       if (node->mContent == aContent) {
 328         mUndisplayedMap->RemoveNodeFor(aParentContent, node);
 329
 330 #ifdef DEBUG_UNDISPLAYED_MAP
 331         printf( "REMOVED!\n");
 332 #endif
 333 #ifdef DEBUG
 334         // make sure that there are no more entries for the same content
 335         nsStyleContext *context = GetUndisplayedContent(aContent);
 336         NS_ASSERTION(context == nullptr, "Found more undisplayed content data after removal");
 337 #endif
 338         return;
 339       }
 340       node = node->mNext;
 341     }
 342   }
 343 #ifdef DEBUG_UNDISPLAYED_MAP
 344   printf( "not found.\n");
 345 #endif
 346 }
 347
 348 void
 349 nsFrameManager::ClearAllUndisplayedContentIn(nsIContent* aParentContent)
 350 {
 351 #ifdef DEBUG_UNDISPLAYED_MAP
 352   static int i = 0;
 353   printf("ClearAllUndisplayedContentIn(%d): parent=%p \n", i++, (void*)aParentContent);
 354 #endif
 355
 356   if (mUndisplayedMap) {
 357     mUndisplayedMap->RemoveNodesFor(aParentContent);
 358   }
 359
 360   // Need to look at aParentContent's content list due to XBL insertions.
 361   // Nodes in aParentContent's content list do not have aParentContent as a
 362   // parent, but are treated as children of aParentContent. We iterate over
 363   // the flattened content list and just ignore any nodes we don't care about.
 364   FlattenedChildIterator iter(aParentContent);
 365   for (nsIContent* child = iter.GetNextChild(); child; child = iter.GetNextChild()) {
 366     if (child->GetParent() != aParentContent) {
 367       ClearUndisplayedContentIn(child, child->GetParent());
 368     }
 369   }
 370 }
 371
 372 //----------------------------------------------------------------------
 373
 374 void
 375 nsFrameManager::SetDisplayContents(nsIContent* aContent,
 376                                    nsStyleContext* aStyleContext)
 377 {
 378   if (!mDisplayContentsMap) {
 379     mDisplayContentsMap = new UndisplayedMap;
 380   }
 381   SetStyleContextInMap(mDisplayContentsMap, aContent, aStyleContext);
 382 }
 383
 384 UndisplayedNode*
 385 nsFrameManager::GetAllDisplayContentsIn(nsIContent* aParentContent)
 386 {
 387   return GetAllUndisplayedNodesInMapFor(mDisplayContentsMap, aParentContent);
 388 }
 389
 390 void
 391 nsFrameManager::ClearDisplayContentsIn(nsIContent* aContent,
 392                                        nsIContent* aParentContent)
 393 {
 394 #ifdef DEBUG_DISPLAY_CONTENTS_MAP
 395   static int i = 0;
 396   printf("ClearDisplayContents(%d): content=%p parent=%p --> ", i++, (void *)aContent, (void*)aParentContent);
 397 #endif
 398
 399   if (mDisplayContentsMap) {
 400     UndisplayedNode* node = mDisplayContentsMap->GetFirstNode(aParentContent);
 401     while (node) {
 402       if (node->mContent == aContent) {
 403         mDisplayContentsMap->RemoveNodeFor(aParentContent, node);
 404
 405 #ifdef DEBUG_DISPLAY_CONTENTS_MAP
 406         printf( "REMOVED!\n");
 407 #endif
 408 #ifdef DEBUG
 409         // make sure that there are no more entries for the same content
 410         nsStyleContext* context = GetDisplayContentsStyleFor(aContent);
 411         NS_ASSERTION(context == nullptr, "Found more entries for aContent after removal");
 412 #endif
 413         ClearAllDisplayContentsIn(aContent);
 414         ClearAllUndisplayedContentIn(aContent);
 415         return;
 416       }
 417       node = node->mNext;
 418     }
 419   }
 420 #ifdef DEBUG_DISPLAY_CONTENTS_MAP
 421   printf( "not found.\n");
 422 #endif
 423 }
 424
 425 void
 426 nsFrameManager::ClearAllDisplayContentsIn(nsIContent* aParentContent)
 427 {
 428 #ifdef DEBUG_DISPLAY_CONTENTS_MAP
 429   static int i = 0;
 430   printf("ClearAllDisplayContentsIn(%d): parent=%p \n", i++, (void*)aParentContent);
 431 #endif
 432
 433   if (mDisplayContentsMap) {
 434     UndisplayedNode* cur = mDisplayContentsMap->UnlinkNodesFor(aParentContent);
 435     while (cur) {
 436       UndisplayedNode* next = cur->mNext;
 437       cur->mNext = nullptr;
 438       ClearAllDisplayContentsIn(cur->mContent);
 439       ClearAllUndisplayedContentIn(cur->mContent);
 440       delete cur;
 441       cur = next;
 442     }
 443   }
 444
 445   // Need to look at aParentContent's content list due to XBL insertions.
 446   // Nodes in aParentContent's content list do not have aParentContent as a
 447   // parent, but are treated as children of aParentContent. We iterate over
 448   // the flattened content list and just ignore any nodes we don't care about.
 449   FlattenedChildIterator iter(aParentContent);
 450   for (nsIContent* child = iter.GetNextChild(); child; child = iter.GetNextChild()) {
 451     if (child->GetParent() != aParentContent) {
 452       ClearDisplayContentsIn(child, child->GetParent());
 453       ClearUndisplayedContentIn(child, child->GetParent());
 454     }
 455   }
 456 }
 457
 458 //----------------------------------------------------------------------
 459 void
 460 nsFrameManager::AppendFrames(nsContainerFrame* aParentFrame,
 461                              ChildListID       aListID,
 462                              nsFrameList&      aFrameList)
 463 {
 464   if (aParentFrame->IsAbsoluteContainer() &&
 465       aListID == aParentFrame->GetAbsoluteListID()) {
 466     aParentFrame->GetAbsoluteContainingBlock()->
 467       AppendFrames(aParentFrame, aListID, aFrameList);
 468   } else {
 469     aParentFrame->AppendFrames(aListID, aFrameList);
 470   }
 471 }
 472
 473 void
 474 nsFrameManager::InsertFrames(nsContainerFrame* aParentFrame,
 475                              ChildListID       aListID,
 476                              nsIFrame*         aPrevFrame,
 477                              nsFrameList&      aFrameList)
 478 {
 479   NS_PRECONDITION(!aPrevFrame || (!aPrevFrame->GetNextContinuation()
 480                   || (((aPrevFrame->GetNextContinuation()->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER))
 481                   && !(aPrevFrame->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER))),
 482                   "aPrevFrame must be the last continuation in its chain!");
 483
 484   if (aParentFrame->IsAbsoluteContainer() &&
 485       aListID == aParentFrame->GetAbsoluteListID()) {
 486     aParentFrame->GetAbsoluteContainingBlock()->
 487       InsertFrames(aParentFrame, aListID, aPrevFrame, aFrameList);
 488   } else {
 489     aParentFrame->InsertFrames(aListID, aPrevFrame, aFrameList);
 490   }
 491 }
 492
 493 void
 494 nsFrameManager::RemoveFrame(ChildListID     aListID,
 495                             nsIFrame*       aOldFrame)
 496 {
 497   bool wasDestroyingFrames = mIsDestroyingFrames;
 498   mIsDestroyingFrames = true;
 499
 500   // In case the reflow doesn't invalidate anything since it just leaves
 501   // a gap where the old frame was, we invalidate it here.  (This is
 502   // reasonably likely to happen when removing a last child in a way
 503   // that doesn't change the size of the parent.)
 504   // This has to sure to invalidate the entire overflow rect; this
 505   // is important in the presence of absolute positioning
 506   aOldFrame->InvalidateFrameForRemoval();
 507
 508   NS_ASSERTION(!aOldFrame->GetPrevContinuation() ||
 509                // exception for nsCSSFrameConstructor::RemoveFloatingFirstLetterFrames
 510                aOldFrame->GetType() == nsGkAtoms::textFrame,
 511                "Must remove first continuation.");
 512   NS_ASSERTION(!(aOldFrame->GetStateBits() & NS_FRAME_OUT_OF_FLOW &&
 513                  GetPlaceholderFrameFor(aOldFrame)),
 514                "Must call RemoveFrame on placeholder for out-of-flows.");
 515   nsContainerFrame* parentFrame = aOldFrame->GetParent();
 516   if (parentFrame->IsAbsoluteContainer() &&
 517       aListID == parentFrame->GetAbsoluteListID()) {
 518     parentFrame->GetAbsoluteContainingBlock()->
 519       RemoveFrame(parentFrame, aListID, aOldFrame);
 520   } else {
 521     parentFrame->RemoveFrame(aListID, aOldFrame);
 522   }
 523
 524   mIsDestroyingFrames = wasDestroyingFrames;
 525 }
 526
 527 //----------------------------------------------------------------------
 528
 529 void
 530 nsFrameManager::NotifyDestroyingFrame(nsIFrame* aFrame)
 531 {
 532   nsIContent* content = aFrame->GetContent();
 533   if (content && content->GetPrimaryFrame() == aFrame) {
 534     ClearAllUndisplayedContentIn(content);
 535     ClearAllDisplayContentsIn(content);
 536   }
 537 }
 538
 539 // Capture state for a given frame.
 540 // Accept a content id here, in some cases we may not have content (scroll position)
 541 void
 542 nsFrameManager::CaptureFrameStateFor(nsIFrame* aFrame,
 543                                      nsILayoutHistoryState* aState)
 544 {
 545   if (!aFrame || !aState) {
 546     NS_WARNING("null frame, or state");
 547     return;
 548   }
 549
 550   // Only capture state for stateful frames
 551   nsIStatefulFrame* statefulFrame = do_QueryFrame(aFrame);
 552   if (!statefulFrame) {
 553     return;
 554   }
 555
 556   // Capture the state, exit early if we get null (nothing to save)
 557   nsAutoPtr<nsPresState> frameState;
 558   nsresult rv = statefulFrame->SaveState(getter_Transfers(frameState));
 559   if (!frameState) {
 560     return;
 561   }
 562
 563   // Generate the hash key to store the state under
 564   // Exit early if we get empty key
 565   nsAutoCString stateKey;
 566   nsIContent* content = aFrame->GetContent();
 567   nsIDocument* doc = content ? content->GetCurrentDoc() : nullptr;
 568   rv = nsContentUtils::GenerateStateKey(content, doc, stateKey);
 569   if(NS_FAILED(rv) || stateKey.IsEmpty()) {
 570     return;
 571   }
 572
 573   // Store the state. aState owns frameState now.
 574   aState->AddState(stateKey, frameState.forget());
 575 }
 576
 577 void
 578 nsFrameManager::CaptureFrameState(nsIFrame* aFrame,
 579                                   nsILayoutHistoryState* aState)
 580 {
 581   NS_PRECONDITION(nullptr != aFrame && nullptr != aState, "null parameters passed in");
 582
 583   CaptureFrameStateFor(aFrame, aState);
 584
 585   // Now capture state recursively for the frame hierarchy rooted at aFrame
 586   nsIFrame::ChildListIterator lists(aFrame);
 587   for (; !lists.IsDone(); lists.Next()) {
 588     nsFrameList::Enumerator childFrames(lists.CurrentList());
 589     for (; !childFrames.AtEnd(); childFrames.Next()) {
 590       nsIFrame* child = childFrames.get();
 591       if (child->GetStateBits() & NS_FRAME_OUT_OF_FLOW) {
 592         // We'll pick it up when we get to its placeholder
 593         continue;
 594       }
 595       // Make sure to walk through placeholders as needed, so that we
 596       // save state for out-of-flows which may not be our descendants
 597       // themselves but whose placeholders are our descendants.
 598       CaptureFrameState(nsPlaceholderFrame::GetRealFrameFor(child), aState);
 599     }
 600   }
 601 }
 602
 603 // Restore state for a given frame.
 604 // Accept a content id here, in some cases we may not have content (scroll position)
 605 void
 606 nsFrameManager::RestoreFrameStateFor(nsIFrame* aFrame,
 607                                      nsILayoutHistoryState* aState)
 608 {
 609   if (!aFrame || !aState) {
 610     NS_WARNING("null frame or state");
 611     return;
 612   }
 613
 614   // Only restore state for stateful frames
 615   nsIStatefulFrame* statefulFrame = do_QueryFrame(aFrame);
 616   if (!statefulFrame) {
 617     return;
 618   }
 619
 620   // Generate the hash key the state was stored under
 621   // Exit early if we get empty key
 622   nsIContent* content = aFrame->GetContent();
 623   // If we don't have content, we can't generate a hash
 624   // key and there's probably no state information for us.
 625   if (!content) {
 626     return;
 627   }
 628
 629   nsAutoCString stateKey;
 630   nsIDocument* doc = content->GetCurrentDoc();
 631   nsresult rv = nsContentUtils::GenerateStateKey(content, doc, stateKey);
 632   if (NS_FAILED(rv) || stateKey.IsEmpty()) {
 633     return;
 634   }
 635
 636   // Get the state from the hash
 637   nsPresState* frameState = aState->GetState(stateKey);
 638   if (!frameState) {
 639     return;
 640   }
 641
 642   // Restore it
 643   rv = statefulFrame->RestoreState(frameState);
 644   if (NS_FAILED(rv)) {
 645     return;
 646   }
 647
 648   // If we restore ok, remove the state from the state table
 649   aState->RemoveState(stateKey);
 650 }
 651
 652 void
 653 nsFrameManager::RestoreFrameState(nsIFrame* aFrame,
 654                                   nsILayoutHistoryState* aState)
 655 {
 656   NS_PRECONDITION(nullptr != aFrame && nullptr != aState, "null parameters passed in");
 657
 658   RestoreFrameStateFor(aFrame, aState);
 659
 660   // Now restore state recursively for the frame hierarchy rooted at aFrame
 661   nsIFrame::ChildListIterator lists(aFrame);
 662   for (; !lists.IsDone(); lists.Next()) {
 663     nsFrameList::Enumerator childFrames(lists.CurrentList());
 664     for (; !childFrames.AtEnd(); childFrames.Next()) {
 665       RestoreFrameState(childFrames.get(), aState);
 666     }
 667   }
 668 }
 669
 670 //----------------------------------------------------------------------
 671
 672 static PLHashNumber
 673 HashKey(void* key)
 674 {
 675   return NS_PTR_TO_INT32(key);
 676 }
 677
 678 static int
 679 CompareKeys(void* key1, void* key2)
 680 {
 681   return key1 == key2;
 682 }
 683
 684 //----------------------------------------------------------------------
 685
 686 nsFrameManagerBase::UndisplayedMap::UndisplayedMap(uint32_t aNumBuckets)
 687 {
 688   MOZ_COUNT_CTOR(nsFrameManagerBase::UndisplayedMap);
 689   mTable = PL_NewHashTable(aNumBuckets, (PLHashFunction)HashKey,
 690                            (PLHashComparator)CompareKeys,
 691                            (PLHashComparator)nullptr,
 692                            nullptr, nullptr);
 693   mLastLookup = nullptr;
 694 }
 695
 696 nsFrameManagerBase::UndisplayedMap::~UndisplayedMap(void)
 697 {
 698   MOZ_COUNT_DTOR(nsFrameManagerBase::UndisplayedMap);
 699   Clear();
 700   PL_HashTableDestroy(mTable);
 701 }
 702
 703 PLHashEntry**
 704 nsFrameManagerBase::UndisplayedMap::GetEntryFor(nsIContent** aParentContent)
 705 {
 706   nsIContent* parentContent = *aParentContent;
 707
 708   if (mLastLookup && (parentContent == (*mLastLookup)->key)) {
 709     return mLastLookup;
 710   }
 711
 712   // In the case of XBL default content, <xbl:children> elements do not get a
 713   // frame causing a mismatch between the content tree and the frame tree.
 714   // |GetEntryFor| is sometimes called with the content tree parent (which may
 715   // be a <xbl:children> element) but the parent in the frame tree would be the
 716   // insertion parent (parent of the <xbl:children> element). Here the children
 717   // elements are normalized to the insertion parent to correct for the mismatch.
 718   if (parentContent && nsContentUtils::IsContentInsertionPoint(parentContent)) {
 719     parentContent = parentContent->GetParent();
 720     // Change the caller's pointer for the parent content to be the insertion parent.
 721     *aParentContent = parentContent;
 722   }
 723
 724   PLHashNumber hashCode = NS_PTR_TO_INT32(parentContent);
 725   PLHashEntry** entry = PL_HashTableRawLookup(mTable, hashCode, parentContent);
 726   if (*entry) {
 727     mLastLookup = entry;
 728   }
 729   return entry;
 730 }
 731
 732 UndisplayedNode*
 733 nsFrameManagerBase::UndisplayedMap::GetFirstNode(nsIContent* aParentContent)
 734 {
 735   PLHashEntry** entry = GetEntryFor(&aParentContent);
 736   if (*entry) {
 737     return (UndisplayedNode*)((*entry)->value);
 738   }
 739   return nullptr;
 740 }
 741
 742 void
 743 nsFrameManagerBase::UndisplayedMap::AppendNodeFor(UndisplayedNode* aNode,
 744                                                   nsIContent* aParentContent)
 745 {
 746   PLHashEntry** entry = GetEntryFor(&aParentContent);
 747   if (*entry) {
 748     UndisplayedNode*  node = (UndisplayedNode*)((*entry)->value);
 749     while (node->mNext) {
 750       if (node->mContent == aNode->mContent) {
 751         // We actually need to check this in optimized builds because
 752         // there are some callers that do this.  See bug 118014, bug
 753         // 136704, etc.
 754         NS_NOTREACHED("node in map twice");
 755         delete aNode;
 756         return;
 757       }
 758       node = node->mNext;
 759     }
 760     node->mNext = aNode;
 761   }
 762   else {
 763     PLHashNumber hashCode = NS_PTR_TO_INT32(aParentContent);
 764     PL_HashTableRawAdd(mTable, entry, hashCode, aParentContent, aNode);
 765     mLastLookup = nullptr; // hashtable may have shifted bucket out from under us
 766   }
 767 }
 768
 769 nsresult
 770 nsFrameManagerBase::UndisplayedMap::AddNodeFor(nsIContent* aParentContent,
 771                                                nsIContent* aChild,
 772                                                nsStyleContext* aStyle)
 773 {
 774   UndisplayedNode*  node = new UndisplayedNode(aChild, aStyle);
 775
 776   AppendNodeFor(node, aParentContent);
 777   return NS_OK;
 778 }
 779
 780 void
 781 nsFrameManagerBase::UndisplayedMap::RemoveNodeFor(nsIContent* aParentContent,
 782                                                   UndisplayedNode* aNode)
 783 {
 784   PLHashEntry** entry = GetEntryFor(&aParentContent);
 785   NS_ASSERTION(*entry, "content not in map");
 786   if (*entry) {
 787     if ((UndisplayedNode*)((*entry)->value) == aNode) {  // first node
 788       if (aNode->mNext) {
 789         (*entry)->value = aNode->mNext;
 790         aNode->mNext = nullptr;
 791       }
 792       else {
 793         PL_HashTableRawRemove(mTable, entry, *entry);
 794         mLastLookup = nullptr; // hashtable may have shifted bucket out from under us
 795       }
 796     }
 797     else {
 798       UndisplayedNode*  node = (UndisplayedNode*)((*entry)->value);
 799       while (node->mNext) {
 800         if (node->mNext == aNode) {
 801           node->mNext = aNode->mNext;
 802           aNode->mNext = nullptr;
 803           break;
 804         }
 805         node = node->mNext;
 806       }
 807     }
 808   }
 809   delete aNode;
 810 }
 811
 812
 813 UndisplayedNode*
 814 nsFrameManagerBase::UndisplayedMap::UnlinkNodesFor(nsIContent* aParentContent)
 815 {
 816   PLHashEntry** entry = GetEntryFor(&aParentContent);
 817   NS_ASSERTION(entry, "content not in map");
 818   if (*entry) {
 819     UndisplayedNode* node = (UndisplayedNode*)((*entry)->value);
 820     NS_ASSERTION(node, "null node for non-null entry in UndisplayedMap");
 821     PL_HashTableRawRemove(mTable, entry, *entry);
 822     mLastLookup = nullptr; // hashtable may have shifted bucket out from under us
 823     return node;
 824   }
 825   return nullptr;
 826 }
 827
 828 void
 829 nsFrameManagerBase::UndisplayedMap::RemoveNodesFor(nsIContent* aParentContent)
 830 {
 831   delete UnlinkNodesFor(aParentContent);
 832 }
 833
 834 static int
 835 RemoveUndisplayedEntry(PLHashEntry* he, int i, void* arg)
 836 {
 837   UndisplayedNode*  node = (UndisplayedNode*)(he->value);
 838   delete node;
 839   // Remove and free this entry and continue enumerating
 840   return HT_ENUMERATE_REMOVE | HT_ENUMERATE_NEXT;
 841 }
 842
 843 void
 844 nsFrameManagerBase::UndisplayedMap::Clear(void)
 845 {
 846   mLastLookup = nullptr;
 847   PL_HashTableEnumerateEntries(mTable, RemoveUndisplayedEntry, 0);
 848 }
 849
 850 uint32_t nsFrameManagerBase::sGlobalGenerationNumber;