[WTF] Clean up StringStatics.cpp by using LazyNeverDestroyed<> for Atoms
[WebKit-https.git] / Source / WebCore / svg / animation / SVGSMILElement.cpp
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "SVGSMILElement.h"
28
29 #include "CSSPropertyNames.h"
30 #include "Document.h"
31 #include "Event.h"
32 #include "EventListener.h"
33 #include "EventNames.h"
34 #include "EventSender.h"
35 #include "FloatConversion.h"
36 #include "FrameView.h"
37 #include "SMILTimeContainer.h"
38 #include "SVGDocumentExtensions.h"
39 #include "SVGNames.h"
40 #include "SVGParserUtilities.h"
41 #include "SVGSVGElement.h"
42 #include "SVGURIReference.h"
43 #include "XLinkNames.h"
44 #include <wtf/MathExtras.h>
45 #include <wtf/StdLibExtras.h>
46 #include <wtf/Vector.h>
47
48 namespace WebCore {
49
50 static SMILEventSender& smilBeginEventSender()
51 {
52     static NeverDestroyed<SMILEventSender> sender(eventNames().beginEventEvent);
53     return sender;
54 }
55
56 static SMILEventSender& smilEndEventSender()
57 {
58     static NeverDestroyed<SMILEventSender> sender(eventNames().endEventEvent);
59     return sender;
60 }
61
62 // This is used for duration type time values that can't be negative.
63 static const double invalidCachedTime = -1.;
64     
65 class ConditionEventListener final : public EventListener {
66 public:
67     static Ref<ConditionEventListener> create(SVGSMILElement* animation, SVGSMILElement::Condition* condition)
68     {
69         return adoptRef(*new ConditionEventListener(animation, condition));
70     }
71
72     static const ConditionEventListener* cast(const EventListener* listener)
73     {
74         return listener->type() == ConditionEventListenerType
75             ? static_cast<const ConditionEventListener*>(listener)
76             : nullptr;
77     }
78
79     bool operator==(const EventListener& other) const final;
80     
81     void disconnectAnimation()
82     {
83         m_animation = nullptr;
84     }
85
86 private:
87     ConditionEventListener(SVGSMILElement* animation, SVGSMILElement::Condition* condition) 
88         : EventListener(ConditionEventListenerType)
89         , m_animation(animation)
90         , m_condition(condition) 
91     {
92     }
93
94     void handleEvent(ScriptExecutionContext*, Event*) final;
95
96     SVGSMILElement* m_animation;
97     SVGSMILElement::Condition* m_condition;
98 };
99
100 bool ConditionEventListener::operator==(const EventListener& listener) const
101 {
102     if (const ConditionEventListener* conditionEventListener = ConditionEventListener::cast(&listener))
103         return m_animation == conditionEventListener->m_animation && m_condition == conditionEventListener->m_condition;
104     return false;
105 }
106
107 void ConditionEventListener::handleEvent(ScriptExecutionContext*, Event* event) 
108 {
109     if (!m_animation)
110         return;
111     m_animation->handleConditionEvent(event, m_condition);
112 }
113
114 SVGSMILElement::Condition::Condition(Type type, BeginOrEnd beginOrEnd, const String& baseID, const String& name, SMILTime offset, int repeats)
115     : m_type(type)
116     , m_beginOrEnd(beginOrEnd)
117     , m_baseID(baseID)
118     , m_name(name)
119     , m_offset(offset)
120     , m_repeats(repeats) 
121 {
122 }
123     
124 SVGSMILElement::SVGSMILElement(const QualifiedName& tagName, Document& doc)
125     : SVGElement(tagName, doc)
126     , m_attributeName(anyQName())
127     , m_targetElement(nullptr)
128     , m_conditionsConnected(false)
129     , m_hasEndEventConditions(false)
130     , m_isWaitingForFirstInterval(true)
131     , m_intervalBegin(SMILTime::unresolved())
132     , m_intervalEnd(SMILTime::unresolved())
133     , m_previousIntervalBegin(SMILTime::unresolved())
134     , m_activeState(Inactive)
135     , m_lastPercent(0)
136     , m_lastRepeat(0)
137     , m_nextProgressTime(0)
138     , m_documentOrderIndex(0)
139     , m_cachedDur(invalidCachedTime)
140     , m_cachedRepeatDur(invalidCachedTime)
141     , m_cachedRepeatCount(invalidCachedTime)
142     , m_cachedMin(invalidCachedTime)
143     , m_cachedMax(invalidCachedTime)
144 {
145     resolveFirstInterval();
146 }
147
148 SVGSMILElement::~SVGSMILElement()
149 {
150     clearResourceReferences();
151     smilBeginEventSender().cancelEvent(*this);
152     smilEndEventSender().cancelEvent(*this);
153     disconnectConditions();
154     if (m_timeContainer && m_targetElement && hasValidAttributeName())
155         m_timeContainer->unschedule(this, m_targetElement, m_attributeName);
156 }
157
158 void SVGSMILElement::clearResourceReferences()
159 {
160     document().accessSVGExtensions().removeAllTargetReferencesForElement(this);
161 }
162
163 void SVGSMILElement::clearTarget()
164 {
165     setTargetElement(nullptr);
166 }
167
168 void SVGSMILElement::buildPendingResource()
169 {
170     clearResourceReferences();
171
172     if (!isConnected()) {
173         // Reset the target element if we are no longer in the document.
174         setTargetElement(nullptr);
175         return;
176     }
177
178     String id;
179     Element* target;
180     auto& href = getAttribute(XLinkNames::hrefAttr);
181     if (href.isEmpty())
182         target = parentElement();
183     else
184         target = SVGURIReference::targetElementFromIRIString(href.string(), document(), &id);
185     SVGElement* svgTarget = is<SVGElement>(target) ? downcast<SVGElement>(target) : nullptr;
186
187     if (svgTarget && !svgTarget->isConnected())
188         svgTarget = nullptr;
189
190     if (svgTarget != targetElement())
191         setTargetElement(svgTarget);
192
193     if (!svgTarget) {
194         // Do not register as pending if we are already pending this resource.
195         if (document().accessSVGExtensions().isPendingResource(this, id))
196             return;
197
198         if (!id.isEmpty()) {
199             document().accessSVGExtensions().addPendingResource(id, this);
200             ASSERT(hasPendingResources());
201         }
202     } else {
203         // Register us with the target in the dependencies map. Any change of hrefElement
204         // that leads to relayout/repainting now informs us, so we can react to it.
205         document().accessSVGExtensions().addElementReferencingTarget(this, svgTarget);
206     }
207 }
208
209 inline QualifiedName SVGSMILElement::constructAttributeName() const
210 {
211     auto parseResult = Document::parseQualifiedName(attributeWithoutSynchronization(SVGNames::attributeNameAttr));
212     if (parseResult.hasException())
213         return anyQName();
214
215     AtomicString prefix, localName;
216     std::tie(prefix, localName) = parseResult.releaseReturnValue();
217
218     if (prefix.isNull())
219         return { nullAtom(), localName, nullAtom() };
220
221     auto namespaceURI = lookupNamespaceURI(prefix);
222     if (namespaceURI.isEmpty())
223         return anyQName();
224
225     return { nullAtom(), localName, namespaceURI };
226 }
227
228 inline void SVGSMILElement::updateAttributeName()
229 {
230     setAttributeName(constructAttributeName());
231 }
232
233 static inline void clearTimesWithDynamicOrigins(Vector<SMILTimeWithOrigin>& timeList)
234 {
235     timeList.removeAllMatching([] (const SMILTimeWithOrigin& time) {
236         return time.originIsScript();
237     });
238 }
239
240 void SVGSMILElement::reset()
241 {
242     clearAnimatedType(m_targetElement);
243
244     m_activeState = Inactive;
245     m_isWaitingForFirstInterval = true;
246     m_intervalBegin = SMILTime::unresolved();
247     m_intervalEnd = SMILTime::unresolved();
248     m_previousIntervalBegin = SMILTime::unresolved();
249     m_lastPercent = 0;
250     m_lastRepeat = 0;
251     m_nextProgressTime = 0;
252     resolveFirstInterval();
253 }
254
255 Node::InsertionNotificationRequest SVGSMILElement::insertedInto(ContainerNode& rootParent)
256 {
257     SVGElement::insertedInto(rootParent);
258     if (!rootParent.isConnected())
259         return InsertionDone;
260
261     // Verify we are not in <use> instance tree.
262     ASSERT(!isInShadowTree());
263
264     updateAttributeName();
265
266     SVGSVGElement* owner = ownerSVGElement();
267     if (!owner)
268         return InsertionDone;
269
270     m_timeContainer = &owner->timeContainer();
271     m_timeContainer->setDocumentOrderIndexesDirty();
272
273     // "If no attribute is present, the default begin value (an offset-value of 0) must be evaluated."
274     if (!hasAttributeWithoutSynchronization(SVGNames::beginAttr))
275         m_beginTimes.append(SMILTimeWithOrigin());
276
277     if (m_isWaitingForFirstInterval)
278         resolveFirstInterval();
279
280     if (m_timeContainer)
281         m_timeContainer->notifyIntervalsChanged();
282
283     return InsertionShouldCallFinishedInsertingSubtree;
284 }
285
286 void SVGSMILElement::finishedInsertingSubtree()
287 {
288     buildPendingResource();
289 }
290
291 void SVGSMILElement::removedFrom(ContainerNode& rootParent)
292 {
293     if (rootParent.isConnected()) {
294         clearResourceReferences();
295         disconnectConditions();
296         setTargetElement(nullptr);
297         setAttributeName(anyQName());
298         animationAttributeChanged();
299         m_timeContainer = nullptr;
300     }
301
302     SVGElement::removedFrom(rootParent);
303 }
304
305 bool SVGSMILElement::hasValidAttributeName()
306 {
307     return attributeName() != anyQName();
308 }
309
310 SMILTime SVGSMILElement::parseOffsetValue(const String& data)
311 {
312     bool ok;
313     double result = 0;
314     String parse = data.stripWhiteSpace();
315     if (parse.endsWith('h'))
316         result = parse.left(parse.length() - 1).toDouble(&ok) * 60 * 60;
317     else if (parse.endsWith("min"))
318         result = parse.left(parse.length() - 3).toDouble(&ok) * 60;
319     else if (parse.endsWith("ms"))
320         result = parse.left(parse.length() - 2).toDouble(&ok) / 1000;
321     else if (parse.endsWith('s'))
322         result = parse.left(parse.length() - 1).toDouble(&ok);
323     else
324         result = parse.toDouble(&ok);
325     if (!ok || !SMILTime(result).isFinite())
326         return SMILTime::unresolved();
327     return result;
328 }
329     
330 SMILTime SVGSMILElement::parseClockValue(const String& data)
331 {
332     if (data.isNull())
333         return SMILTime::unresolved();
334     
335     String parse = data.stripWhiteSpace();
336
337     static NeverDestroyed<const AtomicString> indefiniteValue("indefinite", AtomicString::ConstructFromLiteral);
338     if (parse == indefiniteValue)
339         return SMILTime::indefinite();
340
341     double result = 0;
342     bool ok;
343     size_t doublePointOne = parse.find(':');
344     size_t doublePointTwo = parse.find(':', doublePointOne + 1);
345     if (doublePointOne == 2 && doublePointTwo == 5 && parse.length() >= 8) { 
346         result += parse.substring(0, 2).toUIntStrict(&ok) * 60 * 60;
347         if (!ok)
348             return SMILTime::unresolved();
349         result += parse.substring(3, 2).toUIntStrict(&ok) * 60;
350         if (!ok)
351             return SMILTime::unresolved();
352         result += parse.substring(6).toDouble(&ok);
353     } else if (doublePointOne == 2 && doublePointTwo == notFound && parse.length() >= 5) { 
354         result += parse.substring(0, 2).toUIntStrict(&ok) * 60;
355         if (!ok)
356             return SMILTime::unresolved();
357         result += parse.substring(3).toDouble(&ok);
358     } else
359         return parseOffsetValue(parse);
360
361     if (!ok || !SMILTime(result).isFinite())
362         return SMILTime::unresolved();
363     return result;
364 }
365     
366 static void sortTimeList(Vector<SMILTimeWithOrigin>& timeList)
367 {
368     std::sort(timeList.begin(), timeList.end());
369 }
370     
371 bool SVGSMILElement::parseCondition(const String& value, BeginOrEnd beginOrEnd)
372 {
373     String parseString = value.stripWhiteSpace();
374     
375     double sign = 1.;
376     bool ok;
377     size_t pos = parseString.find('+');
378     if (pos == notFound) {
379         pos = parseString.find('-');
380         if (pos != notFound)
381             sign = -1.;
382     }
383     String conditionString;
384     SMILTime offset = 0;
385     if (pos == notFound)
386         conditionString = parseString;
387     else {
388         conditionString = parseString.left(pos).stripWhiteSpace();
389         String offsetString = parseString.substring(pos + 1).stripWhiteSpace();
390         offset = parseOffsetValue(offsetString);
391         if (offset.isUnresolved())
392             return false;
393         offset = offset * sign;
394     }
395     if (conditionString.isEmpty())
396         return false;
397     pos = conditionString.find('.');
398     
399     String baseID;
400     String nameString;
401     if (pos == notFound)
402         nameString = conditionString;
403     else {
404         baseID = conditionString.left(pos);
405         nameString = conditionString.substring(pos + 1);
406     }
407     if (nameString.isEmpty())
408         return false;
409
410     Condition::Type type;
411     int repeats = -1;
412     if (nameString.startsWith("repeat(") && nameString.endsWith(')')) {
413         // FIXME: For repeat events we just need to add the data carrying TimeEvent class and 
414         // fire the events at appropiate times.
415         repeats = nameString.substring(7, nameString.length() - 8).toUIntStrict(&ok);
416         if (!ok)
417             return false;
418         nameString = "repeat";
419         type = Condition::EventBase;
420     } else if (nameString == "begin" || nameString == "end") {
421         if (baseID.isEmpty())
422             return false;
423         type = Condition::Syncbase;
424     } else if (nameString.startsWith("accesskey(")) {
425         // FIXME: accesskey() support.
426         type = Condition::AccessKey;
427     } else
428         type = Condition::EventBase;
429     
430     m_conditions.append(Condition(type, beginOrEnd, baseID, nameString, offset, repeats));
431
432     if (type == Condition::EventBase && beginOrEnd == End)
433         m_hasEndEventConditions = true;
434
435     return true;
436 }
437
438 void SVGSMILElement::parseBeginOrEnd(const String& parseString, BeginOrEnd beginOrEnd)
439 {
440     Vector<SMILTimeWithOrigin>& timeList = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
441     if (beginOrEnd == End)
442         m_hasEndEventConditions = false;
443     HashSet<double> existing;
444     for (auto& time : timeList)
445         existing.add(time.time().value());
446     Vector<String> splitString;
447     parseString.split(';', splitString);
448     for (auto& string : splitString) {
449         SMILTime value = parseClockValue(string);
450         if (value.isUnresolved())
451             parseCondition(string, beginOrEnd);
452         else if (!existing.contains(value.value()))
453             timeList.append(SMILTimeWithOrigin(value, SMILTimeWithOrigin::ParserOrigin));
454     }
455     sortTimeList(timeList);
456 }
457
458 bool SVGSMILElement::isSupportedAttribute(const QualifiedName& attrName)
459 {
460     static NeverDestroyed<HashSet<QualifiedName>> supportedAttributes;
461     if (supportedAttributes.get().isEmpty()) {
462         supportedAttributes.get().add(SVGNames::beginAttr);
463         supportedAttributes.get().add(SVGNames::endAttr);
464         supportedAttributes.get().add(SVGNames::durAttr);
465         supportedAttributes.get().add(SVGNames::repeatDurAttr);
466         supportedAttributes.get().add(SVGNames::repeatCountAttr);
467         supportedAttributes.get().add(SVGNames::minAttr);
468         supportedAttributes.get().add(SVGNames::maxAttr);
469         supportedAttributes.get().add(SVGNames::attributeNameAttr);
470         supportedAttributes.get().add(XLinkNames::hrefAttr);
471     }
472     return supportedAttributes.get().contains<SVGAttributeHashTranslator>(attrName);
473 }
474
475 void SVGSMILElement::parseAttribute(const QualifiedName& name, const AtomicString& value)
476 {
477     if (name == SVGNames::beginAttr) {
478         if (!m_conditions.isEmpty()) {
479             disconnectConditions();
480             m_conditions.clear();
481             parseBeginOrEnd(attributeWithoutSynchronization(SVGNames::endAttr), End);
482         }
483         parseBeginOrEnd(value.string(), Begin);
484         if (isConnected())
485             connectConditions();
486     } else if (name == SVGNames::endAttr) {
487         if (!m_conditions.isEmpty()) {
488             disconnectConditions();
489             m_conditions.clear();
490             parseBeginOrEnd(attributeWithoutSynchronization(SVGNames::beginAttr), Begin);
491         }
492         parseBeginOrEnd(value.string(), End);
493         if (isConnected())
494             connectConditions();
495     } else if (name == SVGNames::onendAttr)
496         setAttributeEventListener(eventNames().endEventEvent, name, value);
497     else if (name == SVGNames::onbeginAttr)
498         setAttributeEventListener(eventNames().beginEventEvent, name, value);
499     else
500         SVGElement::parseAttribute(name, value);
501 }
502
503 void SVGSMILElement::svgAttributeChanged(const QualifiedName& attrName)
504 {
505     if (!isSupportedAttribute(attrName)) {
506         SVGElement::svgAttributeChanged(attrName);
507         return;
508     }
509
510     if (attrName == SVGNames::durAttr)
511         m_cachedDur = invalidCachedTime;
512     else if (attrName == SVGNames::repeatDurAttr)
513         m_cachedRepeatDur = invalidCachedTime;
514     else if (attrName == SVGNames::repeatCountAttr)
515         m_cachedRepeatCount = invalidCachedTime;
516     else if (attrName == SVGNames::minAttr)
517         m_cachedMin = invalidCachedTime;
518     else if (attrName == SVGNames::maxAttr)
519         m_cachedMax = invalidCachedTime;
520     else if (attrName == SVGNames::attributeNameAttr)
521         updateAttributeName();
522     else if (attrName.matches(XLinkNames::hrefAttr)) {
523         InstanceInvalidationGuard guard(*this);
524         buildPendingResource();
525     } else if (isConnected()) {
526         if (attrName == SVGNames::beginAttr)
527             beginListChanged(elapsed());
528         else if (attrName == SVGNames::endAttr)
529             endListChanged(elapsed());
530     }
531
532     animationAttributeChanged();
533 }
534
535 inline Element* SVGSMILElement::eventBaseFor(const Condition& condition)
536 {
537     return condition.m_baseID.isEmpty() ? targetElement() : treeScope().getElementById(condition.m_baseID);
538 }
539
540 void SVGSMILElement::connectConditions()
541 {
542     if (m_conditionsConnected)
543         disconnectConditions();
544     m_conditionsConnected = true;
545     for (auto& condition : m_conditions) {
546         if (condition.m_type == Condition::EventBase) {
547             ASSERT(!condition.m_syncbase);
548             Element* eventBase = eventBaseFor(condition);
549             if (!eventBase)
550                 continue;
551             ASSERT(!condition.m_eventListener);
552             condition.m_eventListener = ConditionEventListener::create(this, &condition);
553             eventBase->addEventListener(condition.m_name, *condition.m_eventListener, false);
554         } else if (condition.m_type == Condition::Syncbase) {
555             ASSERT(!condition.m_baseID.isEmpty());
556             condition.m_syncbase = treeScope().getElementById(condition.m_baseID);
557             if (!condition.m_syncbase)
558                 continue;
559             if (!is<SVGSMILElement>(*condition.m_syncbase)) {
560                 condition.m_syncbase = nullptr;
561                 continue;
562             }
563             downcast<SVGSMILElement>(*condition.m_syncbase).addTimeDependent(this);
564         }
565     }
566 }
567
568 void SVGSMILElement::disconnectConditions()
569 {
570     if (!m_conditionsConnected)
571         return;
572     m_conditionsConnected = false;
573     for (auto& condition : m_conditions) {
574         if (condition.m_type == Condition::EventBase) {
575             ASSERT(!condition.m_syncbase);
576             if (!condition.m_eventListener)
577                 continue;
578             // Note: It's a memory optimization to try to remove our condition
579             // event listener, but it's not guaranteed to work, since we have
580             // no guarantee that eventBaseFor() will be able to find our condition's
581             // original eventBase. So, we also have to disconnect ourselves from
582             // our condition event listener, in case it later fires.
583             Element* eventBase = eventBaseFor(condition);
584             if (eventBase)
585                 eventBase->removeEventListener(condition.m_name, *condition.m_eventListener, false);
586             condition.m_eventListener->disconnectAnimation();
587             condition.m_eventListener = nullptr;
588         } else if (condition.m_type == Condition::Syncbase) {
589             if (condition.m_syncbase)
590                 downcast<SVGSMILElement>(condition.m_syncbase.get())->removeTimeDependent(this);
591         }
592         condition.m_syncbase = nullptr;
593     }
594 }
595
596 void SVGSMILElement::setAttributeName(const QualifiedName& attributeName)
597 {
598     if (m_timeContainer && m_targetElement && m_attributeName != attributeName) {
599         if (hasValidAttributeName())
600             m_timeContainer->unschedule(this, m_targetElement, m_attributeName);
601         m_attributeName = attributeName;
602         if (hasValidAttributeName())
603             m_timeContainer->schedule(this, m_targetElement, m_attributeName);
604     } else
605         m_attributeName = attributeName;
606
607     // Only clear the animated type, if we had a target before.
608     if (m_targetElement)
609         clearAnimatedType(m_targetElement);
610 }
611
612 void SVGSMILElement::setTargetElement(SVGElement* target)
613 {
614     if (m_timeContainer && hasValidAttributeName()) {
615         if (m_targetElement)
616             m_timeContainer->unschedule(this, m_targetElement, m_attributeName);
617         if (target)
618             m_timeContainer->schedule(this, target, m_attributeName);
619     }
620
621     if (m_targetElement) {
622         // Clear values that may depend on the previous target.
623         clearAnimatedType(m_targetElement);
624         disconnectConditions();
625     }
626
627     // If the animation state is not Inactive, always reset to a clear state before leaving the old target element.
628     if (m_activeState != Inactive)
629         endedActiveInterval();
630
631     m_targetElement = target;
632 }
633
634 SMILTime SVGSMILElement::elapsed() const
635 {
636     return m_timeContainer ? m_timeContainer->elapsed() : 0;
637 }
638
639 bool SVGSMILElement::isInactive() const
640 {
641      return m_activeState == Inactive;
642 }
643
644 bool SVGSMILElement::isFrozen() const
645 {
646     return m_activeState == Frozen;
647 }
648     
649 SVGSMILElement::Restart SVGSMILElement::restart() const
650 {    
651     static NeverDestroyed<const AtomicString> never("never", AtomicString::ConstructFromLiteral);
652     static NeverDestroyed<const AtomicString> whenNotActive("whenNotActive", AtomicString::ConstructFromLiteral);
653     const AtomicString& value = attributeWithoutSynchronization(SVGNames::restartAttr);
654     if (value == never)
655         return RestartNever;
656     if (value == whenNotActive)
657         return RestartWhenNotActive;
658     return RestartAlways;
659 }
660     
661 SVGSMILElement::FillMode SVGSMILElement::fill() const
662 {   
663     static NeverDestroyed<const AtomicString> freeze("freeze", AtomicString::ConstructFromLiteral);
664     const AtomicString& value = attributeWithoutSynchronization(SVGNames::fillAttr);
665     return value == freeze ? FillFreeze : FillRemove;
666 }
667     
668 SMILTime SVGSMILElement::dur() const
669 {   
670     if (m_cachedDur != invalidCachedTime)
671         return m_cachedDur;
672     const AtomicString& value = attributeWithoutSynchronization(SVGNames::durAttr);
673     SMILTime clockValue = parseClockValue(value);
674     return m_cachedDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
675 }
676
677 SMILTime SVGSMILElement::repeatDur() const
678 {    
679     if (m_cachedRepeatDur != invalidCachedTime)
680         return m_cachedRepeatDur;
681     const AtomicString& value = attributeWithoutSynchronization(SVGNames::repeatDurAttr);
682     SMILTime clockValue = parseClockValue(value);
683     m_cachedRepeatDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
684     return m_cachedRepeatDur;
685 }
686     
687 // So a count is not really a time but let just all pretend we did not notice.
688 SMILTime SVGSMILElement::repeatCount() const
689 {    
690     if (m_cachedRepeatCount != invalidCachedTime)
691         return m_cachedRepeatCount;
692     const AtomicString& value = attributeWithoutSynchronization(SVGNames::repeatCountAttr);
693     if (value.isNull())
694         return SMILTime::unresolved();
695
696     static NeverDestroyed<const AtomicString> indefiniteValue("indefinite", AtomicString::ConstructFromLiteral);
697     if (value == indefiniteValue)
698         return SMILTime::indefinite();
699     bool ok;
700     double result = value.string().toDouble(&ok);
701     return m_cachedRepeatCount = ok && result > 0 ? result : SMILTime::unresolved();
702 }
703
704 SMILTime SVGSMILElement::maxValue() const
705 {    
706     if (m_cachedMax != invalidCachedTime)
707         return m_cachedMax;
708     const AtomicString& value = attributeWithoutSynchronization(SVGNames::maxAttr);
709     SMILTime result = parseClockValue(value);
710     return m_cachedMax = (result.isUnresolved() || result <= 0) ? SMILTime::indefinite() : result;
711 }
712     
713 SMILTime SVGSMILElement::minValue() const
714 {    
715     if (m_cachedMin != invalidCachedTime)
716         return m_cachedMin;
717     const AtomicString& value = attributeWithoutSynchronization(SVGNames::minAttr);
718     SMILTime result = parseClockValue(value);
719     return m_cachedMin = (result.isUnresolved() || result < 0) ? 0 : result;
720 }
721                  
722 SMILTime SVGSMILElement::simpleDuration() const
723 {
724     return std::min(dur(), SMILTime::indefinite());
725 }
726
727 void SVGSMILElement::addBeginTime(SMILTime eventTime, SMILTime beginTime, SMILTimeWithOrigin::Origin origin)
728 {
729     ASSERT(!std::isnan(beginTime.value()));
730     m_beginTimes.append(SMILTimeWithOrigin(beginTime, origin));
731     sortTimeList(m_beginTimes);
732     beginListChanged(eventTime);
733 }
734
735 void SVGSMILElement::addEndTime(SMILTime eventTime, SMILTime endTime, SMILTimeWithOrigin::Origin origin)
736 {
737     ASSERT(!std::isnan(endTime.value()));
738     m_endTimes.append(SMILTimeWithOrigin(endTime, origin));
739     sortTimeList(m_endTimes);
740     endListChanged(eventTime);
741 }
742
743 inline SMILTime extractTimeFromVector(const SMILTimeWithOrigin* position)
744 {
745     return position->time();
746 }
747
748 SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
749 {
750     const Vector<SMILTimeWithOrigin>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
751     int sizeOfList = list.size();
752
753     if (!sizeOfList)
754         return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
755
756     const SMILTimeWithOrigin* result = approximateBinarySearch<const SMILTimeWithOrigin, SMILTime>(list, sizeOfList, minimumTime, extractTimeFromVector);
757     int indexOfResult = result - list.begin();
758     ASSERT_WITH_SECURITY_IMPLICATION(indexOfResult < sizeOfList);
759
760     if (list[indexOfResult].time() < minimumTime && indexOfResult < sizeOfList - 1)
761         ++indexOfResult;
762
763     const SMILTime& currentTime = list[indexOfResult].time();
764
765     // The special value "indefinite" does not yield an instance time in the begin list.
766     if (currentTime.isIndefinite() && beginOrEnd == Begin)
767         return SMILTime::unresolved();
768
769     if (currentTime < minimumTime)
770         return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
771     if (currentTime > minimumTime)
772         return currentTime;
773
774     ASSERT(currentTime == minimumTime);
775     if (equalsMinimumOK)
776         return currentTime;
777
778     // If the equals is not accepted, return the next bigger item in the list.
779     SMILTime nextTime = currentTime;
780     while (indexOfResult < sizeOfList - 1) {
781         nextTime = list[indexOfResult + 1].time();
782         if (nextTime > minimumTime)
783             return nextTime;
784         ++indexOfResult;
785     }
786
787     return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
788 }
789
790 SMILTime SVGSMILElement::repeatingDuration() const
791 {
792     // Computing the active duration
793     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
794     SMILTime repeatCount = this->repeatCount();
795     SMILTime repeatDur = this->repeatDur();
796     SMILTime simpleDuration = this->simpleDuration();
797     if (!simpleDuration || (repeatDur.isUnresolved() && repeatCount.isUnresolved()))
798         return simpleDuration;
799     SMILTime repeatCountDuration = simpleDuration * repeatCount;
800     return std::min(repeatCountDuration, std::min(repeatDur, SMILTime::indefinite()));
801 }
802
803 SMILTime SVGSMILElement::resolveActiveEnd(SMILTime resolvedBegin, SMILTime resolvedEnd) const
804 {
805     // Computing the active duration
806     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
807     SMILTime preliminaryActiveDuration;
808     if (!resolvedEnd.isUnresolved() && dur().isUnresolved() && repeatDur().isUnresolved() && repeatCount().isUnresolved())
809         preliminaryActiveDuration = resolvedEnd - resolvedBegin;
810     else if (!resolvedEnd.isFinite())
811         preliminaryActiveDuration = repeatingDuration();
812     else
813         preliminaryActiveDuration = std::min(repeatingDuration(), resolvedEnd - resolvedBegin);
814     
815     SMILTime minValue = this->minValue();
816     SMILTime maxValue = this->maxValue();
817     if (minValue > maxValue) {
818         // Ignore both.
819         // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#MinMax
820         minValue = 0;
821         maxValue = SMILTime::indefinite();
822     }
823     return resolvedBegin + std::min(maxValue, std::max(minValue, preliminaryActiveDuration));
824 }
825
826 void SVGSMILElement::resolveInterval(bool first, SMILTime& beginResult, SMILTime& endResult) const
827 {
828     // See the pseudocode in http://www.w3.org/TR/SMIL3/smil-timing.html#q90.
829     SMILTime beginAfter = first ? -std::numeric_limits<double>::infinity() : m_intervalEnd;
830     SMILTime lastIntervalTempEnd = std::numeric_limits<double>::infinity();
831     while (true) {
832         bool equalsMinimumOK = !first || m_intervalEnd > m_intervalBegin;
833         SMILTime tempBegin = findInstanceTime(Begin, beginAfter, equalsMinimumOK);
834         if (tempBegin.isUnresolved())
835             break;
836         SMILTime tempEnd;
837         if (m_endTimes.isEmpty())
838             tempEnd = resolveActiveEnd(tempBegin, SMILTime::indefinite());
839         else {
840             tempEnd = findInstanceTime(End, tempBegin, true);
841             if ((first && tempBegin == tempEnd && tempEnd == lastIntervalTempEnd) || (!first && tempEnd == m_intervalEnd)) 
842                 tempEnd = findInstanceTime(End, tempBegin, false);    
843             if (tempEnd.isUnresolved()) {
844                 if (!m_endTimes.isEmpty() && !m_hasEndEventConditions)
845                     break;
846             }
847             tempEnd = resolveActiveEnd(tempBegin, tempEnd);
848         }
849         if (!first || (tempEnd > 0 || (!tempBegin.value() && !tempEnd.value()))) {
850             beginResult = tempBegin;
851             endResult = tempEnd;
852             return;
853         }
854
855         beginAfter = tempEnd;
856         lastIntervalTempEnd = tempEnd;
857     }
858     beginResult = SMILTime::unresolved();
859     endResult = SMILTime::unresolved();
860 }
861     
862 void SVGSMILElement::resolveFirstInterval()
863 {
864     SMILTime begin;
865     SMILTime end;
866     resolveInterval(true, begin, end);
867     ASSERT(!begin.isIndefinite());
868
869     if (!begin.isUnresolved() && (begin != m_intervalBegin || end != m_intervalEnd)) {   
870         bool wasUnresolved = m_intervalBegin.isUnresolved();
871         m_intervalBegin = begin;
872         m_intervalEnd = end;
873         notifyDependentsIntervalChanged(wasUnresolved ? NewInterval : ExistingInterval);
874         m_nextProgressTime = std::min(m_nextProgressTime, m_intervalBegin);
875
876         if (m_timeContainer)
877             m_timeContainer->notifyIntervalsChanged();
878     }
879 }
880
881 void SVGSMILElement::resolveNextInterval(bool notifyDependents)
882 {
883     SMILTime begin;
884     SMILTime end;
885     resolveInterval(false, begin, end);
886     ASSERT(!begin.isIndefinite());
887     
888     if (!begin.isUnresolved() && begin != m_intervalBegin) {
889         m_intervalBegin = begin;
890         m_intervalEnd = end;
891         if (notifyDependents)
892             notifyDependentsIntervalChanged(NewInterval);
893         m_nextProgressTime = std::min(m_nextProgressTime, m_intervalBegin);
894     }
895 }
896
897 SMILTime SVGSMILElement::nextProgressTime() const
898 {
899     return m_nextProgressTime;
900 }
901     
902 void SVGSMILElement::beginListChanged(SMILTime eventTime)
903 {
904     if (m_isWaitingForFirstInterval)
905         resolveFirstInterval();
906     else {
907         SMILTime newBegin = findInstanceTime(Begin, eventTime, true);
908         if (newBegin.isFinite() && (m_intervalEnd <= eventTime || newBegin < m_intervalBegin)) {
909             // Begin time changed, re-resolve the interval.
910             SMILTime oldBegin = m_intervalBegin;
911             m_intervalEnd = eventTime;
912             resolveInterval(false, m_intervalBegin, m_intervalEnd);  
913             ASSERT(!m_intervalBegin.isUnresolved());
914             if (m_intervalBegin != oldBegin) {
915                 if (m_activeState == Active && m_intervalBegin > eventTime) {
916                     m_activeState = determineActiveState(eventTime);
917                     if (m_activeState != Active)
918                         endedActiveInterval();
919                 }
920                 notifyDependentsIntervalChanged(ExistingInterval);
921             }
922         }
923     }
924     m_nextProgressTime = elapsed();
925
926     if (m_timeContainer)
927         m_timeContainer->notifyIntervalsChanged();
928 }
929
930 void SVGSMILElement::endListChanged(SMILTime)
931 {
932     SMILTime elapsed = this->elapsed();
933     if (m_isWaitingForFirstInterval)
934         resolveFirstInterval();
935     else if (elapsed < m_intervalEnd && m_intervalBegin.isFinite()) {
936         SMILTime newEnd = findInstanceTime(End, m_intervalBegin, false);
937         if (newEnd < m_intervalEnd) {
938             newEnd = resolveActiveEnd(m_intervalBegin, newEnd);
939             if (newEnd != m_intervalEnd) {
940                 m_intervalEnd = newEnd;
941                 notifyDependentsIntervalChanged(ExistingInterval);
942             }
943         }
944     }
945     m_nextProgressTime = elapsed;
946
947     if (m_timeContainer)
948         m_timeContainer->notifyIntervalsChanged();
949 }
950
951 void SVGSMILElement::checkRestart(SMILTime elapsed)
952 {
953     ASSERT(!m_isWaitingForFirstInterval);
954     ASSERT(elapsed >= m_intervalBegin);
955
956     Restart restart = this->restart();
957     if (restart == RestartNever)
958         return;
959
960     if (elapsed < m_intervalEnd) {
961         if (restart != RestartAlways)
962             return;
963         SMILTime nextBegin = findInstanceTime(Begin, m_intervalBegin, false);
964         if (nextBegin < m_intervalEnd) { 
965             m_intervalEnd = nextBegin;
966             notifyDependentsIntervalChanged(ExistingInterval);
967         }
968     }
969
970     if (elapsed >= m_intervalEnd)
971         resolveNextInterval(true);
972 }
973
974 void SVGSMILElement::seekToIntervalCorrespondingToTime(SMILTime elapsed)
975 {
976     ASSERT(!m_isWaitingForFirstInterval);
977     ASSERT(elapsed >= m_intervalBegin);
978
979     // Manually seek from interval to interval, just as if the animation would run regulary.
980     while (true) {
981         // Figure out the next value in the begin time list after the current interval begin.
982         SMILTime nextBegin = findInstanceTime(Begin, m_intervalBegin, false);
983
984         // If the 'nextBegin' time is unresolved (eg. just one defined interval), we're done seeking.
985         if (nextBegin.isUnresolved())
986             return;
987
988         // If the 'nextBegin' time is larger than or equal to the current interval end time, we're done seeking.
989         // If the 'elapsed' time is smaller than the next begin interval time, we're done seeking.
990         if (nextBegin < m_intervalEnd && elapsed >= nextBegin) {
991             // End current interval, and start a new interval from the 'nextBegin' time.
992             m_intervalEnd = nextBegin;
993             resolveNextInterval(false);
994             continue;
995         }
996
997         // If the desired 'elapsed' time is past the current interval, advance to the next.
998         if (elapsed >= m_intervalEnd) {
999             resolveNextInterval(false);
1000             continue;
1001         }
1002
1003         return;
1004     }
1005 }
1006
1007 float SVGSMILElement::calculateAnimationPercentAndRepeat(SMILTime elapsed, unsigned& repeat) const
1008 {
1009     SMILTime simpleDuration = this->simpleDuration();
1010     repeat = 0;
1011     if (simpleDuration.isIndefinite()) {
1012         repeat = 0;
1013         return 0.f;
1014     }
1015     if (!simpleDuration) {
1016         repeat = 0;
1017         return 1.f;
1018     }
1019     ASSERT(m_intervalBegin.isFinite());
1020     ASSERT(simpleDuration.isFinite());
1021     SMILTime activeTime = elapsed - m_intervalBegin;
1022     SMILTime repeatingDuration = this->repeatingDuration();
1023     if (elapsed >= m_intervalEnd || activeTime > repeatingDuration) {
1024         repeat = static_cast<unsigned>(repeatingDuration.value() / simpleDuration.value()) - 1;
1025
1026         double percent = (m_intervalEnd.value() - m_intervalBegin.value()) / simpleDuration.value();
1027         percent = percent - floor(percent);
1028         if (percent < std::numeric_limits<float>::epsilon() || 1 - percent < std::numeric_limits<float>::epsilon())
1029             return 1.0f;
1030         return narrowPrecisionToFloat(percent);
1031     }
1032     repeat = static_cast<unsigned>(activeTime.value() / simpleDuration.value());
1033     SMILTime simpleTime = fmod(activeTime.value(), simpleDuration.value());
1034     return narrowPrecisionToFloat(simpleTime.value() / simpleDuration.value());
1035 }
1036     
1037 SMILTime SVGSMILElement::calculateNextProgressTime(SMILTime elapsed) const
1038 {
1039     ASSERT(m_timeContainer);
1040     if (m_activeState == Active) {
1041         // If duration is indefinite the value does not actually change over time. Same is true for <set>.
1042         SMILTime simpleDuration = this->simpleDuration();
1043         if (simpleDuration.isIndefinite() || hasTagName(SVGNames::setTag)) {
1044             SMILTime repeatingDurationEnd = m_intervalBegin + repeatingDuration();
1045             // We are supposed to do freeze semantics when repeating ends, even if the element is still active. 
1046             // Take care that we get a timer callback at that point.
1047             if (elapsed < repeatingDurationEnd && repeatingDurationEnd < m_intervalEnd && repeatingDurationEnd.isFinite())
1048                 return repeatingDurationEnd;
1049             return m_intervalEnd;
1050         } 
1051         return elapsed + m_timeContainer->animationFrameDelay();
1052     }
1053     return m_intervalBegin >= elapsed ? m_intervalBegin : SMILTime::unresolved();
1054 }
1055     
1056 SVGSMILElement::ActiveState SVGSMILElement::determineActiveState(SMILTime elapsed) const
1057 {
1058     if (elapsed >= m_intervalBegin && elapsed < m_intervalEnd)
1059         return Active;
1060
1061     return fill() == FillFreeze ? Frozen : Inactive;
1062 }
1063     
1064 bool SVGSMILElement::isContributing(SMILTime elapsed) const 
1065
1066     // Animation does not contribute during the active time if it is past its repeating duration and has fill=remove.
1067     return (m_activeState == Active && (fill() == FillFreeze || elapsed <= m_intervalBegin + repeatingDuration())) || m_activeState == Frozen;
1068 }
1069     
1070 bool SVGSMILElement::progress(SMILTime elapsed, SVGSMILElement* resultElement, bool seekToTime)
1071 {
1072     ASSERT(resultElement);
1073     ASSERT(m_timeContainer);
1074     ASSERT(m_isWaitingForFirstInterval || m_intervalBegin.isFinite());
1075
1076     if (!m_intervalBegin.isFinite()) {
1077         ASSERT(m_activeState == Inactive);
1078         m_nextProgressTime = SMILTime::unresolved();
1079         return false;
1080     }
1081
1082     if (elapsed < m_intervalBegin) {
1083         ASSERT(m_activeState != Active);
1084         if (m_activeState == Frozen) {
1085             if (this == resultElement)
1086                 resetAnimatedType();
1087             updateAnimation(m_lastPercent, m_lastRepeat, resultElement);
1088         }
1089         m_nextProgressTime = m_intervalBegin;
1090         return false;
1091     }
1092
1093     m_previousIntervalBegin = m_intervalBegin;
1094
1095     if (m_isWaitingForFirstInterval) {
1096         m_isWaitingForFirstInterval = false;
1097         resolveFirstInterval();
1098     }
1099
1100     // This call may obtain a new interval -- never call calculateAnimationPercentAndRepeat() before!
1101     if (seekToTime) {
1102         seekToIntervalCorrespondingToTime(elapsed);
1103         if (elapsed < m_intervalBegin) {
1104             // elapsed is not within an interval.
1105             m_nextProgressTime = m_intervalBegin;
1106             return false;
1107         }
1108     }
1109
1110     unsigned repeat = 0;
1111     float percent = calculateAnimationPercentAndRepeat(elapsed, repeat);
1112     checkRestart(elapsed);
1113
1114     ActiveState oldActiveState = m_activeState;
1115     m_activeState = determineActiveState(elapsed);
1116     bool animationIsContributing = isContributing(elapsed);
1117
1118     // Only reset the animated type to the base value once for the lowest priority animation that animates and contributes to a particular element/attribute pair.
1119     if (this == resultElement && animationIsContributing)
1120         resetAnimatedType();
1121
1122     if (animationIsContributing) {
1123         if (oldActiveState == Inactive)
1124             startedActiveInterval();
1125
1126         updateAnimation(percent, repeat, resultElement);
1127         m_lastPercent = percent;
1128         m_lastRepeat = repeat;
1129     }
1130
1131     if (oldActiveState == Active && m_activeState != Active) {
1132         smilEndEventSender().dispatchEventSoon(*this);
1133         endedActiveInterval();
1134         if (m_activeState != Frozen)
1135             clearAnimatedType(m_targetElement);
1136     } else if (oldActiveState != Active && m_activeState == Active)
1137         smilBeginEventSender().dispatchEventSoon(*this);
1138
1139     // Triggering all the pending events if the animation timeline is changed.
1140     if (seekToTime) {
1141         if (m_activeState == Inactive || m_activeState == Frozen)
1142             smilEndEventSender().dispatchEventSoon(*this);
1143     }
1144
1145     m_nextProgressTime = calculateNextProgressTime(elapsed);
1146     return animationIsContributing;
1147 }
1148     
1149 void SVGSMILElement::notifyDependentsIntervalChanged(NewOrExistingInterval newOrExisting)
1150 {
1151     ASSERT(m_intervalBegin.isFinite());
1152     static NeverDestroyed<HashSet<SVGSMILElement*>> loopBreaker;
1153     if (loopBreaker.get().contains(this))
1154         return;
1155     loopBreaker.get().add(this);
1156     
1157     for (auto& dependent : m_timeDependents) {
1158         dependent->createInstanceTimesFromSyncbase(this, newOrExisting);
1159     }
1160
1161     loopBreaker.get().remove(this);
1162 }
1163     
1164 void SVGSMILElement::createInstanceTimesFromSyncbase(SVGSMILElement* syncbase, NewOrExistingInterval)
1165 {
1166     // FIXME: To be really correct, this should handle updating exising interval by changing 
1167     // the associated times instead of creating new ones.
1168     for (auto& condition : m_conditions) {
1169         if (condition.m_type == Condition::Syncbase && condition.m_syncbase == syncbase) {
1170             ASSERT(condition.m_name == "begin" || condition.m_name == "end");
1171             // No nested time containers in SVG, no need for crazy time space conversions. Phew!
1172             SMILTime time = 0;
1173             if (condition.m_name == "begin")
1174                 time = syncbase->m_intervalBegin + condition.m_offset;
1175             else
1176                 time = syncbase->m_intervalEnd + condition.m_offset;
1177             if (!time.isFinite())
1178                 continue;
1179             if (condition.m_beginOrEnd == Begin)
1180                 addBeginTime(elapsed(), time);
1181             else
1182                 addEndTime(elapsed(), time);
1183         }
1184     }
1185 }
1186     
1187 void SVGSMILElement::addTimeDependent(SVGSMILElement* animation)
1188 {
1189     m_timeDependents.add(animation);
1190     if (m_intervalBegin.isFinite())
1191         animation->createInstanceTimesFromSyncbase(this, NewInterval);
1192 }
1193     
1194 void SVGSMILElement::removeTimeDependent(SVGSMILElement* animation)
1195 {
1196     m_timeDependents.remove(animation);
1197 }
1198     
1199 void SVGSMILElement::handleConditionEvent(Event*, Condition* condition)
1200 {
1201     SMILTime elapsed = this->elapsed();
1202     if (condition->m_beginOrEnd == Begin)
1203         addBeginTime(elapsed, elapsed + condition->m_offset);
1204     else
1205         addEndTime(elapsed, elapsed + condition->m_offset);
1206 }
1207
1208 void SVGSMILElement::beginByLinkActivation()
1209 {
1210     SMILTime elapsed = this->elapsed();
1211     addBeginTime(elapsed, elapsed);
1212 }
1213
1214 void SVGSMILElement::endedActiveInterval()
1215 {
1216     clearTimesWithDynamicOrigins(m_beginTimes);
1217     clearTimesWithDynamicOrigins(m_endTimes);
1218 }
1219
1220 void SVGSMILElement::dispatchPendingEvent(SMILEventSender* eventSender)
1221 {
1222     ASSERT(eventSender == &smilBeginEventSender() || eventSender == &smilEndEventSender());
1223     const AtomicString& eventType = eventSender->eventType();
1224     dispatchEvent(Event::create(eventType, false, false));
1225 }
1226
1227 }