DOMXPath.selectNodes(node) throws IllegalArgumentException with jdk 7

This is probably just a manifestation of JAXEN-215 : The NodeComparator is broken, and does not conform to the Comparator's contract.

NodeComparator does not return 0 in all instances of a == b.
NodeComparator in some instances returns compare(a,b) == compare(b,a) != 0

Rolf

// the following illustrates the problem.
// The key to it is that:
// there need to be 32 attributes or more to get over the internal MIN_MERGE magic number in TimSort.
// The second part of the XPath ( | //* ) includes both the root element, and it's child elements.
// this is important because all the attributes should be sorted after the root, but before the kids.
// the trigger for the bug is that the parent of both kid and att* is 'root', and when an att* is
// compared with a kid, it always returns 1 (there is a bug in NodeComparator when only one of the
// values is a isNonChild(...))

import javax.xml.parsers.DocumentBuilderFactory;

import org.jaxen.XPath;
import org.jaxen.dom.DOMXPath;
import org.w3c.dom.Document;
import org.w3c.dom.Element;

public class TestIAE {
public static void main(String[] args) throws Exception {
Document doc = DocumentBuilderFactory.newInstance().newDocumentBuilder().newDocument();
Element root = doc.createElement("root");
doc.appendChild(root);

for (int i = 0; i < 32; i++)

for (int i = 0; i < 32; i++)

XPath xp = new DOMXPath("//@[string() = 'one'] | // ");
System.out.println(xp.evaluate(doc));
}
}

The Test code as Java

edited to add that the XPath query could be as simple as: "//@* | //* "

It took me a while to get Java 7 installed to test this, but I finally did; and I can confirm the bug.

It's a subtle problem though. My initial attempt to fix it failed, as did Rolf's patch in JAXEN-215. I'll try to dig into it some more, and figure out what's going on; but if anyone else sees the answer holler.

I have the code on hand, and some time on the train tomorrow, so I can take a look at it too.

My assumption is that the 'right' solution to this bug depends on the specification of a well-defined and consistent order to the results of the XPath evaluation.

So, that pre-supposes an agreed-apon order of what the 'right' order of results is....

It would also be useful to get more test data on hand.... the one 'test case' I created is pretty unrealistic.... I wonder if there are alternate cases.

Anyway, I am happy to have a look at it too, and then compare notes later.

One observation I made when I first looked at the code was that, in a 'union' condition, it is always 'merging' two pre-sorted sets... the way I inderstand it is that the relative order of the data in each set is already correct, so it ust becomes a case of a merge. I will work on that assumption.... and see where it goes.... perhaps a full sort is not necessary, just a merge.

Right, I have two changes, they are independant....

The first is a re-written NodeComparator class.

The second is a change to the way that the union operation works and it assumes that each side of the union is pre-sorted. I believe this is a valid assumption... but I am not 100% sure. It should be faster than a full sort, but it's usefulness is limited... even though I imagine it is a significant amount faster, it is only used when doing union XPaths.... which is uncommon, I guess, so a performance benefit is marginal....

I do not have the full test harness running for jaxen, so I have only run it through the JDOM harness (which does a lot of XPath exercises already...).

There is one other place where NodeComparator is called... in the DefaultLocationPath code. This is commonly called....

In fact, when I put the new Node comparator in to the JDOM Performance harness, it reduces the execution time from about 32ms for a large select, to 27ms ... that's a significant improvement.

I patched in your latest NodeComparator and it fixed timsort but broke two other tests:

// see JAXEN-105
public void testConsistentNamespaceDeclarations()
throws JaxenException

// see JAXEN-105
public void testInconsistentNamespaceDeclarations()
throws JaxenException

java.lang.IllegalStateException: Nodes are supposed to be siblings, but neither node was in the iterator.
at org.jaxen.expr.NodeComparator.siblingOrder(NodeComparator.java:193)
at org.jaxen.expr.NodeComparator.compare(NodeComparator.java:141)
at java.util.TimSort.countRunAndMakeAscending(TimSort.java:329)
at java.util.TimSort.sort(TimSort.java:189)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217)
at org.jaxen.expr.DefaultLocationPath.evaluate(DefaultLocationPath.java:148)
at org.jaxen.expr.DefaultAbsoluteLocationPath.evaluate(DefaultAbsoluteLocationPath.java:113)
at org.jaxen.expr.DefaultXPathExpr.asList(DefaultXPathExpr.java:102)
at org.jaxen.BaseXPath.selectNodesForContext(BaseXPath.java:677)
at org.jaxen.BaseXPath.selectNodes(BaseXPath.java:216)
at org.jaxen.test.DOMXPathTest.testConsistentNamespaceDeclarations(DOMXPathTest.java:197)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:601)
at junit.framework.TestCase.runTest(TestCase.java:164)
at junit.framework.TestCase.runBare(TestCase.java:130)
at junit.framework.TestResult$1.protect(TestResult.java:106)
at junit.framework.TestResult.runProtected(TestResult.java:124)
at junit.framework.TestResult.run(TestResult.java:109)
at junit.framework.TestCase.run(TestCase.java:120)
at junit.framework.TestSuite.runTest(TestSuite.java:230)
at junit.framework.TestSuite.run(TestSuite.java:225)
at org.eclipse.jdt.internal.junit.runner.junit3.JUnit3TestReference.run(JUnit3TestReference.java:130)
at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)

I found the missing piece to make my fix work, so this is now fixed at head.

I'll see about pushing a 1.1.4 version that includes this soon.

Hi Elliotte,

Thanks for the fix. Is there anyway i can try that fix out in my environment before you include that in the 1.1.4 version, or can you provide me the patched jar?

thanks
Abhay