Introduction and Background

JSON [1] is now a widely used format for data both in web applications and more generally. JSON was designed to be easier to use in the browser with JavaScript, hence the "JS". It has gained momentum for structured data arguably overtaking CSV and XML. Norman Walsh sums this up succinctly in his paper at Balisage in 2016 [3], "If the sweet spot for XML and SGML is marking up 'prose documents', the sweet spot for JSON is collections of atomic values.".

Unlike CSV and XML, JSON is built around maps (key-value pairs) and arrays. JSON is thus much more powerful than CSV because it can represent more complex data structures, but it is much simpler than XML and so easier to implement and use. The origin of XML is in structured documents, i.e. information that contains a significant proportion of readable text. Although XML can and does represent non-document data sets, it is more complicated than it needs to be for this use, resulting in heavy infrastructure to enable it to be used. JSON is simpler but has all that is needed for representing data, and because of its JavaScript roots it is very well supported in browsers. There is, however, a very mature technology stack built around XML, particularly in the area of data (or document) transformation and processing.

The focus of this paper is the comparison of JSON data and the representation of identified changes in JSON. This is of obvious interest to the JSON community, but it is also of interest to the XML community for two reasons. First, it explores how structured data that uses syntax other than explicit markup can be transformed into XML and access the mature processing infrastructure of XML. Second, it explores how technology developed to improve the representation of change in XML can also provide benefit to JSON. This second benefit is realized not because the JSON is transformed into XML, but rather that the techniques for good change representation in XML can also be applied to JSON to provide a better change representation than the JSON Patch format.

There are a number of free tools that will compare JSON data [2] but these are in general simple utilities designed to show changes, typically in a browser, and have limited support for the further processing of those changes. Regarding the representation of the changes in JSON, the standard in this area is the JSON Patch format [4] to represent changes between two JSON data sets. JSON Patch is a transaction-based format, i.e. each operation is a single modification to the structure that needs to be applied before the next change.

The idea of converting JSON to XML is not new: [5] is one of the papers by Steven Pemberton that discusses "invisible XML", i.e. conversion to and from XML. The desire to see the world through 'XML glasses' goes back even further, [6] and techniques for mapping from disparate data sources to XML have been developed [7].

The conversion of JSON to and from XML is now supported by XSLT tools: XSLT 3.0 [9] has support for reading and writing JSON, and XSLT maps are partly designed to handle and correspond to JSON Maps. A presentation on "Transforming JSON using XSLT 3.0" was given at XML Prague 2016 by Michael Kay, Saxonica, [8] but no written paper is available.

The original objective of this work was to demonstrate the use of XML comparison tools to compare JSON data and generate JSON Patch output. But the scope was widened to include other representations of change in JSON in order to better support the processing of changes. JSON Patch is well suited to its goal of providing a patch format to update a JSON data structure, but it is not well suited for other purposes because the context of the changes is not shown. We therefore present a change representation that includes the context of the changes so that new ways of processing and viewing change can be supported.

Conversion of JSON to optimised XML

We used the standard XSLT 3.0 json-to-xml function to convert to XML. Consider a simple example of JSON:

{"Image": {
    "Width": 800,
    "Height": 600,
    "Title": "View from 15th Floor",
    "Thumbnail": {
        "Url": "http://www.example.com/image/481989943",
        "Height": 125,
        "Width": 100
    },
    "Animated": false,
    "IDs": [
        116,
        943,
        234,
        38793
    ]
}}

and using the XSLT 3.0 function json-to-xml, we get this result:

<j:map xmlns:j="http://www.w3.org/2013/XSL/json">
   <j:map key="Image">
      <j:number key="Width">800</j:number>
      <j:number key="Height">600</j:number>
      <j:string key="Title">View from 15th Floor</j:string>
      <j:map key="Thumbnail">
         <j:string key="Url">http://www.example.com/image/481989943</j:string>
         <j:number key="Height">125</j:number>
         <j:number key="Width">100</j:number>
      </j:map>
      <j:boolean key="Animated">false</j:boolean>
      <j:array key="IDs">
         <j:number>116</j:number>
         <j:number>943</j:number>
         <j:number>234</j:number>
         <j:number>38793</j:number>
      </j:array>
   </j:map>
</j:map>

Notice that what JSON refers to as an object is transformed into an XML map element, making use of the map data structure in XSLT 3.0 which supports name/value pairs. Other JSON types use element names corresponding to the type, with an addition of a key where this is relevant, e.g. for object members.

This representation is not ideal for comparison. For example the map (or in JSON terms the object) members have element names that represent the type of member, so alignment in comparison would depend on the type as well as the key. Why might that be a problem? Consider a situation where it is necessary to change the type, as part of an upgrade to the format. We might want to upgrade the 'width' from just a number to an object so that the units of the number could be specified. This is typical of a change that might be made as software is developed and updated - the simple number representaion of width might be found to be insufficient to support a new version of the software because users now need to be able to specify the width in different units.

With this change, an older representation like this:

<j:number key="Width">800</j:number>
would not align naturally (because the element names are different) with the revised representation which now looks like this:
<j:map key="Width">
    <j:number key="value">800</j:number>
    <j:string key="unit">"metre"</j:string>
</j:map>

Although it might be correct in one sense if we represented such a change as a deletion of the first one above, j:number, and addition of the second one, j:map, it would be preferable if these had been identified as related to each other, i.e. what has really happened is that the Width has been changed from a number to a number with a unit. So, to support this, we find that the default representation of JSON in XML is not optimal for our purpose. That is not to say that the default representation is deficient, but for our purposes we prefer a different representation. One of the significant benefits of using XML is that we can quite simply transform it into something more suitable. When we are finished, we can then simply transform it back again.

Therefore we transform the default XML into a more suitable representation, as shown below. Such transformation is very easy to perform in the XML domain, XSLT is well suited to this and it is not difficult to provide the reverse transformation later in the processing pipeline.

<JSON xmlns:deltaxml="http://www.deltaxml.com/ns/well-formed-delta-v1">
   <object deltaxml:ordered="false">
      <member name="Image" deltaxml:key="Image">
         <object deltaxml:ordered="false">
            <member name="Width" deltaxml:key="Width">
               <number>800</number>
            </member>
            <member name="Height" deltaxml:key="Height">
               <number>600</number>
            </member>
            <member name="Title" deltaxml:key="Title">
               <string>View from 15th Floor</string>
            </member>
            <member name="Thumbnail" deltaxml:key="Thumbnail">
               <object deltaxml:ordered="false">
                  <member name="Url" deltaxml:key="Url">
                     <string>http://www.example.com/image/481989943</string>
                  </member>
                  <member name="Height" deltaxml:key="Height">
                     <number>125</number>
                  </member>
                  <member name="Width" deltaxml:key="Width">
                     <number>100</number>
                  </member>
               </object>
               <member name="Animated" deltaxml:key="Animated">
                  <false/>
               </member>
               <member name="IDs" deltaxml:key="IDs">
                  <array>
                     <number>116</number>
                     <number>943</number>
                     <number>234</number>
                     <number>38793</number>
                  </array>
               </member>
            </member>
         </object>
      </member>
   </object>
</JSON>

This structure enables us to align members based on their keys, independent of what type they may be.

There are two additional pieces of information that need to be inserted to provide information to ensure that the correct alignment is performed during the comparison process. These are specific for DeltaXML but the information they provide is needed for any proper comparison alignment. The first of these relates to the order of members in an object. By default, the order of XML elements within a document is significant, so if member elements appear in a different order in two XML files they would be considered to be different. In order to indicate to the alignment process that member elements can appear in any order, a deltaxml:ordered='false' attribute has been added to the object element. The second piece of additional information is also inserted to enable proper alignment of the member elements in the two documents. Members need to be aligned according to their names - they are a key/value pair so we need to use the keys for alignment. Member names are therefore copied into deltaxml:key attributes so they can be used to align members in the two files.

Notice that the array members are not key/value pairs and so are just identified by type. Because they are not keyed, we do not expect to align them using keys - there is further discussion later about how arrays are handled because there are different approaches to the alignment of array members.

Representing changes in JSON

To illustrate how changes are repreented in JSON we will consider a simple example. This is the A version:

{
  "a": "your data",
  "b": "bbc 1",
  "name": "John Joe Smith",
  "age": 21,
  "owner": true,
  "hobbies": [
    "playing guitar badly",
    "reading",
    "Cinema"
  ]
}
and a modifed version, B, of this:
{
  "a": "my data",
  "b": "bbc 2",
  "name": "Mr John Smith",
  "hobbies": [
    "Badminton",
    "guitar",
    "reading"
  ],
  "age": 21,
  "pet": "dog"
}

Notice that although the members are in a different order, they would be aligned by their key.

JSON Patch is a format (identified by the media type "application/json-patch+json") for expressing a sequence of operations to apply to a JSON document; it is suitable for use with the HTTP PATCH method. A JSON Patch document is an array of objects, where each object represents a single operation to be applied to the target JSON document. Operations are applied sequentially in the order they appear in the array. Each operation in the sequence is applied to the target document; the resulting document becomes the target of the next operation. The reasons behind this approach are explained in this blog [https://www.mnot.net/blog/2012/09/05/patch]. The transactional nature means that multiple changes are complex and error-prone in that each successive change relies on the previous change being executed correctly.

The JSON Patch representation of the changes between A and B would be:

[
    {
        "op": "replace",
        "path": "/a",
        "value": "my data"
    },
    {
        "op": "replace",
        "path": "/b",
        "value": "bbc 2"
    },
    {
        "op": "replace",
        "path": "/name",
        "value": "Mr John Smith"
    },
    {
        "op": "remove",
        "path": "/hobbies/2"
    },
    {
        "op": "add",
        "path": "/hobbies/1",
        "value": "guitar"
    },
    {
        "op": "replace",
        "path": "/hobbies/0",
        "value": "Badminton"
    },
    {
        "op": "remove",
        "path": "/owner"
    },
    {
        "op": "add",
        "path": "/pet",
        "value": "dog"
    }
]

The first three operations are easy to understand and apply. The next three modify the hobbies array and here each operation modifies the array so that this modified array is the one that is the subject of the next operation. The first of these array changes,

{
        "op": "remove",
        "path": "/hobbies/2"
    }
results in a new hobbies array:
"hobbies": [
    "playing guitar badly",
    "reading"
  ]

The next operation:

{
        "op": "add",
        "path": "/hobbies/1",
        "value": "guitar"
    }
adds a new array member in position 1 (this is the second position as the numbering starts at zero):
"hobbies": [
    "playing guitar badly",
    "guitar",
    "reading"
  ]
The last operation:
{
        "op": "replace",
        "path": "/hobbies/0",
        "value": "Badminton"
    }
replaces the member in position 0 :
"hobbies": [
    "Badminton",
    "guitar",
    "reading"
  ]
It is obvious that any error that occurs duing this processing, for whatever reason, could have a catastrophic effect on the result because subsequent operations would be incorrectly applied. As deleted or changed values are not recorded in the patch operation, the patch can only be applied in one direction and it is not possible to validate that the correct value is being deleted or changed.

The JSON Patch representation works if it is correctly applied to the right data set, but is useful only for updating one document to the other, it is not easily applied to other change processing. There is no context for the changes, and items that are deleted are not shown so the patch can only work in one direction.

Based on work in XML, we have developed a richer bi-directional representation of change for JSON. It is, like JSON Patch, a valid JSON data set. This delta representation preserves the context of each change as shown below. The key "dx_deltaJSON_delta" introduces the delta object. Each change is shown using an object with a single "dx_delta" member, and within this member each version is shown using, in this case "A" as the first A document and "B" as the second B document. Within each "dx_delta" object, the absence of an "A" member indicates that the item is not in "A", and therefore it has been added in "B". Similarly, the absence of a "B" member indicates that it is not present in "B" and therefore has been deleted in "B". Thus the delta {"dx_delta": {"B": "guitar"}} indicates that this value was present only in the B data set, so has been added. There is nothing in this position in the A data set, so the value is not present. Note that this does not mean that there is a null value at this position.

{"dx_deltaJSON_delta": {
    "a": {"dx_delta": {
        "A": "your data",
        "B": "my data"
    }},
    "b": {"dx_delta": {
        "A": "bbc 1",
        "B": "bbc 2"
    }},
    "name": {"dx_delta": {
        "A": "John Joe Smith",
        "B": "Mr John Smith"
    }},
    "hobbies": [
        {"dx_delta": {
            "A": "playing guitar badly",
            "B": "Badminton"
        }},
        {"dx_delta": {"B": "guitar"}},
        null,
        {"dx_delta": {"A": "Cinema"}}
    ],
    "owner": {"dx_delta": {"A": true}},
    "pet": {"dx_delta": {"B": "dog"}}
}}

This shows only the changes, data that has not been changed has been omitted (in this case, only the age member and one unchanged member of the array, which is represented as null). Notice that for the array changes, the context for each change is clear because the unchanged items are included in order to preserve context correctly and unambiguously.

The advantage of this delta representation is that it is bi-directional and is not transaction based so an incorrect application of one change will not affect other changes. The advantages of being bi-directional are that some validation is possible when a change is applied, e.g. when performing a delete it is possible to check that the correct item is being deleted, and of course the delta can convert A into B as well as convert B into A.

Also, it is possible with this representation to include the unchanged data, as shown below. This is a representation of both data sets merged into one, where the differences are shown within the JSON data. In this particular example, the only unchanged items are age and the array member "reading", which are included here in the full context delta.

{"dx_deltaJSON_delta": {
    "a": {"dx_delta": {
        "A": "your data",
        "B": "my data"
    }},
    "b": {"dx_delta": {
        "A": "bbc 1",
        "B": "bbc 2"
    }},
    "name": {"dx_delta": {
        "A": "John Joe Smith",
        "B": "Mr John Smith"
    }},
    "age": 21,
    "hobbies": [
        {"dx_delta": {
            "A": "playing guitar badly",
            "B": "Badminton"
        }},
        {"dx_delta": {"B": "guitar"}},
        "reading",
        {"dx_delta": {"A": "Cinema"}}
    ],
    "owner": {"dx_delta": {"A": true}},
    "pet": {"dx_delta": {"B": "dog"}}
}}
There are many advantages to having a full representation of the merged data, showing the changes. For example, the full context delta can be processed to provide any combination of the two data sets. Where JSON is used to provide variable data to a template web page, the full context delta allows this template (or a slightly modified version of it) to show where the data has been updated. Users often want to see not just the new version but how it differs from the previous version, and that is made much easier by having this full context delta representation.

A prototype implementation to generate this change format from two JSON data sets is available [10]. Given the ease of processing of XML, the JSON Patch format can also be generated. This prototype is based on conversion of the JSON to XML using XST 3.0, and comparison of the XML.

Representing text changes in JSON

JSON is not as versatile as XML when it comes to text data. A JSON string cannot have structure within it using standard JSON. Fortunately though, many of the considerable problems regarding the proper handling of whitespace in XML have been removed in JSON. JSON is often used to contain quite long strings and when these differ it would be useful to know exactly where they differ rather than just knowing that there is a change. This can be done but of course the changes then need to be represented in the JSON result. Consider the changes between:

A: {"description": "This is a good example of Word by Word processing"}
and
B: {"description": "This is a great example of Word by Word processing"}
which could be represented as:
{"dx_deltaJSON_delta": {"description": {"dx_delta": {
    "A": "This is a good example of Word by Word processing",
    "B": "This is a great example of Word by Word processing"
}}}}
But we cannot see easily where the changes have occurred. Performing a more detailed word-by-word comparison, we can then represent the changes like this:
{"dx_deltaJSON_delta": {"description": {"dx_delta_string": [
    "This is a ",
    {"dx_delta": {
        "A": "good",
        "B": "great"
    }},
    " example of Word by Word processing"
]}}}
To show the changes at the word level, we have represented the text as an array where each member is either a string, indicating unchanged text, or a dx_delta object which indicates a change. The string can be reconstructed by concatenating the array members, selecting the appropriate A or B within a dx_delta object. It would be relatively simple in the context of a web page where JSON data populates some variable text, to show changes by adding formating round the added and deleted text items.The display is more useful if the individual word changes are shown, rather than addition/deletion of complete text strings.

In this situation it may also be useful to perform more intelligent processing of text changes to provide more intuitive display of changes. For example,

A: {"description"  :  "This is a good example of word by word processing"}
and
B: {"description": "When a little bit of change by one person"}
which could be represented as:
{"description": {"dx_delta_string": [
        {"dx_delta": {
            "A": "This is",
            "B": "When"
        }},
        " a ",
        {"dx_delta": {
            "A": "good example",
            "B": "little bit"
        }},
        " of ",
        {"dx_delta": {
            "A": "word",
            "B": "change"
        }},
        " by ",
        {"dx_delta": {
            "A": "word processing",
            "B": "one person"
        }}
    ]}}
but it would have been more useful to have shown these as complete blocks of text, as in
{"description": {"dx_delta": {
        "A": "This is a good example of word by word processing",
        "B": "When a little bit of change by one person"
    }}}
The format allows either representation depending on the particular requirements.

Array alignment

A JSON array is an ordered sequence of zero or more values. When two arrays are being compared, corresponding values need to be aligned with one another. There are several different approaches that can be taken to the way that this alignment is handled. The simplest, and most obvious, is to align each member according to its position, so that the third item in one array is aligned with the third item in the other array and so on. This alignment approach may not always be suitable, for example if an array contains an ordered list of numbers and we want to detect insertions and deletions. In this case, we need to have a best match alignment, i.e. an alignment that will match as many members as possible.

The values in an array may have different types, and an alignment can take account of the types as well as the values. We shall look at some examples to illustrate this.

This example shows two arrays which contain only numbers.

{"IDs": [116, 943, 234, 38793]}
{"IDs": [200, 25, 78, 234, 38793]}
These could be aligned by position:
{"IDs": [116, 943, 234, 38793]}
{"IDs": [200, 25,  78,  234,  38793]}
or they could be aligned using a best match algorithm where equal numbers are aligned if possible, and as a lower priority, a number can be aligned with another number even if it differs in value:
{"IDs": [116, 943,    234, 38793]}
{"IDs": [200, 25, 78, 234, 38793]}

or, if different numbers are not aligned with one another, we could get this alignment:

{"IDs": [116, 943,              234, 38793]}
{"IDs": [          200, 25, 78, 234, 38793]}
This best match approach provides a more optimised result in the sense that there are fewer changes that need to be represented.

This next example shows two arrays which contain both numbers and strings.

{"IDs": [116, 943, "XYZ", 93, 234, 38793]}
{"IDs": [200, "ABC", "DEF", 234, 38793]}
Again, these could be aligned by position:
{"IDs": [116, 943,   "XYZ", 93,   234,  38793]}
{"IDs": [200, "ABC", "DEF", 234,  38793]}
or they could be aligned using a best match algorithm, taking into account the types:
{"IDs": [116, 943,  "XYZ",        234,  38793]}
{"IDs": [200,       "ABC", "DEF", 234,  38793]}

Although an array is supposed to be an ordered sequence, they are sometimes used to represent sets of items simply because there is no JSON object for sets. The situation in XML is similar in that order is always considered to be important (except for attributes, of course), and therefore representation of sets is not natively supported. If an array is being used to represent a set, then the alignment algorithm will need to take this into account. To handle sets, only array values that are exactly equal can be matched up, the other values will either need to be added or deleted.

In some situations members of a set may have some form of key, but in that case the more natural representation in JSON would be objects rather than arrays.

Conclusions

This paper has shown how markup technology can provide benefits to other areas of structured data, in this case JSON. By providing a loss-less, bi-directional transformation from JSON to XML, the powerful processing infrastructure available to XML can be applied to JSON, with access to the results being presented in JSON.

The paper has also shown how technology developed for XML, in this case the representation of changes, can also be applied to JSON. This approach to change representation has proved to be beneficial in XML and it is hoped that the JSON community will be able to gain similar advantages. Although some software developers will be more comfortable using JSON technology rather than XML technology, there are advantages accessing both technology stacks to mix and match as appropriate to get the best of both worlds. The scenario presented in this paper enables access to the XML technology stack with the result transformed back into JSON so that no knowledge of XML is needed.

References

[1] The JavaScript Object Notation (JSON) Data Interchange Format URN: https://tools.ietf.org/html/rfc7159

[2] Online JSON Compare http://json-diff.com

[3] "Marking up and marking down", Norman Walsh, Balisage 2016 http://www.balisage.net/Proceedings/vol17/html/Walsh01/BalisageVol17-Walsh01.html. doi:https://doi.org/10.4242/BalisageVol17.Walsh01

[4] JavaScript Object Notation (JSON) Patch http://tools.ietf.org/html/rfc6902

[5] "Data Just Wants to Be Format-Neutral", Steven Pemberton, CWI http://www.xmlprague.cz/day2-2016/#data

[6] "Looking at the Web through <XML> glasses", Arnaud Sahuguet and Fabien Azavant, http://db.cis.upenn.edu/DL/coopis99_sli.pdf. doi:https://doi.org/ 10.1109/COOPIS.1999.792166.

[7] "Daffodil: Open Source DFDL", Rob Kooper https://opensource.ncsa.illinois.edu/confluence/display/DFDL/Daffodil%3A+Open+Source+DFDL

[8] "Transforming JSON using XSLT 3.0", Michael Kay, Saxonica http://www.xmlprague.cz/day2-2016/#jsonxslt

[9] XSL Transformations (XSLT) Version 3.0 https://www.w3.org/TR/xslt-30/

[10] JSON Compare Online Preview - DeltaXML https://www.deltaxml.com/json-client/

Robin La Fontaine

Robin is the founder and CEO of DeltaXML. His background includes computer aided design software and he has been addressing the challenges and opportunities associated with information change for many years. DeltaXML tools are now providing critical comparison and merge support for corporate and commercial publishing systems around the world, and are integrated into content management, financial and network management applications supplied by major players. Robin studied Engineering Science at Worcester College, Oxford and holds an MSc in Computer Science from the University of Hertford. He is a Chartered Engineer and member of the Institution of Mechanical Engineers. He has three adult children, one granddaughter, and never finds quite enough time for walking, gardening and working with wood.