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

#include "third_party/blink/public/common/unique_name/unique_name_helper.h"

#include <algorithm>
#include <string_view>
#include <utility>

#include "base/check_op.h"
#include "base/memory/raw_ptr.h"
#include "base/notreached.h"
#include "base/strings/strcat.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "base/unguessable_token.h"
#include "crypto/hash.h"

namespace blink {

namespace {

bool g_preserve_stable_unique_name_for_testing = false;

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(std::string_view 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(); }
  std::vector<std::string> CollectAncestorNames(
      BeginPoint begin_point,
      bool (*should_stop)(std::string_view)) 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:
  const raw_ptr<FrameAdapter> parent_;
};

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

// 80% of unique names are shorter than this, and it also guarantees that this
// won't ever increase the length of a unique name, as a hashed unique name is
// exactly 80 characters.
constexpr size_t kMaxRequestedNameSize = 80;

bool IsNameWithFramePath(std::string_view 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<std::string> 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::NumberToString(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::NumberToString(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::NumberToString(number_of_retries++);
    candidate += "-->";
    if (frame->IsCandidateUnique(candidate))
      break;
    candidate.resize(current_length);
  }
  return candidate;
}

std::string CalculateNameInternal(const FrameAdapter* frame,
                                  std::string_view name) {
  if (!name.empty() && frame->IsCandidateUnique(name) && name != "_blank")
    return std::string(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);
}

std::string CalculateFrameHash(std::string_view name) {
  DCHECK_GT(name.size(), kMaxRequestedNameSize);

  return base::StrCat({"<!--frameHash",
      base::HexEncode(crypto::hash::Sha256(name)),
      "-->"});
}

std::string CalculateNewName(const FrameAdapter* frame, std::string_view name) {
  std::string hashed_name;
  // By default, |name| is the browsing context name, which can be arbitrarily
  // long. Since the generated name is part of history entries and FrameState,
  // hash pathologically long names to avoid using a lot of memory.
  if (name.size() > kMaxRequestedNameSize) {
    hashed_name = CalculateFrameHash(name);
    name = hashed_name;
  }
  return CalculateNameInternal(frame, name);
}

}  // namespace

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

UniqueNameHelper::Replacement::Replacement(std::string old_name,
                                           std::string new_name)
    : old_name(std::move(old_name)), new_name(std::move(new_name)) {}

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

UniqueNameHelper::~UniqueNameHelper() {}

std::string UniqueNameHelper::GenerateNameForNewChildFrame(
    const std::string& name,
    bool is_created_by_script) const {
  std::string unique_name_of_new_child;

  // The deterministic part of unique name should be included if
  // 1. The new subframe is not created by script or
  // 2. The new subframe is created by script, but we are still asked for the
  //    old, stable part for web tests (via
  //    |g_preserve_stable_unique_name_for_testing|).
  if (!is_created_by_script || g_preserve_stable_unique_name_for_testing) {
    PendingChildFrameAdapter adapter(frame_);
    unique_name_of_new_child = CalculateNewName(&adapter, name);
  }

  // The random part of unique name is only included for subframes created from
  // scripts.
  if (is_created_by_script) {
    unique_name_of_new_child += kDynamicFrameMarker;
    unique_name_of_new_child += base::UnguessableToken::Create().ToString();
    unique_name_of_new_child += "-->";
  }

  return unique_name_of_new_child;
}

void UniqueNameHelper::UpdateName(const std::string& name) {
  // Don't update the unique name if it should remain frozen.
  if (frozen_)
    return;

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

// |replacements| is used for two purposes:
// - when processing a non-frame path unique name that exceeds the max size,
//   this collection records the original name and the hashed name.
// - when processing a frame path unique name, this collection is used to fix up
//   ancestor frames in the frame path with an updated unique name.
//
std::string UniqueNameHelper::UpdateLegacyNameFromV24(
    std::string legacy_name,
    std::vector<Replacement>* replacements) {
  if (IsNameWithFramePath(legacy_name)) {
    // Frame paths can embed ancestor's unique names. Since the contract of this
    // function is that names must be updated beginning from the root of the
    // tree and go down from there, it is impossible for a frame path to contain
    // a unique name (which needs a replacement) that has not already been seen
    // and inserted into |replacements|.
    for (const auto& replacement : *replacements) {
      // Note: this find() call should only start searching from immediately
      // after the most recent replacement, to guarantee each section of the
      // name is only replaced once. But it was accidentally omitted from the
      // initial version of the migration code.
      size_t next_index = legacy_name.find(replacement.old_name);
      if (next_index == std::string::npos)
        continue;
      legacy_name.replace(next_index, replacement.old_name.size(),
                          replacement.new_name);
    }
    return legacy_name;
  }

  if (legacy_name.size() > kMaxRequestedNameSize) {
    std::string hashed_name = CalculateFrameHash(legacy_name);
    // Suppose 'aaa' and 'caaab' are unique names in the same tree. A
    // hypothetical frame path might look like:
    //   <!--framePath //aaa/caaab/<!--frame0-->-->
    //
    // In this case, it's important to avoid matching 'aaa' against the
    // substring in 'caaab'. To try to avoid this, the search and the
    // replacement strings are wrapped in '/' to try to match the path delimiter
    // in generated frame paths.
    //
    // However, nothing prevents a browsing context name from containing a
    // literal '/', which could lead to an ambiguous parse. Consider the case
    // where 'aaa', 'bbb', and 'aaa/bbb' are unique names in the same tree. The
    // following frame path is ambiguous:
    //   <!--framePath //aaa/bbb/<!--frame0-->-->
    //
    // While it's possible to use the depth of the frame tree as a hint for
    // disambiguating this, the number of ways to split up the frame path
    // quickly becomes quite large. This code takes the simple approach and
    // simply aims to implement a best effort update, accepting that there may
    // be some names that are updated incorrectly.
    std::string original_string = "/";
    original_string += legacy_name;
    original_string += "/";
    std::string new_string = "/";
    new_string += hashed_name;
    new_string += "/";
    replacements->emplace_back(std::move(original_string),
                               std::move(new_string));
    return hashed_name;
  }

  return legacy_name;
}

std::string UniqueNameHelper::CalculateLegacyNameForTesting(
    const FrameAdapter* frame,
    const std::string& name) {
  return CalculateNameInternal(frame, name);
}

// static
void UniqueNameHelper::PreserveStableUniqueNameForTesting() {
  g_preserve_stable_unique_name_for_testing = true;
}

std::string UniqueNameHelper::ExtractStableNameForTesting(
    std::string_view unique_name) {
  size_t i = unique_name.rfind(kDynamicFrameMarker);
  if (i == std::string::npos)
    return std::string(unique_name);
  return std::string(unique_name.substr(0, i));
}

}  // namespace blink