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