1/*
2 * Copyright (C) 2004, 2005, 2006, 2007, 2008 Nikolas Zimmermann <zimmermann@kde.org>
3 * Copyright (C) 2004, 2005, 2006, 2007 Rob Buis <buis@kde.org>
4 * Copyright (C) Research In Motion Limited 2009-2010. All rights reserved.
5 * Copyright (C) 2011 Torch Mobile (Beijing) Co. Ltd. All rights reserved.
6 * Copyright (C) 2012 University of Szeged
7 * Copyright (C) 2012 Renata Hodovan <reni@webkit.org>
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * Library General Public License for more details.
18 *
19 * You should have received a copy of the GNU Library General Public License
20 * along with this library; see the file COPYING.LIB.  If not, write to
21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
23 */
24
25#include "config.h"
26#include "SVGUseElement.h"
27
28#include "CachedResourceLoader.h"
29#include "CachedResourceRequest.h"
30#include "CachedSVGDocument.h"
31#include "Document.h"
32#include "ElementIterator.h"
33#include "Event.h"
34#include "EventListener.h"
35#include "HTMLNames.h"
36#include "NodeRenderStyle.h"
37#include "RegisteredEventListener.h"
38#include "RenderSVGResource.h"
39#include "RenderSVGTransformableContainer.h"
40#include "ShadowRoot.h"
41#include "SVGElementInstance.h"
42#include "SVGElementRareData.h"
43#include "SVGElementInstanceList.h"
44#include "SVGGElement.h"
45#include "SVGLengthContext.h"
46#include "SVGNames.h"
47#include "SVGSMILElement.h"
48#include "SVGSVGElement.h"
49#include "SVGSymbolElement.h"
50#include "StyleResolver.h"
51#include "XLinkNames.h"
52#include "XMLDocumentParser.h"
53#include "XMLSerializer.h"
54#include <wtf/NeverDestroyed.h>
55
56// Dump SVGElementInstance object tree - useful to debug instanceRoot problems
57// #define DUMP_INSTANCE_TREE
58
59// Dump the deep-expanded shadow tree (where the renderers are built from)
60// #define DUMP_SHADOW_TREE
61
62namespace WebCore {
63
64// Animated property definitions
65DEFINE_ANIMATED_LENGTH(SVGUseElement, SVGNames::xAttr, X, x)
66DEFINE_ANIMATED_LENGTH(SVGUseElement, SVGNames::yAttr, Y, y)
67DEFINE_ANIMATED_LENGTH(SVGUseElement, SVGNames::widthAttr, Width, width)
68DEFINE_ANIMATED_LENGTH(SVGUseElement, SVGNames::heightAttr, Height, height)
69DEFINE_ANIMATED_STRING(SVGUseElement, XLinkNames::hrefAttr, Href, href)
70DEFINE_ANIMATED_BOOLEAN(SVGUseElement, SVGNames::externalResourcesRequiredAttr, ExternalResourcesRequired, externalResourcesRequired)
71
72BEGIN_REGISTER_ANIMATED_PROPERTIES(SVGUseElement)
73    REGISTER_LOCAL_ANIMATED_PROPERTY(x)
74    REGISTER_LOCAL_ANIMATED_PROPERTY(y)
75    REGISTER_LOCAL_ANIMATED_PROPERTY(width)
76    REGISTER_LOCAL_ANIMATED_PROPERTY(height)
77    REGISTER_LOCAL_ANIMATED_PROPERTY(href)
78    REGISTER_LOCAL_ANIMATED_PROPERTY(externalResourcesRequired)
79    REGISTER_PARENT_ANIMATED_PROPERTIES(SVGGraphicsElement)
80END_REGISTER_ANIMATED_PROPERTIES
81
82inline SVGUseElement::SVGUseElement(const QualifiedName& tagName, Document& document, bool wasInsertedByParser)
83    : SVGGraphicsElement(tagName, document)
84    , m_x(LengthModeWidth)
85    , m_y(LengthModeHeight)
86    , m_width(LengthModeWidth)
87    , m_height(LengthModeHeight)
88    , m_wasInsertedByParser(wasInsertedByParser)
89    , m_haveFiredLoadEvent(false)
90    , m_needsShadowTreeRecreation(false)
91    , m_svgLoadEventTimer(this, &SVGElement::svgLoadEventTimerFired)
92{
93    ASSERT(hasCustomStyleResolveCallbacks());
94    ASSERT(hasTagName(SVGNames::useTag));
95    registerAnimatedPropertiesForSVGUseElement();
96}
97
98PassRefPtr<SVGUseElement> SVGUseElement::create(const QualifiedName& tagName, Document& document, bool wasInsertedByParser)
99{
100    // Always build a #shadow-root for SVGUseElement.
101    RefPtr<SVGUseElement> use = adoptRef(new SVGUseElement(tagName, document, wasInsertedByParser));
102    use->ensureUserAgentShadowRoot();
103    return use.release();
104}
105
106SVGUseElement::~SVGUseElement()
107{
108    setCachedDocument(0);
109
110    clearResourceReferences();
111}
112
113SVGElementInstance* SVGUseElement::instanceRoot()
114{
115    // If there is no element instance tree, force immediate SVGElementInstance tree
116    // creation by asking the document to invoke our recalcStyle function - as we can't
117    // wait for the lazy creation to happen if e.g. JS wants to access the instanceRoot
118    // object right after creating the element on-the-fly
119    if (!m_targetElementInstance)
120        document().updateLayoutIgnorePendingStylesheets();
121
122    return m_targetElementInstance.get();
123}
124
125SVGElementInstance* SVGUseElement::animatedInstanceRoot() const
126{
127    // FIXME: Implement me.
128    return 0;
129}
130
131bool SVGUseElement::isSupportedAttribute(const QualifiedName& attrName)
132{
133    static NeverDestroyed<HashSet<QualifiedName>> supportedAttributes;
134    if (supportedAttributes.get().isEmpty()) {
135        SVGLangSpace::addSupportedAttributes(supportedAttributes);
136        SVGExternalResourcesRequired::addSupportedAttributes(supportedAttributes);
137        SVGURIReference::addSupportedAttributes(supportedAttributes);
138        supportedAttributes.get().add(SVGNames::xAttr);
139        supportedAttributes.get().add(SVGNames::yAttr);
140        supportedAttributes.get().add(SVGNames::widthAttr);
141        supportedAttributes.get().add(SVGNames::heightAttr);
142    }
143    return supportedAttributes.get().contains<SVGAttributeHashTranslator>(attrName);
144}
145
146void SVGUseElement::parseAttribute(const QualifiedName& name, const AtomicString& value)
147{
148    SVGParsingError parseError = NoError;
149
150    if (!isSupportedAttribute(name))
151        SVGGraphicsElement::parseAttribute(name, value);
152    else if (name == SVGNames::xAttr)
153        setXBaseValue(SVGLength::construct(LengthModeWidth, value, parseError));
154    else if (name == SVGNames::yAttr)
155        setYBaseValue(SVGLength::construct(LengthModeHeight, value, parseError));
156    else if (name == SVGNames::widthAttr)
157        setWidthBaseValue(SVGLength::construct(LengthModeWidth, value, parseError, ForbidNegativeLengths));
158    else if (name == SVGNames::heightAttr)
159        setHeightBaseValue(SVGLength::construct(LengthModeHeight, value, parseError, ForbidNegativeLengths));
160    else if (SVGLangSpace::parseAttribute(name, value)
161             || SVGExternalResourcesRequired::parseAttribute(name, value)
162             || SVGURIReference::parseAttribute(name, value)) {
163    } else
164        ASSERT_NOT_REACHED();
165
166    reportAttributeParsingError(parseError, name, value);
167}
168
169#if !ASSERT_DISABLED
170static inline bool isWellFormedDocument(Document& document)
171{
172    if (document.isSVGDocument() || document.isXHTMLDocument())
173        return static_cast<XMLDocumentParser*>(document.parser())->wellFormed();
174    return true;
175}
176#endif
177
178Node::InsertionNotificationRequest SVGUseElement::insertedInto(ContainerNode& rootParent)
179{
180    // This functions exists to assure assumptions made in the code regarding SVGElementInstance creation/destruction are satisfied.
181    SVGGraphicsElement::insertedInto(rootParent);
182    if (!rootParent.inDocument())
183        return InsertionDone;
184    ASSERT(!m_targetElementInstance || !isWellFormedDocument(document()));
185    ASSERT(!hasPendingResources() || !isWellFormedDocument(document()));
186    SVGExternalResourcesRequired::insertedIntoDocument(this);
187    if (!m_wasInsertedByParser)
188        return InsertionShouldCallDidNotifySubtreeInsertions;
189    return InsertionDone;
190}
191
192void SVGUseElement::didNotifySubtreeInsertions(ContainerNode*)
193{
194    buildPendingResource();
195}
196
197void SVGUseElement::removedFrom(ContainerNode& rootParent)
198{
199    SVGGraphicsElement::removedFrom(rootParent);
200    if (rootParent.inDocument())
201        clearResourceReferences();
202}
203
204Document* SVGUseElement::referencedDocument() const
205{
206    if (!isExternalURIReference(href(), document()))
207        return &document();
208    return externalDocument();
209}
210
211Document* SVGUseElement::externalDocument() const
212{
213    if (m_cachedDocument && m_cachedDocument->isLoaded()) {
214        // Gracefully handle error condition.
215        if (m_cachedDocument->errorOccurred())
216            return 0;
217        ASSERT(m_cachedDocument->document());
218        return m_cachedDocument->document();
219    }
220    return 0;
221}
222
223void SVGUseElement::svgAttributeChanged(const QualifiedName& attrName)
224{
225    if (!isSupportedAttribute(attrName)) {
226        SVGGraphicsElement::svgAttributeChanged(attrName);
227        return;
228    }
229
230    SVGElementInstance::InvalidationGuard invalidationGuard(this);
231
232    auto renderer = this->renderer();
233    if (attrName == SVGNames::xAttr
234        || attrName == SVGNames::yAttr
235        || attrName == SVGNames::widthAttr
236        || attrName == SVGNames::heightAttr) {
237        updateRelativeLengthsInformation();
238        if (renderer)
239            RenderSVGResource::markForLayoutAndParentResourceInvalidation(*renderer);
240        return;
241    }
242
243    if (SVGExternalResourcesRequired::handleAttributeChange(this, attrName))
244        return;
245
246    if (SVGURIReference::isKnownAttribute(attrName)) {
247        bool isExternalReference = isExternalURIReference(href(), document());
248        if (isExternalReference) {
249            URL url = document().completeURL(href());
250            if (url.hasFragmentIdentifier()) {
251                CachedResourceRequest request(ResourceRequest(url.string()));
252                request.setInitiator(this);
253                setCachedDocument(document().cachedResourceLoader()->requestSVGDocument(request));
254            }
255        } else
256            setCachedDocument(0);
257
258        if (!m_wasInsertedByParser)
259            buildPendingResource();
260
261        return;
262    }
263
264    if (SVGLangSpace::isKnownAttribute(attrName)
265        || SVGExternalResourcesRequired::isKnownAttribute(attrName)) {
266        invalidateShadowTree();
267        return;
268    }
269
270    ASSERT_NOT_REACHED();
271}
272
273void SVGUseElement::willAttachRenderers()
274{
275    if (m_needsShadowTreeRecreation)
276        buildPendingResource();
277}
278
279#ifdef DUMP_INSTANCE_TREE
280static void dumpInstanceTree(unsigned int& depth, String& text, SVGElementInstance* targetInstance)
281{
282    SVGElement* element = targetInstance->correspondingElement();
283    ASSERT(element);
284
285    if (element->hasTagName(SVGNames::useTag)) {
286        if (toSVGUseElement(element)->cachedDocumentIsStillLoading())
287            return;
288    }
289
290    SVGElement* shadowTreeElement = targetInstance->shadowTreeElement();
291    ASSERT(shadowTreeElement);
292
293    SVGUseElement* directUseElement = targetInstance->directUseElement();
294    String directUseElementName = directUseElement ? directUseElement->nodeName() : "null";
295
296    String elementId = element->getIdAttribute();
297    String elementNodeName = element->nodeName();
298    String shadowTreeElementNodeName = shadowTreeElement->nodeName();
299    String parentNodeName = element->parentNode() ? element->parentNode()->nodeName() : "null";
300    String firstChildNodeName = element->firstChild() ? element->firstChild()->nodeName() : "null";
301
302    for (unsigned int i = 0; i < depth; ++i)
303        text += "  ";
304
305    text += String::format("SVGElementInstance this=%p, (parentNode=%s (%p), firstChild=%s (%p), correspondingElement=%s (%p), directUseElement=%s (%p), shadowTreeElement=%s (%p), id=%s)\n",
306                           targetInstance, parentNodeName.latin1().data(), element->parentNode(), firstChildNodeName.latin1().data(), element->firstChild(),
307                           elementNodeName.latin1().data(), element, directUseElementName.latin1().data(), directUseElement, shadowTreeElementNodeName.latin1().data(), shadowTreeElement, elementId.latin1().data());
308
309    for (unsigned int i = 0; i < depth; ++i)
310        text += "  ";
311
312    const HashSet<SVGElementInstance*>& elementInstances = element->instancesForElement();
313    text += "Corresponding element is associated with " + String::number(elementInstances.size()) + " instance(s):\n";
314
315    const HashSet<SVGElementInstance*>::const_iterator end = elementInstances.end();
316    for (HashSet<SVGElementInstance*>::const_iterator it = elementInstances.begin(); it != end; ++it) {
317        for (unsigned int i = 0; i < depth; ++i)
318            text += "  ";
319
320        text += String::format(" -> SVGElementInstance this=%p, (refCount: %i, shadowTreeElement in document? %i)\n",
321                               *it, (*it)->refCount(), (*it)->shadowTreeElement()->inDocument());
322    }
323
324    ++depth;
325
326    for (SVGElementInstance* instance = targetInstance->firstChild(); instance; instance = instance->nextSibling())
327        dumpInstanceTree(depth, text, instance);
328
329    --depth;
330}
331#endif
332
333static bool isDisallowedElement(const Element& element)
334{
335    // Spec: "Any 'svg', 'symbol', 'g', graphics element or other 'use' is potentially a template object that can be re-used
336    // (i.e., "instanced") in the SVG document via a 'use' element."
337    // "Graphics Element" is defined as 'circle', 'ellipse', 'image', 'line', 'path', 'polygon', 'polyline', 'rect', 'text'
338    // Excluded are anything that is used by reference or that only make sense to appear once in a document.
339
340    if (!element.isSVGElement())
341        return true;
342
343    static NeverDestroyed<HashSet<QualifiedName>> allowedElementTags;
344    if (allowedElementTags.get().isEmpty()) {
345        allowedElementTags.get().add(SVGNames::aTag);
346        allowedElementTags.get().add(SVGNames::circleTag);
347        allowedElementTags.get().add(SVGNames::descTag);
348        allowedElementTags.get().add(SVGNames::ellipseTag);
349        allowedElementTags.get().add(SVGNames::gTag);
350        allowedElementTags.get().add(SVGNames::imageTag);
351        allowedElementTags.get().add(SVGNames::lineTag);
352        allowedElementTags.get().add(SVGNames::metadataTag);
353        allowedElementTags.get().add(SVGNames::pathTag);
354        allowedElementTags.get().add(SVGNames::polygonTag);
355        allowedElementTags.get().add(SVGNames::polylineTag);
356        allowedElementTags.get().add(SVGNames::rectTag);
357        allowedElementTags.get().add(SVGNames::svgTag);
358        allowedElementTags.get().add(SVGNames::switchTag);
359        allowedElementTags.get().add(SVGNames::symbolTag);
360        allowedElementTags.get().add(SVGNames::textTag);
361        allowedElementTags.get().add(SVGNames::textPathTag);
362        allowedElementTags.get().add(SVGNames::titleTag);
363        allowedElementTags.get().add(SVGNames::trefTag);
364        allowedElementTags.get().add(SVGNames::tspanTag);
365        allowedElementTags.get().add(SVGNames::useTag);
366    }
367    return !allowedElementTags.get().contains<SVGAttributeHashTranslator>(element.tagQName());
368}
369
370static bool subtreeContainsDisallowedElement(SVGElement& start)
371{
372    for (auto& element : descendantsOfType<Element>(start)) {
373        if (isDisallowedElement(element))
374            return true;
375    }
376
377    return false;
378}
379
380void SVGUseElement::clearResourceReferences()
381{
382    // FIXME: We should try to optimize this, to at least allow partial reclones.
383    if (ShadowRoot* shadowTreeRootElement = shadowRoot())
384        shadowTreeRootElement->removeChildren();
385
386    if (m_targetElementInstance) {
387        m_targetElementInstance->detach();
388        m_targetElementInstance = 0;
389    }
390
391    m_needsShadowTreeRecreation = false;
392
393    document().accessSVGExtensions()->removeAllTargetReferencesForElement(this);
394}
395
396void SVGUseElement::buildPendingResource()
397{
398    if (!referencedDocument() || isInShadowTree())
399        return;
400    clearResourceReferences();
401    if (!inDocument())
402        return;
403
404    String id;
405    Element* target = SVGURIReference::targetElementFromIRIString(href(), document(), &id, externalDocument());
406    if (!target || !target->inDocument()) {
407        // If we can't find the target of an external element, just give up.
408        // We can't observe if the target somewhen enters the external document, nor should we do it.
409        if (externalDocument())
410            return;
411        if (id.isEmpty())
412            return;
413
414        referencedDocument()->accessSVGExtensions()->addPendingResource(id, this);
415        ASSERT(hasPendingResources());
416        return;
417    }
418
419    if (target->isSVGElement()) {
420        buildShadowAndInstanceTree(toSVGElement(target));
421        invalidateDependentShadowTrees();
422    }
423
424    ASSERT(!m_needsShadowTreeRecreation);
425}
426
427void SVGUseElement::buildShadowAndInstanceTree(SVGElement* target)
428{
429    ASSERT(!m_targetElementInstance);
430
431    // Do not build the shadow/instance tree for <use> elements living in a shadow tree.
432    // The will be expanded soon anyway - see expandUseElementsInShadowTree().
433    if (isInShadowTree())
434        return;
435
436    // Do not allow self-referencing.
437    // 'target' may be null, if it's a non SVG namespaced element.
438    if (!target || target == this)
439        return;
440
441    // Why a seperated instance/shadow tree? SVG demands it:
442    // The instance tree is accesable from JavaScript, and has to
443    // expose a 1:1 copy of the referenced tree, whereas internally we need
444    // to alter the tree for correct "use-on-symbol", "use-on-svg" support.
445
446    // Build instance tree. Create root SVGElementInstance object for the first sub-tree node.
447    //
448    // Spec: If the 'use' element references a simple graphics element such as a 'rect', then there is only a
449    // single SVGElementInstance object, and the correspondingElement attribute on this SVGElementInstance object
450    // is the SVGRectElement that corresponds to the referenced 'rect' element.
451    m_targetElementInstance = SVGElementInstance::create(this, this, target);
452
453    // Eventually enter recursion to build SVGElementInstance objects for the sub-tree children
454    bool foundProblem = false;
455    buildInstanceTree(target, m_targetElementInstance.get(), foundProblem, false);
456
457    if (instanceTreeIsLoading(m_targetElementInstance.get()))
458        return;
459
460    // SVG specification does not say a word about <use> & cycles. My view on this is: just ignore it!
461    // Non-appearing <use> content is easier to debug, then half-appearing content.
462    if (foundProblem) {
463        clearResourceReferences();
464        return;
465    }
466
467    // Assure instance tree building was successfull
468    ASSERT(m_targetElementInstance);
469    ASSERT(!m_targetElementInstance->shadowTreeElement());
470    ASSERT(m_targetElementInstance->correspondingUseElement() == this);
471    ASSERT(m_targetElementInstance->directUseElement() == this);
472    ASSERT(m_targetElementInstance->correspondingElement() == target);
473
474    ShadowRoot* shadowTreeRootElement = shadowRoot();
475    ASSERT(shadowTreeRootElement);
476
477    // Build shadow tree from instance tree
478    // This also handles the special cases: <use> on <symbol>, <use> on <svg>.
479    buildShadowTree(target, m_targetElementInstance.get());
480
481    // Expand all <use> elements in the shadow tree.
482    // Expand means: replace the actual <use> element by what it references.
483    expandUseElementsInShadowTree(shadowTreeRootElement);
484
485    // Expand all <symbol> elements in the shadow tree.
486    // Expand means: replace the actual <symbol> element by the <svg> element.
487    expandSymbolElementsInShadowTree(shadowTreeRootElement);
488
489    // Now that the shadow tree is completly expanded, we can associate
490    // shadow tree elements <-> instances in the instance tree.
491    associateInstancesWithShadowTreeElements(shadowTreeRootElement->firstChild(), m_targetElementInstance.get());
492
493    // If no shadow tree element is present, this means that the reference root
494    // element was removed, as it is disallowed (ie. <use> on <foreignObject>)
495    // Do NOT leave an inconsistent instance tree around, instead destruct it.
496    if (!m_targetElementInstance->shadowTreeElement()) {
497        clearResourceReferences();
498        return;
499    }
500
501    ASSERT(m_targetElementInstance->shadowTreeElement()->parentNode() == shadowTreeRootElement);
502
503    // Transfer event listeners assigned to the referenced element to our shadow tree elements.
504    transferEventListenersToShadowTree(m_targetElementInstance.get());
505
506    // Update relative length information.
507    updateRelativeLengthsInformation();
508
509    // Eventually dump instance tree
510#ifdef DUMP_INSTANCE_TREE
511    String text;
512    unsigned int depth = 0;
513
514    dumpInstanceTree(depth, text, m_targetElementInstance.get());
515    fprintf(stderr, "\nDumping <use> instance tree:\n%s\n", text.latin1().data());
516#endif
517
518    // Eventually dump shadow tree
519#ifdef DUMP_SHADOW_TREE
520    RefPtr<XMLSerializer> serializer = XMLSerializer::create();
521    String markup = serializer->serializeToString(shadowTreeRootElement, ASSERT_NO_EXCEPTION);
522    fprintf(stderr, "Dumping <use> shadow tree markup:\n%s\n", markup.latin1().data());
523#endif
524}
525
526RenderPtr<RenderElement> SVGUseElement::createElementRenderer(PassRef<RenderStyle> style)
527{
528    return createRenderer<RenderSVGTransformableContainer>(*this, WTF::move(style));
529}
530
531static bool isDirectReference(const SVGElement& element)
532{
533    return element.hasTagName(SVGNames::pathTag)
534        || element.hasTagName(SVGNames::rectTag)
535        || element.hasTagName(SVGNames::circleTag)
536        || element.hasTagName(SVGNames::ellipseTag)
537        || element.hasTagName(SVGNames::polygonTag)
538        || element.hasTagName(SVGNames::polylineTag)
539        || element.hasTagName(SVGNames::textTag);
540}
541
542void SVGUseElement::toClipPath(Path& path)
543{
544    ASSERT(path.isEmpty());
545
546    Node* n = m_targetElementInstance ? m_targetElementInstance->shadowTreeElement() : 0;
547    if (!n)
548        return;
549
550    if (n->isSVGElement() && toSVGElement(*n).isSVGGraphicsElement()) {
551        if (!isDirectReference(toSVGElement(*n))) {
552            // Spec: Indirect references are an error (14.3.5)
553            document().accessSVGExtensions()->reportError("Not allowed to use indirect reference in <clip-path>");
554        } else {
555            toSVGGraphicsElement(*n).toClipPath(path);
556            // FIXME: Avoid manual resolution of x/y here. Its potentially harmful.
557            SVGLengthContext lengthContext(this);
558            path.translate(FloatSize(x().value(lengthContext), y().value(lengthContext)));
559            path.transform(animatedLocalTransform());
560        }
561    }
562}
563
564RenderElement* SVGUseElement::rendererClipChild() const
565{
566    if (!m_targetElementInstance)
567        return nullptr;
568
569    auto* element = m_targetElementInstance->shadowTreeElement();
570    if (!element)
571        return nullptr;
572
573    if (!isDirectReference(*element))
574        return nullptr;
575
576    return element->renderer();
577}
578
579void SVGUseElement::buildInstanceTree(SVGElement* target, SVGElementInstance* targetInstance, bool& foundProblem, bool foundUse)
580{
581    ASSERT(target);
582    ASSERT(targetInstance);
583
584    // Spec: If the referenced object is itself a 'use', or if there are 'use' subelements within the referenced
585    // object, the instance tree will contain recursive expansion of the indirect references to form a complete tree.
586    bool targetHasUseTag = target->hasTagName(SVGNames::useTag);
587    SVGElement* newTarget = 0;
588    if (targetHasUseTag) {
589        foundProblem = hasCycleUseReferencing(toSVGUseElement(target), targetInstance, newTarget);
590        if (foundProblem)
591            return;
592
593        // We only need to track first degree <use> dependencies. Indirect references are handled
594        // as the invalidation bubbles up the dependency chain.
595        if (!foundUse) {
596            document().accessSVGExtensions()->addElementReferencingTarget(this, target);
597            foundUse = true;
598        }
599    } else if (isDisallowedElement(*target)) {
600        foundProblem = true;
601        return;
602    }
603
604    // A general description from the SVG spec, describing what buildInstanceTree() actually does.
605    //
606    // Spec: If the 'use' element references a 'g' which contains two 'rect' elements, then the instance tree
607    // contains three SVGElementInstance objects, a root SVGElementInstance object whose correspondingElement
608    // is the SVGGElement object for the 'g', and then two child SVGElementInstance objects, each of which has
609    // its correspondingElement that is an SVGRectElement object.
610
611    for (auto& element : childrenOfType<SVGElement>(*target)) {
612        // Skip any non-svg nodes or any disallowed element.
613        if (isDisallowedElement(element))
614            continue;
615
616        // Create SVGElementInstance object, for both container/non-container nodes.
617        RefPtr<SVGElementInstance> instance = SVGElementInstance::create(this, 0, &element);
618        SVGElementInstance* instancePtr = instance.get();
619        targetInstance->appendChild(instance.release());
620
621        // Enter recursion, appending new instance tree nodes to the "instance" object.
622        buildInstanceTree(&element, instancePtr, foundProblem, foundUse);
623        if (foundProblem)
624            return;
625    }
626
627    if (!targetHasUseTag || !newTarget)
628        return;
629
630    RefPtr<SVGElementInstance> newInstance = SVGElementInstance::create(this, toSVGUseElement(target), newTarget);
631    SVGElementInstance* newInstancePtr = newInstance.get();
632    targetInstance->appendChild(newInstance.release());
633    buildInstanceTree(newTarget, newInstancePtr, foundProblem, foundUse);
634}
635
636bool SVGUseElement::hasCycleUseReferencing(SVGUseElement* use, SVGElementInstance* targetInstance, SVGElement*& newTarget)
637{
638    ASSERT(referencedDocument());
639    Element* targetElement = SVGURIReference::targetElementFromIRIString(use->href(), *referencedDocument());
640    newTarget = 0;
641    if (targetElement && targetElement->isSVGElement())
642        newTarget = toSVGElement(targetElement);
643
644    if (!newTarget)
645        return false;
646
647    // Shortcut for self-references
648    if (newTarget == this)
649        return true;
650
651    AtomicString targetId = newTarget->getIdAttribute();
652    SVGElementInstance* instance = targetInstance->parentNode();
653    while (instance) {
654        SVGElement* element = instance->correspondingElement();
655
656        if (element->hasID() && element->getIdAttribute() == targetId && &element->document() == &newTarget->document())
657            return true;
658
659        instance = instance->parentNode();
660    }
661    return false;
662}
663
664static inline void removeDisallowedElementsFromSubtree(SVGElement& subtree)
665{
666    ASSERT(!subtree.inDocument());
667    Vector<Element*> toRemove;
668    auto it = descendantsOfType<Element>(subtree).begin();
669    auto end = descendantsOfType<Element>(subtree).end();
670    while (it != end) {
671        if (isDisallowedElement(*it)) {
672            toRemove.append(&*it);
673            it.traverseNextSkippingChildren();
674            continue;
675        }
676        ++it;
677    }
678    // The subtree is not in document so this won't generate events that could mutate the tree.
679    for (unsigned i = 0; i < toRemove.size(); ++i)
680        toRemove[i]->parentNode()->removeChild(toRemove[i]);
681}
682
683void SVGUseElement::buildShadowTree(SVGElement* target, SVGElementInstance* targetInstance)
684{
685    ASSERT(target); // FIXME: Don't be a pointer!
686
687    // For instance <use> on <foreignObject> (direct case).
688    if (isDisallowedElement(*target))
689        return;
690
691    RefPtr<SVGElement> newChild = static_pointer_cast<SVGElement>(targetInstance->correspondingElement()->cloneElementWithChildren());
692
693    // We don't walk the target tree element-by-element, and clone each element,
694    // but instead use cloneElementWithChildren(). This is an optimization for the common
695    // case where <use> doesn't contain disallowed elements (ie. <foreignObject>).
696    // Though if there are disallowed elements in the subtree, we have to remove them.
697    // For instance: <use> on <g> containing <foreignObject> (indirect case).
698    if (subtreeContainsDisallowedElement(*newChild))
699        removeDisallowedElementsFromSubtree(*newChild);
700
701    shadowRoot()->appendChild(newChild.release());
702}
703
704void SVGUseElement::expandUseElementsInShadowTree(Node* element)
705{
706    // Why expand the <use> elements in the shadow tree here, and not just
707    // do this directly in buildShadowTree, if we encounter a <use> element?
708    //
709    // Short answer: Because we may miss to expand some elements. Ie. if a <symbol>
710    // contains <use> tags, we'd miss them. So once we're done with settin' up the
711    // actual shadow tree (after the special case modification for svg/symbol) we have
712    // to walk it completely and expand all <use> elements.
713    if (element->hasTagName(SVGNames::useTag)) {
714        SVGUseElement* use = toSVGUseElement(element);
715        ASSERT(!use->cachedDocumentIsStillLoading());
716
717        ASSERT(referencedDocument());
718        Element* targetElement = SVGURIReference::targetElementFromIRIString(use->href(), *referencedDocument());
719        SVGElement* target = 0;
720        if (targetElement && targetElement->isSVGElement())
721            target = toSVGElement(targetElement);
722
723        // Don't ASSERT(target) here, it may be "pending", too.
724        // Setup sub-shadow tree root node
725        RefPtr<SVGGElement> cloneParent = SVGGElement::create(SVGNames::gTag, *referencedDocument());
726        use->cloneChildNodes(cloneParent.get());
727
728        // Spec: In the generated content, the 'use' will be replaced by 'g', where all attributes from the
729        // 'use' element except for x, y, width, height and xlink:href are transferred to the generated 'g' element.
730        transferUseAttributesToReplacedElement(use, cloneParent.get());
731
732        if (target && !isDisallowedElement(*target)) {
733            RefPtr<Element> newChild = target->cloneElementWithChildren();
734            ASSERT(newChild->isSVGElement());
735            cloneParent->appendChild(newChild.release());
736        }
737
738        // We don't walk the target tree element-by-element, and clone each element,
739        // but instead use cloneElementWithChildren(). This is an optimization for the common
740        // case where <use> doesn't contain disallowed elements (ie. <foreignObject>).
741        // Though if there are disallowed elements in the subtree, we have to remove them.
742        // For instance: <use> on <g> containing <foreignObject> (indirect case).
743        if (subtreeContainsDisallowedElement(*cloneParent))
744            removeDisallowedElementsFromSubtree(*cloneParent);
745
746        RefPtr<Node> replacingElement(cloneParent.get());
747
748        // Replace <use> with referenced content.
749        ASSERT(use->parentNode());
750        use->parentNode()->replaceChild(cloneParent.release(), use);
751
752        // Expand the siblings because the *element* is replaced and we will
753        // lose the sibling chain when we are back from recursion.
754        element = replacingElement.get();
755        for (RefPtr<Node> sibling = element->nextSibling(); sibling; sibling = sibling->nextSibling())
756            expandUseElementsInShadowTree(sibling.get());
757    }
758
759    for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
760        expandUseElementsInShadowTree(child.get());
761}
762
763void SVGUseElement::expandSymbolElementsInShadowTree(Node* element)
764{
765    if (element->hasTagName(SVGNames::symbolTag)) {
766        // Spec: The referenced 'symbol' and its contents are deep-cloned into the generated tree,
767        // with the exception that the 'symbol' is replaced by an 'svg'. This generated 'svg' will
768        // always have explicit values for attributes width and height. If attributes width and/or
769        // height are provided on the 'use' element, then these attributes will be transferred to
770        // the generated 'svg'. If attributes width and/or height are not specified, the generated
771        // 'svg' element will use values of 100% for these attributes.
772        RefPtr<SVGSVGElement> svgElement = SVGSVGElement::create(SVGNames::svgTag, *referencedDocument());
773
774        // Transfer all data (attributes, etc.) from <symbol> to the new <svg> element.
775        svgElement->cloneDataFromElement(*toElement(element));
776
777        // Only clone symbol children, and add them to the new <svg> element
778        for (Node* child = element->firstChild(); child; child = child->nextSibling()) {
779            RefPtr<Node> newChild = child->cloneNode(true);
780            svgElement->appendChild(newChild.release());
781        }
782
783        // We don't walk the target tree element-by-element, and clone each element,
784        // but instead use cloneNode(deep=true). This is an optimization for the common
785        // case where <use> doesn't contain disallowed elements (ie. <foreignObject>).
786        // Though if there are disallowed elements in the subtree, we have to remove them.
787        // For instance: <use> on <g> containing <foreignObject> (indirect case).
788        if (subtreeContainsDisallowedElement(*svgElement))
789            removeDisallowedElementsFromSubtree(*svgElement);
790
791        RefPtr<Node> replacingElement(svgElement.get());
792
793        // Replace <symbol> with <svg>.
794        element->parentNode()->replaceChild(svgElement.release(), element);
795
796        // Expand the siblings because the *element* is replaced and we will
797        // lose the sibling chain when we are back from recursion.
798        element = replacingElement.get();
799        for (RefPtr<Node> sibling = element->nextSibling(); sibling; sibling = sibling->nextSibling())
800            expandSymbolElementsInShadowTree(sibling.get());
801    }
802
803    for (RefPtr<Node> child = element->firstChild(); child; child = child->nextSibling())
804        expandSymbolElementsInShadowTree(child.get());
805}
806
807void SVGUseElement::transferEventListenersToShadowTree(SVGElementInstance* target)
808{
809    if (!target)
810        return;
811
812    SVGElement* originalElement = target->correspondingElement();
813    ASSERT(originalElement);
814
815    if (SVGElement* shadowTreeElement = target->shadowTreeElement()) {
816        if (EventTargetData* data = originalElement->eventTargetData())
817            data->eventListenerMap.copyEventListenersNotCreatedFromMarkupToTarget(shadowTreeElement);
818    }
819
820    for (SVGElementInstance* instance = target->firstChild(); instance; instance = instance->nextSibling())
821        transferEventListenersToShadowTree(instance);
822}
823
824void SVGUseElement::associateInstancesWithShadowTreeElements(Node* target, SVGElementInstance* targetInstance)
825{
826    if (!target || !targetInstance)
827        return;
828
829    SVGElement* originalElement = targetInstance->correspondingElement();
830
831    if (originalElement->hasTagName(SVGNames::useTag)) {
832        // <use> gets replaced by <g>
833        ASSERT(target->nodeName() == SVGNames::gTag);
834    } else if (originalElement->hasTagName(SVGNames::symbolTag)) {
835        // <symbol> gets replaced by <svg>
836        ASSERT(target->nodeName() == SVGNames::svgTag);
837    } else
838        ASSERT(target->nodeName() == originalElement->nodeName());
839
840    SVGElement* element = 0;
841    if (target->isSVGElement())
842        element = toSVGElement(target);
843
844    ASSERT(!targetInstance->shadowTreeElement());
845    targetInstance->setShadowTreeElement(element);
846    element->setCorrespondingElement(originalElement);
847
848    Node* node = target->firstChild();
849    for (SVGElementInstance* instance = targetInstance->firstChild(); node && instance; instance = instance->nextSibling()) {
850        // Skip any non-svg elements in shadow tree
851        while (node && !node->isSVGElement())
852           node = node->nextSibling();
853
854        if (!node)
855            break;
856
857        associateInstancesWithShadowTreeElements(node, instance);
858        node = node->nextSibling();
859    }
860}
861
862SVGElementInstance* SVGUseElement::instanceForShadowTreeElement(Node* element) const
863{
864    if (!m_targetElementInstance) {
865        ASSERT(!inDocument());
866        return 0;
867    }
868
869    return instanceForShadowTreeElement(element, m_targetElementInstance.get());
870}
871
872SVGElementInstance* SVGUseElement::instanceForShadowTreeElement(Node* element, SVGElementInstance* instance) const
873{
874    ASSERT(element);
875    ASSERT(instance);
876
877    // We're dispatching a mutation event during shadow tree construction
878    // this instance hasn't yet been associated to a shadowTree element.
879    if (!instance->shadowTreeElement())
880        return 0;
881
882    if (element == instance->shadowTreeElement())
883        return instance;
884
885    for (SVGElementInstance* current = instance->firstChild(); current; current = current->nextSibling()) {
886        if (SVGElementInstance* search = instanceForShadowTreeElement(element, current))
887            return search;
888    }
889
890    return 0;
891}
892
893void SVGUseElement::invalidateShadowTree()
894{
895    if (m_needsShadowTreeRecreation)
896        return;
897    m_needsShadowTreeRecreation = true;
898    setNeedsStyleRecalc(ReconstructRenderTree);
899    invalidateDependentShadowTrees();
900}
901
902void SVGUseElement::invalidateDependentShadowTrees()
903{
904    // Recursively invalidate dependent <use> shadow trees
905    const HashSet<SVGElementInstance*>& instances = instancesForElement();
906    const HashSet<SVGElementInstance*>::const_iterator end = instances.end();
907    for (HashSet<SVGElementInstance*>::const_iterator it = instances.begin(); it != end; ++it) {
908        if (SVGUseElement* element = (*it)->correspondingUseElement()) {
909            ASSERT(element->inDocument());
910            element->invalidateShadowTree();
911        }
912    }
913}
914
915void SVGUseElement::transferUseAttributesToReplacedElement(SVGElement* from, SVGElement* to) const
916{
917    ASSERT(from);
918    ASSERT(to);
919
920    to->cloneDataFromElement(*from);
921
922    to->removeAttribute(SVGNames::xAttr);
923    to->removeAttribute(SVGNames::yAttr);
924    to->removeAttribute(SVGNames::widthAttr);
925    to->removeAttribute(SVGNames::heightAttr);
926    to->removeAttribute(XLinkNames::hrefAttr);
927}
928
929bool SVGUseElement::selfHasRelativeLengths() const
930{
931    if (x().isRelative()
932     || y().isRelative()
933     || width().isRelative()
934     || height().isRelative())
935        return true;
936
937    if (!m_targetElementInstance)
938        return false;
939
940    SVGElement* element = m_targetElementInstance->correspondingElement();
941    if (!element)
942        return false;
943
944    return element->hasRelativeLengths();
945}
946
947void SVGUseElement::notifyFinished(CachedResource* resource)
948{
949    if (!inDocument())
950        return;
951
952    invalidateShadowTree();
953    if (resource->errorOccurred())
954        dispatchEvent(Event::create(eventNames().errorEvent, false, false));
955    else if (!resource->wasCanceled())
956        SVGExternalResourcesRequired::dispatchLoadEvent(this);
957}
958
959bool SVGUseElement::cachedDocumentIsStillLoading()
960{
961    if (m_cachedDocument && m_cachedDocument->isLoading())
962        return true;
963    return false;
964}
965
966bool SVGUseElement::instanceTreeIsLoading(SVGElementInstance* targetElementInstance)
967{
968    for (SVGElementInstance* instance = targetElementInstance->firstChild(); instance; instance = instance->nextSibling()) {
969        if (SVGUseElement* use = instance->correspondingUseElement()) {
970             if (use->cachedDocumentIsStillLoading())
971                 return true;
972        }
973        if (instance->hasChildNodes())
974            instanceTreeIsLoading(instance);
975    }
976    return false;
977}
978
979void SVGUseElement::finishParsingChildren()
980{
981    SVGGraphicsElement::finishParsingChildren();
982    SVGExternalResourcesRequired::finishParsingChildren();
983    if (m_wasInsertedByParser) {
984        buildPendingResource();
985        m_wasInsertedByParser = false;
986    }
987}
988
989void SVGUseElement::setCachedDocument(CachedResourceHandle<CachedSVGDocument> cachedDocument)
990{
991    if (m_cachedDocument == cachedDocument)
992        return;
993
994    if (m_cachedDocument)
995        m_cachedDocument->removeClient(this);
996
997    m_cachedDocument = cachedDocument;
998    if (m_cachedDocument)
999        m_cachedDocument->addClient(this);
1000}
1001
1002}
1003