yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.parser.util;
   9
  10 import com.google.common.annotations.VisibleForTesting;
  11 import com.google.common.base.Function;
  12 import com.google.common.collect.Lists;
  13 import com.google.common.collect.Maps;
  14 import com.google.common.collect.Sets;
  15 import java.net.URI;
  16 import java.util.Arrays;
  17 import java.util.Collection;
  18 import java.util.Date;
  19 import java.util.HashMap;
  20 import java.util.List;
  21 import java.util.Map;
  22 import java.util.Objects;
  23 import java.util.Set;
  24 import org.opendaylight.yangtools.yang.common.SimpleDateFormatUtil;
  25 import org.opendaylight.yangtools.yang.common.YangVersion;
  26 import org.opendaylight.yangtools.yang.model.api.Module;
  27 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  28 import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node;
  29 import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl;
  30 import org.slf4j.Logger;
  31 import org.slf4j.LoggerFactory;
  32
  33 /**
  34  * Creates a module dependency graph from provided {@link Module}s and
  35  * provides a {@link #sort(Module...)} method. It is topological sort and
  36  * returns modules in order in which they should be processed (e.g. if A imports
  37  * B, sort returns {B, A}).
  38  */
  39 public final class ModuleDependencySort {
  40
  41     private static final Date DEFAULT_REVISION = SimpleDateFormatUtil.DEFAULT_DATE_REV;
  42     private static final Logger LOGGER = LoggerFactory.getLogger(ModuleDependencySort.class);
  43     private static final Function<Node, Module> TOPOLOGY_FUNCTION = input -> {
  44         if (input == null) {
  45             return null;
  46         }
  47         return ((ModuleNodeImpl) input).getReference();
  48     };
  49
  50     /**
  51      * It is not desirable to instance this class
  52      */
  53     private ModuleDependencySort() {
  54     }
  55
  56     /**
  57      * Topological sort of module dependency graph.
  58      *
  59      * @param modules YANG modules
  60      * @return Sorted list of Modules. Modules can be further processed in
  61      *         returned order.
  62      */
  63     public static List<Module> sort(final Module... modules) {
  64         return sort(Arrays.asList(modules));
  65     }
  66
  67     /**
  68      * Topological sort of module dependency graph.
  69      *
  70      * @param modules YANG modules
  71      * @return Sorted list of Modules. Modules can be further processed in
  72      *         returned order.
  73      */
  74     public static List<Module> sort(final Iterable<Module> modules) {
  75         final List<TopologicalSort.Node> sorted = sortInternal(modules);
  76         // Cast to Module from Node and return
  77         return Lists.transform(sorted, TOPOLOGY_FUNCTION);
  78     }
  79
  80     private static List<TopologicalSort.Node> sortInternal(final Iterable<Module> modules) {
  81         final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = createModuleGraph(modules);
  82
  83         final Set<TopologicalSort.Node> nodes = Sets.newHashSet();
  84         for (final Map<Date, ModuleNodeImpl> map : moduleGraph.values()) {
  85             for (final ModuleNodeImpl node : map.values()) {
  86                 nodes.add(node);
  87             }
  88         }
  89
  90         return TopologicalSort.sort(nodes);
  91     }
  92
  93     @VisibleForTesting
  94     static Map<String, Map<Date, ModuleNodeImpl>> createModuleGraph(final Iterable<Module> builders) {
  95         final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = Maps.newHashMap();
  96
  97         processModules(moduleGraph, builders);
  98         processDependencies(moduleGraph, builders);
  99
 100         return moduleGraph;
 101     }
 102
 103     /**
 104      * Extract module:revision from module builders
 105      */
 106     private static void processDependencies(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 107             final Iterable<Module> mmbs) {
 108         final Map<URI, Module> allNS = new HashMap<>();
 109
 110         // Create edges in graph
 111         for (final Module module : mmbs) {
 112             final Map<String, Date> imported = Maps.newHashMap();
 113
 114             String fromName;
 115             Date fromRevision;
 116             Collection<ModuleImport> imports;
 117             URI ns;
 118
 119             fromName = module.getName();
 120             fromRevision = module.getRevision();
 121             imports = module.getImports();
 122             ns = module.getNamespace();
 123
 124             // check for existence of module with same namespace
 125             if (allNS.containsKey(ns)) {
 126                 final Module mod = allNS.get(ns);
 127                 final String name = mod.getName();
 128                 final Date revision = mod.getRevision();
 129                 if (!fromName.equals(name)) {
 130                     LOGGER.warn(
 131                             "Error while sorting module [{}, {}]: module with same namespace ({}) already loaded: [{}, {}]",
 132                             fromName, fromRevision, ns, name, revision);
 133                 }
 134             } else {
 135                 allNS.put(ns, module);
 136             }
 137
 138             // no need to check if other Type of object, check is performed in
 139             // process modules
 140
 141             if (fromRevision == null) {
 142                 fromRevision = DEFAULT_REVISION;
 143             }
 144
 145             for (final ModuleImport imprt : imports) {
 146                 final String toName = imprt.getModuleName();
 147                 final Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION : imprt.getRevision();
 148
 149                 final ModuleNodeImpl from = moduleGraph.get(fromName).get(fromRevision);
 150
 151                 final ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName, toRevision);
 152
 153                 /*
 154                  * If it is an yang 1 module, check imports: If module is imported twice with different
 155                  * revisions then throw exception
 156                  */
 157                 if (YangVersion.VERSION_1.toString().equals(module.getYangVersion()) && imported.get(toName) != null
 158                         && !imported.get(toName).equals(toRevision) && !imported.get(toName).equals(DEFAULT_REVISION)
 159                         && !toRevision.equals(DEFAULT_REVISION)) {
 160                     ex(String.format("Module:%s imported twice with different revisions:%s, %s", toName,
 161                             formatRevDate(imported.get(toName)), formatRevDate(toRevision)));
 162                 }
 163
 164                 imported.put(toName, toRevision);
 165
 166                 from.addEdge(to);
 167             }
 168         }
 169     }
 170
 171     /**
 172      * Get imported module by its name and revision from moduleGraph
 173      */
 174     private static ModuleNodeImpl getModuleByNameAndRevision(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 175             final String fromName, final Date fromRevision, final String toName, final Date toRevision) {
 176         ModuleNodeImpl to = null;
 177
 178         if (moduleGraph.get(toName) == null || !moduleGraph.get(toName).containsKey(toRevision)) {
 179             // If revision is not specified in import, but module exists
 180             // with different revisions, take first
 181             if (moduleGraph.get(toName) != null && !moduleGraph.get(toName).isEmpty()
 182                     && toRevision.equals(DEFAULT_REVISION)) {
 183                 to = moduleGraph.get(toName).values().iterator().next();
 184                 LOGGER.trace(String
 185                         .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort",
 186                                 toName, formatRevDate(toRevision), fromName, formatRevDate(fromRevision), to.getName(),
 187                                 formatRevDate(to.getRevision())));
 188             } else {
 189                 LOGGER.warn(String.format("Not existing module imported:%s:%s by:%s:%s", toName,
 190                         formatRevDate(toRevision), fromName, formatRevDate(fromRevision)));
 191                 LOGGER.warn("Available models: {}", moduleGraph);
 192                 ex(String.format("Not existing module imported:%s:%s by:%s:%s", toName, formatRevDate(toRevision),
 193                         fromName, formatRevDate(fromRevision)));
 194             }
 195         } else {
 196             to = moduleGraph.get(toName).get(toRevision);
 197         }
 198         return to;
 199     }
 200
 201     private static void ex(final String message) {
 202         throw new YangValidationException(message);
 203     }
 204
 205     /**
 206      * Extract dependencies from module builders or modules to fill dependency
 207      * graph
 208      */
 209     private static void processModules(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 210             final Iterable<Module> modules) {
 211
 212         // Process nodes
 213         for (final Module momb : modules) {
 214
 215             final String name = momb.getName();
 216             Date rev = momb.getRevision();
 217             if (rev == null) {
 218                 rev = DEFAULT_REVISION;
 219             }
 220
 221             if (moduleGraph.get(name) == null) {
 222                 moduleGraph.put(name, Maps.newHashMap());
 223             }
 224
 225             if (moduleGraph.get(name).get(rev) != null) {
 226                 ex(String.format("Module:%s with revision:%s declared twice", name, formatRevDate(rev)));
 227             }
 228
 229             moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev, momb));
 230         }
 231     }
 232
 233     private static String formatRevDate(final Date rev) {
 234         return rev.equals(DEFAULT_REVISION) ? "default" : SimpleDateFormatUtil.getRevisionFormat().format(rev);
 235     }
 236
 237     @VisibleForTesting
 238     static class ModuleNodeImpl extends NodeImpl {
 239         private final String name;
 240         private final Date revision;
 241         private final Module originalObject;
 242
 243         public ModuleNodeImpl(final String name, final Date revision, final Module module) {
 244             this.name = name;
 245             this.revision = revision;
 246             this.originalObject = module;
 247         }
 248
 249         public String getName() {
 250             return name;
 251         }
 252
 253         public Date getRevision() {
 254             return revision;
 255         }
 256
 257         @Override
 258         public int hashCode() {
 259             final int prime = 31;
 260             int result = 1;
 261             result = prime * result + Objects.hashCode(name);
 262             result = prime * result + Objects.hashCode(revision);
 263             return result;
 264         }
 265
 266         @Override
 267         public boolean equals(final Object obj) {
 268             if (this == obj) {
 269                 return true;
 270             }
 271             if (obj == null) {
 272                 return false;
 273             }
 274             if (getClass() != obj.getClass()) {
 275                 return false;
 276             }
 277             final ModuleNodeImpl other = (ModuleNodeImpl) obj;
 278             if (name == null) {
 279                 if (other.name != null) {
 280                     return false;
 281                 }
 282             } else if (!name.equals(other.name)) {
 283                 return false;
 284             }
 285             if (revision == null) {
 286                 if (other.revision != null) {
 287                     return false;
 288                 }
 289             } else if (!revision.equals(other.revision)) {
 290                 return false;
 291             }
 292             return true;
 293         }
 294
 295         @Override
 296         public String toString() {
 297             return "Module [name=" + name + ", revision=" + formatRevDate(revision) + "]";
 298         }
 299
 300         public Module getReference() {
 301             return originalObject;
 302         }
 303
 304     }
 305
 306 }