Map-like data in CBOR and CDDL

1.1. Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

This specification uses terminology from [RFC8949] and [RFC8610]. In particular, with respect to CDDL control operators, "target" refers to the left hand side operand, and "controller" to the right hand side operand. The terms "array" and "map" (if unadorned) refer to CBOR major type 4 and CBOR major type 5; this is not called out explicitly.¶

2.1. Summary

*TBD279: https://github.com/Sekenre/cbor-ordered-map-spec/blob/master/CBOR_Ordered_Map.md¶

*TBD280: https://github.com/ecorm/cbor-tag-multimap¶

[The intention of the present document is to obviate the need for defining TBD279/TBD280.]¶

Appendix A.1 provides information about constructs in a few programming languages that are related to the tags being defined.¶

2.2. Key/Value Type

Bits 2 and 3 of the tag provide information on the map's key and value types:¶

• 0b00xx Unspecified: There is no specified type for the map's keys and values¶
• 0b01xx Homogeneous Key: All keys have the same data type¶
• 0b10xx Homogeneous Key/Value: All values have the same data type in addition to all keys having the same data type (the types for keys and values may be distinct).¶

The semantics for homogeneity shall be the same as for [RFC8746] homogeneous arrays (tag 41). That is, "which CBOR data items constitute elements of the same application type is specific to the application" (Section 3.2 of [RFC8746]).¶

Maps with arbitrary keys and homogeneous values are considered unusual, so they are left out of this specification so that fewer tag numbers need to be allocated (12 instead of 16).¶

2.3. Ordering

Bit 1 of the tag represents the map's ordering semantics:¶

• 0: The order of key-value pairs is unspecified¶
• 1: Key-value pairs are encoded in the same order in which they were inserted¶

2.4. Key Uniqueness

Bit 0 of the tag represents the uniqueness of the map's keys.¶

• 0: Keys are unique within the map¶
• 1: Keys may be duplicated (i.e., multimaps)¶

2.5. Data Item

All these map-like data items could be represented as a tag with an enclosed array of alternating key-value pairs, as in:¶

129(["key1", 1, "key2", 2])

However, representing the key-value pairs as a CBOR map for those cases where this is possible enables generic decoders that are oblivious of these tags to represent the data in a more appropriate platform type.¶

Specifically, the key-value pairs are represented as a map if and only if¶

• the ordering is unspecified and¶
• the keys are unique;¶

otherwise, they are represented as an array of alternating keys and values ("flattened alist", see Figure 1).¶

FAList<K, V> = [* (K, V)]

Issue: [MAPREP] discusses alternative representations of (ordered and other) maps. How much of this do we need to address here?¶

2.6. Related Tags (Informative)

3.1. Map notation for map-like data items

[needs better examples]¶

CDDL already can describe both arrays of alternating keys and values and maps (non-ordered and with unique keys). The two control operators .omm and .nomm introduced in this section enable the use of CDDL map notation for map-like types beyond actual maps, increasing readability and possibly even reusability.¶

In a simple example that provides an non-ordered collection of zero or more home addresses and zero or more work addresses, each labeled as such, we use traditional map notation to describe that collection:¶

[* (text, any)] .nomm {
  * home: address
  * work: address
  $$more-addresses
}

The .omm and .nomm control operators convert a group definition enclosed into a CDDL map given as a controller type into an array type given as the target type. The controller type given is unwrapped (Section 3.7 of [RFC8610]) into a group. Keys and values of the entries in that group are then alternatingly matched as elements in the target array. Note that both target and controller type can contribute to the shaping of the data; declaring the key type as text limits what can be added to the $$more-addresses socket.¶

.omm and .nomm differ in the semantics of the array type created: .omm defines an ordered (multi)map, i.e., the order of the key/value element pairs in the array matters, while .nomm defines an non-ordered (multi)map, i.e., data items that present the same set of key/value pairs in different orders are equivalent.¶

The ability to specify specific ("homogeneous") types is provided by the ability to specify the target type, as in the example above.¶

Note that there is not strictly a need to define a control operator for building non-ordered maps with non-duplicate keys, as existing CBOR maps already fill this role, however the use of a map type as the target is allowed for symmetry (implying uniqueness of the keys), allowing the following:¶

{* text => any} .nomm {
  ? home: address
  ? work: address
  $$more-addresses
}

3.2. Uniqueness

The .unique control annotates the target as requiring uniqueness, within the enclosing container(*), of its value, among the other data items in that enclosing container that are also marked .unique, under the same label (given as the controller).¶

E.g.,¶

feature-set = [* feature .unique "set"]
ordered-pairs-with-unique-keys-and-values =
  [* (any .unique "key", any .unique "value") ]

defines a feature-set as an array of zero or more feature values that need to be all different (as they are unique under the label set), and ordered-map-with-unique-keys-and-values as an array of zero pairs of keys and values, where the keys need to be unique among themselves and the values need to be unique among themselves (the latter example could employ an .omm or .nomm operator to further restrict what can be in these keys and values).¶

• Discussion: (*) while it is probably not a big problem to define what exactly the "enclosing" container is, it may be useful to actually define a larger scope of the uniqueness. CDDL currently does not have a way to establish and point to such a larger scope; we might define one ad hoc here or leave that for later extension.¶

5.1. Tags

IANA is requested to allocate the tags of Table 1 in the CBOR tags registry [IANA.cbor-tags], using this document as the specification reference.¶

The allocations are requested to be assigned from the "specification required" space (24..255). The values in the column labeled "Tag" in Table 1 are suggested as the allocated tag numbers.¶

5.2. CDDL control operators

This document requests IANA to register the contents of Table 3 into the CDDL Control Operators registry [IANA.cddl]:¶

A.1. Programming Language Containers (Informative)

The following subsections describe how the tags in this document relate to various programming language containers. Containers that are not part of the programming language or its standard libraries are not considered here.¶

The Encoding Tag column in the following tables provide the recommended tag that best represents the given container type. For example, it's possible to use tag 132 for encoding an ECMAScript Map if all keys happen to be of the same type, however tag 128 is more general and applies to any Map. When encoding an ECMAScript Object, tag 128 would be technically correct but is too general; tag 132 best presents the fact that an Object has text keys only.¶

The Decodable Tags column in the following tables, are for data items can be decoded into the destination container without having to inspect the following:¶

• the uniqueness of the keys,¶
• the ordering of the keys, and,¶
• the data types of every keys/value pair.¶

It may however be necessary to inspect the data types of the first key-value pair in the case of tags representing homogeneous keys/values.¶

A.2. CDDL Implementation Considerations

TBD¶