CBOR is a compact binary data serialization and messaging format. This specification defines CBOR-LD 1.0, a CBOR-based format to serialize Linked Data. The encoding is designed to leverage the existing JSON-LD ecosystem, which is deployed on hundreds of millions of systems today, to provide a compact serialization format for those seeking efficient encoding schemes for Linked Data. By utilizing semantic compression schemes, compression ratios in excess of 60% better than generalized compression schemes are possible. This format is primarily intended to be a way to use Linked Data in storage and bandwidth constrained programming environments, to build interoperable semantic wire-level protocols, and to efficiently store Linked Data in CBOR-based storage engines.

This document is experimental.

There is a reference implementation that is capable of demonstrating the features described in this document.

Introduction

CBOR is a compact binary data serialization and messaging format. This specification defines CBOR-LD 1.0, a CBOR-based format to serialize Linked Data. The encoding is designed to leverage the existing JSON-LD ecosystem, which is deployed on hundreds of millions of systems today, to provide a compact serialization format for those seeking efficient encoding schemes for Linked Data. By utilizing semantic compression schemes, compression ratios in excess of 60% better than generalized compression schemes are possible. This format is primarily intended to be a way to use Linked Data in storage and bandwidth constrained programming environments, to build interoperable semantic wire-level protocols, and to efficiently store Linked Data in CBOR-based storage engines.

How to Read this Document

This document is a detailed specification for a serialization of Linked Data in CBOR. The document is primarily intended for the following audiences:

Contributing

There are a number of ways that one may participate in the development of this specification:

Design Goals and Rationale

CBOR-LD satisfies the following design goals:

Simplicity
Implementations should be simple to implement given an existing JSON-LD implementation.
Efficient Storage
The encoding process should generate an aggressively compact Linked Data binary format.
Generalized Algorithm
The encoding algorithm must be generalized.
Semantic Compression
The encoding format should maximize compression of Linked Data URLs (terms and values). Focusing here ensures that the algorithms can achieve compression ratios better than generalized compression algorithms.
Raw Binary
Base-encoded binary values, and other compressible data types, should be translated to their raw binary forms from base-encoded formats when possible without sacrificing generality.

Similarly, the following are non-goals.

The following minefields have been identified while working on this specification:

Basic Concept

The general CBOR-LD encoding algorithm takes a JSON-LD Document and does the following:

CBOR Tags for CBOR-LD

The first step in decoding a CBOR-LD payload is to recreate the term codec map that was used to encode it by processing the contexts in the payload. However, the contexts needed to create the term codec map can have their URLs encoded as integers by CBOR-LD. If a CBOR-LD payload contains context URLs compressed in such a way, the consumer of the CBOR-LD needs to know what compression tables (maps from JSON-LD terms to integers) were used to compress the context URLs during creation to be able to reconstruct the term codec map. The following sections define the exact mechanism by which this can be accomplished, allowing an arbitrary CBOR-LD consumer to decompress any CBOR-LD payload that conforms to this specification.

To this end, we have registered the range of CBOR tags 1536-1791** (0x0600-0x06FF) to be used for CBOR-LD, where data that includes tag value is used to lookup what compression table(s) are needed to decompress the CBOR-LD context URLs.

This exact range of tag values has not yet been officially registered with the IANA CBOR Tag Registry. The exact range is subject to change.

CBOR-LD Varint

To enable unbounded extension on possible use cases for CBOR-LD that require different compression table material for consumption while working within a fixed number of CBOR tag values, we define the following.

Implementers MUST interpret the last byte of the two-byte CBOR tag value on a CBOR-LD payload as the beginning of a varint. If the CBOR tag is in the range `0x0600`–`0x067F`, the last byte of the CBOR tag is a one-byte varint, and the tagged item MUST be a map containing the encoded JSON-LD. If the CBOR tag is `0x0680` or greater, the tagged item MUST be an array containing two elements. The first item in the array MUST be a major type 2 byte string containing the rest of the varint, and the second item in the array MUST be a map containing the encoded JSON-LD. See Algorithm for more information.

The value of this varint is then used to lookup a CBOR-LD Varint Registry Entry in the CBOR-LD Varint Registry.

CBOR-LD Varint Registry

The CBOR-LD Registry is a global list that provides consumers of CBOR-LD payloads the information they need to reconstruct the term codec map required for decompression. A CBOR-LD Varint Registry Entry contains the following:

  1. Registry Entry ID: a positive integer.
  2. Use Case: what type of CBOR-LD payload this entry is used for.
  3. `typeTables`: an array containing what `Type Tables` are to be used for this type of payload.
  4. `processingModel`: what processing model is used for this registry entry. A processing model specifies how auto-generated CBOR-LD values are created from JSON-LD contexts as well as what type encoders are used alongside the `Type Tables` (e.g. how to partially compress an `xsd:dateTime` value that does not appear in `Type Table`). The default processing model, which will be defined later in this specification, will be used unless otherwise specified in the Registry Entry.
  5. Provisional: a yes/no flag indicating whether the entry is provisional. Provisional entries may change or be removed.

The `typeTables` associated with a CBOR-LD Varint Registry Entry MUST be an array of or JSON objects. The only exception is the string "callerProvidedTable", which may appear in this array, denoting that for this use case, a `Type Table` is required which is not globally defined.

Dereferencing one of these URLs MUST result in a JSON object with the following properties:
  1. `type`: a JSON-LD type.
  2. `table`: a JSON object that maps values of the above type to integers.

If a JSON object is present in the `typeTables` array, it MUST be in the above format.

Registry

The following is the current CBOR-LD registry:

Registry Entry Id Use Case typeTables Processing Model Provisional
0 Uncompressed CBORLD None DEFAULT No
1 Compressed CBORLD, default use case. DEFAULT DEFAULT No
100 Verifiable Credential Barcodes Specification Test Vectors [ { type: "context", table: { "https://www.w3.org/ns/credentials/v2": 32768, "https://w3id.org/vc-barcodes/v1": 32769, "https://w3id.org/utopia/v2": 32770 } }, { type: "https://w3id.org/security#cryptosuiteString", table: { "ecdsa-rdfc-2019": 1, "ecdsa-sd-2023": 2, "eddsa-rdfc-2022": 3, "ecdsa-xi-2023": 4 } } ] DEFAULT Yes
10001 Provisional California DMV Credentials [ { type: "context", table: { "https://www.w3.org/ns/credentials/v2": 1, "https://w3id.org/vc-barcodes/v1": 2, "https://w3id.org/vc-dpp/v1rc1": 3, "https://w3id.org/vdl/v1": 4 } }, { type: "https://w3id.org/security#cryptosuiteString", table: { "ecdsa-rdfc-2019": 1 } }, { type: "url", table: { "did:key:zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee": 1, "did:key:zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee#zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee": 2, "https://dmv.ca.gov/statuses/12345/status-lists": 3 } } ] DEFAULT Yes
10002 Provisional First Responder SAP Credentials [ { type: "context", table: { "https://www.w3.org/ns/credentials/v2": 1, "https://w3id.org/vc-barcodes/v1": 2, "https://w3id.org/first-responder/sap/v1rc1": 3, } }, { type: "https://w3id.org/security#cryptosuiteString", table: { "ecdsa-rdfc-2019": 1 } }, { type: "url", table: { "did:key:zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee": 1, "did:key:zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee#zDnaeW9VZZs7NH1ykvS5EMFmdodu2wj4dPcrV3DzTAadrXJee": 2, "https://caloes.ca.gov/statuses/12345/status-lists": 3 } } ] DEFAULT Yes

Algorithms

In this section, we specify the algorithms required to convert JSON-LD to CBOR-LD and vice versa. We provide first the context processing algorithms, which are required for both decompression and compression; we then provide the mode-specific algorithms.

Encoding and Decoding

JSON-LD to CBOR-LD Compression Algorithm

This algorithm takes a map `typeTable`, an integer `registryEntryId`, and a JSON-LD document `jsonldDocument` as inputs, and returns a hexadecimal string `cborldBytes`.

  1. Set `prefix` to the result of passing `registryEntryId` to .
  2. Set `state` to an empty map.
  3. Set `state.strategy` to "compression".
  4. Set `state.typeTable` to `typeTable`.
  5. Set `state.registryEntryId` to `registryEntryId`.
  6. Set `state` to the result of passing `state` to .
  7. Set `output` to the result of passing `state` and `jsonldDocument` as `inputDocument` to .
  8. Set `suffix` to the CBOR encoding of `output`.
  9. Set `cborldBytes` to a hexidecimal encoding of `prefix` prepended to `suffix`.
  10. Return `cborldBytes`.

CBOR-LD to JSON-LD Decompression Algorithm

This algorithm takes a CBOR-LD payload `cborldBytes`, and returns a JSON-LD document `jsonldDocument`.

  1. Set `result` to the result of passing `registryEntryId` and `cborldBytes` to .
  2. Set `state`.`registryEntryId` to `result`.`registryEntryId` and `suffix` to `result`.`suffix`.
  3. Set `state` to an empty map.
  4. Set `state.strategy` to "decompression".
  5. For each entry `type`: `map` in the `typeTables` array in the CBOR-LD Varint Registry Entry associated with `registryEntryId`, add that entry to `state`.`typeTable`, and set the value of `type` in `state`.`reverseTypeTable` to `inverseMap`, where `inverseMap` is `map` with the mapping inverted.
  6. Set `state` to the result of passing `state` to .
  7. Set `input` to the result of decoding `suffix` from bytes to a map.
  8. Set `jsonldDocument` to the result of passing `state` and `input` as `inputDocuments` to .
  9. Return `jsonldDocument`.

Conversion Algorithms

The algorithms in this section describe the behavior of a "converter" for abstractly converting inputs between data forms. When used in conjunction with a "strategy", such as the "compression" and "decompression" strategies defined later in this section, these algorithms can be instantiated to convert between concrete data forms. The "compression" strategy converts from JSON-LD to CBOR-LD, while the "decompression" strategy converts from CBOR-LD to JSON-LD.

Initialize Conversion Algorithm

This algorithm takes and returns a map `state`.

  1. Set `state` to the result of passing `state` to .
  2. Set `state.initialActiveContext` to the result of passing empty maps `termMap` and `previousActiveContext` to .
  3. Set `state.typesEncodedAsBytes` to an empty set.
  4. Add "none", "http://www.w3.org/2001/XMLSchema#date", "http://www.w3.org/2001/XMLSchema#dateTime", and "url" to `state.typesEncodedAsBytes`.
  5. Return `state`.

Convert Document Algorithm

This algorithm takes a map `state` and a map or array of maps `inputDocuments`, and returns a map containing a map `state` and a map or array of maps `outputMaps`.

  1. If `inputDocuments` is an array, set `inputs` to `inputDocuments`. Otherwise, set `inputs` to `[inputDocuments]`.
  2. Set `outputMaps` to an empty array.
  3. For `input` in `inputs`:
    1. Set `output` to an empty map.
    2. Set `result` to the result of passing `state`, `input`, `output`, and `state.initialActiveContext` as `activeContext` to .
    3. Add `result.output` to `outputMaps`.
    4. Set `state` to `result.state`.
  4. If `inputDocuments` is an array, return `outputMaps`. Otherwise, return the first element of `outputMaps`.

General Conversion Algorithm

This algorithm takes maps `input`, `output`, `state`, and `activeContext` as inputs, and returns a map containing maps `state` and `output`.

  1. If `state.strategy` is set to "compression":
    1. Set `contextConversionResult` to the result of , passing `state`, `activeContext`, `input`, and `output`.
    2. Set `activeContext` to `contextConversionResult.activeContext`, `output` to `contextConversionResult.output`, and `state` to `contextConversionResult.state`.
  2. Otherwise, set `activeContext` to `result.activeContext` and `state` to `result.state` of `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  3. If `state.strategy` is set to "compression", set `state` to `result.state` and `objectTypes` to `result.objectTypes` for `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  4. Otherwise, set `state` to `result.state` and `objectTypes` to `result.objectTypes` for `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  5. Set `activeContext` to the result of passing `activeContext` and `objectTypes` to .
  6. If `state.strategy` is set to "compression", set `state` to `result.state` and `termEntries` to `result.termEntries` for `result` resulting from , passing `state`, `input`, and `activeContext`.
  7. Otherwise, set `state` to `result.state`, `output` to `result.output`, and `termEntries` to `result.termEntries` for `result` resulting from , passing `state`, `input`, output, and `activeContext`.
  8. For `[termInfo, value]` in `termEntries`:
    1. Set `term` to `termInfo.term`.
    2. Set `valueActiveContext` to the result of passing `activeContext` and `term` to .
    3. Set `plural` to the value of `termInfo.plural` and `termType` to the value of `@type` in `termInfo.def`.
    4. If `plural` is set to `true`, set `values` to the value of `value`. Otherwise, set `values` to an array containing the value of `value` as a single element.
    5. Set `outputs` to an empty array.
    6. For `unconvertedValue` in `values`:
      1. Set `result` to the result of , passing `state`, `termType`, `unconvertedValue` as `value`, and `valueActiveContext` as `activeContext`.
      2. Set `state` to `result.state` and add `result.output` to `outputs`.
    7. If `plural` is set to `true`, set `outputValues` to `outputs`. Otherwise, set `outputValues` to the first element of `outputs`.
    8. If `state.strategy` is set to "compression", set the value of `termInfo.termId` to map to `outputValues` in `output`. Otherwise, set the value of `termInfo.term` to map to `outputValues` in `output`.
  9. Set `result` to be an empty map.
  10. Set `result.state` to `state` and `result.output` to `output`.
  11. Return `result`.

Convert Value Algorithm

This algorithm takes maps `state`, `activeContext`, `termInfo`, and values `value` and `termType`. It returns a `result` object containing maps `state` and `output`.

  1. If `value` is `null`, return `null`.
  2. If `state`.`strategy` is set to "compression", set `output` to the result of passing `state`, `termType`, `termInfo`, and `value` to .
  3. Otherwise, set `output` to the result of passing `state`, `termType`, `termInfo`, and `value` to .
  4. If `output` is defined, return `result`, a map contatining `state` and `output`.
  5. If `value` is an array:
    1. Set `outputs` to be an empty array.
    2. For `element` of `value`:
      1. Let `result` be the result of , passing `activeContext`, `state`, `termInfo`, `termType`, and `element` as `value`. Set `state` to `result`.`state` and add `result`.`output` to `outputs`.
    3. Set `result` to be an empty map. Set `result`.`state` to `state` and `result`.`output` to `outputs`.
    4. Return `result`.
  6. Set `output` to an empty map.
  7. Set `result` to the result of , passing `state`, `activeContext`, `value` as `input`, and `output`.
  8. Return `result`.

Compression Strategy Algorithms

The algorithms in this section define the "compression" strategy to be used with the "conversion" algorithms defined previously to convert JSON-LD to CBOR-LD.

Convert Contexts for Compression Algorithm

This algorithm takes maps `state`, `activeContext`, `input`, and `output`, and returns a map `result` containing maps `output`, `state`, and `activeContext`.

  1. Set `applyEmbeddedResult` to the result of , passing `state`, `activeContext`, and `input`.
  2. Set `activeContext` to `applyEmbeddedResult.activeContext` and `state` to `applyEmbeddedResult.state`.
  3. If "@context" does not have an entry in `input`:
    1. Set `result` to an empty map.
    2. Set `result.state` to `state` and `result.activeContext` to `activeContext`.
    3. Return `result`.
  4. Set `context` to the value of "@context" in `input`.
  5. Set `encodedContexts` to an empty array.
  6. If `context` is an array, set `isArray` to `true` and `contexts` to `context`. Otherwise, set `isArray` to `false` and `contexts` to `[context]`.
  7. For `contextValue` in `contexts`:
    1. Set `encoderData` to the result of , passing `state.typeTable` and `contextValue`.
    2. If `encoderData` is an empty map, add `contextValue` to `encodedContexts`.
    3. Otherwise, add the value of `encoderData` to `encodedContexts`.
  8. If `isArray` is `true`, set `id` to the value of "@context" in `state.keywordsMap` plus 1 and set the value of `id` in `output` to `encodedContexts`.
  9. Otherwise, set `id` to the value of "@context" in `state.keywordMap` and set the value of `id` in `output` to the first element of `encodedContexts`.
  10. Set `result.output` to `output`, `result.state` to `state`, and `result.activeContext` to `activeContext`.
  11. Return `result`.

Convert Value for Compression Algorithm

This algorithm takes maps `state` and `termInfo`, and values `valueToEncode` and `termType`, and returns a map `encoderData`.

  1. If `valueToEncode` is an object, return.
  2. Otherwise, set `result` to the result of , passing `state`, `termInfo`, `valueToToEncode`, and `termType`.
  3. Return `result`.

Get Input Entries for Compression Algorithm

This algorithm takes maps `state`, `activeContext`, and `input`, and returns a map `state` and an array `entries`.

  1. Initialize `entries` as an empty array.
  2. Set an array `keys` to the keys of `input`, sorted lexicographically.
  3. For `key` in `keys`:
    1. If `key` is "@context", continue.
    2. Set `value` to the value of `key` in `input`.
    3. If `value` is an array, set `plural` to `true`. Otherwise, set `plural` to `false`.
    4. If `key` does not have an entry in `state`.`termToId`, set `termId` to `key`.
    5. Otherwise, if `plural` is `true`, set `termId` to the value of `key` in `state`.`termToId` plus 1.
    6. Otherwise, set `termId` to the value of `key` in `state`.`termToId`.
    7. If `activeContext`.`termMap` has an entry for `key`, set `definition` to the value of `key` in `activeContext`.`termMap`. Otherwise, set `definition` to an empty map.
    8. Set `entryTerm` to be a new map.
    9. Set the value of "term" in `entryTerm` to be the value of `key`. Add `termId`, `plural`, and `definition` to `entryTerm`.
    10. Create an array `entry` with two elements, `entryTerm` and `value`.
    11. Add `entry` to `entries`.
  4. Return a map `result` containing `entries` and `state`.

Get Object Types for Compression Algorithm

This algorithm takes maps `activeContext` and `input`, and returns a set `objectTypes`.

  1. Set `objectTypes` to be an empty set.
  2. For `term` in `activeContext`.`typeTerms`:
    1. If `term` has an entry in `input`:
      1. Set `types` to the value of `term` in `input`.
      2. Add each value in `types` to `objectTypes`.
  3. Return `objectTypes`.

Decompression Strategy Algorithms

The algorithms in this section define the "decompression" strategy to be used with the "conversion" algorithms defined previously to convert CBOR-LD to JSON-LD.

Convert Contexts for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, `input`, and `output`, and returns a map `result` containing maps `output`, `state`, and `activeContext`.

  1. Set `decoderData` to the result of , passing `state`.`reverseTypeTable`.
  2. Set `contextTermId` to the value of "@context" in `state`.`keywordsMap`.
  3. If `contextTermId` has an entry in `input`, set the value of "@context" in `output` to the result of , passing `decoderData` and the value of `contextTermId` in `input` as `value`.
  4. Set `contextTermIdPlural` to the value of `contextTermId` plus 1.
  5. If `contextTermIdPlural` has an entry in `input`:
    1. If `contextTermId` also had an entry in `input` during the previous check, throw an `ERR_INVALID_ENCODED_CONTEXT` error.
    2. Set `encodedContexts` to be the value of `contextTermIdPlural` in `input`. If `encodedContexts` is not an array, throw an `ERR_INVALID_ENCODED_CONTEXT` error.
    3. Set `contexts` to be an empty array.
    4. For each `valueToDecode` in `encodedContexts`, add the result of passing `decoderData` and `valueToDecode` as `value` to to `contexts`.
    5. Set the value of "@context" in `output` to `contexts`.
  6. Set `embeddedContextResult` to the result of , passing `activeContext`, `output` as `input`, and `state`.
  7. Set `result` to an empty map.
  8. Set `result`.`state` to `embeddedContextResult`.`state` and `result.activeContext` to `embeddedContextResult`.`activeContext`.
  9. Return `result`.

Convert Value for Decompression Algorithm

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToDecode`, and returns a value `decodedValue`.

  1. If `value` is a map, return.
  2. Set `decoderData` to the result of , passing `valueToDecode`, `state`, `termInfo`, and `termType`.
  3. Set `decodedValue` to the result of , passing `decoderData`.
  4. Return `decodedValue`.

Get Input Entries for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, and `input`, and returns a map `state` and an array `entries`.

  1. Initialize `entries` to an empty array.
  2. For key-value pair `key` and `value` in `input`:
    1. If `key` is the value of "@context" in `state`.`keywordsMap` or that value plus 1, continue.
    2. Otherwise, if `key` is a string, set `plural` to false and `term` to `key`.
    3. Otherwise:
      1. If `key` is odd, set `plural` to true. Otherwise, set `plural` to false.
      2. If `plural` is `true`, set `term` to the value of `id` minus 1 in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
      3. Otherwise, set `term` to the value of `id` in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
    4. Set `definition` to the value of `term` in `activeContext`.`termMap`.
    5. Set `entryTerm` to be a new map.
    6. Set the value of "termId" in `entryTerm` to be the value of `key`. Add `term`, `plural`, and `definition` to `entryTerm`.
    7. Create an array `entry` with two elements, `entryTerm` and `value`.
    8. Add `entry` to `entries`.
  3. Sort `entries` by the value of `term` in each element of `entries`.
  4. Return a map `result` containing `entries` and `state`.

Get Object Types for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, `input` as inputs, and returns a map `state` and a set `objectTypes`.

  1. Set `objectTypes` to be an empty set.
  2. For `term` in `activeContext`.`typeTerms`:
    1. If `term` does not have an entry in `state`.`termToId`, set `termId` to `term`.
    2. Otherwise, set `termId` to the value of `term` in `state`.`termToId`.
    3. If neither `termId` nor `termId` plus 1 are present in `input`, continue.
    4. Otherwise, if `termId` is present in `input`, set `value` to the value of `termId` in `input`.
    5. Otherwise, set `value` to the value of `termId` plus 1 in `input`.
    6. If `key` is a string, set `plural` to false and `term` to `key`.
    7. Otherwise:
      1. If `key` is odd, set `plural` to true. Otherwise, set `plural` to false.
      2. If `plural` is `true`, set `term` to the value of `id` minus 1 in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
      3. Otherwise, set `term` to the value of `id` in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
    8. Set `definition` to the value of `term` in `activeContext`.`termMap`.
    9. Set `termInfo` to be a new map.
    10. Add `term`, `termId`, `plural`, and `definition` to `termInfo`.
    11. If `value` is not an array, set `values` to be an array containing as a single element `value`. Otherwise, set `values` to the value of `value`.
    12. For each `value` in `values`:
      1. Set `decoderData` to the result of , passing `value`, `termInfo`, `state`, and "@vocab" as `termType`.
      2. If `decoderData` exists, add the result of , passing `decoderData`, to `objectTypes.
      3. Otherwise, add `value` to `objectTypes`.
  3. Return `objectTypes`.

Active Context Processing

The algorithms in this section describe how to determine what components of the context documents associated with a JSON-LD document are in use at any point during compression or decompression. These algorithms include how to apply embedded, type-scoped, and property-scoped contexts with CBOR-LD. This is in contrast to the Context Loading algorithms defined later in this specification, which describe how to construct the mappings from terms to integers that are the core CBOR-LD compression technique. Together, the Active Context Processing and Context Loading algorithms specify how JSON-LD context documents should be processed when converting to and from CBOR-LD.

Initialize Active Context Algorithm

This algorithm takes maps `previousActiveContext` and `termMap`, and returns a map `activeContext`. It updates the active context in use and finds all aliases for `'@type'`.

  1. Set `activeContext` to a new map.
  2. Set `activeContext.previousActiveContext` to `previousActiveContext`.
  3. Set `activeContext.termMap` to `termMap`.
  4. Set `activeContext.typeTerms` to the array `['@type']`.
  5. For `[term, def]` in `termMap`:
    1. If the value of "@id" in `def` is "@type", add `term` to `activeContext.typeTerms`.
  6. Return `activeContext`.

Apply Embedded Contexts Algorithm

This algorithm takes maps `state`, `activeContext`, and `input` as inputs, and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `termMapUpdateResult` to the result of passing `state`, `activeContext.termMap` as `activeTermMap`, and the value of '@context' in `input` as `contexts` to .
  2. Set `state` to `termMapUpdateResult.state`.
  3. Set `termMap` to `termMapUpdateResult.activeTermMap`.
  4. Set `newActiveContext` to the result of , passing `termMap` and `activeContext` as `previousActiveContext`.
  5. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  6. Return `result`.

Apply Property Scoped Contexts Algorithm

This algorithm takes maps `state`, `activeContext`, and a string `term` as inputs and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `revertedTermMap` to the result of , passing `activeContext`.
  2. Set `termDef` to the value of `term` in `activeContext.termMap`. Set `contexts` to the value of "@context" in `termDef`.
  3. Set `termMapUpdateResult` to the result of passing `state`, `revertedTermMap` as `activeTermMap`, `true` as `propertyScope`, and `contexts` to .
  4. Set `state` to `termMapUpdateResult.state`.
  5. Set `termMap` to `termMapUpdateResult.activeTermMap`.
  6. Set `newActiveContext` to the result of , passing `termMap` and `activeContext` as `previousActiveContext`.
  7. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  8. Return `result`.

Apply Type Scoped Contexts Algorithm

This algorithm takes maps `state`, `activeContext` ,and a set `objectTypes` as inputs, and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `objectTypesSorted` to an empty array.
  2. Lexicographically sort the elements of `objectTypes` and add the elements to `objectTypesSorted` in order.
  3. Set `newTermMap` to `activeContext.termMap`.
  4. For `type` in `objectTypesSorted`:
    1. Set `typeDef` to the value of `type` in `newTermMap`. Set `contexts` to the value of "@context" in `typeDef`.
    2. Set `termMapUpdateResult` to the result of passing `state`, `newTermMap` as `activeTermMap`, `contexts`, and `true` as `typeScope` to .
    3. Set `state` to `termMapUpdateResult.state` and `newTermMap` to `termMapUpdateResult.activeTermMap`.
  5. Set `newActiveContext` to the result of , passing `newTermMap` as `termMap` and `activeContext` as `previousActiveContext`.
  6. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  7. Return `result`.

Update Term Map Algorithm

This algorithm takes maps `state`, `activeTermMap`, and map or array `contexts` as well as booleans `typeScope` and `propertyScope`, both of which default to `false` if not provided, as inputs. It returns maps `state` and `activeTermMap`.

  1. If `contexts` is not an array, set `contexts` to be an array with the previous value of `contexts` as its sole element.
  2. Set `allowProtectedOverride` to the value of `propertyScope`.
  3. Set `propagateDefault` to the negation of the value of `typeScope`.
  4. For `contextIdentifier` in `contexts`:
    1. Set `loadResult` to the result of , passing `state` and `contextIdentifier`.
    2. Set `entry` to `loadResult`.`entry`, `context` to `entry`.`context`, and `state` to `loadResult`.`state`.
    3. If `@propagate` appears in `context`, set `propagate` to the value of `@propagate` in `context`. Otherwise, set `propagate` to the value of `propagateDefault`.
    4. Set `newTermMap` to be an empty map. For [`key`, `value`] in `entry`.`termMap`:
      1. Shallow copy the contents of `value` into a new map `newValue` and add `propagate` to `newValue`.
      2. Set the value of `key` in `newTermMap` to `newValue`.
    5. For [`term`, `activeDef`] in `activeTermMap`:
      1. Let `def` be the value of `term` in `newTermMap`.
      2. If `def` is defined:
        1. If the value of `protected` in `activeDef` is `true`:
          1. If `allowProtectedOverride` is set to `false` and `def` is not identical to `activeDef`, throw an error ERR_PROTECTED_TERM_REDEFINITION.
          2. Otherwise, set the value of `term` in `newTermMap` to a map containing the values from `activeDef` and `propagate` set to the value of `def`.`propagate`.
      3. Otherwise, if `term` appears in `context`, set the value of `term` in `newTermMap` to a map containing all values from `activeDef`.
    6. Set the value of `activeTermMap` to the value of `newTermMap`.
  5. Set `result` to be an empty map.
  6. Set `result`.`state` to `state` and `result`.`activeTermMap` to `activeTermMap`.
  7. Return `result`.

Revert Term Map Algorithm

This algorithm takes as input a map `activeContext`, and returns a map `newTermMap`.

  1. Set `newTermMap` to an empty map.
  2. Set `nonPropagatingTerms` to an empty array.
  3. For `[term, def]` in `activeContext`:
    1. If `def.propagate` is set to `false`, add `term` to `nonPropagatingTerms` and proceed to the next iteration of this loop.
    2. Otherwise, set the value of `term` in `newTermMap` to `def`.
  4. For `term` in `nonPropagatingTerms`:
    1. Set `currentContext` to `activeContext.previousActiveContext`.
    2. Set `def` to the value of `term` in `currentContext.termMap`.
    3. While `def` is not undefined and `def.propagate` is set to `false`:
      1. Set `currentContext` to `activeContext.previousActiveContext`.
      2. Set `def` to the value of `term` in `currentContext.termMap`.
    4. If `def` is not undefined, set the value of `term` in `newTermMap` to `def`.
  5. Return `newTermMap`.

Context Loading

The algorithms in this section define how to construct the mappings between terms and integers that are used as the core CBOR-LD compression technique.

Initialize Context Loader Algorithm

This algorithm takes and returns a map `state`.

  1. Set `state.contextMap` to a new map.
  2. Set `state.nextTermId` to 100.
  3. Set `state.keywordsMap` to the following map of JSON-LD keywords to their associated integer values: 
    {
  '@context' => 0,
  '@type' => 2,
  '@id' => 4,
  '@value' => 6,
  '@direction' => 8,
  '@graph' => 10,
  '@included' => 12,
  '@index' => 14,
  '@json' => 16,
  '@language' => 18,
  '@list' => 20,
  '@nest' => 22,
  '@reverse' => 24,
  '@base' => 26,
  '@container' => 28,
  '@default' => 30,
  '@embed' => 32,
  '@explicit' => 34,
  '@none' => 36,
  '@omitDefault' => 38,
  '@prefix' => 40,
  '@preserve' => 42,
  '@protected' => 44,
  '@requireAll' => 46,
  '@set' => 48,
  '@version' => 50,
  '@vocab' => 52,
  '@propagate' => 54
}
  4. Add each entry in `state.keywordsMap` to `state.termToId`.
  5. If `state.strategy` is set to "decompression", set `state.idToTerm` to the reverse map of `state.termToId` (i.e., a map from integers to JSON-LD keywords).
  6. Return `state`.

Load Context Algorithm

This algorithm takes a map `state` and a context map or URL `contextIdentifier`, and returns `result`, a map containing maps `state` and `entry`.

  1. If `state.contextMap` has an entry for `contextIdentifier`:
    1. Initialize `result` to an empty map.
    2. Set `result.state` to `state`.
    3. Set `result.entry` to the value of `contextIdentifier` in `state.contextMap`.
    4. Return `result`.
  2. If `context` is a string:
    1. Fetch the associated context object and set `context` to the value of "@context" in that object.
    2. Set `contextUrl` to the value of `contextIdentifier`.
  3. Otherwise, set `context` to `contextIdentifier`.
  4. Set `result` to the result of , passing `state`, `context`, and `contextUrl` if set.
  5. Return `result`.

Add Context Algorithm

This algorithm takes a map `state`, a context object `context`, and a context URL `contextUrl`, and returns `result`, a map containing maps `state` and `entry`.

  1. If `context` has an entry "@import":
    1. Set `importUrl` to the value of "@import" in `context.
    2. If `state.contextMap` does not have an entry for `importUrl`:
      1. Fetch the context object associated with `importUrl` and set `importContext` to the value of "@context" in that object.
      2. Set `importedContextAdditionResult` to the result of , passing `state`, `importContext` as `context`, and `importUrl` as `contextUrl`.
      3. Set `state` to `importedContextAdditionResult.state` and `importEntry` to `importedContextAdditionResult.entry`.
    3. Otherwise, set `importEntry` to the value of `importUrl` in `state.contextMap`.
    4. Set `context` to a map containing all entries from `context` as well as `importEntry.context`.
  2. Set `termMap` to an empty map.
  3. Set `entry` to be an object containing `context` and `termMap`.
  4. Set `sortedTerms` to the result of sorting the keys in `context` in lexicographic order.
  5. Set `isProtected` to `true` if "@protected" has an entry in `context` and `false` otherwise.
  6. For `term` in `sortedTerms`:
    1. If `term` has an entry in `state.keywordsMap`, proceed to the next iteration of this loop.
    2. Set `definition` to the value of `term` in `context`.
    3. If `definition` is `null`, proceed to the next iteration of this loop.
    4. If `definition` is a string:
      1. Set `newDefinition` to an empty map.
      2. Set the value of "@id" in `newDefinition` to `definition`.
      3. Set the value of `definition` to `newDefinition`.
    5. Set the value of `protected` in `definition` to `isProtected`.
    6. Set the value of `term` in `termMap` to `definition`.
    7. If `term` does not have an entry in `state.termToId`:
      1. Set `termId` to `state.nextTermId`.
      2. Increment `state.nextTermId` by 2.
      3. Set the value of `term` in `state.termToId` to `termId`.
      4. Set the value of `termId` in `state.idToTerm` to `term`.
  7. If `contextUrl` is defined, set the value of `contextUrl` in `state.contextMap` to `entry`.
  8. Otherwise, set the value of `context` in `state.contextMap` to `entry`.
  9. Set `result` to be an empty map.
  10. Set `result.state` to `state` and `result.entry` to `entry`.
  11. Return `result`.

Codecs

The codecs in this section specify exactly how individual values in JSON-LD should be converted to CBOR and vice versa. They are used by the algorithms in the previous section, and allow CBOR-LD to efficiently encode both primitive and non-primitive types as CBOR.

Context Codec

Create Context Encoder

This algorithm takes a map `typeTable` and a value `contextValue` and returns a map `encoderData`.

  1. Initialize `encoderData` to an empty map.
  2. If `contextValue` is not a string, return.
  3. Otherwise, set `contextTable` to the value of "context" in `typeTable`.
  4. Set `encoderData.context` to `contextValue` and `encoderData.contextTable` to `contextTable`.
  5. Return `encoderData`.

Encode Context

This algorithm takes a map `encoderData`, and returns CBOR binary data.

  1. If `encoderData`.`context` has an entry in `encoderData`.`contextTable`, return a CBOR encoding of the value of `encoderData`.`context` in `encoderData` as a Major Type 0 (unsigned integer) object.
  2. Otherwise, return a CBOR encoding of the value of `encoderData`.`context` as a Major Type 3 (text string) object.

Create Context Decoder

This algorithm takes a map `reverseTypeTable`, and returns a map `encoderData`.

  1. Set `reverseContextTable` to the value of "context" in `reverseTypeTable`.
  2. Initialize `decoderData` to an empty map.
  3. Set `decoderData`.`reverseContextTable` to the value of `reverseContextTable` and return `decoderData`.

Decode Context

This algorithm takes a map `decoderData` and a value `value`, and returns a value.

  1. If `value` is not a number, return `value`.
  2. Otherwise, if `decoderData`.`reverseContextTable` has an entry for `value`, return the value of that entry.
  3. Otherwise, throw an error ERR_UNDEFINED_COMPRESSED_CONTEXT.

Value Codec

Create Value Encoder

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToEncode`, and returns a map `encoderData` or `valueToEncode`.

  1. Set `isUrl` to `false`.
  2. If `termInfo.term` is "@id" or "@type", set `isUrl` to `true`.
  3. If the value of "@id" in `termInfo.def` is "@id" or "@type", set `isUrl` to true.
  4. If `termType` is "@id" or "@vocab", set `isUrl` to `true`.
  5. If `isUrl` is `true`, set `tableType` to "url".
  6. Otherwise, if `termType` is defined, set `tableType` to `termType`.
  7. Otherwise, set `tableType` to "none".
  8. If `state.typeTable` has an entry for `tableType`:
    1. Set `subTable` to the value of `tableType` in `state.typeTable`.
    2. If `subTable` has an entry for `valueToEncode`:
      1. Set `intValue` to the value of `valueToEncode` in `subTable`. Set `includeSign` to `false`.
      2. If `state`.`typesEncodedAsBytes` has an entry for `tableType`, set `convertToBytes` to `true`. Otherwise, set `convertToBytes` to `false`.
    3. Otherwise, if `tableType` is not "none" and `valueToEncode` is an integer:
      1. Set `intValue` to the value of `valueToEncode`.
      2. Set `convertToBytes` and `includeSign` to `true`.
    4. If `intValue` is defined:
      1. Initialize `encoderData` to an empty map.
      2. Set `encoderData`.`intValue` to the value of `intValue`, `encoderData`.`convertToBytes` to the value of `convertToBytes`, and `encoderData`.`includeSign` to the value of `includeSign`.
      3. Return `encoderData`.
  9. If `tableType` has an entry in `state.processingModeTypeEncoders`, set `encoderData` to the result of calling the `Create Encoder` algorithm associated with that entry's codec.
  10. If `encoderData` is defined, return `encoderData`.
  11. Return `valueToEncode`.

Encode Value

This algorithm takes a map `encoderData`, and returns CBOR binary data.

  1. If `encoderData`.`convertToBytes` is `true`:
    1. Set `bytes` to the result of converting `intValue` to bytes, using the value of `includeSign` to determine whether the binary representation of the integer should be signed or unsigned.
    2. Return a CBOR encoding of `bytes` as a Major Type 2 (byte string) object.
  2. Otherwise, return a CBOR encoding of `intValue` as a Major Type 0 (unsigned integer) object.

Create Value Decoder

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToDecode`, and returns a map `decoderData`.

  1. Set `isUrl` to `false`.
  2. If `termInfo.term` is "@id" or "@type", set `isUrl` to `true`.
  3. If the value of "@id" in `termInfo.def` is "@id" or "@type", set `isUrl` to `true`.
  4. If `termType` is "@id" or "@vocab", set `isUrl` to `true`.
  5. If `isUrl` is `true`, set `tableType` to "url".
  6. Otherwise, if `termType` is defined, set `tableType` to `termType`.
  7. Otherwise, set `tableType` to "none".
  8. If `state.reverseTypeTable` has an entry for `tableType`:
    1. Set `subTable` to the value of `tableType` in `state.reverseTypeTable`.
    2. Set `useTable` to `false`.
    3. If `valueToDecode` is a byte array and `state`.`typesEncodedAsBytes` has an entry for `tableType`:
      1. Set `useTable` to `true`.
      2. Set `intValue` to the unsigned integer conversion of the `valueToDecode` bytes.
    4. Otherwise, if `valueToDecode` is an integer and `state`.`typesEncodedAsBytes` does not have an entry for `tableType`:
      1. Set `useTable` to `true`.
      2. Set `intValue` to `valueToDecode`.
    5. If `useTable` is `true`:
      1. If `intValue` is not in `subTable`, throw an error ERR_UNKNOWN_COMPRESSED_VALUE.
      2. Otherwise, set `decoded` to the value of `intValue` in `subTable`.
    6. Otherwise, if `valueToDecode` is a byte array and `tableType` is not "none", set `decoded` to the integer conversion of `valueToDecode`.
    7. If `decoded` is defined, initialize `decoderData` to an empty map, set `decoderData`.`decoded` to the value of `decoded`, and return `decoderData`.
  9. If `tableType` has an entry in `state.processingModeTypeDecoders`, set `DecoderData` to the result of calling the `Create Decoder` algorithm associated with that entry's codec.
  10. If `decoderData` is defined, return `decoderData`.
  11. Otherwise, if `valueToDecode` is not an array, initialize `decoderData` to an empty map, set `decoderData`.`decoded` to `valueToDecode`, and return `decoderData`.

Decode Value

This algorithm takes a map `decoderData`, and returns a value.

  1. Return `decoderData`.`decoded`.

CBOR Tag Processing

Get Varint Structure Algorithm

This algorithm takes as input an integer `registryEntryId`, and returns a byte string `prefix`.
  1. If `registryEntryId` is less than 128:
    1. Set `varintEncoded` to the byte encoding of `registryEntryId`.
    2. Set `prefix` to the result of appending `varintEncoded` to the end of the bytes `0xD906`.
  2. Otherwise:
    1. Set `varintArray` to an array containing the varint representation of `registryEntryId`.
    2. Set `varintTagValue` to `varintArray[0]` appended to the end of the bytes `0xD906`.
    3. Set `varintBytesValue` to a CBOR byte string containing the rest of `varintArray` appended to the end of the bytes `0x82`.
    4. Set `prefix` to `varintBytesValue` appended to the end of `varintTagValue`.
  3. Return `prefix`.

Get Registry Entry ID Algorithm

This algorithm takes an encoded CBOR-LD payload `cborldBytes` as input, and returns `suffix`, the main data to be decoded, as well as the `registryEntryId` value that should be used to decompress `suffix`.

  1. If the CBOR tag on `cborldBytes` is not in the range `0x0600`-`0x06FF`, throw an ERR_NON_CBOR_LD_TAG error.
  2. Otherwise, if the CBOR tag on `cborldBytes` is in the range `0x0600`-`0x067F`, set `registryEntryId` to the value of the last byte of the CBOR tag and set `suffix` to the portion of `cborldBytes` after the tag.
  3. Otherwise:
    1. If the last byte of the CBOR tag does not form the first byte of a valid varint, throw an `ERR_INVALID_VARINT_VALUE` error.
    2. If the CBOR tagged item is not an array containing exactly two elements, throw an `ERR_INVALID_VARINT_STRUCTURE` error.
    3. Otherwise, set the value of `registryEntryId` to the value of the varint for which the first byte is the last byte of the CBOR tag and the rest of the varint is the first element in the two element array. Set `suffix` to the value of the second element in the array.
  4. Set `result` to be an empty map.
  5. Set `result`.`suffix` to the value of `suffix` and `result`.`registryEntryId` to the value of `registryEntryId`.
  6. Return `result`.