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