Subject: [Cbor] CDDL -04 ready; new Version for draft-bormann-cbor-cddl-freezer-01.txt

From: Carsten Bormann <[email-masked]>
Date: Fri, 10 Aug 2018 08:16:44 +0200

I believe CDDL is now ready for submission as -04; I intend to do this at 1200Z (I.e., about 5¾ hours from now).
If you have  a bit of time to look at this, please consult:

http://gg.gg/cddl-editor-diff
https://github.com/cbor-wg/cddl/

In particular, it may be worth to look at the cleaned up ABNF.

I have already submitted an update for the freezer document (see below); comments and pointers to omissions welcome.

Grüße, Carsten

> Name:		draft-bormann-cbor-cddl-freezer
> Revision:	01
> Title:		A feature freezer for the Concise Data Definition Language (CDDL)
> Document date:	2018-08-10
> Pages:		7
> Status:         https://datatracker.ietf.org/doc/draft-bormann-cbor-cddl-freezer/
> Htmlized:       https://tools.ietf.org/html/draft-bormann-cbor-cddl-freezer-01
> Diff:           https://www.ietf.org/rfcdiff?url2=draft-bormann-cbor-cddl-freezer-01
> 
> Abstract:
>   In defining the Concise Data Definition Language (CDDL), some
>   features have turned up that would be nice to have.  In the interest
>   of completing this specification in a timely manner, the present
>   document collects nice-to-have features that did not make it into the
>   first RFC for CDDL.

---

From: Jeffrey Yasskin <[email-masked]>
Date: Thu, 9 Aug 2018 23:58:16 -0700

As I mentioned in https://github.com/cbor-wg/cddl/issues/14, replacing the
undefined term "match" with the undefined term "can produce" doesn't
improve the situation. I suspect it's also inconsistent with the idea of
using a Parse Expression Grammar, since "can produce" seems to imply
backtracking in quantifiers, which PEGs don't do.

This doesn't need to block submission as -04, but it should block
submission as an RFC.

Thanks,
Jeffrey

On Thu, Aug 9, 2018 at 11:16 PM Carsten Bormann <[email-masked]> wrote:

> I have already submitted an update for the freezer document (see below);
> comments and pointers to omissions welcome.
>
> Grüße, Carsten
>
>
> > Status:
> https://datatracker.ietf.org/doc/draft-bormann-cbor-cddl-freezer/
> > Htmlized:
> https://tools.ietf.org/html/draft-bormann-cbor-cddl-freezer-01
> > Diff:
> https://www.ietf.org/rfcdiff?url2=draft-bormann-cbor-cddl-freezer-01
> >
> > Abstract:
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor
>

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 10 Aug 2018 13:53:40 +0200

Hi Jeffrey,

Did you see the changes in 
https://github.com/cbor-wg/cddl/commit/111b90b11b96d1e8fdc8614693a4164086b371b4

This commit has some additional text to define “can produce”, based on your comment that it wasn’t sufficiently defined.

If this new text is not sufficient, at this point, the best way forward would probably some proposed text.
I also would like to understand if you think there is an actual interoperability problem lurking here (and, if yes, I’d like a “failing test” to develop this further), or whether the text just isn’t perfect (which it isn’t).  Also, “can produce” certainly is not the ultimate wording, maybe we can define a better term.

(I’ll go ahead with submitting now; we can discuss this further during WGLC.)

Grüße, Carsten

> On Aug 10, 2018, at 08:58, Jeffrey Yasskin <jyasskin=[email-masked]> wrote:
> 
> As I mentioned in https://github.com/cbor-wg/cddl/issues/14, replacing the undefined term "match" with the undefined term "can produce" doesn't improve the situation. I suspect it's also inconsistent with the idea of using a Parse Expression Grammar, since "can produce" seems to imply backtracking in quantifiers, which PEGs don't do.
> 
> This doesn't need to block submission as -04, but it should block submission as an RFC.
> 
> Thanks,
> Jeffrey
>

---

From: Jeffrey Yasskin <[email-masked]>
Date: Fri, 10 Aug 2018 11:22:55 -0700

> https://github.com/cbor-wg/cddl/commit/111b90b11b96d1e8fdc8614693a4164086b371b4

I hadn't seen that. That's definitely an improvement in precision, but it's
not the definition of matching that
https://rubygems.org/gems/cddl/versions/0.8.5 uses. Is there a newer
version of that tool, or a test suite I can add to?
https://github.com/cabo/cddl doesn't work for me.

Specifically,

tstrs = [*tstr, +tstr]

"can produce"

["a", "a"]

because `tstr` can produce "a" per
https://tools.ietf.org/html/draft-ietf-cbor-cddl-04#section-2.1.2, `*tstr`
can produce () (the empty sequence) per
https://tools.ietf.org/html/draft-ietf-cbor-cddl-04#section-3.2, and
`+tstr` can produce ("a", "a") also per section 3.2.

However,

$ cddl <(echo 'tstrs = [*tstr, +tstr]') validate <(echo '["a",
"a"]'|diag2cbor.rb)

returns

CDDL validation failure (nil for ["a", "a"]):
>
> ["a",
>
>  [:prim, 3],
>  "[\"a\", [:prim, 3], \"occur not reached in array [\\\"a\\\", \\\"a\\\"]
> for [:array, [:member, 0, Infinity, nil, [:prim, 3]], [:member, 1,
> Infinity, nil, [:prim, 3]]]\"] -- cannot complete (false, 2) array [\"a\",
> \"a\"] for [:array, [:member, 0, Infinity, nil, [:prim, 3]], [:member, 1,
> Infinity, nil, [:prim, 3]]]"]

I also suspect the cut text does the wrong thing, but I'm having trouble
understanding

A cut in this position means that once the map key matches the name part of
> an entry that can be produced and carries a cut, other potential matches
> for the key that occur in later entries in the group of the map are no
> longer allowed.

if matching is driven by generating sequences from a rule.

I can't offer to write the better text because I don't know what you intend.

Jeffrey

> This commit has some additional text to define “can produce”, based on
> your comment that it wasn’t sufficiently defined.
>
> I also would like to understand if you think there is an actual
> interoperability problem lurking here (and, if yes, I’d like a “failing
> test” to develop this further), or whether the text just isn’t perfect
> (which it isn’t).  Also, “can produce” certainly is not the ultimate
> wording, maybe we can define a better term.
>
> > As I mentioned in https://github.com/cbor-wg/cddl/issues/14, replacing
> the undefined term "match" with the undefined term "can produce" doesn't
> > I believe CDDL is now ready for submission as -04; I intend to do this
> at 1200Z (I.e., about 5¾ hours from now).

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 10 Aug 2018 21:33:22 +0200

> On Aug 10, 2018, at 20:22, Jeffrey Yasskin <[email-masked]> wrote:
> 
> I hadn't seen that. That's definitely an improvement in precision, but it's not the definition of matching that https://rubygems.org/gems/cddl/versions/0.8.5 uses. Is there a newer version of that tool, or a test suite I can add to? https://github.com/cabo/cddl doesn’t work for me.

I am working on a newer version of the tool.

> tstrs = [*tstr, +tstr]

— the PEG semantics that is exhibited by the current version is intended.

Sorry, I was on a goose chase here, because I thought you were discussing cut semantics and not the general PEG semantics.  So I gather your point is improving the description of those.

(The text in Appendix C about occurrence acting as a potentially infinite group choice together with the text pointing out that choices — both type and group — use PEG semantics provides a full definition.  I might help to point to that from the introductory text.)

> [“a", "a"]

Right.

> because `tstr` can produce "a" per https://tools.ietf.org/html/draft-ietf-cbor-cddl-04#section-2.1.2, `*tstr` can produce () (the empty sequence) per https://tools.ietf.org/html/draft-ietf-cbor-cddl-04#section-3.2, and `+tstr` can produce ("a", "a") also per section 3.2. 
> 
> However, 
> 
> $ cddl <(echo 'tstrs = [*tstr, +tstr]') validate <(echo '["a", "a"]'|diag2cbor.rb)
> 
> returns
> 
> CDDL validation failure (nil for [“a", "a"]):   

As it should according to the PEG semantics.

> I also suspect the cut text does the wrong thing, but I'm having trouble understanding
> 
> A cut in this position means that once the map key matches the name part of an entry that can be produced and carries a cut, other potential matches for the key that occur in later entries in the group of the map are no longer allowed.
> 
> I can’t offer to write the better text because I don't know what you intend.

The intention is to use the PEG semantics for cuts as well.

Grüße, Carsten

---

From: Jeffrey Yasskin <[email-masked]>
Date: Fri, 10 Aug 2018 13:19:33 -0700

On Fri, Aug 10, 2018 at 12:33 PM Carsten Bormann <[email-masked]> wrote:

> > I hadn't seen that. That's definitely an improvement in precision, but
> it's not the definition of matching that
> https://github.com/cabo/cddl doesn’t work for me.
>
> Sorry, I was on a goose chase here, because I thought you were discussing
> cut semantics and not the general PEG semantics.  So I gather your point is
> improving the description of those.
>

I'm discussing both: there has to be 1 definition of when a CDDL rule
matches a CBOR item, and that definition needs to cover both the behavior
of quantifiers and alternation, and the behavior of cuts.

It's not clear what that means.
https://dl.acm.org/citation.cfm?id=964001.964011 defines how a PEG parses
input *strings*, but a CBOR map is not ordered, and so it's not clear how
to run a PEG over it. Without the meaning of a PEG over maps, the spec
can't define how cuts change that meaning.

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 10 Aug 2018 23:52:40 +0200

Hi Jeffrey,

thanks for helping us to get this fixed.

> I’m discussing both: there has to be 1 definition of when a CDDL rule matches a CBOR item, and that definition needs to cover both the behavior of quantifiers and alternation, and the behavior of cuts.

Yes.  I was reading your messages thinking that you had a problem just with cuts and not with the rest of the matching rules, and so I didn’t think about fixing the latter.  I now see what you are trying to achieve.

> It's not clear what that means. https://dl.acm.org/citation.cfm?id=964001.964011 defines how a PEG parses input *strings*, but a CBOR map is not ordered, and so it's not clear how to run a PEG over it. Without the meaning of a PEG over maps, the spec can’t define how cuts change that meaning.

Right.  So, while applying the matching rules of Section 3.3 of that paper to maps instead of strings, we are not chopping off the front of a string, we are picking off elements from that map.  Since the picking can occur anywhere in that map (there is no order), this adds non-determinism.  In real-world specifications, that problem is usually dodged intuitively by going from more-specific to more-general entries.  But it is possible to construct pathological cases:

A = { text => int, text => 2 }

A matches {“a”: 2, “b”: 4} if the first entry of the group happens to pick off “b”: 4 and not if it happens to pick “a”: 2.

(Playing around with version 0.8.5 of the tool is little help here, as its map matching algorithm is not quite up to the current spec.  This is one of the two main reasons I’m rewriting the tool right now.)

Grüße, Carsten

---

From: Jeffrey Yasskin <[email-masked]>
Date: Mon, 13 Aug 2018 09:44:12 -0700

On Fri, Aug 10, 2018 at 2:52 PM Carsten Bormann <[email-masked]> wrote:

> can’t define how cuts change that meaning.
>
> Right.  So, while applying the matching rules of Section 3.3 of that paper
> to maps instead of strings, we are not chopping off the front of a string,
> we are picking off elements from that map.  Since the picking can occur
> anywhere in that map (there is no order), this adds non-determinism.  In
> real-world specifications, that problem is usually dodged intuitively by
> going from more-specific to more-general entries.

It's going to be an interoperability problem if there's non-determinism in
whether an item matches a CDDL spec. The spec needs to either give a
deterministic way to pick the next map item, or give a rule for declaring
CDDL specs invalid so that all valid ones don't care what order the
implementation picks map items.

>   But it is possible to construct pathological cases:
>
> A matches {“a”: 2, “b”: 4} if the first entry of the group happens to pick
> off “b”: 4 and not if it happens to pick “a”: 2.
>
> (Playing around with version 0.8.5 of the tool is little help here, as its
> map matching algorithm is not quite up to the current spec.  This is one of
> the two main reasons I’m rewriting the tool right now.)
>

Unless I'm missing something, the current spec doesn't have a map matching
algorithm. Even if it said "implementations MUST translate the group to PEG
in ... way and then run it", which it doesn't, as described above that
wouldn't be sufficient. 0.8.5 may not be up to what you intend, but your
intent hasn't made it into the spec, and it needs to before there'll be a
point to a WGLC.

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 13 Aug 2018 21:32:48 +0200

> It's going to be an interoperability problem if there's non-determinism in whether an item matches a CDDL spec. The spec needs to either give a deterministic way to pick the next map item, or give a rule for declaring CDDL specs invalid so that all valid ones don’t care what order the implementation picks map items.

Right.  Reminds me of the “ambiguous content model” (again, this was not about ambiguity but non-determinism) discussion when SGML was finished.  Here, this was really complicated, as SGML had the “&” operator, which allows the DTD specification to leave open in which sequence required elements were to be included.  “&” was thrown out for XML because it made things complicated that didn’t need to be.  (Anne Brüggemann-Klein wrote a whole thesis about this subject in 1993.)

Unfortunately, for JSON (and due to its JSON heritage, for CBOR as well), we can’t just throw arbitrary ordering out.

So maybe we should do what SGML and then XML did: outlaw “ambiguous content models”, as in “For compatibility, it is an error if an element in the document can match more than one occurrence of an element type in the content model.” (http://www.w3.org/TR/REC-xml#sec-element-content)
The fun part about making something an “error” in XML is that a processor does not have to check it.

The problem we are discussing has not occurred in practice.  The reason is that it is natural, when writing the group for a map, to be quite specific.  Non-determinism only occurs in contrived examples.  I’d be unhappy to damage CDDL because of contrived examples.  I’d also be unhappy having to wait for Anne to write another thesis.
So just saying “pathological specs introduce non-determinism, don’t do that” is probably the best way to handle this for CDDL 1.0.

> Unless I’m missing something, the current spec doesn't have a map matching algorithm.

No, the semantics of matching a map against a group is not given as an algorithm:

“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 […]”

(Not having an algorithm, but a logical expression, is a feature, not a bug.)

The definition of the group matching mentions PEGs, but only for the choice, this probably needs to be added once more.

> Even if it said "implementations MUST translate the group to PEG in ... way and then run it", which it doesn't, as described above that wouldn't be sufficient. 0.8.5 may not be up to what you intend, but your intent hasn’t made it into the spec, and it needs to before there'll be a point to a WGLC.

Anything else to fix in addition to 
— calling out PEG semantics for occurrence indicators
— making specifications where the non-determinism can leads to multiple interpretations invalid
?

Grüße, Carsten

---

From: Jeffrey Yasskin <[email-masked]>
Date: Mon, 13 Aug 2018 14:21:36 -0700

On Mon, Aug 13, 2018 at 12:32 PM Carsten Bormann <[email-masked]> wrote:

>
> > It's going to be an interoperability problem if there's non-determinism
> in whether an item matches a CDDL spec. The spec needs to either give a
> CDDL specs invalid so that all valid ones don’t care what order the
> Right.  Reminds me of the “ambiguous content model” (again, this was not
> about ambiguity but non-determinism) discussion when SGML was finished.
> Here, this was really complicated, as SGML had the “&” operator, which
> allows the DTD specification to leave open in which sequence required
> elements were to be included.  “&” was thrown out for XML because it made
> things complicated that didn’t need to be.  (Anne Brüggemann-Klein wrote a
> whole thesis about this subject in 1993.)
>
> Unfortunately, for JSON (and due to its JSON heritage, for CBOR as well),
> we can’t just throw arbitrary ordering out.
>
> So maybe we should do what SGML and then XML did: outlaw “ambiguous
> content models”, as in “For compatibility, it is an error if an element in
> the document can match more than one occurrence of an element type in the
> content model.” (http://www.w3.org/TR/REC-xml#sec-element-content)
> The problem we are discussing has not occurred in practice.  The reason is
> that it is natural, when writing the group for a map, to be quite
> specific.  Non-determinism only occurs in contrived examples.  I’d be
> unhappy to damage CDDL because of contrived examples.  I’d also be unhappy
> having to wait for Anne to write another thesis.
> So just saying “pathological specs introduce non-determinism, don’t do
> that” is probably the best way to handle this for CDDL 1.0.
>

I'd count that as an algorithm, thanks. It requires that implementations be
equivalent to doing the O(n!) search over all permutations of the map
contents. Of course, no implementation will actually implement an O(n!)
algorithm, so they'll pick something O(n) that we hope gives the same
answer in all cases. If it doesn't give the same answer, that's an
interoperability bug.

The definition of the group matching mentions PEGs, but only for the
> choice, this probably needs to be added once more.
>
> > Even if it said "implementations MUST translate the group to PEG in ....
> way and then run it", which it doesn't, as described above that wouldn't be
> sufficient. 0.8.5 may not be up to what you intend, but your intent hasn’t
> made it into the spec, and it needs to before there'll be a point to a WGLC.
>

The PEG paper needs to be a normative reference.

— making specifications where the non-determinism can leads to multiple
> interpretations invalid

If "pathological spec" is clearly defined, such that creative spec-writers
can be sure they've written non-pathological CDDL without talking to this
group and without being experts on parsing, I'm happy with that.

- I'm not confident that the current "cut" language is clear: "A cut in
this position means that once the map key matches the name part of an entry
that can be produced and carries a cut, other potential matches for the key
that occur in later entries in the group of the map are no longer allowed."
Do you mean that any item whose key matches the 'cut' key, ignoring the
'cut' key's occurrence indicators, does not match a later group-entry in
the same group? If you mean something else, it didn't come through.

I think that'll be sufficient.

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 21 Aug 2018 19:37:42 +0200

Hi Jeffrey,

> If “pathological spec" is clearly defined, such that creative spec-writers can be sure they've written non-pathological CDDL without talking to this group and without being experts on parsing, I'm happy with that.

Please have a look at the most recent editor’s copy.

> - I'm not confident that the current "cut" language is clear: "A cut in this position means that once the map key matches the name part of an entry that can be produced and carries a cut, other potential matches for the key that occur in later entries in the group of the map are no longer allowed." Do you mean that any item whose key matches the ‘cut' key, ignoring the 'cut' key's occurrence indicators,

There are no occurrence indicators on the key — occurrence indicators are always on a whole group entry.
They are not ignored (why should they be?), but there are only a few cases that make a lot of sense:

? Key: value

That is the classical “if there is a map entry named “Key”, it needs to have value type “value”.

Key: value

The cut is a bit inconsequential here, as there needs to be a member in the map with the right key/value, since “Key” is a single-value type, this makes it impossible to match a »{ “Key”: “foo” }« (wrong value type) anyway.

type => value

with an occurrence indicator of 1*1 tends to give you non-deterministic results if the members could be matched by another entry, and this is less likely to occur.

* type => value

essentially cuts after all members whose keys have “type”, so this does have a meaning if it is followed by something like

* any => any

> does not match a later group-entry in the same group? If you mean something else, it didn’t come through.

Please do have a look at the additional text.

Let’s see if we can lay this to rest tomorrow!

Grüße, Carsten