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 AtomicString& 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<AtomicStringImpl> atomicElementId = AtomicStringImpl::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.toExistingAtomicString())
127 return m_elementsById->getElementById(*atomicElementId, *this);
128
129 return nullptr;
130}
131
132const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& 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 AtomicStringImpl& 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 AtomicStringImpl& 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 AtomicString& 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 AtomicStringImpl& 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 AtomicStringImpl& 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 AtomicStringImpl* 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 AtomicStringImpl* name = imageMap.getName().impl();
251 if (!name)
252 return;
253 m_imageMapsByName->remove(*name, imageMap);
254}
255
256HTMLMapElement* TreeScope::getImageMap(const AtomicString& 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 AtomicStringImpl& 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 AtomicStringImpl& name, HTMLImageElement& element)
271{
272 if (!m_imagesByUsemap)
273 return;
274 m_imagesByUsemap->remove(name, element);
275}
276
277HTMLImageElement* TreeScope::imageElementByUsemap(const AtomicStringImpl& name) const
278{
279 if (!m_imagesByUsemap)
280 return nullptr;
281 return m_imagesByUsemap->getElementByUsemap(name, *this);
282}
283
284void TreeScope::addLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
285{
286 ASSERT(m_labelsByForAttribute);
287 m_labelsByForAttribute->add(forAttributeValue, element, *this);
288}
289
290void TreeScope::removeLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
291{
292 ASSERT(m_labelsByForAttribute);
293 m_labelsByForAttribute->remove(forAttributeValue, element);
294}
295
296HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& 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 AtomicString& 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().renderView()->hitTest(HitTestRequest(), result);
360
361 if (localPoint)
362 *localPoint = result.localPoint();
363
364 return result.innerNode();
365}
366
367RefPtr<Element> TreeScope::elementFromPoint(double clientX, double clientY)
368{
369 Document& document = documentScope();
370 if (!document.hasLivingRenderTree())
371 return nullptr;
372
373 Node* node = nodeFromPoint(LayoutPoint(clientX, clientY), nullptr);
374 if (!node)
375 return nullptr;
376
377 node = &retargetToScope(*node);
378 while (!is<Element>(*node)) {
379 node = node->parentInComposedTree();
380 if (!node)
381 break;
382 node = &retargetToScope(*node);
383 }
384
385 return downcast<Element>(node);
386}
387
388Vector<RefPtr<Element>> TreeScope::elementsFromPoint(double clientX, double clientY)
389{
390 Vector<RefPtr<Element>> elements;
391
392 Document& document = documentScope();
393 if (!document.hasLivingRenderTree())
394 return elements;
395
396 auto absolutePoint = absolutePointIfNotClipped(document, LayoutPoint(clientX, clientY));
397 if (!absolutePoint)
398 return elements;
399
400 HitTestRequest request(HitTestRequest::ReadOnly
401 | HitTestRequest::Active
402 | HitTestRequest::DisallowUserAgentShadowContent
403 | HitTestRequest::CollectMultipleElements
404 | HitTestRequest::IncludeAllElementsUnderPoint);
405 HitTestResult result(absolutePoint.value());
406 documentScope().renderView()->hitTest(request, result);
407
408 Node* lastNode = nullptr;
409 for (const auto& listBasedNode : result.listBasedTestResult()) {
410 Node* node = listBasedNode.get();
411 node = &retargetToScope(*node);
412 while (!is<Element>(*node)) {
413 node = node->parentInComposedTree();
414 if (!node)
415 break;
416 node = &retargetToScope(*node);
417 }
418
419 if (!node)
420 continue;
421
422 if (is<PseudoElement>(node))
423 node = downcast<PseudoElement>(*node).hostElement();
424
425 // Prune duplicate entries. A pseudo ::before content above its parent
426 // node should only result in one entry.
427 if (node == lastNode)
428 continue;
429
430 elements.append(downcast<Element>(node));
431 lastNode = node;
432 }
433
434 if (m_rootNode.isDocumentNode()) {
435 if (Element* rootElement = downcast<Document>(m_rootNode).documentElement()) {
436 if (elements.isEmpty() || elements.last() != rootElement)
437 elements.append(rootElement);
438 }
439 }
440
441 return elements;
442}
443
444Vector<RefPtr<Element>> TreeScope::elementsFromPoint(const FloatPoint& p)
445{
446 return elementsFromPoint(p.x(), p.y());
447}
448
449Element* TreeScope::findAnchor(const String& name)
450{
451 if (name.isEmpty())
452 return nullptr;
453 if (Element* element = getElementById(name))
454 return element;
455 for (auto& anchor : descendantsOfType<HTMLAnchorElement>(m_rootNode)) {
456 if (m_rootNode.document().inQuirksMode()) {
457 // Quirks mode, ASCII case-insensitive comparison of names.
458 // FIXME: This behavior is not mentioned in the HTML specification.
459 // We should either remove this or get this into the specification.
460 if (equalIgnoringASCIICase(anchor.name(), name))
461 return &anchor;
462 } else {
463 // Strict mode, names need to match exactly.
464 if (anchor.name() == name)
465 return &anchor;
466 }
467 }
468 return nullptr;
469}
470
471static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
472{
473 for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
474 if (focusedFrame->tree().parent() == currentFrame)
475 return focusedFrame->ownerElement();
476 }
477 return nullptr;
478}
479
480Element* TreeScope::focusedElementInScope()
481{
482 Document& document = documentScope();
483 Element* element = document.focusedElement();
484
485 if (!element && document.page())
486 element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
487
488 return ancestorElementInThisScope(element);
489}
490
491#if ENABLE(POINTER_LOCK)
492
493Element* TreeScope::pointerLockElement() const
494{
495 Document& document = documentScope();
496 Page* page = document.page();
497 if (!page || page->pointerLockController().lockPending())
498 return nullptr;
499 auto* element = page->pointerLockController().element();
500 if (!element || &element->document() != &document)
501 return nullptr;
502 return ancestorElementInThisScope(element);
503}
504
505#endif
506
507static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
508{
509 while (true) {
510 treeScopes.append(&node->treeScope());
511 Element* ancestor = node->shadowHost();
512 if (!ancestor)
513 break;
514 node = ancestor;
515 }
516}
517
518TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
519{
520 if (!nodeA || !nodeB)
521 return nullptr;
522
523 if (&nodeA->treeScope() == &nodeB->treeScope())
524 return &nodeA->treeScope();
525
526 Vector<TreeScope*, 5> treeScopesA;
527 listTreeScopes(nodeA, treeScopesA);
528
529 Vector<TreeScope*, 5> treeScopesB;
530 listTreeScopes(nodeB, treeScopesB);
531
532 size_t indexA = treeScopesA.size();
533 size_t indexB = treeScopesB.size();
534
535 for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
536
537 // If the nodes had no common tree scope, return immediately.
538 if (indexA == treeScopesA.size())
539 return nullptr;
540
541 return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : nullptr;
542}
543
544} // namespace WebCore
545