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