add proper FType dependency cycle detection

3 files changed, 122 insertions, 71 deletions

diff --git a/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeCycleDetector.xtend b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeCycleDetector.xtend
new file mode 100644
index 0000000..5b623ad
--- /dev/null
+++ b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeCycleDetector.xtend
@@ -0,0 +1,72 @@
+package org.genivi.commonapi.core.generator
+
+import java.util.HashMap
+import java.util.List
+import java.util.Stack
+import org.franca.core.franca.FType
+
+class FTypeCycleDetector {
+	private extension FrancaGeneratorExtensions francaGeneratorExtensions
+
+	private val indices = new HashMap<FType, Integer>
+	private val lowlink = new HashMap<FType, Integer>
+	private val stack = new Stack<FType>
+	private var int index
+
+
+	new(FrancaGeneratorExtensions francaGeneratorExtensions) {
+		this.francaGeneratorExtensions = francaGeneratorExtensions
+	}
+
+	def hasCycle(List<FType> types) {
+		indices.clear()
+		lowlink.clear()
+		stack.clear()
+		index = 0
+
+		val typeWithCycle = types.findFirst[type | !indices.containsKey(type) && tarjan(type)]
+
+		return typeWithCycle != null
+	}
+
+	// Tarjan's Strongly Connected Components Algorithm
+	// returns true if a cycle was detected
+	/**
+	 * Tarjan's Strongly Connected Components Algorithm
+	 * 
+	 * @param type
+	 *            start searching from type.
+	 * @return <code>true</code> if a dependency cycle was detected.
+	 */
+	def private boolean tarjan(FType type) {
+		indices.put(type, index)
+		lowlink.put(type, index)
+		index = index + 1
+                
+        stack.push(type)
+
+        val directlyReferencedTypes = type.directlyReferencedTypes
+
+		for (referencedType : directlyReferencedTypes) {
+			if (!indices.containsKey(referencedType)) {
+				if (tarjan(referencedType))
+					return true
+
+				lowlink.put(
+					type,
+					Math::min(lowlink.get(type), lowlink.get(referencedType))
+				);
+			} else if (stack.contains(referencedType))
+				lowlink.put(
+					type,
+					Math::min(lowlink.get(type), indices.get(referencedType))
+				);
+		}
+
+		// if scc root and not on top of stack, then we have a cycle (scc size > 1)
+		if (lowlink.get(type) == indices.get(type) && !stack.pop().equals(type))
+			return true;
+
+		return false
+	}
+}
\ No newline at end of file
diff --git a/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeGenerator.xtend b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeGenerator.xtend
index 3c913c5..62e54aa 100644
--- a/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeGenerator.xtend
+++ b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FTypeGenerator.xtend
@@ -11,7 +11,6 @@ import java.util.Collection
 import java.util.HashSet
 import java.util.LinkedList
 import java.util.List
-import java.util.Set
 import javax.inject.Inject
 import org.eclipse.emf.common.util.EList
 import org.franca.core.franca.FArrayType
@@ -33,7 +32,7 @@ import org.genivi.commonapi.core.deployment.DeploymentInterfacePropertyAccessor
 import static com.google.common.base.Preconditions.*
 
 class FTypeGenerator {
-    @Inject private extension FrancaGeneratorExtensions
+    @Inject private extension FrancaGeneratorExtensions francaGeneratorExtensions
 
 
     def generateFTypeDeclarations(FTypeCollection fTypeCollection, DeploymentInterfacePropertyAccessor deploymentAccessor) '''
@@ -61,81 +60,15 @@ class FTypeGenerator {
     }
 
     def private hasNoCircularDependencies(EList<FType> types) {
-        for(currentType: types) {
-            var Set<FType> currentTypeSet = new HashSet<FType>
-            val Set<FType> fullDependencySet = new HashSet<FType>
-            currentTypeSet.add(currentType)
-            fullDependencySet.add(currentType)
-            while(!currentTypeSet.empty) {
-                currentTypeSet = currentTypeSet.map[it.directlyReferencedTypes].flatten.toSet
-                for(knownType: fullDependencySet) {
-                    if(currentTypeSet.contains(knownType)) {
-                        return false
-                    }
-                }
-                fullDependencySet.addAll(currentTypeSet)
-            }
-        }
-        return true
+    	val cycleDetector = new FTypeCycleDetector(francaGeneratorExtensions)
+    	return !cycleDetector.hasCycle(types)
     }
 
     def private List<FType> getReferencedTypes(FType fType) {
-        var references = fType.getDirectlyReferencedTypes
+        var references = fType.directlyReferencedTypes
         references.addAll(references.map[it.referencedTypes].flatten.toList)
         return references
     }
-    
-    def private dispatch List<FType> getDirectlyReferencedTypes(FStructType fType) {
-        var references = fType.elements.map[it.type.derived].filter[it != null].toList
-        if(fType.base != null) {
-            references.add(fType.base)
-        }
-        return references
-    }
-
-    def private dispatch List<FType> getDirectlyReferencedTypes(FEnumerationType fType) {
-        var references = new LinkedList<FType>()
-        if(fType.base != null) {
-            references.add(fType.base)
-        }
-        return references
-    }
-
-    def private dispatch List<FType> getDirectlyReferencedTypes(FArrayType fType) {
-        var references = new LinkedList<FType>()
-        if(fType.elementType.derived != null) {
-            references.add(fType.elementType.derived)
-        }
-        return references
-    }
-
-    def private dispatch List<FType> getDirectlyReferencedTypes(FUnionType fType) {
-        var references = fType.elements.map[it.type.derived].filter[it != null].toList
-        if(fType.base != null) {
-            references.add(fType.base)
-        }
-        return references
-    }
-
-    def private dispatch List<FType> getDirectlyReferencedTypes(FMapType fType) {
-        var references = new LinkedList<FType>()
-        if(fType.keyType.derived != null) {
-            references.add(fType.keyType.derived)
-        }
-        if(fType.valueType.derived != null) {
-            references.add(fType.valueType.derived)
-        }
-        return references
-    }
-
-    def private dispatch List<FType> getDirectlyReferencedTypes(FTypeDef fType) {
-        var references = new LinkedList<FType>()
-        if(fType.actualType.derived != null) {
-            references.add(fType.actualType.derived)
-        }
-        return references
-    }
-
 
     def dispatch generateFTypeDeclaration(FTypeDef fTypeDef, DeploymentInterfacePropertyAccessor deploymentAccessor) '''
         typedef «fTypeDef.actualType.getNameReference(fTypeDef.eContainer)» «fTypeDef.name»;
diff --git a/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FrancaGeneratorExtensions.xtend b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FrancaGeneratorExtensions.xtend
index 32e42f6..0d8d055 100644
--- a/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FrancaGeneratorExtensions.xtend
+++ b/org.genivi.commonapi.core/src/org/genivi/commonapi/core/generator/FrancaGeneratorExtensions.xtend
@@ -23,6 +23,7 @@ import org.franca.core.franca.FMethod
 import org.franca.core.franca.FModel
 import org.franca.core.franca.FModelElement
 import org.franca.core.franca.FStructType
+import org.franca.core.franca.FType
 import org.franca.core.franca.FTypeCollection
 import org.franca.core.franca.FTypeDef
 import org.franca.core.franca.FTypeRef
@@ -502,6 +503,51 @@ class FrancaGeneratorExtensions {
 
         return signature
     }
+
+	def List<FType> getDirectlyReferencedTypes(FType type) {
+		val directlyReferencedTypes = newLinkedList
+
+		directlyReferencedTypes.addFTypeDirectlyReferencedTypes(type)
+
+		return directlyReferencedTypes
+	}
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FStructType fType) {
+    	list.addAll(fType.elements.filter[type.derived != null].map[type.derived])
+
+        if (fType.base != null)
+        	list.add(fType.base)
+    }
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FEnumerationType fType) {
+        if (fType.base != null)
+            list.add(fType.base)
+    }
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FArrayType fType) {
+        if (fType.elementType.derived != null)
+        	list.add(fType.elementType.derived)
+    }
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FUnionType fType) {
+    	list.addAll(fType.elements.filter[type.derived != null].map[type.derived])
+
+        if (fType.base != null)
+            list.add(fType.base)
+    }
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FMapType fType) {
+        if (fType.keyType.derived != null)
+            list.add(fType.keyType.derived)
+
+        if (fType.valueType.derived != null)
+            list.add(fType.valueType.derived)
+    }
+
+    def private dispatch addFTypeDirectlyReferencedTypes(List<FType> list, FTypeDef fType) {
+        if (fType.actualType.derived != null)
+            list.add(fType.actualType.derived)
+    }
     
     def generateCppNamespace(FModel fModel) '''
         «fModel.namespaceAsList.map[toString].join("::")»::'''