Source/WebCore/page/FrameTree.cpp - platform/external/webkit - Git at Google

 /*
  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
  * Copyright (C) 2006 Apple Computer, Inc.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Library General Public License for more details.
  *
  * You should have received a copy of the GNU Library General Public License
  * along with this library; see the file COPYING.LIB.  If not, write to
  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  * Boston, MA 02110-1301, USA.
  */

 #include "config.h"
 #include "FrameTree.h"

 #include "Frame.h"
 #include "FrameView.h"
 #include "Page.h"
 #include "PageGroup.h"
 #include <stdarg.h>
 #include <wtf/StringExtras.h>
 #include <wtf/Vector.h>

 using std::swap;

 namespace WebCore {

 FrameTree::~FrameTree()
 {
     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
         child->setView(0);
 }

 void FrameTree::setName(const AtomicString& name)
 {
     m_name = name;
     if (!parent()) {
         m_uniqueName = name;
         return;
     }
     m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
     m_uniqueName = parent()->tree()->uniqueChildName(name);
 }

 void FrameTree::clearName()
 {
     m_name = AtomicString();
     m_uniqueName = AtomicString();
 }

 Frame* FrameTree::parent(bool checkForDisconnectedFrame) const
 {
     if (checkForDisconnectedFrame && m_thisFrame->isDisconnected())
         return 0;
     return m_parent;
 }

 bool FrameTree::transferChild(PassRefPtr<Frame> child)
 {
     Frame* oldParent = child->tree()->parent();
     if (oldParent == m_thisFrame)
         return false; // |child| is already a child of m_thisFrame.

     if (oldParent)
         oldParent->tree()->removeChild(child.get());

     ASSERT(child->page() == m_thisFrame->page());
     child->tree()->m_parent = m_thisFrame;

     // We need to ensure that the child still has a unique frame name with respect to its new parent.
     child->tree()->setName(child->tree()->m_name);

     actuallyAppendChild(child); // Note, on return |child| is null.
     return true;
 }

 void FrameTree::appendChild(PassRefPtr<Frame> child)
 {
     ASSERT(child->page() == m_thisFrame->page());
     child->tree()->m_parent = m_thisFrame;
     actuallyAppendChild(child); // Note, on return |child| is null.
 }

 void FrameTree::actuallyAppendChild(PassRefPtr<Frame> child)
 {
     ASSERT(child->tree()->m_parent == m_thisFrame);
     Frame* oldLast = m_lastChild;
     m_lastChild = child.get();

     if (oldLast) {
         child->tree()->m_previousSibling = oldLast;
         oldLast->tree()->m_nextSibling = child;
     } else
         m_firstChild = child;

     m_childCount++;

     ASSERT(!m_lastChild->tree()->m_nextSibling);
 }

 void FrameTree::removeChild(Frame* child)
 {
     child->tree()->m_parent = 0;

     // Slightly tricky way to prevent deleting the child until we are done with it, w/o
     // extra refs. These swaps leave the child in a circular list by itself. Clearing its
     // previous and next will then finally deref it.

     RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling;
     Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling;
     swap(newLocationForNext, child->tree()->m_nextSibling);
     // For some inexplicable reason, the following line does not compile without the explicit std:: namespace
     std::swap(newLocationForPrevious, child->tree()->m_previousSibling);

     child->tree()->m_previousSibling = 0;
     child->tree()->m_nextSibling = 0;

     m_childCount--;
 }

 AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
 {
     if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
         return requestedName;

     // Create a repeatable name for a child about to be added to us. The name must be
     // unique within the frame tree. The string we generate includes a "path" of names
     // from the root frame down to us. For this path to be unique, each set of siblings must
     // contribute a unique name to the path, which can't collide with any HTML-assigned names.
     // We generate this path component by index in the child list along with an unlikely
     // frame name that can't be set in HTML because it collides with comment syntax.

     const char framePathPrefix[] = "<!--framePath ";
     const int framePathPrefixLength = 14;
     const int framePathSuffixLength = 3;

     // Find the nearest parent that has a frame with a path in it.
     Vector<Frame*, 16> chain;
     Frame* frame;
     for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
         if (frame->tree()->uniqueName().startsWith(framePathPrefix))
             break;
         chain.append(frame);
     }
     String name;
     name += framePathPrefix;
     if (frame)
         name += frame->tree()->uniqueName().string().substring(framePathPrefixLength,
             frame->tree()->uniqueName().length() - framePathPrefixLength - framePathSuffixLength);
     for (int i = chain.size() - 1; i >= 0; --i) {
         frame = chain[i];
         name += "/";
         name += frame->tree()->uniqueName();
     }

     // Suffix buffer has more than enough space for:
     //     10 characters before the number
     //     a number (20 digits for the largest 64-bit integer)
     //     6 characters after the number
     //     trailing null byte
     // But we still use snprintf just to be extra-safe.
     char suffix[40];
     snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());

     name += suffix;

     return AtomicString(name);
 }

 Frame* FrameTree::child(unsigned index) const
 {
     Frame* result = firstChild();
     for (unsigned i = 0; result && i != index; ++i)
         result = result->tree()->nextSibling();
     return result;
 }

 Frame* FrameTree::child(const AtomicString& name) const
 {
     for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
         if (child->tree()->uniqueName() == name)
             return child;
     return 0;
 }

 Frame* FrameTree::find(const AtomicString& name) const
 {
     if (name == "_self" || name == "_current" || name.isEmpty())
         return m_thisFrame;

     if (name == "_top")
         return top();

     if (name == "_parent")
         return parent() ? parent() : m_thisFrame;

     // Since "_blank" should never be any frame's name, the following just amounts to an optimization.
     if (name == "_blank")
         return 0;

     // Search subtree starting with this frame first.
     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
         if (frame->tree()->uniqueName() == name)
             return frame;

     // Search the entire tree for this page next.
     Page* page = m_thisFrame->page();

     // The frame could have been detached from the page, so check it.
     if (!page)
         return 0;

     for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
         if (frame->tree()->uniqueName() == name)
             return frame;

     // Search the entire tree of each of the other pages in this namespace.
     // FIXME: Is random order OK?
     const HashSet<Page*>& pages = page->group().pages();
     HashSet<Page*>::const_iterator end = pages.end();
     for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
         Page* otherPage = *it;
         if (otherPage != page) {
             for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
                 if (frame->tree()->uniqueName() == name)
                     return frame;
             }
         }
     }

     return 0;
 }

 bool FrameTree::isDescendantOf(const Frame* ancestor) const
 {
     if (!ancestor)
         return false;

     if (m_thisFrame->page() != ancestor->page())
         return false;

     for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
         if (frame == ancestor)
             return true;
     return false;
 }

 Frame* FrameTree::traverseNext(const Frame* stayWithin) const
 {
     Frame* child = firstChild();
     if (child) {
         ASSERT(!stayWithin || child->tree()->isDescendantOf(stayWithin));
         return child;
     }

     if (m_thisFrame == stayWithin)
         return 0;

     Frame* sibling = nextSibling();
     if (sibling) {
         ASSERT(!stayWithin || sibling->tree()->isDescendantOf(stayWithin));
         return sibling;
     }

     Frame* frame = m_thisFrame;
     while (!sibling && (!stayWithin || frame->tree()->parent() != stayWithin)) {
         frame = frame->tree()->parent();
         if (!frame)
             return 0;
         sibling = frame->tree()->nextSibling();
     }

     if (frame) {
         ASSERT(!stayWithin || !sibling || sibling->tree()->isDescendantOf(stayWithin));
         return sibling;
     }

     return 0;
 }

 Frame* FrameTree::traverseNextWithWrap(bool wrap) const
 {
     if (Frame* result = traverseNext())
         return result;

     if (wrap)
         return m_thisFrame->page()->mainFrame();

     return 0;
 }

 Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
 {
     // FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm

     if (Frame* prevSibling = previousSibling())
         return prevSibling->tree()->deepLastChild();
     if (Frame* parentFrame = parent())
         return parentFrame;

     // no siblings, no parent, self==top
     if (wrap)
         return deepLastChild();

     // top view is always the last one in this ordering, so prev is nil without wrap
     return 0;
 }

 Frame* FrameTree::deepLastChild() const
 {
     Frame* result = m_thisFrame;
     for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
         result = last;

     return result;
 }

 Frame* FrameTree::top(bool checkForDisconnectedFrame) const
 {
     Frame* frame = m_thisFrame;
     for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent()) {
         frame = parent;
         if (checkForDisconnectedFrame && frame->isDisconnected())
             return frame;
     }
     return frame;
 }

 } // namespace WebCore
	/*
	* Copyright (C) Research In Motion Limited 2010. All rights reserved.
	* Copyright (C) 2006 Apple Computer, Inc.
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Library General Public
	* License as published by the Free Software Foundation; either
	* version 2 of the License, or (at your option) any later version.
	*
	* This library is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	* Library General Public License for more details.
	*
	* You should have received a copy of the GNU Library General Public License
	* along with this library; see the file COPYING.LIB. If not, write to
	* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
	* Boston, MA 02110-1301, USA.
	*/

	#include "config.h"
	#include "FrameTree.h"

	#include "Frame.h"
	#include "FrameView.h"
	#include "Page.h"
	#include "PageGroup.h"
	#include <stdarg.h>
	#include <wtf/StringExtras.h>
	#include <wtf/Vector.h>

	using std::swap;

	namespace WebCore {

	FrameTree::~FrameTree()
	{
	for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
	child->setView(0);
	}

	void FrameTree::setName(const AtomicString& name)
	{
	m_name = name;
	if (!parent()) {
	m_uniqueName = name;
	return;
	}
	m_uniqueName = AtomicString(); // Remove our old frame name so it's not considered in uniqueChildName.
	m_uniqueName = parent()->tree()->uniqueChildName(name);
	}

	void FrameTree::clearName()
	{
	m_name = AtomicString();
	m_uniqueName = AtomicString();
	}

	Frame* FrameTree::parent(bool checkForDisconnectedFrame) const
	{
	if (checkForDisconnectedFrame && m_thisFrame->isDisconnected())
	return 0;
	return m_parent;
	}

	bool FrameTree::transferChild(PassRefPtr<Frame> child)
	{
	Frame* oldParent = child->tree()->parent();
	if (oldParent == m_thisFrame)
	return false; // \|child\| is already a child of m_thisFrame.

	if (oldParent)
	oldParent->tree()->removeChild(child.get());

	ASSERT(child->page() == m_thisFrame->page());
	child->tree()->m_parent = m_thisFrame;

	// We need to ensure that the child still has a unique frame name with respect to its new parent.
	child->tree()->setName(child->tree()->m_name);

	actuallyAppendChild(child); // Note, on return \|child\| is null.
	return true;
	}

	void FrameTree::appendChild(PassRefPtr<Frame> child)
	{
	ASSERT(child->page() == m_thisFrame->page());
	child->tree()->m_parent = m_thisFrame;
	actuallyAppendChild(child); // Note, on return \|child\| is null.
	}

	void FrameTree::actuallyAppendChild(PassRefPtr<Frame> child)
	{
	ASSERT(child->tree()->m_parent == m_thisFrame);
	Frame* oldLast = m_lastChild;
	m_lastChild = child.get();

	if (oldLast) {
	child->tree()->m_previousSibling = oldLast;
	oldLast->tree()->m_nextSibling = child;
	} else
	m_firstChild = child;

	m_childCount++;

	ASSERT(!m_lastChild->tree()->m_nextSibling);
	}

	void FrameTree::removeChild(Frame* child)
	{
	child->tree()->m_parent = 0;

	// Slightly tricky way to prevent deleting the child until we are done with it, w/o
	// extra refs. These swaps leave the child in a circular list by itself. Clearing its
	// previous and next will then finally deref it.

	RefPtr<Frame>& newLocationForNext = m_firstChild == child ? m_firstChild : child->tree()->m_previousSibling->tree()->m_nextSibling;
	Frame*& newLocationForPrevious = m_lastChild == child ? m_lastChild : child->tree()->m_nextSibling->tree()->m_previousSibling;
	swap(newLocationForNext, child->tree()->m_nextSibling);
	// For some inexplicable reason, the following line does not compile without the explicit std:: namespace
	std::swap(newLocationForPrevious, child->tree()->m_previousSibling);

	child->tree()->m_previousSibling = 0;
	child->tree()->m_nextSibling = 0;

	m_childCount--;
	}

	AtomicString FrameTree::uniqueChildName(const AtomicString& requestedName) const
	{
	if (!requestedName.isEmpty() && !child(requestedName) && requestedName != "_blank")
	return requestedName;

	// Create a repeatable name for a child about to be added to us. The name must be
	// unique within the frame tree. The string we generate includes a "path" of names
	// from the root frame down to us. For this path to be unique, each set of siblings must
	// contribute a unique name to the path, which can't collide with any HTML-assigned names.
	// We generate this path component by index in the child list along with an unlikely
	// frame name that can't be set in HTML because it collides with comment syntax.

	const char framePathPrefix[] = "<!--framePath ";
	const int framePathPrefixLength = 14;
	const int framePathSuffixLength = 3;

	// Find the nearest parent that has a frame with a path in it.
	Vector<Frame*, 16> chain;
	Frame* frame;
	for (frame = m_thisFrame; frame; frame = frame->tree()->parent()) {
	if (frame->tree()->uniqueName().startsWith(framePathPrefix))
	break;
	chain.append(frame);
	}
	String name;
	name += framePathPrefix;
	if (frame)
	name += frame->tree()->uniqueName().string().substring(framePathPrefixLength,
	frame->tree()->uniqueName().length() - framePathPrefixLength - framePathSuffixLength);
	for (int i = chain.size() - 1; i >= 0; --i) {
	frame = chain[i];
	name += "/";
	name += frame->tree()->uniqueName();
	}

	// Suffix buffer has more than enough space for:
	// 10 characters before the number
	// a number (20 digits for the largest 64-bit integer)
	// 6 characters after the number
	// trailing null byte
	// But we still use snprintf just to be extra-safe.
	char suffix[40];
	snprintf(suffix, sizeof(suffix), "/<!--frame%u-->-->", childCount());

	name += suffix;

	return AtomicString(name);
	}

	Frame* FrameTree::child(unsigned index) const
	{
	Frame* result = firstChild();
	for (unsigned i = 0; result && i != index; ++i)
	result = result->tree()->nextSibling();
	return result;
	}

	Frame* FrameTree::child(const AtomicString& name) const
	{
	for (Frame* child = firstChild(); child; child = child->tree()->nextSibling())
	if (child->tree()->uniqueName() == name)
	return child;
	return 0;
	}

	Frame* FrameTree::find(const AtomicString& name) const
	{
	if (name == "_self" \|\| name == "_current" \|\| name.isEmpty())
	return m_thisFrame;

	if (name == "_top")
	return top();

	if (name == "_parent")
	return parent() ? parent() : m_thisFrame;

	// Since "_blank" should never be any frame's name, the following just amounts to an optimization.
	if (name == "_blank")
	return 0;

	// Search subtree starting with this frame first.
	for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->traverseNext(m_thisFrame))
	if (frame->tree()->uniqueName() == name)
	return frame;

	// Search the entire tree for this page next.
	Page* page = m_thisFrame->page();

	// The frame could have been detached from the page, so check it.
	if (!page)
	return 0;

	for (Frame* frame = page->mainFrame(); frame; frame = frame->tree()->traverseNext())
	if (frame->tree()->uniqueName() == name)
	return frame;

	// Search the entire tree of each of the other pages in this namespace.
	// FIXME: Is random order OK?
	const HashSet<Page*>& pages = page->group().pages();
	HashSet<Page*>::const_iterator end = pages.end();
	for (HashSet<Page*>::const_iterator it = pages.begin(); it != end; ++it) {
	Page* otherPage = *it;
	if (otherPage != page) {
	for (Frame* frame = otherPage->mainFrame(); frame; frame = frame->tree()->traverseNext()) {
	if (frame->tree()->uniqueName() == name)
	return frame;
	}
	}
	}

	return 0;
	}

	bool FrameTree::isDescendantOf(const Frame* ancestor) const
	{
	if (!ancestor)
	return false;

	if (m_thisFrame->page() != ancestor->page())
	return false;

	for (Frame* frame = m_thisFrame; frame; frame = frame->tree()->parent())
	if (frame == ancestor)
	return true;
	return false;
	}

	Frame* FrameTree::traverseNext(const Frame* stayWithin) const
	{
	Frame* child = firstChild();
	if (child) {
	ASSERT(!stayWithin \|\| child->tree()->isDescendantOf(stayWithin));
	return child;
	}

	if (m_thisFrame == stayWithin)
	return 0;

	Frame* sibling = nextSibling();
	if (sibling) {
	ASSERT(!stayWithin \|\| sibling->tree()->isDescendantOf(stayWithin));
	return sibling;
	}

	Frame* frame = m_thisFrame;
	while (!sibling && (!stayWithin \|\| frame->tree()->parent() != stayWithin)) {
	frame = frame->tree()->parent();
	if (!frame)
	return 0;
	sibling = frame->tree()->nextSibling();
	}

	if (frame) {
	ASSERT(!stayWithin \|\| !sibling \|\| sibling->tree()->isDescendantOf(stayWithin));
	return sibling;
	}

	return 0;
	}

	Frame* FrameTree::traverseNextWithWrap(bool wrap) const
	{
	if (Frame* result = traverseNext())
	return result;

	if (wrap)
	return m_thisFrame->page()->mainFrame();

	return 0;
	}

	Frame* FrameTree::traversePreviousWithWrap(bool wrap) const
	{
	// FIXME: besides the wrap feature, this is just the traversePreviousNode algorithm

	if (Frame* prevSibling = previousSibling())
	return prevSibling->tree()->deepLastChild();
	if (Frame* parentFrame = parent())
	return parentFrame;

	// no siblings, no parent, self==top
	if (wrap)
	return deepLastChild();

	// top view is always the last one in this ordering, so prev is nil without wrap
	return 0;
	}

	Frame* FrameTree::deepLastChild() const
	{
	Frame* result = m_thisFrame;
	for (Frame* last = lastChild(); last; last = last->tree()->lastChild())
	result = last;

	return result;
	}

	Frame* FrameTree::top(bool checkForDisconnectedFrame) const
	{
	Frame* frame = m_thisFrame;
	for (Frame* parent = m_thisFrame; parent; parent = parent->tree()->parent()) {
	frame = parent;
	if (checkForDisconnectedFrame && frame->isDisconnected())
	return frame;
	}
	return frame;
	}

	} // namespace WebCore