Use boyer-moore for word searches

4 files changed, 103 insertions, 19 deletions

diff --git a/src/main/java/org/javacs/JavaCompilerService.java b/src/main/java/org/javacs/JavaCompilerService.java
index ea53b93..56614a8 100644
--- a/src/main/java/org/javacs/JavaCompilerService.java
+++ b/src/main/java/org/javacs/JavaCompilerService.java
@@ -151,9 +151,7 @@ public class JavaCompilerService {
 
     static boolean containsWord(String name, Path file) {
         if (!name.matches("\\w*")) throw new RuntimeException(String.format("`%s` is not a word", name));
-        // TODO consider using Parser.containsText, checking for \\b after finding matches
-        var word = Pattern.compile("\\b" + name + "\\b");
-        return Parser.containsPattern(file, word);
+        return Parser.containsWord(file, name);
     }
 
     static boolean importsAnyClass(String toPackage, List<String> toClasses, Path file) {
@@ -195,28 +193,33 @@ public class JavaCompilerService {
     public List<URI> potentialReferences(Element to) {
         LOG.info(String.format("Find potential references to `%s`...", to));
 
-        // Find files that import toPackage.toClass and contain the word el
-        var toPackage = packageName(to);
-        var toClass = className(to);
-        var name = to.getSimpleName().toString();
-        if (name.equals("<init>")) name = to.getEnclosingElement().getSimpleName().toString();
-        LOG.info(String.format("...look for the word `%s` in files that import %s.%s", name, toPackage, toClass));
-
         // Check all files on source path
         var allFiles = allJavaSources();
         LOG.info(String.format("...check %d files on the source path", allFiles.size()));
 
-        // Check files, one at a time
-        var result = new ArrayList<URI>();
-        int nScanned = 0;
+        // Figure out which files import `to`, explicitly or implicitly
+        var toPackage = packageName(to);
+        var toClass = className(to);
+        var hasImport = new ArrayList<Path>();
         for (var file : allFiles) {
-            if (containsImport(toPackage, toClass, file) && containsWord(name, file)) {
-                result.add(file.toUri());
+            if (containsImport(toPackage, toClass, file)) {
+                hasImport.add(file);
             }
         }
-        LOG.info(String.format("...%d files might have references to `%s`", result.size(), to));
+        LOG.info(String.format("...%d files import %s.%s", hasImport.size(), toPackage, toClass));
 
-        return result;
+        // Figure out which of those files have the word `to`
+        var name = to.getSimpleName().toString();
+        if (name.equals("<init>")) name = to.getEnclosingElement().getSimpleName().toString();
+        var hasWord = new ArrayList<URI>();
+        for (var file : hasImport) {
+            if (containsWord(name, file)) {
+                hasWord.add(file.toUri());
+            }
+        }
+        LOG.info(String.format("...%d files contain the word `%s`", hasWord.size(), name));
+
+        return hasWord;
     }
 
     public static String packageName(Element e) {
diff --git a/src/main/java/org/javacs/Parser.java b/src/main/java/org/javacs/Parser.java
index 354ee54..d1d9bcb 100644
--- a/src/main/java/org/javacs/Parser.java
+++ b/src/main/java/org/javacs/Parser.java
@@ -152,6 +152,21 @@ class Parser {
         }
     }
 
+    static boolean containsWord(Path java, String query) {
+        var search = new StringSearch(query);
+        try (var channel = FileChannel.open(java)) {
+            // Read up to 1 MB of data from file
+            var limit = Math.min((int) channel.size(), SEARCH_BUFFER.capacity());
+            SEARCH_BUFFER.position(0);
+            SEARCH_BUFFER.limit(limit);
+            channel.read(SEARCH_BUFFER);
+            SEARCH_BUFFER.position(0);
+            return search.nextWord(SEARCH_BUFFER) != -1;
+        } catch (IOException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
     static boolean containsPattern(Path java, Pattern pattern) {
         try (var channel = FileChannel.open(java)) {
             // Read up to 1 MB of data from file
diff --git a/src/main/java/org/javacs/StringSearch.java b/src/main/java/org/javacs/StringSearch.java
index 037e894..65a5022 100644
--- a/src/main/java/org/javacs/StringSearch.java
+++ b/src/main/java/org/javacs/StringSearch.java
@@ -96,7 +96,11 @@ class StringSearch {
     }
 
     int next(ByteBuffer text) {
-        var i = pattern.length - 1;
+        return next(text, 0);
+    }
+
+    int next(ByteBuffer text, int startingAfter) {
+        var i = startingAfter + pattern.length - 1;
         while (i < text.limit()) {
             // Compare backwards from the end until the first unmatching character.
             var j = pattern.length - 1;
@@ -112,6 +116,43 @@ class StringSearch {
         return -1;
     }
 
+    boolean isWordChar(byte b) {
+        char c = (char) (b + 128);
+        return Character.isAlphabetic(c) || Character.isDigit(c) || c == '$' || c == '_';
+    }
+
+    boolean startsWord(ByteBuffer text, int offset) {
+        if (offset == 0) return true;
+        return !isWordChar(text.get(offset - 1));
+    }
+
+    boolean endsWord(ByteBuffer text, int offset) {
+        if (offset + 1 >= text.limit()) return true;
+        return !isWordChar(text.get(offset + 1));
+    }
+
+    boolean isWord(ByteBuffer text, int offset) {
+        return startsWord(text, offset) && endsWord(text, offset + pattern.length - 1);
+    }
+
+    int nextWord(String text) {
+        return nextWord(text.getBytes());
+    }
+
+    int nextWord(byte[] text) {
+        return nextWord(ByteBuffer.wrap(text));
+    }
+
+    int nextWord(ByteBuffer text) {
+        var i = 0;
+        while (true) {
+            i = next(text, i);
+            if (i == -1) return -1;
+            if (isWord(text, i)) return i;
+            i++;
+        }
+    }
+
     private boolean hasPrefix(byte[] s, Slice prefix) {
         for (int i = 0; i < prefix.length(); i++) {
             if (s[i] != prefix.get(i)) return false;
diff --git a/src/test/java/org/javacs/StringSearchTest.java b/src/test/java/org/javacs/StringSearchTest.java
index 7827fcd..b11efde 100644
--- a/src/test/java/org/javacs/StringSearchTest.java
+++ b/src/test/java/org/javacs/StringSearchTest.java
@@ -11,8 +11,13 @@ public class StringSearchTest {
         assertThat(got, equalTo(index));
     }
 
+    private void testNextWord(String pat, String text, int index) {
+        var got = new StringSearch(pat).nextWord(text);
+        assertThat(got, equalTo(index));
+    }
+
     @Test
-    public void testFinderNext() {
+    public void testNext() {
         testNext("", "", 0);
         testNext("", "abc", 0);
         testNext("abc", "", -1);
@@ -29,4 +34,24 @@ public class StringSearchTest {
         testNext("baa", "aaaaa", -1);
         testNext("at that", "which finally halts.  at that point", 22);
     }
+
+    @Test
+    public void testNextWord() {
+        testNextWord("", "", 0);
+        testNextWord("", "abc", -1);
+        testNextWord("abc", "", -1);
+        testNextWord("abc", "abc", 0);
+        testNextWord("d", "abcdefg", -1);
+        testNextWord("d", "abc d efg", 4);
+        testNextWord("nan", "banana", -1);
+        testNextWord("nan", "ba nan a", 3);
+        testNextWord("abcd", "abc", -1);
+        testNextWord("abcd", "bcd", -1);
+        testNextWord("bcd", "abcd", -1);
+        testNextWord("bcd", "a bcd", 2);
+        testNextWord("abc", "abc d", 0);
+        testNextWord("aa", "aaa", -1);
+        testNextWord("aa", "a aa", 2);
+        testNextWord("aa", "aa a", 0);
+    }
 }