Bug 564991. Part 9: Retain layer trees. r=tnikkel,sr=mats
authorRobert O'Callahan <robert@ocallahan.org>
Fri, 16 Jul 2010 09:07:51 +1200
changeset 47736 e284964e5bcf5d1951d67d6a1f9386b9f023d583
parent 47735 213c2dc6c88ac76fbc336ea79dd414742e533797
child 47737 e7aa691d74e4797e86197e1b8379401d249a81c3
push idunknown
push userunknown
push dateunknown
reviewerstnikkel, mats
bugs564991
milestone2.0b2pre
Bug 564991. Part 9: Retain layer trees. r=tnikkel,sr=mats
gfx/layers/Layers.h
layout/base/FrameLayerBuilder.cpp
layout/base/FrameLayerBuilder.h
layout/base/nsDisplayList.cpp
layout/base/nsDisplayList.h
layout/base/nsLayoutUtils.cpp
layout/base/nsLayoutUtils.h
layout/reftests/scrolling/reftest.list
layout/reftests/scrolling/uncovering-1-ref.html
layout/reftests/scrolling/uncovering-1.html
--- a/gfx/layers/Layers.h
+++ b/gfx/layers/Layers.h
@@ -155,26 +155,34 @@ public:
   virtual void BeginTransactionWithTarget(gfxContext* aTarget) = 0;
   /**
    * Function called to draw the contents of each ThebesLayer.
    * aRegionToDraw contains the region that needs to be drawn.
    * This would normally be a subregion of the visible region.
    * The callee must draw all of aRegionToDraw. Drawing outside
    * aRegionToDraw will be clipped out or ignored.
    * The callee must draw all of aRegionToDraw.
+   * This region is relative to 0,0 in the ThebesLayer.
    * 
    * aRegionToInvalidate contains a region whose contents have been
    * changed by the layer manager and which must therefore be invalidated.
-   * For example, this could be non-empty if the layer internally switched
-   * from RGBA to RGB or back ... we might want to repaint it to
+   * For example, this could be non-empty if a retained layer internally
+   * switches from RGBA to RGB or back ... we might want to repaint it to
    * consistently use subpixel-AA or not.
+   * This region is relative to 0,0 in the ThebesLayer.
+   * aRegionToInvalidate may contain areas that are outside
+   * aRegionToDraw; the callee must ensure that these areas are repainted
+   * in the current layer manager transaction or in a later layer
+   * manager transaction.
    * 
    * aContext must not be used after the call has returned.
    * We guarantee that buffered contents in the visible
    * region are valid once drawing is complete.
+   * 
+   * The origin of aContext is 0,0 in the ThebesLayer.
    */
   typedef void (* DrawThebesLayerCallback)(ThebesLayer* aLayer,
                                            gfxContext* aContext,
                                            const nsIntRegion& aRegionToDraw,
                                            const nsIntRegion& aRegionToInvalidate,
                                            void* aCallbackData);
   /**
    * Finish the construction phase of the transaction, perform the
--- a/layout/base/FrameLayerBuilder.cpp
+++ b/layout/base/FrameLayerBuilder.cpp
@@ -35,526 +35,1197 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "FrameLayerBuilder.h"
 
 #include "nsDisplayList.h"
 #include "nsPresContext.h"
 #include "nsLayoutUtils.h"
+#include "Layers.h"
+
+#ifdef DEBUG
+#include <stdio.h>
+#endif
 
 using namespace mozilla::layers;
 
 namespace mozilla {
 
 namespace {
 
 /**
- * This class iterates through a display list tree, descending only into
- * nsDisplayClip items, and returns each display item encountered during
- * such iteration. Along with each item we also return the clip rect
- * accumulated for the item.
+ * This is the userdata we associate with a layer manager.
  */
-class ClippedItemIterator {
+class LayerManagerData {
 public:
-  ClippedItemIterator(const nsDisplayList* aList)
+  LayerManagerData() :
+    mInvalidateAllThebesContent(PR_FALSE),
+    mInvalidateAllLayers(PR_FALSE)
   {
-    DescendIntoList(aList, nsnull, nsnull);
-    AdvanceToItem();
-  }
-  PRBool IsDone()
-  {
-    return mStack.IsEmpty();
+    mFramesWithLayers.Init();
   }
-  void Next()
+
+  /**
+   * Tracks which frames have layers associated with them.
+   */
+  nsTHashtable<nsPtrHashKey<nsIFrame> > mFramesWithLayers;
+  PRPackedBool mInvalidateAllThebesContent;
+  PRPackedBool mInvalidateAllLayers;
+};
+
+static void DestroyRegion(void* aPropertyValue)
+{
+  delete static_cast<nsRegion*>(aPropertyValue);
+}
+
+/**
+ * This property represents a region that should be invalidated in every
+ * ThebesLayer child whose parent ContainerLayer is associated with the
+ * frame. This is an nsRegion*; the coordinates of the region are
+ * relative to the top-left of the border-box of the frame the property
+ * is attached to (which is the frame for the ContainerLayer).
+ * 
+ * We add to this region in InvalidateThebesLayerContents. The region
+ * is propagated to ContainerState in BuildContainerLayerFor, and then
+ * the region(s) are actually invalidated in CreateOrRecycleThebesLayer.
+ */
+NS_DECLARE_FRAME_PROPERTY(ThebesLayerInvalidRegionProperty, DestroyRegion)
+
+/**
+ * This is a helper object used to build up the layer children for
+ * a ContainerLayer.
+ */
+class ContainerState {
+public:
+  ContainerState(nsDisplayListBuilder* aBuilder,
+                 LayerManager* aManager,
+                 nsIFrame* aContainerFrame,
+                 ContainerLayer* aContainerLayer) :
+    mBuilder(aBuilder), mManager(aManager),
+    mContainerFrame(aContainerFrame), mContainerLayer(aContainerLayer),
+    mNextFreeRecycledThebesLayer(0),
+    mInvalidateAllThebesContent(PR_FALSE)
   {
-    State* top = StackTop();
-    top->mItem = top->mItem->GetAbove();
-    AdvanceToItem();
-  }
-  // Returns null if there is no clipping affecting the item. The
-  // clip rect is in device pixels
-  const gfxRect* GetEffectiveClipRect()
-  {
-    State* top = StackTop();
-    return top->mHasClipRect ? &top->mEffectiveClipRect : nsnull;
-  }
-  nsDisplayItem* Item()
-  {
-    return StackTop()->mItem;
+    CollectOldThebesLayers();
   }
 
-private:
-  // We maintain a stack of state objects. Each State object represents
-  // where we're up to in the iteration of a list.
-  struct State {
-    // The current item we're at in the list
-    nsDisplayItem* mItem;
-    // The effective clip rect applying to all the items in this list
-    gfxRect mEffectiveClipRect;
-    PRPackedBool mHasClipRect;
+  void SetInvalidThebesContent(const nsIntRegion& aRegion)
+  {
+    mInvalidThebesContent = aRegion;
+  }
+  void SetInvalidateAllThebesContent()
+  {
+    mInvalidateAllThebesContent = PR_TRUE;
+  }
+  /**
+   * This is the method that actually walks a display list and builds
+   * the child layers. We invoke it recursively to process clipped sublists.
+   * @param aClipRect the clip rect to apply to the list items, or null
+   * if no clipping is required
+   */
+  void ProcessDisplayItems(const nsDisplayList& aList,
+                           const nsRect* aClipRect);
+  /**
+   * This finalizes all the open ThebesLayers by popping every element off
+   * mThebesLayerDataStack, then sets the children of the container layer
+   * to be all the layers in mNewChildLayers in that order and removes any
+   * layers as children of the container that aren't in mNewChildLayers.
+   */
+  void Finish();
+
+protected:
+  /**
+   * We keep a stack of these to represent the ThebesLayers that are
+   * currently available to have display items added to.
+   * We use a stack here because as much as possible we want to
+   * assign display items to existing ThebesLayers, and to the lowest
+   * ThebesLayer in z-order. This reduces the number of layers and
+   * makes it more likely a display item will be rendered to an opaque
+   * layer, giving us the best chance of getting subpixel AA.
+   */
+  class ThebesLayerData {
+  public:
+    ThebesLayerData() : mActiveScrolledRoot(nsnull), mLayer(nsnull) {}
+    /**
+     * Record that an item has been added to the ThebesLayer, so we
+     * need to update our regions.
+     */
+    void Accumulate(const nsIntRect& aVisibleRect, PRBool aIsOpaque);
+    nsIFrame* GetActiveScrolledRoot() { return mActiveScrolledRoot; }
+
+    /**
+     * The region of visible content in the layer, relative to the
+     * container layer (which is at the snapped top-left of the display
+     * list reference frame).
+     */
+    nsIntRegion  mVisibleRegion;
+    /**
+     * The region of visible content above the layer and below the
+     * next ThebesLayerData currently in the stack, if any. Note that not
+     * all ThebesLayers for the container are in the ThebesLayerData stack.
+     * Same coordinate system as mVisibleRegion.
+     */
+    nsIntRegion  mVisibleAboveRegion;
+    /**
+     * The region of visible content in the layer that is opaque.
+     * Same coordinate system as mVisibleRegion.
+     */
+    nsIntRegion  mOpaqueRegion;
+    /**
+     * The "active scrolled root" for all content in the layer. Must
+     * be non-null; all content in a ThebesLayer must have the same
+     * active scrolled root.
+     */
+    nsIFrame*    mActiveScrolledRoot;
+    ThebesLayer* mLayer;
   };
 
-  State* StackTop()
-  {
-    return &mStack[mStack.Length() - 1];
-  }
-  void DescendIntoList(const nsDisplayList* aList,
-                       nsPresContext* aPresContext,
-                       const nsRect* aClipRect)
+  /**
+   * Grab the next recyclable ThebesLayer, or create one if there are no
+   * more recyclable ThebesLayers. Does any necessary invalidation of
+   * a recycled ThebesLayer, and sets up the transform on the ThebesLayer
+   * to account for scrolling. Adds the layer to mNewChildLayers.
+   */
+  already_AddRefed<ThebesLayer> CreateOrRecycleThebesLayer(nsIFrame* aActiveScrolledRoot);
+  /**
+   * Grabs all ThebesLayers from the ContainerLayer and makes them
+   * available for recycling.
+   */
+  void CollectOldThebesLayers();
+  /**
+   * Indicate that we are done adding items to the ThebesLayer at the top of
+   * mThebesLayerDataStack. Set the final visible region and opaque-content
+   * flag, and pop it off the stack.
+   */
+  void PopThebesLayerData();
+  /**
+   * Find the ThebesLayer to which we should assign the next display item.
+   * Returns the layer, and also updates the ThebesLayerData. Will
+   * push a new ThebesLayerData onto the stack if necessary. If we choose
+   * a ThebesLayer that's already on the ThebesLayerData stack,
+   * later elements on the stack will be popped off.
+   * @param aVisibleRect the area of the next display item that's visible
+   * @param aActiveScrolledRoot the active scrolled root for the next
+   * display item
+   * @param aIsOpaque whether the bounds of the next display item are
+   * opaque
+   */
+  already_AddRefed<ThebesLayer> FindThebesLayerFor(const nsIntRect& aVisibleRect,
+                                                   nsIFrame* aActiveScrolledRoot,
+                                                   PRBool aIsOpaque);
+  ThebesLayerData* GetTopThebesLayerData()
   {
-    State* state = mStack.AppendElement();
-    if (!state)
-      return;
-    if (mStack.Length() >= 2) {
-      *state = mStack[mStack.Length() - 2];
-    } else {
-      state->mHasClipRect = PR_FALSE;
-    }
-    state->mItem = aList->GetBottom();
-    if (aClipRect) {
-      gfxRect r(aClipRect->x, aClipRect->y, aClipRect->width, aClipRect->height);
-      r.ScaleInverse(aPresContext->AppUnitsPerDevPixel());
-      if (state->mHasClipRect) {
-        state->mEffectiveClipRect = state->mEffectiveClipRect.Intersect(r);
-      } else {
-        state->mEffectiveClipRect = r;
-        state->mHasClipRect = PR_TRUE;
-      }
-    }
+    return mThebesLayerDataStack.IsEmpty() ? nsnull
+        : mThebesLayerDataStack[mThebesLayerDataStack.Length() - 1].get();
   }
-  // Advances to an item that the iterator should return.
-  void AdvanceToItem()
-  {
-    while (!mStack.IsEmpty()) {
-      State* top = StackTop();
-      if (!top->mItem) {
-        mStack.SetLength(mStack.Length() - 1);
-        if (!mStack.IsEmpty()) {
-          top = StackTop();
-          top->mItem = top->mItem->GetAbove();
-        }
-        continue;
-      }
-      if (top->mItem->GetType() != nsDisplayItem::TYPE_CLIP)
-        return;
-      nsDisplayClip* clipItem = static_cast<nsDisplayClip*>(top->mItem);
-      nsRect clip = clipItem->GetClipRect();
-      DescendIntoList(clipItem->GetList(),
-                      clipItem->GetClippingFrame()->PresContext(),
-                      &clip);
+
+  nsDisplayListBuilder*            mBuilder;
+  LayerManager*                    mManager;
+  nsIFrame*                        mContainerFrame;
+  ContainerLayer*                  mContainerLayer;
+  /**
+   * The region of ThebesLayers that should be invalidated every time
+   * we recycle one.
+   */
+  nsIntRegion                      mInvalidThebesContent;
+  nsAutoTArray<nsAutoPtr<ThebesLayerData>,1>  mThebesLayerDataStack;
+  /**
+   * We collect the list of children in here. During ProcessDisplayItems,
+   * the layers in this array either have mContainerLayer as their parent,
+   * or no parent.
+   */
+  nsAutoTArray<nsRefPtr<Layer>,1>  mNewChildLayers;
+  nsTArray<nsRefPtr<ThebesLayer> > mRecycledThebesLayers;
+  PRUint32                         mNextFreeRecycledThebesLayer;
+  PRPackedBool                     mInvalidateAllThebesContent;
+};
+
+/**
+ * The address of gThebesDisplayItemLayerUserData is used as the user
+ * data pointer for ThebesLayers created by FrameLayerBuilder.
+ * It identifies ThebesLayers used to draw non-layer content, which are
+ * therefore eligible for recycling. We want display items to be able to
+ * create their own dedicated ThebesLayers in BuildLayer, if necessary,
+ * and we wouldn't want to accidentally recycle those.
+ */
+static PRUint8 gThebesDisplayItemLayerUserData;
+
+} // anonymous namespace
+
+PRBool
+FrameLayerBuilder::DisplayItemDataEntry::HasContainerLayer()
+{
+  for (PRUint32 i = 0; i < mData.Length(); ++i) {
+    if (mData[i].mLayer->GetType() == Layer::TYPE_CONTAINER)
+      return PR_TRUE;
+  }
+  return PR_FALSE;
+}
+
+/* static */ void
+FrameLayerBuilder::InternalDestroyDisplayItemData(nsIFrame* aFrame,
+                                                  void* aPropertyValue,
+                                                  PRBool aRemoveFromFramesWithLayers)
+{
+  nsRefPtr<LayerManager> managerRef;
+  nsTArray<DisplayItemData>* array =
+    reinterpret_cast<nsTArray<DisplayItemData>*>(&aPropertyValue);
+  NS_ASSERTION(!array->IsEmpty(), "Empty arrays should not be stored");
+
+  if (aRemoveFromFramesWithLayers) {
+    LayerManager* manager = array->ElementAt(0).mLayer->Manager();
+    LayerManagerData* data = static_cast<LayerManagerData*>
+      (manager->GetUserData());
+    NS_ASSERTION(data, "Frame with layer should have been recorded");
+    data->mFramesWithLayers.RemoveEntry(aFrame);
+    if (data->mFramesWithLayers.Count() == 0) {
+      delete data;
+      manager->SetUserData(nsnull);
+      // Consume the reference we added when we set the user data
+      // in DidEndTransaction. But don't actually release until we've
+      // released all the layers in the DisplayItemData array below!
+      managerRef = manager;
+      NS_RELEASE(manager);
     }
   }
 
-  nsAutoTArray<State,10> mStack;
-};
+  array->~nsTArray<DisplayItemData>();
+}
+
+/* static */ void
+FrameLayerBuilder::DestroyDisplayItemData(nsIFrame* aFrame,
+                                          void* aPropertyValue)
+{
+  InternalDestroyDisplayItemData(aFrame, aPropertyValue, PR_TRUE);
+}
 
-/**
- * This class represents a sublist of consecutive items in an nsDisplayList.
- * The first item in the sublist is mStartItem and the last item
- * is the item before mEndItem.
- * 
- * These sublists are themselves organized into a linked list of all
- * the ItemGroups associated with a given layer, via mNextItemsForLayer.
- * This list will have more than one element if the display items in a layer
- * come from different nsDisplayLists, or if they come from the same
- * nsDisplayList but they aren't consecutive in that list.
- * 
- * These objects are allocated from the nsDisplayListBuilder arena.
- */
-struct ItemGroup {
-  // If null, then the item group is empty.
-  nsDisplayItem* mStartItem;
-  nsDisplayItem* mEndItem;
-  ItemGroup* mNextItemsForLayer;
-  // The clipping (if any) that needs to be applied to all these items.
-  gfxRect mClipRect;
-  PRPackedBool mHasClipRect;
-
-  ItemGroup() : mStartItem(nsnull), mEndItem(nsnull),
-    mNextItemsForLayer(nsnull), mHasClipRect(PR_FALSE) {}
-
-  void* operator new(size_t aSize,
-                     nsDisplayListBuilder* aBuilder) CPP_THROW_NEW {
-    return aBuilder->Allocate(aSize);
+void
+FrameLayerBuilder::BeginUpdatingRetainedLayers(LayerManager* aManager)
+{
+  mRetainingManager = aManager;
+  LayerManagerData* data = static_cast<LayerManagerData*>
+    (aManager->GetUserData());
+  if (data) {
+    mInvalidateAllThebesContent = data->mInvalidateAllThebesContent;
+    mInvalidateAllLayers = data->mInvalidateAllLayers;
   }
-};
+}
 
 /**
- * This class represents a layer and the display item(s) it
- * will render. The items are stored in a linked list of ItemGroups.
+ * A helper function to remove the mThebesLayerItems entries for every
+ * layer in aLayer's subtree.
  */
-struct LayerItems {
-  nsRefPtr<Layer> mLayer;
-  // equal to mLayer, or null if mLayer is not a ThebesLayer
-  ThebesLayer* mThebesLayer;
-  ItemGroup* mItems;
-  // The bounds of the visible region for this layer, in device pixels
-  nsIntRect mVisibleRect;
+void
+FrameLayerBuilder::RemoveThebesItemsForLayerSubtree(Layer* aLayer)
+{
+  ThebesLayer* thebes = aLayer->AsThebesLayer();
+  if (thebes) {
+    mThebesLayerItems.RemoveEntry(thebes);
+    return;
+  }
 
-  LayerItems(ItemGroup* aItems) :
-    mThebesLayer(nsnull), mItems(aItems)
-  {
+  for (Layer* child = aLayer->GetFirstChild(); child;
+       child = child->GetNextSibling()) {
+    RemoveThebesItemsForLayerSubtree(child);
+  }
+}
+
+void
+FrameLayerBuilder::DidEndTransaction(LayerManager* aManager)
+{
+  if (aManager != mRetainingManager) {
+    Layer* root = aManager->GetRoot();
+    if (root) {
+      RemoveThebesItemsForLayerSubtree(root);
+    }
+    return;
   }
 
-  void* operator new(size_t aSize,
-                     nsDisplayListBuilder* aBuilder) CPP_THROW_NEW {
-    return aBuilder->Allocate(aSize);
+  // We need to save the data we'll need to support retaining.
+  LayerManagerData* data = static_cast<LayerManagerData*>
+    (mRetainingManager->GetUserData());
+  if (data) {
+    // Update all the frames that used to have layers.
+    data->mFramesWithLayers.EnumerateEntries(UpdateDisplayItemDataForFrame, this);
+  } else {
+    data = new LayerManagerData();
+    mRetainingManager->SetUserData(data);
+    // Addref mRetainingManager. We'll release it when 'data' is
+    // removed.
+    NS_ADDREF(mRetainingManager);
   }
-};
+  // Now go through all the frames that didn't have any retained
+  // display items before, and record those retained display items.
+  // This also empties mNewDisplayItemData.
+  mNewDisplayItemData.EnumerateEntries(StoreNewDisplayItemData, data);
+  data->mInvalidateAllThebesContent = PR_FALSE;
+  data->mInvalidateAllLayers = PR_FALSE;
+
+  NS_ASSERTION(data->mFramesWithLayers.Count() > 0,
+               "Some frame must have a layer!");
+}
 
-/**
- * Given a (possibly clipped) display item in aItem, try to append it to
- * the items in aGroup. If aItem is the next item in the sublist in
- * aGroup, and the clipping matches, we can just update aGroup in-place,
- * otherwise we'll allocate a new ItemGroup, add it to the linked list,
- * and put aItem in the new ItemGroup. We return the ItemGroup into which
- * aItem was inserted.
- */
-static ItemGroup*
-AddToItemGroup(nsDisplayListBuilder* aBuilder,
-               ItemGroup* aGroup, nsDisplayItem* aItem,
-               const gfxRect* aClipRect)
+/* static */ PLDHashOperator
+FrameLayerBuilder::UpdateDisplayItemDataForFrame(nsPtrHashKey<nsIFrame>* aEntry,
+                                                 void* aUserArg)
 {
-  NS_ASSERTION(!aGroup->mNextItemsForLayer,
-               "aGroup must be the last group in the chain");
+  FrameLayerBuilder* builder = static_cast<FrameLayerBuilder*>(aUserArg);
+  nsIFrame* f = aEntry->GetKey();
+  FrameProperties props = f->Properties();
+  DisplayItemDataEntry* newDisplayItems =
+    builder->mNewDisplayItemData.GetEntry(f);
+  if (!newDisplayItems) {
+    // This frame was visible, but isn't anymore.
+    PRBool found;
+    void* prop = props.Remove(DisplayItemDataProperty(), &found);
+    NS_ASSERTION(found, "How can the frame property be missing?");
+    // Pass PR_FALSE to not remove from mFramesWithLayers, we'll remove it
+    // by returning PL_DHASH_REMOVE below.
+    // Note that DestroyDisplayItemData would delete the user data
+    // for the retained layer manager if it removed the last entry from
+    // mFramesWithLayers, but we won't. That's OK because our caller
+    // is DidEndTransaction, which would recreate the user data
+    // anyway.
+    InternalDestroyDisplayItemData(f, prop, PR_FALSE);
+    props.Delete(ThebesLayerInvalidRegionProperty());
+    f->RemoveStateBits(NS_FRAME_HAS_CONTAINER_LAYER);
+    return PL_DHASH_REMOVE;
+  }
 
-  if (!aGroup->mStartItem) {
-    aGroup->mStartItem = aItem;
-    aGroup->mEndItem = aItem->GetAbove();
-    aGroup->mHasClipRect = aClipRect != nsnull;
-    if (aClipRect) {
-      aGroup->mClipRect = *aClipRect;
-    }
-    return aGroup;
+  if (!newDisplayItems->HasContainerLayer()) {
+    props.Delete(ThebesLayerInvalidRegionProperty());
+    f->RemoveStateBits(NS_FRAME_HAS_CONTAINER_LAYER);
+  } else {
+    NS_ASSERTION(f->GetStateBits() & NS_FRAME_HAS_CONTAINER_LAYER,
+                 "This bit should have been set by BuildContainerLayerFor");
   }
 
-  if (aGroup->mEndItem == aItem &&
-      (aGroup->mHasClipRect
-       ? (aClipRect && aGroup->mClipRect == *aClipRect)
-       : !aClipRect))  {
-    aGroup->mEndItem = aItem->GetAbove();
-    return aGroup;
+  // Reset the invalid region now so we can start collecting new dirty
+  // areas.
+  nsRegion* invalidRegion = static_cast<nsRegion*>
+    (props.Get(ThebesLayerInvalidRegionProperty()));
+  if (invalidRegion) {
+    invalidRegion->SetEmpty();
   }
 
-  ItemGroup* itemGroup = new (aBuilder) ItemGroup();
-  if (!itemGroup)
-    return aGroup;
-  aGroup->mNextItemsForLayer = itemGroup;
-  return AddToItemGroup(aBuilder, itemGroup, aItem, aClipRect);
+  // We need to remove and re-add the DisplayItemDataProperty in
+  // case the nsTArray changes the value of its mHdr.
+  void* propValue = props.Remove(DisplayItemDataProperty());
+  NS_ASSERTION(propValue, "mFramesWithLayers out of sync");
+  PR_STATIC_ASSERT(sizeof(nsTArray<DisplayItemData>) == sizeof(void*));
+  nsTArray<DisplayItemData>* array =
+    reinterpret_cast<nsTArray<DisplayItemData>*>(&propValue);
+  // Steal the list of display item layers
+  array->SwapElements(newDisplayItems->mData);
+  props.Set(DisplayItemDataProperty(), propValue);
+  // Don't need to process this frame again
+  builder->mNewDisplayItemData.RawRemoveEntry(newDisplayItems);
+  return PL_DHASH_NEXT;
+}
+
+/* static */ PLDHashOperator
+FrameLayerBuilder::StoreNewDisplayItemData(DisplayItemDataEntry* aEntry,
+                                           void* aUserArg)
+{
+  LayerManagerData* data = static_cast<LayerManagerData*>(aUserArg);
+  nsIFrame* f = aEntry->GetKey();
+  // Remember that this frame has display items in retained layers
+  NS_ASSERTION(!data->mFramesWithLayers.GetEntry(f),
+               "We shouldn't get here if we're already in mFramesWithLayers");
+  data->mFramesWithLayers.PutEntry(f);
+  NS_ASSERTION(!f->Properties().Get(DisplayItemDataProperty()),
+               "mFramesWithLayers out of sync");
+
+  void* propValue;
+  nsTArray<DisplayItemData>* array =
+    new (&propValue) nsTArray<DisplayItemData>();
+  // Steal the list of display item layers
+  array->SwapElements(aEntry->mData);
+  // Save it
+  f->Properties().Set(DisplayItemDataProperty(), propValue);
+
+  return PL_DHASH_REMOVE;
+}
+
+Layer*
+FrameLayerBuilder::GetOldLayerFor(nsIFrame* aFrame, PRUint32 aDisplayItemKey)
+{
+  // If we need to build a new layer tree, then just refuse to recycle
+  // anything.
+  if (!mRetainingManager || mInvalidateAllLayers)
+    return nsnull;
+
+  void* propValue = aFrame->Properties().Get(DisplayItemDataProperty());
+  if (!propValue)
+    return nsnull;
+
+  nsTArray<DisplayItemData>* array =
+    (reinterpret_cast<nsTArray<DisplayItemData>*>(&propValue));
+  for (PRUint32 i = 0; i < array->Length(); ++i) {
+    if (array->ElementAt(i).mDisplayItemKey == aDisplayItemKey) {
+      Layer* layer = array->ElementAt(i).mLayer;
+      if (layer->Manager() == mRetainingManager)
+        return layer;
+    }
+  }
+  return nsnull;
 }
 
 /**
- * Create an empty Thebes layer, with an empty ItemGroup associated with
- * it, and append it to aLayers.
+ * Invalidate aRegion in aLayer. aLayer is in the coordinate system
+ * *after* aLayer's transform has been applied, so we need to
+ * apply the inverse of that transform before calling InvalidateRegion.
+ * Currently we assume that the transform is just an integer translation,
+ * since that's all we need for scrolling.
  */
-static ItemGroup*
-CreateEmptyThebesLayer(nsDisplayListBuilder* aBuilder,
-                       LayerManager* aManager,
-                       nsTArray<LayerItems*>* aLayers)
+static void
+InvalidatePostTransformRegion(ThebesLayer* aLayer, const nsIntRegion& aRegion)
 {
-  ItemGroup* itemGroup = new (aBuilder) ItemGroup();
-  if (!itemGroup)
-    return nsnull;
-  nsRefPtr<ThebesLayer> thebesLayer = aManager->CreateThebesLayer();
-  if (!thebesLayer)
-    return nsnull;
-  LayerItems* layerItems = new (aBuilder) LayerItems(itemGroup);
-  aLayers->AppendElement(layerItems);
-  thebesLayer->SetUserData(layerItems);
-  layerItems->mThebesLayer = thebesLayer;
-  layerItems->mLayer = thebesLayer.forget();
-  return itemGroup;
+  gfxMatrix transform;
+  if (aLayer->GetTransform().Is2D(&transform)) {
+    NS_ASSERTION(!transform.HasNonIntegerTranslation(),
+                 "Matrix not just an integer translation?");
+    // Convert the region from the coordinates of the container layer
+    // (relative to the snapped top-left of the display list reference frame)
+    // to the ThebesLayer's own coordinates
+    nsIntRegion rgn = aRegion;
+    rgn.MoveBy(-nsIntPoint(PRInt32(transform.x0), PRInt32(transform.y0)));
+    aLayer->InvalidateRegion(rgn);
+  } else {
+    NS_ERROR("Only 2D transformations currently supported");
+  }
 }
 
-static PRBool
-IsAllUniform(nsDisplayListBuilder* aBuilder, ItemGroup* aGroup,
-             nscolor* aColor)
+already_AddRefed<ThebesLayer>
+ContainerState::CreateOrRecycleThebesLayer(nsIFrame* aActiveScrolledRoot)
 {
-  nsRect visibleRect = aGroup->mStartItem->GetVisibleRect();
-  nscolor finalColor = NS_RGBA(0,0,0,0);
-  for (ItemGroup* group = aGroup; group;
-       group = group->mNextItemsForLayer) {
-    for (nsDisplayItem* item = group->mStartItem; item != group->mEndItem;
-         item = item->GetAbove()) {
-      nscolor color;
-      if (visibleRect != item->GetVisibleRect())
-        return PR_FALSE;
-      if (!item->IsUniform(aBuilder, &color))
-        return PR_FALSE;
-      finalColor = NS_ComposeColors(finalColor, color);
+  // We need a new thebes layer
+  nsRefPtr<ThebesLayer> layer;
+  if (mNextFreeRecycledThebesLayer <
+      mRecycledThebesLayers.Length()) {
+    // Recycle a layer
+    layer = mRecycledThebesLayers[mNextFreeRecycledThebesLayer];
+    ++mNextFreeRecycledThebesLayer;
+
+    // This gets called on recycled ThebesLayers that are going to be in the
+    // final layer tree, so it's a convenient time to invalidate the
+    // content that changed where we don't know what ThebesLayer it belonged
+    // to, or if we need to invalidate the entire layer, we can do that.
+    // This needs to be done before we update the ThebesLayer to its new
+    // transform. See nsGfxScrollFrame::InvalidateInternal, where
+    // we ensure that mInvalidThebesContent is updated according to the
+    // scroll position as of the most recent paint.
+    if (mInvalidateAllThebesContent) {
+      nsIntRect invalidate = layer->GetValidRegion().GetBounds();
+      layer->InvalidateRegion(invalidate);
+    } else {
+      InvalidatePostTransformRegion(layer, mInvalidThebesContent);
     }
+    // We do not need to Invalidate these areas in the widget because we
+    // assume the caller of InvalidateThebesLayerContents or
+    // InvalidateAllThebesLayerContents has ensured
+    // the area is invalidated in the widget.
+  } else {
+    // Create a new thebes layer
+    layer = mManager->CreateThebesLayer();
+    if (!layer)
+      return nsnull;
+    // Mark this layer as being used for Thebes-painting display items
+    layer->SetUserData(&gThebesDisplayItemLayerUserData);
   }
-  *aColor = finalColor;
-  return PR_TRUE;
+
+  // Set up transform so that 0,0 in the Thebes layer corresponds to the
+  // (pixel-snapped) top-left of the aActiveScrolledRoot.
+  nsPoint offset = mBuilder->ToReferenceFrame(aActiveScrolledRoot);
+  nsIntPoint pixOffset = offset.ToNearestPixels(
+      aActiveScrolledRoot->PresContext()->AppUnitsPerDevPixel());
+  gfxMatrix matrix;
+  matrix.Translate(gfxPoint(pixOffset.x, pixOffset.y));
+  layer->SetTransform(gfx3DMatrix::From2D(matrix));
+
+  NS_ASSERTION(!mNewChildLayers.Contains(layer), "Layer already in list???");
+  mNewChildLayers.AppendElement(layer);
+  return layer.forget();
+}
+
+/**
+ * Returns the appunits per dev pixel for the item's frame. The item must
+ * have a frame because only nsDisplayClip items don't have a frame,
+ * and those items are flattened away by ProcessDisplayItems.
+ */
+static PRUint32
+AppUnitsPerDevPixel(nsDisplayItem* aItem)
+{
+  return aItem->GetUnderlyingFrame()->PresContext()->AppUnitsPerDevPixel();
 }
 
 /**
- * This is the heart of layout's integration with layers. We
- * use a ClippedItemIterator to iterate through descendant display
- * items. Each item either has its own layer or is assigned to a
- * ThebesLayer. We create ThebesLayers as necessary, although we try
- * to put items in the bottom-most ThebesLayer because that is most
- * likely to be able to render with an opaque background, which will often
- * be required for subpixel text antialiasing to work.
+ * Set the visible rect of aLayer. aLayer is in the coordinate system
+ * *after* aLayer's transform has been applied, so we need to
+ * apply the inverse of that transform before calling SetVisibleRegion.
  */
-static void BuildLayers(nsDisplayListBuilder* aBuilder,
-                        const nsDisplayList& aList,
-                        LayerManager* aManager,
-                        nsTArray<LayerItems*>* aLayers)
+static void
+SetVisibleRectForLayer(Layer* aLayer, const nsIntRect& aRect)
 {
-  NS_ASSERTION(aLayers->IsEmpty(), "aLayers must be initially empty");
+  gfxMatrix transform;
+  if (aLayer->GetTransform().Is2D(&transform)) {
+    // if 'transform' is not invertible, then nothing will be displayed
+    // for the layer, so it doesn't really matter what we do here
+    transform.Invert();
+    gfxRect layerVisible = transform.TransformBounds(
+        gfxRect(aRect.x, aRect.y, aRect.width, aRect.height));
+    layerVisible.RoundOut();
+    nsIntRect visibleRect;
+    if (NS_FAILED(nsLayoutUtils::GfxRectToIntRect(layerVisible, &visibleRect))) {
+      NS_ERROR("Visible rect transformed out of bounds");
+    }
+    aLayer->SetVisibleRegion(visibleRect);
+  } else {
+    NS_ERROR("Only 2D transformations currently supported");
+  }
+}
 
-  // Create "bottom" Thebes layer. We'll try to put as much content
-  // as possible in this layer because if the container is filled with
-  // opaque content, this bottommost layer can also be treated as opaque,
-  // which means content in this layer can have subpixel AA.
-  // firstThebesLayerItems always points to the last ItemGroup for the
-  // first Thebes layer.
-  ItemGroup* firstThebesLayerItems =
-    CreateEmptyThebesLayer(aBuilder, aManager, aLayers);
-  if (!firstThebesLayerItems)
-    return;
-  // lastThebesLayerItems always points to the last ItemGroup for the
-  // topmost layer, if it's a ThebesLayer. If the top layer is not a
-  // Thebes layer, this is null.
-  ItemGroup* lastThebesLayerItems = firstThebesLayerItems;
-  // This region contains the bounds of all the content that is above
-  // the first Thebes layer.
-  nsRegion areaAboveFirstThebesLayer;
+void
+ContainerState::PopThebesLayerData()
+{
+  NS_ASSERTION(!mThebesLayerDataStack.IsEmpty(), "Can't pop");
+
+  PRInt32 lastIndex = mThebesLayerDataStack.Length() - 1;
+  ThebesLayerData* data = mThebesLayerDataStack[lastIndex];
+
+  if (lastIndex > 0) {
+    // Since we're going to pop off the last ThebesLayerData, the
+    // mVisibleAboveRegion of the second-to-last item will need to include
+    // the regions of the last item.
+    ThebesLayerData* nextData = mThebesLayerDataStack[lastIndex - 1];
+    nextData->mVisibleAboveRegion.Or(nextData->mVisibleAboveRegion,
+                                     data->mVisibleAboveRegion);
+    nextData->mVisibleAboveRegion.Or(nextData->mVisibleAboveRegion,
+                                     data->mVisibleRegion);
+  }
 
-  for (ClippedItemIterator iter(&aList); !iter.IsDone(); iter.Next()) {
-    nsDisplayItem* item = iter.Item();
-    const gfxRect* clipRect = iter.GetEffectiveClipRect();
-    // Ask the item if it manages its own layer
-    nsRefPtr<Layer> layer = item->BuildLayer(aBuilder, aManager);
-    nsRect bounds = item->GetBounds(aBuilder);
-    // We set layerItems to point to the LayerItems object where the
-    // item ends up.
-    LayerItems* layerItems = nsnull;
-    if (layer) {
-      // item has a dedicated layer. Add it to the list, with an ItemGroup
-      // covering this item only.
-      ItemGroup* itemGroup = new (aBuilder) ItemGroup();
-      if (itemGroup) {
-        AddToItemGroup(aBuilder, itemGroup, item, clipRect);
-        layerItems = new (aBuilder) LayerItems(itemGroup);
-        aLayers->AppendElement(layerItems);
-        if (layerItems) {
-          if (itemGroup->mHasClipRect) {
-            gfxRect r = itemGroup->mClipRect;
-            r.Round();
-            nsIntRect intRect(r.X(), r.Y(), r.Width(), r.Height());
-            layer->IntersectClipRect(intRect);
-          }
-          layerItems->mLayer = layer.forget();
-        }
-      }
-      // This item is above the first Thebes layer.
-      areaAboveFirstThebesLayer.Or(areaAboveFirstThebesLayer, bounds);
-      lastThebesLayerItems = nsnull;
-    } else {
-      // No dedicated layer. Add it to a Thebes layer. First try to add
-      // it to the first Thebes layer, which we can do if there's no
-      // content between the first Thebes layer and our display item that
-      // overlaps our display item.
-      if (!areaAboveFirstThebesLayer.Intersects(bounds)) {
-        firstThebesLayerItems =
-          AddToItemGroup(aBuilder, firstThebesLayerItems, item, clipRect);
-        layerItems = aLayers->ElementAt(0);
-      } else if (lastThebesLayerItems) {
-        // Try to add to the last Thebes layer
-        lastThebesLayerItems =
-          AddToItemGroup(aBuilder, lastThebesLayerItems, item, clipRect);
-        // This item is above the first Thebes layer.
-        areaAboveFirstThebesLayer.Or(areaAboveFirstThebesLayer, bounds);
-        layerItems = aLayers->ElementAt(aLayers->Length() - 1);
-      } else {
-        // Create a new Thebes layer
-        ItemGroup* itemGroup =
-          CreateEmptyThebesLayer(aBuilder, aManager, aLayers);
-        if (itemGroup) {
-          lastThebesLayerItems =
-            AddToItemGroup(aBuilder, itemGroup, item, clipRect);
-          NS_ASSERTION(lastThebesLayerItems == itemGroup,
-                       "AddToItemGroup shouldn't create a new group if the "
-                       "initial group is empty");
-          // This item is above the first Thebes layer.
-          areaAboveFirstThebesLayer.Or(areaAboveFirstThebesLayer, bounds);
-          layerItems = aLayers->ElementAt(aLayers->Length() - 1);
-        }
+  gfxMatrix transform;
+  if (data->mLayer->GetTransform().Is2D(&transform)) {
+    NS_ASSERTION(!transform.HasNonIntegerTranslation(),
+                 "Matrix not just an integer translation?");
+    // Convert from relative to the container to relative to the
+    // ThebesLayer itself.
+    nsIntRegion rgn = data->mVisibleRegion;
+    rgn.MoveBy(-nsIntPoint(PRInt32(transform.x0), PRInt32(transform.y0)));
+    data->mLayer->SetVisibleRegion(rgn);
+  } else {
+    NS_ERROR("Only 2D transformations currently supported");
+  }
+
+  nsIntRegion transparentRegion;
+  transparentRegion.Sub(data->mVisibleRegion, data->mOpaqueRegion);
+  data->mLayer->SetIsOpaqueContent(transparentRegion.IsEmpty());
+
+  mThebesLayerDataStack.RemoveElementAt(lastIndex);
+}
+
+void
+ContainerState::ThebesLayerData::Accumulate(const nsIntRect& aRect,
+                                            PRBool aIsOpaque)
+{
+  mVisibleRegion.Or(mVisibleRegion, aRect);
+  mVisibleRegion.SimplifyOutward(4);
+  if (aIsOpaque) {
+    mOpaqueRegion.Or(mOpaqueRegion, aRect);
+    mOpaqueRegion.SimplifyInward(4);
+  }
+}
+
+already_AddRefed<ThebesLayer>
+ContainerState::FindThebesLayerFor(const nsIntRect& aVisibleRect,
+                                   nsIFrame* aActiveScrolledRoot,
+                                   PRBool aIsOpaque)
+{
+  PRInt32 i;
+  PRInt32 lowestUsableLayerWithScrolledRoot = -1;
+  PRInt32 topmostLayerWithScrolledRoot = -1;
+  for (i = mThebesLayerDataStack.Length() - 1; i >= 0; --i) {
+    ThebesLayerData* data = mThebesLayerDataStack[i];
+    if (data->mVisibleAboveRegion.Intersects(aVisibleRect)) {
+      ++i;
+      break;
+    }
+    if (data->mActiveScrolledRoot == aActiveScrolledRoot) {
+      lowestUsableLayerWithScrolledRoot = i;
+      if (topmostLayerWithScrolledRoot < 0) {
+        topmostLayerWithScrolledRoot = i;
       }
     }
+    if (data->mVisibleRegion.Intersects(aVisibleRect))
+      break;
+  }
+  if (topmostLayerWithScrolledRoot < 0) {
+    --i;
+    for (; i >= 0; --i) {
+      ThebesLayerData* data = mThebesLayerDataStack[i];
+      if (data->mActiveScrolledRoot == aActiveScrolledRoot) {
+        topmostLayerWithScrolledRoot = i;
+        break;
+      }
+    }
+  }
 
-    if (layerItems) {
-      // Update the visible region of the layer to account for the new
-      // item
-      nscoord appUnitsPerDevPixel =
-        item->GetUnderlyingFrame()->PresContext()->AppUnitsPerDevPixel();
-      layerItems->mVisibleRect.UnionRect(layerItems->mVisibleRect,
-        item->GetVisibleRect().ToNearestPixels(appUnitsPerDevPixel));
+  if (topmostLayerWithScrolledRoot >= 0) {
+    while (PRUint32(topmostLayerWithScrolledRoot + 1) < mThebesLayerDataStack.Length()) {
+      PopThebesLayerData();
     }
   }
 
-  if (!firstThebesLayerItems->mStartItem) {
-    // The first Thebes layer has nothing in it. Delete the layer.
-    // Ensure layer is released.
-    aLayers->ElementAt(0)->mLayer = nsnull;
-    aLayers->RemoveElementAt(0);
+  nsRefPtr<ThebesLayer> layer;
+  ThebesLayerData* thebesLayerData = nsnull;
+  if (lowestUsableLayerWithScrolledRoot < 0) {
+    layer = CreateOrRecycleThebesLayer(aActiveScrolledRoot);
+    thebesLayerData = new ThebesLayerData();
+    mThebesLayerDataStack.AppendElement(thebesLayerData);
+    thebesLayerData->mLayer = layer;
+    thebesLayerData->mActiveScrolledRoot = aActiveScrolledRoot;
+  } else {
+    thebesLayerData = mThebesLayerDataStack[lowestUsableLayerWithScrolledRoot];
+    layer = thebesLayerData->mLayer;
   }
 
-  for (PRUint32 i = 0; i < aLayers->Length(); ++i) {
-    LayerItems* layerItems = aLayers->ElementAt(i);
+  thebesLayerData->Accumulate(aVisibleRect, aIsOpaque);
+  return layer.forget();
+}
 
-    nscolor color;
-    // Only convert layers with identity transform to ColorLayers, for now.
-    // This simplifies the code to set the clip region.
-    if (layerItems->mThebesLayer &&
-        IsAllUniform(aBuilder, layerItems->mItems, &color) &&
-        layerItems->mLayer->GetTransform().IsIdentity()) {
-      nsRefPtr<ColorLayer> layer = aManager->CreateColorLayer();
-      layer->SetClipRect(layerItems->mThebesLayer->GetClipRect());
-      // Clip to mVisibleRect to ensure only the pixels we want are filled.
-      layer->IntersectClipRect(layerItems->mVisibleRect);
-      layer->SetColor(gfxRGBA(color));
-      layerItems->mLayer = layer.forget();
-      layerItems->mThebesLayer = nsnull;
+/*
+ * Iterate through the non-clip items in aList and its descendants.
+ * For each item we compute the effective clip rect. Each item is assigned
+ * to a layer. We invalidate the areas in ThebesLayers where an item
+ * has moved from one ThebesLayer to another. Also,
+ * aState->mInvalidThebesContent is invalidated in every ThebesLayer.
+ * We set the clip rect for items that generated their own layer.
+ * (ThebesLayers don't need a clip rect on the layer, we clip the items
+ * individually when we draw them.)
+ * We set the visible rect for all layers, although the actual setting
+ * of visible rects for some ThebesLayers is deferred until the calling
+ * of ContainerState::Finish.
+ */
+void
+ContainerState::ProcessDisplayItems(const nsDisplayList& aList,
+                                    const nsRect* aClipRect)
+{
+  for (nsDisplayItem* item = aList.GetBottom(); item; item = item->GetAbove()) {
+    if (item->GetType() == nsDisplayItem::TYPE_CLIP) {
+      nsDisplayClip* clipItem = static_cast<nsDisplayClip*>(item);
+      nsRect clip = clipItem->GetClipRect();
+      if (aClipRect) {
+        clip.IntersectRect(clip, *aClipRect);
+      }
+      ProcessDisplayItems(*clipItem->GetList(), &clip);
+      continue;
     }
 
-    gfxMatrix transform;
-    nsIntRect visibleRect = layerItems->mVisibleRect;
-    if (layerItems->mLayer->GetTransform().Is2D(&transform)) {
-      // if 'transform' is not invertible, then nothing will be displayed
-      // for the layer, so it doesn't really matter what we do here
-      transform.Invert();
-      gfxRect layerVisible = transform.TransformBounds(
-          gfxRect(visibleRect.x, visibleRect.y, visibleRect.width, visibleRect.height));
-      layerVisible.RoundOut();
-      if (NS_FAILED(nsLayoutUtils::GfxRectToIntRect(layerVisible, &visibleRect))) {
-        NS_ERROR("Visible rect transformed out of bounds");
+    PRInt32 appUnitsPerDevPixel = AppUnitsPerDevPixel(item);
+    nsIntRect itemVisibleRect =
+      item->GetVisibleRect().ToNearestPixels(appUnitsPerDevPixel);
+    nsRefPtr<Layer> ownLayer = item->BuildLayer(mBuilder, mManager);
+    // Assign the item to a layer
+    if (ownLayer) {
+      NS_ASSERTION(ownLayer->Manager() == mManager, "Wrong manager");
+      NS_ASSERTION(ownLayer->GetUserData() != &gThebesDisplayItemLayerUserData,
+                   "We shouldn't have a FrameLayerBuilder-managed layer here!");
+      // It has its own layer. Update that layer's clip and visible rects.
+      if (aClipRect) {
+        ownLayer->IntersectClipRect(
+            aClipRect->ToNearestPixels(appUnitsPerDevPixel));
+      }
+      ThebesLayerData* data = GetTopThebesLayerData();
+      if (data) {
+        data->mVisibleAboveRegion.Or(data->mVisibleAboveRegion, itemVisibleRect);
+      }
+      SetVisibleRectForLayer(ownLayer, itemVisibleRect);
+      ContainerLayer* oldContainer = ownLayer->GetParent();
+      if (oldContainer && oldContainer != mContainerLayer) {
+        oldContainer->RemoveChild(ownLayer);
       }
+      NS_ASSERTION(!mNewChildLayers.Contains(ownLayer),
+                   "Layer already in list???");
+      mNewChildLayers.AppendElement(ownLayer);
+      mBuilder->LayerBuilder()->AddLayerDisplayItem(ownLayer, item);
     } else {
-      NS_ERROR("Only 2D transformations currently supported");
+      nsIFrame* f = item->GetUnderlyingFrame();
+      nsPoint offsetToActiveScrolledRoot;
+      nsIFrame* activeScrolledRoot =
+        nsLayoutUtils::GetActiveScrolledRootFor(f, mBuilder->ReferenceFrame(),
+                                                &offsetToActiveScrolledRoot);
+      NS_ASSERTION(offsetToActiveScrolledRoot == f->GetOffsetTo(activeScrolledRoot),
+                   "Wrong offset");
+
+      nsRefPtr<ThebesLayer> thebesLayer =
+        FindThebesLayerFor(itemVisibleRect, activeScrolledRoot,
+                           item->IsOpaque(mBuilder));
+      
+      NS_ASSERTION(f, "Display items that render using Thebes must have a frame");
+      PRUint32 key = item->GetPerFrameKey();
+      NS_ASSERTION(key, "Display items that render using Thebes must have a key");
+      Layer* oldLayer = mBuilder->LayerBuilder()->GetOldLayerFor(f, key);
+      if (oldLayer && thebesLayer != oldLayer) {
+        NS_ASSERTION(oldLayer->AsThebesLayer(),
+                     "The layer for a display item changed type!");
+        // The item has changed layers.
+        // Invalidate the bounds in the old layer and new layer.
+        // The bounds might have changed, but we assume that any difference
+        // in the bounds will have been invalidated for all Thebes layers
+        // in the container via regular frame invalidation.
+        nsRect bounds = item->GetBounds(mBuilder);
+        nsIntRect r = bounds.ToOutsidePixels(appUnitsPerDevPixel);
+        // Update the layer contents
+        InvalidatePostTransformRegion(oldLayer->AsThebesLayer(), r);
+        InvalidatePostTransformRegion(thebesLayer, r);
+
+        // Ensure the relevant area of the window is repainted.
+        // Note that the area we're currently repainting will not be
+        // repainted again, thanks to the logic in nsFrame::InvalidateRoot.
+        mContainerFrame->Invalidate(bounds - mBuilder->ToReferenceFrame(mContainerFrame));
+      }
+
+      mBuilder->LayerBuilder()->
+        AddThebesDisplayItem(thebesLayer, item, aClipRect, mContainerFrame);
     }
-    layerItems->mLayer->SetVisibleRegion(nsIntRegion(visibleRect));
+  }
+}
+
+void
+FrameLayerBuilder::AddThebesDisplayItem(ThebesLayer* aLayer,
+                                        nsDisplayItem* aItem,
+                                        const nsRect* aClipRect,
+                                        nsIFrame* aContainerLayerFrame)
+{
+  AddLayerDisplayItem(aLayer, aItem);
+
+  ThebesLayerItemsEntry* entry = mThebesLayerItems.PutEntry(aLayer);
+  if (entry) {
+    entry->mContainerLayerFrame = aContainerLayerFrame;
+    NS_ASSERTION(aItem->GetUnderlyingFrame(), "Must have frame");
+    entry->mItems.AppendElement(ClippedDisplayItem(aItem, aClipRect));
   }
 }
 
-} // anonymous namespace
+void
+FrameLayerBuilder::AddLayerDisplayItem(Layer* aLayer,
+                                       nsDisplayItem* aItem)
+{
+  if (aLayer->Manager() != mRetainingManager)
+    return;
+
+  nsIFrame* f = aItem->GetUnderlyingFrame();
+  DisplayItemDataEntry* entry = mNewDisplayItemData.PutEntry(f);
+  if (entry) {
+    entry->mData.AppendElement(DisplayItemData(aLayer, aItem->GetPerFrameKey()));
+  }
+}
+
+void
+ContainerState::CollectOldThebesLayers()
+{
+  for (Layer* layer = mContainerLayer->GetFirstChild(); layer;
+       layer = layer->GetNextSibling()) {
+    if (layer->GetUserData() != &gThebesDisplayItemLayerUserData) {
+      // This layer is not for rendering Thebes-based display items
+      continue;
+    }
+    ThebesLayer* thebes = layer->AsThebesLayer();
+    NS_ASSERTION(thebes, "Wrong layer type");
+    mRecycledThebesLayers.AppendElement(thebes);
+  }
+}
+
+void
+ContainerState::Finish()
+{
+  while (!mThebesLayerDataStack.IsEmpty()) {
+    PopThebesLayerData();
+  }
+
+  for (PRUint32 i = 0; i <= mNewChildLayers.Length(); ++i) {
+    // An invariant of this loop is that the layers in mNewChildLayers
+    // with index < i are the first i child layers of mContainerLayer.
+    Layer* layer;
+    if (i < mNewChildLayers.Length()) {
+      layer = mNewChildLayers[i];
+      if (!layer->GetParent()) {
+        // This is not currently a child of the container, so just add it
+        // now.
+        Layer* prevChild = i == 0 ? nsnull : mNewChildLayers[i - 1];
+        mContainerLayer->InsertAfter(layer, prevChild);
+        continue;
+      }
+      NS_ASSERTION(layer->GetParent() == mContainerLayer,
+                   "Layer shouldn't be the child of some other container");
+    } else {
+      layer = nsnull;
+    }
+
+    // If layer is non-null, then it's already a child of the container,
+    // so scan forward until we find it, removing the other layers we
+    // don't want here.
+    // If it's null, scan forward until we've removed all the leftover
+    // children.
+    Layer* nextOldChild = i == 0 ? mContainerLayer->GetFirstChild() :
+      mNewChildLayers[i - 1]->GetNextSibling();
+    while (nextOldChild != layer) {
+      Layer* tmp = nextOldChild;
+      nextOldChild = nextOldChild->GetNextSibling();
+      mContainerLayer->RemoveChild(tmp);
+    }
+    // If non-null, 'layer' is now in the right place in the list, so we
+    // can just move on to the next one.
+  }
+}
 
 already_AddRefed<Layer>
-FrameLayerBuilder::GetContainerLayerFor(nsDisplayListBuilder* aBuilder,
-                                        LayerManager* aManager,
-                                        nsDisplayItem* aContainer,
-                                        const nsDisplayList& aChildren)
+FrameLayerBuilder::BuildContainerLayerFor(nsDisplayListBuilder* aBuilder,
+                                          LayerManager* aManager,
+                                          nsIFrame* aContainerFrame,
+                                          nsDisplayItem* aContainerItem,
+                                          const nsDisplayList& aChildren)
 {
-  // If there's only one layer, then in principle we can try to flatten
-  // things by returning that layer here. But that adds complexity to
-  // retained layer management so we don't do it. Layer backends can
-  // flatten internally.
-  nsRefPtr<ContainerLayer> container = aManager->CreateContainerLayer();
-  if (!container)
-    return nsnull;
+  FrameProperties props = aContainerFrame->Properties();
+  PRUint32 containerDisplayItemKey =
+    aContainerItem ? aContainerItem->GetPerFrameKey() : 0;
+  NS_ASSERTION(aContainerFrame, "Container display items here should have a frame");
+  NS_ASSERTION(!aContainerItem ||
+               aContainerItem->GetUnderlyingFrame() == aContainerFrame,
+               "Container display item must match given frame");
+
+  nsRefPtr<ContainerLayer> containerLayer;
+  if (aManager == mRetainingManager) {
+    Layer* oldLayer = GetOldLayerFor(aContainerFrame, containerDisplayItemKey);
+    if (oldLayer) {
+      NS_ASSERTION(oldLayer->Manager() == aManager, "Wrong manager");
+      NS_ASSERTION(oldLayer->GetType() == Layer::TYPE_CONTAINER,
+                   "Wrong layer type");
+      containerLayer = static_cast<ContainerLayer*>(oldLayer);
+      // Clear clip rect, the caller will set it.
+      containerLayer->SetClipRect(nsnull);
+    }
+  }
+  if (!containerLayer) {
+    // No suitable existing layer was found.
+    containerLayer = aManager->CreateContainerLayer();
+    if (!containerLayer)
+      return nsnull;
+  }
 
-  nsAutoTArray<LayerItems*,10> layerItems;
-  BuildLayers(aBuilder, aChildren, aManager, &layerItems);
+  ContainerState state(aBuilder, aManager, aContainerFrame, containerLayer);
+
+  if (aManager == mRetainingManager) {
+    DisplayItemDataEntry* entry = mNewDisplayItemData.PutEntry(aContainerFrame);
+    if (entry) {
+      entry->mData.AppendElement(
+          DisplayItemData(containerLayer, containerDisplayItemKey));
+    }
+
+    if (mInvalidateAllThebesContent) {
+      state.SetInvalidateAllThebesContent();
+    }
 
-  Layer* lastChild = nsnull;
-  for (PRUint32 i = 0; i < layerItems.Length(); ++i) {
-    Layer* child = layerItems[i]->mLayer;
-    container->InsertAfter(child, lastChild);
-    lastChild = child;
-    // release the layer now because the ItemGroup destructor doesn't run;
-    // the container is still holding a reference to it
-    layerItems[i]->mLayer = nsnull;
+    nsRegion* invalidThebesContent(static_cast<nsRegion*>
+      (props.Get(ThebesLayerInvalidRegionProperty())));
+    if (invalidThebesContent) {
+      nsPoint offset = aBuilder->ToReferenceFrame(aContainerFrame);
+      invalidThebesContent->MoveBy(offset);
+      state.SetInvalidThebesContent(invalidThebesContent->
+        ToOutsidePixels(aContainerFrame->PresContext()->AppUnitsPerDevPixel()));
+      invalidThebesContent->MoveBy(-offset);
+    } else {
+      // Set up region to collect invalidation data
+      props.Set(ThebesLayerInvalidRegionProperty(), new nsRegion());
+    }
+    aContainerFrame->AddStateBits(NS_FRAME_HAS_CONTAINER_LAYER);
   }
-  container->SetIsOpaqueContent(aChildren.IsOpaque());
-  nsRefPtr<Layer> layer = container.forget();
+
+  state.ProcessDisplayItems(aChildren, nsnull);
+  state.Finish();
+
+  containerLayer->SetIsOpaqueContent(aChildren.IsOpaque());
+  nsRefPtr<Layer> layer = containerLayer.forget();
   return layer.forget();
 }
 
 Layer*
 FrameLayerBuilder::GetLeafLayerFor(nsDisplayListBuilder* aBuilder,
                                    LayerManager* aManager,
                                    nsDisplayItem* aItem)
 {
-  // Layers aren't retained yet
-  return nsnull;
+  if (aManager != mRetainingManager)
+    return nsnull;
+
+  nsIFrame* f = aItem->GetUnderlyingFrame();
+  NS_ASSERTION(f, "Can only call GetLeafLayerFor on items that have a frame");
+  Layer* layer = GetOldLayerFor(f, aItem->GetPerFrameKey());
+  if (!layer)
+    return nsnull;
+  if (layer->GetUserData() == &gThebesDisplayItemLayerUserData) {
+    // This layer was created to render Thebes-rendered content for this
+    // display item. The display item should not use it for its own
+    // layer rendering.
+    return nsnull;
+  }
+  // Clear clip rect; the caller is responsible for setting it.
+  layer->SetClipRect(nsnull);
+  return layer;
 }
 
 /* static */ void
 FrameLayerBuilder::InvalidateThebesLayerContents(nsIFrame* aFrame,
                                                  const nsRect& aRect)
 {
-  // do nothing; layers aren't retained yet
+  nsRegion* invalidThebesContent = static_cast<nsRegion*>
+    (aFrame->Properties().Get(ThebesLayerInvalidRegionProperty()));
+  if (!invalidThebesContent)
+    return;
+  invalidThebesContent->Or(*invalidThebesContent, aRect);
+  invalidThebesContent->SimplifyOutward(20);
+}
+
+/* static */ void
+FrameLayerBuilder::InvalidateAllThebesLayerContents(LayerManager* aManager)
+{
+  LayerManagerData* data = static_cast<LayerManagerData*>
+    (aManager->GetUserData());
+  if (data) {
+    data->mInvalidateAllThebesContent = PR_TRUE;
+  }
+}
+
+/* static */ void
+FrameLayerBuilder::InvalidateAllLayers(LayerManager* aManager)
+{
+  LayerManagerData* data = static_cast<LayerManagerData*>
+    (aManager->GetUserData());
+  if (data) {
+    data->mInvalidateAllLayers = PR_TRUE;
+  }
 }
 
 /* static */ void
 FrameLayerBuilder::DrawThebesLayer(ThebesLayer* aLayer,
                                    gfxContext* aContext,
                                    const nsIntRegion& aRegionToDraw,
                                    const nsIntRegion& aRegionToInvalidate,
                                    void* aCallbackData)
 {
-  // For now, we can ignore aRegionToInvalidate since we don't
-  // use retained layers.
+  nsDisplayListBuilder* builder = static_cast<nsDisplayListBuilder*>
+    (aCallbackData);
+  ThebesLayerItemsEntry* entry =
+    builder->LayerBuilder()->mThebesLayerItems.GetEntry(aLayer);
+  NS_ASSERTION(entry, "We shouldn't be drawing into a layer with no items!");
 
-  LayerItems* layerItems = static_cast<LayerItems*>(aLayer->GetUserData());
-  nsDisplayListBuilder* builder =
-    static_cast<nsDisplayListBuilder*>(aCallbackData);
+  gfxMatrix transform;
+  if (!aLayer->GetTransform().Is2D(&transform)) {
+    NS_ERROR("non-2D transform in our Thebes layer!");
+    return;
+  }
+  NS_ASSERTION(!transform.HasNonIntegerTranslation(),
+               "Matrix not just an integer translation?");
+  // make the origin of the context coincide with the origin of the
+  // ThebesLayer
+  gfxContextMatrixAutoSaveRestore saveMatrix(aContext); 
+  aContext->Translate(-gfxPoint(transform.x0, transform.y0));
+  nsIntPoint offset(PRInt32(transform.x0), PRInt32(transform.y0));
 
-  // For now, we'll ignore toDraw and just draw the entire visible
-  // area, because the "visible area" is already confined to just the
-  // area that needs to be repainted. Later, when we start reusing layers
-  // from paint to paint, we'll need to pay attention to toDraw and
-  // actually try to avoid drawing stuff that's not in it.
+  nsPresContext* presContext = entry->mContainerLayerFrame->PresContext();
+  nscoord appUnitsPerDevPixel = presContext->AppUnitsPerDevPixel();
+  nsRect r = (aRegionToInvalidate.GetBounds() + offset).
+    ToAppUnits(appUnitsPerDevPixel);
+  entry->mContainerLayerFrame->Invalidate(r);
 
   // Our list may contain content with different prescontexts at
   // different zoom levels. 'rc' contains the nsIRenderingContext
   // used for the previous display item, and lastPresContext is the
   // prescontext for that item. We also cache the clip state for that
   // item.
+  // XXX maybe we should stop that from being true by forcing content with
+  // different zoom levels into different layers?
   nsRefPtr<nsIRenderingContext> rc;
   nsPresContext* lastPresContext = nsnull;
-  gfxRect currentClip;
+  nsRect currentClip;
   PRBool setClipRect = PR_FALSE;
-  NS_ASSERTION(layerItems->mItems, "No empty layers allowed");
-  for (ItemGroup* group = layerItems->mItems; group;
-       group = group->mNextItemsForLayer) {
+
+  PRUint32 i;
+  // Update visible regions. We need perform visibility analysis again
+  // because we may be asked to draw into part of a ThebesLayer that
+  // isn't actually visible in the window (e.g., because a ThebesLayer
+  // expanded its visible region to a rectangle internally), in which
+  // case the mVisibleRect stored in the display item may be wrong.
+  nsRegion visible = aRegionToDraw.ToAppUnits(appUnitsPerDevPixel);
+  visible.MoveBy(NSIntPixelsToAppUnits(offset.x, appUnitsPerDevPixel),
+                 NSIntPixelsToAppUnits(offset.y, appUnitsPerDevPixel));
+
+  for (i = entry->mItems.Length(); i > 0; --i) {
+    ClippedDisplayItem* cdi = &entry->mItems[i - 1];
+
+    presContext = cdi->mItem->GetUnderlyingFrame()->PresContext();
+    if (presContext->AppUnitsPerDevPixel() != appUnitsPerDevPixel) {
+      // Some kind of zooming detected, just redraw the entire item
+      nsRegion tmp(cdi->mItem->GetBounds(builder));
+      cdi->mItem->RecomputeVisibility(builder, &tmp);
+      continue;
+    }
+
+    if (!cdi->mHasClipRect || cdi->mClipRect.Contains(visible.GetBounds())) {
+      cdi->mItem->RecomputeVisibility(builder, &visible);
+      continue;
+    }
+
+    // Do a little dance to account for the fact that we're clipping
+    // to cdi->mClipRect
+    nsRegion clipped;
+    clipped.And(visible, cdi->mClipRect);
+    nsRegion finalClipped = clipped;
+    cdi->mItem->RecomputeVisibility(builder, &finalClipped);
+    nsRegion removed;
+    removed.Sub(clipped, finalClipped);
+    nsRegion newVisible;
+    newVisible.Sub(visible, removed);
+    // Don't let the visible region get too complex.
+    if (newVisible.GetNumRects() <= 15) {
+      visible = newVisible;
+    }
+  }
+
+  for (i = 0; i < entry->mItems.Length(); ++i) {
+    ClippedDisplayItem* cdi = &entry->mItems[i];
+
+    if (cdi->mItem->GetVisibleRect().IsEmpty())
+      continue;
+
+    presContext = cdi->mItem->GetUnderlyingFrame()->PresContext();
     // If the new desired clip state is different from the current state,
     // update the clip.
-    if (setClipRect != group->mHasClipRect ||
-        (group->mHasClipRect && group->mClipRect != currentClip)) {
+    if (setClipRect != cdi->mHasClipRect ||
+        (cdi->mHasClipRect && cdi->mClipRect != currentClip)) {
       if (setClipRect) {
         aContext->Restore();
       }
-      setClipRect = group->mHasClipRect;
+      setClipRect = cdi->mHasClipRect;
       if (setClipRect) {
+        currentClip = cdi->mClipRect;
         aContext->Save();
         aContext->NewPath();
-        aContext->Rectangle(group->mClipRect, PR_TRUE);
+        gfxRect clip(currentClip.x, currentClip.y, currentClip.width, currentClip.height);
+        clip.ScaleInverse(presContext->AppUnitsPerDevPixel());
+        aContext->Rectangle(clip, PR_TRUE);
         aContext->Clip();
-        currentClip = group->mClipRect;
       }
     }
-    NS_ASSERTION(group->mStartItem, "No empty groups allowed");
-    for (nsDisplayItem* item = group->mStartItem; item != group->mEndItem;
-         item = item->GetAbove()) {
-      nsPresContext* presContext = item->GetUnderlyingFrame()->PresContext();
-      if (presContext != lastPresContext) {
-        // Create a new rendering context with the right
-        // appunits-per-dev-pixel.
-        nsresult rv =
-          presContext->DeviceContext()->CreateRenderingContextInstance(*getter_AddRefs(rc));
-        if (NS_FAILED(rv))
-          break;
-        rc->Init(presContext->DeviceContext(), aContext);
-        lastPresContext = presContext;
-      }
-      item->Paint(builder, rc);
+
+    if (presContext != lastPresContext) {
+      // Create a new rendering context with the right
+      // appunits-per-dev-pixel.
+      nsresult rv =
+        presContext->DeviceContext()->CreateRenderingContextInstance(*getter_AddRefs(rc));
+      if (NS_FAILED(rv))
+        break;
+      rc->Init(presContext->DeviceContext(), aContext);
+      lastPresContext = presContext;
     }
+    cdi->mItem->Paint(builder, rc);
   }
+
   if (setClipRect) {
     aContext->Restore();
   }
 }
 
+#ifdef DEBUG
+static void
+DumpIntRegion(FILE* aStream, const char* aName, const nsIntRegion& aRegion)
+{
+  if (aRegion.IsEmpty())
+    return;
+
+  fprintf(aStream, " [%s=", aName);
+  nsIntRegionRectIterator iter(aRegion);
+  const nsIntRect* r;
+  PRBool first = PR_TRUE;
+  while ((r = iter.Next()) != nsnull) {
+    if (!first) {
+      fputs(";", aStream);
+    } else {
+      first = PR_FALSE;
+    }
+    fprintf(aStream, "%d,%d,%d,%d", r->x, r->y, r->width, r->height);
+  }
+  fputs("]", aStream);
+}
+
+static void
+DumpLayer(FILE* aStream, Layer* aLayer, PRUint32 aIndent)
+{
+  if (!aLayer)
+    return;
+
+  for (PRUint32 i = 0; i < aIndent; ++i) {
+    fputs("  ", aStream);
+  }
+  const char* name = aLayer->Name();
+  ThebesLayer* thebes = aLayer->AsThebesLayer();
+  fprintf(aStream, "%s(%p)", name, aLayer);
+
+  DumpIntRegion(aStream, "visible", aLayer->GetVisibleRegion());
+
+  gfx3DMatrix transform = aLayer->GetTransform();
+  if (!transform.IsIdentity()) {
+    gfxMatrix matrix;
+    if (transform.Is2D(&matrix)) {
+      fprintf(aStream, " [transform=%g,%g; %g,%g; %g,%g]",
+              matrix.xx, matrix.yx, matrix.xy, matrix.yy, matrix.x0, matrix.y0);
+    } else {
+      fprintf(aStream, " [transform=%g,%g,%g,%g; %g,%g,%g,%g; %g,%g,%g,%g; %g,%g,%g,%g]",
+              transform._11, transform._12, transform._13, transform._14,
+              transform._21, transform._22, transform._23, transform._24,
+              transform._31, transform._32, transform._33, transform._34,
+              transform._41, transform._42, transform._43, transform._44);
+    }
+  }
+
+  const nsIntRect* clip = aLayer->GetClipRect();
+  if (clip) {
+    fprintf(aStream, " [clip=%d,%d,%d,%d]",
+            clip->x, clip->y, clip->width, clip->height);
+  }
+
+  float opacity = aLayer->GetOpacity();
+  if (opacity != 1.0) {
+    fprintf(aStream, " [opacity=%f]", opacity);
+  }
+
+  if (aLayer->IsOpaqueContent()) {
+    fputs(" [opaqueContent]", aStream);
+  }
+
+  if (thebes) {
+    DumpIntRegion(aStream, "valid", thebes->GetValidRegion());
+  }
+
+  fputs("\n", aStream);
+
+  for (Layer* child = aLayer->GetFirstChild(); child;
+       child = child->GetNextSibling()) {
+    DumpLayer(aStream, child, aIndent + 1);
+  }
+}
+
+/* static */ void
+FrameLayerBuilder::DumpLayerTree(LayerManager* aManager)
+{
+  DumpLayer(stderr, aManager->GetRoot(), 0);
+}
+
+void
+FrameLayerBuilder::DumpRetainedLayerTree()
+{
+  if (mRetainingManager) {
+    DumpLayerTree(mRetainingManager);
+  }
+}
+#endif
+
 } // namespace mozilla
--- a/layout/base/FrameLayerBuilder.h
+++ b/layout/base/FrameLayerBuilder.h
@@ -33,68 +33,322 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef FRAMELAYERBUILDER_H_
 #define FRAMELAYERBUILDER_H_
 
-#include "Layers.h"
+#include "nsTHashtable.h"
+#include "nsHashKeys.h"
+#include "nsTArray.h"
+#include "nsRegion.h"
+#include "nsIFrame.h"
 
 class nsDisplayListBuilder;
 class nsDisplayList;
 class nsDisplayItem;
-class nsIFrame;
-class nsRect;
-class nsIntRegion;
 class gfxContext;
 
 namespace mozilla {
 
+namespace layers {
+class Layer;
+class ThebesLayer;
+class LayerManager;
+}
+
+/**
+ * The FrameLayerBuilder belongs to an nsDisplayListBuilder and is
+ * responsible for converting display lists into layer trees.
+ * 
+ * The most important API in this class is BuildContainerLayerFor. This
+ * method takes a display list as input and constructs a ContainerLayer
+ * with child layers that render the contents of the display list. It
+ * also updates userdata for the retained layer manager, and
+ * DisplayItemDataProperty data for frames, to record the relationship
+ * between frames and layers.
+ * 
+ * That data enables us to retain layer trees. When constructing a
+ * ContainerLayer, we first check to see if there's an existing
+ * ContainerLayer for the same frame that can be recycled. If we recycle
+ * it, we also try to reuse its existing ThebesLayer children to render
+ * the display items without layers of their own. The idea is that by
+ * recycling layers deterministically, we can ensure that when nothing
+ * changes in a display list, we will reuse the existing layers without
+ * changes.
+ * 
+ * We expose a GetLeafLayerFor method that can be called by display items
+ * that make their own layers (e.g. canvas and video); this method
+ * locates the last layer used to render the display item, if any, and
+ * return it as a candidate for recycling.
+ * 
+ * FrameLayerBuilder sets up ThebesLayers so that 0,0 in the Thebes layer
+ * corresponds to the (pixel-snapped) top-left of the aActiveScrolledRoot.
+ * It sets up ContainerLayers so that 0,0 in the container layer
+ * corresponds to the snapped top-left of the display list reference frame.
+ */
 class FrameLayerBuilder {
 public:
-  typedef mozilla::layers::Layer Layer;
-  typedef mozilla::layers::ThebesLayer ThebesLayer;
-  typedef mozilla::layers::LayerManager LayerManager;
+  typedef layers::Layer Layer; 
+  typedef layers::ThebesLayer ThebesLayer;
+  typedef layers::LayerManager LayerManager;
+
+  FrameLayerBuilder() :
+    mRetainingManager(nsnull),
+    mInvalidateAllThebesContent(PR_FALSE),
+    mInvalidateAllLayers(PR_FALSE)
+  {
+    mNewDisplayItemData.Init();
+    mThebesLayerItems.Init();
+  }
 
   /**
-   * Get a container layer for a display item that contains a child
-   * list, either reusing an existing one or creating a new one.
-   * aContainer may be null, in which case we construct a root layer.
+   * Call this to register a layer tree which was retained since the last
+   * paint.
    */
-  already_AddRefed<Layer> GetContainerLayerFor(nsDisplayListBuilder* aBuilder,
-                                               LayerManager* aManager,
-                                               nsDisplayItem* aContainer,
-                                               const nsDisplayList& aChildren);
+  void BeginUpdatingRetainedLayers(LayerManager* aManager);
+
+  /**
+   * Call this whenever we end a transaction on aManager. If aManager
+   * is not the retained layer manager then it must be a temporary layer
+   * manager that will not be used again.
+   */
+  void DidEndTransaction(LayerManager* aManager);
 
   /**
-   * Get a retained layer for a leaf display item. Returns null if no
-   * layer is available, in which case the caller will probably need to
-   * create one.
+   * Build a container layer for a display item that contains a child
+   * list, either reusing an existing one or creating a new one. It
+   * sets the container layer children to layers which together render
+   * the contents of the display list. It reuses existing layers from
+   * the retained layer manager if possible.
+   * aContainer may be null, in which case we construct a root layer.
+   * This gets called by display list code. It calls BuildLayer on the
+   * items in the display list, making items with their own layers
+   * children of the new container, and assigning all other items to
+   * ThebesLayer children created and managed by the FrameLayerBuilder.
+   * Returns a layer with clip rect cleared; it is the
+   * caller's responsibility to add any clip rect and set the visible
+   * region.
+   */
+  already_AddRefed<Layer> BuildContainerLayerFor(nsDisplayListBuilder* aBuilder,
+                                                 LayerManager* aManager,
+                                                 nsIFrame* aContainerFrame,
+                                                 nsDisplayItem* aContainerItem,
+                                                 const nsDisplayList& aChildren);
+
+  /**
+   * Get a retained layer for a display item that needs to create its own
+   * layer for rendering (i.e. under nsDisplayItem::BuildLayer). Returns
+   * null if no retained layer is available, which usually means that this
+   * display item didn't have a layer before so the caller will
+   * need to create one.
+   * Returns a layer with clip rect cleared; it is the
+   * caller's responsibility to add any clip rect and set the visible
+   * region.
    */
   Layer* GetLeafLayerFor(nsDisplayListBuilder* aBuilder,
                          LayerManager* aManager,
                          nsDisplayItem* aItem);
 
   /**
    * Call this during invalidation if aFrame has
    * the NS_FRAME_HAS_CONTAINER_LAYER state bit. Only the nearest
    * ancestor frame of the damaged frame that has
    * NS_FRAME_HAS_CONTAINER_LAYER needs to be invalidated this way.
    */
   static void InvalidateThebesLayerContents(nsIFrame* aFrame,
                                             const nsRect& aRect);
 
   /**
+   * Call this to force *all* retained layer contents to be discarded at
+   * the next paint.
+   */
+  static void InvalidateAllThebesLayerContents(LayerManager* aManager);
+
+  /**
+   * Call this to force all retained layers to be discarded and recreated at
+   * the next paint.
+   */
+  static void InvalidateAllLayers(LayerManager* aManager);
+  
+  /**
    * This callback must be provided to EndTransaction. The callback data
    * must be the nsDisplayListBuilder containing this FrameLayerBuilder.
    */
   static void DrawThebesLayer(ThebesLayer* aLayer,
                               gfxContext* aContext,
                               const nsIntRegion& aRegionToDraw,
                               const nsIntRegion& aRegionToInvalidate,
                               void* aCallbackData);
+
+#ifdef DEBUG
+  /**
+   * Dumps aManager's layer tree to stderr.
+   */
+  static void DumpLayerTree(LayerManager* aManager);
+
+  /**
+   * Dumps this FrameLayerBuilder's retained layer manager's retained
+   * layer tree to stderr.
+   */
+  void DumpRetainedLayerTree();
+#endif
+
+  /******* PRIVATE METHODS to FrameLayerBuilder.cpp ********/
+  /* These are only in the public section because they need
+   * to be called by file-scope helper functions in FrameLayerBuilder.cpp.
+   */
+  
+  /**
+   * Record aItem as a display item that is rendered by aLayer.
+   */
+  void AddLayerDisplayItem(Layer* aLayer, nsDisplayItem* aItem);
+
+  /**
+   * Record aItem as a display item that is rendered by the ThebesLayer
+   * aLayer, with aClipRect, where aContainerLayerFrame is the frame
+   * for the container layer this ThebesItem belongs to.
+   * aItem must have an underlying frame.
+   */
+  void AddThebesDisplayItem(ThebesLayer* aLayer, nsDisplayItem* aItem,
+                            const nsRect* aClipRect,
+                            nsIFrame* aContainerLayerFrame);
+
+  /**
+   * Given a frame and a display item key that uniquely identifies a
+   * display item for the frame, find the layer that was last used to
+   * render that display item. Returns null if there is no such layer.
+   * This could be a dedicated layer for the display item, or a ThebesLayer
+   * that renders many display items.
+   */
+  Layer* GetOldLayerFor(nsIFrame* aFrame, PRUint32 aDisplayItemKey);
+
+protected:
+  /**
+   * We store an array of these for each frame that is associated with
+   * one or more retained layers. Each DisplayItemData records the layer
+   * used to render one of the frame's display items.
+   */
+  class DisplayItemData {
+  public:
+    DisplayItemData(Layer* aLayer, PRUint32 aKey)
+      : mLayer(aLayer), mDisplayItemKey(aKey) {}
+
+    nsRefPtr<Layer> mLayer;
+    PRUint32        mDisplayItemKey;
+  };
+
+  static void InternalDestroyDisplayItemData(nsIFrame* aFrame,
+                                             void* aPropertyValue,
+                                             PRBool aRemoveFromFramesWithLayers);
+  static void DestroyDisplayItemData(nsIFrame* aFrame, void* aPropertyValue);
+
+  /**
+   * For DisplayItemDataProperty, the property value *is* an
+   * nsTArray<DisplayItemData>, not a pointer to an array. This works
+   * because sizeof(nsTArray<T>) == sizeof(void*).
+   */
+  NS_DECLARE_FRAME_PROPERTY_WITH_FRAME_IN_DTOR(DisplayItemDataProperty,
+                                               DestroyDisplayItemData)
+
+  /**
+   * We accumulate DisplayItemData elements in a hashtable during
+   * the paint process, and store them in the frame property only when
+   * paint is complete. This is the hashentry for that hashtable.
+   */
+  class DisplayItemDataEntry : public nsPtrHashKey<nsIFrame> {
+  public:
+    DisplayItemDataEntry(const nsIFrame *key) : nsPtrHashKey<nsIFrame>(key) {}
+    DisplayItemDataEntry(const DisplayItemDataEntry &toCopy) :
+      nsPtrHashKey<nsIFrame>(toCopy.mKey), mData(toCopy.mData)
+    {
+      NS_ERROR("Should never be called, since we ALLOW_MEMMOVE");
+    }
+
+    PRBool HasContainerLayer();
+
+    nsTArray<DisplayItemData> mData;
+
+    enum { ALLOW_MEMMOVE = PR_TRUE };
+  };
+
+  /**
+   * We store one of these for each display item associated with a
+   * ThebesLayer, in a hashtable that maps each ThebesLayer to an array
+   * of ClippedDisplayItems. (ThebesLayerItemsEntry is the hash entry
+   * for that hashtable.)
+   * These are only stored during the paint process, so that the
+   * DrawThebesLayer callback can figure out which items to draw for the
+   * ThebesLayer.
+   * mItem always has an underlying frame.
+   */
+  struct ClippedDisplayItem {
+    ClippedDisplayItem(nsDisplayItem* aItem, const nsRect* aClipRect)
+      : mItem(aItem), mHasClipRect(aClipRect != nsnull)
+    {
+      if (mHasClipRect) {
+        mClipRect = *aClipRect;
+      }
+    }
+
+    nsDisplayItem* mItem;
+    nsRect         mClipRect;
+    PRPackedBool   mHasClipRect;
+  };
+
+  /**
+   * We accumulate ClippedDisplayItem elements in a hashtable during
+   * the paint process. This is the hashentry for that hashtable.
+   */
+  class ThebesLayerItemsEntry : public nsPtrHashKey<ThebesLayer> {
+  public:
+    ThebesLayerItemsEntry(const ThebesLayer *key) : nsPtrHashKey<ThebesLayer>(key) {}
+    ThebesLayerItemsEntry(const ThebesLayerItemsEntry &toCopy) :
+      nsPtrHashKey<ThebesLayer>(toCopy.mKey), mItems(toCopy.mItems)
+    {
+      NS_ERROR("Should never be called, since we ALLOW_MEMMOVE");
+    }
+
+    nsTArray<ClippedDisplayItem> mItems;
+    nsIFrame* mContainerLayerFrame;
+
+    enum { ALLOW_MEMMOVE = PR_TRUE };
+  };
+
+  void RemoveThebesItemsForLayerSubtree(Layer* aLayer);
+
+  static PLDHashOperator UpdateDisplayItemDataForFrame(nsPtrHashKey<nsIFrame>* aEntry,
+                                                       void* aUserArg);
+  static PLDHashOperator StoreNewDisplayItemData(DisplayItemDataEntry* aEntry,
+                                                 void* aUserArg);
+
+  /**
+   * The layer manager belonging to the widget that is being retained
+   * across paints.
+   */
+  LayerManager*                       mRetainingManager;
+  /**
+   * A map from frames to a list of (display item key, layer) pairs that
+   * describes what layers various parts of the frame are assigned to.
+   */
+  nsTHashtable<DisplayItemDataEntry>  mNewDisplayItemData;
+  /**
+   * A map from ThebesLayers to the list of display items (plus
+   * clipping data) to be rendered in the layer.
+   */
+  nsTHashtable<ThebesLayerItemsEntry> mThebesLayerItems;
+  /**
+   * Indicates that the contents of all ThebesLayers should be rerendered
+   * during this paint.
+   */
+  PRPackedBool                        mInvalidateAllThebesContent;
+  /**
+   * Indicates that the entire layer tree should be rerendered
+   * during this paint.
+   */
+  PRPackedBool                        mInvalidateAllLayers;
 };
 
 }
 
 #endif /* FRAMELAYERBUILDER_H_ */
--- a/layout/base/nsDisplayList.cpp
+++ b/layout/base/nsDisplayList.cpp
@@ -448,27 +448,28 @@ void nsDisplayList::PaintForFrame(nsDisp
 
   if (aCtx) {
     layerManager->BeginTransactionWithTarget(aCtx->ThebesContext());
   } else {
     layerManager->BeginTransaction();
   }
 
   nsRefPtr<Layer> root = aBuilder->LayerBuilder()->
-    GetContainerLayerFor(aBuilder, layerManager, nsnull, *this);
+    BuildContainerLayerFor(aBuilder, layerManager, aForFrame, nsnull, *this);
   if (!root)
     return;
 
   nsIntRect visible =
     mVisibleRect.ToNearestPixels(aForFrame->PresContext()->AppUnitsPerDevPixel());
   root->SetVisibleRegion(nsIntRegion(visible));
 
   layerManager->SetRoot(root);
   layerManager->EndTransaction(FrameLayerBuilder::DrawThebesLayer,
                                aBuilder);
+  aBuilder->LayerBuilder()->DidEndTransaction(layerManager);
 
   nsCSSRendering::DidPaint();
 }
 
 PRUint32 nsDisplayList::Count() const {
   PRUint32 count = 0;
   for (nsDisplayItem* i = GetBottom(); i; i = i->GetAbove()) {
     ++count;
@@ -634,16 +635,34 @@ void nsDisplayList::SortByContentOrder(n
 }
 
 void nsDisplayList::Sort(nsDisplayListBuilder* aBuilder,
                          SortLEQ aCmp, void* aClosure) {
   ExplodeAnonymousChildLists(aBuilder);
   ::Sort(this, Count(), aCmp, aClosure);
 }
 
+PRBool nsDisplayItem::RecomputeVisibility(nsDisplayListBuilder* aBuilder,
+                                          nsRegion* aVisibleRegion) {
+  nsRect bounds = GetBounds(aBuilder);
+
+  nsRegion itemVisible;
+  itemVisible.And(*aVisibleRegion, bounds);
+  mVisibleRect = itemVisible.GetBounds();
+
+  if (mVisibleRect.IsEmpty() ||
+      !ComputeVisibility(aBuilder, aVisibleRegion, nsnull))
+    return PR_FALSE;
+
+  if (IsOpaque(aBuilder)) {
+    aVisibleRegion->Sub(*aVisibleRegion, bounds);
+  }
+  return PR_TRUE;
+}
+
 void nsDisplaySolidColor::Paint(nsDisplayListBuilder* aBuilder,
                                 nsIRenderingContext* aCtx) {
   aCtx->SetColor(mColor);
   aCtx->FillRect(mVisibleRect);
 }
 
 // Returns TRUE if aContainedRect is guaranteed to be contained in
 // the rounded rect defined by aRoundedRect and aRadii. Complex cases are
@@ -1142,17 +1161,17 @@ PRBool nsDisplayOpacity::IsOpaque(nsDisp
   return PR_FALSE;
 }
 
 // nsDisplayOpacity uses layers for rendering
 already_AddRefed<Layer>
 nsDisplayOpacity::BuildLayer(nsDisplayListBuilder* aBuilder,
                              LayerManager* aManager) {
   nsRefPtr<Layer> layer = aBuilder->LayerBuilder()->
-    GetContainerLayerFor(aBuilder, aManager, this, mList);
+    BuildContainerLayerFor(aBuilder, aManager, mFrame, this, mList);
   if (!layer)
     return nsnull;
 
   layer->SetOpacity(mFrame->GetStyleDisplay()->mOpacity);
   return layer.forget();
 }
 
 PRBool nsDisplayOpacity::ComputeVisibility(nsDisplayListBuilder* aBuilder,
--- a/layout/base/nsDisplayList.h
+++ b/layout/base/nsDisplayList.h
@@ -638,17 +638,27 @@ public:
 #ifdef NS_DEBUG
   /**
    * For debugging and stuff
    */
   virtual const char* Name() = 0;
 #endif
 
   nsDisplayItem* GetAbove() { return mAbove; }
-  
+
+  /**
+   * Like ComputeVisibility, but does the work that nsDisplayList
+   * does per-item:
+   * -- Intersects GetBounds with aVisibleRegion and puts the result
+   * in mVisibleRect
+   * -- Subtracts bounds from aVisibleRegion if the item is opaque
+   */
+  PRBool RecomputeVisibility(nsDisplayListBuilder* aBuilder,
+                             nsRegion* aVisibleRegion);
+
 protected:
   friend class nsDisplayList;
   
   nsDisplayItem() {
     mAbove = nsnull;
   }
   
   nsIFrame* mFrame;
--- a/layout/base/nsLayoutUtils.cpp
+++ b/layout/base/nsLayoutUtils.cpp
@@ -672,16 +672,30 @@ nsLayoutUtils::GetScrollableFrameFor(nsI
   nsIFrame *frame = aScrolledFrame->GetParent();
   if (!frame) {
     return nsnull;
   }
   nsIScrollableFrame *sf = do_QueryFrame(frame);
   return sf;
 }
 
+nsIFrame*
+nsLayoutUtils::GetActiveScrolledRootFor(nsIFrame* aFrame,
+                                        nsIFrame* aStopAtAncestor,
+                                        nsPoint* aOffset)
+{
+  // For now, just use aStopAtAncestor --- i.e., treat nothing as active.
+  // We'll make this more precise when we actually start using layers for
+  // scrolling.
+  if (aOffset) {
+    *aOffset = aFrame->GetOffsetTo(aStopAtAncestor);
+  }
+  return aStopAtAncestor;
+}
+
 // static
 nsIScrollableFrame*
 nsLayoutUtils::GetNearestScrollableFrameForDirection(nsIFrame* aFrame,
                                                      Direction aDirection)
 {
   NS_ASSERTION(aFrame, "GetNearestScrollableFrameForDirection expects a non-null frame");
   for (nsIFrame* f = aFrame; f; f = nsLayoutUtils::GetCrossDocParentFrame(f)) {
     nsIScrollableFrame* scrollableFrame = do_QueryFrame(f);
--- a/layout/base/nsLayoutUtils.h
+++ b/layout/base/nsLayoutUtils.h
@@ -283,16 +283,27 @@ public:
    *
    * Just like IsProperAncestorFrameCrossDoc, except that it returns true when
    * aFrame == aAncestorFrame.
    */
   static PRBool IsAncestorFrameCrossDoc(nsIFrame* aAncestorFrame, nsIFrame* aFrame,
                                         nsIFrame* aCommonAncestor = nsnull);
 
   /**
+   * Finds the nearest ancestor frame that is the root of an "actively
+   * scrolled" frame subtree, or aStopAtAncestor if there is no
+   * such ancestor before we reach aStopAtAncestor in the ancestor chain.
+   * We expect frames with the same "active scrolled root" to be
+   * scrolled together, so we'll place them in the same ThebesLayer.
+   */
+  static nsIFrame* GetActiveScrolledRootFor(nsIFrame* aFrame,
+                                            nsIFrame* aStopAtAncestor,
+                                            nsPoint* aOffset);
+
+  /**
     * GetFrameFor returns the root frame for a view
     * @param aView is the view to return the root frame for
     * @return the root frame for the view
     */
   static nsIFrame* GetFrameFor(nsIView *aView)
   { return static_cast<nsIFrame*>(aView->GetClientData()); }
 
   /**
--- a/layout/reftests/scrolling/reftest.list
+++ b/layout/reftests/scrolling/reftest.list
@@ -1,3 +1,4 @@
 HTTP == fixed-1.html fixed-1.html?ref
 HTTP == opacity-mixed-scrolling-1.html opacity-mixed-scrolling-1.html?ref
 HTTP == simple-1.html simple-1.html?ref
+== uncovering-1.html uncovering-1-ref.html
new file mode 100644
--- /dev/null
+++ b/layout/reftests/scrolling/uncovering-1-ref.html
@@ -0,0 +1,23 @@
+<!DOCTYPE HTML>
+<html>
+<head>
+<style>
+body {
+  width: 1500px;
+  overflow: hidden;
+}
+div#bottom {
+  position: fixed;
+  left: 0;
+  top: 0;
+  height: 200px;
+  width: 200px;
+  background: green;
+}
+</style>
+</head>
+<body>
+<div id="bottom"></div>
+<div style="width:600px; height:100px; background:pink;"></div>
+</body>
+</html>
new file mode 100644
--- /dev/null
+++ b/layout/reftests/scrolling/uncovering-1.html
@@ -0,0 +1,31 @@
+<!DOCTYPE HTML>
+<html class="reftest-wait">
+<head>
+<style>
+body {
+  width: 1500px;
+  overflow: hidden;
+}
+div#bottom {
+  position: fixed;
+  left: 0;
+  top: 0;
+  height: 200px;
+  width: 200px;
+  background: green;
+}
+</style>
+</head>
+<body>
+<div id="bottom"></div>
+<div style="width:600px; height:100px; background:pink;"></div>
+<script>
+document.documentElement.scrollLeft = 200;
+function doTest() {
+  document.documentElement.removeAttribute("class");
+  document.documentElement.scrollLeft = 0;
+}
+window.addEventListener("MozReftestInvalidate", doTest, false);
+</script>
+</body>
+</html>