Repository: FontoXML/fontoxpath (ts)

Issue:
Stack overflow in array:flatten for very large arrays
See the following playground example: https://xpath.playground.fontoxml.com/?state=H4sIACFKG2MAAzVMWwqDMBC8ynS%2FFARrP4PNHXqEtd1CIRpIV1FC7u4qOD%2FzYGYyjfEj5LqGFk4%2FHoL8yVEu1NA6BpO9UesP%2B5olbZZwSrwho%2BqgEY%2B7ocYN%2FRC49Sh4epwV9w2sKlNVw%2BbvOKmsep1Q2QEhXQJZewAAAA%3D%3D

Expected: sequence of the 20k items in the array
Actual: stack overflow in both Chrome and Firefox

I wasn't able to determine exactly where the infinite recursion happens. The `flattenItem` function is recursive, but only along the structure of the array, which is flat in this case. The stack trace seen in the debugger implies the actual overflow happens in a repeating series of `next()` calls (note the repeating column numbers):

```
"RangeError: Maximum call stack size exceeded
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:444843)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:447687)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:444914)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:464694)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:444914)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:447687)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:444914)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:464694)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:444914)
    at Object.next (https://xpath.playground.fontoxml.com/static/js/1.7d5907a9.chunk.js:1:447687)"
```

Pull request description:
Remove recursions from array:flatten function
This makes it work for long and deep arrays as well

Fixes #536 

Patch:
diff --git a/src/expressions/functions/builtInFunctions_arrays.ts b/src/expressions/functions/builtInFunctions_arrays.ts
index fd122ebc..f4f772d8 100644
--- a/src/expressions/functions/builtInFunctions_arrays.ts
+++ b/src/expressions/functions/builtInFunctions_arrays.ts
@@ -460,17 +460,16 @@ const arraySort: FunctionDefinitionType = (
 	});
 };
 
-function flattenItem(flatteneditems: ISequence, item: Value): ISequence {
+function flattenItem(item: Value): ISequence {
 	if (isSubtypeOf(item.type, ValueType.ARRAY)) {
-		return (item as ArrayValue).members.reduce(
-			(flatteneditemsOfMember, member) =>
-				member().mapAll((allValues) =>
-					allValues.reduce(flattenItem, flatteneditemsOfMember)
-				),
-			flatteneditems
+		const arrayItem = item as ArrayValue;
+		return concatSequences(
+			arrayItem.members.map((member) =>
+				member().mapAll((subItems) => concatSequences(subItems.map(flattenItem)))
+			)
 		);
 	}
-	return concatSequences([flatteneditems, sequenceFactory.singleton(item)]);
+	return sequenceFactory.singleton(item);
 }
 const arrayFlatten: FunctionDefinitionType = (
 	_dynamicContext,
@@ -478,7 +477,7 @@ const arrayFlatten: FunctionDefinitionType = (
 	_staticContext,
 	itemSequence
 ) => {
-	return itemSequence.mapAll((items) => items.reduce(flattenItem, sequenceFactory.empty()));
+	return itemSequence.mapAll((items) => concatSequences(items.map(flattenItem)));
 };
 
 const declarations: BuiltinDeclarationType[] = [
diff --git a/src/expressions/xquery-update/applyPulPrimitives.ts b/src/expressions/xquery-update/applyPulPrimitives.ts
index b550dbc4..5573a644 100644
--- a/src/expressions/xquery-update/applyPulPrimitives.ts
+++ b/src/expressions/xquery-update/applyPulPrimitives.ts
@@ -16,6 +16,21 @@ import { Attr, Document, Element } from '../../types/Types';
 import QName from '../dataTypes/valueTypes/QName';
 import { errXUDY0021 } from './XQueryUpdateFacilityErrors';
 
+function hasAttribute(
+	target: ElementNodePointer,
+	localName: string,
+	namespace: string,
+	domFacade: DomFacade
+): boolean {
+	return domFacade
+		.getAllAttributePointers(target, `name-${localName}`)
+		.some(
+			(attr) =>
+				domFacade.getLocalName(attr) === localName &&
+				domFacade.getNamespaceURI(attr) === namespace
+		);
+}
+
 /**
  * Deletes $target.
  *
@@ -35,7 +50,7 @@ export const deletePu = (
 			documentWriter.removeAttributeNS(
 				parent as Element,
 				domFacade.getNamespaceURI(target as AttributeNodePointer),
-				domFacade.getNodeName(target as AttributeNodePointer)
+				domFacade.getLocalName(target as AttributeNodePointer)
 			);
 		} else {
 			documentWriter.removeChild(parent as Document | Element, target.node);
@@ -157,14 +172,19 @@ export const insertAttributes = (
 	documentWriter: (IDocumentWriter | null) | undefined
 ) => {
 	content.forEach((attributeNodePointer) => {
-		const attrName = domFacade.getNodeName(attributeNodePointer);
-		if (domFacade.getAttribute(target as any, attrName)) {
-			throw errXUDY0021(`An attribute ${attrName} already exists.`);
+		const attrLocalName = domFacade.getLocalName(attributeNodePointer);
+		const attrNamespace = domFacade.getNamespaceURI(attributeNodePointer);
+		if (hasAttribute(target, attrLocalName, attrNamespace, domFacade)) {
+			throw errXUDY0021(
+				`An attribute ${
+					attrNamespace ? `Q{${attrNamespace}}${attrLocalName}` : attrLocalName
+				} already exists.`
+			);
 		}
 		documentWriter.setAttributeNS(
 			target.node,
-			domFacade.getNamespaceURI(attributeNodePointer),
-			attrName,
+			attrNamespace,
+			attrLocalName,
 			domFacade.getDataFromPointer(attributeNodePointer)
 		);
 	});
@@ -305,17 +325,24 @@ export const replaceNode = (
 		documentWriter.removeAttributeNS(
 			element,
 			domFacade.getNamespaceURI(attrTarget),
-			domFacade.getNodeName(attrTarget)
+			domFacade.getLocalName(attrTarget)
 		);
 		replacement.forEach((attr: AttributeNodePointer) => {
-			const name = domFacade.getNodeName(attr);
-			if (domFacade.getAttribute(parent as ElementNodePointer, name)) {
-				throw errXUDY0021(`An attribute ${name} already exists.`);
+			const attrLocalName = domFacade.getLocalName(attr);
+			const attrNamespace = domFacade.getNamespaceURI(attr);
+			if (
+				hasAttribute(parent as ElementNodePointer, attrLocalName, attrNamespace, domFacade)
+			) {
+				throw errXUDY0021(
+					`An attribute ${
+						attrNamespace ? `Q{${attrNamespace}}${attrLocalName}` : attrLocalName
+					} already exists.`
+				);
 			}
 			documentWriter.setAttributeNS(
 				element,
-				domFacade.getNamespaceURI(attr),
-				name,
+				attrNamespace,
+				attrLocalName,
 				domFacade.getDataFromPointer(attr)
 			);
 		});
@@ -356,7 +383,7 @@ export const replaceValue = (
 			documentWriter.setAttributeNS(
 				element.node,
 				domFacade.getNamespaceURI(target),
-				domFacade.getNodeName(target),
+				domFacade.getLocalName(target),
 				stringValue
 			);
 		} else {


Test patch:
diff --git a/test/specs/parsing/arrays/arrayFunctions.tests.ts b/test/specs/parsing/arrays/arrayFunctions.tests.ts
index d9878430..cfef7b75 100644
--- a/test/specs/parsing/arrays/arrayFunctions.tests.ts
+++ b/test/specs/parsing/arrays/arrayFunctions.tests.ts
@@ -3,6 +3,7 @@ import {
 	evaluateXPath,
 	evaluateXPathToArray,
 	evaluateXPathToBoolean,
+	evaluateXPathToNumber,
 	evaluateXPathToNumbers,
 	evaluateXPathToString,
 	evaluateXPathToStrings,
@@ -433,6 +434,21 @@ describe('functions over arrays', () => {
 				evaluateXPathToStrings('array:flatten(["a", ["b", "c"], "d"])', documentNode),
 				['a', 'b', 'c', 'd']
 			));
+
+		it('can flatten long arrays', () =>
+			chai.assert.equal(
+				evaluateXPathToNumber('array:flatten(array{1 to 20000}) => count()', documentNode),
+				20000
+			));
+
+		it('can flatten deep arrays', () =>
+			chai.assert.equal(
+				evaluateXPathToNumber(
+					'(1 to 200) => fold-left([1], function ($accum, $item) {[$accum, $item]}) => array:flatten() => count()',
+					documentNode
+				),
+				201
+			));
 	});
 
 	describe('atomizing arrays', () => {
diff --git a/test/specs/parsing/xquery-updating/executePendingUpdateList.tests.ts b/test/specs/parsing/xquery-updating/executePendingUpdateList.tests.ts
new file mode 100644
index 00000000..584309b0
--- /dev/null
+++ b/test/specs/parsing/xquery-updating/executePendingUpdateList.tests.ts
@@ -0,0 +1,126 @@
+import * as chai from 'chai';
+import * as slimdom from 'slimdom';
+
+import { evaluateUpdatingExpressionSync, executePendingUpdateList } from 'fontoxpath';
+
+let documentNode: slimdom.Document;
+beforeEach(() => {
+	documentNode = new slimdom.Document();
+});
+
+describe('executePendingUpdateList', () => {
+	it('deletes an attribute in a different namespace than the parent element', () => {
+		documentNode = slimdom.parseXmlDocument('<element xmlns:ns1="my-ns" ns1:foo="bar"/>');
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`delete node ./element/@Q{my-ns}foo`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		executePendingUpdateList(pendingUpdateList);
+
+		chai.assert.equal(documentNode.documentElement.outerHTML, '<element xmlns:ns1="my-ns"/>');
+	});
+
+	it('renames an element with an attribute in a different namespace', () => {
+		documentNode = slimdom.parseXmlDocument('<element xmlns:ns1="my-ns" ns1:foo="bar"/>');
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`rename node ./element as "e"`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		executePendingUpdateList(pendingUpdateList);
+
+		chai.assert.equal(
+			documentNode.documentElement.outerHTML,
+			'<e xmlns:ns1="my-ns" ns1:foo="bar"/>'
+		);
+	});
+
+	it('replaces an attribute which is in a namespace', () => {
+		documentNode = slimdom.parseXmlDocument('<element xmlns:ns1="my-ns" ns1:foo="bar"/>');
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`replace node ./element/@Q{my-ns}foo with attribute beep { "boop" }`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		executePendingUpdateList(pendingUpdateList);
+
+		chai.assert.equal(
+			documentNode.documentElement.outerHTML,
+			'<element xmlns:ns1="my-ns" beep="boop"/>'
+		);
+	});
+
+	it('replaces the value of an attribute which is in a namespace', () => {
+		documentNode = slimdom.parseXmlDocument('<element xmlns:ns1="my-ns" ns1:foo="bar"/>');
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`replace value of node ./element/@Q{my-ns}foo with "boop"`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		executePendingUpdateList(pendingUpdateList);
+
+		chai.assert.equal(
+			documentNode.documentElement.outerHTML,
+			'<element xmlns:ns1="my-ns" ns1:foo="boop"/>'
+		);
+	});
+
+	it('throws an error when an insert attribute tries to overwrite an existing attribute in a namespace', () => {
+		documentNode = slimdom.parseXmlDocument('<element xmlns:ns1="my-ns" ns1:foo="bar"/>');
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`insert node attribute Q{my-ns}foo { "baz" } into ./element`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		chai.assert.throws(() => executePendingUpdateList(pendingUpdateList), 'XUDY0021');
+	});
+
+	it('throws an error when an replace attribute tries to overwrite an existing attribute in a namespace', () => {
+		documentNode = slimdom.parseXmlDocument(
+			'<element xmlns:ns1="my-ns" ns1:foo="bar" beep="boop"/>'
+		);
+
+		const { pendingUpdateList, xdmValue } = evaluateUpdatingExpressionSync(
+			`replace node ./element/@beep with attribute Q{my-ns}foo { "baz" }`,
+			documentNode,
+			null,
+			{},
+			{}
+		);
+
+		chai.assert.equal(pendingUpdateList.length, 1);
+
+		chai.assert.throws(() => executePendingUpdateList(pendingUpdateList), 'XUDY0021');
+	});
+});