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