RPNX::QueryGraph
Typed, memoized, concurrent query evaluation for C++23
Loading...
Searching...
No Matches
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 owns a persistent worker pool that can execute multiple graphs concurrently. It balances local and global work queues. Each graph owns its handler registrations, memoized nodes, and diagnostics, and wakes 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 <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<>;
};
measure_text(std::string text)
{
co_return text.size();
}
int main()
{
rpnx::querygraph::graph graph(scheduler);
graph.register_handler_function< text_length_handler >(measure_text);
graph.bind_handlers();
std::cout << graph.make_request< text_length_query >("QueryGraph") << '\n';
}
Owns handler registrations, memoized nodes, and query execution.
Owns a persistent worker pool shared by independently cached graphs.
Primary QueryGraph API: specifications, handlers, execution, and errors.
Owning coroutine return object for a registered query handler.

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.

Sharing a scheduler

Pass the same scheduler to each graph that should share its worker pool:

rpnx::querygraph::scheduler scheduler({.thread_count = 4});
rpnx::querygraph::graph first(scheduler);
rpnx::querygraph::graph second(scheduler, {.enable_timing = false});

After registering and binding each graph's handlers, external threads can call make_request(), async_make_request(), make_subquery_request(), or dump_query_to_file() concurrently. The scheduler's thread count limits the combined worker pool across its graphs and requests. Workers remain available between requests and can be reused after a graph is destroyed. Each graph keeps its own cache, so identical query inputs in different graphs are evaluated independently.

scheduler::options contains thread_count and global_workitem_threshold. The default thread count is twice hardware concurrency, or two when hardware concurrency is unknown. The shared queue target defaults to the resolved thread count. Explicit zero values are rejected. Timing settings and the timing logger remain in graph::options.

The scheduler must outlive every graph that uses it. Finish all external calls before destroying a graph; its destructor waits for its scheduled resumptions and coroutine cleanup. Graph completion and dependency-cycle detection use that graph's outstanding work. Another graph's activity does not delay them, provided the pool has a worker available to execute the requested work. Handlers express dependencies with coroutine requests; synchronous external requests from scheduler workers are unsupported.

Submitting requests asynchronously

async_make_request<QuerySpec>(input) returns a std::future<QuerySpec::output_type>. A single calling thread can submit several queries before waiting for their results:

std::future<std::size_t> first = graph.async_make_request<text_length_query>("QueryGraph");
std::future<std::size_t> second = graph.async_make_request<text_length_query>("scheduler");
std::cout << first.get() << ' ' << second.get() << '\n';

Requests execute on the shared scheduler. Each future becomes ready when its node completes, independently of other running queries. Duplicate inputs reuse the same memoized evaluation and give each future its own output copy. Cached results produce ready futures. Handler errors, dependency cycles, and errors copying an output are delivered by get(); submission failures such as a missing handler are thrown by async_make_request().

Destroying a future leaves its query running and does not wait for completion. Graph destruction drains scheduled work and completes outstanding futures, which can then outlive the graph. Handler captures must remain valid until their work has finished. Handlers accepting an input by reference receive the cached key, whose lifetime is the lifetime of the 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 >;
};
double_length(std::string text)
{
std::size_t const length =
co_return length * 2;
}
Awaitable request for a memoized query value.

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);
A diagnostic emitted by a running query handler.

recursive_dependency_error indicates that the graph 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.