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