Remove an explicit ICU dependency (by lars)
[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     uint category = WTF::Unicode::category(aChar);
61     if (category & (WTF::Unicode::Letter_Uppercase|
62                     WTF::Unicode::Letter_Lowercase|
63                     WTF::Unicode::Letter_Other|
64                     WTF::Unicode::Letter_Titlecase|
65                     WTF::Unicode::Number_Letter))
66         return NameStart;
67     if (category & (WTF::Unicode::Mark_NonSpacing|
68                     WTF::Unicode::Mark_SpacingCombining|
69                     WTF::Unicode::Mark_Enclosing|
70                     WTF::Unicode::Letter_Modifier|
71                     WTF::Unicode::Number_DecimalDigit))
72         return NameCont;
73     return NotPartOfName;
74 }
75
76 static void setUpAxisNamesMap(HashMap<String, Step::Axis>& 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     static HashMap<String, Step::Axis> axisNames;
104
105     if (axisNames.isEmpty())
106         setUpAxisNamesMap(axisNames);
107
108     HashMap<String, Step::Axis>::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     static 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() && DeprecatedChar(m_data[m_nextPos]).isSpace())
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(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(ERROR);
313         case '<':
314             if (peekAheadHelper() == '=')
315                 return makeTokenAndAdvance(RELOP, NumericOp::OP_LE, 2);
316             return makeTokenAndAdvance(RELOP, NumericOp::OP_LT);
317         case '>':
318             if (peekAheadHelper() == '=')
319                 return makeTokenAndAdvance(RELOP, NumericOp::OP_GE, 2);
320             return makeTokenAndAdvance(RELOP, NumericOp::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(ERROR);
331             return Token(VARIABLEREFERENCE, name);
332         }
333     }
334
335     String name;
336     if (!lexNCName(name))
337         return Token(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(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(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         case MULOP:
432         case RELOP:
433             yylval->numop = tok.numop;
434             break;
435         case EQOP:
436             yylval->eqop = tok.eqop;
437             break;
438         case NODETYPE:
439         case PI:
440         case FUNCTIONNAME:
441         case LITERAL:
442         case VARIABLEREFERENCE:
443         case NUMBER:
444         case NAMETEST:
445             yylval->str = new String(tok.str);
446             registerString(yylval->str);
447             break;
448     }
449
450     return tok.type;
451 }
452
453 Expression* Parser::parseStatement(const String& statement, PassRefPtr<XPathNSResolver> resolver, ExceptionCode& ec)
454 {
455     reset(statement);
456
457     m_resolver = resolver;
458     
459     Parser* oldParser = currentParser;
460     currentParser = this;
461     int parseError = xpathyyparse(this);
462     currentParser = oldParser;
463
464     if (parseError) {
465         deleteAllValues(m_parseNodes);
466         m_parseNodes.clear();
467
468         HashSet<Vector<Predicate*>*>::iterator pend = m_predicateVectors.end();
469         for (HashSet<Vector<Predicate*>*>::iterator it = m_predicateVectors.begin(); it != pend; ++it) {
470             deleteAllValues(**it);
471             delete *it;
472         }
473         m_predicateVectors.clear();
474
475         HashSet<Vector<Expression*>*>::iterator eend = m_expressionVectors.end();
476         for (HashSet<Vector<Expression*>*>::iterator it = m_expressionVectors.begin(); it != eend; ++it) {
477             deleteAllValues(**it);
478             delete *it;
479         }
480         m_expressionVectors.clear();
481
482         deleteAllValues(m_strings);
483         m_strings.clear();
484
485         m_topExpr = 0;
486
487         if (m_gotNamespaceError)
488             ec = NAMESPACE_ERR;
489         else
490             ec = INVALID_EXPRESSION_ERR;
491         return 0;
492     }
493
494     ASSERT(m_parseNodes.size() == 1);
495     ASSERT(*m_parseNodes.begin() == m_topExpr);
496     ASSERT(m_expressionVectors.size() == 0);
497     ASSERT(m_predicateVectors.size() == 0);
498     ASSERT(m_strings.size() == 0);
499
500     m_parseNodes.clear();
501     Expression* result = m_topExpr;
502     m_topExpr = 0;
503
504     return result;
505 }
506
507 void Parser::registerParseNode(ParseNode* node)
508 {
509     if (node == 0)
510         return;
511     
512     ASSERT(!m_parseNodes.contains(node));
513     
514     m_parseNodes.add(node);
515 }
516
517 void Parser::unregisterParseNode(ParseNode* node)
518 {
519     if (node == 0)
520         return;
521     
522     ASSERT(m_parseNodes.contains(node));
523
524     m_parseNodes.remove(node);
525 }
526
527 void Parser::registerPredicateVector(Vector<Predicate*>* vector)
528 {
529     if (vector == 0)
530         return;
531
532     ASSERT(!m_predicateVectors.contains(vector));
533     
534     m_predicateVectors.add(vector);
535 }
536
537 void Parser::deletePredicateVector(Vector<Predicate*>* vector)
538 {
539     if (vector == 0)
540         return;
541
542     ASSERT(m_predicateVectors.contains(vector));
543     
544     m_predicateVectors.remove(vector);
545     delete vector;
546 }
547
548
549 void Parser::registerExpressionVector(Vector<Expression*>* vector)
550 {
551     if (vector == 0)
552         return;
553
554     ASSERT(!m_expressionVectors.contains(vector));
555     
556     m_expressionVectors.add(vector);    
557 }
558
559 void Parser::deleteExpressionVector(Vector<Expression*>* vector)
560 {
561     if (vector == 0)
562         return;
563
564     ASSERT(m_expressionVectors.contains(vector));
565     
566     m_expressionVectors.remove(vector);
567     delete vector;
568 }
569
570 void Parser::registerString(String* s)
571 {
572     if (s == 0)
573         return;
574     
575     ASSERT(!m_strings.contains(s));
576     
577     m_strings.add(s);        
578 }
579
580 void Parser::deleteString(String* s)
581 {
582     if (s == 0)
583         return;
584     
585     ASSERT(m_strings.contains(s));
586     
587     m_strings.remove(s);
588     delete s;
589 }
590
591 }
592 }
593
594 #endif // XPATH_SUPPORT