Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
/* base class for nsCounterList and nsQuoteList */
#include "nsGenConList.h"
#include "nsContentUtils.h"
#include "nsIContent.h"
#include "nsIFrame.h"
void nsGenConNode::CheckFrameAssertions() {
NS_ASSERTION(mContentIndex < int32_t(mPseudoFrame->StyleContent()
->NonAltContentItems()
.Length()) ||
// Special-case for the USE node created for the legacy
// markers, which don't use the content property.
mContentIndex == 0,
"index out of range");
// We allow negative values of mContentIndex for 'counter-reset' and
// 'counter-increment'.
NS_ASSERTION(mContentIndex < 0 ||
mPseudoFrame->Style()->GetPseudoType() ==
mozilla::PseudoStyleType::before ||
mPseudoFrame->Style()->GetPseudoType() ==
mozilla::PseudoStyleType::after ||
mPseudoFrame->Style()->GetPseudoType() ==
mozilla::PseudoStyleType::marker,
"not CSS generated content and not counter change");
NS_ASSERTION(mContentIndex < 0 ||
mPseudoFrame->HasAnyStateBits(NS_FRAME_GENERATED_CONTENT),
"not generated content and not counter change");
}
void nsGenConList::Clear() {
// Delete entire list.
mNodes.Clear();
while (nsGenConNode* node = mList.popFirst()) {
delete node;
}
mSize = 0;
mLastInserted = nullptr;
}
bool nsGenConList::DestroyNodesFor(nsIFrame* aFrame) {
// This algorithm relies on the invariant that nodes of a frame are
// put contiguously in the linked list. This is guaranteed because
// each frame is mapped to only one (nsIContent, pseudoType) pair,
// and the nodes in the linked list are put in the tree order based
// on that pair and offset inside frame.
nsGenConNode* node = mNodes.Extract(aFrame).valueOr(nullptr);
if (!node) {
return false;
}
MOZ_ASSERT(node->mPseudoFrame == aFrame);
while (node && node->mPseudoFrame == aFrame) {
nsGenConNode* nextNode = Next(node);
Destroy(node);
node = nextNode;
}
// Modification of the list invalidates the cached pointer.
mLastInserted = nullptr;
return true;
}
/**
* Compute the type of the pseudo and the content for the pseudo that
* we'll use for comparison purposes.
* @param aContent the content to use is stored here; it's the element
* that generated the pseudo, or (if not for generated content), the frame's
* own element
* @return -2 for ::marker, -1 for ::before, +1 for ::after, and 0 otherwise.
*/
inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent) {
auto pseudo = aFrame->Style()->GetPseudoType();
if (pseudo == mozilla::PseudoStyleType::marker) {
*aContent = aFrame->GetContent()->GetParent();
return -2;
}
if (pseudo == mozilla::PseudoStyleType::before) {
*aContent = aFrame->GetContent()->GetParent();
return -1;
}
if (pseudo == mozilla::PseudoStyleType::after) {
*aContent = aFrame->GetContent()->GetParent();
return 1;
}
*aContent = aFrame->GetContent();
return 0;
}
/* static */
bool nsGenConList::NodeAfter(const nsGenConNode* aNode1,
const nsGenConNode* aNode2) {
nsIFrame* frame1 = aNode1->mPseudoFrame;
nsIFrame* frame2 = aNode2->mPseudoFrame;
if (frame1 == frame2) {
NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
return aNode1->mContentIndex > aNode2->mContentIndex;
}
nsIContent* content1;
nsIContent* content2;
int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
if (content1 == content2) {
NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
if (pseudoType1 == 0 || pseudoType2 == 0) {
return pseudoType2 == 0;
}
return pseudoType1 > pseudoType2;
}
// Two pseudo-elements of different elements, we want to treat them as if
// they were normal elements and just use tree order.
content1 = frame1->GetContent();
content2 = frame2->GetContent();
int32_t cmp = nsContentUtils::CompareTreePosition<TreeKind::Flat>(
content1, content2, /* aCommonAncestor = */ nullptr);
MOZ_ASSERT(cmp != 0, "same content, different frames");
return cmp > 0;
}
nsGenConNode* nsGenConList::BinarySearch(
const mozilla::FunctionRef<bool(nsGenConNode*)>& aIsAfter) {
if (mList.isEmpty()) {
return nullptr;
}
// The range of indices at which |aNode| could end up.
// (We already know it can't be at index mSize.)
uint32_t first = 0, last = mSize - 1;
// A cursor to avoid walking more than the length of the list.
nsGenConNode* curNode = mList.getLast();
uint32_t curIndex = mSize - 1;
while (first != last) {
uint32_t test = first + (last - first) / 2;
if (last == curIndex) {
for (; curIndex != test; --curIndex) {
curNode = Prev(curNode);
}
} else {
for (; curIndex != test; ++curIndex) {
curNode = Next(curNode);
}
}
if (aIsAfter(curNode)) {
first = test + 1;
// if we exit the loop, we need curNode to be right
++curIndex;
curNode = Next(curNode);
} else {
last = test;
}
}
return curNode;
}
void nsGenConList::Insert(nsGenConNode* aNode) {
// Check for append.
if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
mList.insertBack(aNode);
} else if (mLastInserted && mLastInserted != mList.getLast() &&
NodeAfter(aNode, mLastInserted) &&
NodeAfter(Next(mLastInserted), aNode)) {
// Fast path for inserting many consecutive nodes in one place
mLastInserted->setNext(aNode);
} else {
auto IsAfter = [aNode](nsGenConNode* curNode) {
return NodeAfter(aNode, curNode);
};
auto* insertionNode = BinarySearch(IsAfter);
insertionNode->setPrevious(aNode);
}
++mSize;
mLastInserted = aNode;
// Set the mapping only if it is the first node of the frame.
// The DEBUG blocks below are for ensuring the invariant required by
// nsGenConList::DestroyNodesFor. See comment there.
if (IsFirst(aNode) || Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
#ifdef DEBUG
if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
"oldFrameFirstNode should now be immediately after "
"the newly-inserted one.");
} else {
// If the node is not the only node in the list.
if (!IsFirst(aNode) || !IsLast(aNode)) {
nsGenConNode* nextNode = Next(aNode);
MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
"There shouldn't exist any node for this frame.");
// If the node is neither the first nor the last node
if (!IsFirst(aNode) && !IsLast(aNode)) {
MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
"New node should not break contiguity of nodes of "
"the same frame.");
}
}
}
#endif
mNodes.InsertOrUpdate(aNode->mPseudoFrame, aNode);
} else {
#ifdef DEBUG
nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
for (nsGenConNode* curNode = Prev(aNode); curNode != frameFirstNode;
curNode = Prev(curNode)) {
MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
"Every node between frameFirstNode and the new node inserted "
"should refer to the same frame.");
MOZ_ASSERT(!IsFirst(curNode),
"The newly-inserted node should be in a contiguous run after "
"frameFirstNode, thus frameFirstNode should be reached before "
"the first node of mList.");
}
#endif
}
NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
"sorting error");
NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode), "sorting error");
}