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