components/password_manager/core/browser/ui/passwords_grouper.cc

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

#include "components/password_manager/core/browser/ui/passwords_grouper.h"

#include "base/check_op.h"
#include "base/containers/cxx20_erase.h"
#include "base/containers/flat_set.h"
#include "base/strings/escape.h"
#include "base/strings/string_util.h"
#include "components/password_manager/core/browser/affiliation/affiliation_service.h"
#include "components/password_manager/core/browser/affiliation/affiliation_utils.h"
#include "components/password_manager/core/browser/passkey_credential.h"
#include "components/password_manager/core/browser/password_form.h"
#include "components/password_manager/core/browser/password_list_sorter.h"
#include "components/password_manager/core/browser/password_manager_util.h"
#include "components/password_manager/core/browser/password_ui_utils.h"
#include "components/password_manager/core/browser/ui/credential_ui_entry.h"
#include "components/url_formatter/elide_url.h"

namespace password_manager {

namespace {

constexpr char kDefaultFallbackIconUrl[] = "https://t1.gstatic.com/faviconV2";
constexpr char kFallbackIconQueryParams[] =
    "client=PASSWORD_MANAGER&type=FAVICON&fallback_opts=TYPE,SIZE,URL&size=32&"
    "url=";
constexpr char kDefaultAndroidIcon[] =
    "https://www.gstatic.com/images/branding/product/1x/play_apps_32dp.png";

// Converts signon_realm (url for federated forms) into GURL and strips path. If
// form is valid Android credential or conversion fails signon_realm is returned
// as it is.
std::string GetFacetRepresentation(const PasswordForm& form) {
  FacetURI facet = FacetURI::FromPotentiallyInvalidSpec(form.signon_realm);
  // Return result for android credentials immediately.
  if (facet.IsValidAndroidFacetURI()) {
    return facet.potentially_invalid_spec();
  }
  GURL url;
  // For federated credentials use url. For everything else try to parse signon
  // realm as GURL.
  if (form.IsFederatedCredential()) {
    url = form.url;
  } else {
    url = GURL(form.signon_realm);
  }

  // Strip path and everything after that.
  std::string scheme_and_authority = url.GetWithEmptyPath().spec();

  // If something went wrong (signon_realm is not a valid GURL), use signon
  // realm as it is.
  if (scheme_and_authority.empty()) {
    scheme_and_authority = form.signon_realm;
  }
  return FacetURI::FromPotentiallyInvalidSpec(scheme_and_authority)
      .potentially_invalid_spec();
}

std::string GetFacetRepresentation(const PasskeyCredential& passkey) {
  std::string as_url = RPIDToURL(passkey.rp_id()).possibly_invalid_spec();
  return FacetURI::FromPotentiallyInvalidSpec(as_url)
      .potentially_invalid_spec();
}

// An implementation of the disjoint-set data structure
// (https://en.wikipedia.org/wiki/Disjoint-set_data_structure). This
// implementation uses the path compression and union by rank optimizations,
// achieving near-constant runtime on all operations.
//
// This data structure allows to keep track of disjoin sets. Constructor accepts
// number of elements and initially each element represent an individual set.
// Later by calling MergeSets corresponding sets are merged together.
// Example usage:
//   DisjointSet disjoint_set(5);
//   disjoint_set.GetDisjointSets(); // Returns {{0}, {1}, {2}, {3}, {4}}
//   disjoint_set.MergeSets(0, 2);
//   disjoint_set.GetDisjointSets(); // Returns {{0, 2}, {1}, {3}, {4}}
//   disjoint_set.MergeSets(2, 4);
//   disjoint_set.GetDisjointSets(); // Returns {{0, 2, 4}, {1}, {3}}
class DisjointSet {
 public:
  explicit DisjointSet(size_t size) : parent_id_(size), ranks_(size, 0) {
    for (size_t i = 0; i < size; i++) {
      parent_id_[i] = i;
    }
  }

  // Merges two sets based on their rank. Set with higher rank becomes a parent
  // for another set.
  void MergeSets(int set1, int set2) {
    set1 = GetRoot(set1);
    set2 = GetRoot(set2);
    if (set1 == set2) {
      return;
    }

    // Update parent based on rank.
    if (ranks_[set1] > ranks_[set2]) {
      parent_id_[set2] = set1;
    } else {
      parent_id_[set1] = set2;
      // if ranks were equal increment by one new root's rank.
      if (ranks_[set1] == ranks_[set2]) {
        ranks_[set2]++;
      }
    }
  }

  // Returns disjoin sets after merging. It's guarantee that the result will
  // hold all elements.
  std::vector<std::vector<int>> GetDisjointSets() {
    std::vector<std::vector<int>> disjoint_sets(parent_id_.size());
    for (size_t i = 0; i < parent_id_.size(); i++) {
      // Append all elements to the root.
      int root = GetRoot(i);
      disjoint_sets[root].push_back(i);
    }
    // Clear empty sets.
    base::EraseIf(disjoint_sets, [](const auto& set) { return set.empty(); });
    return disjoint_sets;
  }

 private:
  // Returns root for a given element.
  int GetRoot(int index) {
    if (index == parent_id_[index]) {
      return index;
    }
    // To speed up future lookups flatten the tree along the way.
    return parent_id_[index] = GetRoot(parent_id_[index]);
  }

  // Vector where element at i'th position holds a parent for i.
  std::vector<int> parent_id_;

  // Upper bound depth of a tree for i'th element.
  std::vector<size_t> ranks_;
};

// This functions merges groups together if:
// * the same facet is present in both groups
// * main domain of the facets matches
std::vector<GroupedFacets> MergeRelatedGroups(
    const base::flat_set<std::string>& psl_extensions,
    const std::vector<GroupedFacets>& groups) {
  DisjointSet unions(groups.size());
  std::map<std::string, int> main_domain_to_group;

  for (size_t i = 0; i < groups.size(); i++) {
    for (auto& facet : groups[i].facets) {
      if (facet.uri.IsValidAndroidFacetURI()) {
        continue;
      }

      // If domain is empty - compute it manually.
      std::string main_domain =
          facet.main_domain.empty()
              ? password_manager_util::GetExtendedTopLevelDomain(
                    GURL(facet.uri.potentially_invalid_spec()), psl_extensions)
              : facet.main_domain;

      if (main_domain.empty()) {
        continue;
      }

      auto it = main_domain_to_group.find(main_domain);
      if (it == main_domain_to_group.end()) {
        main_domain_to_group[main_domain] = i;
        continue;
      }
      unions.MergeSets(i, it->second);
    }
  }

  std::vector<GroupedFacets> result;
  for (const auto& merged_groups : unions.GetDisjointSets()) {
    GroupedFacets group;
    for (int group_id : merged_groups) {
      // Move all the elements into a new vector.
      group.facets.insert(group.facets.end(), groups[group_id].facets.begin(),
                          groups[group_id].facets.end());
      // Use non-empty name for a combined group.
      if (!groups[group_id].branding_info.icon_url.is_empty()) {
        group.branding_info = groups[group_id].branding_info;
      }
    }

    result.push_back(std::move(group));
  }
  return result;
}

FacetBrandingInfo CreateBrandingInfoFromFacetURI(
    const CredentialUIEntry& credential,
    const base::flat_set<std::string>& psl_extensions) {
  FacetBrandingInfo branding_info;
  FacetURI facet_uri =
      FacetURI::FromPotentiallyInvalidSpec(credential.GetFirstSignonRealm());
  if (facet_uri.IsValidAndroidFacetURI()) {
    branding_info.name = SplitByDotAndReverse(facet_uri.android_package_name());
    branding_info.icon_url = GURL(kDefaultAndroidIcon);
    return branding_info;
  }
  std::string group_name = password_manager_util::GetExtendedTopLevelDomain(
      credential.GetURL(), psl_extensions);
  if (group_name.empty()) {
    group_name =
        credential.GetURL().is_valid()
            ? base::UTF16ToUTF8(url_formatter::FormatUrlForSecurityDisplay(
                  credential.GetURL()))
            : facet_uri.potentially_invalid_spec();
  }
  branding_info.name = group_name;

  GURL::Replacements replacements;
  std::string query = kFallbackIconQueryParams +
                      base::EscapeQueryParamValue(credential.GetURL().spec(),
                                                  /*use_plus=*/false);
  replacements.SetQueryStr(query);
  branding_info.icon_url =
      GURL(kDefaultFallbackIconUrl).ReplaceComponents(replacements);
  return branding_info;
}

}  // namespace

PasswordsGrouper::Credentials::Credentials() = default;
PasswordsGrouper::Credentials::~Credentials() = default;

PasswordsGrouper::PasswordsGrouper(AffiliationService* affiliation_service)
    : affiliation_service_(affiliation_service) {
  DCHECK(affiliation_service_);
  affiliation_service_->GetPSLExtensions(
      base::BindOnce(&PasswordsGrouper::InitializePSLExtensionList,
                     weak_ptr_factory_.GetWeakPtr()));
}
PasswordsGrouper::~PasswordsGrouper() = default;

void PasswordsGrouper::GroupCredentials(std::vector<PasswordForm> forms,
                                        std::vector<PasskeyCredential> passkeys,
                                        base::OnceClosure callback) {
  // Convert forms to Facets.
  std::vector<FacetURI> facets;
  facets.reserve(forms.size());
  for (const auto& form : forms) {
    // Blocked forms aren't grouped.
    if (!form.blocked_by_user) {
      facets.emplace_back(
          FacetURI::FromPotentiallyInvalidSpec(GetFacetRepresentation(form)));
    }
  }

  // Convert passkey relying party IDs to Facets.
  for (const auto& passkey : passkeys) {
    facets.emplace_back(
        FacetURI::FromPotentiallyInvalidSpec(GetFacetRepresentation(passkey)));
  }

  AffiliationService::GroupsCallback group_callback = base::BindOnce(
      &PasswordsGrouper::GroupPasswordsImpl, weak_ptr_factory_.GetWeakPtr(),
      std::move(forms), std::move(passkeys));

  // Before grouping passwords merge related groups. After grouping is finished
  // invoke |callback|.
  affiliation_service_->GetGroupingInfo(
      std::move(facets), base::BindOnce(&MergeRelatedGroups, psl_extensions_)
                             .Then(std::move(group_callback))
                             .Then(std::move(callback)));
}

std::vector<AffiliatedGroup>
PasswordsGrouper::GetAffiliatedGroupsWithGroupingInfo() const {
  std::vector<AffiliatedGroup> affiliated_groups;
  for (auto const& [group_id, affiliated_group] :
       map_group_id_to_credentials_) {
    // Convert each credential into CredentialUIEntry.
    std::vector<CredentialUIEntry> credentials;
    for (auto const& [username_password_key, forms] : affiliated_group.forms) {
      credentials.emplace_back(forms);
    }
    for (auto const& passkey : affiliated_group.passkeys) {
      credentials.emplace_back(passkey);
    }

    // Add branding information to the affiliated group.
    FacetBrandingInfo brandingInfo;
    auto branding_iterator = map_group_id_to_branding_info_.find(group_id);
    if (branding_iterator != map_group_id_to_branding_info_.end()) {
      brandingInfo = branding_iterator->second;
    }
    // If the branding information is missing, create a default one with the
    // sign-on realm.
    if (brandingInfo.name.empty()) {
      brandingInfo =
          CreateBrandingInfoFromFacetURI(credentials[0], psl_extensions_);
    }
    affiliated_groups.emplace_back(std::move(credentials), brandingInfo);
  }
  // Sort affiliated groups.
  std::sort(affiliated_groups.begin(), affiliated_groups.end(),
            [](AffiliatedGroup& lhs, AffiliatedGroup& rhs) {
              base::StringPiece lhs_name(lhs.GetDisplayName()),
                  rhs_name(rhs.GetDisplayName());
              size_t separator_length =
                  base::StringPiece(url::kStandardSchemeSeparator).size();

              size_t position = lhs_name.find(url::kStandardSchemeSeparator);
              if (position != std::string::npos) {
                lhs_name = lhs_name.substr(position + separator_length);
              }

              position = rhs_name.find(url::kStandardSchemeSeparator);
              if (position != std::string::npos) {
                rhs_name = rhs_name.substr(position + separator_length);
              }

              // Compare names omitting scheme.
              return base::CompareCaseInsensitiveASCII(lhs_name, rhs_name) < 0;
            });
  return affiliated_groups;
}

std::vector<CredentialUIEntry> PasswordsGrouper::GetAllCredentials() const {
  std::vector<CredentialUIEntry> credentials;
  for (const auto& [group_id, affiliated_credentials] :
       map_group_id_to_credentials_) {
    for (const auto& [username_password_key, forms] :
         affiliated_credentials.forms) {
      credentials.emplace_back(forms);
    }
    for (const auto& passkey : affiliated_credentials.passkeys) {
      credentials.emplace_back(passkey);
    }
  }
  return credentials;
}

std::vector<CredentialUIEntry> PasswordsGrouper::GetBlockedSites() const {
  std::vector<CredentialUIEntry> results;
  results.reserve(blocked_sites_.size());
  base::ranges::transform(blocked_sites_, std::back_inserter(results),
                          [](const PasswordForm& password_form) {
                            return CredentialUIEntry(password_form);
                          });
  // Sort blocked sites.
  std::sort(results.begin(), results.end());
  return results;
}

std::vector<PasswordForm> PasswordsGrouper::GetPasswordFormsFor(
    const CredentialUIEntry& credential) const {
  std::vector<PasswordForm> forms;

  // Verify if the credential is in blocked sites first.
  if (credential.blocked_by_user) {
    for (const auto& blocked_site : blocked_sites_) {
      if (credential.GetFirstSignonRealm() == blocked_site.signon_realm) {
        forms.push_back(blocked_site);
      }
    }
    return forms;
  }

  // Get group id based on signon_realm.
  auto group_id_iterator = map_signon_realm_to_group_id_.find(
      SignonRealm(credential.GetFirstSignonRealm()));
  if (group_id_iterator == map_signon_realm_to_group_id_.end()) {
    return {};
  }

  // Get all username/password pairs related to this group.
  GroupId group_id = group_id_iterator->second;
  auto group_iterator = map_group_id_to_credentials_.find(group_id);
  if (group_iterator == map_group_id_to_credentials_.end()) {
    return {};
  }

  // Get all password forms with matching username/password.
  const std::map<UsernamePasswordKey, std::vector<PasswordForm>>&
      username_to_forms = group_iterator->second.forms;
  auto forms_iterator = username_to_forms.find(
      UsernamePasswordKey(CreateUsernamePasswordSortKey(credential)));
  if (forms_iterator == username_to_forms.end()) {
    return {};
  }

  return forms_iterator->second;
}

void PasswordsGrouper::ClearCache() {
  map_signon_realm_to_group_id_.clear();
  map_group_id_to_branding_info_.clear();
  map_group_id_to_credentials_.clear();
  blocked_sites_.clear();
}

void PasswordsGrouper::GroupPasswordsImpl(
    std::vector<PasswordForm> forms,
    std::vector<PasskeyCredential> passkeys,
    const std::vector<GroupedFacets>& groups) {
  ClearCache();
  // Construct map to keep track of facet URI to group id mapping.
  std::map<std::string, GroupId> map_facet_to_group_id =
      MapFacetsToGroupId(groups);

  // Construct a map to keep track of group id to a map of credential groups
  // to password form.
  for (auto& form : forms) {
    // Do not group blocked by user password forms.
    if (form.blocked_by_user) {
      blocked_sites_.push_back(std::move(form));
      continue;
    }
    std::string facet_uri = GetFacetRepresentation(form);

    DCHECK(map_facet_to_group_id.contains(facet_uri));
    GroupId group_id = map_facet_to_group_id[facet_uri];

    // Store group id for sign-on realm.
    map_signon_realm_to_group_id_[SignonRealm(form.signon_realm)] = group_id;

    // Store form for username/password key.
    UsernamePasswordKey key(CreateUsernamePasswordSortKey(form));
    map_group_id_to_credentials_[group_id].forms[key].push_back(
        std::move(form));
  }

  for (auto& passkey : passkeys) {
    // Group passkeys.
    std::string facet_uri = GetFacetRepresentation(passkey);
    GroupId group_id = map_facet_to_group_id[facet_uri];
    map_signon_realm_to_group_id_[SignonRealm(facet_uri)] = group_id;
    map_group_id_to_credentials_[group_id].passkeys.push_back(
        std::move(passkey));
  }
}

std::map<std::string, PasswordsGrouper::GroupId>
PasswordsGrouper::MapFacetsToGroupId(const std::vector<GroupedFacets>& groups) {
  int group_id_int = 1;
  std::map<std::string, GroupId> map_facet_to_group_id;
  std::set<std::string> facet_uri_in_groups;

  for (const GroupedFacets& grouped_facets : groups) {
    GroupId unique_group_id(group_id_int);
    for (const Facet& facet : grouped_facets.facets) {
      std::string facet_uri_str = facet.uri.potentially_invalid_spec();
      map_facet_to_group_id[facet_uri_str] = unique_group_id;

      // Keep track of facet URI (sign-on realm) that are already in a group.
      facet_uri_in_groups.insert(facet_uri_str);
    }

    // Store branding information for the affiliated group.
    map_group_id_to_branding_info_[unique_group_id] =
        grouped_facets.branding_info;

    // Increment so it is a new id for the next group.
    group_id_int++;
  }

  return map_facet_to_group_id;
}

void PasswordsGrouper::InitializePSLExtensionList(
    std::vector<std::string> psl_extension_list) {
  psl_extensions_ =
      base::MakeFlatSet<std::string>(std::move(psl_extension_list));
}

}  // namespace password_manager