Function order

src/compute-engine/boxed-expression/order.ts:298–447

(a: Expression, b: Expression)

  if (isString(expr)) return 'string';

  // Objects rank beside the other opaque values, after strings. They are
  // unordered as a matter of semantics (`cmp()` answers `undefined` for
  // them), so the rank exists only to give a sort a deterministic, total
  // comparator — see the `'object'` arm of `order()`.
  if (isObject(expr)) return 'object';

  return 'other';
}

/**
 * Given two expressions `a` and `b`, return:
 * - `-1` if `a` should be ordered before `b`
 * - `+1` if `b` should be ordered before `a`
 * - `0` if they have the same order (they are structurally equal)
 *
 * The default order is as follow:
 *
 * 1/ Literal numeric values (rational,  machine numbers and Decimal numbers),
 *  ordered by their numeric value (smaller numbers before larger numbers)
 *
 * 2/ Literal complex numbers, ordered by their imaginary parts. In case of a
 * tie, ordered by their real parts. (An arbitrary but established total
 * order — canonical operand order in existing expressions and snapshots
 * depends on it, so it is documented as implemented rather than changed;
 * CORRECTNESS P3-7.)
 *
 * 3/ Symbols, ordered by their name as strings
 *
 * 4/ Addition, ordered as a polynom, with higher degree terms first
 *
 * 5/ Other functions, ordered by their `complexity` property. In case
 * of a tie, ordered by the operator of the expression as a string. In case of a
 * tie, by the leaf count of each expression. In case of a tie, by the order
 * of each argument, left to right.
 *
 * 6/ Strings, ordered by comparing their Unicode code point values. While this
 * sort order is quick to calculate, it can produce unexpected results, for
 * example "E" < "e" < "È" and "11" < "2". This ordering is not suitable to
 * collate natural language strings.
 *
 * See https://reference.wolfram.com/language/ref/Sort.html for a
 * description of the ordering of expressions in Mathematica.
 *
 */
export function order(a: Expression, b: Expression): number {
  if (a === b) return 0;

  const rankA = rank(a);
  const rankB = rank(b);
  if (rankA !== rankB) return RANKS.indexOf(rankA) - RANKS.indexOf(rankB);

  // All NaN operands are equivalent for ordering purposes. Returning a fixed
  // value (0) keeps the comparator total and deterministic — an `af - bf`
  // subtraction would yield `NaN`, corrupting `Array.sort`.
  if (rankA === 'nan') return 0;

  if (rankA === 'complex') {
    // If the rank is complex, the numericValues can't be a number