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