1e34a809355ab55e66d93b1111903c7a541fa335
[WebKit-https.git] / Source / WebCore / page / FrameTree.cpp
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 "FrameView.h"
26 #include "HTMLFrameOwnerElement.h"
27 #include "MainFrame.h"
28 #include "Page.h"
29 #include "PageGroup.h"
30 #include <stdarg.h>
31 #include <wtf/StringExtras.h>
32 #include <wtf/Vector.h>
33 #include <wtf/text/CString.h>
34 #include <wtf/text/StringBuilder.h>
35
36 namespace WebCore {
37
38 FrameTree::~FrameTree()
39 {
40     for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
41         child->setView(nullptr);
42 }
43
44 void FrameTree::setName(const AtomicString& name) 
45 {
46     m_name = name;
47     if (!parent()) {
48         m_uniqueName = name;
49         return;
50     }
51     m_uniqueName = nullAtom; // Remove our old frame name so it's not considered in uniqueChildName.
52     m_uniqueName = parent()->tree().uniqueChildName(name);
53 }
54
55 void FrameTree::clearName()
56 {
57     m_name = nullAtom;
58     m_uniqueName = nullAtom;
59 }
60
61 Frame* FrameTree::parent() const 
62
63     return m_parent;
64 }
65
66 unsigned FrameTree::indexInParent() const
67 {
68     if (!m_parent)
69         return 0;
70     unsigned index = 0;
71     for (Frame* frame = m_parent->tree().firstChild(); frame; frame = frame->tree().nextSibling()) {
72         if (&frame->tree() == this)
73             return index;
74         ++index;
75     }
76     RELEASE_ASSERT_NOT_REACHED();
77 }
78
79 void FrameTree::appendChild(Frame& child)
80 {
81     ASSERT(child.page() == m_thisFrame.page());
82     child.tree().m_parent = &m_thisFrame;
83     Frame* oldLast = m_lastChild;
84     m_lastChild = &child;
85
86     if (oldLast) {
87         child.tree().m_previousSibling = oldLast;
88         oldLast->tree().m_nextSibling = &child;
89     } else
90         m_firstChild = &child;
91
92     m_scopedChildCount = invalidCount;
93
94     ASSERT(!m_lastChild->tree().m_nextSibling);
95 }
96
97 void FrameTree::removeChild(Frame& child)
98 {
99     Frame*& newLocationForPrevious = m_lastChild == &child ? m_lastChild : child.tree().m_nextSibling->tree().m_previousSibling;
100     RefPtr<Frame>& newLocationForNext = m_firstChild == &child ? m_firstChild : child.tree().m_previousSibling->tree().m_nextSibling;
101
102     child.tree().m_parent = nullptr;
103     newLocationForPrevious = std::exchange(child.tree().m_previousSibling, nullptr);
104     newLocationForNext = WTFMove(child.tree().m_nextSibling);
105
106     m_scopedChildCount = invalidCount;
107 }
108
109 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
110 {
111     // If the requested name (the frame's "name" attribute) is unique, just use that.
112     if (!requestedName.isEmpty() && !child(requestedName) && !equalIgnoringASCIICase(requestedName, "_blank"))
113         return requestedName;
114
115     // The "name" attribute was not unique or absent. Generate a name based on the
116     // new frame's location in the frame tree. The name uses HTML comment syntax to
117     // avoid collisions with author names.
118
119     // An example path for the third child of the second child of the root frame:
120     // <!--framePath //<!--frame1-->/<!--frame2-->-->
121
122     const char framePathPrefix[] = "<!--framePath ";
123     const int framePathPrefixLength = 14;
124     const int framePathSuffixLength = 3;
125
126     // Find the nearest parent that has a frame with a path in it.
127     Vector<Frame*, 16> chain;
128     Frame* frame;
129     for (frame = &m_thisFrame; frame; frame = frame->tree().parent()) {
130         if (frame->tree().uniqueName().startsWith(framePathPrefix))
131             break;
132         chain.append(frame);
133     }
134     StringBuilder name;
135     name.append(framePathPrefix);
136     if (frame) {
137         name.append(frame->tree().uniqueName().string().substring(framePathPrefixLength,
138             frame->tree().uniqueName().length() - framePathPrefixLength - framePathSuffixLength));
139     }
140     for (int i = chain.size() - 1; i >= 0; --i) {
141         frame = chain[i];
142         name.append('/');
143         if (frame->tree().parent()) {
144             name.appendLiteral("<!--frame");
145             name.appendNumber(frame->tree().indexInParent());
146             name.appendLiteral("-->");
147         }
148     }
149
150     name.appendLiteral("/<!--frame");
151     name.appendNumber(childCount());
152     name.appendLiteral("-->-->");
153
154     return name.toAtomicString();
155 }
156
157 static bool inScope(Frame& frame, TreeScope& scope)
158 {
159     Document* document = frame.document();
160     if (!document)
161         return false;
162     HTMLFrameOwnerElement* owner = document->ownerElement();
163     if (!owner)
164         return false;
165     return &owner->treeScope() == &scope;
166 }
167
168 inline Frame* FrameTree::scopedChild(unsigned index, TreeScope* scope) const
169 {
170     if (!scope)
171         return nullptr;
172
173     unsigned scopedIndex = 0;
174     for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
175         if (inScope(*result, *scope)) {
176             if (scopedIndex == index)
177                 return result;
178             scopedIndex++;
179         }
180     }
181
182     return nullptr;
183 }
184
185 inline Frame* FrameTree::scopedChild(const AtomicString& name, TreeScope* scope) const
186 {
187     if (!scope)
188         return nullptr;
189
190     for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) {
191         if (child->tree().uniqueName() == name && inScope(*child, *scope))
192             return child;
193     }
194     return nullptr;
195 }
196
197 inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const
198 {
199     if (!scope)
200         return 0;
201
202     unsigned scopedCount = 0;
203     for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
204         if (inScope(*result, *scope))
205             scopedCount++;
206     }
207
208     return scopedCount;
209 }
210
211 Frame* FrameTree::scopedChild(unsigned index) const
212 {
213     return scopedChild(index, m_thisFrame.document());
214 }
215
216 Frame* FrameTree::scopedChild(const AtomicString& name) const
217 {
218     return scopedChild(name, m_thisFrame.document());
219 }
220
221 unsigned FrameTree::scopedChildCount() const
222 {
223     if (m_scopedChildCount == invalidCount)
224         m_scopedChildCount = scopedChildCount(m_thisFrame.document());
225     return m_scopedChildCount;
226 }
227
228 unsigned FrameTree::childCount() const
229 {
230     unsigned count = 0;
231     for (Frame* result = firstChild(); result; result = result->tree().nextSibling())
232         ++count;
233     return count;
234 }
235
236 Frame* FrameTree::child(unsigned index) const
237 {
238     Frame* result = firstChild();
239     for (unsigned i = 0; result && i != index; ++i)
240         result = result->tree().nextSibling();
241     return result;
242 }
243
244 Frame* FrameTree::child(const AtomicString& name) const
245 {
246     for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
247         if (child->tree().uniqueName() == name)
248             return child;
249     return nullptr;
250 }
251
252 Frame* FrameTree::find(const AtomicString& name) const
253 {
254     // FIXME: _current is not part of the HTML specification.
255     if (equalIgnoringASCIICase(name, "_self") || name == "_current" || name.isEmpty())
256         return &m_thisFrame;
257     
258     if (equalIgnoringASCIICase(name, "_top"))
259         return &top();
260     
261     if (equalIgnoringASCIICase(name, "_parent"))
262         return parent() ? parent() : &m_thisFrame;
263
264     // Since "_blank" should never be any frame's name, the following is only an optimization.
265     if (equalIgnoringASCIICase(name, "_blank"))
266         return nullptr;
267
268     // Search subtree starting with this frame first.
269     for (Frame* frame = &m_thisFrame; frame; frame = frame->tree().traverseNext(&m_thisFrame)) {
270         if (frame->tree().uniqueName() == name)
271             return frame;
272     }
273
274     // Then the rest of the tree.
275     for (Frame* frame = &m_thisFrame.mainFrame(); frame; frame = frame->tree().traverseNext()) {
276         if (frame->tree().uniqueName() == name)
277             return frame;
278     }
279
280     // Search the entire tree of each of the other pages in this namespace.
281     // FIXME: Is random order OK?
282     Page* page = m_thisFrame.page();
283     if (!page)
284         return nullptr;
285     
286     for (auto* otherPage : page->group().pages()) {
287         if (otherPage == page)
288             continue;
289         for (Frame* frame = &otherPage->mainFrame(); frame; frame = frame->tree().traverseNext()) {
290             if (frame->tree().uniqueName() == name)
291                 return frame;
292         }
293     }
294
295     return nullptr;
296 }
297
298 bool FrameTree::isDescendantOf(const Frame* ancestor) const
299 {
300     if (!ancestor)
301         return false;
302
303     if (m_thisFrame.page() != ancestor->page())
304         return false;
305
306     for (Frame* frame = &m_thisFrame; frame; frame = frame->tree().parent())
307         if (frame == ancestor)
308             return true;
309     return false;
310 }
311
312 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
313 {
314     Frame* child = firstChild();
315     if (child) {
316         ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin));
317         return child;
318     }
319
320     if (&m_thisFrame == stayWithin)
321         return nullptr;
322
323     Frame* sibling = nextSibling();
324     if (sibling) {
325         ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin));
326         return sibling;
327     }
328
329     Frame* frame = &m_thisFrame;
330     while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) {
331         frame = frame->tree().parent();
332         if (!frame)
333             return nullptr;
334         sibling = frame->tree().nextSibling();
335     }
336
337     if (frame) {
338         ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin));
339         return sibling;
340     }
341
342     return nullptr;
343 }
344
345 Frame* FrameTree::firstRenderedChild() const
346 {
347     Frame* child = firstChild();
348     if (!child)
349         return nullptr;
350     
351     if (child->ownerRenderer())
352         return child;
353
354     while ((child = child->tree().nextSibling())) {
355         if (child->ownerRenderer())
356             return child;
357     }
358     
359     return nullptr;
360 }
361
362 Frame* FrameTree::nextRenderedSibling() const
363 {
364     Frame* sibling = &m_thisFrame;
365
366     while ((sibling = sibling->tree().nextSibling())) {
367         if (sibling->ownerRenderer())
368             return sibling;
369     }
370     
371     return nullptr;
372 }
373
374 Frame* FrameTree::traverseNextRendered(const Frame* stayWithin) const
375 {
376     Frame* child = firstRenderedChild();
377     if (child) {
378         ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin));
379         return child;
380     }
381
382     if (&m_thisFrame == stayWithin)
383         return nullptr;
384
385     Frame* sibling = nextRenderedSibling();
386     if (sibling) {
387         ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin));
388         return sibling;
389     }
390
391     Frame* frame = &m_thisFrame;
392     while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) {
393         frame = frame->tree().parent();
394         if (!frame)
395             return nullptr;
396         sibling = frame->tree().nextRenderedSibling();
397     }
398
399     if (frame) {
400         ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin));
401         return sibling;
402     }
403
404     return nullptr;
405 }
406
407 Frame* FrameTree::traverseNext(CanWrap canWrap, DidWrap* didWrap) const
408 {
409     if (Frame* result = traverseNext())
410         return result;
411
412     if (canWrap == CanWrap::Yes) {
413         if (didWrap)
414             *didWrap = DidWrap::Yes;
415         return &m_thisFrame.mainFrame();
416     }
417
418     return nullptr;
419 }
420
421 Frame* FrameTree::traversePrevious(CanWrap canWrap, DidWrap* didWrap) const
422 {
423     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
424
425     if (Frame* prevSibling = previousSibling())
426         return prevSibling->tree().deepLastChild();
427     if (Frame* parentFrame = parent())
428         return parentFrame;
429     
430     // no siblings, no parent, self==top
431     if (canWrap == CanWrap::Yes) {
432         if (didWrap)
433             *didWrap = DidWrap::Yes;
434         return deepLastChild();
435     }
436
437     // top view is always the last one in this ordering, so prev is nil without wrap
438     return nullptr;
439 }
440
441 Frame* FrameTree::traverseNextInPostOrder(CanWrap canWrap) const
442 {
443     if (m_nextSibling)
444         return m_nextSibling->tree().deepFirstChild();
445     if (m_parent)
446         return m_parent;
447     if (canWrap == CanWrap::Yes)
448         return deepFirstChild();
449     return nullptr;
450 }
451
452 Frame* FrameTree::deepFirstChild() const
453 {
454     Frame* result = &m_thisFrame;
455     while (auto* next = result->tree().firstChild())
456         result = next;
457     return result;
458 }
459
460 Frame* FrameTree::deepLastChild() const
461 {
462     Frame* result = &m_thisFrame;
463     for (Frame* last = lastChild(); last; last = last->tree().lastChild())
464         result = last;
465
466     return result;
467 }
468
469 Frame& FrameTree::top() const
470 {
471     Frame* frame = &m_thisFrame;
472     for (Frame* parent = &m_thisFrame; parent; parent = parent->tree().parent())
473         frame = parent;
474     return *frame;
475 }
476
477 } // namespace WebCore
478
479 #ifndef NDEBUG
480
481 static void printIndent(int indent)
482 {
483     for (int i = 0; i < indent; ++i)
484         printf("    ");
485 }
486
487 static void printFrames(const WebCore::Frame& frame, const WebCore::Frame* targetFrame, int indent)
488 {
489     if (&frame == targetFrame) {
490         printf("--> ");
491         printIndent(indent - 1);
492     } else
493         printIndent(indent);
494
495     WebCore::FrameView* view = frame.view();
496     printf("Frame %p %dx%d\n", &frame, view ? view->width() : 0, view ? view->height() : 0);
497     printIndent(indent);
498     printf("  ownerElement=%p\n", frame.ownerElement());
499     printIndent(indent);
500     printf("  frameView=%p (needs layout %d)\n", view, view ? view->needsLayout() : false);
501     printIndent(indent);
502     printf("  renderView=%p\n", view ? view->renderView() : nullptr);
503     printIndent(indent);
504     printf("  ownerRenderer=%p\n", frame.ownerRenderer());
505     printIndent(indent);
506     printf("  document=%p (needs style recalc %d)\n", frame.document(), frame.document() ? frame.document()->childNeedsStyleRecalc() : false);
507     printIndent(indent);
508     printf("  uri=%s\n", frame.document()->documentURI().utf8().data());
509
510     for (WebCore::Frame* child = frame.tree().firstChild(); child; child = child->tree().nextSibling())
511         printFrames(*child, targetFrame, indent + 1);
512 }
513
514 void showFrameTree(const WebCore::Frame* frame)
515 {
516     if (!frame) {
517         printf("Null input frame\n");
518         return;
519     }
520
521     printFrames(frame->tree().top(), frame, 0);
522 }
523
524 #endif