Reviewed by Darin.
[WebKit-https.git] / WebCore / xml / XPathParser.cpp
1 /*
2  * Copyright 2005 Maksim Orlovich <maksim@kde.org>
3  * Copyright (C) 2006 Apple Computer, Inc.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "XPathParser.h"
29
30 #if ENABLE(XPATH)
31
32 #include "ExceptionCode.h"
33 #include "StringHash.h"
34 #include "XPathEvaluator.h"
35 #include "XPathNSResolver.h"
36 #include "XPathStep.h"
37
38 int xpathyyparse(void*);
39
40 using namespace WTF;
41 using namespace Unicode;
42
43 namespace WebCore {
44 namespace XPath {
45
46 class LocationPath;
47
48 #include "XPathGrammar.h"    
49
50 Parser* Parser::currentParser = 0;
51     
52 enum XMLCat { NameStart, NameCont, NotPartOfName };
53
54 static XMLCat charCat(UChar aChar)
55 {
56     //### might need to add some special cases from the XML spec.
57
58     if (aChar == '_')
59         return NameStart;
60
61     if (aChar == '.' || aChar == '-')
62         return NameCont;
63     CharCategory category = Unicode::category(aChar);
64     if (category & (Letter_Uppercase | Letter_Lowercase | Letter_Other | Letter_Titlecase | Number_Letter))
65         return NameStart;
66     if (category & (Mark_NonSpacing | Mark_SpacingCombining | Mark_Enclosing | Letter_Modifier | Number_DecimalDigit))
67         return NameCont;
68     return NotPartOfName;
69 }
70
71 static void setUpAxisNamesMap(HashMap<String, Step::Axis>& axisNames)
72 {
73     struct AxisName {
74         const char* name;
75         Step::Axis axis;
76     };
77     const AxisName axisNameList[] = {
78         { "ancestor", Step::AncestorAxis },
79         { "ancestor-or-self", Step::AncestorOrSelfAxis },
80         { "attribute", Step::AttributeAxis },
81         { "child", Step::ChildAxis },
82         { "descendant", Step::DescendantAxis },
83         { "descendant-or-self", Step::DescendantOrSelfAxis },
84         { "following", Step::FollowingAxis },
85         { "following-sibling", Step::FollowingSiblingAxis },
86         { "namespace", Step::NamespaceAxis },
87         { "parent", Step::ParentAxis },
88         { "preceding", Step::PrecedingAxis },
89         { "preceding-sibling", Step::PrecedingSiblingAxis },
90         { "self", Step::SelfAxis }
91     };
92     for (unsigned i = 0; i < sizeof(axisNameList) / sizeof(axisNameList[0]); ++i)
93         axisNames.set(axisNameList[i].name, axisNameList[i].axis);
94 }
95
96 static bool isAxisName(const String& name, Step::Axis& type)
97 {
98     static HashMap<String, Step::Axis> axisNames;
99
100     if (axisNames.isEmpty())
101         setUpAxisNamesMap(axisNames);
102
103     HashMap<String, Step::Axis>::iterator it = axisNames.find(name);
104     if (it == axisNames.end())
105         return false;
106     type = it->second;
107     return true;
108 }
109
110 static bool isNodeTypeName(const String& name)
111 {
112     static HashSet<String> nodeTypeNames;
113     if (nodeTypeNames.isEmpty()) {
114         nodeTypeNames.add("comment");
115         nodeTypeNames.add("text");
116         nodeTypeNames.add("processing-instruction");
117         nodeTypeNames.add("node");
118     }
119     return nodeTypeNames.contains(name);
120 }
121
122 /* Returns whether the last parsed token matches the [32] Operator rule
123  * (check http://www.w3.org/TR/xpath#exprlex). Necessary to disambiguate
124  * the tokens.
125  */
126 bool Parser::isOperatorContext() const
127 {
128     if (m_nextPos == 0)
129         return false;
130
131     switch (m_lastTokenType) {
132         case AND: case OR: case MULOP:
133         case '/': case SLASHSLASH: case '|': case PLUS: case MINUS:
134         case EQOP: case RELOP:
135         case '@': case AXISNAME:   case '(': case '[':
136             return false;
137         default:
138             return true;
139     }
140 }
141
142 void Parser::skipWS()
143 {
144     while (m_nextPos < m_data.length() && DeprecatedChar(m_data[m_nextPos]).isSpace())
145         ++m_nextPos;
146 }
147
148 Token Parser::makeTokenAndAdvance(int code, int advance)
149 {
150     m_nextPos += advance;
151     return Token(code);
152 }
153
154 Token Parser::makeTokenAndAdvance(int code, NumericOp::Opcode val, int advance)
155 {
156     m_nextPos += advance;
157     return Token(code, val);
158 }
159
160 Token Parser::makeTokenAndAdvance(int code, EqTestOp::Opcode val, int advance)
161 {
162     m_nextPos += advance;
163     return Token(code, val);
164 }
165
166 // Returns next char if it's there and interesting, 0 otherwise
167 char Parser::peekAheadHelper()
168 {
169     if (m_nextPos + 1 >= m_data.length())
170         return 0;
171     UChar next = m_data[m_nextPos + 1];
172     if (next >= 0xff)
173         return 0;
174     return next;
175 }
176
177 char Parser::peekCurHelper()
178 {
179     if (m_nextPos >= m_data.length())
180         return 0;
181     UChar next = m_data[m_nextPos];
182     if (next >= 0xff)
183         return 0;
184     return next;
185 }
186
187 Token Parser::lexString()
188 {
189     UChar delimiter = m_data[m_nextPos];
190     int startPos = m_nextPos + 1;
191
192     for (m_nextPos = startPos; m_nextPos < m_data.length(); ++m_nextPos) {
193         if (m_data[m_nextPos] == delimiter) {
194             String value = m_data.substring(startPos, m_nextPos - startPos);
195             if (value.isNull())
196                 value = "";
197             ++m_nextPos; // Consume the char.
198             return Token(LITERAL, value);
199         }
200     }
201
202     // Ouch, went off the end -- report error.
203     return Token(ERROR);
204 }
205
206 Token Parser::lexNumber()
207 {
208     int startPos = m_nextPos;
209     bool seenDot = false;
210
211     // Go until end or a non-digits character.
212     for (; m_nextPos < m_data.length(); ++m_nextPos) {
213         UChar aChar = m_data[m_nextPos];
214         if (aChar >= 0xff) break;
215
216         if (aChar < '0' || aChar > '9') {
217             if (aChar == '.' && !seenDot)
218                 seenDot = true;
219             else
220                 break;
221         }
222     }
223
224     return Token(NUMBER, m_data.substring(startPos, m_nextPos - startPos));
225 }
226
227 bool Parser::lexNCName(String& name)
228 {
229     int startPos = m_nextPos;
230     if (m_nextPos >= m_data.length())
231         return false;
232
233     if (charCat(m_data[m_nextPos]) != NameStart)
234         return false;
235
236     // Keep going until we get a character that's not good for names.
237     for (; m_nextPos < m_data.length(); ++m_nextPos)
238         if (charCat(m_data[m_nextPos]) == NotPartOfName)
239             break;
240
241     name = m_data.substring(startPos, m_nextPos - startPos);
242     return true;
243 }
244
245 bool Parser::lexQName(String& name)
246 {
247     String n1;
248     if (!lexNCName(n1))
249         return false;
250
251     skipWS();
252
253     // If the next character is :, what we just got it the prefix, if not,
254     // it's the whole thing.
255     if (peekAheadHelper() != ':') {
256         name = n1;
257         return true;
258     }
259
260     String n2;
261     if (!lexNCName(n2))
262         return false;
263
264     name = n1 + ":" + n2;
265     return true;
266 }
267
268 Token Parser::nextTokenInternal()
269 {
270     skipWS();
271
272     if (m_nextPos >= m_data.length())
273         return Token(0);
274
275     char code = peekCurHelper();
276     switch (code) {
277         case '(': case ')': case '[': case ']':
278         case '@': case ',': case '|':
279             return makeTokenAndAdvance(code);
280         case '\'':
281         case '\"':
282             return lexString();
283         case '0': case '1': case '2': case '3': case '4':
284         case '5': case '6': case '7': case '8': case '9':
285             return lexNumber();
286         case '.': {
287             char next = peekAheadHelper();
288             if (next == '.')
289                 return makeTokenAndAdvance(DOTDOT, 2);
290             if (next >= '0' && next <= '9')
291                 return lexNumber();
292             return makeTokenAndAdvance('.');
293         }
294         case '/':
295             if (peekAheadHelper() == '/')
296                 return makeTokenAndAdvance(SLASHSLASH, 2);
297             return makeTokenAndAdvance('/');
298         case '+':
299             return makeTokenAndAdvance(PLUS);
300         case '-':
301             return makeTokenAndAdvance(MINUS);
302         case '=':
303             return makeTokenAndAdvance(EQOP, EqTestOp::OP_EQ);
304         case '!':
305             if (peekAheadHelper() == '=')
306                 return makeTokenAndAdvance(EQOP, EqTestOp::OP_NE, 2);
307             return Token(ERROR);
308         case '<':
309             if (peekAheadHelper() == '=')
310                 return makeTokenAndAdvance(RELOP, EqTestOp::OP_LE, 2);
311             return makeTokenAndAdvance(RELOP, EqTestOp::OP_LT);
312         case '>':
313             if (peekAheadHelper() == '=')
314                 return makeTokenAndAdvance(RELOP, EqTestOp::OP_GE, 2);
315             return makeTokenAndAdvance(RELOP, EqTestOp::OP_GT);
316         case '*':
317             if (isOperatorContext())
318                 return makeTokenAndAdvance(MULOP, NumericOp::OP_Mul);
319             ++m_nextPos;
320             return Token(NAMETEST, "*");
321         case '$': { // $ QName
322             m_nextPos++;
323             String name;
324             if (!lexQName(name))
325                 return Token(ERROR);
326             return Token(VARIABLEREFERENCE, name);
327         }
328     }
329
330     String name;
331     if (!lexNCName(name))
332         return Token(ERROR);
333
334     skipWS();
335     // If we're in an operator context, check for any operator names
336     if (isOperatorContext()) {
337         if (name == "and") //### hash?
338             return Token(AND);
339         if (name == "or")
340             return Token(OR);
341         if (name == "mod")
342             return Token(MULOP, NumericOp::OP_Mod);
343         if (name == "div")
344             return Token(MULOP, NumericOp::OP_Div);
345     }
346
347     // See whether we are at a :
348     if (peekCurHelper() == ':') {
349         m_nextPos++;
350         // Any chance it's an axis name?
351         if (peekCurHelper() == ':') {
352             m_nextPos++;
353             
354             //It might be an axis name.
355             Step::Axis axis;
356             if (isAxisName(name, axis))
357                 return Token(AXISNAME, axis);
358             // Ugh, :: is only valid in axis names -> error
359             return Token(ERROR);
360         }
361
362         // Seems like this is a fully qualified qname, or perhaps the * modified one from NameTest
363         skipWS();
364         if (peekCurHelper() == '*') {
365             m_nextPos++;
366             return Token(NAMETEST, name + ":*");
367         }
368         
369         // Make a full qname.
370         String n2;
371         if (!lexNCName(n2))
372             return Token(ERROR);
373         
374         name = name + ":" + n2;
375     }
376
377     skipWS();
378     if (peekCurHelper() == '(') {
379         //note: we don't swallow the (here!
380         
381         //either node type of function name
382         if (isNodeTypeName(name)) {
383             if (name == "processing-instruction")
384                 return Token(PI, name);
385
386             return Token(NODETYPE, name);
387         }
388         //must be a function name.
389         return Token(FUNCTIONNAME, name);
390     }
391
392     // At this point, it must be NAMETEST.
393     return Token(NAMETEST, name);
394 }
395
396 Token Parser::nextToken()
397 {
398     Token toRet = nextTokenInternal();
399     m_lastTokenType = toRet.type;
400     return toRet;
401 }
402
403 Parser::Parser()
404 {
405     reset(String());
406 }
407
408 void Parser::reset(const String& data)
409 {
410     m_nextPos = 0;
411     m_data = data;
412     m_lastTokenType = 0;
413     
414     m_topExpr = 0;
415     m_gotNamespaceError = false;
416 }
417
418 int Parser::lex(void* data)
419 {
420     YYSTYPE* yylval = static_cast<YYSTYPE*>(data);
421     Token tok = nextToken();
422
423     switch (tok.type) {
424         case AXISNAME:
425             yylval->axis = tok.axis;
426             break;
427         case MULOP:
428             yylval->numop = tok.numop;
429             break;
430         case RELOP:
431         case EQOP:
432             yylval->eqop = tok.eqop;
433             break;
434         case NODETYPE:
435         case PI:
436         case FUNCTIONNAME:
437         case LITERAL:
438         case VARIABLEREFERENCE:
439         case NUMBER:
440         case NAMETEST:
441             yylval->str = new String(tok.str);
442             registerString(yylval->str);
443             break;
444     }
445
446     return tok.type;
447 }
448
449 bool Parser::expandQName(const String& qName, String& localName, String& namespaceURI)
450 {
451     int colon = qName.find(':');
452     if (colon >= 0) {
453         if (!m_resolver)
454             return false;
455         namespaceURI = m_resolver->lookupNamespaceURI(qName.left(colon));
456         if (namespaceURI.isNull())
457             return false;
458         localName = qName.substring(colon + 1);
459     } else
460         localName = qName;
461     
462     return true;
463 }
464
465 Expression* Parser::parseStatement(const String& statement, PassRefPtr<XPathNSResolver> resolver, ExceptionCode& ec)
466 {
467     reset(statement);
468
469     m_resolver = resolver;
470     
471     Parser* oldParser = currentParser;
472     currentParser = this;
473     int parseError = xpathyyparse(this);
474     currentParser = oldParser;
475
476     if (parseError) {
477         deleteAllValues(m_parseNodes);
478         m_parseNodes.clear();
479
480         HashSet<Vector<Predicate*>*>::iterator pend = m_predicateVectors.end();
481         for (HashSet<Vector<Predicate*>*>::iterator it = m_predicateVectors.begin(); it != pend; ++it) {
482             deleteAllValues(**it);
483             delete *it;
484         }
485         m_predicateVectors.clear();
486
487         HashSet<Vector<Expression*>*>::iterator eend = m_expressionVectors.end();
488         for (HashSet<Vector<Expression*>*>::iterator it = m_expressionVectors.begin(); it != eend; ++it) {
489             deleteAllValues(**it);
490             delete *it;
491         }
492         m_expressionVectors.clear();
493
494         deleteAllValues(m_strings);
495         m_strings.clear();
496
497         m_topExpr = 0;
498
499         if (m_gotNamespaceError)
500             ec = NAMESPACE_ERR;
501         else
502             ec = INVALID_EXPRESSION_ERR;
503         return 0;
504     }
505
506     ASSERT(m_parseNodes.size() == 1);
507     ASSERT(*m_parseNodes.begin() == m_topExpr);
508     ASSERT(m_expressionVectors.size() == 0);
509     ASSERT(m_predicateVectors.size() == 0);
510     ASSERT(m_strings.size() == 0);
511
512     m_parseNodes.clear();
513     Expression* result = m_topExpr;
514     m_topExpr = 0;
515
516     return result;
517 }
518
519 void Parser::registerParseNode(ParseNode* node)
520 {
521     if (node == 0)
522         return;
523     
524     ASSERT(!m_parseNodes.contains(node));
525     
526     m_parseNodes.add(node);
527 }
528
529 void Parser::unregisterParseNode(ParseNode* node)
530 {
531     if (node == 0)
532         return;
533     
534     ASSERT(m_parseNodes.contains(node));
535
536     m_parseNodes.remove(node);
537 }
538
539 void Parser::registerPredicateVector(Vector<Predicate*>* vector)
540 {
541     if (vector == 0)
542         return;
543
544     ASSERT(!m_predicateVectors.contains(vector));
545     
546     m_predicateVectors.add(vector);
547 }
548
549 void Parser::deletePredicateVector(Vector<Predicate*>* vector)
550 {
551     if (vector == 0)
552         return;
553
554     ASSERT(m_predicateVectors.contains(vector));
555     
556     m_predicateVectors.remove(vector);
557     delete vector;
558 }
559
560
561 void Parser::registerExpressionVector(Vector<Expression*>* vector)
562 {
563     if (vector == 0)
564         return;
565
566     ASSERT(!m_expressionVectors.contains(vector));
567     
568     m_expressionVectors.add(vector);    
569 }
570
571 void Parser::deleteExpressionVector(Vector<Expression*>* vector)
572 {
573     if (vector == 0)
574         return;
575
576     ASSERT(m_expressionVectors.contains(vector));
577     
578     m_expressionVectors.remove(vector);
579     delete vector;
580 }
581
582 void Parser::registerString(String* s)
583 {
584     if (s == 0)
585         return;
586     
587     ASSERT(!m_strings.contains(s));
588     
589     m_strings.add(s);        
590 }
591
592 void Parser::deleteString(String* s)
593 {
594     if (s == 0)
595         return;
596     
597     ASSERT(m_strings.contains(s));
598     
599     m_strings.remove(s);
600     delete s;
601 }
602
603 }
604 }
605
606 #endif // ENABLE(XPATH)