jaxen

NodesetComparator only works properly for non-equal Elements

Details

  • Type: Bug Bug
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: 2.0
  • Component/s: None
  • Labels:
    None
  • Number of attachments :
    0

Description

Messing around with merging nodesets as I mentioned on the list , I ran into a problem that too many nodes were being returned. The structure used for the merge was new TreeSet(new NodeComparator(navigator)), which should have kept unique nodes in document order, but it turned out they werent

On inspection I found a number of problems with NodeComparator:

  • it doesn't return 0 for equal nodes.
    I added:
    if (o1 == o2) { return 0; }

    at the start of 'compare' to resolve this.

This showed up a second problem with how attributes and namespace nodes are compared: they just compare as if they were their parent node. This isn't correct for two attributes of the name node:
if (isNonChild(o1) && isNonChild(o2)) {
try

{ // will return 0 now that the first bug is fixed... return compare(navigator.getParentNode(o1), navigator.getParentNode(o2)); }

catch (UnsupportedAxisException ex)

{ return 0; }

}

I removed that code. NS/Attr node comparisons should identical to Element, PI, etc comparisons except for when they have the same parent node, so the special case needs to go in the 'compareSiblings' code. As I was a bit uncertain whether the following sibling check would work for ns/attr nodes I coded up their comparison explicitly:
int nodeType1 = navigator.getNodeType(sib1);
int nodeType2 = navigator.getNodeType(sib2);
if (nodeType1 == Pattern.ATTRIBUTE_NODE) {
if (nodeType2 == Pattern.NAMESPACE_NODE)

{ return 1; }

if (nodeType2 == Pattern.ATTRIBUTE_NODE)

{ String name1 = navigator.getAttributeQName(sib1); String name2 = navigator.getAttributeQName(sib2); int cmp = name1.compareTo(name2); return cmp; }

return -1; // ie atttributes are before elements.
} else if (nodeType1 == Pattern.NAMESPACE_NODE) {
if (nodeType2 == Pattern.ATTRIBUTE_NODE)

{ return -1; }

if (nodeType2 == Pattern.NAMESPACE_NODE)

{ String name1 = navigator.getNamespacePrefix(sib1); String name2 = navigator.getNamespacePrefix(sib2); return name1.compareTo(name2); }

return -1;
}

if (nodeType2 == Pattern.NAMESPACE_NODE

nodeType2 == Pattern.ATTRIBUTE_NODE) { return 1; }

this sorts namespace and attribute nodes separately and alphabetically, and passes the current tests. NB the use of getNodeType above triggers bug jaxen-101!

As for testing this code: if you test nodecomparator with two identical nodes it triggers the first problem, the rest of the issue shows up as test failures (for the order of attribute nodes on the ancestor axis, and the number of attribute/namespace nodes found) if you don't do the rest of the fix.

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Elliotte Rusty Harold added a comment -

There may well be an issue here. Then again there may not be. I'll have to think more deeply about this.

NodeComparator is deliberately a non-public class. It does not attempt to handle every conceivable comparison of objects; only those that can actually arise through the public API. If you can construct a test case that demonstrates the alleged problems solely by invoking the public (or protected) APIs, then we'd have definitive proof that there's a bug here, and can begin fixing it. However, absent such a test case I'm not sure how to fix this, or how to be sure that any proposed fix really does fix the problem, or even whether a problem really exists.

Show
Elliotte Rusty Harold added a comment - There may well be an issue here. Then again there may not be. I'll have to think more deeply about this. NodeComparator is deliberately a non-public class. It does not attempt to handle every conceivable comparison of objects; only those that can actually arise through the public API. If you can construct a test case that demonstrates the alleged problems solely by invoking the public (or protected) APIs, then we'd have definitive proof that there's a bug here, and can begin fixing it. However, absent such a test case I'm not sure how to fix this, or how to be sure that any proposed fix really does fix the problem, or even whether a problem really exists.
Hide
Permalink
Elliotte Rusty Harold added a comment -

I'm not sure your exegesis of the attributes issue is correct. Attributes (and namespace nodes) of the same parent do have the same document order as each other. Thus given something like <a b="c" e="d" /> b and e should compare equal. They do not need to be reordered. XPath defines no particualr order for attribute or namespace nodes of the same parent relative to each other. They do come after their parent element and before any of its children, but that's it. As long as we get that much right, do we otherwise need to swap them? I don't think so but I'm not 100% sure.

Again, a test case that showed incorret output would be definitive proof.

Show
Elliotte Rusty Harold added a comment - I'm not sure your exegesis of the attributes issue is correct. Attributes (and namespace nodes) of the same parent do have the same document order as each other. Thus given something like <a b="c" e="d" /> b and e should compare equal. They do not need to be reordered. XPath defines no particualr order for attribute or namespace nodes of the same parent relative to each other. They do come after their parent element and before any of its children, but that's it. As long as we get that much right, do we otherwise need to swap them? I don't think so but I'm not 100% sure. Again, a test case that showed incorret output would be definitive proof.
Hide
Permalink
Elliotte Rusty Harold added a comment -

Will the NodeComparator ever compare equal nodes? That is, is there any expression that will cause the same node to be passed to this method? Perhaps a union expression? Something like //a | //? You could then turn this around and see if // | //a givens the same result.

Show
Elliotte Rusty Harold added a comment - Will the NodeComparator ever compare equal nodes? That is, is there any expression that will cause the same node to be passed to this method? Perhaps a union expression? Something like //a | // ? You could then turn this around and see if // | //a givens the same result.
Hide
Permalink
Brian Ewins added a comment -

I'm not using this as a public API, I'm using it to re-implement part of the internals for speed. I don't mind this being marked as a minor issue, but there is an issue with using this comparator for maintaining a document-order nodeset - and comparator is defined as being a total ordering relation, not a partial order (as it has to be in order to support the Sorted* Collections), so this implementation doesn't match its documentation.

re the attributes issue: the spec doesnt say there is no order for attributes, it says it is implementation dependent (ditto for namespace nodes). However it does say that namespace nodes come before attribute nodes. The 'isNonChild' code as it stands would mix nodes. I havent figured out yet how to trigger that as a bug, but it looks possible. Since we now claim that jaxen returns nodes in document order, something like "attribute::[1]|namespace::[1]", should return the same results as "namespace::[1]|attribute::[1]". However we don't actually return union patterns sorted - should this be a bug too?

Re the third comment: jaxen only uses the nodecomparator to sort the nodes returned by a step. The way thats being done right now you can't get duplicate nodes (I think) so the comparator works.

Show
Brian Ewins added a comment - I'm not using this as a public API, I'm using it to re-implement part of the internals for speed. I don't mind this being marked as a minor issue, but there is an issue with using this comparator for maintaining a document-order nodeset - and comparator is defined as being a total ordering relation, not a partial order (as it has to be in order to support the Sorted* Collections), so this implementation doesn't match its documentation. re the attributes issue: the spec doesnt say there is no order for attributes, it says it is implementation dependent (ditto for namespace nodes). However it does say that namespace nodes come before attribute nodes. The 'isNonChild' code as it stands would mix nodes. I havent figured out yet how to trigger that as a bug, but it looks possible. Since we now claim that jaxen returns nodes in document order, something like "attribute:: [1] |namespace:: [1] ", should return the same results as "namespace:: [1] |attribute:: [1] ". However we don't actually return union patterns sorted - should this be a bug too? Re the third comment: jaxen only uses the nodecomparator to sort the nodes returned by a step. The way thats being done right now you can't get duplicate nodes (I think) so the comparator works.
Hide
Permalink
Elliotte Rusty Harold added a comment -

I added ordering for union expressions a couple of months ago. That's why NodeComparator is in there. So attribute::[1]|namespace::[1]" or "namespace::[1]|attribute::[1]" might indeed trigger a bug. I'll see if I can concoct a test case for that.

However, to the extent you're using NodeComparator as an internal API, I wouldn't be surprised if you needed to change or reimplement it. One very good reason for making this class non-public is precisely so you can have the freedom to do so as necessary. (Another is so I don;t have to follow the rules for comparators precisely if they don't seem necessary in this particular use case.)

Show
Elliotte Rusty Harold added a comment - I added ordering for union expressions a couple of months ago. That's why NodeComparator is in there. So attribute:: [1] |namespace:: [1] " or "namespace:: [1] |attribute:: [1] " might indeed trigger a bug. I'll see if I can concoct a test case for that. However, to the extent you're using NodeComparator as an internal API, I wouldn't be surprised if you needed to change or reimplement it. One very good reason for making this class non-public is precisely so you can have the freedom to do so as necessary. (Another is so I don;t have to follow the rules for comparators precisely if they don't seem necessary in this particular use case.)
Hide
Permalink
Elliotte Rusty Harold added a comment -

I've fixed NodeComparator so it now sorts namespace nodes before the same element's attribute nodes. There might be some optimization that could yet be done here. I'm probably calling the navigator.isnamespace and navigator.isAttribute methods redundantly.

Show
Elliotte Rusty Harold added a comment - I've fixed NodeComparator so it now sorts namespace nodes before the same element's attribute nodes. There might be some optimization that could yet be done here. I'm probably calling the navigator.isnamespace and navigator.isAttribute methods redundantly.
Hide
Permalink
Brian Ewins added a comment -

I took another look at this because it had no fix-for... its interesting that if in DefaultUnionExpr, if you switch 'new HashSet()' out and use 'new TreeSet(new NodeComparator(...))' (to avoid the cost of the second sort - a natural-order sort is being done inside unique.addAll()), tests begin to fail. The hashset also uses equals() comparisons, as mentioned in another bug, equals() may just mean qnames are the same in some OMs. I'm still uncomfortable with this, but its working well enough for 1.1. Marking as a performance issue for 2.0, we can ditch both sorts here anyway (its a merge)

Show
Brian Ewins added a comment - I took another look at this because it had no fix-for... its interesting that if in DefaultUnionExpr, if you switch 'new HashSet()' out and use 'new TreeSet(new NodeComparator(...))' (to avoid the cost of the second sort - a natural-order sort is being done inside unique.addAll()), tests begin to fail. The hashset also uses equals() comparisons, as mentioned in another bug, equals() may just mean qnames are the same in some OMs. I'm still uncomfortable with this, but its working well enough for 1.1. Marking as a performance issue for 2.0, we can ditch both sorts here anyway (its a merge)

People

  • Assignee:
    Unassigned
    Reporter:
    Brian Ewins
Vote (0)
Watch (0)

Dates

  • Created:
    Updated: