Bug 6638 – Support Mozilla's XPathEvaluator object.

• Component: XML
• Status: RESOLVED FIXED

[Jesse Costello-Good]

Mozilla supports the following method of executing an XPath query on a document:

var xpe = new XPathEvaluator();
var nsResolver = xpe.createNSResolver(doc)
var objResult = xpe.evaluate("/xpath/query", doc, nsResolver, 0, null);

[Jesse Costello-Good]

I am evaluating Safari for a port of TIBCO(R) General Interface, a mature AJAX platform that is currently IE 
only. Fixing this bug would make the port more feasible. 

[Eric Seidel (no email)]

It's possible we could pick up KDOM's xpath 1.0 support from frerich.

[Joost de Valk (AlthA)]

This is an enhancement, marking as such. It seems to be in wide demand :)

[Manos Batsis]

It should be noted that this is actually W3C DOM L3 XPath [1]. Anyone care to raising a bounty? As the author of sarissa [2] i'd like it to work in webkit so i'm willing to add some of my pocketmoney, perhaps more commercial interests can also join in :-)

[1] http://www.w3.org/TR/DOM-Level-3-XPath/
[2] sarissa.sf.net

[Anders Carlsson]

I'm working on this

[Anders Carlsson]

Created attachment 8109 [details]
XPath implementation

Here's an XPath implementation based on the work of Frerich Raabe in KDOM.

There are some things remaining to fix, for example:

* It should be possible to use custom NS resolver objects, the DOM spec has more info about this
* Use String instead of DeprecatedString
* The tokenizer and parser could work a little better, like CSSParser.

Anyway, I think it's a good idea to land this and file bugs for the remaining issues

[Anders Carlsson]

Created attachment 8111 [details]
Just the test cases

[Anders Carlsson]

Created attachment 8112 [details]
Implementation

[Anders Carlsson]

Created attachment 8114 [details]
Misc fixes

[Eric Seidel (no email)]

Created attachment 8117 [details]
Cleanup of misc fixes patch

Here is my attempt at some additional cleanup, including removing spaces in ( ), removing extra { } and adding XPATH_SUPPORT define.

There is some additional work required to make !XPATH_SUPPORT work (sending IDL files through cpp), but we can take care of that later.

[Anders Carlsson]

Created attachment 8121 [details]
Incorporate changes

New patch, incorporating some of the changes. I think we'll do the #define after we've landed so we can do it correctly wrt #ifdefs in the IDL files

[Eric Seidel (no email)]

Comment on attachment 8121 [details]
Incorporate changes

Still discussing this with anders over irc.  We shoudl do the #define stuff now, while it's still easy to see the changes.  Also there are a few more rounds of style fixes which we might as well do now while we're in this code.

[Anders Carlsson]

Created attachment 8124 [details]
New iteration

Here's a new version with a bunch of style changes. I also modified the parsing process to be more like the CSS parser, and also make it reentrant because that can theoretically happen when we support custom NS resolvers.

[Darin Adler]

Comment on attachment 8124 [details]
New iteration

I was working on an extensive review of this, and the browser crashed and I lost my comments! I'll try to do it again. I see many minor issues and a few major ones.

[Darin Adler]

Comment on attachment 8124 [details]
New iteration

Many cases of * not next to the type. It should be Node*, not Node *.

+  } elsif ($type eq "XPathEvaluator") {
+      return 0;
+  } elsif ($type eq "XPathNSResolver") {
+      return 0;
+  } elsif ($type eq "XPathResult") {
+      return 0;

+  } elsif ($type eq "XPathNSResolver" or
+           $type eq "XPathResult") {
+    $implIncludes{"JS$type.h"} = 1;
+    return "to$type($value)";

+  } elsif ($type eq "XPathExpression" or
+           $type eq "XPathNSResolver" or
+           $type eq "XPathResult") {
+    $implIncludes{"JS$type.h"} = 1;
+    return "toJS(exec, $value)";

Why are these all separate and not sharing code with other cases?

+           $type eq "float" or 
+           $type eq "double") {

+        readonly attribute double          numberValue

Is double really allowed in IDL? Doesn't float in IDL mean double?

+    virtual JSObject* construct(ExecState* exec, const List &args) { return static_cast<JSObject *>(toJS(exec, new $interfaceName)); }

Why the static_cast here?

+    int nameIndex = code - INVALID_EXPRESSION_ERR;

This can underflow if the code is a large negative number. Should write this so it works with any value.

-  const char* name = code < nameTableSize ? nameTable[code] : 0;
+  if (!name)
+      name = code < nameTableSize ? nameTable[code] : 0;

I don't like the way this works. If we need a separate nameIndex then lets do that in all cases. The use of a null name as a special flag does not seem like a good way to do things.

+        case Node::XPATH_NAMESPACE_NODE:
+            // FIXME: Create an XPath objective C wrapper
+            return nil;

I'd like to see a bug number here.

+    $(WebCore)/xpath

Missing trailing \ character.

+    PassRefPtr<XPathExpression> createExpression(const String& expression,
+                                                 XPathNSResolver* resolver,
+                                                 ExceptionCode& ec);

Should leave out names like "resolver" and "ec" that are completely redundant with the type name. It's our preferred style and I think it makes things easier to read (especially for "ec").

+Element *XPathNamespace::ownerElement() const
+{
+    // FIXME
+    return 0;
+}

Need more detail here. Also, is there a reason we can't fix this?

+#include "impl/expression.h"
+#include "impl/util.h"

XCode, at least, uses a flat namespace for all headers. So short names like expression.h and util.h are not really compatible; directories don't really provide a namespace. Our filenames will need to include the prefix XPath.

+PassRefPtr<XPathExpression> XPathExpression::createExpression(const String& expression, XPathNSResolver* resolver, ExceptionCode& ec)
+{
+    XPathExpression* expr = new XPathExpression;
+    
+    Expression::evaluationContext().resolver = resolver;
+    if (!expr->m_statement.parse(expression.deprecatedString(), ec)) {
+        delete expr;
+        return 0;
+    }
+    
+    return expr;
+}

Needs to use a RefPtr for the expr local variable. It's bad form to call functions with an expr object floating like this, and it's bad form to do a delete on a shared object.

+    XPathResult* result = new XPathResult(static_cast<EventTargetNode*>(eventTarget),
+                                          m_statement.evaluate(contextNode));
+    
+    if (type != XPathResult::ANY_TYPE) {
+        result->convertTo(type, ec);
+
+        if (ec)
+            return 0;
+    }
+
+    return result;

The result here should be a RefPtr to avoid a storage leak in the case where convertTo fails.

+    // Apparently Node::lookupNamespaceURI doesn't do this.
+    if (prefix == "xml")
+        return "http://www.w3.org/XML/1998/namespace";

Is this a bug in lookupNamespaceURI or not? I don't like leaving the comment like this. I'd like to be clearer on whether this is correct or not.

m_node in XPathNSResolver needs to be a RefPtr.

I think NodeSet is an awful name for a Vector of node pointers!

Expression::optimize overwrites m_constantValue without deleting the old value. Is it guaranteed to only be called once?

+    explicit Value(Node *value);
+    explicit Value(const NodeSet& value);
+    explicit Value(bool value);
+    explicit Value(double value);
+    explicit Value(const String& value);

Why does the Value constructor need to be marked explicit? It doesn't seem harmful to have an implicit conversion to a Value, and we could remove tons of explicit calls to the Value constructor.

+            if (rightVal == 0.0 || rightVal == -0.0)

The way floating point works, both of these expressions are the same. Negative 0 and positive 0 return the same thing. But also, why have this check? Floating point correctly produces infinities and NaN's as needed for cases like this. THere's no need for our code to do a redunddant check.

In NumericOp::doEvaluate:

+        default:
+            assert(0);
+        return Value();

If you leave out the default case from the switch statement, gcc will warn if one of the enum cases is not handled. So you should do that.

+    Parser(const Parser &rhs);                  // disabled
+    Parser &operator=(const Parser &rhs);       // disabled

Preferred style for this is to inherit from Noncopyable.

Can Value go in its own header file, instead of with Expression?

+        if (a.isNodeset())
+            node = a.toNodeSet()[0].get();

If there are no nodes in the set, then this will crash.

Patch doesn't include the NodeSet class!

+    return Value(node->localName().deprecatedString());

Value now takes a String, so this is going to convert to DeprecatedString and then back!

+    // extract 'en' out of 'en-us'
+    langNodeValue = langNodeValue.left(langNodeValue.find('-'));

What does this do when langNodeValue doesn't have a "-".

+        LOG(XPath, "sum() expects <nodeset>\n");

Don't use "\n" in LOG, since it already terminates lines. This is in all the LOG statements.

+    const double num = arg(0)->evaluate().toNumber();
+
+    if (isnan(num) || isinf(num)) {
+        return Value(num);
+    }
+
+    return Value(floor(num));

Excessive use of const on local variable here and elsewhere.

What's the point of checking for nan and inf before calling floor? It already handles those cases properly.

+    return Value(double(round(arg(0)->evaluate().toNumber())));

What's the point of the cast to double here? THe round function returns a double.

+    static FunctionMapping functions[] = {

Need to be static const, not just static.

+    static const unsigned int numFunctions = sizeof(functions) / sizeof(functions[ 0 ]);

No need for static here. I believe with static we get a global variable rather than a compile time constant.

Since we're using objects that are allocated and returned, I think we need to be very careful and come up with a calling convention that makes it clear that objects are allocated.

+Function *FunctionLibrary::getFunction(const char *name, const Vector<Expression*> &args) const

There's nothing about the name of this that makes it clear to me that it allocates its results and you are responsible for deleting it. Should talk to Maciej about the memory allocation strategy.

+            Node *n = context->firstChild();
+            while (n) {
+                nodes.append(n);
+                n = n->nextSibling();
+            }

+            Node *n = context->parentNode();
+            while (n) {
+                nodes.append(n);
+                n = n->parentNode();
+            }
+            return nodes;

+            Node *n = context->nextSibling();
+            while (n) {
+                nodes.append(n);
+                n = n->nextSibling();
+            }

I prefer for statements for this sort of thing. Also, with a for statement you would not need the outer braces.

+        default:
+            LOG(XPath, "Unknown axis %s passed to Step::nodesInAxis", axisAsString(m_axis).ascii());

Same comment about default here as elsewhere.

+/* @return all ancestor nodes of the given node, in document order.
+ */
+NodeSet getChildrenRecursively(Node *node);

This function is a bad idea. There's no need to use a recursive algorithm to build the list of all the children in order because we have enough pointers to walk the tree without that. Instead clients can write a simple loop using traverseNextNode and avoid building a NodeSet entirely. Also, it says "all ancestor nodes" but I assume it means "all desecendant nodes".

+bool isValidContextNode(WebCore::Node *node);

Need to eliminate excess WebCore:: prefixes like this one.

XPathGrammar.y needs a strategy to delete the nodes if there's a parse failure. You can't just use new inside a Yacc grammar. See the JavaScript grammar and the CSS grammar for examples of how to do this.

Don't use cell() on QChar. Instead use unicode(), which is more efficient.

There are a lot of return statements with else statements after them. I think it's better style not to do that.

+>>>>>>> .r14202

Oops! Please remove that.

[Darin Adler]

(In reply to comment #15)
> I think NodeSet is an awful name for a Vector of node pointers!

I think NodeVector is a better name.

> Patch doesn't include the NodeSet class!

Oops, please disregard this incorrect comment.

[Maciej Stachowiak]

IDL has both float and double.

[Darin Adler]

Comment on attachment 8111 [details]
Just the test cases

Test cases look fine to me, but I'm going to clear the review flag until we get the patch with the code changes approved so this doesn't show up in the review queue or the patches-to-be-committed queue.

[Anders Carlsson]

Created attachment 8163 [details]
Address Darin's comments

(In reply to comment #15)
> (From update of attachment 8124 [details] [edit])
> Many cases of * not next to the type. It should be Node*, not Node *.
> 

I've (hopefully) fixed all of these.

> +  } elsif ($type eq "XPathEvaluator") {
> +      return 0;
> +  } elsif ($type eq "XPathNSResolver") {
> +      return 0;
> +  } elsif ($type eq "XPathResult") {
> +      return 0;
> 
> +  } elsif ($type eq "XPathNSResolver" or
> +           $type eq "XPathResult") {
> +    $implIncludes{"JS$type.h"} = 1;
> +    return "to$type($value)";
> 
> +  } elsif ($type eq "XPathExpression" or
> +           $type eq "XPathNSResolver" or
> +           $type eq "XPathResult") {
> +    $implIncludes{"JS$type.h"} = 1;
> +    return "toJS(exec, $value)";
> 
> Why are these all separate and not sharing code with other cases?

I've fixed this.

> 
> +           $type eq "float" or 
> +           $type eq "double") {
> 
> +        readonly attribute double          numberValue
> 
> Is double really allowed in IDL? Doesn't float in IDL mean double?

As Maciej said, double is allowed and the IDL for XPathResult uses double.

> 
> +    virtual JSObject* construct(ExecState* exec, const List &args) { return
> static_cast<JSObject *>(toJS(exec, new $interfaceName)); }
> 
> Why the static_cast here?

because toJS returns a JSValue and construct takes a returns a JSObject.

> 
> +    int nameIndex = code - INVALID_EXPRESSION_ERR;
> 
> This can underflow if the code is a large negative number. Should write this so
> it works with any value.

Won't this be handled by the 

 } else if (code >= XPathExceptionOffset && code <= XPathExceptionMax) {

anyway?

> 
> -  const char* name = code < nameTableSize ? nameTable[code] : 0;
> +  if (!name)
> +      name = code < nameTableSize ? nameTable[code] : 0;
> 
> I don't like the way this works. If we need a separate nameIndex then lets do
> that in all cases. The use of a null name as a special flag does not seem like
> a good way to do things.
> 

Fixed

> +        case Node::XPATH_NAMESPACE_NODE:
> +            // FIXME: Create an XPath objective C wrapper
> +            return nil;
> 
> I'd like to see a bug number here.

Fixed

> 
> +    $(WebCore)/xpath
> 
> Missing trailing \ character.

Fixed

> 
> +    PassRefPtr<XPathExpression> createExpression(const String& expression,
> +                                                 XPathNSResolver* resolver,
> +                                                 ExceptionCode& ec);
> 
> Should leave out names like "resolver" and "ec" that are completely redundant
> with the type name. It's our preferred style and I think it makes things easier
> to read (especially for "ec").

Fixed (hopefully for all cases)

> 
> +Element *XPathNamespace::ownerElement() const
> +{
> +    // FIXME
> +    return 0;
> +}
> 
> Need more detail here. Also, is there a reason we can't fix this?
> 

XPathNamespace isn't used currently (we don't support returning namespace nodes), but I went ahead and fixed this to work according to the spec anyway.

> +#include "impl/expression.h"
> +#include "impl/util.h"
> 
> XCode, at least, uses a flat namespace for all headers. So short names like
> expression.h and util.h are not really compatible; directories don't really
> provide a namespace. Our filenames will need to include the prefix XPath.
> 

I've renamed all the files in the impl directory.

> +PassRefPtr<XPathExpression> XPathExpression::createExpression(const String&
> expression, XPathNSResolver* resolver, ExceptionCode& ec)
> +{
> +    XPathExpression* expr = new XPathExpression;
> +    
> +    Expression::evaluationContext().resolver = resolver;
> +    if (!expr->m_statement.parse(expression.deprecatedString(), ec)) {
> +        delete expr;
> +        return 0;
> +    }
> +    
> +    return expr;
> +}
> 
> Needs to use a RefPtr for the expr local variable. It's bad form to call
> functions with an expr object floating like this, and it's bad form to do a
> delete on a shared object.
> 

Fixed

> +    XPathResult* result = new
> XPathResult(static_cast<EventTargetNode*>(eventTarget),
> +                                          m_statement.evaluate(contextNode));
> +    
> +    if (type != XPathResult::ANY_TYPE) {
> +        result->convertTo(type, ec);
> +
> +        if (ec)
> +            return 0;
> +    }
> +
> +    return result;
> 
> The result here should be a RefPtr to avoid a storage leak in the case where
> convertTo fails.

Fixed

> 
> +    // Apparently Node::lookupNamespaceURI doesn't do this.
> +    if (prefix == "xml")
> +        return "http://www.w3.org/XML/1998/namespace";
> 
> Is this a bug in lookupNamespaceURI or not? I don't like leaving the comment
> like this. I'd like to be clearer on whether this is correct or not.

It's not a bug. Node::lookupNamespaceURI shouldn't special-case the xml prefix. The XPath spec says that XPathNSResolver::lookupNamespaceURI should though. I've clarified this in the comment.

> 
> m_node in XPathNSResolver needs to be a RefPtr.

Fixed.

> 
> I think NodeSet is an awful name for a Vector of node pointers!

The name in the XPath spec is NodeSet, but I've changed this to NodeVector anyway.

> 
> Expression::optimize overwrites m_constantValue without deleting the old value.
> Is it guaranteed to only be called once?

Turns out it wasn't called at all! I've fixed this to have it be called once and I added an ASSERT to make sure this is the case.

> 
> +    explicit Value(Node *value);
> +    explicit Value(const NodeSet& value);
> +    explicit Value(bool value);
> +    explicit Value(double value);
> +    explicit Value(const String& value);
> 
> Why does the Value constructor need to be marked explicit? It doesn't seem
> harmful to have an implicit conversion to a Value, and we could remove tons of
> explicit calls to the Value constructor.

Fixed.

> 
> +            if (rightVal == 0.0 || rightVal == -0.0)
> 
> The way floating point works, both of these expressions are the same. Negative
> 0 and positive 0 return the same thing. But also, why have this check? Floating
> point correctly produces infinities and NaN's as needed for cases like this.
> THere's no need for our code to do a redunddant check.

Right, I've removed that.

> 
> In NumericOp::doEvaluate:
> 
> +        default:
> +            assert(0);
> +        return Value();
> 
> If you leave out the default case from the switch statement, gcc will warn if
> one of the enum cases is not handled. So you should do that.

Fixed.

> 
> +    Parser(const Parser &rhs);                  // disabled
> +    Parser &operator=(const Parser &rhs);       // disabled
> 
> Preferred style for this is to inherit from Noncopyable.

Fixed.

> 
> Can Value go in its own header file, instead of with Expression?
> 

Sure, fixed.

> +        if (a.isNodeset())
> +            node = a.toNodeSet()[0].get();
> 
> If there are no nodes in the set, then this will crash.

Fixed. 

> 
> Patch doesn't include the NodeSet class!
> 
> +    return Value(node->localName().deprecatedString());
> 
> Value now takes a String, so this is going to convert to DeprecatedString and
> then back!

Fixed.

> 
> +    // extract 'en' out of 'en-us'
> +    langNodeValue = langNodeValue.left(langNodeValue.find('-'));
> 
> What does this do when langNodeValue doesn't have a "-".

Whoops. Fixed to make it work like the spec says.

> 
> +        LOG(XPath, "sum() expects <nodeset>\n");
> 
> Don't use "\n" in LOG, since it already terminates lines. This is in all the
> LOG statements.

Fixed.

> 
> +    const double num = arg(0)->evaluate().toNumber();
> +
> +    if (isnan(num) || isinf(num)) {
> +        return Value(num);
> +    }
> +
> +    return Value(floor(num));
> 
> Excessive use of const on local variable here and elsewhere.
> 

Fixed.

> What's the point of checking for nan and inf before calling floor? It already
> handles those cases properly.

Fixed.

> 
> +    return Value(double(round(arg(0)->evaluate().toNumber())));
> 
> What's the point of the cast to double here? THe round function returns a
> double.

Fixed.

> 
> +    static FunctionMapping functions[] = {
> 
> Need to be static const, not just static.
> 
> +    static const unsigned int numFunctions = sizeof(functions) /
> sizeof(functions[ 0 ]);
> 
> No need for static here. I believe with static we get a global variable rather
> than a compile time constant.

Fixed.

> 
> Since we're using objects that are allocated and returned, I think we need to
> be very careful and come up with a calling convention that makes it clear that
> objects are allocated.
> 
> +Function *FunctionLibrary::getFunction(const char *name, const
> Vector<Expression*> &args) const
> 
> There's nothing about the name of this that makes it clear to me that it
> allocates its results and you are responsible for deleting it. Should talk to
> Maciej about the memory allocation strategy.
> 

I've renamed this to createFunction.

> +            Node *n = context->firstChild();
> +            while (n) {
> +                nodes.append(n);
> +                n = n->nextSibling();
> +            }
> 
> +            Node *n = context->parentNode();
> +            while (n) {
> +                nodes.append(n);
> +                n = n->parentNode();
> +            }
> +            return nodes;
> 
> +            Node *n = context->nextSibling();
> +            while (n) {
> +                nodes.append(n);
> +                n = n->nextSibling();
> +            }
> 
> I prefer for statements for this sort of thing. Also, with a for statement you
> would not need the outer braces.

Fixed.

> 
> +        default:
> +            LOG(XPath, "Unknown axis %s passed to Step::nodesInAxis",
> axisAsString(m_axis).ascii());
> 
> Same comment about default here as elsewhere.

Fixed.

> 
> +/* @return all ancestor nodes of the given node, in document order.
> + */
> +NodeSet getChildrenRecursively(Node *node);
> 
> This function is a bad idea. There's no need to use a recursive algorithm to
> build the list of all the children in order because we have enough pointers to
> walk the tree without that. Instead clients can write a simple loop using
> traverseNextNode and avoid building a NodeSet entirely. Also, it says "all
> ancestor nodes" but I assume it means "all desecendant nodes".
> 

I've removed this function.

> +bool isValidContextNode(WebCore::Node *node);
> 
> Need to eliminate excess WebCore:: prefixes like this one.
> 

Fixed.

> XPathGrammar.y needs a strategy to delete the nodes if there's a parse failure.
> You can't just use new inside a Yacc grammar. See the JavaScript grammar and
> the CSS grammar for examples of how to do this.

I've fixed this by keeping around sets of the different object types allocated by the parser. When the parse fails all the objects in the sets are delete. It's a bit kludgy but it works.

> 
> Don't use cell() on QChar. Instead use unicode(), which is more efficient.
> 

Fixed.

> There are a lot of return statements with else statements after them. I think
> it's better style not to do that.
> 

Fixed.

> +>>>>>>> .r14202
> 
> Oops! Please remove that.
> 

Fixed.

Phew. Thanks for the thorough review!

[Darin Adler]

Comment on attachment 8163 [details]
Address Darin's comments

There's still a remnant of the old code path in setDOMException -- the name variable doesn't need to be declared before the big if statement, since it's set entirely afterward.

+    Token(int _type): type(_type), intValue(0) {}

Identifiers with an _ prefix are reserved for the compiler and library. We should not use them in new code even though we can't easily eliminate them all from old code.

Almost all the braces in the case statements in Step::nodesInAxis could be removed. Removing some of the blank lines as well would make that function a bit more consistent and easy to read.

[Darin Adler]

Sorry, I'm close to saying review+ but I am making comments as I go and I actually hit submit.

[Darin Adler]

Comment on attachment 8163 [details]
Address Darin's comments

Seems that unregisterString calls are always paired with a delete.

+    return double();

That's just a "return 0" in sheep's clothing.

+    return bool();

And this is just a "return false".

+            return m_bool ? 1 : 0;

That's the same as return m_bool.

+            else if (m_number == 0)
+                return "0";

Do we really need a special case for that? What *does* DeprecatedString::number do with NaN, 0, and infinity?

These are a few things that could still be improved, but I think this is ready to go.

r=me

[Anders Carlsson]

(In reply to comment #22)
> Do we really need a special case for that? What *does* DeprecatedString::number
> do with NaN, 0, and infinity?
>

::number just uses sprintf, which means that infinity can be converted to either "inf" or "infinity" whereas the XPath spec requires that the value is converted to "Infinity", according to http://www.w3.org/TR/xpath#function-string
 
> These are a few things that could still be improved, but I think this is ready
> to go.
> 
> r=me
> 

Thanks

[Anders Carlsson]

*** Bug 5576 has been marked as a duplicate of this bug. ***

[Jesse Costello-Good]

Thanks to the Safari team for being so responsive regarding requests for better advanced AJAX support. Safari is quickly becoming a 1st class AJAX platform.