Move XPath from ExceptionCode to Exception
[WebKit-https.git] / Source / WebCore / xml / XPathParser.cpp
1 /*
2  * Copyright 2005 Maksim Orlovich <maksim@kde.org>
3  * Copyright (C) 2006, 2013 Apple Inc. All rights reserved.
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 #include "ExceptionCode.h"
32 #include "XPathEvaluator.h"
33 #include "XPathException.h"
34 #include "XPathNSResolver.h"
35 #include "XPathPath.h"
36 #include "XPathStep.h"
37 #include <wtf/NeverDestroyed.h>
38 #include <wtf/StdLibExtras.h>
39 #include <wtf/text/StringHash.h>
40
41 using namespace WebCore;
42 using namespace XPath;
43
44 extern int xpathyyparse(Parser&);
45
46 #include "XPathGrammar.h"
47
48 namespace WebCore {
49 namespace XPath {
50
51 struct Parser::Token {
52     int type;
53     String string;
54     Step::Axis axis;
55     NumericOp::Opcode numericOpcode;
56     EqTestOp::Opcode equalityTestOpcode;
57
58     Token(int type) : type(type) { }
59     Token(int type, const String& string) : type(type), string(string) { }
60     Token(int type, Step::Axis axis) : type(type), axis(axis) { }
61     Token(int type, NumericOp::Opcode opcode) : type(type), numericOpcode(opcode) { }
62     Token(int type, EqTestOp::Opcode opcode) : type(type), equalityTestOpcode(opcode) { }
63 };
64
65 enum XMLCat { NameStart, NameCont, NotPartOfName };
66
67 static XMLCat charCat(UChar character)
68 {
69     if (character == '_')
70         return NameStart;
71
72     if (character == '.' || character == '-')
73         return NameCont;
74     unsigned characterTypeMask = U_GET_GC_MASK(character);
75     if (characterTypeMask & (U_GC_LU_MASK | U_GC_LL_MASK | U_GC_LO_MASK | U_GC_LT_MASK | U_GC_NL_MASK))
76         return NameStart;
77     if (characterTypeMask & (U_GC_M_MASK | U_GC_LM_MASK | U_GC_ND_MASK))
78         return NameCont;
79     return NotPartOfName;
80 }
81
82 static void populateAxisNamesMap(HashMap<String, Step::Axis>& axisNames)
83 {
84     struct AxisName {
85         const char* name;
86         Step::Axis axis;
87     };
88     const AxisName axisNameList[] = {
89         { "ancestor", Step::AncestorAxis },
90         { "ancestor-or-self", Step::AncestorOrSelfAxis },
91         { "attribute", Step::AttributeAxis },
92         { "child", Step::ChildAxis },
93         { "descendant", Step::DescendantAxis },
94         { "descendant-or-self", Step::DescendantOrSelfAxis },
95         { "following", Step::FollowingAxis },
96         { "following-sibling", Step::FollowingSiblingAxis },
97         { "namespace", Step::NamespaceAxis },
98         { "parent", Step::ParentAxis },
99         { "preceding", Step::PrecedingAxis },
100         { "preceding-sibling", Step::PrecedingSiblingAxis },
101         { "self", Step::SelfAxis }
102     };
103     for (auto& axisName : axisNameList)
104         axisNames.add(axisName.name, axisName.axis);
105 }
106
107 static bool parseAxisName(const String& name, Step::Axis& type)
108 {
109     static NeverDestroyed<HashMap<String, Step::Axis>> axisNames;
110     if (axisNames.get().isEmpty())
111         populateAxisNamesMap(axisNames);
112
113     auto it = axisNames.get().find(name);
114     if (it == axisNames.get().end())
115         return false;
116     type = it->value;
117     return true;
118 }
119
120 // Returns whether the current token can possibly be a binary operator, given
121 // the previous token. Necessary to disambiguate some of the operators
122 // (* (multiply), div, and, or, mod) in the [32] Operator rule
123 // (check http://www.w3.org/TR/xpath#exprlex).
124 bool Parser::isBinaryOperatorContext() const
125 {
126     switch (m_lastTokenType) {
127     case 0:
128     case '@': case AXISNAME: case '(': case '[': case ',':
129     case AND: case OR: case MULOP:
130     case '/': case SLASHSLASH: case '|': case PLUS: case MINUS:
131     case EQOP: case RELOP:
132         return false;
133     default:
134         return true;
135     }
136 }
137
138 void Parser::skipWS()
139 {
140     while (m_nextPos < m_data.length() && isSpaceOrNewline(m_data[m_nextPos]))
141         ++m_nextPos;
142 }
143
144 Parser::Token Parser::makeTokenAndAdvance(int code, int advance)
145 {
146     m_nextPos += advance;
147     return Token(code);
148 }
149
150 Parser::Token Parser::makeTokenAndAdvance(int code, NumericOp::Opcode val, int advance)
151 {
152     m_nextPos += advance;
153     return Token(code, val);
154 }
155
156 Parser::Token Parser::makeTokenAndAdvance(int code, EqTestOp::Opcode val, int advance)
157 {
158     m_nextPos += advance;
159     return Token(code, val);
160 }
161
162 // Returns next char if it's there and interesting, 0 otherwise.
163 char Parser::peekAheadHelper()
164 {
165     if (m_nextPos + 1 >= m_data.length())
166         return 0;
167     UChar next = m_data[m_nextPos + 1];
168     if (next >= 0xff)
169         return 0;
170     return next;
171 }
172
173 char Parser::peekCurHelper()
174 {
175     if (m_nextPos >= m_data.length())
176         return 0;
177     UChar next = m_data[m_nextPos];
178     if (next >= 0xff)
179         return 0;
180     return next;
181 }
182
183 Parser::Token Parser::lexString()
184 {
185     UChar delimiter = m_data[m_nextPos];
186     int startPos = m_nextPos + 1;
187
188     for (m_nextPos = startPos; m_nextPos < m_data.length(); ++m_nextPos) {
189         if (m_data[m_nextPos] == delimiter) {
190             String value = m_data.substring(startPos, m_nextPos - startPos);
191             if (value.isNull())
192                 value = emptyString();
193             ++m_nextPos; // Consume the char.
194             return Token(LITERAL, value);
195         }
196     }
197
198     // Ouch, went off the end -- report error.
199     return Token(XPATH_ERROR);
200 }
201
202 Parser::Token Parser::lexNumber()
203 {
204     int startPos = m_nextPos;
205     bool seenDot = false;
206
207     // Go until end or a non-digits character.
208     for (; m_nextPos < m_data.length(); ++m_nextPos) {
209         UChar aChar = m_data[m_nextPos];
210         if (aChar >= 0xff) break;
211
212         if (aChar < '0' || aChar > '9') {
213             if (aChar == '.' && !seenDot)
214                 seenDot = true;
215             else
216                 break;
217         }
218     }
219
220     return Token(NUMBER, m_data.substring(startPos, m_nextPos - startPos));
221 }
222
223 bool Parser::lexNCName(String& name)
224 {
225     int startPos = m_nextPos;
226     if (m_nextPos >= m_data.length())
227         return false;
228
229     if (charCat(m_data[m_nextPos]) != NameStart)
230         return false;
231
232     // Keep going until we get a character that's not good for names.
233     for (; m_nextPos < m_data.length(); ++m_nextPos)
234         if (charCat(m_data[m_nextPos]) == NotPartOfName)
235             break;
236
237     name = m_data.substring(startPos, m_nextPos - startPos);
238     return true;
239 }
240
241 bool Parser::lexQName(String& name)
242 {
243     String n1;
244     if (!lexNCName(n1))
245         return false;
246
247     skipWS();
248
249     // If the next character is :, what we just got it the prefix, if not,
250     // it's the whole thing.
251     if (peekAheadHelper() != ':') {
252         name = n1;
253         return true;
254     }
255
256     String n2;
257     if (!lexNCName(n2))
258         return false;
259
260     name = n1 + ":" + n2;
261     return true;
262 }
263
264 inline Parser::Token Parser::nextTokenInternal()
265 {
266     skipWS();
267
268     if (m_nextPos >= m_data.length())
269         return Token(0);
270
271     char code = peekCurHelper();
272     switch (code) {
273     case '(': case ')': case '[': case ']':
274     case '@': case ',': case '|':
275         return makeTokenAndAdvance(code);
276     case '\'':
277     case '\"':
278         return lexString();
279     case '0': case '1': case '2': case '3': case '4':
280     case '5': case '6': case '7': case '8': case '9':
281         return lexNumber();
282     case '.': {
283         char next = peekAheadHelper();
284         if (next == '.')
285             return makeTokenAndAdvance(DOTDOT, 2);
286         if (next >= '0' && next <= '9')
287             return lexNumber();
288         return makeTokenAndAdvance('.');
289     }
290     case '/':
291         if (peekAheadHelper() == '/')
292             return makeTokenAndAdvance(SLASHSLASH, 2);
293         return makeTokenAndAdvance('/');
294     case '+':
295         return makeTokenAndAdvance(PLUS);
296     case '-':
297         return makeTokenAndAdvance(MINUS);
298     case '=':
299         return makeTokenAndAdvance(EQOP, EqTestOp::OP_EQ);
300     case '!':
301         if (peekAheadHelper() == '=')
302             return makeTokenAndAdvance(EQOP, EqTestOp::OP_NE, 2);
303         return Token(XPATH_ERROR);
304     case '<':
305         if (peekAheadHelper() == '=')
306             return makeTokenAndAdvance(RELOP, EqTestOp::OP_LE, 2);
307         return makeTokenAndAdvance(RELOP, EqTestOp::OP_LT);
308     case '>':
309         if (peekAheadHelper() == '=')
310             return makeTokenAndAdvance(RELOP, EqTestOp::OP_GE, 2);
311         return makeTokenAndAdvance(RELOP, EqTestOp::OP_GT);
312     case '*':
313         if (isBinaryOperatorContext())
314             return makeTokenAndAdvance(MULOP, NumericOp::OP_Mul);
315         ++m_nextPos;
316         return Token(NAMETEST, "*");
317     case '$': { // $ QName
318         m_nextPos++;
319         String name;
320         if (!lexQName(name))
321             return Token(XPATH_ERROR);
322         return Token(VARIABLEREFERENCE, name);
323     }
324     }
325
326     String name;
327     if (!lexNCName(name))
328         return Token(XPATH_ERROR);
329
330     skipWS();
331     // If we're in an operator context, check for any operator names
332     if (isBinaryOperatorContext()) {
333         if (name == "and") //### hash?
334             return Token(AND);
335         if (name == "or")
336             return Token(OR);
337         if (name == "mod")
338             return Token(MULOP, NumericOp::OP_Mod);
339         if (name == "div")
340             return Token(MULOP, NumericOp::OP_Div);
341     }
342
343     // See whether we are at a :
344     if (peekCurHelper() == ':') {
345         m_nextPos++;
346         // Any chance it's an axis name?
347         if (peekCurHelper() == ':') {
348             m_nextPos++;
349             
350             //It might be an axis name.
351             Step::Axis axis;
352             if (parseAxisName(name, axis))
353                 return Token(AXISNAME, axis);
354             // Ugh, :: is only valid in axis names -> error
355             return Token(XPATH_ERROR);
356         }
357
358         // Seems like this is a fully qualified qname, or perhaps the * modified one from NameTest
359         skipWS();
360         if (peekCurHelper() == '*') {
361             m_nextPos++;
362             return Token(NAMETEST, name + ":*");
363         }
364         
365         // Make a full qname.
366         String n2;
367         if (!lexNCName(n2))
368             return Token(XPATH_ERROR);
369         
370         name = name + ":" + n2;
371     }
372
373     skipWS();
374
375     if (peekCurHelper() == '(') {
376         // note: we don't swallow the '(' here!
377
378         // Either node type oor function name.
379
380         if (name == "processing-instruction")
381             return Token(PI);
382         if (name == "node")
383             return Token(NODE);
384         if (name == "text")
385             return Token(TEXT);
386         if (name == "comment")
387             return Token(COMMENT);
388
389         return Token(FUNCTIONNAME, name);
390     }
391
392     // At this point, it must be NAMETEST.
393     return Token(NAMETEST, name);
394 }
395
396 inline Parser::Token Parser::nextToken()
397 {
398     Token token = nextTokenInternal();
399     m_lastTokenType = token.type;
400     return token;
401 }
402
403 Parser::Parser(const String& statement, RefPtr<XPathNSResolver>&& resolver)
404     : m_data(statement)
405     , m_resolver(WTFMove(resolver))
406 {
407 }
408
409 int Parser::lex(YYSTYPE& yylval)
410 {
411     Token token = nextToken();
412
413     switch (token.type) {
414     case AXISNAME:
415         yylval.axis = token.axis;
416         break;
417     case MULOP:
418         yylval.numericOpcode = token.numericOpcode;
419         break;
420     case RELOP:
421     case EQOP:
422         yylval.equalityTestOpcode = token.equalityTestOpcode;
423         break;
424     case NODETYPE:
425     case FUNCTIONNAME:
426     case LITERAL:
427     case VARIABLEREFERENCE:
428     case NUMBER:
429     case NAMETEST:
430         yylval.string = token.string.releaseImpl().leakRef();
431         break;
432     }
433
434     return token.type;
435 }
436
437 bool Parser::expandQualifiedName(const String& qualifiedName, String& localName, String& namespaceURI)
438 {
439     size_t colon = qualifiedName.find(':');
440     if (colon != notFound) {
441         if (!m_resolver) {
442             m_sawNamespaceError = true;
443             return false;
444         }
445         namespaceURI = m_resolver->lookupNamespaceURI(qualifiedName.left(colon));
446         if (namespaceURI.isNull()) {
447             m_sawNamespaceError = true;
448             return false;
449         }
450         localName = qualifiedName.substring(colon + 1);
451     } else
452         localName = qualifiedName;
453     return true;
454 }
455
456 ExceptionOr<std::unique_ptr<Expression>> Parser::parseStatement(const String& statement, RefPtr<XPathNSResolver>&& resolver)
457 {
458     Parser parser { statement, WTFMove(resolver) };
459
460     int parseError = xpathyyparse(parser);
461
462     if (parser.m_sawNamespaceError)
463         return Exception { NAMESPACE_ERR };
464
465     if (parseError)
466         return Exception { XPathException::INVALID_EXPRESSION_ERR };
467
468     return WTFMove(parser.m_result);
469 }
470
471 } }