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