Want Patterns Implementation Plan

[katelynsills]

User Stories

• Find invitation in wallet for offer: As a user, I can find an invitation in my wallet to use for an offer, without having to know the details (such as the invitation handle) for that particular invitation. Just knowing the instance and description should be enough to choose an invitation to use.
• Find all possible invitations in wallet for offer: As a user, I can find all matching invitations that could potentially be used for an offer, without having to know the details (such as the invitation handle) for that particular invitation. Just being able to know the instance should be enough to get a number of invitations to choose from.
• Buy a ticket for an event with offer safety: As a user, I want to be able to buy a ticket to an event and have it be protected by offer safety. I do not want to have to specify things that are not important to me, like a seat number.
• Buy an option with an expirationDate greater than or equal to some timestamp: As a user, I want to buy an option and have my purchase be protected by offer safety. I want to be able to specify things that are important to me, such as that the option will not expire until after a specific timestamp. I don't want to have to specify things that are not important to me, such as the invitation handle for a particular option. (This use case also pertains to staking derivatives.)
• Withdraw an invitation from a purse, even if it is not deposited in the purse yet: As a user, I would like to attempt to withdraw an invitation from a purse even if it has not been deposited yet, and receive a promise that will be resolved to a payment when the withdrawal occurs. This will allow me to set up and approve offers even if I do not yet have the invitation in hand to use. I would like to be able to eventually withdraw without knowing the details of the invitation, such as the invitation handle.
• Dominant Assurance Contract: As a user, I want to specify that either the public good is produced, OR I get money back plus the extra amount I get for participating (note that this is different than what I gave).

Expected Behavior

There will be (at least) three additions to amountMath methods (actual names TBD):

• matchMin(amount, pattern): get the minimal match that satisfies or return undefined
  • aka frugal
• matchMax(amount, pattern) : get the maximal match that satisfies or return undefined.
  • aka anti-frugal
• getPatternMaker: return an object for making patterns
  • make: make a pattern, like amountMath.make
  • any: return a pattern record meaning any, likely { '@pattern': '*' }
  • and: conjunction
  • or: disjunction
  • specifySome: provide some keys and values but don’t care about the others
  • regexp: take a regexp
  • lte: less than or equal to
  • gte: greater than or equal to

MathKind.NAT

matchFirst

Return the second argument if the first is greater than the second, otherwise return undefined.

[Insert code examples here]

matchAll

Return the first argument if the first is greater than the second, otherwise return undefined.

[Insert code examples here]

MathKind.STRING_SET

matchFirst

Return an amount with a value of the first string that matches. Otherwise return undefined. Should be the match that is alphabetically first of all matches. We'd like to specify something that gives us an order-independent deterministic answer (which mine [Mark] does not) and we're not sure that alphabetic (or lexicographic) is the best choice. But cannot think of anything better or less surprising. If the amountPattern has more than one element in the value array, the elements after the first are only used if the first was unsuccessful at finding a match.

amountMath.matchFirst(
  { brand, value: [‘abc’, ‘ab’, ‘b’]}, 
  amountMath.makePattern(
    patternOr(
      [stringPrefix('ab')],
      [stringPrefix('b')]
))) => { brand, value: [‘ab’] }

matchAll

Return an amount with a value of all strings that match. Otherwise return undefined.

[Insert code examples here]

MathKind.SET (and MathKind.INVITATION, if it exists)

matchFirst

Find the first amount that matches, i.e. the amount for one invitation, if any. The amount for one ticket, if any. Return undefined otherwise. If the amountPattern has more than one element in the value array, the elements after the first are only used if the first was unsuccessful at finding a match

[Insert code examples here]

matchAll

Find all the invitations that match. Find all the tickets that match. Deduplicate any matches that are found by different elements of the amount pattern. Return undefined otherwise.

[Insert code examples here]

Implementation Plan

• Agree on use cases
• Agree on expected behavior
• Write test cases for expected behavior, at the amountMath level and at the higher levels (Zoe, wallet, eventualWithdraw, etc). (Amount Patterns: Write test cases for the use cases and for each mathKind and mark as test.failing #2355)
• Clean up mathHelpers
  • Keep strings in StrSetMathHelpers ordered at all times for determinism
    https://github.com/Agoric/agoric-sdk/blob/fungible-derivs/packages/ERTP/src/mathHelpers/strSetMathHelpers.js
  • Create a separate, more efficient mathHelpers for Zoe invitations
    SetMathHelpers is incredibly ill-designed for Zoe invitations currently, as it creates buckets based on keys that are strings concatenated with values that are strings. Since most keys are the same for all invitations, and most values are not strings, this means that the buckets are nearly entirely determined by the invitation description. It’s efficient if the invitation descriptions are all different, but if they are the same and few string customProperties are used, we would expect to see a lot of comparisons made because all the invitations are in the same bucket.
• Create a PR for the patterns only, in sameStructure
• Create a PR for the mathHelpers implementations and amountMath methods only
• Create a PR for flexible wants in Zoe Proposals
  • Note that we cannot enforce offer safety that is intended to matchAll over all the contract has control over, since offer safety is a comparison between an allocation and what is wanted, not what the contract had available and what was wanted.
  • For this reason, only matchFirst makes sense to use within offerSafety.js (or amountMath.satisfies, however we come down on this).
• Create a PR for efficiently finding a single invitation in the wallet using amountMath.matchFirst
• Create a PR for efficiently finding all matching invitations in the wallet using amountMath.matchAll
• Create a PR for allowing offers in the wallet to eventuallyWithdraw an invitation that matches some amount pattern
  • Two steps:
    • Withdraw a pattern rather than withdraw a concrete amount
    • Having an eventualWithdraw method.
• Several other cases I (Mark) could imagine generalizing this way, like splitting a payment, or the second argument to deposit that the incoming payment must match. All these seem reasonable. Many can happen incrementally after we take the first steps.

Relevant PRs

• Amount Patterns in Zoe Proposals (Mark): Have proposal wants be amount patterns rather than just amounts #1905
• AmountMath.find (Kate): feat: add amountMath.find #2155
• Flexible Wants in Zoe Proposals (Kate): feat: allow flexible wants in Zoe #2156
• EventualWithdraw from ERTP purses (Kate): feat: add eventualWithdraw to ERTP #2157
• Generalized Patterns (Mark): DO NOT MERGE Failed experiment: Generalized patterns #2211

cc @erights

[erights]

Hi @katelynsills I took the liberty of editing the whitespace of your code example in place above.