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