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