Source/WebCore/page/FrameTree.cpp

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