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