@agoric/store - npm Package Compare versions

Comparing version 0.6.9-dev-258c280.0 to 0.6.9-dev-2984a74.0

package.json

 {
   "name": "@agoric/store",
-  "version": "0.6.9-dev-258c280.0+258c280",
+  "version": "0.6.9-dev-2984a74.0+2984a74",
   "description": "Wrapper for JavaScript map",
@@ -34,9 +34,9 @@ "type": "module",
   "dependencies": {
-    "@agoric/assert": "0.3.16-dev-258c280.0+258c280",
-    "@agoric/eventual-send": "0.14.1-dev-258c280.0+258c280",
-    "@agoric/marshal": "0.5.1-dev-258c280.0+258c280",
-    "@agoric/promise-kit": "0.2.30-dev-258c280.0+258c280"
+    "@agoric/assert": "0.3.16-dev-2984a74.0+2984a74",
+    "@agoric/eventual-send": "0.14.1-dev-2984a74.0+2984a74",
+    "@agoric/marshal": "0.5.1-dev-2984a74.0+2984a74",
+    "@agoric/promise-kit": "0.2.30-dev-2984a74.0+2984a74"
   },
   "devDependencies": {
-    "@agoric/swingset-vat": "0.24.2-dev-258c280.0+258c280",
+    "@agoric/swingset-vat": "0.24.2-dev-2984a74.0+2984a74",
     "ava": "^3.12.1"
@@ -70,3 +70,3 @@ },
   },
-  "gitHead": "258c2803c9c6f6afa8f8ab58fb272a60fc6cfd18"
+  "gitHead": "2984a7487bcc6064c6cb899b7540e11159eedefd"
 }

src/index.js

@@ -21,3 +21,8 @@ // @ts-check
 } from './patterns/patternMatchers.js';
-export { compareRank, isRankSorted, sortByRank } from './patterns/rankOrder.js';
+export {
+  compareRank,
+  isRankSorted,
+  sortByRank,
+  makeFullOrderComparatorKit,
+} from './patterns/rankOrder.js';
 
@@ -43,1 +48,3 @@ export { makeScalarWeakSetStore } from './stores/scalarWeakSetStore.js';
 export { makeLegacyWeakMap } from './legacy/legacyWeakMap.js';
+
+export { makeCopySet, getCopySetKeys } from './keys/copySet.js';

src/keys/checkKey.js

 // @ts-check
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -5,0 +4,0 @@

src/keys/compareKeys.js

 // @ts-check
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -13,50 +12,3 @@
 
-/**
- * `compareKeys` implements a partial order over keys. As with the
- * rank ordering produced by `compareRank`, -1, 0, and 1 mean
- * "less than", "equivalent to", and "greater than" respectively.
- * NaN means "incomparable" --- the first key is not less, equivalent,
- * or greater than the second. For example, subsets over sets is
- * a partial order.
- *
- * By using NaN for "incomparable", the normal equivalence for using
- * the return value in a comparison is preserved.
- * `compareKeys(left, right) >= 0` iff `left` is greater than or
- * equivalent to `right` in the partial ordering.
- * `compareKeys` is currently not exported directly, so its
- * bizarre but convenient return type is not exposed.
- *
- * Key order (a partial order) and rank order (a full order) are
- * co-designed so that we store passables in rank order and index into them
- * with keys for key-based queries. To keep these distinct, when speaking
- * informally about rank, we talk about "earlier" and "later". When speaking
- * informally about keys, we talk about "smaller" and "bigger".
- *
- * In both orders, the return-0 case defines
- * an equivalence class, i.e., those that are tied for the same place in the
- * order. The global invariant that we need between the two orders is that the
- * key order equivalence class is always at least as precise as the
- * rank order equivalence class. IOW, if `compareKeys(X,Y) === 0` then
- * `compareRank(X,Y) === 0`. But not vice versa. For example, two different
- * remotables are the same rank but incommensurate as keys.
- *
- * A further invariant is if `compareKeys(X,Y) < 0` then
- * `compareRank(X,Y) <= 0`, i.e., if X is smaller than Y in key order, then X
- * must be at least as early as Y in rank order. But not vice versa.
- * X can be earlier than Y in rank order and still be incommensurate with Y in
- * key order. For example, the records `{b: 3, a: 5}` is earlier than but
- * incommensurate with the record `{b: 5, a: 3}`.
- *
- * This lets us translate a range search over the
- * partial key order into a range search over rank order followed by filtering
- * out those that don't match. To get this effect, we store the elements of
- * a set in an array sorted in reverse rank order, from later to earlier.
- * Combined with our lexicographic comparison of arrays, if set X is a subset
- * of set Y then the array representing set X will be an earlier rank that the
- * array representing set Y.
- *
- * @param {Key} left
- * @param {Key} right
- * @returns {-1 | 0 | 1 | NaN}
- */
+/** @type {KeyCompare} */
 export const compareKeys = (left, right) => {
@@ -63,0 +15,0 @@ assertKey(left);

src/keys/copyMap.js

@@ -5,2 +5,3 @@ // @ts-check
   assertChecker,
+  Far,
   getTag,
@@ -13,3 +14,2 @@ makeTagged,
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -61,6 +61,22 @@
 
+/**
+ * @callback IsCopyMap
+ * @param {Passable} m
+ * @returns {m is CopyMap<Key, Passable>}
+ */
+
+/** @type {IsCopyMap} */
 export const isCopyMap = m => checkCopyMap(m);
 harden(isCopyMap);
 
-export const assertCopyMap = m => checkCopyMap(m, assertChecker);
+/**
+ * @callback AssertCopyMap
+ * @param {Passable} m
+ * @returns {asserts m is CopyMap<Key, Passable>}
+ */
+
+/** @type {AssertCopyMap} */
+export const assertCopyMap = m => {
+  checkCopyMap(m, assertChecker);
+};
 harden(assertCopyMap);
@@ -101,6 +117,6 @@
   const { length } = keys;
-  return harden({
+  return Far('CopyMap entries iterable', {
     [Symbol.iterator]: () => {
       let i = 0;
-      return harden({
+      return Far('CopyMap entries iterator', {
         next: () => {
@@ -107,0 +123,0 @@ /** @type {IteratorResult<[K,V],void>} */

src/keys/copySet.js

@@ -12,6 +12,6 @@ // @ts-check
   isRankSorted,
+  makeFullOrderComparatorKit,
   sortByRank,
 } from '../patterns/rankOrder.js';
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -22,2 +22,31 @@
 /**
+ * @param {FullCompare} fullCompare
+ * @returns {(keys: Key[], check?: Checker) => boolean}
+ */
+export const makeCheckNoDuplicates = fullCompare => (keys, check = x => x) => {
+  keys = sortByRank(keys, fullCompare);
+  const { length } = keys;
+  for (let i = 1; i < length; i += 1) {
+    const k0 = keys[i - 1];
+    const k1 = keys[i];
+    if (fullCompare(k0, k1) === 0) {
+      return check(false, X`value has duplicates: ${k0}`);
+    }
+  }
+  return true;
+};
+
+/**
+ * TODO SECURITY HAZARD: https://github.com/Agoric/agoric-sdk/issues/4261
+ * This creates mutable static state that should be unobservable, since it
+ * is only used by checkNoDuplicates in an internal sort algorithm whose
+ * result is tested and then dropped. However, that has a bad performance
+ * cost. It is not yet clear how to fix this without opening a
+ * communications channel.
+ */
+const fullCompare = makeFullOrderComparatorKit(true).antiComparator;
+
+const checkNoDuplicates = makeCheckNoDuplicates(fullCompare);
+
+/**
  * @param {Passable[]} keys
@@ -40,7 +69,7 @@ * @param {Checker=} check
   }
-  return true;
+  return checkNoDuplicates(keys, check);
 };
 harden(checkCopySetKeys);
 
-/** @type WeakSet<CopySet<any>> */
+/** @type WeakSet<CopySet<Key>> */
 const copySetMemo = new WeakSet();
@@ -69,6 +98,22 @@
 
+/**
+ * @callback IsCopySet
+ * @param {Passable} s
+ * @returns {s is CopySet<Key>}
+ */
+
+/** @type {IsCopySet} */
 export const isCopySet = s => checkCopySet(s);
 harden(isCopySet);
 
-export const assertCopySet = s => checkCopySet(s, assertChecker);
+/**
+ * @callback AssertCopySet
+ * @param {Passable} s
+ * @returns {asserts s is CopySet<Key>}
+ */
+
+/** @type {AssertCopySet} */
+export const assertCopySet = s => {
+  checkCopySet(s, assertChecker);
+};
 harden(assertCopySet);
@@ -102,4 +147,7 @@
  */
-export const makeCopySet = elements =>
-  makeTagged('copySet', sortByRank(elements, compareAntiRank));
+export const makeCopySet = elements => {
+  const result = makeTagged('copySet', sortByRank(elements, compareAntiRank));
+  assertCopySet(result);
+  return result;
+};
 harden(makeCopySet);

src/keys/merge-set-operators.js

 // @ts-check
 
+import { sortByRank } from '../patterns/rankOrder.js';
 import {
-  makeFullOrderComparatorKit,
-  sortByRank,
-} from '../patterns/rankOrder.js';
+  getCopySetKeys,
+  makeCheckNoDuplicates,
+  makeCopySet,
+} from './copySet.js';
 
@@ -26,3 +28,3 @@ const { details: X } = assert;
  * @param {Iterable<T>} ys
- * @param {CompareRank} fullCompare
+ * @param {FullCompare} fullCompare
  * @returns {Iterable<[Opt<T>,Opt<T>]>}
@@ -92,3 +94,3 @@ */
 
-const isSupersetOp = xyi => {
+const isIterSuperset = xyi => {
   for (const [x, _yr] of xyi) {
@@ -103,3 +105,3 @@ if (x === PUMPKIN) {
 
-const isDisjointOp = xyi => {
+const isIterDisjoint = xyi => {
   for (const [x, y] of xyi) {
@@ -114,3 +116,3 @@ if (x !== PUMPKIN && y !== PUMPKIN) {
 
-const unionOp = xyi => {
+const iterUnion = xyi => {
   const result = [];
@@ -131,3 +133,3 @@ for (const [x, y] of xyi) {
 
-const disjointUnionOp = xyi => {
+const iterDisjointUnion = xyi => {
   const result = [];
@@ -149,3 +151,3 @@ for (const [x, y] of xyi) {
 
-const intersectionOp = xyi => {
+const iterIntersection = xyi => {
   const result = [];
@@ -161,3 +163,3 @@ for (const [x, y] of xyi) {
 
-const disjointSubtractOp = xyi => {
+const iterDisjointSubtract = xyi => {
   const result = [];
@@ -177,9 +179,18 @@ for (const [x, y] of xyi) {
  * @typedef {Object} SetOps
- * @property {CompareRank} fullCompare
- * @property {(xlist: T[], ylist: T[]) => boolean} isSuperset
- * @property {(xlist: T[], ylist: T[]) => boolean} isDisjoint
- * @property {(xlist: T[], ylist: T[]) => T[]} union
- * @property {(xlist: T[], ylist: T[]) => T[]} disjointUnion
- * @property {(xlist: T[], ylist: T[]) => T[]} intersection
- * @property {(xlist: T[], ylist: T[]) => T[]} disjointSubtract
+ *
+ * @property {(keys: Key[], check?: Checker) => boolean} checkNoDuplicates
+ *
+ * @property {(xlist: T[], ylist: T[]) => boolean} isListSuperset
+ * @property {(xlist: T[], ylist: T[]) => boolean} isListDisjoint
+ * @property {(xlist: T[], ylist: T[]) => T[]} listUnion
+ * @property {(xlist: T[], ylist: T[]) => T[]} listDisjointUnion
+ * @property {(xlist: T[], ylist: T[]) => T[]} listIntersection
+ * @property {(xlist: T[], ylist: T[]) => T[]} listDisjointSubtract
+ *
+ * @property {(x: CopySet<T>, y: CopySet<T>) => boolean} isSetSuperset
+ * @property {(x: CopySet<T>, y: CopySet<T>) => boolean} isSetDisjoint
+ * @property {(x: CopySet<T>, y: CopySet<T>) => CopySet<T>} setUnion
+ * @property {(x: CopySet<T>, y: CopySet<T>) => CopySet<T>} setDisjointUnion
+ * @property {(x: CopySet<T>, y: CopySet<T>) => CopySet<T>} setIntersection
+ * @property {(x: CopySet<T>, y: CopySet<T>) => CopySet<T>} setDisjointSubtract
  */
@@ -189,23 +200,47 @@
  * @template T
- * @param {boolean=} longLived
+ * @param {FullCompare} fullCompare
+ * Must be a total order, not just a rank order. See makeFullOrderComparatorKit.
  * @returns {SetOps<T>}
  */
-export const makeSetOps = (longLived = false) => {
-  const { antiComparator: fullCompare } = makeFullOrderComparatorKit(longLived);
-  const composeOp = op => (xlist, ylist) => {
+export const makeSetOps = fullCompare => {
+  const checkNoDuplicates = makeCheckNoDuplicates(fullCompare);
+
+  const listify = iterOp => (xlist, ylist) => {
     const xs = sortByRank(xlist, fullCompare);
     const ys = sortByRank(ylist, fullCompare);
     const xyi = merge(xs, ys, fullCompare);
-    return op(xyi);
+    return iterOp(xyi);
   };
+
+  const isListSuperset = listify(isIterSuperset);
+  const isListDisjoint = listify(isIterDisjoint);
+  const listUnion = listify(iterUnion);
+  const listDisjointUnion = listify(iterDisjointUnion);
+  const listIntersection = listify(iterIntersection);
+  const listDisjointSubtract = listify(iterDisjointSubtract);
+
+  const rawSetify = listOp => (xset, yset) =>
+    listOp(getCopySetKeys(xset), getCopySetKeys(yset));
+
+  const setify = listOp => (xset, yset) =>
+    makeCopySet(listOp(getCopySetKeys(xset), getCopySetKeys(yset)));
+
   return harden({
-    fullCompare,
-    isSuperset: composeOp(isSupersetOp),
-    isDisjoint: composeOp(isDisjointOp),
-    union: composeOp(unionOp),
-    disjointUnion: composeOp(disjointUnionOp),
-    intersection: composeOp(intersectionOp),
-    disjointSubtract: composeOp(disjointSubtractOp),
+    checkNoDuplicates,
+
+    isListSuperset,
+    isListDisjoint,
+    listUnion,
+    listDisjointUnion,
+    listIntersection,
+    listDisjointSubtract,
+
+    isSetSuperset: rawSetify(isListSuperset),
+    isSetDisjoint: rawSetify(isListDisjoint),
+    setUnion: setify(listUnion),
+    setDisjointUnion: setify(listDisjointUnion),
+    setIntersection: setify(listIntersection),
+    setDisjointSubtract: setify(listDisjointSubtract),
   });
 };
 harden(makeSetOps);

src/patterns/internal-types.js

 // @ts-check
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -5,0 +4,0 @@

src/patterns/patternMatchers.js

@@ -29,3 +29,2 @@ // @ts-check
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -32,0 +31,0 @@

src/patterns/rankOrder.js

@@ -29,5 +29,5 @@ // @ts-check
   /* s  */ ['string', ['s', 't']],
-  /* u  */ ['undefined', ['u', 'v']],
+  /* v  */ ['null', ['v', 'v~']],
   /* y  */ ['symbol', ['y', 'z']],
-  /* z  */ ['null', ['z', 'z~']],
+  /* z  */ ['undefined', ['z', '{']],
   /* | remotable->ordinal mapping prefix: This is not used in covers but it is
@@ -51,3 +51,3 @@ reserved from the same set of strings. Note that the prefix is > any
 /**
- * @type {WeakMap<CompareRank,WeakSet<Passable[]>>}
+ * @type {WeakMap<RankCompare,WeakSet<Passable[]>>}
  */
@@ -57,3 +57,3 @@ const memoOfSorted = new WeakMap();
 /**
- * @type {WeakMap<CompareRank,CompareRank>}
+ * @type {WeakMap<RankCompare,RankCompare>}
  */
@@ -63,3 +63,3 @@ const comparatorMirrorImages = new WeakMap();
 /**
- * @param {CompareRank=} compareRemotables
+ * @param {RankCompare=} compareRemotables
  * An option to create a comparator in which an internal order is
@@ -69,6 +69,6 @@ * assigned to remotables. This defaults to a comparator that
  * for the same rank.
- * @returns {ComparatorKit}
+ * @returns {RankComparatorKit}
  */
 const makeComparatorKit = (compareRemotables = (_x, _y) => 0) => {
-  /** @type {CompareRank} */
+  /** @type {RankCompare} */
   const comparator = (left, right) => {
@@ -190,3 +190,3 @@ if (sameValueZero(left, right)) {
 
-  /** @type {CompareRank} */
+  /** @type {RankCompare} */
   const antiComparator = (x, y) => comparator(y, x);
@@ -202,4 +202,4 @@
 /**
- * @param {CompareRank} comparator
- * @returns {CompareRank=}
+ * @param {RankCompare} comparator
+ * @returns {RankCompare=}
  */
@@ -211,3 +211,3 @@ export const comparatorMirrorImage = comparator =>
  * @param {Passable[]} passables
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @returns {boolean}
@@ -234,3 +234,3 @@ */
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  */
@@ -247,4 +247,13 @@ export const assertRankSorted = (sorted, compare) =>
 /**
+ * TODO SECURITY BUG: https://github.com/Agoric/agoric-sdk/issues/4260
+ * sortByRank currently uses `Array.prototype.sort` directly, and
+ * so only works correctly when given a `compare` function that considers
+ * `undefined` strictly bigger (`>`) than everything else. This is
+ * because `Array.prototype.sort` bizarrely moves all `undefined`s to
+ * the end of the array regardless, without consulting the `compare`
+ * function. This is a genuine bug for us NOW because sometimes we sort
+ * in reverse order by passing a reversed rank comparison function.
+ *
  * @param {Iterable<Passable>} passables
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @returns {Passable[]}
@@ -277,3 +286,3 @@ */
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} key
@@ -336,3 +345,3 @@ * @param {("leftMost" | "rightMost")=} bias
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} a
@@ -345,3 +354,3 @@ * @param {Passable} b
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} a
@@ -354,3 +363,3 @@ * @param {Passable} b
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover[]} covers
@@ -374,3 +383,3 @@ * @returns {RankCover}
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover[]} covers
@@ -421,3 +430,3 @@ * @returns {RankCover}
  * @param {boolean=} longLived
- * @returns {ComparatorKit}
+ * @returns {FullComparatorKit}
  */
@@ -424,0 +433,0 @@ export const makeFullOrderComparatorKit = (longLived = false) => {

src/stores/scalarMapStore.js

@@ -136,10 +136,10 @@ // @ts-check
   keyName = 'key',
-  { keySchema = undefined, valueSchema = undefined } = {},
+  { keyPattern = undefined, valuePattern = undefined } = {},
 ) => {
   const jsmap = new Map();
-  if (keySchema !== undefined) {
-    assertPattern(keySchema);
+  if (keyPattern !== undefined) {
+    assertPattern(keyPattern);
   }
-  if (valueSchema !== undefined) {
-    assertPattern(valueSchema);
+  if (valuePattern !== undefined) {
+    assertPattern(valuePattern);
   }
@@ -153,4 +153,4 @@
     assertPassable(value);
-    if (valueSchema !== undefined) {
-      fit(value, valueSchema);
+    if (valuePattern !== undefined) {
+      fit(value, valuePattern);
     }
@@ -165,4 +165,4 @@ };
     assertScalarKey(key);
-    if (keySchema !== undefined) {
-      fit(key, keySchema);
+    if (keyPattern !== undefined) {
+      fit(key, keyPattern);
     }
@@ -169,0 +169,0 @@ assertKVOkToSet(key, value);

src/stores/scalarSetStore.js

@@ -92,7 +92,7 @@ // @ts-check
   keyName = 'key',
-  { keySchema = undefined } = {},
+  { keyPattern = undefined } = {},
 ) => {
   const jsset = new Set();
-  if (keySchema !== undefined) {
-    assertPattern(keySchema);
+  if (keyPattern !== undefined) {
+    assertPattern(keyPattern);
   }
@@ -106,4 +106,4 @@
     assertScalarKey(key);
-    if (keySchema !== undefined) {
-      fit(key, keySchema);
+    if (keyPattern !== undefined) {
+      fit(key, keyPattern);
     }
@@ -110,0 +110,0 @@ };

src/stores/scalarWeakMapStore.js

@@ -91,10 +91,10 @@ // @ts-check
   keyName = 'key',
-  { longLived = true, keySchema = undefined, valueSchema = undefined } = {},
+  { longLived = true, keyPattern = undefined, valuePattern = undefined } = {},
 ) => {
   const jsmap = new (longLived ? WeakMap : Map)();
-  if (keySchema !== undefined) {
-    assertPattern(keySchema);
+  if (keyPattern !== undefined) {
+    assertPattern(keyPattern);
   }
-  if (valueSchema !== undefined) {
-    assertPattern(valueSchema);
+  if (valuePattern !== undefined) {
+    assertPattern(valuePattern);
   }
@@ -108,4 +108,4 @@
     assertPassable(value);
-    if (valueSchema !== undefined) {
-      fit(value, valueSchema);
+    if (valuePattern !== undefined) {
+      fit(value, valuePattern);
     }
@@ -123,4 +123,4 @@ };
     );
-    if (keySchema !== undefined) {
-      fit(key, keySchema);
+    if (keyPattern !== undefined) {
+      fit(key, keyPattern);
     }
@@ -127,0 +127,0 @@ assertKVOkToSet(key, value);

src/stores/scalarWeakSetStore.js

@@ -73,7 +73,7 @@ // @ts-check
   keyName = 'key',
-  { longLived = true, keySchema = undefined } = {},
+  { longLived = true, keyPattern = undefined } = {},
 ) => {
   const jsset = new (longLived ? WeakSet : Set)();
-  if (keySchema !== undefined) {
-    assertPattern(keySchema);
+  if (keyPattern !== undefined) {
+    assertPattern(keyPattern);
   }
@@ -90,4 +90,4 @@
     );
-    if (keySchema !== undefined) {
-      fit(key, keySchema);
+    if (keyPattern !== undefined) {
+      fit(key, keyPattern);
     }
@@ -94,0 +94,0 @@ };

src/stores/store-utils.js

 // @ts-check
 
+import { Far } from '@agoric/marshal';
+
 const { details: X, quote: q } = assert;
@@ -16,3 +18,3 @@
  * @param {() => Iterable<K>} getRawKeys
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {(k: K, v?: V) => void} assertOkToAdd
@@ -58,3 +60,3 @@ * @param {((k: K) => void)=} assertOkToDelete
 
-  const iterableKeys = harden({
+  const iterableKeys = Far('Iterable of keys', {
     [Symbol.iterator]: () => {
@@ -65,3 +67,3 @@ const generation = updateCount;
       let i = 0;
-      return harden({
+      return Far('Iterator of keys', {
         next: () => {
@@ -68,0 +70,0 @@ assert.equal(

src/types.js

 // @ts-check
 
-// eslint-disable-next-line spaced-comment
 /// <reference types="ses"/>
@@ -50,3 +49,3 @@
  *
- * * I say "indended" above because Patterns, in order to be declarative
+ * * I say "intended" above because Patterns, in order to be declarative
  * and passable, cannot have the generality of predicates written in a
@@ -89,4 +88,4 @@ * Turing-universal programming language. Rather, to represent the category of
  * Defaults to true, so please mark short lived stores explicitly.
- * @property {Pattern=} keySchema
- * @property {Pattern=} valueSchema
+ * @property {Pattern=} keyPattern
+ * @property {Pattern=} valuePattern
  */
@@ -246,3 +245,10 @@
 /**
- * @callback CompareRank
+ * @typedef {-1 | 0 | 1} RankComparison
+ * The result of a `RankCompare` function that defines a rank-order, i.e.,
+ * a total order in which different elements can be tied for the same
+ * rank. See `RankCompare`.
+ */
+
+/**
+ * @callback RankCompare
  * Returns `-1`, `0`, or `1` depending on whether the rank of `left`
@@ -275,11 +281,87 @@ * is before, tied-with, or after the rank of `right`.
  * @param {Passable} right
- * @returns {-1 | 0 | 1}
+ * @returns {RankComparison}
  */
 
 /**
- * @typedef {Object} ComparatorKit
- * @property {CompareRank} comparator
- * @property {CompareRank} antiComparator
+ * @typedef {RankCompare} FullCompare
+ * A `FullCompare` function satisfies all the invariants stated below for
+ * `RankCompare`'s relation with KeyCompare.
+ * In addition, its equality is as precise as the `KeyCompare`
+ * comparison defined below, in that, for all Keys `x` and `y`,
+ * `FullCompare(x, y) === 0` iff `KeyCompare(x, y) === 0`.
+ *
+ * For non-keys a `FullCompare` should be exactly as imprecise as
+ * `RankCompare`. For example, both will treat all errors as in the same
+ * equivalence class. Both will treat all promises as in the same
+ * equivalence class. Both will order taggeds the same way, which is admittedly
+ * weird, as some taggeds will be considered keys and other taggeds will be
+ * considered non-keys.
  */
 
+/**
+ * @typedef {Object} RankComparatorKit
+ * @property {RankCompare} comparator
+ * @property {RankCompare} antiComparator
+ */
+
+/**
+ * @typedef {Object} FullComparatorKit
+ * @property {FullCompare} comparator
+ * @property {FullCompare} antiComparator
+ */
+
+/**
+ * @typedef {-1 | 0 | 1 | NaN} KeyComparison
+ * The result of a `KeyCompare` function that defines a meaningful
+ * and meaningfully precise partial order of `Key` values. See `KeyCompare`.
+ */
+
+/**
+ * @callback KeyCompare
+ * `compareKeys` implements a partial order over keys. As with the
+ * rank ordering produced by `compareRank`, -1, 0, and 1 mean
+ * "less than", "equivalent to", and "greater than" respectively.
+ * NaN means "incomparable" --- the first key is not less, equivalent,
+ * or greater than the second. For example, subsets over sets is
+ * a partial order.
+ *
+ * By using NaN for "incomparable", the normal equivalence for using
+ * the return value in a comparison is preserved.
+ * `compareKeys(left, right) >= 0` iff `left` is greater than or
+ * equivalent to `right` in the partial ordering.
+ *
+ * Key order (a partial order) and rank order (a full order) are
+ * co-designed so that we store passables in rank order and index into them
+ * with keys for key-based queries. To keep these distinct, when speaking
+ * informally about rank, we talk about "earlier" and "later". When speaking
+ * informally about keys, we talk about "smaller" and "bigger".
+ *
+ * In both orders, the return-0 case defines
+ * an equivalence class, i.e., those that are tied for the same place in the
+ * order. The global invariant that we need between the two orders is that the
+ * key order equivalence class is always at least as precise as the
+ * rank order equivalence class. IOW, if `compareKeys(X,Y) === 0` then
+ * `compareRank(X,Y) === 0`. But not vice versa. For example, two different
+ * remotables are the same rank but incommensurate as keys.
+ *
+ * A further invariant is if `compareKeys(X,Y) < 0` then
+ * `compareRank(X,Y) <= 0`, i.e., if X is smaller than Y in key order, then X
+ * must be at least as early as Y in rank order. But not vice versa.
+ * X can be earlier than Y in rank order and still be incommensurate with Y in
+ * key order. For example, the record `{b: 3, a: 5}` is earlier than but
+ * incommensurate with the record `{b: 5, a: 3}`.
+ *
+ * This lets us translate a range search over the
+ * partial key order into a range search over rank order followed by filtering
+ * out those that don't match. To get this effect, we store the elements of
+ * a set in an array sorted in reverse rank order, from later to earlier.
+ * Combined with our lexicographic comparison of arrays, if set X is a subset
+ * of set Y then the array representing set X will be an earlier rank that the
+ * array representing set Y.
+ *
+ * @param {Key} left
+ * @param {Key} right
+ * @returns {KeyComparison}
+ */
+
 // ///////////////////// Should be internal only types /////////////////////////
@@ -310,3 +392,3 @@
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover} rankCover
@@ -313,0 +395,0 @@ * @returns {IndexCover}

New alerts

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

Found 1 instance in 1 package

Fixed alerts

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

150672

increased by3.23%

Lines of code

3592

increased by3.67%

Dependency changes

• Updated@agoric/assert@0.3.16-dev-2984a74.0+2984a74

• Updated@agoric/eventual-send@0.14.1-dev-2984a74.0+2984a74

• Updated@agoric/marshal@0.5.1-dev-2984a74.0+2984a74

• Updated@agoric/promise-kit@0.2.30-dev-2984a74.0+2984a74