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

Hi Merlin and Gregor,

I didn't originally think that the spec was 'missing' a stack of the values of Z because I interpreted the 'update' method for Z to be in a declarative format, not the imperative format.  It does not seem possible to read the Z-update-bullet-point and not translate it into a stack-driven algorithm in an imperative language.

The Z-update-bullet-point says that Z should be updated true if P and updated to ***false if not P***, where P = the node under consideration is in any *subtree-expanded* union and all subsequent *subtree-expanded* intersects but no subsequent *subtree-expanded* subtracts.

In Gregor's example, the fourth iteration should be setting Z to false because, in the declaration above, P is false.

Note, however, that P is false for a different reason than given in Gregor's example.  True that the node <DontSelect/> is not in any filter node-set, but it is in the subtree-expanded union.  Since it is not in the subsequent (subtree expanded) intersect, the logical-and fails, making P false and hence Z false.

The point I will concede is that the statement "iterate through the input document in document order" seems unnecessary.  The declarative style would simply be to say "Process each node in the document, adding each node to the filter node-set..." .  The 'iterate' part simply reflects our knowledge that iteration is what will happen, particularly if the implementer co-mingles the filtration with canonicalization.

I would prefer it if we changed to the "Process each node..." statement, then left the Z update rule as-is since it seems clear enough.  Optionally, we could then add a iterative/imperative pseudo-code version set off in a box or perhaps in an appendix.  This would be done as a clarification.

The point, though, is that a "clarification" could be useful, but I don't think we're talking about a "substantive" change.

Thanks,
John Boyer

-----Original Message-----
From: merlin [mailto:merlin@baltimore.ie]
Sent: Monday, July 08, 2002 10:10 AM
To: Gregor Karlinger
Cc: XMLSigWG
Subject: Re: Comments on XPath Filter 2.0 draft (2002-06-20) 




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.

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
>

Received on Monday, 8 July 2002 13:59:40 UTC