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