Bug 1343596 - Part 2: Refactor nsDisplayList sorting
MozReview-Commit-ID: DlUSf0iQm06
--- a/layout/painting/nsDisplayList.cpp
+++ b/layout/painting/nsDisplayList.cpp
@@ -2477,102 +2477,77 @@ void nsDisplayList::HitTest(nsDisplayLis
}
}
// Clear any remaining preserve-3d transforms.
FlushFramesArray(temp, aOutFrames);
NS_ASSERTION(aState->mItemBuffer.Length() == uint32_t(itemBufferStart),
"How did we forget to pop some elements?");
}
-static void Sort(nsDisplayList* aList, int32_t aCount, nsDisplayList::SortLEQ aCmp,
- void* aClosure) {
- if (aCount < 2)
- return;
-
- nsDisplayList list1;
- nsDisplayList list2;
- int i;
- int32_t half = aCount/2;
- bool sorted = true;
- nsDisplayItem* prev = nullptr;
- for (i = 0; i < aCount; ++i) {
- nsDisplayItem* item = aList->RemoveBottom();
- (i < half ? &list1 : &list2)->AppendToTop(item);
- if (sorted && prev && !aCmp(prev, item, aClosure)) {
- sorted = false;
- }
- prev = item;
- }
- if (sorted) {
- aList->AppendToTop(&list1);
- aList->AppendToTop(&list2);
- return;
- }
-
- Sort(&list1, half, aCmp, aClosure);
- Sort(&list2, aCount - half, aCmp, aClosure);
-
- for (i = 0; i < aCount; ++i) {
- if (list1.GetBottom() &&
- (!list2.GetBottom() ||
- aCmp(list1.GetBottom(), list2.GetBottom(), aClosure))) {
- aList->AppendToTop(list1.RemoveBottom());
- } else {
- aList->AppendToTop(list2.RemoveBottom());
- }
- }
-}
-
static nsIContent* FindContentInDocument(nsDisplayItem* aItem, nsIDocument* aDoc) {
nsIFrame* f = aItem->Frame();
while (f) {
nsPresContext* pc = f->PresContext();
if (pc->Document() == aDoc) {
return f->GetContent();
}
f = nsLayoutUtils::GetCrossDocParentFrame(pc->PresShell()->GetRootFrame());
}
return nullptr;
}
-static bool IsContentLEQ(nsDisplayItem* aItem1, nsDisplayItem* aItem2,
- void* aClosure) {
- nsIContent* commonAncestor = static_cast<nsIContent*>(aClosure);
- // It's possible that the nsIContent for aItem1 or aItem2 is in a subdocument
- // of commonAncestor, because display items for subdocuments have been
- // mixed into the same list. Ensure that we're looking at content
- // in commonAncestor's document.
- nsIDocument* commonAncestorDoc = commonAncestor->OwnerDoc();
- nsIContent* content1 = FindContentInDocument(aItem1, commonAncestorDoc);
- nsIContent* content2 = FindContentInDocument(aItem2, commonAncestorDoc);
- if (!content1 || !content2) {
- NS_ERROR("Document trees are mixed up!");
- // Something weird going on
- return true;
- }
- return nsLayoutUtils::CompareTreePosition(content1, content2, commonAncestor) <= 0;
-}
-
-static bool IsZOrderLEQ(nsDisplayItem* aItem1, nsDisplayItem* aItem2,
- void* aClosure) {
- // Note that we can't just take the difference of the two
- // z-indices here, because that might overflow a 32-bit int.
- return aItem1->ZIndex() <= aItem2->ZIndex();
-}
+struct ZSortItem {
+ nsDisplayItem* item;
+ int32_t zIndex;
+
+ explicit ZSortItem(nsDisplayItem* aItem)
+ : item(aItem), zIndex(aItem->ZIndex()) {}
+
+ operator nsDisplayItem*() {
+ return item;
+ }
+};
+
+struct ZOrderComparator {
+ bool operator()(const ZSortItem& aLeft, const ZSortItem& aRight) const {
+ // Note that we can't just take the difference of the two
+ // z-indices here, because that might overflow a 32-bit int.
+ return aLeft.zIndex < aRight.zIndex;
+ }
+};
void nsDisplayList::SortByZOrder() {
- Sort(IsZOrderLEQ, nullptr);
-}
+ Sort<ZSortItem>(ZOrderComparator());
+}
+
+struct ContentComparator {
+ nsIContent* mCommonAncestor;
+
+ explicit ContentComparator(nsIContent* aCommonAncestor)
+ : mCommonAncestor(aCommonAncestor) {}
+
+ bool operator()(nsDisplayItem* aLeft, nsDisplayItem* aRight) const {
+ // It's possible that the nsIContent for aItem1 or aItem2 is in a subdocument
+ // of commonAncestor, because display items for subdocuments have been
+ // mixed into the same list. Ensure that we're looking at content
+ // in commonAncestor's document.
+ nsIDocument* commonAncestorDoc = mCommonAncestor->OwnerDoc();
+ nsIContent* content1 = FindContentInDocument(aLeft, commonAncestorDoc);
+ nsIContent* content2 = FindContentInDocument(aRight, commonAncestorDoc);
+ if (!content1 || !content2) {
+ NS_ERROR("Document trees are mixed up!");
+ // Something weird going on
+ return true;
+ }
+ return nsLayoutUtils::CompareTreePosition(content1, content2, mCommonAncestor) < 0;
+ }
+};
void nsDisplayList::SortByContentOrder(nsIContent* aCommonAncestor) {
- Sort(IsContentLEQ, aCommonAncestor);
-}
-
-void nsDisplayList::Sort(SortLEQ aCmp, void* aClosure) {
- ::Sort(this, Count(), aCmp, aClosure);
+ Sort<nsDisplayItem*>(ContentComparator(aCommonAncestor));
}
nsDisplayItem::nsDisplayItem(nsDisplayListBuilder* aBuilder, nsIFrame* aFrame)
: nsDisplayItem(aBuilder, aFrame,
aBuilder->CurrentActiveScrolledRoot())
{}
nsDisplayItem::nsDisplayItem(nsDisplayListBuilder* aBuilder, nsIFrame* aFrame,
--- a/layout/painting/nsDisplayList.h
+++ b/layout/painting/nsDisplayList.h
@@ -2323,24 +2323,36 @@ public:
* @param aCommonAncestor a common ancestor of all the content elements
* associated with the display items, for speeding up tree order
* checks, or nullptr if not known; it's only a hint, if it is not an
* ancestor of some elements, then we lose performance but not correctness
*/
void SortByContentOrder(nsIContent* aCommonAncestor);
/**
- * Generic stable sort. Take care, because some of the items might be nsDisplayLists
- * themselves.
- * aCmp(item1, item2) should return true if item1 <= item2. We sort the items
- * into increasing order.
+ * Sort the display list using a stable sort. Take care, because some of the
+ * items might be nsDisplayLists themselves.
+ * aComparator(Item item1, Item item2) should return true if item1 should go
+ * before item2.
+ * We sort the items into increasing order.
*/
- typedef bool (* SortLEQ)(nsDisplayItem* aItem1, nsDisplayItem* aItem2,
- void* aClosure);
- void Sort(SortLEQ aCmp, void* aClosure);
+ template<typename Item, typename Comparator>
+ void Sort(const Comparator& aComparator) {
+ nsTArray<Item> items;
+
+ while (nsDisplayItem* item = RemoveBottom()) {
+ items.AppendElement(Item(item));
+ }
+
+ std::stable_sort(items.begin(), items.end(), aComparator);
+
+ for (Item& item : items) {
+ AppendToTop(item);
+ }
+ }
/**
* Compute visiblity for the items in the list.
* We put this logic here so it can be shared by top-level
* painting and also display items that maintain child lists.
* This is also a good place to put ComputeVisibility-related logic
* that must be applied to every display item. In particular, this
* sets mVisibleRect on each display item.
--- a/layout/tables/nsTableFrame.cpp
+++ b/layout/tables/nsTableFrame.cpp
@@ -1300,21 +1300,21 @@ GetTablePartRank(nsDisplayItem* aItem)
return 0;
if (type == nsGkAtoms::tableRowGroupFrame)
return 1;
if (type == nsGkAtoms::tableRowFrame)
return 2;
return 3;
}
-static bool CompareByTablePartRank(nsDisplayItem* aItem1, nsDisplayItem* aItem2,
- void* aClosure)
-{
- return GetTablePartRank(aItem1) <= GetTablePartRank(aItem2);
-}
+struct TablePartRankComparator {
+ bool operator()(nsDisplayItem* aItem1, nsDisplayItem* aItem2) const {
+ return GetTablePartRank(aItem1) < GetTablePartRank(aItem2);
+ }
+};
/* static */ void
nsTableFrame::GenericTraversal(nsDisplayListBuilder* aBuilder, nsFrame* aFrame,
const nsRect& aDirtyRect, const nsDisplayListSet& aLists)
{
// This is similar to what nsContainerFrame::BuildDisplayListForNonBlockChildren
// does, except that we allow the children's background and borders to go
// in our BorderBackground list. This doesn't really affect background
@@ -1380,34 +1380,34 @@ nsTableFrame::DisplayGenericTablePart(ns
}
aTraversal(aBuilder, aFrame, aDirtyRect, *lists);
if (sortEventBackgrounds) {
// Ensure that the table frame event background goes before the
// table rowgroups event backgrounds, before the table row event backgrounds,
// before everything else (cells and their blocks)
- separatedCollection.BorderBackground()->Sort(CompareByTablePartRank, nullptr);
+ separatedCollection.BorderBackground()->Sort<nsDisplayItem*>(TablePartRankComparator());
separatedCollection.MoveTo(aLists);
}
aFrame->DisplayOutline(aBuilder, aLists);
}
static inline bool FrameHasBorderOrBackground(nsTableFrame* tableFrame, nsIFrame* f)
{
if (!f->StyleVisibility()->IsVisible()) {
return false;
}
if (f->StyleBorder()->HasBorder()) {
return true;
}
if (!f->StyleBackground()->IsTransparent(f) ||
f->StyleDisplay()->mAppearance) {
-
+
nsTableCellFrame *cellFrame = do_QueryFrame(f);
// We could also return false here if the current frame is the root
// of a pseudo stacking context
if (cellFrame && !tableFrame->IsBorderCollapse()) {
return false;
}
return true;
}