1/*
2 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
3 * Copyright (C) 2006 Apple Computer, Inc.
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 "Frame.h"
25#include "FrameView.h"
26#include "Page.h"
27#include "PageGroup.h"
28#include <stdarg.h>
29#include <wtf/StringExtras.h>
30#include <wtf/Vector.h>
31
32using std::swap;
33
34namespace WebCore {
35
36FrameTree::~FrameTree()
37{
38    for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
39        child->setView(0);
40}
41
42void FrameTree::setName(const AtomicString& name)
43{
44    m_name = name;
45    if (!parent()) {
46        m_uniqueName = name;
47        return;
48    }
49    m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
50    m_uniqueName = parent()->tree()->uniqueChildName(name);
51}
52
53void FrameTree::clearName()
54{
55    m_name = AtomicString();
56    m_uniqueName = AtomicString();
57}
58
59Frame* FrameTree::parent(bool checkForDisconnectedFrame) const
60{
61    if (checkForDisconnectedFrame && m_thisFrame->isDisconnected())
62        return 0;
63    return m_parent;
64}
65
66bool FrameTree::transferChild(PassRefPtr<Frame> child)
67{
68    Frame* oldParent = child->tree()->parent();
69    if (oldParent == m_thisFrame)
70        return false; // |child| is already a child of m_thisFrame.
71
72    if (oldParent)
73        oldParent->tree()->removeChild(child.get());
74
75    ASSERT(child->page() == m_thisFrame->page());
76    child->tree()->m_parent = m_thisFrame;
77
78    // We need to ensure that the child still has a unique frame name with respect to its new parent.
79    child->tree()->setName(child->tree()->m_name);
80
81    actuallyAppendChild(child); // Note, on return |child| is null.
82    return true;
83}
84
85void FrameTree::appendChild(PassRefPtr<Frame> child)
86{
87    ASSERT(child->page() == m_thisFrame->page());
88    child->tree()->m_parent = m_thisFrame;
89    actuallyAppendChild(child); // Note, on return |child| is null.
90}
91
92void FrameTree::actuallyAppendChild(PassRefPtr<Frame> child)
93{
94    ASSERT(child->tree()->m_parent == m_thisFrame);
95    Frame* oldLast = m_lastChild;
96    m_lastChild = child.get();
97
98    if (oldLast) {
99        child->tree()->m_previousSibling = oldLast;
100        oldLast->tree()->m_nextSibling = child;
101    } else
102        m_firstChild = child;
103
104    m_childCount++;
105
106    ASSERT(!m_lastChild->tree()->m_nextSibling);
107}
108
109void FrameTree::removeChild(Frame* child)
110{
111    child->tree()->m_parent = 0;
112
113    // Slightly tricky way to prevent deleting the child until we are done with it, w/o
114    // extra refs. These swaps leave the child in a circular list by itself. Clearing its
115    // previous and next will then finally deref it.
116
117    RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling;
118    Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling;
119    swap(newLocationForNext, child->tree()->m_nextSibling);
120    // For some inexplicable reason, the following line does not compile without the explicit std:: namespace
121    std::swap(newLocationForPrevious, child->tree()->m_previousSibling);
122
123    child->tree()->m_previousSibling = 0;
124    child->tree()->m_nextSibling = 0;
125
126    m_childCount--;
127}
128
129AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
130{
131    if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
132        return requestedName;
133
134    // Create a repeatable name for a child about to be added to us. The name must be
135    // unique within the frame tree. The string we generate includes a "path" of names
136    // from the root frame down to us. For this path to be unique, each set of siblings must
137    // contribute a unique name to the path, which can't collide with any HTML-assigned names.
138    // We generate this path component by index in the child list along with an unlikely
139    // frame name that can't be set in HTML because it collides with comment syntax.
140
141    const char framePathPrefix[] = "<!--framePath ";
142    const int framePathPrefixLength = 14;
143    const int framePathSuffixLength = 3;
144
145    // Find the nearest parent that has a frame with a path in it.
146    Vector<Frame*, 16> chain;
147    Frame* frame;
148    for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
149        if (frame->tree()->uniqueName().startsWith(framePathPrefix))
150            break;
151        chain.append(frame);
152    }
153    String name;
154    name += framePathPrefix;
155    if (frame)
156        name += frame->tree()->uniqueName().string().substring(framePathPrefixLength,
157            frame->tree()->uniqueName().length() - framePathPrefixLength - framePathSuffixLength);
158    for (int i = chain.size() - 1; i >= 0; --i) {
159        frame = chain[i];
160        name += "/";
161        name += frame->tree()->uniqueName();
162    }
163
164    // Suffix buffer has more than enough space for:
165    //     10 characters before the number
166    //     a number (20 digits for the largest 64-bit integer)
167    //     6 characters after the number
168    //     trailing null byte
169    // But we still use snprintf just to be extra-safe.
170    char suffix[40];
171    snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());
172
173    name += suffix;
174
175    return AtomicString(name);
176}
177
178Frame* FrameTree::child(unsigned index) const
179{
180    Frame* result = firstChild();
181    for (unsigned i = 0; result && i != index; ++i)
182        result = result->tree()->nextSibling();
183    return result;
184}
185
186Frame* FrameTree::child(const AtomicString& name) const
187{
188    for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
189        if (child->tree()->uniqueName() == name)
190            return child;
191    return 0;
192}
193
194Frame* FrameTree::find(const AtomicString& name) const
195{
196    if (name == "_self" || name == "_current" || name.isEmpty())
197        return m_thisFrame;
198
199    if (name == "_top")
200        return top();
201
202    if (name == "_parent")
203        return parent() ? parent() : m_thisFrame;
204
205    // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
206    if (name == "_blank")
207        return 0;
208
209    // Search subtree starting with this frame first.
210    for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
211        if (frame->tree()->uniqueName() == name)
212            return frame;
213
214    // Search the entire tree for this page next.
215    Page* page = m_thisFrame->page();
216
217    // The frame could have been detached from the page, so check it.
218    if (!page)
219        return 0;
220
221    for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
222        if (frame->tree()->uniqueName() == name)
223            return frame;
224
225    // Search the entire tree of each of the other pages in this namespace.
226    // FIXME: Is random order OK?
227    const HashSet<Page*>& pages = page->group().pages();
228    HashSet<Page*>::const_iterator end = pages.end();
229    for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
230        Page* otherPage = *it;
231        if (otherPage != page) {
232            for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
233                if (frame->tree()->uniqueName() == name)
234                    return frame;
235            }
236        }
237    }
238
239    return 0;
240}
241
242bool FrameTree::isDescendantOf(const Frame* ancestor) const
243{
244    if (!ancestor)
245        return false;
246
247    if (m_thisFrame->page() != ancestor->page())
248        return false;
249
250    for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
251        if (frame == ancestor)
252            return true;
253    return false;
254}
255
256Frame* FrameTree::traverseNext(const Frame* stayWithin) const
257{
258    Frame* child = firstChild();
259    if (child) {
260        ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
261        return child;
262    }
263
264    if (m_thisFrame == stayWithin)
265        return 0;
266
267    Frame* sibling = nextSibling();
268    if (sibling) {
269        ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
270        return sibling;
271    }
272
273    Frame* frame = m_thisFrame;
274    while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
275        frame = frame->tree()->parent();
276        if (!frame)
277            return 0;
278        sibling = frame->tree()->nextSibling();
279    }
280
281    if (frame) {
282        ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
283        return sibling;
284    }
285
286    return 0;
287}
288
289Frame* FrameTree::traverseNextWithWrap(bool wrap) const
290{
291    if (Frame* result = traverseNext())
292        return result;
293
294    if (wrap)
295        return m_thisFrame->page()->mainFrame();
296
297    return 0;
298}
299
300Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
301{
302    // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
303
304    if (Frame* prevSibling = previousSibling())
305        return prevSibling->tree()->deepLastChild();
306    if (Frame* parentFrame = parent())
307        return parentFrame;
308
309    // no siblings, no parent, self==top
310    if (wrap)
311        return deepLastChild();
312
313    // top view is always the last one in this ordering, so prev is nil without wrap
314    return 0;
315}
316
317Frame* FrameTree::deepLastChild() const
318{
319    Frame* result = m_thisFrame;
320    for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
321        result = last;
322
323    return result;
324}
325
326Frame* FrameTree::top(bool checkForDisconnectedFrame) const
327{
328    Frame* frame = m_thisFrame;
329    for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent()) {
330        frame = parent;
331        if (checkForDisconnectedFrame && frame->isDisconnected())
332            return frame;
333    }
334    return frame;
335}
336
337} // namespace WebCore
338