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