WebCore/page/FrameTree.cpp

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