content: /*
   * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
   * particular file as subject to the "Classpath" exception as provided
   * by Oracle in the LICENSE file that accompanied this code.
   *
   * This code is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   * version 2 for more details (a copy is included in the LICENSE file that
   * accompanied this code).
   *
   * You should have received a copy of the GNU General Public License version
   * 2 along with this work; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   *
   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   * or visit www.oracle.com if you need additional information or have any
   * questions.
   */
  
  package openjdk.tools.jdeps;
  
  import static openjdk.tools.jdeps.JdepsFilter.DEFAULT_FILTER;
  import static openjdk.tools.jdeps.Module.trace;
  import static openjdk.tools.jdeps.Graph.*;
  
  import java.lang.module.ModuleDescriptor.Requires;
  import java.io.IOException;
  import java.util.Collections;
  import java.util.Deque;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedList;
  import java.util.Map;
  import java.util.Optional;
  import java.util.Set;
  import java.util.stream.Collectors;
  import java.util.stream.Stream;
  
  /**
   * Inverse transitive dependency analysis (compile-time view)
   */
  public class InverseDepsAnalyzer extends DepsAnalyzer {
      // the end points for the resulting paths to be reported
      private final Map<Archive, Set<Archive>> endPoints = new HashMap<>();
      // target archives for inverse transitive dependence analysis
      private final Set<Archive> targets = new HashSet<>();
  
      public InverseDepsAnalyzer(JdepsConfiguration config,
                                 JdepsFilter filter,
                                 JdepsWriter writer,
                                 Analyzer.Type verbose,
                                 boolean apiOnly) {
          super(config, filter, writer, verbose, apiOnly);
      }
  
      public boolean run() throws IOException {
          try {
              if (apiOnly) {
                  finder.parseExportedAPIs(rootArchives.stream());
              } else {
                  finder.parse(rootArchives.stream());
              }
              archives.addAll(rootArchives);
  
              Set<Archive> archives = archives();
  
              // If -package or -regex is specified, the archives that reference
              // the matching types are used as the targets for inverse
              // transitive analysis.  If -requires is specified, the
              // specified modules are the targets.
  
              if (filter.requiresFilter().isEmpty()) {
                  targets.addAll(archives);
              } else {
                  filter.requiresFilter().stream()
                        .map(configuration::findModule)
                        .flatMap(Optional::stream)
                        .forEach(targets::add);
              }
  
              // If -package or -regex is specified, the end points are
              // the matching archives.  If -requires is specified,
              // the end points are the modules specified in -requires.
              if (filter.requiresFilter().isEmpty()) {
                  Map<Archive, Set<Archive>> dependences = finder.dependences();
                  targets.forEach(source -> endPoints.put(source, dependences.get(source)));
              } else {
                  targets.forEach(t -> endPoints.put(t, Collections.emptySet()));
              }
  
              analyzer.run(archives, finder.locationToArchive());
  
              // print the first-level of dependencies
              if (writer != null) {
                  writer.generateOutput(archives, analyzer);
              }
  
          } finally {
              finder.shutdown();
          }
          return true;
      }
  
      /**
       * Returns the target archives determined from the dependency analysis.
       *
       * Inverse transitive dependency will find all nodes that depend
       * upon the returned set of archives directly and indirectly.
       */
      public Set<Archive> targets() {
          return Collections.unmodifiableSet(targets);
      }
  
      /**
       * Finds all inverse transitive dependencies using the given requires set
       * as the targets, if non-empty.  If the given requires set is empty,
       * use the archives depending the packages specified in -regex or -p options.
       */
      public Set<Deque<Archive>> inverseDependences() throws IOException {
          // create a new dependency finder to do the analysis
          DependencyFinder dependencyFinder = new DependencyFinder(configuration, DEFAULT_FILTER);
          try {
              // parse all archives in unnamed module to get compile-time dependences
              Stream<Archive> archives =
                  Stream.concat(configuration.initialArchives().stream(),
                                configuration.classPathArchives().stream());
              if (apiOnly) {
                  dependencyFinder.parseExportedAPIs(archives);
              } else {
                  dependencyFinder.parse(archives);
              }
  
              Graph.Builder<Archive> builder = new Graph.Builder<>();
              // include all target nodes
              targets().forEach(builder::addNode);
  
              // transpose the module graph
              configuration.getModules().values().stream()
                  .forEach(m -> {
                      builder.addNode(m);
                      m.descriptor().requires().stream()
                          .map(Requires::name)
                          .map(configuration::findModule)  // must be present
                          .forEach(v -> builder.addEdge(v.get(), m));
                  });
  
              // add the dependences from the analysis
              Map<Archive, Set<Archive>> dependences = dependencyFinder.dependences();
              dependences.entrySet().stream()
                  .forEach(e -> {
                      Archive u = e.getKey();
                      builder.addNode(u);
                      e.getValue().forEach(v -> builder.addEdge(v, u));
                  });
  
              // transposed dependence graph.
              Graph<Archive> graph = builder.build();
              trace("targets: %s%n", targets());
  
              // Traverse from the targets and find all paths
              // rebuild a graph with all nodes that depends on targets
              // targets directly and indirectly
              return targets().stream()
                  .map(t -> findPaths(graph, t))
                  .flatMap(Set::stream)
                  .collect(Collectors.toSet());
          } finally {
              dependencyFinder.shutdown();
          }
      }
  
      /**
       * Returns all paths reachable from the given targets.
       */
      private Set<Deque<Archive>> findPaths(Graph<Archive> graph, Archive target) {
  
          // path is in reversed order
          Deque<Archive> path = new LinkedList<>();
          path.push(target);
  
          Set<Edge<Archive>> visited = new HashSet<>();
  
          Deque<Edge<Archive>> deque = new LinkedList<>();
          deque.addAll(graph.edgesFrom(target));
          if (deque.isEmpty()) {
              return makePaths(path).collect(Collectors.toSet());
          }
  
          Set<Deque<Archive>> allPaths = new HashSet<>();
          while (!deque.isEmpty()) {
              Edge<Archive> edge = deque.pop();
  
              if (visited.contains(edge))
                  continue;
  
              Archive node = edge.v;
              path.addLast(node);
              visited.add(edge);
  
              Set<Edge<Archive>> unvisitedDeps = graph.edgesFrom(node)
                      .stream()
                      .filter(e -> !visited.contains(e))
                      .collect(Collectors.toSet());
  
              trace("visiting %s %s (%s)%n", edge, path, unvisitedDeps);
              if (unvisitedDeps.isEmpty()) {
                  makePaths(path).forEach(allPaths::add);
                  path.removeLast();
              }
  
              // push unvisited adjacent edges
              unvisitedDeps.stream().forEach(deque::push);
  
  
              // when the adjacent edges of a node are visited, pop it from the path
              while (!path.isEmpty()) {
                  if (visited.containsAll(graph.edgesFrom(path.peekLast())))
                      path.removeLast();
                  else
                      break;
              }
          }
  
         return allPaths;
      }
  
      /**
       * Prepend end point to the path
       */
      private Stream<Deque<Archive>> makePaths(Deque<Archive> path) {
          Set<Archive> nodes = endPoints.get(path.peekFirst());
          if (nodes == null || nodes.isEmpty()) {
              return Stream.of(new LinkedList<>(path));
          } else {
              return nodes.stream().map(n -> {
                  Deque<Archive> newPath = new LinkedList<>();
                  newPath.addFirst(n);
                  newPath.addAll(path);
                  return newPath;
              });
          }
      }
  }
  