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