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