Balisage Paper: JNodes: a New Model for Navigating JSON Trees

About this Paper

Firstly: the status of the work. The QT4 community group has been busy for about three years developing enhancements to the XSLT, XPath, and XQuery languages, with a view to publishing 4.0 versions of these specifications. The work is ongoing and subject to revision and change as the work proceeds. This paper describes one recent change proposal: the group has spent a fair bit of time reviewing it and revising it. At the time of writing, the proposal has not yet been accepted into the status quo draft, but with luck that will change by the time of the conference.

The paper is in three parts, an end, a middle, and a beginning, in that order.

A lot of the thinking behind the proposal was motivated by use cases involving XSLT transformation of JSON, but in fact XSLT is hardly mentioned in the paper. That's because the JNodes proposal described in this paper is designed to provide the foundations for recursive-descent rule-based transformation in the XSLT style, but the actual XSLT machinery to be built on top of these foundations is not yet fully defined or agreed. Watch this space; meanwhile we focus on navigational queries.

The End

This section is designed to illustrate what becomes possible with the new syntax. We'll start with some sample JSON, and show some queries against it.

We'll start with a sample JSON document that appears in RFC 9535, the specification of JSONPath, a query language inspired by XPath 1.0 but designed exclusively for JSON. The example is frankly bonkers, but by choosing it (a) we can compare the XPath 4.0 and JSONPath solutions for the same queries, and (b) we can't be accused of bias by choosing an example that played to our strengths.

Here's the example JSON: a store catalog for a shop that sells four books and a bicycle.

                  
 { "store": {
       "book": [
         { "category": "reference",
           "author": "Nigel Rees",
           "title": "Sayings of the Century",
           "price": 8.95
         },
         { "category": "fiction",
           "author": "Evelyn Waugh",
           "title": "Sword of Honour",
           "price": 12.99
         },
         { "category": "fiction",
           "author": "Herman Melville",
           "title": "Moby Dick",
           "isbn": "0-553-21311-3",
           "price": 8.99
         },
         { "category": "fiction",
           "author": "J. R. R. Tolkien",
           "title": "The Lord of the Rings",
           "isbn": "0-395-19395-8",
           "price": 22.99
         }
       ],
       "bicycle": {
         "color": "red",
         "price": 399
       }
     }
}

We'll start by presenting the example queries given in the JSONPath specification, and showing their XPath 4.0 equivalents.

$.store.book[*].author

/store/book/*/author

$..author

//author

$.store.*

/store/*

$.store..price

/store//price

$..book[2]

//book/*[3]

$..book[2].author

//book/*[3]/author

$..book[2].publisher

//book/*[3]/publisher

$..book[-1]

//book/*[last()]

$..book[0,1]

//book/*[1,2]

$..book[?@.isbn]

//book/*[isbn]

$..book[?@.price < 10]

//book/*[price lt 10]

$..*

//*

Now, the first thing you have probably noticed is that the syntax of all the examples above is pure XPath 3.1 (in fact, it's almost pure XPath 1.0). Essentially what the JNodes proposal does is to bend the data model for maps and arrays so that it is sufficiently close to the data model for XML that the same syntax can be used, with only minor adjustments to the semantics.

With XPath 4.0 and XQuery 4.0 we can go well beyond these simple examples, both using features that are familiar to XPath 3.1 and XQuery 3.1 users, and using new features in 4.0 (some of which, but not all, are related to the use of JNodes).

Here are some more examples (the fourth is XQuery only, the others work in both XPath and XQuery):

distinct-values(//author) => sort()

//author[../category = 'fiction']

//book/*[title='Moby Dick']/preceding-sibling::*[1]

map:merge(
   for $b in //book/*
   group by $cat := $b/category
   return map:entry($cat, count($b)
)

/store/*[.//price gt 100] => jnode-selector()

Now, frankly, the problem with this JSON sample is that it is too simple. The lookup operator in XPath 3.1 is sufficiently powerful to tackle most of these examples. So it's worth a reminder of why improvements were needed:

The Middle

How does it work?

Reusing the XPath path expression syntax to navigate maps and arrays depends on having a data model whose structure is sufficiently similar to the tree structure used to model XML so that the syntax can be interpreted with only small changes to the semantics of particular structures. In particular the syntax of steps (the construct appearing on the right-hand side of the path operator /) can't depend on what type of item is returned by the left-hand operand, because we don't have enough static type information to know whether we are dealing with XML trees or JSON trees: in fact, at the time we parse the query, we have no type information at all.

This means we need to iron out some of the differences between the XML model and the JSON model — or more accurately, we need to find abstractions that work for both cases. (And note, I'm using the term "JSON" loosely here: maps and arrays in XDM are actually a lot richer than those in JSON. For example the keys in a map aren't necessarily strings, and the associated values can be any XDM value, including for example a sequence of maps rather than a single map, or even an XML node.)

What are the important differences?

The solution adopted is to define the concept of JNodes as an analog of the existing XML-based nodes, now called XNodes for differentiation. The abstract superclass is called GNode (for generalized node).

A root JNode is a transient wrapper around a map or array. The children of this root wrap the map entries or array members. It is expected that these wrappers will be created lazily on demand, and discarded when they are no longer needed. A non-root JNode has the following properties:

Now, if we ignore attributes and namespaces, the existing XPath axes can all be defined in terms of (a) the parent and child relationships, and (b) document order (meaning that the children of a node are ordered). If we can define the child axis for JNodes, then we have essentially defined all the XPath axes. For a value that is a single map or array, defining the child axis is easy (it contains one JNode for each map entry or array member). If the value is atomic, or a sequence of atomic items, then the child axis is empty. For a value that might contain multiple maps or arrays, it gets a bit more complicated, which is where the position property comes into play, but we'll ignore that case.

As for document order, this is intuitive in the case of arrays, and for maps, we had already decided that in 4.0, the entries in a map should be ordered. The reason for this is primarily to make serialized JSON human-readable. XML's distinction between attributes (small) and child elements (often large) gives a natural and predictable output structure even if attribute order is not retained; with JSON, outputting deeply-nested properties and simple string-valued properties in random order makes it quite impossible for the human reader to find anything. So with both maps and arrays, the concept of sibling order is well defined.

So the JNode model gives us all the XPath axes, and the only other thing we need to make path expressions work is a suitable set of selectors - the equivalent of the name tests and node tests used in the XML model.

Existing XPath gives us three ways of selecting nodes on an axis (plus the wildcard node() which selects everything). We can select nodes using a (partial or total) match on the name, or a match on the type, or by a general predicate. The use of predicates needs no adaptation to work with JNodes, and the other two mechanisms can be generalized:

The Beginning

This final section examines the background to the JNodes proposal: it looks at some of the formative steps and insights that led up to it, and at some of the wrong turnings that we took along the road.^[1]

The initial introduction of maps into the data model was motivated by the work on streaming in XSLT 3.0. When streaming, you can't visit a node in the source document more than once, which means that when you encounter a node, you may need to remember selected information until it is needed later in the process, and maps seemed a good way of retaining and accumulating that information. We then realised that maps were also useful for processing JSON, and that led in turn to the addition of arrays to the data model. (Arrays were a bit of an afterthought in XSLT 3.0, they were only fully developed in XPath 3.1).

As early as 2016, the year before XSLT 3.0 was finalized, it was clear that there were limitations in the capabilities for transforming JSON structures. At XML Prague in that year I presented a paper [Kay 2016] that examined a couple of fairly simple transformation tasks, and came to the rather unwelcome conclusion that the best way of transforming the JSON was to covert it to XML, perform an XML-to-XML transformation, and then convert the result back to JSON. Ever since then I have been trying to find a better way of doing such transformations natively. There were two main limitations identified: the inability to access properties from ancestors in the tree, and the difficulty of writing selective patterns to match constructs in the JSON tree.

Two years later, at XML Prague 2018, I took a look at the other side of the coin: how to find a data structure for representing XML trees that achieved some of the benefits of the JSON model, in terms of reducing the overhead of making small changes to large trees [Kay 2018a]. In this paper I "invented" the KL-tree, a representation of XML in which there were no persistent parent pointers, but where instead the act of navigating downwards in the tree retained enough context to enable the ancestors to be found on request. After I presented the talk, a member of the audience pointed out very politely that I had reinvented the Zipper structure. Applying such a structure to XML trees remains unfinished business. I got it working, but never got it performing well enough to put into production, largely because the performance couldn't complete with the Saxon TinyTree which relies on node adjacency in memory to achieve its speed. Use of contiguous memory locations for adjacent nodes gives great CPU caching, but of course makes sharing of subtrees impossible.

Also in 2018, this time at Markup UK, I presented a case study on writing an XSD schema validator in XSLT [Kay 2018b]. This is another project that never made it into production, but I learned a lot from the exercise of writing a significant piece of XSLT code that made heavy use of maps and arrays for its working data. In particular, this work led to the introduction of record types (initially called tuple types) which play a significant role in XPath 4.0. But the maps and arrays used here were essentially single-level and the work didn't make any noticeable contribution to solving the JSON transformation problem.

Fast forward to 2020, again in Prague, where I put forward my ideas for an XSLT 4.0 [Kay 2020]. Many of the ideas in that paper have found their way into the current drafts. The paper identified rule-based transformation of JSON structures as an important area for improvement, but had little to offer in the way of concrete suggestions for how to achieve it.

I tried to fill this gap with my paper at Balisage 2022 [Kay 2022]. There were many good ideas in that paper, and many of them found their way into the 4.0 draft specifications and into Saxon, but the section on rule-based transformation is again rather weak. There are ideas that made a difference, but it's clear I was still struggling with the problem.

In retrospect, I think the reason for this was a reluctance to introduce data model changes. I was aware that introducing data model changes in 3.0, to add maps and arrays, was the major reason that development of 3.0 took so long, and I was keen to finish 4.0 in less than a decade. So I self-imposed a rule, no data model changes. But I think what becomes clear from the JNodes proposal in this paper is that if you get the data model right, everything else becomes easy.

My XML Prague paper in 2024 [Kay 2024] shows some recognition of this. In that paper I introduced the idea of adding semi-hidden labels to the results of a lookup operation, where the labels could retain information about the selection path used to retrieve data from the JSON tree. These labels would be accessible to internal operations, to allow matching of nodes in XSLT and upwards navigation. These labelled values can be seen as prototypes of what we now know as JNodes. We adopted labelled values in the draft spec, but they didn't solve all the problems, and alongside them we introduced another capability with overlapping functionality, a construct that allowed the lookup operator to return key/value pairs rather than plain values, using the syntax $map?pair::KEY. It was clear that the two features overlapped, and didn't play well with each other.

Earlier this year I embarked on a case study to examine just how far the changes we had made in 4.0 (specifically in the area of rule-based tranformation) had taken us towards meeting the requirements. I reported on this case study at Markup UK in June 2025 [Kay 2025]. The case study took an existing XML-based application of significant size and complexity (the Java to C# transpiler that Saxonica uses for porting the Java Saxon product to .NET) and examined how feasible it would be to make it work with JSON rather than XML. This exercise generated lots of ideas. JNodes as such do not appear in the write-up: but it was the exercise of conducting this case study and analysing its conclusions that led directly to the formulation of the JNodes proposal a few days later. Indeed, throughout this ten-year journey, all the significant ideas have come from using XSLT to solve challenging but realistic problems and thinking about how it could be made better.

The journey is not quite at its end. I'm pretty confident that the JNode data model provides the right foundation, and we now have very powerful query facilities as a result. There are still two loose ends that need to be tied up: one is defining match patterns for matching JNodes in XSLT, and the other is a "deep update" capability (probably using higher order functions) that makes it simple to define simple changes to trees of maps and arrays (and possibly trees of XNodes as well) without explicit navigation of the entire structure.