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 }