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