Merge "Improve URI.equals performance."

3 files changed, 66 insertions, 15 deletions

diff --git a/benchmarks/src/benchmarks/regression/EqualsHashCodeBenchmark.java b/benchmarks/src/benchmarks/regression/EqualsHashCodeBenchmark.java
index a15a41a..72bb216 100644
--- a/benchmarks/src/benchmarks/regression/EqualsHashCodeBenchmark.java
+++ b/benchmarks/src/benchmarks/regression/EqualsHashCodeBenchmark.java
@@ -36,6 +36,8 @@ public final class EqualsHashCodeBenchmark extends SimpleBenchmark {
         abstract Object newInstance(String text) throws Exception;
     }
 
+    private static final String QUERY = "%E0%AE%A8%E0%AE%BE%E0%AE%AE%E0%AF%8D+%E0%AE%AE%E0%AF%81%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AE%BF%E0%AE%AF%E0%AE%AE%E0%AE%BE%E0%AE%A9%2C+%E0%AE%9A%E0%AF%81%E0%AE%B5%E0%AE%BE%E0%AE%B0%E0%AE%B8%E0%AF%8D%E0%AE%AF%E0%AE%AE%E0%AE%BE%E0%AE%A9+%E0%AE%87%E0%AE%B0%E0%AF%81%E0%AE%AA%E0%AF%8D%E0%AE%AA%E0%AF%87%E0%AE%BE%E0%AE%AE%E0%AF%8D%2C+%E0%AE%86%E0%AE%A9%E0%AE%BE%E0%AE%B2%E0%AF%8D+%E0%AE%9A%E0%AE%BF%E0%AE%B2+%E0%AE%A8%E0%AF%87%E0%AE%B0%E0%AE%99%E0%AF%8D%E0%AE%95%E0%AE%B3%E0%AE%BF%E0%AE%B2%E0%AF%8D+%E0%AE%9A%E0%AF%82%E0%AE%B4%E0%AF%8D%E0%AE%A8%E0%AE%BF%E0%AE%B2%E0%AF%88+%E0%AE%8F%E0%AE%B1%E0%AF%8D%E0%AE%AA%E0%AE%9F%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%8E%E0%AE%A9%E0%AF%8D%E0%AE%AA%E0%AE%A4%E0%AE%BE%E0%AE%B2%E0%AF%8D+%E0%AE%AA%E0%AE%A3%E0%AE%BF%E0%AE%AF%E0%AF%88%E0%AE%AF%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%B5%E0%AE%B2%E0%AE%BF+%E0%AE%85%E0%AE%B5%E0%AE%B0%E0%AF%88+%E0%AE%9A%E0%AE%BF%E0%AE%B2+%E0%AE%AA%E0%AF%86%E0%AE%B0%E0%AE%BF%E0%AE%AF+%E0%AE%95%E0%AF%86%E0%AE%BE%E0%AE%B3%E0%AF%8D%E0%AE%AE%E0%AF%81%E0%AE%A4%E0%AE%B2%E0%AF%8D+%E0%AE%AE%E0%AF%81%E0%AE%9F%E0%AE%BF%E0%AE%AF%E0%AF%81%E0%AE%AE%E0%AF%8D.+%E0%AE%85%E0%AE%A4%E0%AF%81+%E0%AE%9A%E0%AE%BF%E0%AE%B2+%E0%AE%A8%E0%AE%A9%E0%AF%8D%E0%AE%AE%E0%AF%88%E0%AE%95%E0%AE%B3%E0%AF%88+%E0%AE%AA%E0%AF%86%E0%AE%B1+%E0%AE%A4%E0%AE%B5%E0%AE%BF%E0%AE%B0%2C+%E0%AE%8E%E0%AE%AA%E0%AF%8D%E0%AE%AA%E0%AF%87%E0%AE%BE%E0%AE%A4%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%89%E0%AE%B4%E0%AF%88%E0%AE%95%E0%AF%8D%E0%AE%95+%E0%AE%89%E0%AE%9F%E0%AE%B1%E0%AF%8D%E0%AE%AA%E0%AE%AF%E0%AE%BF%E0%AE%B1%E0%AF%8D%E0%AE%9A%E0%AE%BF+%E0%AE%AE%E0%AF%87%E0%AE%B1%E0%AF%8D%E0%AE%95%E0%AF%86%E0%AE%BE%E0%AE%B3%E0%AF%8D%E0%AE%95%E0%AE%BF%E0%AE%B1%E0%AE%A4%E0%AF%81+%E0%AE%8E%E0%AE%99%E0%AF%8D%E0%AE%95%E0%AE%B3%E0%AF%81%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AF%81+%E0%AE%87%E0%AE%A4%E0%AF%81+%E0%AE%92%E0%AE%B0%E0%AF%81+%E0%AE%9A%E0%AE%BF%E0%AE%B1%E0%AE%BF%E0%AE%AF+%E0%AE%89%E0%AE%A4%E0%AE%BE%E0%AE%B0%E0%AE%A3%E0%AE%AE%E0%AF%8D%2C+%E0%AE%8E%E0%AE%9F%E0%AF%81%E0%AE%95%E0%AF%8D%E0%AE%95.+%E0%AE%B0%E0%AE%AF%E0%AE%BF%E0%AE%B2%E0%AF%8D+%E0%AE%8E%E0%AE%A8%E0%AF%8D%E0%AE%A4+%E0%AE%B5%E0%AE%BF%E0%AE%B3%E0%AF%88%E0%AE%B5%E0%AE%BE%E0%AE%95+%E0%AE%87%E0%AE%A9%E0%AF%8D%E0%AE%AA%E0%AE%AE%E0%AF%8D+%E0%AE%86%E0%AE%A9%E0%AF%8D%E0%AE%B2%E0%AF%88%E0%AE%A9%E0%AF%8D+%E0%AE%AA%E0%AE%AF%E0%AE%A9%E0%AF%8D%E0%AE%AA%E0%AE%BE%E0%AE%9F%E0%AF%81%E0%AE%95%E0%AE%B3%E0%AF%8D+%E0%AE%87%E0%AE%B0%E0%AF%81%E0%AE%95%E0%AF%8D%E0%AE%95+%E0%AE%B5%E0%AF%87%E0%AE%A3%E0%AF%8D%E0%AE%9F%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%A4%E0%AE%AF%E0%AE%BE%E0%AE%B0%E0%AE%BF%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%A4%E0%AE%B5%E0%AE%B1%E0%AF%81+%E0%AE%95%E0%AE%A3%E0%AF%8D%E0%AE%9F%E0%AF%81%E0%AE%AA%E0%AE%BF%E0%AE%9F%E0%AE%BF%E0%AE%95%E0%AF%8D%E0%AE%95+%E0%AE%B5%E0%AE%B0%E0%AF%81%E0%AE%AE%E0%AF%8D+%E0%AE%A8%E0%AE%BE%E0%AE%AE%E0%AF%8D+%E0%AE%A4%E0%AE%B1%E0%AF%8D%E0%AE%AA%E0%AF%87%E0%AE%BE%E0%AE%A4%E0%AF%81+%E0%AE%87%E0%AE%B0%E0%AF%81%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AE%BF%E0%AE%B1%E0%AF%87%E0%AE%BE%E0%AE%AE%E0%AF%8D.+%E0%AE%87%E0%AE%A8%E0%AF%8D%E0%AE%A4+%E0%AE%A8%E0%AE%BF%E0%AE%95%E0%AE%B4%E0%AF%8D%E0%AE%B5%E0%AF%81%E0%AE%95%E0%AE%B3%E0%AE%BF%E0%AE%B2%E0%AF%8D+%E0%AE%9A%E0%AF%86%E0%AE%AF%E0%AF%8D%E0%AE%A4%E0%AE%AA%E0%AE%BF%E0%AE%A9%E0%AF%8D+%E0%AE%85%E0%AE%AE%E0%AF%88%E0%AE%AA%E0%AF%8D%E0%AE%AA%E0%AE%BF%E0%AE%A9%E0%AF%8D+%E0%AE%95%E0%AE%A3%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AF%81%2C+%E0%AE%85%E0%AE%B5%E0%AE%B0%E0%AF%8D%E0%AE%95%E0%AE%B3%E0%AF%8D+%E0%AE%A4%E0%AE%B5%E0%AE%B1%E0%AF%81+%E0%AE%B5%E0%AE%BF%E0%AE%9F%E0%AF%8D%E0%AE%9F%E0%AF%81+quae+%E0%AE%AA%E0%AE%9F%E0%AF%8D%E0%AE%9F%E0%AE%B1%E0%AF%88+%E0%AE%A8%E0%AF%80%E0%AE%99%E0%AF%8D%E0%AE%95%E0%AE%B3%E0%AF%8D+%E0%AE%AA%E0%AE%B0%E0%AE%BF%E0%AE%A8%E0%AF%8D%E0%AE%A4%E0%AF%81%E0%AE%B0%E0%AF%88%E0%AE%95%E0%AF%8D%E0%AE%95%E0%AE%BF%E0%AE%B1%E0%AF%87%E0%AE%BE%E0%AE%AE%E0%AF%8D+%E0%AE%AE%E0%AF%86%E0%AE%A9%E0%AF%8D%E0%AE%AE%E0%AF%88%E0%AE%AF%E0%AE%BE%E0%AE%95+%E0%AE%AE%E0%AE%BE%E0%AE%B1%E0%AF%81%E0%AE%AE%E0%AF%8D";
+
     @Param Type type;
 
     Object a1;
@@ -43,11 +45,18 @@ public final class EqualsHashCodeBenchmark extends SimpleBenchmark {
     Object b1;
     Object b2;
 
+    Object c1;
+    Object c2;
+
     @Override protected void setUp() throws Exception {
         a1 = type.newInstance("https://mail.google.com/mail/u/0/?shva=1#inbox");
         a2 = type.newInstance("https://mail.google.com/mail/u/0/?shva=1#inbox");
         b1 = type.newInstance("http://developer.android.com/reference/java/net/URI.html");
         b2 = type.newInstance("http://developer.android.com/reference/java/net/URI.html");
+
+        c1 = type.newInstance("http://developer.android.com/query?q=" + QUERY);
+        // Replace the very last char.
+        c2 = type.newInstance("http://developer.android.com/query?q=" + QUERY.substring(0, QUERY.length() - 3) + "%AF");
     }
 
     public void timeEquals(int reps) {
@@ -64,4 +73,10 @@ public final class EqualsHashCodeBenchmark extends SimpleBenchmark {
             b1.hashCode();
         }
     }
+
+    public void timeEqualsWithHeavilyEscapedComponent(int reps) {
+        for (int i = 0; i < reps; ++i) {
+            c1.equals(c2);
+        }
+    }
 }
diff --git a/luni/src/main/java/java/net/URI.java b/luni/src/main/java/java/net/URI.java
index 6b7b1da..09268b8 100644
--- a/luni/src/main/java/java/net/URI.java
+++ b/luni/src/main/java/java/net/URI.java
@@ -766,33 +766,51 @@ public final class URI implements Comparable<URI>, Serializable {
     }
 
     /**
-     * Returns true if {@code first} and {@code second} are equal after
-     * unescaping hex sequences like %F1 and %2b.
+     * Returns true if the given URI escaped strings {@code first} and {@code second} are
+     * equal.
+     *
+     * TODO: This method assumes that both strings are escaped using the same escape rules
+     * yet it still performs case insensitive comparison of the escaped sequences.
+     * Why is this necessary ? We can just replace it with first.equals(second)
+     * otherwise.
      */
     private boolean escapedEquals(String first, String second) {
-        if (first.indexOf('%') != second.indexOf('%')) {
-            return first.equals(second);
+        // This length test isn't a micro-optimization. We need it because we sometimes
+        // calculate the number of characters to match based on the length of the second
+        // string. If the second string is shorter than the first, we might attempt to match
+        // 0 chars, and regionMatches is specified to return true in that case.
+        if (first.length() != second.length()) {
+            return false;
         }
 
-        int index, prevIndex = 0;
-        while ((index = first.indexOf('%', prevIndex)) != -1
-                && second.indexOf('%', prevIndex) == index) {
-            boolean match = first.substring(prevIndex, index).equals(
-                    second.substring(prevIndex, index));
-            if (!match) {
+        int prevIndex = 0;
+        while (true) {
+            int index = first.indexOf('%', prevIndex);
+            int index1 = second.indexOf('%', prevIndex);
+            if (index != index1) {
+                return false;
+            }
+
+            // index == index1 from this point on.
+
+            if (index == -1) {
+                // No more escapes, match the remainder of the string
+                // normally.
+               return first.regionMatches(prevIndex, second, prevIndex,
+                       second.length() - prevIndex);
+            }
+
+            if (!first.regionMatches(prevIndex, second, prevIndex, (index - prevIndex))) {
                 return false;
             }
 
-            match = first.substring(index + 1, index + 3).equalsIgnoreCase(
-                    second.substring(index + 1, index + 3));
-            if (!match) {
+            if (!first.regionMatches(true /* ignore case */, index + 1, second, index + 1, 2)) {
                 return false;
             }
 
             index += 3;
             prevIndex = index;
         }
-        return first.substring(prevIndex).equals(second.substring(prevIndex));
     }
 
     @Override public boolean equals(Object o) {
diff --git a/luni/src/test/java/libcore/java/net/URITest.java b/luni/src/test/java/libcore/java/net/URITest.java
index 04a7d2e..0267699 100644
--- a/luni/src/test/java/libcore/java/net/URITest.java
+++ b/luni/src/test/java/libcore/java/net/URITest.java
@@ -16,9 +16,9 @@
 
 package libcore.java.net;
 
+import junit.framework.TestCase;
 import java.net.URI;
 import java.net.URISyntaxException;
-import junit.framework.TestCase;
 import libcore.util.SerializationTester;
 
 public final class URITest extends TestCase {
@@ -57,6 +57,24 @@ public final class URITest extends TestCase {
                 .equals(new URI("http://localhost/foo?bar=baz#QUUX")));
     }
 
+    public void testEqualsEscaping() throws Exception {
+        // Case insensitive when comparing escaped values, but not when
+        // comparing unescaped values.
+        assertEquals(new URI("http://localhost/foo?bar=fooobar%E0%AE%A8%E0bar"),
+                new URI("http://localhost/foo?bar=fooobar%E0%AE%a8%e0bar"));
+        assertFalse(new URI("http://localhost/foo?bar=fooobar%E0%AE%A8%E0bar").equals(
+                new URI("http://localhost/foo?bar=FoooBar%E0%AE%a8%e0bar")));
+        assertFalse(new URI("http://localhost/foo?bar=fooobar%E0%AE%A8%E0bar").equals(
+                new URI("http://localhost/foo?bar=fooobar%E0%AE%a8%e0BaR")));
+
+        // Last byte replaced by an unescaped value.
+        assertFalse(new URI("http://localhost/foo?bar=%E0%AE%A8%E0").equals(
+                new URI("http://localhost/foo?bar=%E0%AE%a8xxx")));
+        // Missing byte.
+        assertFalse(new URI("http://localhost/foo?bar=%E0%AE%A8%E0").equals(
+                new URI("http://localhost/foo?bar=%E0%AE%a8")));
+    }
+
     public void testFileEqualsWithEmptyHost() throws Exception {
         assertEquals(new URI("file", "", "/a/", null), new URI("file:/a/"));
         assertEquals(new URI("file", null, "/a/", null), new URI("file:/a/"));