Skip to content

AGENTS.md

Latest commit

 

History

History
591 lines (454 loc) · 28.6 KB

AGENTS.md

File metadata and controls

591 lines (454 loc) · 28.6 KB

AGENTS.md — Pathrex

Project Overview

Pathrex is a Rust library and CLI tool for benchmarking queries on edge-labeled graphs constrained by regular languages and context-free languages. It uses SuiteSparse:GraphBLAS (via LAGraph) for sparse Boolean matrix operations and decomposes a graph by edge label into one Boolean adjacency matrix per label.

Repository Layout

pathrex/
├── Cargo.toml                  # Crate manifest (edition 2024)
├── build.rs                    # Links LAGraph + LAGraphX; optionally regenerates FFI bindings
├── src/
│   ├── lib.rs                  # Modules: eval, formats, graph, rpq, sparql, utils, lagraph_sys
│   ├── main.rs                 # Binary entry point (placeholder)
│   ├── lagraph_sys.rs          # FFI module — includes generated bindings
│   ├── lagraph_sys_generated.rs# Bindgen output (checked in, regenerated in CI)
│   ├── utils.rs                # Public helpers: CountingBuilder, CountOutput, VecSource,
│   │                           #   grb_ok! and la_ok! macros, build_graph
│   ├── graph/
│   │   ├── mod.rs              # Core traits (GraphBuilder, GraphDecomposition, GraphSource,
│   │   │                       #   Backend, Graph<B>), error types, RAII wrappers, GrB init
│   │   └── inmemory.rs         # InMemory marker, InMemoryBuilder, InMemoryGraph
│   ├── eval/
│   │   └── mod.rs              # Evaluator, PreparedEvaluator, ResultCount traits
│   ├── rpq/
│   │   ├── mod.rs              # RPQ query types, RpqError, RPQ marker subtraits
│   │   ├── nfarpq.rs           # NfaRpqEvaluator (LAGraph_RegularPathQuery)
│   │   └── rpqmatrix.rs        # Matrix-plan RPQ evaluator
│   ├── sparql/
│   │   └── mod.rs              # parse_rpq / extract_rpq → RpqQuery (spargebra)
│   └── formats/
│       ├── mod.rs              # FormatError enum, re-exports
│       ├── csv.rs              # Csv<R> — CSV → Edge iterator (CsvConfig, ColumnSpec)
│       ├── mm.rs               # MatrixMarket directory loader (vertices.txt, edges.txt, *.txt)
│       └── rdf.rs              # Rdf — unified RDF parser (N-Triples, Turtle) → Edge iterator
├── tests/
│   ├── inmemory_tests.rs       # Integration tests for InMemoryBuilder / InMemoryGraph
│   ├── mm_tests.rs             # Integration tests for MatrixMarket format
│   ├── nfarpq_tests.rs         # Integration tests for NfaRpqEvaluator
│   └── rpqmatrix_tests.rs      # Integration tests for matrix-plan RPQ evaluator
├── pathrex-sys/deps/
│   └── LAGraph/                # Git submodule (SparseLinearAlgebra/LAGraph)
└── .github/workflows/ci.yml   # CI: build GraphBLAS + LAGraph, cargo build & test

Build & Dependencies

System prerequisites

Dependency Purpose
cmake Building GraphBLAS and LAGraph from source
git Fetching pinned GraphBLAS source at build time
C/C++ toolchain Compiling GraphBLAS and LAGraph (gcc or clang)
OpenMP runtime Linked dynamically: libgomp on Linux, libomp on macOS, /openmp on MSVC
libclang-dev / clang Required by bindgen when regenerate-bindings feature is active

SuiteSparse:GraphBLAS no longer needs to be installed system-wide. It is fetched, built statically, and linked into the binary by pathrex-sys/build.rs.

Building

# Ensure the LAGraph submodule is present
git submodule update --init --recursive

# Build pathrex. First cold build clones GraphBLAS and runs cmake; takes
# ~2-10 minutes depending on core count. Subsequent builds reuse the
# GraphBLAS source tree under target/.../graphblas-src/ and the cmake
# build dir, so they are incremental.
cargo build

# Run tests (no LD_LIBRARY_PATH needed — everything but the OpenMP
# runtime is statically linked)
cargo test --workspace

How pathrex-sys/build.rs handles linking

pathrex-sys/build.rs performs three jobs:

  1. GraphBLAS fetch. Clones SuiteSparse:GraphBLAS at the pin defined by the GRAPHBLAS_TAG constant (currently v10.3.1) into $OUT_DIR/graphblas-src/ via git clone --depth=1 --branch <tag>. A sentinel file <dir>/.pathrex-fetched containing the tag string marks a completed clone; if the pin is bumped, the sentinel mismatches and the clone is wiped and retried. If the directory exists without a sentinel (interrupted earlier clone), it is also wiped before retrying.

  2. Native build + linking. Drives cmake twice — once for GraphBLAS, once for the pathrex-sys/deps/LAGraph submodule:

    • GraphBLAS flags: BUILD_SHARED_LIBS=OFF, BUILD_STATIC_LIBS=ON, GRAPHBLAS_BUILD_STATIC_LIBS=ON (belt-and-braces), GRAPHBLAS_USE_JIT=OFF (no runtime C compiler required), GRAPHBLAS_COMPACT=OFF (full FactoryKernels for performance), GRAPHBLAS_USE_OPENMP=ON, GRAPHBLAS_USE_CUDA=OFF, SUITESPARSE_DEMOS=OFF, BUILD_TESTING=OFF, Release profile.
    • LAGraph flags: BUILD_SHARED_LIBS=OFF, BUILD_STATIC_LIBS=ON, BUILD_TESTING=OFF, plus CMAKE_PREFIX_PATH=<graphblas_install> and GRAPHBLAS_ROOT=<graphblas_install> so LAGraph's find_package(GraphBLAS) picks up our static build instead of any system one.
    • Static archives land in $OUT_DIR/.../out/lib/ (or lib64/ on Fedora-family distros — both candidates are probed by pick_libdir).
    • Emits cargo:rustc-link-lib=static=lagraphx, cargo:rustc-link-lib=static=lagraph, cargo:rustc-link-lib=static=graphblas. Order matters: lagraphx references symbols from lagraph's utility module; both reference graphblas.
    • Emits OS-specific runtime libraries: gomp+pthread+dl+m on Linux, omp+pthread on macOS, nothing explicit on MSVC. Override via RUSTFLAGS if your toolchain ships a different OpenMP runtime (e.g. libomp on Linux + clang).

  3. docs.rs guard. If the DOCS_RS environment variable is set, the entire native build is skipped. docs.rs sandboxes block all network access (so the git clone would fail) and have strict time/memory limits; rustdoc only needs to compile Rust code, not link or execute it.

  4. Optional FFI binding regeneration (feature regenerate-bindings). When the feature is active, regenerate_bindings() runs bindgen against deps/LAGraph/include/LAGraph.h, deps/LAGraph/include/LAGraphX.h, and the GraphBLAS install tree's include/suitesparse/GraphBLAS.h. The generated Rust file is written to pathrex-sys/src/lagraph_sys_generated.rs. Only a curated allowlist of GraphBLAS/LAGraph types and functions is exposed (see the allowlist_* calls in pathrex-sys/build.rs).

Feature flags

Feature Effect
regenerate-bindings Runs bindgen at build time to regenerate src/lagraph_sys_generated.rs from LAGraph.h, LAGraphX.h (both from deps/LAGraph/include) and GraphBLAS.h. Without this feature the checked-in bindings are used as-is.

Pre-generated FFI bindings

The file src/lagraph_sys_generated.rs is checked into version control. CI regenerates it with --features regenerate-bindings. Do not hand-edit this file.

Architecture & Key Abstractions

Edge

Edge is the universal currency between format parsers and graph builders: { source: String, target: String, label: String }.

GraphSource trait

GraphSource<B> is implemented by any data source that knows how to feed itself into a specific [GraphBuilder]:

Csv<R>, MatrixMarket, and Rdf implement GraphSource<InMemoryBuilder> (see src/graph/inmemory.rs), so they can be passed to [GraphBuilder::load] and [Graph::try_from].

GraphBuilder trait

GraphBuilder accumulates edges and produces a GraphDecomposition:

InMemoryBuilder also exposes lower-level helpers outside the trait:

Backend trait & Graph<B> handle

Backend associates a marker type with a concrete builder/graph pair:

pub trait Backend {
    type Graph: GraphDecomposition;
    type Builder: GraphBuilder<Graph = Self::Graph>;
}

Graph<B> is a zero-sized handle parameterised by a Backend:

InMemory is the concrete backend marker type.

GraphDecomposition trait

GraphDecomposition is the read-only query interface:

Generic evaluator abstraction (src/eval/)

src/eval/mod.rs defines query-language-agnostic evaluator traits:

  • Evaluator uses associated types for Query, Result, Error, and Prepared. The graph backend stays a method-level generic (G: GraphDecomposition) so one evaluator type can run against any graph backend selected at the call site.
  • PreparedEvaluator represents prepared (query, graph) state that can be executed repeatedly, which is used by benchmark timing loops.
  • ResultCount is separate from Evaluator::Result; only CLI runners that need counts require this bound, leaving room for future evaluators with richer result types.

InMemoryBuilder / InMemoryGraph

InMemoryBuilder is the primary GraphBuilder implementation. It collects edges in RAM, then build() calls GraphBLAS to create one GrB_Matrix per label via COO format, wraps each in an LAGraph_Graph, and returns an InMemoryGraph.

Multiple CSV sources can be chained with repeated .load() calls; all edges are merged into a single graph.

Node ID representation: Internally, InMemoryBuilder uses HashMap<usize, String> for id_to_node (changed from Vec<String> to support sparse/pre-assigned IDs from MatrixMarket). The set_node_map() method allows bulk-installing a node mapping, which is used by the MatrixMarket loader.

Format parsers

Three built-in parsers are available, each yielding Iterator<Item = Result<Edge, FormatError>> and pluggable into GraphBuilder::load() via GraphSource<InMemoryBuilder> (see src/graph/inmemory.rs).

Csv<R>

Csv<R> parses delimiter-separated edge files.

Configuration is via CsvConfig:

Field Default Description
source_column Index(0) Column for the source node (by index or name)
target_column Index(1) Column for the target node
label_column Index(2) Column for the edge label
has_header true Whether the first row is a header
delimiter b',' Field delimiter byte

ColumnSpec is either Index(usize) or Name(String). Name-based lookup requires has_header: true.

MatrixMarket directory format

MatrixMarket loads an edge-labeled graph from a directory with:

  • vertices.txt — one line per node: <node_name> <1-based-index> on disk; get_node_id returns the matching 0-based matrix index
  • edges.txt — one line per label: <label_name> <1-based-index> (selects n.txt)
  • <n>.txt — MatrixMarket adjacency matrix for label with index n

Names in mapping files may be written with SPARQL-style angle brackets (e.g. <Article1>). parse_index_map strips a single pair of surrounding </> so dictionary keys match short labels (Article1), aligning with IRIs after RpqQuery::strip_base on SPARQL-derived queries.

The loader uses LAGraph_MMRead to parse each .txt file into a GrB_Matrix, then wraps it in an LAGraph_Graph. Vertex indices from vertices.txt are converted to 0-based and installed via InMemoryBuilder::set_node_map().

Helper functions:

MatrixMarket implements GraphSource<InMemoryBuilder> in src/graph/inmemory.rs (see the impl at line 215): vertices.txt maps are converted from 1-based file indices to 0-based matrix ids before set_node_map; edges.txt indices are unchanged for n.txt lookup.

Rdf — Unified RDF Parser

Rdf is a unified parser for RDF formats using oxttl and oxrdf. It supports both N-Triples (.nt) and Turtle (.ttl) formats via the RdfFormat enum.

Each triple (subject, predicate, object) becomes an Edge where:

  • source — subject IRI or blank-node ID (_:label).
  • target — object IRI or blank-node ID; triples whose object is an RDF literal yield Err(FormatError::LiteralAsNode) (callers may filter these out).
  • label — full predicate IRI string (including fragment #… when present).

Constructor:

  • Rdf::from_path(path) — auto-detects format from file extension (.nt → N-Triples, .ttl → Turtle). Parses in parallel using memory-mapping and rayon.

Format detection via RdfFormat::from_path(path):

Extension Format
.nt, .ntriples RdfFormat::NTriples
.ttl, .turtle RdfFormat::Turtle

Example usage:

use pathrex::formats::Rdf;
use pathrex::graph::{Graph, InMemory};

// Auto-detect from extension
let graph = Graph::<InMemory>::try_from(
    Rdf::from_path("data.ttl")?
)?;

SPARQL parsing (src/sparql/mod.rs)

The sparql module uses the spargebra crate to parse SPARQL 1.1 query strings and build a pathrex-native RpqQuery for RPQ evaluators.

Supported query form: SELECT queries with exactly one triple or property path pattern in the WHERE clause. Relative IRIs such as <knows> require a BASE declaration (or PREFIX / full IRIs). Example:

BASE <http://example.org/>
SELECT ?x ?y WHERE { ?x <knows>/<likes>* ?y . }

Key public items:

  • parse_rpq(sparql) — parses a SPARQL string with SparqlParser and returns an RpqQuery.
  • extract_rpq(query) — validates a parsed [spargebra::Query] is a SELECT with a single path pattern and returns an RpqQuery. Use this when you construct a custom SparqlParser (e.g. with prefix declarations) and call parse_query yourself.
  • ExtractError — error enum for extraction failures (NotSelect, NotSinglePath, UnsupportedSubject, UnsupportedObject, VariablePredicate). Converts to RpqError::Extract via #[from].

Call RpqQuery::strip_base when graph edge labels are short names and the parsed query contains full IRIs sharing a common prefix.

The module handles spargebra's desugaring of sequence paths (?x <a>/<b>/<c> ?y) from a chain of BGP triples back into a single path expression.

RPQ evaluation (src/rpq/)

The rpq module provides an abstraction for evaluating Regular Path Queries (RPQs) over edge-labeled graphs using GraphBLAS/LAGraph.

Key public items:

NfaRpqResult wraps a [GraphblasVector] of reachable target vertices. When the subject is a variable, every vertex is used as a source and LAGraph_RegularPathQuery returns the union of targets — individual (source, target) pairs are not preserved.

RpqMatrixEvaluator (src/rpq/rpqmatrix.rs)

RpqMatrixEvaluator compiles [PathExpr] into a Boolean matrix plan over label adjacency matrices and runs [LAGraph_RPQMatrix]. It returns RpqMatrixResult: the path-relation nnz plus a [GraphblasMatrix] duplicate of the result matrix (full reachability relation for the path). Subject/object do not filter the matrix; a named subject is only validated to exist. Bound objects are not supported yet ([RpqError::UnsupportedPath]). NTriples<R> parses W3C N-Triples RDF files using oxttl and oxrdf. Each triple (subject, predicate, object) becomes an Edge where:

  • source — subject IRI or blank-node ID (_:label).
  • target — object IRI or blank-node ID; triples whose object is an RDF literal yield Err(FormatError::LiteralAsNode) (callers may filter these out).
  • label — full predicate IRI string (including fragment #… when present).

Constructor:

SPARQL parsing (src/sparql/mod.rs)

The rpq module provides an abstraction for evaluating Regular Path Queries (RPQs) over edge-labeled graphs using GraphBLAS/LAGraph.

Key public items:

NfaRpqEvaluator (src/rpq/nfarpq.rs)

NfaRpqEvaluator implements [RpqEvaluator] by:

  1. Converting a [PathExpr] into an Nfa via Thompson's construction (Nfa::from_path_expr()).
  2. Eliminating ε-transitions via epsilon closure (NfaBuilder::epsilon_closure()).
  3. Building one LAGraph_Graph per NFA label transition (Nfa::build_lagraph_matrices()).
  4. Calling [LAGraph_RegularPathQuery] with the NFA matrices, data-graph matrices, start/final states, and source vertices.

type Result = NfaRpqResult ([GraphblasVector] of reachable targets).

Supported path operators match [PathExpr] variants above. Reverse and NegatedPropertySet from SPARQL map to [RpqError::UnsupportedPath] when they appear in extracted paths.

Subject/object resolution: [Endpoint::Variable] means "all vertices"; [Endpoint::Named] resolves to a single vertex via GraphDecomposition::get_node_id().

NfaRpqResult wraps a [GraphblasVector] of reachable target vertices. When the subject is a variable, every vertex is used as a source and LAGraph_RegularPathQuery returns the union of targets — individual (source, target) pairs are not preserved.

RpqMatrixEvaluator (src/rpq/rpqmatrix.rs)

RpqMatrixEvaluator compiles [PathExpr] into a Boolean matrix plan over label adjacency matrices and runs [LAGraph_RPQMatrix]. It returns RpqMatrixResult: the path-relation nnz plus a [GraphblasMatrix] duplicate of the result matrix (full reachability relation for the path). Subject/object do not filter the matrix; a named subject is only validated to exist. Bound objects are not supported yet ([RpqError::UnsupportedPath]).

CLI dispatch (src/cli/dispatch.rs)

With the bench feature enabled, src/cli/dispatch.rs is the single mapping from Algo variants to concrete evaluator types. dispatch_query and dispatch_bench each perform one exhaustive match per requested algorithm, then call generic runners (run_query_for_evaluator<E> and run_bench_for_evaluator<E>) that are monomorphized for the selected evaluator.

Adding a new algorithm requires a new Algo variant, its Display arm, one dispatch_query arm, one dispatch_bench arm, an impl Evaluator for the evaluator type, and an impl ResultCount for any result type used by CLI count reporting.

FFI layer

lagraph_sys exposes raw C bindings for GraphBLAS and LAGraph. Safe Rust wrappers live in graph::mod:

  • LagraphGraph — RAII wrapper around LAGraph_Graph (calls LAGraph_Delete on drop). Also provides LagraphGraph::from_coo() to build directly from COO arrays.
  • GraphblasVector — RAII wrapper around GrB_Vector (derives Debug).
  • GraphblasMatrix — RAII wrapper around GrB_Matrix (dup + free on drop).
  • ensure_grb_init() — internal one-time LAGraph_Init via std::sync::Once. Called automatically by RAII-wrapped constructors (LagraphGraph::from_coo, LagraphGraph::from_matrix, ThreadScope::enter) and by load_mm_file. Crate-private; no other code should call it.

Macros & helpers (src/utils.rs)

Two #[macro_export] macros handle FFI error mapping:

  • grb_ok!(expr) — evaluates a GraphBLAS call inside unsafe, maps the i32 return to Result<(), GraphError::GraphBlas(info)>.
  • la_ok!(fn::path(args…)) — evaluates a LAGraph call, automatically appending the required *mut i8 message buffer, and maps failure to GraphError::LAGraph(info, msg).

A convenience function is also provided:

  • build_graph(edges) — builds an InMemoryGraph from a slice of (&str, &str, &str) triples (source, target, label). Used by integration tests.

Coding Conventions

  • Rust edition 2024.
  • Error handling via thiserror derive macros; three main error enums: GraphError, FormatError, and RpqError.
  • FormatError converts into GraphError via #[from] FormatError on the GraphError::Format variant.
  • GraphError converts into RpqError via #[from] GraphError on the RpqError::Graph variant, enabling ? propagation in evaluators.
  • Unsafe FFI calls are confined to lagraph_sys, graph/mod.rs, graph/inmemory.rs, rpq/nfarpq.rs. All raw pointers are wrapped in RAII types that free resources on drop.
  • unsafe impl Send + Sync is provided for LagraphGraph, GraphblasVector, and GraphblasMatrix because GraphBLAS handles are thread-safe after init.
  • Unit tests live in #[cfg(test)] mod tests blocks inside each module. Integration tests that need GraphBLAS live in tests/inmemory_tests.rs, tests/mm_tests.rs, tests/nfarpq_tests.rs.

Testing

# Run all tests (LAGraph installed system-wide)
LD_LIBRARY_PATH=/usr/local/lib cargo test --verbose

# If LAGraph is NOT installed system-wide (only built in the submodule):
LD_LIBRARY_PATH=deps/LAGraph/build/src:deps/LAGraph/build/experimental:/usr/local/lib cargo test --verbose

Tests in src/graph/mod.rs use CountingBuilder / CountOutput / VecSource from src/utils.rs — these do not call into GraphBLAS and run without native libraries.

Tests in src/formats/csv.rs and src/formats/rdf.rs are pure Rust and need no native dependencies.

Tests in src/sparql/mod.rs are pure Rust and need no native dependencies.

Tests in src/rpq/nfarpq.rs (NFA construction unit tests) are pure Rust and need no native dependencies.

Tests in src/graph/inmemory.rs, tests/inmemory_tests.rs, tests/mm_tests.rs, tests/nfarpq_tests.rs, and tests/rpqmatrix_tests.rs call real GraphBLAS/LAGraph and require the native libraries to be present.

CI

The GitHub Actions workflow (.github/workflows/ci.yml) runs on every push and PR across stable, beta, and nightly toolchains:

  1. Checks out with submodules: recursive and lfs: true.
  2. Installs cmake, libclang-dev, clang via apt.
  3. cargo build --workspace --features pathrex-sys/regenerate-bindings — pathrex-sys/build.rs clones GraphBLAS at the pinned tag, builds it statically, builds LAGraph statically against it, and regenerates FFI bindings.
  4. cargo test --workspace --verbose — runs the full test suite. No LD_LIBRARY_PATH is needed because GraphBLAS and LAGraph are linked statically; only the OpenMP runtime (libgomp) is dynamic and is already on the default loader path.

Releasing

Pushing a v*.*.* tag triggers .github/workflows/release.yml:

  1. docker job — builds the image once and pushes the same tags ({version}, {major}.{minor}, {major}, latest) to two registries:
    • ghcr.io/sparselinearalgebra/pathrex (authenticated via GITHUB_TOKEN, no extra setup needed).
    • docker.io/vanyaglazunov/pathrex (authenticated via DOCKERHUB_USERNAME + DOCKERHUB_TOKEN repository secrets).
  2. publish-crates job — publishes both crates to crates.io in the correct order:
    • Reads pathrex-sys version via cargo metadata.
    • Skips publishing pathrex-sys if that version is already on the registry (allows re-tagging when only pathrex changed).
    • Polls cargo search until the new pathrex-sys is indexed (up to 5 minutes), then publishes pathrex against it.
    • Requires the CARGO_REGISTRY_TOKEN repository secret.

Manual dry-run

To verify the publish path without uploading:

cargo publish --dry-run -p pathrex-sys
# (pathrex dry-run requires pathrex-sys to be on crates.io first)