/* -*- 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
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/* 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()->ContentCount()) ||
          // 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");
}