RPNX::QueryGraph

RPNX::QueryGraph is a C++ library for memoized, concurrent evaluation of typed queries. A query handler is a coroutine: it can request other queries, publish subquery results, emit diagnostic messages, and suspend without growing the native call stack. The graph caches each query by its typed input so overlapping requests share one calculation.

The library is intended for compiler frontends, build systems, analysis tools, and other workloads that can be expressed as a dynamic dependency graph.

QueryGraph was mainly created for Quxlang but is generic and may be useful for other projects.

Why QueryGraph?

Ordinary recursive code is easy to express but can repeat overlapping work, overflow the call stack, and make cross-thread coordination difficult. Memoization removes repeated work, but a conventional memoized function still blocks its caller and usually requires application-specific synchronization.

QueryGraph combines four ideas:

• Typed queries. Each query declares its input and output types and a stable textual identifier.
• Memoized nodes. A (query type, input) pair identifies one cached node. Concurrent callers observe the same calculation instead of starting duplicate work.
• Stackless dependencies. Handlers use co_await to request dependencies, allowing deeply nested graphs without consuming the native call stack.
• Declared edges. A handler lists every query and subquery it may request. Invalid dependency requests are rejected at compile time, and bind_handlers() resolves declared dependencies to direct runtime descriptors before execution.

The scheduler runs ready coroutine resumptions across a worker group, balances local and global work queues, and wakes both coroutine and external-thread waiters when a node reaches a terminal state.

Requirements

• A C++23 compiler and standard library with coroutine, std::format, and std::print support
• CMake 3.21 or newer
• RPNXMetalib
• RPNXSerialization
• RPNXDataStructures when QUERYGRAPH_USE_CONC_UNORDERED_MAP is enabled (the default)
• GoogleTest only when BUILD_TESTING is enabled
• Doxygen to generate the API documentation

Minimal example

#include <rpnx/querygraph/querygraph.hpp>
 
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
 
struct text_length_query
{
    static constexpr char const* query_id = "text_length";
    using input_type = std::string;
    using output_type = std::size_t;
};
 
struct text_length_handler
{
    using query = text_length_query;
    using dependencies = rpnx::typelist<>;
};
 
rpnx::querygraph::coroutine< text_length_handler >
measure_text(std::string text)
{
    co_return text.size();
}
 
int main()
{
    rpnx::querygraph::graph graph;
    graph.register_handler_function< text_length_handler >(measure_text);
    graph.bind_handlers();
 
    std::cout << graph.make_request< text_length_query >("QueryGraph") << '\n';
}

Every handler must be registered exactly once and bind_handlers() must be called after registration and before the first request. Registration, canonical error registration, and binding are configuration operations; complete them before making concurrent requests on the same graph.

Query and handler specifications

A query specification satisfies query_spec_c by exposing:

• input_type: the value used as the memoization key;
• output_type: the value returned by the handler; and
• query_id: a stable, string-convertible identifier used in graph dumps.

A handler specification satisfies query_handler_spec_c by exposing:

• query: the query specification it implements;
• dependencies: an rpnx::typelist containing every query or subquery the handler may request; and
• optionally, produced_subqueries: an rpnx::typelist of subqueries the handler may publish with co_yield.

Inputs must support the selected cache backend. With the default concurrent map they must be hashable through rpnx::querygraph::hasher; with the fallback map they must be ordered. Inputs, outputs, and registered canonical errors must also be supported by RPNX::Serialization if graph dumps are used. Specialize binary_traits<T> to customize binary serialization and debug_traits<T> to customize diagnostic text.

Requesting dependencies

Within a handler, construct a request<QuerySpec> and await it:

struct doubled_length_handler
{
    using query = doubled_length_query;
    using dependencies = rpnx::typelist< text_length_query >;
};
 
rpnx::querygraph::coroutine< doubled_length_handler >
double_length(std::string text)
{
    std::size_t const length =
        co_await rpnx::querygraph::request< text_length_query >(std::move(text));
    co_return length * 2;
}

co_yield dependency(request) declares and schedules an edge without waiting for its value immediately. The original request can be awaited later. A dependency omitted from the handler specification causes a compile-time error.

Handlers may also co_await handler-specific cosubroutines. Cosubroutines share the parent query node and scheduler context, so they are useful for splitting a handler into coroutine-aware operations without creating separately memoized query nodes.

Subqueries

A subquery is a result produced in the context of one parent query node. Its specification exposes parent_query, input_type, output_type, and a stable subquery_id.

A parent handler lists the subquery in produced_subqueries and publishes values with co_yield subquery_result<SubquerySpec>(input, output). A consumer lists both the subquery and its parent query in dependencies, then awaits subquery_request<SubquerySpec>(parent_input, input). External callers can use make_subquery_request<SubquerySpec>().

If the parent finishes without publishing a requested value, subquery_does_not_exist is reported. If the parent fails first, subquery_parent_failed preserves the parent error as a nested exception.

Errors and diagnostics

Unhandled exceptions terminate the affected query node and are rethrown to requesters. Errors registered with register_canonical_error<Error>() are copied into stable, serializable error storage so dumps can retain the error type, payload, and message. Canonical error types must derive from std::exception and be copy constructible.

Handlers can attach source-located messages to their node:

co_yield rpnx::querygraph::debug_message("Resolving input {:?}", input);

recursive_dependency_error indicates that the executor became quiescent while the requested node was still unresolved, usually because of a dependency cycle. bad_continuation indicates that a handler coroutine completed without returning a value, throwing, or leaving a dependency that could continue it.

Graph dumps

graph::dump() returns the structured graph_data representation. graph::marshall() serializes it with RPNXSerialization, and dump_query_to_file<QuerySpec>() evaluates one root query and writes the reachable graph to a binary file. The on-disk schema is documented in doc/dump-file-format.md.

Graph instances retain memoized nodes for their lifetime. Repeating the same query input returns the cached terminal result, including a cached error.

Building and testing

This repository's cbuild workspace is under build/. On a new checkout, detect the local toolchain and download the pinned Git dependencies before building:

cd build
csetup detect-toolchains
csetup download
cbuild build -c Debug -t querygraph
cbuild test -c Debug -t querygraph

For a conventional dependency-provided CMake build:

cmake -S . -B build -DBUILD_TESTING=ON
cmake --build build
ctest --test-dir build --output-on-failure

Consumers link the exported target:

find_package(RPNXQueryGraph REQUIRED)
target_link_libraries(your_target PRIVATE RPNX::querygraph)

Relevant CMake options are:

• QUERYGRAPH_USE_CONC_UNORDERED_MAP: use the sharded concurrent cache backend (default ON);
• RPNX_QUERYGRAPH_BUILD_EXAMPLES: build querygraph-demo (default ON for a top-level build and OFF as a subproject).

Building the API documentation

Run Doxygen from the repository root:

doxygen Doxyfile

The generated HTML entry point is doc-out/html/index.html. The documentation includes this README, the public headers, the graph-dump schema, concepts, customization points, error contracts, and coroutine-facing API types.

Repository layout

• include/rpnx/querygraph/: installed public headers
• sources/querygraph.cpp: library implementation
• sources/: demo graph and example handlers
• tests/: GoogleTest test suite
• Doxyfile: standalone Doxygen configuration
• doc/: graph-dump format documentation

Current limitations and roadmap

The current roadmap is tracked in TODO.md. Major planned work includes scheduler tuning for high-core-count systems and memory-aware scheduling based on estimated node requirements. Persistence and reconstruction of live memoized graphs are not currently provided; graph serialization is intended for debugging and analysis.

License

RPNX::QueryGraph is licensed under the Apache License 2.0. See the LICENSE file.