Subject: [Lager] [lager] #20 (specification): Final evaluation of eligibility for a label with reflexive variant mapping

From: "lager issue tracker" <[email-masked]>
Date: Wed, 16 Sep 2015 17:34:23 -0000

#20: Final evaluation of eligibility for a label with reflexive variant mapping

 On 9/16/2015 8:42 AM, Audric Schiltknecht wrote:
 > 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:
 Correct
 > 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".
 Correct, but I think we don't actually need _all_ variants.
 >   If so, the label is not
 > eligible, and cannot have variant per 7.2, step 6.
 Correct.
 >
 > Can we add some kind of example to illustrate this case?

 Probably a good idea.
 >
 > 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.

 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, forexample, 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 originalcode 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.

-- 
-------------------------+-------------------------------------------------
 Reporter:               |      Owner:  draft-ietf-lager-
  [email-masked]   |  [email-masked]
     Type:  enhancement  |     Status:  new
 Priority:  major        |  Milestone:
Component:               |    Version:
  specification          |   Keywords:
 Severity:  -            |
-------------------------+-------------------------------------------------

Ticket URL: <http://trac.tools.ietf.org/wg/lager/trac/ticket/20>
lager <http://tools.ietf.org/lager/>

---

From: "lager issue tracker" <[email-masked]>
Date: Mon, 21 Sep 2015 18:28:09 -0000

Changes (by [email-masked]):

 * status:  new => closed
 * resolution:   => fixed

-- 
-------------------------+-------------------------------------------------
 Reporter:               |       Owner:  draft-ietf-lager-
  [email-masked]   |  [email-masked]
     Type:  enhancement  |      Status:  closed
 Priority:  major        |   Milestone:
Component:               |     Version:
  specification          |  Resolution:  fixed
 Severity:  -            |
 Keywords:               |
-------------------------+-------------------------------------------------

Ticket URL: <http://trac.tools.ietf.org/wg/lager/trac/ticket/20#comment:1>
lager <http://tools.ietf.org/lager/>