// Copyright 2017 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "content/common/unique_name_helper.h"

#include <algorithm>

#include "base/logging.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"

namespace content {

namespace {

using FrameAdapter = UniqueNameHelper::FrameAdapter;

class PendingChildFrameAdapter : public UniqueNameHelper::FrameAdapter {
 public:
  explicit PendingChildFrameAdapter(FrameAdapter* parent) : parent_(parent) {}

  // FrameAdapter overrides:
  bool IsMainFrame() const override { return false; }
  bool IsCandidateUnique(const std::string& name) const override {
    return parent_->IsCandidateUnique(name);
  }
  int GetSiblingCount() const override {
    // Note: no adjustment is required here: since this adapter is an internal
    // helper, the parent FrameAdapter it delegates to won't know about this
    // child to include it in the count.
    return parent_->GetChildCount();
  }
  int GetChildCount() const override {
    NOTREACHED();
    return 0;
  }
  std::vector<base::StringPiece> CollectAncestorNames(
      BeginPoint begin_point,
      bool (*should_stop)(base::StringPiece)) const override {
    DCHECK_EQ(BeginPoint::kParentFrame, begin_point);
    return parent_->CollectAncestorNames(BeginPoint::kThisFrame, should_stop);
  }
  std::vector<int> GetFramePosition(BeginPoint begin_point) const override {
    DCHECK_EQ(BeginPoint::kParentFrame, begin_point);
    return parent_->GetFramePosition(BeginPoint::kThisFrame);
  }

 private:
  FrameAdapter* const parent_;
};

constexpr char kFramePathPrefix[] = "<!--framePath /";
constexpr int kFramePathPrefixLength = 15;
constexpr int kFramePathSuffixLength = 3;

bool IsNameWithFramePath(base::StringPiece name) {
  return name.starts_with(kFramePathPrefix) && name.ends_with("-->") &&
         (kFramePathPrefixLength + kFramePathSuffixLength) < name.size();
}

std::string GenerateCandidate(const FrameAdapter* frame) {
  std::string new_name(kFramePathPrefix);
  std::vector<base::StringPiece> ancestor_names = frame->CollectAncestorNames(
      FrameAdapter::BeginPoint::kParentFrame, &IsNameWithFramePath);
  std::reverse(ancestor_names.begin(), ancestor_names.end());
  // Note: This checks ancestor_names[0] twice, but it's nicer to do the name
  // extraction here rather than passing another function pointer to
  // CollectAncestorNames().
  if (!ancestor_names.empty() && IsNameWithFramePath(ancestor_names[0])) {
    ancestor_names[0] = ancestor_names[0].substr(kFramePathPrefixLength,
                                                 ancestor_names[0].size() -
                                                     kFramePathPrefixLength -
                                                     kFramePathSuffixLength);
  }
  new_name += base::JoinString(ancestor_names, "/");

  new_name += "/<!--frame";
  new_name += base::IntToString(frame->GetSiblingCount());
  new_name += "-->-->";

  // NOTE: This name might not be unique - see http://crbug.com/588800.
  return new_name;
}

std::string GenerateFramePosition(const FrameAdapter* frame) {
  std::string position_string("<!--framePosition");
  std::vector<int> positions =
      frame->GetFramePosition(FrameAdapter::BeginPoint::kParentFrame);
  for (int position : positions) {
    position_string += '-';
    position_string += base::IntToString(position);
  }

  // NOTE: The generated string is not guaranteed to be unique, but should
  // have a better chance of being unique than the string generated by
  // GenerateCandidate, 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 |position_in_parent|)
  //    instead of sibling-count.
  return position_string;
}

std::string AppendUniqueSuffix(const FrameAdapter* frame,
                               const std::string& prefix,
                               const std::string& likely_unique_suffix) {
  // This should only be called if the |prefix| isn't unique, as this is
  // otherwise pointless work.
  DCHECK(!frame->IsCandidateUnique(prefix));

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

  // Keep trying |prefix| + |likely_unique_suffix| + |number_of_tries|
  // concatenations until we get a truly unique name.
  std::string candidate(prefix);
  candidate += likely_unique_suffix;
  candidate += '/';
  while (true) {
    size_t current_length = candidate.size();
    candidate += base::IntToString(number_of_retries++);
    candidate += "-->";
    if (frame->IsCandidateUnique(candidate))
      break;
    candidate.resize(current_length);
  }
  return candidate;
}

std::string CalculateNewName(const FrameAdapter* frame,
                             const std::string& name) {
  if (!name.empty() && frame->IsCandidateUnique(name) && name != "_blank")
    return name;

  std::string candidate = GenerateCandidate(frame);
  if (frame->IsCandidateUnique(candidate))
    return candidate;

  std::string likely_unique_suffix = GenerateFramePosition(frame);
  return AppendUniqueSuffix(frame, candidate, likely_unique_suffix);
}

}  // namespace

UniqueNameHelper::FrameAdapter::~FrameAdapter() {}

UniqueNameHelper::UniqueNameHelper(FrameAdapter* frame) : frame_(frame) {}

UniqueNameHelper::~UniqueNameHelper() {}

std::string UniqueNameHelper::GenerateNameForNewChildFrame(
    const std::string& name) const {
  PendingChildFrameAdapter adapter(frame_);
  return CalculateNewName(&adapter, name);
}

void UniqueNameHelper::UpdateName(const std::string& name) {
  // The unique name of the main frame is always the empty string.
  if (frame_->IsMainFrame())
    return;
  // It's important to clear this before calculating a new name, as the
  // calculation checks for collisions with existing unique names.
  unique_name_.clear();
  unique_name_ = CalculateNewName(frame_, name);
}

}  // namespace content