failure in elementsIsSuperset({x, y, z}, {z})

[dckc]

Describe the bug

An ERTP withdraw of {z} from a purse with a balance of {x, y, z} failed.

• odd {x, y, z} >= {z} failure in AmountMath.isGTE with AssetKind.SET Agoric/agoric-sdk#10292

I'm abbreviating makeCopySet(...items) using traditional {...items} set notation.

Investigation led to a failure in elementsIsSuperset({x, y, z}, {z}).

Steps to reproduce

test('{x, y, z} is superset of {z}', t => {
  const x = { instance: Remotable('Alleged: fooo'), description: 'fraz' };
  const y = { instance: Remotable('Alleged: fooo'), description: 'fraz' };
  const z = { instance: Remotable('Alleged: fooo'), description: 'alan' };

  const mainList = harden([x, y, z]);
  const withdraw = harden([z]);

  t.true(elementsIsSuperset(mainList, withdraw));
});

Expected behavior

elementsIsSuperset({x, y, z}, {z}) always returns true for keys x, y, and z.

Platform environment

The original environment was a ci log of an a3p test.

It reproduces in 4406f5d

Additional context

• odd {x, y, z} >= {z} failure in AmountMath.isGTE with AssetKind.SET Agoric/agoric-sdk#10292

some diagnosis to follow

[dckc]

@frazarshad writes:

the issue is in the elementsIsSuperset function in this file
https://github.com/endojs/endo/blob/master/packages/patterns/src/keys/merge-set-operators.js

In cases where we have a set of invitations with duplicate descriptions, the function fails to mark it as a subset.

we can verify by adding this test to packages/patterns/test/copySet.test.js file of endojs

test('test', t => {
  const r1 = Remotable('Alleged: fooo');
  const r0 = Remotable('Alleged: fooo');
  const r2 = Remotable('Alleged: fooo');

  const mainList = harden([
    {
      instance: r0,
      description: 'fraz',
    },
    {
      instance: r2,
      description: 'fraz',
    },
    {
      instance: r1,
      description: 'alan',
    },
  ]);

  const withdraw = harden([mainList[2]]);

  t.true(elementsIsSuperset(mainList, withdraw));
});

Longer explanation

this code is triggered through the purse's withdraw function when it tries to verify whether the item we are withdrawing is a subset of the items in the purse.

the elementsIsSuperset function here uses mergeify function that is responsible for creating an iterator. Each returned item in the iterator is an element of the original two arrays along with flags that represent if the element was present in the left or right array or both.
so something like this:

[
    [elem1, 1n, 0n],
    [elem2, 0n, 1n],
    ...
]

in case the elements are invitations, which is a list of object with strings and remotables, it compares them by assigning tag numbers to the remotables.
This tagging is done at the time of comparison so any remotable that is compared (or seen) later has a larger tag number.
This code works as expected if all remotables are untagged before the comparison starts

The problem arises when we pass invitations having the same description.
During the initial parts of mergeify when the two arrays are being converted into iterables using windowResort , this line runs to check if there are any duplicates in the array:

while (j < length && rankCompare(value, elements[j]) === 0) {

rankCompare here is being used to compare two elements of the purse to check for duplicates. the problem is that rankCompare cant tell apart remotable objects, so all remotables are considered equal for it.
therefore if two invitations with the same description are present such as:

{
  instance: Object [Alleged: InstanceHandle] {},
  installation: Object [Alleged: BundleIDInstallation] {},
  handle: Object [Alleged: InvitationHandle] {},
  description: 'oracle invitation'
} 
{
  instance: Object [Alleged: InstanceHandle] {},
  installation: Object [Alleged: BundleIDInstallation] {},
  handle: Object [Alleged: InvitationHandle] {},
  description: 'oracle invitation'
}

It will consider them equal, thus it will move to this line

const resorted = sortByRank(similarRun, fullCompare);

which performs a fullCompare , by running a full compare, we esentially start tagging the remotables of the similar named invitations thereby polluting the state that we require for the rest of mergeify to work properly

[dckc]

@gibson042 writes:

this is amazing! I'll see what I can do about a fix in endo

I'm inclined to assign this to him on that basis, but I'm not quite sure that I should. @gibson042 please assign yourself, unless there's some reason not to.

cc @aj-agoric