1 /* 2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package com.sun.tools.jdeps; 26 27 import com.sun.tools.classfile.AccessFlags; 28 import com.sun.tools.classfile.ClassFile; 29 import com.sun.tools.classfile.ConstantPoolException; 30 import com.sun.tools.classfile.Dependencies; 31 import com.sun.tools.classfile.Dependency; 32 33 import java.io.IOException; 34 import java.nio.file.Path; 35 import java.util.ArrayList; 36 import java.util.Deque; 37 import java.util.HashMap; 38 import java.util.LinkedHashSet; 39 import java.util.LinkedList; 40 import java.util.List; 41 import java.util.Map; 42 import java.util.Objects; 43 import java.util.Optional; 44 import java.util.Set; 45 import java.util.concurrent.Callable; 46 import java.util.concurrent.ConcurrentLinkedDeque; 47 import java.util.concurrent.ConcurrentSkipListSet; 48 import java.util.concurrent.ExecutionException; 49 import java.util.concurrent.ExecutorService; 50 import java.util.concurrent.Executors; 51 import java.util.concurrent.FutureTask; 52 import java.util.stream.Collectors; 53 import java.util.stream.Stream; 54 55 import static com.sun.tools.jdeps.Module.*; 56 import static com.sun.tools.jdeps.ModulePaths.SystemModulePath.JAVA_BASE; 57 58 public class DependencyFinder { 59 private final List<Archive> roots = new ArrayList<>(); 60 private final List<Archive> classpaths = new ArrayList<>(); 61 private final List<Module> modulepaths = new ArrayList<>(); 62 private final List<String> classes = new ArrayList<>(); 63 private final boolean compileTimeView; 64 65 DependencyFinder(boolean compileTimeView) { 66 this.compileTimeView = compileTimeView; 67 } 68 69 /* 70 * Adds a class name to the root set 71 */ 72 void addClassName(String cn) { 73 classes.add(cn); 74 } 75 76 /* 77 * Adds the archive of the given path to the root set 78 */ 79 void addRoot(Path path) { 80 addRoot(Archive.getInstance(path)); 81 } 82 83 /* 84 * Adds the given archive to the root set 85 */ 86 void addRoot(Archive archive) { 87 Objects.requireNonNull(archive); 88 if (!roots.contains(archive)) 89 roots.add(archive); 90 } 91 92 /** 93 * Add an archive specified in the classpath. 94 */ 95 void addClassPathArchive(Path path) { 96 addClassPathArchive(Archive.getInstance(path)); 97 } 98 99 /** 100 * Add an archive specified in the classpath. 101 */ 102 void addClassPathArchive(Archive archive) { 103 Objects.requireNonNull(archive); 104 classpaths.add(archive); 105 } 106 107 /** 108 * Add an archive specified in the modulepath. 109 */ 110 void addModule(Module m) { 111 Objects.requireNonNull(m); 112 modulepaths.add(m); 113 } 114 115 /** 116 * Returns the root set. 117 */ 118 List<Archive> roots() { 119 return roots; 120 } 121 122 /** 123 * Returns a stream of all archives including the root set, module paths, 124 * and classpath. 125 * 126 * This only returns the archives with classes parsed. 127 */ 128 Stream<Archive> archives() { 129 Stream<Archive> archives = Stream.concat(roots.stream(), modulepaths.stream()); 130 archives = Stream.concat(archives, classpaths.stream()); 131 return archives.filter(a -> !a.isEmpty()) 132 .distinct(); 133 } 134 135 /** 136 * Finds dependencies 137 * 138 * @param apiOnly API only 139 * @param maxDepth depth of transitive dependency analysis; zero indicates 140 * @throws IOException 141 */ 142 void findDependencies(JdepsFilter filter, boolean apiOnly, int maxDepth) 143 throws IOException 144 { 145 Dependency.Finder finder = 146 apiOnly ? Dependencies.getAPIFinder(AccessFlags.ACC_PROTECTED) 147 : Dependencies.getClassDependencyFinder(); 148 149 // list of archives to be analyzed 150 Set<Archive> roots = new LinkedHashSet<>(this.roots); 151 152 // include java.base in root set 153 roots.add(JAVA_BASE); 154 155 // If -include pattern specified, classes may be in module path or class path. 156 // To get compile time view analysis, all classes are analyzed. 157 // add all modules except JDK modules to root set 158 modulepaths.stream() 159 .filter(filter::matches) 160 .forEach(roots::add); 161 162 // add classpath to the root set 163 classpaths.stream() 164 .filter(filter::matches) 165 .forEach(roots::add); 166 167 // transitive dependency 168 int depth = maxDepth > 0 ? maxDepth : Integer.MAX_VALUE; 169 170 // Work queue of names of classfiles to be searched. 171 // Entries will be unique, and for classes that do not yet have 172 // dependencies in the results map. 173 ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>(); 174 ConcurrentSkipListSet<String> doneClasses = new ConcurrentSkipListSet<>(); 175 176 TaskExecutor executor = new TaskExecutor(finder, filter, apiOnly, deque, doneClasses); 177 try { 178 // get the immediate dependencies of the input files 179 for (Archive source : roots) { 180 executor.task(source, deque); 181 } 182 executor.waitForTasksCompleted(); 183 184 List<Archive> archives = Stream.concat(Stream.concat(roots.stream(), 185 modulepaths.stream()), 186 classpaths.stream()) 187 .collect(Collectors.toList()); 188 189 // Additional pass to find archive where dependences are identified 190 // and also any specified classes, if any. 191 // If -R is specified, perform transitive dependency analysis. 192 Deque<String> unresolved = new LinkedList<>(classes); 193 do { 194 String name; 195 while ((name = unresolved.poll()) != null) { 196 if (doneClasses.contains(name)) { 197 continue; 198 } 199 if (compileTimeView) { 200 final String cn = name + ".class"; 201 // parse all classes in the source archive 202 Optional<Archive> source = archives.stream() 203 .filter(a -> a.reader().entries().contains(cn)) 204 .findFirst(); 205 trace("%s compile time view %s%n", name, source.map(Archive::getName).orElse(" not found")); 206 if (source.isPresent()) { 207 executor.runTask(source.getWhenPresent(), deque); 208 } 209 } 210 ClassFile cf = null; 211 for (Archive archive : archives) { 212 cf = archive.reader().getClassFile(name); 213 214 if (cf != null) { 215 String classFileName; 216 try { 217 classFileName = cf.getName(); 218 } catch (ConstantPoolException e) { 219 throw new Dependencies.ClassFileError(e); 220 } 221 if (!doneClasses.contains(classFileName)) { 222 // if name is a fully-qualified class name specified 223 // from command-line, this class might already be parsed 224 doneClasses.add(classFileName); 225 for (Dependency d : finder.findDependencies(cf)) { 226 if (depth == 0) { 227 // ignore the dependency 228 archive.addClass(d.getOrigin()); 229 break; 230 } else if (filter.accepts(d) && filter.accept(archive)) { 231 // continue analysis on non-JDK classes 232 archive.addClass(d.getOrigin(), d.getTarget()); 233 String cn = d.getTarget().getName(); 234 if (!doneClasses.contains(cn) && !deque.contains(cn)) { 235 deque.add(cn); 236 } 237 } else { 238 // ensure that the parsed class is added the archive 239 archive.addClass(d.getOrigin()); 240 } 241 } 242 } 243 break; 244 } 245 } 246 if (cf == null) { 247 doneClasses.add(name); 248 } 249 } 250 unresolved = deque; 251 deque = new ConcurrentLinkedDeque<>(); 252 } while (!unresolved.isEmpty() && depth-- > 0); 253 } finally { 254 executor.shutdown(); 255 } 256 } 257 258 /** 259 * TaskExecutor creates FutureTask to analyze all classes in a given archive 260 */ 261 private class TaskExecutor { 262 final ExecutorService pool; 263 final Dependency.Finder finder; 264 final JdepsFilter filter; 265 final boolean apiOnly; 266 final Set<String> doneClasses; 267 final Map<Archive, FutureTask<Void>> tasks = new HashMap<>(); 268 269 TaskExecutor(Dependency.Finder finder, 270 JdepsFilter filter, 271 boolean apiOnly, 272 ConcurrentLinkedDeque<String> deque, 273 Set<String> doneClasses) { 274 this.pool = Executors.newFixedThreadPool(2); 275 this.finder = finder; 276 this.filter = filter; 277 this.apiOnly = apiOnly; 278 this.doneClasses = doneClasses; 279 } 280 281 /** 282 * Creates a new task to analyze class files in the given archive. 283 * The dependences are added to the given deque for analysis. 284 */ 285 FutureTask<Void> task(Archive archive, final ConcurrentLinkedDeque<String> deque) { 286 trace("parsing %s %s%n", archive.getName(), archive.path()); 287 FutureTask<Void> task = new FutureTask<Void>(new Callable<Void>() { 288 public Void call() throws Exception { 289 for (ClassFile cf : archive.reader().getClassFiles()) { 290 String classFileName; 291 try { 292 classFileName = cf.getName(); 293 } catch (ConstantPoolException e) { 294 throw new Dependencies.ClassFileError(e); 295 } 296 297 // tests if this class matches the -include 298 String cn = classFileName.replace('/', '.'); 299 if (!filter.matches(cn)) 300 continue; 301 302 // if -apionly is specified, analyze only exported and public types 303 if (apiOnly && !(isExported(archive, cn) && cf.access_flags.is(AccessFlags.ACC_PUBLIC))) 304 continue; 305 306 if (!doneClasses.contains(classFileName)) { 307 doneClasses.add(classFileName); 308 } 309 310 for (Dependency d : finder.findDependencies(cf)) { 311 if (filter.accepts(d) && filter.accept(archive)) { 312 String name = d.getTarget().getName(); 313 if (!doneClasses.contains(name) && !deque.contains(name)) { 314 deque.add(name); 315 } 316 archive.addClass(d.getOrigin(), d.getTarget()); 317 } else { 318 // ensure that the parsed class is added the archive 319 archive.addClass(d.getOrigin()); 320 } 321 } 322 } 323 return null; 324 } 325 }); 326 tasks.put(archive, task); 327 pool.submit(task); 328 return task; 329 } 330 331 /* 332 * This task will parse all class files of the given archive, if it's a new task. 333 * This method waits until the task is completed. 334 */ 335 void runTask(Archive archive, final ConcurrentLinkedDeque<String> deque) { 336 if (tasks.containsKey(archive)) 337 return; 338 339 FutureTask<Void> task = task(archive, deque); 340 try { 341 // wait for completion 342 task.get(); 343 } catch (InterruptedException|ExecutionException e) { 344 throw new Error(e); 345 } 346 } 347 348 /* 349 * Waits until all submitted tasks are completed. 350 */ 351 void waitForTasksCompleted() { 352 try { 353 for (FutureTask<Void> t : tasks.values()) { 354 if (t.isDone()) 355 continue; 356 357 // wait for completion 358 t.get(); 359 } 360 } catch (InterruptedException|ExecutionException e) { 361 throw new Error(e); 362 } 363 } 364 365 /* 366 * Shutdown the executor service. 367 */ 368 void shutdown() { 369 pool.shutdown(); 370 } 371 372 /** 373 * Tests if the given class name is exported by the given archive. 374 * 375 * All packages are exported in unnamed module. 376 */ 377 private boolean isExported(Archive archive, String classname) { 378 int i = classname.lastIndexOf('.'); 379 String pn = i > 0 ? classname.substring(0, i) : ""; 380 return archive.getModule().isExported(pn); 381 } 382 } 383 }