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