How to sort XML elements in-place?

Question

I'm trying to version control IntelliJ IDEA configuration files. Here's a small sample:

<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="ChangeListManager">
    <ignored path="tilde.iws" />
    <ignored path=".idea/workspace.xml" />
    <ignored path=".idea/dataSources.local.xml" />
    <option name="EXCLUDED_CONVERTED_TO_IGNORED" value="true" />
    <option name="TRACKING_ENABLED" value="true" />
    <option name="SHOW_DIALOG" value="false" />
    <option name="HIGHLIGHT_CONFLICTS" value="true" />
    <option name="HIGHLIGHT_NON_ACTIVE_CHANGELIST" value="false" />
    <option name="LAST_RESOLUTION" value="IGNORE" />
  </component>
  <component name="ToolWindowManager">
    <frame x="1201" y="380" width="958" height="1179" extended-state="0" />
    <editor active="false" />
    <layout>
      <window_info id="TODO" active="false" anchor="bottom" auto_hide="false" internal_type="DOCKED" type="DOCKED" visible="false" show_stripe_button="true" weight="0.33" sideWeight="0.5" order="6" side_tool="false" content_ui="tabs" />
      <window_info id="Palette&#9;" active="false" anchor="left" auto_hide="false" internal_type="DOCKED" type="DOCKED" visible="false" show_stripe_button="true" weight="0.33" sideWeight="0.5" order="2" side_tool="false" content_ui="tabs" />
    </layout>
  </component>
</project>

Some elements, such as /project/component[@name='ToolWindowManager']/layout/window_info seem to be saved in arbitrary sequence every time the IDE saves the configuration. All elements of the same type seem to always have the same attributes in the same sequence. Considering that the sequence of elements is irrelevant for the functioning of the IDE, it would be useful if elements are sorted by element name and then attribute values, and attributes and whitespace are left in place.

Based on another answer I've gotten to this:

<stylesheet version="1.0" xmlns="http://www.w3.org/1999/XSL/Transform">
    <output method="xml" indent="yes" encoding="UTF-8"/>
    <strip-space elements="*"/>

    <template match="processing-instruction()|@*">
        <copy>
            <apply-templates select="node()|@*"/>
        </copy>
    </template>

    <template match="*">
        <copy>
            <apply-templates select="@*"/>
            <apply-templates>
                <sort select="name()"/>
                <sort select="@*[1]"/>
                <sort select="@*[2]"/>
                <sort select="@*[3]"/>
                <sort select="@*[4]"/>
                <sort select="@*[5]"/>
                <sort select="@*[6]"/>
            </apply-templates>
        </copy>
    </template>
</stylesheet>

It's almost there, but with a few issues:

• It doesn't sort by every attribute value (and @* doesn't work)
• It removes space before the end of empty elements (<foo /> becomes <foo/>).
• It adds a newline at EOF (which IMO isn't a bug, but makes the resulting file less similar to the original).

Answer 1

I'm unsure of the details of a canonical xml sort and if it matches what you described, however I would recommend using xmllint to do a canonical xml sort, before saving the file into source control. If you are consistent about this, then your version control should be very clean and useful. You can rework the stuff below to be in a script and if you are using git, the you can setup a githook to kick the script off for you.

$ xmllint --c14n originalConfig.xml > sortedConfig.xml
$ mv sortedConfig.xml originalConfig.xml

The above should work for you if you are using linux or mac. You might have to install something like cygwin, if you are using windows.

Answer 2

I'd tackle it using perl and XML::Twig.

perl has a sort function, which allows you to specify arbitary criteria for comparing a sequence of values. As long as your function returns positive, negative or zero based on relative ordering.

So this is where the magic happens - we specify a sort criteria that:

• Compares based on node name (tag)
• Then compares based on attribute existence
• Then compares on attribute value.

It needs to do this recursively across your structure to sort sub-nodes too.

So:

#!/usr/bin/env perl
use strict;
use warnings;

use XML::Twig;

my $xml = XML::Twig -> new -> parsefile ('sample.xml');

sub compare_elements {
   ## perl sort uses $a and $b to compare. 
   ## in this case, it's nodes we expect;

   #tag is the node name. 
   my $compare_by_tag = $a -> tag cmp $b -> tag;
   #conditional return - this works because cmp returns zero
   #if the values are the same.
   return $compare_by_tag if $compare_by_tag; 

   #bit more complicated - extract all the attributes of both a and b, and then compare them sequentially:
   #This is to handle case where you've got mismatched attributes.
   #this may be irrelevant based on your input. 
   my %all_atts;
   foreach my $key ( keys %{$a->atts}, keys %{$b->atts}) { 
      $all_atts{$key}++;
   }
   #iterate all the attributes we've seen - in either element. 
   foreach my $key_to_compare ( sort keys %all_atts ) {

      #test if this attribute exists. If it doesn't in one, but does in the other, then that gets sorted to the top. 
      my $exists = ($a -> att($key_to_compare) ? 1 : 0) <=> ($b -> att($key_to_compare) ? 1 : 0);
      return $exists if $exists;

      #attribute exists in both - extract value, and compare them alphanumerically. 
      my $comparison =  $a -> att($key_to_compare) cmp $b -> att($key_to_compare);
      return $comparison if $comparison;
   }
   #we have fallen through all our comparisons, we therefore assume the nodes are the same and return zero. 
   return 0;
}

#recursive sort - traverses to the lowest node in the tree first, and then sorts that, before
#working back up. 
sub sort_children {
   my ( $node ) = @_;
   foreach my $child ( $node -> children ) { 
      #sort this child if is has child nodes. 
      if ( $child -> children ) { 
         sort_children ( $child )
      }     
   }  

   #iterate each of the child nodes of this one, sorting based on above criteria
      foreach my $element ( sort { compare_elements } $node -> children ) {

         #cut everything, then append to the end.
         #because we've ordered these, then this will work as a reorder operation. 
         $element -> cut;
         $element -> paste ( last_child => $node );
      }
}

#set off recursive sort. 
sort_children ( $xml -> root );

#set output formatting. indented_a implicitly sorts attributes. 
$xml -> set_pretty_print ( 'indented_a');
$xml -> print;

Which given your input, outputs:

<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="ChangeListManager">
    <ignored path=".idea/dataSources.local.xml" />
    <ignored path=".idea/workspace.xml" />
    <ignored path="tilde.iws" />
    <option
        name="EXCLUDED_CONVERTED_TO_IGNORED"
        value="true"
    />
    <option
        name="HIGHLIGHT_CONFLICTS"
        value="true"
    />
    <option
        name="HIGHLIGHT_NON_ACTIVE_CHANGELIST"
        value="false"
    />
    <option
        name="LAST_RESOLUTION"
        value="IGNORE"
    />
    <option
        name="SHOW_DIALOG"
        value="false"
    />
    <option
        name="TRACKING_ENABLED"
        value="true"
    />
  </component>
  <component name="ToolWindowManager">
    <editor active="false" />
    <frame
        extended-state="0"
        height="1179"
        width="958"
        x="1201"
        y="380"
    />
    <layout>
      <window_info
          active="false"
          anchor="bottom"
          auto_hide="false"
          content_ui="tabs"
          id="TODO"
          internal_type="DOCKED"
          order="6"
          show_stripe_button="true"
          sideWeight="0.5"
          side_tool="false"
          type="DOCKED"
          visible="false"
          weight="0.33"
      />
      <window_info
          active="false"
          anchor="left"
          auto_hide="false"
          content_ui="tabs"
          id="Palette&#x09;"
          internal_type="DOCKED"
          order="2"
          show_stripe_button="true"
          sideWeight="0.5"
          side_tool="false"
          type="DOCKED"
          visible="false"
          weight="0.33"
      />
    </layout>
  </component>
</project>

No matter what order the various child nodes fall in.

I personally like indented_a because it wraps attributes to new lines, and I think that's clearer. But indented output format could do the same trick.