CborElement API

[fzhinkin]

There's a proposal by @JesusMcCloud to add an API to process CBOR documents without mapping them directly to user defined Kotlin objects, similar to what JsonElement is for JSON: #3036

The goal of this discussion is to find solutions to open design issues, the implementation of which will lead to the integration of #3036.

Motivation

See #3036 and referred issues for more details on the motivation, but in general, some protocols built on top of CBOR (like COSE) could not be easily mapped to an object model compatible with what kotlinx-serialization-cbor already supports.

To be more precise, COSE defines a CBOR-protocol, where:

• Messages encoded into a heterogenous CBOR-array, where element at each index has a predefined meaning
• Every message consists of a header common to all algorithms, followed by an algorithm–specific part
• There are several ways to decide on how a message should be parsed (i.e., to figure out the type of a message to correctly parse the algorithm-specific suffix):
  • By knowing what messages you’re receiving
  • By checking a mime-type of a received message (if one is present)
  • By reading a CBOR-tag of the message (COSE assign specific tag values to particular message types, see table 1)
    • Note that we don’t support polymorphic serializers where the object's tag works as the discriminator, do we?
• COSE uses two different ways to encode algorithm parameters (as part of its Headers section):
  • A few parameters are encoded as an array
  • They are followed by a map from a label representing a parameter to a parameter value

Parameter values within a header map are polymorphic, for instance:

  Generic_Headers = (
       ? 1 => int / tstr,  ; algorithm identifier
       ? 2 => [+label],    ; criticality
       ? 3 => tstr / int,  ; content type
       ? 4 => bstr,        ; key identifier
       ? 5 => bstr,        ; IV
       ? 6 => bstr,        ; Partial IV
       ? 7 => COSE_Signature / [+COSE_Signature] ; Counter signature
   )

val headers: Map<Int, CborElememnt>
val ct = headers[3]
ct is CborString || ct is CborInt

Here, the algorithm identifier is either an int, or a text string. The COSE implies that a CBOR data item’s header will work here as a discriminator (i.e., there is no additional metadata helping to guess a type of an item before reading it).
However, with the API kotlinx-serialization is currently providing, the only way to decode such a polymorphic value is by trying to read an int, and if read fails with an exception, fall back to reading a string.
This approach is error prone (after getting an exception, the decoder may be in a state that prevents further reading) and it makes sense to provide a more convenient API to work with it and with any other similar CBOR-protocols.

Refer to RFC 8949 for details about the CBOR format.
Refer to RFC 8152 for details about the COSE protocol.

Proposed solution

The API proposed in #3036 solves challenges related to working with the CBOR-based protocols like COSE.

However, there are few open design questions that has to be address before merging the PR into the mainline.

Open questions

CborElement has protected value property, its inheritors override it and make public

It works for some types (like CborString or CborFloat), it does not make sense for others (like CborNull and CborUndefined).

For CborInteger, the actual value is the (absoluteValue, sign) tuple, and it makes sense to use absoluteValue as the property name, instead of sign.

CborByteString exposes value as a ByteArray

CborByteString’s hashCode and equals depend on the value of the underlying ByteArray, but the ByteArray itself is mutable.

The public accessor should create a copy on each access, and it should probably be a function like .toByteArray. Optionally, we can provide some iterator over bytes, to avoid copying data.

Tags representation

Currently, element’s tags are publicly accessible via tags: ULongArray property. There are two issues with ULongArray:

• It’s experimental
• It’s mutable (and hashCode and equals depend on tags)

We should not expose it this way, and even if element tags will be represented as a flat list, they should rather be some immutable collection.

Another tag-related issue is that tags are currently assigned to an element as a flat list. It is consistent with how tags could be specified using KeyTags/ValueTags/ObjectTags.

At the same time, if an element has multiple tags, these CBOR tags are nested (https://cborbook.com/part_1/cbor_tags.html#tag-nesting).
So tags are not just random permutations of different values, their order matters as different orders mean different things.
When tags are represented as a flat list, it is not clear how such a nesting will be encoded (or represented after decoding).

Some tags (https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml) could be applied to different major types, so the scenario when multiple tags are associated with an element should not be that rare.

An alternative approach is representing each tag as a wrapper around a tagged element:

class CborTagged(val tag: ULong, val nested: CborElement)

See how the same example from https://cborbook.com/part_1/cbor_tags.html#tag-nesting will be represented using these two approaches:

// data
// 200(201("Hello, envelope!"))

// current implementation
val envelop0 = CborString("Hello, envelope!", 200UL, 201UL)

// alternative implementation
val envelop1 = CborTagged(200UL, 
                   CborTagged(201UL, 
                       CborString("Hello, envelope!")
                   )
               )

It’s an open question how well each of these APIs is suited for practical use-cases.

KeyTags/ValueTags/ObjectTags and CborElement relation

Encoding/decoding behavior is not explicitly specified for CborElement-typed properties/values and KeyTags/ValueTags/ObjectTags.

Effectively, tags from the annotation will be prepended before tags associated with CborElement. At the same time, the validation will fail (when enabled) during deserialization, creating an asymmetry - a tagged CborElement value will be successfully serialized as a property annotated with ValueTags, but its deserialization will fail because of mismatching tags.

The behavior should be explicitly specified.

CborNullAsEmptyMap annotation

Previously, we discussed that representing nulls as empty maps was required only to simplify COSE documents processing and that CborElement API will cover it.

Is this annotation still needed after providing the CborElement API? Can it be removed? Can those who need such behavior implement a custom serializer instead?

CborArray -> CborObjectAsArray renaming

It seems like we can start a short CborArray deprecation cycle right now, without waiting for the whole CborElement API, can’t we?

CborEncoder API extension

CborEncoder API was extended with following functions:

• encodeUndefined
• encodePositive
• encodeNegative
• encodeByteString
• encodeTags
• encodeCborElement

At the same time, CborDecoder got only the decodeCborElement function.

It creates an asymmetry between encoder and decoder.
And it is also not clear why encoder needs anything but encodeCborElement, if the decoder works perfectly on that level.

Can we trim down the CborEncoder API to just encodeCborElement?

Miscellaneous

There are some other non-API related topics like documentation improvements, or test coverage improvement, but those should not affect the public API and could be addressed separately.

[fzhinkin]

That's the first discussion we have here, at least the one about the API design, so feel free to suggest anything that'll improve it.

[pdvrieze]

One aspect that would be worthwhile to consider is whether it would be worthwhile to have a generic API for storing serialization events. Such API would probably be closely tied to the specifics of the Encoder and CompositeEncoder api's and allow for format independent storage of decode events that can then also be serialized directly again. It would also make for an interesting mode of custom serialization.

[fzhinkin]

It's unclear if we can generalize it for all formats in a way the API will be useful in practice. Even JSON and CBOR while being siblings (to some extent) looks different enough, not to mention other formats.

I don't rule out introduction of such an API, I'm just saying that it might be challenging.

[JesusMcCloud]

Tags representation

The CBOR format of kotlinx.serialization already uses UByteArray as part of its public API. Hence I fail to see the issue.

[JesusMcCloud]

As for nesting: my personal view on this matter is that a flat list already expresses order and, therefore, nesting.

Reasoning: CBOR nests tags one by one, so there is no way of producing multiple tags on the same nesting level, this an ordered list (or an array for that matter) is perfectly unambiguous and provides a simple API, and does not force the instantiation of a nested hierarchy of objects, but just one object holding the value and a list/array of tags, the latter of which is a highly-optimized hot path in the compilers on all targets.

Bottom line (and possibly a hot take): The proposed solution is needlessly complicated and also provides a worse UX than something flat without any real gains.

[fzhinkin]

As for nesting: my personal view on this matter is that a flat list already expresses order and, therefore, nesting.

For a CBOR document like 1(2(3("tagged"))) (encoded as C1C2C366746167676564, tag values are random and don't correspond to their actual meaning for this particular example), the element is CborString with "tagged" string inside, and tags are [1, 2, 3].

And it all could be interpreted (unless a user took his time to read CBOR's RFC) as a "string tagged with three tags, namely 1, 2, and 3". But in fact, it's a "string "tagged" tagged with 3, which is tagged with 2, which is tagged with 1".

To be less abstract, let's say there's a CBOR document (0(34("MTk5MC0xMi0zMVQyMzo1OTo2MFo=")), which is (assuming I correctly combined everything) a base64-encoded (tag 34) timestamp (tag 0) "1990-12-31T23:59:60Z".

Now, if decoder reads tags array from left to right, it makes sense to construct an Instant from string "MTk5MC0xMi0zMVQyMzo1OTo2MFo=" first. But that would be an error, and the tags array should be interpreted from right to left, which could be counter intuitive.

[fzhinkin]

UX depends on how tags are usually interpreted and how many tags an element has on average. If majority of CBOR elements has at most a single tag value, unwrapping it from something like a CborTag(val tag: ULong, val tagged: CborElement) might be clanky.

On the other hand, for elements having multiple tags, it does not sounds insane to recursively unwrap and decode the element, one tagged layer after another. Like if there's a CborTagged(tag = N, tagged = CborTagged(tag = 34 /* base64 */, tagged = CborString("aGVsbG8=")), the decoder capable of handling tag N, will first decode a byte array from base64 string using a dedicated decoder, and then will do its own things. This way, combining a decoder for any reasonable tag sequence should be a pretty trivial task.

But I'm not sure if it's actually the problem, or CBOR documents are usually have at most one tag.

[JesusMcCloud]

Concerns about the mutability of (byte) arrays

I feel like this is trying to work around a fundamental characteristic of the Kotlin language. Feels somewhat off, as this is not for a serialization format to address, but rather the topic of a KEEP

[fzhinkin]

The API should not expose mutable data if it is not intended to be mutated. It would be nice to use immutable/frozen arrays or ByteStrings, if they were a part of the stdlib or the language itself. But until then, either some other type has to exposed instead of the ByteArray, or the corresponding accessor has to return array's copy.

[JesusMcCloud]

CborElement has protected value property, its inheritors override it and make public

I am really undecided on this as well, because there a two ways to view this:

1. The integer issue is an edge case resulting in Kotlin's Long/ULong lacking a single bit compared to CBOR; tough luck, CBOR undefined is weird anyway, an null is null; dassit!
2. I messed it up and it's a bad shape because there are three elementary primitives that do not work with it.

I feel both takes are legit, but I tend to favour the second one because Kotlin is our ground truth, not CBOR. I don't have a good Idea how to fix it…

[fzhinkin]

Given that there are only a few classes that can safely expose value as their own value, it makes sense to remove the property from the base class and define corresponding properties only in CborFloat, CborString and CborBoolean.

[JesusMcCloud]

CborNullAsEmptyMap annotation

#3126 is already integrated. In other words: CborNullAsEmptyMap is already removed as it was just plain broken. Issue solved, fix committed and no open discussion points imho.

[fzhinkin]

#3126 is already integrated. In other words: CborNullAsEmptyMap is already removed as it was just plain broken.

The annotation is still exist in #3036 (here).

[JesusMcCloud]

Asymmetric Tag Handling

Effectively, tags from the annotation will be prepended before tags associated with CborElement. At the same time, the validation will fail (when enabled) during deserialization, creating an asymmetry - a tagged CborElement value will be successfully serialized as a property annotated with ValueTags, but its deserialization will fail because of mismatching tags.

I feel like this is more of a general disambiguation issue, that also hit ASN.1, but on steroids. See here. Could be I'm mixing things up from your description, but if this is about ambiguitiy, fixing it for CBOR should be ridiculously easy compared seven layers of insanity wrapping ASN.1 disambiguation.

[pdvrieze]

One thing that I would remark here (having looked at ASN.1 too) is that while it would be technically possible to inject tags on serialization, this would not be robust on serialization tree change. An implementation could have the serializer and deserializer could share an extended descriptor tree (XML does this) that would ensure the consistency between encoding and decoding. If however elements are dependent on implicit implementation details such as new types added outside its directly visible ancestor/descendant trees, this likely breaks.

It might be valid to use a cryptographic hash of the descriptor (including the hashes of the children) as automatic key/tag (if valid in the format), but this obviously breaks compatibility with previous versions. Explicit tags might be preferable.

[fzhinkin]

but if this is about ambiguitiy

I'm not sure if there's an ambiguity. The following snippet will fail because of the asymmetry: encoder encodes tags from both @ValueTags annotation and tags embedded into CborElement, but the decoder expects only tags from @ValueTags.

@Serializable
data class Tagged(@ValueTags(42UL) val element: CborElement)

val cbor = Cbor {
  encodeValueTags = true
  encodeKeyTags = true
  verifyKeyTags = true
  verifyObjectTags = true
  verifyValueTags = true
}

cbor.decodeFromByteArray<Tagged>(
  cbor.encodeToByteArray(
    Tagged(CborInteger(1, 43UL))))

[JesusMcCloud]

CborEncoder API extension Asymmetry

I thin this issue would really benefit from a human (and not an AI) that is not me opening the current state in IDEA and check it out. There is an 80% chance I just messed this up for no reason and we can easily fix it and make the APIs of encoder and decoder symmetric, but I don't see it. This is all I am willing to spell out about this issue, even though I have a strong opinion, because a neutral pair of eyes on this, and some playing around with it has the potential to work wonders and me being more concrete may sabotage this.

[pdvrieze]

The way this is done in most formats (including Json) is that there is a format specific interface that provides access to the underlying parser/encoder and custom serializers then use that (or a wrapper - as XML uses for parser access to deal with serializer inconsistency in tag consumption).

For a binary format it is even more important to have some sort of wrapper that ensures correctness (either by throwing an exception on error or recovering errors). As such I would say the interfaces should be on encoder/decoder properties that allow for interacting with the
underlying format. The format could/should provide wrappers that ensure that the format state does not get inconsistent with the manual encoding (and decoding).

At such point any CborElement object is just another object with custom serializer that uses encoder/decoder access for custom behaviour. The advantage would be that your API is then not bound to the CborElement type.