use anchored matching in URIResultParser.isBasicallyValidURI (#2109)

2 files changed, 15 insertions, 5 deletions

diff --git a/core/src/main/java/com/google/zxing/client/result/URIResultParser.java b/core/src/main/java/com/google/zxing/client/result/URIResultParser.java
index 21adc34f5..2c5dc272c 100644
--- a/core/src/main/java/com/google/zxing/client/result/URIResultParser.java
+++ b/core/src/main/java/com/google/zxing/client/result/URIResultParser.java
@@ -18,7 +18,6 @@ package com.google.zxing.client.result;
 
 import com.google.zxing.Result;
 
-import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 
 /**
@@ -70,12 +69,12 @@ public final class URIResultParser extends ResultParser {
       // Quick hack check for a common case
       return false;
     }
-    Matcher m = URL_WITH_PROTOCOL_PATTERN.matcher(uri);
-    if (m.find() && m.start() == 0) { // match at start only
+    // Anchor at the start. find() rescans from every position, which is quadratic on long
+    // input that has no match at the start; lookingAt() matches only a prefix.
+    if (URL_WITH_PROTOCOL_PATTERN.matcher(uri).lookingAt()) {
       return true;
     }
-    m = URL_WITHOUT_PROTOCOL_PATTERN.matcher(uri);
-    return m.find() && m.start() == 0;
+    return URL_WITHOUT_PROTOCOL_PATTERN.matcher(uri).lookingAt();
   }
 
 }
\ No newline at end of file
diff --git a/core/src/test/java/com/google/zxing/client/result/URIParsedResultTestCase.java b/core/src/test/java/com/google/zxing/client/result/URIParsedResultTestCase.java
index 168acbf3c..8b3dac1c0 100644
--- a/core/src/test/java/com/google/zxing/client/result/URIParsedResultTestCase.java
+++ b/core/src/test/java/com/google/zxing/client/result/URIParsedResultTestCase.java
@@ -65,6 +65,17 @@ public final class URIParsedResultTestCase extends Assert {
     doTestNotUri("foo.bar.bing.baz.foo.bar.bing.baz");
   }
 
+  // A long run of characters that never forms a URI at the start must be rejected quickly;
+  // find() rescanned from every position and was quadratic on such input.
+  @Test(timeout = 5000L)
+  public void testNoQuadraticScanning() {
+    StringBuilder sb = new StringBuilder(200000);
+    for (int i = 0; i < 200000; i++) {
+      sb.append('a');
+    }
+    assertFalse(URIResultParser.isBasicallyValidURI(sb.toString()));
+  }
+
   @Test
   public void testURLTO() {
     doTest("urlto::bar.com", "http://bar.com", null);