[FEEDBACK] Simpler formulation of Pattern Selection

[macchiati]

I think the algorithm for variant selection is much too complicated. That is, I think we can structure it in a way that gets the same results, but is not as complicated to explain — and matches a simpler and more efficient implementation that (a) doesn’t involve sorting, (b) is single-pass, and (c) has a fast exit.

This was sparked by the discussion around "resolved value" being needed in pattern selection. The 'dot' notation is used for convenience here, but needn't be in the fleshed-out text.

---

Restructure the BNF to be add a couple of useful terms.

• Define a selector-list = 1*(s selector) and so we'd have match-statement = match selector-list
• Define a key-list = key *(s key) and so we'd have variant = key-list quoted-pattern

The Pattern Selection process depends on two capabilities of selectors:

• selector.match(key) returns a value in {fail, ok, best}
• selector.compare(key1, key2) returns a value in {worse, same, better}

Using these, list versions are defined in a natural way (see below for details):

• selector-list.match(key-list)
• selector-list.compare(key-list1, key-list2)

Determining which of a message's patterns is formatted

(where there are selectors)

• Let bestVariant be undefined.
• For each variant in the list:
  • Let match be selector-list.match(variant.key-list)
  • If match \= fail, continue the for-loop
  • Else if match \= best, return the variant
  • Else if setVariant is undefined, let bestVariant be variant
  • Else if the selector-list.compare(variant.key-list, bestVariant.key-list) \= better, then let bestVariant be variant
  • Continue loop
• If the loop terminated, return bestVariant
  • // We are guaranteed to have one, since there is a key-list with all *’s

Determining selector-list.match(key-list)

• Let result be best
• For each selector, key1 in the selector-list, key-list: (ie, taking the i-th element of each list)
  • Let value be selector.match(key)
  • If value \= fail, return fail
  • Else if value is ok, let result be ok
  • Else continue loop

In other words, the result is fail if any selector.match(key) value \= fail, else best if every selector.match(key) value \= best, else ok.

Determining selector-list.compare(key-list1, key-list2)

• For each selector, key1, key2 in the selector-list, key-list1, key-list2: (ie., taking the i-th element of each list)
  • Let result be selector.compare(key1, key2)
  • If result ≠ same, return result
  • Else continue loop
• If the loop terminated, return same.

Discussion

• This algorithm avoids the complications involved in sorting, and allows for a single pass to find the best pattern. As in the sorting algorithm, there may be multiple key-lists that are "as good" as one another, and in that case the first of that group is chosen.
• The use of a 'best' value allows for early termination. Once a key-list is found where every key is 'best' (meaning no other key is better, though other keys could be the same), then the selection process can terminate. If there is no 'best' value (an odd but possible case), the algorithm is still better than the sorting algorithm.

---

CURRENT TEXT

https://github.com/unicode-org/message-format-wg/blob/main/spec/formatting.md#pattern-selection ...

To determine which variant best matches a given set of inputs, each selector is used in turn to order and filter the list of variants.

Each variant with a key that does not match its corresponding selector is omitted from the list of variants. The remaining variants are sorted according to the selector's key-ordering preference. Earlier selectors in the matcher's list of selectors have a higher priority than later ones.

When all of the selectors have been processed, the earliest-sorted variant in the remaining list of variants is selected.

This selection method is defined in more detail below. An implementation MAY use any pattern selection method, as long as its observable behavior matches the results of the method defined here.

Resolve Selectors

First, resolve the values of each selector:

1. Let res be a new empty list of resolved values that support selection.
2. For each selector sel, in source order,
   1. Let rv be the resolved value of sel.
   2. If selection is supported for rv:
      1. Append rv as the last element of the list res.
   3. Else:
      1. Let nomatch be a resolved value for which selection always fails.
      2. Append nomatch as the last element of the list res.
      3. Emit a Bad Selector error.

The form of the resolved values is determined by each implementation, along with the manner of determining their support for selection.

Resolve Preferences

Next, using res, resolve the preferential order for all message keys:

1. Let pref be a new empty list of lists of strings.
2. For each index i in res:
   1. Let keys be a new empty list of strings.
   2. For each variant var of the message:
      1. Let key be the var key at position i.
      2. If key is not the catch-all key '*':
         1. Assert that key is a literal.
         2. Let ks be the resolved value of key in Unicode Normalization Form C.
         3. Append ks as the last element of the list keys.
   3. Let rv be the resolved value at index i of res.
   4. Let matches be the result of calling the method MatchSelectorKeys(rv, keys)
   5. Append matches as the last element of the list pref.

The method MatchSelectorKeys is determined by the implementation. It takes as arguments a resolved selector value rv and a list of string keys keys, and returns a list of string keys in preferential order. The returned list MUST contain only unique elements of the input list keys. The returned list MAY be empty. The most-preferred key is first, with each successive key appearing in order by decreasing preference.

The resolved value of each key MUST be in Unicode Normalization Form C ("NFC"), even if the literal for the key is not.

If calling MatchSelectorKeys encounters any error, a Bad Selector error is emitted and an empty list is returned.

Filter Variants

Then, using the preferential key orders pref, filter the list of variants to the ones that match with some preference:

1. Let vars be a new empty list of variants.
2. For each variant var of the message:
   1. For each index i in pref:
      1. Let key be the var key at position i.
      2. If key is the catch-all key '*':
         1. Continue the inner loop on pref.
      3. Assert that key is a literal.
      4. Let ks be the resolved value of key.
      5. Let matches be the list of strings at index i of pref.
      6. If matches includes ks:
         1. Continue the inner loop on pref.
      7. Else:
         1. Continue the outer loop on message variants.
   2. Append var as the last element of the list vars.

Sort Variants

Finally, sort the list of variants vars and select the pattern:

1. Let sortable be a new empty list of (integer, variant) tuples.
2. For each variant var of vars:
   1. Let tuple be a new tuple (-1, var).
   2. Append tuple as the last element of the list sortable.
3. Let len be the integer count of items in pref.
4. Let i be len - 1.
5. While i >= 0:
   1. Let matches be the list of strings at index i of pref.
   2. Let minpref be the integer count of items in matches.
   3. For each tuple tuple of sortable:
      1. Let matchpref be an integer with the value minpref.
      2. Let key be the tuple variant key at position i.
      3. If key is not the catch-all key '*':
         1. Assert that key is a literal.
         2. Let ks be the resolved value of key.
         3. Let matchpref be the integer position of ks in matches.
      4. Set the tuple integer value as matchpref.
   4. Set sortable to be the result of calling the method SortVariants(sortable).
   5. Set i to be i - 1.
6. Let var be the variant element of the first element of sortable.
7. Select the pattern of var.

SortVariants is a method whose single argument is a list of (integer, variant) tuples. It returns a list of (integer, variant) tuples. Any implementation of SortVariants is acceptable as long as it satisfies the following requirements:

1. Let sortable be an arbitrary list of (integer, variant) tuples.
2. Let sorted be SortVariants(sortable).
3. sorted is the result of sorting sortable using the following comparator:
   1. (i1, v1) <= (i2, v2) if and only if i1 <= i2.
4. The sort is stable (pairs of tuples from sortable that are equal in their first element have the same relative order in sorted).

[eemeli]

Based on a first look and consideration, this formulation of the selection algorithm should give the same results as the current one, but with a few caveats (in no particular order):

1. The inclusion of a best result for selector.match(key) is an unnecessary complication to the spec algorithm. It would be valid for an implementation to provide that optimization, but we don't need to care about early results in the spec text.
2. The * keys need to be handled directly within the selector-list.match(key-list) and selector-list.compare(key-list1, key-list2) methods rather than being passed to the user-defined methods. That's the only way we can guarantee their behaviour, as well as simplifying the inputs to user code to always be only strings.
3. The bit about parsing key values as NFC needs to be retained.
4. We don't need to amend the ABNF to account for these changes. The selector-list and key-list values contain resolved values rather than syntax values, so they'll need to be constructed as a part of the algorithm in any case.

I'd be very happy to review a PR replacing our current text with this, provided that the above concerns are accounted for.

[macchiati]

I don't want to stress the system, given the pending deadlines. I think the important thing is to have a clause that stresses that the current algorithm doesn't have to be followed exactly, the only requirement is that the same results obtain as the current text.

On Thu, Oct 3, 2024, 22:00 Eemeli Aro @.***> wrote:

Based on a first look and consideration, this formulation of the selection algorithm should give the same results as the current one, but with a few caveats (in no particular order):

1. The inclusion of a best result for selector.match(key) is an unnecessary complication to the spec algorithm. It would be valid for an implementation to provide that optimization, but we don't need to care about early results in the spec text.
2. The keys need to be handled directly within the selector-list.match(key-list) and selector-list.compare(key-list1, key-list2)* methods rather than being passed to the user-defined methods. That's the only way we can guarantee their behaviour, as well as simplifying the inputs to user code to always be only strings.
3. The bit about parsing key values as NFC needs to be retained.
4. We don't need to amend the ABNF to account for these changes. The selector-list and key-list values contain resolved values rather than syntax values, so they'll need to be constructed as a part of the algorithm in any case.

I'd be very happy to review a PR replacing our current text with this, provided that the above concerns are accounted for.

— Reply to this email directly, view it on GitHub https://github.com/unicode-org/message-format-wg/issues/898#issuecomment-2392824887, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACJLEMFRN37GBJCBQPMNMSTZZYOFDAVCNFSM6AAAAABPKV5TAWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOJSHAZDIOBYG4 . You are receiving this because you authored the thread.Message ID: @.***>