diff -r 000000000000 -r 6474c204b198 layout/generic/nsFloatManager.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/layout/generic/nsFloatManager.cpp	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,557 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* class that manages rules for positioning floats */
+
+#include "nsFloatManager.h"
+#include "nsIPresShell.h"
+#include "nsMemory.h"
+#include "nsHTMLReflowState.h"
+#include "nsBlockDebugFlags.h"
+#include "nsError.h"
+#include <algorithm>
+
+using namespace mozilla;
+
+int32_t nsFloatManager::sCachedFloatManagerCount = 0;
+void* nsFloatManager::sCachedFloatManagers[NS_FLOAT_MANAGER_CACHE_SIZE];
+
+/////////////////////////////////////////////////////////////////////////////
+
+// PresShell Arena allocate callback (for nsIntervalSet use below)
+static void*
+PSArenaAllocCB(size_t aSize, void* aClosure)
+{
+  return static_cast<nsIPresShell*>(aClosure)->AllocateMisc(aSize);
+}
+
+// PresShell Arena free callback (for nsIntervalSet use below)
+static void
+PSArenaFreeCB(size_t aSize, void* aPtr, void* aClosure)
+{
+  static_cast<nsIPresShell*>(aClosure)->FreeMisc(aSize, aPtr);
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// nsFloatManager
+
+nsFloatManager::nsFloatManager(nsIPresShell* aPresShell)
+  : mX(0), mY(0),
+    mFloatDamage(PSArenaAllocCB, PSArenaFreeCB, aPresShell),
+    mPushedLeftFloatPastBreak(false),
+    mPushedRightFloatPastBreak(false),
+    mSplitLeftFloatAcrossBreak(false),
+    mSplitRightFloatAcrossBreak(false)
+{
+  MOZ_COUNT_CTOR(nsFloatManager);
+}
+
+nsFloatManager::~nsFloatManager()
+{
+  MOZ_COUNT_DTOR(nsFloatManager);
+}
+
+// static
+void* nsFloatManager::operator new(size_t aSize) CPP_THROW_NEW
+{
+  if (sCachedFloatManagerCount > 0) {
+    // We have cached unused instances of this class, return a cached
+    // instance in stead of always creating a new one.
+    return sCachedFloatManagers[--sCachedFloatManagerCount];
+  }
+
+  // The cache is empty, this means we haveto create a new instance using
+  // the global |operator new|.
+  return nsMemory::Alloc(aSize);
+}
+
+void
+nsFloatManager::operator delete(void* aPtr, size_t aSize)
+{
+  if (!aPtr)
+    return;
+  // This float manager is no longer used, if there's still room in
+  // the cache we'll cache this float manager, unless the layout
+  // module was already shut down.
+
+  if (sCachedFloatManagerCount < NS_FLOAT_MANAGER_CACHE_SIZE &&
+      sCachedFloatManagerCount >= 0) {
+    // There's still space in the cache for more instances, put this
+    // instance in the cache in stead of deleting it.
+
+    sCachedFloatManagers[sCachedFloatManagerCount++] = aPtr;
+    return;
+  }
+
+  // The cache is full, or the layout module has been shut down,
+  // delete this float manager.
+  nsMemory::Free(aPtr);
+}
+
+
+/* static */
+void nsFloatManager::Shutdown()
+{
+  // The layout module is being shut down, clean up the cache and
+  // disable further caching.
+
+  int32_t i;
+
+  for (i = 0; i < sCachedFloatManagerCount; i++) {
+    void* floatManager = sCachedFloatManagers[i];
+    if (floatManager)
+      nsMemory::Free(floatManager);
+  }
+
+  // Disable further caching.
+  sCachedFloatManagerCount = -1;
+}
+
+nsFlowAreaRect
+nsFloatManager::GetFlowArea(nscoord aYOffset, BandInfoType aInfoType,
+                            nscoord aHeight, nsRect aContentArea,
+                            SavedState* aState) const
+{
+  NS_ASSERTION(aHeight >= 0, "unexpected max height");
+  NS_ASSERTION(aContentArea.width >= 0, "unexpected content area width");
+
+  nscoord top = aYOffset + mY;
+  if (top < nscoord_MIN) {
+    NS_WARNING("bad value");
+    top = nscoord_MIN;
+  }
+
+  // Determine the last float that we should consider.
+  uint32_t floatCount;
+  if (aState) {
+    // Use the provided state.
+    floatCount = aState->mFloatInfoCount;
+    NS_ABORT_IF_FALSE(floatCount <= mFloats.Length(), "bad state");
+  } else {
+    // Use our current state.
+    floatCount = mFloats.Length();
+  }
+
+  // If there are no floats at all, or we're below the last one, return
+  // quickly.
+  if (floatCount == 0 ||
+      (mFloats[floatCount-1].mLeftYMost <= top &&
+       mFloats[floatCount-1].mRightYMost <= top)) {
+    return nsFlowAreaRect(aContentArea.x, aYOffset, aContentArea.width,
+                          aHeight, false);
+  }
+
+  nscoord bottom;
+  if (aHeight == nscoord_MAX) {
+    // This warning (and the two below) are possible to hit on pages
+    // with really large objects.
+    NS_WARN_IF_FALSE(aInfoType == BAND_FROM_POINT,
+                     "bad height");
+    bottom = nscoord_MAX;
+  } else {
+    bottom = top + aHeight;
+    if (bottom < top || bottom > nscoord_MAX) {
+      NS_WARNING("bad value");
+      bottom = nscoord_MAX;
+    }
+  }
+  nscoord left = mX + aContentArea.x;
+  nscoord right = mX + aContentArea.XMost();
+  if (right < left) {
+    NS_WARNING("bad value");
+    right = left;
+  }
+
+  // Walk backwards through the floats until we either hit the front of
+  // the list or we're above |top|.
+  bool haveFloats = false;
+  for (uint32_t i = floatCount; i > 0; --i) {
+    const FloatInfo &fi = mFloats[i-1];
+    if (fi.mLeftYMost <= top && fi.mRightYMost <= top) {
+      // There aren't any more floats that could intersect this band.
+      break;
+    }
+    if (fi.mRect.IsEmpty()) {
+      // For compatibility, ignore floats with empty rects, even though it
+      // disagrees with the spec.  (We might want to fix this in the
+      // future, though.)
+      continue;
+    }
+    nscoord floatTop = fi.mRect.y, floatBottom = fi.mRect.YMost();
+    if (top < floatTop && aInfoType == BAND_FROM_POINT) {
+      // This float is below our band.  Shrink our band's height if needed.
+      if (floatTop < bottom) {
+        bottom = floatTop;
+      }
+    }
+    // If top == bottom (which happens only with WIDTH_WITHIN_HEIGHT),
+    // we include floats that begin at our 0-height vertical area.  We
+    // need to to this to satisfy the invariant that a
+    // WIDTH_WITHIN_HEIGHT call is at least as narrow on both sides as a
+    // BAND_WITHIN_POINT call beginning at its top.
+    else if (top < floatBottom &&
+             (floatTop < bottom || (floatTop == bottom && top == bottom))) {
+      // This float is in our band.
+
+      // Shrink our band's height if needed.
+      if (floatBottom < bottom && aInfoType == BAND_FROM_POINT) {
+        bottom = floatBottom;
+      }
+
+      // Shrink our band's width if needed.
+      if (fi.mFrame->StyleDisplay()->mFloats == NS_STYLE_FLOAT_LEFT) {
+        // A left float.
+        nscoord rightEdge = fi.mRect.XMost();
+        if (rightEdge > left) {
+          left = rightEdge;
+          // Only set haveFloats to true if the float is inside our
+          // containing block.  This matches the spec for what some
+          // callers want and disagrees for other callers, so we should
+          // probably provide better information at some point.
+          haveFloats = true;
+        }
+      } else {
+        // A right float.
+        nscoord leftEdge = fi.mRect.x;
+        if (leftEdge < right) {
+          right = leftEdge;
+          // See above.
+          haveFloats = true;
+        }
+      }
+    }
+  }
+
+  nscoord height = (bottom == nscoord_MAX) ? nscoord_MAX : (bottom - top);
+  return nsFlowAreaRect(left - mX, top - mY, right - left, height, haveFloats);
+}
+
+nsresult
+nsFloatManager::AddFloat(nsIFrame* aFloatFrame, const nsRect& aMarginRect)
+{
+  NS_ASSERTION(aMarginRect.width >= 0, "negative width!");
+  NS_ASSERTION(aMarginRect.height >= 0, "negative height!");
+
+  FloatInfo info(aFloatFrame, aMarginRect + nsPoint(mX, mY));
+
+  // Set mLeftYMost and mRightYMost.
+  if (HasAnyFloats()) {
+    FloatInfo &tail = mFloats[mFloats.Length() - 1];
+    info.mLeftYMost = tail.mLeftYMost;
+    info.mRightYMost = tail.mRightYMost;
+  } else {
+    info.mLeftYMost = nscoord_MIN;
+    info.mRightYMost = nscoord_MIN;
+  }
+  uint8_t floatStyle = aFloatFrame->StyleDisplay()->mFloats;
+  NS_ASSERTION(floatStyle == NS_STYLE_FLOAT_LEFT ||
+               floatStyle == NS_STYLE_FLOAT_RIGHT, "unexpected float");
+  nscoord& sideYMost = (floatStyle == NS_STYLE_FLOAT_LEFT) ? info.mLeftYMost
+                                                           : info.mRightYMost;
+  nscoord thisYMost = info.mRect.YMost();
+  if (thisYMost > sideYMost)
+    sideYMost = thisYMost;
+
+  if (!mFloats.AppendElement(info))
+    return NS_ERROR_OUT_OF_MEMORY;
+
+  return NS_OK;
+}
+
+nsRect
+nsFloatManager::CalculateRegionFor(nsIFrame*       aFloat,
+                                   const nsMargin& aMargin)
+{
+  // We consider relatively positioned frames at their original position.
+  nsRect region(aFloat->GetNormalPosition(), aFloat->GetSize());
+
+  // Float region includes its margin
+  region.Inflate(aMargin);
+
+  // Don't store rectangles with negative margin-box width or height in
+  // the float manager; it can't deal with them.
+  if (region.width < 0) {
+    // Preserve the right margin-edge for left floats and the left
+    // margin-edge for right floats
+    const nsStyleDisplay* display = aFloat->StyleDisplay();
+    if (NS_STYLE_FLOAT_LEFT == display->mFloats) {
+      region.x = region.XMost();
+    }
+    region.width = 0;
+  }
+  if (region.height < 0) {
+    region.height = 0;
+  }
+  return region;
+}
+
+NS_DECLARE_FRAME_PROPERTY(FloatRegionProperty, nsIFrame::DestroyMargin)
+
+nsRect
+nsFloatManager::GetRegionFor(nsIFrame* aFloat)
+{
+  nsRect region = aFloat->GetRect();
+  void* storedRegion = aFloat->Properties().Get(FloatRegionProperty());
+  if (storedRegion) {
+    nsMargin margin = *static_cast<nsMargin*>(storedRegion);
+    region.Inflate(margin);
+  }
+  return region;
+}
+
+void
+nsFloatManager::StoreRegionFor(nsIFrame* aFloat,
+                               nsRect&   aRegion)
+{
+  nsRect rect = aFloat->GetRect();
+  FrameProperties props = aFloat->Properties();
+  if (aRegion.IsEqualEdges(rect)) {
+    props.Delete(FloatRegionProperty());
+  }
+  else {
+    nsMargin* storedMargin = static_cast<nsMargin*>
+      (props.Get(FloatRegionProperty()));
+    if (!storedMargin) {
+      storedMargin = new nsMargin();
+      props.Set(FloatRegionProperty(), storedMargin);
+    }
+    *storedMargin = aRegion - rect;
+  }
+}
+
+nsresult
+nsFloatManager::RemoveTrailingRegions(nsIFrame* aFrameList)
+{
+  if (!aFrameList) {
+    return NS_OK;
+  }
+  // This could be a good bit simpler if we could guarantee that the
+  // floats given were at the end of our list, so we could just search
+  // for the head of aFrameList.  (But we can't;
+  // layout/reftests/bugs/421710-1.html crashes.)
+  nsTHashtable<nsPtrHashKey<nsIFrame> > frameSet(1);
+
+  for (nsIFrame* f = aFrameList; f; f = f->GetNextSibling()) {
+    frameSet.PutEntry(f);
+  }
+
+  uint32_t newLength = mFloats.Length();
+  while (newLength > 0) {
+    if (!frameSet.Contains(mFloats[newLength - 1].mFrame)) {
+      break;
+    }
+    --newLength;
+  }
+  mFloats.TruncateLength(newLength);
+
+#ifdef DEBUG
+  for (uint32_t i = 0; i < mFloats.Length(); ++i) {
+    NS_ASSERTION(!frameSet.Contains(mFloats[i].mFrame),
+                 "Frame region deletion was requested but we couldn't delete it");
+  }
+#endif
+
+  return NS_OK;
+}
+
+void
+nsFloatManager::PushState(SavedState* aState)
+{
+  NS_PRECONDITION(aState, "Need a place to save state");
+
+  // This is a cheap push implementation, which
+  // only saves the (x,y) and last frame in the mFrameInfoMap
+  // which is enough info to get us back to where we should be
+  // when pop is called.
+  //
+  // This push/pop mechanism is used to undo any
+  // floats that were added during the unconstrained reflow
+  // in nsBlockReflowContext::DoReflowBlock(). (See bug 96736)
+  //
+  // It should also be noted that the state for mFloatDamage is
+  // intentionally not saved or restored in PushState() and PopState(),
+  // since that could lead to bugs where damage is missed/dropped when
+  // we move from position A to B (during the intermediate incremental
+  // reflow mentioned above) and then from B to C during the subsequent
+  // reflow. In the typical case A and C will be the same, but not always.
+  // Allowing mFloatDamage to accumulate the damage incurred during both
+  // reflows ensures that nothing gets missed.
+  aState->mX = mX;
+  aState->mY = mY;
+  aState->mPushedLeftFloatPastBreak = mPushedLeftFloatPastBreak;
+  aState->mPushedRightFloatPastBreak = mPushedRightFloatPastBreak;
+  aState->mSplitLeftFloatAcrossBreak = mSplitLeftFloatAcrossBreak;
+  aState->mSplitRightFloatAcrossBreak = mSplitRightFloatAcrossBreak;
+  aState->mFloatInfoCount = mFloats.Length();
+}
+
+void
+nsFloatManager::PopState(SavedState* aState)
+{
+  NS_PRECONDITION(aState, "No state to restore?");
+
+  mX = aState->mX;
+  mY = aState->mY;
+  mPushedLeftFloatPastBreak = aState->mPushedLeftFloatPastBreak;
+  mPushedRightFloatPastBreak = aState->mPushedRightFloatPastBreak;
+  mSplitLeftFloatAcrossBreak = aState->mSplitLeftFloatAcrossBreak;
+  mSplitRightFloatAcrossBreak = aState->mSplitRightFloatAcrossBreak;
+
+  NS_ASSERTION(aState->mFloatInfoCount <= mFloats.Length(),
+               "somebody misused PushState/PopState");
+  mFloats.TruncateLength(aState->mFloatInfoCount);
+}
+
+nscoord
+nsFloatManager::GetLowestFloatTop() const
+{
+  if (mPushedLeftFloatPastBreak || mPushedRightFloatPastBreak) {
+    return nscoord_MAX;
+  }
+  if (!HasAnyFloats()) {
+    return nscoord_MIN;
+  }
+  return mFloats[mFloats.Length() - 1].mRect.y - mY;
+}
+
+#ifdef DEBUG_FRAME_DUMP
+void
+DebugListFloatManager(const nsFloatManager *aFloatManager)
+{
+  aFloatManager->List(stdout);
+}
+
+nsresult
+nsFloatManager::List(FILE* out) const
+{
+  if (!HasAnyFloats())
+    return NS_OK;
+
+  for (uint32_t i = 0; i < mFloats.Length(); ++i) {
+    const FloatInfo &fi = mFloats[i];
+    fprintf_stderr(out, "Float %u: frame=%p rect={%d,%d,%d,%d} ymost={l:%d, r:%d}\n",
+                   i, static_cast<void*>(fi.mFrame),
+                   fi.mRect.x, fi.mRect.y, fi.mRect.width, fi.mRect.height,
+                   fi.mLeftYMost, fi.mRightYMost);
+  }
+  return NS_OK;
+}
+#endif
+
+nscoord
+nsFloatManager::ClearFloats(nscoord aY, uint8_t aBreakType,
+                            uint32_t aFlags) const
+{
+  if (!(aFlags & DONT_CLEAR_PUSHED_FLOATS) && ClearContinues(aBreakType)) {
+    return nscoord_MAX;
+  }
+  if (!HasAnyFloats()) {
+    return aY;
+  }
+
+  nscoord bottom = aY + mY;
+
+  const FloatInfo &tail = mFloats[mFloats.Length() - 1];
+  switch (aBreakType) {
+    case NS_STYLE_CLEAR_BOTH:
+      bottom = std::max(bottom, tail.mLeftYMost);
+      bottom = std::max(bottom, tail.mRightYMost);
+      break;
+    case NS_STYLE_CLEAR_LEFT:
+      bottom = std::max(bottom, tail.mLeftYMost);
+      break;
+    case NS_STYLE_CLEAR_RIGHT:
+      bottom = std::max(bottom, tail.mRightYMost);
+      break;
+    default:
+      // Do nothing
+      break;
+  }
+
+  bottom -= mY;
+
+  return bottom;
+}
+
+bool
+nsFloatManager::ClearContinues(uint8_t aBreakType) const
+{
+  return ((mPushedLeftFloatPastBreak || mSplitLeftFloatAcrossBreak) &&
+          (aBreakType == NS_STYLE_CLEAR_BOTH ||
+           aBreakType == NS_STYLE_CLEAR_LEFT)) ||
+         ((mPushedRightFloatPastBreak || mSplitRightFloatAcrossBreak) &&
+          (aBreakType == NS_STYLE_CLEAR_BOTH ||
+           aBreakType == NS_STYLE_CLEAR_RIGHT));
+}
+
+/////////////////////////////////////////////////////////////////////////////
+// FloatInfo
+
+nsFloatManager::FloatInfo::FloatInfo(nsIFrame* aFrame, const nsRect& aRect)
+  : mFrame(aFrame), mRect(aRect)
+{
+  MOZ_COUNT_CTOR(nsFloatManager::FloatInfo);
+}
+
+#ifdef NS_BUILD_REFCNT_LOGGING
+nsFloatManager::FloatInfo::FloatInfo(const FloatInfo& aOther)
+  : mFrame(aOther.mFrame),
+    mRect(aOther.mRect),
+    mLeftYMost(aOther.mLeftYMost),
+    mRightYMost(aOther.mRightYMost)
+{
+  MOZ_COUNT_CTOR(nsFloatManager::FloatInfo);
+}
+
+nsFloatManager::FloatInfo::~FloatInfo()
+{
+  MOZ_COUNT_DTOR(nsFloatManager::FloatInfo);
+}
+#endif
+
+//----------------------------------------------------------------------
+
+nsAutoFloatManager::~nsAutoFloatManager()
+{
+  // Restore the old float manager in the reflow state if necessary.
+  if (mNew) {
+#ifdef NOISY_FLOATMANAGER
+    printf("restoring old float manager %p\n", mOld);
+#endif
+
+    mReflowState.mFloatManager = mOld;
+
+#ifdef NOISY_FLOATMANAGER
+    if (mOld) {
+      static_cast<nsFrame *>(mReflowState.frame)->ListTag(stdout);
+      printf(": space-manager %p after reflow\n", mOld);
+      mOld->List(stdout);
+    }
+#endif
+
+    delete mNew;
+  }
+}
+
+nsresult
+nsAutoFloatManager::CreateFloatManager(nsPresContext *aPresContext)
+{
+  // Create a new float manager and install it in the reflow
+  // state. `Remember' the old float manager so we can restore it
+  // later.
+  mNew = new nsFloatManager(aPresContext->PresShell());
+  if (! mNew)
+    return NS_ERROR_OUT_OF_MEMORY;
+
+#ifdef NOISY_FLOATMANAGER
+  printf("constructed new float manager %p (replacing %p)\n",
+         mNew, mReflowState.mFloatManager);
+#endif
+
+  // Set the float manager in the existing reflow state
+  mOld = mReflowState.mFloatManager;
+  mReflowState.mFloatManager = mNew;
+  return NS_OK;
+}