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