sousa-gecko/dom/base/TextDirectiveCreator.h

/* 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 DOM_TEXTDIRECTIVECREATOR_H_
#define DOM_TEXTDIRECTIVECREATOR_H_

#include <tuple>

#include "RangeBoundary.h"
#include "TextDirectiveUtil.h"
#include "mozilla/RefPtr.h"
#include "mozilla/Result.h"
#include "mozilla/dom/fragmentdirectives_ffi_generated.h"
#include "nsStringFwd.h"

class nsRange;

namespace mozilla {
class ErrorResult;
}

namespace mozilla::dom {
class Document;
/**
 * @brief Helper class to create a text directive string from a given `Range`.
 *
 * The class provides a public static creator function which encapsulates all
 * necessary logic.
 * This class serves as a base class that defines the main algorithm, and is
 * subclassed twice for exact and range-based matching.
 */
class TextDirectiveCreator {
 public:
  /**
   * @brief Static creator function. Takes a `Range` and creates a text
   *        directive string, if possible.
   *
   * @param aDocument   The document in which `aInputRange` lives.
   * @param aInputRange The input range. This range will not be modified.
   * @param aWatchdog   A watchdog to ensure the operation does not run
   *                    longer than the predefined timeout.
   *
   * @return Returns a percent-encoded text directive string on success, an
   *         empty string if it's not possible to create a text fragment for the
   *         given range, or an error code.
   */
  static Result<nsCString, ErrorResult> CreateTextDirectiveFromRange(
      Document* aDocument, AbstractRange* aInputRange,
      const TimeoutWatchdog* aWatchdog);

  virtual ~TextDirectiveCreator();

 protected:
  TextDirectiveCreator(Document* aDocument, AbstractRange* aRange,
                       const TimeoutWatchdog* aWatchdog);

  /**
   * @brief Ensures the boundary points of the range point to word boundaries.
   *
   * This function always returns a new range.
   */
  static Result<RefPtr<AbstractRange>, ErrorResult> ExtendRangeToWordBoundaries(
      AbstractRange* aRange);

  /**
   * @brief Determines whether exact or range-based matching should be used.
   *
   * This function searches for a block boundary in `aRange`, which requires
   * range-based matching. If there is no block boundary, but the range content
   * is longer than a threshold, range-based matching is used as well.
   * This threshold is defined by the pref
   * `dom.text_fragments.create_text_fragment.exact_match_max_length`.
   *
   */
  static Result<bool, ErrorResult> MustUseRangeBasedMatching(
      AbstractRange* aRange);

  /**
   * @brief Creates an instance either for exact or range-based matching.
   */
  static Result<UniquePtr<TextDirectiveCreator>, ErrorResult> CreateInstance(
      Document* aDocument, AbstractRange* aRange,
      const TimeoutWatchdog* aWatchdog);

  /**
   * @brief Collects text content surrounding the target range.
   *
   * The context terms are then stored both in normal and fold case form.
   *
   * Returns false if the algorithm cannot continue, for example if the text
   * directive must use range-based matching because of its length, but the
   * target range only consists of one word.
   */
  virtual Result<bool, ErrorResult> CollectContextTerms() = 0;

  /**
   * @brief Common helper which collects the prefix term of the target range.
   */
  Result<Ok, ErrorResult> CollectPrefixContextTerm();

  /**
   * @brief Common helper which collects the suffix term of the target range.
   */
  Result<Ok, ErrorResult> CollectSuffixContextTerm();

  /**
   * @brief Collect the word begin / word end distances for the context terms.
   *
   * For start (for range-based matching) and suffix terms, the search direction
   * is left-to-right. Therefore, the distances are based off the beginning of
   * the context terms and use the word end boundary.
   *
   * For prefix and end (for range-based matching), the search direction is
   * right-to-left. Therefore, the distances are based off the end of the
   * context terms and use the word start boundary.
   *
   * The distances are always sorted, so that the first entry points to the
   * nearest word boundary in search direction.
   */
  virtual void CollectContextTermWordBoundaryDistances() = 0;

  /**
   * @brief Searches the document for other occurrences of the target range and
   *        converts the results into a comparable format.
   *
   * This method searches the partial document from the beginning up to the
   * target range for occurrences of the target range content.
   * This needs to be done differently based on whether matching is exact or
   * range-based. For exact matching, the whole text content of the target range
   * is searched for. For range-based matching, two search runs are required:
   * One for the minimal `start` term (ie., the first word), which ends at the
   * beginning of the target range. And one for the minimal `end` term (ie., the
   * last word), which starts at the beginning of the target range and ends
   * _before_ its end.
   * The resulting lists of matching ranges do not exclude the target range.
   */
  virtual Result<Ok, ErrorResult> FindAllMatchingCandidates() = 0;

  /**
   * @brief Find all occurrences of `aSearchQuery` in the partial document.
   *
   * This method uses `nsFind` to perform a case-insensitive search for
   * `aSearchQuery` in the partial document from `aSearchStart` to `aSearchEnd`.
   *
   * @return List of `Range`s which have the case-insensitive-same content as
   *         `aSearchQuery`.
   */
  Result<nsTArray<RefPtr<AbstractRange>>, ErrorResult> FindAllMatchingRanges(
      const nsString& aSearchQuery, const RangeBoundary& aSearchStart,
      const RangeBoundary& aSearchEnd);

  /**
   * @brief Creates the shortest possible text directive.
   *
   * @return A percent-encoded string containing a text directive. Returns empty
   *         string in cases where it's not possible to create a text directive.
   */
  Result<nsCString, ErrorResult> CreateTextDirective();

  /**
   * @brief Creates unique substring length arrays which are extended to the
   *        nearest word boundary.
   */
  static std::tuple<nsTArray<uint32_t>, nsTArray<uint32_t>>
  ExtendSubstringLengthsToWordBoundaries(
      const nsTArray<std::tuple<uint32_t, uint32_t>>& aExactSubstringLengths,
      const Span<const uint32_t>& aFirstWordPositions,
      const Span<const uint32_t>& aSecondWordPositions);

  /**
   * @brief Test all combinations to identify the shortest text directive.
   */
  virtual Maybe<TextDirective> FindShortestCombination() const = 0;

  /**
   * @brief Perform a brute-force optimization run to find the shortest
   *        combination of a combination of two context terms.
   *
   * Each combination of the extended values is compared against all exact
   * values. It is only considered valid if at least one value is longer than
   * the exact lengths.
   *
   * @param aExactWordLengths               Array of tuples containing the exact
   *                                        common sub string lengths of this
   *                                        combination.
   * @param aFirstExtendedToWordBoundaries  All valid substring lengths for the
   *                                        first context term, extended to its
   *                                        next word boundary in reading
   *                                        direction.
   * @param aSecondExtendedToWordBoundaries All valid substring lengths for the
   *                                        second context term, extended to its
   *                                        next word boundary in reading
   *                                        direction.
   * @return A tuple of sub string lengths extended to word boundaries, which is
   *         the shortest allowed combination to eliminate all matches.
   *         Returns `Nothing` if it's not possible to eliminate all matches.
   */
  static Maybe<std::tuple<uint32_t, uint32_t>> CheckAllCombinations(
      const nsTArray<std::tuple<uint32_t, uint32_t>>& aExactWordLengths,
      const nsTArray<uint32_t>& aFirstExtendedToWordBoundaries,
      const nsTArray<uint32_t>& aSecondExtendedToWordBoundaries);

  // The maximum length of the context terms around the target range.
  // If a context term is longer, it will be truncated to this length.
  // If -- which seems highly unlikely -- there is another match for the target
  // range which happens to have a context term with the same content, it will
  // essentially be ignored:
  // The common length would be equal to this value, also the maximum common
  // length extended to the word boundary. Therefore, the algorithm could not
  // find a candidate which exceeds this length, therefore ignoring it
  // altogether.
  //
  // If -- even more unlikely -- this condition would happen for _every_ context
  // term, the algorithm would determine that it cannot create a text
  // directive for the target range because it would be ambiguous.
  static constexpr uint32_t kMaxContextTermLength = 1024;

  nsString mPrefixContent;
  nsString mPrefixFoldCaseContent;
  nsTArray<uint32_t> mPrefixWordBeginDistances;

  nsString mStartContent;

  nsString mSuffixContent;
  nsString mSuffixFoldCaseContent;
  nsTArray<uint32_t> mSuffixWordEndDistances;

  NotNull<RefPtr<Document>> mDocument;
  NotNull<RefPtr<AbstractRange>> mRange;

  NotNull<RefPtr<nsFind>> mFinder;

  /**
   * The watchdog ensures that the algorithm exits after a defined time
   * duration, to ensure that the main thread is not blocked for too long.
   *
   * The duration is defined by the pref
   * `dom.text_fragments.create_text_fragment.timeout`.
   */
  RefPtr<const TimeoutWatchdog> mWatchdog;

  nsContentUtils::NodeIndexCache mNodeIndexCache;
};

/**
 * @brief Creator class which creates a range-based text directive.
 *
 */
class RangeBasedTextDirectiveCreator : public TextDirectiveCreator {
 private:
  using TextDirectiveCreator::TextDirectiveCreator;

  Result<bool, ErrorResult> CollectContextTerms() override;

  void CollectContextTermWordBoundaryDistances() override;

  Result<Ok, ErrorResult> FindAllMatchingCandidates() override;

  void FindStartMatchCommonSubstringLengths(
      const nsTArray<RefPtr<AbstractRange>>& aMatchRanges);

  void FindEndMatchCommonSubstringLengths(
      const nsTArray<RefPtr<AbstractRange>>& aMatchRanges);

  Maybe<TextDirective> FindShortestCombination() const override;

  nsString mEndContent;
  // The fold case contents for start and end terms don't include the first/last
  // word of the start and end terms, because they are only used for finding the
  // common lengths for other matches.
  nsString mStartFoldCaseContent;
  nsString mEndFoldCaseContent;

  // These values are only passed into nsFind, therefore fold case is not
  // required.
  nsString mFirstWordOfStartContent;
  nsString mLastWordOfEndContent;

  // The lengths of the first/last word of the start and end terms, including
  // whitespace to the next word.
  // Therefore, these values are equal to
  // `m[Start|End]Content.Length() - m[Start|End]FoldCaseContent.Length()`.
  uint32_t mStartFirstWordLengthIncludingWhitespace = 0;
  uint32_t mEndLastWordLengthIncludingWhitespace = 0;

  // The distances are bound to the Fold Case Content strings, which do not
  // include the first/last word of the start and end terms.
  nsTArray<uint32_t> mStartWordEndDistances;
  nsTArray<uint32_t> mEndWordBeginDistances;

  nsTArray<std::tuple<uint32_t, uint32_t>> mStartMatchCommonSubstringLengths;
  nsTArray<std::tuple<uint32_t, uint32_t>> mEndMatchCommonSubstringLengths;
};

/**
 * @brief Creator class which creates an exact match text directive.
 *
 */
class ExactMatchTextDirectiveCreator : public TextDirectiveCreator {
 private:
  using TextDirectiveCreator::TextDirectiveCreator;

  Result<bool, ErrorResult> CollectContextTerms() override;

  void CollectContextTermWordBoundaryDistances() override;

  Result<Ok, ErrorResult> FindAllMatchingCandidates() override;

  void FindCommonSubstringLengths(
      const nsTArray<RefPtr<AbstractRange>>& aMatchRanges);

  Maybe<TextDirective> FindShortestCombination() const override;

  nsTArray<std::tuple<uint32_t, uint32_t>> mCommonSubstringLengths;
};
}  // namespace mozilla::dom
#endif