Integrate SVGUseElement within the new shadow root concept
[WebKit-https.git] / Source / WebCore / svg / animation / SVGSMILElement.cpp
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27
28 #if ENABLE(SVG)
29 #include "SVGSMILElement.h"
30
31 #include "Attribute.h"
32 #include "CSSPropertyNames.h"
33 #include "Document.h"
34 #include "Event.h"
35 #include "EventListener.h"
36 #include "FloatConversion.h"
37 #include "FrameView.h"
38 #include "HTMLNames.h"
39 #include "SMILTimeContainer.h"
40 #include "SVGDocumentExtensions.h"
41 #include "SVGNames.h"
42 #include "SVGParserUtilities.h"
43 #include "SVGSVGElement.h"
44 #include "SVGURIReference.h"
45 #include "XLinkNames.h"
46 #include <wtf/MathExtras.h>
47 #include <wtf/StdLibExtras.h>
48 #include <wtf/Vector.h>
49
50 using namespace std;
51
52 namespace WebCore {
53     
54 // This is used for duration type time values that can't be negative.
55 static const double invalidCachedTime = -1.;
56     
57 class ConditionEventListener : public EventListener {
58 public:
59     static PassRefPtr<ConditionEventListener> create(SVGSMILElement* animation, SVGSMILElement::Condition* condition)
60     {
61         return adoptRef(new ConditionEventListener(animation, condition));
62     }
63
64     static const ConditionEventListener* cast(const EventListener* listener)
65     {
66         return listener->type() == ConditionEventListenerType
67             ? static_cast<const ConditionEventListener*>(listener)
68             : 0;
69     }
70
71     virtual bool operator==(const EventListener& other);
72     
73     void disconnectAnimation()
74     {
75         m_animation = 0;
76     }
77
78 private:
79     ConditionEventListener(SVGSMILElement* animation, SVGSMILElement::Condition* condition) 
80         : EventListener(ConditionEventListenerType)
81         , m_animation(animation)
82         , m_condition(condition) 
83     {
84     }
85
86     virtual void handleEvent(ScriptExecutionContext*, Event*);
87
88     SVGSMILElement* m_animation;
89     SVGSMILElement::Condition* m_condition;
90 };
91
92 bool ConditionEventListener::operator==(const EventListener& listener)
93 {
94     if (const ConditionEventListener* conditionEventListener = ConditionEventListener::cast(&listener))
95         return m_animation == conditionEventListener->m_animation && m_condition == conditionEventListener->m_condition;
96     return false;
97 }
98
99 void ConditionEventListener::handleEvent(ScriptExecutionContext*, Event* event) 
100 {
101     if (!m_animation)
102         return;
103     m_animation->handleConditionEvent(event, m_condition);
104 }
105
106 SVGSMILElement::Condition::Condition(Type type, BeginOrEnd beginOrEnd, const String& baseID, const String& name, SMILTime offset, int repeats)
107     : m_type(type)
108     , m_beginOrEnd(beginOrEnd)
109     , m_baseID(baseID)
110     , m_name(name)
111     , m_offset(offset)
112     , m_repeats(repeats) 
113 {
114 }
115     
116 SVGSMILElement::SVGSMILElement(const QualifiedName& tagName, Document* doc)
117     : SVGElement(tagName, doc)
118     , m_attributeName(anyQName())
119     , m_targetElement(0)
120     , m_conditionsConnected(false)
121     , m_hasEndEventConditions(false)
122     , m_isWaitingForFirstInterval(true)
123     , m_intervalBegin(SMILTime::unresolved())
124     , m_intervalEnd(SMILTime::unresolved())
125     , m_previousIntervalBegin(SMILTime::unresolved())
126     , m_activeState(Inactive)
127     , m_lastPercent(0)
128     , m_lastRepeat(0)
129     , m_nextProgressTime(0)
130     , m_documentOrderIndex(0)
131     , m_cachedDur(invalidCachedTime)
132     , m_cachedRepeatDur(invalidCachedTime)
133     , m_cachedRepeatCount(invalidCachedTime)
134     , m_cachedMin(invalidCachedTime)
135     , m_cachedMax(invalidCachedTime)
136 {
137     resolveFirstInterval();
138 }
139
140 SVGSMILElement::~SVGSMILElement()
141 {
142     disconnectConditions();
143     if (m_timeContainer)
144         m_timeContainer->unschedule(this);
145     if (m_targetElement)
146         document()->accessSVGExtensions()->removeAnimationElementFromTarget(this, m_targetElement);
147 }
148
149 static inline QualifiedName constructQualifiedName(const SVGElement* svgElement, const String& attributeName)
150 {
151     ASSERT(svgElement);
152     if (attributeName.isEmpty())
153         return anyQName();
154     if (!attributeName.contains(':'))
155         return QualifiedName(nullAtom, attributeName, nullAtom);
156     
157     String prefix;
158     String localName;
159     ExceptionCode ec = 0;
160     if (!Document::parseQualifiedName(attributeName, prefix, localName, ec))
161         return anyQName();
162     ASSERT(!ec);
163     
164     String namespaceURI = svgElement->lookupNamespaceURI(prefix);    
165     if (namespaceURI.isEmpty())
166         return anyQName();
167     
168     return QualifiedName(nullAtom, localName, namespaceURI);
169 }
170
171 static inline void clearTimesWithDynamicOrigins(Vector<SMILTimeWithOrigin>& timeList)
172 {
173     for (int i = timeList.size() - 1; i >= 0; --i) {
174         if (timeList[i].originIsScript())
175             timeList.remove(i);
176     }
177 }
178
179 void SVGSMILElement::reset()
180 {
181     m_activeState = Inactive;
182     m_isWaitingForFirstInterval = true;
183     m_intervalBegin = SMILTime::unresolved();
184     m_intervalEnd = SMILTime::unresolved();
185     m_previousIntervalBegin = SMILTime::unresolved();
186     m_lastPercent = 0;
187     m_lastRepeat = 0;
188     m_nextProgressTime = 0;
189     resolveFirstInterval();
190 }
191
192 void SVGSMILElement::insertedIntoDocument()
193 {
194     SVGElement::insertedIntoDocument();
195
196     // Verify we are not in <use> instance tree.
197     ASSERT(!isInShadowTree());
198
199     m_attributeName = constructQualifiedName(this, fastGetAttribute(SVGNames::attributeNameAttr));
200     SVGSVGElement* owner = ownerSVGElement();
201     if (!owner)
202         return;
203     m_timeContainer = owner->timeContainer();
204     ASSERT(m_timeContainer);
205     m_timeContainer->setDocumentOrderIndexesDirty();
206
207     // "If no attribute is present, the default begin value (an offset-value of 0) must be evaluated."
208     if (!fastHasAttribute(SVGNames::beginAttr))
209         m_beginTimes.append(SMILTimeWithOrigin());
210
211     if (m_isWaitingForFirstInterval) {
212         resolveFirstInterval();
213         reschedule();
214     }
215 }
216
217 void SVGSMILElement::removedFromDocument()
218 {
219     m_attributeName = anyQName();
220     if (m_timeContainer) {
221         m_timeContainer->unschedule(this);
222         m_timeContainer = 0;
223     }
224     if (m_targetElement) {
225         document()->accessSVGExtensions()->removeAnimationElementFromTarget(this, m_targetElement);
226         m_targetElement = 0;
227     }
228     // Calling disconnectConditions() may kill us if there are syncbase conditions.
229     // OK, but we don't want to die inside the call.
230     RefPtr<SVGSMILElement> keepAlive(this);
231     disconnectConditions();
232     SVGElement::removedFromDocument();
233 }
234    
235 SMILTime SVGSMILElement::parseOffsetValue(const String& data)
236 {
237     bool ok;
238     double result = 0;
239     String parse = data.stripWhiteSpace();
240     if (parse.endsWith("h"))
241         result = parse.left(parse.length() - 1).toDouble(&ok) * 60 * 60;
242     else if (parse.endsWith("min"))
243         result = parse.left(parse.length() - 3).toDouble(&ok) * 60;
244     else if (parse.endsWith("ms"))
245         result = parse.left(parse.length() - 2).toDouble(&ok) / 1000;
246     else if (parse.endsWith("s"))
247         result = parse.left(parse.length() - 1).toDouble(&ok);
248     else
249         result = parse.toDouble(&ok);
250     if (!ok)
251         return SMILTime::unresolved();
252     return result;
253 }
254     
255 SMILTime SVGSMILElement::parseClockValue(const String& data)
256 {
257     if (data.isNull())
258         return SMILTime::unresolved();
259     
260     String parse = data.stripWhiteSpace();
261
262     DEFINE_STATIC_LOCAL(const AtomicString, indefiniteValue, ("indefinite"));
263     if (parse == indefiniteValue)
264         return SMILTime::indefinite();
265
266     double result = 0;
267     bool ok;
268     size_t doublePointOne = parse.find(':');
269     size_t doublePointTwo = parse.find(':', doublePointOne + 1);
270     if (doublePointOne == 2 && doublePointTwo == 5 && parse.length() >= 8) { 
271         result += parse.substring(0, 2).toUIntStrict(&ok) * 60 * 60;
272         if (!ok)
273             return SMILTime::unresolved();
274         result += parse.substring(3, 2).toUIntStrict(&ok) * 60;
275         if (!ok)
276             return SMILTime::unresolved();
277         result += parse.substring(6).toDouble(&ok);
278     } else if (doublePointOne == 2 && doublePointTwo == notFound && parse.length() >= 5) { 
279         result += parse.substring(0, 2).toUIntStrict(&ok) * 60;
280         if (!ok)
281             return SMILTime::unresolved();
282         result += parse.substring(3).toDouble(&ok);
283     } else
284         return parseOffsetValue(parse);
285
286     if (!ok)
287         return SMILTime::unresolved();
288     return result;
289 }
290     
291 static void sortTimeList(Vector<SMILTimeWithOrigin>& timeList)
292 {
293     std::sort(timeList.begin(), timeList.end());
294 }
295     
296 bool SVGSMILElement::parseCondition(const String& value, BeginOrEnd beginOrEnd)
297 {
298     String parseString = value.stripWhiteSpace();
299     
300     double sign = 1.;
301     bool ok;
302     size_t pos = parseString.find('+');
303     if (pos == notFound) {
304         pos = parseString.find('-');
305         if (pos != notFound)
306             sign = -1.;
307     }
308     String conditionString;
309     SMILTime offset = 0;
310     if (pos == notFound)
311         conditionString = parseString;
312     else {
313         conditionString = parseString.left(pos).stripWhiteSpace();
314         String offsetString = parseString.substring(pos + 1).stripWhiteSpace();
315         offset = parseOffsetValue(offsetString);
316         if (offset.isUnresolved())
317             return false;
318         offset = offset * sign;
319     }
320     if (conditionString.isEmpty())
321         return false;
322     pos = conditionString.find('.');
323     
324     String baseID;
325     String nameString;
326     if (pos == notFound)
327         nameString = conditionString;
328     else {
329         baseID = conditionString.left(pos);
330         nameString = conditionString.substring(pos + 1);
331     }
332     if (nameString.isEmpty())
333         return false;
334
335     Condition::Type type;
336     int repeats = -1;
337     if (nameString.startsWith("repeat(") && nameString.endsWith(")")) {
338         // FIXME: For repeat events we just need to add the data carrying TimeEvent class and 
339         // fire the events at appropiate times.
340         repeats = nameString.substring(7, nameString.length() - 8).toUIntStrict(&ok);
341         if (!ok)
342             return false;
343         nameString = "repeat";
344         type = Condition::EventBase;
345     } else if (nameString == "begin" || nameString == "end") {
346         if (baseID.isEmpty())
347             return false;
348         type = Condition::Syncbase;
349     } else if (nameString.startsWith("accesskey(")) {
350         // FIXME: accesskey() support.
351         type = Condition::AccessKey;
352     } else
353         type = Condition::EventBase;
354     
355     m_conditions.append(Condition(type, beginOrEnd, baseID, nameString, offset, repeats));
356
357     if (type == Condition::EventBase && beginOrEnd == End)
358         m_hasEndEventConditions = true;
359
360     return true;
361 }
362
363 bool SVGSMILElement::isSMILElement(Node* node)
364 {
365     if (!node)
366         return false;
367     return node->hasTagName(SVGNames::setTag) || node->hasTagName(SVGNames::animateTag) || node->hasTagName(SVGNames::animateMotionTag)
368             || node->hasTagName(SVGNames::animateTransformTag) || node->hasTagName(SVGNames::animateColorTag);
369 }
370     
371 void SVGSMILElement::parseBeginOrEnd(const String& parseString, BeginOrEnd beginOrEnd)
372 {
373     Vector<SMILTimeWithOrigin>& timeList = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
374     if (beginOrEnd == End)
375         m_hasEndEventConditions = false;
376     HashSet<double> existing;
377     for (unsigned n = 0; n < timeList.size(); ++n)
378         existing.add(timeList[n].time().value());
379     Vector<String> splitString;
380     parseString.split(';', splitString);
381     for (unsigned n = 0; n < splitString.size(); ++n) {
382         SMILTime value = parseClockValue(splitString[n]);
383         if (value.isUnresolved())
384             parseCondition(splitString[n], beginOrEnd);
385         else if (!existing.contains(value.value()))
386             timeList.append(SMILTimeWithOrigin(value, SMILTimeWithOrigin::ParserOrigin));
387     }
388     sortTimeList(timeList);
389 }
390
391 void SVGSMILElement::parseAttribute(Attribute* attr)
392 {
393     if (attr->name() == SVGNames::beginAttr) {
394         if (!m_conditions.isEmpty()) {
395             disconnectConditions();
396             m_conditions.clear();
397             parseBeginOrEnd(fastGetAttribute(SVGNames::endAttr), End);
398         }
399         parseBeginOrEnd(attr->value().string(), Begin);
400         if (inDocument())
401             connectConditions();
402     } else if (attr->name() == SVGNames::endAttr) {
403         if (!m_conditions.isEmpty()) {
404             disconnectConditions();
405             m_conditions.clear();
406             parseBeginOrEnd(fastGetAttribute(SVGNames::beginAttr), Begin);
407         }
408         parseBeginOrEnd(attr->value().string(), End);
409         if (inDocument())
410             connectConditions();
411     } else
412         SVGElement::parseAttribute(attr);
413 }
414
415 void SVGSMILElement::attributeChanged(Attribute* attr)
416 {
417     SVGElement::attributeChanged(attr);
418
419     const QualifiedName& attrName = attr->name();
420     if (attrName == SVGNames::durAttr)
421         m_cachedDur = invalidCachedTime;
422     else if (attrName == SVGNames::repeatDurAttr)
423         m_cachedRepeatDur = invalidCachedTime;
424     else if (attrName == SVGNames::repeatCountAttr)
425         m_cachedRepeatCount = invalidCachedTime;
426     else if (attrName == SVGNames::minAttr)
427         m_cachedMin = invalidCachedTime;
428     else if (attrName == SVGNames::maxAttr)
429         m_cachedMax = invalidCachedTime;
430     else if (attrName == SVGNames::attributeNameAttr) {
431         if (inDocument())
432             m_attributeName = constructQualifiedName(this, attr->value());
433     }
434
435     if (inDocument()) {
436         if (attrName == SVGNames::beginAttr)
437             beginListChanged(elapsed());
438         else if (attrName == SVGNames::endAttr)
439             endListChanged(elapsed());
440     }
441 }
442
443 inline Element* SVGSMILElement::eventBaseFor(const Condition& condition)
444 {
445     return condition.m_baseID.isEmpty() ? targetElement() : treeScope()->getElementById(condition.m_baseID);
446 }
447
448 void SVGSMILElement::connectConditions()
449 {
450     if (m_conditionsConnected)
451         disconnectConditions();
452     m_conditionsConnected = true;
453     for (unsigned n = 0; n < m_conditions.size(); ++n) {
454         Condition& condition = m_conditions[n];
455         if (condition.m_type == Condition::EventBase) {
456             ASSERT(!condition.m_syncbase);
457             Element* eventBase = eventBaseFor(condition);
458             if (!eventBase)
459                 continue;
460             ASSERT(!condition.m_eventListener);
461             condition.m_eventListener = ConditionEventListener::create(this, &condition);
462             eventBase->addEventListener(condition.m_name, condition.m_eventListener, false);
463         } else if (condition.m_type == Condition::Syncbase) {
464             ASSERT(!condition.m_baseID.isEmpty());
465             condition.m_syncbase = treeScope()->getElementById(condition.m_baseID);
466             if (!isSMILElement(condition.m_syncbase.get())) {
467                 condition.m_syncbase = 0;
468                 continue;
469             }
470             SVGSMILElement* syncbase = static_cast<SVGSMILElement*>(condition.m_syncbase.get());
471             syncbase->addTimeDependent(this);
472         }
473     }
474 }
475
476 void SVGSMILElement::disconnectConditions()
477 {
478     if (!m_conditionsConnected)
479         return;
480     m_conditionsConnected = false;
481     for (unsigned n = 0; n < m_conditions.size(); ++n) {
482         Condition& condition = m_conditions[n];
483         if (condition.m_type == Condition::EventBase) {
484             ASSERT(!condition.m_syncbase);
485             if (!condition.m_eventListener)
486                 continue;
487             // Note: It's a memory optimization to try to remove our condition
488             // event listener, but it's not guaranteed to work, since we have
489             // no guarantee that eventBaseFor() will be able to find our condition's
490             // original eventBase. So, we also have to disconnect ourselves from
491             // our condition event listener, in case it later fires.
492             Element* eventBase = eventBaseFor(condition);
493             if (eventBase)
494                 eventBase->removeEventListener(condition.m_name, condition.m_eventListener.get(), false);
495             condition.m_eventListener->disconnectAnimation();
496             condition.m_eventListener = 0;
497         } else if (condition.m_type == Condition::Syncbase) {
498             if (condition.m_syncbase) {
499                 ASSERT(isSMILElement(condition.m_syncbase.get()));
500                 static_cast<SVGSMILElement*>(condition.m_syncbase.get())->removeTimeDependent(this);
501             }
502         }
503         condition.m_syncbase = 0;
504     }
505 }
506
507 void SVGSMILElement::reschedule()
508 {
509     if (m_timeContainer)
510         m_timeContainer->schedule(this);
511 }
512
513 SVGElement* SVGSMILElement::targetElement()
514 {
515     if (m_targetElement)
516         return m_targetElement;
517
518     String href = xlinkHref();
519     ContainerNode* target = href.isEmpty() ? parentNode() : SVGURIReference::targetElementFromIRIString(href, document());
520     if (!target || !target->isSVGElement())
521         return 0;
522
523     m_targetElement = static_cast<SVGElement*>(target);
524     document()->accessSVGExtensions()->addAnimationElementToTarget(this, m_targetElement);
525
526     targetElementDidChange(m_targetElement);
527
528     return m_targetElement;
529 }
530
531 void SVGSMILElement::resetTargetElement()
532 {
533     m_targetElement = 0;
534
535     // Force the animation to recompute values that are only calculated when an animation becomes active.
536     // Failing to do this means that a target reset and change during active animation may result in
537     // invalid state.
538     m_activeState = Inactive;
539
540     targetElementDidChange(0);
541 }
542
543 SMILTime SVGSMILElement::elapsed() const
544 {
545     return m_timeContainer ? m_timeContainer->elapsed() : 0;
546 }
547
548 bool SVGSMILElement::isInactive() const
549 {
550      return m_activeState == Inactive;
551 }
552
553 bool SVGSMILElement::isFrozen() const
554 {
555     return m_activeState == Frozen;
556 }
557     
558 SVGSMILElement::Restart SVGSMILElement::restart() const
559 {    
560     DEFINE_STATIC_LOCAL(const AtomicString, never, ("never"));
561     DEFINE_STATIC_LOCAL(const AtomicString, whenNotActive, ("whenNotActive"));
562     const AtomicString& value = fastGetAttribute(SVGNames::restartAttr);
563     if (value == never)
564         return RestartNever;
565     if (value == whenNotActive)
566         return RestartWhenNotActive;
567     return RestartAlways;
568 }
569     
570 SVGSMILElement::FillMode SVGSMILElement::fill() const
571 {   
572     DEFINE_STATIC_LOCAL(const AtomicString, freeze, ("freeze"));
573     const AtomicString& value = fastGetAttribute(SVGNames::fillAttr);
574     return value == freeze ? FillFreeze : FillRemove;
575 }
576     
577 String SVGSMILElement::xlinkHref() const
578 {    
579     return getAttribute(XLinkNames::hrefAttr);
580 }
581     
582 SMILTime SVGSMILElement::dur() const
583 {   
584     if (m_cachedDur != invalidCachedTime)
585         return m_cachedDur;
586     const AtomicString& value = fastGetAttribute(SVGNames::durAttr);
587     SMILTime clockValue = parseClockValue(value);
588     return m_cachedDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
589 }
590
591 SMILTime SVGSMILElement::repeatDur() const
592 {    
593     if (m_cachedRepeatDur != invalidCachedTime)
594         return m_cachedRepeatDur;
595     const AtomicString& value = fastGetAttribute(SVGNames::repeatDurAttr);
596     SMILTime clockValue = parseClockValue(value);
597     m_cachedRepeatDur = clockValue <= 0 ? SMILTime::unresolved() : clockValue;
598     return m_cachedRepeatDur;
599 }
600     
601 // So a count is not really a time but let just all pretend we did not notice.
602 SMILTime SVGSMILElement::repeatCount() const
603 {    
604     if (m_cachedRepeatCount != invalidCachedTime)
605         return m_cachedRepeatCount;
606     const AtomicString& value = fastGetAttribute(SVGNames::repeatCountAttr);
607     if (value.isNull())
608         return SMILTime::unresolved();
609
610     DEFINE_STATIC_LOCAL(const AtomicString, indefiniteValue, ("indefinite"));
611     if (value == indefiniteValue)
612         return SMILTime::indefinite();
613     bool ok;
614     double result = value.string().toDouble(&ok);
615     return m_cachedRepeatCount = ok && result > 0 ? result : SMILTime::unresolved();
616 }
617
618 SMILTime SVGSMILElement::maxValue() const
619 {    
620     if (m_cachedMax != invalidCachedTime)
621         return m_cachedMax;
622     const AtomicString& value = fastGetAttribute(SVGNames::maxAttr);
623     SMILTime result = parseClockValue(value);
624     return m_cachedMax = (result.isUnresolved() || result < 0) ? SMILTime::indefinite() : result;
625 }
626     
627 SMILTime SVGSMILElement::minValue() const
628 {    
629     if (m_cachedMin != invalidCachedTime)
630         return m_cachedMin;
631     const AtomicString& value = fastGetAttribute(SVGNames::minAttr);
632     SMILTime result = parseClockValue(value);
633     return m_cachedMin = (result.isUnresolved() || result < 0) ? 0 : result;
634 }
635                  
636 SMILTime SVGSMILElement::simpleDuration() const
637 {
638     return min(dur(), SMILTime::indefinite());
639 }
640
641 void SVGSMILElement::addBeginTime(SMILTime eventTime, SMILTime beginTime, SMILTimeWithOrigin::Origin origin)
642 {
643     m_beginTimes.append(SMILTimeWithOrigin(beginTime, origin));
644     sortTimeList(m_beginTimes);
645     beginListChanged(eventTime);
646 }
647
648 void SVGSMILElement::addEndTime(SMILTime eventTime, SMILTime endTime, SMILTimeWithOrigin::Origin origin)
649 {
650     m_endTimes.append(SMILTimeWithOrigin(endTime, origin));
651     sortTimeList(m_endTimes);
652     endListChanged(eventTime);
653 }
654
655 inline SMILTime extractTimeFromVector(const SMILTimeWithOrigin* position)
656 {
657     return position->time();
658 }
659
660 SMILTime SVGSMILElement::findInstanceTime(BeginOrEnd beginOrEnd, SMILTime minimumTime, bool equalsMinimumOK) const
661 {
662     const Vector<SMILTimeWithOrigin>& list = beginOrEnd == Begin ? m_beginTimes : m_endTimes;
663     int sizeOfList = list.size();
664
665     if (!sizeOfList)
666         return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
667
668     const SMILTimeWithOrigin* result = binarySearch<const SMILTimeWithOrigin, SMILTime, extractTimeFromVector>(list.begin(), sizeOfList, minimumTime, WTF::KeyMustNotBePresentInArray);
669     int indexOfResult = result - list.begin();
670     if (sizeOfList - 1 > indexOfResult && list[indexOfResult].time() < minimumTime)
671         ++indexOfResult;
672
673     ASSERT(indexOfResult < sizeOfList);
674     const SMILTime& currentTime = list[indexOfResult].time();
675
676     // "The special value "indefinite" does not yield an instance time in the begin list."
677     if (currentTime.isIndefinite() && beginOrEnd == Begin)
678         return SMILTime::unresolved();
679
680     if (currentTime < minimumTime)
681         return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
682
683     // If the equals is NOT accepted, we have to find a bigger one.
684     if (currentTime == minimumTime && !equalsMinimumOK) {
685         if (indexOfResult + 1 >= sizeOfList)
686             return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
687     }
688
689     while (indexOfResult < sizeOfList - 1 && currentTime == list[indexOfResult + 1].time())
690         ++indexOfResult;
691
692     if (currentTime > minimumTime)
693         return currentTime;
694     if (currentTime == minimumTime) {
695         if (indexOfResult + 1 < sizeOfList - 1)
696             return list[indexOfResult + 1].time();
697         return beginOrEnd == Begin ? SMILTime::unresolved() : SMILTime::indefinite();
698     }
699
700     return currentTime;
701 }
702
703 SMILTime SVGSMILElement::repeatingDuration() const
704 {
705     // Computing the active duration
706     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
707     SMILTime repeatCount = this->repeatCount();
708     SMILTime repeatDur = this->repeatDur();
709     SMILTime simpleDuration = this->simpleDuration();
710     if (!simpleDuration || (repeatDur.isUnresolved() && repeatCount.isUnresolved()))
711         return simpleDuration;
712     SMILTime repeatCountDuration = simpleDuration * repeatCount;
713     return min(repeatCountDuration, min(repeatDur, SMILTime::indefinite()));
714 }
715
716 SMILTime SVGSMILElement::resolveActiveEnd(SMILTime resolvedBegin, SMILTime resolvedEnd) const
717 {
718     // Computing the active duration
719     // http://www.w3.org/TR/SMIL2/smil-timing.html#Timing-ComputingActiveDur
720     SMILTime preliminaryActiveDuration;
721     if (!resolvedEnd.isUnresolved() && dur().isUnresolved() && repeatDur().isUnresolved() && repeatCount().isUnresolved())
722         preliminaryActiveDuration = resolvedEnd - resolvedBegin;
723     else if (!resolvedEnd.isFinite())
724         preliminaryActiveDuration = repeatingDuration();
725     else
726         preliminaryActiveDuration = min(repeatingDuration(), resolvedEnd - resolvedBegin);
727     
728     SMILTime minValue = this->minValue();
729     SMILTime maxValue = this->maxValue();
730     if (minValue > maxValue) {
731         // Ignore both.
732         // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#MinMax
733         minValue = 0;
734         maxValue = SMILTime::indefinite();
735     }
736     return resolvedBegin + min(maxValue, max(minValue, preliminaryActiveDuration));
737 }
738
739 void SVGSMILElement::resolveInterval(bool first, SMILTime& beginResult, SMILTime& endResult) const
740 {
741     // See the pseudocode in
742     // http://www.w3.org/TR/2001/REC-smil-animation-20010904/#Timing-BeginEnd-LifeCycle
743     SMILTime beginAfter = first ? -numeric_limits<double>::infinity() : m_intervalEnd;
744     SMILTime lastIntervalTempEnd = numeric_limits<double>::infinity();
745     while (true) {
746         SMILTime tempBegin = findInstanceTime(Begin, beginAfter, true);
747         if (tempBegin.isUnresolved())
748             break;
749         SMILTime tempEnd;
750         if (m_endTimes.isEmpty())
751             tempEnd = resolveActiveEnd(tempBegin, SMILTime::indefinite());
752         else {
753             tempEnd = findInstanceTime(End, tempBegin, true);
754             if ((first && tempBegin == tempEnd && tempEnd == lastIntervalTempEnd) || (!first && tempEnd == m_intervalEnd)) 
755                 tempEnd = findInstanceTime(End, tempBegin, false);    
756             if (tempEnd.isUnresolved()) {
757                 if (!m_endTimes.isEmpty() && !m_hasEndEventConditions)
758                     break;
759             }
760             tempEnd = resolveActiveEnd(tempBegin, tempEnd);
761         }
762         if (tempEnd > 0 || !first) {
763             beginResult = tempBegin;
764             endResult = tempEnd;
765             return;
766         }
767         if (restart() == RestartNever)
768             break;
769
770         beginAfter = tempEnd;
771         lastIntervalTempEnd = tempEnd;
772     }
773     beginResult = SMILTime::unresolved();
774     endResult = SMILTime::unresolved();
775 }
776     
777 void SVGSMILElement::resolveFirstInterval()
778 {
779     SMILTime begin;
780     SMILTime end;
781     resolveInterval(true, begin, end);
782     ASSERT(!begin.isIndefinite());
783
784     if (!begin.isUnresolved() && (begin != m_intervalBegin || end != m_intervalEnd)) {   
785         bool wasUnresolved = m_intervalBegin.isUnresolved();
786         m_intervalBegin = begin;
787         m_intervalEnd = end;
788         notifyDependentsIntervalChanged(wasUnresolved ? NewInterval : ExistingInterval);
789         m_nextProgressTime = min(m_nextProgressTime, m_intervalBegin);
790         reschedule();
791     }
792 }
793
794 void SVGSMILElement::resolveNextInterval()
795 {
796     SMILTime begin;
797     SMILTime end;
798     resolveInterval(false, begin, end);
799     ASSERT(!begin.isIndefinite());
800     
801     if (!begin.isUnresolved() && begin != m_intervalBegin) {
802         m_intervalBegin = begin;
803         m_intervalEnd = end;
804         notifyDependentsIntervalChanged(NewInterval);
805         m_nextProgressTime = min(m_nextProgressTime, m_intervalBegin);
806     }
807 }
808
809 SMILTime SVGSMILElement::nextProgressTime() const
810 {
811     return m_nextProgressTime;
812 }
813     
814 void SVGSMILElement::beginListChanged(SMILTime eventTime)
815 {
816     if (m_isWaitingForFirstInterval)
817         resolveFirstInterval();
818     else {
819         SMILTime newBegin = findInstanceTime(Begin, eventTime, true);
820         if (newBegin.isFinite() && (m_intervalEnd <= eventTime || newBegin < m_intervalBegin)) {
821             // Begin time changed, re-resolve the interval.
822             SMILTime oldBegin = m_intervalBegin;
823             m_intervalEnd = eventTime;
824             resolveInterval(false, m_intervalBegin, m_intervalEnd);  
825             ASSERT(!m_intervalBegin.isUnresolved());
826             if (m_intervalBegin != oldBegin) {
827                 if (m_activeState == Active && m_intervalBegin > eventTime) {
828                     m_activeState = determineActiveState(eventTime);
829                     if (m_activeState != Active)
830                         endedActiveInterval();
831                 }
832                 notifyDependentsIntervalChanged(ExistingInterval);
833             }
834         }
835     }
836     m_nextProgressTime = elapsed();
837     reschedule();
838 }
839
840 void SVGSMILElement::endListChanged(SMILTime)
841 {
842     SMILTime elapsed = this->elapsed();
843     if (m_isWaitingForFirstInterval)
844         resolveFirstInterval();
845     else if (elapsed < m_intervalEnd && m_intervalBegin.isFinite()) {
846         SMILTime newEnd = findInstanceTime(End, m_intervalBegin, false);
847         if (newEnd < m_intervalEnd) {
848             newEnd = resolveActiveEnd(m_intervalBegin, newEnd);
849             if (newEnd != m_intervalEnd) {
850                 m_intervalEnd = newEnd;
851                 notifyDependentsIntervalChanged(ExistingInterval);
852             }
853         }
854     }
855     m_nextProgressTime = elapsed;
856     reschedule();
857 }
858     
859 void SVGSMILElement::checkRestart(SMILTime elapsed)
860 {
861     ASSERT(!m_isWaitingForFirstInterval);
862     ASSERT(elapsed >= m_intervalBegin);
863     
864     Restart restart = this->restart();
865     if (restart == RestartNever)
866         return;
867     
868     if (elapsed < m_intervalEnd) {
869         if (restart != RestartAlways)
870             return;
871         SMILTime nextBegin = findInstanceTime(Begin, m_intervalBegin, false);
872         if (nextBegin < m_intervalEnd) { 
873             m_intervalEnd = nextBegin;
874             notifyDependentsIntervalChanged(ExistingInterval);
875         }
876     } 
877     if (elapsed >= m_intervalEnd)
878         resolveNextInterval();
879 }
880     
881 float SVGSMILElement::calculateAnimationPercentAndRepeat(SMILTime elapsed, unsigned& repeat) const
882 {
883     SMILTime simpleDuration = this->simpleDuration();
884     repeat = 0;
885     if (simpleDuration.isIndefinite()) {
886         repeat = 0;
887         return 0.f;
888     }
889     if (!simpleDuration) {
890         repeat = 0;
891         return 1.f;
892     }
893     ASSERT(m_intervalBegin.isFinite());
894     ASSERT(simpleDuration.isFinite());
895     SMILTime activeTime = elapsed - m_intervalBegin;
896     SMILTime repeatingDuration = this->repeatingDuration();
897     if (elapsed >= m_intervalEnd || activeTime > repeatingDuration) {
898         repeat = static_cast<unsigned>(repeatingDuration.value() / simpleDuration.value());
899         if (fmod(repeatingDuration.value(), !simpleDuration.value()))
900             repeat--;
901
902         SMILTime simpleEndTime = fmod(m_intervalEnd.value() - m_intervalBegin.value(), simpleDuration.value());
903         if (simpleEndTime.value())
904             return narrowPrecisionToFloat(simpleEndTime.value() / simpleDuration.value());
905
906         return 1.f;
907     }
908     repeat = static_cast<unsigned>(activeTime.value() / simpleDuration.value());
909     SMILTime simpleTime = fmod(activeTime.value(), simpleDuration.value());
910     return narrowPrecisionToFloat(simpleTime.value() / simpleDuration.value());
911 }
912     
913 SMILTime SVGSMILElement::calculateNextProgressTime(SMILTime elapsed) const
914 {
915     if (m_activeState == Active) {
916         // If duration is indefinite the value does not actually change over time. Same is true for <set>.
917         SMILTime simpleDuration = this->simpleDuration();
918         if (simpleDuration.isIndefinite() || hasTagName(SVGNames::setTag)) {
919             SMILTime repeatingDurationEnd = m_intervalBegin + repeatingDuration();
920             // We are supposed to do freeze semantics when repeating ends, even if the element is still active. 
921             // Take care that we get a timer callback at that point.
922             if (elapsed < repeatingDurationEnd && repeatingDurationEnd < m_intervalEnd && repeatingDurationEnd.isFinite())
923                 return repeatingDurationEnd;
924             return m_intervalEnd;
925         } 
926         return elapsed + 0.025;
927     }
928     return m_intervalBegin >= elapsed ? m_intervalBegin : SMILTime::unresolved();
929 }
930     
931 SVGSMILElement::ActiveState SVGSMILElement::determineActiveState(SMILTime elapsed) const
932 {
933     if (elapsed >= m_intervalBegin && elapsed < m_intervalEnd)
934         return Active;
935
936     if (m_activeState == Active)
937         return fill() == FillFreeze ? Frozen : Inactive;
938
939     return m_activeState;
940 }
941     
942 bool SVGSMILElement::isContributing(SMILTime elapsed) const 
943
944     // Animation does not contribute during the active time if it is past its repeating duration and has fill=remove.
945     return (m_activeState == Active && (fill() == FillFreeze || elapsed <= m_intervalBegin + repeatingDuration())) || m_activeState == Frozen;
946 }
947     
948 void SVGSMILElement::progress(SMILTime elapsed, SVGSMILElement* resultElement)
949 {
950     ASSERT(m_timeContainer);
951     ASSERT(m_isWaitingForFirstInterval || m_intervalBegin.isFinite());
952     
953     if (!m_conditionsConnected)
954         connectConditions();
955     
956     if (!m_intervalBegin.isFinite()) {
957         ASSERT(m_activeState == Inactive);
958         m_nextProgressTime = SMILTime::unresolved();
959         return;
960     }
961     
962     if (elapsed < m_intervalBegin) {
963         ASSERT(m_activeState != Active);
964         if (m_activeState == Frozen && resultElement)
965             updateAnimation(m_lastPercent, m_lastRepeat, resultElement);
966         m_nextProgressTime = m_intervalBegin;
967         return;
968     }
969     
970     m_previousIntervalBegin = m_intervalBegin;
971     
972     if (m_activeState == Inactive) {
973         m_isWaitingForFirstInterval = false;
974         m_activeState = Active;
975         startedActiveInterval();
976     }
977     
978     unsigned repeat;
979     float percent = calculateAnimationPercentAndRepeat(elapsed, repeat);
980
981     checkRestart(elapsed);
982
983     ActiveState oldActiveState = m_activeState;
984     m_activeState = determineActiveState(elapsed);
985     
986     if (isContributing(elapsed)) {
987         if (resultElement)
988             updateAnimation(percent, repeat, resultElement);
989         m_lastPercent = percent;
990         m_lastRepeat = repeat;
991     }
992
993     if (oldActiveState == Active && m_activeState != Active)
994         endedActiveInterval();
995
996     m_nextProgressTime = calculateNextProgressTime(elapsed);
997 }
998     
999 void SVGSMILElement::notifyDependentsIntervalChanged(NewOrExistingInterval newOrExisting)
1000 {
1001     ASSERT(m_intervalBegin.isFinite());
1002     DEFINE_STATIC_LOCAL(HashSet<SVGSMILElement*>, loopBreaker, ());
1003     if (loopBreaker.contains(this))
1004         return;
1005     loopBreaker.add(this);
1006     
1007     TimeDependentSet::iterator end = m_timeDependents.end();
1008     for (TimeDependentSet::iterator it = m_timeDependents.begin(); it != end; ++it) {
1009         SVGSMILElement* dependent = *it;
1010         dependent->createInstanceTimesFromSyncbase(this, newOrExisting);
1011     }
1012
1013     loopBreaker.remove(this);
1014 }
1015     
1016 void SVGSMILElement::createInstanceTimesFromSyncbase(SVGSMILElement* syncbase, NewOrExistingInterval)
1017 {
1018     // FIXME: To be really correct, this should handle updating exising interval by changing 
1019     // the associated times instead of creating new ones.
1020     for (unsigned n = 0; n < m_conditions.size(); ++n) {
1021         Condition& condition = m_conditions[n];
1022         if (condition.m_type == Condition::Syncbase && condition.m_syncbase == syncbase) {
1023             ASSERT(condition.m_name == "begin" || condition.m_name == "end");
1024             // No nested time containers in SVG, no need for crazy time space conversions. Phew!
1025             SMILTime time = 0;
1026             if (condition.m_name == "begin")
1027                 time = syncbase->m_intervalBegin + condition.m_offset;
1028             else
1029                 time = syncbase->m_intervalEnd + condition.m_offset;
1030             ASSERT(time.isFinite());
1031             if (condition.m_beginOrEnd == Begin)
1032                 addBeginTime(elapsed(), time);
1033             else
1034                 addEndTime(elapsed(), time);
1035         }
1036     }
1037 }
1038     
1039 void SVGSMILElement::addTimeDependent(SVGSMILElement* animation)
1040 {
1041     m_timeDependents.add(animation);
1042     if (m_intervalBegin.isFinite())
1043         animation->createInstanceTimesFromSyncbase(this, NewInterval);
1044 }
1045     
1046 void SVGSMILElement::removeTimeDependent(SVGSMILElement* animation)
1047 {
1048     m_timeDependents.remove(animation);
1049 }
1050     
1051 void SVGSMILElement::handleConditionEvent(Event*, Condition* condition)
1052 {
1053     SMILTime elapsed = this->elapsed();
1054     if (condition->m_beginOrEnd == Begin)
1055         addBeginTime(elapsed, elapsed + condition->m_offset);
1056     else
1057         addEndTime(elapsed, elapsed + condition->m_offset);
1058 }
1059
1060 void SVGSMILElement::beginByLinkActivation()
1061 {
1062     SMILTime elapsed = this->elapsed();
1063     addBeginTime(elapsed, elapsed);
1064 }
1065
1066 void SVGSMILElement::endedActiveInterval()
1067 {
1068     clearTimesWithDynamicOrigins(m_beginTimes);
1069     clearTimesWithDynamicOrigins(m_endTimes);
1070 }
1071
1072 }
1073
1074 #endif