65986 - Need to implement the key() XSLT function

Status: VERIFIED FIXED

(Core :: XSLT, defect)

Description

[Peter Van der Beken [:peterv]]

We need to implement the key() XSLT extension function
(http://www.w3.org/TR/xslt.html#function-key) in Transformiix.

Comment 1

[Axel Hecht]

Hi, Max, Keith, Dan,

to implement xsl:key (a prerequisite) we have had a little discussion in
#transformiix.

The spec in 12.2 is very vague on what exactly is regarded "this node matches
the |match| attribute", is there some WorkingGroup internal understanding of 
this?
We guessed, that we have to iterate over the complete doc, and see if |match|
matches. Is that including text, attribute, comment or even namespace nodes? Or
is there a principal node type for this search?

Thanx

Axel

Comment 2

[Dan Rosen]

Axel: the spec just says "nodes," and I believe part of the design
considerations for the |key| functionality is to remedy the problem that in XML
only elements may have unique identifiers. I think what you can do is something
like: first create a simple table of <xsl:key>s indicated in the stylesheet,
then make a pass over the document and create a table of nodes with keys based
on the rules in the spec. When you encounter key() functions later, you have a
table to work with... Hopefully there's some intelligent way to handle the
initial pass -- I don't know what transformiix does in general here...

To directly answer the question, though, when they say "this node matches the
|match| attribute," that attribute is a path expression like any other. If
you're in the node set resulting from evaluation of that expression, you match
the attribute.

Comment 3

[Keith Visco]

I don't think an initial pass is done at all. After reading the spec, I 
think that when the key() function is encountered the xsl:key actions are 
evaluated using the current context node and the given arguments to the key() 
function. The context node is important for evaluating the match pattern.

I am going to try and implement something this weekend for this. Hopefully we 
can use the Xalan tests for keys to make sure we are at least conforming to 
them. I don't know if they even have a test for this. 

--Keith

Comment 4

[Keith Visco]

Hmmm...ok after reading it a couple more times I think Dan is right about an 
initial pass. I think the match attribute needs to be evaluated against all 
nodes in the document. 

Seems kind of nasty. I used to have to do this with the Id() function when it 
contained some of the functionality which Keys were introduced for. I suppose 
what we could do is once we enounter the first use of the key() function we 
process the entire document and create the table for the keys?

Any better suggestions?

--Keith

Comment 5

[Dan Rosen]

One possible way to ameliorate this slightly might be to do the pass lazily.
That is, I think we understand that to use key() you have to have created keys
for the whole source document, so you either have to do a whole pass of the
source document matching against the keys described, or a whole pass of the keys
described (which, if you have some sort of super-clever XPath implementation,
might be more efficient, but...). But you can avoid doing either of those if you
never use the key() function. So your implementation could lazily construct the
table of keys.

Not super-clever, but whatever. It'll help. Peter, are you taking this bug?

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The keys defenately has to be build lazily since it's not possible to know what 
document to step through until the key() function is called. One <xsl:key> 
could even require searching through multiple documents.

All this is because of the syntax for referring keys to external documents. 
IMHO the syntax for making a key refer to a external document should be:

<xsl:key match="document('books.xml')/Books/Book" value="Name">

I would like to start working on this ASAP, is it ok if I take this bug?

Comment 7

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

just to clarify:
I would like to start working on *this bug* ASAP, is it ok if I take it?

Comment 8

[Axel Hecht]

ok, freaks, let's get serious on this.
I'm going to remove Max, he's getting enough spam.

The dumb me didn't read the spec. Sorry for that. I added the relevant URL to
the header.

Patterns:
Axes are only child or attribute (HEY, NO NAMESPACENODES)
no functions! (no document() for that case)
Context nodes are the matching node or one of it's ancestors.

More contraints in the link, but these are the ones we have been 
misunderstanding the most.

sicking, I'll check out the format-number stuff first, I'm afraid there are 
still some things there ;-)

Axel

Comment 9

[Axel Hecht]

Been looking at this again, we can have calls to the functions id() and key()
at the start of a pattern.
The structure looks so simplified, does this call for a new set of objects?
With hard wired pattern logic? (we can use a Expression, but we won't do 
any error handling then, plus waste some optimisations perhaps)

Axel

Comment 10

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

We need at least another version of the FunctionCall class that inherits 
PatternExpr instead of Expr.

Comment 11

[Keith Visco]

Why?

Comment 12

[Axel Hecht]

OK, I still need to read further in the specs, and the code, but:

I see we have a ExprParser::createPattern, but to me this looked relaxing the
constraints on patterns quite a bit.
It looks like we could optimize the matching there, too.
At least at second glance (the first is way over, and as all can see, miserably
failed)

Keith?

Comment 13

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Ok we don't need another FunctionCall class, but we need to make FunctionCall 
inherit from PatternExpr rather then Expr since functions can be part of a 
pattern as well as an expression. We could probobly make FunctionCall::matches 
always return MB_FALSE and then override it for the classes needed (id and key)

Comment 14

[Keith Visco]

I fail to see when you'd ever call "matches" on a function call. I don't think 
it's necessary to inherit from PatterExpr. A FunctionCall is not a pattern. It's 
evaluated as an expression. Please provide more information on why you want to 
make this change, because I fail to see why you need to.

--Keith

Comment 15

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

as Axel found (see bug url) the following are valid patterns:

id('some-id')//Person
key('mozProjects','xslt')/Bugs/Bug[@num=65986]

Comment 16

[Keith Visco]

It'll work already, you don't need to make it extend pattern. We already use 
document() in patterns. So it should work properly as is. When you create a 
pattern expression it's basically returns a UnionExpr, which is one or more 
PathExprs, etc.  

--Keith

Comment 17

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

There is also the problem of variables and key() calls not allowed in 
match="..." and use="...". I suggest we extend the ContextState class with the 
following functions:

ContextState::disableVaiables(MBool disable)
ContextState::disableFunction(String functionName, MBool disable)

and temporarily disables key() and all variables when the match="..." and 
use="..." are evaluated

Comment 18

[Peter Van der Beken [:peterv]]

Moving forward.

Comment 19

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I've begun working on this...

Comment 20

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 1

Comment 21

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: KeyFunctionCall.cpp ver 1

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

First version of implementation. I had to change the Map class to only delete 
it's contained values and not it's keys. But that should cause any problems 
since it seems the class isn't used anywhere in the code. Ofcource I could 
extend the Map class so you can choose whether it should delete  it's 
keys+values/it's values/nothing. 

On request from Pike I haven't done anything about key() functioncalls and 
variable references in match="..." and use="..."

Comment 23

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 1.1 (left some junk in ver 1, sorry)

Comment 24

[Keith Visco]

I wrote the map for use in the event based API I have locally. Please do not 
change it. Perhaps we could add a flag to prevent deleting of keys, but don't 
change the default behavior.

Comment 25

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 2

Comment 26

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: KeyFunctionCall.cpp ver 2

Comment 27

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

three things are new in ver 2:
* Map::setObjectDeletion take a short instead of MBool
* keynames are validated to be QNames
* moved some logic from KeyFunctionCall::evaluate to XSLKey::getNodes

Comment 28

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I just noticed a small bug in the Map-code patch. The lines that say

if ( deleteObjects == itemsOnly ) {
   tItem->item = 0;
   delete tItem->key;
}

should of course be:

if ( deleteObjects == itemsOnly ) {
   delete tItem->item;
   tItem->key = 0;
}

DOH!

Comment 29

[Peter Van der Beken [:peterv]]

Sicking has the patch, so handing to him. He needs an r (and eventually sr).

Comment 30

[Axel Hecht]

I haven't looked at the patch yet, but comments on KeyFunctionCall.cpp so far:

const NodeSet EMPTY_NODESET;

Dangerous, IMHO. This is a global constant, what happens if any expr appends a 
node to that? Just return a newly created empty nodeset. (Do would expect the
caller to free the returned nodeset?)

Please get rid of the cout. Not only are there serious spelling errors in your
output, they are there for optim builds as well. Not good.

Fix the comments, ::evaluate has the standard comment, which is pretty useless.
XSLKey::XSLKey has parts of the comment for ::getNodes :-(.

More to come, as soon as I'm awake enough to really understand what we try to
do here ;-)

Axel

Comment 31

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 3

Comment 32

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: KeyFunctionCall.cpp ver 3

Comment 33

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The EMPTY_NODESET is never returned from an ::evaluate. XSLKey::getNodes 
returns it when no matching key is found, KeyFunctionCall::evaluate always 
makes a new NodeSet and copies nodes into that. Also, XSLKey::getNodes returns 
a |const NodeSet*| so no function should ever be able to append a node to that.

cout removed (it was never supposed to be in there, sorry)

Comments fixed

Comment 34

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

have to push this :(
will hopefully go in soon after 0.9.1 opening

Comment 35

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: KeyFunctionCall.cpp ver 3.1

Comment 36

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Ver 3.1 only changes KeyFunctionCall::evaluate to do
|NodeSet* res = new NodeSet;| at the beginning and then |return res;| instead 
of |return new NodeSet;|

Comment 37

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Pike: any chance of a review of this before 0.9.1? The patch has been around 
for almost three months now...

Comment 38

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

pushing...

Comment 39

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

reassigning to peterv for review

Comment 40

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

back to me

Comment 41

[Peter Van der Beken [:peterv]]

Mostly nits.

+    xslKeys.setObjectDeletion(MB_TRUE);
keysAndItems instead of MB_TRUE?

+     * Adds the supplied xsl:key to the set of keys
+     * returns NULL if no such key exists
+    **/
+    XSLKey* getKey(String& keyName);
Er. I think that comment is wrong?

     DocumentFunctionCall(ProcessorState* ps, Document* xslDocument);
 
     /**
-     * Evaluates this Expr based on the given context node and processor state
+     * Evaluates a key() xslt-functioncall. First argument is name of key
+     * to use, second argument is value to look up.
I think you changed the wrong comment.

+     * Adds an match/use pair. Returns MB_FALSE if matchString or useString
... a match/use pair

+     * Indexes an document and adds it to the set of indexed documents
... a document

+     * Recursivly searches a node, it's attributes and it's subtree for
Recursively searches a node, its attributes and its subtree for

+     * the node matches it's values are added to the index.
its

+     * ProcessorState used to get parse the match-patterns and
... to parse ...

In KeyFunctionCall.cpp:

    if(!res) {
...
    if ( requireParams(2, 2, cs) ) {
...
        if (!key) {

Please be consistent.

    if (!map)
        map = addDocument(doc);
...
    if(!nodes) return &EMPTY_NODESET;

Same. I prefer
if (test)
    statement
but it's up to you.

 * Adds an match/use pair. Returns MB_FALSE if matchString or useString
... a match/use

 * Indexes an document and adds it to the set of indexed documents
Indexes a document

 * Recursivly searches a node, it's attributes and it's subtree for
Recursively

    //-- check if nodes attributes matches
check if node's attributes match

etc.

The code is good, please fix the spelling errors and the inconsistencies in
coding style. It would be nice to prefix the class names (as we were planning to
do) and I prefer prefix m for member vars and a for arguments, but seeing that
we nearly never use those in Transformiix code, it's not a showstopper for me.

Comment 42

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 4

Comment 43

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: txKeyFunctionCall.cpp ver 3

Comment 44

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

grmbl, that last should be "txKeyFunctionCall.cpp ver 4"...

I've addressed all comments except these:

> +    xslKeys.setObjectDeletion(MB_TRUE);
> keysAndItems instead of MB_TRUE?

Nope, xslKeys is a NamedMap not a Map.

>     //-- check if nodes attributes matches
> check if node's attributes match

genetive s shouldn't be apostrophed I think. But I see now that there should be 
an 'the' in there. Added it in my tree.

Comment 45

[Peter Van der Beken [:peterv]]

Had a quick look, last bits:

+     * The set of all avalible keys
available

+ *    -- added XSLKey class
txXSLKey. There's more comments where you haven't added the tx to XSLKey or
XSLKeyFunctionCall. Not critical to have but it would be nice :).

@@ -48,7 +53,6 @@
     DocumentFunctionCall(ProcessorState* ps, Document* xslDocument);
 
     /**
-     * Evaluates this Expr based on the given context node and processor state
Don't remove the comment for DocumentFunctionCall (though I agree it doesn't say
a lot)

There's some tabs left in txKeyFunctionCall.cpp.

r=peterv if you fix those.

Comment 46

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 5

Comment 47

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: txKeyFunctionCall.cpp ver 5

Comment 48

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

all comments addressed. Will go hunt for sr and a

Comment 49

[Axel Hecht]

ouch, I have comments:
you made a enum out of objectDeletion, which is nice, but use the enum, and
not short as type. And the use of defines as values for the enum scares me.
we don't really need the MBool compat, do we?
mapObjectDeletion? well, I don't come up up with something better. The values
should be prefixed though, none -> eOwnsNone, eOwnsKeysAndItems, 
eOwnsItemsOnly. (I had a name conflict with my own writings in there already)

The {} for methods in txKeyFunctionCall.cpp start a new line in one method, but
don't in the others, I guess we should go for
foo:bla
{
}

Axel

Comment 50

[Axel Hecht]

I now have
    enum txMapOwnership
    {
        eOwnsNone,
        eOwnsKeysAndItems,
        eOwnsItemsOnly
    };
and 
    void  setObjectDeletion(txMapOwnership aOwnership)

Peter just reminded me of Keith's comment, Keith, do you *really* need the
interface being compatible to MBool? Or could you live with this? 
It looks like a good trade, strong type checking and code readability vs. a 
(few ?) modifications in a patch

Axel

Comment 51

[Johnny Stenback (:jst)]

The names in the enum below really should be changed to something that makes it
more ovious from looking at the names that they're enums, like
eMapObjectDeletion_None, ...

+    enum mapObjectDeletion {
+        none = MB_FALSE,
+        keysAndItems = MB_TRUE,
+        itemsOnly

In the new .cpp file:

        ListIterator* iter = params.iterator();

        String keyName;
        evaluateToString((Expr*)iter->next(), aContext, aCs, keyName);
        Expr* param = (Expr*) iter->next();
        delete iter;

could be written like this to avoid the possibility of incorrectly using the
deleted ListeIterator 'iter' further down in the file:

        String keyName;
        Expr* param;

        {
            ListIterator* iter = params.iterator();

            evaluateToString((Expr*)iter->next(), aContext, aCs, keyName);
            param = (Expr*) iter->next();
            delete iter;
        }

In txXSLKey::addKey() and ::addDocument():

    Key* key = new Key;
    key->matchPattern = mProcessorState->getPatternExpr(aMatchString);
 
No out-of-memory check here?

There's also a bunch of other new's that are missing the checks for out of memory.

Other than that, sr=jst

Comment 52

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 6

Comment 53

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: txKeyFunctionCall.cpp ver 6

Comment 54

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

All comments adressed (both jsts and pikes)

We sloved the backwards complience problem and nameing problem by creating a 
new function, Map::setOwnership, and forwarding calls to Map::setObjectDeletion 
to that. I also removed Map::clear(doObjectDeletion) since it's a rather ugly 
function anyway.

Comment 55

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 7

Comment 56

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: txKeyFunctionCall.cpp ver 7

Comment 57

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The following things has changed since ver 5 (the one jst looked at)
1. All |new| calls has null checks
2. Comment changes
3. Whitespace fixes. Do { after class::function at new line.
4. The function Map::setObjectDeletion is depreptiated in favour of
   Map::setOwnership. Calls to setObjectDeletion is forwarded to setOwnership
5. The function Map::clear(MBool deleteObjects) is removed.
6. Removed static constructor by moving EMPTY_NODESET into txXSLKey class

Comment 58

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

7. Interators are allocated on stack so they are no longer |delete|ed
8. Renamed enum constants

Comment 59

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

9. Added code to set correct current-node/nodeset. The code is added in
   txXSLKey::testNode

Comment 60

[Axel Hecht]

r=me. Now that we have yet another feature, we have yet another xalan test 
depending on landing 75102 (xpath parser).

Axel

Comment 61

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: implementation patch ver 8

Comment 62

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: txKeyFunctionCall.cpp ver 8

Comment 63

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

addressed irc-comments from jst:

1. comment change in description of txXSLKey class
2. making Map::txMapOwnership enum values more flag-ish

Comment 64

[Johnny Stenback (:jst)]

sr=jst

Comment 65

[Peter Van der Beken [:peterv]]

r=peterv

Comment 66

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

checked in. Leaving this open to try to get on the 0.9.2 branch

Comment 67

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

After some pain this is actually checked in...

Comment 68

[Axel Hecht]

bitching buttons, verfication spam