#484 key() corrupts ancestor node

Michael Kay

When the key() function is called with three arguments,
and the third argument is an element node (not the
document node at the root of the tree), then this node
is corrupted. (The transient NodeInfo object is
incorrectly set to point to the wrong place in the
TinyTree; the TinyTree structure itself is not affected.)

The effects depend on the subsequent processing applied
to the node: for example, a call on name() will give
the wrong node name. The call on key() itself succeeds.

The source fix below is a replacement for the
isAncestorOrSelf() method in

public boolean isAncestorOrSelf(TinyNodeImpl d) {
    // If it's a different tree, return false
    if (tree != d.tree) return false;
    int dn = d.nodeNr;
    // If d is an attribute, then either "this"

must be the same
attribute, or "this" must
// be an ancestor-or-self of the parent of d.
if (d instanceof TinyAttributeImpl) {
if (this instanceof TinyAttributeImpl) {
return nodeNr == dn;
} else {
dn = tree.attParent[dn];
// If this is an attribute, return false (we've
already handled the
case where it's the same attribute)
if (this instanceof TinyAttributeImpl) return

    // From now on, we know that both "this" and

"dn" are nodes in the
primary array

    // If d is later in document order, return false
    if (nodeNr > dn) return false;

    // If it's the same node, return true
    if (nodeNr == dn) return true;

    // We've dealt with the "self" case: to be an

ancestor, it must be
an element or document node
if (!(this instanceof TinyParentNodeImpl))
return false;

    // If this node is deeper than the target node

then it can't be an
if (tree.depth[nodeNr] >= tree.depth[dn])
return false;

    // The following code will exit as soon as we

find an ancestor that
has a following-sibling:
// when that happens, we know it's an ancestor
iff its
following-sibling is beyond the node we're
// looking for. If the ancestor has no
following sibling, we go up a

    // The algorithm depends on the following

assertion: if A is before
D in document order, then
// either A is an ancestor of D, or some
ancestor-or-self of A has a
following-sibling that
// is before-or-equal to D in document order.

    int n = nodeNr;
    while (true) {
        int nextSib = tree.next[n];
        if (nextSib > dn) {
            return true;
        } else if (tree.depth[nextSib] == 0) {
            return true;
        } else if (nextSib < n) {
            n = nextSib;
        } else {
            return false;