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