Consider switching Nodeset to a set that preserves insertion order

[shepmaster]

This will "do the right thing" in many simple XPaths, but still wouldn't guarantee that the entire thing is in order.

[leoschwarz]

Another option would be to use a BTreeSet and wrap nodes internally in a struct containing a field specifying their position in the document and have the nodes be sorted in the set always.

The advantage of this is that the ordering would be right even if the XPath evaluation does something weird. (Due to my lack of familiarity with the code base I'm not sure where that could happen.)

A Nodeset::add method without index argument could still be provided adding each element after the last currently existing index. The caveat here would be that indices created this way could conflict with the ones generated from reading the document in order. So it would probably boil down to having to expose the node and position wrapper struct when adding the values to the nodeset (or take node and index as separate) arguments, I'm not sure if this is desirable.