[libxslt] Make generate-id() deterministic

[Nick Wellnhofer <nwellnhof src gnome org>]

commit 82f6cbf8ca61b1f9e00dc04aa3b15d563e7bbc6d
Author: Nick Wellnhofer <wellnhofer aevum de>
Date:   Wed Aug 31 13:35:23 2022 +0200

    Make generate-id() deterministic
    
    Rework the generate-id() function to return deterministic values. We use
    a simple incrementing counter and store ids in the 'psvi' member of
    nodes which was freed up by previous commits. The presence of an id is
    indicated by a new "source node" flag.
    
    This fixes long-standing problems with reproducible builds, see
    https://bugzilla.gnome.org/show_bug.cgi?id=751621
    
    This also hardens security, as the old implementation leaked the
    difference between a heap and a global pointer, see
    https://bugs.chromium.org/p/chromium/issues/detail?id=1356211
    
    The old implementation could also generate the same id for dynamically
    created nodes which happened to reuse the same memory. Ids for namespace
    nodes were completely broken. They now use the id of the parent element
    together with the hex-encoded namespace prefix.

 libxslt/functions.c               | 107 ++++++++++++++++++++++++++++++++------
 libxslt/xsltInternals.h           |   1 +
 libxslt/xsltutils.h               |   1 +
 tests/REC/test-12.4-1.out         |  11 ++++
 tests/REC/test-12.4-1.xml         |   6 +++
 tests/REC/test-12.4-1.xsl         |  38 ++++++++++++++
 tests/exslt/common/dynamic-id.out |  13 +++++
 tests/exslt/common/dynamic-id.xml |   1 +
 tests/exslt/common/dynamic-id.xsl |  29 +++++++++++
 9 files changed, 191 insertions(+), 16 deletions(-)
---
diff --git a/libxslt/functions.c b/libxslt/functions.c
index ed2b0023..98146d8d 100644
--- a/libxslt/functions.c
+++ b/libxslt/functions.c
@@ -672,11 +672,16 @@ xsltFormatNumberFunction(xmlXPathParserContextPtr ctxt, int nargs)
  */
 void
 xsltGenerateIdFunction(xmlXPathParserContextPtr ctxt, int nargs){
-    static char base_address;
+    xsltTransformContextPtr tctxt;
     xmlNodePtr cur = NULL;
     xmlXPathObjectPtr obj = NULL;
-    long val;
-    xmlChar str[30];
+    char *str;
+    const xmlChar *nsPrefix = NULL;
+    void **psviPtr;
+    unsigned long id;
+    size_t size, nsPrefixSize;
+
+    tctxt = xsltXPathGetTransformContext(ctxt);
 
     if (nargs == 0) {
        cur = ctxt->context->node;
@@ -686,16 +691,15 @@ xsltGenerateIdFunction(xmlXPathParserContextPtr ctxt, int nargs){
 
        if ((ctxt->value == NULL) || (ctxt->value->type != XPATH_NODESET)) {
            ctxt->error = XPATH_INVALID_TYPE;
-           xsltTransformError(xsltXPathGetTransformContext(ctxt), NULL, NULL,
+           xsltTransformError(tctxt, NULL, NULL,
                "generate-id() : invalid arg expecting a node-set\n");
-           return;
+            goto out;
        }
        obj = valuePop(ctxt);
        nodelist = obj->nodesetval;
        if ((nodelist == NULL) || (nodelist->nodeNr <= 0)) {
-           xmlXPathFreeObject(obj);
            valuePush(ctxt, xmlXPathNewCString(""));
-           return;
+           goto out;
        }
        cur = nodelist->nodeTab[0];
        for (i = 1;i < nodelist->nodeNr;i++) {
@@ -704,22 +708,93 @@ xsltGenerateIdFunction(xmlXPathParserContextPtr ctxt, int nargs){
                cur = nodelist->nodeTab[i];
        }
     } else {
-       xsltTransformError(xsltXPathGetTransformContext(ctxt), NULL, NULL,
+       xsltTransformError(tctxt, NULL, NULL,
                "generate-id() : invalid number of args %d\n", nargs);
        ctxt->error = XPATH_INVALID_ARITY;
-       return;
+       goto out;
+    }
+
+    size = 30; /* for "id%lu" */
+
+    if (cur->type == XML_NAMESPACE_DECL) {
+        xmlNsPtr ns = (xmlNsPtr) cur;
+
+        nsPrefix = ns->prefix;
+        if (nsPrefix == NULL)
+            nsPrefix = BAD_CAST "";
+        nsPrefixSize = xmlStrlen(nsPrefix);
+        /* For "ns" and hex-encoded string */
+        size += nsPrefixSize * 2 + 2;
+
+        /* Parent is stored in 'next'. */
+        cur = (xmlNodePtr) ns->next;
+    }
+
+    psviPtr = xsltGetPSVIPtr(cur);
+    if (psviPtr == NULL) {
+        xsltTransformError(tctxt, NULL, NULL,
+                "generate-id(): invalid node type %d\n", cur->type);
+        ctxt->error = XPATH_INVALID_TYPE;
+        goto out;
     }
 
-    if (obj)
-        xmlXPathFreeObject(obj);
+    if (xsltGetSourceNodeFlags(cur) & XSLT_SOURCE_NODE_HAS_ID) {
+        id = (unsigned long) *psviPtr;
+    } else {
+        if (cur->type == XML_TEXT_NODE && cur->line == USHRT_MAX) {
+            /* Text nodes store big line numbers in psvi. */
+            cur->line = 0;
+        } else if (*psviPtr != NULL) {
+            xsltTransformError(tctxt, NULL, NULL,
+                    "generate-id(): psvi already set\n");
+            ctxt->error = XPATH_MEMORY_ERROR;
+            goto out;
+        }
 
-    val = (long)((char *)cur - (char *)&base_address);
-    if (val >= 0) {
-      snprintf((char *)str, sizeof(str), "idp%ld", val);
+        if (tctxt->currentId == ULONG_MAX) {
+            xsltTransformError(tctxt, NULL, NULL,
+                    "generate-id(): id overflow\n");
+            ctxt->error = XPATH_MEMORY_ERROR;
+            goto out;
+        }
+
+        id = ++tctxt->currentId;
+        *psviPtr = (void *) id;
+        xsltSetSourceNodeFlags(tctxt, cur, XSLT_SOURCE_NODE_HAS_ID);
+    }
+
+    str = xmlMalloc(size);
+    if (str == NULL) {
+        xsltTransformError(tctxt, NULL, NULL,
+                "generate-id(): out of memory\n");
+        ctxt->error = XPATH_MEMORY_ERROR;
+        goto out;
+    }
+    if (nsPrefix == NULL) {
+        snprintf(str, size, "id%lu", id);
     } else {
-      snprintf((char *)str, sizeof(str), "idm%ld", -val);
+        size_t i, j;
+
+        snprintf(str, size, "id%luns", id);
+
+        /*
+         * Only ASCII alphanumerics are allowed, so we hex-encode the prefix.
+         */
+        j = strlen(str);
+        for (i = 0; i < nsPrefixSize; i++) {
+            int v;
+
+            v = nsPrefix[i] >> 4;
+            str[j++] = v < 10 ? '0' + v : 'A' + (v - 10);
+            v = nsPrefix[i] & 15;
+            str[j++] = v < 10 ? '0' + v : 'A' + (v - 10);
+        }
+        str[j] = '\0';
     }
-    valuePush(ctxt, xmlXPathNewString(str));
+    valuePush(ctxt, xmlXPathWrapString(BAD_CAST str));
+
+out:
+    xmlXPathFreeObject(obj);
 }
 
 /**
diff --git a/libxslt/xsltInternals.h b/libxslt/xsltInternals.h
index 74a2b640..2fd1f681 100644
--- a/libxslt/xsltInternals.h
+++ b/libxslt/xsltInternals.h
@@ -1787,6 +1787,7 @@ struct _xsltTransformContext {
     unsigned long opLimit;
     unsigned long opCount;
     int sourceDocDirty;
+    unsigned long currentId; /* For generate-id() */
 };
 
 /**
diff --git a/libxslt/xsltutils.h b/libxslt/xsltutils.h
index 598b1eaf..d858b04e 100644
--- a/libxslt/xsltutils.h
+++ b/libxslt/xsltutils.h
@@ -247,6 +247,7 @@ XSLTPUBFUN xmlXPathCompExprPtr XSLTCALL
 #ifdef IN_LIBXSLT
 #define XSLT_SOURCE_NODE_MASK       15
 #define XSLT_SOURCE_NODE_HAS_KEY    1
+#define XSLT_SOURCE_NODE_HAS_ID     2
 int
 xsltGetSourceNodeFlags(xmlNodePtr node);
 int
diff --git a/tests/REC/test-12.4-1.out b/tests/REC/test-12.4-1.out
new file mode 100644
index 00000000..237a9f27
--- /dev/null
+++ b/tests/REC/test-12.4-1.out
@@ -0,0 +1,11 @@
+<?xml version="1.0"?>
+<result>
+  <document>id1</document>
+  <element>id2</element>
+  <attribute>id3</attribute>
+  <namespace>id2ns</namespace>
+  <namespace>id2nsC3A4C3B6C3BC</namespace>
+  <text>id4</text>
+  <comment>id5</comment>
+  <processing-instruction>id6</processing-instruction>
+</result>
diff --git a/tests/REC/test-12.4-1.xml b/tests/REC/test-12.4-1.xml
new file mode 100644
index 00000000..84484f66
--- /dev/null
+++ b/tests/REC/test-12.4-1.xml
@@ -0,0 +1,6 @@
+<doc xmlns="s:def">
+    <elem attr="value" xmlns:äöü="uri"/>
+    <text>text</text>
+    <!-- comment -->
+    <?pi content?>
+</doc>
diff --git a/tests/REC/test-12.4-1.xsl b/tests/REC/test-12.4-1.xsl
new file mode 100644
index 00000000..5cf5dd33
--- /dev/null
+++ b/tests/REC/test-12.4-1.xsl
@@ -0,0 +1,38 @@
+<xsl:stylesheet
+    version="1.0"
+    xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
+    xmlns:d="s:def"
+    exclude-result-prefixes="d">
+
+<xsl:output indent="yes"/>
+
+<xsl:template match="/">
+    <result>
+        <document>
+            <xsl:value-of select="generate-id(/)"/>
+        </document>
+        <element>
+            <xsl:value-of select="generate-id(/d:doc/d:elem)"/>
+        </element>
+        <attribute>
+            <xsl:value-of select="generate-id(d:doc/d:elem/@attr)"/>
+        </attribute>
+        <namespace>
+            <xsl:value-of select="generate-id(d:doc/d:elem/namespace::*[local-name()=''])"/>
+        </namespace>
+        <namespace>
+            <xsl:value-of select="generate-id(d:doc/d:elem/namespace::äöü)"/>
+        </namespace>
+        <text>
+            <xsl:value-of select="generate-id(d:doc/d:text/text())"/>
+        </text>
+        <comment>
+            <xsl:value-of select="generate-id(d:doc/comment())"/>
+        </comment>
+        <processing-instruction>
+            <xsl:value-of select="generate-id(d:doc/processing-instruction())"/>
+        </processing-instruction>
+    </result>
+</xsl:template>
+
+</xsl:stylesheet>
diff --git a/tests/exslt/common/dynamic-id.out b/tests/exslt/common/dynamic-id.out
new file mode 100644
index 00000000..1b7b7bad
--- /dev/null
+++ b/tests/exslt/common/dynamic-id.out
@@ -0,0 +1,13 @@
+<?xml version="1.0"?>
+<result xmlns:exsl="http://exslt.org/common";>
+  <id>id1</id>
+  <id>id2</id>
+  <id>id3</id>
+  <id>id4</id>
+  <id>id5</id>
+  <id>id6</id>
+  <id>id7</id>
+  <id>id8</id>
+  <id>id9</id>
+  <id>id10</id>
+</result>
diff --git a/tests/exslt/common/dynamic-id.xml b/tests/exslt/common/dynamic-id.xml
new file mode 100644
index 00000000..69d62f2c
--- /dev/null
+++ b/tests/exslt/common/dynamic-id.xml
@@ -0,0 +1 @@
+<doc/>
diff --git a/tests/exslt/common/dynamic-id.xsl b/tests/exslt/common/dynamic-id.xsl
new file mode 100644
index 00000000..8478f6af
--- /dev/null
+++ b/tests/exslt/common/dynamic-id.xsl
@@ -0,0 +1,29 @@
+<xsl:stylesheet
+    version="1.0"
+    xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
+    xmlns:exsl="http://exslt.org/common";>
+
+<xsl:output indent="yes"/>
+
+<xsl:template name="dynamic-id">
+    <id>
+        <xsl:value-of select="generate-id(exsl:node-set('string'))"/>
+    </id>
+</xsl:template>
+
+<xsl:template match="/">
+    <result>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+        <xsl:call-template name="dynamic-id"/>
+    </result>
+</xsl:template>
+
+</xsl:stylesheet>