Rename AtomicString to AtomString
[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 "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
53 namespace WebCore {
54
55 struct SameSizeAsTreeScope {
56     void* pointers[9];
57 };
58
59 COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
60
61 using namespace HTMLNames;
62
63 TreeScope::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
72 TreeScope::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
81 TreeScope::~TreeScope() = default;
82
83 void 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
92 void 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
101 Element* 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
110 Element* 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
121 Element* 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
132 const 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
141 void 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
150 void 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
159 Element* 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
168 void 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
175 void TreeScope::removeElementByName(const AtomStringImpl& name, Element& element)
176 {
177     if (!m_elementsByName)
178         return;
179     m_elementsByName->remove(name, element);
180 }
181
182
183 Node& 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
214 Node* 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
225 Element* 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
236 void 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
246 void 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
256 HTMLMapElement* 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
263 void 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
270 void TreeScope::removeImageElementByUsemap(const AtomStringImpl& name, HTMLImageElement& element)
271 {
272     if (!m_imagesByUsemap)
273         return;
274     m_imagesByUsemap->remove(name, element);
275 }
276
277 HTMLImageElement* TreeScope::imageElementByUsemap(const AtomStringImpl& name) const
278 {
279     if (!m_imagesByUsemap)
280         return nullptr;
281     return m_imagesByUsemap->getElementByUsemap(name, *this);
282 }
283
284 void TreeScope::addLabel(const AtomStringImpl& forAttributeValue, HTMLLabelElement& element)
285 {
286     ASSERT(m_labelsByForAttribute);
287     m_labelsByForAttribute->add(forAttributeValue, element, *this);
288 }
289
290 void TreeScope::removeLabel(const AtomStringImpl& forAttributeValue, HTMLLabelElement& element)
291 {
292     ASSERT(m_labelsByForAttribute);
293     m_labelsByForAttribute->remove(forAttributeValue, element);
294 }
295
296 HTMLLabelElement* 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
315 static 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
352 Node* 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
365 RefPtr<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
386 Vector<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
442 Vector<RefPtr<Element>> TreeScope::elementsFromPoint(const FloatPoint& p)
443 {
444     return elementsFromPoint(p.x(), p.y());
445 }
446
447 Element* 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
469 static 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
478 Element* 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
491 Element* 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
505 static 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
516 TreeScope* 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