The runtime#

Executing a graph involves three pieces, all templates parameterized by the type of the data bank:

Piece	Header	Role
`ng::DataBank<Ts...>`	`data_bank.h`	Stores the values exchanged between operators, one pool per type.
`ng::Operator<DB>`	`operator.h`	Base class of the object doing the computation of a node type.
`ng::GraphRuntime<DB>`	`graph_runtime.h`	Turns a graph into a flat list of operators bound to a data bank, and runs it.

The library provides none of the concrete types: the data types, their parsers and the operators come from the program using it (tests/elements for the tests and examples).

using DataBank = ng::DataBank<Number, Boolean, Text>;

ng::GraphRuntime<DataBank> runtime(graph);   // build: may throw
if (runtime.run()) {                          // run: returns false on failure
    std::optional<Number> total = runtime.get_result<Number>("total");
}

The data bank#

DataBank<Ts...> holds one std::map<data_id_t, T> per type T of the list. All the pools share the same sequence of IDs, so a data_id_t designates a single item whatever its type. The ID 0 (ng::null_data) is never given: it means “no data”.

Method	Behavior
`add<T>(value)`	Stores a value in the pool of `T` under a new ID, returns the ID.
`reserve_id()`	Returns a new ID without storing anything: an empty slot, filled later by `store`.
`get<T>(id)`	`std::optional<T>`: empty if the pool of `T` has nothing under this ID.
`load(id, variant)`	Fills a `std::variant<Args...>` with the item `id`, trying the alternatives in order. Alternatives without a pool in the bank are skipped. Returns `false` if none has the item.
`store(id, variant)`	Erases `id` from all the pools, then stores the value held by the variant. Returns `false` if the bank has no pool for its type. Erasing first guarantees an ID never holds two values.
`add_from_string(str)`	Tries the `ng::Parser<T>` of each type, in the order of the template parameters, and adds the first successful result. Returns `null_data` if no parser accepts the string.
`contains(id)`, `erase(id)`, `get_pool<T>()`	Inspection and cleanup.

Because add_from_string stops at the first parser accepting the string, the order of the types matters. In the tests, DataBank<Number, Boolean, Text> puts Text last because its parser accepts anything: “3” becomes a Number, “true” a Boolean, “add” a Text, and "\"3\"" the Text “3”.

A parser is a specialization of ng::Parser<T>:

template <>
struct ng::Parser<double> {
    static std::optional<double> parse(const std::string& str);
};

Operators#

An operator is the runtime counterpart of a node. It doesn’t know the graph: it only knows a map socket_id_t -> data_id_t, its bindings, which tells where to read each input and where to write each output in the data bank.

template <typename DB>
class Operator {
protected:
    virtual bool launch_process() = 0;       // the computation itself
public:
    virtual bool pull(const DB& db) = 0;     // read the inputs from the data bank
    virtual bool poll() = 0;                 // ready to run?
    virtual bool push(DB& db) = 0;           // write the outputs to the data bank
    bool process();                          // calls launch_process()

    void bind(const socket_id_t&, data_id_t);
    data_id_t get_binding(const socket_id_t&) const;   // null_data if not bound
    data_id_t get_binding(const char*) const;
    const std::string& get_name() const;     // name of the node it comes from
};

launch_process is protected and called through the public process(), so the runtime controls when the computation happens. Every step returns bool: false stops the run.

The typical implementation keeps one std::variant per socket, listing the types it accepts:

class AddOperator : public ng::Operator<DataBank> {
    std::variant<Number> a_, b_, sum_;

    bool launch_process() override {
        sum_ = std::get<Number>(a_) + std::get<Number>(b_);
        return true;
    }

public:
    using ng::Operator<DataBank>::Operator;  // constructor taking the name

    bool pull(const DataBank& db) override { return db.load(get_binding("a"), a_) && db.load(get_binding("b"), b_); }
    bool poll() override { return true; }
    bool push(DataBank& db) override { return db.store(get_binding("sum"), sum_); }
};

For each node type, a function creating its operator is registered in ng::OperatorInstantiatorsRegistry<DB> under the node type’s qualifier. The runtime takes ownership of the returned pointer (std::unique_ptr):

bool registered = ng::OperatorInstantiatorsRegistry<DataBank>::instance().register_entry(
    ADD, [](const std::string& name) -> ng::Operator<DataBank>* { return new AddOperator(name); }
);

There is one registry per data bank type: operators written for DataBank<A, B> are not visible to a GraphRuntime<DataBank<A, B, C>>.

tests/elements/operators.h has a SimpleOperator<Ts...> base class implementing pull, poll and push from a list of socket IDs, so each operator only writes its computation.

Building: from a graph to operators#

The constructor GraphRuntime(const Graph&) does all the work of preparing the execution. It calls build_operators(graph, proxy_inputs = {}), which returns the data IDs of the results of the graph. GraphRuntime(graph_id_t) does the same with a graph of the GraphManager.

The runtime keeps no reference to the graph: once built, modifying the graph has no effect on it.

build_operators(graph, proxy_inputs)

proxy_inputs maps the alias of a parameter to a data ID. It is empty for the root graph, and filled when the graph is the inside of a proxy node. A local map outputs records, for each output socket of this graph, the data ID it writes to.

Sort. ng::sorted_by_depth(graph) returns the nodes by increasing depth (stable sort, so the nodes of a same depth are in the order of their IDs). It throws if the graph has a cycle. Since a node is always deeper than its predecessors, the source of every link has already been processed when its destination is reached.
For each node, in this order:
1. Resolve each input socket to a data ID (resolve_input), with this priority:
  1. the socket is linked: the data ID of the output socket at the other end of the link, taken from outputs;
  2. the socket is a parameter of the graph and proxy_inputs contains its alias: the data ID given by the outer graph;
  3. otherwise the socket is a constant: its string value is parsed with add_from_string, which stores it in the bank and returns its new ID. If no parser accepts it, the ID is null_data and the operator will fail to pull at run time.
2. If the node is a regular node: look its qualifier up in OperatorInstantiatorsRegistry<DB> (throws std::runtime_error if missing), create the operator with the node’s name, bind each input to its resolved ID, and for each output reserve a new ID (reserve_id), bind it and record it in outputs.
3. If the node is a proxy node: read the inner graph from the disk (raw_read), and call build_operators(inner, inputs) recursively, where inputs maps the proxy’s input socket IDs (which are the aliases of the inner parameters) to the IDs resolved at step a. The operators of the inner graph are appended to the list at this position. The recursive call returns the IDs of the inner results by alias, which are recorded in outputs as the outputs of the proxy node (null_data for an output the inner graph doesn’t expose anymore).
4. Results. For each output socket of the node exposed as a result of this graph, record alias -> outputs[socket] in the returned map.
Return the results map. For the root graph, it becomes get_results().

Proxy nodes don’t create operators: they disappear, replaced by the operators of their graph, and a proxy input and the inner socket it feeds share the same data ID. Nothing is copied between graphs at run time.

Recursion guard: before expanding a proxy, its qualifier is checked against the stack of proxies being expanded (building_) and the runtime throws std::runtime_error("Recursive proxy: ...") if it is already there. The root graph is not in the stack, so A → B → A is detected when B is reached the second time.

Example: a plain graph#

product = (x + y) * y with x = 4, y = 5 (example-05_runtime):

(x: Value) ──► (sum: Add).a
(y: Value) ──► (sum: Add).b
(y: Value) ──► (product: BinaryOp).b        product.operation = "mul"
(sum).sum  ──► (product).a

depth 0       y     value->1 (constant "5")      result->2 (reserved)
depth 0       x     value->3 (constant "4")      result->4 (reserved)
depth 1       sum   a->4  b->2                   sum->5    (reserved)
depth 2       product  a->5  b->2  operation->6 (constant "mul")   result->7 (reserved)

results: sum -> 5, product -> 7

After the build, IDs 1, 3 and 6 hold the parsed constants, and 2, 4, 5 and 7 are empty slots. Links show up as shared IDs: sum.a and x.result are both bound to 4, y.result, sum.b and product.b are all bound to 2.

Example: a proxy#

A Value node “x” (value “21”) linked to the x input of a DOUBLER proxy, whose inner graph is a single BinaryOp “times two” with a exposed as x, b = "2", operation = "mul" and result exposed as doubled:

root graph
  x (Value)        value->1 (constant "21")   result->2 (reserved)
  DOUBLER proxy    input x resolved to 2 (linked to x.result)
    └── build_operators(doubler, {x: 2})
          times two   a->2 (parameter x, given by the proxy)
                      b->3 (constant "2")  operation->4 (constant "mul")
                      result->5 (reserved)
          returns {doubled: 5}
  proxy output doubled = 5, exposed as the root result "out"

operators: [x, times two]        results: out -> 5        after run: out = 42

Running#

run() executes the operators sequentially, in the order of the list:

for each operator i:
    if !pull(bank) || !poll() || !process() || !push(bank):  return false
    executed[i] = true
return true

It stops at the first failure: the following operators are not executed. is_executed(i) tells which ones ran.
run() can be called again: all the operators run again, the outputs are overwritten (store erases first), the constants parsed at build time are reused.
get_result<T>(alias) reads a result of the root graph from the bank. It is empty if the alias doesn’t exist, if the run didn’t reach that operator, or if the value has another type than T.
get_data_bank() gives access to all the values, get_operators() to the operators and their bindings (useful to debug: see print_operators in examples/05_runtime.cc).

Errors#

Situation	Effect
The graph contains a cycle (only possible from a corrupted file)	Constructor throws `std::runtime_error`
No operator registered for a node type	Constructor throws `std::runtime_error("Operator not found: ...")`
The graph of a proxy can’t be read from the disk	Constructor throws `std::runtime_error`
Proxies including each other	Constructor throws `std::runtime_error("Recursive proxy: ...")`
A constant can’t be parsed	Bound to `null_data`: the operator’s `pull` fails, `run()` returns `false`
A value has a type the operator doesn’t accept	`pull` fails (`load` finds no matching alternative), `run()` returns `false`
The computation fails (division by zero, …)	`process` returns `false`, `run()` returns `false`

Checklist: adding a node type that can be executed#

Register its NodeDefinition in ng::NodesRegistry (sockets, types, default values).
Make sure the default values are accepted by the parsers of the data bank.
Write its operator: pull reads every input socket, push writes every output socket, using the same socket IDs as the definition.
Register the operator in ng::OperatorInstantiatorsRegistry<DataBank> under the same qualifier.
Add a test in tests/graph_runtime running a small graph containing it.

What the runtime doesn’t do (yet)#

No parallelism: the depth would allow running the operators of a same depth in parallel (the README mentions it), but run() is sequential. The depth is not kept after the sort.
poll() is called once: there is no waiting or retry for operators that are not ready.
The data bank only grows: values are never freed during the life of the runtime.
The graph is converted once: a modification of the graph requires building a new runtime.
See also Known limitations.