b=518506 order child widget moves a little carefully when scrolling r=roc
authorKarl Tomlinson <karlt+@karlt.net>
Mon, 14 Dec 2009 10:01:33 +1300
changeset 35698 274480cf21d74e008336532f954e48d3700f3504
parent 35697 d6cf9a15c50fc191d563b7f12c6e0b61086800d7
child 35699 f20c4c211ac85da40ed2b1098ea1c5049c9e621e
push id10683
push userktomlinson@mozilla.com
push dateMon, 14 Dec 2009 02:37:51 +0000
treeherdermozilla-central@f20c4c211ac8 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersroc
bugs518506
milestone1.9.3a1pre
b=518506 order child widget moves a little carefully when scrolling r=roc
view/src/nsScrollPortView.cpp
widget/public/nsIWidget.h
widget/src/cocoa/nsChildView.mm
widget/src/gtk2/Makefile.in
widget/src/gtk2/nsWindow.cpp
widget/src/gtk2/nsWindow.h
widget/src/os2/nsWindow.cpp
widget/src/qt/nsWindow.cpp
widget/src/windows/nsWindow.cpp
widget/src/xpwidgets/nsBaseWidget.cpp
widget/src/xpwidgets/nsBaseWidget.h
--- a/view/src/nsScrollPortView.cpp
+++ b/view/src/nsScrollPortView.cpp
@@ -572,101 +572,16 @@ ConvertBlitRegionToPixelRects(const nsRe
                             pixRect.ToAppUnits(aAppUnitsPerPixel));
   }
 
   nsRegion repaint;
   repaint.Sub(aBlitRegion, *aAppunitsBlitRegion);
   aRepaintRegion->Or(*aRepaintRegion, repaint);
 }
 
-/**
- * An nsTArray comparator that lets us sort nsIntRects by their right edge.
- */
-class RightEdgeComparator {
-public:
-  /** @return True if the elements are equals; false otherwise. */
-  PRBool Equals(const nsIntRect& aA, const nsIntRect& aB) const
-  {
-    return aA.XMost() == aB.XMost();
-  }
-  /** @return True if (a < b); false otherwise. */
-  PRBool LessThan(const nsIntRect& aA, const nsIntRect& aB) const
-  {
-    return aA.XMost() < aB.XMost();
-  }
-};
-
-// If aPixDelta has a negative component, flip aRect across the
-// axis in that direction. We do this so we can assume all scrolling is
-// down and to the right to simplify SortBlitRectsForCopy
-static nsIntRect
-FlipRect(const nsIntRect& aRect, nsIntPoint aPixDelta)
-{
-  nsIntRect r = aRect;
-  if (aPixDelta.x < 0) {
-    r.x = -r.XMost();
-  }
-  if (aPixDelta.y < 0) {
-    r.y = -r.YMost();
-  }
-  return r;
-}
-
-// Sort aRects so that moving rectangle aRects[i] - aPixDelta to aRects[i]
-// will not cause the rectangle to overlap any rectangles that haven't
-// moved yet.
-// See http://weblogs.mozillazine.org/roc/archives/2009/08/homework_answer.html
-static void
-SortBlitRectsForCopy(nsIntPoint aPixDelta, nsTArray<nsIntRect>* aRects)
-{
-  nsTArray<nsIntRect> rects;
-
-  for (PRUint32 i = 0; i < aRects->Length(); ++i) {
-    nsIntRect* r = &aRects->ElementAt(i);
-    nsIntRect rect =
-      FlipRect(nsIntRect(r->x, r->y, r->width, r->height), aPixDelta);
-    rects.AppendElement(rect);
-  }
-  rects.Sort(RightEdgeComparator());
-
-  aRects->Clear();
-  // This could probably be improved a bit for some worst-case scenarios.
-  // But in common cases this should be very fast, and we shouldn't
-  // make it more complex unless we really need to.
-  while (!rects.IsEmpty()) {
-    PRInt32 i = rects.Length() - 1;
-    PRBool overlappedBelow;
-    do {
-      overlappedBelow = PR_FALSE;
-      const nsIntRect& rectI = rects[i];
-      // see if any rectangle < i overlaps rectI horizontally and is below
-      // rectI
-      for (PRInt32 j = i - 1; j >= 0; --j) {
-        if (rects[j].XMost() <= rectI.x) {
-          // No rectangle with index <= j can overlap rectI horizontally
-          break;
-        }
-        // Rectangle j overlaps rectI horizontally.
-        if (rects[j].y >= rectI.y) {
-          // Rectangle j is below rectangle i. This is the rightmost such
-          // rectangle, so set i to this rectangle and continue.
-          i = j;
-          overlappedBelow = PR_TRUE;
-          break;
-        }
-      }
-    } while (overlappedBelow); 
-
-    // Rectangle i has no rectangles to the right or below.
-    // Flip it back before saving the result.
-    aRects->AppendElement(FlipRect(rects[i], aPixDelta));
-    rects.RemoveElementAt(i);
-  }
-}
-
 void nsScrollPortView::Scroll(nsView *aScrolledView, nsPoint aTwipsDelta,
                               nsIntPoint aPixDelta, PRInt32 aP2A,
                               const nsTArray<nsIWidget::Configuration>& aConfigurations)
 {
   if (aTwipsDelta.x != 0 || aTwipsDelta.y != 0)
   {
     /* If we should invalidate our wrapped view, we should do so at this
      * point.
@@ -703,17 +618,16 @@ void nsScrollPortView::Scroll(nsView *aS
       // adjust dirty regions appropriately.
       mViewManager->WillBitBlit(this, aTwipsDelta);
 
       // innerPixRegion is in device pixels
       nsTArray<nsIntRect> blitRects;
       nsRegion blitRectsRegion;
       ConvertBlitRegionToPixelRects(blitRegion, aP2A, &blitRects, &repaintRegion,
                                     &blitRectsRegion);
-      SortBlitRectsForCopy(aPixDelta, &blitRects);
 
       nearestWidget->Scroll(aPixDelta, blitRects, aConfigurations);
       AdjustChildWidgets(aScrolledView, nearestWidgetOffset, aP2A, PR_TRUE);
       repaintRegion.MoveBy(-nearestWidgetOffset);
       blitRectsRegion.MoveBy(-nearestWidgetOffset);
       mViewManager->UpdateViewAfterScroll(this, blitRectsRegion, repaintRegion);
     }
   }
--- a/widget/public/nsIWidget.h
+++ b/widget/public/nsIWidget.h
@@ -668,21 +668,18 @@ class nsIWidget : public nsISupports {
      * possible) modify the specified child widgets.
      * 
      * This will invalidate areas of the children that have changed, unless
      * they have just moved by the scroll amount, but does not need to
      * invalidate any part of this widget, except where the scroll
      * operation fails to blit because part of the window is unavailable
      * (e.g. partially offscreen).
      * 
-     * The caller guarantees that the rectangles in aDestRects are ordered
-     * so that copying from aDestRects[i] - aDelta to aDestRects[i] does
-     * not alter anything in aDestRects[j] - aDelta for j > i. That is,
-     * it's safe to just copy the rectangles in the order given in
-     * aDestRects.
+     * The caller guarantees that the rectangles in aDestRects are
+     * non-intersecting.
      *
      * @param aDelta amount to scroll (device pixels)
      * @param aDestRects rectangles to copy into
      * (device pixels relative to this widget)
      * @param aReconfigureChildren commands to set the bounds and clip
      * region of a subset of the children of this widget; these should
      * be performed simultaneously with the scrolling, as far as possible,
      * to avoid visual artifacts.
--- a/widget/src/cocoa/nsChildView.mm
+++ b/widget/src/cocoa/nsChildView.mm
@@ -1710,21 +1710,23 @@ void nsChildView::Scroll(const nsIntPoin
   if (!mParentView)
     return;
 
   BOOL viewWasDirty = mVisible && [mView needsDisplay];
   if (mVisible && !aDestRects.IsEmpty()) {
     // Union of all source and destination rects
     nsIntRegion destRegion;
     NSSize scrollVector = {aDelta.x, aDelta.y};
-    for (PRUint32 i = 0; i < aDestRects.Length(); ++i) {
+    nsIntRect destRect; // keep the last rect
+    for (BlitRectIter iter(aDelta, aDestRects); !iter.IsDone(); ++iter) {
+      destRect = iter.Rect();
       NSRect rect;
-      GeckoRectToNSRect(aDestRects[i] - aDelta, rect);
+      GeckoRectToNSRect(destRect - aDelta, rect);
       [mView scrollRect:rect by:scrollVector];
-      destRegion.Or(destRegion, aDestRects[i]);
+      destRegion.Or(destRegion, destRect);
     }
 #ifdef NS_LEOPARD_AND_LATER
     if (viewWasDirty) {
       nsIntRect allRects = destRegion.GetBounds();
       allRects.UnionRect(allRects, allRects - aDelta);
       NSRect all;
       GeckoRectToNSRect(allRects, all);
       [mView translateRectsNeedingDisplayInRect:all by:scrollVector];
@@ -1749,17 +1751,17 @@ void nsChildView::Scroll(const nsIntPoin
 
     // Leopard, at least, has a nasty bug where calling scrollRect:by: doesn't
     // actually trigger a window update. A window update is only triggered
     // if you actually paint something. In some cases Gecko might optimize
     // scrolling in such a way that nothing actually gets repainted.
     // So let's invalidate one pixel. We'll pick a pixel on the trailing edge
     // of the last destination rectangle, since in most situations that's going
     // to be invalidated anyway.
-    nsIntRect lastRect = aDestRects[aDestRects.Length() - 1] + aDelta;
+    nsIntRect lastRect = destRect + aDelta;
     nsIntPoint pointToInvalidate(
       PickValueForSign(aDelta.x, lastRect.XMost(), lastRect.x, lastRect.x - 1),
       PickValueForSign(aDelta.y, lastRect.YMost(), lastRect.y, lastRect.y - 1));
     if (!nsIntRect(0,0,mBounds.width,mBounds.height).Contains(pointToInvalidate)) {
       pointToInvalidate = nsIntPoint(0, 0);
     }
     Invalidate(nsIntRect(pointToInvalidate, nsIntSize(1,1)), PR_FALSE);
   }
--- a/widget/src/gtk2/Makefile.in
+++ b/widget/src/gtk2/Makefile.in
@@ -102,23 +102,24 @@ endif
 
 # build our subdirs, too
 
 SHARED_LIBRARY_LIBS = ../xpwidgets/libxpwidgets_s.a
 
 EXTRA_DSO_LDOPTS += \
 		$(MOZ_COMPONENT_LIBS) \
 		-lgkgfx \
+		-lthebes \
+		$(MOZ_CAIRO_LIBS) \
                 $(MOZ_STARTUP_NOTIFICATION_LIBS) \
 		$(XLDFLAGS) \
 		$(XLIBS) \
 		$(XEXT_LIBS) \
 		$(XCOMPOSITE_LIBS) \
 		$(MOZ_GTK2_LIBS) \
-		-lthebes \
 		$(QCMS_LIBS) \
 		$(NULL)
 
 ifdef MOZ_PLATFORM_HILDON
 ifdef MOZ_ENABLE_GCONF
 EXTRA_DSO_LDOPTS += $(MOZ_GCONF_LIBS)
 endif
 endif
@@ -137,17 +138,17 @@ ifdef NATIVE_THEME_SUPPORT
 CSRCS		+= gtk2drawing.c
 CPPSRCS		+= nsNativeThemeGTK.cpp
 DEFINES		+= -DNATIVE_THEME_SUPPORT
 endif
 
 include $(topsrcdir)/config/rules.mk
 
 CFLAGS          += $(MOZ_GTK2_CFLAGS) $(MOZ_STARTUP_NOTIFICATION_CFLAGS)
-CXXFLAGS        += $(MOZ_GTK2_CFLAGS) $(MOZ_STARTUP_NOTIFICATION_CFLAGS)
+CXXFLAGS        += $(MOZ_CAIRO_CFLAGS) $(MOZ_GTK2_CFLAGS) $(MOZ_STARTUP_NOTIFICATION_CFLAGS)
 
 ifdef MOZ_PLATFORM_HILDON
 ifdef MOZ_ENABLE_GCONF
 CXXFLAGS += $(MOZ_GCONF_CFLAGS)
 endif
 endif
 
 DEFINES         += -DUSE_XIM
--- a/widget/src/gtk2/nsWindow.cpp
+++ b/widget/src/gtk2/nsWindow.cpp
@@ -109,16 +109,19 @@ static const char sAccessibilityKey [] =
 #include <gdk/gdk.h>
 #include <wchar.h>
 #include "imgIContainer.h"
 #include "nsGfxCIID.h"
 #include "nsImageToPixbuf.h"
 #include "nsIInterfaceRequestorUtils.h"
 #include "nsAutoPtr.h"
 
+extern "C" {
+#include "pixman.h"
+}
 #include "gfxPlatformGtk.h"
 #include "gfxContext.h"
 #include "gfxImageSurface.h"
 
 #ifdef MOZ_X11
 #include "gfxXlibSurface.h"
 #endif
 
@@ -370,16 +373,35 @@ template<class T> gpointer
 FuncToGpointer(T aFunction)
 {
     return reinterpret_cast<gpointer>
         (reinterpret_cast<uintptr_t>
          // This cast just provides a warning if T is not a function.
          (reinterpret_cast<void (*)()>(aFunction)));
 }
 
+// nsAutoRef<pixman_region32> uses nsSimpleRef<> to know how to automatically
+// destroy regions.
+template <>
+class nsSimpleRef<pixman_region32> : public pixman_region32 {
+protected:
+    typedef pixman_region32 RawRef;
+
+    nsSimpleRef() { data = nsnull; }
+    nsSimpleRef(const RawRef &aRawRef) : pixman_region32(aRawRef) { }
+
+    static void Release(pixman_region32& region) {
+        pixman_region32_fini(&region);
+    }
+    // Whether this needs to be released:
+    PRBool HaveResource() const { return data != nsnull; }
+
+    pixman_region32& get() { return *this; }
+};
+
 nsWindow::nsWindow()
 {
     mIsTopLevel       = PR_FALSE;
     mIsDestroyed      = PR_FALSE;
     mNeedsResize      = PR_FALSE;
     mNeedsMove        = PR_FALSE;
     mListenForResizes = PR_FALSE;
     mIsShown          = PR_FALSE;
@@ -1680,110 +1702,304 @@ NS_IMETHODIMP
 nsWindow::Update()
 {
     if (!mGdkWindow)
         return NS_OK;
 
     LOGDRAW(("Update [%p] %p\n", this, mGdkWindow));
 
     gdk_window_process_updates(mGdkWindow, FALSE);
+    // Send the updates to the server.
+    gdk_display_flush(gdk_drawable_get_display(GDK_DRAWABLE(mGdkWindow)));
     return NS_OK;
 }
 
+static pixman_box32
+ToPixmanBox(const nsIntRect& aRect)
+{
+    pixman_box32_t result;
+    result.x1 = aRect.x;
+    result.y1 = aRect.y;
+    result.x2 = aRect.XMost();
+    result.y2 = aRect.YMost();
+    return result;
+}
+
+static nsIntRect
+ToIntRect(const pixman_box32& aBox)
+{
+    nsIntRect result;
+    result.x = aBox.x1;
+    result.y = aBox.y1;
+    result.width = aBox.x2 - aBox.x1;
+    result.height = aBox.y2 - aBox.y1;
+    return result;
+}
+
+static void
+InitRegion(pixman_region32* aRegion,
+           const nsTArray<nsIntRect>& aRects)
+{
+    nsAutoTArray<pixman_box32,10> rects;
+    rects.SetCapacity(aRects.Length());
+    for (PRUint32 i = 0; i < aRects.Length (); ++i) {
+        rects.AppendElement(ToPixmanBox(aRects[i]));
+    }
+
+    pixman_region32_init_rects(aRegion,
+                               rects.Elements(), rects.Length());
+}
+
+static void
+GetIntRects(pixman_region32& aRegion, nsTArray<nsIntRect>* aRects)
+{
+    int nRects;
+    pixman_box32* boxes = pixman_region32_rectangles(&aRegion, &nRects);
+    aRects->SetCapacity(aRects->Length() + nRects);
+    for (int i = 0; i < nRects; ++i) {
+        aRects->AppendElement(ToIntRect(boxes[i]));
+    }
+}
+
+/**
+ * ScrollItemIter uses ScrollRectIterBase to order blit rectangles and
+ * rectangular child clip regions in a way such that moving the items in this
+ * order will avoid conflicts of blit rectangles.  Conflicts with child
+ * windows are also avoided in situations with simple child window
+ * arrangements.
+ *
+ * The blit rectangles must not intersect with any other rectangles (of either
+ * blits or children).  Note that child clip regions are not guaranteed to be
+ * exclusive of other child clip regions, so ScrollItemIter may not
+ * necessarily provide an optimal order (if a child rectangle intersects
+ * another child rectangle).
+ */
+class ScrollItemIter : public ScrollRectIterBase {
+public:
+    // Each aChildRects[i] corresponds to
+    ScrollItemIter(const nsIntPoint& aDelta,
+                   const nsTArray<nsIntRect>& aBlitRects,
+                   const nsTArray<const nsIWidget::Configuration*>aChildConfs,
+                   const nsTArray<nsIntRect>& aChildSubRects);
+
+    PRBool IsBlit() const { return !Configuration(); };
+
+private:
+    struct ScrollItem : public ScrollRect {
+        ScrollItem(const nsIntRect& aIntRect) : ScrollRect(aIntRect) {}
+
+        const nsIWidget::Configuration *mChildConf;
+    };
+
+public:
+    const nsIWidget::Configuration* Configuration() const
+    {
+        return static_cast<const ScrollItem&>(Rect()).mChildConf;
+    }
+
+private:
+    // Copying is not supported.
+    ScrollItemIter(const ScrollItemIter&);
+    void operator=(const ScrollItemIter&);
+
+    nsTArray<ScrollItem> mRects;
+};
+
+ScrollItemIter::ScrollItemIter(const nsIntPoint& aDelta,
+                               const nsTArray<nsIntRect>& aBlitRects,
+                               const nsTArray<const nsIWidget::Configuration*>aChildConfs,
+                               const nsTArray<nsIntRect>& aChildSubRects)
+  : mRects(aBlitRects.Length() + aChildConfs.Length())
+{
+    for (PRUint32 i = 0; i < aBlitRects.Length(); ++i) {
+        if (ScrollItem* item = mRects.AppendElement(aBlitRects[i])) {
+            item->mChildConf = nsnull;
+        }
+    }
+
+    PRUint32 numChildren =
+        NS_MIN(aChildConfs.Length(), aChildSubRects.Length());
+    for (PRUint32 i = 0; i < numChildren; ++i) {
+        if (ScrollItem* item = mRects.AppendElement(aChildSubRects[i])) {
+            item->mChildConf = aChildConfs[i];
+        }
+    }
+
+    // Link items into a chain.
+    ScrollRect *next = nsnull;
+    for (PRUint32 i = mRects.Length(); i--; ) {
+        mRects[i].mNext = next;
+        next = &mRects[i];
+    }
+
+    BaseInit(aDelta, next);
+}
+
 void
 nsWindow::Scroll(const nsIntPoint& aDelta,
                  const nsTArray<nsIntRect>& aDestRects,
                  const nsTArray<Configuration>& aConfigurations)
 {
     if (!mGdkWindow) {
         NS_ERROR("Cannot scroll widget");
         return;
     }
 
-    nsAutoTArray<nsWindow*,1> windowsToShow;
-    // Hide any widgets that are becoming invisible or that are moving.
-    // Moving widgets are hidden for the duration of the scroll so that
-    // the XCopyArea treats their drawn pixels as part of the window
-    // that should be scrolled. This works well when the widgets are
-    // moving because they're being scrolled, which is normally true.
+    // Empty Xlib's request buffer to reduce the likelihood of it getting
+    // emptied mid way through the scroll, in the hope that the server gets
+    // all the requests at once.
+    gdk_display_flush(gdk_drawable_get_display(GDK_DRAWABLE(mGdkWindow)));
+
+    // Collect the destination positions of moving child windows where they
+    // will eventually obscure their parent.
+    nsTArray<const Configuration*> movingChildren;
+    nsTArray<nsIntRect> movingChildSubRects;
+
     for (PRUint32 i = 0; i < aConfigurations.Length(); ++i) {
-        const Configuration& configuration = aConfigurations[i];
-        nsWindow* w = static_cast<nsWindow*>(configuration.mChild);
+        const Configuration* conf = &aConfigurations[i];
+        nsWindow* w = static_cast<nsWindow*>(conf->mChild);
         NS_ASSERTION(w->GetParent() == this,
                      "Configured widget is not a child");
-        if (w->mIsShown &&
-            (configuration.mClipRegion.IsEmpty() ||
-             configuration.mBounds != w->mBounds)) {
-            w->NativeShow(PR_FALSE);
-            windowsToShow.AppendElement(w);
-        }
-    }
-
-    // The parts of source regions not covered by their destination get marked
-    // invalid (by GDK).  This is necessary (until covered by another blit)
-    // because GDK translates any pending expose events to the destination,
-    // and so doesn't know whether an expose event might have been due on the
-    // source.
+
+        if (!w->mIsShown)
+            continue;
+
+        // Set the clip region of all visible windows to the intersection of
+        // the current and new region.  This reduces the conflict area with
+        // other objects (including stationary objects).
+        w->SetWindowClipRegion(conf->mClipRegion, PR_TRUE);
+
+        if (conf->mBounds.TopLeft() == w->mBounds.TopLeft())
+            continue; // window is not moving
+
+        nsAutoTArray<nsIntRect,1> rects; // of clip region intersection
+        w->GetWindowClipRegion(&rects);
+
+        // ScrollItemIter is designed only for rectangular scroll items.
+        //
+        // It is not suitable to use the bounding rectangle of complex child
+        // clip regions because that rectangle may intersect with blit
+        // rectangles and ScrollItemIter would then not necessarily provide
+        // the correct order for any such blit rectangles.  If child windows
+        // are not moved in the optimal order there will be some flicker
+        // during the scroll, which will be corrected through invalidations,
+        // but, if blit rectangles were moved in the wrong order, then some
+        // parts would get moved twice, which would not be corrected through
+        // invalidations.
+        //
+        // Choosing a sub-rectangle for the scroll item would make some parts
+        // of the child window scroll nicely but not others.  This can
+        // actually look worse than the whole window being moved out of order,
+        // so moving of child windows with complex clip regions is simply
+        // delayed until after blitting.
+        if (rects.Length() != 1)
+            continue; // no moving content or non-rectangular clip-region
+
+        movingChildren.AppendElement(conf);
+
+        // Destination position wrt mGdkWindow top left.
+        nsIntRect subRect = rects[0] + conf->mBounds.TopLeft();
+        movingChildSubRects.AppendElement(subRect);
+    }
+
+    nsAutoRef<pixman_region32> blitRegion;
+    InitRegion(&blitRegion, aDestRects);
+
+    // Remove some parts of the moving parent region that will be covered by
+    // moving child widgets.  These parts won't need drawing anyway, and it
+    // breaks up the blit rectangles so that we have a chance of moving them
+    // without conflicts with child rectangles.
     //
-    // However, GDK 2.18 does not subtract the invalid regions at the
-    // destinations from the update_area, so the seams between different moves
-    // remain invalid.  GDK 2.18 also delays and queues move operations.  If
-    // gdk_window_process_updates is called before the moves are flushed, GDK
-    // 2.18 removes the invalid seams from the move regions, so the seams are
-    // left with their old content until they get redrawn.  Therefore, the
-    // subtraction of destination invalid regions is performed here.
-    GdkRegion* updateArea = gdk_window_get_update_area(mGdkWindow);
-    if (!updateArea) {
-        updateArea = gdk_region_new(); // Aborts on OOM.
-    }
-
-    // gdk_window_move_region, up to GDK 2.16, has a ghastly bug where it
-    // doesn't restrict blitting to the given region, and blits its full
-    // bounding box. So we have to work around that by blitting one rectangle
-    // at a time.
-    for (PRUint32 i = 0; i < aDestRects.Length(); ++i) {
-        const nsIntRect& r = aDestRects[i];
-        GdkRectangle gdkSource =
-            { r.x - aDelta.x, r.y - aDelta.y, r.width, r.height };
-        GdkRegion* rectRegion = gdk_region_rectangle(&gdkSource);
-        gdk_window_move_region(GDK_WINDOW(mGdkWindow), rectRegion,
-                               aDelta.x, aDelta.y);
-
-        // The part of the old invalid region that is moving.
-        GdkRegion* updateChanges = gdk_region_copy(rectRegion);
-        gdk_region_intersect(updateChanges, updateArea);
-        gdk_region_offset(updateChanges, aDelta.x, aDelta.y);
-
-        // Make |rectRegion| the destination
-        gdk_region_offset(rectRegion, aDelta.x, aDelta.y);
-        // Remove any old invalid areas covered at the destination.
-        gdk_region_subtract(updateArea, rectRegion);
-        gdk_region_destroy(rectRegion);
-
-        // The update_area from the move_region contains:
-        // 1. The part of the source region not covered by the destination.
-        // 2. Any destination regions for which the source was obscured by
-        //    parent window clips or child windows.
-        GdkRegion* newUpdates = gdk_window_get_update_area(mGdkWindow);
-        if (newUpdates) {
-            gdk_region_union(updateChanges, newUpdates);
-            gdk_region_destroy(newUpdates);
+    // Also, subtracting the child sub-rectangles from the blit region ensures
+    // that the blit rectangles will not overlap with any blit or child
+    // rectangles, so ScrollItemIter will ensure that blit rectangles do not
+    // conflict with each other.
+    {
+        nsAutoRef<pixman_region32> childRegion;
+        InitRegion(&childRegion, movingChildSubRects);
+
+        pixman_region32_subtract(&blitRegion, &blitRegion, &childRegion);
+    }
+
+    nsTArray<nsIntRect> blitRects;
+    GetIntRects(blitRegion, &blitRects);
+
+    GdkRegion* updateArea = gdk_region_new(); // aborts on OOM
+
+    for (ScrollItemIter iter(aDelta, blitRects,
+                             movingChildren, movingChildSubRects);
+         !iter.IsDone(); ++iter) {
+        if (iter.IsBlit()) {
+            // The parts of source regions not covered by their destination
+            // get marked invalid by gdk_window_move_region.  This is
+            // necessary (until covered by another blit) because GDK
+            // translates any pending expose events to the destination, and so
+            // doesn't know whether an expose event might have been due on the
+            // source.
+            //
+            // However, GDK 2.18 does not subtract the invalid regions at the
+            // destinations from the update_area, so the seams between
+            // different moves remain invalid.  GDK 2.18 also delays and
+            // queues move operations.  If gdk_window_process_updates is
+            // called before the moves are flushed, GDK 2.18 removes the
+            // invalid seams from the move regions, so the seams are left with
+            // their old content until they get redrawn.  Therefore, the
+            // subtraction of destination invalid regions is performed here.
+            GdkRegion* recentUpdates = gdk_window_get_update_area(mGdkWindow);
+            if (recentUpdates) {
+                gdk_region_union(updateArea, recentUpdates);
+                gdk_region_destroy(recentUpdates);
+            } 
+
+            // We don't attempt to collect rects into regions because
+            // gdk_window_move_region, up to GDK 2.16, has a bug where it
+            // doesn't restrict blitting to the given region, and blits its
+            // full bounding box.
+            nsIntRect source = iter.Rect() - aDelta;
+            GdkRectangle gdkSource =
+                { source.x, source.y, source.width, source.height };
+            GdkRegion* rectRegion = gdk_region_rectangle(&gdkSource);
+            gdk_window_move_region(mGdkWindow, rectRegion,
+                                   aDelta.x, aDelta.y);
+
+            // The update_area on mGdkWindow from the move_region contains
+            // invalidations from the move:
+            // 1. The part of the source region not covered by the destination.
+            // 2. Any destination regions for which the source was obscured by
+            //    parent window clips or child windows.
+            //
+            // Our copy of the old invalid region needs adjusting.
+
+            // The part of the old invalid region that is moving.
+            GdkRegion* updateChanges = gdk_region_copy(rectRegion);
+            gdk_region_intersect(updateChanges, updateArea);
+            gdk_region_offset(updateChanges, aDelta.x, aDelta.y);
+
+            // Make |rectRegion| the destination
+            gdk_region_offset(rectRegion, aDelta.x, aDelta.y);
+            // Remove any old invalid areas covered at the destination.
+            gdk_region_subtract(updateArea, rectRegion);
+            gdk_region_union(updateArea, updateChanges);
+
+            gdk_region_destroy(updateChanges);
+            gdk_region_destroy(rectRegion);
+        } else {
+            const Configuration *conf = iter.Configuration();
+            nsWindow* w = static_cast<nsWindow*>(conf->mChild);
+            const nsIntRect& newBounds = conf->mBounds;
+            // (This move will modify the invalid_area on mGdkWindow to
+            // include areas that are uncovered when the child moves.)
+            w->Move(newBounds.x, newBounds.y);
         }
-        gdk_region_union(updateArea, updateChanges);
-        gdk_region_destroy(updateChanges);
     }
 
     gdk_window_invalidate_region(mGdkWindow, updateArea, FALSE);
     gdk_region_destroy(updateArea);
 
     ConfigureChildren(aConfigurations);
-
-    for (PRUint32 i = 0; i < windowsToShow.Length(); ++i) {
-        windowsToShow[i]->NativeShow(PR_TRUE);
-    }
 }
 
 void*
 nsWindow::GetNativeData(PRUint32 aDataType)
 {
     switch (aDataType) {
     case NS_NATIVE_WINDOW:
     case NS_NATIVE_WIDGET: {
@@ -4465,51 +4681,74 @@ nsWindow::GetTransparencyMode()
 nsresult
 nsWindow::ConfigureChildren(const nsTArray<Configuration>& aConfigurations)
 {
     for (PRUint32 i = 0; i < aConfigurations.Length(); ++i) {
         const Configuration& configuration = aConfigurations[i];
         nsWindow* w = static_cast<nsWindow*>(configuration.mChild);
         NS_ASSERTION(w->GetParent() == this,
                      "Configured widget is not a child");
-        nsresult rv = w->SetWindowClipRegion(configuration.mClipRegion);
-        NS_ENSURE_SUCCESS(rv, rv);
+        w->SetWindowClipRegion(configuration.mClipRegion, PR_TRUE);
         if (w->mBounds.Size() != configuration.mBounds.Size()) {
             w->Resize(configuration.mBounds.x, configuration.mBounds.y,
                       configuration.mBounds.width, configuration.mBounds.height,
                       PR_TRUE);
         } else if (w->mBounds.TopLeft() != configuration.mBounds.TopLeft()) {
             w->Move(configuration.mBounds.x, configuration.mBounds.y);
         } 
+        w->SetWindowClipRegion(configuration.mClipRegion, PR_FALSE);
     }
     return NS_OK;
 }
 
-nsresult
-nsWindow::SetWindowClipRegion(const nsTArray<nsIntRect>& aRects)
-{
-    if (!StoreWindowClipRegion(aRects))
-        return NS_OK;
+void
+nsWindow::SetWindowClipRegion(const nsTArray<nsIntRect>& aRects,
+                              PRBool aIntersectWithExisting)
+{
+    const nsTArray<nsIntRect>* newRects = &aRects;
+
+    nsAutoTArray<nsIntRect,1> intersectRects;
+    if (aIntersectWithExisting) {
+        nsAutoTArray<nsIntRect,1> existingRects;
+        GetWindowClipRegion(&existingRects);
+
+        nsAutoRef<pixman_region32> existingRegion;
+        InitRegion(&existingRegion, existingRects);
+        nsAutoRef<pixman_region32> newRegion;
+        InitRegion(&newRegion, aRects);
+        nsAutoRef<pixman_region32> intersectRegion;
+        pixman_region32_intersect(&intersectRegion,
+                                  &newRegion, &existingRegion);
+
+        if (pixman_region32_equal(&intersectRegion, &existingRegion))
+            return;
+
+        if (!pixman_region32_equal(&intersectRegion, &newRegion)) {
+            GetIntRects(intersectRegion, &intersectRects);
+            newRects = &intersectRects;
+        }
+    }
+
+    if (!StoreWindowClipRegion(*newRects))
+        return;
 
     if (!mGdkWindow)
-        return NS_OK;
-
-    GdkRegion *region = gdk_region_new();
-    if (!region)
-        return NS_ERROR_OUT_OF_MEMORY;
-    for (PRUint32 i = 0; i < aRects.Length(); ++i) {
-        const nsIntRect& r = aRects[i];
+        return;
+
+    GdkRegion *region = gdk_region_new(); // aborts on OOM
+    for (PRUint32 i = 0; i < newRects->Length(); ++i) {
+        const nsIntRect& r = newRects->ElementAt(i);
         GdkRectangle rect = { r.x, r.y, r.width, r.height };
         gdk_region_union_with_rect(region, &rect);
     }
 
     gdk_window_shape_combine_region(mGdkWindow, region, 0, 0);
     gdk_region_destroy(region);
 
-    return NS_OK;
+    return;
 }
 
 void
 nsWindow::ResizeTransparencyBitmap(PRInt32 aNewWidth, PRInt32 aNewHeight)
 {
     if (!mTransparencyBitmap)
         return;
 
--- a/widget/src/gtk2/nsWindow.h
+++ b/widget/src/gtk2/nsWindow.h
@@ -437,17 +437,18 @@ private:
     GtkWidget         *GetMozContainerWidget();
     nsWindow          *GetContainerWindow();
     void               SetUrgencyHint(GtkWidget *top_window, PRBool state);
     void              *SetupPluginPort(void);
     nsresult           SetWindowIconList(const nsTArray<nsCString> &aIconList);
     void               SetDefaultIcon(void);
     void               InitButtonEvent(nsMouseEvent &aEvent, GdkEventButton *aGdkEvent);
     PRBool             DispatchCommandEvent(nsIAtom* aCommand);
-    nsresult           SetWindowClipRegion(const nsTArray<nsIntRect>& aRects);
+    void               SetWindowClipRegion(const nsTArray<nsIntRect>& aRects,
+                                           PRBool aIntersectWithExisting);
 
     GtkWidget          *mShell;
     MozContainer       *mContainer;
     GdkWindow          *mGdkWindow;
 
     GtkWindowGroup     *mWindowGroup;
 
     PRUint32            mContainerGotFocus : 1,
--- a/widget/src/os2/nsWindow.cpp
+++ b/widget/src/os2/nsWindow.cpp
@@ -2122,19 +2122,19 @@ nsWindow::Scroll(const nsIntPoint& aDelt
 
   // This prevents screen corruption while scrolling during
   // a Moz-originated drag - the hps isn't actually used but
   // fetching it unlocks the screen so it can be updated.
   HPS hps = 0;
   CheckDragStatus(ACTION_SCROLL, &hps);
 
   // Step through each rectangle to be scrolled.
-  for (PRUint32 i = 0; i < aDestRects.Length(); ++i) {
+  for (BlitRectIter iter(aDelta, aDestRects); !iter.IsDone(); ++iter) {
     nsIntRect affectedRect;
-    affectedRect.UnionRect(aDestRects[i], aDestRects[i] - aDelta);
+    affectedRect.UnionRect(iter.Rect(), iter.Rect() - aDelta);
 
     ULONG flags = SW_INVALIDATERGN;
 
     // For each child window, see if it intersects the scroll rect.
     for (nsWindow* w = static_cast<nsWindow*>(GetFirstChild()); w;
          w = static_cast<nsWindow*>(w->GetNextSibling())) {
 
       // If it intersects, we want to scroll it but only if it
--- a/widget/src/qt/nsWindow.cpp
+++ b/widget/src/qt/nsWindow.cpp
@@ -660,19 +660,19 @@ nsWindow::Scroll(const nsIntPoint& aDelt
         if (w->mIsShown &&
             (configuration.mClipRegion.IsEmpty() ||
              configuration.mBounds != w->mBounds)) {
             w->NativeShow(PR_FALSE);
             windowsToShow.AppendElement(w);
         }
     }
 
-    for ( unsigned int i = 0; i < aDestRects.Length(); ++i)
+    for (BlitRectIter iter(aDelta, aDestRects); !iter.IsDone(); ++iter) {
     {
-        const nsIntRect & r = aDestRects[i];
+        const nsIntRect & r = iter.Rect();
         QRect rect(r.x - aDelta.x, r.y - aDelta.y, r.width, r.height);
         mWidget->scroll(aDelta.x, aDelta.y, rect);
     }
     ConfigureChildren(aConfigurations);
 
     // Show windows again...
     for (PRUint32 i = 0; i < windowsToShow.Length(); ++i) {
         windowsToShow[i]->NativeShow(PR_TRUE);
--- a/widget/src/windows/nsWindow.cpp
+++ b/widget/src/windows/nsWindow.cpp
@@ -2284,33 +2284,33 @@ nsWindow::Scroll(const nsIntPoint& aDelt
   if (!destRgn) {
     // OOM?
     ::DeleteObject((HGDIOBJ)updateRgn);
     return;
   }
 
   DWORD ourThreadID = GetWindowThreadProcessId(mWnd, NULL);
 
-  for (PRUint32 i = 0; i < aDestRects.Length(); ++i) {
-    const nsIntRect& destRect = aDestRects[i];
+  for (BlitRectIter iter(aDelta, aDestRects); !iter.IsDone(); ++iter) {
+    const nsIntRect& destRect = iter.Rect();
     nsIntRect affectedRect;
     affectedRect.UnionRect(destRect, destRect - aDelta);
     UINT flags = SW_SCROLLCHILDREN;
     // Now check if any of our children would be affected by
     // SW_SCROLLCHILDREN but not supposed to scroll.
     for (nsWindow* w = static_cast<nsWindow*>(GetFirstChild()); w;
          w = static_cast<nsWindow*>(w->GetNextSibling())) {
       if (w->mBounds.Intersects(affectedRect)) {
         // This child will be affected
         nsPtrHashKey<nsWindow>* entry = scrolledWidgets.GetEntry(w);
         if (entry) {
           // It's supposed to be scrolled, so we can still use
           // SW_SCROLLCHILDREN. But don't allow SW_SCROLLCHILDREN to be
-          // used on it again by a later rectangle in aDestRects, we
-          // don't want it to move twice!
+          // used on it again by a later rectangle; we don't want it to
+          // move twice!
           scrolledWidgets.RawRemoveEntry(entry);
 
           nsIntPoint screenOffset = WidgetToScreenOffset();
           RECT screenAffectedRect = {
             screenOffset.x + affectedRect.x,
             screenOffset.y + affectedRect.y,
             screenOffset.x + affectedRect.XMost(),
             screenOffset.y + affectedRect.YMost()
--- a/widget/src/xpwidgets/nsBaseWidget.cpp
+++ b/widget/src/xpwidgets/nsBaseWidget.cpp
@@ -929,16 +929,127 @@ nsBaseWidget::ResolveIconName(const nsAS
 }
 
 NS_IMETHODIMP 
 nsBaseWidget::BeginResizeDrag(nsGUIEvent* aEvent, PRInt32 aHorizontal, PRInt32 aVertical)
 {
   return NS_ERROR_NOT_IMPLEMENTED;
 }
  
+//////////////////////////////////////////////////////////////
+//
+// Code to sort rectangles for scrolling.
+//
+// The algorithm used here is similar to that described at
+// http://weblogs.mozillazine.org/roc/archives/2009/08/homework_answer.html
+//
+//////////////////////////////////////////////////////////////
+
+void
+ScrollRectIterBase::BaseInit(const nsIntPoint& aDelta, ScrollRect* aHead)
+{
+  mHead = aHead;
+  // Reflect the coordinate system of the rectangles so that we can assume
+  // that rectangles are moving in the direction of decreasing x and y.
+  Flip(aDelta);
+
+  // Do an initial sort of the rectangles by y and then reverse-x.
+  // nsRegion does not guarantee yx-banded rectangles but still tends to
+  // prefer breaking up rectangles vertically and joining horizontally, so
+  // tends to have fewer rectangles across x than down y, making this
+  // algorithm more efficient for rectangles from nsRegion when y is the
+  // primary sort parameter.
+  ScrollRect* unmovedHead; // chain of unmoved rectangles
+  {
+    nsTArray<ScrollRect*> array;
+    for (ScrollRect* r = mHead; r; r = r->mNext) {
+      array.AppendElement(r);
+    }
+    array.Sort(InitialSortComparator());
+
+    ScrollRect *next = nsnull;
+    for (PRUint32 i = array.Length(); i--; ) {
+      array[i]->mNext = next;
+      next = array[i];
+    }
+    unmovedHead = next;
+    // mHead becomes the start of the moved chain.
+    mHead = nsnull;
+  }
+
+  // Try to move each rect from an unmoved chain to the moved chain.
+  mTailLink = &mHead;
+  while (unmovedHead) {
+    // Move() will check for other rectangles that might need to be moved first
+    // and move them also.
+    Move(&unmovedHead);
+  }
+
+  // Reflect back to the original coordinate system.
+  Flip(aDelta);
+}
+
+void ScrollRectIterBase::Move(ScrollRect** aUnmovedLink)
+{
+  ScrollRect* rect = *aUnmovedLink;
+  // Remove rect from the unmoved chain.
+  *aUnmovedLink = rect->mNext;
+  rect->mNext = nsnull;
+
+  // Check subsequent rectangles that overlap vertically to see whether they
+  // might need to be moved first.
+  //
+  // The overlapping subsequent rectangles that are not moved this time get
+  // checked for each of their preceding unmoved overlapping rectangles,
+  // which adds an O(n^2) cost to this algorithm (where n is the number of
+  // rectangles across x).  The reverse-x ordering from InitialSortComparator
+  // avoids this for the case when rectangles are aligned in y.
+  for (ScrollRect** nextLink = aUnmovedLink;
+       ScrollRect* otherRect = *nextLink; ) {
+    NS_ASSERTION(otherRect->y >= rect->y, "Scroll rectangles out of order");
+    if (otherRect->y >= rect->YMost()) // doesn't overlap vertically
+      break;
+
+    // This only moves the other rectangle first if it is entirely to the
+    // left.  No promises are made regarding intersecting rectangles.  Moving
+    // another intersecting rectangle with merely x < rect->x (but XMost() >
+    // rect->x) can cause more conflicts between rectangles that do not
+    // intersect each other.
+    if (otherRect->XMost() <= rect->x) {
+      Move(nextLink);
+      // *nextLink now points to a subsequent rectangle.
+    } else {
+      // Step over otherRect for now.
+      nextLink = &otherRect->mNext;
+    }
+  }
+
+  // Add rect to the moved chain.
+  *mTailLink = rect;
+  mTailLink = &rect->mNext;
+}
+
+BlitRectIter::BlitRectIter(const nsIntPoint& aDelta,
+                           const nsTArray<nsIntRect>& aRects)
+    : mRects(aRects.Length())
+{
+    for (PRUint32 i = 0; i < aRects.Length(); ++i) {
+        mRects.AppendElement(aRects[i]);
+    }
+
+    // Link rectangles into a chain.
+    ScrollRect *next = nsnull;
+    for (PRUint32 i = mRects.Length(); i--; ) {
+        mRects[i].mNext = next;
+        next = &mRects[i];
+    }
+
+    BaseInit(aDelta, next);
+}
+
 #ifdef DEBUG
 //////////////////////////////////////////////////////////////
 //
 // Convert a GUI event message code to a string.
 // Makes it a lot easier to debug events.
 //
 // See gtk/nsWidget.cpp and windows/nsWindow.cpp
 // for a DebugPrintEvent() function that uses
--- a/widget/src/xpwidgets/nsBaseWidget.h
+++ b/widget/src/xpwidgets/nsBaseWidget.h
@@ -186,17 +186,17 @@ protected:
   nsCursor          mCursor;
   nsWindowType      mWindowType;
   nsBorderStyle     mBorderStyle;
   PRPackedBool      mOnDestroyCalled;
   nsIntRect         mBounds;
   nsIntRect*        mOriginalBounds;
   // When this pointer is null, the widget is not clipped
   nsAutoArrayPtr<nsIntRect> mClipRects;
-  PRInt32           mClipRectCount;
+  PRUint32          mClipRectCount;
   PRInt32           mZIndex;
   nsSizeMode        mSizeMode;
 
   // the last rolled up popup. Only set this when an nsAutoRollup is in scope,
   // so it can be cleared automatically.
   static nsIContent* mLastRollup;
     
 #ifdef DEBUG
@@ -244,9 +244,94 @@ class nsAutoRollup
   PRBool wasClear;
 
   public:
 
   nsAutoRollup();
   ~nsAutoRollup();
 };
 
+/**
+ * BlitRectIter and/or ScrollRectIterBase are classes used in
+ * nsIWidget::Scroll() implementations.  They provide sorting of rectangles
+ * such that copying from rects[i] - aDelta to rects[i] does not alter
+ * anything in rects[j] for each j > i when rect[i] and rect[j] do not
+ * intersect each other nor any other rectangle.  That is, it is safe to just
+ * copy non-intersecting rectangles in the order provided.
+ *
+ * ScrollRectIterBase is only instantiated within derived classes.  It expects
+ * to be initialized through BaseInit() with a linked list of rectangles.
+ *
+ * BlitRectIter provides a simple constructor from an array of nsIntRects.
+ */
+
+class ScrollRectIterBase {
+public:
+  PRBool IsDone() { return mHead == nsnull; }
+  void operator++() { mHead = mHead->mNext; }
+  const nsIntRect& Rect() const { return *mHead; }
+
+protected:
+  ScrollRectIterBase() {}
+
+  struct ScrollRect : public nsIntRect {
+    ScrollRect(const nsIntRect& aIntRect) : nsIntRect(aIntRect) {}
+
+    // Flip the coordinate system so that we can assume that the rectangles
+    // are moving in the direction of decreasing x and y (left and up).
+    // This function is its own inverse.
+    void Flip(const nsIntPoint& aDelta)
+    {
+      if (aDelta.x > 0) x = -XMost();
+      if (aDelta.y > 0) y = -YMost();
+    }
+
+    ScrollRect* mNext;
+  };
+
+  void BaseInit(const nsIntPoint& aDelta, ScrollRect* aHead);
+
+private:
+  void Flip(const nsIntPoint& aDelta)
+  {
+    for (ScrollRect* r = mHead; r; r = r->mNext) {
+      r->Flip(aDelta);
+    }
+  }
+
+  /**
+   * Comparator for an initial sort of the rectangles.  The rectangles are
+   * primarily sorted in increasing y, which is required for the algorithm.
+   * The secondary sort is in decreasing x, chosen to make Move() more
+   * efficient for rows of rectangles with equal y.
+   */
+  class InitialSortComparator {
+  public:
+    PRBool Equals(const ScrollRect* a, const ScrollRect* b) const
+    {
+      return a->y == b->y && a->x == b->x;
+    }
+    PRBool LessThan(const ScrollRect* a, const ScrollRect* b) const
+    {
+      return a->y < b->y || (a->y == b->y && a->x > b->x);
+    }
+  };
+
+  void Move(ScrollRect** aUnmovedLink);
+
+  // Linked list of rectangles; these are assumed owned by the derived class
+  ScrollRect* mHead;
+  // Used in sorting to point to the last mNext link in the moved chain.
+  ScrollRect** mTailLink;
+};
+
+class BlitRectIter : public ScrollRectIterBase {
+public:
+  BlitRectIter(const nsIntPoint& aDelta, const nsTArray<nsIntRect>& aRects);
+private:
+  // Copying is not supported.
+  BlitRectIter(const BlitRectIter&);
+  void operator=(const BlitRectIter&);
+
+  nsTArray<ScrollRect> mRects;
+};
+
 #endif // nsBaseWidget_h__