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 "nsLayoutUtils.h"
  11 #include "nsIContent.h"
  12
  13 void nsGenConList::Clear() {
  14   // Delete entire list.
  15   mNodes.Clear();
  16   while (nsGenConNode* node = mList.popFirst()) {
  17     delete node;
  18   }
  19   mSize = 0;
  20   mLastInserted = nullptr;
  21 }
  22
  23 bool nsGenConList::DestroyNodesFor(nsIFrame* aFrame) {
  24   // This algorithm relies on the invariant that nodes of a frame are
  25   // put contiguously in the linked list. This is guaranteed because
  26   // each frame is mapped to only one (nsIContent, pseudoType) pair,
  27   // and the nodes in the linked list are put in the tree order based
  28   // on that pair and offset inside frame.
  29   nsGenConNode* node = mNodes.GetAndRemove(aFrame).valueOr(nullptr);
  30   if (!node) {
  31     return false;
  32   }
  33   MOZ_ASSERT(node->mPseudoFrame == aFrame);
  34
  35   while (node && node->mPseudoFrame == aFrame) {
  36     nsGenConNode* nextNode = Next(node);
  37     Destroy(node);
  38     node = nextNode;
  39   }
  40
  41   // Modification of the list invalidates the cached pointer.
  42   mLastInserted = nullptr;
  43
  44   return true;
  45 }
  46
  47 /**
  48  * Compute the type of the pseudo and the content for the pseudo that
  49  * we'll use for comparison purposes.
  50  * @param aContent the content to use is stored here; it's the element
  51  * that generated the pseudo, or (if not for generated content), the frame's
  52  * own element
  53  * @return -2 for ::marker, -1 for ::before, +1 for ::after, and 0 otherwise.
  54  */
  55 inline int32_t PseudoCompareType(nsIFrame* aFrame, nsIContent** aContent) {
  56   auto pseudo = aFrame->Style()->GetPseudoType();
  57   if (pseudo == mozilla::PseudoStyleType::marker) {
  58     *aContent = aFrame->GetContent()->GetParent();
  59     return -2;
  60   }
  61   if (pseudo == mozilla::PseudoStyleType::before) {
  62     *aContent = aFrame->GetContent()->GetParent();
  63     return -1;
  64   }
  65   if (pseudo == mozilla::PseudoStyleType::after) {
  66     *aContent = aFrame->GetContent()->GetParent();
  67     return 1;
  68   }
  69   *aContent = aFrame->GetContent();
  70   return 0;
  71 }
  72
  73 #ifdef DEBUG
  74 static bool IsXBLInvolved(nsIContent* aContent1, nsIContent* aContent2) {
  75   auto* ancestor = nsContentUtils::GetCommonAncestor(aContent1, aContent2);
  76   return ancestor && ancestor->IsElement() &&
  77          ancestor->AsElement()->GetXBLBinding();
  78 }
  79 #endif
  80
  81 /* static */
  82 bool nsGenConList::NodeAfter(const nsGenConNode* aNode1,
  83                              const nsGenConNode* aNode2) {
  84   nsIFrame* frame1 = aNode1->mPseudoFrame;
  85   nsIFrame* frame2 = aNode2->mPseudoFrame;
  86   if (frame1 == frame2) {
  87     NS_ASSERTION(aNode2->mContentIndex != aNode1->mContentIndex, "identical");
  88     return aNode1->mContentIndex > aNode2->mContentIndex;
  89   }
  90   nsIContent* content1;
  91   nsIContent* content2;
  92   int32_t pseudoType1 = PseudoCompareType(frame1, &content1);
  93   int32_t pseudoType2 = PseudoCompareType(frame2, &content2);
  94   if (content1 == content2) {
  95     NS_ASSERTION(pseudoType1 != pseudoType2, "identical");
  96     if (pseudoType1 == 0 || pseudoType2 == 0) {
  97       return pseudoType2 == 0;
  98     }
  99     return pseudoType1 > pseudoType2;
 100   }
 101
 102   // Two pseudo-elements of different elements, we want to treat them as if
 103   // they were normal elements and just use tree order.
 104   content1 = frame1->GetContent();
 105   content2 = frame2->GetContent();
 106
 107   int32_t cmp = nsLayoutUtils::CompareTreePosition(content1, content2);
 108   // DoCompareTreePosition doesn't know about XBL anonymous content, and we
 109   // probably shouldn't bother teaching it about it.
 110   MOZ_ASSERT(cmp != 0 || IsXBLInvolved(content1, content2),
 111              "same content, different frames");
 112   return cmp > 0;
 113 }
 114
 115 void nsGenConList::Insert(nsGenConNode* aNode) {
 116   // Check for append.
 117   if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
 118     mList.insertBack(aNode);
 119   } else if (mLastInserted && mLastInserted != mList.getLast() &&
 120              NodeAfter(aNode, mLastInserted) &&
 121              NodeAfter(Next(mLastInserted), aNode)) {
 122     // Fast path for inserting many consecutive nodes in one place
 123     mLastInserted->setNext(aNode);
 124   } else {
 125     // Binary search.
 126
 127     // the range of indices at which |aNode| could end up.
 128     // (We already know it can't be at index mSize.)
 129     uint32_t first = 0, last = mSize - 1;
 130
 131     // A cursor to avoid walking more than the length of the list.
 132     nsGenConNode* curNode = mList.getLast();
 133     uint32_t curIndex = mSize - 1;
 134
 135     while (first != last) {
 136       uint32_t test = (first + last) / 2;
 137       if (last == curIndex) {
 138         for (; curIndex != test; --curIndex) curNode = Prev(curNode);
 139       } else {
 140         for (; curIndex != test; ++curIndex) curNode = Next(curNode);
 141       }
 142
 143       if (NodeAfter(aNode, curNode)) {
 144         first = test + 1;
 145         // if we exit the loop, we need curNode to be right
 146         ++curIndex;
 147         curNode = Next(curNode);
 148       } else {
 149         last = test;
 150       }
 151     }
 152     curNode->setPrevious(aNode);
 153   }
 154   ++mSize;
 155
 156   mLastInserted = aNode;
 157
 158   // Set the mapping only if it is the first node of the frame.
 159   // The DEBUG blocks below are for ensuring the invariant required by
 160   // nsGenConList::DestroyNodesFor. See comment there.
 161   if (IsFirst(aNode) || Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
 162 #ifdef DEBUG
 163     if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
 164       MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
 165                  "oldFrameFirstNode should now be immediately after "
 166                  "the newly-inserted one.");
 167     } else {
 168       // If the node is not the only node in the list.
 169       if (!IsFirst(aNode) || !IsLast(aNode)) {
 170         nsGenConNode* nextNode = Next(aNode);
 171         MOZ_ASSERT(!nextNode || nextNode->mPseudoFrame != aNode->mPseudoFrame,
 172                    "There shouldn't exist any node for this frame.");
 173         // If the node is neither the first nor the last node
 174         if (!IsFirst(aNode) && !IsLast(aNode)) {
 175           MOZ_ASSERT(Prev(aNode)->mPseudoFrame != nextNode->mPseudoFrame,
 176                      "New node should not break contiguity of nodes of "
 177                      "the same frame.");
 178         }
 179       }
 180     }
 181 #endif
 182     mNodes.Put(aNode->mPseudoFrame, aNode);
 183   } else {
 184 #ifdef DEBUG
 185     nsGenConNode* frameFirstNode = mNodes.Get(aNode->mPseudoFrame);
 186     MOZ_ASSERT(frameFirstNode, "There should exist node map for the frame.");
 187     for (nsGenConNode* curNode = Prev(aNode); curNode != frameFirstNode;
 188          curNode = Prev(curNode)) {
 189       MOZ_ASSERT(curNode->mPseudoFrame == aNode->mPseudoFrame,
 190                  "Every node between frameFirstNode and the new node inserted "
 191                  "should refer to the same frame.");
 192       MOZ_ASSERT(!IsFirst(curNode),
 193                  "The newly-inserted node should be in a contiguous run after "
 194                  "frameFirstNode, thus frameFirstNode should be reached before "
 195                  "the first node of mList.");
 196     }
 197 #endif
 198   }
 199
 200   NS_ASSERTION(IsFirst(aNode) || NodeAfter(aNode, Prev(aNode)),
 201                "sorting error");
 202   NS_ASSERTION(IsLast(aNode) || NodeAfter(Next(aNode), aNode), "sorting error");
 203 }