W3C home > Mailing lists > Public > w3c-ietf-xmldsig@w3.org > July to September 2002

RE: Comments on XPath Filter 2.0 draft (2002-06-20)

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      
> >
> >Verification Successful
> >
> 
> 
> --------------------------------------------------------------
> ---------------
> 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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:10:10 UTC