A case study for XSLT transformation of JSON: the transpiler

[michaelhkay]

One of the design aims of XSLT 4.0 is that it should be easier to transform JSON. Back in 2016 I published a paper at XML Prague (https://www.saxonica.com/papers/xmlprague-2016mhk.pdf) with the rather disappointing result that for a couple of non-trivial JSON transformation tasks, the easiest solution was to convert the JSON to XML, transform the XML, and then convert it back. In many ways it was that discovery that motivated the whole XSLT 4.0 project. So I want to review to what extent we have solved that problem, and what remains to be done. In particular, I have recently raised a number of open issues related to how we transform JSON-derived trees of maps and arrays using template rules, and I'm not sure we can resolve those issues without testing the proposals against real use cases.

I'm proposing to take as a case study the Java-to-C# transpiler which we described in a 2021 paper at https://www.saxonica.com/papers/markupuk-2021mhk.pdf. This is a real XSLT application in daily use. It invokes the (open source) JavaParser to emit an XML representation of Java source code, it performs various transformations of that XML, and then finally spits out equivalent C# source code. My basic question is: suppose the JavaParser had chosen to emit JSON instead of XML (as it might perfectly reasonably have chosen to do). Would we be able to write the transpiler in XSLT 4.0 to work entirely within the JSON space, avoiding all use of XML?

I chose this case study for several reasons:

• It's entirely plausible that the input might have been JSON rather than XML
• The application relies very heavily (and successfully) on rule-based processing: if we didn't have template rules, then it would be dominated by large xsl:choose statements with hundreds of branches.
• At around 5000 lines of XSLT, it's large enough to be non-trivial, yet small enough to be tractable as a case study.

I looked at a couple of other candidates, and found they were things that could be readily done in XSLT 3.0 without any enhancements. For example we have production XSLT 3.0 code that takes a JSON data feed from our online shop at saxonica.com and uses it to update our sales database and to generate license keys. The JSON is voluminous but the structure is simple, and the constructs in XSLT 3.0 for handling maps and arrays are entirely up to the job. The transpiler differs in that the JSON has a much more interesting recursive structure, making rule-based transformation a natural fit to the task.

I'm not proposing to actually produce a complete replacement of the current transpiler, only to explore the task of doing so in enough detail to get some useful insights. I propose to use this issue tracker to capture my working notes as the study proceeds, but if there are recommendations affecting the 4.0 specs (as seems likely), then I will extract those into separate issues. Perhaps at the end of the process I will write up the case study as a conference paper.

My rough plan is as follows:

1. Explore conversion of the current XML output by JavaParser to JSON using the new elements-to-maps() function. We have a number of open issues on the usability of this function and it will be interesting to see whether we encounter similar difficulties to those that have already been raised, and whether the suggested solutions are appropriate.
2. Convert the xml-to-java stylesheet to work on this JSON input. This stylesheet is not actually a working part of the transpiler, rather it's something we built as a stepping stone; before attempting to convert the XML syntax tree to C#, we felt it would be instructive to write code that converted it back to Java. This is an 820-line stylesheet and it should be feasible to convert it completely.
3. The transpiler currently produces, as an intermediate output, a "digest" file containing summary information about all the classes and methods found in the Java code, and their subtyping/override relationships. We then have a process that augments this digest with attributes that are needed by the C# generation, for example which methods to label with "virtual" or "override" modifiers. I propose to experiment with producing (and transforming) this digest in JSON rather than XML format.
4. Examine the XSLT code that generates C# output to look for features that appear to be tricky to convert, for example anything that uses the parent or ancestor axis, and study to what extent we now have the capability in XSLT 4.0 to handle those situations.

Using this format (a GitHub issue) to record progress carries a risk that there will be comments that take things off at a tangent. Please help by resisting that temptation: if there are interesting issues raised in your mind, please take those up as separate issues.

[michaelhkay]

The XML emitted by the JavaParser has an interesting structure. For example a conditional if (iter.next() != null) {iter.close(); return BooleanValue.FALSE} looks like this:

                     <statement nodeType="IfStmt">
                        <condition nodeType="BinaryExpr" operator="NOT_EQUALS">
                           <left nodeType="MethodCallExpr" >
                              <name nodeType="SimpleName" identifier="next"/>
                              <scope nodeType="NameExpr">
                                 <name nodeType="SimpleName" identifier="iter"/>
                              </scope>
                           </left>
                           <right nodeType="NullLiteralExpr"/>
                        </condition>
                        <thenStmt nodeType="BlockStmt">
                           <statements>
                              <statement nodeType="ExpressionStmt">
                                 <expression nodeType="MethodCallExpr" >
                                    <name nodeType="SimpleName" identifier="close"/>
                                    <scope nodeType="NameExpr">
                                       <name nodeType="SimpleName" identifier="iter"/>
                                    </scope>
                                 </expression>
                              </statement>
                              <statement nodeType="ReturnStmt">
                                 <expression nodeType="FieldAccessExpr">
                                    <name nodeType="SimpleName" identifier="FALSE"/>
                                    <scope nodeType="NameExpr" UNRESOLVED="BooleanValue">
                                       <name nodeType="SimpleName" identifier="BooleanValue"/>
                                    </scope>
                                 </expression>
                              </statement>
                           </statements>
                        </thenStmt>
                     </statement>

The content model of an element here is determined not by the element name, but by the value of the nodeType attribute: for example, if @nodeType="BinaryExpr" then the element has children (left, right); if @nodeType="IfStmt" then the element has children (condition, thenStmt, elseStmt), and if @nodeType="BlockStmt" then the children are a statements element containing a sequence of statement elements. Similarly a MethodCallExpr has children name , scope and (not present here) arguments.

(Is this what SGML old-timers used to call "architectural forms"?)

In consequence, much of the transpiler consists of template rules in the form match="*[@nodeType='MethodCallExpr']", rather than matching by element name.

Because the content model depends on the nodeType attribute and not on the element name, it's hard to write an XSD schema for this, and it also means that the design of elements-to-maps doesn't work too well, because that also assumes that structure depends on element name. One possibility we might explore is to turn the nodeType attribute into a child element so in place of <thenStmt nodeType="BlockStmt">...</thenStmt> we have <thenStmt><BlockStmt>...</BlockStmt></thenStmt>.

[michaelhkay]

This is what elements-to-maps() does with this fragment, when defaulting all options. (More precisely, this is a fragment of the result of applying elements-to-maps() to the containing XML document:

{
                  "@nodeType": "IfStmt",
                  "condition": {
                    "@nodeType": "BinaryExpr",
                    "@operator": "NOT_EQUALS",
                    "left": {
                      "@nodeType": "MethodCallExpr",
                      "name": { "@nodeType":"SimpleName", "@identifier":"next" },
                      "scope": {
                        "@nodeType": "NameExpr",
                        "name": { "@nodeType":"SimpleName", "@identifier":"iter" }
                      }
                    },
                    "right": { "@nodeType":"NullLiteralExpr" }
                  },
                  "thenStmt": {
                    "@nodeType": "BlockStmt",
                    "statements": [
                      {
                        "@nodeType": "ExpressionStmt",
                        "expression": {
                          "@nodeType": "MethodCallExpr",
                          "name": { "@nodeType":"SimpleName", "@identifier":"close" },
                          "scope": {
                            "@nodeType": "NameExpr",
                            "name": { "@nodeType":"SimpleName", "@identifier":"iter" }
                          }
                        }
                      },
                      {
                        "@nodeType": "ReturnStmt",
                        "expression": {
                          "@nodeType": "FieldAccessExpr",
                          "name": { "@nodeType":"SimpleName", "@identifier":"FALSE" },
                          "scope": {
                            "@nodeType": "NameExpr",
                            "name": { "@nodeType":"SimpleName", "@identifier":"BooleanValue" }
                          }
                        }
                      }
                    ]
                  }
                },

At first sight this looks quite reasonable, and certainly something that's possible to work with, and something that's not structurally different from what the JavaParser people might have chosen to emit if they had been outputting JSON directly.

Looking in more detail, the only real failure is in handling elements with a single child. For example we get:

            "thrownExceptions": { "thrownException":{
                "@nodeType": "ClassOrInterfaceType",
                "@RESOLVED_TYPE": "net.sf.saxon.trans.XPathException",
                "name": { "@nodeType":"SimpleName", "@identifier":"XPathException" }
              } }

which should really be a list, because in the general case thrownExceptions will have one-or-more thrownException children. There are other examples of the same problem. There are two ways we could try and tackle this: build an explicit list of elements to be treated as list-valued, or use the "uniform" option and give elements-to-maps a larger sample of content to work with.

(As it happens, the XML adopts a convention that list-valued elements always have a name ending in "s" that pluralises the name of the child element, even when this leads to names like properties having children called propertie. It's hard to see how we could take advantage of this, except perhaps by generating the list of list-valued element names by querying the source XML to find elements that follow this pattern).

[michaelhkay]

As suggested in #1645 I experimented with adding the layout to the element name for diagnostics. This gives us:

               {
                  "@nodeType": "IfStmt",
                  "condition (RECORD)": {
                    "@nodeType": "BinaryExpr",
                    "@operator": "NOT_EQUALS",
                    "left (RECORD)": {
                      "@nodeType": "MethodCallExpr",
                      "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"next" },
                      "scope (RECORD)": {
                        "@nodeType": "NameExpr",
                        "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"iter" }
                      }
                    },
                    "right (EMPTY-PLUS)": { "@nodeType":"NullLiteralExpr" }
                  },
                  "thenStmt (RECORD)": {
                    "@nodeType": "BlockStmt",
                    "statements (LIST)": [
                      {
                        "@nodeType": "ExpressionStmt",
                        "expression (RECORD)": {
                          "@nodeType": "MethodCallExpr",
                          "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"close" },
                          "scope (RECORD)": {
                            "@nodeType": "NameExpr",
                            "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"iter" }
                          }
                        }
                      },
                      {
                        "@nodeType": "ReturnStmt",
                        "expression (RECORD)": {
                          "@nodeType": "FieldAccessExpr",
                          "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"FALSE" },
                          "scope (RECORD)": {
                            "@nodeType": "NameExpr",
                            "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"BooleanValue" }
                          }
                        }
                      }
                    ]
                  }
                },
                {
                  "@nodeType": "ReturnStmt",
                  "expression (RECORD)": {
                    "@nodeType": "FieldAccessExpr",
                    "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"TRUE" },
                    "scope (RECORD)": {
                      "@nodeType": "NameExpr",
                      "name (EMPTY-PLUS)": { "@nodeType":"SimpleName", "@identifier":"BooleanValue" }
                    }
                  }
                }
              ]
            },

I can certainly see the value of this. (There is one problem though: because the keys in the map are changed, any subsequent processing of the map is likely to fail.)

Note that this XML vocabulary does not use text nodes: all the leaf information goes into attribute nodes.

[michaelhkay]

My next attempt was to use the "uniform" option to analyze the full XML (2144 files). I used this query:

let $all := collection('file:///Users/****/ee_xmlout?select=*.xml;recurse=yes')/*
let $maps := elements-to-maps($all, {'uniform':true()})
return array {
  $maps[ ??"@identifier" = "AllDifferent" ]
}

and it threw this error:
SERE0022 Key value "import (RECORD)" occurs more than once in JSON map

I think that must be a Saxon bug: elements-to-maps should never generate a map that can't be serialized.

[michaelhkay]

I've made some experimental changes to the Saxon elements-to-maps implementation, including an option to export the layout options inferred by uniform="yes" and then use them in a subsequent call to elements-to-maps; this means I can get layout options by scanning lots of sample documents and then use them to process one particular document. I changed the attribute-marker to "_" and the relevant JSON fragment now looks like this:

{"_nodeType":"IfStmt",
                 "condition":{"_nodeType":"BinaryExpr",
                   "_operator":"NOT_EQUALS",
                   "left":{"_nodeType":"MethodCallExpr",
                     "_RETURN":"net.sf.saxon.value.AtomicValue",
                     "_RESOLVED_TYPE":"com.saxonica.functions.qt4.DuplicateValues.DuplicatesIterator",
                     "name":{"_nodeType":"SimpleName",
                       "_identifier":"next"
                     },
                     "scope":{"_nodeType":"NameExpr",
                       "_RESOLVED_TYPE":"com.saxonica.functions.qt4.DuplicateValues.DuplicatesIterator",
                       "name":{"_nodeType":"SimpleName",
                         "_identifier":"iter"
                       }
                     }
                   },
                   "right":{"_nodeType":"NullLiteralExpr"
                   }
                 },
                 "thenStmt":{"_nodeType":"BlockStmt",
                   "statements":[{"_nodeType":"ExpressionStmt",
                       "expression":{"_nodeType":"MethodCallExpr",
                         "_RETURN":"void",
                         "_RESOLVED_TYPE":"com.saxonica.functions.qt4.DuplicateValues.DuplicatesIterator",
                         "name":{"_nodeType":"SimpleName",
                           "_identifier":"close"
                         },
                         "scope":{"_nodeType":"NameExpr",
                           "_RESOLVED_TYPE":"com.saxonica.functions.qt4.DuplicateValues.DuplicatesIterator",
                           "name":{"_nodeType":"SimpleName",
                             "_identifier":"iter"
                           }
                         }
                       }
                     },
                     
                     {"_nodeType":"ReturnStmt",
                       "expression":{"_nodeType":"FieldAccessExpr",
                         "_RETURN":"net.sf.saxon.value.BooleanValue",
                         "_RESOLVED_TYPE":"net.sf.saxon.value.BooleanValue",
                         "name":{"_nodeType":"SimpleName",
                           "_identifier":"FALSE"
                         },
                         "scope":{"_nodeType":"NameExpr",
                           "_UNRESOLVED":"BooleanValue",
                           "name":{"_nodeType":"SimpleName",
                             "_identifier":"BooleanValue"
                           }
                         }
                       }
                     }
                   ]
                 }
               },

This time I've included some uppercase property names which result from Saxon calling the "symbol solver" in JavaParser to infer type information.

I'm now going to look at how to write XSLT 4.0 code to convert this back to Java.

I'm starting with a stylesheet designed to do this with the XML form of the data, and adapting it as needed.

Many of the template rules are of the form

<xsl:template match="*[@nodeType='ReturnStmt']">
      <xsl:call-template name="indent"/>
      <xsl:text>return </xsl:text>
      <xsl:apply-templates select="*"/>
      <xsl:text>;{$NL}</xsl:text>
   </xsl:template>

and there are two things we need to change here: the match pattern, and the apply-templates call.

We can change this one to:

 <xsl:template match=".[?_nodeType='ReturnStmt']">
      <xsl:call-template name="indent"/>
      <xsl:text>return </xsl:text>
      <xsl:apply-templates select="?expression"/>
      <xsl:text>;{$NL}</xsl:text>
   </xsl:template>

The "." in the match pattern matches anything, but the lookup in the predicate will fail unless it's a map or an array; a failure while evaluating a pattern is treated as "no match" so that's OK (apart perhaps from performance implications in Saxon of throwing and catching errors...). Instead of "." we could write ~map(*) or ~record(_nodeType, *) but it doesn't add much value.

We can't do <xsl:apply-templates select="?*"/> because we no longer have a separation between attributes and children; ?* would also select the _nodeType property. There's also no simple way of selecting all properties other than _nodeType. We could perhaps match _nodeType in a separate "do nothing" template rule.

I'll convert the simple template rules following this pattern and then report on those that are trickier.

[michaelhkay]

There are places where we want to match by the key rather than by a property. At the root level of the JSON we have:

{"root": {
    "_nodeType":"CompilationUnit",
   "packageDeclaration":{"_nodeType":"PackageDeclaration",
                                           "name": ...}
   "imports": [...]
   "types": [ {"type": .... } ]
}

If we're processing the root, how do we apply templates to the packageDeclaration?

I think we have to process a map by applying templates to its entries. This is articulated in the current 4.0 spec for the shallow-copy-all mode of processing - but the implications on match patterns aren't really worked through.

We could model the entries as singleton maps, or as key value pairs. Whichever we do we have to ask how the entry would be matched, and the obvious answer is by a pattern of the form match="?root" or match="?packageDeclaration" (syntax which is currently undefined). It then makes sense for the context item within the template rule (and within predicates of the match pattern) to be the corresponding value.

So this suggests the principles:

• xsl:apply-templates with no select attribute (when the context item is a map) effectively does select="map:entries(.)"
• match="?xyz" matches a map entry (a singleton map) whose key is "xyz"
• the context value within that template rule is the value part of the map entry. Note this is a value, not always an item.

On this basis we could write the top-level processing of our JSON document as:

<xsl:template name="xsl:initial-template">
    <xsl:apply-templates select="json-doc(...) => map:entries()"/>
 </xsl:template>

 <xsl:template match="?root">
     <xsl:apply-templates>
        <xsl:with-param name="indent" select="0" tunnel="yes"/>
     </xsl:apply-templates>
  </xsl:template>
  
  <xsl:template match="?packageDeclaration">
     <xsl:text>package {f:qualifiedName(?name)};{$NL}</xsl:text>
  </xsl:template>

  <xsl:template match="?imports">
     ...
  </xsl:template>

  <xsl:template match="?types">
     ...
  </xsl:template>

  <xsl:template match="?_nodeType"/>

I'm not really comfortable with this, however. It feels wrong that the thing that we're matching in the match pattern is a map entry, but the thing that we're processing in the body of the template rules is the value part of the map entry; that just feels like it's calling for trouble.

If we used key-value-pair records instead of singleton maps to represent map entries, it would become (assuming KVP is available as a named record type):

<xsl:template match="KVP[?key='packageDeclaration']">
     <xsl:text>package {f:qualifiedName(?value?name)};{$NL}</xsl:text>
</xsl:template>

which is much clunkier syntax, but conceptually cleaner.

It almost feels better to invent new constructs:

<xsl:process-map-entries select="$map"/>

<xsl:map-entry-template key="packageDeclaration">

[michaelhkay]

An alternative approach is that we apply-templates to the values (not the entries), and rely on the fact that because the whole tree is pinned, the values are labelled with the corresponding key. The apply-templates would then have (implicitly or expllicitly) select="?*", and the match pattern, unless we invent new syntax, would be something like .[label()?key = 'imports']. We could interpret the pattern ?imports as having that meaning.

[michaelhkay]

I'm going to focus now on writing this stylesheet using facilities currently defined in XSLT 4.0, in order to discover where the rough edges are, and then we'll think about new features to ease the pain when we've done that.

So, given this structure:

{"root": {
    "_nodeType":"CompilationUnit",
   "packageDeclaration":{"_nodeType":"PackageDeclaration",
                                           "name": ...}
   "imports": [...]
   "types": [ {"type": .... } ]
}

how do I apply-templates to all the "children" of "root" except for "_nodeType"?

There are two places to do the filtering, in the apply-templates call, and in the template rules.

Possible ways of doing it in apply-templates:

- select="map:remove(., '_nodeType')?*"
- select="?[?key ne '_nodeType']?*"
- select="?pairs::*[?key ne '_nodeType']?value"

In Saxon, the last is probably the most performant, which is a little unfortunate, because the other expressions are shorter. Of course there's always room for new optimizations.

Doing it through template rules? Without relying on values being pinned, the only way is

<xsl:template match="type(xs:string)"/>

which is a tad unselective. If the values are pinned, then we can do

<xsl:template match="type(xs:string)[label(.)?key = '_nodeType']"/>

which feels rather clumsy.

We could dream of

<xsl:template match="🗝️_nodeType"/>

[michaelhkay]

Noted that with "predicate patterns" there's no equivalent to the union operator - union, intersect, and except patterns apply only to templates that match nodes.

[michaelhkay]

I've now got the stylesheet to run to completion, though the output isn't yet quite right. Most of the template rules have the general form

   <xsl:template match=".[?_nodeType='BinaryExpr']">
      <xsl:text>(</xsl:text>
      <xsl:apply-templates select="?left"/>
      <xsl:text>{$operators(?_operator) otherwise ?_operator}</xsl:text>
      <xsl:apply-templates select="?right"/>
      <xsl:text>)</xsl:text>
   </xsl:template>

So far I've managed to avoid relying on the tree being pinned. The main limitation of that is that I can't match KVPs by their key. Matching by the _nodeType property works well for this particular vocabulary.

Converting the stylesheet from one that processed XML to one that processed JSON was reasonably straightforward - mainly a question of fixing one type error at a time.

The match patterns such as .[?_nodeType='BinaryExpr'] give me a lot of Saxon warnings because they produce a type error when matched against something that isn't a map. There are several ways I could improve that in Saxon (suppress the warnings entirely; recognize statically that the pattern can only match a map, and don't evaluate it against anything else; etc). I could also avoid the warnings by writing map(*)[...] in place of .[...]. Or I could have a higher-priority template rule that matches non-maps.

[michaelhkay]

I've now got the JSON-to-Java stylesheet working to the extent that it is producing satisfactory results for a couple of reasonably-sized Java modules; it's not yet production-quality, but it's good enough that we can stand back and see what we've learned.

I was able to do it entirely without relying on the structure being "pinned": there was no need for any upward navigation. To a considerable extent that's a fortunate accident of the way this particular vocabulary is designed: the processing of individual records depends on the _nodeType property of the record, and not on its key within the containing record. There was one case where I needed to match on the record type: that was because the XML-to-JSON conversion had been done in a slightly odd way, which I suspect is because the XML being analysed had two elements with the same name ("types") but with different content models.

The bottom-line conclusion is that it is possible, and not terribly difficult, to write this particular transformation using XSLT 4.0 in its current state.

Observations:

1. There's no equivalent to match="/" - no specific way to match the root of the tree. I got around that by using match="record(root)" - that is, I had to know what I expected to find at the root of the tree.
2. It took me a while to get used to writing if (exists(?x)) ..." rather than if(?x)`. But so long as ?x selects a map, you get a decent error message: a map item has no EBV. I considered whether we should define an EBV here, but it involves an arbitrary decision whether an empty map is truthy or falsy, and people are going to get it wrong either way, so I think an error is actually better.
3. Almost all the template rules are matching maps. The only template rule that matches arrays is a generic shallow-copy rule <xsl:template match="array(*)"><xsl:apply-templates select="?*"/></xsl:template>. But in most cases we're not using that, because when we expect a property to be array-valued (for example "modifiers": [{ ... }, { .... }]) then we generally do <xsl:apply-templates select="?modifiers?*"/>, processing the array members directly.
4. As a result of the way the JSON is generated from XML (but this would probably happen anyway), the properties in a map tend to be of three kinds:
   -- string-valued properties such as "_identifier": "n"
   -- map-valued properties such as "thenExp": { ..... }
   -- array-valued properties such as "statements": [ { ..... }, {..... }]

We typically process the string-valued properties using <xsl:value-of select="?_identifier"/>. We don't attempt to apply-templates to them. That's fine. But sometimes we want to apply-templates to all children except the string-valued ones: that's currently difficult. With a type filter on lookup expressions we could do select="?~(map(*)|array(*))". But it would also be nice to have an "except" capability: select="?(* except _identifier)", or `select="* except ~xs:string".

Using map:remove for this feels very unnatural and is probably likely to be inefficient: select="map:remove(., "_identifier")?*". Another possibility is select="?pairs::*[?key != "_identifier"]?value", which also feels clumsy.

Template rules in the original XML-based stylesheet sometimes matched the element name, and sometimes the @nodeType attribute. In the replacement, they always match the attribute, because matching the key would require (a) ensuring that the map is pinned, and (b) accessing the key using a messy construct such as match=".[label()?key = 'NNN']". We definitely need a simple construct to match values by their corresponding key.