Subject: [Lager] Final evaluation of eligibility for a label with reflexive variant mapping

From: Audric Schiltknecht <[email-masked]>
Date: Wed, 16 Sep 2015 11:42:22 -0400

Hi,

Last paragraph of 7.1 says:

   For LGRs that contain reflexive variant mappings (defined in
   Section 4.3.4), the final evaluation of eligibility for the label
   must be deferred until variants are generated.  In essence, LGRs that
   use this feature treat the original label as the (identity) variant
   of itself.  For such LGRs, the ordinary iteration over code points
   would generally only exclude a subset of invalid labels, but it could
   be used effectively as a pre-screening.

I've had a hard time understanding this bit (and even now, I'm not sure
I got this right). My current understanding of the text is that we can't
for sure determine the eligibility of an label for an LGR with reflexive
mapping directly: we have to generate all variants for the label, and
ensure none of the variants with the same code point sequence as the
original label has an disposition of "invalid". If so, the label is not
eligible, and cannot have variant per 7.2, step 6.

Can we add some kind of example to illustrate this case?

This also has some impacts on implementation. Since eligibility cannot
be determined directly, one has to generate _all_ variants of a label to
ensure it is actually valid, before the list of variants can be
returned. In some cases, this can easily lead to high memory and CPU
consumption which might be worth a mention in the text.

What do you think about that?

Audric

---

From: Asmus Freytag <[email-masked]>
Date: Wed, 16 Sep 2015 10:24:12 -0700

On 9/16/2015 8:42 AM, Audric Schiltknecht wrote:
> mapping directly:
Correct
> we have to generate all variants for the label, and
> original label has an disposition of "invalid".
Correct, but I think we don't actually need _all_ variants.
>   If so, the label is not
Correct.
> Can we add some kind of example to illustrate this case?

Probably a good idea.
> consumption which might be worth a mention in the text.

In the general case, it's prohibitive to generate _all_ variants. It's 
not necessary for
conflict checking and I believe it's not necessary to handle the issue 
that is raised in
7.1.

First observation is that the variant mappings form disjoint sets. (Any 
two sets that aren't
disjoint, would be replaced by their union as part of enforcing 
transitivity).

Second observation is that this carries through from the code points to 
the set of
variant labels. They equally fall into disjoint sets based on which 
mappings were used.

Now, in both cases, instead of doing all permutations, it's sufficient 
to substitute an
"index" case, in effect identifying the set of variant code points. You 
could take, for
example, the first code point (or sequence) in some sorting order as the 
"index" for
the set of variant mappings.

Then you generate a single variant label from the original, which uses 
the "index"
value for each set as the target for mapping from any code point from 
the set that is
in the label.

That gets you an "index label". You do that with any of the labels you 
want to check
for collision, and if two of the index labels are the same, then you 
have a collision.

Now, for the validity check, you just need to run the label and apply 
any reflexive
mappings. Since source and target are the same for a reflexive mapping, 
there is
only ever one (if any) reflexive mapping per code point. This would 
generate a label
that we can call "reflexive-original" label. It has the same code 
points, but doing the mapping
accumulates all the "type" values from any reflexive mappings present on 
the original
code points.

If those types result in a disposition of invalid, you can stop.

Again, while this requires looking at variants, you only need to 
generate one label.

Similar optimizations are possible for determining all "allocatable" 
variants.
In a typical LGR there are more "blocked" variants than "allocatable" 
ones. In fact,
some sets of variant code points only have mappings of type "blocked". 
If there is an
action of the type <action any-variant="blocked" disp="blocked" /> then 
there is
no need to permute over that set, because any label from that 
permutation would
be blocked.

Which of these optimization techniques deserve to be in the specification?

I think, the "reflexive-original" case is the most compelling, because 
as written,
the spec implies unnecessary work.

The optimization for collision checking could be described, but I would 
like to
hear whether people think it's valuable. (I've seen hypothetical LGRs 
with large
numbers of blocked variants per code point, and no allocatable ones, where
doing a permutation for very simple labels runs into space/time 
limitations).

Any other optimizations are probably best left to the implementer or for 
external
documents such as 
https://community.icann.org/download/attachments/43989034/Variant%20Rules.pdf
or https://community.icann.org/download/attachments/43989034/WLE-Rules.pdf

What do people think?

A./

---

From: Audric Schiltknecht <[email-masked]>
Date: Fri, 18 Sep 2015 20:05:34 -0400

Hi,

Thanks for your detailed answer.

> Correct, but I think we don't actually need _all_ variants.

True, we only need to generate reflexive mappings.

> In the general case, it's prohibitive to generate _all_ variants. It's not necessary for
> conflict checking and I believe it's not necessary to handle the issue that is raised in
> 7.1.

I'll skip comments related to conflict checking and just focus on label eligibility here.

> Now, for the validity check, you just need to run the label and apply any reflexive
> mappings. Since source and target are the same for a reflexive mapping, there is
> only ever one (if any) reflexive mapping per code point. This would generate a label
> that we can call "reflexive-original" label. It has the same code points, but doing the mapping
> accumulates all the "type" values from any reflexive mappings present on the original
> code points.

While I agree on the general idea, there are some corner cases which lead to multiplication of
"reflexive-original" labels when using code point sequences.

For example:

<char cp="0061">
  <var cp="0061" type="type-1"/>
</char>
<char cp="0062"/>
<char cp="0061 0062">
  <var cp="0061 0062" type="type-2"/>
</char>

Given the original label 0061 0062, it will generate the disposition set of {type-1, type-2},
instead of two dispositions set {type-1}, {type-2}. This can then change the final disposition if
actions with "all-variants" or "only-variants" attributes.

> Again, while this requires looking at variants, you only need to generate one label.

In the previous case, it seems you need to generate the two labels to correctly apply the actions.

> 
> Similar optimizations are possible for determining all "allocatable" variants.
> In a typical LGR there are more "blocked" variants than "allocatable" ones. In fact,
> some sets of variant code points only have mappings of type "blocked". If there is an
> action of the type <action any-variant="blocked" disp="blocked" /> then there is
> no need to permute over that set, because any label from that permutation would
> be blocked.
> 
> I think, the "reflexive-original" case is the most compelling, because as written,
> The optimization for collision checking could be described, but I would like to
> hear whether people think it's valuable. (I've seen hypothetical LGRs with large
> doing a permutation for very simple labels runs into space/time limitations).
> 
> Any other optimizations are probably best left to the implementer or for external
> documents such as https://community.icann.org/download/attachments/43989034/Variant%20Rules.pdf

Agreed, but I think we need some text in the Security Considerations section to warn users or
implementers that there is the possibility to exhaust resources on the machine running the LGR
processor, potentially causing a DoS on the server.

Audric

---

From: Asmus Freytag <[email-masked]>
Date: Fri, 18 Sep 2015 22:56:54 -0700

> In the previous case, it seems you need to generate the two labels to correctly apply the actions.

I agree that in the case of {a} {b} as well as {ab} defined as <char> 
elements, you get two partitions of the label "ab"

{a}{b} and {ab}

variants need to be generated for both partitions.

If there's no variant defined for {b} then your example would assign a 
non-empty variant type list as follows

"aa" -> type-1, type-2
"aa" -> type-1
"ab" -> type-1,(none)
"ba" -> type-1,(none)
"bb" -> (none)

(these lists have no duplicate elements and order doesn't matter)

You could make "type-1" result in an invalid variant:

<action disp="invalid" any-variant="type-1" />
and filter out mixed labels like "ab" and "ba" (as well as the duplicate 
"aa"), while you could separately dispose of the surviving "aa" and the 
"bb".

An edge case, but I think one we may need to mention when we discuss 
sequences as source or target for variants.

I tried writing a rule that would prohibit such corner cases and that 
became quite intractable, I found. I've previously come up with cases 
where non-reflexive variants can usefully exhibit this behavior of 
partitioning the label in multiple ways, so there is a subset of these 
cases where there's no duplication of permuted label and where the 
variant relations model a reasonable variant relation in an existing 
writing system. That's reason enough for me to not try to limit the 
schema, but perhaps to point out that implementers need to cover it and 
users should think carefully when using overlapping n:m and 1:1 mappings

> processor, potentially causing a DoS on the server.

Good point.

A./

---

From: Wil Tan <[email-masked]>
Date: Sun, 20 Sep 2015 07:29:40 +1000

> (these lists have no duplicate elements and order doesn't matter)

I'm confused by this. In Audric's example, there are only reflexive
variants; 0062 is not a variant of 0061 and vice versa.

So, I would think that the variant labels generated would be:

"ab" -> type-1,(none)
"ab" -> type-2

Am I missing something?

.wil

> became quite intractable, I found. I've previously come up with cases where
> non-reflexive variants can usefully exhibit this behavior of partitioning
> the label in multiple ways, so there is a subset of these cases where
> there's no duplication of permuted label and where the variant relations
> model a reasonable variant relation in an existing writing system. That's
> reason enough for me to not try to limit the schema, but perhaps to point
> out that implementers need to cover it and users should think carefully
> when using overlapping n:m and 1:1 mappings
>
>
>
>>> or
>>> https://community.icann.org/download/attachments/43989034/WLE-Rules.pdf
>>>
>>
> _______________________________________________
> Lager mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lager
>

---

From: Asmus Freytag <[email-masked]>
Date: Sat, 19 Sep 2015 15:36:12 -0700

On 9/19/2015 2:29 PM, Wil Tan wrote:
>
>
> On Sat, Sep 19, 2015 at 3:56 PM, Asmus Freytag <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>         ...
>     I agree that in the case of {a} {b} as well as {ab} defined as
>     <char> elements, you get two partitions of the label "ab"
>
>     {a}{b} and {ab}
>
>     If there's no variant defined for {b} then your example would
>     assign a non-empty variant type list as follows
>
>     "aa" -> type-1, type-2
>     "aa" -> type-1
>     "ab" -> type-1,(none)
>     "ba" -> type-1,(none)
>     "bb" -> (none)
>

Yeah, I had worked on a different example and when I translated it back 
to his, I got turned around.
> So, I would think that the variant labels generated would be:
Let's add the missing ones for a complete set

  "aa" -> type-1
"ba" -> type-1,(none)
"bb" -> (none)
> Am I missing something?

No, you didn't miss anything.

The main point applies, which is that we have
two labels "ab" with (potentially!) different dispositions.

Here is the suggested draft text for the specification:

Added a paragraph in section 4.3.1 Basic Variants.

    The source and target of a variant mapping may both be sequences,
    but not ranges.

    If the source of one mapping is a prefix sequence of the source for
    another, both variant mappings will be considered at the same
    location in the input label when generating permuted variant labels.
    If poorly designed, an LGR containing such an instance of a prefix
    relation a could generate multiple instances of the same variant
    label for the same original label, but with potentially different
    dispositions (see Section 7.4
    <cid:[email-masked]>).

Last paragraph of section 7.1 Determining Eligibility for a Label:

    To check the validity of a label with reflexive mappings, it is not
    necessary to generate all variant labels. Only a single variant
    needs to be created, where for each code point, any reflexive
    variants are applied, and the label disposition is evaluated. A
    disposition of "invalid" results in the label being not eligible.
    (In the exceptional case where context rules are present on
    reflexive mappings, multiple reflexive variants may be defined, but
    for each original label, at most one of these can be valid at each
    code position. However, see Section 7.4
    <cid:[email-masked]>).

A new section:

      7.4. <cid:[email-masked]> Duplicate
      Variants <cid:[email-masked]>

    For a poorly designed LGR, it is possible to generate duplicate
    variant labels from the same input label, but with different, and
    potentially conflicting dispositions. It is RECOMMENDED that
    implementations flag this as an error.

    The following shows an example of conflicting reflexive variants:

       <char cp="0061">
         <var cp="0061" type="allocatable"/>
       </char>
       <char cp="0062"/>
       <char cp="0061 0062">
         <var cp="0061 0062" type="blocked"/>
       </char>

    A label "ab" would generate the variant labels "{a}{b}" and "{ab}"
    where the curly braces show the sequence boundaries as they were
    applied during variant mapping. The result is a duplicate variant
    label "ab", one based on a variant of type "allocatable" plus an
    original code point "b" that has no variant, and another one based
    on a single variant of type "blocked". If the intention was to use
    the sequence to block the label "ab", the other, duplicate variant
    label would contradict that. As a result, it is RECOMMENDED that
    implementations treat as errors all cases where duplicate variant
    labels are generated with more than one of them receiving a final
    disposition other than invalid.

This occurrence of duplicate variant labels is easily detected at 
"runtime", but might be challenging to discover earlier. I couldn't come 
up with a clean prescription that would have prevented their occurrence 
without really complicating the rules (and potentially limiting valid 
scenarios). But at runtime, if I see two identical labels resulting once 
in "blocked" and once in "allocatable", I clearly have a contradiction 
that I can flag. A clever implementer may find a way to predict that 
from the LGR, but I think we should not require that.

Further, I can imagine valid scenarios (perhaps in conjunction with 
context rules) where, If the type of "a" -> "a" had been "invalid" the 
desired effect might have been to allow label "ab" while preventing 
certain original labels where "a" isn't followed by "b". That's the 
motivation for treating duplicate dispositions as an error only when 
more than one of them are something other than "invalid".

In case that duplicate variant labels have the same disposition, they 
can be folded together. Do we need to spell that out?

A./

---

From: Wil Tan <[email-masked]>
Date: Mon, 21 Sep 2015 01:55:42 +1000

On Sun, Sep 20, 2015 at 8:36 AM, Asmus Freytag <[email-masked]> wrote:

> Yeah, I had worked on a different example and when I translated it back to
> his, I got turned around.
>
>

I get it now, these are not the resulting labels from a single input label
of "ab". Rather, they are the set of all possible 2-character variant
labels that are valid under this LGR.

> The source and target of a variant mapping may both be sequences, but not
> ranges.
>
> another, both variant mappings will be considered at the same location in
> the input label when generating permuted variant labels. If poorly
> designed, an LGR containing such an instance of a prefix relation a could
> generate multiple instances of the same variant label for the same original
> label, but with potentially different dispositions (see Section 7.4).
>
>
>
I wonder if it would also make sense to also point the following scenario
at the new Section 7.4:

4.3.5 <https://tools.ietf.org/html/draft-ietf-lager-specification-02#section-4.3.5>.
Conditional Variants

Care must be taken to ensure that for each variant label at
   most one of the contextual conditions is met for variants with the
   same mapping; otherwise the results are undefined.

> necessary to generate all variant labels. Only a single variant needs to be
> created, where for each code point, any reflexive variants are applied, and
> the label disposition is evaluated. A disposition of "invalid" results in
> the label being not eligible. (In the exceptional case where context rules
> are present on reflexive mappings, multiple reflexive variants may be
> defined, but for each original label, at most one of these can be valid at
> each code position. However, see Section 7.4).
>
> A new section:
>
> 7.4. Duplicate Variants
>
> For a poorly designed LGR, it is possible to generate duplicate variant
> labels from the same input label, but with different, and potentially
> conflicting dispositions. It is RECOMMENDED that implementations flag this
> as an error.
>
>
There is another more specific "RECOMMENDED" sentence in the paragraph
below. Perhaps this one can be deleted.

> A label "ab" would generate the variant labels "{a}{b}" and "{ab}" where
> the curly braces show the sequence boundaries as they were applied during
> variant mapping. The result is a duplicate variant label "ab", one based on
> a variant of type "allocatable" plus an original code point "b" that has no
> variant, and another one based on a single variant of type "blocked". If
> the intention was to use the sequence to block the label "ab", the other,
> duplicate variant label would contradict that. As a result, it is
> RECOMMENDED that implementations treat as errors all cases where duplicate
> variant labels are generated with more than one of them receiving a final
> "runtime", but might be challenging to discover earlier. I couldn't come up
> with a clean prescription that would have prevented their occurrence
> scenarios). But at runtime, if I see two identical labels resulting once in
> "blocked" and once in "allocatable", I clearly have a contradiction that I
> can flag. A clever implementer may find a way to predict that from the LGR,
> but I think we should not require that.
>
> desired effect might have been to allow label "ab" while preventing certain
> original labels where "a" isn't followed by "b". That's the motivation for
> treating duplicate dispositions as an error only when more than one of them
> are something other than "invalid".
>

> In case that duplicate variant labels have the same disposition, they can
> be folded together. Do we need to spell that out?
>
>
Sure, an LGR author may have a use case that necessitates duplicate variant
labels, and could write the rules to address the use case. However, I'm not
sure if there is a real need for it.

Duplicate variant labels feels like a glitch to me, and I would have
preferred to say that the results are undefined. On the other hand,
implementations need to be prepared to deal with such cases, and some
guidance may be useful.

To me, implementations should probably go as far as to warn (or make it an
error in "strict mode") whenever duplicate variant labels are generated
(regardless of dispositions.)

.wil

---

From: Asmus Freytag <[email-masked]>
Date: Sun, 20 Sep 2015 10:49:11 -0700

On 9/20/2015 8:55 AM, Wil Tan wrote:
>
>
> On Sun, Sep 20, 2015 at 8:36 AM, Asmus Freytag <[email-masked] 
>>         The source and target of a variant mapping may both be
>>         sequences, but not ranges.
>>
>>         If the source of one mapping is a prefix sequence of the
>>         source for another, both variant mappings will be considered
>>         at the same location in the input label when generating
>>         permuted variant labels. If poorly designed, an LGR
>>         containing such an instance of a prefix relation a could
>>         generate multiple instances of the same variant label for the
>>         same original label, but with potentially different
>>         dispositions (see Section 7.4).
>>
>>
>
> I wonder if it would also make sense to also point the following 
> scenario at the new Section 7.4:
>
>
>         4.3.5
>         <https://tools.ietf.org/html/draft-ietf-lager-specification-02#section-4.3.5>.
>         Conditional Variants
>

Good point. Deserves a "(See also Section 7.4)."

This is also a case of duplicate variants, with potentially conflicting 
dispositions.

Unlike the prefix case, you cannot construct a scenario where such 
conflict makes a legitimate difference. In essence, the case of 
overlapping context is (for some set of input labels) entirely 
equivalent of having attempted to create two variant mappings with the 
same context or simply, two variants with the same mapping and different 
type, both of which would be forbidden. The only reason we do not flag 
this on parsing is because we can't - context rules can look very 
different, yet be triggered by the same context.

The case of the prefix is different, in that here the mappings are 
rigorously distinct, but the resulting labels are not.

However, perhaps your sense that any form of duplicate variant labels is 
a "glitch" is a good guide here. Both scenarios result in duplicate 
variant labels at runtime.

The one corner case of allowing the "invalid" duplicate seems still 
needed, because of the way context rules and WLE rules interact. If all 
duplicates are taken care of by WLEs, I'd say that's fair game. It also 
keeps the meaning of "invalid', which is that the affected label is 
removed from further processing. It may be simpler to have the context 
rules "overproduce" variants that are then culled by WLE, such tradeoff 
between context rules and WLE definitely exists for conditions on code 
points. Depending on how you split the task there, the statement of the 
various rules could be simpler or more complicated, for the same effect.

So, I suggest we make these changes:

1) a duplicate variant label, no matter how caused, MUST result in an 
ERROR at runtime
2) duplicate variant labels with disposition of "invalid" are ignored 
(in (1)).  (-- still thinking about this one--)
3) section 7.4 gets broadened to apply to other than common prefix cases
4) section 4.3.5 gets revised and to point to 7.4

A./

>         To check the validity of a label with reflexive mappings, it
>         is not necessary to generate all variant labels. Only a single
>         variant needs to be created, where for each code point, any
>         reflexive variants are applied, and the label disposition is
>         evaluated. A disposition of "invalid" results in the label
>         being not eligible. (In the exceptional case where context
>         rules are present on reflexive mappings, multiple reflexive
>         variants may be defined, but for each original label, at most
>         one of these can be valid at each code position. However, see
>         Section 7.4).
>
>     A new section:
>
>
>           7.4. Duplicate Variants
>
>         For a poorly designed LGR, it is possible to generate
>         duplicate variant labels from the same input label, but with
>         different, and potentially conflicting dispositions. It is
>         RECOMMENDED that implementations flag this as an error.
>
>
>         A label "ab" would generate the variant labels "{a}{b}" and
>         "{ab}" where the curly braces show the sequence boundaries as
>         they were applied during variant mapping. The result is a
>         duplicate variant label "ab", one based on a variant of type
>         "allocatable" plus an original code point "b" that has no
>         variant, and another one based on a single variant of type
>         "blocked". If the intention was to use the sequence to block
>         the label "ab", the other, duplicate variant label would
>         contradict that. As a result, it is RECOMMENDED that
>         implementations treat as errors all cases where duplicate
>         variant labels are generated with more than one of them
>         receiving a final disposition other than invalid.
>
>
>     "runtime", but might be challenging to discover earlier. I
>     couldn't come up with a clean prescription that would have
>     prevented their occurrence without really complicating the rules
>     (and potentially limiting valid scenarios). But at runtime, if I
>     see two identical labels resulting once in "blocked" and once in
>     "allocatable", I clearly have a contradiction that I can flag. A
>     clever implementer may find a way to predict that from the LGR,
>     Further, I can imagine valid scenarios (perhaps in conjunction
>     with context rules) where, If the type of "a" -> "a" had been
>     "invalid" the desired effect might have been to allow label "ab"
>     while preventing certain original labels where "a" isn't followed
>     by "b". That's the motivation for treating duplicate dispositions
>     as an error only when more than one of them are something other
>     than "invalid".
>
>
>     In case that duplicate variant labels have the same disposition,
>     they can be folded together. Do we need to spell that out?
>
>
> Sure, an LGR author may have a use case that necessitates duplicate 
> variant labels, and could write the rules to address the use case. 
> However, I'm not sure if there is a real need for it.
>
> To me, implementations should probably go as far as to warn (or make 
> it an error in "strict mode") whenever duplicate variant labels are 
> generated (regardless of dispositions.)
>
>
> .wil