Use "= default" to denote default constructor or destructor
[WebKit-https.git] / Source / WebCore / dom / TreeScope.cpp
1 /*
2  * Copyright (C) 2011 Google Inc. All Rights Reserved.
3  * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "TreeScope.h"
29
30 #include "Attr.h"
31 #include "DOMWindow.h"
32 #include "ElementIterator.h"
33 #include "FocusController.h"
34 #include "Frame.h"
35 #include "FrameView.h"
36 #include "HTMLAnchorElement.h"
37 #include "HTMLFrameOwnerElement.h"
38 #include "HTMLLabelElement.h"
39 #include "HTMLMapElement.h"
40 #include "HitTestResult.h"
41 #include "IdTargetObserverRegistry.h"
42 #include "NodeRareData.h"
43 #include "Page.h"
44 #include "PointerLockController.h"
45 #include "PseudoElement.h"
46 #include "RenderView.h"
47 #include "RuntimeEnabledFeatures.h"
48 #include "Settings.h"
49 #include "ShadowRoot.h"
50 #include <wtf/text/CString.h>
51
52 namespace WebCore {
53
54 struct SameSizeAsTreeScope {
55     void* pointers[8];
56 };
57
58 COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
59
60 using namespace HTMLNames;
61
62 TreeScope::TreeScope(ShadowRoot& shadowRoot, Document& document)
63     : m_rootNode(shadowRoot)
64     , m_documentScope(document)
65     , m_parentTreeScope(&document)
66     , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
67 {
68     shadowRoot.setTreeScope(*this);
69 }
70
71 TreeScope::TreeScope(Document& document)
72     : m_rootNode(document)
73     , m_documentScope(document)
74     , m_parentTreeScope(nullptr)
75     , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
76 {
77     document.setTreeScope(*this);
78 }
79
80 TreeScope::~TreeScope() = default;
81
82 void TreeScope::destroyTreeScopeData()
83 {
84     m_elementsById = nullptr;
85     m_imageMapsByName = nullptr;
86     m_labelsByForAttribute = nullptr;
87 }
88
89 void TreeScope::setParentTreeScope(TreeScope& newParentScope)
90 {
91     // A document node cannot be re-parented.
92     ASSERT(!m_rootNode.isDocumentNode());
93
94     m_parentTreeScope = &newParentScope;
95     setDocumentScope(newParentScope.documentScope());
96 }
97
98 Element* TreeScope::getElementById(const AtomicString& elementId) const
99 {
100     if (elementId.isNull())
101         return nullptr;
102     if (!m_elementsById)
103         return nullptr;
104     return m_elementsById->getElementById(*elementId.impl(), *this);
105 }
106
107 Element* TreeScope::getElementById(const String& elementId) const
108 {
109     if (!m_elementsById)
110         return nullptr;
111
112     if (RefPtr<AtomicStringImpl> atomicElementId = AtomicStringImpl::lookUp(elementId.impl()))
113         return m_elementsById->getElementById(*atomicElementId, *this);
114
115     return nullptr;
116 }
117
118 Element* TreeScope::getElementById(StringView elementId) const
119 {
120     if (!m_elementsById)
121         return nullptr;
122
123     if (auto atomicElementId = elementId.toExistingAtomicString())
124         return m_elementsById->getElementById(*atomicElementId, *this);
125
126     return nullptr;
127 }
128
129 const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& elementId) const
130 {
131     if (elementId.isEmpty())
132         return nullptr;
133     if (!m_elementsById)
134         return nullptr;
135     return m_elementsById->getAllElementsById(*elementId.impl(), *this);
136 }
137
138 void TreeScope::addElementById(const AtomicStringImpl& elementId, Element& element, bool notifyObservers)
139 {
140     if (!m_elementsById)
141         m_elementsById = std::make_unique<DocumentOrderedMap>();
142     m_elementsById->add(elementId, element, *this);
143     if (notifyObservers)
144         m_idTargetObserverRegistry->notifyObservers(elementId);
145 }
146
147 void TreeScope::removeElementById(const AtomicStringImpl& elementId, Element& element, bool notifyObservers)
148 {
149     if (!m_elementsById)
150         return;
151     m_elementsById->remove(elementId, element);
152     if (notifyObservers)
153         m_idTargetObserverRegistry->notifyObservers(elementId);
154 }
155
156 Element* TreeScope::getElementByName(const AtomicString& name) const
157 {
158     if (name.isEmpty())
159         return nullptr;
160     if (!m_elementsByName)
161         return nullptr;
162     return m_elementsByName->getElementByName(*name.impl(), *this);
163 }
164
165 void TreeScope::addElementByName(const AtomicStringImpl& name, Element& element)
166 {
167     if (!m_elementsByName)
168         m_elementsByName = std::make_unique<DocumentOrderedMap>();
169     m_elementsByName->add(name, element, *this);
170 }
171
172 void TreeScope::removeElementByName(const AtomicStringImpl& name, Element& element)
173 {
174     if (!m_elementsByName)
175         return;
176     m_elementsByName->remove(name, element);
177 }
178
179
180 Node& TreeScope::retargetToScope(Node& node) const
181 {
182     auto& scope = node.treeScope();
183     if (LIKELY(this == &scope || !node.isInShadowTree()))
184         return node;
185     ASSERT(is<ShadowRoot>(scope.rootNode()));
186
187     Vector<TreeScope*, 8> nodeTreeScopes;
188     for (auto* currentScope = &scope; currentScope; currentScope = currentScope->parentTreeScope())
189         nodeTreeScopes.append(currentScope);
190     ASSERT(nodeTreeScopes.size() >= 2);
191
192     Vector<const TreeScope*, 8> ancestorScopes;
193     for (auto* currentScope = this; currentScope; currentScope = currentScope->parentTreeScope())
194         ancestorScopes.append(currentScope);
195
196     size_t i = nodeTreeScopes.size();
197     size_t j = ancestorScopes.size();
198     while (i > 0 && j > 0 && nodeTreeScopes[i - 1] == ancestorScopes[j - 1]) {
199         --i;
200         --j;
201     }
202
203     bool nodeIsInOuterTreeScope = !i;
204     if (nodeIsInOuterTreeScope)
205         return node;
206
207     ShadowRoot& shadowRootInLowestCommonTreeScope = downcast<ShadowRoot>(nodeTreeScopes[i - 1]->rootNode());
208     return *shadowRootInLowestCommonTreeScope.host();
209 }
210
211 Node* TreeScope::ancestorNodeInThisScope(Node* node) const
212 {
213     for (; node; node = node->shadowHost()) {
214         if (&node->treeScope() == this)
215             return node;
216         if (!node->isInShadowTree())
217             return nullptr;
218     }
219     return nullptr;
220 }
221
222 Element* TreeScope::ancestorElementInThisScope(Element* element) const
223 {
224     for (; element; element = element->shadowHost()) {
225         if (&element->treeScope() == this)
226             return element;
227         if (!element->isInShadowTree())
228             return nullptr;
229     }
230     return nullptr;
231 }
232
233 void TreeScope::addImageMap(HTMLMapElement& imageMap)
234 {
235     AtomicStringImpl* name = imageMap.getName().impl();
236     if (!name)
237         return;
238     if (!m_imageMapsByName)
239         m_imageMapsByName = std::make_unique<DocumentOrderedMap>();
240     m_imageMapsByName->add(*name, imageMap, *this);
241 }
242
243 void TreeScope::removeImageMap(HTMLMapElement& imageMap)
244 {
245     if (!m_imageMapsByName)
246         return;
247     AtomicStringImpl* name = imageMap.getName().impl();
248     if (!name)
249         return;
250     m_imageMapsByName->remove(*name, imageMap);
251 }
252
253 HTMLMapElement* TreeScope::getImageMap(const String& url) const
254 {
255     if (!m_imageMapsByName)
256         return nullptr;
257     auto hashPosition = url.find('#');
258     if (hashPosition == notFound)
259         return nullptr;
260     String name = url.substring(hashPosition + 1);
261     if (name.isEmpty())
262         return nullptr;
263     return m_imageMapsByName->getElementByMapName(*AtomicString(name).impl(), *this);
264 }
265
266 void TreeScope::addLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
267 {
268     ASSERT(m_labelsByForAttribute);
269     m_labelsByForAttribute->add(forAttributeValue, element, *this);
270 }
271
272 void TreeScope::removeLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
273 {
274     ASSERT(m_labelsByForAttribute);
275     m_labelsByForAttribute->remove(forAttributeValue, element);
276 }
277
278 HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& forAttributeValue)
279 {
280     if (forAttributeValue.isEmpty())
281         return nullptr;
282
283     if (!m_labelsByForAttribute) {
284         // Populate the map on first access.
285         m_labelsByForAttribute = std::make_unique<DocumentOrderedMap>();
286
287         for (auto& label : descendantsOfType<HTMLLabelElement>(m_rootNode)) {
288             const AtomicString& forValue = label.attributeWithoutSynchronization(forAttr);
289             if (!forValue.isEmpty())
290                 addLabel(*forValue.impl(), label);
291         }
292     }
293
294     return m_labelsByForAttribute->getElementByLabelForAttribute(*forAttributeValue.impl(), *this);
295 }
296
297 static std::optional<LayoutPoint> absolutePointIfNotClipped(Document& document, const LayoutPoint& clientPoint)
298 {
299     auto* frame = document.frame();
300     auto* view = document.view();
301     if (!frame || !view)
302         return std::nullopt;
303
304     if (frame->settings().visualViewportEnabled()) {
305         document.updateLayout();
306         FloatPoint layoutViewportPoint = view->clientToLayoutViewportPoint(clientPoint);
307         FloatRect layoutViewportBounds({ }, view->layoutViewportRect().size());
308         if (!layoutViewportBounds.contains(layoutViewportPoint))
309             return std::nullopt;
310         return LayoutPoint(view->layoutViewportToAbsolutePoint(layoutViewportPoint));
311     }
312
313     float scaleFactor = frame->pageZoomFactor() * frame->frameScaleFactor();
314
315     LayoutPoint absolutePoint = clientPoint;
316     absolutePoint.scale(scaleFactor);
317     absolutePoint.moveBy(view->contentsScrollPosition());
318
319     LayoutRect visibleRect;
320 #if PLATFORM(IOS)
321     visibleRect = view->unobscuredContentRect();
322 #else
323     visibleRect = view->visibleContentRect();
324 #endif
325     if (visibleRect.contains(absolutePoint))
326         return absolutePoint;
327     return std::nullopt;
328 }
329
330 Node* TreeScope::nodeFromPoint(const LayoutPoint& clientPoint, LayoutPoint* localPoint)
331 {
332     auto absolutePoint = absolutePointIfNotClipped(documentScope(), clientPoint);
333     if (!absolutePoint)
334         return nullptr;
335
336     HitTestResult result(absolutePoint.value());
337     documentScope().renderView()->hitTest(HitTestRequest(), result);
338
339     if (localPoint)
340         *localPoint = result.localPoint();
341
342     return result.innerNode();
343 }
344
345 RefPtr<Element> TreeScope::elementFromPoint(double clientX, double clientY)
346 {
347     Document& document = documentScope();
348     if (!document.hasLivingRenderTree())
349         return nullptr;
350
351     Node* node = nodeFromPoint(LayoutPoint(clientX, clientY), nullptr);
352     if (!node)
353         return nullptr;
354
355     node = &retargetToScope(*node);
356     while (!is<Element>(*node)) {
357         node = node->parentInComposedTree();
358         if (!node)
359             break;
360         node = &retargetToScope(*node);
361     }
362
363     return downcast<Element>(node);
364 }
365
366 Vector<RefPtr<Element>> TreeScope::elementsFromPoint(double clientX, double clientY)
367 {
368     Vector<RefPtr<Element>> elements;
369
370     Document& document = documentScope();
371     if (!document.hasLivingRenderTree())
372         return elements;
373
374     auto absolutePoint = absolutePointIfNotClipped(document, LayoutPoint(clientX, clientY));
375     if (!absolutePoint)
376         return elements;
377
378     HitTestRequest request(HitTestRequest::ReadOnly
379         | HitTestRequest::Active
380         | HitTestRequest::DisallowUserAgentShadowContent
381         | HitTestRequest::CollectMultipleElements
382         | HitTestRequest::IncludeAllElementsUnderPoint);
383     HitTestResult result(absolutePoint.value());
384     documentScope().renderView()->hitTest(request, result);
385
386     Node* lastNode = nullptr;
387     for (auto listBasedNode : result.listBasedTestResult()) {
388         Node* node = listBasedNode.get();
389         node = &retargetToScope(*node);
390         while (!is<Element>(*node)) {
391             node = node->parentInComposedTree();
392             if (!node)
393                 break;
394             node = &retargetToScope(*node);
395         }
396
397         if (!node)
398             continue;
399
400         if (is<PseudoElement>(node))
401             node = downcast<PseudoElement>(*node).hostElement();
402
403         // Prune duplicate entries. A pseudo ::before content above its parent
404         // node should only result in one entry.
405         if (node == lastNode)
406             continue;
407
408         elements.append(downcast<Element>(node));
409         lastNode = node;
410     }
411
412     if (m_rootNode.isDocumentNode()) {
413         if (Element* rootElement = downcast<Document>(m_rootNode).documentElement()) {
414             if (elements.isEmpty() || elements.last() != rootElement)
415                 elements.append(rootElement);
416         }
417     }
418
419     return elements;
420 }
421
422 Element* TreeScope::findAnchor(const String& name)
423 {
424     if (name.isEmpty())
425         return nullptr;
426     if (Element* element = getElementById(name))
427         return element;
428     for (auto& anchor : descendantsOfType<HTMLAnchorElement>(m_rootNode)) {
429         if (m_rootNode.document().inQuirksMode()) {
430             // Quirks mode, ASCII case-insensitive comparison of names.
431             // FIXME: This behavior is not mentioned in the HTML specification.
432             // We should either remove this or get this into the specification.
433             if (equalIgnoringASCIICase(anchor.name(), name))
434                 return &anchor;
435         } else {
436             // Strict mode, names need to match exactly.
437             if (anchor.name() == name)
438                 return &anchor;
439         }
440     }
441     return nullptr;
442 }
443
444 static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
445 {
446     for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
447         if (focusedFrame->tree().parent() == currentFrame)
448             return focusedFrame->ownerElement();
449     }
450     return nullptr;
451 }
452
453 Element* TreeScope::focusedElementInScope()
454 {
455     Document& document = documentScope();
456     Element* element = document.focusedElement();
457
458     if (!element && document.page())
459         element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
460
461     return ancestorElementInThisScope(element);
462 }
463
464 #if ENABLE(POINTER_LOCK)
465
466 Element* TreeScope::pointerLockElement() const
467 {
468     Document& document = documentScope();
469     Page* page = document.page();
470     if (!page || page->pointerLockController().lockPending())
471         return nullptr;
472     auto* element = page->pointerLockController().element();
473     if (!element || &element->document() != &document)
474         return nullptr;
475     return ancestorElementInThisScope(element);
476 }
477
478 #endif
479
480 static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
481 {
482     while (true) {
483         treeScopes.append(&node->treeScope());
484         Element* ancestor = node->shadowHost();
485         if (!ancestor)
486             break;
487         node = ancestor;
488     }
489 }
490
491 TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
492 {
493     if (!nodeA || !nodeB)
494         return nullptr;
495
496     if (&nodeA->treeScope() == &nodeB->treeScope())
497         return &nodeA->treeScope();
498
499     Vector<TreeScope*, 5> treeScopesA;
500     listTreeScopes(nodeA, treeScopesA);
501
502     Vector<TreeScope*, 5> treeScopesB;
503     listTreeScopes(nodeB, treeScopesB);
504
505     size_t indexA = treeScopesA.size();
506     size_t indexB = treeScopesB.size();
507
508     for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
509
510     // If the nodes had no common tree scope, return immediately.
511     if (indexA == treeScopesA.size())
512         return nullptr;
513     
514     return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : nullptr;
515 }
516
517 } // namespace WebCore