@agoric/store - npm Package Compare versions

Comparing version 0.6.9-dev-0c4d32b.0 to 0.6.9-dev-0cfddd2.0

package.json

 {
   "name": "@agoric/store",
-  "version": "0.6.9-dev-0c4d32b.0+0c4d32b",
+  "version": "0.6.9-dev-0cfddd2.0+0cfddd2",
   "description": "Wrapper for JavaScript map",
@@ -14,6 +14,5 @@ "type": "module",
     "test:xs": "exit 0",
-    "lint-fix": "yarn lint:eslint --fix && yarn lint:types",
-    "lint-check": "yarn lint",
-    "lint": "yarn lint:types && yarn lint:eslint",
-    "lint:types": "tsc -p jsconfig.json",
+    "lint-fix": "yarn lint:eslint --fix",
+    "lint": "run-s --continue-on-error lint:*",
+    "lint:types": "tsc --maxNodeModuleJsDepth 3 -p jsconfig.json",
     "lint:eslint": "eslint '**/*.js'"
@@ -35,9 +34,9 @@ },
   "dependencies": {
-    "@agoric/assert": "0.3.16-dev-0c4d32b.0+0c4d32b",
-    "@agoric/eventual-send": "0.14.1-dev-0c4d32b.0+0c4d32b",
-    "@agoric/marshal": "0.5.1-dev-0c4d32b.0+0c4d32b",
-    "@agoric/promise-kit": "0.2.30-dev-0c4d32b.0+0c4d32b"
+    "@agoric/assert": "0.3.16-dev-0cfddd2.0+0cfddd2",
+    "@agoric/eventual-send": "0.14.1-dev-0cfddd2.0+0cfddd2",
+    "@agoric/promise-kit": "0.2.30-dev-0cfddd2.0+0cfddd2",
+    "@endo/marshal": "^0.5.4"
   },
   "devDependencies": {
-    "@agoric/swingset-vat": "0.24.2-dev-0c4d32b.0+0c4d32b",
+    "@agoric/swingset-vat": "0.24.2-dev-0cfddd2.0+0cfddd2",
     "ava": "^3.12.1"
@@ -67,3 +66,3 @@ },
   },
-  "gitHead": "0c4d32bb53e935bee28e64b53d9d74ae4c89b44a"
+  "gitHead": "0cfddd24197ada6e5badba2ecd698a6cb84656c7"
 }

src/index.js

 // @ts-check
 
-export { isKey, assertKey } from './keys/checkKey.js';
 export {
+  isKey,
+  assertKey,
+  makeCopySet,
+  getCopySetKeys,
+  makeCopyBag,
+  makeCopyBagFromElements,
+  getCopyBagEntries,
+  makeCopyMap,
+  getCopyMapEntries,
+} from './keys/checkKey.js';
+export { coerceToElements } from './keys/copySet.js';
+export { coerceToBagEntries } from './keys/copyBag.js';
+export {
   compareKeys,
@@ -12,17 +24,37 @@ keyLT,
 } from './keys/compareKeys.js';
-export { makeSetOps } from './keys/merge-set-operators.js';
+export {
+  elementsIsSuperset,
+  elementsIsDisjoint,
+  elementsCompare,
+  elementsUnion,
+  elementsDisjointUnion,
+  elementsIntersection,
+  elementsDisjointSubtract,
+  setIsSuperset,
+  setIsDisjoint,
+  setCompare,
+  setUnion,
+  setDisjointUnion,
+  setIntersection,
+  setDisjointSubtract,
+} from './keys/merge-set-operators.js';
 
 export {
+  bagIsSuperbag,
+  bagCompare,
+  bagUnion,
+  bagIntersection,
+  bagDisjointSubtract,
+} from './keys/merge-bag-operators.js';
+
+export {
   M,
+  getRankCover,
   isPattern,
   assertPattern,
+  assertKeyPattern,
   matches,
   fit,
 } from './patterns/patternMatchers.js';
-export {
-  compareRank,
-  isRankSorted,
-  sortByRank,
-  makeFullOrderComparatorKit,
-} from './patterns/rankOrder.js';
+export { compareRank, isRankSorted, sortByRank } from './patterns/rankOrder.js';
 
@@ -48,3 +80,1 @@ export { makeScalarWeakSetStore } from './stores/scalarWeakSetStore.js';
 export { makeLegacyWeakMap } from './legacy/legacyWeakMap.js';
-
-export { makeCopySet, getCopySetKeys } from './keys/copySet.js';

src/keys/checkKey.js

@@ -8,10 +8,18 @@ // @ts-check
   assertPassable,
+  Far,
   getTag,
   isObject,
+  makeTagged,
   passStyleOf,
-} from '@agoric/marshal';
-import { checkCopySet, everyCopySetKey } from './copySet.js';
-import { checkCopyMap, everyCopyMapKey, everyCopyMapValue } from './copyMap.js';
+} from '@endo/marshal';
+import { checkElements, makeSetOfElements } from './copySet.js';
+import { checkBagEntries, makeBagOfEntries } from './copyBag.js';
+import {
+  compareAntiRank,
+  makeFullOrderComparatorKit,
+  sortByRank,
+} from '../patterns/rankOrder.js';
 
 const { details: X, quote: q } = assert;
+const { ownKeys } = Reflect;
 
@@ -83,4 +91,7 @@ // ////////////////// Primitive and Scalar keys ////////////////////////////////
 
-// ///////////////////////////// Keys //////////////////////////////////////////
+// ////////////////////////////// Keys /////////////////////////////////////////
 
+/** @type {WeakSet<Key>} */
+const keyMemo = new WeakSet();
+
 /**
@@ -91,4 +102,424 @@ * @param {Passable} val
  */
+export const checkKey = (val, check = x => x) => {
+  if (isPrimitiveKey(val)) {
+    return true;
+  }
+  if (!isObject(val)) {
+    // TODO There is not yet a checkPassable, but perhaps there should be.
+    // If that happens, we should call it here instead.
+    assertPassable(val);
+    return true;
+  }
+  if (keyMemo.has(val)) {
+    return true;
+  }
+  // eslint-disable-next-line no-use-before-define
+  const result = checkKeyInternal(val, check);
+  if (result) {
+    // Don't cache the undefined cases, so that if it is tried again
+    // with `assertChecker` it'll throw a diagnostic again
+    keyMemo.add(val);
+  }
+  // Note that we do not memoize a negative judgement, so that if it is tried
+  // again with a checker, it will still produce a useful diagnostic.
+  return result;
+};
+harden(checkKey);
+
+/**
+ * @param {Passable} val
+ * @returns {boolean}
+ */
+export const isKey = val => checkKey(val);
+harden(isKey);
+
+/**
+ * @param {Key} val
+ */
+export const assertKey = val => {
+  checkKey(val, assertChecker);
+};
+harden(assertKey);
+
+// //////////////////////////// CopySet ////////////////////////////////////////
+
+// Moved to here so they can check that the copySet contains only keys
+// without creating an import cycle.
+
+/** @type WeakSet<CopySet<Key>> */
+const copySetMemo = new WeakSet();
+
+/**
+ * @param {Passable} s
+ * @param {Checker=} check
+ * @returns {boolean}
+ */
+export const checkCopySet = (s, check = x => x) => {
+  if (copySetMemo.has(s)) {
+    return true;
+  }
+  const result =
+    check(
+      passStyleOf(s) === 'tagged' && getTag(s) === 'copySet',
+      X`Not a copySet: ${s}`,
+    ) &&
+    checkElements(s.payload, check) &&
+    checkKey(s.payload);
+  if (result) {
+    copySetMemo.add(s);
+  }
+  return result;
+};
+harden(checkCopySet);
+
+/**
+ * @callback IsCopySet
+ * @param {Passable} s
+ * @returns {s is CopySet<Key>}
+ */
+
+/** @type {IsCopySet} */
+export const isCopySet = s => checkCopySet(s);
+harden(isCopySet);
+
+/**
+ * @callback AssertCopySet
+ * @param {Passable} s
+ * @returns {asserts s is CopySet<Key>}
+ */
+
+/** @type {AssertCopySet} */
+export const assertCopySet = s => {
+  checkCopySet(s, assertChecker);
+};
+harden(assertCopySet);
+
+/**
+ * @template K
+ * @param {CopySet<K>} s
+ * @returns {K[]}
+ */
+export const getCopySetKeys = s => {
+  assertCopySet(s);
+  return s.payload;
+};
+harden(getCopySetKeys);
+
+/**
+ * @template K
+ * @param {CopySet<K>} s
+ * @param {(key: K, index: number) => boolean} fn
+ * @returns {boolean}
+ */
+export const everyCopySetKey = (s, fn) =>
+  getCopySetKeys(s).every((key, index) => fn(key, index));
+harden(everyCopySetKey);
+
+/**
+ * @template K
+ * @param {Iterable<K>} elementIter
+ * @returns {CopySet<K>}
+ */
+export const makeCopySet = elementIter => {
+  const result = makeSetOfElements(elementIter);
+  assertCopySet(result);
+  return result;
+};
+harden(makeCopySet);
+
+// //////////////////////////// CopyBag ////////////////////////////////////////
+
+// Moved to here so they can check that the copyBag contains only keys
+// without creating an import cycle.
+
+/** @type WeakSet<CopyBag<Key>> */
+const copyBagMemo = new WeakSet();
+
+/**
+ * @param {Passable} b
+ * @param {Checker=} check
+ * @returns {boolean}
+ */
+export const checkCopyBag = (b, check = x => x) => {
+  if (copyBagMemo.has(b)) {
+    return true;
+  }
+  const result =
+    check(
+      passStyleOf(b) === 'tagged' && getTag(b) === 'copyBag',
+      X`Not a copyBag: ${b}`,
+    ) &&
+    checkBagEntries(b.payload, check) &&
+    checkKey(b.payload);
+  if (result) {
+    copyBagMemo.add(b);
+  }
+  return result;
+};
+harden(checkCopyBag);
+
+/**
+ * @callback IsCopyBag
+ * @param {Passable} b
+ * @returns {b is CopyBag<Key>}
+ */
+
+/** @type {IsCopyBag} */
+export const isCopyBag = b => checkCopyBag(b);
+harden(isCopyBag);
+
+/**
+ * @callback AssertCopyBag
+ * @param {Passable} b
+ * @returns {asserts b is CopyBag<Key>}
+ */
+
+/** @type {AssertCopyBag} */
+export const assertCopyBag = b => {
+  checkCopyBag(b, assertChecker);
+};
+harden(assertCopyBag);
+
+/**
+ * @template K
+ * @param {CopyBag<K>} b
+ * @returns {K[]}
+ */
+export const getCopyBagEntries = b => {
+  assertCopyBag(b);
+  return b.payload;
+};
+harden(getCopyBagEntries);
+
+/**
+ * @template K
+ * @param {CopyBag<K>} b
+ * @param {(entry: [K, bigint], index: number) => boolean} fn
+ * @returns {boolean}
+ */
+export const everyCopyBagEntry = (b, fn) =>
+  getCopyBagEntries(b).every((entry, index) => fn(entry, index));
+harden(everyCopyBagEntry);
+
+/**
+ * @template K
+ * @param {Iterable<[K,bigint]>} bagEntryIter
+ * @returns {CopyBag<K>}
+ */
+export const makeCopyBag = bagEntryIter => {
+  const result = makeBagOfEntries(bagEntryIter);
+  assertCopyBag(result);
+  return result;
+};
+harden(makeCopyBag);
+
+/**
+ * @template K
+ * @param {Iterable<K>} elementIter
+ * @returns {CopySet<K>}
+ */
+export const makeCopyBagFromElements = elementIter => {
+  // This fullOrder contains history dependent state. It is specific
+  // to this one call and does not survive it.
+  const fullCompare = makeFullOrderComparatorKit().antiComparator;
+  const sorted = sortByRank(elementIter, fullCompare);
+  /** @type {[K,bigint][]} */
+  const entries = [];
+  for (let i = 0; i < sorted.length; ) {
+    const k = sorted[i];
+    let j = i + 1;
+    while (j < sorted.length && fullCompare(k, sorted[j]) === 0) {
+      j += 1;
+    }
+    entries.push([k, BigInt(j - i)]);
+    i = j;
+  }
+  return makeCopyBag(entries);
+};
+harden(makeCopyBagFromElements);
+
+// //////////////////////////// CopyMap ////////////////////////////////////////
+
+// Moved to here so they can check that the copyMap's keys contains only keys
+// without creating an import cycle.
+
+/** @type WeakSet<CopyMap<any,any>> */
+const copyMapMemo = new WeakSet();
+
+/**
+ * @param {Passable} m
+ * @param {Checker=} check
+ * @returns {boolean}
+ */
+export const checkCopyMap = (m, check = x => x) => {
+  if (copyMapMemo.has(m)) {
+    return true;
+  }
+  if (!(passStyleOf(m) === 'tagged' && getTag(m) === 'copyMap')) {
+    return check(false, X`Not a copyMap: ${m}`);
+  }
+  const { payload } = m;
+  if (passStyleOf(payload) !== 'copyRecord') {
+    return check(false, X`A copyMap's payload must be a record: ${m}`);
+  }
+  const { keys, values, ...rest } = payload;
+  const result =
+    check(
+      ownKeys(rest).length === 0,
+      X`A copyMap's payload must only have .keys and .values: ${m}`,
+    ) &&
+    checkElements(keys, check) &&
+    check(
+      passStyleOf(values) === 'copyArray',
+      X`A copyMap's .values must be a copyArray: ${m}`,
+    ) &&
+    check(
+      keys.length === values.length,
+      X`A copyMap must have the same number of keys and values: ${m}`,
+    );
+  if (result) {
+    copyMapMemo.add(m);
+  }
+  return result;
+};
+harden(checkCopyMap);
+
+/**
+ * @callback IsCopyMap
+ * @param {Passable} m
+ * @returns {m is CopyMap<Key, Passable>}
+ */
+
+/** @type {IsCopyMap} */
+export const isCopyMap = m => checkCopyMap(m);
+harden(isCopyMap);
+
+/**
+ * @callback AssertCopyMap
+ * @param {Passable} m
+ * @returns {asserts m is CopyMap<Key, Passable>}
+ */
+
+/** @type {AssertCopyMap} */
+export const assertCopyMap = m => {
+  checkCopyMap(m, assertChecker);
+};
+harden(assertCopyMap);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @returns {K[]}
+ */
+export const getCopyMapKeys = m => {
+  assertCopyMap(m);
+  return m.payload.keys;
+};
+harden(getCopyMapKeys);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @returns {V[]}
+ */
+export const getCopyMapValues = m => {
+  assertCopyMap(m);
+  return m.payload.values;
+};
+harden(getCopyMapValues);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @returns {Iterable<[K,V]>}
+ */
+export const getCopyMapEntries = m => {
+  assertCopyMap(m);
+  const {
+    payload: { keys, values },
+  } = m;
+  const { length } = keys;
+  return Far('CopyMap entries iterable', {
+    [Symbol.iterator]: () => {
+      let i = 0;
+      return Far('CopyMap entries iterator', {
+        next: () => {
+          /** @type {IteratorResult<[K,V],void>} */
+          let result;
+          if (i < length) {
+            result = harden({ done: false, value: [keys[i], values[i]] });
+            i += 1;
+            return result;
+          } else {
+            result = harden({ done: true, value: undefined });
+          }
+          return result;
+        },
+      });
+    },
+  });
+};
+harden(getCopyMapEntries);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @param {(key: K, index: number) => boolean} fn
+ * @returns {boolean}
+ */
+export const everyCopyMapKey = (m, fn) =>
+  getCopyMapKeys(m).every((key, index) => fn(key, index));
+harden(everyCopyMapKey);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @param {(value: V, index: number) => boolean} fn
+ * @returns {boolean}
+ */
+export const everyCopyMapValue = (m, fn) =>
+  getCopyMapValues(m).every((value, index) => fn(value, index));
+harden(everyCopyMapValue);
+
+/**
+ * @template K,V
+ * @param {CopyMap<K,V>} m
+ * @returns {CopySet<K>}
+ */
+export const copyMapKeySet = m =>
+  // A copyMap's keys are already in the internal form used by copySets.
+  makeTagged('copySet', m.payload.keys);
+harden(copyMapKeySet);
+
+/**
+ * @template K,V
+ * @param {Iterable<[K, V]>} entries
+ * @returns {CopyMap<K,V>}
+ */
+export const makeCopyMap = entries => {
+  // This is weird, but reverse rank sorting the entries is a good first step
+  // for getting the rank sorted keys together with the values
+  // organized by those keys. Also, among values associated with
+  // keys in the same equivalence class, those are rank sorted.
+  // TODO This
+  // could solve the copyMap cover issue explained in patternMatchers.js.
+  // But only if we include this criteria in our validation of copyMaps,
+  // which we currently do not.
+  const sortedEntries = sortByRank(entries, compareAntiRank);
+  const keys = sortedEntries.map(([k, _v]) => k);
+  const values = sortedEntries.map(([_k, v]) => v);
+  const result = makeTagged('copyMap', { keys, values });
+  assertCopyMap(result);
+  return result;
+};
+harden(makeCopyMap);
+
+// //////////////////////// Keys Recur /////////////////////////////////////////
+
+/**
+ * @param {Passable} val
+ * @param {Checker=} check
+ * @returns {boolean}
+ */
 const checkKeyInternal = (val, check = x => x) => {
-  // eslint-disable-next-line no-use-before-define
   const checkIt = child => checkKey(child, check);
@@ -110,8 +541,7 @@
         case 'copySet': {
-          return (
-            checkCopySet(val, check) &&
-            // For a copySet to be a key, all its elements must be keys
-            everyCopySetKey(val, checkIt)
-          );
+          return checkCopySet(val, check);
         }
+        case 'copyBag': {
+          return checkCopyBag(val, check);
+        }
         case 'copyMap': {
@@ -121,4 +551,4 @@ return (
             // For a copyMap to be a key, all its keys and values must
-            // be keys.
-            everyCopyMapKey(val, checkIt) &&
+            // be keys. Keys already checked by `checkCopyMap` since
+            // that's a copyMap requirement in general.
             everyCopyMapValue(val, checkIt)
@@ -150,49 +580,1 @@ );
 };
-
-/** @type {WeakSet<Key>} */
-const keyMemo = new WeakSet();
-
-/**
- * @param {Passable} val
- * @param {Checker=} check
- * @returns {boolean}
- */
-export const checkKey = (val, check = x => x) => {
-  if (isPrimitiveKey(val)) {
-    return true;
-  }
-  if (!isObject(val)) {
-    // TODO There is not yet a checkPassable, but perhaps there should be.
-    // If that happens, we should call it here instead.
-    assertPassable(val);
-    return true;
-  }
-  if (keyMemo.has(val)) {
-    return true;
-  }
-  const result = checkKeyInternal(val, check);
-  if (result) {
-    // Don't cache the undefined cases, so that if it is tried again
-    // with `assertChecker` it'll throw a diagnostic again
-    keyMemo.add(val);
-  }
-  // Note that we do not memoize a negative judgement, so that if it is tried
-  // again with a checker, it will still produce a useful diagnostic.
-  return result;
-};
-harden(checkKey);
-
-/**
- * @param {Passable} val
- * @returns {boolean}
- */
-export const isKey = val => checkKey(val);
-harden(isKey);
-
-/**
- * @param {Key} val
- */
-export const assertKey = val => {
-  checkKey(val, assertChecker);
-};
-harden(assertKey);

src/keys/compareKeys.js

@@ -5,5 +5,7 @@ // @ts-check
 
-import { passStyleOf, getTag } from '@agoric/marshal';
+import { passStyleOf, getTag } from '@endo/marshal';
 import { compareRank } from '../patterns/rankOrder.js';
 import { assertKey } from './checkKey.js';
+import { bagCompare } from './merge-bag-operators.js';
+import { setCompare } from './merge-set-operators.js';
 
@@ -84,3 +86,5 @@ const { details: X, quote: q } = assert;
       }
-      let result = 0; // start with hypothesis they are keyEQ
+      // Presume that both copyRecords have the same key order
+      // until encountering a property disproving that hypothesis.
+      let result = 0;
       for (const name of leftNames) {
@@ -103,7 +107,8 @@ const comp = compareKeys(left[name], right[name]);
       // If copyRecord X is smaller than copyRecord Y, then they must have the
-      // same property names, and every value is X must be smaller or equal to
-      // every corresponding value in Y. The rank order of X and Y is based
-      // on lexicographic rank order of their values, as organized by the
-      // reverse order of their property names. Thus
-      // if compareKeys(X,Y) < 0 then compareRank(X,Y) <= 0.
+      // same property names and every value in X must be smaller or equal to
+      // the corresponding value in Y (with at least one value smaller).
+      // The rank order of X and Y is based on lexicographic rank order of
+      // their values, as organized by reverse lexicographic order of their
+      // property names.
+      // Thus if compareKeys(X,Y) < 0 then compareRank(X,Y) < 0.
       return result;
@@ -121,68 +126,13 @@ }
           // copySet X is smaller than copySet Y when every element of X
-          // is keyEQ to some element of Y.
-          // The following algorithm is good when there are few elements tied
-          // for the same rank. But it is O(N*M) in the size of these ties.
-          // Sets of remotables are a particularly bad case. For these, some
-          // kind of hash table (scalar set or map) should be used instead.
-
-          // TODO to get something working, I am currently implementing
-          // only the special case where there are no rank-order ties.
-
-          let result = 0; // start with the hypothesis they are keyEQ.
-          const xs = left.payload;
-          const ys = right.payload;
-          const xlen = xs.length;
-          const ylen = ys.length;
-          let xi = 0;
-          let yi = 0;
-          while (xi < xlen && yi < ylen) {
-            const x = xs[xi];
-            const y = ys[yi];
-            if (xi + 1 < xlen && compareRank(x, xs[xi + 1]) === 0) {
-              assert.fail(X`sets with rank ties not yet implemented: ${left}`);
-            }
-            if (yi + 1 < ylen && compareRank(y, ys[yi + 1]) === 0) {
-              assert.fail(X`sets with rank ties not yet implemented: ${right}`);
-            }
-            const comp = compareKeys(x, y);
-            if (Number.isNaN(comp)) {
-              // If they are incommensurate, then each element is not in the
-              // other set, so the sets are incommensurate.
-              return NaN;
-            } else if (comp === 0) {
-              //
-              xi += 1;
-              yi += 1;
-            } else {
-              if (result !== comp) {
-                if (result === 0) {
-                  result = comp;
-                } else {
-                  assert(
-                    (result === -1 && comp === 1) ||
-                      (result === 1 && comp === -1),
-                  );
-                  return NaN;
-                }
-              }
-              if (comp === 1) {
-                xi += 1;
-              } else {
-                assert(comp === -1);
-                yi += 1;
-              }
-            }
-          }
-          const comp = compareKeys(xlen, ylen);
-          if (comp === 0) {
-            return result;
-          } else if (result === 0 || result === comp) {
-            return comp;
-          } else {
-            assert(
-              (result === -1 && comp === 1) || (result === 1 && comp === -1),
-            );
-            return NaN;
-          }
+          // is keyEQ to some element of Y and some element of Y is
+          // not keyEQ to any element of X.
+          return setCompare(left, right);
         }
+        case 'copyBag': {
+          // copyBag X is smaller than copyBag Y when every element of X
+          // occurs no more than the keyEQ element of Y, and some element
+          // of Y occurs more than some element of X, where being absent
+          // from X counts as occuring zero times.
+          return bagCompare(left, right);
+        }
         case 'copyMap': {
@@ -189,0 +139,0 @@ // Two copyMaps that have different keys (according to keyEQ) are

src/keys/copySet.js

 // @ts-check
 
+import { assertChecker, makeTagged, passStyleOf } from '@endo/marshal';
 import {
-  assertChecker,
-  getTag,
-  makeTagged,
-  passStyleOf,
-} from '@agoric/marshal';
-import {
   compareAntiRank,
@@ -21,11 +16,31 @@ isRankSorted,
 /**
- * @param {FullCompare} fullCompare
- * @returns {(keys: Key[], check?: Checker) => boolean}
+ * @template T
+ * @param {T[]} elements
+ * @param {FullCompare=} fullCompare If provided and `elements` is already known
+ * to be sorted by this `fullCompare`, then we should get a memo hit rather
+ * than a resorting. However, currently, we still enumerate the entire array
+ * each time.
+ *
+ * TODO: If doing this reduntantly turns out to be expensive, we
+ * could memoize this no-duplicate finding as well, independent
+ * of the `fullOrder` use to reach this finding.
+ * @param {Checker=} check
+ * @returns {boolean}
  */
-export const makeCheckNoDuplicates = fullCompare => (keys, check = x => x) => {
-  keys = sortByRank(keys, fullCompare);
-  const { length } = keys;
+const checkNoDuplicates = (
+  elements,
+  fullCompare = undefined,
+  check = x => x,
+) => {
+  // This fullOrder contains history dependent state. It is specific
+  // to this one call and does not survive it.
+  // TODO Once all our tooling is ready for `&&=`, the following
+  // line should be rewritten using it.
+  fullCompare = fullCompare || makeFullOrderComparatorKit().antiComparator;
+
+  elements = sortByRank(elements, fullCompare);
+  const { length } = elements;
   for (let i = 1; i < length; i += 1) {
-    const k0 = keys[i - 1];
-    const k1 = keys[i];
+    const k0 = elements[i - 1];
+    const k1 = elements[i];
     if (fullCompare(k0, k1) === 0) {
@@ -39,112 +54,51 @@ return check(false, X`value has duplicates: ${k0}`);
 /**
- * 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.
+ * @template T
+ * @param {T[]} elements
+ * @param {FullCompare=} fullCompare
+ * @returns {void}
  */
-const fullCompare = makeFullOrderComparatorKit(true).antiComparator;
+export const assertNoDuplicates = (elements, fullCompare = undefined) => {
+  checkNoDuplicates(elements, fullCompare, assertChecker);
+};
 
-const checkNoDuplicates = makeCheckNoDuplicates(fullCompare);
-
 /**
- * @param {Passable[]} keys
+ * @param {Passable[]} elements
  * @param {Checker=} check
  * @returns {boolean}
  */
-export const checkCopySetKeys = (keys, check = x => x) => {
-  if (passStyleOf(keys) !== 'copyArray') {
+export const checkElements = (elements, check = x => x) => {
+  if (passStyleOf(elements) !== 'copyArray') {
     return check(
       false,
-      X`The keys of a copySet or copyMap must be a copyArray: ${keys}`,
+      X`The keys of a copySet or copyMap must be a copyArray: ${elements}`,
     );
   }
-  if (!isRankSorted(keys, compareAntiRank)) {
+  if (!isRankSorted(elements, compareAntiRank)) {
     return check(
       false,
-      X`The keys of a copySet or copyMap must be sorted in reverse rank order: ${keys}`,
+      X`The keys of a copySet or copyMap must be sorted in reverse rank order: ${elements}`,
     );
   }
-  return checkNoDuplicates(keys, check);
+  return checkNoDuplicates(elements, undefined, check);
 };
-harden(checkCopySetKeys);
+harden(checkElements);
 
-/** @type WeakSet<CopySet<Key>> */
-const copySetMemo = new WeakSet();
+export const assertElements = elements =>
+  checkElements(elements, assertChecker);
+harden(assertElements);
 
-/**
- * @param {Passable} s
- * @param {Checker=} check
- * @returns {boolean}
- */
-export const checkCopySet = (s, check = x => x) => {
-  if (copySetMemo.has(s)) {
-    return true;
-  }
-  const result =
-    check(
-      passStyleOf(s) === 'tagged' && getTag(s) === 'copySet',
-      X`Not a copySet: ${s}`,
-    ) && checkCopySetKeys(s.payload, check);
-  if (result) {
-    copySetMemo.add(s);
-  }
-  return result;
+export const coerceToElements = elementsList => {
+  const elements = sortByRank(elementsList, compareAntiRank);
+  assertElements(elements);
+  return elements;
 };
-harden(checkCopySet);
+harden(coerceToElements);
 
 /**
- * @callback IsCopySet
- * @param {Passable} s
- * @returns {s is CopySet<Key>}
- */
-
-/** @type {IsCopySet} */
-export const isCopySet = s => checkCopySet(s);
-harden(isCopySet);
-
-/**
- * @callback AssertCopySet
- * @param {Passable} s
- * @returns {asserts s is CopySet<Key>}
- */
-
-/** @type {AssertCopySet} */
-export const assertCopySet = s => {
-  checkCopySet(s, assertChecker);
-};
-harden(assertCopySet);
-
-/**
  * @template K
- * @param {CopySet<K>} s
- * @returns {K[]}
- */
-export const getCopySetKeys = s => {
-  assertCopySet(s);
-  return s.payload;
-};
-harden(getCopySetKeys);
-
-/**
- * @template K
- * @param {CopySet<K>} s
- * @param {(key: K, index: number) => boolean} fn
- * @returns {boolean}
- */
-export const everyCopySetKey = (s, fn) =>
-  getCopySetKeys(s).every((key, index) => fn(key, index));
-harden(everyCopySetKey);
-
-/**
- * @template K
- * @param {Iterable<K>} elements
+ * @param {Iterable<K>} elementIter
  * @returns {CopySet<K>}
  */
-export const makeCopySet = elements => {
-  const result = makeTagged('copySet', sortByRank(elements, compareAntiRank));
-  assertCopySet(result);
-  return result;
-};
-harden(makeCopySet);
+export const makeSetOfElements = elementIter =>
+  makeTagged('copySet', coerceToElements(elementIter));
+harden(makeSetOfElements);

src/keys/merge-set-operators.js

 // @ts-check
 
-import { sortByRank } from '../patterns/rankOrder.js';
 import {
-  getCopySetKeys,
-  makeCheckNoDuplicates,
-  makeCopySet,
-} from './copySet.js';
+  assertRankSorted,
+  compareAntiRank,
+  makeFullOrderComparatorKit,
+  sortByRank,
+} from '../patterns/rankOrder.js';
+import { assertNoDuplicates, makeSetOfElements } from './copySet.js';
 
-const { details: X } = assert;
+const { details: X, quote: q } = assert;
 
 /**
- * Different than any valid value. Therefore, must not escape this module.
+ * Asserts that `elements` is already rank sorted by `rankCompare`, where there
+ * may be contiguous regions of elements tied for the same rank.
+ * Returns an iterable that will enumerate all the elements in order
+ * according to `fullOrder`, which should differ from `rankOrder` only
+ * by being more precise.
  *
- * @typedef {symbol} Pumpkin
+ * This should be equivalent to resorting the entire `elements` array according
+ *  to `fullOrder`. However, it optimizes for the case where these contiguous
+ * runs that need to be resorted are either absent or small.
+ *
+ * @template T
+ * @param {T[]} elements
+ * @param {RankCompare} rankCompare
+ * @param {FullCompare} fullCompare
+ * @returns {Iterable<T>}
  */
-const PUMPKIN = Symbol('pumpkin');
+const windowResort = (elements, rankCompare, fullCompare) => {
+  assertRankSorted(elements, rankCompare);
+  const { length } = elements;
+  let i = 0;
+  let optInnerIterator;
+  return harden({
+    [Symbol.iterator]: () =>
+      harden({
+        next: () => {
+          if (optInnerIterator) {
+            const result = optInnerIterator.next();
+            if (result.done) {
+              optInnerIterator = undefined;
+              // fall through
+            } else {
+              return result;
+            }
+          }
+          if (i < length) {
+            const value = elements[i];
+            let j = i + 1;
+            while (j < length && rankCompare(value, elements[j]) === 0) {
+              j += 1;
+            }
+            if (j === i + 1) {
+              i = j;
+              return harden({ done: false, value });
+            }
+            const similarRun = elements.slice(i, j);
+            i = j;
+            const resorted = sortByRank(similarRun, fullCompare);
+            // Providing the same `fullCompare` should cause a memo hit
+            // within `assertNoDuplicates` enabling it to avoid a
+            // redundant resorting.
+            assertNoDuplicates(resorted, fullCompare);
+            // This is the raw JS array iterator whose `.next()` method
+            // does not harden the IteratorResult, in violation of our
+            // conventions. Fixing this is expensive and I'm confident the
+            // unfrozen value does not escape this file, so I'm leaving this
+            // as is.
+            optInnerIterator = resorted[Symbol.iterator]();
+            return optInnerIterator.next();
+          } else {
+            return harden({ done: true, value: null });
+          }
+        },
+      }),
+  });
+};
 
 /**
+ * Returns an iterable whose iteration results are [key, xCount, yCount] tuples
+ * representing the next key in the local full order, as well as how many
+ * times it ocurred in the x input iterator and the y input interator.
+ *
+ * For sets, these counts are always 0 or 1, but this representation
+ * generalizes nicely for bags.
+ *
  * @template T
- * @typedef {T | Pumpkin} Opt
+ * @param {T[]} xelements
+ * @param {T[]} yelements
+ * @returns {Iterable<[T,bigint,bigint]>}
  */
+const merge = (xelements, yelements) => {
+  // This fullOrder contains history dependent state. It is specific
+  // to this one `merge` call and does not survive it.
+  const fullCompare = makeFullOrderComparatorKit().antiComparator;
 
-/**
- * @template T
- * @param {Iterable<T>} xs
- * @param {Iterable<T>} ys
- * @param {FullCompare} fullCompare
- * @returns {Iterable<[Opt<T>,Opt<T>]>}
- */
-const merge = (xs, ys, fullCompare) => {
+  const xs = windowResort(xelements, compareAntiRank, fullCompare);
+  const ys = windowResort(yelements, compareAntiRank, fullCompare);
   return harden({
     [Symbol.iterator]: () => {
+      // These four `let` variables are buffering one ahead from the underlying
+      // iterators. Each iteration reports one or the other or both, and
+      // then refills the buffers of those it advanced.
+      /** @type {T} */
+      let x;
+      let xDone;
+      /** @type {T} */
+      let y;
+      let yDone;
+
       const xi = xs[Symbol.iterator]();
-      /** @type {Opt<T>} */
-      let x; // PUMPKIN when done
       const nextX = () => {
-        assert(x !== PUMPKIN);
-        const { done, value } = xi.next();
-        x = done ? PUMPKIN : value;
+        assert(!xDone, X`Internal: nextX should not be called once done`);
+        ({ done: xDone, value: x } = xi.next());
       };
@@ -45,8 +120,5 @@ nextX();
       const yi = ys[Symbol.iterator]();
-      /** @type {Opt<T>} */
-      let y; // PUMPKIN when done
       const nextY = () => {
-        assert(y !== PUMPKIN);
-        const { done, value } = yi.next();
-        y = done ? PUMPKIN : value;
+        assert(!yDone, X`Internal: nextY should not be called once done`);
+        ({ done: yDone, value: y } = yi.next());
       };
@@ -59,11 +131,15 @@ nextY();
           let done = false;
-          /** @type {[Opt<T>,Opt<T>]} */
-          let value = [x, y];
-          if (x === PUMPKIN && y === PUMPKIN) {
+          /** @type {[T,bigint,bigint]} */
+          let value;
+          if (xDone && yDone) {
             done = true;
-          } else if (x === PUMPKIN) {
+            // @ts-ignore Because the terminating value does not matter
+            value = [null, 0n, 0n];
+          } else if (xDone) {
             // only ys are left
+            value = [y, 0n, 1n];
             nextY();
-          } else if (y === PUMPKIN) {
+          } else if (yDone) {
             // only xs are left
+            value = [x, 1n, 0n];
             nextX();
@@ -74,2 +150,3 @@ } else {
               // x and y are equivalent, so report both
+              value = [x, 1n, 1n];
               nextX();
@@ -79,8 +156,8 @@ nextY();
               // x is earlier, so report it
-              value = [x, PUMPKIN];
+              value = [x, 1n, 0n];
               nextX();
             } else {
               // y is earlier, so report it
-              assert(comp > 0);
-              value = [PUMPKIN, y];
+              assert(comp > 0, X`Internal: Unexpected comp ${q(comp)}`);
+              value = [y, 0n, 1n];
               nextY();
@@ -97,5 +174,5 @@ }
 
-const isIterSuperset = xyi => {
-  for (const [x, _yr] of xyi) {
-    if (x === PUMPKIN) {
+const iterIsSuperset = xyi => {
+  for (const [_m, xc, _yc] of xyi) {
+    if (xc === 0n) {
       // something in y is not in x, so x is not a superset of y
@@ -108,5 +185,5 @@ return false;
 
-const isIterDisjoint = xyi => {
-  for (const [x, y] of xyi) {
-    if (x !== PUMPKIN && y !== PUMPKIN) {
+const iterIsDisjoint = xyi => {
+  for (const [_m, xc, yc] of xyi) {
+    if (xc >= 1n && yc >= 1n) {
       // Something in both, so not disjoint
@@ -119,13 +196,41 @@ return false;
 
+const iterCompare = xyi => {
+  let loneY = false;
+  let loneX = false;
+  for (const [_m, xc, yc] of xyi) {
+    if (xc === 0n) {
+      // something in y is not in x, so x is not a superset of y
+      loneY = true;
+    }
+    if (yc === 0n) {
+      // something in x is not in y, so y is not a superset of x
+      loneX = true;
+    }
+    if (loneX && loneY) {
+      return NaN;
+    }
+  }
+  if (loneX) {
+    return 1;
+  } else if (loneY) {
+    return -1;
+  } else {
+    assert(
+      !loneX && !loneY,
+      X`Internal: Unexpected lone pair ${q([loneX, loneY])}`,
+    );
+    return 0;
+  }
+};
+
 const iterUnion = xyi => {
   const result = [];
-  for (const [x, y] of xyi) {
-    if (x !== PUMPKIN) {
-      result.push(x);
+  for (const [m, xc, yc] of xyi) {
+    if (xc >= 0n) {
+      result.push(m);
     } else {
-      assert(y !== PUMPKIN);
+      assert(yc >= 0n, X`Internal: Unexpected count ${q(yc)}`);
       // if x and y were both ready, then they were equivalent and
-      // above clause already took care of it. Only push y
-      // if x was absent.
-      result.push(y);
+      // above clause already took care of it. Otherwise push here.
+      result.push(m);
     }
@@ -138,12 +243,9 @@ }
   const result = [];
-  for (const [x, y] of xyi) {
-    assert(
-      x === PUMPKIN || y === PUMPKIN,
-      X`Sets must not have common elements: ${x}`,
-    );
-    if (x !== PUMPKIN) {
-      result.push(x);
+  for (const [m, xc, yc] of xyi) {
+    assert(xc === 0n || yc === 0n, X`Sets must not have common elements: ${m}`);
+    if (xc >= 1n) {
+      result.push(m);
     } else {
-      assert(y !== PUMPKIN);
-      result.push(y);
+      assert(yc >= 1n, X`Internal: Unexpected count ${q(yc)}`);
+      result.push(m);
     }
@@ -156,6 +258,6 @@ }
   const result = [];
-  for (const [x, y] of xyi) {
-    if (x !== PUMPKIN && y !== PUMPKIN) {
+  for (const [m, xc, yc] of xyi) {
+    if (xc >= 1n && yc >= 1n) {
       // If they are both present, then they were equivalent
-      result.push(x);
+      result.push(m);
     }
@@ -168,7 +270,7 @@ }
   const result = [];
-  for (const [x, y] of xyi) {
-    assert(x !== PUMPKIN, X`right element ${y} was not in left`);
-    if (y === PUMPKIN) {
+  for (const [m, xc, yc] of xyi) {
+    assert(xc >= 1n, X`right element ${m} was not in left`);
+    if (yc === 0n) {
       // the x was not in y
-      result.push(x);
+      result.push(m);
     }
@@ -179,70 +281,25 @@ }
 
-/**
- * @template T
- * @typedef {Object} SetOps
- *
- * @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
- */
+const mergeify = iterOp => (xelements, yelements) =>
+  iterOp(merge(xelements, yelements));
 
-/**
- * @template T
- * @param {FullCompare} fullCompare
- * Must be a total order, not just a rank order. See makeFullOrderComparatorKit.
- * @returns {SetOps<T>}
- */
-export const makeSetOps = fullCompare => {
-  const checkNoDuplicates = makeCheckNoDuplicates(fullCompare);
+export const elementsIsSuperset = mergeify(iterIsSuperset);
+export const elementsIsDisjoint = mergeify(iterIsDisjoint);
+export const elementsCompare = mergeify(iterCompare);
+export const elementsUnion = mergeify(iterUnion);
+export const elementsDisjointUnion = mergeify(iterDisjointUnion);
+export const elementsIntersection = mergeify(iterIntersection);
+export const elementsDisjointSubtract = mergeify(iterDisjointSubtract);
 
-  const listify = iterOp => (xlist, ylist) => {
-    const xs = sortByRank(xlist, fullCompare);
-    const ys = sortByRank(ylist, fullCompare);
-    const xyi = merge(xs, ys, fullCompare);
-    return iterOp(xyi);
-  };
+const rawSetify = elementsOp => (xset, yset) =>
+  elementsOp(xset.payload, yset.payload);
 
-  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 setify = elementsOp => (xset, yset) =>
+  makeSetOfElements(elementsOp(xset.payload, yset.payload));
 
-  const rawSetify = listOp => (xset, yset) =>
-    listOp(getCopySetKeys(xset), getCopySetKeys(yset));
-
-  const setify = listOp => (xset, yset) =>
-    makeCopySet(listOp(getCopySetKeys(xset), getCopySetKeys(yset)));
-
-  return harden({
-    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);
+export const setIsSuperset = rawSetify(elementsIsSuperset);
+export const setIsDisjoint = rawSetify(elementsIsDisjoint);
+export const setCompare = rawSetify(elementsCompare);
+export const setUnion = setify(elementsUnion);
+export const setDisjointUnion = setify(elementsDisjointUnion);
+export const setIntersection = setify(elementsIntersection);
+export const setDisjointSubtract = setify(elementsDisjointSubtract);

src/patterns/patternMatchers.js

@@ -10,3 +10,3 @@ // @ts-check
   hasOwnPropertyOf,
-} from '@agoric/marshal';
+} from '@endo/marshal';
 import {
@@ -26,5 +26,7 @@ compareAntiRank,
   isScalarKey,
+  checkCopySet,
+  checkCopyBag,
+  checkCopyMap,
+  copyMapKeySet,
 } from '../keys/checkKey.js';
-import { checkCopySet /* , makeCopySet XXX TEMP */ } from '../keys/copySet.js';
-import { checkCopyMap, copyMapKeySet } from '../keys/copyMap.js';
 
@@ -122,2 +124,16 @@ /// <reference types="ses"/>
           }
+          case 'copyBag': {
+            if (!checkCopyBag(patt, check)) {
+              return false;
+            }
+            // If it is a CopyBag, then it must also be a key and we
+            // should never get here.
+            if (isKey(patt)) {
+              assert.fail(
+                X`internal: The key case should have been dealt with earlier: ${patt}`,
+              );
+            } else {
+              assert.fail(X`A CopyMap must be a Key but was not: ${patt}`);
+            }
+          }
           case 'copyMap': {
@@ -140,3 +156,3 @@ return (
               false,
-              X`A passable tagged ${q(tag)} is not a key: ${patt}`,
+              X`A passable tagged ${q(tag)} is not a pattern: ${patt}`,
             );
@@ -810,2 +826,19 @@ }
   /** @type {MatchHelper} */
+  const matchBagOfHelper = Far('match:bagOf helper', {
+    checkMatches: (specimen, keyPatt, check = x => x) =>
+      check(
+        passStyleOf(specimen) === 'tagged' && getTag(specimen) === 'copyBag',
+        X`${specimen} - Must be a a CopyBag`,
+      ) &&
+      specimen.payload.every(([key, _count]) => checkMatches(key, keyPatt)),
+
+    checkIsMatcherPayload: checkPattern,
+
+    getRankCover: () => getPassStyleCover('tagged'),
+
+    checkKeyPattern: (_, check = x => x) =>
+      check(false, X`CopySets not yet supported as keys`),
+  });
+
+  /** @type {MatchHelper} */
   const matchMapOfHelper = Far('match:mapOf helper', {
@@ -981,2 +1014,3 @@ checkMatches: (specimen, [keyPatt, valuePatt], check = x => x) =>
     'match:setOf': matchSetOfHelper,
+    'match:bagOf': matchBagOfHelper,
     'match:mapOf': matchMapOfHelper,
@@ -1008,2 +1042,3 @@ 'match:split': matchSplitHelper,
   const SetShape = makeKindMatcher('copySet');
+  const BagShape = makeKindMatcher('copyBag');
   const MapShape = makeKindMatcher('copyMap');
@@ -1035,2 +1070,3 @@ const RemotableShape = makeKindMatcher('remotable');
     set: () => SetShape,
+    bag: () => BagShape,
     map: () => MapShape,
@@ -1057,2 +1093,3 @@ remotable: () => RemotableShape,
     setOf: (keyPatt = M.any()) => makeMatcher('match:setOf', keyPatt),
+    bagOf: (keyPatt = M.any()) => makeMatcher('match:bagOf', keyPatt),
     mapOf: (keyPatt = M.any(), valuePatt = M.any()) =>
@@ -1091,3 +1128,4 @@ makeMatcher('match:mapOf', [keyPatt, valuePatt]),
   isKeyPattern,
+  getRankCover,
   M,
 } = makePatternKit();

src/patterns/rankOrder.js

@@ -9,3 +9,3 @@ // @ts-check
   sameValueZero,
-} from '@agoric/marshal';
+} from '@endo/marshal';
 
@@ -12,0 +12,0 @@ const { fromEntries, entries, setPrototypeOf } = Object;

src/stores/scalarMapStore.js

@@ -8,6 +8,5 @@ // @ts-check
   mapIterable,
-} from '@agoric/marshal';
+} from '@endo/marshal';
 import { compareRank } from '../patterns/rankOrder.js';
-import { assertScalarKey } from '../keys/checkKey.js';
-import { makeCopyMap } from '../keys/copyMap.js';
+import { assertScalarKey, makeCopyMap } from '../keys/checkKey.js';
 import { matches, fit, assertPattern } from '../patterns/patternMatchers.js';
@@ -132,3 +131,3 @@ import { makeWeakMapStoreMethods } from './scalarWeakMapStore.js';
  * @param {string} [keyName='key'] - the column name for the key
- * @param {Partial<StoreOptions>=} options
+ * @param {StoreOptions=} options
  * @returns {MapStore<K,V>}
@@ -138,10 +137,10 @@ */
   keyName = 'key',
-  { keyPattern = undefined, valuePattern = undefined } = {},
+  { keySchema = undefined, valueSchema = undefined } = {},
 ) => {
   const jsmap = new Map();
-  if (keyPattern !== undefined) {
-    assertPattern(keyPattern);
+  if (keySchema !== undefined) {
+    assertPattern(keySchema);
   }
-  if (valuePattern !== undefined) {
-    assertPattern(valuePattern);
+  if (valueSchema !== undefined) {
+    assertPattern(valueSchema);
   }
@@ -155,4 +154,4 @@
     assertPassable(value);
-    if (valuePattern !== undefined) {
-      fit(value, valuePattern);
+    if (valueSchema !== undefined) {
+      fit(value, valueSchema);
     }
@@ -167,4 +166,4 @@ };
     assertScalarKey(key);
-    if (keyPattern !== undefined) {
-      fit(key, keyPattern);
+    if (keySchema !== undefined) {
+      fit(key, keySchema);
     }
@@ -171,0 +170,0 @@ assertKVOkToSet(key, value);

src/stores/scalarSetStore.js

 // @ts-check
 
-import { Far, filterIterable } from '@agoric/marshal';
+import { Far, filterIterable } from '@endo/marshal';
 import { compareRank } from '../patterns/rankOrder.js';
-import { assertScalarKey } from '../keys/checkKey.js';
-import { makeCopySet } from '../keys/copySet.js';
+import { assertScalarKey, makeCopySet } from '../keys/checkKey.js';
 import { matches, fit, assertPattern } from '../patterns/patternMatchers.js';
@@ -87,3 +86,3 @@ import { makeWeakSetStoreMethods } from './scalarWeakSetStore.js';
  * @param {string} [keyName='key'] - the column name for the key
- * @param {Partial<StoreOptions>=} options
+ * @param {StoreOptions=} options
  * @returns {SetStore<K>}
@@ -93,7 +92,7 @@ */
   keyName = 'key',
-  { keyPattern = undefined } = {},
+  { keySchema = undefined } = {},
 ) => {
   const jsset = new Set();
-  if (keyPattern !== undefined) {
-    assertPattern(keyPattern);
+  if (keySchema !== undefined) {
+    assertPattern(keySchema);
   }
@@ -107,4 +106,4 @@
     assertScalarKey(key);
-    if (keyPattern !== undefined) {
-      fit(key, keyPattern);
+    if (keySchema !== undefined) {
+      fit(key, keySchema);
     }
@@ -111,0 +110,0 @@ };

src/stores/scalarWeakMapStore.js

 // @ts-check
 
-import { Far, assertPassable, passStyleOf } from '@agoric/marshal';
+import { Far, assertPassable, passStyleOf } from '@endo/marshal';
 import { fit, assertPattern } from '../patterns/patternMatchers.js';
@@ -86,3 +86,3 @@
  * @param {string} [keyName='key'] - the column name for the key
- * @param {Partial<StoreOptions>=} options
+ * @param {StoreOptions=} options
  * @returns {WeakMapStore<K,V>}
@@ -92,10 +92,10 @@ */
   keyName = 'key',
-  { longLived = true, keyPattern = undefined, valuePattern = undefined } = {},
+  { longLived = true, keySchema = undefined, valueSchema = undefined } = {},
 ) => {
   const jsmap = new (longLived ? WeakMap : Map)();
-  if (keyPattern !== undefined) {
-    assertPattern(keyPattern);
+  if (keySchema !== undefined) {
+    assertPattern(keySchema);
   }
-  if (valuePattern !== undefined) {
-    assertPattern(valuePattern);
+  if (valueSchema !== undefined) {
+    assertPattern(valueSchema);
   }
@@ -109,4 +109,4 @@
     assertPassable(value);
-    if (valuePattern !== undefined) {
-      fit(value, valuePattern);
+    if (valueSchema !== undefined) {
+      fit(value, valueSchema);
     }
@@ -124,4 +124,4 @@ };
     );
-    if (keyPattern !== undefined) {
-      fit(key, keyPattern);
+    if (keySchema !== undefined) {
+      fit(key, keySchema);
     }
@@ -128,0 +128,0 @@ assertKVOkToSet(key, value);

src/stores/scalarWeakSetStore.js

 // @ts-check
 
-import { Far, passStyleOf } from '@agoric/marshal';
+import { Far, passStyleOf } from '@endo/marshal';
 import { fit, assertPattern } from '../patterns/patternMatchers.js';
@@ -68,3 +68,3 @@
  * @param {string} [keyName='key'] - the column name for the key
- * @param {Partial<StoreOptions>=} options
+ * @param {StoreOptions=} options
  * @returns {WeakSetStore<K>}
@@ -74,7 +74,7 @@ */
   keyName = 'key',
-  { longLived = true, keyPattern = undefined } = {},
+  { longLived = true, keySchema = undefined } = {},
 ) => {
   const jsset = new (longLived ? WeakSet : Set)();
-  if (keyPattern !== undefined) {
-    assertPattern(keyPattern);
+  if (keySchema !== undefined) {
+    assertPattern(keySchema);
   }
@@ -91,4 +91,4 @@
     );
-    if (keyPattern !== undefined) {
-      fit(key, keyPattern);
+    if (keySchema !== undefined) {
+      fit(key, keySchema);
     }
@@ -95,0 +95,0 @@ };

src/stores/store-utils.js

 // @ts-check
 
-import { Far } from '@agoric/marshal';
+import { Far } from '@endo/marshal';
 
@@ -5,0 +5,0 @@ const { details: X, quote: q } = assert;

src/types.js

@@ -8,11 +8,14 @@ // @ts-check
  * Keys are pass-by-copy structures (CopyArray, CopyRecord,
- * CopySet, CopyMap) that end in either passable primitive data or
+ * CopySet, CopyBag, CopyMap) that end in either passable primitive data or
  * Remotables (Far objects or their remote presences.) Keys are so named
  * because they can be used as keys in MapStores and CopyMaps, as well as
- * the elements of CopySets.
+ * the elements of CopySets and CopyBags.
  *
  * Keys cannot contain promises or errors, as these do not have a useful
  * distributed equality semantics. Keys also cannot contain any CopyTagged
- * except for those recognized as CopySets and CopyMaps.
+ * except for those recognized as CopySets, CopyBags, and CopyMaps.
  *
+ * Be aware that we may recognize more CopyTaggeds over time, including
+ * CopyTaggeds recognized as keys.
+ *
  * Distributed equality is location independent.
@@ -26,3 +29,3 @@ * The same two keys, passed to another location, will be equal there iff
  * Patterns are pass-by-copy structures (CopyArray, CopyRecord,
- * CopySet, CopyMap) that end in either Keys or Matchers. Each pattern
+ * CopySet, CopyBag, CopyMap) that end in either Keys or Matchers. Each pattern
  * acts as a declarative passable predicate over passables, where each passable
@@ -37,4 +40,7 @@ * either passes a given pattern, or does not. Every key is also a pattern.
  * Patterns also cannot contain any CopyTaggeds except for those recognized as
- * CopySets, CopyMaps, or Matchers.
+ * CopySets, CopyBags, CopyMaps, or Matchers.
  *
+ * Be aware that we may recognize more CopyTaggeds over time, including
+ * CopyTaggeds recognized as patterns.
+ *
  * Whether a passable matches a given pattern is location independent.
@@ -71,2 +77,7 @@ * For a passable and a pattern, both passed to another location, the passable
 /**
+ * @template K
+ * @typedef {CopyTagged} CopyBag
+ */
+
+/**
  * @template K,V
@@ -91,4 +102,7 @@ * @typedef {CopyTagged} CopyMap
  * Defaults to true, so please mark short lived stores explicitly.
- * @property {Pattern=} keyPattern
- * @property {Pattern=} valuePattern
+ * @property {boolean=} durable  The contents of this store survive termination
+ *   of its containing process, allowing for restart or upgrade but at the cost
+ *   of forbidding storage of references to ephemeral data.  Defaults to false.
+ * @property {Pattern=} keySchema
+ * @property {Pattern=} valueSchema
  */
@@ -250,4 +264,4 @@
  * 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`.
+ * a total preorder in which different elements are always comparable but
+ * can be tied for the same rank. See `RankCompare`.
  */
@@ -261,9 +275,9 @@
  * This comparison function is valid as argument to
- * `Array.prototype.sort`. This is often described as a "total order"
- * but, depending on your definitions, this is technically incorrect
- * because it may return `0` to indicate that two distinguishable elements,
- * like `-0` and `0`, are tied, i.e., are in the same equivalence class
- * as far as this ordering is concerned. If each such equivalence class is
+ * `Array.prototype.sort`. This is sometimes described as a "total order"
+ * but, depending on your definitions, this is technically incorrect because
+ * it may return `0` to indicate that two distinguishable elements such as
+ * `-0` and `0` are tied (i.e., are in the same equivalence class
+ * for the purposes of this ordering). If each such equivalence class is
  * a *rank* and ranks are disjoint, then this "rank order" is a
- * total order among these ranks. In mathematics this goes by several
+ * true total order over these ranks. In mathematics this goes by several
  * other names such as "total preorder".
@@ -277,8 +291,8 @@ *
  * lookups based on those comparisons. For example, in order to get a total
- * order among ranks, we put `NaN` after all other JavaScript "number" values.
- * But otherwise, we order JavaScript numbers by magnitude,
- * with `-0` tied with `0`. A semantically useful ordering of JavaScript number
- * values, i.e., IEEE floating point values, would compare magnitudes, and
- * so agree with the rank ordering everywhere except `NaN`. An array sorted by
- * rank would enable range queries by magnitude.
+ * order among ranks, we put `NaN` after all other JavaScript "number" values
+ * (i.e., IEEE 754 floating-point values). But otherwise, we rank JavaScript
+ * numbers by signed magnitude, with `0` and `-0` tied. A semantically useful
+ * ordering would also compare magnitudes, and so agree with the rank ordering
+ * of all values other than `NaN`. An array sorted by rank would enable range
+ * queries by magnitude.
  * @param {Passable} left
@@ -337,3 +351,3 @@ * @param {Passable} right
  *
- * Key order (a partial order) and rank order (a full order) are
+ * Key order (a partial order) and rank order (a total preorder) are
  * co-designed so that we store passables in rank order and index into them
@@ -350,10 +364,12 @@ * with keys for key-based queries. To keep these distinct, when speaking
  * `compareRank(X,Y) === 0`. But not vice versa. For example, two different
- * remotables are the same rank but incommensurate as keys.
+ * remotables are the same rank but incomparable 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}`.
+ * `compareRank(X,Y) < 0`, i.e., if X is smaller than Y in key order, then X
+ * must be earlier than Y in rank order. But not vice versa.
+ * X can be equivalent to or earlier than Y in rank order and still be
+ * incomparable with Y in key order. For example, the record `{b: 3, a: 5}` is
+ * earlier than the record `{b: 5, a: 3}` in rank order but they are
+ * incomparable as keys. And two distinct remotables such as `Far('X', {})` and
+ * `Far('Y', {})` are equivalent in rank order but incomparable as keys.
  *
@@ -462,3 +478,3 @@ * This lets us translate a range search over the
  * @property {() => Matcher} key
- * Can be in a copySet or the key in a CopyMap.
+ * Can be in a copySet or CopyBag, or the key in a CopyMap.
  * (Will eventually be able to a key is a MapStore.)
@@ -481,2 +497,3 @@ * All keys are patterns that match only themselves.
  * @property {() => Matcher} set A CopySet
+ * @property {() => Matcher} bag A CopyBag
  * @property {() => Matcher} map A CopyMap
@@ -515,2 +532,3 @@ * @property {() => Matcher} remotable A far object or its remote presence
  * @property {(keyPatt?: Pattern) => Matcher} setOf
+ * @property {(keyPatt?: Pattern) => Matcher} bagOf
  * @property {(keyPatt?: Pattern, valuePatt?: Pattern) => Matcher} mapOf
@@ -543,2 +561,3 @@ * @property {(
  * @property {(patt: Passable) => boolean} isKeyPattern
+ * @property {GetRankCover} getRankCover
  * @property {MatcherNamespace} M
@@ -545,0 +564,0 @@ */

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

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

170378

increased by13.13%

Number of package files

24

increased by4.35%

Lines of code

4204

increased by17.04%

Number of medium supply chain risk alerts

1

decreased by-50%

Dependency changes

• + Added@endo/marshal@^0.5.4

• + Added@endo/env-options@0.1.4(transitive)

• + Added@endo/eventual-send@0.14.8(transitive)

• + Added@endo/marshal@0.5.4(transitive)

• + Added@endo/nat@4.1.31(transitive)

• + Added@endo/promise-kit@0.2.60(transitive)

• + Addedses@0.18.8(transitive)

• - Removed@agoric/marshal@0.5.1-dev-0c4d32b.0+0c4d32b

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

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

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