1 /*

     2  * Copyright 2005 Maksim Orlovich <maksim@kde.org>

     3  * Copyright (C) 2006 Apple Computer, Inc.

     4  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions

     8  * are met:

     9  * 

    10  * 1. Redistributions of source code must retain the above copyright

    11  *    notice, this list of conditions and the following disclaimer.

    12  * 2. Redistributions in binary form must reproduce the above copyright

    13  *    notice, this list of conditions and the following disclaimer in the

    14  *    documentation and/or other materials provided with the distribution.

    15  * 

    16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

    17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

    18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

    19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

    20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

    21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

    22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

    23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

    25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    26  */

    27 

    28 #include "config.h"

    29 #include "XPathParser.h"

    30 

    31 #if ENABLE(XPATH)

    32 

    33 #include "ExceptionCode.h"

    34 #include "StringHash.h"

    35 #include "XPathEvaluator.h"

    36 #include "XPathException.h"

    37 #include "XPathNSResolver.h"

    38 #include "XPathStep.h"

    39 #include <wtf/StdLibExtras.h>

    40 

    41 int xpathyyparse(void*);

    42 

    43 using namespace WTF;

    44 using namespace Unicode;

    45 

    46 namespace WebCore {

    47 namespace XPath {

    48 

    49 class LocationPath;

    50 

    51 #include "XPathGrammar.h"    

    52 

    53 Parser* Parser::currentParser = 0;

    54     

    55 enum XMLCat { NameStart, NameCont, NotPartOfName };

    56 

    57 typedef HashMap<String, Step::Axis> AxisNamesMap;

    58 

    59 static XMLCat charCat(UChar aChar)

    60 {

    61     //### might need to add some special cases from the XML spec.

    62 

    63     if (aChar == '_')

    64         return NameStart;

    65 

    66     if (aChar == '.' || aChar == '-')

    67         return NameCont;

    68     CharCategory category = Unicode::category(aChar);

    69     if (category & (Letter_Uppercase | Letter_Lowercase | Letter_Other | Letter_Titlecase | Number_Letter))

    70         return NameStart;

    71     if (category & (Mark_NonSpacing | Mark_SpacingCombining | Mark_Enclosing | Letter_Modifier | Number_DecimalDigit))

    72         return NameCont;

    73     return NotPartOfName;

    74 }

    75 

    76 static void setUpAxisNamesMap(AxisNamesMap& axisNames)

    77 {

    78     struct AxisName {

    79         const char* name;

    80         Step::Axis axis;

    81     };

    82     const AxisName axisNameList[] = {

    83         { "ancestor", Step::AncestorAxis },

    84         { "ancestor-or-self", Step::AncestorOrSelfAxis },

    85         { "attribute", Step::AttributeAxis },

    86         { "child", Step::ChildAxis },

    87         { "descendant", Step::DescendantAxis },

    88         { "descendant-or-self", Step::DescendantOrSelfAxis },

    89         { "following", Step::FollowingAxis },

    90         { "following-sibling", Step::FollowingSiblingAxis },

    91         { "namespace", Step::NamespaceAxis },

    92         { "parent", Step::ParentAxis },

    93         { "preceding", Step::PrecedingAxis },

    94         { "preceding-sibling", Step::PrecedingSiblingAxis },

    95         { "self", Step::SelfAxis }

    96     };

    97     for (unsigned i = 0; i < sizeof(axisNameList) / sizeof(axisNameList[0]); ++i)

    98         axisNames.set(axisNameList[i].name, axisNameList[i].axis);

    99 }

   100 

   101 static bool isAxisName(const String& name, Step::Axis& type)

   102 {

   103     DEFINE_STATIC_LOCAL(AxisNamesMap, axisNames, ());

   104 

   105     if (axisNames.isEmpty())

   106         setUpAxisNamesMap(axisNames);

   107 

   108     AxisNamesMap::iterator it = axisNames.find(name);

   109     if (it == axisNames.end())

   110         return false;

   111     type = it->second;

   112     return true;

   113 }

   114 

   115 static bool isNodeTypeName(const String& name)

   116 {

   117     DEFINE_STATIC_LOCAL(HashSet<String>, nodeTypeNames, ());

   118     if (nodeTypeNames.isEmpty()) {

   119         nodeTypeNames.add("comment");

   120         nodeTypeNames.add("text");

   121         nodeTypeNames.add("processing-instruction");

   122         nodeTypeNames.add("node");

   123     }

   124     return nodeTypeNames.contains(name);

   125 }

   126 

   127 /* Returns whether the last parsed token matches the [32] Operator rule

   128  * (check http://www.w3.org/TR/xpath#exprlex). Necessary to disambiguate

   129  * the tokens.

   130  */

   131 bool Parser::isOperatorContext() const

   132 {

   133     if (m_nextPos == 0)

   134         return false;

   135 

   136     switch (m_lastTokenType) {

   137         case AND: case OR: case MULOP:

   138         case '/': case SLASHSLASH: case '|': case PLUS: case MINUS:

   139         case EQOP: case RELOP:

   140         case '@': case AXISNAME:   case '(': case '[':

   141             return false;

   142         default:

   143             return true;

   144     }

   145 }

   146 

   147 void Parser::skipWS()

   148 {

   149     while (m_nextPos < m_data.length() && isSpaceOrNewline(m_data[m_nextPos]))

   150         ++m_nextPos;

   151 }

   152 

   153 Token Parser::makeTokenAndAdvance(int code, int advance)

   154 {

   155     m_nextPos += advance;

   156     return Token(code);

   157 }

   158 

   159 Token Parser::makeTokenAndAdvance(int code, NumericOp::Opcode val, int advance)

   160 {

   161     m_nextPos += advance;

   162     return Token(code, val);

   163 }

   164 

   165 Token Parser::makeTokenAndAdvance(int code, EqTestOp::Opcode val, int advance)

   166 {

   167     m_nextPos += advance;

   168     return Token(code, val);

   169 }

   170 

   171 // Returns next char if it's there and interesting, 0 otherwise

   172 char Parser::peekAheadHelper()

   173 {

   174     if (m_nextPos + 1 >= m_data.length())

   175         return 0;

   176     UChar next = m_data[m_nextPos + 1];

   177     if (next >= 0xff)

   178         return 0;

   179     return next;

   180 }

   181 

   182 char Parser::peekCurHelper()

   183 {

   184     if (m_nextPos >= m_data.length())

   185         return 0;

   186     UChar next = m_data[m_nextPos];

   187     if (next >= 0xff)

   188         return 0;

   189     return next;

   190 }

   191 

   192 Token Parser::lexString()

   193 {

   194     UChar delimiter = m_data[m_nextPos];

   195     int startPos = m_nextPos + 1;

   196 

   197     for (m_nextPos = startPos; m_nextPos < m_data.length(); ++m_nextPos) {

   198         if (m_data[m_nextPos] == delimiter) {

   199             String value = m_data.substring(startPos, m_nextPos - startPos);

   200             if (value.isNull())

   201                 value = "";

   202             ++m_nextPos; // Consume the char.

   203             return Token(LITERAL, value);

   204         }

   205     }

   206 

   207     // Ouch, went off the end -- report error.

   208     return Token(XPATH_ERROR);

   209 }

   210 

   211 Token Parser::lexNumber()

   212 {

   213     int startPos = m_nextPos;

   214     bool seenDot = false;

   215 

   216     // Go until end or a non-digits character.

   217     for (; m_nextPos < m_data.length(); ++m_nextPos) {

   218         UChar aChar = m_data[m_nextPos];

   219         if (aChar >= 0xff) break;

   220 

   221         if (aChar < '0' || aChar > '9') {

   222             if (aChar == '.' && !seenDot)

   223                 seenDot = true;

   224             else

   225                 break;

   226         }

   227     }

   228 

   229     return Token(NUMBER, m_data.substring(startPos, m_nextPos - startPos));

   230 }

   231 

   232 bool Parser::lexNCName(String& name)

   233 {

   234     int startPos = m_nextPos;

   235     if (m_nextPos >= m_data.length())

   236         return false;

   237 

   238     if (charCat(m_data[m_nextPos]) != NameStart)

   239         return false;

   240 

   241     // Keep going until we get a character that's not good for names.

   242     for (; m_nextPos < m_data.length(); ++m_nextPos)

   243         if (charCat(m_data[m_nextPos]) == NotPartOfName)

   244             break;

   245 

   246     name = m_data.substring(startPos, m_nextPos - startPos);

   247     return true;

   248 }

   249 

   250 bool Parser::lexQName(String& name)

   251 {

   252     String n1;

   253     if (!lexNCName(n1))

   254         return false;

   255 

   256     skipWS();

   257 

   258     // If the next character is :, what we just got it the prefix, if not,

   259     // it's the whole thing.

   260     if (peekAheadHelper() != ':') {

   261         name = n1;

   262         return true;

   263     }

   264 

   265     String n2;

   266     if (!lexNCName(n2))

   267         return false;

   268 

   269     name = n1 + ":" + n2;

   270     return true;

   271 }

   272 

   273 Token Parser::nextTokenInternal()

   274 {

   275     skipWS();

   276 

   277     if (m_nextPos >= m_data.length())

   278         return Token(0);

   279 

   280     char code = peekCurHelper();

   281     switch (code) {

   282         case '(': case ')': case '[': case ']':

   283         case '@': case ',': case '|':

   284             return makeTokenAndAdvance(code);

   285         case '\'':

   286         case '\"':

   287             return lexString();

   288         case '0': case '1': case '2': case '3': case '4':

   289         case '5': case '6': case '7': case '8': case '9':

   290             return lexNumber();

   291         case '.': {

   292             char next = peekAheadHelper();

   293             if (next == '.')

   294                 return makeTokenAndAdvance(DOTDOT, 2);

   295             if (next >= '0' && next <= '9')

   296                 return lexNumber();

   297             return makeTokenAndAdvance('.');

   298         }

   299         case '/':

   300             if (peekAheadHelper() == '/')

   301                 return makeTokenAndAdvance(SLASHSLASH, 2);

   302             return makeTokenAndAdvance('/');

   303         case '+':

   304             return makeTokenAndAdvance(PLUS);

   305         case '-':

   306             return makeTokenAndAdvance(MINUS);

   307         case '=':

   308             return makeTokenAndAdvance(EQOP, EqTestOp::OP_EQ);

   309         case '!':

   310             if (peekAheadHelper() == '=')

   311                 return makeTokenAndAdvance(EQOP, EqTestOp::OP_NE, 2);

   312             return Token(XPATH_ERROR);

   313         case '<':

   314             if (peekAheadHelper() == '=')

   315                 return makeTokenAndAdvance(RELOP, EqTestOp::OP_LE, 2);

   316             return makeTokenAndAdvance(RELOP, EqTestOp::OP_LT);

   317         case '>':

   318             if (peekAheadHelper() == '=')

   319                 return makeTokenAndAdvance(RELOP, EqTestOp::OP_GE, 2);

   320             return makeTokenAndAdvance(RELOP, EqTestOp::OP_GT);

   321         case '*':

   322             if (isOperatorContext())

   323                 return makeTokenAndAdvance(MULOP, NumericOp::OP_Mul);

   324             ++m_nextPos;

   325             return Token(NAMETEST, "*");

   326         case '$': { // $ QName

   327             m_nextPos++;

   328             String name;

   329             if (!lexQName(name))

   330                 return Token(XPATH_ERROR);

   331             return Token(VARIABLEREFERENCE, name);

   332         }

   333     }

   334 

   335     String name;

   336     if (!lexNCName(name))

   337         return Token(XPATH_ERROR);

   338 

   339     skipWS();

   340     // If we're in an operator context, check for any operator names

   341     if (isOperatorContext()) {

   342         if (name == "and") //### hash?

   343             return Token(AND);

   344         if (name == "or")

   345             return Token(OR);

   346         if (name == "mod")

   347             return Token(MULOP, NumericOp::OP_Mod);

   348         if (name == "div")

   349             return Token(MULOP, NumericOp::OP_Div);

   350     }

   351 

   352     // See whether we are at a :

   353     if (peekCurHelper() == ':') {

   354         m_nextPos++;

   355         // Any chance it's an axis name?

   356         if (peekCurHelper() == ':') {

   357             m_nextPos++;

   358             

   359             //It might be an axis name.

   360             Step::Axis axis;

   361             if (isAxisName(name, axis))

   362                 return Token(AXISNAME, axis);

   363             // Ugh, :: is only valid in axis names -> error

   364             return Token(XPATH_ERROR);

   365         }

   366 

   367         // Seems like this is a fully qualified qname, or perhaps the * modified one from NameTest

   368         skipWS();

   369         if (peekCurHelper() == '*') {

   370             m_nextPos++;

   371             return Token(NAMETEST, name + ":*");

   372         }

   373         

   374         // Make a full qname.

   375         String n2;

   376         if (!lexNCName(n2))

   377             return Token(XPATH_ERROR);

   378         

   379         name = name + ":" + n2;

   380     }

   381 

   382     skipWS();

   383     if (peekCurHelper() == '(') {

   384         //note: we don't swallow the (here!

   385         

   386         //either node type of function name

   387         if (isNodeTypeName(name)) {

   388             if (name == "processing-instruction")

   389                 return Token(PI, name);

   390 

   391             return Token(NODETYPE, name);

   392         }

   393         //must be a function name.

   394         return Token(FUNCTIONNAME, name);

   395     }

   396 

   397     // At this point, it must be NAMETEST.

   398     return Token(NAMETEST, name);

   399 }

   400 

   401 Token Parser::nextToken()

   402 {

   403     Token toRet = nextTokenInternal();

   404     m_lastTokenType = toRet.type;

   405     return toRet;

   406 }

   407 

   408 Parser::Parser()

   409 {

   410     reset(String());

   411 }

   412 

   413 void Parser::reset(const String& data)

   414 {

   415     m_nextPos = 0;

   416     m_data = data;

   417     m_lastTokenType = 0;

   418     

   419     m_topExpr = 0;

   420     m_gotNamespaceError = false;

   421 }

   422 

   423 int Parser::lex(void* data)

   424 {

   425     YYSTYPE* yylval = static_cast<YYSTYPE*>(data);

   426     Token tok = nextToken();

   427 

   428     switch (tok.type) {

   429         case AXISNAME:

   430             yylval->axis = tok.axis;

   431             break;

   432         case MULOP:

   433             yylval->numop = tok.numop;

   434             break;

   435         case RELOP:

   436         case EQOP:

   437             yylval->eqop = tok.eqop;

   438             break;

   439         case NODETYPE:

   440         case PI:

   441         case FUNCTIONNAME:

   442         case LITERAL:

   443         case VARIABLEREFERENCE:

   444         case NUMBER:

   445         case NAMETEST:

   446             yylval->str = new String(tok.str);

   447             registerString(yylval->str);

   448             break;

   449     }

   450 

   451     return tok.type;

   452 }

   453 

   454 bool Parser::expandQName(const String& qName, String& localName, String& namespaceURI)

   455 {

   456     int colon = qName.find(':');

   457     if (colon >= 0) {

   458         if (!m_resolver)

   459             return false;

   460         namespaceURI = m_resolver->lookupNamespaceURI(qName.left(colon));

   461         if (namespaceURI.isNull())

   462             return false;

   463         localName = qName.substring(colon + 1);

   464     } else

   465         localName = qName;

   466     

   467     return true;

   468 }

   469 

   470 Expression* Parser::parseStatement(const String& statement, PassRefPtr<XPathNSResolver> resolver, ExceptionCode& ec)

   471 {

   472     reset(statement);

   473 

   474     m_resolver = resolver;

   475     

   476     Parser* oldParser = currentParser;

   477     currentParser = this;

   478     int parseError = xpathyyparse(this);

   479     currentParser = oldParser;

   480 

   481     if (parseError) {

   482         deleteAllValues(m_parseNodes);

   483         m_parseNodes.clear();

   484 

   485         HashSet<Vector<Predicate*>*>::iterator pend = m_predicateVectors.end();

   486         for (HashSet<Vector<Predicate*>*>::iterator it = m_predicateVectors.begin(); it != pend; ++it) {

   487             deleteAllValues(**it);

   488             delete *it;

   489         }

   490         m_predicateVectors.clear();

   491 

   492         HashSet<Vector<Expression*>*>::iterator eend = m_expressionVectors.end();

   493         for (HashSet<Vector<Expression*>*>::iterator it = m_expressionVectors.begin(); it != eend; ++it) {

   494             deleteAllValues(**it);

   495             delete *it;

   496         }

   497         m_expressionVectors.clear();

   498 

   499         deleteAllValues(m_strings);

   500         m_strings.clear();

   501 

   502         deleteAllValues(m_nodeTests);

   503         m_nodeTests.clear();

   504 

   505         m_topExpr = 0;

   506 

   507         if (m_gotNamespaceError)

   508             ec = NAMESPACE_ERR;

   509         else

   510             ec = XPathException::INVALID_EXPRESSION_ERR;

   511         return 0;

   512     }

   513 

   514     ASSERT(m_parseNodes.size() == 1);

   515     ASSERT(*m_parseNodes.begin() == m_topExpr);

   516     ASSERT(m_expressionVectors.size() == 0);

   517     ASSERT(m_predicateVectors.size() == 0);

   518     ASSERT(m_strings.size() == 0);

   519     ASSERT(m_nodeTests.size() == 0);

   520 

   521     m_parseNodes.clear();

   522     Expression* result = m_topExpr;

   523     m_topExpr = 0;

   524 

   525     return result;

   526 }

   527 

   528 void Parser::registerParseNode(ParseNode* node)

   529 {

   530     if (node == 0)

   531         return;

   532     

   533     ASSERT(!m_parseNodes.contains(node));

   534     

   535     m_parseNodes.add(node);

   536 }

   537 

   538 void Parser::unregisterParseNode(ParseNode* node)

   539 {

   540     if (node == 0)

   541         return;

   542     

   543     ASSERT(m_parseNodes.contains(node));

   544 

   545     m_parseNodes.remove(node);

   546 }

   547 

   548 void Parser::registerPredicateVector(Vector<Predicate*>* vector)

   549 {

   550     if (vector == 0)

   551         return;

   552 

   553     ASSERT(!m_predicateVectors.contains(vector));

   554     

   555     m_predicateVectors.add(vector);

   556 }

   557 

   558 void Parser::deletePredicateVector(Vector<Predicate*>* vector)

   559 {

   560     if (vector == 0)

   561         return;

   562 

   563     ASSERT(m_predicateVectors.contains(vector));

   564     

   565     m_predicateVectors.remove(vector);

   566     delete vector;

   567 }

   568 

   569 

   570 void Parser::registerExpressionVector(Vector<Expression*>* vector)

   571 {

   572     if (vector == 0)

   573         return;

   574 

   575     ASSERT(!m_expressionVectors.contains(vector));

   576     

   577     m_expressionVectors.add(vector);    

   578 }

   579 

   580 void Parser::deleteExpressionVector(Vector<Expression*>* vector)

   581 {

   582     if (vector == 0)

   583         return;

   584 

   585     ASSERT(m_expressionVectors.contains(vector));

   586     

   587     m_expressionVectors.remove(vector);

   588     delete vector;

   589 }

   590 

   591 void Parser::registerString(String* s)

   592 {

   593     if (s == 0)

   594         return;

   595     

   596     ASSERT(!m_strings.contains(s));

   597     

   598     m_strings.add(s);        

   599 }

   600 

   601 void Parser::deleteString(String* s)

   602 {

   603     if (s == 0)

   604         return;

   605     

   606     ASSERT(m_strings.contains(s));

   607     

   608     m_strings.remove(s);

   609     delete s;

   610 }

   611 

   612 void Parser::registerNodeTest(Step::NodeTest* t)

   613 {

   614     if (t == 0)

   615         return;

   616     

   617     ASSERT(!m_nodeTests.contains(t));

   618     

   619     m_nodeTests.add(t);        

   620 }

   621 

   622 void Parser::deleteNodeTest(Step::NodeTest* t)

   623 {

   624     if (t == 0)

   625         return;

   626     

   627     ASSERT(m_nodeTests.contains(t));

   628     

   629     m_nodeTests.remove(t);

   630     delete t;

   631 }

   632 

   633 }

   634 }

   635 

   636 #endif // ENABLE(XPATH)