/** @module helpers */

import Color from "./color.mjs";
import {DataFieldOperator, ForcedDeletion, ForcedReplacement} from "../data/operators.mjs";
import {logCompatibilityWarning} from "./logging.mjs";

/**
 * @import {DeepReadonly} from "../_types.mjs";
 * @import {ResolvedUUID} from "./_types.mjs";
 * @import {Document} from "../abstract/_module.mjs";
 */

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

/**
 * Recurse through an object, applying all special DataFieldOperator values.
 * ForcedDeletion values (or deprecated "-=" keys) are removed from the object
 * ForcedReplacement values (or deprecated "==" keys) are updated in the object
 * @param {*} obj
 * @returns {*}
 */
export function applyDataOperators(obj) {
  if ( obj instanceof DataFieldOperator ) obj = DataFieldOperator.get(obj);
  if ( Array.isArray(obj) ) return obj.map(applyDataOperators);
  if ( !isPlainObject(obj) ) return obj;
  const clone = {};
  for ( let key in obj ) {
    let value = obj[key];
    if ( isDeletionKey(key) ) {
      const operator = _migrateDeletionKey(key, value);
      key = operator.key;
      value = operator.value;
    }
    if ( value instanceof ForcedDeletion ) delete clone[key];
    else clone[key] = applyDataOperators(value);
  }
  return clone;
}

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

/**
 * Benchmark the performance of a function, calling it a requested number of iterations.
 * @param {Function} func       The function to benchmark
 * @param {number} iterations   The number of iterations to test
 * @param {...any} args         Additional arguments passed to the benchmarked function
 */
export async function benchmark(func, iterations, ...args) {
  const start = performance.now();
  for ( let i=0; i<iterations; i++ ) {
    await func(...args, i);
  }
  const end = performance.now();
  const t = Math.round((end - start) * 100) / 100;
  const name = func.name ?? "Evaluated Function";
  console.log(`${name} | ${iterations} iterations | ${t}ms | ${t / iterations}ms per`);
}

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

/**
 * A debugging function to test latency or timeouts by forcibly locking the thread for an amount of time.
 * @param {number} ms         A number of milliseconds to lock
 * @param {boolean} debug     Log debugging information?
 * @returns {Promise<void>}
 */
export async function threadLock(ms, debug=false) {
  const t0 = performance.now();
  let d = 0;
  while ( d < ms ) {
    d = performance.now() - t0;
    if ( debug && (d % 1000 === 0) ) {
      console.debug(`Thread lock for ${d / 1000} of ${ms / 1000} seconds`);
    }
  }
}

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

/**
 * Wrap a callback in a debounced timeout and expose a cancel method.
 * Delay execution of the callback function until the function has not been called for delay milliseconds.
 *
 * @example Classic usage
 * const updateSearch = debounce(query => this.#runSearch(query), 250);
 * updateSearch("goblin");
 * updateSearch("goblin king");
 *
 * @example Cancel a pending call
 * const savePosition = debounce(() => this.#save(), 1500);
 * savePosition();
 *
 * // Later, if you need to cancel a pending call before the debounced callback fires
 * savePosition.cancel();
 *
 * @param {Function} callback       A function to execute once the debounced threshold has been passed
 * @param {number} delay            An amount of time in milliseconds to delay
 * @returns {Function}              A wrapped function which can be called to debounce execution with a cancel method
 */
export function debounce(callback, delay) {
  let timeoutId;
  function debounced(...args) {
    clearTimeout(timeoutId);
    timeoutId = setTimeout(() => {
      callback.apply(this, args);
    }, delay);
  }
  debounced.cancel = function() {
    clearTimeout(timeoutId);
  };
  return debounced;
}

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

/**
 * Wrap a callback in a throttled timeout.
 * Delay execution of the callback function when the last time the function was called was delay milliseconds ago
 * @param {Function} callback       A function to execute once the throttled threshold has been passed
 * @param {number} delay            A maximum amount of time in milliseconds between to execution
 * @returns {Function}              A wrapped function which can be called to throttle execution
 */
export function throttle(callback, delay) {
  let pending;
  let lastTime = -delay;
  return function(...args) {
    if ( pending ) {
      pending.thisArg = this;
      pending.args = args;
      return;
    }
    pending = {thisArg: this, args};
    setTimeout(() => {
      const {thisArg, args} = pending;
      pending = null;
      callback.apply(thisArg, args);
      lastTime = performance.now();
    }, Math.max(delay - (performance.now() - lastTime), 0));
  };
}

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

/**
 * A utility function to request a debounced page reload.
 * @type {() => void}
 */
export const debouncedReload = debounce( () => window.location.reload(), 250);

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

/**
 * Recursively freezes (`Object.freeze`) the object (or value).
 * This method DOES NOT support cyclical data structures.
 * This method DOES NOT support advanced object types like Set, Map, or other specialized classes.
 * @template {object} const T
 * @param {T} obj                             The object (or value)
 * @param {object} [options]                  Options to configure the behaviour of deepFreeze
 * @param {boolean} [options.strict=false]    Throw an Error if deepFreeze is unable to seal something instead of
 *                                            returning the original
 * @returns {Readonly<T>}                     The same object (or value) that was passed in
 */
export function deepFreeze(obj, {strict=false}={}) {
  return _deepFreeze(obj, strict, 0);
}

/**
 * An inner function does the work of {@link foundry.utils.deepFreeze}.
 * @param {any} obj           Some sort of data
 * @param {boolean} strict    Throw an Error if deepClone is unable to clone something instead of returning the original
 * @param {number} _d         The depth tracker
 */
function _deepFreeze(obj, strict, _d) {
  if ( _d > 100 ) {
    throw new Error("Maximum depth exceeded. Be sure your object does not contain cyclical data structures.");
  }
  _d++;

  if ( Array.isArray(obj) ) obj.forEach(o => _deepFreeze(o, strict, _d));
  else if ( typeof obj === "object" ) {
    if ( obj === null ) return null;

    // Unsupported advanced objects
    if ( !isPlainObject(obj) ) {
      if ( strict ) throw new Error("deepFreeze cannot freeze advanced objects");
      return obj;
    }

    for ( const key in obj ) _deepFreeze(obj[key], strict, _d);
  }
  return Object.freeze(obj);
}

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

/**
 * Recursively seals (`Object.seal`) the object (or value).
 * This method DOES NOT support cyclical data structures.
 * This method DOES NOT support advanced object types like Set, Map, or other specialized classes.
 * @template {object} T
 * @param {T} obj                             The object (or value)
 * @param {object} [options]                  Options to configure the behaviour of deepSeal
 * @param {boolean} [options.strict=false]    Throw an Error if deepSeal is unable to seal something
 * @returns {T}                               The same object (or value) that was passed in
 */
export function deepSeal(obj, {strict=false}={}) {
  return _deepSeal(obj, strict, 0);
}

/**
 * An inner function does the work of {@link foundry.utils.deepSeal}.
 * @param {any} obj           Some sort of data
 * @param {boolean} strict    Throw an Error if deepClone is unable to clone something instead of returning the original
 * @param {number} _d         The depth tracker
 */
function _deepSeal(obj, strict, _d) {
  if ( _d > 100 ) {
    throw new Error("Maximum depth exceeded. Be sure your object does not contain cyclical data structures.");
  }
  _d++;

  if ( Array.isArray(obj) ) obj.forEach(o => _deepSeal(o, strict, _d));
  else if ( typeof obj === "object" ) {
    if ( obj === null ) return null;

    // Unsupported advanced objects
    if ( !isPlainObject(obj) ) {
      if ( strict ) throw new Error("deepSeal cannot seal advanced objects");
      return obj;
    }

    for ( const key in obj ) _deepSeal(obj[key], strict, _d);
  }
  return Object.seal(obj);
}

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

/**
 * Quickly clone a simple piece of data, returning a copy which can be mutated safely.
 * This method DOES support recursive data structures containing inner objects or arrays.
 * This method DOES NOT support cyclical data structures.
 * This method DOES NOT support advanced object types like Set, Map, or other specialized classes.
 * @template {object} T
 * @param {T} original                      Some sort of data
 * @param {object} [options]                Options to configure the behaviour of deepClone
 * @param {boolean} [options.strict=false]  Throw an Error if deepClone is unable to clone something instead of
 *                                          returning the original
 * @param {boolean} [options.prune=false]   Delete object entries with undefined values
 * @returns {T}                             The clone of that data
 */
export function deepClone(original, {strict=false, prune=false}={}) {
  return _deepClone(original, strict, prune, 0);
}

/**
 * An inner function does the work of the deepClone operation and is optimized to avoid object creation.
 * @param {unknown} original      Some sort of data
 * @param {boolean} strict        Throw an Error if deepClone is unable to clone something instead of returning the
 *                                original
 * @param {boolean} [prune=false] Delete entries with undefined values
 * @param {number} _d             The depth tracker
 */
function _deepClone(original, strict, prune, _d) {
  if ( _d > 100 ) {
    throw new Error("Maximum depth exceeded. Be sure your object does not contain cyclical data structures.");
  }
  _d++;

  // Simple types
  if ( (typeof original !== "object") || (original === null) ) return original;

  // Arrays
  if ( Array.isArray(original) ) return original.map(o => _deepClone(o, strict, prune, _d));

  // Dates
  if ( original instanceof Date ) return new Date(original);

  // Unsupported advanced objects
  if ( !isPlainObject(original) ) {
    if ( strict ) throw new Error("deepClone cannot clone advanced objects");
    return original;
  }

  // Other objects
  const clone = {};
  for ( const k of Object.keys(original) ) {
    if ( (original[k] === undefined) && prune ) continue;
    clone[k] = _deepClone(original[k], strict, prune, _d);
  }
  return clone;
}

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

/**
 * Deeply difference an object against some other, returning the update keys and values.
 * @param {object} original       An object comparing data against which to compare
 * @param {object} other          An object containing potentially different data.
 *                                Supports values that are DataFieldOperator instances.
 * @param {object} [options={}]   Additional options which configure the diff operation
 * @param {boolean} [options.inner=false]  Only recognize differences in other for keys which also exist in original
 * @param {boolean} [options.deletionKeys=false] Apply special logic to deletion keys. They will only be kept if the
 *                                               original object has a corresponding key that could be deleted.
 * @param {boolean} [options.bidirectional=false] Create a bidirectional diff (or "patch" in Unix parlance), setting a
 *                                                forced-deletion value where an entry is defined in the original object
 *                                                but not the other.
 * @param {number} [options._d]           An internal depth tracker
 * @returns {object}              An object of the data in other which differs from that in original
 */
export function diffObject(original, other, {inner=false, deletionKeys=false, bidirectional=false, _d=0}={}) {
  return _diffObject(original, other, inner, deletionKeys, bidirectional, _d);
}

/**
 * An inner function does the work of the diffObject operation and is optimized to avoid object creation.
 * @param {object} original
 * @param {object} other
 * @param {boolean} inner
 * @param {boolean} deletionKeys
 * @param {boolean} bidirectional
 * @param {number} _d
 * @returns {object}
 */
function _diffObject(original, other, inner, deletionKeys, bidirectional, _d=0) {
  if ( _d > 100 ) throw new Error("Maximum diffObject depth exceeded. Be careful of cyclical data structures.");
  const diff = {};
  for ( let key in other ) {
    let value = other[key];

    // Backwards compatibility for legacy deletion keys
    if ( isDeletionKey(key) ) {
      const operator = _migrateDeletionKey(key, value);
      key = operator.key;
      value = operator.value;
    }

    // Forced Deletion or Replacement
    if ( value instanceof DataFieldOperator ) {
      if ( (value instanceof ForcedReplacement) || (key in original) ) diff[key] = value;
      continue;
    }

    // Recursive differencing
    const [isDifferent, difference] = _diffValue(original, key, other[key], inner, deletionKeys, bidirectional, _d);
    if ( isDifferent ) diff[key] = difference;
  }
  if ( bidirectional ) {
    for ( const key in original ) {
      if ( (other[key] === undefined) && (original[key] !== undefined) ) diff[key] = new ForcedDeletion();
    }
  }
  return diff;
}

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

/**
 * Identify differences in individual keys.
 * @param {object} original
 * @param {string} key
 * @param {any} v1
 * @param {boolean} inner
 * @param {boolean} deletionKeys
 * @param {boolean} bidirectional
 * @param {number} _d
 * @returns {[boolean, any]}
 */
function _diffValue(original, key, v1, inner, deletionKeys, bidirectional, _d) {
  const hasKey = key in original;
  if ( inner && !hasKey ) return [false, undefined];
  const v0 = original[key];

  // Set to null or to undefined
  if ( (v1 === undefined) || (v1 === null) ) return [v0 !== v1, v1];

  // Change object type
  const t0 = getType(v0);
  const t1 = getType(v1);
  if ( t0 !== t1 ) return [true, applyDataOperators(v1)];

  // Use an explicitly provided equality testing method, if available
  if ( typeof v0?.equals === "function" ) {
    if ( v0.equals(v1) ) return [false, undefined];
    return [true, applyDataOperators(v1)];
  }

  // Recursively diff objects
  if ( (t0 === "Object") && (t1 === "Object") ) {
    if ( isEmpty(v1) && !bidirectional ) return [false, undefined];
    const d = _diffObject(v0, v1, inner, deletionKeys, bidirectional, _d + 1);
    return [!isEmpty(d), d];
  }

  // Differences in primitives
  return [v0.valueOf() !== v1.valueOf(), v1];
}

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

/**
 * Test if two values are equivalent.
 *
 * This helper supports equality testing for:
 * 1. Primitive data types (number, string, boolean, undefined)
 * 2. Simple objects (Object prototype, null)
 * 3. Complex objects which expose an `equals` method (Array, Set, Color, etc...)
 *
 * This method compares object `b` with object `a`, so in cases where an equality testing method is used it is called
 * as `a.equals(b).
 *
 * @param {any} a  The first value
 * @param {any} b  The second value
 * @returns {boolean}
 */
export function equals(a, b) {
  if ( a === b ) return true;                   // Strict equality
  const ta = getType(a);
  const tb = getType(b);
  if ( ta !== tb ) return false;                // Mismatched types are not equal

  // Complex objects cannot be treated as equal unless they expose an equality testing function
  if ( typeof a.equals === "function" ) return a.equals(b);
  if ( ta !== "Object" ) return false;

  // For simple objects, test that their keys are individually equivalent
  if ( Object.keys(a).length !== Object.keys(b).length ) return false;
  return iterateEntries(a).every(([k, v0]) => equals(v0, b[k]));
}

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

/**
 * A cheap data duplication trick which is relatively robust.
 * For a subset of cases the deepClone function will offer better performance.
 * @param {Object} original   Some sort of data
 */
export function duplicate(original) {
  return JSON.parse(JSON.stringify(original));
}


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

/**
 * Migrate a key, value pair to a new key and value using DataFieldOperator classes.
 * @param {string} k
 * @param {any} v
 * @returns {{key: string, value: ForcedDeletion|ForcedReplacement}}
 * @internal
 */
function _migrateDeletionKey(k, v) {
  const key = k.slice(2);
  let value;
  switch ( k[0] ) {
    case "-":
      if ( v !== null ) throw new Error("Removing a key using the deprecated -= deletion syntax requires the value "
        + " of that deletion key to be null, for example {-=key: null}");
      logCompatibilityWarning(`You are specifying a forced deletion key "${k}" using legacy syntax which should be `
        + `migrated to instead pass {${key}: _del} or {${key}: new foundry.data.operators.ForcedDeletion()}.`);
      value = new ForcedDeletion();
      break;
    case "=":
      logCompatibilityWarning(`You are specifying a forced replacement key "${k}" using legacy syntax which should be `
        + `migrated to instead pass {${key}: _replace(value)} or {${key}: foundry.data.operators.ForcedReplacement.create(value)}.`);
      value = ForcedReplacement.create(v);
      break;
  }
  return {key, value};
}

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

/**
 * Test whether some class is a subclass of a parent.
 * Returns true if the classes are identical.
 * @param {Function} cls        The class to test
 * @param {Function} parent     Some other class which may be a parent
 * @returns {boolean}           Is the class a subclass of the parent?
 */
export function isSubclass(cls, parent) {
  if ( typeof cls !== "function" ) return false;
  if ( cls === parent ) return true;
  return parent.isPrototypeOf(cls);
}

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

/**
 * Search up the prototype chain and return the class that defines the given property.
 * @param {Object|Constructor} obj    A class instance or class definition which contains a property.
 *                                    If a class instance is passed the property is treated as an instance attribute.
 *                                    If a class constructor is passed the property is treated as a static attribute.
 * @param {string} property           The property name
 * @returns {Constructor<Object>}             The class that defines the property
 */
export function getDefiningClass(obj, property) {
  const isStatic = obj.hasOwnProperty("prototype");
  let target = isStatic ? obj : Object.getPrototypeOf(obj);
  while ( target ) {
    if ( target.hasOwnProperty(property) ) {
      target = isStatic ? target : target.constructor;
      break;
    }
    target = Object.getPrototypeOf(target);
  }
  return target;
}

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

/**
 * Encode an url-like string by replacing any characters which need encoding.
 * To reverse this encoding, the native decodeURIComponent can be used on the whole encoded string, without adjustment.
 * @param {string} path     A fully-qualified URL or url component (like a relative path)
 * @returns {string}         An encoded URL string
 */
export function encodeURL(path) {

  // Determine whether the path is a well-formed URL
  const url = URL.parse(path);

  // If URL, remove the initial protocol
  if ( url ) path = path.replace(url.protocol, "");

  // Split and encode each URL part
  path = path.split("/").map(p => encodeURIComponent(p).replace(/'/g, "%27")).join("/");

  // Return the encoded URL
  return url ? url.protocol + path : path;
}

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

/**
 * Expand a flattened object to be a standard nested Object by converting all dot-notation keys to inner objects.
 * Only simple objects will be expanded. Other Object types like class instances will be retained as-is.
 * @param {object} obj      The object to expand
 * @returns {object}        An expanded object
 */
export function expandObject(obj) {
  const _expand = (value, depth) => {
    if ( depth > 32 ) throw new Error("Maximum object expansion depth exceeded");
    if ( !value ) return value;
    if ( Array.isArray(value) ) return value.map(v => _expand(v, depth+1)); // Map arrays
    if ( !isPlainObject(value) ) return value;                              // Return advanced objects directly
    const expanded = {};                                                    // Expand simple objects
    for ( const [k, v] of Object.entries(value) ) {
      setProperty(expanded, k, _expand(v, depth+1));
    }
    return expanded;
  };
  return _expand(obj, 0);
}

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

/**
 * Expand dot-notation keys within a plain object, mutating it in place.
 * Use a lazy allocation strategy that only copies keys when some expansion is required.
 * Performs the dot-key check and expansion in a single forward pass.
 * Keys without dots are passed through via direct assignment.
 * Keys containing dots are expanded via setProperty.
 * @param {object} data                       The object to expand in place.
 * @param {object} [options]                  Options for how expansion occurs.
 * @param {boolean} [options.shallow=false]   Whether to only expand top-level keys.
 * @returns {boolean}                         Whether any expansion was performed at any level.
 */
export function expandObjectInPlace(data, {shallow=false}={}) {
  let copy = null;
  let expanded = false;
  for ( const k in data ) {
    if ( !Object.hasOwn(data, k) ) continue;
    const v = data[k];
    if ( !shallow && (isPlainObject(v) || Array.isArray(v)) ) {
      expanded = expandObjectInPlace(v, {shallow: false}) || expanded;
    }

    // If we have already started expanding, continue directly in single forward pass.
    if ( copy !== null ) {
      if ( k.includes(".") ) setProperty(copy, k, v);
      else copy[k] = v;
    }

    // Identify the first dot-notation key and retroactively allocate copy.
    else if ( k.includes(".") ) {
      copy = {};
      for ( const j in data ) {
        if ( j === k ) break;
        if ( Object.hasOwn(data, j) ) copy[j] = data[j];
      }
      setProperty(copy, k, v);
    }
  }
  if ( copy === null ) return expanded;
  for ( const k in data ) delete data[k];
  Object.assign(data, copy);
  return true;
}

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

/**
 * Filter the contents of some source object using the structure of a template object.
 * Only keys which exist in the template are preserved in the source object.
 *
 * @param {object} source           An object which contains the data you wish to filter
 * @param {object} template         An object which contains the structure you wish to preserve
 * @param {object} [options={}]     Additional options which customize the filtration
 * @param {boolean} [options.templateValues=false]  Instead of keeping values from the source, instead draw values
 *                                                  from the template
 * @returns {object}                The filtered object
 *
 * @example Filter an object
 * ```js
 * const source = {foo: {number: 1, name: "Tim", topping: "olives"}, bar: "baz"};
 * const template = {foo: {number: 0, name: "Mit", style: "bold"}, other: 72};
 * filterObject(source, template); // {foo: {number: 1, name: "Tim"}};
 * filterObject(source, template, {templateValues: true}); // {foo: {number: 0, name: "Mit"}};
 * ```
 */
export function filterObject(source, template, {templateValues=false}={}) {

  // Validate input
  if ( !isPlainObject(source) || !isPlainObject(template) ) {
    throw new Error("One of source or template are not Objects!");
  }

  // Define recursive filtering function
  const _filter = function(s, t, filtered) {
    for ( const [k, v] of Object.entries(s) ) {
      const has = t.hasOwnProperty(k);
      const x = t[k];
      if ( has && isPlainObject(v) && isPlainObject(x) ) filtered[k] = _filter(v, x, {});
      else if ( has ) filtered[k] = templateValues ? x : v;
    }
    return filtered;
  };

  // Begin filtering at the outermost layer
  return _filter(source, template, {});
}

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

/**
 * Flatten a possibly multidimensional object to a one-dimensional one by converting all nested keys to dot notation
 * @param {object} obj        The object to flatten
 * @param {number} [_d=0]     Track the recursion depth to prevent overflow
 * @returns {object}          A flattened object
 */
export function flattenObject(obj, _d=0) {
  const flat = {};
  if ( _d > 100 ) {
    throw new Error("Maximum depth exceeded");
  }
  for ( const [k, v] of Object.entries(obj) ) {
    if ( isPlainObject(v) ) {
      if ( isEmpty(v) ) flat[k] = v;
      const inner = flattenObject(v, _d+1);
      for ( const [ik, iv] of Object.entries(inner) ) {
        flat[`${k}.${ik}`] = iv;
      }
    }
    else flat[k] = v;
  }
  return flat;
}

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

/**
 * Obtain references to the parent classes of a certain class.
 * @param {Function} cls            A class definition
 * @returns {Array<typeof Object>}  An array of parent classes which the provided class extends
 */
export function getParentClasses(cls) {
  if ( typeof cls !== "function" ) {
    throw new Error("The provided class is not a type of Function");
  }
  const parents = [];
  let parent = Object.getPrototypeOf(cls);
  while ( parent ) {
    parents.push(parent);
    parent = Object.getPrototypeOf(parent);
  }
  return parents.slice(0, -2);
}

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

/**
 * Get the URL route for a certain path which includes a path prefix, if one is set
 * @param {string} path             The Foundry URL path
 * @param {string|null} [prefix]    A path prefix to apply
 * @returns {string}                The absolute URL path
 */
export function getRoute(path, {prefix}={}) {
  prefix = prefix === undefined ? globalThis.ROUTE_PREFIX : prefix || null;
  path = path.replace(/(^\/+)|(\/+$)/g, ""); // Strip leading and trailing slashes
  let paths = [""];
  if ( prefix ) paths.push(prefix);
  paths = paths.concat([path.replace(/(^\/)|(\/$)/g, "")]);
  return paths.join("/");
}

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

/**
 * Test whether the given element is an instance of a given HTMLElement class in a cross-window way.
 * @param {HTMLElement} element            The element to test.
 * @param {string|Constructor} tagOrClass  The tag name or HTMLElement subclass to test.
 * @returns {boolean}
 */
export function isElementInstanceOf(element, tagOrClass) {
  if ( typeof tagOrClass === "string" ) {
    return element.tagName === tagOrClass.toUpperCase();
  }

  let proto = element.constructor;
  do {
    if ( proto.name === tagOrClass.name ) return true;
    proto = Object.getPrototypeOf(proto);
  } while ( proto );
  return false;
}

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

/**
 * The identifiable class types.
 * @type {Array<[class: Function, name: string]>}
 */
const typePrototypes = [
  [Set, "Set"],
  [Map, "Map"],
  [Promise, "Promise"],
  [Error, "Error"],
  [Color, "number"]
];

const plainObjectPrototype = Object.getPrototypeOf({});

/**
 * Determine whether a value is a plain object; that is, one with a constructor of Object of null.
 * @param {unknown} value
 * @returns {boolean}
 */
export function isPlainObject(value) {
  if ( !value ) return false;
  const prototype = Object.getPrototypeOf(value);
  return (prototype === plainObjectPrototype) || (prototype === null);
}

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

/**
 * Learn the underlying data type of some variable. Supported identifiable types include:
 * undefined, null, number, string, boolean, function, Array, Set, Map, Promise, Error,
 * HTMLElement (client side only), Object (plain objects).
 * If the type isn't identifiable, Unknown is returned.
 * @param {*} variable  A provided variable
 * @returns {string}    The named type of the token
 */
export function getType(variable) {

  // Primitive types, handled with simple typeof check
  const typeOf = typeof variable;
  if ( typeOf !== "object" ) return typeOf;

  // Special cases of object
  if ( variable === null ) return "null";
  if ( isPlainObject(variable) ) return "Object"; // Plain objects, including those with a null prototype.
  if ( Array.isArray(variable) ) return "Array";

  // Match prototype instances
  for ( const [cls, type] of typePrototypes ) {
    if ( variable instanceof cls ) return type;
  }
  if ( "HTMLElement" in globalThis ) {
    // Detect if a value is an HTMLElement in a way that is agnostic of whichever Document it was created in.
    if ( isElementInstanceOf(variable, HTMLElement) ) return "HTMLElement";
  }

  // Unknown Object type
  return "Unknown";
}

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

/**
 * A helper function which tests whether an object has a property or nested property given a string key.
 * The method also supports arrays if the provided key is an integer index of the array.
 * The string key supports the notation a.b.c which would return true if object[a][b][c] exists
 * @param {object} object   The object to traverse
 * @param {string} key      An object property with notation a.b.c
 * @returns {boolean}       An indicator for whether the property exists
 */
export function hasProperty(object, key) {
  if ( !key || !object ) return false;
  if ( key in object ) return true;
  let target = object;
  const parts = key.split(".");
  for ( let i = 0; i < parts.length; i++ ) {
    const p = parts[i];
    if ( !target || (typeof target !== "object") || !(p in target) ) return false;
    if ( i !== (parts.length - 1) ) target = target[p];
  }
  return true;
}

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

/**
 * A helper function which searches through an object to retrieve a value by a string key.
 * The method also supports arrays if the provided key is an integer index of the array.
 * The string key supports the notation a.b.c which would return object[a][b][c]
 * @param {object} object   The object to traverse
 * @param {string} key      An object property with notation a.b.c
 * @returns {*}             The value of the found property
 */
export function getProperty(object, key) {
  if ( !key || !object ) return undefined;
  if ( key in object ) return object[key];
  let target = object;
  for ( const p of key.split(".") ) {
    if ( !target ) return undefined;
    const type = typeof target;
    if ( (type !== "object") && (type !== "function") ) return undefined;
    if ( p in target ) target = target[p];
    else return undefined;
  }
  return target;
}

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

const SKIPPED_PROPERTIES = new Set(["__proto__", "constructor", "prototype"]);

/**
 * A helper function which searches through an object to assign a value using a string key
 * This string key supports the notation a.b.c which would target object[a][b][c]
 * @param {object} object   The object to update
 * @param {string} key      The string key
 * @param {*} value         The value to be assigned
 * @returns {boolean}       Whether the value was changed from its previous value
 */
export function setProperty(object, key, value) {
  if ( !key || SKIPPED_PROPERTIES.has(key) ) return false;

  // Convert the key to an object reference if it contains dot notation
  let target = object;
  if ( key.indexOf(".") !== -1 ) {
    const parts = key.split(".");
    if ( parts.some(p => SKIPPED_PROPERTIES.has(p)) ) return false;
    key = parts.pop();
    target = parts.reduce((target, p) => {
      if ( target[p] === undefined ) target[p] = {};
      return target[p];
    }, object);
  }

  // Update the target
  if ( target[key] !== value ) {
    target[key] = value;
    return true;
  }
  return false;
}

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

/**
 * A helper function which searches through an object to delete a value by a string key.
 * The string key supports the notation a.b.c which would delete object[a][b][c]
 * @param {object} object   The object to traverse
 * @param {string} key      An object property with notation a.b.c
 * @returns {boolean}       Was the property deleted?
 */
export function deleteProperty(object, key) {
  if ( !key || !object ) return false;
  let parent;
  let target = object;
  const parts = key.split(".");
  for ( const p of parts ) {
    if ( !target ) return false;
    const type = typeof target;
    if ( (type !== "object") && (type !== "function") ) return false;
    if ( !(p in target) ) return false;
    parent = target;
    target = parent[p];
  }
  delete parent[parts.at(-1)];
  return true;
}

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

/**
 * Invert an object by assigning its values as keys and its keys as values.
 * @param {object} obj    The original object to invert
 * @returns {object}      The inverted object with keys and values swapped
 */
export function invertObject(obj) {
  const inverted = {};
  for ( const [k, v] of Object.entries(obj) ) {
    if ( v in inverted ) throw new Error("The values of the provided object must be unique in order to invert it.");
    inverted[v] = k;
  }
  return inverted;
}

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

/**
 * Return whether a target version (v1) is more advanced than some other reference version (v0).
 * Supports either numeric or string version comparison with version parts separated by periods.
 * @param {number|string|null|undefined} v1    The target version
 * @param {number|string|null|undefined} v0    The reference version
 * @param {object} [options]                   Additional options which affect the comparison.
 * @param {boolean} [options.majorOnly]        Compare only the major version numbers.
 * @returns {boolean}                          Is v1 a more advanced version than v0?
 */
export function isNewerVersion(v1, v0, { majorOnly=false }={}) {
  if ( (v1 === null) || (v1 === undefined) ) return false;
  if ( (v0 === null) || (v0 === undefined) ) return true;

  // Handle numeric versions
  if ( (typeof v1 === "number") && (typeof v0 === "number") ) return v1 > v0;

  // Handle string parts
  let v1Parts = String(v1).split(".");
  let v0Parts = String(v0).split(".");

  // Optionally compare only the major version numbers.
  if ( majorOnly ) {
    v1Parts = v1Parts.slice(0, 1);
    v0Parts = v0Parts.slice(0, 1);
  }

  // Iterate over version parts
  for ( const [i, p1] of v1Parts.entries() ) {
    const p0 = v0Parts[i];

    // If the prior version doesn't have a part, v1 wins
    if ( p0 === undefined ) return true;

    // If both parts are numbers, use numeric comparison to avoid cases like "12" < "5"
    if ( Number.isNumeric(p0) && Number.isNumeric(p1) ) {
      if ( Number(p1) !== Number(p0) ) return Number(p1) > Number(p0);
    }

    // Otherwise, compare as strings
    if ( p1 !== p0 ) return p1 > p0;
  }

  // If there are additional parts to v0, it is not newer
  if ( v0Parts.length > v1Parts.length ) return false;

  // If we have not returned false by now, it's either newer or the same
  return !v1Parts.equals(v0Parts);
}

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

/**
 * Test whether a value is empty-like; either undefined or a content-less object.
 * @param {*} value       The value to test
 * @returns {boolean}     Is the value empty-like?
 */
export function isEmpty(value) {
  const t = getType(value);
  switch ( t ) {
    case "undefined":
      return true;
    case "null":
      return true;
    case "Array":
      return !value.length;
    case "Object":
      return !Object.keys(value).length;
    case "Set":
    case "Map":
      return !value.size;
    default:
      return false;
  }
}

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

/**
 * Object entries generator.
 * @param {object} obj
 * @yields {[string, any]}
 */
export function *objectEntries(obj) {
  for ( const key in obj ) {
    if ( Object.hasOwn(obj, key) ) yield [key, obj[key]];
  }
}

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

/**
 * Stream object entries.
 * @param {object} obj
 * @returns {IteratorObject<[string, any], void, unknown>}
 */
export function iterateEntries(obj) {
  if ( obj == null ) throw new TypeError("Cannot convert undefined or null to object");
  return Iterator.from(objectEntries(obj));
}

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

/**
 * Object keys generator.
 * @param {object} obj
 * @yields {string}
 */
export function *objectKeys(obj) {
  for ( const key in obj ) {
    if ( Object.hasOwn(obj, key) ) yield key;
  }
}

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

/**
 * Stream object keys.
 * @param {object} obj
 * @returns {IteratorObject<string, void, unknown>}
 */
export function iterateKeys(obj) {
  if ( obj == null ) throw new TypeError("Cannot convert undefined or null to object");
  return Iterator.from(objectKeys(obj));
}

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

/**
 * Object values generator.
 * @param {object} obj
 * @yields {any}
 */
export function *objectValues(obj) {
  for ( const key in obj ) {
    if ( Object.hasOwn(obj, key) ) yield obj[key];
  }
}

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

/**
 * Stream object values.
 * @param {object} obj
 * @returns {IteratorObject<any, void, unknown>}
 */
export function iterateValues(obj) {
  if ( obj == null ) throw new TypeError("Cannot convert undefined or null to object");
  return Iterator.from(objectValues(obj));
}

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

/**
 * Update a source object by replacing its keys and values with those from a target object.
 *
 * @param {object} original                           The initial object which should be updated with values from the
 *                                                    target
 * @param {object} [other={}]                         A new object whose values should replace those in the source
 * @param {object} [options={}]                       Additional options which configure the merge
 * @param {boolean} [options.insertKeys=true]         Control whether to insert new top-level objects into the resulting
 *                                                    structure which do not previously exist in the original object.
 * @param {boolean} [options.insertValues=true]       Control whether to insert new nested values into child objects in
 *                                                    the resulting structure which did not previously exist in the
 *                                                    original object.
 * @param {boolean} [options.overwrite=true]          Control whether to replace existing values in the source, or only
 *                                                    merge values which do not already exist in the original object.
 * @param {boolean} [options.recursive=true]          Control whether to merge inner-objects recursively (if true), or
 *                                                    whether to simply replace inner objects with a provided new value.
 * @param {boolean} [options.inplace=true]            Control whether to apply updates to the original object in-place
 *                                                    (if true), otherwise the original object is duplicated and the
 *                                                    copy is merged.
 * @param {boolean} [options.enforceTypes=false]      Control whether strict type checking requires that the value of a
 *                                                    key in the other object must match the data type in the original
 *                                                    data to be merged.
 * @param {boolean} [options.applyOperators=false]    Control whether to apply the effects of DataFieldOperator values
 *                                                    (if true) or retain those operators (if false) in the resulting
 *                                                    merged object.
 * @param {number} [_d=0]                             A privately used parameter to track recursion depth.
 * @returns {object}                                  The original source object including updated, inserted, or
 *                                                    overwritten records.
 *
 * @example Control how new keys and values are added
 * ```js
 * mergeObject({k1: "v1"}, {k2: "v2"}, {insertKeys: false}); // {k1: "v1"}
 * mergeObject({k1: "v1"}, {k2: "v2"}, {insertKeys: true});  // {k1: "v1", k2: "v2"}
 * mergeObject({k1: {i1: "v1"}}, {k1: {i2: "v2"}}, {insertValues: false}); // {k1: {i1: "v1"}}
 * mergeObject({k1: {i1: "v1"}}, {k1: {i2: "v2"}}, {insertValues: true}); // {k1: {i1: "v1", i2: "v2"}}
 * ```
 *
 * @example Control how existing data is overwritten
 * ```js
 * mergeObject({k1: "v1"}, {k1: "v2"}, {overwrite: true}); // {k1: "v2"}
 * mergeObject({k1: "v1"}, {k1: "v2"}, {overwrite: false}); // {k1: "v1"}
 * ```
 *
 * @example Control whether merges are performed recursively
 * ```js
 * mergeObject({k1: {i1: "v1"}}, {k1: {i2: "v2"}}, {recursive: false}); // {k1: {i2: "v2"}}
 * mergeObject({k1: {i1: "v1"}}, {k1: {i2: "v2"}}, {recursive: true}); // {k1: {i1: "v1", i2: "v2"}}
 * ```
 *
 * @example Deleting an existing object key
 * ```js
 * mergeObject({k1: "v1", k2: "v2"}, {"k1": new ForcedDeletion()}, {applyOperators: true});   // {k2: "v2"}
 * ```
 *
 * @example Explicitly replacing an inner object key
 * ```js
 * mergeObject({k1: {i1: "v1"}}, {"k1": ForcedReplacement.create({i2: "v2"})}, {applyOperators: true}); // {k1: {i2: "v2"}}
 * ```
 */
export function mergeObject(original, other={}, {insertKeys=true, insertValues=true, overwrite=true, recursive=true,
  inplace=true, enforceTypes=false, applyOperators=false, performDeletions=false}={}, _d=0) {
  if (!(original instanceof Object) || !(other instanceof Object)) {
    throw new Error("One of original or other are not Objects!");
  }

  // Backwards compatibility for performDeletions option
  if ( performDeletions ) {
    logCompatibilityWarning("You have passed the performDeletions option to foundry.utils.mergeObject "
      + "which is deprecated and renamed to applyOperators.", {since: 14, until: 16});
    applyOperators ??= performDeletions;

  }
  const options = {insertKeys, insertValues, overwrite, recursive, inplace, enforceTypes, applyOperators};

  // Special handling at depth 0
  if ( _d === 0 ) {
    if ( Object.keys(other).some(k => k.includes(".")) ) other = expandObject(other);
    if ( Object.keys(original).some(k => k.includes(".")) ) {
      const expanded = expandObject(original);
      if ( options.inplace ) {
        Object.keys(original).forEach(k => delete original[k]);
        Object.assign(original, expanded);
      }
      else original = expanded;
    }
    else if ( !options.inplace ) original = deepClone(original);
  }

  // Iterate over the other object
  for ( let k of Object.keys(other) ) {
    let v = other[k];
    if ( isDeletionKey(k) ) {
      const operator = _migrateDeletionKey(k, v);
      k = operator.key;
      v = operator.value;
    }
    if ( original.hasOwnProperty(k) ) _mergeUpdate(original, k, v, _d+1, options);
    else _mergeInsert(original, k, v, _d+1, options);
  }
  return original;
}

/**
 * A helper function for merging objects when the target key does not exist in the original.
 * @ignore
 */
function _mergeInsert(original, k, v, _d, options) {

  // Take no action if insertion is not possible or for ForcedDeletion operators
  const canInsert = ((_d <= 1) && options.insertKeys) || ((_d > 1) && options.insertValues);
  if ( !canInsert || (v instanceof ForcedDeletion) ) return;

  // Enact or retain ForcedReplacement operators
  if ( v instanceof ForcedReplacement ) {
    original[k] = options.applyOperators ? applyDataOperators(v) : v;
    return;
  }

  // Insert other values directly as clones
  original[k] = options.applyOperators ? applyDataOperators(v) : deepClone(v);
}

/**
 * A helper function for merging objects when the target key exists in the original.
 * @ignore
 */
function _mergeUpdate(original, k, v, _d, options) {
  const x = original[k];
  const tv = getType(v);
  const tx = getType(x);
  const ov = (tv === "Object") || (tv === "Unknown");
  const ox = (tx === "Object") || (tx === "Unknown");

  // ForcedDeletion operator
  if ( v instanceof ForcedDeletion ) {
    if ( options.overwrite === false ) return; // A merge with {overwrite: false} protects against ForcedDeletion
    if ( options.applyOperators ) delete original[k];
    else original[k] = v;
    return;
  }

  // ForcedReplacement operator
  if ( v instanceof ForcedReplacement ) {
    if ( options.overwrite === false ) return; // A merge with {overwrite: false} protects against ForcedReplacement
    original[k] = options.applyOperators ? applyDataOperators(v) : v;
    return;
  }

  // Recursively merge an inner object
  if ( ov && ox && options.recursive ) return mergeObject(x, v, {...options, inplace: true}, _d);

  // Overwrite an existing value, if allowed
  if ( options.overwrite ) {
    if ( (tx !== "undefined") && (tv !== tx) && options.enforceTypes ) {
      throw new Error("Mismatched data types encountered during object merge.");
    }
    original[k] = options.applyOperators ? applyDataOperators(v) : deepClone(v);
  }
}

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

/**
 * Parse an S3 key to learn the bucket and the key prefix used for the request.
 * @param {string} key  A fully qualified key name or prefix path.
 * @returns {{bucket: string|null, keyPrefix: string}}
 */
export function parseS3URL(key) {
  const url = URL.parse(key);
  if ( url ) return {
    bucket: url.host.split(".").shift(),
    keyPrefix: url.pathname.slice(1)
  };
  return {
    bucket: null,
    keyPrefix: ""
  };
}

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

/**
 * Generate a random alphanumeric string ID of a given requested length using `crypto.getRandomValues()`.
 * @param {number} length    The length of the random string to generate, which must be at most 16384.
 * @returns {string}         A string containing random letters (A-Z, a-z) and numbers (0-9).
 */
export function randomID(length=16) {
  const chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
  const cutoff = 0x100000000 - (0x100000000 % chars.length);
  const random = new Uint32Array(length);
  do {
    crypto.getRandomValues(random);
  } while ( random.some(x => x >= cutoff) );
  let id = "";
  for ( let i = 0; i < length; i++ ) id += chars[random[i] % chars.length];
  return id;
}

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

/**
 * Format a file size to an appropriate order of magnitude.
 * @param {number} size  The size in bytes.
 * @param {object} [options]
 * @param {number} [options.decimalPlaces=2]  The number of decimal places to round to.
 * @param {2|10} [options.base=10]            The base to use. In base 10 a kilobyte is 1000 bytes. In base 2 it is
 *                                            1024 bytes.
 * @returns {string}
 */
export function formatFileSize(size, {decimalPlaces=2, base=10}={}) {
  const units = ["B", "kB", "MB", "GB", "TB"];
  const divisor = base === 2 ? 1024 : 1000;
  let iterations = 0;
  while ( (iterations < units.length) && (size > divisor) ) {
    size /= divisor;
    iterations++;
  }
  return `${size.toFixed(decimalPlaces)} ${units[iterations]}`;
}

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

/**
 * Parse a UUID into its constituent parts, identifying the type and ID of the referenced document.
 * The ResolvedUUID result also identifies a "primary" document which is a root-level document either in the game
 * World or in a Compendium pack which is a parent of the referenced document.
 * @param {string} uuid                  The UUID to parse.
 * @param {object} [options]             Options to configure parsing behavior.
 * @param {foundry.abstract.Document} [options.relative]  A document to resolve relative UUIDs against.
 * @returns {ResolvedUUID|null} Returns, if possible, the Collection, Document Type, and Document ID to resolve the
 *                              parent document, as well as the remaining Embedded Document parts, if any.
 */
export function parseUuid(uuid, {relative}={}) {
  if ( typeof uuid !== "string" ) return null;

  // Relative UUID
  if ( uuid.startsWith(".") ) {
    if ( relative ) return _resolveRelativeUuid(uuid, relative);
    else return null;
  }

  // Split UUID parts
  const parts = uuid.split(".");
  let id;
  let type;
  let primaryId;
  let primaryType;
  let collection;

  // Compendium Documents
  if ( parts[0] === "Compendium" ) {
    // Re-interpret legacy compendium UUIDs which did not explicitly include their parent document type.
    let packType = _resolvePrimaryType(parts);
    if ( packType !== parts[3] ) parts.splice(3, 0, packType);

    // Check for redirects.
    if ( game.compendiumUUIDRedirects ) {
      const node = game.compendiumUUIDRedirects.nodeAtPrefix(parts, { hasLeaves: true });
      const leaves = node?.[foundry.utils.StringTree.leaves];
      if ( leaves.length ) {
        const redirect = leaves[0];
        if ( redirect?.length ) {
          parts.splice(0, redirect.length, ...redirect);
          packType ??= _resolvePrimaryType(parts);
          parts[3] = packType;
        }
      }
    }
    const [, scope, packName] = parts.splice(0, 3);
    collection = game.packs.get(`${scope}.${packName}`);
    [primaryType, primaryId] = parts.splice(0, 2);
    if ( primaryType && (primaryType === packType) ) {
      uuid = ["Compendium", scope, packName, primaryType, primaryId, ...parts].join(".");
    }
  }

  // World Documents
  else {
    [primaryType, primaryId] = parts.splice(0, 2);
    collection = globalThis.db?.[primaryType] ?? CONFIG[primaryType]?.collection?.instance;
  }

  // Embedded Documents
  if ( parts.length ) {
    if ( parts.length % 2 ) return null;
    id = parts.at(-1);
    type = parts.at(-2);
  }

  // Primary Documents
  else {
    id = primaryId;
    type = primaryType ?? undefined;
    primaryId = primaryType = undefined;
  }

  // Return resolved UUID
  return {uuid, type, id, collection, embedded: parts, primaryType, primaryId,
    documentType: primaryType ?? type, documentId: primaryId ?? id};
}

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

/**
 * Resolve a UUID relative to another document.
 * The general-purpose algorithm for resolving relative UUIDs is as follows:
 * 1. If the number of parts is odd, remove the first part and resolve it against the current document and update the
 *    current document.
 * 2. If the number of parts is even, resolve embedded documents against the current document.
 * @param {string} uuid        The UUID to resolve.
 * @param {foundry.abstract.Document} relative  The document to resolve against.
 * @returns {ResolvedUUID|null}     A resolved UUID object, if possible to create, or otherwise `null`.
 */
function _resolveRelativeUuid(uuid, relative) {
  if ( !(relative instanceof foundry.abstract.Document) ) {
    throw new Error("A relative Document instance must be provided to _resolveRelativeUuid");
  }
  let k = 1;
  while ( uuid.at(k) === "." ) k++;
  uuid = uuid.substring(k);
  while ( --k && relative ) relative = relative.parent;
  if ( !relative ) return null;
  if ( !uuid ) return parseUuid(relative.uuid);
  const parts = uuid.split(".");
  let id;
  let type;
  let root;
  let primaryType;
  let primaryId;

  // Identify the root document and its collection
  const getRoot = doc => {
    if ( doc.parent ) parts.unshift(doc.documentName, doc.id);
    return doc.parent ? getRoot(doc.parent) : doc;
  };

  // Even-numbered parts include an explicit child document type
  if ( (parts.length % 2) === 0 ) {
    root = getRoot(relative);
    id = parts.at(-1);
    type = parts.at(-2);
    primaryType = root.documentName;
    primaryId = root.id;
    uuid = [primaryType, primaryId, ...parts].join(".");
  }

  // Relative Embedded Document
  else if ( relative.parent ) {
    id = parts.at(-1);
    type = relative.documentName;
    parts.unshift(type);
    root = getRoot(relative.parent);
    primaryType = root.documentName;
    primaryId = root.id;
    uuid = [primaryType, primaryId, ...parts].join(".");
  }

  // Relative Document
  else {
    root = relative;
    type = relative.documentName;
    if ( parts.length > 1 ) {
      primaryType = type;
      primaryId = parts.shift();
      id = parts.at(-1);
      type = parts.at(-2);
      uuid = [primaryType, primaryId, ...parts].join(".");
    }
    else {
      id = parts.pop();
      uuid = [type, id].join(".");
    }
  }

  // Recreate fully-qualified UUID and return the resolved result
  if ( root.pack ) uuid = `Compendium.${root.pack}.${uuid}`;
  return {uuid, type, id, collection: root.collection, primaryType, primaryId, embedded: parts,
    documentType: primaryType ?? type, documentId: primaryId ?? id};
}

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

/**
 * Attempt to resolve a possibly missing primary Document type for a legacy Compendium UUID.
 * @param {string[]} parts
 * @returns {string|null} The Document type, if found, or null
 */
function _resolvePrimaryType(parts) {
  if ( CONST.COMPENDIUM_DOCUMENT_TYPES.includes(parts[3]) || (parts[3] === "Folder") ) return parts[3];
  return game.packs.get(`${parts[1]}.${parts[2]}`)?.documentName ?? null;
}

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

/**
 * Build the relative UUID of the target relative to the origin if possible.
 * @param {string|Document} target  The target UUID or Document
 * @param {string|Document} origin    The origin UUID or Document
 * @returns {string}                The relative UUID of the target relative to the origin if possible,
 *                                  otherwise the absolute UUID of the target
 */
export function buildRelativeUuid(target, origin) {
  const targetUuid = _convertToUuid(target, "target");
  const originUuid = _convertToUuid(origin, "origin");
  const n = originUuid.startsWith("Compendium.") ? 1 : 0;
  let prefix = originUuid;
  const parts = originUuid.split(".");
  let relativeUuid;
  let lastType;
  let k = 0;
  while ( true ) {
    if ( targetUuid === prefix ) {
      relativeUuid = ".";
      break;
    }
    if ( targetUuid.startsWith(`${prefix}.`) ) {
      relativeUuid = targetUuid.slice(prefix.length);
      if ( lastType && relativeUuid.startsWith(`.${lastType}.`) ) {
        relativeUuid = relativeUuid.slice(lastType.length + 1);
        k--;
      }
      break;
    }
    lastType = parts.at(-2);
    parts.length -= 2;
    if ( parts.length <= n ) {
      if ( !targetUuid.startsWith(`${lastType}.`) ) return targetUuid;
      relativeUuid = targetUuid.slice(lastType.length);
      break;
    }
    prefix = parts.join(".");
    k++;
  }
  relativeUuid = `${".".repeat(k)}${relativeUuid}`;
  return relativeUuid;
}

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

/**
 * Convert an argument to a UUID.
 * @param {string|Document} argument
 * @param {string} parameterName
 * @returns {string}
 */
function _convertToUuid(argument, parameterName) {
  let uuid;
  if ( argument instanceof foundry.abstract.Document ) {
    uuid = argument.uuid;
    if ( !uuid ) throw new Error(`The ${parameterName} Document does not have a UUID`);
  } else {
    uuid = parseUuid(argument)?.uuid;
    if ( !uuid ) throw new Error(`The ${parameterName} UUID is not valid`);
  }
  return uuid;
}

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

/**
 * Build a Universally Unique Identifier (uuid) from possibly limited data. An attempt will be made to resolve omitted
 * components, but an identifier and at least one of documentName, parent, and pack are required.
 * @param {object} context  Data for building the uuid
 * @param {string} context.id              The identifier of the document
 * @param {string} [context.documentName]  The document name (or type)
 * @param {Document|null} [context.parent] The document's parent, if any
 * @param {string|null} [context.pack]     The document's compendium pack, if applicable
 * @returns {string|null} A well-formed Document uuid unless one is unable to be created
 */
export function buildUuid({id, documentName, parent, pack}) {
  if ( !id || (!documentName && !parent && !pack) ) return null;
  if ( !pack && !parent && !CONST.WORLD_DOCUMENT_TYPES.includes(documentName) ) return null;
  if ( pack ) documentName ??= game.packs.get(pack)?.documentName;
  const parentUuid = parent?.uuid;
  if ( parent ) {
    if ( !parentUuid ) return null;
    if ( !documentName ) {
    // Note: the possibility exists, however unlikely, that multiple embedded collections will have the same ID
      for ( const collection of Object.values(parent.collections) ) {
        if ( collection.has(id) ) {
          documentName = collection.documentName;
          break;
        }
      }
    }
  }
  if ( !documentName ) return null;
  return [
    parentUuid,
    pack && !parent ? ["Compendium", pack] : null,
    documentName,
    id
  ].flat().filterJoin(".");
}

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

/**
 * The table used for escaping bad characters.
 * @type {Record<string, string>}
 */
const ESCAPE_HTML_TABLE = {
  "&": "&amp;",
  "<": "&lt;",
  ">": "&gt;",
  '"': "&quot;",
  "'": "&#x27;"
};

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

/**
 * The regex of bad characters that need to be escaped.
 * @type {RegExp}
 */
const ESCAPE_HTML_REGEX = new RegExp(`[${Object.keys(ESCAPE_HTML_TABLE).join("")}]`, "g");

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

/**
 * The table used for unescaping HTML character entities of bad characters.
 * @type {Record<string, string>}
 */
const UNESCAPE_HTML_TABLE = invertObject(ESCAPE_HTML_TABLE);

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

/**
 * The regex of HTML entities of bad characters that need to be unescaped.
 * @type {RegExp}
 */
const UNESCAPE_HTML_REGEX = new RegExp(`${Object.keys(UNESCAPE_HTML_TABLE).join("|")}`, "g");

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

/**
 * Escape the given unescaped string.
 *
 * Escaped strings are safe to use inside inner HTML of most tags and in most quoted HTML attributes.
 * They are not NOT safe to use in `<script>` tags, unquoted attributes, `href`, `onmouseover`, and similar.
 * They must be unescaped first if they are used inside a context that would escape them.
 *
 * Handles only `&`, `<`, `>`, `"`, and `'`.
 * @see {@link foundry.utils.unescapeHTML}
 * @param {string|any} value    An unescaped string
 * @returns {string}            The escaped string
 */
export function escapeHTML(value) {
  return String(value).replace(ESCAPE_HTML_REGEX, c => ESCAPE_HTML_TABLE[c]);
}

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

/**
 * Unescape the given escaped string.
 *
 * Handles only `&amp;`, `&lt;`, `&gt;`, `&quot;`, and `&#x27;`.
 * @see {@link foundry.utils.escapeHTML}
 * @param {string} value    An escaped string
 * @returns {string}        The escaped string
 */
export function unescapeHTML(value) {
  return value.replace(UNESCAPE_HTML_REGEX, c => UNESCAPE_HTML_TABLE[c]);
}

/* -------------------------------------------- */
/*  Deprecations and Compatibility              */
/* -------------------------------------------- */

/**
 * @deprecated since v14
 * @ignore
 */
export function applySpecialKeys(obj) {
  logCompatibilityWarning("foundry.utils.applySpecialKeys has been deprecated and renamed to "
    + "foundry.utils.applyDataOperators", {since: 14, until: 16});
  return applyDataOperators(obj);
}

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

/**
 * Is a string key of an object used for certain deletion or forced replacement operations.
 *
 * This function has become internal and undocumented. It can be deprecated and removed once support for
 * legacy deletion keys is fully removed.
 * @ignore
 * @internal
 */
export function isDeletionKey(key) {
  if ( !(typeof key === "string") ) return false;
  return (key[1] === "=") && ((key[0] === "=") || (key[0] === "-"));
}

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

/**
 * @deprecated since v14
 * @ignore
 */
export function objectsEqual(a, b) {
  logCompatibilityWarning("foundry.utils.objectsEqual has been deprecated and renamed to foundry.utils.equals, which"
    + " handles equality testing for more than just objects.", {since: 14, until: 16});
  return equals(a, b);
}
