dca5064162a3fd65f6edbf25934df75c2e7ce7bc
[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
28 #if ENABLE(SVG_ANIMATION)
29 #include "SVGSMILElement.h"
30
31 #include "Attribute.h"
32 #include "CSSPropertyNames.h"
33 #include "Document.h"
34 #include "Event.h"
35 #include "EventListener.h"
36 #include "FloatConversion.h"
37 #include "FrameView.h"
38 #include "HTMLNames.h"
39 #include "SMILTimeContainer.h"
40 #include "SVGDocumentExtensions.h"
41 #include "SVGNames.h"
42 #include "SVGParserUtilities.h"
43 #include "SVGSVGElement.h"
44 #include "SVGURIReference.h"
45 #include "XLinkNames.h"
46 #include <wtf/MathExtras.h>
47 #include <wtf/StdLibExtras.h>
48 #include <wtf/Vector.h>
49
50 using namespace std;
51
52 namespace WebCore {
53     
54 // This is used for duration type time values that can't be negative.
55 static const double invalidCachedTime = -1.;
56     
57 class ConditionEventListener : public EventListener {
58 public:
59     static PassRefPtr<ConditionEventListener> create(SVGSMILElement* animation, SVGSMILElement::Condition* condition)
60     {
61         return adoptRef(new ConditionEventListener(animation, condition));
62     }
63
64     static const ConditionEventListener* cast(const EventListener* listener)
65     {
66         return listener->type() == ConditionEventListenerType
67             ? static_cast<const ConditionEventListener*>(listener)
68             : 0;
69     }
70
71     virtual bool operator==(const EventListener& other);
72     
73     void disconnectAnimation()
74     {
75         m_animation = 0;
76     }
77
78 private:
79     ConditionEventListener(SVGSMILElement* animation, SVGSMILElement::Condition* condition) 
80         : EventListener(ConditionEventListenerType)
81         , m_animation(animation)
82         , m_condition(condition) 
83     {
84     }
85
86     virtual void handleEvent(ScriptExecutionContext*, Event*);
87
88     SVGSMILElement* m_animation;
89     SVGSMILElement::Condition* m_condition;
90 };
91
92 bool ConditionEventListener::operator==(const EventListener& listener)
93 {
94     if (const ConditionEventListener* conditionEventListener = ConditionEventListener::cast(&listener))
95         return m_animation == conditionEventListener->m_animation && m_condition == conditionEventListener->m_condition;
96     return false;
97 }
98
99 void ConditionEventListener::handleEvent(ScriptExecutionContext*, Event* event) 
100 {
101     if (!m_animation)
102         return;
103     m_animation->handleConditionEvent(event, m_condition);
104 }
105
106 SVGSMILElement::Condition::Condition(Type type, BeginOrEnd beginOrEnd, const String& baseID, const String& name, SMILTime offset, int repeats)
107     : m_type(type)
108     , m_beginOrEnd(beginOrEnd)
109     , m_baseID(baseID)
110     , m_name(name)
111     , m_offset(offset)
112     , m_repeats(repeats) 
113 {
114 }
115     
116 SVGSMILElement::SVGSMILElement(const QualifiedName& tagName, Document* doc)
117     : SVGElement(tagName, doc)
118     , m_attributeName(anyQName())
119     , m_targetElement(0)
120     , m_conditionsConnected(false)
121     , m_hasEndEventConditions(false)
122     , m_intervalBegin(SMILTime::unresolved())
123     , m_intervalEnd(SMILTime::unresolved())
124     , m_previousIntervalBegin(SMILTime::unresolved())
125     , m_isWaitingForFirstInterval(true)
126     , m_activeState(Inactive)
127     , m_lastPercent(0)
128     , m_lastRepeat(0)
129     , m_nextProgressTime(0)
130     , m_documentOrderIndex(0)
131     , m_cachedDur(invalidCachedTime)
132     , m_cachedRepeatDur(invalidCachedTime)
133     , m_cachedRepeatCount(invalidCachedTime)
134     , m_cachedMin(invalidCachedTime)
135     , m_cachedMax(invalidCachedTime)
136 {
137 }
138
139 SVGSMILElement::~SVGSMILElement()
140 {
141     disconnectConditions();
142     if (m_timeContainer)
143         m_timeContainer->unschedule(this);
144     if (m_targetElement)
145         document()->accessSVGExtensions()->removeAnimationElementFromTarget(this, m_targetElement);
146 }
147
148 static inline QualifiedName constructQualifiedName(const SVGElement* svgElement, const String& attributeName)
149 {
150     ASSERT(svgElement);
151     if (attributeName.isEmpty())
152         return anyQName();
153     if (!attributeName.contains(':'))
154         return QualifiedName(nullAtom, attributeName, nullAtom);
155     
156     String prefix;
157     String localName;
158     ExceptionCode ec = 0;
159     if (!Document::parseQualifiedName(attributeName, prefix, localName, ec))
160         return anyQName();
161     ASSERT(!ec);
162     
163     String namespaceURI = svgElement->lookupNamespaceURI(prefix);    
164     if (namespaceURI.isEmpty())
165         return anyQName();
166     
167     return QualifiedName(nullAtom, localName, namespaceURI);
168 }
169     
170 void SVGSMILElement::insertedIntoDocument()
171 {
172     SVGElement::insertedIntoDocument();
173 #ifndef NDEBUG
174     // Verify we are not in <use> instance tree.
175     for (ContainerNode* n = this; n; n = n->parentNode())
176         ASSERT(!n->isSVGShadowRoot());
177 #endif
178     m_attributeName = constructQualifiedName(this, getAttribute(SVGNames::attributeNameAttr));
179     SVGSVGElement* owner = ownerSVGElement();
180     if (!owner)
181         return;
182     m_timeContainer = owner->timeContainer();
183     ASSERT(m_timeContainer);
184     m_timeContainer->setDocumentOrderIndexesDirty();
185     reschedule();
186 }
187
188 void SVGSMILElement::removedFromDocument()
189 {
190     m_attributeName = anyQName();
191     if (m_timeContainer) {
192         m_timeContainer->unschedule(this);
193         m_timeContainer = 0;
194     }
195     if (m_targetElement) {
196         document()->accessSVGExtensions()->removeAnimationElementFromTarget(this, m_targetElement);
197         m_targetElement = 0;
198     }
199     // Calling disconnectConditions() may kill us if there are syncbase conditions.
200     // OK, but we don't want to die inside the call.
201     RefPtr<SVGSMILElement> keepAlive(this);
202     disconnectConditions();
203     SVGElement::removedFromDocument();
204 }
205    
206 void SVGSMILElement::finishParsingChildren()
207 {
208     SVGElement::finishParsingChildren();
209
210     // "If no attribute is present, the default begin value (an offset-value of 0) must be evaluated."
211     if (!hasAttribute(SVGNames::beginAttr))
212         m_beginTimes.append(0);
213
214     if (m_isWaitingForFirstInterval) {
215         resolveFirstInterval();
216         reschedule();
217     }
218 }
219
220 SMILTime SVGSMILElement::parseOffsetValue(const String& data)
221 {
222     bool ok;
223     double result = 0;
224     String parse = data.stripWhiteSpace();
225     if (parse.endsWith("h"))
226         result = parse.left(parse.length() - 1).toDouble(&ok) * 60 * 60;
227     else if (parse.endsWith("min"))
228         result = parse.left(parse.length() - 3).toDouble(&ok) * 60;
229     else if (parse.endsWith("ms"))
230         result = parse.left(parse.length() - 2).toDouble(&ok) / 1000;
231     else if (parse.endsWith("s"))
232         result = parse.left(parse.length() - 1).toDouble(&ok);
233     else
234         result = parse.toDouble(&ok);
235     if (!ok)
236         return SMILTime::unresolved();
237     return result;
238 }
239     
240 SMILTime SVGSMILElement::parseClockValue(const String& data)
241 {
242     if (data.isNull())
243         return SMILTime::unresolved();
244     
245     String parse = data.stripWhiteSpace();
246
247     DEFINE_STATIC_LOCAL(const AtomicString, indefiniteValue, ("indefinite"));
248     if (parse == indefiniteValue)
249         return SMILTime::indefinite();
250
251     double result = 0;
252     bool ok;
253     size_t doublePointOne = parse.find(':');
254     size_t doublePointTwo = parse.find(':', doublePointOne + 1);
255     if (doublePointOne == 2 && doublePointTwo == 5 && parse.length() >= 8) { 
256         result += parse.substring(0, 2).toUIntStrict(&ok) * 60 * 60;
257         if (!ok)
258             return SMILTime::unresolved();
259         result += parse.substring(3, 2).toUIntStrict(&ok) * 60;
260         if (!ok)
261             return SMILTime::unresolved();
262         result += parse.substring(6).toDouble(&ok);
263     } else if (doublePointOne == 2 && doublePointTwo == notFound && parse.length() >= 5) { 
264         result += parse.substring(0, 2).toUIntStrict(&ok) * 60;
265         if (!ok)
266             return SMILTime::unresolved();
267         result += parse.substring(3).toDouble(&ok);
268     } else
269         return parseOffsetValue(parse);
270
271     if (!ok)
272         return SMILTime::unresolved();
273     return result;
274 }
275     
276 static void sortTimeList(Vector<SMILTime>& timeList)
277 {
278     std::sort(timeList.begin(), timeList.end());
279 }
280     
281 bool SVGSMILElement::parseCondition(const String& value, BeginOrEnd beginOrEnd)
282 {
283     String parseString = value.stripWhiteSpace();
284     
285     double sign = 1.;
286     bool ok;
287     size_t pos = parseString.find('+');
288     if (pos == notFound) {
289         pos = parseString.find('-');
290         if (pos != notFound)
291             sign = -1.;
292     }
293     String conditionString;
294     SMILTime offset = 0;
295     if (pos == notFound)
296         conditionString = parseString;
297     else {
298         conditionString = parseString.left(pos).stripWhiteSpace();
299         String offsetString = parseString.substring(pos + 1).stripWhiteSpace();
300         offset = parseOffsetValue(offsetString);
301         if (offset.isUnresolved())
302             return false;
303         offset = offset * sign;
304     }
305     if (conditionString.isEmpty())
306         return false;
307     pos = conditionString.find('.');
308     
309     String baseID;
310     String nameString;
311     if (pos == notFound)
312         nameString = conditionString;
313     else {
314         baseID = conditionString.left(pos);
315         nameString = conditionString.substring(pos + 1);
316     }
317     if (nameString.isEmpty())
318         return false;
319
320     Condition::Type type;
321     int repeats = -1;
322     if (nameString.startsWith("repeat(") && nameString.endsWith(")")) {
323         // FIXME: For repeat events we just need to add the data carrying TimeEvent class and 
324         // fire the events at appropiate times.
325         repeats = nameString.substring(7, nameString.length() - 8).toUIntStrict(&ok);
326         if (!ok)
327             return false;
328         nameString = "repeat";
329         type = Condition::EventBase;
330     } else if (nameString == "begin" || nameString == "end") {
331         if (baseID.isEmpty())
332             return false;
333         type = Condition::Syncbase;
334     } else if (nameString.startsWith("accesskey(")) {
335         // FIXME: accesskey() support.
336         type = Condition::AccessKey;
337     } else
338         type = Condition::EventBase;
339     
340     m_conditions.append(Condition(type, beginOrEnd, baseID, nameString, offset, repeats));
341
342     if (type == Condition::EventBase && beginOrEnd == End)
343         m_hasEndEventConditions = true;
344
345     return true;
346 }
347
348 bool SVGSMILElement::isSMILElement(Node* node)
349 {
350     if (!node)
351         return false;
352     return node->hasTagName(SVGNames::setTag) || node->hasTagName(SVGNames::animateTag) || node->hasTagName(SVGNames::animateMotionTag)
353             || node->hasTagName(SVGNames::animateTransformTag) || node->hasTagName(SVGNames::animateColorTag);
354 }
355     
356 void SVGSMILElement::parseBeginOrEnd(const String& parseString, BeginOrEnd beginOrEnd)
357 {
358     Vector<SMILTime>& timeList = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
359     if (beginOrEnd == End)
360         m_hasEndEventConditions = false;
361     HashSet<double> existing;
362     for (unsigned n = 0; n < timeList.size(); ++n)
363         existing.add(timeList[n].value());
364     Vector<String> splitString;
365     parseString.split(';', splitString);
366     for (unsigned n = 0; n < splitString.size(); ++n) {
367         SMILTime value = parseClockValue(splitString[n]);
368         if (value.isUnresolved())
369             parseCondition(splitString[n], beginOrEnd);
370         else if (!existing.contains(value.value()))
371             timeList.append(value);
372     }
373     sortTimeList(timeList);
374 }
375
376 void SVGSMILElement::parseMappedAttribute(Attribute* attr)
377 {
378     if (attr->name() == SVGNames::beginAttr) {
379         if (!m_conditions.isEmpty()) {
380             disconnectConditions();
381             m_conditions.clear();
382             parseBeginOrEnd(getAttribute(SVGNames::endAttr), End);
383         }
384         parseBeginOrEnd(attr->value().string(), Begin);
385         if (inDocument())
386             connectConditions();
387     } else if (attr->name() == SVGNames::endAttr) {
388         if (!m_conditions.isEmpty()) {
389             disconnectConditions();
390             m_conditions.clear();
391             parseBeginOrEnd(getAttribute(SVGNames::beginAttr), Begin);
392         }
393         parseBeginOrEnd(attr->value().string(), End);
394         if (inDocument())
395             connectConditions();
396     } else
397         SVGElement::parseMappedAttribute(attr);
398 }
399
400 void SVGSMILElement::attributeChanged(Attribute* attr, bool preserveDecls)
401 {
402     SVGElement::attributeChanged(attr, preserveDecls);
403     
404     const QualifiedName& attrName = attr->name();
405     if (attrName == SVGNames::durAttr)
406         m_cachedDur = invalidCachedTime;
407     else if (attrName == SVGNames::repeatDurAttr)
408         m_cachedRepeatDur = invalidCachedTime;
409     else if (attrName == SVGNames::repeatCountAttr)
410         m_cachedRepeatCount = invalidCachedTime;
411     else if (attrName == SVGNames::minAttr)
412         m_cachedMin = invalidCachedTime;
413     else if (attrName == SVGNames::maxAttr)
414         m_cachedMax = invalidCachedTime;
415     else if (attrName == SVGNames::attributeNameAttr) {
416         if (inDocument())
417             m_attributeName = constructQualifiedName(this, attr->value());
418     }
419
420     if (inDocument()) {
421         if (attrName == SVGNames::beginAttr)
422             beginListChanged();
423         else if (attrName == SVGNames::endAttr)
424             endListChanged();
425     }
426 }
427
428 inline Element* SVGSMILElement::eventBaseFor(const Condition& condition) const
429 {
430     return condition.m_baseID.isEmpty() ? targetElement() : treeScope()->getElementById(condition.m_baseID);
431 }
432
433 void SVGSMILElement::connectConditions()
434 {
435     if (m_conditionsConnected)
436         disconnectConditions();
437     m_conditionsConnected = true;
438     for (unsigned n = 0; n < m_conditions.size(); ++n) {
439         Condition& condition = m_conditions[n];
440         if (condition.m_type == Condition::EventBase) {
441             ASSERT(!condition.m_syncbase);
442             Element* eventBase = eventBaseFor(condition);
443             if (!eventBase)
444                 continue;
445             ASSERT(!condition.m_eventListener);
446             condition.m_eventListener = ConditionEventListener::create(this, &condition);
447             eventBase->addEventListener(condition.m_name, condition.m_eventListener, false);
448         } else if (condition.m_type == Condition::Syncbase) {
449             ASSERT(!condition.m_baseID.isEmpty());
450             condition.m_syncbase = treeScope()->getElementById(condition.m_baseID);
451             if (!isSMILElement(condition.m_syncbase.get())) {
452                 condition.m_syncbase = 0;
453                 continue;
454             }
455             SVGSMILElement* syncbase = static_cast<SVGSMILElement*>(condition.m_syncbase.get());
456             syncbase->addTimeDependent(this);
457         }
458     }
459 }
460
461 void SVGSMILElement::disconnectConditions()
462 {
463     if (!m_conditionsConnected)
464         return;
465     m_conditionsConnected = false;
466     for (unsigned n = 0; n < m_conditions.size(); ++n) {
467         Condition& condition = m_conditions[n];
468         if (condition.m_type == Condition::EventBase) {
469             ASSERT(!condition.m_syncbase);
470             if (!condition.m_eventListener)
471                 continue;
472             // Note: It's a memory optimization to try to remove our condition
473             // event listener, but it's not guaranteed to work, since we have
474             // no guarantee that eventBaseFor() will be able to find our condition's
475             // original eventBase. So, we also have to disconnect ourselves from
476             // our condition event listener, in case it later fires.
477             Element* eventBase = eventBaseFor(condition);
478             if (eventBase)
479                 eventBase->removeEventListener(condition.m_name, condition.m_eventListener.get(), false);
480             condition.m_eventListener->disconnectAnimation();
481             condition.m_eventListener = 0;
482         } else if (condition.m_type == Condition::Syncbase) {
483             if (condition.m_syncbase) {
484                 ASSERT(isSMILElement(condition.m_syncbase.get()));
485                 static_cast<SVGSMILElement*>(condition.m_syncbase.get())->removeTimeDependent(this);
486             }
487         }
488         condition.m_syncbase = 0;
489     }
490 }
491
492 void SVGSMILElement::reschedule()
493 {
494     if (m_timeContainer)
495         m_timeContainer->schedule(this);
496 }
497
498 SVGElement* SVGSMILElement::targetElement() const
499 {
500     if (m_targetElement)
501         return m_targetElement;
502
503     String href = xlinkHref();
504     ContainerNode* target = href.isEmpty() ? parentNode() : treeScope()->getElementById(SVGURIReference::getTarget(href));
505     if (!target || !target->isSVGElement())
506         return 0;
507     
508     m_targetElement = static_cast<SVGElement*>(target);
509     document()->accessSVGExtensions()->addAnimationElementToTarget(const_cast<SVGSMILElement*>(this), m_targetElement);
510     return m_targetElement;
511 }
512
513 SMILTime SVGSMILElement::elapsed() const 
514 {
515     return m_timeContainer ? m_timeContainer->elapsed() : 0;
516
517     
518 bool SVGSMILElement::isInactive() const
519 {
520      return m_activeState == Inactive;
521 }
522
523 bool SVGSMILElement::isFrozen() const
524 {
525     return m_activeState == Frozen;
526 }
527     
528 SVGSMILElement::Restart SVGSMILElement::restart() const
529 {    
530     DEFINE_STATIC_LOCAL(const AtomicString, never, ("never"));
531     DEFINE_STATIC_LOCAL(const AtomicString, whenNotActive, ("whenNotActive"));
532     const AtomicString& value = getAttribute(SVGNames::restartAttr);
533     if (value == never)
534         return RestartNever;
535     if (value == whenNotActive)
536         return RestartWhenNotActive;
537     return RestartAlways;
538 }
539     
540 SVGSMILElement::FillMode SVGSMILElement::fill() const
541 {   
542     DEFINE_STATIC_LOCAL(const AtomicString, freeze, ("freeze"));
543     const AtomicString& value = getAttribute(SVGNames::fillAttr);
544     return value == freeze ? FillFreeze : FillRemove;
545 }
546     
547 String SVGSMILElement::xlinkHref() const
548 {    
549     return getAttribute(XLinkNames::hrefAttr);
550 }
551     
552 SMILTime SVGSMILElement::dur() const
553 {   
554     if (m_cachedDur != invalidCachedTime)
555         return m_cachedDur;
556     const AtomicString& value = getAttribute(SVGNames::durAttr);
557     SMILTime clockValue = parseClockValue(value);
558     return m_cachedDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
559 }
560
561 SMILTime SVGSMILElement::repeatDur() const
562 {    
563     if (m_cachedRepeatDur != invalidCachedTime)
564         return m_cachedRepeatDur;
565     const AtomicString& value = getAttribute(SVGNames::repeatDurAttr);
566     SMILTime clockValue = parseClockValue(value);
567     m_cachedRepeatDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
568     return m_cachedRepeatDur;
569 }
570     
571 // So a count is not really a time but let just all pretend we did not notice.
572 SMILTime SVGSMILElement::repeatCount() const
573 {    
574     if (m_cachedRepeatCount != invalidCachedTime)
575         return m_cachedRepeatCount;
576     const AtomicString& value = getAttribute(SVGNames::repeatCountAttr);
577     if (value.isNull())
578         return SMILTime::unresolved();
579
580     DEFINE_STATIC_LOCAL(const AtomicString, indefiniteValue, ("indefinite"));
581     if (value == indefiniteValue)
582         return SMILTime::indefinite();
583     bool ok;
584     double result = value.string().toDouble(&ok);
585     return m_cachedRepeatCount = ok && result > 0 ? result : SMILTime::unresolved();
586 }
587
588 SMILTime SVGSMILElement::maxValue() const
589 {    
590     if (m_cachedMax != invalidCachedTime)
591         return m_cachedMax;
592     const AtomicString& value = getAttribute(SVGNames::maxAttr);
593     SMILTime result = parseClockValue(value);
594     return m_cachedMax = (result.isUnresolved() || result < 0) ? SMILTime::indefinite() : result;
595 }
596     
597 SMILTime SVGSMILElement::minValue() const
598 {    
599     if (m_cachedMin != invalidCachedTime)
600         return m_cachedMin;
601     const AtomicString& value = getAttribute(SVGNames::minAttr);
602     SMILTime result = parseClockValue(value);
603     return m_cachedMin = (result.isUnresolved() || result < 0) ? 0 : result;
604 }
605                  
606 SMILTime SVGSMILElement::simpleDuration() const
607 {
608     return min(dur(), SMILTime::indefinite());
609 }
610     
611 void SVGSMILElement::addBeginTime(SMILTime time)
612 {
613     m_beginTimes.append(time);
614     sortTimeList(m_beginTimes);
615     beginListChanged();
616 }
617     
618 void SVGSMILElement::addEndTime(SMILTime time)
619 {
620     m_endTimes.append(time);
621     sortTimeList(m_endTimes);
622     endListChanged();
623 }
624     
625 SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
626 {
627     // FIXME: This searches from the beginning which is inefficient. The list is usually not long
628     // (one entry in common cases) but you can construct a case where it does grow.
629     const Vector<SMILTime>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
630     for (unsigned n = 0; n < list.size(); ++n) {
631         SMILTime time = list[n];
632         ASSERT(!time.isUnresolved());
633         if (time.isIndefinite() && beginOrEnd == Begin) {
634             // "The special value "indefinite" does not yield an instance time in the begin list."
635             continue;
636         }
637         if (equalsMinimumOK) {
638             if (time >= minimumTime)
639                 return time;
640         } else if (time > minimumTime)
641             return time;
642     }
643     return SMILTime::unresolved();
644 }
645
646 SMILTime SVGSMILElement::repeatingDuration() const
647 {
648     // Computing the active duration
649     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
650     SMILTime repeatCount = this->repeatCount();
651     SMILTime repeatDur = this->repeatDur();
652     SMILTime simpleDuration = this->simpleDuration();
653     if (!simpleDuration || (repeatDur.isUnresolved() && repeatCount.isUnresolved()))
654         return simpleDuration;
655     SMILTime repeatCountDuration = simpleDuration * repeatCount;
656     return min(repeatCountDuration, min(repeatDur, SMILTime::indefinite()));
657 }
658
659 SMILTime SVGSMILElement::resolveActiveEnd(SMILTime resolvedBegin, SMILTime resolvedEnd) const
660 {
661     // Computing the active duration
662     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
663     SMILTime preliminaryActiveDuration;
664     if (!resolvedEnd.isUnresolved() && dur().isUnresolved() && repeatDur().isUnresolved() && repeatCount().isUnresolved())
665         preliminaryActiveDuration = resolvedEnd - resolvedBegin;
666     else if (!resolvedEnd.isFinite())
667         preliminaryActiveDuration = repeatingDuration();
668     else
669         preliminaryActiveDuration = min(repeatingDuration(), resolvedEnd - resolvedBegin);
670     
671     SMILTime minValue = this->minValue();
672     SMILTime maxValue = this->maxValue();
673     if (minValue > maxValue) {
674         // Ignore both.
675         // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#MinMax
676         minValue = 0;
677         maxValue = SMILTime::indefinite();
678     }
679     return resolvedBegin + min(maxValue, max(minValue, preliminaryActiveDuration));
680 }
681
682 void SVGSMILElement::resolveInterval(bool first, SMILTime& beginResult, SMILTime& endResult) const
683 {
684     // See the pseudocode in
685     // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#Timing-BeginEnd-LifeCycle
686     SMILTime beginAfter = first ? -numeric_limits<double>::infinity() : m_intervalEnd;
687     SMILTime lastIntervalTempEnd = numeric_limits<double>::infinity();
688     while (true) {
689         SMILTime tempBegin = findInstanceTime(Begin, beginAfter, true);
690         if (tempBegin.isUnresolved())
691             break;
692         SMILTime tempEnd;
693         if (m_endTimes.isEmpty())
694             tempEnd = resolveActiveEnd(tempBegin, SMILTime::indefinite());
695         else {
696             tempEnd = findInstanceTime(End, tempBegin, true);
697             if ((first && tempBegin == tempEnd && tempEnd == lastIntervalTempEnd) || (!first && tempEnd == m_intervalEnd)) 
698                 tempEnd = findInstanceTime(End, tempBegin, false);    
699             if (tempEnd.isUnresolved()) {
700                 if (!m_endTimes.isEmpty() && !m_hasEndEventConditions)
701                     break;
702             }
703             tempEnd = resolveActiveEnd(tempBegin, tempEnd);
704         }
705         if (tempEnd > 0 || !first) {
706             beginResult = tempBegin;
707             endResult = tempEnd;
708             return;
709         }
710         if (restart() == RestartNever)
711             break;
712
713         beginAfter = tempEnd;
714         lastIntervalTempEnd = tempEnd;
715     }
716     beginResult = SMILTime::unresolved();
717     endResult = SMILTime::unresolved();
718 }
719     
720 void SVGSMILElement::resolveFirstInterval()
721 {
722     SMILTime begin;
723     SMILTime end;
724     resolveInterval(true, begin, end);
725     ASSERT(!begin.isIndefinite());
726
727     if (!begin.isUnresolved() && (begin != m_intervalBegin || end != m_intervalEnd)) {   
728         bool wasUnresolved = m_intervalBegin.isUnresolved();
729         m_intervalBegin = begin;
730         m_intervalEnd = end;
731         notifyDependentsIntervalChanged(wasUnresolved ? NewInterval : ExistingInterval);
732         m_nextProgressTime = min(m_nextProgressTime, m_intervalBegin);
733         reschedule();
734     }
735 }
736
737 void SVGSMILElement::resolveNextInterval()
738 {
739     SMILTime begin;
740     SMILTime end;
741     resolveInterval(false, begin, end);
742     ASSERT(!begin.isIndefinite());
743     
744     if (!begin.isUnresolved() && begin != m_intervalBegin) {
745         m_intervalBegin = begin;
746         m_intervalEnd = end;
747         notifyDependentsIntervalChanged(NewInterval);
748         m_nextProgressTime = min(m_nextProgressTime, m_intervalBegin);
749     }
750 }
751
752 SMILTime SVGSMILElement::nextProgressTime() const
753 {
754     return m_nextProgressTime;
755 }
756     
757 void SVGSMILElement::beginListChanged()
758 {
759     SMILTime elapsed = this->elapsed();
760     if (m_isWaitingForFirstInterval)
761         resolveFirstInterval();
762     else if (elapsed < m_intervalBegin) {
763         SMILTime newBegin = findInstanceTime(Begin, elapsed, false);
764         if (newBegin < m_intervalBegin) {
765             // Begin time changed, re-resolve the interval.
766             SMILTime oldBegin = m_intervalBegin;
767             m_intervalBegin = elapsed;
768             resolveInterval(false, m_intervalBegin, m_intervalEnd);  
769             ASSERT(!m_intervalBegin.isUnresolved());
770             if (m_intervalBegin != oldBegin)
771                 notifyDependentsIntervalChanged(ExistingInterval);
772         }
773     }
774     m_nextProgressTime = elapsed;
775     reschedule();
776 }
777
778 void SVGSMILElement::endListChanged()
779 {
780     SMILTime elapsed = this->elapsed();
781     if (m_isWaitingForFirstInterval)
782         resolveFirstInterval();
783     else if (elapsed < m_intervalEnd && m_intervalBegin.isFinite()) {
784         SMILTime newEnd = findInstanceTime(End, m_intervalBegin, false);
785         if (newEnd < m_intervalEnd) {
786             newEnd = resolveActiveEnd(m_intervalBegin, newEnd);
787             if (newEnd != m_intervalEnd) {
788                 m_intervalEnd = newEnd;
789                 notifyDependentsIntervalChanged(ExistingInterval);
790             }
791         }
792     }
793     m_nextProgressTime = elapsed;
794     reschedule();
795 }
796     
797 void SVGSMILElement::checkRestart(SMILTime elapsed)
798 {
799     ASSERT(!m_isWaitingForFirstInterval);
800     ASSERT(elapsed >= m_intervalBegin);
801     
802     Restart restart = this->restart();
803     if (restart == RestartNever)
804         return;
805     
806     if (elapsed < m_intervalEnd) {
807         if (restart != RestartAlways)
808             return;
809         SMILTime nextBegin = findInstanceTime(Begin, m_intervalBegin, false);
810         if (nextBegin < m_intervalEnd) { 
811             m_intervalEnd = nextBegin;
812             notifyDependentsIntervalChanged(ExistingInterval);
813         }
814     } 
815     if (elapsed >= m_intervalEnd)
816         resolveNextInterval();
817 }
818     
819 float SVGSMILElement::calculateAnimationPercentAndRepeat(SMILTime elapsed, unsigned& repeat) const
820 {
821     SMILTime simpleDuration = this->simpleDuration();
822     repeat = 0;
823     if (simpleDuration.isIndefinite()) {
824         repeat = 0;
825         return 0.f;
826     }
827     if (!simpleDuration) {
828         repeat = 0;
829         return 1.f;
830     }
831     ASSERT(m_intervalBegin.isFinite());
832     ASSERT(simpleDuration.isFinite());
833     SMILTime activeTime = elapsed - m_intervalBegin;
834     SMILTime repeatingDuration = this->repeatingDuration();
835     if (elapsed >= m_intervalEnd || activeTime > repeatingDuration) {
836         repeat = static_cast<unsigned>(repeatingDuration.value() / simpleDuration.value());
837         if (fmod(repeatingDuration.value(), !simpleDuration.value()))
838             repeat--;
839         return 1.f;
840     }
841     repeat = static_cast<unsigned>(activeTime.value() / simpleDuration.value());
842     SMILTime simpleTime = fmod(activeTime.value(), simpleDuration.value());
843     return narrowPrecisionToFloat(simpleTime.value() / simpleDuration.value());
844 }
845     
846 SMILTime SVGSMILElement::calculateNextProgressTime(SMILTime elapsed) const
847 {
848     if (m_activeState == Active) {
849         // If duration is indefinite the value does not actually change over time. Same is true for <set>.
850         SMILTime simpleDuration = this->simpleDuration();
851         if (simpleDuration.isIndefinite() || hasTagName(SVGNames::setTag)) {
852             SMILTime repeatingDurationEnd = m_intervalBegin + repeatingDuration();
853             // We are supposed to do freeze semantics when repeating ends, even if the element is still active. 
854             // Take care that we get a timer callback at that point.
855             if (elapsed < repeatingDurationEnd && repeatingDurationEnd < m_intervalEnd && repeatingDurationEnd.isFinite())
856                 return repeatingDurationEnd;
857             return m_intervalEnd;
858         } 
859         return elapsed + 0.025;
860     }
861     return m_intervalBegin >= elapsed ? m_intervalBegin : SMILTime::unresolved();
862 }
863     
864 SVGSMILElement::ActiveState SVGSMILElement::determineActiveState(SMILTime elapsed) const
865 {
866     if (elapsed >= m_intervalBegin && elapsed < m_intervalEnd)
867         return Active;
868
869     if (m_activeState == Active)
870         return fill() == FillFreeze ? Frozen : Inactive;
871
872     return m_activeState;
873 }
874     
875 bool SVGSMILElement::isContributing(SMILTime elapsed) const 
876
877     // Animation does not contribute during the active time if it is past its repeating duration and has fill=remove.
878     return (m_activeState == Active && (fill() == FillFreeze || elapsed <= m_intervalBegin + repeatingDuration())) || m_activeState == Frozen;
879 }
880     
881 void SVGSMILElement::progress(SMILTime elapsed, SVGSMILElement* resultElement)
882 {
883     ASSERT(m_timeContainer);
884     ASSERT(m_isWaitingForFirstInterval || m_intervalBegin.isFinite());
885     
886     if (!m_conditionsConnected)
887         connectConditions();
888     
889     if (!m_intervalBegin.isFinite()) {
890         ASSERT(m_activeState == Inactive);
891         m_nextProgressTime = SMILTime::unresolved();
892         return;
893     }
894     
895     if (elapsed < m_intervalBegin) {
896         ASSERT(m_activeState != Active);
897         if (m_activeState == Frozen && resultElement)
898             updateAnimation(m_lastPercent, m_lastRepeat, resultElement);
899         m_nextProgressTime = m_intervalBegin;
900         return;
901     }
902     
903     m_previousIntervalBegin = m_intervalBegin;
904     
905     if (m_activeState == Inactive) {
906         m_isWaitingForFirstInterval = false;
907         m_activeState = Active;
908         startedActiveInterval();
909     }
910     
911     unsigned repeat;
912     float percent = calculateAnimationPercentAndRepeat(elapsed, repeat);
913
914     checkRestart(elapsed);
915
916     ActiveState oldActiveState = m_activeState;
917     m_activeState = determineActiveState(elapsed);
918     
919     if (isContributing(elapsed)) {
920         if (resultElement)
921             updateAnimation(percent, repeat, resultElement);
922         m_lastPercent = percent;
923         m_lastRepeat = repeat;
924     }
925
926     if (oldActiveState == Active && m_activeState != Active)
927         endedActiveInterval();
928
929     m_nextProgressTime = calculateNextProgressTime(elapsed);
930 }
931     
932 void SVGSMILElement::notifyDependentsIntervalChanged(NewOrExistingInterval newOrExisting)
933 {
934     ASSERT(m_intervalBegin.isFinite());
935     DEFINE_STATIC_LOCAL(HashSet<SVGSMILElement*>, loopBreaker, ());
936     if (loopBreaker.contains(this))
937         return;
938     loopBreaker.add(this);
939     
940     TimeDependentSet::iterator end = m_timeDependents.end();
941     for (TimeDependentSet::iterator it = m_timeDependents.begin(); it != end; ++it) {
942         SVGSMILElement* dependent = *it;
943         dependent->createInstanceTimesFromSyncbase(this, newOrExisting);
944     }
945
946     loopBreaker.remove(this);
947 }
948     
949 void SVGSMILElement::createInstanceTimesFromSyncbase(SVGSMILElement* syncbase, NewOrExistingInterval)
950 {
951     // FIXME: To be really correct, this should handle updating exising interval by changing 
952     // the associated times instead of creating new ones.
953     for (unsigned n = 0; n < m_conditions.size(); ++n) {
954         Condition& condition = m_conditions[n];
955         if (condition.m_type == Condition::Syncbase && condition.m_syncbase == syncbase) {
956             ASSERT(condition.m_name == "begin" || condition.m_name == "end");
957             // No nested time containers in SVG, no need for crazy time space conversions. Phew!
958             SMILTime time = 0;
959             if (condition.m_name == "begin")
960                 time = syncbase->m_intervalBegin + condition.m_offset;
961             else
962                 time = syncbase->m_intervalEnd + condition.m_offset;
963             ASSERT(time.isFinite());
964             if (condition.m_beginOrEnd == Begin)
965                 addBeginTime(time);
966             else
967                 addEndTime(time);
968         }
969     }
970 }
971     
972 void SVGSMILElement::addTimeDependent(SVGSMILElement* animation)
973 {
974     m_timeDependents.add(animation);
975     if (m_intervalBegin.isFinite())
976         animation->createInstanceTimesFromSyncbase(this, NewInterval);
977 }
978     
979 void SVGSMILElement::removeTimeDependent(SVGSMILElement* animation)
980 {
981     m_timeDependents.remove(animation);
982 }
983     
984 void SVGSMILElement::handleConditionEvent(Event*, Condition* condition)
985 {
986     if (condition->m_beginOrEnd == Begin)
987         addBeginTime(elapsed() + condition->m_offset);
988     else
989         addEndTime(elapsed() + condition->m_offset);
990 }
991
992 void SVGSMILElement::beginByLinkActivation()
993 {
994     addBeginTime(elapsed());
995 }
996     
997 }
998
999 #endif