DomReader: slow performance $O(n^2)$ when deserialize on millions of elements to list

[morris821028]

Target Object

LinkedList<String> data = new LinkedList<>();
for (int i = 0; i < 1000000; i++)
  data.add("elem");

Source Code

// Element container; // using DocumentBuilder to append children.

new XStream(new DomDriver()).unmarshal(new DomReader(container));

The parser will achieve $O(n^2)$ time when switching context.

https://github.com/x-stream/xstream/blob/master/xstream/src/java/com/thoughtworks/xstream/io/xml/DomReader.java#L135

Because the parser will move down and up, the DomReader.reassignCurrentElement in linear time $O(n)$. For each element, this function will be called in $O(n)$. Finally, complete in $O(n^2)$.

Then, I'm not sure the implementation of Element.item(int). In my understanding, some of implementations used linked list and make it worse in $O(n^2)$ in one DomReader.reassignCurrentElement.

Here is my workaround for your reference.

public class DomReader extends AbstractDocumentReader {
...
		private List<Element> childElements;
		private Map<Object, List<Element>> cache;
...
		@Override
		protected void reassignCurrentElement(Object current) {
			currentElement = (Element) current;
			if (cache == null)
				cache = new HashMap<>();
			childElements = cache.get(current);
			if (childElements != null)
				return;

			childElements = new ArrayList<>();
			Node node = currentElement.getFirstChild();
			while (node != null) {
				if (node instanceof Element) {
					childElements.add((Element) node);
				}
				node = node.getNextSibling();
			}
			cache.put(current, childElements);
		}

		@Override
		public void moveUp() {
			cache.remove(getCurrent());
			super.moveUp();
		}
...

[joehni]

Actually the code was written 19 years ago (predates my time with XStream), but I confess the current implementation is unfortunate for elements with a lot of children.

[kdebski85]

This can be considered as a security issue.
An attacker can send XML with many elements to perform DOS attack on a server.

[joehni]

This can be considered as a security issue. An attacker can send XML with many elements to perform DOS attack on a server.

No, but you're free to prove it. DOM is a memory-based model. You'll never get an XML structure loaded with so many elements to slow down this code significantly enough for a DOS attack. You'll run into an OOME first.