/*
 * 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 "core/page/FrameTree.h"

#include "core/dom/Document.h"
#include "core/frame/FrameClient.h"
#include "core/frame/FrameView.h"
#include "core/frame/LocalFrame.h"
#include "core/frame/RemoteFrame.h"
#include "core/frame/RemoteFrameView.h"
#include "core/page/Page.h"
#include "wtf/Assertions.h"
#include "wtf/Vector.h"
#include "wtf/text/CString.h"
#include "wtf/text/StringBuilder.h"

using std::swap;

namespace blink {

namespace {

const unsigned invalidChildCount = ~0U;

}  // namespace

FrameTree::FrameTree(Frame* thisFrame)
    : m_thisFrame(thisFrame), m_scopedChildCount(invalidChildCount) {}

FrameTree::~FrameTree() {}

void FrameTree::setName(const AtomicString& name) {
  // This method should only be called for local frames
  // (remote frames should be updated via setPrecalculatedName).
  DCHECK(m_thisFrame->isLocalFrame());

  // When this method is called, m_uniqueName should be already initialized.
  // This assert helps ensure that early return (a few lines below) won't
  // result in an uninitialized m_uniqueName.
  DCHECK(!m_uniqueName.isNull() || (m_uniqueName.isNull() && !parent()));

  // Do not recalculate m_uniqueName if there is no real change of m_name.
  // This is not just a performance optimization - other code relies on the
  // assumption that unique name shouldn't change if the assigned name didn't
  // change (i.e. code in content::FrameTreeNode::SetFrameName).
  if (m_name == name)
    return;

  m_name = name;

  // https://crbug.com/607205: Make sure m_uniqueName doesn't change after
  // initial navigation - session history depends on this.
  if (toLocalFrame(m_thisFrame)
          ->loader()
          .stateMachine()
          ->committedFirstRealDocumentLoad())
    return;

  // Leave main frame's unique name set to a null string.
  if (!parent())
    return;

  // Remove our old frame name so it's not considered in
  // calculateUniqueNameForChildFrame call below.
  m_uniqueName = AtomicString();

  // Calculate a new unique name based on inputs.
  setUniqueName(parent()->tree().calculateUniqueNameForChildFrame(
      m_thisFrame, name, nullAtom));
}

void FrameTree::setPrecalculatedName(const AtomicString& name,
                                     const AtomicString& uniqueName) {
  m_name = name;

  if (parent()) {
    // Non-main frames should have a non-empty unique name.
    DCHECK(!uniqueName.isEmpty());
  } else {
    // Unique name of main frames should always stay empty.
    DCHECK(uniqueName.isEmpty());
  }

  // TODO(lukasza): We would like to assert uniqueness below (i.e. by calling
  // setUniqueName), but
  // 1) uniqueness is currently violated by provisional/old frame pairs.
  // 2) there is an unresolved race between 2 OOPIFs, that can result in a
  //    non-unique |uniqueName| - see https://crbug.com/558680#c14.
  m_uniqueName = uniqueName;
}

DISABLE_CFI_PERF
Frame* FrameTree::parent() const {
  if (!m_thisFrame->client())
    return nullptr;
  return m_thisFrame->client()->parent();
}

Frame* FrameTree::top() const {
  // FIXME: top() should never return null, so here are some hacks to deal
  // with EmptyFrameLoaderClient and cases where the frame is detached
  // already...
  if (!m_thisFrame->client())
    return m_thisFrame;
  Frame* candidate = m_thisFrame->client()->top();
  return candidate ? candidate : m_thisFrame.get();
}

Frame* FrameTree::nextSibling() const {
  if (!m_thisFrame->client())
    return nullptr;
  return m_thisFrame->client()->nextSibling();
}

Frame* FrameTree::firstChild() const {
  if (!m_thisFrame->client())
    return nullptr;
  return m_thisFrame->client()->firstChild();
}

bool FrameTree::uniqueNameExists(const String& uniqueNameCandidate) const {
  // This method is currently O(N), where N = number of frames in the tree.

  // Before recalculating or checking unique name, we set m_uniqueName
  // to an empty string (so the soon-to-be-removed name does not count
  // as a collision).  This means that uniqueNameExists would return
  // false positives when called with an empty |name|.
  DCHECK(!uniqueNameCandidate.isEmpty());

  for (Frame* frame = top(); frame; frame = frame->tree().traverseNext()) {
    if (frame->tree().uniqueName() == uniqueNameCandidate)
      return true;
  }
  return false;
}

AtomicString FrameTree::calculateUniqueNameForNewChildFrame(
    const AtomicString& name,
    const AtomicString& fallbackName) const {
  AtomicString uniqueName =
      calculateUniqueNameForChildFrame(nullptr, name, fallbackName);

  // Caller will likely set the name via setPrecalculatedName, which
  // unfortunately cannot currently assert uniqueness of the name - let's
  // therefore assert the uniqueness here.
  DCHECK(!uniqueNameExists(uniqueName));

  return uniqueName;
}

String FrameTree::generateUniqueNameCandidate(bool existingChildFrame) const {
  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.
  HeapVector<Member<Frame>, 16> chain;
  Frame* frame;
  for (frame = m_thisFrame; frame; frame = frame->tree().parent()) {
    if (frame->tree().uniqueName().startsWith(framePathPrefix))
      break;
    chain.push_back(frame);
  }
  StringBuilder uniqueName;
  uniqueName.append(framePathPrefix);
  if (frame) {
    uniqueName.append(frame->tree().uniqueName().getString().substring(
        framePathPrefixLength, frame->tree().uniqueName().length() -
                                   framePathPrefixLength -
                                   framePathSuffixLength));
  }
  for (int i = chain.size() - 1; i >= 0; --i) {
    frame = chain[i];
    uniqueName.append('/');
    uniqueName.append(frame->tree().uniqueName());
  }

  uniqueName.append("/<!--frame");
  uniqueName.appendNumber(childCount() - (existingChildFrame ? 1 : 0));
  uniqueName.append("-->-->");

  // NOTE: This name might not be unique - see http://crbug.com/588800.
  return uniqueName.toAtomicString();
}

String FrameTree::generateFramePosition(Frame* child) const {
  // This method is currently O(N), where N = number of frames in the tree.

  StringBuilder framePositionBuilder;
  framePositionBuilder.append("<!--framePosition");

  if (!child) {
    framePositionBuilder.append('-');
    framePositionBuilder.appendNumber(childCount());
    child = m_thisFrame;
  }

  while (child->tree().parent()) {
    int numberOfSiblingsBeforeChild = 0;
    Frame* sibling = child->tree().parent()->tree().firstChild();
    while (sibling != child) {
      sibling = sibling->tree().nextSibling();
      numberOfSiblingsBeforeChild++;
    }

    framePositionBuilder.append('-');
    framePositionBuilder.appendNumber(numberOfSiblingsBeforeChild);

    child = child->tree().parent();
  }

  // NOTE: The generated string is not guaranteed to be unique, but should
  // have a better chance of being unique than the string generated by
  // generateUniqueNameCandidate, because we embed extra information into the
  // string:
  // 1) we walk the full chain of ancestors, all the way to the main frame
  // 2) we use frame-position-within-parent (aka |numberOfSiblingsBeforeChild|)
  //    instead of sibling-count.
  return framePositionBuilder.toString();
}

AtomicString FrameTree::appendUniqueSuffix(
    const String& prefix,
    const String& likelyUniqueSuffix) const {
  // Verify that we are not doing unnecessary work.
  DCHECK(uniqueNameExists(prefix));

  // We want unique name to be stable across page reloads - this is why
  // we use a deterministic |numberOfTries| rather than a random number
  // (a random number would be more likely to avoid a collision, but
  // would change after every page reload).
  int numberOfTries = 0;

  // Keep trying |prefix| + |likelyUniqueSuffix| + |numberOfTries|
  // concatenations until we get a truly unique name.
  String candidate;
  do {
    StringBuilder uniqueNameBuilder;
    uniqueNameBuilder.append(prefix);
    uniqueNameBuilder.append(likelyUniqueSuffix);
    uniqueNameBuilder.append('/');
    uniqueNameBuilder.appendNumber(numberOfTries++);
    uniqueNameBuilder.append("-->");

    candidate = uniqueNameBuilder.toString();
  } while (uniqueNameExists(candidate));
  return AtomicString(candidate);
}

AtomicString FrameTree::calculateUniqueNameForChildFrame(
    Frame* child,
    const AtomicString& assignedName,
    const AtomicString& fallbackName) const {
  // Try to use |assignedName| (i.e. window.name or iframe.name) or
  // |fallbackName| if possible.
  const AtomicString& requestedName =
      assignedName.isEmpty() ? fallbackName : assignedName;
  if (!requestedName.isEmpty() && !uniqueNameExists(requestedName) &&
      requestedName != "_blank")
    return requestedName;

  String candidate = generateUniqueNameCandidate(child);
  if (!uniqueNameExists(candidate))
    return AtomicString(candidate);

  String likelyUniqueSuffix = generateFramePosition(child);
  return appendUniqueSuffix(candidate, likelyUniqueSuffix);

  // Description of the current unique name format
  // ---------------------------------------------
  //
  // Changing the format of unique name is undesirable, because it breaks
  // backcompatibility of session history (which stores unique names
  // generated in the past on user's disk).  This incremental,
  // backcompatibility-aware approach has resulted so far in the following
  // rather baroque format... :
  //
  //   uniqueName ::= <nullForMainFrame> | <assignedName> | <generatedName>
  //                 (generatedName is used if assignedName is
  //                 non-unique / conflicts with other frame's unique name.
  //
  //   assignedName ::= value of iframe's name attribute
  //                 or value assigned to window.name (*before* the first
  //                    real commit - afterwards unique name stays immutable).
  //
  //   generatedName ::= oldGeneratedName newUniqueSuffix?
  //                  (newUniqueSuffix is only present if oldGeneratedName was
  //                  not unique after all)
  //
  //   oldGeneratedName ::= "<!--framePath //" ancestorChain
  //                        "/<!--frame" childCount "-->-->"
  //                  (oldGeneratedName is generated by
  //                  generateUniqueNameCandidate method).
  //
  //   childCount ::= current number of siblings
  //
  //   ancestorChain ::= concatenated unique names of ancestor chain,
  //                     terminated on the first ancestor (if any) starting with
  //                     "<!--framePath"; each ancestor's unique name is
  //                     separated by "/" character
  //   ancestorChain example1: "grandparent/parent"
  //  (ancestor's unique names :   #1--^   | #2-^ )
  //   ancestorChain example2:
  //                     "<!--framePath //foo/bar/<!--frame42-->-->/blah/foobar"
  //  (ancestor's unique names:
  //                              ^--#1--^                         | #2 | #3-^ )
  //
  //   newUniqueSuffix ::= "<!--framePosition" framePosition "/" retryNumber
  //                       "-->"
  //
  //   framePosition ::= "-" numberOfSiblingsBeforeChild
  //                     [ framePosition-forParent? ]
  //
  //   retryNumber ::= smallest non-negative integer resulting in unique name
}

void FrameTree::setUniqueName(const AtomicString& uniqueName) {
  // Only subframes can have a non-null unique name - setUniqueName should
  // only be called for subframes and never for a main frame.
  DCHECK(parent());

  DCHECK(!uniqueName.isEmpty() && !uniqueNameExists(uniqueName));
  m_uniqueName = uniqueName;
}

Frame* FrameTree::scopedChild(unsigned index) const {
  unsigned scopedIndex = 0;
  for (Frame* child = firstChild(); child;
       child = child->tree().nextSibling()) {
    if (child->client()->inShadowTree())
      continue;
    if (scopedIndex == index)
      return child;
    scopedIndex++;
  }

  return nullptr;
}

Frame* FrameTree::scopedChild(const AtomicString& name) const {
  for (Frame* child = firstChild(); child;
       child = child->tree().nextSibling()) {
    if (child->client()->inShadowTree())
      continue;
    if (child->tree().name() == name)
      return child;
  }
  return nullptr;
}

unsigned FrameTree::scopedChildCount() const {
  if (m_scopedChildCount == invalidChildCount) {
    unsigned scopedCount = 0;
    for (Frame* child = firstChild(); child;
         child = child->tree().nextSibling()) {
      if (child->client()->inShadowTree())
        continue;
      scopedCount++;
    }
    m_scopedChildCount = scopedCount;
  }
  return m_scopedChildCount;
}

void FrameTree::invalidateScopedChildCount() {
  m_scopedChildCount = invalidChildCount;
}

unsigned FrameTree::childCount() const {
  unsigned count = 0;
  for (Frame* result = firstChild(); result;
       result = result->tree().nextSibling())
    ++count;
  return count;
}

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.get();

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

  // Search subtree starting with this frame first.
  for (Frame* frame = m_thisFrame; frame;
       frame = frame->tree().traverseNext(m_thisFrame)) {
    if (frame->tree().name() == 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 nullptr;

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

  // Search the entire tree of each of the other pages in this namespace.
  // FIXME: Is random order OK?
  for (const Page* otherPage : Page::ordinaryPages()) {
    if (otherPage == page || otherPage->isClosing())
      continue;
    for (Frame* frame = otherPage->mainFrame(); frame;
         frame = frame->tree().traverseNext()) {
      if (frame->tree().name() == name)
        return frame;
    }
  }

  return nullptr;
}

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;
}

DISABLE_CFI_PERF
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 nullptr;

  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 nullptr;
    sibling = frame->tree().nextSibling();
  }

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

  return nullptr;
}

DEFINE_TRACE(FrameTree) {
  visitor->trace(m_thisFrame);
}

}  // namespace blink

#ifndef NDEBUG

static void printIndent(int indent) {
  for (int i = 0; i < indent; ++i)
    printf("    ");
}

static void printFrames(const blink::Frame* frame,
                        const blink::Frame* targetFrame,
                        int indent) {
  if (frame == targetFrame) {
    printf("--> ");
    printIndent(indent - 1);
  } else {
    printIndent(indent);
  }

  blink::FrameView* view =
      frame->isLocalFrame() ? toLocalFrame(frame)->view() : 0;
  printf("Frame %p %dx%d\n", frame, view ? view->width() : 0,
         view ? view->height() : 0);
  printIndent(indent);
  printf("  owner=%p\n", frame->owner());
  printIndent(indent);
  printf("  frameView=%p\n", view);
  printIndent(indent);
  printf("  document=%p\n",
         frame->isLocalFrame() ? toLocalFrame(frame)->document() : 0);
  printIndent(indent);
  printf("  uri=%s\n\n",
         frame->isLocalFrame()
             ? toLocalFrame(frame)->document()->url().getString().utf8().data()
             : 0);

  for (blink::Frame* child = frame->tree().firstChild(); child;
       child = child->tree().nextSibling())
    printFrames(child, targetFrame, indent + 1);
}

void showFrameTree(const blink::Frame* frame) {
  if (!frame) {
    printf("Null input frame\n");
    return;
  }

  printFrames(frame->tree().top(), frame, 0);
}

#endif