1 /* 2 * Copyright 2016 Google Inc. All Rights Reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.googlejavaformat.java; 18 19 import static java.nio.charset.StandardCharsets.UTF_8; 20 21 import com.google.common.base.CharMatcher; 22 import com.google.common.collect.HashMultimap; 23 import com.google.common.collect.ImmutableList; 24 import com.google.common.collect.Iterables; 25 import com.google.common.collect.Multimap; 26 import com.google.common.collect.Range; 27 import com.google.common.collect.RangeMap; 28 import com.google.common.collect.RangeSet; 29 import com.google.common.collect.TreeRangeMap; 30 import com.google.common.collect.TreeRangeSet; 31 import com.google.googlejavaformat.Newlines; 32 import com.sun.source.doctree.DocCommentTree; 33 import com.sun.source.doctree.ReferenceTree; 34 import com.sun.source.tree.IdentifierTree; 35 import com.sun.source.tree.ImportTree; 36 import com.sun.source.tree.Tree; 37 import com.sun.source.util.DocTreePath; 38 import com.sun.source.util.DocTreePathScanner; 39 import com.sun.source.util.TreePathScanner; 40 import com.sun.source.util.TreeScanner; 41 import com.sun.tools.javac.api.JavacTrees; 42 import com.sun.tools.javac.file.JavacFileManager; 43 import com.sun.tools.javac.parser.JavacParser; 44 import com.sun.tools.javac.parser.ParserFactory; 45 import com.sun.tools.javac.tree.DCTree; 46 import com.sun.tools.javac.tree.DCTree.DCReference; 47 import com.sun.tools.javac.tree.JCTree; 48 import com.sun.tools.javac.tree.JCTree.JCCompilationUnit; 49 import com.sun.tools.javac.tree.JCTree.JCFieldAccess; 50 import com.sun.tools.javac.tree.JCTree.JCIdent; 51 import com.sun.tools.javac.tree.JCTree.JCImport; 52 import com.sun.tools.javac.util.Context; 53 import com.sun.tools.javac.util.Log; 54 import com.sun.tools.javac.util.Options; 55 import java.io.IOError; 56 import java.io.IOException; 57 import java.net.URI; 58 import java.util.LinkedHashSet; 59 import java.util.Map; 60 import java.util.Set; 61 import javax.tools.Diagnostic; 62 import javax.tools.DiagnosticCollector; 63 import javax.tools.DiagnosticListener; 64 import javax.tools.JavaFileObject; 65 import javax.tools.SimpleJavaFileObject; 66 import javax.tools.StandardLocation; 67 68 /** 69 * Removes unused imports from a source file. Imports that are only used in javadoc are also 70 * removed, and the references in javadoc are replaced with fully qualified names. 71 */ 72 public class RemoveUnusedImports { 73 74 // Visits an AST, recording all simple names that could refer to imported 75 // types and also any javadoc references that could refer to imported 76 // types (`@link`, `@see`, `@throws`, etc.) 77 // 78 // No attempt is made to determine whether simple names occur in contexts 79 // where they are type names, so there will be false positives. For example, 80 // `List` is not identified as unused import below: 81 // 82 // ``` 83 // import java.util.List; 84 // class List {} 85 // ``` 86 // 87 // This is still reasonably effective in practice because type names differ 88 // from other kinds of names in casing convention, and simple name 89 // clashes between imported and declared types are rare. 90 private static class UnusedImportScanner extends TreePathScanner<Void, Void> { 91 92 private final Set<String> usedNames = new LinkedHashSet<>(); 93 private final Multimap<String, Range<Integer>> usedInJavadoc = HashMultimap.create(); 94 final JavacTrees trees; 95 final DocTreeScanner docTreeSymbolScanner; 96 UnusedImportScanner(JavacTrees trees)97 private UnusedImportScanner(JavacTrees trees) { 98 this.trees = trees; 99 docTreeSymbolScanner = new DocTreeScanner(); 100 } 101 102 /** Skip the imports themselves when checking for usage. */ 103 @Override visitImport(ImportTree importTree, Void usedSymbols)104 public Void visitImport(ImportTree importTree, Void usedSymbols) { 105 return null; 106 } 107 108 @Override visitIdentifier(IdentifierTree tree, Void unused)109 public Void visitIdentifier(IdentifierTree tree, Void unused) { 110 if (tree == null) { 111 return null; 112 } 113 usedNames.add(tree.getName().toString()); 114 return null; 115 } 116 117 @Override scan(Tree tree, Void unused)118 public Void scan(Tree tree, Void unused) { 119 if (tree == null) { 120 return null; 121 } 122 scanJavadoc(); 123 return super.scan(tree, unused); 124 } 125 scanJavadoc()126 private void scanJavadoc() { 127 if (getCurrentPath() == null) { 128 return; 129 } 130 DocCommentTree commentTree = trees.getDocCommentTree(getCurrentPath()); 131 if (commentTree == null) { 132 return; 133 } 134 docTreeSymbolScanner.scan(new DocTreePath(getCurrentPath(), commentTree), null); 135 } 136 137 // scan javadoc comments, checking for references to imported types 138 class DocTreeScanner extends DocTreePathScanner<Void, Void> { 139 @Override visitIdentifier(com.sun.source.doctree.IdentifierTree node, Void aVoid)140 public Void visitIdentifier(com.sun.source.doctree.IdentifierTree node, Void aVoid) { 141 return null; 142 } 143 144 @Override visitReference(ReferenceTree referenceTree, Void unused)145 public Void visitReference(ReferenceTree referenceTree, Void unused) { 146 DCReference reference = (DCReference) referenceTree; 147 long basePos = 148 reference.getSourcePosition((DCTree.DCDocComment) getCurrentPath().getDocComment()); 149 // the position of trees inside the reference node aren't stored, but the qualifier's 150 // start position is the beginning of the reference node 151 if (reference.qualifierExpression != null) { 152 new ReferenceScanner(basePos).scan(reference.qualifierExpression, null); 153 } 154 // Record uses inside method parameters. The javadoc tool doesn't use these, but 155 // IntelliJ does. 156 if (reference.paramTypes != null) { 157 for (JCTree param : reference.paramTypes) { 158 // TODO(cushon): get start positions for the parameters 159 new ReferenceScanner(-1).scan(param, null); 160 } 161 } 162 return null; 163 } 164 165 // scans the qualifier and parameters of a javadoc reference for possible type names 166 private class ReferenceScanner extends TreeScanner<Void, Void> { 167 private final long basePos; 168 ReferenceScanner(long basePos)169 public ReferenceScanner(long basePos) { 170 this.basePos = basePos; 171 } 172 173 @Override visitIdentifier(IdentifierTree node, Void aVoid)174 public Void visitIdentifier(IdentifierTree node, Void aVoid) { 175 usedInJavadoc.put( 176 node.getName().toString(), 177 basePos != -1 178 ? Range.closedOpen((int) basePos, (int) basePos + node.getName().length()) 179 : null); 180 return super.visitIdentifier(node, aVoid); 181 } 182 } 183 } 184 } 185 removeUnusedImports(final String contents)186 public static String removeUnusedImports(final String contents) throws FormatterException { 187 Context context = new Context(); 188 JCCompilationUnit unit = parse(context, contents); 189 if (unit == null) { 190 // error handling is done during formatting 191 return contents; 192 } 193 UnusedImportScanner scanner = new UnusedImportScanner(JavacTrees.instance(context)); 194 scanner.scan(unit, null); 195 return applyReplacements( 196 contents, buildReplacements(contents, unit, scanner.usedNames, scanner.usedInJavadoc)); 197 } 198 parse(Context context, String javaInput)199 private static JCCompilationUnit parse(Context context, String javaInput) 200 throws FormatterException { 201 DiagnosticCollector<JavaFileObject> diagnostics = new DiagnosticCollector<>(); 202 context.put(DiagnosticListener.class, diagnostics); 203 Options.instance(context).put("--enable-preview", "true"); 204 Options.instance(context).put("allowStringFolding", "false"); 205 JCCompilationUnit unit; 206 JavacFileManager fileManager = new JavacFileManager(context, true, UTF_8); 207 try { 208 fileManager.setLocation(StandardLocation.PLATFORM_CLASS_PATH, ImmutableList.of()); 209 } catch (IOException e) { 210 // impossible 211 throw new IOError(e); 212 } 213 SimpleJavaFileObject source = 214 new SimpleJavaFileObject(URI.create("source"), JavaFileObject.Kind.SOURCE) { 215 @Override 216 public CharSequence getCharContent(boolean ignoreEncodingErrors) throws IOException { 217 return javaInput; 218 } 219 }; 220 Log.instance(context).useSource(source); 221 ParserFactory parserFactory = ParserFactory.instance(context); 222 JavacParser parser = 223 parserFactory.newParser( 224 javaInput, /*keepDocComments=*/ true, /*keepEndPos=*/ true, /*keepLineMap=*/ true); 225 unit = parser.parseCompilationUnit(); 226 unit.sourcefile = source; 227 Iterable<Diagnostic<? extends JavaFileObject>> errorDiagnostics = 228 Iterables.filter(diagnostics.getDiagnostics(), Formatter::errorDiagnostic); 229 if (!Iterables.isEmpty(errorDiagnostics)) { 230 // error handling is done during formatting 231 throw FormatterException.fromJavacDiagnostics(errorDiagnostics); 232 } 233 return unit; 234 } 235 236 /** Construct replacements to fix unused imports. */ buildReplacements( String contents, JCCompilationUnit unit, Set<String> usedNames, Multimap<String, Range<Integer>> usedInJavadoc)237 private static RangeMap<Integer, String> buildReplacements( 238 String contents, 239 JCCompilationUnit unit, 240 Set<String> usedNames, 241 Multimap<String, Range<Integer>> usedInJavadoc) { 242 RangeMap<Integer, String> replacements = TreeRangeMap.create(); 243 for (JCImport importTree : unit.getImports()) { 244 String simpleName = getSimpleName(importTree); 245 if (!isUnused(unit, usedNames, usedInJavadoc, importTree, simpleName)) { 246 continue; 247 } 248 // delete the import 249 int endPosition = importTree.getEndPosition(unit.endPositions); 250 endPosition = Math.max(CharMatcher.isNot(' ').indexIn(contents, endPosition), endPosition); 251 String sep = Newlines.guessLineSeparator(contents); 252 if (endPosition + sep.length() < contents.length() 253 && contents.subSequence(endPosition, endPosition + sep.length()).toString().equals(sep)) { 254 endPosition += sep.length(); 255 } 256 replacements.put(Range.closedOpen(importTree.getStartPosition(), endPosition), ""); 257 } 258 return replacements; 259 } 260 getSimpleName(JCImport importTree)261 private static String getSimpleName(JCImport importTree) { 262 return importTree.getQualifiedIdentifier() instanceof JCIdent 263 ? ((JCIdent) importTree.getQualifiedIdentifier()).getName().toString() 264 : ((JCFieldAccess) importTree.getQualifiedIdentifier()).getIdentifier().toString(); 265 } 266 isUnused( JCCompilationUnit unit, Set<String> usedNames, Multimap<String, Range<Integer>> usedInJavadoc, JCImport importTree, String simpleName)267 private static boolean isUnused( 268 JCCompilationUnit unit, 269 Set<String> usedNames, 270 Multimap<String, Range<Integer>> usedInJavadoc, 271 JCImport importTree, 272 String simpleName) { 273 String qualifier = 274 ((JCFieldAccess) importTree.getQualifiedIdentifier()).getExpression().toString(); 275 if (qualifier.equals("java.lang")) { 276 return true; 277 } 278 if (unit.getPackageName() != null && unit.getPackageName().toString().equals(qualifier)) { 279 return true; 280 } 281 if (importTree.getQualifiedIdentifier() instanceof JCFieldAccess 282 && ((JCFieldAccess) importTree.getQualifiedIdentifier()) 283 .getIdentifier() 284 .contentEquals("*")) { 285 return false; 286 } 287 288 if (usedNames.contains(simpleName)) { 289 return false; 290 } 291 if (usedInJavadoc.containsKey(simpleName)) { 292 return false; 293 } 294 return true; 295 } 296 297 /** Applies the replacements to the given source, and re-format any edited javadoc. */ applyReplacements(String source, RangeMap<Integer, String> replacements)298 private static String applyReplacements(String source, RangeMap<Integer, String> replacements) { 299 // save non-empty fixed ranges for reformatting after fixes are applied 300 RangeSet<Integer> fixedRanges = TreeRangeSet.create(); 301 302 // Apply the fixes in increasing order, adjusting ranges to account for 303 // earlier fixes that change the length of the source. The output ranges are 304 // needed so we can reformat fixed regions, otherwise the fixes could just 305 // be applied in descending order without adjusting offsets. 306 StringBuilder sb = new StringBuilder(source); 307 int offset = 0; 308 for (Map.Entry<Range<Integer>, String> replacement : replacements.asMapOfRanges().entrySet()) { 309 Range<Integer> range = replacement.getKey(); 310 String replaceWith = replacement.getValue(); 311 int start = offset + range.lowerEndpoint(); 312 int end = offset + range.upperEndpoint(); 313 sb.replace(start, end, replaceWith); 314 if (!replaceWith.isEmpty()) { 315 fixedRanges.add(Range.closedOpen(start, end)); 316 } 317 offset += replaceWith.length() - (range.upperEndpoint() - range.lowerEndpoint()); 318 } 319 return sb.toString(); 320 } 321 } 322