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