corvus_json_schema/
instance.rs

1//! The instance values the evaluator reads: anything that can show itself as one of the six JSON kinds, with arrays and
2//! objects read in place. `&serde_json::Value` is one; a host language's own values (for example Python objects, read
3//! through its C API) can be another, so that evaluation needs no conversion to `serde_json::Value` first.
4
5use serde_json::{Map, Number, Value};
6
7/// A JSON value the evaluator can read in place. Cheap to copy (a reference or a handle); values reached through it
8/// (items, property values, strings) live as long as `'a`.
9pub trait Instance<'a>: Copy {
10    /// An array of instances.
11    type Array: ArrayView<'a, Item = Self>;
12    /// An object of named instances.
13    type Object: ObjectView<'a, Item = Self>;
14
15    /// The value's kind and content.
16    fn view(self) -> View<'a, Self>;
17
18    /// The value's kind alone (for type tests, which need no content).
19    #[inline]
20    fn kind(self) -> Kind {
21        match self.view() {
22            View::Null => Kind::Null,
23            View::Bool(_) => Kind::Bool,
24            View::Number(_) => Kind::Number,
25            View::String(_) => Kind::String,
26            View::Array(_) => Kind::Array,
27            View::Object(_) => Kind::Object,
28        }
29    }
30}
31
32/// The kind of a JSON value. The discriminants are the evaluator's type bits, so a type test is one mask operation
33/// (and a match that produces a kind compiles to a table, not a jump per value).
34#[derive(Clone, Copy, PartialEq, Eq, Debug)]
35#[repr(u8)]
36pub enum Kind {
37    Null = 1,
38    Bool = 2,
39    Object = 4,
40    Array = 8,
41    Number = 16,
42    String = 32,
43}
44
45/// What an instance is.
46pub enum View<'a, I: Instance<'a>> {
47    Null,
48    Bool(bool),
49    Number(Number),
50    String(&'a str),
51    Array(I::Array),
52    Object(I::Object),
53}
54
55/// The items of an array.
56pub trait ArrayView<'a>: Copy {
57    type Item: Instance<'a>;
58
59    fn len(self) -> usize;
60
61    fn is_empty(self) -> bool {
62        self.len() == 0
63    }
64
65    /// The item at an index (which must be below `len`).
66    fn get(self, index: usize) -> Self::Item;
67
68    fn iter(self) -> impl Iterator<Item = Self::Item>;
69
70    /// The items from an index on (none when it is past the end).
71    fn tail(self, start: usize) -> impl Iterator<Item = Self::Item> {
72        self.iter().skip(start)
73    }
74}
75
76/// The properties of an object, in their order.
77pub trait ObjectView<'a>: Copy {
78    type Item: Instance<'a>;
79
80    fn len(self) -> usize;
81
82    fn is_empty(self) -> bool {
83        self.len() == 0
84    }
85
86    /// The value of a property.
87    fn get(self, name: &str) -> Option<Self::Item>;
88
89    fn contains_key(self, name: &str) -> bool {
90        self.get(name).is_some()
91    }
92
93    fn iter(self) -> impl Iterator<Item = (&'a str, Self::Item)>;
94
95    fn values(self) -> impl Iterator<Item = Self::Item> {
96        self.iter().map(|(_, v)| v)
97    }
98}
99
100impl<'a> Instance<'a> for &'a Value {
101    type Array = &'a [Value];
102    type Object = &'a Map<String, Value>;
103
104    #[inline(always)]
105    fn view(self) -> View<'a, Self> {
106        match self {
107            Value::Null => View::Null,
108            Value::Bool(b) => View::Bool(*b),
109            Value::Number(n) => View::Number(n.clone()),
110            Value::String(s) => View::String(s),
111            Value::Array(a) => View::Array(a.as_slice()),
112            Value::Object(o) => View::Object(o),
113        }
114    }
115
116    #[inline(always)]
117    fn kind(self) -> Kind {
118        match self {
119            Value::Null => Kind::Null,
120            Value::Bool(_) => Kind::Bool,
121            Value::Number(_) => Kind::Number,
122            Value::String(_) => Kind::String,
123            Value::Array(_) => Kind::Array,
124            Value::Object(_) => Kind::Object,
125        }
126    }
127}
128
129impl<'a> ArrayView<'a> for &'a [Value] {
130    type Item = &'a Value;
131
132    #[inline(always)]
133    fn len(self) -> usize {
134        <[Value]>::len(self)
135    }
136
137    #[inline(always)]
138    fn get(self, index: usize) -> &'a Value {
139        &self[index]
140    }
141
142    #[inline(always)]
143    fn iter(self) -> impl Iterator<Item = &'a Value> {
144        <[Value]>::iter(self)
145    }
146
147    #[inline(always)]
148    fn tail(self, start: usize) -> impl Iterator<Item = &'a Value> {
149        self.get(start..).unwrap_or_default().iter()
150    }
151}
152
153/// Objects up to this size are searched by scanning their keys: comparing lengths first, that is cheaper than hashing
154/// the name with serde_json's SipHash.
155const LINEAR_KEYS: usize = 32;
156
157impl<'a> ObjectView<'a> for &'a Map<String, Value> {
158    type Item = &'a Value;
159
160    #[inline(always)]
161    fn len(self) -> usize {
162        Map::len(self)
163    }
164
165    #[inline]
166    fn get(self, name: &str) -> Option<&'a Value> {
167        if Map::len(self) <= LINEAR_KEYS {
168            Map::iter(self).find(|(k, _)| str_eq(k, name)).map(|(_, v)| v)
169        } else {
170            Map::get(self, name)
171        }
172    }
173
174    #[inline]
175    fn contains_key(self, name: &str) -> bool {
176        if Map::len(self) <= LINEAR_KEYS { self.keys().any(|k| str_eq(k, name)) } else { Map::contains_key(self, name) }
177    }
178
179    #[inline(always)]
180    fn iter(self) -> impl Iterator<Item = (&'a str, &'a Value)> {
181        Map::iter(self).map(|(k, v)| (k.as_str(), v))
182    }
183
184    #[inline(always)]
185    fn values(self) -> impl Iterator<Item = &'a Value> {
186        Map::values(self)
187    }
188}
189
190/// String equality with the length test and short comparisons inline (property names are short).
191#[inline(always)]
192pub(crate) fn str_eq(a: &str, b: &str) -> bool {
193    let (a, b) = (a.as_bytes(), b.as_bytes());
194    if a.len() != b.len() {
195        return false;
196    }
197    let n = a.len();
198    if n <= 8 {
199        if n >= 4 {
200            // Two overlapping four-byte words cover every byte (one load each, no per-byte bounds checks).
201            let word = |s: &[u8], i: usize| u32::from_le_bytes(s[i..i + 4].try_into().unwrap());
202            return word(a, 0) == word(b, 0) && word(a, n - 4) == word(b, n - 4);
203        }
204        return a == b;
205    }
206    // Eight-byte words from the start, then one ending at the last byte (overlapping the previous one): property names
207    // are short enough that a call to memcmp costs more than the compare.
208    let word = |s: &[u8], i: usize| u64::from_le_bytes(s[i..i + 8].try_into().unwrap());
209    let mut i = 0;
210    while i + 8 < n {
211        if word(a, i) != word(b, i) {
212            return false;
213        }
214        i += 8;
215    }
216    word(a, n - 8) == word(b, n - 8)
217}
218
219// The kinds are the evaluator's type bits.
220const _: () = {
221    use crate::node::type_mask;
222    assert!(Kind::Null as u8 == type_mask::NULL);
223    assert!(Kind::Bool as u8 == type_mask::BOOLEAN);
224    assert!(Kind::Object as u8 == type_mask::OBJECT);
225    assert!(Kind::Array as u8 == type_mask::ARRAY);
226    assert!(Kind::Number as u8 == type_mask::NUMBER);
227    assert!(Kind::String as u8 == type_mask::STRING);
228};
corvus_json_schema/instance.rs

corvus_json_schema/
instance.rs
