Merge from Chromium at DEPS revision 278856android-wear-5.0.0_r1android-l-preview_r2android-cts-5.0_r9android-cts-5.0_r8android-cts-5.0_r7android-cts-5.0_r6android-cts-5.0_r5android-cts-5.0_r4android-cts-5.0_r3android-5.0.2_r3android-5.0.2_r1android-5.0.1_r1android-5.0.0_r7android-5.0.0_r6android-5.0.0_r5.1android-5.0.0_r5android-5.0.0_r4android-5.0.0_r3android-5.0.0_r2android-5.0.0_r1lollipop-wear-releaselollipop-releaselollipop-devlollipop-cts-releasel-preview

This commit was generated by merge_to_master.py.

Change-Id: I283eef90c15d40ea8cd6290f12094fc152a2c45e

1 files changed, 49 insertions, 3 deletions

diff --git a/cpp/src/util/string_compare.cc b/cpp/src/util/string_compare.cc
index c63b138..31a7534 100644
--- a/cpp/src/util/string_compare.cc
+++ b/cpp/src/util/string_compare.cc
@@ -12,20 +12,54 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-#include "re2ptr.h"  // Must be the first #include statement!
-
 #include "string_compare.h"
 
 #include <libaddressinput/util/basictypes.h>
 
+#include <cassert>
 #include <string>
 
+#include <re2/re2.h>
+
+#include "lru_cache_using_std.h"
+
+// RE2 uses type string, which is not necessarily the same as type std::string.
+// In order to create objects of the correct type, to be able to pass pointers
+// to these objects to RE2, the function that does that is defined inside an
+// unnamed namespace inside the re2 namespace. Oh, my ...
+namespace re2 {
+namespace {
+
+// In order to (mis-)use RE2 to implement UTF-8 capable less<>, this function
+// calls RE2::PossibleMatchRange() to calculate the "lessest" string that would
+// be a case-insensitive match to the string. This is far too expensive to do
+// repeatedly, so the function is only ever called through an LRU cache.
+std::string ComputeMinPossibleMatch(const std::string& str) {
+  string min, max;  // N.B.: RE2 type string!
+
+  RE2::Options options;
+  options.set_literal(true);
+  options.set_case_sensitive(false);
+  RE2 matcher(str, options);
+
+  bool success = matcher.PossibleMatchRange(&min, &max, str.size());
+  assert(success);
+  (void)success;  // Prevent unused variable if assert() is optimized away.
+
+  return min;
+}
+
+}  // namespace
+}  // namespace re2
+
 namespace i18n {
 namespace addressinput {
 
 class StringCompare::Impl {
+  enum { MAX_CACHE_SIZE = 1 << 15 };
+
  public:
-  Impl() {
+  Impl() : min_possible_match_(&re2::ComputeMinPossibleMatch, MAX_CACHE_SIZE) {
     options_.set_literal(true);
     options_.set_case_sensitive(false);
   }
@@ -37,8 +71,15 @@ class StringCompare::Impl {
     return RE2::FullMatch(a, matcher);
   }
 
+  bool NaturalLess(const std::string& a, const std::string& b) const {
+    const std::string& min_a(min_possible_match_(a));
+    const std::string& min_b(min_possible_match_(b));
+    return min_a < min_b;
+  }
+
  private:
   RE2::Options options_;
+  mutable lru_cache_using_std<std::string, std::string> min_possible_match_;
 
   DISALLOW_COPY_AND_ASSIGN(Impl);
 };
@@ -52,5 +93,10 @@ bool StringCompare::NaturalEquals(const std::string& a,
   return impl_->NaturalEquals(a, b);
 }
 
+bool StringCompare::NaturalLess(const std::string& a,
+                                const std::string& b) const {
+  return impl_->NaturalLess(a, b);
+}
+
 }  // namespace addressinput
 }  // namespace i18n