layout/base/nsGenConList.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* base class for nsCounterList and nsQuoteList */
   8
   9 #include "nsGenConList.h"
  10 #include "nsContentUtils.h"
  11 #include "nsIContent.h"
  12 #include "nsIFrame.h"
  13
  14 void nsGenConNode::CheckFrameAssertions() {
  15   NS_ASSERTION(
  16       mContentIndex < int32_t(mPseudoFrame->StyleContent()->ContentCount()) ||
  17           // Special-case for the USE node created for the legacy markers,
  18           // which don't use the content property.
  19           mContentIndex == 0,
  20       "index out of range");
  21   // We allow negative values of mContentIndex for 'counter-reset' and
  22   // 'counter-increment'.
  23
  24   NS_ASSERTION(mContentIndex < 0 ||
  25                    mPseudoFrame->Style()->GetPseudoType() ==
  26                        mozilla::PseudoStyleType::before ||
  27                    mPseudoFrame->Style()->GetPseudoType() ==
  28                        mozilla::PseudoStyleType::after ||
  29                    mPseudoFrame->Style()->GetPseudoType() ==
  30                        mozilla::PseudoStyleType::marker,
  31                "not CSS generated content and not counter change");
  32   NS_ASSERTION(mContentIndex < 0 ||
  33                    mPseudoFrame->HasAnyStateBits(NS_FRAME_GENERATED_CONTENT),
  34                "not generated content and not counter change");
  35 }
  36
  37 void nsGenConList::Clear() {
  38   // Delete entire list.
  39   mNodes.Clear();
  40   while (nsGenConNode* node = mList.popFirst()) {
  41     delete node;
  42   }
  43   mSize = 0;
  44   mLastInserted = nullptr;
  45 }
  46
  47 bool nsGenConList::DestroyNodesFor(nsIFrame* aFrame) {
  48   // This algorithm relies on the invariant that nodes of a frame are
  49   // put contiguously in the linked list. This is guaranteed because
  50   // each frame is mapped to only one (nsIContent, pseudoType) pair,
  51   // and the nodes in the linked list are put in the tree order based
  52   // on that pair and offset inside frame.
  53   nsGenConNode* node = mNodes.Extract(aFrame).valueOr(nullptr);
  54   if (!node) {
  55     return false;
  56   }
  57   MOZ_ASSERT(node->mPseudoFrame == aFrame);
  58
  59   while (node && node->mPseudoFrame == aFrame) {
  60     nsGenConNode* nextNode = Next(node);
  61     Destroy(node);
  62     node = nextNode;
  63   }
  64
  65   // Modification of the list invalidates the cached pointer.
  66   mLastInserted = nullptr;
  67
  68   return true;
  69 }
  70
  71 /**
  72  * Compute the type of the pseudo and the content for the pseudo that
  73  * we'll use for comparison purposes.
  74  * @param aContent the content to use is stored here; it's the element
  75  * that generated the pseudo, or (if not for generated content), the frame's
  76  * own element
  77  * @return -2 for ::marker, -1 for ::before, +1 for ::after, and 0 otherwise.
  78  */
  79 inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent) {
  80   auto pseudo = aFrame->Style()->GetPseudoType();
  81   if (pseudo == mozilla::PseudoStyleType::marker) {
  82     *aContent = aFrame->GetContent()->GetParent();
  83     return -2;
  84   }
  85   if (pseudo == mozilla::PseudoStyleType::before) {
  86     *aContent = aFrame->GetContent()->GetParent();
  87     return -1;
  88   }
  89   if (pseudo == mozilla::PseudoStyleType::after) {
  90     *aContent = aFrame->GetContent()->GetParent();
  91     return 1;
  92   }
  93   *aContent = aFrame->GetContent();
  94   return 0;
  95 }
  96
  97 /* static */
  98 bool nsGenConList::NodeAfter(const nsGenConNode* aNode1,
  99                              const nsGenConNode* aNode2) {
 100   nsIFrame* frame1 = aNode1->mPseudoFrame;
 101   nsIFrame* frame2 = aNode2->mPseudoFrame;
 102   if (frame1 == frame2) {
 103     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
 104     return aNode1->mContentIndex > aNode2->mContentIndex;
 105   }
 106   nsIContent* content1;
 107   nsIContent* content2;
 108   int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
 109   int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
 110   if (content1 == content2) {
 111     NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
 112     if (pseudoType1 == 0 || pseudoType2 == 0) {
 113       return pseudoType2 == 0;
 114     }
 115     return pseudoType1 > pseudoType2;
 116   }
 117
 118   // Two pseudo-elements of different elements, we want to treat them as if
 119   // they were normal elements and just use tree order.
 120   content1 = frame1->GetContent();
 121   content2 = frame2->GetContent();
 122
 123   int32_t cmp = nsContentUtils::CompareTreePosition<TreeKind::Flat>(
 124       content1, content2, /* aCommonAncestor = */ nullptr);
 125   MOZ_ASSERT(cmp != 0, "same content, different frames");
 126   return cmp > 0;
 127 }
 128
 129 nsGenConNode* nsGenConList::BinarySearch(
 130     const mozilla::FunctionRef<bool(nsGenConNode*)>& aIsAfter) {
 131   if (mList.isEmpty()) {
 132     return nullptr;
 133   }
 134
 135   // The range of indices at which |aNode| could end up.
 136   // (We already know it can't be at index mSize.)
 137   uint32_t first = 0, last = mSize - 1;
 138
 139   // A cursor to avoid walking more than the length of the list.
 140   nsGenConNode* curNode = mList.getLast();
 141   uint32_t curIndex = mSize - 1;
 142
 143   while (first != last) {
 144     uint32_t test = first + (last - first) / 2;
 145     if (last == curIndex) {
 146       for (; curIndex != test; --curIndex) curNode = Prev(curNode);
 147     } else {
 148       for (; curIndex != test; ++curIndex) curNode = Next(curNode);
 149     }
 150
 151     if (aIsAfter(curNode)) {
 152       first = test + 1;
 153       // if we exit the loop, we need curNode to be right
 154       ++curIndex;
 155       curNode = Next(curNode);
 156     } else {
 157       last = test;
 158     }
 159   }
 160
 161   return curNode;
 162 }
 163
 164 void nsGenConList::Insert(nsGenConNode* aNode) {
 165   // Check for append.
 166   if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
 167     mList.insertBack(aNode);
 168   } else if (mLastInserted && mLastInserted != mList.getLast() &&
 169              NodeAfter(aNode, mLastInserted) &&
 170              NodeAfter(Next(mLastInserted), aNode)) {
 171     // Fast path for inserting many consecutive nodes in one place
 172     mLastInserted->setNext(aNode);
 173   } else {
 174     auto IsAfter = [aNode](nsGenConNode* curNode) {
 175       return NodeAfter(aNode, curNode);
 176     };
 177     auto* insertionNode = BinarySearch(IsAfter);
 178     insertionNode->setPrevious(aNode);
 179   }
 180   ++mSize;
 181
 182   mLastInserted = aNode;
 183
 184   // Set the mapping only if it is the first node of the frame.
 185   // The DEBUG blocks below are for ensuring the invariant required by
 186   // nsGenConList::DestroyNodesFor. See comment there.
 187   if (IsFirst(aNode) || Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
 188 #ifdef DEBUG
 189     if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
 190       MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
 191                  "oldFrameFirstNode should now be immediately after "
 192                  "the newly-inserted one.");
 193     } else {
 194       // If the node is not the only node in the list.
 195       if (!IsFirst(aNode) || !IsLast(aNode)) {
 196         nsGenConNode* nextNode = Next(aNode);
 197         MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
 198                    "There shouldn't exist any node for this frame.");
 199         // If the node is neither the first nor the last node
 200         if (!IsFirst(aNode) && !IsLast(aNode)) {
 201           MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
 202                      "New node should not break contiguity of nodes of "
 203                      "the same frame.");
 204         }
 205       }
 206     }
 207 #endif
 208     mNodes.InsertOrUpdate(aNode->mPseudoFrame, aNode);
 209   } else {
 210 #ifdef DEBUG
 211     nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
 212     MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
 213     for (nsGenConNode* curNode = Prev(aNode); curNode != frameFirstNode;
 214          curNode = Prev(curNode)) {
 215       MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
 216                  "Every node between frameFirstNode and the new node inserted "
 217                  "should refer to the same frame.");
 218       MOZ_ASSERT(!IsFirst(curNode),
 219                  "The newly-inserted node should be in a contiguous run after "
 220                  "frameFirstNode, thus frameFirstNode should be reached before "
 221                  "the first node of mList.");
 222     }
 223 #endif
 224   }
 225
 226   NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
 227                "sorting error");
 228   NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode), "sorting error");
 229 }