telltale-runtime 17.0.0

Choreographic programming for Telltale - effect-based distributed protocols
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

//! Graph algorithms for choreographic protocol analysis.

use crate::ast::{Protocol, Role};
use std::collections::{HashMap, HashSet};

pub(super) fn has_cycle(graph: &HashMap<Role, HashSet<Role>>) -> bool {
    let mut visited = HashSet::new();
    let mut rec_stack = HashSet::new();

    for node in graph.keys() {
        if !visited.contains(node) && dfs_cycle(node, graph, &mut visited, &mut rec_stack) {
            return true;
        }
    }

    false
}

fn dfs_cycle(
    node: &Role,
    graph: &HashMap<Role, HashSet<Role>>,
    visited: &mut HashSet<Role>,
    rec_stack: &mut HashSet<Role>,
) -> bool {
    visited.insert(node.clone());
    rec_stack.insert(node.clone());

    if let Some(neighbors) = graph.get(node) {
        for neighbor in neighbors {
            if !visited.contains(neighbor) {
                if dfs_cycle(neighbor, graph, visited, rec_stack) {
                    return true;
                }
            } else if rec_stack.contains(neighbor) {
                return true;
            }
        }
    }

    rec_stack.remove(node);
    false
}

// RECURSION_SAFE: structural recursion over finite protocol AST depth.
pub(super) fn has_communication(protocol: &Protocol) -> bool {
    match protocol {
        Protocol::Send { .. } | Protocol::Broadcast { .. } => true,
        Protocol::Choice { branches, .. } => {
            branches.iter().any(|b| has_communication(&b.protocol))
        }
        Protocol::Case { branches, .. } => branches.iter().any(|b| has_communication(&b.protocol)),
        Protocol::Timeout {
            body,
            on_timeout,
            on_cancel,
            ..
        } => {
            has_communication(body)
                || has_communication(on_timeout)
                || on_cancel.as_deref().is_some_and(has_communication)
        }
        Protocol::Loop { body, .. } => has_communication(body),
        Protocol::Parallel { protocols } => protocols.iter().any(has_communication),
        Protocol::Rec { body, .. } => has_communication(body),
        Protocol::Var(_) | Protocol::End => false,
        Protocol::Begin { continuation, .. }
        | Protocol::Await { continuation, .. }
        | Protocol::Resolve { continuation, .. }
        | Protocol::Invalidate { continuation, .. }
        | Protocol::Extension { continuation, .. }
        | Protocol::Let { continuation, .. }
        | Protocol::Publish { continuation, .. }
        | Protocol::PublishAuthority { continuation, .. }
        | Protocol::Materialize { continuation, .. }
        | Protocol::Handoff { continuation, .. }
        | Protocol::DependentWork { continuation, .. } => has_communication(continuation),
    }
}