Investigate storing node collections more efficiently

[shepmaster]

Right now, we store a Nodeset as a collection of Node objects. However, all the nodes should belong to the same document, so it's possible we could split up the node and store the common information just once.

[Boddlnagg]

As I'm considering to write an XSLT implementation based on sxd-xpath, I want to note that it is not true that all nodes belong to the same document. Quoting from the XSLT specification:

The document function gives rise to the possibility that a node-set may contain nodes from more than one document. With such a node-set, the relative document order of two nodes in the same document is the normal document order defined by XPath [XPath]. The relative document order of two nodes in different documents is determined by an implementation-dependent ordering of the documents containing the two nodes. There are no constraints on how the implementation orders documents other than that it must do so consistently: an implementation must always use the same order for the same set of documents.

Furthermore, XSLT needs to access node-sets in document order regularly, so node-sets should always be stored in that order (instead of calculating the first node in order on demand). The difficult part is to merge two node-sets when the union operator is used. That operation has to ensure that the resulting node-set is also in document order and contains no duplicates (related to #14). Maybe some inspiration can be taken from how Gecko does this.

[shepmaster]

@Boddlnagg I can't tell you how excited the sentence "As I'm considering to write an XSLT implementation based on sxd-xpath" makes me! Supporting XSLT has been the part of the plan all along, but requires getting the base parts of the DOM and XPath in place first 😸

I'll go ahead and close this issue for now, since this optimization doesn't make any sense.

I'd like to extend an offer of help for work towards an XSLT library. Of course, I'd love it to be part of the SXD family! There will undoubtedly need to be changes in the document and XPath libraries to support XSLT, so I can make you a collaborator on these repos after the first few PRs. :-)

[Boddlnagg]

Through another project I have some familiarity with the XSLT 1.0 and XPath 1.0 specifications, and have implemented part of an XSLT processor in Scala, however without paying attention to performance. I haven't done any real work in Rust yet, but I'm looking forward to trying this as my first Rust project :-) But first I'll try to understand how your XPath and document libraries work and see what changes may be required there.