Subject: [Cbor] Parsing CDDL

From: David Brown <[email-masked]>
Date: Tue, 31 Jul 2018 16:58:54 -0600

I have written up a small (220 line) parser based on the
draft-ietf-cbor-cddl-03 document.  The code can be found at
https://github.com/d3zd3z/suit-play/blob/master/cddl.rkt.  I used the
Racket lexer and parser tools to make this easier.

I believe this parser parses (nearly) the same language described in
the ABNF grammar in the draft (see below about spaces).  However, a
couple of observations:

  - in the rule for 'rule', since a 'type' by itself is a valid
    'grpent', this rule is ambiguous.  I made the parser work by
    simply commenting out the first alternate.  I would gather that a
    tool using the output of this parser would have to store all
    entities, and check that a name used elsewhere as a type must be
    restricted to the 'type' form.

  - Spaces are a little complicated, and I'm not sure quite as
    intended.  One production (for #6(...)) has a comment "note no
    space", however there are a few other places that are missing
    spaces (such as the space after the open paren on the

       "(" type ")"

    alternate.  I found this much easier to handle by consuming spaces
    in the lexer and not making them part of the grammar at all.  In
    order to do this, three things:

       "#" "6" ["." uint] "(" S type S ")"
       "#" DIGIT ["." uint]

       [uint] "*" [uint]

    must be captured by the lexer, since these production would make
    the grammar ambiguous unless the space is not allowed.  I assume
    the intent is to interpret these with "maximal munch" (mostly
    thanks to the comma being optional).

    I also capture the repetition operation with numbers at lex time
    to avoid additional ambiguity.

  - The ABNF grammar references code points such as %x5D-10FFFD.  Is
    it intentional to include the invalid range D800-DFFF, which are
    reserved for surrogate pairs in UTF-16?  They are not considered
    valid codepoints for UTF-8, and depending on the tools/language
    used, may be rejected before codepoints are given to the parser.

  - The text of the draft states that hexidecimal numbers "... are
    case insensitive", however the ABNF grammar only accepts
    hexidecimal digits in uppercase.

  - There are productions allowed by the grammar whose meaning is not
    described by the text of the draft.  For example:

       item = [ int => bstr ]

    is valid with the grammar, but it is unclear what this means.
    Perhaps this could describe an ordered map, or an array of pairs
    of items.  Related are arrays that contain more than a single
    item:

       item = [ int, bstr, 5 ]

  - What is the intended interpretation of:

       groupname = (a b // c d)

    My parser interprets this as ((a b) // (c d)), however
    (a (b // c) d) is also a valid interpretation, an probably what is
    intended, especially if commas are used  (a, b // c, d).

  - Related to the above, the grammar allows things like like

       grp = (// //)

    is this intentional?

With some work, I believe it would be possible to transform this
grammar into something LALR(1) (my grammar is part way there), but it
would make some of the productions difficult to read.  However, it may
be a useful exercise because it would force any other ambiguities in
the grammar.

I wrote this starting with a LALR(1) parser, and wrote as much as I
could without any shift/reduce conflicts, and reverted to a general
backtracking parser near the end.  The LALR(1) parser is significantly
easier to debug, and tends to produce better error messages.

David Brown

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 1 Aug 2018 01:36:52 +0200

Hi David,

Thanks for doing this work!

It’s already late here, so I’ll save the full follow-up for tomorrow (the space stuff needs me to be awake), but let me just amuse myself with the frequency with which one little detail tends to trip up ABNF users.

>   used, may be rejected before codepoints are given to the parser.

Since CDDL is encoded in UTF-8, the invalid code points cannot happen.
So %x5D-10FFFD is meant as a shortcut for “all the valid code points in this space”.
There is no need for redoing the work of the UTF-8 decoder in the grammar.

>   hexidecimal digits in uppercase.

Let’s see,

HEXDIG = DIGIT / “A" / "B" / "C" / "D" / "E" / "F"

Since ABNF is case-insensitive, this does cover both lower and upper case.

(The same is true for 0x, 0b, h, b64 etc.
Don’t feel bad, *every* ABNF user trips up on this at least once…
It is highly unintuitive in 2018, and hence RFC 7405, which is not needed by CDDL as all language features [not the rule names, though!] are indeed case insensitive.)

>   is valid with the grammar, but it is unclear what this means.

An array with a single bstr in it, as in these three examples:

$ cddl -<<<"item = [ int => bstr ]" gen 3
[h'76697065726C696B65']
[h'6F63756C6F63657068616C6963']
[h’726572697365']

I’m curious what part of the existing text is unclear about this.

>   of items.  Related are arrays that contain more than a single

$ cddl -<<<"item = [ int, bstr, 5 ]" gen 3
[1137, h'6D6974696761626C65', 5]
[-389, h'4E6567726F7068696C65', 5]
[114, h’536F726768756D', 5]

>   My parser interprets this as ((a b) // (c d)),

Yes.  Precedence of // is below ,

> however
>   (a (b // c) d) is also a valid interpretation,

Maybe it is a bit too late in Europe already, but I don’t see how to derive the latter from the grammar (assuming we use the grammar to “parse” the sentences of the language).  Can you give the derivation?

> an probably what is

Again, precedence of // is below , — so ((a, b) // (c, d)) is what is supposed to happen.

(As with ABNF, it is never wrong to add a few parentheses instead of relying on precedences, but experienced CDDL specifiers like it that you can express choices between these sequences without a lot of clutter.)

> - Related to the above, the grammar allows things like like

It is a redundant way of saying

	grp = ()

(That group is always an empty sequence.)

Thanks for finding a bug in my tool :-)

> be a useful exercise because it would force any other ambiguities in

The CDDL grammar has not been made easy for people writing parsers, but for people writing specifications…  But I’d sure like to know whether it can be made LALR(1) — I’d say, it needs a lookahead of 2.

> […] produce better error messages.

Yes, that may indeed be possible.  But redoing the grammar so it works with a lookahead of 1 doesn’t seem possible to me without completely changing the language.

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 1 Aug 2018 01:44:26 +0200

> It is highly unintuitive in 2018, and hence RFC 7405, which is not needed by CDDL as all language features [not the rule names, though!] are indeed case insensitive.)

Actually, h and b64 are not:

bsqual = %x68 ; "h"
       / %x62.36.34 ; "b64"

Should we change this for consistency?

Grüße, Carsten

---

From: David Brown <[email-masked]>
Date: Tue, 31 Jul 2018 18:06:57 -0600

>Since ABNF is case-insensitive, this does cover both lower and upper case.

Yeah, I missed that section of ABNF where it states that _strings_ are
case insensitive.  That is certainly not intuitive, and makes
specifying case-sensitive languages tedious.

>[h'6F63756C6F63657068616C6963']

This comes from the description of 'struct', then.

>[114, h’536F726768756D', 5]

Does this mean that an array specification  [ ... ]  defaults to
allowing only a single entity?  This would require an occurrence
specification on any arrays, and is certainly not how I see other
drafts that use CDDL interpret it (even though it is not stated
explicitly).

I would assume that the above should allow:

  [ 1, h'1AB2', 5 ]
  []
  [ 1, h'1AB2', 5, 7, h'5421' 5 ]
  etc

But I guess that currently requires an explicit occurrence indicator.

This does seem counter-intuitive to me, since CDDL notates structs and
arrays the same way, yet the array requires the explicity occurrence
indicator.

David

---

From: Jeffrey Yasskin <[email-masked]>
Date: Tue, 31 Jul 2018 21:06:19 -0700

> I’m curious what part of the existing text is unclear about this.

That's the wrong question to ask when reviewing a specification. We have to
find a piece of the text that's clear about the meaning we want.

I believe the text that covers this is in Appendix C,
https://cbor-wg.github.io/cddl/draft-ietf-cbor-cddl.html#matching:

     / "[" S group S "]"
> an array expression, which matches a CBOR array the elements of which,
> when taken as values and complemented by a wildcard (matches anything) key
> each, match the group

That is, [ int => bstr ] matches a CBOR array when the elements of the
array (e.g. ['mybstr']) are taken as values and given a matches anything
key (so, [ <matches-anything>: 'mybstr' ]), and then they match against the
(int => bstr) group:

    group = grpchoice S *("//" S grpchoice S)
> A group matches any sequence of key/value pairs that matches any of the
> choices given (again using Parse Expression Grammar semantics).
>

>     grpchoice = *grpent
> Each of the component groups is given as a sequence of group entries. For
> a match, the sequence of key/value pairs given needs to match the sequence
> of group entries in the sequence given.
>

So (int=>bstr) matches (<matches-anything>: 'mybstr') because the one
key/value pair matches the one group entry, but (int=>bstr) doesn't match
(<matches-anything>: 'bstr1', <matches-anything>: 'bstr2'), because 2
elements don't match 1.

*This is less clear than it should be, since nothing says what it means for
one sequence to "match" another sequence.
Hence https://github.com/cbor-wg/cddl/issues/14
<https://github.com/cbor-wg/cddl/issues/14>.*

> This comes from the description of 'struct', then.

https://cbor-wg.github.io/cddl/draft-ietf-cbor-cddl.html#structs is more a
set of examples of how to use CDDL than a specification. The specification
of => is again in
https://cbor-wg.github.io/cddl/draft-ietf-cbor-cddl.html#matching under
"memberkey"

> allowing only a single entity?

As many items as the specification has entries, yes.

> This would require an occurrence

*Can you point to the other drafts you're thinking of here?* It'd be good
to see examples of how people are understanding or misunderstanding CDDL,
to motivate clarifications to the specification.

> But I guess that currently requires an explicit occurrence indicator.

Yep.

> arrays the same way, yet the array requires the explicity occurrence

Structs also require explicit occurrence indicators if you want to repeat
fields, except that's usually pointless because a CBOR map can only have
one entry with a given key, and structs usually specify their keys with
single-value types.

Jeffrey

---

From: David Brown <[email-masked]>
Date: Tue, 31 Jul 2018 22:32:10 -0600

On Tue, Jul 31, 2018 at 09:06:19PM -0700, Jeffrey Yasskin wrote:

>Can you point to the other drafts you're thinking of here? It'd be good to see
>examples of how people are understanding or misunderstanding CDDL, to motivate
>clarifications to the specification.

Specifically: https://datatracker.ietf.org/doc/draft-moran-suit-manifest/

There is, for example, a definition:

   Directive = [ int => bstr ]

I suspect it was meant to be a map, but if I'm understanding the spec,
this is an array containing a single bstr.

SUIT has a need for something like a map, but where the order of the
entries can be controlled.  It sounds to me like:

   [ * (int, bstr) ]

would be useful, or even more useful, instead of a bstr, a specific
type, depending on what the int is.  This is meaningful with a map and
'=>' to give specific types for each int, but can this be specified
for pairs like this.

What SUIT currently has are constructs such as:

   [ ...
     preConditions: [ * PreCondition ],
     ...
   ]

   PreCondition = IdCondition / TimeCondition /
		  ImageCondition / CustomCondition
   IdCondition = [vendor: 1 / class: 2/ device: 3,
		  id: Uuid]
   TimeCondition = [installAfter: 4 / bestBefore: 5,
                    time: Timestamp]
   ...

Where it is an array of structure, where the first element of each
structure is an int that gives the meaning/interpretation of the rest
of the structure.  Is there a better way to represent this?

COSE, for example, uses a map, but its model is indeed a map, and
there is no meaningful order to the entries.  For SUIT, some of the
values are indicating a specific sequence, and order needs to be
maintained.

Hopefully this makes sense,
David