/* 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/. */

#ifndef mozilla_ContentIterator_h
#define mozilla_ContentIterator_h

#include "js/GCAPI.h"
#include "mozilla/Maybe.h"
#include "mozilla/RangeBoundary.h"
#include "mozilla/RefPtr.h"
#include "nsCycleCollectionParticipant.h"
#include "nsINode.h"
#include "nsRange.h"
#include "nsTArray.h"

class nsIContent;

namespace mozilla {

/**
 * ContentIteratorBase is a base class of PostContentIterator,
 * PreContentIterator and ContentSubtreeIterator.  Making each concrete
 * classes "final", compiler can avoid virtual calls if they are treated
 * by the users directly.
 */
template <typename NodeType>
class ContentIteratorBase {
 public:
  ContentIteratorBase() = delete;
  ContentIteratorBase(const ContentIteratorBase&) = delete;
  ContentIteratorBase& operator=(const ContentIteratorBase&) = delete;
  virtual ~ContentIteratorBase();

  /**
   * Allows to iterate over the inclusive descendants
   * (https://dom.spec.whatwg.org/#concept-tree-inclusive-descendant) of
   * aRoot.
   */
  [[nodiscard]] virtual nsresult Init(nsINode* aRoot);

  /**
   * If you want to use `const AbstractRange*`, you can use an overload which
   * takes RawRangeBoundary instances or InitWithoutValidatingPoints().
   * If your range is dynamic, i.e., an nsRange, you can use
   * InitWithoutValidatingPoints() which skips comparing the boundary points.
   */
  [[nodiscard]] virtual nsresult Init(dom::AbstractRange* aRange);
  [[nodiscard]] virtual nsresult Init(nsINode* aStartContainer,
                                      uint32_t aStartOffset,
                                      nsINode* aEndContainer,
                                      uint32_t aEndOffset);
  [[nodiscard]] virtual nsresult Init(const RawRangeBoundary& aStart,
                                      const RawRangeBoundary& aEnd);
  [[nodiscard]] virtual nsresult InitWithoutValidatingPoints(
      const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd);
  virtual void First();
  virtual void Last();
  virtual void Next();
  virtual void Prev();

  nsINode* GetCurrentNode() const { return mCurNode; }

  bool IsDone() const { return !mCurNode; }

  [[nodiscard]] virtual nsresult PositionAt(nsINode* aCurNode);

 protected:
  enum class Order {
    Pre, /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)>.
          */
    Post /*!< <https://en.wikipedia.org/wiki/Tree_traversal#Post-order_(LRN)>.
          */
  };

  explicit ContentIteratorBase(Order aOrder);

  class Initializer;

  /**
   * Callers must guarantee that:
   * - Neither aStartContainer nor aEndContainer is nullptr.
   * - aStartOffset and aEndOffset are valid for its container.
   * - The start point and the end point are in document order.
   */
  [[nodiscard]] nsresult InitInternal(const RawRangeBoundary& aStart,
                                      const RawRangeBoundary& aEnd);

  // Recursively get the deepest first/last child of the node.  This will return
  // the node itself if it has no children.
  template <TreeKind>
  static nsINode* GetDeepFirstInclusiveDescendant(nsINode*);
  // If TreeKind::FlatForSelection, it'll continue with the shadow tree when it
  // reaches to a shadow host.
  template <TreeKind>
  static nsIContent* GetDeepFirstInclusiveDescendant(nsIContent*);
  template <TreeKind>
  static nsINode* GetDeepLastInclusiveDescendant(nsINode*);
  // If TreeKind::FlatForSelection, it'll continue with the shadow tree when it
  // reaches to a shadow host.
  template <TreeKind>
  static nsIContent* GetDeepLastInclusiveDescendant(nsIContent*);

  struct AncestorInfo {
    nsIContent* mAncestor = nullptr;
    // mIsDescendantInShadowTree is used to determine if we should go
    // dive into the shadow tree or regular light DOM tree if mAncestor
    // is a shadow host. It should always be false otherwise.
    bool mIsDescendantInShadowTree = false;
  };

  class InclusiveAncestorComparator {
   public:
    bool Equals(const AncestorInfo& aA, const nsINode* aB) const {
      return aA.mAncestor == aB;
    }
  };
  // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
  // etc.  Returns null if aNode and all its ancestors have no next/previous
  // sibling.
  //
  // If aAllowCrossShadowBoundary is true, it'll continue with the shadow host
  // when it reaches to a shadow root.
  template <TreeKind>
  static nsIContent* GetNextSibling(
      nsINode* aNode,
      nsTArray<AncestorInfo>* aInclusiveAncestorsOfEndContainer = nullptr);
  template <TreeKind>
  static nsIContent* GetPrevSibling(nsINode* aNode);

  template <TreeKind>
  nsINode* NextNode(nsINode* aNode);
  template <TreeKind>
  nsINode* PrevNode(nsINode* aNode);

  void SetEmpty();

  NodeType mCurNode = nullptr;
  NodeType mFirst = nullptr;
  NodeType mLast = nullptr;
  // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
  NodeType mClosestCommonInclusiveAncestor = nullptr;

  Maybe<nsMutationGuard> mMutationGuard;
  Maybe<JS::AutoAssertNoGC> mAssertNoGC;

  const Order mOrder;

  template <typename T>
  friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
                                          ContentIteratorBase<T>&, const char*,
                                          uint32_t);
  template <typename T>
  friend void ImplCycleCollectionUnlink(ContentIteratorBase<T>&);
};

// Each concrete class of ContentIteratorBase<RefPtr<nsINode>> may be owned by
// another class which may be owned by JS.  Therefore, all of them should be in
// the cycle collection.  However, we cannot make non-refcountable classes only
// with the macros.  So, we need to make them cycle collectable without the
// macros.
template <typename NodeType>
void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
                                 ContentIteratorBase<NodeType>& aField,
                                 const char* aName, uint32_t aFlags = 0) {
  ImplCycleCollectionTraverse(aCallback, aField.mCurNode, aName, aFlags);
  ImplCycleCollectionTraverse(aCallback, aField.mFirst, aName, aFlags);
  ImplCycleCollectionTraverse(aCallback, aField.mLast, aName, aFlags);
  ImplCycleCollectionTraverse(aCallback, aField.mClosestCommonInclusiveAncestor,
                              aName, aFlags);
}

template <typename NodeType>
void ImplCycleCollectionUnlink(ContentIteratorBase<NodeType>& aField) {
  ImplCycleCollectionUnlink(aField.mCurNode);
  ImplCycleCollectionUnlink(aField.mFirst);
  ImplCycleCollectionUnlink(aField.mLast);
  ImplCycleCollectionUnlink(aField.mClosestCommonInclusiveAncestor);
}

using SafeContentIteratorBase = ContentIteratorBase<RefPtr<nsINode>>;
using UnsafeContentIteratorBase = ContentIteratorBase<nsINode*>;

/**
 * A simple iterator class for traversing the content in "close tag" order.
 */
class PostContentIterator final : public SafeContentIteratorBase {
 public:
  PostContentIterator() : SafeContentIteratorBase(Order::Post) {}
  PostContentIterator(const PostContentIterator&) = delete;
  PostContentIterator& operator=(const PostContentIterator&) = delete;
  virtual ~PostContentIterator() = default;
  friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
                                          PostContentIterator&, const char*,
                                          uint32_t);
  friend void ImplCycleCollectionUnlink(PostContentIterator&);
};

/**
 * Different from PostContentIterator, UnsafePostContentIterator does not
 * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 * that script won't run while this is alive.
 */
class MOZ_STACK_CLASS UnsafePostContentIterator final
    : public UnsafeContentIteratorBase {
 public:
  UnsafePostContentIterator() : UnsafeContentIteratorBase(Order::Post) {}
  UnsafePostContentIterator(const UnsafePostContentIterator&) = delete;
  UnsafePostContentIterator& operator=(const UnsafePostContentIterator&) =
      delete;
  virtual ~UnsafePostContentIterator() = default;
};

/**
 * A simple iterator class for traversing the content in "start tag" order.
 */
class PreContentIterator final : public SafeContentIteratorBase {
 public:
  PreContentIterator() : ContentIteratorBase(Order::Pre) {}
  PreContentIterator(const PreContentIterator&) = delete;
  PreContentIterator& operator=(const PreContentIterator&) = delete;
  virtual ~PreContentIterator() = default;
  friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
                                          PreContentIterator&, const char*,
                                          uint32_t);
  friend void ImplCycleCollectionUnlink(PreContentIterator&);
};

/**
 * Different from PostContentIterator, UnsafePostContentIterator does not
 * grab nodes with strong pointers.  Therefore, the user needs to guarantee
 * that script won't run while this is alive.
 */
class MOZ_STACK_CLASS UnsafePreContentIterator final
    : public UnsafeContentIteratorBase {
 public:
  UnsafePreContentIterator() : UnsafeContentIteratorBase(Order::Pre) {}
  UnsafePreContentIterator(const UnsafePostContentIterator&) = delete;
  UnsafePreContentIterator& operator=(const UnsafePostContentIterator&) =
      delete;
  virtual ~UnsafePreContentIterator() = default;
};

/**
 *  A simple iterator class for traversing the content in "top subtree" order.
 */
class ContentSubtreeIterator final : public SafeContentIteratorBase {
 public:
  ContentSubtreeIterator() : SafeContentIteratorBase(Order::Pre) {}
  ContentSubtreeIterator(const ContentSubtreeIterator&) = delete;
  ContentSubtreeIterator& operator=(const ContentSubtreeIterator&) = delete;
  virtual ~ContentSubtreeIterator() = default;

  /**
   * Not supported.
   */
  [[nodiscard]] nsresult Init(nsINode* aRoot) override;

  /**
   * If you need to use const AbstractRange, use an overload which take
   * RawRangeBoundary instances.
   */
  [[nodiscard]] nsresult Init(dom::AbstractRange* aRange) override;

  /**
   * Initialize the iterator with aRange that does correct things
   * when the aRange's start and/or the end containers are
   * in shadow dom.
   *
   * If both start and end containers are in light dom, the iterator
   * won't do anything special.
   *
   * When the start container is in shadow dom, the iterator can
   * find the correct start node by crossing the shadow
   * boundary when needed.
   *
   * When the end container is in shadow dom, the iterator can find
   * the correct end node by crossing the shadow boundary when
   * needed. Also when the next node is an ancestor of
   * the end node, it can correctly iterate into the
   * subtree of it by crossing the shadow boundary.
   *
   * Examples of what nodes will be returned can be found
   * at test_content_iterator_subtree_shadow_tree.html.
   *
   * FIXME: This doesn't have a overload of this method which takes
   * `const RawRangeBoundary`s. That allows the callers to make this with
   * `const AbstractRange*`. So, it and its non-validation version (for
   * `const nsRange*` should be here.
   */
  [[nodiscard]] nsresult InitWithAllowCrossShadowBoundary(
      dom::AbstractRange* aRange);

  [[nodiscard]] nsresult Init(nsINode* aStartContainer, uint32_t aStartOffset,
                              nsINode* aEndContainer,
                              uint32_t aEndOffset) override;
  [[nodiscard]] nsresult Init(const RawRangeBoundary& aStartBoundary,
                              const RawRangeBoundary& aEndBoundary) override;
  [[nodiscard]] nsresult InitWithoutValidatingPoints(
      const RawRangeBoundary& aStart, const RawRangeBoundary& aEnd) override {
    // We need to create an nsRange from aStart and aEnd.  Therefore, anyway
    // nsRange will validate them.
    return Init(aStart, aEnd);
  }

  void Next() override;
  void Prev() override;
  // Must override these because we don't do PositionAt
  void First() override;
  // Must override these because we don't do PositionAt
  void Last() override;

  [[nodiscard]] nsresult PositionAt(nsINode* aCurNode) override;

  friend void ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback&,
                                          ContentSubtreeIterator&, const char*,
                                          uint32_t);
  friend void ImplCycleCollectionUnlink(ContentSubtreeIterator&);

 private:
  /**
   * See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
   */
  void CacheInclusiveAncestorsOfEndContainer();

  /**
   * @return may be nullptr.
   */
  nsIContent* DetermineCandidateForFirstContent() const;

  /**
   * @return may be nullptr.
   */
  nsIContent* DetermineCandidateForLastContent() const;

  /**
   * @return may be nullptr.
   */
  nsIContent* DetermineFirstContent() const;

  /**
   * @return may be nullptr.
   */
  nsIContent* DetermineLastContent() const;

  /**
   * Callers must guarantee that mRange isn't nullptr and is positioned.
   */
  [[nodiscard]] nsresult InitWithRange();

  // Returns the highest inclusive ancestor of aNode that's in the range
  // (possibly aNode itself).  Returns null if aNode is null, or is not itself
  // in the range.  A node is in the range if (node, 0) comes strictly after
  // the range endpoint, and (node, node.length) comes strictly before it, so
  // the range's start and end nodes will never be considered "in" it.
  nsIContent* GetTopAncestorInRange(nsINode* aNode) const;

  bool IterAllowCrossShadowBoundary() const {
    return mAllowCrossShadowBoundary == dom::AllowRangeCrossShadowBoundary::Yes;
  }

  RefPtr<dom::AbstractRange> mRange;

  // See <https://dom.spec.whatwg.org/#concept-tree-inclusive-ancestor>.
  AutoTArray<AncestorInfo, 8> mInclusiveAncestorsOfEndContainer;

  // Whether this iterator allows to iterate nodes across shadow boundary.
  dom::AllowRangeCrossShadowBoundary mAllowCrossShadowBoundary =
      dom::AllowRangeCrossShadowBoundary::No;
};

// The Subtree Content Iterator only returns subtrees that are
// completely within a given range. It doesn't return a CharacterData
// node that contains either the start or end point of the range.,
// nor does it return element nodes when nothing in the element is selected.
// We need an iterator that will also include these start/end points
// so that our methods/algorithms aren't cluttered with special
// case code that tries to include these points while iterating.
//
// The RangeSubtreeIterator class mimics the ContentSubtreeIterator
// methods we need, so should the Content Iterator support the
// start/end points in the future, we can switchover relatively
// easy.
class MOZ_STACK_CLASS RangeSubtreeIterator {
 private:
  enum RangeSubtreeIterState { eDone = 0, eUseStart, eUseIterator, eUseEnd };

  Maybe<ContentSubtreeIterator> mSubtreeIter;
  RangeSubtreeIterState mIterState;

  nsCOMPtr<nsINode> mStart;
  nsCOMPtr<nsINode> mEnd;

 public:
  RangeSubtreeIterator() : mIterState(eDone) {}
  ~RangeSubtreeIterator() = default;

  [[nodiscard]] nsresult Init(dom::AbstractRange* aRange,
                              dom::AllowRangeCrossShadowBoundary =
                                  dom::AllowRangeCrossShadowBoundary::No);
  already_AddRefed<nsINode> GetCurrentNode();
  void First();
  void Last();
  void Next();
  void Prev();

  bool IsDone() { return mIterState == eDone; }
};
}  // namespace mozilla

#endif  // #ifndef mozilla_ContentIterator_h