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