1/*
2 * Copyright (C) 2006-2017 Apple Inc. All rights reserved.
3 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 */
20
21#include "config.h"
22#include "FrameTree.h"
23
24#include "Document.h"
25#include "Frame.h"
26#include "FrameLoader.h"
27#include "FrameView.h"
28#include "HTMLFrameOwnerElement.h"
29#include "Page.h"
30#include "PageGroup.h"
31#include <stdarg.h>
32#include <wtf/Vector.h>
33#include <wtf/text/CString.h>
34#include <wtf/text/StringBuilder.h>
35#include <wtf/text/StringConcatenateNumbers.h>
36
37namespace WebCore {
38
39FrameTree::~FrameTree()
40{
41 for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
42 child->setView(nullptr);
43}
44
45void FrameTree::setName(const AtomicString& name)
46{
47 m_name = name;
48 if (!parent()) {
49 m_uniqueName = name;
50 return;
51 }
52 m_uniqueName = nullAtom(); // Remove our old frame name so it's not considered in uniqueChildName.
53 m_uniqueName = parent()->tree().uniqueChildName(name);
54}
55
56void FrameTree::clearName()
57{
58 m_name = nullAtom();
59 m_uniqueName = nullAtom();
60}
61
62Frame* FrameTree::parent() const
63{
64 return m_parent;
65}
66
67void FrameTree::appendChild(Frame& child)
68{
69 ASSERT(child.page() == m_thisFrame.page());
70 child.tree().m_parent = &m_thisFrame;
71 Frame* oldLast = m_lastChild;
72 m_lastChild = &child;
73
74 if (oldLast) {
75 child.tree().m_previousSibling = oldLast;
76 oldLast->tree().m_nextSibling = &child;
77 } else
78 m_firstChild = &child;
79
80 m_scopedChildCount = invalidCount;
81
82 ASSERT(!m_lastChild->tree().m_nextSibling);
83}
84
85void FrameTree::removeChild(Frame& child)
86{
87 Frame*& newLocationForPrevious = m_lastChild == &child ? m_lastChild : child.tree().m_nextSibling->tree().m_previousSibling;
88 RefPtr<Frame>& newLocationForNext = m_firstChild == &child ? m_firstChild : child.tree().m_previousSibling->tree().m_nextSibling;
89
90 child.tree().m_parent = nullptr;
91 newLocationForPrevious = std::exchange(child.tree().m_previousSibling, nullptr);
92 newLocationForNext = WTFMove(child.tree().m_nextSibling);
93
94 m_scopedChildCount = invalidCount;
95}
96
97AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
98{
99 // If the requested name (the frame's "name" attribute) is unique, just use that.
100 if (!requestedName.isEmpty() && !child(requestedName) && !equalIgnoringASCIICase(requestedName, "_blank"))
101 return requestedName;
102
103 // The "name" attribute was not unique or absent. Generate a name based on a counter on the main frame that gets reset
104 // on navigation. The name uses HTML comment syntax to avoid collisions with author names.
105 return generateUniqueName();
106}
107
108AtomicString FrameTree::generateUniqueName() const
109{
110 auto& top = this->top();
111 if (&top.tree() != this)
112 return top.tree().generateUniqueName();
113
114 return makeString("<!--frame", ++m_frameIDGenerator, "-->");
115}
116
117static bool inScope(Frame& frame, TreeScope& scope)
118{
119 Document* document = frame.document();
120 if (!document)
121 return false;
122 HTMLFrameOwnerElement* owner = document->ownerElement();
123 if (!owner)
124 return false;
125 return &owner->treeScope() == &scope;
126}
127
128inline Frame* FrameTree::scopedChild(unsigned index, TreeScope* scope) const
129{
130 if (!scope)
131 return nullptr;
132
133 unsigned scopedIndex = 0;
134 for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
135 if (inScope(*result, *scope)) {
136 if (scopedIndex == index)
137 return result;
138 scopedIndex++;
139 }
140 }
141
142 return nullptr;
143}
144
145inline Frame* FrameTree::scopedChild(const AtomicString& name, TreeScope* scope) const
146{
147 if (!scope)
148 return nullptr;
149
150 for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) {
151 if (child->tree().uniqueName() == name && inScope(*child, *scope))
152 return child;
153 }
154 return nullptr;
155}
156
157inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const
158{
159 if (!scope)
160 return 0;
161
162 unsigned scopedCount = 0;
163 for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
164 if (inScope(*result, *scope))
165 scopedCount++;
166 }
167
168 return scopedCount;
169}
170
171Frame* FrameTree::scopedChild(unsigned index) const
172{
173 return scopedChild(index, m_thisFrame.document());
174}
175
176Frame* FrameTree::scopedChild(const AtomicString& name) const
177{
178 return scopedChild(name, m_thisFrame.document());
179}
180
181unsigned FrameTree::scopedChildCount() const
182{
183 if (m_scopedChildCount == invalidCount)
184 m_scopedChildCount = scopedChildCount(m_thisFrame.document());
185 return m_scopedChildCount;
186}
187
188unsigned FrameTree::childCount() const
189{
190 unsigned count = 0;
191 for (Frame* result = firstChild(); result; result = result->tree().nextSibling())
192 ++count;
193 return count;
194}
195
196Frame* FrameTree::child(unsigned index) const
197{
198 Frame* result = firstChild();
199 for (unsigned i = 0; result && i != index; ++i)
200 result = result->tree().nextSibling();
201 return result;
202}
203
204Frame* FrameTree::child(const AtomicString& name) const
205{
206 for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
207 if (child->tree().uniqueName() == name)
208 return child;
209 return nullptr;
210}
211
212// FrameTree::find() only returns frames in pages that are related to the active
213// page by an opener <-> openee relationship.
214static bool isFrameFamiliarWith(Frame& frameA, Frame& frameB)
215{
216 if (frameA.page() == frameB.page())
217 return true;
218
219 auto* frameAOpener = frameA.mainFrame().loader().opener();
220 auto* frameBOpener = frameB.mainFrame().loader().opener();
221 return (frameAOpener && frameAOpener->page() == frameB.page()) || (frameBOpener && frameBOpener->page() == frameA.page()) || (frameAOpener && frameBOpener && frameAOpener->page() == frameBOpener->page());
222}
223
224Frame* FrameTree::find(const AtomicString& name, Frame& activeFrame) const
225{
226 // FIXME: _current is not part of the HTML specification.
227 if (equalIgnoringASCIICase(name, "_self") || name == "_current" || name.isEmpty())
228 return &m_thisFrame;
229
230 if (equalIgnoringASCIICase(name, "_top"))
231 return &top();
232
233 if (equalIgnoringASCIICase(name, "_parent"))
234 return parent() ? parent() : &m_thisFrame;
235
236 // Since "_blank" should never be any frame's name, the following is only an optimization.
237 if (equalIgnoringASCIICase(name, "_blank"))
238 return nullptr;
239
240 // Search subtree starting with this frame first.
241 for (Frame* frame = &m_thisFrame; frame; frame = frame->tree().traverseNext(&m_thisFrame)) {
242 if (frame->tree().uniqueName() == name)
243 return frame;
244 }
245
246 // Then the rest of the tree.
247 for (Frame* frame = &m_thisFrame.mainFrame(); frame; frame = frame->tree().traverseNext()) {
248 if (frame->tree().uniqueName() == name)
249 return frame;
250 }
251
252 // Search the entire tree of each of the other pages in this namespace.
253 // FIXME: Is random order OK?
254 Page* page = m_thisFrame.page();
255 if (!page)
256 return nullptr;
257
258 for (auto* otherPage : page->group().pages()) {
259 if (otherPage == page)
260 continue;
261 for (auto* frame = &otherPage->mainFrame(); frame; frame = frame->tree().traverseNext()) {
262 if (frame->tree().uniqueName() == name && isFrameFamiliarWith(activeFrame, *frame))
263 return frame;
264 }
265 }
266
267 return nullptr;
268}
269
270bool FrameTree::isDescendantOf(const Frame* ancestor) const
271{
272 if (!ancestor)
273 return false;
274
275 if (m_thisFrame.page() != ancestor->page())
276 return false;
277
278 for (Frame* frame = &m_thisFrame; frame; frame = frame->tree().parent())
279 if (frame == ancestor)
280 return true;
281 return false;
282}
283
284Frame* FrameTree::traverseNext(const Frame* stayWithin) const
285{
286 Frame* child = firstChild();
287 if (child) {
288 ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin));
289 return child;
290 }
291
292 if (&m_thisFrame == stayWithin)
293 return nullptr;
294
295 Frame* sibling = nextSibling();
296 if (sibling) {
297 ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin));
298 return sibling;
299 }
300
301 Frame* frame = &m_thisFrame;
302 while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) {
303 frame = frame->tree().parent();
304 if (!frame)
305 return nullptr;
306 sibling = frame->tree().nextSibling();
307 }
308
309 if (frame) {
310 ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin));
311 return sibling;
312 }
313
314 return nullptr;
315}
316
317Frame* FrameTree::firstRenderedChild() const
318{
319 Frame* child = firstChild();
320 if (!child)
321 return nullptr;
322
323 if (child->ownerRenderer())
324 return child;
325
326 while ((child = child->tree().nextSibling())) {
327 if (child->ownerRenderer())
328 return child;
329 }
330
331 return nullptr;
332}
333
334Frame* FrameTree::nextRenderedSibling() const
335{
336 Frame* sibling = &m_thisFrame;
337
338 while ((sibling = sibling->tree().nextSibling())) {
339 if (sibling->ownerRenderer())
340 return sibling;
341 }
342
343 return nullptr;
344}
345
346Frame* FrameTree::traverseNextRendered(const Frame* stayWithin) const
347{
348 Frame* child = firstRenderedChild();
349 if (child) {
350 ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin));
351 return child;
352 }
353
354 if (&m_thisFrame == stayWithin)
355 return nullptr;
356
357 Frame* sibling = nextRenderedSibling();
358 if (sibling) {
359 ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin));
360 return sibling;
361 }
362
363 Frame* frame = &m_thisFrame;
364 while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) {
365 frame = frame->tree().parent();
366 if (!frame)
367 return nullptr;
368 sibling = frame->tree().nextRenderedSibling();
369 }
370
371 if (frame) {
372 ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin));
373 return sibling;
374 }
375
376 return nullptr;
377}
378
379Frame* FrameTree::traverseNext(CanWrap canWrap, DidWrap* didWrap) const
380{
381 if (Frame* result = traverseNext())
382 return result;
383
384 if (canWrap == CanWrap::Yes) {
385 if (didWrap)
386 *didWrap = DidWrap::Yes;
387 return &m_thisFrame.mainFrame();
388 }
389
390 return nullptr;
391}
392
393Frame* FrameTree::traversePrevious(CanWrap canWrap, DidWrap* didWrap) const
394{
395 // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
396
397 if (Frame* prevSibling = previousSibling())
398 return prevSibling->tree().deepLastChild();
399 if (Frame* parentFrame = parent())
400 return parentFrame;
401
402 // no siblings, no parent, self==top
403 if (canWrap == CanWrap::Yes) {
404 if (didWrap)
405 *didWrap = DidWrap::Yes;
406 return deepLastChild();
407 }
408
409 // top view is always the last one in this ordering, so prev is nil without wrap
410 return nullptr;
411}
412
413Frame* FrameTree::traverseNextInPostOrder(CanWrap canWrap) const
414{
415 if (m_nextSibling)
416 return m_nextSibling->tree().deepFirstChild();
417 if (m_parent)
418 return m_parent;
419 if (canWrap == CanWrap::Yes)
420 return deepFirstChild();
421 return nullptr;
422}
423
424Frame* FrameTree::deepFirstChild() const
425{
426 Frame* result = &m_thisFrame;
427 while (auto* next = result->tree().firstChild())
428 result = next;
429 return result;
430}
431
432Frame* FrameTree::deepLastChild() const
433{
434 Frame* result = &m_thisFrame;
435 for (Frame* last = lastChild(); last; last = last->tree().lastChild())
436 result = last;
437
438 return result;
439}
440
441Frame& FrameTree::top() const
442{
443 Frame* frame = &m_thisFrame;
444 for (Frame* parent = &m_thisFrame; parent; parent = parent->tree().parent())
445 frame = parent;
446 return *frame;
447}
448
449} // namespace WebCore
450
451#ifndef NDEBUG
452
453static void printIndent(int indent)
454{
455 for (int i = 0; i < indent; ++i)
456 printf(" ");
457}
458
459static void printFrames(const WebCore::Frame& frame, const WebCore::Frame* targetFrame, int indent)
460{
461 if (&frame == targetFrame) {
462 printf("--> ");
463 printIndent(indent - 1);
464 } else
465 printIndent(indent);
466
467 WebCore::FrameView* view = frame.view();
468 printf("Frame %p %dx%d\n", &frame, view ? view->width() : 0, view ? view->height() : 0);
469 printIndent(indent);
470 printf(" ownerElement=%p\n", frame.ownerElement());
471 printIndent(indent);
472 printf(" frameView=%p (needs layout %d)\n", view, view ? view->needsLayout() : false);
473 printIndent(indent);
474 printf(" renderView=%p\n", view ? view->renderView() : nullptr);
475 printIndent(indent);
476 printf(" ownerRenderer=%p\n", frame.ownerRenderer());
477 printIndent(indent);
478 printf(" document=%p (needs style recalc %d)\n", frame.document(), frame.document() ? frame.document()->childNeedsStyleRecalc() : false);
479 printIndent(indent);
480 printf(" uri=%s\n", frame.document()->documentURI().utf8().data());
481
482 for (WebCore::Frame* child = frame.tree().firstChild(); child; child = child->tree().nextSibling())
483 printFrames(*child, targetFrame, indent + 1);
484}
485
486void showFrameTree(const WebCore::Frame* frame)
487{
488 if (!frame) {
489 printf("Null input frame\n");
490 return;
491 }
492
493 printFrames(frame->tree().top(), frame, 0);
494}
495
496#endif
497