Subject: Re: [Cbor] Validation of maps

From: Francesca Palombini <[email-masked]>
Date: Thu, 5 Oct 2017 10:50:38 +0000

Agreed with Jeffrey.

Reviving this thread to ask the opinion from the working group:

From: CBOR [mailto:[email-masked]] On Behalf Of Jeffrey Yasskin
Sent: den 20 juli 2017 03:16
To: Carsten Bormann <[email-masked]>
Cc: Kevin Braun <[email-masked]>; [email-masked]
Subject: Re: [Cbor] Validation of maps

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]<mailto:[email-masked]>> wrote:
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?
>
> 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,

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:
>
> 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?

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:
>
>   top = { 1 => 1, ? ( 5 => 5, 6 => 6 ), *int => tstr }
>
> 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:
>
>   top = { 1 => 1, ( 5 => 5 // 6 => 6 ), *int => tstr }
>
> 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:
>
>   top = { * (0..10) => tstr, * (5..15) => int }
>
> 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

_______________________________________________
CBOR mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/cbor

---

From: Francesca Palombini <[email-masked]>
Date: Thu, 5 Oct 2017 10:53:11 +0000

Sorry, early sent. The opinion I’d like to hear from the working group: is cuts something we want to consider putting in at this point?

Francesca

From: Francesca Palombini
Sent: den 5 oktober 2017 12:51
To: 'Jeffrey Yasskin' <[email-masked]>; Carsten Bormann <[email-masked]>
Cc: Kevin Braun <[email-masked]>; [email-masked]
Subject: RE: [Cbor] Validation of maps

Agreed with Jeffrey.

From: CBOR [mailto:[email-masked]] On Behalf Of Jeffrey Yasskin
Sent: den 20 juli 2017 03:16
To: Carsten Bormann <[email-masked]<mailto:[email-masked]>>
Cc: Kevin Braun <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Subject: Re: [Cbor] Validation of maps

Jeffrey

Yes.

Yes.

With a cut like this:

orderbeer = {
  type: “beer”,

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

If you add a cut:

orderbeer = {
  type: “beer” ^,

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

Grüße, Carsten

---

From: Jim Schaad <[email-masked]>
Date: Thu, 5 Oct 2017 09:15:23 -0700

My opinion on this issue is that the open choice only matches if there is not an explicit choice with that value in the map.  It is the intention that this is what is there and if you have a fast parser which check types, then it should fail.  The code is going to presume that the value with tag 4 is an int and should not get surprised in the middle of processing, it should fail during validation if the parser is that smart.

Thus  { ?4=>int, * =>any}  should fail for { 4:”text”} 

Jim

From: CBOR [mailto:[email-masked]] On Behalf Of Francesca Palombini
Sent: Thursday, October 5, 2017 3:53 AM
To: Carsten Bormann <[email-masked]>; [email-masked]
Subject: Re: [Cbor] Validation of maps

Francesca

From: Francesca Palombini 
Sent: den 5 oktober 2017 12:51
To: 'Jeffrey Yasskin' <[email-masked] <mailto:[email-masked]> >; Carsten Bormann <[email-masked] <mailto:[email-masked]> >
Cc: Kevin Braun <[email-masked] <mailto:[email-masked]> >; [email-masked] <mailto:[email-masked]> 
Subject: RE: [Cbor] Validation of maps

Agreed with Jeffrey.

From: CBOR [mailto:[email-masked]] On Behalf Of Jeffrey Yasskin
Sent: den 20 juli 2017 03:16
To: Carsten Bormann <[email-masked] <mailto:[email-masked]> >
Cc: Kevin Braun <[email-masked] <mailto:[email-masked]> >; [email-masked] <mailto:[email-masked]> 
Subject: Re: [Cbor] Validation of maps

Jeffrey

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

Hi Kevin,

Yes.

Yes.

With a cut like this:

orderbeer = {
  type: “beer”,

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

If you add a cut:

orderbeer = {
  type: “beer” ^,

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

Grüße, Carsten

_______________________________________________
CBOR mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/cbor

---

From: Henk Birkholz <[email-masked]>
Date: Thu, 5 Oct 2017 18:24:10 +0200

I tend to agree (pols). Other thoughts?

Henk

On October 5, 2017 6:15:23 PM GMT+02:00, Jim Schaad <[email-masked]> wrote:
>My opinion on this issue is that the open choice only matches if there
>is not an explicit choice with that value in the map.  It is the
>intention that this is what is there and if you have a fast parser
>which check types, then it should fail.  The code is going to presume
>that the value with tag 4 is an int and should not get surprised in the
>middle of processing, it should fail during validation if the parser is
>that smart.
>
> 
>
>Sorry, early sent. The opinion I’d like to hear from the working group:
>is cuts something we want to consider putting in at this point?
>
>
>Francesca
>
> 
>
>To: 'Jeffrey Yasskin' <[email-masked]
><mailto:[email-masked]> >; Carsten Bormann <[email-masked]
><mailto:[email-masked]> >
>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
>
> 
>
>> 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?
>>
>> 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?
>
>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.
>
>So far, we haven’t seen a use case that actually needed the cut, but it
>is still nice to have that error message.
>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:
>

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.