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 "DOMSelection.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 "Page.h"
43#include "RenderView.h"
44#include "RuntimeEnabledFeatures.h"
45#include "ShadowRoot.h"
46#include "TreeScopeAdopter.h"
47#include <wtf/text/CString.h>
48
49namespace WebCore {
50
51struct SameSizeAsTreeScope {
52    void* pointers[9];
53};
54
55COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
56
57using namespace HTMLNames;
58
59TreeScope::TreeScope(ShadowRoot& shadowRoot, Document& document)
60    : m_rootNode(shadowRoot)
61    , m_documentScope(&document)
62    , m_parentTreeScope(&document)
63    , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
64{
65    shadowRoot.setTreeScope(*this);
66}
67
68TreeScope::TreeScope(Document& document)
69    : m_rootNode(document)
70    , m_documentScope(&document)
71    , m_parentTreeScope(nullptr)
72    , m_idTargetObserverRegistry(std::make_unique<IdTargetObserverRegistry>())
73{
74    document.setTreeScope(*this);
75}
76
77TreeScope::~TreeScope()
78{
79    if (m_selection) {
80        m_selection->clearTreeScope();
81        m_selection = nullptr;
82    }
83}
84
85void TreeScope::destroyTreeScopeData()
86{
87    m_elementsById = nullptr;
88    m_imageMapsByName = 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    // Every scope other than document needs a parent scope.
97    ASSERT(newParentScope);
98
99    m_parentTreeScope = newParentScope;
100    setDocumentScope(&newParentScope->documentScope());
101}
102
103Element* TreeScope::getElementById(const AtomicString& elementId) const
104{
105    if (elementId.isNull())
106        return nullptr;
107    if (!m_elementsById)
108        return nullptr;
109    return m_elementsById->getElementById(*elementId.impl(), *this);
110}
111
112Element* TreeScope::getElementById(const String& elementId) const
113{
114    if (!m_elementsById)
115        return nullptr;
116
117    if (AtomicStringImpl* atomicElementId = AtomicString::find(elementId.impl()))
118        return m_elementsById->getElementById(*atomicElementId, *this);
119
120    return nullptr;
121}
122
123const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& elementId) const
124{
125    if (elementId.isEmpty())
126        return nullptr;
127    if (!m_elementsById)
128        return nullptr;
129    return m_elementsById->getAllElementsById(*elementId.impl(), *this);
130}
131
132void TreeScope::addElementById(const AtomicStringImpl& elementId, Element& element)
133{
134    if (!m_elementsById)
135        m_elementsById = std::make_unique<DocumentOrderedMap>();
136    m_elementsById->add(elementId, element, *this);
137    m_idTargetObserverRegistry->notifyObservers(elementId);
138}
139
140void TreeScope::removeElementById(const AtomicStringImpl& elementId, Element& element)
141{
142    if (!m_elementsById)
143        return;
144    m_elementsById->remove(elementId, element);
145    m_idTargetObserverRegistry->notifyObservers(elementId);
146}
147
148Element* TreeScope::getElementByName(const AtomicString& name) const
149{
150    if (name.isEmpty())
151        return nullptr;
152    if (!m_elementsByName)
153        return nullptr;
154    return m_elementsByName->getElementByName(*name.impl(), *this);
155}
156
157void TreeScope::addElementByName(const AtomicStringImpl& name, Element& element)
158{
159    if (!m_elementsByName)
160        m_elementsByName = std::make_unique<DocumentOrderedMap>();
161    m_elementsByName->add(name, element, *this);
162}
163
164void TreeScope::removeElementByName(const AtomicStringImpl& name, Element& element)
165{
166    if (!m_elementsByName)
167        return;
168    m_elementsByName->remove(name, element);
169}
170
171Node* TreeScope::ancestorInThisScope(Node* node) const
172{
173    for (; node; node = node->shadowHost()) {
174        if (&node->treeScope() == this)
175            return node;
176        if (!node->isInShadowTree())
177            return nullptr;
178    }
179    return nullptr;
180}
181
182void TreeScope::addImageMap(HTMLMapElement& imageMap)
183{
184    AtomicStringImpl* name = imageMap.getName().impl();
185    if (!name)
186        return;
187    if (!m_imageMapsByName)
188        m_imageMapsByName = std::make_unique<DocumentOrderedMap>();
189    m_imageMapsByName->add(*name, imageMap, *this);
190}
191
192void TreeScope::removeImageMap(HTMLMapElement& imageMap)
193{
194    if (!m_imageMapsByName)
195        return;
196    AtomicStringImpl* name = imageMap.getName().impl();
197    if (!name)
198        return;
199    m_imageMapsByName->remove(*name, imageMap);
200}
201
202HTMLMapElement* TreeScope::getImageMap(const String& url) const
203{
204    if (url.isNull())
205        return nullptr;
206    if (!m_imageMapsByName)
207        return nullptr;
208    size_t hashPos = url.find('#');
209    String name = (hashPos == notFound ? url : url.substring(hashPos + 1)).impl();
210    if (name.isEmpty())
211        return nullptr;
212    if (m_rootNode.document().isHTMLDocument()) {
213        AtomicString lowercasedName = name.lower();
214        return m_imageMapsByName->getElementByLowercasedMapName(*lowercasedName.impl(), *this);
215    }
216    return m_imageMapsByName->getElementByMapName(*AtomicString(name).impl(), *this);
217}
218
219Node* nodeFromPoint(Document* document, int x, int y, LayoutPoint* localPoint)
220{
221    Frame* frame = document->frame();
222
223    if (!frame)
224        return nullptr;
225    FrameView* frameView = frame->view();
226    if (!frameView)
227        return nullptr;
228
229    float scaleFactor = frame->pageZoomFactor() * frame->frameScaleFactor();
230
231    IntPoint scrollPosition = frameView->contentsScrollPosition();
232    IntPoint point = roundedIntPoint(FloatPoint(x * scaleFactor  + scrollPosition.x(), y * scaleFactor + scrollPosition.y()));
233
234    IntRect visibleRect;
235#if PLATFORM(IOS)
236    visibleRect = frameView->unobscuredContentRect();
237#else
238    visibleRect = frameView->visibleContentRect();
239#endif
240    if (!visibleRect.contains(point))
241        return nullptr;
242
243    HitTestRequest request(HitTestRequest::ReadOnly | HitTestRequest::Active | HitTestRequest::DisallowShadowContent);
244    HitTestResult result(point);
245    document->renderView()->hitTest(request, result);
246
247    if (localPoint)
248        *localPoint = result.localPoint();
249
250    return result.innerNode();
251}
252
253Element* TreeScope::elementFromPoint(int x, int y) const
254{
255    Node* node = nodeFromPoint(&m_rootNode.document(), x, y);
256    while (node && !node->isElementNode())
257        node = node->parentNode();
258    if (node)
259        node = ancestorInThisScope(node);
260    return toElement(node);
261}
262
263void TreeScope::addLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
264{
265    ASSERT(m_labelsByForAttribute);
266    m_labelsByForAttribute->add(forAttributeValue, element, *this);
267}
268
269void TreeScope::removeLabel(const AtomicStringImpl& forAttributeValue, HTMLLabelElement& element)
270{
271    ASSERT(m_labelsByForAttribute);
272    m_labelsByForAttribute->remove(forAttributeValue, element);
273}
274
275HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& forAttributeValue)
276{
277    if (forAttributeValue.isEmpty())
278        return nullptr;
279
280    if (!m_labelsByForAttribute) {
281        // Populate the map on first access.
282        m_labelsByForAttribute = std::make_unique<DocumentOrderedMap>();
283
284        for (auto& label : descendantsOfType<HTMLLabelElement>(m_rootNode)) {
285            const AtomicString& forValue = label.fastGetAttribute(forAttr);
286            if (!forValue.isEmpty())
287                addLabel(*forValue.impl(), label);
288        }
289    }
290
291    return m_labelsByForAttribute->getElementByLabelForAttribute(*forAttributeValue.impl(), *this);
292}
293
294DOMSelection* TreeScope::getSelection() const
295{
296    if (!m_rootNode.document().frame())
297        return nullptr;
298
299    if (m_selection)
300        return m_selection.get();
301
302    if (this != &m_rootNode.document())
303        return m_rootNode.document().getSelection();
304
305    m_selection = DOMSelection::create(&m_rootNode.document());
306    return m_selection.get();
307}
308
309Element* TreeScope::findAnchor(const String& name)
310{
311    if (name.isEmpty())
312        return nullptr;
313    if (Element* element = getElementById(name))
314        return element;
315    for (auto& anchor : descendantsOfType<HTMLAnchorElement>(m_rootNode)) {
316        if (m_rootNode.document().inQuirksMode()) {
317            // Quirks mode, case insensitive comparison of names.
318            if (equalIgnoringCase(anchor.name(), name))
319                return &anchor;
320        } else {
321            // Strict mode, names need to match exactly.
322            if (anchor.name() == name)
323                return &anchor;
324        }
325    }
326    return nullptr;
327}
328
329void TreeScope::adoptIfNeeded(Node* node)
330{
331    ASSERT(this);
332    ASSERT(node);
333    ASSERT(!node->isDocumentNode());
334    ASSERT(!node->m_deletionHasBegun);
335    TreeScopeAdopter adopter(node, *this);
336    if (adopter.needsScopeChange())
337        adopter.execute();
338}
339
340static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
341{
342    for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
343        if (focusedFrame->tree().parent() == currentFrame)
344            return focusedFrame->ownerElement();
345    }
346    return nullptr;
347}
348
349Element* TreeScope::focusedElement()
350{
351    Document& document = m_rootNode.document();
352    Element* element = document.focusedElement();
353
354    if (!element && document.page())
355        element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
356    if (!element)
357        return nullptr;
358    TreeScope* treeScope = &element->treeScope();
359    while (treeScope != this && treeScope != &document) {
360        element = toShadowRoot(treeScope->rootNode()).hostElement();
361        treeScope = &element->treeScope();
362    }
363    if (this != treeScope)
364        return nullptr;
365    return element;
366}
367
368static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
369{
370    while (true) {
371        treeScopes.append(&node->treeScope());
372        Element* ancestor = node->shadowHost();
373        if (!ancestor)
374            break;
375        node = ancestor;
376    }
377}
378
379TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
380{
381    if (!nodeA || !nodeB)
382        return nullptr;
383
384    if (&nodeA->treeScope() == &nodeB->treeScope())
385        return &nodeA->treeScope();
386
387    Vector<TreeScope*, 5> treeScopesA;
388    listTreeScopes(nodeA, treeScopesA);
389
390    Vector<TreeScope*, 5> treeScopesB;
391    listTreeScopes(nodeB, treeScopesB);
392
393    size_t indexA = treeScopesA.size();
394    size_t indexB = treeScopesB.size();
395
396    for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
397
398    // If the nodes had no common tree scope, return immediately.
399    if (indexA == treeScopesA.size())
400        return nullptr;
401
402    return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : nullptr;
403}
404
405} // namespace WebCore
406