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