[libxslt] Use hash table to lookup named templates

[Nick Wellnhofer <nwellnhof src gnome org>]

commit aed0cca049bdd89043d38af931adccf24acbe6f1
Author: Christian Ceelen <christian ceelen amadeus com>
Date:   Thu Aug 20 18:57:57 2015 +0200

    Use hash table to lookup named templates
    
    For big XSLTs (>50000 templates) this results in a huge improvement of the
    compilation time.
    
    Thanks to Christian Ceelen for the original patch.
    
    Fixes GitHub pull request #1

 libxslt/imports.c       |   17 ++++++-----------
 libxslt/pattern.c       |   29 ++++++++++++++++++++++++++++-
 libxslt/xslt.c          |   14 --------------
 libxslt/xsltInternals.h |    2 ++
 tests/REC/test-6.1.err  |    2 ++
 tests/REC/test-6.1.xsl  |   14 ++++++++++++++
 6 files changed, 52 insertions(+), 26 deletions(-)
---
diff --git a/libxslt/imports.c b/libxslt/imports.c
index 9277b4f..7262aab 100644
--- a/libxslt/imports.c
+++ b/libxslt/imports.c
@@ -400,17 +400,12 @@ xsltFindTemplate(xsltTransformContextPtr ctxt, const xmlChar *name,
        return(NULL);
     style = ctxt->style;
     while (style != NULL) {
-       cur = style->templates;
-       while (cur != NULL) {
-           if (xmlStrEqual(name, cur->name)) {
-               if (((nameURI == NULL) && (cur->nameURI == NULL)) ||
-                   ((nameURI != NULL) && (cur->nameURI != NULL) &&
-                    (xmlStrEqual(nameURI, cur->nameURI)))) {
-                   return(cur);
-               }
-           }
-           cur = cur->next;
-       }
+        if (style->namedTemplates != NULL) {
+            cur = (xsltTemplatePtr)
+                xmlHashLookup2(style->namedTemplates, name, nameURI);
+            if (cur != NULL)
+                return(cur);
+        }
 
        style = xsltNextImport(style);
     }
diff --git a/libxslt/pattern.c b/libxslt/pattern.c
index 57f8b9f..720b0cb 100644
--- a/libxslt/pattern.c
+++ b/libxslt/pattern.c
@@ -2090,9 +2090,34 @@ xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
     const xmlChar *name = NULL;
     float priority;              /* the priority */
 
-    if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
+    if ((style == NULL) || (cur == NULL))
        return(-1);
 
+    /* Register named template */
+    if (cur->name != NULL) {
+        if (style->namedTemplates == NULL) {
+            style->namedTemplates = xmlHashCreate(10);
+            if (style->namedTemplates == NULL)
+                return(-1);
+        }
+        else {
+            void *dup = xmlHashLookup2(style->namedTemplates, cur->name,
+                                       cur->nameURI);
+            if (dup != NULL) {
+                xsltTransformError(NULL, style, NULL,
+                                   "xsl:template: error duplicate name '%s'\n",
+                                   cur->name);
+                style->errors++;
+                return(-1);
+            }
+        }
+
+        xmlHashAddEntry2(style->namedTemplates, cur->name, cur->nameURI, cur);
+    }
+
+    if (cur->match == NULL)
+       return(0);
+
     priority = cur->priority;
     pat = xsltCompilePatternInternal(cur->match, style->doc, cur->elem,
                    style, NULL, 1);
@@ -2562,5 +2587,7 @@ xsltFreeTemplateHashes(xsltStylesheetPtr style) {
         xsltFreeCompMatchList(style->piMatch);
     if (style->commentMatch != NULL)
         xsltFreeCompMatchList(style->commentMatch);
+    if (style->namedTemplates != NULL)
+        xmlHashFree(style->namedTemplates, NULL);
 }
 
diff --git a/libxslt/xslt.c b/libxslt/xslt.c
index 972a38e..bca91ee 100644
--- a/libxslt/xslt.c
+++ b/libxslt/xslt.c
@@ -5382,7 +5382,6 @@ xsltParseStylesheetTemplate(xsltStylesheetPtr style, xmlNodePtr template) {
     prop = xmlGetNsProp(template, (const xmlChar *)"name", NULL);
     if (prop != NULL) {
         const xmlChar *URI;
-       xsltTemplatePtr cur;
 
        /*
        * TODO: Don't use xsltGetQNameURI().
@@ -5405,19 +5404,6 @@ xsltParseStylesheetTemplate(xsltStylesheetPtr style, xmlNodePtr template) {
                ret->nameURI = xmlDictLookup(style->dict, BAD_CAST URI, -1);
            else
                ret->nameURI = NULL;
-           cur = ret->next;
-           while (cur != NULL) {
-               if ((URI != NULL && xmlStrEqual(cur->name, ret->name) &&
-                               xmlStrEqual(cur->nameURI, URI) ) ||
-                   (URI == NULL && cur->nameURI == NULL &&
-                               xmlStrEqual(cur->name, ret->name))) {
-                   xsltTransformError(NULL, style, template,
-                       "xsl:template: error duplicate name '%s'\n", ret->name);
-                   style->errors++;
-                   goto error;
-               }
-               cur = cur->next;
-           }
        }
     }
 
diff --git a/libxslt/xsltInternals.h b/libxslt/xsltInternals.h
index 95e8fe6..7123ace 100644
--- a/libxslt/xsltInternals.h
+++ b/libxslt/xsltInternals.h
@@ -1639,6 +1639,8 @@ struct _xsltStylesheet {
      * Forwards-compatible processing
      */
     int forwards_compatible;
+
+    xmlHashTablePtr namedTemplates; /* hash table of named templates */
 };
 
 typedef struct _xsltTransformCache xsltTransformCache;
diff --git a/tests/REC/test-6.1.err b/tests/REC/test-6.1.err
new file mode 100644
index 0000000..2bf9165
--- /dev/null
+++ b/tests/REC/test-6.1.err
@@ -0,0 +1,2 @@
+compilation error: file test-6.1.xsl line 11 element template
+xsl:template: error duplicate name 'duplicateTemplateName'
diff --git a/tests/REC/test-6.1.xsl b/tests/REC/test-6.1.xsl
new file mode 100644
index 0000000..1be9d97
--- /dev/null
+++ b/tests/REC/test-6.1.xsl
@@ -0,0 +1,14 @@
+<xsl:stylesheet version="1.0"
+      xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
+<!-- reject this XSLT named templates should have unique template name + nameURI combinations -->
+
+<xsl:template match="doc">
+    <xsl:call-template name="duplicateTemplateName"/>
+</xsl:template>
+<xsl:template name="duplicateTemplateName">
+<xsl:text>XSLT should be rejected</xsl:text>
+</xsl:template>
+<xsl:template name="duplicateTemplateName">
+<xsl:text>XSLT should be rejected</xsl:text>
+</xsl:template>
+</xsl:stylesheet>