VLink  2.3.0
A high-performance communication middleware
graph_task.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2026 by Thun Lu. All rights reserved.
3  * Author: Thun Lu <thun.lu@zohomail.cn>
4  * Repo: https://github.com/thun-res/vlink
5  * _ __ __ _ __
6  * | | / / / / (_) ____ / /__
7  * | | / / / / / / / __ \ / //_/
8  * | |/ / / /___ / / / / / / / ,<
9  * |___/ /_____/ /_/ /_/ /_/ /_/|_|
10  *
11  * Licensed under the Apache License, Version 2.0 (the "License");
12  * you may not use this file except in compliance with the License.
13  * You may obtain a copy of the License at
14  *
15  * http://www.apache.org/licenses/LICENSE-2.0
16  *
17  * Unless required by applicable law or agreed to in writing, software
18  * distributed under the License is distributed on an "AS IS" BASIS,
19  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20  * See the License for the specific language governing permissions and
21  * limitations under the License.
22  */
23 
24 /**
25  * @file graph_task.h
26  * @brief Directed acyclic task graph with condition branching, cycle guard and DOT export.
27  *
28  * @details
29  * @c GraphTask is VLink's data-flow primitive: every node carries a callback, a list of
30  * predecessors and a list of successors, and is submitted to any engine that exposes
31  * @c post_task / @c post_task_with_priority -- @c MessageLoop, @c MultiLoop or @c ThreadPool.
32  * Edges are declared with @c precede / @c succeed (Taskflow convention) and a process-wide
33  * topology mutex serialises all mutators across every graph instance.
34  *
35  * @par DAG diagram
36  *
37  * @verbatim
38  * +---+ precede +---+ precede +---+
39  * | A | ----------> | B | ----------> | C |
40  * +-+-+ +-+-+ +-+-+
41  * | condition | |
42  * v v v
43  * +-----+ +-----+ +-----+
44  * | D0 | | E | | F |
45  * +-----+ +-----+ +-----+
46  * ^
47  * | D0/D1/... condition task selects which successor branch fires
48  * +-----+
49  * | D1 |
50  * +-----+
51  * @endverbatim
52  *
53  * @par Task factories
54  *
55  * | Factory | Callback signature | Use case |
56  * | ----------------------------- | ------------------- | ------------------------------------- |
57  * | @c create(callback) | @c void() | Regular work node |
58  * | @c create_condition(callback) | @c int() | Branch selector (return value picks) |
59  *
60  * @par Execution policies
61  *
62  * | Policy | Behaviour |
63  * | ------------------ | ------------------------------------------------------------------ |
64  * | @c kPolicyOnce | Runs exactly once per @c execute pass (default) |
65  * | @c kPolicyMultiple | Runs multiple times within one @c execute pass |
66  * | @c kPolicyWaitAll | Waits for every predecessor before running |
67  *
68  * @par Example
69  * @code
70  * vlink::MultiLoop engine(4);
71  * engine.async_run();
72  *
73  * auto load = vlink::GraphTask::create("load", [] { load_data(); });
74  * auto proc = vlink::GraphTask::create("proc", [] { process(); });
75  * auto save = vlink::GraphTask::create("save", [] { save_data(); });
76  *
77  * // load -- > proc means load->precede(proc); produces execution order load, proc, save.
78  * load-- > proc-- > save;
79  *
80  * assert(!load->has_cycle());
81  * load->execute(&engine);
82  * @endcode
83  */
84 
85 #pragma once
86 
87 #include <memory>
88 #include <optional>
89 #include <string>
90 #include <type_traits>
91 #include <unordered_set>
92 #include <utility>
93 #include <vector>
94 
95 #include "./functional.h"
96 #include "./macros.h"
97 #include "./traits.h"
98 
99 namespace vlink {
100 
101 /**
102  * @class GraphTask
103  * @brief DAG node carrying a callback, predecessor and successor links, and run-time state.
104  *
105  * @details
106  * Must be created through the @c create / @c create_condition factories so callbacks share
107  * @c std::enable_shared_from_this safely. @c execute traverses the reachable sub-graph and
108  * submits ready tasks to a user-supplied engine.
109  */
110 class VLINK_EXPORT GraphTask final : public std::enable_shared_from_this<GraphTask> {
111  private:
112  /**
113  * @brief Passkey used to restrict construction to the static factory functions.
114  *
115  * @details
116  * The token type and its default constructor are private. A factory creates the token and
117  * forwards it through @c std::allocate_shared; callers cannot name or create a token and
118  * therefore cannot invoke the token-gated constructors directly.
119  */
120  class PrivateToken final {
121  private:
122  PrivateToken() = default;
123 
124  friend class GraphTask;
125  };
126 
127  public:
128  /**
129  * @brief Run-time execution state of a node within an @c execute pass.
130  */
131  enum Status : uint8_t {
132  kStatusInActive = 0, ///< Not yet submitted or cancelled.
133  kStatusPending = 1, ///< Waiting for predecessors to complete.
134  kStatusRunning = 2, ///< Currently executing.
135  kStatusDone = 3, ///< Execution finished.
136  };
137 
138  /**
139  * @brief Policy controlling how many times the task may run within a pass.
140  */
141  enum Policy : uint8_t {
142  kPolicyOnce = 0, ///< Run exactly once per @c execute pass (default).
143  kPolicyMultiple = 1, ///< Allow multiple invocations within the pass.
144  kPolicyWaitAll = 2, ///< Wait for every predecessor before running.
145  };
146 
147  /**
148  * @brief Callback type for void-returning work nodes.
149  */
150  using Callback = MoveFunction<void()>;
151 
152  /**
153  * @brief Callback type for condition nodes; the return value selects an outgoing branch.
154  */
156 
157  /**
158  * @brief Status-change notification callback.
159  *
160  * @details
161  * Invoked with the task name and the new status whenever the node transitions.
162  */
163  using StatusCallback = MoveFunction<void(const std::string&, Status)>;
164 
165  /**
166  * @brief Creates a regular work node.
167  *
168  * @param callback Work function.
169  * @param condition_number Incoming branch value required to activate this node.
170  * @return Shared pointer to the new task.
171  */
172  [[nodiscard]] static std::shared_ptr<GraphTask> create(Callback&& callback, int condition_number = 0);
173 
174  /**
175  * @brief Creates a named regular work node.
176  *
177  * @param name Node name used in DOT output and status callbacks.
178  * @param callback Work function.
179  * @param condition_number Incoming branch value required to activate this node.
180  * @return Shared pointer to the new task.
181  */
182  [[nodiscard]] static std::shared_ptr<GraphTask> create(const std::string& name, Callback&& callback,
183  int condition_number = 0);
184 
185  /**
186  * @brief Creates a condition node whose return value selects a successor branch.
187  *
188  * @param callback Predicate returning the branch index.
189  * @param condition_number Incoming branch value required to activate this node.
190  * @return Shared pointer to the new condition task.
191  */
192  [[nodiscard]] static std::shared_ptr<GraphTask> create_condition(ConditionCallback&& callback,
193  int condition_number = 0);
194 
195  /**
196  * @brief Creates a named condition node.
197  *
198  * @param name Node name.
199  * @param callback Predicate returning the branch index.
200  * @param condition_number Incoming branch value required to activate this node.
201  * @return Shared pointer to the new condition task.
202  */
203  [[nodiscard]] static std::shared_ptr<GraphTask> create_condition(const std::string& name,
204  ConditionCallback&& callback,
205  int condition_number = 0);
206 
207  /// @cond INTERNAL
208  /**
209  * @brief Factory-only private constructor for a regular task.
210  *
211  * @details This constructor is private at the API level but declared in the public section so
212  * Android libc++ can perform in-place construction inside the @c std::allocate_shared control
213  * block. Callers cannot invoke it because they cannot create the private @p token.
214  */
215  explicit GraphTask(PrivateToken token, Callback&& callback, int condition_number);
216 
217  /**
218  * @brief Factory-only private constructor for a named regular task.
219  *
220  * @details Declared in the public section only for @c std::allocate_shared. Callers cannot
221  * invoke it because they cannot create the private @p token.
222  */
223  explicit GraphTask(PrivateToken token, const std::string& name, Callback&& callback, int condition_number);
224 
225  /**
226  * @brief Factory-only private constructor for a condition task.
227  *
228  * @details Declared in the public section only for @c std::allocate_shared. Callers cannot
229  * invoke it because they cannot create the private @p token.
230  */
231  explicit GraphTask(PrivateToken token, ConditionCallback&& callback, int condition_number);
232 
233  /**
234  * @brief Factory-only private constructor for a named condition task.
235  *
236  * @details Declared in the public section only for @c std::allocate_shared. Callers cannot
237  * invoke it because they cannot create the private @p token.
238  */
239  explicit GraphTask(PrivateToken token, const std::string& name, ConditionCallback&& callback, int condition_number);
240 
241  /**
242  * @brief Destroys the task.
243  *
244  * @details Public because the @c std::allocate_shared control block performs destruction.
245  * Instances must still be created by @c create or @c create_condition and owned by
246  * @c std::shared_ptr; callers must not destroy the managed pointer directly.
247  */
248  ~GraphTask();
249  /// @endcond
250 
251  /**
252  * @brief Submits the reachable sub-graph to @p graph_engine.
253  *
254  * @details
255  * Traverses the sub-graph, identifies ready nodes and posts them via @c post_task or
256  * @c post_task_with_priority when available. Compatible with @c MessageLoop, @c MultiLoop and
257  * @c ThreadPool.
258  *
259  * @tparam GraphEngineT Engine type exposing @c post_task and optionally @c post_task_with_priority.
260  * @param graph_engine Target engine instance.
261  */
262  template <class GraphEngineT>
263  void execute(GraphEngineT* graph_engine);
264 
265  /**
266  * @brief Cancels this node and propagates the cancellation downstream.
267  *
268  * @details
269  * Sets this node's status to @c kStatusInActive and walks the successor list forward marking
270  * every reachable node inactive. Predecessors are unaffected. Inactive nodes are skipped
271  * by the engine and by downstream @c kPolicyWaitAll counters.
272  */
273  void cancel();
274 
275  /**
276  * @brief Declares that this node must complete before @p task starts.
277  *
278  * @details
279  * Runs a reachability pre-check on @p task 's downstream cone before mutating any list; the
280  * edge is rejected (with an error log) if it would form a cycle. On success @p task is
281  * appended to this node's successor list and this node is appended to @p task 's predecessor
282  * list. Topology mutation is serialised by a process-wide recursive mutex shared across
283  * every @c GraphTask instance, so concurrent writers are safe; read paths (@c execute,
284  * @c has_cycle, @c export_to_dot) read per-node snapshots without taking that mutex.
285  *
286  * A rejected cycle is only logged, because a cycle is a legitimate run-time topology the
287  * caller may probe for. Misuse of the call itself -- a null or self @p task, or an edge that
288  * already exists -- is reported as a fatal log and therefore throws.
289  *
290  * @param task Successor node.
291  * @throws vlink::Exception::RuntimeError if @p task is null, is this node, or the edge
292  * already exists.
293  */
294  void precede(const std::shared_ptr<GraphTask>& task);
295 
296  /**
297  * @brief Declares that @p task must complete before this node starts.
298  *
299  * @details
300  * Mirror of @c precede; rejects edges that would form a cycle. Shares the same single-writer
301  * topology mutex as @c precede, and reports the same misuse cases as fatal.
302  *
303  * @param task Predecessor node.
304  * @throws vlink::Exception::RuntimeError if @p task is null, is this node, or the edge
305  * already exists.
306  */
307  void succeed(const std::shared_ptr<GraphTask>& task);
308 
309  /**
310  * @brief Subscribes a callback to status transitions on this node.
311  *
312  * @details
313  * Each call appends a new subscriber. On every status change the node snapshots the current
314  * subscriber set under @c status_callbacks_mtx, releases the lock, then invokes the snapshot
315  * in unspecified order. Because callbacks fire without the mutex held they may freely
316  * register / unregister callbacks on the same node; such mutations apply on the next
317  * transition. Exceptions are caught and logged; remaining subscribers still fire.
318  *
319  * @param callback Status change callback.
320  * @return Subscription id (>0). Returns @c 0 when @p callback is empty.
321  */
323 
324  /**
325  * @brief Removes a previously registered status callback by id.
326  *
327  * @param id Subscription id returned by @c register_status_callback.
328  * @return @c true when the subscription was found and removed.
329  */
330  bool unregister_status_callback(uint32_t id);
331 
332  /**
333  * @brief Removes every status callback subscription on this node.
334  */
336 
337  /**
338  * @brief Sets the node name used in DOT output and status callbacks.
339  *
340  * @param name Node name.
341  */
342  void set_name(const std::string& name);
343 
344  /**
345  * @brief Sets a group name used to visually cluster nodes in DOT output.
346  *
347  * @param name Group name.
348  */
349  void set_group_name(const std::string& name);
350 
351  /**
352  * @brief Sets the incoming branch value required to activate this node.
353  *
354  * @param condition_number Incoming branch value required to activate this node.
355  */
356  void set_condition_number(int condition_number);
357 
358  /**
359  * @brief Sets the dispatch priority used by priority-aware engines.
360  *
361  * @param priority Priority value.
362  */
363  void set_priority(uint16_t priority);
364 
365  /**
366  * @brief Sets the maximum recursion depth that bounds DFS traversals.
367  *
368  * @details
369  * Traversals exceeding this depth treat the graph as conservatively cyclic. Default: @c 10000.
370  *
371  * @param depth Maximum recursion depth.
372  */
373  void set_max_recursion_depth(uint32_t depth);
374 
375  /**
376  * @brief Sets the execution policy for this node.
377  *
378  * @param policy Policy enumerator.
379  */
380  void set_policy(Policy policy);
381 
382  /**
383  * @brief Returns the node name.
384  *
385  * @return Node name.
386  */
387  [[nodiscard]] std::string get_name() const;
388 
389  /**
390  * @brief Returns the group name.
391  *
392  * @return Group name.
393  */
394  [[nodiscard]] std::string get_group_name() const;
395 
396  /**
397  * @brief Returns the incoming branch value required to activate this node.
398  *
399  * @return Incoming branch value required to activate this node.
400  */
401  [[nodiscard]] int get_condition_number() const;
402 
403  /**
404  * @brief Returns the configured dispatch priority.
405  *
406  * @return Priority value.
407  */
408  [[nodiscard]] uint16_t get_priority() const;
409 
410  /**
411  * @brief Returns the maximum recursion depth used for cycle detection.
412  *
413  * @return Recursion depth bound.
414  */
415  [[nodiscard]] uint32_t get_max_recursion_depth() const;
416 
417  /**
418  * @brief Returns the configured execution policy.
419  *
420  * @return Policy enumerator.
421  */
422  [[nodiscard]] Policy get_policy() const;
423 
424  /**
425  * @brief Returns the current execution status of this node.
426  *
427  * @return Status enumerator.
428  */
429  [[nodiscard]] Status get_status() const;
430 
431  /**
432  * @brief Removes an outgoing edge created by @c precede.
433  *
434  * @details
435  * Removes @p task from the successor list and removes this node from @p task 's predecessor
436  * list.
437  *
438  * @param task Previously attached successor.
439  * @throws vlink::Exception::RuntimeError if @p task is null or the edge does not exist.
440  */
441  void remove_precede_task(const std::shared_ptr<GraphTask>& task);
442 
443  /**
444  * @brief Removes an incoming edge created by @c succeed.
445  *
446  * @details
447  * Mirror of @c remove_precede_task. A missing edge is tolerated here; only a null @p task
448  * is reported as fatal.
449  *
450  * @param task Previously attached predecessor.
451  * @throws vlink::Exception::RuntimeError if @p task is null.
452  */
453  void remove_succeed_task(const std::shared_ptr<GraphTask>& task);
454 
455  /**
456  * @brief Returns the current predecessor list as weak pointers.
457  *
458  * @return Vector of weak predecessor pointers.
459  */
460  [[nodiscard]] std::vector<std::weak_ptr<GraphTask>> get_precede_task_list() const;
461 
462  /**
463  * @brief Returns the current successor list as weak pointers.
464  *
465  * @return Vector of weak successor pointers.
466  */
467  [[nodiscard]] std::vector<std::weak_ptr<GraphTask>> get_succeed_task_list() const;
468 
469  /**
470  * @brief Reports whether this node was created via @c create_condition.
471  *
472  * @return @c true for condition nodes.
473  */
474  [[nodiscard]] bool is_condition_task() const;
475 
476  /**
477  * @brief Detects whether the reachable sub-graph contains a cycle.
478  *
479  * @details
480  * Iterative DFS with a recursion stack. Acquires per-node mutexes one at a time and does
481  * not take the global topology mutex; safe to call from status callbacks fired by @c invoke
482  * or @c cancel.
483  *
484  * @return @c true when a cycle is found or the recursion bound is exceeded.
485  */
486  [[nodiscard]] bool has_cycle() const;
487 
488  /**
489  * @brief Exports the reachable sub-graph as a Graphviz DOT document.
490  *
491  * @return DOT source string.
492  */
493  [[nodiscard]] std::string export_to_dot() const;
494 
495  private:
496  template <typename TypeT>
497  struct SharedAllocator;
498 
499  std::vector<std::shared_ptr<GraphTask>> prepare_execution();
500 
501  std::optional<int> invoke(bool once);
502 
503  void set_ready_callback(Callback&& callback);
504 
505  void notify(int condition_number, bool first_invocation = true);
506 
507  void notify_skip();
508 
509  bool mark_predecessor_satisfied(bool active, bool* has_active, bool first_invocation = true);
510 
511  bool mark_ready(bool enable);
512 
513  void update_status(Status status);
514 
515  bool detect_cycle(const GraphTask* task, std::unordered_set<const GraphTask*>& visited,
516  std::unordered_set<const GraphTask*>& recursion_stack, uint32_t& depth, uint32_t max_depth) const;
517 
518  bool reaches_via_successors(const GraphTask* start_node,
519  const std::vector<std::weak_ptr<GraphTask>>& start_successors,
520  const GraphTask* target) const;
521 
522  static void clear_invalid_task(const std::shared_ptr<GraphTask>& task);
523 
524  struct Impl;
525  std::unique_ptr<Impl> impl_;
526 
528 };
529 
530 /**
531  * @typedef GraphTaskPtr
532  * @brief Convenience alias for the canonical @c shared_ptr<GraphTask> handle.
533  */
534 using GraphTaskPtr = std::shared_ptr<GraphTask>;
535 
536 ////////////////////////////////////////////////////////////////
537 /// Details
538 ////////////////////////////////////////////////////////////////
539 
540 template <class GraphEngineT>
541 inline void GraphTask::execute(GraphEngineT* graph_engine) {
542  auto self = shared_from_this();
543  auto tasks = std::make_shared<std::vector<std::shared_ptr<GraphTask>>>(prepare_execution());
544  std::weak_ptr<std::vector<std::shared_ptr<GraphTask>>> weak_tasks = tasks;
545 
546  for (const auto& task : *tasks) {
547  task->set_ready_callback([weak_tasks, node = task.get(), graph_engine]() {
548  auto tasks = weak_tasks.lock();
549 
550  if VUNLIKELY (!tasks) {
551  return;
552  }
553 
554  constexpr bool kHaspriority =
555  VLINK_HAS_MEMBER(GraphEngineT, post_task_with_priority(std::declval<Callback>(), std::declval<uint16_t>()));
556  [[maybe_unused]] constexpr uint8_t kPriorityType = 2;
557 
558  if VUNLIKELY (node->get_status() == kStatusInActive) {
559  return;
560  }
561 
562  auto task_func = [tasks, node]() {
563  auto ret = node->invoke(true);
564 
565  if VLIKELY (ret.has_value()) {
566  node->notify(*ret);
567  }
568  };
569 
570  auto post_task = [graph_engine](auto&& func) -> bool {
571  using Ret = decltype(graph_engine->post_task(std::forward<decltype(func)>(func)));
572 
573  if constexpr (std::is_same_v<Ret, bool>) {
574  return graph_engine->post_task(std::forward<decltype(func)>(func));
575  } else {
576  graph_engine->post_task(std::forward<decltype(func)>(func));
577  return true;
578  }
579  };
580 
581  bool posted = false;
582 
583  if constexpr (kHaspriority) {
584  auto post_task_with_priority = [graph_engine, node](auto&& func) -> bool {
585  using Ret =
586  decltype(graph_engine->post_task_with_priority(std::forward<decltype(func)>(func), node->get_priority()));
587 
588  if constexpr (std::is_same_v<Ret, bool>) {
589  return graph_engine->post_task_with_priority(std::forward<decltype(func)>(func), node->get_priority());
590  } else {
591  graph_engine->post_task_with_priority(std::forward<decltype(func)>(func), node->get_priority());
592  return true;
593  }
594  };
595 
596  if constexpr (VLINK_HAS_MEMBER(GraphEngineT, get_type())) {
597  if (graph_engine->get_type() == kPriorityType) {
598  posted = post_task_with_priority(std::move(task_func));
599  } else {
600  posted = post_task(std::move(task_func));
601  }
602  } else {
603  posted = post_task_with_priority(std::move(task_func));
604  }
605  } else {
606  posted = post_task(std::move(task_func));
607  }
608 
609  if VUNLIKELY (!posted) {
610  node->cancel();
611  }
612  });
613  }
614 
615  self->mark_ready(true);
616 }
617 
618 [[maybe_unused]] static inline GraphTaskPtr& operator--(GraphTaskPtr& task, int) { return task; }
619 
620 [[maybe_unused]] static inline GraphTaskPtr& operator>(GraphTaskPtr& task, GraphTaskPtr& target_task) {
621  task->precede(target_task);
622  return target_task;
623 }
624 
625 [[maybe_unused]] static inline GraphTaskPtr& operator<(GraphTaskPtr& task, GraphTaskPtr& target_task) {
626  task->succeed(target_task);
627  return target_task;
628 }
629 
630 [[maybe_unused]] static inline GraphTaskPtr& operator--(GraphTaskPtr& task) { return task; }
631 
632 } // namespace vlink
Pool-backed type-erased callables: copyable vlink::Function and move-only vlink::MoveFunction.
Cross-platform macros for visibility, branch hints, copy prevention, singletons and string helpers.
#define VUNLIKELY(...)
Short alias for VLINK_UNLIKELY.
Definition: macros.h:292
#define VLINK_EXPORT
Definition: macros.h:81
#define VLIKELY(...)
Short alias for VLINK_LIKELY.
Definition: macros.h:284
#define VLINK_DISALLOW_COPY_AND_ASSIGN(classname)
Deletes the copy constructor and copy-assignment operator of classname.
Definition: macros.h:174
Compile-time type-trait helpers used across the VLink codebase.
#define VLINK_HAS_MEMBER(T, member)
Macro Definitions.
Definition: traits.h:325