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