@agoric/store - npm Package Compare versions

Comparing version 0.6.9-dev-5ac65ec.0 to 0.6.9-dev-6087647.0

package.json

 {
   "name": "@agoric/store",
-  "version": "0.6.9-dev-5ac65ec.0+5ac65ec",
+  "version": "0.6.9-dev-6087647.0+6087647",
   "description": "Wrapper for JavaScript map",
@@ -34,9 +34,9 @@ "type": "module",
   "dependencies": {
-    "@agoric/assert": "0.3.16-dev-5ac65ec.0+5ac65ec",
-    "@agoric/eventual-send": "0.14.1-dev-5ac65ec.0+5ac65ec",
-    "@agoric/marshal": "0.5.1-dev-5ac65ec.0+5ac65ec",
-    "@agoric/promise-kit": "0.2.30-dev-5ac65ec.0+5ac65ec"
+    "@agoric/assert": "0.3.16-dev-6087647.0+6087647",
+    "@agoric/eventual-send": "0.14.1-dev-6087647.0+6087647",
+    "@agoric/marshal": "0.5.1-dev-6087647.0+6087647",
+    "@agoric/promise-kit": "0.2.30-dev-6087647.0+6087647"
   },
   "devDependencies": {
-    "@agoric/swingset-vat": "0.24.2-dev-5ac65ec.0+5ac65ec",
+    "@agoric/swingset-vat": "0.24.2-dev-6087647.0+6087647",
     "ava": "^3.12.1"
@@ -70,3 +70,3 @@ },
   },
-  "gitHead": "5ac65ecdfeed42be99f9316172b2799f70e37562"
+  "gitHead": "6087647a7ff9f893cc032124a878c748ea35b583"
 }

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/compareKeys.js

@@ -13,50 +13,3 @@ // @ts-check
 
-/**
- * `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 +16,0 @@ assertKey(left);

src/keys/copyMap.js

@@ -5,2 +5,3 @@ // @ts-check
   assertChecker,
+  Far,
   getTag,
@@ -60,6 +61,22 @@ makeTagged,
 
+/**
+ * @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);
@@ -100,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: () => {
@@ -106,0 +123,0 @@ /** @type {IteratorResult<[K,V],void>} */

src/keys/copySet.js

@@ -12,2 +12,3 @@ // @ts-check
   isRankSorted,
+  makeFullOrderComparatorKit,
   sortByRank,
@@ -22,2 +23,31 @@ } from '../patterns/rankOrder.js';
 /**
+ * @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 +70,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 +99,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 +148,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/rankOrder.js

@@ -50,3 +50,3 @@ // @ts-check
 /**
- * @type {WeakMap<CompareRank,WeakSet<Passable[]>>}
+ * @type {WeakMap<RankCompare,WeakSet<Passable[]>>}
  */
@@ -56,3 +56,3 @@ const memoOfSorted = new WeakMap();
 /**
- * @type {WeakMap<CompareRank,CompareRank>}
+ * @type {WeakMap<RankCompare,RankCompare>}
  */
@@ -62,3 +62,3 @@ const comparatorMirrorImages = new WeakMap();
 /**
- * @param {CompareRank=} compareRemotables
+ * @param {RankCompare=} compareRemotables
  * An option to create a comparator in which an internal order is
@@ -68,6 +68,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) => {
@@ -189,3 +189,3 @@ if (sameValueZero(left, right)) {
 
-  /** @type {CompareRank} */
+  /** @type {RankCompare} */
   const antiComparator = (x, y) => comparator(y, x);
@@ -201,4 +201,4 @@
 /**
- * @param {CompareRank} comparator
- * @returns {CompareRank=}
+ * @param {RankCompare} comparator
+ * @returns {RankCompare=}
  */
@@ -210,3 +210,3 @@ export const comparatorMirrorImage = comparator =>
  * @param {Passable[]} passables
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @returns {boolean}
@@ -233,3 +233,3 @@ */
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  */
@@ -246,4 +246,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[]}
@@ -276,3 +285,3 @@ */
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} key
@@ -335,3 +344,3 @@ * @param {("leftMost" | "rightMost")=} bias
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} a
@@ -344,3 +353,3 @@ * @param {Passable} b
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {Passable} a
@@ -353,3 +362,3 @@ * @param {Passable} b
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover[]} covers
@@ -373,3 +382,3 @@ * @returns {RankCover}
 /**
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover[]} covers
@@ -420,3 +429,3 @@ * @returns {RankCover}
  * @param {boolean=} longLived
- * @returns {ComparatorKit}
+ * @returns {FullComparatorKit}
  */
@@ -423,0 +432,0 @@ export const makeFullOrderComparatorKit = (longLived = false) => {

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

@@ -244,3 +244,10 @@ // @ts-check
 /**
- * @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`
@@ -273,11 +280,86 @@ * 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 above for
+ * `RankCompare`. 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 /////////////////////////
@@ -308,3 +390,3 @@
  * @param {Passable[]} sorted
- * @param {CompareRank} compare
+ * @param {RankCompare} compare
  * @param {RankCover} rankCover
@@ -311,0 +393,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

150911

increased by3.4%

Lines of code

3598

increased by3.84%

Dependency changes

• Updated@agoric/assert@0.3.16-dev-6087647.0+6087647

• Updated@agoric/eventual-send@0.14.1-dev-6087647.0+6087647

• Updated@agoric/marshal@0.5.1-dev-6087647.0+6087647

• Updated@agoric/promise-kit@0.2.30-dev-6087647.0+6087647