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    /// The names of the open and ranged arguments, ascending: the dimensions of a member's key
103    /// (15.13); none for a version slice.
104    pub(crate) fn key_names(&self) -> Vec<String> {
105        match &self.kind {
106            Kind::Cells { args, .. } => {
107                let mut v: Vec<String> =
108                    args.iter().filter(|(_, a)| !matches!(a, SliceArg::Value(_))).map(|(k, _)| k.clone()).collect();
109                v.sort();
110                v
111            }
112            Kind::Versions { .. } => Vec::new(),
113        }
114    }
115
116    /// Whether this is a version slice (`{"cell", "from", "to"}`).
117    pub fn is_version_slice(&self) -> bool {
118        matches!(self.kind, Kind::Versions { .. })
119    }
120
121    /// Whether `receipt` belongs to the slice (10.1 step 7.5): for a cell object, the same
122    /// `ns`, `fn` and `fn_hash`, the same argument names, bound arguments equal, ranged
123    /// arguments of the range's type and within it, any value for an open argument; for a
124    /// version slice, the same cell with a `tx` in `[from, to]`. That no two members of a
125    /// slice are one cell is a property of the member set, checked by `verify`.
126    pub fn contains(&self, receipt: &Receipt) -> bool {
127        let c = receipt.cell();
128        match &self.kind {
129            Kind::Versions { cell, from, to } => {
130                c == cell && from.as_str() <= receipt.tx() && receipt.tx() <= to.as_str()
131            }
132            Kind::Cells { ns, fn_name, fn_hash, args } => {
133                if c.ns != *ns || c.fn_name != *fn_name || c.fn_hash != *fn_hash || c.args.len() != args.len() {
134                    return false;
135                }
136                args.iter().all(|(name, a)| match (a, c.args.get(name)) {
137                    (_, None | Some(Arg::Slice)) => false,
138                    (SliceArg::Open, Some(Arg::Value(_))) => true,
139                    (SliceArg::Value(want), Some(Arg::Value(got))) => want == got,
140                    (SliceArg::Range { ty, lo, hi }, Some(Arg::Value(got))) => {
141                        got.ty() == *ty
142                            && cmp_lexical(*ty, lo, got.lexical()) != Ordering::Greater
143                            && cmp_lexical(*ty, got.lexical(), hi) != Ordering::Greater
144                    }
145                })
146            }
147        }
148    }
149}
150
151fn cells_value(ns: &str, fn_name: &str, fn_hash: &str, args: &[(String, SliceArg)]) -> Value {
152    let args = args
153        .iter()
154        .map(|(k, a)| {
155            let v = match a {
156                SliceArg::Value(s) => s.to_value(),
157                SliceArg::Open => Value::String("*".into()),
158                SliceArg::Range { ty, lo, hi } => Value::Object(vec![
159                    ("hi".into(), Value::String(hi.clone())),
160                    ("lo".into(), Value::String(lo.clone())),
161                    ("type".into(), Value::String(ty.as_str().into())),
162                ]),
163            };
164            (k.clone(), v)
165        })
166        .collect();
167    Value::Object(vec![
168        ("args".into(), Value::Object(args)),
169        ("fn".into(), Value::String(fn_name.into())),
170        ("fn_hash".into(), Value::String(fn_hash.into())),
171        ("ns".into(), Value::String(ns.into())),
172    ])
173}
174
175fn is_version_slice(m: &[(String, Value)]) -> bool {
176    m.len() == 3 && ["cell", "from", "to"].iter().all(|k| schema::opt(m, k).is_some())
177}
178
179fn is_range(v: &Value) -> bool {
180    matches!(v, Value::Object(m) if m.len() == 3 && ["hi", "lo", "type"].iter().all(|k| schema::opt(m, k).is_some()))
181}
182
183fn slice_structure(v: &Value, path: &str) -> Result<()> {
184    let m = schema::object(v, path)?;
185    if is_version_slice(m) {
186        model::cell_structure(schema::get(m, "cell"), &member(path, "cell"))?;
187        schema::string(m, "from", path)?;
188        schema::string(m, "to", path)?;
189        return Ok(());
190    }
191    schema::exact(m, &["args", "fn", "fn_hash", "ns"], &[], path, ErrorCode::Schema)?;
192    let ap = member(path, "args");
193    for (k, a) in jcs_sorted(schema::object(schema::get(m, "args"), &ap)?) {
194        let p = member(&ap, k);
195        match a {
196            Value::String(s) if s == "*" => {}
197            Value::String(_) => return err(ErrorCode::Schema, &p, "an argument is a typed scalar, \"*\" or a range"),
198            r if is_range(r) => {
199                let rm = schema::object(r, &p)?;
200                for side in ["hi", "lo", "type"] {
201                    schema::string(rm, side, &p)?;
202                }
203            }
204            other => model::scalar_structure(other, &p)?,
205        }
206    }
207    schema::string(m, "fn", path)?;
208    schema::string(m, "fn_hash", path)?;
209    schema::string(m, "ns", path)?;
210    Ok(())
211}
212
213fn slice_canonical(v: &Value, path: &str) -> Result<Slice> {
214    let m = schema::object(v, path)?;
215    let kind = if is_version_slice(m) {
216        let cp = member(path, "cell");
217        let cell = model::cell_canonical(schema::get(m, "cell"), &cp)?;
218        if let Some((k, _)) = cell.args.iter().find(|(_, a)| **a == Arg::Slice) {
219            return err(ErrorCode::Slice, &member(&member(&cp, "args"), k), "a version slice is of one cell");
220        }
221        let from = schema::string(m, "from", path)?;
222        lexical::check_instant(from, &member(path, "from"))?;
223        let to = schema::string(m, "to", path)?;
224        lexical::check_instant(to, &member(path, "to"))?;
225        Kind::Versions { cell, from: from.into(), to: to.into() }
226    } else {
227        let ap = member(path, "args");
228        let am = schema::object(schema::get(m, "args"), &ap)?;
229        if am.len() > limits::ARGS {
230            return err(ErrorCode::CanonLimit, &ap, "more than 32 arguments");
231        }
232        let mut args = Vec::new();
233        for (k, a) in jcs_sorted(am) {
234            let p = member(&ap, k);
235            lexical::check_arg_name(k, &p)?;
236            let arg = match a {
237                Value::String(s) if s == "*" => SliceArg::Open,
238                r if is_range(r) => range_canonical(r, &p)?,
239                other => SliceArg::Value(model::scalar_canonical(other, &p)?),
240            };
241            args.push((k.clone(), arg));
242        }
243        let f = schema::string(m, "fn", path)?;
244        lexical::check_name(f, &member(path, "fn"))?;
245        let h = schema::string(m, "fn_hash", path)?;
246        lexical::check_hex(h, 64, &member(path, "fn_hash"))?;
247        let ns = schema::string(m, "ns", path)?;
248        lexical::check_namespace(ns, &member(path, "ns"))?;
249        if ns.len() + 1 + f.len() > limits::FUNCTION_NAME {
250            return err(ErrorCode::CanonLimit, path, "function name longer than 512 characters");
251        }
252        if !args.iter().any(|(_, a)| !matches!(a, SliceArg::Value(_))) {
253            return err(ErrorCode::Slice, &ap, "a slice object has an open or ranged argument");
254        }
255        args.sort_by(|a, b| a.0.cmp(&b.0));
256        Kind::Cells { ns: ns.into(), fn_name: f.into(), fn_hash: h.into(), args }
257    };
258    let mut s = Slice { kind, canonical: Vec::new(), id: String::new() };
259    s.canonical = s.to_value().to_jcs();
260    s.id = crate::crypto::sha256_hex(&s.canonical);
261    Ok(s)
262}
263
264/// A range object's canonical form: its `type` (one of `date`, `instant`, `number`,
265/// `string`; `E_CANON_TYPE`), then `hi` and `lo` in that type's lexical form. `lo` after `hi`
266/// is an empty range, not an error.
267fn range_canonical(v: &Value, path: &str) -> Result<SliceArg> {
268    let m = schema::object(v, path)?;
269    let tp = member(path, "type");
270    let ty = Type::parse(schema::string(m, "type", path)?, &tp)?;
271    if matches!(ty, Type::Boolean | Type::Blob) {
272        return err(ErrorCode::CanonType, &tp, format!("a {} argument has no range", ty.as_str()));
273    }
274    let hi = schema::string(m, "hi", path)?;
275    model::check_lexical(ty, hi, &member(path, "hi"))?;
276    let lo = schema::string(m, "lo", path)?;
277    model::check_lexical(ty, lo, &member(path, "lo"))?;
278    Ok(SliceArg::Range { ty, lo: lo.into(), hi: hi.into() })
279}
280
281/// A slice manifest (15.13, `spec-0.4.0`): `{"members": [...], "slice": {...}}`, the member
282/// receipt hashes (ascending, unique, at most 1,048,576) and the slice object. It is fetched
283/// by its **entry** `slice:<slice id>:<members hash>`, where the members hash is SHA-256 of the
284/// canonical bytes of the members array (of `[]` for an empty slice).
285#[derive(Clone, Debug, PartialEq, Eq, Hash)]
286pub struct Manifest {
287    slice: Slice,
288    members: Vec<String>,
289    members_hash: String,
290}
291
292impl Manifest {
293    /// Parses a manifest from JSON text: strict JSON; structure (`E_SCHEMA`) over the whole
294    /// manifest, the slice object's included; then the members (`E_CANON_HEX` for each, then
295    /// `E_CANON_SET` for their order, then `E_CANON_LIMIT`), then the slice object (see
296    /// [`Slice::from_json`]).
297    pub fn from_json(bytes: &[u8]) -> Result<Manifest> {
298        Manifest::from_value(&json::parse(bytes)?)
299    }
300
301    /// Checks a parsed JSON value as a manifest.
302    pub fn from_value(v: &Value) -> Result<Manifest> {
303        json::check_value_depth(v)?;
304        let m = schema::object(v, "$")?;
305        schema::exact(m, &["members", "slice"], &[], "$", ErrorCode::Schema)?;
306        let Value::Array(items) = schema::get(m, "members") else {
307            return err(ErrorCode::Schema, "$.members", "members is an array of receipt hashes");
308        };
309        if !items.iter().all(|i| matches!(i, Value::String(_))) {
310            return err(ErrorCode::Schema, "$.members", "members is an array of receipt hashes");
311        }
312        slice_structure(schema::get(m, "slice"), "$.slice")?;
313        let members: Vec<String> = items.iter().filter_map(Value::as_str).map(String::from).collect();
314        check_members(&members)?;
315        let slice = slice_canonical(schema::get(m, "slice"), "$.slice")?;
316        Ok(Manifest::unchecked(slice, members))
317    }
318
319    /// The manifest of `slice` with `members` (receipt hashes), checked as
320    /// [`from_json`](Self::from_json) checks them: each 64 lowercase hex digits
321    /// (`E_CANON_HEX`), strictly ascending (`E_CANON_SET`), at most 1,048,576
322    /// (`E_CANON_LIMIT`).
323    pub fn new(slice: Slice, members: Vec<String>) -> Result<Manifest> {
324        check_members(&members)?;
325        Ok(Manifest::unchecked(slice, members))
326    }
327
328    fn unchecked(slice: Slice, members: Vec<String>) -> Manifest {
329        let hash = crate::crypto::sha256_hex(&members_value(&members).to_jcs());
330        Manifest { slice, members, members_hash: hash }
331    }
332
333    /// The slice object.
334    pub fn slice(&self) -> &Slice {
335        &self.slice
336    }
337
338    /// The member receipt hashes, ascending.
339    pub fn members(&self) -> &[String] {
340        &self.members
341    }
342
343    /// SHA-256 of the canonical bytes of the members array, lowercase hex.
344    pub fn members_hash(&self) -> &str {
345        &self.members_hash
346    }
347
348    /// The `inputs` entry that cites this manifest: `slice:<slice id>:<members hash>`.
349    pub fn entry(&self) -> String {
350        format!("slice:{}:{}", self.slice.id(), self.members_hash)
351    }
352
353    /// The JSON form.
354    pub fn to_value(&self) -> Value {
355        Value::Object(vec![("members".into(), members_value(&self.members)), ("slice".into(), self.slice.to_value())])
356    }
357
358    /// The canonical bytes (6.2).
359    pub fn canonical(&self) -> Vec<u8> {
360        self.to_value().to_jcs()
361    }
362}
363
364fn members_value(members: &[String]) -> Value {
365    Value::Array(members.iter().map(|h| Value::String(h.clone())).collect())
366}
367
368fn check_members(members: &[String]) -> Result<()> {
369    for (i, h) in members.iter().enumerate() {
370        lexical::check_hex(h, 64, &index("$.members", i))?;
371    }
372    if members.windows(2).any(|w| w[0] >= w[1]) {
373        return err(ErrorCode::CanonSet, "$.members", "entries must be strictly ascending");
374    }
375    if members.len() > limits::MEMBERS {
376        return err(ErrorCode::CanonLimit, "$.members", "more than 1048576 members");
377    }
378    Ok(())
379}
380
381/// A manifest error reported inside an input entry: its path under `prefix`.
382pub(crate) fn nest(e: Error, prefix: &str) -> Error {
383    let inner = e.path().strip_prefix('$').unwrap_or(e.path()).to_string();
384    Error::new(e.code(), format!("{prefix}{inner}"), e.detail())
385}
datumesh_core/slice.rs

datumesh_core/
slice.rs
