xml-dev - Re: SAX 2.0 extension proposals.

[Toby Speight <Toby.Speight@streapadair.freeserve.co.uk>]

Miles> Miles Sabin <URL:mailto:msabin@cromwellmedia.co.uk>

0> In article
0> <AA4C152BA2F9D211B9DD0008C79F760A6752B3@odin.cromwellmedia.co.uk>,
0> Miles wrote:

Miles> Toby Speight wrote,
>> You would have to create as many MyFilterImpl objects as you
>> have parsers, and try each one.  With my example (3 parsers, 2
>> filters), that's only 15 different possibilities, but the
>> combinatorial explosion gets you pretty quickly as the number
>> of stacked filters increases.

Miles> You want to be able to enumerate _all_ the parser+filter
Miles> combinations that support "q" and "r", not just find some
Miles> _one_ parser+filter that fits the bill.

That's not quite right.  The problem as I see it is that you don't
know which filters to try with which parsers, and so you have to
iterate through all the combinations until you find a match.

A reminder of the example:

> Feature     p           q           r
>
> A          no          no          no
> B       provides       no          no
> C          no       provides       no
>
> F       passthru    passthru    provides
> G       provides     blocks     provides
>
> We require q and r.


The factory can ask A, B and C what they support; none of them has the
required feature-set.  But it can't ask the filters directly what they
support - it has to ask the pipelines AF, BF, CF, AFG, BFG, ..., AG,
BG, CG, AGF, ..., etc.

With knowledge of the filters, it can straightaway see that ending in G
is always going to fail (because it blocks q), so it can eliminate half
the options in a stroke.  Furthermore, it can hypothesize ending in F,
which provides r and passes q, so it just needs to find something that
provides q, to plug in upstream of F.  This is a recursive call, and it
finds C.  So CF is a viable result.

This is all just using standard search algorithms; the advantage of
knowing the filters' capabilities separately from the underlying
parsers is that it enables the search-space to be reduced much more
quickly than a brute-force search would.

There's are different benefits to the two approaches I suggested: having
the factory do it all allows a breadth-first search, which should lead to
shorter pipelines as results; recursing mutually between factory and
filters means that more complicated relationships between features are
possible (e.g. filter supports feature x only if upstream parser supports
feature y).

This discussion could probably use some concrete examples at this
point; a Namespace filter is one reasonably complex kind - what else?

--