Keys are Passable arbitrarily-nested pass-by-copy containers
(CopyArray, CopyRecord, CopySet, CopyBag, CopyMap) in which every
non-container leaf is either a Passable primitive value or a Remotable (a
remotely-accessible object or presence for a remote object), or such leaves
in isolation with no container.
Keys are so named because they can be used as keys in CopyMaps and
agoric-sdk Stores,
and as elements in CopySets and CopyBags.
Keys cannot contain promises or errors, as these do not have useful
distributed equality semantics. Keys also cannot contain any CopyTagged
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.
The same two Keys, passed to another location, will be keyEQ there iff
they are keyEQ here. (keyEQ tests equality according to the
key distributed equality semantics.)
Rank order and key order
The "key order" of compareKeys implements a partial order over Keys --- it defines relative position between two Keys but leaves some pairs incomparable (for example, subsets over sets is a partial order in which {} precedes {x} and {y}, which are mutually incomparable but both precede {x, y}).
It is co-designed with the "rank order" (a total preorder) of compareRank from @endo/marshal to support efficient range search for Key-based queries (for example, finding all entries in a map for which the key is a CopyRecord with particular fields can be implemented by selecting from rank-ordered keys those that are CopyRecords whose lexicographically greatest field is at least as big as the lexicographically greatest required field, and then filtering out matched keys that don't have the necessary shape).
Both functions use -1, 0, and 1 to respectively mean "less than", "equivalent to", and "greater than".
NaN means "incomparable" --- the first key is not less than, equivalent to, or greater than the second.
To keep the orders distinct when speaking informally, we use "earlier" and "later" for rank order, and "smaller" and "bigger" for key order.
The key ordering of compareKeys refines the rank ordering of compareRank but leaves gaps for which a more complete "full order" relies upon rank ordering:
compareKeys(X,Y) === 0 implies that compareRank(X,Y) === 0 --- if X
is equivalent to Y in key order, then X is equivalent to Y in rank order.
But the converse does not hold; for example, Remotables Far('X') and
Far('Y') are equivalent in rank order but incomparable in key order.
compareKeys(X,Y) < 0 implies that compareRank(X,Y) < 0 --- if X is
smaller than Y in key order, then X is earlier than Y in rank order.
But the converse does not hold; for example, the record {b: 3, a: 5}
is earlier than the record {b: 5, a: 3} in rank order but they are
incomparable in key order.
compareRank(X,Y) === 0 implies that compareKeys(X,Y) is either
0 or NaN --- Keys within the same rank are either equivalent to or
incomparable to each other in key order. But the converse does not hold;
for example, Far('X') and {} are incomparable in key order but not
equivalent in rank order.
compareRank(X,Y) === 0 and compareRank(X,Z) === 0 imply that
compareKeys(X,Y) and compareKeys(X,Z) are the same --- all Keys within
the same rank are either mutually equivalent or mutually incomparable, and
in fact only in the mutually incomparable case can the rank be said to
contain more than one key.
Keys are Passable arbitrarily-nested pass-by-copy containers (CopyArray, CopyRecord, CopySet, CopyBag, CopyMap) in which every non-container leaf is either a Passable primitive value or a Remotable (a remotely-accessible object or presence for a remote object), or such leaves in isolation with no container.
Keys are so named because they can be used as keys in CopyMaps and agoric-sdk Stores, and as elements in CopySets and CopyBags.
Keys cannot contain promises or errors, as these do not have useful distributed equality semantics. Keys also cannot contain any CopyTagged 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. The same two Keys, passed to another location, will be keyEQ there iff they are keyEQ here. (keyEQ tests equality according to the key distributed equality semantics.)
Rank order and key order
The "key order" of
compareKeysimplements a partial order over Keys --- it defines relative position between two Keys but leaves some pairs incomparable (for example, subsets over sets is a partial order in which {} precedes {x} and {y}, which are mutually incomparable but both precede {x, y}). It is co-designed with the "rank order" (a total preorder) ofcompareRankfrom@endo/marshalto support efficient range search for Key-based queries (for example, finding all entries in a map for which the key is a CopyRecord with particular fields can be implemented by selecting from rank-ordered keys those that are CopyRecords whose lexicographically greatest field is at least as big as the lexicographically greatest required field, and then filtering out matched keys that don't have the necessary shape). Both functions use-1,0, and1to respectively mean "less than", "equivalent to", and "greater than".NaNmeans "incomparable" --- the first key is not less than, equivalent to, or greater than the second. To keep the orders distinct when speaking informally, we use "earlier" and "later" for rank order, and "smaller" and "bigger" for key order.The key ordering of
compareKeysrefines the rank ordering ofcompareRankbut leaves gaps for which a more complete "full order" relies upon rank ordering:compareKeys(X,Y) === 0implies thatcompareRank(X,Y) === 0--- if X is equivalent to Y in key order, then X is equivalent to Y in rank order. But the converse does not hold; for example, RemotablesFar('X')andFar('Y')are equivalent in rank order but incomparable in key order.compareKeys(X,Y) < 0implies thatcompareRank(X,Y) < 0--- if X is smaller than Y in key order, then X is earlier than Y in rank order. But the converse does not hold; for example, the record{b: 3, a: 5}is earlier than the record{b: 5, a: 3}in rank order but they are incomparable in key order.compareRank(X,Y) === 0implies thatcompareKeys(X,Y)is either 0 or NaN --- Keys within the same rank are either equivalent to or incomparable to each other in key order. But the converse does not hold; for example,Far('X')and{}are incomparable in key order but not equivalent in rank order.compareRank(X,Y) === 0andcompareRank(X,Z) === 0imply thatcompareKeys(X,Y)andcompareKeys(X,Z)are the same --- all Keys within the same rank are either mutually equivalent or mutually incomparable, and in fact only in the mutually incomparable case can the rank be said to contain more than one key.