Subject: Re: [Cbor] A CBOR tag for alternatives/unions, request for comments

From: Carsten Bormann <[email-masked]>
Date: Wed, 23 Feb 2022 14:16:14 +0100

I finally got around to integrate the proposal by Duncan Coutts and Michael Peyton Jones to allocate tags for enumerated alternative data items into notable-tags.

https://www.ietf.org/archive/id/draft-bormann-cbor-notable-tags-06.html#name-enumerated-alternative-data

I took the liberty to suggest tag 101 (‘e’) for the extended case.
I also made the cases non-overlapping, as this simplifies deterministic encoding (and interop testing in general).

Current state of tag allocation:
range  used     %                 free                total
0 1+0    12 50.00                   12                   24
1 1+1    62 26.72                  170                  232
2 1+2    45  0.07                65235                65280
3 1+4     3  0.00           4294901757           4294901760
4 1+8     2  0.00 18446744069414584318 18446744069414584320

If we have time in the CBOR meeting today (very likely) and you have time and comments, we could complete the discussion and ask IANA to register.

Coordinates of the CBOR meeting are below.
You’ll need an IETF datatracker account to participate; you can do that here:

https://datatracker.ietf.org/accounts/create/

I’m out of English words to apologize for my tardy treatment of this matter (and for the late notice of the meeting in 100 minutes).

Grüße, Carsten

The next CBOR WG Virtual Meeting is this Wednesday, 23 Feb, at 15:00
UTC.  Information for this meeting is here:

Datatracker: https://datatracker.ietf.org/meeting/interim-2022-cbor-04/session/cbor
Notes: https://notes.ietf.org/notes-ietf-interim-2022-cbor-04-cbor
Meetecho: https://meetings.conf.meetecho.com/interim/?short=9d38d4c9-cf9e-48c3-bc25-97b025698ec0

---

From: Richter, Jörg <[email-masked]>
Date: Wed, 23 Feb 2022 14:13:19 +0000

Some time ago we had a discussion to integrate an error-tag. (draft-richter-cbor-error-tag-01.txt)

You made the suggestion to use tag 101 for it. Even if it was never finalized, we still have the need for such a tag.

There are also various other tags we need, including time of day, time zone, currency. These also already have proposed tag numbers that have never been registered anywhere. But I don’t know what I can do to have these tags registered.

- Jörg

-----Original Message-----
From: Carsten Bormann <[email-masked]> 
Sent: Wednesday, February 23, 2022 2:16 PM
To: Michael Peyton Jones <[email-masked]>; Duncan Coutts <[email-masked]>; [email-masked]
Cc: Jared Corduan <[email-masked]>; Alexander Byaly <[email-masked]>
Subject: Re: [Cbor] A CBOR tag for alternatives/unions, request for comments

Grüße, Carsten

The next CBOR WG Virtual Meeting is this Wednesday, 23 Feb, at 15:00 UTC.  Information for this meeting is here:

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

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 23 Feb 2022 15:20:18 +0100

On 2022-02-23, at 15:13, Richter, Jörg <[email-masked]> wrote:
> 
> You made the suggestion to use tag 101 for it.

Ouch, bad memory on my side, plus propensity to drop my cookies.
So I retract my proposal to move the extended tag for enums to 101 (‘e’).

> Even if it was never finalized, we still have the need for such a tag.

Yes.  Maybe we should add a reference relating this to RFC 7807, integrate it into notable-tags, and ask IANA to register it.

Grüße, Carsten

---

From: Emile Cormier <[email-masked]>
Date: Wed, 23 Feb 2022 10:34:50 -0400

Is there any consideration into how such tags and their associated datum be
transcoded to JSON, without loss of information?

On Wed, Feb 23, 2022 at 9:16 AM Carsten Bormann <[email-masked]> wrote:

> I finally got around to integrate the proposal by Duncan Coutts and
> Michael Peyton Jones to allocate tags for enumerated alternative data items
> into notable-tags.
>
>
> I also made the cases non-overlapping, as this simplifies deterministic
> encoding (and interop testing in general).
>
> If we have time in the CBOR meeting today (very likely) and you have time
> and comments, we could complete the discussion and ask IANA to register.
>
> I’m out of English words to apologize for my tardy treatment of this
> matter (and for the late notice of the meeting in 100 minutes).
>
> Grüße, Carsten
>
>
> Datatracker:
> https://datatracker.ietf.org/meeting/interim-2022-cbor-04/session/cbor
> Meetecho:
> https://meetings.conf.meetecho.com/interim/?short=9d38d4c9-cf9e-48c3-bc25-97b025698ec0
>
>

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 23 Feb 2022 15:48:22 +0100

On 2022-02-23, at 15:34, Emile Cormier <[email-masked]> wrote:
> 
> Is there any consideration into how such tags and their associated datum be transcoded to JSON, without loss of information?

I’m not currently proposing to standardize this, but the cbor diagnostic tools support a transform to tunnel CBOR data items through JSON [0]:

$ echo "122(h'1234')" | diag2cbor.rb | cbor2json.rb -j
{
  "@@!t122": {
    "@@!b": "EjQ"
  }
}

This works by hijacking JSON object keys starting with @@!; I’m not sure the code handles all cases so we have achieved full transparency yet, but that is a SMOP [1].

Grüße, Carsten

[0]: https://github.com/cabo/cbor-diag/blob/master/lib/cbor-transform-j.rb
[1]: SMOP = Small matter of programming

---

From: Emile Cormier <[email-masked]>
Date: Wed, 23 Feb 2022 11:06:36 -0400

On Wed, Feb 23, 2022 at 10:48 AM Carsten Bormann <[email-masked]> wrote:

> I’m not currently proposing to standardize this, but the cbor diagnostic
> tools support a transform to tunnel CBOR data items through JSON [0]:
>
> This works by hijacking JSON object keys starting with @@!; I’m not sure
> the code handles all cases so we have achieved full transparency yet, but
> that is a SMOP [1].
>
> Grüße, Carsten
>

I was thinking something as simple as:

[<alt_index>, <value>]

where <alt_index> is a JSON number and <value> is the datum transcoded to
JSON. However, transcoding this back to CBOR would be lossy without any
other context.

---

From: chrysn <[email-masked]>
Date: Wed, 23 Feb 2022 17:09:49 +0100

Hello Carsten,

On Wed, Feb 23, 2022 at 02:16:14PM +0100, Carsten Bormann wrote:
> If we have time in the CBOR meeting today (very likely) and you have
> time and comments, we could complete the discussion and ask IANA to
> register.

I think the text should caution the user to say something about the
alternative number stability, maybe extending the Semantics section like
this:

| Protocols that use these tags should consider and document two factors
| that influence an alternative's interpretation:
| 
| * Postion. In some protocols, the meaning of an enumerated alternative
|   will depend on the location in the data item surrounding it. This is
|   especially true of protocols that incorporate other protocols.
| 
| * Stability. Whereas interchange protocols are expected to specify
|   semantics for alternatives in a future-proof way, other use cases
|   (such as debug information or crash recovery) may use alternatives
|   whose meaning is only stable within a software release, or even only
|   for a single build.

BR
Christian

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 23 Feb 2022 17:10:29 +0100

On 2022-02-23, at 16:55, Michael Peyton Jones <[email-masked]> wrote:
> 
> I do think we would prefer to keep the overlapping encoding. Many other kinds of CBOR encodings have redundancy, starting right from the basics with the encoding of numbers.

Yes.  In 2013, for a while I was hoping to fix this for the entirety of CBOR (like we did in CoAP), but was advised that was too radical.  There also was the occasional use case for non-preferred encoding.

But I don’t think we are out there actively creating more of these cases.

> We believe that not only is this approach consistent, but it's actually helpful: it allows users to decide whether they care more about flexibility or regularity.

Well, in the non-overlapping approach, they get both! :-)

> If you want, you *can* just encode everything with the long form and not worry about the compact form. This simplicity is sometimes helpful.

I think that spending two ifs in the encoder is OK here.
(The decoder will need to handle all cases anyway, so there is no advantage.)

> Of course, we can (and should) require that the canonical version be the most compact.

Which is the case when we do non-overlapping encodings.

Grüße, Carsten

(Leaving the rest of the message intact as that is still in some moderator queue.)

> 
> Best wishes,
> Michael
> 
> On Wed, 23 Feb 2022 at 15:06, Emile Cormier <[email-masked]> wrote:
> where <alt_index> is a JSON number and <value> is the datum transcoded to JSON. However, transcoding this back to CBOR would be lossy without any other context.
> 
> 
> -- 
> 
> Michael Peyton Jones
> Software Engineering Lead | London, UK
> 
> Website: www.iohk.io
> Skype: michael.s.pj
> Twitter: @mpeytonjones
> PGP Key ID: 29F64616
> 
>  
> 
>    
> 
> 
> This e-mail and any file transmitted with it are confidential and intended solely for the use of the recipient(s) to whom it is addressed. Dissemination, distribution, and/or copying of the transmission by anyone other than the intended recipient(s) is prohibited. If you have received this transmission in error please notify IOHK immediately and delete it from your system. E-mail transmissions cannot be guaranteed to be secure or error free. We do not accept liability for any loss, damage, or error arising from this transmission

---

From: Michael Peyton Jones <[email-masked]>
Date: Wed, 23 Feb 2022 15:55:02 +0000

I do think we would prefer to keep the overlapping encoding. Many other
kinds of CBOR encodings have redundancy, starting right from the basics
with the encoding of numbers.

We believe that not only is this approach consistent, but it's actually
helpful: it allows users to decide whether they care more about flexibility
or regularity. If you want, you *can* just encode everything with the long
form and not worry about the compact form. This simplicity is sometimes
helpful.

Of course, we can (and should) require that the canonical version be the
most compact.

Best wishes,
Michael

On Wed, 23 Feb 2022 at 15:06, Emile Cormier <[email-masked]>
wrote:

>> [0]:
>> https://github.com/cabo/cbor-diag/blob/master/lib/cbor-transform-j.rb

-- 

*Michael Peyton Jones*

Website: www.iohk.io <http://iohk.io>
Skype: michael.s.pj
Twitter: @mpeytonjones
PGP Key ID: 29F64616

 <http://iohk.io>

 <https://twitter.com/InputOutputHK> 
<https://github.com/input-output-hk> 
<https://www.linkedin.com/company/input-output-global>

This e-mail and any file transmitted with it are confidential and intended
solely for the use of the recipient(s) to whom it is addressed.
Dissemination, distribution, and/or copying of the transmission by anyone
other than the intended recipient(s) is prohibited. If you have received
this transmission in error please notify IOHK immediately and delete it
from your system. E-mail transmissions cannot be guaranteed to be secure or
error free. We do not accept liability for any loss, damage, or error
arising from this transmission

---

From: Michael Richardson <[email-masked]>
Date: Wed, 23 Feb 2022 18:30:38 -0500

{why haven't we adopted this document yet?}

Hi, I've reviewed section 9 of notable-tags-06.
I raised a minor PR: https://github.com/cabo/notable-tags/pull/1
because I had to stare at the [uint,value] part really hard before I
understood things.  Part of the issue is that the "value" in the previous two
cases was just "obvious", and then I couldn't understand what it meant in the
third case.

I understood from the meeting this morning that tag 101 'e', is not actually
available.  But, actually it looks like it is according to IANA.org.
Or was it that another draft wanted it?
How about 'x' (NOPE) 'X' YES. 'u' YES.
https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml#cbor-tags

I think that the document might explain why we optimize the first 7 (0..6),
rather than the first 3 or 5 or 9.  Are the next 128 worth it?
I wonder if there are more than 7, are there typically more 100s?
If it turns out that 9 is the sweet spot, I'd be okay with more 1+1
and no 1+2.  I don't have any data on this.
I wonder if Michael, Duncan, Jared or Alexander do?

I agree with the discussion that tag 101 could just encode 0..x
rather than uint+128.  I think that the simpler encoder might be worth it
here.  Particularly in some cases where I suspect which ones are the lower
numbered onces might not be known until later, and some code wants to come
back and fill in the alternatives afterwards, having left 1+4 for the uint or
something like that.

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

---

From: Michael Richardson <[email-masked]>
Date: Wed, 23 Feb 2022 18:31:21 -0500

Michael Peyton Jones <michael.peyton-jones=[email-masked]> wrote:
    > helpful: it allows users to decide whether they care more about
    > flexibility or regularity. If you want, you *can* just encode
    > everything with the long form and not worry about the compact
    > form. This simplicity is sometimes helpful.

+1

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 24 Feb 2022 00:52:47 +0100

>> form. This simplicity is sometimes helpful.

Sorry, can’t live with that.

As a protocol designer, I carry a deep conviction that when you create different ways to do the same thing, you'll pay dearly for that.  (Look at the discussion about preferred/deterministic encoding in RATS/COSE.  Duuh.)

As there is no strong (technical or political) reason to do this here, I would regard creating different ways to do the same thing as a professional error.

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 24 Feb 2022 01:06:01 +0100

> {why haven't we adopted this document yet?}

So it’s current author can munge it more freely, instead of waiting for a WG direction to form.
(You can always do a hostile adoption, though ;-)

> cases was just "obvious", and then I couldn't understand what it meant in the

I just commented on the specific words.

> https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml#cbor-tags

(NOPE = tag 120 ‘x’ is already in use.)
I’ll leave that choice to the proposers…

> rather than the first 3 or 5 or 9.  Are the next 128 worth it?

We could skip the whole 1+2 tag range if we think the 24 1+1+1 cases from was-102 are enough of an expansion.
But then we still have lots of 1+2 tags (0.07 % in use right now), if these actually are useful.

I can’t really imagine more than 31 cases in one alternative being used very often, but then I’d like to hear from the people who actually use this.

> I wonder if Michael, Duncan, Jared or Alexander do?

Yes, we need a PDF (probability distribution function) :-)
(Well, really, some intuition about that.)

My hunch is that this is going to be approximately Zipf’s law, and that means the first 4 or 5 are really important, and then it goes down, but slowly. 

> back and fill in the alternatives afterwards, having left 1+4 for the uint or

See my previous message.

Grüße, Carsten

---

From: Michael Peyton Jones <[email-masked]>
Date: Thu, 24 Feb 2022 11:30:47 +0000

I don't think we have any data on how common different number of
alternatives are, but we do have a large amount of experience writing code
in functional programming languages, which are one of the target use cases
for these tags.

The argument for going up to 8 alternatives in the most compact range is
simple:
- As computer scientists, we like to round things to powers of 2 :)
- Data types with more than 4 alternatives are common, so that is fewer
than we would like.
- Data types with more than 8 alternatives are rare.

Ergo: 8 should be enough for most purposes.

The argument for the second range is perhaps less clear. I could see the
argument for not including it at all. However, since the tag space is
comparatively more plentiful, it seemed cheap to use a modest amount of
them for this purpose. Again, the argument for the number of tags is from
experience: data types with more than 100 alternatives are *vanishingly*
rare, and likely machine-generated if they exist at all.

Best wishes,
Michael

On Thu, 24 Feb 2022 at 00:06, Carsten Bormann <[email-masked]> wrote:

> I can’t really imagine more than 31 cases in one alternative being used
> very often, but then I’d like to hear from the people who actually use this.
>
> My hunch is that this is going to be approximately Zipf’s law, and that
> means the first 4 or 5 are really important, and then it goes down, but
> slowly.
>

-- 

*Michael Peyton Jones*

 <http://iohk.io>

---

From: Christian Amsüss <[email-masked]>
Date: Thu, 24 Feb 2022 13:20:13 +0100

Hello Michael, Carsten,

putting my designated-expert hat on because this will sooner or later
reach me through the review that'll be asked for the 24-32767 range.

> Current state of tag allocation:

this is asking 6 (in discussion with Michael, 8) out of the ~170
remaining short tags. Chunk allocations are not unheard of, and it's not
a particularly large chunk, but given that this is not a case coming
from the constrained or high-volume applications that CBOR was designed
for, I'd like to confirm:

Does it, for the applications expecting to use this, make a noticable
difference whether a 1+1 or a 1+2 tag is used?

(The difference is likely most pronounced on alternatives without actual
payload; expressing the two values of `Either () ()` (if I'm getting this
right; in Rust I might say `Result<(), ()>`) would take 4 byte each vs.
3 byte each for the full value including the tagged nil / empty-tuple).

If not, I'd suggest that, say, 128 tags could be requested from 1+2,
leaving the 1+1+1+(2..) version for the unbounded range.

If so, please provide some note about how this does make a difference,
which I can refer to when eventually reviewing the entry.

BR
c

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 24 Feb 2022 14:48:57 +0100

> […] this is not a case coming
> for, […]

I’m not so sure about the constrained space:
Rust has a strong ascent as the language of choice in the constrained space.
Rust also has a strong enum system.

(Rust is also of interest in the high-volume space.)

Grüße, Carsten

---

From: Michael Peyton Jones <[email-masked]>
Date: Thu, 24 Feb 2022 14:12:43 +0000

This is a great question.

> The difference is likely most pronounced on alternatives without actual
payload

More generally, the tag overhead is important in cases where the space used
for tags is significant relative to the space used for the payloads. The
case where there is no payload is one example.

Another example that's interesting is where there is a lot of *structure*
to the data. If you'll permit me a toy example, suppose we have a balanced
binary tree of numbers. In Haskell, the data type definition would look
like this:

data Tree = Leaf Int | Node Tree Tree

If we encode such a structure using the proposed alternative tags ('0' for
'Leaf' and '1' for 'Node') then we will have 2n-1 nodes for n entries in
the tree, and hence that many tags. If the entries themselves are not
enormous, then the proportion of the total space usage devoted to the tags
can become significant! We have encountered this problem in real life.

Putting it another way: some tags are useful, but occur infrequently. There
is little point in optimizing their space usage. However, we expect that
the users who *do* use these tags will use them a *lot*, and so optimizing
them provides a decent benefit.

Best wishes,
Michael

-- 

*Michael Peyton Jones*

 <http://iohk.io>

---

From: Michael Richardson <[email-masked]>
Date: Thu, 24 Feb 2022 09:23:28 -0500

Michael Peyton Jones <[email-masked]> wrote:
    > of them for this purpose. Again, the argument for the number of tags is
    > from experience: data types with more than 100 alternatives are
    > *vanishingly* rare, and likely machine-generated if they exist at all.

Like, a code path for each CBOR tag value :-)

---

From: Michael Richardson <[email-masked]>
Date: Thu, 24 Feb 2022 09:27:12 -0500

> difference whether a 1+1 or a 1+2 tag is used?

...

    > leaving the 1+1+1+(2..) version for the unbounded range.

I would also ask this question.

Carsten Bormann <[email-masked]> wrote:
    >> […] this is not a case coming from the constrained or high-volume
    >> applications that CBOR was designed for, […]

    > I’m not so sure about the constrained space: Rust has a strong ascent
    > as the language of choice in the constrained space.  Rust also has a
    > strong enum system.

    > (Rust is also of interest in the high-volume space.)

As a Rustacian, I'm not sure it matters 1+1 vs 1+2.
It's not about Rust, it's about how/where this serialization is going to be
stored/transfered.
I don't object to 7/8 1+1 though, it's just not clear to me that it is a huge win.