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