Subject: [Cbor] hildjj/cbor-map-entries: Explicit Map datatype for CBOR, in array format

From: Carsten Bormann <[email-masked]>
Date: Wed, 17 Feb 2021 21:02:14 +0100

Do we agree that an order-preserving map occurs often enough to warrant a 1+1 (or even 1+0?) tag?

The current proposal is 1+2.

(Any other comments?)

https://github.com/hildjj/cbor-map-entries 

Grüße, Carsten

---

From: [email-masked] (Dale R. Worley)
Date: Wed, 17 Feb 2021 22:47:26 -0500

> warrant a 1+1 (or even 1+0?) tag?

I may have missed the discussion, but do we have a clear defition of
"order-preserving"?  Naively, that seems to include every issue about
how you compare values ever asked.

Dale

---

From: [email-masked] (Dale R. Worley)
Date: Wed, 17 Feb 2021 22:58:32 -0500

> https://github.com/hildjj/cbor-map-entries 

I found it an odd read, as I couldn't figure out what the point is.  As
written, it's an alternative way to express maps, as a tag applied to an
array containing keys and values.  But what's the point?

The text starts off with "Although CBOR has support for generic Maps
(Major Type 5), some implementation languages (such as ECMAScript) have
two different types they might use to hold the information, depending on
whether all of the keys are strings or not."  And it makes sense that's
a problem to be solved.  But this document doesn't solve that, in that
neither tag-279-array nor CBOR map are constrained to have the keys be
strings, so both of them would have to be decoded into a more general
data type/structure.

Maybe I'm not read into CBOR enough to understand what is intended.  But
it seems to me that this document probably intended to specify that the
key values in a type-279-array must be strings.

Dale

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 18 Feb 2021 13:57:00 +0000

Hi Dale, 

I have made a similar proposal here:
https://github.com/Sekenre/cbor-ordered-map-spec/blob/master/CBOR_Ordered_Map.md

I've tried to explain the rationale that it is adding a straightforward
option for serializing a native data-type in Python 3 and other
languages that support order-preserving key-value maps. 

Cheers, 

Kio Smallwood 

On 2021-02-18 3:47, [email-masked] wrote:

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

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 18 Feb 2021 15:15:39 +0100

> On 2021-02-18, at 14:57, Kio Smallwood <[email-masked]> wrote:
> 
> Hi Dale,
> 
> I have made a similar proposal here: https://github.com/Sekenre/cbor-ordered-map-spec/blob/master/CBOR_Ordered_Map.md

… and here we see the danger of just “claiming” a number…

(272 is Non-UTF-8 CESU-8 string).

> I've tried to explain the rationale that it is adding a straightforward option for serializing a native data-type in Python 3 and other languages that support order-preserving key-value maps.

Yes.  And I agree with Dale that we should look a bit closer, but that is not a reason not to allocate a tag.

Grüße, Carsten

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 18 Feb 2021 14:42:36 +0000

I'll modify it to remove the claim until it moves further.

I definitely want to avoid confusion!

Kio

On 18 February 2021 14:15:39 GMT, Carsten Bormann <[email-masked]> wrote:
>> I've tried to explain the rationale that it is adding a
>straightforward option for serializing a native data-type in Python 3
>and other languages that support order-preserving key-value maps.
>

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

---

From: Alexander Pelov <[email-masked]>
Date: Thu, 18 Feb 2021 16:11:36 +0100

+1

I needed this one on many occasions

Cheers,
Alexander

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 18 Feb 2021 16:15:46 +0000

Thanks Joe! 

I really appreciate the additional input since I wasn't aware of other
languages with a similar datatype. 

I've accepted your PR and updated my README and repo commentary to
reflect the TBD status of the tag. 

Cheers, 

Kio 

On 2021-02-18 15:19, Joe Hildebrand wrote:

> PR's sent for both your repo and mine.
> 
> -- 
> Joe Hildebrand
> 
> On Feb 18, 2021, at 8:00 AM, Joe Hildebrand <[email-masked]> wrote:
> 
> Kio, I'm happy to defer to your document, since you published first.  Sorry I didn't know about it.  If you are amenable, I'll replace my doc with a pointer to yours, and send you a PR with some suggestions for JS examples.
> 
> -- 
> Joe Hildebrand
> 
> On Feb 18, 2021, at 7:42 AM, Kio Smallwood <[email-masked]> wrote:
> 
> ... and here we see the danger of just "claiming" a number...
>

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 18 Feb 2021 16:41:22 +0000

Hi Carsten, 

To answer your original question, I now know of 3 languages in common
use (Python, Ruby, ECMAScript) that have insertion-order-preserving maps
as part of their core libraries. I am happy with 1+2 tag, but shorter is
always nicer. 

Cheers, 

Kio

---

From: Laurence Lundblade <[email-masked]>
Date: Thu, 18 Feb 2021 09:48:21 -0700

This is semi-related and maybe something I’m a little confused about.

My understanding is that map keys/labels can be anything in CBOR including a map or array. This is nye impossible to write general map handling code for — code like lookup up by label and duplicate detection. They will not translate to other map data structures in other languages and serialization formats. Further, this seems like an exotic feature of little practical use (though I’m sure someone could do something very cool and clever with it for entertainment purposes).

What to do?

- Don’t standardize any IETF protocols that use exotic map keys?
- Add text to Kio’s proposal to restrict map keys to text string, byte string and integer?
- Write some warning against this somewhere?

LL

> On Feb 18, 2021, at 9:15 AM, Kio Smallwood <[email-masked]> wrote:
> 
> Thanks Joe!
> 
> I really appreciate the additional input since I wasn't aware of other languages with a similar datatype.
> 
> I've accepted your PR and updated my README and repo commentary to reflect the TBD status of the tag.
> 
> Cheers,
> 
> Kio
> 
>> — 
>>> On Feb 18, 2021, at 8:00 AM, Joe Hildebrand <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> — 
>>>> On Feb 18, 2021, at 7:42 AM, Kio Smallwood <[email-masked] <mailto:[email-masked]>> wrote:
>>>> 
>>>> On 18 February 2021 14:15:39 GMT, Carsten Bormann <[email-masked] <mailto:[email-masked]>> wrote:
>>>> 
>>>> 
>>>> On 2021-02-18, at 14:57, Kio Smallwood <[email-masked] <mailto:[email-masked]>> wrote:
>>>> 
>>>> Hi Dale,
>>>> 
>>>> I have made a similar proposal here: https://github.com/Sekenre/cbor-ordered-map-spec/blob/master/CBOR_Ordered_Map.md <https://github.com/Sekenre/cbor-ordered-map-spec/blob/master/CBOR_Ordered_Map.md>
>>>> 
>>>> [email-masked] <mailto:[email-masked]>
>>>> https://www.ietf.org/mailman/listinfo/cbor <https://www.ietf.org/mailman/listinfo/cbor>
>>>> 
>>>> -- 
>>>> [email-masked] <mailto:[email-masked]>
>>>> https://www.ietf.org/mailman/listinfo/cbor <https://www.ietf.org/mailman/listinfo/cbor>

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 07:56:05 -0700

And, after a couple of hours of sleep, I realized that of course order matters for my use case. 

— 
Joe Hildebrand

> On Feb 18, 2021, at 12:13 AM, Joe Hildebrand <[email-masked]> wrote:
> 
> (Note that I just accepted a PR from Carsten, so the text has changed ever so slightly)
> 
> The main reason I want a type like this isn't to persevere order, but to round-trip Map instances from JavaScript, through CBOR, and back to JavaScript.  I want to ensure that they end up a Map again, even if they have all-string keys.  Node-cbor currently uses a JS Object if all of the keys are strings, and falls back to a Map if it detects anything other than a string.  Another choice would have been to always coerce CBOR map keys into strings, but that is a little difficult to do in a non-surprising way with structured keys.
> 
> That said, order doesn't hurt my use case, and if someone else wants that, great.
> 
> More comments, questions and pull requests welcome.
> 
> — 
> Joe Hildebrand
> 
>> On Feb 17, 2021, at 8:58 PM, Dale R. Worley <[email-masked]> wrote:
>>

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 08:00:20 -0700

— 
Joe Hildebrand

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 08:19:30 -0700

— 
Joe Hildebrand

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 09:18:21 -0700

Thanks, I've replaced my doc with a pointer to yours. 

— 
Joe Hildebrand

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 09:59:22 -0700

I agree that exotic map keys (with exactly your definition of exotic) are almost-always bad protocol design.  There are other uses of CBOR than wire protocols, however.

— 
Joe Hildebrand

> On Feb 18, 2021, at 9:48 AM, Laurence Lundblade <[email-masked]> wrote:
>

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 00:13:44 -0700

— 
Joe Hildebrand

---

From: Michael Richardson <[email-masked]>
Date: Thu, 18 Feb 2021 12:39:15 -0500

> a 1+1 (or even 1+0?) tag?

1+1 definitely.
1+0? maybe.

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Michael Richardson <[email-masked]>
Date: Thu, 18 Feb 2021 12:43:13 -0500

> My understanding is that map keys/labels can be anything in CBOR
    > including a map or array.

yes, that's allowed, but probably unwise to write into a CBOR Protocol.

    > This is nye impossible to write general map
    > handling code for — code like lookup up by label and duplicate
    > detection. They will not translate to other map data structures in
    > other languages and serialization formats.

    > Further, this seems like an
    > exotic feature of little practical use (though I’m sure someone could
    > do something very cool and clever with it for entertainment purposes).

    > What to do?

I think that you got it right in QCBOR: you declare what you support, and
that's it.

    > - Don’t standardize any IETF protocols that use exotic map keys?

I would expect that anyone that tried to do this would get pushback.
So, we lead by example.

Such a hard-to-implem,ent protocol would probably be a terrible failure.
We can't really keep people that are intent on shooting their feet from
obtaining some kind of foot canon.

    > - Add text to Kio’s proposal to restrict map keys to text string, byte string

no, it doesn't belong there.

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 18 Feb 2021 18:52:33 +0100

> On 2021-02-18, at 17:48, Laurence Lundblade <[email-masked]> wrote:
> 
> My understanding is that map keys/labels can be anything in CBOR including a map or array.

Yes.  

Or a Tag!

> - Don’t standardize any IETF protocols that use exotic map keys?

Yes.

(I don’t know what’s exotic, but on the implementation side generally any data structure that is mutable is a bit ugly as a map key.  E.g., languages where strings are mutable already need to jump through extra hoops here.  But, e.g., C++ handles maps with non-trivial keys just fine; these are certainly not exotic at all to a C++ programmer.)

> - Add text to Kio’s proposal to restrict map keys to text string, byte string and integer?

No.

(E.g., think what https://tools.ietf.org/id/draft-ietf-cbor-tags-oid-02.html#name-distinguished-name-in-cbor- would look like without tag factoring.)

> - Write some warning against this somewhere?

Should be obvious to anyone skilled in the art :-)

(The reason CBOR can do this is that many platforms can do it — so not supporting it in the format would have made CBOR less useful for native code/protocols for specific platforms.)

Grüße, Carsten

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 18 Feb 2021 19:51:08 +0000

I can give an example in Python... 

Tuples (among other types) with immutable values can be used as dict
keys: 

   {('a','b'): 'value'} 

But when serialized the tuple is converted to a CBOR array: 

A1               # map(1)
   82            # array(2)
      61         # text(1)
         61      # "a"
      61         # text(1)
         62      # "b"
   65            # text(5)
      76616C7565 # "value" 

Therefore the cbor2 decoder implementation has to know that it is being
called in a context where a hashable datatype is required and in this
case return a Tuple instead of the normal mutable List object. 

The test cases for "exotic map keys" can be found here: 

https://github.com/agronholm/cbor2/blob/818ba624df535ac7cd300aaa6fb963a83b3656e0/tests/test_encoder.py#L457

The intended use case is not for a robust wire protocol, since it would
as you say make interoperability extremely difficult, but it does allow
flexible serialization of complex objects. The Python Pickle module is
the model we are following. 

https://docs.python.org/3/library/pickle.html 

Cheers, 

Kio 

On 2021-02-18 17:52, Carsten Bormann wrote:

>> This is semi-related and maybe something I'm a little confused about.
>> 
>> - Don't standardize any IETF protocols that use exotic map keys?
> 
> Yes.
> 
> (I don't know what's exotic, but on the implementation side generally any data structure that is mutable is a bit ugly as a map key.  E.g., languages where strings are mutable already need to jump through extra hoops here.  But, e.g., C++ handles maps with non-trivial keys just fine; these are certainly not exotic at all to a C++ programmer.)
> 
>> - Add text to Kio's proposal to restrict map keys to text string, byte string and integer?
> 
> No.
> 
> (The reason CBOR can do this is that many platforms can do it -- so not supporting it in the format would have made CBOR less useful for native code/protocols for specific platforms.)
> 
> Grüße, Carsten
>

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 12:58:23 -0700

Oh, that reminds me.  If https://github.com/tc39/proposal-record-tuple progresses a little bit more, I'm also going to be interested in explicit mutable and immutable tags.

Putting an immutable tag around a map key would make Kio's example very clear.

— 
Joe Hildebrand

> On Feb 18, 2021, at 12:51 PM, Kio Smallwood <[email-masked]> wrote:
> 
> Tuples (among other types) with immutable values can be used as dict keys:
> 
>    {('a','b'): 'value'}
> 
> Therefore the cbor2 decoder implementation has to know that it is being called in a context where a hashable datatype is required and in this case return a Tuple instead of the normal mutable List object.
> 
> The intended use case is not for a robust wire protocol, since it would as you say make interoperability extremely difficult, but it does allow flexible serialization of complex objects. The Python Pickle module is the model we are following.
>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 18 Feb 2021 23:44:17 +0100

> On 18. Feb 2021, at 20:58, Joe Hildebrand <[email-masked]> wrote:
> 

The structures created by record-tuple are deeply immutable, so the below may not be relevant for your use case.

How would mutable and immutable interact?
I assume an immutable tag make its whole content immutable.
Can you get back using a nested mutable?

What is the default state at the top?

Grüße, Carsten

---

From: Joe Hildebrand <[email-masked]>
Date: Thu, 18 Feb 2021 17:06:44 -0700

> How would mutable and immutable interact?

Pick one for any given item; if you use both, it might be well-formed but it's not valid.  The tag applies to everything nested inside.

> I assume an immutable tag make its whole content immutable.

Yes, I expect.   Both tags also probably only applies to Maps and Arrays.

> Can you get back using a nested mutable?

Immutable can be nested inside mutable, but not the other way around, I think.  I think I'd just ignore it rather than having it be an error, but I would be easy to talk out of that approach.

> What is the default state at the top?

Implementation-defined?  I might make it an option once I have access to immutable types.

— 
Joe Hildebrand

---

From: [email-masked] (Dale R. Worley)
Date: Fri, 19 Feb 2021 22:43:07 -0500

> how you compare values ever asked.

Ha-ha-ha!  I see my mistake...

If you had said "ordered map", I would think "a set of key/value pairs
in a particular order".

But if you say "order-preserving map", my mathematical training kicks in
and I think "a map F where for every a less than b, F(a) is less than
F(b)".  So for an *order-preserving map*, there must be a defined sense
of comparison between keys, and also a defined sense of comparison
between values!

Dale

---

From: [email-masked] (Dale R. Worley)
Date: Fri, 19 Feb 2021 22:54:08 -0500

My previous message on this was sent at the end of a long day, and I
didn't make my point clearly.

The key idea of the proposed tag is given in the former contents of the
README.md that was referenced:

    Although CBOR has support for generic Maps (Major Type 5), some
    implementation languages (such as ECMAScript) have two different
    types they might use to hold the information, depending on whether
    all of the keys are strings or not.  This makes round-tripping
    between CBOR and native representations more difficult, and adds
    complexity in a generic decoder.

This proposal says that there will be two ways of representing maps,
major type 5, and tag 279 plus major type 4.  However, if you read the
README.md carefully, it does not assert any difference between what is
allowed to be encoded with them.  That is, it does not state which, if
either, of these representations constrains the key values to be string.
That is, it describes a need but does not provide a solution.

Now I'm pretty sure that what is *intended* is that maps encoded as tag
279 plus major type 4 require the keys to be strings.  Though it's
conceivable that it intends that keys in major type 5 be strings; that
would fix the described problem as well.

Dale

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 20 Feb 2021 07:34:07 +0100

> would fix the described problem as well.

I don’t think that’s what the current discussion is about.
(Actually, tag 275 was registered for just that.)

Grüße, Carsten