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