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         Map<String, Date> imported = Maps.newHashMap();
 135
 136         // Create edges in graph
 137         for (Object mb : builders) {
 138
 139             String fromName = null;
 140             Date fromRevision = null;
 141             Set<ModuleImport> imports = null;
 142
 143             if (mb instanceof Module) {
 144                 fromName = ((Module) mb).getName();
 145                 fromRevision = ((Module) mb).getRevision();
 146                 imports = ((Module) mb).getImports();
 147             } else if (mb instanceof ModuleBuilder) {
 148                 fromName = ((ModuleBuilder) mb).getName();
 149                 fromRevision = ((ModuleBuilder) mb).getRevision();
 150                 imports = ((ModuleBuilder) mb).getModuleImports();
 151             }
 152             // no need to check if other Type of object, check is performed in
 153             // process modules
 154
 155             if (fromRevision == null) {
 156                 fromRevision = DEFAULT_REVISION;
 157             }
 158
 159             for (ModuleImport imprt : imports) {
 160                 String toName = imprt.getModuleName();
 161                 Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION : imprt.getRevision();
 162
 163                 ModuleNodeImpl from = moduleGraph.get(fromName).get(fromRevision);
 164
 165                 ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, fromName, fromRevision, toName, toRevision);
 166
 167                 /*
 168                  * Check imports: If module is imported twice with different
 169                  * revisions then throw exception
 170                  */
 171                 if (imported.get(toName) != null && !imported.get(toName).equals(toRevision)
 172                         && !imported.get(toName).equals(DEFAULT_REVISION) && !toRevision.equals(DEFAULT_REVISION)) {
 173                     ex(String.format("Module:%s imported twice with different revisions:%s, %s", toName,
 174                             formatRevDate(imported.get(toName)), formatRevDate(toRevision)));
 175                 }
 176
 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(Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
 188             String fromName, Date fromRevision, String toName, Date toRevision) {
 189         ModuleNodeImpl to = null;
 190
 191         if (moduleGraph.get(toName) == null || !moduleGraph.get(toName).containsKey(toRevision)) {
 192             // If revision is not specified in import, but module exists
 193             // with different revisions, take first
 194             if (moduleGraph.get(toName) != null && !moduleGraph.get(toName).isEmpty()
 195                     && toRevision.equals(DEFAULT_REVISION)) {
 196                 to = moduleGraph.get(toName).values().iterator().next();
 197                 LOGGER.debug(String
 198                         .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort",
 199                                 toName, formatRevDate(toRevision), fromName, formatRevDate(fromRevision), to.getName(),
 200                                 formatRevDate(to.getRevision())));
 201             } else {
 202                 LOGGER.warn(String.format("Not existing module imported:%s:%s by:%s:%s", toName,
 203                         formatRevDate(toRevision), fromName, formatRevDate(fromRevision)));
 204                 LOGGER.warn("Available models: {}", moduleGraph);
 205                 ex(String.format("Not existing module imported:%s:%s by:%s:%s", toName, formatRevDate(toRevision),
 206                         fromName, formatRevDate(fromRevision)));
 207             }
 208         } else {
 209             to = moduleGraph.get(toName).get(toRevision);
 210         }
 211         return to;
 212     }
 213
 214     private static void ex(String message) {
 215         throw new YangValidationException(message);
 216     }
 217
 218     /**
 219      * Extract dependencies from module builders or modules to fill dependency
 220      * graph
 221      */
 222     private static void processModules(Map<String, Map<Date, ModuleNodeImpl>> moduleGraph, List<?> builders) {
 223
 224         // Process nodes
 225         for (Object mb : builders) {
 226
 227             String name = null;
 228             Date rev = null;
 229
 230             if (mb instanceof Module) {
 231                 name = ((Module) mb).getName();
 232                 rev = ((Module) mb).getRevision();
 233             } else if (mb instanceof ModuleBuilder) {
 234                 name = ((ModuleBuilder) mb).getName();
 235                 rev = ((ModuleBuilder) mb).getRevision();
 236             } else {
 237                 throw new IllegalStateException(String.format(
 238                         "Unexpected type of node for sort, expected only:%s, %s, got:%s", Module.class,
 239                         ModuleBuilder.class, mb.getClass()));
 240             }
 241
 242             if (rev == null) {
 243                 rev = DEFAULT_REVISION;
 244             }
 245
 246             if (moduleGraph.get(name) == null) {
 247                 moduleGraph.put(name, Maps.<Date, ModuleNodeImpl> newHashMap());
 248             }
 249
 250             if (moduleGraph.get(name).get(rev) != null) {
 251                 ex(String.format("Module:%s with revision:%s declared twice", name, formatRevDate(rev)));
 252             }
 253
 254             moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev, mb));
 255         }
 256     }
 257
 258     private static String formatRevDate(Date rev) {
 259         return rev.equals(DEFAULT_REVISION) ? "default" : new SimpleDateFormat("yyyy-MM-dd").format(rev);
 260     }
 261
 262     @VisibleForTesting
 263     static class ModuleNodeImpl extends NodeImpl {
 264         private final String name;
 265         private final Date revision;
 266         private final Object originalObject;
 267
 268         public ModuleNodeImpl(String name, Date revision, Object builder) {
 269             this.name = name;
 270             this.revision = revision;
 271             this.originalObject = builder;
 272         }
 273
 274         public String getName() {
 275             return name;
 276         }
 277
 278         public Date getRevision() {
 279             return revision;
 280         }
 281
 282         @Override
 283         public int hashCode() {
 284             final int prime = 31;
 285             int result = 1;
 286             result = prime * result + ((name == null) ? 0 : name.hashCode());
 287             result = prime * result + ((revision == null) ? 0 : revision.hashCode());
 288             return result;
 289         }
 290
 291         @Override
 292         public boolean equals(Object obj) {
 293             if (this == obj) {
 294                 return true;
 295             }
 296             if (obj == null) {
 297                 return false;
 298             }
 299             if (getClass() != obj.getClass()) {
 300                 return false;
 301             }
 302             ModuleNodeImpl other = (ModuleNodeImpl) obj;
 303             if (name == null) {
 304                 if (other.name != null) {
 305                     return false;
 306                 }
 307             } else if (!name.equals(other.name)) {
 308                 return false;
 309             }
 310             if (revision == null) {
 311                 if (other.revision != null) {
 312                     return false;
 313                 }
 314             } else if (!revision.equals(other.revision)) {
 315                 return false;
 316             }
 317             return true;
 318         }
 319
 320         @Override
 321         public String toString() {
 322             return "Module [name=" + name + ", revision=" + formatRevDate(revision) + "]";
 323         }
 324
 325         public Object getReference() {
 326             return originalObject;
 327         }
 328
 329     }
 330
 331 }