tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

nsGenConList.cpp (8480B)

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