Skip to main content

datumesh_http/
foreign.rs

1//! Cross-mesh resolution (SPEC 9.6, 9.7), minimal form: names under hosts this mesh does not
2//! own.
3//!
4//! # How the engine sees foreign names
5//!
6//! The engine reads only its store, and the store holds only what verified on the way in. So
7//! foreign records are **imported into the store before the engine reads them**, through a
8//! read-through layer around every runtime ([`CrossMesh`]): when a function reads a name under
9//! a host this mesh does not own, the layer first
10//!
11//! 1. resolves that host (its key document and its mesh document, `resolve_mesh`, cached),
12//! 2. brings the name's bindings up to date from the host's bindings resource (9.7): the
13//!    binding answering now and, walking back by `since`, every earlier one the store lacks,
14//!    each with its descriptor (fetched by hash, checked by `put_descriptor`), appended with
15//!    `bind_name` in order;
16//! 3. for a **stored** function, brings the cell's versions up to date: the host's envelope
17//!    for the cell now, checked with `check_envelope_any` against the signer's key document
18//!    (fetched from its host over TLS, never from the mesh that served the receipt); then,
19//!    walking back (as of just before each receipt's start), every earlier version the store
20//!    lacks; each receipt stored with `put_receipt` (which verifies it again against the key
21//!    document stored for its signer) and `put_version`, oldest first.
22//!
23//! A foreign function that is not stored (a formula on the other mesh) is evaluated by this
24//! mesh from its descriptor and its inputs, which are imported the same way: its value is
25//! recomputed, never taken on trust.
26//!
27//! Versions and bindings are append-only in the store, in transaction order; importing the
28//! full history back to the first version (or binding) the store lacks keeps them so, so the
29//! store answers every asof as the other mesh would. A history that does not extend what the
30//! store holds (the other mesh rewrote it) is refused with `E_INPUT_UNAVAILABLE`.
31//!
32//! Answers for asofs at or before the last confirmation never change; answers about "now"
33//! are confirmed again after [`Ttls::current`](crate::config::Ttls) (bindings after
34//! `Ttls::binding`). The memo is kept honest by [`Foreign::take_invalidated`]: every cell
35//! whose versions grew is reported to the engine (`stored_version_added`) after the request.
36//!
37//! # Caches and lifetimes
38//!
39//! | What | Where | Lifetime |
40//! |---|---|---|
41//! | key documents | memory ([`KeyCache`]) and the store's namespace record | 300 s; a key id the cached document lacks refetches it at once (at most every 10 s) |
42//! | mesh documents | memory | 300 s |
43//! | a name's bindings | the store | confirmed again after 60 s |
44//! | a cell's versions | the store | confirmed again after 60 s, for requests about now |
45//! | descriptors, receipts | the store | forever: content-addressed |
46//!
47//! Not in 0.1.0: slices over foreign functions (`E_INPUT_UNAVAILABLE`: the store would hold
48//! only the members read so far), cells of a foreign name's earlier bindings that were never
49//! imported while current, and `pending` answers from the other mesh (`E_INPUT_UNAVAILABLE`).
50
51use std::collections::{BTreeMap, HashMap, HashSet};
52use std::sync::{Arc, Mutex};
53use std::time::{Duration, Instant};
54
55use datumesh_core::json::{self, Value};
56use datumesh_core::{
57    check_envelope_any, format_uri, keys_from_response, lexical, resolve_mesh, AnyEnvelope, Args, Cell, CellRef,
58    Error as CoreError, ErrorCode, FunctionDescriptor, KeyDoc, Keys, MeshDoc, Receipt, Request, Retrieval, Scalar,
59};
60use datumesh_engine::{Budget, Clock, EvalError, FnBinding, Input, Inputs, Member, Runtime, SlicePattern};
61use datumesh_store::Store;
62
63use crate::config::Config;
64
65/// The largest body read from another mesh.
66const MAX_BODY: u64 = 16 << 20;
67/// The largest key or mesh document read (SPEC 9.3's suggested bound).
68const MAX_DOC: u64 = 256 << 10;
69/// The most versions or bindings one walk imports.
70const MAX_WALK: usize = 10_000;
71
72/// The latest instant: the store's latest binding or version is the one answering then.
73const END: &str = "9999-12-31T23:59:59.999999Z";
74
75/// Key documents this mesh has fetched or been given, by host: each the result of
76/// interpreting a retrieval (SPEC 9.3), a failure included.
77#[derive(Default)]
78pub struct KeyCache {
79    #[allow(clippy::type_complexity)]
80    docs: Mutex<HashMap<String, (Result<KeyDoc, CoreError>, Vec<u8>, Instant)>>,
81}
82
83impl std::fmt::Debug for KeyCache {
84    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
85        f.debug_struct("KeyCache").field("hosts", &self.docs.lock().map(|d| d.len()).unwrap_or(0)).finish()
86    }
87}
88
89impl KeyCache {
90    /// Adds (or replaces) `host`'s key document, checked as a 200 response for that host;
91    /// a document that fails the check is not added.
92    pub fn insert(&self, host: &str, doc: &[u8]) -> Result<(), CoreError> {
93        let kd = keys_from_response(host, 200, Some(doc))?;
94        self.docs
95            .lock()
96            .unwrap_or_else(|p| p.into_inner())
97            .insert(host.to_string(), (Ok(kd), doc.to_vec(), Instant::now()));
98        Ok(())
99    }
100
101    /// Records what retrieving `host`'s key document gave (status and body, as SPEC 9.3
102    /// interprets them): a document, or the failure (`E_KEY_UNAVAILABLE`, `E_KEY_DOC`).
103    pub fn insert_response(&self, host: &str, status: u16, body: Option<&[u8]>) {
104        let r = keys_from_response(host, status, body);
105        self.docs
106            .lock()
107            .unwrap_or_else(|p| p.into_inner())
108            .insert(host.to_string(), (r, body.unwrap_or_default().to_vec(), Instant::now()));
109    }
110
111    /// `host`'s document, its bytes and when it was fetched.
112    pub fn get(&self, host: &str) -> Option<(KeyDoc, Vec<u8>, Instant)> {
113        match self.docs.lock().unwrap_or_else(|p| p.into_inner()).get(host) {
114            Some((Ok(d), b, at)) => Some((d.clone(), b.clone(), *at)),
115            _ => None,
116        }
117    }
118
119    /// What is recorded for `host`: its document or the failure.
120    pub fn result(&self, host: &str) -> Option<Result<KeyDoc, CoreError>> {
121        self.docs.lock().unwrap_or_else(|p| p.into_inner()).get(host).map(|(r, _, _)| r.clone())
122    }
123
124    /// Forgets `host`'s document.
125    pub fn remove(&self, host: &str) {
126        self.docs.lock().unwrap_or_else(|p| p.into_inner()).remove(host);
127    }
128}
129
130/// A failure of cross-mesh resolution: the code of the `error` envelope it gives, and why.
131#[derive(Clone, Debug)]
132pub struct ForeignError {
133    /// `E_INPUT_UNAVAILABLE` (the other mesh is down or answered otherwise), `E_MESH_DOC`,
134    /// `E_KEY_UNAVAILABLE` or `E_KEY_DOC` (resolving its host), or what checking its envelope
135    /// gave.
136    pub code: ErrorCode,
137    /// Why.
138    pub detail: String,
139}
140
141impl ForeignError {
142    fn new(code: ErrorCode, detail: impl Into<String>) -> ForeignError {
143        ForeignError { code, detail: detail.into() }
144    }
145    fn unavailable(detail: impl Into<String>) -> ForeignError {
146        ForeignError::new(ErrorCode::InputUnavailable, detail)
147    }
148    /// As an evaluation error (the engine reports it as `EngineError::Invalid`, which the
149    /// mesh answers `error` with this code).
150    pub(crate) fn eval(self) -> EvalError {
151        EvalError::InvalidInput(CoreError::new(self.code, "$", format!("cross-mesh: {}", self.detail)))
152    }
153}
154
155/// Percent-encodes a value as SPEC 5.1 says (literal characters as themselves).
156pub fn pct(s: &str) -> String {
157    let mut out = String::with_capacity(s.len());
158    for b in s.bytes() {
159        if b.is_ascii_alphanumeric() || matches!(b, b'-' | b'.' | b'_' | b'~' | b':') {
160            out.push(b as char);
161        } else {
162            out.push_str(&format!("%{b:02X}"));
163        }
164    }
165    out
166}
167
168/// One microsecond before `t`.
169fn before(t: &str) -> Option<String> {
170    let us = datumesh_formula::calendar::parse_instant(t)?;
171    datumesh_formula::calendar::instant_text(us - 1)
172}
173
174/// The host of a function name or namespace: its first segment.
175pub fn host_of(name: &str) -> &str {
176    name.split('/').next().unwrap_or(name)
177}
178
179struct Confirmed {
180    at: Instant,
181    /// The mesh's clock reading then: answers as of it or earlier never change.
182    instant: String,
183}
184
185/// The cross-mesh resolver of a mesh.
186pub struct Foreign {
187    store: Arc<dyn Store + Send + Sync>,
188    keys: Arc<KeyCache>,
189    clock: Arc<dyn Clock>,
190    agent: ureq::Agent,
191    owned: Vec<String>,
192    enabled: bool,
193    allowed: Option<Vec<String>>,
194    peers: BTreeMap<String, String>,
195    ttl_key: Duration,
196    ttl_refetch: Duration,
197    ttl_mesh: Duration,
198    ttl_binding: Duration,
199    ttl_current: Duration,
200    meshes: Mutex<HashMap<String, (MeshDoc, Instant)>>,
201    names: Mutex<HashMap<String, Confirmed>>,
202    cells: Mutex<HashMap<String, Confirmed>>,
203    invalidated: Mutex<Vec<String>>,
204    /// Whether `invalidated` may be non-empty, and whether any cell was imported (checked
205    /// without a lock on every answer).
206    dirty: std::sync::atomic::AtomicBool,
207    any: std::sync::atomic::AtomicBool,
208    deps: Mutex<HashMap<String, Arc<Vec<Cell>>>>,
209    /// Counters for /metrics.
210    pub(crate) fetches: std::sync::atomic::AtomicU64,
211    pub(crate) failures: std::sync::atomic::AtomicU64,
212    pub(crate) imported: std::sync::atomic::AtomicU64,
213}
214
215impl std::fmt::Debug for Foreign {
216    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
217        f.debug_struct("Foreign").field("owned", &self.owned).field("enabled", &self.enabled).finish_non_exhaustive()
218    }
219}
220
221enum Fetched {
222    Receipt(Vec<u8>, Box<Receipt>),
223    NotCovered,
224}
225
226impl Foreign {
227    pub(crate) fn new(
228        config: &Config,
229        store: Arc<dyn Store + Send + Sync>,
230        keys: Arc<KeyCache>,
231        clock: Arc<dyn Clock>,
232    ) -> Foreign {
233        let agent: ureq::Agent = ureq::Agent::config_builder()
234            .max_redirects(0)
235            .http_status_as_error(false)
236            .timeout_global(Some(config.peer_timeout))
237            .user_agent(concat!("datumesh-mesh/", env!("CARGO_PKG_VERSION")))
238            .build()
239            .into();
240        Foreign {
241            store,
242            keys,
243            clock,
244            agent,
245            owned: config.namespaces.clone(),
246            enabled: config.cross_mesh,
247            allowed: config.cross_mesh_hosts.clone(),
248            peers: config.peers.clone(),
249            ttl_key: config.ttl.key_doc,
250            ttl_refetch: config.ttl.key_refetch,
251            ttl_mesh: config.ttl.mesh_doc,
252            ttl_binding: config.ttl.binding,
253            ttl_current: config.ttl.current,
254            meshes: Mutex::new(HashMap::new()),
255            names: Mutex::new(HashMap::new()),
256            cells: Mutex::new(HashMap::new()),
257            invalidated: Mutex::new(Vec::new()),
258            dirty: Default::default(),
259            any: Default::default(),
260            deps: Mutex::new(HashMap::new()),
261            fetches: Default::default(),
262            failures: Default::default(),
263            imported: Default::default(),
264        }
265    }
266
267    /// Whether `name` (a function name) is under a host this mesh does not own, and
268    /// cross-mesh resolution is on.
269    pub fn is_foreign(&self, name: &str) -> bool {
270        let host = host_of(name);
271        self.enabled
272            && !self.owned.iter().any(|h| h == host)
273            && self.allowed.as_ref().is_none_or(|a| a.iter().any(|h| h == host))
274    }
275
276    /// Whether any foreign cell was ever imported (lineage checks are skipped otherwise).
277    pub fn any_cells(&self) -> bool {
278        self.any.load(std::sync::atomic::Ordering::Acquire)
279    }
280
281    /// The cells whose versions grew since the last call: the caller reports each to the
282    /// engine (`stored_version_added`).
283    pub fn take_invalidated(&self) -> Vec<String> {
284        if !self.dirty.swap(false, std::sync::atomic::Ordering::AcqRel) {
285            return Vec::new();
286        }
287        std::mem::take(&mut *self.invalidated.lock().unwrap_or_else(|p| p.into_inner()))
288    }
289
290    /// `GET url`, with the origin replaced for a configured peer: status and body.
291    fn get(&self, url: &str, limit: u64) -> Result<(u16, Vec<u8>), String> {
292        let mut target = url.to_string();
293        if let Some(rest) = url.strip_prefix("https://") {
294            let host = rest.split(['/', '?']).next().unwrap_or("");
295            if let Some(origin) = self.peers.get(host) {
296                target = format!("{origin}{}", &rest[host.len()..]);
297            }
298        }
299        self.fetches.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
300        let r = (|| {
301            let mut resp = self.agent.get(&target).call().map_err(|e| format!("{url}: {e}"))?;
302            let status = resp.status().as_u16();
303            let body = resp.body_mut().with_config().limit(limit).read_to_vec().map_err(|e| format!("{url}: {e}"))?;
304            Ok((status, body))
305        })();
306        if r.is_err() {
307            self.failures.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
308        }
309        r
310    }
311
312    /// The key document of `host`, from the cache while it is fresh, else fetched (SPEC 9.3).
313    /// `refresh` fetches it again unless it was fetched within the refetch interval.
314    pub fn keys_for(&self, host: &str, refresh: bool) -> Result<KeyDoc, ForeignError> {
315        if let Some((doc, _, at)) = self.keys.get(host) {
316            let age = at.elapsed();
317            if (!refresh && age < self.ttl_key) || (refresh && age < self.ttl_refetch) {
318                return Ok(doc);
319            }
320        }
321        if lexical::check_dns_name(host, "$").is_err() {
322            return Err(ForeignError::new(ErrorCode::KeyUnavailable, format!("{host:?} is not a DNS name")));
323        }
324        let url = format!("https://{host}/.well-known/datumesh.json");
325        let (status, body) = self.get(&url, MAX_DOC).map_err(|e| ForeignError::new(ErrorCode::KeyUnavailable, e))?;
326        let doc = keys_from_response(host, status, if status == 200 { Some(&body) } else { None })
327            .map_err(|e| ForeignError::new(e.code(), e.to_string()))?;
328        self.keys.insert(host, &body).map_err(|e| ForeignError::new(e.code(), e.to_string()))?;
329        Ok(doc)
330    }
331
332    /// The mesh document of `host`, resolved with its key document (SPEC 9.6), cached.
333    pub fn mesh(&self, host: &str) -> Result<MeshDoc, ForeignError> {
334        if let Some((m, at)) = self.meshes.lock().unwrap_or_else(|p| p.into_inner()).get(host) {
335            if at.elapsed() < self.ttl_mesh {
336                return Ok(m.clone());
337            }
338        }
339        if lexical::check_dns_name(host, "$").is_err() {
340            return Err(ForeignError::new(ErrorCode::KeyUnavailable, format!("{host:?} is not a DNS name")));
341        }
342        let keys = self.get(&format!("https://{host}/.well-known/datumesh.json"), MAX_DOC);
343        let mesh = match &keys {
344            Ok((200, _)) => self.get(&format!("https://{host}/.well-known/datumesh-mesh.json"), MAX_DOC),
345            _ => Err(String::new()),
346        };
347        fn ret(r: &Result<(u16, Vec<u8>), String>) -> Retrieval<'_> {
348            match r {
349                Ok((s, b)) => Retrieval::Response { status: *s, body: Some(b.as_slice()) },
350                Err(_) => Retrieval::Failed,
351            }
352        }
353        let resolved = resolve_mesh(host, ret(&keys), ret(&mesh)).map_err(|e| {
354            let detail = match (&keys, &mesh) {
355                (Err(e), _) | (_, Err(e)) if !e.is_empty() => e.clone(),
356                _ => e.to_string(),
357            };
358            ForeignError::new(e.code(), detail)
359        })?;
360        if let Ok((_, body)) = &keys {
361            let _ = self.keys.insert(host, body);
362        }
363        let m = resolved.mesh;
364        self.meshes.lock().unwrap_or_else(|p| p.into_inner()).insert(host.to_string(), (m.clone(), Instant::now()));
365        Ok(m)
366    }
367
368    /// The binding of `name` the host's bindings resource gives as of `asof` (now when
369    /// `None`): `(fn_hash, since)`.
370    fn remote_binding(
371        &self,
372        mesh: &MeshDoc,
373        name: &str,
374        asof: Option<&str>,
375    ) -> Result<Option<(String, String)>, ForeignError> {
376        let mut url = format!("{}?name={}", mesh.bindings, pct(name));
377        if let Some(a) = asof {
378            url.push_str(&format!("&asof={}", pct(a)));
379        }
380        let (status, body) = self.get(&url, MAX_DOC).map_err(ForeignError::unavailable)?;
381        if status != 200 {
382            return Err(ForeignError::unavailable(format!("{url}: status {status}")));
383        }
384        let v = json::parse(&body).map_err(|e| ForeignError::unavailable(format!("{url}: {e}")))?;
385        let Some(b) = v.get("bindings").and_then(|b| b.get(name)) else {
386            if v.get("bindings").and_then(Value::as_object).is_none() {
387                return Err(ForeignError::unavailable(format!("{url}: no bindings object")));
388            }
389            return Ok(None);
390        };
391        let h = b.get("fn_hash").and_then(Value::as_str).unwrap_or("");
392        let since = b.get("since").and_then(Value::as_str).unwrap_or("");
393        if lexical::check_hex(h, 64, "$").is_err() || lexical::check_instant(since, "$").is_err() {
394            return Err(ForeignError::unavailable(format!("{url}: malformed binding")));
395        }
396        if let Some(a) = asof {
397            if since > a {
398                return Err(ForeignError::unavailable(format!("{url}: a binding since after the asof")));
399            }
400        }
401        Ok(Some((h.to_string(), since.to_string())))
402    }
403
404    /// Brings the bindings of a foreign `name` up to date (when not confirmed within the TTL).
405    pub fn ensure_name(&self, name: &str) -> Result<(), ForeignError> {
406        if !self.is_foreign(name) {
407            return Ok(());
408        }
409        if let Some(c) = self.names.lock().unwrap_or_else(|p| p.into_inner()).get(name) {
410            if c.at.elapsed() < self.ttl_binding {
411                return Ok(());
412            }
413        }
414        let now = self.clock.now();
415        let mesh = self.mesh(host_of(name))?;
416        let local = self
417            .store
418            .resolve_binding(name, END)
419            .map_err(|e| ForeignError::unavailable(format!("store: {e}")))?
420            .map(|b| (b.fn_hash, b.tx));
421        let mut chain = Vec::new();
422        let mut at: Option<String> = None;
423        while let Some(b) = self.remote_binding(&mesh, name, at.as_deref())? {
424            if Some(&b) == local.as_ref() {
425                break;
426            }
427            if chain.len() >= MAX_WALK {
428                return Err(ForeignError::unavailable(format!("{name}: more than {MAX_WALK} bindings")));
429            }
430            at = Some(before(&b.1).ok_or_else(|| ForeignError::unavailable("a binding at the first instant"))?);
431            let stop = at.as_deref() < Some("0001-01-01T00:00:00.000000Z");
432            chain.push(b);
433            if stop {
434                break;
435            }
436        }
437        if let (Some(oldest), Some(l)) = (chain.last(), &local) {
438            if oldest.1 <= l.1 {
439                return Err(ForeignError::unavailable(format!("{name}: the other mesh's bindings do not extend ours")));
440            }
441        }
442        for (fn_hash, since) in chain.iter().rev() {
443            self.import_descriptor(&mesh, fn_hash)?;
444            self.store
445                .bind_name(name, fn_hash, since)
446                .map_err(|e| ForeignError::unavailable(format!("bind {name}: {e}")))?;
447        }
448        self.names
449            .lock()
450            .unwrap_or_else(|p| p.into_inner())
451            .insert(name.to_string(), Confirmed { at: Instant::now(), instant: now });
452        Ok(())
453    }
454
455    fn import_descriptor(&self, mesh: &MeshDoc, fn_hash: &str) -> Result<(), ForeignError> {
456        if self.store.descriptor(fn_hash).is_some() {
457            return Ok(());
458        }
459        let url = mesh
460            .url("descriptor", &[("hash", fn_hash)])
461            .ok_or_else(|| ForeignError::new(ErrorCode::MeshDoc, "no descriptor endpoint"))?;
462        let (status, body) = self.get(&url, MAX_BODY).map_err(ForeignError::unavailable)?;
463        if status != 200 {
464            return Err(ForeignError::new(ErrorCode::FnUnavailable, format!("{url}: status {status}")));
465        }
466        let h = self
467            .store
468            .put_descriptor(&body)
469            .map_err(|e| ForeignError::new(ErrorCode::FnHashMismatch, e.to_string()))?;
470        if h != fn_hash {
471            return Err(ForeignError::new(ErrorCode::FnHashMismatch, format!("{url} gave the descriptor {h}")));
472        }
473        Ok(())
474    }
475
476    /// The other mesh's answer for `cell` as of `asof` (now when `None`), checked as an
477    /// envelope against the request and the signer's key document.
478    fn fetch_cell(&self, mesh: &MeshDoc, cell: &Cell, asof: Option<&str>) -> Result<Fetched, ForeignError> {
479        let reference = CellRef {
480            ns: cell.ns.clone(),
481            fn_name: cell.fn_name.clone(),
482            args: cell.args.clone(),
483            asof: asof.map(str::to_string),
484        };
485        let uri = format_uri(&reference);
486        let url = mesh
487            .url("cell", &[("cell", &uri["cell://".len()..])])
488            .ok_or_else(|| ForeignError::new(ErrorCode::MeshDoc, "no cell endpoint"))?;
489        let (status, body) = self.get(&url, MAX_BODY).map_err(ForeignError::unavailable)?;
490        let request = Request::new(&cell.id(), asof).map_err(|_| ForeignError::unavailable("request"))?;
491        // The signer is named in the body: its key document comes from its own host.
492        let signer = json::parse(&body).ok().and_then(|v| {
493            v.get("receipt")?.get("computed_by")?.as_str().map(|s| s.split('#').next().unwrap_or("").to_string())
494        });
495        let mut refreshed = false;
496        loop {
497            let mut keys = Keys::new();
498            if let Some(h) = &signer {
499                keys.insert(self.keys_for(h, refreshed)?);
500            }
501            match check_envelope_any(status, &body, &keys, &request) {
502                Ok(AnyEnvelope::Envelope(env, _)) => {
503                    return match (env.outcome.as_str(), env.receipt) {
504                        ("ok" | "stale", Some(r)) => {
505                            // The receipt's own bytes, as served (put_receipt canonicalises).
506                            let bytes = json::parse(&body)
507                                .ok()
508                                .and_then(|v| v.get("receipt").map(Value::to_jcs))
509                                .ok_or_else(|| ForeignError::unavailable("receipt"))?;
510                            Ok(Fetched::Receipt(bytes, Box::new(r)))
511                        }
512                        ("not_covered", _) => Ok(Fetched::NotCovered),
513                        (o, _) => Err(ForeignError::unavailable(format!("{url}: {o}"))),
514                    };
515                }
516                Ok(other) => return Err(ForeignError::unavailable(format!("{url}: {}", other.outcome_str()))),
517                Err(e) if !refreshed && matches!(e.code(), ErrorCode::KeyUnknown | ErrorCode::KeyNotValid) => {
518                    refreshed = true;
519                }
520                Err(e) => {
521                    let code = match e.code() {
522                        ErrorCode::Envelope => ErrorCode::InputUnavailable,
523                        c => c,
524                    };
525                    return Err(ForeignError::new(code, format!("{url}: {e}")));
526                }
527            }
528        }
529    }
530
531    /// Brings the versions of a foreign stored cell up to date (when not confirmed within the
532    /// TTL). `Ok(true)` when versions were added.
533    pub fn ensure_cell(&self, cell: &Cell) -> Result<bool, ForeignError> {
534        let id = cell.id();
535        if let Some(c) = self.cells.lock().unwrap_or_else(|p| p.into_inner()).get(&id) {
536            if c.at.elapsed() < self.ttl_current {
537                return Ok(false);
538            }
539        }
540        let now = self.clock.now();
541        let name = cell.function_name();
542        let current = self
543            .store
544            .resolve_binding(&name, &now)
545            .map_err(|e| ForeignError::unavailable(format!("store: {e}")))?
546            .map(|b| b.fn_hash);
547        if current.as_deref() != Some(cell.fn_hash.as_str()) {
548            if self.cells.lock().unwrap_or_else(|p| p.into_inner()).contains_key(&id) {
549                // A cell of an earlier binding, imported while current: its versions are final.
550                return Ok(false);
551            }
552            return Err(ForeignError::unavailable(format!(
553                "{name}: a cell of an earlier binding is not resolved in 0.1.0"
554            )));
555        }
556        let mesh = self.mesh(host_of(&name))?;
557        let local = self.store.latest(&id).map_err(|e| ForeignError::unavailable(format!("store: {e}")))?;
558        let mut chain: Vec<(Vec<u8>, Box<Receipt>)> = Vec::new();
559        let mut at: Option<String> = None;
560        loop {
561            match self.fetch_cell(&mesh, cell, at.as_deref())? {
562                Fetched::NotCovered => break,
563                Fetched::Receipt(bytes, r) => {
564                    if local.as_ref().is_some_and(|v| v.receipt_hash == r.hash()) {
565                        break;
566                    }
567                    if chain.iter().any(|(_, c)| c.hash() == r.hash()) || chain.len() >= MAX_WALK {
568                        return Err(ForeignError::unavailable(format!(
569                            "{name}: the other mesh's history does not end"
570                        )));
571                    }
572                    let start = std::cmp::max(r.tx(), r.asof()).to_string();
573                    let next = before(&start);
574                    chain.push((bytes, r));
575                    match next {
576                        Some(t) => at = Some(t),
577                        None => break,
578                    }
579                }
580            }
581        }
582        if let (Some((_, oldest)), Some(l)) = (chain.last(), &local) {
583            if oldest.tx() <= l.tx.as_str() {
584                return Err(ForeignError::unavailable(format!("{name}: the other mesh's versions do not extend ours")));
585            }
586        }
587        let added = !chain.is_empty();
588        for (bytes, r) in chain.iter().rev() {
589            self.ensure_namespace(r.signer_host())?;
590            let h =
591                self.store.put_receipt(bytes).map_err(|e| ForeignError::unavailable(format!("put_receipt: {e}")))?;
592            self.store
593                .put_version(&id, r.tx(), &h)
594                .map_err(|e| ForeignError::unavailable(format!("put_version: {e}")))?;
595            self.imported.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
596        }
597        if added {
598            self.invalidated.lock().unwrap_or_else(|p| p.into_inner()).push(id.clone());
599            self.dirty.store(true, std::sync::atomic::Ordering::Release);
600        }
601        self.cells.lock().unwrap_or_else(|p| p.into_inner()).insert(id, Confirmed { at: Instant::now(), instant: now });
602        self.any.store(true, std::sync::atomic::Ordering::Release);
603        Ok(added)
604    }
605
606    /// Puts the signer host's key document (as cached, fetched from that host) in the store,
607    /// unless the store's is the same. Never for a host this mesh owns.
608    fn ensure_namespace(&self, host: &str) -> Result<(), ForeignError> {
609        if self.owned.iter().any(|h| h == host) {
610            return Ok(());
611        }
612        self.keys_for(host, false)?;
613        let (_, bytes, _) =
614            self.keys.get(host).ok_or_else(|| ForeignError::new(ErrorCode::KeyUnavailable, host.to_string()))?;
615        let stored = self.store.namespace(host).map_err(|e| ForeignError::unavailable(format!("store: {e}")))?;
616        if stored.as_ref().map(|n| n.keydoc.as_slice()) != Some(bytes.as_slice()) {
617            self.store
618                .put_namespace(host, &bytes, &self.clock.now())
619                .map_err(|e| ForeignError::new(ErrorCode::KeyDoc, format!("put_namespace {host}: {e}")))?;
620        }
621        Ok(())
622    }
623
624    /// The foreign stored cells a receipt rests on, through its lineage in the store
625    /// (bounded; cached by receipt hash).
626    fn foreign_deps(&self, receipt_hash: &str) -> Arc<Vec<Cell>> {
627        if let Some(d) = self.deps.lock().unwrap_or_else(|p| p.into_inner()).get(receipt_hash) {
628            return d.clone();
629        }
630        let mut out = Vec::new();
631        let mut seen = HashSet::new();
632        let mut todo = vec![receipt_hash.to_string()];
633        while let Some(h) = todo.pop() {
634            if !seen.insert(h.clone()) || seen.len() > 100_000 {
635                continue;
636            }
637            if h.starts_with("slice:") {
638                if let Some(m) = self.store.manifest(&h) {
639                    if let Ok(m) = datumesh_core::Manifest::from_json(&m) {
640                        todo.extend(m.members().iter().cloned());
641                    }
642                }
643                continue;
644            }
645            let Some(bytes) = self.store.receipt(&h) else {
646                continue;
647            };
648            let Ok(r) = Receipt::from_json(&bytes) else { continue };
649            if self.is_foreign(&r.cell().ns) && r.inputs().is_empty() {
650                out.push(r.cell().clone());
651            } else {
652                todo.extend(r.inputs().iter().cloned());
653            }
654        }
655        let d = Arc::new(out);
656        let mut deps = self.deps.lock().unwrap_or_else(|p| p.into_inner());
657        if deps.len() > 100_000 {
658            deps.clear();
659        }
660        deps.insert(receipt_hash.to_string(), d.clone());
661        d
662    }
663
664    /// Confirms the foreign cells an answer rests on, for an answer as of `asof`: those not
665    /// confirmed within the TTL and confirmed before `asof` are fetched again. `Ok(true)` when
666    /// versions were added (the caller answers again).
667    pub fn refresh_deps(&self, receipt_hash: &str, asof: &str) -> Result<bool, ForeignError> {
668        if !self.any_cells() {
669            return Ok(false);
670        }
671        let mut added = false;
672        for cell in self.foreign_deps(receipt_hash).iter() {
673            let stale = match self.cells.lock().unwrap_or_else(|p| p.into_inner()).get(&cell.id()) {
674                Some(c) => c.at.elapsed() >= self.ttl_current && asof > c.instant.as_str(),
675                None => true,
676            };
677            if stale {
678                added |= self.ensure_cell(cell)?;
679            }
680        }
681        Ok(added)
682    }
683
684    /// For a request about a foreign name as of `asof` (now when `None`): its bindings and,
685    /// for a stored function's cell, its versions, brought up to date when needed.
686    pub fn prepare(&self, cell: &Cell, stored: bool, asof: Option<&str>) -> Result<(), ForeignError> {
687        if !self.is_foreign(&cell.function_name()) || !stored {
688            return Ok(());
689        }
690        let fresh = match self.cells.lock().unwrap_or_else(|p| p.into_inner()).get(&cell.id()) {
691            Some(c) => c.at.elapsed() < self.ttl_current || asof.is_some_and(|a| a <= c.instant.as_str()),
692            None => false,
693        };
694        if !fresh {
695            self.ensure_cell(cell)?;
696        }
697        Ok(())
698    }
699}
700
701/// A runtime with cross-mesh reads in front of it (see the module documentation).
702pub struct CrossMesh {
703    inner: Arc<dyn Runtime>,
704    foreign: Arc<Foreign>,
705}
706
707impl CrossMesh {
708    /// `inner`, reading foreign names through `foreign`.
709    pub fn new(inner: Arc<dyn Runtime>, foreign: Arc<Foreign>) -> CrossMesh {
710        CrossMesh { inner, foreign }
711    }
712}
713
714impl Runtime for CrossMesh {
715    fn lang(&self) -> &str {
716        self.inner.lang()
717    }
718
719    fn evaluate(
720        &self,
721        descriptor: &FunctionDescriptor,
722        cell: &Cell,
723        inputs: &mut dyn Inputs,
724        budget: &mut Budget,
725    ) -> Result<Scalar, EvalError> {
726        for name in &descriptor.inputs {
727            self.foreign.ensure_name(name).map_err(ForeignError::eval)?;
728        }
729        let mut w = Through { inner: inputs, foreign: &self.foreign };
730        self.inner.evaluate(descriptor, cell, &mut w, budget)
731    }
732
733    fn asof_dependent(&self, descriptor: &FunctionDescriptor) -> bool {
734        self.inner.asof_dependent(descriptor)
735    }
736}
737
738/// The inputs of one evaluation, foreign reads imported first.
739struct Through<'a> {
740    inner: &'a mut dyn Inputs,
741    foreign: &'a Foreign,
742}
743
744impl Through<'_> {
745    fn pre(&mut self, name: &str, args: &Args, at: Option<&str>) -> Result<(), EvalError> {
746        if !self.foreign.is_foreign(name) {
747            return Ok(());
748        }
749        self.foreign.ensure_name(name).map_err(ForeignError::eval)?;
750        let Some(b) = self.inner.binding_peek(name, at)? else {
751            return Ok(());
752        };
753        if b.descriptor.lang != "stored" {
754            return Ok(());
755        }
756        let (ns, f) = name.rsplit_once('/').unwrap_or((name, ""));
757        let cell = Cell { ns: ns.to_string(), fn_name: f.to_string(), fn_hash: b.fn_hash.clone(), args: args.clone() };
758        self.foreign.ensure_cell(&cell).map_err(ForeignError::eval)?;
759        Ok(())
760    }
761}
762
763impl Inputs for Through<'_> {
764    fn read(&mut self, fn_name: &str, args: &Args) -> Result<Scalar, EvalError> {
765        self.pre(fn_name, args, None)?;
766        self.inner.read(fn_name, args)
767    }
768
769    fn read_cell(&mut self, fn_name: &str, args: &Args) -> Result<Input, EvalError> {
770        self.pre(fn_name, args, None)?;
771        self.inner.read_cell(fn_name, args)
772    }
773
774    fn read_asof(&mut self, fn_name: &str, args: &Args, t: &str) -> Result<Input, EvalError> {
775        self.pre(fn_name, args, Some(t))?;
776        self.inner.read_asof(fn_name, args, t)
777    }
778
779    fn read_slice(&mut self, fn_name: &str, pattern: &SlicePattern) -> Result<Vec<Member>, EvalError> {
780        if self.foreign.is_foreign(fn_name) {
781            self.foreign.ensure_name(fn_name).map_err(ForeignError::eval)?;
782            if let Some(b) = self.inner.binding_peek(fn_name, None)? {
783                if b.descriptor.lang == "stored" {
784                    return Err(ForeignError::unavailable(format!(
785                        "{fn_name}: slices of foreign stored functions are not read in 0.1.0"
786                    ))
787                    .eval());
788                }
789            }
790        }
791        self.inner.read_slice(fn_name, pattern)
792    }
793
794    fn read_versions(&mut self, fn_name: &str, args: &Args, from: &str, to: &str) -> Result<Vec<Input>, EvalError> {
795        self.pre(fn_name, args, None)?;
796        self.inner.read_versions(fn_name, args, from, to)
797    }
798
799    fn binding(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError> {
800        self.foreign.ensure_name(fn_name).map_err(ForeignError::eval)?;
801        self.inner.binding(fn_name, at)
802    }
803
804    fn asof(&mut self) -> String {
805        self.inner.asof()
806    }
807
808    fn binding_peek(&mut self, fn_name: &str, at: Option<&str>) -> Result<Option<FnBinding>, EvalError> {
809        self.foreign.ensure_name(fn_name).map_err(ForeignError::eval)?;
810        self.inner.binding_peek(fn_name, at)
811    }
812
813    fn asof_compare(&mut self, t: &str) -> Result<std::cmp::Ordering, EvalError> {
814        self.inner.asof_compare(t)
815    }
816}