[xml] [PATCH 4/6] Add xmlSaveOption XML_SAVE_SORT

[Adam Spragg <adam spra gg>]

Adds option, initial implementation, and xmllint parameter for use.
---
 include/libxml/xmlsave.h |    1 +
 xmllint.c                |   11 +++++
 xmlsave.c                |   96 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+), 0 deletions(-)

diff --git a/include/libxml/xmlsave.h b/include/libxml/xmlsave.h
index 1669733..737df77 100644
--- a/include/libxml/xmlsave.h
+++ b/include/libxml/xmlsave.h
@@ -35,6 +35,7 @@ typedef enum {
     XML_SAVE_AS_XML     = 1<<5, /* force XML serialization on HTML doc */
     XML_SAVE_AS_HTML    = 1<<6, /* force HTML serialization on XML doc */
     XML_SAVE_WSNONSIG   = 1<<7, /* format with non-significant whitespace */
+    XML_SAVE_SORT       = 1<<8, /* sort "unordered" parts of XML, e.g. attrs */
 } xmlSaveOption;
 
 
diff --git a/xmllint.c b/xmllint.c
index b7af32f..9aef364 100644
--- a/xmllint.c
+++ b/xmllint.c
@@ -135,6 +135,7 @@ static int noout = 0;
 static int nowrap = 0;
 #ifdef LIBXML_OUTPUT_ENABLED
 static int format = 0;
+static int sort = 0;
 static const char *output = NULL;
 static int compress = 0;
 static int oldout = 0;
@@ -2661,6 +2662,9 @@ static void parseAndPrintFile(char *filename, xmlParserCtxtPtr rectxt) {
                 else if (format == 2)
                     saveOpts |= XML_SAVE_WSNONSIG;
 
+                if (sort == 1)
+                    saveOpts |= XML_SAVE_SORT;
+
 #if defined(LIBXML_HTML_ENABLED) || defined(LIBXML_VALID_ENABLED)
                 if (xmlout)
                     saveOpts |= XML_SAVE_AS_XML;
@@ -3020,6 +3024,7 @@ static void usage(const char *name) {
     printf("\t                 0 Do not pretty print\n");
     printf("\t                 1 Format the XML content, as --format\n");
     printf("\t                 2 Add whitespace inside tags, preserving content\n");
+    printf("\t--sort : sort \"unordered\" parts of XML, e.g. attributes\n");
 #endif /* LIBXML_OUTPUT_ENABLED */
     printf("\t--c14n : save in W3C canonical format v1.0 (with comments)\n");
     printf("\t--c14n11 : save in W3C canonical format v1.1 (with comments)\n");
@@ -3355,6 +3360,12 @@ main(int argc, char **argv) {
                 xmlKeepBlanksDefault(0);
             }
        }
+       else if ((!strcmp(argv[i], "-sort")) ||
+                (!strcmp(argv[i], "--sort"))) {
+#ifdef LIBXML_OUTPUT_ENABLED
+            sort = 1;
+#endif
+        }
 #ifdef LIBXML_READER_ENABLED
        else if ((!strcmp(argv[i], "-stream")) ||
                 (!strcmp(argv[i], "--stream"))) {
diff --git a/xmlsave.c b/xmlsave.c
index ddf7143..086b31e 100644
--- a/xmlsave.c
+++ b/xmlsave.c
@@ -525,6 +525,35 @@ xmlOutputBufferWriteWSNonSig(xmlSaveCtxtPtr ctxt, int extra)
 }
 
 /**
+ * xmlNsPtrCmp:
+ * @a: pointer to first xmlNsPtr to compare
+ * @b: pointer to second xmlNsPtr to compare
+ *
+ * Compare two xmlNsPtrs by the NS prefix/href, as used by qsort.
+ * NSs without prefixes sort before those with, and string comparisons
+ * are done asciibetically, so as to be stable no matter the locale.
+ */
+static int
+xmlNsPtrCmp(void const * a, void const * b)
+{
+    xmlNsPtr x = *((xmlNsPtr *) a);
+    xmlNsPtr y = *((xmlNsPtr *) b);
+    int i;
+    if ((x->prefix != NULL)
+            && (y->prefix == NULL))
+        return +1;
+    if ((y->prefix != NULL)
+            && (x->prefix == NULL))
+        return -1;
+    if ((x->prefix != NULL)
+            && (y->prefix != NULL)
+            && (i = strcmp((char const *) x->prefix,
+                    (char const *) y->prefix)) != 0)
+        return i;
+    return strcmp((char const *) x->href, (char const *) y->href);
+}
+
+/**
  * xmlNsDumpOutput:
  * @buf:  the XML buffer output
  * @cur:  a namespace
@@ -580,6 +609,25 @@ xmlNsDumpOutputCtxt(xmlSaveCtxtPtr ctxt, xmlNsPtr cur) {
  */
 static void
 xmlNsListDumpOutputCtxt(xmlSaveCtxtPtr ctxt, xmlNsPtr cur) {
+    if (ctxt->options & XML_SAVE_SORT) {
+        int n;
+        int i;
+        xmlNsPtr ns;
+
+        n = 0;
+        for (ns = cur; ns != NULL; ns = ns->next) {
+            ++n;
+        }
+        xmlNsPtr nss[n];
+        for (ns = cur, i = 0; ns != NULL; ns = ns->next, ++i) {
+            nss[i] = ns;
+        }
+        qsort(nss, n, sizeof(nss[0]), xmlNsPtrCmp);
+        for (i = 0; i < n; ++i) {
+            xmlNsDumpOutput(ctxt->buf, nss[i], ctxt);
+        }
+        return;
+    }
     while (cur != NULL) {
         xmlNsDumpOutput(ctxt->buf, cur, ctxt);
        cur = cur->next;
@@ -659,6 +707,35 @@ xmlDtdDumpOutput(xmlSaveCtxtPtr ctxt, xmlDtdPtr dtd) {
 }
 
 /**
+ * xmlAttrPtrCmp:
+ * @a: pointer to first xmlAttrPtr to compare
+ * @b: pointer to second xmlAttrPtr to compare
+ *
+ * Compare two xmlAttrPtrs by their name and NS prefix, as used by qsort.
+ * Attrs without NS prefixes sort before those with, and string comparisons
+ * are done asciibetically, so as to be stable no matter the locale.
+ */
+static int
+xmlAttrPtrCmp(void const * a, void const * b)
+{
+    xmlAttrPtr x = *((xmlAttrPtr *) a);
+    xmlAttrPtr y = *((xmlAttrPtr *) b);
+    int i;
+    if ((x->ns != NULL) && (x->ns->prefix != NULL)
+            && ((y->ns == NULL) || (y->ns->prefix == NULL)))
+        return +1;
+    if ((y->ns != NULL) && (y->ns->prefix != NULL)
+            && ((x->ns == NULL) || (x->ns->prefix == NULL)))
+        return -1;
+    if ((x->ns != NULL) && (x->ns->prefix != NULL)
+            && (y->ns != NULL) && (y->ns->prefix != NULL)
+            && (i = strcmp((char const *) x->ns->prefix,
+                    (char const *) y->ns->prefix)) != 0)
+        return i;
+    return strcmp((char const *) x->name, (char const *) y->name);
+}
+
+/**
  * xmlAttrDumpOutput:
  * @buf:  the XML buffer output
  * @cur:  the attribute pointer
@@ -698,6 +775,25 @@ xmlAttrDumpOutput(xmlSaveCtxtPtr ctxt, xmlAttrPtr cur) {
 static void
 xmlAttrListDumpOutput(xmlSaveCtxtPtr ctxt, xmlAttrPtr cur) {
     if (cur == NULL) return;
+    if (ctxt->options & XML_SAVE_SORT) {
+        int n;
+        int i;
+        xmlAttrPtr attr;
+
+        n = 0;
+        for (attr = cur; attr != NULL; attr = attr->next) {
+            ++n;
+        }
+        xmlAttrPtr attrs[n];
+        for (attr = cur, i = 0; attr != NULL; attr = attr->next, ++i) {
+            attrs[i] = attr;
+        }
+        qsort(attrs, n, sizeof(attrs[0]), xmlAttrPtrCmp);
+        for (i = 0; i < n; ++i) {
+            xmlAttrDumpOutput(ctxt, attrs[i]);
+        }
+        return;
+    }
     while (cur != NULL) {
         xmlAttrDumpOutput(ctxt, cur);
        cur = cur->next;
-- 
1.7.1