Re: Rewrite of str:replace

From 67b97f2a178690e2fb29327d99cf270e2393cca5 Mon Sep 17 00:00:00 2001
From: Nick Wellnhofer <[email protected]>
Date: Tue, 31 Jul 2012 20:42:48 +0200
Subject: [PATCH 1/4] Fix bug #680920

If the first child of a func:function template is xslt:text, it will be
removed by xsltParseTemplateContent. So xsltParseTemplateContent should be
called before setting func->content to the first child.
---
 libexslt/functions.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/libexslt/functions.c b/libexslt/functions.c
index 13fd06e..0ea72be 100644
--- a/libexslt/functions.c
+++ b/libexslt/functions.c
@@ -489,6 +489,8 @@ exsltFuncFunctionComp (xsltStylesheetPtr style, xmlNodePtr inst) {
     }
     xmlFree(prefix);
 
+    xsltParseTemplateContent(style, inst);
+
     /*
      * Create function data
      */
@@ -500,8 +502,6 @@ exsltFuncFunctionComp (xsltStylesheetPtr style, xmlNodePtr inst) {
 	func->nargs++;
     }
 
-    xsltParseTemplateContent(style, inst);
-
     /*
      * Register the function data such that it can be retrieved
      * by exslFuncFunctionFunction
-- 
1.7.10.4

From f8ee319712081fdc0b9fba7d3687e32712bb2a94 Mon Sep 17 00:00:00 2001
From: Nick Wellnhofer <[email protected]>
Date: Tue, 31 Jul 2012 21:27:51 +0200
Subject: [PATCH 2/4] Null-terminate result string of cry:rc4_decrypt

Bug #675917
---
 libexslt/crypto.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/libexslt/crypto.c b/libexslt/crypto.c
index e2700d6..42ac6c5 100644
--- a/libexslt/crypto.c
+++ b/libexslt/crypto.c
@@ -752,7 +752,7 @@ exsltCryptoRc4DecryptFunction (xmlXPathParserContextPtr ctxt, int nargs) {
     ret_len = exsltCryptoHex2Bin (str, str_len, bin, bin_len);
 
 /* decrypt the binary blob */
-    ret = xmlMallocAtomic (ret_len);
+    ret = xmlMallocAtomic (ret_len + 1);
     if (ret == NULL) {
 	xsltTransformError(tctxt, NULL, tctxt->inst,
 	    "exsltCryptoRc4EncryptFunction: Failed to allocate result\n");
@@ -761,6 +761,7 @@ exsltCryptoRc4DecryptFunction (xmlXPathParserContextPtr ctxt, int nargs) {
 	goto done;
     }
     PLATFORM_RC4_DECRYPT (ctxt, padkey, bin, ret_len, ret, ret_len);
+    ret[ret_len] = 0;
 
     xmlXPathReturnString (ctxt, ret);
 
-- 
1.7.10.4

From deffc00c76f509f3da44b72f51752103bb395ca5 Mon Sep 17 00:00:00 2001
From: Nick Wellnhofer <[email protected]>
Date: Tue, 31 Jul 2012 23:32:05 +0200
Subject: [PATCH 3/4] Test for bug #680920

---
 tests/docs/bug-173.xml    |    1 +
 tests/general/Makefile.am |    1 +
 tests/general/bug-173.out |    2 ++
 tests/general/bug-173.xsl |   18 ++++++++++++++++++
 4 files changed, 22 insertions(+)
 create mode 100644 tests/docs/bug-173.xml
 create mode 100644 tests/general/bug-173.out
 create mode 100644 tests/general/bug-173.xsl

diff --git a/tests/docs/bug-173.xml b/tests/docs/bug-173.xml
new file mode 100644
index 0000000..69d62f2
--- /dev/null
+++ b/tests/docs/bug-173.xml
@@ -0,0 +1 @@
+<doc/>
diff --git a/tests/general/Makefile.am b/tests/general/Makefile.am
index b6c738b..f7fdea9 100644
--- a/tests/general/Makefile.am
+++ b/tests/general/Makefile.am
@@ -180,6 +180,7 @@ EXTRA_DIST = \
     bug-170.out bug-170.xsl \
     bug-171.out bug-171.xsl \
     bug-172.out bug-172.xsl \
+    bug-173.out bug-173.xsl \
     character.out character.xsl \
     character2.out character2.xsl \
     itemschoose.out itemschoose.xsl \
diff --git a/tests/general/bug-173.out b/tests/general/bug-173.out
new file mode 100644
index 0000000..e829790
--- /dev/null
+++ b/tests/general/bug-173.out
@@ -0,0 +1,2 @@
+<?xml version="1.0"?>
+<result/>
diff --git a/tests/general/bug-173.xsl b/tests/general/bug-173.xsl
new file mode 100644
index 0000000..aab57a4
--- /dev/null
+++ b/tests/general/bug-173.xsl
@@ -0,0 +1,18 @@
+<xsl:stylesheet
+	xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
+	xmlns:func = "http://exslt.org/functions"
+	version="1.0" extension-element-prefixes="func">
+
+<func:function name="func:uaf">
+	<xsl:text/>
+	<func:result/>
+</func:function>
+
+<xsl:template match="/">
+        <result>
+	        <xsl:value-of select="func:uaf()"/>
+        </result>
+</xsl:template>
+
+</xsl:stylesheet>
+
-- 
1.7.10.4

From 63ad3d33f88889ba94d79087ea182c9a843fb581 Mon Sep 17 00:00:00 2001
From: Nick Wellnhofer <[email protected]>
Date: Wed, 30 Jun 2010 07:14:54 +0200
Subject: [PATCH 4/4] Rewrite str:replace function

---
 libexslt/strings.c                |  322 ++++++++++++++++++++++++++-----------
 tests/exslt/strings/replace.1.out |   12 +-
 tests/exslt/strings/replace.1.xml |    4 +
 tests/exslt/strings/replace.1.xsl |   13 ++
 4 files changed, 255 insertions(+), 96 deletions(-)

diff --git a/libexslt/strings.c b/libexslt/strings.c
index 1a11976..5167a41 100644
--- a/libexslt/strings.c
+++ b/libexslt/strings.c
@@ -505,38 +505,48 @@ exsltStrConcatFunction (xmlXPathParserContextPtr ctxt, int nargs) {
 }
 
 /**
- * exsltStrReplaceInternal:
- * @str: string to modify
- * @searchStr: string to find
- * @replaceStr: string to replace occurrences of searchStr
+ * exsltStrReturnString:
+ * @ctxt: an XPath parser context
+ * @str: a string
+ * @len: length of string
  *
- * Search and replace string function used by exsltStrReplaceFunction
+ * Returns a string as a node set.
  */
-static xmlChar*
-exsltStrReplaceInternal(const xmlChar* str, const xmlChar* searchStr, 
-                        const xmlChar* replaceStr)
+static int
+exsltStrReturnString(xmlXPathParserContextPtr ctxt, const xmlChar *str,
+                     int len)
 {
-    const xmlChar *curr, *next;
-    xmlChar *ret = NULL;
-    int searchStrSize;
+    xsltTransformContextPtr tctxt = xsltXPathGetTransformContext(ctxt);
+    xmlDocPtr container;
+    xmlNodePtr text_node;
+    xmlXPathObjectPtr ret;
 
-    curr = str;
-    searchStrSize = xmlStrlen(searchStr);
+    container = xsltCreateRVT(tctxt);
+    if (container == NULL) {
+        xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+        return(-1);
+    }
+    xsltRegisterLocalRVT(tctxt, container);
 
-    do {
-      next = xmlStrstr(curr, searchStr);
-      if (next == NULL) {
-        ret = xmlStrcat (ret, curr);
-        break;
-      }
+    text_node = xmlNewTextLen(str, len);
+    if (text_node == NULL) {
+        xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+        return(-1);
+    }
+    xmlAddChild((xmlNodePtr) container, text_node);
+
+    ret = xmlXPathNewNodeSet(text_node);
+    if (ret == NULL) {
+        xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+        return(-1);
+    }
 
-      ret = xmlStrncat (ret, curr, next - curr);
-      ret = xmlStrcat (ret, replaceStr);
-      curr = next + searchStrSize;
-    } while (*curr != 0);
+    xsltExtensionInstructionResultRegister(tctxt, ret);
+    valuePush(ctxt, ret);
 
-    return ret;
+    return(0);
 }
+
 /**
  * exsltStrReplaceFunction:
  * @ctxt: an XPath parser context
@@ -547,97 +557,219 @@ exsltStrReplaceInternal(const xmlChar* str, const xmlChar* searchStr,
  */
 static void
 exsltStrReplaceFunction (xmlXPathParserContextPtr ctxt, int nargs) {
-    xmlChar *str = NULL, *searchStr = NULL, *replaceStr = NULL;
-    xmlNodeSetPtr replaceSet = NULL, searchSet = NULL;
-    xmlChar *ret = NULL, *retSwap = NULL;
-    int i;
+    int i, i_empty, n, slen0, rlen0, *slen, *rlen;
+    void *mem = NULL;
+    const xmlChar *src, *start;
+    xmlChar *string, *search_str = NULL, *replace_str = NULL;
+    xmlChar **search, **replace;
+    xmlNodeSetPtr search_set = NULL, replace_set = NULL;
+    xmlBufferPtr buf;
 
     if (nargs  != 3) {
-      xmlXPathSetArityError(ctxt);
-      return;
+        xmlXPathSetArityError(ctxt);
+        return;
     }
 
-    /* pull out replace argument */
+    /* get replace argument */
+
+    if (!xmlXPathStackIsNodeSet(ctxt))
+        replace_str = xmlXPathPopString(ctxt);
+    else
+        replace_set = xmlXPathPopNodeSet(ctxt);
+
+    if (xmlXPathCheckError(ctxt))
+        goto fail_replace;
+
+    /* get search argument */
+
     if (!xmlXPathStackIsNodeSet(ctxt)) {
-      replaceStr = xmlXPathPopString(ctxt);
+        search_str = xmlXPathPopString(ctxt);
+        n = 1;
     }
-		else {
-      replaceSet = xmlXPathPopNodeSet(ctxt);
-      if (xmlXPathCheckError(ctxt)) {
-        xmlXPathSetTypeError(ctxt);
-        goto fail;
-      }
+    else {
+        search_set = xmlXPathPopNodeSet(ctxt);
+        n = search_set != NULL ? search_set->nodeNr : 0;
     }
 
-    /* behavior driven by search argument from here on */
-    if (!xmlXPathStackIsNodeSet(ctxt)) {
-      searchStr = xmlXPathPopString(ctxt);
-      str = xmlXPathPopString(ctxt);
-
-      if (replaceStr == NULL) {
-        xmlXPathSetTypeError(ctxt);
-        goto fail;
-      }
-
-      ret = exsltStrReplaceInternal(str, searchStr, replaceStr);
-    }
-		else {
-      searchSet = xmlXPathPopNodeSet(ctxt);
-      if (searchSet == NULL || xmlXPathCheckError(ctxt)) {
-        xmlXPathSetTypeError(ctxt);
-        goto fail;
-      }
-
-      str = xmlXPathPopString(ctxt);
-      ret = xmlStrdup(str);
-
-      for (i = 0; i < searchSet->nodeNr; i++) {
-	searchStr = xmlXPathCastNodeToString(searchSet->nodeTab[i]);
-
-        if (replaceSet != NULL) {
-          replaceStr = NULL;
-          if (i < replaceSet->nodeNr) {
-            replaceStr = xmlXPathCastNodeToString(replaceSet->nodeTab[i]);
-          }
-
-          retSwap = exsltStrReplaceInternal(ret, searchStr, replaceStr);
-          
-          if (replaceStr != NULL) {
-            xmlFree(replaceStr);
-            replaceStr = NULL;
-          }
+    if (xmlXPathCheckError(ctxt))
+        goto fail_search;
+
+    /* get string argument */
+
+    string = xmlXPathPopString(ctxt);
+    if (xmlXPathCheckError(ctxt))
+        goto fail_string;
+
+    /* check for empty search node list */
+
+    if (n <= 0) {
+        exsltStrReturnString(ctxt, string, xmlStrlen(string));
+        goto done_empty_search;
+    }
+
+    /* allocate memory for string pointer and length arrays */
+
+    if (n == 1) {
+        search = &search_str;
+        replace = &replace_str;
+        slen = &slen0;
+        rlen = &rlen0;
+    }
+    else {
+        mem = xmlMalloc(2 * n * (sizeof(const xmlChar *) + sizeof(int)));
+        if (mem == NULL) {
+            xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+            goto fail_malloc;
+        }
+        search = (xmlChar **) mem;
+        replace = search + n;
+        slen = (int *) (replace + n);
+        rlen = slen + n;
+    }
+
+    /* process arguments */
+
+    i_empty = -1;
+
+    for (i=0; i<n; ++i) {
+        if (search_set != NULL) {
+            search[i] = xmlXPathCastNodeToString(search_set->nodeTab[i]);
+            if (search[i] == NULL) {
+                n = i;
+                goto fail_process_args;
+            }
+        }
+
+        slen[i] = xmlStrlen(search[i]);
+        if (i_empty < 0 && slen[i] == 0)
+            i_empty = i;
+
+        if (replace_set != NULL) {
+            if (i < replace_set->nodeNr) {
+                replace[i] = xmlXPathCastNodeToString(replace_set->nodeTab[i]);
+                if (replace[i] == NULL) {
+                    n = i + 1;
+                    goto fail_process_args;
+                }
+            }
+            else
+                replace[i] = NULL;
         }
         else {
-          retSwap = exsltStrReplaceInternal(ret, searchStr, replaceStr);
+            if (i == 0)
+                replace[i] = replace_str;
+            else
+                replace[i] = NULL;
         }
 
-				xmlFree(ret);
-        if (searchStr != NULL) {
-          xmlFree(searchStr);
-          searchStr = NULL;
+        if (replace[i] == NULL)
+            rlen[i] = 0;
+        else
+            rlen[i] = xmlStrlen(replace[i]);
+    }
+
+    if (i_empty >= 0 && rlen[i_empty] == 0)
+        i_empty = -1;
+
+    /* replace operation */
+
+    buf = xmlBufferCreate();
+    if (buf == NULL) {
+        xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+        goto fail_buffer;
+    }
+    src = string;
+    start = string;
+
+    while (*src != 0) {
+        int max_len = 0, i_match = 0;
+
+        for (i=0; i<n; ++i) {
+            if (*src == search[i][0] &&
+                slen[i] > max_len &&
+                xmlStrncmp(src, search[i], slen[i]) == 0)
+            {
+                i_match = i;
+                max_len = slen[i];
+            }
         }
 
-				ret = retSwap;
-			}
+        if (max_len == 0) {
+            if (i_empty >= 0 && start < src) {
+                if (xmlBufferAdd(buf, start, src - start) ||
+                    xmlBufferAdd(buf, replace[i_empty], rlen[i_empty]))
+                {
+                    xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+                    goto fail_buffer_add;
+                }
+                start = src;
+            }
 
-      if (replaceSet != NULL)
-        xmlXPathFreeNodeSet(replaceSet);
+            src += xmlUTF8Size(src);
+        }
+        else {
+            if ((start < src &&
+                 xmlBufferAdd(buf, start, src - start)) ||
+                (rlen[i_match] &&
+                 xmlBufferAdd(buf, replace[i_match], rlen[i_match])))
+            {
+                xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+                goto fail_buffer_add;
+            }
 
-      if (searchSet != NULL)
-        xmlXPathFreeNodeSet(searchSet);
-		}
+            src += slen[i_match];
+            start = src;
+        }
+    }
 
-    xmlXPathReturnString(ctxt, ret);
+    if (start < src && xmlBufferAdd(buf, start, src - start)) {
+        xmlXPathSetError(ctxt, XPATH_MEMORY_ERROR);
+        goto fail_buffer_add;
+    }
 
- fail:
-    if (replaceStr != NULL)
-      xmlFree(replaceStr);
+    /* create result node set */
 
-    if (searchStr != NULL)
-      xmlFree(searchStr);
+    exsltStrReturnString(ctxt, xmlBufferContent(buf), xmlBufferLength(buf));
 
-    if (str != NULL)
-      xmlFree(str);
+    /* clean up */
+
+fail_buffer_add:
+    xmlBufferFree(buf);
+
+fail_buffer:
+fail_process_args:
+    if (search_set != NULL) {
+        for (i=0; i<n; ++i)
+            xmlFree(search[i]);
+    }
+    if (replace_set != NULL) {
+        for (i=0; i<n; ++i) {
+            if (replace[i] != NULL)
+                xmlFree(replace[i]);
+        }
+    }
+
+    if (mem != NULL)
+        xmlFree(mem);
+
+fail_malloc:
+done_empty_search:
+    xmlFree(string);
+
+fail_string:
+    if (search_set != NULL)
+        xmlXPathFreeNodeSet(search_set);
+    else
+        xmlFree(search_str);
+
+fail_search:
+    if (replace_set != NULL)
+        xmlXPathFreeNodeSet(replace_set);
+    else
+        xmlFree(replace_str);
+
+fail_replace:
+    return;
 }
 
 /**
diff --git a/tests/exslt/strings/replace.1.out b/tests/exslt/strings/replace.1.out
index 076d110..f41d67c 100644
--- a/tests/exslt/strings/replace.1.out
+++ b/tests/exslt/strings/replace.1.out
@@ -1,5 +1,9 @@
 <?xml version="1.0"?>
 <out>;
+        result nodes: 1
+        result text nodes: 1
+        result string: a
+
 	str:replace('a, simple, list', ', ', '-')
 	a-simple-list
 
@@ -19,4 +23,10 @@
 	tee, eye, billow, a longer string
 
 	str:replace('fee, fi, fo, fum', $x, 'j')
-	j, j, j, j</out>
+	j, , , 
+
+	str:replace('foo', '', 'baz')
+	fbazobazo
+
+	str:replace('Price is $1.10', $from, $to)
+	Price is \$1.10</out>
diff --git a/tests/exslt/strings/replace.1.xml b/tests/exslt/strings/replace.1.xml
index 6371161..16aac14 100644
--- a/tests/exslt/strings/replace.1.xml
+++ b/tests/exslt/strings/replace.1.xml
@@ -8,5 +8,9 @@
 		<y>eye</y>
 		<y>billow</y>
 		<y>a longer string</y>
+                <from>$</from>
+                <from>\</from>
+                <to>\$</to>
+                <to>$\backslash$</to>
 	</strings>
 </doc>
diff --git a/tests/exslt/strings/replace.1.xsl b/tests/exslt/strings/replace.1.xsl
index 0c9e86c..f9a7442 100644
--- a/tests/exslt/strings/replace.1.xsl
+++ b/tests/exslt/strings/replace.1.xsl
@@ -7,8 +7,15 @@
 <xsl:template match="/">
 	<xsl:variable name="x" select="doc/strings/x"/>
 	<xsl:variable name="y" select="doc/strings/y"/>
+	<xsl:variable name="from" select="doc/strings/from"/>
+	<xsl:variable name="to" select="doc/strings/to"/>
+        <xsl:variable name="result" select="str:replace('a', 'b', 'c')"/>
 
 <out>;
+        result nodes: <xsl:value-of select="count($result)"/>
+        result text nodes: <xsl:value-of select="count($result/self::text())"/>
+        result string: <xsl:value-of select="$result/self::text()"/>
+
 	str:replace('a, simple, list', ', ', '-')
 	<xsl:copy-of select="str:replace('a, simple, list', ', ', '-')"/>
 
@@ -30,6 +37,12 @@
 	str:replace('fee, fi, fo, fum', $x, 'j')
 	<xsl:copy-of select="str:replace('fee, fi, fo, fum', $x, 'j')" />
 
+	str:replace('foo', '', 'baz')
+	<xsl:copy-of select="str:replace('foo', '', 'baz')" />
+
+	str:replace('Price is $1.10', $from, $to)
+	<xsl:copy-of select="str:replace('Price is $1.10', $from, $to)" />
+
 </out>
 </xsl:template>
 
-- 
1.7.10.4