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