From: Maros Marsalek Date: Tue, 30 Apr 2013 13:03:20 +0000 (+0200) Subject: Implemented module dependency sort, that returns modules in order in which they shoul... X-Git-Tag: releasepom-0.1.0~501^2 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=bb19f8f0c1d080a1232100b1a0e4ffa89f32a542 Implemented module dependency sort, that returns modules in order in which they should be processed. If module A imports module B, sort returns ordered list [B,A]. Implemented utility topological sort that is used by module dependency sort. Implemented tests for both topological sort and module sort. Removed circular dependencies from test yang files. Change-Id: Id6230a8448b27f80146dc74bf2a8a948523408d3 Signed-off-by: Maros Marsalek --- diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/pom.xml index 33d1053f7d..c48f151499 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/pom.xml @@ -20,7 +20,7 @@ generate-sources - ${basedir} + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile1.yang b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile1.yang deleted file mode 100644 index ba0c15eb4e..0000000000 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile1.yang +++ /dev/null @@ -1,57 +0,0 @@ -module types1 { - yang-version 1; - namespace "urn:simple.container.demo"; - prefix "t1"; - - import types2 { - prefix "data"; - revision-date 2013-02-27; - } - - organization "Cisco"; - contact "WILL-BE-DEFINED-LATER"; - - revision "2013-02-27" { - reference " WILL BE DEFINED LATER"; - } - - container interfaces { - list ifEntry { - key "ifIndex"; - - leaf ifIndex { - type uint32; - units minutes; - } - - leaf ifMtu { - type int32; - } - } - } - - leaf testleaf { - type data:my-base-int32-type { - range "min..max"; - } - } - - leaf test-string-leaf { - type data:my-string-type-ext; - } - - leaf test-int-leaf { - type data:my-int-type-ext; - } - - leaf test-decimal-leaf { - type data:my-decimal-type { - fraction-digits 4; - } - } - - leaf test-decimal-leaf2 { - type data:my-decimal-type-ext; - } - -} diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile2.yang b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile2.yang deleted file mode 100644 index 3e9da5256b..0000000000 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile2.yang +++ /dev/null @@ -1,100 +0,0 @@ -module types2 { - yang-version 1; - namespace "urn:simple.types.data.demo"; - prefix "t2"; - - import types1 { - prefix "if"; - revision-date 2013-02-27; - } - - organization "Cisco"; - contact "WILL-BE-DEFINED-LATER"; - description "This is types-data test description"; - - revision "2013-02-27" { - reference " WILL BE DEFINED LATER"; - } - - typedef my-base-int32-type { - type int32 { - range "2..20"; - } - } - - typedef my-type1 { - type my-base-int32-type { - range "11..max"; - } - } - - typedef my-string-type { - type string { - pattern "[a-k]*"; - } - } - - typedef my-string-type2 { - type my-string-type { - pattern "[b-u]*"; - } - } - - typedef my-string-type-ext { - type my-string-type2 { - pattern "[e-z]*"; - } - } - - typedef my-int-type { - type int32 { - range "10..20"; - } - } - - typedef my-int-type2 { - type my-int-type { - range "12..18"; - } - } - - typedef my-int-type-ext { - type my-int-type2 { - range "14..16"; - } - } - - typedef my-decimal-type { - type decimal64 { - fraction-digits 6; - } - } - - typedef my-decimal-type-ext { - type decimal64 { - fraction-digits 5; - } - } - - augment "/if:interfaces/if:ifEntry" { - when "if:ifType='ds0'"; - leaf ds0ChannelNumber { - type string; - } - } - - leaf if-name { - type leafref { - path "/interface/name"; - } - } - - leaf name { - type string; - } - - leaf nested-type-leaf { - type my-type1; - } - -} diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_combined/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_combined/pom.xml index 4fd10ea70f..4fbffb6904 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_combined/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_combined/pom.xml @@ -21,7 +21,7 @@ generate-resources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_resources/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_resources/pom.xml index acb8e6036a..2a935158c1 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_resources/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_resources/pom.xml @@ -20,7 +20,7 @@ generate-resources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators/pom.xml index 82b2cc5b80..a9ec4893f0 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators/pom.xml @@ -20,7 +20,7 @@ generate-sources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators_resources/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators_resources/pom.xml index 96aadd2ba0..74f9dc38e3 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators_resources/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators_resources/pom.xml @@ -20,7 +20,7 @@ generate-resources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator/pom.xml index 88829dff0c..2c7f922838 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator/pom.xml @@ -20,7 +20,7 @@ generate-sources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator_resources/pom.xml b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator_resources/pom.xml index 9d4175d2df..fb83dc96ec 100644 --- a/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator_resources/pom.xml +++ b/opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator_resources/pom.xml @@ -20,7 +20,7 @@ generate-resources - ${basedir}/../Correct + ${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/impl/YangModelParserImpl.java b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/impl/YangModelParserImpl.java index 50943fa740..35c04a8713 100644 --- a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/impl/YangModelParserImpl.java +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/impl/YangModelParserImpl.java @@ -71,6 +71,8 @@ import org.opendaylight.controller.yang.model.parser.builder.impl.ModuleBuilder; import org.opendaylight.controller.yang.model.parser.builder.impl.TypedefBuilder; import org.opendaylight.controller.yang.model.parser.builder.impl.UnionTypeBuilder; import org.opendaylight.controller.yang.model.parser.builder.impl.UnknownSchemaNodeBuilder; +import org.opendaylight.controller.yang.model.parser.util.ModuleDependencySort; +import org.opendaylight.controller.yang.model.parser.util.ModuleDependencySort.ModuleSimple; import org.opendaylight.controller.yang.model.parser.util.ParserUtils; import org.opendaylight.controller.yang.model.parser.util.RefineHolder; import org.opendaylight.controller.yang.model.parser.util.TypeConstraints; @@ -91,7 +93,7 @@ public class YangModelParserImpl implements YangModelParser { public Set parseYangModels(final List yangFiles) { if (yangFiles != null) { final List inputStreams = new ArrayList(); - + for (final File yangFile : yangFiles) { try { inputStreams.add(new FileInputStream(yangFile)); @@ -119,7 +121,7 @@ public class YangModelParserImpl implements YangModelParser { } private Map> resolveModuleBuilders( - final List yangFileStreams) { + final List yangFileStreams) { final Map> modules = new HashMap>(); final ParseTreeWalker walker = new ParseTreeWalker(); final List trees = parseStreams(yangFileStreams); @@ -135,6 +137,9 @@ public class YangModelParserImpl implements YangModelParser { builders[i] = yangModelParser.getModuleBuilder(); } + // module dependency graph sorted + List sorted = new ModuleDependencySort(builders).sort(); + for (ModuleBuilder builder : builders) { final String builderName = builder.getName(); Date builderRevision = builder.getRevision(); @@ -377,7 +382,7 @@ public class YangModelParserImpl implements YangModelParser { tdb.setPatterns(old.getPatterns()); tdb.setFractionDigits(old.getFractionDigits()); tdb.setPath(old.getPath()); - + final TypeDefinition oldType = old.getType(); if (oldType == null) { tdb.setType(old.getTypedef()); diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySort.java b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySort.java new file mode 100644 index 0000000000..5c128d25d2 --- /dev/null +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySort.java @@ -0,0 +1,271 @@ +/* + * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.yang.model.parser.util; + +import java.util.Date; +import java.util.List; +import java.util.Map; +import java.util.Set; + +import org.opendaylight.controller.yang.model.api.ModuleImport; +import org.opendaylight.controller.yang.model.parser.builder.impl.ModuleBuilder; +import org.opendaylight.controller.yang.model.parser.impl.YangModelParserListenerImpl; +import org.opendaylight.controller.yang.model.parser.util.TopologicalSort.Node; +import org.opendaylight.controller.yang.model.parser.util.TopologicalSort.NodeImpl; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.base.Function; +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; +import com.google.common.collect.Sets; + +/** + * Creates a module dependency graph from provided {@link ModuleBuilder}s and + * provides a {@link #sort()} method. It is topological sort and returns modules + * in order in which they should be processed (e.g. if A imports B, sort returns + * {B, A}). + */ +public final class ModuleDependencySort { + + private static final Date DEFAULT_REVISION = new Date(0); + private static final Logger logger = LoggerFactory + .getLogger(ModuleDependencySort.class); + + private final Map> moduleGraph; + + /** + * + * @param builders + * Source for module dependency graph. + * @throws YangValidationException + * if 1. there are module:revision duplicates 2. there is + * imported not existing module 3. module is imported twice + */ + public ModuleDependencySort(ModuleBuilder... builders) { + this.moduleGraph = createModuleGraph(builders); + } + + @VisibleForTesting + Map> getModuleGraph() { + return moduleGraph; + } + + /** + * Topological sort of module dependency graph. + * + * @return Sorted list of modules. Modules can be further processed in + * returned order. + */ + public List sort() { + Set nodes = Sets.newHashSet(); + for (Map map : moduleGraph.values()) { + for (ModuleNodeImpl node : map.values()) { + nodes.add(node); + } + } + + // Cast to ModuleNode from Node + return Lists.transform(TopologicalSort.sort(nodes), + new Function() { + + @Override + public ModuleSimple apply(Node input) { + return (ModuleSimple) input; + } + }); + } + + private Map> createModuleGraph( + ModuleBuilder... builders) { + Map> moduleGraph = Maps.newHashMap(); + + processModules(moduleGraph, builders); + processDependencies(moduleGraph, builders); + + return moduleGraph; + } + + /** + * Extract module:revision from module builders + */ + private void processDependencies( + Map> moduleGraph, + ModuleBuilder... builders) { + Map imported = Maps.newHashMap(); + + // Create edges in graph + for (ModuleBuilder mb : builders) { + String fromName = mb.getName(); + Date fromRevision = mb.getRevision() == null ? DEFAULT_REVISION + : mb.getRevision(); + for (ModuleImport imprt : mb.getModuleImports()) { + String toName = imprt.getModuleName(); + Date toRevision = imprt.getRevision() == null ? DEFAULT_REVISION + : imprt.getRevision(); + + ModuleNodeImpl from = moduleGraph.get(fromName).get( + fromRevision); + + ModuleNodeImpl to = getModuleByNameAndRevision(moduleGraph, + fromName, fromRevision, toName, toRevision); + + /* + * Check imports: If module is imported twice with different + * revisions then throw exception + */ + if (imported.get(toName) != null + && !imported.get(toName).equals(toRevision)) + ex(String + .format("Module:%s imported twice with different revisions:%s, %s", + toName, + formatRevDate(imported.get(toName)), + formatRevDate(toRevision))); + imported.put(toName, toRevision); + + from.addEdge(to); + } + } + } + + /** + * Get imported module by its name and revision from moduleGraph + */ + private ModuleNodeImpl getModuleByNameAndRevision( + Map> moduleGraph, + String fromName, Date fromRevision, String toName, Date toRevision) { + ModuleNodeImpl to = null; + + if (moduleGraph.get(toName) == null + || !moduleGraph.get(toName).containsKey(toRevision)) { + // If revision is not specified in import, but module exists + // with different revisions, take first + if (moduleGraph.get(toName) != null + && !moduleGraph.get(toName).isEmpty() + && toRevision.equals(DEFAULT_REVISION)) { + to = moduleGraph.get(toName).values().iterator().next(); + logger.warn(String + .format("Import:%s:%s by module:%s:%s does not specify revision, using:%s:%s for module dependency sort", + toName, formatRevDate(toRevision), fromName, + formatRevDate(fromRevision), to.getName(), + formatRevDate(to.getRevision()))); + } else + ex(String.format("Not existing module imported:%s:%s by:%s:%s", + toName, formatRevDate(toRevision), fromName, + formatRevDate(fromRevision))); + } else { + to = moduleGraph.get(toName).get(toRevision); + } + return to; + } + + private void ex(String message) { + throw new YangValidationException(message); + } + + /** + * Extract dependencies from module builders to fill dependency graph + */ + private void processModules( + Map> moduleGraph, + ModuleBuilder... builders) { + + // Process nodes + for (ModuleBuilder mb : builders) { + String name = mb.getName(); + + Date rev = mb.getRevision(); + if (rev == null) + rev = DEFAULT_REVISION; + + if (moduleGraph.get(name) == null) + moduleGraph.put(name, Maps. newHashMap()); + + if (moduleGraph.get(name).get(rev) != null) + ex(String.format("Module:%s with revision:%s declared twice", + name, formatRevDate(rev))); + + moduleGraph.get(name).put(rev, new ModuleNodeImpl(name, rev)); + } + } + + private static String formatRevDate(Date rev) { + return rev == DEFAULT_REVISION ? "default" + : YangModelParserListenerImpl.simpleDateFormat.format(rev); + } + + /** + * Simple representation of module. Contains name and revision. + */ + public interface ModuleSimple { + String getName(); + + Date getRevision(); + } + + static class ModuleNodeImpl extends NodeImpl implements ModuleSimple { + private final String name; + private final Date revision; + + public ModuleNodeImpl(String name, Date revision) { + this.name = name; + this.revision = revision; + } + + @Override + public String getName() { + return name; + } + + @Override + public Date getRevision() { + return revision; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((name == null) ? 0 : name.hashCode()); + result = prime * result + + ((revision == null) ? 0 : revision.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + ModuleNodeImpl other = (ModuleNodeImpl) obj; + if (name == null) { + if (other.name != null) + return false; + } else if (!name.equals(other.name)) + return false; + if (revision == null) { + if (other.revision != null) + return false; + } else if (!revision.equals(other.revision)) + return false; + return true; + } + + @Override + public String toString() { + return "Module [name=" + name + ", revision=" + + formatRevDate(revision) + "]"; + } + + } + +} diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSort.java b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSort.java new file mode 100644 index 0000000000..333137c39a --- /dev/null +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSort.java @@ -0,0 +1,184 @@ +/* + * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.yang.model.parser.util; + +import java.util.List; +import java.util.Set; + +import com.google.common.base.Preconditions; +import com.google.common.collect.Lists; +import com.google.common.collect.Sets; + +/** + * Utility class that provides topological sort + */ +public class TopologicalSort { + + /** + * Topological sort of dependent nodes in acyclic graphs. + * + * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no + * dependencies starting. + * @throws IllegalStateException + * when cycle is present in the graph + */ + public static List sort(Set nodes) { + List sortedNodes = Lists.newArrayList(); + + Set dependentNodes = getDependentNodes(nodes); + + while (!dependentNodes.isEmpty()) { + Node n = dependentNodes.iterator().next(); + dependentNodes.remove(n); + + sortedNodes.add(n); + + for (Edge e : n.getInEdges()) { + Node m = e.getFrom(); + m.getOutEdges().remove(e); + + if (m.getOutEdges().isEmpty()) { + dependentNodes.add(m); + } + } + } + + detectCycles(nodes); + + return sortedNodes; + } + + private static Set getDependentNodes(Set nodes) { + Set S = Sets.newHashSet(); + for (Node n : nodes) { + if (n.getOutEdges().size() == 0) { + S.add(n); + } + } + return S; + } + + private static void detectCycles(Set nodes) { + // Detect cycles + boolean cycle = false; + Node cycledNode = null; + + for (Node n : nodes) { + if (!n.getOutEdges().isEmpty()) { + cycle = true; + cycledNode = n; + break; + } + } + Preconditions.checkState(cycle == false, + "Cycle detected in graph around node: " + cycledNode); + } + + /** + * Interface for nodes in graph that can be sorted topologically + */ + public static interface Node { + Set getInEdges(); + + Set getOutEdges(); + } + + /** + * Interface for edges in graph that can be sorted topologically + */ + public static interface Edge { + Node getFrom(); + + Node getTo(); + } + + /** + * Basic Node implementation. + */ + public static class NodeImpl implements Node { + private final Set inEdges; + private final Set outEdges; + + @Override + public Set getInEdges() { + return inEdges; + } + + @Override + public Set getOutEdges() { + return outEdges; + } + + public void addEdge(Node to) { + Edge e = new EdgeImpl(this, to); + outEdges.add(e); + to.getInEdges().add(e); + } + + public NodeImpl() { + inEdges = Sets.newHashSet(); + outEdges = Sets.newHashSet(); + } + } + + /** + * Basic Edge implementation + */ + public static class EdgeImpl implements Edge { + private final Node from; + private final Node to; + + @Override + public Node getFrom() { + return from; + } + + @Override + public Node getTo() { + return to; + } + + public EdgeImpl(Node from, Node to) { + this.from = from; + this.to = to; + + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((from == null) ? 0 : from.hashCode()); + result = prime * result + ((to == null) ? 0 : to.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) + return true; + if (obj == null) + return false; + if (getClass() != obj.getClass()) + return false; + EdgeImpl other = (EdgeImpl) obj; + if (from == null) { + if (other.from != null) + return false; + } else if (!from.equals(other.from)) + return false; + if (to == null) { + if (other.to != null) + return false; + } else if (!to.equals(other.to)) + return false; + return true; + } + } + +} diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySortTest.java b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySortTest.java new file mode 100644 index 0000000000..216d77854f --- /dev/null +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySortTest.java @@ -0,0 +1,192 @@ +/* + * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.yang.model.parser.util; + +import static org.hamcrest.core.AnyOf.*; +import static org.hamcrest.core.Is.*; +import static org.junit.Assert.*; +import static org.junit.matchers.JUnitMatchers.*; +import static org.mockito.Mockito.*; + +import java.util.Date; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; + +import org.hamcrest.Matcher; +import org.junit.Test; +import org.opendaylight.controller.yang.model.api.ModuleImport; +import org.opendaylight.controller.yang.model.parser.builder.impl.ModuleBuilder; +import org.opendaylight.controller.yang.model.parser.impl.YangModelParserListenerImpl; +import org.opendaylight.controller.yang.model.parser.util.ModuleDependencySort.ModuleNodeImpl; +import org.opendaylight.controller.yang.model.parser.util.ModuleDependencySort.ModuleSimple; +import org.opendaylight.controller.yang.model.parser.util.TopologicalSort.Edge; + +import com.google.common.collect.Sets; + +public class ModuleDependencySortTest { + + private ModuleBuilder a = mockModule("a", null); + private ModuleBuilder b = mockModule("b", null); + private ModuleBuilder c = mockModule("c", null); + private ModuleBuilder d = mockModule("d", null); + + @Test + public void testValid() throws Exception { + + mockDependency(a, b); + mockDependency(b, c); + mockDependency(b, d); + + ModuleBuilder[] builders = new ModuleBuilder[] { d, b, c, a }; + ModuleDependencySort sort = new ModuleDependencySort(builders); + + assertDependencyGraph(sort.getModuleGraph()); + + List l = sort.sort(); + + @SuppressWarnings("unchecked") + Matcher cOrD = anyOf(is(c.getName()), is(d.getName())); + + assertThat(l.get(0).getName(), cOrD); + assertThat(l.get(1).getName(), cOrD); + assertThat(l.get(2).getName(), is(b.getName())); + assertThat(l.get(3).getName(), is(a.getName())); + } + + @Test(expected = YangValidationException.class) + public void testModuleTwice() throws Exception { + ModuleBuilder a2 = mockModule("a", null); + + ModuleBuilder[] builders = new ModuleBuilder[] { a, a2 }; + try { + new ModuleDependencySort(builders); + } catch (YangValidationException e) { + assertThat(e.getMessage(), + containsString("Module:a with revision:default declared twice")); + throw e; + } + } + + @Test(expected = YangValidationException.class) + public void testImportNotExistingModule() throws Exception { + mockDependency(a, b); + + ModuleBuilder[] builders = new ModuleBuilder[] { a }; + try { + new ModuleDependencySort(builders); + } catch (YangValidationException e) { + assertThat(e.getMessage(), + containsString("Not existing module imported:b:default by:a:default")); + throw e; + } + } + + @Test + public void testImportTwice() throws Exception { + mockDependency(a, b); + mockDependency(c, b); + + ModuleBuilder[] builders = new ModuleBuilder[] { a, b, c }; + new ModuleDependencySort(builders); + } + + @Test(expected = YangValidationException.class) + public void testImportTwiceDifferentRevision() throws Exception { + Date date = new Date(); + ModuleBuilder b2 = mockModule("b", date); + + mockDependency(a, b); + mockDependency(c, b2); + + ModuleBuilder[] builders = new ModuleBuilder[] { a, c, b, b2 }; + try { + ModuleDependencySort aaa = new ModuleDependencySort(builders); + System.out.println(aaa.getModuleGraph()); + } catch (YangValidationException e) { + assertThat(e.getMessage(), + containsString("Module:b imported twice with different revisions:default, " + + YangModelParserListenerImpl.simpleDateFormat + .format(date))); + throw e; + } + } + + @Test + public void testModuleTwiceWithDifferentRevs() throws Exception { + ModuleBuilder a2 = mockModule("a", new Date()); + + ModuleBuilder[] builders = new ModuleBuilder[] { a, a2 }; + new ModuleDependencySort(builders); + } + + @Test(expected = YangValidationException.class) + public void testModuleTwice2() throws Exception { + Date rev = new Date(); + ModuleBuilder a2 = mockModule("a", rev); + ModuleBuilder a3 = mockModule("a", rev); + + ModuleBuilder[] builders = new ModuleBuilder[] { a, a2, a3 }; + try { + new ModuleDependencySort(builders); + } catch (YangValidationException e) { + assertThat(e.getMessage(), containsString("Module:a with revision:" + + YangModelParserListenerImpl.simpleDateFormat.format(rev) + + " declared twice")); + throw e; + } + } + + private void assertDependencyGraph( + Map> moduleGraph) { + for (Entry> node : moduleGraph + .entrySet()) { + String name = node.getKey(); + + // Expects only one module revision + + Set inEdges = node.getValue().values().iterator().next() + .getInEdges(); + Set outEdges = node.getValue().values().iterator().next() + .getOutEdges(); + + if (name.equals("a")) { + assertEdgeCount(inEdges, 0, outEdges, 1); + } else if (name.equals("b")) { + assertEdgeCount(inEdges, 1, outEdges, 2); + } else { + assertEdgeCount(inEdges, 1, outEdges, 0); + } + } + } + + private void assertEdgeCount(Set inEdges, int i, Set outEdges, + int j) { + assertThat(inEdges.size(), is(i)); + assertThat(outEdges.size(), is(j)); + } + + private void mockDependency(ModuleBuilder a, ModuleBuilder b) { + ModuleImport imprt = mock(ModuleImport.class); + doReturn(b.getName()).when(imprt).getModuleName(); + doReturn(b.getRevision()).when(imprt).getRevision(); + a.getModuleImports().add(imprt); + } + + private ModuleBuilder mockModule(String name, Date rev) { + ModuleBuilder a = mock(ModuleBuilder.class); + doReturn(name).when(a).getName(); + Set set = Sets.newHashSet(); + doReturn(set).when(a).getModuleImports(); + if (rev != null) { + doReturn(rev).when(a).getRevision(); + } + return a; + } +} diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSortTest.java b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSortTest.java new file mode 100644 index 0000000000..bfb94e530c --- /dev/null +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSortTest.java @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.controller.yang.model.parser.util; + +import static org.hamcrest.core.Is.*; +import static org.junit.Assert.*; + +import java.util.List; +import java.util.Set; + +import org.junit.Test; +import org.opendaylight.controller.yang.model.parser.util.TopologicalSort.Node; +import org.opendaylight.controller.yang.model.parser.util.TopologicalSort.NodeImpl; + +import com.google.common.collect.Sets; + +public class TopologicalSortTest { + + @Test(expected = IllegalStateException.class) + public void test() throws Exception { + Set nodes = Sets.newHashSet(); + + NodeImpl node1 = new NodeImpl(); + nodes.add(node1); + NodeImpl node2 = new NodeImpl(); + nodes.add(node2); + NodeImpl node3 = new NodeImpl(); + nodes.add(node3); + + node1.addEdge(node2); + node2.addEdge(node3); + node3.addEdge(node1); + + try { + TopologicalSort.sort(nodes); + } catch (IllegalStateException e) { + throw e; + } + } + + @Test + public void testValidSimple() throws Exception { + Set nodes = Sets.newHashSet(); + + Node node1 = new NodeImpl(); + nodes.add(node1); + Node node2 = new NodeImpl(); + nodes.add(node2); + Node node3 = new NodeImpl(); + nodes.add(node3); + Node node4 = new NodeImpl(); + nodes.add(node4); + + ((NodeImpl) node1).addEdge(node2); + ((NodeImpl) node1).addEdge(node3); + ((NodeImpl) node2).addEdge(node4); + ((NodeImpl) node3).addEdge(node2); + + List sorted = TopologicalSort.sort(nodes); + + assertThat(sorted.get(0), is(node4)); + assertThat(sorted.get(1), is(node2)); + assertThat(sorted.get(2), is(node3)); + assertThat(sorted.get(3), is(node1)); + } + +} diff --git a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/resources/model/testfile2.yang b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/resources/model/testfile2.yang index 4f146f705d..1a7b45ecb1 100644 --- a/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/resources/model/testfile2.yang +++ b/opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/resources/model/testfile2.yang @@ -3,11 +3,6 @@ module types2 { namespace "urn:simple.types.data.demo"; prefix "t2"; - import types1 { - prefix "if"; - revision-date 2013-02-27; - } - organization "opendaylight"; contact "http://www.opendaylight.org/";