Skip to main content

spacedb_query/
functions.rs

1//! **Database Functions** — read-write compute-to-data (SpaceDB UX mission M4).
2//!
3//! A Database Function is developer-authored WASM that runs next to the data with a
4//! host context: it **reads a pinned record snapshot** and **writes through a
5//! buffered write-set** the caller applies only if the run succeeds. This is the
6//! deliberate, designed extension of the runtime's "no host imports" rule — the
7//! determinism contract survives because every host call is a pure function of
8//! `(snapshot, the run's own prior writes, payload)`:
9//!
10//! > same module + same input + same snapshot ⇒ same output, same write-set,
11//! > same fuel — on any host.
12//!
13//! Corroboration therefore extends to mutations: redundant executors must agree on
14//! [`FunctionCtx::writes_digest`] as well as the output digest, and the caller
15//! applies the write-set **once** (keyed by a deterministic run id) no matter how
16//! many corroborating nodes ran it.
17//!
18//! ## The host ABI (one import)
19//!
20//! In addition to the base ABI (`memory` / `alloc` / `run`), a function module may
21//! import exactly one host function:
22//!
23//! ```wat
24//! (import "spacedb" "host_call" (func (param i32 i32 i32 i32) (result i64)))
25//! ```
26//!
27//! `host_call(op_ptr, op_len, payload_ptr, payload_len)` returns the response slice
28//! packed `(ptr << 32) | len` (written into guest memory via the guest's `alloc`).
29//! Ops and their payloads (`\0` = a NUL byte; collections and record ids must be
30//! NUL-free UTF-8):
31//!
32//! | op       | payload                    | response                                       |
33//! |----------|----------------------------|------------------------------------------------|
34//! | `get`    | `collection \0 id`         | `[0]` absent · `[1] ++ value` present          |
35//! | `query`  | `collection`               | per record, sorted by id: `u32le(id_len) ++ id ++ u32le(val_len) ++ value` |
36//! | `put`    | `collection \0 id \0 value`| empty (buffered)                               |
37//! | `delete` | `collection \0 id`         | empty (buffered tombstone)                     |
38//!
39//! A rights violation, a zero-knowledge collection, or a malformed payload **traps
40//! the run** — the write-set is discarded with it (all-or-nothing).
41
42use std::collections::{BTreeMap, BTreeSet};
43use std::sync::Arc;
44
45use wasmtime::{
46    Caller, Engine, Instance, Linker, Memory, Module, Store, StoreLimits, StoreLimitsBuilder,
47    TypedFunc,
48};
49
50use crate::corroborate::FunctionRun;
51use crate::error::{QueryError, QueryResult};
52use crate::runtime::{Execution, FunctionRuntime, RunLimits};
53
54/// A pinned record view: `(collection, record id) → value bytes`, materialized at
55/// one frontier. `BTreeMap` so iteration (and every digest over it) is
56/// deterministic on every host.
57pub type RecordSnapshot = BTreeMap<(String, String), Vec<u8>>;
58
59/// A [`RecordSnapshot`] shared between the functions that run over it, with its
60/// content hash taken once. Every [`FunctionCtx`] built from it holds the same
61/// records (no clone per run) and the same hash (no re-hash per run).
62#[derive(Clone, Debug)]
63pub struct PinnedRecords {
64    records: Arc<RecordSnapshot>,
65    hash: [u8; 32],
66}
67
68impl PinnedRecords {
69    /// Pin `records`, hashing them once.
70    pub fn new(records: RecordSnapshot) -> Self {
71        let hash = hash_records(&records);
72        Self {
73            records: Arc::new(records),
74            hash,
75        }
76    }
77
78    /// The records.
79    pub fn records(&self) -> &RecordSnapshot {
80        &self.records
81    }
82
83    /// Content hash of the records (what [`FunctionCtx::snapshot_hash`] reports).
84    pub fn hash(&self) -> [u8; 32] {
85        self.hash
86    }
87}
88
89/// What the invoking capability lets the function do — checked on **every** host
90/// call. A function has exactly the caller's rights, never more.
91#[derive(Clone, Copy, Debug, PartialEq, Eq)]
92pub struct CtxRights {
93    pub read: bool,
94    pub write: bool,
95}
96
97/// The context one function invocation executes in: the pinned snapshot it reads,
98/// the write-set it accumulates, the rights it may exercise, and the collections
99/// it must be refused (zero-knowledge: the host holds ciphertext it provably
100/// cannot compute on — serving it to server-side code would break that promise).
101#[derive(Debug)]
102pub struct FunctionCtx {
103    snapshot: Arc<RecordSnapshot>,
104    snapshot_hash: [u8; 32],
105    /// This run's buffered mutations: `Some(value)` = put, `None` = tombstone.
106    /// Overlaid on the snapshot for read-your-writes; applied by the caller only
107    /// after a successful run.
108    overlay: BTreeMap<(String, String), Option<Vec<u8>>>,
109    rights: CtxRights,
110    denied: BTreeSet<String>,
111    /// Scratch `(collection, id)` for `get` lookups: the maps are keyed by owned
112    /// strings, so a lookup needs one - reused rather than allocated per call.
113    lookup: (String, String),
114}
115
116impl FunctionCtx {
117    pub fn new(snapshot: RecordSnapshot, rights: CtxRights, denied: BTreeSet<String>) -> Self {
118        Self::with_pinned(&PinnedRecords::new(snapshot), rights, denied)
119    }
120
121    /// A context over an already-pinned snapshot: the records are shared, not
122    /// copied, and their hash is reused.
123    pub fn with_pinned(pinned: &PinnedRecords, rights: CtxRights, denied: BTreeSet<String>) -> Self {
124        Self {
125            snapshot: Arc::clone(&pinned.records),
126            snapshot_hash: pinned.hash,
127            overlay: BTreeMap::new(),
128            rights,
129            denied,
130            lookup: (String::new(), String::new()),
131        }
132    }
133
134    /// Content hash of the pinned snapshot — bound into the run's `input_digest`
135    /// so corroboration can only succeed between runs that saw the same data.
136    pub fn snapshot_hash(&self) -> [u8; 32] {
137        self.snapshot_hash
138    }
139
140    /// The buffered write-set in deterministic order (`Some` = put, `None` = delete).
141    pub fn writes(&self) -> &BTreeMap<(String, String), Option<Vec<u8>>> {
142        &self.overlay
143    }
144
145    /// Digest of the write-set — the second half of mutation corroboration
146    /// (executors must agree on it, not just on the output).
147    pub fn writes_digest(&self) -> [u8; 32] {
148        let mut h = blake3::Hasher::new();
149        for ((c, id), v) in &self.overlay {
150            frame(&mut h, c.as_bytes());
151            frame(&mut h, id.as_bytes());
152            match v {
153                Some(bytes) => {
154                    h.update(&[1]);
155                    frame(&mut h, bytes);
156                }
157                None => {
158                    h.update(&[0]);
159                }
160            }
161        }
162        *h.finalize().as_bytes()
163    }
164
165    /// Total key+value bytes the write-set will add to the store — what the caller
166    /// bills as propagated transit when the writes replicate.
167    pub fn write_bytes(&self) -> u64 {
168        self.overlay
169            .iter()
170            .map(|((c, id), v)| {
171                (c.len() + id.len() + v.as_ref().map(Vec::len).unwrap_or(0)) as u64
172            })
173            .sum()
174    }
175
176    /// Serve one host call into `out` (cleared first). Pure over `(snapshot,
177    /// overlay-so-far, op, payload)` — the determinism contract's load-bearing
178    /// property. Errors trap the run.
179    fn dispatch(&mut self, op: &str, payload: &[u8], out: &mut Vec<u8>) -> Result<(), String> {
180        out.clear();
181        match op {
182            "get" => {
183                if !self.rights.read {
184                    return Err("rights: get requires database:read".into());
185                }
186                let (c, id) = split2(payload).ok_or("get: payload must be collection\\0id")?;
187                self.check_open(c)?;
188                let (lc, lid) = &mut self.lookup;
189                lc.clear();
190                lc.push_str(c);
191                lid.clear();
192                lid.push_str(id);
193                let value = match self.overlay.get(&self.lookup) {
194                    Some(v) => v.as_deref(),                     // read-your-writes
195                    None => self.snapshot.get(&self.lookup).map(Vec::as_slice),
196                };
197                match value {
198                    Some(v) => {
199                        out.push(1);
200                        out.extend_from_slice(v);
201                    }
202                    None => out.push(0),
203                }
204                Ok(())
205            }
206            "query" => {
207                if !self.rights.read {
208                    return Err("rights: query requires database:read".into());
209                }
210                let c = std::str::from_utf8(payload).map_err(|_| "query: collection must be UTF-8")?;
211                self.check_open(c)?;
212                // Snapshot merged with this run's overlay, sorted by id (BTreeMap order).
213                // Both maps order by (collection, id), so collection `c` is the
214                // contiguous range starting at (c, "") - read just that.
215                let (lc, lid) = &mut self.lookup;
216                lc.clear();
217                lc.push_str(c);
218                lid.clear();
219                let from = &self.lookup;
220                let mut live: BTreeMap<&str, &[u8]> = self
221                    .snapshot
222                    .range::<(String, String), _>(from..)
223                    .take_while(|((col, _), _)| col == c)
224                    .map(|((_, id), v)| (id.as_str(), v.as_slice()))
225                    .collect();
226                for ((col, id), v) in self.overlay.range::<(String, String), _>(from..) {
227                    if col != c {
228                        break;
229                    }
230                    match v {
231                        Some(bytes) => {
232                            live.insert(id.as_str(), bytes.as_slice());
233                        }
234                        None => {
235                            live.remove(id.as_str());
236                        }
237                    }
238                }
239                for (id, v) in live {
240                    frame_into(out, id.as_bytes());
241                    frame_into(out, v);
242                }
243                Ok(())
244            }
245            "put" => {
246                if !self.rights.write {
247                    return Err("rights: put requires database:write".into());
248                }
249                let (c, id, value) =
250                    split3(payload).ok_or("put: payload must be collection\\0id\\0value")?;
251                self.check_open(c)?;
252                self.overlay.insert((c.to_string(), id.to_string()), Some(value.to_vec()));
253                Ok(())
254            }
255            "delete" => {
256                if !self.rights.write {
257                    return Err("rights: delete requires database:write".into());
258                }
259                let (c, id) = split2(payload).ok_or("delete: payload must be collection\\0id")?;
260                self.check_open(c)?;
261                self.overlay.insert((c.to_string(), id.to_string()), None);
262                Ok(())
263            }
264            other => Err(format!("unknown host op `{other}`")),
265        }
266    }
267
268    fn check_open(&self, collection: &str) -> Result<(), String> {
269        if self.denied.contains(collection) {
270            return Err(format!(
271                "collection `{collection}` is zero-knowledge: the host cannot compute on it"
272            ));
273        }
274        Ok(())
275    }
276}
277
278/// One completed function invocation: the execution (output + attestation, with the
279/// snapshot hash bound into `input_digest`) and the context carrying the write-set.
280#[derive(Debug)]
281pub struct FunctionOutcome {
282    pub execution: Execution,
283    pub ctx: FunctionCtx,
284}
285
286pub(crate) struct CtxHostState {
287    limits: StoreLimits,
288    ctx: FunctionCtx,
289    /// The guest's `memory` and `alloc`, resolved once after instantiation so a
290    /// host call does not look both up by name (and re-check `alloc`'s
291    /// signature) every time. `None` only while the instance is still being
292    /// built; `host_call` falls back to the by-name lookup then.
293    memory: Option<Memory>,
294    alloc: Option<TypedFunc<i32, i32>>,
295    /// The response buffer, reused across this run's host calls.
296    resp: Vec<u8>,
297}
298
299impl FunctionRuntime {
300    /// Deploy-time validation: the module may import **only** `spacedb::host_call`
301    /// (and must speak the base ABI). Anything else is rejected before it can ever
302    /// run — the allowlist is what keeps "deterministic" checkable.
303    pub fn validate_function(&self, module_wasm: &[u8]) -> QueryResult<()> {
304        let module = Module::new(self.engine(), module_wasm)
305            .map_err(|e| QueryError::Compile(e.to_string()))?;
306        for import in module.imports() {
307            if !(import.module() == "spacedb" && import.name() == "host_call") {
308                return Err(QueryError::Abi(format!(
309                    "forbidden import `{}::{}` — functions may import only spacedb::host_call",
310                    import.module(),
311                    import.name()
312                )));
313            }
314        }
315        for export in ["memory", "alloc", "run"] {
316            if module.get_export(export).is_none() {
317                return Err(QueryError::Abi(format!("missing required export `{export}`")));
318            }
319        }
320        Ok(())
321    }
322
323    /// Run a Database Function over `input` with `ctx` under `limits`. Reads come
324    /// from the pinned snapshot (+ the run's own writes); writes buffer into the
325    /// ctx, returned for the caller to apply **once** on success. The attestation's
326    /// `input_digest` is `hash(input ‖ snapshot_hash)` so corroboration binds to
327    /// the exact data the run saw.
328    pub fn run_with_ctx(
329        &self,
330        module_wasm: &[u8],
331        input: &[u8],
332        limits: &RunLimits,
333        ctx: FunctionCtx,
334    ) -> QueryResult<FunctionOutcome> {
335        let workload_hash = hash(module_wasm);
336        let input_digest = {
337            let mut h = blake3::Hasher::new();
338            h.update(input);
339            h.update(&ctx.snapshot_hash());
340            *h.finalize().as_bytes()
341        };
342
343        let module = self.module(&workload_hash, module_wasm)?;
344
345        let max_bytes = limits.max_mem_mb as usize * 1024 * 1024;
346        let mut store = Store::new(
347            self.engine(),
348            CtxHostState {
349                limits: StoreLimitsBuilder::new().memory_size(max_bytes).build(),
350                ctx,
351                memory: None,
352                alloc: None,
353                resp: Vec::new(),
354            },
355        );
356        store.limiter(|h| &mut h.limits);
357        store.set_fuel(limits.max_fuel).map_err(|e| QueryError::Fuel(e.to_string()))?;
358
359        // The linker was built once with the runtime (`ctx_linker`): a run only
360        // instantiates from it.
361        let instance: Instance = self
362            .ctx_linker()
363            .instantiate(&mut store, &module)
364            .map_err(|e| QueryError::Instantiate(e.to_string()))?;
365
366        let memory = instance
367            .get_memory(&mut store, "memory")
368            .ok_or(QueryError::MissingExport("memory"))?;
369        let alloc: TypedFunc<i32, i32> = instance
370            .get_typed_func(&mut store, "alloc")
371            .map_err(|_| QueryError::MissingExport("alloc"))?;
372        let run: TypedFunc<(i32, i32), i64> = instance
373            .get_typed_func(&mut store, "run")
374            .map_err(|_| QueryError::MissingExport("run"))?;
375        store.data_mut().memory = Some(memory);
376        store.data_mut().alloc = Some(alloc.clone());
377
378        let in_len =
379            i32::try_from(input.len()).map_err(|_| QueryError::Abi("input too large".into()))?;
380        let in_ptr = alloc.call(&mut store, in_len).map_err(|e| QueryError::Trap(e.to_string()))?;
381        memory
382            .write(&mut store, in_ptr as usize, input)
383            .map_err(|e| QueryError::Abi(format!("input write: {e}")))?;
384
385        let packed =
386            run.call(&mut store, (in_ptr, in_len)).map_err(|e| QueryError::Trap(e.to_string()))?;
387        let packed = packed as u64;
388        let (out_ptr, out_len) = ((packed >> 32) as usize, (packed & 0xFFFF_FFFF) as usize);
389        let output = read_output(memory.data(&store), out_ptr, out_len)?;
390        let output_digest = hash(&output);
391
392        let remaining = store.get_fuel().map_err(|e| QueryError::Fuel(e.to_string()))?;
393        let fuel_used = limits.max_fuel.saturating_sub(remaining);
394        let mem_peak_mb = (memory.data_size(&store) / (1024 * 1024)) as u32;
395
396        Ok(FunctionOutcome {
397            execution: Execution {
398                output,
399                run: FunctionRun {
400                    workload_hash,
401                    input_digest,
402                    output_digest,
403                    fuel_used,
404                    mem_peak_mb,
405                },
406            },
407            ctx: store.into_data().ctx,
408        })
409    }
410}
411
412/// The Database-Function linker: exactly one import, `spacedb::host_call`.
413pub(crate) fn ctx_linker(engine: &Engine) -> QueryResult<Linker<CtxHostState>> {
414    let mut linker: Linker<CtxHostState> = Linker::new(engine);
415    linker
416        .func_wrap("spacedb", "host_call", host_call)
417        .map_err(|e| QueryError::Instantiate(e.to_string()))?;
418    Ok(linker)
419}
420
421/// `spacedb::host_call(op_ptr, op_len, payload_ptr, payload_len) -> packed response`.
422fn host_call(
423    mut caller: Caller<'_, CtxHostState>,
424    op_ptr: i32,
425    op_len: i32,
426    pay_ptr: i32,
427    pay_len: i32,
428) -> wasmtime::Result<i64> {
429    let memory = match caller.data().memory {
430        Some(memory) => memory,
431        None => caller
432            .get_export("memory")
433            .and_then(|e| e.into_memory())
434            .ok_or_else(|| wasmtime::Error::msg("host_call: no guest memory"))?,
435    };
436
437    // 1. Borrow op + payload straight out of guest memory and
438    // 2. dispatch — pure over (snapshot, overlay, op, payload).
439    // `data_and_store_mut` hands out the guest's bytes and the host state
440    // together (disjoint borrows), so neither the op nor the payload is
441    // copied out first.
442    let resp = {
443        let (data, state) = memory.data_and_store_mut(&mut caller);
444        let data: &[u8] = data;
445        let slice = |ptr: i32, len: i32| {
446            let (ptr, len) = (ptr as usize, len as usize);
447            data.get(ptr..ptr + len)
448                .ok_or_else(|| wasmtime::Error::msg("host_call: slice out of bounds"))
449        };
450        let op_bytes = slice(op_ptr, op_len)?;
451        let payload = slice(pay_ptr, pay_len)?;
452        let op = std::str::from_utf8(op_bytes)
453            .map_err(|_| wasmtime::Error::msg("host_call: op must be UTF-8"))?;
454        let mut resp = std::mem::take(&mut state.resp);
455        state
456            .ctx
457            .dispatch(op, payload, &mut resp)
458            .map_err(wasmtime::Error::msg)?;
459        resp
460    };
461
462    // 3. Hand the response back through the guest's own allocator (a reentrant
463    //    call — its fuel burns deterministically).
464    let alloc: TypedFunc<i32, i32> = match caller.data().alloc.clone() {
465        Some(alloc) => alloc,
466        None => caller
467            .get_export("alloc")
468            .and_then(|e| e.into_func())
469            .ok_or_else(|| wasmtime::Error::msg("host_call: no guest alloc"))?
470            .typed(&caller)
471            .map_err(|e| wasmtime::Error::msg(format!("host_call: alloc: {e}")))?,
472    };
473    let len = i32::try_from(resp.len())
474        .map_err(|_| wasmtime::Error::msg("host_call: response too large"))?;
475    let ptr = alloc.call(&mut caller, len)?;
476    memory.write(&mut caller, ptr as usize, &resp)?;
477    let packed = (((ptr as u32) as i64) << 32) | (resp.len() as u32) as i64;
478    caller.data_mut().resp = resp; // keep the buffer for the next call
479    Ok(packed)
480}
481
482// ── framing helpers ────────────────────────────────────────────────────────────
483
484/// Copy the guest's `(out_ptr, out_len)` result slice out of its memory — one
485/// copy, where a zeroed buffer filled by `Memory::read` was a memset and a copy.
486pub(crate) fn read_output(data: &[u8], out_ptr: usize, out_len: usize) -> QueryResult<Vec<u8>> {
487    out_ptr
488        .checked_add(out_len)
489        .and_then(|end| data.get(out_ptr..end))
490        .map(<[u8]>::to_vec)
491        .ok_or_else(|| {
492            // `Memory::read`'s error, word for word.
493            QueryError::Abi(format!(
494                "output read at {out_ptr}+{out_len}: out of bounds memory access"
495            ))
496        })
497}
498
499/// `collection \0 id` (both NUL-free UTF-8).
500fn split2(payload: &[u8]) -> Option<(&str, &str)> {
501    let nul = payload.iter().position(|b| *b == 0)?;
502    let c = std::str::from_utf8(&payload[..nul]).ok()?;
503    let id = std::str::from_utf8(&payload[nul + 1..]).ok()?;
504    (!id.as_bytes().contains(&0)).then_some((c, id))
505}
506
507/// `collection \0 id \0 value` (value = arbitrary bytes, so it goes last).
508fn split3(payload: &[u8]) -> Option<(&str, &str, &[u8])> {
509    let first = payload.iter().position(|b| *b == 0)?;
510    let rest = &payload[first + 1..];
511    let second = rest.iter().position(|b| *b == 0)?;
512    let c = std::str::from_utf8(&payload[..first]).ok()?;
513    let id = std::str::from_utf8(&rest[..second]).ok()?;
514    Some((c, id, &rest[second + 1..]))
515}
516
517fn frame(h: &mut blake3::Hasher, bytes: &[u8]) {
518    h.update(&(bytes.len() as u32).to_le_bytes());
519    h.update(bytes);
520}
521
522fn frame_into(out: &mut Vec<u8>, bytes: &[u8]) {
523    out.extend_from_slice(&(bytes.len() as u32).to_le_bytes());
524    out.extend_from_slice(bytes);
525}
526
527fn hash_records(records: &RecordSnapshot) -> [u8; 32] {
528    let mut h = blake3::Hasher::new();
529    for ((c, id), v) in records {
530        frame(&mut h, c.as_bytes());
531        frame(&mut h, id.as_bytes());
532        frame(&mut h, v);
533    }
534    *h.finalize().as_bytes()
535}
536
537fn hash(bytes: &[u8]) -> [u8; 32] {
538    *blake3::hash(bytes).as_bytes()
539}