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 "HTMLImageElement.h"
39#include "HTMLLabelElement.h"
40#include "HTMLMapElement.h"
41#include "HitTestResult.h"
42#include "IdTargetObserverRegistry.h"
43#include "NodeRareData.h"
44#include "Page.h"
45#include "PointerLockController.h"
46#include "PseudoElement.h"
47#include "RenderView.h"
48#include "RuntimeEnabledFeatures.h"
49#include "Settings.h"
50#include "ShadowRoot.h"
51#include <wtf/text/CString.h>
52
53namespace WebCore {
54
55struct SameSizeAsTreeScope {
56 void* pointers[9];
57};
58
59COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
60
61using namespace HTMLNames;
62
63TreeScope::TreeScope(ShadowRoot& shadowRoot, Document& document)
64 : m_rootNode(shadowRoot)
65 , m_documentScope(document)
66 , m_parentTreeScope(&document)
67 , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
68{
69 shadowRoot.setTreeScope(*this);
70}
71
72TreeScope::TreeScope(Document& document)
73 : m_rootNode(document)
74 , m_documentScope(document)
75 , m_parentTreeScope(nullptr)
76 , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
77{
78 document.setTreeScope(*this);
79}
80
81TreeScope::~TreeScope() = default;
82
83void TreeScope::destroyTreeScopeData()
84{
85 m_elementsById = nullptr;
86 m_elementsByName = nullptr;
87 m_imageMapsByName = nullptr;
88 m_imagesByUsemap = nullptr;
89 m_labelsByForAttribute = nullptr;
90}
91
92void TreeScope::setParentTreeScope(TreeScope& newParentScope)
93{
94 // A document node cannot be re-parented.
95 ASSERT(!m_rootNode.isDocumentNode());
96
97 m_parentTreeScope = &newParentScope;
98 setDocumentScope(newParentScope.documentScope());
99}
100
101Element* TreeScope::getElementById(const AtomString& elementId) const
102{
103 if (elementId.isNull())
104 return nullptr;
105 if (!m_elementsById)
106 return nullptr;
107 return m_elementsById->getElementById(*elementId.impl(), *this);
108}
109
110Element* TreeScope::getElementById(const String& elementId) const
111{
112 if (!m_elementsById)
113 return nullptr;
114
115 if (RefPtr<AtomStringImpl> atomicElementId = AtomStringImpl::lookUp(elementId.impl()))
116 return m_elementsById->getElementById(*atomicElementId, *this);
117
118 return nullptr;
119}
120
121Element* TreeScope::getElementById(StringView elementId) const
122{
123 if (!m_elementsById)
124 return nullptr;
125
126 if (auto atomicElementId = elementId.toExistingAtomString())
127 return m_elementsById->getElementById(*atomicElementId, *this);
128
129 return nullptr;
130}
131
132const Vector<Element*>* TreeScope::getAllElementsById(const AtomString& elementId) const
133{
134 if (elementId.isEmpty())
135 return nullptr;
136 if (!m_elementsById)
137 return nullptr;
138 return m_elementsById->getAllElementsById(*elementId.impl(), *this);
139}
140
141void TreeScope::addElementById(const AtomStringImpl& elementId, Element& element, bool notifyObservers)
142{
143 if (!m_elementsById)
144 m_elementsById = std::make_unique<TreeScopeOrderedMap>();
145 m_elementsById->add(elementId, element, *this);
146 if (notifyObservers)
147 m_idTargetObserverRegistry->notifyObservers(elementId);
148}
149
150void TreeScope::removeElementById(const AtomStringImpl& elementId, Element& element, bool notifyObservers)
151{
152 if (!m_elementsById)
153 return;
154 m_elementsById->remove(elementId, element);
155 if (notifyObservers)
156 m_idTargetObserverRegistry->notifyObservers(elementId);
157}
158
159Element* TreeScope::getElementByName(const AtomString& name) const
160{
161 if (name.isEmpty())
162 return nullptr;
163 if (!m_elementsByName)
164 return nullptr;
165 return m_elementsByName->getElementByName(*name.impl(), *this);
166}
167
168void TreeScope::addElementByName(const AtomStringImpl& name, Element& element)
169{
170 if (!m_elementsByName)
171 m_elementsByName = std::make_unique<TreeScopeOrderedMap>();
172 m_elementsByName->add(name, element, *this);
173}
174
175void TreeScope::removeElementByName(const AtomStringImpl& name, Element& element)
176{
177 if (!m_elementsByName)
178 return;
179 m_elementsByName->remove(name, element);
180}
181
182
183Node& TreeScope::retargetToScope(Node& node) const
184{
185 auto& scope = node.treeScope();
186 if (LIKELY(this == &scope || !node.isInShadowTree()))
187 return node;
188 ASSERT(is<ShadowRoot>(scope.rootNode()));
189
190 Vector<TreeScope*, 8> nodeTreeScopes;
191 for (auto* currentScope = &scope; currentScope; currentScope = currentScope->parentTreeScope())
192 nodeTreeScopes.append(currentScope);
193 ASSERT(nodeTreeScopes.size() >= 2);
194
195 Vector<const TreeScope*, 8> ancestorScopes;
196 for (auto* currentScope = this; currentScope; currentScope = currentScope->parentTreeScope())
197 ancestorScopes.append(currentScope);
198
199 size_t i = nodeTreeScopes.size();
200 size_t j = ancestorScopes.size();
201 while (i > 0 && j > 0 && nodeTreeScopes[i - 1] == ancestorScopes[j - 1]) {
202 --i;
203 --j;
204 }
205
206 bool nodeIsInOuterTreeScope = !i;
207 if (nodeIsInOuterTreeScope)
208 return node;
209
210 ShadowRoot& shadowRootInLowestCommonTreeScope = downcast<ShadowRoot>(nodeTreeScopes[i - 1]->rootNode());
211 return *shadowRootInLowestCommonTreeScope.host();
212}
213
214Node* TreeScope::ancestorNodeInThisScope(Node* node) const
215{
216 for (; node; node = node->shadowHost()) {
217 if (&node->treeScope() == this)
218 return node;
219 if (!node->isInShadowTree())
220 return nullptr;
221 }
222 return nullptr;
223}
224
225Element* TreeScope::ancestorElementInThisScope(Element* element) const
226{
227 for (; element; element = element->shadowHost()) {
228 if (&element->treeScope() == this)
229 return element;
230 if (!element->isInShadowTree())
231 return nullptr;
232 }
233 return nullptr;
234}
235
236void TreeScope::addImageMap(HTMLMapElement& imageMap)
237{
238 AtomStringImpl* name = imageMap.getName().impl();
239 if (!name)
240 return;
241 if (!m_imageMapsByName)
242 m_imageMapsByName = std::make_unique<TreeScopeOrderedMap>();
243 m_imageMapsByName->add(*name, imageMap, *this);
244}
245
246void TreeScope::removeImageMap(HTMLMapElement& imageMap)
247{
248 if (!m_imageMapsByName)
249 return;
250 AtomStringImpl* name = imageMap.getName().impl();
251 if (!name)
252 return;
253 m_imageMapsByName->remove(*name, imageMap);
254}
255
256HTMLMapElement* TreeScope::getImageMap(const AtomString& name) const
257{
258 if (!m_imageMapsByName || !name.impl())
259 return nullptr;
260 return m_imageMapsByName->getElementByMapName(*name.impl(), *this);
261}
262
263void TreeScope::addImageElementByUsemap(const AtomStringImpl& name, HTMLImageElement& element)
264{
265 if (!m_imagesByUsemap)
266 m_imagesByUsemap = std::make_unique<TreeScopeOrderedMap>();
267 return m_imagesByUsemap->add(name, element, *this);
268}
269
270void TreeScope::removeImageElementByUsemap(const AtomStringImpl& name, HTMLImageElement& element)
271{
272 if (!m_imagesByUsemap)
273 return;
274 m_imagesByUsemap->remove(name, element);
275}
276
277HTMLImageElement* TreeScope::imageElementByUsemap(const AtomStringImpl& name) const
278{
279 if (!m_imagesByUsemap)
280 return nullptr;
281 return m_imagesByUsemap->getElementByUsemap(name, *this);
282}
283
284void TreeScope::addLabel(const AtomStringImpl& forAttributeValue, HTMLLabelElement& element)
285{
286 ASSERT(m_labelsByForAttribute);
287 m_labelsByForAttribute->add(forAttributeValue, element, *this);
288}
289
290void TreeScope::removeLabel(const AtomStringImpl& forAttributeValue, HTMLLabelElement& element)
291{
292 ASSERT(m_labelsByForAttribute);
293 m_labelsByForAttribute->remove(forAttributeValue, element);
294}
295
296HTMLLabelElement* TreeScope::labelElementForId(const AtomString& forAttributeValue)
297{
298 if (forAttributeValue.isEmpty())
299 return nullptr;
300
301 if (!m_labelsByForAttribute) {
302 // Populate the map on first access.
303 m_labelsByForAttribute = std::make_unique<TreeScopeOrderedMap>();
304
305 for (auto& label : descendantsOfType<HTMLLabelElement>(m_rootNode)) {
306 const AtomString& forValue = label.attributeWithoutSynchronization(forAttr);
307 if (!forValue.isEmpty())
308 addLabel(*forValue.impl(), label);
309 }
310 }
311
312 return m_labelsByForAttribute->getElementByLabelForAttribute(*forAttributeValue.impl(), *this);
313}
314
315static Optional<LayoutPoint> absolutePointIfNotClipped(Document& document, const LayoutPoint& clientPoint)
316{
317 if (!document.frame() || !document.view())
318 return WTF::nullopt;
319
320 const auto& settings = document.frame()->settings();
321 if (settings.visualViewportEnabled() && settings.clientCoordinatesRelativeToLayoutViewport()) {
322 document.updateLayout();
323 if (!document.view() || !document.hasLivingRenderTree())
324 return WTF::nullopt;
325 auto* view = document.view();
326 FloatPoint layoutViewportPoint = view->clientToLayoutViewportPoint(clientPoint);
327 FloatRect layoutViewportBounds({ }, view->layoutViewportRect().size());
328 if (!layoutViewportBounds.contains(layoutViewportPoint))
329 return WTF::nullopt;
330 return LayoutPoint(view->layoutViewportToAbsolutePoint(layoutViewportPoint));
331 }
332
333 auto* frame = document.frame();
334 auto* view = document.view();
335 float scaleFactor = frame->pageZoomFactor() * frame->frameScaleFactor();
336
337 LayoutPoint absolutePoint = clientPoint;
338 absolutePoint.scale(scaleFactor);
339 absolutePoint.moveBy(view->contentsScrollPosition());
340
341 LayoutRect visibleRect;
342#if PLATFORM(IOS_FAMILY)
343 visibleRect = view->unobscuredContentRect();
344#else
345 visibleRect = view->visibleContentRect();
346#endif
347 if (visibleRect.contains(absolutePoint))
348 return absolutePoint;
349 return WTF::nullopt;
350}
351
352Node* TreeScope::nodeFromPoint(const LayoutPoint& clientPoint, LayoutPoint* localPoint)
353{
354 auto absolutePoint = absolutePointIfNotClipped(documentScope(), clientPoint);
355 if (!absolutePoint)
356 return nullptr;
357
358 HitTestResult result(absolutePoint.value());
359 documentScope().hitTest(HitTestRequest(), result);
360 if (localPoint)
361 *localPoint = result.localPoint();
362 return result.innerNode();
363}
364
365RefPtr<Element> TreeScope::elementFromPoint(double clientX, double clientY)
366{
367 Document& document = documentScope();
368 if (!document.hasLivingRenderTree())
369 return nullptr;
370
371 Node* node = nodeFromPoint(LayoutPoint(clientX, clientY), nullptr);
372 if (!node)
373 return nullptr;
374
375 node = &retargetToScope(*node);
376 while (!is<Element>(*node)) {
377 node = node->parentInComposedTree();
378 if (!node)
379 break;
380 node = &retargetToScope(*node);
381 }
382
383 return downcast<Element>(node);
384}
385
386Vector<RefPtr<Element>> TreeScope::elementsFromPoint(double clientX, double clientY)
387{
388 Vector<RefPtr<Element>> elements;
389
390 Document& document = documentScope();
391 if (!document.hasLivingRenderTree())
392 return elements;
393
394 auto absolutePoint = absolutePointIfNotClipped(document, LayoutPoint(clientX, clientY));
395 if (!absolutePoint)
396 return elements;
397
398 HitTestRequest request(HitTestRequest::ReadOnly
399 | HitTestRequest::Active
400 | HitTestRequest::DisallowUserAgentShadowContent
401 | HitTestRequest::CollectMultipleElements
402 | HitTestRequest::IncludeAllElementsUnderPoint);
403 HitTestResult result(absolutePoint.value());
404 documentScope().hitTest(request, result);
405
406 Node* lastNode = nullptr;
407 for (const auto& listBasedNode : result.listBasedTestResult()) {
408 Node* node = listBasedNode.get();
409 node = &retargetToScope(*node);
410 while (!is<Element>(*node)) {
411 node = node->parentInComposedTree();
412 if (!node)
413 break;
414 node = &retargetToScope(*node);
415 }
416
417 if (!node)
418 continue;
419
420 if (is<PseudoElement>(node))
421 node = downcast<PseudoElement>(*node).hostElement();
422
423 // Prune duplicate entries. A pseudo ::before content above its parent
424 // node should only result in one entry.
425 if (node == lastNode)
426 continue;
427
428 elements.append(downcast<Element>(node));
429 lastNode = node;
430 }
431
432 if (m_rootNode.isDocumentNode()) {
433 if (Element* rootElement = downcast<Document>(m_rootNode).documentElement()) {
434 if (elements.isEmpty() || elements.last() != rootElement)
435 elements.append(rootElement);
436 }
437 }
438
439 return elements;
440}
441
442Vector<RefPtr<Element>> TreeScope::elementsFromPoint(const FloatPoint& p)
443{
444 return elementsFromPoint(p.x(), p.y());
445}
446
447Element* TreeScope::findAnchor(const String& name)
448{
449 if (name.isEmpty())
450 return nullptr;
451 if (Element* element = getElementById(name))
452 return element;
453 for (auto& anchor : descendantsOfType<HTMLAnchorElement>(m_rootNode)) {
454 if (m_rootNode.document().inQuirksMode()) {
455 // Quirks mode, ASCII case-insensitive comparison of names.
456 // FIXME: This behavior is not mentioned in the HTML specification.
457 // We should either remove this or get this into the specification.
458 if (equalIgnoringASCIICase(anchor.name(), name))
459 return &anchor;
460 } else {
461 // Strict mode, names need to match exactly.
462 if (anchor.name() == name)
463 return &anchor;
464 }
465 }
466 return nullptr;
467}
468
469static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
470{
471 for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
472 if (focusedFrame->tree().parent() == currentFrame)
473 return focusedFrame->ownerElement();
474 }
475 return nullptr;
476}
477
478Element* TreeScope::focusedElementInScope()
479{
480 Document& document = documentScope();
481 Element* element = document.focusedElement();
482
483 if (!element && document.page())
484 element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
485
486 return ancestorElementInThisScope(element);
487}
488
489#if ENABLE(POINTER_LOCK)
490
491Element* TreeScope::pointerLockElement() const
492{
493 Document& document = documentScope();
494 Page* page = document.page();
495 if (!page || page->pointerLockController().lockPending())
496 return nullptr;
497 auto* element = page->pointerLockController().element();
498 if (!element || &element->document() != &document)
499 return nullptr;
500 return ancestorElementInThisScope(element);
501}
502
503#endif
504
505static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
506{
507 while (true) {
508 treeScopes.append(&node->treeScope());
509 Element* ancestor = node->shadowHost();
510 if (!ancestor)
511 break;
512 node = ancestor;
513 }
514}
515
516TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
517{
518 if (!nodeA || !nodeB)
519 return nullptr;
520
521 if (&nodeA->treeScope() == &nodeB->treeScope())
522 return &nodeA->treeScope();
523
524 Vector<TreeScope*, 5> treeScopesA;
525 listTreeScopes(nodeA, treeScopesA);
526
527 Vector<TreeScope*, 5> treeScopesB;
528 listTreeScopes(nodeB, treeScopesB);
529
530 size_t indexA = treeScopesA.size();
531 size_t indexB = treeScopesB.size();
532
533 for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
534
535 // If the nodes had no common tree scope, return immediately.
536 if (indexA == treeScopesA.size())
537 return nullptr;
538
539 return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : nullptr;
540}
541
542} // namespace WebCore
543