You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ws.apache.org by co...@apache.org on 2026/08/21 16:33:50 UTC
(ws-xmlschema) branch coheigea/sax-walker created (now f991f6ed)
This is an automated email from the ASF dual-hosted git repository.
coheigea pushed a change to branch coheigea/sax-walker
in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
at f991f6ed Use an explicit heap stack in SaxWalkerOverDom
This branch includes the following new commits:
new f991f6ed Use an explicit heap stack in SaxWalkerOverDom
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(ws-xmlschema) 01/01: Use an explicit heap stack in SaxWalkerOverDom
Posted by co...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
coheigea pushed a commit to branch coheigea/sax-walker
in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
commit f991f6ed39a988d3ed4aa3434d8846f710375c1f
Author: Colm O hEigeartaigh <co...@apache.org>
AuthorDate: Fri Aug 21 17:33:26 2026 +0100
Use an explicit heap stack in SaxWalkerOverDom
---
.../commons/schema/docpath/SaxWalkerOverDom.java | 77 ++++++++++++++++------
.../schema/docpath/TestSaxWalkerOverDom.java | 1 -
.../docpath/TestSaxWalkerOverDomDeepNesting.java | 75 +++++++++++++++++++++
3 files changed, 133 insertions(+), 20 deletions(-)
diff --git a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/SaxWalkerOverDom.java b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/SaxWalkerOverDom.java
index 1e1098ff..c8d5aefb 100644
--- a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/SaxWalkerOverDom.java
+++ b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/docpath/SaxWalkerOverDom.java
@@ -322,7 +322,44 @@ public final class SaxWalkerOverDom {
}
}
+ /*
+ * Walks the element depth-first using an explicit heap stack, so JVM stack
+ * consumption is constant in the nesting depth of the document.
+ */
private void walk(Element element) throws SAXException {
+ final List<ElementFrame> walkStack = new ArrayList<ElementFrame>();
+ walkStack.add(startElement(element));
+
+ while (!walkStack.isEmpty()) {
+ final ElementFrame frame = walkStack.get(walkStack.size() - 1);
+
+ boolean descended = false;
+ while (frame.childIndex < frame.children.getLength()) {
+ final Node node = frame.children.item(frame.childIndex);
+ ++frame.childIndex;
+
+ if (node instanceof Element) {
+ walkStack.add(startElement((Element)node));
+ descended = true;
+ break;
+ } else if (node instanceof Text) {
+ walk((Text)node);
+ } else if (node instanceof org.w3c.dom.Comment) {
+ // Ignored.
+ } else {
+ throw new SAXException("Unrecognized child of " + frame.element.getTagName()
+ + " of type " + node.getClass().getName());
+ }
+ }
+
+ if (!descended) {
+ endElement(frame);
+ walkStack.remove(walkStack.size() - 1);
+ }
+ }
+ }
+
+ private ElementFrame startElement(Element element) throws SAXException {
DomAttrsAsSax attrs = new DomAttrsAsSax(element.getAttributes());
final List<String> prefixes = startPrefixMappings(element);
@@ -333,33 +370,35 @@ public final class SaxWalkerOverDom {
convertNullToEmptyString(element.getNodeName()), attrs);
}
- NodeList children = element.getChildNodes();
-
- for (int childIndex = 0; childIndex < children.getLength(); ++childIndex) {
- Node node = children.item(childIndex);
- if (node instanceof Element) {
- walk((Element)node);
- } else if (node instanceof Text) {
- walk((Text)node);
- } else if (node instanceof org.w3c.dom.Comment) {
- // Ignored.
- } else {
- throw new SAXException("Unrecognized child of " + element.getTagName() + " of type "
- + node.getClass().getName());
- }
- }
+ return new ElementFrame(element, prefixes);
+ }
+ private void endElement(ElementFrame frame) throws SAXException {
for (ContentHandler listener : listeners) {
- listener.endElement(convertNullToEmptyString(element.getNamespaceURI()),
- convertNullToEmptyString(element.getLocalName()),
- convertNullToEmptyString(element.getNodeName()));
+ listener.endElement(convertNullToEmptyString(frame.element.getNamespaceURI()),
+ convertNullToEmptyString(frame.element.getLocalName()),
+ convertNullToEmptyString(frame.element.getNodeName()));
- for (String prefix : prefixes) {
+ for (String prefix : frame.prefixes) {
listener.endPrefixMapping(prefix);
}
}
}
+ private static final class ElementFrame {
+ private final Element element;
+ private final NodeList children;
+ private final List<String> prefixes;
+ private int childIndex;
+
+ ElementFrame(Element element, List<String> prefixes) {
+ this.element = element;
+ this.prefixes = prefixes;
+ this.children = element.getChildNodes();
+ this.childIndex = 0;
+ }
+ }
+
private void walk(Text text) throws SAXException {
/*
* TODO: getData() may throw a org.w3c.dom.DOMException if the actual
diff --git a/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDom.java b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDom.java
index 441d9309..89971ffb 100644
--- a/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDom.java
+++ b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDom.java
@@ -37,7 +37,6 @@ import org.xml.sax.Locator;
import org.xml.sax.SAXException;
import org.xml.sax.helpers.DefaultHandler;
-import org.apache.ws.commons.schema.docpath.SaxWalkerOverDom;
import org.apache.ws.commons.schema.testutils.UtilsForTests;
import org.junit.Test;
diff --git a/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDomDeepNesting.java b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDomDeepNesting.java
new file mode 100644
index 00000000..28082230
--- /dev/null
+++ b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/docpath/TestSaxWalkerOverDomDeepNesting.java
@@ -0,0 +1,75 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.ws.commons.schema.docpath;
+
+import javax.xml.parsers.DocumentBuilder;
+import javax.xml.parsers.DocumentBuilderFactory;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import org.w3c.dom.Document;
+import org.w3c.dom.Element;
+
+import org.xml.sax.helpers.DefaultHandler;
+
+/**
+ * SaxWalkerOverDom must use constant JVM stack space for document nesting.
+ */
+public class TestSaxWalkerOverDomDeepNesting extends Assert {
+
+ private static final int DEPTH = 50000;
+
+ @Test
+ public void testDeeplyNestedDocumentDoesNotOverflowTheStack() throws Exception {
+ DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
+ factory.setNamespaceAware(true);
+ DocumentBuilder builder = factory.newDocumentBuilder();
+ Document document = builder.newDocument();
+
+ Element current = document.createElement("a");
+ document.appendChild(current);
+ for (int index = 1; index < DEPTH; ++index) {
+ Element child = document.createElement("a");
+ current.appendChild(child);
+ current = child;
+ }
+ current.appendChild(document.createTextNode("deepest"));
+
+ final int[] counts = new int[2];
+ SaxWalkerOverDom walker = new SaxWalkerOverDom(new DefaultHandler() {
+ @Override
+ public void startElement(String uri, String localName, String qName,
+ org.xml.sax.Attributes attributes) {
+ ++counts[0];
+ }
+
+ @Override
+ public void endElement(String uri, String localName, String qName) {
+ ++counts[1];
+ }
+ });
+
+ walker.walk(document);
+
+ assertEquals(DEPTH, counts[0]);
+ assertEquals(DEPTH, counts[1]);
+ }
+}
\ No newline at end of file