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