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 #include <wtf/text/CString.h>
  33
  34 using std::swap;
  35
  36 namespace WebCore {
  37
  38 FrameTree::~FrameTree()
  39 {
  40     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
  41         child->setView(0);
  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 = AtomicString(); // 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 = AtomicString();
  58     m_uniqueName = AtomicString();
  59 }
  60
  61 Frame* FrameTree::parent() const
  62 {
  63     return m_parent;
  64 }
  65
  66 bool 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
  85 void 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
  92 void 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_scopedChildCount = invalidCount;
 105
 106     ASSERT(!m_lastChild->tree()->m_nextSibling);
 107 }
 108
 109 void 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_scopedChildCount = invalidCount;
 127 }
 128
 129 AtomicString 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
 178 inline Frame* FrameTree::scopedChild(unsigned index, TreeScope* scope) const
 179 {
 180     unsigned scopedIndex = 0;
 181     for (Frame* result = firstChild(); result; result = result->tree()->nextSibling()) {
 182         if (result->inScope(scope)) {
 183             if (scopedIndex == index)
 184                 return result;
 185             scopedIndex++;
 186         }
 187     }
 188
 189     return 0;
 190 }
 191
 192 inline Frame* FrameTree::scopedChild(const AtomicString& name, TreeScope* scope) const
 193 {
 194     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
 195         if (child->tree()->uniqueName() == name && child->inScope(scope))
 196             return child;
 197     return 0;
 198 }
 199
 200 inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const
 201 {
 202     unsigned scopedCount = 0;
 203     for (Frame* result = firstChild(); result; result = result->tree()->nextSibling()) {
 204         if (result->inScope(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 0;
 250 }
 251
 252 Frame* FrameTree::find(const AtomicString& name) const
 253 {
 254     if (name == "_self" || name == "_current" || name.isEmpty())
 255         return m_thisFrame;
 256
 257     if (name == "_top")
 258         return top();
 259
 260     if (name == "_parent")
 261         return parent() ? parent() : m_thisFrame;
 262
 263     // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
 264     if (name == "_blank")
 265         return 0;
 266
 267     // Search subtree starting with this frame first.
 268     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
 269         if (frame->tree()->uniqueName() == name)
 270             return frame;
 271
 272     // Search the entire tree for this page next.
 273     Page* page = m_thisFrame->page();
 274
 275     // The frame could have been detached from the page, so check it.
 276     if (!page)
 277         return 0;
 278
 279     for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
 280         if (frame->tree()->uniqueName() == name)
 281             return frame;
 282
 283     // Search the entire tree of each of the other pages in this namespace.
 284     // FIXME: Is random order OK?
 285     const HashSet<Page*>& pages = page->group().pages();
 286     HashSet<Page*>::const_iterator end = pages.end();
 287     for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
 288         Page* otherPage = *it;
 289         if (otherPage != page) {
 290             for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
 291                 if (frame->tree()->uniqueName() == name)
 292                     return frame;
 293             }
 294         }
 295     }
 296
 297     return 0;
 298 }
 299
 300 bool FrameTree::isDescendantOf(const Frame* ancestor) const
 301 {
 302     if (!ancestor)
 303         return false;
 304
 305     if (m_thisFrame->page() != ancestor->page())
 306         return false;
 307
 308     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
 309         if (frame == ancestor)
 310             return true;
 311     return false;
 312 }
 313
 314 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
 315 {
 316     Frame* child = firstChild();
 317     if (child) {
 318         ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
 319         return child;
 320     }
 321
 322     if (m_thisFrame == stayWithin)
 323         return 0;
 324
 325     Frame* sibling = nextSibling();
 326     if (sibling) {
 327         ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
 328         return sibling;
 329     }
 330
 331     Frame* frame = m_thisFrame;
 332     while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
 333         frame = frame->tree()->parent();
 334         if (!frame)
 335             return 0;
 336         sibling = frame->tree()->nextSibling();
 337     }
 338
 339     if (frame) {
 340         ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
 341         return sibling;
 342     }
 343
 344     return 0;
 345 }
 346
 347 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
 348 {
 349     if (Frame* result = traverseNext())
 350         return result;
 351
 352     if (wrap)
 353         return m_thisFrame->page()->mainFrame();
 354
 355     return 0;
 356 }
 357
 358 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
 359 {
 360     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
 361
 362     if (Frame* prevSibling = previousSibling())
 363         return prevSibling->tree()->deepLastChild();
 364     if (Frame* parentFrame = parent())
 365         return parentFrame;
 366
 367     // no siblings, no parent, self==top
 368     if (wrap)
 369         return deepLastChild();
 370
 371     // top view is always the last one in this ordering, so prev is nil without wrap
 372     return 0;
 373 }
 374
 375 Frame* FrameTree::deepLastChild() const
 376 {
 377     Frame* result = m_thisFrame;
 378     for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
 379         result = last;
 380
 381     return result;
 382 }
 383
 384 Frame* FrameTree::top() const
 385 {
 386     Frame* frame = m_thisFrame;
 387     for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent())
 388         frame = parent;
 389     return frame;
 390 }
 391
 392 } // namespace WebCore
 393
 394 #ifndef NDEBUG
 395
 396 static void printIndent(int indent)
 397 {
 398     for (int i = 0; i < indent; ++i)
 399         printf("    ");
 400 }
 401
 402 static void printFrames(const WebCore::Frame* frame, const WebCore::Frame* targetFrame, int indent)
 403 {
 404     if (frame == targetFrame) {
 405         printf("--> ");
 406         printIndent(indent - 1);
 407     } else
 408         printIndent(indent);
 409
 410     WebCore::FrameView* view = frame->view();
 411     printf("Frame %p %dx%d\n", frame, view ? view->width() : 0, view ? view->height() : 0);
 412     printIndent(indent);
 413     printf("  ownerElement=%p\n", frame->ownerElement());
 414     printIndent(indent);
 415     printf("  frameView=%p\n", view);
 416     printIndent(indent);
 417     printf("  document=%p\n", frame->document());
 418     printIndent(indent);
 419     printf("  uri=%s\n\n", frame->document()->documentURI().utf8().data());
 420
 421     for (WebCore::Frame* child = frame->tree()->firstChild(); child; child = child->tree()->nextSibling())
 422         printFrames(child, targetFrame, indent + 1);
 423 }
 424
 425 void showFrameTree(const WebCore::Frame* frame)
 426 {
 427     if (!frame) {
 428         printf("Null input frame\n");
 429         return;
 430     }
 431
 432     printFrames(frame->tree()->top(), frame, 0);
 433 }
 434
 435 #endif