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