Balisage Paper: Two Paths are Better than One

XPath

XPath 1.0 itself became a recommendation in 1999; the latest version, 3.1, in 2017; and an updated next generation version 4.0 is being worked on currently. While 3.1 offers significant improvements over 1.0, the basic underlying mechanism for addressing nodes in the XML tree remains the same. In fact, the tool I use most often for simple XPath execution (i.e., use of XPath other than in XSLT or Schematron) is based on XPath 1.0.

Commandline

Wile I love oXygen (it is the only payware on my main system), I primarily work on the commandline. There are, not surprisingly, quite a few utilities for using XPath on the commandline.^[10] My favorite, by far, is xmlstarlet, but I do not claim that it is the best, only that I like it the most, probably because it was the first one I started using seriously. I tried writing my own a few years ago, and while miserable failure would be an exaggeration, roaring success would be a far greater exaggeration. My program, a bash script based on the xpath++ command, had the signature

        $ xpath.bash [-1|-2|-3] <XPath expression> <XML file>

I wrote it, in part, because I felt a bit too constrained by the XPath 1.0 limitation of xmlstarlet. But even on those rare occasions when my program was working, I found that it was not powerful enough, even though it permitted XPath 3.1. It slowly dawned on me that what made (my use of) xmlstarlet so powerful was the capability to do something else with the results of XPath A, for example to execute an XPath B from every selected node. After all, that’s what makes Schematron so powerful, right?

Schematron

Schematron,^[11] which can be very useful for querying XML data, is basically just that — the capability to test any XPath B (the @test attribute) from every node selected by any XPath A (the @context attribute). Sure, it adds other twists to this basic concept — for starters, every XPath B is evaluated as a Boolean. But it also has the capability to insert an XPath into your output message (with <sch:value-of>), abstract patterns, the clever feature that only the first XPath A within a <pattern> is executed, and importantly the ability to store the results of an XPath as a “variable”.^[12] And although those extra capabilities and scaffolding are important, it seems to me that the power of Schematron comes from this basic capability to evaluate XPath B from each node selected by XPath A.

As an example, consider the following pattern which tests that the values of @maxOccurs and @minOccurs are usable.

  <sch:pattern id="att.repeatable-MINandMAXoccurs">
    <sch:rule context="*[ @minOccurs  and  @maxOccurs ]">
      <sch:let name="min" value="@minOccurs cast as xs:integer"/>
      <sch:let name="max" value="if ( normalize-space( @maxOccurs ) eq 'unbounded')
                                 then -1
                                 else @maxOccurs cast as xs:integer"/>
      <sch:assert test="$max eq -1  or  $max ge $min">
        @maxOccurs should be greater than or equal to @minOccurs
      </sch:assert>
    </sch:rule>
    <sch:rule context="*[ @minOccurs  and  not( @maxOccurs ) ]">
      <sch:assert test="@minOccurs cast as xs:integer lt 2">
        When @maxOccurs is not specified, @minOccurs must be 0 or 1
      </sch:assert>
    </sch:rule>
  </sch:pattern>

This pattern uses four XPath tests and two assignments. (The values that are assigned are expressed in XPath as well, but this is not particularly germane to the argument here.) I submit that if the job of these four XPaths were assigned to a single XPath, the result is significantly harder to decipher, whether intermediate variables are used or not. Here is the same test using intermediate variables (as the Schematron does):

        if ( @minOccurs  and  not( @maxOccurs ) ) then
          if ( @minOccurs cast as xs:integer ge 2 ) then
            'When @maxOccurs is not specified, @minOccurs must be 0 or 1'
          else ''
        else if ( @minOccurs  and  @maxOccurs ) then
          let $max := if ( normalize-space( @maxOccurs ) eq 'unbounded')
                      then -1
                      else @maxOccurs cast as xs:integer,
              $min := @minOccurs cast as xs:integer
          return
          if ( $max eq -1  or  $max ge $min ) then
            ''
          else
            '@maxOccurs should be greater than or equal to @minOccurs'
        else ''

Without the intermediate variables comprehension is marginally more difficult:

        if ( @minOccurs  and  @maxOccurs ) then
          if ( @maxOccurs eq 'unbounded'
               or
               (
                 if ( @maxOccurs castable as xs:integer )
                 then xs:integer( @maxOccurs ) ge xs:integer( @minOccurs )
                 else false()
                )
              )
          then ''
          else '@maxOccurs should be greater than or equal to @minOccurs'
        else
          if ( @minOccurs  and  not( @maxOccurs ) ) then
            if ( @minOccurs cast as xs:integer gt 1 ) then
              'When @maxOccurs is not specified, @minOccurs must be 0 or 1'
            else ''
          else ''

And, not surprisingly, without whitespace (or color syntax highlighting or some other aid for the human reader), all hope is lost:

if (@minOccurs and not(@maxOccurs)) then if (@minOccurs cast as xs:integer ge 2) then 'When @maxOccurs is not specified, @minOccurs must be 0 or 1' else '' else if (@minOccurs and @maxOccurs) then let $max := if (normalize-space(@maxOccurs) eq 'unbounded') then -1 else @maxOccurs cast as xs:integer, $min := @minOccurs cast as xs:integer return if ($max eq -1 or $max ge $min) then '' else '@maxOccurs should be greater than or equal to @minOccurs' else ''

While the loss of whitespace would also make the XSLT version very hard to read, lots of XML tools will easily indent it in a reasonable fashion. (E.g., oXygen has a “Format and Indent” capability; or xmllint --format ugly_input.xml > prettier_output.xml.^[13])

Real or imagined?

Of course this assertion, that two XPaths are more powerful than one, is not strictly true. Executing two XPath path expressions in a row is not much different from tacking one onto the other. That is, executing XPath B from each node selected by XPath A is not significantly different from XPath A / XPath B. Furthermore, in XPath 3.1 we have the simple mapping operator (‘!’) so if items instead of nodes are involved, one could use XPath A ! XPath B.

So if my two XPaths (A and B) could have easily been expressed as a single XPath (let’s call it AB), then why do I think it so much better to be able to express them separately? For at least two reasons. First because of human cognition, and second because of what else can be done in addition to XPath B at each node selected by XPath A.

Human cognition — bears of very little brain

Far be it from me to imply that any in the audience or reading this paper is of very little brain, except insofar as, like me, your brain is generally bigger when you write a complex XPath (or any other snippet of complicated code) than it is when you try to read and understand it months or years later. And whether the author of an XPath is of big brain or not, it is almost always the case that someday someone of smaller brain (or, at least, of lesser understanding of the task at hand) will be reading it.

That is, I assert that readability is usually a more important feature of an XPath in particular, and computer code in general, than is brevity or execution efficiency. For starters [p]rogrammers think they get paid to write code, but the truth is, we spend a lot more time reading it than writing it. (NTW1). Given that programmer time in general, and my time in particular, is quite valuable, writing XPaths so that they can be read and understood quickly is valuable.

Thus the divide and conquer approach^[14] of writing complicated chunks of code, including XPaths, can be quite advantageous. This method, of course, is a method for making it easier to write code; my contention here is that it can also make it easier to read the code. Thus I am thinking of this as divide for comprehension instead (although perhaps divide to comprehend is snappier).

As a simple example, the equivalent of the following XPath appears in an obfuscation program I wrote (inspired by and in part based on ERHobx):

        ( ( ( $seed * $b + 1 ) mod $m ) + 1 + $low + $me ) mod ( $high - $low + 1 ) + $low

While it is not impossible to figure out what is going on here, this seems like a reasonable candidate for the Bet you can’t tell me what this does game.^[15] (It helps to know that all the variables are declared as xs:integer, and that $me is between $low and $high.) When re-written as two XPaths (here using XSLT variables), it becomes much easier (although still not easy) to make sense of:

        <xsl:variable name="random" select="( ( $seed * $b + 1 ) mod $m ) + 1"                         as="xs:integer"/>
        <xsl:variable name="result" select="( $random + $low + $me ) mod ( $high - $low + 1 ) + $low"  as="xs:integer"/>

While this code is still not at all obvious at first glance, after a few minutes puzzling one can figure out that $random is a pseudorandom number generated by a linear congruential approach, and $result is thus a pseudorandom number between $low and $high that is based on $me.

It is worth noting, by the way, that the length of an XPath, even if cleverly measured in tokens or terms rather than as the raw number of characters, is not necessarily a good measure of its complexity. For example, the longest XPath I have ever written (before variable substitution, at least) is 45,992 characters long, or 41,994 without spaces, but is very easy to understand. It was written for the project I presented last year, and is nothing more than a single sequence of the first 3,999 positive integers represented in Roman numerals, except those that actually spell out an English word (i.e., ‘I’ and “MIX”) are recorded as a zero-length string instead.

Conversely, some reasonably short XPaths can be quite difficult to decipher. For example, the above example of pseudorandom number generation in a single XPath has only 59 characters other than ignorable whitespace.

Other things

In a corpus of a particular journal I was working with each article is encoded as a TEI document which has a root <TEI> element which itself has two children: <teiHeader> for metadata and <text> for the content of the article (including its bibliography, etc.). Each article has, at a specific spot in the <teiHeader>, a pair of <idno> elements to specify to which volume and issue of the journal the article belongs. I wanted to ask the question “How many articles are in each issue of volume 4?”.

I performed this task as a single one-liner in bash:

        $ xsel -t -m "/*/t:teiHeader//t:idno[@type='volume'][.='004']" -v "../t:idno[@type='issue']" -n /path/to/articles/*.xml | rank

That takes some unpacking.

It is not particularly difficult to whip up an XSLT or XQuery program that reports the same information in a single XPath. But I submit that, presuming the reader has a good knowledge of the host languages involved (in this case bash on one side and either XSLT or XQuery on the other), the shell one-liner is far easier to write, and somewhat easier to understand.

For example, the following XPath (3.1) does a similar job.

        let $articleCorpus := collection('/path/to/articles?select=*.xml')
        return
          let $results :=
            let $v4issues := $articleCorpus/TEI/teiHeader[.//idno[@type eq 'volume'] ne '004']//idno[@type eq 'issue']/text()
            return
              for $thisIssueNum in distinct-values( $v4issues!sort(.) )
              return count( $v4issues[ . eq $thisIssueNum ] )||' '||$thisIssueNum||'
'
          return sort( $results, (), function($result) { tokenize($result)[1] cast as xs:integer } )

^[21]

The result is only “similar” because while the same values are returned in the same order, the whitespace is not quite as nice. Note that this is not a direct comparison of one XPath to two, in that in my shell one-liner (using “divide to comprehend”) the job of counting occurrences and sorting the results has been factored out of the realm of XPath into a simple bash pipeline. If we similarly factor out that work into the host language (in the example below XSLT) we see that a major portion of the advantage of my bash one-liner is that this process of sorting the unique values of the sequence by how many times each occurs is so tersely expressed.

        <xsl:variable name="v4issues" select="$allArticles/TEI/teiHeader[.//idno[@type eq 'volume'] eq '004']//idno[@type eq 'issue']/text()"/>
        <xsl:variable name="uniq_v4issues" select="distinct-values( $v4issues )"/>
        <xsl:for-each select="$uniq_v4issues">
          <xsl:sort select="count( $v4issues[ . eq current() ] )"/>
          <xsl:sequence select="count( $v4issues[ . eq current() ] )||' '||.||'&#x0A;'"/>
        </xsl:for-each>

Distressing dogmatic division

Of course, it is not the case that for every XPath that can be divided into two, doing so improves readability and comprehension. Consider the following single XPath designed to be used to query a Subversion log file that has been created with the --xml and --verbose switches.

        /log/logentry[author = 'syd']/paths/path[ contains(., '.odd') ]!concat( ../../date, ' revision ', ../../@revision, '
 : ', normalize-space(../../msg) )

The above is a long and unwieldy XPath, somewhat hard to understand quickly. But dividing it up recursively into nearly atomic steps (here using the host language XSLT), I claim, results in code that is even harder to comprehend in its totality. (It is likely somewhat easier to debug, though. This is because when debugging we often want to examine each minute step, rather than the totality.)

  <xsl:template name="xsl:initial-template" match="/">
    <xsl:variable name="inputDocument" select="/" as="document-node()"/>
    <xsl:variable name="outermost" select="$inputDocument/*" as="element(log)"/>
    <xsl:variable name="allEntries" select="$outermost/logentry" as="element(logentry)+"/>
    <xsl:variable name="sydEntries" select="$allEntries[ author = 'syd']" as="element(logentry)*"/>
    <xsl:variable name="sydPathss" select="$sydEntries/paths" as="element(paths)*"/>
    <xsl:variable name="sydPaths" select="$sydPathss/path" as="element(path)*"/>
    <xsl:variable name="sydODDPaths" select="$sydPaths[ contains( ., '.odd')]" as="element(path)*"/>
    <xsl:apply-templates select="$sydODDPaths"/>
  </xsl:template>

  <xsl:template match="path">
    <xsl:variable name="date" select="../../date" as="xs:string"/>
    <xsl:variable name="boilerplate1" select="' revision '" as="xs:string"/>
    <xsl:variable name="revision" select="../../@revision" as="xs:string"/>
    <xsl:variable name="boilerplate2" select="'&#x0A; : '" as="xs:string"/>
    <xsl:variable name="message" select="normalize-space(../../msg)" as="xs:string"/>
    <xsl:sequence select="$date||$boilerplate1||$revision||$boilerplate2||$message||'&#x0A;'"/>
  </xsl:template>

However, not surprisingly, dividing it into a small number of XPaths (in this case just two) yields much more readable and comprehensible code than either of the above.

  <xsl:template name="xsl:initial-template" match="/">
    <xsl:variable name="paths" select="/log/logentry[author='syd']/paths/path[contains(.,'.odd')]"/>
    <xsl:sequence select="$paths!concat( ../../date, ' revision ', ../../@revision, '&#x0A; : ', normalize-space(../../msg) )"/>
  </xsl:template>