Sorting XML Elements for Stable Output and Clean Diffs

Two exports of the same data should produce the same file. They rarely do. A database returns rows in whatever order its plan happens to produce, a hash-based collection in a generator iterates differently between runs, and a feed provider adds new items at the top today and the bottom tomorrow. The records are identical and the files differ, so diffs are long, checksums change and caches miss. When the order of records carries no meaning, sorting them by a key makes the output deterministic.

The input

An order file with the records out of order and ids that expose the classic sorting trap:

<orders>
  <order id="10" status="open"><total>7.00</total></order>
  <order id="2" status="paid"><total>12.50</total></order>
  <order id="3" status="open"><total>5.00</total></order>
</orders>

The ids are 10, 2 and 3. By number they sort 2, 3, 10. By text they sort 10, 2, 3, because the string 10 begins with 1. Most "my sort is wrong" bugs in XML come from that.

Sorting with XSLT

XSLT has a sort instruction, xsl:sort, that works inside xsl:apply-templates or xsl:for-each. The stylesheet below copies everything unchanged (the identity template) and overrides only the template for orders, which applies its children in sorted order:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output indent="yes"/>
  <xsl:strip-space elements="*"/>
  <xsl:template match="@*|node()">
    <xsl:copy><xsl:apply-templates select="@*|node()"/></xsl:copy>
  </xsl:template>
  <xsl:template match="orders">
    <xsl:copy>
      <xsl:apply-templates select="order">
        <xsl:sort select="@id" data-type="number"/>
      </xsl:apply-templates>
    </xsl:copy>
  </xsl:template>
</xsl:stylesheet>

xsltproc sort.xsl orders.xml

<?xml version="1.0"?>
<orders>
  <order id="2" status="paid">
    <total>12.50</total>
  </order>
  <order id="3" status="open">
    <total>5.00</total>
  </order>
  <order id="10" status="open">
    <total>7.00</total>
  </order>
</orders>

The orders come out as 2, 3, 10. Remove data-type="number" and the default of text applies, giving 10, 2, 3. The xsl:strip-space instruction drops the whitespace text nodes in the input, which otherwise end up between the sorted elements and add stray blank lines. The identity template is what makes the stylesheet small: every node not matched by the orders rule is copied as it is, so nested content and attributes pass through.

Two keys work by repeating xsl:sort: the first is the primary key and the second breaks ties. To order by status and then by id, write one xsl:sort for @status with the default text type and a second for @id with data-type="number". Add order="descending" for a reverse sort. Sorting is also supported by XSLT 1.0 processors on every platform, so this works in xsltproc, in Java's built-in transformer and in browsers.

Sorting with lxml

In Python the same operation is a sort of the children and a rebuild. Children of an element are a sequence, so sorted works with a key function:

from lxml import etree

tree = etree.parse("orders.xml", etree.XMLParser(remove_blank_text=True))
root = tree.getroot()
children = sorted(root, key=lambda e: int(e.get("id")))
for child in children:
    root.append(child)          # append moves the node, so the order is now sorted
print(etree.tostring(root, pretty_print=True).decode())

Appending an element that already has a parent moves it, so after the loop the root holds the same elements in sorted order. The key function is ordinary Python: int(e.get("id")) for a numeric attribute, e.findtext("customer") for a child's text, or a tuple like (e.get("status"), int(e.get("id"))) for two levels. For a key that may be missing, give a default, for example int(e.get("id", "0")), otherwise one record without an id stops the run with an error that points at the sort rather than at the record.

To sort at every level of a document, recurse: sort the children of each element that has repeated children of the same name. Be careful here. A blanket "sort all children of every element" rewrites <name> before <total> in every record, and if your schema defines a sequence (xs:sequence), the output stops validating. Sort only the repeating elements you have chosen, not the structure inside each record.

Sorting attributes too

Neither approach changes the order of attributes, since XML does not define one and XSLT cannot reorder them. When attribute order varies between exports, run the sorted file through canonical form, which sorts attributes (canonical XML and why diffs need it). The combination "sort elements by key, then canonicalize" gives you output that is identical for identical data, which is what a checksum or a diff wants:

xsltproc sort.xsl orders.xml | xmllint --c14n -

Making sorting part of the pipeline

Put the sort where the file is produced, not where it is read. A generator that writes sorted output makes every downstream diff clean. If you do not control the producer, add the sort as the first step of whatever stores or compares the file. For large files the XSLT and lxml methods both load the document into memory. For a file too big for that, extract the records with their keys using a streaming parser, sort the keys externally (the sort command handles files larger than memory), and write the records in that order (parsing large XML files with iterparse shows the streaming read).

Test the sort with a document that has an awkward key: a missing id, a leading zero, a negative number, an id that is not numeric. Decide which should happen and write it down. An xsl:sort with data-type="number" puts non-numeric keys first, since they convert to NaN, which can hide bad data at the top of the file.

Checking that the sort is stable

A sort is only useful for diffs if running it twice gives the same file. Two things break that. Records with equal keys: Python's sorted and xsl:sort are both stable, so equal keys keep their input order, but if the input order differs between exports, so does the output. Add a second key, a unique one such as the id, and equal records stop mattering. And locale: a text sort in XSLT follows the processor's collation, which can differ between machines. Pass lang or use data-type="number", or compare code points in Python with a plain str key, so the same input sorts the same way everywhere.

A cheap test is to run the pipeline on two exports of the same data, in different order, and compare checksums. If they match, the output is stable.

Related reading

This post belongs to comparing and versioning XML. Merges are the other reason order matters (merging XML config files without conflicts), and the transformation language is introduced in XSLT basics, templates and match. The xsl:sort element is specified in the XSLT 1.0 recommendation, and sorted in the Python sorting guide. Check a key expression with the XPath tester.

When sorting XML elements changes the meaning

Order is data. A list of steps, a ranked result, the paragraphs of a document and the points of a track are all sequences. Sorting them destroys the information. Sort only collections that are sets.

A schema requires a sequence. If the type is an xs:sequence, element order inside a record is part of validity, and sorting records is fine while sorting their children is not.

Mixed content. Text between elements has a position. Moving elements around it changes the text.

Signed data. Sorting changes the bytes. If the document carries a signature, sort before signing or keep the original.