2 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
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
8 package org.opendaylight.controller.yang.parser.util;
10 import java.util.Date;
11 import java.util.List;
15 import org.opendaylight.controller.yang.model.api.ModuleImport;
16 import org.opendaylight.controller.yang.parser.builder.impl.ModuleBuilder;
17 import org.opendaylight.controller.yang.parser.impl.YangParserListenerImpl;
18 import org.opendaylight.controller.yang.parser.util.TopologicalSort.Node;
19 import org.opendaylight.controller.yang.parser.util.TopologicalSort.NodeImpl;
20 import org.slf4j.Logger;
21 import org.slf4j.LoggerFactory;
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;
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
35 public final class ModuleDependencySort {
37 private static final Date DEFAULT_REVISION = new Date(0);
38 private static final Logger logger = LoggerFactory
39 .getLogger(ModuleDependencySort.class);
41 private final Map<String, Map<Date, ModuleNodeImpl>> moduleGraph;
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
51 public ModuleDependencySort(ModuleBuilder... builders) {
52 this.moduleGraph = createModuleGraph(builders);
56 Map<String, Map<Date, ModuleNodeImpl>> getModuleGraph() {
61 * Topological sort of module dependency graph.
63 * @return Sorted list of modules. Modules can be further processed in
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()) {
74 // Cast to ModuleNode from Node
75 return Lists.transform(TopologicalSort.sort(nodes),
76 new Function<Node, ModuleSimple>() {
79 public ModuleSimple apply(Node input) {
80 return (ModuleSimple) input;
85 private Map<String, Map<Date, ModuleNodeImpl>> createModuleGraph(
86 ModuleBuilder... builders) {
87 Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = Maps.newHashMap();
89 processModules(moduleGraph, builders);
90 processDependencies(moduleGraph, builders);
96 * Extract module:revision from module builders
98 private void processDependencies(
99 Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
100 ModuleBuilder... builders) {
101 Map<String, Date> imported = Maps.newHashMap();
103 // Create edges in graph
104 for (ModuleBuilder mb : builders) {
105 String fromName = mb.getName();
106 Date fromRevision = mb.getRevision() == null ? DEFAULT_REVISION
108 for (ModuleImport imprt : mb.getModuleImports()) {
109 String toName = imprt.getModuleName();
110 Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION
111 : imprt.getRevision();
113 ModuleNodeImpl from = moduleGraph.get(fromName).get(
116 ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph,
117 fromName, fromRevision, toName, toRevision);
120 * Check imports: If module is imported twice with different
121 * revisions then throw exception
123 if (imported.get(toName) != null
124 && !imported.get(toName).equals(toRevision))
126 .format("Module:%s imported twice with different revisions:%s, %s",
128 formatRevDate(imported.get(toName)),
129 formatRevDate(toRevision)));
130 imported.put(toName, toRevision);
138 * Get imported module by its name and revision from moduleGraph
140 private ModuleNodeImpl getModuleByNameAndRevision(
141 Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
142 String fromName, Date fromRevision, String toName, Date toRevision) {
143 ModuleNodeImpl to = null;
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();
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())));
159 ex(String.format("Not existing module imported:%s:%s by:%s:%s",
160 toName, formatRevDate(toRevision), fromName,
161 formatRevDate(fromRevision)));
163 to = moduleGraph.get(toName).get(toRevision);
168 private void ex(String message) {
169 throw new YangValidationException(message);
173 * Extract dependencies from module builders to fill dependency graph
175 private void processModules(
176 Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
177 ModuleBuilder... builders) {
180 for (ModuleBuilder mb : builders) {
181 String name = mb.getName();
183 Date rev = mb.getRevision();
185 rev = DEFAULT_REVISION;
187 if (moduleGraph.get(name) == null)
188 moduleGraph.put(name, Maps.<Date, ModuleNodeImpl> newHashMap());
190 if (moduleGraph.get(name).get(rev) != null)
191 ex(String.format("Module:%s with revision:%s declared twice",
192 name, formatRevDate(rev)));
194 moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev));
198 private static String formatRevDate(Date rev) {
199 return rev == DEFAULT_REVISION ? "default"
200 : YangParserListenerImpl.simpleDateFormat.format(rev);
204 * Simple representation of module. Contains name and revision.
206 public interface ModuleSimple {
212 static class ModuleNodeImpl extends NodeImpl implements ModuleSimple {
213 private final String name;
214 private final Date revision;
216 public ModuleNodeImpl(String name, Date revision) {
218 this.revision = revision;
222 public String getName() {
227 public Date getRevision() {
232 public int hashCode() {
233 final int prime = 31;
235 result = prime * result + ((name == null) ? 0 : name.hashCode());
236 result = prime * result
237 + ((revision == null) ? 0 : revision.hashCode());
242 public boolean equals(Object obj) {
247 if (getClass() != obj.getClass())
249 ModuleNodeImpl other = (ModuleNodeImpl) obj;
251 if (other.name != null)
253 } else if (!name.equals(other.name))
255 if (revision == null) {
256 if (other.revision != null)
258 } else if (!revision.equals(other.revision))
264 public String toString() {
265 return "Module [name=" + name + ", revision="
266 + formatRevDate(revision) + "]";