layout/base/nsCSSFrameConstructor.cpp
author Ed Morley <emorley@mozilla.com>
Thu, 24 Oct 2013 10:28:44 +0100
changeset 166699 e33a8cab1096e170cd5585f20ecac241815995db
parent 166692 ce20f4b16d56b245848981ec472a1033bed7e82c
child 166898 44de05b3239bac97f65da0d68462baa2a0ed3042
permissions -rw-r--r--
Backed out changeset ce20f4b16d56 (bug 261037) for reftest failures in 478811-1.html on a CLOSED TREE

/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
// vim:cindent:ts=2:et:sw=2:
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * construction of a frame tree that is nearly isomorphic to the content
 * tree and updating of that tree in response to dynamic changes
 */

#include "nsCSSFrameConstructor.h"

#include "mozilla/AutoRestore.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/dom/HTMLSelectElement.h"
#include "mozilla/Likely.h"
#include "mozilla/LinkedList.h"
#include "nsAbsoluteContainingBlock.h"
#include "nsIAtom.h"
#include "nsIFrameInlines.h"
#include "nsGkAtoms.h"
#include "nsPresContext.h"
#include "nsIDocument.h"
#include "nsTableFrame.h"
#include "nsTableColFrame.h"
#include "nsIDOMHTMLDocument.h"
#include "nsHTMLParts.h"
#include "nsIPresShell.h"
#include "nsUnicharUtils.h"
#include "nsStyleSet.h"
#include "nsViewManager.h"
#include "nsEventStates.h"
#include "nsStyleConsts.h"
#include "nsIDOMXULElement.h"
#include "nsContainerFrame.h"
#include "nsINameSpaceManager.h"
#include "nsIComboboxControlFrame.h"
#include "nsIListControlFrame.h"
#include "nsIDOMCharacterData.h"
#include "nsPlaceholderFrame.h"
#include "nsTableRowGroupFrame.h"
#include "nsIFormControl.h"
#include "nsCSSAnonBoxes.h"
#include "nsTextFragment.h"
#include "nsIAnonymousContentCreator.h"
#include "nsBindingManager.h"
#include "nsXBLBinding.h"
#include "nsContentUtils.h"
#include "nsIScriptError.h"
#ifdef XP_MACOSX
#include "nsIDocShellTreeItem.h"
#endif
#include "ChildIterator.h"
#include "nsError.h"
#include "nsLayoutUtils.h"
#include "nsAutoPtr.h"
#include "nsBoxFrame.h"
#include "nsBoxLayout.h"
#include "nsFlexContainerFrame.h"
#include "nsImageFrame.h"
#include "nsIObjectLoadingContent.h"
#include "nsTArray.h"
#include "nsGenericDOMDataNode.h"
#include "mozilla/dom/Element.h"
#include "nsAutoLayoutPhase.h"
#include "nsStyleStructInlines.h"
#include "nsPageContentFrame.h"
#include "RestyleManager.h"

#ifdef MOZ_XUL
#include "nsIRootBox.h"
#endif
#ifdef ACCESSIBILITY
#include "nsAccessibilityService.h"
#endif

#include "nsBlockFrame.h"

#include "nsIScrollableFrame.h"

#include "nsXBLService.h"

#undef NOISY_FIRST_LETTER

#include "nsMathMLParts.h"
#include "mozilla/dom/SVGTests.h"
#include "nsSVGUtils.h"

#include "nsRefreshDriver.h"
#include "nsRuleProcessorData.h"
#include "nsTextNode.h"

using namespace mozilla;
using namespace mozilla::dom;

// An alias for convenience.
static const nsIFrame::ChildListID kPrincipalList = nsIFrame::kPrincipalList;

nsIFrame*
NS_NewHTMLCanvasFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewHTMLVideoFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

#include "nsSVGTextContainerFrame.h"

nsIFrame*
NS_NewSVGOuterSVGFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGOuterSVGAnonChildFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGInnerSVGFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGPathGeometryFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGGFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGGenericContainerFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGForeignObjectFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGAFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGGlyphFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGSwitchFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGTextFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGTextFrame2(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGTSpanFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGContainerFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGUseFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGViewFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
extern nsIFrame*
NS_NewSVGLinearGradientFrame(nsIPresShell *aPresShell, nsStyleContext* aContext);
extern nsIFrame*
NS_NewSVGRadialGradientFrame(nsIPresShell *aPresShell, nsStyleContext* aContext);
extern nsIFrame*
NS_NewSVGStopFrame(nsIPresShell *aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGMarkerFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGMarkerAnonChildFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
extern nsIFrame*
NS_NewSVGImageFrame(nsIPresShell *aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGClipPathFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGTextPathFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGFilterFrame(nsIPresShell *aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGPatternFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGMaskFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGFEContainerFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGFELeafFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGFEImageFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewSVGFEUnstyledLeafFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);

#include "nsINodeInfo.h"
#include "prenv.h"
#include "nsNodeInfoManager.h"
#include "nsContentCreatorFunctions.h"

#ifdef DEBUG
// Set the environment variable GECKO_FRAMECTOR_DEBUG_FLAGS to one or
// more of the following flags (comma separated) for handy debug
// output.
static bool gNoisyContentUpdates = false;
static bool gReallyNoisyContentUpdates = false;
static bool gNoisyInlineConstruction = false;

struct FrameCtorDebugFlags {
  const char* name;
  bool* on;
};

static FrameCtorDebugFlags gFlags[] = {
  { "content-updates",              &gNoisyContentUpdates },
  { "really-noisy-content-updates", &gReallyNoisyContentUpdates },
  { "noisy-inline",                 &gNoisyInlineConstruction }
};

#define NUM_DEBUG_FLAGS (sizeof(gFlags) / sizeof(gFlags[0]))
#endif


#ifdef MOZ_XUL
#include "nsMenuFrame.h"
#include "nsPopupSetFrame.h"
#include "nsTreeColFrame.h"
#include "nsIBoxObject.h"
#include "nsPIListBoxObject.h"
#include "nsListBoxBodyFrame.h"
#include "nsListItemFrame.h"
#include "nsXULLabelFrame.h"

//------------------------------------------------------------------

nsIFrame*
NS_NewAutoRepeatBoxFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewRootBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewDocElementBoxFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewThumbFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewDeckFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewLeafBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewStackFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewProgressMeterFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewRangeFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewImageBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewTextBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewGroupBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewButtonBoxFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewSplitterFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewMenuPopupFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewPopupSetFrame(nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewMenuFrame (nsIPresShell* aPresShell, nsStyleContext* aContext, uint32_t aFlags);

nsIFrame*
NS_NewMenuBarFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewTreeBodyFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

// grid
nsresult
NS_NewGridLayout2 ( nsIPresShell* aPresShell, nsBoxLayout** aNewLayout );
nsIFrame*
NS_NewGridRowLeafFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);
nsIFrame*
NS_NewGridRowGroupFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

// end grid

nsIFrame*
NS_NewTitleBarFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewResizerFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);


#endif

nsIFrame*
NS_NewHTMLScrollFrame (nsIPresShell* aPresShell, nsStyleContext* aContext, bool aIsRoot);

nsIFrame*
NS_NewXULScrollFrame (nsIPresShell* aPresShell, nsStyleContext* aContext,
                      bool aIsRoot, bool aClipAllDescendants);

nsIFrame*
NS_NewSliderFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewScrollbarFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);

nsIFrame*
NS_NewScrollbarButtonFrame (nsIPresShell* aPresShell, nsStyleContext* aContext);


#ifdef NOISY_FINDFRAME
static int32_t FFWC_totalCount=0;
static int32_t FFWC_doLoop=0;
static int32_t FFWC_doSibling=0;
static int32_t FFWC_recursions=0;
static int32_t FFWC_nextInFlows=0;
#endif

// Returns true if aFrame is an anonymous flex item
static inline bool
IsAnonymousFlexItem(const nsIFrame* aFrame)
{
  const nsIAtom* pseudoType = aFrame->StyleContext()->GetPseudo();
  return pseudoType == nsCSSAnonBoxes::anonymousFlexItem;
}

static inline nsIFrame*
GetFieldSetBlockFrame(nsIFrame* aFieldsetFrame)
{
  // Depends on the fieldset child frame order - see ConstructFieldSetFrame() below.
  nsIFrame* firstChild = aFieldsetFrame->GetFirstPrincipalChild();
  return firstChild && firstChild->GetNextSibling() ? firstChild->GetNextSibling() : firstChild;
}

#define FCDATA_DECL(_flags, _func)                          \
  { _flags, { (FrameCreationFunc)_func }, nullptr, nullptr }
#define FCDATA_WITH_WRAPPING_BLOCK(_flags, _func, _anon_box)  \
  { _flags | FCDATA_CREATE_BLOCK_WRAPPER_FOR_ALL_KIDS,        \
      { (FrameCreationFunc)_func }, nullptr, &_anon_box }

//----------------------------------------------------------------------

/**
 * True if aFrame is an actual inline frame in the sense of non-replaced
 * display:inline CSS boxes.  In other words, it can be affected by {ib}
 * splitting and can contain first-letter frames.  Basically, this is either an
 * inline frame (positioned or otherwise) or an line frame (this last because
 * it can contain first-letter and because inserting blocks in the middle of it
 * needs to terminate it).
 */
static bool
IsInlineFrame(const nsIFrame* aFrame)
{
  return aFrame->IsFrameOfType(nsIFrame::eLineParticipant);
}

/**
 * True if aFrame is an instance of an SVG frame class or is an inline/block
 * frame being used for SVG text.
 */
static bool
IsFrameForSVG(const nsIFrame* aFrame)
{
  return aFrame->IsFrameOfType(nsIFrame::eSVG) ||
         aFrame->IsSVGText();
}

/**
 * Returns true iff aFrame explicitly prevents its descendants from floating
 * (at least, down to the level of descendants which themselves are
 * float-containing blocks -- those will manage the floating status of any
 * lower-level descendents inside them, of course).
 */
static bool
ShouldSuppressFloatingOfDescendants(nsIFrame* aFrame)
{
  return aFrame->IsFrameOfType(nsIFrame::eMathML) ||
    aFrame->IsBoxFrame() ||
    aFrame->GetType() == nsGkAtoms::flexContainerFrame;
}

/**
 * If any children require a block parent, return the first such child.
 * Otherwise return null.
 */
static nsIContent*
AnyKidsNeedBlockParent(nsIFrame *aFrameList)
{
  for (nsIFrame *k = aFrameList; k; k = k->GetNextSibling()) {
    // Line participants, such as text and inline frames, can't be
    // directly inside a XUL box; they must be wrapped in an
    // intermediate block.
    if (k->IsFrameOfType(nsIFrame::eLineParticipant)) {
      return k->GetContent();
    }
  }
  return nullptr;
}

// Reparent a frame into a wrapper frame that is a child of its old parent.
static void
ReparentFrame(RestyleManager* aRestyleManager,
              nsIFrame* aNewParentFrame,
              nsIFrame* aFrame)
{
  aFrame->SetParent(aNewParentFrame);
  aRestyleManager->ReparentStyleContext(aFrame);
}

static void
ReparentFrames(nsCSSFrameConstructor* aFrameConstructor,
               nsIFrame* aNewParentFrame,
               const nsFrameList& aFrameList)
{
  RestyleManager* restyleManager = aFrameConstructor->RestyleManager();
  for (nsFrameList::Enumerator e(aFrameList); !e.AtEnd(); e.Next()) {
    ReparentFrame(restyleManager, aNewParentFrame, e.get());
  }
}

//----------------------------------------------------------------------
//
// When inline frames get weird and have block frames in them, we
// annotate them to help us respond to incremental content changes
// more easily.

static inline bool
IsFrameSpecial(nsIFrame* aFrame)
{
  return (aFrame->GetStateBits() & NS_FRAME_IS_SPECIAL) != 0;
}

static nsIFrame* GetSpecialSibling(nsIFrame* aFrame)
{
  NS_PRECONDITION(IsFrameSpecial(aFrame), "Shouldn't call this");

  // We only store the "special sibling" annotation with the first
  // frame in the continuation chain. Walk back to find that frame now.
  return static_cast<nsIFrame*>
    (aFrame->FirstContinuation()->
       Properties().Get(nsIFrame::IBSplitSpecialSibling()));
}

static nsIFrame* GetSpecialPrevSibling(nsIFrame* aFrame)
{
  NS_PRECONDITION(IsFrameSpecial(aFrame), "Shouldn't call this");
  
  // We only store the "special sibling" annotation with the first
  // frame in the continuation chain. Walk back to find that frame now.  
  return static_cast<nsIFrame*>
    (aFrame->FirstContinuation()->
       Properties().Get(nsIFrame::IBSplitSpecialPrevSibling()));
}

static nsIFrame*
GetLastSpecialSibling(nsIFrame* aFrame, bool aReturnEmptyTrailingInline)
{
  for (nsIFrame *frame = aFrame, *next; ; frame = next) {
    next = GetSpecialSibling(frame);
    if (!next ||
        (!aReturnEmptyTrailingInline && !next->GetFirstPrincipalChild() &&
         !GetSpecialSibling(next))) {
      NS_ASSERTION(!next || !frame->IsInlineOutside(),
                   "Should have a block here!");
      return frame;
    }
  }
  NS_NOTREACHED("unreachable code");
  return nullptr;
}

static void
SetFrameIsSpecial(nsIFrame* aFrame, nsIFrame* aSpecialSibling)
{
  NS_PRECONDITION(aFrame, "bad args!");

  // We should be the only continuation
  NS_ASSERTION(!aFrame->GetPrevContinuation(),
               "assigning special sibling to other than first continuation!");
  NS_ASSERTION(!aFrame->GetNextContinuation() ||
               IsFrameSpecial(aFrame->GetNextContinuation()),
               "should have no non-special continuations here");

  // Mark the frame as "special".
  aFrame->AddStateBits(NS_FRAME_IS_SPECIAL);

  if (aSpecialSibling) {
    NS_ASSERTION(!aSpecialSibling->GetPrevContinuation(),
                 "assigning something other than the first continuation as the "
                 "special sibling");

    // Store the "special sibling" (if we were given one) with the
    // first frame in the flow.
    FramePropertyTable* props = aFrame->PresContext()->PropertyTable();
    props->Set(aFrame, nsIFrame::IBSplitSpecialSibling(), aSpecialSibling);
    props->Set(aSpecialSibling, nsIFrame::IBSplitSpecialPrevSibling(), aFrame);
  }
}

static nsIFrame*
GetIBContainingBlockFor(nsIFrame* aFrame)
{
  NS_PRECONDITION(IsFrameSpecial(aFrame),
                  "GetIBContainingBlockFor() should only be called on known IB frames");

  // Get the first "normal" ancestor of the target frame.
  nsIFrame* parentFrame;
  do {
    parentFrame = aFrame->GetParent();

    if (! parentFrame) {
      NS_ERROR("no unsplit block frame in IB hierarchy");
      return aFrame;
    }

    // Note that we ignore non-special frames which have a pseudo on their
    // style context -- they're not the frames we're looking for!  In
    // particular, they may be hiding a real parent that _is_ special.
    if (!IsFrameSpecial(parentFrame) &&
        !parentFrame->StyleContext()->GetPseudo())
      break;

    aFrame = parentFrame;
  } while (1);
 
  // post-conditions
  NS_ASSERTION(parentFrame, "no normal ancestor found for special frame in GetIBContainingBlockFor");
  NS_ASSERTION(parentFrame != aFrame, "parentFrame is actually the child frame - bogus reslt");

  return parentFrame;
}

//----------------------------------------------------------------------

// Block/inline frame construction logic. We maintain a few invariants here:
//
// 1. Block frames contain block and inline frames.
//
// 2. Inline frames only contain inline frames. If an inline parent has a block
// child then the block child is migrated upward until it lands in a block
// parent (the inline frames containing block is where it will end up).

// After this function returns, aLink is pointing to the first link at or
// after its starting position for which the next frame is a block.  If there
// is no such link, it points to the end of the list.
static void
FindFirstBlock(nsFrameList::FrameLinkEnumerator& aLink)
{
  for ( ; !aLink.AtEnd(); aLink.Next()) {
    if (!aLink.NextFrame()->IsInlineOutside()) {
      return;
    }
  }
}

// This function returns a frame link enumerator pointing to the first link in
// the list for which the next frame is not block.  If there is no such link,
// it points to the end of the list.
static nsFrameList::FrameLinkEnumerator
FindFirstNonBlock(const nsFrameList& aList)
{
  nsFrameList::FrameLinkEnumerator link(aList);
  for (; !link.AtEnd(); link.Next()) {
    if (link.NextFrame()->IsInlineOutside()) {
      break;
    }
  }
  return link;
}

inline void
SetInitialSingleChild(nsIFrame* aParent, nsIFrame* aFrame)
{
  NS_PRECONDITION(!aFrame->GetNextSibling(), "Should be using a frame list");
  nsFrameList temp(aFrame, aFrame);
  aParent->SetInitialChildList(kPrincipalList, temp);
}

// -----------------------------------------------------------

// Structure used when constructing formatting object trees.
struct nsFrameItems : public nsFrameList
{
  // Appends the frame to the end of the list
  void AddChild(nsIFrame* aChild);
};

void 
nsFrameItems::AddChild(nsIFrame* aChild)
{
  NS_PRECONDITION(aChild, "nsFrameItems::AddChild");

  // It'd be really nice if we could just AppendFrames(kPrincipalList, aChild) here,
  // but some of our callers put frames that have different
  // parents (caption, I'm looking at you) on the same framelist, and
  // nsFrameList asserts if you try to do that.
  if (IsEmpty()) {
    SetFrames(aChild);
  }
  else {
    NS_ASSERTION(aChild != mLastChild,
                 "Same frame being added to frame list twice?");
    mLastChild->SetNextSibling(aChild);
    mLastChild = nsLayoutUtils::GetLastSibling(aChild);
  }
}

// -----------------------------------------------------------

// Structure used when constructing formatting object trees. Contains
// state information needed for absolutely positioned elements
struct nsAbsoluteItems : nsFrameItems {
  // containing block for absolutely positioned elements
  nsIFrame* containingBlock;
  
  nsAbsoluteItems(nsIFrame* aContainingBlock);
#ifdef DEBUG
  // XXXbz Does this need a debug-only assignment operator that nulls out the
  // childList in the nsAbsoluteItems we're copying?  Introducing a difference
  // between debug and non-debug behavior seems bad, so I guess not...
  ~nsAbsoluteItems() {
    NS_ASSERTION(!FirstChild(),
                 "Dangling child list.  Someone forgot to insert it?");
  }
#endif
  
  // Appends the frame to the end of the list
  void AddChild(nsIFrame* aChild);
};

nsAbsoluteItems::nsAbsoluteItems(nsIFrame* aContainingBlock)
  : containingBlock(aContainingBlock)
{
}

// Additional behavior is that it sets the frame's NS_FRAME_OUT_OF_FLOW flag
void
nsAbsoluteItems::AddChild(nsIFrame* aChild)
{
  NS_ASSERTION(aChild->PresContext()->FrameManager()->
               GetPlaceholderFrameFor(aChild),
               "Child without placeholder being added to nsAbsoluteItems?");
  aChild->AddStateBits(NS_FRAME_OUT_OF_FLOW);
  nsFrameItems::AddChild(aChild);
}

// -----------------------------------------------------------

// Structure for saving the existing state when pushing/poping containing
// blocks. The destructor restores the state to its previous state
class MOZ_STACK_CLASS nsFrameConstructorSaveState {
public:
  typedef nsIFrame::ChildListID ChildListID;
  nsFrameConstructorSaveState();
  ~nsFrameConstructorSaveState();

private:
  nsAbsoluteItems* mItems;      // pointer to struct whose data we save/restore
  nsAbsoluteItems  mSavedItems; // copy of original data

  // The name of the child list in which our frames would belong
  ChildListID mChildListID;
  nsFrameConstructorState* mState;

  // State used only when we're saving the abs-pos state for a transformed
  // element.
  nsAbsoluteItems mSavedFixedItems;

  bool mSavedFixedPosIsAbsPos;

  friend class nsFrameConstructorState;
};

// Structure used to keep track of a list of bindings we need to call
// AddToAttachedQueue on.  These should be in post-order depth-first
// flattened tree traversal order.
struct PendingBinding : public LinkedListElement<PendingBinding>
{
#ifdef NS_BUILD_REFCNT_LOGGING
  PendingBinding() {
    MOZ_COUNT_CTOR(PendingBinding);
  }
  ~PendingBinding() {
    MOZ_COUNT_DTOR(PendingBinding);
  }
#endif

  nsRefPtr<nsXBLBinding> mBinding;
};

// Structure used for maintaining state information during the
// frame construction process
class MOZ_STACK_CLASS nsFrameConstructorState {
public:
  typedef nsIFrame::ChildListID ChildListID;

  nsPresContext            *mPresContext;
  nsIPresShell             *mPresShell;
  nsFrameManager           *mFrameManager;

#ifdef MOZ_XUL
  // Frames destined for the kPopupList.
  nsAbsoluteItems           mPopupItems;
#endif

  // Containing block information for out-of-flow frames.
  nsAbsoluteItems           mFixedItems;
  nsAbsoluteItems           mAbsoluteItems;
  nsAbsoluteItems           mFloatedItems;

  nsCOMPtr<nsILayoutHistoryState> mFrameState;
  // These bits will be added to the state bits of any frame we construct
  // using this state.
  nsFrameState              mAdditionalStateBits;

  // When working with the -moz-transform property, we want to hook
  // the abs-pos and fixed-pos lists together, since transformed
  // elements are fixed-pos containing blocks.  This flag determines
  // whether or not we want to wire the fixed-pos and abs-pos lists
  // together.
  bool                      mFixedPosIsAbsPos;

  // A boolean to indicate whether we have a "pending" popupgroup.  That is, we
  // have already created the FrameConstructionItem for the root popupgroup but
  // we have not yet created the relevant frame.
  bool                      mHavePendingPopupgroup;

  // If false (which is the default) then call SetPrimaryFrame() as needed
  // during frame construction.  If true, don't make any SetPrimaryFrame()
  // calls, except for generated content which doesn't have a primary frame
  // yet.  The mCreatingExtraFrames == true mode is meant to be used for
  // construction of random "extra" frames for elements via normal frame
  // construction APIs (e.g. replication of things across pages in paginated
  // mode).
  bool                      mCreatingExtraFrames;

  nsCOMArray<nsIContent>    mGeneratedTextNodesWithInitializer;

  TreeMatchContext          mTreeMatchContext;

  // Constructor
  // Use the passed-in history state.
  nsFrameConstructorState(nsIPresShell*          aPresShell,
                          nsIFrame*              aFixedContainingBlock,
                          nsIFrame*              aAbsoluteContainingBlock,
                          nsIFrame*              aFloatContainingBlock,
                          nsILayoutHistoryState* aHistoryState);
  // Get the history state from the pres context's pres shell.
  nsFrameConstructorState(nsIPresShell*          aPresShell,
                          nsIFrame*              aFixedContainingBlock,
                          nsIFrame*              aAbsoluteContainingBlock,
                          nsIFrame*              aFloatContainingBlock);

  ~nsFrameConstructorState();
  
  // Function to push the existing absolute containing block state and
  // create a new scope. Code that uses this function should get matching
  // logic in GetAbsoluteContainingBlock.
  // Also makes aNewAbsoluteContainingBlock the containing block for
  // fixed-pos elements if necessary.
  // aPositionedFrame is the frame whose style actually makes
  // aNewAbsoluteContainingBlock a containing block. E.g. for a scrollable element
  // aPositionedFrame is the element's primary frame and
  // aNewAbsoluteContainingBlock is the scrolled frame.
  void PushAbsoluteContainingBlock(nsIFrame* aNewAbsoluteContainingBlock,
                                   nsIFrame* aPositionedFrame,
                                   nsFrameConstructorSaveState& aSaveState);

  // Function to push the existing float containing block state and
  // create a new scope. Code that uses this function should get matching
  // logic in GetFloatContainingBlock.
  // Pushing a null float containing block forbids any frames from being
  // floated until a new float containing block is pushed.
  // XXX we should get rid of null float containing blocks and teach the
  // various frame classes to deal with floats instead.
  void PushFloatContainingBlock(nsIFrame* aNewFloatContainingBlock,
                                nsFrameConstructorSaveState& aSaveState);

  // Function to return the proper geometric parent for a frame with display
  // struct given by aStyleDisplay and parent's frame given by
  // aContentParentFrame.
  nsIFrame* GetGeometricParent(const nsStyleDisplay* aStyleDisplay,
                               nsIFrame* aContentParentFrame) const;

  /**
   * Function to add a new frame to the right frame list.  This MUST be called
   * on frames before their children have been processed if the frames might
   * conceivably be out-of-flow; otherwise cleanup in error cases won't work
   * right.  Also, this MUST be called on frames after they have been
   * initialized.
   * @param aNewFrame the frame to add
   * @param aFrameItems the list to add in-flow frames to
   * @param aContent the content pointer for aNewFrame
   * @param aStyleContext the style context resolved for aContent
   * @param aParentFrame the parent frame for the content if it were in-flow
   * @param aCanBePositioned pass false if the frame isn't allowed to be
   *        positioned
   * @param aCanBeFloated pass false if the frame isn't allowed to be
   *        floated
   * @param aIsOutOfFlowPopup pass true if the frame is an out-of-flow popup
   *        (XUL-only)
   */
  void AddChild(nsIFrame* aNewFrame,
                nsFrameItems& aFrameItems,
                nsIContent* aContent,
                nsStyleContext* aStyleContext,
                nsIFrame* aParentFrame,
                bool aCanBePositioned = true,
                bool aCanBeFloated = true,
                bool aIsOutOfFlowPopup = false,
                bool aInsertAfter = false,
                nsIFrame* aInsertAfterFrame = nullptr);

  /**
   * Function to return the fixed-pos element list.  Normally this will just hand back the
   * fixed-pos element list, but in case we're dealing with a transformed element that's
   * acting as an abs-pos and fixed-pos container, we'll hand back the abs-pos list.  Callers should
   * use this function if they want to get the list acting as the fixed-pos item parent.
   */
  nsAbsoluteItems& GetFixedItems()
  {
    return mFixedPosIsAbsPos ? mAbsoluteItems : mFixedItems;
  }
  const nsAbsoluteItems& GetFixedItems() const
  {
    return mFixedPosIsAbsPos ? mAbsoluteItems : mFixedItems;
  }


  /**
   * class to automatically push and pop a pending binding in the frame
   * constructor state.  See nsCSSFrameConstructor::FrameConstructionItem
   * mPendingBinding documentation.
   */
  class PendingBindingAutoPusher;
  friend class PendingBindingAutoPusher;
  class MOZ_STACK_CLASS PendingBindingAutoPusher {
  public:
    PendingBindingAutoPusher(nsFrameConstructorState& aState,
                             PendingBinding* aPendingBinding) :
      mState(aState),
      mPendingBinding(aState.mCurrentPendingBindingInsertionPoint)
        {
          if (aPendingBinding) {
            aState.mCurrentPendingBindingInsertionPoint = aPendingBinding;
          }
        }

    ~PendingBindingAutoPusher()
      {
        mState.mCurrentPendingBindingInsertionPoint = mPendingBinding;
      }

  private:
    nsFrameConstructorState& mState;
    PendingBinding* mPendingBinding;
  };

  /**
   * Add a new pending binding to the list
   */
  void AddPendingBinding(PendingBinding* aPendingBinding) {
    if (mCurrentPendingBindingInsertionPoint) {
      mCurrentPendingBindingInsertionPoint->setPrevious(aPendingBinding);
    } else {
      mPendingBindings.insertBack(aPendingBinding);
    }
  }

protected:
  friend class nsFrameConstructorSaveState;

  /**
   * ProcessFrameInsertions takes the frames in aFrameItems and adds them as
   * kids to the aChildListID child list of |aFrameItems.containingBlock|.
   */
  void ProcessFrameInsertions(nsAbsoluteItems& aFrameItems,
                              ChildListID aChildListID);

  // Our list of all pending bindings.  When we're done, we need to call
  // AddToAttachedQueue on all of them, in order.
  LinkedList<PendingBinding> mPendingBindings;

  PendingBinding* mCurrentPendingBindingInsertionPoint;
};

nsFrameConstructorState::nsFrameConstructorState(nsIPresShell*          aPresShell,
                                                 nsIFrame*              aFixedContainingBlock,
                                                 nsIFrame*              aAbsoluteContainingBlock,
                                                 nsIFrame*              aFloatContainingBlock,
                                                 nsILayoutHistoryState* aHistoryState)
  : mPresContext(aPresShell->GetPresContext()),
    mPresShell(aPresShell),
    mFrameManager(aPresShell->FrameManager()),
#ifdef MOZ_XUL    
    mPopupItems(nullptr),
#endif
    mFixedItems(aFixedContainingBlock),
    mAbsoluteItems(aAbsoluteContainingBlock),
    mFloatedItems(aFloatContainingBlock),
    // See PushAbsoluteContaningBlock below
    mFrameState(aHistoryState),
    mAdditionalStateBits(0),
    // If the fixed-pos containing block is equal to the abs-pos containing
    // block, use the abs-pos containing block's abs-pos list for fixed-pos
	// frames.
    mFixedPosIsAbsPos(aFixedContainingBlock == aAbsoluteContainingBlock),
    mHavePendingPopupgroup(false),
    mCreatingExtraFrames(false),
    mTreeMatchContext(true, nsRuleWalker::eRelevantLinkUnvisited,
                      aPresShell->GetDocument()),
    mCurrentPendingBindingInsertionPoint(nullptr)
{
#ifdef MOZ_XUL
  nsIRootBox* rootBox = nsIRootBox::GetRootBox(aPresShell);
  if (rootBox) {
    mPopupItems.containingBlock = rootBox->GetPopupSetFrame();
  }
#endif
  MOZ_COUNT_CTOR(nsFrameConstructorState);
}

nsFrameConstructorState::nsFrameConstructorState(nsIPresShell* aPresShell,
                                                 nsIFrame*     aFixedContainingBlock,
                                                 nsIFrame*     aAbsoluteContainingBlock,
                                                 nsIFrame*     aFloatContainingBlock)
  : mPresContext(aPresShell->GetPresContext()),
    mPresShell(aPresShell),
    mFrameManager(aPresShell->FrameManager()),
#ifdef MOZ_XUL    
    mPopupItems(nullptr),
#endif
    mFixedItems(aFixedContainingBlock),
    mAbsoluteItems(aAbsoluteContainingBlock),
    mFloatedItems(aFloatContainingBlock),
    // See PushAbsoluteContaningBlock below
    mAdditionalStateBits(0),
    // If the fixed-pos containing block is equal to the abs-pos containing
    // block, use the abs-pos containing block's abs-pos list for fixed-pos
	// frames.
    mFixedPosIsAbsPos(aFixedContainingBlock == aAbsoluteContainingBlock),
    mHavePendingPopupgroup(false),
    mCreatingExtraFrames(false),
    mTreeMatchContext(true, nsRuleWalker::eRelevantLinkUnvisited,
                      aPresShell->GetDocument()),
    mCurrentPendingBindingInsertionPoint(nullptr)
{
#ifdef MOZ_XUL
  nsIRootBox* rootBox = nsIRootBox::GetRootBox(aPresShell);
  if (rootBox) {
    mPopupItems.containingBlock = rootBox->GetPopupSetFrame();
  }
#endif
  MOZ_COUNT_CTOR(nsFrameConstructorState);
  mFrameState = aPresShell->GetDocument()->GetLayoutHistoryState();
}

nsFrameConstructorState::~nsFrameConstructorState()
{
  // Frame order comparison functions only work properly when the placeholders
  // have been inserted into the frame tree. So for example if we have a new float
  // containing the placeholder for a new abs-pos frame, and we process the abs-pos
  // insertion first, then we won't be able to find the right place to insert in
  // in the abs-pos list. So put floats in first, because they can contain placeholders
  // for abs-pos and fixed-pos items whose containing blocks are outside the floats.
  // Then put abs-pos frames in, because they can contain placeholders for fixed-pos
  // items whose containing block is outside the abs-pos frames. 
  MOZ_COUNT_DTOR(nsFrameConstructorState);
  ProcessFrameInsertions(mFloatedItems, nsIFrame::kFloatList);
  ProcessFrameInsertions(mAbsoluteItems, nsIFrame::kAbsoluteList);
  ProcessFrameInsertions(mFixedItems, nsIFrame::kFixedList);
#ifdef MOZ_XUL
  ProcessFrameInsertions(mPopupItems, nsIFrame::kPopupList);
#endif
  for (int32_t i = mGeneratedTextNodesWithInitializer.Count() - 1; i >= 0; --i) {
    mGeneratedTextNodesWithInitializer[i]->
      DeleteProperty(nsGkAtoms::genConInitializerProperty);
  }
  if (!mPendingBindings.isEmpty()) {
    nsBindingManager* bindingManager = mPresShell->GetDocument()->BindingManager();
    do {
      nsAutoPtr<PendingBinding> pendingBinding;
      pendingBinding = mPendingBindings.popFirst();
      bindingManager->AddToAttachedQueue(pendingBinding->mBinding);
    } while (!mPendingBindings.isEmpty());
    mCurrentPendingBindingInsertionPoint = nullptr;
  }
}

static nsIFrame*
AdjustAbsoluteContainingBlock(nsIFrame* aContainingBlockIn)
{
  if (!aContainingBlockIn) {
    return nullptr;
  }
  
  // Always use the container's first continuation. (Inline frames can have
  // non-fluid bidi continuations...)
  return aContainingBlockIn->FirstContinuation();
}

void
nsFrameConstructorState::PushAbsoluteContainingBlock(nsIFrame* aNewAbsoluteContainingBlock,
                                                     nsIFrame* aPositionedFrame,
                                                     nsFrameConstructorSaveState& aSaveState)
{
  aSaveState.mItems = &mAbsoluteItems;
  aSaveState.mSavedItems = mAbsoluteItems;
  aSaveState.mChildListID = nsIFrame::kAbsoluteList;
  aSaveState.mState = this;
  aSaveState.mSavedFixedPosIsAbsPos = mFixedPosIsAbsPos;

  if (mFixedPosIsAbsPos) {
    // Since we're going to replace mAbsoluteItems, we need to save it into
    // mFixedItems now (and save the current value of mFixedItems).
    aSaveState.mSavedFixedItems = mFixedItems;
    mFixedItems = mAbsoluteItems;
  }

  mAbsoluteItems =
    nsAbsoluteItems(AdjustAbsoluteContainingBlock(aNewAbsoluteContainingBlock));

  /* See if we're wiring the fixed-pos and abs-pos lists together.  This happens iff
   * we're a transformed element.
   */
  mFixedPosIsAbsPos = aPositionedFrame &&
      aPositionedFrame->StyleDisplay()->HasTransform(aPositionedFrame);

  if (aNewAbsoluteContainingBlock) {
    aNewAbsoluteContainingBlock->MarkAsAbsoluteContainingBlock();
  }
}

void
nsFrameConstructorState::PushFloatContainingBlock(nsIFrame* aNewFloatContainingBlock,
                                                  nsFrameConstructorSaveState& aSaveState)
{
  NS_PRECONDITION(!aNewFloatContainingBlock ||
                  aNewFloatContainingBlock->IsFloatContainingBlock(),
                  "Please push a real float containing block!");
  NS_ASSERTION(!aNewFloatContainingBlock ||
               !ShouldSuppressFloatingOfDescendants(aNewFloatContainingBlock),
               "We should not push a frame that is supposed to _suppress_ "
               "floats as a float containing block!");
  aSaveState.mItems = &mFloatedItems;
  aSaveState.mSavedItems = mFloatedItems;
  aSaveState.mChildListID = nsIFrame::kFloatList;
  aSaveState.mState = this;
  mFloatedItems = nsAbsoluteItems(aNewFloatContainingBlock);
}

nsIFrame*
nsFrameConstructorState::GetGeometricParent(const nsStyleDisplay* aStyleDisplay,
                                            nsIFrame* aContentParentFrame) const
{
  NS_PRECONDITION(aStyleDisplay, "Must have display struct!");

  // If there is no container for a fixed, absolute, or floating root
  // frame, we will ignore the positioning.  This hack is originally
  // brought to you by the letter T: tables, since other roots don't
  // even call into this code.  See bug 178855.
  //
  // XXX Disabling positioning in this case is a hack.  If one was so inclined,
  // one could support this either by (1) inserting a dummy block between the
  // table and the canvas or (2) teaching the canvas how to reflow positioned
  // elements. (1) has the usual problems when multiple frames share the same
  // content (notice all the special cases in this file dealing with inner
  // tables and outer tables which share the same content). (2) requires some
  // work and possible factoring.
  //
  // XXXbz couldn't we just force position to "static" on roots and
  // float to "none"?  That's OK per CSS 2.1, as far as I can tell.
  
  if (aContentParentFrame && aContentParentFrame->IsSVGText()) {
    return aContentParentFrame;
  }

  if (aStyleDisplay->IsFloatingStyle() && mFloatedItems.containingBlock) {
    NS_ASSERTION(!aStyleDisplay->IsAbsolutelyPositionedStyle(),
                 "Absolutely positioned _and_ floating?");
    return mFloatedItems.containingBlock;
  }

  if (aStyleDisplay->mPosition == NS_STYLE_POSITION_ABSOLUTE &&
      mAbsoluteItems.containingBlock) {
    return mAbsoluteItems.containingBlock;
  }

  if (aStyleDisplay->mPosition == NS_STYLE_POSITION_FIXED &&
      GetFixedItems().containingBlock) {
    return GetFixedItems().containingBlock;
  }

  return aContentParentFrame;
}

void
nsFrameConstructorState::AddChild(nsIFrame* aNewFrame,
                                  nsFrameItems& aFrameItems,
                                  nsIContent* aContent,
                                  nsStyleContext* aStyleContext,
                                  nsIFrame* aParentFrame,
                                  bool aCanBePositioned,
                                  bool aCanBeFloated,
                                  bool aIsOutOfFlowPopup,
                                  bool aInsertAfter,
                                  nsIFrame* aInsertAfterFrame)
{
  NS_PRECONDITION(!aNewFrame->GetNextSibling(), "Shouldn't happen");
  
  const nsStyleDisplay* disp = aNewFrame->StyleDisplay();
  
  // The comments in GetGeometricParent regarding root table frames
  // all apply here, unfortunately.

  bool needPlaceholder = false;
  nsFrameState placeholderType;
  nsFrameItems* frameItems = &aFrameItems;
#ifdef MOZ_XUL
  if (MOZ_UNLIKELY(aIsOutOfFlowPopup)) {
      NS_ASSERTION(aNewFrame->GetParent() == mPopupItems.containingBlock,
                   "Popup whose parent is not the popup containing block?");
      NS_ASSERTION(mPopupItems.containingBlock, "Must have a popup set frame!");
      needPlaceholder = true;
      frameItems = &mPopupItems;
      placeholderType = PLACEHOLDER_FOR_POPUP;
  }
  else
#endif // MOZ_XUL
  if (aCanBeFloated && aNewFrame->IsFloating() &&
      mFloatedItems.containingBlock) {
    NS_ASSERTION(aNewFrame->GetParent() == mFloatedItems.containingBlock,
                 "Float whose parent is not the float containing block?");
    needPlaceholder = true;
    frameItems = &mFloatedItems;
    placeholderType = PLACEHOLDER_FOR_FLOAT;
  }
  else if (aCanBePositioned) {
    if (disp->mPosition == NS_STYLE_POSITION_ABSOLUTE &&
        mAbsoluteItems.containingBlock) {
      NS_ASSERTION(aNewFrame->GetParent() == mAbsoluteItems.containingBlock,
                   "Abs pos whose parent is not the abs pos containing block?");
      needPlaceholder = true;
      frameItems = &mAbsoluteItems;
      placeholderType = PLACEHOLDER_FOR_ABSPOS;
    }
    if (disp->mPosition == NS_STYLE_POSITION_FIXED &&
        GetFixedItems().containingBlock) {
      NS_ASSERTION(aNewFrame->GetParent() == GetFixedItems().containingBlock,
                   "Fixed pos whose parent is not the fixed pos containing block?");
      needPlaceholder = true;
      frameItems = &GetFixedItems();
      placeholderType = PLACEHOLDER_FOR_FIXEDPOS;
    }
  }

  if (needPlaceholder) {
    NS_ASSERTION(frameItems != &aFrameItems,
                 "Putting frame in-flow _and_ want a placeholder?");
    nsIFrame* placeholderFrame =
      nsCSSFrameConstructor::CreatePlaceholderFrameFor(mPresShell,
                                                       aContent,
                                                       aNewFrame,
                                                       aStyleContext,
                                                       aParentFrame,
                                                       nullptr,
                                                       placeholderType);

    placeholderFrame->AddStateBits(mAdditionalStateBits);
    // Add the placeholder frame to the flow
    aFrameItems.AddChild(placeholderFrame);
  }
#ifdef DEBUG
  else {
    NS_ASSERTION(aNewFrame->GetParent() == aParentFrame,
                 "In-flow frame has wrong parent");
  }
#endif

  if (aInsertAfter) {
    frameItems->InsertFrame(nullptr, aInsertAfterFrame, aNewFrame);
  } else {
    frameItems->AddChild(aNewFrame);
  }
}

void
nsFrameConstructorState::ProcessFrameInsertions(nsAbsoluteItems& aFrameItems,
                                                ChildListID aChildListID)
{
#define NS_NONXUL_LIST_TEST (&aFrameItems == &mFloatedItems &&            \
                             aChildListID == nsIFrame::kFloatList)    ||  \
                            (&aFrameItems == &mAbsoluteItems &&           \
                             aChildListID == nsIFrame::kAbsoluteList) ||  \
                            (&aFrameItems == &mFixedItems &&              \
                             aChildListID == nsIFrame::kFixedList)
#ifdef MOZ_XUL
  NS_PRECONDITION(NS_NONXUL_LIST_TEST ||
                  (&aFrameItems == &mPopupItems &&
                   aChildListID == nsIFrame::kPopupList), 
                  "Unexpected aFrameItems/aChildListID combination");
#else
  NS_PRECONDITION(NS_NONXUL_LIST_TEST,
                  "Unexpected aFrameItems/aChildListID combination");
#endif

  if (aFrameItems.IsEmpty()) {
    return;
  }
  
  nsIFrame* containingBlock = aFrameItems.containingBlock;

  NS_ASSERTION(containingBlock,
               "Child list without containing block?");

  if (aChildListID == nsIFrame::kFixedList) {
    // Put this frame on the transformed-frame's abs-pos list instead, if
    // it has abs-pos children instead of fixed-pos children.
    aChildListID = containingBlock->GetAbsoluteListID();
  }

  // Insert the frames hanging out in aItems.  We can use SetInitialChildList()
  // if the containing block hasn't been reflowed yet (so NS_FRAME_FIRST_REFLOW
  // is set) and doesn't have any frames in the aChildListID child list yet.
  const nsFrameList& childList = containingBlock->GetChildList(aChildListID);
  DebugOnly<nsresult> rv = NS_OK;
  if (childList.IsEmpty() &&
      (containingBlock->GetStateBits() & NS_FRAME_FIRST_REFLOW)) {
    // If we're injecting absolutely positioned frames, inject them on the
    // absolute containing block
    if (aChildListID == containingBlock->GetAbsoluteListID()) {
      rv = containingBlock->GetAbsoluteContainingBlock()->
           SetInitialChildList(containingBlock, aChildListID, aFrameItems);
    } else {
      rv = containingBlock->SetInitialChildList(aChildListID, aFrameItems);
    }
  } else {
    // Note that whether the frame construction context is doing an append or
    // not is not helpful here, since it could be appending to some frame in
    // the middle of the document, which means we're not necessarily
    // appending to the children of the containing block.
    //
    // We need to make sure the 'append to the end of document' case is fast.
    // So first test the last child of the containing block
    nsIFrame* lastChild = childList.LastChild();

    // CompareTreePosition uses placeholder hierarchy for out of flow frames,
    // so this will make out-of-flows respect the ordering of placeholders,
    // which is great because it takes care of anonymous content.
    nsIFrame* firstNewFrame = aFrameItems.FirstChild();  

    // Cache the ancestor chain so that we can reuse it if needed.
    nsAutoTArray<nsIFrame*, 20> firstNewFrameAncestors;
    nsIFrame* notCommonAncestor = nullptr;
    if (lastChild) {
      notCommonAncestor = nsLayoutUtils::FillAncestors(firstNewFrame,
                                                       containingBlock,
                                                       &firstNewFrameAncestors);
    }

    if (!lastChild ||
        nsLayoutUtils::CompareTreePosition(lastChild, firstNewFrame,
                                           firstNewFrameAncestors,
                                           notCommonAncestor ?
                                             containingBlock : nullptr) < 0) {
      // no lastChild, or lastChild comes before the new children, so just append
      rv = mFrameManager->AppendFrames(containingBlock, aChildListID, aFrameItems);
    } else {
      // Try the other children. First collect them to an array so that a
      // reasonable fast binary search can be used to find the insertion point.
      nsAutoTArray<nsIFrame*, 128> children;
      for (nsIFrame* f = childList.FirstChild(); f != lastChild;
           f = f->GetNextSibling()) {
        children.AppendElement(f);
      }

      nsIFrame* insertionPoint = nullptr;
      int32_t imin = 0;
      int32_t max = children.Length();
      while (max > imin) {
        int32_t imid = imin + ((max - imin) / 2);
        nsIFrame* f = children[imid];
        int32_t compare =
          nsLayoutUtils::CompareTreePosition(f, firstNewFrame, firstNewFrameAncestors,
                                             notCommonAncestor ? containingBlock : nullptr);
        if (compare > 0) {
          // f is after the new frame.
          max = imid;
          insertionPoint = imid > 0 ? children[imid - 1] : nullptr;
        } else if (compare < 0) {
          // f is before the new frame.
          imin = imid + 1;
          insertionPoint = f;
        } else {
          // This is for the old behavior. Should be removed once it is
          // guaranteed that CompareTreePosition can't return 0!
          // See bug 928645.
          NS_WARNING("Something odd happening???");
          insertionPoint = nullptr;
          for (uint32_t i = 0; i < children.Length(); ++i) {
            nsIFrame* f = children[i];
            if (nsLayoutUtils::CompareTreePosition(f, firstNewFrame,
                                                   firstNewFrameAncestors,
                                                   notCommonAncestor ?
                                                     containingBlock : nullptr) > 0) {
              break;
            }
            insertionPoint = f;
          }
          break;
        }
      }
      rv = mFrameManager->InsertFrames(containingBlock, aChildListID,
                                       insertionPoint, aFrameItems);
    }
  }

  NS_POSTCONDITION(aFrameItems.IsEmpty(), "How did that happen?");

  // XXXbz And if NS_FAILED(rv), what?  I guess we need to clean up the list
  // and deal with all the placeholders... but what if the placeholders aren't
  // in the document yet?  Could that happen?
  NS_ASSERTION(NS_SUCCEEDED(rv), "Frames getting lost!");
}


nsFrameConstructorSaveState::nsFrameConstructorSaveState()
  : mItems(nullptr),
    mSavedItems(nullptr),
    mChildListID(kPrincipalList),
    mState(nullptr),
    mSavedFixedItems(nullptr),
    mSavedFixedPosIsAbsPos(false)
{
}

nsFrameConstructorSaveState::~nsFrameConstructorSaveState()
{
  // Restore the state
  if (mItems) {
    NS_ASSERTION(mState, "Can't have mItems set without having a state!");
    mState->ProcessFrameInsertions(*mItems, mChildListID);
    *mItems = mSavedItems;
#ifdef DEBUG
    // We've transferred the child list, so drop the pointer we held to it.
    // Note that this only matters for the assert in ~nsAbsoluteItems.
    mSavedItems.Clear();
#endif
    if (mItems == &mState->mAbsoluteItems) {
      mState->mFixedPosIsAbsPos = mSavedFixedPosIsAbsPos;
      if (mSavedFixedPosIsAbsPos) {
        // mAbsoluteItems was moved to mFixedItems, so move mFixedItems back
        // and repair the old mFixedItems now.
        mState->mAbsoluteItems = mState->mFixedItems;
        mState->mFixedItems = mSavedFixedItems;
#ifdef DEBUG
        mSavedFixedItems.Clear();
#endif
      }
    }
    NS_ASSERTION(!mItems->LastChild() || !mItems->LastChild()->GetNextSibling(),
                 "Something corrupted our list");
  }
}

static 
bool IsBorderCollapse(nsIFrame* aFrame)
{
  for (nsIFrame* frame = aFrame; frame; frame = frame->GetParent()) {
    if (nsGkAtoms::tableFrame == frame->GetType()) {
      return ((nsTableFrame*)frame)->IsBorderCollapse();
    }
  }
  NS_ASSERTION(false, "program error");
  return false;
}

/**
 * Moves aFrameList from aOldParent to aNewParent.  This updates the parent
 * pointer of the frames in the list, and reparents their views as needed.
 * nsFrame::SetParent sets the NS_FRAME_HAS_VIEW bit on aNewParent and its
 * ancestors as needed. Then it sets the list as the initial child list
 * on aNewParent, unless aNewParent either already has kids or has been
 * reflowed; in that case it appends the new frames.  Note that this
 * method differs from ReparentFrames in that it doesn't change the kids'
 * style contexts.
 */
// XXXbz Since this is only used for {ib} splits, could we just copy the view
// bits from aOldParent to aNewParent and then use the
// nsFrameList::ApplySetParent?  That would still leave us doing two passes
// over the list, of course; if we really wanted to we could factor out the
// relevant part of ReparentFrameViewList, I suppose...  Or just get rid of
// views, which would make most of this function go away.
static void
MoveChildrenTo(nsPresContext* aPresContext,
               nsIFrame* aOldParent,
               nsIFrame* aNewParent,
               nsFrameList& aFrameList)
{
  bool sameGrandParent = aOldParent->GetParent() == aNewParent->GetParent();

  if (aNewParent->HasView() || aOldParent->HasView() || !sameGrandParent) {
    // Move the frames into the new view
    nsContainerFrame::ReparentFrameViewList(aPresContext, aFrameList,
                                            aOldParent, aNewParent);
  }

  for (nsFrameList::Enumerator e(aFrameList); !e.AtEnd(); e.Next()) {
    e.get()->SetParent(aNewParent);
  }

  if (aNewParent->PrincipalChildList().IsEmpty() &&
      (aNewParent->GetStateBits() & NS_FRAME_FIRST_REFLOW)) {
    aNewParent->SetInitialChildList(kPrincipalList, aFrameList);
  } else {
    aNewParent->AppendFrames(kPrincipalList, aFrameList);
  }
}

//----------------------------------------------------------------------

nsCSSFrameConstructor::nsCSSFrameConstructor(nsIDocument *aDocument,
                                             nsIPresShell *aPresShell,
                                             nsStyleSet* aStyleSet)
  : nsFrameManager(aPresShell, aStyleSet)
  , mDocument(aDocument)
  , mRootElementFrame(nullptr)
  , mRootElementStyleFrame(nullptr)
  , mFixedContainingBlock(nullptr)
  , mDocElementContainingBlock(nullptr)
  , mGfxScrollFrame(nullptr)
  , mPageSequenceFrame(nullptr)
  , mCurrentDepth(0)
  , mUpdateCount(0)
  , mQuotesDirty(false)
  , mCountersDirty(false)
  , mIsDestroyingFrameTree(false)
  , mHasRootAbsPosContainingBlock(false)
{
#ifdef DEBUG
  static bool gFirstTime = true;
  if (gFirstTime) {
    gFirstTime = false;
    char* flags = PR_GetEnv("GECKO_FRAMECTOR_DEBUG_FLAGS");
    if (flags) {
      bool error = false;
      for (;;) {
        char* comma = PL_strchr(flags, ',');
        if (comma)
          *comma = '\0';

        bool found = false;
        FrameCtorDebugFlags* flag = gFlags;
        FrameCtorDebugFlags* limit = gFlags + NUM_DEBUG_FLAGS;
        while (flag < limit) {
          if (PL_strcasecmp(flag->name, flags) == 0) {
            *(flag->on) = true;
            printf("nsCSSFrameConstructor: setting %s debug flag on\n", flag->name);
            found = true;
            break;
          }
          ++flag;
        }

        if (! found)
          error = true;

        if (! comma)
          break;

        *comma = ',';
        flags = comma + 1;
      }

      if (error) {
        printf("Here are the available GECKO_FRAMECTOR_DEBUG_FLAGS:\n");
        FrameCtorDebugFlags* flag = gFlags;
        FrameCtorDebugFlags* limit = gFlags + NUM_DEBUG_FLAGS;
        while (flag < limit) {
          printf("  %s\n", flag->name);
          ++flag;
        }
        printf("Note: GECKO_FRAMECTOR_DEBUG_FLAGS is a comma separated list of flag\n");
        printf("names (no whitespace)\n");
      }
    }
  }
#endif
}

void
nsCSSFrameConstructor::NotifyDestroyingFrame(nsIFrame* aFrame)
{
  NS_PRECONDITION(mUpdateCount != 0,
                  "Should be in an update while destroying frames");

  if (aFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT) {
    if (mQuoteList.DestroyNodesFor(aFrame))
      QuotesDirty();
  }

  if (mCounterManager.DestroyNodesFor(aFrame)) {
    // Technically we don't need to update anything if we destroyed only
    // USE nodes.  However, this is unlikely to happen in the real world
    // since USE nodes generally go along with INCREMENT nodes.
    CountersDirty();
  }

  RestyleManager()->NotifyDestroyingFrame(aFrame);

  nsFrameManager::NotifyDestroyingFrame(aFrame);
}

struct nsGenConInitializer {
  nsAutoPtr<nsGenConNode> mNode;
  nsGenConList*           mList;
  void (nsCSSFrameConstructor::*mDirtyAll)();
  
  nsGenConInitializer(nsGenConNode* aNode, nsGenConList* aList,
                      void (nsCSSFrameConstructor::*aDirtyAll)())
    : mNode(aNode), mList(aList), mDirtyAll(aDirtyAll) {}
};

static void
DestroyGenConInitializer(void*    aFrame,
                         nsIAtom* aPropertyName,
                         void*    aPropertyValue,
                         void*    aDtorData)
{
  delete static_cast<nsGenConInitializer*>(aPropertyValue);
}

already_AddRefed<nsIContent>
nsCSSFrameConstructor::CreateGenConTextNode(nsFrameConstructorState& aState,
                                            const nsString& aString,
                                            nsCOMPtr<nsIDOMCharacterData>* aText,
                                            nsGenConInitializer* aInitializer)
{
  nsRefPtr<nsTextNode> content = new nsTextNode(mDocument->NodeInfoManager());
  content->SetText(aString, false);
  if (aText) {
    *aText = content;
  }
  if (aInitializer) {
    content->SetProperty(nsGkAtoms::genConInitializerProperty, aInitializer,
                         DestroyGenConInitializer);
    aState.mGeneratedTextNodesWithInitializer.AppendObject(content);
  }
  return content.forget();
}

already_AddRefed<nsIContent>
nsCSSFrameConstructor::CreateGeneratedContent(nsFrameConstructorState& aState,
                                              nsIContent*     aParentContent,
                                              nsStyleContext* aStyleContext,
                                              uint32_t        aContentIndex)
{
  // Get the content value
  const nsStyleContentData &data =
    aStyleContext->StyleContent()->ContentAt(aContentIndex);
  nsStyleContentType type = data.mType;

  if (eStyleContentType_Image == type) {
    if (!data.mContent.mImage) {
      // CSS had something specified that couldn't be converted to an
      // image object
      return nullptr;
    }
    
    // Create an image content object and pass it the image request.
    // XXX Check if it's an image type we can handle...

    nsCOMPtr<nsINodeInfo> nodeInfo;
    nodeInfo = mDocument->NodeInfoManager()->
      GetNodeInfo(nsGkAtoms::mozgeneratedcontentimage, nullptr,
                  kNameSpaceID_XHTML, nsIDOMNode::ELEMENT_NODE);

    nsCOMPtr<nsIContent> content;
    NS_NewGenConImageContent(getter_AddRefs(content), nodeInfo.forget(),
                             data.mContent.mImage);
    return content.forget();
  }

  switch (type) {
  case eStyleContentType_String:
    return CreateGenConTextNode(aState,
                                nsDependentString(data.mContent.mString),
                                nullptr, nullptr);

  case eStyleContentType_Attr:
    {
      nsCOMPtr<nsIAtom> attrName;
      int32_t attrNameSpace = kNameSpaceID_None;
      nsAutoString contentString(data.mContent.mString);
      
      int32_t barIndex = contentString.FindChar('|'); // CSS namespace delimiter
      if (-1 != barIndex) {
        nsAutoString  nameSpaceVal;
        contentString.Left(nameSpaceVal, barIndex);
        nsresult error;
        attrNameSpace = nameSpaceVal.ToInteger(&error);
        contentString.Cut(0, barIndex + 1);
        if (contentString.Length()) {
          if (mDocument->IsHTML() && aParentContent->IsHTML()) {
            ToLowerCase(contentString);
          }
          attrName = do_GetAtom(contentString);
        }
      }
      else {
        if (mDocument->IsHTML() && aParentContent->IsHTML()) {
          ToLowerCase(contentString);
        }
        attrName = do_GetAtom(contentString);
      }

      if (!attrName) {
        return nullptr;
      }

      nsCOMPtr<nsIContent> content;
      NS_NewAttributeContent(mDocument->NodeInfoManager(),
                             attrNameSpace, attrName, getter_AddRefs(content));
      return content.forget();
    }

  case eStyleContentType_Counter:
  case eStyleContentType_Counters:
    {
      nsCSSValue::Array* counters = data.mContent.mCounters;
      nsCounterList* counterList = mCounterManager.CounterListFor(
          nsDependentString(counters->Item(0).GetStringBufferValue()));
      if (!counterList)
        return nullptr;

      nsCounterUseNode* node =
        new nsCounterUseNode(counters, aContentIndex,
                             type == eStyleContentType_Counters);

      nsGenConInitializer* initializer =
        new nsGenConInitializer(node, counterList,
                                &nsCSSFrameConstructor::CountersDirty);
      return CreateGenConTextNode(aState, EmptyString(), &node->mText,
                                  initializer);
    }

  case eStyleContentType_Image:
    NS_NOTREACHED("handled by if above");
    return nullptr;

  case eStyleContentType_OpenQuote:
  case eStyleContentType_CloseQuote:
  case eStyleContentType_NoOpenQuote:
  case eStyleContentType_NoCloseQuote:
    {
      nsQuoteNode* node =
        new nsQuoteNode(type, aContentIndex);

      nsGenConInitializer* initializer =
        new nsGenConInitializer(node, &mQuoteList,
                                &nsCSSFrameConstructor::QuotesDirty);
      return CreateGenConTextNode(aState, EmptyString(), &node->mText,
                                  initializer);
    }
  
  case eStyleContentType_AltContent:
    {
      // Use the "alt" attribute; if that fails and the node is an HTML
      // <input>, try the value attribute and then fall back to some default
      // localized text we have.
      // XXX what if the 'alt' attribute is added later, how will we
      // detect that and do the right thing here?
      if (aParentContent->HasAttr(kNameSpaceID_None, nsGkAtoms::alt)) {
        nsCOMPtr<nsIContent> content;
        NS_NewAttributeContent(mDocument->NodeInfoManager(),
                               kNameSpaceID_None, nsGkAtoms::alt, getter_AddRefs(content));
        return content.forget();
      }

      if (aParentContent->IsHTML() &&
          aParentContent->NodeInfo()->Equals(nsGkAtoms::input)) {
        if (aParentContent->HasAttr(kNameSpaceID_None, nsGkAtoms::value)) {
          nsCOMPtr<nsIContent> content;
          NS_NewAttributeContent(mDocument->NodeInfoManager(),
                                 kNameSpaceID_None, nsGkAtoms::value, getter_AddRefs(content));
          return content.forget();
        }

        nsXPIDLString temp;
        nsContentUtils::GetLocalizedString(nsContentUtils::eFORMS_PROPERTIES,
                                           "Submit", temp);
        return CreateGenConTextNode(aState, temp, nullptr, nullptr);
      }

      break;
    }

  case eStyleContentType_Uninitialized:
    NS_NOTREACHED("uninitialized content type");
    return nullptr;
  } // switch

  return nullptr;
}

/*
 * aParentFrame - the frame that should be the parent of the generated
 *   content.  This is the frame for the corresponding content node,
 *   which must not be a leaf frame.
 * 
 * Any items created are added to aItems.
 * 
 * We create an XML element (tag _moz_generated_content_before or
 * _moz_generated_content_after) representing the pseudoelement. We
 * create a DOM node for each 'content' item and make those nodes the
 * children of the XML element. Then we create a frame subtree for
 * the XML element as if it were a regular child of
 * aParentFrame/aParentContent, giving the XML element the ::before or
 * ::after style.
 */
void
nsCSSFrameConstructor::CreateGeneratedContentItem(nsFrameConstructorState& aState,
                                                  nsIFrame*        aParentFrame,
                                                  nsIContent*      aParentContent,
                                                  nsStyleContext*  aStyleContext,
                                                  nsCSSPseudoElements::Type aPseudoElement,
                                                  FrameConstructionItemList& aItems)
{
  // XXXbz is this ever true?
  if (!aParentContent->IsElement()) {
    NS_ERROR("Bogus generated content parent");
    return;
  }

  nsStyleSet *styleSet = mPresShell->StyleSet();

  // Probe for the existence of the pseudo-element
  nsRefPtr<nsStyleContext> pseudoStyleContext;
  pseudoStyleContext =
    styleSet->ProbePseudoElementStyle(aParentContent->AsElement(),
                                      aPseudoElement,
                                      aStyleContext,
                                      aState.mTreeMatchContext);
  if (!pseudoStyleContext)
    return;
  // |ProbePseudoStyleFor| checked the 'display' property and the
  // |ContentCount()| of the 'content' property for us.
  nsCOMPtr<nsINodeInfo> nodeInfo;
  nsIAtom* elemName = aPseudoElement == nsCSSPseudoElements::ePseudo_before ?
    nsGkAtoms::mozgeneratedcontentbefore : nsGkAtoms::mozgeneratedcontentafter;
  nodeInfo = mDocument->NodeInfoManager()->GetNodeInfo(elemName, nullptr,
                                                       kNameSpaceID_None,
                                                       nsIDOMNode::ELEMENT_NODE);
  nsCOMPtr<nsIContent> container;
  nsresult rv = NS_NewXMLElement(getter_AddRefs(container), nodeInfo.forget());
  if (NS_FAILED(rv))
    return;
  container->SetIsNativeAnonymousRoot();

  rv = container->BindToTree(mDocument, aParentContent, aParentContent, true);
  if (NS_FAILED(rv)) {
    container->UnbindFromTree();
    return;
  }

  uint32_t contentCount = pseudoStyleContext->StyleContent()->ContentCount();
  for (uint32_t contentIndex = 0; contentIndex < contentCount; contentIndex++) {
    nsCOMPtr<nsIContent> content =
      CreateGeneratedContent(aState, aParentContent, pseudoStyleContext,
                             contentIndex);
    if (content) {
      container->AppendChildTo(content, false);
    }
  }

  AddFrameConstructionItemsInternal(aState, container, aParentFrame, elemName,
                                    kNameSpaceID_None, true,
                                    pseudoStyleContext,
                                    ITEM_IS_GENERATED_CONTENT, nullptr,
                                    aItems);
}
    
/****************************************************
 **  BEGIN TABLE SECTION
 ****************************************************/

// The term pseudo frame is being used instead of anonymous frame, since anonymous
// frame has been used elsewhere to refer to frames that have generated content

// Return whether the given frame is a table pseudo-frame.  Note that
// cell-content and table-outer frames have pseudo-types, but are always
// created, even for non-anonymous cells and tables respectively.  So for those
// we have to examine the cell or table frame to see whether it's a pseudo
// frame.  In particular, a lone table caption will have an outer table as its
// parent, but will also trigger construction of an empty inner table, which
// will be the one we can examine to see whether the outer was a pseudo-frame.
static bool
IsTablePseudo(nsIFrame* aFrame)
{
  nsIAtom* pseudoType = aFrame->StyleContext()->GetPseudo();
  return pseudoType &&
    (pseudoType == nsCSSAnonBoxes::table ||
     pseudoType == nsCSSAnonBoxes::inlineTable ||
     pseudoType == nsCSSAnonBoxes::tableColGroup ||
     pseudoType == nsCSSAnonBoxes::tableRowGroup ||
     pseudoType == nsCSSAnonBoxes::tableRow ||
     pseudoType == nsCSSAnonBoxes::tableCell ||
     (pseudoType == nsCSSAnonBoxes::cellContent &&
      aFrame->GetParent()->StyleContext()->GetPseudo() ==
        nsCSSAnonBoxes::tableCell) ||
     (pseudoType == nsCSSAnonBoxes::tableOuter &&
      (aFrame->GetFirstPrincipalChild()->StyleContext()->GetPseudo() ==
         nsCSSAnonBoxes::table ||
       aFrame->GetFirstPrincipalChild()->StyleContext()->GetPseudo() ==
         nsCSSAnonBoxes::inlineTable)));
}

/* static */
nsCSSFrameConstructor::ParentType
nsCSSFrameConstructor::GetParentType(nsIAtom* aFrameType)
{
  if (aFrameType == nsGkAtoms::tableFrame) {
    return eTypeTable;
  }
  if (aFrameType == nsGkAtoms::tableRowGroupFrame) {
    return eTypeRowGroup;
  }
  if (aFrameType == nsGkAtoms::tableRowFrame) {
    return eTypeRow;
  }
  if (aFrameType == nsGkAtoms::tableColGroupFrame) {
    return eTypeColGroup;
  }

  return eTypeBlock;
}
           
static nsIFrame*
AdjustCaptionParentFrame(nsIFrame* aParentFrame) 
{
  if (nsGkAtoms::tableFrame == aParentFrame->GetType()) {
    return aParentFrame->GetParent();;
  }
  return aParentFrame;
}
 
/**
 * If the parent frame is a |tableFrame| and the child is a
 * |captionFrame|, then we want to insert the frames beneath the
 * |tableFrame|'s parent frame. Returns |true| if the parent frame
 * needed to be fixed up.
 */
static bool
GetCaptionAdjustedParent(nsIFrame*        aParentFrame,
                         const nsIFrame*  aChildFrame,
                         nsIFrame**       aAdjParentFrame)
{
  *aAdjParentFrame = aParentFrame;
  bool haveCaption = false;

  if (nsGkAtoms::tableCaptionFrame == aChildFrame->GetType()) {
    haveCaption = true;
    *aAdjParentFrame = AdjustCaptionParentFrame(aParentFrame);
  }
  return haveCaption;
}

void
nsCSSFrameConstructor::AdjustParentFrame(nsIFrame* &                  aParentFrame,
                                         const FrameConstructionData* aFCData,
                                         nsStyleContext*              aStyleContext)
{
  NS_PRECONDITION(aStyleContext, "Must have child's style context");
  NS_PRECONDITION(aFCData, "Must have frame construction data");

  bool tablePart = ((aFCData->mBits & FCDATA_IS_TABLE_PART) != 0);

  if (tablePart && aStyleContext->StyleDisplay()->mDisplay ==
      NS_STYLE_DISPLAY_TABLE_CAPTION) {
    aParentFrame = AdjustCaptionParentFrame(aParentFrame);
  }
}

// Pull all the captions present in aItems out  into aCaptions
static void
PullOutCaptionFrames(nsFrameItems& aItems, nsFrameItems& aCaptions)
{
  nsIFrame *child = aItems.FirstChild();
  while (child) {
    nsIFrame *nextSibling = child->GetNextSibling();
    if (nsGkAtoms::tableCaptionFrame == child->GetType()) {
      aItems.RemoveFrame(child);
      aCaptions.AddChild(child);
    }
    child = nextSibling;
  }
}


// Construct the outer, inner table frames and the children frames for the table. 
// XXX Page break frames for pseudo table frames are not constructed to avoid the risk
// associated with revising the pseudo frame mechanism. The long term solution
// of having frames handle page-break-before/after will solve the problem. 
nsIFrame*
nsCSSFrameConstructor::ConstructTable(nsFrameConstructorState& aState,
                                      FrameConstructionItem&   aItem,
                                      nsIFrame*                aParentFrame,
                                      const nsStyleDisplay*    aDisplay,
                                      nsFrameItems&            aFrameItems)
{
  NS_PRECONDITION(aDisplay->mDisplay == NS_STYLE_DISPLAY_TABLE ||
                  aDisplay->mDisplay == NS_STYLE_DISPLAY_INLINE_TABLE,
                  "Unexpected call");

  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;
  const uint32_t nameSpaceID = aItem.mNameSpaceID;

  // create the pseudo SC for the outer table as a child of the inner SC
  nsRefPtr<nsStyleContext> outerStyleContext;
  outerStyleContext = mPresShell->StyleSet()->
    ResolveAnonymousBoxStyle(nsCSSAnonBoxes::tableOuter, styleContext);

  // Create the outer table frame which holds the caption and inner table frame
  nsIFrame* newFrame;
  if (kNameSpaceID_MathML == nameSpaceID)
    newFrame = NS_NewMathMLmtableOuterFrame(mPresShell, outerStyleContext);
  else
    newFrame = NS_NewTableOuterFrame(mPresShell, outerStyleContext);

  nsIFrame* geometricParent =
    aState.GetGeometricParent(outerStyleContext->StyleDisplay(),
                              aParentFrame);

  // Init the table outer frame
  InitAndRestoreFrame(aState, content, geometricParent, newFrame);  

  // Create the inner table frame
  nsIFrame* innerFrame;
  if (kNameSpaceID_MathML == nameSpaceID)
    innerFrame = NS_NewMathMLmtableFrame(mPresShell, styleContext);
  else
    innerFrame = NS_NewTableFrame(mPresShell, styleContext);

  InitAndRestoreFrame(aState, content, newFrame, innerFrame);

  // Put the newly created frames into the right child list
  SetInitialSingleChild(newFrame, innerFrame);

  aState.AddChild(newFrame, aFrameItems, content, styleContext, aParentFrame);

  if (!mRootElementFrame) {
    // The frame we're constructing will be the root element frame.
    // Set mRootElementFrame before processing children.
    mRootElementFrame = newFrame;
  }

  nsFrameItems childItems;

  // Process children
  nsFrameConstructorSaveState absoluteSaveState;
  const nsStyleDisplay* display = outerStyleContext->StyleDisplay();

  // Mark the table frame as an absolute container if needed
  newFrame->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
  if ((display->IsRelativelyPositionedStyle() ||
       display->IsAbsolutelyPositionedStyle() ||
       (display->HasTransformStyle() &&
        aParentFrame->IsFrameOfType(nsIFrame::eSupportsCSSTransforms))) &&
      !aParentFrame->IsSVGText()) {
    aState.PushAbsoluteContainingBlock(newFrame, newFrame, absoluteSaveState);
  }
  NS_ASSERTION(aItem.mAnonChildren.IsEmpty(),
               "nsIAnonymousContentCreator::CreateAnonymousContent "
               "implementations for table frames are not currently expected "
               "to output a list where the items have their own children");
  if (aItem.mFCData->mBits & FCDATA_USE_CHILD_ITEMS) {
    ConstructFramesFromItemList(aState, aItem.mChildItems,
                                innerFrame, childItems);
  } else {
    ProcessChildren(aState, content, styleContext, innerFrame,
                    true, childItems, false, aItem.mPendingBinding);
  }

  nsFrameItems captionItems;
  PullOutCaptionFrames(childItems, captionItems);

  // Set the inner table frame's initial primary list 
  innerFrame->SetInitialChildList(kPrincipalList, childItems);

  // Set the outer table frame's secondary childlist lists
  if (captionItems.NotEmpty()) {
    newFrame->SetInitialChildList(nsIFrame::kCaptionList, captionItems);
  }

  return newFrame;
}

nsIFrame*
nsCSSFrameConstructor::ConstructTableRow(nsFrameConstructorState& aState,
                                         FrameConstructionItem&   aItem,
                                         nsIFrame*                aParentFrame,
                                         const nsStyleDisplay*    aDisplay,
                                         nsFrameItems&            aFrameItems)
{
  NS_PRECONDITION(aDisplay->mDisplay == NS_STYLE_DISPLAY_TABLE_ROW,
                  "Unexpected call");
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;
  const uint32_t nameSpaceID = aItem.mNameSpaceID;

  nsIFrame* newFrame;
  if (kNameSpaceID_MathML == nameSpaceID)
    newFrame = NS_NewMathMLmtrFrame(mPresShell, styleContext);
  else
    newFrame = NS_NewTableRowFrame(mPresShell, styleContext);

  InitAndRestoreFrame(aState, content, aParentFrame, newFrame);

  nsFrameItems childItems;
  NS_ASSERTION(aItem.mAnonChildren.IsEmpty(),
               "nsIAnonymousContentCreator::CreateAnonymousContent "
               "implementations for table frames are not currently expected "
               "to output a list where the items have their own children");
  if (aItem.mFCData->mBits & FCDATA_USE_CHILD_ITEMS) {
    ConstructFramesFromItemList(aState, aItem.mChildItems, newFrame,
                                childItems);
  } else {
    ProcessChildren(aState, content, styleContext, newFrame,
                    true, childItems, false, aItem.mPendingBinding);
  }

  newFrame->SetInitialChildList(kPrincipalList, childItems);
  aFrameItems.AddChild(newFrame);
  return newFrame;
}

nsIFrame*
nsCSSFrameConstructor::ConstructTableCol(nsFrameConstructorState& aState,
                                         FrameConstructionItem&   aItem,
                                         nsIFrame*                aParentFrame,
                                         const nsStyleDisplay*    aStyleDisplay,
                                         nsFrameItems&            aFrameItems)
{
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;

  nsTableColFrame* colFrame = NS_NewTableColFrame(mPresShell, styleContext);
  InitAndRestoreFrame(aState, content, aParentFrame, colFrame);

  NS_ASSERTION(colFrame->StyleContext() == styleContext,
               "Unexpected style context");

  aFrameItems.AddChild(colFrame);

  // construct additional col frames if the col frame has a span > 1
  int32_t span = colFrame->GetSpan();
  for (int32_t spanX = 1; spanX < span; spanX++) {
    nsTableColFrame* newCol = NS_NewTableColFrame(mPresShell, styleContext);
    InitAndRestoreFrame(aState, content, aParentFrame, newCol, false);
    aFrameItems.LastChild()->SetNextContinuation(newCol);
    newCol->SetPrevContinuation(aFrameItems.LastChild());
    aFrameItems.AddChild(newCol);
    newCol->SetColType(eColAnonymousCol);
  }

  return colFrame;
}

nsIFrame*
nsCSSFrameConstructor::ConstructTableCell(nsFrameConstructorState& aState,
                                          FrameConstructionItem&   aItem,
                                          nsIFrame*                aParentFrame,
                                          const nsStyleDisplay*    aDisplay,
                                          nsFrameItems&            aFrameItems)
{
  NS_PRECONDITION(aDisplay->mDisplay == NS_STYLE_DISPLAY_TABLE_CELL,
                  "Unexpected call");

  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;
  const uint32_t nameSpaceID = aItem.mNameSpaceID;

  bool borderCollapse = IsBorderCollapse(aParentFrame);
  nsIFrame* newFrame;
  // <mtable> is border separate in mathml.css and the MathML code doesn't implement
  // border collapse. For those users who style <mtable> with border collapse,
  // give them the default non-MathML table frames that understand border collapse.
  // This won't break us because MathML table frames are all subclasses of the default
  // table code, and so we can freely mix <mtable> with <mtr> or <tr>, <mtd> or <td>.
  // What will happen is just that non-MathML frames won't understand MathML attributes
  // and will therefore miss the special handling that the MathML code does.
  if (kNameSpaceID_MathML == nameSpaceID && !borderCollapse)
    newFrame = NS_NewMathMLmtdFrame(mPresShell, styleContext);
  else
    // Warning: If you change this and add a wrapper frame around table cell
    // frames, make sure Bug 368554 doesn't regress!
    // See IsInAutoWidthTableCellForQuirk() in nsImageFrame.cpp.    
    newFrame = NS_NewTableCellFrame(mPresShell, styleContext, borderCollapse);

  // Initialize the table cell frame
  InitAndRestoreFrame(aState, content, aParentFrame, newFrame);
  
  // Resolve pseudo style and initialize the body cell frame
  nsRefPtr<nsStyleContext> innerPseudoStyle;
  innerPseudoStyle = mPresShell->StyleSet()->
    ResolveAnonymousBoxStyle(nsCSSAnonBoxes::cellContent, styleContext);

  // Create a block frame that will format the cell's content
  bool isBlock;
  nsIFrame* cellInnerFrame;
  if (kNameSpaceID_MathML == nameSpaceID) {
    cellInnerFrame = NS_NewMathMLmtdInnerFrame(mPresShell, innerPseudoStyle);
    isBlock = false;
  } else {
    cellInnerFrame = NS_NewBlockFormattingContext(mPresShell, innerPseudoStyle);
    isBlock = true;
  }

  InitAndRestoreFrame(aState, content, newFrame, cellInnerFrame);

  nsFrameItems childItems;
  NS_ASSERTION(aItem.mAnonChildren.IsEmpty(),
               "nsIAnonymousContentCreator::CreateAnonymousContent "
               "implementations for table frames are not currently expected "
               "to output a list where the items have their own children");
  if (aItem.mFCData->mBits & FCDATA_USE_CHILD_ITEMS) {
    // Need to push ourselves as a float containing block.
    // XXXbz it might be nice to work on getting the parent
    // FrameConstructionItem down into ProcessChildren and just making use of
    // the push there, but that's a bit of work.
    nsFrameConstructorSaveState floatSaveState;
    if (!isBlock) { /* MathML case */
      aState.PushFloatContainingBlock(nullptr, floatSaveState);
    } else {
      aState.PushFloatContainingBlock(cellInnerFrame, floatSaveState);
    }

    ConstructFramesFromItemList(aState, aItem.mChildItems, cellInnerFrame,
                                childItems);
  } else {
    // Process the child content
    ProcessChildren(aState, content, styleContext, cellInnerFrame,
                    true, childItems, isBlock, aItem.mPendingBinding);
  }
  
  cellInnerFrame->SetInitialChildList(kPrincipalList, childItems);
  SetInitialSingleChild(newFrame, cellInnerFrame);
  aFrameItems.AddChild(newFrame);
  return newFrame;
}

static inline bool 
NeedFrameFor(const nsFrameConstructorState& aState,
             nsIFrame*   aParentFrame,
             nsIContent* aChildContent) 
{
  // XXX the GetContent() != aChildContent check is needed due to bug 135040.
  // Remove it once that's fixed.
  NS_PRECONDITION(!aChildContent->GetPrimaryFrame() ||
                  aState.mCreatingExtraFrames ||
                  aChildContent->GetPrimaryFrame()->GetContent() != aChildContent,
                  "Why did we get called?");

  // don't create a whitespace frame if aParentFrame doesn't want it.
  // always create frames for children in generated content. counter(),
  // quotes, and attr() content can easily change dynamically and we don't
  // want to be reconstructing frames. It's not even clear that these
  // should be considered ignorable just because they evaluate to
  // whitespace.

  // We could handle all this in CreateNeededTablePseudos or some other place
  // after we build our frame construction items, but that would involve
  // creating frame construction items for whitespace kids of
  // eExcludesIgnorableWhitespace frames, where we know we'll be dropping them
  // all anyway, and involve an extra walk down the frame construction item
  // list.
  if (!aParentFrame->IsFrameOfType(nsIFrame::eExcludesIgnorableWhitespace) ||
      aParentFrame->IsGeneratedContentFrame() ||
      !aChildContent->IsNodeOfType(nsINode::eTEXT)) {
    return true;
  }

  aChildContent->SetFlags(NS_CREATE_FRAME_IF_NON_WHITESPACE |
                          NS_REFRAME_IF_WHITESPACE);
  return !aChildContent->TextIsOnlyWhitespace();
}

/***********************************************
 * END TABLE SECTION
 ***********************************************/

static bool CheckOverflow(nsPresContext* aPresContext,
                            const nsStyleDisplay* aDisplay)
{
  if (aDisplay->mOverflowX == NS_STYLE_OVERFLOW_VISIBLE)
    return false;

  if (aDisplay->mOverflowX == NS_STYLE_OVERFLOW_CLIP)
    aPresContext->SetViewportOverflowOverride(NS_STYLE_OVERFLOW_HIDDEN,
                                              NS_STYLE_OVERFLOW_HIDDEN);
  else
    aPresContext->SetViewportOverflowOverride(aDisplay->mOverflowX,
                                              aDisplay->mOverflowY);
  return true;
}

/**
 * This checks the root element and the HTML BODY, if any, for an "overflow" property
 * that should be applied to the viewport. If one is found then we return the
 * element that we took the overflow from (which should then be treated as
 * "overflow:visible"), and we store the overflow style in the prescontext.
 * @return if scroll was propagated from some content node, the content node it
 *         was propagated from.
 */
nsIContent*
nsCSSFrameConstructor::PropagateScrollToViewport()
{
  // Set default
  nsPresContext* presContext = mPresShell->GetPresContext();
  presContext->SetViewportOverflowOverride(NS_STYLE_OVERFLOW_AUTO,
                                           NS_STYLE_OVERFLOW_AUTO);

  // We never mess with the viewport scroll state
  // when printing or in print preview
  if (presContext->IsPaginated()) {
    return nullptr;
  }

  Element* docElement = mDocument->GetRootElement();

  // Check the style on the document root element
  nsStyleSet *styleSet = mPresShell->StyleSet();
  nsRefPtr<nsStyleContext> rootStyle;
  rootStyle = styleSet->ResolveStyleFor(docElement, nullptr);
  if (CheckOverflow(presContext, rootStyle->StyleDisplay())) {
    // tell caller we stole the overflow style from the root element
    return docElement;
  }
  
  // Don't look in the BODY for non-HTML documents or HTML documents
  // with non-HTML roots
  // XXX this should be earlier; we shouldn't even look at the document root
  // for non-HTML documents. Fix this once we support explicit CSS styling
  // of the viewport
  // XXX what about XHTML?
  nsCOMPtr<nsIDOMHTMLDocument> htmlDoc(do_QueryInterface(mDocument));
  if (!htmlDoc || !docElement->IsHTML()) {
    return nullptr;
  }
  
  nsCOMPtr<nsIDOMHTMLElement> body;
  htmlDoc->GetBody(getter_AddRefs(body));
  nsCOMPtr<nsIContent> bodyElement = do_QueryInterface(body);
  
  if (!bodyElement ||
      !bodyElement->NodeInfo()->Equals(nsGkAtoms::body)) {
    // The body is not a <body> tag, it's a <frameset>.
    return nullptr;
  }

  nsRefPtr<nsStyleContext> bodyStyle;
  bodyStyle = styleSet->ResolveStyleFor(bodyElement->AsElement(), rootStyle);

  if (CheckOverflow(presContext, bodyStyle->StyleDisplay())) {
    // tell caller we stole the overflow style from the body element
    return bodyElement;
  }

  return nullptr;
}

nsIFrame*
nsCSSFrameConstructor::ConstructDocElementFrame(Element*                 aDocElement,
                                                nsILayoutHistoryState*   aFrameState)
{
  NS_PRECONDITION(mFixedContainingBlock,
                  "No viewport?  Someone forgot to call ConstructRootFrame!");
  NS_PRECONDITION(mFixedContainingBlock == GetRootFrame(),
                  "Unexpected mFixedContainingBlock");
  NS_PRECONDITION(!mDocElementContainingBlock,
                  "Shouldn't have a doc element containing block here");

  // Make sure to call PropagateScrollToViewport before
  // SetUpDocElementContainingBlock, since it sets up our scrollbar state
  // properly.
#ifdef DEBUG
  nsIContent* propagatedScrollFrom =
#endif
    PropagateScrollToViewport();

  SetUpDocElementContainingBlock(aDocElement);

  NS_ASSERTION(mDocElementContainingBlock, "Should have parent by now");

  nsFrameConstructorState state(mPresShell, mFixedContainingBlock, nullptr,
                                nullptr, aFrameState);
  // Initialize the ancestor filter with null for now; we'll push
  // aDocElement once we finish resolving style for it.
  state.mTreeMatchContext.InitAncestors(nullptr);

  // XXXbz why, exactly?
  if (!mTempFrameTreeState)
    state.mPresShell->CaptureHistoryState(getter_AddRefs(mTempFrameTreeState));

  // Make sure that we'll handle restyles for this document element in
  // the future.  We need this, because the document element might
  // have stale restyle bits from a previous frame constructor for
  // this document.  Unlike in AddFrameConstructionItems, it's safe to
  // unset all element restyle flags, since we don't have any
  // siblings.
  aDocElement->UnsetFlags(ELEMENT_ALL_RESTYLE_FLAGS);

  // --------- CREATE AREA OR BOX FRAME -------
  nsRefPtr<nsStyleContext> styleContext;
  styleContext = mPresShell->StyleSet()->ResolveStyleFor(aDocElement,
                                                         nullptr);

  const nsStyleDisplay* display = styleContext->StyleDisplay();

  // Ensure that our XBL bindings are installed.
  if (display->mBinding) {
    // Get the XBL loader.
    nsresult rv;
    bool resolveStyle;
    
    nsXBLService* xblService = nsXBLService::GetInstance();
    if (!xblService) {
      return nullptr;
    }

    nsRefPtr<nsXBLBinding> binding;
    rv = xblService->LoadBindings(aDocElement, display->mBinding->GetURI(),
                                  display->mBinding->mOriginPrincipal,
                                  getter_AddRefs(binding), &resolveStyle);
    if (NS_FAILED(rv) && rv != NS_ERROR_XBL_BLOCKED)
      return nullptr; // Binding will load asynchronously.

    if (binding) {
      // For backwards compat, keep firing the root's constructor
      // after all of its kids' constructors.  So tell the binding
      // manager about it right now.
      mDocument->BindingManager()->AddToAttachedQueue(binding);
    }

    if (resolveStyle) {
      styleContext = mPresShell->StyleSet()->ResolveStyleFor(aDocElement,
                                                             nullptr);
      display = styleContext->StyleDisplay();
    }
  }

  // --------- IF SCROLLABLE WRAP IN SCROLLFRAME --------

#ifdef DEBUG
  NS_ASSERTION(!display->IsScrollableOverflow() || 
               state.mPresContext->IsPaginated() ||
               propagatedScrollFrom == aDocElement,
               "Scrollbars should have been propagated to the viewport");
#endif

  if (MOZ_UNLIKELY(display->mDisplay == NS_STYLE_DISPLAY_NONE)) {
    SetUndisplayedContent(aDocElement, styleContext);
    return nullptr;
  }

  TreeMatchContext::AutoAncestorPusher
    ancestorPusher(true, state.mTreeMatchContext, aDocElement);

  // Make sure to start any background image loads for the root element now.
  styleContext->StartBackgroundImageLoads();

  nsFrameConstructorSaveState absoluteSaveState;
  if (mHasRootAbsPosContainingBlock) {
    // Push the absolute containing block now so we can absolutely position
    // the root element
    mDocElementContainingBlock->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
    state.PushAbsoluteContainingBlock(mDocElementContainingBlock,
                                      mDocElementContainingBlock,
                                      absoluteSaveState);
  }

  // The rules from CSS 2.1, section 9.2.4, have already been applied
  // by the style system, so we can assume that display->mDisplay is
  // either NONE, BLOCK, or TABLE.

  // contentFrame is the primary frame for the root element. newFrame
  // is the frame that will be the child of the initial containing block.
  // These are usually the same frame but they can be different, in
  // particular if the root frame is positioned, in which case
  // contentFrame is the out-of-flow frame and newFrame is the
  // placeholder.
  nsIFrame* contentFrame;
  nsIFrame* newFrame;
  bool processChildren = false;

  // Check whether we need to build a XUL box or SVG root frame
#ifdef MOZ_XUL
  if (aDocElement->IsXUL()) {
    contentFrame = NS_NewDocElementBoxFrame(mPresShell, styleContext);
    InitAndRestoreFrame(state, aDocElement, mDocElementContainingBlock,
                        contentFrame);
    newFrame = contentFrame;
    processChildren = true;
  }
  else
#endif
  if (aDocElement->IsSVG()) {
    if (aDocElement->Tag() == nsGkAtoms::svg) {
      // We're going to call the right function ourselves, so no need to give a
      // function to this FrameConstructionData.

      // XXXbz on the other hand, if we converted this whole function to
      // FrameConstructionData/Item, then we'd need the right function
      // here... but would probably be able to get away with less code in this
      // function in general.
      // Use a null PendingBinding, since our binding is not in fact pending.
      static const FrameConstructionData rootSVGData = FCDATA_DECL(0, nullptr);
      nsRefPtr<nsStyleContext> extraRef(styleContext);
      FrameConstructionItem item(&rootSVGData, aDocElement,
                                 aDocElement->Tag(), kNameSpaceID_SVG,
                                 nullptr, extraRef.forget(), true, nullptr);

      nsFrameItems frameItems;
      contentFrame = ConstructOuterSVG(state, item, mDocElementContainingBlock,
                                       styleContext->StyleDisplay(),
                                       frameItems);
      newFrame = frameItems.FirstChild();
      NS_ASSERTION(frameItems.OnlyChild(), "multiple root element frames");
    } else {
      return nullptr;
    }
  } else {
    bool docElemIsTable = (display->mDisplay == NS_STYLE_DISPLAY_TABLE);
    if (docElemIsTable) {
      // We're going to call the right function ourselves, so no need to give a
      // function to this FrameConstructionData.

      // XXXbz on the other hand, if we converted this whole function to
      // FrameConstructionData/Item, then we'd need the right function
      // here... but would probably be able to get away with less code in this
      // function in general.
      // Use a null PendingBinding, since our binding is not in fact pending.
      static const FrameConstructionData rootTableData = FCDATA_DECL(0, nullptr);
      nsRefPtr<nsStyleContext> extraRef(styleContext);
      FrameConstructionItem item(&rootTableData, aDocElement,
                                 aDocElement->Tag(), kNameSpaceID_None,
                                 nullptr, extraRef.forget(), true, nullptr);

      nsFrameItems frameItems;
      // if the document is a table then just populate it.
      contentFrame = ConstructTable(state, item, mDocElementContainingBlock,
                                    styleContext->StyleDisplay(),
                                    frameItems);
      newFrame = frameItems.FirstChild();
      NS_ASSERTION(frameItems.OnlyChild(), "multiple root element frames");
    } else {
      contentFrame = NS_NewBlockFormattingContext(mPresShell, styleContext);
      nsFrameItems frameItems;
      // Use a null PendingBinding, since our binding is not in fact pending.
      ConstructBlock(state, display, aDocElement,
                     state.GetGeometricParent(display,
                                              mDocElementContainingBlock),
                     mDocElementContainingBlock, styleContext,
                     &contentFrame, frameItems,
                     display->IsPositioned(contentFrame) ? contentFrame : nullptr,
                     nullptr);
      newFrame = frameItems.FirstChild();
      NS_ASSERTION(frameItems.OnlyChild(), "multiple root element frames");
    }
  }

  MOZ_ASSERT(newFrame);
  MOZ_ASSERT(contentFrame);

  // set the primary frame
  aDocElement->SetPrimaryFrame(contentFrame);

  NS_ASSERTION(processChildren ? !mRootElementFrame :
                 mRootElementFrame == contentFrame,
               "unexpected mRootElementFrame");
  mRootElementFrame = contentFrame;

  // Figure out which frame has the main style for the document element,
  // assigning it to mRootElementStyleFrame.
  // Backgrounds should be propagated from that frame to the viewport.
  mRootElementStyleFrame = contentFrame->GetParentStyleContextFrame();
  bool isChild = mRootElementStyleFrame &&
                 mRootElementStyleFrame->GetParent() == contentFrame;
  if (!isChild) {
    mRootElementStyleFrame = mRootElementFrame;
  }

  if (processChildren) {
    // Still need to process the child content
    nsFrameItems childItems;

    NS_ASSERTION(!nsLayoutUtils::GetAsBlock(contentFrame) &&
                 !contentFrame->IsFrameOfType(nsIFrame::eSVG),
                 "Only XUL frames should reach here");
    // Use a null PendingBinding, since our binding is not in fact pending.
    ProcessChildren(state, aDocElement, styleContext, contentFrame, true,
                    childItems, false, nullptr);

    // Set the initial child lists
    contentFrame->SetInitialChildList(kPrincipalList, childItems);
  }

  SetInitialSingleChild(mDocElementContainingBlock, newFrame);

  return newFrame;
}


nsIFrame*
nsCSSFrameConstructor::ConstructRootFrame()
{
  AUTO_LAYOUT_PHASE_ENTRY_POINT(mPresShell->GetPresContext(), FrameC);

  nsStyleSet *styleSet = mPresShell->StyleSet();

  // Set up our style rule observer.
  // XXXbz wouldn't this make more sense as part of presshell init?
  {
    styleSet->SetBindingManager(mDocument->BindingManager());
  }

  // --------- BUILD VIEWPORT -----------
  nsIFrame*                 viewportFrame = nullptr;
  nsRefPtr<nsStyleContext> viewportPseudoStyle;

  viewportPseudoStyle =
    styleSet->ResolveAnonymousBoxStyle(nsCSSAnonBoxes::viewport, nullptr);

  viewportFrame = NS_NewViewportFrame(mPresShell, viewportPseudoStyle);

  // XXXbz do we _have_ to pass a null content pointer to that frame?
  // Would it really kill us to pass in the root element or something?
  // What would that break?
  viewportFrame->Init(nullptr, nullptr, nullptr);

  // Bind the viewport frame to the root view
  nsView* rootView = mPresShell->GetViewManager()->GetRootView();
  viewportFrame->SetView(rootView);

  nsContainerFrame::SyncFrameViewProperties(mPresShell->GetPresContext(), viewportFrame,
                                            viewportPseudoStyle, rootView);
  nsContainerFrame::SyncWindowProperties(mPresShell->GetPresContext(), viewportFrame,
                                         rootView);

  // The viewport is the containing block for 'fixed' elements
  mFixedContainingBlock = viewportFrame;
  // Make it an absolute container for fixed-pos elements
  mFixedContainingBlock->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
  mFixedContainingBlock->MarkAsAbsoluteContainingBlock();

  return viewportFrame;
}

void
nsCSSFrameConstructor::SetUpDocElementContainingBlock(nsIContent* aDocElement)
{
  NS_PRECONDITION(aDocElement, "No element?");
  NS_PRECONDITION(!aDocElement->GetParent(), "Not root content?");
  NS_PRECONDITION(aDocElement->GetCurrentDoc(), "Not in a document?");
  NS_PRECONDITION(aDocElement->GetCurrentDoc()->GetRootElement() ==
                  aDocElement, "Not the root of the document?");

  /*
    how the root frame hierarchy should look

  Galley presentation, non-XUL, with scrolling:
  
      ViewportFrame [fixed-cb]
        nsHTMLScrollFrame
          nsCanvasFrame [abs-cb]
            root element frame (nsBlockFrame, nsSVGOuterSVGFrame,
                                nsTableOuterFrame, nsPlaceholderFrame)

  Galley presentation, XUL
  
      ViewportFrame [fixed-cb]
        nsRootBoxFrame
          root element frame (nsDocElementBoxFrame)

  Print presentation, non-XUL

      ViewportFrame
        nsSimplePageSequenceFrame
          nsPageFrame [fixed-cb]
            nsPageContentFrame
              nsCanvasFrame [abs-cb]
                root element frame (nsBlockFrame, nsSVGOuterSVGFrame,
                                    nsTableOuterFrame, nsPlaceholderFrame)

  Print-preview presentation, non-XUL

      ViewportFrame
        nsHTMLScrollFrame
          nsSimplePageSequenceFrame
            nsPageFrame [fixed-cb]
              nsPageContentFrame
                nsCanvasFrame [abs-cb]
                  root element frame (nsBlockFrame, nsSVGOuterSVGFrame,
                                      nsTableOuterFrame, nsPlaceholderFrame)

  Print/print preview of XUL is not supported.
  [fixed-cb]: the default containing block for fixed-pos content
  [abs-cb]: the default containing block for abs-pos content
 
  Meaning of nsCSSFrameConstructor fields:
    mRootElementFrame is "root element frame".  This is the primary frame for
      the root element.
    mDocElementContainingBlock is the parent of mRootElementFrame
      (i.e. nsCanvasFrame or nsRootBoxFrame)
    mFixedContainingBlock is the [fixed-cb]
    mGfxScrollFrame is the nsHTMLScrollFrame mentioned above, or null if there isn't one
    mPageSequenceFrame is the nsSimplePageSequenceFrame, or null if there isn't one
  */

  // --------- CREATE ROOT FRAME -------


  // Create the root frame. The document element's frame is a child of the
  // root frame.
  //
  // The root frame serves two purposes:
  // - reserves space for any margins needed for the document element's frame
  // - renders the document element's background. This ensures the background covers
  //   the entire canvas as specified by the CSS2 spec

  nsPresContext* presContext = mPresShell->GetPresContext();
  bool isPaginated = presContext->IsRootPaginatedDocument();
  nsIFrame* viewportFrame = mFixedContainingBlock;
  nsStyleContext* viewportPseudoStyle = viewportFrame->StyleContext();

  nsIFrame* rootFrame = nullptr;
  nsIAtom* rootPseudo;
        
  if (!isPaginated) {
#ifdef MOZ_XUL
    if (aDocElement->IsXUL())
    {
      // pass a temporary stylecontext, the correct one will be set later
      rootFrame = NS_NewRootBoxFrame(mPresShell, viewportPseudoStyle);
    } else
#endif
    {
      // pass a temporary stylecontext, the correct one will be set later
      rootFrame = NS_NewCanvasFrame(mPresShell, viewportPseudoStyle);
      mHasRootAbsPosContainingBlock = true;
    }

    rootPseudo = nsCSSAnonBoxes::canvas;
    mDocElementContainingBlock = rootFrame;
  } else {
    // Create a page sequence frame
    rootFrame = NS_NewSimplePageSequenceFrame(mPresShell, viewportPseudoStyle);
    mPageSequenceFrame = rootFrame;
    rootPseudo = nsCSSAnonBoxes::pageSequence;
  }


  // --------- IF SCROLLABLE WRAP IN SCROLLFRAME --------

  // If the device supports scrolling (e.g., in galley mode on the screen and
  // for print-preview, but not when printing), then create a scroll frame that
  // will act as the scrolling mechanism for the viewport. 
  // XXX Do we even need a viewport when printing to a printer?

  // As long as the docshell doesn't prohibit it, and the device supports
  // it, create a scroll frame that will act as the scolling mechanism for
  // the viewport.
  //
  // Threre are three possible values stored in the docshell:
  //  1) nsIScrollable::Scrollbar_Never = no scrollbars
  //  2) nsIScrollable::Scrollbar_Auto = scrollbars appear if needed
  //  3) nsIScrollable::Scrollbar_Always = scrollbars always
  // Only need to create a scroll frame/view for cases 2 and 3.

  bool isHTML = aDocElement->IsHTML();
  bool isXUL = false;

  if (!isHTML) {
    isXUL = aDocElement->IsXUL();
  }

  // Never create scrollbars for XUL documents
  bool isScrollable = isPaginated ? presContext->HasPaginatedScrolling() : !isXUL;

  // We no longer need to do overflow propagation here. It's taken care of
  // when we construct frames for the element whose overflow might be
  // propagated
  NS_ASSERTION(!isScrollable || !isXUL,
               "XUL documents should never be scrollable - see above");

  nsIFrame* newFrame = rootFrame;
  nsRefPtr<nsStyleContext> rootPseudoStyle;
  // we must create a state because if the scrollbars are GFX it needs the 
  // state to build the scrollbar frames.
  nsFrameConstructorState state(mPresShell, nullptr, nullptr, nullptr);

  // Start off with the viewport as parent; we'll adjust it as needed.
  nsIFrame* parentFrame = viewportFrame;

  nsStyleSet* styleSet = mPresShell->StyleSet();
  // If paginated, make sure we don't put scrollbars in
  if (!isScrollable) {
    rootPseudoStyle = styleSet->ResolveAnonymousBoxStyle(rootPseudo,
                                                         viewportPseudoStyle);
  } else {
      if (rootPseudo == nsCSSAnonBoxes::canvas) {
        rootPseudo = nsCSSAnonBoxes::scrolledCanvas;
      } else {
        NS_ASSERTION(rootPseudo == nsCSSAnonBoxes::pageSequence,
                     "Unknown root pseudo");
        rootPseudo = nsCSSAnonBoxes::scrolledPageSequence;
      }

      // Build the frame. We give it the content we are wrapping which is the
      // document element, the root frame, the parent view port frame, and we
      // should get back the new frame and the scrollable view if one was
      // created.

      // resolve a context for the scrollframe
      nsRefPtr<nsStyleContext>  styleContext;
      styleContext = styleSet->ResolveAnonymousBoxStyle(nsCSSAnonBoxes::viewportScroll,
                                                        viewportPseudoStyle);

      // Note that the viewport scrollframe is always built with
      // overflow:auto style. This forces the scroll frame to create
      // anonymous content for both scrollbars. This is necessary even
      // if the HTML or BODY elements are overriding the viewport
      // scroll style to 'hidden' --- dynamic style changes might put
      // scrollbars back on the viewport and we don't want to have to
      // reframe the viewport to create the scrollbar content.
      newFrame = nullptr;
      rootPseudoStyle = BeginBuildingScrollFrame( state,
                                                  aDocElement,
                                                  styleContext,
                                                  viewportFrame,
                                                  rootPseudo,
                                                  true,
                                                  newFrame);
      parentFrame = newFrame;
      mGfxScrollFrame = newFrame;
  }
  
  rootFrame->SetStyleContextWithoutNotification(rootPseudoStyle);
  rootFrame->Init(aDocElement, parentFrame, nullptr);
  
  if (isScrollable) {
    FinishBuildingScrollFrame(parentFrame, rootFrame);
  }
  
  if (isPaginated) { // paginated
    // Create the first page
    // Set the initial child lists
    nsIFrame* canvasFrame;
    nsIFrame* pageFrame =
      ConstructPageFrame(mPresShell, presContext, rootFrame, nullptr,
                         canvasFrame);
    SetInitialSingleChild(rootFrame, pageFrame);

    // The eventual parent of the document element frame.
    // XXX should this be set for every new page (in ConstructPageFrame)?
    mDocElementContainingBlock = canvasFrame;
    mHasRootAbsPosContainingBlock = true;
  }

  if (viewportFrame->GetStateBits() & NS_FRAME_FIRST_REFLOW) {
    SetInitialSingleChild(viewportFrame, newFrame);
  } else {
    nsFrameList newFrameList(newFrame, newFrame);
    viewportFrame->AppendFrames(kPrincipalList, newFrameList);
  }
}

nsIFrame*
nsCSSFrameConstructor::ConstructPageFrame(nsIPresShell*  aPresShell,
                                          nsPresContext* aPresContext,
                                          nsIFrame*      aParentFrame,
                                          nsIFrame*      aPrevPageFrame,
                                          nsIFrame*&     aCanvasFrame)
{
  nsStyleContext* parentStyleContext = aParentFrame->StyleContext();
  nsStyleSet *styleSet = aPresShell->StyleSet();

  nsRefPtr<nsStyleContext> pagePseudoStyle;
  pagePseudoStyle = styleSet->ResolveAnonymousBoxStyle(nsCSSAnonBoxes::page,
                                                       parentStyleContext);

  nsIFrame* pageFrame = NS_NewPageFrame(aPresShell, pagePseudoStyle);

  // Initialize the page frame and force it to have a view. This makes printing of
  // the pages easier and faster.
  pageFrame->Init(nullptr, aParentFrame, aPrevPageFrame);

  nsRefPtr<nsStyleContext> pageContentPseudoStyle;
  pageContentPseudoStyle =
    styleSet->ResolveAnonymousBoxStyle(nsCSSAnonBoxes::pageContent,
                                       pagePseudoStyle);

  nsIFrame* pageContentFrame = NS_NewPageContentFrame(aPresShell, pageContentPseudoStyle);

  // Initialize the page content frame and force it to have a view. Also make it the
  // containing block for fixed elements which are repeated on every page.
  nsIFrame* prevPageContentFrame = nullptr;
  if (aPrevPageFrame) {
    prevPageContentFrame = aPrevPageFrame->GetFirstPrincipalChild();
    NS_ASSERTION(prevPageContentFrame, "missing page content frame");
  }
  pageContentFrame->Init(nullptr, pageFrame, prevPageContentFrame);
  SetInitialSingleChild(pageFrame, pageContentFrame);
  mFixedContainingBlock = pageContentFrame;
  // Make it an absolute container for fixed-pos elements
  mFixedContainingBlock->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
  mFixedContainingBlock->MarkAsAbsoluteContainingBlock();

  nsRefPtr<nsStyleContext> canvasPseudoStyle;
  canvasPseudoStyle = styleSet->ResolveAnonymousBoxStyle(nsCSSAnonBoxes::canvas,
                                                         pageContentPseudoStyle);

  aCanvasFrame = NS_NewCanvasFrame(aPresShell, canvasPseudoStyle);

  nsIFrame* prevCanvasFrame = nullptr;
  if (prevPageContentFrame) {
    prevCanvasFrame = prevPageContentFrame->GetFirstPrincipalChild();
    NS_ASSERTION(prevCanvasFrame, "missing canvas frame");
  }
  aCanvasFrame->Init(nullptr, pageContentFrame, prevCanvasFrame);
  SetInitialSingleChild(pageContentFrame, aCanvasFrame);
  return pageFrame;
}

/* static */
nsIFrame*
nsCSSFrameConstructor::CreatePlaceholderFrameFor(nsIPresShell*    aPresShell, 
                                                 nsIContent*      aContent,
                                                 nsIFrame*        aFrame,
                                                 nsStyleContext*  aStyleContext,
                                                 nsIFrame*        aParentFrame,
                                                 nsIFrame*        aPrevInFlow,
                                                 nsFrameState     aTypeBit)
{
  nsRefPtr<nsStyleContext> placeholderStyle = aPresShell->StyleSet()->
    ResolveStyleForNonElement(aStyleContext->GetParent());
  
  // The placeholder frame gets a pseudo style context
  nsPlaceholderFrame* placeholderFrame =
    (nsPlaceholderFrame*)NS_NewPlaceholderFrame(aPresShell, placeholderStyle,
                                                aTypeBit);

  placeholderFrame->Init(aContent, aParentFrame, aPrevInFlow);

  // The placeholder frame has a pointer back to the out-of-flow frame
  placeholderFrame->SetOutOfFlowFrame(aFrame);

  aFrame->AddStateBits(NS_FRAME_OUT_OF_FLOW);

  // Add mapping from absolutely positioned frame to its placeholder frame
  aPresShell->FrameManager()->RegisterPlaceholderFrame(placeholderFrame);

  return placeholderFrame;
}

// Clears any lazy bits set in the range [aStartContent, aEndContent).  If
// aEndContent is null, that means to clear bits in all siblings starting with
// aStartContent.  aStartContent must not be null unless aEndContent is also
// null.  We do this so that when new children are inserted under elements whose
// frame is a leaf the new children don't cause us to try to construct frames
// for the existing children again.
static inline void
ClearLazyBits(nsIContent* aStartContent, nsIContent* aEndContent)
{
  NS_PRECONDITION(aStartContent || !aEndContent,
                  "Must have start child if we have an end child");
  for (nsIContent* cur = aStartContent; cur != aEndContent;
       cur = cur->GetNextSibling()) {
    cur->UnsetFlags(NODE_DESCENDANTS_NEED_FRAMES | NODE_NEEDS_FRAME);
  }
}

nsIFrame*
nsCSSFrameConstructor::ConstructSelectFrame(nsFrameConstructorState& aState,
                                            FrameConstructionItem&   aItem,
                                            nsIFrame*                aParentFrame,
                                            const nsStyleDisplay*    aStyleDisplay,
                                            nsFrameItems&            aFrameItems)
{
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;

  // Construct a frame-based listbox or combobox
  dom::HTMLSelectElement* sel = dom::HTMLSelectElement::FromContent(content);
  MOZ_ASSERT(sel);
  if (sel->IsCombobox()) {
    // Construct a frame-based combo box.
    // The frame-based combo box is built out of three parts. A display area, a button and
    // a dropdown list. The display area and button are created through anonymous content.
    // The drop-down list's frame is created explicitly. The combobox frame shares its content
    // with the drop-down list.
    uint32_t flags = NS_BLOCK_FLOAT_MGR;
    nsIFrame* comboboxFrame = NS_NewComboboxControlFrame(mPresShell, styleContext, flags);

    // Save the history state so we don't restore during construction
    // since the complete tree is required before we restore.
    nsILayoutHistoryState *historyState = aState.mFrameState;
    aState.mFrameState = nullptr;
    // Initialize the combobox frame
    InitAndRestoreFrame(aState, content,
                        aState.GetGeometricParent(aStyleDisplay, aParentFrame),
                        comboboxFrame);

    aState.AddChild(comboboxFrame, aFrameItems, content, styleContext,
                    aParentFrame);

    nsIComboboxControlFrame* comboBox = do_QueryFrame(comboboxFrame);
    NS_ASSERTION(comboBox, "NS_NewComboboxControlFrame returned frame that "
                 "doesn't implement nsIComboboxControlFrame");

    // Resolve pseudo element style for the dropdown list
    nsRefPtr<nsStyleContext> listStyle;
    listStyle = mPresShell->StyleSet()->
      ResolveAnonymousBoxStyle(nsCSSAnonBoxes::dropDownList, styleContext);

    // Create a listbox
    nsIFrame* listFrame = NS_NewListControlFrame(mPresShell, listStyle);

    // Notify the listbox that it is being used as a dropdown list.
    nsIListControlFrame * listControlFrame = do_QueryFrame(listFrame);
    if (listControlFrame) {
      listControlFrame->SetComboboxFrame(comboboxFrame);
    }
    // Notify combobox that it should use the listbox as it's popup
    comboBox->SetDropDown(listFrame);

    NS_ASSERTION(!listFrame->IsPositioned(),
                 "Ended up with positioned dropdown list somehow.");
    NS_ASSERTION(!listFrame->IsFloating(),
                 "Ended up with floating dropdown list somehow.");
      
    // Initialize the scroll frame positioned. Note that it is NOT
    // initialized as absolutely positioned.
    nsIFrame* scrolledFrame = NS_NewSelectsAreaFrame(mPresShell, styleContext, flags);

    InitializeSelectFrame(aState, listFrame, scrolledFrame, content,
                          comboboxFrame, listStyle, true,
                          aItem.mPendingBinding, aFrameItems);

    NS_ASSERTION(listFrame->GetView(), "ListFrame's view is nullptr");

    // Create display and button frames from the combobox's anonymous content.
    // The anonymous content is appended to existing anonymous content for this
    // element (the scrollbars).

    nsFrameItems childItems;
    CreateAnonymousFrames(aState, content, comboboxFrame,
                          aItem.mPendingBinding, childItems);

    comboboxFrame->SetInitialChildList(kPrincipalList, childItems);

    // Initialize the additional popup child list which contains the
    // dropdown list frame.
    nsFrameItems popupItems;
    popupItems.AddChild(listFrame);
    comboboxFrame->SetInitialChildList(nsIFrame::kSelectPopupList,
                                       popupItems);

    aState.mFrameState = historyState;
    if (aState.mFrameState) {
      // Restore frame state for the entire subtree of |comboboxFrame|.
      RestoreFrameState(comboboxFrame, aState.mFrameState);
    }
    return comboboxFrame;
  }

  // Listbox, not combobox
  nsIFrame* listFrame = NS_NewListControlFrame(mPresShell, styleContext);

  nsIFrame* scrolledFrame = NS_NewSelectsAreaFrame(
      mPresShell, styleContext, NS_BLOCK_FLOAT_MGR);

  // ******* this code stolen from Initialze ScrollFrame ********
  // please adjust this code to use BuildScrollFrame.

  InitializeSelectFrame(aState, listFrame, scrolledFrame, content,
                        aParentFrame, styleContext, false,
                        aItem.mPendingBinding, aFrameItems);

  return listFrame;
}

/**
 * Used to be InitializeScrollFrame but now it's only used for the select tag
 * But the select tag should really be fixed to use GFX scrollbars that can
 * be create with BuildScrollFrame.
 */
nsresult
nsCSSFrameConstructor::InitializeSelectFrame(nsFrameConstructorState& aState,
                                             nsIFrame*                scrollFrame,
                                             nsIFrame*                scrolledFrame,
                                             nsIContent*              aContent,
                                             nsIFrame*                aParentFrame,
                                             nsStyleContext*          aStyleContext,
                                             bool                     aBuildCombobox,
                                             PendingBinding*          aPendingBinding,
                                             nsFrameItems&            aFrameItems)
{
  const nsStyleDisplay* display = aStyleContext->StyleDisplay();

  // Initialize it
  nsIFrame* geometricParent = aState.GetGeometricParent(display, aParentFrame);
    
  // We don't call InitAndRestoreFrame for scrollFrame because we can only
  // restore the frame state after its parts have been created (in particular,
  // the scrollable view). So we have to split Init and Restore.

  // Initialize the frame
  scrollFrame->Init(aContent, geometricParent, nullptr);

  if (!aBuildCombobox) {
    aState.AddChild(scrollFrame, aFrameItems, aContent,
                    aStyleContext, aParentFrame);
  }
      
  if (aBuildCombobox) {
    nsContainerFrame::CreateViewForFrame(scrollFrame, true);
  }

  BuildScrollFrame(aState, aContent, aStyleContext, scrolledFrame,
                   geometricParent, scrollFrame);

  if (aState.mFrameState) {
    // Restore frame state for the scroll frame
    RestoreFrameStateFor(scrollFrame, aState.mFrameState);
  }

  // Process children
  nsFrameItems                childItems;

  ProcessChildren(aState, aContent, aStyleContext, scrolledFrame, false,
                  childItems, false, aPendingBinding);

  // Set the scrolled frame's initial child lists
  scrolledFrame->SetInitialChildList(kPrincipalList, childItems);
  return NS_OK;
}

nsIFrame*
nsCSSFrameConstructor::ConstructFieldSetFrame(nsFrameConstructorState& aState,
                                              FrameConstructionItem&   aItem,
                                              nsIFrame*                aParentFrame,
                                              const nsStyleDisplay*    aStyleDisplay,
                                              nsFrameItems&            aFrameItems)
{
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;

  nsIFrame* newFrame = NS_NewFieldSetFrame(mPresShell, styleContext);

  // Initialize it
  InitAndRestoreFrame(aState, content,
                      aState.GetGeometricParent(aStyleDisplay, aParentFrame),
                      newFrame);

  // Resolve style and initialize the frame
  nsRefPtr<nsStyleContext> fieldsetContentStyle;
  fieldsetContentStyle = mPresShell->StyleSet()->
    ResolveAnonymousBoxStyle(nsCSSAnonBoxes::fieldsetContent, styleContext);

  nsIFrame* blockFrame = NS_NewBlockFrame(mPresShell, fieldsetContentStyle,
                                          NS_BLOCK_FLOAT_MGR |
                                          NS_BLOCK_MARGIN_ROOT);
  InitAndRestoreFrame(aState, content, newFrame, blockFrame);

  aState.AddChild(newFrame, aFrameItems, content, styleContext, aParentFrame);
  
  // Process children
  nsFrameConstructorSaveState absoluteSaveState;
  nsFrameItems                childItems;

  newFrame->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
  if (newFrame->IsPositioned()) {
    aState.PushAbsoluteContainingBlock(newFrame, newFrame, absoluteSaveState);
  }

  ProcessChildren(aState, content, styleContext, blockFrame, true,
                  childItems, true, aItem.mPendingBinding);

  nsFrameItems fieldsetKids;
  fieldsetKids.AddChild(blockFrame);

  for (nsFrameList::Enumerator e(childItems); !e.AtEnd(); e.Next()) {
    nsIFrame* child = e.get();
    if (child->GetContentInsertionFrame()->GetType() == nsGkAtoms::legendFrame) {
      // We want the legend to be the first frame in the fieldset child list.
      // That way the EventStateManager will do the right thing when tabbing
      // from a selection point within the legend (bug 236071), which is
      // used for implementing legend access keys (bug 81481).
      // GetAdjustedParentFrame() below depends on this frame order.
      childItems.RemoveFrame(child);
      // Make sure to reparent the legend so it has the fieldset as the parent.
      fieldsetKids.InsertFrame(newFrame, nullptr, child);
      break;
    }
  }

  // Set the inner frame's initial child lists
  blockFrame->SetInitialChildList(kPrincipalList, childItems);

  // Set the outer frame's initial child list
  newFrame->SetInitialChildList(kPrincipalList, fieldsetKids);

  newFrame->AddStateBits(NS_FRAME_MAY_HAVE_GENERATED_CONTENT);

  // Our new frame returned is the outer frame, which is the fieldset frame.
  return newFrame; 
}

static nsIFrame*
FindAncestorWithGeneratedContentPseudo(nsIFrame* aFrame)
{
  for (nsIFrame* f = aFrame->GetParent(); f; f = f->GetParent()) {
    NS_ASSERTION(f->IsGeneratedContentFrame(),
                 "should not have exited generated content");
    nsIAtom* pseudo = f->StyleContext()->GetPseudo();
    if (pseudo == nsCSSPseudoElements::before ||
        pseudo == nsCSSPseudoElements::after)
      return f;
  }
  return nullptr;
}

#define SIMPLE_FCDATA(_func) FCDATA_DECL(0, _func)
#define FULL_CTOR_FCDATA(_flags, _func)                             \
  { _flags | FCDATA_FUNC_IS_FULL_CTOR, { nullptr }, _func, nullptr }

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindTextData(nsIFrame* aParentFrame)
{
  if (aParentFrame && IsFrameForSVG(aParentFrame)) {
    nsIFrame *ancestorFrame =
      nsSVGUtils::GetFirstNonAAncestorFrame(aParentFrame);
    if (ancestorFrame) {
      if (NS_SVGTextCSSFramesEnabled()) {
        static const FrameConstructionData sSVGTextData =
          FCDATA_DECL(FCDATA_IS_LINE_PARTICIPANT | FCDATA_IS_SVG_TEXT,
                      NS_NewTextFrame);
        if (ancestorFrame->IsSVGText()) {
          return &sSVGTextData;
        }
      } else {
        static const FrameConstructionData sSVGGlyphData =
          SIMPLE_FCDATA(NS_NewSVGGlyphFrame);
        nsSVGTextContainerFrame* metrics = do_QueryFrame(ancestorFrame);
        if (metrics) {
          return &sSVGGlyphData;
        }
      }
    }
    return nullptr;
  }

  static const FrameConstructionData sTextData =
    FCDATA_DECL(FCDATA_IS_LINE_PARTICIPANT, NS_NewTextFrame);
  return &sTextData;
}

void
nsCSSFrameConstructor::ConstructTextFrame(const FrameConstructionData* aData,
                                          nsFrameConstructorState& aState,
                                          nsIContent*              aContent,
                                          nsIFrame*                aParentFrame,
                                          nsStyleContext*          aStyleContext,
                                          nsFrameItems&            aFrameItems)
{
  NS_PRECONDITION(aData, "Must have frame construction data");

  nsIFrame* newFrame = (*aData->mFunc.mCreationFunc)(mPresShell, aStyleContext);

  InitAndRestoreFrame(aState, aContent, aParentFrame, newFrame);

  // We never need to create a view for a text frame.

  if (newFrame->IsGeneratedContentFrame()) {
    nsAutoPtr<nsGenConInitializer> initializer;
    initializer =
      static_cast<nsGenConInitializer*>(
        aContent->UnsetProperty(nsGkAtoms::genConInitializerProperty));
    if (initializer) {
      if (initializer->mNode->InitTextFrame(initializer->mList,
              FindAncestorWithGeneratedContentPseudo(newFrame), newFrame)) {
        (this->*(initializer->mDirtyAll))();
      }
      initializer->mNode.forget();
    }
  }
  
  // Add the newly constructed frame to the flow
  aFrameItems.AddChild(newFrame);

  if (!aState.mCreatingExtraFrames)
    aContent->SetPrimaryFrame(newFrame);
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindDataByInt(int32_t aInt,
                                     Element* aElement,
                                     nsStyleContext* aStyleContext,
                                     const FrameConstructionDataByInt* aDataPtr,
                                     uint32_t aDataLength)
{
  for (const FrameConstructionDataByInt *curData = aDataPtr,
         *endData = aDataPtr + aDataLength;
       curData != endData;
       ++curData) {
    if (curData->mInt == aInt) {
      const FrameConstructionData* data = &curData->mData;
      if (data->mBits & FCDATA_FUNC_IS_DATA_GETTER) {
        return data->mFunc.mDataGetter(aElement, aStyleContext);
      }

      return data;
    }
  }

  return nullptr;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindDataByTag(nsIAtom* aTag,
                                     Element* aElement,
                                     nsStyleContext* aStyleContext,
                                     const FrameConstructionDataByTag* aDataPtr,
                                     uint32_t aDataLength)
{
  for (const FrameConstructionDataByTag *curData = aDataPtr,
         *endData = aDataPtr + aDataLength;
       curData != endData;
       ++curData) {
    if (*curData->mTag == aTag) {
      const FrameConstructionData* data = &curData->mData;
      if (data->mBits & FCDATA_FUNC_IS_DATA_GETTER) {
        return data->mFunc.mDataGetter(aElement, aStyleContext);
      }

      return data;
    }
  }

  return nullptr;
}

#define SUPPRESS_FCDATA() FCDATA_DECL(FCDATA_SUPPRESS_FRAME, nullptr)
#define SIMPLE_INT_CREATE(_int, _func) { _int, SIMPLE_FCDATA(_func) }
#define SIMPLE_INT_CHAIN(_int, _func)                       \
  { _int, FCDATA_DECL(FCDATA_FUNC_IS_DATA_GETTER, _func) }
#define COMPLEX_INT_CREATE(_int, _func)         \
  { _int, FULL_CTOR_FCDATA(0, _func) }

#define SIMPLE_TAG_CREATE(_tag, _func)          \
  { &nsGkAtoms::_tag, SIMPLE_FCDATA(_func) }
#define SIMPLE_TAG_CHAIN(_tag, _func)                                   \
  { &nsGkAtoms::_tag, FCDATA_DECL(FCDATA_FUNC_IS_DATA_GETTER,  _func) }
#define COMPLEX_TAG_CREATE(_tag, _func)             \
  { &nsGkAtoms::_tag, FULL_CTOR_FCDATA(0, _func) }

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindHTMLData(Element* aElement,
                                    nsIAtom* aTag,
                                    int32_t aNameSpaceID,
                                    nsIFrame* aParentFrame,
                                    nsStyleContext* aStyleContext)
{
  // Ignore the tag if it's not HTML content and if it doesn't extend (via XBL)
  // a valid HTML namespace.  This check must match the one in
  // ShouldHaveFirstLineStyle.
  if (aNameSpaceID != kNameSpaceID_XHTML) {
    return nullptr;
  }

  NS_ASSERTION(!aParentFrame ||
               aParentFrame->StyleContext()->GetPseudo() !=
                 nsCSSAnonBoxes::fieldsetContent ||
               aParentFrame->GetParent()->GetType() == nsGkAtoms::fieldSetFrame,
               "Unexpected parent for fieldset content anon box");
  if (aTag == nsGkAtoms::legend &&
      (!aParentFrame ||
       (aParentFrame->GetType() != nsGkAtoms::fieldSetFrame &&
        aParentFrame->StyleContext()->GetPseudo() !=
          nsCSSAnonBoxes::fieldsetContent) ||
       !aElement->GetParent() ||
       !aElement->GetParent()->IsHTML(nsGkAtoms::fieldset) ||
       aStyleContext->StyleDisplay()->IsFloatingStyle() ||
       aStyleContext->StyleDisplay()->IsAbsolutelyPositionedStyle())) {
    // <legend> is only special inside fieldset, check both the frame tree
    // parent and content tree parent due to XBL issues. For floated or
    // absolutely positioned legends we want to construct by display type and
    // not do special legend stuff.
    // XXXbz it would be nice if we could just decide this based on the parent
    // tag, and hence just use a SIMPLE_TAG_CHAIN for legend below, but the
    // fact that with XBL we could end up with this legend element in some
    // totally weird insertion point makes that chancy, I think.
    return nullptr;
  }

  static const FrameConstructionDataByTag sHTMLData[] = {
    SIMPLE_TAG_CHAIN(img, nsCSSFrameConstructor::FindImgData),
    SIMPLE_TAG_CHAIN(mozgeneratedcontentimage,
                     nsCSSFrameConstructor::FindImgData),
    { &nsGkAtoms::br,
      FCDATA_DECL(FCDATA_IS_LINE_PARTICIPANT | FCDATA_IS_LINE_BREAK,
                  NS_NewBRFrame) },
    SIMPLE_TAG_CREATE(wbr, NS_NewWBRFrame),
    SIMPLE_TAG_CHAIN(input, nsCSSFrameConstructor::FindInputData),
    SIMPLE_TAG_CREATE(textarea, NS_NewTextControlFrame),
    COMPLEX_TAG_CREATE(select, &nsCSSFrameConstructor::ConstructSelectFrame),
    SIMPLE_TAG_CHAIN(object, nsCSSFrameConstructor::FindObjectData),
    SIMPLE_TAG_CHAIN(applet, nsCSSFrameConstructor::FindObjectData),
    SIMPLE_TAG_CHAIN(embed, nsCSSFrameConstructor::FindObjectData),
    COMPLEX_TAG_CREATE(fieldset,
                       &nsCSSFrameConstructor::ConstructFieldSetFrame),
    { &nsGkAtoms::legend,
      FCDATA_DECL(FCDATA_ALLOW_BLOCK_STYLES | FCDATA_MAY_NEED_SCROLLFRAME,
                  NS_NewLegendFrame) },
    SIMPLE_TAG_CREATE(frameset, NS_NewHTMLFramesetFrame),
    SIMPLE_TAG_CREATE(iframe, NS_NewSubDocumentFrame),
    { &nsGkAtoms::button,
      FCDATA_WITH_WRAPPING_BLOCK(FCDATA_ALLOW_BLOCK_STYLES,
                                 NS_NewHTMLButtonControlFrame,
                                 nsCSSAnonBoxes::buttonContent) },
    SIMPLE_TAG_CHAIN(canvas, nsCSSFrameConstructor::FindCanvasData),
    SIMPLE_TAG_CREATE(video, NS_NewHTMLVideoFrame),
    SIMPLE_TAG_CREATE(audio, NS_NewHTMLVideoFrame),
    SIMPLE_TAG_CREATE(progress, NS_NewProgressFrame),
    SIMPLE_TAG_CREATE(meter, NS_NewMeterFrame)
  };

  return FindDataByTag(aTag, aElement, aStyleContext, sHTMLData,
                       ArrayLength(sHTMLData));
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindImgData(Element* aElement,
                                   nsStyleContext* aStyleContext)
{
  if (!nsImageFrame::ShouldCreateImageFrameFor(aElement, aStyleContext)) {
    return nullptr;
  }

  static const FrameConstructionData sImgData = SIMPLE_FCDATA(NS_NewImageFrame);
  return &sImgData;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindImgControlData(Element* aElement,
                                          nsStyleContext* aStyleContext)
{
  if (!nsImageFrame::ShouldCreateImageFrameFor(aElement, aStyleContext)) {
    return nullptr;
  }

  static const FrameConstructionData sImgControlData =
    SIMPLE_FCDATA(NS_NewImageControlFrame);
  return &sImgControlData;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindInputData(Element* aElement,
                                     nsStyleContext* aStyleContext)
{
  static const FrameConstructionDataByInt sInputData[] = {
    SIMPLE_INT_CREATE(NS_FORM_INPUT_CHECKBOX, NS_NewGfxCheckboxControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_RADIO, NS_NewGfxRadioControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_FILE, NS_NewFileControlFrame),
    SIMPLE_INT_CHAIN(NS_FORM_INPUT_IMAGE,
                     nsCSSFrameConstructor::FindImgControlData),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_EMAIL, NS_NewTextControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_SEARCH, NS_NewTextControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_TEXT, NS_NewTextControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_TEL, NS_NewTextControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_URL, NS_NewTextControlFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_RANGE, NS_NewRangeFrame),
    SIMPLE_INT_CREATE(NS_FORM_INPUT_PASSWORD, NS_NewTextControlFrame),
    { NS_FORM_INPUT_COLOR,
      FCDATA_WITH_WRAPPING_BLOCK(0, NS_NewColorControlFrame,
                                 nsCSSAnonBoxes::buttonContent) },
    // TODO: this is temporary until a frame is written: bug 635240.
    SIMPLE_INT_CREATE(NS_FORM_INPUT_NUMBER, NS_NewTextControlFrame),
    // TODO: this is temporary until a frame is written: bug 773205.
    SIMPLE_INT_CREATE(NS_FORM_INPUT_DATE, NS_NewTextControlFrame),
    // TODO: this is temporary until a frame is written: bug 773205
    SIMPLE_INT_CREATE(NS_FORM_INPUT_TIME, NS_NewTextControlFrame),
    { NS_FORM_INPUT_SUBMIT,
      FCDATA_WITH_WRAPPING_BLOCK(0, NS_NewGfxButtonControlFrame,
                                 nsCSSAnonBoxes::buttonContent) },
    { NS_FORM_INPUT_RESET,
      FCDATA_WITH_WRAPPING_BLOCK(0, NS_NewGfxButtonControlFrame,
                                 nsCSSAnonBoxes::buttonContent) },
    { NS_FORM_INPUT_BUTTON,
      FCDATA_WITH_WRAPPING_BLOCK(0, NS_NewGfxButtonControlFrame,
                                 nsCSSAnonBoxes::buttonContent) }
    // Keeping hidden inputs out of here on purpose for so they get frames by
    // display (in practice, none).
  };

  nsCOMPtr<nsIFormControl> control = do_QueryInterface(aElement);
  NS_ASSERTION(control, "input doesn't implement nsIFormControl?");

  return FindDataByInt(control->GetType(), aElement, aStyleContext,
                       sInputData, ArrayLength(sInputData));
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindObjectData(Element* aElement,
                                      nsStyleContext* aStyleContext)
{
  // GetDisplayedType isn't necessarily nsIObjectLoadingContent::TYPE_NULL for
  // cases when the object is broken/suppressed/etc (e.g. a broken image), but
  // we want to treat those cases as TYPE_NULL
  uint32_t type;
  if (aElement->State().HasAtLeastOneOfStates(NS_EVENT_STATE_BROKEN |
                                              NS_EVENT_STATE_USERDISABLED |
                                              NS_EVENT_STATE_SUPPRESSED)) {
    type = nsIObjectLoadingContent::TYPE_NULL;
  } else {
    nsCOMPtr<nsIObjectLoadingContent> objContent(do_QueryInterface(aElement));
    NS_ASSERTION(objContent,
                 "applet, embed and object must implement "
                 "nsIObjectLoadingContent!");

    objContent->GetDisplayedType(&type);
  }

  static const FrameConstructionDataByInt sObjectData[] = {
    SIMPLE_INT_CREATE(nsIObjectLoadingContent::TYPE_LOADING,
                      NS_NewEmptyFrame),
    SIMPLE_INT_CREATE(nsIObjectLoadingContent::TYPE_PLUGIN,
                      NS_NewObjectFrame),
    SIMPLE_INT_CREATE(nsIObjectLoadingContent::TYPE_IMAGE,
                      NS_NewImageFrame),
    SIMPLE_INT_CREATE(nsIObjectLoadingContent::TYPE_DOCUMENT,
                      NS_NewSubDocumentFrame)
    // Nothing for TYPE_NULL so we'll construct frames by display there
  };

  return FindDataByInt((int32_t)type, aElement, aStyleContext,
                       sObjectData, ArrayLength(sObjectData));
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindCanvasData(Element* aElement,
                                      nsStyleContext* aStyleContext)
{
  // We want to check whether script is enabled on the document that
  // could be painting to the canvas.  That's the owner document of
  // the canvas, except when the owner document is a static document,
  // in which case it's the original document it was cloned from.
  nsIDocument* doc = aElement->OwnerDoc();
  if (doc->IsStaticDocument()) {
    doc = doc->GetOriginalDocument();
  }
  if (!doc->IsScriptEnabled()) {
    return nullptr;
  }

  static const FrameConstructionData sCanvasData =
    FCDATA_WITH_WRAPPING_BLOCK(0, NS_NewHTMLCanvasFrame,
                               nsCSSAnonBoxes::htmlCanvasContent);
  return &sCanvasData;
}

void
nsCSSFrameConstructor::ConstructFrameFromItemInternal(FrameConstructionItem& aItem,
                                                      nsFrameConstructorState& aState,
                                                      nsIFrame* aParentFrame,
                                                      nsFrameItems& aFrameItems)
{
  const FrameConstructionData* data = aItem.mFCData;
  NS_ASSERTION(data, "Must have frame construction data");

  uint32_t bits = data->mBits;

  NS_ASSERTION(!(bits & FCDATA_FUNC_IS_DATA_GETTER),
               "Should have dealt with this inside the data finder");

  // Some sets of bits are not compatible with each other
#define CHECK_ONLY_ONE_BIT(_bit1, _bit2)               \
  NS_ASSERTION(!(bits & _bit1) || !(bits & _bit2),     \
               "Only one of these bits should be set")
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_FORCE_NULL_ABSPOS_CONTAINER);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_WRAP_KIDS_IN_BLOCKS);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_MAY_NEED_SCROLLFRAME);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_IS_POPUP);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_SKIP_ABSPOS_PUSH);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR,
                     FCDATA_DISALLOW_GENERATED_CONTENT);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR, FCDATA_ALLOW_BLOCK_STYLES);
  CHECK_ONLY_ONE_BIT(FCDATA_FUNC_IS_FULL_CTOR,
                     FCDATA_CREATE_BLOCK_WRAPPER_FOR_ALL_KIDS);
  CHECK_ONLY_ONE_BIT(FCDATA_WRAP_KIDS_IN_BLOCKS,
                     FCDATA_CREATE_BLOCK_WRAPPER_FOR_ALL_KIDS);
#undef CHECK_ONLY_ONE_BIT
  NS_ASSERTION(!(bits & FCDATA_FORCED_NON_SCROLLABLE_BLOCK) ||
               ((bits & FCDATA_FUNC_IS_FULL_CTOR) &&
                data->mFullConstructor ==
                  &nsCSSFrameConstructor::ConstructNonScrollableBlock),
               "Unexpected FCDATA_FORCED_NON_SCROLLABLE_BLOCK flag");

  // Don't create a subdocument frame for iframes if we're creating extra frames
  if (aState.mCreatingExtraFrames && aItem.mContent->IsHTML() &&
      aItem.mContent->Tag() == nsGkAtoms::iframe)
  {
    return;
  }

  nsStyleContext* const styleContext = aItem.mStyleContext;
  const nsStyleDisplay* display = styleContext->StyleDisplay();
  nsIContent* const content = aItem.mContent;

  // Get the parent of the content and check if it is a XBL children element.
  // Push the children element as an ancestor here because it does
  // not have a frame and would not otherwise be pushed as an ancestor. It is
  // necessary to do so in order to correctly handle style resolution on
  // descendants.
  nsIContent* parent = content->GetParent();
  bool pushInsertionPoint = aState.mTreeMatchContext.mAncestorFilter.HasFilter() &&
    parent && parent->IsActiveChildrenElement();
  TreeMatchContext::AutoAncestorPusher
    insertionPointPusher(pushInsertionPoint,
                         aState.mTreeMatchContext,
                         parent && parent->IsElement() ? parent->AsElement() : nullptr);

  // Push the content as a style ancestor now, so we don't have to do
  // it in our various full-constructor functions.  In particular,
  // since a number of full-constructor functions don't actually call
  // ProcessChildren in some cases (e.g. for CSS anonymous table boxes
  // or for situations where only anonymouse children are having
  // frames constructed), this is the best place to bottleneck the
  // pushing of the content instead of having to do it in multiple
  // places.
  TreeMatchContext::AutoAncestorPusher
    ancestorPusher(aState.mTreeMatchContext.mAncestorFilter.HasFilter(),
                   aState.mTreeMatchContext,
                   content->IsElement() ? content->AsElement() : nullptr);

  nsIFrame* newFrame;
  nsIFrame* primaryFrame;
  if (bits & FCDATA_FUNC_IS_FULL_CTOR) {
    newFrame =
      (this->*(data->mFullConstructor))(aState, aItem, aParentFrame,
                                        display, aFrameItems);
    MOZ_ASSERT(newFrame, "Full constructor failed");
    primaryFrame = newFrame;
  } else {
    newFrame =
      (*data->mFunc.mCreationFunc)(mPresShell, styleContext);

    bool allowOutOfFlow = !(bits & FCDATA_DISALLOW_OUT_OF_FLOW);
    bool isPopup = aItem.mIsPopup;
    NS_ASSERTION(!isPopup ||
                 (aState.mPopupItems.containingBlock &&
                  aState.mPopupItems.containingBlock->GetType() ==
                    nsGkAtoms::popupSetFrame),
                 "Should have a containing block here!");

    nsIFrame* geometricParent =
      isPopup ? aState.mPopupItems.containingBlock :
      (allowOutOfFlow ? aState.GetGeometricParent(display, aParentFrame)
                      : aParentFrame);

    // Must init frameToAddToList to null, since it's inout
    nsIFrame* frameToAddToList = nullptr;
    if ((bits & FCDATA_MAY_NEED_SCROLLFRAME) &&
        display->IsScrollableOverflow()) {
      BuildScrollFrame(aState, content, styleContext, newFrame,
                       geometricParent, frameToAddToList);
    } else {
      InitAndRestoreFrame(aState, content, geometricParent, newFrame);
      // See whether we need to create a view
      nsContainerFrame::CreateViewForFrame(newFrame, false);
      frameToAddToList = newFrame;
    }

    // Use frameToAddToList as the primary frame.  In the non-scrollframe case
    // they're equal, but in the scrollframe case newFrame is the scrolled
    // frame, while frameToAddToList is the scrollframe (and should be the
    // primary frame).
    primaryFrame = frameToAddToList;

    // If we need to create a block formatting context to wrap our
    // kids, do it now.
    const nsStyleDisplay* maybeAbsoluteContainingBlockDisplay = display;
    nsIFrame* maybeAbsoluteContainingBlock = newFrame;
    nsIFrame* possiblyLeafFrame = newFrame;
    if (bits & FCDATA_CREATE_BLOCK_WRAPPER_FOR_ALL_KIDS) {
      nsRefPtr<nsStyleContext> blockContext;
      blockContext =
        mPresShell->StyleSet()->ResolveAnonymousBoxStyle(*data->mAnonBoxPseudo,
                                                         styleContext);
      nsIFrame* blockFrame =
        NS_NewBlockFormattingContext(mPresShell, blockContext);

      InitAndRestoreFrame(aState, content, newFrame, blockFrame);

      SetInitialSingleChild(newFrame, blockFrame);

      // Now figure out whether newFrame or blockFrame should be the
      // absolute container.  It should be the latter if it's
      // positioned, otherwise the former.
      const nsStyleDisplay* blockDisplay = blockContext->StyleDisplay();
      if (blockDisplay->IsPositioned(blockFrame)) {
        maybeAbsoluteContainingBlockDisplay = blockDisplay;
        maybeAbsoluteContainingBlock = blockFrame;
      }
      
      // Our kids should go into the blockFrame
      newFrame = blockFrame;
    }

    aState.AddChild(frameToAddToList, aFrameItems, content, styleContext,
                    aParentFrame, allowOutOfFlow, allowOutOfFlow, isPopup);

#ifdef MOZ_XUL
    // Icky XUL stuff, sadly

    if (aItem.mIsRootPopupgroup) {
      NS_ASSERTION(nsIRootBox::GetRootBox(mPresShell) &&
                   nsIRootBox::GetRootBox(mPresShell)->GetPopupSetFrame() ==
                     newFrame,
                   "Unexpected PopupSetFrame");
      aState.mPopupItems.containingBlock = newFrame;
      aState.mHavePendingPopupgroup = false;
    }
#endif /* MOZ_XUL */

    // Process the child content if requested
    nsFrameItems childItems;
    nsFrameConstructorSaveState absoluteSaveState;

    if (bits & FCDATA_FORCE_NULL_ABSPOS_CONTAINER) {
      aState.PushAbsoluteContainingBlock(nullptr, nullptr, absoluteSaveState);
    } else if (!(bits & FCDATA_SKIP_ABSPOS_PUSH)) {
      nsIFrame* cb = maybeAbsoluteContainingBlock;
      cb->AddStateBits(NS_FRAME_CAN_HAVE_ABSPOS_CHILDREN);
      if ((maybeAbsoluteContainingBlockDisplay->IsAbsolutelyPositionedStyle() ||
           maybeAbsoluteContainingBlockDisplay->IsRelativelyPositionedStyle() ||
           (maybeAbsoluteContainingBlockDisplay->HasTransformStyle() &&
            cb->IsFrameOfType(nsIFrame::eSupportsCSSTransforms))) &&
          !cb->IsSVGText()) {
        aState.PushAbsoluteContainingBlock(cb, primaryFrame, absoluteSaveState);
      }
    }

    if (!aItem.mAnonChildren.IsEmpty()) {
      NS_ASSERTION(!(bits & FCDATA_USE_CHILD_ITEMS),
                   "We should not have both anonymous and non-anonymous "
                   "children in a given FrameConstructorItem");
      AddFCItemsForAnonymousContent(aState, newFrame, aItem.mAnonChildren,
                                    aItem.mChildItems);
      bits |= FCDATA_USE_CHILD_ITEMS;
    }

    if (bits & FCDATA_USE_CHILD_ITEMS) {
      nsFrameConstructorSaveState floatSaveState;

      if (ShouldSuppressFloatingOfDescendants(newFrame)) {
        aState.PushFloatContainingBlock(nullptr, floatSaveState);
      } else if (newFrame->IsFloatContainingBlock()) {
        aState.PushFloatContainingBlock(newFrame, floatSaveState);
      }
      ConstructFramesFromItemList(aState, aItem.mChildItems, newFrame,
                                  childItems);
    } else {
      // Process the child frames.
      ProcessChildren(aState, content, styleContext, newFrame,
                      !(bits & FCDATA_DISALLOW_GENERATED_CONTENT),
                      childItems,
                      (bits & FCDATA_ALLOW_BLOCK_STYLES) != 0,
                      aItem.mPendingBinding, possiblyLeafFrame);
    }

#ifdef MOZ_XUL
    // More icky XUL stuff
    if (aItem.mNameSpaceID == kNameSpaceID_XUL &&
        (aItem.mTag == nsGkAtoms::treechildren || // trees always need titletips
         content->HasAttr(kNameSpaceID_None, nsGkAtoms::tooltiptext) ||
         content->HasAttr(kNameSpaceID_None, nsGkAtoms::tooltip))) {
      nsIRootBox* rootBox = nsIRootBox::GetRootBox(mPresShell);
      if (rootBox) {
        rootBox->AddTooltipSupport(content);
      }
    }
#endif

    if (bits & FCDATA_WRAP_KIDS_IN_BLOCKS) {
      nsFrameItems newItems;
      nsFrameItems currentBlockItems;
      nsIFrame* f;
      while ((f = childItems.FirstChild()) != nullptr) {
        bool wrapFrame = IsInlineFrame(f) || IsFrameSpecial(f);
        if (!wrapFrame) {
          FlushAccumulatedBlock(aState, content, newFrame,
                                currentBlockItems, newItems);
        }

        childItems.RemoveFrame(f);
        if (wrapFrame) {
          currentBlockItems.AddChild(f);
        } else {
          newItems.AddChild(f);
        }
      }
      FlushAccumulatedBlock(aState, content, newFrame,
                            currentBlockItems, newItems);

      if (childItems.NotEmpty()) {
        // an error must have occurred, delete unprocessed frames
        childItems.DestroyFrames();
      }

      childItems = newItems;
    }

    // Set the frame's initial child list
    // Note that MathML depends on this being called even if
    // childItems is empty!
    newFrame->SetInitialChildList(kPrincipalList, childItems);
  }

  NS_ASSERTION(newFrame->IsFrameOfType(nsIFrame::eLineParticipant) ==
               ((bits & FCDATA_IS_LINE_PARTICIPANT) != 0),
               "Incorrectly set FCDATA_IS_LINE_PARTICIPANT bits");

  // Even if mCreatingExtraFrames is set, we may need to SetPrimaryFrame for
  // generated content that doesn't have one yet.  Note that we have to examine
  // the frame bit, because by this point mIsGeneratedContent has been cleared
  // on aItem.
  if ((!aState.mCreatingExtraFrames ||
       ((primaryFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT) &&
        !aItem.mContent->GetPrimaryFrame())) &&
       !(bits & FCDATA_SKIP_FRAMESET)) {
    aItem.mContent->SetPrimaryFrame(primaryFrame);
  }
}

// after the node has been constructed and initialized create any
// anonymous content a node needs.
nsresult
nsCSSFrameConstructor::CreateAnonymousFrames(nsFrameConstructorState& aState,
                                             nsIContent*              aParent,
                                             nsIFrame*                aParentFrame,
                                             PendingBinding*          aPendingBinding,
                                             nsFrameItems&            aChildItems)
{
  nsAutoTArray<nsIAnonymousContentCreator::ContentInfo, 4> newAnonymousItems;
  nsresult rv = GetAnonymousContent(aParent, aParentFrame, newAnonymousItems);
  NS_ENSURE_SUCCESS(rv, rv);

  uint32_t count = newAnonymousItems.Length();
  if (count == 0) {
    return NS_OK;
  }

  nsFrameConstructorState::PendingBindingAutoPusher pusher(aState,
                                                           aPendingBinding);
  TreeMatchContext::AutoAncestorPusher
    ancestorPusher(aState.mTreeMatchContext.mAncestorFilter.HasFilter(),
                   aState.mTreeMatchContext,
                   aParent->AsElement());

  nsIAnonymousContentCreator* creator = do_QueryFrame(aParentFrame);
  NS_ASSERTION(creator,
               "How can that happen if we have nodes to construct frames for?");

  for (uint32_t i=0; i < count; i++) {
    nsIContent* content = newAnonymousItems[i].mContent;
    NS_ASSERTION(content, "null anonymous content?");
    NS_ASSERTION(!newAnonymousItems[i].mStyleContext, "Unexpected style context");
    NS_ASSERTION(newAnonymousItems[i].mChildren.IsEmpty(),
                 "This method is not currently used with frames that implement "
                 "nsIAnonymousContentCreator::CreateAnonymousContent to "
                 "output a list where the items have their own children");

    nsIFrame* newFrame = creator->CreateFrameFor(content);
    if (newFrame) {
      NS_ASSERTION(content->GetPrimaryFrame(),
                   "Content must have a primary frame now");
      aChildItems.AddChild(newFrame);
    }
    else {
      // create the frame and attach it to our frame
      ConstructFrame(aState, content, aParentFrame, aChildItems);
    }
  }

  return NS_OK;
}

static void
SetFlagsOnSubtree(nsIContent *aNode, uintptr_t aFlagsToSet)
{
#ifdef DEBUG
  // Make sure that the node passed to us doesn't have any XBL children
  {
    FlattenedChildIterator iter(aNode);
    NS_ASSERTION(!iter.XBLInvolved() || !iter.GetNextChild(),
                 "The node should not have any XBL children");
  }
#endif

  // Set the flag on the node itself
  aNode->SetFlags(aFlagsToSet);

  // Set the flag on all of its children recursively
  uint32_t count;
  nsIContent * const *children = aNode->GetChildArray(&count);

  for (uint32_t index = 0; index < count; ++index) {
    SetFlagsOnSubtree(children[index], aFlagsToSet);
  }
}

/**
 * This function takes a tree of nsIAnonymousContentCreator::ContentInfo
 * objects where the nsIContent nodes have just been created, and appends the
 * nsIContent children in the tree to their parent. The leaf nsIContent objects
 * are appended first to minimize the number of notifications that are sent
 * out (i.e. by appending as many descendants as posible while their parent is
 * not yet in the document tree).
 *
 * This function is used simply as a convenience so that implementations of
 * nsIAnonymousContentCreator::CreateAnonymousContent don't all have to have
 * their own code to connect the elements that they create.
 */
static void
ConnectAnonymousTreeDescendants(nsIContent* aParent,
                                nsTArray<nsIAnonymousContentCreator::ContentInfo>& aContent)
{
  uint32_t count = aContent.Length();
  for (uint32_t i=0; i < count; i++) {
    nsIContent* content = aContent[i].mContent;
    NS_ASSERTION(content, "null anonymous content?");

    ConnectAnonymousTreeDescendants(content, aContent[i].mChildren);

    aParent->AppendChildTo(content, false);
  }
}

nsresult
nsCSSFrameConstructor::GetAnonymousContent(nsIContent* aParent,
                                           nsIFrame* aParentFrame,
                                           nsTArray<nsIAnonymousContentCreator::ContentInfo>& aContent)
{
  nsIAnonymousContentCreator* creator = do_QueryFrame(aParentFrame);
  if (!creator)
    return NS_OK;

  nsresult rv = creator->CreateAnonymousContent(aContent);
  NS_ENSURE_SUCCESS(rv, rv);

  uint32_t count = aContent.Length();
  for (uint32_t i=0; i < count; i++) {
    // get our child's content and set its parent to our content
    nsIContent* content = aContent[i].mContent;
    NS_ASSERTION(content, "null anonymous content?");

    // least-surprise CSS binding until we do the SVG specified
    // cascading rules for <svg:use> - bug 265894
    if (aParentFrame->GetType() == nsGkAtoms::svgUseFrame) {
      content->SetFlags(NODE_IS_ANONYMOUS_ROOT);
    } else {
      content->SetIsNativeAnonymousRoot();
    }

    ConnectAnonymousTreeDescendants(content, aContent[i].mChildren);

    bool anonContentIsEditable = content->HasFlag(NODE_IS_EDITABLE);
    rv = content->BindToTree(mDocument, aParent, aParent, true);
    // If the anonymous content creator requested that the content should be
    // editable, honor its request.
    // We need to set the flag on the whole subtree, because existing
    // children's flags have already been set as part of the BindToTree operation.
    if (anonContentIsEditable) {
      NS_ASSERTION(aParentFrame->GetType() == nsGkAtoms::textInputFrame,
                   "We only expect this for anonymous content under a text control frame");
      SetFlagsOnSubtree(content, NODE_IS_EDITABLE);
    }
    if (NS_FAILED(rv)) {
      content->UnbindFromTree();
      return rv;
    }
  }

  return NS_OK;
}

static
bool IsXULDisplayType(const nsStyleDisplay* aDisplay)
{
  return (aDisplay->mDisplay == NS_STYLE_DISPLAY_INLINE_BOX || 
#ifdef MOZ_XUL
          aDisplay->mDisplay == NS_STYLE_DISPLAY_INLINE_GRID || 
          aDisplay->mDisplay == NS_STYLE_DISPLAY_INLINE_STACK ||
#endif
          aDisplay->mDisplay == NS_STYLE_DISPLAY_BOX
#ifdef MOZ_XUL
          || aDisplay->mDisplay == NS_STYLE_DISPLAY_GRID ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_STACK ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_GRID_GROUP ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_GRID_LINE ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_DECK ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_POPUP ||
          aDisplay->mDisplay == NS_STYLE_DISPLAY_GROUPBOX
#endif
          );
}


// XUL frames are not allowed to be out of flow.
#define SIMPLE_XUL_FCDATA(_func)                                        \
  FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW | FCDATA_SKIP_ABSPOS_PUSH,    \
              _func)
#define SCROLLABLE_XUL_FCDATA(_func)                                    \
  FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW | FCDATA_SKIP_ABSPOS_PUSH |   \
              FCDATA_MAY_NEED_SCROLLFRAME, _func)
// .. but we allow some XUL frames to be _containers_ for out-of-flow content
// (This is the same as SCROLLABLE_XUL_FCDATA, but w/o FCDATA_SKIP_ABSPOS_PUSH)
#define SCROLLABLE_ABSPOS_CONTAINER_XUL_FCDATA(_func)                   \
  FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW |                             \
              FCDATA_MAY_NEED_SCROLLFRAME, _func)

#define SIMPLE_XUL_CREATE(_tag, _func)            \
  { &nsGkAtoms::_tag, SIMPLE_XUL_FCDATA(_func) }
#define SCROLLABLE_XUL_CREATE(_tag, _func)            \
  { &nsGkAtoms::_tag, SCROLLABLE_XUL_FCDATA(_func) }
#define SIMPLE_XUL_INT_CREATE(_int, _func)      \
  { _int, SIMPLE_XUL_FCDATA(_func) }
#define SCROLLABLE_XUL_INT_CREATE(_int, _func)                          \
  { _int, SCROLLABLE_XUL_FCDATA(_func) }
#define SCROLLABLE_ABSPOS_CONTAINER_XUL_INT_CREATE(_int, _func)         \
  { _int, SCROLLABLE_ABSPOS_CONTAINER_XUL_FCDATA(_func) }

static
nsIFrame* NS_NewGridBoxFrame(nsIPresShell* aPresShell,
                             nsStyleContext* aStyleContext)
{
  nsCOMPtr<nsBoxLayout> layout;
  NS_NewGridLayout2(aPresShell, getter_AddRefs(layout));
  return NS_NewBoxFrame(aPresShell, aStyleContext, false, layout);
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULTagData(Element* aElement,
                                      nsIAtom* aTag,
                                      int32_t aNameSpaceID,
                                      nsStyleContext* aStyleContext)
{
  if (aNameSpaceID != kNameSpaceID_XUL) {
    return nullptr;
  }

  static const FrameConstructionDataByTag sXULTagData[] = {
#ifdef MOZ_XUL
    SCROLLABLE_XUL_CREATE(button, NS_NewButtonBoxFrame),
    SCROLLABLE_XUL_CREATE(checkbox, NS_NewButtonBoxFrame),
    SCROLLABLE_XUL_CREATE(radio, NS_NewButtonBoxFrame),
    SCROLLABLE_XUL_CREATE(autorepeatbutton, NS_NewAutoRepeatBoxFrame),
    SCROLLABLE_XUL_CREATE(titlebar, NS_NewTitleBarFrame),
    SCROLLABLE_XUL_CREATE(resizer, NS_NewResizerFrame),
    SIMPLE_XUL_CREATE(image, NS_NewImageBoxFrame),
    SIMPLE_XUL_CREATE(spring, NS_NewLeafBoxFrame),
    SIMPLE_XUL_CREATE(spacer, NS_NewLeafBoxFrame),
    SIMPLE_XUL_CREATE(treechildren, NS_NewTreeBodyFrame),
    SIMPLE_XUL_CREATE(treecol, NS_NewTreeColFrame),
    SIMPLE_XUL_CREATE(text, NS_NewTextBoxFrame),
    SIMPLE_TAG_CHAIN(label, nsCSSFrameConstructor::FindXULLabelData),
    SIMPLE_TAG_CHAIN(description, nsCSSFrameConstructor::FindXULDescriptionData),
    SIMPLE_XUL_CREATE(menu, NS_NewMenuFrame),
    SIMPLE_XUL_CREATE(menubutton, NS_NewMenuFrame),
    SIMPLE_XUL_CREATE(menuitem, NS_NewMenuItemFrame),
#ifdef XP_MACOSX
    SIMPLE_TAG_CHAIN(menubar, nsCSSFrameConstructor::FindXULMenubarData),
#else
    SIMPLE_XUL_CREATE(menubar, NS_NewMenuBarFrame),
#endif /* XP_MACOSX */
    SIMPLE_TAG_CHAIN(popupgroup, nsCSSFrameConstructor::FindPopupGroupData),
    SIMPLE_XUL_CREATE(iframe, NS_NewSubDocumentFrame),
    SIMPLE_XUL_CREATE(editor, NS_NewSubDocumentFrame),
    SIMPLE_XUL_CREATE(browser, NS_NewSubDocumentFrame),
    SIMPLE_XUL_CREATE(progressmeter, NS_NewProgressMeterFrame),
    SIMPLE_XUL_CREATE(splitter, NS_NewSplitterFrame),
    SIMPLE_TAG_CHAIN(listboxbody,
                     nsCSSFrameConstructor::FindXULListBoxBodyData),
    SIMPLE_TAG_CHAIN(listitem, nsCSSFrameConstructor::FindXULListItemData),
#endif /* MOZ_XUL */
    SIMPLE_XUL_CREATE(slider, NS_NewSliderFrame),
    SIMPLE_XUL_CREATE(scrollbar, NS_NewScrollbarFrame),
    SIMPLE_XUL_CREATE(scrollbarbutton, NS_NewScrollbarButtonFrame)
};

  return FindDataByTag(aTag, aElement, aStyleContext, sXULTagData,
                       ArrayLength(sXULTagData));
}

#ifdef MOZ_XUL
/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindPopupGroupData(Element* aElement,
                                          nsStyleContext* /* unused */)
{
  if (!aElement->IsRootOfNativeAnonymousSubtree()) {
    return nullptr;
  }

  static const FrameConstructionData sPopupSetData =
    SIMPLE_XUL_FCDATA(NS_NewPopupSetFrame);
  return &sPopupSetData;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData
nsCSSFrameConstructor::sXULTextBoxData = SIMPLE_XUL_FCDATA(NS_NewTextBoxFrame);

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULLabelData(Element* aElement,
                                        nsStyleContext* /* unused */)
{
  if (aElement->HasAttr(kNameSpaceID_None, nsGkAtoms::value)) {
    return &sXULTextBoxData;
  }

  static const FrameConstructionData sLabelData =
    SIMPLE_XUL_FCDATA(NS_NewXULLabelFrame);
  return &sLabelData;
}

static nsIFrame*
NS_NewXULDescriptionFrame(nsIPresShell* aPresShell, nsStyleContext *aContext)
{
  // XXXbz do we really need to set those flags?  If the parent is not
  // a block we'll get them anyway, and if it is, do we want them?
  return NS_NewBlockFrame(aPresShell, aContext,
                          NS_BLOCK_FLOAT_MGR | NS_BLOCK_MARGIN_ROOT);
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULDescriptionData(Element* aElement,
                                              nsStyleContext* /* unused */)
{
  if (aElement->HasAttr(kNameSpaceID_None, nsGkAtoms::value)) {
    return &sXULTextBoxData;
  }

  static const FrameConstructionData sDescriptionData =
    SIMPLE_XUL_FCDATA(NS_NewXULDescriptionFrame);
  return &sDescriptionData;
}

#ifdef XP_MACOSX
/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULMenubarData(Element* aElement,
                                          nsStyleContext* aStyleContext)
{
  nsCOMPtr<nsISupports> container =
    aStyleContext->PresContext()->GetContainer();
  if (container) {
    nsCOMPtr<nsIDocShellTreeItem> treeItem(do_QueryInterface(container));
    if (treeItem) {
      int32_t type;
      treeItem->GetItemType(&type);
      if (nsIDocShellTreeItem::typeChrome == type) {
        nsCOMPtr<nsIDocShellTreeItem> parent;
        treeItem->GetParent(getter_AddRefs(parent));
        if (!parent) {
          // This is the root.  Suppress the menubar, since on Mac
          // window menus are not attached to the window.
          static const FrameConstructionData sSuppressData = SUPPRESS_FCDATA();
          return &sSuppressData;
        }
      }
    }
  }

  static const FrameConstructionData sMenubarData =
    SIMPLE_XUL_FCDATA(NS_NewMenuBarFrame);
  return &sMenubarData;
}
#endif /* XP_MACOSX */

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULListBoxBodyData(Element* aElement,
                                              nsStyleContext* aStyleContext)
{
  if (aStyleContext->StyleDisplay()->mDisplay !=
        NS_STYLE_DISPLAY_GRID_GROUP) {
    return nullptr;
  }

  static const FrameConstructionData sListBoxBodyData =
    SCROLLABLE_XUL_FCDATA(NS_NewListBoxBodyFrame);
  return &sListBoxBodyData;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULListItemData(Element* aElement,
                                           nsStyleContext* aStyleContext)
{
  if (aStyleContext->StyleDisplay()->mDisplay !=
        NS_STYLE_DISPLAY_GRID_LINE) {
    return nullptr;
  }

  static const FrameConstructionData sListItemData =
    SCROLLABLE_XUL_FCDATA(NS_NewListItemFrame);
  return &sListItemData;
}

#endif /* MOZ_XUL */

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindXULDisplayData(const nsStyleDisplay* aDisplay,
                                          Element* aElement,
                                          nsStyleContext* aStyleContext)
{
  static const FrameConstructionDataByInt sXULDisplayData[] = {
    SCROLLABLE_ABSPOS_CONTAINER_XUL_INT_CREATE(NS_STYLE_DISPLAY_INLINE_BOX,
                                               NS_NewBoxFrame),
    SCROLLABLE_ABSPOS_CONTAINER_XUL_INT_CREATE(NS_STYLE_DISPLAY_BOX,
                                               NS_NewBoxFrame),
#ifdef MOZ_XUL
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_INLINE_GRID, NS_NewGridBoxFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_GRID, NS_NewGridBoxFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_GRID_GROUP,
                              NS_NewGridRowGroupFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_GRID_LINE,
                              NS_NewGridRowLeafFrame),
    SIMPLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_DECK, NS_NewDeckFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_GROUPBOX, NS_NewGroupBoxFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_INLINE_STACK, NS_NewStackFrame),
    SCROLLABLE_XUL_INT_CREATE(NS_STYLE_DISPLAY_STACK, NS_NewStackFrame),
    { NS_STYLE_DISPLAY_POPUP,
      FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW | FCDATA_IS_POPUP |
                  FCDATA_SKIP_ABSPOS_PUSH, NS_NewMenuPopupFrame) }
#endif /* MOZ_XUL */
  };

  // Processing by display here:
  return FindDataByInt(aDisplay->mDisplay, aElement, aStyleContext,
                       sXULDisplayData, ArrayLength(sXULDisplayData));
}

already_AddRefed<nsStyleContext>
nsCSSFrameConstructor::BeginBuildingScrollFrame(nsFrameConstructorState& aState,
                                                nsIContent*              aContent,
                                                nsStyleContext*          aContentStyle,
                                                nsIFrame*                aParentFrame,
                                                nsIAtom*                 aScrolledPseudo,
                                                bool                     aIsRoot,
                                                nsIFrame*&               aNewFrame)
{
  nsIFrame* gfxScrollFrame = aNewFrame;

  nsFrameItems anonymousItems;

  nsRefPtr<nsStyleContext> contentStyle = aContentStyle;

  if (!gfxScrollFrame) {
    // Build a XULScrollFrame when the child is a box, otherwise an
    // HTMLScrollFrame
    // XXXbz this is the lone remaining consumer of IsXULDisplayType.
    // I wonder whether we can eliminate that somehow.
    const nsStyleDisplay* displayStyle = aContentStyle->StyleDisplay();
    if (IsXULDisplayType(displayStyle)) {
      gfxScrollFrame = NS_NewXULScrollFrame(mPresShell, contentStyle, aIsRoot,
          displayStyle->mDisplay == NS_STYLE_DISPLAY_STACK ||
          displayStyle->mDisplay == NS_STYLE_DISPLAY_INLINE_STACK);
    } else {
      gfxScrollFrame = NS_NewHTMLScrollFrame(mPresShell, contentStyle, aIsRoot);
    }

    InitAndRestoreFrame(aState, aContent, aParentFrame, gfxScrollFrame);
  }

  // if there are any anonymous children for the scroll frame, create
  // frames for them.
  // Pass a null pending binding: we don't care how constructors for any of
  // this anonymous content order with anything else.  It's never been
  // consistent anyway.
  CreateAnonymousFrames(aState, aContent, gfxScrollFrame, nullptr,
                        anonymousItems);

  aNewFrame = gfxScrollFrame;

  // we used the style that was passed in. So resolve another one.
  nsStyleSet *styleSet = mPresShell->StyleSet();
  nsRefPtr<nsStyleContext> scrolledChildStyle =
    styleSet->ResolveAnonymousBoxStyle(aScrolledPseudo, contentStyle);

  if (gfxScrollFrame) {
     gfxScrollFrame->SetInitialChildList(kPrincipalList, anonymousItems);
  }

  return scrolledChildStyle.forget();
}

void
nsCSSFrameConstructor::FinishBuildingScrollFrame(nsIFrame* aScrollFrame,
                                                 nsIFrame* aScrolledFrame)
{
  nsFrameList scrolled(aScrolledFrame, aScrolledFrame);
  aScrollFrame->AppendFrames(kPrincipalList, scrolled);
}


/**
 * Called to wrap a gfx scrollframe around a frame. The hierarchy will look like this
 *
 * ------- for gfx scrollbars ------
 *
 *
 *            ScrollFrame
 *                 ^
 *                 |
 *               Frame (scrolled frame you passed in)
 *
 *
 *-----------------------------------
 * LEGEND:
 * 
 * ScrollFrame: This is a frame that manages gfx cross platform frame based scrollbars.
 *
 * @param aContent the content node of the child to wrap.
 * @param aScrolledFrame The frame of the content to wrap. This should not be
 *                    Initialized. This method will initialize it with a scrolled pseudo
 *                    and no nsIContent. The content will be attached to the scrollframe 
 *                    returned.
 * @param aContentStyle the style context that has already been resolved for the content being passed in.
 *
 * @param aParentFrame The parent to attach the scroll frame to
 *
 * @param aNewFrame The new scrollframe or gfx scrollframe that we create. It will contain the
 *                  scrolled frame you passed in. (returned)
 *                  If this is not null, we'll just use it
 * @param aScrolledContentStyle the style that was resolved for the scrolled frame. (returned)
 */
nsresult
nsCSSFrameConstructor::BuildScrollFrame(nsFrameConstructorState& aState,
                                        nsIContent*              aContent,
                                        nsStyleContext*          aContentStyle,
                                        nsIFrame*                aScrolledFrame,
                                        nsIFrame*                aParentFrame,
                                        nsIFrame*&               aNewFrame)
{
    nsRefPtr<nsStyleContext> scrolledContentStyle =
      BeginBuildingScrollFrame(aState, aContent, aContentStyle, aParentFrame,
                               nsCSSAnonBoxes::scrolledContent,
                               false, aNewFrame);
    
    aScrolledFrame->SetStyleContextWithoutNotification(scrolledContentStyle);
    InitAndRestoreFrame(aState, aContent, aNewFrame, aScrolledFrame);

    FinishBuildingScrollFrame(aNewFrame, aScrolledFrame);
    return NS_OK;
}

const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindDisplayData(const nsStyleDisplay* aDisplay,
                                       Element* aElement,
                                       nsIFrame* aParentFrame,
                                       nsStyleContext* aStyleContext)
{
  PR_STATIC_ASSERT(eParentTypeCount < (1 << (32 - FCDATA_PARENT_TYPE_OFFSET)));

  // The style system ensures that floated and positioned frames are
  // block-level.
  NS_ASSERTION(!(aDisplay->IsFloatingStyle() ||
                 aDisplay->IsAbsolutelyPositionedStyle()) ||
               aDisplay->IsBlockOutsideStyle(),
               "Style system did not apply CSS2.1 section 9.7 fixups");

  // If this is "body", try propagating its scroll style to the viewport
  // Note that we need to do this even if the body is NOT scrollable;
  // it might have dynamically changed from scrollable to not scrollable,
  // and that might need to be propagated.
  // XXXbz is this the right place to do this?  If this code moves,
  // make this function static.
  bool propagatedScrollToViewport = false;
  if (aElement->IsHTML(nsGkAtoms::body)) {
    propagatedScrollToViewport =
      PropagateScrollToViewport() == aElement;
  }

  NS_ASSERTION(!propagatedScrollToViewport ||
               !mPresShell->GetPresContext()->IsPaginated(),
               "Shouldn't propagate scroll in paginated contexts");

  // If the frame is a block-level frame and is scrollable, then wrap it in a
  // scroll frame.
  // XXX Ignore tables for the time being
  // XXXbz it would be nice to combine this with the other block
  // case... Think about how do do this?
  if (aDisplay->IsBlockInsideStyle() &&
      aDisplay->IsScrollableOverflow() &&
      !propagatedScrollToViewport) {
    // Except we don't want to do that for paginated contexts for
    // frames that are block-outside and aren't frames for native
    // anonymous stuff.
    if (mPresShell->GetPresContext()->IsPaginated() &&
        aDisplay->IsBlockOutsideStyle() &&
        !aElement->IsInNativeAnonymousSubtree()) {
      static const FrameConstructionData sForcedNonScrollableBlockData =
        FULL_CTOR_FCDATA(FCDATA_FORCED_NON_SCROLLABLE_BLOCK,
                         &nsCSSFrameConstructor::ConstructNonScrollableBlock);
      return &sForcedNonScrollableBlockData;
    }

    static const FrameConstructionData sScrollableBlockData =
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructScrollableBlock);
    return &sScrollableBlockData;
  }

  // Handle various non-scrollable blocks
  if (aDisplay->IsBlockInsideStyle()) {
    static const FrameConstructionData sNonScrollableBlockData =
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructNonScrollableBlock);
    return &sNonScrollableBlockData;
  }

  static const FrameConstructionDataByInt sDisplayData[] = {
    // To keep the hash table small don't add inline frames (they're
    // typically things like FONT and B), because we can quickly
    // find them if we need to.
    // XXXbz the "quickly" part is a bald-faced lie!
    { NS_STYLE_DISPLAY_INLINE,
      FULL_CTOR_FCDATA(FCDATA_IS_INLINE | FCDATA_IS_LINE_PARTICIPANT,
                       &nsCSSFrameConstructor::ConstructInline) },
    { NS_STYLE_DISPLAY_FLEX,
      FCDATA_DECL(FCDATA_MAY_NEED_SCROLLFRAME, NS_NewFlexContainerFrame) },
    { NS_STYLE_DISPLAY_INLINE_FLEX,
      FCDATA_DECL(FCDATA_MAY_NEED_SCROLLFRAME, NS_NewFlexContainerFrame) },
    { NS_STYLE_DISPLAY_TABLE,
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructTable) },
    { NS_STYLE_DISPLAY_INLINE_TABLE,
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructTable) },
    // NOTE: In the unlikely event that we add another table-part here that has
    // a desired-parent-type (& hence triggers table fixup), we'll need to also
    // update the flexbox chunk in nsStyleContext::ApplyStyleFixups().
    { NS_STYLE_DISPLAY_TABLE_CAPTION,
      FCDATA_DECL(FCDATA_IS_TABLE_PART | FCDATA_ALLOW_BLOCK_STYLES |
                  FCDATA_DISALLOW_OUT_OF_FLOW | FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeTable),
                  NS_NewTableCaptionFrame) },
    { NS_STYLE_DISPLAY_TABLE_ROW_GROUP,
      FCDATA_DECL(FCDATA_IS_TABLE_PART | FCDATA_DISALLOW_OUT_OF_FLOW |
                  FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeTable),
                  NS_NewTableRowGroupFrame) },
    { NS_STYLE_DISPLAY_TABLE_HEADER_GROUP,
      FCDATA_DECL(FCDATA_IS_TABLE_PART | FCDATA_DISALLOW_OUT_OF_FLOW |
                  FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeTable),
                  NS_NewTableRowGroupFrame) },
    { NS_STYLE_DISPLAY_TABLE_FOOTER_GROUP,
      FCDATA_DECL(FCDATA_IS_TABLE_PART | FCDATA_DISALLOW_OUT_OF_FLOW |
                  FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeTable),
                  NS_NewTableRowGroupFrame) },
    { NS_STYLE_DISPLAY_TABLE_COLUMN_GROUP,
      FCDATA_DECL(FCDATA_IS_TABLE_PART | FCDATA_DISALLOW_OUT_OF_FLOW |
                  FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeTable),
                  NS_NewTableColGroupFrame) },
    { NS_STYLE_DISPLAY_TABLE_COLUMN,
      FULL_CTOR_FCDATA(FCDATA_IS_TABLE_PART |
                       FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeColGroup),
                       &nsCSSFrameConstructor::ConstructTableCol) },
    { NS_STYLE_DISPLAY_TABLE_ROW,
      FULL_CTOR_FCDATA(FCDATA_IS_TABLE_PART |
                       FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeRowGroup),
                       &nsCSSFrameConstructor::ConstructTableRow) },
    { NS_STYLE_DISPLAY_TABLE_CELL,
      FULL_CTOR_FCDATA(FCDATA_IS_TABLE_PART |
                       FCDATA_DESIRED_PARENT_TYPE_TO_BITS(eTypeRow),
                       &nsCSSFrameConstructor::ConstructTableCell) }
  };

  return FindDataByInt(aDisplay->mDisplay,
                       aElement, aStyleContext, sDisplayData,
                       ArrayLength(sDisplayData));
}

nsIFrame*
nsCSSFrameConstructor::ConstructScrollableBlock(nsFrameConstructorState& aState,
                                                FrameConstructionItem&   aItem,
                                                nsIFrame*                aParentFrame,
                                                const nsStyleDisplay*    aDisplay,
                                                nsFrameItems&            aFrameItems)
{
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;

  nsIFrame* newFrame = nullptr;
  nsRefPtr<nsStyleContext> scrolledContentStyle
    = BeginBuildingScrollFrame(aState, content, styleContext,
                               aState.GetGeometricParent(aDisplay, aParentFrame),
                               nsCSSAnonBoxes::scrolledContent,
                               false, newFrame);

  // Create our block frame
  // pass a temporary stylecontext, the correct one will be set later
  nsIFrame* scrolledFrame =
    NS_NewBlockFormattingContext(mPresShell, styleContext);

  // Make sure to AddChild before we call ConstructBlock so that we
  // end up before our descendants in fixed-pos lists as needed.
  aState.AddChild(newFrame, aFrameItems, content, styleContext, aParentFrame);

  nsFrameItems blockItem;
  ConstructBlock(aState, scrolledContentStyle->StyleDisplay(), content,
                 newFrame, newFrame, scrolledContentStyle,
                 &scrolledFrame, blockItem,
                 aDisplay->IsPositioned(newFrame) ? newFrame : nullptr,
                 aItem.mPendingBinding);

  NS_ASSERTION(blockItem.FirstChild() == scrolledFrame,
               "Scrollframe's frameItems should be exactly the scrolled frame");
  FinishBuildingScrollFrame(newFrame, scrolledFrame);

  return newFrame;
}

nsIFrame*
nsCSSFrameConstructor::ConstructNonScrollableBlock(nsFrameConstructorState& aState,
                                                   FrameConstructionItem&   aItem,
                                                   nsIFrame*                aParentFrame,
                                                   const nsStyleDisplay*    aDisplay,
                                                   nsFrameItems&            aFrameItems)
{
  nsStyleContext* const styleContext = aItem.mStyleContext;

  // We want a block formatting context root in paginated contexts for
  // every block that would be scrollable in a non-paginated context.
  // We mark our blocks with a bit here if this condition is true, so
  // we can check it later in nsFrame::ApplyPaginatedOverflowClipping.
  bool clipPaginatedOverflow =
    (aItem.mFCData->mBits & FCDATA_FORCED_NON_SCROLLABLE_BLOCK) != 0;
  nsIFrame* newFrame;
  if ((aDisplay->IsAbsolutelyPositionedStyle() ||
       aDisplay->IsFloatingStyle() ||
       NS_STYLE_DISPLAY_INLINE_BLOCK == aDisplay->mDisplay ||
       clipPaginatedOverflow) &&
      !aParentFrame->IsSVGText()) {
    newFrame = NS_NewBlockFormattingContext(mPresShell, styleContext);
    if (clipPaginatedOverflow) {
      newFrame->AddStateBits(NS_BLOCK_CLIP_PAGINATED_OVERFLOW);
    }
  } else {
    newFrame = NS_NewBlockFrame(mPresShell, styleContext);
  }

  ConstructBlock(aState, aDisplay, aItem.mContent,
                 aState.GetGeometricParent(aDisplay, aParentFrame),
                 aParentFrame, styleContext, &newFrame,
                 aFrameItems,
                 aDisplay->IsPositioned(newFrame) ? newFrame : nullptr,
                 aItem.mPendingBinding);
  return newFrame;
}


void
nsCSSFrameConstructor::InitAndRestoreFrame(const nsFrameConstructorState& aState,
                                           nsIContent*              aContent,
                                           nsIFrame*                aParentFrame,
                                           nsIFrame*                aNewFrame,
                                           bool                     aAllowCounters)
{
  NS_PRECONDITION(mUpdateCount != 0,
                  "Should be in an update while creating frames");
  
  MOZ_ASSERT(aNewFrame, "Null frame cannot be initialized");

  // Initialize the frame
  aNewFrame->Init(aContent, aParentFrame, nullptr);
  aNewFrame->AddStateBits(aState.mAdditionalStateBits);

  if (aState.mFrameState) {
    // Restore frame state for just the newly created frame.
    RestoreFrameStateFor(aNewFrame, aState.mFrameState);
  }

  if (aAllowCounters &&
      mCounterManager.AddCounterResetsAndIncrements(aNewFrame)) {
    CountersDirty();
  }
}

already_AddRefed<nsStyleContext>
nsCSSFrameConstructor::ResolveStyleContext(nsIFrame*         aParentFrame,
                                           nsIContent*       aContent,
                                           nsFrameConstructorState* aState)
{
  nsStyleContext* parentStyleContext = nullptr;
  NS_ASSERTION(aContent->GetParent(), "Must have parent here");

  aParentFrame = nsFrame::CorrectStyleParentFrame(aParentFrame, nullptr);

  if (aParentFrame) {
    // Resolve the style context based on the content object and the parent
    // style context
    parentStyleContext = aParentFrame->StyleContext();
  } else {
    // Perhaps aParentFrame is a canvasFrame and we're replicating
    // fixed-pos frames.
    // XXX should we create a way to tell ConstructFrame which style
    // context to use, and pass it the style context for the
    // previous page's fixed-pos frame?
  }

  return ResolveStyleContext(parentStyleContext, aContent, aState);
}

already_AddRefed<nsStyleContext>
nsCSSFrameConstructor::ResolveStyleContext(nsStyleContext* aParentStyleContext,
                                           nsIContent* aContent,
                                           nsFrameConstructorState* aState)
{
  nsStyleSet *styleSet = mPresShell->StyleSet();
  aContent->OwnerDoc()->FlushPendingLinkUpdates();
  
  if (aContent->IsElement()) {
    if (aState) {
      return styleSet->ResolveStyleFor(aContent->AsElement(),
                                       aParentStyleContext,
                                       aState->mTreeMatchContext);
    }
    return styleSet->ResolveStyleFor(aContent->AsElement(), aParentStyleContext);

  }

  NS_ASSERTION(aContent->IsNodeOfType(nsINode::eTEXT),
               "shouldn't waste time creating style contexts for "
               "comments and processing instructions");

  return styleSet->ResolveStyleForNonElement(aParentStyleContext);
}

// MathML Mod - RBS
void
nsCSSFrameConstructor::FlushAccumulatedBlock(nsFrameConstructorState& aState,
                                             nsIContent* aContent,
                                             nsIFrame* aParentFrame,
                                             nsFrameItems& aBlockItems,
                                             nsFrameItems& aNewItems)
{
  if (aBlockItems.IsEmpty()) {
    // Nothing to do
    return;
  }

  nsIAtom* anonPseudo = nsCSSAnonBoxes::mozMathMLAnonymousBlock;

  nsStyleContext* parentContext =
    nsFrame::CorrectStyleParentFrame(aParentFrame,
                                     anonPseudo)->StyleContext();
  nsStyleSet* styleSet = mPresShell->StyleSet();
  nsRefPtr<nsStyleContext> blockContext;
  blockContext = styleSet->
    ResolveAnonymousBoxStyle(anonPseudo, parentContext);


  // then, create a block frame that will wrap the child frames. Make it a
  // MathML frame so that Get(Absolute/Float)ContainingBlockFor know that this
  // is not a suitable block.
  nsIFrame* blockFrame =
      NS_NewMathMLmathBlockFrame(mPresShell, blockContext,
                                 NS_BLOCK_FLOAT_MGR | NS_BLOCK_MARGIN_ROOT);

  InitAndRestoreFrame(aState, aContent, aParentFrame, blockFrame);
  ReparentFrames(this, blockFrame, aBlockItems);
  // abs-pos and floats are disabled in MathML children so we don't have to
  // worry about messing up those.
  blockFrame->SetInitialChildList(kPrincipalList, aBlockItems);
  NS_ASSERTION(aBlockItems.IsEmpty(), "What happened?");
  aBlockItems.Clear();
  aNewItems.AddChild(blockFrame);
}

// Only <math> elements can be floated or positioned.  All other MathML
// should be in-flow.
#define SIMPLE_MATHML_CREATE(_tag, _func)                               \
  { &nsGkAtoms::_tag,                                                   \
      FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW |                         \
                  FCDATA_FORCE_NULL_ABSPOS_CONTAINER |                  \
                  FCDATA_WRAP_KIDS_IN_BLOCKS, _func) }

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindMathMLData(Element* aElement,
                                      nsIAtom* aTag,
                                      int32_t aNameSpaceID,
                                      nsStyleContext* aStyleContext)
{
  // Make sure that we remain confined in the MathML world
  if (aNameSpaceID != kNameSpaceID_MathML) 
    return nullptr;

  // Handle <math> specially, because it sometimes produces inlines
  if (aTag == nsGkAtoms::math) {
    // This needs to match the test in EnsureBlockDisplay in
    // nsRuleNode.cpp.  Though the behavior here for the display:table
    // case is pretty weird...
    if (aStyleContext->StyleDisplay()->IsBlockOutsideStyle()) {
      static const FrameConstructionData sBlockMathData =
        FCDATA_DECL(FCDATA_FORCE_NULL_ABSPOS_CONTAINER |
                    FCDATA_WRAP_KIDS_IN_BLOCKS,
                    NS_CreateNewMathMLmathBlockFrame);
      return &sBlockMathData;
    }

    static const FrameConstructionData sInlineMathData =
      FCDATA_DECL(FCDATA_FORCE_NULL_ABSPOS_CONTAINER |
                  FCDATA_IS_LINE_PARTICIPANT |
                  FCDATA_WRAP_KIDS_IN_BLOCKS,
                  NS_NewMathMLmathInlineFrame);
    return &sInlineMathData;
  }
      

  static const FrameConstructionDataByTag sMathMLData[] = {
    SIMPLE_MATHML_CREATE(annotation_, NS_NewMathMLTokenFrame),
    SIMPLE_MATHML_CREATE(annotation_xml_, NS_NewMathMLmrowFrame),
    SIMPLE_MATHML_CREATE(mi_, NS_NewMathMLTokenFrame),
    SIMPLE_MATHML_CREATE(mn_, NS_NewMathMLTokenFrame),
    SIMPLE_MATHML_CREATE(ms_, NS_NewMathMLTokenFrame),
    SIMPLE_MATHML_CREATE(mtext_, NS_NewMathMLTokenFrame),
    SIMPLE_MATHML_CREATE(mo_, NS_NewMathMLmoFrame),
    SIMPLE_MATHML_CREATE(mfrac_, NS_NewMathMLmfracFrame),
    SIMPLE_MATHML_CREATE(msup_, NS_NewMathMLmmultiscriptsFrame),
    SIMPLE_MATHML_CREATE(msub_, NS_NewMathMLmmultiscriptsFrame),
    SIMPLE_MATHML_CREATE(msubsup_, NS_NewMathMLmmultiscriptsFrame),
    SIMPLE_MATHML_CREATE(munder_, NS_NewMathMLmunderoverFrame),
    SIMPLE_MATHML_CREATE(mover_, NS_NewMathMLmunderoverFrame),
    SIMPLE_MATHML_CREATE(munderover_, NS_NewMathMLmunderoverFrame),
    SIMPLE_MATHML_CREATE(mphantom_, NS_NewMathMLmphantomFrame),
    SIMPLE_MATHML_CREATE(mpadded_, NS_NewMathMLmpaddedFrame),
    SIMPLE_MATHML_CREATE(mspace_, NS_NewMathMLmspaceFrame),
    SIMPLE_MATHML_CREATE(none, NS_NewMathMLmspaceFrame),
    SIMPLE_MATHML_CREATE(mprescripts_, NS_NewMathMLmspaceFrame),
    SIMPLE_MATHML_CREATE(mfenced_, NS_NewMathMLmfencedFrame),
    SIMPLE_MATHML_CREATE(mmultiscripts_, NS_NewMathMLmmultiscriptsFrame),
    SIMPLE_MATHML_CREATE(mstyle_, NS_NewMathMLmstyleFrame),
    SIMPLE_MATHML_CREATE(msqrt_, NS_NewMathMLmsqrtFrame),
    SIMPLE_MATHML_CREATE(mroot_, NS_NewMathMLmrootFrame),
    SIMPLE_MATHML_CREATE(maction_, NS_NewMathMLmactionFrame),
    SIMPLE_MATHML_CREATE(mrow_, NS_NewMathMLmrowFrame),
    SIMPLE_MATHML_CREATE(merror_, NS_NewMathMLmrowFrame),
    SIMPLE_MATHML_CREATE(menclose_, NS_NewMathMLmencloseFrame),
    SIMPLE_MATHML_CREATE(semantics_, NS_NewMathMLsemanticsFrame)
  };

  return FindDataByTag(aTag, aElement, aStyleContext, sMathMLData,
                       ArrayLength(sMathMLData));
}


nsIFrame*
nsCSSFrameConstructor::ConstructFrameWithAnonymousChild(
                                   nsFrameConstructorState& aState,
                                   FrameConstructionItem&   aItem,
                                   nsIFrame*                aParentFrame,
                                   const nsStyleDisplay*    aDisplay,
                                   nsFrameItems&            aFrameItems,
                                   FrameCreationFunc        aConstructor,
                                   FrameCreationFunc        aInnerConstructor,
                                   nsICSSAnonBoxPseudo*     aInnerPseudo,
                                   bool                     aCandidateRootFrame)
{
  nsIContent* const content = aItem.mContent;
  nsStyleContext* const styleContext = aItem.mStyleContext;

  // Create the outer frame:
  nsIFrame* newFrame = aConstructor(mPresShell, styleContext);

  InitAndRestoreFrame(aState, content,
                      aCandidateRootFrame ?
                        aState.GetGeometricParent(styleContext->StyleDisplay(),
                                                  aParentFrame) :
                        aParentFrame,
                      newFrame);

  // Create the pseudo SC for the anonymous wrapper child as a child of the SC:
  nsRefPtr<nsStyleContext> scForAnon;
  scForAnon = mPresShell->StyleSet()->
    ResolveAnonymousBoxStyle(aInnerPseudo, styleContext);

  // Create the anonymous inner wrapper frame
  nsIFrame* innerFrame = aInnerConstructor(mPresShell, scForAnon);

  InitAndRestoreFrame(aState, content, newFrame, innerFrame);

  // Put the newly created frames into the right child list
  SetInitialSingleChild(newFrame, innerFrame);

  aState.AddChild(newFrame, aFrameItems, content, styleContext, aParentFrame,
                  aCandidateRootFrame, aCandidateRootFrame);

  if (!mRootElementFrame && aCandidateRootFrame) {
    // The frame we're constructing will be the root element frame.
    // Set mRootElementFrame before processing children.
    mRootElementFrame = newFrame;
  }

  nsFrameItems childItems;

  // Process children
  NS_ASSERTION(aItem.mAnonChildren.IsEmpty(),
               "nsIAnonymousContentCreator::CreateAnonymousContent should not "
               "be implemented for frames for which we explicitly create an "
               "anonymous child to wrap its child frames");
  if (aItem.mFCData->mBits & FCDATA_USE_CHILD_ITEMS) {
    ConstructFramesFromItemList(aState, aItem.mChildItems,
                                innerFrame, childItems);
  } else {
    ProcessChildren(aState, content, styleContext, innerFrame,
                    true, childItems, false, aItem.mPendingBinding);
  }

  // Set the inner wrapper frame's initial primary list
  innerFrame->SetInitialChildList(kPrincipalList, childItems);

  return newFrame;
}

nsIFrame*
nsCSSFrameConstructor::ConstructOuterSVG(nsFrameConstructorState& aState,
                                         FrameConstructionItem&   aItem,
                                         nsIFrame*                aParentFrame,
                                         const nsStyleDisplay*    aDisplay,
                                         nsFrameItems&            aFrameItems)
{
  return ConstructFrameWithAnonymousChild(
      aState, aItem, aParentFrame, aDisplay, aFrameItems,
      NS_NewSVGOuterSVGFrame, NS_NewSVGOuterSVGAnonChildFrame,
      nsCSSAnonBoxes::mozSVGOuterSVGAnonChild, true);
}

nsIFrame*
nsCSSFrameConstructor::ConstructMarker(nsFrameConstructorState& aState,
                                       FrameConstructionItem&   aItem,
                                       nsIFrame*                aParentFrame,
                                       const nsStyleDisplay*    aDisplay,
                                       nsFrameItems&            aFrameItems)
{
  return ConstructFrameWithAnonymousChild(
      aState, aItem, aParentFrame, aDisplay, aFrameItems,
      NS_NewSVGMarkerFrame, NS_NewSVGMarkerAnonChildFrame,
      nsCSSAnonBoxes::mozSVGMarkerAnonChild, false);
}

// Only outer <svg> elements can be floated or positioned.  All other SVG
// should be in-flow.
#define SIMPLE_SVG_FCDATA(_func)                                        \
  FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW |                             \
              FCDATA_SKIP_ABSPOS_PUSH |                                 \
              FCDATA_DISALLOW_GENERATED_CONTENT,  _func)
#define SIMPLE_SVG_CREATE(_tag, _func)            \
  { &nsGkAtoms::_tag, SIMPLE_SVG_FCDATA(_func) }

static bool
IsFilterPrimitiveChildTag(const nsIAtom* aTag)
{
  return aTag == nsGkAtoms::feDistantLight ||
         aTag == nsGkAtoms::fePointLight ||
         aTag == nsGkAtoms::feSpotLight ||
         aTag == nsGkAtoms::feFuncR ||
         aTag == nsGkAtoms::feFuncG ||
         aTag == nsGkAtoms::feFuncB ||
         aTag == nsGkAtoms::feFuncA ||
         aTag == nsGkAtoms::feMergeNode;
}

/* static */
const nsCSSFrameConstructor::FrameConstructionData*
nsCSSFrameConstructor::FindSVGData(Element* aElement,
                                   nsIAtom* aTag,
                                   int32_t aNameSpaceID,
                                   nsIFrame* aParentFrame,
                                   bool aIsWithinSVGText,
                                   bool aAllowsTextPathChild,
                                   nsStyleContext* aStyleContext)
{
  if (aNameSpaceID != kNameSpaceID_SVG) {
    return nullptr;
  }

  static const FrameConstructionData sSuppressData = SUPPRESS_FCDATA();
  static const FrameConstructionData sContainerData =
    SIMPLE_SVG_FCDATA(NS_NewSVGContainerFrame);

  bool parentIsSVG = aIsWithinSVGText;
  nsIContent* parentContent =
    aParentFrame ? aParentFrame->GetContent() : nullptr;
  // XXXbz should this really be based on the XBL-resolved tag of the parent
  // frame's content?  Should it not be based on the type of the parent frame
  // (e.g. whether it's an SVG frame)?
  if (parentContent) {
    int32_t parentNSID;
    nsIAtom* parentTag =
      parentContent->OwnerDoc()->BindingManager()->
        ResolveTag(parentContent, &parentNSID);

    // It's not clear whether the SVG spec intends to allow any SVG
    // content within svg:foreignObject at all (SVG 1.1, section
    // 23.2), but if it does, it better be svg:svg.  So given that
    // we're allowing it, treat it as a non-SVG parent.
    parentIsSVG = parentNSID == kNameSpaceID_SVG &&
                  parentTag != nsGkAtoms::foreignObject;
  }

  if ((aTag != nsGkAtoms::svg && !parentIsSVG) ||
      (aTag == nsGkAtoms::desc || aTag == nsGkAtoms::title)) {
    // Sections 5.1 and G.4 of SVG 1.1 say that SVG elements other than
    // svg:svg not contained within svg:svg are incorrect, although they
    // don't seem to specify error handling.  Ignore them, since many of
    // our frame classes can't deal.  It *may* be that the document
    // should at that point be considered in error according to F.2, but
    // it's hard to tell.
    //
    // Style mutation can't change this situation, so don't bother
    // adding to the undisplayed content map.
    //
    // We don't currently handle any UI for desc/title
    return &sSuppressData;
  }

  // We don't need frames for animation elements
  if (aElement->IsNodeOfType(nsINode::eANIMATION)) {
    return &sSuppressData;
  }

  if (aTag == nsGkAtoms::svg && !parentIsSVG) {
    // We need outer <svg> elements to have an nsSVGOuterSVGFrame regardless
    // of whether they fail conditional processing attributes, since various
    // SVG frames assume that one exists.  We handle the non-rendering
    // of failing outer <svg> element contents like <switch> statements,
    // and do the PassesConditionalProcessingTests call in
    // nsSVGOuterSVGFrame::Init.
    static const FrameConstructionData sOuterSVGData =
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructOuterSVG);
    return &sOuterSVGData;
  }

  if (aTag == nsGkAtoms::marker) {
    static const FrameConstructionData sMarkerSVGData =
      FULL_CTOR_FCDATA(0, &nsCSSFrameConstructor::ConstructMarker);
    return &sMarkerSVGData;
  }

  nsCOMPtr<SVGTests> tests(do_QueryInterface(aElement));
  if (tests && !tests->PassesConditionalProcessingTests()) {
    // Elements with failing conditional processing attributes never get
    // rendered.  Note that this is not where we select which frame in a
    // <switch> to render!  That happens in nsSVGSwitchFrame::PaintSVG.
    return &sContainerData;
  }

  // Prevent bad frame types being children of filters or parents of filter
  // primitives.  If aParentFrame is null, we know that the frame that will
  // be created will be an nsInlineFrame, so it can never be a filter.
  bool parentIsFilter = aParentFrame &&
    aParentFrame->GetType() == nsGkAtoms::svgFilterFrame;
  bool filterPrimitive = aElement->IsNodeOfType(nsINode::eFILTER);
  if ((parentIsFilter && !filterPrimitive) ||
      (!parentIsFilter && filterPrimitive)) {
    return &sSuppressData;
  }

  // Prevent bad frame types being children of filter primitives or parents of
  // filter primitive children.  If aParentFrame is null, we know that the frame
  // that will be created will be an nsInlineFrame, so it can never be a filter
  // primitive.
  bool parentIsFEContainerFrame = aParentFrame &&
    aParentFrame->GetType() == nsGkAtoms::svgFEContainerFrame;
  if ((parentIsFEContainerFrame && !IsFilterPrimitiveChildTag(aTag)) ||
      (!parentIsFEContainerFrame && IsFilterPrimitiveChildTag(aTag))) {
    return &sSuppressData;
  }

  // Special cases for text/tspan/textPath, because the kind of frame
  // they get depends on the parent frame.  We ignore 'a' elements when
  // determining the parent, however.
  if (aIsWithinSVGText) {
    // If aIsWithinSVGText is true, then we know that the "SVG text uses
    // CSS frames" pref was true when this SVG fragment was first constructed.

    // We don't use ConstructInline because we want different behavior
    // for generated content.
    static const FrameConstructionData sTSpanData =
      FCDATA_DECL(FCDATA_DISALLOW_OUT_OF_FLOW |
                  FCDATA_SKIP_ABSPOS_PUSH |
                  FCDATA_DISALLOW_GENERATED_CONTENT |
                  FCDATA_IS_LINE_PARTICIPANT |
                  FCDATA_IS_INLINE |
                  FCDATA_USE_CHILD_ITEMS,
                  NS_NewInlineFrame);
    if (aTag == nsGkAtoms::textPath) {
      if (aAllowsTextPathChild) {
        return &sTSpanData;
      }
    } else if (aTag == nsGkAtoms::tspan ||
               aTag == nsGkAtoms::altGlyph ||
               aTag == nsGkAtoms::a) {
      return &sTSpanData;
    }
    return &sSuppressData;
  } else if (NS_SVGTextCSSFramesEnabled()) {
    if (aTag == nsGkAtoms::text) {
      static const FrameConstructionData sTextData =
        FCDATA_WITH_WRAPPING_BLOCK(FCDATA_DISALLOW_OUT_OF_FLOW |
                                   FCDATA_ALLOW_BLOCK_STYLES,
                                   NS_NewSVGTextFrame2,
                                   nsCSSAnonBoxes::mozSVGText);
      return &sTextData;
    } else if (aTag == nsGkAtoms::tspan ||
               aTag == nsGkAtoms::altGlyph ||
               aTag == nsGkAtoms::textPath) {
      return &sSuppressData;
    }
  } else {
    nsIFrame *ancestorFrame =
      nsSVGUtils::GetFirstNonAAncestorFrame(aParentFrame);
    if (ancestorFrame) {
      if (aTag == nsGkAtoms::tspan || aTag == nsGkAtoms::altGlyph) {
        // tspan and altGlyph must be children of another text content element.
        nsSVGTextContainerFrame* metrics = do_QueryFrame(ancestorFrame);
        if (!metrics) {
          return &sSuppressData;
        }
      } else if (aTag == nsGkAtoms::textPath) {
        // textPath must be a child of text.
        nsIAtom* ancestorFrameType = ancestorFrame->GetType();
        if (ancestorFrameType != nsGkAtoms::svgTextFrame) {
          return &sSuppressData;
        }
      } else if (aTag != nsGkAtoms::a) {
        // Every other element except 'a' must not be a child of a text content
        // element.
        nsSVGTextContainerFrame* metrics = do_QueryFrame(ancestorFrame);
        if (metrics) {
          return &sSuppressData;
        }
      }
    }
  }

  static const FrameConstructionDataByTag sSVGData[] = {
    SIMPLE_SVG_CREATE(svg, NS_NewSVGInnerSVGFrame),
    SIMPLE_SVG_CREATE(g, NS_NewSVGGFrame),
    SIMPLE_SVG_CREATE(svgSwitch, NS_NewSVGSwitchFrame),
    SIMPLE_SVG_CREATE(polygon, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(polyline, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(circle, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(ellipse, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(line, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(rect, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(path, NS_NewSVGPathGeometryFrame),
    SIMPLE_SVG_CREATE(defs, NS_NewSVGContainerFrame),
    SIMPLE_SVG_CREATE(generic_, NS_NewSVGGenericContainerFrame),
    { &nsGkAtoms::foreignObject,
      FCDATA_WITH_WRAPPING_BLOCK(FCDATA_DISALLOW_OUT_OF_FLOW,
                                 NS_NewSVGForeignObjectFrame,
                                 nsCSSAnonBoxes::mozSVGForeignContent) },
    SIMPLE_SVG_CREATE(a, NS_NewSVGAFrame),
    SIMPLE_SVG_CREATE(altGlyph, NS_NewSVGTSpanFrame),
    SIMPLE_SVG_CREATE(text, NS_NewSVGTextFrame),
    SIMPLE_SVG_CREATE(tspan, NS_NewSVGTSpanFrame),
    SIMPLE_SVG_CREATE(linearGradient, NS_NewSVGLinearGradientFrame),
    SIMPLE_SVG_CREATE(radialGradient, NS_NewSVGRadialGradientFrame),
    SIMPLE_SVG_CREATE(stop, NS_NewSVGStopFrame),
    SIMPLE_SVG_CREATE(use, NS_NewSVGUseFrame),
    SIMPLE_SVG_CREATE(view, NS_NewSVGViewFrame),
    SIMPLE_SVG_CREATE(image, NS_NewSVGImageFrame),
    SIMPLE_SVG_CREATE(clipPath, NS_NewSVGClipPathFrame),
    SIMPLE_SVG_CREATE(textPath, NS_NewSVGTextPathFrame),
    SIMPLE_SVG_CREATE(filter, NS_NewSVGFilterFrame),
    SIMPLE_SVG_CREATE(pattern, NS_NewSVGPatternFrame),
    SIMPLE_SVG_CREATE(mask, NS_NewSVGMaskFrame),
    SIMPLE_SVG_CREATE(feDistantLight, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(fePointLight, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feSpotLight, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feBlend, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feColorMatrix, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feFuncR, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feFuncG, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feFuncB, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feFuncA, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feComposite, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feComponentTransfer, NS_NewSVGFEContainerFrame),
    SIMPLE_SVG_CREATE(feConvolveMatrix, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feDiffuseLighting, NS_NewSVGFEContainerFrame),
    SIMPLE_SVG_CREATE(feDisplacementMap, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feFlood, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feGaussianBlur, NS_NewSVGFELeafFrame),
    SIMPLE_SVG_CREATE(feImage, NS_NewSVGFEImageFrame),
    SIMPLE_SVG_CREATE(feMerge, NS_NewSVGFEContainerFrame),
    SIMPLE_SVG_CREATE(feMergeNode, NS_NewSVGFEUnstyledLeafFrame),
    SIMPLE_SVG_CREATE(feMorphology, NS_NewSVGFELeafFrame), 
    SIMPLE_SVG_CREATE(feOffset, NS_NewSVGFELeafFrame), 
    SIMPLE_SVG_CREATE(feSpecularLighting, NS_NewSVGFEContainerFrame),
    SIMPLE_SVG_CREATE(feTile, NS_NewSVGFELeafFrame), 
    SIMPLE_SVG_CREATE(feTurbulence, NS_NewSVGFELeafFrame) 
  };

  const FrameConstructionData* data =
    FindDataByTag(aTag, aElement, aStyleContext, sSVGData,
                  ArrayLength(sSVGData));

  if (!data) {
    data = &sContainerData;
  }

  return data;
}

void
nsCSSFrameConstructor::AddPageBreakItem(nsIContent* aContent,
                                        nsStyleContext* aMainStyleContext,
                                        FrameConstructionItemList& aItems)
{
  nsRefPtr<nsStyleContext> pseudoStyle;
  // Use the same parent style context that |aMainStyleContext| has, since
  // that's easier to re-resolve and it doesn't matter in practice.
  // (Getting different parents can result in framechange hints, e.g.,
  // for user-modify.)
  pseudoStyle =
    mPresShell->StyleSet()->
      ResolveAnonymousBoxStyle(nsCSSAnonBoxes::pageBreak,
                               aMainStyleContext->GetParent());

  NS_ASSERTION(pseudoStyle->StyleDisplay()->mDisplay ==
                 NS_STYLE_DISPLAY_BLOCK, "Unexpected display");

  static const FrameConstructionData sPageBreakData =
    FCDATA_DECL(FCDATA_SKIP_FRAMESET, NS_NewPageBreakFrame);

  // Lie about the tag and namespace so we don't trigger anything
  // interesting during frame construction.
  aItems.AppendItem(&sPageBreakData, aContent, nsCSSAnonBoxes::pageBreak,
                    kNameSpaceID_None, nullptr, pseudoStyle.forget(), true,
                    nullptr);
}

void
nsCSSFrameConstructor::ConstructFrame(nsFrameConstructorState& aState,
                                      nsIContent*              aContent,
                                      nsIFrame*                aParentFrame,
                                      nsFrameItems&            aFrameItems)

{
  NS_PRECONDITION(aParentFrame, "no parent frame");
  // NOTE: If we start using this code for non-anonymous content, we'll need
  // to evaluate whether the AutoFlexItemStyleFixupSkipper (instantiated below)
  // is appropriate for that content.
  NS_PRECONDITION(aContent->IsRootOfNativeAnonymousSubtree(),
                  "ConstructFrame should only be used for anonymous content");

  FrameConstructionItemList items;
  {
    // Skip flex item style-fixup during our AddFrameConstructionItems() call:
    TreeMatchContext::AutoFlexItemStyleFixupSkipper
      flexItemStyleFixupSkipper(aState.mTreeMatchContext);

    AddFrameConstructionItems(aState, aContent, true, aParentFrame, items);
  }
  items.SetTriedConstructingFrames();

  for (FCItemIterator iter(items); !iter.IsDone(); iter.Next()) {
    NS_ASSERTION(iter.item().DesiredParentType() == GetParentType(aParentFrame),
                 "This is not going to work");
    ConstructFramesFromItem(aState, iter, aParentFrame, aFrameItems);
  }
}

void
nsCSSFrameConstructor::AddFrameConstructionItems(nsFrameConstructorState& aState,
                                                 nsIContent* aContent,
                                                 bool aSuppressWhiteSpaceOptimizations,
                                                 nsIFrame* aParentFrame,
                                                 FrameConstructionItemList& aItems)
{
  aContent->UnsetFlags(NODE_DESCENDANTS_NEED_FRAMES | NODE_NEEDS_FRAME);
  if (aContent->IsElement()) {
    // We can't just remove our pending restyle flags, since we may
    // have restyle-later-siblings set on us.  But we _can_ remove the
    // "is possible restyle root" flags, and need to.  Otherwise we can
    // end up with stale such flags (e.g. if we used to have a
    // display:none parent when our last restyle was posted and
    // processed and now no longer do).
    aContent->UnsetFlags(ELEMENT_ALL_RESTYLE_FLAGS &
                         ~ELEMENT_PENDING_RESTYLE_FLAGS);
  }

  // XXX the GetContent() != aContent check is needed due to bug 135040.
  // Remove it once that's fixed.  
  if (aContent->GetPrimaryFrame() &&
      aContent->GetPrimaryFrame()->GetContent() == aContent &&
      !aState.mCreatingExtraFrames) {
    NS_ERROR("asked to create frame construction item for a node that already "
             "has a frame");
    return;
  }

  // don't create a whitespace frame if aParent doesn't want it
  if (!NeedFrameFor(aState, aParentFrame, aContent)) {
    return;
  }

  // never create frames for comments or PIs
  if (aContent->IsNodeOfType(nsINode::eCOMMENT) ||
      aContent->IsNodeOfType(nsINode::ePROCESSING_INSTRUCTION))
    return;

  nsRefPtr<nsStyleContext> styleContext;
  styleContext = ResolveStyleContext(aParentFrame, aContent, &aState);

  uint32_t flags = ITEM_ALLOW_XBL_BASE | ITEM_ALLOW_PAGE_BREAK;
  if (aParentFrame->IsSVGText()) {
    flags |= ITEM_IS_WITHIN_SVG_TEXT;
  }
  if (aParentFrame->GetType() == nsGkAtoms::blockFrame &&
      aParentFrame->GetParent() &&
      aParentFrame->GetParent()->GetType() == nsGkAtoms::svgTextFrame2) {
    flags |= ITEM_ALLOWS_TEXT_PATH_CHILD;
  }
  AddFrameConstructionItemsInternal(aState, aContent, aParentFrame,
                                    aContent->Tag(), aContent->GetNameSpaceID(),
                                    aSuppressWhiteSpaceOptimizations,
                                    styleContext,
                                    flags, nullptr,
                                    aItems);
}

/* static */ void
nsCSSFrameConstructor::SetAsUndisplayedContent(FrameConstructionItemList& aList,
                                               nsIContent* aContent,
                                               nsStyleContext* aStyleContext,
                                               bool aIsGeneratedContent)
{
  if (aStyleContext->GetPseudo()) {
    if (aIsGeneratedContent) {
      aContent->UnbindFromTree();
    }
    return;
  }

  NS_ASSERTION(!aIsGeneratedContent, "Should have had pseudo type");
  aList.AppendUndisplayedItem(aContent, aStyleContext);
}

void
nsCSSFrameConstructor::AddFrameConstructionItemsInternal(nsFrameConstructorState& aState,
                                                         nsIContent* aContent,
                                                         nsIFrame* aParentFrame,
                                                         nsIAtom* aTag,
                                                         int32_t aNameSpaceID,
                                                         bool aSuppressWhiteSpaceOptimizations,
                                                         nsStyleContext* aStyleContext,
                                                         uint32_t aFlags,
                                                         nsTArray<nsIAnonymousContentCreator::ContentInfo>* aAnonChildren,
                                                         FrameConstructionItemList& aItems)
{
  NS_PRECONDITION(aContent->IsNodeOfType(nsINode::eTEXT) ||
                  aContent->IsElement(),
                  "Shouldn't get anything else here!");

  // The following code allows the user to specify the base tag
  // of an element using XBL.  XUL and HTML objects (like boxes, menus, etc.)
  // can then be extended arbitrarily.
  const nsStyleDisplay* display = aStyleContext->StyleDisplay();
  nsRefPtr<nsStyleContext> styleContext(aStyleContext);
  PendingBinding* pendingBinding = nullptr;
  if ((aFlags & ITEM_ALLOW_XBL_BASE) && display->mBinding)
  {
    // Ensure that our XBL bindings are installed.

    nsXBLService* xblService = nsXBLService::GetInstance();
    if (!xblService)
      return;

    bool resolveStyle;

    nsAutoPtr<PendingBinding> newPendingBinding(new PendingBinding());

    nsresult rv = xblService->LoadBindings(aContent, display->mBinding->GetURI(),
                                           display->mBinding->mOriginPrincipal,
                                           getter_AddRefs(newPendingBinding->mBinding),
                                           &resolveStyle);
    if (NS_FAILED(rv) && rv != NS_ERROR_XBL_BLOCKED)
      return;

    if (newPendingBinding->mBinding) {
      pendingBinding = newPendingBinding;
      // aState takes over owning newPendingBinding
      aState.AddPendingBinding(newPendingBinding.forget());
    }

    if (resolveStyle) {
      styleContext =
        ResolveStyleContext(styleContext->GetParent(), aContent, &aState);
      display = styleContext->StyleDisplay();
      aStyleContext = styleContext;
    }

    aTag = mDocument->BindingManager()->ResolveTag(aContent, &aNameSpaceID);
  }

  bool isGeneratedContent = ((aFlags & ITEM_IS_GENERATED_CONTENT) != 0);

  // Pre-check for display "none" - if we find that, don't create
  // any frame at all
  if (NS_STYLE_DISPLAY_NONE == display->mDisplay) {
    SetAsUndisplayedContent(aItems, aContent, styleContext, isGeneratedContent);
    return;
  }

  bool isText = !aContent->IsElement();

  // never create frames for non-option/optgroup kids of <select> and
  // non-option kids of <optgroup> inside a <select>.
  // XXXbz it's not clear how this should best work with XBL.
  nsIContent *parent = aContent->GetParent();
  if (parent) {
    // Check tag first, since that check will usually fail
    nsIAtom* parentTag = parent->Tag();
    if ((parentTag == nsGkAtoms::select || parentTag == nsGkAtoms::optgroup) &&
        parent->IsHTML() &&
        // <option> is ok no matter what
        !aContent->IsHTML(nsGkAtoms::option) &&
        // <optgroup> is OK in <select> but not in <optgroup>
        (!aContent->IsHTML(nsGkAtoms::optgroup) ||
         parentTag != nsGkAtoms::select) &&
        // Allow native anonymous content no matter what
        !aContent->IsRootOfNativeAnonymousSubtree()) {
      // No frame for aContent
      if (!isText) {
        SetAsUndisplayedContent(aItems, aContent, styleContext,
                                isGeneratedContent);
      }
      return;
    }
  }

  bool isPopup = false;
  // Try to find frame construction data for this content
  const FrameConstructionData* data;
  if (isText) {
    data = FindTextData(aParentFrame);
    if (!data) {
      // Nothing to do here; suppressed text inside SVG
      return;
    }
  } else {
    Element* element = aContent->AsElement();

    // Don't create frames for non-SVG element children of SVG elements.
    if (aNameSpaceID != kNameSpaceID_SVG &&
        ((aParentFrame &&
          IsFrameForSVG(aParentFrame) &&
          !aParentFrame->IsFrameOfType(nsIFrame::eSVGForeignObject)) ||
         (aFlags & ITEM_IS_WITHIN_SVG_TEXT))) {
      SetAsUndisplayedContent(aItems, element, styleContext,
                              isGeneratedContent);
      return;
    }

    data = FindHTMLData(element, aTag, aNameSpaceID, aParentFrame,
                        styleContext);
    if (!data) {
      data = FindXULTagData(element, aTag, aNameSpaceID, styleContext);
    }
    if (!data) {
      data = FindMathMLData(element, aTag, aNameSpaceID, styleContext);
    }
    if (!data) {
      data = FindSVGData(element, aTag, aNameSpaceID, aParentFrame,
                         aFlags & ITEM_IS_WITHIN_SVG_TEXT,
                         aFlags & ITEM_ALLOWS_TEXT_PATH_CHILD,
                         styleContext);
    }

    // Now check for XUL display types
    if (!data) {
      data = FindXULDisplayData(display, element, styleContext);
    }

    // And general display types
    if (!data) {
      data = FindDisplayData(display, element, aParentFrame, styleContext);
    }

    NS_ASSERTION(data, "Should have frame construction data now");

    if (data->mBits & FCDATA_SUPPRESS_FRAME) {
      SetAsUndisplayedContent(aItems, element, styleContext, isGeneratedContent);
      return;
    }

#ifdef MOZ_XUL
    if ((data->mBits & FCDATA_IS_POPUP) &&
        (!aParentFrame || // Parent is inline
         aParentFrame->GetType() != nsGkAtoms::menuFrame)) {
      if (!aState.mPopupItems.containingBlock &&
          !aState.mHavePendingPopupgroup) {
        SetAsUndisplayedContent(aItems, element, styleContext,
                                isGeneratedContent);
        return;
      }

      isPopup = true;
    }
#endif /* MOZ_XUL */
  }

  uint32_t bits = data->mBits;

  // Inside colgroups, suppress everything except columns.
  if (aParentFrame &&
      aParentFrame->GetType() == nsGkAtoms::tableColGroupFrame &&
      (!(bits & FCDATA_IS_TABLE_PART) ||
       display->mDisplay != NS_STYLE_DISPLAY_TABLE_COLUMN)) {
    SetAsUndisplayedContent(aItems, aContent, styleContext, isGeneratedContent);
    return;
  }

  bool canHavePageBreak =
    (aFlags & ITEM_ALLOW_PAGE_BREAK) &&
    aState.mPresContext->IsPaginated() &&
    !display->IsAbsolutelyPositionedStyle() &&
    !(bits & FCDATA_IS_TABLE_PART) &&
    !(bits & FCDATA_IS_SVG_TEXT);

  if (canHavePageBreak && display->mBreakBefore) {
    AddPageBreakItem(aContent, aStyleContext, aItems);
  }

  FrameConstructionItem* item =
    aItems.AppendItem(data, aContent, aTag, aNameSpaceID,
                      pendingBinding, styleContext.forget(),
                      aSuppressWhiteSpaceOptimizations, aAnonChildren);
  if (!item) {
    if (isGeneratedContent) {
      aContent->UnbindFromTree();
    }
    return;
  }

  item->mIsText = isText;
  item->mIsGeneratedContent = isGeneratedContent;
  if (isGeneratedContent) {
    NS_ADDREF(item->mContent);
  }
  item->mIsRootPopupgroup =
    aNameSpaceID == kNameSpaceID_XUL && aTag == nsGkAtoms::popupgroup &&
    aContent->IsRootOfNativeAnonymousSubtree();
  if (item->mIsRootPopupgroup) {
    aState.mHavePendingPopupgroup = true;
  }
  item->mIsPopup = isPopup;
  item->mIsForSVGAElement = aNameSpaceID == kNameSpaceID_SVG &&
                            aTag == nsGkAtoms::a;

  if (canHavePageBreak && display->mBreakAfter) {
    AddPageBreakItem(aContent, aStyleContext, aItems);
  }

  if (bits & FCDATA_IS_INLINE) {
    // To correctly set item->mIsAllInline we need to build up our child items
    // right now.
    BuildInlineChildItems(aState, *item,
                          aFlags & ITEM_IS_WITHIN_SVG_TEXT,
                          aFlags & ITEM_ALLOWS_TEXT_PATH_CHILD);
    item->mHasInlineEnds = true;
    item->mIsBlock = false;
  } else {
    // Compute a boolean isInline which is guaranteed to be false for blocks
    // (but may also be false for some inlines).
    bool isInline =
      // Table-internal things are inline-outside if and only if they're kids of
      // inlines, since they'll trigger construction of inline-table
      // pseudos.
      ((bits & FCDATA_IS_TABLE_PART) &&
       (!aParentFrame || // No aParentFrame means inline
        aParentFrame->StyleDisplay()->mDisplay == NS_STYLE_DISPLAY_INLINE)) ||
      // Things that are inline-outside but aren't inline frames are inline
      display->IsInlineOutsideStyle() ||
      // Popups that are certainly out of flow.
      isPopup;

    // Set mIsAllInline conservatively.  It just might be that even an inline
    // that has mIsAllInline false doesn't need an {ib} split.  So this is just
    // an optimization to keep from doing too much work in cases when we can
    // show that mIsAllInline is true..
    item->mIsAllInline = item->mHasInlineEnds = isInline ||
      // Figure out whether we're guaranteed this item will be out of flow.
      // This is not a precise test, since one of our ancestor inlines might add
      // an absolute containing block (if it's relatively positioned) when there
      // wasn't such a containing block before.  But it's conservative in the
      // sense that anything that will really end up as an in-flow non-inline
      // will test false here.  In other words, if this test is true we're
      // guaranteed to be inline; if it's false we don't know what we'll end up
      // as.
      //
      // If we make this test precise, we can remove some of the code dealing
      // with the imprecision in ConstructInline and adjust the comments on
      // mIsAllInline and mIsBlock in the header.  And probably remove mIsBlock
      // altogether, since then it will always be equal to !mHasInlineEnds.
      (!(bits & FCDATA_DISALLOW_OUT_OF_FLOW) &&
       aState.GetGeometricParent(display, nullptr));

    // Set mIsBlock conservatively.  It's OK to set it false for some real
    // blocks, but not OK to set it true for things that aren't blocks.  Since
    // isOutOfFlow might be false even in cases when the frame will end up
    // out-of-flow, we can't use it here.  But we _can_ say that the frame will
    // for sure end up in-flow if it's not floated or absolutely positioned.
    item->mIsBlock = !isInline &&
                     !display->IsAbsolutelyPositionedStyle() &&
                     !display->IsFloatingStyle() &&
                     !(bits & FCDATA_IS_SVG_TEXT);
  }

  if (item->mIsAllInline) {
    aItems.InlineItemAdded();
  } else if (item->mIsBlock) {
    aItems.BlockItemAdded();
  }

  // Our item should be treated as a line participant if we have the relevant
  // bit and are going to be in-flow.  Note that this really only matters if
  // our ancestor is a box or some such, so the fact that we might have an
  // inline ancestor that might become a containing block is not relevant here.
  if ((bits & FCDATA_IS_LINE_PARTICIPANT) &&
      ((bits & FCDATA_DISALLOW_OUT_OF_FLOW) ||
       !aState.GetGeometricParent(display, nullptr))) {
    item->mIsLineParticipant = true;
    aItems.LineParticipantItemAdded();
  }
}

static void
DestroyContent(void* aPropertyValue)
{
  nsIContent* content = static_cast<nsIContent*>(aPropertyValue);
  content->UnbindFromTree();
  NS_RELEASE(content);
}

NS_DECLARE_FRAME_PROPERTY(BeforeProperty, DestroyContent)
NS_DECLARE_FRAME_PROPERTY(AfterProperty, DestroyContent)

static const FramePropertyDescriptor*
GenConPseudoToProperty(nsIAtom* aPseudo)
{
  NS_ASSERTION(aPseudo == nsCSSPseudoElements::before ||
               aPseudo == nsCSSPseudoElements::after,
               "Bad gen-con pseudo");
  return aPseudo == nsCSSPseudoElements::before ? BeforeProperty()
      : AfterProperty();
}

/**
 * Return true if the frame construction item pointed to by aIter will
 * create a frame adjacent to a line boundary in the frame tree, and that
 * line boundary is induced by a content node adjacent to the frame's
 * content node in the content tree. The latter condition is necessary so
 * that ContentAppended/ContentInserted/ContentRemoved can easily find any
 * text nodes that were suppressed here.
 */
bool
nsCSSFrameConstructor::AtLineBoundary(FCItemIterator& aIter)
{
  if (aIter.item().mSuppressWhiteSpaceOptimizations) {
    return false;
  }

  if (aIter.AtStart()) {
    if (aIter.List()->HasLineBoundaryAtStart() &&
        !aIter.item().mContent->GetPreviousSibling())
      return true;
  } else {
    FCItemIterator prev = aIter;
    prev.Prev();
    if (prev.item().IsLineBoundary() &&
        !prev.item().mSuppressWhiteSpaceOptimizations &&
        aIter.item().mContent->GetPreviousSibling() == prev.item().mContent)
      return true;
  }

  FCItemIterator next = aIter;
  next.Next();
  if (next.IsDone()) {
    if (aIter.List()->HasLineBoundaryAtEnd() &&
        !aIter.item().mContent->GetNextSibling())
      return true;
  } else {
    if (next.item().IsLineBoundary() &&
        !next.item().mSuppressWhiteSpaceOptimizations &&
        aIter.item().mContent->GetNextSibling() == next.item().mContent)
      return true;
  }

  return false;
}

void
nsCSSFrameConstructor::ConstructFramesFromItem(nsFrameConstructorState& aState,
                                               FCItemIterator& aIter,
                                               nsIFrame* aParentFrame,
                                               nsFrameItems& aFrameItems)
{
  nsIFrame* adjParentFrame = aParentFrame;
  FrameConstructionItem& item = aIter.item();
  nsStyleContext* styleContext = item.mStyleContext;
  AdjustParentFrame(adjParentFrame, item.mFCData, styleContext);

  if (item.mIsText) {
    // If this is collapsible whitespace next to a line boundary,
    // don't create a frame. item.IsWhitespace() also sets the
    // NS_CREATE_FRAME_IF_NON_WHITESPACE flag in the text node. (If we
    // end up creating a frame, nsTextFrame::Init will clear the flag.)
    // We don't do this for generated content, because some generated
    // text content is empty text nodes that are about to be initialized.
    // (We check mAdditionalStateBits because only the generated content
    // container's frame construction item is marked with
    // mIsGeneratedContent, and we might not have an aParentFrame.)
    // We don't do it for content that may have XBL anonymous siblings,
    // because they make it difficult to correctly create the frame
    // due to dynamic changes.
    // We don't do it for SVG text, since we might need to position and
    // measure the white space glyphs due to x/y/dx/dy attributes.
    // We check that NS_CREATE_FRAME_FOR_IGNORABLE_WHITESPACE is not set on
    // the node. This lets us disable this optimization for specific nodes
    // (e.g. nodes whose geometry is being queried via DOM APIs).
    if (AtLineBoundary(aIter) &&
        !styleContext->StyleText()->WhiteSpaceOrNewlineIsSignificant() &&
        aIter.List()->ParentHasNoXBLChildren() &&
        !(aState.mAdditionalStateBits & NS_FRAME_GENERATED_CONTENT) &&
        (item.mFCData->mBits & FCDATA_IS_LINE_PARTICIPANT) &&
        !(item.mFCData->mBits & FCDATA_IS_SVG_TEXT) &&
        !item.mContent->HasFlag(NS_CREATE_FRAME_FOR_IGNORABLE_WHITESPACE) &&
        item.IsWhitespace(aState))
      return;

    ConstructTextFrame(item.mFCData, aState, item.mContent,
                       adjParentFrame, styleContext,
                       aFrameItems);
    return;
  }

  // Start background loads during frame construction so that we're
  // guaranteed that they will be started before onload fires.
  styleContext->StartBackgroundImageLoads();

  nsFrameState savedStateBits = aState.mAdditionalStateBits;
  if (item.mIsGeneratedContent) {
    // Ensure that frames created here are all tagged with
    // NS_FRAME_GENERATED_CONTENT.
    aState.mAdditionalStateBits |= NS_FRAME_GENERATED_CONTENT;

    // Note that we're not necessarily setting this property on the primary
    // frame for the content for which this is generated content.  We might be
    // setting it on a table pseudo-frame inserted under that instead.  That's
    // OK, though; we just need to do the property set so that the content will
    // get cleaned up when the frame is destroyed.
    aParentFrame->Properties().Set(GenConPseudoToProperty(styleContext->GetPseudo()),
                                   item.mContent);

    // Now that we've passed ownership of item.mContent to the frame, unset
    // our generated content flag so we don't release or unbind it ourselves.
    item.mIsGeneratedContent = false;
  }

  // XXXbz maybe just inline ConstructFrameFromItemInternal here or something?
  ConstructFrameFromItemInternal(item, aState, adjParentFrame, aFrameItems);

  aState.mAdditionalStateBits = savedStateBits;
}


inline bool
IsRootBoxFrame(nsIFrame *aFrame)
{
  return (aFrame->GetType() == nsGkAtoms::rootFrame);
}

nsresult
nsCSSFrameConstructor::ReconstructDocElementHierarchy()
{
  Element* rootElement = mDocument->GetRootElement();
  if (!rootElement) {
    /* nothing to do */
    return NS_OK;
  }
  return RecreateFramesForContent(rootElement, false);
}

nsIFrame*
nsCSSFrameConstructor::GetFrameFor(nsIContent* aContent)
{
  // Get the primary frame associated with the content
  nsIFrame* frame = aContent->GetPrimaryFrame();

  if (!frame)
    return nullptr;

  // If the content of the frame is not the desired content then this is not
  // really a frame for the desired content.
  // XXX This check is needed due to bug 135040. Remove it once that's fixed.
  if (frame->GetContent() != aContent) {
    return nullptr;
  }

  nsIFrame* insertionFrame = frame->GetContentInsertionFrame();

  NS_ASSERTION(insertionFrame == frame || !frame->IsLeaf(),
    "The insertion frame is the primary frame or the primary frame isn't a leaf");

  return insertionFrame;
}

nsIFrame*
nsCSSFrameConstructor::GetAbsoluteContainingBlock(nsIFrame* aFrame,
                                                  ContainingBlockType aType)
{
  NS_PRECONDITION(nullptr != mRootElementFrame, "no root element frame");

  // Starting with aFrame, look for a frame that is absolutely positioned or
  // relatively positioned (and transformed, if aType is FIXED)
  for (nsIFrame* frame = aFrame; frame; frame = frame->GetParent()) {
    if (frame->IsFrameOfType(nsIFrame::eMathML)) {
      // If it's mathml, bail out -- no absolute positioning out from inside
      // mathml frames.  Note that we don't make this part of the loop
      // condition because of the stuff at the end of this method...
      return nullptr;
    }

    // If the frame is positioned, we will probably return it as the containing
    // block (see the exceptions below).  Otherwise, we'll start looking at the
    // parent frame, unless we're dealing with a scrollframe.
    // Scrollframes are special since they're not positioned, but their
    // scrolledframe might be.  So, we need to check this special case to return
    // the correct containing block (the scrolledframe) in that case.
    // If we're looking for a fixed-pos containing block and the frame is
    // not transformed, skip it.
    if (!frame->IsPositioned() ||
        (aType == FIXED_POS && !frame->StyleDisplay()->HasTransform(frame))) {
      continue;
    }
    nsIFrame* absPosCBCandidate = nullptr;
    if (frame->GetType() == nsGkAtoms::scrollFrame) {
      nsIScrollableFrame* scrollFrame = do_QueryFrame(frame);
      absPosCBCandidate = scrollFrame->GetScrolledFrame();
    } else {
      // Only first continuations can be containing blocks.
      absPosCBCandidate = frame->FirstContinuation();
    }
    // Is the frame really an absolute container?
    if (!absPosCBCandidate || !absPosCBCandidate->IsAbsoluteContainer()) {
      continue;
    }

    // For tables, skip the inner frame and consider the outer table frame.
    if (absPosCBCandidate->GetType() == nsGkAtoms::tableFrame) {
      continue;
    }
    // For outer table frames, we can just return absPosCBCandidate.
    return absPosCBCandidate;
  }

  // It is possible for the search for the containing block to fail, because
  // no absolute container can be found in the parent chain.  In those cases,
  // we fall back to the document element's containing block.
  if (aType == FIXED_POS) {
    return mFixedContainingBlock;
  }
  return mHasRootAbsPosContainingBlock ? mDocElementContainingBlock : nullptr;
}

nsIFrame*
nsCSSFrameConstructor::GetFloatContainingBlock(nsIFrame* aFrame)
{
  // Starting with aFrame, look for a frame that is a float containing block.
  // IF we hit a mathml frame, bail out; we don't allow floating out of mathml
  // frames, because they don't seem to be able to deal.
  // The logic here needs to match the logic in ProcessChildren()
  for (nsIFrame* containingBlock = aFrame;
       containingBlock &&
         !ShouldSuppressFloatingOfDescendants(containingBlock);
       containingBlock = containingBlock->GetParent()) {
    if (containingBlock->IsFloatContainingBlock()) {
      return containingBlock;
    }
  }

  // If we didn't find a containing block, then there just isn't
  // one.... return null
  return nullptr;
}

/**
 * This function will check whether aContainer has :after generated content.
 * If so, appending to it should actually insert.  The return value is the
 * parent to use for newly-appended content.  *aAfterFrame points to the :after
 * frame before which appended content should go, if there is one.
 */
static nsIFrame*
AdjustAppendParentForAfterContent(nsPresContext* aPresContext,
                                  nsIContent* aContainer,
                                  nsIFrame* aParentFrame,
                                  nsIFrame** aAfterFrame)
{
  // See if the parent has an :after pseudo-element.  Check for the presence
  // of style first, since nsLayoutUtils::GetAfterFrame is sorta expensive.
  nsStyleContext* parentStyle = aParentFrame->StyleContext();
  if (nsLayoutUtils::HasPseudoStyle(aContainer, parentStyle,
                                    nsCSSPseudoElements::ePseudo_after,
                                    aPresContext)) {
    // Ensure that the :after frame is on the principal child list.
    aParentFrame->DrainSelfOverflowList();

    nsIFrame* afterFrame = nsLayoutUtils::GetAfterFrame(aParentFrame);
    if (afterFrame) {
      *aAfterFrame = afterFrame;
      return afterFrame->GetParent();
    }
  }

  *aAfterFrame = nullptr;

  if (IsFrameSpecial(aParentFrame)) {
    // We might be in a situation where the last part of the {ib} split was
    // empty.  Since we have no ::after pseudo-element, we do in fact want to be
    // appending to that last part, so advance to it if needed.  Note that here
    // aParentFrame is the result of a GetLastSpecialSibling call, so must be
    // either the last or next to last special sibling.
    nsIFrame* trailingInline = GetSpecialSibling(aParentFrame);
    if (trailingInline) {
      aParentFrame = trailingInline;
    }

    // Always make sure to look at the last continuation of the frame
    // for the {ib} case, even if that continuation is empty.  We
    // don't do this for the non-special-frame case, since in the
    // other cases appending to the last nonempty continuation is fine
    // and in fact not doing that can confuse code that doesn't know
    // to pull kids from continuations other than its next one.
    aParentFrame = aParentFrame->LastContinuation();
  }

  return aParentFrame;
}

/**
 * This function will get the previous sibling to use for an append operation.
 * it takes a parent frame (must not be null) and its :after frame (may be
 * null).
 */
static nsIFrame*
FindAppendPrevSibling(nsIFrame* aParentFrame, nsIFrame* aAfterFrame)
{
  if (aAfterFrame) {
    NS_ASSERTION(aAfterFrame->GetParent() == aParentFrame, "Wrong parent");
    NS_ASSERTION(aAfterFrame->GetPrevSibling() ||
                 aParentFrame->GetFirstPrincipalChild() == aAfterFrame,
                 ":after frame must be on the principal child list here");
    return aAfterFrame->GetPrevSibling();
  }

  aParentFrame->DrainSelfOverflowList();

  return aParentFrame->GetLastChild(kPrincipalList);
}

/**
 * This function will get the next sibling for a frame insert operation given
 * the parent and previous sibling.  aPrevSibling may be null.
 */
static nsIFrame*
GetInsertNextSibling(nsIFrame* aParentFrame, nsIFrame* aPrevSibling)
{
  if (aPrevSibling) {
    return aPrevSibling->GetNextSibling();
  }

  return aParentFrame->GetFirstPrincipalChild();
}

/**
 * This function is called by ContentAppended() and ContentInserted() when
 * appending flowed frames to a parent's principal child list. It handles the
 * case where the parent is the trailing inline of an {ib} split.
 */
nsresult
nsCSSFrameConstructor::AppendFramesToParent(nsFrameConstructorState&       aState,
                                            nsIFrame*                      aParentFrame,
                                            nsFrameItems&                  aFrameList,
                                            nsIFrame*                      aPrevSibling,
                                            bool                           aIsRecursiveCall)
{
  NS_PRECONDITION(!IsFrameSpecial(aParentFrame) ||
                  !GetSpecialSibling(aParentFrame) ||
                  !GetSpecialSibling(aParentFrame)->GetFirstPrincipalChild(),
                  "aParentFrame has a special sibling with kids?");
  NS_PRECONDITION(!aPrevSibling || aPrevSibling->GetParent() == aParentFrame,
                  "Parent and prevsibling don't match");

  nsIFrame* nextSibling = ::GetInsertNextSibling(aParentFrame, aPrevSibling);

  NS_ASSERTION(nextSibling ||
               !aParentFrame->GetNextContinuation() ||
               !aParentFrame->GetNextContinuation()->GetFirstPrincipalChild() ||
               aIsRecursiveCall,
               "aParentFrame has later continuations with kids?");
  NS_ASSERTION(nextSibling ||
               !IsFrameSpecial(aParentFrame) ||
               (IsInlineFrame(aParentFrame) &&
                !GetSpecialSibling(aParentFrame) &&
                !aParentFrame->GetNextContinuation()) ||
               aIsRecursiveCall,
               "aParentFrame is not last?");

  // If we're inserting a list of frames at the end of the trailing inline
  // of an {ib} split, we may need to create additional {ib} siblings to parent
  // them.
  if (!nextSibling && IsFrameSpecial(aParentFrame)) {
    // When we get here, our frame list might start with a block.  If it does
    // so, and aParentFrame is an inline, and it and all its previous
    // continuations have no siblings, then put the initial blocks from the
    // frame list into the previous block of the {ib} split.  Note that we
    // didn't want to stop at the block part of the split when figuring out
    // initial parent, because that could screw up float parenting; it's easier
    // to do this little fixup here instead.
    if (aFrameList.NotEmpty() && !aFrameList.FirstChild()->IsInlineOutside()) {
      // See whether our trailing inline is empty
      nsIFrame* firstContinuation = aParentFrame->FirstContinuation();
      if (firstContinuation->PrincipalChildList().IsEmpty()) {
        // Our trailing inline is empty.  Collect our starting blocks from
        // aFrameList, get the right parent frame for them, and put them in.
        nsFrameList::FrameLinkEnumerator firstNonBlockEnumerator =
          FindFirstNonBlock(aFrameList);
        nsFrameList blockKids = aFrameList.ExtractHead(firstNonBlockEnumerator);
        NS_ASSERTION(blockKids.NotEmpty(), "No blocks?");

        nsIFrame* prevBlock =
          GetSpecialPrevSibling(firstContinuation)->LastContinuation();
        NS_ASSERTION(prevBlock, "Should have previous block here");

        MoveChildrenTo(aState.mPresContext, aParentFrame, prevBlock, blockKids);
      }
    }

    // We want to put some of the frames into this inline frame.
    nsFrameList::FrameLinkEnumerator firstBlockEnumerator(aFrameList);
    FindFirstBlock(firstBlockEnumerator);

    nsFrameList inlineKids = aFrameList.ExtractHead(firstBlockEnumerator);
    if (!inlineKids.IsEmpty()) {
      AppendFrames(aParentFrame, kPrincipalList, inlineKids);
    }

    if (!aFrameList.IsEmpty()) {
      bool positioned = aParentFrame->IsRelativelyPositioned();
      nsFrameItems ibSiblings;
      CreateIBSiblings(aState, aParentFrame, positioned, aFrameList,
                       ibSiblings);

      // Make sure to trigger reflow of the inline that used to be our
      // last one and now isn't anymore, since its GetSkipSides() has
      // changed.
      mPresShell->FrameNeedsReflow(aParentFrame,
                                   nsIPresShell::eTreeChange,
                                   NS_FRAME_HAS_DIRTY_CHILDREN);

      // Recurse so we create new ib siblings as needed for aParentFrame's parent
      return AppendFramesToParent(aState, aParentFrame->GetParent(), ibSiblings,
                                  aParentFrame, true);
    }

    return NS_OK;
  }
  
  // Insert the frames after our aPrevSibling
  return InsertFrames(aParentFrame, kPrincipalList, aPrevSibling, aFrameList);
}

#define UNSET_DISPLAY 255

// This gets called to see if the frames corresponding to aSibling and aContent
// should be siblings in the frame tree. Although (1) rows and cols, (2) row
// groups and col groups, (3) row groups and captions, (4) legends and content
// inside fieldsets, (5) popups and other kids of the menu are siblings from a
// content perspective, they are not considered siblings in the frame tree.
bool
nsCSSFrameConstructor::IsValidSibling(nsIFrame*              aSibling,
                                      nsIContent*            aContent,
                                      uint8_t&               aDisplay)
{
  nsIFrame* parentFrame = aSibling->GetParent();
  nsIAtom* parentType = nullptr;
  nsIAtom* grandparentType = nullptr;
  if (parentFrame) {
    parentType = parentFrame->GetType();
    nsIFrame* grandparentFrame = parentFrame->GetParent();
    if (grandparentFrame) {
      grandparentType = grandparentFrame->GetType();
    }
  }

  uint8_t siblingDisplay = aSibling->GetDisplay();
  if ((NS_STYLE_DISPLAY_TABLE_COLUMN_GROUP == siblingDisplay) ||
      (NS_STYLE_DISPLAY_TABLE_COLUMN       == siblingDisplay) ||
      (NS_STYLE_DISPLAY_TABLE_CAPTION      == siblingDisplay) ||
      (NS_STYLE_DISPLAY_TABLE_HEADER_GROUP == siblingDisplay) ||
      (NS_STYLE_DISPLAY_TABLE_ROW_GROUP    == siblingDisplay) ||
      (NS_STYLE_DISPLAY_TABLE_FOOTER_GROUP == siblingDisplay) ||
      nsGkAtoms::menuFrame == parentType) {
    // if we haven't already, construct a style context to find the display type of aContent
    if (UNSET_DISPLAY == aDisplay) {
      nsRefPtr<nsStyleContext> styleContext;
      nsIFrame* styleParent = aSibling->GetParentStyleContextFrame();
      if (!styleParent) {
        NS_NOTREACHED("Shouldn't happen");
        return false;
      }
      // XXXbz when this code is killed, the state argument to
      // ResolveStyleContext can be made non-optional.
      styleContext = ResolveStyleContext(styleParent, aContent, nullptr);
      const nsStyleDisplay* display = styleContext->StyleDisplay();
      aDisplay = display->mDisplay;
    }
    if (nsGkAtoms::menuFrame == parentType) {
      return
        (NS_STYLE_DISPLAY_POPUP == aDisplay) ==
        (NS_STYLE_DISPLAY_POPUP == siblingDisplay);
    }
    // To have decent performance we want to return false in cases in which
    // reordering the two siblings has no effect on display.  To ensure
    // correctness, we MUST return false in cases where the two siblings have
    // the same desired parent type and live on different display lists.
    // Specificaly, columns and column groups should only consider columns and
    // column groups as valid siblings.  Captions should only consider other
    // captions.  All other things should consider each other as valid
    // siblings.  The restriction in the |if| above on siblingDisplay is ok,
    // because for correctness the only part that really needs to happen is to
    // not consider captions, column groups, and row/header/footer groups
    // siblings of each other.  Treating a column or colgroup as a valid
    // sibling of a non-table-related frame will just mean we end up reframing.
    if ((siblingDisplay == NS_STYLE_DISPLAY_TABLE_CAPTION) !=
        (aDisplay == NS_STYLE_DISPLAY_TABLE_CAPTION)) {
      // One's a caption and the other is not.  Not valid siblings.
      return false;
    }

    if ((siblingDisplay == NS_STYLE_DISPLAY_TABLE_COLUMN_GROUP ||
         siblingDisplay == NS_STYLE_DISPLAY_TABLE_COLUMN) !=
        (aDisplay == NS_STYLE_DISPLAY_TABLE_COLUMN_GROUP ||
         aDisplay == NS_STYLE_DISPLAY_TABLE_COLUMN)) {
      // One's a column or column group and the other is not.  Not valid
      // siblings.
      return false;
    }

    return true;
  }
  else if (nsGkAtoms::fieldSetFrame == parentType ||
           (nsGkAtoms::fieldSetFrame == grandparentType &&
            nsGkAtoms::blockFrame == parentType)) {
    // Legends can be sibling of legends but not of other content in the fieldset
    nsIAtom* sibType = aSibling->GetContentInsertionFrame()->GetType();
    bool legendContent = aContent->IsHTML(nsGkAtoms::legend);

    if ((legendContent  && (nsGkAtoms::legendFrame != sibType)) ||
        (!legendContent && (nsGkAtoms::legendFrame == sibType)))
      return false;
  }

  return true;
}

nsIFrame*
nsCSSFrameConstructor::FindFrameForContentSibling(nsIContent* aContent,
                                                  nsIContent* aTargetContent,
                                                  uint8_t& aTargetContentDisplay,
                                                  bool aPrevSibling)
{
  nsIFrame* sibling = aContent->GetPrimaryFrame();
  if (!sibling || sibling->GetContent() != aContent) {
    // XXX the GetContent() != aContent check is needed due to bug 135040.
    // Remove it once that's fixed.
    return nullptr;
  }

  // If the frame is out-of-flow, GetPrimaryFrame() will have returned the
  // out-of-flow frame; we want the placeholder.
  if (sibling->GetStateBits() & NS_FRAME_OUT_OF_FLOW) {
    nsIFrame* placeholderFrame = GetPlaceholderFrameFor(sibling);
    NS_ASSERTION(placeholderFrame, "no placeholder for out-of-flow frame");
    sibling = placeholderFrame;
  }

  // The frame we have now should never be a continuation
  NS_ASSERTION(!sibling->GetPrevContinuation(), "How did that happen?");

  if (aPrevSibling) {
    // The frame may be a special frame (a split inline frame that
    // contains a block).  Get the last part of that split.
    if (IsFrameSpecial(sibling)) {
      sibling = GetLastSpecialSibling(sibling, true);
    }

    // The frame may have a continuation. If so, we want the last
    // non-overflow-container continuation as our previous sibling.
    sibling = sibling->GetTailContinuation();
  }

  if (aTargetContent &&
      !IsValidSibling(sibling, aTargetContent, aTargetContentDisplay)) {
    sibling = nullptr;
  }

  return sibling;
}

nsIFrame*
nsCSSFrameConstructor::FindPreviousSibling(FlattenedChildIterator aIter,
                                           uint8_t& aTargetContentDisplay)
{
  nsIContent* child = aIter.Get();

  // Note: not all content objects are associated with a frame (e.g., if it's
  // `display: none') so keep looking until we find a previous frame
  while (nsIContent* sibling = aIter.GetPreviousChild()) {
    nsIFrame* prevSibling =
      FindFrameForContentSibling(sibling, child, aTargetContentDisplay, true);

    if (prevSibling) {
      // Found a previous sibling, we're done!
      return prevSibling;
    }
  }

  return nullptr;
}

nsIFrame*
nsCSSFrameConstructor::FindNextSibling(FlattenedChildIterator aIter,
                                       uint8_t& aTargetContentDisplay)
{
  nsIContent* child = aIter.Get();

  while (nsIContent* sibling = aIter.GetNextChild()) {
    nsIFrame* nextSibling =
      FindFrameForContentSibling(sibling, child, aTargetContentDisplay, false);

    if (nextSibling) {
      // We found a next sibling, we're done!
      return nextSibling;
    }
  }

  return nullptr;
}

// For fieldsets, returns the area frame, if the child is not a legend. 
static nsIFrame*
GetAdjustedParentFrame(nsIFrame*       aParentFrame,
                       nsIAtom*        aParentFrameType,
                       nsIContent*     aChildContent)
{
  NS_PRECONDITION(nsGkAtoms::tableOuterFrame != aParentFrameType,
                  "Shouldn't be happening!");
  
  nsIFrame* newParent = nullptr;

  if (nsGkAtoms::fieldSetFrame == aParentFrameType) {
    // If the parent is a fieldSet, use the fieldSet's area frame as the
    // parent unless the new content is a legend. 
    if (!aChildContent->IsHTML(nsGkAtoms::legend)) {
      newParent = GetFieldSetBlockFrame(aParentFrame);
    }
  }
  return (newParent) ? newParent : aParentFrame;
}

nsIFrame*
nsCSSFrameConstructor::GetInsertionPrevSibling(nsIFrame*& aParentFrame,
                                               nsIContent* aContainer,
                                               nsIContent* aChild,
                                               bool* aIsAppend,
                                               bool* aIsRangeInsertSafe,
                                               nsIContent* aStartSkipChild,
                                               nsIContent* aEndSkipChild)
{
  *aIsAppend = false;

  // Find the frame that precedes the insertion point. Walk backwards
  // from the parent frame to get the parent content, because if an
  // XBL insertion point is involved, we'll need to use _that_ to find
  // the preceding frame.

  NS_PRECONDITION(aParentFrame, "Must have parent frame to start with");
  nsIContent* container = aParentFrame->GetContent();

  FlattenedChildIterator iter(container);
  bool xblCase = iter.XBLInvolved() || container != aContainer;
  if (xblCase || !aChild->IsRootOfAnonymousSubtree()) {
    // The check for IsRootOfAnonymousSubtree() is because editor is
    // severely broken and calls us directly for native anonymous
    // nodes that it creates.
    if (aStartSkipChild) {
      iter.Seek(aStartSkipChild);
    } else {
      iter.Seek(aChild);
    }
  } else {
    // Prime the iterator for the call to FindPreviousSibling.
    iter.GetNextChild();
    NS_WARNING("Someone passed native anonymous content directly into frame "
               "construction.  Stop doing that!");
  }

  // Note that FindPreviousSibling is passed the iterator by value, so that
  // the later usage of the iterator starts from the same place.
  uint8_t childDisplay = UNSET_DISPLAY;
  nsIFrame* prevSibling = FindPreviousSibling(iter, childDisplay);

  // Now, find the geometric parent so that we can handle
  // continuations properly. Use the prev sibling if we have it;
  // otherwise use the next sibling.
  if (prevSibling) {
    aParentFrame = prevSibling->GetParent()->GetContentInsertionFrame();
  }
  else {
    // If there is no previous sibling, then find the frame that follows
    if (aEndSkipChild) {
      iter.Seek(aEndSkipChild);
      iter.GetPreviousChild();
    }
    nsIFrame* nextSibling = FindNextSibling(iter, childDisplay);

    if (nextSibling) {
      aParentFrame = nextSibling->GetParent()->GetContentInsertionFrame();
    }
    else {
      // No previous or next sibling, so treat this like an appended frame.
      *aIsAppend = true;
      if (IsFrameSpecial(aParentFrame)) {
        // Since we're appending, we'll walk to the last anonymous frame
        // that was created for the broken inline frame.  But don't walk
        // to the trailing inline if it's empty; stop at the block.
        aParentFrame = GetLastSpecialSibling(aParentFrame, false);
      }
      // Get continuation that parents the last child.  This MUST be done
      // before the AdjustAppendParentForAfterContent call.
      aParentFrame = nsLayoutUtils::LastContinuationWithChild(aParentFrame);
      // Deal with fieldsets
      aParentFrame = ::GetAdjustedParentFrame(aParentFrame,