Subject: [Cbor] draft-ietf-cbor-cddl-05 and maps

From: Kevin Braun <[email-masked]>
Date: Wed, 29 Aug 2018 14:02:52 -0400

Hi folks,

I've looked at draft-ietf-cbor-cddl-05 and read some of the discussion 
on this list regarding maps, which appear to have been made relative to 
draft-ietf-cbor-cddl-04.

It is not entirely clear to me how map validation is supposed to work.  
As this has been an area of some recent discussion already, perhaps this 
mail is superfluous, but in case it is not, I'll try to explain what I 
don't find clear...

The discussion of "pathological non-determinism" is a little confusing.  
Is the problem with the example one of specification or implementation - 
i.e. is the validity of {3: 5, 4: 6} against do-not-do-this 
undecided/undefined, or it is merely difficult for tools to decide 
this?  It seems to me {3: 5, 4: 6} is certainly valid against 
do-not-do-this, so I think the issue is really about implementation 
difficulty.

    do-not-do-this = {
      int => int,
      int => 6,
    }

The text says, "This pathological non-determinism is caused by 
specifying more general before more specific....", so I take it the 
following would NOT be considered pathological:

    do-this = {
      int => 6,
      int => int,
    }

Okay, so why is one pathological and not the other?  I guess because the 
PEG algorithm requires us to match the first entry first, though this 
isn't stated anywhere that I see.  But, even with such a rule, if it is 
a rule, I think do-this and do-not-do-this would validate the exact same 
set of maps, which seems to make sense given what Appendix C says about 
ordering:  a map expression "matches a valid CBOR map the key/value 
pairs of which can be ordered in such a way that the resulting sequence 
matches the group expression".  So, it appears that, at with respect to 
do-this and do-not-do-this, PEG is not actually relevant to specifying 
map validity but only to ensuring that an algorithm can more easily 
determine map validity.

Also, I had to ask myself, "Wait, what exactly is non-deterministic 
here?".  I considered that you might be thinking of ambiguity in the 
attribution of input key-value pairs to the group entries, but I believe 
you had the algorithm in mind.  Attribution would be ambiguous for both 
do-not-do-this and do-this for the input { 4: 6, 5: 6 }, and there is no 
ambiguity of attribution for either case for the input { 4: 6, 5: 7 }.

I think PEG does become relevant to the definition of map validity when 
there are occurrence indicators on the entries.  However, I don't see 
anything saying that occurrence indicators have greedy behavior as in 
PEG.  From the discussion of labeled-values in 3.5.3, I am guessing that 
if we write:

bad-labeled-values = {
      * label => value
      fritz: number,
    }

then we've created a map expression that can't validate any maps, as the 
first entry will consume any entry that could satisfy the second entry.  
That, however, assumes some rule that I'm not quite sure how to state 
precisely.  It seems to depend on a model of execution that involves 
pulling key-value pairs out of the map to satisfy the group entries, a 
rule that occurrence indicators have greedy behavior (they require 
pulling out of the map everything that can be matched), and a rule that 
the pulling of entries from the map must be done for the group entries 
according to the order in which they are given in the map expression.  
That suggests we need an algorithmic definition of map validity, which 
is in contrast to the description in Appendix C.  It seems that if 
bad-labeled-values ought to validate no maps, the key to that is that 
occurrence indicators be understood to be greedy.  However, saying 
occurrence indicators are greedy in the context of map validation lacks 
meaning (since the input is not ordered), unless you say that in the 
context of an algorithmic description that imposes some order on how 
things must be done, in which case "greedy" can mean pulling out all 
possible matches for the "current" group entry, up to the maximum 
allowed by the occurrences indicator.

So, having said all of that, I think where I've ended up is 
that, assuming I've understood the spec's intentions, you really need an 
algorithmic definition of map validity in order to have a model that PEG 
principles can be applied to (e.g. greedy occurrences); the description 
in appendix C just doesn't seem to accomplish that.

I hope you find these comments helpful.

Regards,
Kevin