- From: Gregor Karlinger <gregor.karlinger@iaik.at>
- Date: Wed, 10 Jul 2002 09:26:32 +0200
- To: <merlin@baltimore.ie>
- Cc: "XMLSigWG" <w3c-ietf-xmldsig@w3.org>
- Message-ID: <023e01c227e3$1e382290$2305a8c0@iaik.at>
Merlin,
> Hi Gregor,
>
> No, you're missing nothing; the spec is missing a stack
> of the values of Z. So, in your example, when you pop
> out of Select, we should restore the previous value of
> Z, which is false.
>
> Should the text be something like this, or are things
> getting too complex?
>
> * Any time a node N is encountered that is in any evaluated
> node set S, push the value of Z onto a stack, update Z
> to be the value of filter(N), and then process N and its
> descendants. Finally, pop the previous value of Z from
> the stack and continue.
>
> filter(N) is true if and only if the node N
> is present in any subtree-expanded union node set and
> all subsequent subtree-expanded intersect node sets but
> no subsequent subtree-expanded subtract node sets, or
> false otherwise. If there are no subsequent intersect
> or subtract node sets, then that part of the test is
> automatically passed.
I think the text is correct now. However I am not convinced if the
runtime savings are high enough to justify the additional step of
(a) checking each node's existence in the set S of any filter
(b) maintaining the stack
Wouldn't it be sufficient to have instructions like:
Process each node in the document, adding each node to the
filter node-set if and only if the node is present in any
subtree-expanded union node-set and all subsequent
subtree-expanded intersect node-sets but no subsequent
subtree-expanded subtract node-sets, or false otherwise.
If there are no subsequent intersect or subtract node-sets,
then that part of the test is automatically passed.
Regards, Gregor
>
> Merlin
>
> r/gregor.karlinger@iaik.at/2002.07.08/18:41:22
> >part multipart/signed 16K
> >Content-Type: text/plain;
> > charset="US-ASCII"
> >Content-Transfer-Encoding: 7bit
> >
> >Merlin,
> >
> >> r/gregor.karlinger@iaik.at/2002.07.08/12:48:30
> >> >I have the following comment on the current XPath filter
> 2.0 draft:
> >> >
> >> >The first bullet of the inner list in the performance paragraph in
> >> >section 3.4 says:
> >> >
> >> > "Any time a node is encountered that is in any evaluated node
> >> > set S, update Z ..."
> >> >
> >> >I think this is incorrect. The flag Z must be updated for
> >> each node of the input node set.
> >
> ><merlin>
> >> I think that the flag Z can only change state if a node from
> >> a filter node set is encountered.
> ></merlin>
> >
> >Merlin, maybe I misunderstand what is said in the draft, but let me
> >work out the specified algorithm with the following example:
> >
> > Sample input: <Root><Select/><DontSelect/></Root>
> > Transform params: single intersect filter, xpath="//Select"
> >
> >Step 1: For each XPath expression X, in sequence, evaluate the
> > expression and store the resulting node set, S
> >
> > We only have one filter, whose node set S is {Elem(Select)}
> > Filter("Intersect", {Elem(Select)})
> >
> >Step 2: Prepend a node set consisting of just the document node,
> > along with the operation union.
> >
> > So we have another filter
> > Filter("Union", {Doc}
> >
> >Step 3: Create a new, empty filter node set.
> >
> > OK, denote it FilterNodeSet({})
> >
> >After the first three init steps we have the following setting:
> >
> > InputDocument({Doc, Elem{Root}, Elem{Select}, Elem{DontSelect})
> > FilterList (
> > Filter("Union", {Doc}
> > Filter("Intersect", {Elem(Select)})
> > )
> > FilterNodeSet({})
> > FlagZ(undefinded)
> >
> >Step 4: Iterate through the input document in document order,
> > adding each node that is encountered to the filter node
> > set F if a flag Z is true. This flag is computed as
> > follows: Any time a node is encountered that is in any
> > evaluated node set S, update Z ...
> >
> > first iteration: Doc
> >
> > - Doc is in first filter node set, therefore update flag Z:
> > - Last "Union" filter is our first filter
> > - Doc is not in subsequent expanded "Intersect" filter node
> > set => FlagZ(false)
> >
> > - Doc will not make it in the FilterNodeset
> > => FilterNodeSet({})
> >
> > second iteration: Elem(Root)
> >
> > - Elem(Root) is in no filter node set, so do not update FlagZ
> > => FlagZ(false)
> >
> > - Elem(Root) will not make it in the FilterNodeset
> > => FilterNodeSet({})
> >
> > third iteration: Elem(Select)
> >
> > - Elem(Select) is in the second filter node set, therefore
> > update flag Z:
> > - Last "Union" filter is our first filter
> > - Elem(Select) is in the subsequent expandend "Intersect"
> > filter node set => FlagZ(true)
> >
> > - Elem(Select) is our first member of FilterNodeSet
> > => FilterNodeSet({Elem(Select)})
> >
> > fourth iteration: Elem(DontSelect)
> >
> > - Elem(DontSelect) is in no filter node set, so do not update
> > FlagZ => FlagZ(true)
> >
> > - Elem(DontSelect) will make it in the FilterNodeset, since
> > FlagZ is still true.
> > => FilterNodeSet({Elem(Select), Elem(DontSelect)})
> >
> >So, if this interpretation of the specified algorithm is correct, we
> >have a FilterNodset({Elem(Select), Elem(DontSelect)}, although the
> >intention of the filter should be to select Elem(Select) only.
> >
> >Am I missing something here?
> >
> >Regards, Gregor
> >[32m
> >Verification Successful
> >[0m
>
>
> --------------------------------------------------------------
> ---------------
> The information contained in this message is confidential and
> is intended for the addressee(s) only. If you have received
> this message in error or there are any problems please notify
> the originator immediately. The
> unauthorised use, disclosure, copying or alteration of this
> message is
> strictly forbidden. Baltimore Technologies plc will not be
> liable for direct, special, indirect or consequential damages
> arising from alteration of the contents of this message by a
> third party or as a result of any
> virus being passed on.
>
> This footnote confirms that this email message has been swept
> for Content Security threats, including computer viruses.
http://www.baltimore.com
Received on Wednesday, 10 July 2002 03:29:11 UTC