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.get(), 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 }