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>
 
