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