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