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 :)