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