datumesh_core/
slice.rs

1//! Slice objects (4.4) and manifests (15.13): slice-as-lineage, `spec-0.4.0`.
2
3use core::cmp::Ordering;
4
5use crate::descriptor::cmp_lexical;
6use crate::error::{err, index, member, Error, ErrorCode, Result};
7use crate::json::{self, jcs_sorted, Value};
8use crate::lexical::{self, limits};
9use crate::model::{self, Arg, Cell, Scalar, Type};
10use crate::receipt::Receipt;
11use crate::schema;
12
13/// How one argument of a slice object is given.
14#[derive(Clone, Debug, PartialEq, Eq, Hash)]
15enum SliceArg {
16    /// Bound to a typed scalar.
17    Value(Scalar),
18    /// The slice marker `"*"`: open.
19    Open,
20    /// A range object: bounded, both ends inclusive, in the type's order.
21    Range { ty: Type, lo: String, hi: String },
22}
23
24#[derive(Clone, Debug, PartialEq, Eq, Hash)]
25enum Kind {
26    /// A cell object with at least one open or ranged argument.
27    Cells { ns: String, fn_name: String, fn_hash: String, args: Vec<(String, SliceArg)> },
28    /// `{"cell", "from", "to"}`: the cell's versions with `tx` in `[from, to]`.
29    Versions { cell: Cell, from: String, to: String },
30}
31
32/// A slice object (4.4, `spec-0.4.0`): a cell object with at least one argument open (`"*"`)
33/// or bounded by a range object `{"hi", "lo", "type"}`, or a version slice
34/// `{"cell", "from", "to"}`. Its **slice id** is SHA-256 of its canonical bytes; for an
35/// unbounded slice it is the id of the cell object with the markers.
36///
37/// An object with exactly the members `cell`, `from` and `to` is a version slice; any other is
38/// read as a cell object. Within a cell object, an argument that is an object with exactly
39/// `hi`, `lo` and `type` is a range; any other object is read as a typed scalar.
40#[derive(Clone, Debug, PartialEq, Eq, Hash)]
41pub struct Slice {
42    kind: Kind,
43    canonical: Vec<u8>,
44    id: String,
45}
46
47impl Slice {
48    /// Parses a slice object from JSON text: strict JSON, structure (`E_SCHEMA`), canonical
49    /// form in JCS order (the codes of 3 and 4.5; a range's `type`, then `hi`, then `lo`;
50    /// `E_CANON_TYPE` for a boolean or blob range), then `E_SLICE` for a cell object without an
51    /// open or ranged argument, or a version slice whose cell has one.
52    pub fn from_json(bytes: &[u8]) -> Result<Slice> {
53        Slice::from_value(&json::parse(bytes)?)
54    }
55
56    /// Checks a parsed JSON value as a slice object.
57    pub fn from_value(v: &Value) -> Result<Slice> {
58        json::check_value_depth(v)?;
59        slice_structure(v, "$")?;
60        slice_canonical(v, "$")
61    }
62
63    /// The canonical bytes (6.2).
64    pub fn canonical(&self) -> Vec<u8> {
65        self.canonical.clone()
66    }
67
68    /// The slice id: SHA-256 of the canonical bytes, lowercase hex.
69    pub fn id(&self) -> &str {
70        &self.id
71    }
72
73    /// The JSON form.
74    pub fn to_value(&self) -> Value {
75        match &self.kind {
76            Kind::Cells { ns, fn_name, fn_hash, args } => cells_value(ns, fn_name, fn_hash, args),
77            Kind::Versions { cell, from, to } => Value::Object(vec![
78                ("cell".into(), cell.to_value()),
79                ("from".into(), Value::String(from.clone())),
80                ("to".into(), Value::String(to.clone())),
81            ]),
82        }
83    }
84
85    /// The fully qualified name of the slice's function, `<ns>/<fn>` (of the version slice's
86    /// cell for a version slice).
87    pub fn function_name(&self) -> String {
88        match &self.kind {
89            Kind::Cells { ns, fn_name, .. } => format!("{ns}/{fn_name}"),
90            Kind::Versions { cell, .. } => cell.function_name(),
91        }
92    }
93
94    /// The function hash the slice is over.
95    pub fn fn_hash(&self) -> &str {
96        match &self.kind {
97            Kind::Cells { fn_hash, .. } => fn_hash,
98            Kind::Versions { cell, .. } => &cell.fn_hash,
99        }
100    }
101
102    /// Whether this is a version slice (`{"cell", "from", "to"}`).
103    pub fn is_version_slice(&self) -> bool {
104        matches!(self.kind, Kind::Versions { .. })
105    }
106
107    /// Whether `receipt` belongs to the slice (10.1 step 7.5): for a cell object, the same
108    /// `ns`, `fn` and `fn_hash`, the same argument names, bound arguments equal, ranged
109    /// arguments of the range's type and within it, any value for an open argument; for a
110    /// version slice, the same cell with a `tx` in `[from, to]`. That no two members of a
111    /// slice are one cell is a property of the member set, checked by `verify`.
112    pub fn contains(&self, receipt: &Receipt) -> bool {
113        let c = receipt.cell();
114        match &self.kind {
115            Kind::Versions { cell, from, to } => {
116                c == cell && from.as_str() <= receipt.tx() && receipt.tx() <= to.as_str()
117            }
118            Kind::Cells { ns, fn_name, fn_hash, args } => {
119                if c.ns != *ns || c.fn_name != *fn_name || c.fn_hash != *fn_hash || c.args.len() != args.len() {
120                    return false;
121                }
122                args.iter().all(|(name, a)| match (a, c.args.get(name)) {
123                    (_, None | Some(Arg::Slice)) => false,
124                    (SliceArg::Open, Some(Arg::Value(_))) => true,
125                    (SliceArg::Value(want), Some(Arg::Value(got))) => want == got,
126                    (SliceArg::Range { ty, lo, hi }, Some(Arg::Value(got))) => {
127                        got.ty() == *ty
128                            && cmp_lexical(*ty, lo, got.lexical()) != Ordering::Greater
129                            && cmp_lexical(*ty, got.lexical(), hi) != Ordering::Greater
130                    }
131                })
132            }
133        }
134    }
135}
136
137fn cells_value(ns: &str, fn_name: &str, fn_hash: &str, args: &[(String, SliceArg)]) -> Value {
138    let args = args
139        .iter()
140        .map(|(k, a)| {
141            let v = match a {
142                SliceArg::Value(s) => s.to_value(),
143                SliceArg::Open => Value::String("*".into()),
144                SliceArg::Range { ty, lo, hi } => Value::Object(vec![
145                    ("hi".into(), Value::String(hi.clone())),
146                    ("lo".into(), Value::String(lo.clone())),
147                    ("type".into(), Value::String(ty.as_str().into())),
148                ]),
149            };
150            (k.clone(), v)
151        })
152        .collect();
153    Value::Object(vec![
154        ("args".into(), Value::Object(args)),
155        ("fn".into(), Value::String(fn_name.into())),
156        ("fn_hash".into(), Value::String(fn_hash.into())),
157        ("ns".into(), Value::String(ns.into())),
158    ])
159}
160
161fn is_version_slice(m: &[(String, Value)]) -> bool {
162    m.len() == 3 && ["cell", "from", "to"].iter().all(|k| schema::opt(m, k).is_some())
163}
164
165fn is_range(v: &Value) -> bool {
166    matches!(v, Value::Object(m) if m.len() == 3 && ["hi", "lo", "type"].iter().all(|k| schema::opt(m, k).is_some()))
167}
168
169fn slice_structure(v: &Value, path: &str) -> Result<()> {
170    let m = schema::object(v, path)?;
171    if is_version_slice(m) {
172        model::cell_structure(schema::get(m, "cell"), &member(path, "cell"))?;
173        schema::string(m, "from", path)?;
174        schema::string(m, "to", path)?;
175        return Ok(());
176    }
177    schema::exact(m, &["args", "fn", "fn_hash", "ns"], &[], path, ErrorCode::Schema)?;
178    let ap = member(path, "args");
179    for (k, a) in jcs_sorted(schema::object(schema::get(m, "args"), &ap)?) {
180        let p = member(&ap, k);
181        match a {
182            Value::String(s) if s == "*" => {}
183            Value::String(_) => return err(ErrorCode::Schema, &p, "an argument is a typed scalar, \"*\" or a range"),
184            r if is_range(r) => {
185                let rm = schema::object(r, &p)?;
186                for side in ["hi", "lo", "type"] {
187                    schema::string(rm, side, &p)?;
188                }
189            }
190            other => model::scalar_structure(other, &p)?,
191        }
192    }
193    schema::string(m, "fn", path)?;
194    schema::string(m, "fn_hash", path)?;
195    schema::string(m, "ns", path)?;
196    Ok(())
197}
198
199fn slice_canonical(v: &Value, path: &str) -> Result<Slice> {
200    let m = schema::object(v, path)?;
201    let kind = if is_version_slice(m) {
202        let cp = member(path, "cell");
203        let cell = model::cell_canonical(schema::get(m, "cell"), &cp)?;
204        if let Some((k, _)) = cell.args.iter().find(|(_, a)| **a == Arg::Slice) {
205            return err(ErrorCode::Slice, &member(&member(&cp, "args"), k), "a version slice is of one cell");
206        }
207        let from = schema::string(m, "from", path)?;
208        lexical::check_instant(from, &member(path, "from"))?;
209        let to = schema::string(m, "to", path)?;
210        lexical::check_instant(to, &member(path, "to"))?;
211        Kind::Versions { cell, from: from.into(), to: to.into() }
212    } else {
213        let ap = member(path, "args");
214        let am = schema::object(schema::get(m, "args"), &ap)?;
215        if am.len() > limits::ARGS {
216            return err(ErrorCode::CanonLimit, &ap, "more than 32 arguments");
217        }
218        let mut args = Vec::new();
219        for (k, a) in jcs_sorted(am) {
220            let p = member(&ap, k);
221            lexical::check_arg_name(k, &p)?;
222            let arg = match a {
223                Value::String(s) if s == "*" => SliceArg::Open,
224                r if is_range(r) => range_canonical(r, &p)?,
225                other => SliceArg::Value(model::scalar_canonical(other, &p)?),
226            };
227            args.push((k.clone(), arg));
228        }
229        let f = schema::string(m, "fn", path)?;
230        lexical::check_name(f, &member(path, "fn"))?;
231        let h = schema::string(m, "fn_hash", path)?;
232        lexical::check_hex(h, 64, &member(path, "fn_hash"))?;
233        let ns = schema::string(m, "ns", path)?;
234        lexical::check_namespace(ns, &member(path, "ns"))?;
235        if ns.len() + 1 + f.len() > limits::FUNCTION_NAME {
236            return err(ErrorCode::CanonLimit, path, "function name longer than 512 characters");
237        }
238        if !args.iter().any(|(_, a)| !matches!(a, SliceArg::Value(_))) {
239            return err(ErrorCode::Slice, &ap, "a slice object has an open or ranged argument");
240        }
241        args.sort_by(|a, b| a.0.cmp(&b.0));
242        Kind::Cells { ns: ns.into(), fn_name: f.into(), fn_hash: h.into(), args }
243    };
244    let mut s = Slice { kind, canonical: Vec::new(), id: String::new() };
245    s.canonical = s.to_value().to_jcs();
246    s.id = crate::crypto::sha256_hex(&s.canonical);
247    Ok(s)
248}
249
250/// A range object's canonical form: its `type` (one of `date`, `instant`, `number`,
251/// `string`; `E_CANON_TYPE`), then `hi` and `lo` in that type's lexical form. `lo` after `hi`
252/// is an empty range, not an error.
253fn range_canonical(v: &Value, path: &str) -> Result<SliceArg> {
254    let m = schema::object(v, path)?;
255    let tp = member(path, "type");
256    let ty = Type::parse(schema::string(m, "type", path)?, &tp)?;
257    if matches!(ty, Type::Boolean | Type::Blob) {
258        return err(ErrorCode::CanonType, &tp, format!("a {} argument has no range", ty.as_str()));
259    }
260    let hi = schema::string(m, "hi", path)?;
261    model::check_lexical(ty, hi, &member(path, "hi"))?;
262    let lo = schema::string(m, "lo", path)?;
263    model::check_lexical(ty, lo, &member(path, "lo"))?;
264    Ok(SliceArg::Range { ty, lo: lo.into(), hi: hi.into() })
265}
266
267/// A slice manifest (15.13, `spec-0.4.0`): `{"members": [...], "slice": {...}}`, the member
268/// receipt hashes (ascending, unique, at most 1,048,576) and the slice object. It is fetched
269/// by its **entry** `slice:<slice id>:<members hash>`, where the members hash is SHA-256 of the
270/// canonical bytes of the members array (of `[]` for an empty slice).
271#[derive(Clone, Debug, PartialEq, Eq, Hash)]
272pub struct Manifest {
273    slice: Slice,
274    members: Vec<String>,
275    members_hash: String,
276}
277
278impl Manifest {
279    /// Parses a manifest from JSON text: strict JSON; structure (`E_SCHEMA`) over the whole
280    /// manifest, the slice object's included; then the members (`E_CANON_HEX` for each, then
281    /// `E_CANON_SET` for their order, then `E_CANON_LIMIT`), then the slice object (see
282    /// [`Slice::from_json`]).
283    pub fn from_json(bytes: &[u8]) -> Result<Manifest> {
284        Manifest::from_value(&json::parse(bytes)?)
285    }
286
287    /// Checks a parsed JSON value as a manifest.
288    pub fn from_value(v: &Value) -> Result<Manifest> {
289        json::check_value_depth(v)?;
290        let m = schema::object(v, "$")?;
291        schema::exact(m, &["members", "slice"], &[], "$", ErrorCode::Schema)?;
292        let Value::Array(items) = schema::get(m, "members") else {
293            return err(ErrorCode::Schema, "$.members", "members is an array of receipt hashes");
294        };
295        if !items.iter().all(|i| matches!(i, Value::String(_))) {
296            return err(ErrorCode::Schema, "$.members", "members is an array of receipt hashes");
297        }
298        slice_structure(schema::get(m, "slice"), "$.slice")?;
299        let members: Vec<String> = items.iter().filter_map(Value::as_str).map(String::from).collect();
300        check_members(&members)?;
301        let slice = slice_canonical(schema::get(m, "slice"), "$.slice")?;
302        Ok(Manifest::unchecked(slice, members))
303    }
304
305    /// The manifest of `slice` with `members` (receipt hashes), checked as
306    /// [`from_json`](Self::from_json) checks them: each 64 lowercase hex digits
307    /// (`E_CANON_HEX`), strictly ascending (`E_CANON_SET`), at most 1,048,576
308    /// (`E_CANON_LIMIT`).
309    pub fn new(slice: Slice, members: Vec<String>) -> Result<Manifest> {
310        check_members(&members)?;
311        Ok(Manifest::unchecked(slice, members))
312    }
313
314    fn unchecked(slice: Slice, members: Vec<String>) -> Manifest {
315        let hash = crate::crypto::sha256_hex(&members_value(&members).to_jcs());
316        Manifest { slice, members, members_hash: hash }
317    }
318
319    /// The slice object.
320    pub fn slice(&self) -> &Slice {
321        &self.slice
322    }
323
324    /// The member receipt hashes, ascending.
325    pub fn members(&self) -> &[String] {
326        &self.members
327    }
328
329    /// SHA-256 of the canonical bytes of the members array, lowercase hex.
330    pub fn members_hash(&self) -> &str {
331        &self.members_hash
332    }
333
334    /// The `inputs` entry that cites this manifest: `slice:<slice id>:<members hash>`.
335    pub fn entry(&self) -> String {
336        format!("slice:{}:{}", self.slice.id(), self.members_hash)
337    }
338
339    /// The JSON form.
340    pub fn to_value(&self) -> Value {
341        Value::Object(vec![("members".into(), members_value(&self.members)), ("slice".into(), self.slice.to_value())])
342    }
343
344    /// The canonical bytes (6.2).
345    pub fn canonical(&self) -> Vec<u8> {
346        self.to_value().to_jcs()
347    }
348}
349
350fn members_value(members: &[String]) -> Value {
351    Value::Array(members.iter().map(|h| Value::String(h.clone())).collect())
352}
353
354fn check_members(members: &[String]) -> Result<()> {
355    for (i, h) in members.iter().enumerate() {
356        lexical::check_hex(h, 64, &index("$.members", i))?;
357    }
358    if members.windows(2).any(|w| w[0] >= w[1]) {
359        return err(ErrorCode::CanonSet, "$.members", "entries must be strictly ascending");
360    }
361    if members.len() > limits::MEMBERS {
362        return err(ErrorCode::CanonLimit, "$.members", "more than 1048576 members");
363    }
364    Ok(())
365}
366
367/// A manifest error reported inside an input entry: its path under `prefix`.
368pub(crate) fn nest(e: Error, prefix: &str) -> Error {
369    let inner = e.path().strip_prefix('$').unwrap_or(e.path()).to_string();
370    Error::new(e.code(), format!("{prefix}{inner}"), e.detail())
371}
datumesh_core/slice.rs

datumesh_core/
slice.rs
