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  * This program and the accompanying materials are made available under the
   4  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   5  * and is available at http://www.eclipse.org/legal/epl-v10.html
   6  */
   7 package org.opendaylight.yangtools.yang.parser.util;
   8
   9 import static java.util.Arrays.asList;
  10
  11 import com.google.common.annotations.VisibleForTesting;
  12 import com.google.common.base.Function;
  13 import com.google.common.base.Optional;
  14 import com.google.common.collect.Lists;
  15 import com.google.common.collect.Maps;
  16 import com.google.common.collect.Sets;
  17 import java.net.URI;
  18 import java.util.ArrayList;
  19 import java.util.Collection;
  20 import java.util.Collections;
  21 import java.util.Date;
  22 import java.util.HashMap;
  23 import java.util.List;
  24 import java.util.Map;
  25 import java.util.Set;
  26 import org.opendaylight.yangtools.yang.common.SimpleDateFormatUtil;
  27 import org.opendaylight.yangtools.yang.model.api.Module;
  28 import org.opendaylight.yangtools.yang.model.api.ModuleImport;
  29 import org.opendaylight.yangtools.yang.model.api.SchemaContext;
  30 import org.opendaylight.yangtools.yang.parser.builder.impl.ModuleBuilder;
  31 import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node;
  32 import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl;
  33 import org.slf4j.Logger;
  34 import org.slf4j.LoggerFactory;
  35
  36 /**
  37  * Creates a module dependency graph from provided {@link ModuleBuilder}s and
  38  * provides a {@link #sort(ModuleBuilder...)} method. It is topological sort and
  39  * returns modules in order in which they should be processed (e.g. if A imports
  40  * B, sort returns {B, A}).
  41  */
  42 public final class ModuleDependencySort {
  43
  44     private static final Date DEFAULT_REVISION = new Date(0);
  45     private static final Logger LOGGER = LoggerFactory.getLogger(ModuleDependencySort.class);
  46     private static final Function<Node, Module> TOPOLOGY_FUNCTION = new Function<TopologicalSort.Node, Module>() {
  47         @Override
  48         public Module apply(final TopologicalSort.Node input) {
  49             ModuleOrModuleBuilder moduleOrModuleBuilder = ((ModuleNodeImpl) input).getReference();
  50             return moduleOrModuleBuilder.getModule();
  51         }
  52     };
  53
  54     /**
  55      * It is not desirable to instance this class
  56      */
  57     private ModuleDependencySort() {
  58     }
  59
  60
  61     /**
  62      * Extracts {@link ModuleBuilder} from a {@link ModuleNodeImpl}.
  63      */
  64     private static final Function<TopologicalSort.Node, ModuleBuilder> NODE_TO_MODULEBUILDER = new Function<TopologicalSort.Node, ModuleBuilder>() {
  65         @Override
  66         public ModuleBuilder apply(final TopologicalSort.Node input) {
  67             // Cast to ModuleBuilder from Node and return
  68             ModuleOrModuleBuilder moduleOrModuleBuilder = ((ModuleNodeImpl) input).getReference();
  69             return moduleOrModuleBuilder.getModuleBuilder();
  70         }
  71     };
  72
  73     /**
  74      * Topological sort of module builder dependency graph.
  75      *
  76      * @return Sorted list of Module builders. Modules can be further processed
  77      *         in returned order.
  78      */
  79     public static List<ModuleBuilder> sort(final ModuleBuilder... builders) {
  80         return sort(asList(builders));
  81     }
  82
  83     public static List<ModuleBuilder> sort(final Collection<ModuleBuilder> builders) {
  84         List<TopologicalSort.Node> sorted = sortInternal(ModuleOrModuleBuilder.fromAll(
  85                 Collections.<Module>emptySet(),builders));
  86         return Lists.transform(sorted, NODE_TO_MODULEBUILDER);
  87     }
  88
  89     public static List<ModuleBuilder> sortWithContext(final SchemaContext context, final ModuleBuilder... builders) {
  90         List<ModuleOrModuleBuilder> all = ModuleOrModuleBuilder.fromAll(context.getModules(), asList(builders));
  91
  92         List<TopologicalSort.Node> sorted = sortInternal(all);
  93         // Cast to ModuleBuilder from Node if possible and return
  94         return Lists.transform(sorted, new Function<TopologicalSort.Node, ModuleBuilder>() {
  95
  96             @Override
  97             public ModuleBuilder apply(final TopologicalSort.Node input) {
  98                 ModuleOrModuleBuilder moduleOrModuleBuilder = ((ModuleNodeImpl) input).getReference();
  99                 if (moduleOrModuleBuilder.isModuleBuilder()) {
 100                     return moduleOrModuleBuilder.getModuleBuilder();
 101                 } else {
 102                     return null;
 103                 }
 104             }
 105         });
 106     }
 107
 108     /**
 109      * Topological sort of module dependency graph.
 110      *
 111      * @return Sorted list of Modules. Modules can be further processed in
 112      *         returned order.
 113      */
 114     public static List<Module> sort(final Module... modules) {
 115         List<TopologicalSort.Node> sorted = sortInternal(ModuleOrModuleBuilder.fromAll(asList(modules),
 116                 Collections.<ModuleBuilder>emptyList()));
 117         // Cast to Module from Node and return
 118         return Lists.transform(sorted, TOPOLOGY_FUNCTION);
 119     }
 120
 121     private static List<TopologicalSort.Node> sortInternal(final Iterable<ModuleOrModuleBuilder> modules) {
 122         Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = createModuleGraph(modules);
 123
 124         Set<TopologicalSort.Node> nodes = Sets.newHashSet();
 125         for (Map<Date, ModuleNodeImpl> map : moduleGraph.values()) {
 126             for (ModuleNodeImpl node : map.values()) {
 127                 nodes.add(node);
 128             }
 129         }
 130
 131         return TopologicalSort.sort(nodes);
 132     }
 133
 134     @VisibleForTesting
 135     static Map<String, Map<Date, ModuleNodeImpl>> createModuleGraph(final Iterable<ModuleOrModuleBuilder> builders) {
 136         Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = Maps.newHashMap();
 137
 138         processModules(moduleGraph, builders);
 139         processDependencies(moduleGraph, builders);
 140
 141         return moduleGraph;
 142     }
 143
 144     /**
 145      * Extract module:revision from module builders
 146      */
 147     private static void processDependencies(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 148             final Iterable<ModuleOrModuleBuilder> mmbs) {
 149         Map<URI, ModuleOrModuleBuilder> allNS = new HashMap<>();
 150
 151         // Create edges in graph
 152         for (ModuleOrModuleBuilder mmb : mmbs) {
 153             Map<String, Date> imported = Maps.newHashMap();
 154
 155             String fromName;
 156             Date fromRevision;
 157             Collection<ModuleImport> imports;
 158             URI ns;
 159
 160             if (mmb.isModule()) {
 161                 Module module = mmb.getModule();
 162                 fromName = module.getName();
 163                 fromRevision = module.getRevision();
 164                 imports = module.getImports();
 165                 ns = module.getNamespace();
 166             } else {
 167                 ModuleBuilder moduleBuilder = mmb.getModuleBuilder();
 168                 fromName = moduleBuilder.getName();
 169                 fromRevision = moduleBuilder.getRevision();
 170                 imports = moduleBuilder.getImports().values();
 171                 ns = moduleBuilder.getNamespace();
 172             }
 173
 174             // check for existence of module with same namespace
 175             if (allNS.containsKey(ns)) {
 176                 ModuleOrModuleBuilder mod = allNS.get(ns);
 177                 String name = null;
 178                 Date revision = null;
 179                 if (mod.isModule()) {
 180                     name = mod.getModule().getName();
 181                     revision = mod.getModule().getRevision();
 182                 } else if (mod.isModuleBuilder()) {
 183                     name = mod.getModuleBuilder().getName();
 184                     revision = mod.getModuleBuilder().getRevision();
 185                 }
 186                 if (!(fromName.equals(name))) {
 187                     LOGGER.warn(
 188                             "Error while sorting module [{}, {}]: module with same namespace ({}) already loaded: [{}, {}]",
 189                             fromName, fromRevision, ns, name, revision);
 190                 }
 191             } else {
 192                 allNS.put(ns, mmb);
 193             }
 194
 195             // no need to check if other Type of object, check is performed in
 196             // process modules
 197
 198             if (fromRevision == null) {
 199                 fromRevision = DEFAULT_REVISION;
 200             }
 201
 202             for (ModuleImport imprt : imports) {
 203                 String toName = imprt.getModuleName();
 204                 Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION : imprt.getRevision();
 205
 206                 ModuleNodeImpl from = moduleGraph.get(fromName).get(fromRevision);
 207
 208                 ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName, toRevision);
 209
 210                 /*
 211                  * Check imports: If module is imported twice with different
 212                  * revisions then throw exception
 213                  */
 214                 if (imported.get(toName) != null && !imported.get(toName).equals(toRevision)
 215                         && !imported.get(toName).equals(DEFAULT_REVISION) && !toRevision.equals(DEFAULT_REVISION)) {
 216                     ex(String.format("Module:%s imported twice with different revisions:%s, %s", toName,
 217                             formatRevDate(imported.get(toName)), formatRevDate(toRevision)));
 218                 }
 219
 220                 imported.put(toName, toRevision);
 221
 222                 from.addEdge(to);
 223             }
 224         }
 225     }
 226
 227     /**
 228      * Get imported module by its name and revision from moduleGraph
 229      */
 230     private static ModuleNodeImpl getModuleByNameAndRevision(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 231             final String fromName, final Date fromRevision, final String toName, final Date toRevision) {
 232         ModuleNodeImpl to = null;
 233
 234         if (moduleGraph.get(toName) == null || !moduleGraph.get(toName).containsKey(toRevision)) {
 235             // If revision is not specified in import, but module exists
 236             // with different revisions, take first
 237             if (moduleGraph.get(toName) != null && !moduleGraph.get(toName).isEmpty()
 238                     && toRevision.equals(DEFAULT_REVISION)) {
 239                 to = moduleGraph.get(toName).values().iterator().next();
 240                 LOGGER.trace(String
 241                         .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort",
 242                                 toName, formatRevDate(toRevision), fromName, formatRevDate(fromRevision), to.getName(),
 243                                 formatRevDate(to.getRevision())));
 244             } else {
 245                 LOGGER.warn(String.format("Not existing module imported:%s:%s by:%s:%s", toName,
 246                         formatRevDate(toRevision), fromName, formatRevDate(fromRevision)));
 247                 LOGGER.warn("Available models: {}", moduleGraph);
 248                 ex(String.format("Not existing module imported:%s:%s by:%s:%s", toName, formatRevDate(toRevision),
 249                         fromName, formatRevDate(fromRevision)));
 250             }
 251         } else {
 252             to = moduleGraph.get(toName).get(toRevision);
 253         }
 254         return to;
 255     }
 256
 257     private static void ex(final String message) {
 258         throw new YangValidationException(message);
 259     }
 260
 261     /**
 262      * Extract dependencies from module builders or modules to fill dependency
 263      * graph
 264      */
 265     private static void processModules(final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 266             final Iterable<ModuleOrModuleBuilder> builders) {
 267
 268         // Process nodes
 269         for (ModuleOrModuleBuilder momb : builders) {
 270
 271             String name;
 272             Date rev;
 273
 274             if (momb.isModule()) {
 275                 name = momb.getModule().getName();
 276                 rev = momb.getModule().getRevision();
 277             } else {
 278                 name = momb.getModuleBuilder().getName();
 279                 rev = momb.getModuleBuilder().getRevision();
 280             }
 281
 282             if (rev == null) {
 283                 rev = DEFAULT_REVISION;
 284             }
 285
 286             if (moduleGraph.get(name) == null) {
 287                 moduleGraph.put(name, Maps.<Date, ModuleNodeImpl> newHashMap());
 288             }
 289
 290             if (moduleGraph.get(name).get(rev) != null) {
 291                 ex(String.format("Module:%s with revision:%s declared twice", name, formatRevDate(rev)));
 292             }
 293
 294             moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev, momb));
 295         }
 296     }
 297
 298     private static String formatRevDate(final Date rev) {
 299         return rev.equals(DEFAULT_REVISION) ? "default" : SimpleDateFormatUtil.getRevisionFormat().format(rev);
 300     }
 301
 302     @VisibleForTesting
 303     static class ModuleNodeImpl extends NodeImpl {
 304         private final String name;
 305         private final Date revision;
 306         private final ModuleOrModuleBuilder originalObject;
 307
 308         public ModuleNodeImpl(final String name, final Date revision, final ModuleOrModuleBuilder builder) {
 309             this.name = name;
 310             this.revision = revision;
 311             this.originalObject = builder;
 312         }
 313
 314         public String getName() {
 315             return name;
 316         }
 317
 318         public Date getRevision() {
 319             return revision;
 320         }
 321
 322         @Override
 323         public int hashCode() {
 324             final int prime = 31;
 325             int result = 1;
 326             result = prime * result + ((name == null) ? 0 : name.hashCode());
 327             result = prime * result + ((revision == null) ? 0 : revision.hashCode());
 328             return result;
 329         }
 330
 331         @Override
 332         public boolean equals(final Object obj) {
 333             if (this == obj) {
 334                 return true;
 335             }
 336             if (obj == null) {
 337                 return false;
 338             }
 339             if (getClass() != obj.getClass()) {
 340                 return false;
 341             }
 342             ModuleNodeImpl other = (ModuleNodeImpl) obj;
 343             if (name == null) {
 344                 if (other.name != null) {
 345                     return false;
 346                 }
 347             } else if (!name.equals(other.name)) {
 348                 return false;
 349             }
 350             if (revision == null) {
 351                 if (other.revision != null) {
 352                     return false;
 353                 }
 354             } else if (!revision.equals(other.revision)) {
 355                 return false;
 356             }
 357             return true;
 358         }
 359
 360         @Override
 361         public String toString() {
 362             return "Module [name=" + name + ", revision=" + formatRevDate(revision) + "]";
 363         }
 364
 365         public ModuleOrModuleBuilder getReference() {
 366             return originalObject;
 367         }
 368
 369     }
 370
 371 }
 372 class ModuleOrModuleBuilder {
 373     private final Optional<Module> maybeModule;
 374     private final Optional<ModuleBuilder> maybeModuleBuilder;
 375
 376     ModuleOrModuleBuilder(final Module module) {
 377         maybeModule = Optional.of(module);
 378         maybeModuleBuilder = Optional.absent();
 379     }
 380
 381     ModuleOrModuleBuilder(final ModuleBuilder moduleBuilder) {
 382         maybeModule = Optional.absent();
 383         maybeModuleBuilder = Optional.of(moduleBuilder);
 384     }
 385     boolean isModule(){
 386         return maybeModule.isPresent();
 387     }
 388     boolean isModuleBuilder(){
 389         return maybeModuleBuilder.isPresent();
 390     }
 391     Module getModule(){
 392         return maybeModule.get();
 393     }
 394     ModuleBuilder getModuleBuilder(){
 395         return maybeModuleBuilder.get();
 396     }
 397
 398     static List<ModuleOrModuleBuilder> fromAll(final Collection<Module> modules, final Collection<ModuleBuilder> moduleBuilders) {
 399         List<ModuleOrModuleBuilder> result = new ArrayList<>(modules.size() + moduleBuilders.size());
 400         for(Module m: modules){
 401             result.add(new ModuleOrModuleBuilder(m));
 402         }
 403         for (ModuleBuilder mb : moduleBuilders) {
 404             result.add(new ModuleOrModuleBuilder(mb));
 405         }
 406         return result;
 407     }
 408 }