Prohibit cycles in imperative workflows

Issue-ID: CCSDK-3221
Change-Id: I767003dde40c0fc53a673c4a41cb2430624d7b04
Signed-off-by: Jozsef Csongvai <jozsef.csongvai@bell.ca>

3 files changed, 101 insertions, 13 deletions

diff --git a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt
index 5995a8a9e..26f74669e 100644
--- a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt
+++ b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctions.kt
@@ -33,7 +33,7 @@ fun String.toGraph(): Graph {
     if (!startsWith('[') || !endsWith(']')) {
         throw IllegalArgumentException("Expected string starting '[' and ending with ']' but it was '$")
     }
-    val tokens = substring(1, length - 1).split(", ").map { it.split(graphTokenSeparators) }
+    val tokens = substring(1, length - 1).replace("\n", "").split(", ").map { it.trim().split(graphTokenSeparators) }
     val nodes = tokens.flatMap { it.take(2) }.toCollection(LinkedHashSet())
     val edges = tokens.filter { it.size == 3 }.map { Graph.TermForm.Term(it[0], it[1], EdgeLabel.valueOf(it[2])) }
     return Graph.labeledDirectedTerms(Graph.TermForm(nodes, edges))
@@ -41,7 +41,7 @@ fun String.toGraph(): Graph {
 
 fun Graph.toAdjacencyList(): Graph.AdjacencyList<String, EdgeLabel> {
     val entries = nodes.values.map { node ->
-        val links = node.edges.map { Graph.AdjacencyList.Link(it.target(node).id, it.label) }
+        val links = node.edges.map { Graph.AdjacencyList.Link(it.target.id, it.label) }
         Graph.AdjacencyList.Entry(node = node.id, links = links)
     }
     return Graph.AdjacencyList(entries)
@@ -54,14 +54,33 @@ fun Graph.findAllPaths(from: String, to: String, path: List<String> = emptyList(
         .flatMap { findAllPaths(it.id, to, path + from) }
 }
 
-fun Graph.findCycles(node: String): List<List<String>> {
-    fun findCycles(path: List<String>): List<List<String>> {
-        if (path.size > 3 && path.first() == path.last()) return listOf(path)
-        return nodes[path.last()]!!.neighbors()
-            .filterNot { path.tail().contains(it.id) }
-            .flatMap { findCycles(path + it.id) }
+fun Graph.isAcyclic(): Boolean {
+    val startNodes = startNodes()
+    if (startNodes.isEmpty())
+        return false
+
+    val adj: Map<String, Set<String>> = toAdjacencyList().entries
+        .associate { it.node to it.links }
+        .mapValues { it.value.map { x -> x.node }.toSet() }
+
+    fun hasCycle(node: String, visited: MutableSet<String> = mutableSetOf()): Boolean {
+        if (visited.contains(node))
+            return true
+        visited.add(node)
+
+        if (adj[node]!!.isEmpty()) {
+            visited.remove(node)
+            return false
+        }
+
+        if (adj[node]!!.any { hasCycle(it, visited) })
+            return true
+
+        visited.remove(node)
+        return false
     }
-    return findCycles(listOf(node))
+
+    return startNodes.none { n -> hasCycle(n.id) }
 }
 
 fun Graph.startNodes() = this.nodes.values.filter {
diff --git a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BlueprintGraph.kt b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BlueprintGraph.kt
index b833db755..bc6cbe426 100644
--- a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BlueprintGraph.kt
+++ b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/main/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/data/BlueprintGraph.kt
@@ -97,10 +97,10 @@ class Graph {
 
         val edges: MutableList<Edge> = ArrayList()
 
-        fun neighbors(): List<Node> = edges.map { edge -> edge.target(this) }
+        fun neighbors(): List<Node> = edges.map { it.target }
 
         fun neighbors(label: EdgeLabel): List<Node> = edges.filter { it.label == label }
-            .map { edge -> edge.target(this) }
+            .map { it.target }
 
         fun labelEdges(label: EdgeLabel): List<Edge> = edges.filter { it.label == label }
 
@@ -114,8 +114,6 @@ class Graph {
         var status: EdgeStatus = EdgeStatus.NOT_STARTED
     ) {
 
-        fun target(node: Node): Node = target
-
         fun equivalentTo(other: Edge) =
             (source == other.source && target == other.target) ||
                 (source == other.target && target == other.source)
diff --git a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt
index 86cb473ae..ba4115f02 100644
--- a/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt
+++ b/ms/blueprintsprocessor/modules/blueprints/blueprint-core/src/test/kotlin/org/onap/ccsdk/cds/controllerblueprints/core/GraphExtensionFunctionsTest.kt
@@ -18,7 +18,9 @@ package org.onap.ccsdk.cds.controllerblueprints.core
 
 import org.junit.Test
 import org.onap.ccsdk.cds.controllerblueprints.core.data.EdgeLabel
+import kotlin.test.assertFalse
 import kotlin.test.assertNotNull
+import kotlin.test.assertTrue
 
 class GraphExtensionFunctionsTest {
 
@@ -34,4 +36,73 @@ class GraphExtensionFunctionsTest {
         val nodePath = graph.nodes["p"]!!.neighbors(EdgeLabel.SUCCESS)
         assertNotNull(nodePath, "failed to nodePath from graph for 'p' node 'SUCCESS' label")
     }
+
+    @Test
+    fun `isAcyclic should return false`() {
+        assertFalse(
+            """[
+             assign>deploy/SUCCESS,
+             deploy>assign/FAILURE
+         ]""".toGraph().isAcyclic()
+        )
+
+        assertFalse(
+            """[
+             assign>deploy/SUCCESS,
+             deploy>recover/FAILURE,
+             recover>deploy/SUCCESS
+         ]""".toGraph().isAcyclic()
+        )
+
+        assertFalse(
+            """[
+             assign>deploy/SUCCESS,
+             assign>recover/FAILURE,
+             recover>deploy/SUCCESS,
+             deploy>finalize/SUCCESS,
+             deploy>recover/FAILURE
+         ]""".toGraph().isAcyclic()
+        )
+
+        assertFalse(
+            """[
+             A>B/SUCCESS,
+             A>C/SUCCESS,
+             B>E/SUCCESS,
+             B>D/FAILURE,
+             D>B/FAILURE,
+             C>E/SUCCESS
+         ]""".toGraph().isAcyclic()
+        )
+    }
+
+    @Test
+    fun `isAcyclic should return true`() {
+        assertTrue(
+            """[
+             assign>deploy/SUCCESS,
+             deploy>recover/FAILURE
+         ]""".toGraph().isAcyclic()
+        )
+
+        assertTrue(
+            """[
+             A>C/SUCCESS,
+             A>B/FAILURE,
+             C>B/SUCCESS
+         ]""".toGraph().isAcyclic()
+        )
+
+        assertTrue(
+            """[
+             assign>execute1/SUCCESS,
+             assign>execute2/SUCCESS,
+             execute1>finalize/SUCCESS,
+             execute2>finalize/SUCCESS,
+             execute1>cleanup/FAILURE,
+             execute2>cleanup/FAILURE,
+             finalize>cleanup/SUCCESS
+         ]""".toGraph().isAcyclic()
+        )
+    }
 }