layout/base/nsLayoutUtils.cpp
author Emilio Cobos Álvarez <emilio@crisal.io>
Mon, 26 Nov 2018 09:21:37 +0000
changeset 504393 8e88421b280c2afda62f4ba704ce29701c30549f
parent 504376 14d532b8d89432c1a4b01d5007960295a13022da
child 504743 c8141cbb7ede93f9111de7dec9e0bf9a7e984bd2
permissions -rw-r--r--
Bug 1506547 - Align user-select behavior more with other UAs. r=mats There's a few subtle behavior changes here, which I'll try to break down in the commit message. The biggest one is the EditableDescendantCount stuff going away. This was added in bug 1181130, to prevent clicking on the non-editable div from selecting the editable div inside. This is problematic for multiple reasons: * First, I don't think non-editable regions of an editable element should be user-select: all. * Second, it just doesn't work in Shadow DOM (the editable descendant count is not kept up-to-date when not in the uncomposed doc), so nested contenteditables behave differently inside vs. outside a Shadow Tree. * Third, I think it's user hostile to just entirely disable selection if you have a contenteditable descendant as a child of a user-select: all thing. WebKit behaves like this patch in the following test-case (though not Blink): https://crisal.io/tmp/user-select-all-contenteditable-descendant.html Edge doesn't seem to support user-select: all at all (no pun intended). But we don't allow to select anything at all which looks wrong. * Fourth, it's not tested at all (which explains how we broke it in Shadow DOM and not even notice...). In any case I've verified that this doesn't regress the editor from that bug. If this regresses anything we can fix it as outlined in the first bullet point above, which should also make us more compatible with other UAs in that test-case. The other change is `all` not overriding everything else. So, something like: <div style="-webkit-user-select: all">All <div style="-webkit-user-select: none">None</div></div> Totally ignores the -webkit-user-select: none declaration in Firefox before this change. This doesn't match any other UA nor the spec, and this patch aligns us with WebKit / Blink. This in turn makes us not need -moz-text anymore, whose only purpose was to avoid this. This also fixes a variety of bugs uncovered by the previous changes, like the SetIgnoreUserModify(false) call in editor being completely useless, since presShell->SetCaretEnabled ended in nsCaret::SetVisible, which overrode it. This in turn uncovered even more bugs, from bugs in the caret painting code, like not checking -moz-user-modify on the right frame if you're the last frame of a line, to even funnier bits where before this patch you show the caret but can't write at all... In any case, the new setup I came up with is that when you're editing (the selection is focused on an editable node) moving the caret forces it to end up in an editable node, thus jumping over non-editable ones. This has the nice effect of not completely disabling selection of -moz-user-select: all elements that have editable descendants (which was a very ad-hoc hack for bug 1181130, and somewhat broken per the above), and also not needing the -moz-user-select: all for non-editable bits in contenteditable.css at all. This also fixes issues with br-skipping like not being able to insert content in the following test-case: <div contenteditable="true"><span contenteditable="false">xyz </span><br>editable</div> If you start moving to the left from the second line, for example. I think this yields way better behavior in all the relevant test-cases from bug 1181130 / bug 1109968 / bug 1132768, shouldn't cause any regression, and the complexity is significantly reduced in some places. There's still some other broken bits that this patch doesn't fix, but I'll file follow-ups for those. Differential Revision: https://phabricator.services.mozilla.com/D12687

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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/. */

#include "nsLayoutUtils.h"

#include "mozilla/ArrayUtils.h"
#include "mozilla/BasicEvents.h"
#include "mozilla/ClearOnShutdown.h"
#include "mozilla/EffectCompositor.h"
#include "mozilla/EffectSet.h"
#include "mozilla/EventDispatcher.h"
#include "mozilla/EventStateManager.h"
#include "mozilla/FloatingPoint.h"
#include "mozilla/gfx/gfxVars.h"
#include "mozilla/gfx/PathHelpers.h"
#include "mozilla/layers/PAPZ.h"
#include "mozilla/Likely.h"
#include "mozilla/Maybe.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/dom/ContentChild.h"
#include "mozilla/ServoStyleSetInlines.h"
#include "mozilla/StaticPrefs.h"
#include "mozilla/Unused.h"
#include "nsCharTraits.h"
#include "nsDocument.h"
#include "nsFontMetrics.h"
#include "nsPresContext.h"
#include "nsIContent.h"
#include "nsFrameList.h"
#include "nsGenericHTMLElement.h"
#include "nsGkAtoms.h"
#include "nsAtom.h"
#include "nsCaret.h"
#include "nsCSSPseudoElements.h"
#include "nsCSSAnonBoxes.h"
#include "nsCSSColorUtils.h"
#include "nsView.h"
#include "nsViewManager.h"
#include "nsPlaceholderFrame.h"
#include "nsIScrollableFrame.h"
#include "nsSubDocumentFrame.h"
#include "nsDisplayList.h"
#include "nsRegion.h"
#include "nsCSSFrameConstructor.h"
#include "nsBlockFrame.h"
#include "nsBidiPresUtils.h"
#include "imgIContainer.h"
#include "ImageOps.h"
#include "ImageRegion.h"
#include "gfxRect.h"
#include "gfxContext.h"
#include "gfxContext.h"
#include "nsIInterfaceRequestorUtils.h"
#include "nsCSSRendering.h"
#include "nsTextFragment.h"
#include "nsStyleConsts.h"
#include "nsPIDOMWindow.h"
#include "nsIDocShell.h"
#include "nsIWidget.h"
#include "gfxMatrix.h"
#include "gfxPrefs.h"
#include "gfxTypes.h"
#include "nsTArray.h"
#include "mozilla/dom/HTMLCanvasElement.h"
#include "nsICanvasRenderingContextInternal.h"
#include "gfxPlatform.h"
#include <algorithm>
#include <limits>
#include "mozilla/dom/AnonymousContent.h"
#include "mozilla/dom/HTMLBodyElement.h"
#include "mozilla/dom/HTMLMediaElementBinding.h"
#include "mozilla/dom/HTMLVideoElement.h"
#include "mozilla/dom/HTMLImageElement.h"
#include "mozilla/dom/DOMRect.h"
#include "mozilla/dom/DOMStringList.h"
#include "mozilla/dom/KeyframeEffect.h"
#include "mozilla/dom/SVGPathData.h"
#include "mozilla/layers/APZCCallbackHelper.h"
#include "imgIRequest.h"
#include "nsIImageLoadingContent.h"
#include "nsCOMPtr.h"
#include "nsCSSProps.h"
#include "nsListControlFrame.h"
#include "mozilla/dom/Element.h"
#include "nsCanvasFrame.h"
#include "gfxDrawable.h"
#include "gfxEnv.h"
#include "gfxUtils.h"
#include "nsDataHashtable.h"
#include "nsTableWrapperFrame.h"
#include "nsTextFrame.h"
#include "nsFontInflationData.h"
#include "nsSVGIntegrationUtils.h"
#include "nsSVGUtils.h"
#include "SVGImageContext.h"
#include "SVGTextFrame.h"
#include "nsStyleStructInlines.h"
#include "nsStyleTransformMatrix.h"
#include "nsIFrameInlines.h"
#include "ImageContainer.h"
#include "nsComputedDOMStyle.h"
#include "ActiveLayerTracker.h"
#include "mozilla/gfx/2D.h"
#include "gfx2DGlue.h"
#include "mozilla/LookAndFeel.h"
#include "UnitTransforms.h"
#include "TiledLayerBuffer.h" // For TILEDLAYERBUFFER_TILE_SIZE
#include "ClientLayerManager.h"
#include "nsRefreshDriver.h"
#include "nsIContentViewer.h"
#include "LayersLogging.h"
#include "mozilla/Preferences.h"
#include "nsFrameSelection.h"
#include "FrameLayerBuilder.h"
#include "mozilla/layers/APZUtils.h"    // for apz::CalculatePendingDisplayPort
#include "mozilla/layers/CompositorBridgeChild.h"
#include "mozilla/Telemetry.h"
#include "mozilla/EventDispatcher.h"
#include "mozilla/StyleAnimationValue.h"
#include "mozilla/ServoStyleSet.h"
#include "mozilla/WheelHandlingHelper.h" // for WheelHandlingUtils
#include "RegionBuilder.h"
#include "SVGViewportElement.h"
#include "DisplayItemClip.h"
#include "mozilla/layers/StackingContextHelper.h"
#include "mozilla/layers/WebRenderLayerManager.h"
#include "prenv.h"
#include "RetainedDisplayListBuilder.h"
#include "DisplayListChecker.h"
#include "TextDrawTarget.h"
#include "nsDeckFrame.h"
#include "mozilla/dom/InspectorFontFace.h"

#ifdef MOZ_XUL
#include "nsXULPopupManager.h"
#endif

#include "GeckoProfiler.h"
#include "nsAnimationManager.h"
#include "nsTransitionManager.h"
#include "mozilla/RestyleManager.h"
#include "LayoutLogging.h"

// Make sure getpid() works.
#ifdef XP_WIN
#include <process.h>
#define getpid _getpid
#else
#include <unistd.h>
#endif

using namespace mozilla;
using namespace mozilla::dom;
using namespace mozilla::image;
using namespace mozilla::layers;
using namespace mozilla::layout;
using namespace mozilla::gfx;
using mozilla::dom::HTMLMediaElement_Binding::HAVE_NOTHING;
using mozilla::dom::HTMLMediaElement_Binding::HAVE_METADATA;

#define INTERCHARACTER_RUBY_ENABLED_PREF_NAME "layout.css.ruby.intercharacter.enabled"
#define CONTENT_SELECT_ENABLED_PREF_NAME "dom.select_popup_in_content.enabled"

// The time in number of frames that we estimate for a refresh driver
// to be quiescent
#define DEFAULT_QUIESCENT_FRAMES 2
// The time (milliseconds) we estimate is needed between the end of an
// idle time and the next Tick.
#define DEFAULT_IDLE_PERIOD_TIME_LIMIT 1.0f

#ifdef DEBUG
// TODO: remove, see bug 598468.
bool nsLayoutUtils::gPreventAssertInCompareTreePosition = false;
#endif // DEBUG

typedef ScrollableLayerGuid::ViewID ViewID;
typedef nsStyleTransformMatrix::TransformReferenceBox TransformReferenceBox;

/* static */ uint32_t nsLayoutUtils::sFontSizeInflationEmPerLine;
/* static */ uint32_t nsLayoutUtils::sFontSizeInflationMinTwips;
/* static */ uint32_t nsLayoutUtils::sFontSizeInflationLineThreshold;
/* static */ int32_t  nsLayoutUtils::sFontSizeInflationMappingIntercept;
/* static */ uint32_t nsLayoutUtils::sFontSizeInflationMaxRatio;
/* static */ bool nsLayoutUtils::sFontSizeInflationForceEnabled;
/* static */ bool nsLayoutUtils::sFontSizeInflationDisabledInMasterProcess;
/* static */ uint32_t nsLayoutUtils::sSystemFontScale;
/* static */ uint32_t nsLayoutUtils::sZoomMaxPercent;
/* static */ uint32_t nsLayoutUtils::sZoomMinPercent;
/* static */ bool nsLayoutUtils::sInvalidationDebuggingIsEnabled;
/* static */ bool nsLayoutUtils::sInterruptibleReflowEnabled;
/* static */ bool nsLayoutUtils::sSVGTransformBoxEnabled;
/* static */ uint32_t nsLayoutUtils::sIdlePeriodDeadlineLimit;
/* static */ uint32_t nsLayoutUtils::sQuiescentFramesBeforeIdlePeriod;

static ViewID sScrollIdCounter = ScrollableLayerGuid::START_SCROLL_ID;

typedef nsDataHashtable<nsUint64HashKey, nsIContent*> ContentMap;
static ContentMap* sContentMap = nullptr;
static ContentMap& GetContentMap() {
  if (!sContentMap) {
    sContentMap = new ContentMap();
  }
  return *sContentMap;
}

template<typename TestType>
static bool
HasMatchingAnimations(EffectSet* aEffects, TestType&& aTest)
{
  for (KeyframeEffect* effect : *aEffects) {
    if (aTest(*effect)) {
      return true;
    }
  }

  return false;
}

template<typename TestType>
static bool
HasMatchingAnimations(const nsIFrame* aFrame, TestType&& aTest)
{
  EffectSet* effects = EffectSet::GetEffectSet(aFrame);
  if (!effects) {
    return false;
  }

  return HasMatchingAnimations(effects, aTest);
}

bool
nsLayoutUtils::HasCurrentTransitions(const nsIFrame* aFrame)
{
  return HasMatchingAnimations(aFrame,
    [](KeyframeEffect& aEffect)
    {
      // Since |aEffect| is current, it must have an associated Animation
      // so we don't need to null-check the result of GetAnimation().
      return aEffect.IsCurrent() && aEffect.GetAnimation()->AsCSSTransition();
    }
  );
}

static bool
MayHaveAnimationOfProperty(EffectSet* effects, nsCSSPropertyID aProperty)
{
  MOZ_ASSERT(effects);

  if (aProperty == eCSSProperty_transform &&
      !effects->MayHaveTransformAnimation()) {
    return false;
  }
  if (aProperty == eCSSProperty_opacity &&
      !effects->MayHaveOpacityAnimation()) {
    return false;
  }

  return true;
}

static bool
MayHaveAnimationOfProperty(const nsIFrame* aFrame, nsCSSPropertyID aProperty)
{
  switch (aProperty) {
    case eCSSProperty_transform:
      return aFrame->MayHaveTransformAnimation();
    case eCSSProperty_opacity:
      return aFrame->MayHaveOpacityAnimation();
    default:
      MOZ_ASSERT_UNREACHABLE("unexpected property");
      return false;
  }
}

bool
nsLayoutUtils::HasAnimationOfProperty(EffectSet* aEffectSet,
                                      nsCSSPropertyID aProperty)
{
  if (!aEffectSet || !MayHaveAnimationOfProperty(aEffectSet, aProperty)) {
    return false;
  }

  return HasMatchingAnimations(aEffectSet,
    [&aProperty](KeyframeEffect& aEffect)
    {
      return (aEffect.IsInEffect() || aEffect.IsCurrent()) &&
             aEffect.HasAnimationOfProperty(aProperty);
    }
  );
}

bool
nsLayoutUtils::HasAnimationOfProperty(const nsIFrame* aFrame,
                                      nsCSSPropertyID aProperty)
{
  if (!MayHaveAnimationOfProperty(aFrame, aProperty)) {
    return false;
  }

  return HasMatchingAnimations(aFrame,
    [&aProperty](KeyframeEffect& aEffect)
    {
      return (aEffect.IsInEffect() || aEffect.IsCurrent()) &&
             aEffect.HasAnimationOfProperty(aProperty);
    }
  );

}

bool
nsLayoutUtils::HasEffectiveAnimation(const nsIFrame* aFrame,
                                     nsCSSPropertyID aProperty)
{
  EffectSet* effects = EffectSet::GetEffectSet(aFrame);
  if (!effects || !MayHaveAnimationOfProperty(effects, aProperty)) {
    return false;
  }


  return HasMatchingAnimations(effects,
    [&aProperty, &effects](KeyframeEffect& aEffect)
    {
      return (aEffect.IsInEffect() || aEffect.IsCurrent()) &&
             aEffect.HasEffectiveAnimationOfProperty(aProperty, *effects);
    }
  );
}

/* static */ nsCSSPropertyIDSet
nsLayoutUtils::GetAnimationPropertiesForCompositor(const nsIFrame* aFrame)
{
  nsCSSPropertyIDSet properties;

  EffectSet* effects = EffectSet::GetEffectSet(aFrame);
  if (!effects) {
    return properties;
  }

  AnimationPerformanceWarning::Type warning;
  if (!EffectCompositor::AllowCompositorAnimationsOnFrame(aFrame,
                                                          *effects,
                                                          warning)) {
    return properties;
  }

  for (const KeyframeEffect* effect : *effects) {
    properties |= effect->GetPropertiesForCompositor(*effects, aFrame);
  }

  return properties;
}

static float
GetSuitableScale(float aMaxScale, float aMinScale,
                 nscoord aVisibleDimension, nscoord aDisplayDimension)
{
  float displayVisibleRatio = float(aDisplayDimension) /
                              float(aVisibleDimension);
  // We want to rasterize based on the largest scale used during the
  // transform animation, unless that would make us rasterize something
  // larger than the screen.  But we never want to go smaller than the
  // minimum scale over the animation.
  if (FuzzyEqualsMultiplicative(displayVisibleRatio, aMaxScale, .01f)) {
    // Using aMaxScale may make us rasterize something a fraction larger than
    // the screen. However, if aMaxScale happens to be the final scale of a
    // transform animation it is better to use aMaxScale so that for the
    // fraction of a second before we delayerize the composited texture it has
    // a better chance of being pixel aligned and composited without resampling
    // (avoiding visually clunky delayerization).
    return aMaxScale;
  }
  return std::max(std::min(aMaxScale, displayVisibleRatio), aMinScale);
}

static inline void
UpdateMinMaxScale(const nsIFrame* aFrame,
                  const AnimationValue& aValue,
                  Size& aMinScale,
                  Size& aMaxScale)
{
  Size size = aValue.GetScaleValue(aFrame);
  aMaxScale.width = std::max<float>(aMaxScale.width, size.width);
  aMaxScale.height = std::max<float>(aMaxScale.height, size.height);
  aMinScale.width = std::min<float>(aMinScale.width, size.width);
  aMinScale.height = std::min<float>(aMinScale.height, size.height);
}

static void
GetMinAndMaxScaleForAnimationProperty(const nsIFrame* aFrame,
                                      nsTArray<RefPtr<dom::Animation>>& aAnimations,
                                      Size& aMaxScale,
                                      Size& aMinScale)
{
  for (dom::Animation* anim : aAnimations) {
    // This method is only expected to be passed animations that are running on
    // the compositor and we only pass playing animations to the compositor,
    // which are, by definition, "relevant" animations (animations that are
    // not yet finished or which are filling forwards).
    MOZ_ASSERT(anim->IsRelevant());

    dom::KeyframeEffect* effect =
      anim->GetEffect() ? anim->GetEffect()->AsKeyframeEffect() : nullptr;
    MOZ_ASSERT(effect, "A playing animation should have a keyframe effect");
    for (size_t propIdx = effect->Properties().Length(); propIdx-- != 0; ) {
      const AnimationProperty& prop = effect->Properties()[propIdx];
      if (prop.mProperty != eCSSProperty_transform) {
        continue;
      }

      // We need to factor in the scale of the base style if the base style
      // will be used on the compositor.
      AnimationValue baseStyle = effect->BaseStyle(prop.mProperty);
      if (!baseStyle.IsNull()) {
        UpdateMinMaxScale(aFrame, baseStyle, aMinScale, aMaxScale);
      }

      for (const AnimationPropertySegment& segment : prop.mSegments) {
        // In case of add or accumulate composite, StyleAnimationValue does
        // not have a valid value.
        if (segment.HasReplaceableFromValue()) {
          UpdateMinMaxScale(aFrame, segment.mFromValue, aMinScale, aMaxScale);
        }
        if (segment.HasReplaceableToValue()) {
          UpdateMinMaxScale(aFrame, segment.mToValue, aMinScale, aMaxScale);
        }
      }
    }
  }
}

Size
nsLayoutUtils::ComputeSuitableScaleForAnimation(const nsIFrame* aFrame,
                                                const nsSize& aVisibleSize,
                                                const nsSize& aDisplaySize)
{
  Size maxScale(std::numeric_limits<float>::min(),
                std::numeric_limits<float>::min());
  Size minScale(std::numeric_limits<float>::max(),
                std::numeric_limits<float>::max());

  nsTArray<RefPtr<dom::Animation>> compositorAnimations =
    EffectCompositor::GetAnimationsForCompositor(aFrame,
                                                 eCSSProperty_transform);
  GetMinAndMaxScaleForAnimationProperty(aFrame, compositorAnimations,
                                        maxScale, minScale);

  if (maxScale.width == std::numeric_limits<float>::min()) {
    // We didn't encounter a transform
    return Size(1.0, 1.0);
  }

  return Size(GetSuitableScale(maxScale.width, minScale.width,
                               aVisibleSize.width, aDisplaySize.width),
              GetSuitableScale(maxScale.height, minScale.height,
                               aVisibleSize.height, aDisplaySize.height));
}

bool
nsLayoutUtils::AreAsyncAnimationsEnabled()
{
  static bool sAreAsyncAnimationsEnabled;
  static bool sAsyncPrefCached = false;

  if (!sAsyncPrefCached) {
    sAsyncPrefCached = true;
    Preferences::AddBoolVarCache(&sAreAsyncAnimationsEnabled,
                                 "layers.offmainthreadcomposition.async-animations");
  }

  return sAreAsyncAnimationsEnabled &&
    gfxPlatform::OffMainThreadCompositingEnabled();
}

bool
nsLayoutUtils::IsAnimationLoggingEnabled()
{
  static bool sShouldLog;
  static bool sShouldLogPrefCached;

  if (!sShouldLogPrefCached) {
    sShouldLogPrefCached = true;
    Preferences::AddBoolVarCache(&sShouldLog,
                                 "layers.offmainthreadcomposition.log-animations");
  }

  return sShouldLog;
}

bool
nsLayoutUtils::AreRetainedDisplayListsEnabled()
{
  if (XRE_IsContentProcess()) {
    return gfxPrefs::LayoutRetainDisplayList();
  }

  if (XRE_IsE10sParentProcess()) {
    return gfxPrefs::LayoutRetainDisplayListChrome();
  }

  // Retained display lists require e10s.
  return false;
}

bool
nsLayoutUtils::DisplayRootHasRetainedDisplayListBuilder(nsIFrame* aFrame)
{
  const nsIFrame* displayRoot = nsLayoutUtils::GetDisplayRootFrame(aFrame);
  MOZ_ASSERT(displayRoot);
  return displayRoot->HasProperty(RetainedDisplayListBuilder::Cached());
}

bool
nsLayoutUtils::GPUImageScalingEnabled()
{
  static bool sGPUImageScalingEnabled;
  static bool sGPUImageScalingPrefInitialised = false;

  if (!sGPUImageScalingPrefInitialised) {
    sGPUImageScalingPrefInitialised = true;
    sGPUImageScalingEnabled =
      Preferences::GetBool("layout.gpu-image-scaling.enabled", false);
  }

  return sGPUImageScalingEnabled;
}

bool
nsLayoutUtils::AnimatedImageLayersEnabled()
{
  static bool sAnimatedImageLayersEnabled;
  static bool sAnimatedImageLayersPrefCached = false;

  if (!sAnimatedImageLayersPrefCached) {
    sAnimatedImageLayersPrefCached = true;
    Preferences::AddBoolVarCache(&sAnimatedImageLayersEnabled,
                                 "layout.animated-image-layers.enabled",
                                 false);
  }

  return sAnimatedImageLayersEnabled;
}

bool
nsLayoutUtils::IsInterCharacterRubyEnabled()
{
  static bool sInterCharacterRubyEnabled;
  static bool sInterCharacterRubyEnabledPrefCached = false;

  if (!sInterCharacterRubyEnabledPrefCached) {
    sInterCharacterRubyEnabledPrefCached = true;
    Preferences::AddBoolVarCache(&sInterCharacterRubyEnabled,
                                 INTERCHARACTER_RUBY_ENABLED_PREF_NAME,
                                 false);
  }

  return sInterCharacterRubyEnabled;
}

bool
nsLayoutUtils::IsContentSelectEnabled()
{
  static bool sContentSelectEnabled;
  static bool sContentSelectEnabledPrefCached = false;

  if (!sContentSelectEnabledPrefCached) {
    sContentSelectEnabledPrefCached = true;
    Preferences::AddBoolVarCache(&sContentSelectEnabled,
                                 CONTENT_SELECT_ENABLED_PREF_NAME,
                                 false);
  }

  return sContentSelectEnabled;
}

void
nsLayoutUtils::UnionChildOverflow(nsIFrame* aFrame,
                                  nsOverflowAreas& aOverflowAreas,
                                  FrameChildListIDs aSkipChildLists)
{
  // Iterate over all children except pop-ups.
  FrameChildListIDs skip = aSkipChildLists |
      nsIFrame::kSelectPopupList | nsIFrame::kPopupList;
  for (nsIFrame::ChildListIterator childLists(aFrame);
       !childLists.IsDone(); childLists.Next()) {
    if (skip.Contains(childLists.CurrentID())) {
      continue;
    }

    nsFrameList children = childLists.CurrentList();
    for (nsFrameList::Enumerator e(children); !e.AtEnd(); e.Next()) {
      nsIFrame* child = e.get();
      nsOverflowAreas childOverflow =
        child->GetOverflowAreas() + child->GetPosition();
      aOverflowAreas.UnionWith(childOverflow);
    }
  }
}

static void DestroyViewID(void* aObject, nsAtom* aPropertyName,
                          void* aPropertyValue, void* aData)
{
  ViewID* id = static_cast<ViewID*>(aPropertyValue);
  GetContentMap().Remove(*id);
  delete id;
}

/**
 * A namespace class for static layout utilities.
 */

bool
nsLayoutUtils::FindIDFor(const nsIContent* aContent, ViewID* aOutViewId)
{
  void* scrollIdProperty = aContent->GetProperty(nsGkAtoms::RemoteId);
  if (scrollIdProperty) {
    *aOutViewId = *static_cast<ViewID*>(scrollIdProperty);
    return true;
  }
  return false;
}

ViewID
nsLayoutUtils::FindOrCreateIDFor(nsIContent* aContent)
{
  ViewID scrollId;

  if (!FindIDFor(aContent, &scrollId)) {
    scrollId = sScrollIdCounter++;
    aContent->SetProperty(nsGkAtoms::RemoteId, new ViewID(scrollId),
                          DestroyViewID);
    GetContentMap().Put(scrollId, aContent);
  }

  return scrollId;
}

nsIContent*
nsLayoutUtils::FindContentFor(ViewID aId)
{
  MOZ_ASSERT(aId != ScrollableLayerGuid::NULL_SCROLL_ID,
             "Cannot find a content element in map for null IDs.");
  nsIContent* content;
  bool exists = GetContentMap().Get(aId, &content);

  if (exists) {
    return content;
  } else {
    return nullptr;
  }
}

static nsIFrame*
GetScrollFrameFromContent(nsIContent* aContent)
{
  nsIFrame* frame = aContent->GetPrimaryFrame();
  if (aContent->OwnerDoc()->GetRootElement() == aContent) {
    nsIPresShell* presShell = frame ? frame->PresShell() : nullptr;
    if (!presShell) {
      presShell = aContent->OwnerDoc()->GetShell();
    }
    // We want the scroll frame, the root scroll frame differs from all
    // others in that the primary frame is not the scroll frame.
    nsIFrame* rootScrollFrame = presShell ? presShell->GetRootScrollFrame() : nullptr;
    if (rootScrollFrame) {
      frame = rootScrollFrame;
    }
  }
  return frame;
}

nsIScrollableFrame*
nsLayoutUtils::FindScrollableFrameFor(ViewID aId)
{
  nsIContent* content = FindContentFor(aId);
  if (!content) {
    return nullptr;
  }

  nsIFrame* scrollFrame = GetScrollFrameFromContent(content);
  return scrollFrame ? scrollFrame->GetScrollTargetFrame() : nullptr;
}

ViewID
nsLayoutUtils::FindIDForScrollableFrame(nsIScrollableFrame* aScrollable)
{
  if (!aScrollable) {
    return ScrollableLayerGuid::NULL_SCROLL_ID;
  }

  nsIFrame* scrollFrame = do_QueryFrame(aScrollable);
  nsIContent* scrollContent = scrollFrame->GetContent();

  ScrollableLayerGuid::ViewID scrollId;
  if (scrollContent &&
      nsLayoutUtils::FindIDFor(scrollContent, &scrollId)) {
    return scrollId;
  }

  return ScrollableLayerGuid::NULL_SCROLL_ID;
}

static nsRect
ApplyRectMultiplier(nsRect aRect, float aMultiplier)
{
  if (aMultiplier == 1.0f) {
    return aRect;
  }
  float newWidth = aRect.width * aMultiplier;
  float newHeight = aRect.height * aMultiplier;
  float newX = aRect.x - ((newWidth - aRect.width) / 2.0f);
  float newY = aRect.y - ((newHeight - aRect.height) / 2.0f);
  // Rounding doesn't matter too much here, do a round-in
  return nsRect(ceil(newX), ceil(newY), floor(newWidth), floor(newHeight));
}

bool
nsLayoutUtils::UsesAsyncScrolling(nsIFrame* aFrame)
{
#ifdef MOZ_WIDGET_ANDROID
  // We always have async scrolling for android
  return true;
#endif

  return AsyncPanZoomEnabled(aFrame);
}

bool
nsLayoutUtils::AsyncPanZoomEnabled(nsIFrame* aFrame)
{
  // We use this as a shortcut, since if the compositor will never use APZ,
  // no widget will either.
  if (!gfxPlatform::AsyncPanZoomEnabled()) {
    return false;
  }

  nsIFrame *frame = nsLayoutUtils::GetDisplayRootFrame(aFrame);
  nsIWidget* widget = frame->GetNearestWidget();
  if (!widget) {
    return false;
  }
  return widget->AsyncPanZoomEnabled();
}

float
nsLayoutUtils::GetCurrentAPZResolutionScale(nsIPresShell* aShell) {
  return aShell ? aShell->GetCumulativeNonRootScaleResolution() : 1.0;
}

// Return the maximum displayport size, based on the LayerManager's maximum
// supported texture size. The result is in app units.
static nscoord
GetMaxDisplayPortSize(nsIContent* aContent, nsPresContext* aFallbackPrescontext)
{
  MOZ_ASSERT(!gfxPrefs::LayersTilesEnabled(), "Do not clamp displayports if tiling is enabled");

  // Pick a safe maximum displayport size for sanity purposes. This is the
  // lowest maximum texture size on tileless-platforms (Windows, D3D10).
  // If the gfx.max-texture-size pref is set, further restrict the displayport
  // size to fit within that, because the compositor won't upload stuff larger
  // than this size.
  nscoord safeMaximum = aFallbackPrescontext
      ? aFallbackPrescontext->DevPixelsToAppUnits(
            std::min(8192, gfxPlatform::MaxTextureSize()))
      : nscoord_MAX;

  nsIFrame* frame = aContent->GetPrimaryFrame();
  if (!frame) {
    return safeMaximum;
  }
  frame = nsLayoutUtils::GetDisplayRootFrame(frame);

  nsIWidget* widget = frame->GetNearestWidget();
  if (!widget) {
    return safeMaximum;
  }
  LayerManager* lm = widget->GetLayerManager();
  if (!lm) {
    return safeMaximum;
  }
  nsPresContext* presContext = frame->PresContext();

  int32_t maxSizeInDevPixels = lm->GetMaxTextureSize();
  if (maxSizeInDevPixels < 0 || maxSizeInDevPixels == INT_MAX) {
    return safeMaximum;
  }
  maxSizeInDevPixels = std::min(maxSizeInDevPixels, gfxPlatform::MaxTextureSize());
  return presContext->DevPixelsToAppUnits(maxSizeInDevPixels);
}

static nsRect
GetDisplayPortFromRectData(nsIContent* aContent,
                           DisplayPortPropertyData* aRectData,
                           float aMultiplier)
{
  // In the case where the displayport is set as a rect, we assume it is
  // already aligned and clamped as necessary. The burden to do that is
  // on the setter of the displayport. In practice very few places set the
  // displayport directly as a rect (mostly tests). We still do need to
  // expand it by the multiplier though.
  return ApplyRectMultiplier(aRectData->mRect, aMultiplier);
}

static nsRect
GetDisplayPortFromMarginsData(nsIContent* aContent,
                              DisplayPortMarginsPropertyData* aMarginsData,
                              float aMultiplier)
{
  // In the case where the displayport is set via margins, we apply the margins
  // to a base rect. Then we align the expanded rect based on the alignment
  // requested, further expand the rect by the multiplier, and finally, clamp it
  // to the size of the scrollable rect.

  nsRect base;
  if (nsRect* baseData = static_cast<nsRect*>(aContent->GetProperty(nsGkAtoms::DisplayPortBase))) {
    base = *baseData;
  } else {
    // In theory we shouldn't get here, but we do sometimes (see bug 1212136).
    // Fall through for graceful handling.
  }

  nsIFrame* frame = GetScrollFrameFromContent(aContent);
  if (!frame) {
    // Turns out we can't really compute it. Oops. We still should return
    // something sane. Note that since we can't clamp the rect without a
    // frame, we don't apply the multiplier either as it can cause the result
    // to leak outside the scrollable area.
    NS_WARNING("Attempting to get a displayport from a content with no primary frame!");
    return base;
  }

  bool isRoot = false;
  if (aContent->OwnerDoc()->GetRootElement() == aContent) {
    isRoot = true;
  }

  nsPoint scrollPos;
  if (nsIScrollableFrame* scrollableFrame = frame->GetScrollTargetFrame()) {
    scrollPos = scrollableFrame->GetScrollPosition();
  }

  nsPresContext* presContext = frame->PresContext();
  int32_t auPerDevPixel = presContext->AppUnitsPerDevPixel();

  LayoutDeviceToScreenScale2D res(presContext->PresShell()->GetCumulativeResolution()
                                * nsLayoutUtils::GetTransformToAncestorScale(frame));

  // Calculate the expanded scrollable rect, which we'll be clamping the
  // displayport to.
  nsRect expandedScrollableRect =
    nsLayoutUtils::CalculateExpandedScrollableRect(frame);

  // GetTransformToAncestorScale() can return 0. In this case, just return the
  // base rect (clamped to the expanded scrollable rect), as other calculations
  // would run into divisions by zero.
  if (res == LayoutDeviceToScreenScale2D(0, 0)) {
    // Make sure the displayport remains within the scrollable rect.
    return base.MoveInsideAndClamp(expandedScrollableRect - scrollPos);
  }

  // First convert the base rect to screen pixels
  LayoutDeviceToScreenScale2D parentRes = res;
  if (isRoot) {
    // the base rect for root scroll frames is specified in the parent document
    // coordinate space, so it doesn't include the local resolution.
    float localRes = presContext->PresShell()->GetResolution();
    parentRes.xScale /= localRes;
    parentRes.yScale /= localRes;
  }
  ScreenRect screenRect = LayoutDeviceRect::FromAppUnits(base, auPerDevPixel)
                        * parentRes;

  // Note on the correctness of applying the alignment in Screen space:
  //   The correct space to apply the alignment in would be Layer space, but
  //   we don't necessarily know the scale to convert to Layer space at this
  //   point because Layout may not yet have chosen the resolution at which to
  //   render (it chooses that in FrameLayerBuilder, but this can be called
  //   during display list building). Therefore, we perform the alignment in
  //   Screen space, which basically assumes that Layout chose to render at
  //   screen resolution; since this is what Layout does most of the time,
  //   this is a good approximation. A proper solution would involve moving
  //   the choosing of the resolution to display-list building time.
  ScreenSize alignment;

  nsIPresShell* presShell = presContext->PresShell();
  MOZ_ASSERT(presShell);

  if (presShell->IsDisplayportSuppressed()) {
    alignment = ScreenSize(1, 1);
  } else if (gfxPrefs::LayersTilesEnabled()) {
    // Don't align to tiles if they are too large, because we could expand
    // the displayport by a lot which can take more paint time. It's a tradeoff
    // though because if we don't align to tiles we have more waste on upload.
    IntSize tileSize = gfxVars::TileSize();
    alignment = ScreenSize(std::min(256, tileSize.width), std::min(256, tileSize.height));
  } else {
    // If we're not drawing with tiles then we need to be careful about not
    // hitting the max texture size and we only need 1 draw call per layer
    // so we can align to a smaller multiple.
    alignment = ScreenSize(128, 128);
  }

  // Avoid division by zero.
  if (alignment.width == 0) {
    alignment.width = 128;
  }
  if (alignment.height == 0) {
    alignment.height = 128;
  }

  if (gfxPrefs::LayersTilesEnabled()) {
    // Expand the rect by the margins
    screenRect.Inflate(aMarginsData->mMargins);
  } else {
    // Calculate the displayport to make sure we fit within the max texture size
    // when not tiling.
    nscoord maxSizeAppUnits = GetMaxDisplayPortSize(aContent, presContext);
    MOZ_ASSERT(maxSizeAppUnits < nscoord_MAX);

    // The alignment code can round up to 3 tiles, we want to make sure
    // that the displayport can grow by up to 3 tiles without going
    // over the max texture size.
    const int MAX_ALIGN_ROUNDING = 3;

    // Find the maximum size in screen pixels.
    int32_t maxSizeDevPx = presContext->AppUnitsToDevPixels(maxSizeAppUnits);
    int32_t maxWidthScreenPx = floor(double(maxSizeDevPx) * res.xScale) -
      MAX_ALIGN_ROUNDING * alignment.width;
    int32_t maxHeightScreenPx = floor(double(maxSizeDevPx) * res.yScale) -
      MAX_ALIGN_ROUNDING * alignment.height;

    // For each axis, inflate the margins up to the maximum size.
    const ScreenMargin& margins = aMarginsData->mMargins;
    if (screenRect.height < maxHeightScreenPx) {
      int32_t budget = maxHeightScreenPx - screenRect.height;
      // Scale the margins down to fit into the budget if necessary, maintaining
      // their relative ratio.
      float scale = 1.0f;
      if (float(budget) < margins.TopBottom()) {
        scale = float(budget) / margins.TopBottom();
      }
      float top = margins.top * scale;
      float bottom = margins.bottom * scale;
      screenRect.y -= top;
      screenRect.height += top + bottom;
    }
    if (screenRect.width < maxWidthScreenPx) {
      int32_t budget = maxWidthScreenPx - screenRect.width;
      float scale = 1.0f;
      if (float(budget) < margins.LeftRight()) {
        scale = float(budget) / margins.LeftRight();
      }
      float left = margins.left * scale;
      float right = margins.right * scale;
      screenRect.x -= left;
      screenRect.width += left + right;
    }
  }

  ScreenPoint scrollPosScreen = LayoutDevicePoint::FromAppUnits(scrollPos, auPerDevPixel)
                              * res;

  // Round-out the display port to the nearest alignment (tiles)
  screenRect += scrollPosScreen;
  float x = alignment.width * floor(screenRect.x / alignment.width);
  float y = alignment.height * floor(screenRect.y / alignment.height);
  float w = alignment.width * ceil(screenRect.width / alignment.width + 1);
  float h = alignment.height * ceil(screenRect.height / alignment.height + 1);
  screenRect = ScreenRect(x, y, w, h);
  screenRect -= scrollPosScreen;

  // Convert the aligned rect back into app units.
  nsRect result = LayoutDeviceRect::ToAppUnits(screenRect / res, auPerDevPixel);

  // If we have non-zero margins, expand the displayport for the low-res buffer
  // if that's what we're drawing. If we have zero margins, we want the
  // displayport to reflect the scrollport.
  if (aMarginsData->mMargins != ScreenMargin()) {
    result = ApplyRectMultiplier(result, aMultiplier);
  }

  // Make sure the displayport remains within the scrollable rect.
  result = result.MoveInsideAndClamp(expandedScrollableRect - scrollPos);

  return result;
}

static bool
HasVisibleAnonymousContents(nsIDocument* aDoc)
{
  for (RefPtr<AnonymousContent>& ac : aDoc->GetAnonymousContents()) {
    // We check to see if the anonymous content node has a frame. If it doesn't,
    // that means that's not visible to the user because e.g. it's display:none.
    // For now we assume that if it has a frame, it is visible. We might be able
    // to refine this further by adding complexity if it turns out this condition
    // results in a lot of false positives.
    if (ac->ContentNode().GetPrimaryFrame()) {
      return true;
    }
  }
  return false;
}

bool
nsLayoutUtils::ShouldDisableApzForElement(nsIContent* aContent)
{
  if (!aContent) {
    return false;
  }

  nsIDocument* doc = aContent->GetComposedDoc();
  nsIPresShell* rootShell = APZCCallbackHelper::GetRootContentDocumentPresShellForContent(aContent);
  if (rootShell) {
    if (nsIDocument* rootDoc = rootShell->GetDocument()) {
      nsIContent* rootContent = rootShell->GetRootScrollFrame()
          ? rootShell->GetRootScrollFrame()->GetContent()
          : rootDoc->GetDocumentElement();
      // For the AccessibleCaret: disable APZ on any scrollable subframes that
      // are not the root scrollframe of a document, if the document has any
      // visible anonymous contents.
      // If we find this is triggering in too many scenarios then we might
      // want to tighten this check further. The main use cases for which we want
      // to disable APZ as of this writing are listed in bug 1316318.
      if (aContent != rootContent && HasVisibleAnonymousContents(rootDoc)) {
        return true;
      }
    }
  }

  if (!doc) {
    return false;
  }
  return gfxPrefs::APZDisableForScrollLinkedEffects() &&
         doc->HasScrollLinkedEffect();
}

static bool
GetDisplayPortData(nsIContent* aContent,
                   DisplayPortPropertyData** aOutRectData,
                   DisplayPortMarginsPropertyData** aOutMarginsData)
{
  MOZ_ASSERT(aOutRectData && aOutMarginsData);

  *aOutRectData =
    static_cast<DisplayPortPropertyData*>(aContent->GetProperty(nsGkAtoms::DisplayPort));
  *aOutMarginsData =
    static_cast<DisplayPortMarginsPropertyData*>(aContent->GetProperty(nsGkAtoms::DisplayPortMargins));

  if (!*aOutRectData && !*aOutMarginsData) {
    // This content element has no displayport data at all
    return false;
  }

  if (*aOutRectData && *aOutMarginsData) {
    // choose margins if equal priority
    if ((*aOutRectData)->mPriority > (*aOutMarginsData)->mPriority) {
      *aOutMarginsData = nullptr;
    } else {
      *aOutRectData = nullptr;
    }
  }

  NS_ASSERTION((*aOutRectData == nullptr) != (*aOutMarginsData == nullptr),
               "Only one of aOutRectData or aOutMarginsData should be set!");

  return true;
}

bool
nsLayoutUtils::IsMissingDisplayPortBaseRect(nsIContent* aContent)
{
  DisplayPortPropertyData* rectData = nullptr;
  DisplayPortMarginsPropertyData* marginsData = nullptr;

  if (GetDisplayPortData(aContent, &rectData, &marginsData) && marginsData) {
    return !aContent->GetProperty(nsGkAtoms::DisplayPortBase);
  }

  return false;
}

enum class MaxSizeExceededBehaviour {
  // Ask GetDisplayPortImpl to assert if the calculated displayport exceeds
  // the maximum allowed size.
  eAssert,
  // Ask GetDisplayPortImpl to pretend like there's no displayport at all, if
  // the calculated displayport exceeds the maximum allowed size.
  eDrop,
};

static bool
GetDisplayPortImpl(nsIContent* aContent, nsRect* aResult, float aMultiplier,
                   MaxSizeExceededBehaviour aBehaviour = MaxSizeExceededBehaviour::eAssert)
{
  DisplayPortPropertyData* rectData = nullptr;
  DisplayPortMarginsPropertyData* marginsData = nullptr;

  if (!GetDisplayPortData(aContent, &rectData, &marginsData)) {
    return false;
  }

  if (!aResult) {
    // We have displayport data, but the caller doesn't want the actual
    // rect, so we don't need to actually compute it.
    return true;
  }

  bool isDisplayportSuppressed = false;

  nsIFrame* frame = aContent->GetPrimaryFrame();
  if (frame) {
    nsPresContext* presContext = frame->PresContext();
    MOZ_ASSERT(presContext);
    nsIPresShell* presShell = presContext->PresShell();
    MOZ_ASSERT(presShell);
    isDisplayportSuppressed = presShell->IsDisplayportSuppressed();
  }

  nsRect result;
  if (rectData) {
    result = GetDisplayPortFromRectData(aContent, rectData, aMultiplier);
  } else if (isDisplayportSuppressed ||
      nsLayoutUtils::ShouldDisableApzForElement(aContent)) {
    DisplayPortMarginsPropertyData noMargins(ScreenMargin(), 1);
    result = GetDisplayPortFromMarginsData(aContent, &noMargins, aMultiplier);
  } else {
    result = GetDisplayPortFromMarginsData(aContent, marginsData, aMultiplier);
  }

  if (!gfxPrefs::LayersTilesEnabled()) {
    // Perform the desired error handling if the displayport dimensions
    // exceeds the maximum allowed size
    nscoord maxSize = GetMaxDisplayPortSize(aContent, nullptr);
    if (result.width > maxSize || result.height > maxSize) {
      switch (aBehaviour) {
      case MaxSizeExceededBehaviour::eAssert:
        NS_ASSERTION(false, "Displayport must be a valid texture size");
        break;
      case MaxSizeExceededBehaviour::eDrop:
        return false;
      }
    }
  }

  *aResult = result;
  return true;
}

static void
TranslateFromScrollPortToScrollFrame(nsIContent* aContent, nsRect* aRect)
{
  MOZ_ASSERT(aRect);
  nsIFrame* frame = GetScrollFrameFromContent(aContent);
  nsIScrollableFrame* scrollableFrame = frame ? frame->GetScrollTargetFrame() : nullptr;
  if (scrollableFrame) {
    *aRect += scrollableFrame->GetScrollPortRect().TopLeft();
  }
}

bool
nsLayoutUtils::GetDisplayPort(nsIContent* aContent, nsRect *aResult,
  RelativeTo aRelativeTo /* = RelativeTo::ScrollPort */)
{
  float multiplier =
    gfxPrefs::UseLowPrecisionBuffer() ? 1.0f / gfxPrefs::LowPrecisionResolution() : 1.0f;
  bool usingDisplayPort = GetDisplayPortImpl(aContent, aResult, multiplier);
  if (aResult && usingDisplayPort && aRelativeTo == RelativeTo::ScrollFrame) {
    TranslateFromScrollPortToScrollFrame(aContent, aResult);
  }
  return usingDisplayPort;
}

bool
nsLayoutUtils::HasDisplayPort(nsIContent* aContent) {
  return GetDisplayPort(aContent, nullptr);
}

/* static */ bool
nsLayoutUtils::GetDisplayPortForVisibilityTesting(
  nsIContent* aContent,
  nsRect* aResult,
  RelativeTo aRelativeTo /* = RelativeTo::ScrollPort */)
{
  MOZ_ASSERT(aResult);
  // Since the base rect might not have been updated very recently, it's
  // possible to end up with an extra-large displayport at this point, if the
  // zoom level is changed by a lot. Instead of using the default behaviour of
  // asserting, we can just ignore the displayport if that happens, as this
  // call site is best-effort.
  bool usingDisplayPort = GetDisplayPortImpl(aContent, aResult, 1.0f,
      MaxSizeExceededBehaviour::eDrop);
  if (usingDisplayPort && aRelativeTo == RelativeTo::ScrollFrame) {
    TranslateFromScrollPortToScrollFrame(aContent, aResult);
  }
  return usingDisplayPort;
}

void
nsLayoutUtils::InvalidateForDisplayPortChange(nsIContent* aContent,
                                              bool aHadDisplayPort,
                                              const nsRect& aOldDisplayPort,
                                              const nsRect& aNewDisplayPort,
                                              RepaintMode aRepaintMode)
{
  if (aRepaintMode != RepaintMode::Repaint) {
    return;
  }

  bool changed = !aHadDisplayPort ||
        !aOldDisplayPort.IsEqualEdges(aNewDisplayPort);

  nsIFrame* frame = GetScrollFrameFromContent(aContent);
  if (frame) {
    frame = do_QueryFrame(frame->GetScrollTargetFrame());
  }

  if (changed && frame) {
    // It is important to call SchedulePaint on the same frame that we set the dirty
    // rect properties on so we can find the frame later to remove the properties.
    frame->SchedulePaint();

    if (!nsLayoutUtils::AreRetainedDisplayListsEnabled() ||
        !nsLayoutUtils::DisplayRootHasRetainedDisplayListBuilder(frame)) {
      return;
    }

    nsRect* rect =
      frame->GetProperty(nsDisplayListBuilder::DisplayListBuildingDisplayPortRect());

    if (!rect) {
      rect = new nsRect();
      frame->SetProperty(nsDisplayListBuilder::DisplayListBuildingDisplayPortRect(), rect);
      frame->SetHasOverrideDirtyRegion(true);

      nsIFrame* rootFrame = frame->PresShell()->GetRootFrame();
      MOZ_ASSERT(rootFrame);

      RetainedDisplayListData* data =
        GetOrSetRetainedDisplayListData(rootFrame);
      data->Flags(frame) |= RetainedDisplayListData::FrameFlags::HasProps;
    }

    if (aHadDisplayPort) {
      // We only need to build a display list for any new areas added
      nsRegion newRegion(aNewDisplayPort);
      newRegion.SubOut(aOldDisplayPort);
      rect->UnionRect(*rect, newRegion.GetBounds());
    } else {
      rect->UnionRect(*rect, aNewDisplayPort);
    }
  }
}

bool
nsLayoutUtils::SetDisplayPortMargins(nsIContent* aContent,
                                     nsIPresShell* aPresShell,
                                     const ScreenMargin& aMargins,
                                     uint32_t aPriority,
                                     RepaintMode aRepaintMode)
{
  MOZ_ASSERT(aContent);
  MOZ_ASSERT(aContent->GetComposedDoc() == aPresShell->GetDocument());

  DisplayPortMarginsPropertyData* currentData =
    static_cast<DisplayPortMarginsPropertyData*>(aContent->GetProperty(nsGkAtoms::DisplayPortMargins));
  if (currentData && currentData->mPriority > aPriority) {
    return false;
  }

  nsRect oldDisplayPort;
  bool hadDisplayPort = GetHighResolutionDisplayPort(aContent, &oldDisplayPort);

  aContent->SetProperty(nsGkAtoms::DisplayPortMargins,
                        new DisplayPortMarginsPropertyData(
                            aMargins, aPriority),
                        nsINode::DeleteProperty<DisplayPortMarginsPropertyData>);

  nsRect newDisplayPort;
  DebugOnly<bool> hasDisplayPort = GetHighResolutionDisplayPort(aContent, &newDisplayPort);
  MOZ_ASSERT(hasDisplayPort);

  if (gfxPrefs::LayoutUseContainersForRootFrames()) {
    nsIFrame* rootScrollFrame = aPresShell->GetRootScrollFrame();
    if (rootScrollFrame &&
        aContent == rootScrollFrame->GetContent() &&
        nsLayoutUtils::UsesAsyncScrolling(rootScrollFrame))
    {
      // We are setting a root displayport for a document.
      // If we have APZ, then set a special flag on the pres shell so
      // that we don't get scrollbars drawn.
      aPresShell->SetIgnoreViewportScrolling(true);
    }
  }

  InvalidateForDisplayPortChange(aContent, hadDisplayPort, oldDisplayPort,
    newDisplayPort, aRepaintMode);

  nsIFrame* frame = GetScrollFrameFromContent(aContent);
  nsIScrollableFrame* scrollableFrame = frame ? frame->GetScrollTargetFrame() : nullptr;
  if (!scrollableFrame) {
    return true;
  }

  scrollableFrame->TriggerDisplayPortExpiration();

  // Display port margins changing means that the set of visible frames may
  // have drastically changed. Check if we should schedule an update.
  hadDisplayPort =
    scrollableFrame->GetDisplayPortAtLastApproximateFrameVisibilityUpdate(&oldDisplayPort);

  bool needVisibilityUpdate = !hadDisplayPort;
  // Check if the total size has changed by a large factor.
  if (!needVisibilityUpdate) {
    if ((newDisplayPort.width > 2 * oldDisplayPort.width) ||
        (oldDisplayPort.width > 2 * newDisplayPort.width) ||
        (newDisplayPort.height > 2 * oldDisplayPort.height) ||
        (oldDisplayPort.height > 2 * newDisplayPort.height)) {
      needVisibilityUpdate = true;
    }
  }
  // Check if it's moved by a significant amount.
  if (!needVisibilityUpdate) {
    if (nsRect* baseData = static_cast<nsRect*>(aContent->GetProperty(nsGkAtoms::DisplayPortBase))) {
      nsRect base = *baseData;
      if ((std::abs(newDisplayPort.X() - oldDisplayPort.X()) > base.width) ||
          (std::abs(newDisplayPort.XMost() - oldDisplayPort.XMost()) > base.width) ||
          (std::abs(newDisplayPort.Y() - oldDisplayPort.Y()) > base.height) ||
          (std::abs(newDisplayPort.YMost() - oldDisplayPort.YMost()) > base.height)) {
        needVisibilityUpdate = true;
      }
    }
  }
  if (needVisibilityUpdate) {
    aPresShell->ScheduleApproximateFrameVisibilityUpdateNow();
  }

  return true;
}

void
nsLayoutUtils::SetDisplayPortBase(nsIContent* aContent, const nsRect& aBase)
{
  aContent->SetProperty(nsGkAtoms::DisplayPortBase, new nsRect(aBase),
                        nsINode::DeleteProperty<nsRect>);
}

void
nsLayoutUtils::SetDisplayPortBaseIfNotSet(nsIContent* aContent, const nsRect& aBase)
{
  if (!aContent->GetProperty(nsGkAtoms::DisplayPortBase)) {
    SetDisplayPortBase(aContent, aBase);
  }
}

bool
nsLayoutUtils::GetCriticalDisplayPort(nsIContent* aContent, nsRect* aResult)
{
  if (gfxPrefs::UseLowPrecisionBuffer()) {
    return GetDisplayPortImpl(aContent, aResult, 1.0f);
  }
  return false;
}

bool
nsLayoutUtils::HasCriticalDisplayPort(nsIContent* aContent)
{
  return GetCriticalDisplayPort(aContent, nullptr);
}

bool
nsLayoutUtils::GetHighResolutionDisplayPort(nsIContent* aContent, nsRect* aResult)
{
  if (gfxPrefs::UseLowPrecisionBuffer()) {
    return GetCriticalDisplayPort(aContent, aResult);
  }
  return GetDisplayPort(aContent, aResult);
}

void
nsLayoutUtils::RemoveDisplayPort(nsIContent* aContent)
{
  aContent->DeleteProperty(nsGkAtoms::DisplayPort);
  aContent->DeleteProperty(nsGkAtoms::DisplayPortMargins);
}

nsContainerFrame*
nsLayoutUtils::LastContinuationWithChild(nsContainerFrame* aFrame)
{
  MOZ_ASSERT(aFrame, "NULL frame pointer");
  for (auto f = aFrame->LastContinuation(); f; f = f->GetPrevContinuation()) {
    for (nsIFrame::ChildListIterator lists(f); !lists.IsDone(); lists.Next()) {
      if (MOZ_LIKELY(!lists.CurrentList().IsEmpty())) {
        return static_cast<nsContainerFrame*>(f);
      }
    }
  }
  return aFrame;
}

//static
FrameChildListID
nsLayoutUtils::GetChildListNameFor(nsIFrame* aChildFrame)
{
  nsIFrame::ChildListID id = nsIFrame::kPrincipalList;

  MOZ_DIAGNOSTIC_ASSERT(!(aChildFrame->GetStateBits() & NS_FRAME_OUT_OF_FLOW));

  if (aChildFrame->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER) {
    nsIFrame* pif = aChildFrame->GetPrevInFlow();
    if (pif->GetParent() == aChildFrame->GetParent()) {
      id = nsIFrame::kExcessOverflowContainersList;
    }
    else {
      id = nsIFrame::kOverflowContainersList;
    }
  } else {
    LayoutFrameType childType = aChildFrame->Type();
    if (LayoutFrameType::MenuPopup == childType) {
      nsIFrame* parent = aChildFrame->GetParent();
      MOZ_ASSERT(parent, "nsMenuPopupFrame can't be the root frame");
      if (parent) {
        if (parent->IsPopupSetFrame()) {
          id = nsIFrame::kPopupList;
        } else {
          nsIFrame* firstPopup = parent->GetChildList(nsIFrame::kPopupList).FirstChild();
          MOZ_ASSERT(!firstPopup || !firstPopup->GetNextSibling(),
                     "We assume popupList only has one child, but it has more.");
          id = firstPopup == aChildFrame
                 ? nsIFrame::kPopupList
                 : nsIFrame::kPrincipalList;
        }
      } else {
        id = nsIFrame::kPrincipalList;
      }
    } else if (LayoutFrameType::TableColGroup == childType) {
      id = nsIFrame::kColGroupList;
    } else if (aChildFrame->IsTableCaption()) {
      id = nsIFrame::kCaptionList;
    } else {
      id = nsIFrame::kPrincipalList;
    }
  }

#ifdef DEBUG
  // Verify that the frame is actually in that child list or in the
  // corresponding overflow list.
  nsContainerFrame* parent = aChildFrame->GetParent();
  bool found = parent->GetChildList(id).ContainsFrame(aChildFrame);
  if (!found) {
    found = parent->GetChildList(nsIFrame::kOverflowList)
              .ContainsFrame(aChildFrame);
    MOZ_ASSERT(found, "not in child list");
  }
#endif

  return id;
}

static Element*
GetPseudo(const nsIContent* aContent, nsAtom* aPseudoProperty)
{
  MOZ_ASSERT(aPseudoProperty == nsGkAtoms::beforePseudoProperty ||
             aPseudoProperty == nsGkAtoms::afterPseudoProperty);
  if (!aContent->MayHaveAnonymousChildren()) {
    return nullptr;
  }
  return static_cast<Element*>(aContent->GetProperty(aPseudoProperty));
}

/*static*/ Element*
nsLayoutUtils::GetBeforePseudo(const nsIContent* aContent)
{
  return GetPseudo(aContent, nsGkAtoms::beforePseudoProperty);
}

/*static*/ nsIFrame*
nsLayoutUtils::GetBeforeFrame(const nsIContent* aContent)
{
  Element* pseudo = GetBeforePseudo(aContent);
  return pseudo ? pseudo->GetPrimaryFrame() : nullptr;
}

/*static*/ Element*
nsLayoutUtils::GetAfterPseudo(const nsIContent* aContent)
{
  return GetPseudo(aContent, nsGkAtoms::afterPseudoProperty);
}

/*static*/ nsIFrame*
nsLayoutUtils::GetAfterFrame(const nsIContent* aContent)
{
  Element* pseudo = GetAfterPseudo(aContent);
  return pseudo ? pseudo->GetPrimaryFrame() : nullptr;
}

// static
nsIFrame*
nsLayoutUtils::GetClosestFrameOfType(nsIFrame* aFrame,
                                     LayoutFrameType aFrameType,
                                     nsIFrame* aStopAt)
{
  for (nsIFrame* frame = aFrame; frame; frame = frame->GetParent()) {
    if (frame->Type() == aFrameType) {
      return frame;
    }
    if (frame == aStopAt) {
      break;
    }
  }
  return nullptr;
}

/* static */ nsIFrame*
nsLayoutUtils::GetPageFrame(nsIFrame* aFrame)
{
  return GetClosestFrameOfType(aFrame, LayoutFrameType::Page);
}

// static
nsIFrame*
nsLayoutUtils::GetStyleFrame(nsIFrame* aFrame)
{
  if (aFrame->IsTableWrapperFrame()) {
    nsIFrame* inner = aFrame->PrincipalChildList().FirstChild();
    // inner may be null, if aFrame is mid-destruction
    return inner;
  }

  return aFrame;
}

nsIFrame*
nsLayoutUtils::GetStyleFrame(const nsIContent* aContent)
{
  nsIFrame *frame = aContent->GetPrimaryFrame();
  if (!frame) {
    return nullptr;
  }

  return nsLayoutUtils::GetStyleFrame(frame);
}

/* static */ nsIFrame*
nsLayoutUtils::GetRealPrimaryFrameFor(const nsIContent* aContent)
{
  nsIFrame *frame = aContent->GetPrimaryFrame();
  if (!frame) {
    return nullptr;
  }

  return nsPlaceholderFrame::GetRealFrameFor(frame);
}

nsIFrame*
nsLayoutUtils::GetFloatFromPlaceholder(nsIFrame* aFrame) {
  NS_ASSERTION(aFrame->IsPlaceholderFrame(), "Must have a placeholder here");
  if (aFrame->GetStateBits() & PLACEHOLDER_FOR_FLOAT) {
    nsIFrame *outOfFlowFrame =
      nsPlaceholderFrame::GetRealFrameForPlaceholder(aFrame);
    NS_ASSERTION(outOfFlowFrame && outOfFlowFrame->IsFloating(),
                 "How did that happen?");
    return outOfFlowFrame;
  }

  return nullptr;
}

// static
nsIFrame*
nsLayoutUtils::GetCrossDocParentFrame(const nsIFrame* aFrame,
                                      nsPoint* aExtraOffset)
{
  nsIFrame* p = aFrame->GetParent();
  if (p)
    return p;

  nsView* v = aFrame->GetView();
  if (!v)
    return nullptr;
  v = v->GetParent(); // anonymous inner view
  if (!v)
    return nullptr;
  if (aExtraOffset) {
    *aExtraOffset += v->GetPosition();
  }
  v = v->GetParent(); // subdocumentframe's view
  return v ? v->GetFrame() : nullptr;
}

// static
bool
nsLayoutUtils::IsProperAncestorFrameCrossDoc(nsIFrame* aAncestorFrame, nsIFrame* aFrame,
                                             nsIFrame* aCommonAncestor)
{
  if (aFrame == aAncestorFrame)
    return false;
  return IsAncestorFrameCrossDoc(aAncestorFrame, aFrame, aCommonAncestor);
}

// static
bool
nsLayoutUtils::IsAncestorFrameCrossDoc(const nsIFrame* aAncestorFrame, const nsIFrame* aFrame,
                                       const nsIFrame* aCommonAncestor)
{
  for (const nsIFrame* f = aFrame; f != aCommonAncestor;
       f = GetCrossDocParentFrame(f)) {
    if (f == aAncestorFrame)
      return true;
  }
  return aCommonAncestor == aAncestorFrame;
}

// static
bool
nsLayoutUtils::IsProperAncestorFrame(nsIFrame* aAncestorFrame, nsIFrame* aFrame,
                                     nsIFrame* aCommonAncestor)
{
  if (aFrame == aAncestorFrame)
    return false;
  for (nsIFrame* f = aFrame; f != aCommonAncestor; f = f->GetParent()) {
    if (f == aAncestorFrame)
      return true;
  }
  return aCommonAncestor == aAncestorFrame;
}

// static
int32_t
nsLayoutUtils::DoCompareTreePosition(nsIContent* aContent1,
                                     nsIContent* aContent2,
                                     int32_t aIf1Ancestor,
                                     int32_t aIf2Ancestor,
                                     const nsIContent* aCommonAncestor)
{
  MOZ_ASSERT(aContent1, "aContent1 must not be null");
  MOZ_ASSERT(aContent2, "aContent2 must not be null");

  AutoTArray<nsINode*, 32> content1Ancestors;
  nsINode* c1;
  for (c1 = aContent1;
       c1 && c1 != aCommonAncestor;
       c1 = c1->GetParentOrHostNode()) {
    content1Ancestors.AppendElement(c1);
  }
  if (!c1 && aCommonAncestor) {
    // So, it turns out aCommonAncestor was not an ancestor of c1. Oops.
    // Never mind. We can continue as if aCommonAncestor was null.
    aCommonAncestor = nullptr;
  }

  AutoTArray<nsINode*, 32> content2Ancestors;
  nsINode* c2;
  for (c2 = aContent2;
       c2 && c2 != aCommonAncestor;
       c2 = c2->GetParentOrHostNode()) {
    content2Ancestors.AppendElement(c2);
  }
  if (!c2 && aCommonAncestor) {
    // So, it turns out aCommonAncestor was not an ancestor of c2.
    // We need to retry with no common ancestor hint.
    return DoCompareTreePosition(aContent1, aContent2,
                                 aIf1Ancestor, aIf2Ancestor, nullptr);
  }

  int last1 = content1Ancestors.Length() - 1;
  int last2 = content2Ancestors.Length() - 1;
  nsINode* content1Ancestor = nullptr;
  nsINode* content2Ancestor = nullptr;
  while (last1 >= 0 && last2 >= 0
         && ((content1Ancestor = content1Ancestors.ElementAt(last1)) ==
             (content2Ancestor = content2Ancestors.ElementAt(last2)))) {
    last1--;
    last2--;
  }

  if (last1 < 0) {
    if (last2 < 0) {
      NS_ASSERTION(aContent1 == aContent2, "internal error?");
      return 0;
    }
    // aContent1 is an ancestor of aContent2
    return aIf1Ancestor;
  }

  if (last2 < 0) {
    // aContent2 is an ancestor of aContent1
    return aIf2Ancestor;
  }

  // content1Ancestor != content2Ancestor, so they must be siblings with the same parent
  nsINode* parent = content1Ancestor->GetParentOrHostNode();
#ifdef DEBUG
  // TODO: remove the uglyness, see bug 598468.
  NS_ASSERTION(gPreventAssertInCompareTreePosition || parent,
               "no common ancestor at all???");
#endif // DEBUG
  if (!parent) { // different documents??
    return 0;
  }

  int32_t index1 = parent->ComputeIndexOf(content1Ancestor);
  int32_t index2 = parent->ComputeIndexOf(content2Ancestor);
  if (index1 < 0 || index2 < 0) {
    // one of them must be anonymous; we can't determine the order
    return 0;
  }

  return index1 - index2;
}

// static
nsIFrame*
nsLayoutUtils::FillAncestors(nsIFrame* aFrame,
                             nsIFrame* aStopAtAncestor,
                             nsTArray<nsIFrame*>* aAncestors)
{
  while (aFrame && aFrame != aStopAtAncestor) {
    aAncestors->AppendElement(aFrame);
    aFrame = nsLayoutUtils::GetParentOrPlaceholderFor(aFrame);
  }
  return aFrame;
}

// Return true if aFrame1 is after aFrame2
static bool IsFrameAfter(nsIFrame* aFrame1, nsIFrame* aFrame2)
{
  nsIFrame* f = aFrame2;
  do {
    f = f->GetNextSibling();
    if (f == aFrame1)
      return true;
  } while (f);
  return false;
}

// static
int32_t
nsLayoutUtils::DoCompareTreePosition(nsIFrame* aFrame1,
                                     nsIFrame* aFrame2,
                                     int32_t aIf1Ancestor,
                                     int32_t aIf2Ancestor,
                                     nsIFrame* aCommonAncestor)
{
  MOZ_ASSERT(aFrame1, "aFrame1 must not be null");
  MOZ_ASSERT(aFrame2, "aFrame2 must not be null");

  AutoTArray<nsIFrame*,20> frame2Ancestors;
  nsIFrame* nonCommonAncestor =
    FillAncestors(aFrame2, aCommonAncestor, &frame2Ancestors);

  return DoCompareTreePosition(aFrame1, aFrame2, frame2Ancestors,
                               aIf1Ancestor, aIf2Ancestor,
                               nonCommonAncestor ? aCommonAncestor : nullptr);
}

// static
int32_t
nsLayoutUtils::DoCompareTreePosition(nsIFrame* aFrame1,
                                     nsIFrame* aFrame2,
                                     nsTArray<nsIFrame*>& aFrame2Ancestors,
                                     int32_t aIf1Ancestor,
                                     int32_t aIf2Ancestor,
                                     nsIFrame* aCommonAncestor)
{
  MOZ_ASSERT(aFrame1, "aFrame1 must not be null");
  MOZ_ASSERT(aFrame2, "aFrame2 must not be null");

  nsPresContext* presContext = aFrame1->PresContext();
  if (presContext != aFrame2->PresContext()) {
    NS_ERROR("no common ancestor at all, different documents");
    return 0;
  }

  AutoTArray<nsIFrame*,20> frame1Ancestors;
  if (aCommonAncestor &&
      !FillAncestors(aFrame1, aCommonAncestor, &frame1Ancestors)) {
    // We reached the root of the frame tree ... if aCommonAncestor was set,
    // it is wrong
    return DoCompareTreePosition(aFrame1, aFrame2,
                                 aIf1Ancestor, aIf2Ancestor, nullptr);
  }

  int32_t last1 = int32_t(frame1Ancestors.Length()) - 1;
  int32_t last2 = int32_t(aFrame2Ancestors.Length()) - 1;
  while (last1 >= 0 && last2 >= 0 &&
         frame1Ancestors[last1] == aFrame2Ancestors[last2]) {
    last1--;
    last2--;
  }

  if (last1 < 0) {
    if (last2 < 0) {
      NS_ASSERTION(aFrame1 == aFrame2, "internal error?");
      return 0;
    }
    // aFrame1 is an ancestor of aFrame2
    return aIf1Ancestor;
  }

  if (last2 < 0) {
    // aFrame2 is an ancestor of aFrame1
    return aIf2Ancestor;
  }

  nsIFrame* ancestor1 = frame1Ancestors[last1];
  nsIFrame* ancestor2 = aFrame2Ancestors[last2];
  // Now we should be able to walk sibling chains to find which one is first
  if (IsFrameAfter(ancestor2, ancestor1))
    return -1;
  if (IsFrameAfter(ancestor1, ancestor2))
    return 1;
  NS_WARNING("Frames were in different child lists???");
  return 0;
}

// static
nsIFrame* nsLayoutUtils::GetLastSibling(nsIFrame* aFrame) {
  if (!aFrame) {
    return nullptr;
  }

  nsIFrame* next;
  while ((next = aFrame->GetNextSibling()) != nullptr) {
    aFrame = next;
  }
  return aFrame;
}

// static
nsView*
nsLayoutUtils::FindSiblingViewFor(nsView* aParentView, nsIFrame* aFrame) {
  nsIFrame* parentViewFrame = aParentView->GetFrame();
  nsIContent* parentViewContent = parentViewFrame ? parentViewFrame->GetContent() : nullptr;
  for (nsView* insertBefore = aParentView->GetFirstChild(); insertBefore;
       insertBefore = insertBefore->GetNextSibling()) {
    nsIFrame* f = insertBefore->GetFrame();
    if (!f) {
      // this view could be some anonymous view attached to a meaningful parent
      for (nsView* searchView = insertBefore->GetParent(); searchView;
           searchView = searchView->GetParent()) {
        f = searchView->GetFrame();
        if (f) {
          break;
        }
      }
      NS_ASSERTION(f, "Can't find a frame anywhere!");
    }
    if (!f || !aFrame->GetContent() || !f->GetContent() ||
        CompareTreePosition(aFrame->GetContent(), f->GetContent(), parentViewContent) > 0) {
      // aFrame's content is after f's content (or we just don't know),
      // so put our view before f's view
      return insertBefore;
    }
  }
  return nullptr;
}

//static
nsIScrollableFrame*
nsLayoutUtils::GetScrollableFrameFor(const nsIFrame *aScrolledFrame)
{
  nsIFrame *frame = aScrolledFrame->GetParent();
  nsIScrollableFrame *sf = do_QueryFrame(frame);
  return (sf && sf->GetScrolledFrame() == aScrolledFrame) ? sf : nullptr;
}

/* static */ void
nsLayoutUtils::SetFixedPositionLayerData(Layer* aLayer,
                                         const nsIFrame* aViewportFrame,
                                         const nsRect& aAnchorRect,
                                         const nsIFrame* aFixedPosFrame,
                                         nsPresContext* aPresContext,
                                         const ContainerLayerParameters& aContainerParameters) {
  // Find out the rect of the viewport frame relative to the reference frame.
  // This, in conjunction with the container scale, will correspond to the
  // coordinate-space of the built layer.
  float factor = aPresContext->AppUnitsPerDevPixel();
  Rect anchorRect(NSAppUnitsToFloatPixels(aAnchorRect.x, factor) *
                    aContainerParameters.mXScale,
                  NSAppUnitsToFloatPixels(aAnchorRect.y, factor) *
                    aContainerParameters.mYScale,
                  NSAppUnitsToFloatPixels(aAnchorRect.width, factor) *
                    aContainerParameters.mXScale,
                  NSAppUnitsToFloatPixels(aAnchorRect.height, factor) *
                    aContainerParameters.mYScale);
  // Need to transform anchorRect from the container layer's coordinate system
  // into aLayer's coordinate system.
  Matrix transform2d;
  if (aLayer->GetTransform().Is2D(&transform2d)) {
    transform2d.Invert();
    anchorRect = transform2d.TransformBounds(anchorRect);
  } else {
    NS_ERROR("3D transform found between fixedpos content and its viewport (should never happen)");
    anchorRect = Rect(0,0,0,0);
  }

  // Work out the anchor point for this fixed position layer. We assume that
  // any positioning set (left/top/right/bottom) indicates that the
  // corresponding side of its container should be the anchor point,
  // defaulting to top-left.
  LayerPoint anchor(anchorRect.x, anchorRect.y);

  int32_t sides = eSideBitsNone;
  if (aFixedPosFrame != aViewportFrame) {
    const nsStylePosition* position = aFixedPosFrame->StylePosition();
    if (position->mOffset.GetRightUnit() != eStyleUnit_Auto) {
      sides |= eSideBitsRight;
      if (position->mOffset.GetLeftUnit() != eStyleUnit_Auto) {
        sides |= eSideBitsLeft;
        anchor.x = anchorRect.x + anchorRect.width / 2.f;
      } else {
        anchor.x = anchorRect.XMost();
      }
    } else if (position->mOffset.GetLeftUnit() != eStyleUnit_Auto) {
      sides |= eSideBitsLeft;
    }
    if (position->mOffset.GetBottomUnit() != eStyleUnit_Auto) {
      sides |= eSideBitsBottom;
      if (position->mOffset.GetTopUnit() != eStyleUnit_Auto) {
        sides |= eSideBitsTop;
        anchor.y = anchorRect.y + anchorRect.height / 2.f;
      } else {
        anchor.y = anchorRect.YMost();
      }
    } else if (position->mOffset.GetTopUnit() != eStyleUnit_Auto) {
      sides |= eSideBitsTop;
    }
  }

  ViewID id = ScrollIdForRootScrollFrame(aPresContext);
  aLayer->SetFixedPositionData(id, anchor, sides);
}

ScrollableLayerGuid::ViewID
nsLayoutUtils::ScrollIdForRootScrollFrame(nsPresContext* aPresContext)
{
  ViewID id = ScrollableLayerGuid::NULL_SCROLL_ID;
  if (nsIFrame* rootScrollFrame = aPresContext->PresShell()->GetRootScrollFrame()) {
    if (nsIContent* content = rootScrollFrame->GetContent()) {
      id = FindOrCreateIDFor(content);
    }
  }
  return id;
}

bool
nsLayoutUtils::ViewportHasDisplayPort(nsPresContext* aPresContext)
{
  nsIFrame* rootScrollFrame =
    aPresContext->PresShell()->GetRootScrollFrame();
  return rootScrollFrame &&
    nsLayoutUtils::HasDisplayPort(rootScrollFrame->GetContent());
}

bool
nsLayoutUtils::IsFixedPosFrameInDisplayPort(const nsIFrame* aFrame)
{
  // Fixed-pos frames are parented by the viewport frame or the page content frame.
  // We'll assume that printing/print preview don't have displayports for their
  // pages!
  nsIFrame* parent = aFrame->GetParent();
  if (!parent || parent->GetParent() ||
      aFrame->StyleDisplay()->mPosition != NS_STYLE_POSITION_FIXED) {
    return false;
  }
  return ViewportHasDisplayPort(aFrame->PresContext());
}

// 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);
    if (scrollableFrame) {
      ScrollStyles ss = scrollableFrame->GetScrollStyles();
      uint32_t directions = scrollableFrame->GetPerceivedScrollingDirections();
      if (aDirection == eVertical ?
          (ss.mVertical != NS_STYLE_OVERFLOW_HIDDEN &&
           (directions & nsIScrollableFrame::VERTICAL)) :
          (ss.mHorizontal != NS_STYLE_OVERFLOW_HIDDEN &&
           (directions & nsIScrollableFrame::HORIZONTAL)))
        return scrollableFrame;
    }
  }
  return nullptr;
}

// static
nsIScrollableFrame*
nsLayoutUtils::GetNearestScrollableFrame(nsIFrame* aFrame, uint32_t aFlags)
{
  NS_ASSERTION(aFrame, "GetNearestScrollableFrame expects a non-null frame");
  for (nsIFrame* f = aFrame; f; f = (aFlags & SCROLLABLE_SAME_DOC) ?
       f->GetParent() : nsLayoutUtils::GetCrossDocParentFrame(f)) {
    nsIScrollableFrame* scrollableFrame = do_QueryFrame(f);
    if (scrollableFrame) {
      if (aFlags & SCROLLABLE_ONLY_ASYNC_SCROLLABLE) {
        if (scrollableFrame->WantAsyncScroll()) {
          return scrollableFrame;
        }
      } else {
        ScrollStyles ss = scrollableFrame->GetScrollStyles();
        if ((aFlags & SCROLLABLE_INCLUDE_HIDDEN) ||
            ss.mVertical != NS_STYLE_OVERFLOW_HIDDEN ||
            ss.mHorizontal != NS_STYLE_OVERFLOW_HIDDEN) {
          return scrollableFrame;
        }
      }
      if (aFlags & SCROLLABLE_ALWAYS_MATCH_ROOT) {
        nsIPresShell* ps = f->PresShell();
        if (ps->GetRootScrollFrame() == f &&
            ps->GetDocument() && ps->GetDocument()->IsRootDisplayDocument()) {
          return scrollableFrame;
        }
      }
    }
    if ((aFlags & SCROLLABLE_FIXEDPOS_FINDS_ROOT) &&
        f->StyleDisplay()->mPosition == NS_STYLE_POSITION_FIXED &&
        nsLayoutUtils::IsReallyFixedPos(f)) {
      return f->PresShell()->GetRootScrollFrameAsScrollable();
    }
  }
  return nullptr;
}

// static
nsRect
nsLayoutUtils::GetScrolledRect(nsIFrame* aScrolledFrame,
                               const nsRect& aScrolledFrameOverflowArea,
                               const nsSize& aScrollPortSize,
                               uint8_t aDirection)
{
  WritingMode wm = aScrolledFrame->GetWritingMode();
  // Potentially override the frame's direction to use the direction found
  // by ScrollFrameHelper::GetScrolledFrameDir()
  wm.SetDirectionFromBidiLevel(aDirection == NS_STYLE_DIRECTION_RTL ? 1 : 0);

  nscoord x1 = aScrolledFrameOverflowArea.x,
          x2 = aScrolledFrameOverflowArea.XMost(),
          y1 = aScrolledFrameOverflowArea.y,
          y2 = aScrolledFrameOverflowArea.YMost();

  bool horizontal = !wm.IsVertical();

  // Clamp the horizontal start-edge (x1 or x2, depending whether the logical
  // axis that corresponds to horizontal progresses from L-R or R-L).
  // In horizontal writing mode, we need to check IsInlineReversed() to see
  // which side to clamp; in vertical mode, it depends on the block direction.
  if ((horizontal && !wm.IsInlineReversed()) || wm.IsVerticalLR()) {
    if (x1 < 0) {
      x1 = 0;
    }
  } else {
    if (x2 > aScrollPortSize.width) {
      x2 = aScrollPortSize.width;
    }
    // When the scrolled frame chooses a size larger than its available width
    // (because its padding alone is larger than the available width), we need
    // to keep the start-edge of the scroll frame anchored to the start-edge of
    // the scrollport.
    // When the scrolled frame is RTL, this means moving it in our left-based
    // coordinate system, so we need to compensate for its extra width here by
    // effectively repositioning the frame.
    nscoord extraWidth =
      std::max(0, aScrolledFrame->GetSize().width - aScrollPortSize.width);
    x2 += extraWidth;
  }

  // Similarly, clamp the vertical start-edge.
  // In horizontal writing mode, the block direction is always top-to-bottom;
  // in vertical writing mode, we need to check IsInlineReversed().
  if (horizontal || !wm.IsInlineReversed()) {
    if (y1 < 0) {
      y1 = 0;
    }
  } else {
    if (y2 > aScrollPortSize.height) {
      y2 = aScrollPortSize.height;
    }
    nscoord extraHeight =
      std::max(0, aScrolledFrame->GetSize().height - aScrollPortSize.height);
    y2 += extraHeight;
  }

  return nsRect(x1, y1, x2 - x1, y2 - y1);
}

//static
bool
nsLayoutUtils::HasPseudoStyle(nsIContent* aContent,
                              ComputedStyle* aComputedStyle,
                              CSSPseudoElementType aPseudoElement,
                              nsPresContext* aPresContext)
{
  MOZ_ASSERT(aPresContext, "Must have a prescontext");

  RefPtr<ComputedStyle> pseudoContext;
  if (aContent) {
    pseudoContext = aPresContext->StyleSet()->
      ProbePseudoElementStyle(*aContent->AsElement(), aPseudoElement,
                              aComputedStyle);
  }
  return pseudoContext != nullptr;
}

nsPoint
nsLayoutUtils::GetDOMEventCoordinatesRelativeTo(Event* aDOMEvent, nsIFrame* aFrame)
{
  if (!aDOMEvent)
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  WidgetEvent* event = aDOMEvent->WidgetEventPtr();
  if (!event)
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  return GetEventCoordinatesRelativeTo(event, aFrame);
}

nsPoint
nsLayoutUtils::GetEventCoordinatesRelativeTo(const WidgetEvent* aEvent,
                                             nsIFrame* aFrame)
{
  if (!aEvent || (aEvent->mClass != eMouseEventClass &&
                  aEvent->mClass != eMouseScrollEventClass &&
                  aEvent->mClass != eWheelEventClass &&
                  aEvent->mClass != eDragEventClass &&
                  aEvent->mClass != eSimpleGestureEventClass &&
                  aEvent->mClass != ePointerEventClass &&
                  aEvent->mClass != eGestureNotifyEventClass &&
                  aEvent->mClass != eTouchEventClass &&
                  aEvent->mClass != eQueryContentEventClass))
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);

  return GetEventCoordinatesRelativeTo(aEvent,
           aEvent->AsGUIEvent()->mRefPoint,
           aFrame);
}

nsPoint
nsLayoutUtils::GetEventCoordinatesRelativeTo(const WidgetEvent* aEvent,
                                             const LayoutDeviceIntPoint& aPoint,
                                             nsIFrame* aFrame)
{
  if (!aFrame) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  nsIWidget* widget = aEvent->AsGUIEvent()->mWidget;
  if (!widget) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  return GetEventCoordinatesRelativeTo(widget, aPoint, aFrame);
}

nsPoint
nsLayoutUtils::GetEventCoordinatesRelativeTo(nsIWidget* aWidget,
                                             const LayoutDeviceIntPoint& aPoint,
                                             nsIFrame* aFrame)
{
  if (!aFrame || !aWidget) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  nsView* view = aFrame->GetView();
  if (view) {
    nsIWidget* frameWidget = view->GetWidget();
    if (frameWidget && frameWidget == aWidget) {
      // Special case this cause it happens a lot.
      // This also fixes bug 664707, events in the extra-special case of select
      // dropdown popups that are transformed.
      nsPresContext* presContext = aFrame->PresContext();
      nsPoint pt(presContext->DevPixelsToAppUnits(aPoint.x),
                 presContext->DevPixelsToAppUnits(aPoint.y));
      pt = pt - view->ViewToWidgetOffset();
      pt = pt.RemoveResolution(GetCurrentAPZResolutionScale(presContext->PresShell()));
      return pt;
    }
  }

  /* If we walk up the frame tree and discover that any of the frames are
   * transformed, we need to do extra work to convert from the global
   * space to the local space.
   */
  nsIFrame* rootFrame = aFrame;
  bool transformFound = false;
  for (nsIFrame* f = aFrame; f; f = GetCrossDocParentFrame(f)) {
    if (f->IsTransformed()) {
      transformFound = true;
    }

    rootFrame = f;
  }

  nsView* rootView = rootFrame->GetView();
  if (!rootView) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  nsPoint widgetToView = TranslateWidgetToView(rootFrame->PresContext(),
                                               aWidget, aPoint, rootView);

  if (widgetToView == nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE)) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  // Convert from root document app units to app units of the document aFrame
  // is in.
  int32_t rootAPD = rootFrame->PresContext()->AppUnitsPerDevPixel();
  int32_t localAPD = aFrame->PresContext()->AppUnitsPerDevPixel();
  widgetToView = widgetToView.ScaleToOtherAppUnits(rootAPD, localAPD);
  nsIPresShell* shell = aFrame->PresShell();

  // XXX Bug 1224748 - Update nsLayoutUtils functions to correctly handle nsPresShell resolution
  widgetToView = widgetToView.RemoveResolution(GetCurrentAPZResolutionScale(shell));

  /* If we encountered a transform, we can't do simple arithmetic to figure
   * out how to convert back to aFrame's coordinates and must use the CTM.
   */
  if (transformFound || nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    return TransformRootPointToFrame(aFrame, widgetToView);
  }

  /* Otherwise, all coordinate systems are translations of one another,
   * so we can just subtract out the difference.
   */
  return widgetToView - aFrame->GetOffsetToCrossDoc(rootFrame);
}

nsIFrame*
nsLayoutUtils::GetPopupFrameForEventCoordinates(nsPresContext* aPresContext,
                                                const WidgetEvent* aEvent)
{
#ifdef MOZ_XUL
  nsXULPopupManager* pm = nsXULPopupManager::GetInstance();
  if (!pm) {
    return nullptr;
  }
  nsTArray<nsIFrame*> popups;
  pm->GetVisiblePopups(popups);
  uint32_t i;
  // Search from top to bottom
  for (i = 0; i < popups.Length(); i++) {
    nsIFrame* popup = popups[i];
    if (popup->PresContext()->GetRootPresContext() == aPresContext &&
        popup->GetScrollableOverflowRect().Contains(
          GetEventCoordinatesRelativeTo(aEvent, popup))) {
      return popup;
    }
  }
#endif
  return nullptr;
}

void
nsLayoutUtils::GetContainerAndOffsetAtEvent(nsIPresShell* aPresShell,
                                            const WidgetEvent* aEvent,
                                            nsIContent** aContainer,
                                            int32_t* aOffset)
{
  MOZ_ASSERT(aContainer || aOffset);

  if (aContainer) {
    *aContainer = nullptr;
  }
  if (aOffset) {
    *aOffset = 0;
  }

  if (!aPresShell) {
    return;
  }

  aPresShell->FlushPendingNotifications(FlushType::Layout);

  RefPtr<nsPresContext> presContext = aPresShell->GetPresContext();
  if (!presContext) {
    return;
  }

  nsIFrame* targetFrame = presContext->EventStateManager()->GetEventTarget();
  if (!targetFrame) {
    return;
  }

  nsPoint point =
    nsLayoutUtils::GetEventCoordinatesRelativeTo(aEvent, targetFrame);

  if (aContainer) {
    // TODO: This result may be useful to change to Selection.  However, this
    //       may return improper node (e.g., native anonymous node) for the
    //       Selection.  Perhaps, this should take Selection optionally and
    //       if it's specified, needs to check if it's proper for the
    //       Selection.
    nsCOMPtr<nsIContent> container =
      targetFrame->GetContentOffsetsFromPoint(point).content;
    if (container &&
        (!container->ChromeOnlyAccess() ||
         nsContentUtils::CanAccessNativeAnon())) {
      container.forget(aContainer);
    }
  }
  if (aOffset) {
    *aOffset = targetFrame->GetContentOffsetsFromPoint(point).offset;
  }
}

static void ConstrainToCoordValues(float& aStart, float& aSize)
{
  MOZ_ASSERT(aSize >= 0);

  // Here we try to make sure that the resulting nsRect will continue to cover
  // as much of the area that was covered by the original gfx Rect as possible.

  // We clamp the bounds of the rect to {nscoord_MIN,nscoord_MAX} since
  // nsRect::X/Y() and nsRect::XMost/YMost() can't return values outwith this
  // range:
  float end = aStart + aSize;
  aStart = clamped(aStart, float(nscoord_MIN), float(nscoord_MAX));
  end = clamped(end, float(nscoord_MIN), float(nscoord_MAX));

  aSize = end - aStart;

  // We must also clamp aSize to {0,nscoord_MAX} since nsRect::Width/Height()
  // can't return a value greater than nscoord_MAX. If aSize is greater than
  // nscoord_MAX then we reduce it to nscoord_MAX while keeping the rect
  // centered:
  if (aSize > nscoord_MAX) {
    float excess = aSize - nscoord_MAX;
    excess /= 2;
    aStart += excess;
    aSize = (float)nscoord_MAX;
  }
}

/**
 * Given a gfxFloat, constrains its value to be between nscoord_MIN and nscoord_MAX.
 *
 * @param aVal The value to constrain (in/out)
 */
static void ConstrainToCoordValues(gfxFloat& aVal)
{
  if (aVal <= nscoord_MIN)
    aVal = nscoord_MIN;
  else if (aVal >= nscoord_MAX)
    aVal = nscoord_MAX;
}

static void ConstrainToCoordValues(gfxFloat& aStart, gfxFloat& aSize)
{
  gfxFloat max = aStart + aSize;

  // Clamp the end points to within nscoord range
  ConstrainToCoordValues(aStart);
  ConstrainToCoordValues(max);

  aSize = max - aStart;
  // If the width if still greater than the max nscoord, then bring both
  // endpoints in by the same amount until it fits.
  if (aSize > nscoord_MAX) {
    gfxFloat excess = aSize - nscoord_MAX;
    excess /= 2;

    aStart += excess;
    aSize = nscoord_MAX;
  } else if (aSize < nscoord_MIN) {
    gfxFloat excess = aSize - nscoord_MIN;
    excess /= 2;

    aStart -= excess;
    aSize = nscoord_MIN;
  }
}

nsRect
nsLayoutUtils::RoundGfxRectToAppRect(const Rect &aRect, float aFactor)
{
  /* Get a new Rect whose units are app units by scaling by the specified factor. */
  Rect scaledRect = aRect;
  scaledRect.ScaleRoundOut(aFactor);

  /* We now need to constrain our results to the max and min values for coords. */
  ConstrainToCoordValues(scaledRect.x, scaledRect.width);
  ConstrainToCoordValues(scaledRect.y, scaledRect.height);

  /* Now typecast everything back.  This is guaranteed to be safe. */
  if (aRect.IsEmpty()) {
    return nsRect(nscoord(scaledRect.X()), nscoord(scaledRect.Y()), 0, 0);
  } else {
    return nsRect(nscoord(scaledRect.X()), nscoord(scaledRect.Y()),
                  nscoord(scaledRect.Width()), nscoord(scaledRect.Height()));
  }
}

nsRect
nsLayoutUtils::RoundGfxRectToAppRect(const gfxRect &aRect, float aFactor)
{
  /* Get a new gfxRect whose units are app units by scaling by the specified factor. */
  gfxRect scaledRect = aRect;
  scaledRect.ScaleRoundOut(aFactor);

  /* We now need to constrain our results to the max and min values for coords. */
  ConstrainToCoordValues(scaledRect.x, scaledRect.width);
  ConstrainToCoordValues(scaledRect.y, scaledRect.height);

  /* Now typecast everything back.  This is guaranteed to be safe. */
  if (aRect.IsEmpty()) {
    return nsRect(nscoord(scaledRect.X()), nscoord(scaledRect.Y()), 0, 0);
  } else {
    return nsRect(nscoord(scaledRect.X()), nscoord(scaledRect.Y()),
                  nscoord(scaledRect.Width()), nscoord(scaledRect.Height()));
  }
}


nsRegion
nsLayoutUtils::RoundedRectIntersectRect(const nsRect& aRoundedRect,
                                        const nscoord aRadii[8],
                                        const nsRect& aContainedRect)
{
  // rectFullHeight and rectFullWidth together will approximately contain
  // the total area of the frame minus the rounded corners.
  nsRect rectFullHeight = aRoundedRect;
  nscoord xDiff = std::max(aRadii[eCornerTopLeftX], aRadii[eCornerBottomLeftX]);
  rectFullHeight.x += xDiff;
  rectFullHeight.width -= std::max(aRadii[eCornerTopRightX],
                                   aRadii[eCornerBottomRightX]) + xDiff;
  nsRect r1;
  r1.IntersectRect(rectFullHeight, aContainedRect);

  nsRect rectFullWidth = aRoundedRect;
  nscoord yDiff = std::max(aRadii[eCornerTopLeftY], aRadii[eCornerTopRightY]);
  rectFullWidth.y += yDiff;
  rectFullWidth.height -= std::max(aRadii[eCornerBottomLeftY],
                                   aRadii[eCornerBottomRightY]) + yDiff;
  nsRect r2;
  r2.IntersectRect(rectFullWidth, aContainedRect);

  nsRegion result;
  result.Or(r1, r2);
  return result;
}

nsIntRegion
nsLayoutUtils::RoundedRectIntersectIntRect(const nsIntRect& aRoundedRect,
                                           const RectCornerRadii& aCornerRadii,
                                           const nsIntRect& aContainedRect)
{
  // rectFullHeight and rectFullWidth together will approximately contain
  // the total area of the frame minus the rounded corners.
  nsIntRect rectFullHeight = aRoundedRect;
  uint32_t xDiff = std::max(aCornerRadii.TopLeft().width,
                            aCornerRadii.BottomLeft().width);
  rectFullHeight.x += xDiff;
  rectFullHeight.width -= std::max(aCornerRadii.TopRight().width,
                                   aCornerRadii.BottomRight().width) + xDiff;
  nsIntRect r1;
  r1.IntersectRect(rectFullHeight, aContainedRect);

  nsIntRect rectFullWidth = aRoundedRect;
  uint32_t yDiff = std::max(aCornerRadii.TopLeft().height,
                            aCornerRadii.TopRight().height);
  rectFullWidth.y += yDiff;
  rectFullWidth.height -= std::max(aCornerRadii.BottomLeft().height,
                                   aCornerRadii.BottomRight().height) + yDiff;
  nsIntRect r2;
  r2.IntersectRect(rectFullWidth, aContainedRect);

  nsIntRegion result;
  result.Or(r1, r2);
  return result;
}

// Helper for RoundedRectIntersectsRect.
static bool
CheckCorner(nscoord aXOffset, nscoord aYOffset,
            nscoord aXRadius, nscoord aYRadius)
{
  MOZ_ASSERT(aXOffset > 0 && aYOffset > 0,
             "must not pass nonpositives to CheckCorner");
  MOZ_ASSERT(aXRadius >= 0 && aYRadius >= 0,
             "must not pass negatives to CheckCorner");

  // Avoid floating point math unless we're either (1) within the
  // quarter-ellipse area at the rounded corner or (2) outside the
  // rounding.
  if (aXOffset >= aXRadius || aYOffset >= aYRadius)
    return true;

  // Convert coordinates to a unit circle with (0,0) as the center of
  // curvature, and see if we're inside the circle or outside.
  float scaledX = float(aXRadius - aXOffset) / float(aXRadius);
  float scaledY = float(aYRadius - aYOffset) / float(aYRadius);
  return scaledX * scaledX + scaledY * scaledY < 1.0f;
}

bool
nsLayoutUtils::RoundedRectIntersectsRect(const nsRect& aRoundedRect,
                                         const nscoord aRadii[8],
                                         const nsRect& aTestRect)
{
  if (!aTestRect.Intersects(aRoundedRect))
    return false;

  // distances from this edge of aRoundedRect to opposite edge of aTestRect,
  // which we know are positive due to the Intersects check above.
  nsMargin insets;
  insets.top = aTestRect.YMost() - aRoundedRect.y;
  insets.right = aRoundedRect.XMost() - aTestRect.x;
  insets.bottom = aRoundedRect.YMost() - aTestRect.y;
  insets.left = aTestRect.XMost() - aRoundedRect.x;

  // Check whether the bottom-right corner of aTestRect is inside the
  // top left corner of aBounds when rounded by aRadii, etc.  If any
  // corner is not, then fail; otherwise succeed.
  return CheckCorner(insets.left, insets.top,
                     aRadii[eCornerTopLeftX],
                     aRadii[eCornerTopLeftY]) &&
         CheckCorner(insets.right, insets.top,
                     aRadii[eCornerTopRightX],
                     aRadii[eCornerTopRightY]) &&
         CheckCorner(insets.right, insets.bottom,
                     aRadii[eCornerBottomRightX],
                     aRadii[eCornerBottomRightY]) &&
         CheckCorner(insets.left, insets.bottom,
                     aRadii[eCornerBottomLeftX],
                     aRadii[eCornerBottomLeftY]);
}

nsRect
nsLayoutUtils::MatrixTransformRect(const nsRect &aBounds,
                                   const Matrix4x4 &aMatrix, float aFactor)
{
  RectDouble image = RectDouble(NSAppUnitsToDoublePixels(aBounds.x, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.y, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.width, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.height, aFactor));

  RectDouble maxBounds = RectDouble(double(nscoord_MIN) / aFactor * 0.5,
                                    double(nscoord_MIN) / aFactor * 0.5,
                                    double(nscoord_MAX) / aFactor,
                                    double(nscoord_MAX) / aFactor);

  image = aMatrix.TransformAndClipBounds(image, maxBounds);

  return RoundGfxRectToAppRect(ThebesRect(image), aFactor);
}

nsRect
nsLayoutUtils::MatrixTransformRect(const nsRect &aBounds,
                                   const Matrix4x4Flagged &aMatrix, float aFactor)
{
  RectDouble image = RectDouble(NSAppUnitsToDoublePixels(aBounds.x, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.y, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.width, aFactor),
                                NSAppUnitsToDoublePixels(aBounds.height, aFactor));

  RectDouble maxBounds = RectDouble(double(nscoord_MIN) / aFactor * 0.5,
                                    double(nscoord_MIN) / aFactor * 0.5,
                                    double(nscoord_MAX) / aFactor,
                                    double(nscoord_MAX) / aFactor);

  image = aMatrix.TransformAndClipBounds(image, maxBounds);

  return RoundGfxRectToAppRect(ThebesRect(image), aFactor);
}

nsPoint
nsLayoutUtils::MatrixTransformPoint(const nsPoint &aPoint,
                                    const Matrix4x4 &aMatrix, float aFactor)
{
  gfxPoint image = gfxPoint(NSAppUnitsToFloatPixels(aPoint.x, aFactor),
                            NSAppUnitsToFloatPixels(aPoint.y, aFactor));
  image = aMatrix.TransformPoint(image);
  return nsPoint(NSFloatPixelsToAppUnits(float(image.x), aFactor),
                 NSFloatPixelsToAppUnits(float(image.y), aFactor));
}

void
nsLayoutUtils::PostTranslate(Matrix4x4& aTransform, const nsPoint& aOrigin, float aAppUnitsPerPixel, bool aRounded)
{
  Point3D gfxOrigin =
    Point3D(NSAppUnitsToFloatPixels(aOrigin.x, aAppUnitsPerPixel),
            NSAppUnitsToFloatPixels(aOrigin.y, aAppUnitsPerPixel),
            0.0f);
  if (aRounded) {
    gfxOrigin.x = NS_round(gfxOrigin.x);
    gfxOrigin.y = NS_round(gfxOrigin.y);
  }
  aTransform.PostTranslate(gfxOrigin);
}

// We want to this return true for the scroll frame, but not the
// scrolled frame (which has the same content).
bool
nsLayoutUtils::FrameHasDisplayPort(nsIFrame* aFrame, const nsIFrame* aScrolledFrame)
{
  if (!aFrame->GetContent() || !HasDisplayPort(aFrame->GetContent())) {
    return false;
  }
  nsIScrollableFrame* sf = do_QueryFrame(aFrame);
  if (sf) {
    if (aScrolledFrame && aScrolledFrame != sf->GetScrolledFrame()) {
      return false;
    }
    return true;
  }
  return false;
}

Matrix4x4Flagged
nsLayoutUtils::GetTransformToAncestor(const nsIFrame *aFrame,
                                      const nsIFrame *aAncestor,
                                      uint32_t aFlags,
                                      nsIFrame** aOutAncestor)
{
  nsIFrame* parent;
  Matrix4x4Flagged ctm;
  if (aFrame == aAncestor) {
    return ctm;
  }
  ctm = aFrame->GetTransformMatrix(aAncestor, &parent, aFlags);
  while (parent && parent != aAncestor &&
    (!(aFlags & nsIFrame::STOP_AT_STACKING_CONTEXT_AND_DISPLAY_PORT) ||
      (!parent->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW) &&
       !parent->IsStackingContext() &&
       !FrameHasDisplayPort(parent)))) {
    if (!parent->Extend3DContext()) {
      ctm.ProjectTo2D();
    }
    ctm = ctm * parent->GetTransformMatrix(aAncestor, &parent, aFlags);
  }
  if (aOutAncestor) {
    *aOutAncestor = parent;
  }
  return ctm;
}

gfxSize
nsLayoutUtils::GetTransformToAncestorScale(nsIFrame* aFrame)
{
  Matrix4x4Flagged transform = GetTransformToAncestor(aFrame,
      nsLayoutUtils::GetDisplayRootFrame(aFrame));
  Matrix transform2D;
  if (transform.Is2D(&transform2D)) {
    return ThebesMatrix(transform2D).ScaleFactors(true);
  }
  return gfxSize(1, 1);
}

static Matrix4x4Flagged
GetTransformToAncestorExcludingAnimated(nsIFrame* aFrame,
                                        const nsIFrame* aAncestor)
{
  nsIFrame* parent;
  Matrix4x4Flagged ctm;
  if (aFrame == aAncestor) {
    return ctm;
  }
  if (ActiveLayerTracker::IsScaleSubjectToAnimation(aFrame)) {
    return ctm;
  }
  ctm = aFrame->GetTransformMatrix(aAncestor, &parent);
  while (parent && parent != aAncestor) {
    if (ActiveLayerTracker::IsScaleSubjectToAnimation(parent)) {
      return Matrix4x4Flagged();
    }
    if (!parent->Extend3DContext()) {
      ctm.ProjectTo2D();
    }
    ctm = ctm * parent->GetTransformMatrix(aAncestor, &parent);
  }
  return ctm;
}

gfxSize
nsLayoutUtils::GetTransformToAncestorScaleExcludingAnimated(nsIFrame* aFrame)
{
  Matrix4x4Flagged transform = GetTransformToAncestorExcludingAnimated(aFrame,
      nsLayoutUtils::GetDisplayRootFrame(aFrame));
  Matrix transform2D;
  if (transform.Is2D(&transform2D)) {
    return ThebesMatrix(transform2D).ScaleFactors(true);
  }
  return gfxSize(1, 1);
}

nsIFrame*
nsLayoutUtils::FindNearestCommonAncestorFrame(nsIFrame* aFrame1, nsIFrame* aFrame2)
{
  AutoTArray<nsIFrame*,100> ancestors1;
  AutoTArray<nsIFrame*,100> ancestors2;
  nsIFrame* commonAncestor = nullptr;
  if (aFrame1->PresContext() == aFrame2->PresContext()) {
    commonAncestor = aFrame1->PresShell()->GetRootFrame();
  }
  for (nsIFrame* f = aFrame1; f != commonAncestor;
       f = nsLayoutUtils::GetCrossDocParentFrame(f)) {
    ancestors1.AppendElement(f);
  }
  for (nsIFrame* f = aFrame2; f != commonAncestor;
       f = nsLayoutUtils::GetCrossDocParentFrame(f)) {
    ancestors2.AppendElement(f);
  }
  uint32_t minLengths = std::min(ancestors1.Length(), ancestors2.Length());
  for (uint32_t i = 1; i <= minLengths; ++i) {
    if (ancestors1[ancestors1.Length() - i] == ancestors2[ancestors2.Length() - i]) {
      commonAncestor = ancestors1[ancestors1.Length() - i];
    } else {
      break;
    }
  }
  return commonAncestor;
}

nsLayoutUtils::TransformResult
nsLayoutUtils::TransformPoints(nsIFrame* aFromFrame, nsIFrame* aToFrame,
                               uint32_t aPointCount, CSSPoint* aPoints)
{
  nsIFrame* nearestCommonAncestor = FindNearestCommonAncestorFrame(aFromFrame, aToFrame);
  if (!nearestCommonAncestor) {
    return NO_COMMON_ANCESTOR;
  }
  Matrix4x4Flagged downToDest = GetTransformToAncestor(aToFrame, nearestCommonAncestor);
  if (downToDest.IsSingular()) {
    return NONINVERTIBLE_TRANSFORM;
  }
  downToDest.Invert();
  Matrix4x4Flagged upToAncestor = GetTransformToAncestor(aFromFrame, nearestCommonAncestor);
  CSSToLayoutDeviceScale devPixelsPerCSSPixelFromFrame =
      aFromFrame->PresContext()->CSSToDevPixelScale();
  CSSToLayoutDeviceScale devPixelsPerCSSPixelToFrame =
      aToFrame->PresContext()->CSSToDevPixelScale();
  for (uint32_t i = 0; i < aPointCount; ++i) {
    LayoutDevicePoint devPixels = aPoints[i] * devPixelsPerCSSPixelFromFrame;
    // What should the behaviour be if some of the points aren't invertible
    // and others are? Just assume all points are for now.
    Point toDevPixels = downToDest.ProjectPoint(
        (upToAncestor.TransformPoint(Point(devPixels.x, devPixels.y)))).As2DPoint();
    // Divide here so that when the devPixelsPerCSSPixels are the same, we get the correct
    // answer instead of some inaccuracy multiplying a number by its reciprocal.
    aPoints[i] = LayoutDevicePoint(toDevPixels.x, toDevPixels.y) /
        devPixelsPerCSSPixelToFrame;
  }
  return TRANSFORM_SUCCEEDED;
}

nsLayoutUtils::TransformResult
nsLayoutUtils::TransformPoint(nsIFrame* aFromFrame, nsIFrame* aToFrame,
                              nsPoint& aPoint)
{
  nsIFrame* nearestCommonAncestor = FindNearestCommonAncestorFrame(aFromFrame, aToFrame);
  if (!nearestCommonAncestor) {
    return NO_COMMON_ANCESTOR;
  }
  Matrix4x4Flagged downToDest = GetTransformToAncestor(aToFrame, nearestCommonAncestor);
  if (downToDest.IsSingular()) {
    return NONINVERTIBLE_TRANSFORM;
  }
  downToDest.Invert();
  Matrix4x4Flagged upToAncestor = GetTransformToAncestor(aFromFrame, nearestCommonAncestor);

  float devPixelsPerAppUnitFromFrame =
    1.0f / aFromFrame->PresContext()->AppUnitsPerDevPixel();
  float devPixelsPerAppUnitToFrame =
    1.0f / aToFrame->PresContext()->AppUnitsPerDevPixel();
  Point4D toDevPixels = downToDest.ProjectPoint(
      upToAncestor.TransformPoint(Point(aPoint.x * devPixelsPerAppUnitFromFrame,
                                        aPoint.y * devPixelsPerAppUnitFromFrame)));
  if (!toDevPixels.HasPositiveWCoord()) {
    // Not strictly true, but we failed to get a valid point in this
    // coordinate space.
    return NONINVERTIBLE_TRANSFORM;
  }
  aPoint.x = NSToCoordRound(toDevPixels.x / devPixelsPerAppUnitToFrame);
  aPoint.y = NSToCoordRound(toDevPixels.y / devPixelsPerAppUnitToFrame);
  return TRANSFORM_SUCCEEDED;
}

nsLayoutUtils::TransformResult
nsLayoutUtils::TransformRect(nsIFrame* aFromFrame, nsIFrame* aToFrame,
                             nsRect& aRect)
{
  nsIFrame* nearestCommonAncestor = FindNearestCommonAncestorFrame(aFromFrame, aToFrame);
  if (!nearestCommonAncestor) {
    return NO_COMMON_ANCESTOR;
  }
  Matrix4x4Flagged downToDest = GetTransformToAncestor(aToFrame, nearestCommonAncestor);
  if (downToDest.IsSingular()) {
    return NONINVERTIBLE_TRANSFORM;
  }
  downToDest.Invert();
  Matrix4x4Flagged upToAncestor = GetTransformToAncestor(aFromFrame, nearestCommonAncestor);

  float devPixelsPerAppUnitFromFrame =
    1.0f / aFromFrame->PresContext()->AppUnitsPerDevPixel();
  float devPixelsPerAppUnitToFrame =
    1.0f / aToFrame->PresContext()->AppUnitsPerDevPixel();
  gfx::Rect toDevPixels = downToDest.ProjectRectBounds(
    upToAncestor.ProjectRectBounds(
      gfx::Rect(aRect.x * devPixelsPerAppUnitFromFrame,
                aRect.y * devPixelsPerAppUnitFromFrame,
                aRect.width * devPixelsPerAppUnitFromFrame,
                aRect.height * devPixelsPerAppUnitFromFrame),
      Rect(-std::numeric_limits<Float>::max() * 0.5f,
           -std::numeric_limits<Float>::max() * 0.5f,
           std::numeric_limits<Float>::max(),
           std::numeric_limits<Float>::max())),
    Rect(-std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame * 0.5f,
         -std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame * 0.5f,
         std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame,
         std::numeric_limits<Float>::max() * devPixelsPerAppUnitFromFrame));
  aRect.x = NSToCoordRound(toDevPixels.x / devPixelsPerAppUnitToFrame);
  aRect.y = NSToCoordRound(toDevPixels.y / devPixelsPerAppUnitToFrame);
  aRect.width = NSToCoordRound(toDevPixels.width / devPixelsPerAppUnitToFrame);
  aRect.height = NSToCoordRound(toDevPixels.height / devPixelsPerAppUnitToFrame);
  return TRANSFORM_SUCCEEDED;
}

nsRect
nsLayoutUtils::GetRectRelativeToFrame(Element* aElement, nsIFrame* aFrame)
{
  if (!aElement || !aFrame) {
    return nsRect();
  }

  nsIFrame* frame = aElement->GetPrimaryFrame();
  if (!frame) {
    return nsRect();
  }

  nsRect rect = frame->GetRectRelativeToSelf();
  nsLayoutUtils::TransformResult rv =
    nsLayoutUtils::TransformRect(frame, aFrame, rect);
  if (rv != nsLayoutUtils::TRANSFORM_SUCCEEDED) {
    return nsRect();
  }

  return rect;
}

bool
nsLayoutUtils::ContainsPoint(const nsRect& aRect, const nsPoint& aPoint,
                             nscoord aInflateSize)
{
  nsRect rect = aRect;
  rect.Inflate(aInflateSize);
  return rect.Contains(aPoint);
}

nsRect
nsLayoutUtils::ClampRectToScrollFrames(nsIFrame* aFrame, const nsRect& aRect)
{
  nsIFrame* closestScrollFrame =
    nsLayoutUtils::GetClosestFrameOfType(aFrame, LayoutFrameType::Scroll);

  nsRect resultRect = aRect;

  while (closestScrollFrame) {
    nsIScrollableFrame* sf = do_QueryFrame(closestScrollFrame);

    nsRect scrollPortRect = sf->GetScrollPortRect();
    nsLayoutUtils::TransformRect(closestScrollFrame, aFrame, scrollPortRect);

    resultRect = resultRect.Intersect(scrollPortRect);

    // Check whether aRect is visible in the scroll frame or not.
    if (resultRect.IsEmpty()) {
      break;
    }

    // Get next ancestor scroll frame.
    closestScrollFrame = nsLayoutUtils::GetClosestFrameOfType(
      closestScrollFrame->GetParent(), LayoutFrameType::Scroll);
  }

  return resultRect;
}

bool
nsLayoutUtils::GetLayerTransformForFrame(nsIFrame* aFrame,
                                         Matrix4x4Flagged* aTransform)
{
  // FIXME/bug 796690: we can sometimes compute a transform in these
  // cases, it just increases complexity considerably.  Punt for now.
  if (aFrame->Extend3DContext() || aFrame->HasTransformGetter()) {
    return false;
  }

  nsIFrame* root = nsLayoutUtils::GetDisplayRootFrame(aFrame);
  if (root->HasAnyStateBits(NS_FRAME_UPDATE_LAYER_TREE)) {
    // Content may have been invalidated, so we can't reliably compute
    // the "layer transform" in general.
    return false;
  }
  // If the caller doesn't care about the value, early-return to skip
  // overhead below.
  if (!aTransform) {
    return true;
  }

  nsDisplayListBuilder builder(root,
                               nsDisplayListBuilderMode::TRANSFORM_COMPUTATION,
                               false/*don't build caret*/);
  builder.BeginFrame();
  nsDisplayList list;
  nsDisplayTransform* item =
    MakeDisplayItem<nsDisplayTransform>(&builder, aFrame, &list, nsRect());

  *aTransform = item->GetTransform();
  item->Destroy(&builder);

  builder.EndFrame();

  return true;
}

static bool
TransformGfxPointFromAncestor(nsIFrame *aFrame,
                              const Point &aPoint,
                              nsIFrame *aAncestor,
                              Point* aOut)
{
  Matrix4x4Flagged ctm = nsLayoutUtils::GetTransformToAncestor(aFrame, aAncestor);
  ctm.Invert();
  Point4D point = ctm.ProjectPoint(aPoint);
  if (!point.HasPositiveWCoord()) {
    return false;
  }
  *aOut = point.As2DPoint();
  return true;
}

static Rect
TransformGfxRectToAncestor(const nsIFrame *aFrame,
                           const Rect &aRect,
                           const nsIFrame *aAncestor,
                           bool* aPreservesAxisAlignedRectangles = nullptr,
                           Maybe<Matrix4x4Flagged>* aMatrixCache = nullptr,
                           bool aStopAtStackingContextAndDisplayPortAndOOFFrame = false,
                           nsIFrame** aOutAncestor = nullptr)
{
  Matrix4x4Flagged ctm;
  if (aMatrixCache && *aMatrixCache) {
    // We are given a matrix to use, so use it
    ctm = aMatrixCache->value();
  } else {
    // Else, compute it
    uint32_t flags = 0;
    if (aStopAtStackingContextAndDisplayPortAndOOFFrame) {
      flags |= nsIFrame::STOP_AT_STACKING_CONTEXT_AND_DISPLAY_PORT;
    }
    ctm = nsLayoutUtils::GetTransformToAncestor(aFrame, aAncestor, flags, aOutAncestor);
    if (aMatrixCache) {
      // and put it in the cache, if provided
      *aMatrixCache = Some(ctm);
    }
  }
  // Fill out the axis-alignment flag
  if (aPreservesAxisAlignedRectangles) {
    Matrix matrix2d;
    *aPreservesAxisAlignedRectangles =
      ctm.Is2D(&matrix2d) && matrix2d.PreservesAxisAlignedRectangles();
  }
  const nsIFrame* ancestor = aOutAncestor ? *aOutAncestor : aAncestor;
  float factor = ancestor->PresContext()->AppUnitsPerDevPixel();
  Rect maxBounds = Rect(float(nscoord_MIN) / factor * 0.5,
                        float(nscoord_MIN) / factor * 0.5,
                        float(nscoord_MAX) / factor,
                        float(nscoord_MAX) / factor);
  return ctm.TransformAndClipBounds(aRect, maxBounds);
}

static SVGTextFrame*
GetContainingSVGTextFrame(const nsIFrame* aFrame)
{
  if (!nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    return nullptr;
  }

  return static_cast<SVGTextFrame*>(nsLayoutUtils::GetClosestFrameOfType(
    aFrame->GetParent(), LayoutFrameType::SVGText));
}

nsPoint
nsLayoutUtils::TransformAncestorPointToFrame(nsIFrame* aFrame,
                                             const nsPoint& aPoint,
                                             nsIFrame* aAncestor)
{
    SVGTextFrame* text = GetContainingSVGTextFrame(aFrame);

    float factor = aFrame->PresContext()->AppUnitsPerDevPixel();
    Point result(NSAppUnitsToFloatPixels(aPoint.x, factor),
                 NSAppUnitsToFloatPixels(aPoint.y, factor));

    if (text) {
        if (!TransformGfxPointFromAncestor(text, result, aAncestor, &result)) {
            return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
        }
        result = text->TransformFramePointToTextChild(result, aFrame);
    } else {
        if (!TransformGfxPointFromAncestor(aFrame, result, nullptr, &result)) {
            return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
        }
    }

    return nsPoint(NSFloatPixelsToAppUnits(float(result.x), factor),
                   NSFloatPixelsToAppUnits(float(result.y), factor));
}

nsRect
nsLayoutUtils::TransformFrameRectToAncestor(const nsIFrame* aFrame,
                                            const nsRect& aRect,
                                            const nsIFrame* aAncestor,
                                            bool* aPreservesAxisAlignedRectangles /* = nullptr */,
                                            Maybe<Matrix4x4Flagged>* aMatrixCache /* = nullptr */,
                                            bool aStopAtStackingContextAndDisplayPortAndOOFFrame /* = false */,
                                            nsIFrame** aOutAncestor /* = nullptr */)
{
  SVGTextFrame* text = GetContainingSVGTextFrame(aFrame);

  float srcAppUnitsPerDevPixel = aFrame->PresContext()->AppUnitsPerDevPixel();
  Rect result;

  if (text) {
    result = ToRect(text->TransformFrameRectFromTextChild(aRect, aFrame));
    result = TransformGfxRectToAncestor(text, result, aAncestor,
                                        nullptr, aMatrixCache,
                                        aStopAtStackingContextAndDisplayPortAndOOFFrame, aOutAncestor);
    // TransformFrameRectFromTextChild could involve any kind of transform, we
    // could drill down into it to get an answer out of it but we don't yet.
    if (aPreservesAxisAlignedRectangles)
      *aPreservesAxisAlignedRectangles = false;
  } else {
    result = Rect(NSAppUnitsToFloatPixels(aRect.x, srcAppUnitsPerDevPixel),
                  NSAppUnitsToFloatPixels(aRect.y, srcAppUnitsPerDevPixel),
                  NSAppUnitsToFloatPixels(aRect.width, srcAppUnitsPerDevPixel),
                  NSAppUnitsToFloatPixels(aRect.height, srcAppUnitsPerDevPixel));
    result = TransformGfxRectToAncestor(aFrame, result, aAncestor,
                                        aPreservesAxisAlignedRectangles, aMatrixCache,
                                        aStopAtStackingContextAndDisplayPortAndOOFFrame, aOutAncestor);
  }

  float destAppUnitsPerDevPixel = aAncestor->PresContext()->AppUnitsPerDevPixel();
  return nsRect(NSFloatPixelsToAppUnits(float(result.x), destAppUnitsPerDevPixel),
                NSFloatPixelsToAppUnits(float(result.y), destAppUnitsPerDevPixel),
                NSFloatPixelsToAppUnits(float(result.width), destAppUnitsPerDevPixel),
                NSFloatPixelsToAppUnits(float(result.height), destAppUnitsPerDevPixel));
}

static LayoutDeviceIntPoint GetWidgetOffset(nsIWidget* aWidget, nsIWidget*& aRootWidget) {
  LayoutDeviceIntPoint offset(0, 0);
  while ((aWidget->WindowType() == eWindowType_child ||
          aWidget->IsPlugin())) {
    nsIWidget* parent = aWidget->GetParent();
    if (!parent) {
      break;
    }
    LayoutDeviceIntRect bounds = aWidget->GetBounds();
    offset += bounds.TopLeft();
    aWidget = parent;
  }
  aRootWidget = aWidget;
  return offset;
}

LayoutDeviceIntPoint
nsLayoutUtils::WidgetToWidgetOffset(nsIWidget* aFrom, nsIWidget* aTo) {
  nsIWidget* fromRoot;
  LayoutDeviceIntPoint fromOffset = GetWidgetOffset(aFrom, fromRoot);
  nsIWidget* toRoot;
  LayoutDeviceIntPoint toOffset = GetWidgetOffset(aTo, toRoot);

  if (fromRoot == toRoot) {
    return fromOffset - toOffset;
  }
  return aFrom->WidgetToScreenOffset() - aTo->WidgetToScreenOffset();
}

nsPoint
nsLayoutUtils::TranslateWidgetToView(nsPresContext* aPresContext,
                                     nsIWidget* aWidget, const LayoutDeviceIntPoint& aPt,
                                     nsView* aView)
{
  nsPoint viewOffset;
  nsIWidget* viewWidget = aView->GetNearestWidget(&viewOffset);
  if (!viewWidget) {
    return nsPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  LayoutDeviceIntPoint widgetPoint = aPt + WidgetToWidgetOffset(aWidget, viewWidget);
  nsPoint widgetAppUnits(aPresContext->DevPixelsToAppUnits(widgetPoint.x),
                         aPresContext->DevPixelsToAppUnits(widgetPoint.y));
  return widgetAppUnits - viewOffset;
}

LayoutDeviceIntPoint
nsLayoutUtils::TranslateViewToWidget(nsPresContext* aPresContext,
                                     nsView* aView, nsPoint aPt,
                                     nsIWidget* aWidget)
{
  nsPoint viewOffset;
  nsIWidget* viewWidget = aView->GetNearestWidget(&viewOffset);
  if (!viewWidget) {
    return LayoutDeviceIntPoint(NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE);
  }

  nsPoint pt = (aPt +
  viewOffset).ApplyResolution(GetCurrentAPZResolutionScale(aPresContext->PresShell()));
  LayoutDeviceIntPoint relativeToViewWidget(aPresContext->AppUnitsToDevPixels(pt.x),
                                            aPresContext->AppUnitsToDevPixels(pt.y));
  return relativeToViewWidget + WidgetToWidgetOffset(viewWidget, aWidget);
}

// Combine aNewBreakType with aOrigBreakType, but limit the break types
// to StyleClear::Left, Right, Both.
StyleClear
nsLayoutUtils::CombineBreakType(StyleClear aOrigBreakType,
                                StyleClear aNewBreakType)
{
  StyleClear breakType = aOrigBreakType;
  switch(breakType) {
    case StyleClear::Left:
      if (StyleClear::Right == aNewBreakType ||
          StyleClear::Both == aNewBreakType) {
        breakType = StyleClear::Both;
      }
      break;
    case StyleClear::Right:
      if (StyleClear::Left == aNewBreakType ||
          StyleClear::Both == aNewBreakType) {
        breakType = StyleClear::Both;
      }
      break;
    case StyleClear::None:
      if (StyleClear::Left == aNewBreakType ||
          StyleClear::Right == aNewBreakType ||
          StyleClear::Both == aNewBreakType) {
        breakType = aNewBreakType;
      }
      break;
    default:
      break;
  }
  return breakType;
}

#ifdef MOZ_DUMP_PAINTING
#include <stdio.h>

static bool gDumpEventList = false;

// nsLayoutUtils::PaintFrame() can call itself recursively, so rather than
// maintaining a single paint count, we need a stack.
StaticAutoPtr<nsTArray<int>> gPaintCountStack;

struct AutoNestedPaintCount {
  AutoNestedPaintCount() {
    gPaintCountStack->AppendElement(0);
  }
  ~AutoNestedPaintCount() {
    gPaintCountStack->RemoveLastElement();
  }
};

#endif

nsIFrame*
nsLayoutUtils::GetFrameForPoint(nsIFrame* aFrame, nsPoint aPt, uint32_t aFlags)
{
  AUTO_PROFILER_LABEL("nsLayoutUtils::GetFrameForPoint", LAYOUT);

  nsresult rv;
  AutoTArray<nsIFrame*,8> outFrames;
  rv = GetFramesForArea(aFrame, nsRect(aPt, nsSize(1, 1)), outFrames, aFlags);
  NS_ENSURE_SUCCESS(rv, nullptr);
  return outFrames.Length() ? outFrames.ElementAt(0) : nullptr;
}

nsresult
nsLayoutUtils::GetFramesForArea(nsIFrame* aFrame, const nsRect& aRect,
                                nsTArray<nsIFrame*> &aOutFrames,
                                uint32_t aFlags)
{
  AUTO_PROFILER_LABEL("nsLayoutUtils::GetFramesForArea", LAYOUT);

  nsDisplayListBuilder builder(aFrame,
                               nsDisplayListBuilderMode::EVENT_DELIVERY,
                               false);
  builder.BeginFrame();
  nsDisplayList list;

  if (aFlags & IGNORE_PAINT_SUPPRESSION) {
    builder.IgnorePaintSuppression();
  }

  if (aFlags & IGNORE_ROOT_SCROLL_FRAME) {
    nsIFrame* rootScrollFrame = aFrame->PresShell()->GetRootScrollFrame();
    if (rootScrollFrame) {
      builder.SetIgnoreScrollFrame(rootScrollFrame);
    }
  }
  if (aFlags & IGNORE_CROSS_DOC) {
    builder.SetDescendIntoSubdocuments(false);
  }

  builder.SetHitTestIsForVisibility(aFlags & ONLY_VISIBLE);

  builder.EnterPresShell(aFrame);

  builder.SetVisibleRect(aRect);
  builder.SetDirtyRect(aRect);

  aFrame->BuildDisplayListForStackingContext(&builder, &list);
  builder.LeavePresShell(aFrame, nullptr);

#ifdef MOZ_DUMP_PAINTING
  if (gDumpEventList) {
    fprintf_stderr(stderr, "Event handling --- (%d,%d):\n", aRect.x, aRect.y);

    std::stringstream ss;
    nsFrame::PrintDisplayList(&builder, list, ss);
    print_stderr(ss);
  }
#endif

  nsDisplayItem::HitTestState hitTestState;
  list.HitTest(&builder, aRect, &hitTestState, &aOutFrames);
  list.DeleteAll(&builder);
  builder.EndFrame();
  return NS_OK;
}

// aScrollFrameAsScrollable must be non-nullptr and queryable to an nsIFrame
FrameMetrics
nsLayoutUtils::CalculateBasicFrameMetrics(nsIScrollableFrame* aScrollFrame) {
  nsIFrame* frame = do_QueryFrame(aScrollFrame);
  MOZ_ASSERT(frame);

  // Calculate the metrics necessary for calculating the displayport.
  // This code has a lot in common with the code in ComputeFrameMetrics();
  // we may want to refactor this at some point.
  FrameMetrics metrics;
  nsPresContext* presContext = frame->PresContext();
  nsIPresShell* presShell = presContext->PresShell();
  CSSToLayoutDeviceScale deviceScale = presContext->CSSToDevPixelScale();
  float resolution = 1.0f;
  if (frame == presShell->GetRootScrollFrame()) {
    // Only the root scrollable frame for a given presShell should pick up
    // the presShell's resolution. All the other frames are 1.0.
    resolution = presShell->GetResolution();
  }
  // Note: unlike in ComputeFrameMetrics(), we don't know the full cumulative
  // resolution including FrameMetrics::mExtraResolution, because layout hasn't
  // chosen a resolution to paint at yet. However, the display port calculation
  // divides out mExtraResolution anyways, so we get the correct result by
  // setting the mCumulativeResolution to everything except the extra resolution
  // and leaving mExtraResolution at 1.
  LayoutDeviceToLayerScale2D cumulativeResolution(
      presShell->GetCumulativeResolution()
    * nsLayoutUtils::GetTransformToAncestorScale(frame));

  LayerToParentLayerScale layerToParentLayerScale(1.0f);
  metrics.SetDevPixelsPerCSSPixel(deviceScale);
  metrics.SetPresShellResolution(resolution);
  metrics.SetCumulativeResolution(cumulativeResolution);
  metrics.SetZoom(deviceScale * cumulativeResolution * layerToParentLayerScale);

  // Only the size of the composition bounds is relevant to the
  // displayport calculation, not its origin.
  nsSize compositionSize = nsLayoutUtils::CalculateCompositionSizeForFrame(frame);
  LayoutDeviceToParentLayerScale2D compBoundsScale;
  if (frame == presShell->GetRootScrollFrame() && presContext->IsRootContentDocument()) {
    if (presContext->GetParentPresContext()) {
      float res = presContext->GetParentPresContext()->PresShell()->GetCumulativeResolution();
      compBoundsScale = LayoutDeviceToParentLayerScale2D(
          LayoutDeviceToParentLayerScale(res));
    }
  } else {
    compBoundsScale = cumulativeResolution * layerToParentLayerScale;
  }
  metrics.SetCompositionBounds(
      LayoutDeviceRect::FromAppUnits(nsRect(nsPoint(0, 0), compositionSize),
                                       presContext->AppUnitsPerDevPixel())
      * compBoundsScale);

  metrics.SetRootCompositionSize(
      nsLayoutUtils::CalculateRootCompositionSize(frame, false, metrics));

  metrics.SetScrollOffset(CSSPoint::FromAppUnits(
      aScrollFrame->GetScrollPosition()));

  metrics.SetScrollableRect(CSSRect::FromAppUnits(
      nsLayoutUtils::CalculateScrollableRectForFrame(aScrollFrame, nullptr)));

  return metrics;
}

bool
nsLayoutUtils::CalculateAndSetDisplayPortMargins(nsIScrollableFrame* aScrollFrame,
                                                 RepaintMode aRepaintMode) {
  nsIFrame* frame = do_QueryFrame(aScrollFrame);
  MOZ_ASSERT(frame);
  nsIContent* content = frame->GetContent();
  MOZ_ASSERT(content);

  FrameMetrics metrics = CalculateBasicFrameMetrics(aScrollFrame);
  ScreenMargin displayportMargins = apz::CalculatePendingDisplayPort(
      metrics, ParentLayerPoint(0.0f, 0.0f));
  nsIPresShell* presShell = frame->PresContext()->GetPresShell();
  return nsLayoutUtils::SetDisplayPortMargins(
      content, presShell, displayportMargins, 0, aRepaintMode);
}

bool
nsLayoutUtils::MaybeCreateDisplayPort(nsDisplayListBuilder& aBuilder,
                                      nsIFrame* aScrollFrame,
                                      RepaintMode aRepaintMode)
{
  nsIContent* content = aScrollFrame->GetContent();
  nsIScrollableFrame* scrollableFrame = do_QueryFrame(aScrollFrame);
  if (!content || !scrollableFrame) {
    return false;
  }

  bool haveDisplayPort = HasDisplayPort(content);

  // We perform an optimization where we ensure that at least one
  // async-scrollable frame (i.e. one that WantsAsyncScroll()) has a displayport.
  // If that's not the case yet, and we are async-scrollable, we will get a
  // displayport.
  if (aBuilder.IsPaintingToWindow() &&
      nsLayoutUtils::AsyncPanZoomEnabled(aScrollFrame) &&
      !aBuilder.HaveScrollableDisplayPort() &&
      scrollableFrame->WantAsyncScroll()) {

    // If we don't already have a displayport, calculate and set one.
    if (!haveDisplayPort) {
      CalculateAndSetDisplayPortMargins(scrollableFrame, aRepaintMode);
#ifdef DEBUG
      haveDisplayPort = HasDisplayPort(content);
      MOZ_ASSERT(haveDisplayPort, "should have a displayport after having just set it");
#endif
    }

    // Record that the we now have a scrollable display port.
    aBuilder.SetHaveScrollableDisplayPort();
    return true;
  }
  return false;
}

nsIScrollableFrame*
nsLayoutUtils::GetAsyncScrollableAncestorFrame(nsIFrame* aTarget)
{
  uint32_t flags = nsLayoutUtils::SCROLLABLE_ALWAYS_MATCH_ROOT
                 | nsLayoutUtils::SCROLLABLE_ONLY_ASYNC_SCROLLABLE
                 | nsLayoutUtils::SCROLLABLE_FIXEDPOS_FINDS_ROOT;
  return nsLayoutUtils::GetNearestScrollableFrame(aTarget, flags);
}

void
nsLayoutUtils::SetZeroMarginDisplayPortOnAsyncScrollableAncestors(nsIFrame* aFrame,
                                                                  RepaintMode aRepaintMode)
{
  nsIFrame* frame = aFrame;
  while (frame) {
    frame = nsLayoutUtils::GetCrossDocParentFrame(frame);
    if (!frame) {
      break;
    }
    nsIScrollableFrame* scrollAncestor = GetAsyncScrollableAncestorFrame(frame);
    if (!scrollAncestor) {
      break;
    }
    frame = do_QueryFrame(scrollAncestor);
    MOZ_ASSERT(frame);
    MOZ_ASSERT(scrollAncestor->WantAsyncScroll() ||
      frame->PresShell()->GetRootScrollFrame() == frame);
    if (nsLayoutUtils::AsyncPanZoomEnabled(frame) &&
        !nsLayoutUtils::HasDisplayPort(frame->GetContent())) {
      nsLayoutUtils::SetDisplayPortMargins(
        frame->GetContent(), frame->PresShell(), ScreenMargin(), 0,
        aRepaintMode);
    }
  }
}

bool
nsLayoutUtils::MaybeCreateDisplayPortInFirstScrollFrameEncountered(
  nsIFrame* aFrame, nsDisplayListBuilder& aBuilder)
{
  nsIScrollableFrame* sf = do_QueryFrame(aFrame);
  if (sf) {
    if (MaybeCreateDisplayPort(aBuilder, aFrame, RepaintMode::Repaint)) {
      return true;
    }
  }
  if (aFrame->IsPlaceholderFrame()) {
    nsPlaceholderFrame* placeholder = static_cast<nsPlaceholderFrame*>(aFrame);
    if (MaybeCreateDisplayPortInFirstScrollFrameEncountered(
          placeholder->GetOutOfFlowFrame(), aBuilder)) {
      return true;
    }
  }
  if (aFrame->IsSubDocumentFrame()) {
    nsIPresShell* presShell =
      static_cast<nsSubDocumentFrame*>(aFrame)->GetSubdocumentPresShellForPainting(0);
    nsIFrame* root = presShell ? presShell->GetRootFrame() : nullptr;
    if (root) {
      if (MaybeCreateDisplayPortInFirstScrollFrameEncountered(root, aBuilder)) {
        return true;
      }
    }
  }
  if (aFrame->IsDeckFrame()) {
    // only descend the visible card of a decks
    nsIFrame* child = static_cast<nsDeckFrame*>(aFrame)->GetSelectedBox();
    if (child) {
      return MaybeCreateDisplayPortInFirstScrollFrameEncountered(child, aBuilder);
    }
  }

  for (nsIFrame* child : aFrame->PrincipalChildList()) {
    if (MaybeCreateDisplayPortInFirstScrollFrameEncountered(child, aBuilder)) {
      return true;
    }
  }

  return false;
}

void
nsLayoutUtils::ExpireDisplayPortOnAsyncScrollableAncestor(nsIFrame* aFrame)
{
  nsIFrame* frame = aFrame;
  while (frame) {
    frame = nsLayoutUtils::GetCrossDocParentFrame(frame);
    if (!frame) {
      break;
    }
    nsIScrollableFrame* scrollAncestor = GetAsyncScrollableAncestorFrame(frame);
    if (!scrollAncestor) {
      break;
    }
    frame = do_QueryFrame(scrollAncestor);
    MOZ_ASSERT(frame);
    if (!frame) {
      break;
    }
    MOZ_ASSERT(scrollAncestor->WantAsyncScroll() ||
      frame->PresShell()->GetRootScrollFrame() == frame);
    if (nsLayoutUtils::HasDisplayPort(frame->GetContent())) {
      scrollAncestor->TriggerDisplayPortExpiration();
      // Stop after the first trigger. If it failed, there's no point in
      // continuing because all the rest of the frames we encounter are going
      // to be ancestors of |scrollAncestor| which will keep its displayport.
      // If the trigger succeeded, we stop because when the trigger executes
      // it will call this function again to trigger the next ancestor up the
      // chain.
      break;
    }
  }
}

void
nsLayoutUtils::AddExtraBackgroundItems(nsDisplayListBuilder& aBuilder,
                                       nsDisplayList& aList,
                                       nsIFrame* aFrame,
                                       const nsRect& aCanvasArea,
                                       const nsRegion& aVisibleRegion,
                                       nscolor aBackstop)
{
  LayoutFrameType frameType = aFrame->Type();
  nsPresContext* presContext = aFrame->PresContext();
  nsIPresShell* presShell = presContext->PresShell();

  // For the viewport frame in print preview/page layout we want to paint
  // the grey background behind the page, not the canvas color.
  if (frameType == LayoutFrameType::Viewport &&
      nsLayoutUtils::NeedsPrintPreviewBackground(presContext)) {
    nsRect bounds = nsRect(aBuilder.ToReferenceFrame(aFrame),
                           aFrame->GetSize());
    nsDisplayListBuilder::AutoBuildingDisplayList
      buildingDisplayList(&aBuilder, aFrame, bounds, bounds, false);
    presShell->AddPrintPreviewBackgroundItem(aBuilder, aList, aFrame, bounds);
  } else if (frameType != LayoutFrameType::Page) {
    // For printing, this function is first called on an nsPageFrame, which
    // creates a display list with a PageContent item. The PageContent item's
    // paint function calls this function on the nsPageFrame's child which is
    // an nsPageContentFrame. We only want to add the canvas background color
    // item once, for the nsPageContentFrame.

    // Add the canvas background color to the bottom of the list. This
    // happens after we've built the list so that AddCanvasBackgroundColorItem
    // can monkey with the contents if necessary.
    nsRect canvasArea = aVisibleRegion.GetBounds();
    canvasArea.IntersectRect(aCanvasArea, canvasArea);
    nsDisplayListBuilder::AutoBuildingDisplayList
      buildingDisplayList(&aBuilder, aFrame, canvasArea, canvasArea, false);
    presShell->AddCanvasBackgroundColorItem(
      aBuilder, aList, aFrame, canvasArea, aBackstop);
  }
}

/**
 * Returns a retained display list builder for frame |aFrame|. If there is no
 * retained display list builder property set for the frame, and if the flag
 * |aRetainingEnabled| is true, a new retained display list builder is created,
 * stored as a property for the frame, and returned.
 */
static RetainedDisplayListBuilder*
GetOrCreateRetainedDisplayListBuilder(nsIFrame* aFrame, bool aRetainingEnabled,
                                      bool aBuildCaret)
{
  RetainedDisplayListBuilder* retainedBuilder =
    aFrame->GetProperty(RetainedDisplayListBuilder::Cached());

  if (retainedBuilder) {
    return retainedBuilder;
  }

  if (aRetainingEnabled) {
    retainedBuilder =
      new RetainedDisplayListBuilder(aFrame, nsDisplayListBuilderMode::PAINTING,
                                     aBuildCaret);
    aFrame->SetProperty(RetainedDisplayListBuilder::Cached(), retainedBuilder);
  }

  return retainedBuilder;
}

// #define PRINT_HITTESTINFO_STATS
#ifdef PRINT_HITTESTINFO_STATS
void
PrintHitTestInfoStatsInternal(nsDisplayList& aList,
                              int& aTotal,
                              int& aHitTest,
                              int& aVisible,
                              int& aSpecial)
{
  for (nsDisplayItem* i = aList.GetBottom(); i; i = i->GetAbove()) {
    aTotal++;

    if (i->GetChildren()) {
      PrintHitTestInfoStatsInternal(
        *i->GetChildren(), aTotal, aHitTest, aVisible, aSpecial);
    }

    if (i->GetType() == DisplayItemType::TYPE_COMPOSITOR_HITTEST_INFO) {
      aHitTest++;

      const auto& hitTestInfo =
        static_cast<nsDisplayHitTestInfoItem*>(i)->HitTestFlags();

      if (hitTestInfo.size() > 1) {
        aSpecial++;
        continue;
      }

      if (hitTestInfo == CompositorHitTestVisibleToHit) {
        aVisible++;
        continue;
      }

      aSpecial++;
    }
  }
}

void
PrintHitTestInfoStats(nsDisplayList& aList)
{
  int total = 0;
  int hitTest = 0;
  int visible = 0;
  int special = 0;

  PrintHitTestInfoStatsInternal(
    aList, total, hitTest, visible, special);

  double ratio = (double)hitTest / (double)total;

  printf("List %p: total items: %d, hit test items: %d, ratio: %f, visible: %d, special: %d\n",
    &aList, total, hitTest, ratio, visible, special);
}
#endif

nsresult
nsLayoutUtils::PaintFrame(gfxContext* aRenderingContext, nsIFrame* aFrame,
                          const nsRegion& aDirtyRegion, nscolor aBackstop,
                          nsDisplayListBuilderMode aBuilderMode,
                          PaintFrameFlags aFlags)
{
  AUTO_PROFILER_LABEL("nsLayoutUtils::PaintFrame", GRAPHICS);
  typedef RetainedDisplayListBuilder::PartialUpdateResult PartialUpdateResult;

#ifdef MOZ_DUMP_PAINTING
  if (!gPaintCountStack) {
    gPaintCountStack = new nsTArray<int>();
    ClearOnShutdown(&gPaintCountStack);

    gPaintCountStack->AppendElement(0);
  }
  ++gPaintCountStack->LastElement();
  AutoNestedPaintCount nestedPaintCount;
#endif

  if (aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) {
    nsView* view = aFrame->GetView();
    if (!(view && view->GetWidget() && GetDisplayRootFrame(aFrame) == aFrame)) {
      aFlags &= ~PaintFrameFlags::PAINT_WIDGET_LAYERS;
      NS_ASSERTION(aRenderingContext, "need a rendering context");
    }
  }

  nsPresContext* presContext = aFrame->PresContext();
  nsIPresShell* presShell = presContext->PresShell();
  nsRootPresContext* rootPresContext = presContext->GetRootPresContext();
  if (!rootPresContext) {
    return NS_OK;
  }

  TimeStamp startBuildDisplayList = TimeStamp::Now();

  const bool buildCaret = !(aFlags & PaintFrameFlags::PAINT_HIDE_CARET);
  const bool isForPainting = (aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) &&
    aBuilderMode == nsDisplayListBuilderMode::PAINTING;

  // Only allow retaining for painting when preffed on, and for root frames (since
  // the modified frame tracking is per-root-frame).
  const bool retainingEnabled =
    isForPainting && AreRetainedDisplayListsEnabled() && !aFrame->GetParent();

  RetainedDisplayListBuilder* retainedBuilder =
    GetOrCreateRetainedDisplayListBuilder(aFrame, retainingEnabled, buildCaret);

  // Only use the retained display list builder if the retaining is currently
  // enabled. This check is needed because it is possible that the pref has been
  // disabled after creating the retained display list builder.
  const bool useRetainedBuilder = retainedBuilder && retainingEnabled;

  Maybe<nsDisplayListBuilder> nonRetainedBuilder;
  Maybe<nsDisplayList> nonRetainedList;
  nsDisplayListBuilder* builderPtr = nullptr;
  nsDisplayList* listPtr = nullptr;

  if (useRetainedBuilder) {
    builderPtr = retainedBuilder->Builder();
    listPtr = retainedBuilder->List();
  } else {
    nonRetainedBuilder.emplace(aFrame, aBuilderMode, buildCaret);
    builderPtr = nonRetainedBuilder.ptr();
    nonRetainedList.emplace();
    listPtr = nonRetainedList.ptr();
  }

  // Retained builder exists, but display list retaining is disabled.
  if (!useRetainedBuilder && retainedBuilder) {
    // Clear the modified frames lists and frame properties.
    retainedBuilder->ClearFramesWithProps();

    // Clear the retained display list.
    retainedBuilder->List()->DeleteAll(retainedBuilder->Builder());
  }

  nsDisplayListBuilder& builder = *builderPtr;
  nsDisplayList& list = *listPtr;

  builder.BeginFrame();

  if (aFlags & PaintFrameFlags::PAINT_IN_TRANSFORM) {
    builder.SetInTransform(true);
  }
  if (aFlags & PaintFrameFlags::PAINT_SYNC_DECODE_IMAGES) {
    builder.SetSyncDecodeImages(true);
  }
  if (aFlags & (PaintFrameFlags::PAINT_WIDGET_LAYERS |
                PaintFrameFlags::PAINT_TO_WINDOW)) {
    builder.SetPaintingToWindow(true);
  }
  if (aFlags & PaintFrameFlags::PAINT_IGNORE_SUPPRESSION) {
    builder.IgnorePaintSuppression();
  }

  if (nsIDocShell* doc = presContext->GetDocShell()) {
    bool isActive = false;
    doc->GetIsActive(&isActive);
    builder.SetInActiveDocShell(isActive);
  }

  nsIFrame* rootScrollFrame = presShell->GetRootScrollFrame();
  if (rootScrollFrame && !aFrame->GetParent()) {
    nsIScrollableFrame* rootScrollableFrame = presShell->GetRootScrollFrameAsScrollable();
    MOZ_ASSERT(rootScrollableFrame);
    nsRect displayPortBase = aFrame->GetVisualOverflowRectRelativeToSelf();
    nsRect temp = displayPortBase;
    Unused << rootScrollableFrame->DecideScrollableLayer(&builder, &displayPortBase, &temp,
                /* aSetBase = */ true);
  }

  nsRegion visibleRegion;
  if (aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) {
    // This layer tree will be reused, so we'll need to calculate it
    // for the whole "visible" area of the window
    //
    // |ignoreViewportScrolling| and |usingDisplayPort| are persistent
    // document-rendering state.  We rely on PresShell to flush
    // retained layers as needed when that persistent state changes.
    visibleRegion = aFrame->GetVisualOverflowRectRelativeToSelf();
  } else {
    visibleRegion = aDirtyRegion;
  }

  // If the root has embedded plugins, flag the builder so we know we'll need
  // to update plugin geometry after painting.
  if ((aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) &&
      !(aFlags & PaintFrameFlags::PAINT_DOCUMENT_RELATIVE) &&
      rootPresContext->NeedToComputePluginGeometryUpdates()) {
    builder.SetWillComputePluginGeometry(true);

    // Disable partial updates for this paint as the list we're about to
    // build has plugin-specific differences that won't trigger invalidations.
    builder.SetDisablePartialUpdates(true);
  }

  nsRect canvasArea(nsPoint(0, 0), aFrame->GetSize());
  bool ignoreViewportScrolling =
    aFrame->GetParent() ? false : presShell->IgnoringViewportScrolling();
  if (ignoreViewportScrolling && rootScrollFrame) {
    nsIScrollableFrame* rootScrollableFrame =
      presShell->GetRootScrollFrameAsScrollable();
    if (aFlags & PaintFrameFlags::PAINT_DOCUMENT_RELATIVE) {
      // Make visibleRegion and aRenderingContext relative to the
      // scrolled frame instead of the root frame.
      nsPoint pos = rootScrollableFrame->GetScrollPosition();
      visibleRegion.MoveBy(-pos);
      if (aRenderingContext) {
        gfxPoint devPixelOffset =
          nsLayoutUtils::PointToGfxPoint(pos,
                                         presContext->AppUnitsPerDevPixel());
        aRenderingContext->SetMatrixDouble(
          aRenderingContext->CurrentMatrixDouble().PreTranslate(devPixelOffset));
      }
    }
    builder.SetIgnoreScrollFrame(rootScrollFrame);

    nsCanvasFrame* canvasFrame =
      do_QueryFrame(rootScrollableFrame->GetScrolledFrame());
    if (canvasFrame) {
      // Use UnionRect here to ensure that areas where the scrollbars
      // were are still filled with the background color.
      canvasArea.UnionRect(canvasArea,
        canvasFrame->CanvasArea() + builder.ToReferenceFrame(canvasFrame));
    }
  }

  builder.ClearHaveScrollableDisplayPort();
  if (builder.IsPaintingToWindow()) {
    MaybeCreateDisplayPortInFirstScrollFrameEncountered(aFrame, builder);
  }

  nsRect visibleRect = visibleRegion.GetBounds();
  PartialUpdateResult updateState = PartialUpdateResult::Failed;

  {
    AUTO_PROFILER_LABEL("nsLayoutUtils::PaintFrame:BuildDisplayList",
                        GRAPHICS);
    AUTO_PROFILER_TRACING("Paint", "DisplayList");

    PaintTelemetry::AutoRecord record(PaintTelemetry::Metric::DisplayList);
    TimeStamp dlStart = TimeStamp::Now();

    {
      // If a scrollable container layer is created in nsDisplayList::PaintForFrame,
      // it will be the scroll parent for display items that are built in the
      // BuildDisplayListForStackingContext call below. We need to set the scroll
      // parent on the display list builder while we build those items, so that they
      // can pick up their scroll parent's id.
      ViewID id = ScrollableLayerGuid::NULL_SCROLL_ID;
      if (ignoreViewportScrolling && presContext->IsRootContentDocument()) {
        if (nsIFrame* rootScrollFrame = presShell->GetRootScrollFrame()) {
          if (nsIContent* content = rootScrollFrame->GetContent()) {
            id = nsLayoutUtils::FindOrCreateIDFor(content);
          }
        }
      }
      else if (presShell->GetDocument() && presShell->GetDocument()->IsRootDisplayDocument()
          && !presShell->GetRootScrollFrame()) {
        // In cases where the root document is a XUL document, we want to take
        // the ViewID from the root element, as that will be the ViewID of the
        // root APZC in the tree. Skip doing this in cases where we know
        // nsGfxScrollFrame::BuilDisplayList will do it instead.
        if (dom::Element* element = presShell->GetDocument()->GetDocumentElement()) {
          id = nsLayoutUtils::FindOrCreateIDFor(element);
        }
      // In some cases we get a root document here on an APZ-enabled window
      // that doesn't have the root displayport initialized yet, even though
      // the ChromeProcessController is supposed to do it when the widget is
      // created. This can happen simply because the ChromeProcessController
      // does it on the next spin of the event loop, and we can trigger a paint
      // synchronously after window creation but before that runs. In that case
      // we should initialize the root displayport here before we do the paint.
      } else if (XRE_IsParentProcess() && presContext->IsRoot()
          && presShell->GetDocument() != nullptr
          && presShell->GetRootScrollFrame() != nullptr
          && nsLayoutUtils::UsesAsyncScrolling(presShell->GetRootScrollFrame())) {
        if (dom::Element* element = presShell->GetDocument()->GetDocumentElement()) {
          if (!nsLayoutUtils::HasDisplayPort(element)) {
            APZCCallbackHelper::InitializeRootDisplayport(presShell);
          }
        }
      }

      nsDisplayListBuilder::AutoCurrentScrollParentIdSetter idSetter(&builder, id);

      builder.SetVisibleRect(visibleRect);
      builder.SetIsBuilding(true);
      builder.SetAncestorHasApzAwareEventHandler(
          gfxPlatform::AsyncPanZoomEnabled() &&
          nsLayoutUtils::HasDocumentLevelListenersForApzAwareEvents(presShell));

      DisplayListChecker beforeMergeChecker;
      DisplayListChecker toBeMergedChecker;
      DisplayListChecker afterMergeChecker;

      // Attempt to do a partial build and merge into the existing list.
      // This calls BuildDisplayListForStacking context on a subset of the
      // viewport.
      if (useRetainedBuilder) {
        if (gfxPrefs::LayoutVerifyRetainDisplayList()) {
          beforeMergeChecker.Set(&list, "BM");
        }
        updateState = retainedBuilder->AttemptPartialUpdate(
          aBackstop, beforeMergeChecker ? &toBeMergedChecker : nullptr);
        if ((updateState != PartialUpdateResult::Failed) && beforeMergeChecker) {
          afterMergeChecker.Set(&list, "AM");
        }
      }

      if ((updateState != PartialUpdateResult::Failed) &&
          (gfxPrefs::LayoutDisplayListBuildTwice() || afterMergeChecker)) {
        updateState = PartialUpdateResult::Failed;
        if (gfxPrefs::LayersDrawFPS()) {
          if (RefPtr<LayerManager> lm = builder.GetWidgetLayerManager()) {
            if (PaintTiming* pt = ClientLayerManager::MaybeGetPaintTiming(lm)) {
              pt->dl2Ms() = (TimeStamp::Now() - dlStart).ToMilliseconds();
            }
          }
        }
        dlStart = TimeStamp::Now();
      }

      if (updateState == PartialUpdateResult::Failed) {
        list.DeleteAll(&builder);

        builder.ClearRetainedWindowRegions();
        builder.ClearWillChangeBudget();

        builder.EnterPresShell(aFrame);
        builder.SetDirtyRect(visibleRect);
        aFrame->BuildDisplayListForStackingContext(&builder, &list);
        AddExtraBackgroundItems(
          builder, list, aFrame, canvasArea, visibleRegion, aBackstop);

        builder.LeavePresShell(aFrame, &list);
        updateState = PartialUpdateResult::Updated;

        if (afterMergeChecker) {
          DisplayListChecker nonRetainedChecker(&list, "NR");
          std::stringstream ss;
          ss << "**** Differences between retained-after-merged (AM) and "
             << "non-retained (NR) display lists:";
          if (!nonRetainedChecker.CompareList(afterMergeChecker, ss)) {
            ss << "\n\n*** non-retained display items:";
            nonRetainedChecker.Dump(ss);
            ss << "\n\n*** before-merge retained display items:";
            beforeMergeChecker.Dump(ss);
            ss << "\n\n*** to-be-merged retained display items:";
            toBeMergedChecker.Dump(ss);
            ss << "\n\n*** after-merge retained display items:";
            afterMergeChecker.Dump(ss);
            fprintf(stderr, "%s\n\n", ss.str().c_str());
#ifdef DEBUG_FRAME_DUMP
            fprintf(stderr, "*** Frame tree:\n");
            aFrame->DumpFrameTree();
#endif
          }
        }
      }
    }

    builder.SetIsBuilding(false);
    builder.IncrementPresShellPaintCount(presShell);

    if (gfxPrefs::LayersDrawFPS()) {
      if (RefPtr<LayerManager> lm = builder.GetWidgetLayerManager()) {
        if (PaintTiming* pt = ClientLayerManager::MaybeGetPaintTiming(lm)) {
          pt->dlMs() = (TimeStamp::Now() - dlStart).ToMilliseconds();
        }
      }
    }
  }

  MOZ_ASSERT(updateState != PartialUpdateResult::Failed);
  builder.Check();

  Telemetry::AccumulateTimeDelta(Telemetry::PAINT_BUILD_DISPLAYLIST_TIME,
                                 startBuildDisplayList);

  bool consoleNeedsDisplayList =
      (gfxUtils::DumpDisplayList() || gfxEnv::DumpPaint()) &&
      builder.IsInActiveDocShell();
#ifdef MOZ_DUMP_PAINTING
  FILE* savedDumpFile = gfxUtils::sDumpPaintFile;
#endif

  UniquePtr<std::stringstream> ss;
  if (consoleNeedsDisplayList) {
    ss = MakeUnique<std::stringstream>();
#ifdef MOZ_DUMP_PAINTING
    if (gfxEnv::DumpPaintToFile()) {
      nsCString string("dump-");
      // Include the process ID in the dump file name, to make sure that in an
      // e10s setup different processes don't clobber each other's dump files.
      string.AppendInt(getpid());
      for (int paintCount : *gPaintCountStack) {
        string.AppendLiteral("-");
        string.AppendInt(paintCount);
      }
      string.AppendLiteral(".html");
      gfxUtils::sDumpPaintFile = fopen(string.BeginReading(), "w");
    } else {
      gfxUtils::sDumpPaintFile = stderr;
    }
    if (gfxEnv::DumpPaintToFile()) {
      *ss << "<html><head><script>\n"
             "var array = {};\n"
             "function ViewImage(index) { \n"
             "  var image = document.getElementById(index);\n"
             "  if (image.src) {\n"
             "    image.removeAttribute('src');\n"
             "  } else {\n"
             "    image.src = array[index];\n"
             "  }\n"
             "}</script></head><body>";
    }
#endif
    *ss << nsPrintfCString("Painting --- before optimization (dirty %d,%d,%d,%d):\n",
            visibleRect.x, visibleRect.y, visibleRect.width, visibleRect.height).get();
    nsFrame::PrintDisplayList(&builder, list, *ss, gfxEnv::DumpPaintToFile());

    if (gfxEnv::DumpPaint() || gfxEnv::DumpPaintItems()) {
      // Flush stream now to avoid reordering dump output relative to
      // messages dumped by PaintRoot below.
      fprint_stderr(gfxUtils::sDumpPaintFile, *ss);
      ss = MakeUnique<std::stringstream>();
    }
  }

  uint32_t flags = nsDisplayList::PAINT_DEFAULT;
  if (aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) {
    flags |= nsDisplayList::PAINT_USE_WIDGET_LAYERS;
    if (!(aFlags & PaintFrameFlags::PAINT_DOCUMENT_RELATIVE)) {
      nsIWidget *widget = aFrame->GetNearestWidget();
      if (widget) {
        // If we're finished building display list items for painting of the outermost
        // pres shell, notify the widget about any toolbars we've encountered.
        widget->UpdateThemeGeometries(builder.GetThemeGeometries());
      }
    }
  }
  if (aFlags & PaintFrameFlags::PAINT_EXISTING_TRANSACTION) {
    flags |= nsDisplayList::PAINT_EXISTING_TRANSACTION;
  }
  if (aFlags & PaintFrameFlags::PAINT_NO_COMPOSITE) {
    flags |= nsDisplayList::PAINT_NO_COMPOSITE;
  }
  if (aFlags & PaintFrameFlags::PAINT_COMPRESSED) {
    flags |= nsDisplayList::PAINT_COMPRESSED;
  }
  if (updateState == PartialUpdateResult::NoChange &&
      !aRenderingContext) {
    flags |= nsDisplayList::PAINT_IDENTICAL_DISPLAY_LIST;
  }

#ifdef PRINT_HITTESTINFO_STATS
  if (XRE_IsContentProcess()) {
    PrintHitTestInfoStats(list);
  }
#endif

  TimeStamp paintStart = TimeStamp::Now();
  RefPtr<LayerManager> layerManager
    = list.PaintRoot(&builder, aRenderingContext, flags);
  Telemetry::AccumulateTimeDelta(Telemetry::PAINT_RASTERIZE_TIME,
                                 paintStart);

  builder.Check();

  if (gfxPrefs::GfxLoggingPaintedPixelCountEnabled()) {
    TimeStamp now = TimeStamp::Now();
    float rasterizeTime = (now - paintStart).ToMilliseconds();
    uint32_t pixelCount = layerManager->GetAndClearPaintedPixelCount();
    static std::vector<std::pair<TimeStamp, uint32_t>> history;
    if (pixelCount) {
      history.push_back(std::make_pair(now, pixelCount));
    }
    uint32_t paintedInLastSecond = 0;
    for (auto i = history.begin(); i != history.end(); i++) {
      if ((now - i->first).ToMilliseconds() > 1000.0f) {
        // more than 1000ms ago, don't count it
        continue;
      }
      if (paintedInLastSecond == 0) {
        // This is the first one in the last 1000ms, so drop everything earlier
        history.erase(history.begin(), i);
        i = history.begin();
      }
      paintedInLastSecond += i->second;
      MOZ_ASSERT(paintedInLastSecond); // all historical pixel counts are > 0
    }
    printf_stderr("Painted %u pixels in %fms (%u in the last 1000ms)\n",
        pixelCount, rasterizeTime, paintedInLastSecond);
  }

  if (consoleNeedsDisplayList) {
    *ss << "Painting --- after optimization:\n";
    nsFrame::PrintDisplayList(&builder, list, *ss, gfxEnv::DumpPaintToFile());

    *ss << "Painting --- layer tree:\n";
    if (layerManager) {
      FrameLayerBuilder::DumpRetainedLayerTree(layerManager, *ss,
                                               gfxEnv::DumpPaintToFile());
    }

    fprint_stderr(gfxUtils::sDumpPaintFile, *ss);

#ifdef MOZ_DUMP_PAINTING
    if (gfxEnv::DumpPaintToFile()) {
      *ss << "</body></html>";
    }
    if (gfxEnv::DumpPaintToFile()) {
      fclose(gfxUtils::sDumpPaintFile);
    }
    gfxUtils::sDumpPaintFile = savedDumpFile;
#endif

    std::stringstream lsStream;
    nsFrame::PrintDisplayList(&builder, list, lsStream);
    if (layerManager->GetRoot()) {
      layerManager->GetRoot()->SetDisplayListLog(lsStream.str().c_str());
    }
  }

#ifdef MOZ_DUMP_PAINTING
  if (gfxPrefs::DumpClientLayers()) {
    std::stringstream ss;
    FrameLayerBuilder::DumpRetainedLayerTree(layerManager, ss, false);
    print_stderr(ss);
  }
#endif

  // Update the widget's opaque region information. This sets
  // glass boundaries on Windows. Also set up the window dragging region
  // and plugin clip regions and bounds.
  if ((aFlags & PaintFrameFlags::PAINT_WIDGET_LAYERS) &&
      !(aFlags & PaintFrameFlags::PAINT_DOCUMENT_RELATIVE)) {
    nsIWidget *widget = aFrame->GetNearestWidget();
    if (widget) {
      nsRegion opaqueRegion;
      opaqueRegion.And(builder.GetWindowExcludeGlassRegion(), builder.GetWindowOpaqueRegion());
      widget->UpdateOpaqueRegion(
        LayoutDeviceIntRegion::FromUnknownRegion(
          opaqueRegion.ToNearestPixels(presContext->AppUnitsPerDevPixel())));

      widget->UpdateWindowDraggingRegion(builder.GetWindowDraggingRegion());
    }
  }

  if (builder.WillComputePluginGeometry()) {
    // For single process compute and apply plugin geometry updates to plugin
    // windows, then request composition. For content processes skip eveything
    // except requesting composition. Geometry updates were calculated and
    // shipped to the chrome process in nsDisplayList when the layer
    // transaction completed.
    if (XRE_IsParentProcess()) {
      rootPresContext->ComputePluginGeometryUpdates(aFrame, &builder, &list);
      // We're not going to get a WillPaintWindow event here if we didn't do
      // widget invalidation, so just apply the plugin geometry update here
      // instead. We could instead have the compositor send back an equivalent
      // to WillPaintWindow, but it should be close enough to now not to matter.
      if (layerManager && !layerManager->NeedsWidgetInvalidation()) {
        rootPresContext->ApplyPluginGeometryUpdates();
      }
    }

    // We told the compositor thread not to composite when it received the
    // transaction because we wanted to update plugins first. Schedule the
    // composite now.
    if (layerManager) {
      layerManager->ScheduleComposite();
    }

    // Disable partial updates for the following paint as well, as we now have
    // a plugin-specific display list.
    builder.SetDisablePartialUpdates(true);
  }

  builder.Check();

  {
    AUTO_PROFILER_TRACING("Paint", "DisplayListResources");

    // Flush the list so we don't trigger the IsEmpty-on-destruction assertion
    if (!useRetainedBuilder) {
      list.DeleteAll(&builder);
    }

    builder.EndFrame();
  }
  return NS_OK;
}

/**
 * Uses a binary search for find where the cursor falls in the line of text
 * It also keeps track of the part of the string that has already been measured
 * so it doesn't have to keep measuring the same text over and over
 *
 * @param "aBaseWidth" contains the width in twips of the portion
 * of the text that has already been measured, and aBaseInx contains
 * the index of the text that has already been measured.
 *
 * @param aTextWidth returns the (in twips) the length of the text that falls
 * before the cursor aIndex contains the index of the text where the cursor falls
 */
bool
nsLayoutUtils::BinarySearchForPosition(DrawTarget* aDrawTarget,
                                       nsFontMetrics& aFontMetrics,
                        const char16_t* aText,
                        int32_t    aBaseWidth,
                        int32_t    aBaseInx,
                        int32_t    aStartInx,
                        int32_t    aEndInx,
                        int32_t    aCursorPos,
                        int32_t&   aIndex,
                        int32_t&   aTextWidth)
{
  int32_t range = aEndInx - aStartInx;
  if ((range == 1) || (range == 2 && NS_IS_HIGH_SURROGATE(aText[aStartInx]))) {
    aIndex   = aStartInx + aBaseInx;
    aTextWidth = nsLayoutUtils::AppUnitWidthOfString(aText, aIndex,
                                                     aFontMetrics, aDrawTarget);
    return true;
  }

  int32_t inx = aStartInx + (range / 2);

  // Make sure we don't leave a dangling low surrogate
  if (NS_IS_HIGH_SURROGATE(aText[inx-1]))
    inx++;

  int32_t textWidth = nsLayoutUtils::AppUnitWidthOfString(aText, inx,
                                                          aFontMetrics,
                                                          aDrawTarget);

  int32_t fullWidth = aBaseWidth + textWidth;
  if (fullWidth == aCursorPos) {
    aTextWidth = textWidth;
    aIndex = inx;
    return true;
  } else if (aCursorPos < fullWidth) {
    aTextWidth = aBaseWidth;
    if (BinarySearchForPosition(aDrawTarget, aFontMetrics, aText, aBaseWidth,
                                aBaseInx, aStartInx, inx, aCursorPos, aIndex,
                                aTextWidth)) {
      return true;
    }
  } else {
    aTextWidth = fullWidth;
    if (BinarySearchForPosition(aDrawTarget, aFontMetrics, aText, aBaseWidth,
                                aBaseInx, inx, aEndInx, aCursorPos, aIndex,
                                aTextWidth)) {
      return true;
    }
  }
  return false;
}

void
nsLayoutUtils::AddBoxesForFrame(nsIFrame* aFrame,
                                nsLayoutUtils::BoxCallback* aCallback)
{
  nsAtom* pseudoType = aFrame->Style()->GetPseudo();

  if (pseudoType == nsCSSAnonBoxes::tableWrapper()) {
    AddBoxesForFrame(aFrame->PrincipalChildList().FirstChild(), aCallback);
    if (aCallback->mIncludeCaptionBoxForTable) {
      nsIFrame* kid = aFrame->GetChildList(nsIFrame::kCaptionList).FirstChild();
      if (kid) {
        AddBoxesForFrame(kid, aCallback);
      }
    }
  } else if (pseudoType == nsCSSAnonBoxes::mozBlockInsideInlineWrapper() ||
             pseudoType == nsCSSAnonBoxes::mozMathMLAnonymousBlock() ||
             pseudoType == nsCSSAnonBoxes::mozXULAnonymousBlock()) {
    for (nsIFrame* kid : aFrame->PrincipalChildList()) {
      AddBoxesForFrame(kid, aCallback);
    }
  } else {
    aCallback->AddBox(aFrame);
  }
}

void
nsLayoutUtils::GetAllInFlowBoxes(nsIFrame* aFrame, BoxCallback* aCallback)
{
  while (aFrame) {
    AddBoxesForFrame(aFrame, aCallback);
    aFrame = nsLayoutUtils::GetNextContinuationOrIBSplitSibling(aFrame);
  }
}

nsIFrame*
nsLayoutUtils::GetFirstNonAnonymousFrame(nsIFrame* aFrame)
{
  while (aFrame) {
    nsAtom* pseudoType = aFrame->Style()->GetPseudo();

    if (pseudoType == nsCSSAnonBoxes::tableWrapper()) {
      nsIFrame* f = GetFirstNonAnonymousFrame(aFrame->PrincipalChildList().FirstChild());
      if (f) {
        return f;
      }
      nsIFrame* kid = aFrame->GetChildList(nsIFrame::kCaptionList).FirstChild();
      if (kid) {
        f = GetFirstNonAnonymousFrame(kid);
        if (f) {
          return f;
        }
      }
    } else if (pseudoType == nsCSSAnonBoxes::mozBlockInsideInlineWrapper() ||
               pseudoType == nsCSSAnonBoxes::mozMathMLAnonymousBlock() ||
               pseudoType == nsCSSAnonBoxes::mozXULAnonymousBlock()) {
      for (nsIFrame* kid : aFrame->PrincipalChildList()) {
        nsIFrame* f = GetFirstNonAnonymousFrame(kid);
        if (f) {
          return f;
        }
      }
    } else {
      return aFrame;
    }

    aFrame = nsLayoutUtils::GetNextContinuationOrIBSplitSibling(aFrame);
  }
  return nullptr;
}

struct BoxToRect : public nsLayoutUtils::BoxCallback {
  const nsIFrame* mRelativeTo;
  nsLayoutUtils::RectCallback* mCallback;
  uint32_t mFlags;

  BoxToRect(const nsIFrame* aRelativeTo, nsLayoutUtils::RectCallback* aCallback,
            uint32_t aFlags)
    : mRelativeTo(aRelativeTo), mCallback(aCallback), mFlags(aFlags) {}

  virtual void AddBox(nsIFrame* aFrame) override {
    nsRect r;
    nsIFrame* outer = nsSVGUtils::GetOuterSVGFrameAndCoveredRegion(aFrame, &r);
    if (!outer) {
      outer = aFrame;
      switch (mFlags & nsLayoutUtils::RECTS_WHICH_BOX_MASK) {
        case nsLayoutUtils::RECTS_USE_CONTENT_BOX:
          r = aFrame->GetContentRectRelativeToSelf();
          break;
        case nsLayoutUtils::RECTS_USE_PADDING_BOX:
          r = aFrame->GetPaddingRectRelativeToSelf();
          break;
        case nsLayoutUtils::RECTS_USE_MARGIN_BOX:
          r = aFrame->GetMarginRectRelativeToSelf();
          break;
        default: // Use the border box
          r = aFrame->GetRectRelativeToSelf();
      }
    }
    if (mFlags & nsLayoutUtils::RECTS_ACCOUNT_FOR_TRANSFORMS) {
      r = nsLayoutUtils::TransformFrameRectToAncestor(outer, r, mRelativeTo);
    } else {
      r += outer->GetOffsetTo(mRelativeTo);
    }
    mCallback->AddRect(r);
  }
};

struct MOZ_RAII BoxToRectAndText : public BoxToRect {
  Sequence<nsString>* mTextList;

  BoxToRectAndText(const nsIFrame* aRelativeTo, nsLayoutUtils::RectCallback* aCallback,
                   Sequence<nsString>* aTextList, uint32_t aFlags)
    : BoxToRect(aRelativeTo, aCallback, aFlags), mTextList(aTextList) {}

  static void AccumulateText(nsIFrame* aFrame, nsAString& aResult) {
    MOZ_ASSERT(aFrame);

    // Get all the text in aFrame and child frames, while respecting
    // the content offsets in each of the nsTextFrames.
    if (aFrame->IsTextFrame()) {
      nsTextFrame* textFrame = static_cast<nsTextFrame*>(aFrame);

      nsIFrame::RenderedText renderedText = textFrame->GetRenderedText(
        textFrame->GetContentOffset(),
        textFrame->GetContentOffset() + textFrame->GetContentLength(),
        nsIFrame::TextOffsetType::OFFSETS_IN_CONTENT_TEXT,
        nsIFrame::TrailingWhitespace::DONT_TRIM_TRAILING_WHITESPACE);

      aResult.Append(renderedText.mString);
    }

    for (nsIFrame* child = aFrame->PrincipalChildList().FirstChild();
         child;
         child = child->GetNextSibling()) {
      AccumulateText(child, aResult);
    }
  }

  virtual void AddBox(nsIFrame* aFrame) override {
    BoxToRect::AddBox(aFrame);
    if (mTextList) {
      nsString* textForFrame = mTextList->AppendElement(fallible);
      if (textForFrame) {
        AccumulateText(aFrame, *textForFrame);
      }
    }
  }
};

void
nsLayoutUtils::GetAllInFlowRects(nsIFrame* aFrame, const nsIFrame* aRelativeTo,
                                 RectCallback* aCallback, uint32_t aFlags)
{
  BoxToRect converter(aRelativeTo, aCallback, aFlags);
  GetAllInFlowBoxes(aFrame, &converter);
}

void
nsLayoutUtils::GetAllInFlowRectsAndTexts(nsIFrame* aFrame,
                                         const nsIFrame* aRelativeTo,
                                         RectCallback* aCallback,
                                         Sequence<nsString>* aTextList,
                                         uint32_t aFlags)
{
  BoxToRectAndText converter(aRelativeTo, aCallback, aTextList, aFlags);
  GetAllInFlowBoxes(aFrame, &converter);
}

nsLayoutUtils::RectAccumulator::RectAccumulator() : mSeenFirstRect(false) {}

void nsLayoutUtils::RectAccumulator::AddRect(const nsRect& aRect) {
  mResultRect.UnionRect(mResultRect, aRect);
  if (!mSeenFirstRect) {
    mSeenFirstRect = true;
    mFirstRect = aRect;
  }
}

nsLayoutUtils::RectListBuilder::RectListBuilder(DOMRectList* aList)
  : mRectList(aList)
{
}

void nsLayoutUtils::RectListBuilder::AddRect(const nsRect& aRect) {
  RefPtr<DOMRect> rect = new DOMRect(mRectList);

  rect->SetLayoutRect(aRect);
  mRectList->Append(rect);
}

nsIFrame* nsLayoutUtils::GetContainingBlockForClientRect(nsIFrame* aFrame)
{
  return aFrame->PresShell()->GetRootFrame();
}

nsRect
nsLayoutUtils::GetAllInFlowRectsUnion(nsIFrame* aFrame, const nsIFrame* aRelativeTo,
                                      uint32_t aFlags) {
  RectAccumulator accumulator;
  GetAllInFlowRects(aFrame, aRelativeTo, &accumulator, aFlags);
  return accumulator.mResultRect.IsEmpty() ? accumulator.mFirstRect
          : accumulator.mResultRect;
}

nsRect
nsLayoutUtils::GetTextShadowRectsUnion(const nsRect& aTextAndDecorationsRect,
                                       nsIFrame* aFrame,
                                       uint32_t aFlags)
{
  const nsStyleText* textStyle = aFrame->StyleText();
  if (!textStyle->HasTextShadow())
    return aTextAndDecorationsRect;

  nsRect resultRect = aTextAndDecorationsRect;
  int32_t A2D = aFrame->PresContext()->AppUnitsPerDevPixel();
  for (uint32_t i = 0; i < textStyle->mTextShadow->Length(); ++i) {
    nsCSSShadowItem* shadow = textStyle->mTextShadow->ShadowAt(i);
    nsMargin blur = nsContextBoxBlur::GetBlurRadiusMargin(shadow->mRadius, A2D);
    if ((aFlags & EXCLUDE_BLUR_SHADOWS) && blur != nsMargin(0, 0, 0, 0))
      continue;

    nsRect tmpRect(aTextAndDecorationsRect);

    tmpRect.MoveBy(nsPoint(shadow->mXOffset, shadow->mYOffset));
    tmpRect.Inflate(blur);

    resultRect.UnionRect(resultRect, tmpRect);
  }
  return resultRect;
}

enum ObjectDimensionType { eWidth, eHeight };
static nscoord
ComputeMissingDimension(const nsSize& aDefaultObjectSize,
                        const nsSize& aIntrinsicRatio,
                        const Maybe<nscoord>& aSpecifiedWidth,
                        const Maybe<nscoord>& aSpecifiedHeight,
                        ObjectDimensionType aDimensionToCompute)
{
  // The "default sizing algorithm" computes the missing dimension as follows:
  // (source: http://dev.w3.org/csswg/css-images-3/#default-sizing )

  // 1. "If the object has an intrinsic aspect ratio, the missing dimension of
  //     the concrete object size is calculated using the intrinsic aspect
  //     ratio and the present dimension."
  if (aIntrinsicRatio.width > 0 && aIntrinsicRatio.height > 0) {
    // Fill in the missing dimension using the intrinsic aspect ratio.
    nscoord knownDimensionSize;
    float ratio;
    if (aDimensionToCompute == eWidth) {
      knownDimensionSize = *aSpecifiedHeight;
      ratio = aIntrinsicRatio.width / aIntrinsicRatio.height;
    } else {
      knownDimensionSize = *aSpecifiedWidth;
      ratio = aIntrinsicRatio.height / aIntrinsicRatio.width;
    }
    return NSCoordSaturatingNonnegativeMultiply(knownDimensionSize, ratio);
  }

  // 2. "Otherwise, if the missing dimension is present in the object’s
  //     intrinsic dimensions, [...]"
  // NOTE: *Skipping* this case, because we already know it's not true -- we're
  // in this function because the missing dimension is *not* present in
  // the object's intrinsic dimensions.

  // 3. "Otherwise, the missing dimension of the concrete object size is taken
  //     from the default object size. "
  return (aDimensionToCompute == eWidth) ?
    aDefaultObjectSize.width : aDefaultObjectSize.height;
}

/*
 * This computes & returns the concrete object size of replaced content, if
 * that content were to be rendered with "object-fit: none".  (Or, if the
 * element has neither an intrinsic height nor width, this method returns an
 * empty Maybe<> object.)
 *
 * As specced...
 *   http://dev.w3.org/csswg/css-images-3/#valdef-object-fit-none
 * ..we use "the default sizing algorithm with no specified size,
 * and a default object size equal to the replaced element's used width and
 * height."
 *
 * The default sizing algorithm is described here:
 *   http://dev.w3.org/csswg/css-images-3/#default-sizing
 * Quotes in the function-impl are taken from that ^ spec-text.
 *
 * Per its final bulleted section: since there's no specified size,
 * we run the default sizing algorithm using the object's intrinsic size in
 * place of the specified size. But if the object has neither an intrinsic
 * height nor an intrinsic width, then we instead return without populating our
 * outparam, and we let the caller figure out the size (using a contain
 * constraint).
 */
static Maybe<nsSize>
MaybeComputeObjectFitNoneSize(const nsSize& aDefaultObjectSize,
                              const IntrinsicSize& aIntrinsicSize,
                              const nsSize& aIntrinsicRatio)
{
  // "If the object has an intrinsic height or width, its size is resolved as
  // if its intrinsic dimensions were given as the specified size."
  //
  // So, first we check if we have an intrinsic height and/or width:
  Maybe<nscoord> specifiedWidth;
  if (aIntrinsicSize.width.GetUnit() == eStyleUnit_Coord) {
    specifiedWidth.emplace(aIntrinsicSize.width.GetCoordValue());
  }

  Maybe<nscoord> specifiedHeight;
  if (aIntrinsicSize.height.GetUnit() == eStyleUnit_Coord) {
    specifiedHeight.emplace(aIntrinsicSize.height.GetCoordValue());
  }

  Maybe<nsSize> noneSize; // (the value we'll return)
  if (specifiedWidth || specifiedHeight) {
    // We have at least one specified dimension; use whichever dimension is
    // specified, and compute the other one using our intrinsic ratio, or (if
    // no valid ratio) using the default object size.
    noneSize.emplace();

    noneSize->width = specifiedWidth ?
      *specifiedWidth :
      ComputeMissingDimension(aDefaultObjectSize, aIntrinsicRatio,
                              specifiedWidth, specifiedHeight,
                              eWidth);

    noneSize->height = specifiedHeight ?
      *specifiedHeight :
      ComputeMissingDimension(aDefaultObjectSize, aIntrinsicRatio,
                              specifiedWidth, specifiedHeight,
                              eHeight);
  }
  // [else:] "Otherwise [if there's neither an intrinsic height nor width], its
  // size is resolved as a contain constraint against the default object size."
  // We'll let our caller do that, to share code & avoid redundant
  // computations; so, we return w/out populating noneSize.
  return noneSize;
}

// Computes the concrete object size to render into, as described at
// http://dev.w3.org/csswg/css-images-3/#concrete-size-resolution
static nsSize
ComputeConcreteObjectSize(const nsSize& aConstraintSize,
                          const IntrinsicSize& aIntrinsicSize,
                          const nsSize& aIntrinsicRatio,
                          uint8_t aObjectFit)
{
  // Handle default behavior (filling the container) w/ fast early return.
  // (Also: if there's no valid intrinsic ratio, then we have the "fill"
  // behavior & just use the constraint size.)
  if (MOZ_LIKELY(aObjectFit == NS_STYLE_OBJECT_FIT_FILL) ||
      aIntrinsicRatio.width == 0 ||
      aIntrinsicRatio.height == 0) {
    return aConstraintSize;
  }

  // The type of constraint to compute (cover/contain), if needed:
  Maybe<nsImageRenderer::FitType> fitType;

  Maybe<nsSize> noneSize;
  if (aObjectFit == NS_STYLE_OBJECT_FIT_NONE ||
      aObjectFit == NS_STYLE_OBJECT_FIT_SCALE_DOWN) {
    noneSize = MaybeComputeObjectFitNoneSize(aConstraintSize, aIntrinsicSize,
                                             aIntrinsicRatio);
    if (!noneSize || aObjectFit == NS_STYLE_OBJECT_FIT_SCALE_DOWN) {
      // Need to compute a 'CONTAIN' constraint (either for the 'none' size
      // itself, or for comparison w/ the 'none' size to resolve 'scale-down'.)
      fitType.emplace(nsImageRenderer::CONTAIN);
    }
  } else if (aObjectFit == NS_STYLE_OBJECT_FIT_COVER) {
    fitType.emplace(nsImageRenderer::COVER);
  } else if (aObjectFit == NS_STYLE_OBJECT_FIT_CONTAIN) {
    fitType.emplace(nsImageRenderer::CONTAIN);
  }

  Maybe<nsSize> constrainedSize;
  if (fitType) {
    constrainedSize.emplace(
      nsImageRenderer::ComputeConstrainedSize(aConstraintSize,
                                              aIntrinsicRatio,
                                              *fitType));
  }

  // Now, we should have all the sizing information that we need.
  switch (aObjectFit) {
    // skipping NS_STYLE_OBJECT_FIT_FILL; we handled it w/ early-return.
    case NS_STYLE_OBJECT_FIT_CONTAIN:
    case NS_STYLE_OBJECT_FIT_COVER:
      MOZ_ASSERT(constrainedSize);
      return *constrainedSize;

    case NS_STYLE_OBJECT_FIT_NONE:
      if (noneSize) {
        return *noneSize;
      }
      MOZ_ASSERT(constrainedSize);
      return *constrainedSize;

    case NS_STYLE_OBJECT_FIT_SCALE_DOWN:
      MOZ_ASSERT(constrainedSize);
      if (noneSize) {
        constrainedSize->width =
          std::min(constrainedSize->width, noneSize->width);
        constrainedSize->height =
          std::min(constrainedSize->height, noneSize->height);
      }
      return *constrainedSize;

    default:
      MOZ_ASSERT_UNREACHABLE("Unexpected enum value for 'object-fit'");
      return aConstraintSize; // fall back to (default) 'fill' behavior
  }
}

// (Helper for HasInitialObjectFitAndPosition, to check
// each "object-position" coord.)
static bool
IsCoord50Pct(const mozilla::Position::Coord& aCoord)
{
  return (aCoord.mLength == 0 &&
          aCoord.mHasPercent &&
          aCoord.mPercent == 0.5f);
}

// Indicates whether the given nsStylePosition has the initial values
// for the "object-fit" and "object-position" properties.
static bool
HasInitialObjectFitAndPosition(const nsStylePosition* aStylePos)
{
  const mozilla::Position& objectPos = aStylePos->mObjectPosition;

  return aStylePos->mObjectFit == NS_STYLE_OBJECT_FIT_FILL &&
    IsCoord50Pct(objectPos.mXPosition) &&
    IsCoord50Pct(objectPos.mYPosition);
}

/* static */ nsRect
nsLayoutUtils::ComputeObjectDestRect(const nsRect& aConstraintRect,
                                     const IntrinsicSize& aIntrinsicSize,
                                     const nsSize& aIntrinsicRatio,
                                     const nsStylePosition* aStylePos,
                                     nsPoint* aAnchorPoint)
{
  // Step 1: Figure out our "concrete object size"
  // (the size of the region we'll actually draw our image's pixels into).
  nsSize concreteObjectSize =
    ComputeConcreteObjectSize(aConstraintRect.Size(), aIntrinsicSize,
                              aIntrinsicRatio, aStylePos->mObjectFit);

  // Step 2: Figure out how to align that region in the element's content-box.
  nsPoint imageTopLeftPt, imageAnchorPt;
  nsImageRenderer::ComputeObjectAnchorPoint(aStylePos->mObjectPosition,
                                            aConstraintRect.Size(),
                                            concreteObjectSize,
                                            &imageTopLeftPt, &imageAnchorPt);
  // Right now, we're with respect to aConstraintRect's top-left point.  We add
  // that point here, to convert to the same broader coordinate space that
  // aConstraintRect is in.
  imageTopLeftPt += aConstraintRect.TopLeft();
  imageAnchorPt += aConstraintRect.TopLeft();

  if (aAnchorPoint) {
    // Special-case: if our "object-fit" and "object-position" properties have
    // their default values ("object-fit: fill; object-position:50% 50%"), then
    // we'll override the calculated imageAnchorPt, and instead use the
    // object's top-left corner.
    //
    // This special case is partly for backwards compatibility (since
    // traditionally we've pixel-aligned the top-left corner of e.g. <img>
    // elements), and partly because ComputeSnappedDrawingParameters produces
    // less error if the anchor point is at the top-left corner. So, all other
    // things being equal, we prefer that code path with less error.
    if (HasInitialObjectFitAndPosition(aStylePos)) {
      *aAnchorPoint = imageTopLeftPt;
    } else {
      *aAnchorPoint = imageAnchorPt;
    }
  }
  return nsRect(imageTopLeftPt, concreteObjectSize);
}

already_AddRefed<nsFontMetrics>
nsLayoutUtils::GetFontMetricsForFrame(const nsIFrame* aFrame, float aInflation)
{
  ComputedStyle* computedStyle = aFrame->Style();
  uint8_t variantWidth = NS_FONT_VARIANT_WIDTH_NORMAL;
  if (computedStyle->IsTextCombined()) {
    MOZ_ASSERT(aFrame->IsTextFrame());
    auto textFrame = static_cast<const nsTextFrame*>(aFrame);
    auto clusters = textFrame->CountGraphemeClusters();
    if (clusters == 2) {
      variantWidth = NS_FONT_VARIANT_WIDTH_HALF;
    } else if (clusters == 3) {
      variantWidth = NS_FONT_VARIANT_WIDTH_THIRD;
    } else if (clusters == 4) {
      variantWidth = NS_FONT_VARIANT_WIDTH_QUARTER;
    }
  }
  return GetFontMetricsForComputedStyle(computedStyle, aFrame->PresContext(),
                                        aInflation, variantWidth);
}

already_AddRefed<nsFontMetrics>
nsLayoutUtils::GetFontMetricsForComputedStyle(ComputedStyle* aComputedStyle,
                                              nsPresContext* aPresContext,
                                              float aInflation,
                                              uint8_t aVariantWidth)
{
  WritingMode wm(aComputedStyle);
  const nsStyleFont* styleFont = aComputedStyle->StyleFont();
  nsFontMetrics::Params params;
  params.language = styleFont->mLanguage;
  params.explicitLanguage = styleFont->mExplicitLanguage;
  params.orientation =
    wm.IsVertical() && !wm.IsSideways() ? gfxFont::eVertical
                                        : gfxFont::eHorizontal;
  // pass the user font set object into the device context to
  // pass along to CreateFontGroup
  params.userFontSet = aPresContext->GetUserFontSet();
  params.textPerf = aPresContext->GetTextPerfMetrics();

  // When aInflation is 1.0 and we don't require width variant, avoid
  // making a local copy of the nsFont.
  // This also avoids running font.size through floats when it is large,
  // which would be lossy.  Fortunately, in such cases, aInflation is
  // guaranteed to be 1.0f.
  if (aInflation == 1.0f && aVariantWidth == NS_FONT_VARIANT_WIDTH_NORMAL) {
    return aPresContext->DeviceContext()->GetMetricsFor(styleFont->mFont, params);
  }

  nsFont font = styleFont->mFont;
  font.size = NSToCoordRound(font.size * aInflation);
  font.variantWidth = aVariantWidth;
  return aPresContext->DeviceContext()->GetMetricsFor(font, params);
}

nsIFrame*
nsLayoutUtils::FindChildContainingDescendant(nsIFrame* aParent, nsIFrame* aDescendantFrame)
{
  nsIFrame* result = aDescendantFrame;

  while (result) {
    nsIFrame* parent = result->GetParent();
    if (parent == aParent) {
      break;
    }

    // The frame is not an immediate child of aParent so walk up another level
    result = parent;
  }

  return result;
}

nsBlockFrame*
nsLayoutUtils::GetAsBlock(nsIFrame* aFrame)
{
  nsBlockFrame* block = do_QueryFrame(aFrame);
  return block;
}

nsBlockFrame*
nsLayoutUtils::FindNearestBlockAncestor(nsIFrame* aFrame)
{
  nsIFrame* nextAncestor;
  for (nextAncestor = aFrame->GetParent(); nextAncestor;
       nextAncestor = nextAncestor->GetParent()) {
    nsBlockFrame* block = GetAsBlock(nextAncestor);
    if (block)
      return block;
  }
  return nullptr;
}

nsIFrame*
nsLayoutUtils::GetNonGeneratedAncestor(nsIFrame* aFrame)
{
  if (!(aFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT))
    return aFrame;

  nsIFrame* f = aFrame;
  do {
    f = GetParentOrPlaceholderFor(f);
  } while (f->GetStateBits() & NS_FRAME_GENERATED_CONTENT);
  return f;
}

nsIFrame*
nsLayoutUtils::GetParentOrPlaceholderFor(const nsIFrame* aFrame)
{
  if ((aFrame->GetStateBits() & NS_FRAME_OUT_OF_FLOW)
      && !aFrame->GetPrevInFlow()) {
    return aFrame->GetProperty(nsIFrame::PlaceholderFrameProperty());
  }
  return aFrame->GetParent();
}

nsIFrame*
nsLayoutUtils::GetParentOrPlaceholderForCrossDoc(nsIFrame* aFrame)
{
  nsIFrame* f = GetParentOrPlaceholderFor(aFrame);
  if (f)
    return f;
  return GetCrossDocParentFrame(aFrame);
}

nsIFrame*
nsLayoutUtils::GetNextContinuationOrIBSplitSibling(nsIFrame *aFrame)
{
  nsIFrame *result = aFrame->GetNextContinuation();
  if (result)
    return result;

  if ((aFrame->GetStateBits() & NS_FRAME_PART_OF_IBSPLIT) != 0) {
    // We only store the ib-split sibling annotation with the first
    // frame in the continuation chain. Walk back to find that frame now.
    aFrame = aFrame->FirstContinuation();

    return aFrame->GetProperty(nsIFrame::IBSplitSibling());
  }

  return nullptr;
}

nsIFrame*
nsLayoutUtils::FirstContinuationOrIBSplitSibling(const nsIFrame* aFrame)
{
  nsIFrame* result = aFrame->FirstContinuation();

  if (result->GetStateBits() & NS_FRAME_PART_OF_IBSPLIT) {
    while (auto* f = result->GetProperty(nsIFrame::IBSplitPrevSibling())) {
      result = f;
    }
  }

  return result;
}

nsIFrame*
nsLayoutUtils::LastContinuationOrIBSplitSibling(const nsIFrame* aFrame)
{
  nsIFrame* result = aFrame->FirstContinuation();

  if (result->GetStateBits() & NS_FRAME_PART_OF_IBSPLIT) {
    while (auto* f = result->GetProperty(nsIFrame::IBSplitSibling())) {
      result = f;
    }
  }

  return result->LastContinuation();
}

bool
nsLayoutUtils::IsFirstContinuationOrIBSplitSibling(const nsIFrame *aFrame)
{
  if (aFrame->GetPrevContinuation()) {
    return false;
  }
  if ((aFrame->GetStateBits() & NS_FRAME_PART_OF_IBSPLIT) &&
      aFrame->GetProperty(nsIFrame::IBSplitPrevSibling())) {
    return false;
  }

  return true;
}

bool
nsLayoutUtils::IsViewportScrollbarFrame(nsIFrame* aFrame)
{
  if (!aFrame)
    return false;

  nsIFrame* rootScrollFrame = aFrame->PresShell()->GetRootScrollFrame();
  if (!rootScrollFrame)
    return false;

  nsIScrollableFrame* rootScrollableFrame = do_QueryFrame(rootScrollFrame);
  NS_ASSERTION(rootScrollableFrame, "The root scorollable frame is null");

  if (!IsProperAncestorFrame(rootScrollFrame, aFrame))
    return false;

  nsIFrame* rootScrolledFrame = rootScrollableFrame->GetScrolledFrame();
  return !(rootScrolledFrame == aFrame ||
           IsProperAncestorFrame(rootScrolledFrame, aFrame));
}

// Use only for widths/heights (or their min/max), since it clamps
// negative calc() results to 0.
static bool GetAbsoluteCoord(const nsStyleCoord& aStyle, nscoord& aResult)
{
  if (aStyle.IsCalcUnit()) {
    if (aStyle.CalcHasPercent()) {
      return false;
    }
    // If it has no percents, we can pass 0 for the percentage basis.
    aResult = aStyle.ComputeComputedCalc(0);
    if (aResult < 0)
      aResult = 0;
    return true;
  }

  if (eStyleUnit_Coord != aStyle.GetUnit())
    return false;

  aResult = aStyle.GetCoordValue();
  NS_ASSERTION(aResult >= 0, "negative widths not allowed");
  return true;
}

static nscoord
GetBSizeTakenByBoxSizing(StyleBoxSizing aBoxSizing,
                         nsIFrame* aFrame,
                         bool aHorizontalAxis,
                         bool aIgnorePadding);

// Only call on style coords for which GetAbsoluteCoord returned false.
static bool
GetPercentBSize(const nsStyleCoord& aStyle,
                nsIFrame* aFrame,
                bool aHorizontalAxis,
                nscoord& aResult)
{
  if (eStyleUnit_Percent != aStyle.GetUnit() &&
      !aStyle.IsCalcUnit())
    return false;

  MOZ_ASSERT(!aStyle.IsCalcUnit() || aStyle.CalcHasPercent(),
             "GetAbsoluteCoord should have handled this");

  // During reflow, nsHTMLScrollFrame::ReflowScrolledFrame uses
  // SetComputedHeight on the reflow state for its child to propagate its
  // computed height to the scrolled content. So here we skip to the scroll
  // frame that contains this scrolled content in order to get the same
  // behavior as layout when computing percentage heights.
  nsIFrame *f = aFrame->GetContainingBlock(nsIFrame::SKIP_SCROLLED_FRAME);
  if (!f) {
    MOZ_ASSERT_UNREACHABLE("top of frame tree not a containing block");
    return false;
  }

  WritingMode wm = f->GetWritingMode();

  const nsStylePosition *pos = f->StylePosition();
  const nsStyleCoord& bSizeCoord = pos->BSize(wm);
  nscoord h;
  if (!GetAbsoluteCoord(bSizeCoord, h) &&
      !GetPercentBSize(bSizeCoord, f, aHorizontalAxis, h)) {
    NS_ASSERTION(bSizeCoord.IsAutoOrEnum() || bSizeCoord.HasPercent(),
                 "unknown block-size unit");
    LayoutFrameType fType = f->Type();
    if (fType != LayoutFrameType::Viewport &&
        fType != LayoutFrameType::Canvas &&
        fType != LayoutFrameType::PageContent) {
      // There's no basis for the percentage height, so it acts like auto.
      // Should we consider a max-height < min-height pair a basis for
      // percentage heights?  The spec is somewhat unclear, and not doing
      // so is simpler and avoids troubling discontinuities in behavior,
      // so I'll choose not to. -LDB
      return false;
    }

    NS_ASSERTION(bSizeCoord.IsAutoOrEnum(),
                 "Unexpected block-size unit for viewport or canvas or page-content");
    // For the viewport, canvas, and page-content kids, the percentage
    // basis is just the parent block-size.
    h = f->BSize(wm);
    if (h == NS_UNCONSTRAINEDSIZE) {
      // We don't have a percentage basis after all
      return false;
    }
  }

  const nsStyleCoord& maxBSizeCoord = pos->MaxBSize(wm);

  nscoord maxh;
  if (GetAbsoluteCoord(maxBSizeCoord, maxh) ||
      GetPercentBSize(maxBSizeCoord, f, aHorizontalAxis, maxh)) {
    if (maxh < h)
      h = maxh;
  } else {
    NS_ASSERTION(maxBSizeCoord.IsAutoOrEnum() || maxBSizeCoord.HasPercent(),
                 "unknown max block-size unit");
  }

  const nsStyleCoord& minBSizeCoord = pos->MinBSize(wm);

  nscoord minh;
  if (GetAbsoluteCoord(minBSizeCoord, minh) ||
      GetPercentBSize(minBSizeCoord, f, aHorizontalAxis, minh)) {
    if (minh > h)
      h = minh;
  } else {
    NS_ASSERTION(minBSizeCoord.IsAutoOrEnum() || minBSizeCoord.HasPercent(),
                 "unknown min block-size unit");
  }

  // Now adjust h for box-sizing styles on the parent.  We never ignore padding
  // here.  That could conceivably cause some problems with fieldsets (which are
  // the one place that wants to ignore padding), but solving that here without
  // hardcoding a check for f being a fieldset-content frame is a bit of a pain.
  nscoord bSizeTakenByBoxSizing =
    GetBSizeTakenByBoxSizing(pos->mBoxSizing, f, aHorizontalAxis, false);
  h = std::max(0, h - bSizeTakenByBoxSizing);

  if (aStyle.IsCalcUnit()) {
    aResult = std::max(aStyle.ComputeComputedCalc(h), 0);
    return true;
  }

  aResult = NSToCoordRound(aStyle.GetPercentValue() * h);
  return true;
}

// Return true if aStyle can be resolved to a definite value and if so
// return that value in aResult.
static bool
GetDefiniteSize(const nsStyleCoord&       aStyle,
                nsIFrame*                 aFrame,
                bool                      aIsInlineAxis,
                const Maybe<LogicalSize>& aPercentageBasis,
                nscoord*                  aResult)
{
  switch (aStyle.GetUnit()) {
    case eStyleUnit_Coord:
      *aResult = aStyle.GetCoordValue();
      return true;
    case eStyleUnit_Percent: {
      if (aPercentageBasis.isNothing()) {
        return false;
      }
      auto wm = aFrame->GetWritingMode();
      nscoord pb = aIsInlineAxis ? aPercentageBasis.value().ISize(wm)
                                 : aPercentageBasis.value().BSize(wm);
      if (pb != NS_UNCONSTRAINEDSIZE) {
        nscoord p = NSToCoordFloorClamped(pb * aStyle.GetPercentValue());
        *aResult = std::max(nscoord(0), p);
        return true;
      }
      return false;
    }
    case eStyleUnit_Calc: {
      nsStyleCoord::Calc* calc = aStyle.GetCalcValue();
      if (calc->mPercent != 0.0f) {
        if (aPercentageBasis.isNothing()) {
          return false;
        }
        auto wm = aFrame->GetWritingMode();
        nscoord pb = aIsInlineAxis ? aPercentageBasis.value().ISize(wm)
                                   : aPercentageBasis.value().BSize(wm);
        if (pb == NS_UNCONSTRAINEDSIZE) {
          return false;
        }
        *aResult = std::max(0, calc->mLength +
                               NSToCoordFloorClamped(pb * calc->mPercent));
      } else {
        *aResult = std::max(0, calc->mLength);
      }
      return true;
    }
    default:
      return false;
  }
}

//
// NOTE: this function will be replaced by GetDefiniteSizeTakenByBoxSizing (bug 1363918).
// Please do not add new uses of this function.
//
// Get the amount of vertical space taken out of aFrame's content area due to
// its borders and paddings given the box-sizing value in aBoxSizing.  We don't
// get aBoxSizing from the frame because some callers want to compute this for
// specific box-sizing values.  aHorizontalAxis is true if our inline direction
// is horisontal and our block direction is vertical.  aIgnorePadding is true if
// padding should be ignored.
static nscoord
GetBSizeTakenByBoxSizing(StyleBoxSizing aBoxSizing,
                         nsIFrame* aFrame,
                         bool aHorizontalAxis,
                         bool aIgnorePadding)
{
  nscoord bSizeTakenByBoxSizing = 0;
  if (aBoxSizing == StyleBoxSizing::Border) {
    const nsStyleBorder* styleBorder = aFrame->StyleBorder();
    bSizeTakenByBoxSizing +=
      aHorizontalAxis ? styleBorder->GetComputedBorder().TopBottom()
                      : styleBorder->GetComputedBorder().LeftRight();
    if (!aIgnorePadding) {
      const nsStyleSides& stylePadding =
        aFrame->StylePadding()->mPadding;
      const nsStyleCoord& paddingStart =
        stylePadding.Get(aHorizontalAxis ? eSideTop : eSideLeft);
      const nsStyleCoord& paddingEnd =
        stylePadding.Get(aHorizontalAxis ? eSideBottom : eSideRight);
      nscoord pad;
      // XXXbz Calling GetPercentBSize on padding values looks bogus, since
      // percent padding is always a percentage of the inline-size of the
      // containing block.  We should perhaps just treat non-absolute paddings
      // here as 0 instead, except that in some cases the width may in fact be
      // known.  See bug 1231059.
      if (GetAbsoluteCoord(paddingStart, pad) ||
          GetPercentBSize(paddingStart, aFrame, aHorizontalAxis, pad)) {
        bSizeTakenByBoxSizing += pad;
      }
      if (GetAbsoluteCoord(paddingEnd, pad) ||
          GetPercentBSize(paddingEnd, aFrame, aHorizontalAxis, pad)) {
        bSizeTakenByBoxSizing += pad;
      }
    }
  }
  return bSizeTakenByBoxSizing;
}

// Get the amount of space taken out of aFrame's content area due to its
// borders and paddings given the box-sizing value in aBoxSizing.  We don't
// get aBoxSizing from the frame because some callers want to compute this for
// specific box-sizing values.
// aIsInlineAxis is true if we're computing for aFrame's inline axis.
// aIgnorePadding is true if padding should be ignored.
static nscoord
GetDefiniteSizeTakenByBoxSizing(StyleBoxSizing aBoxSizing,
                                nsIFrame* aFrame,
                                bool aIsInlineAxis,
                                bool aIgnorePadding,
                                const Maybe<LogicalSize>& aPercentageBasis)
{
  nscoord sizeTakenByBoxSizing = 0;
  if (MOZ_UNLIKELY(aBoxSizing == StyleBoxSizing::Border)) {
    const bool isHorizontalAxis =
      aIsInlineAxis == !aFrame->GetWritingMode().IsVertical();
    const nsStyleBorder* styleBorder = aFrame->StyleBorder();
    sizeTakenByBoxSizing =
      isHorizontalAxis ? styleBorder->GetComputedBorder().LeftRight()
                       : styleBorder->GetComputedBorder().TopBottom();
    if (!aIgnorePadding) {
      const nsStyleSides& stylePadding = aFrame->StylePadding()->mPadding;
      const nsStyleCoord& pStart =
        stylePadding.Get(isHorizontalAxis ? eSideLeft : eSideTop);
      const nsStyleCoord& pEnd =
        stylePadding.Get(isHorizontalAxis ? eSideRight : eSideBottom);
      nscoord pad;
      // XXXbz Calling GetPercentBSize on padding values looks bogus, since
      // percent padding is always a percentage of the inline-size of the
      // containing block.  We should perhaps just treat non-absolute paddings
      // here as 0 instead, except that in some cases the width may in fact be
      // known.  See bug 1231059.
      if (GetDefiniteSize(pStart, aFrame, aIsInlineAxis, aPercentageBasis, &pad) ||
          (aPercentageBasis.isNothing() &&
           GetPercentBSize(pStart, aFrame, isHorizontalAxis, pad))) {
        sizeTakenByBoxSizing += pad;
      }
      if (GetDefiniteSize(pEnd, aFrame, aIsInlineAxis, aPercentageBasis, &pad) ||
          (aPercentageBasis.isNothing() &&
           GetPercentBSize(pEnd, aFrame, isHorizontalAxis, pad))) {
        sizeTakenByBoxSizing += pad;
      }
    }
  }
  return sizeTakenByBoxSizing;
}

// Handles only -moz-max-content and -moz-min-content, and
// -moz-fit-content for min-width and max-width, since the others
// (-moz-fit-content for width, and -moz-available) have no effect on
// intrinsic widths.
enum eWidthProperty { PROP_WIDTH, PROP_MAX_WIDTH, PROP_MIN_WIDTH };
static bool
GetIntrinsicCoord(const nsStyleCoord& aStyle,
                  gfxContext* aRenderingContext,
                  nsIFrame* aFrame,
                  eWidthProperty aProperty,
                  nscoord& aResult)
{
  MOZ_ASSERT(aProperty == PROP_WIDTH || aProperty == PROP_MAX_WIDTH ||
             aProperty == PROP_MIN_WIDTH, "unexpected property");

  if (aStyle.GetUnit() != eStyleUnit_Enumerated)
    return false;
  int32_t val = aStyle.GetIntValue();
  NS_ASSERTION(val == NS_STYLE_WIDTH_MAX_CONTENT ||
               val == NS_STYLE_WIDTH_MIN_CONTENT ||
               val == NS_STYLE_WIDTH_FIT_CONTENT ||
               val == NS_STYLE_WIDTH_AVAILABLE,
               "unexpected enumerated value for width property");
  if (val == NS_STYLE_WIDTH_AVAILABLE)
    return false;
  if (val == NS_STYLE_WIDTH_FIT_CONTENT) {
    if (aProperty == PROP_WIDTH)
      return false; // handle like 'width: auto'
    if (aProperty == PROP_MAX_WIDTH)
      // constrain large 'width' values down to -moz-max-content
      val = NS_STYLE_WIDTH_MAX_CONTENT;
    else
      // constrain small 'width' or 'max-width' values up to -moz-min-content
      val = NS_STYLE_WIDTH_MIN_CONTENT;
  }

  NS_ASSERTION(val == NS_STYLE_WIDTH_MAX_CONTENT ||
               val == NS_STYLE_WIDTH_MIN_CONTENT,
               "should have reduced everything remaining to one of these");

  // If aFrame is a container for font size inflation, then shrink
  // wrapping inside of it should not apply font size inflation.
  AutoMaybeDisableFontInflation an(aFrame);

  if (val == NS_STYLE_WIDTH_MAX_CONTENT)
    aResult = aFrame->GetPrefISize(aRenderingContext);
  else
    aResult = aFrame->GetMinISize(aRenderingContext);
  return true;
}

#undef  DEBUG_INTRINSIC_WIDTH

#ifdef DEBUG_INTRINSIC_WIDTH
static int32_t gNoiseIndent = 0;
#endif

// Return true for form controls whose minimum intrinsic inline-size
// shrinks to 0 when they have a percentage inline-size (but not
// percentage max-inline-size).  (Proper replaced elements, whose
// intrinsic minimium inline-size shrinks to 0 for both percentage
// inline-size and percentage max-inline-size, are handled elsewhere.)
inline static bool
FormControlShrinksForPercentISize(nsIFrame* aFrame)
{
  if (!aFrame->IsFrameOfType(nsIFrame::eReplaced)) {
    // Quick test to reject most frames.
    return false;
  }

  LayoutFrameType fType = aFrame->Type();
  if (fType == LayoutFrameType::Meter || fType == LayoutFrameType::Progress) {
    // progress and meter do have this shrinking behavior
    // FIXME: Maybe these should be nsIFormControlFrame?
    return true;
  }

  if (!static_cast<nsIFormControlFrame*>(do_QueryFrame(aFrame))) {
    // Not a form control.  This includes fieldsets, which do not
    // shrink.
    return false;
  }

  if (fType == LayoutFrameType::GfxButtonControl ||
      fType == LayoutFrameType::HTMLButtonControl) {
    // Buttons don't have this shrinking behavior.  (Note that color
    // inputs do, even though they inherit from button, so we can't use
    // do_QueryFrame here.)
    return false;
  }

  return true;
}

// https://drafts.csswg.org/css-sizing-3/#percentage-sizing
// Return true if the above spec's rule for replaced boxes applies.
// XXX bug 1463700 will make this match the spec...
static bool
IsReplacedBoxResolvedAgainstZero(nsIFrame* aFrame,
                                 const nsStyleCoord& aStyleSize,
                                 const nsStyleCoord& aStyleMaxSize)
{
  const bool sizeHasPercent = aStyleSize.HasPercent();
  return ((sizeHasPercent || aStyleMaxSize.HasPercent()) &&
          aFrame->IsFrameOfType(nsIFrame::eReplacedSizing)) ||
         (sizeHasPercent &&
          FormControlShrinksForPercentISize(aFrame));
}

/**
 * Add aOffsets which describes what to add on outside of the content box
 * aContentSize (controlled by 'box-sizing') and apply min/max properties.
 * We have to account for these properties after getting all the offsets
 * (margin, border, padding) because percentages do not operate linearly.
 * Doing this is ok because although percentages aren't handled linearly,
 * they are handled monotonically.
 *
 * @param aContentSize the content size calculated so far
                       (@see IntrinsicForContainer)
 * @param aContentMinSize ditto min content size
 * @param aStyleSize a 'width' or 'height' property value
 * @param aFixedMinSize if aStyleMinSize is a definite size then this points to
 *                      the value, otherwise nullptr
 * @param aStyleMinSize a 'min-width' or 'min-height' property value
 * @param aFixedMaxSize if aStyleMaxSize is a definite size then this points to
 *                      the value, otherwise nullptr
 * @param aStyleMaxSize a 'max-width' or 'max-height' property value
 * @param aFlags same as for IntrinsicForContainer
 * @param aContainerWM the container's WM
 */
static nscoord
AddIntrinsicSizeOffset(gfxContext* aRenderingContext,
                       nsIFrame* aFrame,
                       const nsIFrame::IntrinsicISizeOffsetData& aOffsets,
                       nsLayoutUtils::IntrinsicISizeType aType,
                       StyleBoxSizing aBoxSizing,
                       nscoord aContentSize,
                       nscoord aContentMinSize,
                       const nsStyleCoord& aStyleSize,
                       const nscoord* aFixedMinSize,
                       const nsStyleCoord& aStyleMinSize,
                       const nscoord* aFixedMaxSize,
                       const nsStyleCoord& aStyleMaxSize,
                       uint32_t aFlags,
                       PhysicalAxis aAxis)
{
  nscoord result = aContentSize;
  nscoord min = aContentMinSize;
  nscoord coordOutsideSize = 0;

  if (!(aFlags & nsLayoutUtils::IGNORE_PADDING)) {
    coordOutsideSize += aOffsets.hPadding;
  }

  coordOutsideSize += aOffsets.hBorder;

  if (aBoxSizing == StyleBoxSizing::Border) {
    min += coordOutsideSize;
    result = NSCoordSaturatingAdd(result, coordOutsideSize);

    coordOutsideSize = 0;
  }

  coordOutsideSize += aOffsets.hMargin;

  min += coordOutsideSize;
  result = NSCoordSaturatingAdd(result, coordOutsideSize);

  nscoord size;
  if (aType == nsLayoutUtils::MIN_ISIZE &&
      ::IsReplacedBoxResolvedAgainstZero(aFrame, aStyleSize, aStyleMaxSize)) {
    // XXX bug 1463700: this doesn't handle calc() according to spec
    result = 0; // let |min| handle padding/border/margin
  } else if (GetAbsoluteCoord(aStyleSize, size) ||
             GetIntrinsicCoord(aStyleSize, aRenderingContext, aFrame,
                               PROP_WIDTH, size)) {
    result = size + coordOutsideSize;
  }

  nscoord maxSize = aFixedMaxSize ? *aFixedMaxSize : 0;
  if (aFixedMaxSize ||
      GetIntrinsicCoord(aStyleMaxSize, aRenderingContext, aFrame,
                        PROP_MAX_WIDTH, maxSize)) {
    maxSize += coordOutsideSize;
    if (result > maxSize) {
      result = maxSize;
    }
  }

  nscoord minSize = aFixedMinSize ? *aFixedMinSize : 0;
  if (aFixedMinSize ||
      GetIntrinsicCoord(aStyleMinSize, aRenderingContext, aFrame,
                        PROP_MIN_WIDTH, minSize)) {
    minSize += coordOutsideSize;
    if (result < minSize) {
      result = minSize;
    }
  }

  if (result < min) {
    result = min;
  }

  const nsStyleDisplay* disp = aFrame->StyleDisplay();
  if (aFrame->IsThemed(disp)) {
    LayoutDeviceIntSize devSize;
    bool canOverride = true;
    nsPresContext* pc = aFrame->PresContext();
    pc->GetTheme()->GetMinimumWidgetSize(pc, aFrame, disp->mAppearance,
                                         &devSize, &canOverride);
    nscoord themeSize =
      pc->DevPixelsToAppUnits(aAxis == eAxisVertical ? devSize.height
                                                     : devSize.width);
    // GetMinimumWidgetSize() returns a border-box width.
    themeSize += aOffsets.hMargin;
    if (themeSize > result || !canOverride) {
      result = themeSize;
    }
  }
  return result;
}

static void
AddStateBitToAncestors(nsIFrame* aFrame, nsFrameState aBit)
{
  for (nsIFrame* f = aFrame; f; f = f->GetParent()) {
    if (f->HasAnyStateBits(aBit)) {
      break;
    }
    f->AddStateBits(aBit);
  }
}

/* static */ nscoord
nsLayoutUtils::IntrinsicForAxis(PhysicalAxis              aAxis,
                                gfxContext*               aRenderingContext,
                                nsIFrame*                 aFrame,
                                IntrinsicISizeType        aType,
                                const Maybe<LogicalSize>& aPercentageBasis,
                                uint32_t                  aFlags,
                                nscoord                   aMarginBoxMinSizeClamp)
{
  MOZ_ASSERT(aFrame, "null frame");
  MOZ_ASSERT(aFrame->GetParent(),
             "IntrinsicForAxis called on frame not in tree");
  MOZ_ASSERT(aType == MIN_ISIZE || aType == PREF_ISIZE, "bad type");
  MOZ_ASSERT(aFrame->GetParent()->Type() != LayoutFrameType::GridContainer ||
             aPercentageBasis.isSome(),
             "grid layout should always pass a percentage basis");

  const bool horizontalAxis = MOZ_LIKELY(aAxis == eAxisHorizontal);
#ifdef DEBUG_INTRINSIC_WIDTH
  nsFrame::IndentBy(stderr, gNoiseIndent);
  static_cast<nsFrame*>(aFrame)->ListTag(stderr);
  printf_stderr(" %s %s intrinsic size for container:\n",
                aType == MIN_ISIZE ? "min" : "pref",
                horizontalAxis ? "horizontal" : "vertical");
#endif

  // If aFrame is a container for font size inflation, then shrink
  // wrapping inside of it should not apply font size inflation.
  AutoMaybeDisableFontInflation an(aFrame);

  // We want the size this frame will contribute to the parent's inline-size,
  // so we work in the parent's writing mode; but if aFrame is orthogonal to
  // its parent, we'll need to look at its BSize instead of min/pref-ISize.
  const nsStylePosition* stylePos = aFrame->StylePosition();
  StyleBoxSizing boxSizing = stylePos->mBoxSizing;

  nsStyleCoord styleMinISize =
    horizontalAxis ? stylePos->mMinWidth : stylePos->mMinHeight;
  nsStyleCoord styleISize =
    (aFlags & MIN_INTRINSIC_ISIZE) ? styleMinISize :
    (horizontalAxis ? stylePos->mWidth : stylePos->mHeight);
  MOZ_ASSERT(!(aFlags & MIN_INTRINSIC_ISIZE) ||
             styleISize.GetUnit() == eStyleUnit_Auto ||
             styleISize.GetUnit() == eStyleUnit_Enumerated,
             "should only use MIN_INTRINSIC_ISIZE for intrinsic values");
  nsStyleCoord styleMaxISize =
    horizontalAxis ? stylePos->mMaxWidth : stylePos->mMaxHeight;

  PhysicalAxis ourInlineAxis =
    aFrame->GetWritingMode().PhysicalAxis(eLogicalAxisInline);
  const bool isInlineAxis = aAxis == ourInlineAxis;

  auto resetIfKeywords = [](nsStyleCoord& aSize,
                            nsStyleCoord& aMinSize,
                            nsStyleCoord& aMaxSize) {
    if (aSize.GetUnit() == eStyleUnit_Enumerated) {
      aSize.SetAutoValue();
    }
    if (aMinSize.GetUnit() == eStyleUnit_Enumerated) {
      aMinSize.SetAutoValue();
    }
    if (aMaxSize.GetUnit() == eStyleUnit_Enumerated) {
      aMaxSize.SetNoneValue();
    }
  };
  // According to the spec, max-content and min-content should behave as the
  // property's initial values in block axis.
  // It also make senses to use the initial values for -moz-fit-content and
  // -moz-available for intrinsic size in block axis. Therefore, we reset them
  // if needed.
  if (!isInlineAxis) {
    resetIfKeywords(styleISize, styleMinISize, styleMaxISize);
  }

  // We build up two values starting with the content box, and then
  // adding padding, border and margin.  The result is normally
  // |result|.  Then, when we handle 'width', 'min-width', and
  // 'max-width', we use the results we've been building in |min| as a
  // minimum, overriding 'min-width'.  This ensures two things:
  //   * that we don't let a value of 'box-sizing' specifying a width
  //     smaller than the padding/border inside the box-sizing box give
  //     a content width less than zero
  //   * that we prevent tables from becoming smaller than their
  //     intrinsic minimum width
  nscoord result = 0, min = 0;

  nscoord maxISize;
  bool haveFixedMaxISize = GetAbsoluteCoord(styleMaxISize, maxISize);
  nscoord minISize;

  // Treat "min-width: auto" as 0.
  bool haveFixedMinISize;
  if (eStyleUnit_Auto == styleMinISize.GetUnit()) {
    // NOTE: Technically, "auto" is supposed to behave like "min-content" on
    // flex items. However, we don't need to worry about that here, because
    // flex items' min-sizes are intentionally ignored until the flex
    // container explicitly considers them during space distribution.
    minISize = 0;
    haveFixedMinISize = true;
  } else {
    haveFixedMinISize = GetAbsoluteCoord(styleMinISize, minISize);
  }

  // If we have a specified width (or a specified 'min-width' greater
  // than the specified 'max-width', which works out to the same thing),
  // don't even bother getting the frame's intrinsic width, because in
  // this case GetAbsoluteCoord(styleISize, w) will always succeed, so
  // we'll never need the intrinsic dimensions.
  if (styleISize.GetUnit() == eStyleUnit_Enumerated &&
      (styleISize.GetIntValue() == NS_STYLE_WIDTH_MAX_CONTENT ||
       styleISize.GetIntValue() == NS_STYLE_WIDTH_MIN_CONTENT)) {
    MOZ_ASSERT(isInlineAxis);
    // -moz-fit-content and -moz-available enumerated widths compute intrinsic
    // widths just like auto.
    // For -moz-max-content and -moz-min-content, we handle them like
    // specified widths, but ignore box-sizing.
    boxSizing = StyleBoxSizing::Content;
  } else if (!styleISize.ConvertsToLength() &&
             !(haveFixedMinISize && haveFixedMaxISize && maxISize <= minISize)) {
#ifdef DEBUG_INTRINSIC_WIDTH
    ++gNoiseIndent;
#endif
    if (MOZ_UNLIKELY(!isInlineAxis)) {
      IntrinsicSize intrinsicSize = aFrame->GetIntrinsicSize();
      const nsStyleCoord intrinsicBCoord =
        horizontalAxis ? intrinsicSize.width : intrinsicSize.height;
      if (intrinsicBCoord.GetUnit() == eStyleUnit_Coord) {
        result = intrinsicBCoord.GetCoordValue();
      } else {
        // We don't have an intrinsic bsize and we need aFrame's block-dir size.
        if (aFlags & BAIL_IF_REFLOW_NEEDED) {
          return NS_INTRINSIC_WIDTH_UNKNOWN;
        }
        // XXX Unfortunately, we probably don't know this yet, so this is wrong...
        // but it's not clear what we should do. If aFrame's inline size hasn't
        // been determined yet, we can't necessarily figure out its block size
        // either. For now, authors who put orthogonal elements into things like
        // buttons or table cells may have to explicitly provide sizes rather
        // than expecting intrinsic sizing to work "perfectly" in underspecified
        // cases.
        result = aFrame->BSize();
      }
    } else {
      result = aType == MIN_ISIZE
               ? aFrame->GetMinISize(aRenderingContext)
               : aFrame->GetPrefISize(aRenderingContext);
    }
#ifdef DEBUG_INTRINSIC_WIDTH
    --gNoiseIndent;
    nsFrame::IndentBy(stderr, gNoiseIndent);
    static_cast<nsFrame*>(aFrame)->ListTag(stderr);
    printf_stderr(" %s %s intrinsic size from frame is %d.\n",
                  aType == MIN_ISIZE ? "min" : "pref",
                  horizontalAxis ? "horizontal" : "vertical",
                  result);
#endif

    // Handle elements with an intrinsic ratio (or size) and a specified
    // height, min-height, or max-height.
    // NOTE: We treat "min-height:auto" as "0" for the purpose of this code,
    // since that's what it means in all cases except for on flex items -- and
    // even there, we're supposed to ignore it (i.e. treat it as 0) until the
    // flex container explicitly considers it.
    nsStyleCoord styleBSize =
      horizontalAxis ? stylePos->mHeight : stylePos->mWidth;
    nsStyleCoord styleMinBSize =
      horizontalAxis ? stylePos->mMinHeight : stylePos->mMinWidth;
    nsStyleCoord styleMaxBSize =
      horizontalAxis ? stylePos->mMaxHeight : stylePos->mMaxWidth;

    // According to the spec, max-content and min-content should behave as the
    // property's initial values in block axis.
    // It also make senses to use the initial values for -moz-fit-content and
    // -moz-available for intrinsic size in block axis. Therefore, we reset them
    // if needed.
    if (isInlineAxis) {
      resetIfKeywords(styleBSize, styleMinBSize, styleMaxBSize);
    }

    if (styleBSize.GetUnit() != eStyleUnit_Auto ||
        !(styleMinBSize.GetUnit() == eStyleUnit_Auto ||
          (styleMinBSize.GetUnit() == eStyleUnit_Coord &&
           styleMinBSize.GetCoordValue() == 0)) ||
        styleMaxBSize.GetUnit() != eStyleUnit_None) {

      nsSize ratio(aFrame->GetIntrinsicRatio());
      nscoord ratioISize = (horizontalAxis ? ratio.width  : ratio.height);
      nscoord ratioBSize = (horizontalAxis ? ratio.height : ratio.width);
      if (ratioBSize != 0) {
        AddStateBitToAncestors(aFrame,
            NS_FRAME_DESCENDANT_INTRINSIC_ISIZE_DEPENDS_ON_BSIZE);

        nscoord bSizeTakenByBoxSizing =
          GetDefiniteSizeTakenByBoxSizing(boxSizing, aFrame, !isInlineAxis,
                                          aFlags & IGNORE_PADDING,
                                          aPercentageBasis);
        // NOTE: This is only the minContentSize if we've been passed MIN_INTRINSIC_ISIZE
        // (which is fine, because this should only be used inside a check for that flag).
        nscoord minContentSize = result;
        nscoord h;
        if (GetDefiniteSize(styleBSize, aFrame, !isInlineAxis, aPercentageBasis, &h) ||
            (aPercentageBasis.isNothing() &&
             GetPercentBSize(styleBSize, aFrame, horizontalAxis, h))) {
          h = std::max(0, h - bSizeTakenByBoxSizing);
          result = NSCoordMulDiv(h, ratioISize, ratioBSize);
        }

        if (GetDefiniteSize(styleMaxBSize, aFrame, !isInlineAxis, aPercentageBasis, &h) ||
            (aPercentageBasis.isNothing() &&
             GetPercentBSize(styleMaxBSize, aFrame, horizontalAxis, h))) {
          h = std::max(0, h - bSizeTakenByBoxSizing);
          nscoord maxISize = NSCoordMulDiv(h, ratioISize, ratioBSize);
          if (maxISize < result) {
            result = maxISize;
          }
          if (maxISize < minContentSize) {
            minContentSize = maxISize;
          }
        }

        if (GetDefiniteSize(styleMinBSize, aFrame, !isInlineAxis, aPercentageBasis, &h) ||
            (aPercentageBasis.isNothing() &&
             GetPercentBSize(styleMinBSize, aFrame, horizontalAxis, h))) {
          h = std::max(0, h - bSizeTakenByBoxSizing);
          nscoord minISize = NSCoordMulDiv(h, ratioISize, ratioBSize);
          if (minISize > result) {
            result = minISize;
          }
          if (minISize > minContentSize) {
            minContentSize = minISize;
          }
        }
        if (MOZ_UNLIKELY(aFlags & nsLayoutUtils::MIN_INTRINSIC_ISIZE)) {
          // This is the 'min-width/height:auto' "transferred size" piece of:
          // https://www.w3.org/TR/css-flexbox-1/#min-width-automatic-minimum-size
          // https://drafts.csswg.org/css-grid/#min-size-auto
          result = std::min(result, minContentSize);
        }
      }
    }
  }

  if (aFrame->IsTableFrame()) {
    // Tables can't shrink smaller than their intrinsic minimum width,
    // no matter what.
    min = aFrame->GetMinISize(aRenderingContext);
  }

  nscoord pmPercentageBasis = NS_UNCONSTRAINEDSIZE;
  if (aPercentageBasis.isSome()) {
    // The padding/margin percentage basis is the inline-size in the parent's
    // writing-mode.
    auto childWM = aFrame->GetWritingMode();
    pmPercentageBasis =
      aFrame->GetParent()->GetWritingMode().IsOrthogonalTo(childWM) ?
        aPercentageBasis->BSize(childWM) :
        aPercentageBasis->ISize(childWM);
  }
  nsIFrame::IntrinsicISizeOffsetData offsets =
    MOZ_LIKELY(isInlineAxis) ? aFrame->IntrinsicISizeOffsets(pmPercentageBasis)
                             : aFrame->IntrinsicBSizeOffsets(pmPercentageBasis);
  nscoord contentBoxSize = result;
  result = AddIntrinsicSizeOffset(aRenderingContext, aFrame, offsets, aType,
                                  boxSizing, result, min, styleISize,
                                  haveFixedMinISize ? &minISize : nullptr,
                                  styleMinISize,
                                  haveFixedMaxISize ? &maxISize : nullptr,
                                  styleMaxISize,
                                  aFlags, aAxis);
  nscoord overflow = result - aMarginBoxMinSizeClamp;
  if (MOZ_UNLIKELY(overflow > 0)) {
    nscoord newContentBoxSize = std::max(nscoord(0), contentBoxSize - overflow);
    result -= contentBoxSize - newContentBoxSize;
  }

#ifdef DEBUG_INTRINSIC_WIDTH
  nsFrame::IndentBy(stderr, gNoiseIndent);
  static_cast<nsFrame*>(aFrame)->ListTag(stderr);
  printf_stderr(" %s %s intrinsic size for container is %d twips.\n",
                aType == MIN_ISIZE ? "min" : "pref",
                horizontalAxis ? "horizontal" : "vertical",
                result);
#endif

  return result;
}

/* static */ nscoord
nsLayoutUtils::IntrinsicForContainer(gfxContext* aRenderingContext,
                                     nsIFrame* aFrame,
                                     IntrinsicISizeType aType,
                                     uint32_t aFlags)
{
  MOZ_ASSERT(aFrame && aFrame->GetParent());
  // We want the size aFrame will contribute to its parent's inline-size.
  PhysicalAxis axis =
    aFrame->GetParent()->GetWritingMode().PhysicalAxis(eLogicalAxisInline);
  return IntrinsicForAxis(axis, aRenderingContext, aFrame, aType, Nothing(), aFlags);
}

/* static */ nscoord
nsLayoutUtils::MinSizeContributionForAxis(PhysicalAxis       aAxis,
                                          gfxContext*        aRC,
                                          nsIFrame*          aFrame,
                                          IntrinsicISizeType aType,
                                          const LogicalSize& aPercentageBasis,
                                          uint32_t           aFlags)
{
  MOZ_ASSERT(aFrame);
  MOZ_ASSERT(aFrame->IsFlexOrGridItem(),
             "only grid/flex items have this behavior currently");

#ifdef DEBUG_INTRINSIC_WIDTH
  nsFrame::IndentBy(stderr, gNoiseIndent);
  static_cast<nsFrame*>(aFrame)->ListTag(stderr);
  printf_stderr(" %s min-isize for %s WM:\n",
                aType == MIN_ISIZE ? "min" : "pref",
                aWM.IsVertical() ? "vertical" : "horizontal");
#endif

  // Note: this method is only meant for grid/flex items.
  const nsStylePosition* const stylePos = aFrame->StylePosition();
  nsStyleCoord size = aAxis == eAxisHorizontal ? stylePos->mMinWidth
                                               : stylePos->mMinHeight;
  nsStyleCoord maxSize = aAxis == eAxisHorizontal ? stylePos->mMaxWidth
                                                  : stylePos->mMaxHeight;
  auto childWM = aFrame->GetWritingMode();
  PhysicalAxis ourInlineAxis = childWM.PhysicalAxis(eLogicalAxisInline);
  // According to the spec, max-content and min-content should behave as the
  // property's initial values in block axis.
  // It also make senses to use the initial values for -moz-fit-content and
  // -moz-available for intrinsic size in block axis. Therefore, we reset them
  // if needed.
  if (aAxis != ourInlineAxis) {
    if (size.GetUnit() == eStyleUnit_Enumerated) {
      size.SetAutoValue();
    }
    if (maxSize.GetUnit() == eStyleUnit_Enumerated) {
      maxSize.SetNoneValue();
    }
  }

  nscoord minSize;
  nscoord* fixedMinSize = nullptr;
  auto minSizeUnit = size.GetUnit();
  if (minSizeUnit == eStyleUnit_Auto) {
    if (aFrame->StyleDisplay()->mOverflowX == NS_STYLE_OVERFLOW_VISIBLE) {
      size = aAxis == eAxisHorizontal ? stylePos->mWidth
                                      : stylePos->mHeight;
      // This is same as above: keywords should behaves as property's initial
      // values in block axis.
      if (aAxis != ourInlineAxis && size.GetUnit() == eStyleUnit_Enumerated) {
        size.SetAutoValue();
      }

      if (GetAbsoluteCoord(size, minSize)) {
        // We have a definite width/height.  This is the "specified size" in:
        // https://drafts.csswg.org/css-grid/#min-size-auto
        fixedMinSize = &minSize;
      } else if (::IsReplacedBoxResolvedAgainstZero(aFrame, size, maxSize)) {
        // XXX bug 1463700: this doesn't handle calc() according to spec
        minSize = 0;
        fixedMinSize = &minSize;
      }
      // fall through - the caller will have to deal with "transferred size"
    } else {
      // min-[width|height]:auto with overflow != visible computes to zero.
      minSize = 0;
      fixedMinSize = &minSize;
    }
  } else if (GetAbsoluteCoord(size, minSize)) {
    fixedMinSize = &minSize;
  } else if (minSizeUnit != eStyleUnit_Enumerated) {
    MOZ_ASSERT(size.HasPercent());
    minSize = 0;
    fixedMinSize = &minSize;
  }

  if (!fixedMinSize) {
    // Let the caller deal with the "content size" cases.
#ifdef DEBUG_INTRINSIC_WIDTH
    nsFrame::IndentBy(stderr, gNoiseIndent);
    static_cast<nsFrame*>(aFrame)->ListTag(stderr);
    printf_stderr(" %s min-isize is indefinite.\n",
                  aType == MIN_ISIZE ? "min" : "pref");
#endif
    return NS_UNCONSTRAINEDSIZE;
  }

  // If aFrame is a container for font size inflation, then shrink
  // wrapping inside of it should not apply font size inflation.
  AutoMaybeDisableFontInflation an(aFrame);

  // The padding/margin percentage basis is the inline-size in the parent's
  // writing-mode.
  nscoord pmPercentageBasis =
    aFrame->GetParent()->GetWritingMode().IsOrthogonalTo(childWM) ?
      aPercentageBasis.BSize(childWM) :
      aPercentageBasis.ISize(childWM);
  nsIFrame