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