Implemented module dependency sort, that returns modules in order in which they shoul... 80/280/2
authorMaros Marsalek <mmarsale@cisco.com>
Tue, 30 Apr 2013 13:03:20 +0000 (15:03 +0200)
committerMaros Marsalek <mmarsale@cisco.com>
Thu, 2 May 2013 09:36:07 +0000 (11:36 +0200)
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 <mmarsale@cisco.com>
15 files changed:
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile1.yang [deleted file]
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct/resources/model/testfile2.yang [deleted file]
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_combined/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/Correct_resources/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/NoGenerators_resources/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator/pom.xml
opendaylight/sal/yang-prototype/code-generator/maven-yang-plugin-it/src/test/resources/UnknownGenerator_resources/pom.xml
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/impl/YangModelParserImpl.java
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySort.java [new file with mode: 0644]
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/main/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSort.java [new file with mode: 0644]
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/ModuleDependencySortTest.java [new file with mode: 0644]
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/java/org/opendaylight/controller/yang/model/parser/util/TopologicalSortTest.java [new file with mode: 0644]
opendaylight/sal/yang-prototype/code-generator/yang-model-parser-impl/src/test/resources/model/testfile2.yang

index 33d1053..c48f151 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-sources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <codeGenerators>
                                 <generator>
                                     <codeGeneratorClass>
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 (file)
index ba0c15e..0000000
+++ /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 (file)
index 3e9da52..0000000
+++ /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;
-       }
-
-}
index 4fd10ea..4fbffb6 100644 (file)
@@ -21,7 +21,7 @@
                             <goal>generate-resources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <codeGenerators>
                                 <generator>
                                     <codeGeneratorClass>
index acb8e60..2a93515 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-resources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <resourceProviders>
                                 <provider>
                                     <resourceProviderClass>
index 82b2cc5..a9ec489 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-sources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <codeGenerators>
                             </codeGenerators>
                         </configuration>
index 96aadd2..74f9dc3 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-resources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <resourceProviders>
                             </resourceProviders>
                         </configuration>
index 88829df..2c7f922 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-sources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <codeGenerators>
                                 <generator>
                                     <codeGeneratorClass>
index 9d4175d..fb83dc9 100644 (file)
@@ -20,7 +20,7 @@
                             <goal>generate-resources</goal>
                         </goals>
                         <configuration>
-                            <yangFilesRootDir>${basedir}/../Correct</yangFilesRootDir>
+                            <yangFilesRootDir>${basedir}/../../../../../yang-model-parser-impl/src/test/resources/model</yangFilesRootDir>
                             <resourceProviders>
                                 <provider>
                                     <resourceProviderClass>
index 50943fa..35c04a8 100644 (file)
@@ -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<Module> parseYangModels(final List<File> yangFiles) {
         if (yangFiles != null) {
             final List<InputStream> inputStreams = new ArrayList<InputStream>();
-            
+
             for (final File yangFile : yangFiles) {
                 try {
                     inputStreams.add(new FileInputStream(yangFile));
@@ -119,7 +121,7 @@ public class YangModelParserImpl implements YangModelParser {
     }
 
     private Map<String, TreeMap<Date, ModuleBuilder>> resolveModuleBuilders(
-            final List<InputStream>  yangFileStreams) {
+            final List<InputStream> yangFileStreams) {
         final Map<String, TreeMap<Date, ModuleBuilder>> modules = new HashMap<String, TreeMap<Date, ModuleBuilder>>();
         final ParseTreeWalker walker = new ParseTreeWalker();
         final List<ParseTree> trees = parseStreams(yangFileStreams);
@@ -135,6 +137,9 @@ public class YangModelParserImpl implements YangModelParser {
             builders[i] = yangModelParser.getModuleBuilder();
         }
 
+        // module dependency graph sorted
+        List<ModuleSimple> 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 (file)
index 0000000..5c128d2
--- /dev/null
@@ -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<String, Map<Date, ModuleNodeImpl>> 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<String, Map<Date, ModuleNodeImpl>> getModuleGraph() {
+        return moduleGraph;
+    }
+
+    /**
+     * Topological sort of module dependency graph.
+     *
+     * @return Sorted list of modules. Modules can be further processed in
+     *         returned order.
+     */
+    public List<ModuleSimple> sort() {
+        Set<Node> nodes = Sets.newHashSet();
+        for (Map<Date, ModuleNodeImpl> map : moduleGraph.values()) {
+            for (ModuleNodeImpl node : map.values()) {
+                nodes.add(node);
+            }
+        }
+
+        // Cast to ModuleNode from Node
+        return Lists.transform(TopologicalSort.sort(nodes),
+                new Function<Node, ModuleSimple>() {
+
+                    @Override
+                    public ModuleSimple apply(Node input) {
+                        return (ModuleSimple) input;
+                    }
+                });
+    }
+
+    private Map<String, Map<Date, ModuleNodeImpl>> createModuleGraph(
+            ModuleBuilder... builders) {
+        Map<String, Map<Date, ModuleNodeImpl>> moduleGraph = Maps.newHashMap();
+
+        processModules(moduleGraph, builders);
+        processDependencies(moduleGraph, builders);
+
+        return moduleGraph;
+    }
+
+    /**
+     * Extract module:revision from module builders
+     */
+    private void processDependencies(
+            Map<String, Map<Date, ModuleNodeImpl>> moduleGraph,
+            ModuleBuilder... builders) {
+        Map<String, Date> 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<String, Map<Date, ModuleNodeImpl>> 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<String, Map<Date, ModuleNodeImpl>> 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.<Date, ModuleNodeImpl> 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 (file)
index 0000000..333137c
--- /dev/null
@@ -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<Node> sort(Set<Node> nodes) {
+        List<Node> sortedNodes = Lists.newArrayList();
+
+        Set<Node> 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<Node> getDependentNodes(Set<Node> nodes) {
+        Set<Node> S = Sets.newHashSet();
+        for (Node n : nodes) {
+            if (n.getOutEdges().size() == 0) {
+                S.add(n);
+            }
+        }
+        return S;
+    }
+
+    private static void detectCycles(Set<Node> 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<Edge> getInEdges();
+
+        Set<Edge> 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<Edge> inEdges;
+        private final Set<Edge> outEdges;
+
+        @Override
+        public Set<Edge> getInEdges() {
+            return inEdges;
+        }
+
+        @Override
+        public Set<Edge> 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 (file)
index 0000000..216d778
--- /dev/null
@@ -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<ModuleSimple> l = sort.sort();
+
+        @SuppressWarnings("unchecked")
+        Matcher<String> 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<String, Map<Date, ModuleNodeImpl>> moduleGraph) {
+        for (Entry<String, Map<Date, ModuleNodeImpl>> node : moduleGraph
+                .entrySet()) {
+            String name = node.getKey();
+
+            // Expects only one module revision
+
+            Set<Edge> inEdges = node.getValue().values().iterator().next()
+                    .getInEdges();
+            Set<Edge> 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<Edge> inEdges, int i, Set<Edge> 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<ModuleImport> 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 (file)
index 0000000..bfb94e5
--- /dev/null
@@ -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<Node> 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<Node> 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<Node> 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));
+    }
+
+}
index 4f146f7..1a7b45e 100644 (file)
@@ -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/";