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         final List<TopologicalSort.Node> sorted = sortInternal(Arrays.asList(modules));
  65         // Cast to Module from Node and return
  66         return Lists.transform(sorted, TOPOLOGY_FUNCTION);
  67     }
  68
  69     private static List<TopologicalSort.Node> sortInternal(final Iterable<Module> modules) {
  70         final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = createModuleGraph(modules);
  71
  72         final Set<TopologicalSort.Node> nodes = Sets.newHashSet();
  73         for (final Map<Date, ModuleNodeImpl> map : moduleGraph.values()) {
  74             for (final ModuleNodeImpl node : map.values()) {
  75                 nodes.add(node);
  76             }
  77         }
  78
  79         return TopologicalSort.sort(nodes);
  80     }
  81
  82     @VisibleForTesting
  83     static Map<String, Map<Date, ModuleNodeImpl>> createModuleGraph(final Iterable<Module> builders) {
  84         final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = Maps.newHashMap();
  85
  86         processModules(moduleGraph, builders);
  87         processDependencies(moduleGraph, builders);
  88
  89         return moduleGraph;
  90     }
  91
  92     /**
  93      * Extract module:revision from module builders
  94      */
  95     private static void processDependencies(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
  96             final Iterable<Module> mmbs) {
  97         final Map<URI, Module> allNS = new HashMap<>();
  98
  99         // Create edges in graph
 100         for (final Module module : mmbs) {
 101             final Map<String, Date> imported = Maps.newHashMap();
 102
 103             String fromName;
 104             Date fromRevision;
 105             Collection<ModuleImport> imports;
 106             URI ns;
 107
 108             fromName = module.getName();
 109             fromRevision = module.getRevision();
 110             imports = module.getImports();
 111             ns = module.getNamespace();
 112
 113             // check for existence of module with same namespace
 114             if (allNS.containsKey(ns)) {
 115                 final Module mod = allNS.get(ns);
 116                 final String name = mod.getName();
 117                 final Date revision = mod.getRevision();
 118                 if (!(fromName.equals(name))) {
 119                     LOGGER.warn(
 120                             "Error while sorting module [{}, {}]: module with same namespace ({}) already loaded: [{}, {}]",
 121                             fromName, fromRevision, ns, name, revision);
 122                 }
 123             } else {
 124                 allNS.put(ns, module);
 125             }
 126
 127             // no need to check if other Type of object, check is performed in
 128             // process modules
 129
 130             if (fromRevision == null) {
 131                 fromRevision = DEFAULT_REVISION;
 132             }
 133
 134             for (final ModuleImport imprt : imports) {
 135                 final String toName = imprt.getModuleName();
 136                 final Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION : imprt.getRevision();
 137
 138                 final ModuleNodeImpl from = moduleGraph.get(fromName).get(fromRevision);
 139
 140                 final ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName, toRevision);
 141
 142                 /*
 143                  * If it is an yang 1 module, check imports: If module is imported twice with different
 144                  * revisions then throw exception
 145                  */
 146                 if (YangVersion.VERSION_1.toString().equals(module.getYangVersion()) && imported.get(toName) != null
 147                         && !imported.get(toName).equals(toRevision) && !imported.get(toName).equals(DEFAULT_REVISION)
 148                         && !toRevision.equals(DEFAULT_REVISION)) {
 149                     ex(String.format("Module:%s imported twice with different revisions:%s, %s", toName,
 150                             formatRevDate(imported.get(toName)), formatRevDate(toRevision)));
 151                 }
 152
 153                 imported.put(toName, toRevision);
 154
 155                 from.addEdge(to);
 156             }
 157         }
 158     }
 159
 160     /**
 161      * Get imported module by its name and revision from moduleGraph
 162      */
 163     private static ModuleNodeImpl getModuleByNameAndRevision(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 164             final String fromName, final Date fromRevision, final String toName, final Date toRevision) {
 165         ModuleNodeImpl to = null;
 166
 167         if (moduleGraph.get(toName) == null || !moduleGraph.get(toName).containsKey(toRevision)) {
 168             // If revision is not specified in import, but module exists
 169             // with different revisions, take first
 170             if (moduleGraph.get(toName) != null && !moduleGraph.get(toName).isEmpty()
 171                     && toRevision.equals(DEFAULT_REVISION)) {
 172                 to = moduleGraph.get(toName).values().iterator().next();
 173                 LOGGER.trace(String
 174                         .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort",
 175                                 toName, formatRevDate(toRevision), fromName, formatRevDate(fromRevision), to.getName(),
 176                                 formatRevDate(to.getRevision())));
 177             } else {
 178                 LOGGER.warn(String.format("Not existing module imported:%s:%s by:%s:%s", toName,
 179                         formatRevDate(toRevision), fromName, formatRevDate(fromRevision)));
 180                 LOGGER.warn("Available models: {}", moduleGraph);
 181                 ex(String.format("Not existing module imported:%s:%s by:%s:%s", toName, formatRevDate(toRevision),
 182                         fromName, formatRevDate(fromRevision)));
 183             }
 184         } else {
 185             to = moduleGraph.get(toName).get(toRevision);
 186         }
 187         return to;
 188     }
 189
 190     private static void ex(final String message) {
 191         throw new YangValidationException(message);
 192     }
 193
 194     /**
 195      * Extract dependencies from module builders or modules to fill dependency
 196      * graph
 197      */
 198     private static void processModules(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 199             final Iterable<Module> modules) {
 200
 201         // Process nodes
 202         for (final Module momb : modules) {
 203
 204             final String name = momb.getName();
 205             Date rev = momb.getRevision();
 206             if (rev == null) {
 207                 rev = DEFAULT_REVISION;
 208             }
 209
 210             if (moduleGraph.get(name) == null) {
 211                 moduleGraph.put(name, Maps.newHashMap());
 212             }
 213
 214             if (moduleGraph.get(name).get(rev) != null) {
 215                 ex(String.format("Module:%s with revision:%s declared twice", name, formatRevDate(rev)));
 216             }
 217
 218             moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev, momb));
 219         }
 220     }
 221
 222     private static String formatRevDate(final Date rev) {
 223         return rev.equals(DEFAULT_REVISION) ? "default" : SimpleDateFormatUtil.getRevisionFormat().format(rev);
 224     }
 225
 226     @VisibleForTesting
 227     static class ModuleNodeImpl extends NodeImpl {
 228         private final String name;
 229         private final Date revision;
 230         private final Module originalObject;
 231
 232         public ModuleNodeImpl(final String name, final Date revision, final Module module) {
 233             this.name = name;
 234             this.revision = revision;
 235             this.originalObject = module;
 236         }
 237
 238         public String getName() {
 239             return name;
 240         }
 241
 242         public Date getRevision() {
 243             return revision;
 244         }
 245
 246         @Override
 247         public int hashCode() {
 248             final int prime = 31;
 249             int result = 1;
 250             result = prime * result + Objects.hashCode(name);
 251             result = prime * result + Objects.hashCode(revision);
 252             return result;
 253         }
 254
 255         @Override
 256         public boolean equals(final Object obj) {
 257             if (this == obj) {
 258                 return true;
 259             }
 260             if (obj == null) {
 261                 return false;
 262             }
 263             if (getClass() != obj.getClass()) {
 264                 return false;
 265             }
 266             final ModuleNodeImpl other = (ModuleNodeImpl) obj;
 267             if (name == null) {
 268                 if (other.name != null) {
 269                     return false;
 270                 }
 271             } else if (!name.equals(other.name)) {
 272                 return false;
 273             }
 274             if (revision == null) {
 275                 if (other.revision != null) {
 276                     return false;
 277                 }
 278             } else if (!revision.equals(other.revision)) {
 279                 return false;
 280             }
 281             return true;
 282         }
 283
 284         @Override
 285         public String toString() {
 286             return "Module [name=" + name + ", revision=" + formatRevDate(revision) + "]";
 287         }
 288
 289         public Module getReference() {
 290             return originalObject;
 291         }
 292
 293     }
 294
 295 }