Function.memoize.js

(function () {
// BEGIN :: module scope
'use strict';


/* function type specifc detection helpers */


/**
 * Detects whether a passed function type features a truly `writable`
 * `prototype` property.
 *
 * @param {Function} value
 *  Assumes a `'function'` type, but does not check for it.
 * @returns {boolean}
 *  Returns whether the passed value features a truly `writable`
 *  `prototype` property.
 */
function hasWritablePrototype(value) {
  return Object.getOwnPropertyDescriptor(value, 'prototype')?.writable === true;
}

/**
 * Reaches for any value's built-in type-signature by making use of ...
 * 
 * ```
 * Object.prototype.toString.call(value);
 * ```
 *
 * ... which helps avoiding possibly
 * manipulated `toString` behavior.
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {string}
 *  Returns the value's built-in type-signature
 *  like e.g. `'[object Date]'`.
 */
function getBuiltInTypeSignature(value) {
  return Object.prototype.toString.call(value).trim();
}

/**
 * Reaches for a function's true stringified version by making use of ...
 * 
 * ```
 * Function.prototype.toString.call(value);
 * ```
 *
 * ... which helps avoiding possibly
 * manipulated `toString` behavior.
 *
 * @param {Function} value
 *  Assumes a `'function'` type, but does not check for it.
 * @returns {string}
 *  Returns a function's true/real stringified implementation.
 */
function getFunctionSignature(value) {
  return Function.prototype.toString.call(value).trim();
}

/**
 * Reaches for a function's direct/immediate constructor-function.
 *
 * @param {Function} value
 *  Assumes a `'function'` type, but does not check for it.
 * @returns {string}
 *  Returns a function's direct/immediate constructor-function.
 */
function getConstructorFunction(value) {
  return Reflect.getOwnPropertyDescriptor(

    Object.getPrototypeOf(value), 'constructor'
  )
  .value;
}


/**
 * Detects any function type, which is ...
 *
 * ... the `typeof` operator not only returns the `'function'` string
 * for the processed `value`, but the latter also features both of a
 * function's call methods `call` and `apply`.
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {boolean}
 *  A boolean value which indicates whether the tested value is a function.
 */
function isFunction(value) {
  return (
    typeof value === 'function' &&
    typeof value.call === 'function' &&
    typeof value.apply === 'function'
  );
}

/**
 * Detects whether the passed `value` is any kind of arrow function,
 * either async or not.
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {boolean}
 *  A boolean value which indicates whether the tested value is either
 *  kind of arrow function.
 */
function isArrowFunctionType(value) {
  return (
    isFunction(value) &&
    /^(?:async\s*)?(?:\(.*?\)|[^(),=]+)\s*=>/.test(getFunctionSignature(value))
  );
}

/**
 * Detects whether the passed `value` is any kind of (non generator) async function,
 *  - either async arrow (expression)
 *  - or async function expression
 *  - or async function statement.
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {boolean}
 *  A boolean value which indicates whether the tested value is an async function.
 */
function isAsyncFunction(value) {
  return !!value && getBuiltInTypeSignature(value) === '[object AsyncFunction]';
}

// /**
//  * Detects whether the passed `value` is explicitly an
//  * `AsyncGeneratorFunction` type.
//  *
//  * @param {any} value
//  *  The to be processed value.
//  * @returns {boolean}
//  *  A boolean value which indicates whether the tested
//  *  value is explicitly an `AsyncGeneratorFunction` type.
//  */
// function isAsyncGeneratorFunction(value) {
//   return !!value && getBuiltInTypeSignature(value) === '[object AsyncGeneratorFunction]';
// }
// 
// /**
//  * Detects whether the passed `value` is explicitly a
//  * `GeneratorFunction` type.
//  *
//  * @param {any} value
//  *  The to be processed value.
//  * @returns {boolean}
//  *  A boolean value which indicates whether the
//  *  tested value is explicitly a `GeneratorFunction` type.
//  */
// function isGeneratorFunction(value) {
//   return !!value && getBuiltInTypeSignature(value) === '[object GeneratorFunction]';
// }

/**
 * Detects whether the passed `value` is any kind of generator function,
 * either async or not.
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {boolean}
 *  A boolean value which indicates whether the tested value is either
 *  kind of generator function.
 */
function isGeneratorFunctionType(value) {
  const signature = !!value && getBuiltInTypeSignature(value);
  return signature && (
    signature === '[object GeneratorFunction]' ||
    signature === '[object AsyncGeneratorFunction]'
  );
}

/**
 * Detects whether the passed `value` is exclusively the
 * only known function type as far back as with/at ES3
 * (in addition to all the built-in constructor functions).
 *
 * @param {any} value
 *  The to be processed value.
 * @returns {boolean}
 *  A boolean value which indicates whether the tested value
 *  is exclusively the only known function type back at ES3.
 */
function isES3Function(value) {
  return (
    isFunction(value) &&

    hasWritablePrototype(value) &&
    !isGeneratorFunctionType(value) &&

    // - detects any instance of a class that extends `Function`.
    !getFunctionSignature(getConstructorFunction(value)).startsWith('class ')
  );
}


/* memoization specific reflection and configuration helpers */


/**
 * Reaches for a function's own name.
 *
 * @param {Function} value
 *  Assumes a `'function'` type, but does not check for it.
 * @returns {string}
 *  Returns a function's own name.
 */
function getOwnName(value) {
  return Reflect.getOwnPropertyDescriptor(value, 'name')?.value ?? '';
}
/**
 * A 'hide source' specific `toString` implementation
 * which targets function types.
 *
 * - see ... [https://github.com/tc39/proposal-function-implementation-hiding]
 *
 * @this {Function}
 *  The memoize-function that had been
 *  passed through `asConfiguredMemoization`.
 *
 * @returns {string}
 *  A string value, a modifier-function's stringified version which shows
 *  the modifier-function's name but hides its implementation/source code.
 */
function hideSource() {
  return `function ${ getOwnName(this) }() { [hidden source] }`;
}

/**
 * Assigns the above implemented 'hide source' specific `toString`
 * behavior to any passed function type.
 *
 * @param {string} name
 *  The modifier name as it is supposed to be shown by the
 *  'hide source' and modifier specific `toString` method,
 *  even within minified source code environments.
 * @param {Function} modifier
 *  Assumes a modifier `'function'` type, but does not check for it.
 * @returns {Function}
 *  Returns the passed and augmented modifier-function.
 */
function asConfiguredMemoization(name, memoization) {
  Reflect.defineProperty(memoization, 'name', {

    // - assures the correct fuction name for 'hide source'
    //   specific function stringification, even within
    //   minified source code environments.

    ...Reflect.getOwnPropertyDescriptor(memoization, 'name'),
    value: name,
  });

  Reflect.defineProperty(memoization, 'toString', {
    configurable: true, value: hideSource,
  });
  return memoization;
}

/**
 * Assumes the passed function type to be a memoizer-function and
 * does augment it with memoizer-function specific behavior/traits
 * which are ...
 *
 *  - a changed function `name` property
 *    with a memoization-specific prefix,
 *  - an additional `origin` property which
 *    refers to the original/unmemoized function.
 *
 * @param {Function} origin
 *  The original/unmemoized function's reference.
 * @param {Function} memoizer
 *  The memoizer `'function'` type (assumed, but not checked for).
 * @returns {Function}
 *  Returns the passed and augmented memoizer-function.
 */
function asConfiguredMemoizer(origin, memoizer) {
  const nameDescriptor = Reflect.getOwnPropertyDescriptor(origin, 'name');

  Reflect.defineProperty(memoizer, 'name', {
    ...nameDescriptor,
    value: `memoized ${ nameDescriptor.value }`,
  });
  Reflect.defineProperty(memoizer, 'origin', { value: origin });

  // Reflect.defineProperty(memoizer, 'origin', { get: () => origin });

  return memoizer;
}
const memoizerRegistry = new WeakMap;


/* function type validation guard for the `memoize` specific implementation */

function runThrowingFunctionTypeValidationGuard(value) {
  if (
    !isFunction(value) ||

    isAsyncFunction(value) ||
    isGeneratorFunctionType(value) ||

    (!isArrowFunctionType(value) && !isES3Function(value))
  ) {
    throw new TypeError([
      'Memoization is supported exclusively for non async arrow function expressions',
      'as well as for either ES3 function statements or ES3 function expressions.',
    ].join(' '));
  }
}

/* all memoization specific implementations */

function recallOrMemoize({ proceed, target, registry }, argValue, idx, argsArray) {
  //  getOrCreateMemo
  let memoizationResult;

  if (!registry.has(argValue)) {
    registry.set(argValue, new Map([ ['link', new Map] ]));
  }
  const memoizationNode = registry.get(argValue);

  const willHaveResult = (idx === argsArray.length - 1);

  if (willHaveResult) {
    if (!memoizationNode.has('result')) {

      // memoize result.
      memoizationNode.set('result', proceed.apply(target, argsArray));
    }
    // recall result.
    memoizationResult = memoizationNode.get('result');    
  }
  return {
    proceed,
    target,
    ...(willHaveResult && { result: memoizationResult } || { registry: memoizationNode.get('link') }),
  };
}
function handleMemoization(target, proceed, ...args) {
  let noArgsMemoizationResult;

  target = target ?? memoizationTargetSurrogate;

  if (!memoizerRegistry.has(proceed)) {
    memoizerRegistry.set(proceed, new WeakMap);
  }
  const functionSpecificRegistry = memoizerRegistry.get(proceed);

  if (!functionSpecificRegistry.has(target)) {
    functionSpecificRegistry.set(target, new Map([ ['link', new Map] ]));
  }
  const memoizationNode = functionSpecificRegistry.get(target);

  const willHaveNoArgsResult = (args.length === 0);

  if (willHaveNoArgsResult) {
    if (!memoizationNode.has('result')) {

      // memoize result.
      memoizationNode.set('result', proceed.apply(target, args));
    }
    // recall result.
    noArgsMemoizationResult = memoizationNode.get('result');
  }
  return willHaveNoArgsResult
    ? noArgsMemoizationResult
    : args.reduce(
      recallOrMemoize, {
        proceed,
        target,
        registry: memoizationNode.get('link'),
      },
    )
    .result;
}
const memoizationTargetSurrogate = Symbol('invalid or unprovided target');

function memoize(target) {
  'use strict';
  // see ... [https://github.com/tc39/proposal-function-implementation-hiding]
  'hide source';

  const proceed = this;
  runThrowingFunctionTypeValidationGuard(proceed);

  target = target ?? null;

  return asConfiguredMemoizer(proceed, function /* memoizer */(...args) {

    return handleMemoization((this ?? target), proceed, ...args);
  });
}
Reflect.defineProperty(Function.prototype, 'memoize', {
  writable: true, configurable: true, value: asConfiguredMemoization('memoize', memoize),
});


/* "hide source" specific helpers and a partial polyfill for `Function.prototype.toString` itself */


// - see ... [https://github.com/tc39/proposal-function-implementation-hiding]

const isHideSourceSupport =
  !(/function\s+test\s*\(\s*\)\s*\{\s*['"]use\s+strict['"];\s*['"]hide\s+source['"];\s*\}/)
    .test(
      Function.prototype.toString.call((function test () { 'use strict'; 'hide source'; }))
    );

if (!isHideSourceSupport) {

  // - Partially re-implement `Function.prototype.toString` in order to
  //   hide the implementation details of all newly introduced/defined
  //   prototypal method-modifiers, in case they have been delegated to
  //   `Function.prototype.toString`. The re-implemantation itself does
  //   recognize its own reflection too and mimics the native behavior.

  function hideSourceHandler(nativeToString, customHandler, ...args) {
    const target = this;
    return (
      (hideSourceModifier === target && 'function toString() { [native code] }') ||
      (memoize === target && String(target)) ||
      nativeToString.call(target)
    );
  }
  const hideSourceModifier = Function.prototype.toString.around(hideSourceHandler, Function.prototype);

  Reflect.defineProperty(hideSourceModifier, 'name', {
    ...Reflect.getOwnPropertyDescriptor(Function.prototype.toString, 'name'),
  });
  Reflect.defineProperty(hideSourceModifier, 'toString', {
    configurable: true, value: () => 'function toString() { [native code] }',
  });

  Reflect.defineProperty(Function.prototype, 'toString', {
    // configurable: true, value: hideSourceModifier,
    writable: true, configurable: true, value: hideSourceModifier,
  });
}

// END :: module scope.
}(Function));

heavy-computation-example.js

// Matrix determinant via cofactor expansion — exponential time, pure arithmetic, deterministic:          

function determinant(matrix, size) {                                                                   
  if (size === 1) return matrix[0][0];                                                                 
  if (size === 2) return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];                    

  let det = 0;                                                                                       
  for (let col = 0; col < size; col++) {                                                               
    const minor = [];                                                                                
    for (let row = 1; row < size; row++) {
      minor.push([...matrix[row].slice(0, col), ...matrix[row].slice(col + 1)]);                       
    }
    det += (col % 2 === 0 ? 1 : -1) * matrix[0][col] * determinant(minor, size - 1);                   
  }                                                                                                    
  return det;
}                                                                                                      

// At size 10 it's already noticeably slow (~3 million recursive calls). At 12 it takes seconds. Fully    
// synchronous, pure function, same inputs always produce the same output — ideal for demonstrating
// memoization payoff.                                                                                    

// generate a reproducible NxN matrix
function makeMatrix(n, seed) {                                                                         
  const rows = [];
  for (let i = 0; i < n; i++) {                                                                        
    const row = [];                                                                                  
    for (let j = 0; j < n; j++) {
      row.push(((seed * (i + 1) * (j + 3)) % 97) - 48);                                                
    }                                                                                                  
    rows.push(row);                                                                                    
  }                                                                                                    
  return rows;                                                                                       
}

const m = makeMatrix(11, 7);                                                                           

determinant(m, 11); // takes a noticeable moment

// later

memoizeResult(0, determinant, [m, 11]);

console.log({ resultMap });

naive-memoization-utility.js

class RecallNode {
  value;

  constructor(value) {
    this.value = value;
  }
}
function isRecallNode(value) {
  return value instanceof RecallNode;
}
const resultMap = new WeakMap();

function getOrCreateNextMemoizationNode(node, key) {
  if (!node.has(key)) {
    node.set(key, new Map());
  }
  return node.get(key);
}
function memoizeArgumentSpecificResult(result, node, args) {
  const arity = args.length;

  // - create the arity-specific memoization node first.
  node = getOrCreateNextMemoizationNode(node, arity);

  // - then iterate the arguments except the last one, and
  //   create each an argument-specific memoization node.
  for (let idx = 0; idx < arity - 1; idx++) {
    node = getOrCreateNextMemoizationNode(node, args[idx]);
  }
  // - the last argument is the key to the terminating recall-node.
  const recallKey = args[arity - 1];

  if (node.has(recallKey)) {
    /** @type {RecallNode} */ (node.get(recallKey)).value = result;
  } else {
    node.set(recallKey, new RecallNode(result));
  }
}
function memoizeResult(result, source, args) {
  const arity = args.length;
  const isInstantlyMemoizable = arity < 1;

  if (isInstantlyMemoizable) {
    if (resultMap.has(source)) {
      /** @type {RecallNode} */ (resultMap.get(source)).value = result;
    } else {
      resultMap.set(source, new RecallNode(result));
    }
  } else {
    if (!resultMap.has(source)) {
      resultMap.set(source, new Map());
    }
    memoizeArgumentSpecificResult(result, resultMap.get(source), args);
  }
}