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/FrameClient.h"
  26 #include "core/frame/FrameView.h"
  27 #include "core/frame/LocalFrame.h"
  28 #include "core/frame/RemoteFrame.h"
  29 #include "core/frame/RemoteFrameView.h"
  30 #include "core/page/Page.h"
  31 #include "wtf/Vector.h"
  32 #include "wtf/text/CString.h"
  33 #include "wtf/text/StringBuilder.h"
  34
  35 using std::swap;
  36
  37 namespace blink {
  38
  39 namespace {
  40
  41 const unsigned invalidChildCount = ~0U;
  42
  43 } // namespace
  44
  45 FrameTree::FrameTree(Frame* thisFrame)
  46     : m_thisFrame(thisFrame)
  47     , m_scopedChildCount(invalidChildCount)
  48 {
  49 }
  50
  51 FrameTree::~FrameTree()
  52 {
  53 #if !ENABLE(OILPAN)
  54     // FIXME: Why is this here? Doesn't this parallel what we already do in ~LocalFrame?
  55     for (Frame* child = firstChild(); child; child = child->tree().nextSibling()) {
  56         if (child->isLocalFrame())
  57             toLocalFrame(child)->setView(nullptr);
  58         else if (child->isRemoteFrame())
  59             toRemoteFrame(child)->setView(nullptr);
  60     }
  61 #endif
  62 }
  63
  64 void FrameTree::setName(const AtomicString& name, const AtomicString& fallbackName)
  65 {
  66     m_name = name;
  67     if (!parent()) {
  68         m_uniqueName = name;
  69         return;
  70     }
  71     m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
  72     m_uniqueName = parent()->tree().uniqueChildName(name.isEmpty() ? fallbackName : name);
  73 }
  74
  75 Frame* FrameTree::parent() const
  76 {
  77     if (!m_thisFrame->client())
  78         return 0;
  79     return m_thisFrame->client()->parent();
  80 }
  81
  82 Frame* FrameTree::top() const
  83 {
  84     // FIXME: top() should never return null, so here are some hacks to deal
  85     // with EmptyFrameLoaderClient and cases where the frame is detached
  86     // already...
  87     if (!m_thisFrame->client())
  88         return m_thisFrame;
  89     Frame* candidate = m_thisFrame->client()->top();
  90     return candidate ? candidate : m_thisFrame.get();
  91 }
  92
  93 Frame* FrameTree::previousSibling() const
  94 {
  95     if (!m_thisFrame->client())
  96         return 0;
  97     return m_thisFrame->client()->previousSibling();
  98 }
  99
 100 Frame* FrameTree::nextSibling() const
 101 {
 102     if (!m_thisFrame->client())
 103         return 0;
 104     return m_thisFrame->client()->nextSibling();
 105 }
 106
 107 Frame* FrameTree::firstChild() const
 108 {
 109     if (!m_thisFrame->client())
 110         return 0;
 111     return m_thisFrame->client()->firstChild();
 112 }
 113
 114 Frame* FrameTree::lastChild() const
 115 {
 116     if (!m_thisFrame->client())
 117         return 0;
 118     return m_thisFrame->client()->lastChild();
 119 }
 120
 121 bool FrameTree::uniqueNameExists(const AtomicString& name) const
 122 {
 123     for (Frame* frame = top(); frame; frame = frame->tree().traverseNext()) {
 124         if (frame->tree().uniqueName() == name)
 125             return true;
 126     }
 127     return false;
 128 }
 129
 130 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
 131 {
 132     if (!requestedName.isEmpty() && !uniqueNameExists(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     StringBuilder name;
 155     name.append(framePathPrefix);
 156     if (frame) {
 157         name.append(frame->tree().uniqueName().string().substring(framePathPrefixLength,
 158             frame->tree().uniqueName().length() - framePathPrefixLength - framePathSuffixLength));
 159     }
 160     for (int i = chain.size() - 1; i >= 0; --i) {
 161         frame = chain[i];
 162         name.append('/');
 163         name.append(frame->tree().uniqueName());
 164     }
 165
 166     name.appendLiteral("/<!--frame");
 167     name.appendNumber(childCount() - 1);
 168     name.appendLiteral("-->-->");
 169
 170     return name.toAtomicString();
 171 }
 172
 173 Frame* FrameTree::scopedChild(unsigned index) const
 174 {
 175     if (!m_thisFrame->isLocalFrame())
 176         return 0;
 177     TreeScope* scope = toLocalFrame(m_thisFrame)->document();
 178     if (!scope)
 179         return 0;
 180
 181     unsigned scopedIndex = 0;
 182     for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
 183         if (result->isLocalFrame() && toLocalFrame(result)->inScope(scope)) {
 184             if (scopedIndex == index)
 185                 return result;
 186             scopedIndex++;
 187         }
 188     }
 189
 190     return 0;
 191 }
 192
 193 Frame* FrameTree::scopedChild(const AtomicString& name) const
 194 {
 195     if (!m_thisFrame->isLocalFrame())
 196         return 0;
 197
 198     TreeScope* scope = toLocalFrame(m_thisFrame)->document();
 199     if (!scope)
 200         return 0;
 201
 202     for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
 203         if (child->tree().name() == name && child->isLocalFrame() && toLocalFrame(child)->inScope(scope))
 204             return child;
 205     return 0;
 206 }
 207
 208 inline unsigned FrameTree::scopedChildCount(TreeScope* scope) const
 209 {
 210     if (!scope)
 211         return 0;
 212
 213     unsigned scopedCount = 0;
 214     for (Frame* result = firstChild(); result; result = result->tree().nextSibling()) {
 215         if (result->isLocalFrame() && toLocalFrame(result)->inScope(scope))
 216             scopedCount++;
 217     }
 218
 219     return scopedCount;
 220 }
 221
 222 unsigned FrameTree::scopedChildCount() const
 223 {
 224     if (m_scopedChildCount == invalidChildCount)
 225         m_scopedChildCount = scopedChildCount(toLocalFrame(m_thisFrame)->document());
 226     return m_scopedChildCount;
 227 }
 228
 229 void FrameTree::invalidateScopedChildCount()
 230 {
 231     m_scopedChildCount = invalidChildCount;
 232 }
 233
 234 unsigned FrameTree::childCount() const
 235 {
 236     unsigned count = 0;
 237     for (Frame* result = firstChild(); result; result = result->tree().nextSibling())
 238         ++count;
 239     return count;
 240 }
 241
 242 Frame* FrameTree::child(const AtomicString& name) const
 243 {
 244     for (Frame* child = firstChild(); child; child = child->tree().nextSibling())
 245         if (child->tree().name() == name)
 246             return child;
 247     return 0;
 248 }
 249
 250 Frame* FrameTree::find(const AtomicString& name) const
 251 {
 252     if (name == "_self" || name == "_current" || name.isEmpty())
 253         return m_thisFrame;
 254
 255     if (name == "_top")
 256         return top();
 257
 258     if (name == "_parent")
 259         return parent() ? parent() : m_thisFrame.get();
 260
 261     // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
 262     if (name == "_blank")
 263         return 0;
 264
 265     // Search subtree starting with this frame first.
 266     for (Frame* frame = m_thisFrame; frame; frame = frame->tree().traverseNext(m_thisFrame))
 267         if (frame->tree().name() == name)
 268             return frame;
 269
 270     // Search the entire tree for this page next.
 271     Page* page = m_thisFrame->page();
 272
 273     // The frame could have been detached from the page, so check it.
 274     if (!page)
 275         return 0;
 276
 277     for (Frame* frame = page->mainFrame(); frame; frame = frame->tree().traverseNext())
 278         if (frame->tree().name() == name)
 279             return frame;
 280
 281     // Search the entire tree of each of the other pages in this namespace.
 282     // FIXME: Is random order OK?
 283     const HashSet<Page*>& pages = Page::ordinaryPages();
 284     HashSet<Page*>::const_iterator end = pages.end();
 285     for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
 286         Page* otherPage = *it;
 287         if (otherPage != page) {
 288             for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree().traverseNext()) {
 289                 if (frame->tree().name() == name)
 290                     return frame;
 291             }
 292         }
 293     }
 294
 295     return 0;
 296 }
 297
 298 bool FrameTree::isDescendantOf(const Frame* ancestor) const
 299 {
 300     if (!ancestor)
 301         return false;
 302
 303     if (m_thisFrame->page() != ancestor->page())
 304         return false;
 305
 306     for (Frame* frame = m_thisFrame; frame; frame = frame->tree().parent())
 307         if (frame == ancestor)
 308             return true;
 309     return false;
 310 }
 311
 312 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
 313 {
 314     Frame* child = firstChild();
 315     if (child) {
 316         ASSERT(!stayWithin || child->tree().isDescendantOf(stayWithin));
 317         return child;
 318     }
 319
 320     if (m_thisFrame == stayWithin)
 321         return 0;
 322
 323     Frame* sibling = nextSibling();
 324     if (sibling) {
 325         ASSERT(!stayWithin || sibling->tree().isDescendantOf(stayWithin));
 326         return sibling;
 327     }
 328
 329     Frame* frame = m_thisFrame;
 330     while (!sibling && (!stayWithin || frame->tree().parent() != stayWithin)) {
 331         frame = frame->tree().parent();
 332         if (!frame)
 333             return 0;
 334         sibling = frame->tree().nextSibling();
 335     }
 336
 337     if (frame) {
 338         ASSERT(!stayWithin || !sibling || sibling->tree().isDescendantOf(stayWithin));
 339         return sibling;
 340     }
 341
 342     return 0;
 343 }
 344
 345 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
 346 {
 347     if (Frame* result = traverseNext())
 348         return result;
 349
 350     if (wrap)
 351         return m_thisFrame->page()->mainFrame();
 352
 353     return 0;
 354 }
 355
 356 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
 357 {
 358     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm
 359
 360     if (Frame* prevSibling = previousSibling())
 361         return prevSibling->tree().deepLastChild();
 362     if (Frame* parentFrame = parent())
 363         return parentFrame;
 364
 365     // no siblings, no parent, self==top
 366     if (wrap)
 367         return deepLastChild();
 368
 369     // top view is always the last one in this ordering, so prev is nil without wrap
 370     return 0;
 371 }
 372
 373 Frame* FrameTree::deepLastChild() const
 374 {
 375     Frame* result = m_thisFrame;
 376     for (Frame* last = lastChild(); last; last = last->tree().lastChild())
 377         result = last;
 378
 379     return result;
 380 }
 381
 382 void FrameTree::trace(Visitor* visitor)
 383 {
 384     visitor->trace(m_thisFrame);
 385 }
 386
 387 } // namespace blink
 388
 389 #ifndef NDEBUG
 390
 391 static void printIndent(int indent)
 392 {
 393     for (int i = 0; i < indent; ++i)
 394         printf("    ");
 395 }
 396
 397 static void printFrames(const blink::Frame* frame, const blink::Frame* targetFrame, int indent)
 398 {
 399     if (frame == targetFrame) {
 400         printf("--> ");
 401         printIndent(indent - 1);
 402     } else
 403         printIndent(indent);
 404
 405     blink::FrameView* view = frame->isLocalFrame() ? toLocalFrame(frame)->view() : 0;
 406     printf("Frame %p %dx%d\n", frame, view ? view->width() : 0, view ? view->height() : 0);
 407     printIndent(indent);
 408     printf("  owner=%p\n", frame->owner());
 409     printIndent(indent);
 410     printf("  frameView=%p\n", view);
 411     printIndent(indent);
 412     printf("  document=%p\n", frame->isLocalFrame() ? toLocalFrame(frame)->document() : 0);
 413     printIndent(indent);
 414     printf("  uri=%s\n\n", frame->isLocalFrame() ? toLocalFrame(frame)->document()->url().string().utf8().data() : 0);
 415
 416     for (blink::Frame* child = frame->tree().firstChild(); child; child = child->tree().nextSibling())
 417         printFrames(child, targetFrame, indent + 1);
 418 }
 419
 420 void showFrameTree(const blink::Frame* frame)
 421 {
 422     if (!frame) {
 423         printf("Null input frame\n");
 424         return;
 425     }
 426
 427     printFrames(frame->tree().top(), frame, 0);
 428 }
 429
 430 #endif