Password reuse look-up optimization

components/password_manager/core/browser/password_reuse_detector.cc

Index: components/password_manager/core/browser/password_reuse_detector.cc
diff --git a/components/password_manager/core/browser/password_reuse_detector.cc b/components/password_manager/core/browser/password_reuse_detector.cc
index 625994a7be36952fb62c908b23f105cd62a446ba..dd9b2a94a5a6935bfbe359e8816a9676a454033a 100644
--- a/components/password_manager/core/browser/password_reuse_detector.cc
+++ b/components/password_manager/core/browser/password_reuse_detector.cc
@@ -4,6 +4,8 @@
 
 #include "components/password_manager/core/browser/password_reuse_detector.h"
 
+#include <algorithm>
+
 #include "components/autofill/core/common/password_form.h"
 #include "components/password_manager/core/browser/password_reuse_detector_consumer.h"
 #include "components/password_manager/core/browser/psl_matching_helper.h"
@@ -15,6 +17,22 @@ namespace {
 // It does not make sense to consider short strings for password reuse, since it
 // is quite likely that they are parts of common words.
 constexpr size_t kMinPasswordLengthToCheck = 8;
+
+// Returns true iff |suffix_candidate| is a suffix of |str|.
+bool IsSuffix(const base::string16& str,
+              const base::string16& suffix_candidate) {
+  if (str.size() < suffix_candidate.size())
+    return false;
+  return std::equal(suffix_candidate.rbegin(), suffix_candidate.rend(),
+                    str.rbegin());
+}
+
+}  // namespace
+
+bool ReverseStringLess::operator()(const base::string16& lhs,
+                                   const base::string16& rhs) const {
+  return std::lexicographical_compare(lhs.rbegin(), lhs.rend(), rhs.rbegin(),
+                                      rhs.rend());
 }
 
 PasswordReuseDetector::PasswordReuseDetector() {}
@@ -40,40 +58,62 @@ void PasswordReuseDetector::CheckReuse(
     const base::string16& input,
     const std::string& domain,
     PasswordReuseDetectorConsumer* consumer) {
-  // TODO(crbug.com/668155): Optimize password look-up.
   DCHECK(consumer);
+  if (input.size() < kMinPasswordLengthToCheck)
+    return;
+
   const std::string registry_controlled_domain =
       GetRegistryControlledDomain(GURL(domain));
-  for (size_t i = 0; i + kMinPasswordLengthToCheck <= input.size(); ++i) {
-    const base::string16 input_suffix = input.substr(i);
-    auto passwords_it = passwords_.find(input_suffix);
-    if (passwords_it == passwords_.end())
-      continue;
-
-    // Password found, check whether it's saved on the same domain.
-    const std::set<std::string>& domains = passwords_it->second;
-    DCHECK(!domains.empty());
-    if (domains.find(registry_controlled_domain) == domains.end()) {
-      // Return only one domain.
-      const std::string& saved_domain = *domains.begin();
-      consumer->OnReuseFound(input_suffix, saved_domain, saved_passwords_,
-                             domains.size());
-      return;
-    }
+  auto passwords_iterator = FindSavedPassword(input);
+  if (passwords_iterator == passwords_.end())
+    return;
+
+  const std::set<std::string>& domains = passwords_iterator->second;
+  DCHECK(!domains.empty());
+  if (domains.find(registry_controlled_domain) == domains.end()) {
+    // Return only one domain.
+    const std::string& saved_domain = *domains.begin();
+    consumer->OnReuseFound(passwords_iterator->first, saved_domain,
+                           saved_passwords_, domains.size());
+    return;
   }
 }
 
 void PasswordReuseDetector::AddPassword(const autofill::PasswordForm& form) {
-  const base::string16& password = form.password_value;
-  if (password.size() < kMinPasswordLengthToCheck)
+  if (form.password_value.size() < kMinPasswordLengthToCheck)
     return;
   GURL signon_realm(form.signon_realm);
   const std::string domain = GetRegistryControlledDomain(signon_realm);
-  std::set<std::string>& domains = passwords_[password];
+  std::set<std::string>& domains = passwords_[form.password_value];
   if (domains.find(domain) == domains.end()) {
     ++saved_passwords_;
     domains.insert(domain);
   }
 }
 
+PasswordReuseDetector::passwords_iterator
+PasswordReuseDetector::FindSavedPassword(const base::string16& input) {
+  // Keys in |passwords_| are ordered by lexicographical order of reversed
+  // strings. In order to check a password reuse a key of |passwords_| that is a
+  // suffix of |input| should be found. The longest such key should be the
+  // largest key in the |passwords_| keys order that is equal or smaller to
+  // |input|.
+  if (passwords_.empty())
+    return passwords_.end();
+
+  // lower_bound returns the first key that is bigger or equal to input.
+  auto it = passwords_.lower_bound(input);
+  if (it != passwords_.end() && it->first == input) {
+    // If the key is equal then a saved password is found.
+    return it;
+  }
+
+  // Otherwise the previous key is a candidate for password reuse.
+  if (it == passwords_.begin())
+    return passwords_.end();
+
+  --it;
+  return IsSuffix(input, it->first) ? it : passwords_.end();
+}
+
 }  // namespace password_manager