Subject: [Cbor] Consolidated set of tags for map-like entities

From: Emile Cormier <[email-masked]>
Date: Fri, 12 Mar 2021 19:50:54 -0400

Hi Everyone,

I've been corresponding privately with Prof. Bormann about a new tag I
proposed for encoding multimaps as arrays or pairs. He's made me aware of
your recent discussion about another proposed tag for encoding "ordered"
maps, where the insertion order must be preserved. Carsten has indicated to
me his desire to consolidate all of these map-related tags together.

I would like to contribute to this endeavor of consolidating map-related
tags. To get the discussion started, I would like to share with you a draft
proposal I've written to serve as a starting point:
https://github.com/ecorm/cbor-map-like

Here's a brief summary:

This document proposes a consolidated set of CBOR tags for map-like
> entities involving key-value pairs. These tags encode the following
> meta-data concerning map-like entities:
>
>    - the homogeneity of the key and value types,
>    - the preservation of the insertion order of the key-value pairs,
>    - the uniqueness of the keys, and,
>    - the major type used to encode the key-value pairs.
>
> My interest in CBOR stems from my work on a new C++ serialization library
that can support any JSON-like encoding. This library is closed source for
now, but I may be able to convince my employer to make it open source in
the future.

I'm also involved with the WAMP protocol, which allows CBOR as one of its
encodings.

I'm looking forward to collaborating with you and I hope that we can come
to a solution that satisfies everyone's needs.

Cheers,
Emile Cormier

---

From: Joe Hildebrand <[email-masked]>
Date: Mon, 15 Mar 2021 12:50:02 -0600

Suggestion: make "Unique Keys: no" be a zero bit in the LSB, not 1, for ease of understanding the table.  Alternately, rename to "Allow duplicate keys".

In the "Key/Value Type" section, perhaps use 4 bits, so it's more clear which bits you're talking about?

Data Item being major type 5 should really only be used if the keys are homogeneously strings, in my opinion.

Overall, this feels like somewhat overkill, but solves the problem and I'd be fine with it if it allowed us to move on.

— 
Joe Hildebrand

> On Mar 12, 2021, at 4:50 PM, Emile Cormier <[email-masked]> wrote:
> 
> Hi Everyone,
> 
> I've been corresponding privately with Prof. Bormann about a new tag I proposed for encoding multimaps as arrays or pairs. He's made me aware of your recent discussion about another proposed tag for encoding "ordered" maps, where the insertion order must be preserved. Carsten has indicated to me his desire to consolidate all of these map-related tags together.
> 
> I would like to contribute to this endeavor of consolidating map-related tags. To get the discussion started, I would like to share with you a draft proposal I've written to serve as a starting point: https://github.com/ecorm/cbor-map-like
> 
> Here's a brief summary:
> 
> This document proposes a consolidated set of CBOR tags for map-like entities involving key-value pairs. These tags encode the following meta-data concerning map-like entities:
> 	• the homogeneity of the key and value types,
> 	• the preservation of the insertion order of the key-value pairs,
> 	• the uniqueness of the keys, and,
> 	• the major type used to encode the key-value pairs.
> My interest in CBOR stems from my work on a new C++ serialization library that can support any JSON-like encoding. This library is closed source for now, but I may be able to convince my employer to make it open source in the future.
> 
> I'm also involved with the WAMP protocol, which allows CBOR as one of its encodings.
> 
> I'm looking forward to collaborating with you and I hope that we can come to a solution that satisfies everyone's needs.
> 
> Cheers,
> Emile Cormier
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 15 Mar 2021 19:51:40 +0100

> Data Item being major type 5 should really only be used if the keys are homogeneously strings, in my opinion.

We are using a lot of integer labels with mt5, so why would we make that restriction?

Grüße, Carsten

---

From: Emile Cormier <[email-masked]>
Date: Mon, 15 Mar 2021 16:00:23 -0300

"Unique Keys: no" as zero bit was chosen so that the first tag in the set
is equivalent to no tag at all. Your point about understandability is well
taken and I will change the column heading as you suggested.

I'll expand it to 4 bits in the "Key/Value Type" section as you suggested.
Thanks!

On Mon, Mar 15, 2021 at 3:50 PM Joe Hildebrand <[email-masked]> wrote:

> Suggestion: make "Unique Keys: no" be a zero bit in the LSB, not 1, for
> ease of understanding the table.  Alternately, rename to "Allow duplicate
> keys".
>
> Overall, this feels like somewhat overkill, but solves the problem and I'd
> be fine with it if it allowed us to move on.
>
> —
> Joe Hildebrand
>
> > My interest in CBOR stems from my work on a new C++ serialization
> library that can support any JSON-like encoding. This library is closed
> source for now, but I may be able to convince my employer to make it open
> source in the future.
> >
> > I'm looking forward to collaborating with you and I hope that we can
> come to a solution that satisfies everyone's needs.
> >
> > Cheers,
> > Emile Cormier

---

From: Kio Smallwood <[email-masked]>
Date: Mon, 15 Mar 2021 19:36:49 +0000

Hi Emile, 

Thanks for enumerating all of the possibilities. I have a few thoughts: 

* Would it be worth noting which programming languages and environments
already make use of each type? For example, users of the cbor2 python
library would only see tag 128 (equivalent to major type 5) tag 129,
130, for ordered and multimaps, and 132 when inter-operating with
javascript/json. The rest would be very strange to encounter in a Python
datastructure. 

* For the Homogeneous keys/values, should we (codec implementers) assume
that the type of the first key/value encountered in the data item
determines the type of the remainder? 

Thanks, 

Kio 

On 2021-03-12 23:50, Emile Cormier wrote:

>> * the homogeneity of the key and value types,
>> * the preservation of the insertion order of the key-value pairs,
>> * the uniqueness of the keys, and,
>> * the major type used to encode the key-value pairs.
>

---

From: Joe Hildebrand <[email-masked]>
Date: Mon, 15 Mar 2021 13:44:22 -0600

> On Mar 15, 2021, at 12:51 PM, Carsten Bormann <[email-masked]> wrote:
> 

This is a consequence of my implementation that others probably don't have.  When decoding mt5, I always keep a set of [key,value] tuples until all of the items have been decoded.  Then, if the keys are all strings, I convert the tuples to a JS Object, otherwise I convert them to a Map.  If I've already converted to a Map in mt5 processing, it's too late to (for example) throw an error if there is an unexpected duplicate key.

— 
Joe Hildebrand

---

From: Emile Cormier <[email-masked]>
Date: Mon, 15 Mar 2021 17:09:35 -0300

I don't know anything about "mt5", but with my proposed tag set, you could
check for the presence of tag 132 (homegenous key) and you would know after
decoding the first key if all the key-value pairs can be safely decoded
into a JS Object. Of course, this requires that the sender "play along" and
actually bothers to use the tags.

On Mon, Mar 15, 2021 at 4:44 PM Joe Hildebrand <[email-masked]> wrote:

> This is a consequence of my implementation that others probably don't
> have.  When decoding mt5, I always keep a set of [key,value] tuples until
> all of the items have been decoded.  Then, if the keys are all strings, I
> convert the tuples to a JS Object, otherwise I convert them to a Map.  If
> I've already converted to a Map in mt5 processing, it's too late to (for
> example) throw an error if there is an unexpected duplicate key.
>
> —
> Joe Hildebrand

---

From: Joe Hildebrand <[email-masked]>
Date: Mon, 15 Mar 2021 14:21:14 -0600

Ah, I think I see the difference in implementation that others must have.  I always generically decode the data item first, *then* apply the tag transformation.  This allows me to return a generic Tag implementation if I don't support the tag, or a more-specific type or error-check if I do support the tag.

Others must do special-case decoding of the data item for each tag they support.

— 
Joe Hildebrand

> On Mar 15, 2021, at 2:09 PM, Emile Cormier <[email-masked]> wrote:
> 
> I don't know anything about "mt5", but with my proposed tag set, you could check for the presence of tag 132 (homegenous key) and you would know after decoding the first key if all the key-value pairs can be safely decoded into a JS Object. Of course, this requires that the sender "play along" and actually bothers to use the tags.
>

---

From: Emile Cormier <[email-masked]>
Date: Mon, 15 Mar 2021 18:15:11 -0300

Indeed, I try to feed bytes from the wire into its resulting data structure
as directly as humanly possible in my C++ implementation, while not having
to write decoders by hand for every possible data structure. While CBOR
itself is schema-less, our applications use CBOR (and JSON) to transfer
entities with known schemas at the application level. I can therefore skip
generating intermediate "document" trees and store the CBOR directly into
the intended data structure (this is the idea behind
https://github.com/OneNoteDev/GoldFish, which is partly inspiring my
work-in-progress C++ serialization library).

I know I could use Flat Buffers with fixed schemas, but I'd end up having
to copy everything to standard library containers unless I'm willing to
have Flat Buffers "infect" my entire application instead of remaining at
the boundary. I also like the self-describing nature of CBOR for diagnostic
purposes, plus it's easier to transcode it into JSON for web browser
clients.

On Mon, Mar 15, 2021 at 5:21 PM Joe Hildebrand <[email-masked]> wrote:

> Ah, I think I see the difference in implementation that others must have.
> I always generically decode the data item first, *then* apply the tag
> transformation.  This allows me to return a generic Tag implementation if I
> don't support the tag, or a more-specific type or error-check if I do
> support the tag.
>
> > I don't know anything about "mt5", but with my proposed tag set, you
> could check for the presence of tag 132 (homegenous key) and you would know
> after decoding the first key if all the key-value pairs can be safely
> decoded into a JS Object. Of course, this requires that the sender "play
> along" and actually bothers to use the tags.
> >
> > >> Data Item being major type 5 should really only be used if the keys
> are homogeneously strings, in my opinion.
> > >

---

From: Joe Hildebrand <[email-masked]>
Date: Tue, 16 Mar 2021 11:20:26 -0600

Your approach makes sense to me.

Is there any benefit to using map over array for your approach?  They're roughly the same on the wire.

— 
Joe Hildebrand

> On Mar 15, 2021, at 3:15 PM, Emile Cormier <[email-masked]> wrote:
> 
> Indeed, I try to feed bytes from the wire into its resulting data structure as directly as humanly possible in my C++ implementation, while not having to write decoders by hand for every possible data structure. While CBOR itself is schema-less, our applications use CBOR (and JSON) to transfer entities with known schemas at the application level. I can therefore skip generating intermediate "document" trees and store the CBOR directly into the intended data structure (this is the idea behind https://github.com/OneNoteDev/GoldFish, which is partly inspiring my work-in-progress C++ serialization library).
> 
> I know I could use Flat Buffers with fixed schemas, but I'd end up having to copy everything to standard library containers unless I'm willing to have Flat Buffers "infect" my entire application instead of remaining at the boundary. I also like the self-describing nature of CBOR for diagnostic purposes, plus it's easier to transcode it into JSON for web browser clients.
> 
>

---

From: Emile Cormier <[email-masked]>
Date: Tue, 16 Mar 2021 14:36:45 -0300

Hi Kio,

I'll add an information section on how the various tags relate to
programming language data structures. I could start with JS and C++ data
structures, and allow other folks to send or PR me the ones for other
languages.

For homogeneous key/values, it was actually my intention that the first
key/value encountered "establishes" the type for the remainder. A decoder
could reject a homogenous map where a key/value does not match the type
established by the first.

You've made me realize that the interpretation for "homogenous" could be
tricky for numeric types. For example, if the first homogenous key is a
positive integer, can the decoder assume that the following keys may also
include negative integers and floats? I'll check what it says for
homogenous arrays in https://tools.ietf.org/html/rfc8746 . It may have
already been settled there.

This also begs the question: what does "homogeneous" mean for key/value
types that are themselves arrays or maps?

Thanks for the feedback!
Emile

On Mon, Mar 15, 2021 at 4:36 PM Kio Smallwood <[email-masked]>
wrote:

> library would only see tag 128 (equivalent to major type 5) tag 129, 130,
> for ordered and multimaps, and 132 when inter-operating with

---

From: Emile Cormier <[email-masked]>
Date: Tue, 16 Mar 2021 14:52:35 -0300

The benefit of using map instead of array whenever possible is better
interoperability with other decoders that ignore the tags. For example, if
I send a map tagged 132 (unordered, homogenous, unique keys), an "agnostic"
Javascript decoder will store it in a Map or Object, and the application
will at least know it's a set of key-value pairs.

The disadvantage of this approach is obviously the inconsistency. Sometimes
it's map and sometimes it's array. The decoder needs extra logic for using
the correct major type code.

On Tue, Mar 16, 2021 at 2:20 PM Joe Hildebrand <[email-masked]> wrote:

> > Indeed, I try to feed bytes from the wire into its resulting data
> structure as directly as humanly possible in my C++ implementation, while
> not having to write decoders by hand for every possible data structure.
> While CBOR itself is schema-less, our applications use CBOR (and JSON) to
> transfer entities with known schemas at the application level. I can
> therefore skip generating intermediate "document" trees and store the CBOR
> directly into the intended data structure (this is the idea behind
> > I know I could use Flat Buffers with fixed schemas, but I'd end up
> having to copy everything to standard library containers unless I'm willing
> to have Flat Buffers "infect" my entire application instead of remaining at
> > Ah, I think I see the difference in implementation that others must
> have.  I always generically decode the data item first, *then* apply the
> tag transformation.  This allows me to return a generic Tag implementation
> if I don't support the tag, or a more-specific type or error-check if I do
> support the tag.
> >

---

From: Emile Cormier <[email-masked]>
Date: Tue, 16 Mar 2021 15:38:40 -0300

RFC8746 has this to say about homogeneous arrays:

Which CBOR data items constitute elements of the same application type is
> specific to the application.
>

I think this interpretation of "homogenous" should be the same for this
proposal.

---

From: Emile Cormier <[email-masked]>
Date: Tue, 16 Mar 2021 20:27:04 -0300

I've updated the GitHub repo with a new section describing how the tags
relate to programming language containers. I only have Javascript, Python,
and C++ there for now. I'm not fluent in Python and had to consult online
documentation. It's entirely possible I got things wrong in the Python
subsection.

I have the following new thoughts:

1. We should consider adding similar tags for lists of discrete values (not
key-value pairs). For example, the homogeneity, ordering, and uniqueness
properties could be associated with programming language lists, sets, and
multisets. I think this would add eight additional tags, for a total of 20.

2. I'd like to replace the terms "homogenous/heterogeneous" with the terms
"uniform/arbitrary" for better readability.