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 "ContainerNode.h"
31#include "DOMSelection.h"
32#include "DOMWindow.h"
33#include "Document.h"
34#include "Element.h"
35#include "FocusController.h"
36#include "Frame.h"
37#include "FrameView.h"
38#include "HTMLAnchorElement.h"
39#include "HTMLFrameOwnerElement.h"
40#include "HTMLLabelElement.h"
41#include "HTMLMapElement.h"
42#include "HTMLNames.h"
43#include "HitTestResult.h"
44#include "IdTargetObserverRegistry.h"
45#include "NodeTraversal.h"
46#include "Page.h"
47#include "RenderView.h"
48#include "RuntimeEnabledFeatures.h"
49#include "ShadowRoot.h"
50#include "TreeScopeAdopter.h"
51#include <wtf/Vector.h>
52#include <wtf/text/AtomicString.h>
53#include <wtf/text/CString.h>
54
55namespace WebCore {
56
57struct SameSizeAsTreeScope {
58    virtual ~SameSizeAsTreeScope();
59    void* pointers[9];
60    int ints[1];
61};
62
63COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
64
65using namespace HTMLNames;
66
67TreeScope::TreeScope(ContainerNode* rootNode, Document* document)
68    : m_rootNode(rootNode)
69    , m_documentScope(document)
70    , m_parentTreeScope(document)
71    , m_guardRefCount(0)
72    , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
73{
74    ASSERT(rootNode);
75    ASSERT(document);
76    ASSERT(rootNode != document);
77    m_parentTreeScope->guardRef();
78    m_rootNode->setTreeScope(this);
79}
80
81TreeScope::TreeScope(Document* document)
82    : m_rootNode(document)
83    , m_documentScope(document)
84    , m_parentTreeScope(0)
85    , m_guardRefCount(0)
86    , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
87{
88    ASSERT(document);
89    m_rootNode->setTreeScope(this);
90}
91
92TreeScope::TreeScope()
93    : m_rootNode(0)
94    , m_documentScope(0)
95    , m_parentTreeScope(0)
96    , m_guardRefCount(0)
97{
98}
99
100TreeScope::~TreeScope()
101{
102    ASSERT(!m_guardRefCount);
103    m_rootNode->setTreeScope(noDocumentInstance());
104
105    if (m_selection) {
106        m_selection->clearTreeScope();
107        m_selection = 0;
108    }
109
110    if (m_parentTreeScope)
111        m_parentTreeScope->guardDeref();
112}
113
114void TreeScope::destroyTreeScopeData()
115{
116    m_elementsById.clear();
117    m_imageMapsByName.clear();
118    m_labelsByForAttribute.clear();
119}
120
121void TreeScope::clearDocumentScope()
122{
123    ASSERT(rootNode()->isDocumentNode());
124    m_documentScope = 0;
125}
126
127void TreeScope::setParentTreeScope(TreeScope* newParentScope)
128{
129    // A document node cannot be re-parented.
130    ASSERT(!rootNode()->isDocumentNode());
131    // Every scope other than document needs a parent scope.
132    ASSERT(newParentScope);
133
134    newParentScope->guardRef();
135    if (m_parentTreeScope)
136        m_parentTreeScope->guardDeref();
137    m_parentTreeScope = newParentScope;
138    setDocumentScope(newParentScope->documentScope());
139}
140
141Element* TreeScope::getElementById(const AtomicString& elementId) const
142{
143    if (elementId.isEmpty())
144        return 0;
145    if (!m_elementsById)
146        return 0;
147    return m_elementsById->getElementById(elementId.impl(), this);
148}
149
150const Vector<Element*>* TreeScope::getAllElementsById(const AtomicString& elementId) const
151{
152    if (elementId.isEmpty())
153        return 0;
154    if (!m_elementsById)
155        return 0;
156    return m_elementsById->getAllElementsById(elementId.impl(), this);
157}
158
159void TreeScope::addElementById(const AtomicString& elementId, Element* element)
160{
161    if (!m_elementsById)
162        m_elementsById = adoptPtr(new DocumentOrderedMap);
163    m_elementsById->add(elementId.impl(), element, this);
164    m_idTargetObserverRegistry->notifyObservers(elementId);
165}
166
167void TreeScope::removeElementById(const AtomicString& elementId, Element* element)
168{
169    if (!m_elementsById)
170        return;
171    m_elementsById->remove(elementId.impl(), element);
172    m_idTargetObserverRegistry->notifyObservers(elementId);
173}
174
175Element* TreeScope::getElementByName(const AtomicString& name) const
176{
177    if (name.isEmpty())
178        return 0;
179    if (!m_elementsByName)
180        return 0;
181    return m_elementsByName->getElementByName(name.impl(), this);
182}
183
184void TreeScope::addElementByName(const AtomicString& name, Element* element)
185{
186    if (!m_elementsByName)
187        m_elementsByName = adoptPtr(new DocumentOrderedMap);
188    m_elementsByName->add(name.impl(), element, this);
189}
190
191void TreeScope::removeElementByName(const AtomicString& name, Element* element)
192{
193    if (!m_elementsByName)
194        return;
195    m_elementsByName->remove(name.impl(), element);
196}
197
198Node* TreeScope::ancestorInThisScope(Node* node) const
199{
200    while (node) {
201        if (node->treeScope() == this)
202            return node;
203        if (!node->isInShadowTree())
204            return 0;
205
206        node = node->shadowHost();
207    }
208
209    return 0;
210}
211
212void TreeScope::addImageMap(HTMLMapElement* imageMap)
213{
214    AtomicStringImpl* name = imageMap->getName().impl();
215    if (!name)
216        return;
217    if (!m_imageMapsByName)
218        m_imageMapsByName = adoptPtr(new DocumentOrderedMap);
219    m_imageMapsByName->add(name, imageMap, this);
220}
221
222void TreeScope::removeImageMap(HTMLMapElement* imageMap)
223{
224    if (!m_imageMapsByName)
225        return;
226    AtomicStringImpl* name = imageMap->getName().impl();
227    if (!name)
228        return;
229    m_imageMapsByName->remove(name, imageMap);
230}
231
232HTMLMapElement* TreeScope::getImageMap(const String& url) const
233{
234    if (url.isNull())
235        return 0;
236    if (!m_imageMapsByName)
237        return 0;
238    size_t hashPos = url.find('#');
239    String name = (hashPos == notFound ? url : url.substring(hashPos + 1)).impl();
240    if (rootNode()->document()->isHTMLDocument())
241        return static_cast<HTMLMapElement*>(m_imageMapsByName->getElementByLowercasedMapName(AtomicString(name.lower()).impl(), this));
242    return static_cast<HTMLMapElement*>(m_imageMapsByName->getElementByMapName(AtomicString(name).impl(), this));
243}
244
245Node* nodeFromPoint(Document* document, int x, int y, LayoutPoint* localPoint)
246{
247    Frame* frame = document->frame();
248
249    if (!frame)
250        return 0;
251    FrameView* frameView = frame->view();
252    if (!frameView)
253        return 0;
254
255    float scaleFactor = frame->pageZoomFactor() * frame->frameScaleFactor();
256    IntPoint point = roundedIntPoint(FloatPoint(x * scaleFactor  + frameView->scrollX(), y * scaleFactor + frameView->scrollY()));
257
258    if (!frameView->visibleContentRect().contains(point))
259        return 0;
260
261    HitTestRequest request(HitTestRequest::ReadOnly | HitTestRequest::Active | HitTestRequest::DisallowShadowContent);
262    HitTestResult result(point);
263    document->renderView()->hitTest(request, result);
264
265    if (localPoint)
266        *localPoint = result.localPoint();
267
268    return result.innerNode();
269}
270
271Element* TreeScope::elementFromPoint(int x, int y) const
272{
273    Node* node = nodeFromPoint(rootNode()->document(), x, y);
274    while (node && !node->isElementNode())
275        node = node->parentNode();
276    if (node)
277        node = ancestorInThisScope(node);
278    return toElement(node);
279}
280
281void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
282{
283    ASSERT(m_labelsByForAttribute);
284    m_labelsByForAttribute->add(forAttributeValue.impl(), element, this);
285}
286
287void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
288{
289    ASSERT(m_labelsByForAttribute);
290    m_labelsByForAttribute->remove(forAttributeValue.impl(), element);
291}
292
293HTMLLabelElement* TreeScope::labelElementForId(const AtomicString& forAttributeValue)
294{
295    if (forAttributeValue.isEmpty())
296        return 0;
297
298    if (!m_labelsByForAttribute) {
299        // Populate the map on first access.
300        m_labelsByForAttribute = adoptPtr(new DocumentOrderedMap);
301        for (Element* element = ElementTraversal::firstWithin(rootNode()); element; element = ElementTraversal::next(element)) {
302            if (element->hasTagName(labelTag)) {
303                HTMLLabelElement* label = static_cast<HTMLLabelElement*>(element);
304                const AtomicString& forValue = label->fastGetAttribute(forAttr);
305                if (!forValue.isEmpty())
306                    addLabel(forValue, label);
307            }
308        }
309    }
310
311    return static_cast<HTMLLabelElement*>(m_labelsByForAttribute->getElementByLabelForAttribute(forAttributeValue.impl(), this));
312}
313
314DOMSelection* TreeScope::getSelection() const
315{
316    if (!rootNode()->document()->frame())
317        return 0;
318
319    if (m_selection)
320        return m_selection.get();
321
322    // FIXME: The correct selection in Shadow DOM requires that Position can have a ShadowRoot
323    // as a container. It is now enabled only if runtime Shadow DOM feature is enabled.
324    // See https://bugs.webkit.org/show_bug.cgi?id=82697
325#if ENABLE(SHADOW_DOM)
326    if (RuntimeEnabledFeatures::shadowDOMEnabled()) {
327        m_selection = DOMSelection::create(this);
328        return m_selection.get();
329    }
330#endif
331
332    if (this != rootNode()->document())
333        return rootNode()->document()->getSelection();
334
335    m_selection = DOMSelection::create(rootNode()->document());
336    return m_selection.get();
337}
338
339Element* TreeScope::findAnchor(const String& name)
340{
341    if (name.isEmpty())
342        return 0;
343    if (Element* element = getElementById(name))
344        return element;
345    for (Element* element = ElementTraversal::firstWithin(rootNode()); element; element = ElementTraversal::next(element)) {
346        if (element->hasTagName(aTag)) {
347            HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(element);
348            if (rootNode()->document()->inQuirksMode()) {
349                // Quirks mode, case insensitive comparison of names.
350                if (equalIgnoringCase(anchor->name(), name))
351                    return anchor;
352            } else {
353                // Strict mode, names need to match exactly.
354                if (anchor->name() == name)
355                    return anchor;
356            }
357        }
358    }
359    return 0;
360}
361
362bool TreeScope::applyAuthorStyles() const
363{
364    return true;
365}
366
367bool TreeScope::resetStyleInheritance() const
368{
369    return false;
370}
371
372void TreeScope::adoptIfNeeded(Node* node)
373{
374    ASSERT(this);
375    ASSERT(node);
376    ASSERT(!node->isDocumentNode());
377    ASSERT(!node->m_deletionHasBegun);
378    TreeScopeAdopter adopter(node, this);
379    if (adopter.needsScopeChange())
380        adopter.execute();
381}
382
383static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
384{
385    for (; focusedFrame; focusedFrame = focusedFrame->tree()->parent()) {
386        if (focusedFrame->tree()->parent() == currentFrame)
387            return focusedFrame->ownerElement();
388    }
389    return 0;
390}
391
392Element* TreeScope::focusedElement()
393{
394    Document* document = rootNode()->document();
395    Element* element = document->focusedElement();
396
397    if (!element && document->page())
398        element = focusedFrameOwnerElement(document->page()->focusController()->focusedFrame(), document->frame());
399    if (!element)
400        return 0;
401    TreeScope* treeScope = element->treeScope();
402    while (treeScope != this && treeScope != document) {
403        element = toShadowRoot(treeScope->rootNode())->host();
404        treeScope = element->treeScope();
405    }
406    if (this != treeScope)
407        return 0;
408    return element;
409}
410
411static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
412{
413    while (true) {
414        treeScopes.append(node->treeScope());
415        Element* ancestor = node->shadowHost();
416        if (!ancestor)
417            break;
418        node = ancestor;
419    }
420}
421
422TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
423{
424    if (!nodeA || !nodeB)
425        return 0;
426
427    if (nodeA->treeScope() == nodeB->treeScope())
428        return nodeA->treeScope();
429
430    Vector<TreeScope*, 5> treeScopesA;
431    listTreeScopes(nodeA, treeScopesA);
432
433    Vector<TreeScope*, 5> treeScopesB;
434    listTreeScopes(nodeB, treeScopesB);
435
436    size_t indexA = treeScopesA.size();
437    size_t indexB = treeScopesB.size();
438
439    for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
440
441    return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : 0;
442}
443
444#ifndef NDEBUG
445bool TreeScope::deletionHasBegun()
446{
447    return rootNode() && rootNode()->m_deletionHasBegun;
448}
449
450void TreeScope::beginDeletion()
451{
452    ASSERT(this != noDocumentInstance());
453    rootNode()->m_deletionHasBegun = true;
454}
455#endif
456
457int TreeScope::refCount() const
458{
459    if (Node* root = rootNode())
460        return root->refCount();
461    return 0;
462}
463
464} // namespace WebCore
465