Java 类com.intellij.util.graph.DFSTBuilder 实例源码

项目：intellij-ce-playground 文件：JarsBuilder.java

@Nullable
private JarInfo[] sortJars() {
  final DFSTBuilder<JarInfo> builder = new DFSTBuilder<JarInfo>(GraphGenerator.create(CachingSemiGraph.create(new JarsGraph())));
  if (!builder.isAcyclic()) {
    final Pair<JarInfo, JarInfo> dependency = builder.getCircularDependency();
    String message = "Cannot build: circular dependency found between '" + dependency.getFirst().getPresentableDestination() +
                     "' and '" + dependency.getSecond().getPresentableDestination() + "'";
    myContext.processMessage(new CompilerMessage(IncArtifactBuilder.BUILDER_NAME, BuildMessage.Kind.ERROR, message));
    return null;
  }

  JarInfo[] jars = myJarsToBuild.toArray(new JarInfo[myJarsToBuild.size()]);
  Arrays.sort(jars, builder.comparator());
  jars = ArrayUtil.reverseArray(jars);
  return jars;
}

项目：intellij-ce-playground 文件：LoopAnalyzer.java

static int[] calcInLoop(ControlFlow controlFlow) {
  final int[] loop = new int[controlFlow.getInstructionCount()]; // loop[i] = loop number(strongly connected component number) of i-th instruction or 0 if outside loop

  MyGraph graph = new MyGraph(controlFlow);
  final DFSTBuilder<Instruction> builder = new DFSTBuilder<Instruction>(graph);
  TIntArrayList sccs = builder.getSCCs();
  sccs.forEach(new TIntProcedure() {
    private int myTNumber;
    private int component;

    @Override
    public boolean execute(int size) {
      int value = size > 1 ? ++component : 0;
      for (int i = 0; i < size; i++) {
        Instruction instruction = builder.getNodeByTNumber(myTNumber + i);
        loop[instruction.getIndex()] = value;
      }
      myTNumber += size;
      return true;
    }
  });

  return loop;
}

项目：intellij-ce-playground 文件：CyclicDependenciesUtil.java

public static <Node> List<Chunk<Node>> buildChunks(Graph<Node> graph) {
  final DFSTBuilder<Node> dfstBuilder = new DFSTBuilder<Node>(graph);
  final TIntArrayList sccs = dfstBuilder.getSCCs();
  final List<Chunk<Node>> chunks = new ArrayList<Chunk<Node>>();
  sccs.forEach(new TIntProcedure() {
    int myTNumber = 0;
    public boolean execute(int size) {
      Set<Node> packs = new LinkedHashSet<Node>();
      for (int j = 0; j < size; j++) {
        packs.add(dfstBuilder.getNodeByTNumber(myTNumber + j));
      }
      chunks.add(new Chunk<Node>(packs));
      myTNumber += size;
      return true;
    }
  });

  return chunks;
}

项目：intellij-ce-playground 文件：ConversionServiceImpl.java

private static List<ConversionRunner> createConversionRunners(ConversionContextImpl context, final Set<String> performedConversionIds) {
  List<ConversionRunner> runners = new ArrayList<ConversionRunner>();
  final ConverterProvider[] providers = ConverterProvider.EP_NAME.getExtensions();
  for (ConverterProvider provider : providers) {
    if (!performedConversionIds.contains(provider.getId())) {
      runners.add(new ConversionRunner(provider, context));
    }
  }
  final CachingSemiGraph<ConverterProvider> graph = CachingSemiGraph.create(new ConverterProvidersGraph(providers));
  final DFSTBuilder<ConverterProvider> builder = new DFSTBuilder<ConverterProvider>(GraphGenerator.create(graph));
  if (!builder.isAcyclic()) {
    final Pair<ConverterProvider,ConverterProvider> pair = builder.getCircularDependency();
    LOG.error("cyclic dependencies between converters: " + pair.getFirst().getId() + " and " + pair.getSecond().getId());
  }
  final Comparator<ConverterProvider> comparator = builder.comparator();
  Collections.sort(runners, new Comparator<ConversionRunner>() {
    @Override
    public int compare(ConversionRunner o1, ConversionRunner o2) {
      return comparator.compare(o1.getProvider(), o2.getProvider());
    }
  });
  return runners;
}

项目：tools-idea 文件：JarsBuilder.java

@Nullable
private JarInfo[] sortJars() {
  final DFSTBuilder<JarInfo> builder = new DFSTBuilder<JarInfo>(GraphGenerator.create(CachingSemiGraph.create(new JarsGraph())));
  if (!builder.isAcyclic()) {
    final Pair<JarInfo, JarInfo> dependency = builder.getCircularDependency();
    String message = "Cannot build: circular dependency found between '" + dependency.getFirst().getPresentableDestination() +
                     "' and '" + dependency.getSecond().getPresentableDestination() + "'";
    myContext.processMessage(new CompilerMessage(IncArtifactBuilder.BUILDER_NAME, BuildMessage.Kind.ERROR, message));
    return null;
  }

  JarInfo[] jars = myJarsToBuild.toArray(new JarInfo[myJarsToBuild.size()]);
  Arrays.sort(jars, builder.comparator());
  jars = ArrayUtil.reverseArray(jars);
  return jars;
}

项目：tools-idea 文件：CyclicDependenciesUtil.java

public static <Node> List<Chunk<Node>> buildChunks(Graph<Node> graph) {
  final DFSTBuilder<Node> dfstBuilder = new DFSTBuilder<Node>(graph);
  final TIntArrayList sccs = dfstBuilder.getSCCs();
  final List<Chunk<Node>> chunks = new ArrayList<Chunk<Node>>();
  sccs.forEach(new TIntProcedure() {
    int myTNumber = 0;
    public boolean execute(int size) {
      Set<Node> packs = new LinkedHashSet<Node>();
      for (int j = 0; j < size; j++) {
        packs.add(dfstBuilder.getNodeByTNumber(myTNumber + j));
      }
      chunks.add(new Chunk<Node>(packs));
      myTNumber += size;
      return true;
    }
  });

  return chunks;
}

项目：tools-idea 文件：JarsBuilder.java

@Nullable
private JarInfo[] sortJars() {
  final DFSTBuilder<JarInfo> builder = new DFSTBuilder<JarInfo>(GraphGenerator.create(CachingSemiGraph.create(new JarsGraph())));
  if (!builder.isAcyclic()) {
    final Pair<JarInfo, JarInfo> dependency = builder.getCircularDependency();
    String message = CompilerBundle.message("packaging.compiler.error.cannot.build.circular.dependency.found.between.0.and.1",
                                            dependency.getFirst().getPresentableDestination(),
                                            dependency.getSecond().getPresentableDestination());
    myContext.addMessage(CompilerMessageCategory.ERROR, message, null, -1, -1);
    return null;
  }

  JarInfo[] jars = myJarsToBuild.toArray(new JarInfo[myJarsToBuild.size()]);
  Arrays.sort(jars, builder.comparator());
  jars = ArrayUtil.reverseArray(jars);
  return jars;
}

项目：tools-idea 文件：PluginManagerCore.java

static Comparator<IdeaPluginDescriptor> getPluginDescriptorComparator(Map<PluginId, IdeaPluginDescriptorImpl> idToDescriptorMap) {
  final Graph<PluginId> graph = createPluginIdGraph(idToDescriptorMap);
  final DFSTBuilder<PluginId> builder = new DFSTBuilder<PluginId>(graph);
  /*
  if (!builder.isAcyclic()) {
    final Pair<String,String> circularDependency = builder.getCircularDependency();
    throw new Exception("Cyclic dependencies between plugins are not allowed: \"" + circularDependency.getFirst() + "\" and \"" + circularDependency.getSecond() + "");
  }
  */
  final Comparator<PluginId> idComparator = builder.comparator();
  return new Comparator<IdeaPluginDescriptor>() {
    @Override
    public int compare(IdeaPluginDescriptor o1, IdeaPluginDescriptor o2) {
      return idComparator.compare(o1.getPluginId(), o2.getPluginId());
    }
  };
}

项目：tools-idea 文件：ConversionServiceImpl.java

private static List<ConversionRunner> createConversionRunners(ConversionContextImpl context, final Set<String> performedConversionIds) {
  List<ConversionRunner> runners = new ArrayList<ConversionRunner>();
  final ConverterProvider[] providers = ConverterProvider.EP_NAME.getExtensions();
  for (ConverterProvider provider : providers) {
    if (!performedConversionIds.contains(provider.getId())) {
      runners.add(new ConversionRunner(provider, context));
    }
  }
  final CachingSemiGraph<ConverterProvider> graph = CachingSemiGraph.create(new ConverterProvidersGraph(providers));
  final DFSTBuilder<ConverterProvider> builder = new DFSTBuilder<ConverterProvider>(GraphGenerator.create(graph));
  if (!builder.isAcyclic()) {
    final Pair<ConverterProvider,ConverterProvider> pair = builder.getCircularDependency();
    LOG.error("cyclic dependencies between converters: " + pair.getFirst().getId() + " and " + pair.getSecond().getId());
  }
  final Comparator<ConverterProvider> comparator = builder.comparator();
  Collections.sort(runners, new Comparator<ConversionRunner>() {
    @Override
    public int compare(ConversionRunner o1, ConversionRunner o2) {
      return comparator.compare(o1.getProvider(), o2.getProvider());
    }
  });
  return runners;
}

项目：consulo 文件：ArchivesBuilder.java

@Nullable
private ArchivePackageInfo[] sortArchives() {
  final DFSTBuilder<ArchivePackageInfo> builder = new DFSTBuilder<>(GraphGenerator.create(CachingSemiGraph.create(new ArchivesGraph())));
  if (!builder.isAcyclic()) {
    final Pair<ArchivePackageInfo, ArchivePackageInfo> dependency = builder.getCircularDependency();
    String message = CompilerBundle
            .message("packaging.compiler.error.cannot.build.circular.dependency.found.between.0.and.1", dependency.getFirst().getPresentableDestination(),
                     dependency.getSecond().getPresentableDestination());
    myContext.addMessage(CompilerMessageCategory.ERROR, message, null, -1, -1);
    return null;
  }

  ArchivePackageInfo[] archives = myArchivesToBuild.toArray(new ArchivePackageInfo[myArchivesToBuild.size()]);
  Arrays.sort(archives, builder.comparator());
  archives = ArrayUtil.reverseArray(archives);
  return archives;
}

项目：consulo-java 文件：CyclicDependenciesUtil.java

public static <Node> List<Chunk<Node>> buildChunks(Graph<Node> graph) {
  final DFSTBuilder<Node> dfstBuilder = new DFSTBuilder<Node>(graph);
  final TIntArrayList sccs = dfstBuilder.getSCCs();
  final List<Chunk<Node>> chunks = new ArrayList<Chunk<Node>>();
  sccs.forEach(new TIntProcedure() {
    int myTNumber = 0;
    public boolean execute(int size) {
      Set<Node> packs = new LinkedHashSet<Node>();
      for (int j = 0; j < size; j++) {
        packs.add(dfstBuilder.getNodeByTNumber(myTNumber + j));
      }
      chunks.add(new Chunk<Node>(packs));
      myTNumber += size;
      return true;
    }
  });

  return chunks;
}

项目：intellij-ce-playground 文件：ArtifactSorter.java

private List<JpsArtifact> doGetSortedArtifacts() {
  GraphGenerator<JpsArtifact> graph = createArtifactsGraph();
  DFSTBuilder<JpsArtifact> builder = new DFSTBuilder<JpsArtifact>(graph);
  List<JpsArtifact> names = new ArrayList<JpsArtifact>();
  names.addAll(graph.getNodes());
  Collections.sort(names, builder.comparator());
  return names;
}

项目：intellij-ce-playground 文件：FrameworkSupportUtil.java

public static Comparator<FrameworkSupportInModuleProvider> getFrameworkSupportProvidersComparator(final List<FrameworkSupportInModuleProvider> types) {
  DFSTBuilder<FrameworkSupportInModuleProvider>
    builder = new DFSTBuilder<FrameworkSupportInModuleProvider>(GraphGenerator.create(CachingSemiGraph.create(new ProvidersGraph(types))));
  if (!builder.isAcyclic()) {
    Couple<FrameworkSupportInModuleProvider> pair = builder.getCircularDependency();
    LOG.error("Circular dependency between types '" + pair.getFirst().getFrameworkType().getId() + "' and '" + pair.getSecond().getFrameworkType().getId() + "' was found.");
  }

  return builder.comparator();
}

项目：intellij-ce-playground 文件：ModifiableModelCommitter.java

private static List<RootModelImpl> getSortedChangedModels(Collection<ModifiableRootModel> rootModels, ModifiableModuleModel moduleModel) {
  List<RootModelImpl> result = ContainerUtil.newArrayListWithCapacity(rootModels.size());

  for (ModifiableRootModel model : rootModels) {
    RootModelImpl rootModel = (RootModelImpl)model;
    if (rootModel.isChanged()) {
      result.add(rootModel);
    }
  }

  DFSTBuilder<RootModelImpl> builder = createDFSTBuilder(result, moduleModel);
  Collections.sort(result, builder.comparator());

  return result;
}

项目：intellij-ce-playground 文件：InspectionProfileImpl.java

private boolean initialize(@Nullable Project project) {
  if (myBaseProfile != null) {
    myBaseProfile.initInspectionTools(project);
  }

  final List<InspectionToolWrapper> tools;
  try {
    tools = createTools(project);
  }
  catch (ProcessCanceledException ignored) {
    return false;
  }
  final Map<String, List<String>> dependencies = new HashMap<String, List<String>>();
  for (InspectionToolWrapper toolWrapper : tools) {
    addTool(project, toolWrapper, dependencies);
  }
  final GraphGenerator<String> graphGenerator = GraphGenerator.create(CachingSemiGraph.create(new GraphGenerator.SemiGraph<String>() {
    @Override
    public Collection<String> getNodes() {
      return dependencies.keySet();
    }

    @Override
    public Iterator<String> getIn(String n) {
      return dependencies.get(n).iterator();
    }
  }));

  DFSTBuilder<String> builder = new DFSTBuilder<String>(graphGenerator);
  if (builder.isAcyclic()) {
    final List<String> scopes = builder.getSortedNodes();
    myScopesOrder = ArrayUtil.toStringArray(scopes);
  }

  if (mySource != null) {
    copyToolsConfigurations(mySource, project);
  }
  return true;
}

项目：intellij-ce-playground 文件：ModulesDependenciesPanel.java

private void setSplitterProportion() {
  if (mySplitter == null){
    return;
  }
  myModulesGraph = buildGraph();
  DFSTBuilder<Module> builder = new DFSTBuilder<Module>(myModulesGraph);
  if (builder.isAcyclic()){
    mySplitter.setProportion(1.f);
  } else {
    mySplitter.setProportion(0.5f);
  }
}

项目：tools-idea 文件：ArtifactSorter.java

private List<JpsArtifact> doGetSortedArtifacts() {
  GraphGenerator<JpsArtifact> graph = createArtifactsGraph();
  DFSTBuilder<JpsArtifact> builder = new DFSTBuilder<JpsArtifact>(graph);
  builder.buildDFST();
  List<JpsArtifact> names = new ArrayList<JpsArtifact>();
  names.addAll(graph.getNodes());
  Collections.sort(names, builder.comparator());
  return names;
}

项目：tools-idea 文件：FrameworkSupportUtil.java

public static Comparator<FrameworkSupportInModuleProvider> getFrameworkSupportProvidersComparator(final List<FrameworkSupportInModuleProvider> types) {
  DFSTBuilder<FrameworkSupportInModuleProvider>
    builder = new DFSTBuilder<FrameworkSupportInModuleProvider>(GraphGenerator.create(CachingSemiGraph.create(new ProvidersGraph(types))));
  if (!builder.isAcyclic()) {
    Pair<FrameworkSupportInModuleProvider, FrameworkSupportInModuleProvider> pair = builder.getCircularDependency();
    LOG.error("Circular dependency between types '" + pair.getFirst().getFrameworkType().getId() + "' and '" + pair.getSecond().getFrameworkType().getId() + "' was found.");
  }

  return builder.comparator();
}

项目：tools-idea 文件：ArtifactSortingUtilImpl.java

private List<String> doGetSortedArtifacts() {
  GraphGenerator<String> graph = createArtifactsGraph();
  DFSTBuilder<String> builder = new DFSTBuilder<String>(graph);
  builder.buildDFST();
  List<String> names = new ArrayList<String>();
  names.addAll(graph.getNodes());
  Collections.sort(names, builder.comparator());
  return names;
}

项目：tools-idea 文件：ModulesDependenciesPanel.java

private void setSplitterProportion() {
  if (mySplitter == null){
    return;
  }
  myModulesGraph = buildGraph();
  DFSTBuilder<Module> builder = new DFSTBuilder<Module>(myModulesGraph);
  builder.buildDFST();
  if (builder.isAcyclic()){
    mySplitter.setProportion(1.f);
  } else {
    mySplitter.setProportion(0.5f);
  }
}

项目：consulo 文件：ArtifactSortingUtilImpl.java

private List<String> doGetSortedArtifacts() {
  GraphGenerator<String> graph = createArtifactsGraph();
  DFSTBuilder<String> builder = new DFSTBuilder<String>(graph);
  List<String> names = new ArrayList<String>();
  names.addAll(graph.getNodes());
  Collections.sort(names, builder.comparator());
  return names;
}

项目：consulo 文件：ModulesDependenciesPanel.java

private void setSplitterProportion() {
  if (mySplitter == null){
    return;
  }
  myModulesGraph = buildGraph();
  DFSTBuilder<Module> builder = new DFSTBuilder<Module>(myModulesGraph);
  if (builder.isAcyclic()){
    mySplitter.setProportion(1.f);
  } else {
    mySplitter.setProportion(0.5f);
  }
}

项目：consulo-java 文件：LoopAnalyzer.java

static int[] calcInLoop(ControlFlow controlFlow)
{
    final int[] loop = new int[controlFlow.getInstructionCount()]; // loop[i] = loop number(strongly connected component number) of i-th instruction or 0 if outside loop

    MyGraph graph = new MyGraph(controlFlow);
    final DFSTBuilder<Instruction> builder = new DFSTBuilder<>(graph);
    TIntArrayList sccs = builder.getSCCs();
    sccs.forEach(new TIntProcedure()
    {
        private int myTNumber;
        private int component;

        @Override
        public boolean execute(int size)
        {
            int value = size > 1 ? ++component : 0;
            for(int i = 0; i < size; i++)
            {
                Instruction instruction = builder.getNodeByTNumber(myTNumber + i);
                loop[instruction.getIndex()] = value;
            }
            myTNumber += size;
            return true;
        }
    });

    return loop;
}

项目：intellij-ce-playground 文件：ModuleManagerImpl.java

private Comparator<Module> moduleDependencyComparator() {
  DFSTBuilder<Module> builder = new DFSTBuilder<Module>(moduleGraph(true));
  return builder.comparator();
}

项目：tools-idea 文件：BuildTargetIndexImpl.java

private synchronized void initializeChunks(@NotNull CompileContext context) {
  if (myTargetChunks != null) {
    return;
  }

  final List<? extends BuildTarget<?>> allTargets = getAllTargets();
  TargetOutputIndex outputIndex = new TargetOutputIndexImpl(allTargets, context);
  for (BuildTarget<?> target : allTargets) {
    myDependencies.put(target, target.computeDependencies(this, outputIndex));
  }

  GraphGenerator<BuildTarget<?>>
    graph = GraphGenerator.create(CachingSemiGraph.create(new GraphGenerator.SemiGraph<BuildTarget<?>>() {
    @Override
    public Collection<BuildTarget<?>> getNodes() {
      return myAllTargets;
    }

    @Override
    public Iterator<BuildTarget<?>> getIn(BuildTarget<?> n) {
      return myDependencies.get(n).iterator();
    }
  }));

  final DFSTBuilder<BuildTarget<?>> builder = new DFSTBuilder<BuildTarget<?>>(graph);
  final TIntArrayList sccs = builder.getSCCs();

  myTargetChunks = new ArrayList<BuildTargetChunk>(sccs.size());
  sccs.forEach(new TIntProcedure() {
    int myTNumber = 0;
    public boolean execute(int size) {
      final Set<BuildTarget<?>> chunkNodes = new LinkedHashSet<BuildTarget<?>>();
      for (int j = 0; j < size; j++) {
        final BuildTarget<?> node = builder.getNodeByTNumber(myTNumber + j);
        chunkNodes.add(node);
      }
      myTargetChunks.add(new BuildTargetChunk(chunkNodes));

      myTNumber += size;
      return true;
    }
  });
}

项目：tools-idea 文件：ModuleManagerImpl.java

private Comparator<Module> moduleDependencyComparator() {
  DFSTBuilder<Module> builder = new DFSTBuilder<Module>(moduleGraph(true));
  return builder.comparator();
}

项目：tools-idea 文件：ModifiableModelCommitter.java

private static void sortRootModels(List<RootModelImpl> rootModels, final ModifiableModuleModel moduleModel) {
  DFSTBuilder<RootModelImpl> builder = createDFSTBuilder(rootModels, moduleModel);

  final Comparator<RootModelImpl> comparator = builder.comparator();
  Collections.sort(rootModels, comparator);
}

项目：consulo 文件：ModifiableModelCommitter.java

private static void sortRootModels(List<RootModelImpl> rootModels, final ModifiableModuleModel moduleModel) {
  DFSTBuilder<RootModelImpl> builder = createDFSTBuilder(rootModels, moduleModel);

  final Comparator<RootModelImpl> comparator = builder.comparator();
  Collections.sort(rootModels, comparator);
}

项目：consulo 文件：InspectionProfileImpl.java

private boolean initialize(@Nullable Project project) {
  if (myBaseProfile != null) {
    myBaseProfile.initInspectionTools(project);
  }

  final List<InspectionToolWrapper> tools;
  try {
    tools = createTools(project);
  }
  catch (ProcessCanceledException ignored) {
    return false;
  }
  final Map<String, List<String>> dependencies = new HashMap<String, List<String>>();
  for (InspectionToolWrapper toolWrapper : tools) {
    final String shortName = toolWrapper.getShortName();
    HighlightDisplayKey key = HighlightDisplayKey.find(shortName);
    if (key == null) {
      final InspectionEP extension = toolWrapper.getExtension();
      Computable<String> computable = extension == null ? new Computable.PredefinedValueComputable<String>(toolWrapper.getDisplayName()) : new Computable<String>() {
        @Override
        public String compute() {
          return extension.getDisplayName();
        }
      };
      if (toolWrapper instanceof LocalInspectionToolWrapper) {
        key = HighlightDisplayKey.register(shortName, computable, ((LocalInspectionToolWrapper)toolWrapper).getID(),
                                           ((LocalInspectionToolWrapper)toolWrapper).getAlternativeID());
      }
      else {
        key = HighlightDisplayKey.register(shortName, computable);
      }
    }

    LOG.assertTrue(key != null, shortName + " ; number of initialized tools: " + myTools.size());
    HighlightDisplayLevel level = myBaseProfile != null ? myBaseProfile.getErrorLevel(key, project) : toolWrapper.getDefaultLevel();
    boolean enabled = myBaseProfile != null ? myBaseProfile.isToolEnabled(key) : toolWrapper.isEnabledByDefault();
    final ToolsImpl toolsList = new ToolsImpl(toolWrapper, level, !myLockedProfile && enabled, enabled);
    final Element element = myUninstalledInspectionsSettings.remove(shortName);
    try {
      if (element != null) {
        toolsList.readExternal(element, this, dependencies);
      }
      else if (!myUninstalledInspectionsSettings.containsKey(InspectionElementsMerger.getMergedMarkerName(shortName))) {
        final InspectionElementsMerger merger = getMergers().get(shortName);
        if (merger != null) {
          final Element merged = merger.merge(myUninstalledInspectionsSettings);
          if (merged != null) {
            toolsList.readExternal(merged, this, dependencies);
          }
        }
      }
    }
    catch (InvalidDataException e) {
      LOG.error("Can't read settings for " + toolWrapper, e);
    }
    myTools.put(toolWrapper.getShortName(), toolsList);
  }
  final GraphGenerator<String> graphGenerator = GraphGenerator.create(CachingSemiGraph.create(new GraphGenerator.SemiGraph<String>() {
    @Override
    public Collection<String> getNodes() {
      return dependencies.keySet();
    }

    @Override
    public Iterator<String> getIn(String n) {
      return dependencies.get(n).iterator();
    }
  }));

  DFSTBuilder<String> builder = new DFSTBuilder<String>(graphGenerator);
  if (builder.isAcyclic()) {
    final List<String> scopes = builder.getSortedNodes();
    myScopesOrder = ArrayUtil.toStringArray(scopes);
  }

  if (mySource != null) {
    copyToolsConfigurations(mySource, project);
  }
  return true;
}