jlens_schema/
shape.rs

1//! The structural metadata model and its inference from sample documents.
2
3use std::collections::BTreeMap;
4
5use indexmap::IndexMap;
6use serde::{Deserialize, Serialize};
7use serde_json::Value as JsonValue;
8
9/// Maximum number of distinct values tracked as enumeration candidates.
10const MAX_ENUM: usize = 10;
11/// Maximum number of examples kept per shape.
12const MAX_EXAMPLES: usize = 3;
13
14/// JSON types, as in JSON Schema (`integer` is a number without a fractional part).
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
16#[serde(rename_all = "lowercase")]
17pub enum JsonType {
18    /// `null`
19    Null,
20    /// `true` / `false`
21    Boolean,
22    /// A number without a fractional part.
23    Integer,
24    /// Any number.
25    Number,
26    /// A string.
27    String,
28    /// An array.
29    Array,
30    /// An object.
31    Object,
32}
33
34impl JsonType {
35    /// The JSON Schema name of the type.
36    pub fn name(self) -> &'static str {
37        match self {
38            JsonType::Null => "null",
39            JsonType::Boolean => "boolean",
40            JsonType::Integer => "integer",
41            JsonType::Number => "number",
42            JsonType::String => "string",
43            JsonType::Array => "array",
44            JsonType::Object => "object",
45        }
46    }
47
48    pub(crate) fn from_name(name: &str) -> Option<Self> {
49        Some(match name {
50            "null" => JsonType::Null,
51            "boolean" => JsonType::Boolean,
52            "integer" => JsonType::Integer,
53            "number" => JsonType::Number,
54            "string" => JsonType::String,
55            "array" => JsonType::Array,
56            "object" => JsonType::Object,
57            _ => return None,
58        })
59    }
60}
61
62/// The structure of the values found at one place in the documents.
63#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
64#[serde(rename_all = "camelCase")]
65pub struct Shape {
66    /// The types seen. `Integer` is dropped as soon as a non-integral number is seen.
67    pub types: Vec<JsonType>,
68    /// Fields of the objects, in first-seen order.
69    #[serde(skip_serializing_if = "IndexMap::is_empty", default)]
70    pub fields: IndexMap<String, Field>,
71    /// The shape of array items.
72    #[serde(skip_serializing_if = "Option::is_none", default)]
73    pub items: Option<Box<Shape>>,
74    /// Smallest number seen.
75    #[serde(skip_serializing_if = "Option::is_none", default)]
76    pub minimum: Option<f64>,
77    /// Largest number seen.
78    #[serde(skip_serializing_if = "Option::is_none", default)]
79    pub maximum: Option<f64>,
80    /// A string format shared by every string seen: `date-time`, `date`, `time`, `email`,
81    /// `uuid` or `uri`.
82    #[serde(skip_serializing_if = "Option::is_none", default)]
83    pub format: Option<String>,
84    /// The allowed values, when known (from an override, a JSON Schema, or inferred from a small
85    /// set of repeated values).
86    #[serde(rename = "enum", skip_serializing_if = "Option::is_none", default)]
87    pub enumeration: Option<Vec<JsonValue>>,
88    /// A few example values.
89    #[serde(skip_serializing_if = "Vec::is_empty", default)]
90    pub examples: Vec<JsonValue>,
91    /// What the value means.
92    #[serde(skip_serializing_if = "Option::is_none", default)]
93    pub description: Option<String>,
94    /// A short display name.
95    #[serde(skip_serializing_if = "Option::is_none", default)]
96    pub label: Option<String>,
97    /// Hidden values are not suggested by completion.
98    #[serde(skip_serializing_if = "std::ops::Not::not", default)]
99    pub hidden: bool,
100
101    // Inference state.
102    #[serde(skip)]
103    pub(crate) count: u64,
104    #[serde(skip)]
105    pub(crate) objects: u64,
106    #[serde(skip)]
107    pub(crate) strings: u64,
108    /// Distinct scalar values seen, `None` once there are too many.
109    #[serde(skip)]
110    pub(crate) distinct: Option<Vec<JsonValue>>,
111    /// The common string format so far: `None` before any string, `Some(None)` when they differ.
112    #[serde(skip)]
113    pub(crate) common_format: Option<Option<&'static str>>,
114}
115
116/// A field of an object shape.
117#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
118#[serde(rename_all = "camelCase")]
119pub struct Field {
120    /// The shape of the field's values.
121    pub shape: Shape,
122    /// Present in every object seen.
123    pub required: bool,
124    /// Fraction of the objects that have the field (1.0 when required).
125    pub presence: f64,
126}
127
128/// Structural metadata about a family of JSON documents.
129#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
130#[serde(rename_all = "camelCase")]
131pub struct Schema {
132    /// The shape of the documents themselves.
133    pub root: Shape,
134    /// Number of sample documents the schema was inferred from (0 when imported).
135    pub samples: u64,
136}
137
138impl Schema {
139    /// An empty schema, to be filled with [`Schema::observe`].
140    pub fn new() -> Self {
141        Schema::default()
142    }
143
144    /// Infers a schema from sample documents.
145    ///
146    /// ```
147    /// use jlens_schema::Schema;
148    /// use serde_json::json;
149    ///
150    /// let schema = Schema::infer(&[
151    ///     json!({"id": 1, "tags": ["a"], "owner": {"name": "Ann"}}),
152    ///     json!({"id": 2, "tags": [], "owner": null}),
153    /// ]);
154    /// let id = &schema.root.fields["id"];
155    /// assert!(id.required);
156    /// assert_eq!(id.shape.type_summary(), "integer");
157    /// assert_eq!(schema.root.fields["owner"].shape.type_summary(), "object | null");
158    /// ```
159    pub fn infer(samples: &[JsonValue]) -> Self {
160        let mut schema = Schema::new();
161        for sample in samples {
162            schema.observe(sample);
163        }
164        schema
165    }
166
167    /// Adds one more sample document.
168    pub fn observe(&mut self, sample: &JsonValue) {
169        self.samples += 1;
170        self.root.observe(sample);
171    }
172
173    /// The shape at a path such as `items[].type` (`[]` steps into array items; an empty path or
174    /// `$` is the root).
175    pub fn shape_at(&self, path: &str) -> Option<&Shape> {
176        let mut shape = &self.root;
177        for (name, arrays) in parse_path(path)? {
178            if let Some(name) = name {
179                shape = &shape.fields.get(&name)?.shape;
180            }
181            for _ in 0..arrays {
182                shape = shape.items.as_deref()?;
183            }
184        }
185        Some(shape)
186    }
187
188    fn shape_at_mut(&mut self, path: &str) -> Option<&mut Shape> {
189        let mut shape = &mut self.root;
190        for (name, arrays) in parse_path(path)? {
191            if let Some(name) = name {
192                shape = &mut shape.fields.get_mut(&name)?.shape;
193            }
194            for _ in 0..arrays {
195                shape = shape.items.as_deref_mut()?;
196            }
197        }
198        Some(shape)
199    }
200
201    /// Applies overrides: a map from paths (see [`Schema::shape_at`]) to settings. Unknown
202    /// paths are created, so overrides can also declare fields the samples did not contain.
203    /// Returns the paths that could not be applied.
204    ///
205    /// ```
206    /// use jlens_schema::{Override, Schema};
207    /// use serde_json::json;
208    ///
209    /// let mut schema = Schema::infer(&[json!({"items": [{"type": "a"}]})]);
210    /// let overrides: std::collections::BTreeMap<String, Override> = serde_json::from_value(json!({
211    ///     "items[].type": {"description": "Product category", "enum": ["a", "b", "c"]},
212    ///     "items[].internalCode": {"hidden": true}
213    /// })).unwrap();
214    /// assert!(schema.apply_overrides(&overrides).is_empty());
215    /// let ty = schema.shape_at("items[].type").unwrap();
216    /// assert_eq!(ty.description.as_deref(), Some("Product category"));
217    /// ```
218    pub fn apply_overrides(&mut self, overrides: &BTreeMap<String, Override>) -> Vec<String> {
219        let mut failed = Vec::new();
220        for (path, o) in overrides {
221            if self.shape_at(path).is_none() && !self.create_path(path) {
222                failed.push(path.clone());
223                continue;
224            }
225            let Some(shape) = self.shape_at_mut(path) else {
226                failed.push(path.clone());
227                continue;
228            };
229            if let Some(d) = &o.description {
230                shape.description = Some(d.clone());
231            }
232            if let Some(l) = &o.label {
233                shape.label = Some(l.clone());
234            }
235            if let Some(h) = o.hidden {
236                shape.hidden = h;
237            }
238            if let Some(e) = &o.enumeration {
239                shape.enumeration = Some(e.clone());
240            }
241            if let Some(f) = &o.format {
242                shape.format = Some(f.clone());
243            }
244            if let Some(types) = &o.types {
245                shape.types = types.clone();
246            }
247            if let Some(examples) = &o.examples {
248                shape.examples = examples.clone();
249            }
250        }
251        failed
252    }
253
254    fn create_path(&mut self, path: &str) -> bool {
255        let Some(steps) = parse_path(path) else {
256            return false;
257        };
258        let mut shape = &mut self.root;
259        for (name, arrays) in steps {
260            if let Some(name) = name {
261                if !shape.types.contains(&JsonType::Object) {
262                    shape.types.push(JsonType::Object);
263                }
264                shape = &mut shape
265                    .fields
266                    .entry(name)
267                    .or_insert_with(|| Field {
268                        presence: 0.0,
269                        ..Field::default()
270                    })
271                    .shape;
272            }
273            for _ in 0..arrays {
274                if !shape.types.contains(&JsonType::Array) {
275                    shape.types.push(JsonType::Array);
276                }
277                shape = shape.items.get_or_insert_with(Default::default);
278            }
279        }
280        true
281    }
282}
283
284/// Settings applied to the shape at one path (see [`Schema::apply_overrides`]).
285#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
286#[serde(rename_all = "camelCase", deny_unknown_fields)]
287pub struct Override {
288    /// What the value means.
289    pub description: Option<String>,
290    /// A short display name.
291    pub label: Option<String>,
292    /// Hide from completion.
293    pub hidden: Option<bool>,
294    /// The allowed values.
295    #[serde(rename = "enum")]
296    pub enumeration: Option<Vec<JsonValue>>,
297    /// The string format.
298    pub format: Option<String>,
299    /// The types, replacing the inferred ones.
300    #[serde(rename = "type")]
301    pub types: Option<Vec<JsonType>>,
302    /// Example values.
303    pub examples: Option<Vec<JsonValue>>,
304}
305
306/// Parses `a.b[].c` into `[(Some("a"), 0), (Some("b"), 1), (Some("c"), 0)]`.
307fn parse_path(path: &str) -> Option<Vec<(Option<String>, usize)>> {
308    let path = path.trim();
309    let path = path.strip_prefix('$').unwrap_or(path);
310    let path = path.strip_prefix('.').unwrap_or(path);
311    if path.is_empty() {
312        return Some(Vec::new());
313    }
314    let mut out = Vec::new();
315    for segment in path.split('.') {
316        let mut name = segment;
317        let mut arrays = 0;
318        while let Some(rest) = name.strip_suffix("[]") {
319            name = rest;
320            arrays += 1;
321        }
322        let name = name.trim_matches('`');
323        out.push(((!name.is_empty()).then(|| name.to_owned()), arrays));
324    }
325    Some(out)
326}
327
328impl Shape {
329    /// Records one value.
330    pub fn observe(&mut self, value: &JsonValue) {
331        self.count += 1;
332        let ty = match value {
333            JsonValue::Null => JsonType::Null,
334            JsonValue::Bool(_) => JsonType::Boolean,
335            JsonValue::Number(n) => {
336                let v = n.as_f64().unwrap_or(0.0);
337                self.minimum = Some(self.minimum.map_or(v, |m| m.min(v)));
338                self.maximum = Some(self.maximum.map_or(v, |m| m.max(v)));
339                // Respect how the number was written: `1500.0` is a number, `1500` an integer.
340                if (n.is_i64() || n.is_u64()) && v.fract() == 0.0 {
341                    JsonType::Integer
342                } else {
343                    JsonType::Number
344                }
345            }
346            JsonValue::String(s) => {
347                self.strings += 1;
348                let format = detect_format(s);
349                self.common_format = Some(match self.common_format {
350                    None => format,
351                    Some(prev) if prev == format => prev,
352                    Some(_) => None,
353                });
354                self.format = self.common_format.flatten().map(str::to_owned);
355                JsonType::String
356            }
357            JsonValue::Array(items) => {
358                let item_shape = self.items.get_or_insert_with(Default::default);
359                for item in items {
360                    item_shape.observe(item);
361                }
362                JsonType::Array
363            }
364            JsonValue::Object(map) => {
365                self.objects += 1;
366                for (k, v) in map {
367                    self.fields.entry(k.clone()).or_default().shape.observe(v);
368                }
369                for field in self.fields.values_mut() {
370                    field.required = field.shape.count == self.objects;
371                    field.presence = field.shape.count as f64 / self.objects as f64;
372                }
373                JsonType::Object
374            }
375        };
376        self.add_type(ty);
377        if matches!(
378            ty,
379            JsonType::String | JsonType::Integer | JsonType::Number | JsonType::Boolean
380        ) {
381            if self.count == 1 {
382                self.distinct = Some(Vec::new());
383            }
384            if let Some(distinct) = &mut self.distinct {
385                if !distinct.contains(value) {
386                    distinct.push(value.clone());
387                }
388                if distinct.len() > MAX_ENUM {
389                    self.distinct = None;
390                }
391            }
392            if self.examples.len() < MAX_EXAMPLES && !self.examples.contains(value) {
393                self.examples.push(value.clone());
394            }
395        } else if !matches!(ty, JsonType::Null) {
396            self.distinct = None;
397        }
398        // Repeated values from a small set look like an enumeration.
399        self.enumeration = self
400            .distinct
401            .as_ref()
402            .filter(|d| d.len() >= 2 && (d.len() as u64) < self.count)
403            .cloned();
404    }
405
406    fn add_type(&mut self, ty: JsonType) {
407        let ty = if ty == JsonType::Integer && self.types.contains(&JsonType::Number) {
408            JsonType::Number
409        } else {
410            ty
411        };
412        if ty == JsonType::Number {
413            self.types.retain(|t| *t != JsonType::Integer);
414        }
415        if !self.types.contains(&ty) {
416            self.types.push(ty);
417            self.types.sort();
418        }
419    }
420
421    /// Whether objects with fields were seen here.
422    pub fn is_object(&self) -> bool {
423        self.types.contains(&JsonType::Object)
424    }
425
426    /// A short type description: `string`, `array<object>`, `integer | null`, ...
427    pub fn type_summary(&self) -> String {
428        if self.types.is_empty() {
429            return "unknown".into();
430        }
431        let parts: Vec<String> = self
432            .types
433            .iter()
434            .filter(|t| **t != JsonType::Null)
435            .chain(self.types.iter().filter(|t| **t == JsonType::Null))
436            .map(|t| match t {
437                JsonType::Array => match &self.items {
438                    Some(items) if !items.types.is_empty() => {
439                        format!("array<{}>", items.type_summary())
440                    }
441                    _ => "array".into(),
442                },
443                other => other.name().into(),
444            })
445            .collect();
446        parts.join(" | ")
447    }
448}
449
450/// Recognizes common string formats.
451fn detect_format(s: &str) -> Option<&'static str> {
452    let b = s.as_bytes();
453    let digits =
454        |r: std::ops::Range<usize>| b.get(r).is_some_and(|d| d.iter().all(u8::is_ascii_digit));
455    let is_date = b.len() >= 10
456        && digits(0..4)
457        && b[4] == b'-'
458        && digits(5..7)
459        && b[7] == b'-'
460        && digits(8..10);
461    let is_time_at =
462        |i: usize| b.len() >= i + 5 && digits(i..i + 2) && b[i + 2] == b':' && digits(i + 3..i + 5);
463    if is_date && b.len() == 10 {
464        return Some("date");
465    }
466    if is_date && b.len() > 10 && matches!(b[10], b'T' | b't' | b' ') && is_time_at(11) {
467        return Some("date-time");
468    }
469    if is_time_at(0) && (b.len() == 5 || (b.len() >= 8 && b[5] == b':' && digits(6..8))) {
470        return Some("time");
471    }
472    let hex = |r: std::ops::Range<usize>| {
473        b.get(r)
474            .is_some_and(|d| d.iter().all(u8::is_ascii_hexdigit))
475    };
476    if b.len() == 36
477        && hex(0..8)
478        && b[8] == b'-'
479        && hex(9..13)
480        && b[13] == b'-'
481        && hex(14..18)
482        && b[18] == b'-'
483        && hex(19..23)
484        && b[23] == b'-'
485        && hex(24..36)
486    {
487        return Some("uuid");
488    }
489    if let Some((user, domain)) = s.split_once('@')
490        && !user.is_empty()
491        && !user.contains(char::is_whitespace)
492        && domain.contains('.')
493        && !domain.contains(['@', ' '])
494        && !domain.starts_with('.')
495        && !domain.ends_with('.')
496    {
497        return Some("email");
498    }
499    if let Some((scheme, rest)) = s.split_once("://")
500        && !scheme.is_empty()
501        && scheme
502            .chars()
503            .next()
504            .is_some_and(|c| c.is_ascii_alphabetic())
505        && scheme
506            .chars()
507            .all(|c| c.is_ascii_alphanumeric() || "+.-".contains(c))
508        && !rest.is_empty()
509        && !rest.contains(char::is_whitespace)
510    {
511        return Some("uri");
512    }
513    None
514}
515
516#[cfg(test)]
517mod tests {
518    use super::*;
519    use serde_json::json;
520
521    #[test]
522    fn infers_types_presence_and_items() {
523        let schema = Schema::infer(&[
524            json!({"id": 1, "price": 2.5, "items": [{"type": "a"}, {"type": "a", "extra": true}]}),
525            json!({"id": 2, "price": 3, "items": []}),
526        ]);
527        let root = &schema.root;
528        assert_eq!(root.fields["price"].shape.type_summary(), "number");
529        assert_eq!(root.fields["items"].shape.type_summary(), "array<object>");
530        let item = schema.shape_at("items[]").unwrap();
531        assert!(item.fields["type"].required);
532        assert!(!item.fields["extra"].required);
533        assert_eq!(item.fields["extra"].presence, 0.5);
534        assert_eq!(item.fields["type"].shape.enumeration, None);
535        assert_eq!(schema.shape_at("id").unwrap().minimum, Some(1.0));
536    }
537
538    #[test]
539    fn detects_formats_and_enumerations() {
540        let schema = Schema::infer(&[
541            json!({"at": "2024-01-02T10:00:00Z", "day": "2024-01-02", "mail": "a@b.co", "kind": "x"}),
542            json!({"at": "2024-01-03T11:30:00+01:00", "day": "2024-01-03", "mail": "c@d.org", "kind": "y"}),
543            json!({"at": "2024-01-04T12:00:00Z", "day": "2024-01-04", "mail": "e@f.io", "kind": "x"}),
544        ]);
545        let field = |n: &str| &schema.root.fields[n].shape;
546        assert_eq!(field("at").format.as_deref(), Some("date-time"));
547        assert_eq!(field("day").format.as_deref(), Some("date"));
548        assert_eq!(field("mail").format.as_deref(), Some("email"));
549        assert_eq!(
550            field("kind").enumeration,
551            Some(vec![json!("x"), json!("y")])
552        );
553        assert_eq!(field("mail").enumeration, None);
554    }
555
556    #[test]
557    fn paths() {
558        assert_eq!(
559            parse_path("$.items[].`a b`").unwrap(),
560            vec![(Some("items".into()), 1), (Some("a b".into()), 0)]
561        );
562        assert_eq!(parse_path("").unwrap(), vec![]);
563    }
564}
jlens_schema/shape.rs

jlens_schema/
shape.rs
