Skip to main content

oxilite_datalog/
lib.rs

1//! Datalog over oxilite: recursive rules with stratified negation, constraints and
2//! aggregation, compiled to SQL.
3//!
4//! SPARQL and openCypher both stop at the same wall — recursion beyond a property path — and
5//! the only rules oxilite has are the fixed RDFS/OWL-RL set hard-coded in the core. This crate
6//! makes a rule a first-class thing: named, composable, and evaluated where the data is, which
7//! on Cloudflare D1 means inside the database rather than over the network.
8//!
9//! ```text
10//! @prefix ex: <http://example.org/> .
11//!
12//! ancestor(?x, ?y) :- ex:parent(?x, ?y).
13//! ancestor(?x, ?z) :- ex:parent(?x, ?y), ancestor(?y, ?z).
14//!
15//! adult(?x, ?y) :- ancestor(?x, ?y), ex:age(?y, ?a), ?a >= 18.
16//! orphan(?x)     :- ex:Person(?x), not ancestor(?x, _).
17//!
18//! ?- adult(?x, ?y).
19//! ```
20//!
21//! A program is parsed, checked (safety and stratification), and compiled to one SQL
22//! statement whenever its recursion is linear — the same one-round-trip invariant SPARQL and
23//! Cypher hold.
24//!
25// @lat: [[architecture#Datalog frontend]]
26#![forbid(unsafe_code)]
27
28pub mod ast;
29pub mod error;
30pub mod exec;
31pub mod host;
32#[cfg(feature = "json")]
33pub mod json;
34pub mod lexer;
35pub mod materialize;
36pub mod parser;
37pub mod program;
38pub mod sql;
39
40pub use ast::{Program, Rule};
41pub use error::{DatalogError, Result};
42pub use exec::{DatalogJob, DatalogResult};
43pub use materialize::{plan as materialize_plan, MaterializeJob, MaterializeStats};
44pub use parser::parse;
45pub use program::{Analysis, Shape, Stratum};
46pub use sql::{Compiled, Fixpoint, FixpointPhase, Options};
47
48use ast::{At, Atom, BodyItem};
49use oxilite_core::sql::Capabilities;
50
51/// Parses, checks and compiles a program.
52pub fn compile(src: &str, caps: &Capabilities, options: &Options) -> Result<Compiled> {
53    let program = parse(src)?;
54    let analysis = program::analyse(&program)?;
55    sql::compile(&program, &analysis, caps, options)
56}
57
58/// The version a program reads: the `as_of` option, else its `@version` directive.
59pub fn version_of(src: &str, options: &Options) -> Result<Option<String>> {
60    if options.as_of.is_some() {
61        return Ok(options.as_of.clone());
62    }
63    Ok(parse(src)?.version)
64}
65
66/// Every version a program names: its `as_of` / `@version` first (if any), then the `at "REF"`
67/// of its atoms, deduplicated.
68pub fn version_refs(src: &str, options: &Options) -> Result<(Option<String>, Vec<String>)> {
69    let program = parse(src)?;
70    let whole = options.as_of.clone().or(program.version.clone());
71    let mut refs: Vec<String> = Vec::new();
72    let mut push = |a: &Atom| {
73        if let Some(At::Version(r)) = &a.at {
74            if !refs.contains(r) {
75                refs.push(r.clone());
76            }
77        }
78    };
79    for rule in &program.rules {
80        for item in &rule.body {
81            if let BodyItem::Atom(a) | BodyItem::Negated(a) = item {
82                push(a);
83            }
84        }
85    }
86    if let Some(g) = &program.goal {
87        push(&g.atom);
88    }
89    Ok((whole, refs))
90}
91
92/// Prepares a program for execution.
93pub fn prepare(src: &str, caps: &Capabilities, options: &Options) -> Result<DatalogJob> {
94    let compiled = compile(src, caps, options)?;
95    Ok(DatalogJob::new(compiled, caps.clone()))
96}
97
98/// A program ready to run: plain, or with rules that call host functions (see [`host`]).
99pub enum ProgramJob {
100    Plain(Box<DatalogJob>),
101    Host(Box<host::HostJob>),
102}
103
104impl oxilite_core::job::Job for ProgramJob {
105    type Output = DatalogResult;
106
107    fn step(
108        &mut self,
109        response: Option<oxilite_core::sql::Response>,
110    ) -> oxilite_core::Result<oxilite_core::job::Step<DatalogResult>> {
111        match self {
112            Self::Plain(j) => j.step(response),
113            Self::Host(j) => j.step(response),
114        }
115    }
116}
117
118/// Prepares a program, with the host functions of `options` callable from it.
119pub fn prepare_program(src: &str, caps: &Capabilities, options: &Options) -> Result<ProgramJob> {
120    let program = parse(src)?;
121    if host::uses_host_functions(&program, &options.functions)? {
122        return Ok(ProgramJob::Host(Box::new(host::HostJob::new(
123            program, caps, options,
124        )?)));
125    }
126    let analysis = program::analyse(&program)?;
127    let compiled = sql::compile(&program, &analysis, caps, options)?;
128    Ok(ProgramJob::Plain(Box::new(DatalogJob::new(
129        compiled,
130        caps.clone(),
131    ))))
132}
133
134/// Describes how a program runs: its strata, the strategy chosen for each recursive
135/// component, and the SQL it compiles to.
136pub fn explain(src: &str, caps: &Capabilities, options: &Options) -> Result<String> {
137    let program = parse(src)?;
138    let analysis = program::analyse(&program)?;
139    let mut out = String::from("-- oxilite datalog\n");
140    for (i, stratum) in analysis.strata.iter().enumerate() {
141        out.push_str(&format!(
142            "-- stratum {i}: {} [{}]\n",
143            stratum
144                .preds
145                .iter()
146                .map(ast::Pred::to_string)
147                .collect::<Vec<_>>()
148                .join(", "),
149            match stratum.shape {
150                Shape::NonRecursive => "not recursive",
151                Shape::Linear => "linear recursion, one WITH RECURSIVE member",
152                Shape::LinearMutual => "mutual recursion, one tagged WITH RECURSIVE member",
153                Shape::NonLinear => "non-linear recursion",
154            }
155        ));
156    }
157    match sql::compile(&program, &analysis, caps, options) {
158        Ok(compiled) => {
159            for note in &compiled.notes {
160                out.push_str(&format!("-- {note}\n"));
161            }
162            out.push_str(&compiled.sql);
163            out.push('\n');
164        }
165        Err(e) => out.push_str(&format!("-- cannot compile: {e}\n")),
166    }
167    Ok(out)
168}