[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: SAX 2.0 extension proposals.

• From: Toby Speight <Toby.Speight@s...>
• To: "XML developers' list" <xml-dev@x...>
• Date: 03 Feb 2000 12:54:44 +0000

Miles> Miles Sabin <URL:mailto:msabin@c...>

0> In article
0> <AA4C152BA2F9D211B9DD0008C79F760A6752B3@o...>,
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?

-- 

• Prev by Date: Re: XML-DEV LIST NOW OPERATIONAL
• Next by Date: list policies
• Previous by thread: A new Zvon tutorial - CSS2 for XML
• Next by thread: RE: SAX 2.0 extension proposals.
• Index(es):
  • Date
  • Thread