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

// NB: Modelled after Mozilla's code (originally written by Pamela Greene,
// later modified by others), but almost entirely rewritten for Chrome.
//   (netwerk/dns/src/nsEffectiveTLDService.cpp)
/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Mozilla Effective-TLD Service
 *
 * The Initial Developer of the Original Code is
 * Google Inc.
 * Portions created by the Initial Developer are Copyright (C) 2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Pamela Greene <pamg.bugs@gmail.com> (original author)
 *   Daniel Witte <dwitte@stanford.edu>
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

#include "net/base/registry_controlled_domains/registry_controlled_domain.h"

#include <cstdint>
#include <optional>
#include <ostream>
#include <string_view>

#include "base/check_op.h"
#include "base/containers/span.h"
#include "base/metrics/histogram_macros.h"
#include "base/no_destructor.h"
#include "base/notreached.h"
#include "base/numerics/safe_conversions.h"
#include "base/rand_util.h"
#include "base/strings/string_util.h"
#include "base/strings/utf_string_conversions.h"
#include "base/synchronization/lock.h"
#include "base/types/expected_macros.h"
#include "base/types/is_instantiation.h"
#include "net/base/lookup_string_in_fixed_set.h"
#include "net/base/registry_controlled_domain_constants.h"
#include "net/base/registry_controlled_domains/effective_tld_names-reversed-inc.cc"
#include "net/base/url_util.h"
#include "url/gurl.h"
#include "url/origin.h"
#include "url/third_party/mozilla/url_parse.h"
#include "url/url_util.h"

namespace net::registry_controlled_domains {

namespace {

// See make_dafsa.py for documentation of the generated dafsa byte array.
// This is mutable so that it can be overridden for testing.
base::span<const uint8_t> g_graph = kDafsa;

struct MappedHostComponent {
  size_t original_begin;
  size_t original_end;

  size_t canonical_begin;
  size_t canonical_end;

  // True if this component could be canonicalized.
  bool is_canonical;
};

// A thread-safe cache of the last `kMaxCacheSize` registry lookups. Implemented
// with a circular array but could just as easily be a base::LRUCache if you
// want LRU, with the additional overhead of the doubly-linked list pointers and
// seemingly negligible hit rate win. See crbug.com/383728878 for more
// information.
class RegistryLookupCache {
 public:
  constexpr static uint8_t kMaxCacheSize = 5;
  RegistryLookupCache() = default;
  ~RegistryLookupCache() = default;
  RegistryLookupCache(const RegistryLookupCache&) = delete;
  RegistryLookupCache& operator=(const RegistryLookupCache&) = delete;

  // The returned string_view is a reference to the incoming `host` and
  // therefore has the same lifetime.
  std::optional<std::string_view> Get(std::string_view host,
                                      PrivateRegistryFilter private_filter) {
    std::optional<std::string_view> result;

    {
      base::AutoLock scoped_lock(lock_);
      for (const CachedRegistryLookup& cached_result : cache_) {
        if (cached_result.host == host &&
            cached_result.private_filter == private_filter) {
          result = host.substr(cached_result.offset);
          break;
        }
      }
    }

    // This method is called frequently, so we only record a small fraction of
    // the results to avoid excessive overhead.
    if (base::ShouldRecordSubsampledMetric(0.00001)) {
      UMA_HISTOGRAM_BOOLEAN(
          "Net.RegistryControlledDomains.GetDomainAndRegistry.CacheHit.Sampled",
          result.has_value());
    }
    return result;
  }

  // Stores the input and output of a registry lookup. Rather than make a copy
  // of the output string, it stores the offset into the host string.
  void Set(std::string_view host,
           PrivateRegistryFilter private_filter,
           size_t offset) {
    base::AutoLock scoped_lock(lock_);
    DCHECK_GT(kMaxCacheSize, write_index_);
    cache_[write_index_] = CachedRegistryLookup(host, private_filter, offset);
    write_index_ = (write_index_ + 1) % kMaxCacheSize;
  }

 private:
  // Stores the input parameters and the output offset of a registry lookup.
  struct CachedRegistryLookup {
   public:
    CachedRegistryLookup() = default;
    CachedRegistryLookup(std::string_view host,
                         PrivateRegistryFilter private_filter,
                         size_t offset)
        : host(host),
          private_filter(private_filter),
          offset(base::checked_cast<uint32_t>(offset)) {}
    ~CachedRegistryLookup() = default;

    std::string host;
    PrivateRegistryFilter private_filter;
    uint32_t offset;
  };

  base::Lock lock_;
  std::array<CachedRegistryLookup, kMaxCacheSize> cache_ GUARDED_BY(lock_) = {};
  uint8_t write_index_ GUARDED_BY(lock_) = 0u;
};

// Used as the output of functions that calculate the registry in a hostname.
// `registry` is the substring of the host containing the registry identifier
// (or empty if none is found or the hostname is itself a registry identifier).
// `is_registry_identifier` is true if the host is itself a match for a registry
// identifier.
struct RegistryResult {
  std::string_view registry;
  bool is_registry_identifier = false;
};

// This version assumes we already removed leading dots from host as well as the
// last trailing dot if it had one. If the host is itself a registry identifier,
// the returned `registry` will be empty and `is_registry_identifier` will be
// true.
RegistryResult GetRegistryInTrimmedHost(std::string_view host,
                                        UnknownRegistryFilter unknown_filter,
                                        PrivateRegistryFilter private_filter) {
  const std::optional<SuffixMatch> match = LookupSuffixInReversedSet(
      g_graph, private_filter == INCLUDE_PRIVATE_REGISTRIES, host);

  // No rule found in the registry.
  if (!match.has_value()) {
    // If we allow unknown registries, return the last subcomponent.
    if (unknown_filter == INCLUDE_UNKNOWN_REGISTRIES) {
      const size_t last_dot = host.find_last_of('.');
      if (last_dot != std::string_view::npos) {
        return {host.substr(last_dot + 1), false};
      }
    }
    return {"", false};
  }

  const size_t length = match->suffix.size();
  CHECK_LE(length, host.size());

  // Exception rules override wildcard rules when the domain is an exact
  // match, but wildcards take precedence when there's a subdomain.
  if (match->tags.Has(DomainRuleTag::kWildcard)) {
    // If the complete host matches, then the host is the wildcard suffix, so
    // return an empty registry and mark as registry identifier.
    if (length == host.size()) {
      return {"", true};
    }

    CHECK_LE(length + 2, host.size());
    CHECK_EQ('.', host[host.size() - length - 1]);

    const size_t preceding_dot =
        host.find_last_of('.', host.size() - length - 2);

    // If no preceding dot, then the host is the registry itself, so return
    // an empty registry and mark as registry identifier.
    if (preceding_dot == std::string_view::npos) {
      return {"", true};
    }

    // Return suffix plus the wildcard subdomain label.
    return {host.substr(preceding_dot + 1), false};
  }

  if (match->tags.Has(DomainRuleTag::kException)) {
    const size_t first_dot = match->suffix.find('.');
    // If there is no first dot, we had an exception rule with no dots (e.g.
    // "!foo").  This would only be valid if we had a corresponding wildcard
    // rule, which would have to be "*".  But we explicitly disallow that case,
    // so this kind of rule is invalid.
    // TODO(crbug.com/40406311): This assumes that all wildcard entries,
    // such as *.foo.invalid, also have their parent, foo.invalid, as an entry
    // on the PSL, which is why it returns the length of foo.invalid. This
    // isn't entirely correct.
    CHECK_NE(first_dot, std::string_view::npos)
        << "Invalid exception rule. Suffix: '" << match->suffix << "'";
    return {match->suffix.substr(first_dot + 1), false};
  }

  // If a complete match, then the host is the registry itself, so return an
  // empty registry and mark as registry identifier.
  if (length == host.size()) {
    return {"", true};
  }

  return {match->suffix, false};
}

std::optional<RegistryResult> GetRegistryImpl(
    std::string_view host,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
  if (host.empty()) {
    return std::nullopt;
  }

  std::string_view trimmed_host = host;
  // Skip leading dots.
  if (const size_t host_check_begin = trimmed_host.find_first_not_of('.');
      host_check_begin != std::string_view::npos) {
    trimmed_host.remove_prefix(host_check_begin);
  } else {
    return RegistryResult{"", false};  // Host is only dots.
  }

  // A single trailing dot isn't relevant in this determination, but does need
  // to be included in the final returned registry.
  if (trimmed_host.back() == '.') {
    trimmed_host.remove_suffix(1);
  }

  RegistryResult output =
      GetRegistryInTrimmedHost(trimmed_host, unknown_filter, private_filter);

  if (output.registry.empty()) {
    return output;
  }

  // Include the trailing dot, if there was one.
  output.registry = host.substr(output.registry.data() - host.data());
  return output;
}

// DO NOT change the interface of this function without also updating the
// RegistryLookupCache.
std::string_view GetDomainAndRegistryImpl(
    std::string_view host,
    PrivateRegistryFilter private_filter) {
  CHECK(!host.empty());

  // Because this function is called frequently, and is quite expensive, we
  // 'memoize' previous instantiations of this function by using a cache. Since
  // this method can be called on dozens of sequences and threads, we make it
  // thread-safe.
  static base::NoDestructor<RegistryLookupCache> cache;

  // Check for the origin in the cache.
  std::optional<std::string_view> cached_result =
      cache->Get(host, private_filter);
  if (cached_result.has_value()) {
    return *cached_result;
  }

  // Find the registry for this host.
  const size_t registry_length =
      GetRegistryImpl(host, INCLUDE_UNKNOWN_REGISTRIES, private_filter)
          // Safe because the host is non-empty.
          .value()
          .registry.size();
  if (registry_length == 0) {
    return std::string_view();  // No registry.
  }
  // The "2" in this next line is 1 for the dot, plus a 1-char minimum preceding
  // subcomponent length.
  CHECK_GE(host.length(), 2u);
  CHECK_LE(registry_length, host.length() - 2)
      << "Host does not have at least one subcomponent before registry!";

  // Move past the dot preceding the registry, and search for the next previous
  // dot.  Return the host from after that dot, or the whole host when there is
  // no dot.
  const size_t dot = host.rfind('.', host.length() - registry_length - 2);
  if (dot == std::string::npos) {
    cache->Set(host, private_filter, 0u);
    return host;
  }

  std::string_view result = host.substr(dot + 1);
  cache->Set(host, private_filter, dot + 1);

  return result;
}

// Same as GetDomainAndRegistry, but returns the domain and registry as a
// std::string_view that references the underlying string of the passed-in
// |gurl|.
// TODO(pkalinnikov): Eliminate this helper by exposing std::string_view as the
// interface type for all the APIs.
std::string_view GetDomainAndRegistryAsStringPiece(
    std::string_view host,
    PrivateRegistryFilter filter) {
  if (host.empty() || url::HostIsIPAddress(host)) {
    return std::string_view();
  }
  return GetDomainAndRegistryImpl(host, filter);
}

// These two functions append the given string as-is to the given output,
// converting to UTF-8 if necessary.
void AppendInvalidString(std::string_view str, url::CanonOutput* output) {
  output->Append(str);
}
void AppendInvalidString(std::u16string_view str, url::CanonOutput* output) {
  output->Append(base::UTF16ToUTF8(str));
}

// Backend for PermissiveGetHostRegistry that handles both UTF-8 and UTF-16
// input.
template <typename T>
  requires base::is_instantiation<T, std::basic_string_view>
std::optional<T> DoPermissiveGetHostRegistry(
    T host,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
  std::string canonical_host;  // Do not modify outside of canon_output.
  canonical_host.reserve(host.length());
  url::StdStringCanonOutput canon_output(&canonical_host);

  std::vector<MappedHostComponent> components;

  for (size_t current = 0; current < host.length(); current++) {
    size_t begin = current;

    // Advance to next "." or end.
    current = host.find('.', begin);
    if (current == std::string::npos) {
      current = host.length();
    }

    MappedHostComponent mapping;
    mapping.original_begin = begin;
    mapping.original_end = current;
    mapping.canonical_begin = canon_output.length();
    mapping.is_canonical = true;

    // Try to append the canonicalized version of this component.
    T host_view = host.substr(begin, current - begin);
    if (!url::CanonicalizeHostSubstring(host_view, &canon_output)) {
      // Failed to canonicalize this component; append as-is.
      AppendInvalidString(host_view, &canon_output);
      mapping.is_canonical = false;
    }

    mapping.canonical_end = canon_output.length();
    components.push_back(mapping);

    if (current < host.length()) {
      canon_output.push_back('.');
    }
  }
  canon_output.Complete();

  ASSIGN_OR_RETURN(
      const std::string_view canonical_rcd,
      GetRegistryImpl(canonical_host, unknown_filter, private_filter)
          .transform(
              [](const RegistryResult& result) { return result.registry; }));
  if (canonical_rcd.empty()) {
    // No registry controlled domain.
    return T{};
  }

  // Find which host component the result started in.
  const size_t canonical_rcd_begin =
      canonical_host.length() - canonical_rcd.length();

  for (const auto& mapping : components) {
    // In the common case, GetRegistryImpl will identify the beginning
    // of a component and we can just return where that component was in the
    // original string.
    if (canonical_rcd_begin == mapping.canonical_begin) {
      return host.substr(mapping.original_begin);
    }

    if (canonical_rcd_begin >= mapping.canonical_end) {
      continue;
    }

    // Skip brute-force search if the component cannot be canonicalized.
    // In practice, we should only get here if mapping is the last item in
    // components. If the mapping cannot be canonicalized, RCD can only
    // fall into the middle of it if the mapping is the last in components,
    // such as "%EF%2E%FF%FE.er". In contrast, a hostname like
    // "%EF%2E%FF%FE.test.er" will hit one of the two canonical_rcd_begin checks
    // above because its RCD is "test.er" and the RCD doesn't fall in the middle
    // of a component.
    if (!mapping.is_canonical) {
      continue;
    }

    // The registry controlled domain begin was identified as being in the
    // middle of this dot-separated domain component in the non-canonical
    // input. This indicates some form of escaped dot, or a non-ASCII
    // character that was canonicalized to a dot.
    //
    // Brute-force search from the end by repeatedly canonicalizing longer
    // substrings until we get a match for the canonicalized version. This
    // can't be done with binary search because canonicalization might increase
    // or decrease the length of the produced string depending on where it's
    // split. This depends on the canonicalization process not changing the
    // order of the characters. Punycode can change the order of characters,
    // but it doesn't work across dots so this is safe.


    for (int current_try = static_cast<int>(mapping.original_end) - 1;
         current_try >= static_cast<int>(mapping.original_begin);
         current_try--) {
      std::string try_string;
      url::StdStringCanonOutput try_output(&try_string);

      if (!url::CanonicalizeHostSubstring(
              host.substr(current_try, mapping.original_end - current_try),
              &try_output)) {
        continue;  // Invalid substring, skip.
      }

      try_output.Complete();
      if (try_string == canonical_rcd) {
        return host.substr(current_try);
      }
    }
  }

  // We may get here if the host has components that can't be canonicalized.
  // This should only happen in fuzzing and tests, as invalid hostnames will get
  // blocked much earlier in the stack.
  return T{};
}

bool SameDomainOrHost(std::string_view host1,
                      std::string_view host2,
                      PrivateRegistryFilter filter) {
  // Quickly reject cases where either host is empty.
  if (host1.empty() || host2.empty()) {
    return false;
  }

  // Check for exact host matches, which is faster than looking up the domain
  // and registry.
  if (host1 == host2) {
    return true;
  }

  // Check for a domain and registry match.
  std::string_view domain1 = GetDomainAndRegistryAsStringPiece(host1, filter);
  return !domain1.empty() &&
         (domain1 == GetDomainAndRegistryAsStringPiece(host2, filter));
}

}  // namespace

std::string GetDomainAndRegistry(const GURL& gurl,
                                 PrivateRegistryFilter filter) {
  return std::string(GetDomainAndRegistryAsStringPiece(gurl.host(), filter));
}

std::string GetDomainAndRegistry(const url::Origin& origin,
                                 PrivateRegistryFilter filter) {
  return std::string(GetDomainAndRegistryAsStringPiece(origin.host(), filter));
}

std::string GetDomainAndRegistry(std::string_view host,
                                 PrivateRegistryFilter filter) {
  url::CanonHostInfo host_info;
  const std::string canon_host(CanonicalizeHost(host, &host_info));
  if (canon_host.empty() || host_info.IsIPAddress()) {
    return std::string();
  }
  return std::string(GetDomainAndRegistryImpl(canon_host, filter));
}

std::string_view GetDomainAndRegistryAsStringPiece(
    const url::Origin& origin,
    PrivateRegistryFilter filter) {
  return GetDomainAndRegistryAsStringPiece(origin.host(), filter);
}

bool SameDomainOrHost(const GURL& gurl1,
                      const GURL& gurl2,
                      PrivateRegistryFilter filter) {
  return SameDomainOrHost(gurl1.host(), gurl2.host(), filter);
}

bool SameDomainOrHost(const url::Origin& origin1,
                      const url::Origin& origin2,
                      PrivateRegistryFilter filter) {
  return SameDomainOrHost(origin1.host(), origin2.host(), filter);
}

bool SameDomainOrHost(const GURL& gurl,
                      const url::Origin& origin,
                      PrivateRegistryFilter filter) {
  return SameDomainOrHost(gurl.host(), origin.host(), filter);
}

std::optional<std::string_view> GetRegistry(
    const GURL& gurl,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
  std::string_view host = gurl.host();
  ASSIGN_OR_RETURN(RegistryResult result,
                   GetRegistryImpl(host, unknown_filter, private_filter));
  return result.registry;
}

bool HostHasRegistryControlledDomain(std::string_view host,
                                     UnknownRegistryFilter unknown_filter,
                                     PrivateRegistryFilter private_filter) {
  url::CanonHostInfo host_info;
  const std::string canon_host(CanonicalizeHost(host, &host_info));

  std::optional<std::string_view> rcd;
  switch (host_info.family) {
    case url::CanonHostInfo::IPV4:
    case url::CanonHostInfo::IPV6:
      // IP addresses don't have R.C.D.'s.
      return false;
    case url::CanonHostInfo::BROKEN:
      // Host is not canonicalizable. Fall back to the slower "permissive"
      // version.
      rcd = PermissiveGetHostRegistry(host, unknown_filter, private_filter);
      break;
    case url::CanonHostInfo::NEUTRAL:
      rcd = GetRegistryImpl(canon_host, unknown_filter, private_filter)
                .transform([](const RegistryResult& result) {
                  return result.registry;
                });
      break;
    default:
      NOTREACHED();
  }
  return rcd.has_value() && !rcd->empty();
}

bool HostIsRegistryIdentifier(std::string_view canon_host,
                              PrivateRegistryFilter private_filter) {
  // The input is expected to be a valid, canonicalized hostname (not an IP
  // address).
  CHECK(!canon_host.empty());
  url::CanonHostInfo host_info;
  std::string canonicalized = CanonicalizeHost(canon_host, &host_info);
  CHECK_EQ(canonicalized, canon_host);
  CHECK_EQ(host_info.family, url::CanonHostInfo::NEUTRAL);
  return GetRegistryImpl(canon_host, EXCLUDE_UNKNOWN_REGISTRIES, private_filter)
      // Safe because `canon_host` is non-empty.
      .value()
      .is_registry_identifier;
}

std::optional<std::string_view> GetCanonicalHostRegistry(
    std::string_view canon_host,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
#ifndef NDEBUG
  // Ensure passed-in host name is canonical.
  url::CanonHostInfo host_info;
  DCHECK_EQ(net::CanonicalizeHost(canon_host, &host_info), canon_host);
#endif

  ASSIGN_OR_RETURN(RegistryResult result,
                   GetRegistryImpl(canon_host, unknown_filter, private_filter));
  return result.registry;
}

std::optional<std::string_view> PermissiveGetHostRegistry(
    std::string_view host,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
  return DoPermissiveGetHostRegistry(host, unknown_filter, private_filter);
}

std::optional<std::u16string_view> PermissiveGetHostRegistry(
    std::u16string_view host,
    UnknownRegistryFilter unknown_filter,
    PrivateRegistryFilter private_filter) {
  return DoPermissiveGetHostRegistry(host, unknown_filter, private_filter);
}

void ResetFindDomainGraphForTesting() {
  g_graph = kDafsa;
}

void SetFindDomainGraphForTesting(base::span<const uint8_t> domains) {
  CHECK(!domains.empty());
  g_graph = domains;
}

}  // namespace net::registry_controlled_domains