OT on JSON objects
To the best of our knowledge, based on the current (May 2017) theoretical findings, no proofs for the direct application of OT on JSON objects exist. Therefore, formic transforms JSON objects to trees before applying OT. Transformations for trees have been proven by Davis, Sun and Lu and Jungnickel and Herb. By basing the JSON transformations on the tree transformations, the validity is ensured. Two things are most important for the JSON to tree transformation. Firstly, consistent transformation rules and secondly, unambiguous paths.
A set of eight rules was developed for the JSON object to tree transformation.
- The root of the tree is an object node.
- Every key and value is mapped to its own node.
- Every key must be unique within its sibling nodes.
- A value is always the direct child of its key.
- A key can only have a single child.
- Objects and arrays are represented as individual nodes.
- Only object and array nodes can have multiple children.
- Keys below an object node are sorted by their alphanumerical ordering.
Most of these rules are quite intuitive. Nevertheless, some require a more detailed explanation.
The RFC 7159 allows for application specific behaviour in the presence of duplicated keys. formic enforces unique keys among siblings. In order to be able to identify, where an operation should take place, it is necessary to avoid duplicated keys. Still, within the JSON object the keys do not have to be globally unique. It is sufficient if this is limited to sibling nodes, i.e. nodes with the same parent.
Similar to the reason of having unique sibling keys, this rule is necessary to know where to apply an operation. If the nodes would be in a random order or would be inserted in the order of the operation arrival, inconsistent results could occur. Especially because of the numerical access path (see following section), the ordering is necessary.
To provide a better intuition of the JSON object to tree transformation, the following picture should help. It covers all of the previously presented rules.
Within the code, keys and values are represented as a single node class. Therefore it might happen that nodes contain null as key. E.g. a character node as child of a string node does not have a key.
In order to apply an operation somewhere within the JSON object a path is being used internally. When an objects is being manipulated, the API requires the user to provide a JSON path. This path is simply a list of the keys within the JSON object pointing to the location where the operation should be applied. Still, this JSON path is not being used internally, because a tree requires an access path, which uses numerical indices. Therefore, formic internally transforms this JSON path into an access path. The rules presented in the previous section and the tree transformations make sure that the numerical path leads to consistent results. A visulization is provided below.
