@endo/path-compare

@endo/path-compare

Shortlex-based comparison of string arrays

Overview

This is used by @endo/compartment-mapper when crawling a node_modules directory to find the shortest path to any given transitive dependency from the entry package.

Example

Given a dependency tree like this:

graph TD
  entry --> foo
  foo --> bar
  bar --> baz

The computed path from entry to baz is ['foo', 'bar', 'baz'].

If we have another dependency tree like this:

graph TD
  entry --> foo
  foo --> a
  a --> b
  b --> baz
  foo --> bar
  bar --> baz

The computed path from entry to baz is again ['foo', 'bar', 'baz'], because that has fewer elements than ['foo', 'a', 'b', 'baz'].

If we have yet another dependency tree like this:

graph TD
  entry --> foo
  foo --> bar
  foo --> alternative
  bar --> baz
  alternative --> baz

The computed path from entry to baz is again ['foo', 'bar', 'baz']. This is because while ['foo', 'alternative', 'baz'] is another path with the same array length, the algorithm must choose one, and so chooses the one with the fewest cumulative characters.

And if we have a tree like this:

graph TD
  entry --> foo
  foo --> spam
  foo --> quux
  spam --> baz
  quux --> baz

The computed path from entry to baz is ['foo', 'quux', 'baz']. Both the array length and cumulative character counts are the same. ['foo', 'quux', 'baz'] is lexicographically "before" ['foo', 'spam', 'baz'] (at the first code unit of each array's second element).

Note: the "lexicographic" comparison uses the UTF-16 code unit order, and thus may be surprising.

Usage

This package exports pathCompare.

pathCompare(a?: string[], b?: string[]) => number

Compares two arrays of strings (if provided) and returns a numeric comparison result: 0 if they are equal, -1 if a is "less than" b, and 1 if a is "greater than" b (where "less than" means having fewer elements, or the same element count but a shorter cumulative length, or the same element count and cumulative length but prior when comparing each element lexicographically by UTF-16 code unit).

import { pathCompare } from '@endo/path-compare';

const path1 = ['foo', 'bar', 'baz'];
const path2 = ['foo', 'quux', 'baz'];

const result = pathCompare(path1, path2); // -1

License

Copyright (c) 2021 Endo Project Contributors. Licensed Apache-2.0