X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=yang%2Fyang-model-spi%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Fyang%2Fmodel%2Fspi%2FModuleDependencySort.java;fp=yang%2Fyang-model-spi%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Fyang%2Fmodel%2Fspi%2FModuleDependencySort.java;h=0000000000000000000000000000000000000000;hb=b67b827e357ae40ae26e4bfec35b76ef5ee67967;hp=599cd74a7f7d942967bd9b8f8885d82e3d2c2063;hpb=9728fe497bcb7349f7e6ef9d3d984202d7ac07e7;p=yangtools.git diff --git a/yang/yang-model-spi/src/main/java/org/opendaylight/yangtools/yang/model/spi/ModuleDependencySort.java b/yang/yang-model-spi/src/main/java/org/opendaylight/yangtools/yang/model/spi/ModuleDependencySort.java deleted file mode 100644 index 599cd74a7f..0000000000 --- a/yang/yang-model-spi/src/main/java/org/opendaylight/yangtools/yang/model/spi/ModuleDependencySort.java +++ /dev/null @@ -1,271 +0,0 @@ -/* - * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. - * - * This program and the accompanying materials are made available under the - * terms of the Eclipse Public License v1.0 which accompanies this distribution, - * and is available at http://www.eclipse.org/legal/epl-v10.html - */ -package org.opendaylight.yangtools.yang.model.spi; - -import com.google.common.annotations.Beta; -import com.google.common.collect.HashBasedTable; -import com.google.common.collect.Lists; -import com.google.common.collect.Table; -import java.util.Arrays; -import java.util.Collection; -import java.util.HashMap; -import java.util.HashSet; -import java.util.LinkedHashSet; -import java.util.List; -import java.util.Map; -import java.util.Objects; -import java.util.Optional; -import org.opendaylight.yangtools.util.TopologicalSort; -import org.opendaylight.yangtools.util.TopologicalSort.Node; -import org.opendaylight.yangtools.util.TopologicalSort.NodeImpl; -import org.opendaylight.yangtools.yang.common.Revision; -import org.opendaylight.yangtools.yang.common.XMLNamespace; -import org.opendaylight.yangtools.yang.common.YangVersion; -import org.opendaylight.yangtools.yang.model.api.Module; -import org.opendaylight.yangtools.yang.model.api.ModuleImport; -import org.opendaylight.yangtools.yang.model.api.Submodule; -import org.slf4j.Logger; -import org.slf4j.LoggerFactory; - -/** - * Creates a module dependency graph from provided {@link Module}s and provides a {@link #sort(Collection)} method. - * It is topological sort and returns modules in order in which they should be processed (e.g. if A imports B, sort - * returns {B, A}). - */ -@Beta -public final class ModuleDependencySort { - private static final Logger LOG = LoggerFactory.getLogger(ModuleDependencySort.class); - - private ModuleDependencySort() { - // Hidden on purpose - } - - /** - * Topological sort of module dependency graph. - * - * @param modules YANG modules - * @return Sorted list of Modules. Modules can be further processed in returned order. - * @throws IllegalArgumentException when provided modules are not consistent. - */ - public static List sort(final Module... modules) { - return sort(Arrays.asList(modules)); - } - - /** - * Topological sort of module dependency graph. - * - * @param modules YANG modules - * @return Sorted list of Modules. Modules can be further processed in returned order. - * @throws IllegalArgumentException when provided modules are not consistent. - */ - public static List sort(final Collection modules) { - final List sorted = sortInternal(modules); - // Cast to Module from Node and return - return Lists.transform(sorted, input -> input == null ? null : ((ModuleNodeImpl) input).getReference()); - } - - private static List sortInternal(final Collection modules) { - final Table, ModuleNodeImpl> moduleGraph = createModuleGraph(modules); - return TopologicalSort.sort(new HashSet<>(moduleGraph.values())); - } - - private static Table, ModuleNodeImpl> createModuleGraph( - final Collection builders) { - final Table, ModuleNodeImpl> moduleGraph = HashBasedTable.create(); - - processModules(moduleGraph, builders); - processDependencies(moduleGraph, builders); - - return moduleGraph; - } - - /** - * Extract module:revision from modules. - */ - private static void processDependencies(final Table, ModuleNodeImpl> moduleGraph, - final Collection mmbs) { - final Map allNS = new HashMap<>(); - - // Create edges in graph - for (final Module module : mmbs) { - final Map> imported = new HashMap<>(); - final String fromName = module.getName(); - final XMLNamespace ns = module.getNamespace(); - final Optional fromRevision = module.getRevision(); - - // check for existence of module with same namespace - final Module prev = allNS.putIfAbsent(ns, module); - if (prev != null) { - final String name = prev.getName(); - if (!fromName.equals(name)) { - LOG.warn("Error while sorting module [{}, {}]: module with same namespace ({}) already loaded:" - + " [{}, {}]", fromName, fromRevision, ns, name, prev.getRevision()); - } - } - - // no need to check if other Type of object, check is performed in process modules - for (final ModuleImport imprt : allImports(module)) { - final String toName = imprt.getModuleName(); - final Optional toRevision = imprt.getRevision(); - - final ModuleNodeImpl from = moduleGraph.get(fromName, fromRevision); - final ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName, - toRevision); - - /* - * If it is an yang 1 module, check imports: If module is imported twice with different - * revisions then throw exception - */ - if (module.getYangVersion() == YangVersion.VERSION_1) { - final Optional impRevision = imported.get(toName); - if (impRevision != null && impRevision.isPresent() && !impRevision.equals(toRevision) - && toRevision.isPresent()) { - throw new IllegalArgumentException(String.format( - "Module:%s imported twice with different revisions:%s, %s", toName, - formatRevDate(impRevision), formatRevDate(toRevision))); - } - } - - imported.put(toName, toRevision); - - from.addEdge(to); - } - } - } - - private static Collection allImports(final Module mod) { - if (mod.getSubmodules().isEmpty()) { - return mod.getImports(); - } - - final Collection concat = new LinkedHashSet<>(); - concat.addAll(mod.getImports()); - for (Submodule sub : mod.getSubmodules()) { - concat.addAll(sub.getImports()); - } - return concat; - } - - /** - * Get imported module by its name and revision from moduleGraph. - */ - private static ModuleNodeImpl getModuleByNameAndRevision( - final Table, ModuleNodeImpl> moduleGraph, final String fromName, - final Optional fromRevision, final String toName, final Optional toRevision) { - - final ModuleNodeImpl exact = moduleGraph.get(toName, toRevision); - if (exact != null) { - return exact; - } - - // If revision is not specified in import, but module exists with different revisions, take first one - if (toRevision.isEmpty()) { - final Map, ModuleNodeImpl> modulerevs = moduleGraph.row(toName); - - if (!modulerevs.isEmpty()) { - final ModuleNodeImpl first = modulerevs.values().iterator().next(); - if (LOG.isTraceEnabled()) { - LOG.trace("Import:{}:{} by module:{}:{} does not specify revision, using:{}:{}" - + " for module dependency sort", toName, formatRevDate(toRevision), fromName, - formatRevDate(fromRevision), first.getName(), formatRevDate(first.getRevision())); - } - return first; - } - } - - LOG.warn("Not existing module imported:{}:{} by:{}:{}", toName, formatRevDate(toRevision), fromName, - formatRevDate(fromRevision)); - LOG.warn("Available models: {}", moduleGraph); - throw new IllegalArgumentException(String.format("Not existing module imported:%s:%s by:%s:%s", toName, - formatRevDate(toRevision), fromName, formatRevDate(fromRevision))); - } - - /** - * Extract dependencies from modules to fill dependency graph. - */ - private static void processModules(final Table, ModuleNodeImpl> moduleGraph, - final Iterable modules) { - - // Process nodes - for (final Module momb : modules) { - - final String name = momb.getName(); - final Optional rev = momb.getRevision(); - final Map, ModuleNodeImpl> revs = moduleGraph.row(name); - if (revs.containsKey(rev)) { - throw new IllegalArgumentException(String.format("Module:%s with revision:%s declared twice", name, - formatRevDate(rev))); - } - - revs.put(rev, new ModuleNodeImpl(name, rev.orElse(null), momb)); - } - } - - private static String formatRevDate(final Optional rev) { - return rev.map(Revision::toString).orElse("default"); - } - - private static final class ModuleNodeImpl extends NodeImpl { - private final String name; - private final Revision revision; - private final Module originalObject; - - ModuleNodeImpl(final String name, final Revision revision, final Module module) { - this.name = name; - this.revision = revision; - this.originalObject = module; - } - - String getName() { - return name; - } - - Optional getRevision() { - return Optional.ofNullable(revision); - } - - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result + Objects.hashCode(name); - result = prime * result + Objects.hashCode(revision); - return result; - } - - @Override - public boolean equals(final Object obj) { - if (this == obj) { - return true; - } - if (obj == null) { - return false; - } - if (getClass() != obj.getClass()) { - return false; - } - final ModuleNodeImpl other = (ModuleNodeImpl) obj; - if (!Objects.equals(name, other.name)) { - return false; - } - if (!Objects.equals(revision, other.revision)) { - return false; - } - return true; - } - - @Override - public String toString() { - return "Module [name=" + name + ", revision=" + formatRevDate(getRevision()) + "]"; - } - - public Module getReference() { - return originalObject; - } - } -}