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
40namespace WebCore {
41namespace XPath {
42
43static 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
50class Interval {
51public:
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
60private:
61 int m_min;
62 int m_max;
63};
64
65class FunLast final : public Function {
66 Value evaluate() const override;
67 Value::Type resultType() const override { return Value::NumberValue; }
68public:
69 FunLast() { setIsContextSizeSensitive(true); }
70};
71
72class FunPosition final : public Function {
73 Value evaluate() const override;
74 Value::Type resultType() const override { return Value::NumberValue; }
75public:
76 FunPosition() { setIsContextPositionSensitive(true); }
77};
78
79class FunCount final : public Function {
80 Value evaluate() const override;
81 Value::Type resultType() const override { return Value::NumberValue; }
82};
83
84class FunId final : public Function {
85 Value evaluate() const override;
86 Value::Type resultType() const override { return Value::NodeSetValue; }
87};
88
89class FunLocalName final : public Function {
90 Value evaluate() const override;
91 Value::Type resultType() const override { return Value::StringValue; }
92public:
93 FunLocalName() { setIsContextNodeSensitive(true); } // local-name() with no arguments uses context node.
94};
95
96class FunNamespaceURI final : public Function {
97 Value evaluate() const override;
98 Value::Type resultType() const override { return Value::StringValue; }
99public:
100 FunNamespaceURI() { setIsContextNodeSensitive(true); } // namespace-uri() with no arguments uses context node.
101};
102
103class FunName final : public Function {
104 Value evaluate() const override;
105 Value::Type resultType() const override { return Value::StringValue; }
106public:
107 FunName() { setIsContextNodeSensitive(true); } // name() with no arguments uses context node.
108};
109
110class FunString final : public Function {
111 Value evaluate() const override;
112 Value::Type resultType() const override { return Value::StringValue; }
113public:
114 FunString() { setIsContextNodeSensitive(true); } // string() with no arguments uses context node.
115};
116
117class FunConcat final : public Function {
118 Value evaluate() const override;
119 Value::Type resultType() const override { return Value::StringValue; }
120};
121
122class FunStartsWith final : public Function {
123 Value evaluate() const override;
124 Value::Type resultType() const override { return Value::BooleanValue; }
125};
126
127class FunContains final : public Function {
128 Value evaluate() const override;
129 Value::Type resultType() const override { return Value::BooleanValue; }
130};
131
132class FunSubstringBefore final : public Function {
133 Value evaluate() const override;
134 Value::Type resultType() const override { return Value::StringValue; }
135};
136
137class FunSubstringAfter final : public Function {
138 Value evaluate() const override;
139 Value::Type resultType() const override { return Value::StringValue; }
140};
141
142class FunSubstring final : public Function {
143 Value evaluate() const override;
144 Value::Type resultType() const override { return Value::StringValue; }
145};
146
147class FunStringLength final : public Function {
148 Value evaluate() const override;
149 Value::Type resultType() const override { return Value::NumberValue; }
150public:
151 FunStringLength() { setIsContextNodeSensitive(true); } // string-length() with no arguments uses context node.
152};
153
154class FunNormalizeSpace final : public Function {
155 Value evaluate() const override;
156 Value::Type resultType() const override { return Value::StringValue; }
157public:
158 FunNormalizeSpace() { setIsContextNodeSensitive(true); } // normalize-space() with no arguments uses context node.
159};
160
161class FunTranslate final : public Function {
162 Value evaluate() const override;
163 Value::Type resultType() const override { return Value::StringValue; }
164};
165
166class FunBoolean final : public Function {
167 Value evaluate() const override;
168 Value::Type resultType() const override { return Value::BooleanValue; }
169};
170
171class FunNot : public Function {
172 Value evaluate() const override;
173 Value::Type resultType() const override { return Value::BooleanValue; }
174};
175
176class FunTrue final : public Function {
177 Value evaluate() const override;
178 Value::Type resultType() const override { return Value::BooleanValue; }
179};
180
181class FunFalse final : public Function {
182 Value evaluate() const override;
183 Value::Type resultType() const override { return Value::BooleanValue; }
184};
185
186class FunLang final : public Function {
187 Value evaluate() const override;
188 Value::Type resultType() const override { return Value::BooleanValue; }
189public:
190 FunLang() { setIsContextNodeSensitive(true); } // lang() always works on context node.
191};
192
193class FunNumber final : public Function {
194 Value evaluate() const override;
195 Value::Type resultType() const override { return Value::NumberValue; }
196public:
197 FunNumber() { setIsContextNodeSensitive(true); } // number() with no arguments uses context node.
198};
199
200class FunSum final : public Function {
201 Value evaluate() const override;
202 Value::Type resultType() const override { return Value::NumberValue; }
203};
204
205class FunFloor final : public Function {
206 Value evaluate() const override;
207 Value::Type resultType() const override { return Value::NumberValue; }
208};
209
210class FunCeiling final : public Function {
211 Value evaluate() const override;
212 Value::Type resultType() const override { return Value::NumberValue; }
213};
214
215class FunRound final : public Function {
216 Value evaluate() const override;
217 Value::Type resultType() const override { return Value::NumberValue; }
218public:
219 static double round(double);
220};
221
222DEFINE_FUNCTION_CREATOR(Last)
223DEFINE_FUNCTION_CREATOR(Position)
224DEFINE_FUNCTION_CREATOR(Count)
225DEFINE_FUNCTION_CREATOR(Id)
226DEFINE_FUNCTION_CREATOR(LocalName)
227DEFINE_FUNCTION_CREATOR(NamespaceURI)
228DEFINE_FUNCTION_CREATOR(Name)
229
230DEFINE_FUNCTION_CREATOR(String)
231DEFINE_FUNCTION_CREATOR(Concat)
232DEFINE_FUNCTION_CREATOR(StartsWith)
233DEFINE_FUNCTION_CREATOR(Contains)
234DEFINE_FUNCTION_CREATOR(SubstringBefore)
235DEFINE_FUNCTION_CREATOR(SubstringAfter)
236DEFINE_FUNCTION_CREATOR(Substring)
237DEFINE_FUNCTION_CREATOR(StringLength)
238DEFINE_FUNCTION_CREATOR(NormalizeSpace)
239DEFINE_FUNCTION_CREATOR(Translate)
240
241DEFINE_FUNCTION_CREATOR(Boolean)
242DEFINE_FUNCTION_CREATOR(Not)
243DEFINE_FUNCTION_CREATOR(True)
244DEFINE_FUNCTION_CREATOR(False)
245DEFINE_FUNCTION_CREATOR(Lang)
246
247DEFINE_FUNCTION_CREATOR(Number)
248DEFINE_FUNCTION_CREATOR(Sum)
249DEFINE_FUNCTION_CREATOR(Floor)
250DEFINE_FUNCTION_CREATOR(Ceiling)
251DEFINE_FUNCTION_CREATOR(Round)
252
253#undef DEFINE_FUNCTION_CREATOR
254
255inline Interval::Interval()
256 : m_min(Inf), m_max(Inf)
257{
258}
259
260inline Interval::Interval(int value)
261 : m_min(value), m_max(value)
262{
263}
264
265inline Interval::Interval(int min, int max)
266 : m_min(min), m_max(max)
267{
268}
269
270inline 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
284void 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
297Value FunLast::evaluate() const
298{
299 return Expression::evaluationContext().size;
300}
301
302Value FunPosition::evaluate() const
303{
304 return Expression::evaluationContext().position;
305}
306
307static AtomicString 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 AtomicString(builder.characters8() + start, length);
313 return AtomicString(builder.characters16() + start, length);
314}
315
316Value 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
361static inline String expandedNameLocalPart(Node* node)
362{
363 if (is<ProcessingInstruction>(*node))
364 return downcast<ProcessingInstruction>(*node).target();
365 return node->localName().string();
366}
367
368static inline String expandedName(Node* node)
369{
370 const AtomicString& prefix = node->prefix();
371 return prefix.isEmpty() ? expandedNameLocalPart(node) : prefix + ":" + expandedNameLocalPart(node);
372}
373
374Value 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
388Value 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
402Value 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
416Value FunCount::evaluate() const
417{
418 Value a = argument(0).evaluate();
419
420 return double(a.toNodeSet().size());
421}
422
423Value FunString::evaluate() const
424{
425 if (!argumentCount())
426 return Value(Expression::evaluationContext().node.get()).toString();
427 return argument(0).evaluate().toString();
428}
429
430Value 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
443Value 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
454Value 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
465Value 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
481Value 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
493Value 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
524Value 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
531Value 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
542Value 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
562Value FunBoolean::evaluate() const
563{
564 return argument(0).evaluate().toBoolean();
565}
566
567Value FunNot::evaluate() const
568{
569 return !argument(0).evaluate().toBoolean();
570}
571
572Value FunTrue::evaluate() const
573{
574 return true;
575}
576
577Value 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
612Value FunFalse::evaluate() const
613{
614 return false;
615}
616
617Value FunNumber::evaluate() const
618{
619 if (!argumentCount())
620 return Value(Expression::evaluationContext().node.get()).toNumber();
621 return argument(0).evaluate().toNumber();
622}
623
624Value 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
641Value FunFloor::evaluate() const
642{
643 return floor(argument(0).evaluate().toNumber());
644}
645
646Value FunCeiling::evaluate() const
647{
648 return ceil(argument(0).evaluate().toNumber());
649}
650
651double 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
662Value FunRound::evaluate() const
663{
664 return round(argument(0).evaluate().toNumber());
665}
666
667struct FunctionMapValue {
668 std::unique_ptr<Function> (*creationFunction)();
669 Interval argumentCountInterval;
670};
671
672static 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
715std::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
729std::unique_ptr<Function> Function::create(const String& name)
730{
731 return create(name, 0);
732}
733
734std::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}
744