xml-dev - Re: A weaker XSL?

[Paul Prescod <paul@prescod.net>]

Peter Seibel wrote:
> 
> Buffer the rest of the document. Or make two passes. 

You would have to make n-passes where n depends on the XSL stylesheet. As
an existence proof of a non-tree implementation, you could avoid
implementing a DOM if you re-parsed the document every time you needed to
find some query result. But to get any kind of efficiency you need to do
some darn sophisticated static analysis.


> Presumably your XSL
> processor can figure out what things need that sort of buffering or
> multi-pass treatment. 

I have some ideas about how you would do it, but the market does not seem
to be willing to pay as much for XSL implementations as it does optimizing
C++ compilers so I'm not going to try an implementation. Furthermore you
would need to statically analyze the document AND the stylesheet because
links will affect what you need to keep in memory.

Some people want to allow arbitrary JavaScript code inline so it would be
interesting to see you try static analysis if THAT gets added.

> Of course I'm building some stuff in memory but it
> could be a lot less than the whole document as a DOM tree. For example if
> my document is the Encylopaedia Britanica and I want to output a (strange)
> document consisting of a list of all the articles followed by the full text
> of all the articles containing the word pink I only have to buffer the
> articles with the word pink which is presumably a lot less than the whole
> encyclopedia. 

Certainly. But statically analyzing a stylesheet to figure out what to
buffer is very tricky. It probably isn't as hard as the halting problem
but it is on the level of an optimizing compiler.

> Another way to look at things is to implement your XSL engine
> so it builds a complete tree of the *output* before it writes anything out.

Most of the time XSL's output is larger than the input.

> I'm not arguing that you can implement XSL so it uses no heap, just that
> you could implement it on top of SAX rather than DOM. Or am I still missing
> something?

Sure, you can implement it on top of SAX. It will probably run too slowly
for most common cases of documents to be useful, but you could do it.

 Paul Prescod  - ISOGEN Consulting Engineer speaking for only himself
 http://itrc.uwaterloo.ca/~papresco

"Remember, Ginger Rogers did everything that Fred Astaire did,
but she did it backwards and in high heels."
                                               --Faith Whittlesey

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on CD-ROM/ISBN 981-02-3594-1
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)