Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00%
90 / 90
100.00%
12 / 12
 CRAP
100.00%
1 / 1
graph
100.00%
90 / 90
100.00%
12 / 12
 53
100.00%
1 / 1
 __construct
100.00%
2 / 2
100.00%
1 / 1
 1
 from_json
100.00%
4 / 4
100.00%
1 / 1
 2
 from_array
100.00%
13 / 13
100.00%
1 / 1
 10
 errors
100.00%
40 / 40
100.00%
1 / 1
 17
 is_valid
100.00%
1 / 1
100.00%
1 / 1
 1
 trigger
100.00%
4 / 4
100.00%
1 / 1
 3
 nodes
100.00%
1 / 1
100.00%
1 / 1
 1
 node
100.00%
4 / 4
100.00%
1 / 1
 3
 next
100.00%
5 / 5
100.00%
1 / 1
 5
 is_trigger
100.00%
1 / 1
100.00%
1 / 1
 1
 keys
100.00%
1 / 1
100.00%
1 / 1
 1
 has_cycle
100.00%
14 / 14
100.00%
1 / 1
 8
1<?php
2// This file is part of Moodle - https://moodle.org/
3//
4// Moodle is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// Moodle is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13//
14// You should have received a copy of the GNU General Public License
15// along with Moodle.  If not, see <https://www.gnu.org/licenses/>.
16
17declare(strict_types=1);
18
19namespace tool_autoflow\local\engine;
20
21/**
22 * A workflow graph: nodes and the edges between them, as saved by the editor.
23 *
24 * Validation follows the same rules as frontend/src/graph.ts. The editor checks
25 * them for quick feedback; this class checks them again because the server is the
26 * one that runs the workflow.
27 *
28 * @package    tool_autoflow
29 * @copyright  2026 DevLMS <contact@devlms.com>
30 * @license    https://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
31 */
32final class graph {
33    /** @var array[] Nodes in editor order: id, type, data. */
34    private array $nodes;
35
36    /** @var array[] Edges: source, target, handle. */
37    private array $edges;
38
39    /**
40     * Use from_array() or from_json().
41     *
42     * @param array[] $nodes
43     * @param array[] $edges
44     */
45    private function __construct(array $nodes, array $edges) {
46        $this->nodes = $nodes;
47        $this->edges = $edges;
48    }
49
50    /**
51     * Read a graph from the editor's JSON.
52     *
53     * @param string $json
54     * @return self
55     */
56    public static function from_json(string $json): self {
57        $data = json_decode($json, true);
58        if (!is_array($data)) {
59            throw new invalid_graph('The graph is not valid JSON.');
60        }
61        return self::from_array($data);
62    }
63
64    /**
65     * Read a graph from an array with nodes and edges.
66     *
67     * @param array $data
68     * @return self
69     */
70    public static function from_array(array $data): self {
71        if (!is_array($data['nodes'] ?? null) || !is_array($data['edges'] ?? null)) {
72            throw new invalid_graph('The graph needs a list of nodes and a list of edges.');
73        }
74        $nodes = [];
75        foreach ($data['nodes'] as $n) {
76            if (!is_string($n['id'] ?? null) || !is_string($n['type'] ?? null)) {
77                throw new invalid_graph('Every node in the graph needs a text id and type.');
78            }
79            $nodes[] = ['id' => $n['id'], 'type' => $n['type'], 'data' => is_array($n['data'] ?? null) ? $n['data'] : []];
80        }
81        $edges = [];
82        foreach ($data['edges'] as $e) {
83            if (!is_string($e['source'] ?? null) || !is_string($e['target'] ?? null)) {
84                throw new invalid_graph('Every edge in the graph needs a source and a target.');
85            }
86            $edges[] = ['source' => $e['source'], 'target' => $e['target'], 'handle' => $e['sourceHandle'] ?? null];
87        }
88        return new self($nodes, $edges);
89    }
90
91    /**
92     * Every problem that stops the graph from running. Empty means valid.
93     *
94     * @return array[] Each with a code and, for most codes, the node ids involved.
95     */
96    public function errors(): array {
97        $ids = [];
98        $duplicates = [];
99        foreach ($this->nodes as $n) {
100            if (isset($ids[$n['id']])) {
101                $duplicates[$n['id']] = true;
102            }
103            $ids[$n['id']] = true;
104        }
105
106        $triggers = array_values(array_map(
107            fn($n) => $n['id'],
108            array_filter($this->nodes, fn($n) => self::is_trigger($n['type']))
109        ));
110        if (!$triggers) {
111            return [['code' => 'notrigger']];
112        }
113        $errors = [];
114        if (count($triggers) > 1) {
115            $errors[] = ['code' => 'manytriggers', 'nodeids' => $triggers];
116        }
117        if ($duplicates) {
118            $errors[] = ['code' => 'duplicateid', 'nodeids' => self::keys($duplicates)];
119        }
120        $dangling = [];
121        foreach ($this->edges as $e) {
122            foreach ([$e['target'], $e['source']] as $end) {
123                if (!isset($ids[$end])) {
124                    $dangling[$end] = true;
125                }
126            }
127        }
128        if ($dangling) {
129            $errors[] = ['code' => 'danglingedge', 'nodeids' => self::keys($dangling)];
130        }
131        if ($errors) {
132            return $errors;
133        }
134
135        $next = array_fill_keys(array_keys($ids), []);
136        foreach ($this->edges as $e) {
137            $next[$e['source']][] = $e['target'];
138        }
139        if (self::has_cycle($next)) {
140            return [['code' => 'cycle']];
141        }
142
143        $reached = [$triggers[0] => true];
144        $queue = [$triggers[0]];
145        while ($queue) {
146            foreach ($next[array_shift($queue)] as $target) {
147                if (!isset($reached[$target])) {
148                    $reached[$target] = true;
149                    $queue[] = $target;
150                }
151            }
152        }
153        $unreachable = array_values(array_filter(self::keys($ids), fn($id) => !isset($reached[$id])));
154        return $unreachable ? [['code' => 'unreachable', 'nodeids' => $unreachable]] : [];
155    }
156
157    /**
158     * Whether the graph can run.
159     *
160     * @return bool
161     */
162    public function is_valid(): bool {
163        return $this->errors() === [];
164    }
165
166    /**
167     * The trigger node. Call on a valid graph.
168     *
169     * @return array
170     */
171    public function trigger(): array {
172        foreach ($this->nodes as $n) {
173            if (self::is_trigger($n['type'])) {
174                return $n;
175            }
176        }
177        throw new invalid_graph('The graph has no trigger.');
178    }
179
180    /**
181     * All nodes, in editor order.
182     *
183     * @return array[] Each with id, type and data.
184     */
185    public function nodes(): array {
186        return $this->nodes;
187    }
188
189    /**
190     * One node by id.
191     *
192     * @param string $id
193     * @return array
194     */
195    public function node(string $id): array {
196        foreach ($this->nodes as $n) {
197            if ($n['id'] === $id) {
198                return $n;
199            }
200        }
201        throw new invalid_graph("The graph has no node $id.");
202    }
203
204    /**
205     * Ids of the nodes to run after a node. Edges without a handle always follow;
206     * edges with a handle follow only when the node chose that branch.
207     *
208     * @param string $id
209     * @param string|null $branch
210     * @return string[]
211     */
212    public function next(string $id, ?string $branch): array {
213        $targets = [];
214        foreach ($this->edges as $e) {
215            if ($e['source'] === $id && ($e['handle'] === null || $e['handle'] === $branch)) {
216                $targets[] = $e['target'];
217            }
218        }
219        return $targets;
220    }
221
222    /**
223     * Whether a node type is a trigger.
224     *
225     * @param string $type
226     * @return bool
227     */
228    public static function is_trigger(string $type): bool {
229        return str_starts_with($type, 'trigger.');
230    }
231
232    /**
233     * Array keys as strings. PHP turns numeric string keys such as "1" into integers.
234     *
235     * @param array $array
236     * @return string[]
237     */
238    private static function keys(array $array): array {
239        return array_map('strval', array_keys($array));
240    }
241
242    /**
243     * Depth-first search: reaching a node that is still open means a cycle.
244     *
245     * @param array $next Adjacency list, node id to target ids.
246     * @return bool
247     */
248    private static function has_cycle(array $next): bool {
249        $state = [];
250        $visit = function (string $id) use (&$visit, &$state, $next): bool {
251            $state[$id] = 'open';
252            foreach ($next[$id] as $target) {
253                $s = $state[$target] ?? null;
254                if ($s === 'open' || ($s === null && $visit($target))) {
255                    return true;
256                }
257            }
258            $state[$id] = 'done';
259            return false;
260        };
261        foreach (array_keys($next) as $id) {
262            if (!isset($state[$id]) && $visit((string) $id)) {
263                return true;
264            }
265        }
266        return false;
267    }
268}