datumesh-http 0.3.3

The Datumesh engine behind HTTPS: cell envelopes, batches, slices (JSON and Arrow), receipts, jobs, verification and cross-mesh resolution; the datumesh-mesh server.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
//! `import-vectors`: the spec's vectors' cells into a store (see `deploy/README.md`).
//!
//! What it puts, and nothing else: the key documents of the receipt vectors (each retrieved
//! document) and of the formula vectors' hosts (the test keys of SPEC 11), merged per host;
//! every descriptor the vectors give (a receipt vector's, every formula and excel vector's
//! function, valid or not: a pinned request evaluates any of them); every receipt (each
//! verified by `put_receipt`); the manifests; the names the valid vectors bind (a name bound
//! to several functions keeps the first, reported), and the names only invalid vectors bind
//! (their first function); the stored cells' versions.

use std::collections::{BTreeMap, BTreeSet};
use std::path::Path;

use datumesh_core::json::{self, Value};
use datumesh_core::{keys_from_response, FunctionDescriptor, Manifest, Receipt, SigningKey};
use datumesh_store::Store;

use crate::publish::{PublishError, PublishErrorKind};

/// The formula vectors' conventions (SPEC 11): each host's key from the seed
/// SHA-256("datumesh formula test key: <host>"), valid from 2020-01-01.
const KEY_FROM: &str = "2020-01-01T00:00:00.000000Z";

fn files(dir: &Path, out: &mut Vec<std::path::PathBuf>) {
    let Ok(rd) = std::fs::read_dir(dir) else { return };
    let mut es: Vec<_> = rd.filter_map(Result::ok).map(|e| e.path()).collect();
    es.sort();
    for p in es {
        if p.is_dir() {
            files(&p, out);
        } else if p.extension().is_some_and(|e| e == "json") {
            out.push(p);
        }
    }
}

fn s(v: &str) -> Value {
    Value::String(v.to_string())
}

fn num(n: usize) -> Value {
    json::parse(n.to_string().as_bytes()).unwrap_or(Value::Null)
}

/// An excel vector's function (SPEC 11): `{"code": {"body": <body>, "lang": "formula"},
/// "inputs": <the derived inputs>, "signature": <signature>}`, the inputs the names its body
/// reads.
pub fn excel_descriptor(v: &Value) -> Option<Value> {
    let body = v.get("body")?.as_str()?;
    let ast = datumesh_formula::canonical_ast(body, None).ok()?;
    // The reads of the canonical AST (its JCS form: objects with "node": "read" and "fn").
    fn reads(v: &Value, out: &mut BTreeSet<String>) {
        match v {
            Value::Object(m) => {
                if v.get("node").and_then(Value::as_str) == Some("read") {
                    if let Some(f) = v.get("fn").and_then(Value::as_str) {
                        out.insert(f.to_string());
                    }
                }
                m.iter().for_each(|(_, x)| reads(x, out));
            }
            Value::Array(a) => a.iter().for_each(|x| reads(x, out)),
            _ => {}
        }
    }
    let mut names = BTreeSet::new();
    reads(&json::parse(&ast.to_jcs()).ok()?, &mut names);
    Some(Value::Object(vec![
        ("code".into(), Value::Object(vec![("body".into(), s(body)), ("lang".into(), s("formula"))])),
        ("inputs".into(), Value::Array(names.into_iter().map(|n| s(&n)).collect())),
        ("signature".into(), v.get("signature")?.clone()),
    ]))
}

/// Imports the vectors under `dir` (a spec's `vectors/`) into `store` (see the module docs);
/// a report as JSON: what was put, and what was refused or skipped.
/// The names the vectors in `dir` would bind: their worlds' functions, classes and class methods,
/// and the functions of their valid receipts whose descriptor is the receipt's cell's.
fn bound_names(dir: &Path) -> Vec<String> {
    let mut paths = Vec::new();
    files(dir, &mut paths);
    let mut out = Vec::new();
    for p in &paths {
        let Some(v) = std::fs::read(p).ok().and_then(|b| json::parse(&b).ok()) else { continue };
        let kind = v.get("kind").and_then(Value::as_str).unwrap_or("");
        if matches!(kind, "formula-eval" | "excel") {
            if let Some(w) = v.get("world") {
                for (name, _) in w.get("functions").and_then(Value::as_object).unwrap_or(&[]) {
                    out.push(name.clone());
                }
                for (cname, c) in w.get("classes").and_then(Value::as_object).unwrap_or(&[]) {
                    out.push(cname.clone());
                    let methods = c.get("descriptor").and_then(|d| d.get("methods")).and_then(Value::as_object);
                    for (m, _) in methods.unwrap_or(&[]) {
                        out.push(format!("{cname}/{m}"));
                    }
                }
            }
        }
        if kind == "receipt" && v.get("valid") == Some(&Value::Bool(true)) {
            let rc = v.get("recompute");
            let (Some(d), Some(text)) = (rc.and_then(|r| r.get("descriptor")), v.get("input").and_then(Value::as_str))
            else {
                continue;
            };
            let (Ok(fd), Ok(r)) = (FunctionDescriptor::from_value(d), Receipt::from_json(text.as_bytes())) else {
                continue;
            };
            if fd.hash() == r.cell().fn_hash {
                out.push(r.cell().function_name());
            }
        }
    }
    out
}

/// As [`import`], for a mesh whose own namespaces are `host` and `owned` (`import-vectors`): the
/// whole import is refused before any write when a name it would bind is under one of them
/// ([`PublishErrorKind::OwnedVectorName`]). Other names are exempt from rule A.
pub fn import_in<S: Store + ?Sized>(
    store: &S,
    dir: &Path,
    now: &str,
    host: &str,
    owned: &[String],
) -> Result<Value, PublishError> {
    let mine = |name: &str| {
        let h = name.split('/').next().unwrap_or("");
        h == host || owned.iter().any(|o| o == h)
    };
    if let Some(name) = bound_names(dir).into_iter().find(|n| mine(n)) {
        return Err(PublishError::typed(0, PublishErrorKind::OwnedVectorName(name)));
    }
    Ok(import(store, dir, now))
}

/// Imports the spec's vectors in `dir` into `store`, binding their names at `now` (see the
/// module documentation). The mesh's own namespaces are not checked: see [`import_in`].
pub fn import<S: Store + ?Sized>(store: &S, dir: &Path, now: &str) -> Value {
    let mut paths = Vec::new();
    files(dir, &mut paths);
    let vs: Vec<Value> = paths.iter().filter_map(|p| json::parse(&std::fs::read(p).ok()?).ok()).collect();
    let valid = |v: &Value| v.get("valid") == Some(&Value::Bool(true));
    let kind = |v: &Value| v.get("kind").and_then(Value::as_str).unwrap_or("").to_string();

    // Key documents: every valid receipt vector's retrieved documents and the formula
    // vectors' hosts' test keys, merged per host by key id.
    let mut keys: BTreeMap<String, BTreeMap<String, Value>> = BTreeMap::new();
    let mut world_hosts = BTreeSet::new();
    for v in &vs {
        if kind(v) == "receipt" && valid(v) {
            for (host, env) in v.get("keys").and_then(Value::as_object).unwrap_or(&[]) {
                let https = env.get("https");
                if https.and_then(|h| h.get("status")).and_then(Value::as_number_text) != Some("200") {
                    continue;
                }
                let Some(body) = https.and_then(|h| h.get("body")).and_then(Value::as_str) else { continue };
                if keys_from_response(host, 200, Some(body.as_bytes())).is_err() {
                    continue;
                }
                let doc = json::parse(body.as_bytes()).unwrap_or(Value::Null);
                if let Some(Value::Array(ks)) = doc.get("keys") {
                    for k in ks {
                        if let Some(id) = k.get("id").and_then(Value::as_str) {
                            keys.entry(host.clone()).or_default().entry(id.to_string()).or_insert_with(|| k.clone());
                        }
                    }
                }
            }
        }
        if matches!(kind(v).as_str(), "formula-eval" | "excel") {
            if let Some(w) = v.get("world") {
                for (name, _) in w.get("functions").and_then(Value::as_object).unwrap_or(&[]) {
                    world_hosts.insert(name.split('/').next().unwrap_or("").to_string());
                }
                if let Some(Value::Array(rs)) = w.get("receipts") {
                    for r in rs {
                        if let Some(h) = r.get("computed_by").and_then(Value::as_str) {
                            world_hosts.insert(h.split('#').next().unwrap_or("").to_string());
                        }
                    }
                }
            }
        }
    }
    for host in &world_hosts {
        let key =
            SigningKey::from_seed(&datumesh_core::sha256(format!("datumesh formula test key: {host}").as_bytes()));
        let k = Value::Object(vec![
            ("alg".into(), s("ed25519")),
            ("id".into(), s(key.key_id())),
            ("public".into(), s(&datumesh_core::lexical::to_hex(&key.public_key()))),
            ("valid_from".into(), s(KEY_FROM)),
        ]);
        keys.entry(host.clone()).or_default().entry(key.key_id().to_string()).or_insert(k);
    }
    let mut namespaces = 0;
    for (host, ks) in &keys {
        let doc = Value::Object(vec![
            ("host".into(), s(host)),
            ("keys".into(), Value::Array(ks.values().take(64).cloned().collect())),
            ("proto".into(), s("datumesh/1")),
        ])
        .to_jcs();
        if store.namespace(host).ok().flatten().map(|n| n.keydoc) != Some(doc.clone())
            && store.put_namespace(host, &doc, now).is_ok()
        {
            namespaces += 1;
        }
    }

    // Descriptors, receipts, manifests; candidate bindings and versions.
    let mut descriptors: BTreeMap<String, String> = BTreeMap::new(); // fn_hash -> lang
    let mut bindings: BTreeMap<String, Vec<(String, String)>> = BTreeMap::new(); // name -> (since, fn_hash)
    let mut invalid_bindings: BTreeMap<String, Vec<(String, String)>> = BTreeMap::new();
    let mut versions: BTreeMap<String, Vec<(String, String, String)>> = BTreeMap::new(); // cell id -> (tx, hash, fn_hash)
    let (mut receipts, mut refused, mut manifests) = (0usize, Vec::new(), 0usize);
    let mut blobs = 0usize;
    // Classes a vector world defines: name -> (bound, canonical descriptor bytes); a vector that cannot
    // be loaded through a store (its class names a method hash the world lacks, by design) is skipped.
    let mut classes: BTreeMap<String, (String, Vec<u8>)> = BTreeMap::new();
    let put_descriptor = |d: &Value, descriptors: &mut BTreeMap<String, String>| -> Option<String> {
        let fd = FunctionDescriptor::from_value(d).ok()?;
        let h = store.put_descriptor(&fd.canonical()).ok()?;
        descriptors.insert(h.clone(), fd.lang.clone());
        Some(h)
    };
    let mut put_receipt =
        |bytes: &[u8], id: &str, versions: &mut BTreeMap<String, Vec<(String, String, String)>>| match (
            store.put_receipt(bytes),
            Receipt::from_json(bytes),
        ) {
            (Ok(h), Ok(r)) => {
                receipts += 1;
                versions.entry(r.cell().id()).or_default().push((r.tx().to_string(), h, r.cell().fn_hash.clone()));
            }
            (Err(e), _) => refused.push(format!("{id}: {e}")),
            _ => {}
        };
    for v in &vs {
        let id = v.get("id").and_then(Value::as_str).unwrap_or("?").to_string();
        match kind(v).as_str() {
            "receipt" if valid(v) => {
                let Some(text) = v.get("input").and_then(Value::as_str) else { continue };
                let rc = v.get("recompute");
                if let (Some(d), Ok(r)) = (rc.and_then(|r| r.get("descriptor")), Receipt::from_json(text.as_bytes())) {
                    if let Some(h) = put_descriptor(d, &mut descriptors) {
                        if h == r.cell().fn_hash {
                            bindings.entry(r.cell().function_name()).or_default().push((r.tx().to_string(), h));
                        }
                    }
                }
                for (h, t) in rc.and_then(|r| r.get("inputs")).and_then(Value::as_object).unwrap_or(&[]) {
                    if let Some(t) = t.as_str() {
                        put_receipt(t.as_bytes(), &format!("{id} input {h}"), &mut versions);
                    }
                }
                for (_, t) in rc.and_then(|r| r.get("manifests")).and_then(Value::as_object).unwrap_or(&[]) {
                    if t.as_str().is_some_and(|t| store.put_manifest(t.as_bytes()).is_ok()) {
                        manifests += 1;
                    }
                }
                put_receipt(text.as_bytes(), &id, &mut versions);
            }
            "slice" if valid(v) => {
                if let Some(t) = v.get("input").and_then(Value::as_str) {
                    if Manifest::from_json(t.as_bytes()).is_ok() && store.put_manifest(t.as_bytes()).is_ok() {
                        manifests += 1;
                    }
                }
            }
            "formula-eval" | "excel" => {
                let rebound = id == "invalid/formula-eval-class-dispatch-rebound";
                // Every vector's functions (so a pinned request evaluates it), bound by name
                // from the valid ones only; an excel vector's function is its printed body
                // under its signature (SPEC 11), known by hash only.
                if kind(v) == "excel" {
                    if let Some(d) = excel_descriptor(v) {
                        put_descriptor(&d, &mut descriptors);
                    }
                }
                let Some(w) = v.get("world") else { continue };
                for (_, hex) in w.get("blobs").and_then(Value::as_object).unwrap_or(&[]) {
                    let bytes: Option<Vec<u8>> = hex.as_str().and_then(|h| {
                        (0..h.len()).step_by(2).map(|i| u8::from_str_radix(h.get(i..i + 2)?, 16).ok()).collect()
                    });
                    if let Some(b) = bytes {
                        if store.put_blob(&b).is_ok() {
                            blobs += 1;
                        }
                    }
                }
                for (name, f) in w.get("functions").and_then(Value::as_object).unwrap_or(&[]) {
                    let (Some(d), Some(b)) = (f.get("descriptor"), f.get("bound").and_then(Value::as_str)) else {
                        continue;
                    };
                    if let Some(h) = put_descriptor(d, &mut descriptors) {
                        let to = if valid(v) { &mut bindings } else { &mut invalid_bindings };
                        to.entry(name.clone()).or_default().push((b.to_string(), h));
                    }
                }
                if !rebound {
                    for (name, c) in w.get("classes").and_then(Value::as_object).unwrap_or(&[]) {
                        if let (Some(d), Some(b)) = (c.get("descriptor"), c.get("bound").and_then(Value::as_str)) {
                            classes.entry(name.clone()).or_insert_with(|| (b.to_string(), d.to_jcs()));
                        }
                    }
                }
                if let Some(Value::Array(rs)) = w.get("receipts") {
                    for r in rs {
                        put_receipt(&r.to_jcs(), &format!("{id} world"), &mut versions);
                    }
                }
            }
            _ => {}
        }
    }

    // Bindings: a name with one function is bound from its earliest instant; a name the
    // vectors bind to several functions keeps the first (one name means one function at a
    // time) and the others are reported.
    let (mut bound, mut skipped) = (0usize, Vec::new());
    // A class's methods are bound by `bind_class` (in one transaction with the class, at the same
    // instant a vector binds the function): leave those names to it.
    let json_of = |b: &[u8]| json::parse(b).unwrap_or(Value::Null);
    let mut by_class: BTreeSet<(String, String)> = BTreeSet::new();
    for (cname, (_, bytes)) in &classes {
        for (m, h) in json_of(bytes).get("methods").and_then(Value::as_object).unwrap_or(&[]) {
            if let Some(h) = h.as_str() {
                by_class.insert((format!("{cname}/{m}"), h.to_string()));
            }
        }
    }
    let method_names: BTreeSet<&String> = by_class.iter().map(|(n, _)| n).collect();
    bindings.retain(|n, _| !method_names.contains(n));
    invalid_bindings.retain(|n, _| !method_names.contains(n));
    for (name, cs) in invalid_bindings {
        bindings.entry(name).or_insert(cs);
    }
    for (name, cs) in &bindings {
        let hashes: BTreeSet<&String> = cs.iter().map(|(_, h)| h).collect();
        let (since, h) = cs.iter().filter(|(_, h)| *h == cs[0].1).min().cloned().unwrap_or_default();
        if hashes.len() > 1 {
            skipped.push(format!("{name}: {} functions, the first bound", hashes.len()));
        }
        match store.resolve_binding(name, "9999-12-31T23:59:59.999999Z") {
            Ok(Some(b)) if b.fn_hash == h => {}
            Ok(None) => {
                if store.bind_name(name, &h, &since).is_ok() {
                    bound += 1;
                }
            }
            _ => skipped.push(format!("{name}: already bound otherwise")),
        }
    }
    // Classes, after the functions: `put_class` (a parent first: retried until no more are stored) and
    // `bind_class` from `bound` (it binds the methods too).
    let mut classes_bound = 0usize;
    let mut pending: Vec<(String, String, Vec<u8>)> = classes.into_iter().map(|(n, (b, d))| (n, b, d)).collect();
    loop {
        let before = pending.len();
        pending.retain(|(name, since, bytes)| {
            let Ok(h) = store.put_class(bytes) else { return true };
            match store.resolve_class(name, "9999-12-31T23:59:59.999999Z") {
                Ok(Some(b)) if b == h => return false,
                Ok(None) => {}
                _ => return true,
            }
            match store.bind_class(name, &h, since) {
                Ok(()) => {
                    classes_bound += 1;
                    false
                }
                Err(_) => true,
            }
        });
        if pending.is_empty() || pending.len() == before {
            break;
        }
    }
    skipped.extend(pending.iter().map(|(n, _, _)| format!("{n}: class not stored or bound")));
    // Versions of stored functions' cells, in tx order (a second receipt at one tx is not a
    // version).
    let mut stored_versions = 0usize;
    for (cell_id, mut vs) in versions {
        vs.sort();
        vs.dedup_by(|a, b| a.0 == b.0);
        for (tx, hash, fn_hash) in vs {
            if descriptors.get(&fn_hash).map(String::as_str) != Some("stored") {
                continue;
            }
            match store.latest(&cell_id) {
                Ok(Some(l)) if l.tx >= tx => continue,
                _ => {}
            }
            if store.put_version(&cell_id, &tx, &hash).is_ok() {
                stored_versions += 1;
            }
        }
    }
    Value::Object(vec![
        ("bindings".into(), num(bound)),
        ("blobs".into(), num(blobs)),
        ("classes".into(), num(classes_bound)),
        ("bindings_skipped".into(), Value::Array(skipped.iter().map(|x| s(x)).collect())),
        ("descriptors".into(), num(descriptors.len())),
        ("manifests".into(), num(manifests)),
        ("namespaces".into(), num(namespaces)),
        ("receipts".into(), num(receipts)),
        ("receipts_refused".into(), Value::Array(refused.iter().map(|x| s(x)).collect())),
        ("versions".into(), num(stored_versions)),
    ])
}