jaxen

DOMXPath.selectNodes(node) throws IllegalArgumentException with jdk 7

Details

  • Type: Bug Bug
  • Status: Resolved Resolved
  • Priority: Major Major
  • Resolution: Fixed
  • Affects Version/s: 1.1, 1.1.3
  • Fix Version/s: 1.1.4
  • Component/s: core
  • Labels:
  • Environment:
    linux, x86, Generic issue
  • Number of attachments :
    3

Description

The following exception is thrown from the DOMXPath.selectNodes(node) with jdk7:-

DOMXPath xpath = new DOMXPath("xPath Expression");
nodeList = xpath.selectNodes(node);

Exception:-

Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:747)
at java.util.TimSort.mergeAt(TimSort.java:483)
at java.util.TimSort.mergeForceCollapse(TimSort.java:426)
at java.util.TimSort.sort(TimSort.java:223)
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.DefaultUnionExpr.evaluate(DefaultUnionExpr.java:116)
at org.jaxen.expr.DefaultFilterExpr.evaluate(DefaultFilterExpr.java:168)
at org.jaxen.expr.DefaultXPathExpr.asList(DefaultXPathExpr.java:102)
at org.jaxen.BaseXPath.selectNodesForContext(BaseXPath.java:674)
at org.jaxen.BaseXPath.selectNodes(BaseXPath.java:213)

The issue is not seen with jdk6.

It think the issue is that n JDK 7 the "Arrays.sort" has changed to use a new sorting algorithm TimSort, which is more stringent about the comparison function.

See http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7075600

and http://www.java.net/node/700601

  1. Java Source File
    DefaultUnionExpr.java
    04/May/12 5:33 PM
    6 kB
    Rolf JDom
  2. Java Source File
    NodeComparator.java
    04/May/12 5:33 PM
    7 kB
    Rolf JDom
  3. Java Source File
    TestIAE.java
    22/Apr/12 5:23 PM
    0.7 kB
    Rolf JDom

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Rolf JDom added a comment -

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

Show
Rolf JDom added a comment - 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
Hide
Permalink
Elliotte Rusty Harold added a comment -

Do you have a complete test case that demonstrates this bug?

Show
Elliotte Rusty Harold added a comment - Do you have a complete test case that demonstrates this bug?
Hide
Permalink
Rolf JDom added a comment -

// 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++)

{ root.setAttribute(String.format("att%03d", i), "one"); }

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

{ root.appendChild(doc.createElement(String.format("kid", i))); }

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

Show
Rolf JDom added a comment - // 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++) { root.setAttribute(String.format("att%03d", i), "one"); } for (int i = 0; i < 32; i++) { root.appendChild(doc.createElement(String.format("kid", i))); } XPath xp = new DOMXPath("//@ [string() = 'one'] | // "); System.out.println(xp.evaluate(doc)); } }
Hide
Permalink
Rolf JDom added a comment - - edited

The Test code as Java

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

Show
Rolf JDom added a comment - - edited The Test code as Java edited to add that the XPath query could be as simple as: "//@* | //* "
Hide
Permalink
Elliotte Rusty Harold added a comment -

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.

Show
Elliotte Rusty Harold added a comment - 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.
Hide
Permalink
Rolf JDom added a comment -

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.

Show
Rolf JDom added a comment - 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.
Hide
Permalink
Rolf JDom added a comment -

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.

Show
Rolf JDom added a comment - 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.
Hide
Permalink
Elliotte Rusty Harold added a comment -

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

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

{ Element root = doc.createElement("root"); doc.appendChild(root); Element child = doc.createElementNS("http://www.example.org", "foo:child"); root.appendChild(child); // different prefix child.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:foo2", "http://www.contradictory.org"); XPath xpath = new DOMXPath("//namespace::node()"); List result = xpath.selectNodes(doc); assertEquals(4, result.size()); }

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

{ Element root = doc.createElement("root"); doc.appendChild(root); Element child = doc.createElementNS("http://www.example.org", "foo:child"); root.appendChild(child); // same prefix child.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:foo", "http://www.contradictory.org"); XPath xpath = new DOMXPath("//namespace::node()"); List result = xpath.selectNodes(doc); assertEquals(3, result.size()); }

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)

Show
Elliotte Rusty Harold added a comment - I patched in your latest NodeComparator and it fixed timsort but broke two other tests: // see JAXEN-105 public void testConsistentNamespaceDeclarations() throws JaxenException { Element root = doc.createElement("root"); doc.appendChild(root); Element child = doc.createElementNS("http://www.example.org", "foo:child"); root.appendChild(child); // different prefix child.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:foo2", "http://www.contradictory.org"); XPath xpath = new DOMXPath("//namespace::node()"); List result = xpath.selectNodes(doc); assertEquals(4, result.size()); } // see JAXEN-105 public void testInconsistentNamespaceDeclarations() throws JaxenException { Element root = doc.createElement("root"); doc.appendChild(root); Element child = doc.createElementNS("http://www.example.org", "foo:child"); root.appendChild(child); // same prefix child.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:foo", "http://www.contradictory.org"); XPath xpath = new DOMXPath("//namespace::node()"); List result = xpath.selectNodes(doc); assertEquals(3, result.size()); } 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)
Hide
Permalink
Elliotte Rusty Harold added a comment -

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.

Show
Elliotte Rusty Harold added a comment - 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.
Hide
Permalink
Abhay Kumar Yadav added a comment -

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

Show
Abhay Kumar Yadav added a comment - 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

People

  • Assignee:
    Elliotte Rusty Harold
    Reporter:
    Abhay Kumar Yadav
Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: