Subject: [apps-discuss] Concise Binary Object Representation (CBOR) -- new version -01

From: Carsten Bormann <[email-masked]>
Date: Wed, 29 May 2013 16:53:04 +0200

Based on the substantive feedback we received here, we have submitted draft-bormann-cbor-01.

The major new addition is support for streaming of arrays and maps and chunking of strings.
You may also like the background information about other binary formats in Appendix E.

List of changes below.

Grüße, Carsten

* Major changes

Changed the values for "additional information" to allow for
indefinite length arrays and maps, and to also allow for future
expansion.

While we were changing the encoding for that: swapped major types 6
and 7 to bring the content-bearing major types together numerically.

Added the "break" stop code to (now) major type 7 to allow for
indefinite length arrays and maps.

Added a tag for chunking of (building from multiple chunks) arrays of
byte strings and arrays of UTF-8 strings.

* Minor additions

Added a section discussing indefinite length arrays and maps and their
use in streaming applications.

Added a section on optional canonicalizing CBOR data.

Added a section on extensibility of CBOR and its future evolution.

In the diagnostic notation, added indicators for indefinite length
arrays and maps.

Added an appendix of comparisions of other binary formats with CBOR's
design goals.

* Editorial changes

Clarified CBOR's endiannness.

Added acknowledgements for recent contributors.

Fixed all the tables and examples to deal with the above wire changes.

---

From: "Manger, James H" <[email-masked]>
Date: Fri, 31 May 2013 00:43:55 +1000

> The major new addition is support for streaming of arrays and maps and

CBOR draft 01 looks great.
Streaming support fits in without too much damage to the structure. Thanks.

I wrote a CBOR decoder [Java; DOM-style; 244 loc] and it agreed with all the examples (except 16-bit floats that I haven't implemented; and integers 2^64 - 1 and -2^64 which don't fit in Java's 64-bit signed long).

Very minor comment:
In my experience base64url is invariably used without "=" padding, while base64 is invariably used with "=" padding. I would define tags 21 & 22 as such, instead of saying no padding is used for either [in 2.3.5.2. Expected Later Encoding for CBOR to JSON Converters].

--
James Manger

---

From: Nico Williams <[email-masked]>
Date: Fri, 31 May 2013 11:53:06 -0500

Comments on -01:

 - Do tags stack/nest?  I.e., could you have a chunked bignum?

 - Chunking cannot be optional.  Therefore tags can't be "truly optional".

 - I'm concerned about chunking being a tag.  In particular I'm
concerned about what tag stacking combinations are permitted (see
above), about chunking being optional because tags are optional, and
about chunking being a bit of a bolt-on.  I think I'd recommend using
type 7 to indicate that some of the remaining 5 bits of the type byte
carry type information -- that is, make chunking "first class".

 - JSON cannot provide a strict upper bound on CBOR encoding size.  It
should be trivial to construct a JSON value that takes up more room
using CBOR than JSON (for example: any printable ASCII string (with no
embedded newlines) whose length requires more than two bytes to
encode).

OLD:
   Stream parser:  A process that decodes a data stream and makes each
      of the data items in the sequence available to an application.
NEW:
   Stream parser:  A process that decodes a data stream and makes each
      of the data items in the sequence available to an application as they are
      received.

 - There's also streaming encoders.  On the encoder side the cause of
the need for indefinite length encoding / chunking is lack of
knowledge about the size of source values (the encoder's input is a
"stream"), or the receiver's need for the same for the same reason
regarding the sink.  That is, either the source or the sink can create
a need for streaming.  In particular, having JSON "piped" in to a
JSON->CBOR encoder the encoder cannot use definite lengths nor
non-chunked strings for values that don't fit in its buffers.

   On the receiver side one can imagine CBOR being used to transport
data to be processed in a streaming way by a tool like
stedolan.github.io/jq (a streaming JSON query processor, a JSON sed of
sorts), which might make progress with partially-transferred values.

Anyways, -01 is better than -00.

Nico
--

---

From: "Joe Hildebrand (jhildebr)" <[email-masked]>
Date: Fri, 31 May 2013 17:42:34 +0000

> - Do tags stack/nest?  I.e., could you have a chunked bignum?

An earlier version of the draft explicitly forbid this, but I can't find
the language anymore.  Carsten, is that intentional?  It would be fine
with me if they were still forbidden, from an ease of implementation
perspective.

> - Chunking cannot be optional.  Therefore tags can't be "truly optional".

The tag just says to recombine the chunks into a single object.  Without
the tag, you get an array, which is adequately parseable.

>carry type information -- that is, make chunking "first class".

See section 2.4; it seems like you've already got what you want.  When I
read 2.3.4 without having read the new bits in MT4 and MT5, I thought the
same thing.  I had to re-read those other bits before I got it.

>embedded newlines) whose length requires more than two bytes to

Yes.  Some strings that are 257-65536 octets long will take up an extra
octet on the wire.  However, as long as you're not using chunking, you
have chances to optimize the number of times you allocate memory, and
don't have to worry about escape decoding, both of which are quite nice
CPU wins.

As well, and more importantly for me, you can send generic octet streams
that are not valid UTF8.

>Anyways, -01 is better than -00.

Agree.  It adds complexity, but if those streaming use cases continue to
be important to folks, I suppose it's not enough complexity that it can't
be tolerated.

-- 
Joe Hildebrand

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 31 May 2013 19:51:28 +0200

> with me if they were still forbidden, from an ease of implementation

I believe it would be a mistake for the basic syntax to disallow this.
Tags already can nest indirectly (e.g., a Decimal could have a bignum as a mantissa embedded into its two-element array if only Decimal allowed that).  
It is hard to justify why the basic syntax should disallow direct nesting.

However, every single tag we have defined so far is explicit about what can be in it.
I don't think the current text allows you to have a chunked bignum (i.e., a bignum tag around a chunking tag).
So we probably have to pay more attention to where we actually do want tags to directly nest.

Grüße, Carsten

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 31 May 2013 11:11:03 -0700

On May 31, 2013, at 9:53 AM, Nico Williams <[email-masked]> wrote:

> - Do tags stack/nest?  

We have not specified that yet. Clearly we should do so.

> I.e., could you have a chunked bignum?

We did not anticipate a chunked bignum; is there a non-edge use case for this? 

> - Chunking cannot be optional.  Therefore tags can't be "truly optional".

Why can chunking not be optional? The program doing the parsing presumably knows that is expected at this location that is an array. It thus knows what to do with that array: treat it as a bunch of items, or combine them into a single large item.

Tagging is to allow an encoder to indicate something to the parser, but every application that knows what it is receiving already knows what the tag would be indicating. Tagging is thus only useful to generic parsers that might also do something different if they knew that the incoming array could be chunked. All of the tags, including chunking, share this optional feature.

> carry type information -- that is, make chunking "first class".

See above. I'm not sure where that would be needed other than for a generic parser, but I could be missing it.

> embedded newlines) whose length requires more than two bytes to

Correct. Did we say something in the doc that needs to be corrected or clarified for that point?

>      of the data items in the sequence available to an application as they are

Sounds good.

> non-chunked strings for values that don't fit in its buffers.

That's not true as long as the encoder can jump to a particular place in its buffer. Such an encoder uses a length for the array that is large enough to fit anything that it could hold, accepts all of the data and counts as it comes in, then jumps back to the length value and fills it in.

> Anyways, -01 is better than -00.

Good to hear.

--Paul Hoffman

---

From: Nico Williams <[email-masked]>
Date: Fri, 31 May 2013 15:12:02 -0500

> We have not specified that yet. Clearly we should do so.

Yes.

> We did not anticipate a chunked bignum; is there a non-edge use case for this?

Bignums can get very big.  That's... their point :)

> Why can chunking not be optional? The program doing the parsing presumably knows that is expected at this location that is an array. It thus knows what to do with that array: treat it as a bunch of…

Chunking needs to be first-class.  Otherwise senders and recipients
need to agree a priori (or negotiate) on chunking support -- no
thanks!

> Tagging is to allow an encoder to indicate something to the parser, but every application that knows what it is receiving already knows what the tag would be indicating. Tagging is thus only useful…

I don't agree.  Chunking is not semantics.  "Date" is.  But even
there, "date" is important *type* information in many systems, rather
than incidental or context-specific (or heuristically determined)
information.

Chunking is nothing more than a form of indefinite length encoding for
strings with an unfortunate name (that might be confusing you as to
the essence) -- one that does not require escaping codepoints in the
string.  In fact, JSON's string encoding *is* indefinite-length, and
the price we pay for it is having to escape things in it (ugh!).

If you agree that indefinite-length encoding of arrays and objects is
required, why would you not also agree that indefinite-length encoding
of other potentially huge values is *also* required?

The whole point of indefinite-length encoding is to allow for
streaming encoding and decoding, which means (in part): with bounded-
or fixed-size buffers.  If a value blows past a buffer size we lose
with definite-length encoding.

> See above. I'm not sure where that would be needed other than for a generic parser, but I could be missing it.

I think you are missing it :)

> Correct. Did we say something in the doc that needs to be corrected or clarified for that point?

The doc doesn't say that was a strict goal.  I'm just pointing out a nit.

> That's not true as long as the encoder can jump to a particular place in its buffer. Such an encoder uses a length for the array that is large enough to fit anything that it could hold, accepts all…

The key word in your response there is "buffer".  Picture a
fixed-sized buffer.  There's no way to "jump" to some place in the
buffer that's out of the buffer's bounds.

Being able to set max buffer sizes is very important.  It allows one
to limit the resources that a sink can made to consume by a source
(not even peer, because for an encoder there's still a source) before
realizing that the data is bad (and slam the door).  Or even if you
think beyond security, to stream from/to disk on a system with
thousands of concurrent users, one user forcing you to consume 10GB of
buffer space can ruin the others' day.

I don't think you can escape the conclusion that indefinite-length
encoding is needed for *every* value whose encoding is unbounded
(e.g., null, booleans, doubles don't need indefinite-length encoding,
while strings, arrays, objects, and yes, even bignums, do).

Nico
--

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 31 May 2013 22:23:39 +0200

> Bignums can get very big.  That's... their point :)

This is just proof by lack of imagination, but I can't imagine serializing a bignum the size of which you don't know by the time you start serializing it.

Looking at the other tags that accept strings, the 30+ tags probably all want to accept chunking.
Of course, we could redefine them to just accept arrays with chunking semantics, saving a byte.
(21 to 23 can't be redefined that way unless we lose the "all the things in this map/array are base64url" semantics.)

With respect to the first class thing:  Nothing stops us from proclaiming 0xc5 "first class".
It's still a tag in the big scheme of things, but probably one that you do want to implement along with the streaming arrays and maps.
(In hindsight, I should have given it tag 15 = 0xcf to make this look more symmetric alongside 0x9f, 0xbf, 0xff :-)
Symmetry always is appealing.
To add more apparent symmetry, we can always change it to 0xdf :-)

Grüße, Carsten

---

From: Nico Williams <[email-masked]>
Date: Fri, 31 May 2013 15:33:37 -0500

> This is just proof by lack of imagination, but I can't imagine serializing a bignum the size of which you don't know by the time you start serializing it.

Imagine JSON had bignums (doesn't, but imagine).  Imagine JSON's
bignum encoding as indefinite-length (like *everything* else in JSON).
 Imagine you were writing a fixed-buffers JSON<->CBOR converter.

> (21 to 23 can't be redefined that way unless we lose the "all the things in this map/array are base64url" semantics.)

No, really, chunking is just indefinite-length encoding for
string-like values.  We need it for the same reasons that we need
indefinite-length encoding for arrays and objects.

If you disagree, then please explain the distinction between the two
kinds of values (strings on one side, arrays/objects on the other).

> With respect to the first class thing:  Nothing stops us from proclaiming 0xc5 "first class".

You made it "truly optional".  (Not OPTIONAL, but proper use of
RFC2119 words is a separate nit; I assume you meant OPTIONAL.)

> To add more apparent symmetry, we can always change it to 0xdf :-)

I don't care about aesthetics here.  I care about having
indefinite-length encodings for *all* values that lack a bounded
encoded size.  That's a form of symmetry, but higher up in the stack.
I don't mind chunking being expressed with a tag, as long as it's
REQUIRED and as long as it's clear what other tags it can be mixed
with.

(The fact that chunking was made a tag made me nervous because it made
it seem like an after-thought, and I'm now convinced that's just what
it was.  You misunderstood the point of chunking, it's being just
another way of saying "indefinite-length without escaping".  I can see
why you thought that my complaint as about lack of symmetry in the
details of encoding, but it wasn't.)

Nico
--