Always enable ENABLE(XPATH)
[WebKit-https.git] / Source / WebCore / xml / XPathFunctions.cpp
1 /*
2  * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
3  * Copyright (C) 2006, 2009 Apple Inc.
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 "XPathFunctions.h"
30
31 #include "Element.h"
32 #include "NamedNodeMap.h"
33 #include "ProcessingInstruction.h"
34 #include "TreeScope.h"
35 #include "XMLNames.h"
36 #include "XPathUtil.h"
37 #include "XPathValue.h"
38 #include <wtf/MathExtras.h>
39 #include <wtf/text/StringBuilder.h>
40
41 namespace WebCore {
42 namespace XPath {
43
44 static inline bool isWhitespace(UChar c)
45 {
46     return c == ' ' || c == '\n' || c == '\r' || c == '\t';
47 }
48
49
50 #define DEFINE_FUNCTION_CREATOR(Class) static Function* create##Class() { return new Class; }
51
52 class Interval {
53 public:
54     static const int Inf = -1;
55
56     Interval();
57     Interval(int value);
58     Interval(int min, int max);
59
60     bool contains(int value) const;
61
62 private:
63     int m_min;
64     int m_max;
65 };
66
67 struct FunctionRec {
68     typedef Function *(*FactoryFn)();
69     FactoryFn factoryFn;
70     Interval args;
71 };
72
73 static HashMap<String, FunctionRec>* functionMap;
74
75 class FunLast : public Function {
76     virtual Value evaluate() const;
77     virtual Value::Type resultType() const { return Value::NumberValue; }
78 public:
79     FunLast() { setIsContextSizeSensitive(true); }
80 };
81
82 class FunPosition : public Function {
83     virtual Value evaluate() const;
84     virtual Value::Type resultType() const { return Value::NumberValue; }
85 public:
86     FunPosition() { setIsContextPositionSensitive(true); }
87 };
88
89 class FunCount : public Function {
90     virtual Value evaluate() const;
91     virtual Value::Type resultType() const { return Value::NumberValue; }
92 };
93
94 class FunId : public Function {
95     virtual Value evaluate() const;
96     virtual Value::Type resultType() const { return Value::NodeSetValue; }
97 };
98
99 class FunLocalName : public Function {
100     virtual Value evaluate() const;
101     virtual Value::Type resultType() const { return Value::StringValue; }
102 public:
103     FunLocalName() { setIsContextNodeSensitive(true); } // local-name() with no arguments uses context node. 
104 };
105
106 class FunNamespaceURI : public Function {
107     virtual Value evaluate() const;
108     virtual Value::Type resultType() const { return Value::StringValue; }
109 public:
110     FunNamespaceURI() { setIsContextNodeSensitive(true); } // namespace-uri() with no arguments uses context node. 
111 };
112
113 class FunName : public Function {
114     virtual Value evaluate() const;
115     virtual Value::Type resultType() const { return Value::StringValue; }
116 public:
117     FunName() { setIsContextNodeSensitive(true); } // name() with no arguments uses context node. 
118 };
119
120 class FunString : public Function {
121     virtual Value evaluate() const;
122     virtual Value::Type resultType() const { return Value::StringValue; }
123 public:
124     FunString() { setIsContextNodeSensitive(true); } // string() with no arguments uses context node. 
125 };
126
127 class FunConcat : public Function {
128     virtual Value evaluate() const;
129     virtual Value::Type resultType() const { return Value::StringValue; }
130 };
131
132 class FunStartsWith : public Function {
133     virtual Value evaluate() const;
134     virtual Value::Type resultType() const { return Value::BooleanValue; }
135 };
136
137 class FunContains : public Function {
138     virtual Value evaluate() const;
139     virtual Value::Type resultType() const { return Value::BooleanValue; }
140 };
141
142 class FunSubstringBefore : public Function {
143     virtual Value evaluate() const;
144     virtual Value::Type resultType() const { return Value::StringValue; }
145 };
146
147 class FunSubstringAfter : public Function {
148     virtual Value evaluate() const;
149     virtual Value::Type resultType() const { return Value::StringValue; }
150 };
151
152 class FunSubstring : public Function {
153     virtual Value evaluate() const;
154     virtual Value::Type resultType() const { return Value::StringValue; }
155 };
156
157 class FunStringLength : public Function {
158     virtual Value evaluate() const;
159     virtual Value::Type resultType() const { return Value::NumberValue; }
160 public:
161     FunStringLength() { setIsContextNodeSensitive(true); } // string-length() with no arguments uses context node. 
162 };
163
164 class FunNormalizeSpace : public Function {
165     virtual Value evaluate() const;
166     virtual Value::Type resultType() const { return Value::StringValue; }
167 public:
168     FunNormalizeSpace() { setIsContextNodeSensitive(true); } // normalize-space() with no arguments uses context node. 
169 };
170
171 class FunTranslate : public Function {
172     virtual Value evaluate() const;
173     virtual Value::Type resultType() const { return Value::StringValue; }
174 };
175
176 class FunBoolean : public Function {
177     virtual Value evaluate() const;
178     virtual Value::Type resultType() const { return Value::BooleanValue; }
179 };
180
181 class FunNot : public Function {
182     virtual Value evaluate() const;
183     virtual Value::Type resultType() const { return Value::BooleanValue; }
184 };
185
186 class FunTrue : public Function {
187     virtual Value evaluate() const;
188     virtual Value::Type resultType() const { return Value::BooleanValue; }
189 };
190
191 class FunFalse : public Function {
192     virtual Value evaluate() const;
193     virtual Value::Type resultType() const { return Value::BooleanValue; }
194 };
195
196 class FunLang : public Function {
197     virtual Value evaluate() const;
198     virtual Value::Type resultType() const { return Value::BooleanValue; }
199 public:
200     FunLang() { setIsContextNodeSensitive(true); } // lang() always works on context node. 
201 };
202
203 class FunNumber : public Function {
204     virtual Value evaluate() const;
205     virtual Value::Type resultType() const { return Value::NumberValue; }
206 public:
207     FunNumber() { setIsContextNodeSensitive(true); } // number() with no arguments uses context node. 
208 };
209
210 class FunSum : public Function {
211     virtual Value evaluate() const;
212     virtual Value::Type resultType() const { return Value::NumberValue; }
213 };
214
215 class FunFloor : public Function {
216     virtual Value evaluate() const;
217     virtual Value::Type resultType() const { return Value::NumberValue; }
218 };
219
220 class FunCeiling : public Function {
221     virtual Value evaluate() const;
222     virtual Value::Type resultType() const { return Value::NumberValue; }
223 };
224
225 class FunRound : public Function {
226     virtual Value evaluate() const;
227     virtual Value::Type resultType() const { return Value::NumberValue; }
228 public:
229     static double round(double);
230 };
231
232 DEFINE_FUNCTION_CREATOR(FunLast)
233 DEFINE_FUNCTION_CREATOR(FunPosition)
234 DEFINE_FUNCTION_CREATOR(FunCount)
235 DEFINE_FUNCTION_CREATOR(FunId)
236 DEFINE_FUNCTION_CREATOR(FunLocalName)
237 DEFINE_FUNCTION_CREATOR(FunNamespaceURI)
238 DEFINE_FUNCTION_CREATOR(FunName)
239
240 DEFINE_FUNCTION_CREATOR(FunString)
241 DEFINE_FUNCTION_CREATOR(FunConcat)
242 DEFINE_FUNCTION_CREATOR(FunStartsWith)
243 DEFINE_FUNCTION_CREATOR(FunContains)
244 DEFINE_FUNCTION_CREATOR(FunSubstringBefore)
245 DEFINE_FUNCTION_CREATOR(FunSubstringAfter)
246 DEFINE_FUNCTION_CREATOR(FunSubstring)
247 DEFINE_FUNCTION_CREATOR(FunStringLength)
248 DEFINE_FUNCTION_CREATOR(FunNormalizeSpace)
249 DEFINE_FUNCTION_CREATOR(FunTranslate)
250
251 DEFINE_FUNCTION_CREATOR(FunBoolean)
252 DEFINE_FUNCTION_CREATOR(FunNot)
253 DEFINE_FUNCTION_CREATOR(FunTrue)
254 DEFINE_FUNCTION_CREATOR(FunFalse)
255 DEFINE_FUNCTION_CREATOR(FunLang)
256
257 DEFINE_FUNCTION_CREATOR(FunNumber)
258 DEFINE_FUNCTION_CREATOR(FunSum)
259 DEFINE_FUNCTION_CREATOR(FunFloor)
260 DEFINE_FUNCTION_CREATOR(FunCeiling)
261 DEFINE_FUNCTION_CREATOR(FunRound)
262
263 #undef DEFINE_FUNCTION_CREATOR
264
265 inline Interval::Interval()
266     : m_min(Inf), m_max(Inf)
267 {
268 }
269
270 inline Interval::Interval(int value)
271     : m_min(value), m_max(value)
272 {
273 }
274
275 inline Interval::Interval(int min, int max)
276     : m_min(min), m_max(max)
277 {
278 }
279
280 inline bool Interval::contains(int value) const
281 {
282     if (m_min == Inf && m_max == Inf)
283         return true;
284
285     if (m_min == Inf)
286         return value <= m_max;
287
288     if (m_max == Inf)
289         return value >= m_min;
290
291     return value >= m_min && value <= m_max;
292 }
293
294 void Function::setArguments(const Vector<Expression*>& args)
295 {
296     ASSERT(!subExprCount());
297
298     // Some functions use context node as implicit argument, so when explicit arguments are added, they may no longer be context node sensitive.
299     if (m_name != "lang" && !args.isEmpty())
300         setIsContextNodeSensitive(false);
301
302     Vector<Expression*>::const_iterator end = args.end();
303     for (Vector<Expression*>::const_iterator it = args.begin(); it != end; it++)
304         addSubExpression(*it);
305 }
306
307 Value FunLast::evaluate() const
308 {
309     return Expression::evaluationContext().size;
310 }
311
312 Value FunPosition::evaluate() const
313 {
314     return Expression::evaluationContext().position;
315 }
316
317 Value FunId::evaluate() const
318 {
319     Value a = arg(0)->evaluate();
320     StringBuilder idList; // A whitespace-separated list of IDs
321
322     if (a.isNodeSet()) {
323         const NodeSet& nodes = a.toNodeSet();
324         for (size_t i = 0; i < nodes.size(); ++i) {
325             String str = stringValue(nodes[i]);
326             idList.append(str);
327             idList.append(' ');
328         }
329     } else {
330         String str = a.toString();
331         idList.append(str);
332     }
333     
334     TreeScope* contextScope = evaluationContext().node->treeScope();
335     NodeSet result;
336     HashSet<Node*> resultSet;
337
338     unsigned startPos = 0;
339     unsigned length = idList.length();
340     while (true) {
341         while (startPos < length && isWhitespace(idList[startPos]))
342             ++startPos;
343         
344         if (startPos == length)
345             break;
346
347         size_t endPos = startPos;
348         while (endPos < length && !isWhitespace(idList[endPos]))
349             ++endPos;
350
351         // If there are several nodes with the same id, id() should return the first one.
352         // In WebKit, getElementById behaves so, too, although its behavior in this case is formally undefined.
353         Node* node = contextScope->getElementById(String(idList.characters() + startPos, endPos - startPos));
354         if (node && resultSet.add(node).second)
355             result.append(node);
356         
357         startPos = endPos;
358     }
359     
360     result.markSorted(false);
361     
362     return Value(result, Value::adopt);
363 }
364
365 static inline String expandedNameLocalPart(Node* node)
366 {
367     // The local part of an XPath expanded-name matches DOM local name for most node types, except for namespace nodes and processing instruction nodes.
368     ASSERT(node->nodeType() != Node::XPATH_NAMESPACE_NODE); // Not supported yet.
369     if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE)
370         return static_cast<ProcessingInstruction*>(node)->target();
371     return node->localName().string();
372 }
373
374 static inline String expandedName(Node* node)
375 {
376     const AtomicString& prefix = node->prefix();
377     return prefix.isEmpty() ? expandedNameLocalPart(node) : prefix + ":" + expandedNameLocalPart(node);
378 }
379
380 Value FunLocalName::evaluate() const
381 {
382     if (argCount() > 0) {
383         Value a = arg(0)->evaluate();
384         if (!a.isNodeSet())
385             return "";
386
387         Node* node = a.toNodeSet().firstNode();
388         return node ? expandedNameLocalPart(node) : "";
389     }
390
391     return expandedNameLocalPart(evaluationContext().node.get());
392 }
393
394 Value FunNamespaceURI::evaluate() const
395 {
396     if (argCount() > 0) {
397         Value a = arg(0)->evaluate();
398         if (!a.isNodeSet())
399             return "";
400
401         Node* node = a.toNodeSet().firstNode();
402         return node ? node->namespaceURI().string() : "";
403     }
404
405     return evaluationContext().node->namespaceURI().string();
406 }
407
408 Value FunName::evaluate() const
409 {
410     if (argCount() > 0) {
411         Value a = arg(0)->evaluate();
412         if (!a.isNodeSet())
413             return "";
414
415         Node* node = a.toNodeSet().firstNode();
416         return node ? expandedName(node) : "";
417     }
418
419     return expandedName(evaluationContext().node.get());
420 }
421
422 Value FunCount::evaluate() const
423 {
424     Value a = arg(0)->evaluate();
425     
426     return double(a.toNodeSet().size());
427 }
428
429 Value FunString::evaluate() const
430 {
431     if (!argCount())
432         return Value(Expression::evaluationContext().node.get()).toString();
433     return arg(0)->evaluate().toString();
434 }
435
436 Value FunConcat::evaluate() const
437 {
438     StringBuilder result;
439     result.reserveCapacity(1024);
440
441     unsigned count = argCount();
442     for (unsigned i = 0; i < count; ++i) {
443         String str(arg(i)->evaluate().toString());
444         result.append(str);
445     }
446
447     return result.toString();
448 }
449
450 Value FunStartsWith::evaluate() const
451 {
452     String s1 = arg(0)->evaluate().toString();
453     String s2 = arg(1)->evaluate().toString();
454
455     if (s2.isEmpty())
456         return true;
457
458     return s1.startsWith(s2);
459 }
460
461 Value FunContains::evaluate() const
462 {
463     String s1 = arg(0)->evaluate().toString();
464     String s2 = arg(1)->evaluate().toString();
465
466     if (s2.isEmpty()) 
467         return true;
468
469     return s1.contains(s2) != 0;
470 }
471
472 Value FunSubstringBefore::evaluate() const
473 {
474     String s1 = arg(0)->evaluate().toString();
475     String s2 = arg(1)->evaluate().toString();
476
477     if (s2.isEmpty())
478         return "";
479
480     size_t i = s1.find(s2);
481
482     if (i == notFound)
483         return "";
484
485     return s1.left(i);
486 }
487
488 Value FunSubstringAfter::evaluate() const
489 {
490     String s1 = arg(0)->evaluate().toString();
491     String s2 = arg(1)->evaluate().toString();
492
493     size_t i = s1.find(s2);
494     if (i == notFound)
495         return "";
496
497     return s1.substring(i + s2.length());
498 }
499
500 Value FunSubstring::evaluate() const
501 {
502     String s = arg(0)->evaluate().toString();
503     double doublePos = arg(1)->evaluate().toNumber();
504     if (isnan(doublePos))
505         return "";
506     long pos = static_cast<long>(FunRound::round(doublePos));
507     bool haveLength = argCount() == 3;
508     long len = -1;
509     if (haveLength) {
510         double doubleLen = arg(2)->evaluate().toNumber();
511         if (isnan(doubleLen))
512             return "";
513         len = static_cast<long>(FunRound::round(doubleLen));
514     }
515
516     if (pos > long(s.length())) 
517         return "";
518
519     if (pos < 1) {
520         if (haveLength) {
521             len -= 1 - pos;
522             if (len < 1)
523                 return "";
524         }
525         pos = 1;
526     }
527
528     return s.substring(pos - 1, len);
529 }
530
531 Value FunStringLength::evaluate() const
532 {
533     if (!argCount())
534         return Value(Expression::evaluationContext().node.get()).toString().length();
535     return arg(0)->evaluate().toString().length();
536 }
537
538 Value FunNormalizeSpace::evaluate() const
539 {
540     if (!argCount()) {
541         String s = Value(Expression::evaluationContext().node.get()).toString();
542         return s.simplifyWhiteSpace();
543     }
544
545     String s = arg(0)->evaluate().toString();
546     return s.simplifyWhiteSpace();
547 }
548
549 Value FunTranslate::evaluate() const
550 {
551     String s1 = arg(0)->evaluate().toString();
552     String s2 = arg(1)->evaluate().toString();
553     String s3 = arg(2)->evaluate().toString();
554     String newString;
555
556     // FIXME: Building a String a character at a time is quite slow.
557     for (unsigned i1 = 0; i1 < s1.length(); ++i1) {
558         UChar ch = s1[i1];
559         size_t i2 = s2.find(ch);
560         
561         if (i2 == notFound)
562             newString += String(&ch, 1);
563         else if (i2 < s3.length()) {
564             UChar c2 = s3[i2];
565             newString += String(&c2, 1);
566         }
567     }
568
569     return newString;
570 }
571
572 Value FunBoolean::evaluate() const
573 {
574     return arg(0)->evaluate().toBoolean();
575 }
576
577 Value FunNot::evaluate() const
578 {
579     return !arg(0)->evaluate().toBoolean();
580 }
581
582 Value FunTrue::evaluate() const
583 {
584     return true;
585 }
586
587 Value FunLang::evaluate() const
588 {
589     String lang = arg(0)->evaluate().toString();
590
591     Attribute* languageAttribute = 0;
592     Node* node = evaluationContext().node.get();
593     while (node) {
594         NamedNodeMap* attrs = node->attributes();
595         if (attrs)
596             languageAttribute = attrs->getAttributeItem(XMLNames::langAttr);
597         if (languageAttribute)
598             break;
599         node = node->parentNode();
600     }
601
602     if (!languageAttribute)
603         return false;
604
605     String langValue = languageAttribute->value();
606     while (true) {
607         if (equalIgnoringCase(langValue, lang))
608             return true;
609
610         // Remove suffixes one by one.
611         size_t index = langValue.reverseFind('-');
612         if (index == notFound)
613             break;
614         langValue = langValue.left(index);
615     }
616
617     return false;
618 }
619
620 Value FunFalse::evaluate() const
621 {
622     return false;
623 }
624
625 Value FunNumber::evaluate() const
626 {
627     if (!argCount())
628         return Value(Expression::evaluationContext().node.get()).toNumber();
629     return arg(0)->evaluate().toNumber();
630 }
631
632 Value FunSum::evaluate() const
633 {
634     Value a = arg(0)->evaluate();
635     if (!a.isNodeSet())
636         return 0.0;
637
638     double sum = 0.0;
639     const NodeSet& nodes = a.toNodeSet();
640     // To be really compliant, we should sort the node-set, as floating point addition is not associative.
641     // However, this is unlikely to ever become a practical issue, and sorting is slow.
642
643     for (unsigned i = 0; i < nodes.size(); i++)
644         sum += Value(stringValue(nodes[i])).toNumber();
645     
646     return sum;
647 }
648
649 Value FunFloor::evaluate() const
650 {
651     return floor(arg(0)->evaluate().toNumber());
652 }
653
654 Value FunCeiling::evaluate() const
655 {
656     return ceil(arg(0)->evaluate().toNumber());
657 }
658
659 double FunRound::round(double val)
660 {
661     if (!isnan(val) && !isinf(val)) {
662         if (signbit(val) && val >= -0.5)
663             val *= 0; // negative zero
664         else
665             val = floor(val + 0.5);
666     }
667     return val;
668 }
669
670 Value FunRound::evaluate() const
671 {
672     return round(arg(0)->evaluate().toNumber());
673 }
674
675 struct FunctionMapping {
676     const char* name;
677     FunctionRec function;
678 };
679
680 static void createFunctionMap()
681 {
682     static const FunctionMapping functions[] = {
683         { "boolean", { &createFunBoolean, 1 } },
684         { "ceiling", { &createFunCeiling, 1 } },
685         { "concat", { &createFunConcat, Interval(2, Interval::Inf) } },
686         { "contains", { &createFunContains, 2 } },
687         { "count", { &createFunCount, 1 } },
688         { "false", { &createFunFalse, 0 } },
689         { "floor", { &createFunFloor, 1 } },
690         { "id", { &createFunId, 1 } },
691         { "lang", { &createFunLang, 1 } },
692         { "last", { &createFunLast, 0 } },
693         { "local-name", { &createFunLocalName, Interval(0, 1) } },
694         { "name", { &createFunName, Interval(0, 1) } },
695         { "namespace-uri", { &createFunNamespaceURI, Interval(0, 1) } },
696         { "normalize-space", { &createFunNormalizeSpace, Interval(0, 1) } },
697         { "not", { &createFunNot, 1 } },
698         { "number", { &createFunNumber, Interval(0, 1) } },
699         { "position", { &createFunPosition, 0 } },
700         { "round", { &createFunRound, 1 } },
701         { "starts-with", { &createFunStartsWith, 2 } },
702         { "string", { &createFunString, Interval(0, 1) } },
703         { "string-length", { &createFunStringLength, Interval(0, 1) } },
704         { "substring", { &createFunSubstring, Interval(2, 3) } },
705         { "substring-after", { &createFunSubstringAfter, 2 } },
706         { "substring-before", { &createFunSubstringBefore, 2 } },
707         { "sum", { &createFunSum, 1 } },
708         { "translate", { &createFunTranslate, 3 } },
709         { "true", { &createFunTrue, 0 } },
710     };
711
712     functionMap = new HashMap<String, FunctionRec>;
713     for (size_t i = 0; i < WTF_ARRAY_LENGTH(functions); ++i)
714         functionMap->set(functions[i].name, functions[i].function);
715 }
716
717 Function* createFunction(const String& name, const Vector<Expression*>& args)
718 {
719     if (!functionMap)
720         createFunctionMap();
721
722     HashMap<String, FunctionRec>::iterator functionMapIter = functionMap->find(name);
723     FunctionRec* functionRec = 0;
724
725     if (functionMapIter == functionMap->end() || !(functionRec = &functionMapIter->second)->args.contains(args.size()))
726         return 0;
727
728     Function* function = functionRec->factoryFn();
729     function->setArguments(args);
730     function->setName(name);
731     return function;
732 }
733
734 }
735 }