/**
 * @import WordTree from "@common/utils/string-tree.mjs";
 * @import {StringTreeEntryFilter, StringTreeNode, WordTreeEntry} from "@common/utils/_types.mjs";
 * @import Document from "@common/abstract/document.mjs";
 */

/**
 * This class is responsible for indexing all documents available in the world.
 * Stores documents using a word tree structure that allows for efficient searching.
 */
export default class DocumentIndex {
  constructor() {
    /**
     * A collection of WordTree structures for each document type.
     * @type {Record<string, WordTree>}
     */
    this.trees = {};
    Object.defineProperty(this, "trees", {writable: false, configurable: false});

    /**
     * A reverse-lookup of a document's UUID to its parent nodes in the word tree.
     * @type {Record<string, StringTreeNode[]>}
     */
    this.uuids = {};
    Object.defineProperty(this, "uuids", {writable: false, configurable: false});
  }

  /* -------------------------------------------- */

  /**
   * A unicode-friendly regular-expression pattern matching all non-word characters in a string
   * @type {RegExp}
   */
  static #NON_WORD_CHARACTERS_PATTERN = /[^\p{Alphabetic}\p{Mark}\p{Decimal_Number}\p{Join_Control}]/gu;

  /* -------------------------------------------- */

  /**
   * While we are indexing, we store a Promise that resolves when the indexing is complete.
   * @type {Promise<void>|null}
   */
  #ready = null;

  /**
   * Returns a Promise that resolves when the indexing process is complete.
   * @returns {Promise<void>|null}
   */
  get ready() {
    return this.#ready;
  }

  /* -------------------------------------------- */

  /**
   * Index all available documents in the world and store them in a word tree.
   * @returns {Promise<void>}
   */
  async index() {
    // Conclude any existing indexing.
    await this.#ready;
    const indexedCollections = CONST.WORLD_DOCUMENT_TYPES.filter(c => {
      const documentClass = foundry.utils.getDocumentClass(c);
      return documentClass.metadata.indexed && documentClass.schema.has("name");
    });
    // TODO: Consider running this process in a web worker.
    const start = performance.now();
    return this.#ready = new Promise(resolve => {
      for ( const documentName of indexedCollections ) {
        this._indexWorldCollection(documentName);
      }
      for ( const pack of game.packs ) {
        if ( pack.documentClass.metadata.indexed ) this._indexCompendium(pack);
      }
      resolve();
      console.debug(`${CONST.vtt} | Document indexing complete in ${performance.now() - start}ms.`);
    });
  }

  /**
   * Clean a string such as a Document name or lookup query;
   * @param {string} str The string to clean
   * @returns {string} The cleaned string
   */
  #cleanString(str) {
    if ( !str ) return str;
    return foundry.applications.ux.SearchFilter.cleanQuery(str)
      .toLocaleLowerCase(game.i18n.lang)
      .replace(/['`’]/g, "")
      .replaceAll("-", " ")
      .replace(DocumentIndex.#NON_WORD_CHARACTERS_PATTERN, " ");
  }

  /* -------------------------------------------- */

  /**
   * Return entries that match the given string prefix.
   * @param {string} query                      The search prefix or phrase.
   * @param {object} [options]                  Additional options to configure behaviour.
   * @param {string[]} [options.documentTypes]  Optionally provide an array of document types. Only entries of that type
   *                                            will be searched for.
   * @param {number} [options.limit=10]         The maximum number of items per document type to retrieve. It is
   *                                            important to set this value as very short prefixes will naturally match
   *                                            large numbers of entries.
   * @param {StringTreeEntryFilter} [options.filterEntries]         A filter function to apply to each candidate entry.
   * @param {DOCUMENT_OWNERSHIP_LEVELS|string} [options.ownership]  Only return entries that the user meets this
   *                                                                ownership level for.
   * @returns {Record<string, WordTreeEntry[]>} A number of entries that have the given prefix, grouped by document
   *                                            type.
   */
  lookup(query, {limit=10, documentTypes=[], ownership, filterEntries}={}) {
    const types = documentTypes.length ? documentTypes : Object.keys(this.trees);
    if ( ownership !== undefined ) {
      const originalFilterEntries = filterEntries ?? (() => true);
      filterEntries = entry => {
        return originalFilterEntries(entry) && DocumentIndex.#filterEntryForOwnership(entry, ownership);
      };
    }
    const results = {};
    const cleanedQuery = this.#cleanString(query);
    const terms = cleanedQuery
      .split(" ")
      .filter(t => (t.length > 1) && !CONFIG.i18n.searchStopWords.has(t.toLocaleLowerCase(game.i18n.lang)));
    for ( const type of types ) {
      const tree = this.trees[type];
      if ( !tree ) {
        results[type] = [];
        continue;
      }
      /** @type {WordTreeEntry[]} */
      const typeResults = [];

      // Track entry matches for each term
      /** @type {Record<string, Set<Document>} */
      const entriesByTerm = {};
      for ( const term of terms ) {
        entriesByTerm[term] = new Set();
        const termResults = tree.lookup(term, {filterEntries, limit: Infinity});
        typeResults.push(...termResults);
        for ( const termResult of termResults ) entriesByTerm[term].add(termResult.entry);
      }

      // Result must prefix-match all terms
      const allTermMatches = typeResults.filter(r => terms.every(t => entriesByTerm[t].has(r.entry)));

      // Dedupe
      const distinctEntries = new Set();
      results[type] = allTermMatches.reduce((finalResults, match) => {
        if ( !distinctEntries.has(match.entry) ) {
          finalResults.push(match);
          distinctEntries.add(match.entry);
        }
        return finalResults;
      }, []);

      // TODO: Add real result scoring before truncating to limit
      results[type].sort((a, b) => {
        const cleanA = this.#cleanString(a.entry.name ?? "");
        const cleanB = this.#cleanString(b.entry.name ?? "");
        return ((cleanB === cleanedQuery) - (cleanA === cleanedQuery))
          || (cleanB.startsWith(cleanedQuery) - cleanA.startsWith(cleanedQuery))
          || (cleanA.length < cleanB.length ? -1 : cleanA.length > cleanB.length ? 1 : 0);
      });
      results[type].length = Math.min(limit, results[type].length);
    }
    return results;
  }

  /* -------------------------------------------- */

  /**
   * Add an entry to the index.
   * @param {Document} doc  The document entry.
   */
  addDocument(doc) {
    if ( !doc.constructor.metadata?.indexed ) return;
    if ( doc.pack ) {
      if ( doc.isEmbedded ) return; // Only index primary documents inside compendium packs
      const pack = game.packs.get(doc.pack);
      const index = pack.index.get(doc.id);
      if ( index ) this._addLeaves(index, {pack});
    }
    else this._addLeaves(doc);
  }

  /* -------------------------------------------- */

  /**
   * Remove an entry from the index.
   * @param {Document} doc  The document entry.
   */
  removeDocument(doc) {
    const nodes = this.uuids[doc.uuid];
    if ( !nodes ) return;
    for ( const node of nodes ) {
      node[foundry.utils.StringTree.leaves].findSplice(e => e.uuid === doc.uuid);
    }
    delete this.uuids[doc.uuid];
  }

  /* -------------------------------------------- */

  /**
   * Replace an entry in the index with an updated one.
   * @param {Document} doc  The document entry.
   */
  replaceDocument(doc) {
    this.removeDocument(doc);
    this.addDocument(doc);
  }

  /* -------------------------------------------- */

  /**
   * Add one or more leaf nodes to the word-tree index.
   * @param {object} doc                           The Document or compendium index entry to add.
   * @param {object} [options]                     Additional information for indexing.
   * @param {CompendiumCollection} [options.pack]  The compendium that the index belongs to.
   * @protected
   */
  _addLeaves(doc, {pack}={}) {
    const entry = {entry: doc, documentName: doc.documentName, uuid: doc.uuid};
    if ( pack ) Object.assign(entry, {documentName: pack.documentName, pack: pack.collection});
    const tree = this.trees[entry.documentName] ??= new foundry.utils.WordTree();
    this.uuids[entry.uuid] = this.#cleanString(doc.name)
      .split(" ")
      .filter(w => (w.length > 1) && !CONFIG.i18n.searchStopWords.has(w))
      .map(w => tree.addLeaf(w, entry));
  }


  /* -------------------------------------------- */

  /**
   * Add a leaf node to the word-tree index.
   * @protected
   * @deprecated
   * @ignore
   */
  _addLeaf(doc, options) {
    const message = "You are using DocumentIndex#_addLeaf: use DocumentIndex#_addLeaves instead.";
    foundry.utils.logCompatibilityWarning(message, {since: 14, until: 16, once: true});
    this._addLeaves(doc, options);
  }

  /* -------------------------------------------- */

  /**
   * Aggregate the compendium index and add it to the word tree index.
   * @param {CompendiumCollection} pack  The compendium pack.
   * @protected
   */
  _indexCompendium(pack) {
    for ( const entry of pack.index ) this._addLeaves(entry, {pack});
  }

  /* -------------------------------------------- */

  /**
   * Add all of a parent document's embedded documents to the index.
   * @param {Document} parent  The parent document.
   * @protected
   */
  _indexEmbeddedDocuments(parent) {
    const embedded = parent.constructor.metadata.embedded;
    for ( const embeddedName of Object.keys(embedded) ) {
      if ( !CONFIG[embeddedName].documentClass.metadata.indexed ) continue;
      for ( const doc of parent[embedded[embeddedName]] ) {
        this._addLeaves(doc);
      }
    }
  }

  /* -------------------------------------------- */

  /**
   * Aggregate all documents and embedded documents in a world collection and add them to the index.
   * @param {string} documentName  The name of the documents to index.
   * @protected
   */
  _indexWorldCollection(documentName) {
    const cls = CONFIG[documentName].documentClass;
    const collection = cls.metadata.collection;
    for ( const doc of game[collection] ) {
      this._addLeaves(doc);
      this._indexEmbeddedDocuments(doc);
    }
  }

  /* -------------------------------------------- */
  /*  Helpers                                     */
  /* -------------------------------------------- */

  /**
   * Check if the given entry meets the given ownership requirements.
   * @param {WordTreeEntry} entry                         The candidate entry.
   * @param {DOCUMENT_OWNERSHIP_LEVELS|string} ownership  The ownership.
   * @returns {boolean}
   */
  static #filterEntryForOwnership({ uuid, pack }, ownership) {
    if ( pack ) return game.packs.get(pack)?.testUserPermission(game.user, ownership);
    return foundry.utils.fromUuidSync(uuid)?.testUserPermission(game.user, ownership);
  }
}
