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