Re: [Cbor] Maps: Need for additional compactness?

[Emile Cormier <[e-mail]>]

A quick search reveals that the MList encoding seems to be favored by
various JSON libraries when serializing multimaps. This allows the use of
JSON objects when string keys are used:

{"aaa", [1, 2], "bbb", [3]}

where 1 and 2 are distinct values under the duplicate "aaa" JSON key.

If CBOR were to adopt the same MList convention, then transcoding from CBOR
multimaps to JSON would be trivial. The overhead of one byte per multimap
key seems like an acceptable price to pay for better simplicity and
compatibility with JSON.

In the case of non-string keys I would personally prefer transcoding a CBOR
multimap to a JSON array of pairs:

[[100, [101, 102], [200, [201]]

where 101 and 102 are distinct values under the duplicate 100 key.

Before deciding anything, perhaps it would be a good idea to survey how
existing JSON libraries deal with maps that are not traditional JS objects
with unique string keys. This would minimize the "impedance mismatch"
between CBOR and JSON.

Cheers,
Emile Cormier

On Tue, Jun 15, 2021 at 6:00 PM Emile Cormier <[e-mail]>
wrote:

> Hi Carsten,
>
> Sorry for the late reply. Your message was flagged as spam for some reason
> and I just found it recently.
>
> Thanks for clarifying the OEMLists; they make sense to me now. My example
> with the superfluous brackets was taken directly from your slides, so you
> may want to consider fixing those slides if you plan on reusing them.
>
> I'm not sure which would be easiest to decode between Dittolists and
> OEMLists. With Dittolists, a SAX-like parser either has to "remember" the
> last key (which is not trivial if the key is of arbitrary type), or it has
> to look ahead after the value following the key to see if there's a Ditto
> special value.
>
> What vexes me for both the Dittolists and OEMLists is how I'm supposed to
> transcode them into JSON in a multi-encoding environment, such as a WAMP
> router (https://wamp-proto.org/). Consider the case where a JSON peer
> would expect a multimap to be in the [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]]
> form with repeated keys. My transcoder would therefore have to memorize
> each inbound CBOR multimap key in case it needs to be repeated in the
> output JSON array. I would have to store the keys in some sort of DOM
> tree-like structure, because keys can be arrays or maps. This would ruin
> the simplicity of my current CBOR-to-JSON transcoder.
>
> On the other hand, if I assume that a JSON peer understands OEMLists, then
> I can simply transcode each sub-entity of a CBOR OEMList as-is without
> having to memorize anything.
>
> I'll do some research on how multimaps are expected to be serialized in
> the Javascript world. I'm guessing that there's really no consensus.
>
> Cheers,
> Emile Cormier
>
> On Sat, Jun 12, 2021 at 12:25 PM Carsten Bormann <[e-mail]> wrote:
>
>> Hi Emile,
>>
>> > The MList encoding becomes a pessimization if there are few duplicate
>> keys and a large number of key-value pairs. It might not be so bad to
>> assume that keys tend to be generally short - they are often things like
>> database IDs.
>> >
>> > The OMList encoding not allowing array values seems like a showstopper
>> to me.
>>
>> Yes, both MList and OMList are showing intermediate steps; I think only
>> OEMList would be worth defining tags for.
>>
>> > For OEMList, I'm not clear on this part:
>> >
>> > So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]] becomes [“aaa”,
>> [1, 2], “bbb”, 3, [“ccc”, [[4]]]]
>>
>> There are some spurious brackets here.  I think this should be:
>>
>> [“aaa”, [1, 2], “bbb”, 3, “ccc”, [[4]]]
>>
>> Basically the idea is:
>>
>> Packing:
>> — For keys with only one value:
>>   — if that value is not an array, use the value
>>   — if that value *is* an array, enclose it into an array (what you call
>> “singleton”).
>> — for keys with more than one value:
>>   — enclose all the values into a single array
>> Unpacking:
>> — for values that are not an array: use that as the single value for the
>> key.
>> — for values that are an array: use each element of that array as values
>> for the key.
>>
>> > Is the resulting singleton array [“ccc”, [[4]]] used as an indicator so
>> that the decoder interprets [[4]] as the array [4] to be associated with
>> the key "ccc”?
>>
>> No.  Any outer array is always removed when unpacking, regardless of how
>> many elements are in there.
>>
>> > If so, how is the decoder supposed to distinguish this from an array
>> key in heterogeneous maps? This problem is more obvious if you change the
>> example to this:
>> >
>> > [[“aaa”, 1], [“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, [1,
>> 2], [“bbb”, [[3]]], “ccc”, 4]
>> >
>> > and a decoder interprets this as:
>> > Key,     Value
>> > "aaa",    1
>> > "aaa",    2
>> > [“bbb”, [[3]]],    "ccc"
>> > 4,    <missing value>
>>
>> Yes, doesn’t work with those superfluous brackets.  See above.
>>
>> > It seems to me the only way to avoid the possible pessimization of
>> MList, while also avoiding ambiguities with keys/values that can themselves
>> be arrays/maps, is to introduce a new CBOR special value (or "abuse" CBOR
>> break) to indicate the "shared key" special case. This has the disadvantage
>> that it can't be directly transcoded to JSON.
>>
>> I think OEMLists work well as described above.
>>
>> > 1. For something like OEMList, when encoding a multimap, an encoder
>> needs to look ahead to see if there are multiple values associated with the
>> same key.
>>
>> Yes.  I haven’t talked about Dittolists yet.
>>
>> [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]]
>> becomes
>> [“aaa”, 1, *ditto*, 2, “bbb”, 3, “ccc”, [4]]
>>
>> *ditto* might be a simple value we allocate specifically for this (one
>> byte), e.g., simple(16).
>>
>> The gain of a dittolist then is the (n-1)*(sizeof(key)-1) for a key used
>> n times.
>> The gain of an OEMList is (n-1)*sizeof(key)-1, but then there is a loss
>> of one byte for each array value that comes with a key that is used only
>> once.
>> Which of these is better depends on the use case, but we are talking
>> about adding or removing single bytes for certain cases.
>>
>> Dittolists are definitely easier to stream, and I also think easier to
>> implement (no special cases for array values).
>>
>> In summary, to me it seems we might want to add OEMLists, Dittolists,
>> both, or none of them.
>>
>> Grüße, Carsten
>>
>>