Prune using package names

7 files changed, 298 insertions, 215 deletions

diff --git a/src/main/java/org/javacs/Cache.java b/src/main/java/org/javacs/Cache.java
index 2319e94..b1c893d 100644
--- a/src/main/java/org/javacs/Cache.java
+++ b/src/main/java/org/javacs/Cache.java
@@ -6,51 +6,68 @@ import java.nio.file.Path;
 import java.time.Instant;
 import java.util.HashMap;
 import java.util.Map;
-import java.util.function.Function;
+import java.util.Objects;
 
+/** Cache maps a file + an arbitrary key to a value. When the file is modified, the mapping expires. */
 class Cache<K, V> {
-    private class Entry {
-        final V value;
-        final Instant created = Instant.now();
+    private class Key {
+        final Path file;
+        final K key;
 
-        Entry(V value) {
-            this.value = value;
+        Key(Path file, K key) {
+            this.file = file;
+            this.key = key;
         }
-    }
 
-    private Map<K, Entry> map = new HashMap<>();
+        @Override
+        public boolean equals(Object other) {
+            if (other.getClass() != Key.class) return false;
+            var that = (Key) other;
+            return Objects.equals(this.key, that.key) && Objects.equals(this.file, that.file);
+        }
 
-    private final Function<K, V> loader;
+        @Override
+        public int hashCode() {
+            return Objects.hash(file, key);
+        }
+    }
 
-    private final Function<K, Path> asFile;
+    private class Value {
+        final V value;
+        final Instant created = Instant.now();
 
-    Cache(Function<K, V> loader, Function<K, Path> asFile) {
-        this.loader = loader;
-        this.asFile = asFile;
+        Value(V value) {
+            this.value = value;
+        }
     }
 
-    private void load(K key) {
-        // TODO limit total size of cache
-        var value = loader.apply(key);
-        map.put(key, new Entry(value));
-    }
+    private final Map<Key, Value> map = new HashMap<>();
 
-    V get(K key) {
-        // Check if file is missing from cache
-        if (!map.containsKey(key)) load(key);
+    boolean needs(Path file, K key) {
+        // If key is not in map, it needs to be loaded
+        if (!map.containsKey(key)) return true;
 
-        // Check if file is out-of-date
+        // If key was loaded before file was last modified, it needs to be reloaded
         var value = map.get(key);
-        var file = asFile.apply(key);
         Instant modified;
         try {
             modified = Files.getLastModifiedTime(file).toInstant();
         } catch (IOException e) {
             throw new RuntimeException(e);
         }
-        if (value.created.isBefore(modified)) load(key);
+        return value.created.isBefore(modified);
+    }
 
-        // Get up-to-date file from cache
-        return map.get(key).value;
+    void load(Path file, K key, V value) {
+        // TODO limit total size of cache
+        map.put(new Key(file, key), new Value(value));
+    }
+
+    V get(Path file, K key) {
+        var k = new Key(file, key);
+        if (!map.containsKey(k)) {
+            throw new IllegalArgumentException(k + " is not in map " + map);
+        }
+        return map.get(k).value;
     }
 }
diff --git a/src/main/java/org/javacs/CompileFocus.java b/src/main/java/org/javacs/CompileFocus.java
index 0d73fb9..95369ad 100644
--- a/src/main/java/org/javacs/CompileFocus.java
+++ b/src/main/java/org/javacs/CompileFocus.java
@@ -437,7 +437,6 @@ public class CompileFocus {
 
     private List<ExecutableElement> thisMethods() {
         var thisType = enclosingClass();
-        var types = task.getTypes();
         var result = new ArrayList<ExecutableElement>();
 
         if (thisType instanceof DeclaredType) {
diff --git a/src/main/java/org/javacs/JavaCompilerService.java b/src/main/java/org/javacs/JavaCompilerService.java
index d251222..8bb96fc 100644
--- a/src/main/java/org/javacs/JavaCompilerService.java
+++ b/src/main/java/org/javacs/JavaCompilerService.java
@@ -180,96 +180,11 @@ public class JavaCompilerService {
                 diags.add(new Warning(task, path, kind, "unused", message));
             }
         }
+        // TODO hint fields that could be final
 
         return Collections.unmodifiableList(new ArrayList<>(diags));
     }
 
-    private static class ContainsImportKey {
-        final Path file;
-        final String toPackage, toClass;
-
-        ContainsImportKey(Path file, String toPackage, String toClass) {
-            this.file = file;
-            this.toPackage = toPackage;
-            this.toClass = toClass;
-        }
-
-        @Override
-        public boolean equals(Object other) {
-            if (!(other instanceof ContainsImportKey)) return false;
-            var that = (ContainsImportKey) other;
-            if (!Objects.equals(this.file, that.file)) return false;
-            if (!Objects.equals(this.toPackage, that.toPackage)) return false;
-            if (!Objects.equals(this.toClass, that.toClass)) return false;
-            return true;
-        }
-
-        @Override
-        public int hashCode() {
-            return Objects.hash(file, toPackage, toClass);
-        }
-    }
-
-    private static Cache<ContainsImportKey, Boolean> cacheContainsImport =
-            new Cache<>(k -> containsImport(k.toPackage, k.toClass, k.file), k -> k.file);
-
-    static boolean containsImport(String toPackage, String toClass, Path file) {
-        if (toPackage.isEmpty()) return true;
-        var samePackage = Pattern.compile("^package +" + toPackage + ";");
-        var importClass = Pattern.compile("^import +" + toPackage + "\\." + toClass + ";");
-        var importStar = Pattern.compile("^import +" + toPackage + "\\.\\*;");
-        var importStatic = Pattern.compile("^import +static +" + toPackage + "\\." + toClass);
-        var startOfClass = Pattern.compile("^[\\w ]*class +\\w+");
-        // TODO this needs to use open text if available
-        try (var read = Files.newBufferedReader(file)) {
-            while (true) {
-                var line = read.readLine();
-                if (line == null) return false;
-                if (startOfClass.matcher(line).find()) return false;
-                if (samePackage.matcher(line).find()) return true;
-                if (importClass.matcher(line).find()) return true;
-                if (importStar.matcher(line).find()) return true;
-                if (importStatic.matcher(line).find()) return true;
-                if (importClass.matcher(line).find()) return true;
-            }
-        } catch (IOException e) {
-            throw new RuntimeException(e);
-        }
-    }
-
-    private static class ContainsWordKey {
-        final Path file;
-        final String word;
-
-        ContainsWordKey(Path file, String word) {
-            this.file = file;
-            this.word = word;
-        }
-
-        @Override
-        public boolean equals(Object other) {
-            if (!(other instanceof ContainsWordKey)) return false;
-            var that = (ContainsWordKey) other;
-            if (!Objects.equals(this.file, that.file)) return false;
-            if (!Objects.equals(this.word, that.word)) return false;
-            return true;
-        }
-
-        @Override
-        public int hashCode() {
-            return Objects.hash(file, word);
-        }
-    }
-
-    private static Cache<ContainsWordKey, Boolean> cacheContainsWord =
-            new Cache<>(k -> containsWord(k.word, k.file), k -> k.file);
-
-    static boolean containsWord(String name, Path file) {
-        if (!name.matches("\\w*")) throw new RuntimeException(String.format("`%s` is not a word", name));
-        // TODO this needs to use open text if available
-        return Parser.containsWord(file, name);
-    }
-
     public Set<URI> potentialDefinitions(Element to) {
         LOG.info(String.format("Find potential definitions of `%s`...", to));
 
@@ -281,16 +196,28 @@ public class JavaCompilerService {
             return set;
         }
 
-        // Check all files on source path
-        var allFiles = allJavaFiles.get();
-        LOG.info(String.format("...check %d files on the source path", allFiles.size()));
-
-        // TODO If `to` is package-private, any definitions must be in the same package
-
         if (to instanceof ExecutableElement) {
+            var allFiles = new HashSet<Path>();
+
+            // Look in files in my own package
+            var myPkg = packageName(to);
+            var myPkgFiles = sourceFilesInPackages(Set.of(myPkg));
+            allFiles.addAll(myPkgFiles);
+            LOG.info(String.format("...check %d files in package %s", myPkgFiles.size(), myPkg));
+
+            // If `to` is not package-private, look in other packages
+            if (!isPackagePrivate(to)) {
+                var descendents = descendentPackages(myPkg);
+                var files = sourceFilesInPackages(descendents);
+                allFiles.addAll(files);
+                LOG.info(
+                        String.format(
+                                "...check %d files in %d descendent packages", allFiles.size(), descendents.size()));
+            }
+
             // TODO this needs to use open text if available
             // Check if the file contains the name of `to`
-            var hasWord = hasWord(allFiles, to);
+            var hasWord = containsWord(allFiles, to);
             // Parse each file and check if the syntax tree is consistent with a definition of `to`
             // This produces some false positives, but parsing is much faster than compiling,
             // so it's an effective optimization
@@ -435,22 +362,35 @@ public class JavaCompilerService {
         return e.getSimpleName();
     }
 
+    private boolean isPackagePrivate(Element to) {
+        return !to.getModifiers().contains(Modifier.PROTECTED) && !to.getModifiers().contains(Modifier.PUBLIC);
+    }
+
     private Set<URI> scanForPotentialReferences(Element to, TreePathScanner<Void, Set<URI>> scan) {
-        // Check all files on source path
-        var allFiles = allJavaFiles.get();
-        LOG.info(String.format("...check %d files on the source path", allFiles.size()));
+        var allFiles = new HashSet<Path>();
+
+        // Look in files in my own package
+        var myPkg = packageName(to);
+        var myPkgFiles = sourceFilesInPackages(Set.of(myPkg));
+        allFiles.addAll(myPkgFiles);
+        LOG.info(String.format("...check %d files in my own package %s", myPkgFiles.size(), myPkg));
+
+        // If `to` is not package-private, look in other packages
+        if (!isPackagePrivate(to)) {
+            var descendents = descendentPackages(myPkg);
+            var files = sourceFilesInPackages(descendents);
+            allFiles.addAll(files);
+            LOG.info(String.format("...check %d files in %d descendent packages", allFiles.size(), descendents.size()));
+        }
 
         // TODO this needs to use open text if available
         // Check if the file contains the name of `to`
-        var hasWord = hasWord(allFiles, to);
-
-        // TODO If `to` is package-private, any definitions must be in the same package
+        var hasWord = containsWord(allFiles, to);
 
         // You can't reference a TypeElement without importing it
         if (to instanceof TypeElement) {
-            hasWord = hasImport(hasWord, (TypeElement) to);
+            hasWord = containsImport(hasWord, (TypeElement) to);
         }
-        // TODO for non-TypeElements, check for indirect imports
 
         // Parse each file and check if the syntax tree is consistent with a definition of `to`
         // This produces some false positives, but parsing is much faster than compiling,
@@ -461,6 +401,7 @@ public class JavaCompilerService {
             scan.scan(root, found);
         }
         LOG.info(String.format("...%d files contain matching syntax", found.size()));
+
         return found;
     }
 
@@ -539,13 +480,132 @@ public class JavaCompilerService {
         return false;
     }
 
-    private List<Path> hasWord(Collection<Path> allFiles, Element to) {
+    private static Cache<Void, Set<String>> cacheParseImportedPackages = new Cache<>();
+
+    private static Set<String> parseImportedPackages(Path file) {
+        if (cacheParseImportedPackages.needs(file, null)) {
+            var pkgs = Parser.importsPackages(file);
+            cacheParseImportedPackages.load(file, null, pkgs);
+        }
+        return cacheParseImportedPackages.get(file, null);
+    }
+
+    private static Cache<Void, String> cacheParsePackageName = new Cache<>();
+
+    private String packageName(Path file) {
+        if (cacheParsePackageName.needs(file, null)) {
+            var pkg = Parser.packageName(file);
+            cacheParsePackageName.load(file, null, pkg);
+        }
+        return cacheParsePackageName.get(file, null);
+    }
+
+    /** What packages are directly imported by child? */
+    private Set<String> importsPackages(Collection<String> children) {
+        var pkgs = new HashSet<String>();
+        for (var file : sourceFilesInPackages(children)) {
+            var fileImports = parseImportedPackages(file);
+            pkgs.addAll(fileImports);
+        }
+        return pkgs;
+    }
+
+    /** What packages transitively import parent? */
+    private Collection<String> descendentPackages(String ancestor) {
+        if (ancestor.equals("java.lang")) return allPackagesInSourcePath();
+
+        // invert[parent] is a set of all the packages that import parent
+        var invert = isImportedBy();
+
+        // Find all packages that transitively import ancestor
+        var descendents = new HashSet<String>();
+        var todo = new ArrayDeque<String>();
+        var done = new HashSet<String>();
+        todo.add(ancestor);
+        while (!todo.isEmpty()) {
+            var next = todo.pop();
+            if (!invert.containsKey(next)) continue;
+            var children = invert.get(next);
+            for (var child : children) {
+                if (!descendents.contains(child)) {
+                    LOG.info(String.format("...%s imports %s", child, next));
+                    descendents.add(child);
+                }
+            }
+            done.add(next);
+            for (var i : children) {
+                if (!done.contains(i)) todo.add(i);
+            }
+        }
+        return descendents;
+    }
+
+    private Map<String, Set<String>> isImportedBy() {
+        var map = new HashMap<String, Set<String>>();
+
+        for (var f : allJavaFiles.get()) {
+            var child = packageName(f);
+            var imports = parseImportedPackages(f);
+            for (var parent : imports) {
+                if (!map.containsKey(parent)) {
+                    map.put(parent, new HashSet<>());
+                }
+                map.get(parent).add(child);
+            }
+        }
+
+        return map;
+    }
+
+    /** List .java source files in package */
+    private List<Path> sourceFilesInPackages(Collection<String> inPackage) {
+        var packagePaths = new HashSet<Path>();
+        for (var pkg : inPackage) {
+            var path = Paths.get(pkg.replace('.', File.separatorChar));
+            packagePaths.add(path);
+        }
+        var files = new ArrayList<Path>();
+        for (var f : allJavaFiles.get()) {
+            var dir = f.getParent();
+            for (var packagePath : packagePaths) {
+                if (dir.endsWith(packagePath)) {
+                    files.add(f);
+                }
+            }
+        }
+        return files;
+    }
+
+    private List<String> allPackagesInSourcePath() {
+        var pkgs = new ArrayList<String>();
+        for (var f : allJavaFiles.get()) {
+            for (var src : sourcePath) {
+                if (f.startsWith(src)) {
+                    var dir = f.getParent();
+                    var rel = src.relativize(dir);
+                    var pkg = rel.toString().replace(File.separatorChar, '.');
+                    pkgs.add(pkg);
+                }
+            }
+        }
+        return pkgs;
+    }
+
+    private static Cache<String, Boolean> cacheContainsWord = new Cache<>();
+
+    private List<Path> containsWord(Collection<Path> allFiles, Element to) {
         // Figure out which of those files have the word `to`
         var name = to.getSimpleName().toString();
         if (name.equals("<init>")) name = to.getEnclosingElement().getSimpleName().toString();
+        if (!name.matches("\\w*")) throw new RuntimeException(String.format("`%s` is not a word", name));
         var hasWord = new ArrayList<Path>();
         for (var file : allFiles) {
-            if (cacheContainsWord.get(new ContainsWordKey(file, name))) {
+            if (cacheContainsWord.needs(file, name)) {
+                // TODO this needs to use open text if available
+                var found = Parser.containsWord(file, name);
+                cacheContainsWord.load(file, name, found);
+            }
+            if (cacheContainsWord.get(file, name)) {
                 hasWord.add(file);
             }
         }
@@ -554,13 +614,20 @@ public class JavaCompilerService {
         return hasWord;
     }
 
-    private List<Path> hasImport(Collection<Path> allFiles, TypeElement to) {
+    private static Cache<String, Boolean> cacheContainsImport = new Cache<>();
+
+    private List<Path> containsImport(Collection<Path> allFiles, TypeElement to) {
         // Figure out which files import `to`, explicitly or implicitly
+        var qName = to.getQualifiedName().toString();
         var toPackage = packageName(to);
         var toClass = className(to);
         var hasImport = new ArrayList<Path>();
         for (var file : allFiles) {
-            if (cacheContainsImport.get(new ContainsImportKey(file, toPackage, toClass))) {
+            if (cacheContainsImport.needs(file, qName)) {
+                var found = Parser.containsImport(file, toPackage, toClass);
+                cacheContainsImport.load(file, qName, found);
+            }
+            if (cacheContainsImport.get(file, qName)) {
                 hasImport.add(file);
             }
         }
diff --git a/src/main/java/org/javacs/Parser.java b/src/main/java/org/javacs/Parser.java
index 0ac234f..62e7d10 100644
--- a/src/main/java/org/javacs/Parser.java
+++ b/src/main/java/org/javacs/Parser.java
@@ -232,6 +232,86 @@ class Parser {
         return new Location(dUri, new Range(new Position(startLine, startCol), new Position(endLine, endCol)));
     }
 
+    static boolean containsImport(Path file, String toPackage, String toClass) {
+        if (toPackage.isEmpty()) return true;
+        var samePackage = Pattern.compile("^package +" + toPackage + ";");
+        var importClass = Pattern.compile("^import +" + toPackage + "\\." + toClass + ";");
+        var importStar = Pattern.compile("^import +" + toPackage + "\\.\\*;");
+        var importStatic = Pattern.compile("^import +static +" + toPackage + "\\." + toClass);
+        var startOfClass = Pattern.compile("^[\\w ]*class +\\w+");
+        // TODO this needs to use open text if available
+        try (var read = Files.newBufferedReader(file)) {
+            while (true) {
+                var line = read.readLine();
+                if (line == null) return false;
+                if (startOfClass.matcher(line).find()) return false;
+                if (samePackage.matcher(line).find()) return true;
+                if (importClass.matcher(line).find()) return true;
+                if (importStar.matcher(line).find()) return true;
+                if (importStatic.matcher(line).find()) return true;
+                if (importClass.matcher(line).find()) return true;
+            }
+        } catch (IOException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
+    static String packageName(Path file) {
+        var packagePattern = Pattern.compile("^package +(.*);");
+        var startOfClass = Pattern.compile("^[\\w ]*class +\\w+");
+        // TODO this needs to use open text if available
+        try (var read = Files.newBufferedReader(file)) {
+            for (var line = read.readLine(); line != null; line = read.readLine()) {
+                if (startOfClass.matcher(line).find()) return "";
+                var matchPackage = packagePattern.matcher(line);
+                if (matchPackage.matches()) {
+                    var id = matchPackage.group(1);
+                    return id;
+                }
+            }
+            return "";
+        } catch (IOException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
+    static Set<String> importsPackages(Path file) {
+        var importStatic = Pattern.compile("^import +static +(.+);");
+        var importAny = Pattern.compile("^import +(.+);");
+        var startOfClass = Pattern.compile("^[\\w ]*class +\\w+");
+        // TODO this needs to use open text if available
+        try (var read = Files.newBufferedReader(file)) {
+            var pkgs = new HashSet<String>();
+
+            for (var line = read.readLine(); line != null; line = read.readLine()) {
+                if (startOfClass.matcher(line).find()) break;
+                var matchImportStatic = importStatic.matcher(line);
+                if (matchImportStatic.matches()) {
+                    var id = matchImportStatic.group(1);
+                    var pkg = new StringJoiner(".");
+                    for (var part : id.split("\\.")) {
+                        var firstChar = part.charAt(0);
+                        if (Character.isUpperCase(firstChar) || firstChar == '*') break;
+                        pkg.add(part);
+                    }
+                    pkgs.add(pkg.toString());
+                    continue;
+                }
+                var matchImportAny = importAny.matcher(line);
+                if (matchImportAny.matches()) {
+                    var id = matchImportAny.group(1);
+                    var lastDot = id.lastIndexOf(".");
+                    if (lastDot != -1) id = id.substring(0, lastDot);
+                    pkgs.add(id);
+                }
+            }
+
+            return pkgs;
+        } catch (IOException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
     /** Find all already-imported symbols in all .java files in workspace */
     static ExistingImports existingImports(Collection<Path> allJavaFiles) {
         var classes = new HashSet<String>();
diff --git a/src/test/java/org/javacs/BenchmarkStringSearch.java b/src/test/java/org/javacs/BenchmarkStringSearch.java
deleted file mode 100644
index 1c453d2..0000000
--- a/src/test/java/org/javacs/BenchmarkStringSearch.java
+++ /dev/null
@@ -1,77 +0,0 @@
-package org.javacs;
-
-import java.nio.file.Path;
-import java.nio.file.Paths;
-import java.util.concurrent.TimeUnit;
-import org.openjdk.jmh.annotations.*;
-
-// TODO this is coloring badly
-@Warmup(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
-@Measurement(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
-@Fork(1)
-public class BenchmarkStringSearch {
-    private static final Path largeFile = Paths.get(FindResource.uri("/org/javacs/example/LargeFile.java")),
-            smallFile = Paths.get(FindResource.uri("/org/javacs/example/Goto.java"));
-    // "removeMethodBodies" appears late in the file, so stopping early will not be very effective
-    private static final String query = "removeMethodBodies";
-
-    @Benchmark
-    public void containsWordMatchingSmall() {
-        var found = Parser.containsWordMatching(smallFile, query);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsWordMatchingLarge() {
-        var found = Parser.containsWordMatching(largeFile, query);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsTextSmall() {
-        var found = Parser.containsText(smallFile, query);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsTextLarge() {
-        var found = Parser.containsText(largeFile, query);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsImportLarge() {
-        var found = JavaCompilerService.containsImport("java.util.nopkg", "Logger", largeFile);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsImportSmall() {
-        var found = JavaCompilerService.containsImport("java.util.nopkg", "Logger", smallFile);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsWordLarge() {
-        var found = JavaCompilerService.containsWord("removeMethodBodies", largeFile);
-        assert found;
-    }
-
-    @Benchmark
-    public void containsWordSmall() {
-        var found = JavaCompilerService.containsWord("removeMethodBodies", smallFile);
-        assert found;
-    }
-
-    @Benchmark
-    public void parseLarge() {
-        var found = Parser.parse(largeFile);
-        assert found != null;
-    }
-
-    @Benchmark
-    public void parseSmall() {
-        var found = Parser.parse(smallFile);
-        assert found != null;
-    }
-}
diff --git a/src/test/java/org/javacs/FindReferencesTest.java b/src/test/java/org/javacs/FindReferencesTest.java
index a9d1c0a..a4be019 100644
--- a/src/test/java/org/javacs/FindReferencesTest.java
+++ b/src/test/java/org/javacs/FindReferencesTest.java
@@ -5,13 +5,10 @@ import static org.junit.Assert.*;
 
 import java.util.ArrayList;
 import java.util.List;
-import java.util.logging.Logger;
 import org.javacs.lsp.*;
 import org.junit.Test;
 
 public class FindReferencesTest {
-    private static final Logger LOG = Logger.getLogger("main");
-
     private static final JavaLanguageServer server = LanguageServerFixture.getJavaLanguageServer();
 
     protected List<String> items(String file, int row, int column) {
diff --git a/src/test/java/org/javacs/ParserTest.java b/src/test/java/org/javacs/ParserTest.java
index 93ac5ed..92663a9 100644
--- a/src/test/java/org/javacs/ParserTest.java
+++ b/src/test/java/org/javacs/ParserTest.java
@@ -42,9 +42,9 @@ public class ParserTest {
     @Test
     public void largeFilePossibleReference() {
         var largeFile = Paths.get(FindResource.uri("/org/javacs/example/LargeFile.java"));
-        assertTrue(JavaCompilerService.containsImport("java.util.logging", "Logger", largeFile));
-        assertTrue(JavaCompilerService.containsWord("removeMethodBodies", largeFile));
-        assertFalse(JavaCompilerService.containsWord("removeMethodBodiez", largeFile));
+        assertTrue(Parser.containsImport(largeFile, "java.util.logging", "Logger"));
+        assertTrue(Parser.containsWord(largeFile, "removeMethodBodies"));
+        assertFalse(Parser.containsWord(largeFile, "removeMethodBodiez"));
     }
 
     @Test