e1e1b0e6a90f510c2173a134545428b3baa85a45
[WebKit-https.git] / Source / WebCore / dom / TreeScope.cpp
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 "ElementIterator.h"
36 #include "FocusController.h"
37 #include "Frame.h"
38 #include "FrameView.h"
39 #include "HTMLAnchorElement.h"
40 #include "HTMLFrameOwnerElement.h"
41 #include "HTMLLabelElement.h"
42 #include "HTMLMapElement.h"
43 #include "HTMLNames.h"
44 #include "HitTestResult.h"
45 #include "IdTargetObserverRegistry.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
55 namespace WebCore {
56
57 struct SameSizeAsTreeScope {
58     virtual ~SameSizeAsTreeScope();
59     void* pointers[9];
60     int ints[1];
61 };
62
63 COMPILE_ASSERT(sizeof(TreeScope) == sizeof(SameSizeAsTreeScope), treescope_should_stay_small);
64
65 using namespace HTMLNames;
66
67 TreeScope::TreeScope(ContainerNode* rootNode, Document* document)
68     : m_rootNode(rootNode)
69     , m_documentScope(document)
70     , m_parentTreeScope(document)
71     , m_selfOnlyRefCount(0)
72     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
73 {
74     ASSERT(rootNode);
75     ASSERT(document);
76     ASSERT(rootNode != document);
77     m_parentTreeScope->selfOnlyRef();
78     m_rootNode->setTreeScope(this);
79 }
80
81 TreeScope::TreeScope(Document* document)
82     : m_rootNode(document)
83     , m_documentScope(document)
84     , m_parentTreeScope(0)
85     , m_selfOnlyRefCount(0)
86     , m_idTargetObserverRegistry(IdTargetObserverRegistry::create())
87 {
88     ASSERT(document);
89     m_rootNode->setTreeScope(this);
90 }
91
92 TreeScope::TreeScope()
93     : m_rootNode(0)
94     , m_documentScope(0)
95     , m_parentTreeScope(0)
96     , m_selfOnlyRefCount(0)
97 {
98 }
99
100 TreeScope::~TreeScope()
101 {
102     ASSERT(!m_selfOnlyRefCount);
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->selfOnlyDeref();
112 }
113
114 void TreeScope::destroyTreeScopeData()
115 {
116     m_elementsById.clear();
117     m_imageMapsByName.clear();
118     m_labelsByForAttribute.clear();
119 }
120
121 void TreeScope::clearDocumentScope()
122 {
123     ASSERT(rootNode()->isDocumentNode());
124     m_documentScope = 0;
125 }
126
127 void 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->selfOnlyRef();
135     if (m_parentTreeScope)
136         m_parentTreeScope->selfOnlyDeref();
137     m_parentTreeScope = newParentScope;
138     setDocumentScope(newParentScope->documentScope());
139 }
140
141 Element* 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
150 const 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
159 void 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);
164     m_idTargetObserverRegistry->notifyObservers(elementId);
165 }
166
167 void 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
175 Element* 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
184 void 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);
189 }
190
191 void TreeScope::removeElementByName(const AtomicString& name, Element* element)
192 {
193     if (!m_elementsByName)
194         return;
195     m_elementsByName->remove(name.impl(), element);
196 }
197
198 Node* 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
212 void 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);
220 }
221
222 void 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
232 HTMLMapElement* 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 toHTMLMapElement(m_imageMapsByName->getElementByLowercasedMapName(AtomicString(name.lower()).impl(), this));
242     return toHTMLMapElement(m_imageMapsByName->getElementByMapName(AtomicString(name).impl(), this));
243 }
244
245 Node* 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
271 Element* 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
281 void TreeScope::addLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
282 {
283     ASSERT(m_labelsByForAttribute);
284     m_labelsByForAttribute->add(forAttributeValue.impl(), element);
285 }
286
287 void TreeScope::removeLabel(const AtomicString& forAttributeValue, HTMLLabelElement* element)
288 {
289     ASSERT(m_labelsByForAttribute);
290     m_labelsByForAttribute->remove(forAttributeValue.impl(), element);
291 }
292
293 HTMLLabelElement* 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
302         auto labelDescendants = descendantsOfType<HTMLLabelElement>(rootNode());
303         for (auto label = labelDescendants.begin(), end = labelDescendants.end(); label != end; ++label) {
304             const AtomicString& forValue = label->fastGetAttribute(forAttr);
305             if (!forValue.isEmpty())
306                 addLabel(forValue, &*label);
307         }
308     }
309
310     return toHTMLLabelElement(m_labelsByForAttribute->getElementByLabelForAttribute(forAttributeValue.impl(), this));
311 }
312
313 DOMSelection* TreeScope::getSelection() const
314 {
315     if (!rootNode()->document().frame())
316         return 0;
317
318     if (m_selection)
319         return m_selection.get();
320
321     // FIXME: The correct selection in Shadow DOM requires that Position can have a ShadowRoot
322     // as a container. It is now enabled only if runtime Shadow DOM feature is enabled.
323     // See https://bugs.webkit.org/show_bug.cgi?id=82697
324 #if ENABLE(SHADOW_DOM)
325     if (RuntimeEnabledFeatures::sharedFeatures().shadowDOMEnabled()) {
326         m_selection = DOMSelection::create(this);
327         return m_selection.get();
328     }
329 #endif
330
331     if (this != &rootNode()->document())
332         return rootNode()->document().getSelection();
333
334     m_selection = DOMSelection::create(&rootNode()->document());
335     return m_selection.get();
336 }
337
338 Element* TreeScope::findAnchor(const String& name)
339 {
340     if (name.isEmpty())
341         return 0;
342     if (Element* element = getElementById(name))
343         return element;
344     auto anchorDescendants = descendantsOfType<HTMLAnchorElement>(rootNode());
345     for (auto anchor = anchorDescendants.begin(), end = anchorDescendants.end(); anchor != end; ++anchor) {
346         if (rootNode()->document().inQuirksMode()) {
347             // Quirks mode, case insensitive comparison of names.
348             if (equalIgnoringCase(anchor->name(), name))
349                 return &*anchor;
350         } else {
351             // Strict mode, names need to match exactly.
352             if (anchor->name() == name)
353                 return &*anchor;
354         }
355     }
356     return 0;
357 }
358
359 bool TreeScope::applyAuthorStyles() const
360 {
361     return true;
362 }
363
364 void TreeScope::adoptIfNeeded(Node* node)
365 {
366     ASSERT(this);
367     ASSERT(node);
368     ASSERT(!node->isDocumentNode());
369     ASSERT(!node->m_deletionHasBegun);
370     TreeScopeAdopter adopter(node, this);
371     if (adopter.needsScopeChange())
372         adopter.execute();
373 }
374
375 static Element* focusedFrameOwnerElement(Frame* focusedFrame, Frame* currentFrame)
376 {
377     for (; focusedFrame; focusedFrame = focusedFrame->tree().parent()) {
378         if (focusedFrame->tree().parent() == currentFrame)
379             return focusedFrame->ownerElement();
380     }
381     return 0;
382 }
383
384 Element* TreeScope::focusedElement()
385 {
386     Document& document = rootNode()->document();
387     Element* element = document.focusedElement();
388
389     if (!element && document.page())
390         element = focusedFrameOwnerElement(document.page()->focusController().focusedFrame(), document.frame());
391     if (!element)
392         return 0;
393     TreeScope* treeScope = element->treeScope();
394     while (treeScope != this && treeScope != &document) {
395         element = toShadowRoot(treeScope->rootNode())->hostElement();
396         treeScope = element->treeScope();
397     }
398     if (this != treeScope)
399         return 0;
400     return element;
401 }
402
403 static void listTreeScopes(Node* node, Vector<TreeScope*, 5>& treeScopes)
404 {
405     while (true) {
406         treeScopes.append(node->treeScope());
407         Element* ancestor = node->shadowHost();
408         if (!ancestor)
409             break;
410         node = ancestor;
411     }
412 }
413
414 TreeScope* commonTreeScope(Node* nodeA, Node* nodeB)
415 {
416     if (!nodeA || !nodeB)
417         return 0;
418
419     if (nodeA->treeScope() == nodeB->treeScope())
420         return nodeA->treeScope();
421
422     Vector<TreeScope*, 5> treeScopesA;
423     listTreeScopes(nodeA, treeScopesA);
424
425     Vector<TreeScope*, 5> treeScopesB;
426     listTreeScopes(nodeB, treeScopesB);
427
428     size_t indexA = treeScopesA.size();
429     size_t indexB = treeScopesB.size();
430
431     for (; indexA > 0 && indexB > 0 && treeScopesA[indexA - 1] == treeScopesB[indexB - 1]; --indexA, --indexB) { }
432
433     return treeScopesA[indexA] == treeScopesB[indexB] ? treeScopesA[indexA] : 0;
434 }
435
436 #ifndef NDEBUG
437 bool TreeScope::deletionHasBegun()
438 {
439     return rootNode() && rootNode()->m_deletionHasBegun;
440 }
441
442 void TreeScope::beginDeletion()
443 {
444     ASSERT(this != noDocumentInstance());
445     rootNode()->m_deletionHasBegun = true;
446 }
447 #endif
448
449 int TreeScope::refCount() const
450 {
451     if (Node* root = rootNode())
452         return root->refCount();
453     return 0;
454 }
455
456 } // namespace WebCore