Why does the validation of keyref depend on the ordering of the key element?

My document contains A elements with IDs and B Elements which reference the As, like this:

<root xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:noNamespaceSchemaLocation="file:\\\refissue.xsd">

    <A id="x"/>
    <A id="y"/>

    <B><Aref idref="x" /></B>   

</root>

When I validate against my simple schema (see below) I get the following error:

cvc-identity-constraint.4.3: Key 'ref' with value 'x' not found for identity constraint of element 'root'.

If I change the ordering of the A element to

    <A id="y"/>
    <A id="x"/>

the document validates without any errors.

Why does the validation result depend on the ordering of the elements?

Is this a bug in the validator or in my schema?

<?xml version="1.0" encoding="utf-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xs:element name="root">
        <xs:complexType>
            <xs:sequence>

                <xs:element maxOccurs="unbounded" name="A">
                    <xs:complexType>
                        <xs:attribute name="id" type="xs:ID" />
                    </xs:complexType>
                    <xs:key name="A.KEY">
                        <xs:selector xpath="." />
                        <xs:field xpath="@id" />
                    </xs:key>
                </xs:element>

                <xs:element maxOccurs="unbounded" name="B">
                    <xs:complexType>
                        <xs:sequence>
                            <xs:element minOccurs="0" maxOccurs="1" name="Aref">
                                <xs:complexType>
                                    <xs:attribute name="idref" type="xs:IDREF" />
                                </xs:complexType>
                            </xs:element>
                        </xs:sequence>
                    </xs:complexType>
                </xs:element>

            </xs:sequence>
        </xs:complexType>

        <xs:keyref name="ref" refer="A.KEY">
            <xs:selector xpath="B/Aref" />
            <xs:field xpath="@idref" />
        </xs:keyref>

    </xs:element>
</xs:schema>

I tried the validation with Eclipse (which uses xerces, I think), xerces-c 3.1.1, xmlstarlet 1.5.0 and libxml2 2.7.8 and I get the error only with eclipse and xerces.

Solution

You're right, validity against an identity constraint should not depend on the order of elements in the input.

Here I think the problem is that the schema is not quite right, and Xerces is having trouble generating a useful diagnosis of the problem. (The fact that libxml doesn't report an error is just a consequence of its incomplete coverage of XSD.)

Your key constraint should be defined on the scope of the element within which the key values need to be unique -- so on the root element, not on the A element. (As defined, your A.KEY constraint requires that the string value of each A element be unique within that A element, which will always be the case. The fact that the id attribute is declared as being of type xs:ID does require uniqueness, of course. And similarly, the fact that the Aref idref attribute is declared as being of type xs:IDREF means that your key and keyref declarations are not actually doing much work here that's not already being done by ID and IDREF.)

Once you move the declaration of A.KEY to the declaration of the root element, Xerces and Saxon agree that the schema is OK and the document is valid.