Subject: [Cbor] Validation of maps

From: Kevin Braun <[email-masked]>
Date: Tue, 18 Jul 2017 14:43:01 -0400

Hi,

I know the question of more formally specifying validation rules already 
came up.  One would think map validation would be fairly obvious, but 
what happens when key types overlap?

For example, I think the intention is that if you have

    top = { 4 => int, *int => tstr }

then the key 4 must be present with an integer value, and you can have 
any number of other integer keys with text string values. Okay, but what 
about:

top = { ? 4 => int, *int => tstr }

We might say this means that if a key of 4 appears, then it must have an 
int value.  Or, does it allow a key of 4 to appear with a text string 
value while considering the optional "4 => int" as being absent?  Given 
the examples in the spec, I guess the intention is for such a thing to 
mean the key 4, if present, has to have an int value.  So, there is some 
kind of "match the most specific key" rule implied (I guess).  How that 
rule applies in more complex situations (where there is some kind of 
nesting) probably needs to be spelled out....  Given:

    top = { 1 => 1, ? ( 5 => 5, 6 => 6 ), *int => tstr }

Must keys 5 & 6 be present together, or does the wildcard allow only one 
of them to appear?  Or, given:

    top = { 1 => 1, ( 5 => 5 // 6 => 6 ), *int => tstr }

does this mean { 1 : 1, 5 : 5, 6 : "hi" }  is not valid?  Is the 6 free 
to match the wildcard when the 5 has satisfied the group choice?

Then there are cases where "most specific key" has no meaning, such as 
when two key types overlap each other and neither is a single-value 
type.  Consider:

    top = { * (0..10) => tstr, * (5..15) => int }

Does this mean a key of 5 can have either a text string or an int 
value?  Or, does it require that a key of 5, if present, must have a 
value that is both a text string and an int at the same time (i.e. it 
disallows 5 to appear)?

Regards,
Kevin

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 18 Jul 2017 23:18:55 +0200

Hi Kevin,

> I know the question of more formally specifying validation rules already came up.  One would think map validation would be fairly obvious, but what happens when key types overlap?
> 
> then the key 4 must be present with an integer value,

Right, that is the only way to match the first field.
(And there is no way to have that as well as another /4/ key with a text string value.)

> and you can have any number of other integer keys with text string values. Okay, but what about:
> 
> We might say this means that if a key of 4 appears, then it must have an int value.  Or, does it allow a key of 4 to appear with a text string value while considering the optional "4 => int" as being absent?  

Yes, that is the semantics.  It is not always what a specifier might intend.

The reason is that the map opens a choice point.  A member with key 4 is starting to match the field.  If the value however does not  match (because there is no int), the matcher falls back to the choice point.  It then tries the other field, and indeed, that matches.

In the research underlying CDDL, we have discussed “cuts” (a concept from error handling in Parse Expression Grammars (PEGs)) as the solution to this.  If ^ represents a cut, write:

top = { ? 4 ^ => int, *int => tstr }

Once the 4 matches, there is no way back; for this member, another match is no longer tried.
A nice side effect is that anything except an int after a key of 4 can give a definite error message of “int expected”.
The cut proposal includes : as an abbreviation for ^=>, so you can simply write:

top = { ? 4: int, *int => tstr }

> Given the examples in the spec, I guess the intention is for such a thing to mean the key 4, if present, has to have an int value.

Which example leads you to this conclusion?

>  So, there is some kind of "match the most specific key" rule implied (I guess).  

Actually, the PEG semantics we have borrowed here is that the *first* match is used.  But only rules are matched that indeed match!

> How that rule applies in more complex situations (where there is some kind of nesting) probably needs to be spelled out....  Given:
> 
> Must keys 5 & 6 be present together,

Yes.

The whole group in the parentheses is optional.

> or does the wildcard allow only one of them to appear?  

(That was an early semantics we tried, and it leads down the drain.
It is much better to have a matcher that simply and stupidly follows what’s in the grammar.)

> Or, given:
> does this mean { 1 : 1, 5 : 5, 6 : "hi" }  is not valid?  

No.  The first field eats the 1: 1, the second field only matches the 5: 5, so the third field gets to eat zero or more int: tstr, of which 6: “hi” is a match.

> Is the 6 free to match the wildcard when the 5 has satisfied the group choice?

Yes.

> 
> Then there are cases where "most specific key" has no meaning,

(Again, we use “first match”.)

> such as when two key types overlap each other and neither is a single-value type.  Consider:
> 
> Does this mean a key of 5 can have either a text string or an int value?  

As long as there are no cuts here, yes.

> Or, does it require that a key of 5, if present, must have a value that is both a text string and an int at the same time (i.e. it disallows 5 to appear)?

That would never be the semantics — the fact that there are two branches in a choice that can be fulfilled is not an error.

With a cut like this:

top = { * (0..10) ^ => tstr, * (5..15) => int }

this could mean that key 0..10 cut the choice and therefore need to have a text string value, while the rest, 11..15 can be integers, because the choice is cut after matching 0..10.

So far, we haven’t seen a use case that actually needed the cut, but it is still nice to have that error message.
(We also haven’t implemented it yet, although we will certainly do that over time.)

Another example where a cut helps:

message = orderbeer / orderwine

orderbeer = {
  type: “beer”,
  ferment: “bottom” / “top”,
}

orderwine = {
  type: “wine”,
  color: “red” / “white”.
}

If you feed {“type”: “wine”, “ferment”: “top”} into this, you get a rather unspecific error message that tells you things don’t match up — the matcher can’t really know whether the “type” value of “wine" or the “ferment” key is the “cause” of neither branch matching.

If you add a cut:

message = orderbeer / orderwine

orderbeer = {
  type: “beer” ^,
  ferment: “bottom” / “top”,
}

orderwine = {
  type: “wine” ^,
  color: “red” / “white”.
}

the matcher can tell you right away that the key “ferment” is not allowed in an orderwine message.

Grüße, Carsten

---

From: Kevin Braun <[email-masked]>
Date: Wed, 19 Jul 2017 11:10:45 -0400

Hi Carsten,

Thanks for the explanations.

So,
matches
     { 4 : "okay" }

That surprises me because of the extensibility example:
     PersonalData = {
         ? displayName: tstr,
         NameComponents,
         ? age: uint,
         * tstr => any
     }

I interpreted the extension to allow other keys (other than 
"displayName", "age", and the keys from NameComponents) to appear, but 
not to allow the existing keys to appear with other value types.  (If 
the example is using cuts by using the colon, I didn't realize it; I 
don't think draft -11 says anything about that).  It seems I had the 
wrong idea of extensibility.  I also had a slightly wrong mental model 
for map validation in that I was thinking in terms of "this says that 
this key must have this type", which isn't quite accurate.  Though, I 
would say the example suggests the reading I gave to it, because after 
all what is the point of having "? displayName : tstr" in there if the 
"displayName" key can actually appear with any type of value at all, due 
to the "* tstr => any"?  (I'm still assuming that displayName: tstr is 
the same as "displayName" => tstr - that I wasn't supposed to read the 
example with cuts in mind and the colon being shorthand for a cut.)

I think I understand better now, except this one thing...  I don't 
understand why
    top = { ? 4 => int, *int => tstr }
matches
     { 4 : "okay" }
but
     top = { 1 => 1, ? ( 5 => 5, 6 => 6 ), *int => tstr }
does not match
     { 1 : 1, 6: "hi" }

6 : "hi" does not (alone or with anything else for that matter) match 
the optional group, but it does match the *int => tstr.  It seems 
inconsistent with how the key of 4 is handled in the first example.  
Perhaps there is some rule here that just hasn't been stated yet.

Regards,
Kevin

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 19 Jul 2017 19:02:36 +0200

> On Jul 19, 2017, at 17:10, Kevin Braun <[email-masked]> wrote:
> 
> Hi Carsten,
> 
> I interpreted the extension to allow other keys (other than "displayName", "age", and the keys from NameComponents) to appear, but not to allow the existing keys to appear with other value types.  

(Actually, that may be a valid extension in some universes, but it may or may *not* be what the spec writer intends here.)

> (If the example is using cuts by using the colon, I didn't realize it; I don't think draft -11 says anything about that).  

Draft -11 does not have cuts.  I’m not yet convinced that we want to put cuts in at this point.
That’s why I think the current discussion is very useful:  It could help us find out whether the cases where cuts do more than just help with error messages are interesting enough to justify including them.

> It seems I had the wrong idea of extensibility.  I also had a slightly wrong mental model for map validation in that I was thinking in terms of "this says that this key must have this type", which isn't quite accurate.  Though, I would say the example suggests the reading I gave to it, because after all what is the point of having "? displayName : tstr" in there if the "displayName" key can actually appear with any type of value at all, due to the "* tstr => any"?  (I'm still assuming that displayName: tstr is the same as "displayName" => tstr - that I wasn't supposed to read the example with cuts in mind and the colon being shorthand for a cut.)
> 
> I think I understand better now, except this one thing...  I don't understand why
> 6 : "hi" does not (alone or with anything else for that matter) match the optional group, but it does match the *int => tstr.

That is correct.
(I didn’t validate the examples in my message with a tool, sorry about that…)

Grüße, Carsten

---

From: Kevin Braun <[email-masked]>
Date: Wed, 19 Jul 2017 15:52:01 -0400

Hi Carsten,

>>     top = { ? 4 => int, *int => tstr }

Note that CDDL tool does not agree with the above (it does not validate 
it).  Based on what you've told me, I assume that is a bug.  Or, have I 
really misunderstood something?  I also found that CDDL tool won't 
validate { "displayName" : 5 } against the PersonalData definition below.

> (Actually, that may be a valid extension in some universes, but it may or may *not* be what the spec writer intends here.)

I'm not quite sure what you mean by that.  I think you're just 
acknowledging that my idea of extension might be what some people would 
think of or be looking for, even though it isn't how CDDL actually works?

My thought here is that when you have a "data definition language", 
people are going to approach it like a schema language and interpret the 
above along the lines of defining fields and value types. Whereas, if 
you take the language to be a pattern language, then you start thinking 
of these things in the map definition as alternatives that your 
key-value pairs might or might not match, and then saying "displayName" 
might have any value type given the above rule makes total sense.  
Unfortunately (in my opinion), the example leads one to think in terms 
of field-definitions rather than patterns, since the pattern 
interpretation makes "? displayName : tstr" superfluous and you don't 
expect superfluous things in examples.  I hope what I'm saying makes 
sense.  (But, given the CDDL tool results I noted above, perhaps I've 
completely misunderstood.)

Regards,
Kevin

---

From: Jeffrey Yasskin <[email-masked]>
Date: Thu, 20 Jul 2017 03:15:52 +0200

By the time CDDL makes it to an RFC, we should be answering questions like
this by quoting normative text from
https://tools.ietf.org/html/draft-greevenbosch-appsawg-cbor-cddl-11#section-3.5,
not just pointing at examples.

Jeffrey

On Tue, Jul 18, 2017 at 11:18 PM, Carsten Bormann <[email-masked]> wrote:

> came up.  One would think map validation would be fairly obvious, but what
> happens when key types overlap?
> >
> int value.  Or, does it allow a key of 4 to appear with a text string value
> while considering the optional "4 => int" as being absent?
>
> The reason is that the map opens a choice point.  A member with key 4 is
> starting to match the field.  If the value however does not  match (because
> there is no int), the matcher falls back to the choice point.  It then
> tries the other field, and indeed, that matches.
>
> In the research underlying CDDL, we have discussed “cuts” (a concept from
> error handling in Parse Expression Grammars (PEGs)) as the solution to
> this.  If ^ represents a cut, write:
>
> A nice side effect is that anything except an int after a key of 4 can
> give a definite error message of “int expected”.
> > Given the examples in the spec, I guess the intention is for such a
> thing to mean the key 4, if present, has to have an int value.
>
> Actually, the PEG semantics we have borrowed here is that the *first*
> match is used.  But only rules are matched that indeed match!
>
> > How that rule applies in more complex situations (where there is some
> kind of nesting) probably needs to be spelled out....  Given:
> >
> No.  The first field eats the 1: 1, the second field only matches the 5:
> 5, so the third field gets to eat zero or more int: tstr, of which 6: “hi”
> is a match.
>
> > Or, does it require that a key of 5, if present, must have a value that
> is both a text string and an int at the same time (i.e. it disallows 5 to
> appear)?
>
> That would never be the semantics — the fact that there are two branches
> in a choice that can be fulfilled is not an error.
>
> With a cut like this:
>
> this could mean that key 0..10 cut the choice and therefore need to have a
> text string value, while the rest, 11..15 can be integers, because the
> choice is cut after matching 0..10.
>
> If you feed {“type”: “wine”, “ferment”: “top”} into this, you get a rather
> unspecific error message that tells you things don’t match up — the matcher
> can’t really know whether the “type” value of “wine" or the “ferment” key
> is the “cause” of neither branch matching.
>
> If you add a cut:
>
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor
>