config: validate if config is a DAG

[scriptnull]

The TOML configuration in waymond can have one or many DAGs https://en.wikipedia.org/wiki/Directed_acyclic_graph

We will need to validate this at the startup so that we avoid any cyclic chain of events going on inside waymond.

[legosandorigami]

@scriptnull

To verify if a configuration is a DAG, one could perform a depth first search and use a stack to detect back edges, which indicate the presence of cycles. Example Implementation:

func verifyDAG(connectors map[string]connector.Interface) bool {
	// Map to keep track of visited nodes
	visited := make(map[string]bool)
	// Map to track nodes currently in the recursion stack, indicating potential cycles
	stack := make(map[string]bool)
	
	// Iterate through all connectors
	for _, connector := range connectors {
		if !visited[connector.from] {
			if isCyclic(connector.from, connectors, visited, stack) {
				return false
			}
		}
	}
	return true
}

func isCyclic(node string, connectors map[string]connector.Interface, visited, stack map[string]bool) bool {
	visited[node] = true
	stack[node] = true

	// Iterate over all outgoing edges from the current node
	for _, connector := range connectors {
		if connector.from == node {
			if !visited[connector.to] && isCyclic(connector.to, connectors, visited, stack) {
				return true
			}
			// If the node is already in the recursion stack, a cycle is detected
			else if stack[connector.to] {
				return true
			}
		}
	}

	stack[node] = false
	return false
}

In this algorithm:

• visited[node] tracks whether a node has been fully processed.
• stack[node] is used to detect back edges, which occur when a node is revisited within the same DFS path, indicating a cycle.

However, since the fields connector.to and connector.from are not exported, this approach cannot be used to verify if the config is a DAG from the main package. My understanding is that this verification should be done in the main function immediately after the config parsing is complete.

I also wanted to provide a test case to illustrate this:

I have some ideas for implementing the http_client and http_endpoint triggers. I would like to take on this implementation myself, but I would appreciate the opportunity to discuss and clarify a few points. Would it be possible for us to have a discussion about this?

[scriptnull]

Hi @legosandorigami, thanks for the proposal. Feel free to open a pull request and I will get the patch merged in after a round of review. For http_client and http_endpoint triggers, I propose we discuss it by opening new GitHub issues :)