From 42bea4afb523db0215fc2446b078c6c1824ee1ea Mon Sep 17 00:00:00 2001 From: Jozsef Csongvai Date: Sun, 14 Mar 2021 19:13:35 -0400 Subject: Prohibit cycles in imperative workflows Issue-ID: CCSDK-3221 Change-Id: I767003dde40c0fc53a673c4a41cb2430624d7b04 Signed-off-by: Jozsef Csongvai (cherry picked from commit 2c7207526c37166a0d0ccc5008aaae0ae325064e) --- .../core/GraphExtensionFunctions.kt | 37 ++++++++--- .../core/data/BlueprintGraph.kt | 6 +- .../core/GraphExtensionFunctionsTest.kt | 71 ++++++++++++++++++++++ .../workflow/ImperativeWorkflowExecutionService.kt | 6 ++ 4 files changed, 107 insertions(+), 13 deletions(-) (limited to 'ms/blueprintsprocessor') 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 { 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 = emptyList( .flatMap { findAllPaths(it.id, to, path + from) } } -fun Graph.findCycles(node: String): List> { - fun findCycles(path: List): List> { - 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> = toAdjacencyList().entries + .associate { it.node to it.links } + .mapValues { it.value.map { x -> x.node }.toSet() } + + fun hasCycle(node: String, visited: MutableSet = 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 = ArrayList() - fun neighbors(): List = edges.map { edge -> edge.target(this) } + fun neighbors(): List = edges.map { it.target } fun neighbors(label: EdgeLabel): List = edges.filter { it.label == label } - .map { edge -> edge.target(this) } + .map { it.target } fun labelEdges(label: EdgeLabel): List = 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() + ) + } } diff --git a/ms/blueprintsprocessor/modules/services/workflow-service/src/main/kotlin/org/onap/ccsdk/cds/blueprintsprocessor/services/workflow/ImperativeWorkflowExecutionService.kt b/ms/blueprintsprocessor/modules/services/workflow-service/src/main/kotlin/org/onap/ccsdk/cds/blueprintsprocessor/services/workflow/ImperativeWorkflowExecutionService.kt index 2278dbfb4..561136a87 100644 --- a/ms/blueprintsprocessor/modules/services/workflow-service/src/main/kotlin/org/onap/ccsdk/cds/blueprintsprocessor/services/workflow/ImperativeWorkflowExecutionService.kt +++ b/ms/blueprintsprocessor/modules/services/workflow-service/src/main/kotlin/org/onap/ccsdk/cds/blueprintsprocessor/services/workflow/ImperativeWorkflowExecutionService.kt @@ -23,6 +23,7 @@ import org.onap.ccsdk.cds.blueprintsprocessor.core.api.data.ExecutionServiceOutp import org.onap.ccsdk.cds.blueprintsprocessor.core.api.data.Status import org.onap.ccsdk.cds.controllerblueprints.common.api.EventType import org.onap.ccsdk.cds.controllerblueprints.core.BlueprintConstants +import org.onap.ccsdk.cds.controllerblueprints.core.BlueprintException import org.onap.ccsdk.cds.controllerblueprints.core.BlueprintProcessorException import org.onap.ccsdk.cds.controllerblueprints.core.MDCContext import org.onap.ccsdk.cds.controllerblueprints.core.asGraph @@ -30,6 +31,7 @@ import org.onap.ccsdk.cds.controllerblueprints.core.checkNotEmpty import org.onap.ccsdk.cds.controllerblueprints.core.data.EdgeLabel import org.onap.ccsdk.cds.controllerblueprints.core.data.Graph import org.onap.ccsdk.cds.controllerblueprints.core.interfaces.BlueprintWorkflowExecutionService +import org.onap.ccsdk.cds.controllerblueprints.core.isAcyclic import org.onap.ccsdk.cds.controllerblueprints.core.logger import org.onap.ccsdk.cds.controllerblueprints.core.service.AbstractBlueprintWorkFlowService import org.onap.ccsdk.cds.controllerblueprints.core.service.BlueprintRuntimeService @@ -57,6 +59,10 @@ class ImperativeWorkflowExecutionService( val graph = bluePrintContext.workflowByName(workflowName).asGraph() + if (!graph.isAcyclic()) { + throw BlueprintException("Imperative workflow must be acyclic. Check on_success/on_failure for circular references") + } + return coroutineScope { ImperativeBlueprintWorkflowService( nodeTemplateExecutionService, -- cgit 1.2.3-korg